Hierarchical Adversarial Bandits for Online Configuration Optimization

2025/05/25 by Gil Shabat, Avin, Chen, Lotker, Zvi +8
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Multiagent Systems (cs.MA) #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2505.19061

openalex publication_date 2025/05/25 · openalex created_date 2025/09/29 · openalex updated_date 2026/08/01

Abstract

Motivated by Online Configuration Optimization in large, dynamic parameter spaces, this work studies the nonstochastic multi-armed bandit (MAB) problem in metric action spaces with oblivious Lipschitz adversaries. We propose ABoB (Adversarial Bandit over Bandits), a hierarchical framework that decomposes the configuration space into clusters to accelerate learning and adapt to changing environments. We evaluate ABoB using standard algorithms such as EXP3 and Tsallis-INF on a real-world production storage system, demonstrating significant performance gains of up to 50% compared to state-of-the-art "flat" bandit algorithms. Extensive simulations further confirm that ABoB effectively exploits metric structures, achieving up to 91% improvement in adversarial metric scenarios while significantly reducing computational running time. Theoretical analysis grounds this empirical success: we prove that ABoB maintains a worst-case "safety net" bound of O(√(kT)), matching traditional methods, where T is the number of rounds and k is the number of arms, while capable of accelerating learning to O(k^1/4√(T)) under favorable Lipschitz conditions. This combination of operational efficiency and theoretical soundness makes ABoB a practical solution for automated system tuning.

Citations

• Introduction to Multi-Armed Bandits
• A Survey on Practical Applications of Multi-Armed and Contextual Bandits
• An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
• Corralling a Band of Bandit Algorithms
• Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
• Bandits and Experts in Metric Spaces
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• X-Armed Bandits
• Multi-Armed Bandits in Metric Spaces
• The Nonstochastic Multiarmed Bandit Problem

Related

• A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond
• An Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures
• Federated Linear Bandits with Finite Adversarial Actions
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Batched Bandits with Crowd Externalities