Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces

Abstract

In this paper, we set forth a new vision of reinforcement learning developed by us over the past few years, one that yields mathematically rigorous solutions to longstanding important questions that have remained unresolved: (i) how to design reliable, convergent, and robust reinforcement learning algorithms (ii) how to guarantee that reinforcement learning satisfies pre-specified "safety" guarantees, and remains in a stable region of the parameter space (iii) how to design "off-policy" temporal difference learning algorithms in a reliable and stable manner, and finally (iv) how to integrate the study of reinforcement learning into the rich theory of stochastic optimization. In this paper, we provide detailed answers to all these questions using the powerful framework of proximal operators. The key idea that emerges is the use of primal dual spaces connected through the use of a Legendre transform. This allows temporal difference updates to occur in dual spaces, allowing a variety of important technical advantages. The Legendre transform elegantly generalizes past algorithms for solving reinforcement learning problems, such as natural gradient methods, which we show relate closely to the previously unconnected framework of mirror descent methods. Equally importantly, proximal operator theory enables the systematic development of operator splitting methods that show how to safely and reliably decompose complex products of gradients that occur in recent variants of gradient-based temporal difference learning. This key technical innovation makes it possible to finally design "true" stochastic gradient methods for reinforcement learning. Finally, Legendre transforms enable a variety of other benefits, including modeling sparsity and domain geometry. Our work builds extensively on recent work on the convergence of saddle-point algorithms, and on the theory of monotone operators.

arXiv comment121 pages

References in corpus (5)

• Representation Policy Iteration
• A Dantzig Selector Approach to Temporal Difference Learning
• Control Design for Markov Chains under Safety Constraints: A Convex Approach
• Galerkin Methods for Complementarity Problems and Variational Inequalities
• Practical Kernel-Based Reinforcement Learning

Cited by in corpus (19)

• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
• Scalable Bilinear $\pi$ Learning Using State and Action Features
• Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize
• On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning
• A generalization of regularized dual averaging and its dynamics
• Online Off-policy Prediction
• Accelerated Gradient Temporal Difference Learning
• Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems
• Stochastic Primal-Dual Q-Learning
• Primal-Dual Distributed Temporal Difference Learning
• Average-Reward Off-Policy Policy Evaluation with Function Approximation
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation
• Target-Based Temporal Difference Learning
• Borrowing From the Future: Addressing Double Sampling in Model-free Control
• A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learning
• An Empirical Comparison of Off-policy Prediction Learning Algorithms on the Collision Task
• On Generalized Bellman Equations and Temporal-Difference Learning
• An Empirical Comparison of Off-policy Prediction Learning Algorithms in the Four Rooms Environment