Provably Efficient Reinforcement Learning in Decentralized General-Sum
  Markov Games
  This paper addresses the problem of learning an equilibrium efficiently in
general-sum Markov games through decentralized multi-agent reinforcement
learning. Given the fundamental difficulty of calculating a Nash equilibrium
(NE), we instead aim at finding a coarse correlated equilibrium (CCE), a
solution concept that generalizes NE by allowing possible correlations among
the agents' strategies. We propose an algorithm in which each agent
independently runs optimistic V-learning (a variant of Q-learning) to
efficiently explore the unknown environment, while using a stabilized online
mirror descent (OMD) subroutine for policy updates. We show that the agents can
find an $\epsilon$-approximate CCE in at most $\widetilde{O}( H^6S A
/\epsilon^2)$ episodes, where $S$ is the number of states, $A$ is the size of
the largest individual action space, and $H$ is the length of an episode. This
appears to be the first sample complexity result for learning in generic
general-sum Markov games. Our results rely on a novel investigation of an
anytime high-probability regret bound for OMD with a dynamic learning rate and
weighted regret, which would be of independent interest. One key feature of our
algorithm is that it is fully \emph{decentralized}, in the sense that each
agent has access to only its local information, and is completely oblivious to
the presence of others. This way, our algorithm can readily scale up to an
arbitrary number of agents, without suffering from the exponential dependence
on the number of agents.
