Go to page

Bibliographic Metadata

  • Title
    Multi-armed bandits for trustworthy and resource-efficient algorithm configuration / Jasmin Brandt ; 1st Reviewer: Prof. Dr. Eyke Hüllermeier (Institute of Informatics Ludwig Maximilian University of Munich), 2nd Reviewer: Prof. Dr. Kevin Tierney (Decision and Operation Technologies Group Bielefeld University), Supervisor: Prof. Dr. Eyke Hüllermeier
  • Author
    Brandt, Jasmin
  • Degree supervisor
    Hüllermeier, Eyke ; Tierney, Kevin
  • Published
    Paderborn, 2025
  • Description
    1 Online-Ressource (xii, 164 Seiten)
  • Institutional Note
    Universität Paderborn, Dissertation, 2025
  • Annotation
    Tag der Verteidigung: 19.05.2025
  • Defended on
    2025-05-19
  • Language
    English
  • Document Types
    Dissertation (PhD)
  • Keywords (GND)
    Paderborn
  • URN
    urn:nbn:de:hbz:466:2-54833 
  • DOI
    10.17619/UNIPB/1-2270 
Links
Files
Classification
Zusammenfassung
  • Die Qualität und Laufzeit eines Algorithmus hängen maßgeblich von seinen internen Parametern ab, die in der Regel vom Benutzer vorab festgelegt werden müssen. Da es oft eine herausfordernde oder sogar unlösbare Aufgabe ist, optimale Werte für diese Parameter zu identifizieren, hat sich das Forschungsfeld der automatischen Algorithmenkonfiguration (engl. Algorithm Configuration) entwickelt. Allerdings fehlen den meisten bestehenden Methoden theoretische Garantien bezüglich der Qualität ihrer vorgeschlagenen Parameterkonfigurationen, was es den Nutzern erschwert, den Ergebnissen zu vertrauen. Im Gegensatz dazu bieten die wenigen Methoden, die nachweisbare Qualitätsgarantien für ihre Konfigurationen liefern, oft nicht die Ressourceneffizienz heuristischer Ansätze. Ein Ansatz zur Herleitung theoretischer Garantien besteht darin, Methoden aus gut erforschten theoretischen Kontexten, wie Mehrarmigen Banditen (engl. Multi-Armed Bandits), auf Algorithmenkonfigurationsprobleme anzuwenden und anzupassen. Solche Garantien stärken das Vertrauen der Nutzer in die Ergebnisse und stellen Ressourceneffizienz sicher, wenn das vom Konfigurator benötigte Budget eng mit der unteren Grenze übereinstimmt, die für die Lösung des Problems erforderlich ist. Dadurch bleibt die Vertrauenswürdigkeit gewahrt, ohne dass übermäßige Rechenkosten entstehen. Allerdings macht die Vielzahl an Varianten von Mehrarmigen Banditen – die für unterschiedliche Parallelisierungsmethoden, Beobachtungen oder Kriterien zur Auswahl des besten Arms konzipiert wurden – es schwierig, die geeignetste Methode für Algorithmenkonfiguration zu identifizieren. Zudem sollte ein idealer Konfigurator in der Lage sein, eine Vielzahl von Szenarien abzudecken, wie beispielsweise verschiedene Arten von Beobachtungen. Während spezialisierte Bereiche der Algorithmenkonfiguration, wie die Hyperparameteroptimierung (engl. Hyperparameter Optimization), bereits von Mehrarmigen Banditen-basierten Methoden wie Hyperband profitieren, die in der Praxis gut funktionieren und mit theoretischen Garantien ausgestattet sind, existiert für die allgemeinere Algorithmenkonfiguration derzeit keine vergleichbare Methode. Eine Herausforderung bei der Entwicklung von Algorithmenkonfigurationsmethoden mit theoretischen Garantien besteht darin, dass strikte Einhaltung theoretischer Grenzen nicht immer zu ressourceneffizienten Verfahren führt. Insbesondere die fehlende Kenntnis des Parameterkonfigurationsraums erfordert eine umfassende Exploration, was oft zu einer konservativ hohen Stichprobenanzahl führt. Diese Arbeit entwickelt Mehrarmige Banditen-basierte Algorithmenkonfigurationsmethoden in zwei Richtungen weiter, um sowohl die Ressourceneffizienz als auch die Vertrauenswürdigkeit zu verbessern. Erstens schlagen wir ein allgemeines Mehrarmiges Banditen-Framework vor und wenden es auf das Algorithmenkonfigurationsproblem an, während wir die Ressourceneffizienz durch theoretisch abgeleitete Budgetgrenzen wahren. Zweitens passen wir den bestehenden Hyperparameteroptimierungsalgorithmus Hyperband einschließlich seiner Mehrarmigen Banditen Subroutine Successive Halving an, um die Ressourceneffizienz weiter zu steigern und gleichzeitig die Vertrauenswürdigkeit durch theoretische Einschränkungen sicherzustellen. Konkret führen wir ein allgemeines kombinatorisches Banditen-Framework ein, bei dem in jedem Zeitschritt eine feste, aber zufällig große Menge von Armen parallel gespielt wird. Dieses Framework unterstützt sowohl numerische Belohnungen als auch präferenzbasierte Beobachtungen und identifiziert nachweislich einen optimalen Arm, wenn das verfügbare Budget für Armziehungen ausreichend groß ist. Darüber hinaus entspricht das erforderliche Budget der abgeleiteten unteren Grenze für solche Algorithmen, bis auf einen logarithmischen Faktor. Wir haben diese Methode zudem auf Algorithmenkonfiguration erweitert und die theoretischen Garantien übertragen. Insbesondere haben wir bewiesen, dass unser vorgeschlagener Konfigurator mit hoher Wahrscheinlichkeit eine nahezu optimale Konfiguration findet, wenn das Budget ausreichend ist, und empirisch gezeigt, dass unsere Methode die Leistungslücke zwischen heuristischen und theoretisch fundierten Konfiguratoren weiter schließt. Darüber hinaus stellt diese Arbeit eine Modifikation der bestehenden Mehrarmigen Banditenmethode Successive Halving (SHA) vor, die es ermöglicht, Beobachtungen aus vorherigen Läufen mit kleineren Budgets wiederzuverwenden. Dadurch werden nur minimale neue Stichproben benötigt. Wir haben gezeigt, dass dieselben theoretischen Garantien für den zurückgegebenen Arm gelten, als würde der Algorithmus von Grund auf mit vollständig neuen Stichproben ausgeführt. Außerdem haben wir diese Garantien mit denen verglichen, die wir für asynchrone Erweiterungen von SHA hergeleitet haben, die bisher nicht analysiert wurden. Schließlich haben wir unseren Algorithmus als Subroutine innerhalb des Hyperparameteroptimierungsgerüst Hyperband integriert, eine theoretische Analyse durchgeführt und seine verbesserte Effizienz durch experimentelle Studien validiert.
Abstract
  • The quality and runtime of an algorithm depend significantly on its internal parameters, which usually must be predefined by the user. Since identifying optimal values for these parameters is often daunting or even infeasible, the field of automatic Algorithm Configuration (AC) has emerged. However, most existing methods lack theoretical guarantees regarding the quality of their suggested parameter configurations, making it challenging for users to trust their outcomes. Conversely, the few state-of-the-art methods that provide provable quality guarantees for their configurations often fail to match the resource efficiency of heuristic methods. One approach to derive theoretical guarantees is to adapt and apply methods from well-studied theoretical settings, such as Multi-Armed Bandits (MABs), to AC problems. Providing such guarantees instills user trust and ensures resource efficiency when the configurator's required budget aligns closely with the lower bound necessary to solve the problem. This ensures trustworthiness without excessive computational costs. However, the multitude of MAB variants — designed for different parallelization methods, feedback types, or winning-arm criteria — makes it challenging to identify the most suitable approach for AC. Additionally, an ideal configurator should handle a wide range of scenarios, such as different types of feedback.While specialized areas of AC, such as Hyperparameter Optimization (HPO), already benefit from MAB-based methods like Hyperband, which performs well in practice and comes with theoretical guarantees, no comparable approach exists for the more general AC setting. A challenge in developing AC methods with theoretical guarantees is that strict adherence to theoretical limits does not always result in resource-efficient methods. In particular, the lack of knowledge about the parameter configuration space necessitates extensive exploration, often leading to conservatively high sampling budgets. This thesis advances MAB-based AC methods in two directions to improve both resource efficiency and trustworthiness. First, we propose a general MAB framework and apply it to the broader AC setting while maintaining resource efficiency through theoretically derived budget bounds. Second, we adapt the existing HPO algorithm Hyperband, including its MAB subroutine Successive Halving, to enhance resource efficiency while preserving trustworthiness through theoretical constraints. Specifically, we introduce a general Combinatorial Bandit framework in which a fixed but random-sized set of arms is played in parallel at each time step. This framework accommodates both numerical rewards and preference-based feedback and provably identifies an optimal arm when the available budget of arm pulls is sufficiently large. Furthermore, the necessary budget matches the derived lower bound for such algorithms, up to a logarithmic factor. We also extended and applied this method to the AC setting, transferring the theoretical guarantees. Notably, we proved that our proposed configurator identifies a near-optimal configuration with high probability when the budget is adequate and empirically demonstrated that it narrows the performance gap between heuristic and theoretically grounded configurators. Additionally, this thesis presents a modification of the existing MAB method Successive Halving (SHA), enabling it to reuse observations from previous runs with smaller budgets. As a result, it requires only a minimal number of new samples. We demonstrated that the same theoretical guarantees for the returned arm hold as if the algorithm were run from scratch with entirely new samples. Furthermore, we compared these guarantees to those we derived for asynchronous extensions of SHA, which had not been analyzed until now. Finally, we incorporated our algorithm as a subroutine within the HPO framework Hyperband, conducting a theoretical analysis and validating its improved efficiency through experimental studies.
Content
Stats
  • The PDF-Document has been downloaded 4 times.
License/Rightsstatement