acceptodds
Under review as a conference paper at ICLR 2027

Implicit Thompson Sampling via Imagined Rewards

Abstract

Thompson sampling (TS) is an efficient algorithm for addressing the exploration-exploitation trade-off in sequential decision-making. However, its application to modern auto-regressive predictive models (e.g., LLMs and TabPFN) is limited, since it requires sampling from the posterior of an explicit Bayesian model. To address this challenge, we propose Imagined Reward Thompson Sampling (IRTS) as a family of TS-style algorithms, based on the insight that in-context learning with autoregressive models provides predictive inference for an implicitly defined Bayesian model. IRTS uses autoregressive models to sample imagined rewards autoregressively per action, and acts greedily w.r.t. either their averaged rewards (IRTS-A), or the predictive mean reward conditioned on the observed and imagined rewards (IRTS-C). We provide a regret analysis and prove that IRTS-A and IRTS-C provide a “sandwich” of exploration behaviour over TS, where both algorithms approach TS when . With finite , IRTS-A over-explores due to over-estimation of posterior uncertainty, while IRTS-C under-explores by interpolating between greedy and TS. Experiments across multi-armed and contextual bandits, with analytic, TabPFN and LLM-based in-context learners, demonstrate that IRTS achieves efficient TS-style exploration with implicitly-defined Bayesian models.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Bandits, Thompson Sampling, In-Context Learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_jtxQOpenReview ↗
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 τ\tau 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 O(T/τ)\mathcal{O}(T/\sqrt{\tau}). 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 τ\tau. 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 0.560.56, while arm 2 returns Bernoulli rewards with an unknown mean θ\theta, where

P(θ=0.5)=0.9,P(θ=1)=0.1.P(\theta=0.5)=0.9,\qquad P(\theta=1)=0.1.

The predictive mean of arm 2 is 0.550.55, so greedy selects arm 1. Exact TS selects arm 2 only when its posterior sample has θ=1\theta=1, with probability 0.10.1. For IRTS-C with τ=1\tau=1, 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
  1. What formal definition of exploration supports the claimed "sandwich"? How does the claim accommodate the counterexample above?

  2. Can you provide comparisons with PFN-TS and temperature-scheduled TS-LLM, together with uncertainty estimates for the improvement over greedy?

3 comments

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±.2685.80\pm.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.

τ = 1τ = 5τ = 10
IRTS-A70.68 ± 0.45 (−15.12)80.19 ± 0.37 (−5.60)82.24 ± 0.33 (−3.56)
IRTS-C91.49 ± 0.14 (+5.70)88.40 ± 0.23 (+2.60)87.33 ± 0.21 (+1.53)

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 τ\tau 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:

  • In Table 3 (p. 29), we will add a PFN-TS column reporting regret of 75,991 ± 257.
  • In Table 4 (p. 31), we will report PFN-TS regret of 3,480 ± 11 in the deterministic setting and 610.3 ± 5.0 in the stochastic setting.
  • The OpenML runs are still in progress. We will include those results once the runs finish.

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.

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

ExperimentLinear TSGreedyIRTS-AIRTS-CPFN-TS
Wheel20,831 ± 6,36059,939 ± 13,31212,243 ± 1,05336,434 ± 12,37975,991 ± 257

Table 4 — MovieLens: 1,500 steps, 10 seeds

ExperimentLinear TS (untuned)Linear TSGreedyIRTS-AIRTS-CPFN-TS
Deterministic1,922 ± 110918 ± 691,148 ± 169735 ± 22672 ± 143,480 ± 11
Stochastic476.4 ± 8.9159 ± 15235 ± 14306.8 ± 4.9201.3 ± 6.5610.3 ± 5.0

Table 5 — OpenML: 2,000 steps, 5 seeds

ExperimentLinear TSGreedyIRTS-AIRTS-CPFN-TS
Adult547 ± 19422 ± 14570 ± 13411 ± 6874 ± 39
Covertype1,364 ± 21998 ± 881,837 ± 141,036 ± 971,705 ± 8
EEG901 ± 7598 ± 12847 ± 11714 ± 15936 ± 14
Gas Drift1,085 ± 21954 ± 1351,487 ± 17968 ± 171,670 ± 4
MAGIC522 ± 7396 ± 22682 ± 8429 ± 14997 ± 26
Mushroom293 ± 12125 ± 39567 ± 12133 ± 6999 ± 4
Page Blocks277 ± 11195 ± 15461 ± 18198 ± 121,701 ± 28
Shuttle425 ± 6384 ± 16664 ± 36191 ± 321,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.

Reviewer_vniEOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes IRTS, a Thompson-sampling-style method for in-context learners (TabPFN, LLMs) that only expose a predictive distribution. Each round, the model autoregressively generates τ\tau imagined rewards per arm, and the agent acts greedily on either their average (IRTS-A) or the predictive mean given the observed and imagined data (IRTS-C). The authors show that IRTS-A over-explores and IRTS-C under-explores relative to exact TS, give regret bounds that recover TS as τ→∞\tau\to\infty, and run experiments using analytic Bayesian models, and contextual bandits with TabPFN as well as LLMs.

Critical strengths

The problem is relevant, the method is simple, and the over/under-exploration picture is a useful way to think about the two variants. It also explains why TS-LLM (Sun et al., 2025) needs temperature tuning.

Critical weaknesses
  1. Limited novelty, and theory that does not cover the experiments. The construction is essentially a truncated martingale posterior (Fong et al., 2023). TabMGP (Ng et al., 2025) already does this with TabPFN, Fortini et al. (2026) give a rollout-free CLT approximation to the same object, and Zhang et al. (2025) do TS by simulating missing rewards. The paper cites these only in passing and doesn’t explain what IRTS adds. Seen this way, Lemmas 3.1–3.2 are standard properties of a Doob martingale. Moreover, every result requires the in-context learner to give exactly an exchangeable Bayesian model. The TabMGP paper shows that TabPFN violates the relevant martingale-type conditions, so neither the regret bounds nor the over/under-exploration interpretation is supported in the TabPFN and LLM experiments. The paper should state clearly what is new relative to this literature and discuss what its guarantees mean when the predictive is only approximately Bayesian.
  2. Insufficient empirical support for practical use. The TabPFN experiments compare only against greedy and Linear TS, and Linear TS is weak on Wheel by design. The natural comparisons are flexible TS methods: KernelTS, NeuralTS, tree-ensemble TS methods, BFTS, and especially PFN-TS (Tan et al., 2026), which targets exactly this setting without rollouts and is already cited. Cost is not addressed either, even though tractability is the paper’s main motivation.

References

  • Fong, E., Holmes, C. and Walker, S. G. (2023). Martingale posterior distributions. Journal of the Royal Statistical Society Series B, 85(5), 1357–1391.
  • Fortini, S., Ng, K., Petrone, S., Rousseau, J. and Wei, S. (2026). Uncertainty decomposition for Bayes-filtered transformers via Bayesian predictive inference. arXiv:2602.04596.
  • Ng, K., Fong, E., Frazier, D. T., Knoblauch, J. and Wei, S. (2025). TabMGP: Martingale posterior with TabPFN. arXiv:2510.25154.
  • Tan, Y. S., Ng, K., Deng, R., Loganathan, S., Zhang, Q. and Chakraborty, B. (2026). PFN-TS: Thompson sampling for contextual bandits via prior-data fitted networks. arXiv:2605.10137.
  • Zhang, K. W., Cai, T. T., Namkoong, H. and Russo, D. (2025). Contextual Thompson sampling via generation of missing data. arXiv:2502.07064.
Questions for authors
  1. What does IRTS-C add beyond a truncated martingale-posterior rollout used for TS?
  2. What is the performance of IRTS-C relative to BFTS and PFN-TS in terms of both regret and running time?
3 comments

We thank the reviewer for the thorough assessment of our work. We would like to address the concerns and questions raised.

1. Contribution and scope of the theory. The novel contribution on the theory side is to analyse the consequences of using a finite rollout to make bandit decisions: we characterise how two choices in building the finite-compute approximation (IRTS-A and -C) affect the variance of the arm scores relative to exact TS and give regret bounds for both decision rules that quantify the dependence on τ\tau. The key novel contribution of our work is the analysis in the bandit setting of a computationally tractable, truncated martingale posterior-style TS algorithm. The Fong et al. (2023), Ng et al. (2025) and Fortini et al. (2026) papers are concerned with the supervised learning case and do not address the bandit setting. Zhang et al., (2025) do TS by generating missing rewards but they do not theoretically analyse the effect on regret and exploration due to a finite-sample approximation, which is a key novel contribution of our work. We understand that TabPFN and LLMs in-context learners can violate the martingale conditions assumed in the theory, and the scope of our work is not to correct or theoretically address this challenge. The purpose of our experiments beyond the analytic, well-specified Bayesian model cases is to investigate the applicability and robustness of IRTS exactly in these more challenging contexts where strict theoretical guarantees no longer apply or only approximately apply.

2. Regret comparisons. A key motivation of our work is to analyse a computationally tractable version of an algorithm that employs flexible in-context learning foundation models, which do not require additional hyperparameter tuning or training, which provides flexibility in the task and architecture used (eg TabPFN or LLM in-context learners). KernelTS requires specifying a kernel per task, NeuralTS and tree-ensemble based methods require the training of neural and tree architectures respectively, BFTS requires implementing and learning an MCMC approximation. On the other hand, IRTS can employ a black-box in-context learner with no further training and minimal task-specific design choices, so we think that fair comparisons involve methods that similarly do not require task-dependent training and specific tuning. We agree that PFN-TS is a 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:

  • In Table 3 (p. 29), we will add a PFN-TS column reporting regret of 75,991 ± 257.
  • In Table 4 (p. 31), we will report PFN-TS regret of 3,480 ± 11 in the deterministic setting and 610.3 ± 5.0 in the stochastic setting.
  • The OpenML runs are still in progress. We will include those results once the runs finish.

Our implementation of PFN-TS incurred higher regret than the other baselines in each of the three settings evaluated so far.

3. Runtime profile. As a computational benchmark, we ran greedy (with TabPFN), IRTS-A, IRTS-C (both with τ=1\tau=1) and PFN-TS in parallel on one A30 GPU the wheel bandit task, and recovered the following times to complete 1000 steps.

MethodWall time
Greedy14 m 19 s
IRTS-A (=1)53 m 58 s
IRTS-C (=1)1 h 04 m 08 s
PFN-TS2 h 33 m 52 s

Thank you for the response to my comments.

"The Fong et al. (2023), Ng et al. (2025) and Fortini et al. (2026) papers are concerned with the supervised learning case and do not address the bandit setting."

While they do not address the bandit setting, they introduce and analyze the finite rollout you use. The additional theoretical guarantees, as mentioned in my earlier review, are simple applications of existing bandit theory, and also do not account for the approximation gaps I mentioned earlier.

On the other hand, IRTS can employ a black-box in-context learner with no further training and minimal task-specific design choices, so we think that fair comparisons involve methods that similarly do not require task-dependent training and specific tuning.

I don't think this is strong enough motivation to exclude NeuralTS, XGBoostTS, RFTS, and BFTS. Furthermore, PFN-TS was designed to be used with TabICL or other TFMs with the KV caching, not with TabPFNv2.6, which does not do the caching. I am not convinced that your comparison is entirely fair.

Hence, I will keep my score.

We thank the reviewer for the follow-up. We disagree with characterising the regret bounds as simple applications of existing bandit theory. Wen et al. (2021, §5.3) explicitly conjecture a similar regret bound for the empirical-mean rule based on finitely many imagined rewards, motivated as a computationally more efficient alternative to their analysed algorithm (which involves latent parameter sampling), but leave it as an open problem. Our IRTS-A regret bound is a novel result that addresses the exact-predictive case of this conjecture for bounded rewards. Similarly, IRTS-C also avoids this latent resampling, and its regret bound is another novel result for an algorithm of practical relevance.

We understand PFN-TS was designed for efficient use of KV caching, which will have an effect on runtime - we used TabPFN 2.6 for consistency with the other experiments, and do not draw conclusions about the algorithms' general relative computational efficiency. The limitation that certain aspects of PFN-TS rely on KV caching, whereas IRTS does not, also has implications towards the relative versatility of our algorithm to the type of PFN model in use.

We report the full summary of the PFN-TS experiments's 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

ExperimentLinear TSGreedyIRTS-AIRTS-CPFN-TS
Wheel20,831 ± 6,36059,939 ± 13,31212,243 ± 1,05336,434 ± 12,37975,991 ± 257

Table 4 — MovieLens: 1,500 steps, 10 seeds

ExperimentLinear TS (untuned)Linear TSGreedyIRTS-AIRTS-CPFN-TS
Deterministic1,922 ± 110918 ± 691,148 ± 169735 ± 22672 ± 143,480 ± 11
Stochastic476.4 ± 8.9159 ± 15235 ± 14306.8 ± 4.9201.3 ± 6.5610.3 ± 5.0

Table 5 — OpenML: 2,000 steps, 5 seeds

ExperimentLinear TSGreedyIRTS-AIRTS-CPFN-TS
Adult547 ± 19422 ± 14570 ± 13411 ± 6874 ± 39
Covertype1,364 ± 21998 ± 881,837 ± 141,036 ± 971,705 ± 8
EEG901 ± 7598 ± 12847 ± 11714 ± 15936 ± 14
Gas Drift1,085 ± 21954 ± 1351,487 ± 17968 ± 171,670 ± 4
MAGIC522 ± 7396 ± 22682 ± 8429 ± 14997 ± 26
Mushroom293 ± 12125 ± 39567 ± 12133 ± 6999 ± 4
Page Blocks277 ± 11195 ± 15461 ± 18198 ± 121,701 ± 28
Shuttle425 ± 6384 ± 16664 ± 36191 ± 321,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.

We have uploaded a revised pdf, the aspects most relevant to our discussion involve the new PFN-TS results (in section 5.2 and appendix C). We have also added greater detail in the related work section on the specific novelty of our work relative to similar work.

Reviewer_jVmDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper adapts Thompson sampling (TS) to in-context learners such as tabular models, which give a predictive distribution but no posterior. Its method, IRTS, draws τ\tau imagined rewards per arm autoregressively. IRTS-A scores an arm by the mean of its imagined rewards, IRTS-C by the predictive mean given the history and the imagined outcomes. For rewards in [0,1], both have Bayesian regret at most Tlog⁡K/(2τ)T\sqrt{\log K/(2\tau)} plus a TS-style term. Experiments cover analytic bandits, TabPFN on three task families and three open-weight LLMs.

Critical strengths

The paper explores how to use TS with a given in-context learner like a tabular model, and bounds the regret of two algorithms, IRTS-A and IRTS-C.

  • The framing is useful because it unifies existing schemes. IRTS-A with τ=1\tau= 1 is TS-LLM without its temperature schedule, and IRTS is a finite-τ\tau version of the predictive sampling of Liu, Van Roy & Xu (2023).
  • The proofs are correct for an exact predictive, and I found no error in Prop. A.1 or Theorems 3.3–3.5..
  • The analytic experiments are carefully reported.Table 2 gives 100 seeds with standard errors. In the linear-Gaussian contextual task, IRTS-C at τ=1\tau = 1 has about two-thirds of exact TS's regret (Table 2).
Critical weaknesses
  • The regret bounds provide limited guarantees about the settings tested in the paper. The first term of Eqs. 6–8, Tlog⁡K/(2τ)T\sqrt{\log K/(2\tau)}, is linear in T. The proofs also draw θt\theta_t from the true posterior (line 894 in App. A.3, Eq. 28 in App. A.5), so they need an exact posterior predictive under the environment's prior. No theorem states that assumption, although line 525 says all assumptions are stated, and it puts the TabPFN and LLM experiments outside the theory.

  • The paper shows that IRTS-A's scores are noisier than TS's and IRTS-C's are less noisy. But noisier scores do not always lead to more exploration, so the claim that IRTS-A explores more than TS and IRTS-C less is not proved, and in some cases it is false. The abstract and line 228 state the ordering as one of exploration, while Lemmas 3.1–3.2 compare means and variances only.

  • Both algorithms and the main proof argument appear in work the paper cites, and finite-τ\tau regret has been bounded before. The algorithmic ideas and proof strategy have precedents in work the paper cites. Wen et al. (2021), bound in their Thm. 5.1 the regret of approximate TS from τ\tau jointly imagined outcome vectors, using the same auxiliary target action as Prop. A.1, and in their §5.3 they conjecture a similar bound for IRTS-A's sample-mean rule. Cai et al. test IRTS-A with τ=1\tau = 1 as a variant of their method and report that it incurs linear regret ( Liu, Van Roy & Xu themselves propose truncating predictive sampling to n imagined steps, which by exchangeability is IRTS-C with τ=n\tau=n in a stationary bandit.

  • The experiments with in-context learners give little support to the abstract's claim of "efficient TS-style exploration" . IRTS-C beats greedy by more than two standard errors in only 3 of the 14 TabPFN and LLM settings, and IRTS-A, which has the lowest mean regret on Wheel, is worse than greedy on all eight OpenML datasets and all three LLMs. The LLM task, a Bernoulli bandit with no TS or UCB reference (lines 450–451), uses the τ=1\tau=1 chosen from the contextual task (lines 375–377), although the Bernoulli column of Table 2 favours τ=10\tau=10 for IRTS-C by an order of magnitude in mean regret. With TabPFN, τ\tau is varied only on MovieLens (App. C.2.5), not on Wheel.

Questions for authors

-Do both variants have Ω(T)\Omega(T) regret at fixed τ\tau, and would letting \tauy\tauy grow with each arm's pull count, restore sublinear regret? -Decision Pretrained Transformers (Lee et al., 2023), which the paper cites at lines 291–292, already performs approximate posterior sampling in-context after pretraining to predict optimal actions. When is imagining rewards from an off-the-shelf outcome predictor preferable to that, and could Sec. 4 say so?

4 comments

We thank the reviewer for the thorough assessment of our work. We would like to address the criticisms raised.

1. Scope of the regret bounds. Both IRTS variants can incur linear regret (see the answer to the questions below in point 5). A bound that is linear in TT (but decreasing with τ\tau) is therefore a genuine limitation of IRTS, not a shortcoming of the theory. We will include these examples in the manuscript and clarify this point. Our theoretical analysis is concerned with a well-specified model and prior. Line 100 makes explicit that the predictive model used is induced from the same π\pi that the ground-truth parameter is sampled from. The exact predictive assumption is therefore part of the problem setup. We agree that the scope of the analysis could be easier to identify and we will clarify this in the introduction. In particular, the TabPFN and LLM experiments are designed to investigate the empirical robustness and applicability of IRTS beyond the exact Bayesian setting covered by the theory. We do not claim that these are covered by the theory but we find value in investigating their empirical behaviour nonetheless.

2. 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 behavior. 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 maximizing its posterior mean reward over the first 500 rounds of the Gaussian linear bandit. Exact TS selected a greedy arm in 85.80±0.2685.80\pm 0.26% of rounds. The table below reports the percentage frequency of greedy actions, with accompanying standard errors, and in brackets the difference with respect to exact TS.

τ = 1τ = 5τ = 10
IRTS-A70.68 ± 0.45 (−15.12)80.19 ± 0.37 (−5.60)82.24 ± 0.33 (−3.56)
IRTS-C91.49 ± 0.14 (+5.70)88.40 ± 0.23 (+2.60)87.33 ± 0.21 (+1.53)

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 τ\tau increased. This supports our behavioral interpretation in the linear-Gaussian setting. 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.

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.

3. Relationship to prior work. We agree that the algorithmic ideas and proof strategy have connections to the cited work. The distinction we emphasise is which decision rules the finite-τ\tau regret analysis covers. Wen et al.’s Theorem 5.1 analyses an algorithm that generates imagined observations and then samples latent reward parameters from their conditional distribution given those observations. IRTS-A acts directly on the empirical mean of the imagined rewards, while IRTS-C acts on the predictive mean conditional on the real and imagined observations, and crucially neither require this latent resampling step. Wen et al. explicitly leave the regret analysis of the empirical-mean rule open in Section 5.3, which strengthens the relevance of our contribution. We will make this connection clearer and credit the similarity in the auxiliary action used in the proof.

Cai et al. and Zhang et al. also consider employing truncated sequential generation in a related setting. We emphasise that our novel contribution is to quantifying how the regret bound depends on the finite imagination budget τ\tau for both scoring rules. Likewise, we already identify IRTS as a finite-compute adaptation of the predictive sampling approach of Liu, Van Roy & Xu at line 205. We will revise the related-work discussion to bring the relationship between these works and our finite-budget regret into clearer focus.

4. Experiments with in-context learners. We report results across tasks with different exploration requirements, including settings where greedy performs well. As discussed from line 412 onward, the benefit of exploration is task-dependent. 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. The reviewer also raises a specific point about the LLM experiment, as discussed in line 375, τ=1\tau=1 was chosen here since from the analytic experiments we saw that it strikes a balance between performance and computational cost.

Question 1. Can both variants incur linear regret at fixed, and can a growing budget restore sublinear regret? Yes, both variants can incur linear regret at fixed τ\tau, for different reasons.

IRTS-A: irreducible reward noise can cause the suboptimal arm to be chosen with some probability at every step. Consider two independent Bernoulli arms with known means 0<p2<p1<10<p_2<p_1<1, represented by a degenerate prior. Even with no epistemic uncertainty, the imagined empirical means remain random. The event that all τ\tau imagined rewards for arm 2 are successes and all those for arm 1 are failures has probability p2τ(1−p1)τ>0p_2^\tau(1-p_1)^\tau>0, and forces selection of the suboptimal arm. Consequently, \begin{equation} \mathcal R(T)\ge T(p_1-p_2)p_2^\tau(1-p_1)^\tau. \end{equation}

IRTS-C: not having sufficient imaginary observations may lead the conditional mean to never change enough to select a different arm. Consider a known arm with deterministic reward c∈(0,1)c\in(0,1), and a Bernoulli arm with mean θ∼Beta(1,b)\theta\sim\mathrm{Beta}(1,b). For any fixed τ\tau, choose bb so that \begin{equation} \frac{1+\tau}{1+b+\tau}<c. \end{equation} Even after imagining τ\tau successes, the uncertain arm’s conditional mean remains below cc. IRTS-C therefore always selects the known arm and never learns about θ\theta. Since the prior assigns positive probability to θ>c\theta>c, \begin{equation} \mathcal R(T) =T\mathbb E[\max(c,\theta)-c] =T\frac{(1-c)^{b+1}}{b+1} \end{equation} We conjecture that a growing budget can restore sublinear guarantees. If we let τ\tau vary with time, we expect the contribution to the regret to be proportional to ∑t=1T1τt\sum_{t=1}^T \frac{1}{\sqrt{\tau_t}}, so sublinear regrets are possible provided τt\tau_t increases fast enough. However, in this case sublinearity would require τt\tau_t to increase without bound, which would not be computationally tractable for practical algorithms. If instead each arm’s budget grows only with its own pull count, the IRTS-C example shows the difficulty. The uncertain arm is never pulled, so its budget never grows beyond its initial value.

Question 2. Comparison with Decision-Pretrained Transformers. DPT addresses a related problem with different training requirements. IRTS is attractive when an off-the-shelf predictor is already available, since it can use that predictor without additional decision-specific training. The trade-off is computation at decision time. IRTS generates imagined outcomes, while a suitably pretrained DPT can sample an action directly. Which approach performs better on a particular bandit task will also depend on how well that task is represented in the respective pretraining distributions. We will add this remark in Section 4.

Thank you for the answer, which addresses most of my concerns on the presentation of the results. I still have some requests:

  • First, your new examples show that IRTS can have linear regret when τ\tau is fixed. Hence, the sentence in the abstract that IRTS "achieves efficient TS-style exploration" should be adjusted.

  • Second, the proofs assume that the learner's predictive is the posterior predictive under the true prior π\pi. State this as an assumption in Theorems 3.3–3.5, and not only in the introduction. Line 100 only defines the prior of the environment, and lines 147–151 say that only access to the learner's predictive is assumed.

  • The promised rewording of the sandwich claim, the credit to Wen et al., the revised related work and the DPT remark address some of my other concerns.

  • For IRTS-C, τ=1\tau = 1 was chosen from the contextual task, but in the Bernoulli column of Table 2 its regret drops about thirteen-fold from τ=1\tau=1 to τ=10\tau=10. Without a sweep on τ\tau on Wheel or on the LLM task (or TS and UCB references on the LLM task) the experiments still give little support to the claim efficient exploration for in context learners.

Since the changes are not yet in a revised PDF and this last point is still open, I tend to keep my score.

We thank the reviewer for the follow-up. We have uploaded a revised PDF with changes highlighted. In summary:

  • We explicitly state that both IRTS variants can incur linear regret at fixed τ\tau, and provide the examples discussed above in Appendix A.3. Due to the linear regret, we have removed the claim that IRTS achieves “efficient” exploration from the abstract and introduction.
  • We explicitly state the assumption of an exact posterior predictive under the environment’s prior and likelihood immediately before Theorems 3.3–3.5. We also clarify that the TabPFN and LLM experiments evaluate IRTS beyond the setting covered by these guarantees.
  • 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 τ\tau in the contextual linear bandit experiment.
  • We have expanded the related-work discussion to clarify the connections to Wen et al. (2021), Zhang et al. (2025), and Liu et al. (2023) and how our work is distinct to these. We acknowledge the shared auxiliary-target information-theoretic proof framework with Wen et al. both in the related-work section and in Appendix A.4. We also explain the trade-off between IRTS and Decision Pretrained Transformers.

Comments on the paper

1 comment
Area_Chair_GxWWOpenReview ↗

Reviewer-Author Discussion Phase is Ending

Dear Reviewers,

Thank you for your service in the review process. Now that we are approaching the deadline of the author-reviewer discussion period. Please take time to read authors' responses and let them know if it addresses your concerns. Thank you.

Best,

Area Chair

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.