Although challenging, strategy profile evaluation in large connected learner networks is crucial for enabling the next wave of machine learning applications. Recently, $\alpha$-Rank, an evolutionary algorithm, has been proposed as a solution for ranking joint policy profiles in multi-agent systems. $\alpha$-Rank claimed scalability through a polynomial time implementation with respect to the total number of pure strategy profiles. In this paper, we formally prove that such a claim is not grounded. In fact, we show that $\alpha$-Rank exhibits an exponential complexity in number of agents, hindering its application beyond a small finite number of joint profiles. Realizing such a limitation, we contribute by proposing a scalable evaluation protocol that we title  $\alpha^{\alpha}$-Rank. Our method combines evolutionary dynamics with stochastic optimization and double oracles for \emph{truly} scalable ranking with linear (in number of agents) time and memory complexities. Our contributions allow us, for the first time, to conduct large-scale evaluation experiments of multi-agent systems, where we show successful results on large joint strategy profiles with sizes in the  order of $\mathcal{O}(2^{25})$ (i.e., $\approx \text{$33$ million strategies}$) -- a setting not evaluable using current techniques. Scalable policy evaluation and learning have been long-standing challenges in multi-agent reinforcement learning (MARL) with two difficulties obstructing progress. First, joint-strategy spaces exponentially explode when a large number of strategic decision-makers is considered, and second, the underlying game dynamics may exhibit cyclic behavior (e.g. the game of Rock-Paper-Scissor) rendering an appropriate evaluation criteria non-trivial. Focusing on the second challenge, much work in multi-agent systems followed a game-theoretic treatment proposing fixed-points, e.g., Nash (Nash et al., 1950) equilibrium, as potentially valid evaluation metrics. Though appealing, such measures are normative only when prescribing behaviors of perfectly rational agents -an assumption rarely met in reality Grau-Moya et al. (2018) ; Wen et al. (2019) . In fact, many game dynamics have been proven not converge to any fixed-point equilibria (Hart & Mas-Colell, 2003; Viossat, 2007) , but rather to limit cycles (Palaiopanos et al., 2017; Bowling & Veloso, 2001) . Apart from these aforementioned inconsistencies, solving for a Nash equilibrium even for "simple" settings, e.g. two-player games is known to be PPAD-complete (Chen & Deng, 2005 ) -a demanding complexity class when it comes to computational requirements. To address some of the above limitations, recently proposed α-Rank as a graph-based game-theoretic solution to multi-agent evaluation. α-Rank adopts Markov Conley Chains to highlight the presence of cycles in game dynamics, and attempts to compute stationary distributions as a mean for strategy profile ranking. Though successful in small-scale applications, α-Rank severely suffers in scalability contrary to polynomial time claims made in . In fact, we show that α-Rank exhibits exponential time and memory complexities shedding light on the small-scale empirical study conducted in , whereby the largest reported game included only four agents with four available strategies each. In this work, we put forward α α -Rank as a scalable alternative for multi-agent evaluation with linear time and memory demands. Our method combines numerical optimization with evolutionary game theory for a scalable solver capable of handling large joint spaces with millions of strategy profiles. To handle even larger profiles, e.g., tens to hundreds of millions, we further introduce an oracle Figure 1: Example of population based evaluation on N = 3 learners each with 3 strategies and 5 copies. a) Each population obtains a fitness value P i depending on the strategies chosen, b) mutation strategy (red star), and c) population either selecting original strategy, or adopting the novel strategy. ( McMahan et al., 2003) mechanism transforming joint evaluation into a sequence of incremental sub-games with varying sizes. Given our algorithmic advancements, we justify our claims in a largescale empirical study involving systems with O(2 25 ) possible strategy profiles. We first demonstrate the computation advantages of α α -Rank on varying size stochastic matrices against other implementations in Numpy, PyTorch, and OpenSpiel . With these successes, we then consider experiments unsolvable by current techniques. Precisely, we evaluate multi-agent systems in self-driving and Ising model scenarios each exhibiting a prohibitively-large strategy space (i.e., order of thousands for the former, and tens of millions for the latter). Here, we again show that α α -Rank is capable of recovering correct strategy ranking in such complex domains. So far, we have presented scalable multi-agent evaluations through stochastic optimization. We can further boost scalability (to tens of millions of joint profiles) of our method by introducing an oracle mechanism. The heuristic of oracles was first introduced in solving large-scale zero-sum matrix games (McMahan et al., 2003) . The idea is to first create a restricted sub-game in which all players are only allowed to play a restricted number of strategies, which are then expanded by adding incorporating each of the players' best-responses to opponents; the sub-game will be replayed with agents' augmented strategy pools before a new round of best responses is found. The worse-case scenario of introducing oracles would be to solve the original evaluation problem in full size. The best response is assumed to be given by an oracle that can be simply implemented by a grid search. Precisely, given the top-rank profile π at iteration k, the goal for agent i is to select 4 the optimal π * i from the pre-defined strategy pool S i to maximize the reward with x [k] h denoting the state, u −i,h ) denoting the actions from agent i and the opponents, respectively. The heuristic of solving the full game from restricted sub-games is crucial especially when it is prohibitively expensive to list all joint-strategy profiles, e.g., in scenarios involving tens-of-millions of joint profiles. For a complete exposition, we summarize the pseudo-code in Algorithm 1. In the first phase, vanilla α α -Rank is executed (lines 4-9), while in the second (lines 11 -13), α α -Rank with Oracle (if turned on) is computed. To avoid any confusion, we refer to the latter as α α -Oracle. Note that even though in the two-player zero-sum games, the oracle algorithm (McMahan et al., 2003) is guaranteed to converge to the minimax equilibrium. Providing valid convergence guarantees for α α -Oracle is an interesting direction for future work. In this paper, we rather demonstrate the effectiveness of such an approach in a large-scale empirical study as shown in Section 4. In this paper, we demonstrated that the approach in exhibits exponential time and memory complexities. We then proposed α α -Rank as a scalable solution for multi-agent evaluation with linear time and memory demands. In a set of experiments, we demonstrated that our method is truly scalable capable of handling large strategy spaces. There are a lot of interesting avenues for future research. First, we plan to theoretically analyze convergence properties of the resulting oracle algorithm, and further introduce policy learning through oracles. Second, we plan take our method to the real-world by conducting multi-robot experiments. joint and transition probability matrix T [k] . The second-smallest eigenvalue of the normalized Laplacian of the graph associated with the Markov chain is given by: , with s i denoting the number of strategies of agent i. Proof : For simplicity we drop round index k in the below derivation. Notice, the underlying graph for the constructed Markov Chain can be represented as a Cartesian product of N complete graphs Indeed, two vertices π [k] ,π [k] ∈ G are connected by the edge if and if only these joint strategy profiles differ in at most one individual strategy, i.e ∃!i ∈ {1, . . . , N } : −i }.Hence , the spectral properties of G can be described in terms of spectral properties of K si as follows (Barik et al., 2015) : ) is the i th eigenvalue of the unnormalized Laplacian of the complete graph K sj and ϑ i,j is the corresponding eigenvector 7 . The spectrum of unnormalized Laplacian of the complete graph K si is given by Spectr(K si ) = {0, s i − 1} and the only eigenvector corresponding to zero eigenvalue is 1 ∈ R si . Therefore, the minimum non-zero eigenvalue of unnormalized Laplacian of G is given by min i s i − 1. Finally, due to the fact that G is a regular graph (with degree of each node is equal to N i=1 s i − N + 1), the smallest non-zero eigenvalue of the normalized Laplacian of G is given by Giving this result, the overall time complexity of Power Method is bounded by O n × log = O (log n). As for the memory complexity, Power Method requires has the same requirements as PageRank algorithm. 8 These results imply that Power Method scales exponentially with number of agents N , and therefore, inapplicable when N is large.
We provide a scalable solution to multi-agent evaluation with linear rate complexity in both time and memory in terms of number of agents
{"src": "scitldr-AIC_train", "paper_id": "Hkg_8xBYDS"}