Combining Deep Reinforcement Learning and Search with Generative Models for Game-Theoretic Opponent Modeling

1 Introduction

A central challenge for agent designers is how to build agents that can be well-adapted to unknown opponents in a dynamic multiagent environment. Opponent modeling methods [Al- However, most of these approaches use domain-specific heurstics to handcraft an opponent model. Such knowledge is typically encoded in certain interpretations of game rules or experiences reflected by human plays. These techniques are hard to transfer to domains where relevant data are missing. Meanwhile, even if an opponent model is present, there is no existing best response method that work well in large imperfect information games where computing a posterior distribution over world state is intractable.

In this work, we propose a general-purpose training regime using multiagent reinforcement learning to address the above issues. We adopt extensive-form games (EFG) as a generic formulation for multiagent environments for our algorithmic developments, as opposed to a domain-specific ruleset. We propose Generative Best Response (GenBR), a best response method that extends AlphaZero-style RL and MCTS methods to large general-sum, imperfect information games. GenBR enhances best response strength by leveraging test-time computation and an approximate world model learned by deep neural nets. While GenBR can be plug and play in a variety of multiagent training algorithms, we focus on Policy Space Response Oracles (PSRO) [Lanctot et al., 2017] as our training loop for offline opponent modeling. Our agent thereafter at test-time employs GenBR for both planning and updating an online opponent model via Bayesian learning.

Contributions. We provide three significant contributions. First, we propose enhanced version of AlphaZero-style MCTS to train a best response strategy, thereby equipping our agent with the capability to both plan and infer the environmental state as well as opponents' strategic choices during online decision-making. This novel search method integrates deep RL with Information Set MCTS (IS-MCTS). To handle large imperfect information, we augment the policyand-value network (PVN) in AlphaZero with a generative model that samples world states at the root of the search tree. This results in a novel policy-value-and-generative network (PVGN), which iteratively refines its quality using RL trajec-

…

Figure 1: Example negotiation game in extensive-form. In "Deal or No Deal", the game starts at the empty history (H), chance samples a public pool of resources and private preferences (with some conditions; see Section 5.1) for three different items (books, hats, and basketballs). Then, players alternate proposals for how to split the resources. Rewards are defined by a dot product between received resources and preferences.

tory data during the training loop.

Second, we introduce several novel meta-strategy solvers in the PSRO framework based on the Nash bargaining solution [Nash, 1950]. Lastly, we show an empirical evaluation of several RL agents trained by the combined algorithm against humans in a negotiation game, finding the best ones to be as efficient as humans trading with other humans.

2 Preliminaries

An N-player normal-form game consists of a set of players N " t1, 2, . . . ,Nu, N finite pure strategy sets Πi (one per player) with a joint strategy set Π " Π1 ˆ Π2 ˆ ¨ ¨ ¨ΠN, and a utility tensor (one per player), ui : Π Ñ R, and we denote player i's utility as uipπq. Two-player (2P) normalform games are called matrix games. A two-player zero-sum (purely adversarial) game is such that, N " 2 and for all joint strategies π P Π : řiPN uipπq " 0, whereas a commonpayoff (purely cooperative) game: @π P Π, @i, j P N : uipπq " ujpπq. A general-sum game is one without any restrictions on the utilities. A mixed strategy for player i is a probability distribution over Πi denoted σi P ∆pΠiq, and a strategy profile σ " σ1 ˆ ¨ ¨ ¨ ˆ σN , and for convenience we denote uipσq " Eπ"σruipπqs. By convention, ´i refers to player i's opponents. A best response is a strategy bipσ´iq P BRpσ´iq Ď ∆pΠiq, that maximizes the utility against a specific opponent strategy: for example, σ1 " b1pσ´1q is a best response to σ´1 if u1pσ1, σ´1q " maxσ11 u1pσ11 , σ´1q. An approximate ϵ-Nash equilibrium is a profile σ such that for all i P N , uipbipσ´iq, σ´iq ´ uipσq ď ϵ, with ϵ " 0 corresponding to an exact Nash equilibrium.

In an extensive-form game, play takes place over a sequence of actions a P A. Examples of such games include chess, Go, and poker. A history h P H is a sequence of actions from the start of the game taken by all players. Legal actions are at h are denoted Aphq and the player to act at h as τphq. Players only partially observe the state and hence have imperfect information. There is a special player called chance that plays with a fixed stochastic policy (selecting outcomes that represent dice rolls or private preferences). Policies πi (also called behavioral strategies) is a collection of distributions over legal actions, one for each player's information state, s P Si, which is a set of histories consistent with what the player knows at decision point s (e.g.all the possible private preferences of other players), and πipsq P ∆pApsqq. An illustrative example of interaction in an extensive-form game is "Deal or No Deal" shown in Figure 1.

There is a subset of the histories Z Ă H called terminal histories, and utilities are defined over terminal histories, e.g. uipzq for z P Z could be -1 or 1 in Go (representing a loss and a win for player i, respectively). As before, expected utilities of a joint profile π " π1ˆ¨ ¨ ¨ˆπN is defined as an expectation over the terminal histories, uipπq " Ez"πruipzqs, and best response and Nash equilibria are defined with respect to a player's full policy space.

2.1 CombiningMCTS and RL for Best Response

Computing approximate best responses is critical in a variety of multiagent training algorithms. There have been many previous works that consider enhancing best response strength via deep RL and game-tree search. For example, the original PSRO algorithm [Lanctot et al., 2017] proposed using deep RL in place of value iteration in the double-oracle framework [McMahan et al., 2003] which scales game solving in environments with large state spaces. Approximate Best Response (ABR) [Timbers et al., 2022; Wang et al., 2023] uses MCTS as a best response method which identifies weakness in human-level Go playing agents. However, they only focus on domain where a posterior world belief can be computed exactly. Another relevant work is Best Response Expert Iteration (BRExIT) [Hernandez et al., 2023], which uses MCTS to exploit an opponent mixture trained with an auxiliary loss. However, they only concern perfect information games.

In general, using deep RL+MCTS as a best response method leverages both generalization capability of neural nets and test-time computation by the search method. We elaborate this by explaining how ABR algorithm works. When computing an approximate best response in imperfect information games, ABR uses a variant of Information Set Monte Carlo tree search [Cowling et al., 2012] called ISMCTS-BR. At the root of the IS-MCTS-BR search (starting at information set s), the posterior distribution over world states, Prph | s, π´iq is computed explicitly, which requires both (i) enumerating every history in s, and (ii) computing the opponents' reach probabilities for each history in s. Then, during each search round, a world state is sampled from this belief distribution, then the game-tree regions are explored in a similar way as in the vanilla MCTS, and finally the statistics are aggregated on the information-set level. Steps (i) and (ii) are prohibitively expensive in games with large belief spaces.

Algorithm 1 GenBR Training Loop

function GenBR(i, σ, num eps) Initialize value nets v, v1 , policy nets p, p1 , generative nets g, g1 , data buffers Dv, Dp, Dg for eps " 1, . . . , num eps do h Ð initial state. T " tsiphqu Sample opponents π´i " σ´i. while h not terminal do if τphq " chance then Sample chance event a " πc else if τphq ­" i then Sample a " πτphq else a, π Ð Searchpsiphq, σ, v1 , p1 , g1 q Dp Ð Dp Ťtpsiphq, πqu Dg Ð Dg Ťtpsiphq, hqu end if h Ð h.applypaq, T Ð T Ťtsiphqu end while Dv Ð Dv Ťtps, rq | s P T u, where r is the payoff of i in this trajectory v, p, g Ð Updatepv, p, g, Dv , Dp, Dg q Replace parameters of v1 , p1 , g1 by the latest parameters of v, p, g periodically. end for return Searchp¨, σ, v, p, gq end function

Algorithm 2 GenBR Search

function Search(s, σ, v, p, g) for iter " 1, . . . , num sim do T " tu Sample a world state (gen. model): h " gph | sq Sample an opponent profile using Bayes' rule: π1´i " Prpπ´i | h, σ´iq. Replace opponent nodes with chance events according to π1´i while do if h is terminal then r Ð payoff of i. Break else if τphq " chance then a Ð sample according to chance else if siphq not in search tree then Add siphq to search tree. r Ð vpsiphqq else a Ð MaxPUCTpsiphq, pq T Ð T Y tpsiphq, aqu end if h.applypaq end while for ps, aq P T do s.childpaq.visits Ð s.childpaq.visits ` 1 s.childpaq.value Ð s.childpaq.value ` r s.total visits Ð s.total visits `1 end for end for return action a˚ that receives max visits among children of s, and a policy π˚ that represents the visit frequency of children of s end function

3 GenBR: Learning Best Response Search with a Generative Model

We propose Generative Best Response (GenBR), a new best response method based on AlphaZero-styled MCTS with Prph | s, π´iq learned by a deep generative model. On a highlevel, GenBR is parameterized by three deep neural nets: a policy net p, a value net v and a generative net g. Just as in the AlphaZero training loop [Silver et al., 2018], GenBR training loop generates multiple RL trajectories by calling GenBR search procedure at each decision point to gather data for training these neural nets. These neural nets will further guide and refine the search procedure, producing higher quality data for later training. During the search procedure, the world states are sampled directly from the model given only their information state descriptions, leading to a succinct representation of the posterior that generalizes to large state spaces. Next we explain our algorithms in more details.

The GenBR training loop (Algorithm 1) proceeds analogously to AlphaZero's self-play based training, which trains a value net v, a policy net p, along with a generative network g using trajectories generated by search. We assume we are given an offline opponent model σ represented by a mixed strategy profile of the opponents. There are important differences from AlphaZero. Only one player is learning (e.g.player i). The (set of) opponents are fixed, sampled at the start of each episode from the opponent model σ´i. Whenever it is player i's turn to play, since we are considering imperfect information games, it runs a POMDP search procedure based on Algorithm 2 from its current information state si. The search procedure produces a policy target π˚ , and an action choice a˚ that will be taken at si at that episode. Data about the final outcome and policy targets for player i are stored in data sets Dv and Dp, which are used to improve the value net and policy net that guide the search. Data about the history, h, in each information set, sphq, reached is stored in a data set Dg, which is used to train the generative network g by supervised learning. We call the combination of v, p, and g as the policy-value-and-generative network (PVGN).

The GenBR MCTS search used (Algorithm 2) is based on IS-MCTS-BR in [Timbers et al., 2022] (described in Section 2.1) and POMCP [Silver and Veness, 2010]. Here it utilizes value net v to truncate the search at an unexpanded node and policy net p for action selection at an expanded node s using the PUCT [Silver et al., 2018] formula:

MaxPUCTps, pq " argmaxaPApsq s.childpaq.visits ` cuct ¨

s.childpaq.value

pps, aq¨ ?s.total visits s.childpaq.visits`1 , for some constant cuct. Then at the end of the search call, it returns an action a˚ which receives the most visits at the root node, and a policy π˚ representing the action distribution of the search at the root node.

Algorithm 2 has two important differences from previous methods. First, rather than computing exact posteriors, we use the deep generative model g learned in Algorithm 1 to sample world states. As such, this approach may be capable of scaling to large domains where previous approaches such as particle filtering [Somani et al., 2013] fail.

Second, the imperfect information of the underlying POMDP consists of both (i) the actual world state h and (ii)

opponents' pure-strategy commitment π´i. We make use of the fact Prph, π´i | s, σ´iq " Prph | s, σ´iq Prpπ´i | h, σ´iq such that we approximate Prph | s, σ´iq by g and compute Prpπ´i | h, σ´iq exactly via Bayes' rule. Computing Prpπ´i | h, σ´iq can be viewed as a Bayesian learning procedure [Kreps andWilson, 1982; Hernandez-Leal and Kaisers, 2017; Albrecht et al., 2016; Kalai and Lehrer, 1993] that keeps updating an online opponent model Prpπ´i | h, σ´iq. Therefore, our agent is capable of performing test-time search while automatically inferring environmental state as well as opponents' strategies during online decision making.

Algorithm 3 Opponent Modeling via PSRO and GenBR function PSRO(G, MSS) Initialize strategy sets @i, Πi " tπ0 i u, mixed strategies σipπ0 i q " 1, @i, payoff tensor U 0 . for t P t0, 1, 2 ¨ ¨ ¨ , Tu do for i P N do Πi Ð Πi Ť tGenBRpi, σ, num epsqu end for Update missing entries in U t via simulations σ Ð MSSpU t q end for return Π " pΠ1,Π2, ¨ ¨ ¨ ,ΠNq, σ end function

4 Game-Theoretic Opponent Modeling

In this section, we describe our complete training algorithm for opponent modeling. We use Policy Space Response Oracles to obtain an offline opponent model σ´i for training GenBR in Algorithm 1. We first introduce empirical gametheoretic analysis (EGTA) and PSRO, and then propose new solution concepts in PSRO based on bargaining theory, and provide empirical results of our new meta-strategy solvers at the end of this section.

4.1 Empirical Game-Theoretic Analysis and Policy-Space Response Oracles

Empirical game-theoretic analysis (EGTA) [Wellman et al., 2025] is an approach to reasoning about large sequential games through normal-form empirical game models, induced by simulating enumerated subsets of the players' full policies in the sequential game. Policy-Space Response Oracles (PSRO) [Lanctot et al., 2017] uses EGTA to incrementally build up each player's set of policies ("oracles") through repeated applications of approximate best response using RL. Each player's initial set contains a single policy (e.g.uniform random) resulting in a trivial empirical game U 0 containing one cell. On epoch t, given N sets of policies Π t i for i P N , utility tensors for the empirical game U t are estimated via simulation.

A meta-strategy solver (MSS) derives a profile σt , generally mixed, over the empirical game strategy space. A best response oracle, say bti pσt´i q, is then computed for each player i by training against policies sampled from opponent model σt´i , and are added to strategy sets for the next epoch: Π t`1 i " Π t i Y tbti pσt´i qu. Since the opponent policies are fixed, the oracle response step is a single-agent problem [Oliehoek and Amato, 2014]; RL and search can feasibly handle large state and policy spaces. Our full algorithm (Algorithm 3) employs GenBR as the oracle step in PSRO.

PSRO naturally fits our focus of automating opponent modeling as it generates opponent models σ´i through pure game-theoretic reasoning and reinforcement learning. Furthermore, since each strategy (except the first ones) in the pool is a best response against an early-iteration opponent model (which itself consists of best responses), it in fact induces a cognitive hierarchy [Camerer et al., 2004] of rationalizable strategies [Bernheim, 1984]. An important question is choosing which MSS 1 to compute an opponent mixture. Since our primary application domain of interest in this paper is negotiation game, it is natural to consider solution concepts from bargaining theory as MSSs. Next we introduce computational results of new MSSs based on Nash bargaining solution which were not investigated in previous works.

4.2 Empirical Game Nash Bargaining Solution

In contrast to non-cooperative game theory, bargaining theory considers scenarios where players' utilities are not entirely in conflict, and need to negotiate to achieve a possible cooperative outcome. The Nash Bargaining solution (NBS) selects a Pareto-optimal payoff profile that uniquely satisfies axioms specifying desirable properties of invariance, symmetry, and independence of irrelevant alternatives [Nash, 1950; Ponsati and Watson, 1997]. The axiomatic characterization of NBS abstracts away the process by which said outcomes are obtained through strategic interaction.

Define the set of achievable payoffs as all expected utilities uipxq under a joint-policy profile x. Denote the disagreement outcome of player i, which is the payoff it gets if no agreement is achieved, as di. The NBS is the set of policies that maximizes the Nash bargaining score (A.K.A. Nash product):

which, when N " 2, leads to a quadratic program (QP) with the constraints derived from the policy space structure [Griffin, 2010]. However, even in this simplest case of two-player matrix games, the non-concave objective poses a problem for most QP solvers. Furthermore, scaling to N players requires higher-order polynomial solvers.

Instead of using higher-order polynomial solvers, we propose an algorithm based on (projected) gradient ascent [Singh et al., 2000; Boyd and Vandenberghe, 2004]. Note that the Nash product is non-concave, so instead of maximizing it, we maximize the log Nash product gpxq "

ÿ

which has the same maximizers as (1), and is a sum of concave functions, hence concave. The process is depicted in

1 In App. G.1, we conduct extensive experiments over 16 MSSs on 12 different benchmark games on OpenSpiel [Lanctot et al., 2019]. Appendices can be found in [Li et al., 2023].

Algorithm 4 NBS by projected gradient ascent

Input: Initial iterate x, payoff tensor U. function NBS(x0 , U) Let gpxq be the log Nash product defined in eqn (2) for t " 0, 1, 2 ¨ ¨ ¨ , T do yt`1 Ð xt ` αt∇gpxt q xt`1 Ð Projpyt`1 q end for Return argmaxxt"0:T gpxt q end function

Algorithm 4; Proj is the ℓ2 projection onto the simplex. We can prove it has a convergence rate of OpT ´1{2 q. For a proof, see App. C.

Theorem 4.1. Assume any deal is better than no deal by κ ą 0, i.e., uipxq ´ di ě κ ą 0 for all i, x. Let txt u be the sequence generated by Algorithm 4 with starting point x0 " |Π |´11 and step size sequence αt " κ?p|Π |´1q{|Π | umaxN pt` 1q´1{2 . Then, for all t ą 0 one has

where umax " maxi,x uipxq, |Π| is the number of possible pure joint strategies, and x is assumed to be a joint correlation device (µ).

Besides directly using NBS, we also consider (1) using NBS to select a correlated equilibrium (CE) and coarse correlated equilibrium (CCE) as an MSS, which we denote as max-NBS-(C)CE and (2) profile that maximizes social welfare. A comprehensive list of MSSs that we investigated in our experiments is in App. A.

4.3 Empirical Results on Colored Trails

Here we study the performance of our NBS-based MSSs on colored trails, a highly configurable negotiation game played on a grid [Gal et al., 2010] of colored tiles, which has been actively studied by the AI community [Grosz et al., 2004; Ficici et al., 2008]. Colored Trails does not require search since the number of moves is small, so we use classical RL based oracles (DQN and Boltzmann DQN) to isolate the effects of the new meta-strategy solvers.

We use a three-player variant [Ficici et al., 2008] depicted in Figure 2. At the start of each episode, an instance (a board and colored chip allocation per player) is randomly sampled from a database of strategically interesting and balanced configurations [de Jong et al., 2011, Section 5.1]. There are two proposers (P1 and P2) and a responder (R). R can see all players' chips, both P1 and P2 can see R's chips; however, proposers cannot see each other's chips. Each proposer, makes an offer to the receiver. The receiver than decides to accept one offer and trades chips with that player, or passes. Then, players spend chips to get as close to the flag as possible (each chip allows a player to move to an adjacent tile if it is the same color as the chip). For any configuration (player i at position p), define SCOREpp, iq " p´25qd ` 10t, where d is the Manhattan distance between p and the flag, and t is the number of player i's chips. The utility for player i is their gain: score at the end of the game minus the score at the start. We compute the Pareto frontier for a subset of configurations, and define the Pareto Gap (P-Gap) as the minimal ℓ2 distance from the outcomes to the outer surfaces of the convex hull of the Pareto front, which is then averaged over the set of configurations in the database.

Figure 3 shows representative results of PSRO agents with different MSSs on Colored Trails (for full graphs, and evolution of score diagrams, see App. G.2). The best-performing MSS is NBS-joint, beating the next best by a full 3 points. The NBS meta-strategy solvers comprise five of the six best MSSs under this evaluation. An example of the evolution of the expected score over PSRO iterations is also shown, moving toward the Pareto front, though not via a direct path.

5 Experiments

In this section, we report our major results on the Deal-orNo-Deal (DoND) negotiation game.

5.1 Negotiation Game: Deal or No Deal

"Deal or No Deal" (DoND) is a simple alternating-offer bargaining game with incomplete information, which has been used in many AI studies [Lewis et al., 2017; Cao et al., 2018]. Our focus is to train RL agents to play against humans without human data, similar to previous work [Strouse et al., 2021].

An example game of DoND is shown in Figure 1. Two players are assigned private preferences w1 ě 0,w2 ě 0 for three different items (books, hats, and basketballs). At the start of the game, there is a pool c of 5 to 7 items drawn randomly such that: (i) the total value for a player of all items is 10: w1 ¨ c " w2 ¨ c " 10, (ii) each item has non-zero value for at least one player: w1 `w2 ą 0, (iii) some items have non-zero value for both players, w1 dw2 ­" 0, where d represents element-wise multiplication.

The players take turns proposing how to split the pool of items, for up to 10 turns (5 turns each). If an agreement is not reached, the negotiation ends and players both receive 0. Otherwise, the agreement represents a split of the items to each player, o1 ` o2 " c, and player i receives a utility of wi ¨ oi. DoND is an imperfect information game because the other player's preferences are private. We use a database of 6796 bargaining instances made publicly available in [Lewis et al., 2017]. Deal or No Deal is a significantly large game, with an estimated 1.32 ¨ 1013 information states for player 1 and 5.69 ¨ 1011 information states for player 2 (see App. D.2 for details).

5.2 GenerativeWorld State Sampling

We now show that both the search and the generative model contribute to achieving higher reward than RL alone. The input of our deep generative model is one's private values vi and public observations, and the output is a distribution over v´i (detailed in the Appendix). We compute approximate best responses to three opponents: uniform random, a DQN agent trained against uniform random, and a DQN agent trained in self-play. We compare different world state sampling models as well to DQN in Figure 4, where the deep generative model approach is denoted as simple learn.

The benefit of search is clear: the search methods achieve a high value in a few episodes, a level that takes DQN many more episodes to reach (against random and DQN response to random) and a value that is not reached by DQN against the self-play opponent. The best generative models are the true posterior (exact) and the actual underlying world state (cheat). However, the exact posterior is generally intractable and the underlying world state is not accessible to the agent at test-time, so these serve as idealistic upper-bounds. Uniform seems to be a compromise between the bad and ideal models. The deep generative model approach is roughly comparable to uniform at first, but learns to approximate the posterior as well as the ideal models as data is collected. In contrast, DQN eventually reaches the performance of the uniform model against the weaker opponent but not against the stronger opponent even after 20000 episodes.

5.3 Studies with Human Participants

We recruited participants from Prolific [Pe'er et al., 2021; Pe'er et al., 2017] to evaluate the performance of our agents in DoND (overall 346; 41.4% female, 56.9% male, 0.9% trans or nonbinary; median age range: 30-40), following established ethical guidelines for research with human participants [McKee, 2024]. Crucially, participants played DoND for real monetary stakes, with an additional payout for each point earned in the game. Participants first read game instructions and completed a short comprehension test to ensure they understood key aspects of DoND's rules. Participants then played five episodes of DoND with a randomized sequence of opponents. Episodes terminated after players reached a deal, after 10 moves without reaching a deal, or after 120 seconds elapsed. After playing all five episodes, participants completed a debrief questionnaire collecting standard demographic information and open-ended feedback on the study.

Training Details Our infrastructure restricts that each human participant can only play five matches with our bots. Therefore we decided to select five different agents so every participant can play each of these once. For comparison, we decided to include one independent RL agent and four search-improved PSRO agents of different playing styles. For the independent RL agent, we trained two classes of independent RL agents in self-play: (1) DQN [Mnih et al., 2015] and Boltzmann DQN [Cui and Koeppl, 2021], and (2) policy gradient algorithms such as A2C, QPG, RPG and RMPG [Srinivasan et al., 2018]. We fine-tuned their hyperparameters and eventually select an instance of self-play DQN based on both individual returns and social welfare performances.

For PSRO agents, we consider 16 different meta-strategy solvers, and 4 different back-propagating value types during the tree search procedure, making it 64 different combination in total. Notice that the original MCTS algorithm (Algorithm 2) back-propagates individual rewards during each simulation phase for the search agent.

We consider two way of extracting the final agents given sets of policies Π produced by PSRO, one based on the final-iteration MSS mixture and another based on the finaliteration search-based best response (details are in App F). We trained over 100 PSRO agents with different combinations of MSS, back-propagation targets, and extraction methods. To select among these agents, we apply empirical gametheoretic analysis [Wellman et al., 2025] and obtain a headto-head empirical game matrix. We eventually selected: (i) two most competitive agents (Comp1, Comp2) (maximizing utility), (ii) the most cooperative agents (Coop) (maximizing social welfare), the (iii) the fairest agent (Fair) (minimizing social inequity [Fehr and Schmidt, 1999]); (iv) a separate top-performing independent RL agent (IndRL) trained in selfplay (DQN). Both Coop and Fair are using Nash product as the back-propagating values during tree search, while Comp1 uses inequity aversion and Comp2 uses individual rewards. Comp1, Comp2 and Fair are trained using max-Gini correlated equilibrium notions [Marris et al., 2021], while Coop uses uniform distribution as the MSS.

Results We collect data under two conditions: human vs. human (HvH), and human vs. agent (HvA). In the HvH condition, we collect 483 games: 482 end in deals made (99.8%), and achieve a return of 6.93 (95% c.i. [6.72, 7.14]), on expectation. We collect 547 games in the HvA condition: 526 end in deals made (96.2%; see Table 1). DQN achieves the highest individual return. By looking at the combined reward, it achieves this by aggressively reducing the human reward (down to 5.86)-possibly by playing a policy that is less human-compatible. The competitive PSRO agents seem to do the same, but without overly exploiting the humans, resulting in the lowest social welfare overall. The cooperative agent achieves significantly higher combined utility playing with humans. Better yet is Human vs. Fair, the only Human vs. Agent combination to achieve social welfare comparable to the Human vs. Human social welfare.

Another metric is the objective value of the empirical NBS from Eq. 1, over the symmetric game (randomizing the starting player) played between the different agent types. This metric favors Pareto-efficient outcomes, balancing between the improvement obtained by both sides. From App G.3, the NBS of Coop decreases when playing humans, from 44.51 Ñ 41.35- perhaps due to overfitting to agent-learned conventions. Fair increases slightly (42.56 Ñ 44.23). The NBS of DQN rises from 23.48 Ñ 38.12. The NBS of the competitive agents also rises playing against humans (24.70 Ñ 28.10, and 25.44 Ñ 28.10), and also when playing with Fair (24.70 Ñ 29.63, 25.44 Ñ 28.73). The fair agent is both adaptive to many different types of agents, and cooperative, increasing the social welfare in all groups it negotiated with. This could be due to its MSS putting significant weight on many policies leading to Bayesian prior with high support, or its backpropagation of the product of utilities rather than individual return.

6 Conclusion

We proposed a general-purpose multiagent training regime that combines the power of MCTS search and a populationbased training framework, for general-sum imperfect information domains. We developed a novel search technique that combines IS-MCTS with a deep belief learning module coupled with the RL training loop, which scale to large belief and state spaces. The outer loop of our algorithm is implemented by PSRO, which iteratively trains and adds search strategies guided by game-theoretic analysis. On one hand, search serves as a strong best response method within the PSRO loop, which provides an instance of the framework of its own interests. On the other hand, PSRO automatically produces a belief hierarchy over the opponents' strategies, which endows the search with the capability of inferring opponent types during online decision makings. This dual view of the whole training architecture illustrates its effectiveness in producing agents that are capable of opponent modeling through game-theoretic analysis and planning forward at test-time.

Ethics Statement

We believe our GenBR method with the PSRO training loop advances the general opponent modeling and planning techniques in multi-agent systems with little domain knowledge. Our methods can be potentially deployed in a variety of applications, including automated bidding in auctions, negotiation, cybersecurity, warehouse robotics, and autonomous vehicle systems. All of these are multi-agent scenarios that involve general-sum, imperfect information elements.

One of the potential risks is value misalignment in negotiation. The method can produce strategies that are unpredictable and not easily explained, which could lead to exploitative behaviors in negotiation that are misaligned with the users' intents. This could potentially cause harm in the economic system and reduce market efficiency. Any deployed use of artificial agents built using our algorithm would need to first be thoroughly tested, ideally by third party, and undergo a controlled private study with humans to identify any potentially harmful behavior.