論文の概要: Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification

• arxiv url: http://arxiv.org/abs/2405.19317v4
• Date: Sun, 02 Feb 2025 18:50:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-04 16:07:56.975559
• Title: Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification
• Title（参考訳）: 局所最小値最適ベストアーム同定のための一般化ネマン割当法
• Authors: Masahiro Kato,
• Abstract要約: 本研究では,固定予算ベストアーム識別(BAI)のための局所最小値アルゴリズムについて検討する。 一般化ネマン割当法 (GNA) を提案し, 最良腕の誤同定確率の最悪の上限が, 小ギャップ法の下での最悪の下限と一致することを示した。 我々の下限と上限は厳密であり、小ギャップ状態内の定数項と正確に一致する。
• 参考スコア（独自算出の注目度）: 10.470114319701576
• License:
• Abstract: This study investigates an asymptotically locally minimax optimal algorithm for fixed-budget best-arm identification (BAI). We propose the Generalized Neyman Allocation (GNA) algorithm and demonstrate that its worst-case upper bound on the probability of misidentifying the best arm aligns with the worst-case lower bound under the small-gap regime, where the gap between the expected outcomes of the best and suboptimal arms is small. Our lower and upper bounds are tight, matching exactly including constant terms within the small-gap regime. The GNA algorithm generalizes the Neyman allocation for two-armed bandits (Neyman, 1934; Kaufmann et al., 2016) and refines existing BAI algorithms, such as those proposed by Glynn & Juneja (2004). By proposing an asymptotically minimax optimal algorithm, we address the longstanding open issue in BAI (Kaufmann, 2020) and treatment choice (Kasy & Sautmann, 202) by restricting a class of distributions to the small-gap regimes.
• Abstract（参考訳）: 本研究では,固定予算ベストアーム識別(BAI)のための漸近的に局所的に最小限のアルゴリズムについて検討する。 一般化ナイマン割当法 (GNA) を提案し, 最適アームと最適アームの期待値との差が小さい場合, 最適アームを誤識別する確率の最悪の上限が, 最小ケース下限と最小ケース下限との整合性を示す。 我々の下限と上限は厳密であり、小ギャップ状態内の定数項と正確に一致する。 GNAアルゴリズムは、2本腕のバンディットに対するネイマン割り当てを一般化し(Neyman, 1934; Kaufmann et al , 2016)、2004年にGlynn & Junejaによって提案されたような既存のBAIアルゴリズムを洗練する。 漸近的に最小限のアルゴリズムを提案することにより、BAI (Kaufmann, 2020) における長年のオープン問題と、小ギャップ体制への分布のクラスを制限することにより、治療選択 (Kasy & Sautmann, 202) に対処する。

関連論文リスト

• Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification [10.470114319701576]
  簡単な後悔に対して、ネーマン割当の極小極小性を証明した。 局所正規度に局所性制限を課すことなく、最適性が達成できることが示される。
  論文  参考訳（メタデータ） (2024-12-23T18:06:20Z)
• Best-Arm Identification in Unimodal Bandits [24.001611176749158]
  本研究では, 固定信頼度ベストアーム識別問題について検討する。 我々は任意の境界の停止時間で2つ下げる。 腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T09:05:11Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances [10.470114319701576]
  本稿では,適応実験における分散を推定し,推定標準偏差の比率でアームを描画する手法を提案する。 以上の結果から,小ギャップ体制を特徴とする最悪のシナリオでは,変動が未知であっても,推定分散を利用する戦略が最適であることが示唆された。
  論文  参考訳（メタデータ） (2023-12-20T03:28:49Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Riemannian Langevin Algorithm for Solving Semidefinite Programs [9.340611077939828]
  球面の積多様体上での非最適化とサンプリングのためのランゲヴィンに基づくアルゴリズムを提案する。 提案アルゴリズムは,高い確率で$epsilonの精度が得られることを示す。
  論文  参考訳（メタデータ） (2020-10-21T17:51:08Z)
• 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)

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

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