From NAND Gates to Self-Driving Traffic: Deep Reinforcement Learning in One Lecture

Lex Fridman opens the lecture by previewing DeepTraffic, the first course project, in which students design a network that solves a traffic problem with deep reinforcement learning and compete for a prize. Before that, he sorts machine learning into types. Supervised learning has inputs and known outputs, unsupervised learning has only data with structure to be found, and semi-supervised learning has a small labeled fraction, much like ImageNet is a tiny slice of the images online.

Reinforcement learning, he says, sits somewhere in between. An agent has to exist in a world, sees the inputs that world provides, and knows very little about it except through occasional, time-delayed rewards. He jokes that this is what being human is like: you only find out later that what you did last week was a bad idea.

The standard supervised pipeline is then laid out: raw data, ground-truth labels, feature extraction, a model that is trained and evaluated in a loop, and finally release to predict on unseen data. Fridman stresses that something must always play the role of truth to hold on to. In supervised learning it is the labels, and in reinforcement learning it is the reward.

Neural networks are built from neurons, and the original version, the perceptron, takes binary inputs, multiplies them by weights, adds a bias and outputs 1 or 0 depending on a threshold. Fridman shows that with weights of -2 on each input and a bias of 3, a perceptron reproduces a NAND gate. Because NAND is functionally complete, any computer, including the phone in your pocket, can in principle be built from them.

The difference is that a circuit of NAND gates has to be designed from the bottom up, while a circuit of neurons can learn the same logical functions without a human designer. The weakness of the perceptron is that its step output is brittle: a small tweak to a weight can flip an output from 0 to 1, which makes stacks of them hard to control.

The essential fix is a smooth activation function such as the sigmoid, so the output changes gradually as weights and biases change. Learning then becomes the process of nudging weights and watching whether you move closer to or farther from the ground truth. He mentions recurrent networks, which have memory but are hard to train, and says the lecture will stick to feed-forward networks.

Fridman uses handwritten digit classification as the worked example. A 28 by 28 image becomes 784 input values from 0 to 255, passes through a hidden layer of 15 neurons that forms a representation of the data, and ends in 10 outputs, one per digit. Only four outputs would be needed to encode 0 through 9, but in practice ten work better, with the neuron for the right digit becoming "really excited" near 1.

The forward pass applies weights, sums, adds biases and checks which output is most confident. The gradient of the loss, here a simple squared error against a ten-dimensional ground-truth vector, is then used to reward or punish the weights as it is propagated backward. Thanks to the smooth activations this is mathematically efficient, which is where GPUs come in.

Gradient descent minimizes this loss, but the function is high-dimensional and highly non-linear, which is why so little can be proven about it. Some stochastic element is needed to avoid getting stuck in a local minimum. Fridman's verdict on the supervised setting is that it is a comfort zone, but a network trained there is great at memorization and may not reason beyond the flavor of data it saw.

From the agent's side, existence breaks down into executing an action, receiving a new state as an observation, and getting a reward or punishment. Fridman illustrates with DeepMind's Atari Breakout, where the paddle is rewarded with points and punished by losing a life. The goal is to pick, at each moment, the action that maximizes future reward, formalized as a Markov decision process with no memory beyond the current state.

The main components are a policy, a value function and a model of the environment. He flags the model as the biggest problem behind everything in the lecture: the amazing results come from simplistic worlds, and it is unclear whether they extend to the real world where human lives are at stake in driving.

A toy robot-in-a-room grid shows how the reward structure changes behavior. With a 0.8 chance of moving as intended and a small step penalty, the optimal policy is not the obvious path. A big penalty per step makes the agent walk through the -1 block to finish sooner, a smaller one makes it detour, and a positive reward per step makes it wander forever, as with the Coast Runner boat from the previous lecture that never finished its race.

Future rewards are discounted by a factor gamma because the world is stochastic, so the agent maximizes a discounted sum. There are many ways to find a good policy, including building a model or running Monte Carlo simulation, but the lecture focuses on Q-learning, an off-policy method whose policy is represented by a Q-function.

The Q-function takes a state and an action and estimates the value of taking that action. Using the Bellman equation as an update rule, the agent blends its old estimate with new evidence at a learning rate alpha: at 0 it never changes its worldview, at 1 it overwrites it every time. Through pure experience it approximates the optimal Q-function, as long as it explores enough states and actions.

The balance between exploring and exploiting comes from an epsilon-greedy policy. With probability epsilon the agent takes a random action, otherwise the best-known one, and epsilon is lowered from 1 toward 0 over time. Fridman asks the audience to remember that the estimates are initialized randomly, so the agent starts with no notion of good or bad, and the fact that it learns anything is remarkable.

In Q&A he explains that hand-modeling even Atari's physics requires expert knowledge, while feeding in raw pixels works much like a newborn receiving only light and sound. Robustness to a wrong world model is poorly studied, but a wrong reward function could have huge negative consequences. Alpha should change over time, and how long to keep epsilon high depends on the problem, one of several parameters that stop you from simply dropping an RL agent into the world.

Representation matters. Treating a game as hand-built features does not scale, and treating it as pixels makes the Q-table explode. An 84 by 84 grayscale image, stacked with three previous frames to capture motion, yields a table far larger than the number of atoms in the universe, and Fridman jokes that you would need to run a universe just to fill it in.

Deep learning steps in by learning the Q-function instead of tabulating it. The same type of network used for digits now takes in a state and produces a Q-value, starting from nothing but the rewards of the simulated game. This is the 2013 DeepMind paper on playing Atari with deep reinforcement learning, which used a vanilla convolutional network on raw pixels and a plain squared-error loss against the Bellman target.

Training compares the predicted Q-value with the value actually obtained and backpropagates the difference, so the agent learns against itself. Fridman is candid that the truth is messier than the hope. There is heavy preprocessing and several tricks, the most important being experience replay: storing past transitions and randomly sampling them so the agent does not fall into a local optimum from learning only its latest, narrow experience.

Fridman walks through Breakout training. After ten minutes the paddle just keeps dying, after two hours on a single GPU it plays at roughly human level, and after four hours it finds the lazy winning strategy of digging a hole through the blocks so the ball gets stuck at the top. He says this might be something you would never figure out yourself.

He asks the audience to appreciate what is happening: the input is just pixels, the same kind of thing humans perceive, and the agent knows nothing about paddles or physics. He calls it a very small example of general-purpose intelligence. The same approach beat human-level performance across a range of Atari games, including Boxing and Pinball, with no per-game customization.

The limits are plain. It has only been shown on Atari, whether it transfers to driving is uncertain, and it needs a simulation to generate ground truth. Rewards often arrive ten, twenty or thirty steps later, which he finds amazing given such simple math. Improvements like the distributed Gorila architecture scale up both simulation and learning, and AlphaGo similarly learned from both expert games and self-play.

Returning to driving, Fridman revisits the open question from the first lecture of whether driving is more like chess or like everyday conversation. For today he assumes chess: an obstacle-avoidance problem where the car picks to move left, right, speed up or slow down. In DeepTraffic the goal is the highest average speed on a seven-lane highway full of cars, and students must build a network that reaches 65 miles per hour or higher.

The world is discretized into a grid, with each car occupying about three blocks. Each cell holds a number, the speed of the car in it, the speed limit of 80 miles per hour for empty cells, and a very large value for the blocks the red agent car occupies. A safety system, similar to adaptive cruise control, blocks actions that would cause collisions or leave the road, and the agent chooses among five actions: left, right, stay, accelerate, slow down.

Students can tune how many lanes to the side the car sees (lane side), how many patches ahead and behind it looks, and the temporal window, which determines the input size, for example 135 inputs. The network is defined with ConvNet.js, written by Andrej Karpathy, as a small fully connected layer with ReLU activations and a regression output over the five actions.

Scoring is the median average speed over ten runs of about 30 simulated minutes each, evaluated server-side. Training runs in Web Workers at around a thousand frames per second, entirely in JavaScript, with no special hardware. Fridman demos it live, starts with a deliberately weak network, trains it, gets 56.56 mph in an evaluation run and submits it to the leaderboard under his own name, daring students to beat it. He notes the code was put on Hacker News, so the links stay hidden for a while.

In closing, he calls AlphaGo the most exciting accomplishment of deep reinforcement learning, given that Go was once considered impossible for machines. The policy network was first trained in a supervised way on expert games, so human ground truth anchored it, and was then improved through self-play. For driving, he suggests, the analogue is learning from the growing pool of recorded driver video and then scaling up in simulation.

He ends with a reminder, using a well-known video of an agent behaving unexpectedly, that you cannot trust your first estimate of a reward function to be safe and productive once an intelligent system operates in the real world. Final questions cover the technical details of what the DeepTraffic visualization shows, which is simply the latest snapshot of the network you trained.