# Cooperative Multi-Agent Constrained Stochastic Linear Bandits

arXiv: https://arxiv.org/abs/2410.17382 · HTML: https://mlsanity.com/paper/2410.17382/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 21 references that are in the map.
- First posted on arXiv 22 Oct 2024.

## Builds on (most cited first, 9 of 9)

- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Safe Linear Thompson Sampling with Side Information](https://mlsanity.com/paper/1911.02156/) (2019)
- [A Dynamic Observation Strategy for Multi-agent Multi-armed Bandit Problem](https://mlsanity.com/paper/2004.03793/) (2020)
- [Convex Methods for Constrained Linear Bandits](https://mlsanity.com/paper/2311.04338/) (2023)
- [Collaborative Multi-agent Stochastic Linear Bandits](https://mlsanity.com/paper/2205.06331/) (2022)

## Built on by (most cited first, 2 of 2)

- [Multi-Agent Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2510.00602/) (2025)
- [On-Policy Distillation of Language Models for Autonomous Vehicle Motion Planning](https://mlsanity.com/paper/2604.07944/) (2026)

## Abstract (arXiv)

In this study, we explore a collaborative multi-agent stochastic linear bandit setting involving a network of N agents that communicate locally to minimize their collective regret while keeping their expected cost under a specified threshold τ. Each agent encounters a distinct linear bandit problem characterized by its own reward and cost parameters, i.e., local parameters. The goal of the agents is to determine the best overall action corresponding to the average of these parameters, or so-called global parameters. In each round, an agent is randomly chosen to select an action based on its current knowledge of the system. This chosen action is then executed by all agents, then they observe their individual rewards and costs. We propose a safe distributed upper confidence bound algorithm, so called textitMA-OPLB, and establish a high probability bound on its T-round regret. MA-OPLB utilizes an accelerated consensus method, where agents can compute an estimate of the average rewards and costs across the network by communicating the proper information with their neighbors. We show that our regret bound is of order  Oleft(fracdτ-c0fraclog(NT)2√N√fracTlog(1/|λ2|)right), where λ2 is the second largest (in absolute value) eigenvalue of the communication matrix, and τ-c0 is the known cost gap of a feasible action. We also experimentally show the performance of our proposed algorithm in different network structures.