Name: Mastering Reinforcement Learning: From Mazes to AlphaGo with MDPs, Q-Learning, and Policy Gradients
Author: step-3.5-flash

The Reinforcement Learning Landscape: Agents, Environments, and Rewards

Reinforcement learning (RL) is a computational paradigm concerned with how an autonomous agent ought to take actions in an environment so as to maximize cumulative reward. At its heart, RL is about learning from interaction: an agent perceives the state of its environment, selects actions, and receives feedback in the form of rewards or penalties, gradually improving its decision-making policy through trial and error. This trial-and-error nature distinguishes RL from other major branches of machine learning. Supervised learning relies on a static dataset of input-output pairs, learning to map inputs to known targets. Unsupervised learning seeks to discover hidden patterns or structures within unlabeled data. Reinforcement learning, by contrast, operates in a dynamic, sequential setting where actions influence future states and rewards, and the objective is to learn a behavior that yields the highest long-term return, often under conditions of partial observability and delayed consequences.

The distinction is not merely academic; it defines the very problems each paradigm can address. Supervised learning excels at pattern recognition tasks like image classification or speech translation, where the correct answer is provided in the training data. Unsupervised learning is suited for clustering, dimensionality reduction, or generative modeling, where the goal is to understand the data's inherent structure. Reinforcement learning shines in scenarios requiring sequential decision-making under uncertainty: a robot learning to walk, a chess-playing program discovering winning strategies, a recommendation system adapting to user feedback over time, or a chemical agent optimizing molecular synthesis through experimentation. In each case, the agent must explore its environment, estimate the long-term value of actions, and balance the need to gather new information against the imperative to exploit known good behaviors.

To formalize this intuition, we introduce the core mathematical framework: the Markov Decision Process (MDP). An MDP provides a rigorous model for sequential decision-making problems where outcomes are partly random and partly under the control of a decision maker. Formally, an MDP is defined by a tuple $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma)$, where $\mathcal{S}$ is a set of states, $\mathcal{A}$ is a set of actions, $\mathcal{P}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0,1]$ is the state transition probability function such that $\mathcal{P}(s' | s, a)$ gives the probability of transitioning to state $s'$ after taking action $a$ in state $s$, $\mathcal{R}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$ is the reward function, and $\gamma \in [0,1]$ is the discount factor that weighs immediate versus future rewards. The Markov property assumes that the future is independent of the past given the present state, meaning the transition probabilities depend only on the current state and action, not on the history. This assumption, while not universally true, is a powerful abstraction that makes the problem tractable and forms the foundation for most RL algorithms.

Within this framework, the agent's behavior is governed by a policy, denoted $\pi$. A policy is a mapping from states to probabilities of selecting each possible action: $\pi(a|s)$ gives the probability of taking action $a$ in state $s$. Policies can be deterministic, where $\pi(s)$ directly outputs an action, or stochastic, where they output a probability distribution over actions. The goal of RL is to find an optimal policy $\pi^*$ that maximizes the expected cumulative discounted reward, often called the return. For a given trajectory (or episode) $s_0, a_0, r_1, s_1, a_1, r_2, \dots$, the return at time step $t$ is defined as $G_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}$. The discount factor $\gamma$ serves two purposes: it ensures the return is finite in infinite-horizon problems, and it models the agent's preference for immediate rewards over delayed ones, effectively incorporating a notion of time value akin to financial discounting.

Central to evaluating states or state-action pairs are value functions. The state-value function $V_\pi(s)$ estimates the expected return starting from state $s$ and following policy $\pi$ thereafter: $V_\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$. Similarly, the action-value function $Q_\pi(s,a)$ estimates the expected return after taking action $a$ in state $s$ and then following $\pi$: $Q_\pi(s,a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a]$. The optimal value functions $V^*(s)$ and $Q^*(s,a)$ represent the maximum achievable value under any policy. These functions satisfy fundamental recursive relationships known as the Bellman equations. For the state-value function: $V_\pi(s) = \sum_a \pi(a|s) \sum_{s',r} \mathcal{P}(s',r | s,a) [r + \gamma V_\pi(s')]$. For the optimal state-value function: $V^*(s) = \max_a \sum_{s',r} \mathcal{P}(s',r | s,a) [r + \gamma V^*(s')]$. These equations express that the value of a state equals the expected immediate reward plus the discounted value of the next state, under the policy (or optimal choice). They form the basis for dynamic programming and RL algorithms, providing a recursive decomposition of the value estimation problem.

An episode is a sequence of interactions from an initial state to a terminal state, such as a complete game of chess or a single traversal of a maze. Problems with episodes are called episodic. In contrast, continuing tasks have no predefined endpoint, like a robot performing continuous control or a trading agent operating indefinitely. The horizon refers to the timescale over which we evaluate performance: an infinite horizon assumes the process continues forever, while a finite horizon considers a fixed number of steps. These distinctions influence algorithm design and theoretical guarantees.

To illustrate these abstract concepts, consider a canonical example: a robot navigating a grid-world maze. The environment is a two-dimensional grid of cells, some of which are free (the robot can occupy them) and some are walls (impassable). The robot (agent) starts at a designated cell and must reach a goal cell. At each time step, the agent observes its current grid coordinates (the state $s$), chooses a movement action $a$ from the set {up, down, left, right}, and the environment transitions to a new state according to the dynamics: if the chosen direction leads to a wall, the agent remains in place; otherwise, it moves to the adjacent cell. Upon reaching the goal, the episode terminates. The reward structure might be: $-1$ per step to encourage efficiency, $+10$ for reaching the goal, and $0$ otherwise. This simple setup encapsulates the essence of RL: the agent does not know the maze layout initially (though in this example we assume full observability, i.e., the state is the complete grid position). It must explore the environment, learn which actions lead to progress toward the goal, and eventually discover the shortest path.

style S fill:#e1f5fe style G fill:#c8e6c9 style W fill:#ffcdd2 ```

In this grid-world, the agent faces the classic exploration-exploitation dilemma immediately. Suppose after a few random trials, it discovers a path that leads to the goal: right, right, down. Should it repeatedly follow this known path (exploitation) to collect the goal reward quickly, or should it occasionally try alternative moves, such as going down first, in hopes of finding an even shorter route (exploration)? Pure exploitation risks missing a superior policy; pure exploration wastes steps on suboptimal actions. The optimal strategy balan