- 152 views
- 236 downloads
Optimal Differentially Private Finite Armed Stochastic Bandit
-
- Author / Creator
- Sajed, Touqir
-
We present two provably optimal differentially private algorithms for the stochastic multi-arm bandit problem, as opposed to the private analogue of the UCB-algorithm (Mishra and Thakurta 2015; Tossou and Dimitrakakis 2016) which doesn’t meet the recently discovered lower-bound of Ω( K log(T) / epsilon ) (Shariff and Sheffet 2018). Our construction is based on a different algorithm, Successive Elimination (Even-Dar, Mannor, and Mansour 2002), that repeatedly pulls all remaining arms until an arm is found to be suboptimal and is then eliminated. We devise two private analogues of Successive Elimination. We also visit the problem of a private stopping rule, that takes as input a stream of i.i.d samples from an unknown distribution and returns a multiplicative (1±α)-approximation of the distribution’s mean, and prove the optimality of our private stopping rule. One of our differentially private versions of Successive Elimination leverages the private stopping rule algorithm that meets both the non-private lower bound (Lai and Robbins 1985) and the above-mentioned private lower bound, while the other variant relies on simpler techniques to achieve both the lower bounds. We also compare empirically the performance of our algorithms with the private UCB algorithm.
-
- Graduation date
- Fall 2019
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.