Difference of Convex Functions Programming for Reinforcement Learning

Bilal Piot, Matthieu Geist, Olivier Pietquin

TL;DR

This paper proposes a novel approach to solving large-scale Reinforcement Learning (RL) problems by framing the optimization of the optimal action-value function as a Difference of Convex (DC) programming problem. This allows leveraging a rich existing literature on DC programming to potentially improve RL algorithms, showing competitive results against established methods in initial experiments.

What Problem Does This Paper Address?

Solving large-scale Markov Decision Processes (MDPs) is a significant challenge in Reinforcement Learning. Traditional methods like Approximate Value Iteration (AVI) and Approximate Policy Iteration (API) rely on Dynamic Programming (DP) and face issues with representation (handling vast state spaces) and sampling (limited access to true system dynamics). This paper tackles the problem of finding an accurate estimate of the optimal action-value function ($Q^*$) in these large MDPs by proposing an alternative to standard DP-based approaches.

Methods

The core idea is to directly search for a function $Q$ such that the Optimal Bellman Residual (OBR), $T^*Q - Q$, is minimized. The authors first establish that minimizing a norm of the OBR is a valid proxy for estimating $Q^*$. They then demonstrate that minimizing an empirical norm of the OBR (using sampled data) is Vapnik-consistent, meaning it converges to the true minimum. The key novelty lies in framing this empirical OBR minimization as a Difference of Convex (DC) programming problem. This is achieved by decomposing the objective function into a difference of two convex functions. This transformation allows the application of established DC programming algorithms (like DCA) to solve the RL problem, circumventing the non-convexity of the direct OBR minimization.

Datasets

Not discussed in the paper. The experiments use a synthetic benchmark called "Garnet problems," which are randomly constructed finite MDPs designed to mimic properties of real-world dynamical systems.

Key Insights and Ideas

  • OBR Minimization as a Proxy for $Q^*$: The paper rigorously shows that controlling the Optimal Bellman Residual ($T^*Q - Q$) is directly linked to controlling the error in estimating the optimal action-value function ($Q^*$).
  • Vapnik Consistency of Empirical OBR: Minimizing the OBR using sampled data (empirical norm) is shown to be statistically sound, providing a theoretical justification for using finite datasets.
  • DC Programming for RL: The most significant contribution is reframing the non-convex OBR minimization problem as a DC program. This unlocks a vast body of existing algorithms and theory for solving non-convex optimization problems, offering a new avenue for RL research.
  • Potential for Non-Parametric RL: The authors suggest that the DC programming framework could potentially lead to non-parametric RL algorithms, avoiding the need for hand-crafted features.

Key Results

  • The paper provides theoretical bounds comparing the proposed OBR minimization approach to existing AVI/API methods, showing favorable terms related to horizon and concentrability.
  • Initial experiments on synthetic "Garnet" problems demonstrate that the proposed DC programming-based algorithms (DCA1 and DCA2) are competitive with established methods like LSPI (API) and Fitted-Q (AVI) in terms of performance.
  • Crucially, the DC programming approaches exhibit lower variance compared to AVI/API methods, suggesting greater stability.

Limitations and Future Work

  • Naive DCA Implementation: The experimental setup for DCA is described as "naive," using a basic explicit decomposition and a sub-gradient descent for intermediate convex problems. The authors suggest that more sophisticated choices for decomposition and convex solvers could significantly improve performance.
  • Error Analysis of DCA Output: While the paper shows that controlling the empirical OBR leads to a good estimate of $Q^*$, it acknowledges that the specific error between the output of the DCA algorithm and the true minimizer of the empirical OBR is not yet studied.
  • Non-Parametric Extension: A promising future direction is to explore how to make the DCA approach non-parametric, potentially by using boosting techniques for solving the intermediate convex optimization problems, thus avoiding feature engineering.
  • Real-World Applications: The paper calls for further research to prove the efficiency of this approach on real-world problems.

Summary updated

Abstract

Large Markov Decision Processes are usually solved using Approximate Dy-namic Programming methods such as Approximate Value Iteration or Ap-proximate Policy Iteration. 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. Control-ling 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 problem. 1
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