論文の概要: 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%の改善を達成できることを示す。
関連論文リスト
- Bi-Criteria Optimization for Combinatorial Bandits: Sublinear Regret and Constraint Violation under Bandit Feedback [27.613888121859393]
マルチアームバンディット(CMAB)におけるビクテリア最適化について検討した。
本稿では,離散二線形オフライン近似アルゴリズムをサブ線形後悔と累積制約違反保証を伴うオンラインアルゴリズムに変換する汎用フレームワークを提案する。
これらのアプリケーションは、オフライン保証をランディットフィードバックの下でオンラインの双基準最適化に適応する際のフレームワークの幅広いユーティリティを強調している。
論文 参考訳（メタデータ） (2025-03-15T22:52:27Z) - A Near-optimal, Scalable and Corruption-tolerant Framework for Stochastic Bandits: From Single-Agent to Multi-Agent and Beyond [2.5217803205496283]
我々はBARBATと呼ばれる新しいフレームワークを提案し、これは$K$の係数を排除し、対数係数に縛られた最適の後悔を実現する。
また,BARBATがグラフバンド,半帯域,バッチバンド,マルチエージェントバンドなど,さまざまな設定に拡張可能であることを示す。
論文 参考訳（メタデータ） (2025-02-11T12:33:33Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Online Clustering of Bandits with Misspecified User Models [42.56440072468658]
コンテキスト線形バンディット(Contextual linear bandit)は、与えられた腕の特徴を学習エージェントが各ラウンドで選択し、長期の累積報酬を最大化するオンライン学習問題である。
バンディットのクラスタリング(CB)と呼ばれる一連の研究は、ユーザの好みに対する協調効果を利用しており、古典的な線形バンディットアルゴリズムよりも大幅に改善されている。
本稿では,不特定ユーザモデル (CBMUM) による盗賊のクラスタリングに関する重要な問題を初めて提示する。
モデル誤特定による不正確なユーザの選好推定と誤クラスタリングを両立できる頑健なCBアルゴリズムRCLUMBとRCLUMBを考案した。
論文 参考訳（メタデータ） (2023-10-04T10:40:50Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳（メタデータ） (2021-11-09T09:00:02Z) - Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual
Linear Bandit [10.604939762790517]
我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。
第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T19:35:38Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。