${\alpha }^{\alpha }$-Rank: Practically Scaling $\alpha$-Rank through Stochastic Optimisation

Abstract

Recently, $\alpha$-Rank, a graph-based algorithm, has been proposed as a solution to ranking joint policy profiles in large scale multi-agent systems. $\alpha$-Rank claimed tractability through a polynomial time implementation with respect to the total number of pure strategy profiles. Here, we note that inputs to the algorithm were not clearly specified in the original presentation; as such, we deem complexity claims as not grounded, and conjecture solving $\alpha$-Rank is NP-hard. The authors of $\alpha$-Rank suggested that the input to $\alpha$-Rank can be an exponentially-sized payoff matrix; a claim promised to be clarified in subsequent manuscripts. Even though $\alpha$-Rank exhibits a polynomial-time solution with respect to such an input, we further reflect additional critical problems. We demonstrate that due to the need of constructing an exponentially large Markov chain, $\alpha$-Rank is infeasible beyond a small finite number of agents. We ground these claims by adopting amount of dollars spent as a non-refutable evaluation metric. Realising such scalability issue, we present a stochastic implementation of $\alpha$-Rank with a double oracle mechanism allowing for reductions in joint strategy spaces. Our method, ${\alpha }^{\alpha }$-Rank, does not need to save exponentially-large transition matrix, and can terminate early under required precision. Although theoretically our method exhibits similar worst-case complexity guarantees compared to $\alpha$-Rank, it allows us, for the first time, to practically conduct large-scale multi-agent evaluations. On $10^4\times 10^4$ random matrices, we achieve $1000x$ speed reduction. Furthermore, we also show successful results on large joint strategy profiles with a maximum size in the order of $\mathcal{O}(2^{25})$ ($\approx 33$ million joint strategies) -- a setting not evaluable using $\alpha$-Rank with reasonable computational budget.

arXiv commentAAMAS 2020 Full Paper

References in corpus (13)

• Adam: A Method for Stochastic Optimization
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Mean Field Multi-Agent Reinforcement Learning
• Maximum a Posteriori Policy Optimisation
• OpenSpiel: A Framework for Reinforcement Learning in Games
• Emergent Coordination Through Competition
• Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
• Open-ended Learning in Symmetric Zero-sum Games
• A Generalized Training Approach for Multiagent Learning
• A Study of AI Population Dynamics with Million-agent Reinforcement Learning
• An Information-Theoretic Optimality Principle for Deep Reinforcement Learning
• Modelling Bounded Rationality in Multi-Agent Interactions by Generalized Recursive Reasoning
• Bi-level Actor-Critic for Multi-agent Coordination

Cited by in corpus (1)

• Learning in Nonzero-Sum Stochastic Games with Potentials