Tsuchiya's hybrid regularization achieves sublogarithmic swap regret in multiplayer games

Taira Tsuchiya, a researcher in game theory and machine learning, has released a breakthrough paper on arXiv (2608.04149) that overturns a longstanding complexity barrier in uncoupled learning dynamics. In multiplayer general-sum games where all players follow the same algorithm, the previous best swap regret grew logarithmically with the horizon T. Tsuchiya's new dynamics achieve just O(nm²√(log m log T)) swap regret—the first sublogarithmic individual guarantee for this setting. This directly implies that the time-averaged product distribution of play is an O(nm²√(log m log T)/T)-approximate correlated equilibrium, a dramatic speedup for decentralized multi-agent learning.

The key innovation is a hybrid regularizer that combines negative Shannon entropy with a log-barrier within the optimistic follow-the-regularized-leader framework, built atop the classic Blum-Mansour reduction. The entropy term controls optimistic prediction error, while the log-barrier constrains transition-matrix movement via Bregman divergence. A novel sensitivity theorem for stationary distributions of Markov chains—which avoids mixing parameters or smallest transition probabilities—transfers this control to actual played strategies, simplifying the analysis and bypassing local-norm and self-concordance arguments. The result is robust: an adversarially robust variant achieves O(nm²√(log m log T) + √(mT log m)) swap regret even under arbitrary utility sequences, and a horizon-free version requires no prior knowledge of T. This work addresses a core open question in the theory of learning in games and provides practical guarantees for large-scale multi-agent reinforcement learning systems.