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:

onde $\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)$ e a quantidade de vezes que o par estado-ação $(s, a)$ foi visitado $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:

mas $\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)$, mas por $\sum \rho(s, a)$.

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

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

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

Pseudocódigo