Difference of Convex Functions Programming for Reinforcement Learning
Large Markov Decision Processes are usually solved using Approximate Dynamic Programming methods such as Approximate Value Iteration or Approximate 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. 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 problem.
The paper presents a new technique for solving MDPs. The new technique, presented as an alternative to approximate policy/value iteration, consists in directly minimizing the Optimal Bellman Residual (OBR). The authors first motivate their method by showing that the loss bound of OBR is often tighter than the loss bound of policy/value iteration, which is a known result [9,15]. The authors then show that an empirical estimate of OBR is consistent in the Vapnick sense, i.e. minimizing the empirical OBR is equivalent to minimizing an upper bound on the true OBR, which is unknown when the MDP model is unknown. Finally, the authors show that OBR can be decomposed into a difference of two convex functions, and a standard Difference of Convex Functions (DC) optimization method can be used for finding a local optimum. The authors argue that the obtained optimum is usually not very different from the global one. Finally, the authors show that the performance of their method is similar to the performance of standard techniques, such as LSPI and Fitted-Q learning. The authors also show that the values obtained from OBR minimization have a smaller variance.Pros: The paper is very clear, well-written and well-organized. Technically, the paper is strong and sound. The proofs are not trivial and quite original. Theorem 4 (decomposition of OBR into a difference of convex functions) is probably the most useful result in this paper from a practical point of view. The motivation from a loss bound (Sec 2.2) is appreciated. Moreover, the authors prove the consistency of empirical risk minimization when the value function is approximated with basis functions (features). Cons: The empirical evaluation is very weak. The authors experiment only on a simple artificial MDP, and their method is not better than LSPI or Fitted-Q learning. If it will turn out that OBR minimization is never better than LSPI, then this whole contribution becomes questionable. Moreover, the authors did not report the computational effort needed for solving multiple convex optimization problems. My intuition is that if the DC decomposition is not well-done, than DC programming can be slower than DC programming.However, I agree that the main contribution of this paper is pointing to this new way of solving MDPs, which seems intriguing. I would like to see how the DC iterations are related to the policy/value iterations. Questions/comments:1) What is \mu in line 120? How is it different from the state-action distribution v? This should be introduced before Equation (1).2) Equation (3) is mostly a repetition of Equation (2)3) Typos in line 158: "better that", "manly", in line 313 "is currently is"4) The proof of Theorem 3 is straightforward, you can cut it off, remove Equation (3) and bring the more important proof of Theorem 4 to the main paper.5) In your experiment, is the computational cost of DC programming in the same order of magnitude as dynamic programing?