# When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits

arXiv: https://arxiv.org/abs/2209.02570 · HTML: https://mlsanity.com/paper/2209.02570/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 32 references that are in the map.
- First posted on arXiv 6 Sep 2022.

## Builds on (most cited first, 13 of 13)

- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [Private Reinforcement Learning with PAC and Regret Guarantees](https://mlsanity.com/paper/2009.09052/) (2020)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule](https://mlsanity.com/paper/1905.09383/) (2019)
- [Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?](https://mlsanity.com/paper/1905.12298/) (2019)
- [Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates](https://mlsanity.com/paper/1302.3203/) (2013)
- [Achieving Privacy in the Adversarial Multi-Armed Bandit](https://mlsanity.com/paper/1701.04222/) (2017)
- [Differentially Private Multi-Armed Bandits in the Shuffle Model](https://mlsanity.com/paper/2106.02900/) (2021)
- [Mitigating Bias in Adaptive Data Gathering via Differential Privacy](https://mlsanity.com/paper/1806.02329/) (2018)

## Built on by (most cited first, 28 of 28)

- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Concentrated Differential Privacy for Bandits](https://mlsanity.com/paper/2309.00557/) (2023)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (2023)
- [On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2309.02202/) (2023)
- [Improved Bounds for Private and Robust Alignment](https://mlsanity.com/paper/2512.23816/) (2025)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [Differentially Private Kernelized Contextual Bandits](https://mlsanity.com/paper/2501.07046/) (2025)
- [KL-regularization Itself is Differentially Private in Bandits and RLHF](https://mlsanity.com/paper/2505.18407/) (2025)
- [Fixed-Budget Differentially Private Best Arm Identification](https://mlsanity.com/paper/2401.09073/) (2024)
- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [DP-NCB: Privacy Preserving Fair Bandits](https://mlsanity.com/paper/2508.03836/) (2025)
- [Privacy Preserving Adaptive Experiment Design](https://mlsanity.com/paper/2401.08224/) (2024)
- [FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2405.14038/) (2024)
- [Privacy Preserving Reinforcement Learning for Population Processes](https://mlsanity.com/paper/2406.17649/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Near-Optimal Reinforcement Learning with Shuffle Differential Privacy](https://mlsanity.com/paper/2411.11647/) (2024)
- [Faster Rates for Private Adversarial Bandits](https://mlsanity.com/paper/2505.21790/) (2025)
- [Privacy-Preserving UCB Decision Process Verification via zk-SNARKs](https://mlsanity.com/paper/2404.12186/) (2024)
- [Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing](https://mlsanity.com/paper/2503.07775/) (2025)
- [Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret](https://mlsanity.com/paper/2505.02383/) (2025)
- [Optimal Regret of Bernoulli Bandits under Global Differential Privacy](https://mlsanity.com/paper/2505.05613/) (2025)
- [Differential Privacy in Kernelized Contextual Bandits via Random Projections](https://mlsanity.com/paper/2507.13639/) (2025)
- [Locally Differentially Private Thresholding Bandits](https://mlsanity.com/paper/2507.23073/) (2025)
- [The Fair Game: Auditing & Debiasing AI Algorithms Over Time](https://mlsanity.com/paper/2508.06443/) (2025)
- [Beyond ATE: Multi-Criteria Design for A/B Testing](https://mlsanity.com/paper/2509.05864/) (2025)
- [Randomized Least Squares Value Iteration itself is Joint Differentially Private](https://mlsanity.com/paper/2606.01952/) (2026)

## Abstract (arXiv)

We study the problem of multi-armed bandits with ε-global Differential Privacy (DP). First, we prove the minimax and problem-dependent regret lower bounds for stochastic and linear bandits that quantify the hardness of bandits with ε-global DP. These bounds suggest the existence of two hardness regimes depending on the privacy budget ε. In the high-privacy regime (small ε), the hardness depends on a coupled effect of privacy and partial information about the reward distributions. In the low-privacy regime (large ε), bandits with ε-global DP are not harder than the bandits without privacy. For stochastic bandits, we further propose a generic framework to design a near-optimal ε global DP extension of an index-based optimistic bandit algorithm. The framework consists of three ingredients: the Laplace mechanism, arm-dependent adaptive episodes, and usage of only the rewards collected in the last episode for computing private statistics. Specifically, we instantiate ε-global DP extensions of UCB and KL-UCB algorithms, namely AdaP-UCB and AdaP-KLUCB. AdaP-KLUCB is the first algorithm that both satisfies ε-global DP and yields a regret upper bound that matches the problem-dependent lower bound up to multiplicative constants.