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

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