Abstract
This paper establishes the first instance-dependent logarithmic regret bounds for two-player turn-based stochastic games (2-TBSG). While traditional reinforcement learning (RL) theory for multi-agent systems often relies on pessimistic worst-case $\sqrt{K}$ regret bounds, this work introduces the concept of a "minimal positive sub-optimality gap" ($gap^+_{min}$) to bridge the gap between single-agent and multi-agent theoretical guarantees. We demonstrate that Nash Q-learning algorithms can achieve logarithmic regret in both tabular and linear function approximation settings, matching theoretical lower bounds up to logarithmic factors.
Introduction
In reinforcement learning, the performance of an algorithm is typically measured by its regret: the cumulative difference between the reward an optimal policy would have achieved and the reward actually collected by the agent. In single-agent environments, researchers have long utilized "gap-dependent" analysis to prove that regret can scale logarithmically with the number of episodes ($K$), provided there is a clear separation between the best and second-best actions.
However, extending these results to two-player zero-sum games is non-trivial. In these settings, one player (the max-player) seeks to maximize the value, while the opponent (the min-player) seeks to minimize it. This adversarial structure complicates the definition of a "gap," as sub-optimality is relative to the opponent's strategy and the Nash equilibrium. Consequently, most existing literature has defaulted to "worst-case" bounds that scale with $\sqrt{K}$. This paper addresses this gap by providing a framework for logarithmic regret in two-player turn-based stochastic games (2-TBSG).
The Minimal Positive Gap
The core innovation of this work is the definition of the Minimal Positive Gap ($gap^+_{min}$). In a single-agent MDP, the gap is simply the difference between the optimal value and the value of a sub-optimal action. In a zero-sum game, the authors define the gap as the absolute value of the difference between the Nash Q-value and the value of a specific action.
By focusing on the absolute value, the authors symmetrically account for the mistakes of both the max-player and the min-player. This allows the analysis to bypass the sign-flipping issues inherent in min-max optimization and provides a stable metric for measuring how quickly an algorithm converges toward the Nash equilibrium.
Algorithmic Framework
The authors analyze Nash Q-learning and its variants across different settings. The algorithms utilize several key technical components:
- Simultaneous Confidence Bounds: To account for the dual nature of the game, the algorithm maintains an Upper Confidence Bound (UCB) to guide the max-player and a Lower Confidence Bound (LCB) to guide the min-player.
- Peeling Argument: To prove the logarithmic bound, the authors employ a "peeling" technique. They partition the potential sub-optimality gaps into logarithmic intervals and bound the number of times the algorithm's estimation error falls into each specific interval.
- Linear Function Approximation: For high-dimensional state spaces, the authors extend the analysis to Linear MDPs. They propose LSVI-2TBSG (Least-Squares Value Iteration), which handles both centralized control and independent learning settings where one player acts against an arbitrary opponent.
Theoretical Results
The paper establishes the first logarithmic regret bounds for 2-TBSG in three primary scenarios:
Tabular Episodic Setting
In the tabular setting with a fixed horizon $H$, the expected regret is bounded by: $$\mathcal{O}\left(\frac{H^6 SA \log(SAT)}{gap^+_{min}}\right)$$ where $S$ is the state space and $A$ is the action space. This result is significant because it matches the theoretical lower bound for this class of games up to logarithmic factors.
Tabular Discounted Setting
The authors demonstrate that the gap-dependent logic extends to infinite-horizon discounted settings. This proves that the logarithmic convergence rate is a fundamental property of the game structure, not just an artifact of finite horizons.
Linear Function Approximation
Under the Linear MDP assumption, where dynamics and rewards are linear functions of a feature mapping, the authors achieve a regret bound of: $$\tilde{\mathcal{O}}\left(\frac{d^3 H^5 \log(K)}{gap^+_{min}}\right)$$ where $d$ is the feature dimension. This represents a substantial improvement over previous $\sqrt{K}$ bounds for linear multi-agent RL.
Discussion and Future Work
While this work provides a major step forward in multi-agent RL theory, several challenges remain. The current bounds match lower bounds only "up to a logarithmic term," suggesting that tighter constants may be possible. Furthermore, the analysis is restricted to turn-based games. In simultaneous-move games, the Nash equilibrium often involves mixed strategies (probability distributions), which makes defining a discrete "gap" significantly more complex.
Future research may explore extending these gap-dependent bounds to simultaneous-move games and general non-linear function approximation, such as deep neural networks, to further bridge the gap between theory and practical multi-agent reinforcement learning.
Summary updated