DiffPtr: Diffusion Pointer Networks for Multi-Agent Combinatorial Optimization

Combinatorial Optimization problems in Multi-Agent systems are particularly challenging due to the combination of NP-hardness, agent coordination, and exponentially large joint action space. Existing Constructive (or AutoRegressive) methods such as PARCO typically rely on pointers to deterministically model the joint action distribution, from which multiple trajectories are sampled to explore the solution space. Although these methods have achieved significant progress, they still suffer from issues such as limited generation diversity and poor generalization capability. In this work, we propose the Diffusion Pointer Networks (DiffPtr), which incorporates diffusion models into the pointer generation process, to capture the diverse multimodal distributions over multi-agent joint actions and trajectories. DiffPtr introduces an independence assumption between arbitrary agent–action pairs and defines a discrete diffusion process based on binary action variables, consisting of a forward noising process and a state-conditioned reverse denoising process. By iteratively generating diffusion pointers under different noise levels, DiffPtr progressively refines the joint actions, thereby enhancing inter-agent coordination, promoting solution diversity, and improving robustness under out-of-distribution generalization. Experimental results show that DiffPtr outperforms existing methods in both solution quality and generalization, highlighting the potential of diffusion-based policies for complex Multi-agent Combinatorial Optimization problems.