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

• URL: http://arxiv.org/abs/2505.02383v2
• Date: Thu, 05 Jun 2025 03:07:12 GMT
• Title: Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
• Abstract summary: We propose DP-TS-UCB, a novel parametrized private bandit algorithm that enables to trade off privacy and regret.<n> DP-TS-UCB relies on anti-concentration bounds of Gaussian distributions and links exploration mechanisms in Thompson Sampling-based algorithms.
• Score: 5.050520326139362
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We address differentially private stochastic bandit problems from the angles of exploring the deep connections among Thompson Sampling with Gaussian priors, Gaussian mechanisms, and Gaussian differential privacy (GDP). We propose DP-TS-UCB, a novel parametrized private bandit algorithm that enables to trade off privacy and regret. DP-TS-UCB satisfies $ \tilde{O} \left(T^{0.25(1-\alpha)}\right)$-GDP and enjoys an $O \left(K\ln^{\alpha+1}(T)/\Delta \right)$ regret bound, where $\alpha \in [0,1]$ controls the trade-off between privacy and regret. Theoretically, our DP-TS-UCB relies on anti-concentration bounds of Gaussian distributions and links exploration mechanisms in Thompson Sampling-based algorithms and Upper Confidence Bound-based algorithms, which may be of independent interest.

Related papers

• AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification [0.3560429497877326]
  AdaPrivate-TS is a differentially private contextual bandit that combines Thompson Sampling with batched zCDP composition.<n>We show that AdaPrivate-TS achieves 93-99% of non-private performance at $varepsilon in [0.5, 5]$, outperforming UCB by 0.5-3.7% and up to 18% with tuned adaptive exploration.
  arXiv  Detail & Related papers  (2026-06-19T21:18:33Z)
• Optimal Best Arm Identification under Differential Privacy [8.321992395325912]
  Best Arm Identification (BAI) algorithms are deployed in data-sensitive applications, such as adaptive clinical trials or user studies.<n>We study the problem of fixed-confidence BAI under global Differential Privacy (DP) for Bernoulli distributions.<n>Our algorithm outperforms existing $delta$correct and $epsilon$-global DP BAI algorithms for different values of $epsilon$.
  arXiv  Detail & Related papers  (2025-10-20T09:46:09Z)
• Optimal Regret of Bernoulli Bandits under Global Differential Privacy [44.25744563135375]
  Regret minimisation in bandits under $epsilon$-global Differential Privacy (DP) has been widely studied.<n>We revisit the regret lower and upper bounds of $epsilon-global DP algorithms for Bernoulli bandits and improve both.
  arXiv  Detail & Related papers  (2025-05-08T19:48:58Z)
• Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
  Under privacy constraints, the complexity of private linear regression is emphnot captured by the usual covariance matrix.<n>We introduce an Information-Weighted Regression method that attains the optimal rates.<n> Notably, our results demonstrate that joint privacy comes at almost no additional cost.
  arXiv  Detail & Related papers  (2025-02-18T18:35:24Z)
• Differentially Private Best-Arm Identification [14.916947598339988]
  Best Arm Identification (BAI) problems are progressively used for data-sensitive applications. Motivated by the data privacy concerns invoked by these applications, we study the problem of BAI with fixed confidence in both the local and central models.
  arXiv  Detail & Related papers  (2024-06-10T16:02:48Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
  arXiv  Detail & Related papers  (2024-01-17T09:23:25Z)
• Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy [23.12198546384976]
  Posterior sampling provides $varepsilon$-pure differential privacy guarantees. It does not suffer from potentially unbounded privacy breach introduced by $(varepsilon,delta)$-approximate DP. In practice, however, one needs to apply approximate sampling methods such as Markov chain Monte Carlo.
  arXiv  Detail & Related papers  (2023-10-23T07:54:39Z)
• Concentrated Differential Privacy for Bandits [11.086440815804227]
  This paper contributes to the understanding of Differential Privacy (DP) in bandits with a trusted centralised decision-maker. We propose three private algorithms, namely AdaC-UCB, AdaC-GOPE and AdaC-OFUL, for three bandit settings.
  arXiv  Detail & Related papers  (2023-09-01T16:08:00Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  Online prediction from experts is a fundamental problem in machine learning and several works have studied this problem under privacy constraints. We propose and analyze new algorithms for this problem that improve over the regret bounds of the best existing algorithms for non-adaptive adversaries.
  arXiv  Detail & Related papers  (2022-10-24T18:40:19Z)
• When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits [4.964737844687583]
  We study the problem of multi-armed bandits with $epsilon$-global Differential Privacy (DP) We instantiate $epsilon$-global DP extensions of UCB and KL-UCB algorithms, namely AdaP-UCB and AdaP-KLUCB. AdaP-KLUCB is the first algorithm that both satisfies $epsilon$-global DP and yields a regret upper bound that matches the problem-dependent lower bound up to multiplicative constants.
  arXiv  Detail & Related papers  (2022-09-06T15:26:24Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  We study the semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we propose a BCUCB-T algorithm with variance-aware confidence intervals. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition.
  arXiv  Detail & Related papers  (2022-08-31T13:09:39Z)
• The Poisson binomial mechanism for secure and private federated learning [19.399122892615573]
  We introduce a discrete differential privacy mechanism for distributed mean estimation (DME) with applications to federated learning and analytics. We provide a tight analysis of its privacy guarantees, showing that it achieves the same privacy-accuracy trade-offs as the continuous Gaussian mechanism.
  arXiv  Detail & Related papers  (2022-07-09T05:46:28Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  We study the regret of Thompson sampling (TS) algorithms for exponential family bandits, where the reward distribution is from a one-dimensional exponential family. We propose a Thompson sampling, termed Expulli, which uses a novel sampling distribution to avoid the under-estimation of the optimal arm.
  arXiv  Detail & Related papers  (2022-06-07T18:08:21Z)
• Privacy Amplification via Shuffling for Linear Contextual Bandits [51.94904361874446]
  We study the contextual linear bandit problem with differential privacy (DP) We show that it is possible to achieve a privacy/utility trade-off between JDP and LDP by leveraging the shuffle model of privacy. Our result shows that it is possible to obtain a tradeoff between JDP and LDP by leveraging the shuffle model while preserving local privacy.
  arXiv  Detail & Related papers  (2021-12-11T15:23:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.