論文の概要: Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification
- arxiv url: http://arxiv.org/abs/2405.19317v2
- Date: Mon, 23 Dec 2024 17:43:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:54:54.300449
- 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) に対処する。
関連論文リスト
- Stability and Generalization for Distributed SGDA [70.97400503482353]
分散SGDAのための安定性に基づく一般化分析フレームワークを提案する。
我々は, 安定性の誤差, 一般化ギャップ, 人口リスクの包括的分析を行う。
理論的結果から,一般化ギャップと最適化誤差のトレードオフが明らかになった。
論文 参考訳(メタデータ) (2024-11-14T11:16:32Z) - Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption [11.41663079285674]
両腕の動的部分集合を2つ維持する新しいアンフツーセットポリシーを提案する。
2組のポリシーは、$O(exp(-C N)$Optimity gap for a $N$-armed problem で最適であることを示す。
論文 参考訳(メタデータ) (2024-05-28T07:08:29Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。