Proof. The proof is based on two facts. First, ˜v is feasible with respect to the constraints in
(ABP–L∞). The Bellman residual changes for all the policies identically, since a constant vector is added. Second, because Lπ is greedy with respect to ˜v, we have that ˜v ≥ Lπv˜ ≥ Lv˜.

The value function ˜v is therefore transitive-feasible.

From Proposition 45, L∞-API can be replaced by L∞-API2, which will converge to the same policy π. L∞-API2 will converge to the value function

$$\tilde{v}=v+\frac{\phi}{1-\gamma}{\bf1}.$$

From the constraints in (27) we have that ˜v ≥ Lπv˜. Then, since π is the greedy policy with regard to this value function, we have that ˜v ≥ Lπv˜ ≥ Lv˜. Thus ˜v is transitive-feasible and feasible in (BP–m) according to Lemma 38. The theorem then follows from Lemma 39 and from the fact that the greedy policy minimizes the Bellman residual, as in the proof of Lemma 16.

To summarize, OAPI guarantees convergence, while matching the performance of L∞-
API. The convergence of OAPI is achieved because given a non-negative Bellman residual, the greedy policy also minimizes the Bellman residual. Because OAPI ensures that the Bellman residual is always non-negative, it can progressively reduce it. In comparison, the greedy policy in L∞-API does not minimize the Bellman residual, and therefore L∞-
API does not always reduce it. Theorem 34 also explains why API provides better solutions than ALP, as observed in (Guestrin et al., 2003). From the discussion above, ALP can be seen as an L1-norm approximation of a single iteration of OAPI. L∞-API, on the other hand, performs many such ALP-like iterations.

## 8. Experimental Results

In this section, we validate the approach by applying it to simple reinforcement learning benchmark problems. The focus of the paper is on the theoretical properties and the experiments are intentionally designed to avoid interaction between the approximation in the formulation and approximate solution methods. As Theorem 34 shows, even OAPI, the very simple approximate algorithm for ABP, can perform as well as existing methods on factored MDPs.

ABP is an off-policy approximation method, like LSPI (Lagoudakis and Parr, 2003) or ALP. That means that the samples can be gathered independently of the control policy. It is necessary, though, that multiple actions are sampled for each state to enable the selection of different policies.

First, we demonstrate and analyze the properties of ABP on a simple chain problem with 200 states, in which the transitions move to the right or left (2 actions) by one step with a centered Gaussian noise of standard deviation 3. The rewards were set to sin(i/20) for the right action and cos(i/20) for the left action, where i is the index of the state. This problem is small enough to calculate the optimal value function and to control the approximation features. The approximation basis in this problem is represented by piecewise linear features, of the form φ(si) = [i − c]+, for c from 1 to 200. The discount factor in the experiments was γ = 0.95 and the initial distribution was α(130) = 1. We verified that the solutions of the bilinear programs were always close to optimal, albeit suboptimal.