Оцінювання Функції Цінності

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

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