Вивчайте Керування методом Монте-Карло

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

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

\pi(s) \gets \argmax_a \sum_{s', r} \textcolor{red}{p(s', r | s, a)} \Bigl(r + \gamma v(s')\Bigr)

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

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

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

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

\pi(s) \gets \argmax_a q(s, a) \qquad \forall s \in S

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

\begin{aligned} q_{\pi_{k}}(s, \pi_{k+1}(s)) &= q_{\pi_k}(s, \argmax_a q_{\pi_k}(s, a))\\ &= \max_a q_{\pi_k}(s, a)\\ &\ge q_{\pi_k}(s, \pi_k(s))\\ &= v_{\pi_k}(s) \end{aligned}

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

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

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

Псевдокод

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

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

Оптимізація

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

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

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

Псевдокод

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