# Learning to Identify Top Elo Ratings: A Dueling Bandits Approach

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 12 Jan 2022.

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

- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Real World Games Look Like Spinning Tops](https://mlsanity.com/paper/2004.09468/) (2020)
- [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)
- [Provably Optimal Algorithms for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/1703.00048/) (2017)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling](https://mlsanity.com/paper/2006.04012/) (2020)
- [Multiagent Evaluation under Incomplete Information](https://mlsanity.com/paper/1909.09849/) (2019)
- [Giraffe: Using Deep Reinforcement Learning to Play Chess](https://mlsanity.com/paper/1509.01549/) (2015)
- [αα-Rank: Practically Scaling α-Rank through Stochastic Optimisation](https://mlsanity.com/paper/1909.11628/) (2019)
- [Estimating α-Rank by Maximizing Information Gain](https://mlsanity.com/paper/2101.09178/) (2021)
- [Regret Minimization in Stochastic Contextual Dueling Bandits](https://mlsanity.com/paper/2002.08583/) (2020)

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

- [On the Limitations of Elo: Real-World Games, are Transitive, not Additive](https://mlsanity.com/paper/2206.12301/) (2022)
- [An Analysis of Elo Rating Systems via Markov Chains](https://mlsanity.com/paper/2406.05869/) (2024)

## Abstract (arXiv)

The Elo rating system is widely adopted to evaluate the skills of (chess) game and sports players. Recently it has been also integrated into machine learning algorithms in evaluating the performance of computerised AI agents. However, an accurate estimation of the Elo rating (for the top players) often requires many rounds of competitions, which can be expensive to carry out. In this paper, to improve the sample efficiency of the Elo evaluation (for top players), we propose an efficient online match scheduling algorithm. Specifically, we identify and match the top players through a dueling bandits framework and tailor the bandit algorithm to the gradient-based update of Elo. We show that it reduces the per-step memory and time complexity to constant, compared to the traditional likelihood maximization approaches requiring O(t) time. Our algorithm has a regret guarantee of tildeO(√T), sublinear in the number of competition rounds and has been extended to the multidimensional Elo ratings for handling intransitive games. We empirically demonstrate that our method achieves superior convergence speed and time efficiency on a variety of gaming tasks.