論文の概要: On the Existence of a Complexity in Fixed Budget Bandit Identification

• arxiv url: http://arxiv.org/abs/2303.09468v2
• Date: Fri, 30 Jun 2023 09:42:18 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-03 15:09:56.181526
• Title: On the Existence of a Complexity in Fixed Budget Bandit Identification
• Title（参考訳）: 固定予算バンディット同定における複雑性の存在について
• Authors: R\'emy Degenne
• Abstract要約: 固定予算帯域識別では、アルゴリズムは複数の分布から与えられた最終時点までのサンプルを逐次観察する。 我々は,ベルヌーイの腕を2つの腕で識別するなど,いくつかの固定予算識別タスクにおいて,そのような複雑さは存在しないことを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In fixed budget bandit identification, an algorithm sequentially observes samples from several distributions up to a given final time. It then answers a query about the set of distributions. A good algorithm will have a small probability of error. While that probability decreases exponentially with the final time, the best attainable rate is not known precisely for most identification tasks. We show that if a fixed budget task admits a complexity, defined as a lower bound on the probability of error which is attained by the same algorithm on all bandit problems, then that complexity is determined by the best non-adaptive sampling procedure for that problem. We show that there is no such complexity for several fixed budget identification tasks including Bernoulli best arm identification with two arms: there is no single algorithm that attains everywhere the best possible rate.
• Abstract（参考訳）: 固定予算帯域識別では、アルゴリズムは複数の分布から与えられた最終時点までのサンプルを逐次観察する。 その後、分布の集合に関する問い合わせに答える。 良いアルゴリズムは誤りの確率が小さいだろう。 この確率は最終時刻に指数関数的に減少するが、ほとんどの識別タスクにおいて最高の到達可能率は正確には分かっていない。 固定予算タスクが、すべてのバンディット問題において同じアルゴリズムによって達成される誤差の確率の下限として定義される複雑性を認めると、その問題に対する最適な非適応サンプリング手順によって複雑性が決定されることを示す。 2本の腕を持つベルヌーイのベストアーム識別を含むいくつかの固定予算識別タスクには、そのような複雑さがないことを示す: 可能な最良率を至る所で達成する単一のアルゴリズムは存在しない。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• Best arm identification in rare events [0.43012765978447565]
  このフレームワークのキーとなる応用は、オンライン広告において、広告のクリックレートが1パーセントのごく一部であり、売上への最終的な転換率は高い利益であるが、再びクリックレートのごく一部になるかもしれない。 近年,BAI問題に対するアルゴリズムが開発され,正確なアーム選択に関する統計的保証を提供しながら,サンプルの複雑さを最小化している。 両腕の報酬過程は複合ポアソン法によりよく近似され、より高速なアルゴリズムに到達し、サンプルの複雑さはわずかに増大する。
  論文  参考訳（メタデータ） (2023-03-14T04:51:24Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• Choosing Answers in $\varepsilon$-Best-Answer Identification for Linear Bandits [0.8122270502556374]
  純粋探索問題では、情報を逐次収集して環境問題に答える。 平均値の高い解を選択すると、期待されるサンプルの複雑さの観点からアルゴリズムが最適に到達できないことを示す。 導出線形帯域における$varepsilon$-best-answer識別にベストアーム識別アルゴリズムを適用するための簡単な手法を開発した。
  論文  参考訳（メタデータ） (2022-06-09T12:27:51Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。 ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。 このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
  論文  参考訳（メタデータ） (2020-06-11T20:23:43Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。