Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm
  Configuration
  It has long been observed that the performance of evolutionary algorithms and
other randomized search heuristics can benefit from a non-static choice of the
parameters that steer their optimization behavior. Mechanisms that identify
suitable configurations on the fly ("parameter control") or via a dedicated
training process ("dynamic algorithm configuration") are therefore an important
component of modern evolutionary computation frameworks. Several approaches to
address the dynamic parameter setting problem exist, but we barely understand
which ones to prefer for which applications. As in classical benchmarking,
problem collections with a known ground truth can offer very meaningful
insights in this context. Unfortunately, settings with well-understood control
policies are very rare.
  One of the few exceptions for which we know which parameter settings minimize
the expected runtime is the LeadingOnes problem. We extend this benchmark by
analyzing optimal control policies that can select the parameters only from a
given portfolio of possible values. This also allows us to compute optimal
parameter portfolios of a given size. We demonstrate the usefulness of our
benchmarks by analyzing the behavior of the DDQN reinforcement learning
approach for dynamic algorithm configuration.
