論文の概要: Sharp Non-Asymptotic Analysis of the Penalized Challenger in $β$-EB-TCI for Bernoulli Bandits

• arxiv url: http://arxiv.org/abs/2610.01951v1
• Date: Thu, 01 Oct 2026 16:11:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.263849
• Title: Sharp Non-Asymptotic Analysis of the Penalized Challenger in $β$-EB-TCI for Bernoulli Bandits
• Title（参考訳）: ベルヌーイバンドに対する$β$-EB-TCIにおけるペナル化チャレンジャーのシャープ非漸近解析
• Abstract要約: ベルヌーイ・バンディッツの問題は、Jourdan et alの実証的最上位2つのルールを通して研究する。 以上の結果から,Bernoulliインスタンスの非漸近的高確率が一意のベストアームを持つことを示す。
• 参考スコア（独自算出の注目度）: 2.743619778265185
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Top-two algorithms are simple and effective for fixed-confidence best-arm identification, but their sharp non-asymptotic behavior is still not well understood. We study this problem for Bernoulli bandits through $β$-EB-TCI, the empirical-best top-two rule of Jourdan et al., whose challenger is chosen using a Bernoulli transportation cost with a logarithmic count penalty. We prove that, after the empirical leader has become the true best arm and its sampling fraction stays close to $β$, the stopping time is $T_β^{\star}(μ)\log(1/δ)$ up to lower-order concentration terms. We also show that, in this regime, every challenger is sampled linearly often. Thus, for the original algorithm without forced exploration, the main remaining difficulty is to control when the empirical leader becomes permanently correct. These results imply a non-asymptotic high-probability bound for all Bernoulli instances with a unique best arm. If the algorithm satisfies a finite-mean sufficient-exploration condition, the bound further yields the sharp expected sample complexity. In particular, this gives the sharp expectation result for the unguarded Bernoulli rule when all arm means are pairwise distinct, using the sufficient-exploration result of Jourdan et al. Finally, if we add a mild forced-exploration rule that contributes only $O(\sqrt{Kt})$ pulls up to time $t$, we obtain a self-contained expected sample-complexity theorem for any number of arms under the unique-best-arm assumption. We also identify a limitation of proof strategies that try to handle equal suboptimal means through a single index-comparison argument.
• Abstract（参考訳）: 上位2つのアルゴリズムは、固定信頼度の高いベストアーム識別にシンプルで効果的であるが、その鋭い非漸近的挙動はよく理解されていない。 ベルヌーイのバンディットに対するこの問題について,Jourdan et al の実証的最上位2ルールである$β$-EB-TCIを用いて検討する。 実験的リーダが真のベストアームとなり、サンプリング分画が$β$に近づいた後、停止時間は$T_β^{\star}(μ)\log(1/δ)$より下位の濃度項までであることを示す。 また、この体制では、全ての挑戦者が線形にサンプリングされることも示している。 したがって、強制探索を行わない元のアルゴリズムでは、経験的リーダーが永久に正しいときに制御することが主な難しさである。 これらの結果は、独特なベストアームを持つすべてのベルヌーイインスタンスに対して非漸近高確率が有界であることを意味する。 もしこのアルゴリズムが有限平均探索条件を満たすなら、その境界はさらにシャープなサンプル複雑性をもたらす。 特に、このことは、全てのアーム平均がペアで異なるときにベルヌーイ則に対するシャープな期待結果を与える。これは、Jourdanらによる十分探索結果を使い、最後に、わずかに$O(\sqrt{Kt})$を時間$t$まで引き上げる穏やかな強制探索則を加えると、一意のベスト・アームの仮定の下で任意の腕に対して自己完結した標本複素性定理を得る。 また, 1 つの指数比較論により, 等価な準最適手段を扱おうとする証明戦略の限界も同定する。

関連論文リスト

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。 我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
  論文  参考訳（メタデータ） (2026-08-06T19:49:48Z)
• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  本研究では,学習者が端末の推薦を控えることができるベイジアン固定予算のベストアーム識別問題について検討する。 本研究は,非検出誤りの確率を解析し,吸収を伴わない準最適腕を推奨するリスクについて考察する。
  論文  参考訳（メタデータ） (2026-06-28T05:07:27Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Multi-Armed Sequential Hypothesis Testing by Betting [44.29651618521598]
  我々は、グローバル null 仮説 $mathscrP$ と合成代替 $mathscrQ$ を考える。 いくつかの腕がnullではないとしても、我々は$e$プロセスとシーケンシャルテストを求め、そのパフォーマンスは、どの腕が$mathscrP$に対して最もエビデンスを生成するかというオラクル知識を持つものと同じくらいである。 この最適性分析における重要な技術的装置は、観測不能だが十分に「推定可能」な報酬に対して、上信任性バウンドのようなアルゴリズムを改良したものである。
  論文  参考訳（メタデータ） (2026-03-18T17:01:34Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
  論文  参考訳（メタデータ） (2024-03-14T06:14:07Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit [1.2183405753834562]
  この研究は、両腕のベルヌーイ・バンディット問題(英語版)(Bernoulli bandit problem)の、腕の手段の和が1であるバージョンに対処する。 我々は, それぞれの問題を線形熱方程式の解に関連付けることにより, minmax最適後悔と擬似回帰の先行順序項を得る。
  論文  参考訳（メタデータ） (2022-02-11T17:03:18Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)

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

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