(Locally) Differentially Private Combinatorial Semi-Bandits
Not on the map. Why?
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.
Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Jun 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 7; 2022: 3; 2023: 2; 2024: 0; 2025: 1; 2026: 1.
14 papers.
Sort:
By area:
- 2021Large Scale Private Learning via Low-rank Reparametrizationcited by 87
- 2021Generalized Linear Bandits with Local Differential Privacycited by 29
- 2022Shuffle Private Linear Contextual Banditscited by 27
- 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
- 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
- 2022Offline Reinforcement Learning with Differential Privacycited by 19
- 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
- 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
- 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
- 2021Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environmentcited by 2
- 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
- 2021Cascading Bandit under Differential Privacycited by 1
2 more
- 2025The Safety-Privacy Tradeoff in Linear Banditscited by 0
- 2026Unlearning Offline Stochastic Multi-Armed Banditscited by 0
- 2026Unlearning Offline Stochastic Multi-Armed Bandits1 May 2026
- 2025The Safety-Privacy Tradeoff in Linear Bandits23 Apr 2025
- 2023Federated Linear Contextual Bandits with User-level Differential Privacy8 Jun 2023
- 2023Concurrent Shuffle Differential Privacy Under Continual Observation29 Jan 2023
- 2022Distributed Differential Privacy in Multi-Armed Bandits12 Jun 2022
- 2022Offline Reinforcement Learning with Differential Privacy2 Jun 2022
- 2022Shuffle Private Linear Contextual Bandits11 Feb 2022
- 2021Differentially Private Regret Minimization in Episodic Markov Decision Processes20 Dec 2021
- 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processes19 Oct 2021
- 2021Large Scale Private Learning via Low-rank Reparametrization17 Jun 2021
- 2021Generalized Linear Bandits with Local Differential Privacy7 Jun 2021
- 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits4 Jun 2021
2 more
- 2022Offline Reinforcement Learning with Differential Privacycited by 19
- 2022Offline Reinforcement Learning with Differential Privacy2 Jun 2022
- 2026Unlearning Offline Stochastic Multi-Armed Banditscited by 0
- 2026Unlearning Offline Stochastic Multi-Armed Bandits1 May 2026
- 2021Large Scale Private Learning via Low-rank Reparametrizationcited by 87
- 2021Generalized Linear Bandits with Local Differential Privacycited by 29
- 2022Shuffle Private Linear Contextual Banditscited by 27
- 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
- 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
- 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
- 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
- 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
- 2021Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environmentcited by 2
- 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
- 2021Cascading Bandit under Differential Privacycited by 1
- 2025The Safety-Privacy Tradeoff in Linear Banditscited by 0
- 2025The Safety-Privacy Tradeoff in Linear Bandits23 Apr 2025
- 2023Federated Linear Contextual Bandits with User-level Differential Privacy8 Jun 2023
- 2023Concurrent Shuffle Differential Privacy Under Continual Observation29 Jan 2023
- 2022Distributed Differential Privacy in Multi-Armed Bandits12 Jun 2022
- 2022Shuffle Private Linear Contextual Bandits11 Feb 2022
- 2021Differentially Private Regret Minimization in Episodic Markov Decision Processes20 Dec 2021
- 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processes19 Oct 2021
- 2021Large Scale Private Learning via Low-rank Reparametrization17 Jun 2021
- 2021Generalized Linear Bandits with Local Differential Privacy7 Jun 2021
- 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits4 Jun 2021
- 2021Cascading Bandit under Differential Privacy24 May 2021
- 2021Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment16 Feb 2021