Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.21790 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912399300231168 |
|---|---|
| author | Asi, Hilal Raman, Vinod Talwar, Kunal |
| author_facet | Asi, Hilal Raman, Vinod Talwar, Kunal |
| contents | We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conversion of any non-private bandit algorithm to a private bandit algorithm. Instantiating our conversion with existing non-private bandit algorithms gives a regret upper bound of $O\left(\frac{\sqrt{KT}}{\sqrtε}\right)$, improving upon the existing upper bound $O\left(\frac{\sqrt{KT \log(KT)}}ε\right)$ for all $ε\leq 1$. In particular, our algorithms allow for sublinear expected regret even when $ε\leq \frac{1}{\sqrt{T}}$, establishing the first known separation between central and local differential privacy for this problem. For bandits with expert advice, we give the first differentially private algorithms, with expected regret $O\left(\frac{\sqrt{NT}}{\sqrtε}\right), O\left(\frac{\sqrt{KT\log(N)}\log(KT)}ε\right)$, and $\tilde{O}\left(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{ε^{1/3}} + \frac{N^{1/2}\log(NT)}ε\right)$, where $K$ and $N$ are the number of actions and experts respectively. These rates allow us to get sublinear regret for different combinations of small and large $K, N$ and $ε.$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21790 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Rates for Private Adversarial Bandits Asi, Hilal Raman, Vinod Talwar, Kunal Machine Learning We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conversion of any non-private bandit algorithm to a private bandit algorithm. Instantiating our conversion with existing non-private bandit algorithms gives a regret upper bound of $O\left(\frac{\sqrt{KT}}{\sqrtε}\right)$, improving upon the existing upper bound $O\left(\frac{\sqrt{KT \log(KT)}}ε\right)$ for all $ε\leq 1$. In particular, our algorithms allow for sublinear expected regret even when $ε\leq \frac{1}{\sqrt{T}}$, establishing the first known separation between central and local differential privacy for this problem. For bandits with expert advice, we give the first differentially private algorithms, with expected regret $O\left(\frac{\sqrt{NT}}{\sqrtε}\right), O\left(\frac{\sqrt{KT\log(N)}\log(KT)}ε\right)$, and $\tilde{O}\left(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{ε^{1/3}} + \frac{N^{1/2}\log(NT)}ε\right)$, where $K$ and $N$ are the number of actions and experts respectively. These rates allow us to get sublinear regret for different combinations of small and large $K, N$ and $ε.$ |
| title | Faster Rates for Private Adversarial Bandits |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.21790 |