Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints

This paper considers the problem of multi-agent reinforcement learning (multi-agent RL), where multiple agents aim to make decisions simultaneously in an unfamiliar environment to maximize their individual cumulative rewards. Multi-agent RL is used not only in large-scale strategy games like Go [Silver et al., 2017], Poker [Brown and Sandholm, 2019] and MOBA games [Ye et al., 2020], but also in various real-world applications such as autonomous driving[Shalev-Shwartz et al., 2016], household power management [Chung et al., 2020], and computer networking[Bhattacharyya et al., 2019]. The sheer amount of computation needed for self-play-based learning in these applications often demands the algorithm to run in a distributed fashion where the communication cost becomes a bottleneck. In such circumstances, instead of syncing up after each single trajectory, a more practical alternative is to assign a larger batch of work for each machine to perform independently and sync up only sporadically. The need for infrequent communication could be hard constraints in applications such as autonomous driving [Shalev-Shwartz et al., 2016]. Deploying new policies to vehicle firmware takes weeks, while new data are being collected in millions of cars every second. These constraints render standard multi-agent RL algorithms that require altering the policy after each new data point impractical. In the scenarios discussed above, the agent needs to minimize the number of policy deployments while learning a good policy using (nearly) the same number of samples as its fully-adaptive counterparts.