From Q-Tables to AlphaGo Zero: A Self-Driving Car Lecture on Deep Reinforcement Learning

Fridman frames the lecture around how far systems can be taught to perceive and act from data. He lays out the stack: an environment sensed by lidar, cameras, radar, GPS and other sensors, features and ever higher-order representations, knowledge aggregated from them, reasoning and planning toward an objective or reward function, and effectors that act on the world.

Before deep networks, he notes, experts hand-crafted representations; now networks form them automatically and support supervised, generative and unsupervised tasks. The most successful part of machine learning over three decades has been mapping raw sensory data to useful information. Integrating that information, for example fusing image, activity and audio cues to be confident that something is a duck, is something current approaches do not yet do well.

Planning and control, he says, are increasingly amenable to learning but have so far been most successful with non-learning optimization methods, as with Boston Dynamics' Atlas robot. The open question is whether the learnable portion can expand all the way from sensory data through reasoning to action, something deep reinforcement learning can do on simple tasks and might one day do for autonomous vehicles and humanoid robots.

Fridman places reinforcement learning between supervised learning, where humans label all data, and unsupervised learning, where none is labeled. Its goal is to learn from sparse reward signals while exploiting the fact that the world evolves predictably through time, so information can be traced backward to assign credit to earlier states. Supervised learning, in his words, is memorization of ground truth; reinforcement learning brute-force propagates sparse information through time, which he compares to reasoning.

The framework is an agent taking actions in an environment, observing a new state and receiving a reward, a Markov decision process. He illustrates it with Atari Breakout, cart-pole balancing, first-person shooters like Doom and robotic bin picking. Its main components are a policy, a value function and sometimes a model of the environment.

In a three-by-four grid world with a small penalty per step, he shows how the optimal policy changes. With non-deterministic moves, every state needs a plan, and as the step penalty shrinks the agent wanders more, until positive per-step rewards give an incentive never to finish, which he jokes is like college.

The value of a state is the future reward you expect, with later rewards discounted by a factor gamma. Q-learning is off-policy: as the agent moves through the world, the Bellman equation updates the estimate of an action's value using the received reward plus the discounted maximum value of the next state, scaled by a learning rate. Fridman calls it simple and says that is all there is to it.

He stresses the balance between exploration and exploitation. Early on, when the Q estimate is poor, the agent should explore a lot; as the estimate improves, exploration yields less and the agent increasingly acts greedily. These parameters, he says, matter for winning the DeepTraffic competition.

A table of Q values over states and actions works only for small problems. With raw camera pixels, Atari frames or a Go board, the state space becomes far too large to store or learn accurately through the Bellman update, which is where deep reinforcement learning comes in.

Fridman explains that neural networks are good approximators, so you replace the Q table with a network that takes the state and outputs a value for each action. This is the deep Q-network (DQN) behind DeepMind's Atari results. Training resembles supervised learning, with a loss comparing the network's estimate for the current state with the reward plus the estimated best value of the next state, updated through backpropagation.

The first key trick is experience replay: observations are stored in a library and the network trains on random batches, so it does not overfit one continuous evolution of the game. The second is fixing the target network used inside the loss function, updating it only every thousand or so steps, so the target does not shift constantly and destabilize learning.

Two more simplifications help: reward clipping, which normalizes game scores to plus or minus one, and acting only every four frames on 30 or 60 FPS games. Fridman shows results where replay and the target network together bring order-of-magnitude, even two-orders, gains on games such as Breakout. He says the 2015 result made many think general AI was within reach, though the games remain trivial.

Fridman calls AlphaGo, and especially AlphaGo Zero, one of the greatest AI accomplishments of the decade from a philosophical or research perspective. Go has roughly 2 times 10 to the 170 legal positions on its 19 by 19 board, so the community thought it unsolvable until 2016, when AlphaGo used human expert play to seed a reinforcement learning approach.

AlphaGo Zero used no human expert games at all and reached a rating above AlphaGo and its variants, and above the best human players, in 21 days of self-play. Both rely on Monte Carlo tree search, with a neural network acting as intuition about which board positions deserve exploration. In the Zero version the search's look-ahead provides the ground-truth correction that produces the loss.

He lists the other changes: a network with two heads, one giving move probabilities and one giving the probability of winning, trained together as a form of multitask learning, and an upgrade to residual network architecture of the kind that won ImageNet. Those small changes, he repeats, made all the difference.

DeepTraffic is a competition in which a neural network in the browser controls a car in a micro traffic simulation, choosing among five actions such as speed up, slow down and change lanes. The state is an occupancy grid showing achievable speeds, the network outputs a value per action, and training runs in JavaScript on the user's own CPU. Students must reach 65 miles per hour, and winning requires over 70, with an 80 mph speed limit that cannot be averaged.

This year's version adds multi-agent control of up to ten cars and custom car images. The agents are not aware of each other and act greedily, trained on the joint objective of average speed, which makes the approach scalable to any number of cars. Participants tune layers, activation functions, epsilon, replay size, learning rate, temporal window and other parameters, with a safety system blocking collisions.

To reduce randomness and resubmission gaming, evaluation takes the median speed over 500 server-side runs of about 45 simulated seconds each. Students can submit every five minutes, save and load networks and request custom visualizations.

Fridman closes with a caution: learning from scratch through self-play as AlphaGo Zero did would mean millions of crashes for a real car, so it works only in simulation or on small platforms like their RC car. To his knowledge, the most successful real robots, from Boston Dynamics to Waymo, rely mainly on model-based optimization, and he flags reward hacking as a safety concern for the upcoming AGI portion of the course.