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

Abstract

We consider the problem of heteroskedastic generalized linear bandits with adversarial corruptions, which subsumes various stochastic contextual bandit settings, including heteroskedastic linear bandits and logistic/Poisson bandits. We propose \texttt{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 $\gO(1)$ space and time complexity per iteration. Under the self-concordance assumption on the link function, we show a regret bound of $\tilde{\gO}\left( d \sqrt{g_{\max} \sum_t \dmu_{t,\star}} \wedge d \sqrt{\sum_t g(\tau_t)} + d^2 g_{\max} \kappa + d \kappa C \right)$, where $\dmu_{t,\star}$ is the slope of $\mu$ around the optimal arm at time $t$, $g(\tau_t)$’s are potentially exogenously time-varying dispersions (e.g., $g(\tau_t) = \sigma_t^2$ for heteroskedastic linear bandits, $g(\tau_t) = 1$ for Bernoulli and Poisson), $g_{\max} = \max_{t \in [T]} g(\tau_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 $\Omega(d \sqrt{\sum_t g(\tau_t) \dmu_{t,\star}} + d C)$, unifying previous problem-specific lower bounds. Thus, our algorithm achieves near-instance-wise minimax optimality across various instances of self-concordant, heteroskedastic GLB with adversarial corruption.

Junghyun Lee

PhD Student

PhD student at GSAI, KAIST, jointly advised by Profs. Se-Young Yun and Chulhee Yun. Research focuses on interactive machine learning, particularly at the intersection of RLHF and preference learning, and statistical analyses of large networks, with an emphasis on community detection. Broadly interested in mathematical and theoretical AI, related problems in mathematics, and recently, LLMs.