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 miglioramento della policy basato sulle stime attuali della funzione di valore.

Note
Nota

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

Ora che puoi stimare la funzione di valore di stato per qualsiasi policy, un passo successivo naturale è esplorare se esistono policy migliori di quella attuale. Un modo per farlo è considerare di intraprendere un'azione diversa aa in uno stato ss, e seguire la policy attuale successivamente. Se questo ti sembra familiare, è perché è simile a come definiamo 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, possiamo costruire una politica migliorata π′\pi', identica a π\pi tranne per il fatto che seleziona l'azione aa nello stato ss, che sarebbe superiore alla politica originale π\pi.

Teorema di miglioramento della politica

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

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)\qquqquad∀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) \qquqquad &\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 alcuni stati possa portare a dei 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 data funzione.

La politica greedy risultante, indicata con π′\pi', soddisfa le condizioni del teorema di miglioramento della politica per costruzione, 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

Awesome!

Completion rate improved to 2.7

bookMiglioramento della Policy

Scorri per mostrare il menu

Note
Definizione

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

Note
Nota

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

Ora che puoi stimare la funzione di valore di stato per qualsiasi policy, un passo successivo naturale è esplorare se esistono policy migliori di quella attuale. Un modo per farlo è considerare di intraprendere un'azione diversa aa in uno stato ss, e seguire la policy attuale successivamente. Se questo ti sembra familiare, è perché è simile a come definiamo 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, possiamo costruire una politica migliorata π′\pi', identica a π\pi tranne per il fatto che seleziona l'azione aa nello stato ss, che sarebbe superiore alla politica originale π\pi.

Teorema di miglioramento della politica

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

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)\qquqquad∀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) \qquqquad &\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 alcuni stati possa portare a dei 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 data funzione.

La politica greedy risultante, indicata con π′\pi', soddisfa le condizioni del teorema di miglioramento della politica per costruzione, 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