
## 8. Exploiting Context-Specific Structure

Thus far, we have presented a suite of algorithms which exploit additive structure in the reward and basis functions and sparse connectivity in the DBN representing the transition model. However, there exists another important type of structure that should also be exploited for efficient decision making: context-specific independence **(CSI). For example,** consider an agent responsible for building and maintaining **a house, if the painting task can** only be completed after the plumbing and the electrical wiring have been installed, then the probability that the painting is done is 0, in all contexts where plumbing or electricity are not done, independently **of the agents action. The representation we have used so far in** this paper would use a table to represent this type of function. This table is exponentially large in the number of variables in the scope of the function, **and ignores the context-specific** structure inherent in the problem definition.

Boutilier et al. (Boutilier et al.**, 1995; Dearden & Boutilier, 1997; Boutilier, Dean, &**
Hanks, 1999; Boutilier et al.**, 2000) have developed a set of algorithms which can exploit CSI** in the transition and reward models to perform efficient (approximate) planning. Although this approach is often successful in problems where the value function **contains sufficient** context-specific structure, the approach is not able to exploit the additive structure which is also often present in real-world problems.

In this section, we extend the factored MDP model to include context-specific structure.

We present a simple, yet effective extension of our algorithms which can exploit both CSI
and additive structure to obtain efficient approximations for factored MDPs. We first extend the factored MDP representation to include context-specific structure and then show how the basic operations from Section 4 required by our algorithms can be performed efficiently in this new representation.

## 8.1 Factored Mdps With Context-Specific And Additive Structure

There are several representations for context-specific functions. The most common are decision trees (Boutilier et al.**, 1995), algebraic decision diagrams (ADDs) (Hoey, St-Aubin,** Hu, & Boutilier, 1999), and rules (Zhang & Poole, 1999). We choose to use rules as our basic representation, for two main reasons. First, the rule-based representation allows a fairly simple algorithm for variable elimination, which is **a key operation in our framework.** Second, rules are not required to be mutually exclusive and exhaustive, a requirement that can be restrictive if we want to exploit additive independence, where functions can be represented as a linear combination of a set of non-mutually **exclusive functions.**
We begin by describing the rule-based representation (along the lines of Zhang and Poole's presentation (1999)) for the probabilistic transition model, in particular, the CPDs of our DBN model. Roughly speaking, each rule corresponds to **some set of CPD entries**
that are all associated with a particular probability value. These entries with the same value are referred to as consistent **contexts:**
Definition 8.1 Let C ⊆ {X, X′} and c ∈ Dom(C). We say that c is consistent **with**
b ∈ Dom(B), for B ⊆ {X, X′}, if c and b **have the same assignment for the variables in**
C ∩ B.

The probability of these consistent contexts will be represented by **probability rules**: