Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs

By Sven Seuken, Shlomo Zilberstein. 2007

146 citations recorded by the source corpus.

Memory-Bounded Dynamic Programming (MBDP) has proved extremely effective in solving decentralized POMDPs with large horizons. We generalize the algorithm and improve its scalability by reducing the complexity with respect to the number of observations from exponential to polynomial. We derive error bounds on solution quality with respect to this new approximation and analyze the convergence behavior. To evaluate the effectiveness of the improvements, we introduce a new, larger benchmark problem. Experimental results show that despite the high complexity of decentralized POMDPs, scalable solution techniques such as MBDP perform surprisingly well.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Reinforcement Learning, Optimization & Training

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 Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “Game Reference(s) Status Backgammon Wikipedia Breakthrough Wikipedia Bridge bidding Wikipedia Coin Game [56] ∼ Connect Four Wikipedia Cooperative Box-Pushing [62] ∼ Chess Wikipedia First-price Sealed-bid Auction Wikipedia Go Wikipedia Goofspiel Wikipedia Havannah Wikipedia Hex Wikipedia ∼ Kuhn poker”
Optimal and Approximate Q-value Functions for Decentralized POMDPs (2008, background): “To counter this growth, Seuken and Zilberstein (2007a) proposed an extension that limits the considered observations during the backup step to the maxObs most likely observations.”
Decentralized POMDPs (2012, background): “MAA ∗ performs standard A∗ search (Russell and Norvig, 2003): it maintains an open list P of partial joint policies ϕt and their heuristic values V̂ (ϕt).”
Lossless clustering of histories in decentralized POMDPs (2009, methodology): “Other problems we used are GridSmall with two observations [1]; Cooperative Box Pushing [15], a larger two-robot benchmark; Recycling Robots [2]; FireFighting [12], and Hotel 1 [16].”
Rollout Sampling Policy Iteration for Decentralized POMDPs (2010, methodology): “The policies for ﬁnite-horizon DEC-POMDPs are often represented as a set of local policy trees [1, 8, 11, 17, 18].”
Incremental Policy Generation for Finite-Horizon DEC-POMDPs (2009, methodology): “To improve the worst-case complexity of our algorithm, it can be incorporated into a memory bounded (MBDP-based) algorithm.”