Dynamic Programming

Il Dynamic Programming è una metodologia per risolvere problemi complessi scomponendoli in sottoproblemi più semplici.
L'idea di base è di risolvere ogni sottoproblema una sola volta, memorizzando i risultati per evitare calcoli ripetuti.
DP è particolarmente utile quando il problema presenta sovrapposizione di sottoproblemi e una struttura di sottostruttura ottimale, come nel caso di processi decisionali sequenziali che caratterizzano il Reinforcement Learning.
Nel contesto del Reinforcement Learning, il dynamic programming si applica principalmente alla soluzione dei problemi di decisione sequenziale, in cui un agente deve imparare a prendere decisioni ottimali nel tempo, dato un ambiente dinamico e incerto. Dynamic Programming è un metodo

Model Based

Quando Si Usa il Dynamic Programming

Il Dynamic Programming è generalmente utilizzato quando il modello dell'ambiente è completamente conosciuto.
In altre parole, si ha accesso alla transizione di stato e alle ricompense che l'agente può ottenere per ogni azione in ogni stato.
Questo scenario è tipico in situazioni in cui:
- Il modello dell'ambiente è noto, cioè conosciamo le probabilità di transizione e le funzioni di ricompensa.
- Siamo in grado di calcolare in modo efficiente i valori delle azioni in base agli stati futuri, grazie alla struttura deterministica del modello.
Nel contesto del Reinforcement Learning, quindi, il Dynamic Programming è utile per risolvere i problemi di planning dove non c'è bisogno di apprendere tramite l'esplorazione empirica, ma possiamo sfruttare la conoscenza completa dell'ambiente.

Come si Usa il Dynamic Programming

In Reinforcement Learning, il Dynamic Programming viene principalmente utilizzato per calcolare e ottimizzare le policy e le value functions.
Le due principali tecniche di DP utilizzate sono:
1. Value Iteration (Iterazione del Valore)
2. Policy Iteration (Iterazione della Policy)

Value Iteration

La Value Iteration è un algoritmo iterativo che cerca di determinare la value function ottimale, ovvero il valore associato a ciascuno stato, dove il valore rappresenta la ricompensa attesa a partire da quello stato seguendo la politica ottimale.
L'algoritmo si basa sulla relazione di Bellman, che esprime il valore di uno stato come la somma della ricompensa immediata e dei valori futuri, pesati dalla probabilità di transizione.
L'algoritmo di Value Iteration funziona nel seguente modo:
1. Inizializzare la value function arbitrariamente per tutti gli stati.
2. Iterare fino a convergenza, aggiornando la value function secondo la formula di Bellman:
\[ V(s) = \max_a \left( R(s, a) + \gamma \sum_{s'} P(s' | s, a) V(s') \right) \]
Dove:
- ( V(s) ) è il valore dello stato \( s \),
- ( R(s, a) ) è la ricompensa immediata per aver preso l'azione \( a \) nello stato \( s \),
- ( gamma ) è il fattore di sconto,
- ( P(s' | s, a) ) è la probabilità di transizione dallo stato \( s \) allo stato \( s' \) a seguito dell'azione \( a \).
3. Una volta che la value function converge, si può derivare la policy ottimale, scegliendo per ogni stato l'azione che massimizza il valore atteso.

Policy Iteration

La Policy Iteration è un altro approccio per risolvere i problemi di decisione sequenziale.
A differenza della Value Iteration, la Policy Iteration ottimizza direttamente la **policy** in modo iterativo.
L'algoritmo alterna due fasi:
1. Evaluation della Policy: Dato un insieme di politiche, calcolare la value function associata a quella policy. In questa fase, si risolve il sistema di equazioni di Bellman per la policy corrente.
\[ V^\pi(s) = R(s, \pi(s)) + \gamma \sum_{s'} P(s' | s, \pi(s)) V^\pi(s') \]
Dove ( pi(s) ) è l'azione scelta dalla policy nel stato ( s ).

2. Improvement della Policy: Aggiornare la policy, scegliendo per ogni stato l'azione che massimizza la ricompensa attesa, dato il valore calcolato per ogni stato.
\[ \pi'(s) = \arg\max_a \left( R(s, a) + \gamma \sum_{s'} P(s' | s, a) V^\pi(s') \right) \]

3. Ripetere queste due fasi (Evaluation e Improvement) fino a quando la policy non cambia più, indicando che è stata trovata la politica ottimale.

Ottimizzazione delle Policy e delle Value Functions

Il principale obiettivo del Reinforcement Learning è determinare la politica ottimale che massimizza la ricompensa complessiva nel tempo.
Il Dynamic Programming offre due approcci principali per ottimizzare le **policy** e le **value functions**:
- Ottimizzazione della Value Function: Con la Value Iteration, l'algoritmo cerca la value function che meglio rappresenta il valore di ogni stato.
Una volta trovata la value function ottimale, è possibile derivare la politica ottimale associata, cioè quella che massimizza il valore in ogni stato.

- Ottimizzazione della Policy: Con la Policy Iteration, invece, si cerca direttamente di migliorare la politica.
L'algoritmo alterna tra calcolare la value function per una policy e migliorare la policy stessa. Alla fine del processo, si ottiene una politica ottimale.

Vantaggi e Limitazioni

Vantaggi

- È una tecnica molto potente quando si ha un modello completo dell'ambiente.
- Può fornire soluzioni esatte, se il problema è ben definito.

Limitazioni

- Richiede una conoscenza completa del modello, cosa che non è sempre possibile nel mondo reale (ad esempio, quando l'agente non ha accesso alle probabilità di transizione o alle ricompense).
- È computazionalmente costoso, specialmente per ambienti con uno spazio di stati e azioni molto ampio.
- Non è adatto a problemi di **apprendimento online**, dove l'agente non ha accesso al modello completo e deve esplorare l'ambiente.

Conclusioni

Il Dynamic Programming fornisce una solida base teorica per la risoluzione dei problemi di ottimizzazione in Reinforcement Learning.
Sebbene sia molto efficace in ambienti con modelli noti e ben definiti, la sua applicabilità è limitata nei casi in cui l'ambiente è sconosciuto o altamente dinamico.
Tuttavia, le tecniche di Value Iteration e Policy Iteration rimangono strumenti fondamentali per gli sviluppatori di sistemi RL che hanno accesso completo ai modelli, aiutando a ottimizzare le policy e le value functions in modo efficiente.