Regret Bounds for Generalized Linear Bandits under Parameter Drift

Abstract

Generalized Linear Bandits (GLBs) are powerful extensions to the Linear Bandit (LB) setting, broadening the benefits of reward parametrization beyond linearity. In this paper we study GLBs in non-stationary environments, characterized by a general metric of non-stationarity known as the variation-budget or \emph{parameter-drift}, denoted $B_T$. While previous attempts have been made to extend LB algorithms to this setting, they overlook a salient feature of GLBs which flaws their results. In this work, we introduce a new algorithm that addresses this difficulty. We prove that under a geometric assumption on the action set, our approach enjoys a $\tilde{\mathcal{O}}(B_T^{1/3}{T}^{2/3})$ regret bound. In the general case, we show that it suffers at most a $\tilde{\mathcal{O}}(B_T^{1/5}{T}^{4/5})$ regret. At the core of our contribution is a generalization of the projection step introduced in Filippi et al. (2010), adapted to the non-stationary nature of the problem. Our analysis sheds light on central mechanisms inherited from the setting by explicitly splitting the treatment of the learning and tracking aspects of the problem.

References in corpus (9)

• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Weighted Linear Bandits for Non-Stationary Environments
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• A Simple Approach for Non-stationary Linear Bandits
• An Information-Theoretic Analysis for Thompson Sampling with Many Actions
• Algorithms for Non-Stationary Generalized Linear Bandits
• Efficient Learning in Non-Stationary Linear Markov Decision Processes
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits

Cited by in corpus (1)

• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach