Image: Dietmar Rabich, Wikimedia Commons, CC BY-SA 4.0
A learner that is told only how well it did, and only later, needs its own mathematics. This unit builds it from the agent-environment loop and the Markov decision process to the Bellman equations, runs value iteration and Q-learning by hand on a 4 by 4 gridworld, and shows what the deep Q-network changed so that the same update could learn Atari games from pixels. It ends with policy gradients, Monte Carlo tree search, and the match of March 2016 in which a policy network, a value network, and a search beat Lee Sedol 4 to 1.
Preview: the beginning of the unit
Every learner of the last eight units was handed the right answer. A regression saw the house price, a classifier saw the label, a language model saw the next word. A child learning to ride a bicycle gets nothing of the kind: no one tells it which muscle to move, only whether it is still upright a second later. This unit is about learning from such a signal, a reward that arrives late and says nothing about what should have been done instead. The method has its own mathematics, and in 2016 it produced the program that beat one of the strongest Go players alive, a result the search of Unit 2 could not reach.
1 Agents, rewards, and returns
Reinforcement learning describes a decision maker and its surroundings as two parts that talk to each other in turns (Figure 1). The agent is the part that chooses, and the environment is everything the agent does not control, including the rules of the game and the body of the robot. At each time step \(t\) the agent observes the state\(s_t\) of the environment, chooses an action\(a_t\), and the environment answers with a new state \(s_{t+1}\) and a number \(r_{t+1}\), the reward. The reward carries the index \(t + 1\) because it arrives together with the next state, which is the convention of the standard textbook of the field by Richard Sutton and Andrew Barto. A sequence of steps that ends, such as one game or one attempt to reach a goal, is an episode, and the state in which it ends is called terminal; a task that never ends, such as balancing a pole, is a continuing task.
Figure 1. The agent-environment loop. The agent sees the state \(s_t\), chooses the action \(a_t\), and the environment answers with the reward \(r_{t+1}\) and the next state \(s_{t+1}\), on which the agent acts in turn.
The reward is the only teaching signal: \(+1\) for a win and \(0\) otherwise in a game, paid once at the end, or a small negative number per second until a robot has finished its task. The agent’s aim is to collect as much reward as it can over the whole future, which means that it must sometimes accept a small loss now for a large gain later, and the whole difficulty of the subject lies in the word later. The mathematics that handles it is the Markov decision process, which is the Markov property of Unit 3 with actions and rewards added.
What the agent collects from time \(t\) onward is called the return\(G_t\), and it is a discounted sum of the rewards that follow.
There are three reasons to discount.
The full unit is part of the program
Want to see a complete unit first? Unit 3, Reasoning under Uncertainty, is free to read.