Thompson sampling is a popular way to choose among uncertain options. It draws a plausible value for each option from the current beliefs and picks the highest draw. It works well, but it does not know when the experiment ends. On the last day of a fixed-length A/B test it still explores exactly as much as it would with a year to go, even though anything learned on the final day can never be used. A large body of work tunes how widely Thompson sampling spreads its draws by multiplying the posterior variance by a constant. Other work makes the spread grow over time to guard against bad runs. Separately, the theory of finite-horizon indices shows that the right amount of exploration depends on how many rounds remain, and that it should fall to zero at the deadline. These two lines have not been joined into a randomized algorithm.
We propose to set Thompson sampling's sampling variance, arm by arm and round by round, so that its effective optimism matches the exploration bonus of the finite-horizon Gittins index. The Gittins index is a per-arm score whose exploration term depends on the arm's posterior variance and on the number of rounds left. The resulting sampler explores hard when much time remains and when an arm is still poorly understood. It becomes greedy smoothly as the deadline nears. Because it remains a random sampler, it keeps Thompson sampling's robustness to delayed and batched feedback. Through tempered posteriors it can also be used where the Gittins index itself has no tractable form or guarantee: Bernoulli rewards, and logistic or linear contextual models.
Core Claim
The central object is a variance multiplier $\lambda_{t,k}$ for arm $k$ at round $t$. It replaces the constant multiplier studied in An Empirical Evaluation of Thompson Sampling. Let $\sigma^2_{t,k}$ be the arm's posterior variance and $m = T - t$ the number of remaining rounds. Let $b(\sigma^2_{t,k}, m)$ be the closed-form approximation to the finite-horizon Gittins exploration bonus analyzed in Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits. Let $z_K$ be the upper Gaussian quantile at which a draw beats $K-1$ independent competitors with probability about $1/K$. We set
$$\lambda_{t,k} = \frac{b(\sigma^2_{t,k}, m)^2}{z_K^2\, \sigma^2_{t,k}},$$
and sample $X_{t,k} \sim \mathcal{N}(\hat\mu_{t,k}, \lambda_{t,k}\sigma^2_{t,k})$. In plain terms, the typical "winning" draw of each arm sits about one Gittins bonus above its mean. As in the variance-inflated sampler of Adaptive Variance Inflation in Thompson Sampling, the belief update itself stays standard. Only the action-selection step is changed.
The bonus depends on remaining time and posterior variance mainly through their interaction. Two consequences follow. A well-sampled arm stops receiving exploratory draws earlier than a barely-sampled one. And all arms collapse to their means as $m \to 0$. For non-Gaussian models we use the same schedule as a likelihood tempering exponent $\alpha_{t,k} = 1/\lambda_{t,k}$. This uses the fact, shown in Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling, that tempering by $\alpha$ scales the posterior covariance by roughly $1/\alpha$.
The claim is empirical and theoretical. Empirically, we expect a single untuned schedule to match or beat the best constant multiplier tuned separately for each horizon, across horizons from hundreds to tens of thousands of rounds. Theoretically, we aim to prove for Gaussian bandits an instance-dependent logarithmic regret bound of the same form as Lattimore's bound for the Gittins strategy, together with exact greediness at the final round.
How This Differs From Prior Work
Three papers supply the mechanism or motivate it.
- TS-VI (Adaptive Variance Inflation in Thompson Sampling) multiplies the variance by $t/(K n_{t,k})$, which grows with elapsed time. It therefore inflates under-sampled arms most at the very end of the experiment. Our schedule reverses that end-of-horizon behavior. TS-VI's safety argument (exponential regret tails) is a property we must check we do not lose.
- The finite-horizon Gittins analysis (Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits) gives us the target bonus and its roughly $\log^{3/2} m$ behavior. It is, however, a deterministic index proven only for Gaussian noise and priors. We borrow the bonus but not the deterministic selection.
- Tempered posteriors (Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling) carry the idea beyond Gaussians. That paper ties the exponent to dimension and keeps it fixed. It also proves a $d^{3/2}\sqrt{T}$ lower bound for inflation-based sampling. This constrains our linear-bandit ambitions: we do not expect horizon scheduling to close the $\sqrt d$ gap, only to cut late-horizon waste.
Two frequentist lines constrain the design.
- Fast and Regret Optimal Best Arm Identification (EOCP) inflates the upper-confidence bonus and then switches abruptly to committing on a lower bound. It reports more than 20% lower regret than vanilla UCB. This shows that stopping late exploration pays. - Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification and Bridging the gap between regret minimization and best arm identification show that fixed bonus multipliers trade regret against identifying the best arm, and that no one algorithm wins both.
Our schedule is a regret-oriented point. We will report where it lands on that trade-off rather than claim to escape it.
Research Program
Algorithm. We will implement the matched multiplier for Gaussian, Bernoulli (Beta-posterior, tempered), and logistic contextual Thompson sampling. In the contextual case the "arm variance" is the predictive variance of the action's score.
Theory. For Gaussian arms we will bound the number of suboptimal pulls. The argument follows Lattimore's regret decomposition. We replace the deterministic index comparison with a probability that a draw beats the optimal arm's draw, which the matched variance makes comparable to the index event.
Horizon misspecification. The Gittins index needs the exact horizon, so we will test what happens when the assumed horizon is off by a factor of two in either direction. We will also test a doubling-trick anytime variant. This addresses the open "anytime" problem noted for finite-horizon indices.
Behavioral side check. We will compare final-round behavior with the human data in A Behavioral Model for Exploration vs. Exploitation. There, nearly 30% of subjects still chose a non-leading arm in the final round. Our sampler predicts zero. This is a contrast for interpretation, not a target.
Baselines
Naive references: standard and greedy. The do-nothing references are standard Thompson sampling with unit multiplier and a pure greedy policy. On the Yahoo display-ads semi-synthetic task, An Empirical Evaluation of Thompson Sampling reports 5.00% regret for exploit-only and 4.14% for LinUCB. Beating standard Thompson sampling at every horizon is the minimum bar.
Tuned constant multiplier (strongest simple competitor). This is Thompson sampling with a constant variance multiplier, the strongest simple competitor because it is what practitioners actually do. On the same Yahoo ads task, An Empirical Evaluation of Thompson Sampling reports 3.72% regret for scaled sampling with parameter 0.5.
For fairness, the constant will be tuned by grid search on held-out seeds separately for each horizon and environment. Our schedule gets the same number of tuning runs, used only for a single global scale on $b$. Beating it means lower regret than the per-horizon-tuned constant on average across horizons with one shared setting. It also means no worse than within seed noise at that constant's own tuned horizon.
The Yahoo ads simulator was built from internal Yahoo data. If we cannot obtain it, we will rebuild an analog from public contextual data. In that case the 3.72% figure serves only as orientation, not as a directly comparable number.
Strongest existing horizon-aware or inflation methods. These are the approximate finite-horizon Gittins index (Regret Analysis of the Finite-Horizon Gittins Index Strategy), TS-VI (Adaptive Variance Inflation in Thompson Sampling), and EOCP (Fast and Regret Optimal Best Arm Identification). Each is run with its authors' recommended constants and the same tuning budget where it has free parameters.
The file gives only figures, not scalar regrets, for Gittins and TS-VI. We found no reported result on Lacuna for their numerical regret on these testbeds. EOCP's only reported number is the more-than-20% reduction relative to vanilla UCB. On the Gaussian testbed, matching the Gittins index within seed noise counts as success, since that index is the target we imitate. Beating it is expected only where randomization matters.
Best-arm identification metric. When scoring which arm is reported as best, we add BoBW-lil'UCB (Achieving the Pareto Frontier) across its tuning parameter. This places our method on the regret versus identification-error plane. The file gives no scalar result for it on MovieLens 25M or PKIS2.
Ablations that isolate the key ingredient. Three ablations each remove one part of the design:
- An elapsed-time schedule with the same functional form. This tests whether the direction of time is what matters.
- A shared multiplier $\lambda(m)$ applied to all arms, ignoring each arm's variance. This tests the per-arm interaction.
- Standard Thompson sampling followed by a hard switch to greedy at a tuned time. This tests smoothness against a discontinuity.
Why not just…?
Why not just tune a constant variance multiplier for your horizon? This is the most serious threat. An Empirical Evaluation of Thompson Sampling already shows that a single constant can deliver most of the gain on one task. A constant cannot both explore early and be greedy late, but it may be that, for a known horizon, the cost of that is small. The per-horizon-tuned constant baseline settles the question directly. If the matched schedule only matches it at each tuned horizon, the contribution shrinks to "one setting that works across horizons without retuning." We would report it that way rather than claim a regret advantage.
Why not just use the finite-horizon Gittins index directly? For Gaussian arms with immediate feedback, we expect it to be as good as our method, and we say so. Its limits lie elsewhere:
- Its guarantees and cheap approximation are Gaussian-only (Regret Analysis of the Finite-Horizon Gittins Index Strategy).
- It is deterministic. Under delayed feedback, deterministic rules repeatedly pick the same arm while waiting for rewards, which is exactly how UCB degraded in the 60-minute-delay news experiment of An Empirical Evaluation of Thompson Sampling.
The delayed and batched experiments and the Bernoulli and logistic experiments are designed to show where the index falls short. If it does not fall short there, the randomization argument fails.
Why not just explore, then commit, or use EOCP? Uniform explore-then-commit is dominated by adaptive inflated methods for more than two arms in Bridging the gap between regret minimization and best arm identification. EOCP is a stronger competitor: it achieves fast commitment but depends on gap estimates and discards runner-up information at the switch. The hard-switch ablation and the EOCP baseline together test whether smoothness buys anything. If the switch-to-greedy Thompson sampler matches our schedule, the per-arm Gittins matching is unnecessary decoration.
Proposed Experiments
Synthetic Gaussian bandits. Following Regret Analysis of the Finite-Horizon Gittins Index Strategy, we use 2, 5, and 10 arms and horizons from $10^2$ to $10^4$. This tests whether randomized matching recovers Gittins-level regret. We will also report the regret tail and the probability of negative cumulative reward used in Adaptive Variance Inflation in Thompson Sampling. This checks whether late compression revives the heavy tails that TS-VI removes. Laplace-noise and unequal-variance variants come from the same paper.
Bernoulli bandits. Bernoulli bandits matching the 2- and 3-arm, 100–2000-round settings of the QCARE study test the tempered extension where Gittins theory is absent.
Delayed and batched feedback. All of the above will be rerun with delays of several rounds to isolate the value of randomization.
Real-data recommendation and screening tasks. MovieLens 25M and PKIS2, as used in Achieving the Pareto Frontier, supply evaluation on real recommendation and drug-screening tasks. We report both cumulative regret and final best-arm error, placing every method on the trade-off frontier.
Contextual task. A logistic contextual ads task, either the original Yahoo semi-synthetic or our public analog, serves as the contextual test against the 3.72% scaled-sampling reference.
Decisive checks. Three results would decide the proposal:
- Against the per-horizon-tuned constant, averaged over horizons, with one shared setting.
- Against the Gittins index under delay and on Bernoulli rewards.
- Against the shared-multiplier and hard-switch ablations.
If all three come out flat, horizon-aware variance scaling is not worth its complexity, and that negative result would itself be worth reporting.
References
- An Empirical Evaluation of Thompson Sampling
- Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
- Adaptive Variance Inflation in Thompson Sampling: Efficiency, Safety, Robustness, and Beyond
- Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling
- Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms
- Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits
- Bridging the gap between regret minimization and best arm identification, with application to A/B tests
- A Behavioral Model for Exploration vs. Exploitation: Theoretical Framework and Experimental Evidence