AHMM network in the previous section suggests that the problem of inference in the AHMM can be tractable in the special case when the history of the state and terminating status variables is known. Motivated by this property of the AHMM, our main aim in this section is to derive a hybrid inference scheme that combines both approximation and tractable exact inference for efficiency. We first treat the special case of policy recognition where the belief state of the AHMM has a tractable structure in 5.1. We then present a hybrid inference scheme for the general case using the Rao-Blackwellised Sequential Importance Sampling (RB-SIS) method in 5.2.

## 5.1  Policy Recognition: The Tractable Case

Here, we address the policy recognition problem under two assumptions: (1) the state ssequence can be observed with certainty, and (2) the exact time when each policy starts and ends is known. More precisely, our observation at time t includes the state history š t = (so, . . , s t ) and the policy termination history l t = ( lo, . . , l t ). The belief state that we need to compute in this case is Bt = Pr(πfll, st,lt | št-1, lt-1) and its posterior after absorbing the observation at time t: B t + = P r( π f f | š t, ˆ l t ).

The first assumption means that the observer always knows the true current state and is often referred to as "full observability". When the states are fully observable, we can ignore the observation layer { o t } in the AHMM and thus only have to deal with the AMM instead.

The second assumption means that the observer is fully aware when the current policy ends and a new policy begins. If the policy hierarchy is constructed from the region-based decomposition of the state space (subsection 3.2), the termination status can be inferred directly from the state sequence. Thus for SRD policy hierarchies, only the full observability condition is needed since the second assumption is subsumed by the first and can be left out. Except for SRD policy hierarchies, these two assumptions are usually too restrictive for the policy recognition algorithm presented here to be useful by itself. However, the algorithm for this special case will form the exact step in the hybrid algorithm presented in subsection 5.2 for the general case.

## 5.1.1 Representation Of The Belief State

We first look at the conditional joint distribution Pr( π fil, st | št –1, št –1). From the termination history lt –1, we can derive precisely the starting time of the current level-k policy:

$\tau_{t}^{k}=\max\{0\}\cup\{t^{\prime}<t|\ e_{t^{\prime}}^{k}=T\}=\max\{0\}\cup\{t^{\prime}<t|\,l_{t^{\prime}}\geq k\}$.  
On the other hand, knowing the starting time together with the state history also gives us the starting state H . Thus, both the starting time and the starting state of π f can be derived from š t –1 and l t –1. From Theorem 1, we obtain for all level k :

$$\pi_{\,\,\,t}^{\,\geq\,k}\,\perp\pi_{\,\,\,t}^{\,<\,k}\,\bigm|\,\pi_{\,\,\,t}^{k}\,,\,\tilde{s}_{t-1}\,,\,\tilde{l}_{t-1}\,.$$

In other words, given š t –1 and ˆ ı t –1, the conditional joint distribution of { π t can be represented by a Bayesian network with a simple chain structure. We denote this chain network by C t ≡ Pr(π f l t ′ s t ′ š t − 1 , Í t − 1 ) and term it the belief chain for the role it plays in the representation of the belief state (Fig. 11(a)). If a chain is drawn so that all links