Stanford AA228 Decision Making Under Uncertainty | Autumn 2025 | Offline Belief State Planning

Exact value iteration explodes exponentially

For a small POMDP with just two actions and observations, exact methods must track up to 10^338 conditional plans for a 10-step horizon, making optimal solutions impossible for moderate problem sizes.

Belief space MDPs face continuous state spaces

Formulating POMDPs as belief state MDPs results in continuous state spaces that are computationally prohibitive to solve exactly using standard techniques.

Solve as MDP, execute with belief weighting

QMDP ignores partial observability during planning to compute standard MDP Q-values, then selects actions by taking the belief-weighted average of these values during execution.

Deployed in ACAS X collision avoidance

This computationally efficient approach powers the ACAS X aircraft collision avoidance system, where it prevents mid-air collisions by interpolating pre-computed state values based on current belief distributions.

One alpha vector per action representation

QMDP can be viewed as maintaining a single alpha vector for each action, where each vector entry stores the expected utility for a specific state under that action.

Alpha vectors store state-conditional utilities

Each alpha vector contains one entry per state representing the expected future utility if the agent were actually in that particular state and followed the associated policy.

Value function as belief-weighted sum

The estimated value of a belief state is computed by taking the dot product between the belief probability distribution and the relevant alpha vector entries.