process description and the structure of our basis functions. In problems where the actions modify a large number of variables, the policy representation could become unwieldy. The approximate linear programming approach in Section 5 is more appropriate in such cases, as it does not require an explicit representation of the policy.

## 6.3 Value Determination

In the approximate value determination step our algorithm computes:
w(t) **= arg min**
wkHw − (Rπ(t) + γPπ(t)Hw)k∞ .

By rearranging the expression, we get:
w
(t) **= arg min**
wk(H − γPπ(t)H) w − Rπ(t)k∞ .

This equation is an instance of the optimization in Equation (4). If Pπ(t) **is factored, we can**
conclude that C = (H − γPπ(t)**H) is also a matrix whose columns correspond to restrictedscope functions. More specifically:**

$$c_{i}(\mathbf{x})=h_{i}(\mathbf{x})-\gamma g_{i}^{\pi^{(t)}}(\mathbf{x}),$$

where g π
(t)
iis the backprojection of the basis function hi **through the transition model** Pπ(t) ,
as described in Section 4.1. The target b = Rπ(t) **corresponds to the reward function, which**
for the moment is assumed to be factored. Thus, we can again apply our factored LP in Section 4.2.3 to estimate the value of the policy π
(t).

Unfortunately, the transition model Pπ(t) **is not factored, as a decision list representation for the policy** π
(t) will, in general, induce a transition model Pπ(t) **which cannot be**
represented by a compact DBN. Nonetheless, we can still generate a compact LP by exploiting the decision list structure of the policy. The basic idea is to introduce cost networks corresponding to each branch in the decision list, ensuring, additionally, that only states consistent with this branch are considered in the cost network maximization. Specifically, we have a factored LP construction for each branch hti, aii. The i**th cost network only**
considers a subset of the states that is consistent with the i**th branch of the decision list.**
Let Si be the set of states x such that ti**is the first event in the decision list for which** x is consistent. That is, for each state x ∈ Si, x is consistent with ti, but it is not **consistent** with any tj with **j < i**.

Recall that, as in Equation (11), our LP construction defines **a set of constraints that**
imply that φ ≥Pi wi ci(x) − b(x) for each state x**. Instead, we have a separate set of**
constraints for the states in each subset Si. For each state in Si**, we know that action** aiis taken. Hence, we can apply our construction above using Pai **— a transition model which is**
factored by assumption - in place of the non-factored Pπ(t) **. Similarly, the reward function**
becomes Rai (x) + Pr i=1 Ri(x**) for this subset of states.**
The only issue is to guarantee that the cost network constraints derived from this transition model are applied only to states in Si**. Specifically, we must guarantee that they are**
applied only to states consistent with ti**, but not to states that are consistent with some**
tj for j < i. To guarantee the first condition, we simply instantiate the **variables in** Ti to take the values specified in ti**. That is, our cost network now considers only the variables in**