Decentralized Conflict Resolution for Multi-Agent Reinforcement Learning Through Shared Scheduling Protocols

Decentralized multi-agent reinforcement learning (MARL) is an inherently difficult problem because agents can have individual, unique objectives and no direct incentive to cooperate. Conflicts often arise over bottlenecks in the environment, such as a shared key or an intersection, where multiple agents need to access a single resource. To resolve these conflicts, we propose the use of a shared scheduling protocol. A scheduling protocol coordinates agent behavior such that one agent is allowed to greedily use the resource while the others are required to wait. In particular, we are interested in decentralized scheduling protocols that can be implemented independently by each agent without a centralized controller. We present three protocols and prove that they resolve conflicts when obeyed by all agents. In training, agents learn to obey the protocol as violations incur a penalty. Experimental results show that scheduling protocols increase the performance of multi-agent training fivefold compared to baseline decentralized MARL.