論文の概要: Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits

• arxiv url: http://arxiv.org/abs/2505.20051v1
• Date: Mon, 26 May 2025 14:40:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:43.518316
• Title: Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits
• Title（参考訳）: 非定常重管バンドにおけるレギュレット最小化のためのカタニ-スタイル切替点検出
• Authors: Gianmarco Genalti, Sujay Bhatt, Nicola Gatti, Alberto Maria Metelli,
• Abstract要約: ヘビーテールの片側定常バンディット問題に対処する。 重み付き分布に適した新しいカタニスタイル変化点検出戦略を提案する。 本稿では,この変化点検出戦略と楽観的アルゴリズムを組み合わせたロバストCPD-UCBを提案する。
• 参考スコア（独自算出の注目度）: 31.212504858546232
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Regret minimization in stochastic non-stationary bandits gained popularity over the last decade, as it can model a broad class of real-world problems, from advertising to recommendation systems. Existing literature relies on various assumptions about the reward-generating process, such as Bernoulli or subgaussian rewards. However, in settings such as finance and telecommunications, heavy-tailed distributions naturally arise. In this work, we tackle the heavy-tailed piecewise-stationary bandit problem. Heavy-tailed bandits, introduced by Bubeck et al., 2013, operate on the minimal assumption that the finite absolute centered moments of maximum order $1+\epsilon$ are uniformly bounded by a constant $v<+\infty$, for some $\epsilon \in (0,1]$. We focus on the most popular non-stationary bandit setting, i.e., the piecewise-stationary setting, in which the mean of reward-generating distributions may change at unknown time steps. We provide a novel Catoni-style change-point detection strategy tailored for heavy-tailed distributions that relies on recent advancements in the theory of sequential estimation, which is of independent interest. We introduce Robust-CPD-UCB, which combines this change-point detection strategy with optimistic algorithms for bandits, providing its regret upper bound and an impossibility result on the minimum attainable regret for any policy. Finally, we validate our approach through numerical experiments on synthetic and real-world datasets.
• Abstract（参考訳）: 広告からレコメンデーションシステムまで、現実世界の問題の幅広いクラスをモデル化できるため、確率的でない非定常バンドのレグレト最小化は過去10年間に人気を博した。 現存する文献はベルヌーイやサブガウスの報酬など、報酬を生み出す過程に関する様々な仮定に依存している。 しかし、金融や電気通信といった環境では、重細な分布が自然に発生する。 本研究では,重み付き片側定常バンドイット問題に取り組む。 ブベックらによって2013年に導入された重尾の包帯は、最大次数 $1+\epsilon$ の有限絶対中心モーメントが、ある$\epsilon \in (0,1]$ に対して定数 $v<+\infty$ で一様有界であるという最小の仮定で運営されている。 我々は、最も人気のある非定常的帯域設定、すなわち、報酬生成分布の平均が未知の時間ステップで変化するような断片的定常設定に焦点を当てる。 独立性のある逐次推定理論の最近の進歩に依拠し, 重み付き分布に適した新しいカタニ式変化点検出戦略を提案する。 本稿では,この変化点検出戦略と包帯に対する楽観的アルゴリズムを組み合わせたロバストCPD-UCBを提案する。 最後に,合成および実世界のデータセットに関する数値実験により,本手法の有効性を検証した。

関連論文リスト

• Tracking Most Significant Shifts in Infinite-Armed Bandits [3.591122855617648]
  本研究では,貯水池分布からアクションの平均報酬をサンプリングする無限武装バンディット問題について検討する。 貯水池の正則性の全規則に対して, パラメータフリーな最適後悔境界を示す。 そこで我々は,無作為な除去の変種を用いることで,大きな変化の点におけるより厳密な後悔境界を適応的に達成できることを示した。
  論文  参考訳（メタデータ） (2025-01-31T19:00:21Z)
• 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)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• Minimax Policy for Heavy-tailed Bandits [10.203602318836444]
  我々は、飽和経験平均を用いて、ガウス以下の報酬分布に対するミニマックスポリシー MOSS を修正し、ロバスト MOSS と呼ばれる新しいアルゴリズムを設計する。 報酬分布に対する1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1。
  論文  参考訳（メタデータ） (2020-07-20T21:43:57Z)
• Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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