machine, indicating whether it is working or not. Each basis **function has scope restricted**
to Xi**. These are represented as diamonds in the next time step in Figure 2(b).**
Factored value functions provide the key to performing efficient computations over the exponential-sized state spaces we have in factored MDPs. The main insight is that restricted scope functions (including our basis functions) allow for certain basic operations to be implemented very efficiently. In the remainder of this section, we show how structure in factored MDPs can be exploited to perform two crucial operations very efficiently: one-step lookahead (backprojection), and the representation of exponentially many constraints in the LPs. Then, we use these basic building blocks to formulate very efficient approximation algorithms for factored MDPs, each presented in its own **self-contained section: the**
approximate linear programming for factored MDPs in Section 5, and approximate policy iteration with max-norm projection in Section 6.

## 4.1 One-Step Lookahead

A key step in all of our algorithms is the computation of the one-step lookahead value of some action a**. This is necessary, for example, when computing the greedy policy as in**
Equation (1). Let's consider the computation of a Q function, Qa(x**), which represents the**
expected value the agent obtains after taking action a **at the current time step and receiving** a long-term value V thereafter. This Q **function can be computed by:**

$$Q_{a}({\bf x})=R({\bf x},a)+\gamma\sum_{{\bf x}^{\prime}}P({\bf x}^{\prime}\mid{\bf x},a){\mathcal V}({\bf x}).$$
$$(9)$$

′| x, a)V(x). (9)
That is, Qa(x) is given by the current reward plus the discounted expected **future value.** Using this notation, we can express the greedy policy as: Greedy(V)(x**) = max**a Qa(x).

Recall that we are estimating the long-term value of our policy using a set of basis functions: V(x) = Pi wi hi(x**). Thus, we can rewrite Equation (9) as:**

$$Q_{a}({\bf x})=R({\bf x},a)+\gamma\sum_{{\bf x}^{\prime}}P({\bf x}^{\prime}\mid{\bf x},a)\sum_{i}w_{i}\ h_{i}({\bf x}).\tag{10}$$

The size of the state space is exponential, so that computing **the expectation** Px′ P(x
′| x, a)Pi wi hi(x) seems infeasible. Fortunately, as discussed by Koller and **Parr (1999),**
this expectation operation, or backprojection, can be performed efficiently if the transition model and the value function are both factored appropriately. The linearity of the value function permits a linear decomposition, where each summand in the expectation can be viewed as an independent value function and updated in a manner similar to the value iteration procedure used by Boutilier et al. **(2000). We now recap the construction briefly,** by first defining:

$$G^{a}({\bf x})=\sum_{{\bf x}^{\prime}}P({\bf x}^{\prime}\mid{\bf x},a)\sum_{i}w_{i}\ h_{i}({\bf x}^{\prime})=\sum_{i}w_{i}\sum_{{\bf x}^{\prime}}P({\bf x}^{\prime}\mid{\bf x},a)h_{i}({\bf x}^{\prime}).$$

Thus, we can compute the expectation of each basis function separately:

$$g_{i}^{a}({\bf x})=\sum_{{\bf x}^{\prime}}P({\bf x}^{\prime}\mid{\bf x},a)h_{i}({\bf x}^{\prime}),$$
