# Dynamic Global Sensitivity for Differentially Private Contextual Bandits

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 42 references that are in the map.
- First posted on arXiv 30 Aug 2022.

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

- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [AdaCliP: Adaptive Clipping for Private SGD](https://mlsanity.com/paper/1908.07643/) (2019)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [Multi-Armed Bandits with Local Differential Privacy](https://mlsanity.com/paper/2007.03121/) (2020)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?](https://mlsanity.com/paper/1905.12298/) (2019)
- [Achieving Privacy in the Adversarial Multi-Armed Bandit](https://mlsanity.com/paper/1701.04222/) (2017)
- [Mitigating Bias in Adaptive Data Gathering via Differential Privacy](https://mlsanity.com/paper/1806.02329/) (2018)
- [Private and Byzantine-Proof Cooperative Decision-Making](https://mlsanity.com/paper/2205.14174/) (2022)

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

- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces](https://mlsanity.com/paper/2510.19349/) (2025)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Locally Private Nonparametric Contextual Multi-armed Bandits](https://mlsanity.com/paper/2503.08098/) (2025)
- [AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification](https://mlsanity.com/paper/2606.21757/) (2026)

## Abstract (arXiv)

Bandit algorithms have become a reference solution for interactive recommendation. However, as such algorithms directly interact with users for improved recommendations, serious privacy concerns have been raised regarding its practical use. In this work, we propose a differentially private linear contextual bandit algorithm, via a tree-based mechanism to add Laplace or Gaussian noise to model parameters. Our key insight is that as the model converges during online update, the global sensitivity of its parameters shrinks over time (thus named dynamic global sensitivity). Compared with existing solutions, our dynamic global sensitivity analysis allows us to inject less noise to obtain (ε, δ)-differential privacy with added regret caused by noise injection in tilde O(logT√T/ε). We provide a rigorous theoretical analysis over the amount of noise added via dynamic global sensitivity and the corresponding upper regret bound of our proposed algorithm. Experimental results on both synthetic and real-world datasets confirmed the algorithm's advantage against existing solutions.