Partially Observed Markov Decision Processes
Contents
In the previous chapter we focused on MDPs in a known environment, i.e. a fully observable setting. We saw that we can efficiently find an optimal policy (as long as the MDP is finite).
In this chapter we extend the Markov decision process to a partially observable setting, in which the agent only sees noisy observations \(Y_t\) of its state \(X_t\).
A Partially Observed Markov Decision Process is specified by:
- a set of states \(X\);
- a set of actions \(A\);
- transition probabilities \(p(x' \mid x, a)\);
- a reward function \(r(x, a)\);
- a set of observations \(Y\);
- observation probabilities \(o(y, x) = P(Y_t = y \mid X_t = x)\).
Note that MDPs are controlled Markov chains, whereas POMDPs are controlled Hidden Markov Models.
POMDPs can be viewed as MDPs with an enlarged state space (\(X + Y\)). The idea is to consider an MDP whose states are beliefs:
\[b_t(x) = P(X_t = x \mid y_{1:t}, a_{1:t-1}),\]i.e. probability distributions over the states of the POMDP. At \(t = 0\) we have \(b_0(x) = P(X_0 = x)\), the (deterministic) initial belief.
Given an action \(a_t\), prior belief \(b_t\) and a new observation, the dynamics are
\[x_{t+1} \sim P(\cdot \mid x_t, a_t), \qquad y_{t+1} \sim P(\cdot \mid x_{t+1}),\]and the belief update is
\[\begin{aligned} b_{t+1}(x) &= \mathbb{P}(X_{t+1} = x \mid y_{1:t+1}, a_{1:t}) \\[4pt] &= \tfrac{1}{Z}\, \mathbb{P}(y_{t+1} \mid X_{t+1} = x)\, \mathbb{P}(X_{t+1} = x \mid y_{1:t}, a_{1:t}) && \text{(Bayes' rule)} \\[4pt] &= \tfrac{1}{Z}\, o(y_{t+1} \mid x)\, \mathbb{P}(X_{t+1} = x \mid y_{1:t}, a_{1:t}) && \text{(definition of } o\text{)} \\[4pt] &= \tfrac{1}{Z}\, o(y_{t+1} \mid x) \sum_{x' \in X} p(x \mid x', a_t)\, \mathbb{P}(X_t = x' \mid y_{1:t}, a_{1:t-1}) && \text{(condition on } x'\text{)} \\[4pt] &= \tfrac{1}{Z}\, o(y_{t+1} \mid x) \sum_{x' \in X} p(x \mid x', a_t)\, b_t(x') && \text{(definition of } b_t\text{)}, \end{aligned}\]where
\[Z \;\doteq\; \sum_{x \in X} o(y_{t+1} \mid x) \sum_{x' \in X} p(x \mid x', a_t)\, b_t(x').\]Therefore the updated belief state is a deterministic mapping from the previous belief, depending only on the random observation \(y_{t+1}\).