Achieving Privacy in the Adversarial Multi-Armed Bandit
Abstract
In this paper, we improve the previously best known regret bound to achieve ε-differential privacy in oblivious adversarial bandits from O(T2/3 /ε) to O(√T lnT/ε). This is achieved by combining a Laplace Mechanism with EXP3. We show that though EXP3 is already differentially private, it leaks a linear amount of information in T. However, we can improve this privacy by relying on its intrinsic exponential mechanism for selecting actions. This allows us to reach O(√ ln T)-DP, with a a regret of O(T2/3) that holds against an adaptive adversary, an improvement from the best known of O(T3/4). This is done by using an algorithm that run EXP3 in a mini-batch loop. Finally, we run experiments that clearly demonstrate the validity of our theoretical analysis.
Cite
Text
Tossou and Dimitrakakis. "Achieving Privacy in the Adversarial Multi-Armed Bandit." AAAI Conference on Artificial Intelligence, 2017. doi:10.1609/AAAI.V31I1.10896Markdown
[Tossou and Dimitrakakis. "Achieving Privacy in the Adversarial Multi-Armed Bandit." AAAI Conference on Artificial Intelligence, 2017.](https://mlanthology.org/aaai/2017/tossou2017aaai-achieving/) doi:10.1609/AAAI.V31I1.10896BibTeX
@inproceedings{tossou2017aaai-achieving,
title = {{Achieving Privacy in the Adversarial Multi-Armed Bandit}},
author = {Tossou, Aristide Charles Yedia and Dimitrakakis, Christos},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2017},
pages = {2653-2659},
doi = {10.1609/AAAI.V31I1.10896},
url = {https://mlanthology.org/aaai/2017/tossou2017aaai-achieving/}
}