Robust Value Function Approximation Using Bilinear Programming

Marek Petrik, Shlomo ZilbersteinNeurIPS 2009 · OpenReview

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.

Comparison of Bellman residual errors across different approximation methods.

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

Abstract

Existing value function approximation methods have been successfully used in many applications, but they often lack useful a priori error bounds. We propose approximate bilinear programming, a new formulation of value function approximation that provides strong a priori guarantees. In particular, it provably finds an approximate value function that minimizes the Bellman residual. Solving a bilinear program optimally is NP hard, but this is unavoidable because the Bellman-residual minimization itself is NP hard. We, therefore, employ and analyze a common approximate algorithm for bilinear programs. The analysis shows that this algorithm offers a convergent generalization of approximate policy iteration. Finally, we demonstrate that the proposed approach can consistently minimize the Bellman residual on a simple benchmark problem.
BibTeX
@inproceedings{petrik2009robust,
  author = {Marek Petrik and Shlomo Zilberstein},
  title = {{Robust Value Function Approximation Using Bilinear Programming}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=BkE1cuZO-S},
}
Figure