論文の概要: On Uniformly Optimal Algorithms for Best Arm Identification in Two-Armed
Bandits with Fixed Budget
- arxiv url: http://arxiv.org/abs/2308.12000v2
- Date: Thu, 24 Aug 2023 05:46:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-25 10:38:54.781858
- Title: On Uniformly Optimal Algorithms for Best Arm Identification in Two-Armed
Bandits with Fixed Budget
- Title（参考訳）: 固定予算付き2要素バンドのベストアーム同定のための一様最適アルゴリズムについて
- Authors: Po-An Wang, Kaito Ariu, Alexandre Proutiere
- Abstract要約: ベルヌーイ報奨を伴う二本腕包帯における固定予算によるベストアーム識別の問題について検討した。
意外なことに、各アームを等しくサンプリングするアルゴリズムだけでなく、アルゴリズムも機能しない。
- 参考スコア（独自算出の注目度）: 53.99808986087965
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of best-arm identification with fixed budget in
stochastic two-arm bandits with Bernoulli rewards. We prove that surprisingly,
there is no algorithm that (i) performs as well as the algorithm sampling each
arm equally (this algorithm is referred to as the {\it uniform sampling}
algorithm) on all instances, and that (ii) strictly outperforms this algorithm
on at least one instance. In short, there is no algorithm better than the
uniform sampling algorithm. Towards this result, we introduce the natural class
of {\it consistent} and {\it stable} algorithms, and show that any algorithm
that performs as well as the uniform sampling algorithm on all instances
belongs to this class. The proof is completed by deriving a lower bound on the
error rate satisfied by any consistent and stable algorithm, and by showing
that the uniform sampling algorithm matches this lower bound. Our results
provide a solution to the two open problems presented in \cite{qin2022open}.
- Abstract（参考訳）: ベルヌーイ報奨を伴う確率的二本腕包帯における固定予算によるベストアーム識別の問題について検討した。
驚くべきことに、アルゴリズムは存在しません。
(i)すべてのインスタンスで各アームを等しくサンプリングするアルゴリズム(このアルゴリズムは「一様サンプリング」と呼ばれる)と同様に、そのアルゴリズムを実行する。
(ii) このアルゴリズムを少なくとも1つのインスタンスで厳密に上回る。
要するに、一様サンプリングアルゴリズムより優れたアルゴリズムは存在しない。
この結果に向けて,本アルゴリズムの自然なクラスを導入し,全インスタンスにおける一様サンプリングアルゴリズムと同様に動作する任意のアルゴリズムがこのクラスに属することを示す。
この証明は、任意の一貫した安定なアルゴリズムで満たされた誤差率の低い境界を導出し、一貫したサンプリングアルゴリズムがこの下限と一致することを示す。
この結果は, cite{qin2022open} で示される2つの開問題に対する解を提供する。
関連論文リスト
- Online Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Health [3.534690532561709]
オンライン一様サンプリング(OUS)の新たな課題として,未知の意思決定時間に一様にサンプリング予算を分散させることが目的である。
OUS問題では、アルゴリズムは予算$b$とタイムホライズ$T$を与えられ、敵は[b,T]$の値$tau*を選択し、それをオンラインに公開する。
この問題に対して設計された最初のランダム化アルゴリズムを提示し、その後、学習拡張を組み込むように拡張する。
論文 参考訳（メタデータ） (2024-02-03T02:36:59Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed
Bandit [65.268245109828]
このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。
CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。
提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
論文 参考訳（メタデータ） (2023-10-24T09:47:32Z) - Non-Asymptotic Analysis of a UCB-based Top Two Algorithm [4.18804572788063]
バンディット識別のためのトップ2サンプリングルールは、2つの候補アームの中から次のアームを選択する方法である。
提案するUCBベースのトップ2は,非漸近的保証と競合経験性能を同時に享受する。
論文 参考訳（メタデータ） (2022-10-11T13:21:59Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。
エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。
これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
論文 参考訳（メタデータ） (2020-09-15T17:28:42Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - Corralling Stochastic Bandit Algorithms [54.10645564702416]
相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。
最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
論文 参考訳（メタデータ） (2020-06-16T15:33:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。