論文の概要: Catoni Contextual Bandits are Robust to Heavy-tailed Rewards

• arxiv url: http://arxiv.org/abs/2502.02486v1
• Date: Tue, 04 Feb 2025 17:03:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 15:03:50.317663
• Title: Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
• Title（参考訳）: Catoni Contextual Bandits is Robust to Heavy-tailed Rewards
• Authors: Chenlu Ye, Yujia Jin, Alekh Agarwal, Tong Zhang,
• Abstract要約: 頑健な統計量からカトニ推定器上にアルゴリズム的アプローチを構築する。 我々は、累積的な報酬分散と対数的に報酬範囲の$R$にのみ依存する後悔境界を確立する。 アルゴリズムはまた、対数的報酬範囲依存を伴う分散ベースのバウンダリも享受する。
• 参考スコア（独自算出の注目度）: 31.381627608971414
• License:
• Abstract: Typical contextual bandit algorithms assume that the rewards at each round lie in some fixed range $[0, R]$, and their regret scales polynomially with this reward range $R$. However, many practical scenarios naturally involve heavy-tailed rewards or rewards where the worst-case range can be substantially larger than the variance. In this paper, we develop an algorithmic approach building on Catoni's estimator from robust statistics, and apply it to contextual bandits with general function approximation. When the variance of the reward at each round is known, we use a variance-weighted regression approach and establish a regret bound that depends only on the cumulative reward variance and logarithmically on the reward range $R$ as well as the number of rounds $T$. For the unknown-variance case, we further propose a careful peeling-based algorithm and remove the need for cumbersome variance estimation. With additional dependence on the fourth moment, our algorithm also enjoys a variance-based bound with logarithmic reward-range dependence. Moreover, we demonstrate the optimality of the leading-order term in our regret bound through a matching lower bound.
• Abstract（参考訳）: 典型的な文脈的バンディットアルゴリズムは、各ラウンドの報酬は一定の範囲$[0, R]$で、彼らの後悔は、この報酬範囲$R$で多項式的にスケールする。 しかし、多くの現実的なシナリオは当然、最悪の場合の範囲が分散よりもかなり大きいような、重い尾の報酬や報酬を伴っている。 本稿では,ロバストな統計量からカトニ推定器上に構築したアルゴリズム的アプローチを開発し,これを一般関数近似を用いた文脈的帯域幅に適用する。 各ラウンドにおける報酬の分散が知られているとき、分散重み付き回帰法を用いて、累積的な報酬の分散と対数的に報酬範囲$R$とラウンド数$T$に依存する後悔境界を確立する。 未知分散の場合、注意深い剥離に基づくアルゴリズムを提案し、煩雑な分散推定の必要性を除去する。 第4モーメントへのさらなる依存により、我々のアルゴリズムは対数的報酬範囲に依存する分散ベースのバウンダリも享受する。 さらに, 最優先項の最適性は, 一致した下界を通した残余項の最適性を示す。

関連論文リスト

• An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints [29.596684377841182]
  本研究では、休息状態において、アームの平均報酬が各プルで減少する可能性があるが、そうでなければ変化しない、無限に多くの武器を持つバンディット問題を考察する。 本稿では,ゆがみ報酬に起因するバイアスや分散トレードオフを管理するために,適応的なスライディングウィンドウを備えたUTBを利用するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-22T14:11:54Z)
• 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)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• 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)
• A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits [11.918230810566945]
  本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。 我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
  論文  参考訳（メタデータ） (2022-01-17T17:23:56Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。 評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
  論文  参考訳（メタデータ） (2021-12-13T09:48:54Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)

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

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