The Formal Architecture of Sequential Decision Problems

Sequential decision making constitutes the fundamental paradigm underlying intelligent behavior in dynamic environments. From a robotic vacuum navigating unknown obstacles to the AlphaGo system defeating world champions in Go, the challenge of choosing actions to maximize long-term outcomes is ubiquitous. Reinforcement learning formalizes this challenge as a mathematical optimization problem over time, providing a rigorous framework that abstracts away domain-specific details to reveal core principles. This chapter establishes the formal architecture of sequential decision problems, defining the essential components—agents, environments, states, actions, policies, and reward signals—and introducing the central notion of history. We will articulate the Markovian assumption that underlies most tractable formulations, precisely distinguishing between fully observable settings (Markov decision processes, MDPs) and partially observable settings (partially observable MDPs, POMDPs). The chapter culminates in the canonical problem statement: the optimization of expected cumulative discounted reward. This foundation is indispensable; every algorithm and theory in subsequent chapters rests upon these definitions.

The Agent-Environment Interface

The reinforcement learning paradigm posits a clear separation between a learning agent and its environment. The agent is the entity that learns and makes decisions; the environment comprises everything outside the agent that it cannot directly control. Interaction proceeds in discrete time steps $t = 0, 1, 2, \dots$, forming a closed loop:

1. At time $t$, the agent observes some signal from the environment, typically denoted $O_t$ (observation) or $S_t$ (state). 2. Based on this observation, the agent selects an action $A_t$ according to its internal policy. 3. The environment receives the action and transitions to a new state, emitting a scalar reward $R_{t+1}$ and the next observation $O_{t+1}$ (or state $S_{t+1}$).

This cycle repeats, generating a trajectory of interactions. Formally, we model the interaction as a sequence of random variables defined on a common probability space $(\Omega, \mathcal{F}, P)$:

$$ O_0, A_0, R_1, O_1, A_1, R_2, O_2, A_2, R_3, \dots $$

The environment encapsulates the dynamics—the probabilistic laws governing how states evolve in response to actions and how rewards and observations are generated. The agent encapsulates the policy—the decision-making rule that maps past observations to a distribution over actions. The agent’s sole influence on the environment is through its chosen actions; conversely, the environment’s sole influence on the agent is via the observations and rewards it provides.

This interface is deliberately minimalistic. It does not assume the agent knows the environment’s dynamics; learning often involves estimating these dynamics from experience. Nor does it assume the agent has direct access to the environment’s internal state—only whatever observations are exposed. This abstraction allows the same formalism to model diverse scenarios: a chess engine (agent) playing against a game engine (environment), a recommendation system (agent) interacting with users (environment), or a mobile robot (agent) navigating a physical world (environment).

Mathematical Specification of the Interface

We denote the observation space by $\mathcal{O}$ and the action space by $\mathcal{A}$. These may be discrete (e.g., $\mathcal{A} = \{\text{up}, \text{down}, \text{left}, \text{right}\}$) or continuous (e.g., $\mathcal{A} = \mathbb{R}^n$ for robotic joint torques). The reward is a real-valued random variable $R_t \in \mathbb{R}$. The joint distribution of the interaction sequence is determined by the initial distribution $P(o_0)$ and the transition kernel:

$$ P(o_{t+1}, r_{t+1} \mid h_t, a_t) $$

where $h_t = (o_0, a_0, r_1, o_1, a_1, r_2, \dots, o_{t-1}, a_{t-1}, r_t, o_t)$ denotes the history up to time $t$—the complete record of past observations, actions, and rewards. This kernel specifies, given the entire past history and the current action, the probability distribution over the next observation and reward. The environment is thus fully characterized by $P(o_0)$ and $P(o_{t+1}, r_{t+1} \mid h_t, a_t)$.

The agent’s behavior is defined by a policy $\pi$, which is a stochastic mapping from histories to actions: $\pi(a_t \mid h_t)$ gives the probability of selecting action $a_t$ given history $h_t$. A deterministic policy is a special case where $\pi(a \mid h)$ is 1 for a single action and 0 otherwise; we denote it $a = \mu(h)$. The policy may be stationary (independent of time step) or non-stationary; we typically assume stationarity unless stated.

The interaction generates a trajectory (or episode) $\tau = (o_0, a_0, r_1, o_1, a_1, r_2, \dots, o_T, a_T, r_{T+1})$, which may be finite-horizon ($T < \infty$) or infinite-horizon. Many theoretical results assume infinite horizons with discounting (introduced later), but the formalism accommodates both.

Example: A Grid World Agent

Consider a robot navigating a 5×5 grid world. The observation $o_t$ might be the robot’s current coordinates $(x_t, y_t)$. The action space $\mathcal{A} = \{\text{North}, \text{South}, \text{East}, \text{West}\}$. The environment dynamics: attempting to move North from $(x,y)$ results in $(x, y+1)$ with probability 0.8 (success), but with probability 0.1 slips East and 0.1 slips West. A reward of $+10$ is given for reaching the goal cell $(5,5)$; a reward of $-1$ per step encourages speed. This simple setup illustrates the agent-environment loop: the robot (agent) senses its location (observation), picks a direction (action), the world (environment) updates its position stochastically and returns a reward. The history $h_t$ would include the full path taken so far, but as we will see, under appropriate state definitions the process may be Markovian.

History and the Markov Assumption

The history $h_t$ contains all information about past interactions. In principle, an optimal policy could depend on the entire history: $\pi(a_t \mid h_t)$. However, history spaces grow exponentially with $t$, making direct function approximation infeasible. The Markov assumption provides a powerful reduction: it posits that the future is conditionally independent of the past given the present state.

Definition of a State

A state $S_t$ is a function of the history: $S_t = f(h_t)$. The function $f$ is chosen by the modeler. The key property we desire is Markovianity:

$$ P(s_{t+1} \mid s_t, a_t, h_{t-1}) = P(s_{t+1} \mid s_t, a_t) \quad \text{almost surely} $$

That is, given the current state $S_t$ and action $A_t$, the distribution of the next state $S_{t+1}$ does not depend on earlier history. Equivalently, the state $S_t$ is a sufficient statistic of the history for predicting the future. When such a state exists, we say the process is Markov with respect to that state representation.

The Markov property is not automatically true; it depends on how we define the state. In the grid world example, if the state is defined as the robot’s current coordinates, the process is Markov because the transition probabilities depend only on current position and action (the slip probabilities are fixed). But if the world has doors that open and close based on a hidden timer, coordinates alone may not suffice; the state might need to include a clock variable.

History vs. State: A Formal View

Let $\mathcal{H}_t$ denote the space of possible histories up to time $t$. A state function $f: \mathcal{H}_t \to \mathcal{S}$ maps histories to states. The Markov property holds if for any $h_{t-1}, s_t, a_t$:

$$ P(S_{t+1} \in \cdot \mid h_{t-1}, s_t, a_t) = P(S_{t+1} \in \cdot \mid s_t, a_t) $$

where $S_{t+1} = f(h_t, a_t, r_{t+1}, o_{t+1})$. This is a strong requirement. In practice, we often design the state to be M