Neural regret-matching for distributed constraint optimization problems

• Main Authors: DENG, Yanchen, YU, Runshen, WANG, Xinrun, AN, Bo
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Agent-based and Multi-agent Systems; Coordination and Cooperation; Constraints and SAT: Constraint OptimizationConstraints and SAT; Distributed Constraints; Artificial Intelligence and Robotics; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/9142; https://ink.library.smu.edu.sg/context/sis_research/article/10145/viewcontent/Neural_Regret_Matching_pvoa.pdf
• Institution: Singapore Management University

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.