論文の概要: 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つの開問題に対する解を提供する。
関連論文リスト
- Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
この仕事の動機は、再現可能な機械学習の需要の増加にある。
特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
論文 参考訳(メタデータ) (2024-02-12T03:31:34Z) - Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed
Bandit [65.268245109828]
このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。
CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。
提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
論文 参考訳(メタデータ) (2023-10-24T09:47:32Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳(メタデータ) (2023-01-11T09:12:28Z) - Critic Algorithms using Cooperative Networks [0.0]
マルコフ決定過程における政策評価のためのアルゴリズムを提案する。
このアルゴリズムは、射影ベルマン誤差を追跡し、真の勾配に基づくアルゴリズムとして実装されている。
論文 参考訳(メタデータ) (2022-01-19T19:47:18Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Combining K-means type algorithms with Hill Climbing for Joint
Stratification and Sample Allocation Designs [0.0]
これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。
それぞれのソリューションのコストを評価するのに 費用がかかります
上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
論文 参考訳(メタデータ) (2021-08-18T08:41:58Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - Corralling Stochastic Bandit Algorithms [54.10645564702416]
相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。
最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
論文 参考訳(メタデータ) (2020-06-16T15:33:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。