The second inequality follows from Assumptions 29, 30 and Lemma 36, as follows:

$$\begin{array}{l}{{v_{3}-L v_{3}\leq v_{2}-\tilde{L}v_{2}+\epsilon_{p}{\bf1}}}\\ {{\qquad\qquad\leq v_{2}-\tilde{L}v_{2}+\epsilon_{s}{\bf1}+\epsilon_{p}{\bf1}}}\\ {{\qquad\qquad\leq v_{1}-\tilde{L}v_{1}+\epsilon_{s}{\bf1}+\epsilon_{p}{\bf1}}}\\ {{\qquad\qquad\qquad\leq v_{1}-L v_{1}+2\epsilon_{s}{\bf1}+\epsilon_{p}{\bf1}}}\end{array}$$

Here, we use the fact that vi ≥ Lvi and that vi's minimize the corresponding Bellman residuals.

To summarize, this section identifies basic assumptions on the sampling behavior and shows that approximate bilinear programming scales well in the face of uncertainty caused by incomplete sampling. More detailed analysis will need to focus on identifying problemspecific assumptions and sampling modes that guarantee the basic conditions, namely satisfying Assumption 30 and Assumption 29. Such analysis is beyond the scope of this paper.

## 7. Discussion And Related Adp Methods

This section describes connections between approximate bilinear programming and two closely related approximate dynamic programming methods: ALP, and L∞-API, which are commonly used to solve factored MDPs (Guestrin et al., 2003). Our analysis sheds light on some of their observed properties and leads to a new *convergent* form of approximate policy iteration.

Approximate bilinear programming addresses some important issues with ALP: 1) ALP
provides value function bounds with respect to L1 norm, which does not guarantee small policy loss, 2) ALP's solution quality depends significantly on the heuristically-chosen objective function c in (ALP–L1) (de Farias, 2002), 3) the performance bounds involve a constant 1/(1 − γ) which can be very large when γ is close to 1 and 4) incomplete constraint samples in ALP easily lead to unbounded linear programs. The drawback of using approximate bilinear programming, however, is the higher computational complexity.

The first and the second issue in ALP can be addressed by choosing a problem-specific objective function c (de Farias, 2002). Unfortunately, all existing bounds require that c is chosen based on the optimal ALP solution for c. This is impossible to compute in practice. Heuristic values for c are used instead. Robust approximate bilinear program
(ABP–L∞), on the other hand, has no such parameters. On the other hand, the expectedloss bilinear program (ABP–U) can be seen as a method for simultaneously optimizing c and the approximate linear program.

The fourth issue in approximate linear programs arises when the constraints need to be sampled. The ALP may become unbounded with incomplete samples because its objective value is defined using the L1 norm on the value function, and the constraints are defined using the L∞ norm of the Bellman residual. In approximate bilinear programs, the Bellman residual is used in both the constraints and objective function. The objective function of ABP is then bounded below by 0 for an arbitrarily small number of samples.

The NP-completeness of ABP compares unfavorably with the polynomial complexity of ALP. However, most other approximate dynamic programming algorithms are not guar-