$N$-Timescale Stochastic Approximation: Stability and Convergence

2021-12-07 · Rohan Deb, Shalabh Bhatnagar

This paper presents the first sufficient conditions that guarantee the stability and almost sure convergence of $N$-timescale stochastic approximation (SA) iterates for any $N\geq1$. It extends the existing results on One-timescale and Two-timescale SA iterates to general $N$-timescale stochastic recursions using the ordinary differential equation (ODE) method. As an application of our results, we study SA algorithms with an added heavy ball momentum term in the context of Gradient Temporal Difference (GTD) algorithms. We show that, when the momentum parameters are chosen in a certain way, the schemes are stable and convergent to the same solution using our proposed results.

📄 PDF Abstract BibTeX arXiv:2112.03515

Code (0)

등록된 구현이 없습니다.

Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning

2026-05-29 · Vagul Mahadevan, Claire Chen, Shuze Daniel Liu, Shangtong Zhang arxiv

This work studies the convergence of two-timescale stochastic approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow timescales respectively. Notable examples of two-time…

Reinforcement Learning

Gradient Temporal Difference with Momentum: Stability and Convergence

2021-11-22 · Rohan Deb, Shalabh Bhatnagar

Gradient temporal difference (Gradient TD) algorithms are a popular class of stochastic approximation (SA) algorithms used for policy evaluation in reinforcement learning. Here, we consider Gradient TD algorithms with an…

Two-Timescale Stochastic Approximation for Bilevel Optimisation Problems in Continuous-Time Models

2022-06-14 · Louis Sharrock

We analyse the asymptotic properties of a continuous-time, two-timescale stochastic approximation algorithm designed for stochastic bilevel optimisation problems in continuous-time models. We obtain the weak convergence …

Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning

2017-03-15 · Gal Dalal, Balazs Szorenyi, Gugan Thoppe, Shie Mannor

Two-timescale Stochastic Approximation (SA) algorithms are widely used in Reinforcement Learning (RL). Their iterates have two parts that are updated using distinct stepsizes. In this work, we develop a novel recipe for …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Faster Q-Learning Algorithms for Restless Bandits

2024-09-06 · Parvish Kakarapalli, Devendra Kayande, Rahul Meshram

We study the Whittle index learning algorithm for restless multi-armed bandits (RMAB). We first present Q-learning algorithm and its variants -- speedy Q-learning (SQL), generalized speedy Q-learning (GSQL) and phase Q-l…

Multi-Armed Bandits Q-Learning