Acting When You Cannot See the State

Markov decision processes assume the agent knows where it is. That assumption is doing more work than it looks, and dropping it changes the problem completely - not because the mathematics gets harder in some incidental way, but because the central object of an MDP, a policy indexed by state, stops being something the agent can execute.

This article works through what replaces it, on a world small enough that every number can be computed exactly.

A. One addition

A partially observable MDP has everything an MDP has - transition model, actions, rewards - plus a sensor model $P(e \mid s)$: the probability of perceiving evidence $e$ in state $s$.

The consequence is immediate. A policy $\pi(s)$ requires looking up the state, and the agent cannot. Worse, the optimal action no longer depends only on where the agent is but on how much it knows: two agents in the same state, one certain and one confused, should often act differently.

B. The belief state

The replacement is the distribution over states consistent with everything done and perceived: the belief state $b$, with $b(s)$ the probability of being in $s$.

Two properties make it the right object. It is always observable to the agent - it summarises the agent's own history, not the world - so $\pi(b)$ is executable where $\pi(s)$ is not. And it is a sufficient statistic: because transitions and percepts are Markov, everything the past says about the future is already inside the current distribution, so the history can be discarded.

It is maintained by one recursion:

$$b'(s') = \alpha \; P(e \mid s') \sum_{s} P(s' \mid s, a) \, b(s) .$$

Predict through the transition model, weight by how likely the percept would be, normalise. This is the forward step of HMM filtering with one addition: the transition model depends on the agent's choice, so the agent influences not only where it goes but what it will learn.

C. A world small enough to see

Two states, 0 and 1, with $R(0) = 0$ and $R(1) = 1$. Stay persists with probability 0.9, Go switches with probability 0.9. The sensor is correct with probability 0.6. A belief is one number, $b(1)$, so the whole belief space is $[0, 1]$.

From $b(1) = 1/2$, every action-percept pair:

The action made no difference. From an even belief, Stay and Go both leave the prediction even - one persists with 0.9, the other switches with 0.9, which from 50/50 is the same thing - so the percept does all the work. That separates the two jobs an action does in a POMDP: change the world, and change what you know about it. Here the first cancels and only the second shows.

D. The ceiling on certainty

Confidence is easier to lose than to gain. A belief of 0.99 taking Stay and then one contradicting percept falls to $446/527 = 0.846300$, most of it the Stay leak, which alone takes 0.99 to a prediction of 0.892. Pushing the other way, taking Stay and seeing percept 1 repeatedly from 1/2:

$$0.600, \; 0.674, \; 0.727, \; 0.762, \; 0.786, \; 0.801, \; 0.811, \; 0.817, \ldots$$

It does not reach 1. Iterating converges to $0.827934423$, and solving the fixed-point equation symbolically gives

$$b^{*} = \frac{3 + \sqrt{105}}{16} = 0.827934 .$$

Each percept pulls the belief outward; each transition leaks 0.1 of probability back toward the middle. The fixed point is where those cancel. Certainty is unreachable, so an agent that waits to find out where it is waits forever - it must plan while still uncertain.

This is also why the tempting shortcut fails. Track the belief, take the most likely state, feed it to an ordinary MDP policy: cheap, easy, and it never values an action for what the action would reveal. Offer such an agent a free sensing move and it sees no benefit, because its guessed state does not change. It never looks before it leaps.

Below is that whole belief space - the interval - with the belief on it as a single point. Press “Stay, saw 1” and keep pressing. The steps shrink visibly, the climb bends towards the dashed line, and it stops there. Then press “Stay, saw 0” once from up near the ceiling: a single reading from a sensor that is wrong 40% of the time costs more than two confirmations bought. That asymmetry is not a quirk of these numbers; it is what evidence against a confident belief always does.

E. The reduction

Now the payoff. Beliefs update deterministically from action and percept, and the probability of each percept is computable, so we can define an MDP whose states are beliefs - and an optimal policy for it is optimal for the POMDP. The reduction is exact.

The bill: that MDP has a continuous state space. For the 4×3 grid world of eleven states, a belief is a point in a ten-dimensional continuum (eleven probabilities summing to one). No standard MDP algorithm enumerates that.

The compensation: because an action moves the belief and not just the world, it is valued partly for the information it produces. The value of information stops being a separate calculation and becomes part of the ordinary decision.

F. Why the value function is computable in principle

Fix a conditional plan - a first action, then what to do after each percept, to some depth. It makes no decisions along the way, so its expected utility given true state $s$ is a number. Collect those into $\alpha_p$, and

$$U_p(b) = \sum_s b(s) \, \alpha_p(s)$$

is an inner product: linear in $b$, a hyperplane. The optimal value function takes the best plan at each belief, so it is a maximum of hyperplanes - piecewise linear and convex. The convexity says something: the low points are the beliefs of greatest uncertainty, so uncertainty is what costs.

For one-step plans with $\gamma = 1$:

$$\alpha_{[\text{Stay}]} = (0.1,\, 1.9), \qquad \alpha_{[\text{Go}]} = (0.9,\, 1.1),$$

crossing at $b(1) = 1/2$ where both are worth exactly 1. Go below, Stay above - the intuitive policy, arriving as a computation with the switch point pinned exactly.

Two-step plans number $2 \times 2 \times 2 = 8$, and sweeping the belief interval shows only four ever top the envelope: $(0.28, 2.72)$, $(0.68, 2.48)$, $(1.48, 1.68)$, $(1.72, 1.28)$. The other four are below it everywhere, so deleting them changes $U(b)$ nowhere.

Here are those eight plans as eight lines, with the value function as their upper envelope. The four the recursion keeps are drawn bold and the four dominated ones are drawn faint rather than dropped, because the point is that they exist and are useless: each lies below the envelope at every belief, so deleting it changes nothing. Switch to one step to watch the two lines cross at exactly one half, both worth 1.

G. Why it is not computable in practice

Depth-$d$ plans number $|A|^{(|E|^{d}-1)/(|E|-1)}$:

Doubly exponential, on the smallest interesting POMDP there is. Pruning dominated plans is essential - and insufficient. Running exact value iteration with $\gamma = 0.9$ and keeping only vectors that top the envelope, the surviving set grows sweep by sweep:

$$2, \; 4, \; 8, \; 16, \; 30, \; 52, \; 88 .$$

It never collapses, because the exact value function genuinely acquires more linear pieces as the horizon lengthens. The algorithm is correct; it simply does not finish.

H. Discretise, then check by executing

The belief space here is an interval, so grid it and run ordinary value iteration, splitting each successor belief between its two neighbours. That interpolation keeps the backup a contraction, so it converges - in 281 sweeps at 2001 points:

$$U(0) = 6.822940, \quad U(0.5) = 5.886486, \quad U(1) = 6.822940 .$$

Lowest in the middle: knowing where you are is worth $0.936454$ here. And the two ends are equal, which is worth checking rather than assuming - from certain state 0 the agent plays Go and reaches state 1 with probability 0.9; from certain state 1 it plays Stay and remains with probability 0.9. Same position next step, same value.

Refining the grid gives 6.822981, 6.822942, 6.822940 at 201, 801 and 2001 points. But that only shows the approximation converging to something - an interpolation scheme can converge smoothly to a biased answer and look exactly like this.

So run the policy. Over 30,000 rollouts of horizon 160:

Grid refinement asks whether the approximation is consistent with itself. Execution asks whether the policy actually earns that much. Only the second could have caught a systematic interpolation bias, and it is the one that matters.

Both halves are in the figure below. The plan count is printed in exact integers, because at depth six the answer is 2^63, and although a double stores that exactly, JavaScript prints it as 9223372036854776000, a number this page does not contain. The value function beside it is solved on the grid, and the slider walks the refinement table: 6.822981 at 201 points, 6.822942 at 801, 6.822940 at 2,001, in 281 sweeps. Watch the two ends stay equal while the middle sags - that is the convexity, and it is also the check that says the reward is collected on arrival rather than on departure.

Key takeaways

• A POMDP is an MDP plus a sensor model, and that one addition means a policy cannot be indexed by state.
• The belief state replaces it: always observable, and a sufficient statistic for the whole history.
• A noisy sensor saturates belief rather than resolving it - here at exactly $(3 + \sqrt{105})/16$ - so planning under uncertainty is permanent.
• The reduction to a belief-state MDP is exact, and costs a continuous state space.
• The value function is piecewise linear and convex, which makes exact value iteration possible and, measurably, not practical.
• Approximate, then verify by executing the policy rather than by refining the approximation.

What's next

Every method here assumed the models were known. Learning the transition and sensor models from experience while acting on them is the same problem with the parameters hidden too - and the EM algorithm turns out to be the tool.