論文の概要: Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise

• arxiv url: http://arxiv.org/abs/2603.15596v1
• Date: Mon, 16 Mar 2026 17:53:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 18:28:58.714192
• Title: Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise
• Title（参考訳）: 逆流破壊と重畳音下での線形帯域のロバストと計算効率のよい線形帯域
• Authors: Naoto Tani, Futoshi Futami,
• Abstract要約: 敵対的腐敗と重み付き雑音下での線形文脈的包帯について検討した。 本アルゴリズムは, 対向汚損と重み付き雑音の両面に対して頑健性を実現する。
• 参考スコア（独自算出の注目度）: 5.296855056439798
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study linear contextual bandits under adversarial corruption and heavy-tailed noise with finite $(1+ε)$-th moments for some $ε\in (0,1]$. Existing work that addresses both adversarial corruption and heavy-tailed noise relies on a finite variance (i.e., finite second-moment) assumption and suffers from computational inefficiency. We propose a computationally efficient algorithm based on online mirror descent that achieves robustness to both adversarial corruption and heavy-tailed noise. While the existing algorithm incurs $\mathcal{O}(t\log T)$ computational cost, our algorithm reduces this to $\mathcal{O}(1)$ per round. We establish an additive regret bound consisting of a term depending on the $(1+ε)$-moment bound of the noise and a term depending on the total amount of corruption. In particular, when $ε= 1$, our result recovers existing guarantees under finite-variance assumptions. When no corruption is present, it matches the best-known rates for linear contextual bandits with heavy-tailed noise. Moreover, the algorithm requires no prior knowledge of the noise moment bound or the total amount of corruption and still guarantees sublinear regret.
• Abstract（参考訳）: 対数汚損と重み付き雑音の下での線形文脈帯域を、約$ε\in (0,1]$に対して有限$(1+ε)$-thのモーメントで調べる。 敵対的腐敗と重み付きノイズの両方に対処する既存の作業は、有限分散(すなわち有限第二モーメント)の仮定に依存し、計算の非効率さに悩まされている。 本稿では,オンラインミラー降下に基づく計算効率のよいアルゴリズムを提案する。 既存のアルゴリズムでは$\mathcal{O}(t\log T)$計算コストがかかるが,本アルゴリズムではこれをラウンド当たり$\mathcal{O}(1)$に削減する。 我々は、雑音の1+ε$モーメント境界による項と、腐敗の総量による項からなる加法的後悔境界を確立する。 特に、$ε= 1$のとき、この結果は有限分散仮定の下で既存の保証を回復する。 汚職が存在しない場合、それは線形文脈の包帯と重尾雑音の最もよく知られた速度と一致する。 さらに、このアルゴリズムはノイズモーメント境界や総汚職量の事前知識を必要とせず、サブ線形後悔を保証している。

関連論文リスト

• 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)
• Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions [98.75618795470524]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-13T17:58:58Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)

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

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