A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions
Not on the map. Why?
Abstract (arXiv)
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 tildeOleft( d √sumt g(τt) dotμt,star + d2 gmax kappa + d (gmax + kappa) 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) = σt2 for heteroskedastic linear bandits, g(τt) = 1 for Bernoulli and Poisson), gmax = maxt ∈ [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 tildeOmega(d √sumt g(τt) dotμ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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 57 of its 95 references that are in the map. First posted on arXiv 11 Feb 2026.
Builds on
57 of 95 references.
References · 57
- 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
- 2024Provably Robust DPO: Aligning Language Models with Noisy Feedbackcited by 133
- 2018Stochastic bandits robust to adversarial corruptionscited by 118
- 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
- 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
- 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 113
- 2020Naive Exploration is Optimal for Online LQRcited by 111
- 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
- 2021Adapting to Misspecification in Contextual Banditscited by 81
- 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
- 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
38 more
- 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 56
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
- 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
- 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
- 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
- 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
- 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
- 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
- 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
- 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
- 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
- 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
- 2023Foundations of Reinforcement Learning and Interactive Decision Makingcited by 33
- 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
- 2023RLHFPoison: Reward Poisoning Attack for Reinforcement Learning with Human Feedback in Large Language Modelscited by 32
- 2020Self-Concordant Analysis of Generalized Linear Bandits with Forgettingcited by 29
- 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
- 2015Online Stochastic Linear Optimization under One-bit Feedbackcited by 26
- 2024Robust Reinforcement Learning from Corrupted Human Feedbackcited by 25
- 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
- 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
- 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
- 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
- 2024Nearly Minimax Optimal Regret for Multinomial Logistic Banditcited by 20
- 2024ROPO: Robust Preference Optimization for Large Language Modelscited by 16
- 2025Generalized Linear Bandits: Almost Optimal Regret with One-Pass Updatecited by 16
- 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
- 2025Improved Online Confidence Bounds for Multinomial Logistic Banditscited by 14
- 2020Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attackcited by 13
- 2023Likelihood Ratio Confidence Sets for Sequential Decision Makingcited by 10
- 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
- 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
- 2025Confidence Sequences for Generalized Linear Models via Regret Analysiscited by 9
- 2024Almost Free: Self-concordance in Natural Exponential Families and an Application to Banditscited by 8
- 2025A Unified Theoretical Analysis of Private and Robust Offline Alignment: from RLHF to DPOcited by 8
- 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
- 2025Confidence Estimation via Sequential Likelihood Mixingcited by 6
- 2022Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Banditscited by 5
50 most cited of 57 All 57 (JSON)
Built on by
Citing papers per year: 2026: 1.
1 paper.