Why Playing Against Diverse and Challenging Opponents Speeds Up Coevolution: A Theoretical Analysis on Combinatorial Games
Authors: Alistair Benford
Per Kristian Lehre
Venue: NeurIPS 2025 poster ()
Keywords: coevolution
runtime analysis
combinatorial games
Primary area: theory

Abstract: Competitive coevolutionary algorithms (CoEAs) have a natural application to problems that are adversarial or feature strategic interaction. However, there is currently limited theoretical insight into how to avoid pathological behaviour associated with CoEAs. In this paper we use impartial combinatorial games as a challenging domain for CoEAs and provide a corresponding runtime analysis. By analysing how individuals capitalise on the mistakes of their opponents, we prove that the Univariate Marginal Distribution Algorithm finds (with high probability) an optimal strategy for a game called Reciprocal LeadingOnes within $O(n^2\log^3{n})$ game evaluations, a significant improvement over the best known bound of $O(n^5\log^2{n})$. Critical to the analysis is the introduction of a novel stabilising operator, the impact of which we study both theoretically and empirically.

Why Playing Against Diverse and Challenging Opponents Speeds Up Coevolution: A Theoretical Analysis on Combinatorial Games
Alistair Benford
Per Kristian Lehre School of Computer Science University of Birmingham p k. wwwre@bhamm.mmmmmm ac. uk
School of Computer Science University of Birmingham a. s. benf ordbbbam ac
Abstract
Competitive coevolutionary algorithms (CoEAs) have natural application prob- lems that are adversarial or feature strategic interaction. However, there is currently limited theoretical insight into how to avoid pathological behaviour associated with CoEAs. In this paper we use impartial combinatorial games as challenging domain for CoEAs and provide a corresponding runtime analysis. By analysing how individuals capitalise on the mistakes of their opponents, we prove that the Univariate Marginal Distribution Algorithm finds (with high probability) an opti- mal strategy for game called Reciprocal LeadingOnes within (n² log" n)) game evaluations, significant improvement over the best known bound of O( log n). Critical to the analysis is the introduction of novel stabilising operator, the impact which we study both theoretically and empirically.
1
Introduction
Many of the most popular machine learning methods for multi-agent systems rely on self-play. Indeed, recent breakthroughs on games including Go, Chess, and Poker [43 5 34 have used self-play to produce superhuman performance without prior training data. However, despite their popularity self-play algorithms are not provably efficient in general, and a robust theory of which self-play algorithms are efficient and how performance scales with problem size is an important open question.
A recurring observation is that while self-play agents perform well against similar play styles, they often perform poorly against new agents exhibiting radically different strategies to those trained Accordingly, there is a need to ensure strategic diversity is present during learning. A possible source for this strategic diversity is to utilise population- based approaches such as competitive coevolutionary algorithms (CoEAs) 40) CoEAs iteratively evaluate individuals of a population based on interactions with competitors, selecting the strongest as parents for the next generation's 's population, which is instantiated using mutation and crossover.
against [32 48 44).
The successful application of CoEAs is not straightforward in general, due the possibility of pathological behavior such as cycling, forgetting, and loss of fitness signal [12]. These issues are often caused by failure to accurately ascertain the quality of individuals. which in turn relies on ensuring opponents are both diverse and challenging. For example, a lack of population diversity on highly intransitive games can lead to cycle-chasing: if certain genotypic feature needed defeat particular type of opponent, that feature may be forgotten if such opponents are not also retained in the population; and evaluations against significantly stronger or weaker opponents provide little useful information for progression, which incurs loss of fitness signal.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

As it is critical to avoid such behaviours, our research objective is to gain a deeper understanding of how the distribution of opponents is affected by algorithm design, and how this subsequently impacts the performance of CoEAs. This understanding can be acquired through runtime analysis, which provides rigorous estimates of the number of times the game simulated by an algorithm until a specified objective is achieved [8]. While there is a large amount of runtime analysis for standard evolutionary algorithms (EAs) [9], the first steps towards a corresponding theoretical framework for coevolution have only been taken recently (see Section I.I. despite clear demand [40]
As theoretical work on full-scale real-world problems is generally not feasible, the problems to which runtime analysis applies are often simplifications designed to capture challenging aspect of the corresponding application. There is large amount of interest in the use of CoEAs for game playing (see Section T.Ip, so we consider this a critical area for the development of runtime analysis for CoBAs. One important class of difficult and varied games are combinatorial games. Even though optimal play for small combinatorial games can be computed using the game graph in linear time (as a function of n, the number of game positions), the full space of possible strategies is exponential in n, and CoEAs often struggle to find winning strategies efficiently. Thus combinatorial games can provide a challenging class of benchmarks for CoEAs that are amenable to theoretical analysis.
Recently, the first runtime analysis for CoEAs on combinatorial games 41 showed that for any impartial combinatorial game, CoEA called Tournament UMDA (see Section 2 is likely to find an optimal strategy within n ((3) game evaluations, where is precisely defined invariant of the corresponding game graph. For many games, 3 turns out to be a constant. However, even in such cases, the implied exponent in the polynomial bound is much higher than implied by observed performance, and it was conjectured that more sophisticated analysis of how competing individuals respond to the weaknesses of their opponents could yield tighter runtime bounds.
The main contribution of this paper is to advance the development of a theoretical framework for coevolution by undertaking this more detailed analysis. We will introduce combinatorial game called Reciprocal LeadingOnes (RLO) which is difficult for a range of CoEAs and for which the aforementioned analysis implies a runtime bound of On 5 log? n). With careful examination of the corresponding coevolutionary dynamics, we prove the following improved upper bound, as well as new lower bound demonstrating the result is tight up to a polylogarithmic factor.
Theorem 1.1 (Theorem 5.2 informal version). With appropriate parameters, Tournament UMDA
finds with high probability an optimal strategy for RLO in time bounded above by O( log" n) and bounded below by Ω(n? log n.)
The particular variant of UMDA we analyse includes a novel feature that promotes diversity in the resulting populations. Not only does its inclusion greatly assist the theoretical analysis, but we will see in the experimental analysis of Section f that it also improves the algorithm's 's observed performance. Our experiments will also investigate the performance of range of CoEAs on several combinatorial games, and help motivate RIO as a challenging benchmark for CoEAs.
While population diversity is an important requirement for success on RLO, diversity alone cannot overcome its challenges. Indeed, we will also prove that any evolutionary algorithm (EA) that maximises diversity by foregoing coevolution and evaluating only against uniform random opponents has exponential runtime on RLO, thus confirming that coevolutionary arms race between players and opponents is essential for sustained progress towards optimal play.
Theorem 1.2 (Theorem 6. informal version). If an EA is used to optimise RLO, where evalua- tions are made by playing against uniform random opponents, then with overwhelming probability, exponential time is needed to discover an optimal strategy.
1.1 Related work
There have been numerous case studies on the topic of coevolution for combinatorial games, including for Nim and Tic-Tac- Toe [4 23 Backgammon [39], Othello [24 44 45), Senet [1]. Checkers
[6]. Chess [B] and Go B1. More general game-playing applications of coevolution include
Pong [3), Bomberman [5). Poker (36), and Resistance [26]. Notably, DeepMind's 's groundbreaking AlphaStar algorithm made use of competitive coevolutionary league training system [48] II.
The first runtime analysis for competitive CoEAs was provided by 277, which established conditions for the successful location of the Nash equilibrium of an intransitive game called BILINEAR by

---

population-basee CoEA. Further theoretical analysis of CoEAs on BILINEAR has studied the impact of algorithmic features including archives [2] and fitness aggregation [9). this paper, we ask how to retain a distribution of diverse opponents that are conducive to coevolutionary learning. This question was also examined theoretically in [20] through a method promoting populations of individuals that are diverse in how they rank opponents relative to one another. The coevolutionary instance of UMDA to which our main result applies was first analysed on class of symmetric zero-sum games 3 and also later in the first runtime analysis of coevolutionary algorithm for combinatorial games (and indeed, any turn-based game)
1.2 Notation
Let S be a finite set. A probability distribution over S is function S - [0, 1] such that An S-valued random variable is said to be distributed according p. denoted P. if (sx = s) p(s) for all S. For any subset C S, define p(A) E. p(s). Given y 10, let (S) be the set of distributions p over S with p(s) 7 for all S, and define P(S) = PP) We use (S) to denote the powerset of a set S. All logarithms are the natural logarithm unless stated otherwise, and given k E N we write log" n (log n)g.
Eoes ((8)
2 Tournament UMDA
Whereas most EAs generate new individuals by mutating existing individuals the current population, estimation of distribution algorithms (EDAs) instead use statistics about the current population to instantiate more general probability distribution over the entire search space (38]. Candidates for selection in the next generation are then sampled according to this distribution.
For search domains of the form X' Ilier S₁, where I is finite indexing set, standard practice is to keep track of frequency vector Pt E I P(S.) that evolves with time. Broadly speaking, Pe (s) represents the proportion of individuals in the population P, S X that have an appearing position i. New search points can then generated using the following probability distribution. Definition 2.1. Given X = Ihe S₁ and IIIII P(S.), lei Univ(X, p) denote the probability distribution over X such that, if x Univ(X, (X.)) p), then for any y E X, F(r = y) Ilier p())())-
The cocvolutionary EDA we analyse one- poeppopulation instance of the Univariate Marginal Dis- tribution Algorithm (UMDA) which employs a binary tournament selection, and is delineated in Algorithm (for further comparison of one-population and two-population CoEAs, see Section
Algorithm 1 Tournament UMDA with parameters μ E N, y > 0, 0
Require: Search domain = Il S; and payoff function f :: x + (-1.1).
for é and E S, do
Set po()((s) = [T. end for
for t N until termination criterion met do
for j E [u]] do
Sample Univ Univ(X,pe) and y ~ pniv(X.pp)
x
if f(x, y) = 1
Set w
y if f(x, y) = -1
Sample Pi+ ~ MU.
end for for E do
for s S, do
Set (()((()(s)) = [i (1)1 = =s]
end for Set Pr+1 (i) = n:, (1++1 (i))
end for
end for
3

---

UMDA was first introduced as non-coevolutionary EDA by Mühlenbein and Paaß [5]. and the instance analysed here is closely related to that appearing in [3
As is common for EDAs, there is a special step at the end of each generation to ensure that the probability of a generated individual taking any given value E S; in position 7 never drops below some boundary parameter 7,. This is achieved by use of constraint functions x... PPS.)) + (S.). We refer the reader to for our proofs we only rely on the fact that the constraint function simplities to म. x (p) min {max (p(s), 7), 1 1-7) here (and indeed the only difference to that appearing in [4] is the use of an operator MUTATE(C, Pt, applied to each selected individual.
4
2 for a complete description of n... However, we note that
> in the case |.Si] 2. A novel feature of the instance of UMDA described
Definition 2.2. Given E X' :- Ilier Sú, the operator MUTATE(C, Pt,)),,)))))) x) generates element E X by, independently for each E I, sampling y(ā) uniformly at random from S; with probability ILES. (1 10-P4 (()( and otherwise setting (ii) = z(1).
MUTATE(C, Pt, introduces probability that individuals entering the next population have some entries generated uniformly at random, thus nudging each entry (i) of the frequency vector slightly towards the uniform distribution. This increases the level of population diversity in subsequent generations. Nonetheless, because the size of the nudge is proportional to ILees, (1 (s))), its effect lessens when pe (i) has low entropy, and thus does not prevent the algorithm converging on those positions i where there is strong preference for certain values.
pt
As well as its potential diversity benefits, the inclusion of MUTATE(C, 2) is perhaps best motivated in terms of its relation to the concepts of balance and stability as applied to EDAs [14 25]. Roughly speaking, an EDA is balanced if E Eppr+1 Pa] and it is stable if the distributions (i)(i)) remain close uniform in such case. While these properties do not seem at first to be obviously contradictory, Theorem 6. of [25] shows that they are in fact mutually exclusive. In the same chapter, is shown via an application to the well-known LEADINGONES benchmark (where the fitness of a bitstring is defined as the length of its longest prefix of 1-bits) that stable EDAs can offer significant speed up due to their prevention of premature convergence on positions that do not become relevant until later in the optimisation process.
holds in the absence of any fitness signal,
The addition of the operator MCTATE(C, Pc, 2) transforms Tournament UMDA from coevolutionary EDA that is balanced into one that is stable. With this, we should hope to see improved performance in settings where the optimisation of positions happens sequentially rather than concurrently, as is the case for LEADINGONES. We will see in Section 4 that this change significantly improves the performance of Tournament UMDA on combinatorial games, and also assists with the proof of the associated runtime bounds.
3 Impartial combinatorial games and Reciprocal LeadingOnes
We quickly describe the representation of impartial combinatorial games via directed graphs; for a more comprehensive introduction, see [ 16 17). An impartial combinatorial game (ICG) is finite acyclic rooted directed graph G (V, F, vo where V a vertex set of size n (the game positions), No E V is the initial game position, and F V - (VV) is function mapping each position onto those which can be reached in a single move. Players take turns moving the current position to an element of F(v). If ((v) is empty, the current player loses.
We will encode strategies for ICGS as an assignment of each interior vertex an element of F(v), with this assignment indicating the preferred move at each game position. Formally, using Int(G) to denote the set of E V with F(v) A 6. then XG Ieg F()) will be the set of strategies for G. Given x E XG. let r(u)= E V denote the preferred move at at position u. Let fo Xg X Ne + () be the payoff function for G, where fa y) 1 indicates that wins against y and fa(x, y) = - indicates that x loses against y (where x moves first).
To help motivate Reciprocal LeadingOnes, let us consider why learning winning strategies even for simple combinatorial games can be difficult principle. Whether it Chess or Nim, in order to guarantee optimal play in combinatorial game it is not enough to put oneself in a winning position; one must then also maintain the upper hand by responding correctly to any difficult position an opponent move the game to later. However, for many combinatorial games, each play only bears

---

44
d4
43
ds
Q2
d2
41
d1
C4
b
Cs
bs
C2
b2
Ci
b
CO
Figure 1: The game graph G for RLO.
witness to a fraction of the overall possible positions. It is on such games that learning is potentially improved by training against opponents that both challenging (so that novel and difficult positions occur) and diverse (so that a range of difficult positions occur).
We define Reciprocal LeadingOnes (RLO) to be the impartial combinatorial game G = (V, vo)
with the specification V {co} U (WlE(m) (at, dz, Ca, d,)), to Cz. and
{c-1,ds
if u a, or 2 bi. if d,,
{0-1)
F(u)=
bi)
if C and i i> 1.
i co.
An illustration of the game is shown in Figure 1 RLO can be regarded as series of n challenges and responses, where the player who plays at C is considered be the current challenger and the player who plays at {a,, bj is the current responder. In each play of the game only one of each aj or b; can be encountered, yet optimal play necessitates perfect play at both, and so RIO captures the notion of a difficult game to learn as described above. As the player who plays at co loses, the responder can win by repeatedly moving the game to G-1 (a "correct response") thus maintaining their position as responder. Thus, RLO is second-player by ensuring that z(u) = C for every i E [n] and u E {a,, J. In fact, this condition for perfect play is also necessary one, and so we have the following characterisation of optimal strategies for RLO (see Appendix A for a corresponding proof).
game, and victory can be guaranteed
Definition 3.1. Let Opt(G) S XG be the set of x such that faly.z) for every y No. Proposition 3.2. x E Opt(G) if and only if x(u) = 1 every i E [m] and u E (a,,
Experimental analysis
In this section we present experimental analysis showing combinatorial games to be challenging benchmark and case study for CoEAs. Throughout, the runtimes for an algorithm on a game G were obtained by performing 100 runs of A for each population size in a range of values between 100 and 10000, and retaining only the 100 runs associated to the population size with the lowest average runtime. When refer to the average runtime of A on G, we refer specifically to the mean of these 100 retained runs. All algorithms were run until either the population contained an optimal strategy or 10 game evaluations had been performed, whichever occurred first. As such, runtimes of 10 should be interpreted as failure to discover an optimal strategy in the allocated time. In addition to RLO, we consider number of other well-known ICGs. Many of the algorithms selected were chosen due to previous application to combinatorial games (including Chess, Checkers, and Othello). For further details on the algorithms and games, well details of computational resources used to carry the relevant experiments, see Appendix B
Most CoEAs are two- wo-poouulttion, and evaluate individuals based interactions with the opposing population. For asymmetric problems (especially those with differing search domains), such algo- rithms are the only viable option. However, for settings where both players have the same strategy space, one may opt to use a moppopuuttioon CoEA in which individuals are evaluated based on their interactions with other members of the same population. There are potential benefits to this approach, such as to avoid a loss of fitness signal arising from differing strengths between populations. However, reliable insight into when each paradigm should be employed limited.
The distributions of runtimes shown in Figure relate to three broad classes CoEAs: oneppopulation EDA-type CoEAs (Tourament UMDA with e 0 and e > 0); ane-population non-EDA CoEAs
5

---

Subtraction
RLO
100M
Toumament UMDA (c=0)
10M
(c+0.05)
pollackblar1988
100k
cholappliatoge
pensilluke2022
1000
196inbelew1907
5jk20155
Turning Turtles
Silver Dollar
PDCoEA
RankDwCoEA
10M
100k
10k
1030
Chomp
Tic-Tac-Toe
100M
10M
100k
1000
Figure 2: Distributions runtimes for a range of CoEAs on six combinatorial games. For each algorithm- gegortthm-gameeeo combination, the distribution plotted that of the 100-run batch corresponding the population size with the fastest average runtime.
Tournament UMDA (c=0)
Mean Runtime (log scale)
10a
Tournament UMDA (c=0.05)
109
40
50
60
70
80
90
100
200
Number of Challenges (log scale)
Toumament (c=0): slope=2.116 intercept=3.062, 2=20999
Tournament UMDA (c-0.05): slope=1.543, Intercept=4.921, R~2-0.991
Figure Average runtime of Tournament UMDA on RLO with varying number of challenges.
Similar to the results shown in Figure 2, runtime obtained following a basic parameter sweep. That is, for each n batches 100 runs on RLO both versions of Tournament UMDA were executed using a range of population sizes. Each mean runtime and 95% confidence interval (+1.96 x SEM) that corresponding to batch with lowest average runtime. Dashed lines indicate log-log linear regressions.

---

Table 1: Comparison of runtimes for Tournament UMDA for e == 0 and = 0.05.
Problem
Toumament UMDA (c=0)
Tournament UMDA (c=0.05)
i-statistic
p-value
Mean Runtime
Std Dev
Mean Runtime
Std Dev
Suhtraction Nim
2.60 e4
5.29
2440
e.40
3.45
e-33
RI.O
1.06
4.14e4
e4
1.81 e4
11.23
e.25
Turning Turtles
c.09
e.73
5.76
1.13e4
17.34
10e-35
Silver Dollar
c.65
e450
c.34
e.45
10.50
4.63 e-
Chomp
1.38 e4
5.82
6.20
3.02
11.54
2.12 22
Tic- Tac-TTcoTTT
6.48 e5
6,48
8.13
9.76
28.35
e-86
(pollackblair 1998, chellapillafogel11999 and panaitluke2002); and two-population non-EDA CoEAs (rosinbelew 1997, sjlk2015, PDCoEA, and RankDivCoEA), Despite the games having relatively small game graphs (ranging from between 64 and 629 vertices), most CoEAs required millions of simulations to discover optimal play (if optimal play was found at all). Notably, the best-performing CoEAs in each of the non-EDA classes (panaitluke2002 and rosinbelew 1997) both used crossover and archives, which increase population diversity and help prevent cocvolutionary forgetting.
Despite its simplicity compared to the best-performing non-EDAs, the instances of Tournament UMDA were the best-performing algorithms on all games, justifying selection as an interesting case for further theoretical analysis. Notably, setting the parameter to be positive in the mutation operator MUTATE(C, Pt, x) improved the performance of Tournament UMDA on all six games. Table compares the relative performance for 0 and 0.05, and the speed up was found to be significant with respect to Welch's s t-test [4]]. As these findings only apply to problems a fixed size, we also present in Figure an analysis of how the runtime of Tournament UMDA scales with the number of challenges n in RLO. Polynomial performance is observed from the linear relationship between and runtime when plotted
log-log scale. It is remarkable that while the estimated degree of the polynomial for = 0 closely corresponds to the dominant term of n² in our main theoretical result, the slope of 1.543 for 0.05 indicates that asymptotically superior performance may be possible as a result of introducing MUTATE(C, Pt, 2) for populations of size roughly vn (that is, smaller than considered in our analysis).
5
An upper bound for the runtime of UMDA on Reciprocal LeadingOnes
The runtime of a CoEA is measured as the number of times the payoff is queried until the algorithm reaches the desired search objective (see (TO), follows.
Definition 5.1. Suppose that G is impartial combinatorial game, and that A is algorithm which makes t queries of fG during each generation. Then, given a set B Xg. the runtime of A on fa is defined to be the random variable T (B) =T min {t: Pt n B o (}. where P. C XG is the population of A at the start of generation t.
As discussed in Section 1 an upper runtime bound O(n log² n) for Algorithm 1 on RLO can be quickly obtained using the results of 44] (see Appendix C.I Our main result improves this upper bound and further establishes a lower bound, as follows.
Theorem 5.2. Let K 0 be arbitrary constant, let G be the game graph for RLO, and let A be described by Algorithm where e & 1/600 is a constant and 7 = 1/(100)). Then there exists
nio E N such that, provided n > ni and μ > (K+4)10") ni log n.
P n logn < T (Opt(()) < pn log" n² >1>1-n
While the full proof of Theorem 5.2 is provided in Appendix D here we provide description of some of the key ideas behind the upper bound, and how they relate to the impact of the operator MUTATE(C, Pt)
run of A on RLO generates a Markov chain (pr) over state space which we label Q. For each
0 & & n, we will let A; be the set of Q such that p(c;, a.) E (.. Z. p(u,: cj-1) > 27,
and ((1)
27 whenever j E [i] (where we use p(u, u) as a shorthand for (w)) Note
that Q Ao 2 A 2 ... 2 An. The intuition here is that Pt A, corresponds evaluating
7

---

0
1-1 pla, G-t)
plane-1)
1-9
((.0))
pla,
Figure Deterministic trajectories 1713 induced by (qq) initialised on the line p(a,, G--1) p(b;, G-1 7. The cases () (left) and > 0 (right) are both shown. As A(q) is an illustrative device and does not explicitly feature in the proof of Theorem 5.2 the expression for A(q) used to produce this plot (via Euler's 's method) is one corresponding to the lower bounds featuring in the
definition of &o. as given in Appendix D
against opponents that are both diverse and strong in the final i challenges. Indeed, if y is small and x ~ Univ(Rg, PP) for some Pa E A, then x is likely to always respond correctly the final i challenges, making x impossible to beat when entering those challenges as responder. Moreover, because pr (c,c, Pr (c,, b2) E L 4] for j [i]. if x enters those challenges as challenger, then will discover and punish suboptimal opponents with at least constant probability. The diversity condition Pe(cy. az) E 1. gl is critical to sustaining consistent progress by ensuring suboptimal players do not reenter the population (as observed in Appendix C.2).
If Univ(XX: p) for some p E A,, then x is likely to belong to GG) Thus, we analyse how long it takes (pr) to move from Ag to An- This process is partitioned into phases, with pe moving from 1;-1 to A; in phase i. More specifically, phase examines how the vector
q: (pe(es, 0:) (: G- 1), po(b,, 1-1 E 1-)
moves towards the set À == R+ x [ 27, 712. Applying results from [4], and also carefully accounting for the effects of MUTATE(C, Pt, and the constraint functions, we will be able obtain a fairly precise estimate of the value of
Aqq) == E|q+1 - qe 9: = q Pt E A4-1]-
(qq) defines a (deterministic) vector field over [y, 7)3. In this framing, our analysis reduces to:
(A) Show the trajectories induced by (qq) converge to A. (B) Show the random process (q, ) closely follows these trajectories.
These tasks are the most detailed and technical and part of our proof. However, they are greatly assisted by the role played by MUTATE(C, Pt, 2). To illustrate, consider Figure which shows these trajectories for the cases e is typically whichever of x: or y avoids playing at position 6--1. This observation provides strong intuition for the shape of the trajectories. For example, when Pr (a,, Q-1) is large and (e(c,, a,) is small, most games will visit b, in which instance the responder incurring a strong pressure for Pe(b,, G-1) to increase in that region of [y, 1 7. As another example, if p. (b, c-11) is large but (r G-1) is small, the challenger is more likely to win if they select a,, thus incurring a strong pressure for Pt (c; 0z) to increase. In both cases, the resulting increase is consequence of rewarding another. Thus, the shapes of the curves in Figure 4 are representative of how coevolution learns through a feedback mechanism of individuals capitalising on the mistakes of their opponents.
and > When Pt E A;-1, the winner w sampled Algorithml I
win by moving to C/-1, thus
player for exploiting sub-optimal play exhibited by
Transferring this intuition to a rigorous confirmation of [A] variation in (g:) makes it unlikely to follow any single trajectory. For mic-dimensional stochastic
not straightforward, as random

---

G
4,
41
A. 44, GUG.
B +
G2 m F2
Fr Dr
Da Ci
C3 S B
Figure 5: Trajectory-folloinngg sequences of cuboids appearing in the proof of Theorem 5.2 (or more precisely, in the proof of Lemma D.Sp. The three axes of each representation of [y, 1-11" correspond to p(c,, az), p(a;, 1) and p(b,, c--1) in the same orientation as in Figure 4 boundaries of [y, 7/8 has been enlarged to assist with visualisation.
The space close to the
processes, this is typically handled using drift analysis (2).. One way such methods can applied to higher dimensional processes is by mapping the space down to one-dimension using distance function, however such function with the specific properties needed to apply drift analysis is not always guaranteed to exist (and we were unable to find one in this instance). Aside from possibly using a distance function, there is no clear system for generalising drift analysis to higher dimensions beyond simple linear cases 42 [22] An alternative approach is to level-based analysis 77 (7), however it was not immediately clear in this case how to define associated levels that fully capture the dynamics of (q.) ) Instead, handle this technicality, we will introduce relation > between sub-cuboids of [n, 1 -1 with the property that if q. E B and B <t, C, then qe+r E C holds with high probability (where we assign 7 a fixed value that is (log² n)). We then define sequences of cuboids, with + holding between one cuboid to the next. These sequences collectively follow the paths of the trajectories, and gradually contract down to the set Å. An illustration of this part of the proof is shown in Figure
This transfer from the idealised deterministic progression of Figure to the probabilistic progression of Figure 5 is where the effect of MUTATE(C, .t) is most beneficial. The resulting nudge towards the uniform distribution (recall Section 2 biases the (q:) towards the middle of [y, 1- where the trajectories move more directly towards Å and where fluctuations caused by random variation are less erratic. This difference is evident also in Figure 4 where the trajectories for >> 0 move more directly and smoothly towards Å. This analysis also helps explain the difference in performance between e and e = 0.05 observed in Section 4 Accordingly, is natural to ask how closely the actual trajectories for run of Tournament UMDA on RLO match the idealisations of Figure For this, we refer the reader to Appendix C.2
It is useful to consider the extent to which the proof of Theorem 5.2 generalises beyond RLO. The overall proof technique (that is, analysing the trajectory of the vector q and carrying out steps (AA and (B) is certainly not exclusive to the specific structure of RLO and there is no innate reason it could not be applied to other combinatorial games. In particular, the proof generalises easily to non-binary cases (that is, combinatorial games with more than two moves available in turn), albeit with some heavier notation. However, a focus on RLO greatly simplifies our analysis due to its repeating gadget structure, and most of the proof analyses dynamics on a single gadget. Similar arguments could be recreated for game structures that are more complex or varied, however this may be impractical given the high level of technicality already present for RLO.
EAs cannot optimise combinatorial games by playing against random opponents
The result and corresponding proof of Section helps demonstrate and formalise the benefit provided by evaluating against a range of diverse opponents. However, it would be misguided to conclude that population diversity is the sole contributor to the success of a CoEA the cocvolutionary feedback

---

between player and opponent is fundamental to learning. To this end. in this section we will show that an evolutionary algorithm cannot efficiently optimise Reciprocal LeadingOnes if individuals are evaluated against opponents sampled uniformly at random from the search domain. In this regime, the distribution of opponents maximally diverse, but representative of fixed environment.
The statement and corresponding proof of this black box result relies on the introduction of family of ICGs (RLO(z) z {0, 1)"). Each instance RLO(z) will be obtainable from RLO by simply relabeling vertices, and so are all isomorphic to RLO. In addition, as strategy for RLO may be described using 3n binary choices, we will adopt X' {0, 1)3hh as the search domain for all instances of (zO(2) and write the corresponding payoff function as fRLO(Z) X x X - R. For full description of (1.((2) and the correspondence of strategies to {0, 1) 1}3", we refer the reader to Appendix E.
Algorithm 2 Black box evolutionary algorithm
Require: Initial distribution do P(X) and variation functions vn X IR + P(Z) for E Sample Zo du
for t E N until termination criterion met do
Sample a f(z)
Sample 2141 ~ 0141(20..... .........))
end for
The lower bound will apply to any evolutionary algorithm describable by the black box model of [T0] outlined by Algorithm 2, which, here, has been generalised to apply to stochastic payoff functions
f: X - PRR). We remark that this model is general enough to encompass non-coevolutionary EDAs in addition to classical EAs. With this, we can now state the main result for this section (for a proof, see Appendix (..2).
Theorem 6.1. Given z E {0. 13 and x E EX, let g2(x) be the random variable defined by sampling y Unif( ()) and setting (=(x) = (1, Suppose A is any EA describable by Algorithm
Then there exists {0, 1 such that
P (Op((RLO())) < 2n/²1 2
is often standard to restrict black box analysis to algorithms which sample initial search points uniformly random, and also restrict variation operators those which are unbiased, in the sense that bit values and positions are treated impartially (28). With these restrictions, the conclusion of Theorem 6. holds for all instances of Reciprocal LeadingOnes, as follows (for further details on the unbiasedness condition and a proof of Corollary 6.2. we refer the reader to Appendix E.3).
Corollary 6.2. Suppose A is an EA describable by Algorithm 1ashamm@@whh which employs the uniform distribu- tion over X as do and employs only unbiased variation functions v, X x R2 - P(X). Then for any z {0, S it holds that
P (Opt(RLO(z))) 2"1/11 (((LL((()))<>1111))))))
2-1 2-
7 Concluding remarks
In order to analyse what distributions of opponents are essential to sustain progress coevolution, we have proven that with high probability coevolutionary instance of UMDA is able to find an optimal strategy for RL.O within (n log" n) game simulations. Central to this is detailed analysis of novel mutation operator applied to selected individuals. Experiments indicate that the inclusion of this operator significantly improves the performance of UMDA, which is already among the best-performing CoEAs on combinatorial game benchmarks. We additionally showed that RLO cannot be optimised efficiently by non-cocvolutionary EA evaluating against random opponents.
While our main result provides lower bound for populations of size Ω(n log n) that matches the upper bound (up to polylogarithmic factor), our experiments indicates that asymptotically faster runtimes may be possible for smaller populations. Related analysis of EDAs indicates that tight bounds for smaller populations may be obtainable, but only with detailed arguments that vary significantly over several cases (see Section of (55).. )), and so we leave this as an open question for potential future work.
10

---

Acknowledgements
This research was supported by a Turing AI Fellowship (EPSRC grant ref EP/VO25562/I), The computations were performed using the University of Birmingham's BlueBEAR HPC service. See http::/wwww..brmmngn... ac. uk/bear" for more details.
References
[1] K. Arulkumaran, A. Cully, and J. Togelius, AlphaStar: An evolutionary computation perspec- tive. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '19, pages 314-315, 2019.
[2] F. Ben Jedidia, B. Doerr, and M. S. Krejca. Fssimation-oo-ddssributtto algorithms for multi- valued decision variables. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '23, pages 230-238, 2023.
[3] A. Benford and P. K. Lehre. Runtime analysis of coevolutionary algorithms on class of symmetric zero-sum games. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '24, pages 1542-1550, 2024.
[4] A. Benford and P. K. Lehre. A general upper bound for the runtime of a coevolutionary algorithm on impartial combinatorial games. In Pruceedings of the Genetic and Evolutionary Compulation Conference, GECCO '25, pages 1594-1603, 2025.
[5] N. Brown and T. Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456))883-889 2019.
[6] K. Chellapilla and D. Fogel. Evolving neural networks to play checkers without relying on expert knowledge. IEEE Transactions on Neural Networks, 1086):138--139,, 1999.
[7] D. Corus, D.-C. Dang, A. V. Eremeev, and P. K. Lehre. Level-based analysis of genetic algorithms and other search processes. IEEE Transactions on Evolutionary Computation, 22(5):707-719, 2018.
[8] B. Doerr and F. Neumann. Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, 2020.
[9] B. Doerr and F. Neumann. A survey recent progress in the theory of evolutionary algorithms for discrete optimization. ACM Transactions on Evolutionary Learning and Optimization, 1(4):1-43, 2021.
[10] S. Droste, T. Jansen, and Wegener. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems, (9(4):525-544, 2006.
[11] G. Ferrer and W. Martin. Using genetic programming to evolve board evaluation functions. In Proceedings 1995 IEEE International Conference Evolutionary Computation, volume pages 747-752, 1995.
[12] S. G. Ficici. Solution concepts in coevolutionary algorithms. PhD thesis, Brandeis University, 2004.
[13] D. Fogel. T. Hays, S. Hahn, and J. Quon. A self-learning evolutionary chess program. Proceed- ings of the IEEE, 92(12):1947-1954 2004.
[14] Friedrich, T. Kötzing, and M. Krejea. EDAs cannot be balanced and stable. Proceedings of the Genetic and Evolationary Computation Conference 2016, GECCO '16, pages 1139-1146. 2016.
[15] R. Gold, H. Branquinho, Hemberg, U.-M. O' O'Reilly, and P. Garcfa-Sánchez. Genetic program- ming and coevolution play the Bomberman TM video game. In Applications of Evolutionary Computation, pages 765-779, 2023.
[16] R. K. Guy. Impartial games. Games of No Chance, volume 29 of Mathematical Sciences Research Institute Publications, pages 61-78. Cambridge University Press, 1996.

---

[17] R. K. Guy. What is game? In Games of No Chance, volume 29 of Mathematical Sciences Research Institute Publications, pages 43-60. Cambridge University Press, 1996.
[18] A. Hauptman and M. Sipper. GP-EndChess: Using genetic programming to evolve chess endgame players. In Proceedings of the 8th European Conference on Genetic Programming, EuroGP '05, pages 220-131, 2005.
[19] M. A. Hevia Fajardo and P. K. Lehre. How fitness aggregation methods affect the performance of competitive CoEAS on bilinear problems. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '23, pages 1593-1601, 2023.
[20] M. A. Hevia Fajardo and P. K. Lehre. Ranking diversity benefits coevolutionary algorithms on an intransitive game. Parallel Problem Solving from Nature PPSN XVIII, pages 213-229, 2024.
[21] M. A. Hevia Fajardo, P. K. Lehre, and S. Lin. Runtime analysis of co-evolutionary algorithm: Overcoming negative drift in maximin- cotiiiiiiiotiiitttiinnn.mmm In Proceedings of the 17th Conference on Foundations of Genetic Algorithms, FOGA '23, pages 73-83, 2023.
[22] D. Janett and J. Lengler. Two-dimensional drift analysis: Optimizing functions simultane- ously can be hard. Theoretical Computer Science, 971:1 14072, 2023.
[23] W. Jaškowski, K. Krawiec, and B. Wieloch. Fitnessless coevolution. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '08, pages 355-362, 2008.
[24] W. Jaškowski, M. Szubert, and Liskowski. Multi-criteria comparison of coevolution and temporal difference learning Othello. In Applications of Evolutionary Computation, pages 301-312, 2014.
[25] M. S. Krejca. Theoretical analyses of univariate estimatiion-o--disribbuiti algorithms. PhD thesis, Universität Potsdam, 2019.
[26] J. Lange, M. Stanke, and M. Ebner. Co-evolution of spies and resistance fighters. In Applications of Evolutionary Computation: 25th European Conference, EveApplications 2022, pages 487- 502, 2022.
[27] K. Lehre. Runtime analysis of competitive co-evolutionary algorithms for maximin optimisa- tion of bilinear function. Algorithmica, 86(7):2352-233 2392, 2024.
[28] P. K. Lehre and C. Witt. Black-box search by unbiased variation. In Proceedings of the 12th Anmual Conference on Genetic and Evolutionary Computation, GECCO '10, pages 1441-1448, 2010.
[29] J. Lengler. Drift analysis. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pages 89-131. Springer International Publishing, Cham, 2020.
[30] D. A. Levin and Y. Peres. Markov Chains and Mixing Times. American Mathematical Society, 2nd edition, 2017.
[31] A. Lubberts and R. Mikkullinen. Co-evolving a Go-playing neural network. Coevolu- tion: Turning Adaptive Algorithms Upon Themselves, Genetic and Evolutionary Computation Conference, 2001.
[32] R. MacQueen and J. R. Wright. Guarantees for self-play in multiplayer games via polymatrix decomposability. In Proceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23, 2023.
[33] G. A. Monroy, K. O. Stanley, and R. Mükkulainen. Coevolution of neural networks using a layered pareto archive. In Proceedings the Genetic and Evolutionary Computation Conference, GECCO '06, pages 329-336, 2006.
[34] M. Moravčík, M. Schmid, N. Burch, V. Lisy, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, and M. Bowling. DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 35666337::508-113 2017.
12

---

[35] H. Mühlenbein and G. PaaB. From recombination of genes to the estimation of distributions I. Binary parameters. In Parallel Problem Solving from Nature PPSN IV, pages 178- 778-187, 1996.
[36] Noble and R. A. Watson. Pareto coevolution: using performance against coevolved opponents in game as dimensions for pareto selection. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '01, pages 493-500, 2001.
[37] L. Panait and S. Luke. comparison of two competitive fitness functions. In Proceedings of the 4th Annual Conference Genetic and Evolutionary Computation, GECCO'02, pages 503-511, 2002.
[38] M. Pelikan, M. Hauschild, and F. G. Lobo. Estimation of distribution algorithms. In Springer Handbook of Computational Intelligence, pages 899-928. Springer, 2015.
[39] Pollack and D. Blair. Co-evolution the successful learning of backgammon strategy. Machine Learning, 32(3):225-244) 1998.
[40] E. Popovici, A. Bucci, R. P. Wiegand, and E. D. De Jong. Coevolutionary Principles, pages 987-1033. Springer, 2012.
[41] C. D. Rosin and R. K. Belew. New methods for competitive coevolution. Computation, 5(1):1-29, 1997.
Evolutionary
[42] E. Rowe. Linear multi-objective drift analysis. Theoretical Computer Science, 736:25-40,
2018.
[43] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L.. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, Simonyan, and D. Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419))11440 1144, 2018
[44] M. Szubert, W. Jaskowski, Liskowski, and K. Krawiec. The role behavioral diversity and difficulty of opponents in coevolving game-playing agents. In Applications of Evolutionary Computation, pages 394-405, 2015.
[45] M. Szubert, W. Jaškowski, and K. Krawiec, On scalability, generalization, and hybridization of coevolutionary learning: A case study for Othello. IEEE Transactions Computational Intelligence and AI in Games, 5(3):214-226, 2013.
[46] H. Thorisson. Coupling, Stationarity, and Regeneration. Probability and Its Applications. Springer- ppringer-Verlag, 2000.
[47] A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015.
[48] O. Vinyals, I. Babuschkin, W. M. Czamecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi,
R. Powell, T. Ewalds, P. Georgiev, J. Oh, D. Horgan, M. Kroiss, Danihelka, A. Huang, L. Sifre,
T. Cai, J. P. Agapiou, M. Jaderberg, A. S. Vezhnevets, R. Leblond, T. Pohlen, V. Dalibard, D. Budden, Y. Sulsky, J. Molloy, T. L. Paine, C. Gulcehre, Z. Wang, T. Pfaff, Y. Wu, R. Ring, D. Yogatama, D. Wünsch, K. McKinney, O. Smith, T. Schaul, T. Lillicrap, K. Kavukeuoglu,
D. Hassabis, C. Apps, and D. Silver. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782)350-354 2019.
[49] B. L. Welch. The generalization of 'Student's' problem when several different population variances are involved. Biometrika, 34(1-2):28-33
35, 15.00 01 1947.
13

---

A Proof of Proposition 3.2
Proof of Proposition 3.2 Let
A = {ar x²)) = G--1 for every i E [n] and u E b.).
We have already seen in the discussion of Section 3 that A C Opt(G). Now suppose that x & A, so that there is some i E [n] and u E {a;, such that a<u) A d,. If E A is such that y(c: = then fc .) = 1 (indeed, if y has not become the responder before the game reaches c₁ then y will switch to being the responder the following challenge). Thus & Opt(G), and A Opt as required.
B Experimental details for Section
Here we provide overview of the algorithms and games used for the experiments of Section 4 The algorithms used were the following (see Table 2}.
pollackblair1998 : A (1 + 1)-type CoEA with crossover. As our applications are not probabilistic, repeated play was not used in our implementation.
chellapillafogel19999 [6]: A (A + A)-type CoEA with players evaluated against random opponents. Self-adaptive features appearing the original paper were not used in our implementation.
panaitluke2002 37: A population-basee CoEA that uses a single-elimination tournament evaluation individuals.
rosinbelew 1997 41: A population-based CoEA with unique evaluation method that promotes the retention of individuals that can defeat niches in the opposing population.
sjlk2015 44 : A (X, 2ty-type CoEA which evaluates individuals based average perfor-
mance against the opposing population and "fitness sharing".
PDCoEA 27 A population-
CoEA which independently selects parents based on game-theoretic pairwise dominance relation.
RankDivCoEA 220 : A population-basee CoEA which rewards individuals for inducing
less common rankings of their opponents.
All non-EDA algorithms used the same mutation operator: given x, we obtain a mutant by, for each u E Int (G), randomly resampling æ(u) uniformly from F(u) with probability x/n, and otherwise leaving zu) unchanged. A constant mutation rate of 0.3 was used for all algorithms.
The games Subtraction Nim, Turning Turtles, Silver Dollar, and Chomp are described in 4. Tic-Tac--Toe is not often characterised as impartial combinatorial game, owing to the fact that all possible game positions are reachable by only one player and the win condition being described positively rather than as the absence of a legal move. Nonetheless, it is easy represent Tic- Ve--Tac-TTor Toe as an ICG by creating an additional game position with no out- nuu-neegbbour representing a lost game, and having the losing player sent there upon the completion of 3-in-a-row. As the second player can never force a win on a strong positional game (a class to which Tic- Tac-Toe belongs), draws were counted as win for player two. A summary of relevant games is provided in Table
Each experiment was conducted on an internal cluster provisioned with 1344 CPU cores and 6TB of RAM. The experiment used to produce the data presented in Figure 2 had wall-clock time of 22 hours, resulting in a maximum 29568 core-hours. The experiment used to produce the data presented in Figure had wall-clock time of 8 hours, resulting in a maximum 10752 core-hours. Combined, the experiments required no more than 40320 core-hours.
C
Supplementary material to Section
C.1 An existing upper runtime bound for Tournament UMDA on RLO
The proof of the following runtime bound relies on the definitions of concepts including the switcha- bility s(x) of vertex V, the depth of set of edges A C E(G) == (u,,) V F(u)).
14

---

Table 2: An overview of algorithms used in the experiments of Section 4
Label
Ref.
Applications
Paradigm
Archives
Crossover
Elitist
39
Backgammon Checkers, Chess
one-pop.
chellapillafogel
one-pop.
panaitluke2002
37
Nim
one-pop.
tosinbelew 1997
Nim, 3D Tic- Toe-Toe
two-pop.
v
sjlk2015
Othello
two-pop.
PDCoEA
27
two-pop.
RankDivCoEA
20
two-pop.
Table 3: An overview of games used in the experiments of Section 4
Game
Notes
[V]
Subtraction Nim
100, k =
101
RLO
50 challenges
201
Turning Turtles
coins
64
Silver Dollar
squares, coins
126
Chomp
5 x 5 bar
252
Tic- Tec-Tac-Toe
629
and what it means for set of edges be v-switcher. These notions all defined in detail in Section 4 of [4].
Proposition C.1. There a constant > such that the following holds. Let K be an arbitrary constant, let G be the game graph for RLO, and let A be described by Algorithm 7 where 0 and
= 1/(0m)).. Then, provided = C(K + (40m)) log n1,
P PT & C2 40 (K- 2)m log n 2
Proof. The result is immediate from Corollary 5.3 of [4. provided we can verify that every vertex E V has switchability s(v) at most However, this indeed the case, for each V the A, = {(u, v): : v E F(u) is a r-switcher of depth 1.
C.2 Empirical trajectories
Here investigate how closely the actual trajectories of the vector
q (pe(es, az), (r c-11,, pobb, G-1)) 1y]1
in run of Tournament UMDA on RLO match the idealised deterministic version represented in Figure Tournament UMDA was run with population size μr 300 RLO with 50 challenges. This was repeated 15 times for both c 0 and = 0.05; the corresponding implied trajectories for q: (for challenge number = 25) are shown in the first two plots of Figure 6
Both instances initialise with in the middle of h, -3) and the motion is somewhat akin to a random walk for while. Once the algorithms have optimised the challenges up to selective pressure on the entries of q, kicks in and we see the trajectories of both algorithms follow curves similar those in Figure 4 This is most clearly evident the very direct movements seen the edges of [7, 1 7)3 for the case = 0. There are several notable differences in the behaviour between the two cases. The case 0.05 has qi remain closer to (0.5, 0.5, 0.5) before the application of selective pressure. Recalling the discussion of how setting e > 0 transforms UMDA from balanced EDA to stable one (see Section 2). this behaviour similar to that explaining the speed-up up of stable EDAs over balanced EDAs on the LEADINGONES benchmark (25). After selective pressure is applied
the 0.05 trajectory moves quickly and directly towards the set À == 1 Z x [1 27, 1 - - Perhaps most critically, once the e = 0.05 trajectory reaches Å the bias towards uniformity (on the p(c, a.) axis) combined with the selective pressure (on the other two axes) causes the trajectory
15

---

Toumament UMDA (c=0)
Tournament UMDA (c=0.05)
Panait-Luke
p 0-12
Figure 6: Observed trajectories of q: for Tournament UMDA (in the cases 0 and c = 0.05) as well as the CoEA of [37]. Beneath the plots are projections of the trajectories onto each dimensions, with the horizontal axis representing time. We note that the horizontal axis has been scaled for each algorithm. Thus, while may appear, for example, that the case p(a,, G-11) ~ C-1) sooner, this is only relative to the overall runtime of the algorithm, which is fact much longer.
reaches the region
to remain inside Å. This is in stark contrast to the moving into the corners of the cube, from which point it is then even possible for p(a,, c5-1) and p(b, 1) to drift significantly away from y, thus impeding further progress on the remaining challenges.
where the qı is not prevented from
As reference case, the corresponding trajectories for the CoEA of 37 (the best performing non- EDA from the experimental analysis of Section 4 is provided the third plot Figure [6] Here we observe even more erratic motion in [7, 1 7]. and the coevolutionary forgetting caused by p(c,, a:) being too close to boundary occurs more frequently.
D Proof of Theorem 5.2
D.1 Further notation
Let us outline the notational conventions that will be adopted in the statements and proofs of this section. Throughout this section, A will always refer Algorithm 1 and G will always refer the game graph for RLO. As per the statement of Theorem 5.2
we will always assume the following.
A1 K
0 is an arbitrary constant.
A2 0 is arbitrary constant satisfying < 1/600.
A3 2 fig where up is constant which is sufficiently large depending and K.
(K+4)10 6*
A4 μ >
n log n..
A5 7 1/(100m).
16

---

It is helpful to define the following sets.
Q = II (F(F(e)),
2o II P(F(u))
#EIn((G)
vEIni(G)
Indeed, a rum of on RLO can now be considered as a stochastic process (pt) taking values in Q (with the intermediate frequencies (4:) arising in Algorithm Caaimmm@aaaa taking values in 21). For notational convenience, given E Q we will usually write for u, V E V.
(v) 00
if E F(u).
p(u, v)
otherwise.
The process used constrain at E Co into pt Q can be represented as map ny Qo - Q defined as follows.
( v) = xn F(w) (d(u))(v).
As this particular game graph always has [F(u] whenever Int(G), could equivalently have defined
TH (g), v) min (1 max { g(u +}}}
if F(u), otherwise.
It is therefore helpful to define the simple function t: :0, 1] + 17, - > as
#xx) = min {1 - 7, max {7,z}}.
Given p E Q, we will use wp to represent the random variable taking values in Xa generated by sampling x and y independently according to Univ(Xa, p) and setting W/ x if fa(x, y) = 1 and
Wp = y otherwise. Note that Wp, has the same distribution as a w sampled in Algorithm
Given function 7) Q 2 [-o0 [-1 }), let on Q (2) be the map given by
x. [g) q(u,v) v) > p(u,v) [1 + (m(p,,, + of - p(u,v)) (1 p(u, (1)
(p)
for every u, V E V
The motivation for this definition is that we will later establish that p++1 E (P:)) holds with high probability for carefully defined functions πj. More precisely, we will in Lemmas D.7 and D.9 that if = then individual w sampled in Algorithm [ satisfies equations of the form P P( u) = v) p(u, v) + 7pp u, v) (1 p(u, v))] After then accounting for the effect of MUTATE Cc Pt, w) using Lemma D.3 we will then deduce that E[q v)] > p(u, v) [1 (nle: v) c p(u,v) v)) (1 pl u, ). In this expression we relax 3 to so that we can apply concentration inequalities in the proof of Lemma D.6 The only remaining feature to account for is then constraint steps of Algorithm|] [T. which motivates the inclusion of Ty in the definition of Φn.
For some of the preliminary results (in particular, Lemmas D.4 and D.5 it is helpful to recursively define for V.
(y.x) fa
if v E Int(G),
fō v)
otherwise.
so that fa v) fzr (z. Intuitively, fö is the payoff function for the version of RLO where the initial position is v. is also helpful to denote for x. y E Xc.
Patho v) (vo, x(vo). v(x(v))) (y((()))))
Finally, let 8T/2 : R + be given by
I//2
if > 0.
1122 (1)
otherwise.
Note that /122 is convenient tool for showing certain inequalities hold even when the signs of certain terms unknown, and its role is not very important in the overall proof idea.
17

---

D.2 Probabilistic tools
We quickly collect some probabilistic tools that will be useful later. The first one Bernstein's ss inequalities (see Theorem 6.6.1 of [47] for more general version from which Theorem D. follows). The second is simple bound on the variance of a binomial random variable.
Theorem D.1. Let C > and let X Xn be independent random variables such that, for all i, at X₁ b, almost surely and b,
C. Set S := Die(n) X₁ and V == Var[S]
Ejen Var Then, for any t
12/2
P(S > E[S] +1) & exp
V V+C-t/3
f2/2
P(S < [ - 1) < exp
V+C.
Proposition D.2. If X Bin( p), then Var(X) min [E[X], 1 B[X]}.
Proof. Var(X) = pp(1 p) min {up, p(1 p)} min [E[X], B[X]}.
D.3 Preliminary lemmas for both bounds
The following lemma helps quantify the effect of the mutation operator in Algorithm
Lemma D.3. Suppose in Algorithm that 0 c 1, and i I is such that |St| 2. If r E S. a & 1/2, and p E Iher (S..) is such that
P(w((i) Pt = p) > p(i,r) [1 + a (1 (1- p(irr))
then
E(q(+1(i,)) pt = p] > p(i,r) [1 + (a + cf p(irr))) (1 p(i.r)))
Proof. Let p(i,r) r) be fixed and assume that P( - p: p) > (1 a(1 9)). Noting
that c. II (1 p(t, 8)) = cq - q). We can compute
E B(q+1(i,r) Pt = pl = P(P:41 - - - (1- cg(1 9)) P(w(t) 1) g))
> cq -)) a(dl1-))
-
acg - -1
q [ -4 (1)l-))))10000 (1--))
q. [ (a- (a (1) 9)) (1-9)]
y [ (a+ (1 (1-)))
where in the final inequality we have used that ag(1 9) < 1/8.
Lemma D.4. Suppose that p E Q. Then, for any u E and v E F(u),
(w) = v) p(,, (1+ E Patha (z, (1-P = -P)-P(((rr.))) = =1)) (3)
Proof. See Lemma 3.1 of
Lemma D.5. Suppose that p E Q and that x and y are sampled independently according to
Univ(Xa. p). Then for any E V we have
P(fā(z, v) =1) Σ
p(u,u) (1 P(fE(x.V) 1)).
(4)
VEF(u)
= Σ
Σ
p(u,)) p(r, w) (x, =1)-
(5)
VEF(u) WEF(e)
18

---

Proof. 4 holds by the law of total probability. We can then deduce that
p(u, v) (1 ((Jā(x,)) =
=1- Σ
plu, v) ((JG(( =1)
WE (())
vEF(u)
Σ
p(u,o)-
Σ
p(u,w) w) P1-P(f (x, y) = 1))
(EF(
WEF(M)
Σ
Σ
p(u,t) p(v, P(f 1),
W P(a) WE (())
and hence
5 also holds.
In the proof of the following lemma, we note that for real-valued random variables X, Y, we say that <) P(Y & 2) holds for all TR.
X stochastically dominates Y, written X x Y, if P(X <
Lemma D.6. Suppose that n : Q V 1-00 b is any function such that
P(),(u) v) p(u, [1 71p u)
p(u, v))]
(6)
holds for every p E Q and (u, v) E 22 Then, for every E Q we have P(p++ & (p) p: = =p) n n 2
<
Proof. Let p be fixed. In the following proof, expectations and probabilities are all written conditional on the event that Pt = p. For every (u, v) E V2, the quantity Xu, := -e- ge+1 (u, v) is binomially distributed. Let us define
(u, v) p(u, [1 + (n(p: u, v) + of p(u, u))) (1 p(u, v))]
For every (u, u) E V2 we will show that
P (gi++1u,,) v) < sul,, v)) & K-4
The lemma then follows using a union bound.
Noting that is trivially true when v/p; [-1, Using (6) together with Lemma D.3 we can establish that
oc, we may additionally assume that 7pp; u, v)
Elq v)] > p(u, v) [1 + (mpp: u, + cc p(u. (1 p(u, v))
> (uu v) 6 p(u,v) (1 p(u,
(8)
For each (u,v) E V2 let
Yu,o ~ Bin μ, plu, v) + E p(u, p(u, v)).
Nu, and Yu, are both binomial random variables with trials. addition, ( shows that TE| [[(u,o) 2
E[Y,,,) r. Therefore Xa > Yu,s, and hence
P(q++i(u,)) slu, u)) P(Xu, < s (p,, b)) & P(Y.,v p (p(, v)) P(Y.. < B[Y,,v] on v(u,v) (1 - p(u, r))).
In order to bound the final probability above, we need an upper bound on Var(Yu,w). For this, first observe that because -1 & n(pp v) 1/2 have
# p(u, 8 # v( EYy. 2p p(u, v).
(9)
Therefore,
Proposition D.2
Var(Y
min (E[(a, EY min (2p p(u, v). 1...... (1 p(u, w)2)
min (2p p(u, v), / (1-p(u,v) v) + p(u, w) (1- p(u, v))) < min (2μ p(u, v), 24 1(,((u, v)) 4p p(.,p((.)))))) (1 p(u,
(10)
19

---

Therefore, applying Theorem D.1
(with C' = 1 and % p(u, v) (1 p(u, u))), we obtain
f/2
P(Y,, <E[,,,e]
puu, 1) (1- p(u, v))) & exp VVar(Y,,)) + t/3 qu 6
( p(u, v) (1 p(u, 1))
< exp
Var(Yu.v)) 16t p(u, 8) (1
u3))/3
10
( plu, r) (1- p(u, /)
exp
(4+ T2 p(u, (1 p(u, v))
Ep pl,, v) (1))((111)))1 (1-p(u,)) v),
Ep 7(1 -1)
exp
& exp
72 + 12
72(4 + 12
A5
2p p
A2
exp
exp
7200(4 + )1 -7) n
10
(K + 4)n log 7
K-4
exp
= n
n
Hence 7
holds, thus completing the proof.
D.4 Preliminary lemmas for the upper bound
key tool in the proof of Theorem 5.2 will be a map t :: ((2) (O)), carefully defined so that for any set A C Q, if E A then P+++ ((A) holds with high probability. The runtime result then follows by establishing that a repeated application of & eventually contracts Q down to a small set on which sampling element of Opt(G) is very likely. This part of the argument is handled by the following two technical lemmas. Note that intuition behind the sets (A.) defined below (that is, that A; is representative of populations that are both diverse and strong in the final i challenges) is provided in the discussion of Section
Lemma D.7. For 0 E & n, define
A = D p(c, v) > whenever j E [i] and v E {aj, bj}. 1
50n whenever j E [i] and u E {aj.bū}. }
p(u, C)-1 >
Let a: V2 1-x0 U 1-1, 1 be given by
s (p(s, c-1) c-1)) (12(0(( p(bi,
if (u, v) (c,, and p E Ai-
if (u, v) (ci, bi) and E Ai-1.
u))
a;)
(u, v) (a,, and p E At-1: (11)
b;)
(u, v) = (b1, and A
otherwise.
Then, for any p E Q and (u, v) E 22 we have
P(w,(u)= = v) > plu, v) [1 u(p,,,)) (1 p(u, v))]
Proof of Lemma D.7 All cases where a(p; u. v) cases to verify. This will be done using Lemma D.4
trivially true, which leaves with four
Given u E V, let us write N,, as shorthand for the event (z, y) 1, where æ and are sampled independently according Univ(XX,,)) p). Note that if has an out-neighbourhood F(u) = (v. w) of size 2, then with a view to applying Lemma D.4 we can observe that
1 P(N. PPN..
1 P(N.) - puu, v) P(N.)) (1 - p(u,v) (1-P((...)
-11 - p(u, u) (P(N.. ) PPN.))
(12)
Let p E A;-1- Before verifying the four critical cases, let us collect some useful identities. order for x to win when beginning the game from Cj-1, y must make at least one mistake as the responder
20

---

in the final i - 1 challenges. Because E A;-1, it holds for every j E [i - 1] and E {ay, by} that P(y(u)= # c--1) < 50n Therefore, we have
2(1-
1
P(N (P((())))) c for some j E 1--11 and u E {az,bz))
(13)
50n
10'
and
P(Na.)
P(Ne--.)
(14)
We can now compute
1- 1- 1-N(N,, (P...))
12
p(a;; c--1)) (P(Na.) - P(Na-1)
14
(1-2 (-1)))-1)) ((1)))))11111111111 PPP(N....))
(15)
and similarly,
1 1-P(NN-.) -P((b))))))
(1 ctb), (1-22 P(N((N.))))
(16)
Next,
P(N.))
P(Na,) -
= [1 P( P(N...) )1 -PPNa.))
15 L6
P(N (1 2 PNV...))) (p(b,, G-1) - (-1)).
(1 p(a,, c1-1) (1-2-P((c..)) - (1 p(b,, c2-1) (1-2-I((N...)))
(17)
The cases are then verified by applying Lemma D.4 as follows. If (u, v) = (c,,0;) then
(c, a.))
p(c,,,)) [1 + (1 P(N..) PPN)))))
p(c,, a.) [[
[1+ + (PP(N) P(Na,)) (1 (1- -lp,,,
p(c,,a:) [1 + (1 - PPNe, .)) (p(b;, ((ai;ci-1)) (1 (1-p(c,,a:) a:))
p(c;,a)) [11 + alp; c; a:) (1 p(ppp((a)))) a.)))
If (u, v) = (c,, bx). similar computation to the above also yields P(up(c;) = b,) > p(cc. b.) app b,) (1 p(c, b.)).. If (u, v) (a,, c-11, then
P(up(a;) c--1) plas, c--1) [1 + P(a E Patho(x,))) (1 PPNe..) P(Na.))
p(a;, G-1 [] + p(c; a.) (1-12:1 P-N, (1 p(a.)
p(a;, G- 1) [| ax 0-1) -1,
Finally, if (u, v) (b,, -- 1), then
(bw,((b) G-1)
p(b; 03-1 ((bb,
+ P(b; Patho( v)) P(Na_.) P(No.))
16
plb; (-1 [1 + p(c, by) (1 21 2. 1)) (1 ((1()))-1))))
13
p(b,, ci-) [1 a(p: a-1) (1 p(b,, c-11))].
Lemma D.8. Let the set An and the function Q V2 + u--,, be defined as in Lemma D.7 Let tb Φ ( (Q) be the map given by ((A) = Up)n Fix
log² (1/r).
100
It then holds that & C An.
The proof of Lemma D is by far the most detailed part of this section. Additionally, because follows only from the definition of 4. it does not necessarily provide direct intuition for the dynamics of Algorithm and application to Reciprocal LeadingOnes. For these reasons, we opt to first present the overall proof of Theorem 5.2 before proving Lemma D.8 later in Section D.7
21

---

D.5 Preliminary lemmas for the lower bound
Whereas the sets (A,) are representative of populations that are both diverse and strong ar least the final i challenges, the sets (B,)²= in the following lemma are representative of populations which are strong in at most the final i challenges.
Lemma D.9. Let > 4. For 0 & i & n, define
{p 2 p(u, v) 3 whenever j > i, u {ajyby}, and v E {dj, c3-13)-
Let 3: x 22 (-o0 be given by
3(p:u,0) -2(3/4)
if E (ag,by) E (d and p E Bj-t- (18)
-00
otherwise.
Then, for any p E Q and (u, u) E V2 we have
P(wc((u) = v) > u(u,u) [1 + ((p (1 p(u, v))]
Proof. As with the proof of Lemma D.7 given u E we will use N₂, to denote the event f((x,y) =
1. Note that the identities 12 and (4 apply here also.
We require the following claim.
Claim D.10. For 0 & < and 0 < k < j. if E BN and v E (cj,dj+1) then (PP(N)) - / < (3/4)².
Proof of Claim D.10 By [4). it suffices to prove the claim holds for u === cj. We prove this by induction k2 noting that the case k 0 is trivial. For the inductive case, assume for k >> 0 that p E Bj and [P(NN
& (3/4)* Writing
1 P(Ne,_.). we can now compute
P(N.,))
Σ
Σ
p(ej. v) p(u, w) P(N...
oE (ag,b)y we (d)
Σ p(e,,)) (p(v,d,) P(Na,) + p(v, .)) vEtag,bs}
14
P(N,, E v) ((1 ((1- (((0-)( (1- (1- ,)) + p(u, P(Ne, .))
vEfag,b1
Σ p)g,,). v). ((1 (11-p(u, p(1)) C +5) p(u, C -6)
(E(aybby)
Σ p)c,,)) ( + (1 - 2p(0, (01(), -)
=
vE(ag,bg)
Σ p(c,,) (1 2p(u, c)) 8.
(19)
(E(
Because p Bi-k C By-1 it holds for each v E fag. that p(u, e [ El and hence
1 - 2p(v, cj-1) & 3/4. Therefore,
IP(Ne)) 21
Σ b
p(c,,0) - 2p(v, |8| < 1 & (3/4)*,
as required.
We now turn to proving the lemma. All cases where u.) = oo are trivially true, and so we only need consider the case where E {a,, (dj.c--).. and p E Bj- Under these assumptions, we have
P(u,(u)= dg)
p(u, d,) [1 + PNN,) - P(N.))
p(u, dz) [1+ (PP(No,_1) P(NN,)) )) (1- ((-p(u,d)))
p(u, dz) [1 2(3/4) (1- (-p(u.d,))
22

---

By swapping d, and cj-1 in the above calculation, we also obtain P(wy(u) =g-1) 3 C--1-
[L 2(3/4)(-1 -1 . -1- (1,p(u, puu,
(z-1))
Recall in the following lemma that the definition of ΦB is provided by (T.
Lemma D.11. Let & = log (200/c)]. Let the sets (Ba) and the function 3 Q V2
] be defined as in Lemma D.9 Let v (Q)) + ( be the map given by (AA UpE)
{-o} U 1-
For every 0 &ien n l, it holds that (B,) S Bi+c-
Proof. First, note that
A2
log (200/c)
log (c/200) log (3/4)
e > loo (200/c)
+
(20)
log (4/3)
Suppose that q E (.,),,, that there exists p E Bi such that q E Φi (p). In partieular, there is some o' E 2o such that
d((u,u) u) > p(u, v) [1 + (3(p; u, v) + cG p(u, v))) (1 (1-p(u, u)) for every u, v E V, (21)
(q' = q-
(22)
We will show that g Bi+c. To do this we need to confirm that g(u, v) 3 1 whenever j > i i l. u E {ay.bzh, and {dy. C11). So let > i u bz, and v E (d be fixed, and observe that because p B, S B
u,)
18
2(3/4)
20
(23)
100"
Therefore,
quu, u)
igd (u, v))
A (p(u,e) [1 (3(p, u, u) + o(3 p(u, b))) (1 p(u, v)))
(p((,, v) al 3/4 p(u, v)) p(u, v))l).
(24)
There are now two cases to consider. First, if p(u, v) > 3/16 have
= quu v) *p(u, v) [1 c)) > # 1/ [1 c) > (1/8)=1//
On the other hand, if 1/8 < p(u, v) 3/16 then
q(u,v) (p(u, v)) > #(//)) 1/8.
In either case, have q v) > whenever i+ É. Thus q E Bu+e for every & (B,)), and hence (B:) S Bite, as required.
The following lemma shows that if E Bu/4 describes the current state of Algorithm then the probability that an optimal strategy found in the following generation very small.
Lemma D.12. p E Ba/2 and μ & n², then TP( n Opt(G) + 0 p p) K-2
Proof. Let us assume that p. p for some p E Bn/4- Let j E [p] be fixed. We need to estimate P(P(410) e Opt(G)), where we recall from Algorithm that P++1 MUTATE(C,P. p, wp). As in Algorithm let and both be sampled independently according to Univ(X, p). and let us assume that x MUTATE(C, p, x) and y MUTATE(C,P)) p.y). Note that with this notation, we have (f+ E {a' v').
Repeating the caleulations of Lemma D.3 (with 0), obtain for each i > n/2,
P(x'(a.) d,) > p(a, d,) [1 + c( p(a,, (1 p(a, d,)]] 1
(25)
23

---

where we have used the fact that p(a,, d.) > 1/8 (as e Bn/2). The value of x' (u) is independent for every u E V, and hence using the characterisation of Opt(G) provided by Proposition 3.2
Pix' Opt(G)) & IP (Nien x' a'(a) = = <
II <>2/2
P(x' ({)= =
II -1-PP i>n/2
(1-P(2'0) (() d,)) (7/8) 2 K-5
Similarly, we also have P(y E Opt(GG) < 2n K-4 and hence
(() E Opt(G)) & Pp(' Opt(G)) Ply' Opt(G)) & kn-K5 Taking union bound over all j E [n] then yields the desired result.
D.6 Proof of Theorem 5.2
Proof of Theorem 5.2 First, we consider the upper bound P (Opt(G)) pn(log n) Let the sets (Lo and the function a Q V
{ { U[-1, , 1 be defined in Lemma D.7 and note that we have An .... S Ag = Q. If for some we have pt. E An, then Ze G-1) whenever E {az, bi for i E [m], and hence
50m < pt (u, G-1) <
1 EiEn EiE(m) E Eme(ar (P.())))) = 4--1)
Σ
Σ
lelu,
(E(n) uEtai
> 2n(1 50n) > 2n 1.
It would then follow that there is some such that Eig(n] Ene (a ((Pr(j)(u) = =c-1) = =2n,
and hence Pt(j)= Aopt- Therefore
(Op)((G) & P min (1 pt E An).
(26)
By Lemma D.7 we have that (() = v) > p(u, v) [1 + a(p u, v) (1 p(u, v)]] for every p E Q and (u. E V2. In particular, the condition for Lemma D.6 is satisfied for a, and so
holds for every Q that
P(P+11 & (p( Pt p) & n -K2
(27)
(log (1/-))
Let 7
so that
100
8rn 8n(log (100m))²
nloogn)
(28)
100
Let o: : (QQ) + (Q) be the map given by ((A) = (p) By Lemma D.8 88nn S An Consequently, if Parn & An, then there must exist some & < 8Tn such that pi+1 & oa (p.). Therefore, we have
26
(Opt())))) pm(log n)
Plaa min {t: Pt E A,) > p [)
P[min {t: E A > 87n] < P(psrn $ An)
(Vicerm (pe-1 & da (pr)))
K-2 Snr < 2 -K n
Next we consider the lower bound P (Opt( G)) < n² log n). Note that
10a n
log n
A1
pn
n log
(29)
[4 log (200/c)
c)
2 [4 log (200/c)1
If n² then by definition we have T (Opt G)) >
n and so may additionally assume that
& n Let the sets (B.) and the function B
x 22 {-o0] U 111, ! be defined in
24

---

Lemma D.9 and note that we have Bo - C B, = = Deterministically. it holds that Po E B
By Lemma D.9 we have that P(wp(u) u) > p(u. v) 1+ u(: v) (1 (1-p(us p(u, u)) for every
p E and (u, V2, In particular, the condition for Lemma i. satisfied for 1 3, and holds for every E @ that
P(p++1 & ds(()) P p) < n K-2
(30)
Let V (2) ((2) be the map given by (A) = Upe a Suppose that < t & (2()),
PE
where we define = [4 log (200/c)]. By Lemma D.11 v (2) Bre. Consequently, if Pt $ Ba..
then there must exist some < / such that Ps+1 $ @s(p.). Therefore, we have
P(p & Bu) & P (Veco(Pot1 & (s(p))))
n nn--- tE 1_-K-11
(31)
Next, note that if p Be, then as Be S Bsn/4 and μ & ne we can apply Lemma D.12 to obtain P(Pe+1 n Opt(G) # Pt = p) < n
Therefore, we may deduce for any n/(2) that
PPPP+1 n Opt(G) 0) TP P++1 n Opt(G) * 0 pa Ba) P(pe Bu)
IP( P( n Opt(G) * 0 & Ba) P(pe $ BB)
IP (P+1 n Opt(G) + 0 Pa Ba) P(p: & Ba)
K-2 in -n-
K-1 <
k-1 K
Therefore, we may compute
29
P(T)(Op((G)) < n² lo
P PIT (TT((Op((G)) & (2))
=P (Vien/(22) (pt()) + #0)
n 1
P(P * 0) < (22/(22)
K-1
<
2
K
28 2
The theorem now follows by combining the upper and lower bounds using union bound.
D.7 Proof of Lemma D.8
From here, we will use & as a shorthand for d..
It will be useful to map probabilities in the interval h 7 onto logit space using the function defined in the following lemma. Here we collect some simple properties of this mapping.
Lemma D.13. Let 0 < 7 1/2 be fixed, and let g by, 7 - IR be defined by
glv) log
y/
y
Then the following properties hold.
B1 g is strictly increasing
< log (1/7) for any y E l7: 7]. B2 (g(())
B3 For any [0, 1] and y E [y, 7), we have g + a(1 g))) g(v) a/2.
B4 For any [0, and y E 17, 1 7,, we have g a(1 y))) -9(9) < 0/2.
B5 For any [0, ] and y I 7). we have g(v(1 a(1 v))) g(v) > 22a
1 B6 If~ < 2. then -1 - log < g( y) < log y-
Proof. Because g(y) log ( log y log (1 w). B1 follows from the fact that log is strictly increasing function. Using this, we can deduce that for any E [7, - 71.
[g()) & max (19(7)) 7) max { log (1=²) log [-,) log (772) < log (1/7),
25

---

and so B2 holds. Next, observe that for any E [-1, 1| and
[7, 7].
( + a(1 y))) - g(y)) log
1 y(1 + a(1 - 5)) ) log
y a(1 - y))
y
11-1 y/
y) + aa(1 y))
y)( an)
log
log
y( + a(1 - y))
1 (a + 1)y + az²
y) ay))
1 1 ay
log
log
(1 y) ay)
1 - ay
log
+ ay
(32)
If a E [0, 1] and In, 1 - 7| then
g a(1 7))) g(y)
log 1 ay
log (1 a) a/2,
and so B3 holds. If [0, 1] and y E by, 1 7 then
( a(1 9))) g log
< log
1
log [
<
I + az
1 1 4
2
2
and so B4 holds. a [0. 2 and
by, -ny y] then
a
g(y(1- - a(1 - -))) - g(y) log
> log (1 -aa) a) 3 -2a,
+ ay
and so BS holds. Finally, y < y < then
-1 -1 log (1/2) log y < log -y) -lg
log y-
Observing that g(1 - y) = log (1 y) log y then confirms B6 thus proving the lemma.
The following lemma collects some properties of the map & that will be useful in our analysis. Lemma D.14. Suppose that p E A;-1 and g E <(p). Then the following properties hold.
C1 lf (-1) > min (1 100 p(b;, G-1) and p(c;, ba) > 5. then g(ci, b.) }
C2 Ifp(an, > 1 - 100 and p(e;, b.) a then g(1(c, 6.)) glp(c, bi)) + 32.
C3 ax) > & and p(a; c--1) < son
1 then g(g(as, c-1) > g(p(a,, c1) + +
lfp(c,. az) > 1/2 then q(as, c-1) > ci-).
C5 olg(ai,03 1)) > g(g(a;, 4
-- 1)) 2c.
C6 pfa, 11-1) < then g (as, c-1 > p(p(a;, 10.
C7 pla,, c--1 > }. then g(g 4-1)) > 1
C8 For some fixed function h (0, 1) + (0, 1) that it strictly increasing, glci, ai) > h(p(e,,a)))
C9 1fp(c,,b)) & then q(c,, ax) >
Proof. Let q' E On be chosen such that we have
v((uvv) ) > p(u, v) [] + (a(p,,,)) v) oft p(u, v))) (1 p(u, (1-p(u,))) for every u, E.V, (33)
(,')))
(34)
26

---

C1
If p(a(;, > min (1- - 100 b(s, c-1)) then
((e,bb) bi)
2 p(e, 4)) [] (5 (p(aa -( + p(G,),)) (1 p(c, b;))
> ( [ (- + c ((c..))))) (1 -(),))))
> p(c..)) [1+ cl p(a, b.)) (1 - p(a, b,))].
(35)
additionally
< p(c, b,)
< 16. then follows that
q(c, b,)
34
n. (d'(,, bi)) (n bi)) > (+(()= =
On the other hand, if 16
p(e,, by) then
( t (g (ci, b,)) (p(c,,))) [1 (1- > # --c)) 2 #5)) =
In either case, we find C1 holds.
If p(1);
f and p(c, b,) & then
then
g(c,, b,)
(d (ct, by))
2 R (p(c, b.) [1+ (1 - ple, b1)
p(c,, b,) [1 + 10 (1 - p(c. b,))l.
It then follows from B1 and B3 that g(a(1)) g(((i) + SS and so C2 holds.
C3 Observe that for any 0 < < sum and E [0. z we have
y. v- + a(1 -y] y +v)
Jom (1 TOon
100%
7
(36)
and hence
B3
(f [1 + a(1 - -))) g [1+ + a(1 y)l)
gly) + 2..
(37)
We have
(())))))) pla;, G-1) 11 + (pp(e,, a.) + c5 pla,, ((1)) (1 - pla G-1))]
(38)
If p(c;,;)) > and plai, 1-1 < 1 50n then
((((a;)c-1)) g (g/ (as, 1))) (pl, (1 (1-
g(pla;, 1-) 9z.
C4
If p(cc, > g. then
((a; G--1)
Rey (ailaai (2-1))
2
* = (ar,
=
C5
We have
58
c-1)) f (g' (a:, G-1)))
2 (p(a,
c(1 - -p(as, ()))))
B5
g(p(as 1-11 [1 c(1 - p(a, G-
gpppa. c-11) - 2c.
C6
If Ifpla,,
1 then
((q(ar,a-1))
g (1' (as; C(-)))))))
g( (p(a;; (p-a 30 p(a;,a-111
ggp((ap (as, G-1) + 30 p (a,, G- g(p(ar, + :
C7
First, if g & p(a;, c:-1 < then
((a;,Ci1))
it (g' (ai, 1))
t (p(a,, = -
27

---

On the other hand, if 4 < p(a,, 1-11
then
aaa Ci-1)
(a-1)
(a, c--1))
(-(p) -1 (1-c)) ) > xT()) =
8
We have
((c,, a.)
(d
(p(cs, 0z) + (-1) p(a, + p(c;,a)))) (1 --(()))))
p(a,
> (p(c, a:) [] (c - p(a, a.)) - 1) - (1 p(a, a,))l) > p(a,a) h(p(c, a;)): where h: (0 + (0, 1) is the strictly increasing function given by
h(z) x- [1 + (c{} z) - 1) (1 - x:].
(To see that h is strictly increasing, note that we may write
d
dr h(x)) [1 + (o( - x) (1 x x [(1 c(3 =)) -c11 -x)) x))
2x c ( +
and have 4 h(xx) for sufficiently small.)
C9 If p(cc,, b;) < then p(c; a:) > and hence
g(c,a)) as) h(p(c,,)) h(7/8) = [1+ cc) (3)
The following lemma is essentially the dual of Lemma D.14
Lemma D.15. Suppose that p A:-1 and o(p). Then the following properties hold.
D1 If p(; G-1) > min {1 160 p(a;, G-1)) and p(c,, n.) > 5. then q 0;) >
D2 pfb,,, G-1)
Tou and p(c,, a.) E . then g(q(c,, a.)) > g(p(c,, a:)) + s. g(p(1) c-1)) 64
D3 lfp(c;, bi) > and p(b,, c-1) < 50n' then
D4 Ifp(c; b.) > then q(bi, c--1) p(b;,
DS olq(bs; c--)) > glg(bi, G-1)) - 2c.
D6 If p/ps, 11) < .. then g(g (--1)) 2 g(p(bi, ci-1)) 30
D7 If p(b,, C-11 > 5. then g(g(b;, c2-1)) !
8.
D8 For some fixed function h (0, 1) + (0, 1) that it strictly increasing, g(os, b.) > h(p(e, b:)).
D9 If p(es, a.) < $ then q(ci, bx) g
|
Proof. Swap the roles of a; and by in the proof of Lemma D.14
An observation that will be required in the proof of Lemma D.8 is the following.
Lemma D.16. For any i E [m). (AA)) C A,
Proof. Suppose that q E ((A,). There exists p E A such that q E Φ(p). For every j E [1] we can now deduce that
((5,00 4z)
g
((gy,b by)
(ajj,
p(a,, ()-)) 2
50n
((b,,
2 p(by.cj-1)
> 50m
Therefore, g A,, and hence ((A,) Aq.
28

---

Proof of Lemma D.8 We will say that sequence (q:)i-n in Q is e-sequence if qu ((q-1) holds for every E [r]. Given subsets A, B _ 2 and r E N, we say that A +,, B if for any ø-sequence (g)) with go E A, there exists some I with at E B. Note that the following properties of <x, hold.
E1 If 4, B 4,, C. then A A44 C.
E2 Ir B1 U B2 and By + for E [2], then A Sty+ C.
We will establish that A S787 A; for every i E [n]. To do this, choose a constant ,3 such that
F1 3 is sufficiently small constant depending on for any subsequent relationships between B and e to hold, and
F2 n e no, where no is a sufficiently large constant depending on / (as well as c and K) for any subsequent relationships between no and [ to hold.
Note that such choice of is possible due to A3 Let i E [r]] be fixed, and define the following sets (see Figure 5 for an illustrative guide).
B = {p E 1, p(ci,a)) > 1/4 p(c; > 8: p(a;, G-1) > 1- 100
p(b,, c1-1) 3 1
100
Ci = {p E 1,1 a(c > 3, p(c; b.) > :/4 p(a; G-1)
> - n 3
p(b,, c1-1) 30 1 T00
D1 {p E A p(c,,a) a.) > 8. p(e, b.) 3 8. p(a,, c-11)
> 1 - 1/2
p(b, c--1) 3
E (p E 4-1: p(a, a:) > 1/4 b();,b))
> 7, p(a;; 4-1) > - n 1/2
p(b;, 0--1)
> 1
1/2
F1 = {r E A,11 a() > 1 p(c; > pla; G-1)
p(b, 01-1)
3 1 Sun
G. (p E 1-1: a() 37 p(e,, b.) 77, p(a. G-1)
p(u, G-1) 50m
H (p A-1: a() 7, p(e, b.) 7, p(a, a-1)
p(u, an
C2 = {p E A-1 p(c, a. > 1 8: p(c, > 8, p(a, c-11 2 1- -
e
p(b,, C-1) 3 1 n n -8
100
D2 = (p E A-1: p(e, a:) > : p(a, b.) > ; pla G-1) 1) >
p(bis (-1) 3/ 1 nt 1/2
E2 {p E A plc,, a.) 7,, p(c, b,) 2 5: pla, C1-1)
> 11 1/2
p(b,, c-11) 3/ 1 - n 1/2
F2 {p E A-1: Mcaaa)) > p(ci,b)) 3 3 p(as, C1-1 1) 4 11 - 50m G--) 7
G2 (p E A-1 a(c;,a)) 77, p(c;,b)) 37, 7, pla;, (--1)
> 50n
p(b, G-1)
Using the properties established in Lemmas D.14 and D.15 we will show that Ai-1 ,, H +
G1 G2, B - A, and G1 + FR + Eg - Dr - C +, B for k E [2]. (For those instances of depending on E [2] we will only show the case h = 1, however the case = 2 will also hold analagously.)
B -r A;: Suppose that (o is a e-sequence with qo E B. By induction on 4, the following properties hold for every 0 < 1 <
(c a:) > 1
qe b.) > 1.
gagr (-)) > min [g(1 -
) + 128 90
50m }}
100
glg Q-1)) > min {g(1
+ 128 g(1
50n }}.
1
100
Indeed, the condition on qo (c ax) follows from D1
the condition on ge(c,, by) follows from CI the
condition on qe(a,, --11 follows from C3
and
C4
and the condition on qe (b,, c:-1) follows from D3
and D4 Because, using B2 g(1
log (1/r) 2 g(1 50m
1 ). we then have qr E A,.
100
128
C1 , B: Set
g(t)) 9(B)
< T.
c/32
29

---

Suppose that (q:)7 is desequence with E C1. By induction on t, the following properties hold for every <
@t (ci, ai) 2 min (o(3) + (g)
qe b,) //²
( 1)) > g - - - t 2c 3 a(1 106
(b 11-1) 2 1
100
Indeed, the condition on (e(Cs, a:) follows from D1 and D2
the condition on go(es, b)) follows from
C1 the condition on (at, 1--1) follows from C5 and the fact that
B6
BG
g(1 - - 2c
1 1+ B logn - 2c
log n
g(1 - n 8/2) > g(1 100)
and the condition on ge(bi, 111 follows from
D4 We then have qr E B.
D1 +, Ci: Set
g(1
9
100
<
1/64
and h : (0, 1) + (0, 1) be a strictly increasing function so that C8 holds. Suppose that (4:)ī= is
--sequence with Qo D1. By induction on t, the following properties hold for every 0 & t 7'.
(r(c,, a4) > h²))),
(((r, 1
aai (-1)) > g( - n - 2. -
9 n2 )) 2 g(1 100
(bs c-11) > min {g( +t 64 50n }}
Indeed, the condition on qe (c;, 04) follows from C8 the condition on (:(cs, bi) follows from C1 the condition on (:(a;, 6-1 follows from C5 and the fact that
BTC
g(1 - n 11/3
2c 1 2 logn--'- - - > log n
9(1 n (--1/44 )) > 9(1 nn n-)),
and the condition qe (b;, 12 follows from D3 and D4 Because 7' is defined as function of F1 implies that ht (1) > 3. Hence 9r' C1.
E1 >r D1: Assume for contradiction that there is a d-sequence (q:)_o with E E and qe & Dr for all 0 & & Let > 0 be the maximal value of such that the following properties hold.
ol9o(c, bi)) +t 32 & Aaal,, 0,)) <g()),
qe c--1) 2 1/2
(bb,, 1-1) > 1.-
Note that 8 is well defined because the above properties hold for / = 0 (as E Ei \ Di). Because g(go(c,, b,)) + r 3/ > ( ) must hold that T. However, we then have
(g0 ba)) +
911s41 b:) {()
32
as+1 (a;,
1/2
ao+1 (bi, C:-1) g.
If additionally g(1s+1 1 (c,, b,)) < s(}) then we have contradiction to the maximality of 8, whereas o(t) & g(g (Cs, by)) then we have Gs+1 E Dj (noting in particular that g(g++1 by)) $ 9(3) implies that gs+1 (c,, a:) > }. In either case we obtain a contradiction, and so fact Fg - D1-
Fi +, Ei: Assume for contradiction that there is o-sequence (q:)T=o with qu Fi and &r & E for all 0 < t & F. Let s > be the maximal value of such that the following properties hold.
al(;, a:) > 8
g(go(a;, 1)) +t b4 < glar(a, G-1)) < min [g(g (bi, ci-1).
50n }
(1, g(1 50n t 2c.
30

---

Note that s is well defined because the above properties hold for = 0 (as qu E Fi \ E1). Because g(go(a,, c--1))
g 50m). must hold that
B2
log (1/7)/ 128 log (100n) T.
(39)
However, we then have
l0+1 a4)
8
( az C--1)) +
61 & g ( G-11):
DS
g (bi, (-1)
g(1
50n
(s + 1) 2c.
(40)
Therefore, by the maximality of
40
g(s+t1 (a;,0)))))))) > min (1
50n ) (s + 1) 2c 2
g(1
50n
B6 39
(log (50n) 1) - -27cclog (100n)
R6
log n + log 50
257 log n 600
257
log 100
log (vn) g(1 n2 1/2).
600
But then 9s+1 E1, contradiction. So in fact F1 , E1.
G1 by Fi: Assume for contradiction that there is o d-sequence (4: (== with go G1 and qe $ Fi
for all 0 & & r. Let s > 0 be the maximal value of t such that the following properties hold.
g(go(c,, a:)) S < glaa(c, a:)) g
q: C- > 8
qe(b,, 1-1) >
50%
Note that s is well defined because the above properties hold for = 0 (as qo E G1 Fi), Because g(go(c,, 0:)) + T 32 > ( it must hold that T. However, we then have
(00l(,, a:))
g(q=-1 az)),
C
as+1 as+1 (0;, C--1)
a (bi, C--1)
50m
If additionally g(1x+1(c; ac)) ( then have contradiction to the maximality of s, whereas g(9.+1((e)))) (c,, aa)) > ) then we have g++1 E Fj. either case we obtain contradiction, and so in fact G1 +, Fi.
H +, U2; Assume for contradiction that there is é-sequence (4:)== with go H and & G1 GG2 for all 0 & t & т. Using C7 and D7 we have <(p) C H for every p E H, so we in fact assume that q E H \ (G1 G2) for every 0 & t & Let h Q R be given by
h(p) = g(((a, (-1)) + g(p(pppp G-1)). If (c; 8. then we have
35
h(g(+1)
ga 4-1)) + 64 + plal G-1)) 2c h(g)) + 128
whereas if (e( ax) then (c, b.) > 1 and hence we have
C3 glg,(an c --11) ()) 2c + g(g (b.,
A2 h(g))
1(ge+1)
())
57
125
From this we deduce that h(g+) > h(go) + -e contradiction to the range of h. Therefore,
H , G1 U G2.
A +, H: Suppose that (4:) is a d-squennce with gn A,-1- 1. By induction on t, the following properties hold for every Ettr
g(gr(ai, (-) > min {g(7) + t _. (.)))) c-1)) > min (g(r) + t- o 9())}
31

---

Q4
A3
Q/2
Q1
C4
b3
C2
b2
b
GD
Figure 7: The game RLO((101).
Indeed, the condition on ( 1--1) follows from
C6
and
and the condition on ge (b,, G-11)
follows from D6 and D7 Because, using B2 g(7)
log (1/?) 7 g( then have
4r E H.
We have now shown that A;-1 ++, H -, G1 G2, B A, and Gj: ->, FR + Eg. + we can deduce that A;-1 Str A holds for every i [n], and hence (by E1 that Ao Srn An. Thus, as Ao Q. every sequence sequence (q.)==0 Jrnn t E [8Tn]. However, using Lemma D.16 this implies that f4+1.-..:fsm Isrn E A, also. Therefore, gp (Q) S An, as required.
De Syr Ck S, for E [2]. By applying E1 and E2
with ge E Φ for every t E [8Tn] must satisfy Or An for some
E
Supplementary material to Section 6
E.1 A generalisation of Reciprocal LeadingOnes
Given a bitstring = {0, 1 we define RLO(z) (Reciprocal LeadingOnes with target 2) be the impartial combinatorial game G = (V, F, Po) with the following definition.
V {c,} u (Ulein) 6,, (--1,(-11
00
{an:
if Ca.
(c--)
if 02 or v bi.
F(v)=
{c--1)
if 4-1 1-=(1)
(ai,bi}
if o =(1)
and
< &
if z(1)
Note that all instances of RLO(2) are isomorphic to RLO. An example instance is shown in Figure 7
Given an instance RLO(z) of Reciprocal LeadingOnes, there is natural bijection from & (0, 1 3m + XRILO(2) given by
(()(((()))))))
fa.
if 1. x 0,
66
(a,) cg e(++)
(bx) c; (2n+1)
For the sake of a clearer correspondence between our search domain and existing black box models for evolutionary algorithms, and also a neater proof, we will always identify strategies for RLO(z) using this identification, and hence adopt X' = {0, }:3n as the problem's 's search domain. With this
convention, we remark that the discussion of Proposition 3.2 implies that
Opt(RLO(z)) (x E X x(n
(2n + i) =(i) for all E [n]]]
E.2 Proof of Theorem 6.1
Proving Theorem 6. relies on the following preliminaries.
Lemma E.1. Suppose that 2, 10, satisfy 2(i) = 21) = whenever i & m. Let x. E and y Uni Then,
P(fRLO(e)(E, * fRLOCE) v)) < "
(41)
32

---

Proof. Observe that for each w E {2,2²} and j E {0...., m). exactly one player out of x or takes the turn at position c) in play of (w)(w) using z and y (where we here interpret losing due to being unable to move at og as "taking a turn). Let us use (z(w) to denote the event that this turn is taken by x and (w) denote the event that this turn is taken by y. Finally, let define the event E = (2) A (3())) V (X)(2) A Xz(2)),
and note that Eg occurs if and only if (RL v) + (x, v)-
If for some j E {l...., m) find that Ej does not occur, then the plays of RLO(z) and RLO(=') have coalesced, and so Ej-1 also does not occur. In particular, we have
Ej E
whenever & j & m.
(42)
and hence,
77
PP Ea)
P(A 10 Ej) P(Em) II P(Em-) M Es)
m P(Em) II P(Em-s Em---1) & II P(Em)s Em- II P(E Ey).
m
m
j=1
j=1
Finally, observe that
E -(o(x(c)))==(( P(y(e)) =v) p()()))=o)) =))= 1
P(E E2) = = =
(E(a),b)
Thus, we deduce that P(E)) < 2- as required.
We will use a coupling to prove the desired result (for a general background on coupling in the context of evolutionary computing, see [3 ()). For this, we will first require the notion of total variation and the coupling lemma, as follows. (Note that these notions are usually described in terms of the distributions of the variables, rather than the variables themselves as we have done here for conciseness.)
Definition E.2. Let S be a countable set, and let X1 and X2 be S-valued random variables. The total variation distance between X1 and X2 defined as
dTv(X1, max IP(X, A) A)I.
ASS
The following lemma is Proposition 4.7 of 30 Lemma E.3. Let be a countable set, and let X1 and X2 be S-valued random variables. Then the following properties hold.
G1 dxv X2) = inf (P(X; + X2 (81, X2) is a coupling of X, and X2)-
G2 There exists a coupling (X1, X2) of X, and X2 such that drv (X1, X2) P(Xi X2). It is well-known (see Proposition 4.2 of (30) that the total variation distance satisfies
drv(X (X,, X2)
PP s) - P(X2 = 8)1-
(43)
.ES
In particular,
G2 implies the existence of a coupling (X, X2) of X1 and X2 such that p X2) > 1 drv (X1,
PPX1 8) P(X2 s)
2 SES
suPie/2 P(X, = s) inf,e P(X: = =s)
1
2 SES
P(X; = s) + P(X2 = s) 2 inf P(x; = 8)
2
$ES
Σ
inf P(X; = s).
#ES
33

---

We require generalisation of [2 that extends this observation to larger families of random variables, as follows (see Theorem 4.2 of 46
Lemma E.A. Let S be countable Suppose that (Xs)EEI is famity of S-valued random variables.
Then there is a coupling (Xi)ser of (Xi)xe such that P(N,jEIX; = Xj) Eves infier P(X; s).
The following key lemma for Theorem 6.1 may apply to other settings, and may also generalise to uncountable S C.R
Lemma E.S. Suppose that is finite indexing set, S S IR is countable, (fi)eer is family of stochastic payoff functions X + P(8), and (Bi)ier a family of pairwise disjoint subsets of X. Suppose that > O satisfies
Σ SES
i(free = = 3>>1- for every X.
Let A be any instance of Algorithm 2 It then holds for any T 3 0 that
1
PIT 7| 5
1 +
1
Proof. For every x E X, we have Eves in (z) > E. Thus, using Lemma E.4 for each t E N and x E X, let (f((tx)))ie be coupling of the family of random variables (x))) satisfying P(As,jerfs((,a)) = x)) 2 -
We will simulate -mny parallel runs of A, one on each stochastic function in (fi)ee,, which are carefully coupled together. To do this, we first perform the following steps independently of each other.
Sample Ln ~ do.
For all (t: (t) ENxII X, sample at(x:) f((
For all (t; zo. ................................ Tri ao ................................ ai) N X St+1, sample
8 (xo............................. Zri ao. ar) ie (Zo. Fzi ao, .......))) at).
Given E L, the sequence (x)) is then defined recursively via
o 40: a: = (x)))
o[+1 2e+1 (#) ... 2/: ag. a.).
The result is that each (2/)120 is identical in distribution to run of A on St.
Given t, let E, be the event that the sequences (a))trr are identical for E 1, so that P(E))) = 1. Note that if E,, occurs, then in fact the sequences (#/) also identical, (Tz)egr say, for i T. Thus,
P(E++1 > (() P(A.. x+) [
Thus, we deduce that IPEE,) > (1-s)* > 1- TE. Because the sets (Bi)ier are disjoint, in the event that Æ,-1 occurs, most of the parallel runs can have hit their objective B,. Therefore, if C, is the random variable counting the number of parallel runs that have hit their objective before time we obtain
E[C, P(E,-1) - (1 P(E.-1))
PTT <
11
Tr = T (11 +
< T
required.
34

---

With the tools we have introduced, proving Theorem 6.1 is now easy. We use Lemma E.1 to establish that, with high probability, run of A on RLO(1") will be indistinguishable from a run of A on (I)0(=) if and 1 agree on the final n/3 bits. Thus, there is no real reason to find the optimal strategy for RI.O(1)) as opposed to the optimal strategy for many other instances of RIO that appear similar against random strategies.
Proof of Theurem 6.
Let
== {= E 13" 2(1) whenever & <n/3,,
so that |2| = 2 For any x X' and z, E Z, by noting that sampling y ~ Unif(A)) produces
coupling (JRLO(=)( v), JRLOer v)) of (g=(x)) (x)), we have
G1
drv(g> 9x
P ((f y) + fRLOCZ) y)) $ 2 n/3
2-/33
(44)
Given & E 1- and x X. let 2(k, x) satisfy P(fz(x.)) k) in ((fz(2) ls). We now have for every X' that
Σ
inf P(g. (z) = k)) ((gx(a.))()) 1) P( = -11 sE2
k6(-1.1)
1 P(ge(e,1) = 1) P()
> 1 -d
92(1, 9 0=(x,_1)(x))
2 n/3 2-/3
Therefore, we can apply Lemma E.5 with E = 2 -/3 to obtain.
(1 2n/8| 2n/8 8
2n/3 3 + 2-n33 < 2--n/e (2-2n/3
In particular, there is some E 13" such that PPTT (Opt(g))) < 2n/88] & 2-n/8 required.
E.3 Proof of Corollary 6.2
We quickly outline some further notation for this proof. Sym((3z) will be used to denote the set of bijections o [3n] + [3n]. We recall that X' := {0. 1] 1 (as per Section 6)) and additionally use t to denote the exclusive or-operation on bitstrings, and 0b : + X' to denote the permutation over bitstrings associated to defined via (z(2)(1) = xi)) Finally,
say that real-valued random
variables A and B are equal in distribution, written A _ B Bir < x) P(B < x) holds for every IR
We adopt the following definition of unbiased variation (28]
Definition E.6. variation operator v X x R P(X) unbiased the following conditions are satisfied for all æ1...., Tk, X' and aj,.... E R.
H1 For all E X,
u(a p....,,r5ja 01 "........,...... (x."),...,.)))))) v(x1 @ ,, 4 2; d........ ax) ① z).
H2 For all Sym([3n))
o(z Tsi 01 T,. (x) = ((ou(z))....,,oe (.l (ob(v)))
We are now ready prove Corollary 6.2
Proof of Corollary 6.2 Given a bitstring ws E X' and a set B S X. let us define B @ w S X' via
B w = {i c wewwa B). Furthermore, Given bitstring w E X' and function g : X + S. let us define g 0 w: X R via
(g 2 ()(x) g(x w).
35

---

Note that for any set B S X, function g X + R, and bitstring E A' we have
(x _ T (B@))
(45)
By Theorem 6.1 there exists 3 E {0, 1 such that PTT (Op((R))(()) < 2n/8] & 2- For any 2 E {0, 1 let wa E &' be defined by
if = 0, if E [1,2] and z(i) = z(i),
Wg (kn + i)
if [1,2] and z(1) + =()).
Observe that 9= = 9E t w, and Op((RLO(2) = Opt(RLO(3)) + W2 Hence,
P77x (Opt(RLO(z)) < 2"/8] PTT (Opt(RLO(z)) Bw,) < 2n/²]
P P (Op(ROOO ())) < 2" < 2-n//
as required.
36

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction claim proofs of two theoretical results that help shed light on the role of diverse and challenging opponents for CoEAs. The first these is upper bound for the runtime of Tournament UMDA on combinatorial game called Reciprocal LeadingOnes (Theorem 5.2) and its proof contains detailed analysis of how progress is maintained by sampling opponents that are challenging where necessary and diverse where beneficial to the learning process this is explained in detail in the proof sketch of Section [5] The second main claim, that EAs playing against random opponents cannot efficiently optimise Reciprocal LeadingOnes, is handled in Section 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: A possible gap between the theoretical upper bound of Theorem 5.2 is dis- cussed at the end of Section 4 and we highlight that the challenge in closing the gap arises from the fact that our analysis assisted by assumptions on population size. We point out again in the concluding remarks that improvements can only be made by considering smaller population sizes.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-ted system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
37

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The full version statements for the two results (Theorems 5.2 and 6. include
all necessary assumptions, and care is taken in Sections[annd to precisely define all relevant algorithms and terminology. Corresponding proofs are provided in full in Appendices D and and detailed proof sketch of the main result is the focus of Section References are provided for all preliminary results upon which our proofs depend. Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All algorithms and games used to perform the empirical analysis of Section are provided with references in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
38

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e-g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The codebase used to run the experiments in this paper is part of a large software framework which has been in development for over decade, and at this time a decision has not been made about whether to release this framework.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/guides/ mublit//giidess/ooeeettniesss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Methodology, explanations of how runtime was calculated, and the minimisa- tion used to determine population size are all explained in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental
material.
7. Experiment statistical significance
39

---

Question: Does the paper report enror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are included in the comparison of distributions of runtimes for range of CoEAs on various combinatorial games (Figure and the coefficient of determi- nation is provided in Figure 3 which analyses how runtimes for two different instances of Tournament UMDA on Reciprocal LeadingOnes scale with n. The statistical significance of the difference in performance for the two instances of Tournament UMDA was verified using Welch's 's t-test, as detailed in Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details of compute, memory and wall-clock time, both for individual experi- ments and aggregated, are provided in Appendix B and signposted in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research has been conducted fully in accordance with the NeurlPS Code of Ethics.
40

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: In Section we explain the how the demand for robust theory for self-play algorithms (which are fundamental to multi-agent systems), and in particular for CoEAs, is addressed by our theoretical results. As our work is a theoretical analysis of fundamental aspects of CoEAs on benchmark problems, there are no foreseeable negative societal impacts of note.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
41

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cow datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
42

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.MM policy httppp//eeeerrpspscc////fteeeees for what should or should not be described.
43


Reviews:
[{"review_id": "zuFkP0dBDf", "reviewer": "Reviewer_c2zm", "summary": "The authors conduct runtime analysis of an existing competitive co-evolutionary algorithm (CoEA), the univariate marginal distribution algorithm (UMDA), on a specific combinatorial game (Reciprocal LeadingOne, RLO). By introducing a novel mutation operator, for suitably small games the authors show that UMDA's runtime on RLO has an upper bound $\\mathcal{O}(n\\log^2n)$, improving on the previously known tightest upper bound. The authors also show that their variant of UMDA on RLO has a runtime lower bound of $\\mathcal{O}(n^2\\log n)$, which is the first lower bound established in this setting. The authors also present a corollary showing that not just population diversity, but also coevolutionary feedback between player and opponent is fundamental to learning.", "questions": "* RLO is arguably a very artificial game - to what extent does your approach transfer to games of more practical interest?\n* What would be the significance of finding analogous results for EDAs?\n* Can you explain - in a practical context - what \"small\" means wrt game (as you are saying that $\\mathcal{O}(\\sqrt{n})$ games may have better asymptotic bounds)?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Strengths\n\n* The paper is of utmost clarity and very well-written.\n* The theoretical results, as far as I have been able to verify them in detail, represent significant progress in the chosen setting.\n* The empirical results do illustrate practical utility in the authors' chosen mutation operator across a variety of games (Table 1), although it remains unclear whether the results are statistically significant (also see Figure 2).\n\n# Weaknesses\n\n* While I appreciate the novelty of the theoretical results, I am not convinced about the wider theoretical extendability of the authors' findings outside of the chosen UMDA/RLO setting. \n* Likewise, I am not entirely convinced whether the authors' presented empirical results (Figure 2) indeed add evidence for the practical utility of their mutation operator.\n* Figure 3 seems to be missing confidence intervals.", "was_revised": true, "final_justification": "I maintain my high accepting score after carefully engaging with the authors' rebuttal.", "rebuttal": "Many thanks for your detailed and helpful review. We are grateful for your kind comments about the clarity and written quality of the paper as well as the significance of the analysis.\n\n**Motivating RLO.** RLO may appear artificial at first, but it is archetypical of games that require retention of knowledge. This motivation is explained in detail in our response to Reviewer 97ie.\n\n**The meaning of “small”.** The results presented are stated in terms of n, which always represents the number of game positions. For example, when we derive polynomial runtimes, this means polynomial in terms of the number of game positions. A key limitation here is that the most challenging and interesting combinatorial games (such as Chess or Go) have a combinatorial explosion in the number of positions, and so a result that is polynomial in the number of positions is not practical. In this sense, we say “small” to refer to so-called model or toy games where the number of positions is sufficiently limited for results expressed in this way to be meaningful. We emphasise (as discussed in lines 40-55) that analysis of coevolution on model games is most remarkable in that it provides insights into averting challenges faced by the algorithms more generally.\n\n**Extending our approach.** Our proof provides a framework which can in principle be extended to other games, and we have discussed this in our response to Reviewer 7KRp. In terms of extending the analysis to games of practical interest, the most important consideration relates to moving beyond the model games described above. For very large and interesting games it is impractical to list an explicit move preference at every position. In such settings players use models to map representations of game positions onto move preferences. The most significant challenge is to find a way to adapt theoretical analysis from the exhaustive representation in this paper to a simple instance of such a model. Nonetheless, even for complex models on practical games, the need for diverse and challenging opponents in multi-agent training has been observed empirically [A, B, C]. Our work is the first to analyse this need theoretically for coevolutionary algorithms, and will play an important role in future analysis on practical games.\n\nWe are unsure what is meant by analogous results for EDAs, as the algorithm we analyse is a coevolutionary instance of an EDA (see line 113). If your question concerns how to prove analogous results for a non-coevolutionary EDAs, then our black-box results in Section 6 indicate this is not generally feasible (see lines 301-302).\n\nWe believe the statistical significance of the impact of the mutation operator is demonstrated using Welch’s t-test in Table 1, which presents the same data as Figure 2 just restricted to the two versions of Tournament UMDA (which are most critical for comparison). Can you please advise if there is a particular experiment or statistical analysis we could provide that would strengthen the empirical evidence?\n\nFollowing your advice and similar suggestions from other reviews, confidence intervals will be added to Figure 3. Thank you also for your detailed list of corrections.\n\n\n[A] Vinyals, O., Babuschkin, I., Czarnecki, W.M. et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575, 350–354 (2019).\n\n[B] Ranjeet, T.R., Masek, M., Hingston, P., Lam, CP. (2011). The Effects of Diversity Maintenance on Coevolution for an Intransitive Numbers Problem. In: Wang, D., Reynolds, M. (eds) AI 2011: Advances in Artificial Intelligence. AI 2011. Lecture Notes in Computer Science(), vol 7106. Springer, Berlin, Heidelberg.\n\n[C] Lubberts, A. and Miikkulainen, R., 2001, July. Co-evolving a go-playing neural network. In Genetic and Evolutionary Computation Conference GECCO 2001."}, {"review_id": "z9aBJXZ2mX", "reviewer": "Reviewer_97ie", "summary": "The manuscript applies the Estimation-of-Distribution Algorithm Tournament UMDA to a newly introduced combinatorial game, Reciprocal LeadingOnes (RLO). It derives a better upper bound on the expected runtime for solving RLO and reports empirical results on several small-scale games that suggest a performance advantage over baseline methods.", "questions": "- Please address the three points raised in the “Weaknesses” section above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths.\n- **Improved theoretical bound** The analysis yields a better upper bound on runtime than earlier results, marking clear analytical progress.\n\n- **Potential broader impact** Although the experiments target relatively simple games, the approach could generalise to more complex domains, mirroring the way EDA-inspired ideas have influenced large-scale systems such as AlphaStar.\n\nWeaknesses.\n- **Novelty of the algorithm** Because Tournament UMDA itself was introduced in reference [3], the contribution here appears to be its application and analysis. Please clarify which aspects-parameter settings, proof techniques, or new insights-differ from the original proposal.\n\n- **Status of RLO** The paper seems to be the first to study Reciprocal LeadingOnes. If RLO is indeed novel, please state this explicitly and outline why analysing this game is interesting or representative of a broader problem class.\n\n- **Significance of the bound** The prior bound you improve upon was obtained with the same algorithm in a very recent study [3]. Please elaborate on why this incremental improvement matters-for example, does it reveal new theoretical behaviour or enable practical speed-ups on larger instances?\n\nMinor Comments\n- **Comprehensive appendix** The detailed proof in the appendix is valuable. Including a concise, reader-friendly proof sketch in the main text (e.g., an outline of key lemmas and ideas) would make the paper easier to follow without forcing readers to consult supplementary material.\n\n- **Figure 2 readability** The legend font is too small; please enlarge it for clarity.", "was_revised": true, "final_justification": "My main initial concern was about the novelty of this work in comparison to reference [3]. The authors' rebuttal has clarified this point to my satisfaction, so I have revised my rating.", "rebuttal": "Thank you for your helpful review. We are pleased that you recognise the progress made by our analysis and potential broader impact on large-scale systems. In reply to your request to address the weaknesses set out in your review:\n\n**Novel operator.** The most novel aspect of our approach is the introduction of the operator Mutate (Definition 2.2), which is applied after each selection step in Algorithm 1. This is a novel feature which is not present in the original proposal [3], and a major contribution of this paper is theoretical and empirical insights into the stabilising effect it has on the algorithm.\nFigure 3 and the subsequent discussion highlights the empirical effects on runtime compared to the original proposal (c=0 corresponds to the original proposal, c=0.05 corresponds to use of the novel operator).\nThe stabilising effect of the operator has an important and enabling role in the theoretical analysis. This is discussed at a high level in lines 274-282, and has a recurring effect on the proof contained in Appendix E.\nFurther discussion and visualisation of the impact of this novel feature which was too detailed for inclusion in the main text is provided in Appendix D.2.\nOur paper also presents novel proof techniques, detailed in our comments about the significance of the bound.\n\n**Novel proof technique.** Our proof requires careful analysis of a non-linear multidimensional stochastic process. As discussed in lines 262-273, existing tools to handle such cases are very limited. We develop a novel proof technique that sequentially restricts the multidimensional space (cf. Figure 5 and the surrounding discussion) that could be applied in other such cases.\n\n**Significance of bound.** The prior bound that we improve upon is a very general bound that applies to arbitrary combinatorial games. However due to this generality of the bound, it is often far weaker than observed performance. Indeed, it was stated in the conclusion of [3] that the proof of the original bound did not account for the accelerated learning due to players capitalising on the mistakes of their opponents, and that the general bound “could be greatly improved through closer analysis of coevolutionary dynamics, especially for specific games”. Our analysis is significant because it demonstrates that by accounting for these interactions one can prove a bound that essentially matches best possible. We also point out that our result includes a lower bound on runtime, whereas [3] only proves an upper bound.\n\n**RLO is archetypical of games that require the retention of learned knowledge.** Whether it’s Chess or Nim, in order to guarantee optimal play in a combinatorial game it is not enough to simply put yourself in a winning position – you must then also maintain the upper hand by responding correctly to any difficult position your opponent could put you in later. This makes learning optimal play difficult, as each play of a game only bears witness to a fraction of the possible positions. It is in this way that learning is improved by training against opponents that are both challenging (so that difficult positions occur) and diverse (so that a *range* of difficult positions occur). RLO captures this notion perfectly – in each play of the game only one of each $a_i$ or $b_i$ can be encountered, yet optimal play necessitates perfect play at both. Like established games it is difficult for coevolutionary algorithms to optimise (see Figure 2), yet the regular structure keeps it amenable to theoretical analysis."}, {"review_id": "Uh6Rytxz9G", "reviewer": "Reviewer_ZkQQ", "summary": "The paper continues the line of work that analyse self-playing Univariate Marginal Distribution Algorithm in combinatorial games. A game, whose optimal strategies are characterized by a sequence of independent \"correct\" moves, is introduced as a testbed to analyse the dynamic of coevolution. The analysis provides insight into the utility of maintaining diverse opponents in finding marginal move distributions aligned with optimal strategies. This insight is demonstrated empirically.", "questions": "Theorem 1.1 summarizes the upper bound as $O(n^2\\log^3n)$. This means that $C_{pop}$ in Theorem 5.2 is $O(1)$. It is not clear how the assumption of Theorem 5.2 implies this. Is it not possible that $C_{pop}$ is $\\Theta(n)$ or $\\Theta(\\log n)$?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The studied problem is significantly more challenging than optimizing LeadingOnes since there is no measure of \"progress\" towards optimal play. Rather, the algorithm is responsible for maintaining this \"measure\" via self-play, in the form of adversarial strategies. The simplicity of the combinatorial game, thus, helps expose the effect of opponent distributions on the discovery of best strategies. As such, the study gives meaningful insight into the self-play dynamics, which is reminiscent of the bias-variance trade-off phenomenon in reinforcement learning.\n\nThe theoretical findings are summarized in two theorems. The second one is particularly useful since it applies to general black-box searchers. On the other hand, the first one is conditioned on rather stringent parameter settings and the use of the novel mutation operator. A more fine-grained analysis of the effect of the mutation's parameter $c$ on the discovery time distribution would be appreciated.\n\nThe proof details are very involved, and not described in a self-contained manner. Following the proofs is challenging as the result.\n\nSome minor things:\n\nOne of the two experiments in the paper is not presented with enough information. Specifically the one on the RLO: the number of runs is not given and the variances are not shown. Adding log-scaled variance whiskers to the points in Figure 3 should suffice.\n\nFigure 4: two more trajectories (one for each subfigure) should probably be added whose starting point matches the initial distribution $p_0$ in Algorithm 1.\n\nFigure 6: perhaps the overall runtimes can be added to the second set of images to contextualize the horizontal scaling.\n\nRasterized images are used in figures. It is advisable to use vectorized images instead.", "was_revised": true, "final_justification": "The authors addressed the concern that the implication of the main theorem can be misinterpreted as the novel relation is not sufficiently explained in the main text, while simultaneously offers a very loose coupling between the operands. While the latter strengthens the claim itself, it can obfuscate the insight on parameter selection. Assuming that this clarity issue will be addressed in a subsequent revision, I will keep my score.", "rebuttal": "Thank you very much for your helpful and detailed review. We are very pleased you recognise the challenge inherent in the studied problem and the usefulness of the result for black-box searchers.\n\nTo answer your question about $C_{\\text{pop}}$: Indeed, $C_{\\text{pop}}$ is $O(1)$ in Theorem 1.1. It is likely that the lack of clarity here has come about from the use of hierarchy notation $\\ll$ which, while convenient for concisely stating relations between constants, is not always standardised across all disciplines and sub-disciplines. In the sense we are using it (which is stated formally in Appendix A), the assumption $1/n_0 \\ll 1/C_{\\text{pop}} \\ll c \\ll 1/K$ is essentially the same as “for fixed $n_0$, $C_\\text{pop}$, $c$, $K$, the following holds provided provided $c$ is sufficiently small (how small depends on $K$), $C$ is sufficiently large (how large depends on $c$), $n_0$ is sufficiently large (how large depends on $n_0$)”. Because the subsequent statement takes $n \\geqslant n_0$, all four of these numbers are $O(1)$ as $n\\to\\infty$. Therefore we certainly cannot allow $C_\\text{pop}$ to behave as a function of $n$, so it is not possible for it to be $\\Theta(n)$ or $\\Theta(\\log{n})$. We appreciate this is not obvious at a glance in the current notation, and so we can rewrite the theorem to make $C_\\text{pop}=O(1)$ clearer.\n\nOther reviewers have indicated the need for confidence intervals or variance whiskers in Figure 3, and we will gladly add these in any subsequent revisions. As with the other experiments in Section 4, each plotted runtime was calculated using 100 runs (using the population size that yielded best performance), and we will seek to clarify this in the main text. Thank you also for your suggested improvements to the other figures in the paper."}, {"review_id": "JqHX3dhSfi", "reviewer": "Reviewer_7KRp", "summary": "The main contribution of this paper is to advance the theoretical understanding of coevolution by undertaking a more detailed runtime analysis of CoEAs on combinatorial games, which are a challenging domain for CoEAs. Through this detailed analysis, it proves an improved upper bound, as well as a new lower bound that shows the result is tight up to a polylogarithmic factor. It also shows that an EA cannot efficiently optimise Reciprocal LeadingOnes if opponents are sampled purely uniformly at random.", "questions": "To what extent can the findings (other than Theorem 1.2/6.1, which applies generally) be generalized or extended to games beyond RLO? Would doing so require substantially different proof techniques?\n\nDo you currently have any theoretical insight on the c parameter of the Mutate operator (lines 202-212), or only empirical results?\n\nHow well do your results generalize to the non-binary case (lines 119-121)?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The idea presented in the paper seems sound. The exposition is mostly clear. Its findings are relevant to the field of CoEA and appear to be novel.\n\nPage-by-page comments and suggestions:\n\nPage 1:\n\n4: associated to -> associated with\n\n5: provide -> provide a\n\n28-32: Split into separate sentences\n\nPage 2:\n\n43: and so we consider this as a -> so we consider this a\n\n52: Add comma after \"even in such cases\"\n\n82-83: Put AlphaStar comment in new sentence\n\nPage 3:\n\n87: Add comma after \"In this paper\"\n\n88-89: Replace semicolon with period (new sentence)\n\n89: \"a method of ranking diversity\" Briefly elaborate.\n\n119: Make \"however...\" a new sentence\n\n120: \"we only use that when |S_i| = 2 the constraint...\" grammatically awkward, reword\n\n122: difference from -> difference to\n\n134: Put quotes around 'balanced' and 'stable', since these are technical terms that are being introduced\n\nPage 4:\n\n135: Suggest clarifying explicitly what the expectation is with respect to\n\n138: Suggest adding a brief informal description of LeadingOnes here\n\n148: state -> describe\n\n153: empty the -> empty, the\n\nPage 5:\n\nMove Figure 1 to this page, if possible\n\nPage 6:\n\nFigure 3: Consider adding error bars (e.g. standard error of the mean)\n\n190: Period before \"however\" (new sentence)\n\n194-195: Broken citations\n\n208: What is remarkable is that -> It is remarkable that, \n\nPage 8:\n\nFigure 5: Font size for the axes labels is too small\n\n252: who avoids -> avoids\n\n264-265: What precisely do you mean by \"is not guaranteed to exist in general\"?\n\n265: Add comma before \"there is\"\n\nPage 9:\n\n294: Add comma after \"In addition\"\n\n300: which has here been generalised -> which, here, has been generalised\n\n307: to to -> to", "was_revised": true, "final_justification": "The authors have answered my questions to my satisfaction. Although it would be nice to go beyond RLO, that setting is significant enough on its own, as the authors explained in their response to Reviewer 97ie. I encourage the authors to include this explanation in the paper for motivation. I lean toward acceptance.", "rebuttal": "Thank you very much for your detailed review and your many helpful suggestions to improve clarity, readability, and grammar.\n\n**To what extent can Theorem 1.2/5.2 be generalised or extended?** This is an important question. The overall proof technique is certainly not exclusive to the specific structure of RLO, and there is no innate reason it could not be applied to other combinatorial games. However, one way RLO simplifies our analysis is due to the fact it consists of a sequence or repeating “gadgets” (see Figure 1). Essentially, the vast majority of the proof analyses the dynamics on a single such gadget. If the structure of the game were more complex or varied then the same argument could be recreated, however this may be impractical given how involved the proof process is even for RLO. (We would also like to emphasise that there are valuable insights to be derived from analysing RLO itself, as outlined in the reply to Reviewer 97ie).\n\n**Theoretical insights into the parameter c.** Having c>0 plays an important and enabling role in our proof. The benefit given to us is explained at a very high level in lines 274-282 in the context of the overall proof idea, and its impact is described mathematically in Lemma E.3 (on which many critical steps in the proof ultimately rely). Our main result indicates that near best-possible performance is attained provided c is a sufficiently small constant, however we were not able to quantify theoretically exactly how small and whether there is an optimal theoretical parameter setting.\n\n**Generalisation to non-binary case.** This is another great question! We believe the proof should generalise fairly straightforwardly to the non-binary case, but with some additional details. Where the present proof focuses on $p(u,c_{i-1})$ (where $u\\in\\{a_i,b_i\\}$), one would instead need to focus on $\\sum_{v\\in W(u)}p(u,v)$, where $W(u)$ is the set of winning moves that can be made from $u$. As this is just a linear combination of the $p(u,v)$, many of the required bounds and equations follow just the same as with the existing analysis. One added complication is that in the present proof we need to show that (with the stabilising operator) players become on average “indifferent” between 2 losing moves; extending this part of the argument to more moves would require some careful analysis of both the constraint function and Mutate procedure. Nonetheless, ultimately the reason we chose to restrict attention to a binary case was to simplify notation and make the proof clearer."}]

Author rebuttal:

Meta-review: All reviewers recommend acceptance. The general opinion is that this paper is an interesting contribution to an important problem (the notoriously difficult dynamics of competitive coevolution).

Therefore, I recommend acceptance.
Decision: Accept (poster)