We can now characterize the concept of local rewards. Let Ra 1
, . . . , Ra r **be a set of**
functions, where the scope of each Ra i is restricted to variable cluster Ua i ⊂ {X1**, . . . , X**n}.

The reward for taking action a at state x is defined to be Ra(x) = Pr i=1 Ra i
(Ua i
) ∈ R**. In**
our example, we have a reward function Ri associated with each machine i**, which depends** only Xi**, and does not depend on the action choice. These local rewards are represented**
by the diamonds in Figure 2(b), in the usual notation for influence diagrams (Howard & Matheson, 1984).

## 3. Approximate Solution Algorithms

There are several algorithms to compute the optimal policy in an MDP. The three most commonly used are value iteration, policy iteration, and linear programming. A key component in all three algorithms is the computation of value functions, as defined in Section 2.1.

Recall that a value function defines a value for each state x **in the state space. With an** explicit representation of the value function as a vector of **values for the different states,**
the solution algorithms all can be implemented as a series of **simple algebraic steps. Thus,**
in this case, all three can be implemented very efficiently.

Unfortunately, in the case of factored MDPs, the state space **is exponential in the number**
of variables in the domain. In the SysAdmin problem, for example, the state x **of the system** is an assignment describing which machines are working or have failed; that is, a state x is an assignment to each random variable Xi**. Thus, the number of states is exponential in**
the number m of machines in the network (|X| = N = 2m**). Hence, even representing an**
explicit value function in problems with more than about ten **machines is infeasible. One** might be tempted to believe that factored transition dynamics and rewards would result in a factored value function, which can thereby be represented **compactly. Unfortunately, even**
in trivial factored MDPs, there is no guarantee that structure in the model is preserved in the value function (Koller & Parr, 1999).

In this section, we discuss the use of an approximate **value function, that admits a**
compact representation. We also describe approximate versions of these exact algorithms, that use approximate value functions. Our description in this section is somewhat abstract, and does not specify how the basic operations required by the **algorithms can be performed**
explicitly. In later sections, we elaborate on these issues, and describe the algorithms in detail. For brevity, we choose to focus on policy iteration and linear programming; our techniques easily extend to value iteration.

## 3.1 Linear Value Functions

A very popular choice for approximating value functions is by using linear regression**, as first**
proposed by Bellman et al. **(1963). Here, we define our space of allowable value functions**
V ∈ H ⊆ RN via a set of **basis functions**:
Definition 3.1 A linear value function over a set of basis functions H = {h1**, . . . , h**k}
is a function V that can be written as V(x) = Pk j=1 wj hj (x) **for some coefficients** w =
(w1**, . . . , w**k)
′.

We can now define H to be the linear subspace of RN **spanned by the basis functions** H.

It is useful to define an N × k matrix H whose columns are the k **basis functions viewed as**