
## 4.3 Approximation With Unobservable Mdp

The MDP-approximation assumes full observability of POMDP states to obtain simpler and more efficient updates. The other extreme is to discard all observations available to the decision maker. An MDP with no observations is called unobservable MDP (UMDP) and one may choose its value-function solution as an alternative approximation.

To find the solution for the unobservable MDP, we derive the corresponding update rule, H UMDP , similarly to the update for the partially observable case. H UMDP preserves piccewise linearity and convexity of the value function and is a contraction. The update equals:

$$\widehat{V}_{i+1}(b)=\max_{a\in A}\left\{\sum_{s\in S}\rho(s,a)b(s)+\gamma\max_{\alpha_{i}\in\Gamma_{i}}\sum_{s\in S}\sum_{s^{\prime}\in S}P\big{(}s^{\prime}|s,a\big{)}b(s)\alpha_{i}\big{(}s^{\prime}\big{)}\right\}$$ $$=\big{(}H_{U\,M\,D^{p}}\,\widehat{V}_{i}\big{)}(b),$$

where Γ is a set of linear functions describing ˆ ν i +1 remains piecewise linear and convex and it consists of at most | Γ i | A | linear functions. This is in contrast to the exact update, where the number of possible vectors in the next step can grow exponentially in the number of observations and leads to | A || Γ i || Θ | possible vectors.  The time complexity of the update is O(| A || S | 2 | F i |). Thus, starting from V 0 with one linear function, the running-time complexity for k updates is bounded by O ( | A | k | S | 2 ).  The problem of finding the optimal solution for the unobservable MDP remains intractable: the finite-horizon case is NP-hard(Burago et al., 1996), and the discounted infinite-horizon case is undecidable (Madani et al., 1999). Thus, it is usually not very useful approximation.

The update H UMDP lower-bounds the exact update, an intuitive result reflecting the fact that one cannot do better with less information. To provide some insight into how the two updates are related, we do the following derivation, which also proves the bound property in an elegant way:

 $$\begin{array}{rcll}(H\hat{V_{i}})(b)&=&\\ \end{array}$$  $$\begin{array}{rcll}\geq&\\ \end{array}$$  $$\begin{array}{rcll}=&\\ \end{array}$$  $$\begin{array}{rcll}=&\\ \end{array}$$ . 
ols, a )b(s)a; (s' (H U M DP V i )( b )
We see that the difference between the exact and UMDP updates is that the max and the sum over next-step observations are exchanged. This causes the choice of α vectors in HUMDP to become independent of the observations.  Once the sum and max operations are exchanged, the observations can be marginalized out. Recall that the idea of swaps leads to a number of approximation updates; see Figure 15 for their summary.