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

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

Методы Монте-Карло. Идея методов Монте-Карло состоит в том, чтобы рассчитать полную выборку доходности для каждого состояния (или пары состояние-действие) и усреднить такую ​​доходность по нескольким эпизодам. Это контрастирует с использованием ожидаемой доходности и, следовательно, потребует, чтобы задачи были эпизодическими.

Давайте теперь посмотрим на алгоритм прогнозирования MC при первом посещении, который используется для оценки функций ценности. Эпизод создается с использованием оцениваемой политики. Значение каждого состояния (или пары состояние-действие) - это доход, полученный от состояния (или пары состояние-действие), полученный путем суммирования вознаграждений от состояния (или пары состояние-действие) до конца эпизода. Мы рассматриваем только первое появление состояния (или пары состояние-действие), поэтому его называют алгоритмом первого посещения. Этот процесс повторяется бесконечно, генерируя эпизоды, и значение состояния (или пары состояние-действие) обновляется как среднее значение выборки. Эта способность учиться на образцах может быть значительным преимуществом, поскольку функцию динамики может быть трудно вычислить для многих сред.

Мы сосредоточимся на значениях состояния и действия (для краткости, значениях действия), поскольку они оказываются более полезными при отсутствии модели. Ниже представлена ​​реализация для прогнозирования MC при первом посещении.

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

Один из способов решить эту проблему - использовать начало исследования. Каждый эпизод начинается со случайной пары состояние-действие, где все пары состояние-действие равновероятны, а остальная часть эпизода генерируется с использованием политики.

Другой способ решить проблему исследования - использовать стохастическую политику, при которой каждое действие в каждом состоянии имеет некоторую ненулевую вероятность. Эта идея уступает место двум различным методам: методам, связанным с политикой и вне политики. Методы, основанные на политике, улучшают ту же политику, которая генерирует опыт, тогда как методы вне политики улучшают политику, отличную от той, которая используется для создания опыта.

Политическое обучение с использованием epsilon-greedy. Мы будем использовать обучение на основе политик, поэтому у нас будет фактически одна политика для создания эпизодов, а та же политика будет улучшена с помощью создания эпизодов. Политика, которую мы используем, будет эпсилон-жадной, чтобы позаботиться об исследовательском аспекте. При реализации нам не нужно поддерживать явную политику. Жадная функция epsilon определяется неявно с использованием текущих значений действия. Ниже представлена ​​реализация.

Среда лабиринта. Для нашего эксперимента мы будем использовать лабиринт в качестве среды, в которой агенту нужно достичь целевой позиции. За каждый шаг вознаграждение составляет -0,004, а за достижение цели - +1. Движение в лабиринте детерминировано, и каждый эпизод заканчивается, когда достигается цель или когда делается 2000 шагов. Ниже показано исходное состояние лабиринта.

Эксперимент. Я хотел бы обсудить в основном два параметра. Эпсилон, который контролирует степень исследования и количество опыта.

Эпсилон является частью политики агента, которая используется для создания опыта, на котором агент учится, а затем используется для действий в окружающей среде. Низкий эпсилон приводит к высокому исследованию, что приводит к разнообразному опыту, на котором можно учиться. Тем не менее, как только значения действий сходятся, политика остается весьма исследовательской, что приводит к неоптимальным доходам. С другой стороны, высокий эпсилон приводит к низкому уровню исследования, требующему большего опыта для схождения. Как только значения действий сходятся, политика становится лишь небольшой, что приводит к почти оптимальной отдаче.

Чтобы оценить эффект эпсилон и количество опыта, я обучил 25 разных агентов с разным эпсилон и размером опыта. Эпсилон варьируется от 0,1 до 0,9. Размер опыта варьируется от 10 до 1000. Наконец, каждый агент оценивается на 200 эпизодах в среде, где рассчитывается его общая отдача.

Это ожидаемый результат. Агенты с низким уровнем эпсилон сходятся быстрее, но достигают более низкой отдачи из-за высокой разведки. Агенты с высоким эпсилон сходятся медленнее, но достигают более высокой отдачи.

Ниже мы видим двух агентов Монте-Карло, решающих лабиринт. У того, что слева, низкий эпсилон и меньше опыта (0,2, 70). Тот, что справа, имеет высокий эпсилон и больше опыта (0,9, 1000).

Если вы заинтересованы в воспроизведении результатов или проведении собственных экспериментов, код доступен здесь.