

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

Figure 30: Factored model illustrating model-reduction techniques.

Figure 31: Models involving aggregate states: (a) the model corresponding to the initial

partition and (b) the minimal model.

The initial partition shown in Figure 31(a) is dened in terms of immediate rewards.

We say that all the states in particular starting cluster behave the same with respect

to particular destination cluster if the probability of ending up in the destination

$$\overline{{C R}}$$
cluster is the same for all states in the starting cluster. This property is not satised

1997) and MDPs (Dean Givan, 1997). The basic step of splitting cluster is closely

the model reduction approach apply when the action space is large and represented in

factored form (Dean, Givan, Kim, 1998); for example, when each action is specied

by set of parameters such as those corresponding to the allocations of several dierent

resources in an optimization problem. There also exist algorithms for computing approxi-

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

$$C R$$
$$\mathbb{N}$$

$$\overline{{C R}}$$
for starting cluster CR and destination cluster CR in Figure 31(a), and so we split the

for all pairs of clusters and the model in Figure 31(b) is the minimal model. 2

cluster labeled CR to obtain the model in Figure 31(b). Now the property is satised

The Lee and Yannakakis algorithm for non-deterministic nite-state machines has been extended by Givan and Dean to handle classical Strips planning problems (Givan Dean, related to goal regression, relationship explored in (Givan Dean, 1997). Variants of
