論文の概要: Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds

• arxiv url: http://arxiv.org/abs/2302.02988v2
• Date: Wed, 12 Jul 2023 16:06:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-13 19:46:48.183116
• Title: Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds
• Title（参考訳）: 可変境界を持つ漸近的最適固定ベストアーム同定
• Authors: Masahiro Kato, Masaaki Imaizumi, Takuya Ishihara, Toru Kitagawa
• Abstract要約: 単純後悔を最小化するための固定予算ベストアーム識別(BAI)の問題点について検討する。 この決定は,最善腕と推奨腕の期待結果との違いである,期待された単純後悔に基づいて評価する。 我々は,HIR推定器(ヒラノら,2003年)を用いて最適な腕を推奨する2段階(TS-Hirano-Imbens-Ridder-HIR)戦略を提案する。
• 参考スコア（独自算出の注目度）: 10.915684166086026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the problem of fixed-budget best arm identification (BAI) for minimizing expected simple regret. In an adaptive experiment, a decision maker draws one of multiple treatment arms based on past observations and observes the outcome of the drawn arm. After the experiment, the decision maker recommends the treatment arm with the highest expected outcome. We evaluate the decision based on the expected simple regret, which is the difference between the expected outcomes of the best arm and the recommended arm. Due to inherent uncertainty, we evaluate the regret using the minimax criterion. First, we derive asymptotic lower bounds for the worst-case expected simple regret, which are characterized by the variances of potential outcomes (leading factor). Based on the lower bounds, we propose the Two-Stage (TS)-Hirano-Imbens-Ridder (HIR) strategy, which utilizes the HIR estimator (Hirano et al., 2003) in recommending the best arm. Our theoretical analysis shows that the TS-HIR strategy is asymptotically minimax optimal, meaning that the leading factor of its worst-case expected simple regret matches our derived worst-case lower bound. Additionally, we consider extensions of our method, such as the asymptotic optimality for the probability of misidentification. Finally, we validate the proposed method's effectiveness through simulations.
• Abstract（参考訳）: 単純後悔を最小化するための固定予算ベストアーム識別(BAI)の問題について検討する。 適応的な実験において、意思決定者は過去の観察に基づいて複数の治療アームの1つを描画し、描画された腕の結果を観察する。 実験後、意思決定者は最も期待された結果で治療腕を推奨する。 この決定は,最善腕と推奨腕の期待結果との違いである,期待された単純後悔に基づいて評価する。 内因性不確実性のため,ミニマックス基準を用いて後悔を評価する。 まず, 潜在的な結果のばらつき(リード要因)を特徴とする, 最悪の場合の単純な後悔に対する漸近的下限を導出する。 下界に基づいて,HIR推定器(ヒラノら,2003年)を用いて最適な腕を推奨する2段式(TS)-ヒラノ・イブンゼンス・ライダー(HIR)戦略を提案する。 我々の理論的分析は、TS-HIR戦略は漸近的に最小限の最適化であり、最悪の場合予測される単純な後悔の要因は、得られた最悪のケースの低い境界と一致していることを示している。 さらに,本手法の拡張,例えば誤認の確率に対する漸近的最適性について検討する。 最後に,提案手法の有効性をシミュレーションにより検証する。

関連論文リスト

• 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)
• Rate-optimal Bayesian Simple Regret in Best Arm Identification [11.389780431092914]
  マルチアームバンディット問題における腕の識別について検討する。 本稿では,その先行項を定数係数まで下界にマッチングする,単純で容易に計算できるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-18T18:59:35Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。 我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。 我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
  論文  参考訳（メタデータ） (2021-07-05T21:05:11Z)
• 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)

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

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