Dynamic algorithm configuration by reinforcement learning

Abstract: The performance of algorithms, be it in the domain of machine learning, hard combinatorial problem solving or AI in general depends on their many parameters. Tuning an algorithm manually, however, is error-prone and very time-consuming. Many, if not most, algorithms are iterative in nature. Thus, they traverse a potentially diverse solution space, which might require different parameter settings at different stages to behave optimally. Further, algorithms are often used for solving a diverse set of problem instances, which by themselves might require different parameters. Taking all of this into account is infeasible for a human designer. Automated methods have therefore been proposed to mitigate human errors and minimize manual efforts. While such meta-algorithmic methods have shown large successes, there is still a lot of untapped potentials as prior approaches typically only consider configurations that do not change during an algorithm’s run or do not adapt to the problem instance.

In this dissertation, we present the first framework that is capable of dynamically
configuring algorithms, in other words, capable of adapting configurations to the problem instance at hand during an algorithm’s solving process. To this end, we model the dynamic algorithm configuration (DAC) problem as a contextual Markov decision process. This enables us to learn dynamic configuration policies in a data-driven way by means of reinforcement learning.

We empirically demonstrate the effectiveness of our framework on a diverse set of problem settings consisting of artificial benchmarks, evolutionary algorithms, AI planning systems, as well as deep learning. We show that DAC outperforms previous meta-algorithmic approaches. Building on these successes, we formulate the first standardized interface for dynamic configuration and an extensive benchmark to facilitate reproducibility and lower the barrier of entry for new researchers into this novel research field. Lastly, our work on DAC feeds back into the reinforcement learning paradigm. Through the lens of DAC, we identify shortcomings in current state-of-the-art approaches and demonstrate how to solve these. In particular, intending to learn general policies for DAC, our work pushes the boundaries of generalization in reinforcement learning. We demonstrate how to efficiently incorporate domain knowledge when training general agents and propose to move from a reactive way of doing reinforcement learning to a proactive way by learning when to make new decisions

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch
• Notes: Universität Freiburg, Dissertation, 2022

Classification and Topics

• Keyword: Maschinelles Lernen ; Bestärkendes Lernen ; Künstliche Intelligenz ; Maschinelles Lernen ; Bestärkendes Lernen ; Markov-Entscheidungsprozess

Contributors, Places and Time

• Event: Veröffentlichung
• (where): Freiburg
• (who): Universität
• (when): 2022
• Creator: Biedenkapp, André
• Contributor: Hutter, Frank ; Lindauer, Marius ; Hutter, Frank ; Doerr, Carola ; Albert-Ludwigs-Universität Freiburg. Institut für Informatik ; Maschinelles Lernen und Natürlichsprachliche Systeme, Professur Frank Hutter ; Albert-Ludwigs-Universität Freiburg. Fakultät für Angewandte Wissenschaften

Further information

• DOI: 10.6094/UNIFR/230869
• URN: urn:nbn:de:bsz:25-freidok-2308697
• Rights: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 25.03.2025, 1:57 PM CET