A Black-box Approach for Non-stationary Multi-agent Reinforcement
  Learning
Haozhe Jiang Qiwen Cui Zhihan Xiong Maryam Fazel Simon S. Du
We investigate learning the equilibria in non-stationary multi-agent systems
and address the challenges that differentiate multi-agent learning from
single-agent learning. Specifically, we focus on games with bandit feedback,
where testing an equilibrium can result in substantial regret even when the gap
to be tested is small, and the existence of multiple optimal solutions
(equilibria) in stationary games poses extra challenges. To overcome these
obstacles, we propose a versatile black-box approach applicable to a broad
spectrum of problems, such as general-sum games, potential games, and Markov
games, when equipped with appropriate learning and testing oracles for
stationary environments. Our algorithms can achieve
$\widetilde{O}\left(\Delta^{1/4}T^{3/4}\right)$ regret when the degree of
nonstationarity, as measured by total variation $\Delta$, is known, and
$\widetilde{O}\left(\Delta^{1/5}T^{4/5}\right)$ regret when $\Delta$ is
unknown, where $T$ is the number of rounds. Meanwhile, our algorithm inherits
the favorable dependence on number of agents from the oracles. As a side
contribution that may be independent of interest, we show how to test for
various types of equilibria by a black-box reduction to single-agent learning,
which includes Nash equilibria, correlated equilibria, and coarse correlated
equilibria.