"The last chapter gave me a state and I loved it the way a sleepwalker loves a handrail. Tell me where I am and I will tell you what to do; the policy was a lookup table and life was a lookup table and everything was fine. Then they put me behind a door. Now I get a sensor, not a state: a click, a creak, a smell of something that might be a reward or might be a tiger, and the true world stays politely hidden on the other side of a probability. I cannot act on where I am because I no longer know where I am. So I keep a running confession instead, a distribution over every place I could be, and I update it after every glance, and I act on the confession rather than the fact. They call it a belief. I call it the only honest thing a creature without eyes can carry. And the strangest part, the part I am still getting used to, is that this confession is just a filter wearing a crown: the same Kalman recursion from Chapter 7, the same hidden-Markov posterior, promoted from forecasting the world to deciding inside it."
A Belief State Listening at the Door for a Tiger
Chapter Overview
The previous chapter handed the agent a gift it quietly took for granted: the Markov state. In a Markov decision process the agent sees exactly the quantity that makes the future independent of the past, and the optimal policy collapses into a function of that single observable thing. Reality is rarely so generous. A robot reads noisy sensors, not coordinates; a clinician sees vital signs, not the underlying disease; a trading system observes prices, not the regime that produces them; a dialogue agent hears words, not the user's intent. In every one of these settings the true state is hidden, the observation is a partial and noisy shadow of it, and the comfortable MDP assumption that "what you see is the state" simply fails. This chapter, the second of Part VI, is about acting well anyway. It is the chapter where sequential decision making meets partial observability, and where the classical filtering of Part II returns wearing a crown.
The central move is to stop pretending the agent knows where it is and to track, instead, a distribution over where it could be. That distribution is the belief state, and maintaining it is nothing more exotic than Bayesian filtering: start from a prior over hidden states, push it forward through the transition model, and correct it by the likelihood of each new observation, exactly the predict-and-update recursion that the Kalman filter and the hidden Markov model forward algorithm performed in Chapter 7. The belief is a sufficient statistic of the entire action-observation history, which means the partially observed problem becomes a fully observed one again, just over a continuous belief space rather than the original discrete states. This is the formal payoff of the partially observable Markov decision process, the POMDP: it converts "act under uncertainty about the state" into "act on a belief you can compute," and it makes the whole machinery of the previous chapter applicable one level up.
That reduction is beautiful and, in the worst case, computationally brutal, because the belief space is continuous and high-dimensional and exact value functions over it grow without mercy. The chapter therefore moves from the exact theory (the value function is piecewise-linear and convex in the belief, represented by alpha-vectors) to the approximate solvers that made POMDPs practical: point-based value iteration that only backs up the belief points the agent actually reaches, anytime variants like SARSOP that focus computation on the optimally reachable belief region, and online tree-search methods like POMCP that plan from the current belief by Monte Carlo rollouts without ever enumerating the belief space. These are the algorithms that let a real robot localize and act in a world it cannot fully see. The chapter treats them not as a zoo of acronyms but as a single progression: how to spend a fixed compute budget on the beliefs that matter.
Then comes the modern shortcut, and the chapter's deepest temporal-thread payoff. Deep reinforcement learning mostly does not maintain an explicit belief at all. Instead it feeds the action-observation history into a recurrent network or a state-space model and lets the agent learn its own internal memory, a learned summary of the past that plays the functional role of a belief without ever being told to be one, trained end to end from reward. The recurrent agents of Part III (Chapter 10) return here as the memory of a decision maker: DRQN replaces the Q-network's stack of frames with an LSTM, R2D2 scales recurrent replay to the front of the benchmark, and recent work shows a well-tuned recurrent model-free agent is a strong baseline across many POMDPs. The unifying lesson of the chapter is one clean equation of ideas, the spine of the entire book in a single line: filtering equals belief equals agent memory. The Kalman recursion that forecast a series, the belief that a planner reasons over, and the hidden state an RNN learns from reward are three faces of the same thing, the running summary a temporal system carries so it can act on a past it can no longer see.
Prerequisites
This chapter sits at a confluence of three earlier threads, and it leans on each of them. From the immediately preceding Chapter 22: Markov Decision Processes you need the full MDP vocabulary: states, actions, transition and reward models, the discounted return, value functions, the Bellman equations, and value and policy iteration, because a POMDP is built directly on top of an MDP and its solvers are belief-space versions of the same recursions. From Chapter 7: State-Space Models and Filtering you need the predict-and-update structure of Bayesian filtering, the Kalman filter for the linear-Gaussian case and the hidden Markov model forward algorithm for the discrete case, since the belief-state update at the heart of this chapter is precisely that recursion, now driving a decision rather than a forecast. From the recurrent models of Chapter 10: Recurrent Neural Networks you need the idea of a hidden state that carries a learned summary of a sequence forward in time, because the deep-RL approach to partial observability replaces the explicit belief with exactly such a learned memory. The probability you need (conditional distributions, Bayes' rule, marginalization) is the same spine as the filtering chapter; readers wanting a refresher on any of these will find every chapter and the appendices through the Table of Contents.
If you keep one idea from this chapter, keep this: when the true state is hidden, the agent should act on a belief, a distribution over states maintained by Bayesian filtering, and that belief is a sufficient statistic that turns a partially observed problem back into a solvable one, whether you compute the belief explicitly with a POMDP solver or learn it implicitly as the hidden state of a recurrent or state-space agent trained from reward. The belief update is the Kalman and HMM recursion of Chapter 7; exact POMDP value functions are piecewise-linear and convex in the belief and represented by alpha-vectors; approximate solvers (PBVI, SARSOP, POMCP) spend compute only on the beliefs that matter; and deep-RL agents skip the explicit belief and let an RNN or SSM learn its own memory. Filtering equals belief equals agent memory: the same running summary, used to forecast, to plan, and to act.
Chapter Roadmap
- 23.1 Partial Observability and Belief States Why "what you see is the state" fails in the real world: the POMDP model of hidden states, noisy observations, and observation likelihoods, the belief state as a distribution over hidden states, and the Bayesian filtering recursion that maintains it, the same predict-and-update of Chapter 7 now used to decide rather than to forecast.
- 23.2 Solving POMDPs: Exact and Approximate Turning the belief into a policy: the belief MDP, the piecewise-linear and convex value function and its alpha-vector representation, why exact solving is intractable, and the approximate solvers that made POMDPs practical, point-based value iteration, the anytime SARSOP, and the online tree search of POMCP.
- 23.3 Recurrent and SSM-Based Agents for Partial Observability The deep-RL shortcut: instead of computing an explicit belief, feed the action-observation history into a recurrent network or a state-space model and let the agent learn its own memory from reward, DRQN's LSTM Q-network, R2D2's recurrent replay, and the strong recurrent model-free baseline for many POMDPs.
- 23.4 Bridge: Filtering, Belief Tracking, and Memory The chapter's punchline and one of the book's load-bearing arcs: the Kalman and HMM filter, the belief a POMDP solver reasons over, and the hidden state a recurrent agent learns are three faces of one idea, the running summary a temporal system carries so it can act on a past it can no longer see.
Once you have worked through the four sections, the Hands-On Lab below chains them into a single experiment on one small but classic POMDP. Each lab stage maps to a section, so the lab doubles as a review: by the time you finish you will have built the explicit belief filter of Section 23.1, solved the problem approximately with the alpha-vector and solver machinery of Section 23.2, trained the learned-memory agent of Section 23.3, and seen for yourself the equivalence that Section 23.4 argues.
Hands-On Lab: Believe Then Act
Objective
Take the smallest honest POMDP, the classic Tiger problem, where two doors hide a tiger and a reward and the only action besides opening a door is to listen, imperfectly, for the growl, and solve it three ways that turn out to be the same way. First you will implement a Bayes belief filter by hand and act on the belief, watching the predict-and-update recursion of Section 23.1 drive a decision: listen until the belief is confident enough, then open the door the belief favors. Second you will solve the same problem approximately, computing alpha-vectors yourself or calling a POMDP library, and recover a near-optimal policy over the belief simplex, the machinery of Section 23.2. Third you will throw away the explicit belief entirely and train a recurrent agent that receives only the raw observation history and a reward signal, and watch it learn, from reward alone, an internal memory that behaves like the belief you hand-built in stage one, the learned-memory approach of Section 23.3. The single thread, and the lesson of Section 23.4, is that the hand-built belief, the solver's alpha-vectors, and the RNN's hidden state are three routes to one policy.
What You'll Practice
- Specifying a POMDP (states, actions, observations, transition, observation, and reward models) and implementing the Bayes belief update by hand, following Section 23.1.
- Acting on a belief: choosing actions from the current belief and tracing how each observation sharpens or flips it, following Section 23.1.
- Solving the POMDP approximately with alpha-vectors or a library and reading the policy off the belief simplex, following Section 23.2.
- Training a recurrent model-free agent on the raw observation history and verifying its hidden state tracks the belief, following Section 23.3.
- Comparing the three policies and articulating the filtering-equals-belief-equals-memory equivalence, following Section 23.4.
Setup
You need a Python environment with a POMDP toolkit for the solving stage and a reinforcement-learning stack for the recurrent agent. pomdp-py gives a clean way to declare the Tiger model and run point-based or online solvers, and any RL library with recurrent-policy support (or a short custom training loop over Gymnasium) suffices for the learned-memory agent. The one discipline that governs the whole lab is to keep the three solutions reading from the same model specification: the transition, observation, and reward tables you write for the hand-built filter must be exactly the tables the solver consumes and exactly the dynamics the RL environment simulates, because the entire point is to show that one problem admits three equivalent solutions, and a mismatched model quietly breaks the comparison while every individual number still looks plausible. The code below maintains the explicit belief for the Tiger problem in a handful of lines, the predict-and-update recursion that stage one is built around.
import numpy as np
# States: tiger-left (0), tiger-right (1). Observation: hear-left / hear-right, 85% accurate.
def update_belief(belief, obs):
obs_model = np.array([[0.85, 0.15], # P(hear-left | state)
[0.15, 0.85]]) # P(hear-right | state)
likelihood = obs_model[obs] # likelihood of this observation per state
posterior = likelihood * belief # Bayes: multiply prior by likelihood
return posterior / posterior.sum() # renormalize to a valid belief
belief = np.array([0.5, 0.5]) # prior: tiger equally likely either side
for obs in [0, 0, 0]: # three "hear-left" growls
belief = update_belief(belief, obs) # belief shifts toward tiger-left
# belief is now strongly peaked: listen has paid off, now act on it.
obs_model[obs]) for brevity, whereas Section 23.1 uses the state-major Z convention (rows = state, columns = observation); the two are transposes of the same model.Steps
Step 1: Build the belief filter and act on it
Specify the Tiger POMDP and implement the belief update above, then write a simple policy that listens while the belief is near uniform and opens the favored door once the belief crosses a confidence threshold, the act-on-the-belief loop of Section 23.1. Run many episodes and record the average return as a function of the threshold, watching the cost of listening trade against the cost of opening too soon.
Step 2: Solve the POMDP approximately
Declare the same model in pomdp-py and solve it with a point-based or online solver, recovering the alpha-vectors and the policy they induce over the belief simplex, the machinery of Section 23.2. Compare the solver's threshold and value against the hand-tuned threshold from Step 1 and confirm the solver finds the optimal listen-then-open boundary you searched for by hand.
Step 3: Train a recurrent agent from reward
Wrap the Tiger dynamics in an environment that emits only the raw observation (never the belief or the true state) and train a recurrent model-free agent (an LSTM or SSM policy) on reward alone, the approach of Section 23.3. Give it enough episodes to discover that listening before opening pays, the same lesson the belief filter encodes explicitly.
Step 4: Show the three are one
Probe the trained agent's hidden state across an episode and regress or correlate it against the explicit belief from Step 1, demonstrating that the learned memory tracks the Bayesian belief it was never told to compute, the equivalence of Section 23.4. Put the three returns side by side and confirm all three policies converge on the same listen-then-act behavior.
Expected Output
The lab produces one POMDP solved three ways and a single picture of why they agree. The hand-built filter of Step 1 yields a belief that sharpens with each consistent growl and flips when the evidence contradicts it, and a threshold policy whose average return peaks at an intermediate confidence level, listen too little and you open onto the tiger, listen too long and you pay the listening cost without extra safety. The solver of Step 2 returns alpha-vectors whose induced policy carves the belief simplex into a listen region and two open regions, and its optimal threshold matches the best hand-tuned threshold from Step 1, the explicit confirmation that the belief is a sufficient statistic. The recurrent agent of Step 3 learns, from reward and raw observations only, to listen before committing, reaching a return close to the solver's optimum. The probe of Step 4 is the payoff: the agent's hidden state, projected down, traces the same trajectory as the hand-computed belief, so the RNN has rediscovered Bayesian filtering without ever being told the transition or observation model. The reader finishes with the chapter's thesis made concrete, that a filter, a belief, and a learned memory are three names for the running summary a temporal agent carries so it can act on a state it cannot see.
Each stage of this lab has a mature library that collapses the from-scratch version into a few calls. The exact and point-based solving that Section 23.2 derives, the belief MDP, the alpha-vector backups, and the reachable-belief search, is a model declaration plus a solver call in pomdp-py, which ships the Tiger problem and PBVI, SARSOP-style, and POMCP solvers ready to run; the explicit belief filter of Section 23.1 is a single recursion as shown above; and the recurrent agent of Section 23.3 is a recurrent-policy flag in a modern RL library rather than a hand-rolled LSTM training loop. The discipline the chapter teaches still governs the libraries: a solver fed a mismatched observation model, a belief initialized from a wrong prior, or a recurrent agent whose history window is too short to be a sufficient statistic will each return a confident and wrong policy in exactly the same few lines. The library makes the solver free; it does not make the model correct or the memory long enough.
Stretch Goals
- Make the observation noisier (drop the listening accuracy toward chance) and watch the optimal listen region of Section 23.2 grow: the worse the sensor, the longer the optimal policy waits before acting, and the harder the recurrent agent of Section 23.3 has to work to learn it.
- Swap the LSTM policy of Step 3 for a state-space-model policy and compare sample efficiency and final return, testing whether the structured memory of Chapter 10's successors tracks the belief more cheaply than a recurrent net.
- Scale up from Tiger to a small grid-world POMDP with a continuous belief and re-run the comparison, finding the point where the explicit solver of Section 23.2 strains and the learned-memory agent of Section 23.3 becomes the only practical option.
What's Next?
This chapter took the comfortable observable state of the previous one and hid it, and taught the agent to act on a belief instead, whether computed by a POMDP solver or learned as the memory of a recurrent agent. But both chapters so far have assumed the agent knows the rules of the world: the transition model, the reward model, the observation model were all given. Real agents are rarely handed the rules. Chapter 24: Bandits and Foundations of Reinforcement Learning drops that assumption and confronts the agent with an unknown environment it must learn about by acting, starting from the simplest such problem, the multi-armed bandit, where there is no state to track at all and the entire difficulty is the exploration-versus-exploitation tradeoff: whether to pull the arm that looks best so far or the one you have not yet learned enough about. From bandits the chapter builds the foundations of reinforcement learning proper, value estimation from sampled experience and the temporal-difference learning that powers everything in the chapters after it. The belief you learned to track here becomes, in the next chapter, a thing you must also learn the dynamics behind. The full path through Part VI and the rest of the book is laid out in the Table of Contents.
Bibliography & Further Reading
Foundations: Belief States and the POMDP Framework
Astrom, K. J. "Optimal Control of Markov Processes with Incomplete State Information." Journal of Mathematical Analysis and Applications, 10(1), 174-205, 1965. doi.org/10.1016/0022-247X(65)90154-X
The original result that the belief state, a posterior distribution over hidden states, is a sufficient statistic for optimal control under partial observation, the formal foundation of everything in Section 23.1.
Kaelbling, L. P., Littman, M. L., Cassandra, A. R. "Planning and Acting in Partially Observable Stochastic Domains." Artificial Intelligence, 101(1-2), 99-134, 1998. cs.cmu.edu/~ggordon/.../kaelbling-littman-cassandra-pomdp.pdf
The canonical introduction to POMDPs: the belief MDP, the piecewise-linear convex value function, and exact value iteration over beliefs, the single best entry point to Sections 23.1 and 23.2.
Sutton, R. S., Barto, A. G. "Reinforcement Learning: An Introduction." 2nd ed., MIT Press, 2018. incompleteideas.net/book/the-book.html
The standard textbook of the field, whose treatment of states, value functions, and function approximation under partial observability frames the MDP-to-POMDP step that this chapter builds on.
Solving POMDPs: Exact and Approximate
Pineau, J., Gordon, G., Thrun, S. "Point-based Value Iteration: An Anytime Algorithm for POMDPs." IJCAI, 1025-1032, 2003. ijcai.org/Proceedings/03/Papers/147.pdf
Point-based value iteration (PBVI), the breakthrough that made POMDPs tractable by backing up only the belief points an agent actually reaches, the workhorse approximate solver of Section 23.2.
Kurniawati, H., Hsu, D., Lee, W. S. "SARSOP: Efficient Point-Based POMDP Planning by Approximating Optimally Reachable Belief Spaces." Robotics: Science and Systems, 2008. roboticsproceedings.org/rss04/p9.pdf
SARSOP, which focuses computation on the belief region reachable under an optimal policy, a leading offline POMDP solver and a centerpiece of the approximate methods in Section 23.2.
Silver, D., Veness, J. "Monte-Carlo Planning in Large POMDPs (POMCP)." NeurIPS, 2010. papers.nips.cc/paper/2010/.../POMCP
POMCP, online Monte Carlo tree search that plans from the current belief by sampled rollouts without enumerating the belief space, the scalable online solver of Section 23.2.
Deep RL Under Partial Observability: Learned Memory
Hausknecht, M., Stone, P. "Deep Recurrent Q-Learning for Partially Observable MDPs (DRQN)." 2015. arXiv:1507.06527. arxiv.org/abs/1507.06527
DRQN, which replaces the deep Q-network's stack of frames with an LSTM so the agent learns its own memory of the observation history, the founding deep-RL approach of Section 23.3.
Kapturowski, S., Ostrovski, G., Quan, J., Munos, R., Dabney, W. "Recurrent Experience Replay in Distributed Reinforcement Learning (R2D2)." ICLR, 2019. openreview.net/forum?id=r1lyTjAqYX
R2D2, which scales recurrent replay to the front of the Atari benchmark and details how to train an LSTM agent's hidden state correctly, the state-of-the-art recurrent agent of Section 23.3.
Ni, T., Eysenbach, B., Salakhutdinov, R. "Recurrent Model-Free RL is a Strong Baseline for Many POMDPs." ICML, 2022. arXiv:2110.05038. arxiv.org/abs/2110.05038
A careful study showing a well-tuned recurrent model-free agent matches or beats specialized POMDP methods across many benchmarks, the empirical backbone of the learned-memory argument in Sections 23.3 and 23.4.
Tools and Libraries
Zheng, K., Tellex, S. "pomdp-py: A Framework to Build and Solve POMDP Problems." ICAPS Workshop on Planning and Robotics, 2020. h2r.github.io/pomdp-py
The reference Python framework for declaring POMDP models and running belief updates and solvers (point-based, POMCP, and more), the engine behind the solving stage of the lab.