

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

Figure 8: An example of a four-state FSM poli y. Nodes represent states, links transitions between states (
onditioned on observations). Every memory state has an asso iated ontrol a tion (output).

```
fa
  t that the value fun
                tion for exe
                         uting an FSM strategy from some memory state x is
                                                               

```

linear (Platzman, 1980).9

```
Theorem 5 Let C be a nite-state ma
                            hine 
                                ontrol ler with a set of memory states M.
                                                             

```

The value fun tion for applying C from a memory state x 2 M, V C
(x; b), is linear. Value

```
fun
   tions for al l x 2 M 
                  an be found by solving a system of linear equations with jSjjMj
                                                               

```

variables.

We illustrate the main idea by an example. Assume an FSM 
ontroller with four memory states fx1; x2; x3; x4g, as in Figure 8, and a sto
hasti pro
ess with two hidden states S =
fs1; s2g. The value of the poli
y for an augmented state spa
e S - M satises a system of linear equations

$$\begin{array}{r l}{V\big(x_{1},\,s_{1}\big)}&{{}=}\\ {}&{}&{}\\ {V\big(x_{1},\,s_{2}\big)}&{{}=}\\ {}&{}&{}\\ {V\big(x_{2},\,s_{1}\big)}&{{}=}\\ {}&{}&{}\\ {V\big(x_{4},\,s_{2}\big)}&{{}=}\end{array}$$

V (x1; s1) = (s1; (x1)) +  X
$$\begin{array}{l}{{\rho(s_{1},\eta(x_{1}))+\gamma\sum_{o\in\Theta}\sum_{s\in S}P(o,s|s_{1},\eta(x_{1}))V(\phi(x_{1},o),\,s)}}\\ {{\rho(s_{2},\eta(x_{1}))+\gamma\sum_{o\in\Theta}\sum_{s\in S}P(o,s|s_{2},\eta(x_{1}))V(\phi(x_{1},o),\,s)}}\\ {{\rho(s_{1},\eta(x_{2}))+\gamma\sum_{o\in\Theta}\sum_{s\in S}P(o,s|s_{1},\eta(x_{2}))V(\phi(x_{2},o),\,s)}}\\ {{\rho(s_{2},\eta(x_{4}))+\gamma\sum_{o\in\Theta}\sum_{s\in S}P(o,s|s_{2},\eta(x_{4}))V(\phi(x_{4},o),\,s),}}\end{array}$$

V (x1; s2) = (s2; (x1)) +  X

V (x2; s1) = (s1; (x2)) +  X

V (x4; s2) = (s2; (x4)) +  X

where (x) is the a
tion exe
uted in x and (x; o) is the state to whi
h one transits after seeing an input (observation) o. Assuming we start the poli y from the memory state x1, the value of the poli y is:

V C
(x1; b) = X
s2S

V (x1; s)b(s):