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

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

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

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

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

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

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

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

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

Дослідження початкових станів

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

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

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

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

Псевдокод

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