論文の概要: Asymptotically Minimax Optimal Fixed-Budget Best Arm Identification for Expected Simple Regret Minimization

• arxiv url: http://arxiv.org/abs/2302.02988v1
• Date: Mon, 6 Feb 2023 18:27:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-07 15:35:24.556442
• Title: Asymptotically Minimax Optimal Fixed-Budget Best Arm Identification for Expected Simple Regret Minimization
• Title（参考訳）: 簡易レジスト最小化のための漸近的に最小限の固定ベストアーム同定
• Authors: Masahiro Kato, Masaaki Imaizumi, Takuya Ishihara, Toru Kitagawa
• Abstract要約: 単純後悔に対する固定予算ベストアーム識別(BAI)について検討した。 固定分散(位置シフトモデル)を持つ分布に対するminimax criterion を用いた後悔の評価を行う。 その結果, 位置シフトモデルでは, 最適なRS-AIPW戦略は, 異なる確率で治療アームを描画することを示した。
• 参考スコア（独自算出の注目度）: 10.915684166086026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate fixed-budget best arm identification (BAI) for expected simple regret minimization. In each round of an adaptive experiment, a decision maker draws one of multiple treatment arms based on past observations and subsequently observes the outcomes of the chosen arm. After the experiment, the decision maker recommends a treatment arm with the highest projected outcome. We evaluate this decision in terms of the expected simple regret, a difference between the expected outcomes of the best and recommended treatment arms. Due to the inherent uncertainty, we evaluate the regret using the minimax criterion. For distributions with fixed variances (location-shift models), such as Gaussian distributions, we derive asymptotic lower bounds for the worst-case expected simple regret. Then, we show that the Random Sampling (RS)-Augmented Inverse Probability Weighting (AIPW) strategy proposed by Kato et al. (2022) is asymptotically minimax optimal in the sense that the leading factor of its worst-case expected simple regret asymptotically matches our derived worst-case lower bound. Our result indicates that, for location-shift models, the optimal RS-AIPW strategy draws treatment arms with varying probabilities based on their variances. This result contrasts with the results of Bubeck et al. (2011), which shows that drawing each treatment arm with an equal ratio is minimax optimal in a bounded outcome setting.
• Abstract（参考訳）: 単純後悔最小化のための固定予算ベストアーム識別(BAI)について検討した。 適応実験の各ラウンドにおいて、意思決定者は過去の観察に基づいて複数の治療アームの1つを描画し、選択した腕の結果を観察する。 実験の後、意思決定者は最も予測された結果の大きい治療アームを推奨する。 我々は,この決定を,最善腕と推奨腕の期待結果との違いとして,期待された単純後悔の観点から評価した。 また,本質的不確実性から,ミニマックス基準を用いて後悔を評価する。 ガウス分布のような固定分散(位置シフトモデル)を持つ分布に対しては、予想される最悪の場合の単純な後悔に対して漸近下界を導出する。 そして,加藤ら(2022年)が提唱したランダムサンプリング(RS)-拡張逆確率重み付け(AIPW)戦略が,最悪の予測された単純な後悔の要因が,得られた最悪の下限と漸近的に一致するという意味で,漸近的に最小限であることを示す。 その結果, 位置シフトモデルでは, 最適なRS-AIPW戦略は, 異なる確率で治療アームを描画することを示した。 この結果は Bubeck et al. (2011) の結果と対照的であり、これは各処理アームを等比で描画することが有界な結果設定において極小であることを示している。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances [10.470114319701576]
  本稿では,適応実験における分散を推定し,推定標準偏差の比率でアームを描画する手法を提案する。 以上の結果から,小ギャップ体制を特徴とする最悪のシナリオでは,変動が未知であっても,推定分散を利用する戦略が最適であることが示唆された。
  論文  参考訳（メタデータ） (2023-12-20T03:28:49Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Data-driven optimal stopping: A pure exploration analysis [1.0742675209112622]
  最小限の最適性は、単純な後悔に対する下界を一致させて上界結果を完成させることによって検証される。 本研究は, 具体的な探査・探査戦略について, 簡単な後悔から累積後悔への移動について検討した。
  論文  参考訳（メタデータ） (2023-12-10T13:16:01Z)
• Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget [10.470114319701576]
  本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。 分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。 GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
  論文  参考訳（メタデータ） (2023-10-30T17:52:46Z)
• Semiparametric Best Arm Identification with Contextual Information [10.915684166086026]
  バンディット問題において,固定予算と文脈情報を用いたベストアーム識別について検討した。 本研究では,ターゲットアロケーション比とレコメンデーションルールを追跡するランダムサンプリングルールとからなる「コンテキストRS-AIPW戦略」を開発する。 提案手法は,予算が無限に進むと,誤識別確率の上限が半下限と一致するため,最適である。
  論文  参考訳（メタデータ） (2022-09-15T14:38:47Z)
• Minimax Off-Policy Evaluation for Multi-Armed Bandits [58.7013651350436]
  有界報酬を用いたマルチアームバンディットモデルにおけるオフポリシー評価の問題点について検討する。 3つの設定でミニマックスレート・オプティマティックな手順を開発。
  論文  参考訳（メタデータ） (2021-01-19T18:55:29Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)

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

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