André Biedenkapp

selected publications

1. Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration

   André Biedenkapp*, Nguyen Dang*, Martin S. Krejca*, Frank Hutter, and Carola Doerr

   In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’22), pp. 766–775, 2022 *Joint first authorship 🏅Won the best paper award on the GECH track.
   

   Abs arXiv Bib PDF Blog Code Website Talk

   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.

   @inproceedings{biedenkapp-gecco22a,
     title = {Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration},
     author = {Biedenkapp, André and Dang, Nguyen and Krejca, Martin S. and Hutter, Frank and Doerr, Carola},
     year = {2022},
     pages = {766--775},
     booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference ({GECCO}'22)},
   }

2. Automated Reinforcement Learning (AutoRL): A Survey and Open Problems

   Jack Parker-Holder, Raghu Rajan, Xingyou Song, André Biedenkapp, Yingjie Miao, Theresa Eimer, Baohe Zhang, Vu Nguyen, Roberto Calandra, Aleksandra Faust, Frank Hutter, and Marius Lindauer

   Journal of Artificial Intelligence Research (JAIR), 74, pp. 517-568, 2022
   

   Abs arXiv Bib PDF Poster Talk

   The combination of Reinforcement Learning (RL) with deep learning has led to a series of impressive feats, with many believing (deep) RL provides a path towards generally capable agents. However, the success of RL agents is often highly sensitive to design choices in the training process, which may require tedious and error-prone manual tuning. This makes it challenging to use RL for new problems, while also limits its full potential. In many other areas of machine learning, AutoML has shown it is possible to automate such design choices and has also yielded promising initial results when applied to RL. However, Automated Reinforcement Learning (AutoRL) involves not only standard applications of AutoML but also includes additional challenges unique to RL, that naturally produce a different set of methods. As such, AutoRL has been emerging as an important area of research in RL, providing promise in a variety of applications from RNA design to playing games such as Go. Given the diversity of methods and environments considered in RL, much of the research has been conducted in distinct subfields, ranging from meta-learning to evolution. In this survey we seek to unify the field of AutoRL, we provide a common taxonomy, discuss each area in detail and pose open problems which would be of interest to researchers going forward.

   @article{parker-holder-jair22a,
     title = {Automated Reinforcement Learning (AutoRL): A Survey and Open Problems},
     author = {Parker-Holder, Jack and Rajan, Raghu and Song, Xingyou and Biedenkapp, André and Miao, Yingjie and Eimer, Theresa and Zhang, Baohe and Nguyen, Vu and Calandra, Roberto and Faust, Aleksandra and Hutter, Frank and Lindauer, Marius},
     year = {2022},
     journal = {Journal of Artificial Intelligence Research (JAIR)},
     pages = {517-568},
     volume = {74},
     doi = {10.1613/jair.1.13596},
   }

3. TempoRL: Learning When to Act

   André Biedenkapp, Raghu Rajan, Frank Hutter, and Marius Lindauer

   In Proceedings of the 38th International Conference on Machine Learning (ICML 2021), 139, pp. 914–924, 2021
   

   Abs arXiv Bib PDF Supp Blog Code Poster Slides Talk

   Reinforcement learning is a powerful approach to learn behaviour through interactions with an environment. However, behaviours are usually learned in a purely reactive fashion, where an appropriate action is selected based on an observation. In this form, it is challenging to learn when it is necessary to execute new decisions. This makes learning inefficient, especially in environments that need various degrees of fine and coarse control. To address this, we propose a proactive setting in which the agent not only selects an action in a state but also for how long to commit to that action. Our TempoRL approach introduces skip connections between states and learns a skip-policy for repeating the same action along these skips. We demonstrate the effectiveness of TempoRL on a variety of traditional and deep RL environments, showing that our approach is capable of learning successful policies up to an order of magnitude faster than vanilla Q-learning.

   @inproceedings{biedenkapp-icml21,
     title = {TempoRL: Learning When to Act},
     author = {Biedenkapp, André and Rajan, Raghu and Hutter, Frank and Lindauer, Marius},
     year = {2021},
     volume = {139},
     pages = {914--924},
     booktitle = {Proceedings of the 38th International Conference on Machine Learning (ICML 2021)},
   }

4. Dynamic Algorithm Configuration: Foundation of a New Meta-Algorithmic Framework

   André Biedenkapp, Furkan H Bozkurt, Theresa Eimer, Frank Hutter, and Marius Lindauer

   In Proceedings of the Twenty-fourth European Conference on Artificial Intelligence (ECAI’20), pp. 427–434, 2020
   

   Abs Bib PDF Supp Blog Code Slides Talk

   The performance of many algorithms in the fields of hard combinatorial problem solving, machine learning or AI in general depends on parameter tuning. Automated methods have been proposed to alleviate users from the tedious and error-prone task of manually searching for performance-optimized configurations across a set of problem instances. However, there is still a lot of untapped potential through adjusting an algorithm’s parameters online since different parameter values can be optimal at different stages of the algorithm. Prior work showed that reinforcement learning is an effective approach to learn policies for online adjustments of algorithm parameters in a data-driven way. We extend that approach by formulating the resulting dynamic algorithm configuration as a contextual MDP, such that RL not only learns a policy for a single instance, but across a set of instances. To lay the foundation for studying dynamic algorithm configuration with RL in a controlled setting, we propose white-box benchmarks covering major aspects that make dynamic algorithm configuration a hard problem in practice and study the per- formance of various types of configuration strategies for them. On these white-box benchmarks, we show that (i) RL is a robust candidate for learning configuration policies, outperforming standard pa- rameter optimization approaches, such as classical algorithm configuration; (ii) based on function approximation, RL agents can learn to generalize to new types of instances; and (iii) self-paced learning can substantially improve the performance by selecting a useful sequence of training instances automatically.

   @inproceedings{biedenkapp-ecai20,
     title = {Dynamic Algorithm Configuration: Foundation of a New Meta-Algorithmic Framework},
     author = {Biedenkapp, André and Bozkurt, Furkan H and Eimer, Theresa and Hutter, Frank and Lindauer, Marius},
     year = {2020},
     pages = {427--434},
     booktitle = {Proceedings of the Twenty-fourth European Conference on Artificial Intelligence (ECAI'20)},
   }