Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems
Assignment problems are a classic combinatorial optimization problem in which a group of agents must be assigned to a group of tasks such that maximum utility is achieved while satisfying assignment constraints. Given the utility of each agent completing each task, polynomial-time algorithms exist to solve a single assignment problem in its simplest form. However, in many modern-day applications such as satellite constellations, power grids, and mobile robot scheduling, assignment problems unfold over time, with the utility for a given assignment depending heavily on the state of the system. We apply multi-agent reinforcement learning to this problem, learning the value of assignments by bootstrapping from a known polynomial-time greedy solver and then learning from further experience. We then choose assignments using a distributed optimal assignment mechanism rather than by selecting them directly. We demonstrate that this algorithm is theoretically justified and avoids pitfalls experienced by other RL algorithms in this setting. Finally, we show that our algorithm significantly outperforms other methods in the literature, even while scaling to realistic scenarios with hundreds of agents and tasks.
Code (1)
Tasks
Combinatorial OptimizationMulti-agent Reinforcement Learningreinforcement-learningReinforcement LearningSchedulingSimilar Papers 제목 키워드 기반
Cooperative Multi-Agent Reinforcement Learning with Sequential Credit Assignment
Centralized training with decentralized execution is a standard paradigm for cooperative multi-agent reinforcement learning (MARL), with credit assignment being a major challenge. In this paper, we propose a cooperative …
counterfactualMulti-agent Reinforcement Learningreinforcement-learningReinforcement Learning+3Concurrent Meta Reinforcement Learning
State-of-the-art meta reinforcement learning algorithms typically assume the setting of a single agent interacting with its environment in a sequential manner. A negative side-effect of this sequential execution paradigm…
Efficient ExplorationMeta-LearningMeta Reinforcement LearningMulti-agent Reinforcement Learning+3SrSv: Integrating Sequential Rollouts with Sequential Value Estimation for Multi-agent Reinforcement Learning
Although multi-agent reinforcement learning (MARL) has shown its success across diverse domains, extending its application to large-scale real-world systems still faces significant challenges. Primarily, the high complex…
MuJoCoMulti-agent Reinforcement LearningStarcraftAgentOPSD: Recursive Self-Distillation for Agentic Reinforcement Learning
Reinforcement learning (RL) with verifiable rewards constructs trajectory-level advantage estimates, yet it often fails to credit the few pivotal decisions that determine outcomes in long-horizon, multi-turn agentic task…
Reinforcement LearningShapley Value Based Multi-Agent Reinforcement Learning: Theory, Method and Its Application to Energy Network
Multi-agent reinforcement learning is an area of rapid advancement in artificial intelligence and machine learning. One of the important questions to be answered is how to conduct credit assignment in a multi-agent syste…
Learning TheoryMulti-agent Reinforcement Learningreinforcement-learningReinforcement Learning