Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DP-TS-UCB, a parametrized Thompson-Sampling-with-Gaussian-priors bandit that caps Gaussian sampling with a budget and reuses the max sample (UCB-like), trading privacy (tilde-O(T^{0.25(1-alpha)})-GDP) against regret (O(K ln^{alpha+1}(T)/Delta)).
Problem
Differentially private stochastic bandits must trade off privacy (GDP/DP noise) against regret; existing Thompson Sampling-based private analyses give only O(sqrt(T))-GDP because a fresh Gaussian sample is drawn every round.
Approach
Limit fresh Gaussian mean-reward samples per arm between pulls to a budget phi, then reuse the maximum of those samples (acting like a UCB) for remaining rounds, combined with an arm-specific epoch structure so each observation is used at most once; alpha tunes the privacy-regret trade-off.
Key results
- DP-TS-UCB with alpha=0 satisfies tilde-O(T^0.25)-GDP versus O(sqrt(T))-GDP for TS-Gaussian, with problem-dependent regret O(ln(T^1.5 Delta^2)/Delta) per arm.
- With alpha=1, DP-TS-UCB satisfies O(1)-GDP (constant in T) at regret cost O(ln(T)ln(T Delta^2)/Delta).
- In the equal-privacy comparison at alpha=1, DP-TS-UCB achieves lower empirical regret than M-TS-Gaussian (which was tuned with b=2000, c=60.46) over T=10^6.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the trade-off parameter α (ablation) | DP-TS-UCB · Five-arm Bernoulli bandit | GDP parameter | Helped |
| Increase the trade-off parameter α (ablation) | DP-TS-UCB · Five-arm Bernoulli bandit | regret | Hurt |
| Use DP-TS-UCB instead of M-TS-Gaussian with b = 0, c = 5ln^α(T), at equal theoretical regret bound | Stochastic bandit with T = 10^6 · Five-arm Bernoulli bandit | empirical regret | Helped |
| Use DP-TS-UCB instead of M-TS-Gaussian with b = 0, c = 5ln^α(T), at equal theoretical regret bound | Stochastic bandit with T = 10^6 · Five-arm Bernoulli bandit | privacy guarantee | Helped |
| Use M-TS-Gaussian (b = 1, c = 1.18) instead of DP-TS-UCB at equal GDP guarantee (α = 0) | Stochastic bandit with T = 10^6 · Five-arm Bernoulli bandit | empirical regret | Helped |
| Use DP-TS-UCB instead of M-TS-Gaussian (b = 2000, c = 60.46) at equal GDP guarantee (α = 1) | Stochastic bandit with T = 10^6 · Five-arm Bernoulli bandit | empirical regret | Helped |
| Set α = 0 rather than α = 1 (ablation) | DP-TS-UCB · Stochastic bandits (theoretical) | GDP guarantee: $\tilde{O}\left(T^{0.25}\right) \to O(1)$ | Hurt |
| Set α = 0 rather than α = 1 (ablation) | DP-TS-UCB · Stochastic bandits (theoretical) | problem-dependent regret bound: $O ( K\ln \left( T^{1.5} \Delta^2 \right) /\Delta + K \ln \ln (T)/\Delta) \to O ( K\ln \left( T \Delta^2 \right) \ln(T)/ | Helped |
Surprising findings
- The optimal M-TS-Gaussian choice at alpha=0 slightly beats DP-TS-UCB empirically, despite the privacy advantage of DP-TS-UCB.
Limitations
- Algorithm is not anytime and its worst-case regret is O(sqrt(KT ln T)) rather than O(sqrt(KT ln K)).
- Privacy guarantee is not problem-dependent; the budget phi depends on T rather than on the gap.
- Experiments are limited to a single 5-arm Bernoulli setting.
Experimental setup
Benchmarks: 5-arm Bernoulli bandit simulation (means 0.95, 0.75, 0.55, 0.35, 0.15), T=10^6
Metrics: pseudo-regret GDP parameter
Baselines: TS-Gaussian M-TS-Gaussian DP-SE Anytime-Lazy-UCB Lazy-DP-TS
Builds on: TS-Gaussian M-TS-Gaussian UCB1 arm-specific epoch structure
Closest papers by meaning
- Optimal Regret of Bandits under Differential Privacy (NeurIPS 2025 · similarity 0.91)
- Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits (NeurIPS 2026 · similarity 0.90)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.88)
- Faster Rates for Private Adversarial Bandits (ICML 2025 · similarity 0.88)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.88)
- On Differentially Private Federated Linear Contextual Bandits (ICLR 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.