Extending the black-box complexity framework, we consider multistage stochastic optimisation problems under recourse. Such problems ask for a solution to an optimisation problem under uncertainty, where once the uncertainty is (partially) observed, in one or more stages, a stage-by-stage set of 'recourse' actions may be applied to repair the solution. These problems have been studied in the optimisation literature for decades, and applications include multistage portfolio investment, routing under uncertainty, and (dynamic) rescheduling. To facilitate rigorous complexity analysis of these problems in a black-box setting, we develop a precise, broad framework enabling us to describe what information is exchanged between the black-box and the optimisation algorithm, and what solution concept is used. To illustrate the power of the technique, we develop runtime bounds for evolutionary algorithms applied to stochastic optimisation problems with recourse. The theoretical results are complemented by experiments.

The maximin optimisation problem, inspired by Von Neumann’s work (von Neumann 1928) and widely applied in adversarial optimisation, has become a key research area in machine learning. Gradient Descent Ascent (GDA) is a common method for solving these problems but requires the pay-off function to be differentiable, making it unsuitable for discrete or binary functions that often occur in game-theoretical scenarios. Co-evolutionary algorithms (CoEAs), which are derivative-free, offer an alternative to these problems. However, the theoretical understanding of CoEAs is still limited. This paper provides the first rigorous runtime analysis of CoEAs with pairwise dominance on binary two-player zero-sum games (or maximin problems), specifically focusing on the DIAGONAL game. The mathematical analysis rigorously shows that the PDCoEA can efficiently find the optimum in polynomial runtime with high probability under low mutation rates and large population sizes. Empirical evidence also identifies an error threshold where higher mutation rates lead to inefficiency. In contrast, single-pair-individual algorithms, i.e., RLS-PD and (1+1)-CoEAs, fail to find the optimum in polynomial time. These findings highlight the usefulness of pairwise dominance, low mutation rates, and large populations in maintaining a “co-evolutionary arms race”.

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

Black-box optimisation is one of the important areas in optimisation. The original No Free Lunch (NFL) theorems highlight the limitations of traditional black-box optimisation and learning algorithms, serving as a theoretical foundation for traditional optimisation. No Free Lunch Analysis in adversarial (also called maximin) optimisation is a long-standing problem [45 , 46]. This paper first rigorously proves a (NFL) Theorem for general black-box adversarial optimisation when considering Pure Strategy Nash Equilibrium (NE) as the solution concept. We emphasise the solution concept (i.e. define the optimality in adversarial optimisation) as the key in our NFL theorem. In particular, if Nash Equilibrium is considered as the solution concept and the cost of the algorithm is measured in terms of the number of columns and rows queried in the payoff matrix, then the average performance of all black-box adversarial optimisation algorithms is the same. Moreover, we first introduce black-box complexity to analyse the black-box adversarial optimisation algorithm. We employ Yao’s Principle and our new NFL Theorem to provide general lower bounds for the query complexity of finding a Nash Equilibrium in adversarial optimisation. Finally, we illustrate the practical ramifications of our results on simple two-player zero-sum games. More specifically, no black-box optimisation algorithm for finding the unique Nash equilibrium in two-player zero-sum games can exceed logarithmic complexity relative to search space size. Meanwhile, no black-box algorithm can solve any bimatrix game with unique NE with fewer than a linear number of queries in the size of the payoff matrix.

Many Real-world optimisation tasks are increasingly large-scale optimisation (LSO) problems. Cooperative co-evolutionary algorithms (CoEAs), which involve more than two populations and utilise the divide-and-conquer approach, have been introduced to solve LSO problems more efficiently. However, the behaviour of cooperative CoEAs is not fully understood because the interactions between two or more populations make analysis challenging. Runtime analysis has improved the under-standing of traditional EAs. We argue that using runtime analysis of CoEAs could provide helpful insights, e.g., how their expected runtime depends on alaorithmic design decisions. In this paper, we show that the expected optimisation time of the basic cooperative co-evolutionary (1+1) EA (CC-(1+1) EA) on linear functions is$\Theta(n\log n)$. This solves an open conjecture by (Jansen and Wiegand, 2004). Moreover, empirical analysis is conducted on two more complicated problems: NK − LANDSCAPE and$k$-MAXSAT problems. Our results show that the CC-(1+1) EA perform similarly to the (1+1) EA on these problems. However, adjusting block length allows us to optimise its performance on the NK − LANDSCAPE problem. Our results provide a more precise bound for the expected runtime of CC-(1+1) EA and a more detailed empirical analysis of its behaviour on more complicated inseparable problems.

Co-evolutionary algorithms have found several applications in game-theoretic applications and optimisation problems with an adversary, particularly where the strategy space is discrete and exponentially large, and where classical game-theoretic methods fail. However, the application of co-evolutionary algorithms is difficult because they often display pathological behaviour, such as cyclic behaviour and evolutionary forgetting. These challenges have prevented the broad application of co-evolutionary algorithms.