Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality
Authors: Stefanos Leonardos
Georgios Piliouras
Kelly Spendlove
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Exploration-Exploitation
Q-learning
Zero-Sum Polymatrix Games
Quantal Response Equilibria
Bounded Rationality

Abstract: The interplay between exploration and exploitation in competitive multi-agent learning is still far from being well understood. Motivated by this, we study smooth Q-learning, a prototypical learning model that explicitly captures the balance between game rewards and exploration costs. We show that Q-learning always converges to the unique quantal-response equilibrium (QRE), the standard solution concept for games under bounded rationality, in weighted zero-sum polymatrix games with heterogeneous learning agents using positive exploration rates. Complementing recent results about convergence in weighted potential games [16,34], we show that fast convergence of Q-learning in competitive settings obtains regardless of the number of agents and without any need for parameter fine-tuning. As showcased by our experiments in network zero-sum games, these theoretical results provide the necessary guarantees for an algorithmic approach to the currently open problem of equilibrium selection in competitive multi-agent settings.

Exploration-Exploitttio in Multi-Agent Competition:
Convergence with Bounded Rationality
Stefanos Leonardos, Georgios Piliouras
Kelly Spendlove University of Oxford
Singapore University of Technology and Design : oor
spendlovedmat ox. acc
Abstract
The interplay between exploration and exploitation in competitive multi-agent learning is still far from being well understood. Motivated by this, we study smooth Q-learning, a prototypical learning model that explicitly captures the balance between game rewards and exploration costs. We show that Q-learning always converges to the unique quantal-response equilibrium (QRE), the standard solution concept for games under bounded rationality, in weighted zero-sum polymatrix games with heterogeneous learning agents using positive exploration rates. Com- plementing recent results about convergence in weighted potential games [16 34), we show that fast convergence Q-lcarning in competitive settings obtains regard- less of the number of agents and without any need for parameter fine- tine-tunigg As showcased by our experiments network zero-sum games, these theoretical results provide the necessary guarantees for algorithmic approach to the currently open problem of equilibrium selection in competitive multi-agent settings.
Introduction
Zero-sum games and variants thereof are arguably amongst the most well studied settings in game theory. Indeed much attention has focused on the class of strictly competitive games [4), i.e., two player games such that when both players change their mixed strategies, then either there is change in the expected payoffs, or one of the two expected payoffs increases and the other decreases I According Aumann [4) "Strictly competitive games constitule one of the few areas in game theory, and indeed in the social sciences, where a fairly sharp, unique prediction is made." " The unique prediction, of course, refers the min-max solution and the resulting values guaranteed to both agents due to the classic work of von Neumann 53
Unfortunately, when move away from the safe haven of two-agent strictly competitive games, a lot these regularities disappear. For example, in multi-agent variants zero-sum and strictly competitive games, several critical aspects of the min-max theorem collapse [2]. Critically, Nash Equilibrium (NE) payoffs need not be unique. In fact, there can be continua of equilibria with the payoff range of different agents corresponding positive measure sets. Furthermore, NE strategies need not be exchangeable (i.c., mixing-maan matching strategies from different Nash profiles does not lead to Nash) nor max-min. Thus, network competition is not only significantly harder, but poses qualitatively different questions than two-agent competition.
Nevertheless, and despite the intense recent interest inspired by Artificial Intelligence (AI) and Machine Learning (ML) applications such as generative adversarial networks and actor-critic systems to understand learning dynamics in zero-sum games and even network variants thereof 19 22 27). so far, there has been no systematic study of how agents should deal with uncertainty the resulting
In fact, as recent work has established these strictly competitive games are formally equivalent to weighted zero-sum games, i.e., affine transformations of zero-sum sum games [
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

payoffs in such games. In these settings, the use of purely optimization regret-minimizing algorithms no longer equally attractive as in the two-player case. The multiplicity of equilibria and the lack of unique value give rise to non-trivial problem of equilibrium selection and learning agents face the fundamental dilemma between exploration and exploitation considerations drive our motivating question:
59 These
Are there exploration-exploiiae dynamics that provably converge in networks of strictly competitive games? How do they behave in settings with multiple, payoff diverse Nash equilibria?
Model and Results. We study a well-known smooth variant of Q-learning [55] 154, with softmax
or Boltzmann exploration, one of the most fundamental models of exploration-epploittiio in multi- agent systems (MAS), termed Boltzmann or smooth Q-learning [51 4 Informally (see Section for the rigorous definition), each agent l updates their choice distribution x = (I²) according to the rule /2, = (r: f) [1 x; - Σj Tyy In xyy), where rs, F denote agent k's rewards from action i and average rewards, respectively, given all other agents' actions and 1 is agent k's exploration rate.
In our main result, we show convergence of Q-learning to Quantal Response Equilibria (QRE), the prototypical extension of Nash equilibria for games with bounded rationality [36. in multi- agent/network generalizations of strictly competitive games [13 12]. As long as all exploration rates positive, we prove via global Lyapunov argument that the Q-learning dynamic converges pointwise to a unique QRE regardless of initial conditions and regardless of the number of the Nash equilibria of the original network game (Theorem 4.1). Related to the above, demonstrate how exploration by all agents leads to equilibrium selection. Thus, this long-standing open problem (32) 45 4 becomes tractable in practice due to the theoretical guarantees of fast convergence to QRE that we provide in Theorem 4. for this class of competitive games. In fact. [heorem 4.1 is in some sense tight, as there exist network competitive settings whose dynamics lead limit cycles if not all of the agents are performing exploration (see experiments and discussion in Section 5
Other Related Works. The variant of Q-learning that we study has recently received lot of attention due to its connection to evolutionary game theory [47 31 (5]. It has been also extensively studied in the economics and reinforcement learning literature under various names, see e.g.. 46
and [28] 39]. Recent works demonstrate that it is possible to show convergence of the Q-learning dynamics in multi-agent cooperative settings and to select highly desirable equilibria via complex bifurcation phenomena (34]
On the other hand, competitive multi-agent systems constitute of the current frontiers in Al and ML research. Many recent works investigate the complex behavior of competitive game theoretic settings
44
371, focusing carefully designed convergent algorithms, e.g., optimism 19
20 [56. extra-gradient methods [40] 3 26),, regularization 43), momentum adapted dynamics 23
or symplectic integration schemes 6 However, despite the theoretical progress and the impressive
results in the empirical front 49
52
33.. the literature on equilibrium selection seems to have
received little attention so far. Prior works have focused on equilibrium selection in cooperative Al or have theoretically studied competition in 2-agent zero-sum games in which equilibrium selection is irrelevant [8). To our knowledge, we are the first paper to explicitly study both theoretically and experimentally multi-agent competitive settings without uniquely defined values.
2 Game-Theoretic Model
A polymatrix or separable network game, I' ((V, wx) wx)Kev (AS)))..EE) consists of a graph (V, E), where V (1,2....,n) n) is the set of players (or agents), and E is a set of pairs, [R:, 1], of players h & I E V. Each player, k E V, has finite set of actions (or strategies) Sş with generic elements 8 E S₂ (depending on the context, sometimes we will also write i or E Sv). Players may also use mixed strategies (or choice distributions) X (II.)iES E Ar. where As is the simplex Ag. The interior of A is the set of all points X E As with JRi E (0, 1) for all E St. All points of A that are not in the interior, are called boundary points. We will write x = (x1, X2,xx,..... Xn.) or x = (x,,x_s) for a mixed strategy profile x E A := Ikev Ag, where X E A_ = IILSEv A is the vector of mixed strategies of all players 1 V other than k.
in RSA i.e., Eies, Tki = 1, and Tki 2 0, for any

---

Each edge [ E E defines a two-player game with payoff matrices An E RiSs|xISi and AiR E | The elements (5, st) of a matrix Au denote the payoff's of player k when players and use pure actions 8y E Sk and 81 Si, respectively. Each player k E V chooses strategy (mixed or pure) and plays that strategy in all games [k: 1] E E. Thus, the payoff of player & at the pure strategy profile s ($1...., 8n) E S = LLEV Sk is (x(s) = Lj.lee Ond 81). Similarly,
the expected reward player in the mixed strategy profile x E A
ux(xx) == EII.EE x/ A = =x
(IIAIEE AUXI)
(1)
It will be convenient to write (x:(x=)) = ug (i, x-xx LA (where {u}, to denotes the i-th element of vector v), for the reward of pure action i E Se of player I when all other players use the strategy profile x and ri (x-x)
x) == (rt:(x-*))sEss for the resulting reward vector of all pure actions of agent k; respectively. Using this notation, the expected reward of player k E V at the mixed strategy profile x (xx;X_N) x-x) can be compactly expressed as uy (x) = x Tu (x=x).
Weighted Zero-Sum Polymatrix Games. I is called a weighted or rescaled zero-sum polymatrix game [12 if there exist positive constants W1, 022 Wn > 0, so that
for all A. Enev (x)+(()
(2)
By summing the edges in E (instead of the players in V), we can equivalently express the weighted zero-sum property as
EnTEE [wxX] A + wix! Auxi] = 0, for all AllxEs
(3)
Nash Equilibrium. A strategy profile (tuple of mixed strategies), p (DE)REV E A, with P& (Pk))es, E AS for each & E V is a Nash equilibrium (NE) of I if
(p) 2 ( P-k), for all my E Ak. for all & E V,
(NE)
i.e., if there exist no profitable unilateral deviations. By linearity, it suffices to verify the condition in equation (NE) only for pure actions E S₁ instead of all z E Ag.
3 Joint Learning Model: Q-Learning Dynamics
We next discuss how we can get to the Q-learning dynamics from Q-learning agents when there multiple learners in the system. Our goal is to identify the dynamics in competitive systems in which multiple agents are playing a rescaled zero-sum polymatrix game repeatedly over time.
is value-iteration method for solving the optimal strategies in Markov Decision Processes (MDPs). It can be used as a model where users learn about their optimal strategy when facing uncertaintics. Specifically, at every time-point n 2 0, each Q-learning agent, k E V. keeps track of the past performance of each of their actions, E S2, via Q-value, denoted by (n). Que (z) is also called the memory of agent & about the performance of action E S₁ up to time step n 2 0. After selecting action i time n, the corresponding Q-value is updated according to the Q-learning update rule
Q-learning- Q-learning 55 54
Que(n + 1) = Qu)(n) + or [F Qua i Sk
(4)
where ds E [0, I] denotes the learning rate or memory decay of agent & [48 31. Agent updates their actions (choice distributions) according to Boltzmann-type distribution, with
V
cxp (Qki(n)TTA
Z&. Ejes, exp (Qky (n)/T)))
for each E St.
where T& E [0, +oo) denotes agent k's learning sensitivity or adaptation, i.e., how much the choice
distribution is affected by the past performance. We will refer to Tr the exploration rate or
temperature of player & [34] [5]] (see also next paragraph for a discussion). Combining equations (4) and (5), one obtains the recursive equation of player k's mixed strategy (or choice distribution)
(Ri(n) exp ([Qui(n + 1) Qui (n))
(n 1) Ejes, (n)(n) exp ((Q + 1) Qk, (n))/Tb)
3

---

for each E Sk. In practice, agents perform large numbers of action updates (updates of Q-values) for each distribittii update. This motivates to consider a continuous time version of the learning process of each agent which results in the following update rules for both the memories Qki and the selection probabilities Tki of each action E Sk
Q = ag (x a) Qual, and Pus Iik (QRi -ESes 2ns) /Tu.
where we omitted the dependence the continuous time, t O. Combining these two expressions with equation (5) under the assumptions that pairs of actions have constant relationship over time and that agents' choice distributions are independently distributed, we obtain the Q-Learning Dynamics
Tks = Iki (x_x(x x) - x Ta x) - Th (In (#xs) x In (xx))]
(QLD)
for all players & E V and all actions E Sk-
Fixed Points QLD. Using the convention In a 0 (recall that lim In = 0), we can see from equation (QLD) that (t) = (0) for all t > 0, for all i E Sş such that (0) E {0, 1}. In other words, the boundary of Ag is invariant for (QLD), i.e. if the dynamics start on the boundary, then they will remain there. This implies that all boundary points of the simplex,
Ag. are trivially fixed points of (QLD).
The interesting part concerns the fixed-points of the dynamics for interior starting points. In this case, equation (QL). implies that, whenever T3 > any resulting fixed point of (QLD) can only lie again in the interior of As due to the entropy term (In of the choice probabilities). Clearly, the rate of change of T&e must be equal to zero. Formally, this implies that a strategy profile p = (pk)kev with p: (Pa))es, for each & E V is an interior fixed point of (QLD) if
The (p- x) = P (p=x)++ Th (Ins) - P In (p+)), for all E.V.
(6)
Exploration Rates. Equation (QLD) suggests that higher values of TV 's indicate higher exploration rates, whereas values close to 0 indicate a higher exploitation rates. Specifically, for Tj = 0, the dynamics in (QLD) reduce to the well-known replicator dynamics, and agent simply selects the action i E S2 with the highest Q-value. On the other hand, as Th - oc, player k essentially ignores the input (rewards) from the environment and maximizes the entropy of their current choice distribu- tion (which leads to uniform randomization over their available actions in St). From a behavioral perspective, this leads to an equivalent interpretation the T 's as the degree of bounded rationality of the agent (25 24 21). Finally, from an algorithmic perspective, Ti and the corresponding entropy term can be viewed as regularizers that prevent the learning dynamics from overfitting. i.e., reaching
the boundary getting trapped in local optima [10 16 38 and 29 30).
Exponential Discounting. In continuous time, the Q-learning updates of equation 4 can be intuitively interpreted as exponential discounting of payoffs, with payoffs further back in the past being less important. In other words, an agent's 's Q-value for an action shows how beneficial is the action for that agent when payoffs are discounted.
Proposition 3.1 (Q-Value Updates and Exponential Discounting). For an agent l V, consider the Q-learning updates in equation 4 and assume that Q,(0) = for all i E Sy. Then, in continuous time, the Q-value updates are given by
(1) -00 L -ase -arrr:(tt s)ds = ac aast S (s) ds, for any any t >> 0.
r:(())
This interpretation also showcases the connection between QLD) and another commonly studied dynamic in behavioral game theory, Experienced Weighted Attraction (EWA) 21] Along with the proof Propositionn 3.1 this is explained in more detail in Appendix A.
3.1 Solution Concept: Quantal Response Equilibria
When considering agents with bounded rationality, the standard solution concept the quantal response equilibrium [36). In its most common definition, strategy profile p (pk)kev with

---

P: (Pk))Ees, for each k E V is an Quantal Response Equilibrium (QRE) of T, if it satisfies the following logit or softmax expression.
(xp( Pki Σ 1ES, exp (P-)(P=)/TT))
for all & E V,i Sk-
(QRE)
The following property suggests that the interior fixed points of QLLD coincide with the QRE of Т. Following directly from equations convergence analysis of (QLD).
(6 and (QRE), this statement will be the starting point of our
Proposition 3.2 (Interior Fixed Points of (QLD) and QRE). Let I' be an arbitrary game, with positive exploration rates, T& for all k E V. Then, for any interior starting point x(0) E A, the fixed points of the associated (QLD) always exist and coincide with the QRE of T. Moreover, given any such fixed point p. we have, for all Xk A and for all k V, that
[x P&) [rx(p=)) - Tk In (p+)]= =.
Proposition 3.2 does not make use of the weighted network zero-sum property, ef. (2) and thus, it holds for arbitrary network games. We also remark that the QREs are not refinement the NEs of I and, in fact, the two may be significantly different from each other. However, as we argued above, when Th = for all & E V. (QLD) reduce to standard replicator dynamies and this case, QRE coincide with the NE of T, cf. equations (NE and QRE.
Technical Remark. The condition in equation in Proposition 3.2 is critical for the main step in our proof of convergence of (QLD) in weighted zero-sum polymatrix games. Thus, it is important to note that (7) only holds when all exploration rates, Tg, A V are positive and not merely non oognegaaive. The intuition is that when all Te > O, every QRE becomes interior, i.c., has full support. This implics pure mixed actions give the same expected reward to the deviating agent. If some T& are equal to O, then 7 holds with (non-strict) inequality which is not generally enough for the proof of Theorem 4.1 This case exhibits more interesting behavior and will be discussed in detail in the experimental section. In brief, if this is the case, then the dynamics may also converge to boundary point even if the dynamics start in the interior.
that all deviations
4 Convergence of Q-learning in Weighted Zero-sum Polymatrix Games
Our main result is that Q-learning QLL)) converges to the QRE of any weighted zero-sum polymatrix game, I' Importantly, when the exploration rates of all agents are positive, this QRE is unique. The key step in the proof of both claims is to show that the distance between an interior QRE, p E A, and the sequence of play, x(f), 2 0 E A, that is generated by (QLD) is monotonically decreasing. To measure this distance in a meaningful way, we will use the notion of KL-divergence which is formally defined next.
Definition 1 (Kullback-Leible (KL) Divergence). The Kullback- or KL-Divergence (also called relative entropy), DKL, between two strategy profiles p = (Pn)REV. x(l) (xu(1))REV E A with p = (Pts)ess, and (t) (1)= = (Ine()))ESs, As for all & E V, defined as
DKL (p x(t)) Σ KEV DKL(PE || xx(t)) Σ REV Ps In
(t)
where P In Pk = Eies, Pas (pts/Iaattt) If = (wx)aEv is a k-dimensional vector of xx(t)
positive scalars, then the weighted or rescaled KL-divergence, DKL(W)) defined as
DKL(w) (pl) x(t))())= Enev (KL xx (f)).).
(9)
The KL-divergence between p and x(I can thought of a measurement of how far the distribution is from the distribution x(1). However, the KL-divergence is not symmetric, i.e., in general it holds that (p x()) * DxI(((1) ()) || p). Using the notion of KI.-divergence we can now formulate main result.
5

---

Theorem 4.1 (Convergence of (QLD) to QRE
Let I be rescaled zero-sum polymatrix game, with positive exploration rates Tt. There exists a unique QRE p such that if x(t) trajectory of the associated Q-learning dynamics, & = f((x,, where Si is given via (QLD). and x(0) an interior point, then x(1) converges to P exponentially fast. particular, we have that
any
d D kL(()) (P x(1)) = - WKTh (Pxc || xx. + DxL(xx Pk)]-
(10)
dl.
Sketch of Proof. (px= be QRE of (existence of p guaranteed via Proposition 3.2), and let x(t) be trajectory of the Q-learning dynamics (QLD) with x(0) an interior point. We will first establish (TO), from which the other statements follow. The first step is derive an explicit formula for the time derivative of the KL divergence between Pa: and X (t) for given player k.
Lemma 4.2. For any QRE equilibrium p and any player k V we have that
dt (RI(P (t)) (x* -P&) [rk (x=x) [x]p=)]] Tk (Pk || xx) + DKL(xx pk)]
It follows from Lemma 4.2 that
d dt
d
(p x()) Ene kev dt
Wh (PI Xx)
Σ wh [(X - -Px)] [Tx (x=+) - (x((p=)]] - -T (DKL ) xx) + (xL |l Pk))]] (11)
KEV
wx((x - -PA) (Pa (x-x) - (p-x)) - Σ
Th (PKL
|| xx)) + DKL Px)]
REV
KEV
Notice that (10) follows from the last line of (1I) if the first term vanishes. This can be shown by utilizing the following result regarding weighted zero-sum polymatrix games.
Lemma 4.3. Given any QRE, p (P&)keV, and any point x (xx)kev A we have that
Σkey we [x] rk (p-x) + PI rx (x= = 0.
Returning to [I]. we have that the first term in the right-hand side of the last equation vanishes since
Σnev kEV we (x+ pa) Ir (x= (x(P Enev wxXx rh (x x))
Wi Pr (p-+)
kVV
Σ kev wk X Th (p-x) + P Th (xxx) 0,
where the last equality follows from both the zero-sum property (2) and Lemma 4.3 Thus,
dt (p x(t)) = - - kEv TA [KIL (Px xx) + Dxi, Px)].
This equality implies that DRL(w) is a Lyapunov function for the Q-learning dynamics. Moreover, it implies that is unique, and that x(t) is converging to at an exponential rate.
provides tractable, algorithmic approach to the problem of equilibrium selection in weighted zero-sum polymatrix games. Given any such a game I, an interior initial condition and positive exploration rates Tk. Theorem 4.1 guarantees that the Q-learning agents will converge unique QRE can be very different from any Nash equilibrium but it will be arbitrarily close to some Nash equilibrium of I' as exploration rates approach zero (yet remain positive for all agents). Thus, exploration by all agents creates an arbitrarily good and efficient approximate equilibrium selection mechanism for the original game.
Approximate Equilibrium Selection Mechanism. Theorem 4.1
unique QRE of I' at exponentially fast rate. This
the exploration rates are high,
As discussed above (see Technical Remark in Section 3.1), the condition that the exploration rates of all agents are positive is necessary to establish convergence of QLD to unique QRE of a weighted zero-sum polymatrix game. As demonstrated next our experimental section, there can multiple QREs if one some agents have zero exploration rates.

---

CLR vs CLR.I
ETE va CLR-1
0.8
P(R)
012
85
T2
Pxpkeuticn wane 7,.%
Paplocaioo raleo T..,.
Figure I: QRE surface and exploration paths (upper tiles) for two different exploration policy profiles (lower tiles) in the Asymmetric MPs game. For any combination of exploration policies (CLR-1 and ETE), the sequence of play converges the unique QRE and as the exploration rates decrease to zero, the sequence of play converges to the unique Nash equilibrium of the game.
5 Experiments: Equilibrium Selection in Competitive Games
Two-Agent Weighted Zero-Sum Games. Starting with the performance of (QLD) in this low- dimensional case, we can visualize the QRE surface and exploration paths and gain intuition that carries over to the higher dimensional cases with more agents that we treat later.
Experimental setup: We consider the 2-agent Asymmetric Matching Pennies (AMPs) game, variation of the matching pennies [88, in which each agent has two actions, (). and payoffs
(
2 B 2
(-1 4 -
A
(AMPs)
The AMPs game is weighted zero-sum game since A + 0.5 B (each agent is the agent in their matrix), with a unique interior Nash equilibrium, (p, q) = =(1/3, 2/3), (2/3, 1/3)).
we visualize the QRE surfaces (light blue manifolds) for different exploration rates Tz, Ty of the two agents (æ: y plane). The vertical axis shows the probability with which agent 1 chooses H the unique QRE of the game. We plot the exploration path along two representative exploration-exploitaiion policies: Expplre--Then--iplore (ETE) (5), which starts with (relatively) high exploration that gradually reduces zero and Cyclical Learning Rate with I cycle (CLR-1) [50), which starts with low exploration, increases to high exploration around the half-life of the cycle and then decays O. For each pair of exploration rates, the learning dynamics converge to the corresponding unique QRE. As the exploration rates decay to zero, the dynamics converge to (i.c., select) the unique QRE (i.e., the Nash equilibrium in this case) of the original game.
Results: In Figuue I,
Ri E31 JandE
Fy
T
H
86
8
8
8
Figure 2: Q-learning dynamics the AMPs game for Tú (no exploration by r-agent) and four different exploration rates, Ty 2 0 by y-agent.

---

By contrast, the first tile of Figure shows that the dynamics cycle around the unique Nash equilibrium when both agents do not use exploration. The rest of the tiles of Figure show that in this case, exploration by only one agent suffices to lead the joint-learning dynamics to converge to a unique QRE. this case, for higher values of exploration by the exploring agent, the QRE component of the non-exploring agent may lie at the boundary (see tile 4 in Figure 2 and Appendix C).
Network Zero-Sum Games, As the next experiment shows, equilibrium selection works also in larger networks, provided that all agents maintain a positive exploration rate. In contrast to the previous example, in this case, exploration by only some agents not sufficient for convergence.
Experimental setup:
We consider the Match-Mismatch weighted zero-sum polymatrix game (MMG) with n + agents (n E N is arbitrary) which is shown in Figure 3 Each of the agents p1 to
A
Aa
d1
P1
Po
d2
(H)
(H,T)
A_
A
(H,T)
(T)
Figure 3: The match-mismatch weighted zero-sum polymatrix game (MMG).
Pn has two actions, {H, T), and receives +1 if they match the action of the next agent (otherwise they receive 1) and +1 if they mismatch the strategy of the previous agent (otherwise they receive -1). There are two dummy agents, d1, d2, who have the same payoffs but only one action: H for dj and T for d2. The payoff matrices for the games between non-dummy agents are given by
A+ = -) A
(MMG)
whereas the payoff matrices of dummy agents dj and d2 are given by A A2 A2 (1, column agents in the payoff matrices A₁ and A2 p1 and Pa. and their payoffs in the encounters against dj and d2 are given by - A and -A respectively. This game has infinite many NE the following form: the odd-numbered agents play strategy T (which, for agent I ensures -1 against dı) whereas the even agents are indifferent between H, T (since they are certain to have opposing results in the two games against the previous and the next agent, both being odd and playing T).
The
Results: In Figure 4. we consider an instance of (MGG with n = non-dummy agents and show the projections (tiles I to 3) of the QRE surfaces the H coordinate at QRE for agents 1 to 3 for fixed T3 = 3 and all possible combinations of Ti, T2 (x-y planes). The QRE manifolds continuously approach the boundary (case with T: for 1, 2) which leads unique equilibrium selection also when 7, T2 = 0. Tile 4 shows a snapshot of the Lyapunov function (KL-divergence between choice distribution and unique QRE q) in non-dummy agents instance of (MMG) for fixed exploration profile with positive exploration rates for all agents, Tę > 0, for all A: T....,7 7. To obtain this plot, (which similar for all n > 1), we use the dimension reduction technique of (35 to visualize high-dimensional surfaces along two randomly chosen directions (cf. Appendix C). As expected, the KL-divergence is convex and decreasing for all x with a unique minimizer.
Figure 5 shows summary statistics for the n = (MGG) instance for three different exploration profiles. The tiles in the left column show the equilibria (top) and utilities (bottom) of the agents
PL
P2
P1
05
Figure 4: Projections of the QRE surfaces on the coordinate of players Pt, P2, Ps (tiles 1-3) and a snapshot of the Lyapunov function, KL-divergence, (tile 4) in two instances of the (MMG) game with 3 and non-dummy agents, respectively, as discussed in Section 5]
8

---

explocation
Explrittion by
Expicraioon by
08
0.6
02
0.2
0.2
2
2
3
06
00
+
86
0.0
02
0.5
0.2 0.5
2
2
2
Agests
Agunna
Agents
Figure 5: Summary statistics from 100 runs with 3 profiles of exploration rates in 7 non-dummy agent instance of (MMG). No exploration leads multiple, payoff-diverss equilibria (left), explo- ration by some agents is not enough to ensure convergence to a unique outcome which shows the tightness Theorem 4. (middle) and exploration by all agents leads unique QRE (right column).
in 100 runs when T = for all k = 1,2..... n (no exploration). this case, (LLD) converge in e
all runs to the pure action for the odd agents and some arbitrary (and possibly different between runs) mixed action for the even agents. This behavior of (QLD) conforms with previous results in adversarial learning concerning equilibria that lie on one face (relative boundary) of the high- dimensional simplex (cf. (.8). The tiles in the middle column correspond to a case with exploration by agents 2, 3 and no exploration by agents to 7. Exploration by the first group of agents ensures convergence of their individual dynamics to the corresponding component of the QRE but even-numbered agents that lie further away from that group fail converge or to obtain a unique payoff (boxplots for agents 3 to 7). The outcome in this case, shows that the statement of Theorem 4.1 is tight, and exploration by only subset of agents may not be enough to ensure a unique outcome in general settings. In particular, zero exploration by agents 4 to 7 leads to multiple equilibria for agents and 6 (upper middle tile) and to non-unique payoff's for agents 5 and 7 but also for agent 3 who has positive exploration rate (lower middle tile). Finally, the tiles in the right column show convergence a unique QRE when all agents have positive exploration rates.
unique outcome
6 Conclusions
In this paper, we studied a commonly used smooth variant of the Q-learning dynamics in multi-agent competitive games. Given that each agent's 's strategy includes at least some amount of exploration, we showed that the dynamics always converge to a unique Quantal Response Equilibrium (QRE) of the game at an exponentially fast rate. The convergence of Q-learning in this (competitive) setting remarkably robust phenomenon, occurring regardless of the number of agents or degree of competition, and without any need for parameter fine-tuning.
Our theoretical results have important implications from an algorithmic perspective. In contrast to two-agent zero-sum games in which agents have the same reward in all equilibria, multi-agent systems typically exhibit multiplicity of equilibria in which each agent may have different rewards. This inherent complexity within multi-agent systems leads to the non-trivial problem of equilibrium selection which has been previously studied only within cooperative settings. The exponentially fast convergence of the Q-learning dynamics to unique QRE that we prove in this paper establishes an efficient and simple mechanism select (approximate) Nash equilibria, implying that the problem of equilibrium selection is tractable within competitive multi- settings as well. In particular, while QRE may correspond to a significantly different outcome from all Nash equilibria of the original game when exploration rates are high, it offers an arbitrarily good approximation of some Nash equilibrium for close-to-zero exploration rates. Together with 34 our results establishe that exploration-exploitatio with Q-learning works well in both as equilibrium selection mechanism in both cooperative and competitive settings and provide a solid starting point for the study of general, mixed multi-agent settings that involve both cooperative and competitive interactions.

---

Acknowledgments and Disclosure of Funding
This research/project is supported in part by the National Research Foundation, Singapore un- der its AI Singapore Program (AISG Award No: AISGG-RP-2020--11,, NRF 2018 Fellowship NRF-NRFF2018--1
ALIAS grant, grant PIE-SGP-AI-201 8-01, AME Pro- grammatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A*STAR), and by EPSRC grant EP/2018472/1.
References
[1] Adler, C. Daskalakis, and C. H. Papadimitriou. note on strictly competitive games. In WINE, pages 471-474 Springer, 2009.
[2] C. Alós-Ferrer and N. Netzer. The logit-response dynamics. Games and Economic Behavior, 68(2):413-427, 2010.
[3] K. Antonakopoulos, E. V. Belmega, and P. Mertikopoulos. Adaptive extra-gradient methods for min-max optimization and games. arXiv preprint arXiv:2010./2100 02./0000.///0,., 2020.
[4] R. J. Aumann. Game Theory, pages 1-40. Palgrave Macmillan UK, London, 2017.
[5] Y. Bai and C. Jin. Provable Self-Play Algorithms for Competitive Reinforcement Learning. In Proceedings of the 37th International Conference Machine Learning, 20, Madison, WI, USA, 2020. Omnipress.
[6] J. Bailey, G. Gauthier, and G. Piliouras. Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent, ArXiv e-prints, 2019.
[7] J. Bailey and G. Piliouras. Multiplicative Weights Update in Zero-Sum Games, In Proceedings of the 2018 ACM Conference on Economics and Computation, EC '18, page 321-338, New York, NY, USA, 2018. Association for Computing Machinery.
[8] J. Bailey and G. Piliouras. Agent-Agent Learning in Network Zero-Sum Games is a Hamilto- nian System. In 18th International Conference Autonomous Agents and Multiagent Systems (AAMAS), 2019.
[9] D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel. The mechanics of n-player differentiabbee games. ICML, 2018.
[10] M. Bowling and M. Veloso. Multiagent learning using variable learning rate. Artificial Intelligence, 136(2):215-255)) 2002.
[11] L. Busoniu, R. Babuska, and B. De Schutter. A Comprehensive Survey of Multiagent Reinforce- ment Learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-77,,, 2008
[12] Y. Cai, O. Candogan, Daskalakis, and C. Papadimitriou. Zero-Sum Polymatrix Games: Generalization of Minmax. Mathematics of Operations Research, 41(2):648-655 2016.
[13] Y. Cai and C. Daskalakis. On minmax theorems for multiplayer games. In Proceedings of the Twenty-Second Annual ACM-SIAN Symposiun on Discrete Algorithms, SODA '11, page 217-234, USA, 2011. Society for Industrial and Applied Mathematics.
[14] C. F. Camerer. Behavioral game theory: Experiments in strategic interaction. Princeton university press, 2011.
[15) C. Claus and C. Boutilier. Systems. In Proceedings of the Fifteenth National/Tenth Conference on Artificial Intelli- gence/Innovative Applications of Artificial Intelligence, AAAI '98/IAAI '98, page 746-752, 1998.
The Dynamics Reinforcement Learning in Cooperative Multiagent
[16] Coucheney, B. Gaujal, and P. Mertikopoulos. Penalty- Dynamics and Robust Learning Procedures in Games, Mathematics of Operations Research, 40(3):611-633, 2015.
10

---

[17] A. Dafoe, E. Hughes, Y. Bachrach, Т. Collins, K. R. McKee, J. Z. Leibo, K. Larson, and Graepel. Open Problems in Cooperative AI. arXiv e-prints, December 2020.
[18] C. Daskalakis, DJJ. Foster, and N. Golowich. Independent Policy Gradient Methods for Competitive Reinforcement Learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5527-5540. Curran Associates, Inc., 2020.
[19] C. Daskalakis, A. Hyas, V. Syrgkanis, and H. Zeng. Training GANs with Optimism. In ICLR, 2018.
[20] C. Daskalakis and I. Panageas. Ltst-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. In A. Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124, pages 27:1-27:15 2018.
[21] T. Galla and J. D. Farmer. Complex dynamics in learning complicated games. Proceedings of the National Academy of Sciences, 110(4):1232 121122222262,----111112111 2013.
[22] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. variational inequality perspective generative adversarial networks. In ICLR, 2019.
[23] G. Gidel, R. Hemmat, M. Pezeshki, Huang, R. Lepriol. S. Lacoste-Julien and I. Mitliagkas. Negative momentum for improved game dynamics. In AISTATS, 2019.
[24] T.-H. Ho and C. Camerer. weiigte attraction learning in coordination games: Probability rules, hetcrogeneity, and time-variation. Journal of mathematical psychology. 42:305-326, 1998.
[25] T.-H. Ho and C. Camerer. Experience-weighted attraction learning in normal form games. Econometrica, 67:827-874, 1999.
[26] Y.-G. Hsieh, F. lutzeler, J. Malick, and P. Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. arXiv preprint arXiv: 08460, 2019.
[27] A. Jacob, A. L. Kevin, and A. Wibisono. Last-iterate convergence rates for min-max optimiza- tion: Convergence of hamiltonian gradient descent and consensus optimization. In V. Feldman, K. Ligett, and S. Sabato, editors, Proceedings of the 32nd International Conference on Algorith- mic Learning Theory, volume 132 Proceedings of Machine Learning Research, pages 3-47.
PMLR, 16-19 Mar 2021.
[28] L. P. Kaelbling, M. L. Littman, and A. W. Moore. Reinforcement learning: A survey, Journal of Artificial Intelligence Research, 4(1):237-285, 1996.
[29] M. Kaisers and K. Tuyls. Frequency adjusted multi-agent g-learning. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1 Volume 1, AAMAS 10, page 309-316, 2010.
[30] M. Kaisers and K. Tuyls. FAQ-Learning in Matrix Games: Demonstrating Convergence near Nash Equilibria, and Bifurcation of Attractors in the Battle of Sexes. In Proceedings of the 13th AAAI Conference on Interactive Decision Theory and Game Theory, AAAIWS' 11-13, page 36-42. AAAI Press, 2011. [31] A. Kianercy and Galstyan. Dynamics Boltzmann Q learning in two-player two-action games. Phys. Rev. E, 85:041145, Apr 2012.
[32] Y. Kim. Equilibrium Selection in n-Person Coordination Games. Games and Economic Behavior, 15(2):203-22 1996.
[33] M. Lanctot, E. Lockhart, J.-B. Lespiau, V. Zambaldi, S. Upadhyay, J. Pérolat, S. Srinivasan, Timbers, K. Tuyls, Omidshafiei, D. Hennes, D. Morrill, P. Muller, T. Ewalds, R. Faulkner, J. Kramár, B. De Vylder, B. Saeta, J. Bradbury, D. Ding, S. Borgeaud, M. Lai, J. Schrit- twieser, T. Anthony, F. Hughes, I. Danihelka, and J. Ryan-Davis. Openspiel: A framework for reinforcement learning in games, 2020.

---

[34] S. Leonardds and G. Piliouras. Exploration- Exploitation in Multi-Agent Learning: Catastro- phe Theory Meets Game Theory. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, AAAI-21, 2021.
[35] H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein. Visualizing the Loss Landscape of Neural Nets. In S. Bengio. H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Desa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 6389-6399. Curran Associates, Inc., 2018.
[36] R. D. McKelvey and T. R. Palfrey. Quantal Response Equilibria for Normal Form Games. Games and Economic Behavior, 10(1):6 -3,6,,,877 1995.
[37] P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Op- timistic mirror descent in saddle-point problems: Going the extra(-gradient) mile. In ICLR, 2019.
[38] P. Mertikopoulos, C. Papadimitrion, and G. Piliouras. Cycles in Adversarial Regularized Learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, page 2703-2717, USA, 2018. Society for Industrial and Applied Mathematics.
[39] P. Mertikopoulos and W. H. Sandholm. Learning in Games via Reinforcement and Regulariza- tion. Mathematics of Operations Research, 41(4 1297-1142,, 2016.
[40] Mertikopoulos, H. Zenati, B. Lecouat, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Mirror descent in saddle-poing problems: Going the extra (gradient) mile. ArXiv e-prints, July 2018.
[41] L. Panait and S. Luke. Cooperative Multi-Agent Learning: The State of the Art. Autonomous Agents and Aulti-Agent Systems, 11(3):387-43 Nov 2005.
[42] M. Pangallo, J. Sanders, T. Galla, and D. Farmer. A taxonomy of learning dynamics in x games. arXiv e-prints, page arXiv: 770109903,, January 2017.
[43] J. Perolat, R. Munos, J.-B. Lespiau, S. Omidshafiei, M. Rowland, P. Ortega, N. Burch, T. An- thony, D. Balduzzi, B. De Vylder, G. Piliouras, M. Lanetot, and K. Tuyls. From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regulariza- tion, 2020.
[44] S. Rakhlin and Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, pages 3066-3074, 2013.
[45] J. Romero. The effect of hysteresis on equilibrium selection in coordination games. Journal of Economic Behavior & Organization. 111:88-105, 2015.
[46] J. B. T. Sanders, J. D. Farmer, and T. Galla. The prevalence of chaotic dynamics in games with many players. Scientific Reports, 8(1):4902, 2018.
[47] Y. Sato, E. Akiyama, and J. P. Crutchfield. Stability and diversity in collective adaptation. Physica D:Nonlinear Phenomena, 210(1):21-57, 2005.
[48] Y. Sato and J. P. Crutchfield. Coupled replicator equations for the dynamics of learning in multiagent systems. Phys. Rev. E, 67:015206, Jan 2003.
[49] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser,
I. Antonogiou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalch- brenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukeuoglu, T. Graepel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):84-- 489, Jan 2016
[50] L. N. Smith and N. Topin. Super- Copee-Converg:nc::: Very Fast Training of Neural Networks Using Large Learning Rates. arXiv e-prints, page arXiv:1708.071200 2017.
[51] K. Tuyls, K. Verbeeck, and T. Lenaerts. A Selection-muration Model for Q-learning in Multi- agent Systems. Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS '03, pages 693-700, 2003.
12

---

[52] O. Vinyals. I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, J. Oh, D. Horgan, M. Kroiss, Danihelka, A. Huang, L. Sifre, T. Cai, J. P. Agapiou, M. Jaderberg, A. S. Vezhnevets, R. Leblond, T. Pohlen, V. Dalibard, D. Budden, Sulsky, J. Molloy, T. Paine, C. Gulcehre, Z. Wang. T. Pfaff, Wu, R. Ring,
D. Yogatama, D. Wünsch, K. McKinney, O. Smith, T. Schaul, T. Lillicrap, K. Kavukcuoglu,
D. Hassabis, C. Apps, and D. Silver. Grandmaster level in StarCraft II using multi-agent reinforcement learning, Nature, 575(7782)3500335, Nov 2019.
[53] J. von Neumann. Zur theorie der gesellschaftsspicle. Mathemattische Annalen, 100:295-300, 1928.
[54] C.J.C.H. Watkins. Learning from delayed rewards. PhD thesis, King's College, Cambridge United Kingdom, 1989.
[55] C.J.C.H. Watkins and Dayan. Technical Note: Q-Learning. Machine Learning. 8(3)279--922 May 1992.
[56] C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo. Linear Last-iterate Convergence in Constrained Saddle-point Optimization. In International Conference on Learning Representations, 2021.
[57] D. H. Wolpert, M. Harré, E. Olbrich, N. Bertschinger, and J. Jost. Hysteresis effects of changing the parameters of noncooperative games. Phys. Rev. E, 85:036102, Mar 2012.
[58] M. Wunder, M. Littman, and M. Babes. Classes of Multiagent Q-Learning Dynamies with c-Greedy Exploration. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, page 1167-1174, Madison, WI, USA, 2010. Omnipress.
[59] K. Zhang, Z. Yang, and T. Başar. Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms, arXiy e-prints, page 1911. 10635, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
This is theoretical work which does not present any foresceable societal conse-
quence.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
Yes, this work includes theoretical results. In the main part, provide proof sketches of all our results. In the supplementary material, we also provide the complete technical details.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
Our simulations concern theoretical abstractions of network games. The total amount of computation is not concern and all our experiments be reproduced any conventional machine.
4. If you are using existing assets (c.g., code, data, models) or curating/rellusing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l rou're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "Q7auanQbYXq", "reviewer": "Reviewer_kq4E", "summary": "This paper investigates the convergence of a smooth variant of Q-learning dynamics in multiplayer network games called weighted zero-sum polymatrix games. The authors suggest interpreting the exploration rate of Q-learning as the inverse of the lambda parameter of the quantal response model, determining the degree of the agent’s rationality. The main result of this work claims that in weighted zero-sum polymatrix games, the Q-learning dynamics will always converge to the unique quantal response equilibrium associated with strictly positive exploration rates exponentially fast, irrespective of the initial profile of strictly mixed strategies (i.e., no agent adopts a pure strategy). The manuscript is concluded by empirical analysis of convergence of Q-learning in two-player and multiplayer weighted zero-sum games. The results show that with strictly positive exploration rates, the dynamic will indeed converge to the associated quantal response equilibrium and approximate Nash equilibrium as exploration rates approach zero. In the case of the two-player setting, the authors observe the quantal response equilibrium is reached even when only one of the players explore (and the dynamic is cyclic when no one explores), which is turned into a formal proposition in appendix C for two-player games with two actions per each player. For multiplayer games, exploration by only a subset of players will not guarantee to reach equilibrium.", "questions": "", "limitations": "", "rating": 8, "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": "The results the authors present in this work are indeed interesting; the inverse of the lambda parameter was interpreted previously as the intensity of noise, and it is compelling to see the interpretation based on exploration. In the limited time allocated for reviewing, I went through the proofs presented in the appendix (and partially also in the main text), and as far as I can tell, they seem correct to me. I am convinced the quality of results meets the standards of NeurIPS, and analyzing the convergence of different variants of Q-learning is definitely worth investigating. The manuscript is well written in terms of prose, the relevant concepts are well described, and the notation is clear. I suggest the authors allocate some space in the introduction to motivate the class of games they study with some real-world examples. I also have a few notes and questions relating mainly to the experimental part of the paper.\n\nWhat I am missing in the experimental part is some comparison to traditional methods for computing quantal response equilibrium in terms of practical scalability in the number of players and their actions. Even seeing how the convergence is affected by the number of players and sizes of their action spaces for the smooth Q-learning with fixed exploration rates alone would be interesting. Moreover, limiting the exploration rates to zero, as described in the manuscript, closely resembles the tracing procedure introduced by McKelvey and Palfrey in their 1995 paper, for which Turocy presents a practical algorithm in his paper “A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence”. The algorithm is implemented in the Gambit library. I believe that comparing Turocy’s method to smooth Q-learning with ELE or CLR-1 strategy would also provide insight into how smooth Q-learning performs in solving the equilibrium selection problem in practice.\n\nMcKelvey and Palfrey call the selected Nash equilibrium when lambda approaches infinity (or equivalently, the exploration rates go to zero) the limiting logit equilibrium. Turocy claims that in 2x2 games, the limiting logit equilibrium is risk-dominant (and a similar result is also achieved by Anderson, Goeree, and Holt in minimum-effort coordination games), but Zhang and Hofbauer later disputed this. Do the authors have some intuition which equilibrium would be selected, e.g., in the ZSPG game with many players, besides what is described in part C.5 of the appendix?\n\nWhat do the authors consider to be the main takeaway from the experiments? Is it the fact that strictly positive rates are indeed necessary for multiplayer games to guarantee convergence? Is the convergence lost in the ZSPG game even when all but one player explore?\n\n### After rebuttal\n\nI would like to thank the authors for their detailed response to my questions, and for pointing me to the work of Leonardos and Piliouras. The assumption that the limiting equilibrium will exhibit a higher entropy than other Nash equilibria is intriguing yet natural and I hope there will be some results in this direction in the future. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I can not think of any limitation not addressed by the authors.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}, {"review_id": "DN71ydhBhux", "reviewer": "Reviewer_xRAX", "summary": "This paper studies the convergence of Boltzmann Q-learning to the unique quantal-response equilibrium (QRE),   in weighted zero-sum polymatrix games, assuming all agents using positive exploration rates. ", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n\nThis paper provides a solid contribution to the literature on selecting Nash equilibria in multi-agent systems, not only in cooperative settings but also in competitive settings. Considering the complexity of multi-agent systems and the minor assumptions needed in this paper,  the present paper serves as a good start to understanding the effectiveness of exploration in the convergence of Q-learning in multi-agent systems. The experiments on some zero-sum games show the convergence of the algorithm and the necessity of exploration.\n\nQuestions:\n- In the experiment ''Two-agent Weighted Zero-Sum Games'', what's the performance if both of the agents use ETE? I wonder whether both of the agents doing exploration at the beginning stage would affect the convergence. \n- Can the convergence be observed in larger games and would it be robust? Currently, the simulation is in a 7-agent game. What's the potential difficulty of simulating the proposed method in larger games?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No visible negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No visible ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "5MXX4UVYdox", "reviewer": "Reviewer_SnP7", "summary": "This paper studies the convergence of simple bandit learning algorithm in weighted zero-sum games, to the Quantal Response Equilibria. I have several major questions regarding the problem setup, motivation and conclusion.", "questions": "", "limitations": "", "rating": 6, "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": "This paper studies the convergence of a simple bandit learning algorithm in weighted zero-sum games, to Quantal Response Equilibria. I have several major questions regarding the problem setup and conclusions.\n\n1) Problem setup: The \"Q-learning\" algorithm defined in Eq (5) is actually a bandit learning algorithm, as it does not consider the transition dynamics (simple repeated game). However, the authors didn't clearly state this is a bandit setup, and mentioned MDP in line 111, which confused the readers a lot.\n\n2) Main result: For the main convergence result part (Section 4), in line 222, the author mentioned the bandit learning will converge to QRE, and will approximate a NE. The first claim is proved, but why this QRE can approximate a NE? QRE and NE are two different solution concepts in games, and one does not imply the other. The authors should theoretically explain the latter statement. \n\n3) Motivation of this work: the author mentioned equilibrium selection is mostly discussed in cooperative game setting, and this is the first work studies these concepts in multi-agent competitive setting. Equilibrium selection in cooperative games make sense, as all agents are collaborative and can coordinate to maximize certain central utility. But it seems equilibrium selection in competitive games doesn't make much sense? Agents are self-interested and the outcome of the game cannot be selected - it's determined by agent's self-interested actions.\n\n4) Experiment: Similar to my question (2), the authors mentioned the learning dynamics converge to Nash equilibrium in all simulated game. But the main convergence result is about the Quantal Response Equilibria  - not the Nash equilibrium. The author should either show results about the convergence to QRE, or clearly explain why convergence to QRE implies convergence to NE in these example games.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not apply", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows that for a class of multi-agent competitive games -- weighted zero-sum polymatrix games, a variant of Q-learning can provably converge to the unique quantal response equilibrium.
(+) The paper presents a set of new theoretical results regarding convergence guarantees of learning rules in multi-agent games, an area that is understudied so far despite the popularity of learning algorithms used for multi-agent settings. The theoretical analysis is solid.
(+) The numerical experiments show the learning dynamics in some example games, which confirms the theoretical results.
(-) There are some minor presentation issues, for example, the term “network competition” is used without explanation in the introduction, and the use of “.” instead of “,” in line 67.
(-) The reviewers also made a number of suggestions to further strengthen the paper, including adding additional motivations, connections between QRE and NE, additional experiments regarding the scalability.

Overall, the reviewer team has a positive view of the paper. We suggest the authors make changes they promised in the responses to improve the paper.
Decision: Accept (Spotlight)