# Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2025.

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

- [Information-Theoretic Privacy Control for Sequential Multi-Agent LLM Systems](https://mlsanity.com/paper/2603.05520/) (2026)
- [FairGC: Fairness-aware Graph Condensation](https://mlsanity.com/paper/2603.28321/) (2026)

## Abstract (arXiv)

In this paper, we present two effective policy learning algorithms for multi-agent online coordination(MA-OC) problem. The first one, textttMA-SPL, not only can achieve the optimal (1-fracce)-approximation guarantee for the MA-OC problem with submodular objectives but also can handle the unexplored α-weakly DR-submodular and (γ,β)-weakly submodular scenarios, where c is the curvature of the investigated submodular functions, α denotes the diminishing-return(DR) ratio and the tuple (γ,β) represents the submodularity ratios. Subsequently, in order to reduce the reliance on the unknown parameters α,γ,β inherent in the textttMA-SPL algorithm, we further introduce the second online algorithm named textttMA-MPL. This textttMA-MPL algorithm is entirely parameter-free and simultaneously can maintain the same approximation ratio as the first textttMA-SPL algorithm. The core of our textttMA-SPL and textttMA-MPL algorithms is a novel continuous-relaxation technique termed as policy-based continuous extension. Compared with the well-established multi-linear extension, a notable advantage of this new policy-based continuous extension is its ability to provide a lossless rounding scheme for any set function, thereby enabling us to tackle the challenging weakly submodular objectives. Finally, extensive simulations are conducted to validate the effectiveness of our proposed algorithms.