A Jointly Efficient and Near-Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions

We consider heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions and propose HCW-GLB-OMD, a simple algorithm that combines an online mirror descent (OMD)-based estimator with Hessian-based confidence weights. Although both components are well studied, establishing guarantees for the combined algorithm requires a nontrivial analysis. We establish a corruption-robust confidence sequence using technical tools not required in prior analyses, including a weighted likelihood supermartingale and a self-bounding argument. For the regret analysis, we derive a new Hessian potential lemma to handle the interaction between adversarial corruption and adaptive confidence weighting. For self-concordant GLMs, we prove a high-probability regret bound of (d sqrt sum t g(τ t) μ t, + d squared g κ+ d(1+κ)(C 1)), where μ t, is the slope of μ at the optimal arm at time t, g(τ t) is the observed dispersion, g= t g(τ t), κ is the worst-case inverse slope of μ, and C is the corruption budget. The algorithm attains this bound with one OMD update per round and O(d 2) storage. We complement this guarantee with matching lower bounds for the leading sqrt T term and, up to κ, the dC corruption term.