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

By Sridhar Mahadevan, Bo Liu, Philip S. Thomas, Will Dabney, Stephen Giguere, Nicholas Jacek, Ian Gemp, Ji Liu. 2014

73 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistical and Nonlinear Physics

Citations in the corpus

Smoothed Dual Embedding Control (2017, methodology): “adient descent (SGD) to optimize them (Sutton et al., 2009; Maei, 2011). Later on, it was realized that several of these gradient-based algorithms can be interpreted as solving a primal-dual problem (Mahadevan et al., 2014; Liu et al., 2015; Macua et al., 2015; Dai et al., 2016). This insight has le”
Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, background): “In the literatures of reinforcement learning, there have been works on dual temporal diﬀerence learning which use primal-dual-type methods, see for examples (Yang et al., 2009; Liu et al., 2012; Mahadevan and Liu, 2012; Mahadevan et al., 2014).”
Finite-Sample Analysis of Proximal Gradient TD Algorithms (2015, methodology): “The line of research reported here has much in common with work on proximal reinforcement learning [Mahadevan et al., 2014], which explores first-order reinforcement learning algorithms using mirror maps [Bubeck, 2014; Juditsky et al.”
SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation (2017, background): “Later on, it was realized that several of these gradient-based algorithms can be interpreted as solving a primal-dual problem (Mahadevan et al., 2014; Liu et al., 2015; Macua et al., 2015; Dai et al., 2017).”
Provably Convergent Off-Policy Actor-Critic with Function Approximation (2019, methodology): “Mahadevan et al. (2014) introduce the proximal GTD learning framework to integrate GTD algorithms with first-order optimization-based regularization via saddle-point formulations and proximal operators.”
Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation (2019, methodology): “Mahadevan et al. (2014) introduce the proximal GTD learning framework to integrate GTD algorithms with ﬁrst-order optimization-based regularization via saddle-point formulations and proximal operators.”
Two-Timescale Networks for Nonlinear Value Function Approximation (2019, background): “Additionally, there have been a variety of algorithms derived for the linear setting, both for on-policy and off-policy learning (Sutton et al., 2009; Maei, 2011; van Seijen and Sutton, 2014; van Hasselt et al., 2014; Mahadevan et al., 2014; Sutton et al., 2016; Mahmood et al., 2017).”
Online Off-policy Prediction (2018, methodology): “As with the hybrid methods, comparative studies to date remain inconclusive about the advantages of these methods over their vanilla Gradient-TD counterparts (Mahadevan et al., 2014; White & White, 2016).”
Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD (2018, background): “We also note a primaldual variant of the GTD in [18] with proximal operator approaches.”
Investigating Practical Linear Temporal Difference Learning (2016, methodology): “The MSPBE is often used as a performance measure, but the MSPBE changes with λ; for completeness, we include results with the MSPBE in the appendix.”
Scalable Bilinear π Learning Using State and Action Features (2018, background): “It should be noted that there is another line of research that studies saddle-point formulations that result from the ﬁxed-point (as opposed to LP) view of the Bellman equation for ﬁxed policy evaluation (Mahadevan et al., 2014; Macua et al., 2015; Du et al., 2017; Dai et al., 2017).”
Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize (2015, background): “In the gradient-TD algorithms [47, 45, 23] and the proximal gradient-TD algorithms [22, 24] (see also [21, 25]), the difficulty in TD(λ) is overcome by reformulating the approximate policy evaluation problem TD(λ) attempts to solve as optimization problems and then tackle them with optimization tech”