Abstract
This paper addresses the challenge of maintaining user privacy in stochastic multi-armed bandit (MAB) problems. We introduce two novel Thompson Sampling-based algorithms: DP-TS and Lazy-DP-TS. By incorporating the principle of "optimism in the face of uncertainty" into the posterior distribution, these algorithms achieve near-optimal and optimal regret bounds, respectively. Specifically, Lazy-DP-TS achieves a regret of $\sum_{j \in \mathcal{A}: \Delta_j > 0} O \left(\frac{\log(T)}{\min \{\epsilon, \Delta_j \}} \right)$, matching the theoretical lower bound for differentially private bandits. Empirical evaluations demonstrate that our proposed methods consistently outperform existing state-of-the-art algorithms across various privacy regimes.
Introduction
The Stochastic Multi-Armed Bandit (MAB) problem is a fundamental framework for sequential decision-making under uncertainty. An agent repeatedly selects an action (an "arm") and receives a reward, aiming to maximize the cumulative reward over time. While algorithms like Thompson Sampling (TS) are highly effective, they typically require access to exact reward data. In sensitive domains such as personalized healthcare or targeted advertising, this data often contains private information.
Differential Privacy (DP) provides a rigorous mathematical standard for protecting individual privacy. A differentially private bandit algorithm ensures that the presence or absence of a single user's data does not significantly alter the algorithm's behavior. The central challenge is balancing the "noise tax" required for privacy with the need for low regret—the difference between the rewards of the chosen strategy and the optimal one.
Methodology
We propose two algorithms that adapt Thompson Sampling for the private setting by reshaping the posterior distribution to remain "optimistic" despite added noise.
DP-TS: Differentially Private Thompson Sampling
DP-TS utilizes all available observations. To satisfy DP, it adds noise to the cumulative rewards using a combination of a modified Logarithmic Mechanism and a Binary Mechanism. To counteract the uncertainty introduced by this noise, the algorithm shifts the posterior distribution of each arm to the right. This ensures that the algorithm continues to explore arms that might appear sub-optimal simply due to the privacy-preserving noise.
Lazy-DP-TS: Achieving Optimality through Data Dropping
While DP-TS is near-optimal, it incurs an extra logarithmic factor in its regret bound. To reach the theoretical lower bound, we introduce Lazy-DP-TS. This algorithm employs a "lazy" update strategy, processing observations in batches of doubling size.
Crucially, Lazy-DP-TS uses fresh subsequences of data for each update and discards previous observations. Although discarding data seems counter-intuitive, it significantly reduces the total sensitivity of the reward estimates over the time horizon $T$. This reduction in sensitivity allows for less added noise, ultimately leading to optimal regret performance.
Theoretical Results
The primary contribution of this work is the derivation of regret bounds that match the fundamental limits of private learning.
- DP-TS achieves a regret bound of $\sum_{j \in \mathcal{A}: \Delta_j > 0} O \left(\frac{\log(T)}{\min \{\epsilon, \Delta_j \}} \log \left(\frac{\log(T)}{\epsilon \cdot \Delta_j} \right) \right)$.
- Lazy-DP-TS improves this to $ \sum_{j \in \mathcal{A}: \Delta_j > 0} O \left(\frac{\log(T)}{\min \{\epsilon, \Delta_j \}} \right)$, which is asymptotically optimal.
Empirical Performance
We evaluated our algorithms using synthetic Bernoulli bandit environments with 5 arms (mean rewards 0.25 to 0.75) over a horizon of $T = 10^5$. We compared them against existing benchmarks, including DP-SE (Successive Elimination) and Anytime-Lazy-UCB.
In the low-privacy regime ($\epsilon = 500$), both DP-TS and Lazy-DP-TS exhibit very low regret, significantly outperforming UCB-based and elimination-based methods. In this setting, DP-TS slightly outperforms its "lazy" counterpart because it utilizes the full dataset.
As the privacy constraint tightens ($\epsilon = 0.1$), the advantage of the "lazy" update strategy becomes evident. Lazy-DP-TS maintains the lowest regret, demonstrating its robustness to the high levels of noise required for strict differential privacy.
Conclusion
This work demonstrates that Thompson Sampling can be effectively adapted for differentially private bandits. By strategically reshaping the posterior and managing data usage through lazy updates, we can achieve optimal regret while guaranteeing user privacy. Future research may explore leveraging the inherent stochasticity of Thompson Sampling to provide "privacy for free," potentially further reducing the noise requirements in private sequential decision-making.
Summary updated