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

bookEquações de Bellman

Note
Definição

Uma equação de Bellman é uma equação funcional que define uma função de valor em forma recursiva.

Para esclarecer a definição:

  • Uma equação funcional é uma equação cuja solução é uma função. Para a equação de Bellman, essa solução é a função de valor para a qual a equação foi formulada;
  • Uma forma recursiva significa que o valor no estado atual é expresso em termos dos valores nos estados futuros.

Em resumo, resolver a equação de Bellman fornece a função de valor desejada, e derivar essa equação exige identificar uma relação recursiva entre os estados atuais e futuros.

Função de Valor de Estado

Como lembrete, aqui está uma função de valor de estado em forma compacta:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Para obter a equação de Bellman para esta função de valor, vamos expandir o lado direito da equação e estabelecer uma relação recursiva:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

A última equação desta cadeia é uma equação de Bellman para a função de valor de estado.

Intuição

Para encontrar o valor de um estado ss, deve-se:

  1. Considerar todas as possíveis ações aa que podem ser tomadas a partir deste estado, cada uma ponderada pela probabilidade de escolha sob a política atual π(a∣s)\pi(a | s);
  2. Para cada ação aa, considerar todos os possíveis próximos estados s′s' e recompensas rr, ponderados por sua probabilidade p(s′,r∣s,a)p(s', r | s, a);
  3. Para cada um desses resultados, somar a recompensa imediata rr recebida mais o valor descontado do próximo estado γvπ(s′)\gamma v_\pi(s').

Ao somar todas essas possibilidades, obtém-se o valor esperado total do estado ss sob a política atual.

Função de Valor de Ação

Aqui está uma função de valor de ação em forma compacta:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

A dedução da equação de Bellman para esta função é bastante semelhante à anterior:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

A última equação desta cadeia é uma equação de Bellman para a função de valor de ação.

Intuição

Para encontrar o valor de um par estado-ação (s,a)(s, a), você:

  1. Considera todos os possíveis próximos estados s′s' e recompensas rr, ponderados pela sua probabilidade p(s′,r∣s,a)p(s', r | s, a);
  2. Para cada um desses resultados, soma a recompensa imediata rr recebida mais o valor descontado do próximo estado;
  3. Para calcular o valor do próximo estado s′s', para todas as ações a′a' possíveis a partir do estado s′s', multiplica o valor da ação q(s′,a′)q(s', a') pela probabilidade de escolher a′a' no estado s′s' sob a política atual π(a′∣s′\pi(a' | s'. Em seguida, soma tudo para obter o valor final.

Ao somar todas essas possibilidades, obtém-se o valor esperado total do par estado-ação (s,a)(s, a) sob a política atual.

question mark

Qual das alternativas a seguir melhor descreve a função da equação de Bellman?

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 3. Capítulo 2

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

bookEquações de Bellman

Deslize para mostrar o menu

Note
Definição

Uma equação de Bellman é uma equação funcional que define uma função de valor em forma recursiva.

Para esclarecer a definição:

  • Uma equação funcional é uma equação cuja solução é uma função. Para a equação de Bellman, essa solução é a função de valor para a qual a equação foi formulada;
  • Uma forma recursiva significa que o valor no estado atual é expresso em termos dos valores nos estados futuros.

Em resumo, resolver a equação de Bellman fornece a função de valor desejada, e derivar essa equação exige identificar uma relação recursiva entre os estados atuais e futuros.

Função de Valor de Estado

Como lembrete, aqui está uma função de valor de estado em forma compacta:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Para obter a equação de Bellman para esta função de valor, vamos expandir o lado direito da equação e estabelecer uma relação recursiva:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

A última equação desta cadeia é uma equação de Bellman para a função de valor de estado.

Intuição

Para encontrar o valor de um estado ss, deve-se:

  1. Considerar todas as possíveis ações aa que podem ser tomadas a partir deste estado, cada uma ponderada pela probabilidade de escolha sob a política atual π(a∣s)\pi(a | s);
  2. Para cada ação aa, considerar todos os possíveis próximos estados s′s' e recompensas rr, ponderados por sua probabilidade p(s′,r∣s,a)p(s', r | s, a);
  3. Para cada um desses resultados, somar a recompensa imediata rr recebida mais o valor descontado do próximo estado γvπ(s′)\gamma v_\pi(s').

Ao somar todas essas possibilidades, obtém-se o valor esperado total do estado ss sob a política atual.

Função de Valor de Ação

Aqui está uma função de valor de ação em forma compacta:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

A dedução da equação de Bellman para esta função é bastante semelhante à anterior:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

A última equação desta cadeia é uma equação de Bellman para a função de valor de ação.

Intuição

Para encontrar o valor de um par estado-ação (s,a)(s, a), você:

  1. Considera todos os possíveis próximos estados s′s' e recompensas rr, ponderados pela sua probabilidade p(s′,r∣s,a)p(s', r | s, a);
  2. Para cada um desses resultados, soma a recompensa imediata rr recebida mais o valor descontado do próximo estado;
  3. Para calcular o valor do próximo estado s′s', para todas as ações a′a' possíveis a partir do estado s′s', multiplica o valor da ação q(s′,a′)q(s', a') pela probabilidade de escolher a′a' no estado s′s' sob a política atual π(a′∣s′\pi(a' | s'. Em seguida, soma tudo para obter o valor final.

Ao somar todas essas possibilidades, obtém-se o valor esperado total do par estado-ação (s,a)(s, a) sob a política atual.

question mark

Qual das alternativas a seguir melhor descreve a função da equação de Bellman?

Select the correct answer

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

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