È particolarmente utile nell'apprendimento per rinforzo (RL) per risolvere in modo efficiente i processi decisionali di Markov (MDP) quando è disponibile un modello completo dell'ambiente.

Condizioni per l'applicazione della DP

Non tutti i problemi possono essere risolti con la DP. Esistono due attributi chiave che un problema deve possedere affinché la DP sia applicabile:

• Struttura ottimale dei sottoproblemi: la soluzione ottimale di un problema deriva dalle soluzioni ottimali dei suoi sottoproblemi. Negli MDP, ciò significa che la politica ottimale in uno stato dipende dalle politiche ottimali degli stati successivi. Poiché le decisioni in un MDP sono sequenziali, risolvere sottoproblemi più piccoli (trovare la migliore azione per stati futuri) porta a risolvere il problema complessivo (trovare la migliore azione per lo stato attuale);
• Sovrapposizione dei sottoproblemi: le soluzioni ai sottoproblemi vengono riutilizzate per risolvere problemi più grandi. Negli MDP, questo è evidente perché il valore di uno stato viene calcolato ripetutamente in diverse sequenze decisionali. Poiché gli stati vengono spesso rivisitati, i valori calcolati in precedenza possono essere memorizzati e riutilizzati, riducendo i calcoli ridondanti e migliorando l'efficienza.

Ogni nodo nell'immagine rappresenta una chiamata ricorsiva per calcolare Fib(n), e la struttura ad albero mostra come queste chiamate vengano suddivise in sottoproblemi più piccoli. Si noti che sottoproblemi come Fib(2) e Fib(1) compaiono più volte, dimostrando la sovrapposizione dei sottoproblemi, mentre la soluzione di Fib(5) è costruita a partire dalle soluzioni ottimali dei suoi sottoproblemi, dimostrando la struttura ottimale dei sottoproblemi. Questa ridondanza è ciò che la programmazione dinamica mira a eliminare memorizzando e riutilizzando i risultati.

Poiché gli MDP presentano sia struttura ottimale dei sottoproblemi sia sovrapposizione dei sottoproblemi, sono particolarmente adatti a soluzioni basate sulla DP.

Perché utilizzare la DP nell'RL?

• Garanzie di optimalità: i metodi di DP garantiscono la convergenza verso la politica ottimale quando il modello completo è noto;
• Efficienza per soluzioni generali: con l'aiuto della DP, è possibile ottenere soluzioni generali in modo efficiente, il che significa che la politica risultante sarà ottimale per ogni singolo stato;
• Fondamentale per altri metodi: i concetti della DP costituiscono la base per altri metodi di RL, come Monte Carlo e temporal difference learning.

Tuttavia, la DP non è praticabile per problemi su larga scala a causa della sua dipendenza da un modello completo e delle richieste computazionali, il che porta alle sfide discusse di seguito.

Sfide e limitazioni della Dynamic Programming

Sebbene la Programmazione Dinamica (DP) offra un quadro elegante per la risoluzione dei problemi di RL, presenta sfide significative che ne limitano l'applicabilità in scenari reali:

• Complessità computazionale: i metodi DP richiedono calcoli per ogni singolo stato in un ambiente. All'aumentare dello spazio degli stati, il numero di calcoli necessari cresce in modo significativo, rendendo la DP impraticabile per problemi complessi;
• Necessità di un modello noto: la DP presuppone che le probabilità di transizione e le ricompense dell'ambiente siano note in anticipo. Tuttavia, in molte applicazioni RL reali, queste informazioni non sono disponibili, rendendo più pratici gli approcci senza modello.