Partial Observability: Planning and Recurrent Policies

This builds on Partial Observability: POMDPs and the Belief State, which built the POMDP tuple, showed that the belief state — the posterior over hidden states — is a sufficient statistic that turns a POMDP into an MDP over beliefs, and worked the Bayes-filter update that maintains it.

That reduction says a POMDP is, in principle, just an MDP whose state is a probability distribution. This lesson is about why in principle does so much work: planning over the space of beliefs is computationally intractable, and the belief itself is usually uncomputable because the agent lacks the model. Both push practice toward learning a policy directly from history.

Why exact planning is intractable

The belief-MDP equivalence promised a fully observable problem, but on a continuous simplex. What does its value function look like? For a finite-horizon POMDP, the optimal value function over the belief simplex is piecewise-linear and convex (PWLC).

The reason is that each fixed plan (a conditional strategy for the remaining steps) has a value that is linear in the belief: if the plan earns $\alpha (s)$ starting from hidden state $s$, then starting from belief $b$ it earns ${\sum }_{s}b(s)\alpha (s)=b\cdot \alpha$, a dot product — a linear function of $b$. Each such plan is an alpha-vector $\alpha \in {\mathbb{R}}^{|\mathcal{S}|}$. The optimal value at $b$ is the best plan there, so

the upper envelope of a set $\Gamma$ of linear pieces, a piecewise-linear convex surface. Each alpha-vector dominates over a region of the simplex; the optimal action is read off whichever alpha-vector is on top there.

Convexity has a direct interpretation: the value of certainty (a corner) exceeds the value of uncertainty (an interior mix), and the gap is the value of information — how much resolving the ambiguity is worth. An agent that can pay a small cost to reduce uncertainty (listen again, take a sensing action) moves toward a higher-valued corner.

Worked example: why convexity forces information gathering

For example, return to the tiger: opening the door with the hazard costs $-100$, opening the safe door earns $+10$, and listening costs a small $-1$. Consider two plans, each a single-step alpha-vector giving the value of committing now from each hidden state:

• Plan open-left: value $+10$ if the hazard is on the right ($s_R$), $-100$ if it is on the left ($s_L$). As an alpha-vector over $(s_L,s_R)$ that is ${\alpha }_{\text{left}}=(-100,+10)$.
• Plan open-right: the mirror, ${\alpha }_{\text{right}}=(+10,-100)$.

At the uniform belief $b=(0.5,0.5)$, both plans have value $b\cdot \alpha =0.5\times (-100)+0.5\times 10=-45$. Committing blind is worth $-45$. Now suppose listening once takes the belief to $(0.85,0.15)$ (the worked filter step above). At that belief, open-right is worth $0.85\times 10+0.15\times (-100)=8.5-15=-6.5$, and after paying the $-1$ listen cost the net is $-7.5$ — still negative, but a huge improvement on $-45$. Listen a second time to $(0.97,0.03)$: open-right is worth $0.97\times 10+0.03\times (-100)=9.7-3=6.7$, minus $2$ for two listens gives $+4.7$, now solidly positive. The gap between the $-45$ of acting at the uncertain center and the $+6.7$ of acting at the confident corner is precisely the value of information the convexity of $V^{\ast }$ encodes — and it is what makes the optimal policy listen before it acts, spending the small listen cost to climb from the low-valued middle of the simplex to a high-valued corner.

The difficulty is that the number of alpha-vectors needed can explode. Exact value iteration on a POMDP (the DP backup, restated over the simplex) generates a new set of alpha-vectors each step, and in the worst case that set grows doubly exponentially in the horizon: with $|\mathcal{A}|$ actions and $|\mathcal{O}|$ observations, one backup can turn $|\Gamma |$ vectors into $|\mathcal{A}||\Gamma {|}^{|\mathcal{O}|}$ before pruning. Finite-horizon POMDP planning is PSPACE-hard, and exact solutions are hopeless beyond a handful of states.

Point-based value iteration

The practical escape is to give up on the whole simplex and track value only at a finite set of sampled belief points. Point-based value iteration (PBVI) collects a set of reachable beliefs $B=\{b_1,\dots ,b_m\}$ by simulating the Bayes filter forward under some exploration, then maintains exactly one alpha-vector per point rather than a combinatorial set. Each backup improves the alpha-vector at each sampled belief, and the value at any other belief is read from whichever of those $m$ vectors is highest there.

PBVI and its successors (Perseus, HSVI, SARSOP) made POMDPs with thousands of states solvable by keeping the vector set small and focusing computation on beliefs the agent actually reaches.¹ But they all still require a known model $(T,Z,R)$ and an explicit belief over a discrete state set. Neither applies with pixel observations or an unknown environment; that setting falls to deep RL.

Online POMDP planning by sampling

PBVI computes a policy offline, over the whole reachable belief set, before the agent acts. A different escape from intractability computes only what the agent needs right now: given the current belief, search forward from it for a good next action, act, observe, and re-plan from the updated belief. This online branch scaled POMDPs far past what offline alpha-vector methods reached, and it is the practical state of the art.

These methods drop the belief as an explicit vector and represent it instead by a bag of sampled states (particles), then run Monte Carlo tree search over action-observation histories. POMCP (Partially Observable Monte Carlo Planning) does exactly this: it runs UCT in the belief tree, using a particle filter in place of the exact Bayes update and a black-box simulator in place of the explicit models $T$ and $Z$.² Because it only needs a generative simulator — one you can sample from, not one whose probabilities you can write down — POMCP scaled to POMDPs with $10^{56}$ states, far beyond any alpha-vector method.

DESPOT (Determinized Sparse Partially Observable Tree) tightened this idea by searching a sparse tree under a small set of sampled scenarios (fixed random seeds), which bounds the tree's width and comes with a regret guarantee, making the search both faster and more reliable than plain POMCP on many problems.³ The whole online line shares one commitment with the deep-RL methods that follow: give up the explicit belief vector, and represent the posterior implicitly — as particles here, as a network's hidden state next.

The deep-RL answer: recurrent policies

Deep RL confronts a harder version of the problem. The state set is not a small enumerable list, the models $T$ and $Z$ are unknown, and even writing down a belief is out of reach. But the structural conclusion still holds: the policy must be a function of history, not of the current observation. If we cannot compute the belief, we can learn a network that summarizes history into a hidden vector and treat that vector as the belief-substitute.

A recurrent network does precisely this. A recurrent policy processes the stream of observations one at a time, maintaining a hidden state ${\mathbf{c}}_t$ that it updates with each new observation and reads out into values or actions:

Compare this to the POMDP state-update function $S_{t+1}=u(S_t,A_t,O_{t+1})$ from the frontiers lesson: the RNN's recurrence is a learned state-update $u$, and its hidden vector ${\mathbf{c}}_t$ is a learned, implicit belief. The network is never told to compute a posterior; it learns whatever summary of history makes the value predictable, which is the role the belief plays.

Frame stacking versus recurrence

The original DQN used a cruder fix, and it is the baseline recurrence improves on. Instead of a hidden state, stack the last $k$ observations and feed the concatenation as input: DQN on Atari fed the last four frames so the network could see velocity and direction, which a single frame hides. Frame stacking is a fixed, hand-set memory of length $k$ — a $k$-th-order Markov approximation. It works when the relevant history is short and of known length, and fails the moment a dependency reaches back further than $k$ steps (a door opened twenty frames ago, a card seen at the start of the hand). A recurrent network has, in principle, unbounded memory: its hidden state can carry information arbitrarily far.

DRQN: a recurrent DQN

The first direct demonstration of recurrence in deep RL was DRQN (Deep Recurrent Q-Network), Hausknecht and Stone (2015).⁴ It took DQN and replaced the first fully-connected layer after the convolutional stack with an LSTM. The convolutions encode a single frame; the LSTM integrates that encoding over time into a hidden state, and the Q-head reads the hidden state. DRQN is fed one frame at a time — no frame stacking — so any temporal integration must happen through the recurrence.

Hausknecht and Stone tested the idea by taking Atari partially observable on purpose: they flickered the screen, blanking each frame with probability $0.5$ so the agent saw only half the frames. Standard DQN, which relies on stacked frames, degraded badly under flickering; DRQN, carrying information in its LSTM, held up far better, recovering much of the lost performance because its hidden state bridged the missing frames. On standard (non-flickering) Atari the two were comparable — recurrence is not free when four frames already suffice — but under genuine partial observability the recurrent agent was the more robust.⁴

The training wrinkle is that a recurrent Q-network cannot be updated on isolated, shuffled transitions the way DQN's replay buffer serves them: the LSTM needs a sequence to build up a hidden state. DRQN samples contiguous sequences of experience from replay and unrolls the LSTM over them (backpropagation through time), either from a zero initial hidden state each time or carrying the hidden state across the sequence.

R2D2: recurrence at scale

DRQN showed recurrence works; R2D2 (Recurrent Replay Distributed DQN), Kapturowski et al. (2019), made it work at scale and set a new state of the art on the Atari-57 and DMLab-30 benchmarks.⁵ R2D2 combined the recurrent value network of DRQN with the distributed, prioritized replay of the strong distributional-DQN line, and in doing so had to solve the central difficulty of recurrent replay: what hidden state to use for a sequence sampled from the buffer.

The problem is subtle and it is the paper's main contribution. A sequence stored an hour ago was generated when the network was in a hidden state the current network would never produce — the parameters have since changed. Starting each replayed sequence from a zero hidden state (as DRQN did) is safe but biased: early steps of every sequence are learned from a hidden state that never occurs at evaluation time, a representational mismatch. Storing and replaying the exact hidden state from generation is stale: it was produced by old parameters. R2D2's fix is two-part:

• Store the recurrent state in replay alongside each sequence, so training starts from something realistic rather than zero.
• Burn-in: before computing any loss, unroll the network over the first several steps of the sequence purely to warm up the hidden state, using the stored state as a starting point, and only compute the TD loss on the steps after the burn-in. The warm-up lets the current network re-establish a hidden state consistent with its present parameters before it is asked to learn from one.

With recurrence, burn-in, prioritized distributed replay, and a longer $n$-step return, R2D2 roughly quadrupled the previous best median score on Atari-57 and became the reference recurrent agent. Later general agents build on it directly: Agent57, the first to beat the human benchmark on all $57$ games, uses the R2D2 recurrent-replay design.⁵

Memory beyond the RNN

An RNN's hidden state is one way to compress history, but not the only one, and the frontier has moved past it. Two directions matter.

Attention and transformer memories. A recurrent hidden state must funnel all of history through one fixed vector, and long-range credit assignment through backpropagation-through-time is hard to train. A transformer keeps the past observations around and attends over them directly, so a dependency twenty or two hundred steps back is one attention hop away rather than a signal that must persist through many recurrent updates. Sequence-model agents (the Decision Transformer line and transformer-based memory architectures) replace the RNN's recurrence with self-attention over the observation-action history, trading the RNN's constant-memory summary for a window of remembered tokens the policy can look back into. The belief is now whatever the attention layers read out of that window.

World-model latents as learned belief. The model-based lesson built agents whose recurrent state-space models maintain a compact latent $z_t$ and predict the next latent from the current one and the action. That latent is doing double duty: it is the model's state and the agent's belief. A recurrent state-space model updated with each observation is a learned Bayes filter — predict the next latent, correct it against the observation actually seen — with the transition and observation models learned rather than given. When Dreamer acts from its latent state, it is acting from an implicit belief, and it copes with partial observation for the reason this lesson has developed: the latent carries the history a single frame lacks.

The one idea

A POMDP is an MDP with the state hidden behind an observation, and every technique here answers the same question: given that one observation is not a Markov signal, what do you condition your policy on instead? The principled answer is the belief state, the posterior over hidden states, updated by a Bayes filter; it is a sufficient statistic that turns the POMDP into an MDP over beliefs — exactly solvable in theory, PSPACE-hard in practice, and approximated by point-based methods on a known model. The deep-RL answer keeps the structure and drops the model: a recurrent (or attention, or world-model) network learns to summarize history into a hidden vector that stands in for the belief, trained end-to-end from reward. DRQN showed the recurrence survives flickered observations; R2D2 made recurrent replay work at scale. Whatever the mechanism, the commitment is the same: remember the past, because the present observation is not enough.