Deep Reinforcement Learning: Pong from Pixels

This is a long overdue blog post on Reinforcement Learning (RL). RL is hot! You may have noticed that computers can now automatically learn to play ATARI games (from raw game pixels!), they are beating world champions at Go, simulated quadrupeds are learning to run and leap, and robots are learning how to perform complex manipulation tasks that defy explicit programming. It turns out that all of these advances fall under the umbrella of RL research. I also became interested in RL myself over the last ~year: I worked through Richard Sutton’s book, read through David Silver’s course, watched John Schulmann’s lectures, wrote an RL library in Javascript, over the summer interned at DeepMind working in the DeepRL group, and most recently pitched in a little with the design/development of OpenAI Gym, a new RL benchmarking toolkit. So I’ve certainly been on this funwagon for at least a year but until now I haven’t gotten around to writing up a short post on why RL is a big deal, what it’s about, how it all developed and where it might be going.

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

It’s interesting to reflect on the nature of recent progress in RL. I broadly like to think about four separate factors that hold back AI:

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

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

Similar to what happened in Computer Vision, the progress in RL is not driven as much as you might reasonably assume by new amazing ideas. In Computer Vision, the 2012 AlexNet was mostly a scaled up (deeper and wider) version of 1990’s ConvNets. Similarly, the ATARI Deep Q Learning paper from 2013 is an implementation of a standard algorithm (Q Learning with function approximation, which you can find in the standard RL book of Sutton 1998), where the function approximator happened to be a ConvNet. AlphaGo uses policy gradients with Monte Carlo Tree Search (MCTS) - these are also standard components. Of course, it takes a lot of skill and patience to get it to work, and multiple clever tweaks on top of old algorithms have been developed, but to a first-order approximation the main driver of recent progress is not the algorithms but (similar to Computer Vision) compute/data/infrastructure.

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

Now back to RL. Whenever there is a disconnect between how magical something seems and how simple it is under the hood I get all antsy and really want to write a blog post. In this case I’ve seen many people who can’t believe that we can automatically learn to play most ATARI games at human level, with one algorithm, from pixels, and from scratch - and it is amazing, and I’ve been there myself! But at the core the approach we use is also really quite profoundly dumb (though I understand it’s easy to make such claims in retrospect). Anyway, I’d like to walk you through Policy Gradients (PG), our favorite default choice for attacking RL problems at the moment. If you’re from outside of RL you might be curious why I’m not presenting DQN instead, which is an alternative and better-known RL algorithm, widely popularized by the ATARI game playing paper. It turns out that Q-Learning is not a great algorithm (you could say that DQN is so 2013 (okay I’m 50% joking)). In fact most people prefer to use Policy Gradients, including the authors of the original DQN paper who have shown Policy Gradients to work better than Q Learning when tuned well. PG is preferred because it is end-to-end: there’s an explicit policy and a principled approach that directly optimizes the expected reward. Anyway, as a running example we’ll learn to play an ATARI game (Pong!) with PG, from scratch, from pixels, with a deep neural network, and the whole thing is 130 lines of Python only using numpy as a dependency (Gist link). Lets get to it.

Теперь вернёмся к 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 from pixels

Pong по пикселям

The game of Pong is an excellent example of a simple RL task. In the ATARI 2600 version we’ll use you play as one of the paddles (the other is controlled by a decent AI) and you have to bounce the ball past the other player (I don’t really have to explain Pong, right?). On the low level the game works as follows: we receive an image frame (a 210x160x3 byte array (integers from 0 to 255 giving pixel values)) and we get to decide if we want to move the paddle UP or DOWN (i.e. a binary choice). After every single choice the game simulator executes the action and gives us a reward: Either a +1 reward if the ball went past the opponent, a -1 reward if we missed the ball, or 0 otherwise. And of course, our goal is to move the paddle so that we get lots of reward.

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

As we go through the solution keep in mind that we’ll try to make very few assumptions about Pong because we secretly don’t really care about Pong; We care about complex, high-dimensional problems like robot manipulation, assembly and navigation. Pong is just a fun toy test case, something we play with while we figure out how to write very general AI systems that can one day do arbitrary useful tasks.

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

Policy network. First, we’re going to define a policy network that implements our player (or “agent”). This network will take the state of the game and decide what we should do (move UP or DOWN). As our favorite simple block of compute we’ll use a 2-layer neural network that takes the raw image pixels (100,800 numbers total (210*160*3)), and produces a single number indicating the probability of going UP. Note that it is standard to use a stochastic policy, meaning that we only produce a probability of moving UP. Every iteration we will sample from this distribution (i.e. toss a biased coin) to get the actual move. The reason for this will become more clear once we talk about training.

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

and to make things concrete here is how you might implement this policy network in Python/numpy. Suppose we’re given a vector x that holds the (preprocessed) pixel information. We would compute:

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

h = np.dot(W1, x) # compute hidden layer neuron activations h[h<0] = 0 # ReLU nonlinearity: threshold at zero logp = np.dot(W2, h) # compute log probability of going up p = 1.0 / (1.0 + np.exp(-logp)) # sigmoid function (gives probability of going up)

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

where in this snippet W1 and W2 are two matrices that we initialize randomly. We’re not using biases because meh. Notice that we use the sigmoid non-linearity at the end, which squashes the output probability to the range [0,1]. Intuitively, the neurons in the hidden layer (which have their weights arranged along the rows of W1) can detect various game scenarios (e.g. the ball is in the top, and our paddle is in the middle), and the weights in W2 can then decide if in each case we should be going UP or DOWN. Now, the initial random W1 and W2 will of course cause the player to spasm on spot. So the only problem now is to find W1 and W2 that lead to expert play of Pong!

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

Fine print: preprocessing. Ideally you’d want to feed at least 2 frames to the policy network so that it can detect motion. To make things a bit simpler (I did these experiments on my Macbook) I’ll do a tiny bit of preprocessing, e.g. we’ll actually feed difference frames to the network (i.e. subtraction of current and last frame).

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

It sounds kind of impossible. At this point I’d like you to appreciate just how difficult the RL problem is. We get 100,800 numbers (210*160*3) and forward our policy network (which easily involves on order of a million parameters in W1 and W2). Suppose that we decide to go UP. The game might respond that we get 0 reward this time step and gives us another 100,800 numbers for the next frame. We could repeat this process for hundred timesteps before we get any non-zero reward! E.g. suppose we finally get a +1. That’s great, but how can we tell what made that happen? Was it something we did just now? Or maybe 76 frames ago? Or maybe it had something to do with frame 10 and then frame 90? And how do we figure out which of the million knobs to change and how, in order to do better in the future? We call this the credit assignment problem. In the specific case of Pong we know that we get a +1 if the ball makes it past the opponent. The true cause is that we happened to bounce the ball on a good trajectory, but in fact we did so many frames ago - e.g. maybe about 20 in case of Pong, and every single action we did afterwards had zero effect on whether or not we end up getting the reward. In other words we’re faced with a very difficult problem and things are looking quite bleak.

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

Supervised Learning. Before we dive into the Policy Gradients solution I’d like to remind you briefly about supervised learning because, as we’ll see, RL is very similar. Refer to the diagram below. In ordinary supervised learning we would feed an image to the network and get some probabilities, e.g. for two classes UP and DOWN. I’m showing log probabilities (-1.2, -0.36) for UP and DOWN instead of the raw probabilities (30% and 70% in this case) because we always optimize the log probability of the correct label (this makes math nicer, and is equivalent to optimizing the raw probability because log is monotonic). Now, in supervised learning we would have access to a label. For example, we might be told that the correct thing to do right now is to go UP (label 0). In an implementation we would enter gradient of 1.0 on the log probability of UP and run backprop to compute the gradient vector \(\nabla_{W} \log p(y=UP \mid x) \). This gradient would tell us how we should change every one of our million parameters to make the network slightly more likely to predict UP. For example, one of the million parameters in the network might have a gradient of -2.1, which means that if we were to increase that parameter by a small positive amount (e.g. 0.001), the log probability of UP would decrease by 2.1 * 0.001 (decrease due to the negative sign). If we then did a parameter update then, yay, our network would now be slightly more likely to predict UP when it sees a very similar image in the future.

Обучение с учителем. Прежде чем мы погрузимся в решение 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. Okay, but what do we do if we do not have the correct label in the Reinforcement Learning setting? Here is the Policy Gradients solution (again refer to diagram below). Our policy network calculated probability of going UP as 30% (logprob -1.2) and DOWN as 70% (logprob -0.36). We will now sample an action from this distribution; E.g. suppose we sample DOWN, and we will execute it in the game. At this point notice one interesting fact: We could immediately fill in a gradient of 1.0 for DOWN as we did in supervised learning, and find the gradient vector that would encourage the network to be slightly more likely to do the DOWN action in the future. So we can immediately evaluate this gradient and that’s great, but the problem is that at least for now we do not yet know if going DOWN is good. But the critical point is that that’s okay, because we can simply wait a bit and see! For example in Pong we could wait until the end of the game, then take the reward we get (either +1 if we won or -1 if we lost), and enter that scalar as the gradient for the action we have taken (DOWN in this case). In the example below, going DOWN ended up to us losing the game (-1 reward). So if we fill in -1 for log probability of DOWN and do backprop we will find a gradient that discourages the network to take the DOWN action for that input in the future (and rightly so, since taking that action led to us losing the game).

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

And that’s it: we have a stochastic policy that samples actions and then actions that happen to eventually lead to good outcomes get encouraged in the future, and actions taken that lead to bad outcomes get discouraged. Also, the reward does not even need to be +1 or -1 if we win the game eventually. It can be an arbitrary measure of some kind of eventual quality. For example if things turn out really well it could be 10.0, which we would then enter as the gradient instead of -1 to start off backprop. That’s the beauty of neural nets; Using them can feel like cheating: You’re allowed to have 1 million parameters embedded in 1 teraflop of compute and you can make it do arbitrary things with SGD. It shouldn’t work, but amusingly we live in a universe where it does.

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

Training protocol. So here is how the training will work in detail. We will initialize the policy network with some W1, W2 and play 100 games of Pong (we call these policy “rollouts”). Lets assume that each game is made up of 200 frames so in total we’ve made 20,000 decisions for going UP or DOWN and for each one of these we know the parameter gradient, which tells us how we should change the parameters if we wanted to encourage that decision in that state in the future. All that remains now is to label every decision we’ve made as good or bad. For example suppose we won 12 games and lost 88. We’ll take all 200*12 = 2400 decisions we made in the winning games and do a positive update (filling in a +1.0 in the gradient for the sampled action, doing backprop, and parameter update encouraging the actions we picked in all those states). And we’ll take the other 200*88 = 17600 decisions we made in the losing games and do a negative update (discouraging whatever we did). And… that’s it. The network will now become slightly more likely to repeat actions that worked, and slightly less likely to repeat actions that didn’t work. Now we play another 100 games with our new, slightly improved policy and rinse and repeat.

Протокол обучения. Итак, вот как обучение будет работать в деталях. Мы инициализируем 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: Run a policy for a while. See what actions led to high rewards. Increase their probability.

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

If you think through this process you’ll start to find a few funny properties. For example what if we made a good action in frame 50 (bouncing the ball back correctly), but then missed the ball in frame 150? If every single action is now labeled as bad (because we lost), wouldn’t that discourage the correct bounce on frame 50? You’re right - it would. However, when you consider the process over thousands/millions of games, then doing the first bounce correctly makes you slightly more likely to win down the road, so on average you’ll see more positive than negative updates for the correct bounce and your policy will end up doing the right thing.

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

Update: December 9, 2016 - alternative view. In my explanation above I use the terms such as “fill in the gradient and backprop”, which I realize is a special kind of thinking if you’re used to writing your own backprop code, or using Torch where the gradients are explicit and open for tinkering. However, if you’re used to Theano or TensorFlow you might be a little perplexed because the code is oranized around specifying a loss function and the backprop is fully automatic and hard to tinker with. In this case, the following alternative view might be more intuitive. In vanilla supervised learning the objective is to maximize \( \sum_i \log p(y_i \mid x_i) \) where \(x_i, y_i \) are training examples (such as images and their labels). Policy gradients is exactly the same as supervised learning with two minor differences: 1) We don’t have the correct labels \(y_i\) so as a “fake label” we substitute the action we happened to sample from the policy when it saw \(x_i\), and 2) We modulate the loss for each example multiplicatively based on the eventual outcome, since we want to increase the log probability for actions that worked and decrease it for those that didn’t. So in summary our loss now looks like \( \sum_i A_i \log p(y_i \mid x_i) \), where \(y_i\) is the action we happened to sample and \(A_i\) is a number that we call an advantage. In the case of Pong, for example, \(A_i\) could be 1.0 if we eventually won in the episode that contained \(x_i\) and -1.0 if we lost. This will ensure that we maximize the log probability of actions that led to good outcome and minimize the log probability of those that didn’t. So reinforcement learning is exactly like supervised learning, but on a continuously changing dataset (the episodes), scaled by the advantage, and we only want to do one (or very few) updates based on each sampled dataset.

Обновление: 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, и мы хотим сделать только одно (или очень мало) обновлений на основе каждого сэмплированного набора данных.

More general advantage functions. I also promised a bit more discussion of the returns. So far we have judged the goodness of every individual action based on whether or not we win the game. In a more general RL setting we would receive some reward \(r_t\) at every time step. One common choice is to use a discounted reward, so the “eventual reward” in the diagram above would become \( R_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k} \), where \(\gamma\) is a number between 0 and 1 called a discount factor (e.g. 0.99). The expression states that the strength with which we encourage a sampled action is the weighted sum of all rewards afterwards, but later rewards are exponentially less important. In practice it can can also be important to normalize these. For example, suppose we compute \(R_t\) for all of the 20,000 actions in the batch of 100 Pong game rollouts above. One good idea is to “standardize” these returns (e.g. subtract mean, divide by standard deviation) before we plug them into backprop. This way we’re always encouraging and discouraging roughly half of the performed actions. Mathematically you can also interpret these tricks as a way of controlling the variance of the policy gradient estimator. A more in-depth exploration can be found here.

Более общие функции 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. Так мы всегда поощряем и наказываем примерно половину выполненных действий. Математически эти трюки можно также интерпретировать как способ контролировать дисперсию оценщика градиента политики. Более глубокое исследование можно найти здесь.

Deriving Policy Gradients. I’d like to also give a sketch of where Policy Gradients come from mathematically. Policy Gradients are a special case of a more general score function gradient estimator. The general case is that when we have an expression of the form \(E_{x \sim p(x \mid \theta)} [f(x)] \) - i.e. the expectation of some scalar valued score function \(f(x)\) under some probability distribution \(p(x;\theta)\) parameterized by some \(\theta\). Hint hint, \(f(x)\) will become our reward function (or advantage function more generally) and \(p(x)\) will be our policy network, which is really a model for \(p(a \mid I)\), giving a distribution over actions for any image \(I\). Then we are interested in finding how we should shift the distribution (through its parameters \(\theta\)) to increase the scores of its samples, as judged by \(f\) (i.e. how do we change the network’s parameters so that action samples get higher rewards). We have that:

Вывод 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\) (то есть как изменить параметры сети так, чтобы сэмплы действий получали более высокие награды). У нас есть:

To put this in English, we have some distribution \(p(x;\theta)\) (I used shorthand \(p(x)\) to reduce clutter) that we can sample from (e.g. this could be a gaussian). For each sample we can also evaluate the score function \(f\) which takes the sample and gives us some scalar-valued score. This equation is telling us how we should shift the distribution (through its parameters \(\theta\)) if we wanted its samples to achieve higher scores, as judged by \(f\). In particular, it says that look: draw some samples \(x\), evaluate their scores \(f(x)\), and for each \(x\) also evaluate the second term \( \nabla_{\theta} \log p(x;\theta) \). What is this second term? It’s a vector - the gradient that’s giving us the direction in the parameter space that would lead to increase of the probability assigned to an \(x\). In other words if we were to nudge \(\theta\) in the direction of \( \nabla_{\theta} \log p(x;\theta) \) we would see the new probability assigned to some \(x\) slightly increase. If you look back at the formula, it’s telling us that we should take this direction and multiply onto it the scalar-valued score \(f(x)\). This will make it so that samples that have a higher score will “tug” on the probability density stronger than the samples that have lower score, so if we were to do an update based on several samples from \(p\) the probability density would shift around in the direction of higher scores, making highly-scoring samples more likely.

Если выразить это словами: у нас есть некоторое распределение \(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\), плотность вероятности сдвигалась бы в сторону более высоких оценок, делая высокооценённые сэмплы более вероятными.

I hope the connection to RL is clear. Our policy network gives us samples of actions, and some of them work better than others (as judged by the advantage function). This little piece of math is telling us that the way to change the policy’s parameters is to do some rollouts, take the gradient of the sampled actions, multiply it by the score and add everything, which is what we’ve done above. For a more thorough derivation and discussion I recommend John Schulman’s lecture.

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

Learning. Alright, we’ve developed the intuition for policy gradients and saw a sketch of their derivation. I implemented the whole approach in a 130-line Python script, which uses OpenAI Gym’s ATARI 2600 Pong. I trained a 2-layer policy network with 200 hidden layer units using RMSProp on batches of 10 episodes (each episode is a few dozen games, because the games go up to score of 21 for either player). I did not tune the hyperparameters too much and ran the experiment on my (slow) Macbook, but after training for 3 nights I ended up with a policy that is slightly better than the AI player. The total number of episodes was approximately 8,000 so the algorithm played roughly 200,000 Pong games (quite a lot isn’t it!) and made a total of ~800 updates. I’m told by friends that if you train on GPU with ConvNets for a few days you can beat the AI player more often, and if you also optimize hyperparameters carefully you can also consistently dominate the AI player (i.e. win every single game). However, I didn’t spend too much time computing or tweaking, so instead we end up with a Pong AI that illustrates the main ideas and works quite well:

Обучение. Итак, мы разработали интуитивное понимание 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-ИИ, который иллюстрирует основные идеи и работает довольно хорошо:

Learned weights. We can also take a look at the learned weights. Due to preprocessing every one of our inputs is an 80x80 difference image (current frame minus last frame). We can now take every row of W1, stretch them out to 80x80 and visualize. Below is a collection of 40 (out of 200) neurons in a grid. White pixels are positive weights and black pixels are negative weights. Notice that several neurons are tuned to particular traces of bouncing ball, encoded with alternating black and white along the line. The ball can only be at a single spot, so these neurons are multitasking and will “fire” for multiple locations of the ball along that line. The alternating black and white is interesting because as the ball travels along the trace, the neuron’s activity will fluctuate as a sine wave and due to the ReLU it would “fire” at discrete, separated positions along the trace. There’s a bit of noise in the images, which I assume would have been mitigated if I used L2 regularization.

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

What isn’t happening

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

So there you have it - we learned to play Pong from from raw pixels with Policy Gradients and it works quite well. The approach is a fancy form of guess-and-check, where the “guess” refers to sampling rollouts from our current policy, and the “check” refers to encouraging actions that lead to good outcomes. Modulo some details, this represents the state of the art in how we currently approach reinforcement learning problems. Its impressive that we can learn these behaviors, but if you understood the algorithm intuitively and you know how it works you should be at least a bit disappointed. In particular, how does it not work?

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

Compare that to how a human might learn to play Pong. You show them the game and say something along the lines of “You’re in control of a paddle and you can move it up and down, and your task is to bounce the ball past the other player controlled by AI”, and you’re set and ready to go. Notice some of the differences:

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

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

I’d like to also emphasize the point that, conversely, there are many games where Policy Gradients would quite easily defeat a human. In particular, anything with frequent reward signals that requires precise play, fast reflexes, and not too much long-term planning would be ideal, as these short-term correlations between rewards and actions can be easily “noticed” by the approach, and the execution meticulously perfected by the policy. You can see hints of this already happening in our Pong agent: it develops a strategy where it waits for the ball and then rapidly dashes to catch it just at the edge, which launches it quickly and with high vertical velocity. The agent scores several points in a row repeating this strategy. There are many ATARI games where Deep Q Learning destroys human baseline performance in this fashion - e.g. Pinball, Breakout, etc.

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

In conclusion, once you understand the “trick” by which these algorithms work you can reason through their strengths and weaknesses. In particular, we are nowhere near humans in building abstract, rich representations of games that we can plan within and use for rapid learning. One day a computer will look at an array of pixels and notice a key, a door, and think to itself that it is probably a good idea to pick up the key and reach the door. For now there is nothing anywhere close to this, and trying to get there is an active area of research.

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

Non-differentiable computation in Neural Networks

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

I’d like to mention one more interesting application of Policy Gradients unrelated to games: It allows us to design and train neural networks with components that perform (or interact with) non-differentiable computation. The idea was first introduced in Williams 1992 and more recently popularized by Recurrent Models of Visual Attention under the name “hard attention”, in the context of a model that processed an image with a sequence of low-resolution foveal glances (inspired by our own human eyes). In particular, at every iteration an RNN would receive a small piece of the image and sample a location to look at next. For example the RNN might look at position (5,30), receive a small piece of the image, then decide to look at (24, 50), etc. The problem with this idea is that there a piece of network that produces a distribution of where to look next and then samples from it. Unfortunately, this operation is non-differentiable because, intuitively, we don’t know what would have happened if we sampled a different location. More generally, consider a neural network from some inputs to outputs:

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

Notice that most arrows (in blue) are differentiable as normal, but some of the representation transformations could optionally also include a non-differentiable sampling operation (in red). We can backprop through the blue arrows just fine, but the red arrow represents a dependency that we cannot backprop through.

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

Policy gradients to the rescue! We’ll think about the part of the network that does the sampling as a small stochastic policy embedded in the wider network. Therefore, during training we will produce several samples (indicated by the branches below), and then we’ll encourage samples that eventually led to good outcomes (in this case for example measured by the loss at the end). In other words we will train the parameters involved in the blue arrows with backprop as usual, but the parameters involved with the red arrow will now be updated independently of the backward pass using policy gradients, encouraging samples that led to low loss. This idea was also recently formalized nicely in Gradient Estimation Using Stochastic Computation Graphs.

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

Trainable Memory I/O. You’ll also find this idea in many other papers. For example, a Neural Turing Machine has a memory tape that they it read and write from. To do a write operation one would like to execute something like m[i] = x, where i and x are predicted by an RNN controller network. However, this operation is non-differentiable because there is no signal telling us what would have happened to the loss if we were to write to a different location j != i. Therefore, the NTM has to do soft read and write operations. It predicts an attention distribution a (with elements between 0 and 1 and summing to 1, and peaky around the index we’d like to write to), and then doing for all i: m[i] = a[i]*x. This is now differentiable, but we have to pay a heavy computational price because we have to touch every single memory cell just to write to one position. Imagine if every assignment in our computers had to touch the entire RAM!

Обучаемый ввод/вывод памяти. Вы также найдёте эту идею во многих других статьях. Например, 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!

However, we can use policy gradients to circumvent this problem (in theory), as done in RL-NTM. We still predict an attention distribution a, but instead of doing the soft write we sample locations to write to: i = sample(a); m[i] = x. During training we would do this for a small batch of i, and in the end make whatever branch worked best more likely. The large computational advantage is that we now only have to read/write at a single location at test time. However, as pointed out in the paper this strategy is very difficult to get working because one must accidentally stumble by working algorithms through sampling. The current consensus is that PG works well only in settings where there are a few discrete choices so that one is not hopelessly sampling through huge search spaces.

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

However, with Policy Gradients and in cases where a lot of data/compute is available we can in principle dream big - for instance we can design neural networks that learn to interact with large, non-differentiable modules such as Latex compilers (e.g. if you’d like char-rnn to generate latex that compiles), or a SLAM system, or LQR solvers, or something. Or, for example, a superintelligence might want to learn to interact with the internet over TCP/IP (which is sadly non-differentiable) to access vital information needed to take over the world. That’s a great example.

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

Conclusions

Заключение

We saw that Policy Gradients are a powerful, general algorithm and as an example we trained an ATARI Pong agent from raw pixels, from scratch, in 130 lines of Python. More generally the same algorithm can be used to train agents for arbitrary games and one day hopefully on many valuable real-world control problems. I wanted to add a few more notes in closing:

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

On advancing AI. We saw that the algorithm works through a brute-force search where you jitter around randomly at first and must accidentally stumble into rewarding situations at least once, and ideally often and repeatedly before the policy distribution shifts its parameters to repeat the responsible actions. We also saw that humans approach these problems very differently, in what feels more like rapid abstract model building - something we have barely even scratched the surface of in research (although many people are trying). Since these abstract models are very difficult (if not impossible) to explicitly annotate, this is also why there is so much interest recently in (unsupervised) generative models and program induction.

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

On use in complex robotics settings. The algorithm does not scale naively to settings where huge amounts of exploration are difficult to obtain. For instance, in robotic settings one might have a single (or few) robots, interacting with the world in real time. This prohibits naive applications of the algorithm as I presented it in this post. One related line of work intended to mitigate this problem is deterministic policy gradients - instead of requiring samples from a stochastic policy and encouraging the ones that get higher scores, the approach uses a deterministic policy and gets the gradient information directly from a second network (called a critic) that models the score function. This approach can in principle be much more efficient in settings with very high-dimensional actions where sampling actions provides poor coverage, but so far seems empirically slightly finicky to get working. Another related approach is to scale up robotics, as we’re starting to see with Google’s robot arm farm, or perhaps even Tesla’s Model S + Autopilot.

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

There is also a line of work that tries to make the search process less hopeless by adding additional supervision. In many practical cases, for instance, one can obtain expert trajectories from a human. For example AlphaGo first uses supervised learning to predict human moves from expert Go games and the resulting human mimicking policy is later finetuned with policy gradients on the “real” objective of winning the game. In some cases one might have fewer expert trajectories (e.g. from robot teleoperation) and there are techniques for taking advantage of this data under the umbrella of apprenticeship learning. Finally, if no supervised data is provided by humans it can also be in some cases computed with expensive optimization techniques, e.g. by trajectory optimization in a known dynamics model (such as \(F=ma\) in a physical simulator), or in cases where one learns an approximate local dynamics model (as seen in very promising framework of Guided Policy Search).

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

On using PG in practice. As a last note, I’d like to do something I wish I had done in my RNN blog post. I think I may have given the impression that RNNs are magic and automatically do arbitrary sequential problems. The truth is that getting these models to work can be tricky, requires care and expertise, and in many cases could also be an overkill, where simpler methods could get you 90%+ of the way there. The same goes for Policy Gradients. They are not automatic: You need a lot of samples, it trains forever, it is difficult to debug when it doesn’t work. One should always try a BB gun before reaching for the Bazooka. In the case of Reinforcement Learning for example, one strong baseline that should always be tried first is the cross-entropy method (CEM), a simple stochastic hill-climbing “guess and check” approach inspired loosely by evolution. And if you insist on trying out Policy Gradients for your problem make sure you pay close attention to the tricks section in papers, start simple first, and use a variation of PG called TRPO, which almost always works better and more consistently than vanilla PG in practice. The core idea is to avoid parameter updates that change your policy too much, as enforced by a constraint on the KL divergence between the distributions predicted by the old and the new policy on a batch of data (instead of conjugate gradients the simplest instantiation of this idea could be implemented by doing a line search and checking the KL along the way).

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

And that’s it! I hope I gave you a sense of where we are with Reinforcement Learning, what the challenges are, and if you’re eager to help advance RL I invite you to do so within our OpenAI Gym :) Until next time!

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