--- title: What Is Reinforcement Learning? module: Foundations moduleNumber: 1 lessonNumber: 1 order: 101 summary: > Reinforcement learning is learning what to do — how to map situations to actions — so as to maximize a numerical reward signal, discovered by trial and error rather than told. We set up the agent–environment loop, separate it from supervised and unsupervised learning, name the four elements (policy, reward, value, and an optional model), and train a tic-tac-toe player with a temporal-difference value update. topics: [Foundations] sources: - book: Sutton & Barto ref: "Ch. 1 — Introduction; §1.1 Reinforcement Learning" - book: Sutton & Barto ref: "§1.3 Elements of Reinforcement Learning; §1.4 Limitations and Scope" - book: Sutton & Barto ref: "§1.5 An Extended Example: Tic-Tac-Toe" --- 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.[^sb-intro] 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](/reinforcement-learning/foundations/markov-decision-processes). 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. $$ % caption: The agent–environment interaction. At step $t$ the agent sees state % $S_t$, takes action $A_t$; the environment returns reward $R_{t+1}$ and next % state $S_{t+1}$, which the agent sees at the following step. \begin{tikzpicture}[>=stealth, font=\small, blk/.style={draw, thick, minimum width=26mm, minimum height=13mm, align=center}] \definecolor{acc}{HTML}{2348F2} \node[blk, draw=acc, text=acc] (ag) at (0,1.6) {agent}; \node[blk] (env) at (0,-1.6) {environment}; % action down the right side \draw[->, acc, thick] (ag.east) -- ++(2.6,0) |- (env.east) node[pos=0.25, right, font=\footnotesize, text=acc] {action A(t)}; % reward and state back up the left side \draw[->, thick] (env.west) -- ++(-2.6,0) |- (ag.west) node[pos=0.25, left, font=\footnotesize] {reward R(t+1)} node[pos=0.35, left, font=\footnotesize] {state S(t+1)}; \end{tikzpicture} $$ 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.[^sb-scope] > **Definition (Reinforcement learning).** Learning what to do — a mapping from > situations to actions — so as to maximize a numerical reward signal, where the > learner is not told which actions to take but must discover which yield the most > reward by trying them, and where actions may affect not only the immediate > reward but all subsequent situations and rewards. 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.[^sb-para] | Paradigm | Signal it learns from | What it optimizes | Feedback | | --- | --- | --- | --- | | Supervised | labelled examples $(x, y)$ | match the given label | correct answer, per example | | Unsupervised | unlabelled data $x$ | describe hidden structure | none | | Reinforcement | scalar reward $R_t$ from acting | maximize long-run reward | evaluative, often delayed | 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. > **Definition (Exploration–exploitation dilemma).** Neither exploration nor > exploitation can be pursued exclusively without failing at the task. The agent > must try a variety of actions _and_ progressively favor those that appear best; > on a stochastic task each action must be tried enough times to gain a reliable > estimate of its expected reward. 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](/reinforcement-learning/foundations/multi-armed-bandits) 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 $\varepsilon$ 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. $$ % caption: The four elements. The policy chooses actions; the reward signal % defines the goal step by step; the value function estimates long-run reward; % an optional model of the environment supports planning. \begin{tikzpicture}[>=stealth, font=\footnotesize, el/.style={draw, minimum width=32mm, minimum height=12mm, align=center}] \definecolor{acc}{HTML}{2348F2} \node[el, draw=acc, text=acc] (pol) at (0,0) {policy\\(state $\to$ action)}; \node[el] (rew) at (4.4,0) {reward signal\\(the goal)}; \node[el] (val) at (0,-1.9) {value function\\(long-run reward)}; \node[el] (mod) at (4.4,-1.9) {model\\(optional)}; \draw[->, black, thick] (rew) -- (val) node[midway, right, font=\scriptsize, text=black] {predicts}; \draw[->, black, thick] (val) -- (pol) node[midway, left, font=\scriptsize, text=black] {guides}; \end{tikzpicture} $$ ### 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. > **Definition (Policy).** A policy $\pi$ maps each state to a distribution over > actions: $\pi(a \mid s)$ is the probability of taking action $a$ when in state > $s$. A deterministic policy $\pi(s) = a$ is the special case that puts all the > probability on one action. The policy alone determines behavior. ### 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. > **Definition (Reward hypothesis).** That all goals and purposes can be well > thought of as the maximization of the expected value of the cumulative sum of a > received scalar reward signal. If the hypothesis holds, the entire task of > designing a reinforcement learning problem reduces to designing the reward. 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. $$ % caption: Sparse versus shaped reward on a path to a goal. Under sparse reward % (top) every step returns $0$ until a single $+1$ at the goal — honest about the % objective but slow to learn from. Under shaped reward (bottom) each step toward % the goal returns a small positive hint — faster to learn but able to reward the % wrong behavior if the shaping is imperfect. \begin{tikzpicture}[>=stealth, font=\footnotesize, cellbox/.style={draw, minimum size=8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % --- sparse row --- \node[anchor=east, font=\scriptsize] at (-0.6,1.6) {sparse}; \foreach \i/\v in {0/0, 1/0, 2/0, 3/0, 4/0} { \node[cellbox] at (\i*0.9,1.6) {\v}; } \node[cellbox, draw=acc, text=acc] at (4.5,1.6) {+1}; \node[anchor=west, font=\scriptsize, text=black] at (5.2,1.6) {goal}; % --- shaped row --- \node[anchor=east, font=\scriptsize] at (-0.6,0.2) {shaped}; \foreach \i/\v in {0/.1, 1/.2, 2/.3, 3/.5, 4/.7} { \node[cellbox] at (\i*0.9,0.2) {\v}; } \node[cellbox, draw=acc, text=acc] at (4.5,0.2) {+1}; \node[anchor=west, font=\scriptsize, text=black] at (5.2,0.2) {goal}; \end{tikzpicture} $$ ### 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. > **Definition (Value function).** The state-value $v_\pi(s)$ is the expected > return — total future reward, suitably discounted — when starting in state $s$ > and following policy $\pi$ thereafter. The action-value $q_\pi(s, a)$ is the > expected return when starting in $s$, taking action $a$, and following $\pi$ > after that. 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, $$ v_\pi(s) \doteq \mathbb{E}_\pi\!\left[\, \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \;\middle|\; S_t = s \right], \qquad q_\pi(s, a) \doteq \mathbb{E}_\pi\!\left[\, \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \;\middle|\; S_t = s,\, A_t = a \right], $$ where the symbol $\doteq$ reads "equal by definition." (We build these carefully in the [value-functions lesson](/reinforcement-learning/foundations/value-functions-and-optimality); 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](/reinforcement-learning/tabular-methods/planning-and-learning). 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. $$ % caption: Two ways to improve. Evolutionary search perturbs whole policies and % keeps the winners; value-based learning credits individual states visited % during play, using information ignored by the outer loop. \begin{tikzpicture}[>=stealth, font=\footnotesize, b/.style={draw, minimum width=30mm, minimum height=12mm, align=center}, s/.style={circle, draw, minimum size=5mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % --- evolutionary (left) --- \node[b] (pop) at (0,0) {population of\\whole policies}; \node[b] (win) at (0,-2.1) {keep the winners,\\perturb, repeat}; \draw[->, black, thick] (pop) -- (win) node[midway, right, font=\scriptsize, text=black] {f\/inal score only}; \node[font=\footnotesize] at (0,1.15) {evolutionary}; % --- value-based (right) --- \begin{scope}[xshift=6.6cm] \node[s, draw=acc, text=acc] (s1) at (0,0.2) {}; \node[s, draw=acc, text=acc] (s2) at (1.3,-0.6) {}; \node[s, draw=acc, text=acc] (s3) at (2.6,-1.5) {}; \draw[->, acc, thick] (s1) -- (s2); \draw[->, acc, thick] (s2) -- (s3); \draw[->, acc, thick, bend left=45] (s2) to (s1); \draw[->, acc, thick, bend left=45] (s3) to (s2); \node[anchor=west, font=\scriptsize, text=acc] at (0.35,0.2) {value updated}; \node[anchor=west, font=\scriptsize, text=acc] at (1.65,-0.6) {each visited}; \node[anchor=west, font=\scriptsize, text=acc] at (2.95,-1.5) {state}; \node[font=\footnotesize] at (1.1,1.15) {value-based}; \end{scope} \end{tikzpicture} $$ 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. $$ % caption: A sequence of tic-tac-toe moves. Solid lines are moves actually played; % dotted lines are moves considered but not made. Our second move was exploratory % (to a state ranked below its sibling); the red arrows back up each greedy move's % value from the later state to the earlier one. \begin{tikzpicture}[>=stealth, font=\footnotesize, n/.style={circle, fill=black, inner sep=0pt, minimum size=3pt}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % single played chain a -> b -> c -> d -> e -> f -> g (solid black) \node[n, label=right:{a}] (a) at (0,6) {}; \node[n, label=right:{b}] (b) at (0,5) {}; \node[n, label=left:{c}] (c) at (0,4) {}; \node[n, label=right:{d}] (d) at (0,3) {}; \node[n, label=right:{e}] (e) at (0.7,2) {}; \node[n, label=right:{f}] (f) at (0.7,1) {}; \node[n, label=right:{g}] (g) at (1.4,0) {}; \draw[thick] (a) -- (b) -- (c) -- (d) -- (e) -- (f) -- (g); % starred siblings actually considered (dashed) -- placed clear of the chain \node[n] (cs) at (1.4,4) {}; \node[anchor=west, font=\scriptsize] at (1.5,4) {c*}; \node[n] (es) at (-1.0,2) {}; \node[anchor=east, font=\scriptsize] at (-1.1,2) {e*}; \node[n] (gs) at (2.2,-0.3) {}; \node[anchor=west, font=\scriptsize] at (2.3,-0.3) {g*}; \draw[dashed, black] (b) -- (cs); \draw[dashed, black] (d) -- (es); \draw[dashed, black] (f) -- (gs); % fan of unconsidered dotted moves at each of our-move levels \foreach \ang in {210,235,260} \draw[dashed, black] (b) -- ++(\ang:0.9); \foreach \ang in {215,245,320} \draw[dashed, black] (d) -- ++(\ang:0.9); \foreach \ang in {215,255,300} \draw[dashed, black] (f) -- ++(\ang:0.9); % backup arrows (red): value flows from later state up to earlier, bowed right \draw[->, red, thick] (d) to[out=25, in=-25] (b); \draw[->, red, thick] (e) to[out=115, in=-25] (d); \draw[->, red, thick] (g) to[out=115, in=-25] (e); % row labels down the left \node[anchor=east, font=\scriptsize, text=black] at (-1.8,6) {starting position}; \node[anchor=east, font=\scriptsize, text=black] at (-1.8,5) {opponent move}; \node[anchor=east, font=\scriptsize, text=black] at (-1.8,3) {our move}; \end{tikzpicture} $$ 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 $$ V(S_t) \;\leftarrow\; V(S_t) + \alpha \big[\, V(S_{t+1}) - V(S_t) \,\big], $$ 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](/reinforcement-learning/tabular-methods/temporal-difference-learning). 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 $$ V(S_A) = 0.50, \quad V(S_B) = 0.50, \quad V(S_C) = 0.50, \quad V(S_D) = 1.0, $$ 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$, $$ V(S_C) \leftarrow 0.50 + 0.1\,(1.0 - 0.50) = 0.55, $$ 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$, $$ V(S_B) \leftarrow 0.50 + 0.1\,(0.55 - 0.50) = 0.505, $$ and the move into $S_B$ carries a still-smaller nudge to $S_A$, $$ V(S_A) \leftarrow 0.50 + 0.1\,(0.505 - 0.50) = 0.5005. $$ 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. $$ % caption: One temporal-difference backup pass with $\alpha = 0.1$ along a won % line $S_A \to S_B \to S_C \to S_D$. The won state $S_D$ has value $1$; each % earlier state moves a tenth of the way toward its successor's current value, so % the update shrinks as it travels back ($+0.05$, $+0.005$, $+0.0005$). Repeated % play compounds these into the true win probabilities. \begin{tikzpicture}[>=stealth, font=\footnotesize, sb/.style={draw, minimum width=20mm, minimum height=11mm, align=center}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \node[sb] (a) at (0,0) {S\_A\\0.5000}; \node[sb] (b) at (2.7,0) {S\_B\\0.5050}; \node[sb] (c) at (5.4,0) {S\_C\\0.5500}; \node[sb, draw=acc, text=acc] (d) at (8.1,0) {S\_D\\1.0 (won)}; \draw[->, black, thick] (a) -- (b); \draw[->, black, thick] (b) -- (c); \draw[->, black, thick] (c) -- (d); % backup arrows curving back, above \draw[->, red, thick] (d) to[bend right=38] node[above, font=\scriptsize, text=red] {+0.05} (c); \draw[->, red, thick] (c) to[bend right=38] node[above, font=\scriptsize, text=red] {+0.005} (b); \draw[->, red, thick] (b) to[bend right=38] node[above, font=\scriptsize, text=red] {+0.0005} (a); \node[anchor=north, font=\scriptsize, text=black] at (4.0,-1.0) {greedy moves (left to right); value backed up (red, right to left)}; \end{tikzpicture} $$ ### What the example shows The tic-tac-toe player illustrates the whole picture at small scale, and where each piece generalizes. | Feature in the example | The general point | | --- | --- | | Learns by playing, not from a labelled set | emphasis on learning while interacting with an environment | | Sets multi-move traps for a shortsighted opponent | correct behavior accounts for the delayed effects of choices | | No search over future move sequences, no opponent model | the effect of planning without a model, via learned values | | Backs up each visited state's value | credit assigned to individual states, not whole policies | 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](/reinforcement-learning/approximation/on-policy-prediction) 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](/reinforcement-learning/foundations/a-brief-history-of-rl). [^sb-intro]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), Ch. 1 — Introduction; §1.1 Reinforcement Learning: RL as learning what to do to maximize a numerical reward, characterized by trial-and-error search and delayed reward. [^sb-scope]: **Sutton & Barto**, §1.1; §1.4 — Limitations and Scope: the problem formalized as the optimal control of an incompletely-known Markov decision process, capturing sensation, action, and goal. [^sb-para]: **Sutton & Barto**, §1.1 — Reinforcement Learning: RL distinguished from supervised learning (labelled examples) and unsupervised learning (hidden structure) as a third paradigm defined by reward maximization.