An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces
This work addresses a limitation in bandit theory for researchers, but it is incremental as it builds directly on existing frameworks.
The paper tackles the problem of analyzing the Bayesian regret of Thompson Sampling for bandit problems with infinite action spaces, extending prior information-theoretic frameworks to derive regret bounds that account for action space complexity, such as Lipschitz continuity.
This paper studies the Bayesian regret of the Thompson Sampling algorithm for bandit problems, building on the information-theoretic framework introduced by Russo and Van Roy (2015). Specifically, it extends the rate-distortion analysis of Dong and Van Roy (2018), which provides near-optimal bounds for linear bandits. A limitation of these results is the assumption of a finite action space. We address this by extending the analysis to settings with infinite and continuous action spaces. Additionally, we specialize our results to bandit problems with expected rewards that are Lipschitz continuous with respect to the action space, deriving a regret bound that explicitly accounts for the complexity of the action space.