Deep Reinforcement Learning: Pong from Pixels

Это давно назревший пост в блоге об обучении с подкреплением (Reinforcement Learning, RL). RL сейчас на пике популярности! Вы могли заметить, что компьютеры теперь умеют автоматически учиться играть в игры ATARI (по сырым пикселям!), они обыгрывают чемпионов мира в го, симулированные четвероногие учатся бегать и прыгать, а роботы осваивают сложные манипуляционные задачи, не поддающиеся явному программированию. Оказывается, все эти достижения относятся к области исследований RL. Я и сам заинтересовался RL за последний ~год: проработал книгу Richard Sutton, прошёл курс David Silver, посмотрел лекции John Schulmann, написал RL-библиотеку на JavaScript, летом стажировался в DeepMind в группе DeepRL, а недавно немного поучаствовал в проектировании/разработке OpenAI Gym — нового инструментария для бенчмаркинга RL. Так что я уже как минимум год катаюсь на этом весёлом поезде, но до сих пор не нашёл времени написать короткий пост о том, почему RL — это важно, в чём его суть, как всё это развивалось и куда движется.

Интересно поразмышлять о природе недавнего прогресса в RL. Мне в целом нравится выделять четыре отдельных фактора, сдерживающих развитие ИИ:

Вычислительные мощности (очевидный фактор: закон Мура, GPU, ASIC), данные (в удобной форме, а не просто где-то в интернете — например, ImageNet), алгоритмы (исследования и идеи, например backprop, CNN, LSTM) и инфраструктура (программное обеспечение под вами — Linux, TCP/IP, Git, ROS, PR2, AWS, AMT, TensorFlow и т. д.).

Как и в случае с компьютерным зрением, прогресс в RL не настолько обусловлен новыми удивительными идеями, как может разумно показаться. В компьютерном зрении AlexNet 2012 года был в основном масштабированной (более глубокой и широкой) версией ConvNets из 1990-х. Аналогично, статья 2013 года по Deep Q Learning для ATARI — это реализация стандартного алгоритма (Q Learning с аппроксимацией функции, который можно найти в стандартной книге по RL Sutton 1998), где аппроксиматор функции просто оказался ConvNet. AlphaGo использует policy gradients с Monte Carlo Tree Search (MCTS) — это тоже стандартные компоненты. Конечно, требуется много мастерства и терпения, чтобы это заработало, и поверх старых алгоритмов было разработано множество остроумных приёмов, но в первом приближении основной двигатель недавнего прогресса — не алгоритмы, а (как и в компьютерном зрении) вычисления/данные/инфраструктура.

Теперь вернёмся к RL. Каждый раз, когда есть разрыв между тем, насколько чем-то магическим что-то кажется, и тем, насколько просто оно устроено внутри, мне становится не по себе и очень хочется написать пост в блоге. В данном случае я видел много людей, которые не верят, что мы можем автоматически научиться играть в большинство игр ATARI на человеческом уровне, одним алгоритмом, по пикселям и с нуля — и это действительно поразительно, я сам через это прошёл! Но в основе используемый подход глубоко тупой (хотя я понимаю, что задним числом легко делать такие заявления). В любом случае, мне хотелось бы провести вас через Policy Gradients (PG) — наш любимый выбор по умолчанию для атаки на задачи RL на данный момент. Если вы не из RL, вам может быть интересно, почему я не представляю вместо этого DQN — альтернативный и более известный RL-алгоритм, широко популяризированный статьёй про игру в ATARI. Оказывается, Q-Learning — не очень хороший алгоритм (можно сказать, что DQN — это уже «прошлый век» (ладно, я наполовину шучу)). На самом деле большинство предпочитают использовать Policy Gradients, в том числе авторы оригинальной статьи о DQN, которые показали, что Policy Gradients при хорошей настройке работают лучше Q Learning. PG предпочтительнее, потому что он end-to-end: есть явная политика и принципиальный подход, который напрямую оптимизирует ожидаемую награду. В качестве сквозного примера мы будем учиться играть в игру ATARI (Pong!) с помощью PG, с нуля, по пикселям, с помощью глубокой нейронной сети, и всё это — 130 строк Python с единственной зависимостью numpy (ссылка на Gist). Приступим.

Pong по пикселям

Игра Pong — отличный пример простой задачи RL. В версии для ATARI 2600, которую мы будем использовать, вы играете одной из ракеток (другую контролирует приличный ИИ), и вам нужно отбить мяч так, чтобы он пролетел мимо другого игрока (мне ведь не нужно объяснять Pong, правда?). На низком уровне игра работает так: мы получаем кадр-изображение (массив байтов 210x160x3 (целые числа от 0 до 255, дающие значения пикселей)) и должны решить, хотим ли мы двигать ракетку ВВЕРХ или ВНИЗ (то есть бинарный выбор). После каждого выбора игровой симулятор выполняет действие и даёт нам награду: либо +1, если мяч пролетел мимо соперника, либо -1, если мы пропустили мяч, либо 0 в остальных случаях. И, конечно, наша цель — двигать ракетку так, чтобы получать побольше награды.

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

Policy network. Сначала мы определим policy network, реализующую нашего игрока (или «агента»). Эта сеть будет принимать состояние игры и решать, что нам следует делать (двигаться ВВЕРХ или ВНИЗ). В качестве нашего любимого простого вычислительного блока мы будем использовать 2-слойную нейронную сеть, которая принимает сырые пиксели изображения (всего 100 800 чисел (210*160*3)) и выдаёт одно число, обозначающее вероятность пойти ВВЕРХ. Обратите внимание, что стандартно используется стохастическая политика, то есть мы выдаём только вероятность движения ВВЕРХ. На каждой итерации мы будем сэмплировать из этого распределения (то есть бросать «нечестную» монетку), чтобы получить фактический ход. Причина этого станет яснее, когда мы поговорим об обучении.

Чтобы сделать это более конкретным, вот как можно реализовать эту policy network на Python/numpy. Допустим, нам дан вектор x, содержащий (предобработанную) информацию о пикселях. Мы вычислили бы:

h = np.dot(W1, x) # вычисляем активации нейронов скрытого слоя h[h<0] = 0 # нелинейность ReLU: пороговое значение в нуле logp = np.dot(W2, h) # вычисляем логарифм вероятности пойти вверх p = 1.0 / (1.0 + np.exp(-logp)) # сигмоидная функция (даёт вероятность пойти вверх)

где в этом фрагменте W1 и W2 — две матрицы, которые мы инициализируем случайно. Мы не используем смещения, потому что лень. Обратите внимание, что мы используем сигмоидную нелинейность в конце, которая сжимает выходную вероятность в диапазон [0,1]. Интуитивно, нейроны в скрытом слое (веса которых расположены по строкам W1) могут обнаруживать различные игровые сценарии (например, мяч находится сверху, а наша ракетка посередине), а веса в W2 затем могут решать, должны ли мы в каждом случае двигаться ВВЕРХ или ВНИЗ. Конечно, изначальные случайные W1 и W2 заставят игрока дёргаться на месте. Так что единственная проблема теперь — найти такие W1 и W2, которые приведут к экспертной игре в Pong!

Мелким шрифтом: предобработка. В идеале вы хотели бы подавать в policy network как минимум 2 кадра, чтобы она могла обнаруживать движение. Чтобы немного упростить (я делал эти эксперименты на своём Macbook), я сделаю крошечную предобработку, например, мы будем подавать сети разностные кадры (то есть разность текущего и предыдущего кадра).

Звучит вроде как невозможно. На этом этапе я хотел бы, чтобы вы оценили, насколько сложна задача RL. Мы получаем 100 800 чисел (210*160*3) и пропускаем их через нашу policy network (которая легко включает порядка миллиона параметров в W1 и W2). Допустим, мы решили пойти ВВЕРХ. Игра может ответить, что на этом временном шаге мы получаем 0 награды, и даст нам ещё 100 800 чисел для следующего кадра. Мы можем повторять этот процесс в течение сотен временных шагов, прежде чем получим хоть какую-то ненулевую награду! Например, предположим, что мы наконец получили +1. Это здорово, но как мы можем понять, что именно к этому привело? Что-то, что мы сделали только что? Или, может быть, 76 кадров назад? Или, может быть, это как-то связано с кадром 10, а затем с кадром 90? И как нам понять, какие из миллиона рычажков и как нужно повернуть, чтобы в будущем поступать лучше? Мы называем это проблемой назначения заслуг (credit assignment problem). В конкретном случае с Pong мы знаем, что получаем +1, если мяч пролетает мимо соперника. Истинная причина в том, что нам случилось отбить мяч по хорошей траектории, но на самом деле мы сделали это много кадров назад — например, около 20 в случае Pong, и каждое отдельное действие, которое мы предприняли после, не имело никакого эффекта на то, получим ли мы награду. Иными словами, мы столкнулись с очень сложной задачей, и ситуация выглядит довольно мрачно.

Обучение с учителем. Прежде чем мы погрузимся в решение Policy Gradients, я хотел бы кратко напомнить об обучении с учителем (supervised learning), потому что, как мы увидим, RL очень похоже на него. Обратитесь к диаграмме ниже. В обычном обучении с учителем мы подаём изображение в сеть и получаем некоторые вероятности, например, для двух классов ВВЕРХ и ВНИЗ. Я показываю логарифмы вероятностей (-1.2, -0.36) для ВВЕРХ и ВНИЗ вместо сырых вероятностей (30% и 70% в данном случае), потому что мы всегда оптимизируем логарифм вероятности правильной метки (так математика приятнее, и это эквивалентно оптимизации сырой вероятности, потому что логарифм монотонен). В обучении с учителем у нас есть доступ к метке. Например, нам могут сказать, что правильное действие сейчас — идти ВВЕРХ (метка 0). В реализации мы бы ввели градиент 1.0 на логарифм вероятности ВВЕРХ и запустили backprop, чтобы вычислить вектор градиента \(\nabla_{W} \log p(y=UP \mid x) \). Этот градиент сказал бы нам, как нужно изменить каждый из нашего миллиона параметров, чтобы сеть стала чуть более склонной предсказывать ВВЕРХ. Например, один из миллиона параметров в сети может иметь градиент -2.1, что означает, что если бы мы увеличили этот параметр на небольшую положительную величину (например, 0.001), логарифм вероятности ВВЕРХ уменьшился бы на 2.1 * 0.001 (уменьшится из-за отрицательного знака). Если бы затем мы сделали обновление параметров, ура, наша сеть теперь была бы немного более склонна предсказывать ВВЕРХ, увидев очень похожее изображение в будущем.

Policy Gradients. Хорошо, но что нам делать, если у нас нет правильной метки в задаче RL? Вот решение Policy Gradients (снова обратитесь к диаграмме ниже). Наша policy network вычислила вероятность пойти ВВЕРХ как 30% (logprob -1.2) и ВНИЗ как 70% (logprob -0.36). Теперь мы будем сэмплировать действие из этого распределения; например, предположим, что мы сэмплировали ВНИЗ и выполним это действие в игре. На этом этапе обратите внимание на один интересный факт: мы могли бы немедленно ввести градиент 1.0 для ВНИЗ, как мы делали в обучении с учителем, и найти вектор градиента, который побудил бы сеть быть чуть более склонной выполнять действие ВНИЗ в будущем. Так что мы можем сразу же вычислить этот градиент, и это здорово, но проблема в том, что мы пока ещё не знаем, хорошо ли идти ВНИЗ. Но критический момент в том, что это нормально, потому что мы можем просто немного подождать и посмотреть! Например, в Pong мы могли бы подождать до конца игры, затем взять награду, которую мы получаем (+1, если выиграли, или -1, если проиграли), и ввести этот скаляр в качестве градиента для предпринятого действия (ВНИЗ в данном случае). В приведённом ниже примере поход ВНИЗ привёл к нашему проигрышу в игре (награда -1). Так что если мы введём -1 для логарифма вероятности ВНИЗ и сделаем backprop, мы найдём градиент, который отбивает у сети желание выполнять действие ВНИЗ для этого входа в будущем (и совершенно справедливо, поскольку это действие привело нас к проигрышу в игре).

И это всё: у нас есть стохастическая политика, которая сэмплирует действия, а затем действия, которые в итоге приводят к хорошим результатам, поощряются в будущем, а действия, приводящие к плохим результатам, наказываются. Кроме того, награда даже не обязана быть +1 или -1, если мы в итоге выигрываем игру. Это может быть произвольная мера некоего итогового качества. Например, если всё сложилось действительно хорошо, она может быть равна 10.0, что мы тогда вводили бы как градиент вместо -1 для запуска backprop. В этом красота нейросетей: их использование может казаться жульничеством — у вас может быть 1 миллион параметров, заключённых в 1 терафлопс вычислений, и вы можете заставить их делать произвольные вещи с помощью SGD. Это не должно работать, но забавно, что мы живём во вселенной, где это работает.

Протокол обучения. Итак, вот как обучение будет работать в деталях. Мы инициализируем policy network некоторыми W1, W2 и сыграем 100 игр в Pong (мы называем это «прокатами» (rollouts) политики). Допустим, что каждая игра состоит из 200 кадров, так что в общей сложности мы приняли 20 000 решений идти ВВЕРХ или ВНИЗ, и для каждого из них мы знаем градиент параметров, который говорит нам, как мы должны изменить параметры, если бы хотели поощрить это решение в этом состоянии в будущем. Теперь остаётся лишь пометить каждое принятое решение как хорошее или плохое. Например, предположим, что мы выиграли 12 игр и проиграли 88. Мы возьмём все 200*12 = 2400 решений, принятых в выигранных играх, и сделаем положительное обновление (введя +1.0 в градиент для сэмплированного действия, выполнив backprop и обновление параметров, поощряющее действия, которые мы выбрали во всех этих состояниях). А мы возьмём остальные 200*88 = 17 600 решений, принятых в проигранных играх, и сделаем отрицательное обновление (отбивая желание делать то, что мы делали). И… вот и всё. Теперь сеть станет немного более склонной повторять действия, которые сработали, и немного менее склонной повторять действия, которые не сработали. Теперь мы играем ещё 100 игр с нашей новой, слегка улучшенной политикой и повторяем.

Policy Gradients: запустите политику на какое-то время. Посмотрите, какие действия привели к высоким наградам. Увеличьте их вероятность.

Если вы продумаете этот процесс, вы начнёте находить несколько забавных свойств. Например, что если мы сделали хорошее действие в кадре 50 (правильно отбили мяч), но затем пропустили мяч в кадре 150? Если каждое отдельное действие теперь помечено как плохое (потому что мы проиграли), не будет ли это отбивать желание делать правильный отбой в кадре 50? Вы правы — будет. Однако, если рассмотреть процесс на протяжении тысяч/миллионов игр, то правильный первый отбой делает вас немного более склонным выиграть впоследствии, так что в среднем для правильного отбоя вы увидите больше положительных обновлений, чем отрицательных, и ваша политика в итоге будет делать правильные вещи.

Обновление: 9 декабря 2016 года — альтернативный взгляд. В моём объяснении выше я использую такие термины, как «введите градиент и сделайте backprop», что, как я понимаю, представляет собой особый тип мышления, если вы привыкли писать собственный код backprop или использовать Torch, где градиенты явные и открытые для манипуляций. Однако, если вы привыкли к Theano или TensorFlow, вы можете немного озадачиться, потому что код организован вокруг указания функции потерь, а backprop полностью автоматический и его трудно настраивать. В этом случае следующий альтернативный взгляд может оказаться более интуитивным. В обычном обучении с учителем цель — максимизировать \( \sum_i \log p(y_i \mid x_i) \), где \(x_i, y_i \) — обучающие примеры (например, изображения и их метки). Policy gradients — это в точности то же самое, что и обучение с учителем, с двумя небольшими отличиями: 1) у нас нет правильных меток \(y_i\), поэтому в качестве «фейковой метки» мы подставляем действие, которое случилось так, что мы сэмплировали из политики, когда она увидела \(x_i\), и 2) мы мультипликативно модулируем потери для каждого примера на основе итогового результата, поскольку мы хотим увеличить логарифм вероятности для действий, которые сработали, и уменьшить его для тех, которые не сработали. Так что в итоге наша функция потерь теперь выглядит как \( \sum_i A_i \log p(y_i \mid x_i) \), где \(y_i\) — действие, которое мы сэмплировали, а \(A_i\) — число, которое мы называем преимуществом (advantage). В случае Pong, например, \(A_i\) может быть 1.0, если мы в итоге выиграли в эпизоде, содержавшем \(x_i\), и -1.0, если проиграли. Это гарантирует, что мы максимизируем логарифм вероятности действий, приведших к хорошему результату, и минимизируем логарифм вероятности тех, что не привели. Так что обучение с подкреплением — это в точности как обучение с учителем, но на непрерывно меняющемся наборе данных (эпизодах), масштабированном на advantage, и мы хотим сделать только одно (или очень мало) обновлений на основе каждого сэмплированного набора данных.

Более общие функции advantage. Я также обещал немного больше обсуждения возвратов (returns). До сих пор мы оценивали хорошесть каждого отдельного действия по тому, выиграли мы игру или нет. В более общей постановке RL мы получали бы некоторую награду \(r_t\) на каждом временном шаге. Один распространённый выбор — использовать дисконтированную награду (discounted reward), так что «итоговая награда» на диаграмме выше станет \( R_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k} \), где \(\gamma\) — число между 0 и 1, называемое коэффициентом дисконтирования (например, 0.99). Выражение утверждает, что сила, с которой мы поощряем сэмплированное действие, — это взвешенная сумма всех последующих наград, причём более поздние награды экспоненциально менее важны. На практике также может быть важно нормализовать их. Например, предположим, что мы вычислили \(R_t\) для всех 20 000 действий в пакете из 100 прокатов игры в Pong выше. Хорошая идея — «стандартизировать» эти возвраты (например, вычесть среднее, поделить на стандартное отклонение), прежде чем подставлять их в backprop. Так мы всегда поощряем и наказываем примерно половину выполненных действий. Математически эти трюки можно также интерпретировать как способ контролировать дисперсию оценщика градиента политики. Более глубокое исследование можно найти здесь.

Вывод Policy Gradients. Я также хотел бы дать набросок того, откуда математически берутся Policy Gradients. Policy Gradients — это частный случай более общего оценщика градиента score-функции (score function gradient estimator). Общий случай — это когда у нас есть выражение вида \(E_{x \sim p(x \mid \theta)} [f(x)] \), то есть математическое ожидание некоторой скалярнозначной score-функции \(f(x)\) при некотором распределении вероятностей \(p(x;\theta)\), параметризованном некоторым \(\theta\). Подсказка: \(f(x)\) станет нашей функцией награды (или функцией advantage в более общем случае), а \(p(x)\) будет нашей policy network, которая на самом деле является моделью для \(p(a \mid I)\), дающей распределение над действиями для любого изображения \(I\). Тогда нам интересно узнать, как мы должны сдвигать распределение (через его параметры \(\theta\)), чтобы увеличить оценки его сэмплов, по мнению \(f\) (то есть как изменить параметры сети так, чтобы сэмплы действий получали более высокие награды). У нас есть:

Если выразить это словами: у нас есть некоторое распределение \(p(x;\theta)\) (я использовал сокращение \(p(x)\), чтобы уменьшить захламлённость), из которого мы можем сэмплировать (например, это может быть гауссиан). Для каждого сэмпла мы также можем вычислить score-функцию \(f\), которая берёт сэмпл и даёт нам некоторую скалярную оценку. Это уравнение говорит нам, как мы должны сдвинуть распределение (через его параметры \(\theta\)), если бы хотели, чтобы его сэмплы получали более высокие оценки, по мнению \(f\). В частности, оно говорит: смотрите, сэмплируйте несколько \(x\), вычислите их оценки \(f(x)\), и для каждого \(x\) также вычислите второй член \( \nabla_{\theta} \log p(x;\theta) \). Что это за второй член? Это вектор — градиент, дающий нам направление в пространстве параметров, которое привело бы к увеличению вероятности, присвоенной \(x\). Иначе говоря, если бы мы подтолкнули \(\theta\) в направлении \( \nabla_{\theta} \log p(x;\theta) \), мы увидели бы, что новая вероятность, присвоенная некоторому \(x\), слегка увеличилась. Если вы посмотрите на формулу, она говорит нам, что нужно взять это направление и умножить его на скалярнозначную оценку \(f(x)\). Это приведёт к тому, что сэмплы с более высокой оценкой будут «тянуть» плотность вероятности сильнее, чем сэмплы с более низкой оценкой, так что если бы мы сделали обновление на основе нескольких сэмплов из \(p\), плотность вероятности сдвигалась бы в сторону более высоких оценок, делая высокооценённые сэмплы более вероятными.

Надеюсь, связь с RL ясна. Наша policy network даёт нам сэмплы действий, и некоторые из них работают лучше других (по мнению функции advantage). Эта маленькая математическая выкладка говорит нам, что способ изменить параметры политики — сделать несколько прокатов, взять градиент сэмплированных действий, умножить его на оценку и всё сложить, что мы и сделали выше. Для более тщательного вывода и обсуждения я рекомендую лекцию John Schulman.

Обучение. Итак, мы разработали интуитивное понимание policy gradients и увидели набросок их вывода. Я реализовал весь подход в скрипте на Python в 130 строк, который использует ATARI 2600 Pong из OpenAI Gym. Я обучил 2-слойную policy network с 200 единицами скрытого слоя, используя RMSProp на пакетах по 10 эпизодов (каждый эпизод — это несколько десятков игр, потому что игры идут до счёта 21 для любого игрока). Я не слишком подкручивал гиперпараметры и запустил эксперимент на своём (медленном) Macbook, но после обучения в течение 3 ночей я получил политику, которая чуть лучше ИИ-игрока. Общее количество эпизодов составило примерно 8000, так что алгоритм сыграл примерно 200 000 игр Pong (немало, не правда ли!) и сделал около ~800 обновлений. Друзья говорят мне, что если обучать на GPU с ConvNets в течение нескольких дней, можно побеждать ИИ-игрока чаще, а если ещё и тщательно оптимизировать гиперпараметры, можно стабильно доминировать над ИИ-игроком (то есть выигрывать каждую игру). Однако я не тратил слишком много времени на вычисления или подкрутку, поэтому мы в итоге получаем Pong-ИИ, который иллюстрирует основные идеи и работает довольно хорошо:

Выученные веса. Мы также можем посмотреть на выученные веса. Из-за предобработки каждый из наших входов — это разностное изображение 80x80 (текущий кадр минус предыдущий). Теперь мы можем взять каждую строку W1, растянуть её до 80x80 и визуализировать. Ниже представлена коллекция из 40 (из 200) нейронов в сетке. Белые пиксели — это положительные веса, а чёрные — отрицательные. Обратите внимание, что несколько нейронов настроены на определённые траектории отскакивающего мяча, закодированные чередующимися чёрным и белым вдоль линии. Мяч может находиться только в одном месте, так что эти нейроны мультизадачные и будут «срабатывать» для нескольких положений мяча вдоль этой линии. Чередование чёрного и белого интересно, потому что по мере того, как мяч движется по траектории, активность нейрона будет колебаться как синусоида, и из-за ReLU он будет «срабатывать» в дискретных, разделённых положениях вдоль траектории. На изображениях немного шума, который, я полагаю, был бы смягчён, если бы я использовал L2-регуляризацию.

Чего здесь не происходит

Итак, вот вам результат — мы научились играть в Pong по сырым пикселям с помощью Policy Gradients, и это работает довольно хорошо. Подход — это причудливая форма «угадай и проверь», где «угадай» означает сэмплирование прокатов из нашей текущей политики, а «проверь» — поощрение действий, ведущих к хорошим результатам. С точностью до некоторых деталей, это представляет собой текущий уровень развития в подходе к задачам обучения с подкреплением. Впечатляет, что мы можем выучить такое поведение, но если вы интуитивно поняли алгоритм и знаете, как он работает, вы должны быть как минимум немного разочарованы. В частности, как он НЕ работает?

Сравните это с тем, как человек мог бы научиться играть в Pong. Вы показываете ему игру и говорите что-то вроде «Ты управляешь ракеткой и можешь двигать её вверх и вниз, твоя задача — отбить мяч мимо другого игрока, управляемого ИИ», и всё, можно начинать. Обратите внимание на некоторые различия:

На практике мы обычно передаём задачу каким-то образом (например, по-английски, как выше), но в стандартной задаче RL вы предполагаете произвольную функцию награды, которую нужно открыть через взаимодействие со средой. Можно утверждать, что если бы человек попал в игру в Pong, ничего не зная о функции награды (особенно если функция награды — это некоторая статичная, но случайная функция), у человека были бы большие трудности с обучением тому, что нужно делать, а Policy Gradients были бы безразличны и, вероятно, работали бы намного лучше. Аналогично, если бы мы взяли кадры и случайно перемешали пиксели, люди, скорее всего, провалились бы, но наше решение на Policy Gradient даже не смогло бы заметить разницы (если оно использует полносвязную сеть, как здесь). Человек привносит огромный объём предварительных знаний, таких как интуитивная физика (мяч отскакивает, маловероятно, что он телепортируется, маловероятно, что он внезапно остановится, он сохраняет постоянную скорость и т. д.) и интуитивная психология (ИИ-противник «хочет» выиграть, вероятно, следует очевидной стратегии движения к мячу и т. д.). Вы также понимаете концепцию того, что вы «управляете» ракеткой и что она реагирует на ваши команды клавиш ВВЕРХ/ВНИЗ. Напротив, наши алгоритмы начинают с нуля, что одновременно впечатляет (потому что это работает) и удручает (потому что у нас нет конкретных идей, как избежать этого). Policy Gradients — это решение методом грубой силы, где правильные действия в конечном итоге обнаруживаются и интернализуются в политику. Люди строят богатую, абстрактную модель и планируют внутри неё. В Pong я могу рассуждать, что противник довольно медленный, поэтому может быть хорошей стратегией отбивать мяч с высокой вертикальной скоростью, что заставит противника не успеть его поймать. Однако также кажется, что мы в итоге «интернализуем» хорошие решения в нечто, что больше напоминает реактивную политику мышечной памяти. Например, если вы учитесь новой моторной задаче (например, водить машину с ручной коробкой?), вы часто чувствуете, что в начале много думаете, но в конце концов задача становится автоматической и бездумной. Policy Gradients должны фактически испытать положительную награду, и испытать её очень часто, чтобы в конечном итоге медленно сдвинуть параметры политики в сторону повторения движений, дающих высокие награды. С нашей абстрактной моделью люди могут понять, что, скорее всего, даст награду, даже фактически не испытав вознаграждающего или невознаграждающего перехода. Мне не нужно фактически разбить свою машину о стену несколько сотен раз, прежде чем я медленно начну этого избегать.

Я хотел бы также подчеркнуть, что, наоборот, есть много игр, в которых Policy Gradients довольно легко победили бы человека. В частности, всё, что имеет частые сигналы награды, требует точной игры, быстрых рефлексов и не слишком много долгосрочного планирования, было бы идеальным, поскольку эти краткосрочные корреляции между наградами и действиями могут быть легко «замечены» подходом, а исполнение тщательно отточено политикой. Вы можете видеть намёки на это уже происходящие в нашем агенте Pong: он вырабатывает стратегию, в которой ждёт мяч, а затем быстро бросается, чтобы поймать его прямо у края, что запускает его быстро и с высокой вертикальной скоростью. Агент набирает несколько очков подряд, повторяя эту стратегию. Есть много игр ATARI, где Deep Q Learning разгромно превосходит человеческие показатели в подобном духе — например, Pinball, Breakout и т. д.

В заключение, как только вы поймёте «трюк», благодаря которому работают эти алгоритмы, вы можете рассуждать об их сильных и слабых сторонах. В частности, мы и близко не подошли к людям в построении абстрактных, богатых представлений игр, внутри которых мы можем планировать и использовать для быстрого обучения. Однажды компьютер посмотрит на массив пикселей и заметит ключ, дверь и подумает, что, вероятно, хорошая идея — поднять ключ и добраться до двери. Сейчас нет ничего и близкого к этому, и попытки добраться туда — активная область исследований.

Недифференцируемые вычисления в нейронных сетях

Я хотел бы упомянуть ещё одно интересное применение Policy Gradients, не связанное с играми: они позволяют нам проектировать и обучать нейронные сети с компонентами, которые выполняют (или взаимодействуют с) недифференцируемые вычисления. Идея была впервые представлена в Williams 1992 и недавно популяризирована в Recurrent Models of Visual Attention под названием «hard attention», в контексте модели, которая обрабатывала изображение последовательностью низкоразрешённых фовеальных взглядов (вдохновлённых нашими собственными человеческими глазами). В частности, на каждой итерации RNN получала бы небольшой фрагмент изображения и сэмплировала бы позицию, куда смотреть дальше. Например, RNN могла бы посмотреть на позицию (5,30), получить небольшой фрагмент изображения, затем решить посмотреть на (24, 50) и т. д. Проблема с этой идеей в том, что есть часть сети, которая выдаёт распределение того, куда смотреть дальше, а затем сэмплирует из него. К сожалению, эта операция недифференцируема, потому что, интуитивно, мы не знаем, что произошло бы, если бы мы сэмплировали другое местоположение. В более общем смысле, рассмотрим нейронную сеть от некоторых входов к выходам:

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

Policy gradients спешат на помощь! Мы будем думать о части сети, которая выполняет сэмплирование, как о маленькой стохастической политике, встроенной в более широкую сеть. Поэтому во время обучения мы будем производить несколько сэмплов (обозначенных ветвями ниже), а затем поощрять сэмплы, которые в итоге привели к хорошим результатам (в данном случае измеряемым, например, потерями в конце). Иными словами, мы будем обучать параметры, связанные с синими стрелками, с помощью backprop как обычно, но параметры, связанные с красной стрелкой, теперь будут обновляться независимо от обратного прохода с помощью policy gradients, поощряя сэмплы, приведшие к низким потерям. Эта идея также была недавно красиво формализована в Gradient Estimation Using Stochastic Computation Graphs.

Обучаемый ввод/вывод памяти. Вы также найдёте эту идею во многих других статьях. Например, Neural Turing Machine имеет ленту памяти, из которой они читают и в которую пишут. Чтобы выполнить операцию записи, хотелось бы выполнить что-то вроде m[i] = x, где i и x предсказываются управляющей сетью RNN. Однако эта операция недифференцируема, потому что нет сигнала, который бы говорил нам, что произошло бы с потерями, если бы мы записали в другое местоположение j != i. Поэтому NTM должен выполнять мягкие операции чтения и записи. Он предсказывает распределение внимания a (с элементами от 0 до 1, суммирующимися к 1 и пиковыми вокруг индекса, в который мы хотели бы записать), а затем выполняет for all i: m[i] = a[i]*x. Теперь это дифференцируемо, но мы должны платить большую вычислительную цену, потому что приходится трогать каждую ячейку памяти, чтобы записать в одну позицию. Представьте, если бы каждое присваивание в наших компьютерах должно было трогать всю RAM!

Однако мы можем использовать policy gradients, чтобы обойти эту проблему (в теории), как сделано в RL-NTM. Мы по-прежнему предсказываем распределение внимания a, но вместо мягкой записи мы сэмплируем местоположения для записи: i = sample(a); m[i] = x. Во время обучения мы делали бы это для небольшого пакета i и в итоге делали бы более вероятной ту ветвь, которая сработала лучше всего. Большое вычислительное преимущество в том, что теперь нам нужно читать/писать только в одно местоположение во время тестирования. Однако, как указано в статье, эту стратегию очень трудно заставить работать, потому что приходится случайно наткнуться на работающие алгоритмы через сэмплирование. Нынешний консенсус таков, что PG хорошо работает только в условиях, где есть несколько дискретных вариантов, чтобы не пришлось безнадёжно сэмплировать через огромные пространства поиска.

Однако с Policy Gradients и в случаях, когда доступно много данных/вычислений, мы в принципе можем мечтать масштабно — например, мы можем проектировать нейронные сети, которые учатся взаимодействовать с большими, недифференцируемыми модулями, такими как компиляторы LaTeX (например, если вы хотите, чтобы char-rnn генерировала LaTeX, который компилируется), или системой SLAM, или решателями LQR, или чем-то ещё. Или, например, сверхинтеллект мог бы захотеть научиться взаимодействовать с интернетом по TCP/IP (который, к сожалению, недифференцируем), чтобы получить доступ к жизненно важной информации, необходимой для захвата мира. Это отличный пример.

Заключение

Мы увидели, что Policy Gradients — это мощный, общий алгоритм, и в качестве примера мы обучили агента ATARI Pong по сырым пикселям, с нуля, в 130 строках Python. В более общем плане тот же алгоритм можно использовать для обучения агентов для произвольных игр и однажды, надеюсь, для многих ценных реальных задач управления. Я хотел бы добавить ещё несколько заметок в завершение:

О продвижении ИИ. Мы увидели, что алгоритм работает через поиск методом грубой силы, где вы сначала случайно дёргаетесь и должны случайно наткнуться на вознаграждающие ситуации хотя бы один раз, а в идеале часто и многократно, прежде чем распределение политики сдвинет свои параметры, чтобы повторять ответственные действия. Мы также видели, что люди подходят к этим задачам совсем иначе, в стиле, который больше похож на быстрое построение абстрактной модели — то, поверхность чего мы едва ли коснулись в исследованиях (хотя многие пытаются). Поскольку эти абстрактные модели очень трудно (если не невозможно) явно аннотировать, именно поэтому в последнее время такой большой интерес к (неконтролируемым) генеративным моделям и индукции программ.

Об использовании в сложных робототехнических постановках. Алгоритм наивно не масштабируется на условия, где трудно получить огромные объёмы исследования. Например, в робототехнических условиях у одного может быть единственный (или несколько) роботов, взаимодействующих с миром в реальном времени. Это запрещает наивные применения алгоритма в том виде, как я представил его в этом посте. Одно связанное направление работы, призванное смягчить эту проблему, — детерминированные градиенты политики (deterministic policy gradients) — вместо того, чтобы требовать сэмплов из стохастической политики и поощрять те, что получают более высокие оценки, подход использует детерминированную политику и получает информацию о градиенте напрямую из второй сети (называемой critic), которая моделирует score-функцию. Этот подход в принципе может быть гораздо более эффективным в условиях с очень высокоразмерными действиями, где сэмплирование действий обеспечивает плохое покрытие, но пока эмпирически кажется немного капризным в работе. Другой родственный подход — масштабировать робототехнику, как мы начинаем видеть с фермой роботизированных рук Google или, возможно, даже с Tesla Model S + Autopilot.

Существует также направление работы, которое пытается сделать процесс поиска менее безнадёжным, добавляя дополнительный контроль. Во многих практических случаях, например, можно получить экспертные траектории от человека. Например, AlphaGo сначала использует обучение с учителем для предсказания ходов человека из экспертных партий го, а получившаяся политика, имитирующая человека, позднее дообучается с помощью policy gradients на «реальной» цели — выиграть партию. В некоторых случаях у одного может быть меньше экспертных траекторий (например, из телеуправления роботом), и существуют техники, использующие эти данные, под зонтиком обучения подмастерья (apprenticeship learning). Наконец, если люди не предоставляют контролируемых данных, в некоторых случаях их также можно вычислить с помощью дорогостоящих техник оптимизации, например, с помощью оптимизации траектории в известной модели динамики (например, \(F=ma\) в физическом симуляторе) или в случаях, когда обучается приближенная локальная модель динамики (как видно в очень многообещающем фреймворке Guided Policy Search).

Об использовании PG на практике. В качестве последнего замечания, я хотел бы сделать то, чего не сделал в своём посте про RNN. Думаю, я мог создать впечатление, что RNN — это магия и они автоматически решают произвольные последовательные задачи. Правда в том, что заставить эти модели работать может быть непросто, требует осторожности и опыта, а во многих случаях может даже оказаться чрезмерным — где более простые методы могут провести вас на 90%+ пути. То же самое касается Policy Gradients. Они не автоматические: нужно много сэмплов, обучение длится вечно, и трудно отлаживать, когда не работает. Всегда следует пробовать пневматическую винтовку, прежде чем браться за базуку. В случае обучения с подкреплением, например, одна сильная базовая линия, которую всегда следует попробовать первой, — это метод кросс-энтропии (CEM), простой стохастический подход «угадай и проверь» восхождения на холм, вдохновлённый эволюцией. И если вы настаиваете на том, чтобы попробовать Policy Gradients для своей задачи, обязательно обратите пристальное внимание на раздел tricks в статьях, начните с простого и используйте вариацию PG под названием TRPO, который почти всегда работает лучше и более стабильно, чем ванильный PG на практике. Основная идея — избегать обновлений параметров, которые слишком сильно меняют вашу политику, что обеспечивается ограничением на KL-дивергенцию между распределениями, предсказанными старой и новой политикой на пакете данных (вместо сопряжённых градиентов простейшую реализацию этой идеи можно сделать через линейный поиск с проверкой KL по пути).

И это всё! Надеюсь, я дал вам представление о том, где мы находимся с обучением с подкреплением, в чём заключаются вызовы, и если вы горите желанием помочь продвинуть RL, я приглашаю вас сделать это в нашем OpenAI Gym :) До следующего раза!