Backproja (h) - where basis function h has scope C.

Define the scope of the backprojection: Γa(C′) = ∪X′
i∈C′**Parents**a(X′
i
).

For each assignment y ∈ Γa(C′):
g a(y) = Pc′∈C′
Qi|X′
i∈C′ Pa(c
′[X′
i
] | y)h(c
′).

Return g a.

Figure 3: Backprojection of basis function h.

linear programming algorithm. These LPs have some common characteristics: they have a small number of free variables (for k basis functions there are k + 1 free variables in approximate policy iteration and k **in approximate linear programming), but the number of**
constraints is still exponential in the number of state variables. However, in factored MDPs, these LP constraints have another very useful property: the **functionals in the constraints**
have restricted scope. This key observation allows us to represent these constraints very compactly.

First, observe that the constraints in the linear programs are all of the form:

$$\phi\geq\sum_{i}w_{i}\ c_{i}({\bf x})-b({\bf x}),\forall{\bf x},$$
$$(11)$$
wi ci(x) − b(x), ∀x, **(11)**
where only φ and w1, . . . , wk are free variables in the LP and x **ranges over all states. This**
general form represents both the type of constraint in the max-norm projection LP in (5)
and the approximate linear programming formulation in (8).3 The first insight in our construction is that we can replace the entire set of constraints in Equation (11) by one equivalent non-linear constraint:

$$\phi\geq\operatorname*{max}_{\mathbf{x}}\sum_{i}w_{i}\ c_{i}(\mathbf{x})-b(\mathbf{x}).$$
$$(12)$$

i
wi ci(x) − b(x). **(12)**
The second insight is that this new non-linear constraint can be implemented by a set of linear constraints using a construction that follows the structure of variable elimination in cost networks. This insight allows us to exploit structure in factored MDPs to represent this constraint compactly.

We tackle the problem of representing the constraint in Equation (12) in two steps:
first, computing the maximum assignment for a fixed set of weights; then, representing the non-linear constraint by small set of linear constraints, using a construction we call the factored LP. 4.2.1 Maximizing Over the State Space The key computation in our algorithms is to represent a non-linear constraint of the form in Equation (12) efficiently by a small set of linear constraints. Before presenting this construction, let's first consider a simpler problem: Given some fixed weights wi**, we would**
like to compute the maximization: φ
∗ **= max**x Pi wi ci(x) − b(x), that is, the state x**, such**