Deep Reinforcement Learning from First Principles: Rewards, Q-Learning, Policy Gradients and AlphaZero

Fridman calls deep reinforcement learning one of the most exciting areas of AI because it marries a neural network's ability to represent the world with the ability to act on that understanding. He sees understanding the world and acting in it as the essence of building intelligent beings. The setting is sequential decision-making, where an agent's choices affect the world around it and learning happens by trial and error.

He pushes back on the idea that only supervised learning needs supervision. Every kind of machine learning is supervised by a loss function that says what is good and bad, and the categories differ in the source of that signal and how much human labor it costs. As he puts it, it is never turtles all the way down: at the bottom there is a human.

Supervised learning learns from fixed examples with ground truth, whereas reinforcement learning teaches through experience, by placing an agent in a world. The designer therefore designs the world, its dynamics and its rewards, and the reward, the definition of good versus bad, is perhaps the hardest part. A baby walking across a room is his example of a simple success definition.

Fridman lists possible explanations for how people learn from so few trial-and-error attempts. It may be hardware encoded by evolution, from hundreds of millions of years of walking and seeing, or fast learning from observation and imitation in the first months and years. A third option is that the brain's learning algorithm itself, possibly something like backpropagation, is simply not understood.

He asks students to keep this in mind as they study RL's comparatively trivial accomplishments. He describes the agent stack from sensors, such as cameras, lidar, GPS or microphones, through learned representations to actions. Deep learning provides the step from raw data to higher-level abstractions, and deep RL goes beyond it by using that representation to act and succeed. Combining image, audio and video understanding, or transferring from Atari to Go to robotics, he notes, is still an open problem.

In the basic framework an agent receives an observation, takes an action, the environment changes, and a new observation and reward arrive. Most formulations assume no memory beyond the previous state, the next state and the reward. Environments can be fully or partially observable, single or multi-agent, deterministic or stochastic, static or dynamic, and discrete or continuous.

The core agent components are a policy, a value function that estimates how good a state or state-action pair is, and a model, the agent's understanding of the environment. The goal is to maximize discounted reward, partly as a mathematical convenience for analysis and partly because uncertainty makes distant rewards hard to estimate. He notes that today agents are mostly trained in simulation or constrained real-world settings, so closing the gap means either better transferable algorithms or higher-fidelity simulation.

In the 12-cell example the robot starts at the bottom left, seeks a +1 square and avoids a -1 square, paying a small cost per step. In a deterministic world the optimal policy is the shortest path, but with 80% reliable moves it takes longer routes to avoid risk near the -1 square. Raising the per-step penalty to -2 makes it ignore risk, a milder one makes it more urgent, and positive rewards make the optimal policy the longest possible path, which he jokes is grad school.

Fridman shows the boat-racing game CoastRunners, where a human tries to finish fast and first. A reinforcement learning agent discovered that picking up green turbo items scored more, so it circled endlessly and crashed into walls to keep collecting them, since finishing would end the stream of reward. It is a trivial example, but such unintended outcomes can be seriously harmful in real systems.

He extends this to autonomous vehicles that must take subtle risks at intersections full of pedestrians, and to a Doom agent whose objective is eliminating opponents, which he uses to raise concerns about autonomous weapons. Groups at DeepMind and OpenAI work on AI safety for good reason. He believes AI will define some of the most positive impacts of the 21st century but that we are nowhere near solving fundamental safety problems.

Other benchmark examples are cart-pole balancing, with the pole angle and cart velocity as state and a +1 reward per upright step, and robotic grasping from raw pixels. He adds that autonomous driving forces ethical questions about risk, human life and efficiency that must be encoded somehow. The real-world lesson he draws is that for deep learning the hard part is data and good questions, while for deep RL the hard parts are defining the environment and reward and crossing the sim-to-real gap.

He divides RL algorithms into model-based, value-based and policy-based. Model-based methods learn a model of the world so they can plan ahead and are very sample-efficient, as in chess or Go where the rules are given. Value-based methods estimate the quality of taking an action in a state and pick the best one, while policy-based methods directly learn a stochastic policy, and he recommends OpenAI's Spinning Up taxonomy.

Q-learning keeps a table of state-action values that is updated with the Bellman equation, off-policy and model-free, with exploration via epsilon-greedy random actions that decrease over time. A table is hopeless for raw sensory input: four 84-by-84 grayscale Breakout frames have 256 values per pixel, a state space he says exceeds the number of atoms in the universe. The deep Q-network fixes this by using a neural network as a function approximator, and a fairly simple network reached superhuman performance on many Atari games from raw pixels.

The loss compares the predicted Q-value with a target built from the next state's best Q-value, so the network is partly chasing its own tail. Two tricks stabilize it: experience replay, which trains on remembered past experience, and a target network that is updated only every thousand steps or so. Extensions include dueling DQN, which separates state value from action advantage, and prioritized experience replay, which replays experiences with large temporal-difference errors more often.

Vanilla policy gradient plays whole episodes, such as Pong, and rewards or punishes every action based only on whether the game was eventually won. Fridman finds it remarkable that this works despite the muddy credit assignment. It handles stochastic policies and continuous actions naturally and can still learn when a Q function cannot be learned, but it is inefficient and can be unstable.

Advantage actor-critic combines the two families: an actor samples actions from a policy network and a critic, which is value-based, evaluates them at every step, making learning more sample-efficient. A3C updates a global network asynchronously, so agents work with slightly outdated parameters. OpenAI's A2C variant waits for all agents to finish a round and then distributes identical parameters, which improves stability.

DDPG blends DQN ideas with continuous actions by having the actor choose a deterministic action, so exploration must be injected by adding noise to the actions or the parameters, shrinking as training proceeds. TRPO and PPO treat RL as an optimization problem in which bad steps can collapse training, so they limit the size of each policy change with a trust region instead of choosing a direction first and a step size second.

For model-based settings with known rules, such as Go and chess, the neural network's task is to estimate the quality of board positions and which branches of the exponentially growing game tree are worth exploring. The first AlphaGo that beat the world champion was pre-trained on expert games, whereas AlphaGo Zero used no expert data and learned purely through self-play. These systems use Monte Carlo tree search to balance exploiting promising positions with exploring others.

AlphaZero applies a similar architecture to chess, shogi and Go and outperforms the leading engines, including Stockfish in chess and Elmo in shogi. Fridman likes the comparison with human grandmasters, who explore few moves because they have a good internal sense of which are valuable, while Stockfish is more brute force. AlphaZero moves toward the grandmaster, doing much of the work in the network's representation and exploring far fewer branches.

Fridman calls it a sobering truth that most real-world agents, including the autonomous vehicle companies operating today and industrial and humanoid robots, learn no action from data and use neural networks only for perception. He notes that Boston Dynamics' work, as far as is known, involves no machine learning. That is starting to change, for example with the ANYmal robot learning to get up from arbitrary positions and with Waymo using some RL for driving policy and predicting intent.

Because most work still happens in simulation, the field needs better transfer learning or higher-fidelity simulations. He relays an idea mentioned by Pieter Abbeel: instead of making one simulation more realistic, build a very large number of simulations so that reality is just another sample. He jokes that this may be exactly what whoever created our own simulation did.

For students wanting to start in research, he recommends building the math background, learning the basics of deep learning and RL, picking TensorFlow or PyTorch, and implementing the core algorithms from scratch, which takes only a couple of hundred lines. Then read follow-up papers for their tricks rather than headline performance, and iterate quickly on OpenAI Gym environments. Research contributions generally come from improving an existing approach, tackling an unsolved task, or posing an entirely new problem for RL.