Lossless clustering of histories in decentralized POMDPs

By Frans Adriaan Oliehoek, Shimon Whiteson, Matthijs T. J. Spaan. 2009

52 citations recorded by the source corpus.

Decentralized partially observable Markov decision processes (Dec-POMDPs) constitute a generic and expressive framework for multiagent planning under uncertainty. However, planning optimally is difficult because solutions map local observation histories to actions, and the number of such histories grows exponentially in the planning horizon. In this work, we identify a criterion that allows for lossless clustering of observation histories: i.e., we prove that when two histories satisfy the criterion, they have the same optimal value and thus can be treated as one. We show how this result can be exploited in optimal policy search and demonstrate empirically that it can provide a speed-up of multiple orders of magnitude, allowing the optimal solution of significantly larger problems. We also perform an empirical analysis of the generality of our clustering method, which suggests that it may also be useful in other (approximate) Dec-POMDP solution methods.

How researchers see this paper

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

Citations in the corpus

Multi-agent reinforcement learning as a rehearsal for decentralized planning (2016, neutral): “Exact solution methods [22] have dealt with this expo-”
A Concise Introduction to Decentralized POMDPs (2016, methodology): “In order to mitigate the problem, it is possible to apply lossless clustering of the histories of the agents [Oliehoek et al., 2009], or to try and avoid the expansion of all child nodes by incrementally expanding nodes only when needed [Spaan et al.”
Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion (2011, background): “Categories and Subject Descriptors I.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence—Multiagent systems General Terms Algorithms, Theory, Experimentation Keywords Planning under uncertainty, Cooperative multiagent systems, Decentralized POMDPs, Heuristic search”
Incremental Policy Generation for Finite-Horizon DEC-POMDPs (2009, methodology): “The results in Table 2 show that on these problems, incremental policy generation is always more scalable than the previous dynamic programming approach and generally more scalable than the leading top-down approach, C-GMAA∗.”
Decentralized POMDPs (2012, methodology): “Second, it is possible to reduce the number of histories under concern via pruning (Emery-Montemerlo et al, 2004), approximate clustering (Emery-Montemerlo et al, 2005) or lossless clustering (Oliehoek et al, 2009).”
Rethinking Formal Models of Partially Observable Multiagent Decision Making (2019, background): “For example, [37] studies lossless clustering of histories in Dec-POMDPs, which very closely corresponds to the notion of well-formed imperfect-recall games [27, 24].”
Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games (2011, methodology): “f minimizing regret, as suggested by Vickrey and Koller (2002). Our approach to solving Dec-POMDPs with CGBGs could be integrated with methods for clustering histories (Emery-Montemerlo et al., 2005; Oliehoek et al., 2009) to allow scaling to larger horizons. In addition, there is great potential fo”