# Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 42 references that are in the map.
- First posted on arXiv 16 Feb 2021.

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

- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule](https://mlsanity.com/paper/1905.09383/) (2019)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [MOTS: Minimax Optimal Thompson Sampling](https://mlsanity.com/paper/2003.01803/) (2020)
- [(Locally) Differentially Private Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.00706/) (2020)

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

- [Thompson Sampling Itself is Differentially Private](https://mlsanity.com/paper/2407.14879/) (2024)
- [Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning](https://mlsanity.com/paper/2605.29148/) (2026)

## Abstract (arXiv)

In this paper, we study differentially private online learning problems in a stochastic environment under both bandit and full information feedback. For differentially private stochastic bandits, we propose both UCB and Thompson Sampling-based algorithms that are anytime and achieve the optimal O left(sumj: Deltaj>0 fracln(T)min leftDeltaj, ε right right) instance-dependent regret bound, where T is the finite learning horizon, Deltaj denotes the suboptimality gap between the optimal arm and a suboptimal arm j, and ε is the required privacy parameter. For the differentially private full information setting with stochastic rewards, we show an Omega left(fracln(K)min leftDeltamin, ε right right) instance-dependent regret lower bound and an Omegaleft(√Tln(K) + fracln(K)εright) minimax lower bound, where K is the total number of actions and Deltamin denotes the minimum suboptimality gap among all the suboptimal actions. For the same differentially private full information setting, we also present an ε-differentially private algorithm whose instance-dependent regret and worst-case regret match our respective lower bounds up to an extra log(T) factor.