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

Вот, собственно, главный артефакт (если вы это видео не видели, посмотрите обязательно, оно взрывает мозг)


Вот столько примерно публично известно про компанию, когда ее покупают за полмиллиарда долларов.

Disclaimer: пост написан на основе изрядно отредактированных логов чата closedcircles.com, отсюда и стиль изложения, и наличие уточняющих вопросов.

Seminal paper, про то как это работает — https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

Итак, быстро и на пальцах про Q-learning

Пусть мы находимся в какой-то среде, у которой есть текущее состояние s, и мы в каждый момент можем выполнить действие a из дискретного набора. Это действие переводит систему в новое состояние (стохастически, т.е. в системе есть всякое случайное) и может выдать нам reward или закончить игру.

Вводится понятие cumulative return over time — это общее количество reward, которое мы можем получить от текущего момента до конца игры, причем будущие rewards уменьшаются на y за каждый тик времени, т.е. reward в следующий момент времени — это y*r, еще через один — y²*r

Так вот, оптимальное поведение можно описать некой функцией Q*(s,a), которая возвращает одно число.
Главное понять, что оно значит!

Значит оно следующее — если мы находимся в состоянии s, и предпринимаем действие a, какой у нас будет cumulative reward до конца игры, если мы после действия a будем действовать оптимальным образом?
Если такая функция дана свыше, с ее помощью легко играть оптимально — попробуем Q*(s,a) для всех a, выберем максимальный.

Всем понятно? Пойду чай поставлю.
Ну ладно, ваши проблемы.

Далее, есть ключевое рекуррентное уравнение для этой вот воображаемой Q* функции, так называемый Bellman Equation

Вот такой красивый.
Что он говорит!

Он говорит, что если мы знаем, с какими вероятностями s переходит в следующее состояние s` из-за действия a…
То Q* для текущего состояния s должно быть равно максимуму из выбора дальнейший действий на следующем шаге.

Ну, мол, если мы знаем будущее, то чтобы понять какой будет reward на текущем стейте при выполнении действия a, можно в это будущее заглянуть, посмотреть какие там действия оптимальны и таким образом сказать какой будет cumulative reward.

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

О, чай вскипел.

послушай, я значит чего вообще не понял — это как она после этого может играть во все игры Atari?
Она не играет во все игры сразу. Она тренирует Q-функцию для каждой игры.

Ну так вот. Идея собственно простая. Давайте представим эту Q-функцию как CNN! (в смысле, convolutional neural network)
Вот прям обычный такой, с пикселями на инпутах и с количеством нейронов в аутпуте равным количеству возможных действий. Более точно — на вход сети выдаются пиксели нескольких прошлых кадров эмулятора (в оригинальной реализации — 4-х кадров), то есть сеть может отследить движущиеся объекты.
На каждом нейроне последнего слоя сети — Q(s,a) для нужного a.

Как эту сеть натренировать?

Вот есть версия сети на текущем шаге, с некоторыми весами. Произошел новый шаг, мы узнали новый переход из s в s' в результате действия a и был ли reward.
Будем вот все такие туплы (s,s',a,r) сохранять, все какие мы видели за игру.

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

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

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

У самой нейросети памяти и стейта нет вообще, вся память системы — в натренированных весах. Если угодно, мышечная такая память.
(почему надо тренировать на случайном наборе из истории, а не на последних — чтобы не случалось positive feedback loop, т.е. чтобы система не приспосабливалась к последствиям конкретного недавнего выбора, а к данным в целом)

Маленькие детали — они еще используют так называемую e-greedy policy.
На каждом шаге с вероятностью e будет сделано тупо случайное действие, а с вероятностью (1-e) предсказанное текущим эстимейтом Q-функции.
От времени e, понятно, уменьшается.



Вот псевдокод алгоритма.
И все. Не делают больше ничего.

Только обучают CNN предсказывать Q-функцию по ходу дела. На массиве состояний, итеративно.

интересно, долго ли оно учится
Десятки и сотни часов

во, а ещё расскажи про experience replay (они там общими фразами обделались, а в коде все слишком просто).
Experience replay — это их название того, что нужно запоминать все переходы состояний, которые были за время работы и тренироваться на них всех.
Да, очень круто. Они я так понимаю не особо заморачивались выбором стратегии "забывания" (у них тупо по циклу "забывает" старое по факту перезаписи его).
Угу, сколько памяти хватает, столько и помнят.

по поводу препроцессинга — я правильно понимаю что пойнт упаковки четырех (трех) изображений в "фи" — тупо экономия вычислений, а не вовсе потуги как-то работать с локальной анимацией / направлением движения и т.п.?
Они дают на вход прошлые 4 кадра истории.
Мне кажется, это таки независимо от frame skipping для экономии ресурсов, так что это дает возможность сети посмотреть на анимацию, да.

кстати, во время Дипхака в одной команде парни сократили кол-во кадров до 3, без видимого ухудшения по результатам
Они в статье пишут, что везде было ок с 4 (и это лучше чем 3 для времени тренировки), кроме Space Invaders.
В них лазер стрелял раз в 4 кадра и поэтому становился невидимым с пропусками. Для них сделали 3.

вооот, и наконец тупой вопрос пока мы обсуждаем входные кадры и Главную Формулу с Гамма-Дисконтом Риворда
откуда они reward-то брали?
Из игры. Тупо scores. В изначальной версии просто смотрели на знак изменения scores.

"из игры" — это из эмулятора дополнительным хаком эмулятора?
Короткий ответ на вопрос и заодно на незаданные вопросы о кадрах на экране и как нажимать кнопки — используйте готовые библиотеки типа http://www.arcadelearningenvironment.org, иначе ваше исследование в области DQN быстро остановится.
Как хорошо что мы живем в ХХ1 веке! И риворды и end-of-game сигналы экстрактятся например этим самым ALE из более чем 50 атари игр.

Тут очень интересна связь с внешним миром, мне кажется. Чтобы этот весь deep reinforcement learning происходил — должно сойтись много всего. Прежде всего, должны быть игры.

Игры — главный двигатель прогресса (и видимо порно еще)

Так как есть игры, у нас есть очень мощные GPU.
Так как есть игры на Атари, есть мощное community про эмулятор и прочая инфраструктура.
Так как есть игры и люди в них играют, мы создали другие игры — прекрасные тренировочные программы, прекрасно варьирующейся степени сложности. Чем дальше, тем более реалистичные.
Не бережем себя.

Для людей, которым код нравится читать больше, чем пейперы, вот неплохая реализация — https://github.com/spragunr/deep_q_rl