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

bookCondizioni 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
Approfondisci

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_*. Anche se possono 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 influenza le ricompense o gli 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 sia ottimale sia deterministica. Infatti, se per uno stato ss, due azioni aa e a′a' producono lo stesso ritorno atteso, sceglierne solo una non influirà sull'ottimalità della politica. Applicando questo principio a ogni singolo stato, la politica diventa 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 le politiche vengono confrontate. 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 riferimento a una politica specifica. Queste equazioni sono chiamate equazioni di ottimalità di Bellman.

Funzione di valore di stato ottimale

Note
Definizione

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]

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é si sa che verrà sempre selezionata la migliore azione possibile, si può 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

Suggested prompts:

Can you explain the difference between deterministic and stochastic policies?

How do Bellman optimality equations help in finding the optimal policy?

Can you provide an example of how to compute the optimal value function for a simple MDP?

Awesome!

Completion rate improved to 2.7

bookCondizioni di Ottimalità

Scorri per mostrare il menu

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
Approfondisci

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_*. Anche se possono 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 influenza le ricompense o gli 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 sia ottimale sia deterministica. Infatti, se per uno stato ss, due azioni aa e a′a' producono lo stesso ritorno atteso, sceglierne solo una non influirà sull'ottimalità della politica. Applicando questo principio a ogni singolo stato, la politica diventa 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 le politiche vengono confrontate. 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 riferimento a una politica specifica. Queste equazioni sono chiamate equazioni di ottimalità di Bellman.

Funzione di valore di stato ottimale

Note
Definizione

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]

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é si sa che verrà sempre selezionata la migliore azione possibile, si può 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