Decentralized Multi-Agent Linear Bandits with Safety Constraints

We study decentralized stochastic linear bandits, where a network of N agents acts cooperatively to efficiently solve a linear bandit-optimization problem over a d-dimensional space. For this problem, we propose DLUCB: a fully decentralized algorithm that minimizes the cumulative regret over the entire network. At each round of the algorithm each agent chooses its actions following an upper confidence bound (UCB) strategy and agents share information with their immediate neighbors through a carefully designed consensus procedure that repeats over cycles. Our analysis adjusts the duration of these communication cycles ensuring near-optimal regret performance O(d log N T √ N T ) at a communication rate of O(dN 2 ) per round. The structure of the network affects the regret performance via a small additive term -coined the regret of delay -that depends on the spectral gap of the underlying graph. Notably, our results apply to arbitrary network topologies without a requirement for a dedicated agent acting as a server. In consideration of situations with high communication cost, we propose RC-DLUCB: a modification of DLUCB with rare communication among agents. The new algorithm trades off regret performance for a significantly reduced total communication cost of O(d 3 N 2.5 ) over all T rounds. Finally, we show that our ideas extend naturally to the emerging, albeit more challenging, setting of safe bandits. For the recently studied problem of linear bandits with unknown linear safety constraints, we propose the first safe decentralized algorithm. Our study contributes towards applying bandit techniques in safety-critical distributed systems that repeatedly deal with unknown stochastic environments. We present numerical simulations for various network topologies that corroborate our theoretical findings. Contributions DLUCB. We propose a fully decentralized linear bandit algorithm (DLUCB), at each round of which, the agents simultaneously share information among each other and pick their next actions. We prove a regret bound that captures both the degree of selected actions' optimality and the inevitable delay in informationsharing due to the network structure. See Section 2.1 and 2.2. Compared to existing distributed LB algorithms, ours can be implemented (and remains valid) for any arbitrary (connected) network without requiring a peer-to-peer network structure or a master node. See Section 2.4. RC-DLUCB. We propose a fully decentralized algorithm with rare communication (RC-DLUCB) to reduce the communication cost (total number of values communicated during the run of algorithm) for applications that are sensitive to high communication cost. See Section 2.3 Safe-DLUCB. We present and analyze the first fully decentralized algorithm for safe LBs with linear