Learning Algorithms with Self-Play: A New Approach to the Distributed Directory Problem

Many deep learning methods have been proposed recently to learn algorithms for combinatorial problems. However, most approaches focus on either supervised/imitation learning (the target algorithm is known) or single agent reinforcement learning (the input distribution is fixed). In some cases, however, the input distribution scales combinatorially as well and cannot easily be fully represented in a concise data set. In this paper, we propose a self-play approach to learn a distributed directory protocol to coordinate concurrent requests to a shared mobile resource among a network of nodes. The self-play is between two agents – a request agent, which finds worst case request inputs – and a route agent, which finds an algorithm that works well on the proposed worst case inputs (and consequently, works well on most queries). We show that our self-play approach is successful in learning an algorithm that works well across diverse request sequences. The empirical performance of the learnt algorithms is within the best known theoretical bounds, and sometimes significantly better than the best known upper bounds.