論文の概要: Parameter-Free Heavy-Tailed Bandits

• arxiv url: http://arxiv.org/abs/2607.29460v1
• Date: Fri, 31 Jul 2026 14:27:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-03 14:29:40.760483
• Title: Parameter-Free Heavy-Tailed Bandits
• Title（参考訳）: パラメータフリーヘビープレートバンド
• Abstract要約: 固定テール指数のモーメント境界$u$に対する適応について研究する。 我々は、全てのアルゴリズムが$u$を知らないこと、あるいはその上限を知らないことは、その分布依存と分布に依存しない後悔の保証の間に急激なトレードオフを従わなければならないことを証明している。
• 参考スコア（独自算出の注目度）: 36.983245230853434
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Heavy-tailed distributions arise naturally in sequential decision-making problems such as financial investment, online advertising, and network management, where rare but extreme outcomes can dominate performance. Heavy-tailed bandits model online decision-making in these settings by assuming only that rewards $X$ satisfy $\mathbb{E}[|X|^{1+ε}]\leq u$, for some tail exponent $ε\in(0,1]$ and moment bound $u<+\infty$. However, most existing regret minimization algorithms require these parameters to be known. This assumption is particularly restrictive in practice: $ε$ and $u$ govern the frequency and magnitude of rare events and are therefore precisely the quantities that are hardest to infer reliably from limited observations. Motivated by an open problem posed by Genalti and Metelli at COLT 2025, we resolve the assumption-free adaptation problem for heavy-tailed bandits and characterize the price in the regret of not knowing the tail parameters. We first study adaptation to the moment bound $u$ for a fixed tail exponent $ε$. We prove that every algorithm unaware of $u$, or of any upper bound on it, must obey a sharp trade-off between its distribution-dependent and distribution-free regret guarantees. We then introduce a scheduled-exploration algorithm that requires no knowledge of $u$ and matches the resulting adaptation frontier up to logarithmic factors. Finally, we show that the same algorithm can be instanced without knowing $ε$ by calibrating its exploration schedule to the endpoint $ε=1$. It achieves sublinear regret for every fixed $ε>0$, while no algorithm can guarantee sublinear regret uniformly over all $ε\in(0,1]$. Altogether, our results resolve the COLT open problem without additional distributional assumptions and provide a sharp characterization of the statistical cost of adapting to unknown heavy tails.
• Abstract（参考訳）: 重細な分布は、金融投資、オンライン広告、ネットワーク管理といったシーケンシャルな意思決定問題に自然に現れ、稀だが極端な結果がパフォーマンスを左右する。 重い尾のバンディットは、これらの設定でオンライン意思決定をモデル化し、$X$が$\mathbb{E}[|X|^{1+ε}]\leq u$を満足するものと仮定し、あるテール指数$ε\in(0,1]$と、モーメント境界$u<+\infty$を仮定する。 しかし、既存の後悔の最小化アルゴリズムはこれらのパラメータを知っておく必要がある。 ε$ と $u$ は稀な事象の頻度と大きさを支配しており、したがって厳密には、限られた観測から確実に推測することが難しい量である。 COLT 2025でGenalti と Metelli が提起したオープンな問題に動機付けられ、重尾のバンディットに対する仮定なし適応問題を解決し、テールパラメータを知らないことを後悔して価格を特徴付ける。 まず、固定尾指数$ε$に対するモーメント有界$u$への適応について研究する。 我々は、全てのアルゴリズムが$u$を知らないこと、あるいはその上限を知らないことは、その分布依存と分布に依存しない後悔の保証の間に急激なトレードオフを従わなければならないことを証明している。 次に、$u$の知識を必要としないスケジュール探索アルゴリズムを導入し、その結果の適応フロンティアを対数因子に一致させる。 最後に、探索スケジュールを$ε=1$に調整することで、同じアルゴリズムが$ε$を知らずにインスタンス化可能であることを示す。 すべての固定された$ε>0$に対してサブリニア後悔を達成するが、すべての$ε\in(0,1]$に対して一様にサブリニア後悔を保証するアルゴリズムは存在しない。 また,この結果から,COLTの開解問題を,余分な分布仮定を伴わずに解決し,未知の重みに適応する統計的コストの急激な評価を行うことができた。

関連論文リスト

• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  本研究では,学習者が端末の推薦を控えることができるベイジアン固定予算のベストアーム識別問題について検討する。 本研究は,非検出誤りの確率を解析し,吸収を伴わない準最適腕を推奨するリスクについて考察する。
  論文  参考訳（メタデータ） (2026-06-28T05:07:27Z)
• Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning [39.8867004581646]
  すべての信頼レベル$in (0,1]$に対して均一に保たれる確率的保証として分布的後悔を定式化する。 探索ボーナス$minc_1,k/N,c_2,k/sqrtN$,$N$は訪問数を表し,$(c_1,k,c_2,k)$はユーザ指定パラメータである。 我々の境界は、ミニマックスとインスタンス依存のレジームの両方において、期待と分布の後悔の間の最適なトレードオフを達成する
  論文  参考訳（メタデータ） (2026-05-06T16:38:30Z)
• No-Regret Linear Bandits under Gap-Adjusted Misspecification [38.592043705502725]
  既存の線形包帯の作用は通常、最良の線形近似のsup-norm誤差を測定する一様不特定パラメータ$epsilon$に依存する。 そこで本研究では,各入力における近似誤差をx$で近似し,その差分をx$で比例する,より自然な不特定モデルを提案する。 我々は,従来のLinUCBアルゴリズムが,そのような$rho$-gap-adjusted misspecificationに対して自動的に堅牢であることを示す。
  論文  参考訳（メタデータ） (2025-01-09T16:44:53Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。 AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-04T17:11:15Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)
• Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed Distributions [2.2940141855172036]
  我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。 $delta$-correctアルゴリズムの下位境界はよく知られている。 我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
  論文  参考訳（メタデータ） (2019-08-24T05:31:49Z)

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

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