Refined Sample Complexity for Markov Games with Independent Linear
  Function Approximation
Yan Dai Qiwen Cui Simon S. Du
Markov Games (MG) is an important model for Multi-Agent Reinforcement
Learning (MARL). It was long believed that the "curse of multi-agents" (i.e.,
the algorithmic performance drops exponentially with the number of agents) is
unavoidable until several recent works (Daskalakis et al., 2023; Cui et al.,
2023; Wang et al., 2023. While these works did resolve the curse of
multi-agents, when the state spaces are prohibitively large and (linear)
function approximations are deployed, they either had a slower convergence rate
of $O(T^{-1/4})$ or brought a polynomial dependency on the number of actions
$A_{\max}$ -- which is avoidable in single-agent cases even when the loss
functions can arbitrarily vary with time (Dai et al., 2023). This paper first
refines the `AVLPR` framework by Wang et al. (2023), with an insight of
*data-dependent* (i.e., stochastic) pessimistic estimation of the
sub-optimality gap, allowing a broader choice of plug-in algorithms. When
specialized to MGs with independent linear function approximations, we propose
novel *action-dependent bonuses* to cover occasionally extreme estimation
errors. With the help of state-of-the-art techniques from the single-agent RL
literature, we give the first algorithm that tackles the curse of multi-agents,
attains the optimal $O(T^{-1/2})$ convergence rate, and avoids
$\text{poly}(A_{\max})$ dependency simultaneously.