Introduction: The Scope and Evolution of Reinforcement Learning

Reinforcement learning (RL) occupies a unique and increasingly central position within the broader landscape of machine learning. At its core, it provides a computational framework for an autonomous agent to learn optimal behavior through direct interaction with a dynamic environment, guided solely by a scalar reward signal. This paradigm, where learning is driven by trial-and-error and the delayed consequences of actions, distinguishes it fundamentally from both supervised learning, which relies on a static dataset of input-output pairs, and unsupervised learning, which seeks to uncover hidden structure in unlabeled data. The RL agent is not a passive recipient of a fixed curriculum; it is an active explorer, a decision-maker whose actions shape the very data it subsequently observes. This chapter establishes the formal and historical bedrock upon which the subsequent exploration of advanced topics—from the rigorous theory of Markov Decision Processes (MDPs) to the groundbreaking architecture of AlphaGo—is built. We will precisely define the canonical agent-environment loop, introduce the essential mathematical formalism, survey the pivotal intellectual milestones that have shaped the field, and articulate the core challenges that continue to drive cutting-edge research.

1.1 The Agent-Environment Interaction Loop: A Formal Definition

The fundamental unit of analysis in reinforcement learning is the interaction loop between an agent and its environment. This loop, depicted in Figure 1.1, is a continuous, sequential process:

```mermaid graph LR A[Agent] -- Action a_t --> E[Environment]; E -- State s_t & Reward r_t --> A; A -- Policy π --> E; ```

At each discrete time step *t*: 1. The agent observes the state of the environment, denoted $s_t \in \mathcal{S}$, where $\mathcal{S}$ is the (potentially vast or continuous) state space. 2. Based on this observation and its internal knowledge, the agent selects an action $a_t \in \mathcal{A}(s_t)$, where $\mathcal{A}(s_t)$ is the set of actions available in state $s_t$. The mapping from states to actions is the agent's policy, denoted $\pi(a|s)$, which is a probability distribution over actions given a state. 3. The environment transitions to a new state $s_{t+1}$ according to its dynamics or transition model, $p(s'|s, a)$. This model encapsulates the probabilistic laws governing the environment. In the most general RL setting, this model is *unknown* to the agent. 4. Simultaneously, the environment emits a scalar reward $r_{t+1} = \mathcal{R}(s, a, s')$, a numerical feedback signal that evaluates the immediate consequence of the action $a_t$ taken in state $s_t$ that led to $s_{t+1}$. 5. The agent receives the new state $s_{t+1}$ and reward $r_{t+1}$, and the cycle repeats.

The agent's sole objective is to maximize the expected return, a cumulative, potentially discounted, sum of future rewards. The most common formalization is the discounted return: $$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$ where $\gamma \in [0, 1]$ is the discount factor. A $\gamma$ close to 0 makes the agent "myopic," valuing immediate reward highly. A $\gamma$ close to 1 makes it "far-sighted," valuing long-term outcomes more equally. The expectation is taken over the stochasticity of the policy and the environment dynamics.

Example 1.1: A Gridworld Navigation Task. Consider a simple 5x5 grid (Figure 1.2). The agent starts in a corner. Each step (N, S, E, W) incurs a small negative reward (e.g., -0.01) to encourage efficiency. Reaching a goal cell yields a large positive reward (+10). Falling into a pit yields a large negative reward (-10). The state is the agent's (x,y) coordinate. The policy $\pi$ defines the probability of moving in each direction from each cell. The optimal policy $\pi^*$ is the one that navigates to the goal while avoiding pits with the highest expected discounted return. The agent must learn this mapping without being given the "correct" path.

```mermaid graph TD subgraph "Agent-Environment Loop" direction LR S1[State s_t] --> P[Policy π]; P --> A[Action a_t]; A --> ENV[Environment]; ENV --> S2[State s_{t+1}]; ENV --> R[Reward r_{t+1}]; S2 --> P; end ```

1.2 Distinguishing Reinforcement Learning from Other Paradigms

The RL problem definition above highlights key differentiators:

• **Vs. Supervised Learning:** Supervised learning operates on an *i.i.d.* (independent and identically distributed) dataset $(x_i, y_i)$. The "label" $y_i$ is the ground truth for input $x_i$. In RL, there is no explicit supervisor providing the correct action for each state. The reward is a *scalar, evaluative* signal, not a *vector, instructive* one. It criticizes the outcome but does not prescribe the action. Furthermore, the agent's actions influence future data (states), violating the i.i.d. assumption and introducing a sequential dependency and temporal credit assignment problem.
• **Vs. Unsupervised Learning:** Unsupervised learning (e.g., clustering, density estimation) aims to discover patterns or representations in data without any reward signal. RL has a clear, scalar objective (maximize return). While representation learning is crucial in RL (e.g., learning state features), it is always in service of the ultimate reward maximization goal.
• **Vs. Evolutionary Algorithms:** Evolutionary methods optimize a population of policies via selection and mutation based on total episode return. They are typically **population-based** and **off-policy** (learning from old, potentially unrelated policies). RL, particularly temporal difference (TD) learning, is typically **trajectory-based** and can learn **on-policy** (updating the policy being executed) or **off-policy** (learning about a target policy from data generated by a different behavior policy). RL's use of value functions and bootstrapping allows for more sample-efficient, online learning from single trajectories.

1.3 Core Terminology and Mathematical Primitives

We now formalize the central concepts that will recur throughout this text.

Policy ($\pi$): The agent's behavior function. A deterministic policy is a mapping $\pi: \mathcal{S} \rightarrow \mathcal{A}$. A stochastic policy $\pi(a|s)$ gives a probability distribution over actions. The optimal policy $\pi^*$ maximizes the expected return from any start state: $\pi^* = \arg\max_\pi \mathbb{E}_\pi[G_t | S_t = s]$.

State Value Function ($V^\pi(s)$): The expected return starting from state $s$ and following policy $\pi$ thereafter: $$V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s] = \mathbb{E}_\pi\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg| S_t = s\right]$$ $V^\pi(s)$ measures the *long-term quality* of being in state $s$ under policy $\pi$.

Action Value Function ($Q^\pi(s, a)$): The expected return starting from state $s$, taking action $a$, and thereafter following policy $\pi$: $$Q^\pi(s, a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a] = \mathbb{E}_\pi\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg| S_t = s, A_t = a\right]$$ $Q^\pi(s, a)$ measures the *long-term quality* of the *state-action pair*.

Optimal Value Functions: The ultimate goal is the optimal state value function $V^*(s) = \max_\pi V^\pi(s)$ and the optimal action value function $Q^*(s, a) = \max_\pi Q^\pi(s, a)$. A policy $\pi^*$ is optimal if it greedily selects actions with respect to $Q^*$: $\pi^*(a|s) = 1$ if $a = \arg\max_{a'} Q^*(s, a')$, and 0 otherwise (ties can be broken arbitrarily).

Bellman Equations: The recursive, self-consistent nature of value functions is captured by the Bellman expectation equations: $$V^\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V^\pi(s') \right]$$ $$Q^\pi(s, a) = \sum_{s',r} p(s',r|s,a) \left[ r + \gamma \sum_{a'} \pi(a