

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

These two problems involve n binary variables X1, . . . , Xn and n **deterministic actions**
a1, . . . , an. The reward is 1 when all variables Xk are true**, and is 0 otherwise. The problem**
is discounted by a factor γ = 0.99. The difference between the Linear and the **Expon**
problems is in the transition probabilities. In the Linear problem, the action ak **sets the**
variable Xk to true and makes all succeeding variables, Xifor i > k, false**. If the state space**
of the Linear **problem is seen as a binary number, the optimal policy is to set repeatedly the**
largest bit (Xk variable) which has all preceding bits set to true**. Using an ADD, the optimal**
value function for this problem can be represented in linear space, with n**+1 leaves (Boutilier**
et al.**, 2000). This is the "best-case" for Apricodd, and the algorithm can compute this value**
function quite efficiently. Figure 19(a) compares the running time of Apricodd to that of one of our algorithms with indicator basis functions between pairs of consecutive variables. Note that both algorithms obtain the same policy in polynomial time in the number of variables. However, in such structured problems, the efficient implementation of the ADD package used in Apricodd makes it faster in this problem.

On the other hand, the Expon **problem illustrates the worst-case for Apricodd. In this**
problem, the action ak sets the variable Xk to true, if all preceding variables, Xifor i < k**, are**
true, and it makes all preceding variables false**. If the state space is seen as a binary number,** the optimal policy goes through all binary numbers in sequence, by repeatedly setting the largest bit (Xk variable) which has all preceding bits set to true**. Due to discounting, the**
optimal value function assigns a value of γ 2 n−j−1to the j**th binary number, so that the**
value function contains exponentially many different values. Using an ADD, the optimal value function for this problem requires an exponential number of leaves (Boutilier **et al.**, 2000), which is illustrated by the exponential running time **in Figure 19(b). However,** the same value function can be approximated very compactly as a factored linear value function using n + 1 basis functions: an indicator over each variable Xk **and the constant**
base. As shown in Figure 19(b), using this representation, our factored approximate linear programming algorithm computes the value function in polynomial time. Furthermore, the