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

arXiv:2602.10971v2 Announce Type: replace 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 ilde{{O}}left( d sqrt{sum_t g(au_t) ot{mu}{t,star}} + d^2 g{max} kappa + d (g_{max} + kappa) C right), where ot{mu}{t,star} is the slope of mu around the optimal arm at time t, g(au_t)'s are potentially exogenously time-varying dispersions (e.g., g(au_t) = sigma_t^2 for heteroskedastic linear bandits, g(au_t) = 1 for Bernoulli and Poisson), g{max} = max_{t in [T]} g(au_t) is the maximum dispersion, and C geq 0 is the total corruption budget of the adversary. We complement this with a lower bound of ilde{Omega}(d sqrt{sum_t g(au_t) ot{mu}_{t,star}} + d C), unifying previous problem-specific lower bounds. Thus, our algorithm achieves, up to a kappa-factor in the corruption term, instance-wise minimax optimality simultaneously across various instances of heteroskedastic GLBs with adversarial corruptions.

Source: arXiv cs.LG | 2026-06-23