Search-Improved Game-Theoretic Multiagent Reinforcement Learning in General and Negotiation Games
Authors: 
Zun Li, Marc Lanctot, Kevin R. McKee, Luke Marris, Ian Gemp, Daniel Hennes, Kate Larson, Yoram Bachrach, 
Michael P. Wellman, Paul MullerAuthors Info & Claims
Pages 2445 - 2447
Abstract
Multiagent reinforcement learning (MARL) has benefited significantly from population-based and game-theoretic training regimes. One approach, Policy-Space Response Oracles (PSRO), employs standard reinforcement learning to compute response policies via approximate best responses and combines them via meta-strategy selection. We augment PSRO by adding a novel search procedure with generative sampling of world states, and introduce two new meta-strategy solvers based on the Nash bargaining solution. We evaluate PSRO's ability to compute approximate Nash equilibrium, and its performance in negotiation games: Colored Trails and Deal-or-no-Deal. We conduct behavioral studies where human participants negotiate with our agents (N = 346). Search with generative modeling finds stronger policies during both training time and test time, enables online Bayesian co-player prediction, and can produce agents that achieve comparable social welfare negotiating with humans as humans trading among themselves.
References
[1]
Kris Cao, Angeliki Lazaridou, Marc Lanctot, Joel Z. Leibo, Karl Tuyls, and Stephen Clark. 2018. Emergent communication through negotiation. In Sixth International Conference on Learning Representations.
[2]
Peter I. Cowling, Edward J. Powley, and Daniel Whitehouse. 2012. Information set Monte Carlo tree search. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 4 (2012), 120--143. Issue 2.
[3]
David DeVault, Johnathan Mell, and Jonathan Gratch. 2015. Toward natural turn-taking in a virtual human negotiation agent. In AAAI Spring Symposium on Turn-taking and Coordination in Human-Machine Interaction.
[4]
E. Fehr and K. Schmidt. 1999. A theory of fairness, competition and cooperation. Quarterly Journal of Economics, Vol. 114 (1999), 817--868.
[5]
Christopher Griffin. 2010. Quadratic programs and general-sum games. In Game Theory: Penn State Math 486 Lecture Notes. 138--144. https://docs.ufpr.br/volmir/Math486.pdf.
[6]
John C Harsanyi and Reinhard Selten. 1972. A generalized Nash solution for two-person bargaining games with incomplete information. Management science, Vol. 18 (1972), 80--106.
[7]
Johannes Heinrich, Marc Lanctot, and David Silver. 2015. Fictitious self-play in extensive-form games. In Thirty-Second International Conference on Machine Learning.
[8]
Johannes Heinrich and David Silver. 2016. Deep reinforcement learning from self-play in imperfect-information games. CoRR, Vol. abs/1603.01121 (2016).
[9]
Minae Kwon, Siddharth Karamcheti, Mariano-Florentino Cuellar, and Dorsa Sadigh. 2021. Targeted data acquisition for evolving negotiation agents. In Thirty-Eighth International Conference on Machine Learning, Vol. 139. 5894--5904.
[10]
Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, and Thore Graepel. 2017. A unified game-theoretic approach to multiagent reinforcement learning. In Thirtieth International Conference on Neural Information Processing Systems.
[11]
Mike Lewis, Denis Yarats, Yann N. Dauphin, Devi Parikh, and Dhruv Batra. 2017. Deal or no deal End-to-end learning for negotiation dialogues. In 2017 Conference on Empirical Methods in Natural Language Processing.
[12]
Zun Li, Marc Lanctot, Kevin R. McKee, Luke Marris, Ian Gemp, Daniel Hennes, Paul Muller, Kate Larson, Yoram Bachrach, and Michael P. Wellman. 2023. Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning. https://doi.org/10.48550/ARXIV.2302.00797
[13]
Luke Marris, Paul Muller, Marc Lanctot, Karl Tuyls, and Thore Graepel. 2021. Multi-agent training beyond zero-sum with correlated equilibrium meta-solvers. In Twenty-Eighth International Conference on Machine Learning.
[14]
Peter Morris. 2012. Introduction to game theory. Springer Science & Business Media.
[15]
Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls, Julien Pé rolat, Siqi Liu, Daniel Hennes, Luke Marris, Marc Lanctot, Edward Hughes, Zhe Wang, Guy Lever, Nicolas Heess, Thore Graepel, and Ré mi Munos. 2019. A generalized training approach for multiagent learning. In Eighth International Conference on Learning Representations.
[16]
John Nash. 1950. The bargaining problem. Econometrica, Vol. 18, 2 (1950), 155--162.
[17]
Eyal Peer, Laura Brandimarte, Sonam Samat, and Alessandro Acquisti. 2017. Beyond the Turk: Alternative platforms for crowdsourcing behavioral research. Journal of Experimental Social Psychology, Vol. 70 (2017), 153--163.
[18]
Eyal Pe'er, David Rothschild, Andrew Gordon, Zak Evernden, and Ekaterina Damer. 2021. Data quality of platforms and panels for online behavioral research. Behavior Research Methods (2021), 1--20.
[19]
DJ Strouse, Kevin McKee, Matt Botvinick, Edward Hughes, and Richard Everett. 2021. Collaborating with Humans without Human Data. In Thirty-Fifth Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. 14502--14515.
[20]
Finbarr Timbers, Nolan Bard, Edward Lockhart, Marc Lanctot, Martin Schmid, Neil Burch, Julian Schrittwieser, Thomas Hubert, and Michael Bowling. 2022. Approximate exploitability: Learning a best response in large games. In Thirty-First International Conference on Artificial Intelligence.
[21]
Michael P. Wellman. 2006. Methods for empirical game-theoretic analysis. In Twenty-First National Conference on Artificial Intelligence.
Index Terms
- Search-Improved Game-Theoretic Multiagent Reinforcement Learning in General and Negotiation Games
Recommendations
Bilateral Multi-issue Parallel Negotiation Model Based on Reinforcement Learning
IDEAL 2013: Proceedings of the 14th International Conference on Intelligent Data Engineering and Automated Learning --- IDEAL 2013 - Volume 8206This paper proposes a bilateral multi-issue parallel negotiation model based on reinforcement learning. Considering the equality of both sides and that both negotiators refuse to give more information for their own interests, it introduces a mediator ...
Coordination in multiagent reinforcement learning: a Bayesian approach
AAMAS '03: Proceedings of the second international joint conference on Autonomous agents and multiagent systemsMuch emphasis in multiagent reinforcement learning (MARL) research is placed on ensuring that MARL algorithms (eventually) converge to desirable equilibria. As in standard reinforcement learning, convergence generally requires sufficient exploration of ...
Generalized reinforcement learning in perfect-information games
AbstractThis paper studies reinforcement learning in which players base their action choice on valuations they have for the actions. We identify two general conditions on valuation updating rules that together guarantee that the probability of playing a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2023
3131 pages
ISBN:9781450394321
- General Chairs:
- Noa Agmon,
- Bo An,
- Program Chairs:
- Alessandro Ricci,
- William Yeoh
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 30 May 2023
Check for updates
Author Tags
Qualifiers
- Poster
Conference
AAMAS '23
Sponsor:
AAMAS '23: International Conference on Autonomous Agents and Multiagent Systems
May 29 - June 2, 2023
London, United Kingdom
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 56Total Downloads
- Downloads (Last 12 months)25
- Downloads (Last 6 weeks)2
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in