Logarithmic Regret for Matrix Games against an Adversary with Noisy Bandit Feedback

Arnab Maiti, Kevin G. Jamieson, Lillian J. Ratliff

Abstract

This paper considers a variant of zero-sum matrix games where at each timestep the row player chooses row $i$, the column player chooses column $j$, and the row player receives a noisy reward with mean $A_{i,j}$. The objective of the row player is to accumulate as much reward as possible, even against an adversarial column player. If the row player uses the EXP3 strategy, an algorithm known for obtaining $\sqrt{T}$ regret against an arbitrary sequence of rewards, it is immediate that the row player also achieves $\sqrt{T}$ regret relative to the Nash equilibrium in this game setting. However, partly motivated by the fact that the EXP3 strategy is myopic to the structure of the game, O'Donoghue et al. (2021) proposed a UCB-style algorithm that leverages the game structure and demonstrated that this algorithm greatly outperforms EXP3 empirically. While they showed that this UCB-style algorithm achieved $\sqrt{T}$ regret, in this paper we ask if there exists an algorithm that provably achieves $\text{polylog}(T)$ regret against any adversary, analogous to results from stochastic bandits. We propose a novel algorithm that answers this question in the affirmative for the simple $2 \times 2$ setting, providing the first instance-dependent guarantees for games in the regret setting. Our algorithm overcomes two major hurdles: 1) obtaining logarithmic regret even though the Nash equilibrium is estimable only at a $1/\sqrt{T}$ rate, and 2) designing row-player strategies that guarantee that either the adversary provides information about the Nash equilibrium, or the row player incurs negative regret. Moreover, in the full information case we address the general $n \times m$ case where the first hurdle is still relevant. Finally, we show that EXP3 and the UCB-based algorithm necessarily cannot perform better than $\sqrt{T}$.

Introduction

In the field of online learning, the $\sqrt{T}$ regret rate is often viewed as an unavoidable consequence of adversarial environments. For zero-sum matrix games with noisy feedback, standard algorithms like Hedge or EXP3 have long been the baseline, consistently yielding $\sqrt{T}$ regret. This paper challenges that paradigm, demonstrating that by leveraging the specific structure of matrix games, it is possible to achieve instance-dependent polylogarithmic regret, even when facing an adversarial opponent.

The Problem: Nash Regret vs. External Regret

The core challenge lies in minimizing Nash Regret. Unlike external regret, which compares performance to the best fixed strategy in hindsight, Nash Regret compares the player's total reward to the value of the game's Nash Equilibrium ($V^*$). In a repeated game with an unknown matrix $A$, the row player must contend with two primary difficulties: the stochastic noise in reward samples and an opponent who actively seeks to minimize the row player's gains.

Existing literature, including recent UCB-style approaches, suggested that $\sqrt{T}$ was the optimal rate. This work identifies that these algorithms fail to reach logarithmic rates because they are either "myopic" (ignoring game structure) or "action-ignorant" (failing to track the opponent's specific choices).

Proposed Methodology

To overcome the $\sqrt{T}$ barrier, the authors propose a two-phase algorithmic framework designed to exploit game structure while remaining robust to adversarial play:

  1. The Burn-in Phase (Support Identification): The algorithm plays the Nash Equilibrium of the empirical average matrix until it can statistically guarantee the identification of the $k \times k$ sub-matrix containing the true Nash Equilibrium support.
  2. The Subroutine Phase (Doubling Trick): Once the support is identified, the algorithm enters epochs of increasing length. It employs a descent-based subroutine that uses the opponent's specific actions to make fine-tuned adjustments to the row player's strategy.

Crucially, while standard algorithms like UCB react too slowly to the adversary (at a rate of $T^{-3/2}$), the proposed algorithm reacts at a rate of $T^{-1}$. This faster reaction is sufficient to cancel out adversarial influence without being derailed by stochastic noise.

Key Results and Comparison

The theoretical analysis proves that while Nash Regret can be logarithmic, external regret cannot (Theorem 3), marking a fundamental separation between these metrics. The proposed algorithm achieves a Nash regret of $O(\frac{(\log T)^2}{\Delta_A})$ in the full-information setting for general $n \times m$ games and in the bandit setting for $2 \times 2$ games.

Comparison of algorithms and their regret bounds across different feedback settings.

As shown in the table above, the new algorithm is the first to provide provable polylogarithmic regret in these settings, whereas traditional methods like Hedge, FTRL, and UCB are limited to $\Omega(\sqrt{T})$ regret even in simple $2 \times 2$ cases.

Conclusion

This research provides the first instance-dependent guarantees for matrix games in the regret setting. By demonstrating that logarithmic regret is achievable, the authors open new avenues for designing non-myopic learning agents. Future work remains to bridge the "bandit gap" for general $n \times m$ games and to refine the dependence on the size of the Nash Equilibrium support.

Summary updated

Abstract

This paper considers a variant of zero-sum matrix games where at each timestep the row player chooses row $i$, the column player chooses column $j$, and the row player receives a noisy reward with mean $A_{i,j}$. The objective of the row player is to accumulate as much reward as possible, even against an adversarial column player. If the row player uses the EXP3 strategy, an algorithm known for obtaining $\sqrt{T}$ regret against an arbitrary sequence of rewards, it is immediate that the row player also achieves $\sqrt{T}$ regret relative to the Nash equilibrium in this game setting. However, partly motivated by the fact that the EXP3 strategy is myopic to the structure of the game, O'Donoghue et al. (2021) proposed a UCB-style algorithm that leverages the game structure and demonstrated that this algorithm greatly outperforms EXP3 empirically. While they showed that this UCB-style algorithm achieved $\sqrt{T}$ regret, in this paper we ask if there exists an algorithm that provably achieves $\text{polylog}(T)$ regret against any adversary, analogous to results from stochastic bandits. We propose a novel algorithm that answers this question in the affirmative for the simple $2 \times 2$ setting, providing the first instance-dependent guarantees for games in the regret setting. Our algorithm overcomes two major hurdles: 1) obtaining logarithmic regret even though the Nash equilibrium is estimable only at a $1/\sqrt{T}$ rate, and 2) designing row-player strategies that guarantee that either the adversary provides information about the Nash equilibrium, or the row player incurs negative regret. Moreover, in the full information case we address the general $n \times m$ case where the first hurdle is still relevant. Finally, we show that EXP3 and the UCB-based algorithm necessarily cannot perform better than $\sqrt{T}$.
BibTeX
@inproceedings{maiti2023logarithmic,
  author = {Arnab Maiti and Kevin G. Jamieson and Lillian J. Ratliff},
  title = {{Logarithmic Regret for Matrix Games against an Adversary with Noisy Bandit Feedback}},
  booktitle = {SAGT},
  year = {2023},
}
Figure