論文の概要: Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget

• arxiv url: http://arxiv.org/abs/2310.19788v3
• Date: Mon, 11 Mar 2024 00:56:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-13 15:27:23.440618
• Title: Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget
• Title（参考訳）: 固定予算付き最適多関節型ガウスベストアーム同定法
• Authors: Masahiro Kato
• Abstract要約: 本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。 分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。 GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
• 参考スコア（独自算出の注目度）: 10.470114319701576
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This study investigates the experimental design problem for identifying the arm with the highest expected outcome, referred to as best arm identification (BAI). In our experiments, the number of treatment-allocation rounds is fixed. During each round, a decision-maker allocates an arm and observes a corresponding outcome, which follows a Gaussian distribution with variances that can differ among the arms. At the end of the experiment, the decision-maker recommends one of the arms as an estimate of the best arm. To design an experiment, we first discuss lower bounds for the probability of misidentification. Our analysis highlights that the available information on the outcome distribution, such as means (expected outcomes), variances, and the choice of the best arm, significantly influences the lower bounds. Because available information is limited in actual experiments, we develop a lower bound that is valid under the unknown means and the unknown choice of the best arm, which are referred to as the worst-case lower bound. We demonstrate that the worst-case lower bound depends solely on the variances of the outcomes. Then, under the assumption that the variances are known, we propose the Generalized-Neyman-Allocation (GNA)-empirical-best-arm (EBA) strategy, an extension of the Neyman allocation proposed by Neyman (1934). We show that the GNA-EBA strategy is asymptotically optimal in the sense that its probability of misidentification aligns with the lower bounds as the sample size increases infinitely and the differences between the expected outcomes of the best and other suboptimal arms converge to the same values across arms. We refer to such strategies as asymptotically worst-case optimal.
• Abstract（参考訳）: 本研究は, 最良腕識別 (best arm identification, bai) と呼ばれる最も期待された結果を持つ腕を識別するための実験設計問題を検討する。 実験では,治療アロケーションラウンドの数を固定した。 各ラウンドの間、意思決定者は腕を割り当て、対応する結果を観察し、腕間で異なるばらつきを持つガウス分布に従う。 実験の最後には、意思決定者は腕の1つを最適な腕の見積もりとして推奨する。 実験を設計するために,まず,誤認確率の下限について検討する。 分析の結果,平均値(予測結果),ばらつき,ベストアームの選択などの結果分布に関する情報が,下限に大きく影響していることが明らかになった。 利用可能な情報は実際の実験では限られているため、未知の手段と最善のアームの未知の選択の下で有効となる下限を開発し、最悪の下限と呼ぶ。 最悪の場合の低い境界は結果のばらつきにのみ依存することを示す。 次に,分散が知られていると仮定して,ニーマン(1934)が提案したニーマン割当の延長であるgna-empirical-best-arm(eba)戦略を提案する。 gna-eba戦略は,標本サイズが無限に増大するにつれて誤同定の確率が下界と一致し,最善と他の準最適アームの期待結果の差が腕間で同じ値に収束するという意味で漸近的に最適であることを示す。 このような戦略を漸近的に最悪の場合最適と呼ぶ。

関連論文リスト

• 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)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。 各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。 その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
  論文  参考訳（メタデータ） (2023-10-20T10:04:05Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。 本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。 本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
  論文  参考訳（メタデータ） (2023-08-29T18:18:21Z)
• Covariance Adaptive Best Arm Identification [0.0]
  ゴールは、腕のプル数を最小化しながら、最低でも1-$delta$の確率で腕を最も平均的な報酬で識別することである。 武器を頼りにでき、報酬を同時にサンプリングできる、より柔軟なシナリオを提案する。 この枠組みは、患者と薬物の類似性から根底にある相関関係が示唆される臨床試験など、様々な応用に関係している。
  論文  参考訳（メタデータ） (2023-06-05T06:57:09Z)
• Best Arm Identification in Bandits with Limited Precision Sampling [14.011731120150124]
  学習者が腕選択の精度に限界がある多腕バンディット問題の変種における最適な腕識別について検討する。 非特異な最適アロケーションを処理するために,修正されたトラッキングベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-10T12:07:48Z)
• Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds [10.915684166086026]
  単純後悔を最小化するための固定予算ベストアーム識別(BAI)の問題点について検討する。 この決定は,最善腕と推奨腕の期待結果との違いである,期待された単純後悔に基づいて評価する。 我々は,HIR推定器(ヒラノら,2003年)を用いて最適な腕を推奨する2段階(TS-Hirano-Imbens-Ridder-HIR)戦略を提案する。
  論文  参考訳（メタデータ） (2023-02-06T18:27:11Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)
• 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)
• Towards Minimax Optimal Best Arm Identification in Linear Bandits [95.22854522340938]
  固定予算設定における線形包帯における最適な腕識別の問題について検討する。 G-最適設計の特性を活用し、アーム割り当て規則に組み込むことにより、パラメータフリーなアルゴリズムを設計する。 OD-LinBAIの故障確率に関する理論的解析を行った。
  論文  参考訳（メタデータ） (2021-05-27T09:19:10Z)

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

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