Neural Regret-Matching for Distributed Constraint Optimization Problems

Distributed constraint optimization problems (DCOPs) are a powerful model for multi-agent coordination and optimization, where information and controls are distributed among multiple agents by nature. Sampling-based algorithms are important incomplete techniques for solving medium-scale DCOPs. However, they use tables to exactly store all the information (e. g. , costs, confidence bounds) to facilitate sampling, which limits their scalability. This paper tackles the limitation by incorporating deep neural networks in solving DCOPs for the first time and presents a neural-based sampling scheme built upon regret-matching. In the algorithm, each agent trains a neural network to approximate the regret related to its local problem and performs sampling according to the estimated regret. Furthermore, to ensure exploration we propose a regret rounding scheme that rounds small regret values to positive numbers. We theoretically show the regret bound of our algorithm and extensive evaluations indicate that our algorithm can scale up to large-scale DCOPs and significantly outperform the state-of-the-art methods.

Authors

• Yanchen Deng
• Runsheng Yu Hong Kong University of Science and Technology, Hong Kong, China
• Xinrun Wang Nanyang Technological University
• Bo An Nanyang Technological University

Keywords

• Agent-based and Multi-agent Systems: Coordination and Cooperation
• Constraints and SAT: Constraint Optimization
• Constraints and SAT: Distributed Constraints