# Matrix games with bandit feedback

arXiv: https://arxiv.org/abs/2006.05145 · HTML: https://mlsanity.com/paper/2006.05145/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2020.

## Built on by (most cited first, 16 of 16)

- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games](https://mlsanity.com/paper/2303.10565/) (2023)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret](https://mlsanity.com/paper/2602.06348/) (2026)
- [Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions](https://mlsanity.com/paper/2605.09363/) (2026)
- [Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games](https://mlsanity.com/paper/2502.09780/) (2025)
- [Optimistic Thompson Sampling for No-Regret Learning in Unknown Games](https://mlsanity.com/paper/2402.09456/) (2024)
- [Is Thompson Sampling Susceptible to Algorithmic Collusion?](https://mlsanity.com/paper/2405.17463/) (2024)
- [Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2506.14518/) (2025)
- [Minimax Last-Iterate Convergence in Matrix Games with Observed Actions](https://mlsanity.com/paper/2609.34656/) (2026)
- [Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback](https://mlsanity.com/paper/2505.13562/) (2025)
- [Learning in Matching Games with Bandit Feedback](https://mlsanity.com/paper/2506.03802/) (2025)
- [No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics](https://mlsanity.com/paper/2604.05129/) (2026)
- [Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback](https://mlsanity.com/paper/2609.34812/) (2026)
- [Thompson Sampling for Learning in Zero-Sum Games](https://mlsanity.com/paper/2610.18899/) (2026)

## Abstract (arXiv)

We study a version of the classical zero-sum matrix game with unknown payoff matrix and bandit feedback, where the players only observe each others actions and a noisy payoff. This generalizes the usual matrix game, where the payoff matrix is known to the players. Despite numerous applications, this problem has received relatively little attention. Although adversarial bandit algorithms achieve low regret, they do not exploit the matrix structure and perform poorly relative to the new algorithms. The main contributions are regret analyses of variants of UCB and K-learning that hold for any opponent, e.g., even when the opponent adversarially plays the best-response to the learner's mixed strategy. Along the way, we show that Thompson fails catastrophically in this setting and provide empirical comparison to existing algorithms.