What Is Reinforcement Learning?

Learning by interacting with our environment is probably the first idea to occur to us when we think about learning. An infant waving its arms has no teacher, but it has a direct sensorimotor connection to its surroundings, and exercising that connection produces a wealth of information about cause and effect, about the consequences of actions, and about what to do to achieve goals. Reinforcement learning is the computational face of that idea: learning what to do — how to map situations to actions — so as to maximize a numerical reward signal.¹

The learner is not told which actions to take. It must discover which actions yield the most reward by trying them. In the most interesting cases an action affects not only the immediate reward but also the next situation and, through that, every subsequent reward. Two features follow, and they are the two most important distinguishing features of the whole subject: trial-and-error search (nobody hands you the right answer) and delayed reward (the payoff for a good choice may arrive much later, through a chain of intervening states).

Learning from interaction

Everything in this lesson comes back to one picture: an agent and an environment passing signals back and forth in a loop. Before the formal names, here is the plain version — you act, the world reacts and hands you a score, you act again. Learning is adjusting how you act so the scores add up.

Formally the problem is the optimal control of an incompletely-known Markov decision process, a formalism we build in full in a later lesson. The idea is simpler than the name. An agent interacts with an environment over a sequence of discrete time steps. At step $t$ the agent observes a state $S_t$, selects an action $A_t$, and one step later the environment responds with a scalar reward $R_{t+1}$ and a new state $S_{t+1}$. That single loop, closed over and over, is the entire setting.

Three requirements make a problem a reinforcement learning problem, and Markov decision processes are meant to capture exactly these three, in their simplest possible forms without trivializing any of them. The agent must be able to sense the state of its environment to some extent; it must be able to take actions that affect that state; and it must have a goal or goals relating to the state of the environment. Sensation, action, goal — any method well suited to solving problems with these three aspects we consider a reinforcement learning method.²

Note that reinforcement learning names three things at once, like many words ending in -ing: a problem (goal-directed learning from interaction), a class of solution methods that work well on it, and the field that studies both. It is convenient to use one name, but essential to keep the three separate — in particular, the distinction between the problem and the methods for solving it is important, and failing to make it is the source of many confusions.

How RL differs from other machine learning

Reinforcement learning is neither of the two paradigms that usually divide machine learning between them. It is a third.

Supervised learning learns from a training set of labelled examples supplied by a knowledgeable external supervisor. Each example is a situation paired with a label — the specification of the correct action for that situation — and the object is to generalize, to respond correctly in situations not present in the training set. This is important, but it is not adequate for learning from interaction. In interactive problems it is often impractical to obtain examples of desired behavior that are both correct and representative of all the situations the agent must act in. In uncharted territory — where one would expect learning to be most useful — an agent must be able to learn from its own experience.

Unsupervised learning is typically about finding structure hidden in collections of unlabelled data. One might be tempted to file reinforcement learning here, since it does not rely on examples of correct behavior. But reinforcement learning is trying to maximize a reward signal, not to find hidden structure. Uncovering structure in an agent's experience can certainly help, but it does not by itself address the reinforcement learning problem of maximizing a reward. Supervised and unsupervised learning do not exhaustively classify the paradigms; reinforcement learning is a third one alongside them.³

The distinction is in the kind of feedback. A supervised label is instructive — it states the right action regardless of what the agent did. A reward is evaluative — it grades the action the agent actually took, and says nothing about whether some other action would have scored higher. That is why RL needs to try alternatives at all.

Exploration versus exploitation

Because the feedback is only evaluative, an agent faces a tension that does not even arise in supervised or unsupervised learning, at least in their purest forms. To obtain a lot of reward, the agent must prefer actions it has tried before and found effective. But to discover such actions in the first place, it has to try actions it has not selected before. The agent has to exploit what it already knows in order to obtain reward, and it also has to explore in order to make better action selections in the future.

The dilemma is that pursuing either exclusively fails. Exploit only, and you lock in the first mediocre action that happened to pay off before you found a better one. Explore only, and you keep sampling actions you already know are bad, never cashing in what you learned. The tension has been studied intensively by mathematicians for decades and remains, in general, unresolved; we take it up concretely in the multi-armed bandit lesson, the simplest setting where it appears in isolation.

For example, suppose a restaurant chooser faces three dishes with true (unknown) mean satisfactions $1.0$, $3.0$, and $2.0$. On the very first three visits the chooser samples each once and, by the luck of the draw, records $1.2$ for dish $1$, $1.5$ for dish $2$, and $2.1$ for dish $3$. A pure exploiter now ranks dish $3$ best and orders it forever, banking a long-run average near $2.0$ and never discovering that dish $2$, the true best, was merely unlucky on its single sample — the $1.5$ it drew sat well below its mean of $3.0$. The exploiter is off by a full point of reward per step, permanently, because it stopped gathering evidence exactly when the evidence was worst. A chooser that instead keeps a small exploration probability $\epsilon$ keeps returning to dish $2$, watches its average climb toward $3.0$ as the samples accumulate, and eventually switches. The cost of that correction is the handful of times it deliberately ordered a dish it believed to be worse. That trade — a bounded exploration cost now against an unbounded exploitation loss later — is the whole dilemma.

The four elements

Beyond the agent and the environment, one can identify four main subelements of a reinforcement learning system: a policy, a reward signal, a value function, and — optionally — a model of the environment.

Policy

A policy defines the agent's way of behaving at a given time. Roughly, it is a mapping from perceived states to the actions to be taken in those states. It corresponds to what psychology would call a set of stimulus–response rules. In some cases the policy is a simple lookup table; in others it involves extensive computation such as a search. The policy is the core of a reinforcement learning agent, in the sense that it alone is sufficient to determine behavior. In general policies may be stochastic, specifying probabilities for each action.

Reward signal

A reward signal defines the goal. On each time step the environment sends the agent a single number, the reward $R_t$, and the agent's sole objective is to maximize the total reward it receives over the long run. The reward signal defines what the good and bad events are for the agent; in a biological system we might think of rewards as analogous to pleasure and pain. Rewards are the immediate, defining features of the problem. They are the primary basis for altering the policy: if an action selected by the policy is followed by low reward, the policy may be changed to select some other action in that situation in the future. In general reward signals may be stochastic functions of the state and the actions taken.

That a single scalar can carry any goal at all is a substantive claim, not an accident of convenience. The reward hypothesis states it outright: that all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal. Everything the agent is meant to accomplish must be expressible as one number to be maximized. A robot learning to walk might get a reward proportional to its forward velocity; a chess agent might get $+1$ for a win, $-1$ for a loss, $0$ otherwise; an escape-from-a-maze agent might get $-1$ on every step, so that maximizing total reward means minimizing time to the exit.

The design is easy to get wrong. The reward must encode what we want achieved, not how we imagine achieving it. A chess agent rewarded for capturing pieces or controlling the center may learn to do exactly those things at the expense of winning; Sutton and Barto's example is that we should reward the agent only for actually winning, not for reaching subgoals we think lead to winning, or it may find a way to achieve the subgoals without the goal. This is the difference between sparse reward (a single signal at the end, hard to learn from but honest about the objective) and shaped reward (frequent hints, easy to learn from but able to mislead). The whole point of the value function, next, is to bridge that gap — to turn a sparse, delayed reward into a dense estimate of long-run desirability that can guide every move.

Value function

Whereas the reward signal indicates what is good in an immediate sense, a value function specifies what is good in the long run. Roughly, the value of a state is the total amount of reward an agent can expect to accumulate over the future, starting from that state. Rewards determine the immediate, intrinsic desirability of environmental states; values indicate the long-term desirability after taking into account the states that are likely to follow and the rewards available in them. A state might yield a low immediate reward but still have high value because it is regularly followed by other states that yield high rewards — or the reverse.

In plain terms: the value of a state is the total reward the agent expects to collect from that state onward. The two formulas below write that sum out. Writing $\gamma \in [0,1]$ for a discount that weights sooner reward above later,

where the symbol $\doteq$ reads equal by definition. (We build these carefully in the value-functions lesson; here only the intuition matters.) Rewards are in a sense primary; values, as predictions of rewards, are secondary. Without rewards there could be no values, and the only purpose of estimating values is to achieve more reward. Yet it is values with which we are most concerned when making decisions. We seek actions that bring about states of highest value, not highest reward, because those actions earn the greatest reward over the long run.

And here is the difficulty. Rewards are basically given directly by the environment, but values must be estimated — and re-estimated — from the sequences of observations an agent makes over its entire lifetime. The most important component of almost every reinforcement learning algorithm we consider is a method for efficiently estimating values. The central role of value estimation is arguably the most important thing that has been learned about reinforcement learning over the last six decades.

Model (optional)

The fourth and final element of some reinforcement learning systems is a model of the environment: something that mimics the environment's behavior, or more generally lets the agent make inferences about how the environment will behave. Given a state and an action, a model might predict the resultant next state and next reward. Models are used for planning — deciding on a course of action by considering possible future situations before they are actually experienced. Methods that use models and planning are called model-based; the simpler model-free methods are explicitly trial-and-error learners, viewed as almost the opposite of planning. We explore systems that learn by trial and error, learn a model, and plan with it all at once in the planning-and-learning lesson. Modern reinforcement learning spans the spectrum from low-level trial-and-error learning to high-level deliberative planning.

Value functions versus evolutionary methods

It is not strictly necessary to estimate value functions to solve a reinforcement learning problem. Evolutionary methods — genetic algorithms, genetic programming, simulated annealing, and other optimization methods — apply many static policies, each interacting over an extended period with a separate copy of the environment. The policies that obtain the most reward, and random variations of them, are carried over to the next generation, and the process repeats. We call these methods evolutionary because their operation is analogous to the way biological evolution produces skilled behavior even though organisms do not learn during their individual lifetimes.

Evolutionary methods can be effective when the policy space is small enough to search, or when a lot of time is available. But they ignore much of the useful structure of the reinforcement learning problem: they do not use the fact that the policy being searched for is a function from states to actions, and they do not notice which states an individual passes through during its life, or which actions it selects. To evaluate a policy an evolutionary method holds it fixed and plays many games; only the final outcome of each game is used, and what happens during the game is ignored. If a player wins, all of its behavior is credited, independently of how specific moves were critical to the win — credit is even given to moves that never occurred.

Value function methods, in contrast, let individual states be evaluated, and so take advantage of information available during the course of play. This is the position we take throughout: value functions are important for efficient search in the space of policies, and the use of value functions is what distinguishes the methods in these notes from evolutionary methods that search policy space directly. We do not cover evolutionary methods on their own — although evolution and learning share many features and naturally work together.

An extended example: tic-tac-toe

To make all of this concrete, consider tic-tac-toe against an imperfect opponent — one whose play is sometimes incorrect and allows us to win. For the moment, count draws and losses as equally bad. How might we build a player that finds the imperfections in its opponent's play and learns to maximize its chances of winning?

Classical techniques fall short. The minimax solution from game theory is not correct here: it assumes a particular (worst-case) way of playing by the opponent, so a minimax player would never reach a game state from which it could lose, even if in fact it always won from that state because of the opponent's mistakes. Classical dynamic programming can compute an optimal solution for any opponent, but requires a complete specification of that opponent as input — the probability with which it makes each move in each state — which we do not have a priori. An evolutionary method would search policy space directly, playing many games to score each candidate policy and hill-climbing toward better ones. It works, but credits only whole policies by their final win rate.

Here is how the problem looks with a value function. We set up a table of numbers, one for each possible state of the game — each number the latest estimate of our probability of winning from that state. We treat this estimate as the state's value, and the whole table is the learned value function. Assuming we always play Xs, states with three Xs in a row have value $1$ (we have already won); states with three Os in a row, or that are filled, have value $0$ (we cannot win); and all other states start at $0.5$, a guess that we have a 50% chance of winning.

We then play many games. To select a move we look at the states that would result from each possible move and read their current values from the table. Most of the time we move greedily, selecting the move that leads to the state of greatest value — the highest estimated probability of winning. Occasionally we select randomly from among the other moves instead. These are exploratory moves, because they cause us to experience states we might otherwise never see.

While we play, we change the values of the states we find ourselves in, trying to make them more accurate estimates of the probability of winning. The idea behind the update is simple: if a move led to a state that looks better than where we started, nudge the starting state's value up a little toward it; if worse, nudge it down. We do not wait for the game to end — each state learns from the one right after it.

To do this we back up the value of a state after each greedy move to the state before the move, as suggested by the red arrows above. More precisely, we move the earlier state's value a fraction of the way toward the later state's value. If $S_t$ is the state before the greedy move and $S_{t+1}$ the state after it, the update to the estimated value $V(S_t)$ is

where $\alpha$ is a small positive fraction called the step-size parameter, which governs the rate of learning. This rule is a temporal-difference learning method, so called because its change is based on a difference, $V(S_{t+1})-V(S_t)$, between estimates at two successive times — each guess nudged toward the next guess. The bracketed term is the TD error, and the method that generalizes it is the subject of the temporal-difference lesson.

Exploratory moves do not trigger a backup: we do not want to learn from a move we made only to look around. Every other move does. If the step-size parameter is reduced properly over time, this method converges, for any fixed opponent, to the true probabilities of winning from each state given optimal play by our player; the moves taken (other than exploratory ones) then become the optimal moves against that imperfect opponent. If instead the step size is kept small but nonzero, the player continues to adapt and plays well even against opponents that slowly change their way of playing.

The backup with real numbers

A numerical run shows what the update rule does. Take $\alpha =0.1$ and suppose four states along one game currently hold the estimates

where $S_D$ is a won position (three Xs in a row, value fixed at $1$) and $S_A\to S_B\to S_C\to S_D$ is the sequence of our-move states in one played game, all greedy. The backups run from the later states to the earlier ones. After the move into $S_D$,

so a state one greedy move from a win climbs toward $1$. The move into $S_C$ then backs its new value up to $S_B$,

and the move into $S_B$ carries a still-smaller nudge to $S_A$,

One game moved $S_C$ by $0.05$, $S_B$ by $0.005$, and $S_A$ by $0.0005$ — the credit decays as it travels back, because each state is dragged only a tenth of the way toward a successor that has itself only just started to move. Play the same line many times and the increments compound: $S_C$ climbs toward its true probability of winning first, then $S_B$ follows it, then $S_A$. Value information propagates backward along the trajectory, one greedy backup per visit, one $\alpha$-fraction at a time. This solves the delayed-reward credit assignment named at the start of the lesson with a value function rather than by reasoning about the whole game.

What the example shows

The tic-tac-toe player illustrates the whole picture at small scale, and where each piece generalizes.

The player achieves the effect of planning and lookahead without searching over sequences of future states, and without a model of the opponent — exactly what a good value function buys. And although tic-tac-toe is a two-person game, reinforcement learning applies just as well to the case of no external adversary, a game against nature; to problems that do not break into separate episodes with reward only at the end; and — with more machinery — to continuous state and action spaces. Tic-tac-toe has a tiny, finite state set, but the same ideas run when the state set is enormous or infinite: Tesauro's backgammon player combined this update rule with an artificial neural network over roughly $10^{20}$ states and reached near the level of the best human players. There the network supplies the ability to generalize from experience — the point at which reinforcement learning most needs function approximation, which later modules take up.

This lesson set up the frame. Its history — where the value backup came from — and its future — the deep reinforcement learning systems built on it — continue in A Brief History of Reinforcement Learning.