Reinforcement learning (RL) relies heavily on value function approximation to solve large-scale Markov Decision Processes (MDPs). However, existing methods face significant trade-offs. Approximate Dynamic Programming (ADP) is popular but often lacks convergence guarantees, while Approximate Linear Programming (ALP) has better theoretical properties but is highly sensitive to difficult-to-tune state weighting parameters.
The core issue is the non-linear, non-convex "max" operator in the Bellman equation. Simplifying this operator often sacrifices a priori (before-the-fact) error bounds. This paper introduces Approximate Bilinear Programming (ABP), a novel formulation that provably minimizes the Bellman residual, bridging policy search and linear programming to yield a new, finitely-convergent algorithm: Optimistic Approximate Policy Iteration (OAPI).
Methodology: A Bilinear Framework
The paper’s primary contribution is reframing the minimization of the $L_\infty$ norm of the Bellman residual as a Separable Bilinear Program.
- Bilinear Formulation: The objective function is modeled as a product of two sets of variables: the value function and the policy. While solving this optimally is NP-hard (which is unavoidable as the underlying RL problem is itself NP-hard), it explicitly models the interaction between the "maximizing" policy and the "minimizing" value function approximation.
- Iterative Solving: To tackle the optimization, the authors use an alternating strategy. By fixing the policy, they solve for the value function (a linear program), and by fixing the value function, they solve for the policy.
- Optimistic Approximate Policy Iteration (OAPI): Derived from this bilinear framework, OAPI includes specific constraints ensuring the Bellman residual is non-negative and monotonically decreases. Unlike standard Approximate Policy Iteration (API), which can oscillate or diverge, OAPI guarantees convergence in finite time. Furthermore, ABP is highly robust to sparse sampling because it minimizes a residual naturally bounded below by zero, preventing the unbounded solutions sometimes seen in ALP.
Experiments and Results
The authors evaluated their approach on the classic Mountain Car benchmark, where an underpowered car must oscillate back and forth to gain enough momentum to drive up a steep hill. The setup used 200 uniformly sampled states with 3 actions each, approximating the value function using uniformly-spaced linear splines with 100 and 144 features.
The empirical results demonstrate that OAPI is significantly more consistent than its predecessors at minimizing the Bellman residual. As shown in the results table, OAPI achieved an $L_\infty$ error of 0.13 with 144 features, vastly outperforming traditional ALP (3.6) and Least-Squares Policy Iteration (LSPI, 3.9). While standard API achieved low error in this specific test, it lacks the theoretical convergence guarantees of OAPI.
Despite the theoretical NP-hardness of bilinear programming, OAPI's iterative approximation performed with runtimes comparable to existing state-of-the-art methods, consistently reaching a stable solution.
Limitations and Future Work
While ABP provides strong theoretical guarantees and empirical stability, the authors note a few limitations:
- Global Optimality: The alternating iterative algorithm guarantees a local optimum, but not necessarily the global optimum of the bilinear program.
- Conservative Bounds: The $L_\infty$ norm optimizes for worst-case error, which can be overly conservative for practical applications where average-case performance ($L_2$ norm) matters more. Formulating a similar bilinear approach for $L_2$ norms is a promising future direction.
- Scaling: Scaling this approach to high-dimensional problems, such as complex robotics or game-playing, will require more sophisticated sampling strategies and specialized bilinear solvers.
Summary updated