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

arXiv: https://arxiv.org/abs/1907.06290 · HTML: https://mlsanity.com/paper/1907.06290/

## Key facts

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

## Built on by (most cited first, 30 of 40)

- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [High-probability sample complexities for policy evaluation with linear function approximation](https://mlsanity.com/paper/2305.19001/) (2023)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)
- [Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation](https://mlsanity.com/paper/2106.07472/) (2021)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Correcting Momentum in Temporal Difference Learning](https://mlsanity.com/paper/2106.03955/) (2021)
- [Robust Markov Decision Processes without Model Estimation](https://mlsanity.com/paper/2302.01248/) (2023)
- [Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise](https://mlsanity.com/paper/2104.01627/) (2021)
- [Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems](https://mlsanity.com/paper/2112.09579/) (2021)
- [Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning](https://mlsanity.com/paper/2405.09660/) (2024)
- [Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation](https://mlsanity.com/paper/2104.02836/) (2021)
- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity](https://mlsanity.com/paper/2103.16377/) (2021)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity](https://mlsanity.com/paper/2401.12764/) (2024)
- [Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2502.09884/) (2025)
- [Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity](https://mlsanity.com/paper/2103.13147/) (2021)
- [Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way](https://mlsanity.com/paper/2410.13067/) (2024)
- [A Credibility-aware Swarm-Federated Deep Learning Framework in Internet of Vehicles](https://mlsanity.com/paper/2108.03981/) (2021)
- [Finite-Time Error Bounds for Greedy-GQ](https://mlsanity.com/paper/2209.02555/) (2022)
- [Global Convergence of the ODE Limit for Online Actor-Critic Algorithms in Reinforcement Learning](https://mlsanity.com/paper/2108.08655/) (2021)
- [PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Method](https://mlsanity.com/paper/2110.06906/) (2021)

## 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.