The Markov Property

"Tell me where you stand and I will tell you where you are going. Tell me the long road that brought you here and I will yawn: I wrote that road into where you stand. I am the state, and I insist the future forgets the past the moment it knows the present."

A State That Insists the Future Forgets the Past Once It Knows the Present

In Section 22.1 we framed sequential decision making as an agent interacting with an environment in a loop: observe, act, receive a reward, repeat. We left open the question that determines whether that loop is tractable at all: when the agent decides what to do next, what does it need to remember? The naive answer is "everything", the full history $h_t = (s_0, a_0, s_1, a_1, \dots, s_t)$ of observations and actions. That answer is a dead end, because the history grows without bound and no learnable function can be defined over an unbounded, ever-growing input in any stable way. The Markov property is the assumption that turns "remember everything" into "remember only the present state", and this section is devoted to stating it, justifying it, and (most usefully) engineering it when the world does not hand it to us for free.

This is not a new idea in this book, it is a returning one. Part II built an entire edifice (the AR and Markov-chain models of Section 3.1, the state-space and Kalman filtering machinery of Chapter 7) on the premise that a compact latent state can carry forward everything the past says about the future. There the state served prediction; here it serves decision. The continuity is exact: an MDP is a controlled Markov chain, a state-space model with an action input and a reward output, and the sufficient-statistic role of the state is identical. We use the unified notation of Appendix A throughout: $s_t \in \mathcal{S}$ the state, $a_t \in \mathcal{A}$ the action, $r_t$ the reward, $\gamma$ the discount factor.

The four competencies this section installs are these: to write the Markov property as a conditional-independence statement and read it as "the state is a sufficient statistic of history"; to name the five components of the MDP tuple and what each contributes; to take a non-Markov observation stream and design a Markov state from it by augmenting with history or features, recognizing when augmentation cannot save you and you have a POMDP instead; and to distinguish a stationary MDP whose dynamics are fixed from a drifting environment whose dynamics change, the non-stationarity studied in Chapter 20. These are the foundations every algorithm in Part VI silently assumes.

1. The Markov Property: The Future Forgets the Past Given the Present Beginner

A stochastic process over states $s_0, s_1, s_2, \dots$ has the Markov property when the distribution of the next state depends on the past only through the current state. Formally, for every time $t$ and every state $s'$,

In words: once you know $s_t$, knowing $s_{t-1}, s_{t-2}, \dots, s_0$ as well tells you nothing further about $s_{t+1}$. The earlier states are not irrelevant to the future in general; they are irrelevant given the present, because whatever they contributed has already been absorbed into $s_t$. This is a statement of conditional independence: the future $s_{t+1}$ is conditionally independent of the past $(s_{t-1}, \dots, s_0)$ given the present $s_t$, written $s_{t+1} \perp (s_{t-1}, \dots, s_0) \mid s_t$. The same statement extends to the full future trajectory, not just the next step: conditioned on $s_t$, the entire future $(s_{t+1}, s_{t+2}, \dots)$ is independent of the entire past.

In the controlled setting that defines an MDP, the agent also chooses an action $a_t$ at each step, and the property is stated for the action-conditioned transition. The next state and reward depend on the past only through the current state and the action taken there:

This is the version that powers everything downstream. It says the environment's response to an action is a function of the present state and that action alone, never of how the agent arrived at the present state. The decisive consequence is that an optimal action can be chosen from $s_t$ without reference to the trajectory that produced it, which is precisely what makes the value functions and Bellman recursions of Section 22.3 functions of the state rather than functions of the whole history.

It is worth being careful about a common misreading. The Markov property does not claim the process has no memory in the everyday sense, that the past leaves no trace. A river's water level today plainly depends on the rain of the past week. The property claims something subtler: that if the state is chosen well, all of that traced-through influence is encoded in the present state's value, so the past adds nothing once the state is known. The entire practical content of this section is that "if the state is chosen well" is a design obligation, not a gift. Choose the state to be just today's rainfall and the process is not Markov, because last week's rain still predicts tomorrow's level beyond what today's rain reveals. Choose the state to be the full soil-moisture and upstream-flow vector and it can be Markov. Same world, different state, different answer to whether the Markov property holds.

2. The State as a Sufficient Statistic of History Beginner

The cleanest way to understand what the Markov property asks of a state is through the statistical notion of a sufficient statistic. A statistic of the history is sufficient for the future if it captures everything in the history that is predictive of the future, so that conditioning on the statistic makes the future independent of the rest of the history. The Markov property is exactly the assertion that the current state is a sufficient statistic of the entire history for predicting the future:

where $h_t = (s_0, a_0, \dots, s_t)$ is the full history. The right-hand side has compressed $h_t$ down to $s_t$ with no loss of predictive information. A Markov state is therefore a lossless compression of history with respect to the future: you may discard everything except $s_t$ and forecast the future exactly as well as if you had kept the whole record.

Reading the state as a sufficient statistic immediately reframes the practitioner's job. You are not "given" a Markov state by the environment; you are choosing a representation, and the question for any candidate representation $s_t = \phi(h_t)$ is a single sharp one: does $\phi(h_t)$ retain everything in $h_t$ that predicts the future? If yes, your representation is Markov and every Part VI algorithm applies directly. If no, your representation has thrown away predictive information, the process looks non-Markov through its lens, and you must either enrich $\phi$ until sufficiency is restored (subsection 3) or accept partial observability and carry a belief (Chapter 23). The sufficient-statistic view turns a vague modelling worry into a concrete checklist item: name what predicts the future, then verify your state contains it.

3. The MDP Tuple: $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ Intermediate

A Markov decision process packages the Markov dynamics, the agent's choices, and the objective into five components, the tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$. Each piece earns its place:

• $\mathcal{S}$, the state space: the set of states the environment can be in. By the Markov property, each $s \in \mathcal{S}$ is a sufficient statistic of history.
• $\mathcal{A}$, the action space: the set of actions available to the agent (possibly state-dependent, $\mathcal{A}(s)$).
• $P$, the transition kernel: $P(s' \mid s, a) = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)$, the controlled dynamics, the probability of landing in $s'$ after taking $a$ in $s$.
• $R$, the reward function: $R(s, a)$ (or $R(s, a, s')$), the expected immediate reward for taking $a$ in $s$, the scalar the agent seeks to accumulate.
• $\gamma \in [0, 1)$, the discount factor: how much a reward one step later is worth relative to now, which makes the infinite-horizon return finite and well defined.

The transition kernel is a proper conditional distribution: for every state-action pair it places a probability over next states that sums to one, $\sum_{s'} P(s' \mid s, a) = 1$. The agent's objective is to choose actions so as to maximize the expected discounted return, the discounted sum of future rewards:

The discount $\gamma$ does double duty: it encodes a genuine preference for sooner rewards, and it guarantees convergence of the infinite sum whenever rewards are bounded, since $\sum_k \gamma^k = 1/(1-\gamma) < \infty$. The Markov property is what makes the whole tuple coherent: because $P$ and $R$ depend only on the current state and action, the return $G_t$ from a state can be analyzed without reference to how the state was reached, and that is the foundation on which Section 22.3 builds policies, value functions, and the Bellman equations.

The single arrow carrying only $s_{t+1}$ back to the agent, never the history, is the picture of the Markov property in action. If the environment needed the agent's past to determine the next state, that arrow would have to carry the whole trajectory, and the clean loop would collapse. The discipline of subsection 4 below is precisely the discipline of making sure that single arrow really does carry enough.

4. State Design: Recovering the Markov Property When Observations Are Not Markov Intermediate

Here is the uncomfortable truth that every practitioner meets. The raw observation an environment hands you is usually not a Markov state. A single video frame does not reveal velocity (you cannot tell which way the ball is moving from one still image); a single sensor reading does not reveal a trend; a single board position in some games hides whose move it is or what castling rights remain. When the observation omits something that predicts the future, the process is non-Markov through that observation, and a memoryless policy that conditions only on the current observation is structurally unable to act well, because it cannot distinguish situations that look identical now but evolve differently next.

State design is the craft of building a Markov state out of non-Markov observations. The dominant technique is augmentation: enlarge the state to include the missing history or derived features until sufficiency is restored. Three moves cover most cases:

• Stack history. Define the state as the last $n$ observations, $s_t = (o_{t-n+1}, \dots, o_t)$. Stacking frames recovers velocity (two frames reveal motion); stacking sensor readings recovers trend. This is the move the worked example and the library wrapper below both use.
• Add derived features. Append quantities the dynamics depend on but the raw observation omits: velocity, elapsed time, a running average, an inventory level, a counter. A single richer vector can replace a long stack when you know which summary the future depends on.
• Carry a recurrent summary. Let a learned hidden state $h_t = f(h_{t-1}, o_t)$ accumulate the relevant history, the RNN-as-state idea, and treat $h_t$ as the state. This is the bridge to Chapter 23 and to the recurrent policies of deep RL.

The foreshadowing deserves to be explicit, because it marks the boundary of this chapter. Augmentation works when the missing information is present somewhere in the recent history, just not in the single latest observation: stacking or featurizing recovers it. Augmentation fails when the relevant variable is never directly observed at all, only ever inferred from a stream of noisy partial clues, the location of a robot that sees only a local sensor, the true health state behind a few vital signs. No finite stack of observations is sufficient then, because the observations themselves do not determine the hidden variable; the best you can do is maintain a probability distribution (a belief) over the hidden state, and that belief, not any observation, becomes the Markov sufficient statistic. That is the subject of Chapter 23 on POMDPs. The art of state design in this section is the art of staying inside the MDP world as long as augmentation can keep you there, and recognizing the moment it cannot.

5. Stationarity: Fixed Dynamics Versus a Drifting World Intermediate

A second assumption rides quietly alongside the Markov property in the standard MDP: stationarity of the dynamics. The transition kernel $P(s' \mid s, a)$ and reward $R(s, a)$ are assumed not to depend on the absolute time $t$, only on the state and action. The world's rules are fixed; take action $a$ in state $s$ today and the distribution of outcomes is the same as it would be a thousand steps from now. This is what licenses learning a single policy and a single value function that are good for all time, rather than a different policy for every timestep.

Stationarity and the Markov property are distinct assumptions and it pays to keep them apart. The Markov property is about which variables the next state depends on (only the present state and action, not the history). Stationarity is about whether that dependence changes over time (it does not). A process can be Markov but non-stationary: the transition rule is a clean function of $(s_t, a_t)$ at each instant, yet that function itself drifts as $t$ grows, so $P_t(s' \mid s, a) \ne P_{t'}(s' \mid s, a)$ for $t \ne t'$. A market microstructure whose volatility regime shifts, a machine whose wear changes its response, a recommender whose users' tastes evolve: each is plausibly Markov given a good state, yet non-stationary because the dynamics themselves move.

The practical line between the two is the line between Part VI and Chapter 20. The standard MDP machinery of this part, value iteration, Q-learning, policy gradients, all assumes a stationary MDP and learns one fixed solution. When the environment genuinely drifts and cannot be re-stationarized by state augmentation, that machinery degrades, and the adaptive, drift-aware methods of Chapter 20 take over. For the rest of Chapter 22 we assume a stationary MDP, with the understanding that "stationary after a well-chosen state augmentation" is the realistic version of that assumption.

6. Worked Example: A Memoryless Policy Fails, History Stacking Saves It Advanced

We now make the whole section executable on the smallest world that exhibits the phenomenon. Consider a one-dimensional corridor where an agent must move in the direction it is already heading. The raw observation is only the agent's position; the agent's velocity (which way it is going) is not observed. Under the position-only observation the process is not Markov, because the same position can be reached while moving left or moving right, and the correct action differs between the two, yet they look identical to a memoryless policy. We will show a position-only policy is provably ambiguous, then stack the last two positions so velocity becomes recoverable, and watch the same policy succeed. Code 22.2.1 builds the environment and demonstrates the ambiguity from scratch.

import numpy as np

# A corridor of positions 0..9. The agent has a hidden "heading" (+1 or -1).
# Each step it moves one cell in its heading; bouncing reverses heading at the walls.
# OBSERVATION given to the agent = position only (heading is hidden).
# REWARD: +1 each step the agent's chosen action matches its true heading, else 0.

class Corridor:
    def __init__(self, n=10, seed=0):
        self.n = n
        self.rng = np.random.default_rng(seed)
    def reset(self):
        self.pos = self.n // 2
        self.heading = self.rng.choice([-1, +1])   # hidden direction of motion
        return self.pos                             # observation = position ONLY
    def step(self, action):                         # action in {-1, +1}: guess heading
        reward = 1.0 if action == self.heading else 0.0
        self.pos += self.heading
        if self.pos <= 0 or self.pos >= self.n - 1: # bounce at a wall, reverse heading
            self.pos = int(np.clip(self.pos, 0, self.n - 1))
            self.heading *= -1
        return self.pos, reward

# A memoryless policy must map a single position to a single action.
# Build the BEST possible such table by majority vote over many visits.
env = Corridor(seed=1)
counts = {p: {-1: 0, +1: 0} for p in range(env.n)}   # position -> heading tally
o = env.reset()
for _ in range(20000):
    counts[o][env.heading] += 1                      # record true heading at this position
    o, _ = env.step(env.heading)                     # drive with the true heading to explore
# Each position is visited under BOTH headings: the position alone cannot disambiguate.
ambiguous = sum(1 for p in counts if counts[p][-1] > 0 and counts[p][+1] > 0)
print("positions seen under both headings:", ambiguous, "of", env.n)
best_table = {p: (+1 if counts[p][+1] >= counts[p][-1] else -1) for p in counts}
print("best memoryless table:", best_table)

positions seen under both headings: 8 of 10
best memoryless table: {0: 1, 1: 1, 2: -1, 3: -1, 4: -1, 5: 1, 6: 1, 7: 1, 8: -1, 9: -1}

The diagnostic is unambiguous: position alone is not a sufficient statistic, because it does not determine the heading that drives both the dynamics and the reward. Now we repair the state. Stacking the two most recent positions makes the heading recoverable, because the difference of consecutive positions is the heading. Code 22.2.2 implements the same from-scratch fix: wrap the environment so the state is the pair $(\text{prev}, \text{curr})$, derive a policy on that two-position state, and measure the reward.

# Repair: STACK the last two positions. state = (prev_pos, curr_pos).
# Then heading = curr_pos - prev_pos (away from walls), so the state is Markov.

def run_policy(stacked, steps=20000, seed=7):
    env = Corridor(seed=seed)
    o = env.reset(); prev = o
    total = 0.0
    for _ in range(steps):
        if stacked:
            vel = np.sign(o - prev) or env.heading   # velocity from the two-frame stack
            action = int(vel)                        # act on the RECOVERED heading
        else:
            action = best_table[o]                   # memoryless: act on position alone
        prev = o
        o, r = env.step(action)
        total += r
    return total / steps                             # average reward per step (max 1.0)

print("memoryless (position only) avg reward:", round(run_policy(False), 3))
print("stacked   (two positions) avg reward:", round(run_policy(True), 3))

memoryless (position only) avg reward: 0.514
stacked   (two positions) avg reward: 0.998

Read the three results together. Code 22.2.1 proved the observation was non-Markov by exhibiting the same position under both headings; Code 22.2.2 restored the Markov property by stacking two positions and recovered near-optimal reward with the identical policy; the numeric example showed the Markov factorization that makes such a clean state tractable in the first place. The lesson that generalizes far beyond this toy: when an RL agent underperforms, suspect the state before the algorithm.

import gymnasium as gym
from gymnasium.wrappers import FrameStackObservation

base = gym.make("CartPole-v1")               # single-step observations
env = FrameStackObservation(base, stack_size=4)  # state = last 4 observations, Markov-ified
obs, _ = env.reset()
print(obs.shape)                             # (4, 4): four stacked observations

(4, 4)