Finite-Sample Analysis of Proximal Gradient TD Algorithms

By Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, Marek Petrik. 2015

164 citations recorded by the source corpus.

In this paper, we show for the first time how gradient TD (GTD) reinforcement learning methods can be formally derived as true stochastic gradient algorithms, not with respect to their original objective functions as previously attempted, but rather using derived primal-dual saddle-point objective functions. We then conduct a saddle-point error analysis to obtain finite-sample bounds on their performance. Previous analyses of this class of algorithms use stochastic approximation techniques to prove asymptotic convergence, and no finite-sample analysis had been attempted. Two novel GTD algorithms are also proposed, namely projected GTD2 and GTD2-MP, which use proximal "mirror maps" to yield improved convergence guarantees and acceleration, respectively. The results of our theoretical analysis imply that the GTD family of algorithms are comparable and may indeed be preferred over existing least squares TD methods for off-policy learning, due to their linear complexity. We provide experimental results showing the improved performance of our accelerated gradient TD methods.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Control and Systems Engineering, Reinforcement Learning, Optimization & Training

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 Theory and Mathematics

In Control and Systems Engineering

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values (2020, methodology): “Self-normalization (Liu et al., 2018; Zhang et al., 2020a) is also an approach to ensure nonlinearity, where we normalize the τ prediction over all possible state-action pairs. Recently, Mousavi et al. (2020) propose an objective with Maximum Mean Discrepancy and use self-normalization.”
Reinforcement Learning via Fenchel-Rockafellar Duality (2020, methodology): “Typically, the Q -values are estimated by ﬁnding the ﬁxed point of the Bellman recurrence (Sutton et al., 2008, 2009; Scherrer, 2010; Liu et al., 2015; Dai et al., 2016; Du et al., 2017); i.e. , minimizing the (surrogate) squared diﬀerence between the LHS and RHS of (23), potentially with target…”
Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation (2019, methodology): “Primal-Dual Value Learning Primal-dual optimization techniques have been widely used for off-policy value function learning and policy optimization (Liu et al., 2015; Chen & Wang, 2016; Dai et al., 2017a,b; Feng et al., 2019).”
Smoothed Dual Embedding Control (2017, background): “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 led to novel, faster, and ”
Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis (2015, methodology): “(Partial) Following the same derivation that Sutton, Mahmo od, and White (2015) 8”
A Kernel Loss for Solving the Bellman Equation (2019, methodology): “Another line of work seeks alternative objective functions, the minimization of which leads to desired value functions (Sutton et al., 2009; Maei, 2011; Liu et al., 2015; Dai et al., 2017).”
Provably Convergent Off-Policy Actor-Critic with Function Approximation (2019, background): “However, their analysis is conducted with the saddle-point formulation of the GTD objective (Liu et al., 2015; Macua et al., 2014) and requires a fixed target policy, which is impractical in our control setting.”
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).”
Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates (2018, background): “One popular choice for the surrogate cost is the Mean Square Projected Bellman Error (MSPBE) (see, e.g., [6], [7], [15] and [16]); this cost has the inconvenience that its minimizer θ o is different from (7) and some bias given by ( θ − θ o ) is incurred. we In order to control the magnitude of the…”
Linear Stochastic Approximation: How Far Does Constant Step-Size and Iterate Averaging Go? (2018, methodology): “08, see [12]) with the choice of α = 1 2×2 (2 is to normalize the features) and initial condition θ0 = [1 1 1 1 1 1 10 1].”
Stochastic Variance Reduction Methods for Policy Evaluation (2017, methodology): “Liu et al. (2015) and Valcarcel Macua et al. (2015) independently showed that the GTD2 algorithm (Sutton et al., 2009b) is indeed a stochastic gradient method for solving the saddle-point problem (10), although they obtained the saddle-point formulation with different derivations.”
Learning from Conditional Distributions via Dual Kernel Embeddings (2016, methodology): “We compare the proposed algorithm to several prevailing algorithms in reinforcement learning, including gradient-TD2 (GTD2) [30, 17], residual gradient (RG) [3] and kernel MDP [11] in terms of mean square Bellman error.”
Harnessing Inﬁnite-Horizon Off-Policy Evaluation: Double Robustness via Duality (2019, methodology): “Primal-Dual Value Learning Primal-dual optimization techniques have been widely used for off-policy value function learning and policy optimization (Liu et al., 2015; Chen & Wang, 2016; Dai et al., 2017a,b; Feng et al., 2019).”
Convergent Tree-Backup and Retrace with Function Approximation (2017, methodology): “Later, Liu et al. (2015) provided the ﬁrst sample complexity by reformulating GTD/GTD2 as an instance of mirror stochastic approximation (Nemirovski et al., 2009).”
Learning from Conditional Distributions via Dual Embeddings (2016, methodology): “We compare the proposed algorithm to several prevailing algorithms for policy evaluation , including gradient - TD2 ( GTD2 ) ( Sutton et al .”
Safe Reinforcement Learning (2015, background): “1) and other related algorithms are true stochastic gradient algorithms for primal-dual saddle-point objective functions (Liu et al., 2015).”
Online Off-policy Prediction (2018, methodology): “Another potential improvement on Gradient-TD can be derived by reformulating the excursion objective into a saddlepoint problem, resulting in several new methods (Liu et al., 2015; Liu et al., 2016; Du et al., 2017; Touati et al., 2018).”
Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation (2019, background): “However, their analysis is conducted with the saddle-point formulation of the GTD objective (Liu et al., 2015; Macua et al., 2015) and requires a ﬁxed target policy, which is impractical in our control setting.”
Off-Policy Evaluation via the Regularized Lagrangian (2020, methodology): “In one line of literature, it was used to solve the Bellman equation, whose fixed point is the value function [6, 7, 16].”