# No-Regret Learning in Time-Varying Zero-Sum Games

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 37 references that are in the map.
- First posted on arXiv 30 Jan 2022.

## Builds on (most cited first, 19 of 19)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Tracking the Best Expert in Non-stationary Stochastic Environments](https://mlsanity.com/paper/1712.00578/) (2017)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Multi-agent online learning in time-varying games](https://mlsanity.com/paper/1809.03066/) (2018)
- [Online Learning in Periodic Zero-Sum Games](https://mlsanity.com/paper/2111.03377/) (2021)
- [Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization](https://mlsanity.com/paper/1912.01698/) (2019)

## Built on by (most cited first, 30 of 36)

- [Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning](https://mlsanity.com/paper/2407.00617/) (2024)
- [Adapting to Online Label Shift with Provable Guarantees](https://mlsanity.com/paper/2207.02121/) (2022)
- [AdaSociety: An Adaptive Environment with Social Structures for Multi-Agent Decision-Making](https://mlsanity.com/paper/2411.03865/) (2024)
- [Adapting to Continuous Covariate Shift via Online Density Ratio Estimation](https://mlsanity.com/paper/2302.02552/) (2023)
- [Efficient Methods for Non-stationary Online Learning](https://mlsanity.com/paper/2309.08911/) (2023)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2209.12430/) (2022)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach](https://mlsanity.com/paper/2307.08360/) (2023)
- [Regret Minimization in Stackelberg Games with Side Information](https://mlsanity.com/paper/2402.08576/) (2024)
- [Gradient-Variation Online Adaptivity for Accelerated Optimization with H"older Smoothness](https://mlsanity.com/paper/2511.02276/) (2025)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2306.07465/) (2023)
- [Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games](https://mlsanity.com/paper/2406.10605/) (2024)
- [Proximal Point Method for Online Saddle Point Problem](https://mlsanity.com/paper/2407.04591/) (2024)
- [Parameter-free Algorithms for the Stochastically Extended Adversarial Model](https://mlsanity.com/paper/2510.04685/) (2025)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games](https://mlsanity.com/paper/2505.17277/) (2025)
- [cMALC-D: Contextual Multi-Agent LLM-Guided Curriculum Learning with Diversity-Based Context Blending](https://mlsanity.com/paper/2508.20818/) (2025)
- [Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach](https://mlsanity.com/paper/2601.21243/) (2026)
- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)
- [Robust Correlated Equilibrium: Definition and Computation](https://mlsanity.com/paper/2311.17592/) (2023)
- [Tracking solutions of time-varying variational inequalities](https://mlsanity.com/paper/2406.14059/) (2024)
- [A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization](https://mlsanity.com/paper/2509.07901/) (2025)
- [Learning from Delayed Feedback in Games via Extra Prediction](https://mlsanity.com/paper/2509.22426/) (2025)
- [Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality](https://mlsanity.com/paper/2511.06597/) (2025)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [Bandit Convex Optimization with Gradient Prediction Adaptivity](https://mlsanity.com/paper/2605.22191/) (2026)
- [On the Relation Between Interval Regret and Dynamic Regret](https://mlsanity.com/paper/2609.34423/) (2026)

## Abstract (arXiv)

Learning from repeated play in a fixed two-player zero-sum game is a classic problem in game theory and online learning. We consider a variant of this problem where the game payoff matrix changes over time, possibly in an adversarial manner. We first present three performance measures to guide the algorithmic design for this problem: 1) the well-studied individual regret, 2) an extension of duality gap, and 3) a new measure called dynamic Nash Equilibrium regret, which quantifies the cumulative difference between the player's payoff and the minimax game value. Next, we develop a single parameter-free algorithm that simultaneously enjoys favorable guarantees under all these three performance measures. These guarantees are adaptive to different non-stationarity measures of the payoff matrices and, importantly, recover the best known results when the payoff matrix is fixed. Our algorithm is based on a two-layer structure with a meta-algorithm learning over a group of black-box base-learners satisfying a certain property, along with several novel ingredients specifically designed for the time-varying game setting. Empirical results further validate the effectiveness of our algorithm.