Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Aprenda Melhoria de Política | Programação Dinâmica
Introdução ao Aprendizado por Reforço

bookMelhoria de Política

Note
Definição

Melhoria de política é um processo de aprimoramento da política com base nas estimativas atuais da função de valor.

Note
Observação

Assim como na avaliação de política, a melhoria de política pode ser realizada tanto com a função de valor de estado quanto com a função de valor de ação. Porém, para métodos de Programação Dinâmica, será utilizada a função de valor de estado.

Agora que é possível estimar a função de valor de estado para qualquer política, um próximo passo natural é explorar se existem políticas melhores do que a atual. Uma forma de fazer isso é considerar tomar uma ação diferente aa em um estado ss, e seguir a política atual em seguida. Se isso parece familiar, é porque é semelhante à forma como definimos a função de valor de ação:

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 esse novo valor for maior que o valor original do estado vπ(s)v_\pi(s), isso indica que tomar a ação aa no estado ss e então continuar com a política π\pi leva a resultados melhores do que seguir estritamente a política π\pi. Como os estados são independentes, é ótimo sempre selecionar a ação aa sempre que o estado ss for encontrado. Portanto, podemos construir uma política aprimorada π′\pi', idêntica à π\pi, exceto pelo fato de selecionar a ação aa no estado ss, o que seria superior à política original π\pi.

Teorema de Melhoria de Política

O raciocínio descrito acima pode ser generalizado como o teorema de melhoria de política:

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}

A demonstração deste teorema é relativamente simples e pode ser realizada por meio de uma substituição repetida:

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}

Estratégia de Melhoria

Embora atualizar as ações para certos estados possa levar a melhorias, é mais eficaz atualizar as ações para todos os estados simultaneamente. Especificamente, para cada estado ss, selecionar a ação aa que maximiza o valor da ação 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}

onde arg max⁡\argmax (abreviação de argumento do máximo) é um operador que retorna o valor da variável que maximiza uma determinada função.

A política gananciosa resultante, denotada por π′\pi', satisfaz as condições do teorema de melhoria de política por construção, garantindo que π′\pi' seja pelo menos tão boa quanto a política original π\pi, e tipicamente melhor.

Se π′\pi' for tão boa quanto, mas não melhor que π\pi, então ambas π′\pi' e π\pi são políticas ótimas, pois suas funções de valor são iguais e satisfazem a equação de otimalidade de 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

Como a adoção de uma política gananciosa garante uma melhoria em relação à política anterior?

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 3. Capítulo 5

Pergunte à IA

expand

Pergunte à IA

ChatGPT

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

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

bookMelhoria de Política

Deslize para mostrar o menu

Note
Definição

Melhoria de política é um processo de aprimoramento da política com base nas estimativas atuais da função de valor.

Note
Observação

Assim como na avaliação de política, a melhoria de política pode ser realizada tanto com a função de valor de estado quanto com a função de valor de ação. Porém, para métodos de Programação Dinâmica, será utilizada a função de valor de estado.

Agora que é possível estimar a função de valor de estado para qualquer política, um próximo passo natural é explorar se existem políticas melhores do que a atual. Uma forma de fazer isso é considerar tomar uma ação diferente aa em um estado ss, e seguir a política atual em seguida. Se isso parece familiar, é porque é semelhante à forma como definimos a função de valor de ação:

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 esse novo valor for maior que o valor original do estado vπ(s)v_\pi(s), isso indica que tomar a ação aa no estado ss e então continuar com a política π\pi leva a resultados melhores do que seguir estritamente a política π\pi. Como os estados são independentes, é ótimo sempre selecionar a ação aa sempre que o estado ss for encontrado. Portanto, podemos construir uma política aprimorada π′\pi', idêntica à π\pi, exceto pelo fato de selecionar a ação aa no estado ss, o que seria superior à política original π\pi.

Teorema de Melhoria de Política

O raciocínio descrito acima pode ser generalizado como o teorema de melhoria de política:

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}

A demonstração deste teorema é relativamente simples e pode ser realizada por meio de uma substituição repetida:

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}

Estratégia de Melhoria

Embora atualizar as ações para certos estados possa levar a melhorias, é mais eficaz atualizar as ações para todos os estados simultaneamente. Especificamente, para cada estado ss, selecionar a ação aa que maximiza o valor da ação 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}

onde arg max⁡\argmax (abreviação de argumento do máximo) é um operador que retorna o valor da variável que maximiza uma determinada função.

A política gananciosa resultante, denotada por π′\pi', satisfaz as condições do teorema de melhoria de política por construção, garantindo que π′\pi' seja pelo menos tão boa quanto a política original π\pi, e tipicamente melhor.

Se π′\pi' for tão boa quanto, mas não melhor que π\pi, então ambas π′\pi' e π\pi são políticas ótimas, pois suas funções de valor são iguais e satisfazem a equação de otimalidade de 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

Como a adoção de uma política gananciosa garante uma melhoria em relação à política anterior?

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 3. Capítulo 5
some-alt