Abstract

This paper studies the Bayesian regret of the Thompson Sampling algorithm forbandit problems, building on the information-theoretic framework introduced byRusso and Van Roy (2015). Specifically, it extends the rate-distortion analysisof Dong and Van Roy (2018), which provides near-optimal bounds for linearbandits. A limitation of these results is the assumption of a finite actionspace. We address this by extending the analysis to settings with infinite andcontinuous action spaces. Additionally, we specialize our results to banditproblems with expected rewards that are Lipschitz continuous with respect tothe action space, deriving a regret bound that explicitly accounts for thecomplexity of the action space.

 

Quick Read (beta)