Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning

Abstract

We study two time-scale linear stochastic approximation algorithms, which can be used to model well-known reinforcement learning algorithms such as GTD, GTD2, and TDC. We present finite-time performance bounds for the case where the learning rate is fixed. The key idea in obtaining these bounds is to use a Lyapunov function motivated by singular perturbation theory for linear differential equations. We use the bound to design an adaptive learning rate scheme which significantly improves the convergence rate over the known optimal polynomial decay rule in our experiments, and can be used to potentially improve the performance of any other schedule where the learning rate is changed at pre-determined time instants.

17 pages, 3 figures, preprint

Cited by in corpus (18)

• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Distributed two-time-scale methods over clustered networks
• Hyperparameter Auto-tuning in Self-Supervised Robotic Learning
• Adaptive Temporal Difference Learning with Linear Function Approximation
• Finite-Time Error Bounds for Distributed Linear Stochastic Approximation
• Robust Reinforcement Learning: A Case Study in Linear Quadratic Regulation
• The Mean-Squared Error of Double Q-Learning
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Method
• Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation
• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes
• Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms