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

Abstract

We consider the problem of heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions, which subsumes heteroskedastic linear bandits and logistic/Poisson bandits, in the presence of adversarial corruptions. We propose HCW-GLB-OMD, which consists of two components: an online mirror descent (OMD)-based estimator and Hessian-based confidence weights to achieve corruption robustness. This is computationally efficient in that it only requires $O(1)$ space and time complexity per iteration. Under the self-concordance assumption on the link function, we show a regret bound of $\tilde{O}\left(d\sqrt{{\sum }_{t}g(\ddot{I}{„}_t)\dot{\hat{I}}{¼}_{t,\star }}+d^2{g}_{\max }\hat{I}º+d(g_{\max }+\hat{I}º)C\right)$, where $\dot{\hat{I}}{¼}_{t,\star }$ is the slope of $\hat{I}¼$ around the optimal arm at time $t$, $g(\ddot{I}{„}_t)$'s are potentially exogenously time-varying dispersions (e.g., $g(\ddot{I}{„}_t)=\ddot{I}{ƒ}_t^2$ for heteroskedastic linear bandits, $g(\ddot{I}{„}_t)=1$ for Bernoulli and Poisson), $g_{\max }={\max }_{t\in [T]}g(\ddot{I}{„}_t)$ is the maximum dispersion, and $C\ge 0$ is the total corruption budget of the adversary. We complement this with a lower bound of $\tilde{\hat{I}}\text{c◯}(d\sqrt{{\sum }_{t}g(\ddot{I}{„}_t)\dot{\hat{I}}{¼}_{t,\star }}+dC)$, unifying previous problem-specific lower bounds. Thus, our algorithm achieves, up to a $\hat{I}º$-factor in the corruption term, instance-wise minimax optimality simultaneously across various instances of heteroskedastic GLBs with adversarial corruptions.

40 pages, 1 table (ver2: some updates)