# Learning in Quantum Games

Kyriakos Lotidis∗ ∗ Department of Management Science & Engineering, Stanford
University<EMAIL_ADDRESS>,  Panayotis Mertikopoulos♯ ♯ Univ.
Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
<EMAIL_ADDRESS>and  Nicholas Bambos‡ ‡ Department of
Electrical Engineering and Management Science & Engineering, Stanford
University<EMAIL_ADDRESS>
###### Abstract.

In this paper, we introduce a class of learning dynamics for general quantum
games, that we call “follow the quantum regularized leader” (FTQL), in
reference to the classical FTRL template for finite games. We show that the
induced quantum state dynamics decompose into  (it n) a classical, commutative
component which governs the dynamics of the system’s eigenvalues in a way
analogous to the evolution of mixed strategies under FTRL; and  (it n) a non-
commutative component for the system’s eigenvectors which has no classical
counterpart.  Despite the complications that this non-classical component
entails, we find that the “follow the quantum regularized leader” (FTQL)
dynamics incur no more than constant regret in _all_ quantum games. Moreover,
adjusting classical notions of stability to account for the nonlinear geometry
of the state space of quantum games, we show that only _pure quantum
equilibria_ can be stable and attracting under FTQL while, as a partial
converse, pure equilibria that satisfy a certain “variational stability”
condition are always attracting. Finally, we show that the FTQL dynamics are
_Poincaré recurrent_ in quantum min-max games, extending in this way a very
recent result for the quantum replicator dynamics.

###### Key words and phrases:

Quantum games; Nash equilibrium; regularized learning; asymptotic stability

###### 2020 Mathematics Subject Classification:

Primary 91A81, 37N40, 68Q32; secondary 68T05, 81Q93, 91B80.

##  1\. Introduction

The advent of quantum information theory – and, with it, the associated
“quantum advantage” [36, 4, 50] – has had a profound impact on computer
science and machine learning, from quantum cryptography and shadow tomography
[1], to quantum generative adversarial networks and adversarial learning [11,
7, 27]. At a high level, the advantages of quantum-based computing are owed to
the possibility of preparing superpositions of binary-state quantum systems
known as _qubits_ : classical bits cannot lie in superposition, so the
calculations that can be performed by classical computers are _de facto_
limited by their binary alphabet and memory structure. In light of this,
quantum computing has the potential to greatly accelerate the development of
artificial intelligence algorithms and models, with Google’s “Sycamore”
$54$-qubit processor training an autonomous vehicle model in less than $200$
seconds [4].

In a similar manner, when such models are deployed in a multi-agent context –
e.g., as in the case of QGANs or autonomous vehicles – the landscape changes
drastically relative to classical non-cooperative frameworks. The main reason
for this is again the “quantum advantage”: due to the intricacies of
decoherence and entaglement – two quantum notions that have no classical
counterpart – quantum players can have a distinct advantage over “classical”
players, achieving higher payoffs at equilibrium than would otherwise be
possible [33, 15]. This is again owed to the fact that probabilistic mixing
works differently in the quantum and classical worlds: in classical games, a
mixed _strategy_ is a probabilistic convex combination of the constituent pure
strategies; in quantum games, a mixed _state_ is a probabilistic mixture of
the quantum _projectors_ associated to each constituent state. Because of
this, a mixed quantum state can return payoffs that lie outside the convex
hull of classical mixed strategies, thus providing a tangible advantage to
players with access to quantum technologies – e.g., the ability to encode
their action in a qubit register, which is then submitted to a “referee” (the
natural mechanism determining the payoffs of a quantum game).

Of course, the extent to which the advantage of quantum players manifests
itself is contingent on the players’ actually reaching an equilibrium. The
recent work of Bostanci & Watrous [5] has shown that the problem of computing
an approximate Nash equilibrium of a quantum game is included in PPAD, so, by
the seminal work of Daskalakis et al. [12, 13], it must be complete for this
class (since computing a quantum equilibrium is at least as hard as computing
a classical one). Thus, given that the dimensionality of a quantum game is
exponential in the number of qubits available to each player, computing a Nash
equilibrium of a quantum game quickly becomes an intractable affair, in all
but the smallest games. On that account, it seems more reasonable to turn to
an online learning paradigm where each player seeks to minimize their
individual regret, and instead ask:

Are all equilibrium outcomes equally likely under a quantum no-regret learning
scheme?
Is there a class of equilibria with an inherent selection bias – either for or
against?

### Our contributions.

First, to achieve no-regret in a quantum setting, we introduce a flexible
model for learning in general $N$-player quantum games based on the popular
“follow the regularized leader” (FTRL) template for _finite_ games [42, 41].
The resulting model, which we call “follow the quantum regularized leader”
(FTQL), contains as a special case the matrix multiplicative / exponential
weights (MMW) dynamics that have been used extensively in quantum games and
matrix learning [46, 22, 24, 2, 23], and which give rise to the quantum
replicator dynamics [20, 23]. Importantly, as we show in Section 3, the mixed-
state dynamics of FTQL decompose into a “classical” part (eigenvalues evolve
as the FTRL dynamics in finite games), plus a “quantum” component capturing
the evolution of the system’s eigenfunctions (and which has no classical
analogue).

In terms of regret minimization, all FTQL dynamics incur at most constant
regret, so they represent a compelling choice from a learning standpoint.
However, deriving the dynamics’ equilibrium convergence properties is
significantly more difficult because of the nonlinear geometry of the game’s
state space. Specifically, in contrast to finite games (where pure strategies
are isolated extreme points), the pure states of a quantum game form a
continuous manifold of stationary points (all of them extreme), so the study
of stability and convergence questions becomes a highly involved affair.
Nonetheless, despite these topological complications, we show that FTQL enjoys
the following fundamental properties:  (it n) Nash equilibriaare stationary;
(it n) limits of interior trajectories and Lyapunov stable states are Nash;
(it n) only _pure quantum equilibria_ can be stable and attracting under FTQL
(up to the exclusion of trivial stationary states); and  (it n) as a partial
converse, we show that pure states that satisfy a certain “variational
stability” condition are attracting, irrespective of the chosen regularizer.
On that account, our results lead to an implicit quantum “purification”
principle: under FTQL, _mixed states are inherently fragile, and only pure
quantum states can be consistently attracting._ 111In the classical world, a
version of the above collection of results is sometimes referred to as the
“folk theorem” of evolutionary game theory [10, 21, 30, 17].

Finally, we complement our results with a closer look at two-player, zero-sum
quantum games, where we show that FTQL exhibits a cycling property known as
_Poincaré recurrence:_ almost all trajectories of play return arbitrarily
close to their starting point infinitely often. This result is a broad
generalization of a recent result by Jain et al. [23], who established this
property for the MMW dynamics. In this regard, our result shows that the MMW
result is not a coincidence: despite the “quantum advantage”, perfect
competition cannot be resolved by the dynamics of regularized learning.

To simplify the presentation, we focus throughout on models that evolve in
continuous time. This allows us to sidestep issues having to do with
hyperparameter tuning and the like, and instead spotlight the essential
aspects of the theory.

##  2\. Preliminaries

We start by briefly reviewing some basics of quantum game theory and
introducing the necessary context for our results.

### Notation.

Given a (complex) Hilbert space $\mathcal{H}$, we will use Dirac’s bra-ket
notation to distinguish between an element $\lvert\psi\rangle$ of
$\mathcal{H}$ and its adjoint $\langle\psi\rvert$; otherwise, when a basis is
implied by the context, we will use the dagger notation “${\dagger}$” to
denote the Hermitian transpose $\psi^{{\dagger}}$ of $\psi$. We will also
write $\mathbb{H}^{d}$ for the space of $d\times d$ Hermitian matrices, and
$\mathbb{H}_{+}^{d}$ for the cone of positive-semidefinite matrices in
$\mathbb{H}^{d}$. Finally, given a real function
$f\colon\mathbb{R}\to\mathbb{R}$ and a Hermitian matrix
$\mathbf{X}\in\mathbb{H}^{d}$ with unitary eigen-decomposition
$\mathbf{X}=\sum_{\alpha=1}^{d}x_{\alpha}\mathbf{u}_{\alpha}\mathbf{u}_{\alpha}^{{\dagger}}$,
we will write $f(\mathbf{X})$ for the (likewise Hermitian) matrix
$f(\mathbf{X})=\sum_{\alpha=1}^{d}f(x_{\alpha})\mathbf{u}_{\alpha}\mathbf{u}_{\alpha}^{{\dagger}}$.

### Quantum games.

Following [15, 19], a _quantum game_ consists of the following primitives:

  1. (1)

A finite set of _players_ $i\in\mathcal{N}=\\{1,\dotsc,N\\}$.

  2. (2)

Each player $i\in\mathcal{N}$ has access to a complex Hilbert space
$\mathcal{H}_{i}\cong\mathbb{C}^{d_{i}}$ describing the set of (pure) _quantum
states_ available to the player (typically a discrete register of qubits). In
more detail, a quantum state is an element $\psi_{i}$ of $\mathcal{H}_{i}$
with unit norm, so the set of all such states is the unit sphere
$\Psi_{i}\coloneqq\\{\psi_{i}\in\mathcal{H}_{i}:\lVert\psi_{i}\rVert=1\\}$ of
$\mathcal{H}_{i}$. We will also write $\Psi\coloneqq\prod_{i}\Psi_{i}$ for the
space of all ensembles $\psi=(\psi_{1},\dotsc,\psi_{N})$ of pure states
$\psi_{i}\in\Psi_{i}$ that are independently prepared by each player
$i\in\mathcal{N}$.

  3. (3)

The players’ rewards are determined by their individual _payoff functions_
$u_{i}\colon\Psi\to\mathbb{R}$. These payoff functions are not arbitrary, but
are obtained from a joint positive operator-valued measure (POVM) quantum
measurement process that unfolds as follows [8]: First, we assume given a
finite set of possible _measurement outcomes_ $\omega\in\Omega$ that a referee
can observe from the players’ quantum states (e.g., measure a player-prepared
qubit to be “up” or “down”). Each such outcome $\omega\in\Omega$ is associated
to a positive semi-definite operator
$\mathbf{P}_{\omega}\colon\mathcal{H}\to\mathcal{H}$ that acts on the tensor
product $\mathcal{H}\coloneqq\bigotimes_{i}\mathcal{H}_{i}$ of the players’
individual state spaces; we further assume that
$\sum_{\omega\in\Omega}\mathbf{P}_{\omega}=\mathbf{I}$ so the joint
probability of observing $\omega\in\Omega$ when the system is at state
$\psi\in\Psi$ is

$P_{\omega}(\psi)=\langle\psi_{1}\otimes\dotsm\otimes\psi_{N}\rvert\mathbf{P}_{\omega}\lvert\psi_{1}\otimes\dotsm\otimes\psi_{N}\rangle$
(1)

The payoff to each player $i\in\mathcal{N}$ is given by the outcome of this
measurement process via a _payoff observable_
$U_{i}\colon\Omega\to\mathbb{R}$; specifically, in this context, $u_{i}(\psi)$
denotes the player’s expected payoff at state $\psi\in\Psi$, viz.

$u_{i}(\psi)\coloneqq\langle
U_{i}\rangle\equiv\sum\nolimits_{\omega}P_{\omega}(\psi)\,U_{i}(\omega).$ (2)

A _quantum game_ is then defined as a tuple
$\mathcal{Q}\equiv\mathcal{Q}(\mathcal{N},\Psi,u)$ with players, quantum
states, and payoff functions as above.

### Mixed states.

In addition to pure states, each player $i\in\mathcal{N}$ can also prepare
probabilistic mixtures thereof, known as _mixed states_. In contrast to mixed
strategies in classical, finite games, these mixed states are _not_ convex
combinations of their pure counterparts; instead, given a family of pure
quantum states $\psi_{i\alpha_{i}}\in\Psi_{i}$ indexed by
$\alpha_{i}\in\mathcal{A}_{i}$, a mixed state is described by a _density
matrix_ of the form

$\mathbf{X}_{i}=\smashoperator[]{\sum_{\alpha_{i}\in\mathcal{A}_{i}}^{}}x_{i\alpha_{i}}\lvert\psi_{i\alpha_{i}}\rangle\langle\psi_{i\alpha_{i}}\rvert$
(3)

where $x_{i\alpha_{i}}\geq 0$ is the mixing weight of $\psi_{i\alpha_{i}}$,
and we assume that $\operatorname{tr}\mathbf{X}_{i}=1$ (the states
$\psi_{i\alpha_{i}}$ are not assumed to be orthogonal in this context). By
Born’s rule, this means that if each player $i\in\mathcal{N}$ prepares a mixed
state according to $\mathbf{X}_{i}$, the probability of observing
$\omega\in\Omega$ under $\mathbf{X}=(\mathbf{X}_{1},\dotsc,\mathbf{X}_{N})$
will be
$P_{\omega}(\mathbf{X})=\sum_{\alpha}x_{\alpha}\langle\psi_{\alpha}\rvert\mathbf{P}_{\omega}\lvert\psi_{\alpha}\rangle,$
where, in multi-index notation, $\alpha=(\alpha_{1},\dotsc,\alpha_{N})$,
$x_{\alpha}=\prod_{i}x_{i\alpha_{i}}$, and
$\psi_{\alpha}=\bigotimes_{i}\psi_{i\alpha_{i}}$. Thus, in a slight abuse of
notation, the expected payoff to player $i\in\mathcal{N}$ under $\mathbf{X}$
will be

$\displaystyle u_{i}(\mathbf{X})$
$\displaystyle=\sum_{\omega\in\Omega}\sum_{\alpha\in\mathcal{A}}x_{\alpha}P_{\omega}(\psi_{\alpha})\,U_{i}(\omega)=\sum_{\alpha\in\mathcal{A}}x_{\alpha}u_{i}(\psi_{\alpha})$
$\displaystyle=\smashoperator[]{\sum_{\alpha_{1}\in\mathcal{A}_{1}}^{}}\>\dotsi\>\smashoperator[]{\sum_{\alpha_{N}\in\mathcal{A}_{N}}^{}}x_{\alpha_{1}}\\!\dotsm
x_{\alpha_{N}}\,u_{i}(\psi_{\alpha_{1}},\dotsc,\psi_{\alpha_{N}}).$ (4)

### Contrasting to other classes of games.

The expression (2) for a player’s expected payoff under a mixed state is
reminiscent of mixed extensions of classical finite games, but this
association is very tenuous. From a conceptual standpoint, the principal
differences are as follows:

  1. (1)

There is an infinite continuum of pure states $\psi\in\Psi$, not a finite
number thereof (as is the case in finite games).

  2. (2)

The decomposition (3) of a density matrix into pure states is not unique;
generically, there may be a continuum of (non-equivalent) families of pure
states and mixing weights giving rise to the same density matrix.

  3. (3)

The convex superposition $\lambda\psi+(1-\lambda)\psi^{\prime}$ of two pure
states $\psi$ and $\psi^{\prime}$ may give rise to quantum interference terms
of the form $\lvert\psi\rangle\langle\psi^{\prime}\rvert$ and
$\lvert\psi^{\prime}\rangle\langle\psi\rvert$ in the induced payoff; these
cross-terms have no analogue in finite games.

Because of the above, treating a quantum game as a “tensorial” extension of a
finite game can be misleading. Instead, it would be more appropriate to view a
quantum game as a _continuous game_ where each player $i\in\mathcal{N}$
controls a matrix variable $\mathbf{X}_{i}$ drawn from the “spectraplex”

$\boldsymbol{\mathcal{X}}_{i}=\\{\mathbf{X}_{i}\in\mathbb{H}_{+}^{d_{i}}:\operatorname{tr}\mathbf{X}_{i}=1\\}$
(5)

and the player’s payoff function
$u_{i}\colon\boldsymbol{\mathcal{X}}\equiv\prod_{j}\boldsymbol{\mathcal{X}}_{j}\to\mathbb{R}$
is linear in every player’s density matrix
$\mathbf{X}_{j}\in\boldsymbol{\mathcal{X}}_{j}$, $j\in\mathcal{N}$.

###  NE.

In our quantum setting, the classical solution concept of a Nash equilibrium
(NE) characterizes mixed quantum states
$\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$ which discourage unilateral
deviations in the sense that

$u_{i}(\mathbf{X}^{\ast})\geq
u_{i}(\mathbf{X}_{i};\mathbf{X}^{\ast}_{-i})\quad\text{for all
$\mathbf{X}_{i}\in\boldsymbol{\mathcal{X}}_{i}$, $i\in\mathcal{N}$}$ (NE)

where we write
$(\mathbf{X}_{i};\mathbf{X}_{-i})=(\mathbf{X}_{1},\dots,\mathbf{X}_{i},\dotsc,\mathbf{X}_{N})$
for the choice of player $i$ relative to all other players. Since
$\boldsymbol{\mathcal{X}}_{i}$ is convex and $u_{i}$ is linear in
$\mathbf{X}_{i}$, the existence of Nash equilibria follows from the seminal
theorem of Debreu [14].

Now, letting

$\mathbf{V}_{i}(\mathbf{X})=\nabla_{\mathbf{X}_{i}^{\top}}u_{i}(\mathbf{X})$
(6)

denote the individual payoff gradient of player $i$, standard arguments [16,
40] show that the Nash equilibria of a quantum game $\mathcal{Q}$ are
precisely the solutions of the variational inequality

$\operatorname{tr}[\mathbf{V}(\mathbf{X}^{\ast})(\mathbf{X}-\mathbf{X}^{\ast})]\leq
0\quad\text{for all $\mathbf{X}\in\boldsymbol{\mathcal{X}}$}$ (VI)

where
$\mathbf{V}(\mathbf{X})=(\mathbf{V}_{1}(\mathbf{X}),\dotsc,\mathbf{V}_{N}(\mathbf{X}))$.
We note here that, since $u_{i}$ is linear in $\mathbf{X}_{i}$, the $i$-th
block $\mathbf{V}_{i}(\mathbf{X})$ of $\mathbf{V}(\mathbf{X})$ does not depend
on $\mathbf{X}_{i}$, and we have

$u_{i}(\mathbf{X}_{i};\mathbf{X}_{-i})=\operatorname{tr}[\mathbf{X}_{i}\mathbf{V}_{i}(\mathbf{X})]\quad\text{for
all $\mathbf{X}\in\boldsymbol{\mathcal{X}}$}.$ (7)

We will use these properties freely in the sequel.

### Regret.

Complementing the notion of a Nash equilibrium, an important rationality
requirement in dynamic environments is the minimization of a player’s _regret_
, i.e., the performance gap between the player’s expected cumulative payoff
over time versus the payoff of the best fixed state in hindsight. Formally,
the regret of the $i$-th player against the trajectory of play
$\mathbf{X}(t)\in\boldsymbol{\mathcal{X}}$, $t\geq 0$, is defined as

$\operatorname{Reg}_{i}(T)=\max_{\mathbf{X}^{\prime}_{i}\in\boldsymbol{\mathcal{X}}_{i}}\int_{0}^{T}[u_{i}(\mathbf{X}^{\prime}_{i};\mathbf{X}_{-i}(t))-u_{i}(\mathbf{X}(t))]\>dt$
(8)

and we say that player $i$ has _no regret_ if
$\operatorname{Reg}_{i}(T)=o(T)$. In the rest of the paper, we will focus on
learning dynamics that incur no regret, and we will examine their convergence
properties relative to the game’s Nash equilibria.

##  3\. Learning dynamics

### Learning via quantum regularization.

In classical, finite games, the most widely studied class of no-regret
dynamics is the so-called “follow the regularized leader” (FTRL) family of
algorithms [41, 42, 30]. The main idea behind this popular template is the
following: at each instance $t\geq 0$, every player $i\in\mathcal{N}$ plays a
mixed strategy that maximizes the player’s cumulative payoff minus a certain
regularization penalty. In this way, strategies that perform consistently
better tend to be preferred over their underpeforming counterparts, while the
“regularization penalty” introduces a certain degree of exploration to avoid
getting stuck.

In the quantum regime, the role of mixed strategies is played by the game’s
mixed quantum states, so the reinforcement mechanism behind FTRL leads to the
matrix-valued “follow the quantum regularized leader” (FTQL) dynamics

$\mathbf{X}_{i}(t)=\operatorname*{arg\,max}\limits_{\mathbf{X}_{i}\in\boldsymbol{\mathcal{X}}_{i}}\left\\{\int_{0}^{t}u_{i}(\mathbf{X}_{i};\mathbf{X}_{-i}(s))\>ds-
h_{i}(\mathbf{X}_{i})\right\\}$ (9)

where $h_{i}\colon\boldsymbol{\mathcal{X}}_{i}\to\mathbb{R}$ denotes the
_penalty function_ – or _regularizer_ – of player $i$ (discussed in detail
below). As stated, the FTQL dynamics (9) are in integral form, which is not
particularly well-suited for our analysis. Instead, to obtain a more concrete,
autonomous reformulation, consider as a first step the _regularized best
response maps_

$\mathbf{Q}_{i}(\mathbf{Y}_{i})\coloneqq\operatorname*{arg\,max}\nolimits_{\mathbf{X}_{i}\in\boldsymbol{\mathcal{X}}_{i}}\\{\operatorname{tr}[\mathbf{Y}_{i}\mathbf{X}_{i}]-h_{i}(\mathbf{X}_{i})\\}$
(10)

defined for all Hermitian
$\mathbf{Y}_{i}\in\boldsymbol{\mathcal{Y}}_{i}\coloneqq\mathbb{H}^{d_{i}}$.
Then, in view of (7), the integral dynamics (9) can be recast in differential
form as

$\dot{\mathbf{Y}}_{i}(t)=\mathbf{V}_{i}(\mathbf{X}(t))\qquad\mathbf{X}_{i}(t)=\mathbf{Q}_{i}(\mathbf{Y}_{i}(t)).$
(FTQL)

The dynamics (FTQL) will be the basis of our analysis, so some remarks are in
order. First, in terms of interpretation, (FTQL) can be seen as a gradient-
following process coupled with a regularized state selection scheme – the
dynamics $\dot{\mathbf{Y}}_{i}=\mathbf{V}_{i}$ and the mapping
$\mathbf{Q}_{i}\colon\mathbf{Y}_{i}\mapsto\mathbf{X}_{i}$ respectively. In
this regard, the regularizer $h_{i}$ which underlies the definition of
$\mathbf{Q}_{i}$ plays a crucial role, and different choices of $h_{i}$ may
yield very different dynamics. For concreteness, we will only assume in the
sequel that $h_{i}$ is a trace function of the form
$h_{i}(\mathbf{X}_{i})=\operatorname{tr}[\theta_{i}(\mathbf{X}_{i})]$ where
$\theta_{i}\colon[0,1]\to\mathbb{R}$ is continuous on $[0,1]$ and has
$\inf_{x\in(0,1]}\theta_{i}^{\prime\prime}(x)>0$. We will also say that
$\theta_{i}$ is _steep_ when $\lim_{x\to
0^{+}}\theta_{i}^{\prime}(x)=-\infty$, and, for normalization purposes, we
will assume that $\theta_{i}(0)=0$.

Suppressing player indices for simplicity, some standard examples of
regularizers are as follows:

######  Example 3.1 ($L^{2}$ regularization).

If $\theta(x)=x^{2}/2$, the players’ penalty function is the squared Frobenius
norm $h(\mathbf{X})=(1/2)\lVert\mathbf{X}\rVert_{F}^{2}$, in which case Eq. 10
gives the orthogonal projector
$\mathbf{Q}(\mathbf{Y})=\operatorname{\mathbf{\Pi}}_{\boldsymbol{\mathcal{X}}}(\mathbf{Y})\equiv\operatorname*{arg\,min}_{\mathbf{X}\in\boldsymbol{\mathcal{X}}}\lVert\mathbf{X}-\mathbf{Y}\rVert_{F}$.
This choice leads to the (Frobenius) projection dynamics:

$\dot{\mathbf{Y}}=\mathbf{V}(\mathbf{X})\qquad\mathbf{X}=\operatorname{\mathbf{\Pi}}_{\boldsymbol{\mathcal{X}}}(\mathbf{Y})$
(PD)

######  Example 3.2 (Von Neumann regularization).

Another standard choice is $\theta(x)=x\log x$ which yields the (negative) von
Neumann entropy $h(\mathbf{X})=\operatorname{tr}[\mathbf{X}\log\mathbf{X}]$.
By a standard calculation, this choice of regularizer gives rise to the matrix
multiplicative / exponential weights (MMW) dynamics

$\dot{\mathbf{Y}}=\mathbf{V}(\mathbf{X})\qquad\mathbf{X}=\frac{\exp(\mathbf{Y})}{\operatorname{tr}[\exp(\mathbf{Y})]}$
(MMW)

A discrete-time version of these dynamics was introduced in the context of
kernel learning by Tsuda et al. [46] and Kakade et al. [24]; for a series of
more recent developments in the context of quantum learning see [22, 2, 23].

######  Example 3.3 (Tsallis regularization).

Interpolating between the above, the _Tsallis regularizer_ is given by
$\theta(x)=[q(1-q)]^{-1}(x-x^{q})$ for some $q>0$ (with the continuity
convention $(x-x^{q})/(1-q)=x\log x$ for $q=1$). When $q\leftarrow 2$, we
recover the projection dynamics (PD); by contrast, the choice $q\leftarrow 1$
gives rise to (MMW); finally, the choice $q\leftarrow 1/2$ is particularly
popular in the context of bandit online learning, cf. [24, 51] and references
therein.

### The mixed-state dynamics of FTQL.

Under (FTQL), the evolution of the players’ mixed states $\mathbf{X}(t)$ is
described _implicitly_ via that of the auxiliary score matrix $\mathbf{Y}(t)$.
On the other hand, obtaining an _explicit_ expression for the dynamics of
$\mathbf{X}(t)=\mathbf{Q}(\mathbf{Y}(t))$ is considerably more difficult
because the rules of matrix calculus do not provide an analytic expression for
the tensor derivative $\nabla_{\mathbf{Y}}\mathbf{Q}(\mathbf{Y})$ of
$\mathbf{Q}$, even when the latter is available in closed form.

To circumvent this difficulty, we will work with a unitary eigendecomposition
of $\mathbf{X}$ of the form

$\mathbf{X}=\sum\nolimits_{\alpha=1}^{d}x_{\alpha}\mathbf{u}_{\alpha}\mathbf{u}_{\alpha}^{{\dagger}}$
(11)

where $x_{\alpha}\geq 0$, $\alpha=1,\dotsc,d$, is an enumeration of the
eigenvalues of $\mathbf{X}$, $\mathbf{u}_{\alpha}\in\mathcal{H}$ is a unit-
norm eigenvector of $\mathbf{X}$ corresponding to $x_{\alpha}$, and player
indices have again been suppressed (to lighten notation). Since, in general,
$\mathbf{X}$ does not commute with $\mathbf{V}$ (and hence with
$\dot{\mathbf{X}}$), the eigenvalues and eigenvectors of $\mathbf{X}$ will
evolve in a coupled, concurrent manner; our first result below provides an
explicit expression for this co-evolution:

######  Theorem 1.

Let
$\mathbf{X}(t)=\sum_{\alpha=1}^{d}x_{\alpha}(t)\,\mathbf{u}_{\alpha}(t)\mathbf{u}_{\alpha}^{{\dagger}}(t)$
be an eigendecomposition of $\mathbf{X}(t)$ as per (11), and suppose that $h$
is steep. Then, under (FTQL), the entries
$[\dot{\mathbf{X}}]_{\alpha\beta}=\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{X}}\mathbf{u}_{\beta}$
of $\dot{\mathbf{X}}$ follow the quantum state dynamics:

$[\dot{\mathbf{X}}]_{\alpha\beta}=\begin{dcases}\frac{V_{\alpha\alpha}}{\theta^{\prime\prime}(x_{\alpha})}-\frac{\sum_{\kappa}V_{\kappa\kappa}/\theta^{\prime\prime}(x_{\kappa})}{\sum_{\kappa}\theta^{\prime\prime}(x_{\alpha})/\theta^{\prime\prime}(x_{\kappa})}&\alpha=\beta\\\\[6.0pt]
\frac{x_{\beta}-x_{\alpha}}{\theta^{\prime}(x_{\beta})-\theta^{\prime}(x_{\alpha})}V_{\alpha\beta}&\alpha\neq\beta\end{dcases}$
(QD)

where
$V_{\alpha\beta}=\mathbf{u}_{\alpha}^{{\dagger}}\mathbf{V}(\mathbf{X})\mathbf{u}_{\beta}$
and we are using the continuity convention
$(x-y)/[\theta^{\prime}(x)-\theta^{\prime}(y)]=1/\theta^{\prime\prime}(x)$
when $y\to x$.

The proof of Theorem 1 is based on the fact that, if a Hermitian matrix
$\mathbf{A}$ with eigendecomposition
$\mathbf{A}=\sum_{\alpha}\lambda_{\alpha}\mathbf{u}_{\alpha}\mathbf{u}_{\alpha}^{{\dagger}}$
follows the dynamics $\dot{\mathbf{A}}=\mathbf{M}$, a differentiation of the
eigenvalue equation
$\mathbf{A}\mathbf{u}_{\alpha}=\lambda_{\alpha}\mathbf{u}_{\alpha}$ yields

$\dot{\lambda}_{\alpha}\delta_{\alpha\beta}=(\lambda_{\alpha}-\lambda_{\beta})\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{u}}_{\beta}+\mathbf{u}_{\alpha}^{{\dagger}}\mathbf{M}\mathbf{u}_{\beta}\quad\text{for
all $\alpha,\beta$}.$ (12)

This identity allows us to analyze and derive an expression for
$\dot{\mathbf{X}}$ by solving the Lagrangian associated with the maximization
problem (10). The full proof is relegated to the appendix; instead, we focus
here on a representative example.

######  Example 3.4 (The quantum replicator dynamics).

An important special case of the dynamics (QD) is obtained by the von Neumann
regularizer $h(\mathbf{X})=\operatorname{tr}[\mathbf{X}\log\mathbf{X}]$ of
Example 3.2. This yields the quantum replicator dynamics

$[\dot{\mathbf{X}}]_{\alpha\beta}=\begin{dcases*}\textstyle
x_{\alpha}[V_{\alpha\alpha}-\sum_{\kappa}x_{\kappa}V_{\kappa\kappa}]&for
$\alpha=\beta$\\\\[3.0pt] \frac{x_{\beta}-x_{\alpha}}{\log x_{\beta}-\log
x_{\alpha}}V_{\alpha\beta}&for $\alpha\neq\beta$\end{dcases*}$ (QRD)

for the diagonal and off-diagonal elements of $\mathbf{X}$ respectively. The
diagonal part of (QRD) is formally analogous to the replicator dynamics of
evolutionary game theory [45, 48, 39] and captures the evolution of the
eigenvalues of $\mathbf{X}(t)$. Thus, taken together with its off-diagonal
component, (QRD) provides an explicit expression for the evolution of mixed
states under (MMW). Alternatively, by applying Fréchet’s differentiation
formula to (MMW) directly, (QRD) can be rewritten in basis-free notation as

$\dot{\mathbf{X}}=\int_{0}^{1}\mathbf{X}^{1-s}\mathbf{V}(\mathbf{X})\mathbf{X}^{s}\>ds-\operatorname{tr}[\mathbf{X}\mathbf{V}(\mathbf{X})]\mathbf{X}$
(13)

The dynamics (QRD) and the coordinate-free expression (13) agree with the
dynamics of Jain et al. [23] (who derived an equivalent expression under the
assumption that $\mathbf{X}$ and $\dot{\mathbf{X}}$ commute), but not with the
dynamics of Hidalgo [20] that follow a different, unrelated quantization
paradigm. We provide the relevant calculations in Appendix B. $\lozenge$

In the sections that follow, we will examine in detail how the classical and
quantum components of (FTQL) interface with each other to determine the
player’s long-run behavior.

##  4\. Regret minimization

We begin our analysis of (FTQL) with a result concerning the dynamics’ regret
minimization properties. To provide the necessary context, it is known that
the FTRL dynamics incur at most constant regret in classical, _finite_ games
[25, 32]. As we illustrate below, despite taking place over a _continuum_ of
pure states, the matrix-valued dynamics (FTQL) enjoy the same regret
minimization guarantees in quantum games. Formally, we have the following
result.

######  Proposition 1.

Let $\mathbf{X}(t)=\mathbf{Q}(\mathbf{Y}(t))$, $t\geq 0$, be a trajectory of
play induced by (FTQL). Then, for all $T\geq 0$, we have

$\operatorname{Reg}_{i}(T)\leq\lvert
d_{i}\cdot\theta_{i}(1/d_{i})-\theta_{i}(1)\rvert.$ (14)

The proof of Proposition 1 builds on the general theory of [25] and is
presented in detail in Appendix C. Instead, we only note here that the
dependence of the bound (14) on the dimensionality of the game depends
crucially on the choice of regularizer:  (it n) the Euclidean regularizer
$\theta(x)=x^{2}/2$ gives an $\operatorname{\mathcal{O}}(1)$ bound;  (it n)
the von Neumann entropy leads to an $\operatorname{\mathcal{O}}(\log d)$
dependence; and, finally,  (it n) the bound for the Tsallis regularizer
$\theta(x)\propto x-x^{q}$ is $\operatorname{\mathcal{O}}(d^{1-q})$ for all
$q\in(0,1)$.  This should be contrasted to _discrete-time_ models of online
learning, where quadratic regularization leads to suboptimal results relative
to _both_ the entropic and Tsallis variants [44, 26, 51]. The reason for this
discrete-to-continuous gap has to do with the fact that (FTQL) admits an
_exact_ energy function, the so-called _Fenchel coupling_

$\displaystyle F_{i}(\mathbf{X}_{i},\mathbf{Y}_{i})$
$\displaystyle=h_{i}(\mathbf{X}_{i})+h^{\ast}_{i}(\mathbf{Y}_{i})-\operatorname{tr}[\mathbf{X}_{i}\mathbf{Y}_{i}]$
(15) where $\mathbf{X}_{i}\in\boldsymbol{\mathcal{X}}_{i}$,
$\mathbf{Y}_{i}\in\boldsymbol{\mathcal{Y}}_{i}$, and $\displaystyle
h^{\ast}_{i}(\mathbf{Y}_{i})$
$\displaystyle=\max\nolimits_{\mathbf{X}_{i}\in\boldsymbol{\mathcal{X}}_{i}}\\{\operatorname{tr}[\mathbf{X}_{i}\mathbf{Y}_{i}]-h_{i}(\mathbf{X}_{i})\\}$
(16)

denotes the convex conjugate of $h_{i}$. A version of this primal-dual
coupling was first introduced by [30] in the setting of finite games, and it
has the following fundamental property:

######  Lemma 1.

Let $\mathbf{X}(t)=\mathbf{Q}(\mathbf{Y}(t))$, $t\geq 0$, be a trajectory of
play induced by (FTQL). Then, for all $\mathbf{P}\in\boldsymbol{\mathcal{X}}$,
we have

$\frac{d}{dt}F_{i}(\mathbf{P}_{i},\mathbf{Y}_{i}(t))=\operatorname{tr}[\mathbf{V}_{i}(\mathbf{X}(t))\,(\mathbf{X}_{i}(t)-\mathbf{P}_{i})].$
(17)

The importance of this lemma (which is proved in Appendix A) lies in that the
RHS of (17) is precisely the integrand of the regret, so Proposition 1 is
obtained by applying Lemma 1 to the state that witnesses the maximum in the
definition (8) of the regret of player $i$. We defer the relevant calculations
to Appendix C.

##  5\. Convergence, stability, and the folk theorem

In view of the strong regret minimization guarantees of Proposition 1, the
matrix-valued dynamics (FTQL) emerge as a very compelling choice from a
learning standpoint. At the same time, even in the case of classical finite
games, it is known that regret minimization _does not_ suffice to exclude non-
rationalizable outcomes: for example, as was shown by Viossat & Zapechelnyuk
[47], the players’ empirical frequency of play under a no-regret policy may
still end up assigning positive selection probability to (strictly) dominated
strategies, and _only_ dominated ones. On that account, our aim in the rest of
this section will be to take a closer look at the convergence and stability
properties of (FTQL) relative to the game’s Nash equilibria.

### Notions of stability and convergence.

Our analysis will require some basic concepts from the theory of dynamical
systems, which we quickly discuss below. To begin with, recall that a _flow_
on an abstract metric space $\mathcal{Z}$ is a continuous map
$\phi\colon\mathbb{R}\times\mathcal{Z}\to\mathcal{Z}$ such that  n(itn)
$\phi_{#1}(z)=z$; and  n(itn) $\phi_{#1}(z)=\phi_{#1}(\phi_{#1}(z))$ for all
$t,s\in\mathbb{R}$ and all $z\in\mathcal{Z}$. Informally, a flow is usually
generated by the _solution orbits_ of a system of well-posed ordinary
differential equations, such as (FTQL): in this interpretation, $\phi_{#1}(z)$
simply denotes the position at time $t$ of the ODE solution that starts at $z$
at time $t=0$.

With this in mind, the following notions of invariance and stability will play
a key role in our analysis. Given a point $p\in\mathcal{Z}$, we will say that:

  1. (1)

$p$ is _stationary_ if $\phi_{#1}(p)=p$ for all $t\in\mathbb{R}$.

  2. (2)

$p$ is _Lyapunov stable_ – or just _stable_ – if, for every neighborhood
$\mathcal{U}$ of $p$ in $\mathcal{Z}$, there exists some (smaller)
neighborhood $\mathcal{U}^{\prime}$ of $p$ in $\mathcal{Z}$ such that
$\phi_{#1}(\mathcal{U}^{\prime})\subseteq\mathcal{U}$ for all
$t\in\mathbb{R}$. In other words, $p$ is stable if any orbit that starts close
enough to $p$ remains close enough.

  3. (3)

$p$ is _attracting_ if it admits a neighborhood $\mathcal{U}$ such that
$\lim_{t\to\infty}\phi_{#1}(z)=p$ for all $z\in\mathcal{U}$. In other words,
$p$ is attracting if all nearby orbits converge to $p$.

  4. (4)

$p$ is _asymptotically stable_ if it is stable and attracting.

In what follows, we will seek to characterize precisely the stable and/or
attracting states of (FTQL).

### The classical regime.

To set the stage for the analysis to come, it will be useful to revisit the
classical regime of learning in classical _finite_ games. Focusing for
concreteness on the standard case of the replicator dynamics (cf. Examples 3.2
and 3.4 above), the stability and convergence landscape for general finite
games can be encoded in the so-called “folk theorem” of evolutionary game
theory, which states the following [10, 21]:

  1. (1)

Nash equilibria are stationary.

  2. (2)

Limits of interior orbits are Nash equilibria.

  3. (3)

Lyapunov stable states are Nash equilibria.

  4. (4)

A state is asymptotically stable if and only if it is a strict Nash
equilibrium (that is, every player has a unique best response at equilibrium).

Modulo some technicalities, these properties extend to the entire class of
FTRL dynamics for learning in classical _finite_ games, cf. [30, 17], and
references therein. However, the nonlinear geometry of the players’ state
space in quantum games places severe structural limitations on which of these
properties transfer over to the non-commutative, matrix-valued setting of
(FTQL). We explore this issue below.

### Regularized learning in the spectraplex.

A quick look at the quantum replicator dynamics (QRD) reveals the following
structural property: an eigenvalue of $\mathbf{X}$ that is initially zero in
(QRD) will always remain zero; likewise, an eigenvalue that is initially
positive, will always remain positive. Formally, this means that the kernel
$\ker(\mathbf{X})$ of $\mathbf{X}$ remains invariant under (QRD); hence, given
that the linear span of a Hermitian matrix is the orthocomplement of its
kernel, the same holds for $\operatorname{im}(\mathbf{X})$ as well.

The fact that the kernel – or, equivalently, the image – of a density matrix
remains invariant under (QRD) is the quantum analogue of the fact that the
support of a mixed strategy profile remains invariant under the standard
replicator dynamics. In the context of finite games, an immediate consequence
of this invariance is that _all_ pure strategy profiles are stationary (as
zero-dimensional faces of the simplex). This property extends to (QRD) and, in
fact, to the entire class of mixed-state dynamics under study: formally, under
(QD), _all pure quantum states are stationary._

That being said, the major qualitative difference between the quantum and
classical regimes is that, in quantum games, there is a _continuum_ of pure
states, namely the entire manifold $\Psi$ of rank $1$ density matrices (a
product of spheres). By contrast, in finite games, the pure states are the
corners of the simplex $\operatorname{\operatorname{\Delta}}$ spanned by the
player’s pure strategies, so they are finite in number and _isolated_. As a
result, in classical finite games, a pure strategy profile _can_ be
asymptotically stable; in quantum games, since every pure state is surrounded
by other invariant states, _it cannot_.

A second major difference is that, in finite games, strict Nash equilibria are
_robust:_ a small perturbation of the payoffs of the game does not change the
game’s strict equilibria. In quantum games, this robustness disappears:
indeed, the variational characterization (VI) of Nash equilibria means that
$\mathbf{V}(\mathbf{X}^{\ast})$ must be an element of the normal cone to
$\boldsymbol{\mathcal{X}}$ at $\mathbf{X}^{\ast}$; however, the normal cone to
the spectraplex at a matrix of rank $1$ has empty topological interior, so the
required membership property cannot be robust (for a graphical illustration,
see Fig. 1). In particular, any generic perturbation to the payoffs of a
quantum game, no matter how small, may lead to a small displacement of the
equilibrium in question on the manifold of pure states $\Psi$.

Figure 1. The fundamental geometric discrepancy between the classical and
quantum regimes (left and right respectively). In classical finite games, the
normal cone $\operatorname{NC}_{\operatorname{\operatorname{\Delta}}}(p)$ to
the simplex at a pure strategy $p$ has nonempty topological interior, so pure
Nash equilibria are generically _robust_ : if $v(p)$ is normal to
$\operatorname{\operatorname{\Delta}}$ at $p$, it will remain normal to
$\operatorname{\operatorname{\Delta}}$ after a small perturbation. On the
other hand, in quantum games, the normal cone
$\operatorname{NC}_{\boldsymbol{\mathcal{X}}}(\mathbf{P})$ to the spectraplex
at a pure state $\mathbf{P}$ is a ray, so pure Nash equilibria cannot be
robust in this sense. We also note the different geometry of pure states: in
the simplex, pure strategy profiles are isolated extreme points; in the
spectraplex, pure states form a continuous manifold.

### Consistency and variational stability.

In view of the above, we can already draw two major conclusions for the
quantum setting:

  1. (1)

Any concept of asymptotic stability must also include a notion of
_consistency:_ a state cannot be accessed if it is absent from the linear span
of the dynamics’ initial state.

  2. (2)

Any concept of robustness must likewise incorporate a notion of _variational
stability:_ small perturbations to an equilibrium state must tend to reinstate
it.

We formalize these two ideas as follows:

######  Definition 1.

Fix a state $\mathbf{P}\in\boldsymbol{\mathcal{X}}$ and let

$\boldsymbol{\mathcal{X}}_{\mathbf{P}}\coloneqq\\{\mathbf{X}\in\boldsymbol{\mathcal{X}}:\ker(\mathbf{X})\leq\ker(\mathbf{P})\\}$
(18)

denote the _domain of consistency_ of $\mathbf{P}$ in
$\boldsymbol{\mathcal{X}}$, i.e., the set of mixed states whose linear span
contains that of $\mathbf{P}$. Then, given a flow
$\boldsymbol{\chi}\colon\mathbb{R}\times\boldsymbol{\mathcal{X}}\to\boldsymbol{\mathcal{X}}$,
we will say that:

  1. (1)

$\mathbf{P}$ is _consistently attracting_ if it admits a neighborhood
$\boldsymbol{\mathcal{U}}$ such that
$\lim_{t\to\infty}\boldsymbol{\chi}_{#1}(\mathbf{X})=\mathbf{P}$ for all
$\mathbf{X}\in\boldsymbol{\mathcal{U}}\cap\boldsymbol{\mathcal{X}}_{\mathbf{P}}$.
In other words, $\mathbf{P}$ is consistently attracting if it attracts all
nearby consistent initializations.

  2. (2)

$\mathbf{P}$ is _consistently asymptotically stable_ if it is Lyapunov stable
and consistently attracting.

######  Definition 2.

We say that $\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$ is _( locally)
variationally stable_ if there exists a neighborhood
$\boldsymbol{\mathcal{U}}$ of $\mathbf{X}^{\ast}$ in
$\boldsymbol{\mathcal{X}}$ such that

$\operatorname{tr}[\mathbf{V}(\mathbf{X})(\mathbf{X}-\mathbf{X}^{\ast})]<0\quad\text{for
all
$\mathbf{X}\in\boldsymbol{\mathcal{U}}\mathopen{}\setminus\\{\mathbf{X}^{\ast}\\}$}.$
(VS)

Intuitively, Definition 1 captures precisely the accessibility condition that
we discussed above: $\boldsymbol{\mathcal{X}}_{\mathbf{P}}$ is a dense convex
set consisting of the relative interior of all faces of
$\boldsymbol{\mathcal{X}}$ that contain $\mathbf{P}$ (including
$\boldsymbol{\mathcal{X}}$ itself). As for Definition 2, variational stability
should be seen as an equilibrium refinement in the spirit of the seminal
concept of _evolutionary stability_ [29, 28] that underlies the “folk theorem”
for finite games; for a detailed discussion of (VS) in the context of
continuous games, see [31].

######  Remark.

In Definition 1, the notion of Lyapunov stability does not have a
“consistency” caveat tacked on. As we discuss in Appendix D, the reason for
this is that, in the case of Lyapunov stability, the two notions end up
coinciding, so it is not necessary to make this distinction. $\lozenge$

### A quantum “folk theorem”.

We are now in a position to state the main result of this section. To simplify
the presentation, we assume below that (FTQL) is run with a steep regularizer
and, as per Theorem 1, the quantum state dynamics (QD) refer to the flow
induced by (FTQL) on $\boldsymbol{\mathcal{X}}$.

######  Theorem 2.

Let $\mathcal{Q}\equiv\mathcal{Q}(\mathcal{N},\Psi,u)$ be a quantum game, fix
some state $\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$, and let
$\mathbf{X}(t)=\mathbf{Q}(\mathbf{Y}(t))$ be a trajectory of play induced by
(FTQL) with steep regularizers. Then:

  1. (1)

If $\mathbf{X}^{\ast}$ is a Nash equilibrium, it is a rest point of (QD).

  2. (2)

If $\mathbf{X}(t)\to\mathbf{X}^{\ast}$ as $t\to\infty$, $\mathbf{X}^{\ast}$ is
a Nash equilibrium of $\mathcal{Q}$.

  3. (3)

If $\mathbf{X}^{\ast}$ is stable under (QD), it is a Nash equilibrium of
$\mathcal{Q}$.

  4. (4)

If $\mathbf{X}^{\ast}$ is consistently asymptotically stable, then it is pure.

  5. (5)

If $\mathbf{X}^{\ast}$ satisfies (VS), it is consistently asymptotically
stable.

Before discussing the proof of Theorem 2, some remarks are in order. Perhaps
the most important one concerns the asymptotic stability part of the theorem
(which is arguably the most salient point of the classical folk theorem as
well). Here, even though the standard notion of asymptotic stability is ruled
out by the geometry of the game’s state space, (FTQL) achieves the next best
thing: by definition, states that are consistently asymptotically stable
attract all but a measure zero of nearby initial conditions, and Theorem 2
shows that _only_ pure states can have this property. This selection result
has important implications for quantum games because it shows that regularized
learning essentially “collapses” an initial mixed state to a _specific_ pure
state – and this, despite the fact that any mixed state can be prepared by an
infinitum of combinations of pure states.

On the flip side of all this, the implication that variationally stable states
are also (consistently) asymptotically stable provides a relevant convergence
criterion for (FTQL) and indicates an inherent robustness to variations of
player beliefs and predictions. In particular, since (VS) only involves the
primitives of the underlying game, the fact that such states are attracting
under _all_ FTQL dynamics means that they can be seen as universal attractors
– and since only pure states can have this property, we also infer indirectly
that variationally stable states are _a fortiori_ pure.

Figure 2. Convergence to a variationally stable equilibrium in a quantum anti-
coordination game. Each player’s trajectory is represented in their individual
Bloch sphere; see Appendix F for the details.

### Proof sketch.

We conclude this section with a short outline of the proof of the last two
parts of Theorem 2 (the full proof is presented in Appendix D). First, the
implication that only pure states can be stable attractors hinges on the
following volume preservation principle:

######  Proposition 2.

Let $\boldsymbol{\mathcal{W}}\subseteq\boldsymbol{\mathcal{Y}}$ be an open set
of initial conditions of (FTQL), and let
$\boldsymbol{\mathcal{W}}_{t}=\boldsymbol{\psi}_{#1}(\boldsymbol{\mathcal{W}})$,
$t\geq 0$, denote the evolution of $\boldsymbol{\mathcal{W}}$ under the flow
$\boldsymbol{\psi}\colon\mathbb{R}\times\boldsymbol{\mathcal{Y}}\to\boldsymbol{\mathcal{Y}}$
of (FTQL). Then,
$\operatorname{vol}(\boldsymbol{\mathcal{W}}_{t})=\operatorname{vol}(\boldsymbol{\mathcal{W}})$
for all $t\geq 0$.

Proposition 2 is central to our work in several aspects. First, this volume-
preservation property applies to _all_ quantum games and _all_ FTQL dynamics,
generalizing in this way the very recent analysis of Jain et al. [23] for
(MMW) / (QRD) in two-player, zero-sum games. This degree of generality is due
to the fact that each player’s payoff function is individually linear in the
player’s own density matrix, so the individual gradient fields
$\mathbf{V}_{i}$ do not depend on $\mathbf{X}_{i}$; Proposition 2 then follows
by an application of Liouville’s formula.

In this regard, Proposition 2 can be seen as a quantum analogue of the
universal volume-preservation property of FTRL dynamics in _finite_ games [9,
17]. However, as in the classical world, it is worth noting that Proposition 2
concerns the flow of (FTQL) on $\boldsymbol{\mathcal{Y}}$, not the induced
flow on $\boldsymbol{\mathcal{X}}$; in particular,
$\mathbf{Q}(\boldsymbol{\mathcal{W}}_{t})$ could still collapse to a boundary
state of $\boldsymbol{\mathcal{X}}$ if $\boldsymbol{\mathcal{W}}_{t}$ escapes
to infinity. Because of this, although Proposition 2 precludes convergence to
full-rank equilibria relatively easily, excluding lower-rank equilibria
requires more delicate arguments, where the notion of consistency plays a
major role (and has no classical counterpart).

Finally, the last part of Theorem 2 leverages an energy argument in the spirit
of Lyapunov’s direct method. In tune with the primal-dual nature of (FTQL), a
natural choice of energy function is the Fenchel coupling
$E(t)=F(\mathbf{X}^{\ast},\mathbf{Y}(t))$ of (15), which is in turn linked to
(VS) via Lemma 1. Putting these two elements together readily yields that
$\lim_{t\to\infty}E(t)$ exists; then, by a trapping argument, it can be shown
that there exists a sequence of times $t_{n}\to\infty$ such that
$\mathbf{X}(t_{n})\to\mathbf{X}^{\ast}$, which allows us to conclude that
$E(t)\to 0$ and ultimately yields our claim.

##  6\. Poincaré recurrence in zero-sum games

In this last section, our aim is to study the long-run behavior of (FTQL) in
zero-sum games, a class of games that arise frequently in applications – and
is possibly the most widely studied family of quantum games.

In classical finite games, it is well known that the replicator dynamics –
and, more generally, all FTRL dynamics – produce trajectories that cycle
around interior equilibria, leading to a behavior known as _Poincaré
recurrence_ [35, 32]. Formally, in our setting, the dynamics (FTQL) are said
to be Poincaré recurrent if, for almost every initial condition
$\mathbf{X}(0)=\mathbf{Q}(\mathbf{Y}(0))\in\boldsymbol{\mathcal{X}}$ (in the
sense of Lebesgue), there exists an increasing sequence of times
$t_{n}\to\infty$ such that $\mathbf{X}(t_{n})\to\mathbf{X}(0)$ as
$n\to\infty$, i.e., almost all trajectories of (FTQL) return infinitely close
to their starting point infinitely often.

In our notation, a two-player zero-sum quantum game
$\mathcal{Q}\equiv\mathcal{Q}(\mathcal{N},\Psi,u)$ corresponds to the case
where $\mathcal{N}=\\{1,2\\}$ and $u_{1}=-u_{2}=-\mathcal{L}$ for some min-max
merit function
$\mathcal{L}\colon\boldsymbol{\mathcal{X}}_{1}\times\boldsymbol{\mathcal{X}}_{2}\to\mathbb{R}$.
In this context, Jain et al. [23] recently showed that the matrix
multiplicative / exponential weights dynamics (MMW) are Poincaré recurrent in
all two-player, zero-sum games that admit a full-rank equilibrium. As we show
below, this property extends to the _entire_ class of regularized learning
dynamics under study.

######  Theorem 3.

Let $\mathcal{Q}\equiv\mathcal{Q}(\mathcal{N},\Psi,u)$ be a $2$-player zero-
sum game admitting a full-rank equilibrium
$\mathbf{X}^{\ast}\in\operatorname{ri}\boldsymbol{\mathcal{X}}$. Then, almost
every solution orbit $\mathbf{X}(t)=\mathbf{Q}(\mathbf{Y}(t))$ of (FTQL) is
Poincaré recurrent: there exists an increasing sequence of times
$t_{n}\to\infty$ such that $\lim_{n\to\infty}\mathbf{X}(t_{n})=\mathbf{X}(0)$.

The proof of Theorem 3 comprises three main ingredients: The first is
Proposition 2, which shows that the flow induced by (FTQL) on
$\boldsymbol{\mathcal{Y}}$ is volume-preserving. The second is that the
Fenchel coupling (15) that played the role of a local energy function in
Theorem 2 becomes a _constant of motion_ in zero-sum games (this is also where
the full-rank assumption comes into play). The third is that, modulo a certain
quotient process that does not affect the dynamics’ trajectories on
$\boldsymbol{\mathcal{X}}$, the level sets of the Fenchel coupling are
bounded; this is the most challenging part of the proof, and the point where
the non-commutativity of the various processes involved complicates things
considerably. With these basic ingredients in place, our result follows by an
application of Poincaré’s theorem, which states that volume-preserving flows
with bounded trajectories are recurrent. We provide the relevant details in
Appendix E.

##  7\. Concluding remarks

When quantum computing models are deployed in a multi-agent context – from
autonomous vehicles to quantum GANs – the players’ interaction landscape
changes dramatically relative to classical interactions. The study of game-
theoretic learning in this quantum setting is still in its infancy, so it is
not clear at this stage what can be expected by quantum players with bounded
rationality. In this regard, the study of the FTQL dynamics provides the
following important insights: the geometric structure of quantum state space
leads to an inflation of “learning traps” (stationary states) that have no
classical counterpart; nonetheless, the only states that can be stable and
attracting under FTQL are the game’s pure quantum equilibria. Solidifying our
understanding of the limits of quantum game-theoretic learning is a
particularly fruitful research direction with potentially far-reaching
implications for the deployment of multi-agent quantum computing systems.

##  Appendix A Regularized best responses and the Fenchel coupling

In this appendix, we introduce the basic properties of the regularized best
response map $\mathbf{Q}$ and the Fenchel coupling. To simplify notation, we
will suppress player indices throughout; formally, this means that, for
example, $\mathbf{X}$ stands for the profile
$\mathbf{X}=(\mathbf{X}_{i})_{i\in\mathcal{N}}$; the ensemble mirror map
$\mathbf{Q}\colon\boldsymbol{\mathcal{Y}}\to\boldsymbol{\mathcal{X}}$ denotes
the product map $\mathbf{Q}=\prod_{i}\mathbf{Q}_{i}$; the aggregate
regularizer $h$ on $\boldsymbol{\mathcal{X}}$ represents the sum
$h=\sum_{i}h_{i}$, etc. The proper substitutions are easily inferred from the
context, so there is no danger of confusion.

We will also assume that $\boldsymbol{\mathcal{V}}$ is endowed with some
abstract norm $\lVert\cdot\rVert$, not necessarily induced by the Hilbert
structure of the quantum state space $\mathcal{H}$. Also, for technical
reasons, it will also be convenient to view $h$ as an extended-real-valued
function $h\colon\boldsymbol{\mathcal{V}}\to\mathbb{R}\cup\\{\infty\\}$
defined over the entire space $\boldsymbol{\mathcal{V}}\equiv\mathbb{H}^{d}$
of $d\times d$ Hermitian matrices by assigning the value
$h(\mathbf{X})=+\infty$ to all
$\mathbf{X}\in\boldsymbol{\mathcal{V}}\setminus\boldsymbol{\mathcal{X}}$.
Following Rockafellar [37], this allows us to define the _subdifferential_ of
$h$ at $\mathbf{X}\in\boldsymbol{\mathcal{X}}$ as

$\partial
h(\mathbf{X})\coloneqq\\{\mathbf{Y}\in\boldsymbol{\mathcal{Y}}:h(\mathbf{X}^{\prime})\geq
h(\mathbf{X})+\operatorname{tr}[\mathbf{Y}(\mathbf{X}^{\prime}-\mathbf{X})]\;\text{for
all $\mathbf{X}^{\prime}\in\boldsymbol{\mathcal{V}}$}\\},$ (A.1)

where $\boldsymbol{\mathcal{Y}}\equiv\boldsymbol{\mathcal{Y}}$ plays here the
role of the algebraic dual of $\boldsymbol{\mathcal{V}}$. The _domain of
subdifferentiability_ of $h$ is then defined as

$\operatorname{dom}\partial
h\coloneqq\\{\mathbf{X}\in\operatorname{dom}h:\partial h\neq\varnothing\\}$
(A.2)

and the _convex conjugate_ of $h$ is given by the expression

$h^{\ast}(\mathbf{Y})=\max_{\mathbf{X}\in\boldsymbol{\mathcal{X}}}\\{\operatorname{tr}[\mathbf{Y}\mathbf{X}]-h(\mathbf{X})\\}\quad\text{for
all $\mathbf{Y}\in\boldsymbol{\mathcal{Y}}$}.$ (A.3)

Since $h$ is a trace function of the form
$h(\mathbf{X})=\operatorname{tr}[\theta(\mathbf{X})]$ with $\theta$ strongly
convex over $[0,1]$, it readily follows that $h$ is also $K$-strongly convex
relative to $\lVert\cdot\rVert$ for some positive constant $K>0$. We then have
the following basic results:

######  Lemma A.1.

Let $h$ be a $K$-strongly convex regularizer on $\boldsymbol{\mathcal{X}}$ as
above, and let
$\mathbf{Q}\colon\boldsymbol{\mathcal{Y}}\to\boldsymbol{\mathcal{X}}$ be its
induced mirror map. Then:

  1. (1)

$\mathbf{Q}$ is single-valued on $\boldsymbol{\mathcal{Y}}$: in particular,
for all $\mathbf{X}\in\boldsymbol{\mathcal{X}}$,
$\mathbf{Y}\in\boldsymbol{\mathcal{Y}}$, we have
$\mathbf{X}=\mathbf{Q}(\mathbf{Y})\iff\mathbf{Y}\in\partial h(\mathbf{X})$.

  2. (2)

The prox-domain
$\boldsymbol{\mathcal{X}}_{h}\coloneqq\operatorname{im}\mathbf{Q}$ of $h$
satisfies
$\operatorname{ri}\boldsymbol{\mathcal{X}}\subseteq\boldsymbol{\mathcal{X}}_{h}\subseteq\boldsymbol{\mathcal{X}}$.

  3. (3)

$\mathbf{Q}$ is $(1/K)$-Lipschitz continuous and $\mathbf{Q}=\nabla h^{\ast}$.

Variants of these properties can be found in several points in the literature
– see e.g., [31] and references therein – but we provide a few quick pointers
here for completeness.

###### Proof.

For the first property of $\mathbf{Q}$, note that the maximum in (10) is
attained for all $\mathbf{Y}\in\boldsymbol{\mathcal{Y}}$ because $h$ is lower-
semicontinuous (l.s.c.) and strongly convex. Furthermore, by Fermat’s theorem
for stationarity points, $\mathbf{X}$ solves (10) if and only if
$\mathbf{Y}-\partial h(\mathbf{X})\ni 0$, i.e., if and only if
$\mathbf{Y}\in\partial h(\mathbf{X})$. The above also shows that
$\boldsymbol{\mathcal{X}}_{h}=\operatorname{dom}\partial h$; since
$\operatorname{ri}\boldsymbol{\mathcal{X}}\subseteq\operatorname{dom}\partial
h\subseteq\boldsymbol{\mathcal{X}}$ [37, Chap. 26], our second claim follows.
Finally, for our third claim, the expression $\mathbf{Q}=\nabla h^{\ast}$ is
an immediate consequence of Danskin’s theorem [43], while the Lipschitz
continuity of $\mathbf{Q}$ follows from standard variational analysis results,
[see e.g., 38, Theorem 12.60(b)]. ∎

The next properties of $\mathbf{Q}$ are more specialized and are intimately
related to the structure of the spectraplex:

######  Lemma A.2.

With notation and assumptions as in Lemma A.1, we have:

  1. (1)

$\partial
h(\mathbf{X})=\theta^{\prime}(\mathbf{X})+\operatorname{NC}(\mathbf{X})$,
where $\operatorname{NC}(\mathbf{X})$ denotes the normal cone to
$\boldsymbol{\mathcal{X}}$ at $\mathbf{X}$; in particular, for all
$\mathbf{X}\in\operatorname{ri}\boldsymbol{\mathcal{X}}$, we have $\partial
h(\mathbf{X})=\\{\theta^{\prime}(\mathbf{X})+\lambda\mathbf{I}:\lambda\in\mathbb{R}\\}$.

  2. (2)

$\mathbf{Y}$ and $\mathbf{Q}(\mathbf{Y})$ commute for all
$\mathbf{Y}\in\boldsymbol{\mathcal{Y}}$.

  3. (3)

If $\operatorname{eig}(\mathbf{Y})=\\{\mathbf{Y}_{\alpha}\\}_{\alpha=1}^{d}$
and $\operatorname{eig}(\mathbf{X})=\\{x_{\alpha}\\}_{\alpha=1}^{d}$
respectively denote the eigenvalues of $\mathbf{Y}\in\boldsymbol{\mathcal{Y}}$
and $\mathbf{X}=\mathbf{Q}(\mathbf{Y})\in\boldsymbol{\mathcal{X}}$, we have
$x_{\alpha}\to 0$ whenever $\mathbf{Y}_{\alpha}-\mathbf{Y}_{\beta}\to-\infty$
for some $\beta\neq\alpha$.

###### Proof.

For our first claim, let $\delta_{\boldsymbol{\mathcal{X}}}$ denote the
(convex) indicator of $\boldsymbol{\mathcal{X}}$, viz.
$\delta_{\boldsymbol{\mathcal{X}}}(\mathbf{X})=0$ for all
$\mathbf{X}\in\boldsymbol{\mathcal{X}}$ and
$\delta_{\boldsymbol{\mathcal{X}}}(\mathbf{X})=\infty$ for all
$\mathbf{X}\in\boldsymbol{\mathcal{V}}\setminus\boldsymbol{\mathcal{X}}$. By
standard convex analysis arguments [37], we have
$\partial\delta_{\boldsymbol{\mathcal{X}}}(\mathbf{X})=\operatorname{NC}(\mathbf{X})$
for all $\mathbf{X}\in\boldsymbol{\mathcal{X}}$, so

$\partial
h(\mathbf{X})=\partial\left[\operatorname{tr}[\theta(\mathbf{X})]+\delta_{\boldsymbol{\mathcal{X}}}(\mathbf{X})\right]=\theta^{\prime}(\mathbf{X})+\operatorname{NC}(\mathbf{X}),$
(A.4)

and our assertion follows.

For our second claim, let
$\mathbf{Y}=\mathbf{U}\mathbf{\Psi}\mathbf{U}^{{\dagger}}$ be an eigen-
decomposition of $\mathbf{Y}$. Then the objective of (10) can be rewritten as

$\displaystyle\operatorname{tr}[\mathbf{Y}\mathbf{X}]-h(\mathbf{X})=\operatorname{tr}[\mathbf{U}\mathbf{\Psi}\mathbf{U}^{{\dagger}}\mathbf{X}]-\operatorname{tr}[\theta(\mathbf{X})]$
$\displaystyle=\operatorname{tr}[\mathbf{\Psi}\mathbf{U}^{{\dagger}}\mathbf{X}\mathbf{U}]-\operatorname{tr}[\mathbf{U}^{{\dagger}}\theta(\mathbf{X})\mathbf{U}]$
$\displaystyle=\operatorname{tr}[\mathbf{\Psi}\mathbf{U}^{{\dagger}}\mathbf{X}\mathbf{U}]-\operatorname{tr}[\theta(\mathbf{U}^{{\dagger}}\mathbf{X}\mathbf{U})]$
(A.5)

since $\mathbf{X}$ and $\mathbf{U}^{{\dagger}}\mathbf{X}\mathbf{U}$ have the
same eigenvalues and $\operatorname{tr}[\theta(\cdot)]$ only depends on the
eigenvalues of its argument. Since $\boldsymbol{\mathcal{X}}$ remains
invariant under conjugation by any unitary matrix (i.e.,
$\mathbf{U}^{{\dagger}}\boldsymbol{\mathcal{X}}\mathbf{U}=\boldsymbol{\mathcal{X}}$
for every unitary $\mathbf{U}$), it follows that

$\max_{\mathbf{X}\in\boldsymbol{\mathcal{X}}}\\{\operatorname{tr}[\mathbf{Y}\mathbf{X}]-h(\mathbf{X})\\}=\max_{\mathbf{X}\in\boldsymbol{\mathcal{X}}}\\{\operatorname{tr}[\mathbf{\Psi}\mathbf{X}-\theta(\mathbf{X})]\\}=\max_{x\in\operatorname{\operatorname{\Delta}}_{d}}\left\\{\sum_{\alpha=1}^{d}[\mathbf{Y}_{\alpha}x_{\alpha}-\theta(x_{\alpha})]\right\\}$
(A.6)

where, in obvious notation, $x_{\alpha}$ and $\mathbf{Y}_{\alpha}$
respectively denote the eigenvalues of $\mathbf{X}$ and $\mathbf{Y}$. This
expression shows that the maximum value of (10) is attained when $\mathbf{Y}$
and $\mathbf{X}$ have a common basis of eigenvectors, which in turn means that
they commute. Since $\theta$ is strongly convex by assumption, (10) admits a
unique solution, and our claim follows.

Finally, for our third claim, let $\mathbf{X}_{n}=\mathbf{Q}(\mathbf{Y}_{n})$
for some sequence $\mathbf{Y}_{n}\in\boldsymbol{\mathcal{Y}}$, and write
$x_{\alpha,n}$ and $\mathbf{Y}_{\alpha,n}$ for the eigenvalues of
$\mathbf{X}_{n}$ and $\mathbf{Y}_{n}$ respectively. We seek to show that
$x_{\alpha,n}\to 0$ if there exists some $\beta$ such that
$\mathbf{Y}_{\alpha,n}-\mathbf{Y}_{\beta,n}\to-\infty$.

Now, by descending to a subsequence if necessary, we may assume without loss
of generality that there exists some $\varepsilon>0$ such that
$x_{\alpha,n}\geq\varepsilon>0$ for all $n$. Then, by the defining relation
(10) of $\mathbf{Q}(\mathbf{Y})$, we have

$\displaystyle\sum_{\alpha=1}^{d}[\mathbf{Y}_{\alpha,n}x_{\alpha,n}-\theta(x_{\alpha,n})]\geq\sum_{\alpha=1}^{d}[\mathbf{Y}_{\alpha,n}x^{\prime}_{\alpha,n}-\theta(x^{\prime}_{\alpha,n})]$
(A.7)

for all $x^{\prime}\in\operatorname{\operatorname{\Delta}}_{d}$. Therefore,
taking $x_{n}^{\prime}=x_{n}+\varepsilon(e_{\beta}-e_{\alpha})$, we readily
obtain

$\varepsilon(\mathbf{Y}_{\alpha,n}-\mathbf{Y}_{\beta,n})\geq\sum_{\kappa}[\theta(x_{\kappa,n})-\theta(x^{\prime}_{\kappa,n})]\geq\min
h-\max h$ (A.8)

which contradicts our original assumption that
$\mathbf{Y}_{\alpha,n}-\mathbf{Y}_{\beta,n}\to-\infty$. With
$\boldsymbol{\mathcal{X}}$ compact, the above shows that $x_{\alpha}^{\ast}=0$
for any limit point $x^{\ast}$ of $x_{n}$, as claimed. ∎

With all this in hand, we proceed below with the basic properties of the
Fenchel coupling – so named to account for the fact that it collects all terms
of Fenchel’s inequality, cf. [31]. The two main properties we will need are
encoded in the following proposition

######  Proposition A.1.

With notation and assumptions as in Lemma A.1, we have:

  1. (1)

$F(\mathbf{P},\mathbf{Y})\geq(K/2)\,\lVert\mathbf{Q}(\mathbf{Y})-\mathbf{P}\rVert^{2}$
for all $\mathbf{P}\in\boldsymbol{\mathcal{X}}$,
$\mathbf{Y}\in\boldsymbol{\mathcal{Y}}$.

  2. (2)

$\nabla_{\mathbf{Y}^{\top}}F(\mathbf{P},\mathbf{Y})=\mathbf{Q}(\mathbf{Y})-\mathbf{P}$
for all $\mathbf{P}\in\boldsymbol{\mathcal{X}}$,
$\mathbf{Y}\in\boldsymbol{\mathcal{Y}}$.

###### Proof.

For our first claim, let $\mathbf{X}=\mathbf{Q}(\mathbf{Y})$ so
$h^{\ast}(\mathbf{Y})=\operatorname{tr}[\mathbf{Y}\mathbf{X}]-h(\mathbf{X})$
by the definition (A.3) of $h^{\ast}$. The strong convexity of $h$ then yields

$\displaystyle
h(\mathbf{X})+t\operatorname{tr}[\mathbf{Y}(\mathbf{P}-\mathbf{X})]\leq
h(\mathbf{X}+t(\mathbf{P}-\mathbf{X}))\leq
th(\mathbf{P})+(1-t)h(\mathbf{X})-\tfrac{1}{2}Kt(1-t)\lVert\mathbf{X}-\mathbf{P}\rVert^{2},$
(A.9)

leading to the bound

$\tfrac{1}{2}K(1-t)\lVert\mathbf{X}-\mathbf{P}\rVert^{2}\leq
h(\mathbf{P})-h(\mathbf{X})-\operatorname{tr}[\mathbf{Y}(\mathbf{P}-\mathbf{X})]=F(\mathbf{P},\mathbf{Y})$
(A.10)

for all $t\in(0,1]$. Our assertion then follows by letting $t\to 0^{+}$ in
(A.10).

As for our second claim, Lemma A.1 readily yields

$\displaystyle\nabla
F(\mathbf{P},\mathbf{Y})=\nabla_{\mathbf{Y}^{\top}}h^{\ast}(\mathbf{Y})-\nabla_{\mathbf{Y}^{\top}}\operatorname{tr}[\mathbf{Y}\mathbf{P}]=\mathbf{Q}(\mathbf{Y})-\mathbf{P}$
(A.11)

as claimed. ∎

We are now in a position to prove Lemma 1 on the evolution of the Fenchel
coupling under the dynamics (FTQL); for convenience, we restate the result
below.

See 1

###### Proof.

By definition, we have

$\displaystyle\frac{d}{dt}F_{i}(\mathbf{P}_{i},\mathbf{Y}_{i}(t))$
$\displaystyle=\frac{d}{dt}\left[h_{i}(\mathbf{P}_{i})+h^{\ast}_{i}(\mathbf{Y}_{i}(t))-\operatorname{tr}[\mathbf{Y}_{i}(t)\mathbf{P}_{i}]\right]$
$\displaystyle=\operatorname{tr}[\dot{\mathbf{Y}}_{i}(t)\,(\mathbf{X}_{i}(t)-\mathbf{P}_{i})]=\operatorname{tr}[\mathbf{V}_{i}(\mathbf{X}(t))\,(\mathbf{X}(t)-\mathbf{P})],$
(A.12)

where, in the last line, we used Proposition A.1. ∎

The last result we will need is a “reciprocity” property in the spirit of [31]
which shows that the convergence topology induced by $F$ on
$\boldsymbol{\mathcal{X}}$ is compatible with the ordinary one. While this
property is relatively easy to establish in linear polytopes with decomposable
regularizers, the matrix setting complicates things considerably.

######  Proposition A.2.

Let $\mathbf{Y}_{n}$, $n=1,2,\dotsc$, be a sequence in
$\boldsymbol{\mathcal{Y}}$. Then $\mathbf{X}_{n}=\mathbf{Q}(\mathbf{Y}_{n})$
converges to $\mathbf{P}\in\boldsymbol{\mathcal{X}}$ if and only if
$\lim_{n\to\infty}F(\mathbf{P},\mathbf{Y}_{n})=0$.

###### Proof.

We begin by showing the direct implication “$\implies$”. Indeed, assuming that
$\mathbf{X}_{n}\to\mathbf{P}$, the definition of $F$ gives

$\displaystyle F(\mathbf{P},\mathbf{X}_{n})$
$\displaystyle=h(\mathbf{P})+h^{\ast}(\mathbf{Y}_{n})-\operatorname{tr}[\mathbf{Y}_{n}\mathbf{P}]$
$\displaystyle=h(\mathbf{P})-h(\mathbf{X}_{n})+\operatorname{tr}[\mathbf{Y}_{n}\,(\mathbf{X}_{n}-\mathbf{P})]$
$\displaystyle=h(\mathbf{P})-h(\mathbf{X}_{n})+\operatorname{tr}[\theta^{\prime}(\mathbf{X}_{n})(\mathbf{X}_{n}-\mathbf{P})]$
(A.13)

where, in the last equality, we used the first part of Lemma A.2. Since
$\mathbf{X}_{n}\to\mathbf{P}$, the term $h(\mathbf{P})-h(\mathbf{X}_{n})$
vanishes as $n\to\infty$, so it suffices to show the same for the second term
as well. To that end, if we let
$\mathbf{X}_{n}=\sum_{\alpha}x_{\alpha,n}\mathbf{u}_{\alpha,n}\mathbf{u}_{\alpha,n}^{{\dagger}}$
be an eigen-decomposition of $\mathbf{X}_{n}$ and we set
$p_{\alpha,n}=\mathbf{u}_{\alpha,n}^{{\dagger}}\mathbf{P}\mathbf{u}_{\alpha,n}$
and $p_{\alpha}=\lim_{n\to\infty}p_{\alpha,n}$ (the limit exists because
$\mathbf{X}_{n}$ converges to $\mathbf{P}$ by assumption), we readily get

$\displaystyle\operatorname{tr}[\theta^{\prime}(\mathbf{X}_{n})(\mathbf{X}_{n}-\mathbf{P})]$
$\displaystyle=\sum_{\alpha=1}^{d}\theta^{\prime}(x_{\alpha,n})(x_{\alpha,n}-p_{\alpha,n})$
$\displaystyle=\sum_{\alpha\in\operatorname{supp}(p)}\theta^{\prime}(x_{\alpha,n})(x_{\alpha,n}-p_{\alpha,n})+\sum_{\alpha:p_{\alpha}=0}\theta^{\prime}(x_{\alpha,n})(x_{\alpha,n}-p_{\alpha,n})$
(A.14)

Since $\mathbf{X}_{n}$ converges to $\mathbf{P}$ the first sum above vanishes:
this is because $\lim_{n\to\infty}x_{\alpha,n}>0$, so
$\theta^{\prime}(x_{\alpha,n})$ has a finite limit for all
$\alpha\in\operatorname{supp}(p)$. As for the second, since
$x_{\alpha,n}-p_{\alpha,n}\leq x_{\alpha,n}$, it suffices to show that
$z\theta^{\prime}(z)\to 0$ as $z\to 0^{+}$; we prove that this is so in Lemma
A.3 below, for $f=\theta^{\prime}$.

Finally, as for the converse implication “$\Longleftarrow$”, our assertion
follows immediately from the first part of Proposition A.1. ∎

######  Lemma A.3.

Let $f:(0,1]\to\mathbb{R}$ be differentiable such that (i) $\lim_{x\to
0^{+}}f(x)=-\infty$, (ii) $\inf_{x\in(0,1]}f^{\prime}(x)>0$, and (iii)
$\int_{0}^{1}\lvert f(x)\rvert\>dx<\infty$. Then, $\lim_{x\to 0^{+}}xf(x)=0$.

###### Proof.

For convenience, let $g=-f$. Then, we readily get (i) $\lim_{x\to
0^{+}}g(x)=+\infty$, (ii) $\inf_{x\in(0,1]}g^{\prime}(x)<0$, and (iii)
$\int_{0}^{1}\lvert g(x)\rvert\>dx<\infty$. Since
$\inf_{x\in(0,1]}g^{\prime}(x)<0$, we get that $g$ is strictly decreasing.
Now, $\lim_{x\to 0^{+}}g(x)=+\infty$ implies that $g$ is strictly positive
close to $0$, i.e., $g(x)>0$ in $(0,c)$ for some $c>0$. Let
$\varepsilon\in(0,c)$. Since $g$ is decreasing and positive in $(0,c)$, we
have:

$0\leq\varepsilon g(\varepsilon)\leq\int_{0}^{\varepsilon}g(x)\>dx$ (A.15)

We will now show that $\lim_{\varepsilon\to
0^{+}}\int_{0}^{\varepsilon}g(x)\>dx=0$. For this, we can write
$\int_{0}^{\varepsilon}g(x)\>dx$ as:

$\int_{0}^{\varepsilon}g(x)\>dx=\int\operatorname{\mathds{1}}_{(0,\varepsilon)}g(x)\>dx$
(A.16)

where $\operatorname{\mathds{1}}_{A}(x)=1$ if $x\in A$ and $0$, otherwise. Let
$\\{\varepsilon_{n}\\}_{n\in\mathbb{N}}$ be a sequence of positive reals with
$\varepsilon_{n}\to 0$ as $n\to\infty$. Then, it holds:

$\operatorname{\mathds{1}}_{(0,\varepsilon_{n})}g(x)\xrightarrow{n\to\infty}0\quad\text{for
all }x\in(0,1]$ (A.17)

since, for fixed $x\in(0,1]$, we have that $\varepsilon_{n}<x$ for all $n$
large enough, which implies that
$\operatorname{\mathds{1}}_{(0,\varepsilon_{n})}g(x)=0$. Moreover, for all
$x\in(0,1]$, it holds:

$\lvert\operatorname{\mathds{1}}_{(0,\varepsilon_{n})}g(x)\rvert\leq\lvert
g(x)\rvert$ (A.18)

with $\int_{0}^{1}\lvert g(x)\rvert\>dx<\infty$. Hence, by the dominated
convergence theorem [18], we get that:

$\lim_{n\to\infty}\int_{0}^{1}\operatorname{\mathds{1}}_{(0,\varepsilon_{n})}g(x)\>dx=0$
(A.19)

and, since $\\{\varepsilon_{n}\\}_{n\in\mathbb{N}}$ was arbitrary, we conclude
that $\lim_{\varepsilon\to 0^{+}}\int_{0}^{\varepsilon}g(x)\>dx=0$. Hence,
combining it with (A.15), we get that $\lim_{x\to 0^{+}}xg(x)=0$, i.e.,
$\lim_{x\to 0^{+}}xf(x)=0$. ∎

##  Appendix B General properties of the dynamics

See 1

###### Proof.

First of all, according to the dynamics described in Section 3,
$\mathbf{X}(t)$ is obtained as a regularized best-response, i.e., a solution
of the maximization problem:

$\mathbf{Q}(\mathbf{Y})=\operatorname*{arg\,max}\nolimits_{\mathbf{X}^{\prime}\in\boldsymbol{\mathcal{X}}}\\{\operatorname{tr}[\mathbf{Y}\mathbf{X}^{\prime}]-\operatorname{tr}[\theta(\mathbf{X}^{\prime})]\\}.$
(B.1)

Letting
$\mathbf{X}(t)=\sum_{\alpha=1}^{d}x_{\alpha}(t)\,\mathbf{u}_{\alpha}(t)\mathbf{u}_{\alpha}^{{\dagger}}(t)$
be an eigendecomposition of $\mathbf{X}(t)$, since $h$ is steep, we readily
obtain that $\mathbf{X}(t)\in\operatorname{ri}{\boldsymbol{\mathcal{X}}}$,
which implies that $x_{\alpha}(t)>0$ for all $\alpha$. Since
$\inf_{x\in(0,1]}\theta^{\prime\prime}(x)>0$, the function $x\mapsto\theta(x)$
is strictly convex, and so is
$\mathbf{X}\mapsto\operatorname{tr}[\theta(\mathbf{X})]$, see [6, Theorem
2.10]. Hence, (B.1) has a unique solution in $\boldsymbol{\mathcal{X}}$.

By the KKT conditions, the dual variables associated with the positive semi-
definiteness constraints, $x_{\alpha}(t)\geq 0$ for $\alpha=1,\dots,d$, are
equal to zero in the optimal solution, since the inequalities are strict, as
argued before. Hence, it is enough to consider the “reduced” Lagrangian:

$\mathcal{L}(\mathbf{X};\lambda)=\operatorname{tr}[\mathbf{Y}\mathbf{X}]-\operatorname{tr}[\theta(\mathbf{X})]-\lambda(\operatorname{tr}[\mathbf{X}]-1)$
(B.2)

where $\lambda\in\mathbb{R}$ is the dual variable associated with the
constraint $\operatorname{tr}[\mathbf{X}]=1$. Then, differentiating
$\mathcal{L}$ with respect to $\mathbf{X}^{\top}$, the solutions need to
satisfy
$\nabla_{\mathbf{X}^{\top}}\mathcal{L}(\mathbf{X};\lambda)=\mathbf{Y}-\theta^{\prime}(\mathbf{X})-\lambda\mathbf{I}=0$,
i.e.,

$\theta^{\prime}(\mathbf{X})=\mathbf{Y}-\lambda\mathbf{I}$ (B.3)

where we used that
$\nabla_{\mathbf{X}^{\top}}\operatorname{tr}[\theta(\mathbf{X})]=\theta^{\prime}(\mathbf{X})$,
see [34]. Differentiating (B.3) with respect to $t$, and invoking that
$\dot{\mathbf{Y}}=\mathbf{V}$, we obtain:

$\displaystyle\frac{d}{dt}\theta^{\prime}(\mathbf{X})$
$\displaystyle=\dot{\mathbf{Y}}-\dot{\lambda}\mathbf{I}$
$\displaystyle=\mathbf{V}-\dot{\lambda}\mathbf{I}$ (B.4)

Writing $\theta^{\prime}(\mathbf{X})$ in the same eigenbasis as $\mathbf{X}$,
i.e.,
$\theta^{\prime}(\mathbf{X})=\sum_{\alpha=1}^{d}\theta^{\prime}(x_{\alpha})\mathbf{u}_{\alpha}\mathbf{u}_{\alpha}^{{\dagger}}$,
the above equation becomes:

$\displaystyle\sum_{k=1}^{d}\theta^{\prime\prime}(x_{k})\dot{x}_{k}\mathbf{u}_{k}\mathbf{u}_{k}^{{\dagger}}+\sum_{k=1}^{d}\theta^{\prime}(x_{k})\dot{\mathbf{u}}_{k}\mathbf{u}_{k}^{{\dagger}}+\sum_{k=1}^{d}\theta^{\prime}(x_{k})\mathbf{u}_{k}\dot{\mathbf{u}}_{k}^{{\dagger}}=\mathbf{V}-\dot{\lambda}\mathbf{I}$
(B.5)

Applying $\mathbf{u}_{\alpha}^{{\dagger}}$ on the left and
$\mathbf{u}_{\beta}$ on the right of (B.5), we obtain:

$\sum_{k=1}^{d}\theta^{\prime\prime}(x_{k})\dot{x}_{k}\mathbf{u}_{\alpha}^{{\dagger}}\mathbf{u}_{k}\mathbf{u}_{k}^{{\dagger}}\mathbf{u}_{\beta}+\sum_{k=1}^{d}\theta^{\prime}(x_{k})\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{u}}_{k}\mathbf{u}_{k}^{{\dagger}}\mathbf{u}_{\beta}+\sum_{k=1}^{d}\theta^{\prime}(x_{k})\mathbf{u}_{\alpha}^{{\dagger}}\mathbf{u}_{k}\dot{\mathbf{u}}_{k}^{{\dagger}}\mathbf{u}_{\beta}=\mathbf{u}_{\alpha}^{{\dagger}}\mathbf{V}\mathbf{u}_{\beta}-\dot{\lambda}\mathbf{u}_{\alpha}^{{\dagger}}\mathbf{u}_{\beta}$
(B.6)

and using that $\mathbf{u}_{k}^{{\dagger}}\mathbf{u}_{\ell}=\delta_{k\ell}$,
the above relation becomes:

$\theta^{\prime\prime}(x_{\alpha})\dot{x}_{\alpha}\delta_{\alpha\beta}+\theta^{\prime}(x_{\beta})\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{u}}_{\beta}+\theta^{\prime}(x_{\alpha})\dot{\mathbf{u}}_{\alpha}^{{\dagger}}\mathbf{u}_{\beta}=\mathbf{V}_{\alpha\beta}-\dot{\lambda}\delta_{\alpha\beta}$
(B.7)

Now, we observe that since
$\mathbf{u}_{\alpha}^{{\dagger}}\mathbf{u}_{\beta}=\delta_{\alpha\beta}$,
differentiating it with respect to $t$, we get:

$\dot{\mathbf{u}}_{\alpha}^{{\dagger}}\mathbf{u}_{\beta}+\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{u}}_{\beta}=0$
(B.8)

and, hence, (B.7) becomes:

$\theta^{\prime\prime}(x_{\alpha})\dot{x}_{\alpha}\delta_{\alpha\beta}+(\theta^{\prime}(x_{\beta})-\theta^{\prime}(x_{\alpha}))\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{u}}_{\beta}=\mathbf{V}_{\alpha\beta}-\dot{\lambda}\delta_{\alpha\beta}$
(B.9)

With the above equation in hand, we proceed to the final steps of the proof.
Following the same procedure as before, the $\alpha\beta$-entry of
$\dot{\mathbf{X}}$, can be written as:

$[\dot{\mathbf{X}}]_{\alpha\beta}=\dot{x}_{\alpha}\delta_{\alpha\beta}+(x_{\beta}-x_{\alpha})\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{u}}_{\beta}$
(B.10)

  1. (1)

For $\alpha=\beta$, equation (B.10) gives:

$[\dot{\mathbf{X}}]_{\alpha\alpha}=\dot{x}_{\alpha}$ (B.11)

and, equation (B.9) becomes:

$\theta^{\prime\prime}(x_{\alpha})\dot{x}_{\alpha}=\mathbf{V}_{\alpha\alpha}-\dot{\lambda}$
(B.12)

Since $x_{\alpha}>0$, by the hypothesis on $\theta$, we have
$\theta^{\prime\prime}(x_{\alpha})>0$, and therefore:

$\dot{x}_{\alpha}=\frac{\mathbf{V}_{\alpha\alpha}}{\theta^{\prime\prime}(x_{\alpha})}-\frac{\dot{\lambda}}{\theta^{\prime\prime}(x_{\alpha})}$
(B.13)

Summing the above for $\beta=1,\dots,d$, and using the fact that
$\sum_{\beta=1}^{d}\dot{x}_{\beta}=0$ (since $\sum_{\beta=1}^{d}x_{\beta}=1$),
we obtain:

$\dot{\lambda}=\frac{\sum_{\beta=1}^{d}V_{\beta\beta}/\theta^{\prime\prime}(x_{\beta})}{\sum_{\beta=1}^{d}1/\theta^{\prime\prime}(x_{\beta})}$
(B.14)

Hence, combining (B.14) with (B.11) and (B.13), we obtain:

$[\dot{\mathbf{X}}]_{\alpha\alpha}=\frac{V_{\alpha\alpha}}{\theta^{\prime\prime}(x_{\alpha})}-\frac{\sum_{\beta}V_{\beta\beta}/\theta^{\prime\prime}(x_{\beta})}{\sum_{\beta}\theta^{\prime\prime}(x_{\alpha})/\theta^{\prime\prime}(x_{\beta})}$
(B.15)

  2. (2)

For $\alpha=\beta$, equation (B.10) gives:

$[\dot{\mathbf{X}}]_{\alpha\beta}=(x_{\beta}-x_{\alpha})\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{u}}_{\beta}$
(B.16)

and, equation (B.9) becomes:

$(\theta^{\prime}(x_{\beta})-\theta^{\prime}(x_{\alpha}))\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{u}}_{\beta}=\mathbf{V}_{\alpha\beta}$
(B.17)

Expressing $\dot{\mathbf{u}}_{\beta}$ in the basis
$\mathbf{u}_{1},\dots,\mathbf{u}_{d}$, we write it as
$\dot{\mathbf{u}}_{\beta}=\sum_{k=1}^{d}B_{\beta k}\mathbf{u}_{k}$ with the
coefficients $B_{\beta k}$’s to be determined. Hence, (B.17) can be written
as:

$(\theta^{\prime}(x_{\beta})-\theta^{\prime}(x_{\alpha}))\sum_{k=1}^{d}B_{\beta
k}\mathbf{u}_{\alpha}^{{\dagger}}\mathbf{u}_{k}=\mathbf{V}_{\alpha\beta}$
(B.18)

and, since $\mathbf{u}_{k}^{{\dagger}}\mathbf{u}_{\ell}=\delta_{k\ell}$, we
readily get:

$(\theta^{\prime}(x_{\beta})-\theta^{\prime}(x_{\alpha}))B_{\beta\alpha}=\mathbf{V}_{\alpha\beta}$
(B.19)

or, equivalently:

$B_{\beta\alpha}=\frac{\mathbf{V}_{\alpha\beta}}{\theta^{\prime}(x_{\beta})-\theta^{\prime}(x_{\alpha})}$
(B.20)

Now, it is easy to see that
$\mathbf{u}_{\alpha}^{{\dagger}}\dot{\mathbf{u}}_{\beta}=B_{\beta\alpha}$.
Therefore, combining it with (B.16) and (B.20), we conclude that:

$\displaystyle[\dot{\mathbf{X}}]_{\alpha\beta}=\frac{x_{\beta}-x_{\alpha}}{\theta^{\prime}(x_{\beta})-\theta^{\prime}(x_{\alpha})}\mathbf{V}_{\alpha\beta}$
(B.21)

This concludes the proof. ∎

######  Proposition B.1.

The quantum replicator dynamics (QRD) can be written in the form:

$\dot{\mathbf{X}}=\int_{0}^{1}\mathbf{X}^{1-s}\mathbf{V}(\mathbf{X})\mathbf{X}^{s}\>ds-\operatorname{tr}[\mathbf{X}\mathbf{V}(\mathbf{X})]\mathbf{X}$
(B.22)

###### Proof.

In the case of the von Neumann regularizer, we ontain the replicator dynamics:

$\dot{\mathbf{Y}}=\mathbf{V}(\mathbf{X})\qquad\mathbf{X}=\frac{\exp(\mathbf{Y})}{\operatorname{tr}[\exp(\mathbf{Y})]}$
(B.23)

Hence, differentiating with respect to $t$ and using the chain rule, we
obtain:

$\displaystyle\dot{\mathbf{X}}$
$\displaystyle=\frac{1}{\operatorname{tr}[\exp(\mathbf{Y})]}\frac{d}{dt}\exp(\mathbf{Y})+\exp(\mathbf{Y})\frac{d}{dt}\frac{1}{\operatorname{tr}[\exp(\mathbf{Y})]}$
$\displaystyle=\frac{1}{\operatorname{tr}[\exp(\mathbf{Y})]}\frac{d}{dt}\exp(\mathbf{Y})-\frac{\exp(\mathbf{Y})}{\operatorname{tr}[\exp(\mathbf{Y})]^{2}}\frac{d}{dt}\operatorname{tr}[\exp(\mathbf{Y})]$
$\displaystyle=\frac{1}{\operatorname{tr}[\exp(\mathbf{Y})]}\frac{d}{dt}\exp(\mathbf{Y})-\frac{\exp(\mathbf{Y})}{\operatorname{tr}[\exp(\mathbf{Y})]^{2}}\operatorname{tr}\left[\frac{d}{dt}\exp(\mathbf{Y})\right]$
(B.24)

By the Fréchet derivative [49], it holds:

$\displaystyle\frac{d}{dt}\exp(\mathbf{Y})$
$\displaystyle=\int_{0}^{1}e^{(1-s)\mathbf{Y}}\dot{\mathbf{Y}}e^{s\mathbf{Y}}\>ds$
$\displaystyle=\int_{0}^{1}e^{(1-s)\mathbf{Y}}\mathbf{V}(\mathbf{X})e^{s\mathbf{Y}}\>ds$
$\displaystyle=\operatorname{tr}[\exp(\mathbf{Y})]\int_{0}^{1}\mathbf{X}^{1-s}\mathbf{V}(\mathbf{X})\mathbf{X}^{s}\>ds$
(B.25)

and, using (B) in (B), we get:

(B.26)

as asserted. ∎

##  Appendix C Regret minimization

Our aim in this appendix is to prove that the dynamics (FTQL) incur at most
constant regret. For convenience, we restate the relevant result below.

See 1

Our proof essentially follows the analysis of [25]; the specialization of the
proof occurs in deriving the exact value of the regret bound (14) but, for
completeness, we provide the entire proof.

###### Proof.

Let $\mathbf{P}_{i}\in\boldsymbol{\mathcal{X}}$ be a best fixed action in
hindsight, i.e.,:

$\mathbf{P}_{i}\in\operatorname*{arg\,max}_{\mathbf{X}^{\prime}_{i}\in\boldsymbol{\mathcal{X}}_{i}}\int_{0}^{T}u_{i}(\mathbf{X}^{\prime}_{i};\mathbf{X}_{-i}(t))\>dt$
(C.1)

and define the function $E_{i}(t)\coloneqq
F_{i}(\mathbf{P}_{i},\mathbf{Y}_{i}(t))$ for $t\geq 0$. By Lemma 1, we have
that:

$\displaystyle\frac{d}{dt}E_{i}(t)=\operatorname{tr}[\mathbf{V}_{i}(\mathbf{X}(t))(\mathbf{X}_{i}(t)-\mathbf{P}_{i})]=u_{i}(\mathbf{X}(t))-u_{i}(\mathbf{P}_{i};\mathbf{X}_{-i}(t))$
(C.2)

Integrating over time, and combining (8) with (C.1), we obtain:

$\displaystyle\operatorname{Reg}_{i}(T)$ $\displaystyle=E_{i}(0)-E_{i}(T)$
$\displaystyle=h^{\ast}_{i}(\mathbf{Y}_{i}(0))-\operatorname{tr}[\mathbf{P}_{i}\mathbf{Y}_{i}(0)]-h^{\ast}_{i}(\mathbf{Y}_{i}(T))+\operatorname{tr}[\mathbf{P}_{i}\mathbf{Y}_{i}(T)]$
$\displaystyle\leq
h^{\ast}_{i}(\mathbf{Y}_{i}(0))-\operatorname{tr}[\mathbf{P}_{i}\mathbf{Y}_{i}(0)]+h_{i}(\mathbf{P}_{i})$
$\displaystyle=h_{i}(\mathbf{P}_{i})-h_{i}(\mathbf{Q}_{i}(\mathbf{Y}_{i}(0)))$
$\displaystyle=\operatorname{tr}[\theta_{i}(\mathbf{P}_{i})]-\operatorname{tr}[\theta_{i}(\mathbf{Q}_{i}(\mathbf{Y}_{i}(0)))]$
$\displaystyle\leq\max_{\mathbf{X}^{\prime}_{i}\in\boldsymbol{\mathcal{X}}_{i}}\operatorname{tr}[\theta_{i}(\mathbf{X}^{\prime}_{i})]-\min_{\mathbf{X}^{\prime}_{i}\in\boldsymbol{\mathcal{X}}_{i}}\operatorname{tr}[\theta_{i}(\mathbf{X}^{\prime}_{i})]$
(C.3)

where we used the fact that

$\displaystyle
h^{\ast}_{i}(\mathbf{Y}_{i})=\max\nolimits_{\mathbf{X}^{\prime}_{i}\in\boldsymbol{\mathcal{X}}_{i}}\\{\operatorname{tr}[\mathbf{X}^{\prime}_{i}\mathbf{Y}_{i}]-h_{i}(\mathbf{X}^{\prime}_{i})\\}\geq\operatorname{tr}[\mathbf{P}_{i}\mathbf{Y}_{i}]-h_{i}(\mathbf{P}_{i})$
(C.4)

with equality if and only if
$\mathbf{X}^{\prime}_{i}=\mathbf{Q}_{i}(\mathbf{Y}_{i})$. The precise bound
(14) then follows by noting that the maximum difference in the values of $h$
is attained between the barycenter of the spectraplex and any pure density
matrix of rank $1$, which thus hields the bound

$\max h_{i}-\min h_{i}=\lvert
d_{i}\cdot\theta_{i}(1/d_{i})-\theta_{i}(1)\rvert,$ (C.5)

and our assertion follows. ∎

##  Appendix D The folk theorem

In this appendix, our aim is to prove Theorem 2. To lay the necessary
groundwork, we begin with a series of helper lemmas. The first is related to
the verification parts of Theorem 2, and concerns the behavior of the dynamics
near its trapping regions.

######  Lemma D.1.

Fix some $\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$, and assume that every
neighborhood $\boldsymbol{\mathcal{U}}$ of $\mathbf{X}^{\ast}$ in
$\boldsymbol{\mathcal{X}}$ admits a solution trajectory
$\mathbf{X}(t)=\mathbf{Q}(\mathbf{Y}(t))$ of (FTQL) such that
$\mathbf{X}(t)\in\boldsymbol{\mathcal{U}}$ for all $t\geq 0$. Then
$\mathbf{X}^{\ast}$ is a Nash equilibrium.

###### Proof.

We argue by contradiction. Indeed, if $\mathbf{X}^{\ast}$ is not Nash, then,
by the variational characterization (VI) of Nash equilibria, there exists some
deviation $\mathbf{P}\in\boldsymbol{\mathcal{X}}$ such that
$\operatorname{tr}[\mathbf{V}(\mathbf{X}^{\ast})\,(\mathbf{P}-\mathbf{X}^{\ast})]>0$.
Then, by continuity, there exists a sufficiently small compact neighborhood
$\boldsymbol{\mathcal{C}}$ of $\mathbf{X}^{\ast}$ in
$\boldsymbol{\mathcal{X}}$ such that
$\operatorname{tr}[\mathbf{V}(\mathbf{X})\,(\mathbf{P}-\mathbf{X})]>0$ for all
$\mathbf{X}\in\boldsymbol{\mathcal{C}}$, implying in turn that
$c\coloneqq\inf_{\mathbf{X}\in\boldsymbol{\mathcal{C}}}\operatorname{tr}[\mathbf{V}(\mathbf{X})\,(\mathbf{P}-\mathbf{X})]>0$,
Now, by assumption, there exists a solution orbit
$\mathbf{X}(t)=\mathbf{Q}(\mathbf{Y}(t))$ of (FTQL) such that
$\mathbf{X}(t)\in\boldsymbol{\mathcal{U}}$ for all $t\geq 0$ so, by Lemma 1,
we readily obtain

$\frac{d}{dt}F(\mathbf{P},\mathbf{Y}(t))=\operatorname{tr}[\mathbf{V}(\mathbf{X}(t))\,(\mathbf{X}(t)-\mathbf{P})]\leq-c<0\quad\text{for
all $t\geq 0$}.$ (D.1)

A simple integration then yields $F(\mathbf{P},\mathbf{Y}(t))\to-\infty$ as
$t\to\infty$, a contradiction that proves our claim. ∎

The second intermediate result we will need is a uniform convergence lemma for
states that are consistently asymptotically stable:

######  Lemma D.2.

Suppose that $\mathbf{X}^{\ast}\in\operatorname{ri}\boldsymbol{\mathcal{X}}$
is consistently asymptotically stable under (FTQL). Then, for every
sufficiently small compact neighborhood $\boldsymbol{\mathcal{U}}$ of
$\mathbf{X}^{\ast}$ in $\operatorname{ri}\boldsymbol{\mathcal{X}}$, we have

$\lim_{t\to\infty}\sup_{\mathbf{X}\in\boldsymbol{\mathcal{U}}}\lVert\boldsymbol{\chi}_{#1}(\mathbf{X})-\mathbf{X}^{\ast}\rVert=0.$
(D.2)

###### Proof.

First of all, since
$\mathbf{X}^{\ast}\in\operatorname{ri}\boldsymbol{\mathcal{X}}$, we have that
$\ker(\mathbf{X}^{\ast})=\\{0\\}$, which implies that
$\boldsymbol{\mathcal{X}}_{\mathbf{X}^{\ast}}=\operatorname{ri}\boldsymbol{\mathcal{X}}$.
Hence, for any open set $O$ in $\operatorname{ri}\boldsymbol{\mathcal{X}}$, it
holds that $O\cap\boldsymbol{\mathcal{X}}_{\mathbf{X}^{\ast}}=O$. Now, let
$\boldsymbol{\mathcal{U}}_{0}$ be the basin of attraction of
$\mathbf{X}^{\ast}$, according to the definition of the consistent asymptotic
stability in Definition 1, and let
$\boldsymbol{\mathcal{U}}\subseteq\boldsymbol{\mathcal{U}}_{0}$ be a compact
neighborhood of $\mathbf{X}^{\ast}$. Suppose, for the sake of contradiction,
that
$\sup_{\mathbf{X}\in\boldsymbol{\mathcal{U}}}\lVert\boldsymbol{\chi}_{#1}(\mathbf{X})-\mathbf{X}^{\ast}\rVert\not\to
0$. This implies that there exists $\varepsilon>0$, a sequence
$\\{t_{n}\\}_{n\in\mathbb{N}}$ with $t_{n}\to\infty$ as $n\to\infty$, and
$\mathbf{X}_{n}\in\boldsymbol{\mathcal{U}}$ for $n\in\mathbb{N}$, such that

$\lVert\boldsymbol{\chi}_{#1}(\mathbf{X}_{n})-\mathbf{X}^{\ast}\rVert\geq\varepsilon\quad\text{for
all }n\in\mathbb{N}$ (D.3)

Since $\boldsymbol{\mathcal{U}}$ is compact, we may assume (by taking
subsequences, if necessary) that $\mathbf{X}_{n}$ converges to some limit
point $\mathbf{X}_{\infty}\in\boldsymbol{\mathcal{U}}$. Now, since
$\mathbf{X}^{\ast}$ is Lyapunov stable, there exists a neighborhood
$\boldsymbol{\mathcal{U}}^{\prime}$ of $\mathbf{X}^{\ast}$, such that the
trajectory $\boldsymbol{\chi}_{#1}(\mathbf{X})$ remains within
$\varepsilon/2$-distance of $\mathbf{X}^{\ast}$, if
$\mathbf{X}\in\boldsymbol{\mathcal{U}}^{\prime}$, or, equivalently:

$\lVert\boldsymbol{\chi}_{#1}(\mathbf{X})-\mathbf{X}^{\ast}\rVert<\frac{\varepsilon}{2}\quad\text{for
all }t\geq 0\text{ and }\mathbf{X}\in\boldsymbol{\mathcal{U}}^{\prime}$ (D.4)

Define the hitting time $\tau\coloneqq\inf\\{t\geq
0:\boldsymbol{\chi}_{#1}(\mathbf{X}_{\infty})\in\boldsymbol{\mathcal{U}}^{\prime}\\}$,
as the first time that the trajectory enters
$\boldsymbol{\mathcal{U}}^{\prime}$ when starting from $\mathbf{X}_{\infty}$.
It is easy to see that $\tau<\infty$, since
$\mathbf{X}_{\infty}\in\boldsymbol{\mathcal{U}}\subseteq\boldsymbol{\mathcal{U}}_{0}$,
and, thus,
$\lVert\boldsymbol{\chi}_{#1}(\mathbf{X}_{\infty})-\mathbf{X}^{\ast}\rVert\to
0$ as $t\to\infty$ by the asymptotic stability of $\mathbf{X}^{\ast}$.

By continuity of $\boldsymbol{\chi}$, we readily get that there exists a
neighborhood $\mathcal{D}$ of $\mathbf{X}_{\infty}$ such that
$\boldsymbol{\chi}_{#1}(\mathcal{D})\subseteq\mathcal{U}^{\prime\prime}$,
where $\mathcal{U}^{\prime\prime}$ is a neighborhood of $\mathbf{X}^{\ast}$
with
$\lVert\boldsymbol{\chi}_{#1}(\mathbf{X})-\mathbf{X}^{\ast}\rVert<\varepsilon$
for all $t\geq 0$ and $\mathbf{X}\in\mathcal{U}^{\prime\prime}$.

Since $\mathbf{X}_{n}\to\mathbf{X}_{\infty}$, we conclude that
$\mathbf{X}_{n}\in\mathcal{D}$ for all sufficiently large $n$, which, in turn,
implies that
$\boldsymbol{\chi}_{#1}(\mathbf{X}_{n})\in\mathcal{U}^{\prime\prime}$.
Moreover, by definition of the sequence $\\{t_{n}\\}_{n\in\mathbb{N}}$, we
have that $t_{n}\to\infty$, which gives that $t_{n}>\tau$ for $n$ sufficiently
large, since $\tau<\infty$, as argued before.

Therefore, for all $n$ sufficiently large, we have
$\lVert\boldsymbol{\chi}_{#1}(\mathbf{X}_{n})-\mathbf{X}^{\ast}\rVert<\varepsilon$,
which contradicts (D.3). ∎

Our last step before proving Theorem 2 is a comparison between the notions of
Lyapunov stability induced by the flow $\boldsymbol{\psi}$ on
$\boldsymbol{\mathcal{X}}$ via $\mathbf{Q}$, and the corresponding notion
relative to the conjugate flow $\boldsymbol{\chi}$ on
$\boldsymbol{\mathcal{X}}$. Formally, we have the following definition.

######  Definition 3.

We say that $\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$ is:

  1. (1)

$\boldsymbol{\chi}$-stable, if for all neighborhoods
$\boldsymbol{\mathcal{U}}$ of $\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$,
there exists a neighborhood $\boldsymbol{\mathcal{U}}^{\prime}$ of
$\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$, such that
$\boldsymbol{\chi}_{#1}(\mathbf{X})\in\boldsymbol{\mathcal{U}}$ for all
$\mathbf{X}\in\boldsymbol{\mathcal{U}}^{\prime}$ and all $t\geq 0$.

  2. (2)

$\boldsymbol{\psi}$-stable, if for all neighborhoods
$\boldsymbol{\mathcal{U}}$ of $\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$,
there exists a neighborhood $\boldsymbol{\mathcal{U}}^{\prime}$ of
$\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$, such that
$\boldsymbol{\chi}_{#1}(\mathbf{X})\in\boldsymbol{\mathcal{U}}$ for all
$\mathbf{X}\in\boldsymbol{\mathcal{U}}^{\prime}\cap\operatorname{im}\mathbf{Q}$
and all $t\geq 0$.

######  Lemma D.3.

A point $\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$ is
$\boldsymbol{\chi}$-stable if and only if it is $\boldsymbol{\psi}$-stable.

###### Proof.

The “only if” part is trivial, so we focus on the “if” part. To that end,
suppose that $\mathbf{X}^{\ast}$ is $\boldsymbol{\psi}$-stable but not
$\boldsymbol{\chi}$-stable. Then, there exists a neighborhood
$\boldsymbol{\mathcal{U}}$ of $\mathbf{X}^{\ast}$ in
$\boldsymbol{\mathcal{X}}$ such that for all neighborhoods
$\boldsymbol{\mathcal{U}}^{\prime}$ of $\mathbf{X}^{\ast}$, there exists
$\mathbf{X}\in\boldsymbol{\mathcal{U}}^{\prime}$ such that
$\boldsymbol{\chi}_{#1}(\mathbf{X})\not\in\mathcal{U}$ for some $t\geq 0$.
Now, let $\boldsymbol{\mathcal{U}}_{0}$ be a neighborhood of
$\mathbf{X}^{\ast}$ such that
$\operatorname{cl}(\boldsymbol{\mathcal{U}}_{0})\subseteq\boldsymbol{\mathcal{U}}$.
Then, by $\boldsymbol{\psi}$-stability of $\mathbf{X}^{\ast}$, there exists a
neighborhood $\boldsymbol{\mathcal{U}}_{0}^{\prime}$ of $\mathbf{X}^{\ast}$
such that $\boldsymbol{\chi}_{#1}(\mathbf{X})\in\boldsymbol{\mathcal{U}}_{0}$
for all
$\mathbf{X}\in\boldsymbol{\mathcal{U}}_{0}^{\prime}\cap\operatorname{im}\mathbf{Q}$
and all $t\geq 0$. But, since $\mathbf{X}^{\ast}$ is not
$\boldsymbol{\chi}$-stable, there exists
$\mathbf{X}\in\boldsymbol{\mathcal{U}}_{0}^{\prime}\cap(\operatorname{im}\mathbf{Q})^{c}$
such that the hitting time $\tau=\inf\\{t\geq
0:\boldsymbol{\chi}_{#1}(\mathbf{X})\not\in\boldsymbol{\mathcal{U}}\\}$ is
finite. Moreover, let
$\\{\mathbf{X}_{n}\\}_{n\in\mathbb{N}}\subseteq\boldsymbol{\mathcal{U}}_{0}^{\prime}\cap\operatorname{im}\mathbf{Q}$
be a sequence converging to $\mathbf{X}$ (such a sequence exists, because
$\operatorname{cl}(\operatorname{im}\mathbf{Q})=\boldsymbol{\mathcal{X}}$).
Since $\mathbf{X}^{\ast}$ is $\boldsymbol{\psi}$-stable, it holds that
$\boldsymbol{\chi}_{#1}(\mathbf{X}_{n})\in\boldsymbol{\mathcal{U}}_{0}$ for
all $n$, and, therefore, using the continuity of $\boldsymbol{\chi}$, we get:

$\boldsymbol{\chi}_{#1}(\mathbf{X})=\lim_{n\to\infty}\boldsymbol{\chi}_{#1}(\mathbf{X}_{n})$
(D.5)

which implies that
$\boldsymbol{\chi}_{#1}(\mathbf{X})\in\operatorname{cl}(\boldsymbol{\mathcal{U}}_{0})\subseteq\boldsymbol{\mathcal{U}}$,
as a limit point of $\boldsymbol{\mathcal{U}}_{0}$. But, since
$\boldsymbol{\chi}_{#1}(\mathbf{X})\not\in\boldsymbol{\mathcal{U}}$ by
assumption, we obtain a contradiction that completes our proof. ∎

Thanks to the above proposition, we do not need to distinguish between
“Lyapunov stable” and “consistently Lyapunov stable” states, as the two
notions are equivalent. Thus, with this issue settled, we are in a position to
prove our quantum version of the “folk theorem”, which we restate for
convenience below:

See 2

We prove the various parts of the theorem below.

###### Proof of Part 1.

Suppose that $\mathbf{X}^{\ast}$ is a Nash equilibrium of $\mathcal{Q}$. If
$\operatorname{rank}(\mathbf{X}^{\ast})=1$, there is nothing to show, so it
suffices to establish our claim for the case
$\operatorname{rank}(\mathbf{X}^{\ast})>1$. In that case, by restricting the
dynamics if necessary to the relative interior of the face
$\boldsymbol{\mathcal{X}}^{\ast}=\\{\mathbf{X}\in\boldsymbol{\mathcal{X}}:\ker\mathbf{X}\geq\ker\mathbf{X}^{\ast}\\}$
of $\boldsymbol{\mathcal{X}}$ whose relative interior contains
$\mathbf{X}^{\ast}$, we may assume without loss of generality that
$\mathbf{X}^{\ast}$ has, in fact, full rank. With this in mind, fix some
$\mathbf{Y}\in\mathbf{Q}^{-1}(\mathbf{X}^{\ast})$, and consider the trajectory
$\mathbf{Y}(t)=\mathbf{Y}+t\mathbf{V}(\mathbf{X}^{\ast})$ starting at
$\mathbf{Y}$ at time $t=0$. Since
$\mathbf{V}(\mathbf{X}^{\ast})\in\operatorname{NC}(\mathbf{X}^{\ast})$ by the
variational characterization (VI) of Nash equilibria, we conclude by Lemma A.1
that $\mathbf{Q}(\mathbf{Y}(t))=\mathbf{Q}(\mathbf{Y})$ for all $t\geq 0$. In
turn, this shows that
$\dot{\mathbf{Y}}(t)=\mathbf{V}(\mathbf{X}^{\ast})=\mathbf{V}(\mathbf{Q}(\mathbf{Y}(t)))$
for all $t=0$, i.e., $\mathbf{Y}(t)$ is a solution orbit of (FTQL). By the
Picard-Lindelöf theorem, this implies that $\mathbf{Y}(t)$ is the unique
solution thereof; hence, given that
$\mathbf{X}(t)=\mathbf{Q}(\mathbf{Y}(t))=\mathbf{X}^{\ast}$ for all $t\geq 0$,
our claim follows. ∎

###### Proof of Parts 2 and 3.

Convergence to and Lyapunov stability of $\mathbf{X}^{\ast}$ both imply the
assumption of Lemma D.1, so our assertions follow immediately by the
conclusion of said lemma. ∎

###### Proof of Part 4.

The proof of this part consists of three steps. First, we will construct a
measure $\mu$ on $\operatorname{ri}\boldsymbol{\mathcal{X}}$ that is invariant
under the flow $\boldsymbol{\chi}$, i.e.,
$\mu(A)=\mu(\boldsymbol{\chi}_{#1}(A))$ for all measurable sets $A$ and $t\geq
0$, where by $\boldsymbol{\chi}_{#1}(A)$ we denote the image of $A$ after time
$t$. Next, we will show that if
$\mathbf{X}^{\ast}\in\operatorname{ri}\boldsymbol{\mathcal{X}}$, it cannot be
consistently asymptotically stable. Finally, we will conclude that if
$\mathbf{X}^{\ast}\in\boldsymbol{\mathcal{X}}$, is consistently asymptotically
stable, then it is pure with a simple reduction argument.

### Step 1.

By the definition of $\mathbf{Q}$, we have
$\mathbf{Y}=\nabla_{\mathbf{X}^{\top}}\theta(\mathbf{X})+c\cdot\mathbf{I}$,
i.e.,
$\mathbf{Q}^{-1}(\mathbf{X})=\\{\nabla_{\mathbf{X}^{\top}}\theta(\mathbf{X})+c\cdot\mathbf{I}:c\in\mathbb{R}\\}$.
Let $\boldsymbol{\mathcal{Y}}_{0}\coloneqq\boldsymbol{\mathcal{Y}}/\sim$ be
the quotient space induced by the equivalence relation $\sim$, where
$\mathbf{Y}\sim\mathbf{Y}^{\prime}$ if
$\mathbf{Y}-\mathbf{Y}^{\prime}=c\cdot\mathbf{I}$ for some $c\in\mathbb{R}$,
and let $q:\boldsymbol{\mathcal{Y}}\to\boldsymbol{\mathcal{Y}}_{0}$ be the
corresponding quotient map, defined as
$q(\mathbf{Y})=\\{\mathbf{Y}+c\cdot\mathbf{I}:c\in\mathbb{R}\\}$. Thus, by
descending to the quotient space $\boldsymbol{\mathcal{Y}}_{0}$, the mirror
map $\mathbf{Q}$ factors through $\boldsymbol{\mathcal{Y}}_{0}$ as
$\mathbf{Q}_{0}:\boldsymbol{\mathcal{Y}}_{0}\to\boldsymbol{\mathcal{X}}$
defined as $\mathbf{Q}_{0}\coloneqq\mathbf{Q}\circ q$. Now, let $\lambda$
denote the Lebesgue measure on $\boldsymbol{\mathcal{Y}}_{0}$, and let
$\mu=\mathbf{Q}_{0}\texttt{\\#}\lambda$ denote the pushforward of $\lambda$ to
$\boldsymbol{\mathcal{X}}$ via $\mathbf{Q}_{0}$, i.e.,
$\mu(A)=\lambda(\mathbf{Q}_{0}^{-1}(A))$ for all measurable sets $A$ in
$\boldsymbol{\mathcal{X}}$. Finally, by Proposition E.1, we readily get that
$\mu(\boldsymbol{\chi}_{#1}(A))=\mu(A)$ for all measurable sets
$A\subseteq\boldsymbol{\mathcal{X}}$ and all $t\geq 0$.

### Step 2.

For the sake of contradiction, suppose
$\mathbf{X}^{\ast}\in\operatorname{ri}\boldsymbol{\mathcal{X}}$ is
consistently asymptotically stable, and let $\boldsymbol{\mathcal{U}}$ be a
sufficiently small compact neighborhood of $\mathbf{X}^{\ast}$, as per Lemma
D.2. Then, it holds
$\lim_{t\to\infty}\sup_{\mathbf{X}\in\boldsymbol{\mathcal{U}}}\lVert\boldsymbol{\chi}_{#1}(\mathbf{X})-\mathbf{X}^{\ast}\rVert=0$,
which implies that:

$\lim_{t\to\infty}\mu(\boldsymbol{\chi}_{#1}(\boldsymbol{\mathcal{U}}))=\mu(\\{\mathbf{X}^{\ast}\\})=0<\mu(\boldsymbol{\mathcal{U}}).$
(D.6)

However, by _Step 1_ of the proof, we have that
$\lim_{t\to\infty}\mu(\boldsymbol{\chi}_{#1}(\boldsymbol{\mathcal{U}}))=\mu(\boldsymbol{\mathcal{U}})$,
since
$\mu(\boldsymbol{\chi}_{#1}(\boldsymbol{\mathcal{U}}))=\mu(\boldsymbol{\mathcal{U}})$
for all $t\geq 0$. Hence, combining it with (D.6), we arrive at a
contradiction.

### Step 3.

Suppose, finally, that $\mathbf{X}^{\ast}$ is consistently asymptotically
stable with $r\coloneqq\operatorname{rank}(\mathbf{X}^{\ast})>1$. Note that if
$\mathbf{X}^{\ast}$ is full-rank, it cannot be consistently asymptotically
stable, as shown at the _Step 2_ of the proof. Let
$\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}\coloneqq\\{\mathbf{X}\in\boldsymbol{\mathcal{X}}:\ker(\mathbf{X})\geq\ker(\mathbf{X}^{\ast})\\}$,
which is convex. Indeed, let
$\mathbf{X},\mathbf{X}^{\prime}\in\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}$
and $\lambda\in(0,1)$. For $y\in\ker(\mathbf{X}^{\ast})$, we have:

$\displaystyle[\lambda\mathbf{X}+(1-\lambda)\mathbf{X}^{\prime}]y$
$\displaystyle=\lambda\mathbf{X}y+(1-\lambda)\mathbf{X}^{\prime}y$
$\displaystyle=0$ (D.7)

i.e., $y\in\ker(\lambda\mathbf{X}+(1-\lambda)\mathbf{X}^{\prime})$, and, thus,
$\ker(\lambda\mathbf{X}+(1-\lambda)\mathbf{X}^{\prime})\geq\ker(\mathbf{X}^{\ast})$.

Hence, considering the restriction of the dynamics on
$\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}$, _Step 2_ of the proof shows
that a point in
$\operatorname{ri}\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}$ cannot be
consistently asymptotically stable on the induced topology. Therefore, the
restriction of $\mathbf{X}^{\ast}$ on
$\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}$, denoted
$\mathbf{X}^{\ast}\mid_{\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}}$ cannot
be consistently asymptotically stable on
$\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}$, since it has full-rank on
$\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}$. So, it remains to show that
$\mathbf{X}^{\ast}$ cannot be consistently asymptotically stable on
$\boldsymbol{\mathcal{X}}$.

For the sake of contradiction, suppose it is. Then, according to Definition 1,
there exist $\boldsymbol{\mathcal{U}}$ of $\mathbf{X}^{\ast}$ in
$\boldsymbol{\mathcal{X}}$ such that
$\lim_{t\to\infty}\boldsymbol{\chi}_{#1}(\mathbf{X})=\mathbf{X}^{\ast}$ for
all
$\mathbf{X}\in\boldsymbol{\mathcal{U}}\cap\boldsymbol{\mathcal{X}}_{\mathbf{X}^{\ast}}$.
But, since $\boldsymbol{\mathcal{U}}$ is a neighborhood of $\mathbf{X}^{\ast}$
in $\boldsymbol{\mathcal{X}}$,

$\left(\boldsymbol{\mathcal{U}}\cap\boldsymbol{\mathcal{X}}_{\mathbf{X}^{\ast}}\right)\cap\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}=\boldsymbol{\mathcal{U}}\cap\\{\mathbf{X}^{\prime}\in\boldsymbol{\mathcal{X}}:\ker(\mathbf{X}^{\prime})=\ker(\mathbf{X}^{\ast})\\}\supsetneq\\{\mathbf{X}^{\ast}\\}$
(D.8)

and, thus, the restriction of
$\boldsymbol{\mathcal{U}}\cap\\{\mathbf{X}^{\prime}\in\boldsymbol{\mathcal{X}}:\ker(\mathbf{X}^{\prime})=\ker(\mathbf{X}^{\ast})\\}$
on $\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}$ is a neighborhood of
$\mathbf{X}^{\ast}$ in $\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}$.
Therefore, by our previous argument on the induced dynamics on
$\boldsymbol{\mathcal{A}}_{\mathbf{X}^{\ast}}$, there exists
$\mathbf{X}_{0}\in\boldsymbol{\mathcal{U}}\cap\\{\mathbf{X}^{\prime}\in\boldsymbol{\mathcal{X}}:\ker(\mathbf{X}^{\prime})=\ker(\mathbf{X}^{\ast})\\}$
such that $\boldsymbol{\chi}_{#1}(\mathbf{X}_{0})\not\to\mathbf{X}^{\ast}$, as
$t\to\infty$. This contradicts our original assumption, so our proof is
complete. ∎

###### Proof of Part 5.

Suppose that $\mathbf{X}^{\ast}$ is (locally) variationally stable, i.e.,
$\operatorname{tr}[\mathbf{V}(\mathbf{X})(\mathbf{X}-\mathbf{X}^{\ast})]<0$
for all $\mathbf{X}\in\boldsymbol{\mathcal{U}}$, where
$\boldsymbol{\mathcal{U}}$ is a neighborhood of $\mathbf{X}^{\ast}$. Then, by
Lyapunov’s direct method for the energy function $E(t)\coloneqq
F(\mathbf{X}^{\ast},\mathbf{Y}(t))$, and invoking Lemma D.3, we get that
$\mathbf{X}^{\ast}$ is stable, thus, there exists neighborhood
$\boldsymbol{\mathcal{U}}^{\prime}$ of $\mathbf{X}^{\ast}$, such that
$\mathbf{X}(t)\in\boldsymbol{\mathcal{U}}$ for all $t\geq 0$, if
$\mathbf{X}(0)\in\boldsymbol{\mathcal{U}}^{\prime}$. This means that if
$\mathbf{X}(0)\in\boldsymbol{\mathcal{U}}^{\prime}$, then
$\operatorname{tr}[\mathbf{V}(\mathbf{X}(t))(\mathbf{X}(t)-\mathbf{X}^{\ast})]<0$
for all $t\geq 0$. In what follows, we will show that
$\mathbf{X}(t)\to\mathbf{X}^{\ast}$ if
$\mathbf{X}(0)\in\boldsymbol{\mathcal{U}}^{\prime}$.

Now, let $\mathbf{X}(0)\in\boldsymbol{\mathcal{U}}^{\prime}$. Since
$\mathbf{X}(t)\in\boldsymbol{\mathcal{U}}$ for all $t\geq 0$, and using Lemma
1, we have that:

$\frac{d}{dt}E(t)=\operatorname{tr}[\mathbf{V}(\mathbf{X}(t))(\mathbf{X}(t)-\mathbf{X}^{\ast})]<0$
(D.9)

where the last inequality comes from (VS). Hence, $E(t)$ is decreasing if
$\mathbf{X}(0)\in\boldsymbol{\mathcal{U}}$.

Now, we will show that $\mathbf{X}^{\ast}$ is an $\omega$-limit of the flow,
i.e., there exists a sequence $\\{t_{n}\\}_{n\in\mathbb{N}}$ such that
$\mathbf{X}(t_{n})\to\mathbf{X}^{\ast}$ as $n\to\infty$. For the sake of
contradiction, suppose such a sequence does not exist. Then,
$\lVert\mathbf{X}(t)-\mathbf{X}^{\ast}\rVert$ is bounded away from zero, which
implies that there exists $c>0$ such that
$\operatorname{tr}[\mathbf{V}(\mathbf{X}(t))(\mathbf{X}(t)-\mathbf{X}^{\ast})]<-c$,
i.e., $\frac{d}{dt}E(t)<-c$. Integrating over time, we get

$\displaystyle E(t)-E(0)<-ct$

which implies that $E(t)\to-\infty$ as $t\to\infty$. This contradicts the non-
negativity property of the Fenchel coupling, thus, we conclude that there
exists a sequence $\\{t_{n}\\}_{n\in\mathbb{N}}$ such that
$\mathbf{X}(t_{n})\to\mathbf{X}^{\ast}$ as $n\to\infty$.

Finally, by Proposition A.2, we get that
$F(\mathbf{X}^{\ast},\mathbf{Y}(t_{n}))\to 0$ as $n\to\infty$, i.e.,
$E(t_{n})\to 0$. Therefore, since $E(t)$ is decreasing and $E(t_{n})\to 0$, we
conclude that $E(t)\to 0$ as $t\to\infty$, i.e.,
$F(\mathbf{X}^{\ast},\mathbf{Y}(t))\to 0$. Again, using Proposition A.2, we
conclude that $\mathbf{X}(t)\to\mathbf{X}^{\ast}$, i.e., $\mathbf{X}^{\ast}$
is consistently asymptotically stable. ∎

##  Appendix E Poincaré recurrence

Our aim in this appendix will be to prove our recurrence result for min-max
games admitting a full-rank equilibrium. For ease of reference, we restate the
result below:

See 3

As we briefly discussed in the main part of the paper, our proof strategy will
consist of the following steps:

  1. (1)

First, we will need to collapse the space of dual space
$\boldsymbol{\mathcal{Y}}$ of $\boldsymbol{\mathcal{V}}\equiv\mathbb{H}^{d}$
to a subspace $\boldsymbol{\mathcal{Z}}$ with constant trace. The reason for
this is that the mirror map
$\mathbf{Q}\colon\boldsymbol{\mathcal{Y}}\to\boldsymbol{\mathcal{X}}$ is not
injective, even when $h$ is steep: for all $\lambda\in\mathbb{R}$, we have
$\mathbf{Q}(\mathbf{Y}+\lambda\mathbf{I})=\mathbf{Q}(\mathbf{Y})$, which means
that the inverse image of any point in $\operatorname{im}\mathbf{Q}$ always
contains a copy of the real line. This collapse is intended to “quotient out”
this redundancy so as to enable volume comparisons later on.

  2. (2)

The second step is to show that the dynamics (FTQL) remain well-defined on the
quotient space $\boldsymbol{\mathcal{Z}}$, and that they are incompressible,
that is, the volume of a set of initial conditions is maintained over time.
This is encoded by Proposition 2 in the main text.

  3. (3)

The next step in our proof will be to show that the induced dynamics on
$\boldsymbol{\mathcal{Z}}$ admit a _constant of motion_. This will be provided
by the Fenchel coupling relative to the game’s interior equilibrium (and it is
also the point where the full-rank assumption is needed).

  4. (4)

Finally, the last – and most challenging – part of the proof is to show that
the level sets of the Fenchel coupling are bounded in
$\boldsymbol{\mathcal{Z}}$ (by contrast, they are _not_ bounded in
$\boldsymbol{\mathcal{Y}}$).

Once these steps our complete, Theorem 3 will follow from Poincaré’s theorem.
In what follows, we encode each of these steps in a series of lemmas and
proposition. To lighten notation, we will suppress player indices throughout
unless it is absolutely necessary to include them.

### Step 1: Descending to the quotient.

To quotient out the redundancy mentioned above, consider the transformed
matrix variables

$\mathbf{Z}=\mathbf{Y}-(1/d)\operatorname{tr}[\mathbf{Y}]\mathbf{I}$ (E.1)

so $\operatorname{tr}\mathbf{Z}=0$ for all
$\mathbf{Y}\in\boldsymbol{\mathcal{Y}}$. Formally, this transformation can be
represented via tha map
$\boldsymbol{\Pi}\colon\boldsymbol{\mathcal{Y}}\to\boldsymbol{\mathcal{Z}}$,
where

$\boldsymbol{\mathcal{Z}}=\\{\mathbf{Z}\in\boldsymbol{\mathcal{Y}}:\operatorname{tr}\mathbf{Z}=0\\}$
(E.2)

and
$\boldsymbol{\Pi}\colon\mathbf{Y}\mapsto\boldsymbol{\Pi}(\mathbf{Y})=\mathbf{Z}$
is defined via (E.1) above. As such, $\mathbf{Z}$ can be seen as a
representative of the equivalence relation
$\mathbf{Y}\sim\mathbf{Y}+\lambda\mathbf{I}$, $\lambda\in\mathbb{R}$, under
which light $\boldsymbol{\mathcal{Z}}$ can be identified with the quotient
$\boldsymbol{\mathcal{Y}}/\sim$.

By construction and the properties of $\mathbf{Q}$ (Lemma A.1 in particular),
we have
$\mathbf{Q}(\mathbf{Y})=\mathbf{Q}(\boldsymbol{\Pi}(\mathbf{Y}))=\mathbf{Q}(\mathbf{Z})$
for all $\mathbf{Y}\in\boldsymbol{\mathcal{Y}}$. Accordingly, (FTQL) readily
gives

$\displaystyle\dot{\mathbf{Z}}=\frac{d}{dt}[\mathbf{Y}-(1/d)\operatorname{tr}[\mathbf{Y}]\mathbf{I}]$
$\displaystyle=\dot{\mathbf{Y}}-(1/d)\operatorname{tr}[\dot{\mathbf{Y}}]\mathbf{I}$
$\displaystyle=\mathbf{V}(\mathbf{Q}(\mathbf{Y}))-(1/d)\operatorname{tr}[\mathbf{V}(\mathbf{Q}(\mathbf{Y}))]\mathbf{I}$
$\displaystyle=\mathbf{V}(\mathbf{Q}(\mathbf{Z}))-(1/d)\operatorname{tr}[\mathbf{V}(\mathbf{Q}(\mathbf{Z}))]\mathbf{I}$
(E.3)

so we can rewrite (FTQL) in terms of $\mathbf{Z}$ as

$\dot{\mathbf{Z}}=\mathbf{V}(\mathbf{X})-(1/d)\operatorname{tr}[\mathbf{V}(\mathbf{X})]\mathbf{I}\qquad\mathbf{X}=\mathbf{Q}(\mathbf{Z}).$
(FTQLZ)

Since
$\operatorname{tr}[\dot{\mathbf{Z}}]=\operatorname{tr}[\mathbf{V}(\mathbf{X})]-(1/d)\operatorname{tr}[\mathbf{V}(\mathbf{X})]\operatorname{tr}\mathbf{I}=0$,
it follows that any traceless initial condition of (FTQLZ) will remain
traceless – and hence remain in $\boldsymbol{\mathcal{X}}$ for all $n\geq 0$.
We thus conclude that (FTQLZ) is a well-posed dynamical system on
$\boldsymbol{\mathcal{Z}}$ whose induced flow
$\boldsymbol{\zeta}\colon\mathbb{R}\times\boldsymbol{\mathcal{Z}}\to\boldsymbol{\mathcal{Z}}$
conjugates $\boldsymbol{\psi}$ in the sense that
$\boldsymbol{\zeta}_{t}\circ\boldsymbol{\Pi}=\boldsymbol{\Pi}\circ\boldsymbol{\psi}_{t}$
for all $t\geq 0$.

### Step 2: Volume preservation.

Our second step is to show that the dynamics (FTQLZ) are volume-preserving.
Formally, we establish the following direct analogue of Proposition 2:

######  Proposition E.1.

Let $\boldsymbol{\mathcal{W}}\subseteq\boldsymbol{\mathcal{Z}}$ be an open set
of initial conditions of (FTQLZ), and let
$\boldsymbol{\mathcal{W}}_{t}=\boldsymbol{\zeta}_{#1}(\boldsymbol{\mathcal{W}})$,
$t\geq 0$, denote the evolution of $\boldsymbol{\mathcal{W}}$ under the flow
$\boldsymbol{\zeta}\colon\mathbb{R}\times\boldsymbol{\mathcal{Z}}\to\boldsymbol{\mathcal{Z}}$
of (FTQLZ). Then,
$\operatorname{vol}(\boldsymbol{\mathcal{W}}_{t})=\operatorname{vol}(\boldsymbol{\mathcal{W}})$
for all $t\geq 0$.

######  Remark.

In the above (as in Proposition 2), the volume form
$\operatorname{vol}(\cdot)$ stands for the ordinary Lebesgue measure on
$\boldsymbol{\mathcal{Z}}$.

###### Proof of Proposition E.1.

The key observation here is that the dynamics (FTQLZ) are _incompressible_ –
that is, _divergence-free_. Indeed, since $\mathbf{V}_{i}$ does not depend on
$\mathbf{X}_{i}$ (it is not possible to suppress player indices here), we
readily have
$\nabla_{\mathbf{Z}_{i}^{\top}}\mathbf{V}_{i}(\mathbf{Q}(\mathbf{Y}))=0$ for
all $i\in\mathcal{N}$. This immediately implies that the field

$\mathbf{W}_{i}(\mathbf{Z})=\mathbf{V}_{i}(\mathbf{Q}(\mathbf{Z}))-(1/d_{i})\operatorname{tr}[\mathbf{V}_{i}(\mathbf{Q}(\mathbf{Z}))]\mathbf{I}$
(E.4)

has $\mathrm{div}_{\mathbf{Z}}(\mathbf{W}(\mathbf{Z}))=0$, so (FTQLZ) is
incompressible. Our claim then follows from Liouville’s formula [3]. ∎

Proposition 2 is proved in exactly the same way, so we omit its proof (which
is not needed for the sequel, anyway).

### Step 3: The Fenchel coupling as a constant of motion.

We now proceed to show that the dynamics (FTQLZ) admit a constant of motion,
namely the Fenchel coupling relative to the game’s full-rank equilibrium.
Indeed, letting $E(t)=F(\mathbf{X}^{\ast},\mathbf{Z}(t))$, Lemma 1 readily
gives:

$\displaystyle\frac{dE}{dt}$
$\displaystyle=\operatorname{tr}[\mathbf{V}_{1}(\mathbf{X})(\mathbf{X}_{1}-\mathbf{X}^{\ast}_{1})]+\operatorname{tr}[\mathbf{V}_{2}(\mathbf{X})(\mathbf{X}_{2}-\mathbf{X}^{\ast}_{2})]$
$\displaystyle=u_{1}(\mathbf{X}_{1},\mathbf{X}_{2})-u_{1}(\mathbf{X}^{\ast}_{1},\mathbf{X}_{2})+u_{2}(\mathbf{X}_{1},\mathbf{X}_{2})-u_{2}(\mathbf{X}_{1},\mathbf{X}^{\ast}_{2})$
$\displaystyle=-\mathcal{L}(\mathbf{X}_{1},\mathbf{X}_{2})+\mathcal{L}(\mathbf{X}^{\ast}_{1},\mathbf{X}_{2})+\mathcal{L}(\mathbf{X}_{1},\mathbf{X}_{2})-\mathcal{L}(\mathbf{X}_{1},\mathbf{X}^{\ast}_{2})=\mathcal{L}(\mathbf{X}^{\ast}_{1},\mathbf{X}_{2})-\mathcal{L}(\mathbf{X}_{1},\mathbf{X}^{\ast}_{2})=0$
(E.5)

where, in the last line, we used the assumption that $\mathbf{X}^{\ast}$ is a
full-rank equilibrium; see also the relevant discussion in [22, 23].

### Step 4: Boundedness of the trajectories.

We are left to show that the trajectories of (FTQLZ) are bounded. The key to
this will be the following technical lemma:

######  Lemma E.1.

Let $\mathbf{Z}_{n}$, $n=1,2,\dotsc$, be a sequence in
$\boldsymbol{\mathcal{Z}}$ such that $F(\mathbf{P},\mathbf{Z}_{n})$ remains
constant for some interior $\mathbf{P}\in\boldsymbol{\mathcal{X}}$. Then the
eigenvalues $\\{z_{\alpha,n}\\}_{\alpha=1,\dotsc,d}$ of $\mathbf{Z}_{n}$ are
bounded, i.e., $\sup_{\alpha,n}\lvert z_{\alpha,n}\rvert<\infty$.

###### Proof.

We argue by contradiction. Indeed, assume that $F(\mathbf{P},\mathbf{Z}_{n})$
is constant but $\sup_{\alpha,n}z_{\alpha,n}=\infty$. Then, letting
$z_{n}^{+}=\max_{\alpha}z_{\alpha,n}$ and
$z_{n}^{-}=\min_{\alpha}z_{\alpha,n}$, we will also have
$\limsup_{n\to\infty}(z_{n}^{+}-z_{n}^{-})=\infty$ by the fact that
$\mathbf{Z}_{n}\in\boldsymbol{\mathcal{Z}}$ (so
$\operatorname{tr}\mathbf{Z}_{n}=0$). Then, by relabeling indices and
descending to a finer subsequence if necessary, we may assume without loss of
generality that the following properties hold concurrently:

  1. (1)

$\mathbf{X}_{n}=\mathbf{Q}(\mathbf{Z}_{n})$ converges to some
$\mathbf{X}\in\boldsymbol{\mathcal{X}}$ (by the compactness of
$\boldsymbol{\mathcal{X}}$).

  2. (2)

All elements of the eigen-decomposition
$\mathbf{X}_{n}=\sum_{\alpha}x_{\alpha,n}\mathbf{u}_{\alpha,n}\mathbf{u}_{\alpha,n}^{{\dagger}}$
of $\mathbf{X}_{n}$ also converge (by the compactness of the unitary group
$U(d)$ and the unit simplex).

  3. (3)

$z_{d,n}=z_{n}^{+}$ and $z_{1,n}=z_{n}^{-}$ for all $n=1,2,\dotsc$

  4. (4)

The index set $\\{1,\dotsc,d\\}$ can be partitioned into two nonempty sets
$\mathcal{S}^{+}$ and $\mathcal{S}^{-}$ such that  itn) $\sup_{n}\lvert
z_{n}^{+}-z_{\alpha,n}\rvert<\infty$for all $\alpha\in\mathcal{S}^{+}$; and
itn) $z_{n}^{+}-z_{\alpha,n}\to\infty$for all $\alpha\in\mathcal{S}^{-}$.

Since $\mathbf{X}_{n}$ and $\mathbf{Z}_{n}$ commute (by Lemma A.2), we get:

$\displaystyle\operatorname{tr}[\mathbf{Z}_{n}\cdot(\mathbf{P}-\mathbf{X}_{n})]$
$\displaystyle=\sum_{\alpha=1}^{d}z_{\alpha,n}(p_{\alpha,n}-x_{\alpha,n})$
$\displaystyle=\sum_{\alpha=1}^{d}(z_{\alpha,n}-z_{n}^{+})(p_{\alpha,n}-x_{\alpha,n})$
$\displaystyle=\sum_{\alpha\in\mathcal{S}^{+}}(z_{\alpha,n}-z_{n}^{+})(p_{\alpha,n}-x_{\alpha,n})+\sum_{\alpha\in\mathcal{S}^{-}}(z_{\alpha,n}-z_{n}^{+})(p_{\alpha,n}-x_{\alpha,n})$
(E.6)

where we let
$p_{\alpha,n}=\mathbf{u}_{\alpha,n}^{\operatorname{diag}}\mathbf{P}\mathbf{u}_{\alpha,n}$,
and we used the fact that
$\operatorname{tr}\mathbf{P}=\operatorname{tr}\mathbf{X}_{n}=1$ in the second
line. Now, by the third part of Lemma A.2, we have $x_{\alpha,n}\to 0$ for all
$\alpha\in\mathcal{S}^{-}$, so
$\lim_{n\to\infty}(p_{\alpha,n}-x_{\alpha,n})>0$ for all
$\alpha\in\mathcal{S}^{-}$ (recall that $p_{\alpha,n}$ converges and
$\mathbf{P}$ has been assumed full-rank). As a result, we get

$\sum_{\alpha\in\mathcal{S}^{-}}(z_{\alpha,n}-z_{n}^{+})(p_{\alpha,n}-x_{\alpha,n})\to-\infty\quad\text{as
$n\to\infty$}.$ (E.7)

and hence, since all quantities involved in the sum over
$\alpha\in\mathcal{S}^{+}$ are bounded, we conclude that
$\operatorname{tr}[\mathbf{Z}_{n}\cdot(\mathbf{P}-\mathbf{X}_{n})]\to-\infty$
as $n\to\infty$. However, by the definition of the Fenchel coupling, we have

$F(\mathbf{P},\mathbf{Z}_{n})=h(\mathbf{P})+h^{\ast}(\mathbf{Z}_{n})-\operatorname{tr}[\mathbf{Z}_{n}\mathbf{P}]=h(\mathbf{P})-h(\mathbf{X}_{n})-\operatorname{tr}[\mathbf{Z}_{n}\cdot(\mathbf{P}-\mathbf{X}_{n})],$
(E.8)

which in turn yields $\lim_{n\to\infty}F(\mathbf{P},\mathbf{Z}_{n})=-\infty$,
a contradiction. ∎

### Step 5: Putting everything together.

With all this said and done, we are finally in a position to prove Theorem 3.

###### Proof of Theorem 3.

By Lemma E.1 and the fact that $F(\mathbf{X}^{\ast},\mathbf{Z}(t))$ is a
constant of motion under (FTQLZ), it follows that the trajectories of (FTQLZ)
remain bounded. Hence, by Proposition E.1 and Poincaré’s recurrence theorem,
it follows that the dynamics (FTQLZ) are recurrent, i.e., for (Lebesgue)
almost every initial condition $\mathbf{Z}\in\boldsymbol{\mathcal{Z}}$, the
induced trajector $\mathbf{Z}(t)\equiv\boldsymbol{\zeta}_{t}(\mathbf{Z})$
returns arbitrarily close to $\mathbf{Z}$ infinitely many times. More
precisely, this means that for every neighborhood $\boldsymbol{\mathcal{W}}$
of $\mathbf{Z}(0)$ in $\boldsymbol{\mathcal{Z}}$, there exists some finite
return time $\tau_{\boldsymbol{\mathcal{W}}}$ such that
$\boldsymbol{\zeta}_{\tau_{\mathcal{U}}}(\mathbf{Z})\in\boldsymbol{\mathcal{W}}$.
Hence, by taking a shrinking net of balls $\boldsymbol{\mathcal{W}}_{n}$
centered at $\mathbf{Z}$ and with radius $1/n$, and letting
$t_{n}=\tau_{\boldsymbol{\mathcal{W}}_{n}}$, we deduce that
$\boldsymbol{\zeta}(t_{n})\to\mathbf{Z}$ as $n\to\infty$. Our assertion then
follows by applying the above construction to some
$\mathbf{Z}\in\mathbf{Q}^{-1}(\mathbf{X}(0))\cap\mathbf{Z}$ and noting that
$\mathbf{X}(t_{n})=\boldsymbol{\chi}_{t_{n}}(\mathbf{X}(0))=\mathbf{Q}(\boldsymbol{\zeta}_{t_{n}}(\mathbf{Z}))\to\mathbf{Q}(\mathbf{Z})=\mathbf{X}(0)$.
∎

##  Appendix F Numerical Results

In this appendix, we describe our simulations setup. We consider a simple two-
player zero-sum game with payoff matrices $P_{1}=\begin{pmatrix}2&1\\\
-2&-1\end{pmatrix}$ for the row- and $P_{2}=-P_{1}$ for the column-player,
expressed in the quantum regime. Denoting the rows as
$(\alpha_{1},\alpha_{2})$ and the columns as $(\beta_{1},\beta_{2})$, we have
that the action profile $(\alpha_{1},\beta_{2})$ is a strict
$\operatorname{NE}$. We run (MMW) on the two-player quantum game with initial
conditions $(0.2,0.8)$ and $(0.8,0.2)$ for the row- and column-player,
respectively, and generate the trajectories of the players’ states up to time
$t=100$. The way we visualize them is through each player’s Bloch sphere. Note
that the red diamond “$\blacklozenge$” on the figures denotes the initial
mixed states of the players. As we observe, the trajectories converge to the
boundary of the Bloch spheres, i.e., to pure states. To facilitate the
reproducibility of our results, we used we denote that we used the openly
available code from: [23, https://openreview.net/forum?id=FFZYhY2z3j]

## References

  * Aaronson [2020] Aaronson, S.  Shadow tomography of quantum states.  _SIAM Journal on Computing_ , 49(5):STOC18–368–STOC18–394, January 2020.
  * Aaronson et al. [2018] Aaronson, S., Chen, X., Hazan, E., Kale, S., and Nayak, A.  Online learning of quantum states.  In _NeurIPS ’18: Proceedings of the 32nd International Conference of Neural Information Processing Systems_ , 2018.
  * Arnold [1989] Arnold, V. I.  _Mathematical Methods of Classical Mechanics_.  Number 60 in Graduate Texts in Mathematics. Springer, New York, NY, 2 edition, 1989.
  * Arute et al. [2019] Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G., Buell, D. A., Burkett, B., Chen, Y., Chen, Z., Chiaro, B., Collins, R., Courtney, W., Dunsworth, A., Farhi, E., Foxen, B., Fowler, A., Gidney, C., Giustina, M., Graff, R., Guerin, K., Habegger, S., Harrigan, M. P., Hartmann, M. J., Ho, A., Hoffmann, M. R., Huang, T., Humble, T. S., Isakov, S. V., Jeffrey, E., Jiang, Z., Kafri, D., Kechedzhi, K., Kelly, J., Klimov, P. V., Knysh, S., Korotkov, A. N., Kostritsa, F., Landhuis, D., Lindmark, M., Lucero, E., Lyakh, D., Mandra, S., McClean, J. R., McEwen, M., Megrant, A., Mi, X., Michielsen, K., Mohseni, M., Mutus, J., Naaman, O., Neeley, M., Neill, C., Niu, M. Y., Ostby, E., Petukhov, A., Platt, J. C., Quintana, C., Rieffel, E. G., Roushan, P., Rubin, N. C., Sank, D., Satzinger, K. J., Smelyanskiy, V., Sung, K. J., Trevithick, M. D., Vainsencher, A., Villalonga, B., White, T., Yao, Z. J., Yeh, P., Zalcman, A., Neven, H., and Martinis, J. M.  Quantum supremacy using a programmable superconducting processor.  _Nature_ , 574(7779):505–510, 2019.
  * Bostanci & Watrous [2022] Bostanci, J. and Watrous, J.  Quantum game theory and the complexity of approximating quantum Nash equilibria.  _Quantum_ , 6:882, 2022.
  * Carlen [2009] Carlen, E. A.  Trace inequalities and quantum entropy: An introductory course.  2009\.
  * Chakrabarti et al. [2019] Chakrabarti, S., Huang, Y., Li, T., Feizi, S., and Wu, X.  Quantum Wasserstein generative adversarial networks.  In _NeurIPS ’19: Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , 2019.
  * Chuang & Nielsen [2010] Chuang, I. and Nielsen, M.  _Quantum Computation and Quantum Information_.  Cambridge University Press, 2 edition, 2010.
  * Coucheney et al. [2015] Coucheney, P., Gaujal, B., and Mertikopoulos, P.  Penalty-regulated dynamics and robust learning procedures in games.  _Mathematics of Operations Research_ , 40(3):611–633, August 2015.
  * Cressman [2003] Cressman, R.  _Evolutionary Dynamics and Extensive Form Games_.  The MIT Press, 2003.
  * Dallaire-Demers & Killoran [2018] Dallaire-Demers, P.-L. and Killoran, N.  Quantum generative adversarial networks.  _Physical Review A_ , 98(1):012324, 2018.
  * Daskalakis et al. [2006] Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H.  The complexity of computing a Nash equilibrium.  In _STOC ’06: Proceedings of the 38th annual ACM symposium on the Theory of Computing_ , 2006.
  * Daskalakis et al. [2009] Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H.  The complexity of computing a Nash equilibrium.  _Communications of the ACM_ , 52(2):89–97, 2009\.
  * Debreu [1952] Debreu, G.  A social equilibrium existence theorem.  _Proceedings of the National Academy of Sciences of the USA_ , 38(10):886–893, October 1952.
  * Eisert et al. [1999] Eisert, J., Wilkens, M., and Lewenstein, M.  Quantum games and quantum strategies.  _Physical Review Letters_ , 83(15):3077–3080, October 1999.
  * Facchinei & Pang [2003] Facchinei, F. and Pang, J.-S.  _Finite-Dimensional Variational Inequalities and Complementarity Problems_.  Springer Series in Operations Research. Springer, 2003.
  * Flokas et al. [2020] Flokas, L., Vlatakis-Gkaragkounis, E. V., Lianeas, T., Mertikopoulos, P., and Piliouras, G.  No-regret learning and mixed Nash equilibria: They do not mix.  In _NeurIPS ’20: Proceedings of the 34th International Conference on Neural Information Processing Systems_ , 2020.
  * Folland [1999] Folland, G. B.  _Real Analysis_.  Wiley-Interscience, 2 edition, 1999.
  * Gutoski & Watrous [2007] Gutoski, G. and Watrous, J.  Toward a general theory of quantum games.  In _STOC ’07: Proceedings of the 39th annual ACM symposium on the Theory of Computing_ , 2007.
  * Hidalgo [2006] Hidalgo, E. G.  Quantum replicator dynamics.  _Physica A: Statistical Mechanics and its Applications_ , 369(2):393–407, September 2006.
  * Hofbauer & Sigmund [2003] Hofbauer, J. and Sigmund, K.  Evolutionary game dynamics.  _Bulletin of the American Mathematical Society_ , 40(4):479–519, July 2003.
  * Jain & Watrous [2009] Jain, R. and Watrous, J.  Parallel approximation of non-interactive zero-sum quantum games.  In _CCC ’09: Proceedings of the 2009 IEEE International Conference on Computational Complexity_ , 2009.
  * Jain et al. [2022] Jain, R., Piliouras, G., and Sim, R.  Matrix multiplicative weights updates in quantum games: Conservation law & recurrence.  In _NeurIPS ’22: Proceedings of the 36th International Conference on Neural Information Processing Systems_ , 2022.
  * Kakade et al. [2012] Kakade, S. M., Shalev-Shwartz, S., and Tewari, A.  Regularization techniques for learning with matrices.  _The Journal of Machine Learning Research_ , 13:1865–1890, 2012.
  * Kwon & Mertikopoulos [2017] Kwon, J. and Mertikopoulos, P.  A continuous-time approach to online optimization.  _Journal of Dynamics and Games_ , 4(2):125–148, April 2017.
  * Lattimore & Szepesvári [2020] Lattimore, T. and Szepesvári, C.  _Bandit Algorithms_.  Cambridge University Press, Cambridge, UK, 2020.
  * Lloyd & Weedbrook [2018] Lloyd, S. and Weedbrook, C.  Quantum generative adversarial learning.  _Physical Review Letters_ , 121(4):040502–040507, July 2018.
  * Maynard Smith [1982] Maynard Smith, J.  _Evolution and the Theory of Games_.  Cambridge University Press, Cambridge, 1982.
  * Maynard Smith & Price [1973] Maynard Smith, J. and Price, G. R.  The logic of animal conflict.  _Nature_ , 246:15–18, November 1973.
  * Mertikopoulos & Sandholm [2016] Mertikopoulos, P. and Sandholm, W. H.  Learning in games via reinforcement and regularization.  _Mathematics of Operations Research_ , 41(4):1297–1324, November 2016.
  * Mertikopoulos & Zhou [2019] Mertikopoulos, P. and Zhou, Z.  Learning in games with continuous action sets and unknown payoff functions.  _Mathematical Programming_ , 173(1-2):465–507, January 2019.
  * Mertikopoulos et al. [2018] Mertikopoulos, P., Papadimitriou, C. H., and Piliouras, G.  Cycles in adversarial regularized learning.  In _SODA ’18: Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithms_ , 2018.
  * Meyer [1999] Meyer, D. A.  Quantum strategies.  _Physical Review Letters_ , 82(5):1052–1055, February 1999.
  * Petersen & Pedersen [2012] Petersen, K. B. and Pedersen, M. S.  The matrix cookbook, nov 2012.
  * Piliouras & Shamma [2014] Piliouras, G. and Shamma, J. S.  Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré recurrence.  In _SODA ’14: Proceedings of the 25th annual ACM-SIAM Symposium on Discrete Algorithms_ , 2014.
  * Preskill [2018] Preskill, J.  Quantum computing in the NISQ era and beyond.  _Quantum_ , 2:79, August 2018.
  * Rockafellar [1970] Rockafellar, R. T.  _Convex Analysis_.  Princeton University Press, Princeton, NJ, 1970.
  * Rockafellar & Wets [1998] Rockafellar, R. T. and Wets, R. J. B.  _Variational Analysis_ , volume 317 of _A Series of Comprehensive Studies in Mathematics_.  Springer-Verlag, Berlin, 1998.
  * Sandholm [2010] Sandholm, W. H.  _Population Games and Evolutionary Dynamics_.  MIT Press, Cambridge, MA, 2010.
  * Scutari et al. [2010] Scutari, G., Facchinei, F., Palomar, D. P., and Pang, J.-S.  Convex optimization, game theory, and variational inequality theory in multiuser communication systems.  _IEEE Signal Process. Mag._ , 27(3):35–49, May 2010.
  * Shalev-Shwartz [2011] Shalev-Shwartz, S.  Online learning and online convex optimization.  _Foundations and Trends in Machine Learning_ , 4(2):107–194, 2011.
  * Shalev-Shwartz & Singer [2006] Shalev-Shwartz, S. and Singer, Y.  Convex repeated games and Fenchel duality.  In _NIPS’ 06: Proceedings of the 19th Annual Conference on Neural Information Processing Systems_ , pp. 1265–1272. MIT Press, 2006.
  * Shapiro et al. [2009] Shapiro, A., Dentcheva, D., and Ruszczyński, A.  _Lectures on Stochastic Programming_.  Society for Industrial and Applied Mathematics, Philadelphia, PA, 2009\.
  * Slivkins [2019] Slivkins, A.  Introduction to multi-armed bandits.  _Foundations and Trends in Machine Learning_ , 12(1-2):1–286, November 2019.
  * Taylor & Jonker [1978] Taylor, P. D. and Jonker, L. B.  Evolutionary stable strategies and game dynamics.  _Mathematical Biosciences_ , 40(1-2):145–156, 1978.
  * Tsuda et al. [2005] Tsuda, K., Rätsch, G., and Warmuth, M. K.  Matrix exponentiated gradient updates for on-line Bregman projection.  _Journal of Machine Learning Research_ , 6:995–1018, 2005\.
  * Viossat & Zapechelnyuk [2013] Viossat, Y. and Zapechelnyuk, A.  No-regret dynamics and fictitious play.  _Journal of Economic Theory_ , 148(2):825–842, March 2013.
  * Weibull [1995] Weibull, J. W.  _Evolutionary Game Theory_.  MIT Press, Cambridge, MA, 1995.
  * Wilcox [1967] Wilcox, R. M.  Exponential operators and parameter differentiation in quantum physics.  _Journal of Mathematical Physics_ , 8(4):962–982, 1967.
  * Zhong et al. [2020] Zhong, H.-S., Wang, H., Deng, Y.-H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Qin, J., Wu, D., Ding, X., Hu, Y., Hu, P., Yang, X.-Y., Zhang, W.-J., Li, H., Li, Y., Jiang, X., Gan, L., Yang, G., You, L., Wang, Z., Li, L., Liu, N.-L., Lu, C.-Y., and Pan, J.-W.  Quantum computational advantage using photons.  _Science_ , 370(6523):1460–1463, December 2020\.
  * Zimmert & Seldin [2021] Zimmert, J. and Seldin, Y.  Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits.  _Journal of Machine Learning Research_ , 22(28):1–49, 2021.

  *[FTQL]: “follow the quantum regularized leader”
  *[FTRL]: “follow the regularized leader”
  *[QGANs]: quantum generative adversarial network
  *[MMW]: matrix multiplicative / exponential weights
  *[POVM]: positive operator-valued measure
  *[NE]: Nash equilibrium
  *[RHS]: right-hand side
  *[ODE]: ordinary differential equation
  *[GANs]: generative adversarial network
  *[l.s.c.]: lower-semicontinuous
  *[QRD]: quantum replicator dynamics