Fugu-MT 論文翻訳(概要): Adversarial Bandit over Bandits: Hierarchical Bandits for Online Configuration Management

論文の概要: Adversarial Bandit over Bandits: Hierarchical Bandits for Online Configuration Management

arxiv url: http://arxiv.org/abs/2505.19061v1
Date: Sun, 25 May 2025 09:30:47 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-27 16:58:42.877104
Title: Adversarial Bandit over Bandits: Hierarchical Bandits for Online Configuration Management
Title（参考訳）: 帯域をめぐる対立的帯域幅:オンライン構成管理のための階層的帯域幅
Authors: Chen Avin, Zvi Lotker, Shie Mannor, Gil Shabat, Hanan Shteingart, Roey Yadgar,
Abstract要約: 本研究は, 難解なリプシッツ逆数を持つ計量作用空間における非確率的マルチアーム・バンディット(MAB)問題を研究する。我々は,現在最先端のフラットなアルゴリズムを利用できる階層型Adversarial Bandit over BanditsアルゴリズムであるABoBを提案する。
参考スコア（独自算出の注目度）: 37.696481970844054
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Motivated by dynamic parameter optimization in finite, but large action (configurations) spaces, this work studies the nonstochastic multi-armed bandit (MAB) problem in metric action spaces with oblivious Lipschitz adversaries. We propose ABoB, a hierarchical Adversarial Bandit over Bandits algorithm that can use state-of-the-art existing "flat" algorithms, but additionally clusters similar configurations to exploit local structures and adapt to changing environments. We prove that in the worst-case scenario, such clustering approach cannot hurt too much and ABoB guarantees a standard worst-case regret bound of $O\left(k^{\frac{1}{2}}T^{\frac{1}{2}}\right)$, where $T$ is the number of rounds and $k$ is the number of arms, matching the traditional flat approach. However, under favorable conditions related to the algorithm properties, clusters properties, and certain Lipschitz conditions, the regret bound can be improved to $O\left(k^{\frac{1}{4}}T^{\frac{1}{2}}\right)$. Simulations and experiments on a real storage system demonstrate that ABoB, using standard algorithms like EXP3 and Tsallis-INF, achieves lower regret and faster convergence than the flat method, up to 50% improvement in known previous setups, nonstochastic and stochastic, as well as in our settings.
Abstract（参考訳）: 有限だが大きな作用(構成)空間における動的パラメータ最適化によって動機づけられたこの研究は、不明瞭なリプシッツ逆数を持つ計量作用空間における非確率的多重武装バンディット(MAB)問題を研究する。 ABoBは、最先端の「フラット」アルゴリズムを利用できる階層的逆帯域バンドアルゴリズムであり、また、類似した構成をクラスタ化して、局所構造を利用して環境の変化に適応する。最悪のシナリオでは、そのようなクラスタリングアプローチが大きすぎることはなく、ABoBは、$O\left(k^{\frac{1}{2}}T^{\frac{1}{2}}\right)$で、$T$はラウンドの数、$k$はアームの数であり、従来のフラットなアプローチと一致することを保証している。しかし、アルゴリズムの性質、クラスタ特性、特定のリプシッツ条件に関連する好ましい条件の下では、後悔の限界は$O\left(k^{\frac{1}{4}}T^{\frac{1}{2}}\right)$に改善することができる。実記憶システムにおけるシミュレーションと実験により,EXP3やTsallis-INFのような標準アルゴリズムを用いたABoBは,既知の既知セットアップ,非確率的,確率的,および我々の設定において最大50%の改善を達成できることを示す。

論文の概要: Adversarial Bandit over Bandits: Hierarchical Bandits for Online Configuration Management

関連論文リスト