
## 4.1.1 Mdp Approximation

The MDP-approximation approa h (Equation 8) 
an be also des ribed in terms of valuefun tion updates for the belief-spa e MDP. Although this step is stri tly speaking redundant here, it simplies the analysis and omparison of this approa h to other approximations.

Let Vbi be a linear value fun
tion des
ribed by a ve
tor MDP
i 
orresponding to values of V MDP
i (s 0

) for all states s 0 2 S. Then the (i + 1)th value fun tion Vbi+1 is

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

b Vi+1 is des
ribed by a linear fun
tion with 
omponents

(

$$\alpha_{i+1}^{M D P}\left(s\right)=V_{i+1}^{M D P}\left(s\right)=\operatorname*{max}_{a}\left\{\rho\!\left(s,a\right)+\gamma\sum_{s\in S}P\!\left(s^{\prime}\middle|s,a\right)\!\alpha_{i}^{M D P}\!\left(s^{\prime}\right)\right\}.$$

)

:

The MDP-based rule HMDP 
an be also rewritten in a more general form that starts from an arbitrary pie ewise linear and onvex value fun tion Vi, represented by a set of linear fun tions i:

$$\begin{array}{r c l}{{\widehat{V}_{i+1}(b)}}&{{=}}&{{\sum_{s\in S}b(s)\operatorname*{max}_{a\in A}\left\{\rho(s,a)+\gamma\sum_{s^{\prime}\in S}P\left(s^{\prime}|s,a\right)\operatorname*{max}_{\alpha_{i}\in\Gamma_{i}}\alpha_{i}\left(s^{\prime}\right)\right\}\,,}}\end{array}$$

The appli ation of the HMDP mapping always leads to a linear value fun
tion. The update is easy to ompute and takes O(jAjjSj 2 + jijjSj) time. This redu
es to O(jAjjSj 2

)

time when only MDP-based updates are strung together. As remarked earlier, the optimal solution for the innite-horizon, dis ounted problem an be solved eÆ
iently via linear programming.

The update for the MDP approximation upper-bounds the exa t update, that is, HVbi HMDP Vbi. We show this property later in Theorem 9, whi
h 
overs more 
ases. The intuition is that we annot get a better solution with less information, and thus the fully observable MDP must upper-bound the partially observable ase.

## 4.1.2 Approximation With Q-Fun Tions (Qmdp)

A variant of the approximation based on the fully observable MDP uses Q-fun tions (Littman, Cassandra, & Kaelbling, 1995):

$${\widehat{V}}(b)=\operatorname*{max}_{a\in A}\,\sum_{s\in S}b(\,s\,)Q_{\,\,M\,D P}^{\,\ast}\left(s,a\,\right),$$

where

$$Q_{M D P}^{*}(s,a)=\rho(s,a)+\gamma\sum_{s^{\prime}\in S}P(\,s^{\prime}|s,a\,)V_{M D P}^{*}(\,s^{\prime}\,)$$

is the optimal a tion-value fun tion (Q-fun tion) for the fully observable MDP. The QMDP

approximation Vb is pie ewise linear and onvex with jAj linear fun tions, ea h orresponding
