論文の概要: 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 15:57:53.074343
• Title: Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identification
• Title（参考訳）: 局所最小値最適ベストアーム同定のための一般化ネマン割当法
• Authors: Masahiro Kato,
• Abstract要約: 本研究では,固定予算ベストアーム識別(BAI)のための局所最小値アルゴリズムについて検討する。 一般化ネマン割当法 (GNA) を提案し, 最良腕の誤同定確率の最悪の上限が, 小ギャップ法の下での最悪の下限と一致することを示した。 我々の下限と上限は厳密であり、小ギャップ状態内の定数項と正確に一致する。
• 参考スコア（独自算出の注目度）: 10.470114319701576
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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)
• Stability and Generalization for Distributed SGDA [70.97400503482353]
  分散SGDAのための安定性に基づく一般化分析フレームワークを提案する。 我々は, 安定性の誤差, 一般化ギャップ, 人口リスクの包括的分析を行う。 理論的結果から,一般化ギャップと最適化誤差のトレードオフが明らかになった。
  論文  参考訳（メタデータ） (2024-11-14T11:16:32Z)
• Best-Arm Identification in Unimodal Bandits [24.001611176749158]
  本研究では, 固定信頼度ベストアーム識別問題について検討する。 我々は任意の境界の停止時間で2つ下げる。 腕の数に対する線形依存は、信頼性に依存しないコストでは避けられないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T09:05:11Z)
• 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)
• 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)
• 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)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)
• 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)
• 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)

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

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