EITC/AI/ARL Apprendimento per rinforzo avanzato

L'apprendimento per rinforzo differisce dall'apprendimento supervisionato in quanto non è necessario presentare coppie di input/output etichettati e non è necessario correggere esplicitamente azioni subottimali. L'attenzione è invece sulla ricerca di un equilibrio tra esplorazione (di territori inesplorati) e sfruttamento (delle conoscenze attuali).

L'ambiente è tipicamente definito sotto forma di un processo decisionale markoviano (MDP), perché molti algoritmi di apprendimento per rinforzo per questo contesto utilizzano tecniche di programmazione dinamica. La principale differenza tra i metodi classici di programmazione dinamica e gli algoritmi di apprendimento per rinforzo è che questi ultimi non presuppongono la conoscenza di un modello matematico esatto dell'MDP e si rivolgono a MDP di grandi dimensioni in cui i metodi esatti diventano irrealizzabili.

A causa della sua generalità, l'apprendimento per rinforzo è studiato in molte discipline, come teoria dei giochi, teoria del controllo, ricerca operativa, teoria dell'informazione, ottimizzazione basata sulla simulazione, sistemi multi-agente, swarm intelligence e statistica. Nella letteratura sulla ricerca operativa e sul controllo, l'apprendimento per rinforzo è chiamato programmazione dinamica approssimata o programmazione neuro-dinamica. I problemi di interesse nell'apprendimento per rinforzo sono stati studiati anche nella teoria del controllo ottimale, che riguarda principalmente l'esistenza e la caratterizzazione di soluzioni ottimali e algoritmi per il loro calcolo esatto, e meno l'apprendimento o l'approssimazione, in particolare in assenza di un modello matematico dell'ambiente. In economia e teoria dei giochi, l'apprendimento per rinforzo può essere utilizzato per spiegare come può sorgere l'equilibrio sotto una razionalità limitata.

Il rinforzo di base è modellato come un processo decisionale Markoviano (MDP). In matematica, un processo decisionale Markoviano (MDP) è un processo di controllo stocastico a tempo discreto. Fornisce un quadro matematico per modellare il processo decisionale in situazioni in cui i risultati sono in parte casuali e in parte sotto il controllo di un decisore. Gli MDP sono utili per studiare i problemi di ottimizzazione risolti tramite la programmazione dinamica. Gli MDP erano noti almeno negli anni '1950. Un nucleo centrale di ricerca sui processi decisionali di Markov è il risultato del libro di Ronald Howard del 1960, Dynamic Programming and Markov Processes. Sono utilizzati in molte discipline, tra cui robotica, controllo automatico, economia e produzione. Il nome degli MDP deriva dal matematico russo Andrey Markov in quanto sono un'estensione delle catene di Markov.

In ogni fase temporale, il processo si trova in uno stato S e il decisore può scegliere qualsiasi azione a disponibile nello stato S. Il processo risponde nella fase temporale successiva spostandosi in modo casuale in un nuovo stato S 'e dando il al decisore una ricompensa corrispondente Ra (S, S ').

La probabilità che il processo si sposti nel suo nuovo stato S 'è influenzata dall'azione scelta a. Nello specifico, è dato dalla funzione di transizione di stato Pa (S, S '). Pertanto, il successivo stato S 'dipende dallo stato corrente S e dall'azione del decisore a. Ma dati S e a, è condizionatamente indipendente da tutti gli stati e le azioni precedenti. In altre parole, le transizioni di stato di un MDP soddisfano la proprietà Markov.

I processi decisionali di Markov sono un'estensione delle catene di Markov; la differenza è l'aggiunta di azioni (consentire la scelta) e ricompense (dare motivazione). Al contrario, se esiste una sola azione per ogni stato (es. "Aspetta") e tutte le ricompense sono le stesse (es. "Zero"), un processo decisionale markoviano si riduce a una catena markoviana.

Un agente di apprendimento per rinforzo interagisce con il suo ambiente in fasi temporali discrete. Ad ogni istante t, l'agente riceve lo stato corrente S (t) e la ricompensa r (t). Quindi sceglie un'azione a (t) dall'insieme di azioni disponibili, che viene successivamente inviata all'ambiente. L'ambiente si sposta in un nuovo stato S (t + 1) e viene determinata la ricompensa r (t + 1) associata alla transizione. L'obiettivo di un agente di apprendimento per rinforzo è apprendere una politica che massimizzi la ricompensa cumulativa attesa.

Formulare il problema come MDP presuppone che l'agente osservi direttamente lo stato ambientale corrente. In questo caso si dice che il problema ha piena osservabilità. Se l'agente ha accesso solo a un sottoinsieme di stati, o se gli stati osservati sono corrotti dal rumore, si dice che l'agente ha un'osservabilità parziale e formalmente il problema deve essere formulato come un processo decisionale markoviano parzialmente osservabile. In entrambi i casi, l'insieme di azioni disponibili per l'agente può essere limitato. Ad esempio, lo stato del saldo di un conto potrebbe essere limitato a essere positivo; se il valore corrente dello stato è 3 e la transizione di stato tenta di ridurre il valore di 4, la transizione non sarà consentita.

Quando le prestazioni dell'agente vengono confrontate con quelle di un agente che agisce in modo ottimale, la differenza di prestazioni dà origine alla nozione di rimpianto. Per agire in modo quasi ottimale, l'agente deve ragionare sulle conseguenze a lungo termine delle sue azioni (ovvero massimizzare il reddito futuro), sebbene la ricompensa immediata associata a ciò potrebbe essere negativa.

Pertanto, l'apprendimento per rinforzo è particolarmente adatto a problemi che includono un compromesso di ricompensa a lungo termine rispetto a quello a breve termine. È stato applicato con successo a vari problemi, tra cui il controllo del robot, la programmazione degli ascensori, le telecomunicazioni, il backgammon, la dama e il Go (AlphaGo).

Due elementi rendono potente l'apprendimento per rinforzo: l'uso di campioni per ottimizzare le prestazioni e l'uso dell'approssimazione delle funzioni per gestire ambienti di grandi dimensioni. Grazie a queste due componenti chiave, l'apprendimento per rinforzo può essere utilizzato in ambienti di grandi dimensioni nelle seguenti situazioni:

• È noto un modello dell'ambiente, ma non è disponibile una soluzione analitica.
• Viene fornito solo un modello di simulazione dell'ambiente (oggetto dell'ottimizzazione basata sulla simulazione).
• L'unico modo per raccogliere informazioni sull'ambiente è interagire con esso.

I primi due di questi problemi potrebbero essere considerati problemi di pianificazione (poiché è disponibile una qualche forma di modello), mentre l'ultimo potrebbe essere considerato un vero problema di apprendimento. Tuttavia, l'apprendimento per rinforzo converte entrambi i problemi di pianificazione in problemi di apprendimento automatico.

Il compromesso tra esplorazione e sfruttamento è stato studiato in modo più approfondito attraverso il problema dei banditi multi-armati e per gli MDP nello spazio degli stati finiti in Burnetas e Katehakis (1997).

L'apprendimento per rinforzo richiede meccanismi di esplorazione intelligenti; la selezione casuale di azioni, senza riferimento a una distribuzione di probabilità stimata, mostra prestazioni scadenti. Il caso dei processi decisionali (piccoli) finiti di Markov è relativamente ben compreso. Tuttavia, a causa della mancanza di algoritmi che si adattano bene al numero di stati (o scalano a problemi con spazi di stato infiniti), i metodi di esplorazione semplici sono i più pratici.

Anche se la questione dell'esplorazione viene ignorata e anche se lo stato fosse osservabile, resta il problema di utilizzare l'esperienza passata per scoprire quali azioni portano a ricompense cumulative più elevate.