Timezone: »

 
Spotlight
Estimating $\alpha$-Rank from A Few Entries with Low Rank Matrix Completion
Yali Du · Xue Yan · Xu Chen · Jun Wang · Haifeng Zhang

Wed Jul 21 05:30 AM -- 05:35 AM (PDT) @
in Learning Theory 3 »
Multi-agent evaluation aims at the assessment of an agent's strategy on the basis of interaction with others. Typically, existing methods such as $\alpha$-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.
Keywords: Optimization · Algorithms · Distributed Inference · Algorithms Evaluation

Author Information

Yali Du (University College London)

Yali Du is a 3rd year PhD student with her research focusing on matrix completion and its applications on recommender systems, multi-label learning and social analysis. She has the enthusiasm to communicate with other researchers and learn from them. She has published two full-length papers on IJCAI 2017.

Xue Yan (Institute of Automation, Chinese Academy of Sciences)
Xu Chen (Renmin University of China)
Jun Wang (UCL)
Haifeng Zhang (Institute of Automation, Chinese Academy of Sciences)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors