Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits

We study the problem of online generalized linear regression in the stochastic setting, where the label is generated from a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. More specifically, for σ-sub-Gaussian label noise, our analysis provides a regret upper bound of O(σ 2 d log T ) + o(log T ), where d is the dimension of the input vector, T is the total number of rounds. We also prove a Ω(σ 2 d log(T /d)) lower bound for stochastic online linear regression, which indicates that our upper bound is nearly optimal. In addition, we extend our analysis to a more refined Bernstein noise condition. As an application, we study generalized linear bandits with heteroscedastic noise and propose an algorithm based on FTRL to achieve the first variance-aware regret bound. * This is a revised version of the original manuscript titled 'Bandit learning with general function classes: Heteroscedastic noise and variance-dependent regret bounds'. In this updated version, we have added new theoretical results on the FTRL algorithm and mainly focused on stochastic online regression. Refer to https: //arxiv.org/abs/2202.13603v1 for the previous version, which contains more results on heteroscedastic bandits.