Abstract
We consider the problem of heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions, which subsumes various stochastic contextual bandit settings, including heteroskedastic linear bandits and logistic/Poisson bandits. 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 O( d √Σ_t g(τ_t) μ_t,⋆ + d² g_max κ + d κ C ), where μ_t,⋆ is the slope of μ around the optimal arm at time t, g(τ_t)'s are potentially exogenously time-varying dispersions (e.g., g(τ_t) = σ_t² for heteroskedastic linear bandits, g(τ_t) = 1 for Bernoulli and Poisson), g_max = max_t ∈ [T] g(τ_t) is the maximum dispersion, and C ≥ 0 is the total corruption budget of the adversary. We complement this with a lower bound of Ω(d √Σ_t g(τ_t) μ_t,⋆ + d C), unifying previous problem-specific lower bounds. Thus, our algorithm achieves, up to a κ-factor in the corruption term, instance-wise minimax optimality simultaneously across various instances of heteroskedastic GLBs with adversarial corruptions.