mlsanityData to 14 Oct 2026

Differentially Private Linear Bandits with Partial Distributed Feedback

arXiv 2207.05827 ↗First posted 12 Jul 2022cs.LG cs.CR cs.NAcited by 8

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the problem of global reward maximization with only partial distributed feedback. This problem is motivated by several real-world applications (e.g., cellular network configuration, dynamic pricing, and policy selection) where an action taken by a central entity influences a large population that contributes to the global reward. However, collecting such reward feedback from the entire population not only incurs a prohibitively high cost but often leads to privacy concerns. To tackle this problem, we consider differentially private distributed linear bandits, where only a subset of users from the population are selected (called clients) to participate in the learning process and the central server learns the global model from such partial feedback by iteratively aggregating these clients' local feedback in a differentially private fashion. We then propose a unified algorithmic learning framework, called differentially private distributed phased elimination (DP-DPE), which can be naturally integrated with popular differential privacy (DP) models (including central DP, local DP, and shuffle DP). Furthermore, we prove that DP-DPE achieves both sublinear regret and sublinear communication cost. Interestingly, DP-DPE also achieves privacy protection ``for free'' in the sense that the additional cost due to privacy guarantees is a lower-order additive term. In addition, as a by-product of our techniques, the same results of ``free" privacy can also be achieved for the standard differentially private linear bandits. Finally, we conduct simulations to corroborate our theoretical results and demonstrate the effectiveness of DP-DPE.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 30 of its 55 references that are in the map. First posted on arXiv 12 Jul 2022.

Builds on

30 of 55 references.

References · 30

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Introduction to Multi-Armed Banditscited by 481
  3. 2017Differentially Private Federated Learning: A Client Level Perspectivecited by 459
  4. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  5. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 164
  6. 2020The Discrete Gaussian for Differential Privacycited by 135
  7. 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 128
  8. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  9. 2018Distributed Differential Privacy via Shufflingcited by 115
  10. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 107
  11. 2020Differentially-Private Federated Linear Banditscited by 83
  12. 2018Differentially Private Contextual Linear Banditscited by 82
18 more
  1. 2020Federated Bayesian Optimization via Thompson Samplingcited by 77
  2. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  3. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  4. 2021Federated Linear Contextual Banditscited by 61
  5. 2021Federated Multi-Armed Banditscited by 59
  6. 2020Federated Bandit: A Gossiping Approachcited by 55
  7. 2020Locally Differentially Private (Contextual) Bandits Learningcited by 53
  8. 2015Algorithms for Differentially Private Multi-Armed Banditscited by 45
  9. 2020Multi-Armed Bandits with Local Differential Privacycited by 37
  10. 2020Cooperative Multi-Agent Bandits with Heavy Tailscited by 31
  11. 2021Multi-Agent Multi-Armed Bandits with Limited Communicationcited by 29
  12. 2022Shuffle Private Linear Contextual Banditscited by 27
  13. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  14. 2020Kernel Methods for Cooperative Multi-Agent Contextual Banditscited by 21
  15. 2020Local Differential Privacy for Bayesian Optimizationcited by 19
  16. 2021Shuffle Private Stochastic Convex Optimizationcited by 17
  17. 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
  18. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14

Built on by

Cited by year

Citing papers per year: 2023: 5; 2024: 1; 2025: 2.

8 papers.

  1. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  2. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  3. 2023Concentrated Differential Privacy for Banditscited by 10
  4. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  5. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  6. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
  7. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  8. 2025Optimal Regret of Bernoulli Bandits under Global Differential Privacycited by 0