Introduction
Finding the Nash Equilibrium (NE) of a two-player zero-sum game is a foundational problem across economics, optimization, and machine learning, with applications ranging from robust optimization to Generative Adversarial Networks (GANs). Traditionally, the payoff matrix in these games is assumed to be fixed or drawn from a static distribution.
But what happens if the payoff matrix evolves arbitrarily or adversarially over time?
This paper introduces the Online Matrix Games (OMG) setting to answer this question. In OMG, players engage in a repeated zero-sum game where the payoff matrix changes adversarially each round. The players' goal is to find sequential strategies that compete with the Nash Equilibrium of the long-term average payoff matrix in hindsight. The authors define this objective as minimizing Nash Equilibrium (NE) regret.
The Core Challenge: Individual vs. Nash Equilibrium Regret
The most surprising insight of this work is a formal impossibility result: Individual Regret $\neq$ NE Regret.
The authors mathematically prove that standard approaches from Online Convex Optimization (OCO)—where each player greedily minimizes their own individual regret—are fundamentally insufficient for achieving sublinear NE regret when payoffs change adversarially. If two players play a game where the matrix changes, simply reacting to their own historical losses guarantees they will fail to converge to the NE of the average game. In fact, if both players use algorithms guaranteeing sublinear individual regret, an adversary can construct a sequence of matrices (e.g., alternating variations of "matching pennies") that forces their NE regret to grow linearly ($\Omega(T)$).
Proposed Solutions: Joint Updates
To succeed in the OMG setting, players must abandon individual historical tracking and instead coordinate to solve the saddle point of the historical average game. The authors propose novel joint-update algorithms across two distinct feedback settings:
1. Full Information Setting (SP-RFTL)
When players can see the entire payoff matrix at the end of each round, the authors propose Saddle-Point Regularized Follow-the-Leader (SP-RFTL). Instead of updating independently, both players update jointly by playing the saddle point of the sum of all regularized games observed so far. By using negative entropy as a regularizer, they adapt the algorithm to handle probability simplexes efficiently.
2. Bandit Feedback Setting (BANDIT-OMG-RFTL)
When players only observe the single scalar payoff of the specific actions they chose, the problem becomes significantly harder. Estimating an entire $d_1 \times d_2$ matrix from a single scalar observation seems impossible. To bypass this, the authors design a novel one-point matrix estimator. By allowing players to share their underlying action probability distributions and randomize jointly, they can inversely weight their single observation to create a sparse, unbiased estimator of the full matrix. This estimated matrix is then fed into the SP-RFTL machinery.
Key Theoretical Results
As a purely theoretical contribution focused on algorithm design, the paper establishes rigorous mathematical regret bounds for these methods:
- Full Information Bound: The SP-RFTL algorithm achieves an NE regret of $O(\max\{\ln(d_1), \ln(d_2)\} \ln(T) \sqrt{T})$. Crucially, the dependence on the number of actions ($d_1, d_2$) is logarithmic. This means the algorithm remains highly efficient even in combinatorial games where players have exponentially many available actions.
- Bandit Bound: The BANDIT-OMG-RFTL algorithm achieves a sublinear NE regret of $O((\max\{d_1, d_2\})^{5/3} T^{5/6})$.
Limitations and Future Directions
The authors acknowledge that their regret bound for the bandit feedback setting ($T^{5/6}$) is likely suboptimal. In standard bandit convex optimization, more complex algorithms can achieve bounds closer to $\sqrt{T}$. Furthermore, the bandit algorithm's dependence on the dimension (number of actions) is polynomial, whereas the full-information setting enjoys a much tighter logarithmic dependence.
For future work, the authors suggest integrating more sophisticated techniques from recent bandit convex optimization literature—such as kernel-based methods—to improve the $T^{5/6}$ bound and reduce the dimensional dependence.
Summary updated