# Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 49 references that are in the map.
- First posted on arXiv 19 May 2025.

## Builds on (most cited first, 16 of 16)

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Evolution-Guided Policy Gradient in Reinforcement Learning](https://mlsanity.com/paper/1805.07917/) (2018)
- [CEM-RL: Combining evolutionary and gradient-based methods for policy search](https://mlsanity.com/paper/1810.01222/) (2018)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Evolutionary Reinforcement Learning: A Survey](https://mlsanity.com/paper/2303.04150/) (2023)
- [Bridging Evolutionary Algorithms and Reinforcement Learning: A Comprehensive Survey on Hybrid Algorithms](https://mlsanity.com/paper/2401.11963/) (2024)
- [No-Regret Learning in Unknown Games with Correlated Payoffs](https://mlsanity.com/paper/1909.08540/) (2019)
- [Matrix games with bandit feedback](https://mlsanity.com/paper/2006.05145/) (2020)
- [ERL-Re2: Efficient Evolutionary Reinforcement Learning with Shared State Representation and Individual Policy Representation](https://mlsanity.com/paper/2210.17375/) (2022)
- [Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games](https://mlsanity.com/paper/2405.06797/) (2024)
- [Novelty Search in Competitive Coevolution](https://mlsanity.com/paper/1407.0576/) (2014)
- [Runtime Analysis of Competitive co-Evolutionary Algorithms for Maximin Optimisation of a Bilinear Function](https://mlsanity.com/paper/2206.15238/) (2022)
- [Optimistic Thompson Sampling for No-Regret Learning in Unknown Games](https://mlsanity.com/paper/2402.09456/) (2024)
- [Overcoming Binary Adversarial Optimisation with Competitive Coevolution](https://mlsanity.com/paper/2407.17875/) (2024)

## Abstract (arXiv)

Learning in games is a fundamental problem in machine learning and artificial intelligence, with numerous applications~citepsilver2016mastering,schrittwieser2020mastering. This work investigates two-player zero-sum matrix games with an unknown payoff matrix and bandit feedback, where each player observes their actions and the corresponding noisy payoff. Prior studies have proposed algorithms for this setting~citepo2021matrix,maiti2023query,cai2024uncoupled, with citeto2021matrix demonstrating the effectiveness of deterministic optimism (e.g., ucb) in achieving sublinear regret. However, the potential of randomised optimism in matrix games remains theoretically unexplored. We propose Competitive Co-evolutionary Bandit Learning (coebl), a novel algorithm that integrates evolutionary algorithms (EAs) into the bandit framework to implement randomised optimism through EA variation operators. We prove that coebl achieves sublinear regret, matching the performance of deterministic optimism-based methods. To the best of our knowledge, this is the first theoretical regret analysis of an evolutionary bandit learning algorithm in matrix games. Empirical evaluations on diverse matrix game benchmarks demonstrate that coebl not only achieves sublinear regret but also consistently outperforms classical bandit algorithms, including exptr~citepauer2002nonstochastic, the variant exptrni~citepcai2024uncoupled, and ucb~citepo2021matrix. These results highlight the potential of evolutionary bandit learning, particularly the efficacy of randomised optimism via evolutionary algorithms in game-theoretic settings.