Thompson Sampling for Contextual Bandits with Linear Payoffs

By Shipra Agrawal, Navin Goyal. 2012

1,155 citations recorded by the source corpus.

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 version of the contextual bandits problem. We prove a high probability regret bound of O(d2/e√T1+e) in time T for any 0 < e < 1, where d is the dimension of each context vector and e is a parameter used by the algorithm. Our results provide the first theoretical guarantees for the contextual version of Thompson Sampling, and are close to the lower bound of Ω(d√T) for this problem. This essentially solves a COLT open problem of Chapelle and Li [COLT 2012].

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “Though it was introduced in 1933 [150], TS has attracted renewed interest in the multiarmed bandit community, producing empirical evaluations [38], [135] as well as theoretical results [2], [85], [127].”
Balanced Linear Contextual Bandits (2018, methodology): “2010) and LinTS (Agrawal and Goyal 2013), and we propose two new algorithms, balanced linear UCB (BLUCB) and balanced linear Thompson sampling (BLTS).”
Estimation Considerations in Contextual Bandits (2017, methodology): “BLTS and BLUCB build on linear contextual bandits LinTS [6] and LinUCB [45] respectively.”
Learning to Learn for Global Optimization of Black Box Functions (2016, neutral): “Here again we encounter a huge variety of strategies, including Thompson sampling [Thompson, 1933, Scott, 2010, Chapelle and Li, 2011, Agrawal and Goyal, 2013], information gain [Villemonteix et al., 2009, Hennig and Schuler, 2012, Russo and Van Roy, 2014, Shahriari et al., 2014, Hern ´…”
Learning to Optimize via Posterior Sampling (2013, background): “This matches what is implied by the analysis of Agrawal and Goyal [5].”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, neutral): “Our results suggest this method has great potential in reinforcement learning as well.”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, background): “This approach does not increase the computation cost of DDQN, since the last layer has a negligible fraction of the model parameters and it is a nice and direct extension of TS of contextual linear bandits [46], [47].”
A Tutorial on Thompson Sampling (2017, background): “The ﬁrst regret bounds for such problems were established by [40] for linear contextual bandits and by [41, 42] for an extremely general class of bandit models.”
Deep Exploration via Randomized Value Functions (2017, background): “Further, the theory suggests that “well-designed” upper-confidence-bound-based approaches, which appropriately couple uncertainties across state-action pairs, but are often computationally intractable, are similarly near-optimal (statistically) and competitive with Thompson sampling in such…”
Thompson Sampling for Learning Parameterized Markov Decision Processes (2014, background): “Related Work & Future Directions A line of recent work (Agrawal and Goyal, 2012; Kaufmann et al., 2012; Korda et al., 2013; Agrawal and Goyal, 2013; Gopalan et al., 2014) has demonstrated that Thompson sampling enjoys nearoptimal regret guarantees for multi-armed bandits – a widely studied subclass ”
Contextual Bandits with Latent Confounders: An NMF Approach (2016, background): “Contextual bandits with linear payoff functions have been analyzed in [2, 12] in the adversarial setting, while in [1] it has been analyzed in the stochastic setting.”
Further Optimal Regret Bounds for Thompson Sampling (2012, methodology): “Our technique easily extends to distributions other than Beta distribution, and it also extends to the more general contextual bandits setting [2].”
Convex Optimization: Algorithms and Complexity (2015, positive): “On the theoretical side, Agrawal and Goyal [Agrawal and Goyal, 2013b] study contextual bandits with rewards that linearly depend on the context, and show a frequentist regret bound of Õ ( d2 √ T 1+ ) , where d is the dimension of the context vector, and is an algorithmparameter that can be chosen…”
Learning to Learn without Gradient Descent by Gradient Descent (2016, methodology): “zed at each step so as to tradeoff exploration and exploitation. Here again we encounter a huge variety of strategies, including Thompson sampling [Thompson, 1933, Scott, 2010, Chapelle and Li, 2011, Agrawal and Goyal, 2013], information gain [Villemonteix et al., 2009, Hennig and Schuler, 2012, Rus”
Efficient Thompson Sampling for Online Matrix-Factorization Recommendation (2015, background): “While many solutions have been proposed for bandit problems, in the last ﬁve years or so, there has been a renewed interest in the use of Thompson sampling (TS) which was originally proposed in 1933 [3, 4].”
Optimistic posterior sampling for reinforcement learning: worst-case regret bounds (2022, background): “…Long Beach, CA, USA. attractive empirical performance [Chapelle and Li, 2011, Kaufmann et al., 2012], as well as provably optimal performance bounds that have been recently obtained for many variations of MAB [Agrawal and Goyal, 2012, 2013b,a, Russo and Van Roy, 2015, 2014, Bubeck and Liu, 2013].”
On Kernelized Multi-armed Bandits (2017, methodology): “These assumptions are required to make the regret bounds scale-free and are standard in the literature (Agrawal and Goyal, 2013).”
Transferable Contextual Bandit for Cross-Domain Recommendation (2018, methodology): “Under the same assumption, Agrawal and Goyal proposed a Thompson Sampling style method (Agrawal and Goyal 2013).”
An Information-Theoretic Analysis of Thompson Sampling (2014, background): “To our knowledge, Agrawal and Goyal [4] are the only other authors to have studied the application of Thompson sampling to linear bandit problems.”