Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Aprenda Condições de Otimalidade | Programação Dinâmica
Introdução ao Aprendizado por Reforço com Python

Condições de Otimalidade

Deslize para mostrar o menu

No capítulo anterior, você aprendeu sobre as equações de Bellman para funções de valor de estado e valor de ação-estado. Essas equações descrevem como os valores dos estados podem ser definidos recursivamente por meio dos valores de outros estados, sendo dependentes de uma determinada política. No entanto, nem todas as políticas são igualmente eficazes. Na verdade, as funções de valor fornecem uma ordem parcial para as políticas, que pode ser descrita da seguinte forma:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Assim, a política π\pi é melhor ou igual à política π′\pi' se, para todos os estados possíveis, o retorno esperado da política π\pi não for menor que o retorno esperado da política π′\pi'.

Note
Estude Mais

Uma ordem parcial segue as regras usuais de ordenação, mas não exige que todo par seja comparado. No nosso caso, só podemos classificar duas políticas se elas produzirem os mesmos resultados ou se uma delas claramente superar a outra. Em todos os outros casos, as políticas permanecem incomparáveis.

Política Ótima

Note
Definição

Para qualquer MDP, existe pelo menos uma política que é tão boa quanto ou melhor do que todas as outras políticas. Essa política é chamada de política ótima π∗\pi_*. Embora possam existir muitas políticas ótimas, todas são denotadas como π∗\pi_*.

Por que sempre existe uma política ótima?

Você pode estar se perguntando por que uma política ótima sempre existe para qualquer MDP. Essa é uma ótima pergunta, e a intuição por trás disso é surpreendentemente simples. Lembre-se de que os estados em um MDP capturam completamente a condição do ambiente. Isso implica que cada estado é independente dos demais: a ação escolhida em um estado não afeta as recompensas ou resultados alcançáveis em outro. Portanto, ao selecionar a ação ótima em cada estado separadamente, você naturalmente chega à melhor sequência geral de ações em todo o processo. E esse conjunto de ações ótimas em cada estado constitui uma política ótima.

Além disso, sempre existe pelo menos uma política que é tanto ótima quanto determinística. De fato, se para algum estado ss, duas ações aa e a′a' produzem o mesmo retorno esperado, escolher apenas uma delas não afetará a otimalidade da política. Aplicando esse princípio a cada estado individualmente, a política se tornará determinística enquanto preserva sua otimalidade.

Exemplo de tornar uma política ótima determinística

Funções de valor ótimo

Políticas ótimas compartilham as mesmas funções de valor — um fato que se torna evidente ao considerarmos como as políticas são comparadas. Isso significa que políticas ótimas compartilham tanto a função de valor de estado quanto a função de valor de ação.

Além disso, as funções de valor ótimo possuem suas próprias equações de Bellman, que podem ser escritas sem referência a nenhuma política específica. Essas equações são chamadas de equações de otimalidade de Bellman.

Função de valor de estado ótimo

Note
Definição

Função de valor ótimo de estado V∗V_* (ou v∗v_*) representa o retorno esperado máximo alcançável a partir de um determinado estado ao seguir uma política ótima.

Pode ser definida matematicamente da seguinte forma:

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]

A equação de otimalidade de Bellman para essa função de valor pode ser derivada assim:

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}

Intuição

Como você já sabe, sempre existe pelo menos uma política que é tanto ótima quanto determinística. Tal política, para cada estado, selecionaria consistentemente uma ação específica que maximiza os retornos esperados. Portanto, a probabilidade de escolher essa ação ótima seria sempre 1, e a probabilidade de escolher qualquer outra ação seria 0. Diante disso, a equação de Bellman original não precisa mais do operador de soma. Em vez disso, como sabemos que sempre selecionaremos a melhor ação possível, podemos simplesmente substituir a soma por um máximo sobre todas as ações disponíveis.

Função valor de ação ótima

Note
Definição

Função valor de ação ótima Q∗Q_*(ou q∗q_*) representa o retorno esperado máximo alcançável ao tomar uma determinada ação em um determinado estado e seguir a política ótima posteriormente.

Pode ser definido matematicamente da seguinte forma:

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]

A equação de otimalidade de Bellman para essa função valor pode ser derivada assim:

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}

Intuição

De forma semelhante à função valor de estado, a soma pode ser substituída por tomar o máximo entre todas as ações disponíveis.

question mark

Por que sempre existe uma política ótima para qualquer processo de decisão de Markov?

Selecione a resposta correta

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 3. Capítulo 3

Pergunte à IA

expand

Pergunte à IA

ChatGPT

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

Condições de Otimalidade

No capítulo anterior, você aprendeu sobre as equações de Bellman para funções de valor de estado e valor de ação-estado. Essas equações descrevem como os valores dos estados podem ser definidos recursivamente por meio dos valores de outros estados, sendo dependentes de uma determinada política. No entanto, nem todas as políticas são igualmente eficazes. Na verdade, as funções de valor fornecem uma ordem parcial para as políticas, que pode ser descrita da seguinte forma:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Assim, a política π\pi é melhor ou igual à política π′\pi' se, para todos os estados possíveis, o retorno esperado da política π\pi não for menor que o retorno esperado da política π′\pi'.

Note
Estude Mais

Uma ordem parcial segue as regras usuais de ordenação, mas não exige que todo par seja comparado. No nosso caso, só podemos classificar duas políticas se elas produzirem os mesmos resultados ou se uma delas claramente superar a outra. Em todos os outros casos, as políticas permanecem incomparáveis.

Política Ótima

Note
Definição

Para qualquer MDP, existe pelo menos uma política que é tão boa quanto ou melhor do que todas as outras políticas. Essa política é chamada de política ótima π∗\pi_*. Embora possam existir muitas políticas ótimas, todas são denotadas como π∗\pi_*.

Por que sempre existe uma política ótima?

Você pode estar se perguntando por que uma política ótima sempre existe para qualquer MDP. Essa é uma ótima pergunta, e a intuição por trás disso é surpreendentemente simples. Lembre-se de que os estados em um MDP capturam completamente a condição do ambiente. Isso implica que cada estado é independente dos demais: a ação escolhida em um estado não afeta as recompensas ou resultados alcançáveis em outro. Portanto, ao selecionar a ação ótima em cada estado separadamente, você naturalmente chega à melhor sequência geral de ações em todo o processo. E esse conjunto de ações ótimas em cada estado constitui uma política ótima.

Além disso, sempre existe pelo menos uma política que é tanto ótima quanto determinística. De fato, se para algum estado ss, duas ações aa e a′a' produzem o mesmo retorno esperado, escolher apenas uma delas não afetará a otimalidade da política. Aplicando esse princípio a cada estado individualmente, a política se tornará determinística enquanto preserva sua otimalidade.

Exemplo de tornar uma política ótima determinística

Funções de valor ótimo

Políticas ótimas compartilham as mesmas funções de valor — um fato que se torna evidente ao considerarmos como as políticas são comparadas. Isso significa que políticas ótimas compartilham tanto a função de valor de estado quanto a função de valor de ação.

Além disso, as funções de valor ótimo possuem suas próprias equações de Bellman, que podem ser escritas sem referência a nenhuma política específica. Essas equações são chamadas de equações de otimalidade de Bellman.

Função de valor de estado ótimo

Note
Definição

Função de valor ótimo de estado V∗V_* (ou v∗v_*) representa o retorno esperado máximo alcançável a partir de um determinado estado ao seguir uma política ótima.

Pode ser definida matematicamente da seguinte forma:

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]

A equação de otimalidade de Bellman para essa função de valor pode ser derivada assim:

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}

Intuição

Como você já sabe, sempre existe pelo menos uma política que é tanto ótima quanto determinística. Tal política, para cada estado, selecionaria consistentemente uma ação específica que maximiza os retornos esperados. Portanto, a probabilidade de escolher essa ação ótima seria sempre 1, e a probabilidade de escolher qualquer outra ação seria 0. Diante disso, a equação de Bellman original não precisa mais do operador de soma. Em vez disso, como sabemos que sempre selecionaremos a melhor ação possível, podemos simplesmente substituir a soma por um máximo sobre todas as ações disponíveis.

Função valor de ação ótima

Note
Definição

Função valor de ação ótima Q∗Q_*(ou q∗q_*) representa o retorno esperado máximo alcançável ao tomar uma determinada ação em um determinado estado e seguir a política ótima posteriormente.

Pode ser definido matematicamente da seguinte forma:

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]

A equação de otimalidade de Bellman para essa função valor pode ser derivada assim:

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}

Intuição

De forma semelhante à função valor de estado, a soma pode ser substituída por tomar o máximo entre todas as ações disponíveis.

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

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