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

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Hi, I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "A Jointly Efficient and Near-Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions".

Jane: Here's the gist of the paper. The gist A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions proposes HCW-GLB-OMD, an algorithm that simultaneously tackles heteroskedastic GLBs with adversarial corruptions to achieve instance-wise minimax optimality.

Tom: This is important because it provides a unified framework for sequential decision making under uncertainty in complex real-world scenarios where rewards follow generalized linear models and are subject to adaptive adversarial manipulations.

Jane: Problem Setting The problem involves generalized linear bandits (GLBs), where the expected reward for an arm xt is given by E

rtxt; θ⋆: = µ(⟨xt, θ⋆⟩) with a known inverse link function µ and an unknown parameter θ⋆ in R d The learner receives a potentially time-varying contextual arm-set Xt ⊂ R d (which can be adversarial), selects an action xt ∈ Xt, and observes a stochastic reward rt ∼ GLM(· xt, τt; θ⋆), where the probability density is dp(r x, τt; θ⋆) ∝ exp r⟨x, θ⋆⟩ − m(⟨x, θ⋆⟩) g(τt)-1 dν (1) The only unknown to the learner is theta⋆ ∈ R d and the others are known: g: R -> R>0 is the dispersion function controlling the variability; dν is an appropriate base measure (e.g., Lebesgue or counting); and m: R -> R is the log-partition function satisfying Assumption 1.

Tom: Assumption 1 states that m(·) is three-times differentiable and convex We adopt several standard assumptions from the GLB literature (Lee et al., 2024a; Russac et al., 2021) Denoting X

T: := S t∈

T: Xt, Assumption 2 states that X

T: ⊆ X ≜ B d(1) and θ⋆ ∈ Θ ≜ B d(S) for a known S ∈ (0,∞) Assumption 3 states that there exists Lµ ∈ (0, ∞) and Rs ∈

0, ∞) such that for all (x, θ) ∈ X[T: × Θ, µ˙(⟨x, θ⟩) ≤ Lµ and µ¨(⟨x, θ⟩) ≤ Rsµ˙(⟨x, θ⟩) After observing xt and rt, the adaptive adversary then chooses a corruption level ct ∈ R subject to a corruption budget P tct ≤ C, and reveals only the corrupted reward r˜t = rt + ct to the learner The goal of the learner is to minimize the cumulative pseudo-regret: Reg(T):= X T t=1 µ(⟨xt,⋆, θ⋆⟩) − X T t=1 µ(⟨xt, θ⋆⟩), where xt,⋆ ≜ arg max x∈Xt µ(⟨x, θ⋆⟩) Our Algorithm: HCW-GLB-OMD The algorithm is designed under two principles: first, the algorithm downweights observations from highly uncertain directions.

Paper summary: Tom: So, wrapping up on "A Jointly Efficient and Near-Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions". The authors propose HCW-GLB-OMD.

Jane: They show this method simultaneously handles the heteroskedastic nature of the rewards and the threat of adversarial manipulations by using online mirror descent combined with Hessian confidence weights.

Lu: The main implication is that we get a corruption-robust regret bound that depends on time, dimension d, and those dispersion functions, which is tighter than what’s typically achieved without accounting for corruption or heteroskedasticity.

Meng: From a deployment standpoint, it suggests a way to keep the model stable against adaptive attacks while maintaining reasonable computational overhead per step.

Tom: The authors prove this bound using technical tools like a weighted likelihood supermartingale and a self-bounding argument, which are new for prior analyses in this area.

Jane: It means we have a more rigorous framework for sequential decision making when the underlying model parameters are unknown and the data stream is potentially malicious.

Lu: The work provides that high-probability regret bound of (d sqrt sum t g(tau t) mu t, + d squared g kappa+ d(g + kappa)C) <ref:2602.10971#pg1>.

Tom: And they matched this with lower bounds, showing this is near-optimal performance for this class of problems. It’s a solid result based on rigorous analysis.

Conclusion: Tom: So we’re wrapping up on this paper about heteroskedastic generalized linear bandits and adversarial corruptions by the authors of HCW-GLB-OMD.

Jane: Basically, they developed an algorithm that tackles two tricky problems at once—the reward variance changing over time, and someone actively trying to trick the system.

Lu: They used a combination of online mirror descent for the updates and Hessian based confidence weights to keep things stable against those attacks.

Meng: From where I stand on deployment, the key is that this whole thing runs with just one update per round, which keeps the computational cost manageable.

Lalam: The main result is a regret bound that handles both the uncertainty from heteroskedasticity and the corruption budget C.

Tom: That bound looks pretty solid—it's (d sqrt sum t g(tau t) mu t, + d squared g kappa+ d(g + kappa)C.

Jane: What this means in plain language is that if your rewards are messy, and someone is trying to mess with the data stream, you still get a predictable performance guarantee.

Lu: They established a corruption-robust confidence sequence using tools like a weighted likelihood supermartingale which was pretty novel for this setup.

Meng: The caveat I see is that the complexity of that analysis means applying it in practice needs careful tuning because those technical requirements are quite demanding to implement.

Tom: So the authors proved they can get near-optimal performance, matching lower bounds for both the standard uncertainty term and the corruption term dC.

Jane: It really shows how important it is to think about these combined factors—variance and attack budget—when you're building sequential decision systems in complex environments.

Lu: This kind of joint efficiency is what we need when we move beyond simple bandits into more realistic, messy applications where data quality isn't guaranteed.

Tom: It sets a new baseline for how robust these learners can be when they face both inherent noise and malicious interference simultaneously.