Adaptive Variance Inflation in Thompson Sampling: Efficiency, Safety, Robustness, and Beyond

1. The use of $O$, $\tilde O$ and $\Omega$.

• Thank you for the comment. We follow standard practice in using these notations to focus on dependencies with respect to $K$, $T$, and other key parameters. Where possible (e.g., Theorems 1 and 2), we explicitly specify environmental parameters and constants. We plan to provide detailed expressions --- including environmental dependencies --- in the appendix and will revise the main text accordingly.

2. I would not exactly agree with the sentence line 30-32: "Intuitively, this is because TS — like many other bandit algorithms — is primarily designed to maximize the expected cumulative reward within an experiment from an instance-dependent perspective." As far as I know, Thompson sampling was first designed for cumulative Bayesian regret, and because of that, some parameters (that have low mass according to the prior) could result in underexplored arms and then incorrect estimation.

• Thank you for pointing this out. We agree that the sentence could be misleading. Our intent was to emphasize that TS, while originally motivated by Bayesian regret minimization, often lacks strong guarantees for safety and post-experiment decisions, particularly when under-exploration occurs. Even when the prior is not severely mis-specified, insufficient exploration can still lead to unreliable estimates. We will revise the sentence to reflect this more accurately.

3. The number of experiments is missing, and no error intervals are shown in the experimental part. (The number of experiments appears in the checklist.)

• Thank you. As noted in the experimental section, each setting involves 10000 trials with different random seeds. We report both the mean and log tail probabilities to capture distributional characteristics. We will include standard deviations and error bars in the final version. However, we caution that standard deviation alone may not fully characterize safety, particularly in heavy-tailed settings.

4. One of the papers cited to justify the work may state a wrong theorem 1 [4] "Bandit algorithms: Letting go of logarithmic regret for statistical robustness". Their lower bound on the regret is incorrect; a sup on the parameter (the variance) should be added in order to have infinite logarithmic normalised regret. A table of the minimum of the divergences can be found here from Page 207, Bandit Algorithms Tor Lattimore and Csaba Szepesvári. Furthermore, in the present paper, the noise is assumed to be fixed as only a sup on $\mu$ is taken.

• Thank you for pointing this out. We reference [4] to highlight robustness limitations in standard UCB and TS under volatility mis-specification. We will clarify that our citation is intended to support this point, and not necessarily to endorse every claim in [4]. We will also correct the reference and note its limitations in the final version.

5. Assuming that the gap $|\Delta_k|\leq 1$ is bounded, weakens the claim of the paper a bit. But it may provide a cleaner result for the statement of your theorems.

• We agree. The boundedness assumption is made to simplify theoretical presentation. Our algorithm does not require prior knowledge of the bound. If $|\Delta_k| \leq C$, our regret bounds scale proportionally with $C$, and tail bounds adjust accordingly (an additional factor of $C$ on the denominator in the exponents). We will clarify this in the final version.

6. Can you point me to where you show that the best action is played enough, so that $n_{t, 1}$ is big enough? As it can usually be a problem for sampling algorithms.

• Theorem 1 and its proof demonstrate that the best arm is played at least $T - O(\sqrt{T}/\Delta)$ times with high probability, where $\Delta$ is the minimum gap. When $\Delta$ is small, arm pulls may become more balanced --- this is expected behavior and consistent with existing lower bounds.

7. Would it be possible to compare in the experiment, or theoretically (because only two arms are used), this Thompson sampling algorithm to the best arm identification algorithms (with the same metrics)? So that we can see where this algorithm lies (trade-off between cumulative regret and estimation error)?

• Thank you for the suggestion. Due to space constraints, detailed comparisons with best-arm identification algorithms are not in the main paper, but multi-arm results are provided in the appendix. Previous work (e.g., [28]) has explored the trade-off between cumulative regret and estimation error. Our work offers a unified framework that achieves worst-case optimal performance for both, and we are happy to expand on this point in the final version and pursue direct comparisons in future work.

8. On the experiment side, I think one of the most important ones is missing. How do your performance metrics scale in $\sigma, \nu$, with a fixed $\sigma_0$? I think you should also add error bars, or distribution bars, to see how the cumulative regret is distributed, as it is one of the main theoretical points of the paper. Or you may also compare the distributions of regret between the different algorithms. This is, I think, very important, and I am willing to raise my grade if you do so.

• We appreciate your detailed comment. Our experiments (including those in the appendix) illustrate that TS-VI-$\eta$ with $\eta=0.3$ to $0.6$ appears robust and safe under various different environments, while retaining good efficiency. This corresponds to fixing $\sigma_0$ while varying $\sigma$ and $\nu$. We are willing to include a direct comparison among those environments for fixed $\eta$ in the final version. In our experiments, for each environment and each policy, we run 10000 trials with different random seeds. We report both mean and log tail probabilities (serve as an analogous functionality as standard deviations). We will report standard deviations in the final version of our paper. Meanwhile, we would also like to point out that standard deviation might not fully capture the safety of a policy because there might be some chance that the tail is not characterized by the standard deviation. Initially we did not incorporate comparison of distributions because there are so many policies and various $T$. In the final version, we will plot comparison of distributions when $T=10000$ for various environments.

1. The intuition behind the adaptive inflation factor $t / (K n_{t,k})$ is not entirely clear. Is there a principled criterion or theoretical justification for choosing this form? More broadly, if one introduces an unknown adaptive factor, it seems possible to search for other forms that satisfy similar efficiency requirements.

• Thank you for this excellent question. Indeed, several inflation forms could satisfy the same regret expectations—for example, $(t/Kn)^\alpha$ for $\alpha \in (0, 1/2]$. However, only $\alpha = 1/2$ ensures the optimal regret tail decay rate for any $x > 0$, given the worst-case expected regret of $O(\sqrt{KT})$. The linear scaling with $n$ and square-root scaling with $t$ are essential; deviating from these would either violate worst-case optimal regret or degrade tail performance.

2. Beyond identifying the optimal mean reward, can the proposed method be extended to settings where the goal is to estimate the difference in means between arms? Such a scenario is of particular practical interest.

• Yes, our method extends naturally to estimating differences in means between arms. Theorem 3 implies controlled estimation error for each arm. Specifically, Lemma 2 shows that each arm is sampled at least $\Theta(T/K)$ times with high probability, ensuring reliable estimates of both individual means and their differences.

3. What happens if the hyperparameter $\sigma_0$ is set equal to or larger than the true $\sigma$?

• Thank you for pointing out this ambiguity. Our focus is on underestimation of $\sigma$, where the decision-maker risks being overly aggressive due to under-perceived uncertainty. If the hyperparameter equals or exceeds the true $\sigma$, the policy typically maintains optimal expected regret, although practical performance may degrade due to conservativeness. However, tail behavior remains polynomial, as shown in Simchi-Levi et al. (2022). Moreover, if the environment is mis-specified (e.g., exponential rather than Gaussian), even a larger $\sigma_0$ may not suffice --- highlighting the need for robust policies.

4. It would be beneficial to include experiments with $K > 2$ arms, as well as scenarios where $K$ is unknown to the learner.

• Multi-arm experiments are included in the appendix due to space constraints. As for unknown $K$, our current policy assumes knowledge of $K$, and extending it to handle unknown $K$ remains an open direction for future work.

5. From Figures 1-3, the proposed method appears to be sensitive to the choice of the hyperparameter $\sigma_0$, with different values leading to noticeably different performance. This raises concerns about the robustness of the approach.

• We appreciate the concern. In our context, ``robustness'' refers specifically to protection against under-specification of risk. As shown in Figures 1-3, while regret expectations do vary with the hyperparameter, the regret tail decays much more favorably with our method. This trade-off is inherent—some loss in expected performance is necessary to gain safety. That said, improving robustness in expectation (i.e., reducing constant-factor differences) is an interesting direction for future work.

6. $\sigma_0$ also appears in standard Thompson Sampling (TS). It would be helpful to report the performance of TS when $\sigma_0$ is slightly smaller than the true $\sigma$, for a more direct comparison with the proposed method.

• Thank you for the suggestion. We have included experiments with standard TS using a slightly mis-specified variance ($(0.9\sigma)^2$), along with UCB baselines: standard UCB ($\sigma\sqrt{2\ln t/n}$), and UCB with mis-specified bonus ($0.9\sigma\sqrt{2\ln t/n}$). Our conclusions remain the same: while these policies perform well in terms of average regret, they exhibit poor tail performance and mean estimation quality. These results will be added to the final version. We reiterate that our TS-GN policy offers a more robust alternative under uncertainty and heterogeneity.

We would like to first thank the reviewer for the very careful correction on some typos in the paper. We will make corresponding amendment, revise such language, and correct all mistakes in the final version.

1. Experimental validation lacks uncertainty quantification. Repeating trials with multiple random seeds and reporting standard deviations would strengthen the empirical claims.

• Thank you for the suggestion. As stated in the experimental section, we conduct 10,000 trials for each environment-policy pair using different random seeds. We report both the mean and the log tail probabilities, which serve a similar purpose as standard deviations by capturing distributional behavior. We will explicitly include standard deviations in the final version. However, we note that standard deviations may not fully characterize safety, particularly when tail events deviate from Gaussian assumptions.

2. The experimental section would benefit from comparison with other baselines beyond standard TS, such as UCB or $\epsilon$-TS [1].

• Thank you for the suggestion. In addition to standard TS, we also evaluated standard TS with slightly mis-specified variance ($(0.9\sigma)^2$), standard UCB ($\sigma\sqrt{2\ln t/n}$), and UCB with mis-specified bonus ($0.9\sigma\sqrt{2\ln t/n}$). Our findings hold across these baselines—while these methods perform well in terms of expected reward, they suffer significantly in terms of tail safety and mean estimation. These additional results will be included in the final version. We again emphasize that TS-GN is a practical solution for handling unknown heterogeneous variances across arms.

3. What would be the main challenges in extending the variance inflation idea to a more general MDP setting? How could this work benefit MDP analysis?

• We assume the reviewer is referring to the episodic MDP setting. The main challenge is that current actions affect future states, leading to error propagation over time. Estimation errors in later stages can also influence earlier decisions, making analysis much more complex. While we have begun exploring extensions of variance inflation to MDPs, establishing theoretical guarantees appears to require new tools beyond our current variance inflation framework.

Thank you for the response. My main concerns have been addressed. I will maintain my original score, as I am unsure whether the work meets the acceptance bar, in part due to my limited familiarity with the safety and robustness literature.

I also pointed out some notational issues under "Quality and Clarity". Please revise accordingly if appropriate.

1. The significance of the results is not well motivated. As someone not directly working in this field, I find it difficult to appreciate the broader contributions of this paper. It is also unclear which aspects of the work represent novel contributions to the literature.

• Thank you for the insightful comment. We would like to clarify our contributions more explicitly. (a) On the practical side, our work aims to develop bandit policies that simultaneously achieve optimal expected regret, optimal tail decay in regret, and strong post-experiment performance in both best-arm identification and mean estimation tasks. In real-world scenarios, decision-makers must balance multiple objectives—accounting not just for within-experiment performance, but also for the downstream impact of decisions made under uncertainty and possible model mis-specification. (b) On the theoretical side, our work proposes a conceptually simple yet powerful modification to the Thompson Sampling (TS) policy, along with a unifying analysis framework that ensures efficiency, safety, and robustness across multiple objectives. We believe this framework offers fresh insights for the design of safe and practically reliable bandit algorithms.

2. While I understand this is primarily a theoretical paper, I would appreciate more extensive empirical studies to support the theoretical claims and help make the insights more tangible. The current version, including the experiments in the appendix, focuses solely on synthetic scenarios. The impact of the paper could be significantly elevated by including empirical studies involving real-world problems and drawing insights from them to demonstrate the practical relevance of the results.

• Thank you for the valuable suggestion. We agree that incorporating real-world experiments would enhance the practical impact of our work, and we plan to explore this in future work. Nonetheless, we wish to emphasize that our proposed TS-GN policy is already a practical enhancement --- it specifically addresses the challenge of unknown heterogeneous variance across arms, which is common in applied settings.

3. What exactly is the set $\Theta$?

• $\Theta$ is the set of all vectors in $\mathbb R^d$ such that $\Delta_k\leq 1$ for all $k$. We will make this more precise in the final version.

4. What is the precise dependence of the constant factors in your bounds on the environmental hyperparameters?

• The dependence on environmental hyperparameters is explicitly provided in Theorems 1 and 2. For Theorem 3, the dependence is more intricate and is detailed in the appendix. While we suppress absolute constants for clarity (as they are difficult to characterize precisely), we note that loose upper bounds are available and will be clarified in the final version.