

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

## 3.2.1 Randomized Poli Ies

By restri ting the spa e of poli ies we simplify the poli y optimization problem. On the other hand, we simultaneously give up an opportunity to nd the best optimal poli y, repla
-

ing it with the best restri ted poli y. Up to this point, we have onsidered only deterministi poli ies with a xed number of internal ontroller states, that is, poli ies with deterministi output and transition fun tions. However, nding the best deterministi poli y is not always the best option: randomized poli ies, with randomized output and transition fun tions, usually lead to the far better performan e. The appli ation of randomized (or sto hasti
)

poli ies to POMDPs was introdu ed by Platzman (1980). Essentially, any deterministi poli y an be represented as a randomized poli y with a single a tion and transition, so that the best randomized poli y is no worse than the best deterministi poli y. The dieren e in ontrol performan e of two poli ies shows up most often in ases when the number of states of the ontroller is relatively small ompared to that in the optimal strategy.

The advantage of sto hasti poli ies is that their spa e is larger and parameters of the poli y are ontinuous. Therefore the problem of nding the optimal sto hasti poli y be omes a non-linear optimization problem and a variety of optimization methods an be applied to solve it. An example is the gradient-based approa h (see Meuleau et al., 1999).

## 4. Value-Fun Tion Approximation Methods

In this se tion we dis uss in more depth value-fun tion approximation methods. We fous on approximations with belief information spa e.12 We survey known te hniques, but also in lude a number of new methods and modi ations of existing methods. Figure 10 summarizes the methods overed. We des ribe the methods by means of update rules they
