Stocker chaque retour pour chaque paire état-action peut rapidement épuiser la mémoire et augmenter considérablement le temps de calcul — en particulier dans les environnements de grande taille. Cette limitation affecte à la fois les algorithmes de contrôle Monte Carlo on-policy et off-policy. Pour y remédier, nous adoptons des stratégies de calcul incrémentiel, similaires à celles utilisées dans les algorithmes multi-armed bandit. Ces méthodes permettent de mettre à jour les estimations de valeur à la volée, sans conserver l'historique complet des retours.

Contrôle Monte Carlo On-Policy

Pour la méthode on-policy, la stratégie de mise à jour ressemble à celle utilisée dans les algorithmes MAB :

où $\displaystyle \alpha = \frac{1}{N(s, a)}$ pour l'estimation de la moyenne. Les seules valeurs à stocker sont les estimations actuelles des valeurs d'action $Q(s, a)$ et le nombre de fois que la paire état-action $(s, a)$ a été visitée $N(s, a)$.

Pseudocode

Contrôle Monte Carlo hors politique

Pour la méthode hors politique avec l'échantillonnage d'importance ordinaire, tout est identique à la méthode sur politique.

Une situation plus intéressante se présente avec l'échantillonnage d'importance pondéré. L'équation reste la même :

mais $\displaystyle \alpha = \frac{1}{N(s, a)}$ ne peut pas être utilisé car :

1. Chaque retour est pondéré par $\rho$ ;
2. La somme finale est divisée non pas par $N(s, a)$, mais par $\sum \rho(s, a)$.

La valeur de $\alpha$ qui peut réellement être utilisée dans ce cas est égale à $\displaystyle \frac{W}{C(s,a)}$ où :

• $W$ est le $\rho$ pour la trajectoire courante ;
• $C(s, a)$ est égal à $\sum \rho(s, a)$.

Et chaque fois que la paire état-action $(s, a)$ apparaît, le $\rho$ de la trajectoire courante est ajouté à $C(s, a)$ :

Pseudocode