Chapter 1 — the reinforcement learning problem.

Chapter 1 sets up the whole book. Reinforcement learning is learning what to do — mapping situations to actions — to maximize a numerical reward, discovered by trial and error with possibly delayed consequences. This page walks every idea: why RL is a third paradigm distinct from supervised and unsupervised learning, the central exploration–exploitation tension, the four elements (policy, reward signal, value function, model), the limits of the framework, and the tic-tac-toe example that quietly previews temporal-difference learning. Maps to lecture CS1.

RL is three things at once

The first thing to untangle: "reinforcement learning" names three different things, and the book is careful about which it means.

• A problem — the problem of an agent learning to behave well through interaction with an environment to achieve a goal. This is the most fundamental meaning.
• A class of solution methods — algorithms that work well on that problem (value methods, policy methods, and so on).
• A field of study — the research area built around the problem and its methods.

Keeping these apart avoids confusion later: when we say a method "is RL," we mean it tackles the RL problem, not that it uses a particular trick. The defining characteristic is the problem, not the algorithm.

What reinforcement learning is

RL is 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. Instead it must discover which actions yield the most reward by trying them out. This is the essence: no instructor hands you the right answer; you find it by experimenting and observing outcomes.

Two features run through everything and distinguish RL from all other kinds of learning:

1. Trial-and-error search — the agent is not told the correct action; it must try actions and judge them by the reward they produce.
2. Delayed reward — an action may not pay off immediately. Its consequences, including future rewards, can unfold many steps later. The agent must learn to sacrifice immediate reward for greater long-term reward.

Goal-directed learning from interaction

RL is, more than any other approach, goal-directed learning from interaction. The agent senses the state of its environment, takes actions that affect that state, and pursues a goal expressed through reward. Three threads are always present: sensation (perceiving the state), action (affecting the environment), and goal (something to maximize). Any method that omits one of these is not addressing the full RL problem.

This is also a very natural model of learning. A baby waving its arms has no teacher, but it has a direct sensorimotor connection to its environment and learns about cause and effect, about consequences, and about what to do to achieve goals. RL formalizes exactly this kind of learning.

Why RL is not supervised learning

It is tempting to lump RL with supervised learning, but they are fundamentally different. Supervised learning learns from a training set of labelled examples provided by a knowledgeable supervisor — each example says "in this situation, the correct output is this." Its goal is to generalize so the system responds correctly to situations not in the training set.

That is exactly the kind of feedback RL does not have. In an interactive problem it is often impractical to obtain examples of correct behaviour that are both correct and representative of every situation the agent will face. In uncharted territory — where learning is most useful — an agent must be able to learn from its own experience. Supervised learning tells you the right answer; RL only tells you, via reward, how good the answer you tried was. This difference between instructive feedback (here is the correct action) and evaluative feedback (here is a score for the action you took) is the heart of the matter, and Chapter 2 studies it in isolation.

Why RL is not unsupervised learning

RL is also not unsupervised learning. Unsupervised learning finds structure hidden in collections of unlabelled data — clusters, patterns, lower-dimensional representations. That can be useful inside an RL agent, but it does not address the RL problem, because uncovering structure is not the same as maximizing a reward signal. RL is trying to maximize a reward, not to find hidden structure. This is why the book treats RL as a third machine-learning paradigm, alongside supervised and unsupervised learning, not a special case of either.

Paradigm	Feedback	Goal	Data
Supervised	Instructive — the correct label	Generalize to new inputs	Labelled examples
Unsupervised	None	Find hidden structure	Unlabelled data
Reinforcement	Evaluative — a reward score	Maximize cumulative reward	Experience from interaction

The exploration–exploitation dilemma

One challenge is unique to RL and appears nowhere in supervised or unsupervised learning: the trade-off between exploration and exploitation. To get a lot of reward, an agent must prefer actions it has tried before and found to be rewarding — it must exploit what it already knows. But to discover such actions in the first place, it must try actions it has not selected before — it must explore.

The dilemma is that neither exploration nor exploitation can be pursued exclusively without failing. Pure exploitation locks onto whatever looked best early, even if something better was never tried. Pure exploration gathers knowledge but never cashes it in for reward. The agent must try a variety of actions and progressively favour those that appear best, balancing the two over time. On a stochastic task each action must be tried many times to gain a reliable estimate of its expected reward. Mathematicians have studied this dilemma intensely for decades, and it remains unresolved in general — Chapter 2 gives the practical first answers (\(\varepsilon\)-greedy, optimistic initial values, UCB).

The four elements of an RL system

Beyond the agent and the environment, four sub-elements make up an RL system. The next four sections take them one at a time, because the rest of the book is essentially the study of how to represent and learn these objects.

Element 1 — the policy

A policy defines the learning agent's way of behaving at a given time. Roughly, it is a mapping from perceived states of the environment to actions to be taken in those states. It corresponds to what in psychology would be called a set of stimulus–response rules or associations. The policy is the core of an RL agent in the sense that it alone is sufficient to determine behaviour. In general policies may be stochastic, specifying probabilities for each action, written \(\pi(a\mid s)\). Everything the agent learns is, in the end, in service of a better policy.

Element 2 — the reward signal

A reward signal defines the goal of the RL problem. On each time step the environment sends the agent a single number, the reward. The agent's sole objective is to maximize the total reward it receives over the long run. The reward signal thus defines what the good and bad events are for the agent — it is the immediate, defining feature of the problem. Rewards 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 biological terms, reward signals are analogous to the experiences of pleasure and pain. Importantly, the reward signal is generated by the environment, not by the agent — the agent cannot simply choose to reward itself.

Element 3 — the value function (and why value ≠ reward)

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 those states.

The distinction is subtle and crucial: a state might yield a low immediate reward but still have a high value because it is regularly followed by other high-reward states — and vice versa. By analogy, rewards are like immediate pleasure (if high) or pain (if low), whereas values correspond to a more refined and farsighted judgement of how pleased or displeased we will be that our environment is in a particular state.

Element 4 — the model (optional)

The fourth and final element, present in some systems, is a model of the environment. A model mimics the behaviour of the environment, or more generally allows inferences about how the environment will behave: given a state and an action, the model predicts 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.

• Model-based methods use models and planning.
• Model-free methods are explicitly trial-and-error learners — viewed as almost the opposite of planning.

Modern RL spans the full spectrum from low-level trial-and-error learning to high-level, deliberative planning. (Bandits, DP, and Monte Carlo — the mid-sem topics — sit at different points on this spectrum: bandits and MC are model-free; DP assumes a perfect model.)

Limitations and scope

The book is candid about the framework's edges. Most of RL is structured around estimating value functions, but this is not strictly necessary — evolutionary methods (genetic algorithms, simulated annealing, and other optimization methods) can solve RL problems without ever estimating value functions, by applying many static policies, each interacting over an extended period, and carrying forward the policies that earn the most reward. These methods are effective when the policy space is small or can be structured well, or when much time is available to search. But they ignore much of the useful structure of the RL problem: they do not use the fact that the policy is a function from states to actions, and they do not notice which states an individual passed through or which actions it selected. Value-function methods exploit exactly that structure, which is why the book focuses on them.

The framework also relies on a notion of state — the information available to the agent about its environment — which we mostly take as given here. How state is constructed from sensations is a deep question the book largely sets aside in the early chapters.

Extended example — tic-tac-toe

Chapter 1 closes with a concrete example that shows RL's distinctive features and previews the methods to come: learning to play tic-tac-toe against an imperfect opponent. Classical approaches fall short — a "minimax" game-theory solution assumes a particular way the opponent plays, and classical optimization for sequential decision problems (like dynamic programming) needs a complete specification of the opponent, including the probabilities with which the opponent makes each move. So consider an RL approach using a value function.

Set up a table of numbers, one for each possible state of the board. Each number is the latest estimate of the probability of winning from that state — this is the state's value, and the whole table is the learned value function. State A is better than state B if our current estimate of the probability of winning from A is higher than from B.

Initialize: states with three X's in a row have value 1 (we have won); states with three O's in a row, or that are filled, have value 0 (we cannot win); all other states start at 0.5 (a guess of a 50% chance of winning).

Playing and learning

We then play many games against the opponent. To select moves we examine the states that would result from each possible move and look up their current values. Most of the time we move greedily, selecting the move that leads to the state of greatest value — the highest estimated probability of winning (exploitation). Occasionally, however, 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.

The learning rule — a taste of temporal difference

While playing, we change the values of the states we find ourselves in, trying to make them more accurate estimates of the probability of winning. To do this we back up the value of the state after each greedy move to the state before the move, nudging the earlier estimate toward the later one:

Here \(S_t\) is the state before the greedy move, \(S_{t+1}\) the state after it, \(\alpha\) is a small positive step-size (learning rate), and the bracket \([\,V(S_{t+1}) - V(S_t)\,]\) is the difference between the two estimates. This update rule is an example of a temporal-difference (TD) learning method, so called because its changes are based on a difference between estimates at two successive times. It quietly previews the central learning mechanism of the whole field — and it is exactly the same shape as the incremental update you will meet again in bandits (Chapter 2) and the Bellman backups in DP (Chapter 4).

What tic-tac-toe teaches

The little example illustrates the differences between RL and other methods, and the features that recur throughout the book:

• Learning while interacting with an environment, here an opponent — no separate training phase.
• A clear goal, and behaviour that must account for delayed effects of choices: a move's value depends on moves that will follow it.
• Bootstrapping: the agent improves each estimate using other learned estimates (the value of the next state), without waiting for the final outcome. Learning a guess from a guess is what makes TD methods efficient.
• No model required of the opponent: the method learned to play well by interaction alone, despite never being told the opponent's strategy. (It can also benefit from a model if one is available — RL is not opposed to planning.)
• Exploration matters: the random exploratory moves are what let the agent discover and correct its estimates for states it would otherwise avoid.

The generality of the idea

Although tic-tac-toe has a small, finite state set, RL is not limited to such cases. When the state space is vast or even infinite, the table of values is replaced by a function approximator — for instance an artificial neural network — that generalizes from states the agent has visited to states it has not. This is precisely where "deep" reinforcement learning enters: deep neural networks become the value function (or the policy), letting the same ideas scale to images, games, and robots. The mid-sem stays in the tabular world to build intuition; the function-approximation machinery is layered on later.

Lecture map & how to revise this chapter

Idea	Where it returns
Evaluative vs instructive feedback; explore/exploit	Chapter 2 (bandits)
State, action, reward, policy, value formalized	Chapter 3 (MDPs)
Planning with a model	Chapter 4 (DP)
Learning value from experience	Chapter 5 (Monte Carlo)
The TD update \(V\leftarrow V+\alpha[\cdot]\)	Post-mid-sem (TD learning)

References & next

• Chapter 2 — Multi-armed Bandits → · explore/exploit, in isolation
• CS1 — Slides Explained · the lecture version
• Sutton & Barto — RL: An Introduction (2e), free PDF · Chapter 1