Abstract
In the field of reinforcement learning (RL), Q-learning has emerged as a cornerstone method, yet its theoretical performance in multi-agent settings often relies on pessimistic worst-case analysis. This paper provides a significant advancement by establishing the first gap-dependent logarithmic regret bounds for two-player turn-based stochastic games (2-TBSG). By moving beyond the standard $O(\sqrt{K})$ regret bounds, we demonstrate that Q-learning algorithms can achieve $O(\log K)$ cumulative regret when a sub-optimality gap exists. We extend these results across three primary settings: episodic tabular, discounted infinite-horizon, and linear Markov Decision Processes (MDPs).
Introduction
Measuring the efficiency of an RL algorithm typically involves analyzing its regret—the difference between the cumulative reward an agent receives and the reward it would have received by following an optimal policy from the start. In single-agent RL, it is well-established that if there is a "gap" between the value of the optimal action and the next-best action, algorithms can achieve logarithmic regret, which is significantly more efficient than the $\sqrt{K}$ growth seen in gap-free environments.
However, extending this logic to two-player games, such as turn-based versions of Chess or Go, presents unique challenges. In a zero-sum game, "sub-optimality" is relative; an action that is poor for the "max-player" might be highly beneficial for the "min-player." Defining a consistent gap and controlling the influence of an opponent's strategy requires a more sophisticated mathematical framework than single-agent scenarios.
Defining the Sub-optimality Gap in Games
A core innovation of this research is the definition of the Positive Gap ($gap^+_{\min}$). While gaps in games can technically be zero or negative depending on the player's perspective, the authors identify that the absolute difference between the Nash Equilibrium value and the value of a sub-optimal action provides a stable anchor for analysis. This metric allows the researchers to quantify the "clarity" of the environment, even when two players have diametrically opposed objectives.
Methodology: Dual Confidence Bounds and Peeling
To achieve logarithmic regret, the authors analyze a Nash Q-learning variant that incorporates two specific techniques:
- Dual Confidence Bounds (UCB and LCB): Standard Q-learning often uses an Upper Confidence Bound (UCB) to encourage exploration. In the 2-TBSG setting, the authors employ both UCB and a Lower Confidence Bound (LCB) simultaneously. This approach "sandwiches" the true Nash Equilibrium value, accounting for the max-player's optimism and the min-player's pessimism.
- The Peeling Argument: To prove the logarithmic bound, the researchers utilize a "peeling" technique. They divide the possible sub-optimality gaps into logarithmic intervals and bound the number of times the algorithm can select an action within each interval before it successfully "learns" the superior strategy.
Theoretical Results
The paper establishes the first logarithmic regret bounds for 2-TBSG across three distinct settings:
1. Tabular Episodic Setting
In the tabular setting, where states and actions are discrete and finite, the total regret scales as: $$O\left(\frac{H^6 SA \log(SAT)}{gap^+_{\min}}\right)$$ where $H$ is the horizon, $S$ is the state space, and $A$ is the action space. This matches the theoretical lower bound up to a logarithmic term.
2. Discounted Infinite-Horizon Setting
The authors extend the conclusion to discounted games with an infinite horizon. They prove that even without a fixed end-point, the gap-dependent logarithmic regret bound holds, showing the robustness of the Nash Q-learning approach.
3. Linear MDP Assumption
To address high-dimensional state spaces where tabular methods fail, the authors apply their analysis to Linear MDPs. Under both centralized and independent settings, they achieve a regret bound of: $$O\left(\frac{d^3 H^5 \log(K)}{gap^+_{\min}}\right)$$ where $d$ represents the dimension of the feature mapping. This demonstrates that the benefits of logarithmic regret are applicable to complex environments requiring function approximation.
Discussion and Future Work
While these results represent a theoretical breakthrough, certain limitations remain. The current bounds feature a high dependency on the horizon ($H^6$ in the tabular case), which is likely higher than what is achievable in practice. Furthermore, this work is specifically tailored to turn-based games.
Future research directions include:
- Simultaneous-Move Games: Extending these bounds to games where players act at the same time (e.g., Rock-Paper-Scissors), which requires mixed strategies and complicates the definition of a sub-optimality gap.
- Multi-player Scaling: Investigating whether these logarithmic benefits persist in many-player or mean-field game scenarios.
In conclusion, this paper bridges a critical gap in multi-agent RL theory, proving that when environments offer clear distinctions between actions, two-player games can be solved with the same logarithmic efficiency as single-agent tasks.
Summary updated