Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret

Thank you very much for the constructive comments. We address each of your questions as follows.

(1) Regarding the similarity between our proposed algorithm and UCB, as 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.

(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.

(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.

After 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.

(4) The reasons why we provide tuning $\alpha \in [0,1]$ to trade off privacy and regret:

From 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.

(5) Last but not least, we thank you very much for the careful review. We will fix all the typos.

Thank you very much for the constructive comments. We address each of your questions as follows.

(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.

(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.

[1] Saha, A., & Kveton, B. (2023). Only Pay for What is Uncertain: Variance-adaptive Thompson Sampling. arXiv preprint arXiv:2303.09033.

[2]: Roshan Shariff & Or Sheffet, Differentially Private Contextual Linear Bandits, NeurIPS 2018.

[3]: Achraf Azize & Debabrota Basu, When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits, NeurIPS 2022.

[4]: Siwei Wang & Jun Zhu, Optimal Learning Policies for Differential Privacy in Multi-armed Bandits, Journal of Machine Learning Research 2024.

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.