Adaptive Variance Inflation in Thompson Sampling: Efficiency, Safety, Robustness, and Beyond
Authors: Feng Zhu
David Simchi-Levi
Venue: NeurIPS 2025 poster ()
Keywords: multi-armed bandit
variance inflation
Thompson Sampling
efficiency
safety
robustness
Primary area: reinforcement_learning

Abstract: Thompson Sampling (TS) has emerged as a powerful algorithm for sequential decision-making, with strong empirical success and theoretical guarantees. However, it has been shown that its behavior under stringent safety and robustness criteria --- such as safety of cumulative regret distribution and robustness to model mis-specification --- can sometimes perform poorly. In this work, we try to address these aspects through the lens of adaptive variance inflation for Gaussian Thompson Sampling. Our one-line change introduces a time- and arm-dependent inflation factor into the sampling variance, and yields several compelling benefits. The resulting policy achieves provably worst-case optimal expected regret and worst-case optimal fast-decaying regret tail bounds, even in the presence of heavy-tailed (sub-exponential) noise or mis-specified environments. The policy is also robust to mis-specified noise variances. Beyond cumulative regret, we further demonstrate that our method ensures strong post-experiment guarantees: simple regret and estimation error per arm exhibit fast-decaying tail probabilities, contributing to more reliable and robust downstream decisions. Finally, we extend our policy to incorporate settings with unknown arm-specific variances and empirically validate the consistent performance of our approach across a range of environments.

Adaptive Variance Inflation in Thompson Sampling: Efficiency, Safety, Robustness, and Beyond
Feng Zhu
David Simchi-Levi
Institute for Data, Systems, and Society Massachusetts Institute of Technology Cambridge, MA 02139
Institute for Data, Systems, and Society Massachusetts Institute of Technology Cambridge, MA 02139 dslevi eerii@@it tomit.ee edu
fengzhulmit.cc
Abstract
Thompson Sampling (TS) has emerged as a powerful algorithm for sequential Decision-making, with strong empirical success and theoretical guarantees. How- ever, it has been shown that its behavior under stringent safety and robustness criteria such safety of cumulative regret distribution and robustness model mis-specification - can sometimes perform poorly. In this work, we try to address these aspects through the lens of adaptive variance inflation for Gaussian Thompson Sampling. Our one-line change introduces a time- and arm-dependent inflation factor into the sampling variance, and yields several compelling benefits. The resulting policy achieves provably worst-case optimal expected regret and worst- case optimal fast-decaying regret tail bounds, even in the presence of heavy-tailed ssub-exponentia)) noise or mis- spiciifee environments. The policy is also robust to mis-specified noise variances. Beyond cumulative regret, we further demonstrate that our method ensures strong post-experiment guarantees: simple regret and estimation error per arm exhibit fast-decaying tail probabilities, contributing to more reliable and robust downstream decisions. Finally, we extend our policy to incorporate settings with unknown arm-specific variances and empirically validate the consistent performance of our approach across range of environments.
Introduction
The stochastic multi-armen bandit (MAB) problem is a foundational framework for sequential under uncertainty, with broad applications ranging from recommendation systems 277 to clinical trials [3 and financial portfolio optimization [16] A central challenge in MAB is balaneing exploration and exploitation. Among the many algorithms proposed to address this trade-off, Thompson Sampling (TS), originally introduced in [32], has emerged as both conceptually elegant and practically effective approach. a Bayesian method, TS selects actions based on samples drawn from the posterior distributions over arm rewards. By naturally balancing exploration and exploitation
through probabilistic sampling. TS enjoys near-optimal thcoretical guarantees (19] [ 2 24 3 25 20)
and demonstrates excellent empirical performance [TO 25 11. Its simplicity of implementation and strong empirical results have contributed to its widespread adoption real-world systems.
Despite its success, recent work has revealed notable limitations of Thompson Sampling, particularly regarding regret tail behavior [14 30 31 and statistical inference power (3
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-depenuent perspective. As result, it tends adapt quickly to perceived optimal arm and reduce exploration prematurely. This limited exploration can lead to sub-optimal performance on other critical dimensions, such as safety under heavy- risks and robustness to model mis-specification.
29 22
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

While efficiency (i.e., good expected outcome) remains central goal, safety (i.e., concentration of outcomes around the mean) and robustness (i.e., stability of both the mean and distribution with respect to hyperraraaeeter tuning and environmental mis-specification) are equally important for practical deployment. In this work, we revisit Thompson Sampling from the perspective of efficiency, safety, and robustness, and ask:
How can we modify Thompson Sampling achieve efficiency, safety, and robustness, ensuring strong performance both during and after an experiment?
1.1 Our contributions
Our work makes both methodological and practical contributions. We propose Thompson Sampling with Variance Inflation (TS-VI), simple yet effective extension of Gaussian Thompson Sampling that inflates the posterior sampling variance using a carefully designed time- and arm-dependent factor, with the goal of achieving strong theoretical guarantees and robust empirical performance particularly in settings that involve multiple tasks and require safe decision making. decision-making.
Within- experieee regret control. We show that TS-VI achieves a worst-case optimal cumulative regret tail decay rate of exp(-Q(x/v//))
where x denotes the regret threshold. As a corollary, its worst-case expected regret grows at the optimal rate of Ó (K)). Moreover, we demonstrate that TS- VI is robust: maintains these performance guarantees even under mild mis-specification of policy
and environmental conditions.
Post-experiment decision quality. We establish that TS-VI facilitates high-quality post-experiment decisions. Specifically, both the simple regret (in best-arm identification) and the per-arm estimation error (in mean reward estimation) exhibit fast tail decay and optimal expected error rates. Our analysis further implies that TS-VI promotes exploratory behavior in worst-case environments.
Simulation validation and practical refinement. We complement theoretical results with numerical simulations, demonstrating that TS-V VI is efficient, safe, and robust across diverse environments. To handle unknown arm arm-specific variances in practice, incorporate Gamma-Normal Bayesian updates into our design and show that this amendment preserves the stability and effectiveness of the policy.
1.2 Other Related Work
Safety and robustness in bandit algorithms. Recent work has increasingly focused on understand- ing the safety and robustness of bandit algorithms, particularly in the context of within-experiment regret. Farly studies by (6 26 showed that regret concentration typically occurs only at polynomial rate. More recently, 4 demonstrated that bandit algorithms targeting logarithmic expected regret can be fragile: a mis-specified risk parameter (e.g., the sub-Gaussian noise level) can lead to instance- dependent regret growing polynomially in T. Building on this line of work, [4] 30 established that standard bandit algorithms achieving instance-dependee
Õ(1) regret such as TS and its variants can suffer from poor tail behavior: the probability of incurring large regret decays slowly with the time horizon. [30] also show that this tail performance can be significantly improved under worst-case design. Further, (31) offers a comprehensive characterization of the trade-off between expected regret and tail risk, shedding light the intrinsic tension between efficiency and safety.
Bandit experimental design. There is also growing literature on understanding the quality of pnst-experiment decisions in bandit settings, shifting focus from cumulative regret to final outcomes.
In best-arm identification [3 & 17 28 36 35). a commonly used performance measure is simple regret, introduced by 77]. which quantifies the gap between the optimal arm's 's mean and the selected arm's 's mean. This contrasts with the probability of selecting a sub-optimal arm [5). metric that is highly sensitive to the smallest sub-optimality gap [9] and often becomes meaningful only at
it has been shown that standard bandit policies achieving instance-dependent Õ(1) regret often perform poorly due to insufficient exploration of sub-optimal arms. Much of this literature has focused on minimizing the estimation error in expectation or constructing (anytime) valid confidence intervals. However, questions of decision safety and robustness in these post-experiment settings remain largely unexplored.
large sample sizes. For mean estimation tasks 12 29 34

---

Before proceeding, we introduce some other notations. Throughout the paper. we use O(-) (Ó(-) and ())) (9)()) to present upper and lower bounds on the growth rate up to constant (logarithmic) factors, and (-)) (O(-) characterize the rate when the upper and lower bounds match up to constant (logarithmic) factors. We use o(-) to present strictly dominating upper bounds. In addition, for any a. b E R. A b- min(a, b) and V b max(a, b). For any a E R. a+ max(a,
2 Model and Setup
Let the number of arms be K. In each time f 1, 2....... the decision maker (DM) needs to decide which arm d, E [K] should be pulled. To be more precise, let H, = {a1, "",,,',,.. , -0--1 1.e-1:7 1t be the history prior to time I. When = 1, H1 = 0. In time the DM adopts a policy ग. : H, + 0e that maps the history H, to an action dg, where follows discrete probability distribution Ty (ax) H2) on [K]. The environment then reveals an independent reward Tr,a, = Pa, + Ét,a, to the DM. Here, Pa: is the mean reward of arm de, and 6r,o, is independent zero-mean noise term. We assume that Et,os is (a, wwwssss-e-ppoeeeee nub-exxponettil.. That is, for any time t and arm k,
< E [exp(Aer,N)] I exp (APo2/2), AY: 1A:AA<<1/ 1/v.
Let μ1 (MI,.... [Kk) be the mean vector. Let ju+ max(un.... : .K)) } be the optimal mean reward among the K arms. Note that DM does not know ju at the beginning. Let A = μe, - P4k be the gap between the optimal arm and the kth arm. For theoretical analysis, We assume A S 1 (which is not necessarily known by the DM). Let I be all E I K such that | S 1. Let 12.,k be the number of times arm & has been pulled prior to time t. That is, de, E lfa = k}. We additionally define & (n) as the time period that arm & pulled for the nih time. Let ft,E be the empirical mean of --1
arm k prior to time t. That is, ir = E r. (a, = k)/ //=/
==1 [a, = k) = => 5 Pea(s)/Ne,.-
2.1 Evaluation metric
Denote & (rx; o, v) as the environment parameter. Fix a time horizon T > K (which may not be known a priori by the DM). We are interested two types tasks - -xpriiet regret control and post-experiment decision quality, illustrated as follows.
Within-experiment regret. Define the cumulative regret of policy under the environment up to time T as
K
(T(T) Σ (px Mai) Σ k=1
NT+1&
1=1
For simplicity, we write (T') instead of (T), but we need to keep in mind that I2, is depen- dent on the environment profile. We are interested in studying the efficiency metric supper E. B (T) and the safety metric sup ((R ) > x) for large æ, and the robustness of these two metrics with respect to mis-specified policy hyper-parameter and environment parameters (such as (a, v)).
Post-experiment decision. We are interested in two post- post-exppriment decisions: best arm selection and mean estimation.
Best arm selection. After T steps, the task is to select an arm az. such that Aap. is as small as possible. In particular, we are interested in studying the efficiency metric supper [[[a;]] and the safety metric supper P(Aa;. > y). and their robustness to policy hyper-parameters and environment parameters.
Mean estimation. After T steps, the task is to estimate the true mean of each arm such that the error is as small as possible. In particular, we are interested in studying the efficiency metric supper E[llĀT+1 =1l33, and the safety metric supper [P[]@T++1 - =1113-11 > y). and their robustness to policy typer-parameters and environment parameters. Here 4r++1 is the estimated arm mean vector after the experiment.
Remarks on the worst-case analysis. The rationale for focusing on the worst-case scenario is twofold. First, worst-case analysis provides strong, uniform guarantees that hold across all environments. In particular, allows us to investigate policy robustness with respect to both the mean reward vector and the broader environment profile (a, v). In contrast, instance-dependen optimal policies are often fragile, exhibiting unsafe and highly sensitive behavior in both within- and eost-experiment performance [14 30 29)
3

---

Second, from practical standpoint, the DM can only observe empirical quantities namely, the cumulative reward and the sample mean of each arm:
Σ
r TT+LAM
Ct
and
(l)
Pk
(t)
TecK
t=1
The noise terms in both expressions are generally not controllable by the decision-manl maker. While these terms vanish in expectation, they remain significant when considering tail probabilities of high cumulative regret or large estimation error. In such cases, it is meaningful to focus on thresholds of the form x = ((VT) or = 2(11vT)) as any threshold below these (c.g. I = o(vT). = o(1/vT) will typically be dominated by the noise, rendering tail bounds ineffective uninformative.
2.2 Thompson Sampling with adaptive variance inflation
We present Gaussian Thompson Sampling (TS) Algorithm and introduce our one-line modifica- tion, TS with Variance Inflation (TS-VI), in Algorithm 2 Both algorithms follow Bayesian updating framework that corresponds to placing an improper prior on each arm, p(us)) o 1 (or, approximately, weakly informative prior μ4 ~ (O, o²) with a + xc), and assuming the reward distribution for arm & is Gaussian: F₁ N (pu of) (see, e.g.. [8]. The key distinction in TS- VI (Algorithm? 2 is that each posterior sample is drawn from Gaussian distribution whose variance is inflated relative to the standard posterior variance o Rt, by an adaptive factor t/(Kn,,)). Importantly, this inflation
affects only the sampling distribution; the Bayesian posterior update remains unchanged.
Algorithm TS
Algorithm 2 TS-VI
[K]. . 2: Pull each arm once.
1: Input:
1: Input: A [K], og-
2: Pull each arm once.
3: for / = K I,... do
3: for = K + 1.... do
4: For each arm k, draw random sample
4: For each arm k. draw a random sample
X1,6 ~ N [in. 1
Dekk ob
(1)
Ne.6 ~ N -
(
où [ie
1/K ni
(2)
5: Take action ag = arg max (e,b).
5: Take action 0r = arg Maxe (XLA).
Collect reward rr,a. = Ma, + EL
6: Collect reward rt,oz Mu. + Ceor
7: end for
7:
end for
3 Within-experiment regret
In this section, we study the safety and robustness behavior of TS-VI. Our goal is to build safety guarantees for the tail distribution of cumulative regret I27 Starting from the safety result, we also build guarantees for efficiency (low expected regret) and robustness (robust regret tail distribution).
3.1 Main results
Theorem (Within--xpprrmment regret) Fix dg and (a, v). Define M(oo; = 1Vog (ave)
There exists absolute positive constants e and C such that for any 2 o we have
sup P RR (T) > x) & exp (-c M
x
eer
We provide a brief discussion the proof for Theorem T and highlight how address the proof challenges. Without loss of generality, we assume that arm 1 the optimal arm. The proof is based on the fact that for any time a sub-optimal arm & is pulled, we have
Vt/K S1.1 S fun,
Vt/K
Eo,k
11,6

---

A 2
Rik Li=l
CLK
Vt/K Re.k
Σ
(e
Vi/K
A
+
S
(3)
71,11
2
To establish the desired bound, it suffices to control the probability of each of the two events in (3) However, there two main challenges that render the techniques in 30 31 insufficient for
setting.
The first challenge lies in relating A and & to the time index t and the regret threshold in way that yields the desired tail decay dependence on I, K, and T simultancously. This is nontrivial because &t,& and & are inherently intertwined. We address this by carefully designing regret decomposition, showing that the cumulative regret reaches level z, then As must satisfy a precise lower bound that depends on K, T, and tx (n), and meanwhile, P1r+1,6 must be sufficiently large.
The second challenge arises from the noise term Et,k+ which is mean-zero random variable beyond the DM's control. This term could cause the second event in 33) to occur with non-negligible probability. To handle this, we analyze multiple values of collectively: when 1.T is large enough, there exists - with high probability
at least one time ł at which arm l is pulled and εt,1 exceeds fixed constant 1j > 0. However, care must be taken in selecting the range of t considered - smaller t leads to smaller /t/K, which weakens the tail bound. Thus, bounding the overall tail probabilities is delicate, and we defer the full technical details to the supplementary material.
3.2 Implications
Efficiency. Theorem iimplis that the expected regret of is-VI In where in O()) we are hiding a constant factor. In fact, we have that
sup E| (T)) S 2 + sup NET
P (R x)) dz S (2c C)M
WET
The expected regret bound worst-case optimal on both K and up to a logarithmic factor. We would like to point out that in contrast to most approaches taken in the literature that obtain expected regret bound, the approach we take here is to first derive regret tail bound and then yield guarantee in expectation. While the current work is not trying obtain the best dependence on logarithmic factors, it would be interesting to see whether and how these logarithmic factors can be removed.
Safety. Theorem I gives the optimal regret tail decaying rate. As is shown by 30 through two- armed bandit case, for the family of policies that obtains the worst-case expected regret performance guarantee Ö Ö(VT), the tail probability PRR (T) > x) cannot be decaying faster than exp( /T) for large While 30 31 only consider UCB-like deterministic policies, our result show that the standard TS policy, as randomized policy, can also be amended to achieve the desired optimal safety
guarantee.
Robustness. Lastly, we would like to emphasize the robustness performance of TS-VI, which can be of great importance in practice. Note that our policy is almost parameter-free (the only input parameter is K and og) without assuming any knowledge the distribution of the environment.
Knowledge of K. Typically K is known to the decision-matee utilized in variance inflation, we can derive worst-case guarantee similar to that in Theorem with sub-optimal dependence Ö(K (T). In other words, the 1/K factor in the variance inflation term is "recommended" scaling parameter that makes sure the worst-case rate has an optimal dependence on K.
If K is not known a priori or not
K (but not T) by setting o / VKog, the expected regret becomes
Robustness to hyperparameter dg. TS-VI is robust to mis-specified do. in the sense that for any do (as long it is positive), we can always achieve the optimal regret tail decaying rate as well as the optimal regret expectation growing rate, with only constant factors affected. Apparently, if we have prior knowledge on a and v (say in the sub-gaussian case we know a and we know that v/ = 0), we can set ou V obtain better constant factors. In Section [ we will examine selection of do under various situations.
Robustness to environment mix-specification. A feature of our result is that we consider sub- exponential environment, where the reward tail can heavier than that from a sub-gaus gabssaann distri- bution. Regardless of whether the environment is sub-gaussian or sub-exponential, TS-VI does not
5

---

require any knowledge on environment profiles, and each random sample is drawn from a Gaussian distribution (instead of Seavier-tailed distribution that caters to the environment). As we will empirically show in Section 5 standard TS and some of it variants can lead to high hidden risk in the tail region under an exponential environment, while our policy can significantly alleviate the issue.
Post-experiment decision
In this section, we study the safety and robustness behavior of TS-V "'S-VI for two types of post-experiment decisions. Our goal build theoretical safety guarantees for the tail distribution of simple regret Day and estimation error | palloo Starting from the safety result, we build guarantees for efficiency (low expected simple regret and low expected estimation error) and robustness (robust simple regret tail distribution and robust estimation tail distribution). Our analysis also provide deeper insights on the exploration behavior of TS-VI.
For any 7 2 K, we adopt the following decisions: (a) Best arm selection We select the arm that is pulled the most often in the second half of the time horizon: 0zz arg max (1 71//21+1,8) (b) Mean estimation. For each arm k, we simply take the empirical mean Pr+1k
4.1 Main results
Theorem (Post-experiment best arm selection) Fix do and v). There exists absolute con- stants C1, C1 0 such that for any y 2 c1 Mooouo, / In K InT
have
y
T
sup PP (Da; > S exp
(T
K
WET
Theorem (Post-experiment mean estimation) Fix oy and (o, v). There exists absolute constants
C22 C2 dependent only on do and (o, such that for any y 2 22v K T
In T, we have
U C2
T
sup P (llĀT+1- - -1l3 > v) exp pET
K
The proof of Theorem 2 is based on Lemma] which indicates that the number of times that each sub- optimal arm is pulled for Q(T/K) times is exponentially decaying with respect the sub-optimality gap Ag. Intuitively, for the second half of the whole time horizon, with very low probability that TS-VI continuously exploring or even sticking to any sub-optimal arm. Since we are selecting the arm that is pulled the most often, Theorem then follows.
Lemma There exists absolute positive constants d; C₁ such that for any k and A d M v,v) (,)
K Kla
T I exp (-o;
AK
T
P BT+LK B67 > 2K
Mi
K
The proof of Theorem 3 is based on Lemma which shows an interesting fact that TS-VI with very high probability explores each sub-optimal arm with at least 9 (TVK)) times. Intuitively, TS-VI circumvents tail risk by inflating the variance and doing more exploration. Since the worst-case expected regret is Õ(VKT) (followed from Theorem J this leaves enough space for TS-VI to explore each arm on average for 22 (T/K) times, which leads to more estimation accuracy shown in Theorem 3
Lemma There exists positive constants dg C2 dependent only on do. (a, v) such that for any have
T P MT+Lk < 22 K
T
< exp

---

4.2 Implications
Efficiency. Theorem implies that the expected simple regret of iS O(VK/T), and Theorem
shows that the expected deviation between the empirical and true means is also O( K/T). Both results follow from similar arguments as the expected regret bound in Theorem []] These bounds worst-case optimal in their dependence on K and T, up logarithmic factors (see, e.g., [5] 29
In particular, for Theorem 3 the Õ(1/VT) rate is known to be optimal for any policy achieving expected regret Õ(vT)
29
Safety. Unlike prior works (e.g.. (291) that focus solely on expected performance, Theorems 2 and also provide exponential tail bounds for simple regret and estimation error, respectively, offering reliability guarantees for decision quality. These are obtained by first deriving tail bounds - similar in spirit to Theorem D and then translating them into expectation bounds. It remains open question whether the logarithmic factors these results can be improved or removed.
Robustness. TS-V also exhibits robustness to both the prior variance do and environmental mis- specification. While additional environmental knowledge may improve empirical performance. incorrect assumptions only affect constant factors, without changing the asymptotic efficiency loss or tail decay rates.
Numerical Experiments
We conduct numerical experiments the 2-armed bandit case to illustrate the benefits brought by our policy. The mean vector fixed as μ = (-6, 6) with 5 = 0.3. We focus on empirical metrics:
(a) expected regret t;
(b) log tail probability of cumulative reward < 0 vs. f;
(c) mean absolute estimation error per arm vs. t;
(d) log tail probability of absolute estimation error > vs.
For each policy considered below, we collect 10t trajectories. In (a) and (c), we also show the error bars (95% confidence interval) for the expected regret and the mean absolute estimation error. In the supplementary material, also provide experiments for 5 0.5, and a 6-armed bandit case study with 0.3, 0.5.
5.1 Environments and Results
Well-specified environment with known variances. We first consider Gaussian environments where the noise variances are correctly specified. We consider o² 2 for both arms. Results are provided in Figure T
For both TS and TS-VI, we assume the prior is No0 10a)
We consider the standard TS (ap = =o), a slightly under-specified TS (a. = 0.9o), and a slightly over-specified TS (ao 1.1r).
For TS- VI, consider σo 0.3or 0.4o, 0.5g less than the true yields empirically stronger performance.
empirically find that a being slightly
We also consider the UCB policy with the bonus term du 2n 15 where = 0.9g
(slightly under-specified), do 1.0g (standard), 1.1a (slightly over specifiee...
Mis-specified environment with known variances. We then consider Exponential environments with Laplacian noises - that is, the probability density function is (26) exp(-Iar/ We consider
b 1 for both arms. Note that the variance of Laplace distribution 262, Results are provided in Figure 2]
For both TS and TS-V VI, we assume the prior is ((0 10
For TS and UCB, we treat each sample as if is drawn from a Gaussian distribution (0, 2).
We consider do = 0.9g, 1.0or, 1.1o.
7

---

T5-0.9
TS-1-0.3
UCB-0.9
T549
TS-V-0.3
UCB-0.9
15:
TSMBC-
regret)
100
T5-11
T5V1-0.5
UCB-1.1
-1.0
T511
TSVV-S
UCB-1.1
00
-1.
60
2.0
-5
-2.0
-3.
-4.0
2000
4000
6000
6000
10000
2000
4100
6000
8000
10000
Time step
Time step t
T5-09
TS-V-0.3
UCD-0.9
0.0
T5-0.9
T5460.3
UCB-0.9
T5:10
UCB-1-0
T5-1
TSVI-4
UCB-1.0
arror]
1.0
T5-11
TS-10.
UCB-1.1
-0.5
Pljestimation
0.6
0.-
-2.0
step
Figure 1: Results for the well-specified environment with known variances
For TS-VI, we consider do 0.3o, 0.4o, 0.5gr
Mis-specified environment with unknown heterogeneous variances. Finally, we consider Exponen- tial environments with noises following unknown Laplace distributions. We consider =1, 1, 2. We focus exclusively on TS and TS-V IT-VIin in this environment. Results are provided in Figure
Since variances unknown, adopt the Gamma-Normal TS where the variance of each arm of modeled following an inverse Gamma distribution. The detailed paradigms of Gamma-Normal TS and its inflated version provided in the supplementary material.
For TS, we treat each sample as it is drawn from Gaussian distribution (O, of). The sampling variance is taken do.k 0.90%, 1.00k, 1.10k.
For TS-VI, we consider 0o = 0.30 0.4 0.50p.
5.2 Observations and Implications
Efficiency. Across all environments, TS and UCB consistently exhibit lower expected within- experiment regret compared TS-VI under various hyperparameter settings. This expected, as TS-VI encourages greater exploration than TS, leading to more frequent pulls of sub-optimal arms consistent with Lemma However, we also observe that for smaller time horizons (e.g., 7 S 1000), the performance gap narrows and in some cases, TS-VI even achieves lower expected regret than TS and UCB. For larger horizons such as T 10000, the increase in expected regret under TS-VI remains moderate, generally ranging from 20 to 100 (or 20 to 40 for TS-VI-0.33 This controlled sacrifice in regret is compensated by markedly improved estimation accuracy. In particular, across all settings, TS-VI VI consistently yields lower mean absolute estimation error compared to TS and UCB.
Safety. In terms of tail risk both for within-experiment regret and post-experiment decision TS-VI significantly outperforms TS and UCB. The empirical probability of incurring negative cumulative reward or large estimation error for the best arm under TS-V decays rapidly, typically approaching zero by T x 5000 (and in many cases as early as T ~ 2000). TS-V VI also substantially mitigates the risk of large estimation errors for sub-optimal arms, whereas TS and UCB exhibits much slower tail decay.

---

120
T509
TS-V-0.3
UCB-0.9
Elcumuistive regret)
100
-1.0
-0.5
T511
15:
TSVFCS
UCB-1.1
00
-13
logse Picumulatss
-2.0
2.5
-3.0
T
UCB-0.9
T5-10
TS-W-0.1
UCB-1.0
-3.
15-11
TS-V..
UCB-1.1
-4.0
2000
4000
6000
6000
0000
2000
4100
6000
8000
10000
Time step
Time step t
1.2
T5-0.9
T5-1.0
TS-V-04
T5-V-0.3
T5-0.9
T5-1
TSV1-4
UCB-1.0
UCB-0.9
TS/VIC.5
-0.5
T5:1
TSVI0.
Pljestimation
-1.0
0.6
0.4
-15
0.2
-2.0
step
step
Figure 2: Results for the mis-specified environment with known variances
Robustness. TS- VI demonstrates stable performance across different hyperparameter settings and environmental conditions, both in terms of efficiency and safety, validating the theoretical results presented in SectionsBaandp In contrast, while TS reliably achieves low expected regret within an experiment, it consistently underperforms on the other three metrics: estimation accuracy, tail safety, and robustness. Notably, safety performance of either TS or UCB deteriorates significantly the presence of environment mis mnisspeciiicatiins.
Finally, we would like to provide additional remark on the performance of TS and UCB under under-specified (oo 0.9o) and over-specified (op = 1.1o) variances.
For under-specified policies, while they perform well in terms of expected regret, they suffer significantly in terms of tail safety and mean estimation accuracy.
For over-specified policies, they show slightly worse average regret but improved tail behav- ior and mean estimation. However, tail decay remains slow T grows, suggesting that while empirical gains are possible via over-specification, achieving intrinsic improvement in safety necessitates explicit variance inflation. We also discuss this point via a distribution visualization in the supplementary material.
6 Conclusion
In this work, we propose TS-VI, I, a modified version of Thompson Sampling in which the sampling posterior variance inflated by an adaptive factor. We show that TS-VI achieves efficiency, safety, and robustness in the worst-case setting, both for within-experiment regret control and post-experiment decision quality. These theoretical findings are validated through simulations, and we further extend the policy design to handle heterogeneous, arm-specific variances via Gamma-Normal Bayesian updates. Several promising directions remain for future investigation, and we highlight three below:
desteeet analysis. While this work focuses primarily worst-case performance, it would be insightful to conduct an instance-dependent analysis. It remains unclear whether safety and robustness guarantees established here continue to hold under such perspective. An instaece-dependent view may offer more nuanced understanding of how efficiency, safety, and robustness interact and trade-off with each other in different environments.

---

120
T5-0.9
T5-1-0.3
-0.3
T5-09
TS-V-0.3
regret)
T5-11
T5.1-0.5
-1.0
TS-11
TS-V-0.5
80
-15
Pcumulltivv
-2.
40
-30
-1.
-4.0
2000
4000
6000
8000
00000
2000
4100
6000
8000
10000
Time step
Time step t
T5-0
TS41-0.3
0.0
T5-0.9
TS-V-0.3
1.75
T5-10
TS-V-0.44
T5-10
TS-V-0.4
Elsstiatten arorr]
1,50
1.25
Pllestimation
1.00
-1.3
0.75
-1.
0.50
0.25
-2.0
0.00
step
Figure Results for the mis-specified environment with unknown variances
Asymptotic behavior. Our theoretical results provide finite-time error bounds for various within- and post-experiment objectives. However, questions remain about the asymptotic behavior of TS-V VI for example, what is the limiting proportion of times each arm is pulled? A deeper analysis of the long-run behavior could yield sharper characterizations of the policy and offer principled guidance for hyperparameter tuning.
More complex models. This work focuses on the standard stochastic multi-armed bandit setting. Extending our approach to more complex frameworks such as linear bandits, nonparametric models, and Markov decision processes - both challenging and worthwhile. is also important to investigate how the presence of heavy-tailed reward distributions (beyond sub-exponential) affects the performance guarantces and policy behavior.
References
[1] S. Agrawal and N. Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
[2] S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR, 2013.
[3] Agrawal and N. Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1-24 2017.
[4] K. Ashutosh, J. Nair, A. Kagrecha, and K. Jagannathan. Bandit algorithms: Letting go of logarithmic regret for statistical robustness. International Conference on Artificial Intelligence and Statistics, pages 622-653 630. PMLR, 2021.
[5] J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits. In COLT-23th Conference on learning theory-2010, pages 13-p. 2010.
[6] J.-Y. Audibert, Munos, and C. Szepesvári. Exploration-exploitttio tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 110619):1876-11002 2009.
10

---

[7] S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in mullii-rmee bandits problems. In International Conference on Algorithmic Learning Theory, 2009.
[8] Bubeck, R. Munos, and G. Stoltz. Pure exploration in finitely-armed and continuous-armed bandits. Theoretical Computer Science, 412(119:1832-1888 2011.
[9] A. Carpentier and A. Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference on Learning Theory, pages 590-604, PMLR, 2016.
[10] O. Chapelle and L. Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.
[11] D. Eckles and M. Kaptein. Bootstrap thompson sampling and sequential decision problems in the behavioral sciences. Sage Open, 902):1582440198511677 2019.
[12] A. Erraqabi, A. Lazaric, M. Valko, E. Brunskill, and Y.-E. Liu. Trading off rewards and errors in multi-armed bandits. In Artificial Intelligence and Statistics, pages 709-717. PMLR, 2017.
[13] E. Even-Dar, S. Mannor, and Y. Mansour. Pac bounds for multi-armed bandit and markov decision processes. In Computational Learning Theory: 15th Annual Conference Compula- tional Learning Theury, COLT 2002 Sydney, Australia, July 8-10, 2002 Proceedings 15, pages 255-270. Springer, 2002.
[14] L. Fan and P. W. Glynn. The fragility of optimized bandit algorithms. Operations Research, 2024.
[15] A. Garivier and Cappé. The kl-ueb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
[16] X. Huo and Fu. Risk-aware multi-armed bandit problem with application portfolio selection. Royal Society open science, 4(1 1(111377377 2017.
[17] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. lil'ueb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439, PMLR, 2014.
[18] T. Jin, P. Xu, J. Shi, X. Xiao, and Q. Gu. Mots: Minimax optimal thompson sampling. In International Conference on Machine Learning, pages 5074-5083. PMLR, 2021.
[19] E. Kaufmann, N. Korda, and R. Munos. Thompson sampling: An asymptotically optimal finite-tima analysis. In International conference algorithmic learning theory, pages 199-213. Springer, 2012.
[20] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[21] B. Liang and I. Bojinov. An experimental design for anytime-valid causal inference on multi- armed bandits. arXiv preprint arXiv:2311.0579. 2023.
[22] C. Qin and D. Russo. Optimizing adaptive experiments: A unified approach to regret minimiza- tion and best-arm identification. arXiv preprint 10X55 2024.
[23] D. Russo. Simple bayesian algorithms for best arm identification. In Conference on learning theory, pages 1417-1418. PMLR, 2016.
[24] D. Russo and B. Van Roy. An cntemmation-theoreee analysis of thompson sampling. Journal of Machine Learning Research, 17(68):1-33 1-00, 2016.
[25] D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[26] A. Salomon and J.-Y. Audibert. Deviations of stochastic bandit regret. In International Conference Algorithmic Learning Theory, pages 159-173. Springer, 2011.
[27] N. Silva, H. Werneck, T. Silva, A. C. Pereira, and L. Rocha. Multi-armed bandits in recom- mendation systems: A survey the state-of-the-ard and future directions. Expert Systems with Applications, 197:1 16669, 2022.
11

---

[28] D. Silver. A. Huang, J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam. M. Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, nalure, (2997787)44844495 2016.
[29] D. Simchi-Levi and C. Wang. Multi-armed bandit experimental design: Online decision-making and adaptive inference. Available at SSRN 4224969, 2022.
[30] D. Simchi-Levi, Z. Zheng, and F. Zhu. A simple and optimal policy design for online learning with safety against heavy-tailed risk. Advances in Neural Information Processing Systems, 35:33795-33805, 2022.
[31] D. Simchi-Levi, Z. Zheng, and F. Zhu. Stochastic multi-armed bandits: optimal trade-off among optimality, consistency, and tail risk. Advances in Neural Information Processing Systems, 36:35619-35633 2023.
[32] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4) 1933.
[33] S. S. Villar, Bowden, and J. Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
[34] I. Waudby-Smith, D. T. Arbour, R. Sinha, E. H. Kennedy, and A. Ramdas. Time-uniform central limit theory and asymptotic confidence sequences. The Annaly of Statistics, 2021.
[35] Yang, Y. Tan, and Jin. Best arm identification with minimal regret. arXiv preprint MwXi::240911809, 2024.
[36] Y. Zhao, C. J. Stephens, C. Szepesvari, and K.-S. Jun. Revisiting simple regret: Fast rates for returning a good arm, In International Conference on Machine Learning, 2022.
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims are correctly reflected via theory and experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Provided in Section 0
13

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Provided in model, proof idea and supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Provided in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Code provided in supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ 7/nips. /ttppp.cc/pbllc/guideeee http://oeeuuiiisssoooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting//etails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Provided in Section Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: The paper investigates tail distributions and runs 10000 samples for each environment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-simma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
16

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp://bourrpp..ccpuul/////ibi
Answer: [Yes]
Justification: N/A
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper poses such risks.
17

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: N/A
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLM is used only for polishing paragraphs and speeding up experiments.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
19


Reviews:
[{"review_id": "c5oyplg0Y0", "reviewer": "Reviewer_vVC8", "summary": "This paper proposes a modification of the well-known Thompson Sampling method to balance efficiency, safety, and robustness both during and after an online learning experiment in the multi-armed bandit setting. The authors consider three key evaluation scenarios for these metrics: i) within-experiment cumulative regret $R\\_T$, ii) post-experiment best-arm selection regret $\\Delta\\_{\\hat{a}\\_T}$, and iii) post-experiment mean reward estimation $\\hat{\\mu}\\_{T+1}$. The proposed method, TS with Variance Inflation (TS-VI), differs from standard Gaussian TS through a slight modification of the variance term in the sampling step, designed to encourage greater exploration.\n\nRather than deriving bounds on the expected values of these metrics for specific environmental hyperparameter settings (eg, subexponential noise parameters and reward means), the authors first establish (in Theorems 1, 2, and 3) uniform upper bounds on the tail probabilities of these metrics across a set of mean rewards, i.e., $\\sup_{\\mu \\in \\Theta}\\mathbb{P}(\\texttt{metric} > x)$. These bounds serve as a proxy for safety and, in turn, enable the derivation of bounds on the expected values of the metrics, serving as a proxy for efficiency. The authors further argue that the asymptotic bounds are robust to misspecification of environmental parameters, as their effect appear only as constant factors.", "questions": "1. What exactly is the set $\\Theta$?\n\n2. What is the precise dependence of the constant factors in your bounds on the environmental hyperparameters?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The proposed algorithm is a straightforward modification of Thompson Sampling and can be easily implemented.\n2. The uniform tail probability bounds on within-experiment regret and post-experiment decision quality provide a more comprehensive framework for analyzing the performance of such algorithms from multiple perspectives (e.g., safety, robustness, and efficiency).\n3. The results are clearly stated and well organized.\n\nWeaknesses:\n1. 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.\n2. 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.", "was_revised": true, "final_justification": "Rebuttal addressed some of my questions. I keep my score the same because I cannot assess the paper properly given that I am not an expert in this field and unfamiliar with the literature. So my assessment does not cary as much weight.", "rebuttal": "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.*\n- 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.\n\n2. *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.*\n- 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.\n\n3. *What exactly is the set $\\Theta$?*\n- $\\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.\n\n4. *What is the precise dependence of the constant factors in your bounds on the environmental hyperparameters?*\n- 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."}, {"review_id": "L25xSf4af9", "reviewer": "Reviewer_3uyB", "summary": "This paper proposes Thompson Sampling with Variance Inflation (TS-VI), a modification of Gaussian TS that inflates the posterior sampling variance by a time- and arm-dependent factor `t/(Kn)`. The key contribution is achieving simultaneously optimal expected regret, optimal regret tail decay, and strong post-experiment performance for both best-arm identification and mean estimation tasks. The authors provide theoretical guarantees showing that TS-VI maintains robustness to hyperparameter misspecification and environmental conditions, including heavy-tailed (sub-exponential) noise. The approach is validated through numerical experiments on multi-armed bandit problems under various noise conditions.", "questions": "1. Experimental validation lacks uncertainty quantification. Repeating trials with multiple random seeds and reporting standard deviations would strengthen the empirical claims.\n\n2. The experimental section would benefit from comparison with other baselines beyond standard TS, such as UCB or $\\epsilon$-TS [1].\n\n3. 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?\n\n**Reference:**\n[1] Thompson Sampling with Less Exploration is Fast and Optimal, ICML 2023", "limitations": "The *mistake in Theorem 3* (lines 812-815 in the appendix) should be corrected in the final version. \n\nThe work does not raise immediate ethical concerns.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1. **Quality:** \nThe theoretical analysis is comprehensive and technically solid, but the manuscript suffers from numerous notation inconsistencies and mathematical presentation issues that significantly affect readability. The writing feels somewhat hasty, and the paper would benefit from a careful revision to improve clarity and rigor in notation. For example:\n\n    * Line 102: `r_{t_k(n)} / n_{t,k}` should be `r_{t_k(s)} / n_{t,k}` (inconsistent summation index).\n    * Lines 115–118: Inconsistent notation between `\\mu^*` and `\\mu_*` (as used in line 96); the description “approximating the true optimal arm `\\mu^*`” is conceptually unclear.\n    * Line 121: `\\hat{\\mu}_{T+1}` lacks an arm subscript, and the expression  `\\left\\|\\hat{\\mu}_{T+1} - \\mu\\right\\|_\\infty^2 > y`\n      contains an extra delimiter in the original version.\n    * Line 214: `\\hat{a}^{*}_t` should be `\\hat{a}^{*}_T`.\n    * Algorithms 1–2: The loop should use `for t = 1 to T` instead of starting from `K+1`. Since the only difference between TS and TS-VI is the variance term, the two algorithms could be merged into one with a parameter to control the variance setting.\n\n 2. **Clarity:**\n   Overall, the paper is readable, and the regret analysis appears reasonable. Adaptive variance inflation forces each arm to explore suboptimal arms more and to be sampled at least `\\Omega(\\sqrt{T/K})` times. *The reviewer acknowledges a limited prior background in the safety and robustness literature and is therefore not fully confident in evaluating the appropriateness of the analysis (section 4) from that perspective.*\n\n    Some conceptual descriptions are imprecise and impact readability. For example, in the discussion of post-experiment evaluation metrics (lines 115–118), the best-arm selection task is described as choosing “an arm `\\hat{a}^T` such that `\\mu_{\\hat{a}^T}` approximates the true optimal arm `\\mu^*` as close as possible.” This phrasing is conceptually unclear, as both `\\mu_{\\hat{a}^T}` and `\\mu^*` refer to true mean values. \n\n    It is recommended that the authors carefully review the paper and revise such language to improve conceptual clarity and ensure the presentation is precise throughout.\n\n3. **Significance:** \nThis work makes a meaningful contribution to our understanding of safety and robustness in TS, which has been underexplored despite TS's widespread practical adoption. The unified framework that addresses both cumulative regret and post-experiment decision quality is especially valuable for practical deployment.\n\n4. **Originality:** \nThe proposed variance inflation mechanism is novel and conceptually simple. The accompanying theoretical framework, which unifies efficiency, safety, and robustness through worst-case and tail analyses, offers new insights for the design of safe bandit algorithms.", "was_revised": true, "final_justification": "The authors have adequately addressed my main concerns. However, as I mentioned earlier, I find it difficult to assess the significance of the contribution in terms of safety and robustness. The paper and the rebuttal do not make this aspect of the work particularly clear to me. Therefore, I will maintain my current score with low confidence.", "rebuttal": "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.\n1. *Experimental validation lacks uncertainty quantification. Repeating trials with multiple random seeds and reporting standard deviations would strengthen the empirical claims.*\n- 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.\n\n2. *The experimental section would benefit from comparison with other baselines beyond standard TS, such as UCB or $\\epsilon$-TS [1].*\n- 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.\n\n3. *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?*\n- 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."}, {"review_id": "vVnnbW4MD6", "reviewer": "Reviewer_exTB", "summary": "This paper proposes a modification to Thompson Sampling by introducing a time- and arm-dependent inflation factor into the sample variance. The authors establish strong theoretical guarantees for the proposed policy, demonstrating that it achieves worst-case optimal expected regret as well as a worst-case optimal, exponentially decaying regret tail bound. Furthermore, the paper provides post-experimental theoretical guarantees to complement the proposed method.", "questions": "See Weaknesses.", "limitations": "See Weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- The proposed method is conceptually simple and easy to understand, while being supported by solid and rigorous theoretical guarantees.\n\nWeaknesses\n- 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. \n\n- 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.\n\n- The experimental evaluation raises several concerns:\n     - What happens if the hyperparameter $\\sigma_0$ is set equal to or larger than the true $\\sigma$? \n     - It would be beneficial to include experiments with $K > 2$ arms, as well as scenarios where $K$ is unknown to the learner.\n     - 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.\n    - $\\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.", "was_revised": true, "final_justification": "The authors have addressed my concerns. Accordingly, I increase my score.", "rebuttal": "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.*\n- 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.\n\n2. *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.*\n- 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.\n\n3. *What happens if the hyperparameter $\\sigma_0$ is set equal to or larger than the true $\\sigma$?*\n- 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.\n\n4. *It would be beneficial to include experiments with $K > 2$ arms, as well as scenarios where $K$ is unknown to the learner.*\n- 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.\n\n5. *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.*\n- 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.\n\n6. *$\\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.*\n- 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."}, {"review_id": "BEmwjShjBO", "reviewer": "Reviewer_TRXM", "summary": "The paper analyses a modification of Thompson Sampling for Sub-exponential noise. The proposed algorithm adds a boost to the variance of the posterior samples that adapt to the noise level. The paper provides a mean $\\mu$ independent, noise $(\\sigma,\\nu)$ dependent concentration result for the cumulative regret of their algorithm. (That does not require the knowledge of $(\\mu,\\sigma,\\nu)$) Additionally, they provide concentration bounds of the gap between the best arm and the estimated best arm, but also on the maximal estimation error of all the arms at the end of the experiment.", "questions": "- 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. \n\n- 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)\n\n- On the experiment side, I think one of the most important ones is missing. How do your performance metrics scale in $\\sigma,v$? 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.\nThis is, I think, very important, and I am willing to raise my grade if you do so.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strenght\n\nThe paper is well written, and the proofs seem correct. The result on the concentration of the regret and the post estimation of the parameter is very interesting and should be explored more in general. It provides a nice addition to the analysis of sampling-like algorithms. \n\n==============\n\nWeakness\n\nSome impressions should be corrected and are confusing: \n- The use of $O$, $\\tilde{O}$ and $\\Omega$.\n    - I believe that $\\tilde{O}$ notation should be avoided as it can be very confusing and can hide a lot. Especially the $\\tilde{O}(1)$ when talking about instant dependent regret, because it hides the dependency of the parameters. (The inverse of the gaps can be much larger than $\\sqrt{T}$)\n    - Line 172, I think that the $O$ notation should not leave out the variance $\\sigma$ of the noise nor the $\\sigma_0$ of the algorithm because it is a problem-dependent regret bound on $\\sigma,\\nu$ but not on $\\mu$. So I think it should keep those dependencies for a better understanding of the paper. \n    - Line 222 and 229,  in the $\\Omega$ the $\\sigma, \\sigma_0, v$ should be left apparent. \n\n- 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. \n\n- The number of experiments is missing, and no error intervals are shown in the experimental part. (The number of experiments appears in the checklist.)\n\n- 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 Page 207, Bandit Algorithms\nTor Lattimore and Csaba Szepesvári from. Furthermore, in the present paper, the noise is assumed to be fixed as only a sup on $\\mu$ is taken. \n\n==============\n\nMinor remarks\n\n- 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.", "was_revised": true, "final_justification": "The author properly addressed my concerns, and I raised my grade to 5. Provided the comparison of the cumulative regret distribution of different versions of TS is made in the main paper, and indeed shows an exponential concentration of the regret for this novel TS-VI algorithm compared to a more spread out cumulative regret for vanilla TS.\n\nThis special way of inflating the variance seems very interesting (If one is willing to trade the $log(T)$ term for a more robust algorithm). I am looking forward to seeing its expansion to other bandit settings, combinatorial, linear...", "rebuttal": "1. *The use of $O$, $\\tilde O$ and $\\Omega$.*\n- 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.\n\n2. *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.*\n- 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.\n\n3. *The number of experiments is missing, and no error intervals are shown in the experimental part. (The number of experiments appears in the checklist.)*\n- 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.\n\n4. *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.*\n- 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.\n\n5. *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.*\n- 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.\n\n6. *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.*\n- 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.\n\n7. *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)?*\n- 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.\n\n8. *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.*\n\n- 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."}]

Author rebuttal:

Meta-review: This paper proposes a modification to Gaussian Thompson Sampling (TS) by introducing an adaptive, time- and arm-dependent variance inflation factor. The resulting algorithm (TS-VI) is designed to balance efficiency, safety, and robustness in multi-armed bandits. The authors provide theoretical guarantees: worst-case optimal expected regret, exponentially decaying regret tails under sub-exponential noise, and robust behavior under variance misspecification. Beyond cumulative regret, the framework also ensures fast-decaying tails for simple regret and mean estimation error, making it attractive for both online and post-experiment performance. Empirical results on synthetic bandit problems, and extensions to scenarios with unknown variances.

The reviewers found the contribution technically substantial and conceptually simple, appreciating the unification of efficiency, safety, and robustness perspectives. However, multiple concerns were raised: (i) lack of clarity and notational inconsistencies, which sometimes affected readability (R3uyB, TRXM); (ii) limited experimental validation beyond synthetic scenarios, with requests for comparisons against broader baselines such as UCB and ε-TS (R3uyB, exTB); (iii) unclear intuition for the exact form of the variance inflation factor (RexTB); and (iv) insufficient discussion of practical significance for broader applications (RvVC8). The authors addressed many of these concerns in rebuttal, promising corrections to notational issues, distributional plots, additional experiments with mis-specified baselines. 

Overall, I recommend acceptance. The method is novel, technically correct, and supported by meaningful theoretical advances. While empirical evaluation could be further expanded, the promised additional results and clarifications will help increase the strength of the paper. Please incorporate the final suggestions of the reviewers in the camera-ready version as promised.
Decision: Accept (poster)