論文の概要: 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（参考訳）: 逆流破壊と重畳音下での線形帯域のロバストと計算効率のよい線形帯域
• 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 Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
  一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。 我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
  論文  参考訳（メタデータ） (2023-10-23T04:07:26Z)
• 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)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。 我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。 GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
  論文  参考訳（メタデータ） (2022-02-03T21:19:36Z)
• On the power of adaptivity in statistical adversaries [18.973408992715203]
  統計的問題における対向雑音モデルに関する基礎的問題について検討する。 アルゴリズムの振舞い $mathcalA'$ は、アルゴリズムの $mathcalA'$ のアダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダクティブ・アダクショナル・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ・アダクティブ(英語版)によって常によく近似することができるか?
  論文  参考訳（メタデータ） (2021-11-19T18:26:25Z)
• Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs [27.636407641546914]
  実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。 非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2021-10-26T17:30:44Z)
• 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)

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

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