論文の概要: On Uniformly Optimal Algorithms for Best Arm Identification in Two-Armed
Bandits with Fixed Budget
- arxiv url: http://arxiv.org/abs/2308.12000v3
- Date: Mon, 4 Sep 2023 08:24:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-07 02:54:32.807652
- 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 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 first 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 then proceeds 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つのインスタンスで厳密に上回る。
要するに、一様サンプリングアルゴリズムより優れたアルゴリズムは存在しない。
この結果に向けて、まず自然クラスである it consistent} と {\it stable} アルゴリズムを導入し、全てのインスタンスにおける一様サンプリングアルゴリズムと同様に動作する任意のアルゴリズムがこのクラスに属することを示す。
証明は、任意の一貫した安定なアルゴリズムで満たされた誤差率の低い境界を導出し、均一サンプリングアルゴリズムがこの下限に一致することを示す。
この結果は, 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。