Corruption-Robust Variance-Aware Algorithms for Generalized Linear Bandits Under Heavy-Tailed Rewards
Abstract
Stochastic linear bandits have recently received significant attention in sequential decision-making. However, real-world challenges such as heavy-tailed noise, reward corruption, and nonlinear reward functions remain difficult to address. To tackle these difficulties, we propose GAdaOFUL, a novel algorithm that leverages adaptive Huber regression to achieve robustness in generalized linear models (GLMs), where rewards can be nonlinear functions of features. GAdaOFUL achieves a state-of-the-art variance-aware regret bound, scaling with the square root of the cumulative reward variance over time, plus an additional term proportional to the level of corruption. The algorithm adapts to problem complexity, yielding improved regret when the cumulative variance is small. Simulation results demonstrate the robustness and effectiveness of GAdaOFUL in practice. The code is available at \url{https://github.com/NeXAIS/GAdaOFUL}.
Cite
Text
Yu et al. "Corruption-Robust Variance-Aware Algorithms for Generalized Linear Bandits Under Heavy-Tailed Rewards." Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, 2025.Markdown
[Yu et al. "Corruption-Robust Variance-Aware Algorithms for Generalized Linear Bandits Under Heavy-Tailed Rewards." Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, 2025.](https://mlanthology.org/uai/2025/yu2025uai-corruptionrobust/)BibTeX
@inproceedings{yu2025uai-corruptionrobust,
title = {{Corruption-Robust Variance-Aware Algorithms for Generalized Linear Bandits Under Heavy-Tailed Rewards}},
author = {Yu, Qingyuan and Baek, Euijin and Li, Xiang and Sun, Qiang},
booktitle = {Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence},
year = {2025},
pages = {4826-4843},
volume = {286},
url = {https://mlanthology.org/uai/2025/yu2025uai-corruptionrobust/}
}