TY - GEN

T1 - A Dynamic Observation Strategy for Multi-agent Multi-armed Bandit Problem

AU - Madhushani, Udari

AU - Leonard, Naomi Ehrich

N1 - Funding Information:
This research has been supported in part by ARO grant W911NF-18-1-0325 and ONR grant N00014-19-1-2556. Department of Mechanical and Aerospace Engineering, Princeton University, NJ 08544, USA.

PY - 2020/5

Y1 - 2020/5

N2 - We define and analyze a multi-agent multi-armed bandit problem in which decision-making agents can observe the choices and rewards of their neighbors under a linear observation cost. Neighbors are defined by a network graph that encodes the inherent observation constraints of the system. We define a cost associated with observations such that at every instance an agent makes an observation it receives a constant observation regret. We design a sampling algorithm and an observation protocol for each agent to maximize its own expected cumulative reward through minimizing expected cumulative sampling regret and expected cumulative observation regret. For our proposed protocol, we prove that total cumulative regret is logarithmically bounded. We verify the accuracy of analytical bounds using numerical simulations.

AB - We define and analyze a multi-agent multi-armed bandit problem in which decision-making agents can observe the choices and rewards of their neighbors under a linear observation cost. Neighbors are defined by a network graph that encodes the inherent observation constraints of the system. We define a cost associated with observations such that at every instance an agent makes an observation it receives a constant observation regret. We design a sampling algorithm and an observation protocol for each agent to maximize its own expected cumulative reward through minimizing expected cumulative sampling regret and expected cumulative observation regret. For our proposed protocol, we prove that total cumulative regret is logarithmically bounded. We verify the accuracy of analytical bounds using numerical simulations.

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

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

M3 - Conference contribution

AN - SCOPUS:85090123440

T3 - European Control Conference 2020, ECC 2020

SP - 1677

EP - 1682

BT - European Control Conference 2020, ECC 2020

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 18th European Control Conference, ECC 2020

Y2 - 12 May 2020 through 15 May 2020

ER -