Pianificazione mediante Programmazione dinamica Flashcards
Cos’è la programmazione dinamica?
La programmazione dinamica è una tecnica di progettazione degli algoritmi utilizzata in informatica per risolvere problemi di ottimizzazione. Questa tecnica prevede la suddivisione di un problema complesso in sottoproblemi più piccoli, la risoluzione dei sottoproblemi e la memorizzazione dei risultati in modo da evitarne il calcolo ripetuto.
Iterative Policy Evaluation
L’idea è andare ad applicare la funzione di Bellman in maniera iterativa in modo da ottenere le varie value function finché non ci sono aggiornamenti dunque finché non si raggiunge la convergenza.
Policy Iteration
Durante la fase di policy iteration, l’obiettivo è migliorare la policy, individuando le azioni ottimali per ciascuno stato. Questo viene fatto utilizzando la value function, che valuta la bontà delle azioni in uno stato. La strategia greedy consiste nel selezionare le azioni che massimizzano la value function per ogni stato, il che può portare a miglioramenti incrementali della politica. Tuttavia, in alcuni casi, potrebbe essere necessario riapplicare l’algoritmo di valutazione della politica e successivamente migliorare la politica stessa, in un processo noto come “danza della policy e della value function”. L’obiettivo principale è ottenere una politica sempre migliore rispetto alla precedente, fino a raggiungere la politica ottimale. Questo approccio evita il rischio di cadere in minimi locali, garantendo progressivamente un miglioramento della politica decisionale del sistema.
Value Iteration
Prima azione ottimale e poi successivamente la value function ottimale dello stato successivo
Algoritmi di programmazione dinamica sincrona
tabellasulq
Fase di prediction: In questa fase, si cerca di valutare una data policy, cioè di stimare i valori di ogni stato sotto la policy data. Questo viene spesso fatto utilizzando l’equazione di Bellman in modo iterativo finché la stima dei valori converge. In sostanza, si cerca di capire “quanto è buona” la policy attuale senza ancora modificarla.
Fase di control: Dopo aver valutato la policy, si passa alla fase di controllo, che consiste nel migliorare effettivamente la policy stessa. Questo può essere fatto in diverse modalità, ma una delle tecniche più comuni è la cosiddetta “policy iteration”. In questo approccio, si utilizza l’equazione di Bellman per migliorare iterativamente la policy, selezionando le azioni migliori per ciascuno stato fino a raggiungere una policy ottimale.
Value iteration: È un altro algoritmo utilizzato per trovare la policy ottimale. Si basa sull’equazione di ottimalità di Bellman e viene applicato in modo iterativo per stimare i valori ottimi per ogni stato. A differenza della policy iteration, non si mantiene esplicitamente una policy durante il processo, ma piuttosto si aggiorna direttamente i valori degli stati fino a raggiungere la convergenza
Programmazione dinamica asincrona
Gli aggiornamenti asincroni si riferiscono alla pratica di aggiornare solo alcuni stati durante l’iterazione, basandosi sui valori già calcolati.
Programmazione dinamica in place: invece di due value function ne abbiamo solo una per risparmiare memoria
Prioritised sweeping: È una tecnica che assegna priorità agli stati più importanti o influenti durante la risoluzione di problemi di programmazione dinamica.
Ad ogni stato calcoli la Bellman error e poi quella con l’errore maggiore è quella che dai priorità per l’aggiornamento
