Apprendimento per rinforzo Programmazione dinamica e Monte Carlo – Parte 2

Apprendimento per rinforzo - Parte 2

Introduzione a due semplici tecniche iterative per risolvere il Processo Decisionale Markoviano

Immagine di Wil Stewart su Unsplash

Nell’articolo precedente – Parte 1 – abbiamo formulato il Processo Decisionale Markoviano (MDP) come paradigma per risolvere qualsiasi problema di Apprendimento per Rinforzo (RL). Tuttavia, il framework generale discusso non ha menzionato una soluzione sistematica per l’MDP. Abbiamo escluso l’uso di tecniche lineari – come l’inversione di matrici – e abbiamo brevemente sollevato la possibilità di utilizzare tecniche iterative per risolvere l’MDP. Per rivedere l’idea di MDP, consulta la Parte I di seguito:

Apprendimento per Rinforzo: Processo Decisionale Markoviano – Parte 1

Introduzione alla base dell’Apprendimento per Rinforzo – Il Processo Decisionale Markoviano

pub.towardsai.net

A partire da questo articolo, in relazione all’RL, discuteremo tecniche iterative e soluzioni per l’MDP. In particolare, in questo articolo, presenteremo 2 metodi iterativi per risolvere l’MDP: la Programmazione Dinamica e i Metodi Monte Carlo.

1. Programmazione Dinamica

Parleremo prima della Programmazione Dinamica. La Programmazione Dinamica è una tecnica di soluzione iterativa che fa uso di 2 proprietà della struttura del problema:

  • Il sottoproblema può ripetersi molte volte
  • Le soluzioni ad ogni ripetizione possono essere memorizzate nella cache e riutilizzate

Di conseguenza, questa tecnica è particolarmente applicabile ai problemi di MDP, poiché l’equazione di Bellman può fornire una decomposizione ricorsiva della Funzione di Valore dello Stato V(s). Rivediamo l’Equazione di Bellman per V(s):

Tuttavia, la differenza nella Programmazione Dinamica è che per una particolare policy π, stiamo utilizzando l’Equazione di Bellman per mappare il vicino V(s') dal passaggio temporale t allo stato corrente V(s) al passaggio temporale t+1. Il diagramma sottostante fornisce una intuizione simile (la variabile k sottostante rappresenta il passaggio di iterazione). Inoltre, nota che la seguente iterazione viene applicata ad ogni stato nell’algoritmo di Programmazione Dinamica.