Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality
Year: 2021

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.

heading: 1 Introduction
text: 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 no change in the expected payoffs, or one of the two expected payoffs increases and the other decreases.1 According to Aumann [4], “Strictly competitive games constitute 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 to the min-max solution and the resulting values guaranteed to both agents due to the classic work of von Neumann [53].
Unfortunately, when we move away from the safe haven of two-agent strictly competitive games, a lot of these regularities disappear. For example, in multi-agent variants of zero-sum and strictly competitive games, several critical aspects of the min-max theorem collapse [12]. 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 to positive measure sets. Furthermore, NE strategies need not be exchangeable (i.e., mixing-matching strategies from different Nash profiles does not lead to a 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 of the resulting
1In 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 games [1].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
payoffs in such games. In these settings, the use of purely optimization-driven, regret-minimizing algorithms is no longer equally attractive as in the two-player case. The multiplicity of equilibria and the lack of unique value give rise to a non-trivial problem of equilibrium selection and learning agents face the fundamental dilemma between exploration and exploitation [15, 41, 11, 59]. These considerations drive our motivating question:
Are there exploration-exploitation 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, 54], with softmax or Boltzmann exploration, one of the most fundamental models of exploration-exploitation in multiagent systems (MAS), termed Boltzmann or smooth Q-learning [51, 48]. Informally (see Section 3 for the rigorous definition), each agent k updates their choice distribution x = (xi) according to the rule ẋi/xi = (ri − r̄)− Tk(lnxi − ∑ j xj lnxj), where ri, r̄ denote agent k’s rewards from action i and average rewards, respectively, given all other agents’ actions and Tk 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 multiagent/network generalizations of strictly competitive games [13, 12]. As long as all exploration rates are positive, we prove via a 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, we demonstrate how exploration by all agents leads to equilibrium selection. Thus, this long-standing open problem ([32, 45, 43]) becomes tractable in practice due to the theoretical guarantees of fast convergence to QRE that we provide in Theorem 4.1 for this class of competitive games. In fact, Theorem 4.1 is in some sense tight, as there exist network competitive settings whose dynamics lead to 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 a lot of attention due to its connection to evolutionary game theory [47, 31, 57]. It has been also extensively studied in the economics and reinforcement learning literature under various names, see e.g., [2, 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 one of the current frontiers in AI and ML research. Many recent works investigate the complex behavior of competitive game theoretic settings [44, 9, 8, 7, 37], focusing on 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 AI or have theoretically studied competition in 2-agent zero-sum games in which equilibrium selection is irrelevant [17, 18]. To our knowledge, we are the first paper to explicitly study both theoretically and experimentally multi-agent competitive settings without uniquely defined values.

heading: 2 Game-Theoretic Model
text: A polymatrix or separable network game, Γ = ( (V,E), (Sk, wk)k∈V , (Akl)[k,l]∈E ) , consists of a graph (V,E), where V = {1, 2, . . . , n} is the set of players (or agents), and E is a set of pairs, [k, l], of players k ̸= l ∈ V . Each player, k ∈ V , has a finite set of actions (or strategies) Sk with generic elements sk ∈ Sk (depending on the context, sometimes we will also write i or j ∈ Sk). Players may also use mixed strategies (or choice distributions) xk = (xki)i∈Sk ∈ ∆k, where ∆k is the simplex in R|Sk|, i.e., ∑ i∈Sk xki = 1, and xki ≥ 0, for any xk ∈ ∆k. The interior of ∆k is the set of all points xk ∈ ∆k with xki ∈ (0, 1) for all i ∈ Sk. All points of ∆k that are not in the interior, are called boundary points. We will write x = (x1,x2, . . . ,xn) or x = (xk,x−k) for a mixed strategy profile x ∈ ∆ := ∏ k∈V ∆k, where x−k ∈ ∆−k = ∏ l ̸=k∈V ∆l is the vector of mixed strategies of all players l ∈ V other than k.
Each edge [k, l] ∈ E defines a two-player game with payoff matrices Akl ∈ R|Sk|×|Sl| and Alk ∈ R|Sl|×|Sk|. The elements akl(sk, sl) of a matrix Akl denote the payoffs of player k when players k and l use pure actions sk ∈ Sk and sl ∈ Sl, respectively. Each player k ∈ V chooses a strategy (mixed or pure) and plays that strategy in all games [k, l] ∈ E. Thus, the payoff of player k at the pure strategy profile s = (s1, . . . , sn) ∈ S := ∏ k∈V Sk is uk(s) = ∑ [k,l]∈E akl(sk, sl). Similarly, the expected reward of player k in the mixed strategy profile x ∈ ∆ is
uk(x) := ∑
[k,l]∈E x⊤k Aklxl = x ⊤ k (∑ [k,l]∈E Aklxl ) . (1)
It will be convenient to write rki(x−k) := uk (i,x−k) = ∑
[k,l]∈E{Aklxl}i (where {v}i to denotes the i-th element of a vector v), for the reward of pure action i ∈ Sk of player k when all other players use the strategy profile x−k and rk (x−k) := (rki(x−k))i∈Sk for the resulting reward vector of all pure actions of agent k, respectively. Using this notation, the expected reward of player k ∈ V at the mixed strategy profile x = (xk,x−k) can be compactly expressed as uk(x) = x⊤k rk (x−k).
Weighted Zero-Sum Polymatrix Games. Γ is called a weighted or rescaled zero-sum polymatrix game [12], if there exist positive constants w1, w2, . . . , wn > 0, so that∑
k∈V wkuk(x) = 0, for all x ∈ ∆. (2)
By summing over the edges in E (instead of the players in V ), we can equivalently express the weighted zero-sum property as∑
[k,l]∈E
[ wkx ⊤ k Aklxl + wlx ⊤ l Alkxk ] = 0, for all x ∈ ∆. (3)
Nash Equilibrium. A strategy profile (tuple of mixed strategies), p = (pk)k∈V ∈ ∆, with pk = (pki)i∈Sk ∈ ∆k for each k ∈ V is a Nash equilibrium (NE) of Γ if
uk(p) ≥ uk(xk,p−k), for all xk ∈ ∆k, for all k ∈ 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 sk ∈ Sk instead of all xk ∈ ∆k.

heading: 3 Joint Learning Model: Q-Learning Dynamics
text: We next discuss how we can get to the Q-learning dynamics from Q-learning agents when there are 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.
Q-learning. Q-learning [55, 54] is a 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 uncertainties. Specifically, at every time-point n ≥ 0, each Q-learning agent, k ∈ V , keeps track of the past performance of each of their actions, i ∈ Sk, via a Q-value, denoted by Qik(n). Qki(n) is also called the memory of agent k about the performance of action i ∈ Sk up to time step n ≥ 0. After selecting action i at time n, the corresponding Q-value is updated according to the Q-learning update rule
Qki(n+ 1) = Qki(n) + αk [rki(x−k, n)−Qki(n)] , i ∈ Sk, (4) where αk ∈ [0, 1] denotes the learning rate or memory decay of agent k [48, 31]. Agent k ∈ V updates their actions (choice distributions) according to a Boltzmann-type distribution, with
xki(n) = exp (Qki(n)/Tk)∑
j∈Sk exp (Qkj(n)/Tk) , for each i ∈ Sk, (5)
where Tk ∈ [0,+∞) 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 Tk as the exploration rate or temperature of player k [34, 51] (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)
xki(n+ 1) = xki(n) exp ((Qki(n+ 1)−Qki(n))/Tk)∑
j∈Sk xkj(n) exp ((Qkj(n+ 1)−Qkj(n))/Tk) ,
for each i ∈ Sk. In practice, agents perform large numbers of action updates (updates of Q-values) for each choice-distribution 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 xki of each action i ∈ Sk
Q̇ki = αk [rki(x−k)−Qki] , and ẋki = xki ( Q̇ki − ∑ j∈Sk Q̇kj ) /Tk,
where we omitted the dependence on the continuous time, t ≥ 0. 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
ẋki = xki [ rki(x−k)− x⊤k rk (x−k)− Tk ( ln (xki)− x⊤k ln (xk) )] , (QLD)
for all players k ∈ V and all actions i ∈ Sk.
Fixed Points of QLD. Using the convention x lnx := 0 if x = 0 (recall that limx→0+ x lnx = 0), we can see from equation (QLD) that xki(t) = xki(0) for all t > 0, for all i ∈ Sk such that xki(0) ∈ {0, 1}. In other words, the boundary of ∆k 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, ∆k, are trivially fixed points of (QLD).
The interesting part concerns the fixed-points of the dynamics for interior starting points. In this case, equation (QLD), implies that, whenever Tk > 0, any resulting fixed point of (QLD) can only lie again in the interior of ∆k due to the entropy term (ln of the choice probabilities). Clearly, the rate of change of xki must be equal to zero. Formally, this implies that a strategy profile p = (pk)k∈V with pk = (pki)i∈Sk for each k ∈ V is an interior fixed point of (QLD) if
rki(p−k) = p ⊤ k rk (p−k) + Tk ( ln (pki)− p⊤k ln (pk) ) , for all k ∈ V. (6)
Exploration Rates. Equation (QLD) suggests that higher values of Tk’s indicate higher exploration rates, whereas values close to 0 indicate a higher exploitation rates. Specifically, for Tk = 0, the dynamics in (QLD) reduce to the well-known replicator dynamics, and agent k simply selects the action i ∈ Sk with the highest Q-value. On the other hand, as Tk → ∞, player k essentially ignores the input (rewards) from the environment and maximizes the entropy of their current choice distribution (which leads to uniform randomization over their available actions in Sk). From a behavioral perspective, this leads to an equivalent interpretation of the Tk’s as the degree of bounded rationality of the agent [25, 24, 21]. Finally, from an algorithmic perspective, Tk and the corresponding entropy term can be viewed as regularizers that prevent the learning dynamics from overfitting, i.e., reaching the boundary or 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 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 k ∈ V , consider the Q-learning updates in equation (4) and assume that Qi(0) = 0 for all i ∈ Sk. Then, in continuous time, the Q-value updates are given by
Qik(t) = α ∫ t 0 e−αksri(t− s)ds = αe−αkt ∫ t 0 eαksri(s) ds, for any t > 0.
This interpretation also showcases the connection between (QLD) and another commonly studied dynamic in behavioral game theory, Experienced Weighted Attraction (EWA) [14, 21]. Along with the proof of Proposition 3.1, this is explained in more detail in Appendix A.

heading: 3.1 Solution Concept: Quantal Response Equilibria
text: When considering agents with bounded rationality, the standard solution concept is the quantal response equilibrium [36]. In its most common definition, a strategy profile p = (pk)k∈V with
pk = (pki)i∈Sk for each k ∈ V is an Quantal Response Equilibrium (QRE) of Γ, if it satisfies the following logit or softmax expression,
pki = exp (rki(p−k)/Tk)∑
j∈Sk exp (rkj(p−k)/Tk) , for all k ∈ V, i ∈ Sk. (QRE)
The following property suggests that the interior fixed points of (QLD) coincide with the QRE of Γ. Following directly from equations (6) and (QRE), this statement will be the starting point of our convergence analysis of (QLD).
Proposition 3.2 (Interior Fixed Points of (QLD) and QRE). Let Γ be an arbitrary game, with positive exploration rates, Tk > 0 for all k ∈ V . Then, for any interior starting point x(0) ∈ ∆, the fixed points of the associated (QLD) always exist and coincide with the QRE of Γ. Moreover, given any such fixed point p, we have, for all xk ∈ ∆k and for all k ∈ V , that
(xk − pk)⊤ [rk(p−k)− Tk ln (pk)] = 0. (7)
Proposition 3.2 does not make use of the weighted network zero-sum property, cf. (2), and thus, it holds for arbitrary network games. We also remark that the QREs are not a refinement of the NEs of Γ and, in fact, the two may be significantly different from each other. However, as we argued above, when Tk = 0 for all k ∈ V , (QLD) reduce to the standard replicator dynamics and in this case, the QRE coincide with the NE of Γ, cf. equations (NE) and (QRE).
Technical Remark. The condition in equation (7) 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, Tk, k ∈ V are positive and not merely non-negative. The intuition is that when all Tk > 0, every QRE becomes interior, i.e., has full support. This implies that all deviations to pure or mixed actions give the same expected reward to the deviating agent. If some Tk are equal to 0, 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 a boundary point even if the dynamics start in the interior.

heading: 4 Convergence of Q-learning in Weighted Zero-sum Polymatrix Games
text: Our main result is that Q-learning (QLD) converges to the QRE of any weighted zero-sum polymatrix game, Γ. 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 ∈ ∆, and the sequence of play, x(t), t ≥ 0 ∈ ∆, 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-Leibler (KL) Divergence). The Kullback-Leibler or KL-Divergence (also called relative entropy), DKL, between two strategy profiles p = (pk)k∈V ,x(t) = (xk(t))k∈V ∈ ∆ with pk = (pki)i∈Sk and xk(t) = (xki(t))i∈Sk ∈ ∆k for all k ∈ V , is defined as
DKL (p ∥ x(t)) := ∑
k∈V DKL(pk ∥ xk(t)) = ∑ k∈V p⊤k ln ( pk
xk(t)
) , (8)
where p⊤k ln ( pk xk(t) ) = ∑ i∈Sk pki ln (pki/xki(t)). If w = (wk)k∈V is a k-dimensional vector of positive scalars, then the weighted or rescaled KL-divergence, DKL(w), is defined as
DKL(w) (p ∥ x(t)) := ∑
k∈V wkDKL(pk ∥ xk(t)). (9)
The KL-divergence between p and x(t) can be thought of as a measurement of how far the distribution p is from the distribution x(t). However, the KL-divergence is not symmetric, i.e., in general it holds that DKL(p ∥ x(t)) ̸= DKL(x(t) ∥ p). Using the notion of KL-divergence we can now formulate our main result.
Theorem 4.1 (Convergence of (QLD) to (QRE)). Let Γ be a rescaled zero-sum polymatrix game, with positive exploration rates Tk. There exists a unique QRE p such that if x(t), t ≥ 0 is any trajectory of the associated Q-learning dynamics, ẋ = f(x), where fi is given via (QLD), and x(0) is an interior point, then x(t) converges to p exponentially fast. In particular, we have that
d dt DKL(w)(p ∥ x(t)) = − ∑ k∈V wkTk [DKL(pk ∥ xk) +DKL(xk ∥ pk)] . (10)
Sketch of Proof. Let p = (pk) be QRE of Γ (existence of p is guaranteed via Proposition 3.2), and let x(t) be a trajectory of the Q-learning dynamics (QLD) with x(0) an interior point. We will first establish (10), from which the other statements follow. The first step is to derive an explicit formula for the time derivative of the KL divergence between pk and xk(t) for a given player k.
Lemma 4.2. For any QRE equilibrium p and any player k ∈ V we have that
d dt DKL(pk ∥ xk(t)) = (xk − pk)⊤ [rk (x−k)− rk(p−k)]− Tk [DKL(pk ∥ xk) +DKL(xk ∥ pk)] .
It follows from Lemma 4.2 that
d dt DKL(p ∥ x(t)) = ∑ k∈V d dt wkDKL(pk ∥ xk)
= ∑ k∈V wk [ (xk − pk)⊤ [rk (x−k)− rk(p−k)]− Tk (DKL(pk ∥ xk) +DKL(xk ∥ pk)) ] (11)
= ∑ k∈V wk(xk − pk)⊤ [rk (x−k)− rk(p−k)]− ∑ k∈V wkTk [DKL(pk ∥ xk) +DKL(xk ∥ pk)] .
Notice that (10) follows from the last line of (11) 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 = (pk)k∈V , and any point x = (xk)k∈V ∈ ∆ we have that∑ k∈V wk [ x⊤k rk (p−k) + p ⊤ k rk (x−k) ] = 0.
Returning to (11), we have that the first term in the right-hand side of the last equation vanishes since∑ k∈V wk(xk − pk)⊤ [rk (x−k)− rk(p−k)] = ∑ k∈V wkx ⊤ k rk (x−k) + ∑ k∈V wkp ⊤ k rk(p−k)
+ ∑
k∈V wk
[ x⊤k rk (p−k) + p ⊤ k rk (x−k) ] = 0,
where the last equality follows from both the zero-sum property (2) and Lemma 4.3. Thus,
d dt DKL(p ∥ x(t)) = − ∑ k∈V wkTk [DKL(pk ∥ xk) +DKL(xk ∥ pk)] .
This equality implies that DKL(w) is a Lyapunov function for the Q-learning dynamics. Moreover, it implies that p is unique, and that x(t) is converging to p at an exponential rate.
Approximate Equilibrium Selection Mechanism. Theorem 4.1 provides a tractable, algorithmic approach to the problem of equilibrium selection in weighted zero-sum polymatrix games. Given any such a game Γ, an interior initial condition and positive exploration rates Tk, Theorem 4.1 guarantees that the Q-learning agents will converge to a unique QRE of Γ at an exponentially fast rate. This unique QRE can be very different from any Nash equilibrium of Γ if the exploration rates are high, but it will be arbitrarily close to some Nash equilibrium of Γ 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.
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 a unique QRE of a weighted zero-sum polymatrix game. As demonstrated next in our experimental section, there can be multiple QREs if one or some agents have zero exploration rates.

heading: 5 Experiments: Equilibrium Selection in Competitive Games
text: Two-Agent Weighted Zero-Sum Games. Starting with the performance of (QLD) in this lowdimensional 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, a variation of the matching pennies [58], in which each agent has two actions, {H,T}, and payoffs
A = ( 2 −2 0 2 ) B = ( 4 0 −4 −4 ) . (AMPs)
The AMPs game is a weighted zero-sum game since A+ 0.5 ·B⊤ = 0 (each agent is the row agent in their matrix), with a unique interior Nash equilibrium, (p,q) = ((1/3, 2/3), (2/3, 1/3)).
Results: In Figure 1, we visualize the QRE surfaces (light blue manifolds) for different exploration rates Tx, Ty of the two agents (x− y plane). The vertical axis shows the probability with which agent 1 chooses H at the unique QRE of the game. We plot the exploration path along two representative exploration-exploitation policies: Explore-Then-Exploit (ETE) [5], which starts with (relatively) high exploration that gradually reduces to zero and Cyclical Learning Rate with 1 cycle (CLR-1) [50], which starts with low exploration, increases to high exploration around the half-life of the cycle and then decays to 0. 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.e., select) the unique QRE (i.e., the Nash equilibrium in this case) of the original game.
By contrast, the first tile of Figure 2 shows that the dynamics cycle around the unique Nash equilibrium when both agents do not use exploration. The rest of the tiles of Figure 2 show that in this case, exploration by only one agent suffices to lead the joint-learning dynamics to converge to a unique QRE. In 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 is not sufficient for convergence.
Experimental setup: We consider the Match-Mismatch weighted zero-sum polymatrix game (MMG) with n+ 2 agents (n ∈ N is arbitrary) which is shown in Figure 3. Each of the agents p1 to
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 d1 and T for d2. The payoff matrices for the games between non-dummy agents are given by
A+ =
( 1 −1
−1 1
) , A− = −A+ (MMG)
whereas the payoff matrices of dummy agents d1 and d2 are given by A1 = A2 = (1,−1). The column agents in the payoff matrices A1 and A2 are p1 and pn, and their payoffs in the encounters against d1 and d2 are given by −A⊤1 and −A⊤2 , respectively. This game has infinite many NE of the following form: the odd-numbered agents play strategy T (which, for agent 1 ensures +1 against d1) 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 ).
Results: In Figure 4, we consider an instance of (MMG) with n = 3 non-dummy agents and show the projections (tiles 1 to 3) of the QRE surfaces on the H coordinate at QRE for agents 1 to 3 for fixed T3 = 3 and all possible combinations of T1, T2 (x-y planes). The QRE manifolds continuously approach the boundary (case with Ti = 0 for i = 1, 2) which leads to a unique equilibrium selection also when T1 = T2 = 0. Tile 4 shows a snapshot of the Lyapunov function (KL-divergence between choice distribution x and unique QRE q) in a 7 non-dummy agents instance of (MMG) for a fixed exploration profile with positive exploration rates for all agents, Tk > 0, for all k = 1, . . . , 7. To obtain this plot, (which is 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 = 7 (MMG) instance for three different exploration profiles. The tiles in the left column show the equilibria (top) and utilities (bottom) of the 7 agents
in 100 runs when Tk = 0 for all k = 1, 2, . . . , n (no exploration). In this case, (QLD) converge in all runs to the pure action for the odd agents and to 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 highdimensional simplex (cf. [38]). The tiles in the middle column correspond to a case with exploration by agents 1, 2, 3 and no exploration by agents 4 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 to converge to a unique outcome 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 a 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 4 and 6 (upper middle tile) and to non-unique payoffs for agents 5 and 7 but also for agent 3 who has a positive exploration rate (lower middle tile). Finally, the tiles in the right column show convergence to a unique QRE when all agents have positive exploration rates.

heading: 6 Conclusions
text: 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 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 is a 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 a 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 a unique QRE that we prove in this paper establishes an efficient and simple mechanism to select (approximate) Nash equilibria, implying that the problem of equilibrium selection is tractable within competitive multi-agent settings as well. In particular, while a 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-exploitation with Q-learning works well in both as an 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 under its AI Singapore Program (AISG Award No: AISG2-RP-2020-016), NRF 2018 Fellowship NRF-NRFF2018-07, NRF2019-NRF-ANR095 ALIAS grant, grant PIE-SGP-AI-2018-01, AME Programmatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A*STAR), and by EPSRC grant EP/R018472/1.

Review summaries:
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.