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

• URL: http://arxiv.org/abs/2605.31172v1
• Date: Fri, 29 May 2026 11:37:07 GMT
• Title: Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning
• Abstract summary: This work studies the convergence of two-timescale approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow respectively.
• Score: 24.119393507396158
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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-timescale SA in reinforcement learning (RL) include temporal difference learning with gradient correction (TDC) and actor-critic methods. Previously, the stability (i.e., boundedness) and convergence of two-timescale SA were only established under i.i.d. noise. This work instead establishes the stability and convergence of two-timescale SA under Markovian noise, a setup that is more realistic in RL. Notably, we do not need to use any projection operator and the noise does not need to live in a compact space. Our key technical novelty is to control the fast timescale parameter with the running max of the slow timescale parameter, instead of with the current slow timescale parameter, as most prior works do. As a key application, we establish the first almost sure convergence of TDC with eligibility traces under off-policy learning with linear function approximation.

Related papers

• Parallel Continuous-Time Relative Localization with Augmented Clamped Non-Uniform B-Splines [13.396140913210637]
  This paper proposes CT-RIO, a novel Continuous-Time Relative-Inertial Odometry framework.<n>We employ Clamped Non-Uniform B-splines (C-NUBS) to represent robot states for the first time, eliminating the query-time delay.<n>It consistently outperforms state-of-the-art methods, with improvements of up to 60% under high-speed motion.
  arXiv  Detail & Related papers  (2026-02-25T15:23:18Z)
• Non-Asymptotic Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes [4.169915659794567]
  This work presents the first finite-time analysis for the last-iterate convergence of average-reward Q-learning with an asynchronous implementation.<n>A key feature of the algorithm we study is the use of adaptive stepsizes, which serve as local clocks for each state-action pair.
  arXiv  Detail & Related papers  (2025-04-25T23:41:14Z)
• Decoupled Functional Central Limit Theorems for Two-Time-Scale Stochastic Approximation [28.07082348529648]
  In two-time-scale approximations, two iterates are updated at different rates governed by distinct step sizes, with each update influencing the other.<n>Previous studies have demonstrated that the convergence rates of the error terms for these updates depend solely on their respective step sizes, a property known as decoupled convergence.<n>Our work fills this gap by establishing decoupled functional central limit theorems for two-time-scale SA, offering a more precise characterization of its behavior.
  arXiv  Detail & Related papers  (2024-12-22T15:43:01Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  We consider a setting in which $N$ agents aim to speedup a common Approximation problem by acting in parallel and communicating with a central server. To mitigate the effect of delays and stragglers, we propose textttDASA, a Delay-Adaptive algorithm for multi-agent Approximation.
  arXiv  Detail & Related papers  (2024-03-25T22:49:56Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise [8.739101659113157]
  We derive an upper bound on the error for the iterations of linear two-time-scale SA with Markovian noise.<n>A special case of linear two-time-scale SA that is extensively studied is linear SA with Polyak-Ruppert averaging.
  arXiv  Detail & Related papers  (2023-12-31T01:30:14Z)
• Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
  We propose an RL methodology attuned to the mixing time by employing a multi-level Monte Carlo estimator for the critic, the actor, and the average reward embedded within an actor-critic (AC) algorithm. We experimentally show that these alleviated restrictions on the technical conditions required for stability translate to superior performance in practice for RL problems with sparse rewards.
  arXiv  Detail & Related papers  (2023-01-28T04:12:56Z)
• Parameter-free Gradient Temporal Difference Learning [3.553493344868414]
  We develop gradient-based temporal difference algorithms for reinforcement learning. Our algorithms run in linear time and achieve high-probability convergence guarantees matching those of GTD2 up to $log$ factors. Our experiments demonstrate that our methods maintain high prediction performance relative to fully-tuned baselines, with no tuning whatsoever.
  arXiv  Detail & Related papers  (2021-05-10T06:07:05Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  We develop a doubly robust off-policy AC (DR-Off-PAC) for discounted MDP. DR-Off-PAC adopts a single timescale structure, in which both actor and critics are updated simultaneously with constant stepsize. We study the finite-time convergence rate and characterize the sample complexity for DR-Off-PAC to attain an $epsilon$-accurate optimal policy.
  arXiv  Detail & Related papers  (2021-02-23T18:56:13Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms [58.57004511121862]
  Actor-critic (AC) and natural actor-critic (NAC) algorithms are often executed in two ways for finding optimal policies. We show that two time-scale AC requires the overall sample complexity at the order of $mathcalO(epsilon-2.5log3(epsilon-1))$ to attain an $epsilon$-accurate stationary point. We develop novel techniques for bounding the bias error of the actor due to dynamically changing Markovian sampling.
  arXiv  Detail & Related papers  (2020-05-07T15:42:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.