Learning in Time-Varying Zero-Sum Games: Information-Theoretic and Computational Limits

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 $V_T.$ On the information-theoretic side, we show that sublinear $V_T$ 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 $\text{P}=\text{PPAD}$, stable learners with $n$ actions cannot achieve vanishing average dynamic NE regret within $\text{poly}(n)$ rounds. Our results reveal a separation between information-theoretic and computational learnability in time-varying zero-sum games.