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

bookCondições de Otimalidade

No capítulo anterior, foram apresentados os equacionamentos de Bellman para as funções de valor de estado e valor de ação-estado. Esses equacionamentos descrevem como os valores dos estados podem ser definidos recursivamente por meio dos valores de outros estados, sendo dependentes de uma política específica. 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 inferior ao retorno esperado da política π′\pi'.

Note
Aprofunde-se

Uma ordem parcial segue as regras usuais de ordenação, mas não exige que todo par seja comparado. Neste contexto, só é possível classificar duas políticas se elas produzirem os mesmos resultados ou se uma delas superar claramente a outra. Nos demais 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, chega-se naturalmente à 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' resultam no mesmo retorno esperado, selecionar apenas uma delas não afetará a otimalidade da política. Aplicando esse princípio a cada estado individualmente, a política se torna determinística enquanto preserva sua otimalidade.

Funções de Valor Ótimas

Políticas ótimas compartilham as mesmas funções de valor — um fato que se torna claro 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, funções de valor ótimas possuem suas próprias equações de Bellman, que podem ser escritas sem referência a uma política específica. Essas equações são chamadas de equações de otimalidade de Bellman.

Função de valor de estado ótima

Note
Definição

Função de valor de estado ótima 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 definido 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]

Equação de otimalidade de Bellman para esta função de valor pode ser derivada da seguinte maneira:

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 já se sabe, sempre existe pelo menos uma política que é ótima e determinística. Tal política, para cada estado, seleciona consistentemente uma ação específica que maximiza os retornos esperados. Portanto, a probabilidade de escolher essa ação ótima será sempre 1, e a probabilidade de escolher qualquer outra ação será 0. Diante disso, a equação original de Bellman 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-ação ótima

Note
Definição

Função valor-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 definida 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]

Equação de otimalidade de Bellman para esta função de valor pode ser derivada da seguinte forma:

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 de valor de estado, a soma pode ser substituída pela escolha do 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?

Select the correct answer

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

Awesome!

Completion rate improved to 2.7

bookCondições de Otimalidade

Deslize para mostrar o menu

No capítulo anterior, foram apresentados os equacionamentos de Bellman para as funções de valor de estado e valor de ação-estado. Esses equacionamentos descrevem como os valores dos estados podem ser definidos recursivamente por meio dos valores de outros estados, sendo dependentes de uma política específica. 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 inferior ao retorno esperado da política π′\pi'.

Note
Aprofunde-se

Uma ordem parcial segue as regras usuais de ordenação, mas não exige que todo par seja comparado. Neste contexto, só é possível classificar duas políticas se elas produzirem os mesmos resultados ou se uma delas superar claramente a outra. Nos demais 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, chega-se naturalmente à 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' resultam no mesmo retorno esperado, selecionar apenas uma delas não afetará a otimalidade da política. Aplicando esse princípio a cada estado individualmente, a política se torna determinística enquanto preserva sua otimalidade.

Funções de Valor Ótimas

Políticas ótimas compartilham as mesmas funções de valor — um fato que se torna claro 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, funções de valor ótimas possuem suas próprias equações de Bellman, que podem ser escritas sem referência a uma política específica. Essas equações são chamadas de equações de otimalidade de Bellman.

Função de valor de estado ótima

Note
Definição

Função de valor de estado ótima 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 definido 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]

Equação de otimalidade de Bellman para esta função de valor pode ser derivada da seguinte maneira:

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 já se sabe, sempre existe pelo menos uma política que é ótima e determinística. Tal política, para cada estado, seleciona consistentemente uma ação específica que maximiza os retornos esperados. Portanto, a probabilidade de escolher essa ação ótima será sempre 1, e a probabilidade de escolher qualquer outra ação será 0. Diante disso, a equação original de Bellman 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-ação ótima

Note
Definição

Função valor-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 definida 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]

Equação de otimalidade de Bellman para esta função de valor pode ser derivada da seguinte forma:

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 de valor de estado, a soma pode ser substituída pela escolha do 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?

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

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