Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Вивчайте Інкрементні Реалізації | Методи Монте-Карло
Вступ до навчання з підкріпленням

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

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

On-Policy Monte Carlo Control

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

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

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

Псевдокод

Off-Policy Monte Carlo Control

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

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

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

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

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

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

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

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

C(s,a)C(s,a)+WC(s, a) \gets C(s, a) + W

Псевдокод

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 4. Розділ 7

Запитати АІ

expand

Запитати АІ

ChatGPT

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Awesome!

Completion rate improved to 2.7

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

Свайпніть щоб показати меню

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

On-Policy Monte Carlo Control

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

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

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

Псевдокод

Off-Policy Monte Carlo Control

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

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

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

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

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

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

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

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

C(s,a)C(s,a)+WC(s, a) \gets C(s, a) + W

Псевдокод

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 4. Розділ 7
some-alt