mlsanityData to 7 Oct 2026

Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise

arXiv 2409.19546 ↗First posted 29 Sep 2024cs.LG cs.AI math.OCcited by 10

Not on the map. Why?

Abstract (arXiv)

Stochastic approximation is a powerful class of algorithms with celebrated success. However, a large body of previous analysis focuses on stochastic approximations driven by contractive operators, which is not applicable in some important reinforcement learning settings like the average reward setting. This work instead investigates stochastic approximations with merely nonexpansive operators. In particular, we study nonexpansive stochastic approximations with Markovian noise, providing both asymptotic and finite sample analysis. Key to our analysis are novel bounds of noise terms resulting from the Poisson equation. As an application, we prove for the first time that classical tabular average reward temporal difference learning converges to a sample-path dependent fixed point.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 10 of its 43 references that are in the map. First posted on arXiv 29 Sep 2024.

Builds on

10 of 43 references.

References · 10

  1. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  2. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  3. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  4. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 29
  5. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 23
  6. 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noisecited by 23
  7. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  8. 2023Off-Policy Average Reward Actor-Critic with Deterministic Policy Searchcited by 10
  9. 2021Average-Reward Learning and Planning with Optionscited by 8
  10. 2017Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spacescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 8.

10 papers.

  1. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  2. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 5
  3. 2026Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processescited by 2
  4. 2026A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averagingcited by 2
  5. 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
  6. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  7. 2026A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Mapscited by 1
  8. 2026On the Divergence of Differential Temporal Difference Learning without Local Clockscited by 0
  9. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 0
  10. 2026High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependencecited by 0