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

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

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

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

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

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

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

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

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

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

Псевдокод

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

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

Оптимізація

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

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

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

Псевдокод

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