Payoff-based Learning with Matrix Multiplicative Weights in Quantum Games

Kyriakos Lotidis, Panayotis Mertikopoulos, Nicholas Bambos, Jose H. Blanchet

TL;DR

Existing algorithms for learning equilibria in quantum games—such as Matrix Multiplicative Weights (MMW)—require full knowledge of game dynamics or payoff gradients. This paper introduces 3MW (Minimal-Information MMW), a gradient-free, payoff-based framework that enables players to reach Nash equilibria using only scalar reward feedback. Remarkably, when players can observe two mixed payoffs per step, 3MW achieves an $\mathcal{O}(1/\sqrt{T})$ convergence rate that matches full-information algorithms, while single-point bandit feedback yields an $\mathcal{O}(T^{-1/4})$ rate.

What Problem Does This Paper Address?

In quantum games, players choose quantum states (represented by density matrices on the unit-trace positive semidefinite cone, or "spectraplex") and receive rewards determined by quantum measurements (positive operator-valued measures, or POVMs).

While the Matrix Multiplicative Weights (MMW) algorithm converges to minimax equilibrium in two-player zero-sum quantum games at a rate of $\mathcal{O}(1/\sqrt{T})$, it relies on full information—meaning agents must observe their exact payoff gradient matrices. In real-world decentralized or online settings, agents typically observe only their own scalar payoffs.

Standard bandit techniques from classical game theory (like the EXP3 importance-weighted estimator) fail in quantum games for two reasons:

  1. Continuous action spaces: Unlike classical finite games with a discrete set of pure actions, quantum games have a continuous infinity of pure states (points on the Bloch sphere) whose payoffs are correlated.
  2. Quantum measurement noise: The POVM measurement process injects inherent stochasticity into the realized reward even after actions are fixed.

Methods

The authors reframe quantum games as continuous games played over the spectraplex $\mathcal{X} = \{X \in \mathbb{H}_+^d : \text{tr}(X) = 1\}$ and design a zeroth-order gradient estimator tailored to semidefinite geometry:

  • Tangent Space Basis: The algorithm constructs an orthonormal basis $\mathcal{E}$ for the subspace of traceless Hermitian matrices $\mathcal{Z} = \{Z \in \mathbb{H}^d : \text{tr}(Z) = 0\}$, consisting of diagonal traceless matrices and symmetric/antisymmetric off-diagonal elements.
  • Safety Net & Feasibility Adjustment: Because perturbing a boundary density matrix along $Z \in \mathcal{E}$ can violate positive semidefiniteness, iterates are contracted toward a reference state $R = \frac{1}{d}I$ before perturbation: $$X^{(\delta)} = X + \frac{\delta}{r}(R - X)$$ with safety radius $r = \min\{1/\sqrt{d(d-1)}, \sqrt{2}/d\}$.

  • Two Estimator Variants:

  • Two-Point Estimator (2PE): Players query two exploration points ($X^{(\delta)} \pm s\delta Z$). Due to multilinearity, the second moment of the gradient estimate is $\mathcal{O}(1)$, removing the variance blowup.
  • One-Point Estimator (1PE): In true bandit settings, players observe only a single realization $U_i(\omega_t)$ from the quantum measurement. The estimator scales as $\mathcal{O}(1/\delta_t)$, creating a bias-variance dilemma.

Datasets

Not discussed in the paper. The work is theoretical and evaluated on synthetic quantum game testbeds, specifically quantum extensions of standard $2 \times 2$ and $3 \times 3$ matrix games (e.g., zero-sum games where payoffs are encoded into diagonal Hermitian matrices).

Key Insights and Ideas

  • Zeroth-order optimization adapts to quantum geometry: Estimating gradients over the spectraplex requires respecting both the linear trace constraint and the non-linear positive-semidefinite cone. Shifting toward the maximally mixed state $I/d$ creates a guaranteed "cushion" for exploration.
  • Zero asymptotic penalty for two-point scalar feedback: Despite observing only scalar mixed payoffs instead of full $d \times d$ gradient matrices, 2PE retains the $\mathcal{O}(1/\sqrt{T})$ rate of full-information MMW. The cost of scalar feedback appears strictly as a dimension-dependent constant ($D = d^2 - 1$).
  • Trajectory convergence to strict equilibria: Unlike classical zero-sum games where MMW dynamics can cycle, orbits in quantum games with strict/pure Nash equilibria collapse rapidly into the corner states of the Bloch sphere, producing empirical convergence rates closer to $\mathcal{O}(1/T)$ in practice.

Key Results

  • Deterministic / Two-Point Feedback (Theorem 2): (3MW) + (2PE) achieves an expected duality gap of: $$\mathbb{E}[\text{Gap}_{\mathcal{L}}(\bar{X}_T)] \le 8DG\sqrt{\frac{2H}{T}} = \mathcal{O}\left(\frac{1}{\sqrt{T}}\right)$$ matching the rate of full-information MMW, where $D = \max_i(d_i^2 - 1)$ and $H = \log(d_1 d_2)$.

  • Stochastic Bandit Feedback (Theorem 3): Under single-point observation of POVM measurement outcomes, (3MW) + (1PE) achieves an expected duality gap of: $$\mathbb{E}[\text{Gap}_{\mathcal{L}}(\bar{X}_T)] = \mathcal{O}\left(T^{-1/4}\right)$$

  • General $N$-Player Quantum Games (Theorem 4): In $N$-player non-zero-sum quantum games, a regularized 3MW variant provides last-iterate convergence: iterates converge locally to any variationally stable equilibrium with probability at least $1 - \eta$.

Limitations and Future Work

  • Rate gap for 1PE: The single-point bandit rate is $\mathcal{O}(T^{-1/4})$, trailing the $\mathcal{O}(T^{-1/2})$ rate of full information. While kernel-based methods could theoretically bridge part of this gap, they typically incur severe dimension dependencies.
  • Curse of dimensionality: The dimension parameter $D = d^2 - 1$ scales exponentially with the number of qubits ($d = 2^n$), posing scalability challenges for multi-qubit systems.
  • Local convergence in general games: For general $N$-player games, the guarantees are purely local and apply specifically to variationally stable equilibria; establishing convergence rates for this setting remains an open question.

Summary updated

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.
BibTeX
@inproceedings{lotidis2023payoff,
  author = {Kyriakos Lotidis and Panayotis Mertikopoulos and Nicholas Bambos and Jose H. Blanchet},
  title = {{Payoff-based Learning with Matrix Multiplicative Weights in Quantum Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=DCIsNIUCV7},
}
Figure