mlsanityData to 7 Oct 2026

On Private and Robust Bandits

arXiv 2302.02526 ↗First posted 6 Feb 2023cs.LG cs.AI cs.CRcited by 6

Not on the map. Why?

Abstract (arXiv)

We study private and robust multi-armed bandits (MABs), where the agent receives Huber's contaminated heavy-tailed rewards and meanwhile needs to ensure differential privacy. We first present its minimax lower bound, characterizing the information-theoretic limit of regret with respect to privacy budget, contamination level and heavy-tailedness. Then, we propose a meta-algorithm that builds on a private and robust mean estimation sub-routine textttPRM that essentially relies on reward truncation and the Laplace mechanism only. For two different heavy-tailed settings, we give specific schemes of textttPRM, which enable us to achieve nearly-optimal regret. As by-products of our main results, we also give the first minimax lower bound for private heavy-tailed MABs (i.e., without contamination). Moreover, our two proposed truncation-based textttPRM achieve the optimal trade-off between estimation accuracy, privacy and robustness. Finally, we support our theoretical results with experimental studies.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 28 of its 54 references that are in the map. First posted on arXiv 6 Feb 2023.

Builds on

28 of 54 references.

References · 28

  1. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 133
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  4. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  5. 2018Privately Learning High-Dimensional Distributionscited by 103
  6. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  7. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  8. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  9. 2015Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Modelcited by 47
  10. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  11. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  12. 2019An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rulecited by 37
16 more
  1. 2020Multi-Armed Bandits with Local Differential Privacycited by 37
  2. 2022When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Banditscited by 28
  3. 2023From Robustness to Privacy and Backcited by 27
  4. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  5. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  6. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  7. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  8. 2020Privacy-Preserving Dynamic Personalized Pricing with Demand Learningcited by 23
  9. 2022On robustness and local differential privacycited by 15
  10. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  11. 2021Differential Privacy in Personalized Pricing with Nonparametric Demand Modelscited by 13
  12. 2019A Unified Approach to Robust Mean Estimationcited by 11
  13. 2019What You See May Not Be What You Get: UCB Bandit Algorithms Robust to ε-Contaminationcited by 6
  14. 2021Mean-based Best Arm Identification in Stochastic Bandits under Reward Contaminationcited by 6
  15. 2022Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithmcited by 6
  16. 2017A Multi-Armed Bandit to Smartly Select a Training Set from Big Medical Datacited by 5

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 4.

6 papers.

  1. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
  2. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
  3. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  4. 2025Improved Bounds for Private and Robust Alignmentcited by 3
  5. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  6. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1