Partially Observable MDP

A partially observable MDP has the same transition model, action set and reward function as an MDP, plus a sensor model giving the probability of each percept in each state. The addition looks small and changes the problem completely: the optimal action now depends not just on where the agent is but on how much it knows, so a policy cannot be a function of the state.

The resolution is to make it a function of the belief instead. Because the belief state is a sufficient statistic for the history and is always available to the agent, an optimal policy for the MDP defined over belief states is also optimal for the original problem. The reduction is exact rather than approximate - but the MDP it produces has a continuous and usually high-dimensional state space, so value iteration and policy iteration cannot simply be run on it.

What makes progress possible is the shape of the value function. Executing a fixed conditional plan makes no further decisions, so its expected utility is an inner product between the belief and a vector of per-state utilities - a hyperplane over belief space. The optimal value function takes the best plan at each belief, so it is a maximum of hyperplanes: piecewise linear and convex. Its convexity is a statement about uncertainty, since the low points are the beliefs where the agent least knows what to do.

That structure supports a value-iteration algorithm over sets of these vectors rather than over numbers, with dominated plans pruned at each step. It is exact and it does not scale: the number of conditional plans of depth d grows doubly exponentially, and pruning slows rather than stops the growth of the set that must be kept. Practical work therefore discretises the belief space, restricts attention to reachable beliefs, or plans online by lookahead from the current belief with a particle filter tracking it.

In a two-state world with rewards 0 and 1, one action persisting with probability 0.9 and the other switching with probability 0.9, and a sensor correct 60% of the time, the two one-step plans have utility vectors (0.1, 1.9) and (0.9, 1.1). The lines cross at a belief of 1/2, where both are worth exactly 1: switch below that belief, persist above it.

Extending to two steps produces 8 distinct conditional plans of which only 4 are undominated. The counts then run away - 128 at depth three and 32,768 at depth four - and pruning does not rescue them: over seven sweeps of exact value iteration the undominated set still grew 2, 4, 8, 16, 30, 52, 88.

Discretising the belief interval and running ordinary value iteration with interpolation converges in 281 sweeps, giving 6.822940 at both certain beliefs and 5.886486 at the even one - uncertainty is what costs. Simulating the resulting policy for 30,000 rollouts returns 6.8230 ± 0.0216 and 5.8769 ± 0.0188, which is the independent check that the approximation did not converge smoothly to the wrong answer.