論文の概要: Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leiblier Maillard Sampling
- arxiv url: http://arxiv.org/abs/2502.14379v1
- Date: Thu, 20 Feb 2025 09:12:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-21 14:26:48.888866
- Title: Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leiblier Maillard Sampling
- Title(参考訳): Exponential-Kullback Leiblier Maillard Smpling を用いたマルチアームバンディットの適応性と最適性
- Authors: Hao Qin, Kwang-Sung Jun, Chicheng Zhang,
- Abstract要約: 本研究では, 1-Exponential Distribution (OPED) ファミリーに属する報酬分布を持つマルチアーメッド・バンディット(MAB)の問題について検討する。
本稿では,複数の最適性基準を同時に達成できるアルゴリズム,Exponential Kullback-Leibler Maillard Sampling(expklms)を設計する。
- 参考スコア(独自算出の注目度): 24.487235945761913
- License:
- Abstract: We study the problem of Multi-Armed Bandits (MAB) with reward distributions belonging to a One-Parameter Exponential Distribution (OPED) family. In the literature, several criteria have been proposed to evaluate the performance of such algorithms, including Asymptotic Optimality (A.O.), Minimax Optimality (M.O.), Sub-UCB, and variance-adaptive worst-case regret bound. Thompson Sampling (TS)-based and Upper Confidence Bound (UCB)-based algorithms have been employed to achieve some of these criteria. However, none of these algorithms simultaneously satisfy all the aforementioned criteria. In this paper, we design an algorithm, Exponential Kullback-Leibler Maillard Sampling (abbrev. \expklms), that can achieve multiple optimality criteria simultaneously, including A.O., M.O. with a logarithmic factor, Sub-UCB, and variance-adaptive worst-case regret bound.
- Abstract(参考訳): 1パラメータ指数分布(OPED)ファミリーに属する報酬分布を持つマルチアーメッド帯域(MAB)の問題について検討する。
論文の中では、漸近的最適性(A.O.)、ミニマックス最適性(M.O.)、サブUCB、分散適応型最悪の後悔境界など、そのようなアルゴリズムの性能を評価するためのいくつかの基準が提案されている。
Thompson Sampling (TS) とUpper Confidence Bound (UCB) をベースとしたアルゴリズムは、これらの基準のいくつかを達成するために使われている。
しかし、これらのアルゴリズムは上記の全ての基準を同時に満たさない。
本稿では,Exponential Kullback-Leibler Maillard Sampling (abbrev) というアルゴリズムを設計する。
A.O.、M.O.、対数係数、サブUCB、分散適応型最悪の後悔境界を含む複数の最適基準を同時に達成できる。
関連論文リスト
- Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳(メタデータ) (2025-02-19T06:37:37Z) - Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳(メタデータ) (2024-05-24T04:11:58Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine
Constraints [21.38692458445459]
ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。
単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
論文 参考訳(メタデータ) (2023-10-02T08:07:36Z) - A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [14.33758865948252]
我々は2つの有名なバンディットアルゴリズム、Minimum Empirical Divergence (MED)とThompson Sampling (TS)を再検討する。
MEDがこれらのモデルすべてに最適であることを示すとともに、最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。
論文 参考訳(メタデータ) (2023-03-10T16:43:48Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳(メタデータ) (2022-06-07T18:08:21Z) - From Optimality to Robustness: Dirichlet Sampling Strategies in
Stochastic Bandits [0.0]
本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。
この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
論文 参考訳(メタデータ) (2021-11-18T14:34:21Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。