REVIEW 2 major objections 3 minor 1 cited by
Optimism Stabilizes Thompson Sampling for Adaptive Inference
T0 review · 2 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read Optimism—implemented as variance inflation or a mean bonus—makes Thompson sampling stable and restores the validity of standard Wald confidence intervals under adaptive data collection.
desk verdict Plausible K-armed stability result, but the key transfer step for multiple optimal arms is asserted rather than proven; worth refereeing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The stability argument rests on several interacting mechanisms. For variance inflation, the core object is a 'winner map' g(x): the probability that a pure-noise Gaussian index from arm i is the maximum when proportions are x. The map has a negative-feedback property—over-pulled arms win less often—which yields a dot-product inequality whose violation drives a quadratic Lyapunov function toward uniformity; a perturbation bound shows the actual Thompson selection probabilities track the ideal map up to a vanishing error. A separate rare-event analysis bounds the chance a suboptimal arm's index exceeds the best optimal-arm index, giving sharp exponential selection probabilities that are sandwi
What would settle it
Simulate variance-inflated TS for K=3 with means (0,0,-Delta) and a growing horizon, and check whether N_{a,T}/(sigma(A) log T) converges to 2/Delta^2 for the suboptimal arm while both optimal arms receive N_{a,T}/T converging to 1/2; a persistent divergence at large T, or a third-arm counterexample to the cited suboptimal-pull bound, would refute the stability claim.
Extended reading notes
Core claim
On the paper's own terms: with Gaussian unit-variance rewards and K fixed, if Thompson sampling draws indices from a posterior whose variance is inflated by a factor sigma(A) growing slower than T/log^2 T, or from a pseudo-posterior whose mean is shifted by sqrt(2 beta(A) log T / N_{a,t}) with beta(A) growing slowly, then N_{a,T}/N*_{a,T} converges in probability to 1, where the deterministic scale is T/m for optimal arms and 2 c(A) log T / Delta_a^2 for suboptimal arms. Consequently studentized sample means converge to N(0,1) and Wald confidence intervals for each arm mean have asymptotic coverage 1-alpha. The paper frames optimism as the unifying mechanism: either form of upward bias preve
Load-bearing premise
The proof borrows a prior bound on the expected number of suboptimal pulls, developed for two-armed TS, and applies it to the K-armed setting without proving it there; it also assumes Gaussian unit-variance rewards, even though the abstract advertises sub-Gaussian noises, so the argument stands or falls on those two premises.
Editorial extensions
If this is right
- Variance-inflated TS is stable for any K >= 2, including multiple optimal arms, resolving the K-armed extension left open in prior two-armed work.
- Mean-bonus TS—a randomized analogue of optimistic bonus rules—is stable with the same sharp suboptimal pull asymptotics, isolating optimism as the key driver.
- Under either variant, studentized sample means are asymptotically normal and Wald confidence intervals have nominal coverage despite adaptive sampling.
- Suboptimal arms are pulled on a logarithmic scale: 2 sigma(A) log T / Delta_a^2 under variance inflation and 2 beta(A) log T / Delta_a^2 under a mean bonus.
- Regret grows by only a mild slowly varying factor (e.g., (log log T)^2) relative to vanilla Thompson sampling.
Reading between the lines
- If optimism is the stabilizing mechanism, other optimistic posterior rules—such as upper-quantile indexing or drawing multiple posterior samples and taking their maximum—should also stabilize TS; the mean-bonus proof already points in that direction.
- A concrete boundary test: replace Gaussian noise with a non-Gaussian sub-Gaussian distribution. The proofs rely on Gaussian posterior updates and Gaussian tail bounds, so the current guarantee is for Gaussian rewards despite the abstract's wider promise; a sub-Gaussian extension would require new concentration tools.
- The winner-map negative feedback resembles balancing mechanisms in other randomized allocation problems; the same Lyapunov argument may provide stable inference for a broader class of randomized rules whose selection probabilities decrease in their own allocation share.
- For practitioners, the result suggests a simple recipe—run optimistic TS and use ordinary sample-mean confidence intervals without debiasing—but the slowly growing regret inflation should be weighed against the convenience of classical inference in a specific experiment.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies adaptive inference for K-armed Gaussian bandits under two optimistic variants of Thompson sampling: variance-inflated TS (Algorithm 1, Option B) and mean-bonus TS (Algorithm 1, Option C). It claims both are stable in the sense of Lai and Wei: optimal arms receive asymptotically T/m pulls, suboptimal arm a receives (2c(A) log T)/Δ_a^2 pulls where c(A)=σ(A) or β(A), and consequently studentized sample means are asymptotically normal and Wald confidence intervals are valid. The proofs introduce a pure-noise winner map and Lyapunov drift for uniform allocation among optimal arms, and geometric waiting-time arguments for suboptimal-pull asymptotics. The variance-inflation result is presented as resolving the K-armed extension question raised by Halder et al. (2025).
Significance. If the results are correct, the paper makes a useful contribution: it identifies optimism as a mechanism for restoring stability of Thompson sampling, treats the multiple-optimal-arm regime, and gives a clean route from stability to Wald inference. The equal-means winner-map analysis is an appealing technique, and the mean-bonus proof is largely self-contained. The claimed regret penalty is mild when the tuning parameters grow slowly. At the same time, the ``sharp constant 2'' is algorithm-relative: it is inherited from the Gaussian index distribution and depends on the inflation factor σ(A) or β(A), so it is not a parameter-free law. The central gap described below concerns the proof of uniform allocation among multiple optimal arms for variance-inflated TS, and must be repaired before the main theorem is established.
major comments (2)
- [Appendix A.1.2, Eq. (A.9)] The key step for Theorem 4.1(a) asserts, after ``Similarly to Lemma A.3,'' that on E_T∩Ω_T, max_i |q_{i,τ_s} − g_i(e y_s)| ≤ c m η_T. This is not a consequence of Lemma A.3. Lemma A.3 bounds a single-round winner probability under additive mean shifts; q_{i,τ_s} is a conditional first-hitting probability: it requires that no optimal arm be pulled for possibly several steps and that the eventual optimal pull be arm i. Conditioning on the first optimal pull size-biases the within-optimal maximizer, since suboptimal index samples act as a random threshold. In particular q_i is proportional to g_i·s_i with s_i = P(M_opt > M_sub | argmax_opt = i), and the factors s_i are not shown to be within 1 ± O(η_T). Without this bound the Lyapunov drift recursion for Ṽ_s has no justification, so the claim of asymptotically uniform allocation among multiple optimal arms is unsupported.
- [Appendix A, Lemma C.3 and Eq. (A.3)] The proof of Theorem 4.1(b) relies at a load-bearing point on Lemma C.3, imported from Halder et al. (2025), for the expected suboptimal-pull bound E[N_{a,T}] = O(σ(A) log(TΔ_a^2/σ(A))/Δ_a^2). This lemma is used to define the high-probability event Ω_T in (A.3) and to control the burn-in time in Lemma A.7. The manuscript neither proves this lemma nor states the scope of the original result (two-armed vs. K-armed). If the cited lemma is only two-armed, the K-armed variance-inflation result is incomplete. Please supply a proof for K arms or an explicit statement that the source lemma holds in the required K-armed setting.
minor comments (3)
- [Abstract and §2.1] The abstract promises ``independent sub-Gaussian reward noises,'' but Section 2.1 explicitly sets rewards to be Gaussian with unit variance, and the proofs use Gaussian tail bounds and Gaussian posterior indices throughout. The abstract should be aligned with the actual model, or the sub-Gaussian claim proved.
- [§A.2.2, Lemma A.6 and Eq. (A.17)-(A.18)] There are notation/typo inconsistencies: in the text immediately before Lemma C.4, α−(ε) is called (Δ_a − 3ε)^2/2 whereas Eq. (A.17) defines α−(ε)=(Δ_a + 3ε)^2/2; the displayed formula for n−(T) uses α+(ε) in one place and α−(ε) in another. In the proof of Lemma A.6, the displayed couplings 1{U≤p+} ≤ 1{A=a} ≤ 1{U≤p−} appear reversed if p+ denotes the upper bound and p− the lower bound. These should be corrected.
- [§5.1, Step 3] The overview says the final result is a bracket N_{a,T} = Θ(2σ(A) log T/Δ_a^2), but Theorem 4.1(b) is the stronger claim N_{a,T}/(σ(A) log T) → 2/Δ_a^2. The overview should state the convergence, not just order notation.
Circularity Check
No significant circularity: stability scales are derived from algorithm dynamics, not assumed; external Lemma C.3 is only a coarse-input bound and not load-bearing for the sharp constants.
full rationale
I walked the derivation chain. Theorem 4.1's equal-means winner map is constructed from the algorithm's own Gaussian indices, and Lemmas A.1-A.3 prove the negative-feedback and perturbation properties rather than assuming them; the Lyapunov argument then derives V_T->0. The general K-armed case embeds at optimal pulls; the approximation q_{i,tau_s} ≈ g_i(e y_s) is asserted ('Similarly to Lemma A.3') without a full proof, but this is a proof gap/correctness risk, not circularity, because q is not a fitted parameter or a restatement of the conclusion. The suboptimal counts are obtained from Gaussian overshoot probabilities (Lemmas A.4-A.6) and a geometric log-growth law (Lemma C.4); the constant 2/Delta_a^2 emerges from the Mills-ratio computation, not from an input. The mean-bonus proof (Theorem 4.2) uses the bonus formula's own threshold N*_{a,T}=2 beta(A) log T / Delta_a^2 both in the upper and lower bracketing arguments; this is a self-consistency analysis of the designed rule, but the theorem still proves concentration (via G_T, Lemmas B.3-B.5) rather than assuming it. Lemma C.3 is an external citation (Halder et al. 2025), not a self-citation, and it is used only for the coarse event Omega_T and burn-in control; it does not supply the sharp constant. The inference result Theorem 4.4 follows from stability plus the externally cited Lai-Wei CLT. There are no load-bearing self-citations, no fitted value renamed as a prediction, and no uniqueness theorem imported from the authors' prior work. The closest thing to a 'self-dictated scale' is that the deterministic sequences N*_{a,T} contain sigma(A) or beta(A), but that merely reflects that the theorems characterize the algorithms' tuning parameters; the ratio statements are derived, not true by construction.
Assumptions & free parameters
free parameters (2)
- sigma(A) (variance inflation factor) =
not specified; must satisfy sigma/log log T -> infinity and sigma (log T)^2 / T -> 0
- beta(A) (mean-bonus strength) =
not specified; must satisfy beta -> infinity and beta logT / T -> 0
assumptions (6)
- domain assumption Rewards are Gaussian with unit variance: R_{a,t}=mu_a+Z_{a,t}, Z_{a,t} i.i.d. N(0,1).
- domain assumption Each arm is pulled once in an initialization phase before Gaussian-index sampling begins.
- ad hoc to paper Growth conditions on sigma(A) (3.2) and beta(A) (3.3).
- domain assumption Lemma C.3 from Halder et al. (2025): E[N_{a,T}] <= O(sigma log(T Delta^2 / sigma) / Delta^2) for variance-inflated TS.
- standard math Time-uniform sub-Gaussian concentration (Lemma C.2, Howard et al.) and Gaussian tail bounds (Lemma C.1).
- standard math Martingale central limit/Slutsky (Proposition 2.2, Lai-Wei).
Cite this review
Pith. "Pith review of Optimism Stabilizes Thompson Sampling for Adaptive Inference." pith.science (2026). https://pith.science/paper/LMBEHSRA
@misc{pith2026260206014,
author = {Pith},
title = {Pith review of: Optimism Stabilizes Thompson Sampling for Adaptive Inference},
year = {2026},
howpublished = {\url{https://pith.science/paper/LMBEHSRA}},
note = {Machine review of arXiv:2602.06014}
}
abstract
Thompson sampling (TS) is widely used for stochastic multi-armed bandits, yet its inferential properties under adaptive data collection are subtle. Classical asymptotic theory for sample means can fail because arm-specific sample sizes are random and coupled with the rewards through the action-selection rule. We study adaptive inference for Thompson sampling with Gaussian randomized indices in $K$-armed stochastic bandits with independent sub-Gaussian reward noises, and identify \emph{optimism} as a key mechanism for restoring \emph{stability}, meaning that each arm's pull count concentrates around a deterministic scale. This stability yields asymptotically valid Wald inference despite adaptive sampling. First, we prove that variance-inflated TS is stable for any $K \ge 2$, including the challenging regime where multiple arms are optimal, with asymptotically uniform allocation over optimal arms and sharp logarithmic pull-count asymptotics for suboptimal arms. This resolves the $K$-armed extension question raised by \citet{halder2025stable}, using new winner-map and Lyapunov-drift techniques to control allocation among multiple optimal arms. Second, we analyze an alternative optimistic modification that keeps the Gaussian index variance unchanged but adds an explicit mean bonus to the index center, and establish a similar stability conclusion. In summary, suitably implemented optimism stabilizes Thompson sampling and enables asymptotically valid Wald inference in multi-armed bandits, while incurring only a mild additional regret cost.
Forward citations
Cited by 1 Pith paper
-
Bandit Simulation for Average Reward Inference
BSI fits an environment simulator from bandit data and propagates parameter uncertainty to produce asymptotically valid confidence intervals for mean reward under arbitrary evaluation policies, including black-box ada...
Reference graph
Works this paper leans on
-
[1]
Abbasi-Yadkori, Y ., P´al, D. and Szepesv´ari, C. (2011). Improved algorithms for linear stochastic bandits.Advances in neural information processing systems,24. Agarwal, A. and Zhang, T. (2022). Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity.Advances in Neural Information Processing Systems,3535284–35297. A...
arXiv 2011
-
[3]
+ 2√C1 logT)∆ ap 2β(A) logT < ∆aβ(A) −1/4 8 (B.24) 28 asβ(A) −1/4 →0. Plugging (B.23) and (B.24) into (B.21) gives Υa,t+1 ≥µ a + ∆a 1 + β(A) −1/4 2 − ∆aβ(A) −1/4 8 =µ ⋆ + 3∆aβ(A) −1/4 8 .(B.25) Finally, (B.20) and (B.25) imply Υa,t+1 > µ⋆ + 3∆aβ(A) −1/4 8 >max i∈S ⋆ Υi,t+1, which proves (B.18). Contradiction based on(B.18).If (B.18) holds for everyt∈ {T− ...
2020
-
[4]
Assume eachX t is1-sub-Gaussian. Then there exists an absolute constantc >0such that, for anyδ∈(0,1), with probability at least1−δ, the following holds simultaneously for all integerst≥3: 1 t tX i=1 Xi ≤c r 1 t log logt+ log(1/δ) . Lemma C.3(Lemma 3 and Proposition 1 in Halder et al. (2025)).Forσ(A)≥4andT∆ 2 a/σ(A)→ ∞, the expectation of the pull number o...
2025
-
[1114]
Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules.Advances in applied mathematics, 64–22. Lai, T. L. and Wei, C. Z. (1982). Least squares estimates in stochastic regression models with applications to identifi- cation and control of dynamic systems.The Annals of Statistics154–166. Lattimore, T. and Szepesv´ari, C. (2020...
arXiv 1985
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.