Payoff-based learning with matrix multiplicative weights in quantum games
Not on the map. Why?
Abstract (arXiv)
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 O(1/√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 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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 16 of its 61 references that are in the map. First posted on arXiv 4 Nov 2023.
Builds on
16 of 61 references.
References · 16
- 2018Quantum generative adversarial networkscited by 128
- 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
- 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 105
- 2016Learning in games with continuous action sets and unknown payoff functionscited by 78
- 2016Kernel-based methods for bandit convex optimizationcited by 63
- 2018Online Learning of Quantum Statescited by 37
- 2019Quantum Wasserstein Generative Adversarial Networkscited by 33
- 2018Bandit learning in concave N-person gamescited by 32
- 2022A unified stochastic approximation framework for learning in gamescited by 22
- 2019Sublinear quantum algorithms for training linear and kernel-based classifierscited by 19
- 2018Learning with minimal information in continuous gamescited by 7
- 2016Distributed stochastic optimization via matrix exponential learningcited by 6
4 more
- 2016Quantum Speed-ups for Semidefinite Programmingcited by 6
- 2023Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Gamescited by 6
- 2020Sublinear classical and quantum algorithms for general matrix gamescited by 4
- 2022Semidefinite gamescited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.