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 $\epsilon$-approximate coarse correlated equilibrium (CCE) is $\tilde{O}(H^{4}S{\sum }_{i=1}^m{A}_i/{\epsilon }^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 $\tilde{O}(H^{4}S{\max }_{i\in [m]}{A}_i/{\epsilon }^2)$, matching the lower bound of $\Omega (H^{4}S{\max }_{i\in [m]}{A}_i/{\epsilon }^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 $\tilde{O}(H^{6}S{\max }_{i\in [m]}{A}_i/{\epsilon }^2)$ (Song et al., 2021; Jin et al., 2024; Mao et al., 2022). In this work, we improve this to $\tilde{O}(H^{5}S{\max }_{i\in [m]}{A}_i/{\epsilon }^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.