Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Temporal State and Memory › Non-Markov Environments and State Aliasing

Michael BrenndoerferJune 16, 20267 min read

World Models HandbookAll chapters

Part 3 of 12Representing Agents and Worlds

Chapter 16Temporal State and Memory › Non-Markov Environments and State Aliasing

Reading section 7 of 12 · Non-Markov Environments and State Aliasing · 7 minSection 7 of 12 · 7 min

Section 7 of 12 · 7 min read

Temporal State and Memory › Non-Markov Environments and State AliasingOne section · Sections in this chapter7 / 12 ↓

Sections in this chapter12

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

With the mechanisms in hand, we can now state the failure they exist to prevent. This section defines state aliasing precisely, shows how it manifests, and gives practical diagnostics for detecting inadequate memory.

Precisely What Goes WrongLink Copied

Let us now state the aliasing problem with care, because it is the standard diagnostic for memory failures. Assume the environment has an underlying Markov state $s_t$ , and the agent observes $o_t$ through a many-to-one channel. Consider two situations with identical observations:

Aliased situations

Situations $(\tau_t, \tau'_t)$ are aliased for a target when they induce the same current observation, $o_t = o'_t$ , but the history-conditioned target differs. For example, for some action $a$ ,

p(o_{t+1}, r_{t+1} \mid \tau_t, a) \neq p(o_{t+1}, r_{t+1} \mid \tau'_t, a).

They may instead require disjoint optimal actions. An observation-only model must assign both histories the same prediction or action distribution because it receives the same $o_t$ .

The formal definition rewards a close reading. The two histories agree on the observation-conditional and disagree on the history-conditional. That gap is exactly the information the memory is responsible for supplying, and it is also exactly what a stateless model cannot represent, since a stateless model's predictions are a function of $o_t$ alone and therefore identical across the two situations.

Aliasing has different consequences depending on what differs across the aliased situations, and the two cases fail in instructively different ways:

Different futures, same optimal action. The agent may still behave correctly, but a point predictor trained with a mean-seeking loss can average mutually exclusive futures into an infeasible outcome, such as a door halfway between open and closed. Planning on that average can distort values when rewards or dynamics are nonlinear, although affine values preserve expectations. A calibrated distribution can instead represent both unresolved modes.
Disjoint optimal actions. No observation-only reactive policy can select a different unique optimum in both situations. This creates an irreducible performance ceiling for that policy class when both situations occur. Better planning over the same aliased state cannot remove it; a history-dependent representation can.

Whether a given pair of situations is aliased depends on the policy and prediction task as well as the environment. Two corridor positions with identical walls but different door positions are only behaviorally aliased if the agent will eventually act differently there. If every policy under consideration treats the two doors identically, the distinction never matters, and spending memory capacity on it is waste. This is the temporal shadow of the bisimulation-style equivalences you met when we discussed state abstraction in Part III, Chapter 2: two histories are equivalent when they cannot be told apart by any future interaction, and a good memory is precisely a map from histories to a state space where only non-equivalent histories land in different places. The practical corollary is that memory requirements are task-relative: a shorter or cheaper memory may be perfectly sufficient for one controller and fatally inadequate for another operating in the same environment.

Diagnosing Memory FailuresLink Copied

How do you know, in practice, that a model's memory is inadequate? The corridor suggests several complementary checks. None is conclusive alone:

The one-step / long-horizon gap. Compare one-step error with multi-step rollouts or distant outcomes. A large gap is a screening signal, not a measurement of missing information: compounding transition error, rollout distribution shift, stochasticity, and decoder instability can produce the same pattern. Follow it with controlled memory tests.
Conditional uncertainty. A point estimate at the mean of mutually exclusive futures indicates mean-seeking prediction under unresolved uncertainty. A calibrated multimodal distribution can be the correct output of a stateless model that has forgotten which branch occurred. Evidence for disambiguating memory is history-conditioned concentration on the appropriate mode, not multimodality by itself.
Probe the state directly. Train a specified probe on one set of episodes and evaluate it on held-out episodes to predict the hidden cue from $b_t$ . High held-out accuracy shows that the cue is decodable by that probe class; it does not prove every downstream head can use it. Plot accuracy against time since the cue to estimate a task- and threshold-dependent memory horizon.

A concrete decay curve makes the diagnostic vivid. The figure below defines two synthetic curves by modeling probe accuracy as a cue signal with per-step retention rate $g$ : accuracy falls as $0.5 + 0.5 \, g^{\Delta t}$ , where $\Delta t$ is steps since the cue. A protected curve has $g$ near one; a leaking curve has $g$ well below one. The horizontal band is a chosen near-chance threshold for this illustration, not a statistical confidence interval.

In[7]:

Code

import numpy as np

dt = np.arange(0, 51)
retention_protected = (
    0.999  # gate stays open: cue signal survives nearly intact
)
retention_leaking = 0.94  # gates leak: cue signal decays each step

acc_protected = 0.5 + 0.5 * retention_protected ** dt.astype(float)
acc_leaking = 0.5 + 0.5 * retention_leaking ** dt.astype(float)

Out[8]:

Visualization

Two synthetic decay curves of probe accuracy versus steps since cue, one staying high and one entering a shaded near-chance band. — Illustrative probe-accuracy curves defined by 0.5 + 0.5 g^Delta-t. For g = 0.94, the curve enters the chosen 0.5-0.6 near-chance band at about 27 discrete steps; for g = 0.999 it remains high through 50 steps. The threshold is a diagnostic convention, not a universal horizon.

With the chosen 0.6 threshold, the leaking curve enters the shaded band at step 27. That crossing is an illustrative operational horizon, not a property of the retention rate alone; change the probe, threshold, or task and the number changes. Aggregate metrics can still hide this temporal pattern.

This held-out probe test is inexpensive and useful alongside behavioral evaluation; we will return to it in Part XI.

Behavioral ablation. Compare a memory-enabled policy with a reactive policy while matching observations, policy capacity, data, optimization, and compute as closely as possible. The performance gap estimates the benefit of the entire memory-enabled setup under those controls, not memory in isolation, and an empirical reactive baseline is not generally the best possible reactive policy.

Predictive State: Memory Without ReconstructionLink Copied

Before leaving the formal territory, one more classical viewpoint is worth having in your pocket. Predictive state representations (PSRs) define state through predictions of tests: action-observation sequences such as "if I push left, then the light will be green." Two histories with the same sufficient vector of test predictions occupy the same predictive state, regardless of their hidden causes. In a linear PSR, each action-observation pair $(a,o)$ selects a matrix $M_{ao}$ and vector $m_{ao}$ . If $q(h)=p(Q\mid h)$ is the row vector of core-test predictions after history $h$ and the predicted observation probability satisfies $q(h)m_{ao} > 0$ , the normalized update is

q(hao) = \frac{q(h) M_{ao}}{q(h) m_{ao}}.

The numerator is linear in $q(h)$ , while division by the predicted observation probability makes the normalized update linear-fractional rather than linear.

This viewpoint also clarifies modern recurrent predictors. A model trained only on observable prediction targets shares the predictive-state motivation: its hidden vector is useful insofar as it supports those targets, without reconstructing a privileged hidden cause. It is not automatically a classical PSR, because one-step prediction need not produce a sufficient set of controlled multi-step test predictions or the update above. The warning still applies: a representation trained only for selected predictions may omit everything the loss leaves out, which is why controlled probes remain worthwhile.