# Near-Optimal Multi-Agent Learning for Safe Coverage Control

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 75 references that are in the map.
- First posted on arXiv 12 Oct 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [A General Safety Framework for Learning-Based Control in Uncertain Robotic Systems](https://mlsanity.com/paper/1705.01292/) (2017)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [AI Safety Gridworlds](https://mlsanity.com/paper/1711.09883/) (2017)
- [Stagewise Safe Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1806.07555/) (2018)
- [Safe Exploration in Finite Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/1606.04753/) (2016)
- [Safe Reinforcement Learning via Curriculum Induction](https://mlsanity.com/paper/2006.12136/) (2020)
- [Cooperative Exploration for Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/2107.11444/) (2021)
- [Safe Exploration for Interactive Machine Learning](https://mlsanity.com/paper/1910.13726/) (2019)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Distributionally Robust Chance Constrained Data-enabled Predictive Control](https://mlsanity.com/paper/2006.01702/) (2020)
- [Multi-Agent Safe Planning with Gaussian Processes](https://mlsanity.com/paper/2008.04452/) (2020)
- [Coverage Control in Multi-Robot Systems via Graph Neural Networks](https://mlsanity.com/paper/2109.15278/) (2021)
- [Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization](https://mlsanity.com/paper/1511.07211/) (2015)
- [Experimental Design for Linear Functionals in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2205.13627/) (2022)
- [Competitive Policy Optimization](https://mlsanity.com/paper/2006.10611/) (2020)
- [Multi-agents adaptive estimation and coverage control using Gaussian regression](https://mlsanity.com/paper/1407.5807/) (2014)
- [Sensing Cox Processes via Posterior Sampling and Positive Bases](https://mlsanity.com/paper/2110.11181/) (2021)

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

- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [Safe Guaranteed Exploration for Non-linear Systems](https://mlsanity.com/paper/2402.06562/) (2024)
- [Performance-driven Constrained Optimal Auto-Tuner for MPC](https://mlsanity.com/paper/2503.07127/) (2025)
- [Safe Exploration via Policy Priors](https://mlsanity.com/paper/2601.19612/) (2026)
- [Finite-Sample-Based Reachability for Safe Control with Gaussian Process Dynamics](https://mlsanity.com/paper/2505.07594/) (2025)
- [Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis](https://mlsanity.com/paper/2401.10383/) (2024)
- [Safe and Near-Optimal Control with Online Dynamics Learning](https://mlsanity.com/paper/2509.16650/) (2025)
- [Information-Theoretic Safe Bayesian Optimization](https://mlsanity.com/paper/2402.15347/) (2024)
- [Scalable Submodular Policy Optimization via Pruned Submodularity Graph](https://mlsanity.com/paper/2507.13834/) (2025)
- [Towards safe control parameter tuning in distributed multi-agent systems](https://mlsanity.com/paper/2508.13608/) (2025)

## Abstract (arXiv)

In multi-agent coverage control problems, agents navigate their environment to reach locations that maximize the coverage of some density. In practice, the density is rarely known textita priori, further complicating the original NP-hard problem. Moreover, in many applications, agents cannot visit arbitrary locations due to textita priori unknown safety constraints. In this paper, we aim to efficiently learn the density to approximately solve the coverage problem while preserving the agents' safety. We first propose a conditionally linear submodular coverage function that facilitates theoretical analysis. Utilizing this structure, we develop MacOpt, a novel algorithm that efficiently trades off the exploration-exploitation dilemma due to partial observability, and show that it achieves sublinear regret. Next, we extend results on single-agent safe exploration to our multi-agent setting and propose SafeMac for safe coverage and exploration. We analyze SafeMac and give first of its kind results: near optimal coverage in finite time while provably guaranteeing safety. We extensively evaluate our algorithms on synthetic and real problems, including a bio-diversity monitoring task under safety constraints, where SafeMac outperforms competing methods.