Temporal State and Memory › History as State

The natural response to partial observability is to condition on the observation history itself. This section examines why that fallback is always safe but never practical, and what a usable replacement must preserve.

In Part II, Chapter 1, you met the Markov assumption: the current state is a sufficient statistic for the future. In a Markov decision process, $p(s_{t+1} \mid s_t, a_t)$ captures everything, and no amount of additional history can improve a prediction conditioned on $s_t$. Partially observable settings break this at the level of observations. The environment's underlying state $s_t$ may still be Markovian; the problem is that the agent sees only an observation $o_t \sim p(o_t \mid s_t)$, and the map from states to observations is many-to-one. Many distinct underlying states collapse onto the same observation, and once the collapse happens, the agent cannot tell which of them it is in. Note carefully that the difficulty is not that the world is unpredictable; it is that the agent's view of the world is lossy.

Given a full history $\tau_t = (o_0, a_0, o_1, a_1, \ldots, o_t)$, two facts hold:

1. The history is always enough. Conditioning on $\tau_t$ is never worse than conditioning on $o_t$, because the history contains the current observation. Any quantity of interest, such as $p(o_{t+1} \mid \tau_t)$ or the value $V(\tau_t)$, is well-defined. In a precise sense, history is the universal fallback: when in doubt about whether some information matters for the future, conditioning on history is always safe.
2. The history is usually too much. It grows without bound, most of it is redundant, and downstream models (policies, planners, predictors) cannot consume an ever-growing sequence efficiently. An agent that reprocesses its entire history at every timestep pays a cost that grows linearly with episode length at best, and it spends most of that compute re-deriving conclusions it has already reached.

So the practical design problem is to compute a useful state $b_t$ from history under a finite memory budget. When an exact finite sufficient statistic exists, we would like to recover it. Otherwise, the goal is an approximation that preserves the distinctions relevant to the predictions and decisions we care about. A corridor where only one bit matters is easy; a world where thousands of features of the past can each matter is not. In Part II, Chapter 2 you saw the classical answer for a finite-state POMDP with known transition and observation models: the belief state, a probability distribution over underlying states, updated recursively by Bayesian filtering. That belief is a fixed-dimensional sufficient statistic for optimal control, though it need not be the smallest possible representation. General continuous-state beliefs need not have an exact finite-dimensional parameterization. Here we tackle the learned case: the models are unknown, and a useful history summary must be learned from data. We give up the guarantees of exact Bayesian filtering in exchange for applicability where we cannot write down the transition and observation models.

It is worth asking what information a memory must preserve. Three kinds, with different lifetimes, and the differences among them drive most of the architectural choices in this chapter:

• Cue information. One-time signals (the corridor sign) whose consequences persist. The memory must retain them, unchanged, for as long as they matter. Failure here is silent and total: a forgotten cue is indistinguishable from a cue that never existed, and no amount of clever downstream processing can recover it.
• Integration information. Quantities built up over many steps: accumulated velocity, running averages, elapsed time since an event, total charge drained from a battery. The memory must aggregate. No single observation contains these quantities; they exist only as summaries, and the memory mechanism is the only place they can live.
• Recent-context information. Short-lived but high-bandwidth: the last few frames of a video, the recent trajectory of a joint. The memory must carry this faithfully but can let it decay. What matters is fidelity over the last handful of steps, not persistence.

These three requirements pull in opposite directions. A single scalar hidden state cannot serve all three well. Cue retention wants constancy over time; integration wants accumulation; recent context wants high capacity and fast turnover. A mechanism optimized for one, for example a heavily damped accumulator, is actively bad at another, for example a buffer that must reflect the latest frame before it settles. This tension is why memory architectures end up with multiple compartments, which is the subject of the next two sections. It also connects back to Part III, Chapter 2: the question "which features of history are sufficient?" is the temporal version of the sufficient-state question, and the answer is a set of dynamical roles, not a single snapshot.