Markov Decision Processes: The Formal Object

Before we can talk about solving a sequential decision problem, learning value functions, running policy gradients, or proving a Bellman operator is a contraction, we need to be precise about the object we are reasoning over. That object is the Markov Decision Process (MDP). It is usually introduced quickly, on the way to the algorithms. This post slows down instead and treats the MDP as a mathematical structure, the way Puterman or a controls textbook would, because almost every subtlety in RL theory (why stationary deterministic policies are enough, why off-policy correction looks the way it does, why the discount factor must be less than one) is already implicit in this formulation.

The payoff for being careful here is large. Once the formal object is nailed down, the rest of RL reads as a sequence of questions about this object: how good is a given policy, which policy is best, and how do we find it without knowing the dynamics.

What an MDP Models

A Markov Decision Process is a mathematical model for sequential decision making under uncertainty. It describes a system that evolves over time, where the evolution depends not only on random effects but also on deliberate actions chosen by a decision maker.

The cleanest way to place the MDP is to compare it to a Markov chain. A Markov chain evolves on its own; you watch it. An MDP generalizes a Markov chain by letting the transition probabilities between states depend on the action selected at each decision epoch. You are no longer a spectator. You steer.

The interaction loop, at each decision epoch, is:

• the system occupies a state;
• an action is selected;
• an immediate reward (or cost) is incurred;
• the system transitions to a new state according to a controlled probability law.

As the process unfolds, the decision maker observes a sequence of rewards. The objective of a sequential decision problem is to choose actions over time so as to optimize a prescribed function of this reward sequence. That single sentence is the whole game; everything below is the apparatus needed to make it precise.

Decision Epochs and Time

Decisions are made at discrete points in time called decision epochs. We index time by

A small but important modeling distinction depends on how much real time elapses between epochs:

• If the time between decision epochs is constant, the model is a Markov Decision Process.
• If the time between decision epochs is random, the model is a Semi-Markov Decision Process.

Here we restrict attention to discrete decision epochs with constant spacing. Continuous-time decision problems exist, but they are typically treated within control theory (think Hamilton-Jacobi-Bellman rather than the discrete Bellman equation). Keeping time discrete is what makes the sums and the dynamic-programming recursions in later posts well behaved.

The State Space

At each decision epoch the system occupies a state that summarizes all relevant information needed for future decision making. We denote the state space by $S$ and, throughout, assume it is finite, $|S| < \infty$. (We reserve $N$ for the horizon, the number of decision epochs.)

The defining feature of a state is worth stating carefully because it is the whole reason the model is tractable: given the current state and the action chosen, the future evolution of the system is conditionally independent of the past. In other words, the state is a sufficient statistic for the future. If your candidate "state" leaks information about the future that is not captured by its current value, it is not really a state, and you have not finished modeling.

Action Sets

When the system is in state $s \in S$, the decision maker chooses an action from a set of feasible actions. We denote the available actions in state $s$ by $A_s$, and the set of all actions in the model by

The key design choice here is that the action set is indexed by the state. This is not just notational tidiness: letting $A_s$ depend on $s$ is how the model encodes physical, logical, or operational constraints. A robot at a joint limit cannot command motion past it; a queue that is empty cannot serve a customer. Those constraints live in $A_s$, not in some external penalty.

Immediate Rewards

If action $a \in A_s$ is chosen when the system is in state $s$ at decision epoch $t$, an immediate reward is received, denoted

The reward depends only on:

• the decision epoch $t$,
• the current state $s$,
• the chosen action $a$,

and not on the past history of the process. This memorylessness mirrors the Markov property on the dynamics: just as the next state depends on the past only through $(s, a)$, so does the reward. Depending on the application, $r_t(s,a)$ may represent profits, utilities, or negative costs; the sign convention is yours to pick, and "maximize reward" and "minimize cost" are the same problem with a flipped sign.

Transition Probabilities and the Markov Property

After choosing action $a \in A_s$ in state $s$ at time $t$, the system transitions to a new state at the next decision epoch. The transition law is the conditional distribution of the next state given the current state and action:

This is the controlled probability law: it is what makes the MDP a chain you drive rather than merely observe. The defining Markov property states that the full conditional collapses to this controlled one-step kernel:

Here $X_u$ denotes the random state and $Y_u$ the random action at epoch $u$. Read this from left to right: even though you condition on the entire trajectory of states and actions so far, the only things that survive on the right are the current state $X_t$ and the current action $Y_t$. The future depends on the past only through where you are now and what you do now. This is precisely the property that will let dynamic programming work: it justifies replacing "reason about all of history" with "reason about the current state," which is the difference between an intractable problem and a tractable one.

The Planning Horizon

The number of decision epochs is called the planning horizon.

• If the horizon $N < \infty$, the model is a finite-horizon MDP.
• If $N = \infty$, the model is an infinite-horizon MDP.

The finite-horizon case has one wrinkle. At the terminal epoch $N$ no action is chosen, because there is no "next" state to influence. Instead, a terminal reward depending only on the final state is received, denoted

This terminal reward is what anchors the backward recursion in finite-horizon dynamic programming: you know the value at the last epoch outright, and you sweep backward from there. Infinite-horizon problems lose this anchor, which is exactly why discounting and fixed-point arguments (the subject of later posts) become necessary.

Assembling the MDP

Collecting the pieces, a finite-horizon Markov Decision Process is completely specified by the tuple

These five objects, the state space, the per-state action sets, the transition kernels, the running rewards, and the terminal reward, define the dynamics, the rewards, and the admissible decisions of the system. Everything else in MDP theory is derived from this tuple. Notice what is not in it: there is no policy yet, and no notion of "optimal." The MDP is the environment; the agent's behavior is a separate object, which we build next.

Decision Rules and Policies

At each decision epoch $t$, the system occupies a state $s_t \in S$, and an action must be selected from the feasible set $A_{s_t}$.

A decision rule specifies how that action is determined at a single epoch $t$. It is the agent's local behavior, designed by the decision maker, governing action selection at that one decision epoch.

A policy stitches these together into a behavior for the whole horizon:

where $d_t$ is the decision rule used at epoch $t$. A policy is the complete prescription; a decision rule is one frame of it. Most of the subtlety in MDP theory is hiding inside the question of what kind of decision rule we allow, so we now classify them carefully.

Two Independent Axes

There are two independent aspects that characterize how a decision rule specifies actions:

1. Information: what does the rule look at? Just the current state, or the entire past?
2. Action specification: does the rule output a single action, or a probability distribution over feasible actions?

The first axis distinguishes Markovian from history-dependent rules. The second distinguishes deterministic from randomized rules. Two binary choices give four classes, and crucially these axes are orthogonal: you can mix and match. Keeping them separate is what makes the later inclusion theorem clean.

Histories and Available Information

To make the "information" axis precise we need the notion of history. The history of the system up to time $t$ is the full record of states and actions seen so far, ending at the current state:

where $s_u$ and $a_u$ are the state and action at epoch $u$. It is often convenient to write the history recursively, by appending the latest action and state:

Let $H_t$ denote the set of all possible histories up to time $t$. It is built up the same way:

Unrolling the recursion gives the explicit product form,

which makes the combinatorial blowup obvious: the space of histories grows like $(|S|\,|A|)^{t-1}$. This explosion is exactly why we hope, eventually, to get away with only looking at the current state. With the history defined, the information axis is simply:

• a rule is Markovian if it depends only on the current state $s_t$;
• a rule is history-dependent if it may depend on the entire history $h_t$.

The Four Classes of Decision Rules

Crossing the two axes gives four classes. We go from the most restrictive to the most general.

Deterministic Markovian (MD)

A deterministic Markovian rule looks only at the current state and returns a single action with certainty:

It is Markovian because it uses only the current state, and deterministic because the action is pinned down once the state is known. Note that the rule may still depend on time through its subscript $t$: the same state can map to different actions at different epochs. This is the class that almost all of practical RL ultimately cares about, a lookup from state to action, and a recurring theme of the theory is showing that this humble class is, under the right criteria, good enough.

Deterministic History-Dependent (HD)

A deterministic history-dependent rule uses the entire history but still commits to a single action:

where $s_t$ is the current state contained in $h_t$. The rule is free to use any aspect of the past, but the action it outputs must be feasible now, i.e. in $A_{s_t}$. The feasibility constraint always attaches to the current state, no matter how much history the rule consumed to reach its decision.

Randomized Markovian (MR)

A randomized Markovian rule looks only at the current state, but outputs a probability distribution over feasible actions:

At state $s_t$ the rule produces a distribution over $A_{s_t}$, and the realized action is sampled from it. Here $\mathcal{P}(A_s)$ is the set of all probability distributions on the finite set $A_s$:

The randomness here is a feature of the rule, deliberately injected by the decision maker, and is conceptually distinct from the randomness already living in the transition kernel $P_t$. This is the same stochastic policy you sample from in policy-gradient methods; it is also what makes exploration and certain game-theoretic equilibria possible, since a deterministic player can sometimes be exploited.

Randomized History-Dependent (HR)

The most general class uses the full history and outputs a distribution over feasible actions:

This is the broadest class of decision rules considered in finite-state, discrete-time MDP theory. Everything else is a special case. If a good policy exists at all, it exists somewhere inside HR; the entire art is then showing you never actually need this much generality.

Deterministic Rules as a Special Case of Randomized

The two axes are not fully symmetric: deterministic is a degenerate special case of randomized. A deterministic Markovian rule $d_t$ corresponds to the point-mass distribution

and an analogous representation holds in the history-dependent case. This is why we can write inclusions among the classes rather than treating them as four disjoint boxes: collapsing a distribution onto a single point recovers determinism.

Classification Summary

The four classes, by their two-letter codes:

• MD: Markovian and deterministic,
• MR: Markovian and randomized,
• HD: history-dependent and deterministic,
• HR: history-dependent and randomized.

Let $D_t^{(K)}$ denote the set of all decision rules at epoch $t$ in class $K \in \{\mathrm{MD}, \mathrm{MR}, \mathrm{HD}, \mathrm{HR}\}$. We call $D_t^{(K)}$ a decision rule set. This sets up the question that organizes the entire theory.

The Fundamental Question of MDP Theory

With four classes of decision rules ranging from a simple state-to-action lookup (MD) to a randomized function of the entire past (HR), the natural question is whether all that generality is ever needed:

For a given optimality criterion, under what conditions is it sufficient to restrict attention to deterministic Markovian decision rules?

This is not idle. The HR class is astronomically large, the history space $H_t$ grows exponentially in $t$, while the MD class is a finite lookup table. If we can prove that an optimal MD rule always exists, we have reduced an intractable search over policies-that-remember-everything to a tractable search over policies-that-look-at-the-current-state. A large fraction of classical MDP theory exists to answer exactly this question, and for the standard expected-total-reward and discounted criteria the answer is a reassuring "yes, MD suffices."

Policies, Formally

A policy (also called a contingency plan, plan, or strategy) specifies which decision rule is used at every decision epoch. Intuitively, a policy is a complete prescription for action selection under all possible future evolutions of the system, whether those evolutions are described by states alone (Markovian rules) or by full histories (history-dependent rules). It tells you what to do in every contingency before the process even starts.

Formally,

where $d_t \in D_t^{(K)}$ for each epoch $t$ and $K \in \{\mathrm{MD}, \mathrm{MR}, \mathrm{HD}, \mathrm{HR}\}$ is the class of decision rules being used. The set of all policies of class $K$ is the product of the per-epoch decision rule sets:

The key observation is that the class of a policy is entirely inherited from the class of its decision rules. There is nothing more to a policy's classification than the kind of rules it is made of.

Stationary Policies

A policy is stationary if the same decision rule is used at every epoch:

so that

often abbreviated $d^\infty$, or just $d$ when context is clear. Stationarity means the action-selection mechanism does not explicitly depend on time: the same rule is applied whenever the system visits a given state, regardless of when that visit happens. Intuitively, this makes sense in the infinite-horizon setting, where there is no special "end" to steer toward; the problem looks the same from every epoch, so an optimal response should too. Stationary policies accordingly play a fundamental role in infinite-horizon MDP theory.

Stationary Markovian Randomized Policies as Matrices

Consider a stationary Markovian randomized rule

which assigns to each state a distribution over its feasible actions. Because both $S$ and $A$ are finite, this rule has a clean linear-algebraic representation as a matrix

The matrix satisfies three properties:

• $d(s, a) \ge 0$ for all $s \in S$ and $a \in A$;
• $d(s, a) = 0$ for all $a \notin A_s$ (you cannot put mass on an infeasible action);
• for each $s \in S$, $\displaystyle \sum_{a \in A_s} d(s, a) = 1$.

Each row of $D$ is a state, and that row is a probability distribution over the actions feasible in that state. Hence $D$ is row-stochastic; we call it the decision matrix of the policy. This representation is more than bookkeeping: composing $D$ with the transition kernel collapses the controlled MDP into an ordinary Markov chain over states, which is precisely the move that makes policy evaluation a linear-algebra problem in later posts.

Stationary Markovian Deterministic Policies

A stationary Markovian deterministic policy is the degenerate special case where each state's distribution is a point mass. For each $s \in S$ the policy selects a single action $a = d(s) \in A_s$ with certainty, so the decision matrix satisfies

Each row of $D$ then has exactly one entry equal to $1$ and the rest equal to $0$: $D$ is a $0/1$ row-stochastic matrix, one chosen action per state. Such policies are sometimes called pure policies. We write $\Pi^{\mathrm{SD}}$ for the set of stationary deterministic policies and $\Pi^{\mathrm{SR}}$ for the stationary randomized ones.

The Hierarchy of Policy Classes

All these classes are related by inclusion, and laying them out makes the structure of the whole theory visible. Adding generality, time-dependence, history, or randomization, only ever enlarges the set of policies:

and along the deterministic branch,

Read the chains outward: randomized history-dependent policies ($\Pi^{\mathrm{HR}}$) are the most general, sitting at the top of both, while stationary deterministic policies ($\Pi^{\mathrm{SD}}$) are the most restrictive, sitting at the bottom of both. Every other class lives in between.

This picture frames the central theme we keep returning to. The optimum, if it exists, certainly lives in the big set $\Pi^{\mathrm{HR}}$. The deep and useful results of MDP theory show that, for the standard optimality criteria, the optimum can already be found in the small, structured set $\Pi^{\mathrm{SD}}$, a single fixed lookup table from states to actions. That collapse from "remember everything and randomize" down to "a fixed deterministic map" is what makes dynamic programming, value iteration, and ultimately reinforcement learning possible. The next posts make "optimality criterion" precise and prove the collapse.