# Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environments

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 43 references that are in the map.
- First posted on arXiv 22 May 2023.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Efficient Informative Sensing using Multiple Robots](https://mlsanity.com/paper/1401.3462/) (2014)
- [Distributed Submodular Maximization with Limited Information](https://mlsanity.com/paper/1706.04082/) (2017)
- [Optimal Algorithms for Submodular Maximization with Distributed Constraints](https://mlsanity.com/paper/1909.13676/) (2019)
- [Resilient Active Information Acquisition with Teams of Robots](https://mlsanity.com/paper/2103.02733/) (2021)
- [Distributed Strategy Selection: A Submodular Set Function Maximization Approach](https://mlsanity.com/paper/2107.14371/) (2021)
- [Scalable Operator Allocation for Multi-Robot Assistance: A Restless Bandit Approach](https://mlsanity.com/paper/2111.06437/) (2021)
- [Distributed Resilient Submodular Action Selection in Adversarial Environments](https://mlsanity.com/paper/2105.07305/) (2021)
- [The Impact of Information in Greedy Submodular Maximization](https://mlsanity.com/paper/1807.10639/) (2018)
- [Execution Order Matters in Greedy Algorithms with Limited Information](https://mlsanity.com/paper/2111.09154/) (2021)
- [Scalable Distributed Planning for Multi-Robot, Multi-Target Tracking](https://mlsanity.com/paper/2107.08550/) (2021)
- [Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making](https://mlsanity.com/paper/2204.07520/) (2022)
- [Active Inference for Autonomous Decision-Making with Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2209.09185/) (2022)
- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [An Upper Confidence Bound for Simultaneous Exploration and Exploitation in Heterogeneous Multi-Robot Systems](https://mlsanity.com/paper/2105.06118/) (2021)

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

- [Leveraging Untrustworthy Commands for Multi-Robot Coordination in Unpredictable Environments: A Bandit Submodular Maximization Approach](https://mlsanity.com/paper/2309.16161/) (2023)
- [Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design](https://mlsanity.com/paper/2409.01411/) (2024)
- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)
- [Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach](https://mlsanity.com/paper/2603.27803/) (2026)
- [SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search](https://mlsanity.com/paper/2606.01325/) (2026)
- [Who to Trust in Multi-Robot Systems: Joint Robot and Object Hypothesis Trust Inference via Neural-Symbolic Cross-Validation](https://mlsanity.com/paper/2610.14530/) (2026)

## Abstract (arXiv)

We study the problem of multi-agent coordination in unpredictable and partially observable environments, that is, environments whose future evolution is unknown a priori and that can only be partially observed. We are motivated by the future of autonomy that involves multiple robots coordinating actions in dynamic, unstructured, and partially observable environments to complete complex tasks such as target tracking, environmental mapping, and area monitoring. Such tasks are often modeled as submodular maximization coordination problems due to the information overlap among the robots. We introduce the first submodular coordination algorithm with bandit feedback and bounded tracking regret -- bandit feedback is the robots' ability to compute in hindsight only the effect of their chosen actions, instead of all the alternative actions that they could have chosen instead, due to the partial observability; and tracking regret is the algorithm's suboptimality with respect to the optimal time-varying actions that fully know the future a priori. The bound gracefully degrades with the environments' capacity to change adversarially, quantifying how often the robots should re-select actions to learn to coordinate as if they fully knew the future a priori. The algorithm generalizes the seminal Sequential Greedy algorithm by Fisher et al. to the bandit setting, by leveraging submodularity and algorithms for the problem of tracking the best action. We validate our algorithm in simulated scenarios of multi-target tracking.