Near-Optimal Reinforcement Learning with Self-Play under Adaptivity
  Constraints
Dan Qiao Yu-Xiang Wang
We study the problem of multi-agent reinforcement learning (MARL) with
adaptivity constraints -- a new problem motivated by real-world applications
where deployments of new policies are costly and the number of policy updates
must be minimized. For two-player zero-sum Markov Games, we design a (policy)
elimination based algorithm that achieves a regret of $\widetilde{O}(\sqrt{H^3
S^2 ABK})$, while the batch complexity is only $O(H+\log\log K)$. In the above,
$S$ denotes the number of states, $A,B$ are the number of actions for the two
players respectively, $H$ is the horizon and $K$ is the number of episodes.
Furthermore, we prove a batch complexity lower bound
$\Omega(\frac{H}{\log_{A}K}+\log\log K)$ for all algorithms with
$\widetilde{O}(\sqrt{K})$ regret bound, which matches our upper bound up to
logarithmic factors. As a byproduct, our techniques naturally extend to
learning bandit games and reward-free MARL within near optimal batch
complexity. To the best of our knowledge, these are the first line of results
towards understanding MARL with low adaptivity.