Thompson Sampling for Contextual Bandits with Linear Payoffs
This work addresses a foundational gap in bandit theory by offering the first theoretical analysis for contextual Thompson Sampling, which is incremental but crucial for understanding its performance in adversarial settings.
The paper tackles the problem of providing theoretical guarantees for Thompson Sampling in stochastic contextual bandits with linear payoffs under an adaptive adversary, achieving a high probability regret bound of ˜O(d^{3/2}\sqrt{T}) or ˜O(d\sqrt{T \log(N)}), which is the best among computationally efficient algorithms and close to the information-theoretic lower bound.
Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state-of-the-art methods. However, many questions regarding its theoretical performance remained open. In this paper, we design and analyze a generalization of Thompson Sampling algorithm for the stochastic contextual multi-armed bandit problem with linear payoff functions, when the contexts are provided by an adaptive adversary. This is among the most important and widely studied versions of the contextual bandits problem. We provide the first theoretical guarantees for the contextual version of Thompson Sampling. We prove a high probability regret bound of $\tilde{O}(d^{3/2}\sqrt{T})$ (or $\tilde{O}(d\sqrt{T \log(N)})$), which is the best regret bound achieved by any computationally efficient algorithm available for this problem in the current literature, and is within a factor of $\sqrt{d}$ (or $\sqrt{\log(N)}$) of the information-theoretic lower bound for this problem.