Partially Observable MDP

A Markov Decision Process together with a Sensor Model OO that has the Sensor Markov Property and is stationary, which means

O(s,e)=P(e∣s).O(s,e)=P(e\mid s).

This models a partially observable and stochastic environment. As the Agent does not know which state it is in, it makes no sense to talk about policies that map concrete states to Actions.
Thus we introduce the Optimal Policy as a function

π∗(b)\pi^*(b)

that maps belief states to actions instead.

Now the idea is to convert a POMDP into an MDP in Belief State space. Which means we want to have a Transition Model on the belief states and a reward function on the belief states.

Filtering at the Belief State Level

b′(s′)=FORWARD⁡(b,a,e)=α⋅P(e∣s′)⋅(∑sP(s′∣s,a)⋅b(s))b^{\prime}\left(s^{\prime}\right)=\operatorname{FORWARD}(b,a,e)=\alpha \cdot P\left(e \mid s^{\prime}\right) \cdot\left(\sum_s P\left(s^{\prime} \mid s, a\right) \cdot b(s)\right)

[!orange-highlight]- Overview Formula
IMG_C57EF646A1A7-1.jpeg
Transition Model
Sensor Model
Belief State

POMDP Decision Cycle

  • Given current Belief State bb, execute Action a=π∗(b)a=\pi^*(b)
  • Receive Percept ee
  • Update Belief State with FORWARD⁡(b,a,e)\operatorname { FORWARD }(b, a, e)

Reducing POMDPs to Belief State MDPs

Transition Model at the Belief State level

P(b′∣b,a)=P(b′∣a,b)=∑eP(b′∣e,a,b)⋅P(e∣a,b)=∑eP(b′∣e,a,b)⋅(∑s′P(e∣s′)⋅(∑sP(s′∣s,a),b(s)))\begin{aligned} P\left(b^{\prime} \mid b, a\right) & =P\left(b^{\prime} \mid a, b\right)=\sum_e P\left(b^{\prime} \mid e, a, b\right) \cdot P(e \mid a, b) \\ & =\sum_e P\left(b^{\prime} \mid e, a, b\right) \cdot\left(\sum_{s^{\prime}} P\left(e \mid s^{\prime}\right) \cdot\left(\sum_s P\left(s^{\prime} \mid s, a\right), b(s)\right)\right) \end{aligned}

where P(b′∣e,a,b)P\left(b^{\prime} \mid e, a, b\right) is 11 if b′=FORWARD⁡(b,a,e)b^{\prime}=\operatorname{FORWARD}(b, a, e) and 0 otherwise.

Reward function at the Belief State level.

ρ(b):=∑sb(s)⋅R(s)\rho(b):=\sum_s b(s) \cdot R(s)

The expected reward for the states the Agent might be in.

Now we reduced the POMDP to a Markov Decision Process with a Transition Model

P(b′∣b,a)P\left(b^{\prime} \mid b, a\right)

and a reward function

ρ(b).\rho(b).

This is actually observable now as the Belief State state is always observable.

An Optimal Policy on this MDP is also an optimal policy on the POMDP.