Методы прогнозирования Монте-Карло с примерами кода

Недавно я начал курс обучения с подкреплением под названием Move37 от Siraj Raval. Я закончил третью неделю курса, посвященного методам обучения с подкреплением методом Монте-Карло (MC). Ниже я собираюсь обобщить методы прогнозирования MC, используемые в обучении с подкреплением, а в следующих частях я расскажу о методах управления MC и обучения с временной разностью (TD), каждый из них с примерами кода. Итак, давайте погрузимся.

Необходимое условие: чтобы понять концепции, обсуждаемые в этой статье, необходимо иметь хотя бы базовое представление об обучении с подкреплением (rl), марковских процессах принятия решений (MDP), уравнениях Беллмана и динамическом программировании (DP). . Для быстрого ознакомления с этими темами можно просмотреть эпизоды 1–4 серии этот блог и этот блог от neptune.ai.

Изучив rl, MDP и DP, можно было бы понять, что центральная идея rl состоит в том, чтобы найти оптимальную политику, то есть политику, которая максимизирует вознаграждение, возвращаемое средой (env). Таким образом, цель каждого rl-алгоритма (algo/algos) состоит в том, чтобы найти оптимальную политику, т. е. наилучший способ поведения в MDP (который на жаргоне rl называется контролем), и определить эффективность политики, т. е. вычислить функции ценности. MDP (что на жаргоне RL называется прогнозированием или оценкой политики). Выяснение эффективности политики важно, потому что только тогда можно судить, является ли политика оптимальной или нет.

При применении этого алгоритма могут быть разные ограничения на агентов и MDP, например, если мы обучаем rl-агента управлять вертолетом, то мы точно не знаем, с какого направления может дуть ветер в следующий момент, т.е. точно не знаю динамику (вероятность перехода и вознаграждения в MDP) MDP (или env), или динамика известна, но слишком велика, чтобы использовать ее, кроме как по образцам. Алгоритмы для работы с такими ограничениями на MDP называются алгоритмами без модели (свободными от динамики среды) и отличаются от алгоритмов, которые могут применяться к полностью известным MDP, также называемым алгоритмами на основе моделей. Методы DP популярны для решения (т.е. для поиска оптимальной политики) полностью известных MDP или envs, например. итерация политики и итерация значения.

В реальных задачах большую часть времени мы не знаем динамики среды, поэтому алгоритмы без моделей будут наиболее полезными и практичными. Алгоритмы без моделей работают с выбранными эпизодами из env (env), т.е. набора случайно выбранных состояний, действий и вознаграждений. Два типа алгоритмов без моделей, которые мы рассмотрим здесь и в следующих сообщениях блога, — это обучение MC и TD соответственно. В этом блоге мы обсудим методы прогнозирования MC.

Прогноз Монте-Карло (или оценка политики MC)

В алгоритмах прогнозирования наша главная цель — найти функции ценности для данной политики. DP достигает этого, используя итеративное применение уравнений ожидания Беллмана. Предсказание MC достигается путем
а) выборки полных эпизодов (т. е. конечное состояние является конечным состоянием) из окружения, а затем
б) вычисления среднего значения результатов выборки для каждого состояния по разным эпизодам.

Предсказание MC бывает двух разных видов:
i) MC при первом посещении: здесь мы рассматриваем каждое состояние только в первый раз, когда оно встречается в эпизоде, чтобы найти его возвращение.
ii) MC при каждом посещении. : Здесь мы рассматриваем каждое состояние каждый раз, когда оно встречается в эпизоде, чтобы найти его возвращение.

Для дальнейшего разъяснения вы можете ознакомиться со слайдами лекций из Курса Дэвида Сильвера по RL. Но основная идея заключается в том, что если мы рассматриваем V(s) как оценку функции значения состояния для состояния s, а Vπ(s) как фактическую функцию значения состояния, то

где S(s) – это сумма возвратов для состояния s по всем эпизодам, а N(s) – количество повторений состояния s. было посещено, т.е. V(s) является простым средним значением возврата, и по закону больших чисел мы знаем, что

то есть, если мы посетим каждое состояние достаточное количество раз, мы получим несмещенную оценку функции значения состояния.

Еще одна важная концепция, которую следует здесь понять, — это постепенное обновление среднего значения. Основная идея заключается в том, что мы можем записать среднее значение k чисел как сумму среднего значения k-1 чисел и разницы между k-м числом и средним значением k-1 чисел. В нашем алгоритме прогнозирования он преобразуется в

Ниже приведен код для каждого прогноза посещения MC в тренажерном зале Cartpole env: