The Markov Ladder

What Makes a State a State

The previous chapter left “maximize expected cumulative reward” not yet well-posed, and named the missing piece: a structural assumption about states. This chapter supplies it, and then builds the standard environment model of reinforcement learning on top of it in three rungs.

Start with the assumption itself. Before any environment model can be built, “state” needs a precise meaning. Not every summary of the past deserves to be called a state; the Markov property is the condition that decides which ones do.

DefinitionMarkov Property

A state $s_t$ is Markov if, conditioned on $s_t$, the future is independent of the entire past history:

$$P(s_{t+1} \mid s_t, s_{t-1}, \dots, s_0) = P(s_{t+1} \mid s_t)$$

When actions are involved, the same statement conditions on the action as well:

$$P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots) = P(s_{t+1} \mid s_t, a_t)$$

Plainly: given the current state, the future is conditionally independent of the past.

RemarkState as a Sufficient Statistic

This is exactly the notion of a sufficient statistic from classical statistics, applied to time instead of to a sample. A sufficient statistic for a parameter is a summary of data that loses no information relevant to inferring that parameter. Everything else in the raw data is noise once you have it. A Markov state is a sufficient statistic for the future: it is a summary of history that loses no information relevant to predicting what happens next. This is also, not coincidentally, the same idea that lets physics write down first-order differential equations for dynamical systems. Position and momentum are a Markov state for classical mechanics precisely because they screen off the system’s entire history from its future evolution. “Find a state” and “find a sufficient statistic for the future” are the same problem wearing different clothes.

What It Costs to Do Without

The definition says what the Markov property asserts, and the remark above says what it means. Neither says why anyone would assume it. The usual answer, that it makes the mathematics tractable, undersells the situation: without it, the model is not merely inconvenient to work with, it is not representable and not learnable at all. That claim can be made exact by counting.

PropositionThe Cost of Conditioning on Full History

Let the state space be finite with $|S| = n$, and fix a horizon $T$. A transition model that conditions on the entire history requires

$$\sum_{t=0}^{T-1} n^{t+1}(n-1) = n^{T+1} - n$$

free parameters. A transition model that assumes the Markov property requires $n(n-1)$, independent of $T$.

Proof

At time $t$, the history $(s_0, s_1, \dots, s_t)$ ranges over $n^{t+1}$ distinct values. Each one indexes its own distribution over the $n$ possible next states, and a distribution over $n$ outcomes has $n-1$ free parameters, since the probabilities are constrained to sum to one. Time $t$ therefore contributes $n^{t+1}(n-1)$ parameters. Summing over the $T$ transitions and evaluating the geometric series $\sum_{t=0}^{T-1} n^{t+1} = n(n^T-1)/(n-1)$ for $n > 1$,

$$\sum_{t=0}^{T-1} n^{t+1}(n-1) = (n-1)\cdot\frac{n(n^{T}-1)}{n-1} = n^{T+1} - n.$$

Note these are $T$ genuinely different tables: the histories have different lengths at different $t$, so nothing forces the model at one timestep to share parameters with another.

Under the Markov property, $P(s_{t+1} \mid s_t, \dots, s_0) = P(s_{t+1} \mid s_t)$ for every $t$, so all $T$ tables collapse onto a single $n \times n$ stochastic matrix. It has $n$ rows, each a distribution over $n$ outcomes, hence $n(n-1)$ free parameters, and $T$ has left the expression entirely.

The gap this opens is not a constant factor. Take a $10 \times 10$ grid world, so $n = 100$, with episodes of $T = 100$ steps, which is a small problem by any standard:

Conditioning on	Free parameters	Grid world, $n=100$, $T=100$
The entire history	$n^{T+1} - n$	$\approx 10^{202}$
The last $k$ states	$n^{k}(n-1)$	$\approx 10^{2k+2}$
The last state only (Markov)	$n(n-1)$	$9{,}900$

The full-history model needs on the order of $10^{202}$ numbers. The observable universe contains roughly $10^{80}$ atoms. The request is not expensive, it is not a request that can be addressed by any physical amount of memory, and the Markov model answers the same question with $9{,}900$ numbers, which fits comfortably in a cache line’s worth of pages.

The Deeper Problem Is Statistical, Not Storage

Storage is the easier objection to state and the less serious one. Suppose memory were free. The parameters would still have to be estimated from data, and here the full-history model fails in a way no hardware can rescue.

To estimate $P(\cdot \mid h)$ for a history $h$ by counting frequencies, the learner must visit $h$ many times. But within a single trajectory, each history prefix $(s_0,\dots,s_t)$ occurs exactly once, by construction: a trajectory passes through each of its own prefixes one time. So visits to a given length-$t$ history can only be accumulated across trajectories, and there are $n^{t+1}$ histories competing for them. Seeing each length-$T$ history even once, let alone often enough to estimate a distribution conditioned on it, requires on the order of $n^{T}$ trajectories.

The Markov property changes what the data is pooled over. Every visit to state $s$, at any timestep, in any trajectory, whatever came before it, is evidence about the same row $P(\cdot \mid s)$. The requirement collapses from “visit this exact history repeatedly” to “visit this state repeatedly,” and the latter is satisfied constantly by ordinary interaction. This is why the Markov property is an enabling assumption rather than a convenience: it is the thing that makes the transition model estimable from a finite amount of experience.

RemarkThe Assumption Has a Dial, and the Dial Has a Price

Full history and last-state-only are the two extremes of a spectrum. An order-$k$ Markov model conditions on the last $k$ states, costing $n^{k}(n-1)$ parameters, and recovers the ordinary Markov property at $k=1$. The table above prices the dial: on the grid world, $k=1$ costs $9{,}900$ parameters, $k=2$ costs $990{,}000$, $k=3$ costs about $10^{8}$, and $k=4$ is already past $10^{10}$. Every additional remembered step multiplies the model by another factor of $n$.

This is the bill for the history-augmentation fixes named at the end of this section. Frame stacking is exactly an order-$k$ model, and the reason it stacks four frames rather than four hundred is visible in that geometric growth, not in any deep principle.

RemarkWhat Function Approximation Does and Does Not Fix

The counting above assumes the model is stored explicitly, as a table indexed by history. Replacing the table with a function approximator changes the storage arithmetic: a network mapping a history to a next-state distribution has whatever parameter count its architecture has, not $n^{T+1}$.

It does not repeal the statistical argument. The approximator still has to learn the mapping from data, and the data still contains each long history at most once per trajectory. What function approximation actually buys is generalization across histories: an assumption, implicit in the architecture, that similar histories have similar futures. That is not an escape from the problem in this section. It is a different structural assumption doing the same job the Markov property does here, chosen for the same reason, and it should be recognized as an assumption rather than mistaken for their absence.

Being Markov is not automatic. It is a property the state representation either has or lacks, and getting it right matters:

Why the State Must Be Informative

A Markov state must contain everything task-relevant needed to predict the next-state distribution, the immediate reward, and, once actions exist, the consequences of every available action. If the state representation omits important history, two identical-looking states may in fact have different futures. Value functions and policies learned from such an insufficient state can be wrong in a structural sense: the agent is solving a partially observed problem while its algorithms assume a fully observed one.

RemarkWhen the Markov Property Fails

If the current observation is not Markov, common fixes include augmenting the state with history, frame stacking, an RNN or other hidden state, learning an explicit belief state, or reformulating the problem as a POMDP (partially observable MDP). The deeper issue is never just that computation becomes large. It is that the state representation is structurally insufficient, so whatever value function or policy gets learned from it may not even be well-defined for the true underlying process.

Everything from here on assumes the property holds. The three rungs below are what can be built once it does, added one ingredient at a time, because each addition changes what questions the model is capable of asking.

Rung One: State Transition Alone

The simplest object satisfying the Markov property is a system with a state space and a rule for moving between states, and nothing else.

DefinitionMarkov Process

A Markov process is a system that moves randomly between states while satisfying the Markov property. It is written as the pair

$$(S, P)$$

where $S$ is the state space and $P$ is the transition probability, $P(s' \mid s)$: if the current state is $s$, the system moves to state $s'$ with probability $P(s' \mid s)$.

There is no agent here, and no reward. The world simply evolves on its own, according to $P$, and nothing in the model asks whether any particular state is good or bad. It only describes how states change over time. In compressed form: MP = state transition, and nothing else.

Rung Two: Adding a Notion of Good

The first rung of structure to add above a bare Markov process is a scalar judgment of outcomes (a reward) together with a way to aggregate rewards over an unboundedly long future.

DefinitionMarkov Reward Process

A Markov reward process is a Markov process with reward and discounting added:

$$(S, P, R, \gamma)$$

where $R$ is the reward function and $\gamma \in [0,1]$ is the discount factor. In compressed form: MRP = MP + reward + discount.

Having reward is what finally lets the model ask a question a bare Markov process cannot: starting from state $s$, how much long-term reward should we expect? Answering that precisely requires two more pieces of machinery, the discounted return and the value function, which are substantial enough to deserve their own chapter. For now, the important structural fact is narrower: an MRP still has no agent action. The system transitions according to $P(s' \mid s)$, exactly as in a bare Markov process; reward is commentary added on top of a transition process that nothing is steering.

Rung Three: Adding Control

The final rung is the one that turns a passively evolving, scored system into something an agent can actually act inside of.

DefinitionMarkov Decision Process

A Markov decision process is a Markov reward process with actions added:

$$(S, A, P, R, \gamma)$$

where $A$ is the action space. In compressed form: MDP = MRP + action.

Adding $A$ changes the transition and reward functions themselves, not just their interpretation. Where a Markov process or Markov reward process transitions according to $P(s' \mid s)$, a Markov decision process transitions according to

$$P(s' \mid s, a)$$

and reward is typically written $R(s,a)$ or $R(s,a,s')$ rather than $R(s)$. The future is no longer just the world evolving by itself with a running score attached; it is shaped by which action the agent chooses at every step.

That change has an immediate consequence, and it is the reason this rung is not merely the previous one with an extra letter in the tuple.

PropositionActions Force a Second Value Function

Once actions exist, a state’s value alone is no longer enough to compare actions against each other. Two value functions are needed: the state-value function $V^\pi(s)$, asking starting in state $s$ and following policy $\pi$, what long-term return should we expect?, and the action-value function $Q^\pi(s,a)$, asking starting in state $s$, first taking action $a$, and then following $\pi$, what long-term return should we expect?

This split between $V^\pi$ and $Q^\pi$, and the recursive Bellman equations that relate them to each other and to reward, is what the next chapter is about. This one stops at the point where the question becomes precisely askable.

The Ladder, Compressed

$$\underbrace{(S,P)}_{\text{MP: state transition}} \ \xrightarrow{\ +\,\text{reward},\ \gamma\ }\ \underbrace{(S,P,R,\gamma)}_{\text{MRP: state transition + reward}} \ \xrightarrow{\ +\,\text{action}\ }\ \underbrace{(S,A,P,R,\gamma)}_{\text{MDP: state transition + reward + action}}$$

Model	State transitions	Reward	Action
Markov process (MP)	yes, $P(s' \mid s)$	no	no
Markov reward process (MRP)	yes, $P(s' \mid s)$	yes, $R$, discounted by $\gamma$	no
Markov decision process (MDP)	yes, $P(s' \mid s,a)$	yes, $R(s,a)$	yes, $A$

Read as plain language: an MP is a world that moves by itself. An MRP is a world that moves by itself, where each step also carries a score. An MDP is a world where an agent chooses actions, the world responds, and each step still carries a score. Reinforcement learning, in essentially all of its classical formulations, is the study of what to do once you are standing at the top of this ladder.

The ladder is also worth remembering downward, not just upward. Later chapters repeatedly collapse an MDP back down a rung on purpose: fixing a policy $\pi$ and averaging the action out turns an MDP back into the MRP it induces, which is precisely the trick that makes policy evaluation an already-solved problem rather than a new one.

References

• Datawhale Easy RL, Chapter 2