論文の概要: Expected Sample Complexity in Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2610.09929v1
• Date: Wed, 07 Oct 2026 12:16:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:22.899822
• Title: Expected Sample Complexity in Multi-Armed Bandits
• Title（参考訳）: マルチアーマッドバンドにおける期待されるサンプル複雑度
• Abstract要約: 我々は,多武装バンディット問題のサンプル複雑性について検討し,ほぼ正当性(ACE)と呼ばれる新しいフレームワークを用いて解析する。 ACEは、他のフレームワークで見られる高い確率保証とは対照的に、最適に期待される報酬にほぼ確実に収束することを示す。
• 参考スコア（独自算出の注目度）: 12.167870120188232
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sample complexity is a widely used metric in sequential decision-making problems, defined as the number of suboptimal decisions during the interaction between the agent and an environment. We study the sample complexity of stochastic multi-armed bandit problems and introduce the expected sample complexity performance measure, analyzing it in a novel framework called approximately correct in expectation (ACE). We show that ACE guarantees imply almost sure convergence to the optimal expected reward, in contrast to high-probability guarantees found in other frameworks, and also show how to convert ACE guarantees into explicit expected regret bounds. We further show that, in contrast to existing measures, deterministic algorithms cannot obtain favorable ACE bounds, and analyze stochastic algorithms in two settings: when the allowed suboptimality level $ε$ is known to the algorithm and when it is unknown. In the former, we devise an explore-then-$ε$-greedy algorithm, and in the latter, we analyze the expected sample complexity of Thompson sampling. Finally, we establish nearly matching lower bounds for both settings, showing that the algorithms are tight in $ε$ and proving a performance separation between the two regimes.
• Abstract（参考訳）: サンプル複雑性はシーケンシャルな意思決定問題において広く用いられる指標であり、エージェントと環境の間の相互作用における最適下決定の回数として定義される。 本稿では,確率的マルチアームバンディット問題におけるサンプル複雑性について検討し,ほぼ正しい予測(ACE)と呼ばれる新しいフレームワークを用いて解析し,期待されるサンプル複雑性性能指標を導入する。 ACE保証は他のフレームワークで見られる高い確率保証とは対照的に、ACE保証が最適に期待される報酬にほぼ確実に収束することを示し、ACE保証を明示的に期待された後悔の限界に変換する方法を示す。 さらに、既存の測度とは対照的に、決定論的アルゴリズムは好ましいACE境界を得ることができず、確率的アルゴリズムを2つの設定で解析する。 前者では、探索-then-$ε$-greedyアルゴリズムを考案し、後者では、トンプソンサンプリングの期待されるサンプル複雑性を分析する。 最後に、両方の設定に対してほぼ一致した下限を確立し、アルゴリズムがε$で厳密であり、2つの条件間の性能分離を証明していることを示す。

関連論文リスト

• EVaR-Optimal Arm Identification in Bandits [7.340828059560291]
  The fixed-confidence best arm identification problem in the multiarmed bandit (MAB) framework under the Entropic Value-at-Risk criterion。
  論文  参考訳（メタデータ） (2025-10-06T11:49:56Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• GBOSE: Generalized Bandit Orthogonalized Semiparametric Estimation [3.441021278275805]
  そこで本稿では,半パラメトリック報酬モデルを用いた新たなアルゴリズムを提案する。 我々の研究は、同じアクションフィルタリング法に基づいて構築されたアルゴリズムを提案することによって、同様の報酬モデルを用いて、最先端の複雑さの別の代表的アルゴリズムの範囲を広げる。 本研究は,2本以上の腕を持つ症例に対して,既知の半パラメトリックバンディットアルゴリズムから,これらの手法の優位性を確認するためのシミュレーション結果と,その上界の複雑さを導出したものである。
  論文  参考訳（メタデータ） (2023-01-20T19:39:10Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。 我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
  論文  参考訳（メタデータ） (2020-11-17T05:41:50Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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