Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
Authors: Austin A. Nguyen
Anri Gu
Michael P. Wellman
Venue: ICML 2025 poster (2025)
Keywords: Empirical game theoretic analysis
equilibrium selection
game solving
strategy exploration
Primary area: reinforcement_learning->multiagent

Abstract: Iterative extension of empirical game models through deep reinforcement learning (RL) has proved an effective approach for finding equilibria in complex games. When multiple equilibria exist, we may also be interested in finding solutions with particular characteristics. We address this issue of equilibrium selection in the context of Policy Space Response Oracles (PSRO), a flexible game-solving framework based on deep RL, by skewing the strategy exploration process towards higher-welfare solutions. At each iteration, we create an exploration policy that imitates high welfare-yielding behavior and train a response to the current solution, regularized to be similar to the exploration policy. With no additional simulation expense, our approach, named Ex$^2$PSRO, tends to find higher welfare equilibria than vanilla PSRO in two benchmarks: a sequential bargaining game and a social dilemma game. Further experiments demonstrate Ex$^2$PSRO's composability with other PSRO variants and illuminate the relationship between exploration policy choice and algorithmic performance.

Explicit Exploration for High-Welfare Equilibria in Game-Theoreti Multiagent Reinforcement Learning
Austin A. Nguyen'
Anri Gu
Michael P. Wellman'
Abstract
paradigm of centralized training decentralized execution (Rashid et al., 2020; Lowe et al., 2017).
Iterative extension of empirical game models through deep reinforcement learning (RL) has proved an effective approach for finding equilib- ria in complex games. When multiple equilib- ria exist, we may have preferences among solu- tions. We address this equilibrium selection issue in the context of Policy Space Response Oracles (PSRO), flexible game-solving framework based deep RL, by skewing strategy generation to- wards welfer- solutions. At each iteration, we create an exploration policy that imitates high welfare-yielding behavior and train a response to the current solution, regularized to be similar to the exploration policy. With no additional simu- lation expense, our approach, named Ex?PSRO, tends to find higher welfare equilibria than vanilla PSRO in two benchmarks: sequential bargain- ing game and social dilemma game. Further ex- periments demonstrate Ex²PSRO's composability with other PSRO variants and illuminate the re- lationship between exploration policy choice and algorithmic performance.
When the agents are independently controlled, it makes sense to frame the problem in terms of solving a game. In game formulation,
stn-sstttonaitty can be understood as arising from strategic interactions among agent decisions. Our work builds on standard framework in this genre called Policy Space Response Oracles (PSRO) (Lanctot et al., 2017). PSRO uses form of population- passlltttioo-beedddd training, where the set of available policies (strategies) is iteratively extended by deriving best responses to the evolving game model. PSRO can also be viewed as a form of empirical game-theoretic analysis (EGTA) (Wellman et al., 2025), as the game model is estimated through agent-based simulation. PSRO addresses scalability and non-stationarity by focusing enumerated set of strategies from large space and training one agent at time in a context where other agents' strategies are fixed.
The efficacy of such iterative methods depends on the ability to identify strategies that cover the relevant game features and contribute to game solutions. Alternative approaches to strategy exploration (Jordan et al., 2010) generate different sequences of game models and thus determine how quickly solution is found (Wang et al., 2022). The method of strategy exploration can also shape which solution is found, that is, influence equilibrium selection for games with multiple strategic equilibria (Wang & Wellman, 2024).
1. Introduction
Multiagent reinforcement learning (MARL) research addresses two core challenges: scalability and non- stationarity. Scalability refers to how the relevant search space for training grows exponentially with the number of players and strategies. Non-stationarity describes how agents' learning contexts change as their observations and rewards depend the evolving strategies of other agents. If the goal is to specify policies for distributed agents under unified control, these challenges can be addressed under the
This work addresses equilibrium selection by steering strat- egy exploration toward solutions with desirable character- istics. Specifically, we extend PSRO by leveraging the simulation data already generated by the algorithm to iden- tify policy elements that seem promising for high-welfare solutions. Using behavior cloning, we train an exploration policy that reflects the promising behavior found in sim- ulation traces. We then modify the process of training best-response strategy, by adding a regularization term that biases the output to be similar to the exploration policy. This explicit form of controlled exploration in policy space gives the algorithm its name: EX?PS
'Computer Science & Engineering, University of Michi- gan, Ann Arbor, MI, United States. Correspondence to: Austin A. Nguyen <ngaussinne Ingaustin@umich.edu.. umich.edu>, Anri Gu <an- rigu igu@umich.cdu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
The primary contribution of this work is method based on policy-level regularization for strategy exploration in service

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
of equilibrium selection. Through experiments two game classes for which equilibrium selection is paramount- social dilemma game and a bargaining game-we find that EXPPSRO tends to produce higher welfare solutions than the PSRO baseline. Further experiments combining PXRP with existing high-welfare equilibrium selection approaches demonstrate its modularity and ability to improve welfare on other PSRO variants.
t (-) (r (one for each player). Each trajectory is a sequence of observations, actions, and rewards for player p over time: rj = {[o (lo rf))
3. Related Work
Policy regularization is widely used in RL to instill prior behavior during training (Cheng et al., 2019; Rudner et al., 2021; Bakhtin et al., 2022). In offline RL., regularization can encourage similarity between the learned policy and the dataset's 's behavior, reducing distribution shift (Wu et al., 2019; Kostrikov et al., 2021; Xu et al., 2021). In online RL, self-imitation learning reinforces behaviors that yield de- sired outcomes in sparse-reward contexts (Oh et al., 2018). In MARI., policy regularization has been used to promote coordination (Roy et al., 2020) or as an alternative en- tropy regularization (Su & Lu, 2022). Regularized Nash Dynamics (R-NaD) (Pérolat et al., 2021) demonstrated the use of regularization as part of game-theoretic MARL regime. Approaches like Follow the Regularized Leader (FoReL) have also utilized regularization to balance the explotation-eexllraaton tradeoff (Pérolat et al., 2021).
2. Terminology and Notation
A symmetric game I' is represented in normal form by a tuple (II, U, n), where n is the number of players, II their set of available strategies, and payoff function U II - R maps joint strategies π = (I1...., .T) to vectors of payoffs. Symmetry dictates that U be invariant to permutations of player position: (p)rm(TT)
perm (U (T)). Policy π E II is called pure strategy. and a E (IT)) is a mixed strategy. A subscript -1 indicates all players except one. For instance, IT-I is the joint strategy of all other players, with "other" clear from context. We write the payoff for playing ı when the others play x-1 as u( 11). where u refers to the element of vector U indicating the payoff given to the player invoking strategy æ. When the others play joint mixed strategy --1, the payoff is given by expectation:
The PSRO algorithm (Lanctot et al., 2017) works by iter- atively extending an empirical game model I (II, U, ,)) using RL. We initialize II, for example with a single ran- dom policy. PSRO extends I at each iteration through these steps: (1) update T by estimating payoffs for all strategy profiles (i.e., joint strategies over II) through simulation, (2) extract target profile T by applying a meta-strategy solver (MSS) to r, and (3) derive best-response policy "" II by applying deep RL in an environment where other players are fixed to play o² and add 'T to II.
" 1-1) = Ex 1ー ((TT 1)).
(1)
Given our symmetry assumption, we often overload notation to allow a strategy (pure or mixed) to stand for a symmetric joint strategy (i.e., all play the same). The welfare of a refers to the expected summed payoff's across all players when playing strategy o.
Likewise under symmetry, a player's best response to all oth- ers playing a is given by BR(a)= arg max u(n, 0-1).
A key idea of PSRO is abstracting the selection of best- response target, through the MSS. Different MSSs generate different response sequences and hence guide strategy explo- ration. Using replicator dynamics (RD) (Taylor & Jonker, 1978) or any other Nash solver as MSS corresponds the double oracle method (McMahan et al., 2003). The original PSRO paper (Lanctot et al., 2017) noted that DO overfits to the current solution and introduced projected replicator dy- namics (PRD) as an MSS that produces approximate Nash equilibrium. The PSRO literature has investigated a variety of alternative MSSs, as well as other variants designed to reduce computational cost or exploit game model structure (Bighashdel et al., 2024).
Mixed strategy o² is a (symmetric) Nash equilibrium (NE) iff o* E BR(o*). The potential gains of deviating from symmetric play of a is called regret: (og = max u( 0-11) - E 1-1). By definition, if a² is a NE, its regret zero. An empirical game model -= (II, U, n) is normal-form game over strategy set II (a finite subset of a larger policy space II), with payoff function U estimated through simulation.
Reinforcement learning (RL) models the environment as a Markov Decision Process (MDP). A policy Tg is defined as a mapping from the MDP's observation space O to a prob-
ability simplex over the action space A: To : O - A(A).
A recent study by Wang & Wellman (2024) investigated how varying the response objective can affect the behavior of PSRO, including its selection of equilibria. In particular, this work showed that optimizing responses for a combina- tion of own and other-agent utility could steer PSRO toward helfer-welfare equilibria. These objectives may incorpo- rate broader measures (c.g. total social welfare), enabling
The probability of choosing action a, given observation Or
is given by Te (a I ot). When agent applies action a; given observation or, reward r, is observed. Each sim- ulation of the environment generates a set of trajectories
'ee assume symmetry throughout this paper for convenience, experiments performed on symmetric games. Extension to non-symmetric or role-symmetric games is discussed below.
2

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
PSRO to discover more desirable equilibria. Related re- search has focused on integrating diversity measures into response objectives to ensure thorough exploration of policy space (Balduzzi et al., 2019; Liu et al., 2022; Perez-Nieves et al., 2021; Parker-Holder et al., 2020).
where V = = is player p's return in trajectory T This criterion maximizes welfare and disregards trajectories where welfare is high at the expense of any one player. Trajectories are collected from all simulation queries (i.e., empirical game updates, response training). Among the observed trajectories Tj, B selects the N with the highest criterion score (TT)).
4. Explicit Exploration
Consider the simple 2-player game shown in Fig. 1. There two symmetric equilibria: playing A and B with equal probability or playing C. The latter Pareto dominates, but starting double oracle (or PSRO) from A or B would pro- duce the former. Even if we replaced best-response with an optimization of social welfare (or any linear combination with individual payoff), C would never be selected when the other player is fixed at a mixture of A and B.
4.2. Constructing Exploration Policies
We reiterate that an exploration policy should introduce el- ements that potentially incorporate pro-welfare properties. Since our criterion (TT,) expressly selects for that behavior, it is reasonable that the exploration strategy should match be- havior in B. We denote an exploration policy at EXRPSRO's hth iteration by _ ExPPSRO trains Th.. by using behavior cloning (BC) on B. Specifically, we create policy that maximizes:
A
B
C
A
2,2
2,3
1,-2
o eo (a 0) = arg max ((T ox)) (or, ax) ~ B, (3)
B
3,2
1,1
2,-1
C
-2,1
-12
5,5
where we ignore the reward component of trajectories in B. Note that T is not itself added to the empirical game but rather used to steer Ti (Ex (Ex*PSRO' 's response policy at iteration i), in particular way. This is discussed in the next section. Ti. is estimated using neural network with a softmax output layer and is optimized using cross- erossyy loss. We defer further details to Apps. A.1 and B.
Figure 1. A 2-player, symmetric normal-form game. Starting from either A or B, PSRO converges to an equilibrium mixture over A and B (regardless of MSS), which is Pareto-dominate by (C, C).
This example highlights that discovering high-welfare equi- libria sometimes requires players to add strategies that are currently suboptimal (i.e., with respect to any other agents' generated strategies), but could ultimately lead to more favorable equilibria. In the absence of an all-knowing co- ordinator, we need some way to identify and steer strategy exploration toward potentially effective joint behavior. In the context of the PSRO framework, this suggests we may need to produce strategies that could not be found through best-response operations alone, regardless of MSS.
4.3. Policy Regularization Objective
We now demonstrate how exploration policy Tez is used to influence the added strategy mt- EX²PSRO builds on the bascline's "vanilla" PSRO's best-response step of the algorithm. At each iteration vanilla PSRO trains an approximate best-response policy Tे² to optimize the objec- tive:
T
4.1. Extracting Desired Behavior
J'(0) = E
Σ
r
(4)
To guide exploration, we first identify behavior that could lead to higher welfare equilibria. EXPP does this by scanning simulation data for traces that seem to produce helh-welfare outcomes. To that end, Ex²PSRO extracts a buffer B of N trajectories {r that maximize some crite- rion C(Ty). In symmetric games, 2 we employ a maximin welfare criterion:
1=1
#i R arg max J'(O),
T
To
where rt is the player's reward time 1, T refers to the (potentially infinite) horizon, 0 represents the parameters of the policy Ta. and z underscores the use of deep RL to approximate the best-response. The expectation in (4) is conditioned on i, reflecting the best-response target selected by PSRO's 's MSS at that iteration.
((i))=min(V??
= mimmmnn V2)).
We insert a regularization term Ri(0) that steers T/ to be more similar to n² More formally, let R' R'(0) be mea- sure of the distance of a policy parameterized by 0 to the
2Symmetry entails we can evaluate player payoffs on the same scale when a given trajectory plays out differently for various players. For non-symmetric games, payoff normalization (using empirically estimated minimum across players return percentile as C(T,)) and player-specific exploration policies would he required.
Stochasticity returns is not accounted for, chance success affects the selection.
3

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretis Multiagent Reinforcement Learning
exploration policy at iteration i. Specifically, we define:
Algorithm EXPPSRO
Input: Max number of trajectories N, meta- mneta-ttrategy solver M, Initial regularization Banat. Regularization decay steps
R²(0) (F TT),
(5)
S3, PSRO itcrations T. number of players n
where DKL(. || .) denotes KL divergence. (0) is esti- mated through sampling and assumes R. the RL oracle's replay buffer, defines the prior over observations o2:
Output: Strategy set II, Profile oT
1: Initialize empty empirical game I"; (11, U,, n))
DxL(Ter TO)= x
2: Initialize strategy set w/ random policy IT f- {mg]
3: Initialize 8g + Binst
Ten (a oz) Te(a oz)
Bo Σ aEA
Tea (a oz) log
(6)
4: Update empirical game T
5: Initialize Bo with used trajectories
6: Initialize B <- N trajectories in Bo maximizing C(T))
Ex EXRPSRO encourages exploration by introducing (0) regularization term in the response objective and weighting R (0) by Be at iteration i:
7: for each PSRO iteration i of to T do
8: Compute Tez using B and Eq. 3 if > >
9: Compute response Tá using 3rs T d_1 and Eq. 7
10: Update strategy sets + 11 U T
T R3 arg max (J)
11: Update empirical game r
We
12:
Store used trajectories in B,
13:
B x- Top N trajectories T, (B; UB) w/ Eq. 2
Intuitively, the objective (7) skews the response the direc-
14: Update joint profile of 1 M(T)
tion of the exploration policy. T is constructed to reflect
15: Anneal 3 c- max(0, Binn (Sa-))
gigh-wefare-yielding behavior, so the objective encourages
16: end for
the introduction of strategies that contain more pro- pro-welfare elements. Moreover, since the trajectory buffer is shared amongst all players, they are all regularized towards behav- iors that ideally coordinate well with each other. This can help address the issue posed by the example in Fig. 1. Ide- ally, behavior in B and strategy C would be similar. Then, regularization toward 8 behavior would skew strategy exploration by encouraging the addition of high-welfare yielding policies similar to strategy C. We underscore that trajectory buffer sharing does not modify game dynamics- each player still only has access to their own information. This is discussed further in App. F.
17: return IT, TT
deep reinforcement learning, updating the empirical game F, and updating meta-strategies. (T). EXPPSRO creates an unregularized best response TT' because B at that point only contains trajectories from random rollouts, which may contain uninformative and possibly detrimental behavior to regularize towards for certain exploration policy choices. In our implementation, the initial policies sample uniformly from actions in all states.
4.4. 2 Algorithm
Many PSRO implementations use value-based RL methods to train approximate best responses. Our explicit explo- ration approach employs regularization defined in policy space. As regularizing value estimates by policy is unde- fined, value-based methods are unsuitable. Accordingly, we adopt the Soft Actor-Critic (SAC) (Haarnoja et al., 2018) 8) method to train approximate best responses, specifically its discrete implementation (Christodoulou, 2019; Zhou et al., 2022). EX²PSRO (Alg. 1) modifies SAC's actor update by augmenting its objective with the regularization term from Eq. (6). For consistency in comparison, we use SAC for both PSRO and vanilla PSRO's best responses, where the latter's 's regularization strength B; is set to zero for each iteration i.
We describe in detail how the trajectory buffers B are built. Let B, denote the trajectories gathered from training itera- tion i's best response and empirical game updates. These are added the trajectory buffer, B B U B, Then, Ex EPRR filters B by taking the top N trajectories that maximize criterion C(T).
The Ex² PSRR procedure is depicted schematically in Fig. 2. We define or train exploration policy ~ Next, we train our regularized best responses by optimizing (7) with SAC, augmenting its actor loss with the regularization term. Ex? PSRO then updates the empirical game I and, subse- quently, meta-strategies using the MSS M. The regulariza- tion strength 3r is initialized to 3 and lincarly annealed across S PSRO iterations, where Seni and Sy are hyper- parameters. This process repeats until the max number of Ex²PSRO iterations reached.
The first iteration of Ex PSRO is nearly identical to that of PSRO. It starts by initializing random strategies for each player, creating an unregularized best response nt using
4

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretis Multiagent Reinforcement Learning
n
?
Train nt' with BC
π
?
o,
?
Train Regularized Response I
Update Empirical Game
Update Profiles
Figure 2. After the first iteration, PSRO cycles through three steps: (1) updating the empirical game model I, (2) deriving the response
target M(T) = a² using MSS M while training exploration policy T using trajectories {Tz}ÿ=1- and (3) training new strategy Ty. Following steps (1) and (3), all observed simulation trajectories Ty are added buffer and filtered using criterion C(Ty).
5. Results
Expected Welfare Over Iterations: Simple Game
5.1. Environments
37.5
We first demonstrate how EXPPSRO operates in hand- crafted dynamic environment (Fig. 3) exhibiting the coor- dination issue exemplified in Fig. 1. Players alternately choose to move left or right, and the episode ends after 10 total actions. There are two equilibria of interest. The first, which we refer to as Equilibrium 1, consists of players going between states so and $1. repeatedly gathering +1 reward. The second, analogously Equilibrium has players reach and alternate between states 87 and 8y, which collects lower rewards initially but dominates the first in overall return. Co- ordination is vital in achieving the latter equilibrium. The second equilibrium strategy is a best-response only to strate- gies similar to itself, meaning it cannot be found through strict best-response. Using welfare-oriented objective does not help in this case.
35.0
Expusieed www.scc//wafaame. Walffae
27.5
25.0
22.5
15
38
Beration
Figure 4. Welfare trends over PSRO itcrations using Vanilla, Gen- eralized Response Objectives with 5 optimizing welfare, and Ex PSRO with Brast = .I. in the proof-of-concepl MDP.
61-11
(3
(5,5)
fare improvements. In contrast, EX2PSRO bookmarks high- welfare trajectories that travel states 87 and $g, constructs strategies similar to such behavior, and eventually includes relevant strategies in I to discover Equilibrium 2. Ex EX²PSRO achieves a significantly higher welfare 38.0. This high- lights the effectiveness of its regularization-driver approach in uncovering higher-weltee welfare equilibria that are inaccessible through immediate or myopic optimization. Welfare plots for this experiment are shown in Fig. 4.
S
9
01.
M,-1)
(2. 2)
(1.41
(1.41
(1.1)
(3,
Figure 3. Hand-crafted Markov Decision Process
In this and GRO welfare do not add the strategy to move right towards 37 and s3 to the empirical game, therefore never discovering Equilibrium 2. They both achieve welfare of 20.0. GRO Welfare, which optimizes welfare at each iteration, is inherently limited by its focus on myopic wel-
MDP environment, Vanilla PSRO
We more extensively test our approach in four game vari- ants: two disparate versions of two benchmarks. Harvest (also known as Gathering) (Perolat et al., 2017) is a grid- world sequential social dilemma game where players collect apples that stochastically spawn, each of which gives
5

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
reward. After being collected, apples respawn at dedicated locations with probability proportional to the number of surrounding apples at each timestep. The players individ- ually benefit by gathering as many apples as possible, but collectively benefit by leaving sufficient apples to enable respawning. Players may also shoot a laser, firing a beam several spaces ahead of them and removing any hit player from the game for a fixed number of time steps. We test our approach in two Harvest maps, referred to Hervest-Dense and Harvest-Sparse, designed to be distinct enough to sig- nificantly change underlying game dynamics. We elaborate further in App. C.I.
averaged over 10. Details on hyperparameters, tuning, and implementation are provided in Apps. A.1, B, C.I, and C.2.
5.3. Varying Exploration Policy
We also conduct experiments varying Ex EX²PSRO's explo- ration policy to analyze its dependence on the target behav- ior it regularizes towards. Table 4 in App. A.1 summarizes the four tested exploration policy alternatives. Uniform sets गेe to a policy that selects actions uniformly for all states. Min Melfere and MalWelfare use BC to train v:e on datasets generated by trajectory criteria prioritizing low and high welfare, respectively, and disregarding return distribu- tion among players. PrevBR sets T²e to the most recently added strategy. From this point forward, we refer to this suite of ablations over The as "Ablation-TTer experrments...
We also test our approach on 2-player, turn-based, im- perfect information bargaining game, employing a version defined by Lewis et al. (2017). The game (which we refer to as Bargaining) features a pool of items that players must divide among themselves. Each player has a random, private value function that assigns a non-negative utility value to each item. Players alternate making offers of division until a player accepts or the game reaches a maximum number of iterations. If a player accepts, players receive utility ac- cording to the accepted asset allocations and their respective value functions, discounted by 7' where 0 7 < is hyperparameter and is the number of time steps so far. If no agreement is reached by the turn limit, both players receive zero utility. We test our approach in two Bargaining variants (detailed in App. C.2). setting y to .99 and .95. Dis- count factor differences drastically modify game dynamics, so experiments in both settings are essential for a thorough evaluation of Ex 2PRRO.
All Ablation- experiments use the same regret threshold À and initial regularization Simst as tuned EX²PSRO, simi- larly fixing S = 25. This experiment isolates and measures to what extent Ex 2 PSRO's performance depends on regu- larization choice versus regularization strength. Ablations over Benit and À are provided in App. H.2.
5.4. Equilibrium Welfare
Fig. 5 shows welfare of equilibria returned from tuned ver- sions of vanilla PSRO, Ex EX"PSRO, and Ablation-T
Welfare differences should be measured relative to the game's distribution of available equilibria, though comput- ing this distribution becomes computationally intractable for large games. The bar graph in Fig. uses normalized values to approximate this relative measurement, providing meaningful representation of the improvements achieved.
5.2. Implementation and Reproducibility
We build on an implementation of PSRO in an existing codebase, OpenSpiel, provided by Deepmind (Lanctot et al., 2019). Our experiments use MSS called regularized replicator dynamics (RRD) (Wang& & Wellman, 2023), cho- sen for its simplicity and strong empirical performance. RRD has a regret threshold parameter X that determines the regret at which RD terminates, yielding a X-Nash equi- librium. X is linearly annealed across all PSRO iterations. When x= = 0, RRD reduces RD.
We also provide significance tests for our welfare results, comparing Ex² to vanilla PSRO and Ablation- We use Welch's t-test to calculate P-values as informed by Colas et al. (2019) for its robustness to false positives compared to non-parametrie tests. P-values are not adjusted for multiple hypotheses.
Performance in these four benchmarks indicates that Ex PSRO tends to increase welfare through strategy explo- ration, yielding welfare improvements over vanilla PSRO with low P-values on all benchmarks tested. EX²PSRO also tends to outperform approaches in Ablation- with low value, noting a few exceptions in the next paragraph.
We compare EXRO to vanilla PSRO, a SOTA game- solving framework. For Ex ESR,,, we performed a grid search over À and Binst, keeping Sn- = 25 constant, where each parameter setting's welfare is averaged over 5 trials. Then, we select the parameter setting (A, 3rose) with the highest welfare and provide it an additional 5 trials, totaling 10 trials for the final result. Vanilla PSRO is tuned over X, where we immediately run 10 trials for each À candidate and report data from the perfort-p parameter setting. Due to computational limitations (App. G), Ex PSRO regret values are averaged over 5 trials, while all other settings are
While PXRR and Uniform showed comparable perfor- mance in Harvest benchmarks, EXRP demonstrated distinct advantages in Bargaining scenarios. Similarly, P. values indicate PXRO and Max Welfare performed simi- larly in Harvest-Sparse. Performance across environments reveals key relationships between game dynamics and reg- ularization. In Ablation Tezz Harvest's welfare improve-
6

---

Explicit Exploration for High-Welfarr Equilibria in Game-Theoretic Multiagent Reinforcement Learning
11
130
F
150
12.8
14.0
125
145
13.8
140
12.6
1
Welfare
135
13.6
Vrilla EXPPRRO MaxWeifere
115
130
13.4
Vinilietfare PrevBR
110
13.2
12.2
120
100
115
13.0
12.0
95
110
12.8
Harvest Sparse
Hervest Denae
Bargaining (99)
Bargaining (95)
Algorithm
Harvest-Dense
Harvest-Sparse
Bargaining
-99
Bargaining 7
EXRR (Ours)
150.2 1
N/A
129.0 N/A
12.86 + 0.26 N/A
14.02 0.22 N/A
Vanilla
119.6+3.4
p .01
8.9
p .01
12.50 + 0.55
p= -04
13.76 0.34
p == .03
Uniform
146.0 8.3
p p= .13
1.3
p= .24
12.49 0.33
== .01
13.72
0.34
0.34
p .02
MinWelfare
143.5 9.5
p .05
119.9
p .02
12.63
p .05
13.38
+ 0.73
p .01
Max Welfare
142.0
p .01
1.6.4
.32
12.13
0.37
p .01
13.83
1.831100 0.48
p .08
PrevBR
128.2 1 4.3
p <
123.4 7.3 p = .05
12.53 0.33
p = .01
13.56
0.39
p
Figure 5. Welfare of equilibria found by vanilla PSRO, Ex EPRRO, and Ablation with significance results. These tests alternatively hypothesize whether PSRO yields higher welfare equilibria than vanilla PSRO and Ablation- ea Bolded values in the table indicate each environment's highest relfare-yielding approach. Welfare is averaged over 10 trials with tuned hyperparameters (A, (mii). Bar graph axis bounds are scaled to display the middle 68% of welfare found across all trials (185 per game), discussed in App. D. This is intended provide normalized view of observed differences, further discussed in $5.4 App. D. Error are omitted for clarity.
Table Combining Ex ESRO with GRO. P-Values of EXRPSRO and GRO are measured with respect to Vanilla. Paluue of GRO+Ex?PSRO measured with respect GRO.
Algorithm
Harvest-Dent
Harvest-Sparse
Bargaining 7 .99
Bargaining 7 = .95
Vanilla
119.6 3.4
108.6 8.9
12.50 .55
13.76 .34
GRO
134.6 = 9.1
115.2 = 11.0
12.99 + .33
15.07 .10
Ex ESRO (Ours)
150.2 + 7.9
129.0 + 7.5
12.86 + .26
14.02 + .22
GRO + EXPRS (Ours)
151.0 p < .01
122.3 9.5 p =0
.07 13.49 1: .39 p < 15.24 +: .08 p <
ments naturally emerge from any regularization that re- duces immediate apple collection, allowing more apples to spawn. Shown with detailed significance tests in App. D, Ablation- variants achieved improvements over vanilla PSRO in Harvest with low P-values. EX"PSRO particu- larly shines in Bargaining, where achieving high- welf-re behaviors requires navigating more nuanced and complex interactions.
Additional analysis and data for hyperparameter searches over À and Binst are provided Apps. H, H.2, and Table 8, while ablation experiments varying Smi or À are detailed in App. H.2. EX²PSRO's tuning was conservative, potentially missing stronger parameter settings, whereas vanilla PSRO underwent exhaustive tuning, and results reflect its highest- welfare configuration.
5.5. Combining with Generalized Response Objectives
Fig. demonstrates Ex Ex²PSRO's ability to discover high- welfare solutions more rapidly than other tested approaches. While Uniform exploration achieves quick initial gains in Harvest, its progress plateaus early. MinWelfare shows swift improvements in Bargaining 7 .99 but gradual in Harvest. Max Welfare welfare trends vary widely while Pre- vBR's welfare increases slowest within Ablation-T These results underscore a key strength of EX²PSRO: its strong performance (in its consistency, speed, and magnitude of welfare increases) can attributed to both the presence and deliberate choice of regularization.
In principle, any PSRO variant can incorporate Ex EXPPSRO by including the regularization term (Fq. 5) in its response objective. We demonstrate Ex²PSRO's composability by combining it with another approach addressing high-welfare equilibrium selection: Generalized Response Objectives (GRO) (Wang Wellman, 2024). We highlight that GRO is not considered competing approach but one whose per- formance can be bolstered and amplified by Ex²PSRO.
Experiments augmenting vanilla PSRO and GRO with ESRR are shown in Table 1. With low P-values, the
7

---

Explicit Exploration for High-Welfare Equilibria in Game Theoreic Multiagent Reinforcement Learning
Sepected Eue Dar tweation Harved Derie
Bargsning (95) Ragud va Wellare
14.5
14.0
13.5
44.3
13.5
11.0
144
11.
Expectid
Expacioc Weltoe Over teralen: Bangiiting y
Dargaiiigg Regret vs.
13.5
12.0
11.5
02
0.1
1.
34
legeet
Harvest Scarsn Righet vs. Weiltrr
150
Figure 6. Welfare plots for vanilla PSRO, Ex PSRO, and Ablation- Wex. include error bars for only vanilla PSRO, Ex PSRO, and the top performer in Ablation-T for each game for clarity. App. H has additional plots.
160
L:0
110
data supports that combining Ex PSRO with GRO tends to find higher welfare equilibria than GRO alone. Compared to tested approaches, GRO+EX*PSRO tends to find the highest welfare equilibria, suggesting that the combination ampli- fies welfare improvements. An exception Harvest-Sparse, where EXRPSRO achieved the highest welfare. Note that do not compare GRO and EXO directly tune GRO-specific parameters. Instead, these experiments sup- port EXPPS'O's 'ss flexibility and composability with different PSRO variants to improve welfare potential. App. A. pro- vides additional details on hyperparameters and procedures.
Harvest Dense Regret vs. Welfore
110-
1:0
130-
100
Nogest
Figure 7. Final regret and welfare of output solutions across ap- proaches. Circles and squares represent individual trials and aver- aged performance within a specified approach, respectively.
5.6. Regret X Welfare Analysis
The regret and welfare of final profiles discovered are shown in Fig. 7, where square markers indicate the averaged perfor- mance of a particular algorithm. Bargaining 7 = .99 and Harvest-Sparse, Ex Ex²PSRO dominates all tested approaches. While EXRO generally tends to find high-welfare solu- tions with lower regret, Uniform and PrevBR tend to find slightly lower regret profiles than Ex PXRR in Bargaining yy=66 .95, In Harvest-Dense, MaxWelfare finds lower regret profiles than Ex EXPP
approximations are provided in App. G. Trends in Fig. 8 and App. H indicate that EX²PSRO appropriately generates approximate equilibria in all benchmarks. We note that all regret trends approach equilibria shown by the untrun- cated plots (App. H) but Fig, 8 enlarges some of the last few iterations' datapoints for clarity.
Ex PSRO tends to find lower regret solutions faster than vanilla PSRO, indicating a link between convergence and regularization. Relative to Ablation- experiments, Ex PSRO is consistently among the top performers in con- vergence speed and final solution regret. These results sug- gest PXRPS presence and choice of regularization to- gether provide a mechanism to improve convergence while encouraging the discovery of solutions with higher welfare and, possibly, lower regret. We highlight that Ex?PSRO's 's true regret estimation was more thorough than other ap-
Small positive correlations between regret and welfare in Harvest could reflect the game structure of social dilemmas, where high-welfare profiles tend to have high-value strategic deviations. In Bargaining, there is a negative correlation between the two metrics, suggesting relative stability of high-welfare solutions found.
Next, we compare and analyze regret trends of intermedi- ate profiles of all approaches. Details on true game regret
8

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
Negrtt Over thretees Harvest Sparso
provides a simple and effective mechanism to guide strategy exploration in service of high-welfare equilibrium selec- tion. Experiments combining EX²PSRO and Generalized Response Objectives support its composability with other PSRO-adjacent approaches to improve welfare. Lastly, ex- periments illuminate how a game's inherent structure may influence which regularization choices are beneficial or detri- mental to performance.
Buchei) Sark Reade
Patninn Maceehas undenn
12
15
12
Prggret Over beret one Bappninng yn 23
Regret Dael tevisansc Neiganing yo-15
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Figure 8. Regret plots for vanilla PSRO, Ex PSRO, and Ablation- Ten- We include error bars for only vanilla PSRO, Ex PSRO, and the top performer in Ablation- for clarity. Harvest plots observe trends in later iterations. App. H has additional plots.
Bakhtin, A., Wu, D. J., Lerer, A., Gray, J., Jacob, A. P., Farina, G., Miller, A. H., and Brown, N. Mastering the game of no-press Diplomacy via human- regaan-rggllriized rein- forcement learning and planning. In / Ith International Conference on Learning Representations, 2022.
proaches (App. G), meaning vanilla and Ablation-Tez ee so- lutions are more likely to have even higher true regret than reported. In summary, regret trends favor EXRP despite being given a disadvantage in terms of its regret evaluation. Additional regret trends and ablations are provided in Apps. H and H.2.
Balduzzi, D., Garnelo, M., Bachrach, Y., Czamecki,, W., Perolat, J., Jaderberg, M., and Graepel. T. Open-ended learning in symmetric zero-sum games. In 36th Internu- tional Conference on Machine Learning, pp. 434-443, 2019.
Bighashdel, A., Wang, Y., McAleer, S., Savani, R., and Oliehoek, A. Policy space response oracles: A sur- vey. In 33rd International Joint Conference on Artificial Intelligence, pp. 7951-7961, 2024.
6. Conclusions
We investigated the possibility of steering MARL game- solving toward preferred equilibria, particularly those with higher welfare. Toward this end, we introduce the concept of exploration policies. To construct these exploration poli- cies. EXPPSRO filters already-presse present simulation traces for high-welfare yielding behavior and applies behavior cloning to the filtered data. Then, EX²PSRO uses these policies to regularize best-response computations towards promis- ing behavior within the PSRO framework. Notably, since Ex does not require any additional simulations rel- ative to PSRO, it has shown to be a simple yet effective extension to the current SOTA. We tested our approach in two benchmark environments: a sequential social dilemma game and a game of bargaining over resource division.
Cheng, R., Verma, A., Orosz, G., Chaudhuri, S., Yue, Y., and Burdick, J. Control regularization for reduced variance reinforcement learning. In 36th International Conference on Machine Learning, pp. 1141-11 150, 2019.
Christodoulou, P. Soft actor-critic for discrete action settings. arXiv preprint A9
2019.
Colas, C., Sigaud, O., and Oudeyer, P.-Y. A hitchhiker's guide to statistical comparisons of reinforcement learning algorithms. In 2019 Workshop on Reproducibility in Machine Learning. 2019.
Haarnoja, T., Zhou, A., Hartikainen, K., Tucker, G., Ha, S., Tan, J., Kumar, V., Zhu, H., Gupta, A., Abbeel, P., et al. Soft actor-critic algorithms and applications. arXiv preprint arXiv: 2018
Our experiments show that EXPPSRO tends to improve equi- librium welfare across all benchmarks. By varying the explo- ration policy, we show that EXROSs''s performance hinges not only on its added regularization but also its choice of regularizing behavior. In our experiments, EXPP most consistently discovers lewer-regret, welfer solutions quicker than its vanilla counterpart and other exploration policy alternatives. These findings suggest that EXRO
Jordan, P. R., Schvartzman, L. J., and Wellman, M. P. Strat- egy exploration in empirical games. In 9th International Conference on Autonomous Agents and Multiagent Sys- tems, pp. 1131-1138, 1138, 2010.

---

Explicit Exploration for High-Welfare Equilibria in Game-Theorete Multiagent Reinforcement Learning
Kostrikov, I., Fergus, R., Tompson, J., and Nachum, O. Offline reinforcement learning with Fisher divergence critic regularization. In 38th International Conference Machine Learning, Pp. 3774-5783. 2021.
Pérolat, J., Munos, R., Lespiau, J., Omidshafiei, S., Row- land, M., Ortega, P. A., Burch, N., Anthony, T. W. Bal- duzzi, D., Vylder, B. D., Piliouras, G., Lanctot, M., and Tuyls, K. From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In 38th International Conference on Ma- chine Learning, pp. 8525-8535, 2021.
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., and Graepel, uni- fied same-theoretic approach to multiagent reinforcement learning. In st Annual Conference on Neural Informa- tion Processing Systems, pp. 4190-4203, 2017.
Rashid, T., Samvelyan, M.. De Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, Monotonic value function factorisation for deep multi-agent reinforcement learning, Journal of Machine Learning Research, 21(178):1-51, 2020.
Lanctot, M., Lockhart, F.,, Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J.. Srinivasan, S., Timbers, F., Tuyls, K., Omidshafiei, S., et al. Openspiel: frame- work for reinforcement learning in games. arXiv preprint arXiv: /908. 09450,944333 2019.
Roy, J., Barde, P., Harvey, F., Nowrouzezahraii D., and Pal, C. Promoting coordination through policy regulariza- tion in multi-agent deep reinforcement learning. In 34th Annual Conference on Neural Information Processing Systems, pp. 15774-15785, 2020.
Lewis, M., Yarats, D., Dauphin, Y. N.N., Parikh, D., and Batra, D. Deal or no deal? End-to-end learning for negotiation dialogues. In 2017 Conference on Empirical Methods in Natural Language Processing, pp. -453,, 2017.
Rudner, T. G. J., Lu, C., Osborne, M. A., Gal, Y., and Tch, Y. On pathologies in KL-regularized reinforcement learning from expert demonstrations. In 35th Annual Conference on Neural Information Processing Systems, pp. 28376- 28389, 2021.
Liu, Z.,, Yu, C., Yang, Y., Wu, Z., Li, Y., et al. A unified diversity measure for multiagent reinforcement learning. In 36th Annual Conference on Neural Information Pro- cessing Systems, pp. 10339-10352, 2022.
Su, K. and Lu, Z. Divergence-regularize multi-agent actor- critic. In 39th International Conference on Machine Learning, pp. 20580-20603 2022.
Lowe, R., WU, I.I. Tamar, A., Harb, J., Abbeel, P., and Mor- datch, Multi Multi-agent actor-critic for mixed cooperative- competitive environments. In 31 Annual Conference on Neural Information Processing Systems, pp. 6382-6393, 2017.
Taylor, P. D. and Jonker, L. B. Evolutionary stable strategies and game dynamics. Mathematical Biosciences, 40(1-2) 145-156, 1978.
McMahan, H. B., Gordon, G. J., and Blum, A. Planning in the presence of cost functions controlled by an adversary. In 20th International Conference on Machine Learning, pp. 536-543, 2003.
Wang. Y. and Wellman, M. P. Regularization for strategy exploration in empirical game-theoretic analysis. arXiv preprint arXiv:2302.04992 2023.
Oh, J., Guo, Y., Singh, S., and Lee, H. Self-imitation learn- ing. In 35th International Conference on Machine Learn- ing, pp. 3878-3887, 2018.
Wang. Y. and Wellman, M. P. Generalized response objectives for strategy exploration in empirical game- theoretic analysis. In 23rd International Conference on Autonomous Agents and Multi-Agent Systems, pp. 1892- 1900, 2024.
Parker-Holder, J., Pacchiano, A., Choromanski, K. M., and Roberts, S. J. Effective diversity population based rein- forcement learning. In 34th Annual Conference on Neural Information Processing Systems, pp. 18050-18062, 2020.
Wang. Y., Ma, Q., and Wellman, M. P. Evaluating strat- egy exploration in empirical game-theoreeic analysis. In / International Conference on Autonomous Agents and Multi-Agent Systems, pp. 1346-1354, 2022.
Perez-Nieves, N., Yang, Y., Slumbers, O., Mguni, D. H., Wen, Y., and Wang, Modelling behavioural diversity for learning in open-ended games. In 38th International Conference on Machine Learning, pp. 8514-8524, 2021.
Wellman, M. P., Tuyls, K., and Greenwald, A. Empirical game-theoretic analysis: A survey. Journal of Artificial Intelligence Research, 82:503-562, 2025.
Perolat, J., Leibo, J. Z.,, Zambaldi, V., Beattie, C., Tuyls, K., and Graepel, T. A multi-agent reinforcement learning model of common-por pool resource appropriation. In 3/st Annual Conference on Neural Information Processing Systems, pp. 3646-3655, 2017.
Wu, Y., Tucker, G., and Nachum, O. Behavior regu- larized offline reinforcement learning. arXiv preprint M.Vv:/9/1.11300 2019.
10

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
Xu, H., Zhan, X., Li, J., and Yin, H. Offline reinforcement learning with soft behavior regularization. In NeurlPS-2/ Workshop Offline Reinforcement Learning, 2021.
Zhou, H., Lin, Z., Li, J., Ye, D., Fu, Q. and Yang, W. Revisiting discrete soft actor-critic. arXiv preprint 100001, 2022.

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
A. Hyperparameters
All Soft Actor-Critic (SAC) parameters considered and chosen for each environment are shown Table The top section lists parameters held fixed while the bottom lists parameters included in the parameter search. These chosen hyperparameters were common across vanilla PSRO, Ex PSRO, and Ablation-Tee::
Table 2. Soft-Actor Critic Parameter Scarch
Parameter
Candidates
Harvest
Bargaining
Network Depth
[2]
Activation
[RcLU]
ReLU
ReLU
Discount Factor
[.99]
.99
.99
Gradient Steps Update
[1]
BC Epochs
[50]
50
50
BC Learning Rate
[3e-4]
3e-4
3e-4
BC Batch Size
[256]
256
256
BC Network Depth
[2]
BC Network Width
[Match Network Width]
50
100
BC Entropy Threshold
None
.2
.8
Max Trajectory Buffer Size
None
1000
100,000
Entropy Temperature (a:
[0, 1e-3, 3e-3, Ie-2, 3c-2, le-1]
3e-2
le-1
Value Epsilon Clip (r2)
[.2 .5 1.0 2.0]
.2
.2
Update Every (P)
[1, 2. 5, 10]
Number of Training Steps (S)
[100K, 500K, 1M 2M 3M 4M]
2M
100K
Policy Learning Rate (Ap)
[ße-5, lc-4, 3e-4]
3c-5
3e-5
Value Learning Rate (he)
[3e-5, le-4, 3e-4]
le-4
3e-4
Max Buffer Size (B)
[50K 100K 200K 500K]
100K
50K
Network Width (W)
[50 100 250]
50
100
Batch Size (b)
[32, 64]
64
64
We divided the parameter search for SAC hyperparameters into three phases, each of which advanced a subset of parameters the next. The first parameter search was over figh-priority parameters that we believed would highly influence performance. The second search was over lower-priority parameters that we believed were important when fine-tuning tne-tunnng policies. The evaluation of policy in rounds and 2 was dictated by the average final policy returns across 3 trials when responding to uniform action policy. In round 3, we compared performance between the strongest configurations determined from the previous two rounds, averaging across trials responding to uniform mixture of policies. The policy mixture was generated by five iterations of PSRO using SAC parameters from one of the parameter candidates in round 3. If parameter configurations resulted in similar performance, configurations with less computational cost were favored. These details are summarized in Table
Table 3. Hyperparameter Tuning Procedure Summary
Round Parameters
Trials
Response Target
a, Cv. P.
3
πe (AA)
Xn, Ay, B, W.b
3
Tg = U(A)
All finalists
5
σ = U
Table 2 also includes some parameters for Ex²PSRO, specifically behavior cloning parameters and trajectory buffer size. These parameters were not included in the search, the latter of which was chosen based on initial empirical results. Future work could be dedicated to determining how trajectory buffer size affects EX2PSRO's performance.
In Table 5, we show the PSRO and Ex PSRR regularization-reltte hyperparameters used to generate the welfare values in Fig. 5, where the candidate hyperparameters search over are shown in Tables 8. The number of steps to anneal exploration regularization S3 was held fixed 25. The 2X2PSRO parameter search was conducted over two parameters: RRD
12

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
regularization λ and initial exploration regularization 8iat- Ex²PSRO parameters selected by conducting 5 trials for each parameter configuration. For each environment, the setting yielding equilibria with the highest welfare chosen and given an additional 5 trials to produce the results in Fig. 5. Vanilla PSRO was tuned across only À as it does not include exploration regularization. Each À was given 10 trials and we immediately report data from the best- parameter setting in Fig. 5.
A.1. Generalized Response Objectives
GRO optimizes a modified response objective at each iteration of PSRO. Our experiments optimized social welfare, where the resultant policy optimizes the following, with slight notation changes:
T Cary + (1 - a)r, = arg max JGRO
T = arg max Folk
where superscript p and -p indicate rewards assigned to player p and all others except p. respectively, and is a hyper- parameter. We selected a .8 justified by the original work (Wang & Wellman, 2024). When combining GRO and EX²PSRO, behavior regularization was also applied, meaning the aggregate optimization the following:
T = arg
To
Experiments combining GRO and EX²PSRO were not tuned across hyperparameters. Ex²PSRO's Binit was fixed to .01 and was fixed 5 and 5 in both Bargaining and Harvest variants, respectively.
Table 4. Ex vs. Ablation-Ter
Name
Criterion
Exploration Policy
EX?PSRO
Eq. 2
Eq. 3
Ablation-Ter
Uniform
N/A
U(4)
MinWelfare
Σp VP
Eq. 3
Max Welfare
E, VP
Eq.
PrevBR
N/A
f-1
Table S. Vanilla PSRO and Ex EXPP Parameter Summary
Game
Parameter
PSRO
Ex²
RRD (A)
Harvest-Dent
Bess
le-2
RRD (A)
2
5
Harvest-Sparse
Benst
le-2
RRD (X)
.1
.2
Bargaining .99
Bait
3e-4
RRD (A)
55
.5
Bargaining 7 .95
Benst
le-2
B. Behavior Cloning
Exploration policies - at each iteration are trained using behavior cloning (BC) on a trajectory buffer that consists of trajectories maximizing criterion C(Ty) as noted in Eq. 2. The training of exploration policy n² be executed
13

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
immediately before training responses zh at each iteration i.
The full behavior cloning algorithm is shown in Algorithm 2, where we train multilayer perceptron (ReLU activations) with softmax output layer using cross-entropy loss. Batch sizes, number of epochs, size of trajectory buffer B, and learning rates are enumerated in Table 2. We insert an early stopping criterion (called "BC Entropy Threshold" in Table 2) to avoid divide-by-near-zerro errors when calculating the regularization term in Equation 5.
Algorithm 2 Create Exploration Policy with Behavior Cloning
Inputs: Trajectory data B, Epochs E, Minibatch size M, learning rate a, model shape S
Outputs: Exploration policy Taz parameterized by 6'...
Initialize deep model Te. of shape S and parameters 6
2: Create dataloader DD using data B of minibatch size M
3: for E' epochs do
4: for each minibatch (ox, ai.) in D do
5: J( C 0x)
6: 0 = 0x 2.
7: end for
8: Shuffle and rebatch dataloader
9: end for
10: return n
C. Environment Details
C.1. Harvest Details
Each space in the Harvest (Perolat al., 2017) grid-world characterized by one of four states: empty, wall, apple, or a player. Apples are only able to reside in dedicated locations. Players initially spawn randomly in one of the four corners. The grid worlds are shown in Fig. 9.
A player's observation is defined by their position and orientation. In this implementation, agents observe rectangular viewing box of 7 spaces forward and 3 to the left and right, both of which include their position. The vectorized state input to policy neural network xy is created by unraveling the viewing box into a length 21 tensor, creating indicator tensors for each of the possible space states (empty, wall, apple, player). These tensors are then concatenated to create an aggregate length 84 tensor. The player tensor has value of 11 to refer itself, for other players, and 0 for spaces without other players.
At each time step, players take actions simultaneously, where each can take one of eight actions: {left, right, forward, backward, turn clockwise, turn counter-clockwiee laser, no operation). The first four change the player's location by moving relative to their orientation. The next two modify their orientation. The "laser" action fires a beam that spans the player's 's viewing box (3x7) and removes hit players from the game for 25 time steps.
an apple spawn location empty (no player and no apple), an apple respawns with probability proportional to the number of apples within 2 units of Euclidean distance. Table summarizes these respawn probabilities. An episode terminates when either there are no apples on the map 1000 time steps are reached.
We construct two variants of the Harvest game, which we term Harvest-Denss and Harvest-Sparse. The former's map is densely populated with apples and has initial spawn points that are close to the players' spawn points. The latter's s map consists of a central trove of apples, forcing players to interact with each other in the middle. Harvest-Sparse can be considered a more challenging variant than Harvest-Dema as the central allocation and decreased presence of apples make coordination more important for high welfare.
Table 6. Harvest Respawn Probabilities
Apples in Vicinity (2 units)
2
> 3
Respawn Probability
0.000
.005
.020
.050
14

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoree Multiagent Reinforcement Learning
P
P
P
A
A
P
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
P
P
P
A
A
A
P
Figure Diagrams of Harvest Sparse Harvest Dense environments, Blue and green tiles indicate where players apples can spawn, respectively. Gray tiles are walls and yellow tiles are empty.
C.2. Bargaining Details
The objective in Bargaining (Lewis et al., 2017) is for players to divide up the items so that all items are owned by one of the 2 players. Each player's random, private value function (assigns non-negative utility value to each of the items) is constrained such that: (1) the sum the utility values of all items the same for both players (i.e., the individual values per item may be different between users but the sum of the items' utilities the same for both players); (2) each item has non-zero value for least one user; and (3) some items have non-zero value for both users. The game starts by having one player offer certain division of assets.* The other player can either accept the offer decline and present counteroffer. This process continues until all assets have been divided or turn limit has been reached. Both players receive utility if no agreement is reached by the turn limit. In our implementation, the total turn limit is 10, which includes moves by both players. Received utilities are discounted after each iteration by y. Smaller leads players to strategize more myopically, focusing on shorter-tern gains rather than long-term. This changes game dynamics dramatically as players may prioritize making deals in less time-steps at the cost of potentially higher-welfare yielding division of assets. Our implementation sets y = and 7 .95. This prevents players from foreing ultimatums at the last iteration, relatively degenerate version of the game. We adapt implementation provided by OpenSpiel to establish symmetry between players by having players sample from the same pool of valuations and determining the starting player by coin flip. We defer further implementation details to Deepmind's OpenSpiel repository (Lanctot al., 2019).
D. Welfare Distributions and Significance Tests
underscore that welfare improvement should be measured relative to distribution of welfare values available equilirria in each game. To that end, raw welfare values are not as valuable to examine. For example, suppose game contains equilibria whose welfare values all lie within [1000, 1005). While an improvement from 1000 1004 may not seem large relative to the raw welfare scores, it is large relative to the distribution of equilibria welfare.
Calculation of this actual distribution is infeasible, as it depends on finding all equilibria. To capture the proportions relative to what we can compute, for Fig. 5 we scale the y-axis to cover the inner 68% points we found across all runs of each game. This is done to encourage analysis with respect to the welfare distribution in the game, but we do not claim that our data samples accurately reflect the distribution of available equilibria. Fig. provides significance tests comparing all pairs of tested approaches listed Fig. 5.
*The starting player is determined by a coin flip, establishing symmetry the game.
15

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
Table All P-values Welch's t-test, verifying whether the approaches listed in the outperform those in the column in the listed
game benchmark.
Harvest-Dent
Vanilla
Ex PSRO
Uniform
Min Welfare
Max Welfaee
PrevBR
Vanilla
N/A
1.00
1.00
1.00
1.00
1.00
EXPPSRO
4e-8
N/A
.131
.052
.009
le-6
Uniform
4e-7
.869
N/A
.269
.118
le-5
Min Welfare
5e-6
.948
.731
N/A
.340
2e-4
Max Welfare
4e-8
.991
.882
.660
N/A
le-5
PrevBR
6e-5
1.00
1.00
1.00
1.00
N/A
Harvest- Sparse
Vanilla
EXRP
Uniform
Min Welfare
Max Welfare
PrevBR
Vanilla
N/A
1.00
1.00
1.00
1.00
1.00
ExPPSRO
le-5
N/A
.243
.018
.321
.054
Uniform
3e-5
.757
N/A
.043
.575
.139
MinWelfare
8e-3
.922
.957
N/A
.961
.806
Max Welfare
4e-5
.679
.425
.039
N/A
.123
PrevBR
3e-4
946
.860
.194
.877
N/A
Bargaining 7 = .99
Vanilla
PSRR
Uniform
Min Welfare
Max Welfare
PrevBR
Vanilla
N/A
.958
.481
.737
.048
.558
EX²PSRO
.042
N/A
.006
.045
le-4
.012
Uniform
.19
.994
N/A
.829
.017
.605
Min Welfare
.263
.955
.171
N/A
.002
.247
Max Welfare
.952
1.00
.983
.998
N/A
.990
PrevBR
442
.988
.395
.753
.010
N/A
Bargaining Y .95
Vanilla
EXPPSRO
Uniform
MinWelfare
Max Welfare
PrevBR
Vanilla
N/A
.970
.398
.080
.644
.119
EXPPSRO
.030
N/A
.016
.011
.080
.003
Uniform
.602
.984
N/A
.103
.719
.171
Min Welfare
.920
.999
.897
N/A
.938
.748
Max Welfare
336
862
.281
.062
N/A
.092
PrevBR
.881
.997
.829
.252
.908
N/A
E. Compute Resources
Experiments were run on the University Michigan's 's research computing cluster. We summarize computational resources allocated Harvest and Bargaining variants. Using a CPU, each PSRO, EX"PSRO, and Ablation- run took anywhere between and 4 days to finish as there were total of 30 RL policies being trained in sequence. Ex²PSRO variants required roughly 8-12 GB of RAM support trajectory buffer storage, which could be reduced through code changes allowing with 5 GB of RAM while Ex EXPPSRO and Ablation-
disk storage. Vanilla PSRO of RAM. Additional computation was allocated for regret calculations, elaborated in App. G, which took an additional 3-4 days and GB of RAM. For each game variant, experiments included 40 vanilla PSRO runs (tuning across X), 105 Ex PSRO runs (100 for tuning across (A, Bins), 5 for the finalist) and 40 Ablation-TT... runs (10 for each variant), totaling 185 runs per game. With benchmarks, a total of 740 trials were conducted throughout, each requiring the aforementioned compute.
with 12-15 GB
16

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
F. Trajectory Buffer Sharing
key part of the EX²PSRO algorithm is the trajectory buffer, which leverages simulation data generated during the PSRO process to guide the algorithm towards discovering higler-welfare equilibrium. This approach attributes additional value to trajectory data that would otherwise be discarded in vanilla PSRO after response training. Here, we discuss the assumption that trajectories are shared across players.
We emphasize that a shared trajectory buffer does not change the underlying nature of the game. Crucially, EXPP still enforces that players only have access to their own information when making decisions. EX²PSRO's 's design is to be interpreted from the perspective of game analyst: EX²PSRO is used to discover equilibria, not reflect how players would develop or change their strategies over time to arrive at an equílibrium. More concretely, access to shared trajectory buffer used aid algorithmic discovery of higher-welfare equilibria, not advocating that players in the real world would have access to such a buffer for strategy generation.
G. Estimating True Regret
Let Uy and Iy be the un-regularized and regularized sets of strategies, respectively, at the end of PSRO trial where T is the total number of PSRO iterations. Note that for vanilla PSRO, I1, = 0 and for EX²PSRO, [1I] = T - Sg and | = S3. To ensure Ex² EXRP was rigorously evaluated, we augment Ex PSRO's Hy after each full run by training unnregularized best responses x for each profile of for which a regularized response TiJ IT was created. We estimate the true game regret as the max deviation gain from the iteration's 's profile where we consider strategies in πy U IT and lower-bound the estimate by 0:
Regret(o")= rell,Ull,,
max
-
(8)
All utilities are estimated empirically using fixed number of simulations. We note that for EX"PSRO, I1l -1 SB while for vanilla PSRO, IIr U JI T. Ex2PSRO's ' regret evaluation set includes T non-regularized responses (just like vanilla PSRO) but contains an additional S regularized responses. This discrepancy makes 2 regret calculations more thorough than that of vanilla PSRO, meaning vanilla PSRO's regret has a higher chance of being underestimated than EXRPSRO. In other words, vanilla PSRO given an "advantage" terms of regret calculations. Despite this, regret values for Ex EXRP are equal to, arguably lower than, vanilla PSRO's all benchmarks shown in $5.6. Trials in Ablation- Tex not given non-regularized responses, meaning Iy and reported regret for Ablation- ez trials similarly have higher chances of being underestimated.
H. Additional Results
Regret Over lterations: Harvest Sparse
Regret Over Iterations: Harvest Dense
100
Vesille
Weills
ExPPSRO
BxceRRo
MaxWelfare
MaxWerfree
80
Minttelfaree
MinWelfare
Previnn
Prevtin
Uniform
Pegres
40
20
35
Bereaion
RCc aeration
Figure 10. Non-truncated version of regret trends for Harvest-Sparse and Harvest-Dense.
17

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
H.1. Regret and Welfare
We provide un-truncated versions of the plots provided in the main paper Fig. 10. Table 8 summarizes welfare metrics in Harvest and Bargaining during hyperparameter tuning. Underlined entries correspond to metrics that averaged over 10 trials. All other entries are averaged over 5. Bolded metrics indicate the strongest- configuration given A. These tables correspond to the hyperparameter tuning mentioned in Table 5. Vanilla PSRO metrics are each averaged over 10 trials and the final metrics correspond to the best-performing vanilla PSRO parameter configuration. EXRO metrics are averaged over 5 trials except for the chosen hyperparameter configuration,, which is then given additional trials for a total of 10. We reiterate that this parameter tuning procedure is conservative, as Ex PSRO's tuning process is susceptible to high variance and may neglect to choose parameter setting that would have yielded even stronger performance.
Table 8. Welfare Tuning
Harvest-Sparse
Beis
À = 0
À 2
À =
À A= 10
le-4
102.36 + 7.53
96.85 + 6.21
108.58 + 6.77
(01.27
3e-4
104.14 12.45
112.39 + 4.11
107.54 8.47
118.39 5.37
le-3
117.81 + 13.90
110.35 + 12.64
+ 11.07+2..4
113.00 10.98
36-3
116.35 + 4.28
112.18 + 6.73
116.94
115.68 4.60
le-2
113.77 6.99
122.18 3.42
120.84 10.44
Vanilla
103.80 + 5.85
108.57 + 8.95
106.48 + 8.83
106.60 + 4.88
Harvest-
le-4
117.88 + 4.89
1
126.91 + 2.76
121.52 + 5.57
3e-4
123.05 5.74
121.30 + 5.66
125.46 + 8.52
126.10 + 7.39
1o-3
220.96
127.27 4.06
127.15 + 2.70
125.97 + 3.13
3e-3
134.73 4.90
136.28 + 12.36
138.82 + 6.03
140.74 = 8.09
le-2
141.46 6.30
137.81 4.14
150.22 + 7.86
137.61 3.28
Vanilla
118.98 5.67
117.38 2.30
118.36 + 7.81
119.57 3.35
Bargaining ? .99
Sinit
À ==0 0
X = .1
X 22
.5
le-4
12.37 + 0.10
12.23 + 0.58
12.57 0.12
12.67 + 0.56
3e-4
0.28
11.82 + 0.48
12.86 + 0.26
12.48 + 0.16
le-3
12.15 = 0.64
12.34 + 0.24
12.75 + 0.15
12.33 + 0.42
3e-3
12.27 = 0.23
12.63 + 0.36
12.63 + 0.13
12.72 = 0.36
le-2
12.55 0.24
12.66 0.13
12.55 + 0.34
12.66 + 0.20
Vanilla
11.95 + 0.66
12.50 + 0.55
12.34 + 0.28
12.40 + 0.21
Bargaining 7 .95
le-4
12.54 0.22
12.83 + 0.42
13.41 + 0.28
13.82 + 0.20
3e-4
13.14 + 0.37
13.31 + 0.41
12.28 + 1.08
13.74 + 0.14
le-3
12.83 + 0.16
13.46 + 0.36
13.22 + 0.29
12.74 + 0.71
3e-3
12.51 + 1.05
13.76 0.14
13.49 + 0.32
13.32 0.29
le-2
13.23 0.12
12.78 0.23
13.82 + 0.37
14.02 0.22
Vanilla
12.85 + 0.38
12.80 + 0.39
13.25 + 0.56
13.76 + 0.34
H.2. Hyperparameter Ablation
We next analyze the effect of Benit and on Ex 2PSR's performance. We conduct ablation tests in Bargaining .99 and Harvest-Sparse We fix one the parameters and vary the other for both environments. Bargaining y = .99 fixes A = .2 and Bysit = 3e-4 while Sarvest-Sparse fixes X = 5 and Bynst = 1e-2. Fig. 11 displays the regret and welfare trends over iterations, where we vary either À or Binit-
18

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretic Multiagent Reinforcement Learning
In Harvest-Sparse, results indicate that increased regularization correlates with higher-welfare equilibria. In particular, greater regularization seems reduce how steeply welfare initially dips, characteristic common across all trials. We posit that this arises because higher regularization encourages more coordinated abstinence from over-harvesting apples. This relationship between regularization and welfare supports that Ex EX²PSRO, through Smatt has some control over the welfare of its solutions, an equilibrium selection mechanism not previously available in vanilla PSRO. In Bargaining 7 .99, relationships between regret, welfare, and tested parameters are relatively unclear. We leave future work to ascertain any correlations between these values.
19

---

Explicit Exploration for High-Welfare Equilibria in Game-Theoretis Multiagent Reinforcement Learning
Segret henaisss Earpahirgy. 50
Experted Over terationt Bargaining
35-
Regret hertisss Eargahingy- y- 59
Ecsented t Over terations Barganing y-
beniions: Hanvest
Cxpecter laanest
tentions laavess Sporte
31.
300
130
02
Dopectec
Regrst
03
4
15
Figure 11. Ablation tests for Ex PSRO in Harvest Sparse and Bargaining = .99, varying À or Binit and fixing the other parameter. We analyze both welfare regret trends over iterations, displaying the data iterations. omit standard deviation lines for clarity.
20


Reviews:
[{"review_id": "nxxnqRxZ5B", "reviewer": "Reviewer_uMdQ", "summary": "This paper proposes the Ex2PSRO algorithm, which introduces an explicit exploration mechanism into the PSRO framework to optimize equilibrium social welfare. Specifically, the method constructs exploration policies through behavior cloning on high-welfare trajectories and guides policy optimization via KL-divergence regularization. Experimental results demonstrate that Ex2PSRO significantly improves social welfare and can be combined with existing methods to further enhance performance. This is the first equilibrium selection approach that integrates policy regularization with trajectory imitation without incurring additional simulation costs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive comments and feedback. We would like to clarify that Ex2PSRO is not inherently limited to symmetric games—any more than PSRO is. The methods work for non-symmetric games simply by performing strategy generation for each player separately. Assuming symmetry for this paper simplifies the notation and algorithm description, and also the presentation of experimental results (avoiding the need to show payoffs or regret for each player). The only minor twist for Ex2PSRO (as noted in Footnote 2) is that we would need to account for possible difference in utility scales across players in our criterion for trajectory selection. What we suggest is replacing raw utilities in the criterion with percentiles, measured by using the trajectory buffer as an empirical estimate of return distribution. (Interpreting welfare can also be more complicated in general for non-symmetric games, regardless of method used.)\n\nIn fact, a natural description of the bargaining game is non-symmetric, between the first-moving and second-moving player. We make this symmetric ex ante by having the players flip a coin to determine who offers first. But note that our solution to this symmetric version actually contains a solution to the non-symmetric one, since our players’ policies have to cover the cases where they move first or second.\n\nQuestion 1: To clarify: the y-axis in Fig. 4 does show unnormalized welfare. The use of “middle 68% of welfare found across all trials” is just to decide the visual scaling (i.e, the axis range) in the plots. We elaborate our rationale in Appendix D. As noted there, we would like to calibrate this to the range of game equilibria. The actual range or distribution of these is not known for Harvest or Bargaining instances, and not apparently feasible to compute. So actually, the welfare results “found across all trials” (each in an approximate equilibrium) is our best available estimate of this equilibrium distribution.", "claims_and_evidence": "The central claim is well-supported: Significant welfare gains validated by statistical significance testing and ablation studies.", "methods_and_evaluation_criteria": "Appropriate methodology leverages PSRO's iterative structure with KL regularization for directional exploration. Welfare and regret metrics effectively capture performance.", "theoretical_claims": "Theoretical claims are well-supported, convergence is shown via regret trends, and KL regularization aligns with imitation learning theory, validated experimentally.", "experimental_designs_or_analyses": "Comprehensive experiments include baseline comparisons, ablation studies, and composition tests. Statistical rigor maintained through parameter control and repeated trials.", "relation_to_broader_scientific_literature": "Well-connected: Builds on PSRO and GRO. Policy regularization adapts offline RL to equilibrium selection. FPDE could be cited but differs in focus.", "essential_references_not_discussed": "No critical omissions.", "other_strengths_and_weaknesses": "Strengths:\nInnovative cross-method integration: First combination of policy regularization with trajectory behavior imitation, adapting behavior cloning techniques from offline RL to equilibrium selection scenarios through KL divergence.\nZero additional simulation cost: Exploration policies are entirely based on historical trajectory filtering, requiring no extra environmental interactions.\nModular design: Seamlessly combinable with existing methods like GRO through insertion of regularization terms (Table 1), demonstrating method versatility.\n\nWeaknesses:\nSymmetric game dependency: Experiments validated only on symmetric games (§2 terminology), requiring additional trajectory filtering criteria design for asymmetric scenarios, limiting generalizability.\nHyperparameter sensitivity: Requires grid search for initial regularization strength β_init and annealing steps Sβ, increasing parameter tuning difficulty in real-world deployment.", "other_comments_or_suggestions": "There are no more comments and suggestions.", "questions_for_authors": "The bar graph in Figure 4 normalizes welfare values to \"the middle 68% of welfare found across all trials,\" but the rationale for this choice is unclear. Why not use absolute welfare or percentiles relative to known game equilibria?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xYHHQ0GgyM", "reviewer": "Reviewer_isKQ", "summary": "The authors propose EX2PSRO, which extends PSRO to encourage finding maximum welfare solutions. A regularization target policy is trained by behavior cloning high minimum welfare trajectories collected during best-response training. This policy then acts as a regularizer during SAC best response training, encouraging similar behavior to it.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful comments and feedback. We agree that any evaluation could benefit from additional benchmarks. However, we believe the four benchmarks (two qualitatively distinct variants on two very different games) cover a very informative range of cases. The artificial MDP example also provides insight. Ex2PSRO’s evaluation was comprehensive and prioritized thoroughness over breadth, including detail analysis of all four benchmarks with varied exploration policies as well as consideration of generalized response objectives (GRO). \n\nRegarding Ex2PSRO’s scale of improvements, we believe that Fig. 4 shows the magnitude of these in a meaningful way (see our response to Q1 of reviewer uMdQ regarding this figure). That is, Ex2PSRO generates substantial welfare improvements relative to the empirically estimated distribution of equilibria. These improvements are statistically robust, as indicated by low p-values. It is true that we employ extensive hyperparameter tuning, but, as described in Appendix H.1, we exhaustively tune the vanilla baseline but conservatively tune Ex2PSRO, meaning a stronger parameter setting may not have been identified for the latter.\n\nRegarding theoretical convergence, please refer to our response to reviewer Rgj4.\n\nQ1: The minimum of summed rewards is a non-linear objective and cannot be optimized with standard RL methods. Furthermore, online optimization would incur additional simulation expense, while offline RL algorithms are known for their relative instability, which would be exacerbated in large games.\n\nQ2: The exploration strategy pi_ex itself is usually not very good overall, even though it contains useful ingredients for an effective policy. Thus, adding it to the empirical game would not change the equilibrium, and so would not influence the trajectory of PSRO at all. We did try this in preliminary experiments and confirmed its ineffectiveness. We agree this is worth noting in the paper.", "claims_and_evidence": "The authors claim that EX2PSRO finds higher-welfare equilibria with lower regret. \n\nThe welfare improvements are demonstrated only on two domains (Harvest and Bargaining), which limits the generality of the claims.\n\nAdditionally, many of the performance improvements are fairly subtle, which in combination with the small amount of domains, makes it difficult to tell how much of the improvements are from extensive hyperparameter tuning, etc.", "methods_and_evaluation_criteria": "The EX2PSRO method proposed is intuitive and clear as an extension to PSRO. Likewise, the domains tested on are also appropriate. Welfare and regret as the primary metrics are sensible for the problem setting.", "theoretical_claims": "The theoretical justification for using behavior cloning to steer exploration is largely heuristic, and there are no formal results guaranteeing that the addition of the regularization term will lead to an improvement in welfare.", "experimental_designs_or_analyses": "The experimental design is sound overall, though it is disappointing how much of an effect hyperparameter tuning has on EX2PSRO and thus is required for the reported positive results.", "relation_to_broader_scientific_literature": "This paper builds on PSRO by adding a regularizing term to try to shape the equilibrium that PSRO finds.", "essential_references_not_discussed": "There are no key missing references that I can discern.", "other_strengths_and_weaknesses": "Strengths:\n- The proposed approach is straightforward to implement as an extension to PSRO.\n- The authors confirm an improvement to welfare in the domains tested.\n\nWeaknesses:\n- The method lacks any theoretical guarantees, and is sensitive to hyperparameters.\n- Only two domains (each with two variations) are tested.", "other_comments_or_suggestions": "Figure 5 is confusing without axis labels. I'm assuming Regret is the x-axis, making EX2PSRO perform well compared to other methods.", "questions_for_authors": "To generate the exploration policy to be used as a regularizer, why not directly optimize something like $\\min_p \\sum^{|T|}_{t=1}r^p_t$ with reinforcement learning (offline or online)? Would this not be preferable to behavior cloning because you could then generate novel trajectories with the exploration policy that maximize welfare?\n\nWhy do you not add $\\pi_{ex}^i$ to the empirical game? Would it hurt the solution?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "I have no ethical concerns for this paper."}}, {"review_id": "MvKDvRpVzr", "reviewer": "Reviewer_yU4Z", "summary": "Multi agent RL environments are getting more and more relevant. In many environments in order for solving very different tasks in the real world multiple agents are going to collaborate and solve a task. However, discovering NEs with high social welfare is hard with current RL algorithms. Even more so, discovering a diverse set of policies for these agents are hard. If we update all the models at the same time, the agents may lead to suboptimal behaviour or converging to defect defect NEs in social dilemmas. This is known since the LOLA paper which shows naive RL even fails in the very simple IPD game. Achieving a diverse set of policies is specifically hard as most of the time the diversity of the policies in a population collapses quickly. This can also lead the agents far from some high social welfare NEs as the behaviour goes extinct in the population before it gets the chance to be picked up by the RL signal. While methods like PSRO, suggest training best responses to the population and adding that best response iteratively is a nice way to achieve diversity but that does not maintain enough diversity in the population for some tasks and does not discover high social welfare policies. \n\nThis paper suggests a simple approach to this problem.  They filter out the trajectories that look promising based on a criterion, and then add another loss on the best response training loss to resemble also those filtered trajectories. It can be seen as guiding the search for best response to also explore promising training directions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the insightful comments and feedback. We agree that improvements should be appropriately contextualized to determine improvement magnitude. Please refer to our answer to Q1 of reviewer uMdQ: our bar graph visual range is normalized according to an available distribution of equilibria. We don’t know the highest welfare equilibria of these games with certainty, but our experimental experience gives us reasonable evidence of the range. These bar graphs, coupled with significance tests, show that Ex2PSRO substantially outperforms vanilla PSRO considering known equilibria. \n\nWe agree that exploration policy choice is vital to performance. We are not sure what the reviewer means in wondering what happens in a “mixed environment”. Our environments are all mixed in the sense of being neither completely adversarial nor common-interest. \n\nWe agree with the points raised regarding additional hyperparameter search discussions and key references.\n\nQ1: Yes, Harvest generally has welfares ranging from approximately 0 and 200 while Bargaining ranges between 0 and 16.  However, as discussed above, it is more valuable to measure improvements relative to the welfare attainable in equilibrium as opposed to all possible joint policies. \nQ2: We agree that the choice of exploration policy is essential to performance. Analogous to exploration in RL, we work under the assumption that we do not know which exploration mechanisms would be effective. Otherwise, exploration would not be an issue. Our experiments demonstrate that mining experience for clues is beneficial, examine several heuristic possibilities, and validate Ex2PSRO’s MaxMin heuristic works best in practice.\nQ3: Yes, the reason is that simple matrix games are defined in terms of atomic policies and so do not provide the opportunity to exploit clues from examining constituent components of policies. The key idea of Ex2PSRO is to mine trajectory traces for policy ideas, and this could not apply in a matrix game. (Matrix games also have no use for deep RL  for strategy generation, which is a defining characteristic of vanilla PSRO.)", "claims_and_evidence": "The claim is: by adding a small incentive to preserve the filtered trajectories that pass a criterion, we can incentivize better exploration. At the end, it should lead to discovery of higher social welfare NEs. \n\nEvidence: They show results on Harvest Dense and Harvest Sparse and the bargaining game. The results are not dramatic but better than the baseline. \n\nMy concern: What is the highest possible NE in the bargaining games and the harvest games? The problem is I cannot contextualize the results by the numbers as I don't know what is the ceiling for the number and the increase itself does not look dramatic in the games. When the increases are not dramatic, minor concerns become important like whether enough seeds were used or the hyperparameters were carefully tuned.", "methods_and_evaluation_criteria": "I think the evaluation makes sense. However, I wish the paper also tested their method on matrix games. However, I don't want to bug the authors with requesting experimenting on different environments as I know this mostly is frustrating.", "theoretical_claims": "I have not checked the correctness but I did not observe a claim that  raised my suspicioun.", "experimental_designs_or_analyses": "I think the design makes sense and analysis are ok. However, I think better context should be provided for the best possible NE for the environments.", "relation_to_broader_scientific_literature": "I think the paper is very relevant. multi agent RL is becoming more important and maintaining diverse policies in the population is important for effective exploration.", "essential_references_not_discussed": "I think it would be nice to mention LOLA and Best Response Shaping papers. LOLA is a fundamental paper showing naive RL fails in social dilemmas. Best Response Shaping also is another way to change the enhance best response shaping to elicit algorithms that solve social dilemmas in the sense of discovering policies with high social welfare. However, I don't want to bug the authors much because the field is vast but I thought they are important papers to notice.", "other_strengths_and_weaknesses": "I think I have mentioned everything in the above boxes. The strength is the paper is very well written and seems motivated and also the method makes sense. The weakness is I don't know if the results are dramatic or not because of the lack of what the max NE is. Also, I think hyperparameter search should have been explained in more depth. Also, I am a bit worried about the filtering mechanism. As far as I understand, different mechanisms can be chosen and the choice does really matter. I think that is a nice way to steer the exploration. However, I am not sure what happens in a mixed environment. In an environment that actually simple heuristics for flitering trajectories do not work.", "other_comments_or_suggestions": "I don't have other comments.", "questions_for_authors": "Q1-Can you provide a max possible return and lowest possible return in the games discussed in the paper?\nQ2-If in an environment, we don't have an idea on what explorations are useful, what should we do? It seems the choice for filtering the trajectories is very important. \nQ3-Is there a reason not to test the simple matrix games as most of time is done in the literature?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sKqJHqdsR1", "reviewer": "Reviewer_RgJ4", "summary": "This paper proposes a strategy exploration method that introduces social welfare maximization into the PSRO framework. By creating an exploration strategy and using it to regularize new strategies, E$\\text{x}^2$PSRO tends to discover strategies with higher social welfare when solving the Nash equilibrium. Especially in sequential bargaining games and social dilemma games, E$\\text{x}^2$PSRO demonstrates better prosocial behavior.\n\n## update after rebuttal\n\nThanks for the author's reply, and my main concerns have been addressed, so I raise the point to a weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments and feedback. As noted, we rely on experiments to validate Ex2PSRO’s faster convergence compared to classical PSRO (see Fig. 6, with more details in App. H). We do not theoretically guarantee Ex2PSRO’s performance. However, note that Ex2PSRO’s response objective differs from PSRO’s through a regularization term, and the weight on this is annealed and limited to S_{\\beta} steps. Thus, Ex2PSRO naturally inherits whatever eventual convergence guarantees are provided by classical PSRO. We did not consider this a significant theoretical claim so we did not develop it explicitly.\n\nWe likewise cannot guarantee deterministic social welfare improvement, and tend to doubt that is a feasible goal. As with any algorithm involving deep RL, applicable theoretical guarantees are limited and there is natural variance across trials, so equilibria found by Ex2PSRO do not have exclusively higher welfare than those of PSRO. In tested benchmarks, experiments validate that Ex2PSRO tends to improve welfare on average with significant margins relative to discovered equilibria. Just as our provided proof-of-concept MDP demonstrates a case where GRO does not improve welfare while Ex2PSRO does, there are undoubtedly environments where Ex2PSRO will not yield improvement.\n\nEx2PSRO’s improved efficacy over alternative methods is justified in Section 4, where we motivate its design and note that high-welfare solutions may not be discovered regardless of MSS choice. \n\nFor question 2, social welfare calculations are conducted during evaluation, therefore not adding computation to Ex2PSRO trials. Compared to classical PSRO in general, Ex2PSRO incurs no additional simulation expense but requires offline behavior cloning training at every iteration, which is a relatively inexpensive computation compared to online RL optimization.", "claims_and_evidence": "The paper provides a comprehensive explanation of the method's claims, allowing readers to understand its intentions. The experimental design is thorough and demonstrates the effectiveness of the algorithm. However, the authors have not provided an adequate analysis of the theoretical properties of the algorithm, making it difficult to determine whether the method proposed in this paper is sufficiently supported.", "methods_and_evaluation_criteria": "From an application perspective, social welfare maximization is indeed an objective that can be considered when solving equilibrium strategies. The method presented in the paper may be a solution to this problem, but I believe more theoretical evidence should be provided to demonstrate that it can be effective.", "theoretical_claims": "The paper does not provide sufficient theoretical proof, which could be a limitation.", "experimental_designs_or_analyses": "The paper provides detailed experiments that demonstrate the effectiveness of the algorithm, and I believe the experimental analysis is sufficiently thorough.", "relation_to_broader_scientific_literature": "In previous PSRO research, the primary goal was often just to solve equilibrium strategies, with little consideration given to the selection problem between different equilibria. This paper presents an algorithmic improvement addressing the potential social welfare differences between various equilibria, thus providing inspiration for research on prosocial behavior strategies.", "essential_references_not_discussed": "The authors have appropriately cited the latest works in this field.", "other_strengths_and_weaknesses": "I believe the main limitation of this paper is the lack of theoretical analysis of the algorithm. For algorithms that solve equilibrium strategies in games, analyzing convergence and the results of convergence is necessary. I would like the authors to address the following questions: First, does the convergence of the E$\\text{x}^2$PSRO algorithm align with that of the classical PSRO algorithm? Does introducing social welfare into the strategy exploration affect the algorithm's convergence to the Nash equilibrium? Additionally, I would like the authors to clarify whether the optimization objective in the strategy exploration presented in the paper can deterministically improve the social welfare of the equilibrium. Or, why is the method in this paper more effective in discovering equilibria with higher social welfare compared to other possible approaches (such as simultaneously using multiple meta-strategy solvers in each exploration and selecting the one with the maximum social welfare)?", "other_comments_or_suggestions": "My comments are given above.", "questions_for_authors": "(1) I would like the authors to explain theoretically why the E$\\text{x}^2$PSRO algorithm does not affect the convergence of the original PSRO algorithm, and whether the E$\\text{x}^2$PSRO algorithm can deterministically improve social welfare when multiple different equilibria exist.\n\n(2) I would like the authors to clarify the impact of introducing social welfare on computational complexity and whether it will consume more time in each iteration.\n\nIf there are any mistakes in my comments, please correct me. I will adjust my perspective accordingly.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors have adequately addressed the concerns the reviewers had and are all in favor of the paper being accepted to ICML.  I concur.  The paper makes a clear contribution (finding a method to find equilibria with high welfare) to the field.
Decision: Accept (poster)