Faster Rates for Private Adversarial Bandits
Authors: Hilal Asi, Vinod Raman, Kunal Talwar
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 KT ε , improving upon the existing upper bound KT log(KT ) for all ε 1. In particular, our algorithms allow for sublinear expected regret even when ε 1 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 KT log(N) log(KT ) and O N 1/6K1/2T 2/3 log(NT ) ε1/3 + N 1/2 log(NT ) ε , 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 ε. |
| Researcher Affiliation | Collaboration | 1Apple 2Department of Statistics, University of Michigan, Ann Arbor. Work done while interning at Apple. |
| Pseudocode | Yes | Algorithm 1 Non-Private to Private Conversion Algorithm 2 Private, Batched EXP4 Algorithm 3 EXP3 with Mixing Algorithm 4 Bandit FTPL with Geometric Resampling Algorithm 5 Bandit to Bandit with Expert Advice Algorithm 6 Local-DP EXP4 |
| Open Source Code | No | The paper does not provide an explicit statement about open-sourcing the code for the main methodologies described, nor does it provide a direct link to a code repository. The Python snippet in Appendix G.1 is for illustrating a theoretical point, not for the algorithms themselves. |
| Open Datasets | No | The paper is theoretical, presenting algorithms and regret bounds for adversarial bandits. It does not perform experiments using specific datasets and therefore does not mention any publicly available datasets. |
| Dataset Splits | No | The paper is theoretical and does not perform experiments on datasets, so there is no mention of dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setups that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe an implementation of its algorithms that would require specific software dependencies with version numbers. The Python code snippet in Appendix G.1 is for an illustrative plot, not for the core methodology, and does not list specific library versions. |
| Experiment Setup | No | The paper is theoretical, focusing on the design and analysis of algorithms for private adversarial bandits and expert advice. It does not include an experimental section with hyperparameters or training configurations. |