Difference of Convex Functions Programming Applied to Control with Expert Data

Bilal Piot, Matthieu Geist, Olivier PietquinarXiv 2016 · OpenReview

Abstract

This paper reports applications of Difference of Convex functions (DC) programming to Learning from Demonstrations (LfD) and Reinforcement Learning (RL) with expert data. This is made possible because the norm of the Optimal Bellman Residual (OBR), which is at the heart of many RL and LfD algorithms, is DC. Improvement in performance is demonstrated on two specific algorithms, namely Reward-regularized Classification for Apprenticeship Learning (RCAL) and Reinforcement Learning with Expert Demonstrations (RLED), through experiments on generic Markov Decision Processes (MDP), called Garnets.

Introduction

Reinforcement Learning (RL) has achieved remarkable success in complex decision-making tasks, yet it frequently encounters significant hurdles when rewards are sparse. In such scenarios, an agent may spend an impractical amount of time exploring without receiving meaningful feedback. Learning from Demonstrations (LfD) mitigates this by providing the agent with expert trajectories to guide the learning process.

However, LfD methods face two primary challenges: maintaining awareness of the underlying environment dynamics and navigating the optimization complexity of their objective functions. Many advanced methods that account for dynamics rely on the Optimal Bellman Residual (OBR). While theoretically sound, the OBR is typically non-convex and non-differentiable, making it a difficult target for standard optimization tools like gradient descent, which often converge to sub-optimal local minima.

The DC Programming Framework

To address these optimization challenges, this research leverages Difference of Convex (DC) programming. A function $J$ is considered DC if it can be expressed as the difference between two convex functions: $J = f - g$.

The core innovation of this paper is the mathematical proof that the OBR—despite its complexity—is a DC function. This allows the authors to utilize the DC Algorithm (DCA). Unlike standard gradient descent, which follows local slopes, DCA iteratively linearizes the $g$ component of the function. This process creates a sequence of convex sub-problems that are significantly easier to solve reliably and efficiently. Furthermore, because these specific decompositions are "polyhedral" (composed of flat faces), the DCA can often converge to a local minimum in a finite number of steps, providing superior stability.

Algorithmic Enhancements

The authors apply this DC framework to two prominent algorithms:

  1. RCAL (Reward-regularized Classification for Apprenticeship Learning): An LfD method that seeks a policy consistent with expert data while assuming a sparse underlying reward structure.
  2. RLED (Reinforcement Learning with Expert Demonstrations): A hybrid approach that integrates environment rewards with expert data to accelerate the learning curve.

By providing explicit DC decompositions for the objectives in RCAL and RLED, the authors transform these "black box" non-convex problems into structured optimization tasks.

Experimental Evaluation

The proposed methods were evaluated using Garnets, which are abstract, randomly generated Markov Decision Processes. These provide a controlled environment to test mathematical robustness without the specific biases of complex simulators. The experiments utilized Garnets with 100 states, 5 actions, and deterministic transitions. Expert data was generated using optimal policies derived from Policy Iteration.

Key Results

  • RCAL Performance: The DC-optimized version, RCALDC, demonstrated a significant advantage over the original gradient-descent implementation. In a comprehensive test across 2,000 different data scenarios, RCALDC outperformed standard RCAL 86.6% of the time.
  • RLED Performance: While RLED is inherently robust, the DC-enhanced version showed a consistent performance edge as the volume of expert data and environment transitions increased.
  • Optimization Quality: The authors ensured a fair comparison by matching the total computational steps between the DC and baseline methods. The results indicate that the performance gains stem from the superior quality of the optimization path provided by DCA, rather than increased computation.

Conclusion and Future Work

This research demonstrates that the non-convexity of the Optimal Bellman Residual is not an insurmountable barrier. By identifying the OBR as a DC function, the authors provide a more reliable mathematical pathway for Learning from Demonstrations.

While the current work focuses on linear function approximation and manual feature engineering, future research will explore extending this DC framework to non-parametric methods and deep neural networks. Additionally, the authors aim to automate feature learning while preserving the DC structure, eventually scaling these controllers to real-world robotics and physical systems.

Summary updated

Abstract

This paper reports applications of Difference of Convex functions (DC) programming to Learning from Demonstrations (LfD) and Reinforcement Learning (RL) with expert data. This is made possible because the norm of the Optimal Bellman Residual (OBR), which is at the heart of many RL and LfD algorithms, is DC. Improvement in performance is demonstrated on two specific algorithms, namely Reward-regularized Classification for Apprenticeship Learning (RCAL) and Reinforcement Learning with Expert Demonstrations (RLED), through experiments on generic Markov Decision Processes (MDP), called Garnets.
BibTeX
@misc{piot2016difference,
  author = {Bilal Piot and Matthieu Geist and Olivier Pietquin},
  title = {{Difference of Convex Functions Programming Applied to Control with Expert Data}},
  year = {2016},
  eprint = {1606.01128},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1606.01128},
}
Figure