Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions

# 概要
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…

# 原典
https://arxiv.org/abs/2610.38243

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。