Замінюючи крок оцінки політики у стандартному алгоритмі ітерації політики на методи оцінки Монте-Карло, описані в попередньому розділі, ми вже можемо отримати новий варіант ітерації політики — той, що ґрунтується на досвіді з вибірки, а не на динамічному програмуванні.

Однак існує важливе обмеження. У традиційній ітерації політики крок покращення політики залежить від наявності повної моделі середовища. Зокрема, для оновлення політики використовується наступний вираз:

Це рівняння передбачає, що нам відомі ймовірності переходу $p(s', r | s, a)$. Але саме в цьому і полягає проблема: методи Монте-Карло призначені для налаштувань без моделі, коли динаміка переходів у середовищі невідома. Якщо повна модель доступна, тоді доцільніше використовувати динамічне програмування на всіх етапах, включаючи оцінку політики, оскільки це буде ефективніше та точніше.

Отже, хоча заміна методів оцінки значення на Монте-Карло є кроком до навчання з підкріпленням без моделі, нам також потрібно знайти спосіб виконувати покращення політики без опори на знання моделі. Це вимагає переходу від функції цінності стану до функції цінності дії.

Чому саме цінності дій?

Використовуючи цінності дій, можна виконувати покращення політики без необхідності мати модель середовища. Замість того, щоб покладатися на ймовірності переходу для обчислення очікуваних виграшів, ми можемо безпосередньо обирати дії, які, ймовірно, дають найвищу цінність. Крок покращення політики тоді виглядає так:

І неважко довести, що нова політика не гірша за попередню, оскільки теорема покращення політики все ще застосовується:

І, як і у випадку з DP, ця теорема гарантує, що або $\pi_{k+1}$ краща за $\pi_k$, або вони обидві рівні й оптимальні.

Оцінювання функції значення дії

Процес оцінювання майже ідентичний до функції значення стану. Усі ідеї, що використовуються для оцінювання значень стану, можуть бути застосовані для оцінювання значень дій.

Псевдокод

Таким чином, після достатньої кількості ітерацій, оцінені значення дій наближаються до справжніх значень дій.

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

Оптимізація

Хоча крок оцінки можна виконувати за допомогою оцінювання Монте-Карло, як описано вище, цей підхід зазвичай є обчислювально неефективним. Як вже було показано, методи Монте-Карло зазвичай потребують великої кількості вибірок для отримання достатньо точних оцінок. Якщо дотримуватися структури, подібної до ітерації політики, ця неефективність лише посилюється: після кожного покращення політики потрібно знову запускати оцінювання Монте-Карло для переоцінки нової політики — це призводить до значних витрат часу та повільного навчання.

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

Це призводить до методу, який більше нагадує ітерацію значень: поєднання елементів оцінки та покращення в одному кроці. Це підвищує ефективність використання вибірок і пришвидшує обчислення.

Псевдокод

Цей алгоритм слідує структурі GPI, оскільки містить етапи оцінки політики та покращення політики, і називається керування Монте-Карло. Основний недолік цієї конкретної реалізації — припущення про дослідницькі старти. У наступних розділах ви дізнаєтеся, чому це є проблемою та як з цим можна впоратися.