Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Impara Condizioni di Ottimalità | Programmazione Dinamica
Introduzione al Reinforcement Learning
course content

Contenuti del Corso

Introduzione al Reinforcement Learning

Introduzione al Reinforcement Learning

1. Teoria Fondamentale dell'RL
Che cos'è l'RL?RL Rispetto ad Altri Paradigmi di ApprendimentoProcesso Decisionale di MarkovEpisodi e RitorniModello, Politica e ValoriEsplorazione vs SfruttamentoBasi di GymnasiumSfida: Configurazione di un Ambiente
2. Problema del Multi-Armed Bandit
Introduzione al ProblemaValori d'AzioneAlgoritmo Epsilon-GreedyAlgoritmo del Limite Superiore di ConfidenzaAlgoritmo dei Banditi a GradienteSfida: Multi-Armed Banditi
3. Programmazione Dinamica
Che cos'è la programmazione dinamica?Equazioni di BellmanCondizioni di OttimalitàValutazione della PolicyMiglioramento della PolicyIterazione Generalizzata delle PoliticheIterazione delle PoliticheIterazione del ValoreSfida: Programmazione Dinamica
4. Metodi Monte Carlo
Cosa Sono i Metodi Monte Carlo?Stima della Funzione di ValoreControllo Monte CarloApprocci di EsplorazioneControllo Monte Carlo On-PolicyControllo Monte Carlo Off-PolicyImplementazioni IncrementaliSfida: Metodi Monte Carlo
5. Apprendimento a Differenza Temporale
Che cos'è l'Apprendimento a Differenza Temporale?TD(0): Stima della Funzione di ValoreSARSA: Apprendimento TD On-PolicyQ-Learning: Apprendimento TD Off-PolicyGeneralizzazione dell'Apprendimento TDSfida: Apprendimento a Differenza Temporale

book
Condizioni di Ottimalità

Nel capitolo precedente, hai appreso le equazioni di Bellman per le funzioni di valore di stato e di valore stato-azione. Queste equazioni descrivono come i valori degli stati possano essere definiti ricorsivamente attraverso i valori di altri stati, con i valori che dipendono da una determinata politica. Tuttavia, non tutte le politiche sono ugualmente efficaci. Infatti, le funzioni di valore forniscono un ordinamento parziale per le politiche, che può essere descritto come segue:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Quindi la politica π\pi è migliore o uguale alla politica π′\pi' se, per tutti gli stati possibili, il rendimento atteso della politica π\pi non è inferiore al rendimento atteso della politica π′\pi'.

Note
Approfondimento

Un ordinamento parziale segue le regole usuali dell'ordinamento ma non obbliga a confrontare ogni coppia. Nel nostro caso, possiamo classificare due politiche solo se producono gli stessi risultati, oppure se una supera chiaramente l'altra. In tutti gli altri casi, le politiche rimangono incomparabili.

Politica Ottimale

Note
Definizione

Per qualsiasi MDP, esiste almeno una politica che è buona quanto o migliore di tutte le altre politiche. Questa politica è chiamata politica ottimale π∗\pi_*. Sebbene possano esistere molte politiche ottimali, tutte sono indicate come π∗\pi_*.

Perché esiste sempre una politica ottimale?

Potresti chiederti perché una politica ottimale esiste sempre per qualsiasi MDP. È una domanda interessante, e l'intuizione alla base è sorprendentemente semplice. Ricorda che gli stati in un MDP catturano completamente la condizione dell'ambiente. Questo implica che ogni stato è indipendente dagli altri: l'azione scelta in uno stato non influisce sulle ricompense o sugli esiti ottenibili in un altro. Pertanto, selezionando l'azione ottimale in ciascuno stato separatamente, si ottiene naturalmente la migliore sequenza complessiva di azioni nell'intero processo. E questo insieme di azioni ottimali in ogni stato costituisce una politica ottimale.

Inoltre, esiste sempre almeno una politica che è sia ottimale sia deterministica. Infatti, se per uno stato ss, due azioni aa e a′a' producono lo stesso rendimento atteso, sceglierne solo una non influirà sull'ottimalità della politica. Applicando questo principio a ogni singolo stato, la politica diventerà deterministica pur mantenendo la sua ottimalità.

Funzioni di Valore Ottimali

Le politiche ottimali condividono le stesse funzioni di valore — un fatto che diventa evidente quando si considera come vengono confrontate le politiche. Questo significa che le politiche ottimali condividono sia la funzione di valore di stato sia la funzione di valore d'azione.

Inoltre, le funzioni di valore ottimali possiedono le proprie equazioni di Bellman che possono essere scritte senza fare riferimento a una politica specifica. Queste equazioni sono chiamate equazioni di ottimalità di Bellman.

Funzione di valore di stato ottimale

Note
Definizione

La funzione di valore di stato ottimale V∗V_* (o v∗v_*) rappresenta il rendimento atteso massimo ottenibile da uno stato specifico seguendo una politica ottimale.

Può essere definito matematicamente come segue:

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

L'equazione di ottimalità di Bellman per questa funzione di valore può essere derivata come segue:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuizione

Come già noto, esiste sempre almeno una politica che è sia ottimale sia deterministica. Una tale politica, per ogni stato, selezionerebbe costantemente una particolare azione che massimizza i ritorni attesi. Pertanto, la probabilità di scegliere questa azione ottimale sarebbe sempre 1, mentre la probabilità di scegliere qualsiasi altra azione sarebbe 0. Dato ciò, l'equazione di Bellman originale non necessita più dell'operatore di sommatoria. Invece, poiché sappiamo che selezioneremo sempre la migliore azione possibile, possiamo semplicemente sostituire la somma prendendo il massimo su tutte le azioni disponibili.

Funzione di valore d'azione ottimale

Note
Definizione

Funzione di valore d'azione ottimale Q∗Q_* (o q∗q_*) rappresenta il rendimento atteso massimo ottenibile eseguendo una determinata azione in uno stato specifico e seguendo successivamente la politica ottimale.

Può essere definita matematicamente come segue:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Equazione di ottimalità di Bellman per questa funzione di valore può essere derivata come segue:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuizione

Analogamente alla funzione di valore di stato, la somma può essere sostituita prendendo il massimo su tutte le azioni disponibili.

question mark

Perché esiste sempre una politica ottimale per qualsiasi processo decisionale di Markov?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 3. Capitolo 3

Chieda ad AI

expand

Chieda ad AI

ChatGPT

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

course content

Contenuti del Corso

Introduzione al Reinforcement Learning

Introduzione al Reinforcement Learning

1. Teoria Fondamentale dell'RL
Che cos'è l'RL?RL Rispetto ad Altri Paradigmi di ApprendimentoProcesso Decisionale di MarkovEpisodi e RitorniModello, Politica e ValoriEsplorazione vs SfruttamentoBasi di GymnasiumSfida: Configurazione di un Ambiente
2. Problema del Multi-Armed Bandit
Introduzione al ProblemaValori d'AzioneAlgoritmo Epsilon-GreedyAlgoritmo del Limite Superiore di ConfidenzaAlgoritmo dei Banditi a GradienteSfida: Multi-Armed Banditi
3. Programmazione Dinamica
Che cos'è la programmazione dinamica?Equazioni di BellmanCondizioni di OttimalitàValutazione della PolicyMiglioramento della PolicyIterazione Generalizzata delle PoliticheIterazione delle PoliticheIterazione del ValoreSfida: Programmazione Dinamica
4. Metodi Monte Carlo
Cosa Sono i Metodi Monte Carlo?Stima della Funzione di ValoreControllo Monte CarloApprocci di EsplorazioneControllo Monte Carlo On-PolicyControllo Monte Carlo Off-PolicyImplementazioni IncrementaliSfida: Metodi Monte Carlo
5. Apprendimento a Differenza Temporale
Che cos'è l'Apprendimento a Differenza Temporale?TD(0): Stima della Funzione di ValoreSARSA: Apprendimento TD On-PolicyQ-Learning: Apprendimento TD Off-PolicyGeneralizzazione dell'Apprendimento TDSfida: Apprendimento a Differenza Temporale

book
Condizioni di Ottimalità

Nel capitolo precedente, hai appreso le equazioni di Bellman per le funzioni di valore di stato e di valore stato-azione. Queste equazioni descrivono come i valori degli stati possano essere definiti ricorsivamente attraverso i valori di altri stati, con i valori che dipendono da una determinata politica. Tuttavia, non tutte le politiche sono ugualmente efficaci. Infatti, le funzioni di valore forniscono un ordinamento parziale per le politiche, che può essere descritto come segue:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Quindi la politica π\pi è migliore o uguale alla politica π′\pi' se, per tutti gli stati possibili, il rendimento atteso della politica π\pi non è inferiore al rendimento atteso della politica π′\pi'.

Note
Approfondimento

Un ordinamento parziale segue le regole usuali dell'ordinamento ma non obbliga a confrontare ogni coppia. Nel nostro caso, possiamo classificare due politiche solo se producono gli stessi risultati, oppure se una supera chiaramente l'altra. In tutti gli altri casi, le politiche rimangono incomparabili.

Politica Ottimale

Note
Definizione

Per qualsiasi MDP, esiste almeno una politica che è buona quanto o migliore di tutte le altre politiche. Questa politica è chiamata politica ottimale π∗\pi_*. Sebbene possano esistere molte politiche ottimali, tutte sono indicate come π∗\pi_*.

Perché esiste sempre una politica ottimale?

Potresti chiederti perché una politica ottimale esiste sempre per qualsiasi MDP. È una domanda interessante, e l'intuizione alla base è sorprendentemente semplice. Ricorda che gli stati in un MDP catturano completamente la condizione dell'ambiente. Questo implica che ogni stato è indipendente dagli altri: l'azione scelta in uno stato non influisce sulle ricompense o sugli esiti ottenibili in un altro. Pertanto, selezionando l'azione ottimale in ciascuno stato separatamente, si ottiene naturalmente la migliore sequenza complessiva di azioni nell'intero processo. E questo insieme di azioni ottimali in ogni stato costituisce una politica ottimale.

Inoltre, esiste sempre almeno una politica che è sia ottimale sia deterministica. Infatti, se per uno stato ss, due azioni aa e a′a' producono lo stesso rendimento atteso, sceglierne solo una non influirà sull'ottimalità della politica. Applicando questo principio a ogni singolo stato, la politica diventerà deterministica pur mantenendo la sua ottimalità.

Funzioni di Valore Ottimali

Le politiche ottimali condividono le stesse funzioni di valore — un fatto che diventa evidente quando si considera come vengono confrontate le politiche. Questo significa che le politiche ottimali condividono sia la funzione di valore di stato sia la funzione di valore d'azione.

Inoltre, le funzioni di valore ottimali possiedono le proprie equazioni di Bellman che possono essere scritte senza fare riferimento a una politica specifica. Queste equazioni sono chiamate equazioni di ottimalità di Bellman.

Funzione di valore di stato ottimale

Note
Definizione

La funzione di valore di stato ottimale V∗V_* (o v∗v_*) rappresenta il rendimento atteso massimo ottenibile da uno stato specifico seguendo una politica ottimale.

Può essere definito matematicamente come segue:

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

L'equazione di ottimalità di Bellman per questa funzione di valore può essere derivata come segue:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuizione

Come già noto, esiste sempre almeno una politica che è sia ottimale sia deterministica. Una tale politica, per ogni stato, selezionerebbe costantemente una particolare azione che massimizza i ritorni attesi. Pertanto, la probabilità di scegliere questa azione ottimale sarebbe sempre 1, mentre la probabilità di scegliere qualsiasi altra azione sarebbe 0. Dato ciò, l'equazione di Bellman originale non necessita più dell'operatore di sommatoria. Invece, poiché sappiamo che selezioneremo sempre la migliore azione possibile, possiamo semplicemente sostituire la somma prendendo il massimo su tutte le azioni disponibili.

Funzione di valore d'azione ottimale

Note
Definizione

Funzione di valore d'azione ottimale Q∗Q_* (o q∗q_*) rappresenta il rendimento atteso massimo ottenibile eseguendo una determinata azione in uno stato specifico e seguendo successivamente la politica ottimale.

Può essere definita matematicamente come segue:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Equazione di ottimalità di Bellman per questa funzione di valore può essere derivata come segue:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuizione

Analogamente alla funzione di valore di stato, la somma può essere sostituita prendendo il massimo su tutte le azioni disponibili.

question mark

Perché esiste sempre una politica ottimale per qualsiasi processo decisionale di Markov?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 3. Capitolo 3
some-alt