Yan, Xue;
Du, Yali;
Ru, Binxin;
Wang, Jun;
Zhang, Haifeng;
Chen, Xu;
(2022)
Learning to Identify Top Elo Ratings: A Dueling Bandits Approach.
In:
Proceedings of the AAAI Conference on Artificial Intelligence.
(pp. pp. 8797-8805).
AAAI: Online.
Preview |
Text
2201.04480.pdf - Other Download (6MB) | Preview |
Abstract
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 Õ(√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.
| Type: | Proceedings paper |
|---|---|
| Title: | Learning to Identify Top Elo Ratings: A Dueling Bandits Approach |
| Event: | Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22) |
| Location: | ELECTR NETWORK |
| Dates: | 22 Feb 2022 - 1 Mar 2022 |
| ISBN: | 1577358767 |
| ISBN-13: | 9781577358763 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1609/aaai.v36i8.20860 |
| Publisher version: | https://doi.org/10.1609/aaai.v36i8.20860 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Machine Learning (ML), Multiagent Systems (MAS) |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10173721 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
