CRW-FTRL matches corruption-free regret under strong bandit corruption
Original title: Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
For K actions in d dimensions it reaches Õ(√(dT log K)+dC) regret and settles the compact-set rate.
The paper studies adversarial linear bandits in which an adaptive adversary picks reward vectors and a strong adversary corrupts observed rewards after seeing the learner’s action, under a known total budget C. Strong corruption breaks importance-weighted estimates by amplifying corruption on rarely sampled actions. The authors propose CRW-FTRL, follow-the-regularized-leader with a radius-weighted entropy regularizer and a normalized kernel estimator. They report high-probability regret matching the best known corruption-free rate and the Ω(dC) lower bound up to logs, and Õ(d√T+dC) on a discretization of a compact action set.
- Liu et al. (2024) had Õ(√(d³T)+dC), a √d gap in the leading term.
- Radii are nondecreasing and chosen with the sampling distribution via a log-determinant barrier.
- A negative linear regularizer term is said to cancel corruption bias and estimation error.
- The compact-action result is presented as settling the statistical rate under strong corruption.
From the original article
1 min read at arxiv.orgWe 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$.
By Qiwei Di · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.