Timezone: »

R2-B2: Recursive Reasoning-Based Bayesian Optimization for No-Regret Learning in Games
Zhongxiang Dai · Yizhou Chen · Bryan Kian Hsiang Low · Patrick Jaillet · Teck-Hua Ho

Thu Jul 16 07:00 AM -- 07:45 AM & Thu Jul 16 07:00 PM -- 07:45 PM (PDT) @ Virtual #None

This paper presents a recursive reasoning formalism of Bayesian optimization (BO) to model the reasoning process in the interactions between boundedly rational, self-interested agents with unknown, complex, and costly-to-evaluate payoff functions in repeated games, which we call Recursive Reasoning-Based BO (R2-B2). Our R2-B2 algorithm is general in that it does not constrain the relationship among the payoff functions of different agents and can thus be applied to various types of games such as constant-sum, general-sum, and common-payoff games. We prove that by reasoning at level 2 or more and at one level higher than the other agents, our R2-B2 agent can achieve faster asymptotic convergence to no regret than that without utilizing recursive reasoning. We also propose a computationally cheaper variant of R2-B2 called R2-B2-Lite at the expense of a weaker convergence guarantee. The performance and generality of our R2-B2 algorithm are empirically demonstrated using synthetic games, adversarial machine learning, and multi-agent reinforcement learning.

Author Information

Zhongxiang Dai (National University of Singapore)
Yizhou Chen (National University of Singapore)
Bryan Kian Hsiang Low (National University of Singapore)

Dr. Bryan Low is an Associate Professor of Computer Science at the National University of Singapore and the Deputy Director of AI Research at AI Singapore. He obtained the B.Sc. (Hons.) and M.Sc. degrees in Computer Science from National University of Singapore, Singapore, in 2001 and 2002, respectively, and the Ph.D. degree in Electrical and Computer Engineering from Carnegie Mellon University, Pittsburgh, Pennsylvania, in 2009. His research interests include probabilistic & automated machine learning, planning under uncertainty, and multi-agent/robot systems. Dr. Low is the recipient of the (1) Andrew P. Sage Best Transactions Paper Award for the best paper published in all 3 of the IEEE Transactions on Systems, Man, and Cybernetics - Parts A, B, and C in 2006; (2) National University of Singapore Overseas Graduate Scholarship for Ph.D. studies in Carnegie Mellon University (CMU) in 2004-2009; (3) Singapore Computer Society Prize for Best M.Sc. Thesis in School of Computing, National University of Singapore in 2003; and (4) Faculty Teaching Excellence Award in School of Computing, National University of Singapore in 2017-2018. Dr. Low has served as a World Economic Forum’s Global Future Councils Fellow for the Council on the Future of Artificial Intelligence and Robotics from Sep 2016 to Jun 2018 and an IEEE Robotics & Automation Society (RAS) Distinguished Lecturer for the IEEE RAS Technical Committee on Multi-Robot Systems in Mar 2019. He has served as an organizing chair for the IEEE RAS Summer School on Multi-Robot Systems in Jun 2016 and the AI Summer Schools in Jul 2019 and Aug 2020. Dr. Low has also served as associate editors, area chairs and program committee members, and reviewers for premier AI (specifically, multiagent systems, AI planning, robotics, machine learning) conferences: IJCAI, AAAI, ECAI, AAMAS, ICAPS, RSS, IROS, ICRA, CoRL, NeurIPS, ICML, AISTATS, ICLR and journals: TKDE, JMLR, JAIR, MLJ, TNNLS, T-ASE, IJRR, T-RO, AURO, JFR, TOSN, JAAMAS. He was the top 5% reviewer for ICML 2019 and top 33% reviewer for ICML 2020.

Patrick Jaillet (MIT)
Teck-Hua Ho (National University of Singapore)

More from the Same Authors