# On the Optimal Regret of Locally Private Linear Contextual Bandit

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 15 Apr 2024.

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

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [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)
- [Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits](https://mlsanity.com/paper/2007.07876/) (2020)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Privacy-Preserving Dynamic Personalized Pricing with Demand Learning](https://mlsanity.com/paper/2009.12920/) (2020)
- [Differentially Private Stochastic Linear Bandits: (Almost) for Free](https://mlsanity.com/paper/2207.03445/) (2022)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [Differential Privacy in Personalized Pricing with Nonparametric Demand Models](https://mlsanity.com/paper/2109.04615/) (2021)
- [Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection](https://mlsanity.com/paper/2009.02003/) (2020)
- [Wishart Mechanism for Differentially Private Principal Components Analysis](https://mlsanity.com/paper/1511.05680/) (2015)
- [Singularity structures and impacts on parameter estimation in finite mixtures of distributions](https://mlsanity.com/paper/1609.02655/) (2016)
- [Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data](https://mlsanity.com/paper/1910.00482/) (2019)

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

- [Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2602.00417/) (2026)
- [Locally Private Nonparametric Contextual Multi-armed Bandits](https://mlsanity.com/paper/2503.08098/) (2025)

## Abstract (arXiv)

Contextual bandit with linear reward functions is among one of the most extensively studied models in bandit and online learning research. Recently, there has been increasing interest in designing locally private linear contextual bandit algorithms, where sensitive information contained in contexts and rewards is protected against leakage to the general public. While the classical linear contextual bandit algorithm admits cumulative regret upper bounds of tilde O(√T) via multiple alternative methods, it has remained open whether such regret bounds are attainable in the presence of local privacy constraints, with the state-of-the-art result being tilde O(T3/4). In this paper, we show that it is indeed possible to achieve an tilde O(√T) regret upper bound for locally private linear contextual bandit. Our solution relies on several new algorithmic and analytical ideas, such as the analysis of mean absolute deviation errors and layered principal component regression in order to achieve small mean absolute deviation errors.