Інкрементні Реалізації

Зберігання кожного повернення для кожної пари стан-дія може швидко вичерпати пам'ять і суттєво збільшити час обчислення — особливо у великих середовищах. Це обмеження впливає як на on-policy, так і на off-policy алгоритми керування Монте-Карло. Для вирішення цієї проблеми застосовуються інкрементальні стратегії обчислення, подібні до тих, що використовуються в алгоритмах багаторуких бандитів. Ці методи дозволяють оновлювати оцінки значень на льоту, без необхідності зберігати всю історію повернень.

On-Policy Monte Carlo Control

Для on-policy методу стратегія оновлення подібна до стратегії, що використовується в алгоритмах MAB:

де $\displaystyle \alpha = \frac{1}{N(s, a)}$ для оцінки середнього. Єдині значення, які потрібно зберігати — це поточні оцінки значень дій $Q(s, a)$ та кількість відвідувань пари стан-дія $(s, a)$ $N(s, a)$.

Псевдокод

Off-policy керування методом Монте-Карло

Для позаполітичного методу з звичайним важливісним вибірковим методом усе відбувається так само, як і для політичного методу.

Більш цікава ситуація виникає з зваженим важливісним вибірковим методом. Рівняння виглядає так само:

але $\displaystyle \alpha = \frac{1}{N(s, a)}$ не можна використовувати, тому що:

1. Кожне повернення зважується за допомогою $\rho$;
2. Остаточна сума ділиться не на $N(s, a)$, а на $\sum \rho(s, a)$.

Значення $\alpha$, яке можна фактично використовувати в цьому випадку, дорівнює $\displaystyle \frac{W}{C(s,a)}$, де:

• $W$ — це $\rho$ для поточної траєкторії;
• $C(s, a)$ дорівнює $\sum \rho(s, a)$.

І кожного разу, коли пара стан-дія $(s, a)$ зустрічається, $\rho$ поточної траєкторії додається до $C(s, a)$:

Псевдокод