Policy Gradients vs. Q-Learning: John Schulman's Field Guide to Deep Reinforcement Learning

John Schulman opens by defining reinforcement learning as the branch of machine learning concerned with taking sequences of actions. An agent interacts with a previously unknown environment and tries to maximize a cumulative reward that the designer defines. Almost any goal-directed task can be phrased this way, which makes the formulation extremely general.

Deep reinforcement learning, he says, is simply RL where neural networks act as function approximators. The less obvious part is what the network should approximate. It can represent the policy, the value functions that score states and actions, or a dynamics model that predicts next states and rewards, and different algorithms choose different targets.

He then runs through example problems. In robotics the observations are camera images and joint angles, the actions are joint torques, and the reward is whatever the designer wants. In inventory management the actions are purchase quantities and the reward is profit. RL is also used inside machine learning itself, for example in attention models that decide where to crop an image and in machine translation, where a sentence-level score is non-differentiable and calls for a policy gradient method.

Schulman compares RL to its neighbours as a ladder of increasing difficulty. In supervised learning the environment asks a question and then reveals the right answer. In the contextual bandit setting the agent only gets a noisy score drawn from an unknown distribution, which describes personalized recommendations and advertising. That means you cannot differentiate through the loss and need a different kind of algorithm.

Full reinforcement learning adds one more step, which is that the environment is stateful. Because the state evolves according to your previous states and actions, the inputs you receive depend on what you do. This makes it harder to build a stable algorithm, since the data changes as the agent learns. It also creates delayed effects, so the agent has to think ahead instead of acting greedily.

He sums this up as two differences from supervised learning. You lack analytic access to the function you are optimizing and must query it through interaction, and you are interacting with a world that remembers your actions. Take only the first difference and you land halfway between the two settings, at the contextual bandit.

Speaking to practitioners in the audience, Schulman says the honest answer may be that RL is overkill. Deep RL is a fairly new set of techniques that does not work well out of the box and has many knobs to tune. If your problem has a small number of parameters and a simulator you can run many experiments on, derivative-free optimization of a black-box function is likely easier to get working.

Many problems are also better viewed as contextual bandits. Advertising is the example he gives: the user is technically stateful, since a terrible ad might push them to install an ad blocker, but treating it as stateless is usually a good approximation and comes with better theoretical guarantees. Operations research has likewise used policy iteration and value iteration with well-developed feature engineering for years, so those are worth considering before throwing a large network at a problem.

He then lists results that probably would not have been possible with those alternatives. These include DeepMind's deep Q-learning on Atari from raw screen images, and a champion-level Go player that combined supervised learning, policy gradients, Monte Carlo tree search and value functions. They also include guided policy search for robot manipulation on the PR2, locomotion learned with general policy gradient methods, and 3D game playing.

The talk then turns formal. A Markov decision process consists of a state space, an action space, and a probability distribution over the next state and reward given the current state and action, plus an initial state distribution. Schulman focuses on the episodic setting, where experience is split into finite episodes that run until the world reaches a terminal state.

He illustrates the different flavors of termination with examples. A taxi robot wants to end its episode as fast as possible, a waiter robot works a fixed-length shift, and a walking robot wants the episode to last as long as possible before it falls over. In every case the goal is to maximize the expected total reward per episode.

A policy is the function the agent uses to choose actions, and it can be deterministic or stochastic. For policy gradient methods it is parameterized by a vector theta, such as the weights of a network. Representing it works just like classification or regression: with discrete actions the network outputs probabilities, and with continuous actions it outputs the mean and diagonal covariance of a Gaussian.

Policy gradient methods collect trajectories with the current policy and make the good ones more probable. The simplest versions raise the probability of whole good trajectories, better ones work out which actions were good, and a third family differentiates the loss with respect to the actions themselves. Schulman concentrates on the first two.

The mathematical core is the score function gradient estimator. To estimate the gradient of an expectation of f(x), you sample x and multiply f(x) by the gradient of the log probability of x. The estimator is unbiased, and the intuition is that you push up the log probability of each sample in proportion to how good it was, so the density slides toward better regions.

What makes this remarkable is how little it requires. It works when f is discontinuous, when f is unknown and can only be queried, and when the sample space is discrete. In robotic locomotion, making and breaking contact between foot and ground creates discontinuities that break smooth optimization, yet this estimator can still optimize through them.

Applied to a whole trajectory, the unfriendly trajectory probability turns into a product of terms, and the logarithm makes it a sum. Everything that does not depend on theta, including the unknown dynamics and initial state distribution, drops out. What remains is the total reward times the sum of the gradients of the log action probabilities, which treats high-reward trajectories like positive examples in supervised learning.

The basic estimator is unbiased but has very high variance when episodes are long, so Schulman gives three fixes. First, use temporal structure: an action cannot affect earlier rewards, so only the sum of future rewards should multiply each action's log probability. This leaves the mean unchanged and lowers the variance.

Second, subtract a baseline that depends only on the state. A near-optimal choice is the expected return, so that an action is reinforced only if the rewards after it were better than expected. Third, use discounting with a factor such as 0.99, which decays the influence of distant rewards. It looks like a hack, he says, but it rests on the assumption that actions do not strongly affect rewards far in the future.

These pieces generalize into a gradient of log probability times an advantage estimate, meaning how much better an action was than expected. The vanilla policy gradient algorithm runs the policy for whole episodes, computes returns and advantages, refits the baseline by regression, and takes a gradient step on the policy. Schulman stresses that without these variance reduction techniques, little will work beyond small problems.

Step sizes are not a big deal in supervised learning, because a bad step is fixed by the next update and the classifier does not affect which inputs it sees. In RL a step that is too large can change behavior drastically and send the agent to an entirely different part of state space. The next batch of data then comes from the bad policy, and the agent may never recover.

His fix, developed with colleagues, is trust region policy optimization. It constrains the KL divergence between the action distributions of the old and new policy so no single update changes behavior too much. It is closely related to natural policy gradient methods, which are usually not framed as a hard constraint. He also mentions actor-critic methods and reparameterization-style approaches, which cut variance but add bias that no amount of data can fix.

To show it in action, he plays a video of a simulated humanoid in the MuJoCo physics simulator, controlled by a network that maps raw joint angles and velocities to torques 100 times a second. The reward is just moving forward, and the humanoid goes from falling over to a stable run. A multi-legged robot invented without much thought finds its own odd gait, and a variant rewarded for head height learns to get up off the ground.

In the questions that follow, Schulman admits that nothing is guaranteed if rewards are delayed by more than about one over one minus gamma steps. He sees this as something fundamental that is missing, and he points to hierarchical RL as an active research direction. The learned walkers are surprisingly robust to dynamics changes because they were trained with a noisy stochastic policy.

The second family does not optimize a policy directly. Instead it learns a Q function that measures how good state-action pairs are. Schulman notes that these methods are the preferred way to solve MDPs exactly when states and actions are finite, but with continuous spaces and neural networks it is harder to know when they will work. He defines the Q function, the state value function V, and the advantage as the difference between them.

The Bellman equation is a consistency condition: the value of an action equals the first reward plus the value of what follows. Turning the right-hand side into a backup operator gives a map from Q functions to Q functions. The true Q function of a policy is its fixed point, and repeatedly applying the operator to any starting Q function converges to it.

The same idea works for the optimal Q function, using the argmax over actions in the backup. This leads to the two classic dynamic programming algorithms, value iteration, which repeats Bellman backups, and policy iteration, which alternates evaluating a policy and acting greedily on its Q function. Remarkably, both can be run with only sampled interaction, since a single sample gives an unbiased estimate of the backup target.

With a neural network Q function, you cannot set outputs directly, so the backup becomes a least-squares problem minimized with SGD. An early version of this was neural fitted Q iteration. To act, you can take the highest-valued action, or sample with probability exponential in Q over a temperature, which is known as Boltzmann exploration.

A nice property of these algorithms is that you do not have to execute the greedy policy, so you can use any exploration policy and still converge. DeepMind's DQN is an online version of this approach with two tweaks. A replay pool keeps a rolling history of data that is representative for fitting the Q function, and a lagged target network is used in the backups, which is the natural way to run value iteration online.

Sarsa is the classic online counterpart for policy iteration, and Schulman says it sometimes works as well as or better than DQN, though not in all settings. In his view the jury is still out on how these algorithms compare under function approximation, so both should be taken seriously.

Summing up, Schulman puts policy gradient variants (vanilla, A3C, and the natural and trust region methods) on one side and Q-function descendants of value and policy iteration on the other. Trust region methods are more sample efficient than vanilla gradients because they extract more than one update from each batch of data. He calls his comparison anecdotal but says it reflects the current consensus.

Q-function methods are more sample efficient when they work, but they work less generally and are harder to diagnose when they fail. That makes sense to him, since policy gradients optimize exactly what you care about with gradient descent, while Q-learning learns something indirect and hopes it yields a good policy. He cautions that comparisons are confounded by different time horizons, since Q methods use one-step lookahead and policy gradients use multi-step returns.

He hopes for improvements that combine the best of both: the easy off-policy exploration of Q methods and the reliability of policy gradients. He is not sure that is possible.

Asked about model-based RL, Schulman likes his colleagues' guided policy search and a paper on stochastic value gradients that uses a model for variance reduction. He calls it a wide-open area, since learning much faster with a model should be possible but has not yet been compellingly shown. On the real world, he says the locomotion results add up to about two weeks of real time, which is not bad compared with toddlers learning to walk, and colleagues at Berkeley are running RL on real robots.

On the loss landscape, he says RL's difficulty comes from the space of behaviors rather than numerical optimization. A walking robot can get stuck standing still to avoid the penalty for falling, or diving forward for a little reward before it falls. He has found that the network architecture matters surprisingly little.

On sparse rewards, he says problems get harder when rewards are far away, and the head-height task became easier with a smooth reward based on squared distance from the target height. With zero reward until success, exploration becomes the problem. The last question concerns discretizing time: too small a time step delays rewards, which makes credit assignment harder and turns exploration into a random walk. He calls this a flaw of current methods.