---
title: "Partial Observability: Planning and Recurrent Policies"
module: Modern Deep Reinforcement Learning
moduleNumber: 5
lessonNumber: 19
order: 519
summary: >
  A companion to the belief-state lesson. In principle a POMDP reduces to an MDP over
  beliefs; in practice two obstacles block that. Exact planning over the belief simplex
  is intractable — the value function is piecewise-linear-and-convex with a number of
  pieces that can explode — and computing the belief needs a model the agent rarely
  has. This lesson develops the intractability, the point-based approximations that
  address it, and the deep-RL answer: make the policy a function of history with a
  recurrent network (DRQN, R2D2), with frame-stacking, attention, and world-model
  latents as learned beliefs.
topics: [Deep RL]
sources:
  - book: Sutton & Barto
    ref: "Ch. 17 — Frontiers; §17.3 Observations and State (history, Markov state, belief state)"
  - book: Grokking Deep RL
    ref: "Ch. 12 — partial observability and recurrent agents"
---

This builds on
[Partial Observability: POMDPs and the Belief State](/reinforcement-learning/modern-deep-rl/partial-observability-pomdps),
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

$$
V^\ast(b) \;=\; \max_{\alpha \in \Gamma}\; b \cdot \alpha,
$$

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.

$$
% caption: The value function over the belief simplex is piecewise-linear and convex.
% Over a two-state belief (horizontal axis $b(s_1)$ from 0 to 1), each conditional
% plan is a line (an alpha-vector); $V^\ast$ is their upper envelope (blue). Convexity
% means certainty at the corners is worth more than uncertainty in the middle — the
% value of information. Each linear piece maps to one optimal action over its region.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (7.0,0) node[anchor=north, font=\footnotesize, text=black] {belief b(s1)};
  \draw[->, black] (0,0) -- (0,4.2) node[anchor=east, font=\footnotesize, text=black, rotate=90, yshift=6mm] {V(b)};
  \node[anchor=north, font=\scriptsize, text=black] at (0,0) {0};
  \node[anchor=north, font=\scriptsize, text=black] at (6.2,0) {1};
  % alpha-vector lines (each a linear plan value), light
  \draw[black] (0,0.7) -- (6.2,3.4);   % alpha 1
  \draw[black] (0,3.2) -- (6.2,0.9);   % alpha 2
  \draw[black] (0,2.1) -- (6.2,2.4);   % alpha 3
  \node[anchor=west, font=\scriptsize, text=black] at (6.25,3.4) {plan A};
  \node[anchor=west, font=\scriptsize, text=black] at (6.25,0.9) {plan B};
  \node[anchor=west, font=\scriptsize, text=black] at (6.25,2.4) {plan C};
  % upper envelope (PWLC), blue thick: follows plan B then C then A
  \draw[acc, very thick] (0,3.2) -- (1.15,2.77) -- (4.1,2.28) -- (6.2,3.4);
  \node[acc, anchor=south, font=\footnotesize] at (2.6,3.55) {V*(b) = upper envelope};
  % region ticks for optimal action
  \draw[red, thick] (1.15,0.08) -- (1.15,-0.08);
  \draw[red, thick] (4.1,0.08) -- (4.1,-0.08);
  \node[red, anchor=north, font=\scriptsize] at (0.6,-0.15) {act B};
  \node[red, anchor=north, font=\scriptsize] at (2.6,-0.15) {act C};
  \node[red, anchor=north, font=\scriptsize] at (5.2,-0.15) {act A};
\end{tikzpicture}
$$

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.

> **Definition (Alpha-vector).** A vector $\alpha \in \mathbb{R}^{|\mathcal{S}|}$ whose
> $s$-th entry is the expected return of a fixed conditional plan started in hidden
> state $s$. Its value at belief $b$ is the linear form $b \cdot \alpha$, and the
> optimal value function is the upper envelope $V^\ast(b) = \max_{\alpha} b \cdot \alpha$
> over the plans that survive.

### 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, \ldots, 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.

$$
% caption: Point-based value iteration keeps one alpha-vector per sampled belief
% (dots on the axis) instead of the full PWLC set, so the number of pieces stays fixed
% at the number of sampled points. The approximate value (blue) tracks the true
% envelope well near sampled beliefs and can only under-estimate between them. Sampling
% more reachable beliefs tightens the fit.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (7.0,0) node[anchor=north, font=\footnotesize, text=black] {belief b(s1)};
  \draw[->, black] (0,0) -- (0,4.0) node[anchor=east, font=\footnotesize, text=black, rotate=90, yshift=6mm] {V(b)};
  % true envelope (light)
  \draw[black] (0,3.1) -- (1.4,2.55) -- (4.2,2.15) -- (6.2,3.3);
  \node[anchor=west, font=\scriptsize, text=black] at (6.25,3.3) {true V*};
  % sampled belief points on the axis
  \foreach \x in {0.6,2.4,4.4,5.6} {
    \fill[red] (\x,0) circle (2pt);
    \draw[black, dashed] (\x,0) -- (\x,3.5);
  }
  \node[red, anchor=north, font=\scriptsize] at (3.0,-0.15) {sampled beliefs B};
  % PBVI alpha-vectors (a few lines) and their envelope
  \draw[acc, very thick] (0,3.0) -- (1.4,2.5) -- (4.2,2.05) -- (6.2,3.15);
  \node[acc, anchor=south, font=\footnotesize] at (2.7,3.4) {PBVI approximation};
\end{tikzpicture}
$$

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.[^pbvi] 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](/reinforcement-learning/tabular-methods/monte-carlo-tree-search)
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$.[^pomcp] 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.

$$
% caption: Online POMCP-style planning. Instead of an explicit belief vector, the
% current belief is a bag of sampled states (particles). Monte Carlo tree search
% branches on actions and observations, running the generative simulator forward from
% sampled particles; the most-visited root action is played, the true observation is
% received, and the particle set is filtered and re-used to re-plan from the new belief.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  nd/.style={circle, draw, minimum size=6mm, inner sep=0pt, font=\scriptsize},
  ob/.style={draw, minimum width=8mm, minimum height=6mm, inner sep=1pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % root belief = particles
  \node[nd, draw=acc, text=acc] (root) at (0,3.0) {b};
  \node[anchor=east, font=\scriptsize, red, align=right] at (-0.4,3.0) {particles\\(sampled states)};
  % actions
  \node[nd] (a1) at (-2.0,1.5) {a1};
  \node[nd] (a2) at (2.0,1.5) {a2};
  \draw[->, black] (root) -- (a1) node[midway, above left, font=\scriptsize] {act};
  \draw[->, black] (root) -- (a2);
  % observations under a1
  \node[ob] (o1) at (-3.0,0) {o};
  \node[ob] (o2) at (-1.0,0) {o'};
  \draw[->, black] (a1) -- (o1);
  \draw[->, black] (a1) -- (o2);
  % observations under a2
  \node[ob] (o3) at (1.0,0) {o};
  \node[ob] (o4) at (3.0,0) {o'};
  \draw[->, black] (a2) -- (o3);
  \draw[->, black] (a2) -- (o4);
  % rollout arrows
  \draw[->, acc, thick, dashed] (o1) -- ++(0,-0.9) node[anchor=north, font=\scriptsize, acc] {rollout};
  \draw[->, acc, thick, dashed] (o4) -- ++(0,-0.9) node[anchor=north, font=\scriptsize, acc] {rollout};
\end{tikzpicture}
$$

**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.[^despot] 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:

$$
\mathbf{c}_t = \text{RNN}_\theta(\mathbf{c}_{t-1}, o_t), \qquad
Q_t = f_\theta(\mathbf{c}_t, a).
$$

Compare this to the POMDP state-update function $S_{t+1} = u(S_t, A_t, O_{t+1})$ from
the [frontiers lesson](/reinforcement-learning/deep-rl/frontiers): 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.

$$
% caption: A recurrent policy as a learned belief. Observations $o_1, o_2, o_3$ arrive
% one per step; the recurrent cell folds each into a hidden state $c_t$ that carries
% forward, and a head reads $c_t$ into Q-values. The hidden state plays the role of the
% belief — a compact summary of history — but is learned end-to-end rather than
% computed from a known model.
\begin{tikzpicture}[>=stealth, font=\small,
  cell/.style={draw, minimum width=15mm, minimum height=10mm, align=center, font=\footnotesize},
  obs/.style={circle, draw, draw=acc, text=acc, minimum size=8mm, inner sep=0pt, font=\footnotesize},
  head/.style={draw, minimum width=13mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % observation inputs
  \node[obs] (o1) at (0,-1.7)   {o1};
  \node[obs] (o2) at (3.4,-1.7) {o2};
  \node[obs] (o3) at (6.8,-1.7) {o3};
  % recurrent cells
  \node[cell] (c1) at (0,0)   {cell};
  \node[cell] (c2) at (3.4,0) {cell};
  \node[cell] (c3) at (6.8,0) {cell};
  \draw[->, black, thick] (o1) -- (c1);
  \draw[->, black, thick] (o2) -- (c2);
  \draw[->, black, thick] (o3) -- (c3);
  % recurrence forward
  \draw[->, red, thick] (c1) -- (c2) node[midway, above, font=\scriptsize, text=red] {c1};
  \draw[->, red, thick] (c2) -- (c3) node[midway, above, font=\scriptsize, text=red] {c2};
  % heads
  \node[head, draw=acc, text=acc] (q1) at (0,1.7)   {Q values};
  \node[head, draw=acc, text=acc] (q2) at (3.4,1.7) {Q values};
  \node[head, draw=acc, text=acc] (q3) at (6.8,1.7) {Q values};
  \draw[->, acc] (c1) -- (q1);
  \draw[->, acc] (c2) -- (q2);
  \draw[->, acc] (c3) -- (q3);
  \node[anchor=west, font=\scriptsize, text=red] at (7.2,0) {hidden state = learned belief};
\end{tikzpicture}
$$

### Frame stacking versus recurrence

The original [DQN](/reinforcement-learning/deep-rl/deep-q-networks)
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.

| | Frame stacking | Recurrent policy |
| --- | --- | --- |
| Memory | fixed, last $k$ observations | in principle unbounded |
| Set by | the designer (chooses $k$) | learned in the hidden state |
| Cost | input grows with $k$ | one hidden vector, any horizon |
| Fails when | dependency older than $k$ | long-range credit assignment is hard to train |
| Belief analogue | $k$-th-order Markov window | learned sufficient statistic |

### DRQN: a recurrent DQN

The first direct demonstration of recurrence in deep RL was **DRQN** (Deep Recurrent
Q-Network), Hausknecht and Stone (2015).[^drqn] 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.[^drqn]

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.

$$
% caption: DRQN. A convolutional encoder turns each single frame into a feature
% vector; an LSTM integrates those features over time into a hidden state that a
% Q-head reads. Unlike DQN, DRQN sees one frame at a time and must remember through
% the recurrence, which is why it survives flickered, partially observed inputs.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=15mm, minimum height=9mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box] (frame) at (0,0) {frame o(t)};
  \node[box] (conv) at (2.4,0) {conv\\encoder};
  \node[box, draw=acc, text=acc, thick] (lstm) at (4.8,0) {LSTM};
  \node[box] (qh) at (7.2,0) {Q head};
  \draw[->, black, thick] (frame) -- (conv);
  \draw[->, black, thick] (conv) -- (lstm);
  \draw[->, acc, thick] (lstm) -- (qh);
  % recurrence: a curved arrow leaving the top and returning to it
  \coordinate (lu) at (4.4,0.45);
  \coordinate (ru) at (5.2,0.45);
  \draw[->, red, thick] (lu) .. controls (4.4,1.6) and (5.2,1.6) .. (ru);
  \node[anchor=south, font=\scriptsize, text=red] at (4.8,1.45) {hidden state c(t)};
  \node[anchor=north, font=\scriptsize, text=black] at (2.4,-0.7) {one frame, no stacking};
\end{tikzpicture}
$$

### 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] 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.

$$
% caption: R2D2's recurrent replay. A replayed sequence is split into a burn-in
% prefix and a learning suffix. The stored hidden state seeds the network; the
% burn-in steps only warm up the hidden state (no loss), and the TD loss is computed
% on the learning steps, by which point the hidden state is consistent with the
% current parameters. This removes the zero-state bias that hurt naive recurrent
% replay.
\begin{tikzpicture}[>=stealth, font=\small,
  stepbox/.style={draw, minimum width=9mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % stored state seed
  \node[anchor=east, font=\scriptsize, text=red] at (-0.2,0) {stored c};
  \draw[->, red, thick] (-0.2,0) -- (0.4,0);
  % burn-in steps
  \foreach \i/\x in {1/0.9, 2/1.9, 3/2.9} {
    \node[stepbox] (b\i) at (\x,0) {b};
  }
  % learning steps
  \foreach \i/\x in {1/4.2, 2/5.2, 3/6.2, 4/7.2} {
    \node[stepbox, draw=acc, text=acc] (l\i) at (\x,0) {L};
  }
  % chain arrows
  \draw[->, black] (b1) -- (b2);
  \draw[->, black] (b2) -- (b3);
  \draw[->, black] (b3) -- (l1);
  \draw[->, acc] (l1) -- (l2);
  \draw[->, acc] (l2) -- (l3);
  \draw[->, acc] (l3) -- (l4);
  % brackets
  \draw[black, thick] (0.4,0.75) -- (0.4,0.95) -- (3.4,0.95) -- (3.4,0.75);
  \node[anchor=south, font=\scriptsize, text=black] at (1.9,0.95) {burn-in: warm up hidden state, no loss};
  \draw[acc, thick] (3.7,-0.75) -- (3.7,-0.95) -- (7.7,-0.95) -- (7.7,-0.75);
  \node[acc, anchor=north, font=\scriptsize] at (5.7,-0.95) {learning steps: compute TD loss};
\end{tikzpicture}
$$

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.[^r2d2]

## 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](/reinforcement-learning/modern-deep-rl/model-based-rl) 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.

$$
% caption: Three ways to represent the belief the agent cannot compute exactly. A
% recurrent policy compresses history into one hidden vector; an attention memory keeps
% past tokens and reads over them; a world-model latent is updated like a learned Bayes
% filter (predict next latent, correct against the observation). All three are the same
% commitment: carry a summary of history because one observation is not Markov.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=30mm, minimum height=13mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc] (r) at (0,0)   {recurrent hidden\\state (RNN)};
  \node[box] (a) at (4.6,0)   {attention over\\past tokens};
  \node[box] (w) at (9.2,0)   {world-model\\latent z};
  % common label below
  \node[anchor=north, font=\scriptsize, text=black, align=center] at (0,-1.0)   {compress history\\to one vector};
  \node[anchor=north, font=\scriptsize, text=black, align=center] at (4.6,-1.0) {keep and look back\\at history};
  \node[anchor=north, font=\scriptsize, text=black, align=center] at (9.2,-1.0) {learned Bayes\\f\/ilter latent};
  % unifying bracket above
  \draw[red, thick] (-1.5,1.05) -- (-1.5,1.25) -- (10.7,1.25) -- (10.7,1.05);
  \node[red, anchor=south, font=\footnotesize] at (4.6,1.25) {all learned belief-substitutes: remember the past};
\end{tikzpicture}
$$

## 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.


[^pbvi]: **Pineau, Gordon, Thrun (2003)**, "Point-based value iteration: An anytime algorithm for POMDPs," _IJCAI_. PBVI approximates the PWLC value function by maintaining one alpha-vector per sampled reachable belief and backing up only at those points, making POMDPs of hundreds of states tractable; the SARSOP and HSVI successors (Kurniawati et al. 2008; Smith & Simmons 2004) push this to thousands of states by focusing sampling on optimally reachable beliefs.
[^pomcp]: **Silver & Veness (2010)**, "Monte-Carlo Planning in Large POMDPs" (POMCP), _NeurIPS_. Runs UCT search in the belief tree using a particle filter for the belief update and a black-box generative simulator instead of explicit $T$ and $Z$, scaling online POMDP planning to state spaces of $10^{56}$ far beyond exact or point-based methods.
[^despot]: **Ye, Somani, Hsu, Lee (2017)**, "DESPOT: Online POMDP Planning with Regularization," _JAIR_ (and NeurIPS 2013). Searches a Determinized Sparse Partially Observable Tree under a small fixed set of sampled scenarios, bounding tree width and giving a regret guarantee, improving robustness and speed over POMCP on many benchmarks.
[^drqn]: **Hausknecht & Stone (2015)**, "Deep Recurrent Q-Learning for Partially Observable MDPs," _AAAI Fall Symposium_ (arXiv:1507.06527). DRQN replaces DQN's first post-convolutional fully-connected layer with an LSTM, is fed one frame at a time, and is trained by sampling contiguous sequences and unrolling the LSTM; it matches DQN on standard Atari and degrades far more gracefully under "flickering" (each frame blanked with probability 0.5), demonstrating that the recurrent hidden state substitutes for stacked frames under partial observability.
[^r2d2]: **Kapturowski, Ostrovski, Quan, Munos, Dabney (2019)**, "Recurrent Experience Replay in Distributed Reinforcement Learning" (R2D2), _ICLR_. Combines a recurrent (LSTM) value network with distributed prioritized replay; identifies the representational-mismatch / staleness problem of hidden states in recurrent replay and fixes it by storing the recurrent state and adding a burn-in prefix that warms up the hidden state before any loss is computed, roughly quadrupling the previous best median human-normalized score on Atari-57. Its recurrent-replay backbone underlies Agent57 (Badia et al. 2020), the first agent to exceed the human benchmark on all 57 games.