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
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
2. Problema do Bandido de Múltiplos Braços
3. Programação Dinâmica
4. Métodos de Monte Carlo
5. Aprendizado por Diferença Temporal

book
Implementaçõ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

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
2. Problema do Bandido de Múltiplos Braços
3. Programação Dinâmica
4. Métodos de Monte Carlo
5. Aprendizado por Diferença Temporal

book
Implementaçõ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
some-alt