Equazione di Bellman

L’equazione di Bellman è la ricorrenza fondamentale della programmazione dinamica. Esprime il valore ottimo di uno stato come combinazione tra costo immediato e valore ottimo del problema residuo.

Nel caso deterministico a orizzonte finito:

V_t(s)= \min_{a\in A(s)} \left\{ c_t(s,a)+V_{t+1}(T(s,a)) \right\}.

$s$ è lo stato, $a$ l’azione, $c_t(s,a)$ il costo immediato, $T(s,a)$ la transizione e $V_t(s)$ la funzione valore.

La formula va letta così: per ogni azione possibile si somma il costo immediato al valore ottimo dello stato successivo; poi si sceglie l’azione che rende minima questa somma. Il valore non è quindi una proprietà statica dello stato, ma il risultato di una scelta ottima.

Forma con massimizzazione

Se il problema è formulato come massimizzazione di un ricavo o di un’utilità:

V_t(s)= \max_{a\in A(s)} \left\{ r_t(s,a)+V_{t+1}(T(s,a)) \right\}.

La struttura è la stessa: una scelta locale viene valutata insieme alle sue conseguenze future.

In alcuni testi si passa da minimizzazione a massimizzazione cambiando segno al costo:

r_t(s,a)=-c_t(s,a).

Il contenuto matematico non cambia, ma cambia il linguaggio: costi e penalità diventano ricompense negative, mentre ricavi e utilità diventano quantità da massimizzare.

Caso stocastico

Quando lo stato successivo è aleatorio, l’equazione contiene un valore atteso:

V_t(s)= \min_{a\in A(s)} \left\{ c_t(s,a)+ \sum_{s'}p(s'\mid s,a)V_{t+1}(s') \right\}.

Questa è la forma tipica dei processi decisionali di Markov. La probabilità $p(s'\mid s,a)$ descrive la transizione dallo stato corrente allo stato successivo.

Se si usa un fattore di sconto $\gamma$ , la forma diventa:

V(s)= \min_{a\in A(s)} \left\{ c(s,a)+ \gamma\sum_{s'}p(s'\mid s,a)V(s') \right\}.

Il parametro $\gamma$ riduce il peso dei costi futuri. Nei modelli economici e decisionali rappresenta preferenza temporale, rischio di interruzione o semplice esigenza matematica di convergenza.

Condizione terminale

Per calcolare la ricorrenza serve una condizione finale:

V_T(s)=g(s),

dove $g(s)$ è costo terminale, valore residuo o penalità finale. Da lì si procede all’indietro fino a $V_0$ .

Senza condizione terminale, la ricorrenza resta sospesa: ogni valore dipende da un valore futuro non ancora definito. Nei problemi a orizzonte finito, il terminale chiude il sistema; negli orizzonti infiniti, la chiusura avviene tramite stazionarietà, sconto o condizioni di stabilità.

Politica ottima

Oltre al valore, interessa l’azione che realizza il minimo:

\pi_t^\ast(s)= \arg\min_{a\in A(s)} \left\{ c_t(s,a)+V_{t+1}(T(s,a)) \right\}.

$\pi_t^\ast$ è la politica ottima. La funzione valore dice quanto costa partire da uno stato; la politica dice che cosa fare in quello stato.

Questa distinzione è importante nei software: prima si calcolano o approssimano i valori, poi si ricostruiscono le decisioni ottime.

Iterazione sui valori

Negli MDP stazionari si può approssimare la soluzione tramite iterazione sui valori:

V_{k+1}(s)= \min_{a\in A(s)} \left\{ c(s,a)+ \gamma\sum_{s'}p(s'\mid s,a)V_k(s') \right\}.

Si parte da una stima iniziale $V_0$ e si aggiorna fino alla convergenza. Il metodo è concettualmente semplice, ma può essere costoso se lo spazio degli stati è grande.

Interpretazione ingegneristica

L’equazione di Bellman non è solo una formula: è un modo per separare decisione immediata e conseguenza futura. In gestione può descrivere scorte, manutenzione o investimenti; in automatica descrive costi di controllo; in informatica descrive cammini minimi, parsing e problemi combinatori.

Nel controllo ottimo lineare quadratico, versioni specializzate dell’equazione di Bellman portano a ricorrenze matriciali come la ricorsione di Riccati discreta e, al limite stazionario, all’equazione algebrica di Riccati.

Nei problemi su reti, la stessa idea appare nella ricorrenza dei cammini minimi:

d_j= \min_{(i,j)\in A} \left\{ d_i+c_{ij} \right\}.

Il valore di arrivare a $j$ dipende dal miglior predecessore $i$ e dal costo dell’ultimo arco.

Equazione di Bellman e ottimalità

L’equazione di Bellman è la forma algebrica del principio di ottimalità. Se una politica ottima parte da $s$ , dopo la prima azione deve restare ottima nello stato successivo. Per questo il valore futuro può essere scritto come $V_{t+1}$ o $V$ .

Se questa proprietà non vale, la ricorrenza può produrre una soluzione coerente con il modello, ma il modello non rappresenta correttamente il problema reale. La verifica dello stato è quindi parte della formulazione, non un dettaglio successivo.

Valore, costo e vincoli

Molte versioni pratiche includono vincoli sulle azioni:

a\in A(s).

Questo insieme può dipendere dallo stato: una macchina già guasta non ha le stesse azioni di una macchina funzionante; un veicolo vicino a un vincolo termico non può seguire qualunque profilo di controllo. La qualità della formulazione dipende anche dalla correttezza di questi insiemi ammissibili.

Errori comuni

Un errore frequente è scrivere una ricorrenza senza verificare il principio di ottimalità. Se lo stato non è sufficiente, il valore futuro non dipende solo da $s$ e l’equazione è incompleta.

Un secondo errore è ignorare il costo computazionale: l’equazione può essere corretta ma impossibile da valutare se il numero di stati è troppo grande.