Almacenar cada retorno para cada par estado-acción puede agotar rápidamente la memoria y aumentar significativamente el tiempo de cómputo, especialmente en entornos grandes. Esta limitación afecta tanto a los algoritmos de control Monte Carlo on-policy como off-policy. Para abordar este problema, se adoptan estrategias de cálculo incremental, similares a las utilizadas en los algoritmos de multi-armed bandit. Estos métodos permiten que las estimaciones de valor se actualicen en tiempo real, sin necesidad de conservar todo el historial de retornos.

Control Monte Carlo On-Policy

Para el método on-policy, la estrategia de actualización es similar a la utilizada en los algoritmos MAB:

donde $\displaystyle \alpha = \frac{1}{N(s, a)}$ para la estimación de la media. Los únicos valores que deben almacenarse son las estimaciones actuales de los valores de acción $Q(s, a)$ y la cantidad de veces que el par estado-acción $(s, a)$ ha sido visitado $N(s, a)$.

Pseudocódigo

Control Monte Carlo Fuera de Política

Para el método fuera de política con muestreo de importancia ordinario todo es igual que para el método en política.

Una situación más interesante ocurre con el muestreo de importancia ponderado. La ecuación se ve igual:

pero $\displaystyle \alpha = \frac{1}{N(s, a)}$ no puede usarse porque:

1. Cada retorno está ponderado por $\rho$;
2. La suma final no se divide por $N(s, a)$, sino por $\sum \rho(s, a)$.

El valor de $\alpha$ que realmente puede usarse en este caso es igual a $\displaystyle \frac{W}{C(s,a)}$ donde:

• $W$ es el $\rho$ para la trayectoria actual;
• $C(s, a)$ es igual a $\sum \rho(s, a)$.

Y cada vez que el par estado-acción $(s, a)$ ocurre, el $\rho$ de la trayectoria actual se suma a $C(s, a)$:

Pseudocódigo