Почнемо з повторення знайомого поняття: функція цінності стану, яка позначається як $v_\pi(s)$. Її можна визначити так:

Мета цього розділу — оцінити цю функцію на основі даних, припускаючи, що задано фіксовану політику $\pi$, але немає доступу до моделі середовища.

Оцінювання методом Монте-Карло

Методи Монте-Карло виконують це завдання оцінювання шляхом вибірки епізодів досвіду згідно з політикою $\pi$, а потім використовують ці вибірки для емпіричного оцінювання $v_\pi(s)$.

Загалом процес можна розділити на такі етапи:

1. Згенерувати епізод, використовуючи політику $\pi$;
2. Зберегти отримане значення виграшу для кожного стану, що з'являється в епізоді;
3. Повторювати кроки 1-2 певний час;
4. Обчислити нові значення шляхом усереднення виграшів для кожного стану.

Збір повернень

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

• Перший візит: для кожного стану $s$, який зустрічається в епізоді, враховується лише повернення після його першої появи. Наступні появи того ж стану в межах одного епізоду ігноруються для цілей оцінювання;
• Кожен візит: враховується кожна поява стану $s$ в епізоді. Тобто повернення після кожного відвідування стану включається в оцінку, навіть якщо стан з'являється кілька разів у тому ж епізоді.

Дослідження стартових станів

Уявіть собі простий одномірний світ, представлений у вигляді лінії, що простягається від -10 до +10. Агент починає з позиції 0, і його поточна політика передбачає, що на кожному кроці він завжди рухається вправо.

Якщо ми спробуємо згенерувати епізоди за цією політикою, що відбудеться? Агент буде постійно рухатися до позитивного кінця лінії — відвідуючи стани 1, 2, 3 і так далі — але ніколи не відвідає жодного негативного стану. У результаті ми не можемо оцінити функції цінності для станів ліворуч від початку координат, просто тому, що агент їх ніколи не відчуває.

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

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

Псевдокод

Цей псевдокод використовує підхід кожного відвідування разом із дослідницькими стартами.