# Interactive and Concentrated Differential Privacy for Bandits

**Authors:** Achraf Azize, Debabrota Basu  
**arXiv:** [2309.00557](https://arxiv.org/abs/2309.00557)  
**Date:** 2023-09-01  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2309.00557v1/

## Key points

- Bandits play a pivotal role in interactive learning schemes and modern recommender systems
- Privacy concerns arise due to reliance on sensitive user data in these systems
- This paper focuses on privacy in bandits with a trusted centralized decision-maker using interactive Differential Privacy (DP)
- Study introduces zero Concentrated DP (zCDP) for understanding bandits, providing lower bounds on regret for finite-armed and linear bandits under $\rho$-global zCDP
- Two novel $\rho$-global zCDP bandit algorithms proposed: AdaC-UCB for finite-armed bandits and AdaC-GOPE for linear bandits, leveraging Gaussian mechanism and adaptive episodes
- AdaC-UCB achieves problem-dependent regret lower bound accurately, while AdaC-GOPE attains minimax regret lower bound with poly-logarithmic factors
- Theoretical findings validated through experimental simulations, highlighting the balance between privacy preservation and performance optimization in bandit algorithms

## Summary

, , , , 

In the realm of interactive learning schemes and modern recommender systems, bandits play a pivotal role. However, these systems often rely on sensitive user data, raising significant privacy concerns. This paper delves into the realm of privacy in bandits with a trusted centralized decision-maker through the lens of interactive Differential Privacy (DP). Previous studies have extensively explored bandits under pure $\epsilon$-global DP, but this research contributes to understanding bandits under zero Concentrated DP (zCDP). By providing minimax and problem-dependent lower bounds on regret for both finite-armed and linear bandits, this study quantifies the impact of $\rho$-global zCDP in these settings. These lower bounds unveil two distinct hardness regimes based on the privacy budget $\rho$, indicating that $\rho$-global zCDP may result in less regret compared to pure $\epsilon$-global DP. To address these challenges, two novel $\rho$-global zCDP bandit algorithms are proposed: AdaC-UCB for finite-armed bandits and AdaC-GOPE for linear bandits. Both algorithms leverage a Gaussian mechanism and adaptive episodes as part of their design. Through rigorous analysis, it is demonstrated that AdaC-UCB achieves the problem-dependent regret lower bound with high accuracy while AdaC-GOPE attains the minimax regret lower bound with poly-logarithmic factors. The theoretical findings are further validated through experimental simulations conducted under various settings. The research sheds light on the intricate balance between privacy preservation and performance optimization in bandit algorithms, offering valuable insights for enhancing privacy-aware decision-making processes in interactive learning environments.