What is Reinforcement Learning? The Maze as a Metaphor
Imagine an agent—a tiny, digital explorer—placed in the top-left corner of a grid. Its world is a maze: a rectangular lattice of cells, some open, some blocked by walls, with a single goal cell glowing somewhere in the distance. The agent has no map, no instructions, only a simple capacity: at each step, it can move one cell up, down, left, or right. If it bumps into a wall, it stays put. If it reaches the goal, it receives a treasure chest of points—say, +100. Every other move? Perhaps a small penalty, like -1, to encourage efficiency. The agent’s task? To learn, through trial and error, a sequence of actions that maximizes its total score. This is reinforcement learning (RL) in its purest, most intuitive form.
This simple scenario encapsulates the profound core of RL: an autonomous entity learning to make good decisions by interacting with an environment, guided solely by the consequences of its actions. It is not told the “right” move at each moment (as in supervised learning), nor is it left to find hidden structure without guidance (as in unsupervised learning). Instead, it discovers behavior through a continuous loop of state (where am I?), action (what do I do?), reward (how did that feel?), and policy (what should I do next?). The maze is more than a toy problem; it is a metaphor for any sequential decision-making task—from a robot learning to walk, to a chatbot optimizing dialogue, to AlphaGo mastering the game of Go. In this chapter, we will unpack this loop, trace the historical roots of RL, contrast it with other machine learning paradigms, and build a concrete Python implementation that brings the maze to life. By the end, you will not only understand what RL is but also feel its intuitive pull: a general science of goal-directed learning from interaction.
---
The Agent-Environment Interface: A Dance of Interaction
At the heart of RL lies a timeless dance between two protagonists: the agent and the environment. The agent is the learner and decision-maker; the environment is everything outside the agent—the world it inhabits. This relationship is formalized as a continuous loop, often called the agent-environment interface.
1. State (s): At time step *t*, the environment presents the agent with a state *sₜ*. In our grid-world maze, the state is simply the agent’s coordinates, e.g., `(row, column)`. States encapsulate all relevant information the agent can perceive. In more complex settings, a state might be a pixels from a camera (in robotics), the current board configuration (in games), or a patient’s vital signs (in healthcare). A crucial distinction is between fully observable environments, where the state contains all necessary information (like our grid), and partially observable ones, where the agent has limited sensory input (like a robot with a narrow field of view). The Markov property is key: a state is Markov if it contains all history needed to predict the future; in our maze, knowing your current cell is sufficient—you don’t need to remember the path taken to get there.
2. Action (a): Based on the state, the agent selects an action *aₜ* from its set of possible actions, called the action space. In the maze, this is typically discrete: `{UP, DOWN, LEFT, RIGHT}`. In other domains, actions can be continuous (e.g., steering angles for a self-driving car, torque values for a robot arm). The action is the agent’s only means of influencing the environment.
3. Reward (r): The environment responds to the action by transitioning to a new state *sₜ₊₁* and emitting a scalar reward *rₜ₊₁*. The reward is the immediate, numerical feedback signal—the “pleasure” or “pain” associated with the transition. It is the agent’s sole source of information about what is good or bad. In our maze, reaching the goal yields a large positive reward (+100), while each step incurs a small negative reward (-1) to penalize dawdling. Bumping into a wall might yield 0 or a small negative reward. Critically, the reward function *R(s, a, s’)* defines the task’s objective. All learning is directed toward maximizing the cumulative reward over time, often the sum of discounted future rewards: $G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots$, where $\gamma \in [0,1]$ is the discount factor that weighs immediate reward higher than distant reward.
4. Policy (π): The agent’s behavior is governed by its policy—a mapping from states to actions. A deterministic policy $\pi(s)$ directly outputs an action (e.g., “if at (2,3), go RIGHT”). A stochastic policy $\pi(a|s)$ gives a probability distribution over actions (e.g., “at (2,3), go RIGHT with 70% probability, DOWN with 30%”). The policy is the agent’s “brain,” the thing we aim to improve through learning. The ultimate goal is to find an optimal policy $\pi^*$ that maximizes expected cumulative reward from any start state.
This loop—state, action, reward, next state—repeats ad infinitum or until a terminal state is reached (like the goal cell). The agent’s challenge is to infer, from the stream of experiences $(s_t, a_t, r_{t+1}, s_{t+1})$, a policy that yields the highest long-term reward. This is a credit assignment problem: when the agent finally gets the treasure, which of its past actions deserve credit? Which were wasteful? RL algorithms are mechanisms for solving this problem.
---
The Maze as a Metaphor: Why Grid-Worlds?
Before diving into history and formalism, let’s solidify why the maze is such a powerful teaching tool. Grid-worlds are the “hello world” of RL for several reasons:
- **Simplicity and Transparency**: The state space is discrete and small (e.g., a 5x5 grid has only 25 states). Actions are simple and discrete. The reward structure is easy to design and understand. This allows us to focus on core algorithmic ideas without being bogged down by high-dimensional state representations (like images) or complex action spaces.
- **Sequential Decision-Making**: The maze inherently requires planning multiple steps ahead. A suboptimal move might lead to a dead end, forcing backtracking. This captures the **long-term credit assignment** problem central to RL. Unlike a one-shot decision, the value of an action depends on the future trajectory it enables.
- **Exploration vs. Exploitation**: The agent faces a fundamental trade-off. Should it **exploit** a known path that yields moderate reward, or **explore** unknown corridors that might lead to a shortcut? This tension is universal in RL and is vividly illustrated in a maze with unknown topology.
- **Sparse Rewards**: Often, the only positive reward is at the goal. All other states yield zero or small negative reward. This creates a **sparse reward problem**—the agent receives little feedback until the very end, making learning difficult. Real-world tasks (like winning a chess game) share this sparsity.
- **Rich Variants**: Simple grid-worlds can be extended to model complex phenomena: stochastic transitions (slippery floors), partially observable states (fog of war), non-stationary environments (maze walls that move), and multi-agent settings (multiple agents racing). Thus, the maze is a microcosm of the RL universe.
Consider a concrete 4x4 maze (Figure 1.1, described textually). The agent starts at `(0,0)`, the goal is at `(3,3)`. Walls block cells `(1,1)`, `(2,1)`, `(1,2)`. A random policy—choosing actions uniformly—will eventually reach the goal by chance, but it will take many episodes and many futile collisions. The learning task is to discover the shortest path: `(0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (2,3) → (3,3)`. This path is not obvious; it requires seeing that moving right along the top row avoids the central wall cluster. An RL algorithm must assign credit to the early rightward moves when the final reward is obtained, a non-trivial inference.
---
A Brief History: From Psychology to DeepMind
Reinforcement learning d