Markov and Partially Observable Decision Processes › When the Markov Assumption Fails

This section examines how real environments violate the assumptions we just made, why those violations are dangerous, and what conceptual repairs exist. The T-maze experiment later in the chapter measures one such failure precisely.

The Markov property is a statement about a representation, not about the world. The physical world is arguably Markovian at the level of microscopic physics, but the representations available to an agent almost never are. Cameras see surfaces, not velocities; software agents inherit databases, not causal mechanisms. Between the full physical state and whatever the agent records lies an abstraction, and abstractions lose information. The common representation-induced failures fall into a handful of recurring patterns:

• Sensor aliasing: two distinct situations produce identical observations. Our delivery robot at either end of a symmetric corridor sees the same walls. Anything built only from momentary sensations is blind to the difference, however consequential it may be.
• Latent physical quantities: variables that matter but are not directly sensed, such as the charge left in a battery, the contents of a closed drawer, or whether a door is locked. These variables influence outcomes while hiding from measurement.
• Observation delays: the reading available at time $t$ describes an earlier state, so the current observation alone omits the intervening evolution. Timestamping and stacking delayed observations can restore sufficiency when the delay is known.
• Exogenous processes: parts of the environment the agent does not model, such as other people moving through the office, inject state changes the agent's $s_t$ cannot explain. To the agent these events look like irreducible noise, though from a richer viewpoint they are perfectly predictable.
• Deliberate abstraction: compressed or learned state representations merge situations for the sake of tractability, silently destroying distinctions that matter for control. Dimensionality reduction is safe only when the discarded directions carry no decision-relevant information, which is rarely verifiable for free.

The consequence of these representation failures is the same: the agent's apparent state becomes an unreliable basis for prediction and control. Predictions conditioned on $s_t$ are systematically biased, because the omitted history carried real information. Note the word systematically: these errors do not average out like sampling noise, because they repeat in exactly the same direction whenever the same hidden context recurs. Worse for decision making, the optimal action can depend on the missing information. In an aliased corridor whose two ends hide a goal and a hazard, no fixed reaction to the current observation can be safe; the right move depends on which end you are actually at, and only your history distinguishes the two.

Two principal formal repairs restore a Markov state, and mature systems often combine them. The first is to enrich the state: engineer or learn features that restore sufficiency, which is the business of Sufficient State and State Abstraction in Part III. The second is to infer the missing information from history: maintain an explicit probability distribution over what the true state might be, and treat that distribution as the effective state. Enrichment pushes the ambiguity backward into sensing; inference pulls it forward into estimation. History-dependent recurrent policies and robust policies can sometimes act effectively without an explicit calibrated belief, but they do not by themselves prove that the chosen state is Markov. The second formal repair is the subject of the next section and, in full generality, of the next chapter on Bayesian filtering.

A separate assumption can fail even when the representation is sufficient: nonstationarity. As tires wear or other agents adapt, yesterday's transition kernel no longer applies. Adding time, wear state, or regime variables can convert predictable drift into a larger stationary model; changes that cannot be represented this way call for online or adaptive identification rather than belief filtering over a fixed hidden state.