mlsanityData to 7 Oct 2026

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

arXiv 1907.06290 ↗First posted 14 Jul 2019cs.LG cs.AI stat.MLcited by 40

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Jul 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 20; 2022: 5; 2023: 6; 2024: 5; 2025: 2; 2026: 2.

40 papers.

Sort:

By area:

  1. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  2. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  3. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  4. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 22
  5. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 20
  6. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  7. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  8. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  9. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  10. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 14
  11. 2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
  12. 2023Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noisecited by 14
28 more
  1. 2021Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximationcited by 13
  2. 2021Correcting Momentum in Temporal Difference Learningcited by 12
  3. 2023Robust Markov Decision Processes without Model Estimationcited by 11
  4. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  5. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  6. 2021Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximationcited by 8
  7. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 8
  8. 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7
  9. 2022Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximationcited by 7
  10. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  11. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  12. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  13. 2021Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexitycited by 5
  14. 2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5
  15. 2021A Credibility-aware Swarm-Federated Deep Learning Framework in Internet of Vehiclescited by 4
  16. 2022Finite-Time Error Bounds for Greedy-GQcited by 3
  17. 2021Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learningcited by 2
  18. 2021PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Methodcited by 2
  19. 2021Gradient Temporal Difference with Momentum: Stability and Convergencecited by 2
  20. 2022Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learningcited by 2
  21. 2022Two-Timescale Stochastic Approximation for Bilevel Optimisation Problems in Continuous-Time Modelscited by 2
  22. 2023A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothnesscited by 2
  23. 2021Learning Image Attacks toward Vision Guided Autonomous Vehiclescited by 1
  24. 2021Finite-Time Error Bounds for Distributed Linear Stochastic Approximationcited by 0
  25. 2023Intelligent gradient amplification for deep neural networkscited by 0
  26. 2025Intrinsic-Motivation Multi-Robot Social Formation Navigation with Coordinated Explorationcited by 0
  27. 2026Convergence of Two Time-Scale Stochastic Approximation: A Martingale Approachcited by 0
  28. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0