論文の概要: Best-Arm Identification in Unimodal Bandits

• arxiv url: http://arxiv.org/abs/2411.01898v1
• Date: Mon, 04 Nov 2024 09:05:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:42:15.522780
• Title: Best-Arm Identification in Unimodal Bandits
• Title（参考訳）: 一様帯域におけるBest-Arm識別
• Authors: Riccardo Poiani, Marc Jourdan, Emilie Kaufmann, Rémy Degenne,
• Abstract要約: 本研究では, 固定信頼度ベストアーム識別問題について検討する。 我々は任意の境界の停止時間で2つ下げる。 腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
• 参考スコア（独自算出の注目度）: 24.001611176749158
• License:
• Abstract: We study the fixed-confidence best-arm identification problem in unimodal bandits, in which the means of the arms increase with the index of the arm up to their maximum, then decrease. We derive two lower bounds on the stopping time of any algorithm. The instance-dependent lower bound suggests that due to the unimodal structure, only three arms contribute to the leading confidence-dependent cost. However, a worst-case lower bound shows that a linear dependence on the number of arms is unavoidable in the confidence-independent cost. We propose modifications of Track-and-Stop and a Top Two algorithm that leverage the unimodal structure. Both versions of Track-and-Stop are asymptotically optimal for one-parameter exponential families. The Top Two algorithm is asymptotically near-optimal for Gaussian distributions and we prove a non-asymptotic guarantee matching the worse-case lower bound. The algorithms can be implemented efficiently and we demonstrate their competitive empirical performance.
• Abstract（参考訳）: 本研究は,腕の指数を最大まで上げて腕の手段を増大させ,その後減少させる一助包帯における固定信頼度ベストアーム識別問題について検討した。 任意のアルゴリズムの停止時間に2つの下限を導出する。 インスタンス依存の下限は、一様構造のため、3つの腕だけが主要な信頼依存コストに寄与していることを示唆している。 しかし、最悪の場合の低い境界は、自信に依存しないコストでは、腕の数に対する線形依存は避けられないことを示している。 単調構造を利用したトラック・アンド・ストップとトップ2のアルゴリズムの修正を提案する。 トラック・アンド・ストップのどちらのバージョンも漸近的に1パラメータ指数族に最適である。 トップ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)
• Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
  中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。 予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。 本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
  論文  参考訳（メタデータ） (2022-10-14T13:09:11Z)
• Optimal Fixed-Budget Best Arm Identification using the Augmented Inverse Probability Estimator in Two-Armed Gaussian Bandits with Unknown Variances [27.122181278234617]
  両腕のガウスバンドにおける固定予算ベストアーム識別問題について検討する。 本稿では,アームドローの目標配置確率を推定し,ランダム化サンプリング(RS)を用いたサンプリングルールを含む戦略を提案する。 提案手法は,サンプルサイズが無限大になり,両腕間のギャップがゼロとなる場合に,不可視的に最適であることを示す。
  論文  参考訳（メタデータ） (2022-01-12T13:38:33Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• On Regret with Multiple Best Arms [12.315392649501101]
  バンディット設定における複数のベスト/ニア最適アームの存在に関する後悔問題について検討する。 我々の目標は、問題の未知の硬さに自動的に適応できるアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2020-06-26T04:01:46Z)
• Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme [16.1694012177079]
  我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。 ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。 このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
  論文  参考訳（メタデータ） (2020-06-11T20:23:43Z)

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

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