  A unique challenge in Multi-Agent Reinforcement Learning (MARL) is the curse
of multiagency, where the description length of the game as well as the
complexity of many existing learning algorithms scale exponentially with the
number of agents. While recent works successfully address this challenge under
the model of tabular Markov Games, their mechanisms critically rely on the
number of states being finite and small, and do not extend to practical
scenarios with enormous state spaces where function approximation must be used
to approximate value functions or policies.
  This paper presents the first line of MARL algorithms that provably resolve
the curse of multiagency under function approximation. We design a new
decentralized algorithm -- V-Learning with Policy Replay, which gives the first
polynomial sample complexity results for learning approximate Coarse Correlated
Equilibria (CCEs) of Markov Games under decentralized linear function
approximation. Our algorithm always outputs Markov CCEs, and achieves an
optimal rate of $\widetilde{\mathcal{O}}(\epsilon^{-2})$ for finding
$\epsilon$-optimal solutions. Also, when restricted to the tabular case, our
result improves over the current best decentralized result
$\widetilde{\mathcal{O}}(\epsilon^{-3})$ for finding Markov CCEs. We further
present an alternative algorithm -- Decentralized Optimistic Policy Mirror
Descent, which finds policy-class-restricted CCEs using a polynomial number of
samples. In exchange for learning a weaker version of CCEs, this algorithm
applies to a wider range of problems under generic function approximation, such
as linear quadratic games and MARL problems with low ''marginal'' Eluder
dimension.
