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

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

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