Монте Карло и RL

Sep 28, 2019 12:44

Вообще термин "Монте Карло" (МК) используют для обозначения широкого спектра методов, основанных на повторении случайных выборок. В обучении с подкреплением (RL) методы МК позволяют производить оценку значений непосредственно из опыта: из последовательности состояний (state), действий (action) и вознаграждений (reward).

Обучение на опыте - хороший и удобный подход, поскольку агент может довольно точно оценивать функцию значений (value function) без априорных знаний того, как устроена динамика среды.

Конечно, для решения задач можно попытаться воспользоваться подходом, который предлагает динамическое программирование, но оказывается, что оно эффективно только в тех случаях, когда можно легко вычислить вероятности перехода агента из одного состояния в другое. В случае же, когда среда сложна, оценить эти вероятности становится очень сложно, а порой не просто сложно, а даже невозможно. Для примера представьте метеоролога, который пытается предсказать погоду. Изменения погоды зависят от такого большого количества факторов окружающей среды, что оценка всех вероятностей изменений состояний среды в будущем становится нерешаемой задачей.

Вычисление вероятностей перехода из одного состояния в другое может оказаться сложным даже для относительно простых задач. Представьте, что вы пытаетесь оценить исход двенадцатикратного бросания игральной кости. Решение этой задачи при помощи динамического программирования, с оценкой вероятностей всех возможных исходов всех состояний, оказывается довольно трудоёмким занятием. В этом случае может помочь МК, для которого не требуется совершать проход по всем состояниям. На самом деле, для МК не требуется знать вероятности даже одного исхода. Всё что нужно - это многократно совершить случайные выборки и усреднить полученные значения.

Приведённый ниже пример простой эмуляция пятидесяти попыток двенадцатикратного бросания кубика, дал среднее значение 41.631, которое оказалось очень близко к реальному среднему - 42.

gist.github.com/kukumber/27d6fa399158f48dd1d8b7bd174fc52e
В RL требуется найти функцию значения, которая отображает ожидаемое значение, поэтому метод МК должен получить многократный ответ от одного и того же состояния, а затем усреднить полученные значения для оценки истинного значения ответа этого состояния. С увеличением числа попыток среднее значение будет стремиться к истинному.

Методы МК очень похожи на методы многорукого бандита. Разница между ними состоит в том, что вычисление значения руки бандита происходит усреднением ответов, полученных от дёрганья этой конкретной руки, а методы МК для вычисления используют политики.

конспект, reinforcement learning, монте карло

Previous post Next post
Up