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.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as JSONCSVXML

Archive Staff Only

View Item