mlsanityData to 7 Oct 2026

Differentially Private Contextual Linear Bandits

arXiv 1810.00068 ↗First posted 28 Sep 2018cs.LG stat.MLcited by 82

Not on the map. Why?

Abstract (arXiv)

We study the contextual linear bandit problem, a version of the standard stochastic multi-armed bandit (MAB) problem where a learner sequentially selects actions to maximize a reward which depends also on a user provided per-round context. Though the context is chosen arbitrarily or adversarially, the reward is assumed to be a stochastic function of a feature vector that encodes the context and selected action. Our goal is to devise private learners for the contextual linear bandit problem. We first show that using the standard definition of differential privacy results in linear regret. So instead, we adopt the notion of joint differential privacy, where we assume that the action chosen on day t is only revealed to user t and thus needn't be kept private that day, only on following days. We give a general scheme converting the classic linear-UCB algorithm into a joint differentially private algorithm using the tree-based algorithm. We then apply either Gaussian noise or Wishart noise to achieve joint-differentially private algorithms and bound the resulting algorithms' regrets. In addition, we give the first lower bound on the additional regret any private algorithms for the MAB problem must incur.

Key facts. Cited by 82 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Sep 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 17; 2023: 15; 2024: 12; 2025: 18; 2026: 8.

82 papers.

Sort:

By area:

  1. 2021Generalized Linear Bandits with Local Differential Privacycited by 29
  2. 2022When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Banditscited by 28
  3. 2022Shuffle Private Linear Contextual Banditscited by 27
  4. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  5. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  6. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  7. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  8. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  9. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  10. 2022Differentially Private Stochastic Linear Bandits: (Almost) for Freecited by 19
  11. 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
  12. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
38 more
  1. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  2. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  3. 2021Differential Privacy in Personalized Pricing with Nonparametric Demand Modelscited by 13
  4. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  5. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  6. 2023Differentially Private Reward Estimation with Preference Feedbackcited by 12
  7. 2021No-Regret Algorithms for Private Gaussian Process Bandit Optimizationcited by 11
  8. 2021Differentially Private Exploration in Reinforcement Learning with Linear Representationcited by 11
  9. 2022Federated Online Clustering of Banditscited by 10
  10. 2023Concentrated Differential Privacy for Banditscited by 10
  11. 2022Private and Byzantine-Proof Cooperative Decision-Makingcited by 9
  12. 2022Improved Regret for Differentially Private Exploration in Linear MDPcited by 8
  13. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  14. 2022Byzantine-Robust Federated Linear Banditscited by 7
  15. 2023Advancements in Federated Learning: Models, Methods, and Privacycited by 7
  16. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  17. 2022Federated X-Armed Banditcited by 5
  18. 2022Dynamic Global Sensitivity for Differentially Private Contextual Banditscited by 5
  19. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  20. 2023On Differentially Private Online Predictionscited by 3
  21. 2023Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regressioncited by 3
  22. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
  23. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  24. 2025Improved Bounds for Private and Robust Alignmentcited by 3
  25. 2021Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environmentcited by 2
  26. 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
  27. 2023An Empirical Evaluation of Federated Contextual Bandit Algorithmscited by 2
  28. 2024Fixed-Budget Differentially Private Best Arm Identificationcited by 2
  29. 2024Replicability is Asymptotically Free in Multi-armed Banditscited by 2
  30. 2024On the Optimal Regret of Locally Private Linear Contextual Banditcited by 2
  31. 2025KL-regularization Itself is Differentially Private in Bandits and RLHFcited by 2
  32. 2025DP-NCB: Privacy Preserving Fair Banditscited by 2
  33. 2021Cascading Bandit under Differential Privacycited by 1
  34. 2022On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Banditscited by 1
  35. 2022Anonymous Bandits for Multi-User Systemscited by 1
  36. 2023Randomized algorithms for precise measurement of differentially-private, personalized recommendationscited by 1
  37. 2024Privacy Preserving Adaptive Experiment Designcited by 1
  38. 2024Fairness and Privacy Guarantees in Federated Contextual Banditscited by 1

50 most cited of 82 All 82 (JSON)