arXiv:2505.19061cs.LGcs.MA2025-05KDD

通过分层结构加速大规模配置优化,显著提升系统调优效率。

Hierarchical Adversarial Bandits for Online Configuration Optimization

  • 将参数空间分簇,用分层对抗机制实现快速学习
  • 实测性能最高提升50%,恶劣环境下改善达91%
  • 兼顾理论保障与实际效率,适合动态系统自动调参

针对大规模动态参数空间中的在线配置优化问题,本文研究度量空间中非随机多臂老虎机(MAB)在固定利普希茨对手下的情形。提出ABoB(Adversarial Bandit over Bandits)分层框架,将配置空间分解为簇以加速学习并适应环境变化。在真实生产级存储系统上使用EXP3和Tsallis-INF等标准算法评估,相较当前主流“平坦”带宽算法性能提升高达50%。大量仿真进一步验证:ABoB有效利用度量结构,在对抗性度量场景下实现最高91%的改进,并显著降低计算耗时。理论分析表明:尽管最坏情况仍保持$O(\sqrt{kT})$的安全边界($T$为轮次数,$k$为臂数),但在有利利普希茨条件下可加速至$O(k^{1/4}\sqrt{T})$。该组合使ABoB成为自动化系统调优的实用方案。

原文摘要 · Abstract (English)

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(\sqrt{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}\sqrt{T})$ under favorable Lipschitz conditions. This combination of operational efficiency and theoretical soundness makes ABoB a practical solution for automated system tuning.

在线优化多臂老虎机系统调参分层结构

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。