- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper evaluates approximate Thompson sampling algorithms that rely solely on predictive distributions rather than parameter posterior samples. It examines two approaches that draw synthetic outcomes per action: IRTS-A selects actions using empirical imagined rewards, while IRTS-C uses predictive means conditioned on the imagined data. The authors establish score-variance characterizations and prove Bayesian regret bounds featuring a finite-sampling penalty of order . Their theoretical findings are validated across four analytical bandit models, TabPFN benchmarks (Wheel, MovieLens, and eight OpenML datasets), and a five-arm Bernoulli task evaluated on three Large Language Models.
The finite-budget analysis is useful, but the central exploration interpretation needs correction, and the empirical evidence does not yet establish a sufficiently strong advantage over closely related methods.
Critical strengths
Useful analysis of finite imagination budgets. The regret bounds explicitly quantify dependence on . The variance results show that IRTS-A’s scores contain extra noise from simulated outcomes, while IRTS-C’s predicted mean rewards have lower variance than TS’s scores. These findings clarify how using a limited number of imagined rewards changes the scores used for action selection.
Critical weaknesses
The exploration claims are stronger than the variance results establish. Lemmas 3.1–3.2 (lines 216–226) establish an ordering of each arm’s score variance: IRTS-C has lower variance than exact TS, while IRTS-A has higher variance. However, this does not establish the corresponding ordering of exploration behavior asserted at lines 228–229, or justify describing finite-budget IRTS-C as a “greedier” version of TS at lines 260–261. Action selection depends on which score is largest, rather than on the marginal score variances alone.
A counterexample illustrates this distinction. Consider two arms: arm 1 always returns , while arm 2 returns Bernoulli rewards with an unknown mean , where
The predictive mean of arm 2 is , so greedy selects arm 1. Exact TS selects arm 2 only when its posterior sample has , with probability . For IRTS-C with , an imagined success raises arm 2’s conditional predictive mean to
=\frac{0.9(0.5)^2+0.1(1)^2}{0.9(0.5)+0.1(1)} \approx0.591,$$ whereas an imagined failure reduces it to $0.5$. Consequently, IRTS-C selects arm 2 whenever the imagined observation is a success, with probability $0.55$. Thus, IRTS-C chooses the nongreedy arm more frequently than TS, despite having lower score variance. This example does not contradict the variance lemmas; it challenges their interpretation as a universal ordering of policy exploration. The authors should define “exploration” precisely and either establish the claimed ordering under additional assumptions or restrict the conclusion to score variances. The corresponding claims in the abstract (lines 020–024), introduction (lines 080–090), and discussion (lines 484–485) should also be qualified. **Comparisons with closely related methods are incomplete.** PFN-TS is discussed but not evaluated experimentally. Furthermore, the LLM experiments compare against IRTS-A without the temperature schedule used in the original TS-LLM method to control exploration. Including these alternatives would help establish whether IRTS-C improves on existing approaches. **The advantage over greedy selection remains uncertain.** Greedy selects the action with the highest predicted mean without generating imagined rewards. In Table 6, IRTS-C achieves lower mean regret than greedy for Mistral and Qwen, but higher mean regret for LLaMA; the improvements are also modest relative to the reported standard errors. With only one LLM bandit configuration evaluated, the results do not clearly establish when imagined rewards provide a reliable benefit over greedy selection.Questions for authors
-
What formal definition of exploration supports the claimed "sandwich"? How does the claim accommodate the counterexample above?
-
Can you provide comparisons with PFN-TS and temperature-scheduled TS-LLM, together with uncertainty estimates for the improvement over greedy?
3 comments
We would like to follow up by highlighting the updates made in the revised pdf which are most relevant to our discussion. In summary:
- We have revised the abstract, introduction, and discussion to distinguish the proved score-variance ordering from its heuristic interpretation in terms of exploration. Appendix C.1.4 additionally reports greedy-action frequencies for both IRTS variants at different values of in the contextual linear bandit experiment.
- We have included PFN-TS results in Section 5.2 and Appendix C. We summarise in the following the updated cumulative regret tables and results.
We tested both disjoint and joint encoding on the Wheel, both MovieLens tasks, Adult and EEG bandit tasks. We found that the disjoint encoding performed better in all these tasks with the exception of Wheel (75,991 ± 257 cumulative regret for disjoint vs 71,335 ± 407 for disjoint). We therefore completed the PFN-TS results with the disjoint encoding and report all results using this encoding. We report here the summary for the 3 updated tables with cumulative regrets.
Table 3 — Wheel: 2,500 steps, 10 seeds
| Experiment | Linear TS | Greedy | IRTS-A | IRTS-C | PFN-TS |
|---|---|---|---|---|---|
| Wheel | 20,831 ± 6,360 | 59,939 ± 13,312 | 12,243 ± 1,053 | 36,434 ± 12,379 | 75,991 ± 257 |
Table 4 — MovieLens: 1,500 steps, 10 seeds
| Experiment | Linear TS (untuned) | Linear TS | Greedy | IRTS-A | IRTS-C | PFN-TS |
|---|---|---|---|---|---|---|
| Deterministic | 1,922 ± 110 | 918 ± 69 | 1,148 ± 169 | 735 ± 22 | 672 ± 14 | 3,480 ± 11 |
| Stochastic | 476.4 ± 8.9 | 159 ± 15 | 235 ± 14 | 306.8 ± 4.9 | 201.3 ± 6.5 | 610.3 ± 5.0 |
Table 5 — OpenML: 2,000 steps, 5 seeds
| Experiment | Linear TS | Greedy | IRTS-A | IRTS-C | PFN-TS |
|---|---|---|---|---|---|
| Adult | 547 ± 19 | 422 ± 14 | 570 ± 13 | 411 ± 6 | 874 ± 39 |
| Covertype | 1,364 ± 21 | 998 ± 88 | 1,837 ± 14 | 1,036 ± 97 | 1,705 ± 8 |
| EEG | 901 ± 7 | 598 ± 12 | 847 ± 11 | 714 ± 15 | 936 ± 14 |
| Gas Drift | 1,085 ± 21 | 954 ± 135 | 1,487 ± 17 | 968 ± 17 | 1,670 ± 4 |
| MAGIC | 522 ± 7 | 396 ± 22 | 682 ± 8 | 429 ± 14 | 997 ± 26 |
| Mushroom | 293 ± 12 | 125 ± 39 | 567 ± 12 | 133 ± 6 | 999 ± 4 |
| Page Blocks | 277 ± 11 | 195 ± 15 | 461 ± 18 | 198 ± 12 | 1,701 ± 28 |
| Shuttle | 425 ± 6 | 384 ± 16 | 664 ± 36 | 191 ± 32 | 1,802 ± 27 |
Entries report mean cumulative regret ± standard error. IRTS variants use τ=1; PFN-TS uses disjoint encoding. Bold entries have mean regret within one standard error of the lowest mean, using the standard error of the method attaining that minimum.
The repository linked to from the PFN-TS paper version on arXiv is expired and no longer available, so we made our best effort to reimplement PFN-TS independently from the description in the paper (with the disjoint encoding and changing the backbone to use TabPFN instead of TabICL). Under this implementation and backbone, we did not recover the competitive performance reported in the original paper.
Thank you for your response. I acknowledge the revision, and I will consider it in more depth during the reviewer-AC discussion period.
We thank the reviewer for the thorough assessment of our work and would like to address the concerns raised.
1. Score variance and exploration. We agree that an ordering of score variances does not, by itself, imply an ordering of action-selection probabilities. Our intended interpretation is that the variance lemmas help explain why the two variants can exhibit different exploratory behaviour. We also find precedents in literature related to the idea linking the variance of scores to exploration. For example, in [1] at the end of page 4 the authors argue that widening the distribution from which the posterior samples are taken would favour exploration, and in [2] the authors inflate the sampling variance to discourage the premature decay of exploration. To examine this directly, we measured how often each algorithm selected an arm maximising its posterior mean reward over the first 500 rounds of the Gaussian linear bandit. Exact TS selected a greedy arm in 85.80±.26% of rounds. The table below reports the frequency in percentages of greedy actions, with accompanying standard errors, and in brackets the difference with respect to exact TS.
Across all three budgets, IRTS-A selected the greedy arm less often than exact TS and IRTS-C selected it more often. Both gaps narrowed as τ increased. This supports our behavioural interpretation in the linear-Gaussian setting. Nonetheless, we will qualify the relevant passages in the abstract, introduction, and discussion so that they distinguish this empirical tendency from the score-variance ordering established by the lemmas - and explicitly amend the discussion after the variance lemmas to use a more precise wording of their implication.
2. PFN-TS comparison. We agree that PFN-TS is a particularly relevant baseline because it addresses the same practical question of how to use a PFN for Thompson sampling. We have implemented PFN-TS (using the categorical arm encoding and the same TabPFN architecture used in the other experiments) and are adding it as a baseline. The TabPFN arXiv preprint links to source code that is no longer available, so we evaluated our own implementation. The summary of the results we include are as follows:
Our implementation of PFN-TS incurred higher regret than the other baselines in each of the three settings evaluated so far.
3. Advantage over greedy action selection. As discussed from line 412 onward, the benefit of exploration is task-dependent, which is a point common to all bandit algorithms. For example, IRTS-A has the lowest mean regret on Wheel, while greedy performs better on the OpenML tasks derived from supervised learning. The analytic bandits, where the model is well specified and we can sample many seeds per task, provide a more direct and principled assessment of performance in the Bayesian setting studied by the theory.
Question 1. We will qualify the relevant passages in the abstract, introduction, and discussion to disambiguate that the variance lemmas provide guarantees in terms of the relative noise of the score rather than action-selection frequencies.
Question 2. We report the new PFN-TS comparison in point 2 above. For the LLM experiments, we evaluated IRTS-A without a temperature schedule. This lets us compare the two IRTS scoring rules under the same generation settings, but leaves the comparison with manually-tuned temperature-scheduled TS-LLM open. We don’t claim to outperform TS-LLM generally, but we believe that our analysis provides an explanation for why the manual temperature scaling employed there is necessary in the first place.
References:
[1] Chapelle, Olivier, and Lihong Li. "An empirical evaluation of Thompson sampling." Advances in neural information processing systems 24 (2011).
[2] Zhu, Feng, and David Simchi-Levi. "Adaptive variance inflation in Thompson sampling: Efficiency, safety, robustness, and beyond." Advances in Neural Information Processing Systems 38 (2026): 50466-50484.