# (Locally) Differentially Private Combinatorial Semi-Bandits

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2020.

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

- [Large Scale Private Learning via Low-rank Reparametrization](https://mlsanity.com/paper/2106.09352/) (2021)
- [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)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Differentially Private Regret Minimization in Episodic Markov Decision Processes](https://mlsanity.com/paper/2112.10599/) (2021)
- [Offline Reinforcement Learning with Differential Privacy](https://mlsanity.com/paper/2206.00810/) (2022)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2110.10133/) (2021)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment](https://mlsanity.com/paper/2102.07929/) (2021)
- [Concurrent Shuffle Differential Privacy Under Continual Observation](https://mlsanity.com/paper/2301.12535/) (2023)
- [Cascading Bandit under Differential Privacy](https://mlsanity.com/paper/2105.11126/) (2021)
- [The Safety-Privacy Tradeoff in Linear Bandits](https://mlsanity.com/paper/2504.16371/) (2025)
- [Unlearning Offline Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2605.00638/) (2026)

## Abstract (arXiv)

In this paper, we study Combinatorial Semi-Bandits (CSB) that is an extension of classic Multi-Armed Bandits (MAB) under Differential Privacy (DP) and stronger Local Differential Privacy (LDP) setting. Since the server receives more information from users in CSB, it usually causes additional dependence on the dimension of data, which is a notorious side-effect for privacy preserving learning. However for CSB under two common smoothness assumptions citekveton2015tight,chen2016combinatorial, we show it is possible to remove this side-effect. In detail, for B∞-bounded smooth CSB under either varepsilon-LDP or varepsilon-DP, we prove the optimal regret bound is Theta(fracmB2∞ln T  Deltaε2) or tildeTheta(fracmB2∞ln T  Deltaε) respectively, where T is time period, Delta is the gap of rewards and m is the number of base arms, by proposing novel algorithms and matching lower bounds. For B1-bounded smooth CSB under varepsilon-DP, we also prove the optimal regret bound is tildeTheta(fracmKB21ln T Deltaε) with both upper bound and lower bound, where K is the maximum number of feedback in each round. All above results nearly match corresponding non-private optimal rates, which imply there is no additional price for (locally) differentially private CSB in above common settings.