Abstract
Effective coordination is crucial to solve multi-agent collaborative (MAC) problems. While centralized reinforcement learning methods can optimally solve small MAC instances, they do not scale to large problems and they fail to generalize to scenarios different from those seen during training. In this paper, we consider MAC problems with some intrinsic notion of locality (e.g., geographic proximity) such that interactions between agents and tasks are locally limited. By leveraging this property, we introduce a novel structured prediction approach to assign agents to tasks. At each step, the assignment is obtained by solving a centralized optimization problem (the inference procedure) whose objective function is parameterized by a learned scoring model. We propose different combinations of inference procedures and scoring models able to represent coordination patterns of increasing complexity. The resulting assignment policy can be efficiently learned on small problem instances and readily reused in problems with more agents and tasks (i.e., zero-shot generalization). We report experimental results on a toy search and rescue problem and on several target selection scenarios in StarCraft: Brood War, in which our model significantly outperforms strong rule-based baselines on instances with 5 times more agents and tasks than those seen during training.
Introduction
In cooperative multi-agent reinforcement learning (MARL), the "curse of dimensionality" presents a significant barrier to scalability. As the number of agents and tasks increases, the joint action space grows exponentially, often causing standard RL algorithms to fail when generalizing to larger scenarios. A model trained to coordinate a small team typically struggles when deployed in a much larger environment.
This research addresses this gap by exploiting the intrinsic locality found in many collaborative tasks, such as search-and-rescue or real-time strategy games. By focusing on local coordination and treating agent-to-task assignment as a structured prediction problem, the authors develop policies that can be trained on small groups and immediately scaled to much larger populations without further training.
Methodology: Structured Prediction for Coordination
The core innovation is a hierarchical framework that separates high-level strategic assignment from low-level tactical execution.
Task Decomposition and Inference
The system assumes agents possess fixed "low-level" policies (e.g., moving to a target). The RL model focuses exclusively on the high-level assignment: determining which agent should be paired with which task. This is achieved through a Coordination Inference Procedure (CIP), where the policy is defined as the solution to an optimization problem:
- AMAX (Greedy): Agents independently select the task with the highest individual score.
- LP (Linear Program): Introduces constraints to prevent redundancy, such as limiting the number of agents per task.
- QUAD (Quadratic Program): The most sophisticated variant, incorporating "task-task" scores. This allows the model to learn complex coordination patterns, such as spreading out to maximize coverage or concentrating fire on high-priority targets.
Scoring Models
Neural networks generate the weights for these optimization problems. The Direct Model (DM) considers only local agent-task features, making it highly portable across different scenario sizes. In contrast, the Positional Embedding Model (PEM) uses spatial context via CNNs, though it often faces greater challenges with zero-shot generalization.
Experimental Results
The approach was evaluated on two benchmarks: a Toy Search and Rescue grid-world and StarCraft: Brood War (SCBW) micromanagement scenarios.
Zero-Shot Generalization in StarCraft
In SCBW, the models were tested on target selection tasks involving different unit types (Wraiths, Marines, and Zergling-Hydralisk). A key finding was the model's ability to scale: a policy trained on 15 units significantly outperformed strong rule-based baselines when tested on 80 units—a 5x increase in scale with zero additional training.
Search and Rescue Efficiency
In the Search and Rescue benchmark, the QUAD-DM model achieved results nearing the theoretical optimal solver (topline). While simpler greedy approaches (AMAX) often resulted in "clumping"—where all agents move toward the same closest target—the LP and QUAD versions successfully avoided this redundancy by respecting the constraints embedded in the optimization layer.
Discussion and Conclusion
By embedding optimization solvers (like Linear or Quadratic Programs) directly into the policy, this framework forces agents to respect hard constraints that standard neural networks would otherwise have to learn through extensive trial and error.
While the approach demonstrates remarkable zero-shot generalization, it does introduce computational overhead; solving a Quadratic Program at every step can be demanding for real-time applications with very high agent counts. Furthermore, the model currently assumes independent tasks and fixed low-level policies. Future work may explore learning both high-level assignments and low-level execution simultaneously to better handle environments where physical collisions and movement bottlenecks are prevalent.
Summary updated