Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback
Shishen Lin · 2025
Read Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback by Shishen Lin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13562.txt.
Introduction
Shishen Lin studies learning in two player matrix games when payoffs are hidden and feedback is noisy, in a 2025 paper. Each player sees only their own move and a noisy reward. Prior work leaned on fixed optimism, always assuming the best plausible payoff, and reached slow growing regret.
Whether randomized optimism, sampling hopes rather than fixing them, can do as well in games was open. Lin builds a co evolving scheme where strategies compete and adapt against each other. The analysis targets regret bounds for the randomized route. The work extends a tool proven in single agent bandits into the harder world of opposed play.
Catalog record
| CREATOR | Shishen Lin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13562
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedback Shishen Lin Abstract Learning in games is a fundamental problem in machine learning and artificial intelligence, with numerous applications ( Silver et al., 2016 ; Schrittwieser et al., 2020 ) . 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 ( O’Donoghue et al., 2021 ; Maiti et al., 2023 ; Cai et al., 2023 ) , with O’Donoghue et al. (2021) 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 Exp3 ( Auer et al., 2002 ) , the variant Exp3-IX ( Cai et al., 2023 ) , and Ucb ( O’Donoghue et al., 2021 ) . These results highlight the potential of evolutionary bandit learning, particularly the efficacy of randomised optimism via evolutionary algorithms in game-theoretic settings. 1 Introduction 1.1 Two-Player Zero-Sum Games Triggered by von Neumann’s seminal work ( Von Neumann, 1928 ; Von Neumann et al., 1953 ) , the maximin optimisation problem (i.e., \max_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}g(x,y) ) has become a major research topic in machine learning and optimisation. In particular, two-player zero-sum games, represented by a payoff matrix A\in\mathbb{R}^{m\times m} , constitute a widely studied problem class in the machine learning and AI literature ( Littman, 1994 ; Auger et al., 2015 ; O’Donoghue et al., 2021 ; Cai et al., 2023 ) . The row player selects i\in[m] , the column player selects j\in[m] and these choices, leading to a payoff A_{ij} (i.e. the row player receives the payoff A_{ij} and the column player receives the payoff -A_{ij} ). The objective is to find the optimal mixed strategy, which is a probability distribution over actions for each player. Formally, we define our problem as follows: to find x^{*},y^{*}\in\Delta_{m} , where \Delta_{m} denotes the probability simplex of dimension m-1 , satisfying \displaystyle V_{A}^{*}:=\max_{x\in\Delta_{m}}\min_{y\in\Delta_{m}}y^{T}Ax. (1) By von Neumann’s minimax theorem ( Von Neumann, 1928 ) , V_{A}^{*}=\min_{y\in\Delta_{m}}\max_{x\in\Delta_{m}}y^{T}Ax . (x^{*},y^{*}) solving for Eq.( 1 ) is called a Nash equilibrium. V_{A}^{*} is the shared optimal quantity at the Nash equilibrium. In this paper, we call it the Nash equilibrium payoff. Nash’s Theorem, or von Neumann’s minimax theorem, guarantees the existence of (x^{*},y^{*}) for Eq.( 1 ) ( Von Neumann, 1928 ; Nash, 1950 ) . If the payoff matrix is given or known, then Eq.( 1 ) can be reformulated as a linear programming problem, and it can be solved in polynomial time using algorithms including the ellipsoid method or interior point method ( Bubeck and others, 2015 ; Maiti et al., 2023 ) . Now, if the payoff matrix is unknown, let the row and column player play an iterative two-player zero-sum game. At each iteration, they select actions and observe the corresponding payoff entry from the matrix. Based on the observed rewards, both players update their strategies. This iterative setting is referred to as a repeated matrix game (or matrix games, for short). Our goal is to design algorithms that can perform competitively in such games. A standard measure of performance in this setting is regret, which we define formally in later sections. We are also interested in whether the algorithm can approximate the Nash equilibrium (x^{*},y^{*}) , measured using divergence metrics such as KL-divergence or total variation distance. 1.2 Evolutionary Reinforcement Learning Evolutionary Algorithms (EAs) are randomised heuristics inspired by natural selection, designed to solve optimisation problems ( Popovici et al., 2012 ; Eiben and Smith, 2015 ) . EAs aim to find global optima with minimal knowledge about fitness functions, making them well-suited for black-box or oracle settings compared to gradient-based methods. They are powerful tools for discovering effective reinforcement learning policies. EAs are particularly useful because they can identify good representations, manage continuous action spaces, and handle partial observability. Due to these strengths, evolutionary reinforcement learning (ERL) techniques have shown strong empirical success, and we refer readers to ( Whiteson, 2012 ; Bai et al., 2023 ; Li et al., 2024a ) for detailed reviews of ERL. Coevolution, rooted in evolutionary biology, involves the simultaneous evolution of multiple interacting populations ( Popovici et al., 2012 ) . Interactions can be cooperative (e.g., humans and gut bacteria) or competitive (e.g., predator-prey dynamics). These co-evolutionary dynamics have been studied and applied in ERL, demonstrating empirical effectiveness in many applications ( Whiteson, 2012 ; Xue et al., 2024 ; Li et al., 2024a ) . For example, co-evolutionary algorithms (CoEAs), a subset of EAs, have been applied in many black-box optimisation problems under various game-theoretic scenarios ( Xue et al., 2024 ; Gomes et al., 2014 ; Hemberg et al., 2021 ; Flores et al., 2022 ; Fajardo et al., 2023 ; Hevia Fajardo et al., 2024 ; Benford and Lehre, 2024b ) . Despite the practical success of evolutionary reinforcement learning in domains such as game playing, robotics, and optimisation ( Moriarty et al., 1999 ; Khadka and Tumer, 2018 ; Pourchot and Sigaud, 2019 ; HAO et al., 2023 ; Li et al., 2024b ; Li et al., 2024c ) , there is a lack of rigorous theoretical analysis ( Li et al., 2024a ) . In particular, the theoretical foundations of coevolutionary learning in matrix games remain largely unexplored. As a starting point, in this work, we aim to bridge this gap by combining evolutionary heuristics with bandit learning and analysing their performance in matrix games from both theoretical and empirical perspectives. 1.3 Contributions This paper introduces evolutionary algorithms for learning in matrix games with bandit feedback. To the best of our knowledge, this is the first work to provide a rigorous regret analysis of evolutionary reinforcement learning (i.e., Coebl ) in matrix games with bandit feedback. Specifically, we show that randomised optimism implemented via evolutionary algorithms can achieve sublinear regret in this setting. Our empirical results demonstrate that Coebl outperforms existing bandit learning baselines for matrix games, including Exp3 , Ucb , and the Exp3-IX variant. These findings highlight the significant potential of evolutionary algorithms for bandit learning in game-theoretic environments and reveal the role of randomness in effective game-play. This work serves as a first step towards a rigorous theoretical understanding of evolutionary reinforcement learning in game-theoretic settings. 1.4 Related Works 1.4.1 Regret Analysis of Bandit Learning in Matrix Games Theoretical analysis of bandit learning algorithms in matrix games has been extensively studied. Recent works, such as ( Auger et al., 2015 ; O’Donoghue et al., 2021 ; Cai et al., 2023 ) , have studied classical bandit algorithms under settings where