Содержание

• DDQN_Snake_game
• Описание проекта
• Обзор алгоритма
  • Несколько моментов
  • Алгоритм
• История работы над проектом и прочие заметки
  • Змейка
    • Написание змейки
    • Вектор состояний и умная змейка
• Результаты работы
• Воспроизведение результатов
• Список литературы, которой я обязан всеми своими знаниями

DDQN_Snake_game

Это учебная реализация алгортма Double-DQN для игры в змейку.

Описание проекта

Проект представляет из себя алгоритм обучения с подкреплением, называемый q-обучение. Суть алгоритма, как и любого другого алгоритма обучения с подкреплением, состоит в том, чтобы составить некоторую стратегию действий агента, позволяющую получить максимальную выгоду. В q-обучении такой стратегией будет выбор действия из q-таблицы. В столбцах таблицы указаны все возможные действия, в строках - все возможные состояния. Таким образом значение ячейки q-таблицы будет отражать полезность (q - quality) выполнения конкретного действия из конкретного состояния.

Значения эти можно получить из уравнения Беллмана:

• Где:

  — состояние и новое состояние, в которое попадает агент, выполнив действие.

  — награда, полученная за совершение данного действия из данного состояния

  — значения q-функций для текущего и следующего состояний

  — гиперпараметры

Собственно, суть обучения заключается в изучении всех состояний и заполнении q-таблицы.

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

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

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

Обзор алгоритма

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

Несколько моментов

1. Epsilon-greedy police Политика поведения агента в среде, при которой он с вероятностью, равной Epsilon, выбирает случайное действие и с вероятностью 1-Epsilon выбирает действие, предсказанное моделью. Такая политика позволяет исследовать всю среду, улучшая предсказания модели, а не только выбирать самое выгодное действие. Обычно в ходе обучения модели Epsilon уменьшается. Таким образом, в самом начале обучения агент отдает предпочтение случайным действиям, чтобы исследовать всю среду, но в ходе обучения агент все больше и больше доверяет предсказаниям модели, стараясь максимизировать награду или достичь установленного правилами среды выигрыша.

2. Буфер памяти Поскольку обучения происходит прямо во время сбора данных, нужно как-то сохранять полученные данные, чтобы модель "не забывала" о том, что было раньше. Поэтому в моем алгоритме присутствует буфер памяти — список, каждый элемент которого — тьюпл вида . Таким образом, модель получает информацию о текущем состоянии, награду за него, следующее состояние, и булеву переменную , если игра закончилась на данном шаге, иначе .

3. Temporal Difference Error Об этой ошибке было сказано выше, но вкратце. Такой расчет не только следует из уравнения Беллмана, но и, более того, кажется логичным. Приведем формулу TD-Error:

   

   Видно, что она очень похожа на уравнение Беллмана, с той лишь разницей, что и — предсказанные разными моделями величины, зависящие от разных весов и )

   Некоторые улучшения, предпринятые автором

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

   1. Инициализируем модель
   2. Исследуем среду, добавляем данные в буфер
   3. Предсказываем и двумя разными моделями
   4. Если done = True для данного состояния, т.е. игра закончилась, то для такого случая заменяем предсказанное моделью значение Q-функции на 0 или награду, начисляемую за проигрыш (выигрыш).
   5. Считаем ошибку (Temporal Difference Error)
   6. Обновляем веса основной модели
   7. Каждые шагов копируем веса из основной модели в модель, предсказывающую полезность следующего состояния

   Такая методика обучения вносит стабильность в работу модели.

Алгоритм

1. В каждой итерации цикла обучения:
   1. Инициализируем начальное состояние среды
   2. Пока done ≠ True или не сделано максимальное число шагов:
      1. рассчитываем epsilon для e-greedy police
      2. выбираем действие согласно e-greedy police
      3. делаем шаг в среде, получая new_state, reward и done
      4. Если done=True, сохраняем в буфер state, action, reward, new_state, done, выходим из цикла игры.
      5. Иначе сохраняем в буфер state, action, reward, new_state, done, определяем state=new_state. Продолжаем играть
   3. Выбираем случайный батч размера batch_size из буфера
   4. Рассчитываем TD-Error:
      1. Рассчитываем q-функцию для следующего состояния
         1. target_q = target_model(next_state)
         2. target_q = target_q + gamma * reward
         3. target_q[done] = 0 — если игра закончилась на данном состоянии, предсказывать следующее нет смысла
      2. Рассчитываем q-функцию для следующего состояния:
         1. q = model(state)
         2. q = q.gather(1, actions) — мы уже знаем, какое действие было выбрано для каждого состояния из батча, поэтому нам нужна q-функция не для всех возможных действий из данного состояния, а только для действия, которое выбрал агент
      3. Рассчитываем ошибку — loss = MSELoss(q, q_target).
      4. Берем градиент ошибки — loss.backward()
      5. Делаем шаг оптимизатора, обновляем веса модели — optimiser.step .
   5. Если епоха % tau == 0, то копируем параметры model в target_model
2. Сохраняем модели и другие полезные данные, строим графики обучения
3. Тестируем модель, заставляя агента играть в игру

История работы над проектом и прочие заметки

Поскольку это первая моя реализация алгоритма обучения с подкреплением, использующая нейронные сети (и вторая вообще), я решил для начала протестировать алгоритм на одной из сред, предоставляемый фреймворком Open AI Gym, а именно -- MountainCar-v0. ##Mountain car Вот так выглядит эта среда. Суть игры в том, что нужно заехать машинкой на правый холм, совершив не более 200 ходов. Вектор состояния представляет из себя координату и проекцию скорости машинки на горизонтальную ось в данный момент времени. Из каждого состояния можно совершить три действия: двигаться влево, оставаться на месте или двигаться вправо, при этом просто двигаясь вправо на горку заехать не получится: не наберется нужная скорость.

Задача оказалась сложнее, чем я думал, ведь награда начислялась по принципу "-1 за шаг, +10 за завершение", что не позволяло модели понять, куда нужно двигаться, поэтому я применил такую хитрость: на каждой итерации прибавлял к награде разность модулей скоростей текущего и следующего состояния, сообщая модели, что, чем больше она разгонится, тем лучше. Результат не заставил себя ждать, и после переобучения модели я получил вот такой график зависимости награды (не модифицированной, -- по правилу "-1" за шаг, т.е. -200 -- если игра не завершена за 200 шагов, и т.д.) от итераций:

Для сравнения приведу график той же зависимости, но для модели, обученной на немодифицированной награде:

Змейка

Написание змейки

После удачных опытов с горной машинкой (0.0% проигранных игр за 15к тестов), я перешел к написанию змейки. Изначально мне с этим помог друг, за что ему огромное спасибо. Но впоследствии я решил, что лучше обернуть код змейки как наследника класса gym.Env, поскольку так будет удобнее работать с ней как со средой тренировки модели. Тогда я переписал код, обернув его, как хотел, и добавил несколько функций специально для удобства работы с игрой как со средой.

Вектор состояний и умная змейка

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

Алгоритм превзошел создателя. Змейка дорастала до определенной длины, после чего начинала ходить по кругу, увеличивая время жизни, но при этом получая не слишком маленькую награду за ход. Я пытался исправить это разными способами: если убирал награду за продолжительность жизни, змейка убивала себя об стену, считая это выгодным; если делал награду за ход слишком маленькой -- змейка убивала себя; если убирал длину змеи из награды, она убивалась о ближайшую стену. В итоге я не нашел решения лучше, чем анализировать последовательность ее ходов и снимать с нее очень много награды, если будет похоже, что она ходит по кругу. Сначала это помогло.

После удачных, но трудных (особенно для моих нервов) экспериментов с одномерным вектором параметров, я решил передавать скриншот игры, как параметр, характеризующий состояние, а нейронную сеть сделать сверточной. Учиться алгоритм стал намного (примерно в 40-50 раз) медленнее. Теперь уже нельзя было и вообразить, чтобы он учился хотя бы полмиллиона эпох (первоначальный алгоритм полмиллиона эпох преодолевал за 3-4 часа). Мои переживания по этому поводу прекратились, когда я запустил промежуточный тест через полчаса (около 1800 эпох) обучения. Сверточная сеть всего через 1800 эпох показывала результаты лучше, чем изначальный алгоритм после полумиллиона эпох. Но, став такой умной, змейка не только научилась жить значительно дольше, но и стала обходить мой алгоритм проверки движения по кругу. Умная змейка превзошла меня и свою младшую сестру. Теперь она двигалась по циклической, но абсолютно непредсказуемой траектории, иногда это был круг, иногда -- зигзагообрзные движения, но всегда -- новые. Стоит отметить, что я так и не придумал, как наказывать змейку за такие движения (увеличение награды за поедание приза не смогло стимулировать ее должным образом, а алоритма для выявления случайных циклических перемещений пока не создал). Таким образом, по результатам работы я имею несколько сохраненных бинарных файлов с весами моделей: файл модели, играющей в горную машинку, файл (или несколько) для модели, играющей в змейку и принимающей вектор состояния на вход и файл весов сверточной нейронной сети, также играющей в змейку.

Результаты работы

Все результаты можно с легкостью воспроизвести. Об этом будет ниже.

Все результаты (удачные и не очень) я старался записывать. Вот, например, одна из визуализаций игры модели с fc-слоями:

Видео сюда вставить нельзя, поэтому вот ссылка

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

Воспроизведение результатов

Чтобы посмотреть, как играет мой алгоритм, нужно клонировать этот репозиторий на локальное устройство с GPU и запустить файл test.py. Весь код подробно документирован, а комментарии объясняют неочевидные моменты. Но, несмотря на всю документацию, я бы советовал прочесть текстовое описание алгоритма, прежде чем смотреть код.

Список литературы, которой я обязан всеми своими знаниями

Отсортирован по вкладу литературы в развитие проекта.

• Замечательная серия статей Free Code Camp:

  Part 1: An introduction to Reinforcement Learning

  Part 2: Diving deeper into Reinforcement Learning with Q-Learning

  Part 3: An introduction to Deep Q-Learning: let’s play Doom

  Part 3+: Improvements in Deep Q Learning: Dueling Double DQN, Prioritized Experience Replay, and fixed Q-targets

  Part 4: An introduction to Policy Gradients with Doom and Cartpole

• Работа DeepMind Technologies:

  Playing Atari with Deep Reinforcement Learning

• Stack OverFlow, DataScience:

  Why is a target network required?

  Q-Learning: Target Network vs Double DQN

  How is the target_f updated in the Keras solution to the Deep Q-learning Cartpole/Gym algorithm?

• PyTorch Tutorials:

  REINFORCEMENT LEARNING (DQN) TUTORIAL

• Статьи на Хабре:

  Обучение с подкреплением на языке Python

  Mountain Car: решаем классическую задачу при помощи обучения с подкреплением

  Нейросеть — обучение без учителя. Метод Policy Gradient

  Deep Reinforcement Learning (или за что купили DeepMind)

  Глубокое обучение с подкреплением: пинг-понг по сырым пикселям