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

1 Introduction

1.1 Two-Player Zero-SumGames

Learning in games is a fundamental problem in machine learning and artificial intelligence, with numerous applications [Silver et al., 2016; Schrittwieser et al., 2020]. Triggered by von Neumann's seminal work [Von Neumann, 1928; Von Neumann et al., 1953], the maximin optimisation problem (i.e., maxx∈X miny∈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 ∈ Rm×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 ∈ [m], the column player selects j ∈ [m] and these choices, leading to a payoff Aij (i.e. the row player receives the payoff Aij and the column player receives the payoff -Aij). 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∗ ∈ ∆m, where ∆m denotes the probability simplex of dimension m - 1, satisfying

By von Neumann's minimax theorem [Von Neumann, 1928], V ∗ A = miny∈∆m maxx∈∆m yT 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 algorithmic performance is regret, which we define formally later. 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 some blackbox or oracle settings compared to gradient-based methods [Eiben and Smith, 2015]. EAs are powerful and useful tools for discovering effective reinforcement learning policies because they can identify good representations, manage continuous action spaces, and handle partial observability [Whiteson, 2012]. 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 [Anderson and May, 1982]. 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 gametheoretic 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 RelatedWorks

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 only rewards or payoffs are observed. In particular, O'Donoghue et al. [2021] conducted an in-depth regret analysis of the UCB algorithm, Thompson Sampling, and K-Learning, showing that these methods achieve sublinear regret in matrix games. Neu [2015] established a sublinear regret bound for EXP3-IX, which was subsequently extended to matrix games by Cai et al. [2023] through a new variant. Additionally, Auger et al. [2015] provided convergence analyses of bandit algorithms in sparse binary zerosum games, while Cai et al. [2023] extended these results to uncoupled learning in two-player zero-sum Markov games. A more recent study by Li et al. [2024d] investigates adversarial regret for Optimistic Thompson Sampling, exploiting repeated-game structures and partial observability to anticipate opponent strategies.

In contrast, our work aligns with [O'Donoghue et al., 2021] in focusing on Nash regret in two-player zero-summatrix games with bandit feedback. While their approach highlights adversarial dynamics, ours demonstrates the potential of randomised optimism via evolutionary algorithms. We provide a novel regret analysis that complements stochastic optimism-based methods in achieving sublinear Nash regret. Moreover, the theoretical understanding of evolutionary bandit learning remains largely unexplored. This paper aims to fill that gap, marking a first step towards the rigorous study of evolutionary bandit learning in matrix games, an area that remains both promising and under-explored.

Runtime Analysis of Co-evolutionary Algorithms

Recent studies have conducted runtime analyses of cooperative and competitive co-evolutionary algorithms [Jansen and Wiegand, 2004; Lehre, 2022]. Here, runtime refers to the number of function evaluations required for the algorithm to find the Nash equilibrium. For a comprehensive overview of these contributions to competitive co-evolutionary algorithms, we refer readers to the recent papers [Lehre, 2022; Hevia Fajardo and Lehre, 2023; Fajardo et al., 2023; Lehre and Lin, 2024b; Benford and Lehre, 2024b; Benford and Lehre, 2024a; Lehre and Lin, 2024a; Lehre and Lin, 2025]. Although we do not analyse the runtime of COEBL in this paper, an interesting future research direction is to explore how the runtime of COEBL could be analysed in the context of matrix games with bandit feedback. The idea of competitive coevolution in game-theoretic settings, as explored in the aforementioned works, serves as the foundation for our application of evolutionary methods to bandit learning algorithms.

2 Preliminaries

2.1 Notations

Given n ∈ N, we write [n] := {1, 2, · · · , n}. Fp denotes the finite field of p (prime number) elements. For example, F3 denotes the finite field of three elements, {-1, 0, 1}. We denote the row player by the x-player and the column player by the y-player. f(n) ∈ O(h(n)) if there exists some constant c > 0 such that f(n) ≤ ch(n). f(n) ∈ ˜O(h(n)) if there exists some constant k > 0 such that f ∈ O(h(n) logk (h(n))). We define the (m - 1)-dimensional probability simplex as

∆m := {z ∈ Rm | ∑mi=1 zi = 1, zi ≥ 0}. In each round t ∈ N, the row player chooses it ∈ [m], and the column player chooses jt ∈ [m]; and then rt is the reward obtained by the row player. We define the corresponding filtration Ft prior to round t by Ft := (i1, j1, r1, . . . , it-1, jt-1, rt-1). We denoted Et(·) := E(· | Ft). For any real number x, we define 1 ∨ x := max(1, x). Given x ∈ {0, 1}n , |x|1 := ∑ni=1 xi.

Definition 1. A random variable X ∈ R is σ2 -subGaussian with variance proxy σ2 if E(X) = 0 and satisfies E(exp(sX)) ≤ exp ( σ2 s2 2 ), for all s ∈ R.

2.2 Two-Player Zero-SumGames and Nash Regret

A two-player game is characterised by the strategy spaces X and Y, along with payoff functions gi : X × Y → R, where i ∈ [2]. Here, gi(x, y) denotes the payoff received by player i when player 1 plays strategy x and player 2 plays strategy y.

Definition 2. Given a two-player game with strategy spaces X and Y, and a prime number p ∈ N, let the payoff functions g1, g2 : X × Y → R represent the payoffs for player 1 and player 2, respectively. The game is said to be zero-sum if the gain of one player is exactly the loss of the other, i.e., g1(x, y) + g2(x, y) = 0 for all x ∈ X and y ∈ Y.

Many classical games where the outcomes are win, lose and draw, such as Rock-Paper-Scissors, Tic-Tac-Toe and Go, can be modelled as ternary zero-sum games,where g(x, y) = 1 denotes a win for player 1, g(x, y) = -1 a win for player 2, and g(x, y) = 0 a draw. In this paper, we mainly focus on ternary two-player zero-sum games. In matrix games, we evaluate performance using the Nash regret, defined as the cumulative difference between the Nash equilibrium payoff in Eq. (1) and the actual rewards obtained by the players [O'Donoghue et al., 2021].

Definition 3 (Nash Regret). Consider any matrix game with payoff matrix A ∈ Rm×m and the reward for the row player choosing action it ∈ [m] and the column player choosing action jt ∈ [m] is given by rt = Aitjt +ηt, where ηt is zeromean noise, independent and identically distributed from a known distribution at iteration t ∈ N. Given an algorithm ALG that maps the filtration Ft to a distribution over actions x ∈ ∆m, we define the Nash regret with respect to the Nash equilibrium payoff V ∗ A ∈ R by

Given any class of games A ∈ A, for any T ∈ N, we define

Given a fixed unknown payoff matrix A, the regret R (A, ALG, T ) represents the expected cumulative difference between the Nash equilibrium payoff and the actual rewards obtained by player 1 using algorithm ALG over T iterations. The worst-case regret WORSTCASEREGRET (A, ALG, T) denotes the maximum regret of algorithm ALG across all possible payoff matrices within the class of games A, thus capturing performance in the worst-case scenario.

Nash regret serves as a fundamental measure for evaluating an agent's performance against a best-response opponent, enabling fair comparison with prior work [O'Donoghue et al., 2021]. It emphasises long-term convergence to equilibrium strategies, thereby reflecting robust and generalised behaviour in game-theoretic settings. Although it may be less informative for analysing intermediate behaviours [Li et al., 2024d], it offers critical guarantees regarding the agent's capacity to adapt towards optimal and resilient strategies against adversarial best-response opponents.

3 Co-evolutionary Bandit Learning

3.1 Learning in Games and COEBL

The study of learning dynamics in games seeks to understand how players can adapt their strategies to approach the equilibrium when interacting with rational opponents [Fudenberg and Levine, 1998]. A commonly used metric for evaluating algorithmic performance in such settings is regret, as formally defined in Definition 3. Alternative evaluation criteria include convergence to Nash equilibrium, which may be measured using KL-divergence or total variation distance.

In this section, we only present the algorithm for the xplayer, noting that the counterpart for the y-player is symmetric. The proposed method, COEBL (Co-Evolutionary Bandit Learning), leverages co-evolutionary approach in bandit feedback settings. We denote the empirical mean of the rewards sampled from entry Aij by ¯ Atij , and the number of times up to round t that the row player has selected action i while the column player has selected action j, by ntij ∈ [t] ∪ {0}.

Algorithm 1 COEBL for matrix games

Require: Fitness(x,B) := miny∈∆m yT Bx where B ∈ Rm×m and x ∈ ∆m.

• 1: Initialisation: x0, y0 = (1/m, . . . , 1/m) and n0ij = 0 for all i, j ∈ [m]
• 2: for round t = 1, 2, . . . , T do
• 3: for all i, j ∈ [m] do
• 4: Compute ˜ Atij =Mutate( ¯ Atij , 1/1 ∨ ntij )
• 5: end for
• 6: Obtain x′ ∈ argmaxx∈∆m miny∈∆m yT ˜ Atx
• 7: if Fitness(x′ , ˜ At ) > Fitness (xt-1, ˜ At ) then
• 8: Update policy xt := x′
• 9: else
• 10: Update policy xt := xt-1
• 11: end if
• 12: Update the query number of each entry in the payoff matrix ntij for all i, j ∈ [m]
• 13: end for

The following mutation variant is considered in this paper.

where N (µ, σ2 ) denotes a Gaussian random variable with mean µ and variance σ2 , and c is some constant with respect to T and m.

Evolutionary algorithms typically consist of two main components: variation operators and selection mechanisms. Variation operators generate new candidate policies from the current population, while the selection mechanism retains the most promising policies based on a predefined fitness function. In COEBL, we define the fitness function as Fitness(x,B) := miny∈∆m yT Bx, which evaluates the performance of a policy x against the best response of the opponent, given the payoff matrix B. Initially, COEBL applies a Gaussian mutation operator to perturb the estimated payoff matrix ˜ At , and generates a mutated policy x′ for the row player. As the estimated matrix ˜ A is fully observable by the x-player, the optimal response x′ in line 6 is computed by solving a linear programming problem [Bubeck and others, 2015; Maiti et al., 2023]. Between lines 7 and 10, the new policy x′ is evaluated using the fitness function and compared against the previous policy xt-1. If x′ strictly outperforms xt-1, the policy is updated; otherwise, we retain xt-1 to avoid potential instability in the maximin solution.

The central idea behind COEBL is to adopt the principle of optimism in the face of uncertainty (OFU) to explore the action space and exploit the opponent's best response [Bubeck et al., 2012; Lattimore and Szepesv´ari, 2020]. However, unlike traditional bandit algorithms such as those in the UCB family, COEBL implements randomised optimism via evolutionary algorithms. Through the variation operator, COEBL generates diverse estimated payoff matrices, which in turn lead to a broader range of diverse candidate policies. The selection mechanisms then guide the evolutionary process towards higher fitness.

Although COEBL shares similar priors as Thompson Sampling using Gaussian priors by [Agrawal and Goyal, 2017] and Optimism-then-NoRegret (OTN) framework [Li et al., 2024d], it differs in two key ways. First, our Gaussian prior is defined via upper confidence bounds rather than empirical means alone, with a higher variance term 1/(1+ntij ) compared with one by [Agrawal and Goyal, 2017] and a different scaling constant than used in OTN [Li et al., 2024d]. Second, COEBL incorporates a selection mechanism, which implicitly adjusts the sampling distribution and is uncommon in Thompson Sampling. These two key changes are proven to be beneficial for adversarial matrix game settings in later sections.

While O'Donoghue et al. [2021] has demonstrated that deterministic optimism enables UCB to achieve sublinear regret and outperform classic EXP3, and other bandit baselines, we will show that randomised optimism (via evolution) also exhibits sublinear Nash regret. More importantly, we will demonstrate that randomised optimism in matrix games can be more effective and adaptive in preventing exploitation by the opponent than deterministic optimism, and thus outperforms existing bandit baselines. Specifically, it outperforms the current bandit baseline algorithms for matrix games, including EXP3, UCB and the EXP3-IX variant on the matrix game benchmarks considered in this paper.

3.2 Regret Analysis of COEBL

In this section, we conduct the regret analysis of COEBL in matrix games. Before our analysis, we need some technical lemmas. We defer these lemmas to the appendix 1 .

We follow the setting in [O'Donoghue et al., 2021] and consider the case where there is 1-sub-Gaussian noise when querying the payoff matrix. Assume that given t ∈ N:

(A): The noise process ηt is 1-sub-Gaussian and the payoff matrix satisfies A ∈ [0, 1]m×m.

Lemma 1. Suppose Assumption (A) holds with T ≥ 2m2 ≥ 2 and δ := (1/2T 2m2 )c/8 where c > 0 is the mutation rate in COEBL. For each iteration t ∈ N, given ˜ At in Algorithm 1, we have:

Theorem 2 (Main Result). Consider any two-player zerosum matrix game. Under Assumption (A) with T ≥ 2m2 ≥ 2 and δ = (1/2T 2m2 )c/8 , where c > 0 is the mutation rate in COEBL, the worst-case Nash regret of COEBL for c ≥ 8 is bounded by 2√2cTm2 log(2T 2m2 ), i.e., ˜O(√m2T).

Sketch of Proof. Due to page limit, we defer the full proofs of Lemma 1 and Theorem 2 to the appendix and provide a simple proof sketch here. First, we bound the regret under the case where all the entries of the estimated payoff matrix are greater than those of the real, unknown payoff matrix (this event is denoted by Ec t at iteration t ∈ N). Secondly, we use the law of total probability to consider both cases: when all the entries of the estimated payoff matrix are greater than the real payoff matrix, and the converse (i.e., event Et). We already have the upper bound for the first part; the second part can be trivially bounded by 1 in each iteration. Using Lemma 1, we can obtain the upper bound of probability of event Et. Combining these bounds provides us with the upper bound for the regret of COEBL.

Theorem 2 demonstrates that, under the worst-case scenario (assuming the best response of the opponent across all possible matrix game instances under Assumption (A)), COEBL achieves sublinear regret. Specifically, the regret of COEBL is bounded by ˜O(√m2T), matching the regret bound of UCB. This result suggests that deterministic optimism in the face of uncertainty, as highlighted in [O'Donoghue et al., 2021], is not the sole determinant for achieving sublinear regret. In fact, it indicates that the mechanism of optimism: whether deterministic or stochastic is not necessarily critical to the asymptotic regret guarantees in adversarial settings.

However, a key distinction lies in the practical robustness of randomised (stochastic) optimism via evolution compared to deterministic optimism. As we demonstrate in later sections, randomised optimism offers greater adaptability and robustness in game-playing scenarios, enabling COEBL to outperform other algorithms in benchmark tasks.

1 A full version of this paper can be found in https://arxiv.org/abs/ 2505.13562.

Intuitively, stochastic optimism facilitates a more balanced exploration-exploitation trade-off by incorporating upperconfidence-bound randomness, which helps prevent premature convergence to sub-optimal strategies and allows the algorithm to respond more flexibly to dynamic and adversarial environments.

This analysis highlights the potential advantages of stochastic methods in algorithm design for complex environments. Notably, the current analysis of COEBL assumes c ≥ 8 due to technical constraints. We conjecture that the regret bound can be improved by considering smaller values of c, which may further enhance the practical performance of COEBL. Therefore, we recommend hyper-parameter tuning to optimise performance across various problem settings.

4 Empirical Results

In this section, we present empirical results comparing the discussed algorithms. We are interested in empirical regret in specific game instances, measured by cumulative (absolute) regret, i.e.,

where rt is the obtained reward at round t. We focus on two scenarios, including self-play and ALG 1-vs-ALG 2. In the self-play scenario, both row and column players use the same algorithm with the same information. We use the absolute regret (the first metric) to measure the performance of the algorithms in this case. The ALG 1-vs-ALG 2 is a generalisation of the self-play scenario. We use the second metric in Eq. 3 to measure the performance of the algorithms. The ALG 1vs-ALG 2 means the row player uses ALG 1, and the column player uses ALG 2 with the same information. As in the setting of [O'Donoghue et al., 2021], the plots below show the regret (not absolute regret) from the maximiser's (ALG 1) perspective. A positive regret value means that the minimiser (ALG 2) is, on average winning and vice versa. This allows us to compare our algorithms directly.

Moreover, to measure how far the players are from the Nash equilibrium, we use the KL-divergence between the policies of both players and the Nash equilibrium or the total variation distance (for the case where the KL-divergence is not well-defined), i.e., KL(xt, x∗ ) + KL(yt, y∗ ) and TV(xt, x∗ ) + TV(yt, y∗ ), where

for any a, b ∈ ∆m and (x∗ , y∗ ) is the Nash equilibrium of A.

Parameter Settings

Given K is the number of actions for each player and T is the time horizon, for EXP3, we use the exploration rate γt = min{√K logK/t, 1} and learning rate ηt = √2 logK/tK as suggested in [O'Donoghue et al., 2021]. For the variant of EXP3-IX, we use the same settings ηt = t-kη , βt = t-kβ , εt = t-kε where kη = 5/8, kβ = 3/8, kε = 1/8 as suggested in [Cai et al., 2023]. For COEBL, we set the mutation rate c = 2 for the RPS game and c = 8 for the rest of the games. There is no hyper-parameter needed for UCB. For the observed reward, we consider standard Gaussian noise with zero mean and unit variance, i.e. rt = Ait,jt + ηt where ηt ∼ N(0, 1). We compute the empirical mean of the regrets and the KL-divergence (or total variation distance), and present the 95% confidence intervals in the plots. We run 50 independent simulations (up to 3000 iterations) for each configuration (over 50 seeds).

4.1 Rock-Paper-Scissors Game

We consider the classic matrix game benchmark: RockPaper-Scissors games [Littman, 1994; O'Donoghue et al., 2021], and its payoff matrix is defined as follows.

Table 1: The payoff matrix of RPS game. R denotes rock, P denotes paper, and S denotes scissors.

It is well known that x∗ , y∗ = (1/3, 1/3, 1/3) is the unique mixed Nash equilibrium of the RPS game for both players. We conduct experiments using EXP3, EXP3-IX, UCB and compare them with our proposed Algorithm 1 (i.e. COEBL) on the classic matrix game benchmark: the RPS game.

In Figure 1, we present the self-play results of each algorithm. We can observe that COEBL also exhibits sublinear regret in the RPS game, similar to other bandit baselines, and matches our theoretical bound. In terms of the KLdivergence, EXP3, as reported in [O'Donoghue et al., 2021; Cai et al., 2023], diverges from the Nash equilibrium. By zooming in on the KL-divergence plot, we can observe that COEBL and UCB converges to the Nash equilibrium faster than the other algorithms; especially, EXP3-IX has a much slower convergence rate.

Next, we compare the performance of the algorithms by examining their regret bounds and KL-divergence from the Nash equilibrium when algorithms compete with each other using the same information. In Figure 2, we can clearly observe that COEBL outperforms the EXP3 family, including EXP3 and EXP3-IX, in terms of regret. On average, COEBL

has a smaller advantage over UCB in terms of regret, since the empirical mean of regret is above 5 but below 10 after iteration 2000.

The RPS game with a small number of actions is relative simple for these algorithms to play. Moreover, although COEBL completely outperforms the EXP3 family, it does not have an overwhelming advantage over the UCB. How do these algorithms behave on more complex games with exponentially many actions? Can COEBL still take over the game? Next, we answer these questions by considering DIAGONAL and BIGGERNUMBER games.

4.2 DIAGONAL Game

DIAGONAL is a pseudo-Boolean maximin-benchmark on which Lehre and Lin [2024b] conducted runtime analysis of coevolutionary algorithms. Both players have an exponential number (i.e. 2n ) of pure strategies. To distinguish between pure strategies that consist of the same number of 1, we modify the original DIAGONAL by introducing a 'draw' outcome. For U = {0, 1}n and V = {0, 1}n , the payoff function DIAGONAL : U × V → {0, 1} is defined by

As shown by [Lehre and Lin, 2024b], this game (we provide a simple example in the appendix) exhibits a unique pure Nash equilibrium where both players choose 1n . This corresponds to the mixed Nash equilibriumwhere x∗ = (0, · · · , 1) and y∗ = (0, · · · , 1). We conduct experiments using EXP3 to and compare them with our proposed Algorithm 1 (i.e. COEBL) on another matrix game benchmark: the DIAGONAL game. We set the mutation constant c = 8 for COEBL and consider n = 2, 3, 4, 5, 6, 7 in the experiments.

In Figures 3 and 7 2 , we present the self-play results of each algorithm on DIAGONAL game for various values of n. Our results show that COEBL consistently exhibits sublinear regret in the DIAGONAL game, aligning with our theoretical bounds and similar to other bandit algorithms. As n increases, the regret of the baseline algorithms grows as expected. COEBL remains more adaptive and robust in more challenging games, maintaining sublinear regret beneath the theoretical bound (0.1√K2T), as indicated by the black dotted line. We also observe that the regrets of all algorithms increases as n grows, which is expected due to the exponential increase in the number of pure strategies and the corresponding complexity of the game. In terms of convergence measured by TV-distance, COEBL converges to the Nash equilibrium for n = 2, 3, while the baseline algorithms do not converge. However, for n ≥ 4, as the number of strategies grows exponentially, COEBL also struggles to converge to the Nash equilibrium. In Figures 4 and 8 3 , we present the regrets for ALG 1-vs-ALG 2 on DIAGONAL. The empirical regrets across all algorithms exceed 16.2, with a maximum of 389.8 for n = 6, indicating that the minimiser is dominant. In other words, COEBL outperforms the other bandit algorithms across all values of n, from 2 to 7.

2 Figure 7 is in the appendix.

4.3 BIGGERNUMBER Game

BIGGERNUMBER is another challenging two-player zerosum game proposed and analysed by [Zhang and Sandholm, 2024]. In this game, each player aims to select a number that is larger than their opponent's. The players' action space is X = {0, 1}n , representing binary bitstrings of length n corresponding to natural numbers in the range [0, 2n - 1]. A formal definition and the complete results can be found in the appendix. We present part of the results here.

3 Figure 8 is in the appendix.

In summary, we conducted extensive experiments on three matrix games: the RPS game, the DIAGONAL game, and the BIGGERNUMBER game. In terms of regret performance, COEBL in self-play aligns with our theoretical bounds. Moreover, COEBL consistently outperforms other bandit baselines when competing across various matrix game benchmarks, as shown in Figures 4 and 6. COEBL matches the performance of UCB and converges more quickly than EXP3-IX in the RPS game. COEBL converges to the Nash equilibrium for n = 2, 3 and for n = 2, 3, 4, respectively, while the other baselines do not converge, as shown in Figures 3 and 5. Therefore, we conclude that COEBL is a promising algorithm for matrix games, demonstrating sublinear regret, outperforming other bandit baselines, and achieving convergence to the Nash equilibrium in several matrix game instances. However, as the number of strategies grows exponentially, COEBL, like other algorithms, fails to converge to the Nash equilibrium. This observation points out the current limitation of existing algorithms in exponentially large matrix games, and it will be an exciting path for future research.

5 Conclusion and Discussion

This paper addresses the unsolved problem of learning in unknown two-player zero-sum matrix games with bandit feedback, proposing a novel algorithm, COEBL, which integrates evolutionary algorithms with bandit learning. To the best of our knowledge, this is the first work that combines evolutionary algorithms and bandit learning for matrix games and provides the first regret analysis of evolutionary bandit learning (EBL) algorithms in this context. This paper demonstrates that randomised or stochastic optimism, particularly through evolutionary algorithms, can also enjoy a sublinear regret in matrix games, offering a more robust and adaptive solution compared to traditional methods in practice.

Theoretically, we prove that COEBL exhibits sublinear regret in matrix games, extending the rigorous understanding of evolutionary approaches in bandit learning. Practically, we show through extensive experiments on various matrix games, including RPS, DIAGONAL, and BIGGERNUMBER that COEBL outperforms existing bandit baselines, offering practitioners a new tool (randomised optimism via evolution) for handling matrix games playing with bandit feedback.

Despite these promising results, our work has some limitations. Theoretically, we only consider two-player zerosum games, which is consistent with prior studies such as [O'Donoghue et al., 2021; Cai et al., 2023]. Extending COEBL to general-sum games with more players or to Markov games represents an exciting and challenging avenue for future research. More technically, we conjecture whether Theorem 2 could also hold for smaller value of c < 8 with certain threshold. Additionally, our analysis assumes sub-Gaussian noise. Investigating the algorithm's performance under different noise distributions, such as sub-exponential noise, could yield further insights. From an experimental perspective, testing on more diverse problem instances would strengthen the current empirical analysis.

Future work could focus on both theoretical and practical extensions of evolutionary bandit learning. From a theoretical perspective, it would be worthwhile to explore how COEBL or other evolutionary bandit learning algorithms can be adapted to more complex game structures, such as multi-player or general-sum games. On the practical side, improving COEBL by incorporating more sophisticated mutation operators, additional crossover operator, non-elitist selection mechanisms, or population-based evolutionary algorithms could enhance its performance in more complex settings. EBL could be a suitable class of algorithms, serving as a starting point for more general evolutionary reinforcement learning algorithms.

Ethical Statement

There are no ethical issues.

Acknowledgements

We would like to thank Professor Per Kristian Lehre, Dr Alistair Benford and Dr Mario Alejandro Hevia Fajardo for the fruitful discussion and comments on an earlier draft of this paper and also thank the anonymous reviewers for their helpful reviews. Shishen is supported by International PhD Studentship at School of Computer Science, the University of Birmingham. The computations were performed using the University of Birmingham's BlueBEAR high performance computing (HPC) service.