Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Aprenda Implementações Incrementais | Métodos de Monte Carlo
Introdução ao Aprendizado por Reforço

bookImplementações Incrementais

Armazenar cada retorno para cada par estado-ação pode rapidamente esgotar a memória e aumentar significativamente o tempo de computação — especialmente em ambientes grandes. Essa limitação afeta tanto os algoritmos de controle Monte Carlo on-policy quanto off-policy. Para lidar com isso, adotamos estratégias de computação incremental, semelhantes às utilizadas em algoritmos multi-armed bandit. Esses métodos permitem que as estimativas de valor sejam atualizadas em tempo real, sem a necessidade de manter todo o histórico de retornos.

Controle Monte Carlo On-Policy

Para o método on-policy, a estratégia de atualização é semelhante à utilizada em algoritmos MAB:

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

onde α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} para estimativa da média. Os únicos valores que precisam ser armazenados são as estimativas atuais dos valores de ação Q(s,a)Q(s, a) e a quantidade de vezes que o par estado-ação (s,a)(s, a) foi visitado N(s,a)N(s, a).

Pseudocódigo

Controle Monte Carlo Off-Policy

Para o método off-policy com amostragem de importância ordinária, tudo é igual ao método on-policy.

Uma situação mais interessante ocorre com amostragem de importância ponderada. A equação permanece a mesma:

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

mas α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} não pode ser usada porque:

  1. Cada retorno é ponderado por ρ\rho;
  2. A soma final é dividida não por N(s,a)N(s, a), mas por ρ(s,a)\sum \rho(s, a).

O valor de α\alpha que pode ser realmente utilizado neste caso é igual a WC(s,a)\displaystyle \frac{W}{C(s,a)} onde:

  • WW é o ρ\rho da trajetória atual;
  • C(s,a)C(s, a) é igual a ρ(s,a)\sum \rho(s, a).

E cada vez que o par estado-ação (s,a)(s, a) ocorre, o ρ\rho da trajetória atual é adicionado a C(s,a)C(s, a):

C(s,a)C(s,a)+WC(s, a) \gets C(s, a) + W

Pseudocódigo

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 4. Capítulo 7

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

bookImplementações Incrementais

Deslize para mostrar o menu

Armazenar cada retorno para cada par estado-ação pode rapidamente esgotar a memória e aumentar significativamente o tempo de computação — especialmente em ambientes grandes. Essa limitação afeta tanto os algoritmos de controle Monte Carlo on-policy quanto off-policy. Para lidar com isso, adotamos estratégias de computação incremental, semelhantes às utilizadas em algoritmos multi-armed bandit. Esses métodos permitem que as estimativas de valor sejam atualizadas em tempo real, sem a necessidade de manter todo o histórico de retornos.

Controle Monte Carlo On-Policy

Para o método on-policy, a estratégia de atualização é semelhante à utilizada em algoritmos MAB:

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

onde α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} para estimativa da média. Os únicos valores que precisam ser armazenados são as estimativas atuais dos valores de ação Q(s,a)Q(s, a) e a quantidade de vezes que o par estado-ação (s,a)(s, a) foi visitado N(s,a)N(s, a).

Pseudocódigo

Controle Monte Carlo Off-Policy

Para o método off-policy com amostragem de importância ordinária, tudo é igual ao método on-policy.

Uma situação mais interessante ocorre com amostragem de importância ponderada. A equação permanece a mesma:

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

mas α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} não pode ser usada porque:

  1. Cada retorno é ponderado por ρ\rho;
  2. A soma final é dividida não por N(s,a)N(s, a), mas por ρ(s,a)\sum \rho(s, a).

O valor de α\alpha que pode ser realmente utilizado neste caso é igual a WC(s,a)\displaystyle \frac{W}{C(s,a)} onde:

  • WW é o ρ\rho da trajetória atual;
  • C(s,a)C(s, a) é igual a ρ(s,a)\sum \rho(s, a).

E cada vez que o par estado-ação (s,a)(s, a) ocorre, o ρ\rho da trajetória atual é adicionado a C(s,a)C(s, a):

C(s,a)C(s,a)+WC(s, a) \gets C(s, a) + W

Pseudocódigo

Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 4. Capítulo 7
some-alt