Successor Features Based Multi-Agent RL for Event-Based Decentralized MDPs.

Tarun Gupta, Akshat Kumar, Praveen ParuchuriAAAI 2019 · OpenReview

Abstract

Decentralized Markov Decision Processes (Dec-MDPs) provide a rigorous framework for collaborative multi-agent sequential decision-making under uncertainty. However, their computational complexity limits their practical impact. To address this, we focus on a class of Dec-MDPs consisting of independent collaborating agents tied together through a global reward function that depends upon their entire histories of states and actions to accomplish joint tasks. To overcome the scalability barrier, we propose a new actor-critic based Reinforcement Learning (RL) approach for event-based Dec-MDPs using successor features (SF), a value function representation that decouples environment dynamics from rewards. We present Dec-ESR (Decentralized Event-based Successor Representation), which generalizes learning for event-based Dec-MDPs within an end-to-end deep RL framework. We demonstrate that Dec-ESR allows for the useful transfer of information across related tasks, bootstrapping learning for faster convergence. Validation on a large multi-agent coverage problem modeling urban subway network coordination shows that Dec-ESR achieves superior solution quality compared to previous state-of-the-art approaches.

The Challenge of Event-Based Dec-MDPs

In many real-world decentralized systems—such as coordinating autonomous vehicle fleets or managing urban infrastructure—agents operate independently but are evaluated based on collective "events." For instance, in a subway network, a joint reward might be triggered only if at least one agent inspects a specific station within a certain time window.

Standard Dec-MDPs are notoriously difficult to solve, categorized as NEXP-hard. The complexity intensifies when rewards are "event-based," meaning they depend on the entire history of actions rather than just the current state. Traditional RL methods struggle here; they either fail to scale or rely on Monte-Carlo estimates that suffer from high variance and an inability to "bootstrap" (learning from estimated future values). Furthermore, these models lack flexibility; if task priorities shift slightly, the agents typically must relearn their entire policies from scratch.

The Dec-ESR Framework

To address these limitations, we introduce Dec-ESR. The framework's core innovation lies in two primary areas: Markovian Event Modeling and the application of Successor Features (SF).

1. Markovian Event Modeling

We transform non-Markovian event probabilities into a recursive form that adheres to the Markov property. This critical step enables the use of Temporal Difference (TD) learning. By employing an "event critic," the model can update policies at every timestep based on immediate feedback, rather than waiting for the end of an episode. This significantly reduces the variance that typically plagues standard policy gradient methods in history-dependent settings.

2. Successor Features (SF)

We adapt Successor Features to the multi-agent event-based setting. SF decomposes the value function into two distinct components:

  • The Successor Map (Dynamics): Represents the expected future occupancy of features.
  • The Reward Weight: Maps those features to scalar rewards.

In Dec-ESR, we extend this to Event Successor Features, which represent the probability of an event occurring given the current state and action. This decoupling allows agents to learn the "physics" of their environment (how to move and what events occur) independently of the specific reward weights assigned to those events.

The end-to-end deep RL architecture of Dec-ESR, featuring state encoders, decoders, reward predictors, and successor feature networks.

Experimental Evaluation

We evaluated Dec-ESR on a Multi-Agent Coverage Problem modeled after a real-world urban subway (MRT) network. The task requires agents to coordinate their movements to cover stations and satisfy event-based rewards. We tested across three difficulty tiers—Easy, Medium, and Hard—varying the number of lines (3 to 5), stations (50 to 140), and shared interchange stations (5 to 15).

Key Results and Performance

Dec-ESR significantly outperformed the previous state-of-the-art method, GKP. As shown in the performance plots, the performance gap widens as the environment complexity increases:

  • Easy Settings: 28% improvement over GKP.
  • Medium Settings: 42.8% improvement.
  • Hard Settings: Nearly 50% improvement.
Average global reward across Easy, Medium, and Hard settings. Dec-ESR consistently outperforms GKP and the 'No Event Critic' (NEC) ablation.

An ablation study using a "No Event Critic" (NEC) version of the model confirmed that event-based bootstrapping is essential for high-quality coordination. Without the critic, the model's performance dropped significantly across all settings.

Transfer Learning and Scalability

One of the most powerful features of Dec-ESR is its ability to handle Zero-Start Transfer. Because the successor features capture the environment's layout and transition dynamics, when joint rewards change (e.g., a specific station's priority is increased), the agent only needs to relearn the reward weights $w$, not the entire navigation policy. In our tests, the transfer-enabled model (Dec-ESR-TRF) converged in fewer than 700 iterations, whereas the model learning from scratch required over 3,000 iterations.

Finally, we tested scalability on a large-scale synthetic map with 30 agents and 30 lines. Dec-ESR maintained a high performance gain (up to 52% over GKP), demonstrating its viability for complex, real-world urban systems.

Limitations and Future Work

While Dec-ESR shows great promise, it currently assumes transition independence, meaning agents do not physically obstruct one another. Future work could extend this to environments where physical crowding or collisions are factors. Additionally, the current model relies on centralized training, which may present a bottleneck for privacy-sensitive or extremely large-scale deployments where data cannot be easily aggregated.

Summary updated

Abstract

Decentralized MDPs (Dec-MDPs) provide a rigorous framework for collaborative multi-agent sequential decisionmaking under uncertainty. However, their computational complexity limits the practical impact. To address this, we focus on a class of Dec-MDPs consisting of independent collaborating agents that are tied together through a global reward function that depends upon their entire histories of states and actions to accomplish joint tasks. To overcome scalability barrier, our main contributions are: (a) We propose a new actor-critic based Reinforcement Learning (RL) approach for event-based Dec-MDPs using successor features (SF) which is a value function representation that decouples the dynamics of the environment from the rewards; (b) We then present Dec-ESR (Decentralized Event based Successor Representation) which generalizes learning for event-based Dec-MDPs using SF within an end-to-end deep RL framework; (c) We also show that Dec-ESR allows useful transfer of information on related but different tasks, hence bootstraps the learning for faster convergence on new tasks; (d) For validation purposes, we test our approach on a large multi-agent coverage problem which models schedule coordination of agents in a real urban subway network and achieves better quality solutions than previous best approaches.
BibTeX
@inproceedings{gupta2019successor,
  author = {Tarun Gupta and Akshat Kumar and Praveen Paruchuri},
  title = {{Successor Features Based Multi-Agent RL for Event-Based Decentralized MDPs.}},
  booktitle = {AAAI},
  year = {2019},
  url = {https://openreview.net/forum?id=Hjlx-I7GeupH},
}
Figure