(observations). The start state of the FSM controller is osen greedily by selecting the linear function (controller state) optimizing the value of an initial belief state.

The advantage of the finite-state machine representation of the strategy is that for the first i steps it works with observations directly; belief-state updates are not needed. This contrasts with the other two policy models (lookahead and direct models), which must keep track of the current belief state and update it over time in order to extract appropriate control. The drawback of the approach is that the FSM controller is limited to i steps that correspond to the number of value iteration steps performed. However, in the infinitehorizon model the controller is expected to run for an infinite number of steps.  One way to remedy this deficiency is to extend the FSM structure and to create cycles that let us visit controller states repeatedly. For example, adding a cycle transition to the end state of the FSM controller in Figure 7 (dashed line) ensures that the controller is also applicable to the infinite-horizon problem.

## 2.6  Policy Iteration

An alternative method for finding the solution for the discounted infinite-horizon problem is policy iteration (Howard, 1960; Sondik, 1978). Policy iteration seares the policy space and gradually improves the current control policy for one or more belief states.  The method consists of two steps performed iteratively:
- policy evaluation : computes expected value for the current policy;
- policy improvement : improves the current policy.

As we saw in Section 2.5, there are many ways to represent a control policy for a POMDP. Here we restrict attention to a finite-state machine model in which observations correspond to inputs and actions to outputs (Platzman, 1980; Hansen, 1998b; Kaelbling et al., 1999). 8

## 2.6.1  Finite-State Machine Controller

A finite-state machine (FSM) controller C = (M, Θ, A, φ, η, ψ) for a POMDP is described by a set of memory states M of the controller, a set of observations (inputs) O, a set of actions (outputs) A, a transition function φ : M × Θ → M mapping states of the FSM to next memory states given the observation, and an output function η : M → A mapping memory states to actions. A function ψ : I 0 → M selects the initial memory state given the initial information state. The initial information state corresponds either to a prior or a posterior belief state at time to depending on the availability of an initial observation.

## 2.6.2 P Olicy E Valuation

The first step of the policy iteration is policy evaluation. The most important property of the FSM model is that the value function for a specific FSM strategy can be computed efficiently in the number of controller states M . The key to efficient computability is the