Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewards
This work addresses theoretical guarantees for Thompson Sampling in contextual bandits, which is important for researchers in online learning and reinforcement learning, but it is incremental as it extends existing frameworks to more general reward distributions.
The paper tackles the problem of analyzing Thompson Sampling for contextual bandits with sub-Gaussian rewards, proving a comprehensive expected cumulative regret bound based on mutual information and introducing new bounds on the lifted information ratio that generalize prior results from binary to sub-Gaussian rewards, with explicit regret bounds provided for several special cases.
In this work, we study the performance of the Thompson Sampling algorithm for Contextual Bandit problems based on the framework introduced by Neu et al. and their concept of lifted information ratio. First, we prove a comprehensive bound on the Thompson Sampling expected cumulative regret that depends on the mutual information of the environment parameters and the history. Then, we introduce new bounds on the lifted information ratio that hold for sub-Gaussian rewards, thus generalizing the results from Neu et al. which analysis requires binary rewards. Finally, we provide explicit regret bounds for the special cases of unstructured bounded contextual bandits, structured bounded contextual bandits with Laplace likelihood, structured Bernoulli bandits, and bounded linear contextual bandits.