Abstract
Multi-agent reinforcement learning (MARL) in environments with large state and action spaces is often hindered by the "curse of dimensionality." We introduce Cooperative Prioritized Sweeping (CPS), a model-based algorithm designed for sample-efficient learning in factored multi-agent Markov decision processes. By leveraging a Dynamic Decision Network (DDN) to approximate the environment and a factored Q-function for value estimation, CPS isolates local updates and propagates knowledge efficiently through a priority queue of partial state-action pairs. Our results demonstrate that CPS significantly outperforms existing model-free methods like Sparse Cooperative Q-Learning (SCQL) on the SysAdmin benchmark and randomized environments, achieving near-optimal performance in systems with hundreds of agents.
The Challenge of Scale in MARL
In cooperative multi-agent systems, such as traffic management or robot coordination, the joint state and action spaces grow exponentially with the number of agents. Traditional model-free reinforcement learning often requires an impractical amount of data to converge. Conversely, exact model-based planning methods, while sample-efficient, are computationally prohibitive for large-scale systems due to the complexity of solving global optimization problems at each step. CPS bridges this gap by combining the sample efficiency of model-based learning with the computational tractability of factored representations.
Methods: Cooperative Prioritized Sweeping
The core of CPS lies in its ability to exploit the sparse interactions between agents. It represents the environment as a Dynamic Decision Network (DDN), where each agent's next state depends only on a small subset of its neighbors.
The algorithm approximates the global Q-function as a sum of local Q-components. When an agent experiences a transition, CPS calculates a local Temporal Difference (TD) error. Instead of updating the entire global state, it uses the DDN to identify the specific "parent" states that influenced the change. These partial state-action pairs are placed in a priority queue.
Between real-world interactions, CPS performs batch updates (or hallucination), where it pops high-priority partial states from the queue, simulates experiences using the learned model, and updates the Q-function. This targeted back-propagation ensures that the most critical information spreads rapidly through the network without redundant computation.
Key Results and Performance
The authors evaluated CPS against Sparse Cooperative Q-Learning (SCQL) on the SysAdmin benchmark across various topologies. In a 300-agent ring topology—featuring $2^{300}$ actions and $9^{300}$ states—CPS reached near-optimal performance in just 250 time steps, a feat impossible for standard model-free methods.
As shown in the figure above, CPS consistently achieves lower regret than SCQL across different planning horizons ($t_g$). Furthermore, the algorithm is robust to computational constraints; while larger batch sizes for simulated updates lead to faster convergence, even small batches eventually reach the same high-quality policy. This flexibility allows CPS to be tuned for different hardware limitations.
Conclusion and Future Directions
Cooperative Prioritized Sweeping demonstrates that model-based RL is not only viable but highly effective for large-scale MARL when combined with factored approximations. By focusing updates on relevant local interactions and using a priority queue for partial states, CPS overcomes the sample inefficiency of model-free methods and the computational burden of exact planning.
Future work includes integrating more sophisticated exploration strategies to maximize information gain and extending these factored techniques to deep reinforcement learning architectures, potentially allowing for arbitrary factorizations in complex neural models.
Summary updated