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

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

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

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

Чому саме значення дій?

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

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

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

Оцінювання функції цінності дії

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

Псевдокод

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

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

Оптимізація

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

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

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

Псевдокод

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