mlsanityData to 7 Oct 2026

Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffer

arXiv 2601.01502 ↗First posted 4 Jan 2026math.OC stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

We introduce the Multiscale Experience Replay (MER) algorithm for solving a class of stochastic variational inequalities (VIs) in settings where samples are generated from a Markov chain and we have access to a memory buffer to store them. Rather than uniformly sampling from the buffer, MER utilizes a multi-scale sampling scheme to emulate the behavior of VI algorithms designed for independent and identically distributed samples, overcoming bias in the de facto serial scheme and thereby accelerating convergence. Notably, unlike standard sample-skipping variants of serial algorithms, MER is robust in that it achieves this acceleration in iteration complexity whenever possible, and without requiring knowledge of the mixing time of the Markov chain. We also discuss applications of MER, particularly in policy evaluation with temporal difference learning and in training generalized linear models with dependent data.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 33 of its 69 references that are in the map. First posted on arXiv 4 Jan 2026.

Builds on

33 of 69 references.

References · 33

  1. 2022Generative Adversarial Networkscited by 5,603
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  3. 2016Sample Efficient Actor-Critic with Experience Replaycited by 185
  4. 2020Revisiting Fundamentals of Experience Replaycited by 171
  5. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  6. 2017A Deeper Look at Experience Replaycited by 104
  7. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  8. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  9. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  10. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  11. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  12. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
21 more
  1. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  2. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  3. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
  4. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  5. 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
  6. 2020Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learningcited by 22
  7. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 22
  8. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  9. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  10. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  11. 2021Streaming Linear System Identification with Reverse Experience Replaycited by 17
  12. 2024Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theoremcited by 10
  13. 2022Analysis of Stochastic Processes through Replay Bufferscited by 9
  14. 2023Accelerated stochastic approximation with state-dependent noisecited by 8
  15. 2025Uncertainty quantification for Markov chain induced martingales with application to temporal difference learningcited by 8
  16. 2024Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequencecited by 4
  17. 2025Estimating stationary mass, frequency by frequencycited by 4
  18. 2022Introspective Experience Replay: Look Back When Surprisedcited by 3
  19. 2025Accurate, provable and fast polychromatic tomographic reconstruction: A variational inequality approachcited by 3
  20. 2025Auto-exploration for online reinforcement learningcited by 2
  21. 2025Beyond Maximum Likelihood: Variational Inequality Estimation for Generalized Linear Modelscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Next-token functional estimationcited by 0