Thompson Sampling Is 2-Competitive for Mistakes

Gregory Valiant; Mark Sellke

Thompson Sampling Is 2-Competitive for Mistakes

T0 review · 2 major / 0 minor · reviewed 2026-07-15 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Thompson sampling makes at most twice as many expected mistakes as any other policy in Bayesian bandits with independent restful arms.

desk verdict Abstract-only: clean resolution of the Guha–Munagala 2-competitive conjecture for Thompson sampling under independence and restfulness, but the proof itself is not inspectable. read the letter →

arxiv 2607.12389 v1 pith:FUJOIZLS submitted 2026-07-14 stat.ML cs.LG

Mark Sellke , Gregory Valiant This is my paper

classification stat.MLcs.LG

keywords ThompsonsamplingBayesianbanditscompetitiveanalysismistakesrestfularmsindependentlatentprocessesmulti-armed

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that Thompson sampling is 2-competitive for expected mistakes in Bayesian bandit models. Under the conditions that latent arm processes are independent and each arm evolves only when played, Thompson sampling selects a suboptimal arm at most twice as often, in expectation, as any competing policy. The guarantee holds for any nonincreasing sequence of round weights, covering fixed horizons and geometric discounting. For the classical stochastic bandit where the best arm is defined by mean reward, the result confirms a 2014 conjecture of Guha and Munagala; the factor of 2 is already known to be tight. A sympathetic reader cares because Thompson sampling is a simple, widely used Bayesian heuristic, and a universal factor-2 bound on mistakes places it among the most competitive policies one can hope for without solving the full dynamic program.

What carries the argument

The competitive analysis of Thompson sampling under independence and restfulness of latent arm processes, which yields a universal factor-2 bound on expected weighted mistakes relative to any alternative policy.

What would settle it

Exhibit a Bayesian bandit instance with independent restful arms, a nonincreasing weight sequence, and a policy whose expected weighted mistakes are strictly less than half those of Thompson sampling; or show that the same factor-2 bound continues to hold after dropping independence or restfulness.

Watch

Extended reading notes

Core claim

In Bayesian bandits whose latent arm processes are independent and restful (each arm’s state evolves only when that arm is pulled), Thompson sampling incurs at most twice the expected number of weighted mistakes of any other policy, under every nonincreasing sequence of round weights. When the best arm is the one with highest mean reward, this settles the Guha–Munagala conjecture and the constant 2 is optimal.

Load-bearing premise

The latent processes of distinct arms must be independent, and each arm’s state may change only when that arm is played; if either condition fails the factor-2 argument does not apply.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The one thing you need to know is that this abstract claims a clean resolution of the Guha–Munagala 2014 conjecture: Thompson sampling is 2-competitive for expected mistakes against any policy, for Bayesian bandits with independent restful arms, and the factor 2 is tight. That is a real result if the proof holds.

What is new is the competitive-ratio statement itself. The setting is standard—latent processes independent, each arm evolves only when played—and the bound is said to hold for any nonincreasing round weights, so it covers fixed horizon and geometric discounting in one go. For ordinary stochastic bandits with the usual mean-reward definition of the best arm, that is exactly the conjecture. No free parameters, no circular definitions; pure comparison of expected mistakes.

The soft spot is purely logistical: we only have the abstract. Independence and restfulness are the natural load-bearing assumptions, and the abstract is explicit that the argument needs them. Without the lemmas we cannot check whether the coupling or information argument is tight only for certain priors, or whether extra regularity on the prior support sneaks in. That is not a manufactured flaw; it is simply that soundness cannot be verified from what is in front of us. The claim is stated cleanly and the circularity burden is zero, so I am not inventing problems.

This is for people who work on Bayesian bandits, competitive analysis of sequential algorithms, or the theory of Thompson sampling. If you care about regret or mistake bounds under partial information, you will want the full paper. It deserves a serious referee: the conjecture is known, the statement is sharp, and a correct proof would be a solid permanent contribution. I would send it out rather than desk-reject, even while noting that we cannot yet audit the argument.

Recommendation: accept for peer review once the full text is available; the abstract alone already justifies referee time.

Referee Report

2 major / 0 minor

Summary. The manuscript claims that, for Bayesian bandits whose latent arm processes are independent and restful (each arm evolves only when played), Thompson sampling incurs at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. The bound holds under any nonincreasing sequence of round weights, covering fixed-horizon and geometrically discounted settings. For the special case of stochastic bandits with the best arm defined by mean reward, the result is said to confirm a 2014 conjecture of Guha and Munagala, for which the factor 2 is already known to be tight.

Significance. If the claimed competitive ratio is correctly established under the stated independence and restfulness assumptions, the paper would settle a long-standing conjecture and supply a clean, parameter-free guarantee for Thompson sampling that is stronger than typical regret bounds. The extension to arbitrary nonincreasing weights would further broaden the result’s applicability. Because the factor 2 is already known to be best possible in the stochastic case, the contribution would be a sharp characterization rather than a loose constant.

major comments (2)

Only the abstract is available for review. The central competitive-ratio claim cannot be verified: the derivation, intermediate lemmas, the precise definition of a “mistake”/suboptimal arm under a general Bayesian prior, and any technical side-conditions beyond independence and restfulness are all absent. Without the proof it is impossible to confirm that the factor-2 bound is obtained under exactly the hypotheses stated, or that no hidden regularity assumptions are required. This is a load-bearing obstacle to acceptance.
The abstract asserts that the result confirms the Guha–Munagala conjecture for stochastic bandits. Because the full argument is missing, it is not possible to check whether the reduction from the general Bayesian setting to the mean-reward stochastic case is free of additional assumptions, or whether the known tightness example is recovered inside the same framework.

Circularity Check

0 steps flagged · score 0.0 of 10

Abstract-only pure competitive-ratio theorem; no circularity detectable or constructible from available text.

full rationale

The available material is only the abstract of a theoretical result: Thompson sampling is at most 2-competitive for expected mistakes versus any policy, for Bayesian bandits with independent restful latent arm processes, under any nonincreasing round weights. No parameters are fitted, no quantity is defined in terms of the claimed factor-2 bound, no uniqueness theorem or ansatz is imported from the authors’ prior work, and no empirical pattern is renamed. The abstract states a competitive-ratio theorem whose inputs (independence, restfulness, nonincreasing weights) are explicit modeling assumptions rather than quantities derived from the conclusion. Because the full derivation is unavailable, no equation-level reduction can be exhibited; under the hard rule that circularity may be claimed only when a specific quote-and-reduction is possible, the honest finding is score 0 with empty steps. The reader’s own circularity assessment of 1.0 is consistent with this non-finding.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The claim rests on the standard Bayesian bandit model plus two domain assumptions (independence of latent arm processes and restfulness). No free parameters are fitted and no new entities are introduced.

assumptions (4)

domain assumption Latent arm processes are mutually independent
Stated as a necessary modeling condition for the competitive analysis to hold.
domain assumption Each arm evolves only when it is played (restful arms)
Explicitly required; without it the factor-2 argument does not apply.
domain assumption Best arm is defined via mean reward (stochastic case)
Used when specializing the general Bayesian result to ordinary stochastic bandits.
domain assumption Round weights form a nonincreasing sequence
Covers fixed horizon and geometric discounting; the analysis is stated for any such sequence.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Thompson Sampling Is 2-Competitive for Mistakes." pith.science (2026). https://pith.science/paper/FUJOIZLS

@misc{pith2026260712389,
  author       = {Pith},
  title        = {Pith review of: Thompson Sampling Is 2-Competitive for Mistakes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FUJOIZLS}},
  note         = {Machine review of arXiv:2607.12389}
}

abstract

We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor $2$ is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.

Discussion (0). Sign in to comment.

Pith tools

Reviewed July 15, 2026 · model on record in the stance chip above.