Equazione di Bellman

L'equazione di Bellman è una formula fondamentale nell'ambito della **teoria del controllo ottimo** e della **programmazione dinamica**. È utilizzata per risolvere problemi di decisione sequenziale, dove un agente deve prendere una serie di decisioni ottimali per massimizzare una ricompensa cumulativa o minimizzare un costo nel tempo.

Cos'è l'equazione di Bellman

L'equazione di Bellman esprime il principio di ottimalità: una strategia ottimale può essere definita come tale che, indipendentemente dallo stato iniziale e dalla decisione iniziale, le decisioni successive devono costituire una strategia ottimale rispetto al nuovo stato risultante.
La forma generale è: \[ V(s) = \max_{a} \left[ R(s, a) + \gamma \sum_{s'} P(s' | s, a) V(s') \right] \] Dove: - (V(s)): Valore dello stato (s) (valore atteso a partire da (s)).
- (R(s, a)): Ricompensa immediata scegliendo l'azione (a) nello stato (s).
- (gamma in [0, 1]): Fattore di sconto che pondera il valore delle ricompense future.
- (P(s' | s, a)): Probabilità di transizione dallo stato (s) al nuovo stato (s') eseguendo l'azione (a).

Cosa serve

L'equazione di Bellman è fondamentale per:
1. Controllo ottimo: Determinare il comportamento ottimale in sistemi dinamici, ad esempio nei robot o nei sistemi di gestione di risorse.
2. Apprendimento per rinforzo: Usata per calcolare la politica ottimale in algoritmi come Q-Learning e Deep Q-Networks (DQN).
3. Pianificazione: Valutare percorsi ottimali in problemi come la navigazione o il problem solving.

Come si risolve

La risoluzione dell'equazione di Bellman dipende dal problema:
1. Iterazione sul valore (Value Iteration):
- Si parte da una stima iniziale (V_0(s)).
- Si aggiorna iterativamente con:
\[ V_{k+1}(s) = \max_{a} \left[ R(s, a) + \gamma \sum_{s'} P(s' | s, a) V_k(s') \right] \] - Si itera fino a convergenza, ossia quando i valori non cambiano significativamente.

2. Iterazione sulla politica (Policy Iteration):
- Si inizia con una politica iniziale (pi(s)).
- Si alternano due passaggi:
- Valutazione della politica: Calcolare (V(s)) per la politica corrente.
- Miglioramento della politica: Aggiornare (pi(s)) scegliendo l'azione (a) che massimizza \(R(s, a) + \gamma \sum_{s'} P(s' | s, a) V(s')\).
3. Approcci approssimati:
- Quando lo spazio degli stati è troppo grande, si usano metodi come apprendimento per rinforzo o funzioni di approssimazione.

Significato intuitivo

L'equazione di Bellman bilancia:
- Il valore immediato di un'azione (la ricompensa (R(s, a))).
- Il valore futuro atteso a partire dal nuovo stato ((gamma V(s'))).

In pratica, calcola quanto vale ogni stato (s) assumendo che le decisioni successive siano ottimali.
È una guida per scegliere l'azione migliore in ogni stato.