Distributed cooperative decision-making in multiarmed bandits: Frequentist and Bayesian algorithms

Peter Landgren; Vaibhav Srivastava; Naomi Ehrich Leonard

doi:10.1109/CDC.2016.7798264

Distributed cooperative decision-making in multiarmed bandits: Frequentist and Bayesian algorithms

Peter Landgren, Vaibhav Srivastava, Naomi Ehrich Leonard

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

73 Scopus citations

Abstract

We study distributed cooperative decision-making under the explore-exploit tradeoff in the multiarmed bandit (MAB) problem. We extend state-of-the-art frequentist and Bayesian algorithms for single-agent MAB problems to cooperative distributed algorithms for multi-agent MAB problems in which agents communicate according to a fixed network graph. We rely on a running consensus algorithm for each agent's estimation of mean rewards from its own rewards and the estimated rewards of its neighbors. We prove the performance of these algorithms and show that they asymptotically recover the performance of a centralized agent. Further, we rigorously characterize the influence of the communication graph structure on the decision-making performance of the group.

Original language	English (US)
Title of host publication	2016 IEEE 55th Conference on Decision and Control, CDC 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	167-172
Number of pages	6
ISBN (Electronic)	9781509018376
DOIs	https://doi.org/10.1109/CDC.2016.7798264
State	Published - Dec 27 2016
Event	55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States Duration: Dec 12 2016 → Dec 14 2016

Publication series

Name	2016 IEEE 55th Conference on Decision and Control, CDC 2016

Other

Other	55th IEEE Conference on Decision and Control, CDC 2016
Country/Territory	United States
City	Las Vegas
Period	12/12/16 → 12/14/16

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Decision Sciences (miscellaneous)
Control and Optimization

Access to Document

10.1109/CDC.2016.7798264

Cite this

Landgren, P., Srivastava, V., & Leonard, N. E. (2016). Distributed cooperative decision-making in multiarmed bandits: Frequentist and Bayesian algorithms. In 2016 IEEE 55th Conference on Decision and Control, CDC 2016 (pp. 167-172). Article 7798264 (2016 IEEE 55th Conference on Decision and Control, CDC 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2016.7798264

@inproceedings{ab405f7d6e144b2f983b04ff29deee53,

title = "Distributed cooperative decision-making in multiarmed bandits: Frequentist and Bayesian algorithms",

abstract = "We study distributed cooperative decision-making under the explore-exploit tradeoff in the multiarmed bandit (MAB) problem. We extend state-of-the-art frequentist and Bayesian algorithms for single-agent MAB problems to cooperative distributed algorithms for multi-agent MAB problems in which agents communicate according to a fixed network graph. We rely on a running consensus algorithm for each agent's estimation of mean rewards from its own rewards and the estimated rewards of its neighbors. We prove the performance of these algorithms and show that they asymptotically recover the performance of a centralized agent. Further, we rigorously characterize the influence of the communication graph structure on the decision-making performance of the group.",

author = "Peter Landgren and Vaibhav Srivastava and Leonard, {Naomi Ehrich}",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 55th IEEE Conference on Decision and Control, CDC 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

year = "2016",

month = dec,

day = "27",

doi = "10.1109/CDC.2016.7798264",

language = "English (US)",

series = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "167--172",

booktitle = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

address = "United States",

}

Landgren, P, Srivastava, V & Leonard, NE 2016, Distributed cooperative decision-making in multiarmed bandits: Frequentist and Bayesian algorithms. in 2016 IEEE 55th Conference on Decision and Control, CDC 2016., 7798264, 2016 IEEE 55th Conference on Decision and Control, CDC 2016, Institute of Electrical and Electronics Engineers Inc., pp. 167-172, 55th IEEE Conference on Decision and Control, CDC 2016, Las Vegas, United States, 12/12/16. https://doi.org/10.1109/CDC.2016.7798264

Distributed cooperative decision-making in multiarmed bandits: Frequentist and Bayesian algorithms. / Landgren, Peter; Srivastava, Vaibhav; Leonard, Naomi Ehrich.
2016 IEEE 55th Conference on Decision and Control, CDC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 167-172 7798264 (2016 IEEE 55th Conference on Decision and Control, CDC 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Distributed cooperative decision-making in multiarmed bandits

T2 - 55th IEEE Conference on Decision and Control, CDC 2016

AU - Landgren, Peter

AU - Srivastava, Vaibhav

AU - Leonard, Naomi Ehrich

PY - 2016/12/27

Y1 - 2016/12/27

N2 - We study distributed cooperative decision-making under the explore-exploit tradeoff in the multiarmed bandit (MAB) problem. We extend state-of-the-art frequentist and Bayesian algorithms for single-agent MAB problems to cooperative distributed algorithms for multi-agent MAB problems in which agents communicate according to a fixed network graph. We rely on a running consensus algorithm for each agent's estimation of mean rewards from its own rewards and the estimated rewards of its neighbors. We prove the performance of these algorithms and show that they asymptotically recover the performance of a centralized agent. Further, we rigorously characterize the influence of the communication graph structure on the decision-making performance of the group.

AB - We study distributed cooperative decision-making under the explore-exploit tradeoff in the multiarmed bandit (MAB) problem. We extend state-of-the-art frequentist and Bayesian algorithms for single-agent MAB problems to cooperative distributed algorithms for multi-agent MAB problems in which agents communicate according to a fixed network graph. We rely on a running consensus algorithm for each agent's estimation of mean rewards from its own rewards and the estimated rewards of its neighbors. We prove the performance of these algorithms and show that they asymptotically recover the performance of a centralized agent. Further, we rigorously characterize the influence of the communication graph structure on the decision-making performance of the group.

UR - http://www.scopus.com/inward/record.url?scp=85010764309&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010764309&partnerID=8YFLogxK

U2 - 10.1109/CDC.2016.7798264

DO - 10.1109/CDC.2016.7798264

M3 - Conference contribution

AN - SCOPUS:85010764309

T3 - 2016 IEEE 55th Conference on Decision and Control, CDC 2016

SP - 167

EP - 172

BT - 2016 IEEE 55th Conference on Decision and Control, CDC 2016

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 12 December 2016 through 14 December 2016

ER -

Landgren P, Srivastava V, Leonard NE. Distributed cooperative decision-making in multiarmed bandits: Frequentist and Bayesian algorithms. In 2016 IEEE 55th Conference on Decision and Control, CDC 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 167-172. 7798264. (2016 IEEE 55th Conference on Decision and Control, CDC 2016). doi: 10.1109/CDC.2016.7798264

Distributed cooperative decision-making in multiarmed bandits: Frequentist and Bayesian algorithms

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this