Improved Sample Complexity for Markov Games via Variance-Aware Bandit Learning

We study the problem of learning in multi-player general-sum Markov games. In the simulator setting, where the learner can sample the next state conditioned on an arbitrary state action pair, the previous best-known upper bound of the sample complexity for learning an $\varepsilon$-approximate coarse correlated equilibrium (CCE) is $\widetilde{O}(H^4S\sum_{i=1}^m A_i/\varepsilon^2)$ (Li et al., 2022), where $H$ is the horizon, $S$ is the number of states, and $A_i$ denotes the number of actions for the $i$-th player. This work improves the upper bound to $\widetilde{O}(H^4S\max_{i\in[m]} A_i/\varepsilon^2)$, matching the lower bound of $\Omega(H^4S\max_{i\in[m]} A_i/\varepsilon^2)$ (Li et al., 2022). In the online setting, in which the learner can only sample a trajectory, the previous best-known sample complexity upper bound for learning CCE in multi-player general-sum Markov games is $\widetilde{O}(H^6S\max_{i\in[m]} A_i/\varepsilon^2)$ (Song et al., 2021; Jin et al., 2024; Mao et al., 2022). In this work, we improve this to $\widetilde{O}(H^5S\max_{i\in[m]} A_i/\varepsilon^2)$. To our knowledge, this is the tightest upper bound that breaks the curse of multi-agency. The core of our algorithmic design and analysis is the new gap decomposition and, in particular, a bandit algorithm with a high-probability empirical variance regret bound, which might be of independent interest.