Solving Transition Independent Decentralized Markov Decision Processes

By Raphen Becker, Shlomo Zilberstein, Victor R. Lesser, C. V. Goldman. 2004

278 citations recorded by the source corpus.

Formal treatment of collaborative multi-agent systems has been lagging behind the rapid progress in sequential decision making by individual agents. Recent work in the area of decentralized Markov Decision Processes (MDPs) has contributed to closing this gap, but the computational complexity of these models remains a serious obstacle. To overcome this complexity barrier, we identify a specific class of decentralized MDPs in which the agents' transitions are independent. The class consists of independent collaborating agents that are tied together through a structured global reward function that depends on all of their histories of states and actions. We present a novel algorithm for solving this class of problems and examine its properties, both as an optimal algorithm and as an anytime algorithm. To the best of our knowledge, this is the first algorithm to optimally solve a non-trivial subclass of decentralized MDPs. It lays the foundation for further work in this area on both exact and approximate algorithms.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Multi-agent Reinforcement Learning in Sequential Social Dilemmas (2017, background): “Researchers have also studied the emergence of multi-agent coordination in the decentralized, partially observable MDP framework [36, 37, 38].”
Optimal and Approximate Q-value Functions for Decentralized POMDPs (2008, background): “In particular, transition and observation independent Dec-MDPs (Becker et al., 2004b; Wu & Durfee, 2006) and Dec-POMDPs (Kim, Nair, Varakantham, Tambe, & Yokoo, 2006; Varakantham et al., 2007) have received quite some attention.”
Decentralized planning under uncertainty for teams of communicating agents (2006, background): “Given a factored state space one can further assume that the agents’ transitions are independent [27, 1, 18], or impose a particular joint reward structure [1].”
Perseus: Randomized Point-based Value Iteration for POMDPs (2005, unknown): “…(Guestrin, Koller, & Parr, 2001; Theocharous, Murphy, & Kaelbling, 2004), as well as applying Perseus to cooperative multiagent domains, extending recent approaches (Emery-Montemerlo, Gordon, Schneider, & Thrun, 2004; Becker, Zilberstein, Lesser, & Goldman, 2004; Paquet, Tobin, & Chaib-draa, 2005).”
Graphical Model Inference in Optimal Control of Stochastic Multi-Agent Systems (2008, methodology): “A similar approach was taken by Becker, Zilberstein, Lesser, and Goldman (2003, 2004) , assuming independent collaboration of the agents with a global reward function, resulting in transition-independent decentralized MDPs.”
Multi-objective multi-agent decision making: a utility-based analysis and survey (2019, background): “Another approach is to build influence models that allow agents to identify what are the important components that should be factored into their reasoning process [15,34,114].”
Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games (2011, background): “vich et al., 2003). Given these difﬁculties, most research efforts have focuse d on special cases that are more tractable. In particular, assumptions of transition and observation independence (TOI) (Becker et al., 2004) have been investigated to exploit independence between agents, e.g., as in ND-P”
Scalable Planning and Learning for Multiagent POMDPs (2014, methodology): “uture directions in multiagent learning. Further improvements could utilize additional domain or policy assumptions to improve scalability. For instance, with transition and observation independence (Becker et al. 2004), and other models of locality of interaction, such as ND-POMDPs (Nair et al. 200”
Q-value Heuristics for Approximate Solutions of Dec-POMDPs (2007, methodology): “Besides brute force search, more sophisticated methods of searching for policies have been proposed in recent years (Hansen, Bernstein, & Zilberstein 2004; Becker et al. 2004; Emery-Montemerloet al. 2004; Gmytrasiewicz & Doshi 2005). In this paper we focus on the algorithm of EmeryMontemerloet al. (”
Point-based Dynamic Programming for DEC-POMDPs (2006, background): “It has also been shown that the exploitation of particular structure may facilitate the computation of an optimal solution ( Becker et al. 2004 ).”
Decentralized POMDPs (2012, methodology): “Mostafa and Lesser (2009) introduced the EDI-CR, a type of Dec-POMDP that generalizes TOI and ED-Dec-MDPs.”
Decentralized MDPs with sparse interactions (2011, methodology): “Transition independent Dec-MDPs are NP-complete and can be solved using the Coverage Set algorithm [41,27].”
Multiagent Learning of Coordination in Loosely Coupled Multiagent Systems (2015, result): “In [37], a specific Dec-MDPs model called transition-independent Dec-MDPs [37], [38] is identified, in which the overall transition function P can be separated into n+1 distinct functions P0, .”
Memory-Bounded Dynamic Programming for DEC-POMDPs (2007, background): “Another way of addressing the high complexity of DECPOMDPs is to develop algorithms for problem classes that exhibit certain structure [Becker et al., 2004; Goldman and Zilberstein, 2005].”
Planning with macro-actions in decentralized POMDPs (2014, methodology): “Events which may require or allow interaction have been explored in Dec-MDPs [5] and (centralized) multirobot systems [21].”
QueryPOMDP: POMDP-Based Communication in Multiagent Systems (2011, background): “In the Dec-POMDP literature, early approaches introduced the idea of transition and reward independence as forms of simpliﬁed interactions [26].”