Model Free Control Flashcards
Cos’è il model-free control?
Il model-free control è un paradigma nell’apprendimento per rinforzo che si concentra sull’apprendimento di politiche decisionali ottimali direttamente dall’esperienza, senza avere una conoscenza esplicita del modello dell’ambiente.
In termini più semplici, il model-free control riguarda l’addestramento di agenti di apprendimento in modo tale che possano prendere decisioni ottimali basandosi esclusivamente sull’esperienza accumulata interagendo con l’ambiente, senza dover costruire o fare ipotesi sul funzionamento interno dell’ambiente stesso
Cos’è l’on-policy e l’off-policy learning?
On-Policy Learning:
Nell’on-policy learning, l’agente apprende e ottimizza una politica π basandosi sull’esperienza generata seguendo la stessa politica π. L’aggiornamento dei valori di stato-azione (come i valori Q) e la valutazione della politica sono effettuati utilizzando dati provenienti dall’esperienza di eseguire azioni secondo la politica corrente.
La valutazione della politica e l’aggiornamento dei valori Q seguono la stessa politica π che l’agente sta attualmente utilizzando per esplorare l’ambiente.
Off-Policy Learning:
Nell’off-policy learning, l’agente apprende e valuta una politica π_target utilizzando dati provenienti da un’altra politica π_behavior, che potrebbe essere differente dalla politica obiettivo.
L’agente può apprendere da esperienze generate da politiche diverse da quella che sta cercando di ottimizzare. Un esempio è il Q-learning, dove l’agente apprende ad aggiornare i valori Q utilizzando la politica che massimizza i valori Q, indipendentemente dalle azioni intraprese dall’attuale politica.
Cos’è la esplorazione epsilon-greedy?
Concetto di Base:
Nell’apprendimento per rinforzo, un agente deve bilanciare tra esplorare l’ambiente per scoprire nuove informazioni e sfruttare le conoscenze già acquisite per massimizzare le ricompense a lungo termine. L’approccio epsilon-greedy mira a questa bilancia.
Funzionamento:
Greedy Exploitation (Sfruttamento avido): L’agente sceglie l’azione che attualmente sembra migliore, basandosi sui valori stimati delle azioni (come i valori Q in Q-learning). Questo è lo sfruttamento delle conoscenze attuali per massimizzare le ricompense a breve termine.
Epsilon-Greedy Exploration (Esplorazione epsilon-greedy): Tuttavia, con una probabilità ϵ (epsilon), l’agente opta per un’azione casuale, ignorando temporaneamente le informazioni ottimali attualmente conosciute. Questo comportamento di esplorazione consente di scoprire nuove azioni o stati che potrebbero portare a ricompense più elevate a lungo termine.
Scelta di Epsilon:
Il valore di ϵ è cruciale. Se è troppo basso, l’agente potrebbe rimanere bloccato in azioni subottimali. Se è troppo alto, l’agente potrebbe esplorare troppo senza sfruttare le informazioni acquisite.
Vantaggi:
Bilancio tra esplorazione e sfruttamento: Permette all’agente di trovare un equilibrio ottimale tra esplorare nuove azioni e sfruttare quelle attualmente considerate migliori.
Limitazioni:
Fissaggio di ϵ: Trovare il valore ottimale di ϵ per un problema specifico può essere complesso e richiedere sperimentazioni.
Stallo in ottimi locali: Se ϵ è troppo basso, l’agente potrebbe restare bloccato in azioni subottimali senza esplorare sufficientemente.
Formulazione Matematica Semplificata:
L’agente sceglie un’azione casuale con probabilità ϵ e l’azione ottimale con probabilità −1−ϵ.
Questa strategia epsilon-greedy è una delle tecniche di esplorazione più utilizzate nell’apprendimento per rinforzo, poiché consente di trovare un equilibrio tra esplorazione e sfruttamento delle informazioni.
teorema epsilon-greedy policy improvement
Il teorema dell’epsilon-greedy policy improvement afferma che, per ogni policy epsilon-greedy π, esiste una policy epsilon-greedy π’ rispetto a q_π che è un miglioramento, nel senso che la value function di π’ è maggiore o uguale alla value function di π per tutti gli stati.
Ecco una spiegazione più dettagliata:
Policy Epsilon-Greedy: Una policy epsilon-greedy è una strategia di esplorazione e sfruttamento comunemente utilizzata nell’apprendimento per rinforzo. Con probabilità 1 - ε si sceglie l’azione migliore secondo la stima corrente della value function (sfruttamento), mentre con probabilità ε si sceglie un’azione casuale (esplorazione).
Policy Improvement: Il teorema dice che possiamo sempre trovare una nuova policy (denotata come π’) che è almeno altrettanto buona della policy attuale (π) rispetto alla value function q_π, nel senso che la value function di π’ è maggiore o uguale alla value function di π per tutti gli stati.
Convergenza: Se l’algoritmo di apprendimento esplora abbastanza (cioè, se ε è sufficientemente grande) e si eseguono un numero sufficientemente grande di iterazioni, l’epsilon-greedy policy improvement può convergere a una policy ottimale. Questo significa che, con il tempo, la policy trovata diventa sempre migliore, fino a raggiungere l’ottimalità (cioè, scegliere sempre l’azione migliore in ogni stato).
Numero di Campioni (k): La convergenza dipende anche dal numero di campioni (k), ovvero quanti esempi vengono considerati durante l’apprendimento. Se il numero di campioni tende all’infinito, e se ε è abbastanza grande, l’algoritmo epsilon-greedy policy improvement può convergere all’ottimalità.
In breve, l’epsilon-greedy policy improvement è un metodo per migliorare gradualmente la policy di decisione in un problema di apprendimento per rinforzo, garantendo che l’esplorazione venga bilanciata con lo sfruttamento e che la policy converga a una soluzione ottimale nel lungo termine.
Cos’è il GLIE?
GLIE sta per “Greedy in the Limit with Infinite Exploration”, un concetto nell’ambito dell’apprendimento per rinforzo che esprime una condizione sotto la quale un algoritmo di apprendimento si comporta in modo “avidamente ottimale” nell’apprendimento asintotico.
Concetto di Base:
L’obiettivo principale nell’apprendimento per rinforzo è che un agente diventi sempre più abile nell’interagire con un ambiente per massimizzare le ricompense totali. Nella pratica, vogliamo che l’agente apprenda una politica ottimale, cioè una politica che massimizza le ricompense nel lungo termine.
Greedy in the Limit with Infinite Exploration (GLIE):
GLIE è una condizione che assicura che un algoritmo di apprendimento per rinforzo esplori in modo sufficiente (infinite exploration) e tenda a diventare sempre più avidamente ottimale (greedy) nell’apprendimento asintotico, cioè con un numero infinito di passi temporali.
Elementi Chiave della Condizione GLIE:
Esplorazione Infinita: L’algoritmo deve garantire una forma di esplorazione continua e infinita, assicurandosi che tutte le azioni abbiano la possibilità di essere selezionate, anche se con probabilità minima.
Convergenza all’ottimalità (Greedy): L’algoritmo deve tendere a diventare sempre più avidamente ottimale. Ciò significa che, nel lungo termine, l’agente dovrebbe preferire sempre più le azioni che massimizzano le ricompense attese.
Utilità della Condizione GLIE:
Convergenza alla Politica Ottimale: La condizione GLIE fornisce un’assicurazione teorica che l’algoritmo di apprendimento per rinforzo tenda a convergere a una politica ottimale, massimizzando le ricompense nel lungo termine.
Bilancio tra Esplorazione e Sfruttamento: Garantisce che l’agente continui a esplorare l’ambiente per scoprire nuove azioni, ma tenda gradualmente a selezionare sempre più frequentemente le azioni che sembrano essere ottimali.
Cos’è SARSA?
SARSA è un algoritmo di apprendimento per rinforzo on-policy basato su metodi Temporal-Difference (TD) che permette di apprendere una politica ottimale.
Funzionamento di SARSA (in modo formale):
- Aggiornamento dei valori Q durante l’esplorazione dell’ambiente.
- Sia Q(s, a) il valore Q per lo stato s e l’azione a.
- Ad ogni passo:
- L’agente esegue un’azione a nello stato s e osserva la ricompensa R.
- Passa allo stato successivo s’ seguendo una politica π.
- Sceglie un’azione a’ in s’ basandosi su π (ad esempio, ε-greedy).
- Aggiornamento dei valori Q in SARSA:
Q(s, a) ← Q(s, a) + α * [ R + γ * Q(s’, a’) - Q(s, a) ]
Convergenza di SARSA:
- La convergenza non è garantita in tutti i casi.
- Può convergere a una politica ottimale sotto alcune condizioni.
- Requisiti per la convergenza:
- Politica stabile durante l’apprendimento.
- Esplorazione continua per garantire visite infinite degli stati.
- Limitazioni e considerazioni:
- Sensibile al tasso di apprendimento e alla politica di esplorazione.
- La convergenza può richiedere tempo in ambienti complessi.
La convergenza di SARSA non è garantita in tutti i casi, ma può convergere a una politica ottimale sotto alcune condizioni. Se l’ambiente è stazionario e le visite degli stati sono infinite, con un tasso di apprendimento correttamente selezionato, SARSA può convergere alla politica ottimale.
Cos’è l’n-step SARSA(λ)?
n-step SARSA:
- Estensione di SARSA che considera una sequenza di n passi anziché un singolo passo per gli aggiornamenti dei valori Q.
- Utilizza una finestra temporale di lunghezza n per valutare le azioni e le ricompense.
Funzionamento di n-step SARSA:
1. Sequenza di n Passi:
- L’agente osserva una sequenza consecutiva di n passi durante l’esecuzione.
2. Aggiornamento dei Valori Q:
- Dopo la sequenza di n passi, vengono aggiornati i valori Q considerando le ricompense cumulative e le azioni eseguite durante l’intera sequenza.
3. Formula di Aggiornamento:
- L’aggiornamento dei valori Q in n-step SARSA tiene conto delle ricompense cumulative e delle azioni selezionate in n passi temporali:
formulasulq.
Dove G_{t:t+n} è il ritorno cumulativo ottenuto dai passi t a t+n (sequenza n-step) e α è il tasso di apprendimento.
Vantaggi di n-step SARSA:
- Prospettiva Temporale più Ampia: Considerando una sequenza di n passi, l’agente può valutare le azioni in un contesto temporale più ampio, migliorando la stabilità dell’apprendimento.
Considerazioni:
- Selezione di n: La scelta del parametro n influenza la dimensione della finestra temporale considerata e può influenzare l’efficacia dell’apprendimento.
- Complessità: Un valore maggiore di n aumenta la complessità computazionale e il tempo richiesto per gli aggiornamenti dei valori Q.
Cos’è l’importance sampling?
L’importance sampling è una tecnica utilizzata per stimare o correggere le distribuzioni di probabilità quando si dispone di dati provenienti da una distribuzione di campionamento diversa da quella che si desidera valutare o stimare.
Concetto di Base:
L’importance sampling è ampiamente utilizzato in vari campi, tra cui l’apprendimento automatico, le simulazioni e l’analisi dei dati. In contesti di apprendimento per rinforzo, è particolarmente rilevante quando si lavora con politiche di comportamento diverse dalla politica target.
Funzionamento dell’Importance Sampling:
- Scenari di Utilizzo: L’importance sampling è impiegato quando si desidera valutare una distribuzione di probabilità (o una stima) relativa a un determinato evento o condizione, ma si dispone di dati provenienti da una distribuzione di probabilità diversa.
- Correzione delle Stime: La tecnica consiste nell’aspettarsi che l’evento desiderato sia raro secondo la distribuzione di campionamento, quindi si correggono le stime o le valutazioni moltiplicando i valori ottenuti per il rapporto tra le probabilità di campionamento delle due distribuzioni.
Formula dell’Importance Sampling:
Considerando due distribuzioni di probabilità P (la distribuzione target) e Q (la distribuzione di campionamento), l’importance sampling corregge le stime di una certa quantità f(x) come segue:
E[f(x)]_P = ∑_x P(x) * f(x)^E_Q[f(x)] = 1/N ∑_i^N f(x_i)
Dove:
- E[f(x)]_P rappresenta l’aspettativa di f(x) rispetto alla distribuzione P.
- ^E_Q[f(x)] è una stima dell’aspettativa di f(x) rispetto alla distribuzione Q ottenuta dai dati campionati.
- N è il numero di campioni x_i ottenuti da Q.
L’importance sampling corregge l’aspettativa ^E_Q[f(x)] moltiplicandola per il rapporto tra le probabilità di campionamento delle distribuzioni P e Q:
E[f(x)]_P = 1/N ∑_i^N P(x_i)/Q(x_i) * f(x_i)
Applicazioni:
Nell’apprendimento per rinforzo, l’importance sampling è spesso utilizzato per correggere stime di valori d’azione o valutazioni di politiche quando i dati vengono raccolti da politiche di comportamento diverse dalla politica target. Questo è particolarmente utile nell’off-policy learning, dove si desidera valutare una politica target utilizzando dati provenienti da una politica di comportamento diversa.
Come funziona l’importance sampling per off-policy monte carlo?
Nell’off-policy Monte Carlo, l’importance sampling, confronto tra le 2 policy, nella sua interezza
Come funziona l’importance sampling per off-policy TD?
Nell’off-policy TD learning, l’importance sampling aiuta a valutare o aggiornare una politica target usando dati raccolti da un’altra politica di comportamento. È come confrontare due modi diversi di fare le cose.
Si fa soltanto per la singola correzione e poi utilizzi la tua policy
Cos’è il Q-Learning?
Il Q-learning è un algoritmo di apprendimento per l’apprendimento automatico rinforzato (RL) che mira a imparare una funzione Q ottimale, che valuta la bontà di una data azione in uno stato specifico. Formalmente, il Q-learning utilizza la programmazione dinamica e l’approccio basato sul valore per stimare il valore ottimale di una coppia stato-azione.
La funzione Q(s, a) rappresenta il valore atteso cumulativo di eseguire un’azione “a” in uno stato “s” e quindi seguire una politica ottimale da quel punto in poi. L’algoritmo Q-learning aggiorna iterativamente i valori di Q(s, a) in base alle ricompense ottenute esplorando l’ambiente, utilizzando l’equazione di aggiornamento della Q-funzione:
Q(s, a) <- Q(s, a) + α * [R + γ * max_a’ Q(s’, a’) - Q(s, a)]
Dove:
- Q(s, a) è il valore della funzione Q per lo stato “s” e l’azione “a”.
- α è il tasso di apprendimento che regola l’importanza dell’aggiornamento della Q-funzione.
- R è la ricompensa ottenuta eseguendo l’azione “a” nello stato “s”.
- γ è il fattore di sconto che indica l’importanza delle future ricompense rispetto a quelle immediate.
- s’ è lo stato successivo dopo aver eseguito l’azione “a”.
- max_a’ Q(s’, a’) è il valore massimo della funzione Q per lo stato successivo s’ e tutte le possibili azioni a’.
L’obiettivo del Q-learning è di apprendere la migliore politica decisionale senza conoscere il modello dell’ambiente, tramite esplorazione e sfruttamento iterativo. Alla fine del processo di apprendimento, la funzione Q approssima il valore ottimale di ogni azione in ciascun stato, consentendo di selezionare le azioni migliori per massimizzare le ricompense nel lungo periodo.
Policy iteration generalizzata
L’approccio per ottenere una policy ottimale è un approccio iterativo in cui andiamo in maniera alternata a fare prediction e control, quindi partiamo da una value function e andiamo ad ottimizzarla mediante un processo greedy, dopo ripetiamo la valutazione della policy e così via con un’altra ottimizzazione, dopo una serie di iterazioni la policy non dovrebbe più cambiare in quel caso vuol dire che siamo arrivati alla policy ottimata
