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

Reinforcement learning is a simple, and yet, comprehensive theory of learning that simultaneously models the adaptive behavior of artificial agents, such as robots and autonomous software programs, as well as attempts to explain the emergent behavior of biological systems. It also gives rise to computational ideas that provide a powerful tool to solve problems involving sequential prediction and decision making. Temporal difference learning is the most widely used method to solve reinforcement learning problems, with a rich history dating back more than three decades. For these and many other reasons, devel1 This article is currently not under review for the journal Foundations and Trends in ML, but will be submitted for formal peer review at some point in the future, once the draft reaches a stable “equilibrium” state. ar X iv :1 40 5. 67 57 v1 [ cs .L G ] 2 6 M ay 2 01 4 oping a complete theory of reinforcement learning, one that is both rigorous and useful has been an ongoing research investigation for several decades. 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 “safely” 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 most important 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, as we show, 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 in Hilbert spaces, both in optimization and for variational inequalities. The latter framework, the subject of another ongoing investigation by our group, holds the promise of an even more elegant framework for reinforcement learning. Its explication is currently the topic of a further monograph that will appear in due course. Dedicated to Andrew Barto and Richard Sutton for inspiring a generation of researchers to the study of reinforcement learning. Algorithm 1 TD (1984) (1) δt = rt + γφ ′ t T θt − φt θt (2) θt+1 = θt + βtδt Algorithm 2 GTD2-MP (2014) (1) wt+ 1 2 = wt + βt(δt − φt wt)φt, θt+ 1 2 = proxαth ( θt + αt(φt − γφt)(φt wt) ) (2) δt+ 1 2 = rt + γφ ′ t T θt+ 1 2 − φt θt+ 1 2 (3) wt+1 = wt + βt(δt+ 1 2 − φt wt+ 1 2 )φt , θt+1 = proxαth ( θt + αt(φt − γφt)(φt wt+ 1 2 ) )