MaxOut (**f, B**)
Let g = {}.

Add completing rules to f: hB = bi: 0i, i = 1**, . . . , k**.

// Summing consistent rules:
While there are two consistent rules ρ1 = hc1 : v1i and ρ2 = hc2 : v2i:
If c1 = c2, then replace these two rules by hc1 : v1 + v2i; Else replace these two rules by the set: **Split**(ρ1 6 c2) ∪ **Split**(ρ2 6 c1).

// Maximizing out variable B: Repeat until f is empty:
If there are rules hc ∧ B = bi: vii, ∀bi ∈ **Dom(**B) :
Then remove these rules from f and add rule hc **: max**i vii to g; Else select two rules: ρi = hci ∧ B = bi: vii and ρj = hcj ∧ B = bj : vj i such that ci is consistent with cj , but not identical, and replace them with **Split**(ρi 6 cj ) ∪ **Split**(ρj 6 ci) .

Return g.

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

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

that: g(b**) = max**xi f(b, xi**). Such a procedure is an extension of the variable elimination**
algorithm of Zhang and Poole (Zhang & Poole, 1999).

The rule-based variable elimination algorithm maintains a set F **of value rules, initially**
containing the set of rules to be maximized. The algorithm then repeats the following steps for each variable Xi **until all variables have been eliminated:**

1. Collect all rules which depend on Xiinto fi - fi = {hc : vi ∈ F | Xi ∈ C} **— and**
remove these rules from F.

2. Perform the local maximization step over Xi: gi = MaxOut (fi, Xi);
3. Add the rules in gi to F; now, Xi **has been "eliminated."**
The cost of this algorithm is polynomial in the number of new rules generated in the maximization operation MaxOut (fi, Xi**). The number of rules is never larger and in many**
cases exponentially smaller than the complexity bounds on the table-based maximization in Section 4.2.1, which, in turn, was exponential only in the induced width **of the cost network** graph (Dechter, 1999). However, the computational costs involved in managing sets of rules usually imply that the computational advantage of the rule-based approach over the tablebased one will only be significant in problems that possess a fair amount of context-specific structure.

In the remainder of this section, we present the algorithm for computing the local maximization MaxOut (fi, Xi**). In the next section, we show how these ideas can be applied**
to extending the algorithm in Section 4.2.2 to exploit CSI in **the LP representation for** planning in factored MDPs.

The procedure, presented in Figure 13, is divided into two parts: first, all consistent rules are added together as described in Section 8.2; then, variable B **is maximized. This** maximization is performed by generating a set of rules, one for each assignment of B**, whose** contexts have the same assignment for all variables except for B**, as in Definition 8.8. This** set is then substituted by a single rule without a B **assignment in its context and with value**
equal to the maximum of the values of the rules in the original **set. Note that, to simplify**