Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise

Abstract

Greedy-GQ is an off-policy two timescale algorithm for optimal control in reinforcement learning. This paper develops the first finite-sample analysis for the Greedy-GQ algorithm with linear function approximation under Markovian noise. Our finite-sample analysis provides theoretical justification for choosing stepsizes for this two timescale algorithm for faster convergence in practice, and suggests a trade-off between the convergence rate and the quality of the obtained policy. Our paper extends the finite-sample analyses of two timescale reinforcement learning algorithms from policy evaluation to optimal control, which is of more practical interest. Specifically, in contrast to existing finite-sample analyses for two timescale methods, e.g., GTD, GTD2 and TDC, where their objective functions are convex, the objective function of the Greedy-GQ algorithm is non-convex. Moreover, the Greedy-GQ algorithm is also not a linear two-timescale stochastic approximation algorithm. Our techniques in this paper provide a general framework for finite-sample analysis of non-convex value-based reinforcement learning algorithms for optimal control.

UAI 2020

References in corpus (6)

• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• An Alternative Softmax Operator for Reinforcement Learning
• On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning

Cited by in corpus (3)

• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Breaking the Deadly Triad with a Target Network