Generalized linear bandits are sequential decision problems in which each action has a feature vector and the expected reward is related to it through a link function. The paper considers two complications at once: heteroskedastic noise, where the dispersion of observations varies over time, and adversarial corruptions, where an attacker can tamper with a bounded budget of rewards before they are observed.
The authors propose HCW-GLB-OMD, a simple combination of an online mirror descent (OMD) estimator with Hessian-based confidence weights. Although both ingredients are known, the combined algorithm needs a new analysis. The proof introduces a weighted likelihood supermartingale and a self-bounding argument to build a corruption-robust confidence sequence, plus a Hessian potential lemma to control the interaction between adaptive weights and corruption.
For self-concordant generalized linear models, the algorithm's high-probability regret bound has a leading term of order d times the square root of accumulated observed dispersion, with additive terms depending on the worst-case inverse slope and the corruption budget C. The algorithm is computationally efficient: one OMD update per round and O(d^2) storage. The authors also prove matching lower bounds for the leading sqrt(T) term and, up to a slope factor, the dC corruption term, indicating the algorithm is near-optimal.