Poster
Noise-Adaptive Thompson Sampling for Linear Contextual Bandits
Ruitu Xu · Yifei Min · Tianhao Wang
Great Hall & Hall B1+B2 (level 1) #1805
Abstract:
Linear contextual bandits represent a fundamental class of models with numerous real-world applications, and it is critical to develop algorithms that can effectively manage noise with unknown variance, ensuring provable guarantees for both worst-case constant-variance noise and deterministic reward scenarios. In this paper, we study linear contextual bandits with heteroscedastic noise and propose the first noise-adaptive Thompson sampling-style algorithm that achieves a variance-dependent regret upper bound of , where is the dimension of the context vectors and is the variance of the reward in round . This recovers the existing regret guarantee in the constant-variance regime and further improves to in the deterministic regime, thus achieving a smooth interpolation in between. Our approach utilizes a stratified sampling procedure to overcome the too-conservative optimism in the linear Thompson sampling algorithm for linear contextual bandits.
Chat is not available.