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

Abstract

We consider heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions and propose \texttt{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 $\tilde{\mathcal{O}}(d\sqrt{{\sum }_{t}g({\tau }_t){\dot{\mu }}_{t,\star }}+d^2{g}_{\max }\kappa +d(1+\kappa )(C\vee 1))$, where ${\dot{\mu }}_{t,\star }$ is the slope of $\mu$ at the optimal arm at time $t$, $g({\tau }_t)$ is the observed dispersion, $g_{\max }={\max }_{t}g({\tau }_t)$, $\kappa$ is the worst-case inverse slope of $\mu$, and $C$ is the corruption budget. The algorithm attains this bound with one OMD update per round and $\mathcal{O}(d^2)$ storage. We complement this guarantee with matching lower bounds for the leading $\sqrt{T}$ term and, up to $\kappa$, the $dC$ corruption term.

arXiv comment44 pages, 1 figure, 1 table (ver3: some updates)