論文の概要: Adaptive Generalized Neyman Allocation: Local Asymptotic Minimax Optimal Best Arm Identification

• arxiv url: http://arxiv.org/abs/2405.19317v1
• Date: Wed, 29 May 2024 17:43:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-30 15:52:40.448540
• Title: Adaptive Generalized Neyman Allocation: Local Asymptotic Minimax Optimal Best Arm Identification
• Title（参考訳）: Adaptive Generalized Neyman Allocation: Local Asymptotic Minimax Optimal Best Arm Identification
• Authors: Masahiro Kato,
• Abstract要約: 本研究は、固定予算ベストアーム識別(BAI)のための局所的ミニマックス最適戦略について検討する。 最強の腕を誤識別する確率の最悪の上限は、小ギャップ体制下での最悪の下限と一致していることを示す。
• 参考スコア（独自算出の注目度）: 10.470114319701576
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This study investigates a local asymptotic minimax optimal strategy for fixed-budget best arm identification (BAI). We propose the Adaptive Generalized Neyman Allocation (AGNA) strategy and show that its worst-case upper bound of 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 strategy corresponds to a generalization of the Neyman allocation for two-armed bandits (Neyman, 1934; Kaufmann et al., 2016) and a refinement of existing strategies such as the ones proposed by Glynn & Juneja (2004) and Shin et al. (2018). Compared to Komiyama et al. (2022), which proposes a minimax rate-optimal strategy, our proposed strategy has a tighter upper bound that exactly matches the lower bound, including the constant terms, by restricting the class of distributions to the class of small-gap distributions. Our result contributes to the longstanding open issue about the existence of asymptotically optimal strategies in fixed-budget BAI, by presenting the local asymptotic minimax optimal strategy.
• Abstract（参考訳）: 本研究は, 固定予算ベストアーム識別(BAI)のための局所的漸近性極小戦略について検討した。 本稿では, 適応一般化ナイマン割当(AGNA)戦略を提案し, その最悪のケース上限が, 最適アームと準最適アームの期待結果の差が小さい小ギャップ体制下での最悪のケース下限と一致していることを示す。 我々の戦略は、2本腕のバンディットに対するネイマン割り当ての一般化(Neyman, 1934; Kaufmann et al , 2016)と、Glynn & Juneja (2004) や Shin et al (2018) による既存の戦略の洗練に対応している。 小山ら (2022) に比較して, 提案手法は, 小ギャップ分布のクラスに分布のクラスを限定することにより, 定数項を含む下限と正確に一致する, より厳密な上限を持つ。 本結果は, 固定予算BAIにおける漸近的最適戦略の存在に関して, 局所的漸近的最小戦略を提示することによって, 長年にわたる課題に寄与する。

関連論文リスト

• When is exponential asymptotic optimality achievable in average-reward restless bandits? [11.41663079285674]
  我々は,$O(exp(-C N))$Optimity gap for a $N$-armed problem。 我々の政策は、上記の容易に検証できる仮定の下で指数的最適性を初めて達成する一方、事前の作業は強いグローバルアトラクタ仮定を必要とするか、あるいは$O(sqrtN)$最適性ギャップしか達成しない。
  論文  参考訳（メタデータ） (2024-05-28T07:08:29Z)
• Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits [11.41663079285674]
  我々のポリシーは、$O(1/sqrtN)$Optimity gap for a $N$-armed problemで最適であることを示す。 当社のアプローチは、インデックスや優先順位ポリシーに重点を置く既存の作業から逸脱しています。
  論文  参考訳（メタデータ） (2024-02-08T14:07:20Z)
• Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances [10.470114319701576]
  本稿では,適応実験における分散を推定し,推定標準偏差の比率でアームを描画する手法を提案する。 以上の結果から,小ギャップ体制を特徴とする最悪のシナリオでは,変動が未知であっても,推定分散を利用する戦略が最適であることが示唆された。
  論文  参考訳（メタデータ） (2023-12-20T03:28:49Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Efficient Stochastic Approximation of Minimax Excess Risk Optimization [36.68685001551774]
  我々はMEROを直接対象とする効率的な近似手法を開発した。 最小リスクの推定誤差に起因するバイアスが制御下にあることを示す。 また,各分布から抽出したサンプルの量が異なる場合の現実的シナリオについても検討し,分布依存収束率を導出する手法を提案する。
  論文  参考訳（メタデータ） (2023-05-31T02:21:11Z)
• Sharpness-Aware Gradient Matching for Domain Generalization [84.14789746460197]
  ドメイン一般化(DG)の目標は、ソースドメインから他の見えないドメインに学習したモデルの一般化能力を強化することである。 最近開発されたシャープネス・アウェア最小化(SAM)法は、損失景観のシャープネス測定を最小化することで、この目標を達成することを目的としている。 モデルが小さな損失を伴って平らな最小値に収束することを保証するための2つの条件と,シャープネス・アウェア・グラディエントマッチング(SAGM)というアルゴリズムを提案する。 提案手法は5つのDGベンチマークにおける最先端の手法よりも一貫して優れている。
  論文  参考訳（メタデータ） (2023-03-18T07:25:12Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  そこで本研究では,次元に明示的な有界な有限次元設定に最適化を移動させることができる次元削減法を開発した。 この問題を進展させるため、比較的大きな損失関数、すなわちブレグマンの発散によって引き起こされるベイズ的リスクに限定する。
  論文  参考訳（メタデータ） (2022-02-23T16:22:28Z)
• 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)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• On the Optimality of Randomization in Experimental Design: How to Randomize for Minimax Variance and Design-Based Inference [58.442274475425144]
  条件平均値が与えられたセットで異なる場合の2本腕制御実験のミニマックス最適設計について検討する。 最適設計はカラスの混合戦略最適設計(MSOD)であることが示されている。 そこで,このような制約を受けるすべての設計において,最小値が最適である推論制約MSODを提案する。
  論文  参考訳（メタデータ） (2020-05-06T21:43:50Z)

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

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