# Locally Private Nonparametric Contextual Multi-armed Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 39 of its 61 references that are in the map.
- First posted on arXiv 11 Mar 2025.

## Builds on (most cited first, 30 of 39)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Transfer Learning for High-dimensional Linear Regression: Prediction, Estimation, and Minimax Optimality](https://mlsanity.com/paper/2006.10593/) (2020)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [Transfer Learning for Nonparametric Classification: Minimax Rate and Adaptive Classifier](https://mlsanity.com/paper/1906.02903/) (2019)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [Multi-Task Learning for Contextual Bandits](https://mlsanity.com/paper/1705.08618/) (2017)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12](https://mlsanity.com/paper/1709.02753/) (2017)
- [Local Differential Privacy and Its Applications: A Comprehensive Survey](https://mlsanity.com/paper/2008.03686/) (2020)
- [A new similarity measure for covariate shift with applications to nonparametric regression](https://mlsanity.com/paper/2202.02837/) (2022)
- [Balanced Linear Contextual Bandits](https://mlsanity.com/paper/1812.06227/) (2018)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Transfer Learning for Contextual Multi-armed Bandits](https://mlsanity.com/paper/2211.12612/) (2022)
- [Transfer Learning for Nonparametric Regression: Non-asymptotic Minimax Analysis and Adaptive Procedure](https://mlsanity.com/paper/2401.12272/) (2024)
- [Privacy Amplification via Shuffling for Linear Contextual Bandits](https://mlsanity.com/paper/2112.06008/) (2021)
- [Multitask Bandit Learning Through Heterogeneous Feedback Aggregation](https://mlsanity.com/paper/2010.15390/) (2020)
- [Offline Contextual Multi-armed Bandits for Mobile Health Interventions: A Case Study on Emotion Regulation](https://mlsanity.com/paper/2008.09472/) (2020)
- [Differential Privacy in Personalized Pricing with Nonparametric Demand Models](https://mlsanity.com/paper/2109.04615/) (2021)
- [Differentially Private Bayesian Optimization](https://mlsanity.com/paper/1501.04080/) (2015)
- [Self-Tuning Bandits over Unknown Covariate-Shifts](https://mlsanity.com/paper/2007.08584/) (2020)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [Classification under local differential privacy](https://mlsanity.com/paper/1912.04629/) (2019)
- [Strongly universally consistent nonparametric regression and classification with privatised data](https://mlsanity.com/paper/2011.00216/) (2020)

## Abstract (arXiv)

Motivated by privacy concerns in sequential decision-making on sensitive data, we address the challenge of nonparametric contextual multi-armed bandits (MAB) under local differential privacy (LDP). We develop a uniform-confidence-bound-type estimator, showing its minimax optimality supported by a matching minimax lower bound. We further consider the case where auxiliary datasets are available, subject also to (possibly heterogeneous) LDP constraints. Under the widely-used covariate shift framework, we propose a jump-start scheme to effectively utilize the auxiliary data, the minimax optimality of which is further established by a matching lower bound. Comprehensive experiments on both synthetic and real-world datasets validate our theoretical results and underscore the effectiveness of the proposed methods.