

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

Denition 2 (Abstra t Poli y). Let  be a set of abstra t poli ies. An abstra t poli y over the poli ies in  is a tuple hS ; D ;  ;  i where:
 S  [2S is the set of appli
able states.

 D  [2D is the set of destination states.  : D ! (0; 1℄ is the set of stopping probabilities.

  : S -  ! [0; 1℄ is the sele
tion fun
tion where  (s; ) is the probability that sele ts the poli y  at the state s.

Note the re ursiveness in denition 2 that allows an abstra t poli y to sele t among a set of other abstra t poli ies. At the base level, primitive a tions are viewed as abstra t poli ies themselves. Sin e primitive a tions always stop after one time-step, Da  Sa and (d) =
1 8d 2 Da (Sutton et al., 1999). The idea that poli
ies with suitable stopping 
ondition an be viewed just as primitive a tions is rst made expli it in (Sutton, 1995), whi h also introdu es the  model for representing the stopping probabilities. Their subsequent work (Sutton et al., 1999) introdu es the abstra t poli y on ept under the name options.

The exe ution of an abstra t poli y is as follows. Starting from some state s, sele ts a poli y  2  a ording to the distribution  (s; :). The sele
ted poli
y  is then exe uted until it is terminated in some state d 2 D . If d is also a destination state of 
(d 2 D ), the poli
y stops with probability  (d). If still 
ontinues, a new poli
y 0 2  is sele ted by at d, whi h will be exe uted until its termination and so on (Fig. 3).

Some remarks about the representation of an abstra t poli y are needed here. Let s 2 [2S, we denote the subset of poli
ies in  whi
h are appli
able at s by (s) =
f 2  j s 2 Sg. For an abstra
t poli
y to be well-dened, we have to make sure that at ea h state s, only sele ts among the poli ies that are appli able at s. Thus, the sele tion fun tion has to be su h that  (s; ) > 0 only if  2 (s). This helps to keep the spe i ation of the sele tion fun tion to a manageable size, even when the set of all poli ies  to be hosen from an be large. In addition, the spe i ation of the sele tion fun tion and the stopping probabilities an make use of fa tored representations (Boutilier, Dearden, & Goldszmidt, 2000) in the ase where the state spa e is the omposite of a set of relatively independent variables. This ensures that we still have a ompa t spe i ation
