Timezone: »
Spotlight
Estimating $\alpha$-Rank from A Few Entries with Low Rank Matrix Completion
Yali Du · Xue Yan · Xu Chen · Jun Wang · Haifeng Zhang
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.
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)
-
2021 Poster: Estimating $\alpha$-Rank from A Few Entries with Low Rank Matrix Completion »
Wed. Jul 21st 04:00 -- 06:00 PM Room Virtual
More from the Same Authors
-
2022 Poster: Understanding Policy Gradient Algorithms: A Sensitivity-Based Approach »
Shuang Wu · Ling Shi · Jun Wang · Guangjian Tian -
2022 Poster: Plan Your Target and Learn Your Skills: Transferable State-Only Imitation Learning via Decoupled Policy Optimization »
Minghuan Liu · Zhengbang Zhu · Yuzheng Zhuang · Weinan Zhang · Jianye Hao · Yong Yu · Jun Wang -
2022 Spotlight: Understanding Policy Gradient Algorithms: A Sensitivity-Based Approach »
Shuang Wu · Ling Shi · Jun Wang · Guangjian Tian -
2022 Spotlight: Plan Your Target and Learn Your Skills: Transferable State-Only Imitation Learning via Decoupled Policy Optimization »
Minghuan Liu · Zhengbang Zhu · Yuzheng Zhuang · Weinan Zhang · Jianye Hao · Yong Yu · Jun Wang -
2021 Poster: Learning in Nonzero-Sum Stochastic Games with Potentials »
David Mguni · Yutong Wu · Yali Du · Yaodong Yang · Ziyi Wang · Minne Li · Ying Wen · Joel Jennings · Jun Wang -
2021 Poster: Modelling Behavioural Diversity for Learning in Open-Ended Games »
Nicolas Perez-Nieves · Yaodong Yang · Oliver Slumbers · David Mguni · Ying Wen · Jun Wang -
2021 Spotlight: Learning in Nonzero-Sum Stochastic Games with Potentials »
David Mguni · Yutong Wu · Yali Du · Yaodong Yang · Ziyi Wang · Minne Li · Ying Wen · Joel Jennings · Jun Wang -
2021 Oral: Modelling Behavioural Diversity for Learning in Open-Ended Games »
Nicolas Perez-Nieves · Yaodong Yang · Oliver Slumbers · David Mguni · Ying Wen · Jun Wang -
2020 Poster: Multi-Agent Determinantal Q-Learning »
Yaodong Yang · Ying Wen · Jun Wang · Liheng Chen · Kun Shao · David Mguni · Weinan Zhang -
2019 Poster: Grid-Wise Control for Multi-Agent Reinforcement Learning in Video Game AI »
Lei Han · Peng Sun · Yali Du · Jiechao Xiong · Qing Wang · Xinghai Sun · Han Liu · Tong Zhang -
2019 Poster: BayesNAS: A Bayesian Approach for Neural Architecture Search »
Hongpeng Zhou · Minghao Yang · Jun Wang · Wei Pan -
2019 Oral: BayesNAS: A Bayesian Approach for Neural Architecture Search »
Hongpeng Zhou · Minghao Yang · Jun Wang · Wei Pan -
2019 Oral: Grid-Wise Control for Multi-Agent Reinforcement Learning in Video Game AI »
Lei Han · Peng Sun · Yali Du · Jiechao Xiong · Qing Wang · Xinghai Sun · Han Liu · Tong Zhang -
2018 Poster: Mean Field Multi-Agent Reinforcement Learning »
Yaodong Yang · Rui Luo · Minne Li · Ming Zhou · Weinan Zhang · Jun Wang -
2018 Oral: Mean Field Multi-Agent Reinforcement Learning »
Yaodong Yang · Rui Luo · Minne Li · Ming Zhou · Weinan Zhang · Jun Wang