

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

Figure 7: A policy graph (finite-state machine) obtained after two value iteration steps.

Nodes correspond to linear functions (or states of the finite-state machine) and links to dependencies between linear functions (transitions between states). Every linear function (node) is associated with an action.  To ensure that the policy can be also applied to the infinite-horizon problem, we add a cycle to the last state
(dashed line).

$$Q_{i}\,(b,a\,)=R\,(b,a\,)+\gamma\sum_{o\,\in\,\Theta}P\,(o|b,a\,)V_{i-1}\,(\tau\,(\,b,a,o\,)).$$

From this perspective, the direct strategy selects the action with the best (maximum) Q-
function for a given belief state. 7

## 2.5.3  Finite- State  Machine  Design

A more complex refinement of the above technique is to remember, for every linear function in V i , not only the action choice but also the oice of a linear function for the previous step and to do this for all observations (see Equation 7). As the same idea can be applied recursively to the linear functions for all previous steps, we can obtain a relatively complex dependency structure relating linear functions in V i , V i –1, · · V o , observations and actions that itself represents a control strategy (Kaelbling et al., 1999).

To see this, we model the structure in graphical terms (Figure 7). Here different nodes represent linear functions, actions associated with nodes correspond to optimizing actions, links emanating from nodes correspond to different observations, and successor nodes correspond to linear functions paired with observations.  Such graphs are also called policy graphs
(Kaelbling et al., 1999; Littman, 1996; Cassandra, 1998). One interpretation of the dependency structure is that it represents a collection of finite-state machines (FSMs) with many possible initial states that implement a POMDP controller: nodes correspond to states of the controller, actions to controls (outputs), and links to transitions conditioned on inputs