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

Sanghwa Kim, Junghyun Lee, Se-Young Yun

TL;DR

This paper introduces HCW-GLB-OMD, the first algorithm for Generalized Linear Bandits (GLBs) that is simultaneously computationally efficient ($O(1)$ per step), robust to adversarial reward corruptions, and "instance-wise" optimal. It achieves a state-of-the-art regret bound that adapts to the specific curvature of the reward function and varying noise levels, bridging the gap between theoretical optimality and practical scalability.

What Problem Does This Paper Address?

In the world of contextual bandits, a learner tries to pick the best "arm" (action) based on a set of features (context). Generalized Linear Bandits (GLBs) are a popular framework where the reward follows a specific distribution, like Logistic (for clicks) or Poisson (for counts).

However, real-world scenarios are messy in two specific ways:

  1. Heteroskedasticity: The noise level isn't constant. Sometimes it's external (the environment gets noisier), and sometimes it's internal (picking a certain action inherently has higher variance).
  2. Adversarial Corruptions: A malicious actor (or just a glitchy system) might slightly alter the rewards the learner sees. Most algorithms break down if they can't distinguish between "natural noise" and "malicious corruption."

Existing solutions usually force a trade-off: they are either computationally expensive (requiring a full re-calculation of the model at every step), or they aren't robust to corruption, or they provide "worst-case" guarantees that ignore the specific, easier-to-learn structure of a particular problem instance.

Methods

The authors propose HCW-GLB-OMD (Hessian-based Confidence Weighted GLB via Online Mirror Descent). The algorithm has two key "secret sauces":

  • Online Mirror Descent (OMD) Estimator: Instead of solving a complex optimization problem (Maximum Likelihood Estimation) from scratch every time new data arrives, it performs a single, fast gradient-style update. This keeps the per-step complexity at $O(1)$ space and time, making it feasible for high-speed applications.
  • Hessian-based Confidence Weights ($w_t$): This is the "trust mechanism." When the learner receives a reward, it calculates a weight based on the Hessian (the curvature) of the loss function. If a reward comes from a direction where the learner is already very uncertain, the algorithm "discounts" that observation. This prevents an adversary from leading the learner astray by corrupting rewards in high-uncertainty directions.

Datasets

Not discussed in the paper. This is a theoretical machine learning paper focused on proving mathematical guarantees (regret bounds) and establishing lower bounds for a class of algorithms. No empirical experiments on specific datasets were conducted.

Key Insights and Ideas

  • The "Subscript Disagreement" Advantage: Interestingly, the authors found that using an online estimator (OMD) is actually more mathematically tractable for proving robustness than the standard batch MLE. In batch MLE, a single corruption at time $s$ affects the global estimate at time $t$, creating a "disagreement" that is hard to bound. OMD's local update structure avoids this.
  • Unifying Noise Types: The paper treats exogenous noise (varying $\sigma^2$) and endogenous noise (variance inherent to the link function, like in Logistic/Poisson) under a single mathematical umbrella of "time-varying dispersions."
  • Self-Bounding Inequality: To handle the corruption term in the proof, the authors developed a "maximum-involved self-bounding inequality" technique. This allows them to show that the error introduced by the adversary doesn't grow faster than the learner's ability to correct for it.
  • Instance-Wise Optimality: Most bounds depend on the worst-case curvature ($\kappa$) of the link function. This paper's bound depends on the actual slope at the optimal arm ($\dot{\mu}_{t,\star}$), which is often much smaller (and thus better) in practice.

Key Results

  • Regret Upper Bound: The algorithm achieves a regret of: $$\tilde{O}\left( d \sqrt{\sum_t g(\tau_t) \dot{\mu}_{t,\star}} + (d^2 g_{\max} + dC)\kappa \right)$$ The first term is the "clean" regret (optimal for the problem instance), and the second term is the penalty for corruption ($C$) and global curvature ($\kappa$).

  • Lower Bound: They proved a matching lower bound of $\tilde{\Omega}(d \sqrt{\sum_t g(\tau_t) \dot{\mu}_{t,\star}} + dC)$, showing that their algorithm is essentially as good as any algorithm could possibly be for this problem.

  • First for Poisson: This work establishes the first-ever regret lower bound specifically for Poisson bandits.

Limitations and Future Work

  • The $\kappa$ Gap: There is still a small gap in the corruption term. The upper bound scales with $d\kappa C$, while the lower bound is just $dC$. The authors conjecture that the $\kappa$ factor in the corruption term might be removable, but it remains an open technical challenge.
  • Knowledge of Dispersion: The current algorithm assumes the learner observes the exact dispersion parameter $\tau_t$ (the noise level) at each step. In many real-world cases, this might be unknown or misspecified, which would require even more robust analytical tools.
  • Self-Concordance: The results rely on the "self-concordance" of the link function. While this covers Logistic and Poisson, it doesn't cover all possible GLMs (like Gamma or Inverse Gaussian), which could be a direction for expansion.

Summary updated

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 $\tilde{O}\left( d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d^2 g_{\max} κ+ d κC \right)$, where $\dotμ_{t,\star}$ 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^2$ for heteroskedastic linear bandits, $g(τ_t) = 1$ for Bernoulli and Poisson), $g_{\max} = \max_{t \in [T]} g(τ_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 $\tildeΩ(d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + 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.
BibTeX
@misc{kim2026jointly,
  author = {Sanghwa Kim and Junghyun Lee and Se-Young Yun},
  title = {{A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions}},
  year = {2026},
  eprint = {2602.10971},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.10971},
}
Figure