# Multi-Agent Stage-wise Conservative Linear Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 1 Oct 2025.

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

- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (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)
- [Stage-wise Conservative Linear Bandits](https://mlsanity.com/paper/2010.00081/) (2020)
- [Safe Linear Stochastic Bandits](https://mlsanity.com/paper/1911.09501/) (2019)
- [Multi-scale exploration of convex functions and bandit convex optimization](https://mlsanity.com/paper/1507.06580/) (2015)
- [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)
- [Cooperative Multi-Agent Constrained Stochastic Linear Bandits](https://mlsanity.com/paper/2410.17382/) (2024)

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

- [On-Policy Distillation of Language Models for Autonomous Vehicle Motion Planning](https://mlsanity.com/paper/2604.07944/) (2026)

## Abstract (arXiv)

In many real-world applications such as recommendation systems, multiple learning agents must balance exploration and exploitation while maintaining safety guarantees to avoid catastrophic failures. We study the stochastic linear bandit problem in a multi-agent networked setting where agents must satisfy stage-wise conservative constraints. A network of N agents collaboratively maximizes cumulative reward while ensuring that the expected reward at every round is no less than (1-α) times that of a baseline policy. Each agent observes local rewards with unknown parameters, but the network optimizes for the global parameter (average of local parameters). Agents communicate only with immediate neighbors, and each communication round incurs additional regret. We propose MA-SCLUCB (Multi-Agent Stage-wise Conservative Linear UCB), an episodic algorithm alternating between action selection and consensus-building phases. We prove that MA-SCLUCB achieves regret tildeOleft(fracd√N√T·fraclog(NT)√log(1/|λ2|)right) with high probability, where d is the dimension, T is the horizon, and |λ2| is the network's second largest eigenvalue magnitude. Our analysis shows: (i) collaboration yields frac1√N improvement despite local communication, (ii) communication overhead grows only logarithmically for well-connected networks, and (iii) stage-wise safety adds only lower-order regret. Thus, distributed learning with safety guarantees achieves near-optimal performance in reasonably connected networks.