Difference of Convex Functions Programming for Reinforcement Learning

Bilal Piot, Matthieu Geist, Olivier Pietquin

Introduction

In Reinforcement Learning (RL), finding the optimal state-action value function (the $Q$-function) is central to solving Markov Decision Processes (MDPs). For large-scale problems where exact calculation is impossible, Approximate Dynamic Programming (ADP) methods like Approximate Value Iteration (AVI) and Approximate Policy Iteration (API) are the gold standards.

However, these standard methods suffer from a significant theoretical weakness: their error bounds grow quadratically as the problem's horizon increases (controlled by the discount factor $\gamma$). An alternative approach is to directly minimize the Optimal Bellman Residual (OBR), which measures how much the current $Q$-function deviates from the Bellman optimality equation. While OBR minimization offers tighter theoretical error bounds, it results in a non-convex and non-differentiable optimization problem that is notoriously difficult to solve without getting trapped in local minima.

This paper introduces a novel solution by framing the OBR minimization as a Difference of Convex (DC) functions optimization, bridging the gap between strong theoretical bounds and practical solvability.

Methods: Difference of Convex (DC) Programming

The authors prove that the OBR minimization problem belongs to a specific class of functions called Difference of Convex (DC) functions. A DC function $f$ can be expressed as $f = g - h$, where both $g$ and $h$ are convex.

This formulation is a "sweet spot" in non-convex optimization because it allows the use of the Difference of Convex functions Algorithm (DCA). DCA works by linearizing the $h$ component, thereby creating a sequence of convex sub-problems that are significantly easier to solve.

Key technical contributions include:

  • Explicit Decompositions: The authors provide exact mathematical formulas to split the OBR (for both $L_1$ and $L_2$ norms) into its convex components ($g$ and $h$), allowing researchers to plug this directly into DCA solvers.
  • Vapnik-Consistency: They prove that minimizing the OBR using a finite set of samples (the "empirical norm") converges to the true solution as more data is added, justifying the use of batch sampled transitions rather than requiring a perfect world model.

Key Insights and Theoretical Advantages

The most significant theoretical advantage of the OBR minimization approach (OBRM) is its scaling with respect to the planning horizon.

Comparison of error bound terms between API/AVI and OBRM

As shown in the bounds comparison, the "horizon term" for OBRM scales at $\frac{2}{1-\gamma}$, whereas standard methods like AVI/API scale at $\frac{2\gamma}{(1-\gamma)^2}$. In practical terms, as the planning horizon gets longer (i.e., $\gamma$ approaches 1), the DC-based method theoretically maintains tighter accuracy bounds than classical ADP methods. This was made possible by the realization that the absolute value of a DC function remains a DC function, allowing the entire OBR objective—despite its max operators and absolute values—to be solved via DCA.

Experiments and Key Results

To test the practical viability of the DC approach, the researchers evaluated their algorithms (DCA1 and DCA2) against state-of-the-art methods like LSPI (a form of API) and Fitted-Q (a form of AVI). The evaluation used Garnet problems (Generalized Average Reward Non-stationary Elastic Transitions)—randomly constructed finite MDPs designed to mimic the topological structure of real-world dynamical systems. The authors generated 50 different Garnet "worlds" to ensure robust results.

Performance and standard deviation of DCA methods compared to baselines on Garnet problems
  • Competitive Performance: In the Garnet experiments, the DC approach achieved mean performance levels nearly identical to the established benchmarks (LSPI and Fitted-Q).
  • Lower Variance: Notably, the DC algorithms demonstrated a lower standard deviation in performance across different samples. This suggests that the DCA-based method is more stable and less prone to "bad runs" than traditional ADP methods.

Limitations and Future Work

While the theoretical foundation is strong, the empirical implementation in this paper was relatively "naive." The authors utilized a basic sub-gradient descent to solve the internal convex sub-problems. Employing more sophisticated convex solvers could significantly boost computational performance and efficiency.

An exciting direction for future work is non-parametric RL. Because each step of the DCA algorithm involves a convex minimization, it could potentially be combined with "boosting" techniques. This would allow an RL agent to automatically learn the necessary features of its environment, rather than relying on hand-designed feature engineering.

Summary updated

Abstract

Large Markov Decision Processes (MDPs) are usually solved using Approximate Dynamic Programming (ADP) methods such as Approximate Value Iteration (AVI) or Approximate Policy Iteration (API). The main contribution of this paper is to show that, alternatively, the optimal state-action value function can be estimated using Difference of Convex functions (DC) Programming. To do so, we study the minimization of a norm of the Optimal Bellman Residual (OBR) $T^*Q-Q$, where $T^*$ is the so-called optimal Bellman operator. Controlling this residual allows controlling the distance to the optimal action-value function, and we show that minimizing an empirical norm of the OBR is consistant in the Vapnik sense. Finally, we frame this optimization problem as a DC program. That allows envisioning using the large related literature on DC Programming to address the Reinforcement Leaning (RL) problem.
BibTeX
@inproceedings{piot2014difference,
  author = {Bilal Piot and Matthieu Geist and Olivier Pietquin},
  title = {{Difference of Convex Functions Programming for Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=l3oekeHlSN},
}
Figure