2023/10/28 by Bo Xue, Yimu Wang, Xue, Bo +7 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Age of Information Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2310.18701
openalex publication_date 2023/10/28 · openalex created_date 2023/11/01 · openalex updated_date 2026/07/28
This paper investigates the problem of generalized linear bandits with heavy-tailed rewards, whose (1+ε)-th moment is bounded for some ε∈ (0,1]. Although there exist methods for generalized linear bandits, most of them focus on bounded or sub-Gaussian rewards and are not well-suited for many real-world scenarios, such as financial markets and web-advertising. To address this issue, we propose two novel algorithms based on truncation and mean of medians. These algorithms achieve an almost optimal regret bound of \widetildeO(dT(1)/(1+ε)), where d is the dimension of contextual information and T is the time horizon. Our truncation-based algorithm supports online learning, distinguishing it from existing truncation-based approaches. Additionally, our mean-of-medians-based algorithm requires only O(log T) rewards and one estimator per epoch, making it more practical. Moreover, our algorithms improve the regret bounds by a logarithmic factor compared to existing algorithms when ε=1. Numerical experimental results confirm the merits of our algorithms.