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

Mengxiao Zhang, Peng Zhao, Haipeng Luo, Zhi-Hua Zhou

Introduction

Learning in repeated two-player zero-sum games is a cornerstone of game theory and online learning. Traditionally, research has focused on stationary environments where the payoff matrix remains fixed. In such settings, players aim to minimize regret and converge to a Nash Equilibrium (NE). However, modern applications—ranging from high-frequency trading to adversarial machine learning—often involve "rules of the game" that shift over time, sometimes even in response to the players' actions. This paper addresses the challenge of no-regret learning in these time-varying environments, proposing new metrics and a robust, parameter-free algorithm.

The Challenge of Non-Stationarity

In a static zero-sum game, the goal is well-defined: reach a Nash Equilibrium where neither player can improve their outcome by changing their strategy unilaterally. In a time-varying game, the payoff matrix $A_t$ changes at each round $t$. This non-stationarity makes standard performance measures problematic.

A significant contribution of this work is identifying the flaws in the existing "NE-regret" metric. NE-regret typically compares players' performance against the minimax value of the average payoff matrix over time. The authors demonstrate that this can be highly misleading; even if players choose the optimal Nash Equilibrium for every single round, their cumulative NE-regret could still grow linearly if the game changes rapidly. This disconnect necessitates a more granular approach to measuring success in dynamic environments.

Proposed Performance Measures

To better capture the nuances of time-varying games, the authors propose three distinct performance measures:

  1. Individual Regret: This is the standard online learning metric, measuring how much a player loses by not having played the best fixed strategy in hindsight.
  2. Duality Gap: This measures how close the joint strategies of both players are to a Nash Equilibrium at any given time.
  3. Dynamic NE-regret: This is a novel measure introduced to fix the shortcomings of standard NE-regret. It compares a player's actual payoff at each round to the minimax value of the game at that specific round. By benchmarking against the instantaneous game value, it provides a more accurate reflection of performance in a shifting landscape.

Algorithmic Framework: The Two-Layer Approach

The authors introduce a parameter-free algorithm designed to provide simultaneous guarantees across all three metrics. A key difficulty in non-stationary learning is that the optimal learning rate (step size) depends on the "path-length" or the total variation of the environment, which is usually unknown in advance.

To solve this, the proposed algorithm uses a two-layer architecture:

  • Base-Learners: A group of black-box algorithms, each operating with a different fixed step size. These base-learners are designed to satisfy a "Dynamic Regret bounded by Variation in Utilities" (DRVU) property, ensuring their regret is tied to environmental changes.
  • Meta-Algorithm: A higher-level learner that aggregates the strategies of the base-learners.

The meta-algorithm incorporates two novel components:

  • Stability Correction: This term biases the meta-learner toward base-learners that exhibit more stable behavior. This effectively filters out the "noise" generated by the opponent's shifting strategies and the changing payoff matrix.
  • Dummy Learners: To maintain control over the duality gap, the pool of base-learners includes "dummy" learners that always play a fixed action. This ensures the algorithm doesn't drift too far from a stable strategy when the game is relatively stationary.

Theoretical and Empirical Results

The primary theoretical contribution is a set of upper bounds for the three performance measures, which are adaptive to different measures of non-stationarity: $V_T$ (variation in payoffs), $P_T$ (variation in strategies), and $W_T$ (variation in the minimax value).

Summary of theoretical guarantees for time-varying and stationary games compared to prior work.

As shown in the table above, the algorithm achieves near-optimal regret bounds in time-varying settings. Crucially, it also exhibits "stationary recovery": if the game stops changing ($V_T, P_T, W_T = 0$), the algorithm automatically recovers the best-known $O(1)$ individual regret and NE-regret bounds for fixed games, without needing to be manually retuned.

Empirical evaluations using synthetic data further validate these results. In environments where the Nash Equilibrium and payoff matrices drift at varying rates, the proposed algorithm consistently matches or outperforms base-learners that were manually tuned with perfect knowledge of the environment's variation.

Conclusion

This work advances the state of no-regret learning by providing a robust framework for time-varying zero-sum games. By introducing Dynamic NE-regret and a parameter-free two-layer algorithm, the authors bridge the gap between theoretical stationary models and the dynamic reality of complex systems. Future research directions include extending these dynamic guarantees to multi-player or general-sum games and optimizing the computational overhead inherent in multi-layer learning architectures.

Summary updated

Abstract

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.
BibTeX
@inproceedings{zhang2022no,
  author = {Mengxiao Zhang and Peng Zhao and Haipeng Luo and Zhi-Hua Zhou},
  title = {{No-Regret Learning in Time-Varying Zero-Sum Games}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=9UiHLAJhlg},
}
Figure