Distributed Clustering of Linear Bandits in Peer to Peer Networks

Nathan Korda, Balazs Szorenyi, Shuai Li
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1301-1309, 2016.

Abstract

We provide two distributed confidence ball algorithms for solving linear bandit problems in peer to peer networks with limited communication capabilities. For the first, we assume that all the peers are solving the same linear bandit problem, and prove that our algorithm achieves the optimal asymptotic regret rate of any centralised algorithm that can instantly communicate information between the peers. For the second, we assume that there are clusters of peers solving the same bandit problem within each cluster, and we prove that our algorithm discovers these clusters, while achieving the optimal asymptotic regret rate within each one. Through experiments on several real-world datasets, we demonstrate the performance of proposed algorithms compared to the state-of-the-art.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-korda16, title = {Distributed Clustering of Linear Bandits in Peer to Peer Networks}, author = {Korda, Nathan and Szorenyi, Balazs and Li, Shuai}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {1301--1309}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/korda16.pdf}, url = {https://proceedings.mlr.press/v48/korda16.html}, abstract = {We provide two distributed confidence ball algorithms for solving linear bandit problems in peer to peer networks with limited communication capabilities. For the first, we assume that all the peers are solving the same linear bandit problem, and prove that our algorithm achieves the optimal asymptotic regret rate of any centralised algorithm that can instantly communicate information between the peers. For the second, we assume that there are clusters of peers solving the same bandit problem within each cluster, and we prove that our algorithm discovers these clusters, while achieving the optimal asymptotic regret rate within each one. Through experiments on several real-world datasets, we demonstrate the performance of proposed algorithms compared to the state-of-the-art.} }
Endnote
%0 Conference Paper %T Distributed Clustering of Linear Bandits in Peer to Peer Networks %A Nathan Korda %A Balazs Szorenyi %A Shuai Li %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-korda16 %I PMLR %P 1301--1309 %U https://proceedings.mlr.press/v48/korda16.html %V 48 %X We provide two distributed confidence ball algorithms for solving linear bandit problems in peer to peer networks with limited communication capabilities. For the first, we assume that all the peers are solving the same linear bandit problem, and prove that our algorithm achieves the optimal asymptotic regret rate of any centralised algorithm that can instantly communicate information between the peers. For the second, we assume that there are clusters of peers solving the same bandit problem within each cluster, and we prove that our algorithm discovers these clusters, while achieving the optimal asymptotic regret rate within each one. Through experiments on several real-world datasets, we demonstrate the performance of proposed algorithms compared to the state-of-the-art.
RIS
TY - CPAPER TI - Distributed Clustering of Linear Bandits in Peer to Peer Networks AU - Nathan Korda AU - Balazs Szorenyi AU - Shuai Li BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-korda16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 1301 EP - 1309 L1 - http://proceedings.mlr.press/v48/korda16.pdf UR - https://proceedings.mlr.press/v48/korda16.html AB - We provide two distributed confidence ball algorithms for solving linear bandit problems in peer to peer networks with limited communication capabilities. For the first, we assume that all the peers are solving the same linear bandit problem, and prove that our algorithm achieves the optimal asymptotic regret rate of any centralised algorithm that can instantly communicate information between the peers. For the second, we assume that there are clusters of peers solving the same bandit problem within each cluster, and we prove that our algorithm discovers these clusters, while achieving the optimal asymptotic regret rate within each one. Through experiments on several real-world datasets, we demonstrate the performance of proposed algorithms compared to the state-of-the-art. ER -
APA
Korda, N., Szorenyi, B. & Li, S.. (2016). Distributed Clustering of Linear Bandits in Peer to Peer Networks. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1301-1309 Available from https://proceedings.mlr.press/v48/korda16.html.

Related Material