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

Зберігання кожного повернення для кожної пари стан-дія може швидко вичерпати пам'ять і суттєво збільшити час обчислень — особливо у великих середовищах. Це обмеження впливає як на 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 Monte Carlo Control

Для off-policy методу з звичайним імпортанс-семплінгом усе відбувається так само, як і для on-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)$:

Псевдокод