RB variables st and lt, we need to perform the evidence reversal step. 7  This can be done by positioning the root of the belief chain C t at s t and reverse the link from s t to o t . This gives us the network structure for B f = B t (s t,l t, t f f [ ] o t ] which is exactly the same as B t
(see Fig. 15), except that the evidence o t has been absorbed into the marginal distribution of s t . The weight w t = B t ( o t ) can also be obtained as a by-product of this evidence reversal step. In order to sample st and l from B fr without the need to compute the marginal distribution for these two variables, we can use forward sampling to sample every variable of B f r , starting from the root node s t and proceeding upward. Since l t by definition is the highest level of policy termination, the sampling can stop at the first level k where ξ = F .

We can then assign l the value k - 1. Any unnecessary samples for the policy nodes along the way are discarded. Once we have the new samples for st and lt, the updating of the RB belief state from B t to B t+1 is identical to the belief state updating procedure described in 5.1. The h function can then be obtained by computing the corresponding marginal of the new belief chain C t +1 At each time step, the complexity of maintaining a sample (sampling the new RB
variables and updating the RB belief state) is again O ( t ), and thus, on average, bounded by a constant. The overall complexity of maintaining every sample is thus O ( N ) on average. If a prediction is needed, for each sample, we have to compute h by manipulating the chain C t +1 with the complexity O ( K ). Thus the complexity at the time step when a prediction needs to be made is O ( NK ).

In comparison with the use of an SIS method such as LW-ER, the RB-SIS has the same order of computational complexity (the SIS also has complexity O ( N K )). However, while the SIS method needs to sample every layers of the AHMM, the RB-SIS method only needs to sample two sequences of variables št, lt, and avoids having to sample the K policy sequences { 7 }. After Rao-Blackwellisation, the dimension of the sample space becomes much smaller, and more importantly, does not grow with K . As a result, the accuracy of the approximation by the RB-SIS method does not depend on the height of the hierarchy K. In contrast, due to the problems of sampling in high dimensional space, the accuracy of SIS methods tends to degrade, especially when K is large.

## 5.2.2  Performing Evidence Reversal With A Factored State Space

In many cases, the state space S is the Cartesian product of many state variables representing relatively independent properties of a state: s t = (s t , s t , . . , s t M ). Since the overall state space is very large, specifying an action by the usual transition probability matrix is problematic. It is advantageous in this case to represent the state information in a factored form, i.e., representing each state variable s m in a separate node rather than lumping them into a single node st. It has been shown that using factored representations, we can specify the transition probability of each action in a compact form since an action is likely to affect only a small number of state variables and the specification of the effects of actions has many regularities (Boutilier et al., 2000).