Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
Authors: Bingshan Hu
ZHIMING HUANG
Tianyue H. Zhang
Mathias Lécuyer
Nidhi Hegde
Venue: ICML 2025 poster (2025)
Keywords: bandits
Thompson Sampling
privacy
Primary area: theory->online_learning_and_bandits

Abstract: We address differentially private stochastic bandit problems by leveraging  Thompson Sampling with Gaussian priors  and Gaussian differential privacy (GDP). 
 We propose DP-TS-UCB, a novel parametrized private  algorithm that enables trading off privacy and regret. DP-TS-UCB satisfies $ \tilde{O} \left(T^{0.25(1-\alpha)}\right)$-GDP and achieves
 $O \left(K\ln^{\alpha+1}(T)/\Delta \right)$ regret bounds, where $K$ is the number of arms, $ \Delta$ is the sub-optimality gap, $T$ is the learning horizon, and
 $\alpha \in [0,1]$ controls the trade-off between privacy and regret. Theoretically, 
 DP-TS-UCB relies on anti-concentration bounds for the Gaussian distributions, linking the exploration mechanisms of Thompson Sampling and Upper Confidence Bound, which may be of independent research interest.

Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
Bingshan Hu
Zhiming Huang? Tianyue H. Zhang Mathias Lécuyer' Nidhi Hegde
Abstract
loss between the highest mean reward and the carned mean reward, is used to measure the performance of the algorithm used by the learning agent to make decisions.
We address differentially private stochastic ban- dit problems by leveraging Thompson Sam- pling with Gaussian priors and Gaussian differ- ential privacy (GDP). We propose DP-TS-UCB, novel parametrized private algorithm that en- ables trading off privacy and regret. DP-TS- UCB satisfies Ô (T9.25(1-a))-GDD and achieves O OK In (T))) (T) regret bounds, where K' the number of arms, Á is the sub-optimality gap. T is the learning horizon, and a E [0, 1] controls the trade-off between privacy and regret. Theoret- ically. DP- -E-TTS-UUB relies on mnticconcentaation bounds for the Gaussian distributions, linking the exploration mechanisms of Thompson Sampling and Upper Confidence Bound, which may of independent research interest.
Low-regret bandit algorithms should leverage past informa- tion to inform future decisions, as previous observations reveal which arms have the potential yield higher rewards. However, due to privacy concerns, the learning agent may not be allowed to directly use past information to make de- cisions. For example, a hospital collects health data from patients participating in clinical trials over time to learn the side effects of some newly developed treatments. To comply with privacy regulations, the hospital is required to publish scientific findings in a differentially private manner, as the sequentially collected data from patients carries sensitive information from individuals. The framework of differential privacy (DP) (Dwork et al., 2014) is widely accepted to pre- serve the privacy of individuals whose data have been used for data analysis. Differentially private learning algorithms bound the privacy loss, the amount of information that an external observer can infer about individuals.
1. Introduction
This paper studies differentially private stochastic bandit problems previously studied in Mishra & Thakurta (2015);
DP is commonly achieved by adding noise to summary statistics computed based on the collected data. Therefore, to solve private bandit problem, the learning agent has to navigate two trade-offs. The first one is the fundamental trade-off between exploitation and exploration due to bandit feedback: in each round, the learning agent can only focus either exploitation (pulling arms seemingly promising to attain reward) exploration (pulling arms helpful to learn the unknown mean rewards and reduce uncertainty). The second one is the prade-off between privacy and regret due to the DP noise: adding more noise enhances privacy, but it reduces data estimation accuracy and weakens regret guarantees.
Hu et al. (2021); Hu & Hegde (2022); Azize & Basu (2022); Ou al. (2024). In a classical stochastic bandit problem, we have fixed arm set [K]. Each arm is associated with fixed but unknown reward distribution p; with mean reward
H4. In each round, a learning agent pulls an arm and obtains a random reward that is distributed according to the reward distribution associated with the pulled arm. The goal of the learning agent to pull arms sequentially to accumulate as much reward as possible over finite number of T rounds. Since the pulled arm in each round may not always be the optimal one, regret, defined as the expected cumulative
'epparmment of Computer Science, University of British Columbia, Canada. 'Department of Computer Science, Univer- sity of Victoria, Canada. "nniversité de Montréal, Canada. 'Mila Quebec AI Institute, Canada. 'Department of Computing Sci- ence, University of Alberta, Canada. 6 Alberta Machine Intelli- gence Instribute (Amii), Canada. Correspondence to: Bingshan Hu <bingshanhu3 @ .mail.com>.
There are two main strategies to design (non-private) stochastic bandit algorithms that efficiently balance ex- ploitation and exploration: Upper Confidence Bound (UCB) (Auer et al., 2002) and Thompson Sampling (Agrawal & Goyal, 2017; Kaufmann et al., 2012b). Both enjoy good theoretical regret guarantees and competitive empirical per- formance. UCB is inspired by the principle of optimism in the face of uncertainty, adding deterministic bonus terms to the empirical estimates based on their uncertainty to achieve
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Connecting Thompson Sampling and UCB: Towards More Efficient Trade-off's Between Privacy and Regret
exploration. Thompson Sampling is inspired by Bayesian learning, using the idea of sampling mean reward models from posterior distributions (e.g.. Gaussian distributions) that model the unknown mean rewards of each arm. The procedure of sampling mean reward models can be viewed as adding random bonus terms to the empirical estimates.
reward model in each of the first & rounds. If arm i is still not pulled after & rounds, DP-TS-UCB reuses the highest model value among the previously sampled & Gaussian mean reward models in the remaining rounds until arm i is pulled again. Figure presents a concrete example of how DP-TS-UCB works.
The design of the existing private stochastic bandit algo- rithms (Sajed & Sheffet, 2019; Hu et al., 2021; Azize & Basu, 2022; Hu & Hegde, 2022) follows the framework of adding calibrated noise to the empirical estimates first to achieve privacy. Then, the learning agent makes deci- sions based on noisy estimates, which can be viewed as post-processing that preserves DP guarantees. Since both Thompson Sampling and DP algorithms rely on adding noise to the empirical estimates, it is natural to wonder whether the existing Thompson Sampling- based algorithms offer some level of privacy at no additional cost, without compromising any regret guarantees.
0
0
07
0
60
0
07
Of
0f
of
of
[+ +
7 0
Figure I. Cap the number of mean reward models sampled from a Gaussian distribution. Assume arm i is pulled in rounds I. t' and t", and & = 4. In each of the rounds t ...... + h...., f+ DP-TS-UCB samples a Gaussian mean reward model 0f and uses it in the learning for arm i. In each of the rounds reuses the highest model
Very recently, Ou et al. (2024) show that Thompson Sam- pling with Gaussian priors (Agrawal & Goyal, 2017) (we rename it as TS-Gaussian in this work) without any modifi- cation is indeed DP by leveraging Gaussian privacy mecha- nism (adding Gaussian noise to the collected data (Dwork et al., 2014)) and the notion of Gaussian differential privacy (GDP) (Dong et al., 2022). They show that TS-Gaussian is O OVP However, this privacy guarantee is not tight due to the fact that TS-Gaussian has to sample a mean re- ward model from data data-dependent Gaussian distribution for each arm in each round to achieve exploration. Each sampled Gaussian mean reward model implies the injection of some Gaussian noise into the empirical estimate, and sampling in total T Gaussian mean reward models for each arm provides a privacy guarantee in the order of VT.
t 6 + value 0¹ (aX 8 among the previously sampled ø mean reward models in the learning for arm i. Once new Gaussian distribution is available (the Gaussian distribution located on the right side). DP-TS-UCB is allowed to draw á Gaussian mean reward models again in each of the rounds t' + 1, + +2,..., .......... t.
t'. DDDPPTS-UU
X X
Xy Xin + X1i + Xx2
A,=Xi
X2
A,
A.
X
X,
X,
X,
X
Xn
Xu
4
12
13
44 1/ 17
18
1g
110
411
422
413
Figure 2. Arm-specific epoch structure. The dashed lines par- tition rounds from t1 to f12 into three epochs. Assume pulled in round f1, then we compute its empirical mean as jt. = Xx at the end of round fı and arm i's first epoch ends in round f, If arm is pulled in rounds 13. 44 again, then we compute its empir- ical mean as رa; (X3 + X2)/2 the end of round 4 and arm i's second epoch ends in round f4. It is important to note that arm i's empirical mean will not be updated at the end of round to even though it is pulled in round ts.
i is
In this paper, we propose a novel private bandit algorithm, DP-TS-UCB (presented in Algorithm 1), which does not require sampling Gaussian mean reward model in each round, and is hence more efficient at trading off privacy and regret. Theoretically, OP-TS-UCB uncovers the connection between exploration mechanisms in TS- S--usssii and UCBI (Auer et al., 2002), which may be of independent interest.
Our proposed algorithm builds upon the insight that, for each arm i, the Gaussian distribution that models the mean reward of arm i can only change when arm i pulled, as new pull of arm indicates the arrival of new data associated with arm i. In other words, the Gaussian distribution stays the same in all rounds between two consecutive pulls of arm i. Based on this insight, to avoid unnecessary Gaussian sampling, which increases privacy loss, DP-TS- sets a budget & for the number of Gaussian mean reward models that are allowed to draw from a Gaussian dis- tribution. Among all the rounds between two consecutive pulls of arm i, DP-TS-UCD can only draw Gaussian mean
To have a tight privacy guarantee, in addition to capping the number of Gaussian mean reward models, we also need to limit the number of times that a revealed observation can be used when computing empirical estimates. Similar to Sajed & Sheffet (2019); Hu et al. (2021); Azize & Basu (2022); Hu & Hegde (2022), we use an arm-specific epoch structure to process the revealed observations. As already discussed in these works, using this structure is the key to designing good private online learning algorithms. The key idea of this structure is to update the empirical estimate using the most recent 2" observations, where r 2 O. Figure 2 illustrates this structure for the first three epochs.
2

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
Preview of results. DP-TS-UCB uses an input parame- ter a E [0, 1] control the trade-off between privacy and regret, and the choice of o = O(T0-5(1-0)) In (.5((--))(T) (T)) depends on both a and the learning horizon T. Our tech- nical Lemma 4.1 shows that this choice of ensures suffi- cient exploration, that is, giving enough optimism, for the rounds when sampling new Gaussian mean reward models is not allowed. DP-TS-UCB is ((T0025(1-a)) 20(1-0))-GDD J-GPP (The- orem 4.4) and achieves EsA,s0 (In ( (TT) regret bounds (Theorem 4.2), where A, is the mean re- ward gap between the optimal arm and a sub-optimal arm
the reward vectors up round t. Let Xi. be a neighbouring sequence of X1: which differs in at most one reward vector, say, in some round S t.
Definition 2.1 (DP in online learning). An online learning algorithm A is (e, 6) 6)- if for any two neighbouring reward sequences XI:r and X 1:T, for any decision set Di:e S [K]], we have IP {A(()::) Di:e} S E {AA()))) E Piaa+0 holds for all t S T simultaneously.
Like Ou et al. (2024), we also perform our analysis using Gaussian differential privacy (GDP) (Dong et al., 2022), which is well suited to analyzing the composition of Gaus- sian mechanisms. We then translate the GDP guarantee to the classical (s, 5)-DP guarantee by using the duality between GDP and DP (Theorem 2.4). Indeed, Dong et al. (2022) show that GDP can be viewed as the primal privacy representation with its dual being an infinite collection of (s, DDD guarantees.
For the case where a 0, DP-TS- -P-B enjoys the optimal E. O1In( 6T /)) regret bounds and sat- isfies Ö(T0.25) ((T0025)-GDP J-GP, which improves the previous ((VT)- GDP guarantee significantly. For the case where a 1, DP-TS-UCB satisfies constant ((D--DDP and achieves EnA,s ((In(TTA)) (n() A,) regret bounds.
2. Learning Problem
To introduce GDP, we first need define trade-off functions:
In this section, we first present the learning problem of stochastic bandits and then we provide key knowledge re- lated to differentially private online learning.
Definition 2.2 (Trade-off function (Dong et al., 2022)). For any two probability distributions P and Q on the same space, define the trade-off function T(P.Q) : [0, 1] + [0, 1] T(P, (z) inf (Bg : a S x), where op. Ep[15], 8. = 1 Eg[(,) and the infimum is taken over all measurable rejection rules a E [0,
2.1. Stochastic Bandits
In a classical stochastic bandit problem, we have a fixed arm set [K] of size K, and each arm i E [K] is associated with a fixed but unknown reward distribution pt with [0, 1] support. Let bu denote the mean of reward distribution p5- Without loss of generality, we assume that the first arm is the unique optimal arm, i.e., H11 > (4; for all * 1. Let A; == μ11 b4 denote the mean reward gap. The learning protocol is in each round f, a reward vector X2 := (X, generated, where each (t) ~ ps. Simultaneously, the learning agent pulls an arm in E [K]. At the end of the round, the learning agent receives a reward X; (1). The goal of the learning agent is to pull arms sequentially to maximize the cumulative reward over T rounds, or equiva- lently, minimize the (pseudo)-regret, defined as
Let denote the cumulative distribution function (CDF) of the standard normal distribution 10. To de- fine GDP in the context of online learning, for any r 2 0, we let G,((z) = T (NV 1), (7, 1)) (z) = & (1 - x) n) denote the trade-off function of two normal distributions.
(t))
Definition 2.3 (n-GDP in online learning). A randomized online learning algorithm A is 1/-DPP if for any two reward vector sequences X1.T and X differing in at most one vector, we have T' (AA (X1:r) . (X(+)) (x) 2 G,(()) holds for all x E [0, 1] and S T simultaneously.
R(T) T M1 -
E
Σ
Mi 1
For easier comparison, we use the following theorem to convert an GDD guarantee to (s, d)-DP guarantees:
where the expectation is taken over the pulled arm éz. The regret measures the expected cumulative mean reward loss between always pulling the optimal arm and the learning agent's 's actual pulled arms.
Theorem 2.4 (Primal to dual (Dong et al., 2022)). ran- domized algorithm nDDD if and only if (e. 8(P) for all 2 0, where
8(E) +b (- & + 3
-
2.2. Differential Privacy
Remark. Fix any 2 0. We can also view 6(E) as an increasing function of n. This means, for a fixed e, the smaller the GDP parameter
Our DP definition in the context of online learning follows the one used in Dwork et al. (2014); Sajed & Sheffet 2201)); Hu et al. (2021); Hu & Hegde (2022), Azize & Basu (2022);
+ (-5+ -
Ou al. (2024). Let X1:t = (X1, X2....; X,) collect all
n) is, the smaller the 5(8) is after the translation.
3

---

Connecting Thompson Sampling and UCB: Towards More Efficient Trade-off's Between Privacy and Regret
3. Related Work
Gaussian mean reward model 0, - (Ra.:: 1/n,). The learning agent pulls the arm with the highest mean reward model value. Ou et al. (2024) showed that TS-Gaussian satisfies V0.5T-GDP, before translating this GDP guar- antee to (e, 6)DD guarantees with Theorem 2.4. Since there is no modification to the original algorithm, the op- timal Ess,so
There a vast amount of literature on (non-private) stochas- tic bandit algorithms. We split them based on UCB-base versus Thompson Sampling-based, ie., deterministic versus randomized exploration. Then, we discuss the most relevant algorithms for private stochastic bandits.
(A))) problem-dependent regret bounds and the near-optimal O regret bounds are preserved. Ou et al. (2024) also proposed Modified Thompson Sampling with Gaussian priors (we re- name it as L-TS-Gaussian), which enables a privacy and re- gret trade-off. Compared to TS- TS-Gaussian, the modifications are pre-pulling each arm b times and scaling the variance of the Gaussian distribution as c/nq. They proved that M- TS- Gaussian satisfies /TT(cc(b + 1))-GDP, and achieves bK + Eis,s0 ((cIn(TA))) A.) problem-dependent re- gret bounds and &K + O(cv In worst-case regret bounds. Table summarizes the theoretical results of TS- Gaussian and M-TS-Gaussian with different choices of b, c.
UCB-based algorithms (Auer et al., 2002; Audibert et al., 2007; Garivier & Cappé, 2011; Kaufmann et al., 2012a; Lattimore, 2018) usually conduct exploration in a deterministic way. The key idea is to construct confidence intervals centred on the empirical estimates. Then, the learning agent makes decisions based the upper bounds of the confidence intervals. The widths of the confidence intervals control the exploration level. Thompson Sampling- based algorithms (Agrawal & Goyal, 2017: Kaufmann et al., 2012b; Bian & Jun, 2022: Jin et al., 2021: 2022: 2023) conduct exploration in a randomized way. The key idea is use a sequence of well-chosen data-dependent distributions to model each arm's mean reward. Then, the learning agent makes decisions by sampling random mean reward models from these distributions. The spread of the data-dependent distributions controls the exploration level. In addition to the aforementioned algorithms, we also have DMED (Honda & Takemura, 2010), IMED (Honda & Takemura, 2015), elimination-style algorithm (Auer & Ortner, 2010), Non-parametric TS (Riou & Honda, 2020), and Generic Dirichlet Sampling (Baudry et al., 2021). All these algorithms enjoy either EEA.>0 ((I(TT/AA) or E ((I(()), / (44,, + A.)) problem- dependent regret bounds, where KL(a, b) denotes the KL.-divergence between two Bernoulli distributions with parameters a, b e (0, 1).
KKT KTln(K) worst-case
The order of VT-GDP guarantee from TS- TS-Gaussian and --TTS-Gaussaan may not be tight when T is large. There are two reasons resulting in this loose privacy guarantee: (I) sampling a Gaussian mean reward model in each round for each arm injects too much noise; (2) repeatedly using the same observation to compute the empirical estimates creates too much privacy loss. In this work, we propose DP-TS-UCB, novel private algorithm that does not require sampling Gaussian mean reward model in each round for each arm. The intuition is that once we are confident some arm is sub-optimal, we do not need to further explore it. To avoid using the same observation to compute the empirical estimates, we use the arm-specific epoch structure devised by Hu al. (2021); Azize & Basu (2022); Hu & Hegde (2022) to process the obtained observations. Using this structure ensures that each observation can only be used at most once for computing empirical estimates.
Sajed & Sheffet (2019); Azize& & Basu (2022); Hu et al. (2021) developed optimal (s, DDP stochastic bandit al- gorithms by first adding calibrated Laplace noise to the empirical estimates to ensure (s, DD. Then, eliminating arms and constructing data-dependent distributions based on noisy estimates can be viewed as post-processing which do not hurt privacy. Although Hu & Hegde (2022) proposed private Thompson Sampling-basse based algorithm, it still follows the above recipe without leveraging the inherent randomness present in Thompson Sampling for privacy.
Regarding lower bounds with a finite learning horizon T for differentially private stochastic bandits, lower bounds exist under the classical (c, 5)-DP notion. Shariff & Shef- fet (2018) established D(Es,, >o In()) In(T)/ + K In(T")/e) problem-dependen regret lower bound and Azize & Basu (2022) established an Ω2( / KT + K/s) minimax regret lower bound for (a, DD- Wang & Zhu (2024) established an I<EA,,> (T) + In (e (17 problem- dependent regret lower bound for (c, In this work, we do not provide any new lower bounds. Our theoretical results are compatible with these established lower bounds.
Ou et al. (2024) connected Thompson Sampling with Gaus- sian priors (we rename it as TS- TS-Gaussian) (Agrawal & Goyal, 2017) to the Gaussian privacy mechanism (Dwork et al. 2014) and Gaussian differential privacy (Dong al., 2022). The idea of TS-Gaussian is to use N (Ai.n, 1/n.) to model arm i's mean reward, i.e., the mean of reward distribution p;- The centre of the Gaussian distribution ji.n, is the empirical average of n; observations that are iid. according to p.. To decide which arm to pull, for each arm in each round, the learning agent samples a
(c--1)+8T
4. DP-TS-UCB
We present DP-TS-UCB and then provide its regret (Theo- rem 4.2) and privacy (Theorems 4.4 and 4.6) guarantees.
4

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
Algorithm 1 DP-TS-UCB
denote arm i's learning model in round t 12 K +++1 1. Each (t))) can either be a new Gaussian mean reward model some Gaussian mean reward model already used be- fore. To decide which case fits arm i in round t. we check the value of h2 to see whether drawing a new Gaus- sian mean reward from N (tt) In (T) is allowed: if 1y 2 1, we sample a new mean reward model !! ~ NN' (Ri,m In (1) (T)/n,(t (t-(tt))))) 1)) and use it in the learning, i.e., (t) = 0//23 : if h; = 0, we use (t) = MAX; = maxp.e(o) [c] ((h)) in the learning as we have all 1,n,
1: Input: trade-off parameter a E [0, 1). learning horizon T, and budget & = oo (2205((1-a) In (.5((3a)) a) (T).
2: Initialization: (1) pull each arm once to initialize n; and Pi.m. (2) set arm-specific epoch index r; t 1 and the number of unprocessed observations O <- 0, (3) set remaining Gaussian sampling budget h; t- Φ and the highest Gaussian mean reward model MAX, < 0.
1))
3:
for t = K + 1, K + + I do
4: for E [K] do
5:
if h;; 2 1 then
0 s,m where s,m9 NV (Dimes (T)) %Manndaorr TS- SS-Sssssi
Set (,(t) + o llh.)
((2) i,m," ................................ (( in hand already.
6:
Our technical Lemma 4.1 below shows that the highest mean reward model MAX, is analogous to the upper con- fidence bound in UCB1 (Auer et al., 2002). The usage of MAX; ensures sufficient exploration for the rounds when sampling new Gaussian mean reward models is not allowed. We can view DP-TS-UCB as two-phase algorithm with mandatory TS- IS-Gaussian phase and an optional UCB phase. Note that DP-TS-UCH itself does not explicitly construct up- per confidence bounds; MAX; itself behaves like the upper confidence bound of arm i UCBI in terms of achieving exploration.
Set hi f- 11,1,, MAX; <- max max(MAX, (
7:
8:
else
9:
Set (t({)) < MAX; %Optional UCB
10:
end if
11:
end for
12:
Pull arm i, E arg [ (t),), observe X;, (t),
and set Oi, + Oz, +1
13:
if O., = 2", then
14:
Compute Pi.,,,, + where ni: = 2%
15:
Reset hi, + Φ. MAX;, <0
Lemma 4.1. Fix any observation number 3 2 1 and let ( 1. 0 be i.i.d. according to N (jrtss In (T)/s) We have P maxne (0) 0 ス mi 2 1 (11/T)
16:
Set r4 + 1 and reset Os, t- 0.
17:
end if
18:
end for
Make a decision and collect data (Line 12). With all learn- ing models (t) in hand, the learning agent pulls the arm i E arg max (t(t) with the highest model value, ob- serves (t,()) and increments the unprocessed observation counter O,, by one.
4.1. DP-TS-UCB Algorithm
Algorithm| presents the pseudo-code of DP-TS-UCB, Let cu - V2Te. We input trade-off parameter E [0, 1] and learning horizon T, and then we compute the sampling bud- get (551- In 0.5(33-)) (TT). Let nt(t 1) denote the number of observations that are used to compute the empirical estimate (t-), at the end of round 1.
Process collected data (Line 13 to Line 17). To control the number of times any observation can be used when computing the empirical mean, we only update the empirical mean of the pulled arm is when the number of unprocessed observations O₁ 2 After the update, we reset hi, Oi, and MAX,, and increment the epoch progress Ti, by one.
Initialize learning algorithm (Line 2). There are several steps to initialize the learning algorithm. (1) We pull each arm i E [K] once to initialize each arm's empirical mean ji...- Since the decisions in these rounds do not rely on any data, we do not have any privacy concerns. (2) As we use the arm-specific epoch structure (Figure 2 describes the key ideas of this structure) to process observations, we use r; to track arm i's epoch progress and use O to count the number of unprocessed observations epoch r,, We initialize r; = 1 and O = 0. (3) Since we can only draw at most & mean reward models from each Gaussian distribution, to count the remaining Gaussian sampling budget at the end of round f 1, and MAX; to track the maximum value among these @ Gaussian mean reward models. Initially, we
Remark on Algorithm 1. We use data collected in epoch r; in a differentially private manner to guide the fu- ture data collection in epoch r;. We have a mandatory TS- Gaussian phase where drawing Gaussian mean reward mod- els is allowed and an optional UCB phase where the agent can only reuse the best Gaussian mean reward model in the mandatory TS-Gaussian phase. Separating all the rounds belonging to epoch r, into two possible phases controls the cumulative injected noise (and privacy loss) regardless of the epoch length.
use h;
set h = à and MAX;- = 0.
4.2. Regret Analysis of DP-TS-UCB
Decide learning models (Line 4 Line 11). Let (c(t)
In this section, we provide regret analysis of Algorithm 1.
5

---

Connecting Thompson Sampling and UCB: Towards More Efficient Trade-off's Between Privacy and Regret
Theorem 4.2. The problem-dependent regret bound of DP-
where, generally, the first term will use the regret analysis of TS-Gaussian in Agrawal & Goyal (2017) and the second term will use Lemma 4.1. In Appendix D, we present an improved analysis of TS TS-Gaussian and show that the regret of the first term is at most O (In@TTA)) In (T)/A.). The second term uses a union bound and Lemma 4.1, and is at most Ei=411 PP Σ P P(0:(0) S MI MI T10) S ((I(()).
TS-UCB with trade-off parameter [0, 1] is
EnSiso O In(T (n(rr)(0-)) 2)) In (T) (3-a) (() A.
A.
The worst-case regret bound of DP-TS-UCH with trade-off parameter E [0, is KT In 0.5 (T)).
pf is =i, (,),()) S μa + 0.54,, (tt)
<
Theorem 4.2 gives the following corollary immediately.
Corollary 4.3. DP-TS-UCD with trade-off parameter 0 achieves End O (In (T) +0 (In in((T//A) problem-dependen regret bounds and O(VKTIn(T) worst-case regret bounds.
4.3. Privacy Analysis of DP-TS-UCB
This section provides the privacy analysis of Algorithm 1. Theorem 4.4, DP-TS- UCSB with trade-off parameter a E
Discussion. DP-TS-UCB with parameter a = can be viewed as a groblem-dependent optimal bandit algorithm with theoretical guarantees lying between TS- Gaussinn (Agrawal& & Goyal, 2017) and UCB1 (Auer et al., 2002); the E.A,>0 O (In (TI. A / + O (IT) A.)) bound is better than the E O (In(T)/A)) bound of UCBI, 1, but it is slightly worse than the Ei O (In(TA))\)) bound of TS-Gaussian. DP-TS-UCB with parameter a 0 is not optimal in terms of regret guarantees, but offers a constant GDP guarantee (see Corollary 4.5 in Section 4.3).
[0, 1] satisfies v TV.cTT)) In (n15(1a))(T)))))))))))) (T)-
Theorem 4.4 gives the following corollary immediately. Corollary 4.5. DP-TS-UCE with trade-off parameter = O satisfies O (7 In (T)))GDP -DP;; DP-TS-UCB with trade- off parameter a = satisfies O (1)-GDP.
Discussion. Together, Theorem 4.2 (regret guarantees) and Theorem 4.4 (privacy guarantees) show that DP-TS-UCB is able to trade off privacy and regret. The privacy guarantee improves with the increase of trade-off parameter a, at the cost of suffering more regret.
We sketch the proof of Theorem 4.2. The full proof is deferred to Appendix D. Since DP-TS-UCB lies in between TS- "S-Gaussian and UCB1, the regret analysis includes key ingredients extracted from both algorithms.
Table I summarizes privacy and regret guarantees of TS- Gaussian (Agrawal & Goyal, 2017), M-TS-Gaussian (Ou et al., 2024), and DP-TS-UCB. From the results, even for the worst case, i.e., Ô ( which could be much better than the O(VT)-GDP guarantee of TS-Gaussian. Since DP-TS- UCB with a achieves a constant GDP guarantee, increasing learning horizon T does not increase privacy cost. M-TS-GGussian pre-pulls each arm b times and uses c/n; as the Gaussian variance. Generally, it achieves bK + Endiso ((cloo(TA))/A) regret bounds and satis- 10) GDP. By tuning b, c = O (In (T)), M- TS-Gaussian achieves Ess.so O(I ((T) (Tg( A.) regret bounds (almost the same as DP-TS-UCB's regret bounds), but satisfying O(VT/ In (T))-GDP guarantees, which could be much worse than the Ô (T0.25) -GP guar- antees of DP-TS-UCB. By tuning h, e = 0 (T)), where Y > 0, ML-TS-Gaussian achieves ΣEA, 0 log(T
Proof sketch of Theorem 4.2. Fix a sub-optimal arm i. Let L, = O (L) In (T) indicate the number of observations needed to sufficiently observe sut-mmtimal arm We know that the total regret accumulated from arm i before is sufficiently observed is most L; A, By tuning L, properly, for all the rounds when arm i is observed sufficiently, the regret accumulated from arm i can be upper bounded by
O, DP-TS-UCB is still
ET.HI P(c = (1) S 14 + 0.5A,)
(2)
fies /T/(c(b+ +
where (t) can either be fresh Gaussian mean reward model (TS- GTussias phase, Line 6) or the highest Gaussian mean model used before (UCB phase, Line 9).
We further decompose (2) based on whether the optimal arm 1 is in VS-GGussiaan phase (Line 6) or UCB phase (Line 9). Define (1) as the event that the optimal arm uses a fresh Gaussian mean reward model in round 6, i.e., in TS- Gaussian phase, and let Ti (t) denote the complement. We have (2) decomposed as
regret bounds and satisfies O(VT1-27) (1)/1-27)-GDP.. Although the GDP guarantee is improved to be in the order of VTI-27, the regret bound may be worse than DP-TS-UCB's bounds due to the existence of the T term. For example, when set- ting 0.25, ErA.> =o O log (TA)//A)) regret bound, which will not be problem-dependent optimal.
is O(79.25)-GDP, but it has
T Σ ΣT<+1 P P(i = -,0 S p. + 0.5A, T((t)
K+ P -,0(()) S p + 0.5A, T(
Since the classical (e, 6D- notion is more interpretable, we translate GDP guarantee presented in Theorem 4.4 into
6

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
Table 1. Summary of privacy and regret guarantees
Regret bounds
GDP guarantees
TS-G (Agrawal & Goyal, 2017)
O [K In(T 17AA)
O
M-IS-G (Ou al., 2024)
+ O(cK (A(A))
OlyT//cbb 1)M)
M-IS-G (tune bu = O(T") J.y > 0)
O(KТ (n
O(T45-7)
M-TS-G (tunc bu (Iu" (T))
O(K 1K'nn(1 (T) In [/A]
O1T05//n"(1
DP-TS-UCB (Algorithm 1)
0,K In (70.03 A²) In (TY/A+ + (
O 0 (T)
DP-IS-UCB (tune 0)
O In (T.AA))
0,K (n In (TT))AA 0 (T
(T/)
DP-TS-UCR (tune 1)
O(1)
(e, 6)-P guarantees by using Theorem 2.4.
the optional UCB phase, DP-TS-UCB is also /0/h" (T)- GDP, as by post-processing Theorem 4.8, the maximum MAX, of ø Gaussian mean reward models is v / In (T)- GDP. Composing the privacy guarantees these two phases concludes the proof.
Theorem 4.6. DP-7S-UCB is (s, 6())) for all 0,
where d(s) 4b V26
22
ef. &
/20 V2
where o c0.50. a)) In 0.5/3 (T).
Proof. Directly using Theorem 2.4 concludes the proof.
5. Experimental Results
The proof for Theorem 4.4 relies on the following composi- tion theorem and post-processing theorem of GDP.
5000
DP-TS-UCB (a =
Theorem 4.7 (GDP composition (Dong al., 2022)).
Regret by the end round
2000
DP-TS-UCB (a 0225)
DP-TS-UCB (o 0.5)
The m-fold composition of -DDG mechanisms is
DP-TS-UCB (a 0.73)
VTi -DP.
3000
DP-TS-UCB (o
Theorem 4.8 (GDP Post-processing (Dong et al., 2022)). If a mechanism A is q- GDGPP its post-processe prsteprocsssing is also 17- GDP.
2000
1000
Proof of Theorem 4.4. Fix any two neighbouring reward and Xi.r
10000
100000
1000000
10000000
sequences X1. x Xr) (XI,.... XT), where the complete reward vector in round is changed. Under the bandit feedback model, this change only impacts the empirical mean of the arm pulled in round т, that is arm é,. Name i, j:: based on the arm-specific epoch structure (Figure 2), the observation (T) will only used once for computing the empirical mean arm j the end of some future round, which is the last round of some epoch ry associated with arm j.
T
(a) The impact of learning horizon T and trade-off parameter the regret by the end of round T.
a the and of round T
109
DP-TS-UCR (o
108
DP.TS-UCB (o 0.25)
DP-TS-UCB 0.5)
10a
DP-TS-UCB 0.75)
DP-TS-UCB (a
11P
We have one Gaussian distribution constructed using (T) at the beginning of epoch ry. If arm only has the manda- tory TS-Gaussian phase epoch rj. we draw at most & Gaussian mean reward models from that constructed Gaus- sian distribution. From Lemma 5 of Ou al. (2024), we know DP-TS-UCB
GDP parameeia
10f
10F
108
10000
100000
1000000
10000000
In (T) in each round in the mandatory TTS-Gaussian phase. From Theorem 4.7, we know the GDP composition over at most á rounds is (T))n"(T))GDD Note that X,(7) will not be used to con- struct Gaussian distributions starting from epoch r, + I to the end of learning due to the usage of arm-specific epoch structure, i.e., we abandon (7) at the end of epoch rj-
(b) The impact of learning horizon T and trade-off parameter the GDP parameter the end of round T..
Figure 3. OP-TS-UCBS privacy vs regret with different a and T.
The setup consists of five arms with Bernoulli rewards. We set the mean rewards as [0.95, 0.75, 0.55, 0.35, 0.15). We first analyze DP-TS- AETT--CB'S privacy and regret across differ- ent values a and T. Then, we compare DP-TS-UCB with (Ou et al., 2024) from two perspectives:
If arm has both the mandatory TS-Gaussian phase and the optional UCB phase in epoch ry, for the mandatory TS Gaussian phase, DP-TS-UCB is V In" (T for

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
(I) Privacy cost under equal regret; (2) Regret under
7000
DP-TS-UCB
equal privacy guarantee. We also compare with (e, 0)- DP algorithms, including DP-SE (Sajed & Sheffet, 2019), Anytime-Lazy-UCB (Hu et al., 2021), and Lazy-DP-TS (Hu & Hegde, 2022) for = 0.5, which can be found in Ap-
Regret by the and round T
6000
M-TS- Gouessiin [== fl (T")))
5000
pendix E.2. All the experimental results are an average of 20 independent runs on a MacBook Pro with MI Max and 32GB RAM.
5.1. Privacy and Empirical Regret DP-TS-UCB with Different Values of and T
0.25
0.5
0.75
(a) Regret the end of round T' of OP-TS-UCH and M-TS- Gaussian with different parameters.
The performance of OP-TS-UCB in terms of the privacy guarantees and regret across different values of a and time horizons 7 are shown in Figure 3. The results reveal trade- off between regret minimization and privacy preservation: increasing leads to stronger privacy guarantee, reflected in lower GDP parameter 1), but at the cost higher regret. However, when a 1, the privacy guarantee becomes con- stant, meaning that increasing 7 longer deteriorates the privacy protection of DP-TS-UCB.
GDP parameter the end of round
DP USBB
600
TS. Gaussian (6 0, (n))
500
400
200
5.2. Privacy and Empirical Regret Comparison under the Same Theoretical Regret Bound
100
0.25
0.5
0.75
Since DP-TS-UCB with parameter a and M-TS-Gaussian with parameters 5 0, 5 5In"(T)) share the same theoretical regret bound, we now present empirical re- gret and privacy guarantees for different values of a = {0, 0.25, 0.5, 0.75, 1]. We set 7 = 10 Figure 4(a) shows that DP-TS-UCB incurs lower empirical regret than M-TS- Gaussian, whereas Figure 4(b) shows that DP-TS-UCB achieves better privacy.
(b) GDP parameter 7) by the end of round T of DP-TS-UCB and M-TS M-TS-Gaussian with different parameters.
Figure 4. The performance of DP-TS-UCB and M-TS-Gaussian under the same theoretical regret bound.
outperforming M-TS L-TS-Gaussian, as shown in Figure 5(b).
5.3. Empirical Regret Comparison under the Same Privacy Guarantee
6. Conclusion
M-TS-Gaussian satisfies V (T/(c(b GDP guarantee
This paper presents a novel private stochastic bandit algo- rithm DP-TS-UCB (Algorithm by leveraging the con- nection between exploration mechanisms in TS-Gaussian and UCBI We first show that DP-TS-UCB satisfies (T (VTT0.5(1-00) (TT)) - GDP and then we translate this GDP guar- antee to the classical (s, 5)-DP guarantees by using dual- ity between these two privacy notions. Corollary 4.3 and Corollary 4.5 show that DP-TS-UCB with parameter O achieves the optimal O(K In(T)/A) AA) problem-dependee re- gret bounds and the near-optimal O(V Tn) worst-case regret bounds, and satisfies Ô (19.25)- This privacy guarantee could be much better than the ((VT)- guar- antees achieved by TS-Gaussian and T--Gaussian of Ou et al. (2024). We conjecture that our privacy improvement is at the cost of the anytime property of the learning al- gorithm and the worst-case regret bounds. Note that both TS Gaussian and M-TS- Gaussian are anytime and achieve O OVVTT) KT In K) worst-case regret bounds, whereas our DP.
while DP-TS-UCB satisfies V T0.50.5(1-a) 1.5( 111 (T)-
GDP. Thus, we let c (b++) (0.5(1+a) In - 115(1-a) T
for any b of M-TS-Gaussian ensure the same privacy guarantees as DP-TS-UCB. We compare their empirical regret over T 10 rounds under two privacy settings determined by for both algorithms. For each a, we select b from {0, 1, 500, 1000, 2000, 5000, 100000} to minimize regret of M-TS- Gaussian (see Appendix E.I).
20g In 1.3 T-GDP Guarantee (a 0). The optimal M-TS-Gaussian parameters are b = 1 and = 1.18. As shown in Figure 5(a), M TS--Gussiinn slightly outperforms DP-TS-UCB, but the empirical regret gap is small.
GDP Guarantee (a 1). For this setting, the best M-TS-Gaussian parameters are 2000 and e 60.46. However, OP-TS-UCB achieves lower regret, significantly
8

---

Connecting Thompson Sampling and UCB: Towards More Efficient Trade-off's Between Privacy and Regret
Lécuyer is grateful for the support of NSERC with reference number RGPIN-2022-04469, Nidhi Hegde would like to acknowledge funding support from the Canada CIFAR Al
Chairs program.
Regret
MA-TS-Gassiaan (b 1.18)
DP-TS-UCR (ox
Impact Statement
sequential decision-making makiong is important in modern interactive machine learning systems, particu- larly in bandit learning and its general variant reinforce- ment learning (RI.). Our work contributes to this field by proposing a novel differentially private bandit algorithm that connects classical algorithms the RL community and DP community. Understanding the interplay between decision- decision-making algorithms like Thompson Sampling. and privacy mechanisms and notions is fundamental to advance the deployment of RL algorithms using sensitive data.
0
200000
400000
600000
S00000
1000000
(a) Empirical regret for O 70.3 GDP (a 0)
6000
References
Regret
1000
M. TS Gaussian (b = 2000, 60.46)
Agrawal, S. and Goyal, N. Near-optimal regret bounds for Thompson Sampling. http://wwwz columbia edu cclp:=sa3305/ppprr////aaa (atppper//.-ccorrrteee...... 2017.
DP-TS-UCB
1)
2000
Audibert, J.-Y., Munos, R., and Szepesvári, C. Tuning bandit algorithms stochastic environments. In Inter- national conference on algorithmic learning theory, pp. 150-165. Springer, 2007.
400000
600000
1000000
(b) Empirical regret for V 2c--GDP GDP (a 1).
Auer, P. and Ortner, R. UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, 61(1-2):55-65, 2010.
Figure 5. The regret of DP-TS-UCB and M-TS- GTS-Gaasiian under the same privacy guarantee with a 0 and a
Auer, P., Cesa- Besa--Banchi, N., and Fischer, P. Pinite-time analysis of the multi-armed bandit problem. Machine learning, 47:235-24 2266,225,211 2002.
TS-UCB is not anytime and achieves only O O(VKThn worst-case regret bounds. If we know the maximum mean reward gap Amax = max A, in advance, by slightly modifying the thcoretical analysis, we know a better choice of o should be the one depending on Amax- Tuning é that GDP
Azize, A. and Basu, D. When privacy meets partial informa- tion: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 35: 2022.
depends on Amax will provide guarantees. This intuition motivates develop private algorithms that achieve problem-dependent GDP guarantees as the main future work.
Baudry, D., Saux, P., and Maillard, O.-A. From optimality to robustness: Adaptive re-sampling strategies in stochastic bandits. Advances in Neural Information Processing Systems, 34:14029-14041, 2021.
Acknowledgements
Bingshan Hu is grateful for the funding support from the Natural Sciences and Engincering Resource Council of Canada (NSERC), the Canada CIFAR AI chairs program, and the UBC Data Science Institute. Zhiming Huang would like to acknowledge funding support from NSERC and the British Columbia Graduate Scholarship. Tianyue H. Zhang is grateful for the support from Canada CIFAR AI chairs program and Samsung Electronics Co., Limited. Mathias
Bian, J. and Jun, K--S. Maillard sampling: Boltzmann exploration done optimally. In International Conference Artificial Intelligence and Statistics, pp. 54-72. PMLR, 2022.
Dong. J., Roth, A., and Su, W. J. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3337, 2022.

---

Connecting Thompson Sampling and UCB: Towards More Efficient Trade-off's Between Privacy and Regret
Dwork, C., Roth, A., al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3-4)2211-40) 2014.
Ou, T., Medina, M. A., and Cummings, R. Thompson sampling itself is differentially private, 2024. URL https: /tapsi//axxv..../// org/ htrrg/ab/22400 14879.
Garivier, A. and Cappé, O. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pp- 359-376. JMLR Workshop and Conference Proceedings, 2011.
Riou, C. and Honda, J. Bandit algorithms based on Thomp- son Sampling for bounded reward distributions. In Algo- rithmic Learning Theory, pp. 777-826. PMLR, 2020.
Sajed, T. and Sheffet, O. An optimal private stochastic- mab algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pp. 5579-5588. PMLR, 2019.
Honda, J. and Takemura, A. An asymptotically optimal bandit algorithm for bounded support models. In COLT, pp. 67-79. Citeseer, 2010.
Shariff, R. and Sheffet, O. Differentially private contextual linear bandits. Advances in Neural Information Process- ing Systems, 31, 2018.
Honda, J. and Takemura, A. Non-asyon -on-ssymti analysis of a new bandit algorithm for semi- cemi-bounded rewards. J. Mach. Learn. Res., 16:3721-3756, 2015.
Wang. S. and Zhu, J. Optimal learning policies for differen- tial privacy in multi-armed bandits. Journal of Machine Learning Research, 25(314):1-52, 2024.
Hu, and Hegde, N. Near-optimal Thompson Sampling- based algorithms for differentially private stochastic ban- dits. In Uncertainty in Artificial Intelligence, pp. 844 852.
PMLR, 2022.
Hu, B., Huang, Z., and Mehta, N. A. Near-optimal algo- rithms for private online learning in a stochastic environ- ment. arXiv preprint arXiv:2102.07923 2021.
Jin, T., Xu, P., Shi, J., Xiao, X., and Gu, Q MOTS: Minimax optimal Thompson Sampling. In International Confer- ence on Machine Learning, pp. 5074-5083. PMLR, 2021.
Jin, T., Xu, P., Xiao, X., and Anandkumar, A. Finite-time regret of Thompson Sampling algorithms for exponential family multi-armed bandits. Advances in Neural Infor- mation Processing Systems, 35:38475-38487, 2022.
Jin, T., Yang, X., Xiao, X., and Xu, P. Thompson Sampling with less exploration is fast and optimal. 2023.
Kaufmann, E., Cappé, O., and Garivier, A. On Bayesian upper confidence bounds for bandit problems. In Artificiaa intelligence and statistics, pp. 592-5922699 600. PMLR, 2012a.
Kaufmann, E.,, Korda, N., and Munos, R. Thompson Sam- pling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory: 23rd International Con- ference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23, pp. 199-213. Springer, 2012b.
Lattimore, T. Refining the confidence level for optimistic bandit strategies. The Journal of Machine Learning Re- search, 19(1)765-779. 2018.
Mishra, N. and Thakurta, A. (Nearly) optimal differentially private stochastic multi-arm bandits. In Proceedings of the Thirty-Fire First Conference on Uncertainty in Artificial Intelligence, pp- 592-601, 2015.
10

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
The appendix is organized follows.
1. Useful facts are provided in Appendix
2. Proofs for Lemma 4.1 is presented Appendix B;
3. Proofs for Lemma C.1 is presented in Appendix C;
4. Proofs for Theorem 4.2 is presented in Appendix D;
5. Additional experimental results are presented in Appendix E.
A. Useful facts
Fact A.1. For any T > e², for any E [0, we have In' (T) S (1 (1- a + 1.
Proof. Let function f(a) = (1 a) In( + 1- -1---n IIn'-a (T). where variable a E [0,1]. 1]. Then, we have f'(a) = (T( +
In (n)-(((Tn(TTT) It is not hard to verify that f In(lu(T)) O. The fact that f'(a) 2 0 when a E
0. In(In(In(T)))
ln(In(T)
gives f(a)= 2 f0) > 0 for any E [0, In(m(In(T))) Similarly, the fact that f'(a) S 0 when a E In(In(2))
In(In(In(T)
In(l(())
gives f(a) 2 f1) = 0 for any E [[((n((a((()) .1]. Therefore, we have f(a) 2 0 for any a E [0, 1].
Fact A.2 (Hoeffding's inequality). Let X1, X2,..,, X, be independent random variables with support [0, 1). Let M1 -i=1 X,. Then, for any a > have P ([ - E [pt.,]] 2 a} S 2e- 2na?
Fact A.3 (Concentration and anti-concentration bounds of Gaussian distributions). For a Gaussian distributed random variable with mean μ and variance o², for any O, we have
P > μ + 20) < Je- 2, PIZ < p 2020 S fe-
(4)
and
P (Z μ + 20 2
v25 2"11 -
(5)
B. Proofs for Lemma 4.1
Proof of Lemma 4.1. Let Et denote the event that IAi, H4l S VIn(T)/s holds. Let E denote the complement. We have
maxhela) 0 S ui
P PO }
maXke(M) 0/00 S Mi
gP +
1,8
W
II P
S Pi.s + VIn(T)/s
2e 2ln((T
1,5
KE A)
(T) 8 }) +2/72
1
-
P
(h) jul, (nt==a())nn
NE
II
1
In (T
00.5l -0
+ 22/T2
2 In [T]++
AE
(6)
(8)
1 1-
1
(IT
0..((1 (0)(1-0) +2/72
2
In In!-
VInt-a(T) 01
+2/T2
2u
In'-a(7)
// V/Te Vist बाा pooit + 2/T2
2. if o00 o (T) / v 70.31 of + 2/T2
I II
3/T,
where step (a) uses the anti-concentration bound shown in (5), step (b) uses In aT) & (1 In() + shown in
Fact 1, and step (c) uses (1 2) -

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
C. Proofs for Lemma C.1
For the case where a = 0, Lemma C.I below is an improved version of Lemma 2.13 in Agrawal Goyal (2017) and our new results imply both improved problem-dependen and problem-inge independent regret bounds for Algorithm in Agrawal Goyal (2017). Assume TA?
Lemma C.I. Let 11 N (p1.01 In((T)
Then, for any integer 2 L, we have
12.34
(7)
F
4(1+-22 In(TA))
Also. for any integer
have
A
B As.e
T2 TA
(8)
P(D 11
Proof. For the result shown in (7), we analyze two cases: 5 = 1 and 2 2. For s = 1, we have
LHS of (7) E Pl Pa..]
<(a) E
1 (b)
12.176, (9)
P D0,e
Ia Jār.
V2n
where step (a) uses in iA (T) and step (b) uses the anti-concentration bound shown in (5).
For any 2 2, since Ais is random variable in [0, 1], we know l Mul E [0, 1] is also random variable. Now, define a sequence of disjoint sub-intervals
0,
2l)(2)
2 (l(
2 (2-1))1
2lm(r+2)
2 (l((r(()++1)
(ln(ra())+22)
where (s)s) is the smallest integer such that [0, _ 0, 211(2)
U
22m(++11)
2lu(r+2)
ISrSro(s)
{ 1i2.. - Hal
0, v //2m((2) } and S, = 1 - Hil [cVVe Velictu / 22m(x+22)
}
We also define events S, =
for
all S r S (s) accordingly.
Now, we have
LHS of (7) E
1 < E
1(Se)
Σ
E
1
(10)
1SrSro(s)
For the first term in (10), we have
1(5
1(Sa)
1(Sa)
E
E
< E
P(0 (....
p
2m
F
0
2in(2) in (3)
(11)
10.161.
-0.5222m(2)
2
where the second last inequality uses the anti-concentration bound shown in (5).
12

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
For the second term in (10), we have
Σ
E
1(S.)
15rSro(s)
101.. Mile
V 2lalrr 1)
2late 21
Σ
E
9
P(01,2/110111
1grSro(H)
1a M MalE
11
21a(r-2) 2)
Σ 1grSro(e)
E
2infr42) 101. P{ 11.0
210(e+1)
2ln(e-a)
Σ
E
21air 2)
15rSro(e)
(12)
<(() Σ
E
1 |in.. mil E
2lnfr+1)
2
(srSro())
(n(m422) V2x 211
0.8.21m(r12)
Σ
(2n((+2)) In(r22) P | -112 21n(r+11
(2
15rSro(e)
<(1) Σ
(2
2e 2s. 20.2..2..nn 21n(r+1)
22ln(+22)-e-nii (n(r+2)
(g
Σ (22
(n(r+2)
(r+1)*
(srSro())
3.176
where step (a) uses the anti-concentration bound shown in (5) and step (b) uses Hoeffddin'ss inequality.
Plugging the results shown in (11) and (12) into (10), we have
LHS of (7) E
P(0
1 < E
1(80)
)
+ Σ E
P(0 >
1(S.
(1.)
115 12.34,
(13)
r2
which concludes the proof of the first result.
13

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
for For the result shown in (8), we define the following sequence of sub-intervals
0, in(T))))
In(r-TA:))
In((++1)-T3))
In(ro
[n((ro(s))1)TT))
In(TA?)
In(TTA)))
In((r+1)-T23)
where rs)s) is the smallest integer such that [0,1]
0,
ISrSra(s)
We define events So 1M,,. Mul
0,
In(Ta?) and S, | mile
In(eTAR)
In((++1)7A3)
all 1 S S (s) accordingly.
From 8
4(1+v2) (nn we also have A; 2
42++ In(1 A? (x)
Then, we have
4
LHS of (8)
E
P 0.34 M1..)
E
(141222 ( 181.0
01.0211-
E
1(50
Σ
E
1(S.}
P 01.03/11
(2 In (T 102.0
(SrSro(s)
01,0301
(1+v2)² in a in (2)
11.0
E
1(So
-1
Σ
E
1(8,)
P 01.
(14 (u (n
101
ISrSro(s)
P 11..)
(14)
For the first term in (14), we have
1(So)
E
-1
81, 311
1(S)
-1
0, >p, ln(ra?)
P
1
1(5b)
1
(15)
In(rap)
(14339 in(Aa) in (7)
1111
1(Sb]
2 (2)
01 21.
A1.0
(a)
(b)
0.613 TA?
where step (a) uses concentration bound shown in (4) and step (b) uses
T42
0.5
TA?
1-0.5
TA?
14

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
For the second term in (14), we have
Σ
E
1(S,)
241
(11.))
(grSnu(s)
In((=11))44))
AA Male
V
Σ
E
(grSmo(s)
in(x++))Ta?)
11 11.E
V
Σ
E
1grSmo(s)
1))
l
Infr-TaP)
In In((++I)TAR)
Σ (grīnu(s)
E
p 01,2211
Σ
P
Ai1, MilE
Iu(r-TA7)
I(((+1)-TA)))
(r+1)-T'??) 0.
IgrSro(s) 20 (m(et)))Tag)
In(r-TA?)
Σ
P
((+1))TA))-
1srSro(s) 2y (i((r+)))Ta))
(16)
<(6)
Σ
(0+1))727)-03 -2e"
-21n(--TA?)
(grSro(s) 2026 Vi(lt+n)-aa)
Σ
2(r (A?)
((+1))747)-03
IgrSrols) 2025 T
Σ
(T-TAR)²
(CrSro(s)
(1+)))n((++))TTT)))))
Σ
TA
VV
IA IN
1SrSr(()
A TA
Σ
(r+1)ln(r-1)
15rSro(s)
7.034
TA
70.5235
TA?
where step (a) uses the anti-concentration bound shown in (5), i.c., we have
P(O1o 01. > ai,s + V In((++))-TA))
P0.1 01.0 > 10, +
In(x+1)-TA)) In (T)
[In((r+))-TA7]
V2T
In((r=1)-TAA+1
[In((++1)TTA2]
((r+ 1) -TA)) -0.5
In((r=1)-TA/)+1
VI(((++))TAA]
1(++1))AA7) -0.5
2
21n((r-1)-TA))
((++1)TAAY)
2/2
()n((=-))-AA])
15

---

Connecting Thompson Sampling and UCB: Towards More Efficient Trade-off's Between Privacy and Regret
D. Proofs for Theorem 4.2
Proof. We first define two high-probability events. For any arm E [K], let (1-1)) = [ 14 $ V
/mITTA) (1-1-
and (t) { (t(() (1) + v 2In Φ) respectively.
n;(t-1) Let Et 1) and (t) denote the complements,
In" (T)
Fix sub-optimal arm i. Let L
(v2+1)²
In (TA 6)
In
and r.") [Log)(Li)]
Let ta denote the last round of epoch v!*) That is also to say, at the end of round to, arm i's empirical mean will be updated
by using 2nd") observations.
Let (T) denote the number of pulls of sub-optimal arm i by the end of round T. We upper bound E [T), the expected number of pulls of sub-optimal arm i. We decompose the regret based on whether the above-defined events are true or not. We have
E [T)]
Σ E+=K+1
T
E [ -+)=)))++
Er Ei= 14 - i, 1) 1.)) +1
E
k1= 1
+
S
2 + T
+1
E 2 + Σ Lt=k+1 E1 4.H1
s 4L
Σ E
4i
k+
E
i 1), 4
k=
k=
w)=0(1/())
Lemma D.1
w==0(1/2f), Lennnn D.2
(17)
For w2 and W3 terms, we prepare a lemma for each of them.
1 00 50())) x 1) Lemma D.2. We have Eis+1 E 1 {ir i, E (t- ()- 1 0o (t))
Lemma D.1. We have Et=k+1 E I i = i, (1), mi(t 1) 11) 2
The challenging part is to upper bound term W1. By wning L properly, we have
- (t, 1) 2 4.]1 Σn E 1 (ūe = 1)
W1 =
(18)
<(a)
E B i, 0:(() S + 0.52,
where step (a) uses the argument that if both events E (t 1) = { (1ammet-1) Hil
Im(a?))
n.(1-13 and (t)
(B((t) S (im + (2 Φ) v
(T) m1(1-1) are true, and n,(t 1) 2 Li, we have
(t(
< (i, +
AT d)
(T) Re(t-1)
IN(A
W M4 + 1)(t1))
(-
< P4 + In(T
(T)) + 2n Φ)
(T)
(19)
In
< Mi + (V2+ + 1)V
In(T
(In
L.
M + 0.5A,
where the last step applics L, (V2+1)²
A Φ)
(T)
A?
16

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
Since the optimal 1 either be in the mandatory TS-Gaussian phase the optional UCB phase, we continue decomposing the regret based the case of the optimal arm 1. Define Ti (t) as the event that the optimal arm in round t is in the mandatory TS-Gaussian phase, that is, using fresh Gaussian mean reward model in the learning. Let (t)) denote the
complement, that is, using MAX, = max;; Elo) ((()) (t-11 in the learning, where all ((b)) (.m1(t-1) ~ N (A1,m)(t-1)- (T) (1-11)
are i.i.d. random variables.
We have
W1
E (1e = i,t,(t S m +
Σ
E 1 {
- =
14 Ti(t)
(20)
K+1
K+1
Upper bound /.. Note that event (1) is true, we know the optimal arm is using a fresh Gaussian mean re- ward model in the learning in round 4, that is, (1( N (PImi(t-1)) In (T) Term / will use a similar anal- ysis to Lemma 2.8 of Agrawal & Goyal (2017), which links the probability of pulling sub-optimal arm i to the probability of pulling the optimal arm 1. We formalize this into our technical Lemma D.3 below. Let Fi-1 X,, (T), VT .,,, 1} collect all the history information by the end of round t - 1. collects the number of unused Gaussian sampling budget (T) by the end of round т for all i E [K]. the index i, of the (T) pulled arm, and the observed reward ,, (T) for all rounds T = 1,2, ... - 1. Let (1-(111)) ~ N (A1, (.(1-1) be a Gaussian random variable.
mi(t-1)
(T), (T)).).
Lemma D.3. For any instantiation F of Fi-1, have
E f4 = T,))),, (t) S 44 0.5A. F Fi-1l
(21)
s B/00mm/t-1/31-0000111 0.3 1= -1 B f FF-1= Ft-1).
With Lemma D.3 hand, we upper bound term J,. Let L1, 4(1+2)) (T(A la (T)
Let ri [Igg((n1))]] We have
A
4
Σ
E[1 -1,=-,;0,00) 5 +055, T(())
E EE (i, = i,0,00 1 (T)) F.-Ill
k=+11
Σ
E
-1)
E E[ (1, 1) Fi F1-1]
P(0lmnit- >21 201
k=1+
Σ
E
1 = 11 Fz-1 = F-
7 ( 0.54, F.
1=
T
Σ
E
1 1 11
1((0 >11 100.11t------00-11----11--
1.. 11
1=K+1
log(?")
20+1, E
P(01.2* S41 0.5A, 2
$=0
1
-1) 1)
log(T)
20+1. E
+
Σ 20+1 E s=x(-)
P [ > 11 0.5A; 11,200
P P
1I 0.5A,
1
==
< $12.34 34 from (7)
$ 12 from (8)
log(T) 4. L1.i 12.34
Σ
20+1
TA7
s=r(")
< 50 + O(1AA))
(22)
17

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
Upper bound 1z. Note that if event (1) is false, we know the optimal arm using MAX, = max E(d] ( 1mn((t-1) in (T) the learning, where ((hu)) (,=1(t-1) ~N (Dimi(t-1) (1-1-)) ) for each hy [o]. We have
12
Σ
T
E
1 4 = it) S As +0.4, (1()) }
k=++
1 { -,0,00,000 S u A. T0(1) }
Σ
E
K+1
Σ k=++
E
f[ 11 i,0(10 S u A. Ti (1)
(23)
T
Ing(T)
Σ
E
max k
! 11
k=
Lemma 4.1
T log(T)
O(1/))
t=
(ln(T))
From (22) and (23), we have wi E I + 12 S 50L + 0(1/4)) + +(I((T) 0 In
which gives
4
E [T) So ( [I(dTT2))
0 (n
0 [In(TT In (T)
(24)
A
Therefore, the problem-dependent regret bound by the end of round T is
B A.
In(dTA)) In
EiEjKTAA O
EiEKK]ASIO O
To.0 m) In 0.5(3 (T))TS))
(25)
A.
S EiERK]AA O
In In(T0:03-0) A?) In (T)
+ 0
(3-a) In (n(T) In " (2)
A.
For the proof of worst-case regret bound, we set the critical gap A. = v (Iintt (T)/T. The regret from pulling any sub-
optimal arms with mean reward gaps no greater than A, at most TA O(v ((TIn'=(7))
The regret from pulling
In (333))) a3) In
In" (T)
any sub-optimal arms with mean reward gaps greater than A, is most EiEKKTAIZA. O
4.
O (3-a) In In(T) la (X) (X))
EiE o
[n(T) la (T)
+ In (T')
50 (0(1 (VKTIntooT)
A.
2.
A.
18

---

Connecting Thompson Sampling and UCB: Towards More Efficient Trade-off's Between Privacy and Regret
Proof of Lemma D.I. Let Ta observations.
(0) be the round by the end of which the empirical mean will be computed based on 2 fresh
We have
Σ
E
1 (t) 4.
1= K+
Σ
E
1 -= > (m.m(t111)+ + /2ln o) V
m[( : ni(t - 1) }
(T)
f=K+1
(ng(T)
Σ ==0
E
1011
Σ
1 1fi = ii,0(t)) > P))m(t-11)++++ + V 2Im(T Ø)
(T"
(=1) +1
+1
(26)
log(T)
MAX; > Pr.2- + 22n 6) / /
Σ 20+1. PP-
$=0
log(T)
Σ 20+1 Φ ())
W 0 T Φ T
0
x
which concludes the proof.
Proof of Lemma D.2. From Hoeffding's inequality, we have
E 1 fir =
())
2 [
log( T)
P |i4.2-- Hil S V
la(T
2
log(T)
(27)
2e 2lu(T2)) 20+1
8=0)
IA IA
0 T TATTA
A7
which concludes the proof.
Proof of Lemma D.3. For any F:-1, we have
E [1 fúr = i, (t) S + + 0.54, [tt}}}
< (t) (0) S p4 44 0.5A, (,(t) S p4 0.5A,
+ Vj e [K] (1)) Fi-1= = F
1 (1) (l) S 5m:
(0,0)) < # + 0.5A, Vje [K] (()) Fi F--
(28)
where the first incquality uses the fact that event (t()) is determined by the history information. Note if hy - 1) E [Ø], we have 1 (t) = 1; if (t - 1)= = 0. we have 1 (t)) = O.
We also have
E [1 (úr - 1, (()) < mm (() 1T-1= Fr-1]
2 1 (T) [ (0) > +.54, 2 (t), e [K] (
Fi-1=
= 1 (t) (0) > +055, F = -
E [K] (1)) Fr = =F
(29)
Now, we categorize all the possible F 's of Fi-1 into two groups based on whether (Ti(1) = 0 or 1 (T(()) =
19

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
Case 1: For any Pi-1 such that 1 (Ti(() 0, combining (28) and (29) gives
E 1 { i,0,(t) - μr + 0.5A, Ti(t)) Fi-1 Fi-1)
(30)
F(0 (1 / P 1) E
[i (i
11 Fi-1 Pi-1
where the last equality uses the fact that P0untt--22ttb55333=....... -1) 1) +00.
Case 2: For any Fi-1 such that 1 (Ti(t)) 1, we have
[ = i1) < +4 Ti (1)) Fi-1 Pt-1]
s 1 (t) (t) $ μ4 +.5A, (t O.5
Fi-1 Vj = Fi-1
1 (T)(t)) (0 S
0.54,
E
1 (0 (m, $ μ4 +.5., Fi-1
vj E $x
(31)
We also have
E [1 f4+ = = 0,5 (0) = F1-1=
2 1 (t) (())) > H 2 (1) (1N |, Fi-1]
1 (T)(t) 33
>
E > -10 X --
(32)
From (31) and (32), we have
E 1 = i,0
14 0.54, Ti(1) - Fi-1]
11 1-
B[1 =1,0,() S + T((I) F Fi-il
(33)
[11 = F = Fi-1l
which concludes the proof.
20

---

Connecting Thompson Sampling and UCB: Towards More Efficient Tradc-off's Between Privacy and Regret
E. Additional Experimental Results
E.1. L-TS-Gaussian parameter selection
Recall that in Section 5.3, we let c
(0.5(1++a) In -1.5((11a)) (T) for any b for M-TS-Gaussian to satisfy (0o(b+1)
V 22 In 1-5(1 -) (ZT)-GDP To determine the best b value for each considered in Section 5.3, we conduct experiments with b {0, 1, 500, 1000, 2000, 5000, 100000}. The results are shown in Figure 6.
10a
10a
10a
Regret
10a
Regret
10a
10a
10
M-T5 Caneson (b 0. 9.30)
-
M-T5 Gaussion (b 0,0 120955 39
10
M.TS Geussion
60492.68
M-T5 Gaussion (6 000,
M-T5 Gaussin (b 500. 241 49)
M-T5 Gammton
M-TS-Gammeon (b 2000, 09:46)
5000,
10a
Gaussinn (b- o
M--5 Camebn
10000
M-T5 Gonecon (6 = 10000, = 12 (2.99)
0.4
1.0
0.2
0.4
1.0 x10"
x10
(a) Regret for O
5 In 15 T) -GDP (a 0).
(b) Regret for V2co-GDP GDP (a 1).
Figure 6. The regret of M-TS- TTS-Gaus with parameters {0, 500, 1000, 2000, 5000, 100000) under two privacy guarantees.
We can observe that when a = 0, M-TS-Gaussian achieves the lowest regret with b = and c = 1.18, as shown in Figure 6(a). When a = 1, ---TS-Gausiaan achieves the lowest regret with = 2000 and 60.46, as shown in Figure 6(b).
E.2. Comparison with (c. DDP algorithms
We compare DP-TS-UCB with (e, OD- algorithms with E = 0.5: DP-SE (Sajed & Sheffet, 2019), Anytime-Lazy-Un UCB (Hu et al., 2021) and Lazy-DP-TS (Hu & Hegde, 2022). These algorithms use the Laplace mechanism to inject noise.
2500
6009
M-TS-Grumian
EP-TS-UCIE
BE-TS-UCHS (o
Vaniila TS (Gaussan)
Vanila TS (Gunsian)
Regret
1500
RP:SF (.5)
Lac [c 0.0)
Regret
4000
BP-SF 0.5)
ArytimeLagg-UCB [c 0.0) Lasy-DP-T is (e 0.53
Lasy-DP- TS 0.4)
1000
2000
500
2000000
400000
600000
800000
1000000
200000
400000
600000
800000 1000000
(a) Regret for O In T) -GP (a = 0).
(b) Regret for 2 GDP (ex 1).
Figure 7. The regret of DP-TS-UCB and M-TS-Gaussinn Gaussian under the same privacy guarantee with = 0 and 1, with comparison to (e, DD algorithms.
We that when 0, both DP-TS-UCE and M-TS-Gaussian perform better than the (e, DD algorithms, shown in Figure 7(a). When we increase = 1, M-TS-GauSSSAE Gaussian performs worse than the (c, DD algorithms, but DP-TS-UCE still outperforms Anytime-Lazy--CCB, as shown Figure 7(b).
21


Reviews:
[{"review_id": "LcNJ9mcIpw", "reviewer": "Reviewer_BBHN", "summary": "This paper describes a stochatic MAB algorithm that preserves DP. It uses Thompson sampling with a limited budget of samples per epoch. Once the samples are exhausted within a round it uses the maximum of those samples. This is akin to an upper confidence bound. It also has a  parameter $\\alpha$ that can tune the behaviour from privacy-preserving to regret-minimising.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive comments. Regarding the results of GDP guarantees, we would like to clarify that when choosing $\\alpha = 0$, the privacy guarantee depends on $T$. In Theorem 4.4, the GDP guarantee is in the order of $ \\sqrt{ T^{0.5(1-\\alpha)} \\ln^{1.5(1-\\alpha)}(T)}$. So, only $\\alpha=1$ yields a constant GDP guarantee. Therefore, the algorithm is not always $2.875$-GDP if we change the values of $T$, and $\\alpha$ does parametrize a privacy-regret tradeoff. For a fixed $T$ and $\\alpha$, it is possible to achieve any specific lower level of GDP via scaling the Gaussian variance by a constant larger than one. However, it will result in an increased regret.", "claims_and_evidence": "The presentation is ok, and the sketch proofs are readable. The structure of the proofs makes sense.", "methods_and_evaluation_criteria": "Standard bandit experiments.", "theoretical_claims": "I checked the sketch proofs and some of the appendix, but I could not really go through all the algebra.", "experimental_designs_or_analyses": "The experimental analysis is only a minor aspect.", "relation_to_broader_scientific_literature": "It is of interest to online learning and DP", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The writing could be improved.", "other_comments_or_suggestions": "It seems that $\\alpha$ can tune the algorithm only to a limited extent. Is there a way to achieve e.g. a specific fixed level of GDP? At this point, it seems like, for $\\alpha = 0$ we get 2.875-GDP,  or (1, 0.7612)-DP. It still is an improvement over TS-G.", "questions_for_authors": "See above. How meaningful is the DP guarantee?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GiCk5XxYf3", "reviewer": "Reviewer_BT5n", "summary": "This paper examines the regret-privacy trade-off for the Gaussian TS algorithm under Gaussian Differential Privacy. By drawing the connection between Gaussian TS and UCB, authors propose the DP-TS-UCB algorithm, which does not need to sample a Gaussian model at each round, the paper achieves a new privacy-regret trade-off that improves upon the previous state-of-the-art results.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive comments. We address each of your questions as follows. \n\n(1) Thank you very much for referring us to this interesting paper [1]. Under the notion of Bayesian regret and using Gaussian priors, we think it is possible to achieve an improved trade-off between regret and privacy by changing the variances of prior distributions. It is an interesting research direction, but it is out of the scope of our work as we focus on the frequentist regret setting.\n\n(2) Regarding the lower bounds on the regret-privacy trade-off, lower bounds exist for differentially private bandits under the notion of the classical $(\\varepsilon, \\delta)$-DP [2, 3, 4]. We will discuss those in the related work. Establishing lower bounds for our specific algorithm is an interesting avenue for future work. \n\n[1] Saha, A., & Kveton, B. (2023). Only Pay for What is Uncertain: Variance-adaptive Thompson Sampling. arXiv preprint arXiv:2303.09033.\n\n\n[2]: Roshan Shariff & Or Sheffet,  Differentially Private Contextual Linear Bandits, NeurIPS 2018.\n\n[3]: Achraf Azize & Debabrota Basu, When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits, NeurIPS 2022.\n\n[4]: Siwei Wang & Jun Zhu, Optimal Learning Policies for Differential Privacy in Multi-armed Bandits, Journal of Machine Learning Research 2024.", "claims_and_evidence": "Yes. Most claims are well-supported.", "methods_and_evaluation_criteria": "Yes, the evaluation criteria(Regret and GDP) are standard and widely applied in most related areas.", "theoretical_claims": "I have not thoroughly reviewed all the proofs and the appendix in full detail, but based on the provided intuition and the outlined proofs, I am inclined to believe that the theoretical claims are correct.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This paper follows the line of work exploring the privacy-regret tradeoff for bandits with a Gaussian TS, as listed in the related work section and the table. The contributions made by this paper, including the improved tradeoff bound and the principles behind its algorithm design, provide valuable insights into this line of research.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Other Strengths:\n\nThe authors provide a clear explanation of the intuition behind their algorithm design, which makes the paper easy to follow. \n\nWeakness: \n\nOne potential weakness is the lack of lower bound results on such regret-privacy tradeoff.", "other_comments_or_suggestions": "I don't have other comments.", "questions_for_authors": "1. While this paper focuses on the frequentist setting, I am curious whether improved results could be achieved by considering Bayesian regret, even under the assumption of a Gaussian prior. Additionally, I wonder how the variance of prior distributions impacts such tradeoff in heterogeneous reward setting, as in non-privacy setting [1].\n\n2. Are there any lower bound results on such regret-privacy tradeoff?\n\n[1] Saha, A., & Kveton, B. (2023). Only pay for what is uncertain: Variance-adaptive thompson sampling. arXiv preprint arXiv:2303.09033.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yw8iabbsAo", "reviewer": "Reviewer_95KC", "summary": "This paper studies the problem of differentially private stochastic bandit. It proposes a new algorithm which is roughly Thompson sampling, with an option to re-use previous samples. Their algorithm offers a trade-off between regret and privacy, a strict improvement over previous works on the privacy when maintaining a near-optimal regret.\n\n## update after rebuttal\n\nI have no other concerns. Please consider (1) justifying or modifying the \"UCB\" naming, and (2) adding a discussion on the trade-off of $\\alpha$ in a future version.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive comments. We address each of your questions as follows.\n\n(1) Regarding the **similarity between our proposed algorithm and UCB**, \nas theoretically justified in Lemma 4.1 and the content just above it (Lines 266 to 271), the reason why we call it UCB is that the maximum value of previous samples behaves like the upper confidence bound in the classical UCB1 algorithm.  We agree with the comment that the UCB part in our proposed algorithm is a kind of bound similarity as our proposed algorithm itself does not explicitly construct upper confidence bounds. We appreciate your concern about the potential misinterpretation and will refine our writing to ensure clarity.\n\n(2) Regarding the proof of our presented theorems, we appreciate your suggestions. For Theorem 4.2, we will clarify more key steps by bringing some of the details currently in Appendix D into the main text to provide a more complete picture of the proof sketch. For Theorem 4.4, we will complement the existing proof with a more formal, math-style proof to enhance its rigor and clarity in the appendix.\n\n(3) Regarding **\"TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation\"**, by Jackie Baek and Vivek F. Farias, AISTATS2023, we thank you very much for referring us to this relevant paper. \n\nAfter carefully reviewing it, in addition to our focus on privacy, we identify two other key differences between their TS-UCB and our proposed algorithm. (1) Their work focuses on Bayesian regret, whereas our analysis is in the frequentist setting. Since Bayesian regret bound cannot be translated to frequentist regret bound easily, this represents a fundamental distinction. (2) While their TS-UCB samples multiple posterior models, it aggregates them by averaging. The averaging will not behave like an upper confidence bound (as opposed to our maximum), which does not provide sufficient exploration. We will incorporate these points into our discussion of related work.\n\n\n(4) The reasons  **why we provide  tuning $\\alpha \\in [0,1]$ to trade off privacy and regret**:\n\nFrom a theoretical standpoint, it provides insights into the interplay between the privacy and regret while also offering the privacy-regret trade-off flexibility by tuning the parameter $\\alpha$ to balance these two. This perspective helps us better understand the fundamental limits of private decision-making. For the stochastic bandit community, we care more about the regret bounds, and, thus we would like to avoid the extra $\\ln T$ factor. From the perspective of privacy, we agree that in practical scenarios, setting $\\alpha = 1$ may often be the preferable choice, as the extra $\\ln T$ factor is typically negligible.  Achieving a constant privacy guarantee could be more beneficial. We appreciate your perspective and will clarify this point in our discussion.\n\n(5) Last but not least, we thank you very much for the careful review. We will fix all the typos.", "claims_and_evidence": "It's unclear to me how much similarity there is between UCB and the algorithm in this paper. According to line 10 of the algorithm, the re-using phase where we set $\\theta_i(t)$ as the maximum of previous samples is considered the only UCB-style part. The justification, Lemma 4.1, seems to be a bound similarity instead of algorithmic similarity. I'm not sure if calling such mechanism UCB is misleading, since there is no upper confidence bound involved.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I only checked the proof sketch of Theorem 4.2 and the proof of Theorem 4.4. The proof sketch of Theorem 4.2 is intuitive, but I would like to see more details on the step of putting everything together. The proof of Theorem 4.4 is too casually written.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This work is of potential interest to the privacy community, besides the ML community.", "essential_references_not_discussed": "\"TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation\", by Jackie Baek and Vivek F. Farias, AISTATS2023. Although this paper doesn't study DP, I would appreciate a discussion on algorithmic and idea similarities/differences between the two works.", "other_strengths_and_weaknesses": "The new technique of re-using previous samples is smart and interesting, which plays a crucial role in the improvement over previous works.\n\nIn the title, it should be \"Thompson\" instead of \"Thomson\".\n\nIn table 1, the use of $\\log$ and $\\ln$ is inconsistent.", "other_comments_or_suggestions": "No.", "questions_for_authors": "I wonder if the trade-off is necessary, when constant privacy is achievable at the cost of only a logarithmic term in regret. Does an $O(\\sqrt{\\ln T})$ term matter a lot in regret? In my opinion it doesn't, and it seems setting $\\alpha=1$ is a strictly better choice.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors propose a private stochastic multi-armed bandit algorithm based on Thompson sampling, which allows trading-off regret bounds and privacy bounds. The reviewers were unanimously positive about the paper and recommended acceptance. We suggest that the authors explain the connection to UCB and the role of the parameter $$\alpha$$ more clearly in the final version.
Decision: Accept (poster)