# Estimating α-Rank by Maximizing Information Gain

arXiv: https://arxiv.org/abs/2101.09178 · HTML: https://mlsanity.com/paper/2101.09178/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 34 references that are in the map.
- First posted on arXiv 22 Jan 2021.

## Builds on (most cited first, 9 of 9)

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [A Generalized Training Approach for Multiagent Learning](https://mlsanity.com/paper/1909.12823/) (2019)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [Re-evaluating Evaluation](https://mlsanity.com/paper/1806.02643/) (2018)
- [Multiagent Evaluation under Incomplete Information](https://mlsanity.com/paper/1909.09849/) (2019)
- [αα-Rank: Practically Scaling α-Rank through Stochastic Optimisation](https://mlsanity.com/paper/1909.11628/) (2019)

## Built on by (most cited first, 4 of 4)

- [On the Limitations of Elo: Real-World Games, are Transitive, not Additive](https://mlsanity.com/paper/2206.12301/) (2022)
- [Game Theoretic Rating in N-player general-sum games with Equilibria](https://mlsanity.com/paper/2210.02205/) (2022)
- [Learning to Identify Top Elo Ratings: A Dueling Bandits Approach](https://mlsanity.com/paper/2201.04480/) (2022)
- [Efficient Nash Equilibrium Computation for Cybersecurity Games](https://mlsanity.com/paper/2609.19399/) (2026)

## Abstract (arXiv)

Game theory has been increasingly applied in settings where the game is not known outright, but has to be estimated by sampling. For example, meta-games that arise in multi-agent evaluation can only be accessed by running a succession of expensive experiments that may involve simultaneous deployment of several agents. In this paper, we focus on α-rank, a popular game-theoretic solution concept designed to perform well in such scenarios. We aim to estimate the α-rank of the game using as few samples as possible. Our algorithm maximizes information gain between an epistemic belief over the α-ranks and the observed payoff. This approach has two main benefits. First, it allows us to focus our sampling on the entries that matter the most for identifying the α-rank. Second, the Bayesian formulation provides a facility to build in modeling assumptions by using a prior over game payoffs. We show the benefits of using information gain as compared to the confidence interval criterion of ResponseGraphUCB (Rowland et al. 2019), and provide theoretical results justifying our method.