scaletikzpicturetowidth[1]

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

Stefanos Leonardos  Singapore University of Technology and Design, _{
stefanos_leonardos<EMAIL_ADDRESS>Georgios Piliouras  Singapore
University of Technology and Design, _{ stefanos_leonardos,
<EMAIL_ADDRESS>Kelly Spendlove  Mathematical Institute, University of
Oxford<EMAIL_ADDRESS>
###### 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 [14, 32], we show that fast convergence of Q-learning in
competitive settings is obtained 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.

##  1 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 no change in the
expected payoffs, or one of the two expected payoffs increases and the other
decreases.111In 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]. 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 [51].

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 payoffs need not be unique. In fact, there could be continua of
equilibria with the payoff range of different agents corresponding to positive
measure sets. Furthermore, Nash equilibrium strategies need not be
exchangeable (i.e., mixing-matching strategies from different Nash profiles
does not lead to a Nash) or max-min. Thus, network competition is not only
significantly harder, but poses qualitatively different questions than two-
agent competition.

Nevertheless, and in spite of the intense recent interest, inspired by ML
applications such as Generative Adversarial Networks (GANs) and actor-critic
systems, on understanding learning dynamics in zero-sum games and even network
variants thereof [17, 20, 25], so far there has been no systematic study of
how agents should deal with uncertainty of the resulting 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 [13, 39, 11, 57].
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 [53, 52], with softmax or
Boltzmann exploration (one of the most fundamental models of exploration-
exploitation in MAS), termed Boltzmann Q-learning or _smooth Q-learning_ [49,
46]. Informally (see Section 3 for the rigorous definition), each agent $k$
updates their choice distribution $x=(x_{i})$ according to the rule
$\dot{x}_{i}/x_{i}=(r_{i}-\bar{r})-T_{k}(\ln{x_{i}}-\sum_{j}x_{j}\ln{x_{j}})$,
where $r_{i},\bar{r}$ denote agent $k$’s rewards from action $i$ and average
rewards, respectively, given all other agents’ actions and $T_{k}$ 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 NE for games with bounded
rationality [34]) in arbitrary networks of strictly competitive games [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.
This theoretically and empirically long-standing open problem ([30, 43, 41])
becomes tractable 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 as long as not all of the agents
are performing exploration (see discussion and experiments 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 [45, 29, 55]. It
has also been also extensively studied in the economics and reinforcement
learning literature under various names, see e.g., [2, 44] and [26, 37].
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 bifurcations [32].

On the other hand, competitive multi-agent systems constitute one of the
current frontiers in Artificial Intelligence and Machine Learning research.
Many recent works investigate the complex behavior of competitive game
theoretic settings [42, 9, 8, 7, 35], focusing on carefully designed
convergent algorithms, e.g., “optimism” [17, 18, 54], extra-gradient methods
[38, 3, 24], regularization [41], momentum adapted dynamics [21], or
symplectic integration schemes [6]. However, despite the theoretical progress
and the impressive results in the empirical front [47, 50, 31], 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 [15, 16]. 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 Preliminaries

A _polymatrix or separable network game_ ,
$\Gamma=\left((V,E),\left(S_{k},w_{k}\right)_{k\in
V},\left(\mathbf{A}_{kl}\right)_{[k,l]\in E}\right)$ consists of a graph
$(V,E)$, where $V=\\{1,2,\dots,n\\}$ is the set of players (or agents), and
$E$ is a set of pairs, $[k,l]$, of players $k\neq l\in V$. Each player, $k\in
V$, has a finite set of actions (or strategies) $S_{k}$ with generic elements
$s_{k}\in S_{k}$ (depending on the context, sometimes we will also write $i$
or $j\in S_{k}$). Players may also use mixed strategies (or choice
distributions) $\mathbf{x}_{k}=(x_{ki})_{i\in S_{k}}\in\Delta_{k}$, where
$\Delta_{k}$ is the simplex in $\mathbb{R}^{|S_{k}|}$, i.e., $\sum_{i\in
S_{k}}x_{ki}=1$, and $x_{ki}\geq 0$, for any $\mathbf{x}_{k}\in\Delta_{k}$.
The _interior_ of $\Delta_{k}$ is the set of all points
$\mathbf{x}_{k}\in\Delta_{k}$ with $x_{ki}\in(0,1)$ for all $i\in S_{k}$. All
points of $\Delta_{k}$ that are not in the interior, are called _boundary
points_. We will write
$\mathbf{x}=(\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{n})$ or
$\mathbf{x}=(\mathbf{x}_{k},\mathbf{x}_{-k})$ for a mixed strategy profile
$\mathbf{x}\in\Delta:=\prod_{k\in V}\Delta_{k}$, where
$\mathbf{x}_{-k}\in\Delta_{-k}=\prod_{l\neq k\in V}\Delta_{l}$ is the vector
of mixed strategies of all players $l\in V$ other than $k$.

Each edge $[k,l]\in E$ defines a two player game with payoff matrices
$\mathbf{A}_{kl}\in\mathbb{R}^{|S_{k}|\times|S_{l}|}$ and
$\mathbf{A}_{lk}\in\mathbb{R}^{|S_{l}|\times|S_{k}|}$. The elements
$a_{kl}(s_{k},s_{l})$ of a matrix $\mathbf{A}_{kl}$ denote the payoffs of
player $k$ when players $k$ and $l$ use pure actions $s_{k}\in S_{k}$ and
$s_{l}\in S_{l}$, respectively. Each player $k\in V$ chooses a strategy (mixed
or pure) and plays that strategy in _all_ games $[k,l]\in E$. Thus, the payoff
of player $k$ at the pure strategy profile $\mathbf{s}=(s_{1},\dots,s_{n})\in
S:=\prod_{k\in V}S_{k}$ is $u_{k}(\mathbf{s})=\sum_{[k,l]\in
E}a_{kl}(s_{k},s_{l})$. Similarly, the expected reward of player $k$ in the
mixed strategy profile $\mathbf{x}\in\Delta$ is

$u_{k}(\mathbf{x}):=\sum\nolimits_{[k,l]\in
E}\mathbf{x}_{k}^{\top}\mathbf{A}_{kl}\mathbf{x}_{l}=\mathbf{x}_{k}^{\top}\left(\sum\nolimits_{[k,l]\in
E}\mathbf{A}_{kl}\mathbf{x}_{l}\right).$ (1)

It will be convenient to write
$r_{ki}(\mathbf{x}_{-k}):=u_{k}\left(i,\mathbf{x}_{-k}\right)=\sum_{[k,l]\in
E}\\{\mathbf{A}_{kl}\mathbf{x}_{l}\\}_{i}$ (where $\\{v\\}_{i}$ to denotes the
$i$-th element of a vector $v$), for the reward of pure action $i\in S_{k}$ of
player $k$ when all other players use the strategy profile $\mathbf{x}_{-k}$
and $r_{k}\left(\mathbf{x}_{-k}\right):=(r_{ki}(\mathbf{x}_{-k}))_{i\in
S_{k}}$ for the resulting reward vector of all pure actions of agent $k$,
respectively. Using this notation, the expected reward of player $k\in V$ at
the mixed strategy profile $\mathbf{x}=(\mathbf{x}_{k},\mathbf{x}_{-k})$ can
be compactly expressed as
$u_{k}(\mathbf{x})=\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)$.

#### Weighted Zero-Sum Polymatrix Games.

$\Gamma$ is called a _weighted or rescaled_ zero-sum polymatrix game [12], if
there exist positive constants $w_{1},w_{2},\dots,w_{n}>0$, so that

$\sum\nolimits_{k\in V}w_{k}u_{k}(\mathbf{x})=0,\;\;\text{for all
}\mathbf{x}\in\Delta.$ (2)

By summing over the edges in $E$ (instead of the players in $V$), we can
equivalently express the weighted zero-sum property as

$\sum\nolimits_{[k,l]\in
E}\left[w_{k}\mathbf{x}_{k}^{\top}\mathbf{A}_{kl}\mathbf{x}_{l}+w_{l}\mathbf{x}_{l}^{\top}\mathbf{A}_{lk}\mathbf{x}_{k}\right]=0,\;\;\text{for
all }\mathbf{x}\in\Delta.$ (3)

#### Nash Equilibrium.

A strategy profile (tuple of mixed strategies), $\mathbf{p}=(p_{k})_{k\in
V}\in\Delta$, with $\mathbf{p}_{k}=(p_{ki})_{i\in S_{k}}\in\Delta_{k}$ for
each $k\in V$ is a _Nash equilibrium_ of $\Gamma$ if

$u_{k}(\mathbf{p})\geq u_{k}(x_{k},\mathbf{p}_{-k}),\quad\text{for all
}x_{k}\in\Delta_{k},\;\text{for all }k\in V,$ (4)

i.e., if there exist no profitable unilateral deviations. By linearity, it
suffices to verify the condition in equation (4) only for pure actions
$s_{k}\in S_{k}$ instead of all $x_{k}\in\Delta_{k}$.

##  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 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 [53, 52] 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. In
Q-learning, each agent $k\in\mathcal{N}$ keeps track of the past performance
of their actions $i\in S_{k}$ via the Q-learning update rule

$Q_{ki}(n+1)=Q_{ki}(n)+\alpha_{k}\left[r_{ki}(\mathbf{x}_{-k},n)-Q_{ki}(n)\right],\;i\in
S_{k}$ (5)

where the additional argument, $n\geq 0$, denotes (discrete) time steps and
$\alpha_{k}\in[0,1]$ denotes the learning rate or memory decay of agent $k$,
cf. [46, 29]. $Q_{ki}(t)$ is called the _memory_ of agent $k$ about the
performance of action $i\in S_{k}$ up to time step $t\geq 0$. Agent $k\in V$
updates their actions (choice distributions) according to a Boltzmann type
distribution, with

$x_{ki}(n)=\frac{\exp{(Q_{ki}(n)/T_{k})}}{\sum_{j\in
S_{k}}\exp{(Q_{kj}(n)/T_{k})}},\quad\text{for each }i\in S_{k},$ (6)

where $T_{k}\in[0,+\infty)$ 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 $T_{k}$ as the _exploration rate_ or
_temperature_ of player $k$ [32, 49] (see Remark 1 for a discussion).
Combining equations (5) and (6), one obtains the recursive equation of player
$k$’s mixed strategy (or choice distribution)

$\displaystyle
x_{ki}(n+1)=\frac{x_{ki}(n)\exp{((Q_{ki}(n+1)-Q_{ki}(n))/T_{k})}}{\sum_{j\in
S_{k}}x_{kj}(n)\exp{((Q_{kj}(n+1)-Q_{kj}(n))/T_{k})}}\,,$

for each $i\in S_{k}$. In practice, agents perform a large number of actions
(updates of Q-values) for each choice-distribution (update of Boltzmann
selection probabilities). This motivates to consider a continuous time version
of the learning process for each agent $k\in V$ which results in the following
update rules for both the memories $Q_{ki}$ and the selection probabilities
$x_{ki}$ of each action $i\in S_{k}$

$\dot{Q}_{ki}=\alpha_{k}\left[r_{ki}(\mathbf{x}_{-k})-Q_{ki}\right],\;\text{
and }\;\dot{x}_{ki}=x_{ki}\left(\dot{Q}_{ki}-\sum\nolimits_{j\in
S_{k}}\dot{Q}_{kj}\right)/T_{k},$

where we suppressed the dependence on (the continuous) time steps $t\geq 0$.
Combining the last two equations under the assumptions that the relationship
between pairs of actions is constant over time and that the choice
distributions of the various agents are independently distributed, yields the
_Q-learning dynamics_

$\dot{x}_{ki}=x_{ki}\left[r_{ki}(\mathbf{x}_{-k})-\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)-T_{k}\left(\ln{(x_{ki})}-\mathbf{x}_{k}^{\top}\ln{(\mathbf{x}_{k})}\right)\right],$
(7)

for all $i\in S_{k}$ and all players $k\in V$. The next property provides
intuition for the meaning of Q-values in a practical context (see also Remark
1 for a discussion). As is the case for all technical materials of this
section, the proof of Proposition 3.1 is deferred to Appendix A.

######  Proposition 3.1 (Q-value Updates and Exponential Discounting).

Consider the Q-learning updates

$Q_{i}(n+1)=Q_{i}(n)+\alpha[r_{i}(n)-Q_{i}(n)]$ (8)

where $n\geq 0$ are discrete time steps and assume that $Q_{i}(0)=0$ for all
$i\in A$. Then, in continuous time, the updates are given by

$Q_{i}(t)=\alpha\int_{0}^{t}e^{-\alpha s}r_{i}(t-s)ds=\alpha e^{-\alpha
t}\int_{0}^{t}e^{\alpha s}r_{i}(s)\mathop{ds},\quad\text{for any }t>0.$

######  Remark 1.

Equation (6) implies that higher values of $T_{k}$ indicate a higher
exploration rate, i.e., randomization among the agent’s available choices in
$S_{k}$, whereas values of $T_{k}$ close to $0$ indicate a higher exploitation
rate, i.e., preference of the agent towards the best performing action.
Specifically, for $T_{k}\to 0$, (6) corresponds to the best-response update
rule, and agent $k$ selects the action $i\in S_{k}$ with the highest $Q$-value
with probability one. On the other hand, as $T_{k}\to\infty$, equation (6)
corresponds to the case in which player $k$ selects their actions uniformly at
random.

From a behavioral perspective, this leads to an equivalent interpretation of
the $T_{k}$’s as the degrees of (bounded) rationality of the agents [23, 22,
19]. Similarly, Proposition 3.1 implies that the Q-learning updates can be
intuitively interpreted as exponential discounting in the payoffs, with
payoffs further back in the past being less important. In other words, the
Q-value of an agent for an action $i$ shows how beneficial the (discounted)
strategy $i$ is for that agent. On the other hand, from a purely algorithmic
perspective, the $T_{k}$’s and the corresponding entropy terms in the players’
choice distributions updates can be viewed as regularization terms that
prevent the learning dynamics from reaching the boundary or from getting
trapped in local optima, see [10, 14, 36] and [27, 28].

#### Quantal Response Equilibria.

Using the convention $x\ln{x}:=0$ whenever $x=0$ (recall that $\lim_{x\to
0^{+}}x\ln{x}=0$), it is immediate to infer from equation (7) that
$x_{ki}(t)=x_{ki}(0)$ for all $t>0$, for all $i\in S_{k}$ such that
$x_{ki}(0)\in\\{0,1\\}$. In other words, if the dynamics start on the
boundary, then they will remain there, i.e., the boundary of $\Delta_{k}$ is
invariant for the Q-learning dynamics. This implies, in particular, that all
corner points of the simplex $\Delta_{k}$, i.e, all points
$x_{k}=(x_{ki})_{i\in S_{k}}$ with one coordinate equal to $1$ (and
consequently, all other coordinates equal to $0$) are (trivially) fixed points
of the Q-learning dynamics. Thus, the interesting part concerns the fixed-
point analysis of the dynamics for _interior_ starting points.

The _interior_ fixed points of the Q-learning dynamics are called _Quantal
Response Equilibria_. From equation (7), it is apparent that whenever
$T_{k}>0$ for all $k\in V$, then such points can only lie in the interior of
$\Delta_{k}$ due to the entropy term ($\ln$ of the choice probabilities).
Thus, at such fixed points the rate of change of $x_{ki}$ must be equal to
zero. Specifically, a strategy profile $\mathbf{p}=(p_{k})_{k\in V}$ with
$\mathbf{p}_{k}=(p_{ki})_{i\in S_{k}}$ for each $k\in V$ is a _Quantal
Response Equilibrium (QRE)_ of $\Gamma$ if

$r_{ki}(\mathbf{p}_{-k})=\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+T_{k}\left(\ln{(p_{ki})}-\mathbf{p}_{k}^{\top}\ln{(\mathbf{p}_{k})}\right),\;\;\text{for
all }k\in V.$ (9)

The following properties are immediate from the characterization of the QRE in
equation (9).

######  Theorem 3.2 (Interior Fixed Points of the Q-learning Dynamics).

Let $\Gamma$ be an arbitrary game, with positive exploration rates $T_{k}$ and
consider the associated Q-learning dynamics

$\dot{x}_{ki}=x_{ki}\left[r_{ki}(\mathbf{x}_{-k})-\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)-T_{k}\left(\ln{(x_{ki})}-\mathbf{x}_{k}^{\top}\ln{(\mathbf{x}_{k})}\right)\right],\;\;i\in
S_{k},k\in V.$

The interior fixed points, $\mathbf{p}=(p_{k})_{k\in V}$ of the Q-learning
dynamics are the solutions of the system

$p_{ki}=\frac{\exp{\left(r_{ki}(\mathbf{p}_{-k})/T_{k}\right)}}{\sum_{j\in
S_{k}}\exp{\left(r_{kj}(\mathbf{p}_{-k})/T_{k}\right)}},\quad\text{for all
}i\in S_{k}.$ (10)

Such fixed points always exists and coincide with the Quantal Response
Equilibria (QRE) of $\Gamma$. Given any such fixed point $\mathbf{p}$, we
have, for all $\mathbf{x}_{k}\in\Delta_{k}$ and for all $k\in V$, that

$(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}(\mathbf{p}_{-k})-T_{k}\ln{(\mathbf{p}_{k})}\right]=0.$
(11)

The proof of Theorem 3.2 does not make use of the weighted zero-sum property,
cf. equation (2), and thus, it holds for arbitrary network games (not
necessarily weighted network zero-sum).

#### Exploration Rates.

Equation (11) in Theorem 3.2 is critical for the main technical step in our
proof of convergence of the Q-learning dynamics in weighted zero-sum
polymatrix games. Thus, it is important to note that this equation only holds
when _all_ exploration rates, $T_{k},k\in V$ are positive (and not merely non-
negative). The intuition is that when all $T_{k}>0$, every QRE becomes
interior, i.e., has full support. This implies that all deviations (to pure or
mixed strategies) give the _same_ expected reward to the deviating agent. If
some $T_{k}$ are equal to $0$, then (11) holds with (non-strict) inequality
which is not generally enough for the proof of Theorem 4.1.

When $T_{k}=0$ for all $k\in V$, the Q-learning dynamics reduce to the
standard replicator dynamics and the QRE coincide with the Nash equilibria of
$\Gamma$, cf. equation (4). The case in which only some $T_{k}$ are equal to
$0$ exhibits more interesting behavior and will be discussed in detail later.
In brief, if this is the case, then the dynamics may also converge to a
boundary point (for the non-exploring players, i.e., for the players $k\in V$
with $T_{k}=0$), even if the dynamics start in the interior.

##  4 Convergence of Q-learning in Weighted Zero-sum Polymatrix Games

Next, we consider the joint learning model (Q-learning) of the previous
section in rescaled zero-sum polymatrix games, $\Gamma$, as defined above. Our
main result in this section is that Q-learning converges to the QRE of
$\Gamma$. The key step of the proof is to show that the _distance_ between an
interior QRE, $\mathbf{p}\in\Delta$ and the sequence of play,
$\mathbf{x}(t),t\geq 0\in\Delta$, that is generated by the Q-learning model 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_),
$D_{\text{KL}}$, between two strategy profiles
$\mathbf{p}=(\mathbf{p}_{k})_{k\in V},\mathbf{x}(t)=(\mathbf{x}_{k}(t))_{k\in
V}\in\Delta$ with $\mathbf{p}_{k}=(p_{ki})_{i\in S_{k}}$ and
$\mathbf{x}_{k}(t)=(x_{ki}(t))_{i\in S_{k}}\in\Delta_{k}$ for all $k\in V$, is
defined as

$D_{\text{KL}}\left(\mathbf{p}\parallel\mathbf{x}(t)\right):=\sum\nolimits_{k\in
V}D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k}(t))=\sum\nolimits_{k\in
V}\mathbf{p}_{k}^{\top}\ln{\left(\frac{\mathbf{p}_{k}}{\mathbf{x}_{k}(t)}\right)},$
(12)

where
$\mathbf{p}_{k}^{\top}\ln{\left(\frac{\mathbf{p}_{k}}{\mathbf{x}_{k}(t)}\right)}=\sum_{i\in
S_{k}}p_{ki}\ln{(p_{ki}/x_{ki}(t))}$. If $\mathbf{w}=(w_{k})_{k\in V}$ is a
$k$-dimensional vector of positive scalars, then the _weighted or rescaled KL-
divergence_ , $D_{\text{KL}(w)}$, is defined as

$D_{\text{KL}(w)}\left(\mathbf{p}\parallel\mathbf{x}(t)\right):=\sum\nolimits_{k\in
V}w_{k}D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k}(t)).$ (13)

The KL-divergence between $\mathbf{p}$ and $\mathbf{x}(t)$ can be thought of
as a measurement of how far the distribution $\mathbf{p}$ is from the
distribution $\mathbf{x}(t)$. However, the KL-divergence is not symmetric,
i.e., in general it holds that
$D_{\text{KL}}(\mathbf{p}\parallel\mathbf{x}(t))\neq
D_{\text{KL}}(\mathbf{x}(t)\parallel\mathbf{p})$.

#### Main Result.

Using the notion of KL-divergence we can now formulate our main result.

######  Theorem 4.1 (Convergence of Q-learning dynamics).

Let $\Gamma$ be a rescaled zero-sum polymatrix game, with positive exploration
rates $T_{k}$. There exists a unique QRE $\mathbf{p}$ such that if
$\mathbf{x}(t)$ is any trajectory of the associated Q-learning dynamics
$\dot{\mathbf{x}}=f(\mathbf{x})$, with $f_{i}$ is given via (7), where
$\mathbf{x}(0)$ is an interior point, then $\mathbf{x}(t)$ converges to
$\mathbf{p}$ exponentially fast. In particular, we have that

$\frac{d}{dt}D_{\text{KL}(w)}(\mathbf{p}\parallel\mathbf{x}(t))=-\sum\nolimits_{k\in
V}w_{k}T_{k}\left[D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right].$
(14)

###### Sketch of Proof.

Let $\mathbf{p}=(\mathbf{p}_{k})$ be a QRE equilibrium for the Q-learning
dynamics (existence of $\mathbf{p}$ is guaranteed via Theorem 3.2), and let
$\mathbf{x}(t)$ be a trajectory with $\mathbf{x}(0)$ an interior point. We
will first establish (14), from which the other statements follow. The first
step is to derive an explicit formula for the time derivative of the KL
divergence between $\mathbf{p}_{k}$ and $\mathbf{x}_{k}(t)$ for a given player
$k$.

######  Lemma 4.2.

For any QRE equilibrium $\mathbf{p}$ and any player $k\in V$ we have that

$\frac{d}{dt}D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k}(t))=(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]-T_{k}\left[D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right].$

It follows from Lemma 4.2 that

$\displaystyle\frac{d}{dt}D_{\text{KL}}(\mathbf{p}\parallel\mathbf{x}(t))=~{}\sum_{k\in
V}\frac{d}{dt}w_{k}D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})$
$\displaystyle=~{}\sum_{k\in
V}w_{k}\left[(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]-T_{k}\left(D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right)\right]$
$\displaystyle=~{}\sum_{k\in
V}w_{k}(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]-\sum_{k\in
V}w_{k}T_{k}\left[D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right].$
(15)

Notice that (14) follows from (15) if the first term vanishes. This can be
shown by utilizing the following result regarding rescaled zero-sum polymatrix
games.

######  Lemma 4.3.

Given any QRE equilibrium $\mathbf{p}=(\mathbf{p}_{k})$ and
$\mathbf{x}=(\mathbf{x}_{k})$ we have that

$\sum\nolimits_{k\in
V}w_{k}\left[\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)\right]=0.$
(16)

Returning to (15), we have that the first term in the right hand side of the
last equation vanishes since

$\displaystyle\sum_{k\in
V}w_{k}(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]$
$\displaystyle~{}=~{}\sum_{k\in
V}w_{k}\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)+\sum_{k\in
V}w_{k}\mathbf{p}_{k}^{\top}r_{k}(\mathbf{p}_{-k})$
$\displaystyle~{}~{}+\sum_{k\in
V}w_{k}\left[\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)\right]=0,$

where the last equality follows from both the zero-sum property (2) and Lemma
4.3. Thus,

$\displaystyle\frac{d}{dt}D_{\text{KL}}(\mathbf{p}\parallel\mathbf{x}(t))=-\sum\nolimits_{k\in
V}w_{k}T_{k}\left[D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right].$

This equality implies that $D_{\text{KL}(w)}$ is a Lyapunov function for the
Q-learning dynamics. Moreover, it implies that $\mathbf{p}$ is unique, and
that $\mathbf{x}(t)$ is converging to $\mathbf{p}$ at an exponential rate. ∎

#### Equilibrium Selection.

Theorem 4.1 suggests a tractable, algorithmic approach to the problem of
equilibrium selection in weighted zero-sum polymatrix games. In particular,
given an interior initial condition and positive exploration rates $T_{k}$,
Theorem 4.1 guarantees the system will converge to a unique QRE. Moreover, it
will do so exponentially fast. Thus, one can use the following exploration
policy set up a fast-slow system for equilibrium selection: for each player,
the exploration rates $T_{k}$ are brought to zero slowly (the slow system),
while the Q-learning dynamics (the fast system) converge at an exponentially
rate to the unique QRE; this process will approximate a Nash equilibrium of
$\Gamma$.

##  5 Experiments: Equilibrium Selection in Competitive Games

We study the performance of Q-learning in (weighted) network zero-sum and (as
a subcase thereof) in 2-agent zero-sum games. We also investigate numerically
the case in which only _some_ of the agents have positive exploration rates.

#### Two-agent Weighted Zero-Sum Games.

The visualizations that we obtain in this low-dimensional case allow us to
build intuition that carries over to the higher dimensional cases (with more
agents) that we treat later.
Experimental setup: We consider the Asymmetric Matching Pennies (AMPs) (a
variation of the well-known Matching Pennies game [56]) which is a 2-agent,
weighted zero-sum game. Each agent has two actions $\\{H,T\\}$ and the payoff
matrices are $\mathbf{A}=\begin{pmatrix}2&-2\\\
0&\phantom{-}2\end{pmatrix},\mathbf{B}=\begin{pmatrix}\phantom{-}4&\phantom{-}0\\\
-4&-4\end{pmatrix}$. The AMPs game is a weighted zero-sum game since
$\mathbf{A}+0.5\cdot\mathbf{B}^{\top}=0$ (each agent is the row agent in their
matrix), with a unique interior Nash equilibrium,
$(\mathbf{p},\mathbf{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 $T_{x},T_{y}$ of the two agents ($x-y$ plane).

Figure 1: QRE surface and exploration paths (upper panels) for two different
exploration policy profiles (lower panels) in the Asymmetric MPs game. For any
combination of exploration policies (CLR-1 and ETE), the sequence of play
converges to the unique QRE and as the exploration rates decrease zero, the
sequence of play converges to the unique Nash equilibrium of the game.

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 one cycle_ (CLR-1) [48], which starts
with low exploration, increases to high exploration around the half-life of
the cycle and then decays to zero. For each pair of exploration rates, the
learning dynamics converge to the unique QRE that corresponds to these
exploration rates. 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.

Figure 2: Q-learning dynamics in the AMPs game for $T_{x}=0$ (no exploration
by $x$-agent) and four different exploration rates, $T_{y}\geq 0$ by
$y$-agent.

By contrast, the first panel of Figure 2 shows that the dynamics cycle around
the unique Nash equilibrium when both agents do not use exploration. The rest
of the panels of Figure 2 show that in this case, exploration by only one
agent suffices to lead the joint-learning dynamics to convergence. 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 panel 4 in
Figure 2 and Appendix C).

#### Network Zero-Sum Games.

As the next experiment shows, equilibrium selections 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 a zero-sum polymatrix game (ZSPG) with $n+2$ agents
($n\in\mathbb{N}$ is arbitrary) which is depicted in Figure 3.

0.7
$d_{1}$(H)$p_{1}$(H,T)$\dots$$\dots$$p_{n}$(H,T)$d_{2}$(T)$\mathbf{A}_{1}$$\mathbf{A}_{2}$$\mathbf{A}_{+}$$\mathbf{A}_{+}$$\mathbf{A}_{-}$$\mathbf{A}_{-}$

Figure 3: The match-mismatch network zero-sum game.

Each agent $p_{1},p_{2},\dots,p_{n}$ 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, $d_{1},d_{2}$, who have the same
payoffs but only one action: H for $d_{1}$ and $T$ for $d_{2}$. In particular,
the payoff matrices for the games between non-dummy agents are given by

$\mathbf{A}_{+}=\begin{pmatrix}\phantom{-}1&-1\\\
-1&\phantom{-}1\end{pmatrix},\quad\mathbf{A}_{-}=-\mathbf{A}_{+}$ (ZSPG)

whereas the payoff matrices of dummy agents $d_{1}$ and $d_{2}$ are given by
$\mathbf{A}_{1}=\mathbf{A}_{2}=(1,-1)$. The column agents in the payoff
matrices $\mathbf{A}_{1}$ and $\mathbf{A}_{2}$ are $p_{1}$ and $p_{n}$, and
their payoffs in the encounters against $d_{1}$ and $d_{2}$ are given by
$-\mathbf{A}_{1}^{\top}$ and $-\mathbf{A}_{2}^{\top}$, respectively. This game
has multiple (infinite many) Nash equilibria of the following form: the odd-
numbered agents play pure strategy $T$ (which, for agent 1 ensures $+1$
against $d_{1}$) whereas the even agents are indifferent between $H,T$ (since
they are certain to have the opposing result in the two games against the
previous and the next agent, both being odd and playing $T$).

#### Results:

We provide visualizations from two instances of the (ZSPG) game. In the first,
with $n=3$ non-dummy agents (cf. panels 1-3 in Figure 4), we visualize the
projections of the QRE surfaces on the $H$ coordinate at QRE for agents $1$ to
$3$ for fixed $T_{3}=3$ and all possible combinations of $T_{1},T_{2}$ (x-y
planes). The QRE manifolds approach continuously the boundary (case with
$T_{i}=0$ for $i=1,2$) which leads to a unique equilibrium selection (also
when $T_{1}=T_{2}=0$). The fourth panel shows a snapshot of the Lyapunov
function (KL-divergence between a choice distribution $\mathbf{x}$ and the
unique QRE $\mathbf{q}$) for a fixed exploration profile $T_{k}>0$ for all
$k=1,\dots,n$ in an instance with $n=7$ non-dummy agents (the plot is
similarly for all $n$). For this plot, we use the dimension reduction
technique (to visualize high-dimensional surfaces along two randomly chosen
directions) of [33] (see also Appendix C). As expected, the KL-divergence is
convex and decreasing for all $\mathbf{x}$ with a unique minimizer.

Figure 4: Projections of the QRE surfaces on the $H$ coordinate of players
$p_{1},p_{2},p_{3}$ (panels 1-3) and a snapshot of the Lyapunov function, KL-
divergence, (panel 4) in two instances of the (ZSPG) game with $3$ and $7$
non-dummy agents, respectively, as discussed in Section 5.

Figure 5 shows summary statistics for the $n=7$ instance of the (ZSPG) game
for three different exploration profiles. The panels in the leftmost column
show the equilibria (top) and utilities (bottom) of the $7$ agents in $100$
runs when $T_{k}=0$ for all $k=1,2,\dots,n$ (no exploration). In this case,
the dynamics converge in all runs to the pure action for the odd agents and to
some arbitrary (and different every time) mixed action for the even agents.
This behavior of the learning dynamics is in line with previous results in
adversarial learning when equilibria lie on one face (relative boundary) of
the high-dimensional simplex (cf. [36]).

The panels in the middle column correspond to a case with exploration by
agents $1,2,3$ and no exploration by agents $4,\dots,7$. Exploration by the
first group of agents ensures convergence of their individual dynamics to the
corresponding component of the QRE (in line with the theoretical prediction of
Theorem 4.1) but even-numbered agents that lie further away from that group
fail to converge to a unique outcome (boxplot for agents 4 and 6). 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. Finally, the panels in the rightmost column show
convergence to a unique QRE when all agents have positive exploration rates.

Figure 5: Different rates of exploration in an instance of the match-mismatch
ZSPG with $7$ agents. The boxplots show summery statistics from $100$ runs. No
exploration leads to multiple equilibria (first column), exploration by all
agents leads to a unique QRE (last column), whereas equilibrium by some agents
is not enough to ensure convergence to a unique outcome which shows the
tightness of Theorem 4.1 (middle column).

##  6 Conclusions

In this paper, we studied a commonly used smooth variant of the Q-learning
dynamics in multi-agent competitive systems. 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). In particular,
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 may 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, and currently
open problem, of equilibrium selection, which has previously been studied only
within _cooperative_ settings. The bounds we prove on the speed of convergence
of the Q-learning dynamics to the QRE provide the necessary theoretical
guarantees for a simple algorithm to select (approximate) Nash equilibria, in
turn implying that the problem of equilibrium selection is tractable within
competitive multi-agent settings as well. Our results complement previous
advances on the convergence of Q-learning and equilibrium selection in
cooperative settings and provide a promising starting point for exploring
general multi-agent settings which combine elements from both cooperative and
competitive systems.

## Acknowledgements

For this research, Stefanos Leonardos and Georgios Piliouras were supported in
part by NRF2019-NRF-ANR095 ALIAS grant, grant PIE-SGP-AI-2018-01, NRF 2018
Fellowship NRF-NRFF2018-07, AME Programmatic Fund (Grant No. A20H6b0151) from
the Agency for Science, Technology and Research (A*STAR) and the National
Research Foundation, Singapore under its AI Singapore Program (AISG Award No:
AISG2-RP-2020-016). Kelly Spendlove was supported by EPSRC grant EP/R018472/1.

## References

  * [1] I. Adler, C. Daskalakis, and C. H. Papadimitriou.  A 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.12100, 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 on Machine Learning, ICML’20, Madison, WI, USA, 2020. Omnipress.
  * [6] P. 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] P. 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] P. J. Bailey and G. Piliouras.  Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System.  In 18th International Conference on 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 differentiable games.  In ICML, 2018.
  * [10] M. Bowling and M. Veloso.  Multiagent learning using a variable learning rate.  Artificial Intelligence, 136(2):215–250, 2002.
  * [11] L. Busoniu, R. Babuska, and B. De Schutter.  A Comprehensive Survey of Multiagent Reinforcement Learning.  IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156–172, 2008.
  * [12] Y. Cai, O. Candogan, C. Daskalakis, and C. Papadimitriou.  Zero-Sum Polymatrix Games: A Generalization of Minmax.  Mathematics of Operations Research, 41(2):648–655, 2016.
  * [13] C. Claus and C. Boutilier.  The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems.  In Proceedings of the Fifteenth National/Tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence, AAAI ’98/IAAI ’98, page 746–752, 1998.
  * [14] P. Coucheney, B. Gaujal, and P. Mertikopoulos.  Penalty-Regulated Dynamics and Robust Learning Procedures in Games.  Mathematics of Operations Research, 40(3):611–633, 2015.
  * [15] A. Dafoe, E. Hughes, Y. Bachrach, T. Collins, K. R. McKee, J. Z. Leibo, K. Larson, and T. Graepel.  Open Problems in Cooperative AI.  arXiv e-prints, December 2020.
  * [16] C. Daskalakis, D.J. 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.
  * [17] C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng.  Training GANs with Optimism.  In ICLR, 2018.
  * [18] C. Daskalakis and I. Panageas.  Last-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:18, 2018.
  * [19] T. Galla and J. D. Farmer.  Complex dynamics in learning complicated games.  Proceedings of the National Academy of Sciences, 110(4):1232–1236, 2013.
  * [20] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien.  A variational inequality perspective on generative adversarial networks.  In ICLR, 2019.
  * [21] G. Gidel, R. A. Hemmat, M. Pezeshki, G. Huang, R. Lepriol, S. Lacoste-Julien, and I. Mitliagkas.  Negative momentum for improved game dynamics.  In AISTATS, 2019.
  * [22] T.-H. Ho and C. Camerer.  Experience-weighted attraction learning in coordination games: Probability rules, heterogeneity, and time-variation.  Journal of mathematical psychology, 42:305–326, 1998.
  * [23] T.-H. Ho and C. F. Camerer.  Experience-weighted attraction learning in normal form games.  Econometrica, 67:827–874, 1999.
  * [24] Y.-G. Hsieh, F. Iutzeler, J. Malick, and P. Mertikopoulos.  On the convergence of single-call stochastic extra-gradient methods.  arXiv preprint arXiv:1908.08465, 2019.
  * [25] A. Jacob, A. L. Kevin, and A. Wibisono.  Last-iterate convergence rates for min-max optimization: Convergence of hamiltonian gradient descent and consensus optimization.  In V. Feldman, K. Ligett, and S. Sabato, editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 3–47. PMLR, 16–19 Mar 2021.
  * [26] L. P. Kaelbling, M. L. Littman, and A. W. Moore.  Reinforcement learning: A survey.  Journal of Artificial Intelligence Research, 4(1):237–285, 1996\.
  * [27] M. Kaisers and K. Tuyls.  Frequency adjusted multi-agent q-learning.  In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1 - Volume 1, AAMAS ’10, page 309–316, 2010.
  * [28] 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\.
  * [29] A. Kianercy and A. Galstyan.  Dynamics of Boltzmann $Q$ learning in two-player two-action games.  Phys. Rev. E, 85:041145, Apr 2012.
  * [30] Y. Kim.  Equilibrium Selection in n-Person Coordination Games.  Games and Economic Behavior, 15(2):203–227, 1996.
  * [31] M. Lanctot, E. Lockhart, J.-B. Lespiau, V. Zambaldi, S. Upadhyay, J. Pérolat, S. Srinivasan, F. Timbers, K. Tuyls, S. 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. Schrittwieser, T. Anthony, E. Hughes, I. Danihelka, and J. Ryan-Davis.  Openspiel: A framework for reinforcement learning in games, 2020.
  * [32] S. Leonardos and G. Piliouras.  Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory.  In Proceedings of the 35th AAAI Conference on Artificial Intelligence, AAAI-21, 2021.
  * [33] 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-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 6389–6399. Curran Associates, Inc., 2018.
  * [34] R. D. McKelvey and T. R. Palfrey.  Quantal Response Equilibria for Normal Form Games.  Games and Economic Behavior, 10(1):6–38, 1995.
  * [35] P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras.  Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile.  In ICLR, 2019.
  * [36] P. Mertikopoulos, C. Papadimitriou, 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.
  * [37] P. Mertikopoulos and W. H. Sandholm.  Learning in Games via Reinforcement and Regularization.  Mathematics of Operations Research, 41(4):1297–1324, 2016.
  * [38] P. Mertikopoulos, H. Zenati, B. Lecouat, C.-S. Foo, V. Chandrasekhar, and G. Piliouras.  Mirror descent in saddle-point problems: Going the extra (gradient) mile.  ArXiv e-prints, July 2018.
  * [39] L. Panait and S. Luke.  Cooperative Multi-Agent Learning: The State of the Art.  Autonomous Agents and Multi-Agent Systems, 11(3):387–434, Nov 2005\.
  * [40] M. Pangallo, J. Sanders, T. Galla, and D. Farmer.  A taxonomy of learning dynamics in 2 x 2 games.  arXiv e-prints, page arXiv:1701.09043, January 2017.
  * [41] J. Perolat, R. Munos, J.-B. Lespiau, S. Omidshafiei, M. Rowland, P. Ortega, N. Burch, T. Anthony, D. Balduzzi, B. De Vylder, G. Piliouras, M. Lanctot, and K. Tuyls.  From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization, 2020.
  * [42] S. Rakhlin and K. Sridharan.  Optimization, learning, and games with predictable sequences.  In Advances in Neural Information Processing Systems, pages 3066–3074, 2013.
  * [43] J. Romero.  The effect of hysteresis on equilibrium selection in coordination games.  Journal of Economic Behavior & Organization, 111:88–105, 2015\.
  * [44] 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.
  * [45] Y. Sato, E. Akiyama, and J. P. Crutchfield.  Stability and diversity in collective adaptation.  Physica D:Nonlinear Phenomena, 210(1):21–57, 2005.
  * [46] Y. Sato and J. P. Crutchfield.  Coupled replicator equations for the dynamics of learning in multiagent systems.  Phys. Rev. E, 67:015206, Jan 2003.
  * [47] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis.  Mastering the game of Go with deep neural networks and tree search.  Nature, 529(7587):484–489, Jan 2016.
  * [48] L. N. Smith and N. Topin.  Super-Convergence: Very Fast Training of Neural Networks Using Large Learning Rates.  arXiv e-prints, page arXiv:1708.07120, 2017.
  * [49] K. Tuyls, K. Verbeeck, and T. Lenaerts.  A Selection-mutation Model for Q-learning in Multi-agent Systems.  In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS ’03, pages 693–700, 2003.
  * [50] 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, I. Danihelka, A. Huang, L. Sifre, T. Cai, J. P. Agapiou, M. Jaderberg, A. S. Vezhnevets, R. Leblond, T. Pohlen, V. Dalibard, D. Budden, Y. Sulsky, J. Molloy, T. L. Paine, C. Gulcehre, Z. Wang, T. Pfaff, Y. 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):350–354, Nov 2019.
  * [51] J. von Neumann.  Zur theorie der gesellschaftsspiele.  Mathematische Annalen, 100:295–300, 1928.
  * [52] C.J.C.H. Watkins.  Learning from delayed rewards.  PhD thesis, King’s College, Cambridge United Kingdom, 1989.
  * [53] C.J.C.H. Watkins and P. Dayan.  Technical Note: Q-Learning.  Machine Learning, 8(3):279–292, May 1992.
  * [54] 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.
  * [55] 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.
  * [56] M. Wunder, M. Littman, and M. Babes.  Classes of Multiagent Q-Learning Dynamics with $\epsilon$-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.
  * [57] K. Zhang, Z. Yang, and T. Başar.  Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms.  arXiv e-prints, page arXiv:1911.10635, 2019.

##  Appendix A Omitted Proofs and Materials: Section 3

We first restate and prove Proposition 3.1.

Proposition 3.1. Consider the Q-learning updates

$Q_{i}(n+1)=Q_{i}(n)+\alpha[r_{i}(n)-Q_{i}(n)]$ (17)

where $n\geq 0$ are discrete time steps and assume that $Q_{i}(0)=0$ for all
$i\in A$. Then, in continuous time, the updates are given by

$Q_{i}(t)=\alpha\int_{0}^{t}e^{-\alpha s}r_{i}(t-s)ds=\alpha e^{-\alpha
t}\int_{0}^{t}e^{\alpha s}r_{i}(s)\mathop{ds},\quad\text{for any }t>0.$

###### Proof.

We will provide two proofs of the above statement. For the first, we solve the
recursion in equation (17) and then use the approximation of the exponential
function by the geometric sum. Specifically, we have that

$\displaystyle Q_{i}(n+1)$ $\displaystyle=\alpha r_{i}(n)+(1-\alpha)Q_{i}(n)$
$\displaystyle=\alpha r_{i}(n)+(1-\alpha)[\alpha
r_{i}(n-1)+(1-\alpha)Q_{i}(n-1)]$ $\displaystyle=\alpha
r_{i}(n)+(1-\alpha)\alpha r_{i}(n-1)+(1-\alpha)^{2}Q_{i}(n-1)$
$\displaystyle=\alpha r_{i}(n)+(1-\alpha)\alpha
r_{i}(n-1)+(1-\alpha)^{2}[\alpha r_{i}(n-2)+(1-\alpha)Q_{i}(n-2)]$
$\displaystyle=\dots$
$\displaystyle=(1-\alpha)^{n+1}Q_{i}(0)+\sum_{k=0}^{n}\alpha(1-\alpha)^{k}r_{i}(n-k)$
$\displaystyle=\sum_{k=0}^{n}\alpha(1-\alpha)^{k}r_{i}(n-k)$

where in the last equation we did a change of variables in the summation since
$Q_{i}(0)=0$ by assumption. By taking continuous time steps (i.e., if instead
of $k\to k+1$, we consider $k\to\Delta k$ with $\Delta k\to 0$), then the
above becomes

$Q(t)=\alpha\int_{0}^{t}e^{-as}r_{i}(t-s)ds$

as claimed. By a change of variables, we also obtain the second expression in
the Lemma’s statement. The second way to prove this statement is by
considering directly a continuous time version of (17). In this case, we have
that

$\dot{Q}_{i}(s)=\alpha[r_{i}(s)-Q_{i}(s)],$

where $\dot{Q}_{i}(s)$ denotes the time derivative of $Q_{i}(s)$, i.e.,
$dQ_{i}(s)/ds$. This is a first order non homogeneous (in the constant term)
linear differential equation of the form

$\dot{Q}_{i}(s)+\alpha Q_{i}(s)=\alpha r_{i}(s).$

By multiplying both sides with the integrating factor $e^{\alpha s}$, we
obtain that

$e^{\alpha s}[\dot{Q}_{i}(s)+\alpha Q_{i}(s)]=\alpha e^{\alpha
s}r_{i}(s)\implies\frac{d}{ds}(e^{\alpha s}Q_{i}(s))=\alpha e^{\alpha
s}r_{i}(s).$

We can now integrate both sides of the last expression from $0$ to $t$ to
obtain that

$e^{\alpha t}Q_{i}(t)=\alpha\int_{0}^{t}e^{\alpha s}r_{i}(s)ds\implies
Q_{i}(t)=\alpha e^{-\alpha t}\int_{0}^{t}e^{\alpha s}r_{i}(s)ds$

as claimed, where the integration constant disappears due to the boundary
condition $Q_{i}(0)=0$. ∎

###  A.1 Derivation of Q-learning dynamics

We next provide two formal derivations of the Q-learning dynamics of equation
(7). Similar calculations can be found in [49, 46, 45, 29] and [19, 40].

######  Proposition A.1 (Derivation of Q-learning Dynamics).

Assume that players select their actions according to a Boltzmann (or softmax)
distribution with parameter $T$, i.e.,

$x_{i}(t)=\frac{\exp{\left(Q_{i}(t)/T\right)}}{\sum_{j\in
A}\exp{\left(Q_{j}(t)/T\right)}}\,\quad\text{for any }t>0,$ (18)

with $x_{i}(0)$ is initialized arbitrarily for all $i\in A$, where $Q_{i}(t)$
is the Q-value of action $i$ at time $t$. Then, the evolution of the action
probabilities is governed by the Q-learning dynamics

$\dot{x}_{i}(t)=x_{i}(t)\left[r_{i}(t)-\sum_{j\in
A}r_{j}(t)x_{j}(t)-T\left(\ln{x_{i}(t)}-\sum_{j\in
A}x_{j}(t)\ln{x_{j}(t)}\right)\right].$ (19)

###### Proof.

The time derivative of $x_{i}(t)$ is equal to

$\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\frac{\exp{\left(Q_{i}(t)/T\right)}}{T\sum_{j\in
A}\exp{\left(Q_{j}(t)/T\right)}}\left[\dot{Q}_{i}\left(t\right)-\frac{\sum_{j\in
A}\dot{Q}_{j}(t)\exp{\left(Q_{j}(t)/T\right)}}{\sum_{j\in
A}\exp{\left(Q_{j}(t)/T\right)}}\right]$
$\displaystyle=\frac{1}{T}x_{i}(t)\left[\dot{Q}_{i}\left(t\right)-\sum_{j\in
A}\left(\frac{\exp{\left(Q_{j}(t)/T\right)}}{\sum_{j\in
A}\exp{\left(Q_{j}(t)/T\right)}}\right)\dot{Q}_{j}(t)\right]$
$\displaystyle=\frac{1}{T}x_{i}(t)\left[\dot{Q}_{i}\left(t\right)-\sum_{j\in
A}x_{j}(t)\dot{Q}_{j}(t)\right].$

Hence, using that $\dot{Q}_{i}(t)=\alpha[r_{i}(t)-Q_{i}(t)]$, the above yields

$\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\frac{\alpha}{T}x_{i}(t)\left[r_{i}(t)-Q_{i}(t)-\sum_{j\in
A}x_{j}(t)[r_{j}(t)-Q_{j}(t)]\right]$
$\displaystyle=\frac{\alpha}{T}x_{i}(t)\left[r_{i}(t)-\sum_{j\in
A}x_{j}(t)r_{j}(t)-\left(Q_{i}(t)-\sum_{j\in
A}x_{j}(t)Q_{j}(t)\right)\right].$ ($\ast$)

Finally, taking $\ln{}$ in equation (18), and solving for $Q_{i}(t)$, we have
that

$Q_{i}(t)=T\left[\ln{x_{i}(t)}+\ln{\left(\sum_{j\in
A}\exp{(Q_{j}(t)/T)}\right)}\right]$

In the above expression, we may set $C:=\ln{\left(\sum_{j\in
A}\exp{(Q_{j}(t)/T)}\right)}$ since this term is the same for all $i\in A$.
Thus, we have that

$\displaystyle Q_{i}(t)-\sum_{j\in A}x_{j}(t)Q_{j}(t)$
$\displaystyle=T\left(\ln{x_{i}(t)}+C\right)-\sum_{j\in
A}x_{j}(t)T\left(\ln{x_{i}(t)}+C\right)$
$\displaystyle=T\left(\ln{x_{i}(t)}-\sum_{j\in
A}x_{j}(t)\ln{x_{j}(t)}\right)+T\left(C-\sum_{j\in A}x_{j}(t)C\right)$
$\displaystyle=T\left(\ln{x_{i}(t)}-\sum_{j\in A}x_{j}(t)\ln{x_{j}(t)}\right)$

since $\sum_{j\in A}x_{j}(t)=1$ and hence, the terms $C$ and $\sum_{j\in
A}x_{j}(t)C$ cancel out. Substituting the last expression in equation (A.1),
we obtain the desired solution, namely

$\dot{x}_{i}(t)=\frac{\alpha}{T}x_{i}(t)\left[r_{i}(t)-\sum_{j\in
A}x_{j}(t)r_{j}(t)-T\left(\ln{x_{i}(t)}-\sum_{j\in
A}x_{j}(t)\ln{x_{j}(t)}\right)\right].$

Rescaling time by $t\to\alpha t/T$, we obtain the solution. ∎

#### An Alternative Derivation

(see also [19, 40]). Another way to obtain the Q-learning dynamics in equation
(19) is by a direct substitution of (17) in (18). In this case, we have that

$\displaystyle x_{i}(t+1)$
$\displaystyle=\frac{\exp{\left(Q_{i}(t+1)/T\right)}}{\sum_{j\in
A}\exp{\left(Q_{j}(t+1)/T\right)}}$
$\displaystyle=\frac{\exp{\left(\left(\alpha
r_{i}(t+1)+(1-\alpha)Q_{i}(t)\right)/T\right)}}{\sum_{j\in
A}\exp{\left(\left(\alpha r_{j}(t+1)+(1-\alpha)Q_{j}(t)\right)/T\right)}}$
$\displaystyle=\frac{\exp{\left((1-\alpha)Q_{i}(t)/T\right)}\cdot\exp{\left(\alpha
r_{i}(t+1)/T\right)}}{\sum_{j\in
A}\exp{\left((1-\alpha)Q_{j}(t)/T\right)}\cdot\exp{\left(\alpha
r_{j}(t+1)/T\right)}}$
$\displaystyle=\frac{\left(\exp{\left(Q_{i}(t)/T\right)}\right)^{(1-\alpha)}\cdot\exp{\left(\alpha
r_{i}(t+1)/T\right)}}{\sum_{j\in
A}\left(\exp{\left(Q_{j}(t)/T\right)}\right)^{(1-\alpha)}\cdot\exp{\left(\alpha
r_{j}(t+1)/T\right)}}$
$\displaystyle=\frac{x_{i}(t)^{(1-\alpha)}\cdot\exp{\left(\alpha
r_{i}(t+1)/T\right)}}{\sum_{j\in A}x_{j}(t)^{(1-\alpha)}\cdot\exp{\left(\alpha
r_{j}(t+1)/T\right)}}$

where the last equality is obtained by dividing both numerator and denominator
with the normalizing constant $\sum_{k\in
A}\left(\exp{\left(Q_{k}(t)/T\right)}\right)^{(1-\alpha)}$. By taking $\ln{}$
of both sides in the previous equation, we then have that

$\ln{x_{i}(t+1)}=\ln{x_{i}(t)}-\alpha\ln{x_{i}(t)}+\frac{\alpha}{T}r_{i}(t+1)-\ln{\left(\sum_{j\in
A}x_{j}(t)^{(1-\alpha)}\cdot\exp{\left(\alpha r_{j}(t+1)/T\right)}\right)}$

or equivalently

$\displaystyle\ln{x_{i}(t+1)}-\ln{x_{i}(t)}$
$\displaystyle=\frac{\alpha}{T}r_{i}(t+1)-\alpha\ln{x_{i}(t)}-\ln{C}$

where $C:=\sum_{j\in A}x_{j}(t)^{(1-\alpha)}\cdot\exp{\left(\alpha
r_{j}(t+1)/T\right)}$ is the denominator of the previous expression which is
the same for all $i\in A$. Thus, in continuous time, the above equation
becomes

$\frac{d}{dt}\ln{x_{i}(t)}=\frac{\alpha}{T}r_{i}(t)-\alpha\ln{x_{i}(t)}-\ln{C}$

which yields

$\displaystyle\dot{x}_{i}(t)=\frac{\alpha}{T}x_{i}(t)\left[r_{i}(t)-T\ln{x_{i}(t)}-\frac{T}{\alpha}\ln{C}\right].$
($\ast\ast$)

To determine $\ln{C}$, note that $\sum_{i\in A}\dot{x}_{i}(t)=0$ since
$\sum_{i\in A}x_{i}(t)=1$ for all $t$ (i.e., the sum of the $x_{i}$’s remains
constant, and equal to 1, at all times $t\geq 0$). Thus, summing over all
$i\in A$, we obtain

$\displaystyle 0$ $\displaystyle=\sum_{i\in A}x_{i}(t)r_{i}(t)-T\sum_{i\in
A}x_{i}(t)\ln{x_{i}(t)}-\frac{T}{\alpha}\ln{C}\sum_{i\in A}x_{i}(t)$
$\displaystyle=\sum_{i\in A}x_{i}(t)r_{i}(t)-T\sum_{i\in
A}x_{i}(t)\ln{x_{i}(t)}-\frac{T}{\alpha}\ln{C}$

or equivalently

$\frac{T}{\alpha}\ln{C}=\sum_{i\in A}x_{i}(t)r_{i}(t)-T\sum_{i\in
A}x_{i}(t)\ln{x_{i}(t)}$

Substituting this expression back in equation ($\ast\ast$ ‣ A.1), we obtain

$\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\frac{\alpha}{T}x_{i}(t)\left[r_{i}(t)-T\ln{x_{i}(t)}-\sum_{j\in
A}x_{j}(t)r_{j}(t)+T\sum_{j\in A}x_{j}(t)\ln{x_{j}(t)}\right]$
$\displaystyle=\frac{\alpha}{T}x_{i}(t)\left[r_{i}(t)-\sum_{j\in
A}x_{j}(t)r_{j}(t)-T\left(\ln{x_{i}(t)}-\sum_{i\in
A}x_{j}(t)\ln{x_{j}(t)}\right)\right],$

which after rescaling time to $t\to\alpha t/T$ is precisely the expression of
the Q-learning dynamics in equation (19).

#### Relation to Experience Weighted Attraction (EWA) Learning

(see also [40]). In Experience Weighted Learning (EWA), the _attractions_ (the
equivalent of Q-values), $Q_{i}(t)$ of each action $i\in A$ are updated
according to the following scheme

$\displaystyle Q_{i}(t+1)$
$\displaystyle=\frac{(1-\alpha)N(t)Q_{i}(t)+[\delta+(1-\delta)I(i,s_{i}(t))]r_{i}(t)}{N(t+1)},$
$\displaystyle N(t+1)$ $\displaystyle=\rho N(t)+1,$

where $I(i,s(t))=1$ if $i=s(t)$ and $0$ otherwise. Here $s(t)$ denotes the
action taken by the agent at time $t$. The variables $N(t)$ and $Q_{i}(t)$ are
initialized arbitrarily at $t=0$, but typically, they are set to be $0$ at
$t=0$. For $\rho=0$, i.e., in the case in which previous experience does not
reduce the impact of current rewards, the above system becomes

$\displaystyle Q_{i}(t+1)$
$\displaystyle=(1-\alpha)Q_{i}(t)+\begin{cases}\phantom{\delta}r_{i}(t),&\text{if
}s(t)=i,\\\ \delta r_{i}(t),&\text{otherwise}\end{cases}$

Thus, for $\delta=1$, the EWA update rule becomes equal to the Q-learning
updates, up to a constant $\alpha$ in the rewards.

###  A.2 Q-learning and Quantal Response Equilibria

We next restate and prove Theorem 3.2.

Theorem 3.2. Let $\Gamma$ be an arbitrary game, with positive exploration
rates $T_{k}$ and consider the associated Q-learning dynamics

$\dot{x}_{ki}=x_{ki}\left[r_{ki}(\mathbf{x}_{-k})-\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)-T_{k}\left(\ln{(x_{ki})}-\mathbf{x}_{k}^{\top}\ln{(\mathbf{x}_{k})}\right)\right],\;\;i\in
S_{k},k\in V.$

The interior fixed points, $\mathbf{p}=(p_{k})_{k\in V}$ of the Q-learning
dynamics are the solutions of the system

$p_{ki}=\frac{\exp{\left(r_{ki}(\mathbf{p}_{-k})/T_{k}\right)}}{\sum_{j\in
S_{k}}\exp{\left(r_{kj}(\mathbf{p}_{-k})/T_{k}\right)}},\quad\text{for all
}i\in S_{k}.$ (20)

Such fixed points always exists and coincide with the Quantal Response
Equilibria (QRE) of $\Gamma$. Given any such fixed point $\mathbf{p}$, we
have, for all $\mathbf{x}_{k}\in\Delta_{k}$ and for all $k\in V$, that

$(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}(\mathbf{p}_{-k})-T_{k}\ln{(\mathbf{p}_{k})}\right]=0.$
(21)

###### Proof.

Solving equation (9) for $\ln{q_{ki}}$ and applying the exponential function
on both sides of the resulting equation yields that

$\displaystyle p_{ki}$
$\displaystyle=\exp{\left(\frac{r_{ki}(\mathbf{p}_{-k})-\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+T_{k}\mathbf{p}_{k}^{\top}\ln{(\mathbf{p}_{k})}}{T_{k}}\right)}$
$\displaystyle=\exp{\left(\frac{r_{ki}(\mathbf{p}_{-k})}{T_{k}}\right)}\cdot\exp{\left(\frac{-\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+T_{k}\mathbf{p}_{k}^{\top}\ln{(\mathbf{p}_{k})}}{T_{k}}\right)}.$

The second term in the last equation, i.e.,
$\exp{\left(\frac{-\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+T_{k}\mathbf{p}_{k}^{\top}\ln{(\mathbf{p}_{k})}}{T_{k}}\right)}$,
is the same (constant) for all $i\in S_{k}$. Thus, denoting this term by $Z$,
we have that

$p_{ki}=\exp{\left(\frac{r_{ki}(\mathbf{p}_{-k})}{T_{k}}\right)}\cdot
Z,\quad\text{for all}i\in S_{k}.$

Since $\mathbf{p}_{k}$ lies in $\Delta_{k}$, it must be the case that
$\sum_{j\in S_{k}}p_{ki}=1$, which implies that

$\sum_{i\in S_{k}}p_{ki}=\sum_{i\in
S_{k}}\exp{\left(\frac{r_{ki}(\mathbf{p}_{-k})}{T_{k}}\right)}\cdot
Z=1\implies Z=\left(\sum_{i\in
S_{k}}\exp{\left(\frac{r_{ki}(\mathbf{p}_{-k})}{T_{k}}\right)}\right)^{-1}.$

Substituting back in the expression for $p_{ki}$, we obtain that

$p_{ki}=\frac{\exp{\left(r_{ki}(\mathbf{p}_{-k})/T_{k}\right)}}{\sum_{j\in
S_{k}}\exp{\left(r_{kj}(\mathbf{p}_{-k})T_{k}\right)}},$

as claimed in equation (20). Existence follows from the application of
Brouwer’s fixed point theorem on the continuous map defined by the previous in
$\Delta_{k}$, see [34]. To obtain equation (21), we observe that for each
$x_{k}\in\Delta_{k}$ and each $k\in V$, equation (9) implies that

$\mathbf{x}_{k}^{\top}r_{k}(\mathbf{p}_{-k})=\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)-T_{k}(\mathbf{p}_{k}-\mathbf{x}_{k})^{\top}\ln{(\mathbf{p}_{k})},\;\;\text{for
all }k\in V.$

or equivalently that

$(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}(\mathbf{p}_{-k})-T_{k}\ln{(\mathbf{p}_{k})}\right]=0,$

for all $k\in V$ as claimed in equation (21). ∎

##  Appendix B Omitted Proofs and Materials: Section 4

In this section, we develop the necessary technical framework for the proof of
Theorem 4.1. Theorem 4.1 is based upon two critical lemmas and properties of
both KL divergence and rescaled zero-sum polymatrix games.

First, recall that in KL-divergence is not symmetric, i.e., it need not hold
that
$D_{\text{KL}}(\mathbf{p}\parallel\mathbf{x}(t))=D_{\text{KL}}(\mathbf{x}(t)\parallel\mathbf{p})$.
However, KL-divergence does obey the following property.

######  Property 1.

Let $k\in V$ and let $\mathbf{p}_{k},\mathbf{x}_{k}$ be interior points of
$\Delta_{k}$. Then, it holds that

$D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})=(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[\ln{(\mathbf{x}_{k})}-\ln{(\mathbf{p}_{k})}\right].$

###### Proof.

It is immediate to check that

$\displaystyle(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[\ln{(\mathbf{x}_{k})}-\ln{(\mathbf{p}_{k})}\right]$
$\displaystyle=\mathbf{x}_{k}^{\top}\ln{\left(\frac{\mathbf{x}_{k}}{\mathbf{p}_{k}}\right)}-\mathbf{p}_{k}^{\top}\ln{\left(\frac{\mathbf{x}_{k}}{\mathbf{p}_{k}}\right)}$
$\displaystyle=\mathbf{x}_{k}^{\top}\ln{\left(\frac{\mathbf{x}_{k}}{\mathbf{p}_{k}}\right)}+\mathbf{p}_{k}^{\top}\ln{\left(\frac{\mathbf{p}_{k}}{\mathbf{x}_{k}}\right)}$
$\displaystyle=D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})+D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k}),$

as claimed. ∎

Lemma 4.2. Let $k\in V$. The time-derivative of the $D_{\text{KL}}$-divergence
between the $k$-th component, $\mathbf{p}_{k}\in\Delta_{k}$, of a QRE
$\mathbf{p}\in\Delta$ of $\Gamma$, and the $k$-th component,
$\mathbf{x}_{k}(t)\in\Delta_{k}$ of a system trajectory with $\mathbf{x}(0)$
an interior point, is given by

$\frac{d}{dt}D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k}(t))=(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]-T_{k}\left[D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right].$
(22)

###### Proof.

The time derivative of the term
$D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})$ for $k\in V$ can be
calculated as follows (note that after the first line, we omit the dependence
of $\mathbf{x}$ on $t$ to simplify notation)

$\displaystyle\frac{d}{dt}D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k}(t))$
$\displaystyle=-\sum_{i\in
S_{k}}p_{ki}\frac{d}{dt}(\ln{(x_{ki}(t))})=-\sum_{i\in
S_{k}}p_{ki}\frac{\dot{x}_{ki}(t)}{x_{ki}(t)}$ $\displaystyle=-\sum_{i\in
S_{k}}p_{ki}\left[r_{ki}(\mathbf{x}_{-k})-\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)+T_{k}\left(-\ln{(x_{ki})}+\mathbf{x}_{k}^{\top}\ln{(\mathbf{x}_{k})}\right)\right]$
$\displaystyle=-\left[\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)-\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)+T_{k}\left(-\mathbf{p}_{k}^{\top}\ln{(\mathbf{x}_{k})}+\mathbf{x}_{k}^{\top}\ln{(\mathbf{x}_{k})}\right)\right]$
$\displaystyle=\phantom{-\,}(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}r_{k}\left(\mathbf{x}_{-k}\right)-T_{k}(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\ln{(\mathbf{x}_{k})}$
$\displaystyle=\phantom{-\,}(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-T_{k}\ln{(\mathbf{x}_{k})}\right].$

Using equation (21), i.e., that

$(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}(\mathbf{p}_{-k})-T_{k}\ln{(\mathbf{p}_{k})}\right]=0,$

we can write the time derivative of $D_{\text{KL}}$ as follows

$\displaystyle\frac{d}{dt}D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k}(t))$
$\displaystyle=(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-T_{k}\ln{(\mathbf{x}_{k})}\right]-(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}(\mathbf{p}_{-k})-T_{k}\ln{(\mathbf{p}_{k})}\right]$
$\displaystyle=(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]-T_{k}(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[\ln{\mathbf{x}_{k}}-\ln{\mathbf{p}_{k}}\right]$
$\displaystyle=(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]-T_{k}\left[D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right]$

where the last equation holds due to Property 1. This concludes the proof of
the Lemma. ∎

Lemma 4.3. Let $\mathbf{p}=(\mathbf{p}_{k})_{k\in V}$ be a QRE of $\Gamma$ and
let $\mathbf{x}=(\mathbf{x}_{k})_{k\in V}$. Then, it holds that

$\sum_{k\in
V}w_{k}\left[\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)\right]=0.$
(23)

Before proceeding with the proof of Lemma 4.3, note that if there only two
players, i.e., if $V=\\{1,2\\}$, then
$\mathbf{p}=(\mathbf{p}_{1},\mathbf{p}_{2})$ and
$\mathbf{x}=(\mathbf{x}_{1},\mathbf{x}_{2})$, and it is rather immediate to
check the validity equation (23), since

$\displaystyle\sum_{k=1,2}w_{k}[\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)$
$\displaystyle+\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)]=$
$\displaystyle=w_{1}\left[\mathbf{x}_{1}^{\top}r_{1}(\mathbf{p}_{2})+\mathbf{p}_{1}^{\top}r_{1}(\mathbf{x}_{2})\right]+w_{2}\left[\mathbf{x}_{2}^{\top}r_{2}(\mathbf{p}_{1})+w_{2}\mathbf{p}_{2}^{\top}r_{2}(\mathbf{x}_{1})\right]$
$\displaystyle=\left[w_{1}\mathbf{x}_{1}^{\top}r_{1}(\mathbf{p}_{2})+w_{2}\mathbf{p}_{2}^{\top}r_{2}(\mathbf{x}_{1})\right]+\left[w_{2}\mathbf{x}_{2}^{\top}r_{2}(\mathbf{p}_{1})+w_{2}\mathbf{p}_{1}^{\top}r_{1}(\mathbf{x}_{2})\right]$
$\displaystyle=\underbrace{\sum_{k=1,2}w_{k}u_{k}(\mathbf{x}_{1},\mathbf{p}_{2})}_{=\,0\text{
by equation
\eqref{eq:zsprop}}}+\underbrace{\sum_{k=1,2}w_{k}u_{k}(\mathbf{p}_{1},\mathbf{x}_{2})}_{=\,0\text{
by equation \eqref{eq:zsprop}}}=0.$

In particular, the last equation holds because the summations are over all
payoffs in the strategy profiles $(\mathbf{x}_{1},\mathbf{p}_{2})$ and
$(\mathbf{p}_{1},\mathbf{x}_{2})$. When we have more than two players, this
argument does not hold, since the summation is over different strategy
profiles. However, it still holds that the summation is equal to zero. To show
this, we will need to apply the following property that has been established
in [12] for zero-sum polymatrix games to the case of weighted zero-sum
polymatrix games (the extension is rather straightforward as we show below).
To state the property in the general case, we will use the following
definition.

######  Definition 2 ($w_{k}$-Payoff equivalence).

Consider two arbitrary games $\Gamma=\left((V,E),(S_{k},u_{k})_{k\in
V}\right)$ and $\Gamma^{\prime}=\left((V,E),(S_{k},u_{k}^{\prime})_{k\in
V}\right)$. We will say that $\Gamma$ is $w_{k}$-payoff equivalent to
$\Gamma^{\prime}$ if there exist positive constants $w_{k},k\in V$ so that

$u_{k}(\mathbf{x})=w_{k}u_{k}^{\prime}(\mathbf{x}),\;\;\text{for all
}x\in\Delta.$

######  Property 2 (Payoff equivalent transformation [12].).

Let $\Gamma=\left((V,E),\left(S_{k},w_{k}\right)_{k\in
V},\left(\mathbf{A}_{kl}\right)_{[k,l]\in E}\right)$ be a rescaled zero-sum
polymatrix game. Then, $\Gamma$ is $1/w_{k}$-payoff equivalent to a pairwise
constant-sum (unweighted) polymatrix game
$\hat{\Gamma}=\left((V,E),\left(S_{k}\right)_{k\in
V},\left(\hat{\mathbf{A}}_{kl}\right)_{[k,l]\in E}\right)$, i.e., a game in
which every two-player game $[k,l]\in E$ is constant-sum and all these
constants sum up to zero. Specifically, for all $k,l\in V$ with $[k,l]\in E$,
there exist payoff matrices
$\hat{\mathbf{A}}_{kl}=\left(\hat{a}_{kl}(s_{k},s_{l})\right)_{\\{s_{k}\in
S_{k},s_{l}\in S_{l}\\}}$ and constants $c_{kl}\in\mathbb{R}$, so that

$\displaystyle\hat{a}_{kl}(s_{k},s_{l})+\hat{a}_{lk}(s_{l},s_{k})$
$\displaystyle=c_{kl},\;\;\text{for all }s_{k}\in S_{k},s_{l}\in S_{l},$ (24)

with

$\sum_{[k,l]\in E}c_{kl}=0,$ (25)

and

$\hat{r}_{ki}(\mathbf{x}_{-k}):=\sum_{[k,l]\in
E}\\{\hat{\mathbf{A}}_{kl}\mathbf{x}_{l}\\}_{i}=\sum_{[k,l]\in
E}w_{k}\\{\mathbf{A}_{kl}\mathbf{x}_{l}\\}_{i}=w_{k}r_{ki}(\mathbf{x}_{-k}),$
(26)

for all $k\in V$ and all $i\in S_{k}$, i.e., for every pure (and hence, also
for every mixed) strategy profile, the payoff of each player $k\in V$ in
$\hat{\Gamma}$ is equal to $1/w_{k}$ their payoff in the original game
$\Gamma$.

###### Proof.

As mentioned above, all claims of Property 2 have been established for
(unweighted) zero-sum polymatrix games in [12]. Thus, it remains to show that
the proof extends to the weighted case. To see this, consider a weighted zero-
sum polymatrix game $\Gamma$ with weights $\mathbf{w}=(w_{k})_{k\in V}$,
payoff matrices $\left(\mathbf{A}_{kl}\right)_{[k,l]\in E}$ and utilities
$u_{k},k\in V$ as in equation (1) and define the transformed game
$\Gamma^{\mathbf{B}}$ with payoff matrices
$\left(\mathbf{B}_{kl}\right)_{[k,l]\in E}$ given by

$\mathbf{B}_{kl}:=w_{k}\mathbf{A}_{kl},\quad\text{for all }k\in V,[k,l]\in E,$

and utilities $u_{k}^{\mathbf{B}},k\in V$. Then, it follows from equation (1)
that $u_{k}(\mathbf{x})=\frac{1}{w_{k}}u_{k}^{\mathbf{B}}(\mathbf{x})$ for all
$\mathbf{x}\in\Delta$ and $k\in V$ since

$u_{k}^{\mathbf{B}}(\mathbf{x})=\sum_{[k,l]\in
E}\mathbf{x}_{k}^{\top}\mathbf{B}_{kl}\mathbf{x}_{l}=\sum_{[k,l]\in
E}\mathbf{x}_{k}^{\top}\left(w_{k}\mathbf{A}_{kl}\right)\mathbf{x}_{l}=w_{k}\sum_{[k,l]\in
E}\mathbf{x}_{k}^{\top}\mathbf{A}_{kl}\mathbf{x}_{l}=w_{k}u_{k}(\mathbf{x}).$

Moreover, $\Gamma^{\mathbf{B}}$ is an _unweighted_ zero-sum game since

$\sum_{k\in V}u_{k}^{\mathbf{B}}(\mathbf{x})=\sum_{k\in
V}w_{k}u_{k}(\mathbf{x})=0,$

where the last equality follows from the fact that $\Gamma$ is a weighted
zero-sum polymatrix game with weights $(w_{k})_{k\in V}$. Thus, transforming
$\Gamma$ to $\Gamma^{\mathbf{B}}$ and then applying the transformation of [12]
on $\Gamma^{\mathbf{B}}$ to obtain the payoff equivalent (to
$\Gamma^{\mathbf{B}}$) game $\hat{\Gamma}$ with payoff matrices
$\hat{\mathbf{A}}_{kl},[k,l]\in E$ yields the result, i.e., the
$1/w_{k}$-payoff equivalence between the original weighted zero-sum polymatrix
game $\Gamma$ and the pairwise constant-sum, unweighted polymatrix game
$\hat{\Gamma}$. ∎

Using Property 2, we can now prove Lemma 4.3 for general $k\geq 2$.

###### Proof of Lemma 4.3.

Equation (26) in Property 2 implies that

$\displaystyle\sum_{k\in
V}w_{k}\left[\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)\right]$
$\displaystyle\overset{\eqref{eq:appendix:trans2}}{=}\sum_{k\in
V}w_{k}\left[\mathbf{x}_{k}^{\top}\left(\frac{1}{w_{k}}\hat{r}_{k}(\mathbf{x}_{-p})\right)+\mathbf{p}_{k}^{\top}\left(\frac{1}{w_{k}}\hat{r}_{k}(\mathbf{x}_{-k})\right)\right]$
$\displaystyle\overset{\phantom{(18)}}{=}$ $\displaystyle\sum_{k\in
V}\sum_{[k,l]\in
E}\left[\mathbf{x}_{k}^{\top}\hat{\mathbf{A}}_{kl}\mathbf{p}_{l}+\mathbf{p}_{k}^{\top}\hat{\mathbf{A}}_{kl}\mathbf{x}_{l}\right]$
$\displaystyle\overset{\phantom{(18)}}{=}$ $\displaystyle\sum_{[k,l]\in
E}\left[\mathbf{x}_{k}^{\top}\hat{\mathbf{A}}_{kl}\mathbf{p}_{l}+\mathbf{p}_{k}^{\top}\hat{\mathbf{A}}_{kl}\mathbf{x}_{l}+\mathbf{x}_{l}^{\top}\hat{\mathbf{A}}_{lk}\mathbf{p}_{k}+\mathbf{p}_{l}^{\top}\hat{\mathbf{A}}_{kl}\mathbf{x}_{k}\right]$
$\displaystyle\overset{\phantom{(18)}}{=}$ $\displaystyle\sum_{[k,l]\in
E}\underbrace{\left[\mathbf{x}_{k}^{\top}\hat{\mathbf{A}}_{kl}\mathbf{p}_{l}+\mathbf{p}_{l}^{\top}\hat{\mathbf{A}}_{kl}\mathbf{x}_{k}\right]}_{=\,c_{kl}\text{
by equation
\eqref{eq:appendix:trans1}}}+\underbrace{\left[\mathbf{x}_{l}^{\top}\hat{\mathbf{A}}_{lk}\mathbf{p}_{k}+\mathbf{p}_{k}^{\top}\hat{\mathbf{A}}_{kl}\mathbf{x}_{l}\right]}_{=\,c_{kl}\text{
by equation \eqref{eq:appendix:trans1}}}$
$\displaystyle\overset{\phantom{(18)}}{=}$ $\displaystyle 2\sum_{[k,l]\in
E}c_{kl}=0,$

where the last equality holds by equation (25). ∎

###  B.1 Proof of Theorem 4.1

Combining Lemmas 4.2 and 4.3, we can now restate and prove Theorem 4.1.

Theorem 4.1. Let $\Gamma$ be a rescaled zero-sum polymatrix game, with
positive exploration rates $T_{k}$. There exists a unique QRE $\mathbf{p}$
such that if $\mathbf{x}(t)$ is any trajectory of the associated Q-learning
dynamics $\dot{\mathbf{x}}=f(\mathbf{x})$, with $f_{i}$ is given via (7),
where $\mathbf{x}(0)$ is an interior point, then $\mathbf{x}(t)$ converges to
$\mathbf{p}$ exponentially fast. In particular, we have that

$\frac{d}{dt}D_{\text{KL}(w)}(\mathbf{p}\parallel\mathbf{x}(t))=-\sum\nolimits_{k\in
V}w_{k}T_{k}\left[D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right].$
(27)

###### Proof.

Theorem 3.2 states that there must exist some a QRE equilibrium
$\mathbf{p}=(\mathbf{p}_{k})$. We first establish (27), from which the
remaining statements will follow. The time derivative of the KL-divergence
between $\mathbf{p}$ and $\mathbf{x}(t)$ is given by (as in the proof of Lemma
4.2, we again omit the dependence of $\mathbf{x}$ on $t$ after the first line
to simplify notation)

$\displaystyle\frac{d}{dt}$ $\displaystyle
D_{\text{KL}}(\mathbf{p}\parallel\mathbf{x}(t))=~{}\sum_{k\in
V}\frac{d}{dt}w_{k}D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})$
$\displaystyle=~{}\sum_{k\in
V}w_{k}\left[(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]-T_{k}\left(D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right)\right]$
$\displaystyle=~{}\sum_{k\in
V}w_{k}(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]-\sum_{k\in
V}w_{k}T_{k}\left[D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right].$

The first term in the right hand side of the last equation is equal to zero,
since

$\displaystyle\sum_{k\in
V}w_{k}(\mathbf{x}_{k}-\mathbf{p}_{k})^{\top}\left[r_{k}\left(\mathbf{x}_{-k}\right)-r_{k}(\mathbf{p}_{-k})\right]$
$\displaystyle~{}=~{}\sum_{k\in
V}w_{k}\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)+\sum_{k\in
V}w_{k}\mathbf{p}_{k}^{\top}r_{k}(\mathbf{p}_{-k})$
$\displaystyle~{}~{}+\sum_{k\in
V}w_{k}\left[\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)\right]=0,$

where in the last equality, we used the zero-sum property (cf. equation (2))
to conclude that the terms $\sum_{k\in
V}w_{k}\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)$ and $\sum_{k\in
V}w_{k}\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)$ are equal to
$0$ and equation (23) in Lemma 4.3 to conclude that the term $\sum_{k\in
V}w_{k}\left[\mathbf{x}_{k}^{\top}r_{k}\left(\mathbf{p}_{-k}\right)+\mathbf{p}_{k}^{\top}r_{k}\left(\mathbf{x}_{-k}\right)\right]$
is also equal to $0$. Thus,

$\displaystyle\frac{d}{dt}D_{\text{KL}}(\mathbf{p}\parallel\mathbf{x}(t))=-\sum_{k\in
V}w_{k}T_{k}\left[D_{\text{KL}}(\mathbf{p}_{k}\parallel\mathbf{x}_{k})+D_{\text{KL}}(\mathbf{x}_{k}\parallel\mathbf{p}_{k})\right],$
(28)

which implies that
$\frac{d}{dt}D_{\text{KL}}(\mathbf{p}\parallel\mathbf{x})<0$ for all
$\mathbf{x}\neq\mathbf{p}$ as $T_{k}>0$ for each $k$. In other words,
$\Phi(\mathbf{x}):=D_{\text{KL}}(\mathbf{p}\parallel\mathbf{x})$ obeys the
properties i) $\Phi(\mathbf{p})=0$, ii) $\Phi(\mathbf{x})>0$ if
$\mathbf{x}\neq\mathbf{p}$ and iii) $\dot{\Phi}(\mathbf{x})<0$ for
$\mathbf{x}\neq\mathbf{p}$, i.e., $\Phi$ is a Lyapunov function for the
Q-learning dynamics (7). In particular, since
$D_{\text{KL}}\left(\mathbf{x}_{k}\parallel\mathbf{p}_{k}\right)>0$ as long as
the distributions $\mathbf{p}_{k},\mathbf{x}_{k}$ are not equal, then

$\dot{\Phi}(x)\leq-\min_{k}T_{k}\cdot\Phi(x),$ (29)

thus the KL-divergence converges to zero exponentially fast. As any QRE
$\mathbf{p}^{\prime}\neq\mathbf{p}$ must also satisfy
$\dot{\Phi}(\mathbf{p}^{\prime})=\nabla\Phi\cdot f(\mathbf{p}^{\prime})=0$ (as
$\mathbf{p}^{\prime}$ is a fixed point for $\dot{\mathbf{x}}=f(\mathbf{x})$,
where $f$ is given in (7)), but we have that $\dot{\Phi}(\mathbf{x})<0$ for
all $\mathbf{x}\neq\mathbf{p}$, it follows that $\mathbf{p}$ is unique. ∎

##  Appendix C Additional Experiments

In the section, we present additional simulations and calculations that
complement our experimental results in Section 5 in the main paper.

###  C.1 Q-learning dynamics in the AMPs game

We start with Figure 6 which completes the possible combinations of the two
representative policies that we consider, CLR-1 and ETE, in the AMPs game (cf.
Section 5). The plots are similar to that in Figure 1.

Figure 6: QRE surface and exploration paths (upper panels) for two different
exploration policy profiles (lower panels) in the Asymmetric MPs game. As in
Figure 1 in the main part, the sequence of play converges to the unique QRE
for any combination of exploration policies (CLR-1 and ETE). As the
exploration rates decrease zero, the sequence of play converges to the unique
Nash equilibrium of the game.

###  C.2 Q-learning dynamics in two-player games with more actions

We next turn to visualizations of the Q-learning in games with two-players but
more than two actions for each player. For this purpose, we consider the
(symmetric) zero-sum game, Rock-Paper-Scissors (RPS) with payoff matrices
given by

$\mathbf{A}=\begin{pmatrix}\phantom{-}0&-1&\phantom{-}1\\\
\phantom{-}1&\phantom{-}0&-1\\\
-1&\phantom{-}1&\phantom{-}0\end{pmatrix},\quad\mathbf{B}=-\mathbf{A}^{\top}.$

The RPS game has a unique (interior) Nash equilibrium given by
$(p^{*},q^{*})=((1/3,1/3,1/3)$, $(1/3,1/3,1/3))$. This is also the unique QRE
for any positive exploration rates (since exploration favors the uniform
distribution). In Figure 7, we visualize the Q-learning dynamics (cf. equation
(7)) for $T_{x}=0$ and various values of $T_{y}$. The setup and the plots are
similar to that of Figure 2.

Figure 7: Q-learning dynamics in Rock-Paper-Scissors for $T_{x}=0$ (no
exploration by $x$-agent) and six different exploration rates, $T_{y}\geq 0$
by $y$-agent. The light to dark trajectories (with darkening color indicating
increasing time) show the choice distribution for the $x$-agent in the Rock-
Paper space.

The trajectories in Figure 7 have been generated for random initial conditions
(similar plots are obtained for any other initial condition) and show the
choice distribution of the $x$-agent at each time point of the simulation (we
used $2\times 10^{7}$ iterations with a step $0.0003$ for the discretization
of the continuous time ODE in equation (7)). We obtain similar plots for the
exploring agent ($y$-agent), see Figure 8. When $T_{y}=0$, the Q-learning
dynamics reduce to the replicator dynamics and we recover their cyclic
behavior (Poincaré Recurrence) around the unique interior Nash equilibrium
(upper left panel) (see [41] and references therein). In all other cases,
exploration by one agent suffices for the convergence of the joint-learning
dynamics as in the AMPs game (in panels 2 and 3, the dynamics spiral inwards
and will eventually converge to the QRE (blue dot)). As we saw in Section 5
this is in sharp contrast to the (ZSPG) game in which exploration (even) by
several agents was not sufficient for the convergence of Q-learning to a
single QRE. It is worth mentioning that this behavior of the Q-learning
dynamics in RPS does not rely on the symmetry of the game. We obtain similar
plots for the a modified RPS game (with asymmetric Nash equilibrium) (not
depicted here).

Figure 8: Q-learning trajectories for the $y$-agent in the instances of the
RPS game that are shown in Figure 7.

###  C.3 Edge Case: Exploration by one player in $2x2$ games

Up to now, we have treated the case of exploration by only agent
experimentally (cf. Figures 2, 7 and 8). In this part, we consider the edge-
case in which only one of two players is exploring in $2x2$ games which is
also analytically tractable. Our result is presented in Proposition C.1 and
the ensuing intuition is summarized in Remark 2. For the following (technical)
calculations, we will use the notation

$\mathbf{A}=\begin{pmatrix}a_{11}&a_{12}\\\
a_{21}&a_{22}\end{pmatrix},\quad\mathbf{B}=\begin{pmatrix}b_{11}&b_{12}\\\
b_{21}&b_{22}\end{pmatrix}.$

We assume that the game has a (unique) interior Nash equilibrium. This implies
(without loss of generality, see e.g., [40]) that

$a_{11}>a_{21},\;a_{12}<a_{22},\;\;\text{ and
}\;\;b_{11}<b_{21},\;b_{12}>b_{22}.$ (30)

By letting $a_{1}:=a_{12}-a_{22}$ and $a_{2}:=a_{12}+a_{21}-a_{11}-a_{22}$
with $a_{1},a_{2}<0$ and $b_{1}:=b_{12}-b_{22}$ and
$b_{2}:=b_{12}+b_{21}-b_{11}-b_{22}$ with $b_{1},b_{2}>0$, we have that the
unique Nash equilibrium, $(\mathbf{p},\mathbf{q})$, with
$\mathbf{p}=(p,1-p),\mathbf{q}=(q,1-q)$ of this game is given by
$q=\frac{a_{1}}{a_{2}}$ and $p=\frac{b_{1}}{b_{2}}$ with $p,q\in(0,1)$ by
assumption.

Since players have two strategies, we can represent their mixed strategies by
the vectors $\mathbf{x}=(x,1-x)$ and $\mathbf{y}=(y,1-y)$ with $x,y\in[0,1]$.
Using this notation and under the assumption that $T_{x}=0$, i.e., that the
$x$ player is not exploring, the dynamics for the $x$ player in equation (7)
take the form

$\displaystyle\dot{x}$
$\displaystyle=x\left[(1,\;0)\mathbf{A}\dbinom{y}{1-y}-(x,\;1-x)\mathbf{A}\dbinom{y}{1-y}\right]=x(1-x)\left[a_{1}-a_{2}y\right]$
by assumption (30). Similarly, the dynamics for the $y$ player in equation (7)
take the form $\displaystyle\dot{y}$
$\displaystyle=y\left[(1,\;0)\mathbf{B}\dbinom{x}{1-x}-(y,\;1-y)\mathbf{B}\dbinom{x}{1-x}+T_{y}(y\ln{y}+(1-y)\ln{1-y}-\ln{y})\right]$
$\displaystyle=y(1-y)\left[b_{1}-b_{2}x+T_{y}\ln{\left(\frac{1}{y}-1\right)}\right]$

where we defined $b_{1}:=b_{12}-b_{22}$ and
$b_{2}:=b_{12}+b_{21}-b_{11}-b_{22}$ with $b_{1},b_{2}>0$ by assumption (30).
For the $y$ player, we will consider various values for $T_{y}\geq 0$. Putting
these together, we obtain the system

$\displaystyle\dot{x}$ $\displaystyle=x(1-x)\left[a_{1}-a_{2}y\right]$
$\displaystyle\dot{y}$
$\displaystyle=y(1-y)\left[b_{1}-b_{2}x+T_{y}\ln{\left(\frac{1}{y}-1\right)}\right]$
(31)

with $x,y\in[0,1]$ and $T_{y}\geq 0$. It is immediate that all four points
$(x,y)\in\\{0,1\\}\times\\{0,1\\}$ are resting point of the system. All these
points lie on the boundary. For the system to have an interior resting point,
we have the conditions

$y=\frac{a_{1}}{a_{2}},\quad\text{ and }\quad
x=\frac{1}{b_{2}}\left[b_{1}+T_{y}\ln{\left(\frac{a_{2}}{a_{1}}-1\right)}\right].$
(32)

The condition for $y$ is always satisfied by assumption (30). In particular,
this yields the Nash equilibrium strategy for the $y$ player. However, the
condition for $x$ may yield an $x$ that does not lie within $(0,1)$. For
$T_{y}=0$, the condition becomes $x=b_{1}/b_{2}$ which is the Nash equilibrium
strategy for the $x$ player. By assumption, this is strictly between $0$ and
$1$. However, $x$ depends linearly on $T_{y}$ and depending on whether
$a_{2}/a_{1}>2$ or $a_{2}/a_{1}<2$ it either increases or decreases in
$T_{y}$.222The case $a_{2}=2a_{1}$ is trivial since it implies that $y=1/2$
and $x=b_{1}/b_{2}$ regardless of $T_{y}$. Thus, there exists a critical
threshold, $T_{y}^{*}$, for which $x$ hits the boundary of $[0,1]$, i.e., it
either becomes $0$ or $1$. Assume that $x=1$ without loss of generality. At
that point, the upper equation in (C.3) is satisfied regardless of whether
$y=a_{1}/a_{2}$. Thus, we turn to the lower equation in (C.3) to obtain a
condition for $y$, which yields

$b_{1}-b_{2}\cdot 1+T_{y}\ln{\left(\frac{1}{y}-1\right)}=0\iff
y=\left[1+\exp{\left((b_{2}-b_{1})/T_{y}\right)}\right]^{-1}.$

Note, that in all the above cases, if an interior resting point exists (for
either or both players), then it is unique. We summarize our findings for the
$2\times 2$ case in Proposition C.1.

######  Proposition C.1.

Let $\Gamma=(\\{1,2\\},\mathbf{A},\mathbf{B})$ with
$\mathbf{A},\mathbf{B}\in\mathbb{R}^{2\times 2}$ be a two-player, two-strategy
($2\times 2$) game with $a_{2}>2a_{1}$ and a unique interior Nash equilibrium,
i.e., such that condition (30) holds, and let

$T_{y}^{\text{crit}}:=(b_{2}-b_{1})\cdot\left[\ln{\left(\frac{a_{2}}{a_{1}}-1\right)}\right]^{-1}.$

If $T_{x}=0$, then for any interior starting point $(x_{0},y_{0})\in(0,1)$,
the fixed points $(\mathbf{p},\mathbf{q})=((p,1-p),(q,1-q))$ with
$p,q\in[0,1]$ of the Q-learning dynamics

$\displaystyle\dot{x}$ $\displaystyle=x(1-x)\left[a_{1}-a_{2}y\right]$
$\displaystyle\dot{y}$
$\displaystyle=y(1-y)\left[b_{1}-b_{2}x+T_{y}\ln{\left(\frac{1}{y}-1\right)}\right]$

depend on $T_{y}$ as follows:

  * •

if $T_{y}=0$, then the dynamics are cyclic, i.e., they do not have a resting
point.

  * •

if $0<T_{y}<T_{y}^{\text{crit}}$, then they have a unique interior resting
point which is given by

$(p,q)=\left(\frac{1}{b_{2}}\left[b_{1}+T_{y}\ln{\left(\frac{a_{2}}{a_{1}}-1\right)}\right],\;\frac{a_{1}}{a_{2}}\right)\;\;\text{
with }p,q\in(0,1).$

  * •

otherwise, i.e., if $T_{y}>T_{y}^{\text{crit}}$, then they have a resting
point that lies in the interior only for the exploring player which is given
by

$(p,q)=\left(1,\;\left[1+\exp{\left((b_{2}-b_{1})/T_{y}\right)}\right]^{-1}\right),\;\;\text{
with }q\in(0,1).$

In particular, as $T_{y}\to\infty$, it holds that $q\to 1/2$.

If $a_{2}<2a_{1}$, then $x$ is decreasing in $T_{y}$ and hence, at
$T_{y}^{crit}$ it becomes $0$ (rather than $1$). In this case, solving
equation (32) for $T_{y}^{\text{crit}}$ yields
$T_{y}^{\text{crit}}=-b_{1}\cdot\left[\ln{\left(\frac{a_{2}}{a_{1}}-1\right)}\right]^{-1}$.
By renaming the strategies of the $x$ player, this case is equivalent to the
one presented in Proposition C.1. The general case of more than $2$ strategies
for each player is qualitatively equivalent to the case presented here.

######  Remark 2 (Intuition of Proposition C.1).

The main takeaway of Proposition C.1 is the qualitative description of the
resting points of the Q-learning dynamics for any interior starting point.
When $T_{y}=0$, the dynamics are the replicator dynamics, which are well-known
to cycle around the unique interior Nash equilibrium in this case [7]. If
$T_{y}>0$, then this suffices to ensure convergence to the unique interior QRE
(cf. Theorem 4.1). As long as $T_{y}$ is small enough, i.e., smaller than a
critical value, $T_{y}^{\text{crit}}$, the $y$ component of the QRE
corresponds precisely to the Nash equilibrium (mixed) strategy for the
$y$-player (the exploring player) and an interior value for the $x$-player
(different that her Nash equilibrium mixture). This value is increasing
(assuming that $a_{2}>2a_{1}$, otherwise it is decreasing or constant if
$a_{2}=2a_{1}$) in the exploration rate $T_{y}$ of the $y$-player. This
implies, that the QRE component for the $x$-player approaches the boundary.
After exploration by the $y$-player exceeds the critical threshold
$T_{y}^{\text{crit}}$, the $x$-player starts playing a pure strategy. At that
point onward (i.e., for larger exploration rates), the utility of the $y$
player is dominated by her exploration term and her mixture (at QRE) starts to
approach the uniform distribution.

The result of Proposition C.1 is illustrated in the main part of the paper via
Asymmetric Matching Pennies (AMPs) game in Figure 2.

###  C.4 3D Visualization of the Lyapunov function in $n$-agent network games

To visualize the Lyapunov function in zero-sum network games with $n$-agents
with strictly positive exploration profiles, i.e., $T_{k}>0$ for all $k\in V$,
(KL-divergence from the current action profile to the unique QRE for that
exploration profile), we adapt the dimension reduction method of [33] (cf.
[32]). This yields panel 4 in Figure 4.

For an $n$-agent network game, with a fixed and strictly positive exploration
profile, we start by determining its unique QRE, $q$. By our main result,
Theorem 4.1, this can be done by simulating the Q-learning dynamics. Then, we
select two vectors $u,v$ with $n$ random entries each in $(0,1)$. The random
entries of the vectors $u,v$ correspond to the probability with which each
agent selects their first action (here $H$). Instead of forming convex
combinations of these random vectors and plotting the Lyapunov function across
this (randomly selected) space, we perform the following transformation that
allows for a more comprehensive snapshot of the whole joint action space.
Specifically, we map each coordinate $u(k)$ (and similarly for $v$) with $k\in
V$ to $\tilde{u}(k)=\ln{u(k)/(1-u(k))}$. Then, we form linear combinations of
the transformed vectors $\tilde{u},\tilde{v}$ using real-valued
scalars,$\alpha,\beta\in\mathbb{R}$. Note that the all-zero vector (in the
transformed space) corresponds to the uniform distribution for each agent (in
the choice distribution space). Finally, we map the resulting point
$z:=\alpha\cdot\tilde{u}+\beta\cdot\tilde{v}$ from the transformed space back
to the product simplex via the (coordinate-wise) transformation
$z(k)\to\exp{(z(k))}/(\exp{(z(k))}+1)$ and plot the potential at the resulting
point (KL-divergence between that point and the unique QRE, $q$). We repeat
the process for a range of both positive and negative values for $\alpha$’s
and $\beta$’s. This yields the $x-y$ coordinates in panel 4 and the evaluation
yields the depicted 3D surface. The process is summarized in Algorithm 1.

Algorithm 1 3D Visualization of the Lyapunov function (KL-divergence)

Input (network game): number of agents, payoff matrices, (strictly positive)
exploration rates.
Output: Snapshot of the Lyapunov function (KL-divergence).

1:procedure Compute QRE($T_{k},k=1,\dots,n$)

2: $q\leftarrow$ unique QRE (e.g., by running (7))

3:$u,v$ generate random vectors with $n$ entries in $(0,1)$.

4:procedure Transform Variables($u,v,\alpha,\beta$)

5: for $k\leftarrow V$ do

6: $u(k)\leftarrow\ln{\left(u(k)/(1-u(k))\right)}$

7: $v(k)\leftarrow\ln{\left(v(k)/(1-v(k))\right)}$

8: $z\leftarrow\alpha\cdot u+\beta\cdot v$

9: for $k\leftarrow V$ do

10: $z(k)\leftarrow\exp{\left(z(k)/(z(k)+1)\right)}$

11:procedure Evaluate Lyapunov function($q,z$)

12: $D_{\text{KL}}=0$

13: for $k\in V$ do

14: $D_{\text{KL}}\leftarrow
D_{\text{KL}}+q(k)\ln\frac{q(k)}{z(k)}+(1-q(k))\ln\frac{1-q(k)}{1-z(k)}$

15: return tuple ($\alpha,\beta,D_{\text{KL}}$)

16:plot $\leftarrow$ ($\alpha,\beta,D_{\text{KL}}$)

A restriction of this method in $n$-player games is that, for each point that
it generates, it uses the same $\alpha,\beta$ to scale the transformed
variables of _all_ agents. Figure 9 shows snapshots of the Lyapunov function
in four instances of the (ZSPG) game with fixed (and strictly positive)
exploration profiles for different numbers of agents.

Figure 9: Snapshots of the Lyapunov function (KL-divergence between each
choice distribution profile and the unique QRE) in four instances of the
(ZSPG) game with fixed (and strictly positive) exploration profiles and
different numbers of agents. In all cases, the Lyapunov (potential) function
is convex with a unique minimizer at $0$.

###  C.5 Equilibrium selection in the network game

One question that is hard to tackle theoretically concerns the equilibrium
selection as exploration rates converge to $0$. As we saw in Theorem 4.1, when
all agents have positive exploration rates, then there is a unique QRE and the
joint-learning dynamics converge to that QRE. However, as exploration rates
approach zero (for instance, after the exploration phase ends for all agents),
it is not clear which equilibrium will be selected in the original game (as
the limit of the sequence of the unique QRE for the different strictly
positive exploration profiles).

In this part, we test this question experimentally in the (ZSPG) game of
Section 5. We consider an instance with $3$ non-dummy agents and different
exploration policies for the agents. Recall that in this case, the original
network game (with no exploration) has multiple Nash equilibria of the
following form: the odd agents ($p_{1}$ and $p_{3}$) select $T$ with
probability 1 and the even agent ($p_{2}$) plays an arbitrary strategy in
$(0,1)$ (i.e., probabilities of playing $H$). In any equilibrium, the payoff
of $p_{2}$ is $0$ whereas the payoffs of $p_{1}$ and $p_{3}$ sum up to $2$.
However, the crucial point is that the split of $2$ between $p_{1}$ and
$p_{3}$ critically depends on the strategy of $p_{2}$. In particular, we saw
in Figure 5 that without exploration, the Q-learning dynamics can converge to
any of these multiple equilibria, thus inducing arbitrary asymmetries between
the payoffs of $p_{1}$ and $p_{3}$.

The results of one representative exploration scenario (with linearly changing
exploration rates) and averages over 50 runs with randomly matched CLR-1 and
ETE exploration policies are presented in Figure 10.

Figure 10: Effects of exploration on equilibrium selection in the (ZSPG) of
Section 5. The upper panels show an individual run and the bottom panels show
averages (means and 1 standard deviation as shaded region around the mean)
over 50 runs. Panels 1 to 3 show the probability of playing $H$ at QRE, the
utilities and the exploration rates of the agents, respectively. The effect of
exploration is shown via the ratio of utilities of $p_{1}$ and $p_{3}$ in the
fourth panel of each row. Exploration by the even agent ($p_{2}$) leads that
agent to select the $0.5$ strategy at equilibrium (when exploration drops back
to $0$ by all agents) which results in a fair split (close to 1, dotted red
line in panels 4) of the payoffs between agents $p_{1}$ and $p_{3}$.

The main takeaway of these experiments is captured by the last panel "Ratio of
utilities" of each row. Namely, sufficient exploration by the even agent (the
agent with multiple equilibrium strategies) leads that agent to select a
strategy close to the uniform one (here $0.5$ since there are two actions). In
turn, this leads to a fair split of the stake between the odd numbered agents
($p_{1}$ and $p_{3}$). This is in sharp contrast to the case without
exploration (cf. Figure 5 in the main part) in which any equilibrium (i.e.,
any strategy between $0,1$) is a potential limit point of the dynamics for the
even agent (thus, leading to arbitrary splits of the share between the odd
numbered agents).

While these results cannot lead to a formal argument about the effect of
exploration in equilibrium selection (when exploration goes back to zero for
all agents), they highlight the importance of further studying equilibrium
selection in competitive environments both experimentally and theoretically.
In particular, the (potentially positive) effects of (individual) exploration
to social welfare (here, fair distribution of rewards) constitute an concrete
and intriguing direction for future research in this area.