Du, Yali;
Yan, Xue;
Chen, Xu;
Wang, Jun;
Zhang, Haifeng;
(2021)
Estimating α-Rank from A Few Entries with Low Rank Matrix Completion.
In: Meila, Marina and Zhang, Tong, (eds.)
Proceedings of the 38th International Conference on Machine Learning.
Proceedings of Machine Learning Research (PMLR): Virtual conference.
Preview |
Text
du21e.pdf - Published Version Download (2MB) | Preview |
Abstract
Multi-agent evaluation aims at the assessment of an agent's strategy on the basis of interaction with others. Typically, existing methods such as α-rank and its approximation still require to exhaustively compare all pairs of joint strategies for an accurate ranking, which in practice is computationally expensive. In this paper, we aim to reduce the number of pairwise comparisons in recovering a satisfying ranking for n strategies in two-player meta-games, by exploring the fact that agents with similar skills may achieve similar payoffs against others. Two situations are considered: the first one is when we can obtain the true payoffs; the other one is when we can only access noisy payoff. Based on these formulations, we leverage low-rank matrix completion and design two novel algorithms for noise-free and noisy evaluations respectively. For both of these settings, we theorize that O(nr log n) (n is the number of agents and r is the rank of the payoff matrix) payoff entries are required to achieve sufficiently well strategy evaluation performance. Empirical results on evaluating the strategies in three synthetic games and twelve real world games demonstrate that strategy evaluation from a few entries can lead to comparable performance to algorithms with full knowledge of the payoff matrix.
| Type: | Proceedings paper |
|---|---|
| Title: | Estimating α-Rank from A Few Entries with Low Rank Matrix Completion |
| Event: | International Conference on Machine Learning (ICML) 2021 |
| Location: | ELECTR NETWORK |
| Dates: | 18 Jul 2021 - 24 Jul 2021 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://proceedings.mlr.press/v139/du21e.html |
| Language: | English |
| Additional information: | This is an Open Access paper published under a Creative Commons Attribution 4.0 International (CC BY 4.0) Licence (https://creativecommons.org/licenses/by/4.0/). |
| 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/10174057 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
