What is Reinforcement Learning?

Every day, we make decisions without explicit instructions. A child touches a hot stove and learns to avoid it. A chess player sacrifices a pawn now for a positional advantage ten moves later. A driver adjusts speed on an unfamiliar road based on feedback from the steering wheel, the curve ahead, and past experience. None of these involve a teacher providing the "correct" answer — instead, we learn by interacting with the world and observing the consequences of our actions. Reinforcement learning formalizes this process: an agent learns a behavior strategy by trial and error, guided only by a scalar reward signal.

This chapter lays the groundwork for everything that follows. We introduce the core abstractions — agent, environment, state, action, reward — and show how they fit together into a mathematical framework.

Learning from Interaction

Supervised learning requires a dataset of input-output pairs: images labeled "cat" or "dog", sentences paired with translations. The learner memorizes patterns from these examples and generalizes to new inputs. This works remarkably well — but it assumes someone already knows the right answers and has taken the time to label them.

Reinforcement learning starts from a fundamentally different premise. There are no labels. Instead, an agent takes actions in an environment and receives rewards — numerical signals indicating how good or bad the outcome was. The agent's goal is to discover, through repeated interaction, a strategy that maximizes the total reward it accumulates over time.

Think of learning to ride a bicycle. No one hands you a dataset of "correct muscle activations for each body position." You get on, wobble, fall, adjust, and gradually develop balance. The reward signal is simple: staying upright is good, falling is bad. But the relationship between your actions (leaning, pedaling, steering) and the outcome (balance or crash) is complex, delayed, and noisy. This is the essence of the RL problem.

Three features distinguish reinforcement learning from other forms of machine learning:

1. No supervisor, only rewards. The agent never sees the "correct" action. It only knows whether what it did led to high or low reward — and even that signal may arrive much later.

2. Sequential decision-making. Actions have consequences that extend beyond the immediate moment. Sacrificing short-term reward for long-term gain is often the right strategy, and the agent must learn when.

3. The agent's actions affect its data. In supervised learning, the training set is fixed. In RL, the data the agent sees depends on the decisions it makes. Explore a different part of the environment, and you encounter different states and rewards. This creates a feedback loop between learning and data collection that has no analogue in supervised or unsupervised learning.

The Agent-Environment Interface

We now formalize the intuition above. The RL framework consists of two entities — an agent and an environment — that interact in discrete time steps $t = 0, 1, 2, \ldots$

At each step $t$:

1. The agent observes the current state $s_t \in \mathcal{S}$.
2. The agent selects an action $a_t \in \mathcal{A}$.
3. The environment transitions to a new state $s_{t+1}$ according to the transition dynamics $P(s_{t+1} \mid s_t, a_t)$.
4. The environment emits a reward $r_{t+1} = R(s_t, a_t)$.

This produces a trajectory — a sequence of states, actions, and rewards:

$$s_0, \; a_0, \; r_1, \; s_1, \; a_1, \; r_2, \; s_2, \; a_2, \; r_3, \; \ldots$$

In words: the agent perceives the world, acts, and receives feedback. Then the world changes — partly because of the agent's action, partly due to its own dynamics — and the cycle repeats. This loop is the atomic unit of reinforcement learning. Everything we build in this handbook — from tabular Q-learning to PPO to AlphaZero — operates within this framework.

Let us pin down each component more precisely.

State space $\mathcal{S}$. The set of all possible situations the agent can encounter. It may be finite (the 64 squares of a chessboard), countably infinite (positions in an unbounded grid), or continuous (joint angles of a robotic arm, $\mathcal{S} \subseteq \mathbb{R}^n$).

Action space $\mathcal{A}$. The set of moves available to the agent. Like states, it can be discrete (left, right, up, down) or continuous (a torque applied to each joint, $\mathcal{A} \subseteq \mathbb{R}^m$). In some formulations, the action space depends on the state: $\mathcal{A}(s)$.

Transition function $P(s' \mid s, a)$. The probability of arriving in state $s'$ given that the agent was in state $s$ and took action $a$. This function encodes the environment's dynamics. The agent typically does not know $P$ — it must learn from experience.

Reward function $R(s, a)$. A scalar signal the environment returns after the agent takes action $a$ in state $s$. Rewards can also depend on the next state: $R(s, a, s')$. The reward is the agent's sole source of feedback about the quality of its behavior.

Discount factor $\gamma \in [0, 1)$. A parameter that controls how much the agent cares about future rewards relative to immediate ones. We return to this below.

Together, these components define a Markov Decision Process (MDP), which we study in depth in the next section. For now, the key property is the Markov assumption: the next state and reward depend only on the current state and action, not on the full history.

$$P(s_{t+1} \mid s_0, a_0, s_1, a_1, \ldots, s_t, a_t) = P(s_{t+1} \mid s_t, a_t)$$

In other words, the state contains all the information the agent needs to make decisions. The past is irrelevant once the present is known. This is a strong assumption, but it makes the problem tractable — and many real-world problems satisfy it or can be reformulated to satisfy it.

Where RL Fits in Machine Learning

Machine learning is often divided into three paradigms. Understanding how they differ clarifies what makes RL unique.

The most important distinction is the last row about data. In supervised and unsupervised learning, the dataset exists before training begins and does not change. In RL, the agent generates its own training data through its actions. This creates a fundamental challenge: the data distribution depends on the current policy, but the policy is exactly what we are trying to improve. As the policy changes, the distribution of visited states shifts — a phenomenon with no parallel in classical machine learning.

This also means that RL faces a problem the other paradigms do not: the exploration-exploitation dilemma. The agent must decide whether to take actions it already knows are good (exploit) or try something new in hopes of discovering something better (explore). We study this problem in depth in the chapter on multi-armed bandits.

Formalizing the Goal

An agent that merely maximizes the next reward is myopic. Consider a chess player who captures an opponent's piece at the cost of losing the queen two moves later — the immediate reward is positive, but the long-term consequence is catastrophic. We need a notion of cumulative, long-term reward.

The return $G_t$ is the total accumulated reward from time step $t$ onward:

$$G_t = r_{t+1} + \gamma \, r_{t+2} + \gamma^2 \, r_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k \, r_{t+k+1}$$

The discount factor $\gamma$ determines the balance between present and future. When $\gamma$ is close to 0, the agent is short-sighted — it cares mostly about the next reward. When $\gamma$ is close to 1, it is far-sighted — it values future rewards almost as much as immediate ones.

Why discount at all? Three reasons:

• Mathematical convenience. Without discounting ($\gamma = 1$), the sum may diverge for infinite-horizon tasks, making the objective ill-defined.
• Uncertainty. The further into the future, the less certain we are about what will happen. Discounting reflects this uncertainty.
• Preference for sooner rewards. All else equal, receiving reward sooner is better. This mirrors economic concepts like the time value of money.

Notice that the return satisfies a recursive relationship:

$$G_t = r_{t+1} + \gamma \, G_{t+1}$$

This simple identity — the return at time $t$ equals the immediate reward plus the discounted return from the next step — is the seed from which the Bellman equations grow. We explore this in the chapter on MDPs and dynamic programming.

Policies

A policy $\pi$ is the agent's strategy: a rule that maps states to actions. It is the central object we want to learn.

A policy can be deterministic — for every state, it prescribes a single action:

$$a = \pi(s)$$

Or it can be stochastic — for every state, it defines a probability distribution over actions:

$$\pi(a \mid s) = P(A_t = a \mid S_t = s)$$

Why would we ever want a stochastic policy? Two reasons. First, in partially observable environments, randomness can be optimal — think of rock-paper-scissors, where any deterministic strategy is exploitable. Second, stochastic policies are easier to optimize with gradient-based methods, as we shall see in the policy gradient chapter.

The goal of RL, stated precisely, is to find a policy $\pi^*$ that maximizes the expected return from every state:

$$\pi^* = \arg\max_\pi \, \mathbb{E}_\pi \left[ G_t \mid S_t = s \right] \quad \text{for all } s \in \mathcal{S}$$

This is the optimal policy. A central result in RL theory (which we prove in the MDP chapter) is that at least one deterministic optimal policy always exists for any finite MDP.

Value Functions

Directly searching over all possible policies is intractable. Instead, we evaluate how good it is to be in a given state (or to take a given action in a given state) under a particular policy. These evaluations are called value functions.

The state-value function $V^\pi(s)$ answers: "If I am in state $s$ and follow policy $\pi$ from now on, what return can I expect?"

$$V^\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t = s \right] = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k \, r_{t+k+1} \; \middle| \; S_t = s \right]$$

The action-value function $Q^\pi(s, a)$ is more specific: "If I am in state $s$, take action $a$, and then follow policy $\pi$, what return can I expect?"

$$Q^\pi(s, a) = \mathbb{E}_\pi \left[ G_t \mid S_t = s, A_t = a \right]$$

These two functions are closely related. If we know $Q^\pi$, we can recover $V^\pi$ by averaging over the policy:

$$V^\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \, Q^\pi(s, a)$$

In plain terms: the value of a state is the average value of the actions we might take there, weighted by how likely we are to take each one.

The optimal value functions $V^*(s)$ and $Q^*(s, a)$ correspond to the best possible policy:

$$V^*(s) = \max_\pi V^\pi(s), \qquad Q^*(s, a) = \max_\pi Q^\pi(s, a)$$

Once we know $Q^*$, finding the optimal policy is trivial — just pick the action with the highest value:

$$\pi^*(s) = \arg\max_{a \in \mathcal{A}} Q^*(s, a)$$

This is why so much of RL reduces to the problem of estimating value functions accurately. The methods differ in how they estimate these values — from exact dynamic programming to deep neural network approximations — but the underlying logic is the same.

The Exploration-Exploitation Dilemma

Imagine you are choosing a restaurant for dinner. You know a place nearby that is reliably good — an 8 out of 10. But there is a new restaurant you have never tried. It might be a 10. It might be a 4. Do you exploit your known option or explore the unknown one?

This is the exploration-exploitation dilemma, and it pervades all of reinforcement learning. An agent that only exploits will converge to a locally good policy but may miss the globally optimal one. An agent that only explores will gather information but never use it. The challenge is to balance the two.

We study this problem through the lens of the multi-armed bandit — a simplified setting that isolates the exploration-exploitation trade-off from the complexities of sequential decision-making. There, we develop principled strategies: $\epsilon$-greedy, upper confidence bounds (UCB), and Thompson sampling. These ideas carry forward into every RL algorithm we encounter later.

What Lies Ahead

This chapter introduced the framework and vocabulary of reinforcement learning — the agent-environment loop, policies, value functions, and the objective of maximizing discounted returns.

The next chapter maps out the landscape of RL algorithms along three axes: model-free vs. model-based, value-based vs. policy-based, and on-policy vs. off-policy. After that, we trace the history of the field from Bellman's equation to RLHF.

From the Introduction section, we move to Value-Based Methods, starting with multi-armed bandits and building up through MDPs, dynamic programming, and deep Q-networks. The notation is consistent throughout — refer back to this chapter whenever you need to check a symbol's meaning.

References

1. Sutton, R. S. & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Book
2. Mnih, V. et al. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529–533. Paper
3. Silver, D. et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484–489. Paper