Thompson sampling#Upper-Confidence-Bound (UCB) Algorithms

Consider a set of contexts $\backslash mathcal\{X\}$, a set of actions $\backslash mathcal\{A\}$, and rewards in $\backslash mathbb\{R\}$. The aim of the player is to play actions under the various contexts, such as to maximize the cumulative rewards. Specifically, in each round, the player obtains a context $x\; \backslash in\; \backslash mathcal\{X\}$, plays an action $a\; \backslash in\; \backslash mathcal\{A\}$ and receives a reward $r\; \backslash in\; \backslash mathbb\{R\}$ following a distribution that depends on the context and the issued action.

The elements of Thompson sampling are as follows:{{rp|sec. 4}}

1. a likelihood function $P(r|\backslash theta,a,x)$;
2. a set $\backslash Theta$ of parameters $\backslash theta$ of the distribution of $r$;
3. a prior distribution $P(\backslash theta)$ on these parameters;
4. past observations triplets $\backslash mathcal\{D\}\; =\; \backslash \{(x;\; a;\; r)\backslash \}$;
5. a posterior distribution $P(\backslash theta|\backslash mathcal\{D\})\; \backslash propto\; P(\backslash mathcal\{D\}|\backslash theta)P(\backslash theta)$, where $P(\backslash mathcal\{D\}|\backslash theta)$ is the likelihood function.

Thompson sampling consists of playing the action $a^\backslash ast\; \backslash in\; \backslash mathcal\{A\}$ according to the probability that it maximizes the expected reward; action $a^\backslash ast$ is chosen with probability{{rp|Algorithm 4}}

:$\backslash int\; \backslash mathbb\{I\}\; \backslash left[\; \backslash mathbb\{E\}(r|a^\backslash ast,x,\backslash theta)\; =\; \backslash max\_\{a\text{'}\}\; \backslash mathbb\{E\}(r|a\text{'},x,\backslash theta)\; \backslash right]\; P(\backslash theta|\backslash mathcal\{D\})\; d\backslash theta,$

where $\backslash mathbb\{I\}$ is the indicator function.

In practice, the rule is implemented by sampling. In each round, parameters $\backslash theta^\backslash ast$ are sampled from the posterior $P(\backslash theta|\backslash mathcal\{D\})$,{{rp|7}} and an action $a^\backslash ast$ chosen that maximizes $\backslash mathbb\{E\}[r|\backslash theta^\backslash ast,a^\backslash ast,x]$, i.e. the expected reward given the sampled parameters, the action, and the current context. Conceptually, this means that the player instantiates their beliefs randomly in each round according to the posterior distribution, and then acts optimally according to them. In most practical applications, it is computationally onerous to maintain and sample from a posterior distribution over models. As such, Thompson sampling is often used in conjunction with approximate sampling techniques.{{rp|sec. 5}}

Thompson sampling was originally described by Thompson in 1933. It was subsequently rediscovered numerous times independently in the context of multi-armed bandit problems. A first proof of convergence for the bandit case has been shown in 1997. The first application to Markov decision processes was in 2000. A related approach (see Bayesian control rule) was published in 2010. In 2010 it was also shown that Thompson sampling is instantaneously self-correcting. Asymptotic convergence results for contextual bandits were published in 2011. Thompson Sampling has been widely used in many online learning problems including A/B testing in website design and online advertising, and accelerated learning in decentralized decision making. A Double Thompson Sampling (D-TS) algorithm has been proposed for dueling bandits, a variant of traditional MAB, where feedback comes in the form of pairwise comparison.

{{See also|Probability matching}}

Probability matching is a decision strategy in which predictions of class membership are proportional to the class base rates. Thus, if in the training set positive examples are observed 60% of the time, and negative examples are observed 40% of the time, the observer using a probability-matching strategy will predict (for unlabeled examples) a class label of "positive" on 60% of instances, and a class label of "negative" on 40% of instances.

A generalization of Thompson sampling to arbitrary dynamical environments and causal structures, known as Bayesian control rule, has been shown to be the optimal solution to the adaptive coding problem with actions and observations. In this formulation, an agent is conceptualized as a mixture over a set of behaviours. As the agent interacts with its environment, it learns the causal properties and adopts the behaviour that minimizes the relative entropy to the behaviour with the best prediction of the environment's behaviour. If these behaviours have been chosen according to the maximum expected utility principle, then the asymptotic behaviour of the Bayesian control rule matches the asymptotic behaviour of the perfectly rational agent.

The setup is as follows. Let $a\_1,\; a\_2,\; \backslash ldots,\; a\_T$ be the actions issued by an agent up to time $T$, and let $o\_1,\; o\_2,\; \backslash ldots,\; o\_T$ be the observations gathered by the agent up to time $T$. Then, the agent issues the action $a\_\{T+1\}$ with probability:

:$P(a\_\{T+1\}|\backslash hat\{a\}\_\{1:T\},\; o\_\{1:T\}),$

where the "hat"-notation $\backslash hat\{a\}\_t$ denotes the fact that $a\_t$ is a causal intervention (see Causality), and not an ordinary observation. If the agent holds beliefs $\backslash theta\; \backslash in\; \backslash Theta$ over its behaviors, then the Bayesian control rule becomes

:$P(a\_\{T+1\}|\backslash hat\{a\}\_\{1:T\},\; o\_\{1:T\})\; =\; \backslash int\_\{\backslash Theta\}\; P(a\_\{T+1\}|\backslash theta,\; \backslash hat\{a\}\_\{1:T\},\; o\_\{1:T\})\; P(\backslash theta|\backslash hat\{a\}\_\{1:T\},\; o\_\{1:T\})\; \backslash ,\; d\backslash theta$,

where $P(\backslash theta|\backslash hat\{a\}\_\{1:T\},\; o\_\{1:T\})$ is the posterior distribution over the parameter $\backslash theta$ given actions $a\_\{1:T\}$ and observations $o\_\{1:T\}$.

In practice, the Bayesian control amounts to sampling, at each time step, a parameter $\backslash theta^\backslash ast$ from the posterior distribution $P(\backslash theta|\backslash hat\{a\}\_\{1:T\},\; o\_\{1:T\})$, where the posterior distribution is computed using Bayes' rule by only considering the (causal) likelihoods of the observations $o\_1,\; o\_2,\; \backslash ldots,\; o\_T$ and ignoring the (causal) likelihoods of the actions $a\_1,\; a\_2,\; \backslash ldots,\; a\_T$, and then by sampling the action $a^\backslash ast\_\{T+1\}$ from the action distribution $P(a\_\{T+1\}|\backslash theta^\backslash ast,\backslash hat\{a\}\_\{1:T\},o\_\{1:T\})$.

Thompson sampling and upper-confidence bound algorithms share a fundamental property that underlies many of their theoretical guarantees. Roughly speaking, both algorithms allocate exploratory effort to actions that might be optimal and are in this sense "optimistic". Leveraging this property, one can translate regret bounds established for UCB algorithms to Bayesian regret bounds for Thompson sampling or unify regret analysis across both these algorithms and many classes of problems.

{{Reflist|refs=

Thompson, William R. [https://www.dropbox.com/s/yhn9prnr5bz0156/1933-thompson.pdf "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples"]. Biometrika, 25(3–4):285–294, 1933.

Thompson, W. R. (1935). On the theory of apportionment. American Journal of Mathematics, 57(2), 450-456.

J. Wyatt. Exploration and Inference in Learning from Reinforcement. Ph.D. thesis, Department of Artificial Intelligence, University of Edinburgh. March 1997.

Chapelle, Olivier, and Lihong Li. "An empirical evaluation of Thompson sampling." Advances in neural information processing systems. 2011.

http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling

B. C. May, B. C., N. Korda, A. Lee, and D. S. Leslie. "Optimistic Bayesian sampling in contextual-bandit problems". Technical report, Statistics Group, Department of Mathematics, University of Bristol, 2011.

P. A. Ortega and D. A. Braun. "A Minimum Relative Entropy Principle for Learning and Acting", Journal of Artificial Intelligence Research, 38, pages 475–511, 2010, http://arxiv.org/abs/0810.3605

M. J. A. Strens. "A Bayesian Framework for Reinforcement Learning", Proceedings of the Seventeenth International Conference on Machine Learning, Stanford University, California, June 29–July 2, 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1701

O.-C. Granmo. "Solving Two-Armed Bernoulli Bandit Problems Using a Bayesian Learning Automaton", International Journal of Intelligent Computing and Cybernetics, 3 (2), 2010, 207-234.

{{Cite journal | last1 = Granmo | first1 = O. C. | last2 = Glimsdal | first2 = S. | title = Accelerated Bayesian learning for decentralized two-armed bandit based decision making with applications to the Goore Game | doi = 10.1007/s10489-012-0346-z | journal = Applied Intelligence | volume = 38 | issue = 4 | pages = 479–488 | year = 2012 | hdl = 11250/137969 | s2cid = 8746483 | hdl-access = free }}

Ian Clarke. "Proportionate A/B testing", September 22nd, 2011, http://blog.locut.us/2011/09/22/proportionate-ab-testing/

{{citation

| arxiv = 1604.07101| last1 = Wu

| first1 = Huasen

| last2 = Liu

| first2 = Xin

| last3 = Srikant

| first3 = R

| title = Double Thompson Sampling for Dueling Bandits

| year = 2016

| bibcode= 2016arXiv160407101W}}

Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband and Zheng Wen (2018), "A Tutorial on Thompson Sampling", Foundations and Trends in Machine Learning: Vol. 11: No. 1, pp 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf

Daniel J. Russo and Benjamin Van Roy (2013), "Eluder Dimension and the Sample Complexity of Optimistic Exploration", Advances in Neural Information Processing Systems 26, pp. 2256-2264. https://proceedings.neurips.cc/paper/2013/file/41bfd20a38bb1b0bec75acf0845530a7-Paper.pdf

{{cite journal

| last1=Russo | first1=Daniel J.

| last2=Van Roy | first2=Benjamin

| title=Learning to Optimize Via Posterior Sampling

| journal=Mathematics of Operations Research

| volume=39

| issue=4

| pages=1221–1243

| date=2014

| doi=10.1287/moor.2014.0650| arxiv=1301.2609

}}

}}

Category:Artificial intelligence engineering

Category:Heuristic algorithms

Category:Sequential methods

Category:Sequential experiments