Payoff-based Learning with Matrix Multiplicative Weights in Quantum Games
Authors: Kyriakos Lotidis
Panayotis Mertikopoulos
Nicholas Bambos
Jose Blanchet
Venue: NeurIPS 2023 poster (2023)
Keywords: quantum games
Matrix Multiplicative Weights
zero-sum games
Nash equilibrium

Abstract: In this paper, we study the problem of learning in quantum games - and other classes of semidefinite games - with scalar, payoff-based feedback.
For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks.
The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed.
Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand.
As a first result, we show that the 3MW method with deterministic payoff feedback retains the $\mathcal{O}(1/\sqrt{T})$ convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar.
Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an $\mathcal{O}(T^{-1/4})$ rate.
Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.

Payoff-based Learning with Matrix Multiplicative Weights in Quantum Games
Kyriakos Lotidis Stanford University
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP
LIG 38000 Grenoble, France
htrp:iiissmmeiiooooooosssiiiiii fr
Nicholas Bambos
Jose Blanchet
Stanford University
Stanford University
bambos@stanford. edu
jose. www.bblaaneettttannoooooe edu
Abstract
this paper, we study the problem of learning quantum games and other classes of semidefinite games with scalar, sayoff-basee feedback. For concrete- ness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimallinformatioon matrix multi- plicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence this setting is that, in contrast to classical finite games, quantum games have infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weightee techniques for estimating payoff vectors cannot be employed. Instead, we bor- row ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted the semidefinite geometry of the problem hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the O(1/VT) convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's 's information requirements even further and we provide 3MW method that only requires players to observe a random realiza- tion of their payoff observable, and converges equilibrium an ((T-1/4) rate. Finally, going beyond zero-sum games, we show that regularized variant of the proposed 3MW method guarantees local convergence with high probability all equilibria that satisfy certain first-order stability condition.
1 Introduction
The integration quantum information theory into computer science and machine learning [4, 51, 64] has the potential ofy providing faster and more efficient computing resources, encryption and security protocols, and improved machine learning algorithms, enabling advancements in areas such as quantum cryptography, shadow tomography, quantum GANs, and adversarial learning [1, 15. 18, 37]. As a well-known example, Google's "Sycamore" 54-qubit processor recently showcased this "quantum advantage" by training an autonomous vehicle model in less than 200 seconds [4]. fact made possible by the ability of quantum computers to prepare superpositions of qubits that exceed the operational capabilities of standard Boolean gates.
Deploying such models within a multi-agent context, such as the utilization of QGANs or autonomous vehicles, leads to significant transformation compared to classical non-cooperative environments.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Indeed, unlike classical games (where mixed strategy is probabilistic mixture of the underlying pure strategies), quantum games utilize mixed states, which represent probabilistic mixtures of quantum projectors. As a consequence, a mixed quantum state can yield payoffs that cannot be expressed as a convex combination of classical pure strategies.
In light of this, quantum learning has drawn significant attention in recent years [2, 27, 28, 33, 34, 60]. In a multi-agent context, the most widely used framework is the so-called matrix multiplicative weights (MMW) algorithm [2, 16, 27, 28, 35]: First introduced by Tsuda et al. [59] in the context of matrix and dictionary learning. MMW can be viewed as semidefinite analogue of the standard Hedge / EXP3 methods for multi-
bandits [6, 36, 61], and is a special case of the mirror descent family of algorithms [47]. Specifically, in the contrete setting of two-player, zero-sum quantum games, Jain& & Watrous [27] showed that players using the MMW algorithm can learn an e-equilibrium in O(1/E²) iterations or, in terms of speed of convergence after T iterations, they converge to equilibrium at a ( rate.
To the best of our knowledge, this result remains the tightest known bound for equilibrium learning in quantum games and the more general class of semidefinite games [26]. At this point, we highlight that we focus on classical computing algorithms for solving quantum games, unlike recent results [10, 22] that employ quantum algorithms to solve classical games and semidefinite programs. Building on [27]. Jain et al. [28] studied its continuous-time analogue the quantum replicator dynamics (QRD)- - quantum min-max games, focusing on the recurrence and volume conservation properties of the players' actual trajectory of play. Going beyond the min-max case, [38] examined the convergence of the dynamies of "follow the quantum leader" " (FTQL), a class of continuous- time dynamics that includes the QRD as a special case. The main result of [38] was that the only states that are asymptotically stable under the (continuous- certain first-order stationarity condition known variational stability [44, 46]. In similar line of work, Lin et al. [35] studied the continuous-time QRD, and discrete-time MMW in quantum potential games, utilizing Riemannian metric to obtain gradient flow in the spirit of [41, 42].
dynamics of FTQL are those that satisfy a
Our contributions in the context of previous work. All works mentioned above, in both continu- ous and discrete time, assume full information, i.e., players have access to their individual payoff gradients- which, among others, might imply that they have full knowledge of the game. How- ever, this condition is rarely met in online learning environments where players only observe their in-game payoffs; this is precisely the starting point of our paper which aims to derive convergent payoff-based, gradient-free variant of MMW algorithm for learning in quantum games.
A major roadblock in this is that standard approaches from learning in finite games fail in the quantum setup for two reasons: First and foremost, there is a continuum of pure states available to every player, unlike classical finite games where there is only a finite set of pure actions. Second, even after the realization of the pure states of the players, there is an inherent uncertainty and randomness due to the sayoff-generatie quantum process (an aspect that has no classical counterpart). To overcome this hurdle, we employ a contimuous-action reformulation of quantum games, and we leverage techniques from bandit convex optimization for estimating the players' payoff gradients.
Our first contribution is a variant of MMW that only requires mixed payoff observations and achieves an 001VV)) equilibrium convergence rate in two-player zero-sum quantum games, matching the rate of the full information MMW in [27]. Then, to account for information-starved environments where players are only able to observe their in-game, realized payoff observable, we also develop a bandit variant of MMW which utilizes single- gradient estimation technique in the spirit of [55] and achieves an (77-1/4) equilibrium convergence rate. Finally, we also examine the behavior of the MMW algorithm with bandit information in general N-player games, where we show that variationally stable equilibria are locally attracting with high probability.
Importantly, the above results transfer to more general games with a semidefinite structure such as multi-agent covariance matrix optimization in signal processing, energy efficiency maximization in multi-antenna systems, etc. [43, 45, 62). While we do not provide a complete theory, we discuss a number of non-quantum applications that showcase how our results can be generalized further.
Given (complex) Hilbert space H. we will use Dirac's bra-ket notation and write (w) for an element of H and (66 for its adjoint; otherwise, when a specific basis is implied by the context, we will use the dagger notation "4" to denote the Hermitian transpose s' of v. We will also write
Notation.

---

H" for the space of d x d Hermitian matrices, and Hę for the cone of positive semidefite matrices in Hd. Finally, we denote by || vir[A[A] the Frobenius norm of A in H4!
2 Problem setup and preliminaries
We begin by reviewing some basic notions from the theory of quantum games, mainly intended to set notation and terminology; for a comprehensive introduction, see [23]. To streamline our presentation, we introduce the primitives of quantum games in a 2-player setting before treating the general case.
Quantum games. Following [20, 23], a 2-player quaantum game consists of the following:
1. Each player i N == (1.2) has access to a complex Hilbert space Hi Cd. describing the set of (pure) quantum states available to the player (typically discrete register of qubits). A quantum state is an element di; of Hi with unit norm, so the set of pure states is the unit sphere P, = (v/ Hy ||ı I} of H,, We will write Y PP x 42 for the space of all ensembles & = (2)) of pure states dy e Vi that are independently prepared by each player.
The rewards that players receive are based on their individual payoff functions u,: - R, and they are derived through positive aperator-valuet measure (POVM) quantum measurement process. Following [17]. this unfolds as follows: Given a finite set of measurement outcomes Q that referee can observe from the players' quantum states (e.g., measure player-prepared qubit to be "up" or "down"), each outcome @ E Q is associated to positive semi-defnntte operator pw: H - H defined on the tensor product H. Hi H2 of the players' individual state spaces. We further assume that Ewen P.. = so the probability of observing w E Ω at state & E Y is Pw (v) (1/1 @ 22(Pa/l11 @ 122).
The payoff of each player is then generated by this measurement process via a payoff observable U:: 5 - IR: specifically, the measurement is drawn from Ω based on the players' state profile &/ = (v), 1/2), and each player i E N receives as reward the quantity ((w).. Accordingly, the player's is expected payoff at state & P is in (v) (U,) = E. (v)) (,(w).
A quanlum game is then defined as tuple Q Q(V, Y. u) with players, states, and payoff as above.
Mixed states. Apart from pure states, each player E N may prepare probabilistic mixtures thereof, known as mixed states. These mixed states differ from mixed strategies used in classical, finite games as they do not correspond to convex combinations of their pure counterparts; instead, given a family of pure quantum states Vie, E V; indexed by a; E A;, a mixed state is described by density matrix of the form
X; x= Eares, Xia; (iii,) (Wiarl where the mixing weights Xta, 0 of each diaa normalized so that X, 1. By Born's 's rule, this means that the probability of observing w E Q under X (x) is
(1)
(x) = -,,SA, Emgas x2, P (w).)
where vhr 11., @ 22.a.. Therefore, in slight abuse of notation, the expected payoff of player i E N under X will be (X) Eoe Natt( (Va). which, equivalently, can be written as:
": (x( = Σ wen EOcANati (a Ui(w).
This gives a succint representation of the payoff structure of Q see also Eq. (5) below.
Continuous game reformulation. extension of a finite game can be misleading. For our purposes, it would be more suitable to treat a quantum game as a continuous game where each player i N controls a matrix variable X, drawn from the "spectraplex" defined as X, (X, E H tr X; = 1}. In this interpretation, the players' payoff functions X = X1 x X₂ + R are linear in each player's 's density matrix X; E X i E N. Since ni, 22 are linear in X, and X2, the individual payoff gradients of each player will be given by
view of the above, treating a quantum game as "tensorial"
(x) = Xx (X) and (2(X)= == (X)
(4)
so we can further write each player's 's payoff function as
#1 (X) vx and (X) = ir X, (X))
for all X E X.
(5)
3

---

Since X' is compact and each is multilinear in X, the players' payoff functions are automatically bounded, Lipschitz continuous and Lipschitz smooth, i.e. there exist constants B,, G, and L,, e N, such that, for all X, X' E X, we have:
1. Boundedness:
(x,(X) & B;
2. Lipschitz continuity:
(X) (X - IIV V S L
Lipschitz smoothness:
The most widely used solution concept in game theory is that of a Nash equilibrium (NE). In context, is mixed profile X X from which no player has incentive to deviate, i.e., 4i (X") 2 ij (X1;X) and u²(X*) 2 u2 xx(X;;x)) for all X E X X, E Xz. Since X is convex and u; linear X,, the existence of Nash equilibria follows from the Debreu's theorem [19].
Nash equilibrium.
Zero-sum quantum games. In the case where #n -12 and setting L: X1 x x - R, the Nash equilibria of the saddle points of L. i.e., the solutions of the minimax problem
max min (2) min max (()),Xg) X X28X2
(6)
X
By Sion's minimax theorem [54], the set of Nash equilibria is nonempty. Then, given a Nash equilibrium X", define the duality gap of X (X,, X2)
(X) = LXX; X2) ((),,X))
so (X) 2 0 with equality if and only if X is itself Nash equilibrium. In particular, X is an e-Nash equilibrium of Q if and only if Gap (X) s
Other semidefinite games. In addition to quantum games, our framework can also be used for learning other classes of games with semidefinite structure as per [26, 45]. As an example, consider the problem of covariance matrix optimization in vector Gaussian multiple-access channels .N: each player
[9, 43, 57, 62]. In this case, there is finite set of players indexed by e i E ' picks a unit-trace semidefinite matrix X; E X; and their payoff is given by the Channon-Telate capacity formula [57], viz.
Xv) = log det(I + Σ, H)X
(8)
where each H, is player- specific gain matrix [58]. Even though M; is no longer multilinear in X, the algorithms we derive later in the paper can be applied to this setting essentially verbatim.
The matrix multiplicative weights algorithm
Throughout the sequel, we will focus on equilibrium learning in quantum and semidefinite games. In the context of two-player, zero-sum quantum games, the offte- method is based on the so-called matrix multiplicative weights (MMW) algorithm [7, 27, 29, 59] which updates as
X exp(Y Yi,))
Yis+ Yis + y (XX,)
(MMW)
tr er|exp( Y..)
In the above, (a) X, (X1,,X denotes the players' density matrix profile at each stage r = 1.2.... of the process; (b) (X,,, is the payoff gradient of player i E N under X,; (c) Y, is an auxiliary state matrix that aggregates gradient steps time; and (d) y, 0, 1, learning rate (or step-size) parameter that can be freely tuned by the players.
Importantly, as stated, (MMW) requires full information at the player end: specifically, at each stage / 1, 2. ... the process, each player A must receive their individual payoff gradient Vi(X,) in order to perform the gradient update step in (MMW). Under this assumption, Jain & Watrous [27] showed that the induced empirical frequency of play
X,
Σ X, T
1
(9)
converges to equilibrium at a rate of O(IvVT) per the formal result below:

---

Theorem 1 (Jain & Watrous [27]). Suppose that each player of a 2-player zero-sum game follows
(MMW) for epochs with learning rate y y= G /2H where H log(did2). Then the players' empirical frequency of play enjoys the bound
(Xr) & GV2HIT
(10)
In particular, if (MMW) is run for T 0(1/82) iterations, Xr will be an 8-Nash equilibrium of Q
To the best of our knowledge, this guarantee of Jain & Watrous [27] remains the tightest known bound for Nash equilibrium learning in 2-player zero-sum quantum games, At the same time, Theorem 1 hinges on the players having perfect access their individual gradients which, among others, might entail full knowledge of the game, observing the other player's density matrix, etc. Our goal in the sequel will be relax precisely this assumption and develop a payoff-based based variant of (MMW) that can be employed without stringent information and observability requirements as above.
4 Matrix learning without matrix feedback
In an online learning framework, it is more realistic to assume that players observe only the outcome of their actions i.e. their individual payoffs. In this information-starved payoff-based setting, our main goal will be to employ a minimal-inforrmatinn matrix multiplicative weights (3MW) algorithm that updates as
exp(Yr.r)
Y Y1.++1 Y1,1 +
X
(3MW)
tr ex(exp(Y Vo.)]
where Vi, is some payoff- baffdd-baddddee estimate of the payoff gradient V,,,, of player at X,, and all other quantities are defined as per (MMW). In this regard, the main challenge that arises how to reconstruct each player's payoff gradient matrices when they are not accessible via an oracle.
4.1. The classical approach: Importance weighted estimators. In the context of classical, finite games and multi-armed bandits, standard approach for reconstructing Vi,, is via the so-called importance weighted estimator (TWE) [12, 14, 32). To state in the context of finite games, assume that each player has at their disposal a finite set of pure strategies a; A,, and if each player plays & E A,, then, in obvious notation, their individual payoff will be û; = u; â-)) Then, each player is using mixed strategy X; E A(A:) to draw their chosen action â,, the importance weighted estimator (IWE) for the payoff of the (possibly unplayed) action a; E A, of player i is defined as
(ar; = فū)
IWE
u;(ā;;; (i-) for all a; A;
(IWE)
Xiar
with the assumption that x; has full support, i.e., each action a; E A has strictly positive probability Xio; of being chosen by the i-th player.
This approach has proven extremely fruitful in the context of multi-armed bandits and finite games where (IWE) is an essential ingredient of the optimal algorithms for each context [5, 12, 32, 65]. However, in our case, there are two insurmountable difficulties in extending (IWE) to a quantum context: First and foremost, the quantum regime is characterized by a continuum of pure states with highly correlated payoffs (in the sense that quantum states that are close in the Bloch sphere will have highly correlated POVM payoff observables); this comes in stark contrast the classical regime of finite normal-form games, where players only have to contend with finite number of actions (with no prior payoff correlations between them). Secondly, even after the realization of the pure states of the players, there is an inherent uncertainty and randomness due to the quantum measurement process that is invovled in the payoff-generane exogenous source of randomness which is altogether absent from (IWE).
process; such, the players' payoffs are also affected by an
Our approach to tackle these issues will be to exploit the reformulation of a quantum game continuous game with multilinear payoffs over the spectraplex (or, rather, a product thereof), and use ideas from bandit convex optimization in the spirit of [21, 31] to estimate the players' payoff gradients with minimal, scalar information requirements.
TThe assumption that x has full support is only for technical reasons. In practice, it can be relaxed by using IWE with explicit exploration see [32] for more details.
5

---

4.2. Gradient estimation via finite-difference quotients on the spectraplex. To provide some intuition for the analysis to come, consider first a single-variable smooth function f: R - and estimate
point x E R. Then, for error tolerance 8 > 0, a two-point estimate of the derivative of f at is given by the expression
f. f(x+ + fx -
(11)
28
Going to higher dimensions, letting f Rd - R be a smooth function, (ei....,ea' eat be the standard basis of Rd and s drawn from (e1. le.....,e.. ea) uniformly at random, the estimator
fx [f(x ( - f(x - 55)]s
(12)
28
a -pprxxooooinntooon of the gradient, i.e., - the
= O()). This idea is the basis of stochastic approximation scheme [30] and will be the backbone of our work.
Now, employ this type of estimator for function over the set of density matrices X' in H4, we need to ensure two things: (i) the feasibility of the sampling direction, and (ii) the feasibility of the evaluation point. The first caveat is due the fact that the set of the density matrices forms lower dimensional manifold in the set of Hermitian operators, and therefore, not all directions from a base of H4 are feasible. The second one is due to the fact that X' is bounded, thus, even if the sampling direction is feasible, the evaluation point can lie outside the set X. We proceed to ensure all this in series of concrete steps below.
Sampling Directions. We begin with the issue of defining a proper sampling set for the estimator's finiteddifference directions. To that end, we will first construct an orthonormal basis of the tangent hull Z- {Z E Hd Z = 0) of X, i.c. the subşpace of traceless matrices of H Note that if Z Z then for any X Hd it holds (a) X + Z HJ and (b) tr[X + Z] tr[X].
Denoting by Art E HH the matrix with in the (k, f) -pooiition and O's everywhere else, it is easy to see that the set {{رد}} )d
, (exc)
{ec))ke) is an orthonormal basis of H where
1 -
i
e =
Auc
Aee
and Tet = Aur Ar
(13)
V2
V2
V2
V2
for 1 S k < 6 d. where is the imaginary unit with 1 = -. The next proposition provides basis for the subspace 3, whose proof lies in the appendix.
Proposition 1. Let Ej be defined Ej
(Au + Ajj- jAj-j,jj))) for I..... d
Vs(+o)
Then, the set & [E,) (euc) (Euc ( is an orthonormal basis of Z.
In the sequel, we will use this basis as an orthnormal sampler from which to pick the finite-difference directions for the estimation of V.
Feasibility Adjustment. After establishing orthonormal basis for Z per Proposition 1, readily get that for any X X, any Z 8* == {(=E,) (=ex)) {=ēkc)k<t) } and 8 > 0, the point X + 5 Z belongs to Z. However, depending on the value of the exploration parameter ō and the distance of X from the boundary of X. the point X + 5Z e H' may fail lie in X due to violation of the positive-semidefinic condition. On that account, we now treat the latter restriction, i.e., the feasibility of the evaluation point.
To tackle this, the idea to transfer the point X toward the interior of X and move along the sampled direction from there. For this, we need find a reference point R e ri(X) and "safety net" r such that R + rZ E X' for any Z &*. Then, for ò E (0, r), the point
X X x
5 (
(14)
lies in ri) and moving along Z E Et, the point X(6) ( (R+ remains in X' as a convex combination of two elements in X. The following proposition provides an exact expression for R and r, which we will use next to guarantee the feasibility of the sampled iterates.
Proposition 2. Let R 1 Ed Aij- Then, for min
v2. it holds that R + rZ E X for
Va(d-1) d
any direction Z E 8²

---

Bandit learning in zero-sum quantum games
With all these hand, we are now ready to proceed to the presentation of the MMW with limited feedback information. To streamline our presentation, before delving into the more difficult "bandit feedback" case where each player E N only observes the realized payoff observable (((w) - we begin with the simpler case where players observe their mixed payoffs u, given profile X E X.
5.1. Learning with mixed payoff' observations. Our main idea to exploit the observation of mixed payoffs and the differeifeerenc sampling to the fullest will be to introduce a "ccordination phase" where players take a sampling step before updating their state variables and continue playing. In more detail, we will take an approach similar to Bervoets al. [8] and assume that players alternate between an "exploration" and an "exploitation" update that allows them to sample the landscape of L efficiently at each iteration. Concretely, writing X, and 6, for the players' state profile and sampling radius 6, at stage = .,.,..., the sequence of events that we envision proceeds as follows:
Step 1. Draw a sampling direction Zi,, E & and Si,r E {+1} uniformly at random.
Step 2. (a) Play ())
i, Sta ò, Zi, and observe u; (X, (6) s,
(b) Play X St,r 6, Zi,, and observe u, (x, 5,6,Zz).
Step 3. Approximate Vi(X,) via the two-point estimator (2PE):
V., D;
(X, + s,,,Z,) u; (X( sy Zi) si. Zi.
(2PE)
26,
where D, = d.- 1 is the dimension of H4, and D := max Dj.
The main guarantee of the resulting (3MW)+ + (2PE) algorithm may then be stated as follows:
Theorem 2. Suppose that each player of 2-player zero-sum game Q follows (3MW) T epochs
with learning rate y. sampling radius 6, and gradient estimates provided by (2PE). Then the players' empirical frequency of play enjoys the duality gap guarantee
E G[app s yT
+ +
(15)
where H = log(d,d2). In particular, particular,fory y (DG) (H((TT) and 5 = (8)L the players enjoy the equilibrium convergence guarantee
E E(Gapp((Xr) 8DG
(16)
Compared to Theorem 1, the convergence rate (16) of Theorem is quite significant because it only differs by factor which is linear in the dimension of the ambient space and otherwise maintains the same (vV) dependence on the algorithm's 's runtime. In this regard, Theorem 2 shows that the "explore-exploit" sampler underlying (2PF) is essentially as powerful as the full information framework of Jain & Watrous [27] - and this, despite the fact that players no longer require access the gradient matrix V of L. This echoes a range of previous findings in stochastic convex optimization for the efficiency of two-point samplers [3. 53], similarity we find particularly surprising given the stark differences between the two settings non-commutativity. min-max versus min-min landscape. The key ingredients for the equilibrium convergence rate of Theorem 2 the two technical results below. The first is feedback feenback-agnostic "energy inequality" which is tied to the update structure of (MMW) and stated in terms of the quantum relative entropy function
D(P, X) tr [r[o P log X)]
(17)
for P. X X with X > O. Concretely, we have the following estimate. Lemma Fix some P E X, and let X, X,,1 be two successive iterates of (3MW), without any assumptions for the input sequence V,. We then have
22 1
D(P.X,.1) S D(P.X,)) LxV, -P]]
(18)
The proof of Lemma I follows established techniques in the theory of (MMW), we defer a detailed discussion to the appendix. The second result that we will need tailored to the estimator (2PE) and provides a tight estimate of its moments conditioned on the history F, F(X...... X,) of X,-
7

---

Algorithm 1: MMW with bandit feedback
1: Input: Y1 <- O; safety parameter r; and anchor point R,, / e W: step-size y;; sampling radius
2: for prr== 1.2.... do simultancously for all i e N
3: Set X,, exp(Y,,,) (tr.)//r(eetr /ttr///((xx,))))
4: Sample L,, uniformly from e
5: Play x(,) 767
6: Observe U;(wr).
7: Set Vi,, == Dj/0, U;(()) Zi.--
Update Vi,4 - Yia + Yi Vi.-
9:
end for
Proposition 3. The estimator (2PE) enjoys the conditional bounds
(19) The defining element in Proposition 3 is that even though the estimator (2PE) is biased, its second moment is bounded as (1). This is ultimately due to the multilinearity of the players' payoff functions and plays a pivotal role in showing that the duality gap of X, under (3MW) is of the same order as under (MMW), because the bias can be controlled with affecting the variance of the estimator. We provide detailed proof of Lemma 1, Proposition 3, and Theorem 2 in the appendix.
(i) [ [r] - v(X,)l s 4DL6, and (ii) [[ s 16D'
5.2. Learning with bandit feedback. Despite its strong convergence guarantees, major limiting factor in the applicability of Theorem is that, in many cases, the game's players may only be able to observe their realized payoff observables U,(w), and their mixed payoffs (X. could be completely inaccessible. In particular, as we described in Section 2, each outcome w Q2 of the POVM occurs with probability P (X,) under the strategy profile X,. Accordingly, if this is the only information available to the players, they will need to estimate their individual payoff gradients through the single observation of the (random) scalar U,(w;) R. In view of this, and inspired by previous works on payoff-based learning and zeroth-order optimization [8, 9, 11, 25, 49, 50], we will consider the single-poin stochastic approximation approach of [21, 55] which unfolds as follows:
Step 1. Each player draws sampling direction Zi, E7 uniformly at random.
Step 2. Each player plays x + +,, Zi,e-
Step 3.
Each player receives (;(w)).
Step 4.
Each player approximates (X,,, via the the one-point estimator (1PE):
Vi. Di U,(w,) Zi,,
(IPE)
6,
In this case, the players' gradient estimates may be bounded as follows:
Proposition The estimator (IPE) enjoys the conditional bounds
(i) || V(X,)llF S 4DL6, and (ii) ELN 4D2
(20)
The crucial difference between Propositions 3 and 4 is that the former leads to a gradient estimator with O(1) variance and magnitude, whereas the magnitude of the latter is inversely proportional to o;; however, since ö, in turn controls the bias of the gradient estimator, we must now resolve a bias-variance dilemma, which was absent the case of (2PE). This leads the following variant of Theorem 2 with bandit, realization-batt based feedback:
Theorem 3. Suppose that each player of 2-player zero-sum game follows (3MW) for T epochs with learning rate y, sampling radius 8, and gradiens estimates provided by (1PE). Then the players' empirical frequency of play enjoys the duality gap guarantee
H
21
B²y + 16DLS
E E[Gap (
(21)
yT
82
where Il lo) In particular, for y the equilibrium convergence guarantee:
3/4
and 5 =
1/4
B
the players enjoy
2T
2D
23/4 1/ DVBL
ElGapz(XT))
(22)
T1/4
8

---

An important observation here is that the players' equilibrium convergence rate under (3MW)+ (IPE) no longer matches the convergence rate of the vanilla MMW algorithm (Theorem 1). The reason for this is the bias-variance trade-off in the estimator (IPE), and is reminiscent of the drop in the rate of regret minimization from ((T!/2) to ((T2/3) under (IWE) with bandit feedback and explicit exploration in finite games. A kernel-based approach in the spirit of Bubeck et al. [13] could possibly be used to fill the ((T)/4) gap between Theorems 1 and 3, but this would come at the cost of possibly catastrophic dependence on the dimension (which is already quadratic in our setting). This consideration is beyond the scope of our work, but it would constitute important future direction.
6 Bandit learning in N-player quantum games
We conclude our paper with an examination of the behavior of the MMW algorithm in general, N-player quantum games. Here, a major difficulty that arises is that, in stark contrast to the min-max case, the set of the game's equilibria can be disconnected, so any convergence result will have to be, by necessity, local. In addition, because general N-games do not have the amenable profile of a bilinear min-max problem they are multilinear, multi-objective problems- it will not be possible to obtain any convergence guarantees for the game's s empirical frequency of play (since there is no convex structure exploit). Instead, will have to focus squarely the induced trajectory of play, which carries with it a fair share of complications.
Inspired by the very recent work of [38], we will not constrain our focus to specific class of games, but to a specific class of equilibria. In particular, we will consider the behavior of MMW-based learning with respect to Nash equilibria X X that satisfy the variational stability condition
tr(V(X) - (')) < 0 for all X (X')..
(VS)
This condition can be traced back to [44], and can be seen as a same-theoretic analogue of first-order stationarity in the context of continuous optimization, or as an equilibrium refinement in the spirit of the seminal concept of evolutionary stability in population games [39, 40].2 Importantly, as was shown in [38], variationally stable equilibria are the only equilibria that are asymptotically stable under the continuous-tin dynamics of the "follow the regularized leader" (FTRL) class of learning policies, so it stands to reason to ask whether they enjoy a similar convergence landscape in the context of bona fide, discrete-time learning with minimal, payoff- based feedback.
Our final result provides an unambiguously positive answer to this question:
Theorem 4. Fix some tolerance level 1 E (0, 1) and suppose that the players of an N-player quantum game follow (3MW) with bandit, realization-base the estimator (IPE) with step-size and sampling radius parameters such that
feedback, and surrogate gradients provided by
E Y1 = on,
(ii) E 7, < 00, and (ii) 2 yi { co.
(23)
If X' is variationally stable, there exists a neighborhoold U Xf such that
P(lim X, = X*) 2 17 whenever X1 E U.
(24)
It is worth noting that the last-iterate convergence guarantee of Theorem 4 is considerably stronger than the time-averaged variants of Theorems 1-3, and we are not aware of any comparable conver- gence guarantee for general quantum games. [Trivially, last-iterate convergence implies time-averaged convergence, but the converse, of course, may fail to hold] As such, especially in cases that require to track the trajectory of the system or the players' day-to-day rewards, Theorem 4 provides an important guarantee for the realized sequence of events.
On the other hand, in contrast to Theorem 4, it should be noted that the guarantees of Theorems 1-3 global. Given that general quantum games may in general possess large number of disjoint Nash equilibria, this transition from global to local convergence guarantees seems unavoidable. It is, however, an open question whether (VS) could be exploited further in order deduce the rate of convergence to such equilibria; we leave this as a direction for future research.
2It should be noted here that, if reduced to the simplex, the stability condition (VS) is exactly equivalently to the variational characterization of evolutionarily stable states due to Taylor [56]. *Strictly speaking. the algorithms (3MW) and (IPE) have been stated in the context of 2-player games. The extension to N- N-player games is straightforward, so we do not present it here; for the details (which hide no subtleties), the appendix.

---

13
Seetdtiee (7)
Suetstion (7)
Figure 1: Performance evaluation of the (3MW) with the (2PE) and (IPF) estimators and comparison with the full information (MMW). The solid lines correspond to the mean values of the duality gap of each method, and the shaded regions enclose the area (sample) standard deviation among the different runs.
7 Numerical Experiments
In this last section, we provide numerical simulations to validate and explore the performance of (MMW) with payoff-based feedback. Additional experiments can be found in Appendix E.
Game setup. Our testbed is two-player zero-sum quantum game, which the quantum analogue of a 2 x 2 min-max game with actions (01 02) and (B1,B2) B2), and payoff matrix
-4) (2, -2) (-4.4)
P
(25)
(-2, 2)
In the quantum regime, the payoff information of the quantum game is encoded in the Hermitian matrices W₁ diag(4. 2, -4. 22), and W2 = W as per Eq. (3) in Section 2. By elementary considerations, the action profile (2) is a strict Nash equilibrium of the classical zero-sum game, which corresponds to the pure quantum state with density matrix profile X = (X", (Xj.X.) where Xi = el @ ei and X; e2 e2 the standard basis which W1 and W2 are diagonal.
Convergence speed analysis. In Fig. 1, we evaluate the convergence properties of (3MW) using the estimators (2PE) and (IPE), and compare with the full information variant (MMW). For each method, we perform 10 different runs, with T 10 steps each, and compute the mean value of the duality gap as a function of the iteration = 1, .......77 T. The solid lines correspond to the mean values of the duality gap of each method, and the shaded regions enclose the area of (sample) standard deviation among the 10 different runs. Note that the red line, which corresponds to the full information (MMW). does not have shaded region, since there is no randomness in the algorithm. All the runs for the three different methods were initialized for Y = 0 and we used 10 for all methods. In particular, for (3MW) with gradient estimates given by (2PE) estimator, we used a sampling radius 5 10-2, and for (3MW) with (1PE) estimator, we used 5 = 10-1 (in tune with our theoretical results which suggest the use of tighter sampling radius when mixed payoff information available to the players).
Figure has several important take-aways. First and foremost, as is be expected, the payoff-based methods lag behind the full-information variant of (MMW); however, what is particularly surprising that the drop performance is singularly mild. As we see the second plot in Fig. 1, the various algorithms achieved a rate of convergence closer to O(1/T), which is significantly faster than O1/vTT) and/or (4/ This suggests that, in practice, the bandit variants of (MMW) may yield excellent performance benefits, despite the high degree of uncertainty incurred by the complete lack of information the game being played.
10

---

Acknowledgments and Disclosure of Funding
This work has been partially supported by the Air Force Office of Scientific Research under award number FA9550-20- 110--220----777
Additional support is gratefully acknowledged from NSF 1915967. 2118199. 2229012, 2312204. KL is grateful for financial support by the Onassis Foundation (F ZR 033-1/2021-288 -2222).. PM is also with the Archimedes Research Unit Athena RC University of Athens, and gratefully acknowledges financial support by project MIS 5154714 14 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationFU Program, and by the French National Research Agency (ANR) in the framework of the "Investisse- ments d' T'avenir" program (ANR-15-IDEX- the LabEx PERSYVAL (ANR-II-LBBX-0025-- MIAI@ Grenoble Alpes FANR-19-P31AN Digital Living 2030 project.
NB was supported by the Koret Foundation via the
References
[1] Aaronson, S. Shadow tomography of quantum states. SIAM Journal on Computing, 49(5), January 2020.
[2] Aaronson, S., Chen, X., Hazan, E.,, Kale, S., and Nayak, A. Online learning of quantum states. In NewrIPS 18: Proceedings of the 32nd International Conference of Neural Information Processing Systems, 2018.
[3] Agarwal, A., Dekel, O., and Xiao, L. Optimal algorithms for online convex optimization with multi multi-point bandit feedback. In COLT 10: Proceedings of the 23rd Annual Conference on Learning Theory, 2010.
[4] 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, J., Ho, A., Hoffmann, M. R., Huang, T., Humble, T. S., Isakov, S. V. Jeffrey. F., Jiang, 7., Kafri, D., Kechedzhi, K., Kelly, J., Klimov, P. V., Knysh, S., Korotkov, A. N., Kostritsa, F,, Landhuis, D., Lindmark, M., Lucero, F., Lyakh, D., Mandra, S., McClean, J. R., McFwwen 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., Ych, P., Zaleman, A., Neven, H., and Martinis, J. M. Quantum supremacy using programmable superconducting processor. Nature, 2019.
[5] Audibert, J.-Y. and Bubeck, S. Regret bounds and minimax policies under partial monitoring. Journal of Machine Learning Research, 11:2635-266 2686, 2010.
[6] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. Gambling in a rigged casino: The adversarial multi-armes bandit problem. Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995.
[7] Beck, A. and Teboulle, M. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 3173):167-775. 2003.
[8] Bervoets, S., Bravo, M., and Faure, M. Learning with minimal information continuous games. Theoreti- cal Economics, 15:1471 150,, 2020.
[9] Bilenne. O.. Mertikopoulos. P., and Belmega, E. V. Fast optimization with zeroth-order feedback in distributed multi-use' MIMO systems. IEEE Trans. Signal Process.. 68:6088-6111 October 2020.
[10] Brandao, F. G. L. and Svore, K. Quantum speed-ups for semidefinite programming. 2017.
[11] Bravo, M., Leslie, D. S., and Mertikopoulos, P. Bandit learning in concave N N-person games. In NeurlPS 18: Proceedings of the 32nd International Conference of Neural Information Processing Systems, 2015 88.
[12] Bubeck, S. and Cesa- Bianchi, N. Regret amalysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning. 5(1):1122,, 2012.
[13] Bubeck, S., Lee, Y. T., and Eldan, R. Kernel-based methods for bandit convex optimization. In STOC '17 Proceedings of the 49th annual ACM SIGACT symposiun on the Theory of Computing, 2017.
[14] Cesa- Desa-Bianchi, N. and Lugosi, G. Prediction, Learning, and Games. Cambridge University Press, 2006.
[15] Chakrabarti, S., Huang, Y., Li, T., Feizi, S., and Wu, X. Quantum Wasserstein generative adversarial networks. In NewrIPS 'I9: Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
[16] Chen, X., Hazan, Li, T., Lu, Z., Wang, X., and Yang, R. Adaptive online learning of quantum states, 2022.
[17] Chuang. 1. and Nielsen, M. Quantum Computation and Quantum Information. Cambridge University Press, 2 edition, 2010.
11

---

[18] Dallaire-Demers, P.-L. and Killoran, N. Quantum generative adversarial networks. Physical Review A. 98 (1):012324, 2018.
[19] Dehreu, G. A social equilibrium existence theorem. Proceedings of the National Academy of Sciences of the USA, October 1952.
[20] Eisert, J., Wilkens, M., and Lewenstein, M. Quantum games and quantum strategies. Physical Review
Letters, 83, October 1999.
[21] Flaxman, A. D., Kalai, A. T., and McMahan, H. B. Online convex optimization in the bandit setting: gradient descent without gradient. In SODA '05; Proceedings of the 16th annual ACM-SIAM Symposium Discrete Algorithms, pp. 385-394, 2005.
[22] Gao, M., Ji, 7.,, Li, T., and Wang, Q. Logarithmic-regre quantum learning algorithms for zero-sum games, 2023.
[23] 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.
[24] Hall, P. and Heyde, C. C. Martingale Limit Theory and Its Application. Probability and Mathematical Statistics. Academic Press, New York, 1980.
[25] Héliou, A., Mertikopoulos, P., and Zhou, Z. Gradient-free online learning in continuous games with delayed rewards. In ICMI. '20: Proceedings of the 37th International Conference on Machine Learning, 2020.
[26] lckstadt, C., Thcobald, T., and Tsigaridas, E. Semidefinite games. https://arrai.oorppdd///2 12035, 2022.
[27] 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.
[28] Jain, R., Piliiuurs, G., and Sim, R. Matrix multiplicative weights updates in quantum games: Conservation
law recurrence. In NeurlPS '22: Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022.
[29] Kakade, S. M., Sawartzz,, S., and Tewari, A. Regularization techniques for learning with matrices. The Journal of Machine Learning Research, 13:1865- 1890, 2012.
[30] Kiefer. J. and Wolfowitz, J. Stochastic estimation of the maximum of regression function. The Annuls of Mathematical Statistics, 23(3):662-466, 1952.
[31] Kleinberg. R. D. Nearly tight bounds for the continuum-armed bandit prohlem. In NIPS' 04: Proceedings of the 18th Annual Conference on Neural Information Processing Systems, 2004.
[32] Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, Cambridge, UK, 2020.
[33] Li, T., Chakrabarti, S., and Wu, X. Sublinear quantum algorithms for training linear and kernel-based classificrs. In International Conference on Machine Learning, 2019.
[34] Li, T., Wang, C., Chakrabarti, S., and Wu, X. Sublinear classical and quantum algorithms for general matrix games. Proceedings of the AAAI Conference on Artificial Intelligence, 35(10), May 2021. doi: 10. 0..160/aaai.v3355 v35510. 17028..
[35] Lin, W., Piliouras, G., Sim, R., and Varvitsiotis, A. Quantum potential games, replicator dynamies, and the separability problem, 2023.
[36] Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. Information and Computation, 108
(2):212-261, 1994.
[37] Lloyd. S. and Weedbrook, C. Quantum generative adversarial learning. Physical Review Letters, 121(4).
July 2018.
[38]
Lotidis, K., Mertikopoulos, P., and Bambos, N. Learning in quantum games, 2023.
[39] Maynard Smith, J. Evolution and the Theory of Games. Cambridge University Press, Cambridge, 1982.
[40] Maynard Smith, J. and Price, G. R. The logic of animal conflict. Nature, 246:15-18, November 1973.
[41]
Mertikopoulos, P. Strange bedfellows: Riemann, Gibbs and vector Gaussian multiple access channels. In NerGCoop 12: Proceedings of the 2012 International Conference on Network Games, Control and Optimization, 2012.
[42] Mertikopoulas, P. and Moustakas, A. L. Entropy-driven optimization dynamics for Gaussian vector multiple access channels. In ICC '13 Proceedings of the 2013 IEFE International Conference Communications, 2013.
[43] Mertikopoulos, P. and Moustakas, L. Learning an uncertain world: MIMO covariance matrix optimization with imperfect feedback. IEEE Trans. Signal Process., 64(1), January 2016.
[44] Mertikopoulos, P. and Zhou, Z. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programmiing 173(1-2):465-500 January 2019.
[45] Mertikopoulos, P., Belmega, E. V., Negrel, R., and Sanguinetti, L. Distributed stochastic optimization via matrix exponential learning. IEEE Trans, Signal Process.. 65(9):2277-2299 May 2017.
12

---

[46] Mertikopoulos, P.. Hsieh, Y.-P., and Cevher, V. A unified stochastic approximation framework for learning in games. Mathematical Programming, forthcoming, 2023.
[47] Nemirovski, S. and Yudin, B. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, NY, 1983.
[48] Nielsen, M. A. and Chuang, I. L. Quantum Computation and Quanium Information: 10th Anniversary
Edition. Cambridge University Press, 2010. doi: 10.1017/CB0978D0 1976667.
[49] Perkins, S. and Leslie, D. S. Stochastic fictitious play with continuous action sets. Journal of Economic
Theory, 152:179-213, July 2014.
[50] Perkins, S., Mertikopoulos, P., and Leslie, D. S. Mixed-strategy learning with continuous action sets. IEEE Trans. Autom. Control, 62(1): (3333994,, January 2017.
[51] Preskill, J. Quantum computing in the NISQ era and beyond. Quantum, 2:79, August 2018.
[52] Robbins, H. and Siegmund. D. A convergence theorem for nonnegative almost supermartingales and some applications. Rustagi, (ed.), Optimizing Methods in Statistics. Academic Press, New York, NY. 1971.
[53] Shamir, O. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18,5 2017.
[54] Sion, M. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171 176, 1958.
[55] Spall, J. C. Multivariate stochastic approximation using simultancous perturbation gradient approximation. IEEE Trans, Autom, Control, 37(3):332-33 -332,4,, March 1992.
[56] Taylor, P. D. Evolutionarily stable strategies with two types of player. Journal of Applied Probability, 16 (1):76-83, March 1979.
[57] Telatar, E, Capacity of multi-antenna Gaussian channels. European Transactions on Telecommunications and Related Technologies, 10(6):585-59)) 1999.
[58] Tse, D. and Viswanath, Fundamentals of Wireless Communication, Cambridge University Press, Cambridge, UK, 2005.
[59] 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.
[60] van Apeldoorn, J. and Gily' en, A. Quantum algorithms for zero-sum games. arXiv: Quantum Physics. 2019.
[61] Vovk, V. G. Aggregating strategies. In COLT '90: Proceedings of the 3rd Workshop on Computational Learning Theory, pp. 371-383, 1990.
[62] Yu, W., Rhee, W., Boyd, S. P., and Cioffi, J. M. Iterative water-filling for Gaussian vector multiple-access channels. IEEE Trans. Inf. Theory, 50(1):145-152, 2004.
[63] Yu, Y.-L. The strong convexity of von Neumann's 's entropy. 2015.
[64] Zhong, H.-S., Wang, H., Deng, Y.-.., 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);14604 1460-1463, December 2020.
[65] 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.
13

---

Appendix
In the series of technical appendices that follow, we provide the missing proofs from the main part of paper, and provide some numerical illustrations of the performance of the proposed algorithms. As roadmap, we begin in Appendix A with some auxiliary results that are required throughout our analysis. Subsequently, in Appendices B-D, we provide the proofs of the results presented in Sections 4-6 respectively. Finally, in Appendix E, we provide a suite of numerical experiments to assess the practical performance of (3MW) using the estimators (2PE) and (IPE), and we compare with the full information setting underlying (MMW).
A Auxiliary Results
We now introduce some notation for quantum games in a N-player setting, and explain how the extension from the 2-player setting straightforward.
N-player quantum games. First of all, quantum game Q consists of a finite set of players i E W = (I....,N) N), where each player N /f has access complex Hilbert space Hi Cd. The set of pure states is the unit sphere V, == (// Hi : ll = 1) of H4. We will write 4 = [I, 4, for the space of all ensembles & 14/ ... v)) of pure states b, E V, that are independently prepared by each i E ..
In analogy with the 2-player case, each outcome operator Pw: : H + H defined on the tensor product H = &, Hi of the players' individual state spaces; we further assume that Ewen P. I, thus, the probability of observing Q at state & e y
S2 is associated to positive semi-definite
(v) ( @ MNN P. Pn @ ...&&M sbN)
(A.1)
and, the player's expected payoff at state v will be
( = (UI) = E., Po( U(())
(A.2)
Similarly to the 2-player setting, if each player e N prepares density matrix X; per (I), the expected payoff of player e N under X = (X),...,X, .N) will be
(x(X)=
Σ Ui(w) X1 XN] tr| W X, wE
Xn]
(A.3)
where W, EwEn Pa E for N. Finally, we denote by VX(X) the individual payoff gradient of player under X as
Vi()) = (X)
(A.4)
All other notions are extended, accordingly.
As noted in Section 2, we define the norm || [ur[At]] for any A Hd: i.e., (H4, (1-Ilr) is an
inner-product space. With slight abuse of notation, we define for X = (X)...,,y,, ..) E X its norm as:
|X
Σ
I
(A.5)
,, it holds ||X||e 1, and diam X) = N Lemma A.1. For any X; E X,,
Proof. For the first part, since X, E X, admits an orthonormal decomposition QAQ such that QQ = = I and A = diag(A)................... 2a,) with d d; = 1, and A; 2 0 for all j. Hence
di
di
x = - -rlaa
Σ f=1
(A.6)
f=1
where the last inequality holds, since 0 2 1, and the result follows.
14

---

For the second part, letting X = (X,, XN) and X' = (X) X2y be two points in X, we have
X
|X - X Σ (2 + 211x111))) s 2VN
(A.7)
i=1
and since the equality is attained, we get the result.
Our next result concerns the quanium relative entropy
D(P.X) Σ X,),
(A.8)
where P = (PI,... PN) E X and x= (X,......
Xx) E ri and
D,,,, = (log - X,)]
(A.9)
The lemma will require is semidefinite version of Pinsker's inequality which reads follows: Lemma A.2. For all and X ri(X) we have
D(P.X) 2 2 -
(A.10)
Proof. Focusing on player i N, we will show first that
X,, 2
2 PIP - X2il?
(A.11)
for all P= PP....... E X' and x= (x,,..,, XN) E ri(2).
To this end, we define the function h;: H - as h (X,) = tr[x; log X,1, which is I-strongly convex with respect to the nuclear norm ||-Il [63], and since ||X;lh 2 |Xille for all X; X;, we readily get that h, is I-strongly convex with respect to the Frobenius norm, as well.
Letting (X,, log X; + I, by 1-strong convexity, we have for P (PI..... PN) E X and X (X)..... XN) ri(X):
h; (P;)) 2 (;(X, + (X)) X,)] + - -1P; Xill.
-
= xr[X, log X;] + (P; X;) log x; + tr[P, - X,1 ++1le,, -xili
=r[[P, log X;| 2 -|P
I -
X
(A.12)
where we used that tr[P, X 0. Hence, by reordering, we automatically get that
D;(P,, 2 Z IP, -0-xpp -xilf
(A.13)
Therefore, we have:
D(P,X) 2
Σ i=l
P, X.I1. = -1IPP- -XI
(A.14)
2
and the proof is completed.
B Omitted proofs from Section 4
In this appendix, we develop the basic scaffolding required for the estimators (2PE) and (IPE). We begin with the construction of the estimators' sampling basis, as encoded in Proposition 1, which we restate below for convenience:
Proposition 1. Let E, be defined as E, VS(+1) (A + +, (Af+1A) for j = I....,d- d-
Then, the set ((E,) (Eucheet, (Euckked is an orthonormal basis of Z.
Proof. First of all, note that
0
if # m if f = m
AgcAmn
(B.1)
Akn
15

---

Unit norm.
To begin with, we will show that all elements in & have unit norm. Indeed, we have:
For j = = d - I, we have:
ARt jAUenoon
EEyl = tr 1(i+1) tr
ARR JACHDOAA
Σ
k=1
+(++) tr
Σ
ARR f (A(=)0A)))
=
-
1(++1)
(1+}))
(B.2)
k=1
For k l, we have:
1
1
||exr 11
uree
Aek
+
Akr
Agc
Ark
V2
v2
12
v2
tr
Akk
Art
=1
(B.3)
2
For k C, we also have:
i
|@er|1 ur(e
Excl
=tr
Ack
- Akt
Akt
Ark
V2
V2
V2
v2
[
1
1
ARk
2
Arc
=
=1
(B.4)
Orthogonality.
Now, we will show that any two elements of & are orthogonal to each other.
For < n, we have:
tr E En
ALR mA m& (m=)))mmm))
Σ Aua nA (A
Vm + 1) Dvnnn+1
tr Σ Akk (m++)))mmt))
vm(m + 1) Dnn
(m m) = =0
(B.5)
Vm(m + 1) [n(++1)
For & l, we have:
i
i
tr[e Eurl tr
Ark Avt
Aut
Ark
V22
V2
V22
v2
i
i
2 Acc
ARk
(B.6)
2
2
For () (m with k and n, we have:
a e Eme tr urre e tr e emn =
(B.7)
since all the nonzero terms in e Cmn, e 6mm and e 6mm are of the form Aag for some E C, and a {k, l, m, n} with a # B. Thus, tr(c- Aap since all the diagonal elements are equal to O. Note that it is not possible to have = B because this would imply that (k, E) = (m,
For k & and ......d d we have:
e E. tr tr(ettEE,) =
(B.8)
since the non-zero terms of both e,, E, and et E, are of the form Akn. Arm for k * and #
16

---

We thus conclude that any two elements of & are orthogonal.
Finally, it is clear & aff Xo), since & Hd and tr[ear] tr @ tr [r[E]] and j = 1 1....., - 1. Therefore, the elements in & form an orthonormal basis a and dim (af) d2 11 1.
0. for k t
We now proceed with the construction of the precise "safety net" that guarantees that the sampling perturbation of the gradient estimator remains within the problem's feasible region. Again, for convenience, we restate the relevant result below:
v Vaid-1j d it holds that R + rZ E X for
Proposition 2. Let R à Ejz Ai.. Then, for min
any direction 7. E E²
Proof. To begin with, it is clear that e Hd and tr[] -ز=1 1/d Moreover, for any Cdd \\ (0), we have:
Ru=
Σ
(B.9)
j=1
where |رyا is the modulus of the complex number "j E C. Therefore, R is positive definite, i.e., lies ri))).
Now, we need to find r > 0 such that
R rZ X
(B.10)
for any 8
is clear that for any Z E 8t, we have tr[R+ + +r] = =tr[R]= = 1, since tr|2] = 0. Hence, remains to consider the positive semi-definite constraint. For this, we will the following identities, for k &:
u' (ARe Ack)u ügue + ueug = 2Re(ūgut)
(B.11)
and
uiAer - iAca)u = i(ūuue ūrux) = - (m
(B.12)
For == 1/ (ARe And) and Cd ((0), and using (B.11), we have: v2
u² (R+r
1
Σ
d
|ay12
r
2Ro(ūuu))
d
V2
1
rd 1 (Iual² luel2 2Re(()u))
Σ
1
(B.13)
d
v2
jækil
If Re(ūgu)) O, we get that u''R+ rZ)u O, while if Re(ūku)) s 0 and r
v2/d:
n'(R + rZ)u 2
Σ luz|2 7 lux + uzl 20
(B.14)
Jzk.
Hence, for r S 22/d. and Z + ( Acx), we have that u' (R + rZ)u 2 0 for all u e Cd.
For = - V5 (Are Ark), we have
1 d
[R+++ZZu
Σ
|111
r -2Re(ūnue)
V2
j=l
á
1
Σ
| + 1 |luel luel fuef- rd
v2
2Re(axu))
(B.15)
f+k.l
If Re(ūgu)) O, get that u'(R Z)
0, while if Re(ūgut) and r v2/d:
R + + 2 d
Σ 1 -lu url 0
(B.16)
jæk.(
Hence, for r s v2/d, and Z. = - (Aer Are), we have that a²( (R + rZ)u 2 0 for all u e Cd.
17

---

For Z = 1 (Axc AAr) and E Cd
{0}, and using (B.11), we have:
V/
d
d |
r
21m 2lm(
v2
1
Σ
luil²
2 [leal lurl - rd
21m(
(B.17)
à
v2
jak,t
If [m(ūgue)) < O, we get that u'RR+ rZ) > 0, while if Im( 2 and r z V2/d:
u' + rZ)u 2 d
Σ
|u,|= gluz + +iul 0
(B.18)
jzh,t
Hence, for r & v2/2d, and 7= (Apr Art), we have that ut (R + rZ)u 2 0 for all u Cd.
V2
For (Axe Aek) and Cd (0), and using (B.11), we have:
42
1
d
rR)u
|
21m(ūuu
d |=1
V2
1
1
I /url 2 rd
Σ
1 12 +
21m(ūuue)
(B.19)
d
v2
jzh.(
If Im(āgue) O, get that u' u'(R+ rZ.uu 0, while if Im(ūgue) 0 and v2/d:
"'(R + rZ) 2
Σ jak!
[ujl 7 Jime - iuul?
(B.20)
Hence, for r s V2/2d, and Z - (ARt Ack). we have that ut uRRR + rZ)u 2 0 for all a e cd.
For
Vi(+t)) (A11+ + :...+.+.AA +Ais j((+))(H)) we have:
jr
u" n2(R+ rZ)u =
uxl²
!ujal?
k=1
vj( + 1)
k=1
vj(+1)
jr
Σ
[uk
[uk 2
(B.21)
k=f+1
VJ
k=1
d VJ(+1)
Thus, we need to ensure that
jr 20
(B.22)
d
VJ(+1)
for all j = 1,..,, d-1 1. Because the function x + Vx(x+ + 1)/x decreasing, it obtains the smallest
value from x d 1. Therefore, for 1/ 1), readily obtain that u (R rZ)u 0 for all Cd.
For
(A + + رイ jAG4D04)) we have: Vs(++)
n2(R+
Σ
|
Iujil?
7
k=l
NJ(+ + 1)
R=
VjU +
1
Σ EuuR +
1
Σ
d
|
jr
(B.23)
d
Nj(+I
+1)
k=1
k=j+1
vj(i+1]
Thus, we need to ensure that
r
20
(B.24)
d
JJU + 1)
18

---

for all I....,dd. d 1. Because it holds that
1
1 jr
(B.25)
à
VJ(+1) d
1)
we obtain the inequality for free by the previous case, i.e., for 1/ 1/vd(d-1). Therefore, for
v2 min Vd(d- -
(B.26)
readily obtain that u'RR (R+ for all Cd, and our proof is complete.
C Omitted proofs from Section 5
Our aim in this appendix will be prove the basic guarantees of (3MW) with payoff-based feedback. The structure this appendix shadows that Section 5 and is broken into two parts, depending on the specific type of input available to the players. The only point of departure is the energy inequality of Lemma 1, which is common to both algorithms, and which we restate and prove below:
Lemma 1. Fix some P E X, and let X, X be two successive iterates of (3MW), without any assumptions for the imput sequence V.. We then have
y2 11
D(P, $ D(P,X, + u
(18)
Proof. By the definition of D, is easy that for e X and X, X' ri(X), have
D(P.X) D(P, D(X.X) tro X' log X) P)]
(C.1)
Since V4(X) = log X I, the above equality can be written as:
D(P.X') D(P.X) + D(X.X') (r((()))(((((()) Vh(X)) P)]
(C.2)
Setting X as X and X' as X,, and invoking the easily verifiable fact that VI(X,1))VV(XXX = y Vi, get
D(P, X,) = (PP, X.+1) D(X++) X,) (X P)]
(C.3)
and hence:
D(P, X,+1) D(P.X) - D( X,) + tVV, - P)]
s D(P,X,) 3 |X - X, ur| (X.+1 PP]
D(P.X,,) ||X,+1 X, 11 + 7, tr| I.
P)] + tr xx)]
D(P.X,) y ur V (X, P)] y V 11
(C.4)
2
where the first inequality holds due to Lemma A.2, and the last step we used that || || is an inner-product norm X,
y i .I 2 urV, xX)I
2 X
X,1
(C.5)
This concludes our proof.
With this template inequality in hand, we proceed with the guarantees of (3MW) in the next sections.
19

---

C.1. Learning with mixed payoff observations. We begin with the statistics of the 2-point sampler
(2PE), which we restate below: Proposition 3. The estimator (2PE) enjoys the conditional bounds
| [F] v(X+)lF 4DL6, and (ii) E 11 s 16D2
(19)
Proof. We prove each part separately.
(i) Let / and | be defined for players E (1,2) as
- = (x(,) it + $2,6;74,1) - Xi.
di. + 81 (R; -x,1) 8, St,1 St. - (R, Xx.))
_RR
(C.6)
nl
n1
and
1 - (x(.) - XX,, 6, -si. - -RR - X1.1) -X.1)
(C.7)
11
Taking first-order Taylor expansion of ue, we obtain:
(x (6) s,ū, = (X,, +
Σ tr Vx (2() jEN
(C.8a)
and
(X(X| (6) - s,,,Z,) = (X,)
Σ tr Vx ( X1) (X) / + +2((E
(C.8b)
JEN
where R-(-) is the 2nd order Taylor remainder. Now, for # E N, since st, is zero-mean and independent of any other process:
B tr V Vxpui(x,
(E)) - = si.zai Fr =0
(C.9)
and using that [ - - 25 o Zi,ro we have:
(X)
- - st.
Fz
E|tr (X (2 (, Zi. I Fi,
26, E
Zi,1 Js,, | [ii
26, F( V,(X,) Zi. 77,, [F)
28, Σ tr (V,
D;
Wee
28,
28, D, proje, (V,(X,))
VX())) (C.10)
D,
where in the last step, with a slight abuse of notation, we identify proje, (Vx(X)) with VX())). The reason for this is that we apply the differential operator V,(X,) only on elements of X;, and thus, we can ignore the component of VX(X,) that is orthogonal to span(E,).
Moreover, have that
L |
(R(E
)
IP L8;
(C.11)
2
and similarly, we get the same bound for [R |. Therefore, in light of the above, we obtain the bound:
- s D,
(C. 12)
and, hence
[E[V, [F] V(X))l v2 DLS,
(C.12b)
20

---

(ii) By the definition of Vi., we have:
Dj 26,
[V
M; (X; s, Z,) -x((; 6, 2,) I1s,,
Di 26,
Gl|2s, 6, Z,Il V2D,G
(C.13)
and therefore, readily obtain that:
E elIV |r & 2D?G2
(C.14)
so
E Fi - 4D
(C.15)
and our proof is complete.
With all these technical elements in place, we finally in position to prove our convergence result for (3MW) run with 2-point gradient estimators. As before, we restate our result below for convenience:
Theorem
Suppose that each player of a 2-player zero-sum game Q follows (3MW) for epochs with learning rate sampling radius ò. and gradient estimates provided by (2PE). Then the players' empirical frequency of play enjoys the duality gap guarantee
H +DD
E G (X+) S
(15)
yT
where H = log( In particular, yory (DG) ( H8( (H((T) and (8)L))HH(8),, the players enjoy the equilibrium convergence guarantee
E(Gap,,(xr) s 8DG
(16)
Proof. Let X E X be a NE point. By Lemma for P = X", and setting F, = D(X*,XX X,) for all I 1,2..., we have
x _ 112
Fir s F, FF+y - -X)]
(C.16)
2
or, equivalently
-X'
- (F. Fi+1)
1
+ Yt 2
V
(C.17)
V1
Summing over the whole sequence = 1..... T, we get:
T
1 T
L X,)
Σ
(F, Frai)
Σ [=]
Yr Vell
(C.18)
f=1 7/
which can be rewritten by setting yo = 00, as:
Σ
-
xx)I
s
Σ
F
1 Σ
v1
11
(C.19)
1=1
1=1
71
7t-1
1=1
Decomposing V, as
+(x,)
(C.20)
with
(i) b, = E Fi V(X))
(i) U, v, E v, F.
21

---

equation (D.18) becomes:
1
Σ -=l
tr| v(X() (XXX))(X'
-X)]
Σ
F
+ 2
Vr
111I
[=1
1/
1=1
T
+
Σ
[X
- -X'] + Σ (x, -X]]
Σ
7
K
1
1 T
Σ
11
71
Y
2
1=1
T
T
+
Σ
|
Σ
-X']
(C.21)
-
1=1
The left-hand side (LHS) of (D.20) gives:
(X) x1,))+ + > (x - -x,,)
T
(X,. X2,1) =u(()))) + Σ (12(11... X²) -x2(
uz2(x,)
Σ (C() X2.) L(X X²))
(C.22)
Hence, dividing by T, we get:
(2x) -(x,,7, X,) s Σ (X-
(C.23)
1=1
or, equivalently,
Gapz(X7) S = Σ
tr(v(X,)*
(x'-
T [=]
1 T
1
Σ
Fr
+
Σ 7=1
T
71
V1-1
2T
4
T
T Σ
Σ
|b,
ulll 1x, (X, X*)]
(C.24)
T
1=1
1=1
Now, we focus on the right-hand side (RHS) of (D.20). Specifically, we have:
Xx)] = -X,] E[E[t [F,]] =
(C.25)
since X, is F-measurralle and E|U, = O.
Moreover, by Proposition 3, have:
|b; = [ V Fi V:(X.)lF $ L22,L
(C.26a)
and
E
E
FF
4D7G2
(C.26b)
Hence, taking expectation in (D.20), we obtain:
1
T
1
T Σ
4 7 Σ
E E(Gap
X7)
E
F,
Yi
E
V
1111
E[]]b]le]]
7 |=1
Y1
7--1
2T 1=1
T |=1
1
T
1
GD2 T
16DL T
Σ
E(F;
Σ
Y1
2 6,
(C.27)
-=1
Y1
-t-1
1=1
1=1
22

---

Setting and 6, 6, we obtain:
Fi s yr
E E[Gapc(Xx))
- 16DL8
(C.28)
and finally, noting that we get:
Fi = Di= S log(d)d2)
(C.29)
H +DDD
B Gap (X7)
(C.30)
yT
for = (og(d)d2). Hence, after tuning to optimize this last expression, our result follows by G
setting H and ő
STD
8L
C.2. Learning with bandit feedback. We now proceed with the more arduous task of proving the bona fide, bandit guarantees of (3MW) with 1-point, stochastic, payoff- based feedback. The key difference with our previous analysis lies in the different statistical properties of the 1-point estimator (IPE). The relevant result that we will need restated below: Proposition 4. The estimator (IPE) enjoys the conditional bounds
(i) | [F] Vl s 4DLC, and (ii) E[N 4D2
(20)
Proof. We prove each part separately.
(i) Let E defined for all players N::
E. i. X1, = 6, 6,7,, + 5, (R, X,,) = o,
7i, + -(R; Xx.))
(C.31)
ri
1i
Taking first-order Taylor expansion of u; obtain:
(6 + 5,2,) = (X( + Σ (x R2(E,)
(C.32)
jEN
Since [(U)(w,)) F, Z,] (xx o.Z,,), combining it with (D.3), we readily get:
D;
E[V, FF,
(X +6,Z,) Zi,;
(C.33)
6,
Dj
u/ (X,)
Dj 6,
Σ [x) Z.. JEN
DI Pe,,,,,,, (C.34) o,
6,
Now, because E E F, = and Zr, is sampled independent any other process, we have:
E Ex,
Fil (X,) HE E| [ =
(C.35)
and for #
tr V Zin Fr. =0
(C.36)
Therefore, we obtain:
E Σ tr (X,,
Zu Fr
E 'E,, 4 [F]]
JEN
=,, Zz Zz. [F
ö, Σ tr (X,, WW]W
Di WEE,
8,
proje, (V.(X.)) 6, v.(X,)
D; (C.37)
D.
23

---

where in the last step, we identify proje, (X)(X)) with V,(X,), as explained in the proof of Proposition 3. Moreover, we have that
1. (2( V 2 | s L5;
(C.38)
view of the above, we have:
|E 1-)
- Vx),)l D,L5,
(C.39)
and, therefore,
- = V2DLO,
(C.40)
(ii) By the definition of Vi.. we have:
Dj u1 (x, (0) + 6, Zi) IZ,,1l1 1 5,
D
Wulll
(C.41)
6,
and therefore, we readily obtain that:
D2
E
B F.
(C.42)
87
We thus obtain
2D²
E
E
F
(C.43)
87
and our proof is complete.
The only step missing is the proof of the actual guarantee of (3MW) with bandit feedback. We restate and prove the relevant result below:
Theorem 3. Suppose that each player of a 2-player zero-sum game Q follows (3MW) for epochs with learning rate y. sampling radius 6, and gradient estimates provided by (1PE). Then the players' empirical frequency of play enjoys the duality gap guarantee
H
2D²
E (XT)]
+
+ 16DL5
(21)
yT
62
where H log(d)d2). In particular, for the equilibrium convergence guarantee:
H ET
2DVBL.
and 8= =
(77
H
B AL
the players enjoy
2// 8H
c s
(22)
T1/4
Proof. Following the same procedure as in the proof of Theorem 2, we readily obtain:
1 T
Gap (xy)
Σ
tr
((X,)
) (X'
-X)]
T
[=1
1
T
1
<
Σ
Fi
Σ
7:
V 11
[=1
711
71-1
2T 1=1
Σ
bb
+
Σ
ull (x, -X)]
(C.44)
T 1=1
T
1=1
Now, we have:
EX -X X') =
(C.45)
since X, is F-measurable and E Fi] = 0.
24

---

Moreover, by Proposition 4, we have:
|bb,,lle = [V Fi v.(X,)ll $ 2D,Lō,
(C.46)
and
D²
-
=
Fi s
(C.47)
6;
Hence, taking expectation in (D.34), we obtain:
1
1
E Ga (XT))
S
F
Σ
Y1
E[1l
111I+1
Σ
B[[|b]]r]]
T
1-1
Y--1
2T
T
[=1
1 T
1
2D B²
T
16DL
T
Σ
E[F]]
+
Σ 6
(C.48)
T
Y/1
Y1-1
T
8
T
Setting Y/ = y and 6, we obtain:
B[Fi]
2D B²y
Gap (Xr)
+ 16DLS
(C.49)
yT
8²
and finally, noting that
E Fi = D(X*, X1) I log(d)d2)
(C.50)
we get:
H
2D²
E E|Gap (xr) (xr)
+
+ 16DLS
(C.51)
yT
8²
where H = loog(ddd)). Hence, after tuning y and ō to optimize this last expression, our result follows 3/4
by setting y
27
2DVBT. and 5
27
H
1/4
AL
B
D Omitted proofs from Section 6
We provide first the bounds of the estimator (IPE) in N-player quantum game. Formally, we have:
Lemma D.1. The estimator (IPE) in a N-player quantum game Q enjoys the conditional bounds
1 DLN3/26, and (ii) E 1 /
D²B
(i
(D.I)
8
Proof. We prove each part separately.
(i) Let E,, be defined for all players i e N:
B x X1,, 6,Z,, + 5, (R, Xi,)) 6, Zi,, + -(R, Xi.r)
(D.2)
ri
ri
Taking a Ist-order Taylor expansion of uj, we obtain:
(X + 5,,,, = (X, + Σ (x) R2
(D.3)
JEN
Since (w,) F,, Z,] (x O. combining it with (D.3), we readily get:
E d. FF,
D;
(X
(6)
+8,Z,) Zi,
6,
Di
Di
D; R,,E,, (D.4)
Zr,
+ 8, jeN
Ze, Σ tr Vx, [z. 5,
6,
25

---

Now, because E E Fi] = and z is sampled independent of any other process, we have:
[X, Fil u, (X,)
1E Z
Fi]
(D.5)
and for j /
E|r[Vxqu(()) Z1, Fr =0
(D.6)
Therefore, we obtain:
E
Σ tr (X) JEN
Zi F,
=B(urV.,X, E., [z, Fi.]
Eur Z,,1 |Z,, FF]
6, Σ (X,, WWW
Di WEE,
6
proje, (V,(X,)) 6, D (X,,
(D.7)
D.
where in the last step, we identify proje, (V)(X,)) with Vi(X,), explained in the proof of Proposition 3. Moreover, we have that
L |R2(E,)1 s 2 1 / LNO?
(D.8)
In view of the above, we have:
1 D,,LN
(D.9)
and, therefore,
| [=] 2 DDL
1
(D.10)
(i) By the definition of Vi,. we have:
Dj u (X( + 6, Z,) 6,
D.B
|Zi,r|1 s
(D.11)
6,
and therefore, we readily obtain that:
D²B²²
E E[1I F
(D.12)
Hence, ultimately, get the bound
D B
E[| H 11 [F
(D.13)
and our proof is complete.
With all this in hand, we are finally in a position to proceed with the proof of Theorem 4, which we restate below for convenience:
Theorem 4. Fix some tolerance level 1j (0, 1) and suppose that the players of an N-player quantum game follow (3MW) with bandit, realization-baser feedbuck, and surrogate gradients provided by the estimator (1PE) with step-size and sampling radius parameters such thut
i ا Y, 00, (ii) 2 7: < <0, and (ii) 2 2 v:16? < 0o.
(23)
If X* variationally stable, there exists a neighborhoold U of such that
Pllim 00 X, =X") 2 1- whenever X1 Eu.
(24)
26

---

Proof. Since X' is variationally stable, there exists neighborhood Un of it such that
tr[v()(XXX)) <0 for all X E Us )
(D.14)
For any s' > 0, defining
U' = (X : D(X, <
(D.15)
we readily obtain by the continuity of X + D(X,,, X) at X that there exists neighborhood of X' such that e Us. Note that if 81 < 82, we automatically get that U S g..
In view of this, we let X, E e/44 C u _ Uss We divide the rest of the proof in steps.
Step 1. Deriving the general energy inequality
By Lemma we have that:
D(X D(X.X,,,)) s D(X, X,) + +, VX, (X)] + Yi 1V
(D.16)
2
Decomposing V, into
V, = V(X,) b, + U.
(D.17)
per (C.20) and applying (D.16) inequality iteratively, get that
(+)) & D(X'XX))
Σ Ys tr A - -x)] + 2 Σ &
S D(X''X
Ys tr VXX,) xx) Σ vs (X, -x)
Ys ur (X, - x*) + 2 Σ 11
$ D(X',X) Σ 7s ir - -X)] Σ x11b,lle11x,- -X
Ys trrlU, - -X)] + 2 Σ 1
$ D(X' X1) Σ 7s ((X,,) x*)] + diam(x)) Σ Ysllballe
Ys trrl - -x)] + 2 s=l
Σ 1
(D.18)
s=l
Defining the processes v, M, and 24 for 1,2.... as
1
V. = Σ x21 111
(D.19a)
2 s=l
M, = Σ (X,
(D.19b)
1=1
Z = diam x) Σ Yssllbll
(D.19c)
equation (D.18) can be rewritten as
D(X", X..) XX")Xx) Σ sml
7s -X,
(D.20)
Step 2. Bounding the noise terms
Let & > 0 as defined in the beginning of the proof.
27

---

Regarding the term Z,, it is clear that the process {Z, : 2 1 is sub-martingal. Hence, by Doob's maximal inequality for sub-martingales [24]. we get that:
E[Z,]
P sup Zs e/4 551
8/4
diam( X) E1 Ys B[]|bs]le]
8/4
diam( X) -,m1 Yr [[Ibb,ll]]
8/4
diam(X)) 2 Y1 B| [b,, le [F]
8/4
2 (iam(()))LN Σ 7;0,
(D.21)
8
By ensuring that
oc
Y 6diam (2)
(D.22)
[=
and taking go co, (D.21) becomes:
IP
sup 2, 8/4 S sn/3 /21
(D.23)
Similarly, it is clear that the process ( :12 1} is a mab-martingale. Following the same procedure, by Doob's ss maximal inequality for sub-martingales [24], we get that:
E[V 8/4
y IE
||
1
I
sup x5
V 2 8/4 2
8/4
y EE [IV
t-l
$
8/4
2D B² N ا 17
(D.24)
By ensuring that
Σ 16 = ET
(D.25)
6D2
and taking - co, (D.24) becomes:
P sup V, 2 e/4 $ 1/3 121
(D.26)
Finally, regarding the term M, the process (M, r 1} is martingale. Following the same procedure, by Doob's maximal inequality for martingales [24], we get that:
M[M (c/4)2
E' x (rIIIU -x)]
P sup M, e/4 S P 551
sup M, 2 e/4
(6/4)
Isst
diam
(x)) Σ1 s=1 x E ||
(8/4)2
diam(X E,m ri E [|U,
(8/4)2
4 diam 2 Eie Y E [
(8/4)2
diam(X)) B² E 16,
(D.27)
(s/4)2
28

---

where we used the fact that
E[M,]= = E
Σ (X,
-x)]++
-
x=1
ket
E Σ
(X, -XD1
(D.28)
x=1
itself following from the total expectation
E[ur[Ux(Xx xx)]u[U,(X -X)]] E[E[[T[U, - -X)] -X)] Fil
= E|tr[U; EIT X') Fil
(D.29)
Now, by ensuring that
(8/4)²n
Σ 1
(D.30)
12 12dim dia (x)=
[=1
and taking / go co, (D.27) becomes:
P
sup M, 2 e/4 $ n/3
(D.31)
(21
Therefore, combining (D.23), (D.26) and (D.31) and applying a union bound, we get:
Pi e/4 U sup M, 2 e/4 s
P sup Z, e/4 sup
(D.32)
121
[2)
(12]
Thus, defining the event E (supral Z, V, M, < f6.. Eq. (D.32) readily implies that:
P(E) 2 1 1-
(D.33)
Step 3. X, u with high probability
Since X1 e/4 S Us by induction have that under the event E
D(X, xxx) D(X, Σ ys - +,+ -X
(D.34)
8 8
8
8
4
(D.35)
where in the last step we used the inductive hypothesis that X, E Uvs for all I,....f
which implies tr(V(X,) - XX)] < O. This implies that X,+1 E U2 Uv
Therefore, obtain that X,+1 E E Uvs for all 2 1. For the rest of the proof will work under the event E.
Step 4. Subsequential convergence
Now will show that there exists subsequence (X,, k 2 1) suct that lime so0 X,, X' Suppose it does not. Then, this would mean that the quantity tr[ (X,) -X)] is bounded away from zero. Combining it with the fact that X, Uvs for all 2 O, we readily get that there exists > O such that:
(VV(X,) X-)1 <-C
(D.36)
Then, (D.20) would give:
D(X'X,,,)) S Σn
(D.37)
s=1
Hence, taking co, and using that Σi21 71 = c0, would get that D(X", X,) -00,
which is contradiction, since (XX" X,) 2 0.
Hence, there exists subsequence (X,, k 2 1} suct that lime- X,, = X", i.e.
lim D(X X, 0. k0000
(D.38)
29

---

Step 5. Existence of lom D
We define the sequence of events {E, : 1)
E = sup 1551-1
Z₃ + v, M, 46
for 2
(D.39)
and
E1 = | El1
(D.40)
Then we have that E, E F, and E, & [X, Uss I.....I). Defining the random process
{D, : 2 1] as
D, D(X, x,) LE
(D.41)
Then, by (D.16) have
D(X'Xx++)) & D(X X1) ,, y, trl( - X*) + (iam(X)y
+ txU, X') + 11.11
(D.42)
Multiplying the above relation with 1g, and noting that 1E, S 1E, since Est1 E,, have
D s D, y, trl( X¹) LE, diam diam(X))
1 + tr - X')] 11, 11
(D.43)
S D, diam( (Y)rrlbbrll 18, +y, tr(u; (X, - X')] 1E 1 , 1,,
(D.44)
where in the last step we used that (r(V(X))(,, X')] 18, S. Therefore, we obtain that:
1
B(Dm [F] s D, diam(()) 1 B[[|b, Fi + ア 1e, II (D.45)
where we used that
E/I[V(X)((X - [.] DA
- -X)]
=F =0
(D.46)
Therefore, {D, : 1} is almost super-martingale [52] and, thus, there exists D.. with Dec finite (a.s.) and 1, Do (a.s.).
Since Er, we have:
P lim D(",X,) exists E) 1-000
P( P((lim, DXX X,) exists) n E)
(D.47)
P(E)
P( P((lim, D, exists n E)
(D.48)
P(E)
Hence, lim D, exists E and by Step we readily get that lim, D, 0 on E. Thus, by Lemma A.2, we get
lim X, X* on the event E 1-00
(D.49)
and setting 4 14 e/4, obtain
lim X, =xx= 1-17 whenever X₁ e l.
(D.50)
This concludes our discussion and our proof.
E Numerical experiments
In this last appendix, we provide series additional numerical simulations validate and explore the performance of (MMW) with payoff-based feedback.
30

---

10
10
[1]
E
(a) Full information (MMW).
101
1o
10)
(b) (3MW) with the (2PE) estimator
10
11)
(c) (3MW) with the (IPE) estimator
Figure 2: Trajectories of the three methods for different initial conditions. The red points correspond to player
1, and the blue points to player 2. The initial points of the red trajectories are marked with ,, while the initial points of the blue ones are marked with
Trajectory analysis. First, proceed to trajectory analysis of the game setup presented in Section 7. Specifically, in Fig. 2, we provide visualization of the actual trajectories of play generated by the three methods with the same parameters as before, for different initial conditions. The trajectories are presented in Bloch spheres [48], where the points (0) and [1) in the figure correspond the density matrices
10) !
0)
and 11) = ( !)
(E.1)
respectively. In all figures, the points in red indicate the trajectory of Player 1, while the points in blue are for Player 2. The initial points of the red trajectories are marked with e, while the initial points of the blue ones are marked with [Each column of Bloch spheres in Fig. 2 has the same initial conditions.]
An important remark here is that, suggested by Theorem 4, the trajectories of all methods converge and quite rapidly at that to the game's s (strict) Nash equilibrium. In fact, given that the trajectories converge to pure state, this goes to explain the faster convergence rates observed in Fig. 1: instead
31

---

(a) Performance evaluation and comparison on 22
(b) Performance evaluation and comparison on 23.
(c) Performance evaluation and comparison on Q4-
Figure 3: Performance evaluation of (3MW) with estimators provided by (2PE) and (IPE), and comparison with the information algorithm (MMW).
of oscillating around solution, the MMW orbits actually converge to equilibrium in this case, so the trailing average converges at a much faster rate. This holds in all zero-sum games with pure equilibrium, thus indicating very important class of zero-sum games where the worst-case guarantees of MMW algorithms can be significantly improved.
Convergence speed analysis. In addition to the game setup described in Section 7, we consider the following quantum games:
Q2: quantum analogue of the x min-max game with payoff matrix
( (10, -00)
(10.-10) (-10, (o)
P2 =
(o2)
10, 10)
C3: quantum analogue of the 3 x min-max game with payoff
(4, -4)
(2
(4,
P3 =
(-4.44 4)
(-2,2)
(-4.-4)
(2x)
(-4,4) 4)
(-2.2)
(-4.-4)
Q:: quantum analogue of the x min-max game with payoff
(10. -10)
(10--10)
(10,-10)
P4 (-10, 10)
(-10, 10)
(-10,
(o4)
10, 10)
(-10, 10)
(-10,
32

---

In Fig. 3, we evaluate the convergence properties of (3MW) using the estimators (2PE) and (IPE), and compare it with the full information variant (MMW), following the same setup as described in Section 7. Specifically, for each method, we perform 10 different runs, with 7 = 10 steps each, and compute the mean value of the duality gap as a function of the iteration solid lines correspond to the mean values of the duality gap of each method, and the shaded regions enclose the area of +1 (sample) standard deviation among the different runs. Note that the red line, which corresponds to the full information (MMW), does not have shaded region, since there is no randomness in the algorithm. All the runs for the three different methods were initialized for Y and we used y 10 for all methods. In particular, for (3MW) with gradient estimates given by (2PE) estimator, we used a sampling radius 5 = 10-2, and for (3MW) with (1PE) estimator, we used 8 = 10 (in tune with our theoretical results which suggest the use of tighter sampling radius when mixed payoff information is available to the players). As highlighted in the main text, we observe that the decrease in performance is mild, and the different algorithms achieved better rates than their theoretical guarantees.
1, 2. ..... T. The
33


Reviews:
[{"review_id": "qgtxKdxHcu", "reviewer": "Reviewer_TyoP", "summary": "The authors consider the quantum games in the bandit setting, which players observe only the payoff value of their actions. In order to facilitate this, the authors extend the online bandit estimation methodology into the quantum-state space. As a result, they are able to realize a duality gap of $\\mathcal O(T^{-\\frac{1}{4}})$ and $\\mathcal O(T^{-\\frac{1}{2}})$ for bilinear quantum games.", "questions": "- I would like to inquire about the necessity of the $L$-smooth assumption in the quantum game setting. Specifically, it seems that in classical games or online learning problems, the bandit estimator can be constructed without requiring an $L$-smooth condition. Could the authors elaborate on whether this condition is necessary in the context of quantum games and, if so, could you explain the rationale behind this requirement?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Originality & Significance: Considering the concept of games within quantum state spaces in the bandit setting is innovative, and the result is nice and matches those found in classical matrix games.\n\n- Quality & Clarity: The paper is effectively structured, allowing readers to follow the presented arguments and conclusions with ease.", "weaknesses": "- The applications of blinear quantum games are questionable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging input and positive evaluation. To streamline our response, we reply to your questions and comments in a point-by-point thread below, and we will revise our manuscript accordingly at the next revision opportunity:\n\n---\n\n1. \"*In classical games or online learning problems, the bandit estimator can be constructed without requiring an $L$-smooth condition. Could the authors elaborate on whether this condition is necessary in the context of quantum games and, if so, could you explain the rationale behind this requirement?*\"\n\n   **Reply.** When choosing the sampling direction uniformly at random from the unit sphere - e.g., as in the original paper of Flaxman et al. [17] - Lipschitz smoothness is not required because the resulting estimator is an unbiased stochastic gradient of a suitably \"smoothed\" version of the sampled function. In our case however, uniform sampling from a sphere introduces several computational complications because we need to also respect the eigenvalue constraints of the spectraplex and sample from a specific tangent sphere (by contrast, the original paper of Flaxman et al. only considered sampling from convex bodies, which the spectraplex is not).\n   \n   These complications are not insurmountable, but we found it was computationally much more efficient to use the specific Hermitian frame that we designed in Proposition 1 to pick a sampling direction. When working with this particular sampling frame, Lipschitz smoothness appears in the conditional bounds of Proposition 3, and we are not aware of a technique to get rid of it (essentially because the sampling frame only covers a finite number of directions so it cannot \"smooth out\" the sampled function on its own). However, since quantum games are Lipschtiz smooth by default (thanks to the compactness of the spectraplex and the multilinearity of the players' payoff functions), the smoothness requirement comes \"for free\"; because of this, we leveraged the computational efficiency of the frame derived in Proposition 1.\n\n---\n\n2. \"*The applications of blinear quantum games are questionable.*\"\n\n   **Reply.** Some prominent applications of quantum games involve quantum generative adversarial networks (Q-GANs) [references 11,14,31 in our paper], (robust) shadow state tomography [refs. 1,2 in our paper], the best separable state (BSS) problem [see e.g., L. Gurvits, *Classical deterministic complexity of Edmonds’ problem and quantum entanglement*, STOC 2003], and many others. Admittedly, some of these applications involve quantum games that are not necessarily multilinear, but the theory of online learning in quantum games is still at its early stages, and the class of multilinear quantum games is a natural starting point.\n   \n   At the same time - and perhaps more importantly - it should be noted that our paper provides an **application-agnostic** template for the analysis of the MMW algorithm with bandit information. In particular, our paper's results extend directly to other applications of the MMW algorithm, most notably to online kernel learning [the original motivation of Tsuda et al., ref. 45 in our paper], covariance matrix optimization in vector Gaussian channels [Capacity of multi-antenna Gaussian channels, Telatar, 1999; Yu et al., Iterative water-filling for Gaussian vector multiple-access channels, Transactions of Information Theory, 2004], etc. For example, in the latter case, the game being played has the same player-action structure as a quantum game but with payoff functions \n   $$\n   \\textstyle\n   u_i(\\mathbf{X}) = \\log\\det\\left(\\mathbf{I} + \\sum_j \\mathbf{H}_j \\mathbf{X_j} \\mathbf{H}_j^\\dagger\\right) - \\log\\det\\left(\\mathbf{I} + \\sum _{j\\neq i} \\mathbf{H}_j \\mathbf{X_j} \\mathbf{H}_j^\\dagger\\right)\n   $$\n   where $\\mathbf{H}_i$ is the gain matrix of player $i=1,\\dotsc,N$, and each $\\mathbf{X}_i$ is constrained to lie on the spectraplex $\\mathbf{X}_i \\succcurlyeq 0$, $\\mathrm{tr}(\\mathbf{X}_i) = 1$ (for a detailed formulation, see the paper by Yu et al. above). By the concavity of the $\\log\\det$ function, our analysis extends directly to this setting, simply by replacing the quantum game gap function in Eqs. (C.23) and (C.24) of the appendix with the aforementioned payoff structure.\n   \n   We did not highlight these further applications of our approach because we were constrained by space and we did not want to dilute the focus of our paper. However, we would be happy to take advantage of the extra page provided in the revision phase to detail all this.\n\n\n---\n\nWe hope and trust that these points address your questions - but please let us know if any of the above is not sufficiently clear.\n\nThank you again for your input and positive evaluation,\n\nThe authors"}, {"review_id": "41APX36bry", "reviewer": "Reviewer_G5vn", "summary": "This paper studies Quantum Games (mainly in the two-player zero-sum setting) and develops payoff-based learning algorithms with provable convergence-rate guarantees. The learning algorithm combines matrix multiplicative weights (MMW) and zeroth order method for gradient estimation. The overall convergence rate is either $O(1/\\sqrt{T})$ or $1/T^{1/4}$, depending the information structure. The authors also provide numerical simulations in the appendix to verify the performance of the proposed algorithm.", "questions": "Do the authors expect the bound to be tight? Are there any known lower bounds for the convergence rate in the literature?", "limitations": "The authors did not explicitly point out the limitations of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is very well-written. The appendix is also of high quality. ", "weaknesses": "(1) The learning algorithm combines MMW with zeroth order method for gradient estimation. Since the convergence rate of MMW was established in the literature, and the zeroth order method is well studied in optimization, the technical novelty is not entirely clear. Are there any significant challenges in the analysis? \n\n(2) From Theorem 2, it seems that there are no consequences for choosing $\\delta$ to be arbitrarily small. Am I missing anything?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank your for your input and positive evaluation. To streamline our response, we reply to your questions and comments in a point-by-point thread below, and we will revise our manuscript accordingly at the next revision opportunity:\n\n1. *Do the authors expect the bound to be tight? Are there any known lower bounds for the convergence rate in the literature?*\n\n   In the context of convex-concave min-max problems without access to perfect gradient information, the associated lower bound is $\\Omega(1/\\sqrt{T})$ [Ouyang and Xu, *Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems*, Mathematical Programming, 2021]. In this regard, the $O(1/\\sqrt{T})$ guarantee of the 2PE scheme is order-optimal and cannot be tightened further.\n   \n   The case of noisy function evaluations for 1PE is trickier. For convex **minimization** problems (a simpler class than min-max problems), the best-known lower bound is $\\Omega(D/\\sqrt{T})$ [Dani et al., *The price of bandit information for online optimization*, NeurIPS 2008]. As far as this lower bound is concerned, the guarantee (21) of Theorem 3 is tight in terms of $D$, but not in terms of $T$. To the best of our knowledge, the only implementable algorithm with an $O(1/\\sqrt{T})$ convergence rate under comparable assumptions is the method of Bubeck et al. [*Kernel-based methods for bandit convex optimization*, STOC 2017]. However, this method has a much worse $\\Theta(D^{9.5})$ dependence on the dimension which makes it impractical for most applications.\n   \n   Importantly, the above bounds of Dani et al. and Bubeck et al. both concern **minimization** problems. The min-max case is considerably more complex and much less is known in that case, so we cannot tell whether the bound of Theorem 3 for the 1PE method is tight. We speculate that the dependence on $T$ may be improved via the use of a suitable semidefinite sampling kernel, but this is not clear, and even if true, such a modification would likely come at a cost of a much worse dependence on the dimensionality of the problem.\n   \n   We were constrained by space in our original submission, but we would be happy to use the extra page of the revision to include the above discussion.\n\n---\n\n2. \"*The learning algorithm combines MMW with zeroth order method for gradient estimation. Are there any significant challenges in the analysis?*\"\n\n   First, we would like to point out that the MMW algorithm was conceived as a deterministic algorithm with full access to perfect gradient information. In that sense, it was not a given that it could be combined with a zeroth-order gradient estimator and remain convergent. (As an example to the contrary, Nesterov's accelerated gradient algorithm fails to converge altogether if run with stochastic gradients or zeroth-order estimates)\n   \n   Regarding the specific technical challenges that arise in the matrix setting, most obstacles concerned the design of the Hermitian sampling frame that underlies the definition of estimators 2PE and 1PE (cf. Propositions 1 and 2), and the derivation of the associated bounds for each estimator (Propositions 3 and 4). The reason that this particular frame was required was because the standard zeroth-order sampling scheme of Flaxman et al. [17] involves drawing a sampling direction uniformly at random from a sphere. In our case however, we also had to respect the eigenvalue constraints of the spectraplex and sample from a specific tangent sphere (by contrast, the original paper of Flaxman et al. did not encounter this complication because it only considered sampling from convex bodies, which the spectraplex is not). To circumvent this obstacle, we had to design a Hermitian sampling frame and an associated feasibility correction term that would preserve the structure of the spectraplex (cf. Appendix B). However, because any sampling frame can only cover a finite number of directions, the sampled function was not \"smoothed out\" (as in the case of Flaxman et al.), so the established zeroth-order approximation arguments could not be employed in our case. This then had to be paired with the lengthy calculations involved in Propositions 3 and 4 (cf. Appendix C) that were needed to derive the anytime convergence rates of the 2PE and 1PE schemes in Theorems 2 and 3.\n   \n   Finally, we should also point out that, to the best of our knowledge, there are no comparable results to the sequential convergence analysis of Section 6 for general games, even in the case of MMW with *full* gradient information - at least, we are not aware of a comparable analysis in the literature.\n\n---\n\n3. \"*From Theorem 2, it seems that there are no consequences for choosing $\\delta$ to be arbitrarily small. Am I missing anything?*\"\n\n   This is true. The reason for this is that 2PE is run with mixed payoff observations, so the associated finite difference quotient is uniformly bounded. As a result, the variance of 2PE is always $O(1)$ and its bias can be made arbitrarily small by taking $\\delta \\to 0$, so there is no bias-variance trade-off in (14). The proposed value $\\delta = (G/L) \\sqrt{H/(8T)}$ was only intended to provide a compact expression for the algorithm's end guarantee; in theory, $\\delta$ can be taken as small as the machine precision allows.\n   \n   That said, any measurable error in the observation of the players' mixed payoffs would lead to finite differences that are $O(1)$, even when the sampled points are $O(\\delta)$-close. In this case, 2PE would lead to a bias-variance trade-off similar to that of 1PE, and there would be a distinct disadvantage in taking $\\delta$ arbitrarily small. Thus, in practice, $\\delta$ would be limited by the machine precision of the players' calculating device and the associated floating-point accuracy.\n\n---\n\nPlease let us know if you have any further questions - and thank you again for your input and positive evaluation.\n\nKind regards,\n\nThe authors"}, {"review_id": "XQBmHKuAYg", "reviewer": "Reviewer_Kb52", "summary": "This paper studies online learning of quantum algorithms based on the matrix multiplicative weight (MMW) updates. A main technical contribution is to introduce a weaker version called the minimal-information matrix multiplicative weights (3MW), which only requires zeroth-order gradient sampler and can achieve an overall regret of O(T^{-1/4}). In addition, for N-player quantum games, the paper proved a convergence result that 3MW guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.", "questions": "1. Can the authors further comment on whether the convergence rate of the proposed 3MW algorithm, or in other words the online regret, can be further improved? Given the existence of works such as Gao et al. mentioned above, it would be helpful if the authors can provide a more complete picture here. \n\n2. I’m confused by the sentence “in contrast to classical finite games, quantum games have an infinite continuum of pure states” in the abstract. On classical computers, even if we play games with finite cardinality, we can still choose mixed strategies and the set of probability distributions supported on a finite set can be uncountable.\n\n3. It would in general be helpful if the authors can introduce more on the applications of 3MW. In particular, in MMW the payoff gradient of player i is defined as V_i(X_t). However, in most existing quantum papers, V_i is very simple: the identity function. For instance, in the above Brandao-Svore paper as well as several important follow-up works that solves semidefinite programs with quantum speedup, V_i is the identity function and the update is simply a learning rate \\eta * X_t. \n\nIn all, it’s nice to know that 3MW can be applied with bandit information and for general V_i, but this should probably be further motivated about why we need to consider more complicated V_i’s.\n\n4. In numerical experiments, around Page 29, the authors claimed that the their algorithms achieved a rate of convergence closer O(1/T) instead of the weaker O(1/\\sqrt{T}) or O(1/T^{1/4}) bounds. However, I didn’t see detailed evidence for this; it would be helpful if the authors can present more detailed data and plots for demonstrating this phenomenon.\n\nNote that this is related to my question 1: if the convergence rate is ~O(1/T), the overall online regret will be poly-log. So it is probably worth closer study about this, both theoretically and experimentally.", "limitations": "This work is mainly theoretical so I don't think there are notable limitations, but it would work better if the authors can articulate this more clearly.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "From my perspective, the most notable strength of this paper is the nice observation that less information is required to make MMW works. Considering that MMW has wide applications in quantum algorithms for machine learning and optimization, I believe that the result may be of general interest. Technically, this is achieved by exploiting ideas from machine learning, in particular bandit optimization, which provides interesting perspective for designing future quantum algorithms.", "weaknesses": "The most notable weakness is the claim in intro that the result by Jain and Watrous [21] with O(\\sqrt{T}) regret for quantum online learning algorithms remains the tightest known bound for Nash equilibrium learning in quantum games. This is not true, as a recent paper by Gao et al. https://arxiv.org/abs/2304.14197 gave a quantum algorithm with poly-loga regret for zero-sum games. Compared to this paper, the results obtained by this paper is sub-optimal.\n\nAnother notable weakness is that the dependence in dimension is at least D, and does not present a quantum speedup here. In fact, a main merit of applying MMW into quantum algorithms is that MMW provides fast quantum algorithms for solving relevant problems. An important paper was Brandao and Svore https://arxiv.org/pdf/1609.05537.pdf in FOCS 2017, which can solve semidefinite programs with complexity square-root in D. If the current framework 3MW has at least linear dependence in D, it will prohibit its further applications in quantum computing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your input and positive evaluation. We reply to your questions and comments point-by-point below:\n\n1. \"*[The $O(\\sqrt{T})$ regret of Jain & Watrous is not the tightest known bound.] A recent paper by Gao et al. gave a quantum algorithm with poly-log regret for zero-sum games.*\"\n\n   Thanks for bringing this work to our attention. This paper was posted on arxiv just three weeks before the NeurIPS submission deadline so we were not aware of it at the time, but we will be happy to discuss it in detail in our revision.\n   \n   First, we would like to point out that Gao et al. employ a **quantum algorithm to solve classical, finite zero-sum games**. By contrast, our paper (as well as Jain & Watrous) study **classical computing algorithms for solving quantum games.** These two questions are mutually orthogonal, and it is not possible to compare results across papers: in particular, **Gao et al. do not offer any guarantees for quantum zero-sum games;** their analysis focuses exclusively on the (optimistic) multiplicative weights algorithm for classical, finite zero-sum games, so it does not apply to our context.\n   \n   The quantum speedup of Gao et al. is due to a quantum Gibbs sampling oracle that relies on coherent quantum access to the matrix of the game and the use of quantum registers and quantum RAM storage. In our setting however, we no longer have probability distributions living in the **simplex** but density matrices living in the **spectraplex**, so the quantum sampling oracle cannot be applied. Augmenting the MMW algorithm via the use of quantum computing would be a fruitful direction for future research, but one which lies beyond the scope of our work.\n\n---\n2. \"*The dependence in dimension is at least D, and does not present a quantum speedup. [...] Brandao and Svore (2017) can solve semidefinite programs with complexity square-root in D.*\"\n\n   As above, Brandao and Svore propose a **quantum** algorithm for **classical** semidefinite programs. By contrast, we employ *classical* computing to solve **quantum** games, so an improvement in $D$ would clash with the $\\Omega(D/\\sqrt{T})$ lower bound of Dani et al., *The price of bandit information for online optimization* (NeurIPS 2008). Enhancing MMW via quantum computing would be a fruitful direction for future research, but one which lies beyond the scope of our work.\n\n---\n3. \"*I'm confused by the sentence [regarding pure states] in the abstract.*\"\n\n   The relevant phrase reads \"*quantum games have an infinite continuum of pure states [...] so standard importance-weighting techniques for estimating payoff vectors cannot be employed.*\" This is explained in Section 4.1, where we detail the IWE approach for bandit learning in finite games.\n   \n   In short, the main difficulty is as follows: in classical games, the set of pure strategies is finite, so mixed strategies are purely atomic. By contrast, the set of pure states in quantum games is a Hilbert sphere, so a generic probability distribution over this set would be nonatomic. The IWE approach only makes sense for purely atomic distributions (because it divides by pure strategy probabilities), so it cannot be employed against a continuum of pure actions. Also, in quantum games, we do not have probability distributions but *density matrices*, so the use of IWE techniques is even less relevant.\n\n---\n4. \"*In most existing quantum papers, V_i is the identity function.*\"\n\n   It is not true that $V_i$ is the identity matrix in general - this is not even the case in classical games (where $V_i$ is diagonal, but not the identity). \n   \n   In more detail, the objective function of a quantum zero-sum game is of the form $$L(X,Y) = \\sum _{i,j=1}^{d_1} \\sum _{k,\\ell=1}^{d_2} X _{ij} Y _{k\\ell} W _{ijk\\ell}$$ where $W$ is the game's payoff bi-array (cf. \"Semidefinite Games\" by Ickstadt et al). This gives $V _{ij}^{(1)} = \\sum _{k,\\ell=1}^{d_2} W _{ijk\\ell} Y _{k\\ell}$ for Player 1 (and analogously for Player 2) so, unless $W$ has a very special form (which is not the case even in quantum games coming from *classical* games), there is no reason for $V$ to be the identity matrix (or diagonal).\n\n---\n5. \"*It would be helpful if the authors can say more on the applications of 3MW.*\"\n\n   Just like MMW, 3MW can be applied to online kernel learning [45], covariance matrix optimization in vector Gaussian channels [Telatar, 1999; Yu, Rhee, Boyd & Cioffi, 2004], etc. For example, in the latter case, we have the player-action structure of a quantum game but with payoffs $$\n   u_i(X) = \\log\\det\\left(I + \\sum_j H_j X_j H_j^\\dagger\\right) $$ where $H_i$ is the gain matrix of player $i$, and each $X_i$ lies on the spectraplex. Since $\\log\\det$ is concave, our analysis extends directly to this setting by replacing the quantum game gap function in (C.23) and (C.24) with the above.  [We also note that $V_i$ is not the identity here either.]\n   \n   We did not insist on these further applications because we did not want to dilute the focus of our paper, but we would be happy to take advantage of the extra page to detail all this.\n---\n6. \"*The authors [observed] a rate closer to O(1/T) [...] it would be helpful if the authors can present more detailed data.*\"\n\n   We performed additional experiments to illustrate this behavior in the one-page rebuttal PDF. In more detail, we plotted $T \\mathrm{Gap}(T)$ and $\\sqrt{T} \\mathrm{Gap}(T)$ to estimate the rate of convergence of the duality gap. Our experiments show that both 2PE and 1PE stabilize very close to $1/T$, and are faster than $1/\\sqrt{T}$. This is what motivated our comment that the convergence rate in our experiments is closer to $O(1/T)$ and is due to the fact that the sequence of iterates of MMW/3MW converges itself, not only in time-averages (in line with our analysis in Section 6); we will expand further on this in the final version.\n\n---\nPlease let us know if you have any further questions - and thank you again for your input and positive evaluation."}, {"review_id": "GuzhtLezQh", "reviewer": "Reviewer_UZra", "summary": "The paper studies the setting of learning in quantum games, in the case where agents only have access to a scalar (for instance, a payoff value) instead of their full individual gradient, and have to update their strategies in order to converge to some equilibrium. The primary contribution is a variant of the well-studied MMW algorithm called 3MW, which matches the equilibrium convergence rate of (full information) MMW in 2-player quantum zero-sum games. Moreover, with a relaxation of 3MW’s information requirements (i.e. that players observe a random realization of their payoff observable), the algorithm converges to equilibrium at O(T^{-1/4}) rate. Finally, in general N-player quantum games, a regularized version of 3MW using estimator 1PE is able to locally converge to Nash equilibria that are variationally stable. ", "questions": "In the experiments, 3MW is compared with MMW and is shown to exhibit decent performance even with the lack of information. Does the practical performance of 3MW deteriorate significantly for games of larger dimension? To what extent can we rely on 3MW in practical settings (i.e. large games, games with larger number of players)?", "limitations": "Limitations are very briefly discussed, and perhaps a longer discussion would improve the paper (if space allows)", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper answers an important question in the realm of learning in quantum games - in this framework it is quite unreasonable to assume full information of gradients, especially without properly defining how measurements are made, how players access said measurements etc. Hence, in my opinion the bandit framework is very fitting for the quantum setting, and indeed players should be able to update their strategies in a truly ‘online’ setting using only their measured/realized payoff observable. The techniques used in the paper, while not entirely novel, show interesting similarities and differences between classical and quantum settings. Finally, I think the results on variational stability are quite significant, as not only does this give (to my knowledge) the broadest last-iterate convergence result in N-player quantum games yet, it also points to a potential class of FTRL variants using bandit feedback that could potentially also be convergent in the last-iterate sense.", "weaknesses": "I think overall this is a strong paper, the only issue to me is that most of the techniques and ideas used in the paper are not particularly different from the classical bandit setting. If there is significant technical novelty, it is not made clear to the reader in the main text. I would be very interested to see what the differences are in the analysis between the quantum and classical setting, if there are any.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging input and strongly positive evaluation. To streamline our response, we reply to your questions and comments in a point-by-point thread below, and we will revise our manuscript accordingly at the next revision opportunity:\n\n1. \"*In the experiments, 3MW is compared with MMW and is shown to exhibit decent performance even with the lack of information. Does the practical performance of 3MW deteriorate significantly for games of larger dimension? To what extent can we rely on 3MW in practical settings (i.e. large games, games with larger number of players)?*\"\n\n    **Reply.**  In the current context, the goal of our simulations was to illustrate the behavior of our algorithm in simple examples, providing some additional intuition and corroborating the theoretical results. However, we believe that the performance of the algorithm would remain analogous in larger games. An extensive study of the performance of 3MW in specific game-theoretic scenarios (especially with more players) would be a very fruitful direction, and one that we would seek to undertake in future research to better understand the performance envelope of MMW and 3MW in larger multi-agent systems.\n\n---\n\n2. \"*Most of the techniques and ideas used in the paper are not particularly different from the classical bandit setting. If there is significant technical novelty, it is not made clear to the reader in the main text. I would be very interested to see what the differences are in the analysis between the quantum and classical setting.*\"\n\n   **Reply.** First, we would like to point out that in classical, finite games, the de facto way of learning with bandit-type feedback is via the use of IWE techniques. However, as we explain in Section 4.1, this is not possible in our case because of the quantum / semidefinite nature of the underlying game. More precisely, in a classical game, the set of pure strategies is finite, so any mixed strategy is purely atomic by default. By contrast, the set of pure strategies in quantum games is continuous (a Hilbert sphere), so a generic probability distribution over this set would be nonatomic. The IWE approach only makes sense for purely atomic distributions (because it requires dividing by the probability with which a specific pure strategy was employed), so it cannot be employed in a setting with a continuum of pure actions. In addition, because of the specific setup of quantum games, mixing over this continuum of pure states does not lead to a (continuous) probability distribution, but to a density matrix, so the use of standard bandit techniques based on an IWE approach is made even less relevant.\n   \n   As for the specific technical challenges that arise in the matrix setting, most obstacles concerned the design of the Hermitian sampling frame that underlies the definition of estimators 2PE and 1PE (cf. Propositions 1 and 2), and the derivation of the associated bounds for each estimator (Propositions 3 and 4). The reason that this particular frame was required was because the standard zeroth-order sampling scheme of Flaxman et al. [17] requires drawing a sampling direction uniformly at random from a sphere. In our case however, we also had to respect the eigenvalue constraints of the spectraplex and sample from a specific tangent space (by contrast, the original paper of Flaxman et al. did not encounter this complication because it only considered sampling from convex bodies, which the spectraplex is not). To circumvent this obstacle, we had to design a Hermitian sampling frame and an associated feasibility correction term that would preserve the structure of the spectraplex (cf. Appendix B). However, because any sampling frame can only cover a finite number of directions, the sampled function was not \"smoothed out\" (as in the case of Flaxman et al.), so the established zeroth-order approximation arguments could not be employed in our case. This then had to be paired with the lengthy calculations involved in Propositions 3 and 4 (cf. Appendix C) that were needed to derive the anytime convergence guarantees of the 2PE and 1PE schemes in Theorems 2 and 3 respectively.\n \n---\n\nWe hope and trust that these points address your questions - thank you again for your encouraging remarks and positive evaluation!\n\nKind regards,\n\nThe authors"}]

Author rebuttal:
Dear AC, dear reviewers,

We are sincerely grateful for your time, input and positive evaluation. To streamline the discussion phase, we reply to each reviewer's questions in a separate point-by-point thread below. We only include in this global rebuttal a pdf with some additional experiments to illustrate the convergence of the 3MW framework in different games (including a more precise estimation of its convergence rate).

We defer all other points to the reviewer-specific threads below and we are looking forward to the discussion phase if any further questions remain.

Kind regards,

The authors

Meta-review: This paper studies online learning of quantum algorithms based on the matrix multiplicative weight (MMW) updates. A main technical contribution is to introduce a weaker version called the minimal-information matrix multiplicative weights (3MW), which only requires zeroth-order gradient sampler and can achieve an overall sublinear regret. In addition, for N-player quantum games, the paper proved a convergence result that 3MW guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.

All reviewers believe this paper makes valid contributions to the community. The AC agrees and recommends acceptance.
Decision: Accept (poster)