Sparse Q-learning with Mirror Descent

By Sridhar Mahadevan, Bo Liu. 2012

41 citations recorded by the source corpus.

This paper explores a new framework for reinforcement learning based on online convex optimization, in particular mirror descent and related algorithms. Mirror descent can be viewed as an enhanced gradient method, particularly suited to minimization of convex functions in high-dimensional spaces. Unlike traditional gradient methods, mirror descent undertakes gradient updates of weights in both the dual space and primal space, which are linked together using a Legendre transform. Mirror descent can be viewed as a proximal algorithm where the distance generating function used is a Bregman divergence. A new class of proximal-gradient based temporal-difference (TD) methods are presented based on different Bregman divergences, which are more powerful than regular TD learning. Examples of Bregman divergences that are studied include p-norm functions, and Mahalanobis distance based on the covariance of sample gradients. A new family of sparse mirror-descent reinforcement learning methods are proposed, which are able to find sparse fixed points of an l1-regularized Bellman equation at significantly less computational cost than previous methods based on second-order matrix methods. An experimental study of mirror-descent reinforcement learning is presented using discrete and continuous Markov decision processes.

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

Stochastic Primal-Dual Q-Learning (2018, neutral): “…as the distributed RL (Kar et al., 2013; Macua et al., 2015; Zhang et al., 2018; Lee et al., 2018), Q-learning with function approximations (Sutton et al., 2009b,a), sparsity promoted RL (Mahadevan and Liu, 2012), safe RL (Garcıa and Fern´andez, 2015), and the inverse RL (Ng and Russell, 2000).”
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, positive): “This work began originally with a dual space formulation of ﬁrst-order sparse TD learning [Mahadevan and Liu, 2012].”
Investigating Practical Linear Temporal Difference Learning (2016, background): “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.”
Regularized Off-Policy TD-Learning (2012, background): “Regularized first-order reinforcement learning approaches have recently been investigated in the on-policy setting as well, wherein convergence of l1 regularized temporal difference learning is discussed in [16] and mirror descent [6] is used in [11].”
Basis Adaptation for Sparse Nonlinear Reinforcement Learning (2013, methodology): “We combine basis adaptation with mirrordescent RL (Mahadevan and Liu 2012), a recently developed first-order approach to sparse RL.”
Stochastic Primal-Dual Q-Learning Algorithm For Discounted MDPs (2019, background): “Q-learning with function approximations [11], [24], sparsity promoted RL [18], safe RL [25], and the inverse RL [26].”
An online primal-dual method for discounted Markov decision processes (2016, background): “In the RL literatures, there have been some works about dual temporal difference learning and primaldual methods, see for examples [13], [15], [16], [24].”
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”