# Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning

arXiv: https://arxiv.org/abs/2302.00797 · HTML: https://mlsanity.com/paper/2302.00797/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 102 references that are in the map.
- First posted on arXiv 1 Feb 2023.

## Builds on (most cited first, 30 of 32)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Deal or No Deal? End-to-End Learning for Negotiation Dialogues](https://mlsanity.com/paper/1706.05125/) (2017)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Deep Reinforcement Learning from Self-Play in Imperfect-Information Games](https://mlsanity.com/paper/1603.01121/) (2016)
- [Collaborating with Humans without Human Data](https://mlsanity.com/paper/2110.08176/) (2021)
- [Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems](https://mlsanity.com/paper/1709.08071/) (2017)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Approximately Solving Mean Field Games via Entropy-Regularized Deep Reinforcement Learning](https://mlsanity.com/paper/2102.01585/) (2021)
- [Emergent Communication through Negotiation](https://mlsanity.com/paper/1804.03980/) (2018)
- [A Generalized Training Approach for Multiagent Learning](https://mlsanity.com/paper/1909.12823/) (2019)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [Re-evaluating Evaluation](https://mlsanity.com/paper/1806.02643/) (2018)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [Actor-Critic Policy Optimization in Partially Observable Multiagent Environments](https://mlsanity.com/paper/1810.09026/) (2018)
- [Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent](https://mlsanity.com/paper/1903.05614/) (2019)
- [Adversarial Policies Beat Superhuman Go AIs](https://mlsanity.com/paper/2211.00241/) (2022)
- [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019)
- [Belief and Truth in Hypothesised Behaviours](https://mlsanity.com/paper/1507.07688/) (2015)
- [Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers](https://mlsanity.com/paper/2106.09435/) (2021)
- [Deep Reinforcement Learning for Green Security Games with Real-Time Information](https://mlsanity.com/paper/1811.02483/) (2018)
- [Nash Convergence of Gradient Dynamics in Iterated General-Sum Games](https://mlsanity.com/paper/1301.3892/) (2013)
- [Solving Common-Payoff Games with Approximate Policy Iteration](https://mlsanity.com/paper/2101.04237/) (2021)
- [Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent](https://mlsanity.com/paper/2106.01285/) (2021)
- [Evaluating Strategy Exploration in Empirical Game-Theoretic Analysis](https://mlsanity.com/paper/2105.10423/) (2021)
- [Targeted Data Acquisition for Evolving Negotiation Agents](https://mlsanity.com/paper/2106.07728/) (2021)

## Built on by (most cited first, 6 of 6)

- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [Deep Reinforcement Learning for Autonomous Cyber Defence: A Survey](https://mlsanity.com/paper/2310.07745/) (2023)
- [Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2402.19420/) (2024)
- [A Fairness-Driven Method for Learning Human-Compatible Negotiation Strategies](https://mlsanity.com/paper/2409.18335/) (2024)
- [Combining a Meta-Policy and Monte-Carlo Planning for Scalable Type-Based Reasoning in Partially Observable Environments](https://mlsanity.com/paper/2306.06067/) (2023)
- [Global Policy-Space Response Oracles for Two-Player Zero-Sum Games](https://mlsanity.com/paper/2605.28273/) (2026)

## Abstract (arXiv)

Opponent modeling methods typically involve two crucial steps: building a belief distribution over opponents' strategies, and exploiting this opponent model by playing a best response. However, existing approaches typically require domain-specific heurstics to come up with such a model, and algorithms for approximating best responses are hard to scale in large, imperfect information domains. In this work, we introduce a scalable and generic multiagent training regime for opponent modeling using deep game-theoretic reinforcement learning. We first propose Generative Best Respoonse (GenBR), a best response algorithm based on Monte-Carlo Tree Search (MCTS) with a learned deep generative model that samples world states during planning. This new method scales to large imperfect information domains and can be plug and play in a variety of multiagent algorithms. We use this new method under the framework of Policy Space Response Oracles (PSRO), to automate the generation of an offline opponent model via iterative game-theoretic reasoning and population-based training. We propose using solution concepts based on bargaining theory to build up an opponent mixture, which we find identifying profiles that are near the Pareto frontier. Then GenBR keeps updating an online opponent model and reacts against it during gameplay. We conduct behavioral studies where human participants negotiate with our agents in Deal-or-No-Deal, a class of bilateral bargaining games. 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 and Nash bargaining score negotiating with humans as humans trading among themselves.