Керування методом Монте-Карло з політикою на основі поточної політики

Ідея on-policy методів інтуїтивно зрозуміла: агент навчається, дотримуючись своєї поточної політики, та покращує цю політику на основі отриманих результатів. Щоб знаходити кращі дії та уникати застрягання в субоптимальній поведінці, агент додає певний рівень випадковості — іноді пробує альтернативні дії для заохочення дослідження.

Аналогія

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

Спроба нового смаку не обов'язково була найлогічнішим вибором на основі попереднього досвіду, але дала можливість відкрити щось нове. Саме такий тип дослідження лежить в основі on-policy методів.

Стохастичні політики

Формально, застосування цієї ідеї означає заміну детермінованих (жорстких) політик, які використовуються в динамічному програмуванні, на стохастичні (м'які) політики, що позначаються як $\pi(a | s)$, де:

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

$\Large\varepsilon$-жадібні політики

Щоб включити дослідження у політику, скористаємося концепцією $\varepsilon$-жадібного дослідження з задачі про багаторукі бандити. Це дозволяє визначити стохастичну політику, яка балансує між використанням найкращої відомої дії та дослідженням альтернатив:

Ця політика поводиться жадібно більшість часу — обирає дію з найвищою оцінкою — але з ймовірністю $\varepsilon$ вибирає випадкову дію, забезпечуючи, що всі дії мають ненульовий шанс бути обраними (навіть жадібна дія може бути вибрана знову через рівномірне вибіркове дослідження).

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

Однак GPI не вимагає, щоб політика одразу ставала оптимальною — потрібно лише, щоб кожна політика покращувалася (або залишалася незмінною) порівняно з попередньою, поступово наближаючись до оптимальності. $\varepsilon$-жадібна політика задовольняє цю умову: вона покращує політику в середньому та забезпечує постійне дослідження для кращих оцінок.

Щоб вирішити питання збіжності до справді оптимальної політики, можна поступово зменшувати $\varepsilon$ з часом. Така стратегія дозволяє політиці ставати дедалі жадібнішою в міру навчання. На початкових етапах дослідження допомагає отримати різноманітний досвід, а на пізніших — агент використовує набуті знання. При належному зменшенні $\varepsilon$ метод збігається до оптимальної політики в межі.

Псевдокод