The Reinforcement Learning Paradigm: From Mazes to Intelligent Agents

Consider a robot dropped into an unfamiliar maze. Its goal is to find the exit as quickly as possible. It has no map, no instructions, and no supervisor to tell it “turn left here.” Instead, it must *explore*—trying different corridors, encountering dead ends, and occasionally stumbling upon the exit. Each wrong turn yields no reward; finding the exit delivers a positive reward. Over many trials, the robot learns which actions in which situations lead to the reward. This simple scenario encapsulates the essence of reinforcement learning (RL): an *agent* learning to behave optimally through sequential interaction with an *environment*, guided solely by *rewards*. Unlike supervised learning, where a model is trained on a static dataset of input-output pairs, or unsupervised learning, which seeks hidden structure in data, RL is about *learning by doing*. The agent’s actions shape its future inputs, creating a closed loop of experience and improvement. This chapter establishes the foundational paradigm of RL through the intuitive lens of maze navigation. We will define its core components—agents, environments, states, actions, rewards, and policies—and contrast RL with other machine learning paradigms via the central exploration–exploitation trade-off. Using a gridworld example, we will formalize the agent–environment interaction loop, discuss the historical context that birthed the field, survey key applications from robotics to games, and set the stage for the rigorous mathematical formulation via Markov decision processes (MDPs). A Python implementation of a simple gridworld agent will ground these concepts in executable code. By the end, you will see how the abstract principles of RL emerge from this concrete, maze-navigation narrative.

---

The Core Components: Building Blocks of an RL System

At its heart, any RL problem can be described by five fundamental elements: the agent, the environment, the state $s$, the action $a$, and the reward $r$. The policy $\pi$ is the agent’s behavior function, mapping states to actions. Let’s dissect each component through our maze analogy.

• **Agent**: The learner or decision-maker. In the maze, this is the robot. It perceives the environment (the maze layout) and takes actions (moving north, south, east, west). The agent’s objective is to maximize cumulative reward over time.

• **Environment**: Everything outside the agent that it interacts with. The maze walls, corridors, and exit constitute the environment. The environment responds to the agent’s actions, transitioning from one *state* to another and emitting *rewards*. It is generally assumed to be stationary (its dynamics do not change arbitrarily), though we will later consider non-stationary cases.

• **State** $s$: A representation of the environment’s current configuration. In a simple gridworld, the state could be the agent’s coordinates $(x, y)$. More generally, a state encapsulates all information relevant to future decision-making. A key assumption in the standard RL formalism (the *Markov property*) is that the state contains enough information to predict the next state and reward given the current action, without needing the full history. That is, $P(s_{t+1}, r_t | s_t, a_t)$ is sufficient. In our maze, knowing the current cell is enough to determine the outcome of moving north (e.g., you’ll either hit a wall or move to an adjacent cell), without needing to remember the path taken to get there.

• **Action** $a$: The set of possible moves the agent can take. In the gridworld, the action space $\mathcal{A}$ might be $\{\text{up}, \text{down}, \text{left}, \text{right}\}$. Actions are chosen by the agent according to its policy. The environment’s dynamics determine the next state $s'$ and reward $r$ as a result of $(s, a)$.

• **Reward** $r$: A scalar feedback signal from the environment at each time step. It is the sole criterion guiding the agent. In the maze, $r = +1$ for reaching the exit, $r = 0$ for each step, and perhaps $r = -1$ for hitting a wall (penalty). The agent’s goal is to maximize the *expected return* $G_t$, which is typically the discounted sum of future rewards:

$$ 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 short-sighted (myopic), caring only about immediate rewards. A $\gamma$ close to 1 makes it far-sighted, valuing long-term cumulative reward. The discount factor also ensures the return is finite in infinite-horizon problems and can be interpreted as the probability of the task continuing at each step.

• **Policy** $\pi$: The agent’s strategy. It is a mapping from states to a probability distribution over actions: $\pi(a|s) = \mathbb{P}[A_t = a | S_t = s]$. A deterministic policy is a special case where $\pi(s)$ directly outputs an action. The policy is the entity that gets improved through learning. Initially, it may be random (exploration); eventually, it should become near-optimal, directing the agent to the exit efficiently.

These components form a closed loop: at each time step $t$, the agent observes state $s_t$, selects action $a_t \sim \pi(\cdot|s_t)$, executes it in the environment, which responds with reward $r_t$ and next state $s_{t+1}$. This interaction produces a trajectory (or episode, if the task has a terminal state) $\tau = (s_0, a_0, r_1, s_1, a_1, r_2, \dots)$. The agent’s learning objective is to find a policy $\pi^*$ that maximizes the expected return from any start state: $\pi^* = \arg\max_\pi \mathbb{E}_\pi[G_0]$.

---

Reinforcement Learning vs. Supervised and Unsupervised Learning

Understanding what makes RL distinct requires contrasting it with the other two primary paradigms of machine learning.

Supervised Learning relies on a dataset of labeled examples $\{(x_i, y_i)\}$. The model learns a mapping from inputs $x$ to outputs $y$ by minimizing a loss function (e.g., cross-entropy, mean squared error) between its predictions and the provided labels. The data is *i.i.d.* (independent and identically distributed), and the model does not affect the data distribution. In our maze, a supervised approach would require a pre-recorded dataset of state–action pairs from an expert (e.g., “at cell (2,3), go right”). This is often impractical: expert demonstrations may be unavailable, expensive, or suboptimal. Moreover, supervised learning assumes the test data comes from the same distribution as the training data. In RL, the agent’s actions *change* the distribution of states it experiences (the *data distribution is non-stationary*), breaking the i.i.d. assumption. The agent must therefore learn from its own *interactively collected* data.

Unsupervised Learning works with unlabeled data, seeking to uncover hidden structure—clusters, low-dimensional manifolds, or probability densities. Techniques like k-means clustering or principal component analysis (PCA) do not involve decision-making or reward optimization. They are about *description* or *compression* of data, not *control*. In the maze, an unsupervised algorithm might group similar-looking cells or discover that the maze has a cyclic structure, but it would not learn how to escape.

Reinforcement Learning sits at the intersection of *decision-making* and *learning from experience*. Its key characteristics are:

1. Trial-and-error learning: The agent must try actions to see their consequences. There is no explicit “correct” action provided; only a delayed reward signal evaluates long-term outcomes. 2. Credit assignment: When a reward is finally received (e.g., finding the exit), which of the preceding actions deserve credit? This is the *temporal credit assignment problem*. RL algorithms must propagate reward information back through time to update the policy. 3. Exploration–exploitation trade-off: To maximize reward, the agent must *e