Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Impara Miglioramento della Policy | Programmazione Dinamica
Introduzione al Reinforcement Learning

bookMiglioramento della Policy

Note
Definizione

Miglioramento della policy è un processo di ottimizzazione della policy basato sulle stime attuali della funzione di valore.

Note
Nota

Come per la valutazione della policy, il miglioramento della policy può essere applicato sia alla funzione di valore di stato sia alla funzione di valore d'azione. Tuttavia, per i metodi DP, verrà utilizzata la funzione di valore di stato.

Ora che è possibile stimare la funzione di valore di stato per qualsiasi policy, un passo successivo naturale è esplorare se esistono policy migliori rispetto a quella attuale. Un modo per farlo consiste nel considerare l'esecuzione di un'azione diversa aa in uno stato ss, e seguire successivamente la policy corrente. Se questo sembra familiare, è perché è simile a come viene definita la funzione di valore d'azione:

qπ(s,a)=∑s′,rp(s′,r∣s,a)(r+γvπ(s′))q_\pi(s, a) = \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Se questo nuovo valore è maggiore del valore originale dello stato vπ(s)v_\pi(s), indica che intraprendere l'azione aa nello stato ss e poi continuare con la politica π\pi porta a risultati migliori rispetto a seguire rigorosamente la politica π\pi. Poiché gli stati sono indipendenti, è ottimale selezionare sempre l'azione aa ogni volta che si incontra lo stato ss. Pertanto, è possibile costruire una politica migliorata π′\pi', identica a π\pi tranne per il fatto che seleziona l'azione aa nello stato ss, che risulterebbe superiore rispetto alla politica originale π\pi.

Teorema del Miglioramento della Politica

Il ragionamento descritto sopra può essere generalizzato come il teorema del miglioramento della politica:

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)∀s∈S\begin{aligned} &q_\pi(s, \pi'(s)) \ge v_\pi(s) \qquad &\forall s \in S\\ \implies &v_{\pi'}(s) \ge v_\pi(s) \qquad &\forall s \in S \end{aligned}

La dimostrazione di questo teorema è relativamente semplice e può essere ottenuta tramite una sostituzione ripetuta:

vπ(s)≤qπ(s,π′(s))=E⁡π′[Rt+1+γvπ(St+1)∣St=s]≤E⁡π′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=E⁡π′[Rt+1+γE⁡π′[Rt+2+γvπ(St+2)]∣St=s]=E⁡π′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]...≤E⁡π′[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=vπ′(s)\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s))\\ &= \E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\\ &\le \E_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma \E_{\pi'}[R_{t+2} + \gamma v_\pi(S_{t+2})] | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t = s]\\ &...\\ &\le \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= v_{\pi'}(s) \end{aligned}

Strategia di miglioramento

Sebbene aggiornare le azioni per determinati stati possa portare a miglioramenti, è più efficace aggiornare le azioni per tutti gli stati simultaneamente. In particolare, per ogni stato ss, selezionare l'azione aa che massimizza il valore d'azione qπ(s,a)q_\pi(s, a):

π′(s)←arg max⁡aqπ(s,a)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\begin{aligned} \pi'(s) &\gets \argmax_a q_\pi(s, a)\\ &\gets \argmax_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

dove arg max⁡\argmax (abbreviazione di argomento del massimo) è un operatore che restituisce il valore della variabile che massimizza una determinata funzione.

La politica greedy risultante, indicata con π′\pi', soddisfa per costruzione le condizioni del teorema di miglioramento della politica, garantendo che π′\pi' sia almeno valida quanto la politica originale π\pi, e tipicamente migliore.

Se π′\pi' è valida quanto, ma non migliore di π\pi, allora sia π′\pi' che π\pi sono politiche ottimali, poiché le loro funzioni di valore sono uguali e soddisfano l'equazione di ottimalità di Bellman:

vπ(s)=max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)
question mark

In che modo l'adozione di una politica greedy garantisce un miglioramento rispetto alla politica precedente?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 3. Capitolo 5

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 policy improvement theorem in simpler terms?

How does the greedy policy guarantee improvement over the original policy?

What is the Bellman optimality equation and why is it important?

Awesome!

Completion rate improved to 2.7

bookMiglioramento della Policy

Scorri per mostrare il menu

Note
Definizione

Miglioramento della policy è un processo di ottimizzazione della policy basato sulle stime attuali della funzione di valore.

Note
Nota

Come per la valutazione della policy, il miglioramento della policy può essere applicato sia alla funzione di valore di stato sia alla funzione di valore d'azione. Tuttavia, per i metodi DP, verrà utilizzata la funzione di valore di stato.

Ora che è possibile stimare la funzione di valore di stato per qualsiasi policy, un passo successivo naturale è esplorare se esistono policy migliori rispetto a quella attuale. Un modo per farlo consiste nel considerare l'esecuzione di un'azione diversa aa in uno stato ss, e seguire successivamente la policy corrente. Se questo sembra familiare, è perché è simile a come viene definita la funzione di valore d'azione:

qπ(s,a)=∑s′,rp(s′,r∣s,a)(r+γvπ(s′))q_\pi(s, a) = \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Se questo nuovo valore è maggiore del valore originale dello stato vπ(s)v_\pi(s), indica che intraprendere l'azione aa nello stato ss e poi continuare con la politica π\pi porta a risultati migliori rispetto a seguire rigorosamente la politica π\pi. Poiché gli stati sono indipendenti, è ottimale selezionare sempre l'azione aa ogni volta che si incontra lo stato ss. Pertanto, è possibile costruire una politica migliorata π′\pi', identica a π\pi tranne per il fatto che seleziona l'azione aa nello stato ss, che risulterebbe superiore rispetto alla politica originale π\pi.

Teorema del Miglioramento della Politica

Il ragionamento descritto sopra può essere generalizzato come il teorema del miglioramento della politica:

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)∀s∈S\begin{aligned} &q_\pi(s, \pi'(s)) \ge v_\pi(s) \qquad &\forall s \in S\\ \implies &v_{\pi'}(s) \ge v_\pi(s) \qquad &\forall s \in S \end{aligned}

La dimostrazione di questo teorema è relativamente semplice e può essere ottenuta tramite una sostituzione ripetuta:

vπ(s)≤qπ(s,π′(s))=E⁡π′[Rt+1+γvπ(St+1)∣St=s]≤E⁡π′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=E⁡π′[Rt+1+γE⁡π′[Rt+2+γvπ(St+2)]∣St=s]=E⁡π′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]...≤E⁡π′[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=vπ′(s)\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s))\\ &= \E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\\ &\le \E_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma \E_{\pi'}[R_{t+2} + \gamma v_\pi(S_{t+2})] | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t = s]\\ &...\\ &\le \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= v_{\pi'}(s) \end{aligned}

Strategia di miglioramento

Sebbene aggiornare le azioni per determinati stati possa portare a miglioramenti, è più efficace aggiornare le azioni per tutti gli stati simultaneamente. In particolare, per ogni stato ss, selezionare l'azione aa che massimizza il valore d'azione qπ(s,a)q_\pi(s, a):

π′(s)←arg max⁡aqπ(s,a)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\begin{aligned} \pi'(s) &\gets \argmax_a q_\pi(s, a)\\ &\gets \argmax_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

dove arg max⁡\argmax (abbreviazione di argomento del massimo) è un operatore che restituisce il valore della variabile che massimizza una determinata funzione.

La politica greedy risultante, indicata con π′\pi', soddisfa per costruzione le condizioni del teorema di miglioramento della politica, garantendo che π′\pi' sia almeno valida quanto la politica originale π\pi, e tipicamente migliore.

Se π′\pi' è valida quanto, ma non migliore di π\pi, allora sia π′\pi' che π\pi sono politiche ottimali, poiché le loro funzioni di valore sono uguali e soddisfano l'equazione di ottimalità di Bellman:

vπ(s)=max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)
question mark

In che modo l'adozione di una politica greedy garantisce un miglioramento rispetto alla politica precedente?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 3. Capitolo 5
some-alt