Why Tie Handling Matters
In Thompson sampling, a draw is taken from each treatment arm’s posterior distribution of clinical utility, and the arm with the largest draw is selected. With continuous utility draws, exact ties are generally a probability-zero event. In computation, however, ties can appear because posterior draws are discrete, values are rounded, or numerical software stores values at finite precision. The rule for resolving them is part of the allocation procedure: it can change the probability assigned to each arm.
This is a question about choosing the maximum among posterior draws, not about deciding whether any treatment exceeds a clinical threshold. To state the rule precisely, let \(U_k\) denote the posterior draw of utility for arm \(k\), for \(k=1,\ldots,K\). For one joint draw, define the set of maximizers as the arms whose draws equal the largest draw.
The phrase “best-arm probability” therefore depends on the selection rule whenever tied maxima have positive probability. If ties occur with probability zero, different tie-breaking rules agree except on a probability-zero event and give the same theoretical probabilities.
When Continuous Draws Do Not Tie
For two arms \(i\) and \(j\), a tie occurs exactly when \(U_i-U_j=0\). A sufficient condition for a tie to have probability zero is that the difference \(U_i-U_j\) has a continuous distribution. For example, independent draws with continuous densities have a continuously distributed difference. A joint density for the utility vector also suffices: the equality \(U_i=U_j\) describes a lower-dimensional set that has probability zero under that density. With a finite number of arms, the probability of any tie is then zero, because a finite union of probability-zero events still has probability zero.
The key condition concerns pairwise differences, not merely the separate distributions of each arm. Continuous marginal distributions alone do not guarantee no ties. For instance, if \(U_1=U_2=Z\) for a continuously distributed random variable \(Z\), each marginal is continuous but the two draws tie with probability one. This can arise with strong posterior dependence. The relevant check is whether the joint posterior makes a pairwise difference nondegenerate and atomless at zero.
Worked Example: Continuous Normal Posterior Draws
Suppose two arms have independent posterior utility draws \(U_A\sim N(0.20,0.04^2)\) and \(U_B\sim N(0.18,0.03^2)\). Utility is measured in hypothetical utility units. The draws are independent and have continuous densities, so the difference also has a continuous distribution.
Derivation. The difference \(D=U_A-U_B\) has a normal distribution. Independence gives its mean as \(0.20-0.18=0.02\) and its variance as \(0.04^2+0.03^2=0.0016+0.0009=0.0025\). Thus \(D\sim N(0.02,0.0025)\), with standard deviation \(0.05\).
because a normal random variable assigns probability zero to any single point. Hence the posterior best-arm probabilities do not depend on how an exact tie would be resolved. This conclusion is about exact draws from the stated posterior, not about values rounded for display or stored by a finite-precision computer.
Defining Probabilities When Ties Are Possible
A generally symmetric rule is to choose uniformly from the tie set: conditional on the draws, each arm in \(T\) is selected with probability \(1/|T|\), and arms outside \(T\) receive probability zero. If \(q_k\) denotes arm \(k\)’s posterior best-arm allocation probability under this rule, then
Here \(\mathbf{1}\{k\in T\}\) equals one when arm \(k\) is among the maximizers and zero otherwise. This definition counts a unique maximum fully for its arm and shares a tied maximum equally among the tied arms. It follows directly that the probabilities sum to one: for every draw, the tie-set members each receive \(1/|T|\), so their total contribution is one.
Uniform selection is not the only valid rule. More generally, assign weights \(w_k(T)\) to arms in the tie set, with \(w_k(T)\geq 0\), \(w_k(T)=0\) for \(k\notin T\), and \(\sum_{k\in T}w_k(T)=1\). The corresponding probability is \(q_k=E[w_k(T)]\). A fixed priority rule is a special case: it gives all the tie’s selection weight to the highest-priority arm in \(T\). The rule must be stated because different valid rules can produce different probabilities.
Worked Example: Discrete Posterior Draws and Uniform Ties
Suppose a hypothetical posterior calculation for three arms, A, B, and C, produces the following eight equally weighted joint draws of utility. Utility values are discrete, and all three arms are on the same hypothetical utility scale.
| Draw | Arm A | Arm B | Arm C | Maximizing arm(s) |
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | A |
| 2 | 1 | 1 | 0 | A, B |
| 3 | 0 | 1 | 1 | B, C |
| 4 | 0 | 0 | 1 | C |
| 5 | 1 | 0 | 1 | A, C |
| 6 | 0 | 0 | 0 | A, B, C |
| 7 | 1 | 1 | 1 | A, B, C |
| 8 | 0 | 1 | 0 | B |
Under uniform tie-breaking, each unique maximum contributes one selection to its arm. Each two-arm tie contributes one-half to each tied arm, and each three-arm tie contributes one-third to each. Arm A’s total is \(1+1/2+1/2+1/3+1/3=8/3\) selections across the eight draws. Arm B’s total is \(1/2+1/2+1/3+1/3+1=8/3\); arm C’s is \(1/2+1+1/2+1/3+1/3=8/3\).
These are exact probabilities for this hypothetical eight-point, equally weighted posterior distribution. If instead a fixed priority A over B over C were used, the selected-arm counts would be 5 for A, 2 for B, and 1 for C, giving probabilities \(5/8\), \(2/8\), and \(1/8\). The draw distribution is unchanged; the allocation probabilities differ because the tie rule differs.
Rounding and Finite-Precision Ties
A posterior draw may be continuous in the statistical model but tied after its numerical representation is altered. Rounding maps a range of distinct values to the same displayed value. Finite-precision computation can also represent nearby values identically. In either case, blindly treating the stored values as exact draws changes the rule being implemented.
If the intended algorithm compares unrounded numerical draws, retain as much precision as is practically available and compare those draws directly. If the algorithm intentionally rounds before choosing the maximum, then the induced ties are part of its definition and must be resolved by a stated rule. A tolerance-based rule also changes the comparison: it treats values within a chosen distance as tied, even if one is larger. The tolerance and tie rule should therefore be prespecified and reported rather than selected after seeing which arms benefit.
Worked Example: Rounded Draws Create Apparent Ties
Consider five hypothetical independent Monte Carlo draw pairs for arms A and B. The unrounded utility values are shown to four decimal places; for this example, suppose an implementation rounds each value to two decimal places before selecting an arm. Utility is in hypothetical utility units.
| Draw | Unrounded A | Unrounded B | After rounding A, B | Selection under uniform ties |
|---|---|---|---|---|
| 1 | 0.8124 | 0.8116 | 0.81, 0.81 | Half to each |
| 2 | 0.7640 | 0.7510 | 0.76, 0.75 | A |
| 3 | 0.7020 | 0.7090 | 0.70, 0.71 | B |
| 4 | 0.6500 | 0.6490 | 0.65, 0.65 | Half to each |
| 5 | 0.6200 | 0.6000 | 0.62, 0.60 | A |
There are two rounded ties. Arm A receives \(1/2+1+0+1/2+1=3\) selections across five draws; arm B receives \(1/2+0+1+1/2+0=2\). The estimated probabilities under the rounded-and-uniform rule are therefore \(\hat q_A=3/5=0.60\) and \(\hat q_B=2/5=0.40\). If ties were instead always assigned to A, its estimated probability would be \(4/5=0.80\). If the unrounded values were compared, A would win draws 1, 2, and 5, while B would win draws 3 and 4, giving \(3/5\) and \(2/5\) for these five draws. The agreement in this particular example is incidental: in draw 4, rounding reverses the unrounded winner, while in draw 1 it creates a tie.
The calculation illustrates why the implementation must record whether rounding happens before comparison. These five Monte Carlo draws illustrate the arithmetic; they do not establish the exact posterior probabilities for any broader model.
Diagnostics, Alternatives, and Limitations
When ties appear unexpectedly, first locate where they enter the computation. Check whether the posterior itself is discrete, whether the stored draws have been rounded, and whether the numerical representation has limited precision. Compare the number of ties using stored values with the number obtained at higher precision, if available. For correlated posteriors, inspect whether pairwise differences can be degenerate or have a point mass at zero. A large tie frequency in a model thought to have continuous, nondegenerate differences is a useful warning to check the implementation and the posterior dependence structure.
The main alternatives express different allocation policies:
| Rule | How a tied maximum is resolved | Implication |
|---|---|---|
| Uniform random | Choose each tied arm with equal probability | Does not privilege arm labels within a tie; adds randomization. |
| Fixed priority | Choose the highest-priority tied arm | Reproducible, but can favor an arm because of its assigned order. |
| Specified weighted rule | Choose tied arms using prespecified weights summing to one | Allows a deliberate policy, but weights affect allocation probabilities. |
| Compare unrounded values | Use the most precise draws available before resolving exact ties | Often appropriate for continuous models, but cannot remove genuine ties in discrete draws. |
Uniform random tie-breaking is symmetric within a tie, but it does not imply equal overall best-arm probabilities: arms can differ in how often they are uniquely maximal or included in a tie. A deterministic order can be useful for reproducibility, but the order is not statistically neutral when ties occur. A custom weighted rule can be valid if it is explicit and its probabilities sum to one, but it represents a different allocation policy.
No rule makes a tie disappear without changing what “select the best arm” means for that draw. In particular, silently picking the first maximum in a software array is a fixed-priority rule whether or not that was intended. A small tolerance may also convert close but unequal draws into ties, and its effect can depend on the utility scale. For a clinical implementation, document the comparison precision, the tie definition, and the selection rule. The resulting best-arm probabilities describe that complete procedure, not a rule-independent property when ties have positive probability.
Check Your Understanding
Answer each question using the definitions and rules above. Brief solutions follow the questions.
- For two independent continuous posterior utility draws, why does the probability of an exact tie equal zero?
- Can continuous marginal distributions guarantee that two posterior draws never tie? Give a counterexample.
- In one equally weighted posterior draw, four arms tie for the maximum. What contribution does each receive under uniform tie-breaking?
- Three equally weighted draws have unique winners A and B on the first two draws, and a tie between B and C on the third. Find the uniform-tie estimated best-arm probabilities.
- Why can a fixed priority rule produce different best-arm probabilities from uniform tie-breaking?
Solutions. (1) The difference of independent continuous draws has a continuous distribution, so it assigns probability zero to the single value zero. (2) No. If \(U_1=U_2=Z\) for a continuous random variable \(Z\), both marginals are continuous but the draws tie on every realization. (3) Each tied arm receives \(1/4\) of that draw’s selection weight. (4) A receives \(1/3\); B receives \(1/3+1/6=1/2\); C receives \(1/6\). These sum to one. (5) A fixed priority assigns all tie weight to one arm, while uniform tie-breaking shares it; when ties have positive probability, these rules allocate different total probability to arms in the tie set.