Multi-Agent Best Arm Identification with Private Communications

Alexandre Rio, Merwan Barlier, Igor Colin, Marta Soare
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:29082-29102, 2023.

Abstract

We address multi-agent best arm identification with privacy guarantees. In this setting, agents collaborate by communicating to find the optimal arm. To avoid leaking sensitive data through messages, we consider two notions of privacy withholding different kinds of information: differential privacy and $(\epsilon, \eta)$-privacy. For each privacy definition, we propose an algorithm based on a two-level successive elimination scheme. We provide theoretical guarantees for the privacy level, accuracy and sample complexity of our algorithms. Experiments on various settings support our theoretical findings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-rio23a, title = {Multi-Agent Best Arm Identification with Private Communications}, author = {Rio, Alexandre and Barlier, Merwan and Colin, Igor and Soare, Marta}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {29082--29102}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/rio23a/rio23a.pdf}, url = {https://proceedings.mlr.press/v202/rio23a.html}, abstract = {We address multi-agent best arm identification with privacy guarantees. In this setting, agents collaborate by communicating to find the optimal arm. To avoid leaking sensitive data through messages, we consider two notions of privacy withholding different kinds of information: differential privacy and $(\epsilon, \eta)$-privacy. For each privacy definition, we propose an algorithm based on a two-level successive elimination scheme. We provide theoretical guarantees for the privacy level, accuracy and sample complexity of our algorithms. Experiments on various settings support our theoretical findings.} }
Endnote
%0 Conference Paper %T Multi-Agent Best Arm Identification with Private Communications %A Alexandre Rio %A Merwan Barlier %A Igor Colin %A Marta Soare %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-rio23a %I PMLR %P 29082--29102 %U https://proceedings.mlr.press/v202/rio23a.html %V 202 %X We address multi-agent best arm identification with privacy guarantees. In this setting, agents collaborate by communicating to find the optimal arm. To avoid leaking sensitive data through messages, we consider two notions of privacy withholding different kinds of information: differential privacy and $(\epsilon, \eta)$-privacy. For each privacy definition, we propose an algorithm based on a two-level successive elimination scheme. We provide theoretical guarantees for the privacy level, accuracy and sample complexity of our algorithms. Experiments on various settings support our theoretical findings.
APA
Rio, A., Barlier, M., Colin, I. & Soare, M.. (2023). Multi-Agent Best Arm Identification with Private Communications. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:29082-29102 Available from https://proceedings.mlr.press/v202/rio23a.html.

Related Material