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

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper presents two online algorithms—MA-SPL and MA-MPL—for the Multi-Agent Online Coordination (MA-OC) problem, extending prior submodular-only guarantees to weakly submodular objectives. The key innovation is a policy-based continuous extension, a continuous relaxation that provides a lossless rounding scheme for any set function, unlike the classical multi-linear extension which requires strict submodularity.

Problem¶

Existing algorithms for MA-OC either (1) only handle strictly submodular utility functions, achieving a sub-optimal (1−e^{−c})/c-approximation rather than the tight (1−e^c) bound, or (2) fail entirely on near-submodular (α-weakly DR-submodular, (γ,β)-weakly submodular) objectives that arise in real-world tasks like UAV trajectory planning under a Kalman filter framework. No prior work extended online weakly submodular maximization—rooted in discrete local search—to the multi-agent online setting.

Method¶

The core technique is the policy-based continuous extension F_t(π_1,...,π_n): each agent i maintains a mixed policy π_i over its action set V_i, and the extension is defined as the expected set function value over independent per-agent action draws. This construction guarantees a lossless rounding scheme for any set function (not just submodular ones), since the policy simplex domain respects the partition constraint by design.

For optimization, the paper designs surrogate functions F_t^s whose gradients are weighted averages of ∇F_t(z∗x) with carefully chosen weight functions w(z): - Submodular (curvature c): w(z) = e^{z−1}, plus a linear correction G_t based on minimum marginal gains → achieves (1−e^c)-approximation at stationary points. - α-weakly DR-submodular: w(z) = e^{α(z−1)} → achieves (1−e^{−α}). - (γ,β)-weakly submodular: w(z) = e^{ϕ(γ,β)(z−1)} where ϕ(γ,β) = β(1−γ)+γ² → achieves γ²(1−e^{−ϕ})/ϕ.

MA-SPL (Algorithm 1) combines this surrogate gradient with a consensus update (doubly stochastic weight matrix W) and projected gradient ascent. Each agent samples actions, exchanges policy vectors with neighbors, estimates surrogate gradients via one oracle query per step, and projects onto the simplex.

MA-MPL (Algorithm 2, in Appendix B) eliminates the need for parameters α, γ, β via a novel inequality relating F_t to the original set objective, making it fully parameter-free. It uses projection-free updates and runs in O(T^{3/2}) communications/O(κT^{5/2}) oracle queries versus O(T) for MA-SPL.

Key Contributions¶

Policy-based continuous extension: a new continuous relaxation with a lossless rounding scheme for arbitrary set functions; differentiability, monotonicity, and weak DR-submodularity properties fully characterized.
Surrogate function design: three weight functions that elevate stationary-point approximation from suboptimal 1/(1+c) to tight (1−e^c) for each objective class.
MA-SPL: first online MA-OC algorithm achieving the optimal (1−e^c) for submodular objectives and extending to previously unaddressed weakly submodular settings, with dynamic regret O(√(P_T T/(1−τ))).
MA-MPL: parameter-free variant with identical approximation ratios, regret O(d(G)√(P_T T)), requiring no knowledge of curvature or submodularity ratios.

Results¶

Submodular (facility-location, multi-target tracking): MA-SPL and MA-MPL significantly exceed state-of-the-art MA-OSMA and MA-OSEA [126] in average utility across all target-mix ratios (R:A:P = 8:1:1, 6:3:1, 4:5:1) on both complete and Erdos-Renyi random graphs.
Weakly submodular (Bayesian A-optimal, target tracking): MA-SPL (best α=0.1 via grid search) and MA-MPL substantially outperform the random baseline; MA-MPL matches MA-SPL performance without parameter tuning.
Theoretical comparison (Table 1): MA-SPL is the only algorithm that is both parameter-free (for submodular case) and achieves (1−e^c) approximation; prior OSEA achieves only (1−e^{−c})/c.

Limitations¶

MA-SPL requires prior knowledge of α, γ, β for weakly submodular settings, which demands exponential computation to compute exactly.
MA-MPL is parameter-free but incurs higher complexity: O(T^{3/2}) communications and O(κT^{5/2}) oracle queries vs. O(T) for MA-SPL.
MA-SPL requires projection onto the simplex at each step (MA-MPL is projection-free, but at greater communication cost).
Experiments are simulation-only (UAV target tracking); no real-hardware or LLM fine-tuning validation.
Step size η_t depends on the unknown deviation P_T of the maximizer sequence, requiring adaptive tuning in practice.

Relevance to Agentic AI / LLM Agents¶

This paper directly addresses multi-agent collaborative data selection for LLM fine-tuning—explicitly framed as a MA-OC problem—providing the first online algorithms with provable guarantees for objectives beyond strict submodularity. For researchers building agentic systems where agents must coordinate action selection in dynamic environments (e.g., tool use, resource allocation, distributed inference), the policy-based continuous extension offers a principled, communication-efficient framework. The parameter-free MA-MPL is particularly relevant to deployed LLM agent systems where utility function parameters are unknown. More broadly, this work establishes a theoretical foundation connecting combinatorial multi-agent coordination to the gradient-based policy optimization paradigm underlying modern LLM agents.