Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916780188893184 |
|---|---|
| author | Hu, Bingshan Huang, Zhiming Zhang, Tianyue H. Lécuyer, Mathias Hegde, Nidhi |
| author_facet | Hu, Bingshan Huang, Zhiming Zhang, Tianyue H. Lécuyer, Mathias Hegde, Nidhi |
| contents | 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-α)}\right)$-GDP and enjoys an $O \left(K\ln^{α+1}(T)/Δ\right)$ regret bound, where $α\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02383 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret Hu, Bingshan Huang, Zhiming Zhang, Tianyue H. Lécuyer, Mathias Hegde, Nidhi Machine Learning 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-α)}\right)$-GDP and enjoys an $O \left(K\ln^{α+1}(T)/Δ\right)$ regret bound, where $α\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. |
| title | Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.02383 |