Payoff-based learning with matrix multiplicative weights in quantum
  games
Kyriakos Lotidis Panayotis Mertikopoulos Nicholas Bambos Jose Blanchet
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.