Planning Under Uncertainty: MDPs and POMDPs

Real moves do not always go as planned: a wheel slips, a door sticks. A Markov decision process plans for that by valuing each state by its expected future reward. When the robot also cannot be sure where it is, the problem becomes a partially observable MDP, where the robot plans over its beliefs and may choose to gather information first.

Chance a move slips sideways Discount γ POMDP: belief the goal is behind the left door POMDP: cost of looking first

Value iteration

Each state's value is the best expected reward over actions, counting future rewards with a discount $\gamma$. Repeating this update until it stops changing gives the optimal values and policy:

$$V(s) \leftarrow \max_a \sum_{s'} P(s' \mid s, a)\,\big[R(s, a, s') + \gamma\,V(s')\big]$$

Acting under a belief

In a POMDP the robot keeps a belief $b$, a probability over states. Here it must pick the left or right door, and the reward is behind only one. Acting now earns the expected reward under its belief. Looking first costs a little but reveals the answer, so its value is the reward minus the cost:

$$V_{\text{act}} = \max(b,\ 1 - b)\cdot 10 - \min(b,\ 1-b)\cdot 10 \qquad V_{\text{look}} = 10 - c_{\text{look}}$$

What to notice

With no slipping, the policy hugs the pit on the shortest route. Add slip and the arrows swing away from the pit, accepting a longer path to avoid falling in. In the POMDP chart, when the robot is unsure, a belief near one half, looking first is worth its cost. When it is already fairly sure, it should just act.