  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.
