

![0_image_0.png](0_image_0.png)

```
poli
    y iteration with an FSM model (Hansen, 1998b). The main obsta
                                                           le preventing these
                                                                           

algorithms from obtaining the optimal or 
                                         lose-to-optimal solution was the 
                                                                         omplexity of
                                                                                     

the value fun
             tion (the number of linear fun
                                           tions needed to des
                                                               ribe it) and subsequent
                                                                                     

```

running times and memory problems.

## 4.1 Approximations With Fully Observable Mdp

Perhaps the simplest way to approximate the value fun tion for a POMDP is to assume

```
that states of the pro
                     ess are fully observable (Astrom, 1965; Lovejoy, 1993). In that 
                                                                                   ase
                                                                                      

```

the optimal value fun tion V 
for a POMDP 
an be approximated as:

$$\widehat{V}(b)=\sum_{s\in S}b(s)V_{M D P}^{*}(s),$$

b(s)V MDP (s); (8)
where V MDP (s) is the optimal value fun
tion for state s for the fully observable version of the pro ess. We refer to this approximation as to the MDP approximation. The idea of the approximation is illustrated in Figure 12a. The resulting value fun tion is linear and is fully dened by values at extreme points of the belief simplex. These orrespond to the optimal values for the fully observable ase. The main advantage of the approximation is that the fully observable MDP (FOMDP) 
an be solved eÆ
iently for both the nitehorizon problem and dis ounted innite-horizon problems.14 The update step for the (fully observable) MDP is:

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

9

$$\left({8}\right)$$
