Planning and Learning for Decentralized MDPs with Event Driven Rewards

Tarun Gupta, Akshat Kumar, Praveen ParuchuriWorkshops @ AAAI 2018 · OpenReview

Abstract

Decentralized (PO)MDPs provide a rigorous framework for sequential multiagent decision making under uncertainty. However, their high computational complexity limits the practical impact. To address scalability and real-world impact, we focus on settings where a large number of agents primarily interact through complex joint-rewards that depend on their entire histories of states and actions. Such history-based rewards encapsulate the notion of events or tasks such that the team reward is given only when the joint-task is completed. Algorithmically, we contribute — 1) A nonlinear programming (NLP) formulation for such event-based planning model; 2) A probabilistic inference based approach that scales much better than NLP solvers for a large number of agents; 3) A policy gradient based multiagent reinforcement learning approach that scales well even for exponential state-spaces.

Introduction

In multi-agent systems, agents often need to collaborate to achieve high-level goals, such as ensuring a subway station is inspected at regular intervals. Standard models like Decentralized Markov Decision Processes (Dec-MDPs) are notoriously difficult to solve (NEXP-Hard) because the optimal action for one agent depends on the actions of all others. Most existing solvers struggle with scalability and complex reward structures. Modeling "event-based" rewards—those dependent on a sequence of actions over time—typically requires adding "memory bits" to the state space, which causes an exponential explosion in complexity. This research bridges this gap by creating algorithms that handle event-driven rewards directly and efficiently, allowing for large-scale coordination without state-space bloat.

Methodology

The authors propose a three-tiered algorithmic approach to address these challenges:

  • Nonlinear Programming (NLP) Formulation: The planning problem is framed as a compact NLP. Unlike previous methods, this formulation handles event-based rewards in the objective function itself, avoiding the need to expand the state space with extra memory variables.
  • Inference-based Approach (EM): To improve on the speed of general NLP solvers, the planning problem is translated into a Maximum Likelihood Estimation (MLE) problem within a graphical model. By using the Expectation-Maximization (EM) algorithm, the system effectively decouples the agents. In each iteration, every agent solves its own small convex optimization problem, making the system highly scalable.
  • Multi-agent Reinforcement Learning (MARL): For environments where the state space is too massive for tabular methods (like the Singapore MRT scenario), a policy gradient RL approach is developed. Deep Neural Networks represent agent policies, and gradients are backpropagated through the event-based reward structure.
Graphical model representation of the event-based reward structure.

A key insight is that "Planning as Inference" allows for independent optimization per agent, providing a massive computational win over monolithic solvers. Furthermore, the paper demonstrates that history-dependent rewards can be mathematically accounted for without baking history into the agent's state, keeping the underlying MDP tractable.

Experimental Evaluation

The methods were evaluated on two primary domains: the Mars Rover Domain, a benchmark task for coordinating multiple rovers, and the Singapore MRT Coverage, a large-scale real-world application modeling the Singapore subway system with an exponential state space ($O(2^n)$ per agent).

Performance comparison between NLP and EM solvers across various metrics.

In the Mars Rover domain, the EM approach was significantly faster and more reliable than standard NLP solvers. On "Hard" instances, the NLP solver only finished 40% of the time within the 30-minute limit, while EM converged for 100% of instances. EM also consistently achieved higher rewards, with the performance gap widening as problem difficulty increased. In the Singapore MRT scenario, where the state space was too large for EM or NLP to initialize, the MARL approach successfully scaled. The coordinated MARL approach outperformed independent reinforcement learning by 15% to 36% in total reward, proving that the method successfully fosters meaningful agent cooperation.

Discussion and Conclusion

While the paper makes significant strides, it assumes "transition independence," meaning one agent's movement doesn't physically block another. Future work could extend these event-based reward techniques to fully decentralized POMDPs where agents have even less information about the world. Despite the longer training times for the RL approach compared to EM on smaller problems, its ability to scale to real-world complexities like urban subway networks marks a significant step forward in practical multi-agent coordination.

Summary updated

Abstract

Decentralized (PO)MDPs provide a rigorous framework for sequential multiagent decision making under uncertainty. However, their high computational complexity limits the practical impact. To address scalability and real-world impact, we focus on settings where a large number of agents primarily interact through complex joint-rewards that depend on their entire histories of states and actions. Such history-based rewards encapsulate the notion of events or tasks such that the team reward is given only when the joint-task is completed. Algorithmically, we contribute — 1) A nonlinear programming (NLP) formulation for such event-based planning model; 2) A probabilistic inference based approach that scales much better than NLP solvers for a large number of agents; 3) A policy gradient based multiagent reinforcement learning approach that scales well even for exponential state- spaces.
BibTeX
@inproceedings{gupta2018planning,
  author = {Tarun Gupta and Akshat Kumar and Praveen Paruchuri},
  title = {{Planning and Learning for Decentralized MDPs with Event Driven Rewards}},
  booktitle = {Workshops @ AAAI},
  year = {2018},
  url = {https://openreview.net/forum?id=r1WZyeWd-r},
}
Figure