論文の概要: Exploration in the Limit

• arxiv url: http://arxiv.org/abs/2601.00084v1
• Date: Wed, 31 Dec 2025 19:27:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-05 15:04:33.248095
• Title: Exploration in the Limit
• Title（参考訳）: 限界の探索
• Authors: Brian M. Cho, Nathan Kallus,
• Abstract要約: 最小サンプルサイズに対して有効なエラー制御を必要とする緩和された定式化を導入する。 これは、弱い信号、高い所望の重要度、実験後の推論要求を含む多くの実世界の設定と整合する。 我々は、腕の指標よりも常に有効な新しい信頼シーケンスを開発し、それを用いて、フレームワークのための新しいBAIアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 37.0278529107694
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In fixed-confidence best arm identification (BAI), the objective is to quickly identify the optimal option while controlling the probability of error below a desired threshold. Despite the plethora of BAI algorithms, existing methods typically fall short in practical settings, as stringent exact error control requires using loose tail inequalities and/or parametric restrictions. To overcome these limitations, we introduce a relaxed formulation that requires valid error control asymptotically with respect to a minimum sample size. This aligns with many real-world settings that often involve weak signals, high desired significance, and post-experiment inference requirements, all of which necessitate long horizons. This allows us to achieve tighter optimality, while better handling flexible nonparametric outcome distributions and fully leveraging individual-level contexts. We develop a novel asymptotic anytime-valid confidence sequences over arm indices, and we use it to design a new BAI algorithm for our asymptotic framework. Our method flexibly incorporates covariates for variance reduction and ensures approximate error control in fully nonparametric settings. Under mild convergence assumptions, we provide asymptotic bounds on the sample complexity and show the worst-case sample complexity of our approach matches the best-case sample complexity of Gaussian BAI under exact error guarantees and known variances. Experiments suggest our approach reduces average sample complexities while maintaining error control.
• Abstract（参考訳）: 固定信頼ベストアーム識別(BAI)では、所望のしきい値以下でエラーの確率を制御しながら、最適な選択肢を迅速に特定することが目的である。 BAIアルゴリズムの多さにもかかわらず、既存の手法は通常、厳密な正確な誤差制御では、ゆるやかな尾の不等式やパラメトリックな制限を用いる必要があるため、実践的な設定では不足する。 これらの制限を克服するために、最小サンプルサイズに対して漸近的に有効なエラー制御を必要とする緩和された定式化を導入する。 これは、弱い信号、高い所望の重要度、実験後の推論要求など、長い地平線を必要とする多くの実世界の設定と一致している。 これにより、フレキシブルな非パラメトリックな結果分布を処理し、個々のレベルのコンテキストを完全に活用しながら、より厳密な最適性を達成することができる。 我々は、腕の指標よりも新しい漸近的随意信頼シーケンスを開発し、それを用いて、我々の漸近的フレームワークのための新しいBAIアルゴリズムを設計する。 本手法は分散低減のための共変分を柔軟に組み込んで,完全非パラメトリック設定における近似誤差制御を保証する。 緩やかな収束仮定の下では、サンプルの複雑さに関する漸近的な境界を提供し、我々のアプローチの最悪のサンプルの複雑さは、正確な誤差保証と既知の分散の下でのガウス的BAIの最良のサンプルの複雑さと一致することを示す。 実験により,提案手法は誤差制御を維持しながら平均サンプルの複雑さを低減することが示唆された。

関連論文リスト

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Fair Best Arm Identification with Fixed Confidence [4.6193503399184275]
  フェアネス制約下でのベストアーム識別(BAI)のための新しいフレームワークを提案する。 本稿では,F-TaSを提案する。 数値計算の結果,F-TaSは試料の複雑さを最小限に抑えつつ,フェアネス違反を抑える効果を示した。
  論文  参考訳（メタデータ） (2024-08-30T14:18:34Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Accelerated and instance-optimal policy evaluation with linear function approximation [17.995515643150657]
  既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。 我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
  論文  参考訳（メタデータ） (2021-12-24T17:21:04Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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