# Capacity-Aware Planning and Scheduling in Budget-Constrained Multi-Agent MDPs: A Meta-RL Approach

arXiv: https://arxiv.org/abs/2410.21249 · HTML: https://mlsanity.com/paper/2410.21249/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 47 references that are in the map.
- First posted on arXiv 28 Oct 2024.

## Builds on (most cited first, 10 of 10)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [RL2: Fast Reinforcement Learning via Slow Reinforcement Learning](https://mlsanity.com/paper/1611.02779/) (2016)
- [State Representation Learning for Control: An Overview](https://mlsanity.com/paper/1802.04181/) (2018)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)
- [Qualitative Controller Synthesis for Consumption Markov Decision Processes](https://mlsanity.com/paper/2005.07227/) (2020)
- [Constrained Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/2006.11984/) (2020)
- [Welfare Maximization Algorithm for Solving Budget-Constrained Multi-Component POMDPs](https://mlsanity.com/paper/2303.10302/) (2023)
- [Solving Truly Massive Budgeted Monotonic POMDPs with Oracle-Guided Meta-Reinforcement Learning](https://mlsanity.com/paper/2408.07192/) (2024)

## Abstract (arXiv)

We study capacity- and budget-constrained multi-agent MDPs (CB-MA-MDPs), a class that captures many maintenance and scheduling tasks in which each agent can irreversibly fail and a planner must decide (i) when to apply a restorative action and (ii) which subset of agents to treat in parallel. The global budget limits the total number of restorations, while the capacity constraint bounds the number of simultaneous actions, turning na"ive dynamic programming into a combinatorial search that scales exponentially with the number of agents. We propose a two-stage solution that remains tractable for large systems. First, a Linear Sum Assignment Problem (LSAP)-based grouping partitions the agents into r disjoint sets (r = capacity) that maximise diversity in expected time-to-failure, allocating budget to each set proportionally. Second, a meta-trained PPO policy solves each sub-MDP, leveraging transfer across groups to converge rapidly. To validate our approach, we apply it to the problem of scheduling repairs for a large team of industrial robots, constrained by a limited number of repair technicians and a total repair budget. Our results demonstrate that the proposed method outperforms baseline approaches in terms of maximizing the average uptime of the robot team, particularly for large team sizes. Lastly, we confirm the scalability of our approach through a computational complexity analysis across varying numbers of robots and repair technicians.