  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.
