A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games
Authors: Samuel Sokota
Ryan D'Orazio
J Zico Kolter
Nicolas Loizou
Marc Lanctot
Ioannis Mitliagkas
Noam Brown
Christian Kroer
Venue: ICLR 2023 poster (2023)
Keywords: reinforcement learning
quantal response equilibria
two-player zero-sum games
mirror descent
variational inequalities
Nash equilibria
algorithmic game theory
proximal gradient

Abstract: This work studies an algorithm, which we call magnetic mirror descent, that is inspired by mirror descent and the non-Euclidean proximal gradient algorithm. Our contribution is demonstrating the virtues of magnetic mirror descent as both an equilibrium solver and as an approach to reinforcement learning in two-player zero-sum games. These virtues include: 1) Being the first quantal response equilibria solver to achieve linear convergence for extensive-form games with first order feedback; 2) Being the first standard reinforcement learning algorithm to achieve empirically competitive results with CFR in tabular settings; 3) Achieving favorable performance in 3x3 Dark Hex and Phantom Tic-Tac-Toe as a self-play deep reinforcement learning algorithm.

Published as a conference paper at ICLR 2023
A UNIFIED APPROACH TO REINFORCEMENT LEARNING, QUANTAL RESPONSE EQUILIBRIA, AND TWO-PLAYER ZERO-SUM GAMES
Samuel Sokota* *
Ryan D'Orazio*
Carnegie Mellon University
Mila, Université de Montréal ryan,doral www.ziolaiiiiiicooooooooooooooie quebec
ssokota@andrew cmu. edu
Zico Kolter
Nicolas Loizou Johns Hopkins University nloizouu juu. edu
Marc Lanctot
Carnegie Mellon University zkolterêcs cww.reessccuu..o.mmmmmmo cmu. edu
DeepMind
lanctot deroottdeeeeeeeieen com
Ioannis Mitliagkas
Noam Brown
Christian Kroer
Mila, Université de Montréal ioanni @mila. guebec
Meta AI
Columbia University
noambrown@mete com
ck29452col Lumuaa edu
ABSTRACT
This work studies an algorithm, which call magnetic mirror descent, that is inspired by mirror descent and the non-Euclidean proximal gradient algorithm. Our contribution is demonstrating the virtues of magnetic mirror descent both an equilibrium solver and as an approach to reinforcement learning in two-player zero-sum games. These virtues include: Being the first quantal response equi- libria solver to achieve linear convergence for extensive-form games with first order feedback; 2) Being the first standard reinforcement learning algorithm achieve empirically competitive results with CFR in tabular settings; 3) Achieving favorable performance 3x3 Dark Hex and Phantom Tic-Tac-Too Toe as a self-play deep reinforcement learning algorithm.
INTRODUCTION
This work studies an algorithm that we call magnetic mirror descent (MMD) in the context of two- player zero-sum games. MMD is extension of mirror descent (Beck & Teboulle 2003 Nemirovsky & Yudin 1983) with proximal regularization and a special case of a non Con-Euclidean proximal gra- dient method (T (eenng 2010; Beck 2017)- of which have been studied extensively in convex optimization. To facilitate our anal ysiiss of MMD, we extend the non non-Euclidean proximal gradient method from convex optimization 2p0s games and variational inequality problems (Facchinei & Pang 2003) more generally. We then prove new linear convergence result for the non non-Euclidean proximal gradient method in variational inequality problems with composite structure. As a conse- quence of our general analysis, we attain formal guarantees for MMD by showing that solving for quantal response equílibria (McKelvey & Palfrey 1995) (i.e., entropy regularized Nash equilibria) in extensive- form games (EFGs) can be modeled as variational inequality problems via the sequence form (Romanovskij. 1962 Von Stengel 1996 Koller et al. 1996). These guarantees provide the first linear convergence results to quantal response equilibria (QREs) in EFGs for first order method.
Our empirical contribution investigates MMD as last iterate (regularized) equilibrium approximation algorithm across variety of 2p0s benchmarks. We begin by confirming
soooy--hhowing that
MMD converges exponentially fast to QREs in both NFGs and EFGs. We also find that, empirically, MMD converges to agent QREs (AQREs) (McKelvey & Palfrey 1998) alternative formulation of QREs for extensive-form games-ae when applied with action-value feedback. These results lead us examine MMD as an RL algorithm for approximating Nash equilibria. On this front, we show
$ Equal contribution

---

Published as a conference paper at ICLR 2023
competitive performance with counterfactual regret minimization (CFR) Zinkevich al. 2007). This is the first instance of a standard RL algorithuf] yielding empirically competitive performance with CFR in tabular benchmarks when applied in self play. Motivated by our tabular results, we examine MMD as a multi-agent deep RI. algorithm for 3x3 Abrupt Dark Hex and Phantom Tic-Tac-Toe fieeTic-Thee-enncuuagigggg encouragingly, we find that MMD is able successfully minimize approximation of exploitability, In addition to those listed above, we also provide numerous other experiments in the appendix. In aggregate, we believe that our results suggest that MMD is unifying approach to reinforcement learning, quantal response equilibria, and two-player pero-sum games.
2 BACKGROUND
Sections 2.1 and 3.3 provide casual treatment of our problem settings and solution concepts and summary of our algorithm and some of our theoretical results. Sections 2.2 through [.2 give a more formal and detailed treatment of the same material- these sections are self-contained and safe-to-skip for readers less interested in our thcoretical results.
2.1 PROBLEM SETTINGS AND SOLUTION CONCEPTS
This work is concerned with 2p0s games-i.e. settings with two players in which the reward for one player is the negation of the reward for the other player Two-player zero-sum games are often formalized as NFGs, partially observable stochastic games (Hansen et al.. 2004) or perfect-recall EFGs (von Neumann & Morgenstern, 1947). An important idea that it is possible to convert any EFG into an equivalent NFG. The actions of the equivalent NFG correspond to the deterministic policies of the EFG. The payoffs for a joint action are dictated by the expected returns of the corresponding joint policy in the EFG.
We introduce the solution concepts studied in this work as generalizations of single-agent solution concepts. In single-agent settings, we call these concepts optimal policies and soft-optimal policies. We say a policy is optimal if there does not exist another policy achieving a greater expected return (Sutton & Barto 2018). In problems with single decision-point, say policy is a-soft optimal in the normal sense it maximizes a weighted combination of its expected action value and its entropy:
π arg max max
+ aH(('),
(1)
where is policy, A(A) is the action simplex, q is the action-value function, is the regularization temperature, and H is Shannon entropy. More generally, we say a policy is a-soft optimal in the behavioral sense if it satisfies equation (1) every decision point.
In 2p0s settings, we refer to the solution concepts used in this work as Nash equilibria and QREs. We say joint policy is a Nash equilibrium if each player's policy is optimal, conditioned on the other plaver not changing its policy. In games with a single-decision point, we say a joint policy QRE (McKelvey & Palfrey 1995) if each player's policy is soft optimal in the normal sense, conditioned on the other player not changing its policy. More generally, we say joint policy is an agent QRE (AQRE) (McKelvey & Palfrey 1998) if each player's policy is soft optimal in the behavioral sense, subject to the opponent's 's policy being fixed. Note that AQREs of EFGs do not generally correspond with the QREs their normal-form equivalents.
Outside of (A)QREs, our results also apply to other regularized solution concepts, such as those having KL regularization toward a non-uniform policy.
2.2 NOTATION
We use superscript to denote a particular coordinate of x (x (xt,.... ,,)..,")))))....)".)) E Rn and subscript to denote time 24. We use the standard inner product denoted as (x, v) Σn= w'y". For given
We use "standard RI. algorithm" to mean algorithms that would look ordinary to single-agent RI. practitioners- e.g. algorithms that converge in the average iterate operate over sequence form. Note that 2p0s games generalize single-agent settings, such as Markov decision processes [Puterman 2014 and partially observable Markov decision processes (Kaeibling et al. 1998). "Specifically, is logit QRE; We omit "logit" a prehx for brevity.
2

---

Published as a conference paper at ICLR 2023
norm | on R" define its dual norm 1y|* /up|=|=1 <y) For example, the dual norm
to || E |--|| is || max; |.l| We assume all functions f : IR" - (- + to be closed, with domain of f as dom f = fa f(x) < +o0 and corresponding interior int dom f. If f is convex and differentiable, then its minimum Te E arg milgge (x) over a closed convex set C satisfies (Vf(x*), x x.> > 0 for any x E C.
We use the Bregman divergence of da to generalize the notion of distance. Let da be a convex function differentiable over int dom v). Then the Bregman divergence with respect to & is B dom & x int dom a - R, defined as B (z: y) = vb(a) - (yy) (Vv(y), x - y). We say that f is p-strongly convex over C' with respect to if By y) 2 51 y/ for any x C.y E C' C int dom ah. Similarly we define relative strong convexity (Lu et al. 2018). We say g is je-ttrongly convex Vely), x - y) or, equivalently, Note both ya and Bx(:y)) are
relative to vb over C (Vg(æ) Vg(y), - 1) > μK (
if (2 y) > pz y), Vr, int dom v C (Lu et al. 2018 1-strongly convex relative to t..
2.3 ZERO- SUM GAMES AND QRES
In 2p0s games, the solution of QRE can be written as the solution to a negative entropy regularized saddle point problem. To model QREs (and more), we consider the regularized min max problem
min max agi(z) + f(z, v) ag2(3), nEX yey
(2)
where X' = Rd y = 1n are closed and convex (and possibly unbounded) and Ø R R.
92 R - R. R R. -m Moreover, 91 and f(- y) are differentiable and convex for every
y. Similarly -92. f(x, .) are differentiable and concave for every A solution (I*,, M/)) to equation 2 is a Nash equilibrium in the regularized game with the following best response conditions along with their equivalent first order optimality conditions
To E arg min agi (x) [1x, Mw) (z + VZ [ Uo x 2 0v X, zE
V& E arg min agg(y)) - f v) + (a (V+) Vyu [ U+). y/ 3 Ovy e V
yEy
Ay for some payoff matrix A, and 91 92 are negative entropy. The corresponding best response conditions 33 can be written in closed form
In the context of QREs we have that X' A y A with [(x
2 exp( Avs/aa, X exp(4 s*/a). Similarly, for EFGs, normal-form QREs take the form of equation 2 (Ling et al. 2018) with g1 92 being dilated entropy (Hoda et al., 2010), fx, 3) xx Ay (A being the sequence- from payoff matrix), and X, y the sequence-form strategy spaces of both players.
2.4 CONNECTION BETWEEN ZERO-SUM GAMES AND VARIATIONAL INEQUALITIES
More generally, solutions equation 2 (including QREs) can be written solutions variational inequalities (VIs) with specific structure. The equivalent VI formulation stacks both first-order best response conditions 4 into one inequality.
Definition 2.1 (Variational Inequality Problem (VI)). Given 2 s IR and mapping G: Z - R", the variational inequality problem VT(2,G) to find 24 Z such that
(G(z)), Zz
Vz E 2.
(5)
In particular, the optimality conditions
3 are equivalent to VI(Z, where G = F+ aVg. 9 (x) + (2(),, with corresponding operators F(z)
Z X' y and g 2 IR, (x. v)
V y). Vyf(zz, v)] and Vg IV #1 (z), Vo For more details see Facchinei &
Pang (2003) (Section 1.4.2). Note that VIs are more general than min-max problems; they also include fixed-point problems and Nash equilibria in re-plaeer general-sum games (Facchinci & Pang 2003). However, in the case of convex- coneee- zero-sum games and convex optimization, the problem admits efficient algorithms since the corresponding operator G is monotone (Rockafellar) 1970).
Definition 2.2. G is said to be strongly monotone if, for μ > and any 2, where G is defined,
(G(z) G(z'), z - z²) > A||: - 2/112 G is monotone if this is true for μ 0.
Definition 2.3, G is said to be L-smooth with respect to || if, for any 2, x where G is defined, [[G(=) - G(=')l * & T.I z'1.
3

---

Published as a conference paper at ICLR 2023
For EFGs, Ling et al. (2018) showed that the QRE is the solution of a min-man problem of the form equation 2 where f is bilinear and each 9: could be non smooth. Therefore, we can write the problem VI with strongly monotone operator G having composite structure, smooth part coming from f and non-smooth part from the regularization 9t, 92-
Proposition 2.4. Solving a normal-forn reduced QRE in a two-player zero-sum EFG is equivalent to solving (I F + (VVb) where Z is the cross-product of the sequence form strategy spuces and d is the sum of the dilated entropy functions for each player. The function 1p is strongly convex with respect to || Il, Furthermore, is monotone and maxss [Aiy -Ayl-smmooth (A being the sequence-form payoff matrix) with respect to and F + a VV is strongly monotone.
3 ALGORIHTM AND THEORY
In Proposition 2.4 we provided a new perspective to QRE problems that draws connections to VIs with special composite structure. Motivated by this connection, in Section 3.1 we consider approach to solve such problems via a Non-Euclidean proximal gradient method Tseng 2010); Beck (2017) and prove a novel linear convergence result. Thereafter, in Section 3.2 demonstrate how this general algorithm specializes to MMD and splits into two decentralized simultaneous updates in 2p0s games (one for each player). Finally, in Section 3.3 we discuss specific instances of MMD, give new algorithms for RL and QRE solving, and summarize our linear convergence result for QREs.
3.1 CONVERGENCE ANALYSIS
We now present main algorithm, non-Euclidean proximal gradient method solve VI(Z, F + VVg) Since Vg is possibly not smooth, we incorporate as proximal regularization. Algorithm 3.1. Starting with E int dom de e Z at each iteration I do
arg min 1y (<)) 2) + ag(z)) + (z;
2++1
To ensure that 2 is well defined, we make the following assumption. Assumption 3.2 (Well-defined). Assume &b is 1-strongly convex with respect to || over Z and, for any L, stepsize 1) > 0, a > 2t+1 arg min rj ((t, 2) + ag(=)) (2; 21) e int dom v.
We also make some assumptions on and g.
Assumption 3.3. Let F' be monotone and L-smooth with respect to || and g be 1-strongly convex relative to & over Z with g differentiable over int dom vi
These assumptions imply F+aVg strongly monotone with unique solution 24 Bauschke et al. 2011]. Our result shows that, if 2g int dom xfF] then Algorithm converges linearly to 2.. Theorem 3.4. Let Assumptions 3.2 and 3.3 hold and assume the unique solution zu VI(Z, F+ aV Vg) satisfies E int dom vb. Then Algorithm 3.7 converges if & a and guarantees
L"
B3(24)4411)
Ba(2ai21)
I+ 1jax
Note a > 0 necessary to converge to the solution. If = in the context of solving equation 2 Al- with or cycle for any positive stepsize. However, choosing the strong convexity constants of and 1a to be 1 is for convenience-tfe the theorem still holds with arbitrary constants, in which case the stepsize condi- tion becomes proportional to the relative strong convexity constant of g (see Corollary Doófor details).
gorithm with (2) 1 =| becomes projected gradient descent ascent, which is known to diverge
Due to the generality of VIs, we have the following convex optimization result.
Corollary 3.5. Consider the composite optimization problem min f(z + ag((2). Then under the same assumptions as Theorem 3.4 with F = f. Algorithm 3.7 converges linearly to the solution.
Note that Corollary 3.5 guarantees linear convergence, which is faster than existing results ( TTsegg 2010 Bauschke et al. 2017: Hanzely et al. 2021), due to the additional assumption that g is
ellaively-strongly convex.
3.3 imply is strongly convex and hence Vg is strongly monotone. "This assumption is guaranteed the ORF setting where g the sum of dilated entropy.
*This follows because Assumptions 3.2
4

---

Published as a conference paper at ICLR 2023
3.2 APPLICATION OF MAGNETIC MIRROR DESCENT TO TWO-PLAYER ZERO-SUL SUM GAMES
We define MMD to be Algorithm 3.1 with taken to be either & or (x(+=²) for some z': in both cases the 1-relative strongly convex assumption satisfied, and Et+1 is attracted either minzez (=) or z', which we call the magnet.
A Algorithm 3.6 (Magnetic Mirror Descent (MMD)).
2++1 arg min ((F(z)) 2) + ar((z)) + Bx(2;z)
(6)
sE
or
2++1 arg min
m ((F(z),,) + aab((zzz)) + (2(2;)).
(7)
seZ
Remark 3.7. MMD has the same computational cost as mirror descent since the updates can be equivalently written as 2++1= arg mingee (l, 2) + (z(2) (e.g. (=(nf(a) (ioaala)--VVaa))((aaa))) (V(x)))((+mo))) for equation 6). In fact, Proposition D.7] shows that MMD is equivalent to mirror descent on the regularized loss with different stepsize.
MMD and, more generally, Algorithm 3. can be used to derive a descent-ascent method solve the zero-sum game equation 2 If 91 1 and 92 222 strongly convex over X' and V then can let 2b(2) = 1/ (z) + (y), which makes v strongly convex over Z. Then the MMD update rule equation converges to the solution of equation ann splits into simultancous descent-ascent updates:
1++1 = arg min (V (Ir, (t). + anl (x)) + Bo (x) 21),
(8)
-ex
1 arg max 7) (VV ( anb2(1)) B Vt). yEy
3.3 MAGNET MIRROR DESCENT SUMMARY
MMD's update parameterized by four objects: a stepsize 1), a regularization temperature a, a mirror map b, and a magnet, which we denote as either the extent to which moving away from the current iterate penalized; the regularization temperature dictates the extent to which being far away from the magnet (i.e., () is penalized; the mirror map & determines how distance measured.
depending on the v.. The stepsize 17 dictates
If we take v to be negative entropy, then, in reinforcement learning language, MMD takes the form
aKL( 1 "
Te+1 arg.aa,,Easaaapp
[K(TTT)), mt),
(10)
where n. the current policy, q is the Q-value vector for time t. and p is a magnet policy. For parameterized problems, if tb = MMD takes the form
1 110 0.122
A argmin, Vo, C(O.), 0) + 2
<ll
(11)
21
where 8g is the current parameter vector, is the loss, and Ç is the magnet.
In settings with discrete actions and unconstrained domains, respectively, these instances of MMD possess close forms, as shown below
Fe+ [TT no Jrlu,
Oc+1 = 10. + ank V, ((0,) CN)
(12)
Our main result, Theorem 3.4 and Proposition 2.4 imply that if both players simultancously update their policies using equation 110p with a uniform magnet in 2p0s NFGs, then their joint policy converges to the o- o-QRE exponentially fast. Similarly, in EFGs, if both players use a type of policy called sequence form with & taken to be dilated entropy, then their joint policy converges to the a-QRE exponentially fast. Both of these results also hold more generally for equilibria induced by non-unifome magnet policies. MMD can also be a considered as a rehavioral-fome algorithm in which update rule (10) or IIT) is applied at each information state. If p is uniform, fixed point of this instantiation is an Q- a- AQRE; more generally, fixed points are regularized equilibria (i.c., fixed points of regularized best response operator).
5

---

Published as a conference paper at ICLR 2023
00.05
Normal-Fon Foom-Fom QREs
MND Pg
KL D.veerggooo
kynt
Gam OMAUU
Quarles
Extensive- Form QREs
Divergence of Diated Entropy
Kulnn Poker
Abrupt
Dica
Sadtle Pontt Gon
13.1
0.5
0.2
200
1700
Extensive- Form AQRES
127
17
0.05
Divergence
Mean
Narations
Figure 1: Solving for (A)QREs in various settings.
EXPERIMENTS
Our main body focuses on highlighting the high level takeaways of our main experiments. Additional discussion of each experiment, well additional experiments, are included in the appendix. Code for the sequence form experiments is available at
www/rconooooeeeeee. wya-- mmd-d1 lated Code for some of the other experiments is available at
3sokota/ mmd
Experimental Domains For tabular normal-form settings, used stage games of a 2p0s Markov variant of the game Diplomacy (Paquette et al. (011)). These games have payoff matrices of shape (50, 50), (35, 43), (50, 50), and (4, 4), respectively, and were constructed using an open-source value function (Bakhtin et al. 2021). For tabular extensive-fore form settings, we used games implemented in OpenSpiel (Lanctot et al.) 2019): Kuhn Poker, 2x2 Abrupt Dark Hex, 4-Sided Liar's Dice, and Ledue Poker. These games have 54, 471, 8176, and 9300 non-terminal histories, respectively. For deep multi-agent settings, we used 3x3 Abrupt Dark Hex and Phantom Tie-Tac-Toe, which are also implemented in OpenSpiel.
Convergence to Quantal Response Equilibria First, we examine MMD's performance as a QRE solver. We Ling et al. (2018)'s solver to compute ground truth solutions for NFGs and Gambit (McKelvey, Richard D., McLennan, Andrew M., and Turocy, Theodore L.) 2016) to compute ground truth solutions for EFGs. We show the results in Figure Il We show NFG results in the top row of the figure compared against algorithms introduced by Cen et al. (202)), with each algorithm using the largest stepsize allowed by theory. All three algorithms converge exponentially fast, is guaranteed by theory. The middle row shows results for QREs on EFG benchmarks. For Kuhn Poker and 2x2 Abrupt Dark Hex, we observe that MMD's divergence converges exponentially fast, as is also guaranteed by theory. For 4-Sided Liar's Dice and Ledue Poker, we found that Gambit had difficulty approximating the QREs, due to the size of the games. Thus, we instead report the saddle point gap (the sum of best response values in the regularized game), for which we observe linear convergence, as is guaranteed by Proposition D.6 The bottom row shows results for AQRES using behavioral form MMD (with y a/10) on the same benchmarks, where we also observe convergence (despite a lack of guarantees). For further details, see Sections G.3 for the QRE experiments and Section G.4 for the AQRE experiments.
Exploitability Experiments From our AQRE experiments, immediately follows that it is possible to use behavioral form MMD with constant stepsize, temperature, and magnet to compute strategies with low exploitabilities
0 Indeed, we show such results (again with 77 = a/ 10 and a uniform magnet) in the
'Nte that this would also be possible with fequence-form MMD.

---

Published as a conference paper at ICLR 2023
2x2 Abrupt
Kuhn Poker
Dark Hex
4-Sided Liar's Dice
Leduc Poker
10
1011
0.05
Exploitability
10"4
20,000
40,000
20.000
40,000
0
20.000
40.000
0
20,000
40,000
MMD (Annealing Temperature)
10P
10"
(Maving Magnet)
10--
10-
CFR
10-
10--
GFR+
10
10a
10a
10
10
10
10
10a
10
10a
10a
10
10a
10a
10a
10
10
102
10
10
10
Iterations
Figure 2: (top) Behavioral-form MMD with constant hyperparameters for various temperatures; (bottom) instances of behavioral-form MMD as Nash equilibria solvers, compared to CFR and CFR+.
top row of Figure 2 A natural follow up question to these experiments is whether MMD can be made into a Nash equilibrium solver by either annealing the amount of regularization over time or by having the magnet trail behind the current iterate. We investigate this question in the bottom row of Figure 2 by comparing i) MMD with an annealed temperature, annealed stepsize, and constant magnet; ii) MMD with constant temperature, constant stepsize, and moving magnet; iii) CFR (Zinkvichh et al., 2007]: and iv) CFR+ (Tammelin] (014). While CFR+ yields the strongest performance, suggesting that it remains the best choice for tabularly solving games, view the results very positive. Indeed, not only do both variants of MMD exhibit last-iterate convergent behavior, they also perform compet- itively with (or better than) CFR. This is the first instance of a standard RL algorithm yielding results competitive with tabular CFR in classical 2p0s benchmark games. For further details, see Section H.3 for the annealing temperature experiments and Section H.5 the moving magnet experiments.
Deep Multi-Agent Reinforcement Learning The last experiments in the main body examine MMD as a deep multi-agent RL algorithm using self play. We benchmarked against OpenSpiel's (Lanctot et al. (219)) implementation of NFSP (Heinrich & Silver (016) and RLlib's (Liang et al., 2018) implementation of PPO (Schulman et al. 2017). We implemented MMD as a modification of RLlib's 's (Liang al.] 2018) PPO implementation by changing the adapative forward KL regularization to reverse KL regularization. For hyperparameters, we tuned {(a,, m7)) for MMD; otherwise, used default hyperparameters for each algorithm.
As the games are too large to easily compute exact exploitability, we approximate exploitability using a DQN best response, trained for 10 million time steps. The results are shown in the top row of Figure 3 The results include checkpoints after both million and 10 million time steps, as well as bots that select the first legal action (Arbitrary) and that select actions uniformly at random (Random). As expected, both NFSP and MMD yield lower approximate exploitability after 10M steps than they do after IM steps; on the other hand, PPO does not reliably reduce approximate exploitability over time. In terms of raw value, we find that MMD substantially outperforms the baselines in terms of approximate exploitabilty. We also show results of head match-ups in the bottom row of Figure for the 10M time step checkpoints. As may be expected given the approximate exploitability results, we find that MMD outperforms our baselines head-to-head matchups. For further details, see Section [
Subject Matter of Additional Experiments In the appendix, we include 14 additional experiments:
Trajectory visualizations for MMD applied as a QRE solver for NFGs (Section D.4)
2. Trajectory visualizations for MMD applied as a saddle point solver (Section D.5)
Solving for QREs in NFGs with black box (b.b.) sampling (Section G.2):
4. Solving for QRBs in NFGs with b.b. sampling under different gradient estimators (Section G.2
5. Solving for QREs in Kuhn Poker 2x2 Abrupt Dark Hex, shown in saddle point gap (Section G.3
6. Solving for Nash in NFGs with full feedback (Section H.T
7. Solving for Nash in NFGs with b.b. sampling (Section H2
8. Solving for Nash in EFGs with a reach- beachh-rbbbblltyyweeeeee stepsize (Section H.3
7

---

Published as a conference paper at ICLR 2023
3x3 Abrupt Dark Hex
Phantom Tic-Tac-Too
Approximate Exploitability
1.0
Exploitee
NFSP(OpenSpiel)
PRO/RLIN)
Random
Arbitrary
milioo
10 million
millonn
millio
Exploitee Training Steps
3x3 Abrupt Dark Hex
Phantom Tic-Tac- Tac-Toe
1.00
Expected Return
Opponent
MMD
0.25
NISPIOpenScieef
0.00
PPO/RLIR)
-0.25
Random
-0.50
Arbitrary
40.5
MMD
NFS/PCpenSpiee) PPO(RUI))
MMD
NFSPiOOenSSpeel) PPO(RLI))
Figure (top) Approximate exploitability experiments; (bottom) head-to-head experiments.
Solving for Nash EFGs with b.b. sampling (Section H.4):
10. Solving for Nash in EFGs using MaxEnt and MiniMaxEnt objectives (Section H.6
11. Solving for Nash EFGs with a Euclidean mirror map (Section H.7):
12. Solving for MiniMaxEnt equilibria (Section H.8))
13. Learning in EFGs with constant hyperparameters and a MiniMaxEnt objective (Section H.9
14. Single-agent deep RL on small collection Mujoco and Atari games (Section I
RELATED WORK
We discuss the main related work below. Additional related work concerning average policy deep reinforcement learning for 2p0s games can be found in Section
Convex Optimization and Variational Inequalities Like MMD and Algorithm 3.1 the extragradient method (Korpelevich) 1976 Gorbunov et al. 2022) and the optimistic method (Popov) 1980) have also been studied in the context zero-sum games and variational inequalities more generally. However, in contrast to MMD, these methods require smoothness to guarantee convergence. Outside the context of variational inequalities, analogues MMD and Algorithm 3.1 have been studied in convex optimiza- tion under the non- -un-Euclidean proximal gradient method (Beck 2017) originally proposed by Tseng (2010). But, in contrast to Theorem 3.4 existing convex optimization results (Beck 2017 Tseng 2010 Hanzely et al. 2021 Bauschke et al. 2017) are without linear rates because they do not assume the proximal regularization be relatively-strongee convex. In addition to convex optimization, the non-Euclidean proximal gradient algorithm has also been studied in online optimization under the name composite mirror descent (Duchi et al. 2010). Duchi et al. (0100) show a O(vE) regret bound without strong convexity assumptions the proximal term. In the case where the proximal term is rel- atively strongly convex, Duchi et al. (2010) give an improved rate of Olog t) implying that MMD has average iterate convergence with rate of (log for bounded problems, like QRE solving.
8

---

Published as a conference paper at ICLR 2023
Quantal Response Equilibria Among QRE solvers for NFGs, the PU and OMWPU algorithms from Cen et al. (222)) ). which also possess linear convergence rates for NFGs, are most similar to MMD. However, both PU and OMWPU require two steps per iteration (because of their similarities to mirror-prox (Nemirovski] 2004) and optimistic mirror descent (Rakhlin & Sridharan| (013)), and PU requires an extra gradient evaluation. In contrast, our algorithm needs only one simple step per iteration (with the same computation cost as mirror descent) and our analysis applies to various choices of mirror map, meaning our algorithm can be used to compute larger class of regularized equilibria, rather than only QREs. Among QRE solvers for EFGs, existing algorithms differ from MMD in that they either require second order information (Ling et al. 2018) or are first order methods with average iterate convergence (Farina et al. 2019 Ling et al. 2019). In contrast to these methods, MMD attains linear last-iterate convergence.
Single-Agent Reinforcement Learning Considered as a reinforcement learning algorithm, MMD with a negative entropy mirror map and MaxEnt RI. objective coincides with the NE-TRPO algorithm studied in (Shani et al. 2020). MMD with negative entropy mirror map is also similar to the MD-MPI algorithm proposed by Vieillard et al. (2020) but differs in that MD-MPI includes the negative KL divergence between the current and previous iterate within its Q-values, whereas MMD does not. Considered as a deep reinforcement learning algorithm, MMD with a negative entropy mirror map bears relationships both KL-PPPO variant of PPO that served motivation for the more widely adopted gradient clipping variant) (Schulman et al.. (017)) and MDPO (Tomar ct al. 2020; Hsu al., 2020). In short, the negative entropy instantiation of MMD corresponds with KL-PPO with a flipped KL term and with MDPO when there is entropy regularization. We describe
these relationships using symbolic expressions in Section L
Another line of work has combined follow-the- regularized-leader with additional regularization, under the names friction follow-the-regue regulaagrar leader (F-FoReL) (Pérolat et al. [202]) and piKL (Jacob et al. (022). in an analogous fashion to how we combine mirror descent with additional regularization.
Regularized Follow-the- Follov-the-Regularizee
Similarly to our work, F-FoReL was designed for the purpose of achieving last iterate convergence in 2p0s games. In terms of convergence guarantees, we prove discrete-time time linear convergence for NFGs, while Pérolat et al. (202I) give continuous-time linear convergence for EFGs using counterfactual values; neither possesses the desired discrete-time result for EFGs using action values. In terms of case-of-use, MMD offers the advantage that it is dccentralizable, whereas the version of F-FoReL that (Pérolat et al. (2021) present is not. In terms of scalability, MMD offers the advantage that it only requires approximating bounded quantities; in contrast, F-FoRel. requires estimating an arbitrarily accumulating sum. I Lastly, in terms of empirical performance, the tabular results presented in this work for MMD are substantially better than those presented for F-FoRel. For example, F-FoReL's best result in Ledue is an exploitability of about 0.08 after 200,000 iterations takes MMD fewer than 1,000 iterations to achieve the same value.
On the other hand, piKL was motivated by improving the prediction accuracy of imitation learning via decision-time time planning. We believe the success of piKL in this context suggests that MMD may also perform well in such setting. While Jacob et al. (022) also attains convergence to KL-regularized equilibria NFGs, our results differ in two ways: First, our results only handle the full feedback case, whereas Jacob et al.] (2022);s 's results allow for stochasticity. Second, our results give linear last-iterate convergence, whereas Jacob et al. (2022) only show (l1) average-iterate convergence.
CONCLUSION
In this work, we introduced MMD an algorithm for reinforcement learning in single-agent settings and 2p0s games, and regularized equilibrium solving. We presented proof that MMD converges exponentially fast to QREs in EFGs-the first algorithm of its kind to do so. We showed empirically that MMD exhibits desirable properties as tabular equilibrium solver, as a single-agent deep RL algorithm, and as a multi-agent deep RL algorithm. This is the first instance of an algorithm exhibiting such strong performance across all of these settings simultancously. We hope that, due to its simplicity, MMD will help open the door to 2p0s games research for RL researchers without game-theoretic backgrounds. We provide directions for future work in Section M

---

Published as a conference paper at ICLR 2023
7 ACKNOWLEDGEMENTS
We thank Jeremy Cohen, Chun Kai Ling, Brandon Amos, Paul Muller, Gauthier Gidel, Kilian Fatras, Julien Perolat, Swaminathan Gurumurthy, Gabriele Farina, and Michal Sustr for helpful discussions and feedback. This research was supported by the Bosch Center for Artificial Intelligence, NSERC Discovery grant Research Young Investigator Program grant N00014-22-1-2530.
Samsung, a Canada CIFAR Al Chair, and the Office of Naval
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017,
pp. 1200-1205 New York, NY, USA, 2017. Association for Computing Machinery. ISBN
9781450345286.
doi: 10.1 40444333355399909554444
URL https://doi.or//10..
3055399 3055448
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In Proceedings of the 37th International Conference on Machine Learning. ICML'20, JMLR.org. 2020.
Anton Bakhtin, David Wu, Adam Lerer, and Noam Brown. No-press diplomacy from scratch. Advances in Neural Information Processing Systems, 34, 2021.
Aaron Bakst and Martin Gardner. The second scientific american book of mathematical puzzles and diversions. American Mathematical Monthly, 69:455, 1962.
Heinz H Bauschke, Jonathan M Borwein, and Patrick I. Combettes. Bregman monotone optimization algorithms. SIAM Journal on control and optimization, 42(2):596-636 6366, 2003.
Heinz H Bauschke, Patrick L Combettes, et al. Convex anulysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
Heinz H Bauschke, Jérôme Bolte, and Mare Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research. 42(2):330-348, 2017.
Amir Beck. First-Order Methods in Optimization. Society for Industrial and Applied Mathematies, Philadelphia, PA, 2017.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Reseurch Letters, 31(3):667175,, 2003. ISSN 0167-6377.
Marc G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning envi- ronment: An evaluation platform for general agents. J. Artif. Int. Res., 47(1):253-279 may 2013. ISSN 1076-9757.
G.W. Brown. Iterative solutions of games by fictitious play. In Activity Analysis of Production and Allocation, 1951.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. ArXiv, abs/1811.00166 2019.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-37, 2015.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 34, 2021.
Trevor Davis, Martin Schmid, and Michael Bowling. Low-variance and vero-nariance baselines for extensive-form games. In Proceedings of the 37th International Conference on Machine Learning, (0.. JMLR.org. 2020.
10

---

Published as a conference paper at ICLR 2023
John C Duchi, Shai Shalev-Shwarte Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In COLT, volume 10. pp. 14-26. Citeseer, 2010.
Francisco Facchinei and Jong-Shi Pang. Fintte-dmeeniooal variational inequalities and complemen- lurity problems. Springer, 2003.
Jiajun Fan and Changnan Xiao, Generalized data distribution iteration. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Reseurch, pp. 6183-6184. PMIR, 17-23 Jul 2022. URL https: htttps://prrcceednnngg mlr wwtpppssss//faaaaaaeeeep
html
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Online convex optimization for sequential decision processes and extensive-for games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33. pp. 1917-1925, 2019.
Christopher P. Ferguson and Thomas S. Ferguson. Models for the Game of Liar's Dice, pp. 15-28. Springer Netherlands, Dordrecht, 1991. ISBN 978-94--01--376-- 778-94-011-3760-2 URL hww.hhtts:://tt http://ooooooggg/////// www.oo..oooo.ooo.oooooooo 1000000007000 -1-1---------1------------------
doi: 10.1007/
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling,
C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL / neurip
Paper.par
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In Gustau Camps- Valls, Francisco R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 366-402. PMLR, 28-30 Mar 2022. URL http:::t///pptt /tttps://proceednng html
mlr. wtt.peess/v1111oorrrsees
Audrunas Gruslys, Mare Lanctot, Remi Munos, Finbarr Timbers, Martin Schmid, Julien Perolet, Dustin Morrill, Vinicius Zambaldi, Jean-Baptiste Lespiau, John Schultz, Mohammad Gheshlaghi Azar, Michael Bowling, and Karl Tuyls. The advantage regret-matching actor-critic, 2021. URL
https:://ppnnrett
net forum (efoorumid=yyMse ddwwdddeedddeaaaaae
Eric A. Hansen, Daniel Bernstein, and Shlomo Zilberstein. Dynamic programming for partially ob- servable stochastic games. In Proceedings of the 19th National Conference on Artifical Intelligence, AAAI' 04, pp. 709-715. AAAI Press, 2004. ISBN 026251 1835.
Filip Hanzely, Peter Richtarik, and Lin Xiao. Accelerated bregman proximal gradient methods for relatively smooth convex optimization. Computational Optimization and Applications, 79(2): 405-440, 2021.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games, 2016.
Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2): 494-512, 2010.
Chloe Ching Yun Hsu, Celestine Mendler-Dünner and Moritz Hardt. Revisiting design choices in proximal policy optimization. CoRR, abs/2009.10897, 2020. URL /ttps::/arxxv..or// 2009 10897
Shengyi Huang, Rousslan Fernand Julien Dossa, Antonin Raffin, Anssi Kanervisto, and Weixun Wang. The 37 implementation details of proximal policy optimization. In ICLR Blog Track, 2022. URL
ceteo-immlemmeettte. details/
implemeenation-detaillks.
11

---

Published as a conference paper at ICLR 2023
Athul Paul Jacob, David Wu, Gabriele Farina, Adam Lerer, Hengyuan Hu, Anton Bakhtin, Jacob Andreas, and Noam Brown. Modeling strong and human- like gameplay with KL-regularized search. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 9695-9728, PMLR, 17-23 Jul 2022. URL htttps:/pproceedingg
mlr press vl 62/ jacob2aa.aaaa..oaaaaaa att.oo222a..tllllll...
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in
partially observable stochastic domains. Artificial Intelligence, 101(1):99-134, 1998. ISSN 0004-3702. doi:
0000333X URL https::/ //ww
sci http://eerereteo/eeeeeeeaaaaaaaa
Daphne Koller, Nimrod Megiddo, and Bernhard Von Stengel. Efficient computation of equilibria for extensive two-person games. Games and economic behavior, 14(2):247-25, 1996.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976. URLhhttps://c mwi. hptpaaaaoo11115551111111111
Christian Kroer, Kevin Waugh, Fatma Kalmee-Karzun and Tuomas Sandholm. Faster algorithms for extensive-form game solving via improved smoothing functions. Mathematical Programming, 179 (1):385-417, 2020.
Helmut Kuhn. 9. a simplified two-person poker. 1951.
Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte carlo sampling for regret minimization in extensive games. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and Culotta (eds.), Advances in Neural Information Processing Systems, volume 22, Curran As- sociates, Inc., 2009, URL http:::: .ew.eeeeeedddneee.eeeesee....eee neurips wwtpappee/00////ee.ecpc
Mare Lanctot, Vinícius Flores Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent
reinforcement learning. In NIPS, 2017.
Marc Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafici, Daniel Hennes, Dustin Morrill, Paul Muller, Timo Ewalds, Ryan Faulkner, János Kramár, Bart De Vylder, Brennan Saeta, James Bradbury, David Ding, Sebastian Borgeaud, Matthew Lai, Julian Schrittwieser, Thomas Anthony, Edward Hughes, Ivo Danihelka, and Jonah Ryan-Davis. Open- Spiel: A framework for reinforcement learning in games. CoRR, 054/1908.09453. 2019. URL http:://axiv.. org/ http:/ivvvggg/bb////aa// absp///ss/199 09453
Alistair Letcher, David Balduzzi, Sébastien Racanière, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics. Joumnal of Machine Learning Research, 20 (84):1-40, 2019. /ttht:: http://ll.rrrrrrrrmmma wttp://pppp.//////////ppp
008 html
Hui Li, Kailiang Hu, Shaohua Zhang, Yuan Qi, and Le Song. Double neural counterfactual regret minimization. In International Conference on Learning Representations, 2020. URL https
//openreview net wttp://www.ettttuumiiiiiee
Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and Ion Stoica. RLlib: Abstractions for distributed reinforcement learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3062-3062. PMLR, 10-15 Jul 2018. URL httpsss/pppeeeednggg.. wwwpeeeiiiinim.........mmmemmeme www.mmmr..rr...mmmmmmmmmmmm v liangl88 (angg18bb.4 html
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst acceleration for first-order convex optimization: From theory to practice. J. Mach. Learn. Res., 18(1):7854-7977, jan 2017. ISSN 1532-4435.
Chun Kai Ling, Fei Fang, and J Zico Kolter. What game playing? end-to-end learning in normal and extensive form games. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 396-4962222 2018
12

---

Published as a conference paper at ICLR 2023
Chun Kai Ling, Fei Fang, and Zico Kolter. Large scale learning of agent rationality in two-player zero-sum games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 6104-6114 2019.
Haihao Lu, Robert Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and upplications. SIAM Journal Optimization, (111:3333-3444 2018.
Stephen Marcus McAleer, John Banister Lanier, Kevin Wang. Pierre Baldi, and Roy Fox. XDO: A double oracle algorithm for extensive-form games. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances Neural Information Processing Systems, 2021. URL https:///penre:
net forum? wtwpummmidWDDLEBBC V8
Richard McKelvey and Thomas Palfrey. Quantal response equilibria for normal form games. Games and Economic Behavior, 10(1):6-38 38, 1995. URL /Fappp/// reppeepppppprrpppp..peppeee repec. org/ RePEc:eee: gam.be::::e::::ee.ee.ae::::::::: : htt.mbbbee....011119919111.1
38
Richard D. McKelvey and Thomas R. Palfrey. Quantal response equilibria for extensive form games.
Experimental Economics, 1:9-41, 1998.
McKelvey, Richard D., McLennan, Andrew M., and Turocy, Theodore L. Gambit: Software tools for game theory, 2016. Utt/:ttp: www.
.org
H. Brendan McMahan, Geoffrey J. Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by adversary. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML'08 '3, pp. 536-543, AAAI Press, 2003, ISBN 1577351894.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg. and Demis Hassabis. Human-level control through deep rein- forcement learning. Nature, 518(7540):529 533, February 2015. ISSN 00280836. URL http://dx.co do1. wtw.:/oco...gg..... 1038 1ttg//000003///turee142222
Arkadi Nemirovski. Prox-method with rate of convergence (1/l) for variational inequalities with lipschitz continuous monotone operators and smooth convex- conceve saddle point problems. SIAM Journal on Optimization, 15(1):229-251) 2004.
A.S. Nemirovsky and D.B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience publication. Wiley, 1983. ISBN 9780471103455
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani (eds.). Algorithmic Game Theory. Cambridge University Press, 2007.
Philip Paquette, Yuchen Lu, Seton Steven Bocco, Max Smith, Satya O-G, Jonathan K Kummerfeld, Joelle Pineau, Satinder Singh, and Aaron Courville. No-press diplomacy: Modeling multi-agent gameplay. Advances in Neural Information Processing Systems, 32, 2019.
Lconid Denisovich Popov. modification the Arrow-Hurwicz method for search saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845 848, 1980. Publisher: Springer.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Julien Pérolat, Rémi Munos, Jean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro A. Ortega, Neil Burch, Thomas W. Anthony, David Balduzzi, Bart De Vylder, Georgios Piliouras, Mare Lanctot, and Karl Tuyls. From poincaré recurrence to convergence in imperfect information Finding equilibrium via regularization. In Marina Meila and Tong Zhang 0001 (eds.), Proceedings of the 38th International Conference Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 8525 8535. PMLR, 2021. URL htt.hhttp//ppoceeeiiii ngs ml www.rrssssee.. / wwtp////.///eee at html
games:
13

---

Published as a conference paper at ICLR 2023
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pp. 993-1019. PMLR, 2013.
R. Tymelll Rockafellar. Monotone operators associated with saddle.function. and minimax problems, 1970.
IV Romanovskii. Reduction of game with full memory to a matrix game. Doklady Akademi Nauk SSSR, 144(1):62-+, 1962.
Martin Schmid, Neil Burch, Mare Lanctot, Matej Moravcik, Rudolf Kadlec, and Michael Bowling. Variance reduction in monte carlo counterfactual regret minimization (vr-meefr) for extensive form games using baselines. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty--Frss! Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, 19/AAT 19/ 19. doi:
AAAI Press, 2019. ISBN 978-1--7735--0000 809-5
URL https:
7/doi org.i.rr///o /00. 0. 2a/00//aaai.. v331 01 33012157]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017. URL
.63477
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. Proceedings of the AAAI Conference on Artificial Intelligence. 34(04):5668-50 5675, Apr. 2020. doi: 10.1609/aaai, http9//aaaiv4404..666 v34104.60111. URL
https://ojs aaai. org/ index. phpp AAAI/AAII/// hwt./AAAA/aaariiiia http:/aattteeeeeeeeeeeeeeeeeattt 6021
Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems: Algorithmic,
and
Logical Foundations. Cambridge University Press, USA, 2008. ISBN 0521899435.
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, UAI'05, pp. 550-558, Arlington, Virginia, USA, 2005. AUAI Press. ISBN 0974903914.
Eric Steinberger, Adam Lerer, and Noam Brown. DREAM: deep regret minimization with advantage baselines and model-free learning. CoRR, abs/2006. 10410, 2020. URL abs/ 2bss/2066. 10.10044 10410
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Oskari Tammelin. Solving large imperfect information games using cfr+. 07 2014.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-basee control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror descent policy optimization, 2020. httptt//t/// org/ abs / 200000055.000 09814
Paul Tseng, On accelerated proximal gradient methods for convex-concave optimization. submitted to SIAM Journal on Optimization, 2(3), 2008.
Paul Tseng. Approximation accuracy, gradient methods, and error bound for structured convex optimization. Muthematical Progrumming, 125(2):263-295, 2010.
Theodore L. Turocy. A dynamic homotopy interpretation of the logistic quantal response equilib- rium correspondence. Games and Economic Behavior, 51(2):243-263, 2005. ISSN 0899-8256.
doi: bccjaacceeertttaeea//////9332229
00..000000.00.......000000000000 URL CtReLlttts://// www. www.scieeiiee www.sceeiiiiciccc.ooooo.oo rect. com/
Special Issue in Honor of Richard D.
McKelvey.
Theodore L. Turocy. Computing sequential equilibria using agent quantal response equilibria.
Economic Theory, 42(1):255 269, 2010. ISSN 09382259, 14320479. URL http: //www
jstor. Sstor.org/sttablee25569999
14

---

Published as a conference paper at ICLR 2023
Nino Vieillard, Tadashi Kozuno, Bruno Scherrer, Olivier Pietquin, Remi Munos, and Matthieu Geist. Leverage the average: an analysis of kl regularization in reinforcement learn- ing. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 12163-12174. Curran As- sociates, Inc., 2020. URL /ttp/tttpp.://rroeeddnn neurips cc hctppp/pp/t/222///11.e pdf
J. von Neumann and O. Morgenstern. Theory of games and economic behavior. Princeton University Press, 1947.
Bernhard Von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-22) 246, 1996.
Hugh Zhang, Adam Lerer, and Noam Brown. Equilibrium finding in normal-form games via greedy regret minimization, 2022. URL
Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd National Conference on Artificial Intelligence Volume 3, AAAI08,, pp. 1433-1438. AAAI Press, 2008. ISBN 9781577353683.
Martin Zinkevich. Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret min- imization in games with incomplete information. In J. Platt, D. Koller, Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran As- sociates, Inc., 2007. URL / 0
15

---

Published as a conference paper at ICLR 2023
Appendices
Table of Contents
Problem Setting
17
A. Reduction to Normal Form
17
B Solution Concepts
18
Reduced Normal- Form Logit- QREs and MMD
Sequence-Ford Form Background
Proof for Proposition 2.4
19
MMD for Finding Reduced Formal-Forn QREs over the Scquence-Form
20
Proofs
21
D.1
Supporting Lemmas and Propositions
21
D.2
Proof Theoreml3.
22
D.3
Equivalence between MMD MD
23
D.4
Negative Entropy MMD Example
24
D.5
Euclidean MMD Example
24
D.6
Bounding the Gap
25
MMD for Logit-AQREs and MiniMaxEnt Equilibria
26
Experimental Domains
G
QRE Experiments
27
G.1
Full Feedback QRE Convergence Diplomacy
27
2
Black Box QRE Convergence Diplomacy
27
G.3
Full Feedback QRE Convergence EFGs
29
G.4
Full Feedback AQRE Convergence EFGs
30
Exploitability Experiments
31
H.1
Full Feedback Nash Convergence Diplomacy
................................
31
H.2
Black Box Nash Convergence Diplomacy
................................
31
H.3
Full Feedback Nash Convergence EFGS
32
11.4
Black Box Nash Convergence EFGs
33
H.5
Moving Magnet
34
H.6
MaxEnt and MiniMaxEnt Objectives
34
Euclidean Mirror Map Over Logits)
35
H88
MiniMaxEnt Exploitability with Fixed Parameters
................................
36
H.9
Exploitability with Fixed Parameters
36
Atari and Mujoco Experiments
37
Deep Multi-Agent Reinforcement Learning Experiments
37
J.1 Results Averaged Across Seeds
39
K Additional Related Work
40
L Relationship to KL-PPO and MDPO
40
M Future Work
41
16

---

Published as a conference paper at ICLR 2023
A PROBLEM SETTING
In our notation, we use
5 S to notate Markov states,
a; A, notate actions,
0, O notate observations,
h4 Hi U,(0, x A,)' O2 to denote information states (i.c., decision points).
We use
T:Sx A A U {+}) to notate the transition function, where 1 notates termination,
R A notate a reward function,
S A 0; notate an observation function.
AA: [H], A. to notate legal action function.
We are interested in 2p0s games, in which e {1,2) 2] and Vs, (s, = -2((s, a). For conve- nience, we use to notate the player "not v". Single-agent settings are captured as special case in which the second player has trivial action set [A2 1. Normal-form games captured special case in which there is only one state and the transition function only supports termination: Va, supp(T(s, a)) {1). (Here,
supp(X')) denote the support of distribution X'-ie., the subset the domain of X' that mapped to a value greater than zero: {x ((x) > 0}.)
Each agent's goal is to maximize its expected return
E
Σ RS A') (())
using its policy n, which dictates distribution over actions for each information state
: H.; (A.))
In game theory literature, these policies are called behavioral form and assume perfect recall.
We notate the expected value for agent's 's action a; an information state h; at time / under joint policy и as
y (ni, a.) = R.(S, A + R.S" ,A") n. hi,
PSt
Here, the first expectation samples the current Markov state S and the current opponent action A from posterior induced by player i reaching information state h;s when each player uses its part of joint policy determine its actions. The second expectation is over trajectories under the same conditions, with the additional condition that a; the agent's action at the current time step.
A.1 REDUCTION TO NORMAL FORM
Given any game of the above form. we can reduce the game normal form follows. Let I1, denote the set of deterministic policies-i.e. -ie., the set of policies that support exactly one action at a time:
11,
{ Vh, |supp (hx)) = 1}.
The action space of the normal-form game is the space of deterministic policies: À. π. The reward function of the normal-form game is dictated by the expected return of the deterministic joint policy.
Althoughh the actions d. give an equivalent normal- foomal-form representation, many the actions are redundant because actions taken at certain decision points may make other decision points unreachable. The reduced normal-form (a.k.a. reduced strategic form) removes duplicate actions by identifying redundant choices at future decision points that unreachable (Nisan al. 2007). Hereinafter consider the reduced normal-form.
17

---

Published as a conference paper at ICLR 2023
Remark A.I. Any policy TT can be expressed finite mixture policies in II, in a fashion that induces the same distribution over trajectories (against arbitrary, but fixed, opponents). Conversely, any finite mixture over policies in II, can be expressed a policy и, that induces the same distribution over trajectories (against arbitrary, but fixed, opponents).
By the remark above, joint policies in the original game possess counterparts in the normal-form game (and vice versa) achieving identical expected returns. It is in the sense that the normal-form game is equivalent to the original game.
more detailed exposition on this equivalence can be found in Shoham & Leyton- Broon 2008).
B SOLUTION CONCEPTS
Nash equilibria perhaps the most commonly sought-after solution concept in 2p0s games. A joint policy T1, 42 is a Nash equilibrium neither player can improve its expected return by changing its policy (assuming the other player does not change its policy):
Vi, n, E arg max, E Σ R. , 11) n TT-
Note that, in single-agent settings, this corresponds with the notion of an optimal policy in reinforce-
ment learning.
Another solution concept a logit quantal response equilibrium (McKelvey & Palfrey 1995 1998). As only deal with logit quantal response equilibria, generally drop logit and refer them simply as quantal reponse equilibria. In normal-form games, there are multiple equivalent ways to define quantal response equilibrium. One way is using entropy regularization. We say joint policy is an a- -RE in normal-form game if each player maximizes weighted combination of expected return and policy entropy
Vi, arg max,; (R,(A) aH((z) TT, m-
In a temporally-extente game, we say a joint policy is an a-QRE the equivalent mixture over deterministic joint policies is an a-QRE of the equivalent normal-form game.
An alternative way extend QREs temporally extended settings to ask that they satisfy the normal-form QRE condition at each information state:
Vi, Vh, Te(h)) E arg max ((h.))
(..tt,,)Aaa EA-a(((h)) [4 (h4, A) + (T((())))))
(13)
When joint policy satisfies this condition, it is called an agent QRE (as it is as if there is separate agent playing part of normal-form QRE each information state). In single-agent settings, a-AQREs correspond with the fixed point of the instantiation of expected SARSA (Sutton & Barto 2018 in which the policy a softmax distribution over Q-values with temperature a.
The last solution concept that we investigate is called the MiniMaxEnt equilibirum. A joint policy is an M-MiniMaxEEt equilibrium if satisfies condition (3) for MiniMaxEnt Q-values
ya (he a:) E R.(S,AA,, - aH(T((H))) + RSS A²) ) (H((((I))) aH(((HH)) h,
gst
Alternatively, a-MiniMaxEnt equilibria can be defined as the saddlepoint of the o-MiniMaxEnn objective
ERi(H', ( -aH(m(
max min T1
While the name Min novel to this work, the concept has been studied in recent existing work (Pérolat et al. 2021 Cen et al. 202T).
18

---

Published as a conference paper at ICLR 2023
C REDUCED NORMAL-FORM LOGIT-QRES AND MMD
C.1 REQUENCE-FORT BACKGROUND
Nash-equilibrium in a 2p0s extensive-form game can be formulated as bilinear saddle point problem over the sequence form (Nisan et al. 2007)
min max x Ay; DE yEy
where and V are the sequence form polytopes, which equivalently can be viewed as treeplexes (Hoda et al. 2010, Kroer al. 2020). We provide some background on the sequence form in the context of the min player (player 1); the max player follows similarly. Recall all the decision points for player 1 are denoted as Hi] (also known as information states) and the actions available at decision point h E HI1 are A1 (h). Recall that a policy (a.k.a behavioral-form strategy) is denoted as и with Ti (h) (A) being the policy decision point h. For convenience, let T (h, a) denote the probability of taking action E A1 (h) at decision point h. Next we denote p(h) as the parent sequence to reach decision point that is, the unique previous decision point and action taken by the player before reaching h. Note that this parent is unique due to perfect recall and that it possible for many decision points to share the same parent. Then we can construct the sequence form from the top down, where the (h, a) sequence of X is given by
x. (h.a) p(h)) T uh.
For convenience, the root sequence is defined to be the parent of all initial decision points of the game and is set the constant n. 1. We denote xº as the slice of (z((ha)) oz corresponding to decision point h. Note we have the following relationship
x (hh x= /a
Because (hhha)) corresponds to the probability of player I choosing all actions along the sequence until reaching (h, a), we get that x Ay is the expected payoff for player 2 given pair of sequence-form strategies 2, y. Thus the sequence form allows us to get bilinear objective.
Given the bilinear structure of the sequence-form problem, we convert the problem into VI using first-order optimality conditions. order to apply MMD (or other first-order methods), we need good choice of a mirror map for X' and y. A such choice is the class of dilated distance generating functions (Hoda et al. 2010):
xt
(xx)
Σ
Broplhy
th
(14)
KEH,
( (T(())))) Σ
(15)
NeHi
where (Ba)keN, > 0 are per-decision-poing weights and tha is a distance-genenn generatingnnnnggggg function for the simplex associated to If thn taken to be the negative entropy then we say & is the dilated entropy function. In the normal-form setting the dilated entropy is simply the standard negative entropy.
Recently was shown that an a-QRE (for the reduced normal form) is the solution to the following saddle point problem over the sequence form (Ling et al. 2018).
min max an/ (x) + x' Ay 03/2(1), sExt yEy
(16)
where 4/1, a/e are dilated entropy functions with weights B, = 1. Note that we have the normal form a a-QRE as a special case of equation 16
C.2 PROOF FOR PROPOSITION 2.4
Proposition 2.4, Solving normal-form reduced QRE in a two-player zero-sum EFG is equivalent to solving VI F + Vv where Z is the cross-pros cross-product of the sequence form strategy spaces and db is the sum of the dilated entropy functions for each player. The function to is strongly convex with respect to || 1.. Furthermore, is monotone and max., -mooth (A being the sequence-form payoff matrix) with respect to and F + a V is strongly monotone.
19

---

Published as a conference paper at ICLR 2023
Proof. The problem of finding reduced normal-fome logit QRE is equivalent to solving the saddle- point problem stated in equation I6 (Ling et al. 2018). Therefore, due to the convexity of 1/1 and
S and the discussion from Section 2.3
we have that the solution to equation 16 is equivalent to the
solution of V F + V where,
Ay A
Va V V2((1)
F(z)
Vx(2)
(17)
From Hoda al. (2010) we know there exists constants μ11, A2 such that th is fi-strongly convex over A' with respect to || and U/y is ug-strongly convex over y with respect to 11a (Hoda et al. (20T0) do not show bounds these constants, but only need them exist). Therefore, 1 is also strongly convex over Z with constant min with respect to |2|| V 1y since, for
= (2, v). and Æ' = (x',3/) we have
(Vv(z)) Vvb(2), = (2))()) Vibi('),, x'> (Vbz(y)) Vo2(1))
Mıllz z' + +2 -y'l?
min(M1, U2) (I d'1, 1y 1/ 11)
min((,,))))) ='112.
Following Theorem 3.4 it is useful to characterize the smoothness of F under the same norm for which vi is strongly-convex. First, notice that for any matrix A we have that |Ar - Ayll < maxi; |Aij||>> y/1 (see for example Bubeck et al. [ 5.2.4J.. Therefore altogether we
have
FF()) - F(z1)1 = ||y - Ay'll + 11A x - xx113
max |A,j 12 (1y- | x')
1/
max AAg 22| 2- =
showing that F is L maxiy |Asylsmmooth with respect to || ||. The strong-monotonicity of F Vib follows since monotone and Viù strongly monotone since s is strongly convex.
Note that in general the Hessian have unbounded entries (Kroer al. 2020) meaning that V cannot be L-smooth (Beck) 2017). Our MMD algorithm which handles to in closed form allows us to sidestep this issue. We also have that the dual norm of ||- simply |=| / M + |1yl3 (Bubeck ett al. 2015 Nemirovski] 2004).
C.3 MMD FOR FINDING REDUCED NORMAL-FORA. QRES OVER THE SEQUENCE-FORM
From Proposition 2.4 and Corollary D.6 we have that the MMD descent-ascent updates 8 with 4/1,42, taken to dilated entropy with 77 & 9/max,, |A.y1 converges linearly to the solution of equa-
tion 16 The updates, as mentioned by Remark 3.7 can be computed in closed-form as a one-line change to mirror descent with dilated-entropy (Kroer et al., 2020).. Indeed, setting Jt Aye (the gradient for the min player), we have that the update for the min player can be written as follows
1 arg min (119,, x) + m)²((()) + (x;2z))
TeA
arg min <n9: Vib(ar)) + (na + (2)
19t
arg min xex
.x) vb(x)
(1 + n7)
no!
arg min x
, + zp((k) th (o (20h//1)))))
(1 + na)
hell,
ng! (1 na)
Vahaa)) ((h)) th (T()))
(hh)
arg min
Updates can be computed in closed-fomm starting from decision points h without any children and progressing upwards in the game tree.
20

---

Published as a conference paper at ICLR 2023
D PROOFS
D.1 SUPPORTING LEMMAS AND PROPOSITIONS
Proposition D.1 (Bauschke et al. Proposionnn 2.3). Let {2, v} dom v and {u, 8}
int dom tb. Then
1. Bo (u; + (o( = (Vb(u) Vel()), 20 v)
2. (z; = (x; + (o( + (Vo(o) Ve(u), x 8)
3. (2) + (w (, u) + (1 + (v((u) - Ve(o), w>.
The following result is also known as the non- oun-uucidd prox theorem (Beck 2017 Theorem 9.12] or the three-point property property[T'engg 2008).
Proposition D.2. Assume Z closed corvex and both f and to are differentiable at z (defined below).
Then the following statements are equivalent
1. 2 = arg min Kg. 2) + f(z) + (2())))
ZEZ
<ng + V 2. V2 Z
Bx( (x Bx(2,y)
Proof.
2 = arg min (K,,2)
2) f(2) + = (Vb(3) ng Vf((2) -2()),v))))200) - =) V
xEx
(Vp(y) -v(3) (Vv(2) - Ve(v), <Vv((( 8)
- =0 V
(ng + -
Vz 2
(ng + 5 5-2) & B₂(2;y) (2; B (2:1) 22 E 2.
The first equivalence follows by the first-order optimality condition and the last one by Proposition D.I
Lemma D.3. One step of Algorithm all 2,
3.1 under the assumptions of Theorem 3.4 guarantees that, for
Bo(2) & By(2;2) - (e( + (nF((2)) + T7O: Vg((+)))) =- 2411).
(18)
(19)
Proof. Immediate from Proposition D.2
Lemma D.4. Under the same assumptions as Theorem 3.4 2a be the solution to VI(Z, FV
Then, for any Z O int dom v, the following inequality holds
(n)(2)) + na 24 12) - (Bo(2i2)) + (zxii2))
Proof.
(nF(()) 7o 2) = (1F((2) + V)(2) 7)(22)) 17c Vg(zs))
(n)((2+) Vo (2+ 24 2)
(1) (=*)) 24 +nax Vg(2) Vg(=o), - 2)
(1)((E)) na Vol 20 =2
< V)(2)))) Vg(2e), 24 - 2)
na (g(2) - V9(2z), ), 2 2z)
< na (Ve((( - (2(2),, 24
na (Byl (2; 2x) (z( 2))
21

---

Published as a conference paper at ICLR 2023
Note that Vg(2).
Vg(2s), Vi((2. (2()2) are all well-defined because 2* int dom and Assump-
tions (3.2 3.3 The first inequality follows since F is monotone and 2s E sol VI a Vg).
The second iequulityy follows since g is 1-strongly convex relative to & and the last equality by Proposition D.I
D.2 PROOF OF THEOREM 3.4
Theorem 3.4 Let Assumptions 3.2 and 3.3 hold and assume the unique solution ze to VI(Z, F
VVg) satisfies 2* E int dom v.. Then Algorithm 3.1 converges if & To and guarantees
Bx(2z) <
1+ 1++ Bol2ei21).
Proof.
Be(zzi & Bolzziz) Bg (24112)) + (nF(2t) + Vg(z441)) 2++1)
Bolzzi 21) Bx(24112) (nF(2)) nF((2+1)) 2* 2+1) (n (244))1) VoVg(2<41) - =
< (x(2xi2)) 21) - B2(24112) + (nF(2t) -7 2x 2+11 na
+ (26 21+1))
Bo(zxi 24) (+(++1)2)) n/Il= -2+11ll -1+1ll 1/a (2 24) + (z( 21-1)
1 - 2+11 12²L²
(e (x(2+1iz) )
12+ z 1| na (B 15 + Sy(zaizz4)
< Bolzxiz 2)) + Be 24) - na (2441 2n) + ( ((41)
10000 < Bx(x+i2)) - na (2+) B 2++1
The first incquality follows from Lemma D.3 and the second inequality from Lemma D.4 the third inequality by the generalized Cauchy-Schwarz inequality and the smoothness of F; the fourth inequality by elementary inequality ab pa" 8²
2p Vp> 0: and the fifth inequality by the strong
convexity of zb since 2/11 - y/12 < Bv(azy). Therefore altogether we have
Bx(20)241) < (zx)
1 1
Iterating the inequality yields the result.
Corollary D.6. Under the same assumptions Theorem 3.4 if is p-strongly comvex relative to r on
and ip is Pog strongly convex, then if v) & T2, Algorithm
3.1
guarantees
)
Be(z41241) & I+ qpce)
Proof. Observe that + 2t is 1-strongly convex and av
_ is 1-strongly convex relative to J.
mmw
(Vg(z) Vg(v), 4) (Vg(z) Vgly), v)
(20)
uml
(Vb(z) Vu(y), 4)
(21)
Pv (vi(x)) Volv), v).
(22)
22

---

Published as a conference paper at ICLR 2023
Rewriting the update of Algorithm 3.1 in terms of ā and vb gives
arg min 1 1 (<F(z)), + ag(z)) Bx(2;2)
:e2
arg min xE2
(F(2z): 2) (F(z)),
aup
g(z) + Me (x(2)2))
upy
My
arg min "
a s(z)) + 1 Bx((;
Hy
uP6
po
arg min fj (FF))), 2) + auppp(())) + (z((z
arg min 8j (FF()), 2) + ag(z)) + B,( z1)
xE2
The result follows from Theorem 3.4 with stepsize îj
n and ā = p4 py
D.3 EQUIVALENCE BETWEEN MMD AND MD
In this section we show that MMD equivalent to mirror descent (MD) with a different stepsize when an extra regularized loss is added. In the game context this implies that MMD can be implemented as mirror descent ascent on the regularized game with a particular stepsize.
Proposition D.7. Magnetic mirror descent updates ( 7 are equivalent to the following updates respectively (where the second update uses magnet
2++1 arg min ij (z))) + (V(())) 2) + Bo(=;2),
(23)
2
20+1 arg min i7 F((z) + 0z V B (2 2))))))))))))))))))) + (2; =EZ
(24)
with stepsize
I+na
Proof. We begin by proving the first equivalence, between equation (6) and (3
2+11
arg min 77 ((F(z)) 2) ax)(2)) + B,
1 arg min (n Ve)(z,), 2) (1 + (2)
25Z
FF(22) (2+) - V+((2r)
00++1 arg min 2
.2) + x1(2)
1+ 17at
nF(22) naV (2)) Vo(a),, + v12)
474+1 arg min 2t Z
1 1/a
44+1 = arg min (f + (v((22)) - VV(x), 2) + (2))
zEZ
2+++ = arg min ij (F(z)) + VVv((2); 2)+ + B2(2;2)
ZE2
The second equivalence follows from similar steps:
-t+1 arg min 1) ((F(=)), 2) + (B + (z;
2=2
2 arg min (n.) na Vob22) - VV((z), 2) (1 + na))(2)
s62
FF(())) ma Vi(2') VV(EE)
29+++ arg min 262
.2) ++=)
1+ na
F)()))) - Ta0 Vi((2') + Vo(()) Vo(2e), 2) + (2))
211+ arg min zE2
1 1+ 170
+2++1 arg min (1 (F(x) (V)(())))))))))))))))))))))))))) QV)(2)) Vv(2)), 2) 422)
202+1 arg min (1 (F(x.) .V Bp((1)/)) VV(=)) + v12)
#62
2 arg min if (2))) oV Bo 2)+ (x)
262
23

---

Published as a conference paper at ICLR 2023
D.4 NEGATIVE ENTROPY MMD EXAMPLE
KL Divergence to QRE
Simplex Trajectories
Payoff Matrix
Temparsture
10
0.2
R
P
S
10
1.0
R
0
-1
3
10r9
P
1
0
-3
10
S
-3
3
0
00
10
200
400
800
800
1000
Recations
Figure 4: A visualization of convergence in perturbed RPS.
An example showing the simplex trajectories of MMD applied to small NFG is shown in Figure
D.5 EUCLIDEAN MMD EXAMPLE
We discuss the Euclidean case for update equation 6 (update 211 112 we have that update equation reduces to
is similar). In the Eucldiean case were
(F + naa
2t+1
ll
where llz denotes the Euclidean projection onto Z. In the context of solving min max problems
where vb = 4/ + 122 the sum of then the descent-ascent updates of (8 become
D: [ Bc)
T2+1
TTx
+ nj
1/s + 17 ye ( y1)
1e+1 Ily
+ 1ja
Note that results don't ton'tteeuue require bounded constraints in the unconstrained setting there would be no projection step. By Theorem 3.4 the above iterations converge linearly to the solution of
min max xe yey
|10| + f(z. v) 2 lol..
provided f is smooth in the sense that F(x, v) = |V -v
- fff 8)] is smooth.
For example, in the 1-D case we have that the following unconstrained saddle point problem can be solved with Euclidean MMD:
a min max -22 (x ax DER 2
2 y.y
Where a, are constants. In this case F(x,y) = - -, a)l which 1-smooth. Therefore, with stepsize = a the following update rule converges linearly to the solution:
Ft a(y b)
Ve + a(x, - a)
Ti+1
Bt+1
1 a²
1 1 a²
See Figure 5 for visualization with b=
24

---

Published as a conference paper at ICLR 2023
Divergence equilibrium for Euclidean MMD
Trajectories of Euclidean MMD
10P
=02
-=02
=05
15
=0.5
10-2
--
1.0
10
0.5
10.5
10.0
0.5
100
300
400
500
600
0.5
1.0
1.5
2.0
Iterations
Figure 5: Convergence of Fuclidean MMD for the saddle point problem mingeR max yeR xx² + (x
(y 1) yy
D.6 BOUNDING THE GAP
Below we show how Theorem 3.4 can be used to guarantee linear convergence of the gap.
Proposition D.8. Suppose the assumptions of T'Thorrmm 3.4 hold. Moreover, assume that is twice continuously differentiable over int dom vp and 2 is bounded. In that case, there exists constant C and a time step t' such that, for any 2 t.
(zop(2)== (up(F(2)) + a VVg())) 2)
Bo(zazze).
Proof. By Theorem 3.4 we know 2t 2. where {at u {=+] S int dom th Therefore, we have that {2the1 {2 is eventually within a closed ball centered at 2g. That is, there exists t' and a closed ball B such that (athz U {2z} S B s int dom eh. Since B is compact and V2g is B. Therefore, there exists Ln such that [Vg(('') - Vg(z)l & Tall= 2'Il for any z, E B. Setting = F + Vg, we have that, for any z, E B, [G((z) - G(*))l * < Ż| z'1 for L = L + LB.
continuous over B, we have that V V²g(2) is bounded
Then for any e Z, L', denoting sw the solution VI(2, G), have
(G(z), - 2) (G(zz) 2 2 (G(2) G(2+), 2)
(G(ze), 24 =) (G(z)) 2t 2+) (G(z)) G(2*), 2)
E0
& [[G(z))| - 2xl + Tollz z =11 - 2||
([G(Z))]l+ + LD)
1| zn
CV (a))
V (2s
1+ na
where is such that max, 22e2 |z - z'1l & D and C [G(2))ll + LD. The first inequality is by
the generalized Cauchy-Schwarg inequality and the Lipschitz property of G. The second inequality is
by boundedness of Z. The third inequality is by the fact that (2x; 21) > ] 1 2, The fourth inequality is by applying Theorem 3.4 inductively.
Note that we have the following well-known inequality between the saddle-point gap
{(x, v) = max + f(x. Ø) og2(ū) min (g1(#) f(E, u) - -gz(v))
gEy
xeN
25

---

Published as a conference paper at ICLR 2023
and
8 [2) = F()) =V -2),
8=2
as shown below:
E(x, v) max agi (x) f(x, 13 - ag2(ğ) - min + f(3, 2) ag2(y)
yey
+ f(x, ag)(
(1) (agi(x) + f(z, y) ag2(Ui)
+ (agi(z)) + f 00g2 ag2(v)) - (x)) f(x', ()) -agz(u)) for some pair (a', E X x & (x, +V 5/) (Vfx(z,)) + oVgi(a),
(F((2) + a Vg z') for z = (r,z) and z' = (z'.
(g)p(2)
Therefore Proposition D.6 gives guarantee the saddle-point gap E(x, v).
E MMD FOR LOGIT-AQRES AND MINIMAXENT EQUILIBRIA
By Proposition D.2 the MMD update equation 6 restated below, has fixed points corresponding to the solutions of VI( Z, F Vt):
arg min /) (FF(2), + anb(=)) (z(=;2))
Z++1
se2
If 2 is the cross-product of policy spaces for both players (cross product of sets of behavioral-foo form policies) and v is the sum of negative entropy over all decision points (information states), and F includes the the negative q- q-values for both players, then the iteration above reduces to
Te+1 (h.) 7 (0n
with fixed points corresponding to
Vi, Wh, ग. (h:) E arg max ((h,) BA-x((t)) [gx (h,, A) + aH(T((h:))
or, equivalently, the solution to VI(2, F Vvb), which corresponds to logit-AQRE. If F includes the negative MiniMaxEnt Q-values for both players, the fixed point instead corresponds to a MiniMaxEnt equilibrium.
F EXPERIMENTAL DOMAINS
For our experiments with normal-form games, used No-Press Diplomacy stage games. No-Press Diplomacy is seven-player Markov game which players compete to conquer Europe. Because the game is Markov game (which means that the game is fully observable but that the players move simultaneously), each turn of the game resembles a normal- form game. We constructed the normal- form games that used for experiments by querying open source value function (Bakhtin ct al. 2021 in different circumstances for a two-player variant of the game, similarly to Zhang et al. (2022). These games have payoff matrices of shape (50, 50) (game A), (35, 43) (game B), (50, 50) (game C), and (4,4) (game D). We normalized the payoff's of each game to [0, 1].
For our extensive-form games, used the implementations of Kuhn Poker, 2x2 (and also 3x3) Abrupt Dark Hex, 4-Sided Liar's Dice, and Ledue Poker provided by OpenSpiel (Lanctot et al. 2019). Kuhn poker (Kuhn [951] simplified poker game with three cards (J, Q. K). It has 54 non-terminal histories (not counting chance nodes). Abrupt Dark Hex is a variant of the classical board game Hex (Bakst & Gardner 1962). In Hex, two players take turns placing stones onto a board. One player's is goal is to create path of its stones connecting the east end of the board with the west end, while the other player's goal is to do the same with the north end and south end. Dark Hex is variant in which players cannot see where their opponents are placing stones. Abrupt Dark Hex is a variant Dark Hex in which placing a stone in an occupied position results in a loss of turn. The prefix nxn describes the size of the board. 2x2 Abrupt Dark Hex has 471 non-terminal histories. 3x3 Abrupt Dark Hex has too many non-terminal histories to enumerate on our hardware.
Liar's Dice (Ferguson & Ferguson 1991) is dice game in which players privately roll dice and place
26

---

Published as a conference paper at ICLR 2023
bids based the observed outcomes, similarly to poker games. The prefix n-sided means that the players play with 4-sided dice. 4-Sided Liar's s Dice has 8176 non-terminal histories (not counting chance nodes). Ledue Poker (Southey al. 2005) is small poker game with three card values (J, Q. K), each of which have two instances in the deck. It has 9300 non-terminal histories non-terminal histories (not counting chance nodes).
For our single-agent deep RL experiments, we use three Atari games (Bellemare et al. 2013 and three Mujoco games (Todorov et al. (012). We selected these games because Huang et al. 2022 used them to benchmark an open source implementation of PPO.
G QRE EXPERIMENTS
G.1 FULL FREDBACK QRE CONVERGENCE DIPLOMACY
C = 0.05
= 0.1
a: = 0.2
a = 0.5
KL Divergence
10-1
10-1
10
(66))
10-2
10
10-15
111
Iterations
Figure 6: Solving for normal-form QREs in Diplomacy stage games with full feedback.
We perform various QRE experiments under full feedback for Diplomacy stage games. Full feedback means that each player outputs a fully specified policy and receives its exact Q-values (given both players' policies) feedback. Both players then perform the update
For our experiments, we set = a (for each a:) for MMD, which is the maximal value that retains a linear convergence guarantee for normal-form games with max payoff magnitude of one. For PU and OMWU (Cen et al. 202I), we also used the maximal values that guarantee linear convergence. We solved for the QRE for each game using Ling et al. Newton's 's method approach. We show iterations on the r-axis and (soluttion, iterate) on the y-axis. We count each query to the oracle as an iterate, meaning that OMWU uses two iterates for every update (contrasting MMD and PU, which only use one).
The results of the experiment, found in Figure 6 show that all three algorithms converge linearly with faster rates for larger values of alpha, as is guaranteed by theory. We find that, for our Diplomacy games, MMD converges faster than PU and OMWU. However, we found that all three algorithms also exhibited faster convergence with larger than theoretically allowed stepsizes.
G.2 BLACK Box QRE CONVERGENCE DIPLOMACY
Our second set of experiments examine convergence QREs for our Diplomacy stage games with black box feedback. In this context, black box feedback means that each player outputs an action A; sampled from its current policy and that player i receives R(-, Ai, A.;) (but not A_,) as feedback. One way to approach such a setting is to construct an unbiased estimate of the exact Q-values. Letting r be the observed reward
(r/me(as)
if A; a; otherwise
(a())))
0
27

---

Published as a conference paper at ICLR 2023
is such estimate. To see that this is true, observe
T((a;)- R(,,a;, A-i)
E[qi(a;) Tel = EA some
+
Σ te(a))
TT(a))
a
R(. azs Ar)
= EALINE
Te(aa))
Te(a;)
EALINT R(- ai, A-i) =q((a))
In Figure 7 we show results for each of MMD, PU and OMWU, with the exact Q-values replaced by the unbiased estimates ds. For each algorithm, the stepsize at iteration & was set be equal the maximal step size for which there exists an exponential convergence guarantee divided by 10v/. In other words,
10VE
Each line is an average over 30 runs. The bands depict estimates of 95% confidence intervals computed using bootstrapping. Although none of the algorithms possess existing black box convergence guarantees, we observe that they all exhibit convergent behavior empirically. In terms of convergence speed, we observe that MMD compares favorably to PU and OMWU for a (0.05, 0.1, 0.2): however, for = 0.5, OMWU performed the best, with the exception of game D. It is likely that all algorithms could achieve better performance, as we did not perform much hyperparameter tuning.
0.05
0.1
Ct 0.2
a 0.5
KL Divergence
10
10
10
10-2
Camw
Came
280
Iterations
Figure 7: MMD, PU, and OMWU applied to Diplomacy stage games for QRE finding with black box sampling.
We also investigate the performance of other methods for estimating Q-values for the black box setting. One such method uses an unbiased baseline to reduce variance (Schmid et al. 2019 Davis et al., 2020). The premise of this approach is the idea that any quantity that is zero in expectation can be subtracted from an unbiased Q-value estimate without introducing bias. As result, if the quantity is correlated with the estimator, subtracting it from the estimate reduce variance "for free". We call this quantity a baseline. For our bascline, we used
(a.) = (io(aa//T(aa) - (a.))) if a. = A; (a:)
otherwise.
By a similar argument as above, this quantity is zero in expectation
(a,) m. (a,) (a:(a;) (.(a.))
Σ Tt(a)) (a(a.)
((())) T((a,)((a)) (1- xz(a;)) gc(as)
(((a,) (a:):)
0.
Also, if q is close to g. our baseline will be correlated with q. Thus, satisfies our desired criteria. For q. used running estimate of the reward observed after selecting action a, Specifically, every time action a, was selected, we updated
(a,) (1 (a.)) îr.
28

---

Published as a conference paper at ICLR 2023
We used fj 1/2,, inspired by Schmid et al. (2019).
We also investigated the use of biased Q-value estimates, as this is the setting that corresponds with function approximation. For this approach, plugged in q, computed above, instead of the exact Q-values q.
0.05
= 0.1
0.2
0.5
KL Divergence
10
10
10-1
10-1
10
203 I0C 05
1610
233 21C
100
X31
1000
X:30
2010
2013
v00
780
430
KIDI
RED
10:00
Iterations
Figure 8: MMD with no baseline, an unbiased baseline, and (biased) Q-values applied to diplomacy stage games for QRE finding with black box sampling.
We show the results of the experiment if Figure The column shows the temperature for the QRE. The y-axis shows the KI. divergence to the corresponding logit-QRF. The x-axis shows the number of iterations. For each algorithm, the step size iteration was set to be equal to the maximal step size for which there exists an exponential convergence guarantee divided by 10 Each line is an average over 30 runs. The bands depict estimates of 95% confidence intervals computed using bootstrapping. Overall, we find that both using unbiased baselines and biased Q-value estimates appears to improve convergence speed.
G.3 FULL FREDBACK QRE CONVERGENCE EFGs
Kuhn Poker
2x2 Abrupt Dark Hex
Divergence of Dilated Entropy
10
10
10
0.5
2
0.2
10-3
0.1
10
0.05
10-5
10-1
Iterations
Figure Convergence for normal-fort form QREs in EFGs, measured by divergence.
Kuhn Poker
2x2 Abrupt Dark Hex
4-Sided Liar's Dice
Leduc Poker
10P
85
85
Saddle Point Gap
3
U22
10
107*
300
1530
2000
3000
5.00
Iterations
Figure 10: Convergence for normal-form QREs in EFGs, measured by saddle point gap.
29

---

Published as a conference paper at ICLR 2023
We perform several experiments for solving reduced normal-fomn logit QREs by using MMD over the sequence form with dilated entropy. We use the aescent-assenn updates
arg min (V.x, n. (Tx, vi), m) + adl (x)) + B (2)
2 1
wex
V++1 arg max v (VV v. yEy
4) - cnp2(y)) - B (v: yt).
The method is full feedback since Vn, (x4t sequence form payoff matrix. Note in the normal form setting - Ay, and A are the Q-values for both players and the algorithm is the same as described in Section G.1 We set the stepsize to be
Аy, and v. y/s) A ATxr, where A is the
7) m/maxx |A, D) the largest possible allowed from Theorem 3.4 For more details on the sequence
form algorithm, see Section
For Kuhn Poker and 2x2 Abrubt Dark Hex, we used Gambit (McKelvey, Richard D., McL .enann Andrew M., and Turocy, Theodore L. 2016 Turocy 2005) to compute the reduced normal-fore QRE. We check the convergence of MMD by plotting the sum of Bregman divergences with respect to dilated entropy (2 24) By, (Ia; xx) )+ + B (U&: yt), with respect to the solution 2* (Ø y/ observer linear convergence with faster convergence for larger
As predicted by Theorem 3.4
values of a..
For 4-Sided Liar's Dice and Ledue Poker, the games D., McL Andrew M., and Turocy, Theodore I..] 2016 Turocy 2005) to compute the reduced normal-form QRE
large for Gambit (McKelvey, Richard
hardware. Therefore, check the convergence of MMD by plotting the saddle point gap {
V1)) ) of the min max problem given by Ling et al. (0188).
max onhh (ax) + x. Ag - (1)2( min ant (i) + x Ay, anp2(1))- gEy
BEX
Theorem 3.4 guarantees that the gap will converge to zero. Note the gap is zero if and only the solution and, by Proposition [.6]] the gap also guaranteed converge linearly. In both 4-Sided Liar's Dice and Ledue Poker we observe linear convergence of the gap, with faster convergence for larger values of a. Additionally, due the Ollog(t) regret bound from Duchi al. (2010), we have
that the gap is guaranteed to converge at rate of O log(() for the average iterates of both players.
G.4 FULL FEEDBACK AQRE CONVERGENCE EFGs
Next, we investigate whether MMD can be made to converge to AQREs in extensive-form games. For these experiments applied MMD behavioral form, as described in Section E Specifically, we computed qi (h:) for each player i and each information state h4. Then, we applied the update rule
t++1 (h:) [T (h, "9 (ha))
for each player i and information state h4 For each setting, used
10
2x2 Abrupt Dark Hex
Kuhn Poker
4-Sided Liar's Dice
Leduc Poker
10"
Mean KL Divergence
10-1
a 0.5
10
0.2
10-3
0.1
10-4
0.05
10-6
10-6
Iterations
Figure 11: Solving for AQREs in EFGs.
We show the results Figure II We measure convergence against solutions computed using Gambit (McKelvey, Richard D.,, MeLennan, Andrew M., and Turocy, Theodore I.. 2016 Turocy 2010).
30

---

Published as a conference paper at ICLR 2023
Despite lack of proven convergence guarantees, observe that MMD converges to the AQRE in each game, for each temperature. While the convergence is not monotonic, it is roughly linear over large time scales.
H EXPLOITABILITY EXPERIMENTS
Next, we investigate the convergence of MMD as a Nash equilibrium solver. To induce convergence, most of our experiments, we anneal the temperature of the regularization over time.
H.1 FULL FEEDBACK NASH CONVERGENCE DIPLOMACY
In our full feedback Nash convergence Diplomacy experiments, we used
= 5vt
10"
We show the results of the experiment in Figure 12 Over short iteration horizons, we observe that CFR tends to outperform MMD. However, for longer horizons, we find that MMD tends to catch up with CFR. In game D, the qualitatively different behavior is likely to due the fact that the Nash equilibrium is a pure strategy, unlike the Nash equilibria of the first three games, which are mixed.
Game A
Game
Game C
Game
10-1
10
Expbtablity
2
10
20
MMD
CFR
-5
107
107
10"
10"
100
107
107
10"
10"
10'
107
10"
10f
107
107
107
107
10*
Iterations
Figure 12: MMD and CFR applied to diplomacy stage games for computing Nash equilibria.
H.2 BLACK BOX NASH CONVERGENCE DIPLOMACY
For our black box Nash convergence experiments, we compare against the "opponent on-policy" variant of Monte Carlo CFR (Lanctot al. 2009). In this variant, the two players alternate between an updating player and an on-policy player. The updating player plays off-policy according to policy that provides sufficiently large support to each action (in our Diplomacy experiments we used uniform policy). The advantage to this setup is that it guarantees that the updating player will receive bounded gradients, which necessary for Monte Carlo CFR's 's convergence proof. In contrast, we show results for an on-policy Monte Carlo variant of MMD, despite the fact that this causes unbounded gradients. This is not fair comparison in the sense that the same "opponent on on-policy" setup is equally applicable to MMD and would keep the gradients bounded, whereas the "on-pooicy" version of Monte Carlo CFR does not converge. We made this decision because the on on-policy Monte Carlo variant of MMD is simpler and more elegant. Nevertheless, believe that the "opponent on-policy" version of MMD remains an interesting direction for future, and would very possibly yield faster convergence.
We again investigated three ways of estimating Q-values. For our unbiased estimator with no baseline used
1
20
Ti = 5vi
at =
VL
for games A, B, and C, and
1
Th Vt
Vt
31

---

Published as a conference paper at ICLR 2023
for game D. For our unbiased estimator with baseline, used
10
1/8
10v8
a
Vt
for games A, B, and C, and
1
1/1
vt
a4
V
for game D. For our biased estimator, we used
M/ 5vt
0t
for games A, B, and C, and
1h
Vi
for game D. We show results in Figure 15 confidence intervals computed from bootstrapping.
with averages across 30 runs and estimates of 95 %
Game A
Game
Game
Game
111
367
Itarations
Figure 13: MMD and OS-MCCFR applied to diplomacy stage games for computing Nash equilibria with black box sampling.
For MMD, we observe that biased Q-value estimates generally perform best, followed by an unbiased estimate with baseline, followed by an unbiased estimate without baseline, except on game D, where the unbiased baseline performs similarly to biased Q-value estimates. We also find that CFR tends to follow this trend, though the difference between biased Q-value estimates and an unbiased baseline less pronounced, except game D, where the unbiased baseline performs poorly. Between MMD and CFR, CFR tends to perform better on an estimator-to-estiman though MMD is relatively competitive with CFR under biased Q-value estimates. For game D, observe that this comparison is more favorable for MMD than the other games.
basis in games A, B and C,
H.3 FULL FEEDBACK NASH CONVERGENCE EFGs
For our full feedback Nash convergence EFG experiments, we examined variants of MMD. The first, which we call unweighted MMD, corresponds with the version tested in the AQRE experiments
(f.)) (bel) ( 1/(1+na)),
The second, which we call weighted MMD, uses
ne (m, pr (he) (/1 (t
In other words, it weights the stepsize of the update by the probability reaching that information state under the current policy. We test this variant because it corresponds with a "determinized" version of black box sampling for temporally extended settings.
For unweighted MMD, we used
1
17
VE
C4
V
for Kuhn Poker.
1
=
VE
32

---

Published as a conference paper at ICLR 2023
for 2x2 Dark Hex,
2
1
7)
vt
vt
for 4-Sided Liar's dice, and
1
5 Vt
111
04
Vt"
for Leduc Poker. For weighted MMD, we used
2
2
1/1
v8
00
Vt
for Kuhn Poker,
1
1}:
Vt
vt
for 2x2 Abrupt Dark Hex,
100
2
Vt
Or
Vt
for 4-Sided Liar's Dice, and
500
10
Vl
Vt
for Ledue Poker. Note that larger stepsize values required for weighted MMD to achieve competitive performance because, otherwise, the reach probability weighting would make updates at the bottom of the tree very small.
Kulni Poker
Abrupt
4-5kied Liar's Dice
Leduo Poker
1011
Jamegghho MMO
Und sutpridd
107
100m
30"d
Mird rudgghok
107
00
10
12
107
Iterations
Figure 14: MMD (unweighted) and MMD (weighted by reach probability) compared against CFR across standard OpenSpiel games.
We show the results of our experiments in Figure 14 unweighted MMD exhibit convergent behavior. Furthermore, they converge at rates comparable with CFR on average across the games.
We find that both weighted MMD and
H.4 BLACK BOX NASH CONVERGENCE EFGS
For our black box Nash convergence EFG experiments, we used the Monte Carlo CFR implementation in OpenSpiel (Lanctot et al., 2019), which uses an update policy with 0.4 weight on the current policy and 0.6 weight on the uniform policy. For MMD, we used the sampling version of weighted MMD, meaning that the information states touched during the trajectory are updated with the full stepsize, while information not touched during the trajectory are not updated. For Kuhn Poker, we used
50
10
04
Vi
For 2x2 Abrupt Dark Hex, we used
7
50
th
20 1
vt
For 4-Sided Liar's Dice, we used
2
200
T)t =
V
VE
33

---

Published as a conference paper at ICLR 2023
For Ledue Poker, used
1 vt
300
7]
Vt
Noting again that the caveats about comparing on-policy MMD to opponent on-policy Monte Carlo CFR also apply here, we present the results in Figure 14 and shown with 95% confidence intervals estimated from bootstrapping. As in the normal-form experiments, we find that Monte Carlo CFR generally outperforms MMD for unbiased gradient estimates with no baseline.
Results are averaged across 30 runs
Kuhn Poker
2x2 Abrupt Dark Hax
4-Sided Liar Dice
Expletabiiy
307
10122
0RAMOOF
081
107
107
101
L17"
Lf
10F
10P
101
10!
10P
10
107
10
Ieeations
Figure 15: MMD compared against OS-MCCFR across standard OpenSpiel games with black box sampling.
H.5 MOVING MAGNET
Next, we investigate using moving magnet, rather than an annealing temperature, to induce convergence Nash equilibrium. In the moving magnet setup, updates take the form
Te (h.) phs) (h,"" " e ( (1)pp/(+te))
where Ar slowly trails behind ny. In our experiment, we used
Pi+ (h. "
For each game, we used a 1, 0.1, f 0.05.
2x2 Abrupt Dark Hex
Kuhn Poker
4-Sided Liar's Dice
Leduc Poker
MMD (Annealing
Exploitabiiit
10a
Temperature)
10-1
MMD (Maving
10-2
Magnet)
CFR
10-4
10-5
CFR+
10-t
10
10
10
10
10
10at
10"
10.
102
10"
10
10 102 10 10²
Iterations
Figure 16: Comparing a moving magnet to an annealing temperature.
We show the results in Figure 16 compared against CFR and MMD with an annealing temperature before). Encouragingly, we find that that moving the magnet
(with the same hyperparameters behind the current iterate also appears to induce convergence, Furthermore, convergence may occur much faster rate than that which is induced by annealing the temperature.
H.6 MAXENT AND MINIMAXENT OBJECTIVES
Next, we examine the convergence properties of other related objectives. We consider two different types. One involves an information state entropy bonus, wherein (H(()))))) is added to the reward for player for reaching information state hg- This corresponds with maximum entropy objective in reinforcement learning (Ziebart et al.] 2008); we call this objective MaxEnt. The second involves simultaneously giving information state entropy bonus (like MaxEnt), while also penalizing the
34

---

Published as a conference paper at ICLR 2023
player with the opponent's information state entropy. This second approach can be viewed modification the first approach that makes the game zero-sum. It is the objective that was examined Pérolatt et al. (202T). We call this objective MiniMaxEnt.
For each algorithm, we used
1
1h
vl
1/
for Kuhn Poker,
1
Vi 10 = 4
for 2x2 Dark Hex,
2
1
11t
v1
00
VL'
for 4-Sided Liar's Dice, and
Tht
01
Vl
Vl
for Ledue Poker.
Abrupt
107
Eipotabiity
1983 Japiccas
1oml
1047 Mari
10-4
1007 Morrd
10"1
10
10"
107
10a
107
-07
10
10"
101
107
10
127
307
10'
10"
101
10'
107
10"
107
Iterationa
Figure 17: Comparing different objectives.
We show the results in Figure We find that MMD exhibits convergent behavior with each of the
objectives.
H.7 EUCLIDEAN MIRROR MAP OVER LOGITS
Next, we examine an instantiation of MMD that optimizes the logits using Euclidean mirror map (wb 1 122 discussed in Section D.5 this approach is given by
rather than reverse KL regularization. The update rule for
1
(h+) arg max, <V EE an (bi, ()
11 ((hi)11
|| ze (h+))
2n
where (h(,,) softmax(2; (h:)) and Ç is the magnet. The closed form is
(h+) 2h)) + v so (h;, ())www, + on)()))
1 an
We test the convergence Euclidean MMD for Leduc poker, using
2
1
VE
VE
We show the results in Figure 18 We find that Euclidean MMD also exhibits convergence behavior in Ledue poker. However, convergence may be slower than the negative entropy variant.
35

---

Published as a conference paper at ICLR 2023
Leduc Poker
100
Negative Entropy
Exploitability
Euclidean
GFR
10-1
10-2
10
10a
10a
10
10
Iterations
Figure 18: Comparing different mirror maps.
H.8 MINIMAXENT EXPLOITABILITY WITH FIXED PARAMETERS
Next, we examine using MMD for the purposes of computing MiniMaxEnt equilibria. For each temperature a, used a/ '10. We show the results in Figure 19 In the figure, convergence measured terms of exploitability in the entropy regularized game. Similarly to our AQRE results, find that, althought convergence non-monotonic, the empirical rate appears roughly linear over long time scales. This is the first empirical demonstration of convergence in MiniMaxEnt exploitability EFGs.
2x2 Abrupt
Kuhn Poker
4-Sided Liar's Dice
Leduc Poker
Dark Hex
10a
MiniMaxEnt
Exploitability
10-1
a=0.5
0=0,2
10
0=0.1
a=0.05
10
20,000
40,000
20,000
40 10:000
20,000
40,000
20,000
43,000
Iterations
Figure 19: MiniMaxEnt exploitability with fixed parameter values.
H.9 EXPLOITABILITY WITH FIXED PARAMETERS
our AQRE and MiniMaxEnt experiments, we observed that MMD exhibits convergent behavior to AQREs and MiniMaxEnt equilibria with fixed parameter values. It follows that MMD achieve relatively good exploitability values without using any scheduling. We show these results in Figure
20
and Figure
2x2 Abrupt Dark Hex
Kuhn Poker
4-Sided Liar's Dice
Leduc Poker
Exploitability
10a
0.5 a
10-1
0.1
0.05
10-2
Iterations
Figure 20: Convergence with fixed hyperparameter values under an expected return objective.
36

---

Published as a conference paper at ICLR 2023
2x2 Abrupt
Kuhn Poker
4-Sided Liar's Dice
Leduc Poker
Dark Hex
Exploitability
10
0=0.5
0=0.2
0=0.1
000005
20.000
40.000
25,000
40,000
20,000
Iterations
Figure 21: Convergence with fixed hyperparameter values under a MiniMaxEnt objective.
I ATARI AND MUJOCO EXPERIMENTS
For our single-agent deep RI. experiments, we implemented MMD as a modification to Huang et al. implementation of PPO. For Atari, we added a reverse KL penalty with a coefficient 1/1 0.001; we kept the temperature as the default value set by Huang ct al. 2022) (a = 0.01). For Mujoco, we added a reverse KL penalty with a coefficient 1/4, 0.1; we added an entropy bonus (Huang et al. (2022) do not use an entropy bonus) with value of a = 0.0001. Otherwise, for both Atari and Mujoco, the hyperparameters were set to those selected by Huang et al. (2022). We show the results again in Table convenience. The baseline results for PPO are copied directly from Huang et al. (2022). The exact numbers should be interpreted cautiously as they are averaged over only three runs, leaving high levels of uncertainty. That said, the results in Table provide evidence that MMD can perform comparably to PPO. But, even without looking at empirical results, the idea that a deep form of MMD can perform comparably to PPO should not be surprising, MMD be implemented in a way that resembles PPO in many aspects.
Table 1: Atari and Mujoco results averaged over runs, with standard errors.
Breakout
Pong
BeamRider
Hopper-v2
Walker2d-v2
HalfCheetah-v2
PPO
409 + 31
20.59 0.40
2628 + 626
2448 t 596
3142 + 982
2149 + 1166
MMD
414 + 6 21.0 + 0.00
2549 + 524
2898 + 544
2215 + 840
3638 + 782
J DEEP MULTI-AGEN REINFORCEMENT LEARNING EXPERIMENTS
For our deep multi-agent reinforcement learning experiments, we implemented MMD as a modifi- cation to PPO, as implemented by RLlib (Liang et al., 2018). This involved changing the adaptive forward KI regularization to a constant reverse KL. regularization and setting f)t a according the following schedule
10 million
aa = 0.05g 10 million
7/ = 0.05
1
where is the number of time steps steps-not not the number of episodes. Otherwise, we used the default hyperparameters. We also show results for PPO, using RLlib's default hyperparameters. We ran these implementations in self-play using RLlib's OpenSpiel environment wrapper, modified work with information states, rather than observations. For NESP (Heinrich & Silver 2016), we used the same hyperparameters those found the NFSP Ledue example in the OpenSpiel codebase. For the best response, we used the OpenSpiel's 's DQN best response code, without modifying any hyperparameters. We ran the best response for 10 million time steps and evaluated all match-ups over 2000 games (with each agent being the first-moving player in 1000).
There are two caveats to consider in interpreting these experiments. First, is likely that RLlib's default PPO hyperparameters are generally stronger than the default hyperparameters for NFSP in the OpenSpiel. In this respect, the results we present may be unfair to NESP. Second, RLlib's 's OpenSpiel wrapper does endow agents with knowledge about which actions action is selected, the agent is given a small penalty and a random legal action is executed. In contrast, OpenSpiel's implementation of NFSP uses information about the legal actions to perform masking.
legal-instead, instead, if an illegal
37

---

Published as a conference paper at ICLR 2023
3x3 Abrupt Dark Hex
Phantom Ta--Tc--To
Approximate Exploitability
1.0
Exploitee
MMD
NFSPIOpeeSSiee))
PPO(RLibb
Arbilrary
0.1
million
10 million
millon
millinn
Exploitee Training Steps
Figure 22: Approximate exploitability experiments.
In other words, MMD and PPO face a harder version of the game than NESP faces. In this respect, the results present are unfair MMD and PPO.
We ran five seeds of each algorithm and checkpointed the parameters after both million time steps and 10 million time steps. Because these games are too large to compute exact exploitability, show results for DQN (Mnih et al. 2015) instances trained to best respond to each agent. For our DQN implementation, we used OpenSpiel's rl rl_response implementation. We did modify any hyperparameters and ran DQN for 10 million time steps in all cases. We show results for the final DQN agent evaluated over 2000 games (1000 with DQN moving first and 1000 with DQN moving second) rounded to two decimal places. We also include results for bot that selects actions uniformly random (Random) and bot that determinisically selects the first legal action (Arbitrary). These results of this experiment are presented in Figure
In the games, the return for a win is and the return for loss is -1; in Phantom possible to tie, in which case the return is O. Thus, approximate exploitability of I would mean that DQN defeats the agent 100% of the time, whereas an approximate exploitability of would mean that DQN ties in expected value against the agent. As might be expected, we observe that playing an arbitrary deterministic policy (purple line) is perfectly exploitable by DQN in both games. In contrast, while playing uniformly at random (red line) is also highly exploitable, it is less because of the randomization.
it also
Among the three learning agents, one trend is that PPO with RLlib's default hyperparameters does not appear to decrease exploitability over time. This is not necessarily surprising, as RL algorithms do generally converge in two-player zero-sum games. On the other hand, both NFSP with OpenSpiel hyperparameters and MMD exhibit clear downward trends over time. Again, this is not necessarily surprising, as both MMD and NFSP are designed with exploitability in mind.
Among the learning agents, in terms of raw value, MMD exhibits substantially stronger performance than the baselines. Indeed, even after 1 million time steps, every seed of MMD is less exploitable than any seed of the baselines after either million or 10 million time steps. In contrast, the learning agent baselines do not substantially outperform uniform random play in Phantom Tic-Tac-To Toe and only NFSP after 10 million time steps substantially outperforms uniform random play in 3x3 Abrupt Dark Hex.
We also show results for head-to-head matchups between the agents in Figure 23 For all learning agents, we use the 5 seeds that were trained for 10 million time steps. For matchups between learning agents, we each seed of each agent against each other (for total of 25 matchups) for 2000 games (1000 with each agent moving first) and rounded to the nearest two decimal places. For matchups between learning agents and bots, we each seed of the learning agent against the bot (for a total of 5 matchups) for 2000 games (1000 with each agent moving first) and rounded to the nearest two decimal places. We show the results in Figure
38

---

Published as a conference paper at ICLR 2023
Each learning algorithm's 's results denoted by x-axis label; the hue denotes the opponent not the agent being evaluated. Because the games are zero-sum matchup results are negations of each other. For example, in the 3x3 Abrupt Dark Hex column, the orange boxplot (L.e., opponent=NFSP) above the MMD label is the negation of the blue boxplot (i.e., opponent=MMDD) above the NFSP label.
One observation from the results is that MMD outperforms the baselines and the bots uniformly seeds. This encouraging in the sense that having low approximate exploitability appears to lead to strong performance in head-to-head matchups. Like MMD, the NESP seeds win head-to-head matchups against the bots. On the other hand. PPO exhibits much higher variance- tends to lose against the bot selecting the first legal action in Phantom Tic-Tace Tac-Toe, but tends to defeat it by the largest margin in 3x3 Abrupt Dark Hex.
3x3 Abrupt Dark Hex
Phantom Tic-Tac-Toe
1.00
Expected Return
0.75
Opponent
MMD
0.25
NFSP/OpenSpiel)
0.00
PPO(ALIib)
Random
-0.50
Arbitrary
-0755
MMD
NFSP(OpenSpiel) PPO(RLIB)
MMD
NFSP(OpenSpiee) PPO(RLIb)
Figure 23: Hcad-to-head experiments.
J.1 RESULTS AVERAGED ACROSS SEEDS
Table 2: Approximate exploitability and standard error in units of 10 over seeds.
3x3 Abrupt Dark Hex
Phantom Tic-Tac-Tos
First Legal Action Taker
100 =
100 t
Uniform Random
74 + 1
78 = 0
PPO(IM steps)
85 + 6
89 + 6
PPO(10M steps)
100 +
90 + 4
NFSP(IM steps)
91 + 4
95 + 1
NESP(10M steps)
59 1
78
MMD(IM steps)
34 2
37 + 1
MMD(10M steps)
+
15
Table 3: Head-to-head expected return in 3x3 Abrupt Dark Hex for column player and standard error units of 10-2
Arbitrary
Random
PPO
NFSP
MMD
Arbitrary Random
0
0
92
45 +
66
+ 2
0
56 + 3
57 +
66 +
PPO
-92
3
0
3
13
NFSP
9
-57
-443
0
12 +
MMD
-66
-66
2
+
0
39

---

Published as a conference paper at ICLR 2023
Table 4: head- expected return in Phantom Tic-Tac-Toe for column player and standard error in units of 10
Arbitrary
Random
PPO
NFSP
MMD
Arbitrary Random
-22 2
-28 24
41 10
36 + 2
-2
28 1
46
57 +
PPO
28 - 24
-28 +
3 3
30 +
NFSP
+
-46 2
-3+3
+
MMD
2
-57 0
-30
27 +
0
K ADDITIONAL RELATED WORK
Average Policy Deep Reinforcement I Learning for Two-Player Zero-Sum Games One class of deep reinforcement learning methods for two-player zero-sum games, which includes NESP (Heinrich) & Silver 2 and PSRO (Lanctot al.) 2017). scales oracle-based approaches (Brown) 1951 McMahan et al. )003) by using single-agent reinforcement learning as a subroutine to compute approximate best responses. While this class of methods is very scalable, it require computing many best responses (McAlerr et al.] [021]. making very slow in some cases. MMD differs from this class in that it does not historical policies. Another class of methods, which includes deep CFR (Brown et al. 2019) and double neural CFR (Li al. 2020). is motivated by scaling CFR (Zinkevich et al. 2007 the dominant paradigm in tabular settings-to function approximation. Unfortunately. the sampling variant of CFR (Lanctot al., 2009) requires importance sampling across trajectories, making straightforward extensions to stochasticity (Steinberger et al., (020) difficult to apply to games with long trajectories. though more recent extensions may make progress toward resolving this issue (Gruslys al. 2021). MMD differs from this class both in that it neither requires policy averaging nor importance sampling over trajectories.
best response subroutine and in that it does not averages
L RELATIONSHIP TO KL-PPO AND MDPO
On the single-agent deep reinforcement learning side, MMD most closely resembles KL-PPO (Schul man et al. 2017) and MDPO Tomaar et al. 2020 Hsu et al. 2020 8 KL-PPO uses the policy loss function
T(a st)
E,
A. aH(T(s:)) - (KL((a ((s:))
(a st)
where A, is an advantage function (a learned estimate of Jr, (st, ax) Ur, (st)). In expectation, the first term acts as (#+(*e): 97, (st)), which the first term MMD's loss function. The second term is the same entropy bonus as exists in MMD's loss function, using uniform magnet with negative entropy mirror map. However, unlike MMD, KL-PPO's KL regularization goes forward KL( (S)), (s:)). In contrast, MMD's KL regularization goes backward (L(T(s;), Tau (s:)). Hsu et al. 2020) investigated modifying KL-PPO to use reverse KL regularization instead forward KL Mujoco and found that the two yielded similar performance.
MDPO uses the policy loss function
[ 8t). A. (KL((T())), mata(se)) Tata(aa 8t)
E2
where A, is the approximate advantage function (a learned estimate of qn (St, a.) Us (st)). In the context of a negative entropy mirror map and uniform magnet, MDPO differs from MMD in that does not necessarily include an entropy regularization term (F((T(s))) (s))); ;) in the case that does include such an entropy term, MDPO and MMD coincide.
MMD with negative entropy mirror map and a uniform magnet takes the form
( st)
E,
Å. aH((T(s:) (KL(((ss), Toua(s:)))
Folu az st)
where 3 acts as an inverse stepsize.
Hsu al. 2020
investigate MDPO under the PPO KT..
40

---

Published as a conference paper at ICLR 2023
M FUTURE WORK
Our work opens up a multitude of important directions for future work. On the theoretical side, these directions include pursuing results for black box sampling, behavioral-form convergence, convergence with annealing regularization, convergence with moving magnets (Lin et al.
2017 Allen-Zhuj 2017))
and relaxing the smoothness assumption relative smoothness (Lu al., 2018 Bauschke al. 2017) while removing strong convexity assumptions. On the empirical side, these directions include constructing an adaptive mechanism for adapting the stepsize, temperature, and magnet (Badia et al.) 2020. Fan & Xiao, 2022). pushing the limits of MMD as a deep RI. algorithm for large scale 2p0s games, and investigating MMD as an optimizer for differentiable games (Goodfellow et al. 2014
Fan
Letcher et al. 2019).
41


Reviews:
[{"review_id": "Ot9fye8AcQg", "reviewer": "Reviewer_UyUG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper introduces an iterative optimization algorithm based on mirror descent that demonstrates competitive performance in reinforcement-learning tasks while provably converging to (logit) quantal response equilibrium in both normal-form and extensive-form two-player zero-sum games. The key idea of this algorithm - called Magnetic Mirror Descent (MMD) - appears to be to model these scenarios as variational inequality problems with monotone G operators that admit efficient optimization. The authors generalize a non-Euclidean proximal gradient method for this purpose. After formally proving the convergence in Theorem 3.4, the authors present a series of experimental results to substantiate their claims. First, they evaluate the convergence to quantal response equilibrium against Predictive Update and Optimistic Multiplicative Weight Update methods. In the second experiment they leverage the logit correspondence to reach Nash equilibrium and compare the speed of convergence over iterations to CFR. The last two experiments consider reinforcement-learning, either in single-agent setting, against PPO,  or in multi-agent setting, against NFSP.\n", "summary_of_the_review": "This appears to be a theoretically well grounded paper that presents a new algorithm for solving variational inequality problems. It reads well and the theoretical results seem correct to me. I would appreciate if the empirical section considered more baselines to better evaluate the algorithm's performance though. ", "strength_and_weaknesses": "This is a highly technical work with an extensive appendix. The text reads relatively well, given the degree of technicality, and the authors seem to exert great effort to position their work in other literature on the topic. Still, I can't shake the feeling this paper would benefit from more carefully developed exposition, with more examples in the main text, and more detailed discussions on the introduced concepts. I understand this is not possible given the space limits. \n\nIn the short timeframe given by ICLR for reviewing I attempted to go through some of the theoretical results and I did not spot any obvious errors. I find Theorem 3.4 to be a nice result. Reiterating my previous concern regarding limited space dedicated to discussions though, I wonder how strong this theorem’s assumptions are in practice, especially in the context of reinforcement-learning problems. From the game-theoretic perspective, I also fail to find any other solution concept that would admit a VI formulation besides (logit) QREs. Are there some, for example, refinements of Nash equilibrium the authors know of that would be computable via MMD?\n\nIn addition, I remain confused about the convergence rates. The text mentions at multiple points the exponential convergence to QRE, yet the abstract and other parts claim linear convergence? What am I missing?\n\nFor completeness, I believe it would be also fair to discuss which Nash equilibria are actually reachable as limits of logit quantal response equilibria, i.e., to mention the convergence is pointwise to the best response if it is single valued, otherwise all actions in the best response are played with equal probabilities. \n\nFinally, I also wonder why the authors did not compare their approach to other QRE-based algorithms like ADIDAS in normal-form games, since it is readily available in OpenSpiel? Why there is no comparison to other QRE algorithms in extensive-form games like the algorithms of Farina et al. or Ling et al. which this work refers to? Why is the comparison in the second experiment done with respect to CFR and not to (at least) CFR+? Also, how time consuming is one iteration of the MMD in contrast to other iterative algorithms mentioned in this work, i.e., how would the reported results look like with a temporal x-axis instead of plotting over iterations?\n\n\nA few nitpicks:\nThe graphs in Fig 2 are missing y-axis labels.\nWhich quantity exactly is reported in Table 1? Are these utilities?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KOpRoMvowcV", "reviewer": "Reviewer_Mj5Y", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper presents a method, Magnetic Mirror Decent, which can get comparable performance to state of the art in both single-agent and multi-agent RL settings.  To the best of my knowledge it is the first algorithm known to have such strong empirical performance in both settings, and to have strong theoretical convergence guarantees in both settings.", "summary_of_the_review": "This paper has the potential to be very impactful to the field, as such I am recommending acceptance.  However, it is quite dense, to some extent unavoidably.  I believe this can be mitigated to some extent, to allow the central result to be accessible to more readers. ", "strength_and_weaknesses": "Strengths:\n* Provides the first algorithm to get empirically strong performance in both single-agent and multi-agent RL settings\n* The theoretical convergence guarantees of magnetic mirror decent is the first time such guarantees have been shown in 2 player zero sum games with a first order solver.\n\nWeaknesses:\n* The biggest weakness of this paper is the clarity.  Given the subject matter, this is not the fault of the authors, but the authors themselves seem to be aiming for a broader audience than this paper is accessible to:\n ``\n We hope that, due to its simplicity, MMD will help open the door to 2p0s games research for RL researchers without game theoretic backgrounds.\n '' \nI believe, how the paper is written now, such researchers would have find it difficult to understand the core method or contribution.  I think this is a challenging goal to set, but I think the authors are right to aim for it.  Given that this paper has the potential to be seminal, it could be the starting point for many RL researchers aiming to understand this subfield, it would be best if the paper offered enough direction for those researchers to be successful in understanding it.\n\nI appreciate that the authors have already put some effort into doing this, it is claimed that Section 2.2 - Section 3.1 can be skipped.  However, there are a few points this misses:\n* variables used in 3.2 are not defined if Section 2.2-3.1 are skipped (eta, zeta, psi)\n* The term \"magnet policy\" is never explained even informally\n* The core reason why the intuition as to why this approach works where other approaches have failed is not clear\n\nThere are also bits of prior knowledge that are assumed from readers: \n* the term ``behavioral strategies'' is used but not explained\n* It's not initially clear from context that the Gambit engine on page 6 is only used to measure performance of the algorithm, rather than as a part of the algorithm itself.\n* The term \"regularized equilibria\" is used without explanation \n\nFinally, within Section 2.2-3.1, it would be good to be accommodating to those readers as well, at least in having a short summary that outlines the main sections of the argument.  Ideally this would highlight what the key change is that other methods missed.  For instance, just flagging that you will cast it to a variational inference problem, show a dynamical system which converges to the solution of that variational inference problem, and then noticing that that dynamical system factors into separate updates.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "D5BondMcK9S", "reviewer": "Reviewer_8q9G", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes an algorithm, magnetic mirror descent (MMD), for RL problem and 2p0s games. Sound theoretical results are obtained for the algorithm. Empirically, MMD exhibits desirable properties as a tabular equilibrium solver, as a single-agent deep RL algorithm, and as a multi-agent deep RL algorithm.", "summary_of_the_review": "The idea to deal with RL and games in a unified way is good, and the algorithm proposed enjoys linear convergence. However, it seems that the improved convergence rate compared with existing approach results from stronger assumption. The authors are expected to provide more insights of the algorithm and the novelty of the algorithm and its analysis scheme.", "strength_and_weaknesses": "Strength: \n1.\tThis paper provides a unified perspective to view the RL problem and 2p0s games and proposes an algorithm to solve it. \n2.\tThe theoretical results are strong and some results are attained for the first time as the authors claim.\nWeaknesses:\n1.\tThe algorithm seems not to be of novelty. Maybe the contributions mainly lie in the analysis. \n2.\tThe paper is not well organized, and the problem is not highly motivated. The comparisons with existing and the idea behind the algorithm are not clearly presented. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2QUC0mcTTEw", "reviewer": "Reviewer_BKWB", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposed MMD, a variant of MD with an extra \"behavior cloning\" term, to unify single-agent RL and Two-Player Zero-Sum Games. The method is shown to converge linear in a functional sense. Some numerical experiments are provided to justify the algorithm. ", "summary_of_the_review": "Overall I think the current revision lacks a strong motivation. Given other concerns mentioned before, I recommend reject. ", "strength_and_weaknesses": "Strength: \n - The paper is generally well written, with complete theory and numerical experiment details.\n\nWeaknesses: \n - My biggest concern is about the motivation of designing a single RL algorithm for both single-agent RL and 2p0s. Extending single-agent methods to 2p0s seems reasonable for me: many 2p0s methods are at least inspired by single-agent methods. But the other way does not look reasonable since if we know we are solving single-agent RL, why bother using 2p0s methods? I think the authors need more elaboration on this. \n - Another concern is the novelty of the proposed method. MMD in (10) seems to add a “BC” term $KL(\\pi, \\rho)$ beyond MD, which from my understanding helps stabilize the algorithm in the single-agent setting (most works from offline paper adopted a similar idea: TD3-BC, BCQ, SCORE, etc). In 2p0s, this term seems to drive the policies toward an equilibrium in a uniform sense. In terms of the proof, it follows a standard MD proof on the functional level (no parameterization) with some extra work on the “BC” term. \n - I also have concerns about the experiments. The experiments seem to be too simple. For example, in single-agent RL, they only consider very limited atari and mujoco games. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster