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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 69 references that are in the map.
- First posted on arXiv 4 Jan 2026.

## Builds on (most cited first, 30 of 33)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Sample Efficient Actor-Critic with Experience Replay](https://mlsanity.com/paper/1611.01224/) (2016)
- [Revisiting Fundamentals of Experience Replay](https://mlsanity.com/paper/2007.06700/) (2020)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [A Deeper Look at Experience Replay](https://mlsanity.com/paper/1712.01275/) (2017)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (2021)
- [Extragradient method with variance reduction for stochastic variational inequalities](https://mlsanity.com/paper/1703.00260/) (2017)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operators](https://mlsanity.com/paper/1311.2776/) (2013)
- [Projected Reflected Gradient Methods for Monotone Variational Inequalities](https://mlsanity.com/paper/1502.04968/) (2015)
- [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020)
- [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)
- [Improved Regret Bound and Experience Replay in Regularized Policy Iteration](https://mlsanity.com/paper/2102.12611/) (2021)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning](https://mlsanity.com/paper/2502.13822/) (2025)
- [Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem](https://mlsanity.com/paper/2410.21704/) (2024)
- [Analysis of Stochastic Processes through Replay Buffers](https://mlsanity.com/paper/2206.12848/) (2022)
- [Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence](https://mlsanity.com/paper/2404.05819/) (2024)
- [Estimating stationary mass, frequency by frequency](https://mlsanity.com/paper/2503.12808/) (2025)
- [Introspective Experience Replay: Look Back When Surprised](https://mlsanity.com/paper/2206.03171/) (2022)

## Built on by (most cited first, 2 of 2)

- [Instance-optimal stochastic convex optimization: Can we improve upon sample-average and robust stochastic approximation?](https://mlsanity.com/paper/2603.25657/) (2026)
- [Next-token functional estimation](https://mlsanity.com/paper/2609.19529/) (2026)

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