Deriving the Thompson Sampling Allocation Identity

Why the Allocation Identity Matters

Thompson sampling is often described as drawing a plausible response parameter for each treatment and assigning the next participant to the treatment with the largest draw. That operational rule has a precise probability interpretation: conditional on the trial information so far, a treatment is selected as often as its posterior probability of being best. The equality is not an approximation or a rule based on posterior means. It follows from using the posterior distribution both to define “best” and to generate the trial’s allocation draw.

This identity makes posterior best-arm probabilities directly relevant to allocation. It also clarifies the assumptions behind the procedure: the posterior draws must represent the appropriate joint uncertainty across treatments, the outcome direction must be specified, and ties must be treated consistently.

Set-Up and Formal Statement

Suppose a trial has \(K\) treatments, indexed by \(i=1,\ldots,K\). Let \(\theta_i\) be the response parameter for treatment \(i\), with larger values defined as more desirable. Let \(\mathcal H\) denote the observed trial history at the point when the next participant is to be assigned. All probabilities below are conditional on this history.

Definition: The posterior probability that treatment \(i\) is uniquely best is \(q_i(\mathcal H)=P(\theta_i>\theta_j\text{ for every }j\ne i\mid\mathcal H)\). Under Thompson sampling, draw a vector \((\theta_1^*,\ldots,\theta_K^*)\) from the posterior distribution of \((\theta_1,\ldots,\theta_K)\) given \(\mathcal H\), then assign the participant to an arm whose draw is largest. If the posterior probability of any tie for the maximum is zero, the conditional probability of assigning to treatment \(i\) is exactly \(q_i(\mathcal H)\).

A common trial model has independent arm-specific posteriors given \(\mathcal H\). In that case, drawing one value independently from each arm’s posterior is a draw from the joint posterior, so the identity applies. More generally, it applies when the parameter vector is sampled from its full joint posterior, including any dependence. Independently sampling marginal posteriors is not generally equivalent to a joint posterior draw.

For discrete or otherwise tie-prone posteriors, “is best” and “is selected” require a tie convention. If a tie for the largest sampled value is broken uniformly at random, the matching posterior quantity is the probability that arm \(i\) receives that same randomized tie-break when the parameter vector is drawn from the posterior. The probability \(P(\theta_i\geq\theta_j\text{ for all }j\mid\mathcal H)\) is not, by itself, an allocation probability when several arms can tie: those nonexclusive events can overlap.

Deriving the Identity

First consider independent, continuous posterior distributions. Write \(f_i(x)\) for the posterior density of \(\theta_i\) and \(F_i(x)=P(\theta_i\leq x\mid\mathcal H)\) for its posterior cumulative distribution function. Conditional on \(\theta_i=x\), each other arm \(j\) has probability \(F_j(x)\) of drawing below \(x\). Independence means these events multiply. Integrating over possible values of \(\theta_i\) gives the chance that arm \(i\)’s draw exceeds all the others:

P\!\left(\theta_i^*>\theta_j^*\text{ for every }j\ne i\mid\mathcal H\right) =\int_{-\infty}^{\infty} f_i(x)\prod_{j\ne i}F_j(x)\,dx.

The posterior best-arm probability has exactly the same expression. To see this, condition on the posterior value \(\theta_i=x\). Given that value, arm \(i\) is uniquely best precisely when every other parameter is below \(x\). Posterior independence again gives the product of cumulative probabilities, and integrating over \(x\) gives the same integral. Thus the probability of assignment by posterior sampling equals \(q_i(\mathcal H)\).

There is also a direct argument that does not require independence. Let \(\boldsymbol{\theta}^*\) be one draw from the joint posterior. By construction, its distribution conditional on \(\mathcal H\) is the same as the posterior distribution of \(\boldsymbol{\theta}\). Therefore, for any event \(B\) defined by the parameter vector, \(P(\boldsymbol{\theta}^*\in B\mid\mathcal H)=P(\boldsymbol{\theta}\in B\mid\mathcal H)\). Take \(B\) to be the event that arm \(i\) is uniquely largest. Selecting the largest component of \(\boldsymbol{\theta}^*\) selects \(i\) exactly on this event. This proves the identity for a joint posterior draw whenever ties have probability zero.

Worked Example: Two Uniform Posterior Distributions

Suppose, hypothetically, that conditional on the current trial history, \(\theta_1\sim\text{Uniform}(0,1)\) and \(\theta_2\sim\text{Uniform}(0,0.5)\), independently. Larger response rates are preferred. These distributions are continuous, independent, and have zero probability of a tie, so the identity applies.

For \(0\leq x\leq 0.5\), the cumulative distribution function of \(\theta_2\) is \(F_2(x)=2x\); for \(0.5<x\leq1\), \(F_2(x)=1\). The density of \(\theta_1\) is 1 on \([0,1]\). Consequently,

P(\theta_1>\theta_2\mid\mathcal H) =\int_0^{0.5}2x\,dx+\int_{0.5}^{1}1\,dx =\left[x^2\right]_0^{0.5}+\left[x\right]_{0.5}^{1} =0.25+0.5=0.75.

The posterior probability that treatment 1 is best is \(0.75\), and Thompson sampling assigns the next participant to treatment 1 with probability \(0.75\). Since ties have probability zero, treatment 2 is best with probability \(1-0.75=0.25\), and it is selected with the same probability.

Worked Example: Three Arms and the Full Allocation Distribution

Consider hypothetical independent posteriors \(\theta_1\sim\text{Uniform}(0,1)\), \(\theta_2\sim\text{Uniform}(0,0.5)\), and \(\theta_3\sim\text{Uniform}(0,0.25)\). Again, larger values are better. All three distributions are continuous, so there are no posterior ties with positive probability.

For arm 1, the integrand is its density times the probabilities that arms 2 and 3 are below \(x\). On \(0\leq x\leq0.25\), those cumulative probabilities are \(2x\) and \(4x\). On \(0.25<x\leq0.5\), arm 3’s cumulative probability is 1, while arm 2’s is \(2x\). Above 0.5, both are 1. Thus,

\begin{aligned} P(\theta_1\text{ is best}\mid\mathcal H) &=\int_0^{0.25}8x^2\,dx+\int_{0.25}^{0.5}2x\,dx+\int_{0.5}^{1}1\,dx\\ &=\frac{8(0.25)^3}{3}+\left[(x^2)\right]_{0.25}^{0.5}+0.5\\ &=\frac{1}{24}+0.1875+0.5 =\frac{35}{48}\approx0.7292. \end{aligned}

For arm 2, its density is 2 on \([0,0.5]\). Arm 1’s cumulative probability is \(x\), and arm 3’s is \(4x\) up to 0.25 and 1 thereafter. Therefore,

\begin{aligned} P(\theta_2\text{ is best}\mid\mathcal H) &=\int_0^{0.25}8x^2\,dx+\int_{0.25}^{0.5}2x\,dx\\ &=\frac{1}{24}+0.1875 =\frac{11}{48}\approx0.2292. \end{aligned}

For arm 3, its density is 4 on \([0,0.25]\). The probabilities that arms 1 and 2 are below \(x\) are \(x\) and \(2x\), respectively. Hence,

P(\theta_3\text{ is best}\mid\mathcal H) =\int_0^{0.25}8x^2\,dx =\frac{8(0.25)^3}{3} =\frac{1}{24}\approx0.04167.

The three probabilities sum to \(35/48+11/48+1/24=35/48+11/48+2/48=1\), as they must when exactly one arm is best. The identity says that Thompson sampling’s allocation probabilities are approximately \(0.7292\), \(0.2292\), and \(0.04167\) for arms 1, 2, and 3, respectively.

What the Assumptions Do—and Do Not—Allow

The identity is about a probability conditional on the current history, not a statement that the selected treatment will produce the best outcome for the participant. It concerns uncertainty about the arm-specific response parameters under the specified model. The posterior must be based on the trial data and model being used, and the parameter ordering must match the trial objective. If smaller values represent better outcomes, such as an adverse-event rate, the rule must select the smallest draw or the parameter must be redefined so that larger is better.

Independence is a sufficient condition for independently drawing one parameter from each marginal posterior to produce a valid joint posterior draw. It is not necessary if the algorithm instead draws the entire vector jointly from the posterior. When posterior dependence exists but marginal draws are sampled independently, the draw vector has the wrong joint distribution; the equality with the joint posterior best-arm probability can fail.

The equality is also conditional on the posterior state used for allocation. If the data are updated, the posterior probabilities and allocation probabilities may change. The identity does not say that allocation proportions across a completed trial equal one fixed best-arm probability: the conditional probabilities can vary as the history changes.

Comparison, Diagnostics, and Limitations

Allocation rule	How it chooses an arm	Relation to posterior best probability
Thompson sampling	Draws parameters from the posterior and selects the largest draw	Its conditional selection probability equals the posterior probability of being best, under the stated draw and tie conditions
Greedy plug-in rule	Selects the arm with the largest posterior mean	Usually assigns all probability to one arm; it does not generally allocate in proportion to best-arm probabilities
Uniform random allocation	Selects each arm with the same probability	Matches best-arm probabilities only when those probabilities are equal

Several checks can reveal an implementation or interpretation problem. Under continuous posteriors with a unique maximum almost surely, the calculated best-arm probabilities should sum to 1, and so should the induced allocation probabilities. If these sums differ materially, investigate numerical integration, omitted arms, or inconsistent conditioning. Check that the posterior draws are generated from the intended joint distribution and that the code selects the correct extreme for the outcome direction. For discrete posteriors, verify that both the reported best-arm probabilities and the implemented assignment rule use the same tie convention.

A practical limitation is that the identity does not make posterior best-arm probabilities easy to calculate. It establishes that the sampling rule has the desired interpretation; obtaining numerical values may still require integration or computation. Nor does the identity certify that the outcome model, prior, or treatment objective is appropriate. If those are unsuitable, the algorithm can faithfully implement probabilities that are not scientifically useful.

Common mistake: “Treatment 1 has the largest posterior mean, so Thompson sampling selects it with probability one.” That is the greedy plug-in rule, not the identity. Thompson sampling selects treatment 1 with probability equal to the posterior probability that it is best; another treatment can still be selected when its posterior draw exceeds treatment 1’s draw.

Key takeaway: A posterior draw is a random parameter vector with the same conditional distribution as the unknown parameter vector. Selecting its largest component therefore selects each uniquely best arm with probability equal to that arm’s posterior probability of being best—provided the draw preserves the relevant joint posterior and the tie rule is aligned.

Worked Example: Why Independent Marginal Draws Can Fail

Suppose, hypothetically, the joint posterior assigns probability \(0.5\) to \((\theta_1,\theta_2)=(0.9,0.8)\) and probability \(0.5\) to \((\theta_1,\theta_2)=(0.1,0.2)\). There are no ties, and arm 1 is best in both possible posterior states. Its joint posterior best-arm probability is therefore \(1\). A joint posterior draw always selects arm 1.

Now instead draw independently from the two marginal posteriors. Each marginal takes its high value with probability \(0.5\) and its low value with probability \(0.5\). The four combinations each have probability \(0.25\). Arm 1 wins in \((0.9,0.8)\) and \((0.9,0.2)\), but loses in \((0.1,0.8)\) and \((0.1,0.2)\). Its independent-marginal-draw selection probability is \(0.25+0.25=0.5\), not 1. The discrepancy occurs because independent marginal draws destroy the dependence in the joint posterior.

Check Your Understanding

Answer each question using the conditional-on-history interpretation.

For two independent, continuous arm posteriors, what integral gives the probability that arm \(i\) is selected?
Three continuous posterior best-arm probabilities are \(0.52\), \(0.31\), and \(0.17\). What are the corresponding Thompson sampling allocation probabilities?
Why does a posterior tie require an explicit tie rule?
If posterior parameters are dependent, when does the allocation identity still hold?

Solutions. (1) It is \(\int f_i(x)\prod_{j\ne i}F_j(x)\,dx\), because conditional on arm \(i\)’s draw being \(x\), every other independent draw must be below \(x\). (2) They are \(0.52\), \(0.31\), and \(0.17\), respectively, since each arm’s selection probability equals its posterior probability of being uniquely best when ties have probability zero. (3) Tied arms do not have a unique maximum, and events defined by “at least as large as every other arm” can overlap. The reported probability must match how the allocation actually breaks ties. (4) It holds if the algorithm draws the full parameter vector from the joint posterior and applies the same best-arm or tie-breaking rule; independent marginal draws need not preserve the joint posterior.