論文の概要: Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification

• arxiv url: http://arxiv.org/abs/2412.17753v1
• Date: Mon, 23 Dec 2024 18:06:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-24 16:00:02.994681
• Title: Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification
• Title（参考訳）: 2列ベストアーム同定における最小限の簡易レグレット
• Authors: Masahiro Kato,
• Abstract要約: 簡単な後悔に対して、ネーマン割当の極小極小性を証明した。 局所正規度に局所性制限を課すことなく、最適性が達成できることが示される。
• 参考スコア（独自算出の注目度）: 10.470114319701576
• License:
• Abstract: This study investigates an asymptotically minimax optimal algorithm in the two-armed fixed-budget best-arm identification (BAI) problem. Given two treatment arms, the objective is to identify the arm with the highest expected outcome through an adaptive experiment. We focus on the Neyman allocation, where treatment arms are allocated following the ratio of their outcome standard deviations. Our primary contribution is to prove the minimax optimality of the Neyman allocation for the simple regret, defined as the difference between the expected outcomes of the true best arm and the estimated best arm. Specifically, we first derive a minimax lower bound for the expected simple regret, which characterizes the worst-case performance achievable under the location-shift distributions, including Gaussian distributions. We then show that the simple regret of the Neyman allocation asymptotically matches this lower bound, including the constant term, not just the rate in terms of the sample size, under the worst-case distribution. Notably, our optimality result holds without imposing locality restrictions on the distribution, such as the local asymptotic normality. Furthermore, we demonstrate that the Neyman allocation reduces to the uniform allocation, i.e., the standard randomized controlled trial, under Bernoulli distributions.
• Abstract（参考訳）: 本研究では,両腕固定予算ベストアーム識別(BAI)問題における漸近的に最小限のアルゴリズムについて検討した。 2つの治療用アームが与えられた場合、適応実験により最も期待された結果の腕を特定することが目的である。 我々は、結果標準偏差の比率に従って治療用アームが割り当てられるネイマン割当に焦点を当てる。 我々の主な貢献は、真のベストアームと推定されたベストアームの期待結果との違いとして定義される単純な後悔に対するネイマン割り当ての最小値の最適性を証明することである。 具体的には,まず,ガウス分布を含む位置シフト分布で達成可能な最悪のケース性能を特徴付ける,期待される単純な後悔に対するミニマックス下界を導出する。 すると、ネイマン割り当ての単純な後悔は、最悪の場合の分布の下で、サンプルサイズだけに限らず、定数項を含むこの下界に漸近的に一致することを示す。 特に、我々の最適性は、局所漸近正規性のような分布に局所性制限を課すことなく成り立つ。 さらに、ネーマン割当はベルヌーイ分布の下での一様割当、すなわち標準ランダム化制御試行に還元されることを示す。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances [10.470114319701576]
  本稿では,適応実験における分散を推定し,推定標準偏差の比率でアームを描画する手法を提案する。 以上の結果から,小ギャップ体制を特徴とする最悪のシナリオでは,変動が未知であっても,推定分散を利用する戦略が最適であることが示唆された。
  論文  参考訳（メタデータ） (2023-12-20T03:28:49Z)
• Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget [10.470114319701576]
  本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。 分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。 GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
  論文  参考訳（メタデータ） (2023-10-30T17:52:46Z)
• 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)
• Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits [40.71199236098642]
  無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。 我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-01T18:20:10Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  そこで本研究では,次元に明示的な有界な有限次元設定に最適化を移動させることができる次元削減法を開発した。 この問題を進展させるため、比較的大きな損失関数、すなわちブレグマンの発散によって引き起こされるベイズ的リスクに限定する。
  論文  参考訳（メタデータ） (2022-02-23T16:22:28Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  確率分布が未知な分布の不確実性の下でBQOについて検討する。 標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。 この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
  論文  参考訳（メタデータ） (2020-01-19T12:00:33Z)

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

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