  Quality-Diversity (QD) algorithms are a new type of Evolutionary Algorithms
(EAs), aiming to find a set of high-performing, yet diverse solutions. They
have found many successful applications in reinforcement learning and robotics,
helping improve the robustness in complex environments. Furthermore, they often
empirically find a better overall solution than traditional search algorithms
which explicitly search for a single highest-performing solution. However,
their theoretical analysis is far behind, leaving many fundamental questions
unexplored. In this paper, we try to shed some light on the optimization
ability of QD algorithms via rigorous running time analysis. By comparing the
popular QD algorithm MAP-Elites with $(\mu+1)$-EA (a typical EA focusing on
finding better objective values only), we prove that on two NP-hard problem
classes with wide applications, i.e., monotone approximately submodular
maximization with a size constraint, and set cover, MAP-Elites can achieve the
(asymptotically) optimal polynomial-time approximation ratio, while
$(\mu+1)$-EA requires exponential expected time on some instances. This
provides theoretical justification for that QD algorithms can be helpful for
optimization, and discloses that the simultaneous search for high-performing
solutions with diverse behaviors can provide stepping stones to good overall
solutions and help avoid local optima.
