

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

point away from the level-k node, we say that the chain has root at level k . The root of the chain can be moved from k to another level k ′ simply by reversing the links lying between k and k ′ using the standard link-reversal operation for Bayesian networks (Shachter, 1986).

Each node in the belief chain also has a manageable size. In principle, the domain of π k is Π k , the set of all policies at level k , and the domain of s t is S , the set of all possible states. When K is large, we basically want to model a larger state space, and the set of policies to cover this state space is also large. The sizes of these domains would most likely grow exponential w.r.t. K. However, given a particular state, the number of policies applicable at that state would remain relatively constant and independent of K . For each policy π t , we know its starting state b t , which implies that π t ∈ Π k ( t ), the set of all level- k policies applicable at b k . Thus Π k ( H ) can be used as the "local" domain for π k to avoid the exponential dependency on K . Similarly, the domain for s t can be taken as the set of neighbouring states of s t − 1 (reachable from s t − 1 by performing one primitive action). For a given state, we term the maximum number of relevant objects (applicable policies/actions, neighbouring states) at a single level the degree of connectivity N of the domain being modelled. The size of the conditional probability table for each link of the belief chain is then O(N 2 ), and the overall size of the belief chain is O(KN 2 ).

We now can construct the belief state B t from C t . Since the current terminating status is solely determined by the current policies and the current state, the belief state B t can be factorised into:

$$\Pr\bigl(\pi_{t}^{a l},s_{t},l_{t}\mid\hat{s}_{t-1},\hat{l}_{t-1}\bigr)=\Pr\bigl(l_{t}\mid\pi_{t}^{a l},s_{t}\bigr)\Pr\bigl(\pi_{t}^{a l},s_{t}\mid\hat{s}_{t-1},\hat{l}_{t-1}\bigr)=\Pr\bigl(l_{t}\mid\pi_{t}^{a l l},s_{t}\bigr){\mathcal C}_{t}$$

Note that the variable l is equivalent to the set of variables {eff,...,ef}. Thus, the full belief state B t can be realised by adding to C t the links from the current policies and the current state to the terminating status variables & (Fig. 11(b)). The size of the belief state