論文の概要: Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions

• arxiv url: http://arxiv.org/abs/2610.38243v1
• Date: Wed, 28 Oct 2026 03:48:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.369402
• Title: Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
• Title（参考訳）: 強い破壊を伴う逆線形帯域に対する極小最小レグレット
• Abstract要約: 本研究では, 学習者の行動を見た結果, 適応的相手がそれぞれの報酬を損なうような, 強い腐敗を伴う逆線形包帯について検討した。 本稿では,正規化カーネル推定器を用いて,半径重み付きエントロピー正規化器で追従正規化リーダを動作させ,報酬を推定するCRW-FTRLを提案する。 $mathbbRd$ の $K$ アクションに対して、CRW-FTRL は $tilde O(sqrtdTlog K + dC)$ regret を達成する。
• 参考スコア（独自算出の注目度）: 56.915716369803356
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study adversarial linear bandits with strong corruption, in which an adaptive adversary chooses the reward vectors and a strong adversary corrupts each observed reward after seeing the learner's action, subject to a known total corruption budget $C$. Strong corruption breaks the importance-weighted reward estimates used by adversarial bandit algorithms: by corrupting only the rounds in which a rarely sampled action is drawn, the adversary amplifies each unit of corruption by the inverse of its sampling probability. The best known bound for this problem, $\tilde O(\sqrt{d^3T} + dC)$ by Liu et al. (2024), is a factor $\sqrt{d}$ above the corruption-free rate in its leading term, and whether $\tilde O(d\sqrt{T} + dC)$ regret is achievable was left open. We propose CRW-FTRL, which runs follow-the-regularized-leader with a radius-weighted entropy regularizer and estimates rewards with a normalized kernel estimator whose sensitivity to corruption is governed by per-action radii instead of inverse sampling probabilities. The radii are nondecreasing and are chosen jointly with the sampling distribution through a monotone log-determinant barrier problem, so that a negative linear term in the regularizer cancels both the corruption bias and the estimation error of every comparator. For $K$ actions in $\mathbb{R}^d$, CRW-FTRL achieves $\tilde O(\sqrt{dT\log K} + dC)$ regret with high probability against an adaptive adversary, which matches the best known corruption-free rate and the $Ω(dC)$ lower bound up to logarithmic factors. Applied to a discretization of a general compact action set, it yields $\tilde O(d\sqrt{T} + dC)$ regret, which settles the statistical rate of corrupted adversarial linear bandits under strong corruption.
• Abstract（参考訳）: 適応的相手が報酬ベクトルを選択し、強い相手が学習者の行動を見た後に各観察された報酬を、既知の全汚職予算(C$)を条件として、強い汚職を伴う敵線形帯域について検討した。 強い腐敗は、敵のバンドイットアルゴリズムが用いる重み付けされた報酬推定を破る: 稀にサンプリングされたアクションが引き出されるラウンドのみを腐敗させることで、敵は、そのサンプリング確率の逆で各不正の単位を増幅する。 この問題の最もよく知られた境界は、Liu et al (2024) による $\tilde O(\sqrt{d^3T} + dC)$ であり、その先行項における汚職フリー率より上の係数 $\sqrt{d}$ であり、$\tilde O(d\sqrt{T} + dC)$ 後悔は達成可能かどうかである。 本稿では, 正規化カーネル推定器を用いて, 逆サンプリング確率ではなく, 逆サンプリング確率ではなく, 反応ラジイによって汚損に対する感受性が支配される正則化カーネル推定器で報酬を推定するCRW-FTRLを提案する。 ラジイは非減少であり、単調な対数決定障壁問題を通じてサンプリング分布と共同選択されるので、正規化器内の負の線形項は、各コンパレータの腐敗バイアスと推定誤差の両方をキャンセルする。 $\mathbb{R}^d$の$K$アクションに対して、CRW-FTRL は $\tilde O(\sqrt{dT\log K} + dC)$ regret with high probability against an Adaptive adversary, which is match the best known corruption-free rate and $Ω(dC)$ lower bound to logarithmic factors。 一般的なコンパクトな作用集合の離散化に適用すると、$\tilde O(d\sqrt{T} + dC)$ regret となり、強い汚職の下で崩壊した逆線型包帯の統計速度を落ち着かせる。

関連論文リスト

• 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)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)

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

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