論文の概要: Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards

• arxiv url: http://arxiv.org/abs/2604.14876v1
• Date: Thu, 16 Apr 2026 11:05:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-17 21:29:31.857524
• Title: Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
• Title（参考訳）: ジェネリック・リワードを用いた最適帯域幅アルゴリズムのレグレト・テール特性
• Authors: Subhodip Panda, Shubhada Agrawal,
• Abstract要約: 予測に最適なアルゴリズムの多腕バンディットにおける後悔の尾の挙動について検討する。 我々は後悔の尾の確率に新しい上限を導いた。 この結果から, 最適KLに基づく UCB アルゴリズムにおいて, 後悔尾の統一的, 厳密な特徴付けが得られた。
• 参考スコア（独自算出の注目度）: 3.396415446890748
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the tail behavior of regret in stochastic multi-armed bandits for algorithms that are asymptotically optimal in expectation. While minimizing expected regret is the classical objective, recent work shows that even such algorithms can exhibit heavy regret tails, incurring large regret with non-negligible probability. Existing sharp characterizations of regret tails are largely restricted to parametric settings, such as single-parameter exponential families. In this work, we extend the $\KLinf$-UCB algorithm of to a broad nonparametric class of reward distributions satisfying mild assumptions, and establish its asymptotic optimality in expectation. We then analyze the tail behavior of its regret and derive a novel upper bound on the regret tail probability. As special cases, our results recover regret-tail guarantees for both bounded-support and heavy-tailed (moment-bounded) bandit models. Moreover, for the special case of finitely-supported reward distributions, our upper bound matches the known lower bound exactly. Our results thus provide a unified and tight characterization of regret tails for asymptotically optimal KL-based UCB algorithms, going beyond parametric models.
• Abstract（参考訳）: 本稿では,確率的マルチアームバンディットにおける後悔の尾の挙動について,漸近的に最適であるアルゴリズムについて検討する。 期待される後悔を最小化することが古典的な目的であるが、最近の研究は、そのようなアルゴリズムでさえ重い後悔の尾を呈し、無視できない確率で大きな後悔を引き起こすことを示している。 既存の後悔の尾の鋭い特徴は、単パラメータ指数族のようなパラメトリックな設定に大きく制限されている。 この研究は、$\KLinf$-UCBアルゴリズムを、軽度の仮定を満たす広い非パラメトリックな報酬分布のクラスに拡張し、期待する際の漸近的最適性を確立する。 次に、その後悔の尾の挙動を分析し、後悔の尾の確率に新しい上限を導出する。 特別の場合として,本研究の結果は,有界サポートモデルとヘビーテール(モメントバウンド)バンディットモデルの両方において,遺残テール保証を回復する。 さらに、有限支持された報酬分布の特別な場合、上界は既知の下界と正確に一致する。 この結果から, 漸近的に最適なKLに基づく UCB アルゴリズムに対して, パラメトリックモデルを超えて, 後悔の尾の統一的, 厳密な特徴付けが得られた。

関連論文リスト

• Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses [0.6321283533425183]
  損失関数が非滑らかである可能性のある,逆帯域最適化問題のクラスについて検討する。 分析の特別な場合として,古典的帯域最適化の高確率化を図った。
  論文  参考訳（メタデータ） (2026-03-27T04:33:08Z)
• Tail Distribution of Regret in Optimistic Reinforcement Learning [3.9962751777898955]
  累積的後悔$R_K$ over $K$ エピソードのテール分布を,期待値や単一高確率量子化ではなく,特徴付ける。 提案したアルゴリズムは、期待される後悔と、その後悔がガウス以下の尾を示す範囲のバランスをとるチューニングパラメータ$$に依存する。
  論文  参考訳（メタデータ） (2025-11-23T02:23:09Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• The Fragility of Optimized Bandit Algorithms [4.390757904176221]
  帯域幅アルゴリズムの最適設計に関する文献の多くは、期待される後悔の脆弱さに基づいている。 最適化された UCB バンディットの設計は,問題をわずかに誤定義した場合に脆弱であることを示す。 提案手法は, 誤り特定に対する強靭性を確保するために, UCBアルゴリズムを改良可能であることを示す。
  論文  参考訳（メタデータ） (2021-09-28T10:11:06Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)

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

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