# Cascading Bandit under Differential Privacy

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 24 May 2021.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Multi-Armed Bandits with Local Differential Privacy](https://mlsanity.com/paper/2007.03121/) (2020)
- [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)
- [(Locally) Differentially Private Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.00706/) (2020)
- [Reviewing and Improving the Gaussian Mechanism for Differential Privacy](https://mlsanity.com/paper/1911.12060/) (2019)
- [Conservative Contextual Combinatorial Cascading Bandit](https://mlsanity.com/paper/2104.08615/) (2021)

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

- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)

## Abstract (arXiv)

This paper studies differential privacy (DP) and local differential privacy (LDP) in cascading bandits. Under DP, we propose an algorithm which guarantees ε-indistinguishability and a regret of O((fraclog Tε)1+xi) for an arbitrarily small xi. This is a significant improvement from the previous work of O(fraclog3 Tε) regret. Under (ε,δ)-LDP, we relax the K2 dependence through the tradeoff between privacy budget ε and error probability δ, and obtain a regret of O(fracKlog (1/δ) log Tε2), where K is the size of the arm subset. This result holds for both Gaussian mechanism and Laplace mechanism by analyses on the composition. Our results extend to combinatorial semi-bandit. We show respective lower bounds for DP and LDP cascading bandits. Extensive experiments corroborate our theoretic findings.