論文の概要: 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における漸近的最適戦略の存在に関して, 局所的漸近的最小戦略を提示することによって, 長年にわたる課題に寄与する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。