POMDPs and belief states
Real agents rarely see the true state of the world. A POMDP agent keeps a probability for every state it might be in, and updates it after each action and observation. That belief, not the raw observation, is what it acts on.
Kind: not an agent: the model for agents that can’t see everything.
Week: 4 (slides 45 to 50).
Book: one paragraph in Wooldridge, Ch. 2 notes (p. 46), citing the same paper as slide 46 (Kaelbling et al. 1998). Russell and Norvig 17.4 for more.
Techniques on this page: the POMDP tuple, the belief as the new state, the Bayes-filter update, \(o_t\) vs \(m_t\) vs \(s_t\) for LLM agents.
The problem it solves
Everything in the MDP pages assumed the agent sees the true state, \(o_t = s_t\). Many settings break that (slide 45): robot sensors are noisy; a doctor sees symptoms, not physiology; an LLM agent never sees the world, only text. Week 1 called this an inaccessible (partially observable) environment.
Acting on the latest observation alone (a purely reactive agent, \(a_t = \pi(o_t)\)) then throws information away. The fix is to carry a belief forward, and the lecture’s punchline is that the belief is Markov even when the observations aren’t.
Words you’ll hear
| Word or symbol | Plain meaning |
|---|---|
| POMDP | partially observable MDP |
| \(\Omega\) (Omega) | the set of possible observations |
| \(O(o \mid s', a)\) | the chance of seeing \(o\) on arriving in \(s'\) after action \(a\) |
| belief \(m_t\) | a probability for each state: “where I think I am” |
| Bayes filter | predict with \(P\), correct with \(O\), normalise |
| \(\propto\) | “proportional to”: divide by the total at the end |
Technique 1: the POMDP tuple
Problem it solves: adds what the agent can observe to the MDP.
\[\langle S, A, P, R, \gamma, \Omega, O\rangle\]
The agent never sees \(s_t\), only \(o_0, o_1, \ldots\) and its own actions (slide 46).
Technique 2: the belief is the new state
Problem it solves: gets back a Markov state to decide from.
\[m_t(s) = P(s_t = s \mid o_0, a_0, \ldots, a_{t-1}, o_t)\]
The belief summarises the whole history that matters, so it is Markov (slide 47). The price: it lives in the space of probability distributions over \(S\), which is continuous and much bigger than \(S\).
Compare BDI (week 2): there beliefs were symbolic facts (“door is closed”); here they’re numbers (“closed with probability 0.85”). Same role.
Technique 3: the belief update
Problem it solves: folds each new observation into what the agent believes (slide 48).
\[m_t(s') \propto O(o_t \mid s', a_{t-1}) \sum_s P(s' \mid s, a_{t-1})\, m_{t-1}(s)\]
- Predict: push the old belief through the dynamics.
- Correct: multiply each state by how well it explains what was just seen.
- Normalise so it sums to 1.
This is week 1’s \(m_t = f(m_{t-1}, o_t, a_{t-1})\) (the next function) made precise.
Worked example (which room am I in?). Rooms L and R. Each step the robot stays, but is moved to the other room with probability 0.1. Its camera sees a window with probability 0.8 in L and 0.3 in R. Start at \((0.5, 0.5)\).
“window”: predict \((0.5, 0.5)\); correct \((0.8 \times 0.5, 0.3 \times 0.5) = (0.40, 0.15)\); normalise by 0.55: \((0.727, 0.273)\).
“window” again: predict \(L = 0.727(0.9) + 0.273(0.1) = 0.682\); correct \((0.545, 0.095)\); \((0.851, 0.149)\).
“none”: predict \(L = 0.781\); correct \((0.2 \times 0.781, 0.7 \times 0.219) = (0.1562, 0.1534)\); \((0.504, 0.496)\). One “none” nearly cancels two “window”s, because “none” is 3.5 times likelier in R.
Technique 4: \(o_t\), \(m_t\), \(s_t\) for an LLM agent
Problem it solves: says precisely why week 1 kept three symbols (slides 49 to 50).
| Symbol | What it is | For an LLM agent |
|---|---|---|
| \(o_t\) | what the environment reveals | a tool result, a message |
| \(m_t\) | what the agent carries forward | (roughly) its context window |
| \(s_t\) | the true state, maybe never fully known | the database row, the file, what the user really wants |
The true state is outside the agent’s boundary. An LLM’s context is not automatically a Markov state (topic 6): if it was trimmed (as in practical 2’s conversation window) or a tool result is stale, \(m_t\) no longer summarises what matters, and the agent acts on a wrong picture.
A failure to recognise. The agent read a file earlier; another process edits it; the agent edits based on the old contents in its context. \(s_t\) changed, \(m_t\) didn’t. Re-reading before writing is a belief update.
What to read
| Source | Read? | Why |
|---|---|---|
| Wooldridge, Ch. 2 Notes and Further Reading (p. 46) | Skim one paragraph | the book’s only mention of POMDPs |
| Russell and Norvig 17.4 (first pages) | Optional | belief states and the filtering update |
Page numbers are the book’s; in the scanned PDF add 21.
Practice prompt
I'm studying CS5940 Intelligent Agents, week 4 (MDPs and reinforcement learning). I want practice on POMDPs AND BELIEF STATES:
- what a POMDP adds to an MDP (Omega and O), and why the agent can't act on s_t
- what a belief m_t is, and why it is Markov when observations are not
- doing the belief update by hand (predict with P, correct with O, normalise) on two-state examples with friendly numbers
- why acting on the belief beats acting on the latest observation
- the difference between o_t, m_t and s_t for an LLM agent, with examples of when m_t goes stale
Please:
1. Use plain, everyday language and explain any symbol in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.