Optimal Regret of Bandits under Differential Privacy

par Achraf Azize (TSE)

mardi 10 nov. 2026, 11:15 → 12:15 Europe/Paris

Salle K. Johnson (1R3, 1er étage)

As sequential learning algorithms are increasingly applied to real life, ensuring data privacy while maintaining their utility emerges as a timely question. This talk explores this question through stochastic multi-armed bandits, a basic model of sequential decision-making, and Differential Privacy (DP), a standard framework for formalising privacy guarantees. I will begin with an introduction to bandits, regret minimisation, and DP, before bringing these concepts together to study the trade-off between privacy and regret.
I will then present the main ideas behind proving regret lower bounds under privacy constraints and designing algorithms that attain them. On one hand, the lower bound introduces a new information-theoretic quantity, smoothly interpolating between Kullback–Leibler divergence and Total Variation distance, that characterises the hardness of DP in stochastic bandits. On the other hand, the algorithms follow a unified blueprint combining adaptive phases, calibrated Laplace noise added to sufficient statistics, and exploration bonuses that account for this noise. For Bernoulli bandits under DP, I will show a specialisation of this blueprint achieving a regret that asymptotically matches our lower bound up to a multiplicative factor, arbitrarily close to one.