Learning in Time-Varying Zero-Sum Games: Information-Theoretic and Computational Limits
Abstract
In many multi-agent learning settings, the underlying game evolves over time, raising the question of whether learning remains possible in a changing environment. In this setting, Zhang et al. [2022] introduced dynamic Nash equilibrium (NE) regret as a performance measure for learning in time-varying zero-sum games. We study the information-theoretic and computational limits of achieving small dynamic NE regret, with the nonstationarity of the environment measured by the second-order path-length variation of the payoff matrices, denoted by On the information-theoretic side, we show that sublinear is sufficient to achieve vanishing average dynamic NE regret, and complement this result with a variation-dependent lower bound. On the computational side, we show that, unless , stable learners with actions cannot achieve vanishing average dynamic NE regret within rounds. Our results reveal a separation between information-theoretic and computational learnability in time-varying zero-sum games.
- Primary area:
- learning theory
- Keywords:
- Time varying games, dynamic NE regret, PPAD, game theory, no regret learning