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
course content

Conteúdo do Curso

Introdução ao Aprendizado por Reforço

Introdução ao Aprendizado por Reforço

1. Teoria Central de RL
O Que É RL?RL vs. Outros Paradigmas de AprendizadoProcesso de Decisão de MarkovEpisódios e RetornosModelo, Política e ValoresExploração vs ExploraçãoNoções Básicas de GymnasiumDesafio: Configurando um Ambiente
2. Problema do Bandido de Múltiplos Braços
Introdução ao ProblemaValores de AçãoAlgoritmo Epsilon-GreedyAlgoritmo do Limite Superior de ConfiançaAlgoritmo de Bandido por GradienteDesafio: Problema dos Multi-Armed Bandits
3. Programação Dinâmica
O Que É Programação Dinâmica?Equações de BellmanCondições de OtimalidadeAvaliação de PolíticaMelhoria de PolíticaIteração de Política GeneralizadaIteração de PolíticaIteração de ValorDesafio: Programação Dinâmica
4. Métodos de Monte Carlo
O Que São Métodos de Monte Carlo?Estimação da Função de ValorControle de Monte CarloAbordagens de ExploraçãoControle Monte Carlo On-PolicyControle Monte Carlo Off-PolicyImplementações IncrementaisDesafio: Métodos de Monte Carlo
5. Aprendizado por Diferença Temporal
O Que É Aprendizado por Diferença Temporal?TD(0): Estimativa da Função de ValorSARSA: Aprendizado TD On-PolicyQ-Learning: Aprendizado TD Off-PolicyGeneralização do Aprendizado TDDesafio: Aprendizado por Diferença Temporal

book
Condições de Otimalidade

No capítulo anterior, você aprendeu sobre as equações de Bellman para funções de valor de estado e de 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 os valores dependentes de uma política dada. 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 totalmente 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' resultam no 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.

Funções de Valor Ótimas

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, 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 matematicamente definido 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 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 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 será selecionada a melhor ação possível, basta 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 essa 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 por um máximo sobre 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

course content

Conteúdo do Curso

Introdução ao Aprendizado por Reforço

Introdução ao Aprendizado por Reforço

1. Teoria Central de RL
O Que É RL?RL vs. Outros Paradigmas de AprendizadoProcesso de Decisão de MarkovEpisódios e RetornosModelo, Política e ValoresExploração vs ExploraçãoNoções Básicas de GymnasiumDesafio: Configurando um Ambiente
2. Problema do Bandido de Múltiplos Braços
Introdução ao ProblemaValores de AçãoAlgoritmo Epsilon-GreedyAlgoritmo do Limite Superior de ConfiançaAlgoritmo de Bandido por GradienteDesafio: Problema dos Multi-Armed Bandits
3. Programação Dinâmica
O Que É Programação Dinâmica?Equações de BellmanCondições de OtimalidadeAvaliação de PolíticaMelhoria de PolíticaIteração de Política GeneralizadaIteração de PolíticaIteração de ValorDesafio: Programação Dinâmica
4. Métodos de Monte Carlo
O Que São Métodos de Monte Carlo?Estimação da Função de ValorControle de Monte CarloAbordagens de ExploraçãoControle Monte Carlo On-PolicyControle Monte Carlo Off-PolicyImplementações IncrementaisDesafio: Métodos de Monte Carlo
5. Aprendizado por Diferença Temporal
O Que É Aprendizado por Diferença Temporal?TD(0): Estimativa da Função de ValorSARSA: Aprendizado TD On-PolicyQ-Learning: Aprendizado TD Off-PolicyGeneralização do Aprendizado TDDesafio: Aprendizado por Diferença Temporal

book
Condições de Otimalidade

No capítulo anterior, você aprendeu sobre as equações de Bellman para funções de valor de estado e de 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 os valores dependentes de uma política dada. 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 totalmente 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' resultam no 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.

Funções de Valor Ótimas

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, 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 matematicamente definido 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 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 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 será selecionada a melhor ação possível, basta 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 essa 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 por um máximo sobre 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