# Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 50 references that are in the map.
- First posted on arXiv 7 May 2024.

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

- [Co-Evolutionary Compression for Unpaired Image Translation](https://mlsanity.com/paper/1907.10804/) (2019)
- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [Spatial Evolutionary Generative Adversarial Networks](https://mlsanity.com/paper/1905.12702/) (2019)
- [Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms](https://mlsanity.com/paper/1910.14389/) (2019)
- [Runtime Analysis of Competitive co-Evolutionary Algorithms for Maximin Optimisation of a Bilinear Function](https://mlsanity.com/paper/2206.15238/) (2022)
- [Self-adaptation in non-Elitist Evolutionary Algorithms on Discrete Problems with Unknown Structure](https://mlsanity.com/paper/2004.00327/) (2020)

## Abstract (arXiv)

Runtime analysis, as a branch of the theory of AI, studies how the number of iterations algorithms take before finding a solution (its runtime) depends on the design of the algorithm and the problem structure. Drift analysis is a state-of-the-art tool for estimating the runtime of randomised algorithms, such as evolutionary and bandit algorithms. Drift refers roughly to the expected progress towards the optimum per iteration. This paper considers the problem of deriving concentration tail-bounds on the runtime/regret of algorithms. It provides a novel drift theorem that gives precise exponential tail-bounds given positive, weak, zero and even negative drift. Previously, such exponential tail bounds were missing in the case of weak, zero, or negative drift. Our drift theorem can be used to prove a strong concentration of the runtime/regret of algorithms in AI. For example, we prove that the regret of the rwab bandit algorithm is highly concentrated, while previous analyses only considered the expected regret. This means that the algorithm obtains the optimum within a given time frame with high probability, i.e. a form of algorithm reliability. Moreover, our theorem implies that the time needed by the co-evolutionary algorithm RLS-PD to obtain a Nash equilibrium in a bilinear max-min-benchmark problem is highly concentrated. However, we also prove that the algorithm forgets the Nash equilibrium, and the time until this occurs is highly concentrated. This highlights a weakness in the RLS-PD which should be addressed by future work.