Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms

Per Kristian Lehre, Shishen Lin

Abstract

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 bandit and evolutionary algorithms. This paper considers the problem of deriving concentration tail-bounds on the runtime 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.

Introduction

In the theoretical analysis of AI, "drift analysis" is a fundamental tool used to estimate an algorithm's runtime by measuring the expected progress toward a solution in each step. While existing theorems are effective at calculating expected (average) runtimes, averages can be deceptive. A fast average runtime does not guarantee that an algorithm won't occasionally get stuck in a "nightmare scenario" for an excessive duration. To ensure "algorithm reliability," researchers require concentration tail-bounds—mathematical proofs that the actual runtime will not deviate significantly from the expectation.

This paper, presented at IJCAI-2024, addresses a critical gap in the literature: the lack of general exponential tail-bounds for cases where the drift is very weak, zero, or even slightly negative.

The Recurrent Method and Theorem 1

The authors introduce a "Recurrent Method" centered around a new variance-based drift theorem (Theorem 1). This theorem allows for the derivation of precise exponential tail-bounds even in challenging scenarios.

A key technical insight is that variance (randomness) can act as an engine. The authors prove that as long as an algorithm possesses sufficient variance, it can overcome small amounts of negative drift—where the algorithm occasionally moves away from the goal—and still reach the target quickly with high probability. Unlike traditional tools like the Azuma-Hoeffding inequality, which often require fixed step sizes, this method utilizes the Optional Stopping Time Theorem for martingales, allowing for the analysis of algorithms that make "large jumps" in the search space.

Applications in AI

The theoretical framework is applied to several benchmark problems and algorithms, demonstrating its versatility across different domains of AI.

Bandit Learning: RWAB

For the RWAB (Random Walk Across Boundaries) bandit algorithm, the paper proves that the regret—the reward missed by not picking the best arm—is highly concentrated. Specifically, the regret is at most $O(\sqrt{LT})$ with high probability (where $L$ is the number of changes and $T$ is time), matching theoretical lower bounds for optimality. This ensures the algorithm is reliable across different runs, not just on average.

Coevolutionary Search: RLS-PD

The analysis of the Randomized Local Search with Population Dynamics (RLS-PD) on the BILINEAR max-min benchmark revealed two significant findings:

  1. Efficiency: The algorithm finds a Nash Equilibrium (NE) in $O(n^{1.5})$ iterations with overwhelmingly high probability.
  2. Instability: The algorithm also "forgets" the NE and moves away from it just as quickly. This "evolutionary forgetting" is a critical instability that average-case analysis might overlook, suggesting a need for mechanisms to "lock in" solutions.

Key Results and Empirical Validation

The theoretical proofs are supported by empirical experiments involving 1,000 simulations per configuration. The results consistently show that the probability of an algorithm taking significantly longer than its average runtime decays exponentially.

Runtime distributions for the RLS-PD algorithm across various parameter settings, demonstrating concentrated performance.

As shown in the figure above, the runtime distributions for RLS-PD across various $\alpha$ and $\beta$ parameters exhibit a clear concentration around the mean. The "nightmare scenarios" where the algorithm fails to converge within a reasonable timeframe are vanishingly rare, confirming the reliability predicted by the new drift theorem. The empirical data aligns with the theoretical expectation that runtimes follow a distribution with a sharp peak and rapidly thinning tails.

Conclusion

This work provides a significant theoretical upgrade to the analysis of randomized AI algorithms. By providing tools to prove reliability through concentration tail-bounds, it moves the field beyond simple average-case analysis. Future work remains to sharpen the leading constants in these theorems and to extend these techniques to more complex Reinforcement Learning environments with larger state spaces. Additionally, addressing the "forgetting" phenomenon in coevolutionary algorithms is a key area for algorithmic improvement.

Summary updated

Abstract

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 bandit and evolutionary 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 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.
BibTeX
@inproceedings{lehre2024concentration,
  author = {Per Kristian Lehre and Shishen Lin},
  title = {{Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=f8iB5AAnRL},
}
Figure