Il principio di ottimalità è l’idea centrale della programmazione dinamica. Afferma che una politica ottima possiede questa proprietà: qualunque sia la prima decisione, la sequenza residua di decisioni deve essere ottima per lo stato raggiunto.
In forma intuitiva: se una soluzione è davvero ottima, anche la parte che resta dopo una scelta deve essere ottima rispetto al problema residuo.
Significato operativo
Supponiamo di dover minimizzare un costo lungo più stadi. Se al tempo t ci troviamo nello stato s e scegliamo l’azione a, il problema futuro dipende dallo stato successivo. La scelta ottima non può essere valutata guardando solo il costo immediato: deve includere anche il valore del problema residuo.
Per questo si introduce una funzione valore:
Questa è una forma deterministica dell’equazione di Bellman.
Il principio trasforma un problema globale in una famiglia di problemi locali collegati. Non dice che la scelta localmente più economica sia sempre giusta; dice che ogni scelta va giudicata sommando effetto immediato e conseguenze future.
Decisione miope e decisione ottima
Una decisione miope minimizza soltanto c_t(s,a). Una decisione dinamicamente ottima minimizza:
La differenza è cruciale. Una scelta economica oggi può portare a uno stato futuro costoso; una scelta più cara oggi può lasciare maggiore flessibilità e ridurre il costo totale.
In gestione delle scorte, per esempio, ordinare poco può sembrare conveniente nel periodo corrente, ma può generare stockout e costi futuri. In controllo, un’azione aggressiva può ridurre subito l’errore ma consumare troppa energia o portare il sistema vicino a vincoli.
Stato sufficiente
Il principio funziona solo se lo stato contiene tutte le informazioni necessarie per descrivere il futuro. Se due storie diverse portano allo stesso stato, allora da quel punto in poi devono generare lo stesso problema residuo.
Questa proprietà è decisiva. Uno stato incompleto rompe la ricorrenza: la formula può sembrare corretta, ma nasconde informazioni passate ancora rilevanti.
Uno stato sufficiente non deve contenere tutto il passato, ma solo ciò che serve per predire costi, vincoli e transizioni future. Questa compressione è il vantaggio della formulazione dinamica.
Se però si aggiungono troppe variabili allo stato, il modello diventa più fedele ma anche più costoso. La progettazione dello stato è quindi un compromesso tra informazione e calcolabilità.
Esempio
Nel problema dello zaino zero-uno, dopo aver considerato i primi i oggetti e una capacità residua c, non importa quale sequenza di scelte abbia prodotto quella capacità. Il valore ottimo residuo può essere descritto da:
Questo rende possibile costruire la soluzione tramite sottoproblemi.
Nel cammino minimo, se il percorso ottimo da una sorgente a un nodo j passa per un nodo i, allora il tratto dalla sorgente a i deve essere a sua volta ottimo. Altrimenti si potrebbe sostituire quel tratto con uno migliore e ottenere un percorso totale più corto.
Questa argomentazione è la forma più semplice del principio di ottimalità: un segmento non ottimo dentro una soluzione ottima genera una contraddizione.
Orizzonte finito e infinito
Nei problemi a orizzonte finito il principio si applica procedendo all’indietro da una condizione terminale:
Negli orizzonti infiniti, invece, si cerca spesso una funzione valore stazionaria:
Il fattore \gamma pesa il futuro. Se \gamma è vicino a zero, conta quasi solo il costo immediato; se è vicino a uno, il futuro pesa molto.
Incertezza
Quando le transizioni sono aleatorie, il principio resta valido se lo stato è markoviano. La ricorrenza usa un valore atteso:
Questa forma è alla base dei processi decisionali di Markov. Il principio di ottimalità non scompare con l’incertezza: cambia il modo in cui si valuta il futuro.
Limiti
Non tutti i problemi soddisfano il principio di ottimalità. Se una decisione crea vincoli futuri non riassumibili nello stato, oppure se il valore di una scelta dipende dall’intera storia, una ricorrenza semplice può non essere valida.
Nei problemi stocastici serve anche una struttura markoviana: dato lo stato corrente e l’azione, la distribuzione dello stato successivo non deve dipendere dalla storia precedente. Questo porta ai processi decisionali di Markov.
Un altro limite è computazionale. Anche quando il principio è valido, il numero di stati può essere enorme. In quel caso la soluzione esatta tramite tabella dei valori diventa impraticabile e servono approssimazioni.
Relazione con decomposizione del problema
Il principio di ottimalità funziona perché spezza il problema lungo una frontiera informativa: lo stato. Tutto ciò che è avvenuto prima dello stato può essere sostituito dal valore già accumulato; tutto ciò che avviene dopo viene trattato come problema residuo.
Questa separazione è diversa da dividere il problema in parti indipendenti. I sottoproblemi non sono necessariamente indipendenti: sono collegati dalla funzione valore. La programmazione dinamica è efficace proprio quando questo collegamento può essere riassunto con poche variabili di stato.
Errori comuni
Un errore frequente è applicare la programmazione dinamica appena si vede una sequenza temporale. La sequenzialità da sola non basta: serve una sottostruttura ottima e uno stato sufficiente.
Un altro errore è scegliere uno stato troppo dettagliato. In questo caso il principio resta valido, ma il numero di stati può esplodere e portare alla maledizione della dimensionalità.