Source-linked AI summary
Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs
Sven Seuken, Shlomo Zilberstein
TL;DR
DEC-POMDPs are difficult to solve, and original MBDP still has exponential memory growth in the observation set. The paper improves MBDP with partial backups over likely observations and analyzes the approximation. Experiments report efficient good solutions for reasonably hard problems, while a complete error bound remains open.
Problem
Original MBDP's memory requirements grow exponentially with the observation set, limiting its scalability for DEC-POMDPs.
Source: §1 · p. 1, §4.1 · p. 3Method
Results
Good solutions for reasonably hard DEC-POMDPs can be computed efficiently despite their double-exponential complexity.
Source: §7 · pp. 7–8Takeaways & Limitations
The experiments support scalable MBDP as a way to compute good solutions for reasonably hard DEC-POMDPs.
Source: §7 · p. 8A complete error bound remains unavailable because the error from selecting policy trees through belief-space sampling is not bounded.
Source: §7 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
DEC-POMDPs model cooperative agents with different partial knowledge, but solving finite-horizon problems is computationally hard. The paper improves MBDP to reduce its observation-related memory demands and evaluates the approach on a harder benchmark.
1 Introduction
- Finite-horizon DEC-POMDP solving is NEXP-complete, and even ε-approximations are hard.The model supports cooperative multi-agent problems in which agents have different partial knowledge of the environment and one another.Source: §1 · p. 1
- MBDP enabled much longer horizons than prior approximate algorithms, with polynomial runtime in the horizon and a demonstrated horizon of 100,000 for multi-agent tiger.The cited comparison says other approximate algorithms could not solve problems with horizons larger than 10.Source: §1 · p. 1
- The improved MBDP targets exponential memory growth in the observation set by focusing on observations likely or possible at a belief point.The paper also analyzes the approximation's error and convergence, and tests it on a new, harder benchmark.Source: §1 · p. 1
2 Related Work
Prior work explores heuristic search, reachable-belief policies, and game-theoretic approximations for finite-horizon DEC-POMDPs. The section emphasizes that scalability remained a challenge beyond MBDP.
2 Related Work
- Point-Based Dynamic Programming (PBDP) computes policies from a subset of reachable belief states and is most closely related to original MBDP, though it is not memory-bounded.Source: §2 · p. 2
- Common-payoff POSGs can be approximated through a series of smaller Bayesian games.The section presents this as one example of game-theoretic techniques applied to DEC-POMDPs treated as POSGs.Source: §2 · p. 2
- Except for MBDP, the surveyed algorithms could not solve existing benchmark problems beyond horizon 10, while MBDP quickly found near-optimal solutions at much larger horizons.The section concludes that true scalability remained a challenge.Source: §2 · p. 2
3 Solving Decentralized POMDPs
A finite-horizon DEC-POMDP represents decentralized agents, states, beliefs, actions, observations, transitions, rewards, and a horizon; a solution is a joint policy. The section contrasts top-down search with bottom-up dynamic programming and explains how MBDP combines their strengths.
3 Solving Decentralized POMDPs
- A DEC-POMDP specifies agents, states, an initial belief, actions, transitions, observations, rewards, and a finite horizon.Agents act from local observation histories, and solving the model means finding a joint policy maximizing expected total reward.Source: §3 · p. 2
- In a DEC-POMDP, an agent's policy tree maps observation histories to actions, and a joint policy's value depends on the other agents' policies and the initial belief.The agents do not observe the underlying system state during execution and instead use beliefs about the state and other agents' policies.Source: §3 · p. 2
- MAA∗ expands joint policy trees from one horizon to the next and uses heuristics to prune search, but its search space grows double exponentially with horizon.It can run out of time even on small problems with very short horizons.Source: §3 · pp. 2–3
Bottom-up Approach: Dynamic Programming
- Bottom-up dynamic programming builds policy trees from their frontiers and eliminates dominated policies, yet the remaining tree sets can still exhaust memory.MBDP addresses this pruning limitation by using top-down heuristics to identify relevant beliefs for evaluating bottom-up trees and selecting a joint policy.Source: Bottom-up Approach: Dynamic Programming · p. 3
4 The Improved MBDP Algorithm
The improved MBDP retains top-down belief selection and bottom-up policy construction while limiting backups to likely observations. This targets exponential observation-set complexity, with local search completing branches omitted from partial backups.
4 The Improved MBDP Algorithm
- Recursive MBDP uses completed solutions as heuristic policies to identify relevant belief states, and can be applied with arbitrary recursion depth.The usefulness of heuristics and computed belief states depends on the problem.Source: §4 · p. 3
4.1 Motivation for new Approximation
- Original MBDP is linear in horizon but exponential in observation-set size, making even a small two-action, five-observation problem prohibitive at maxTrees = 5.The passage reports that no existing algorithm could solve a DEC-POMDP with two actions and five observations.Source: §4.1 · p. 3
4.2 The Improvement: Partial Backups
- Because many observations may be unlikely or impossible for a given belief and action, the algorithm selects the most likely observations, capped at maxObs, for partial backups.It ranks joint observations by probability, selects the most likely observations separately for each agent, and implicitly considers maxObs^n joint observations.Source: §4.2 · p. 4, §4.1 · p. 4
- After partial backups, local search fills missing observation branches by choosing available subnodes with the highest expected utility for the belief state.Figure 1 depicts a single policy tree combining top-down and bottom-up construction.Source: §4.2 · p. 4, Figure 1 · p. 4
5 Theoretical Analysis
The analysis bounds solution-value loss from partial backups, shows the bound vanishes as maxObs approaches the full observation set, and establishes polynomial time and space complexity under fixed-parameter conditions.
5.1 Error Bound
- The approximation depends on maxTrees and maxObs, while ε tracks the probability mass retained by selected observations.The selected observations are constrained so each agent has at most maxObs local observations.Source: §5 · p. 4, §5.1 · pp. 4–5
- For horizon-T policies, partial-backup error is bounded; in the base case, value loss is at most (1−ε)(Rmax−Rmin).The overall error bound is denoted µT; the base-case loss occurs when an observation outside the selected set is encountered.Source: §5.1 · pp. 5–6
5.2 Convergence
- As maxObs approaches |O|, the error bound strictly decreases and reaches zero when maxObs equals |O|.At that limit, the algorithm performs full rather than partial backups.Source: §5.2 · p. 6
5.3 Complexity Properties
- For a fixed number of agents, the improved MBDP algorithm has polynomial time and space complexity in the other input parameters.The analysis assumes fixed maxTrees and maxObs.Source: §5.3 · p. 6
- The complexity result does not describe scaling with desired accuracy; if every observation matters, maxObs < |O| can produce a bad solution.How large maxObs must be for a target accuracy depends on the entries of the observation-probability table.Source: §5.3 · p. 6
6 Experiments
Existing benchmarks show MBDP’s ability to handle very long horizons, but their small observation spaces do not test partial backups. Cooperative Box-Pushing adds a larger-observation benchmark that the improved algorithm can tackle.
6.1 Existing Benchmark Problems
- MBDP matched or exceeded existing algorithms on the MABC benchmark and solved horizons up to 100,000 within 24 hours.The results suggest optimal values at every tested horizon, although optimal-solver comparisons were unavailable at the larger horizons.Source: §6.1 · p. 6
- Because MABC and multi-agent tiger each have only two observations, improved MBDP produces the same results as original MBDP on these benchmarks.Partial backups are unnecessary for observation spaces of size two.Source: §6.1 · p. 6
6.2 Cooperative Box-Pushing
- Cooperative Box-Pushing is introduced as a flexible DEC-POMDP benchmark for algorithms handling larger observation spaces.Two or more non-communicating agents must coordinate to move a large box they cannot move alone.Source: §6.2 · p. 6
- The small Box-Pushing instance has 100 states, four actions, and five observations; previous algorithms, including original MBDP, cannot tackle it even for horizons below five.The improved algorithm handles this instance using partial backups with maxObs = 3 and maxTrees = 3; Table 1 is captioned as comparing MABC and Box-Pushing performance.Source: §6.2 · p. 7, Table 1 · p. 7
7 Conclusion
The paper reduces MBDP’s observation-set complexity using partial backups and analyzes the resulting approximation error. It reports efficient good solutions on harder problems, while noting that a complete error bound remains unresolved.
7 Conclusion
- Partial backups over only the most likely observations reduce MBDP’s observation-set complexity from exponential to polynomial.The approach relies on many observations being highly unlikely or impossible in most belief states.Source: §7 · p. 7
- The analysis bounds worst-case error from partial backups, finds a quadratic relationship with horizon, and shows the bound decreases toward zero as maxObs increases.The paper notes that this quadratic relationship contrasts with the intuitive expectation of exponential error accumulation.Source: §7 · p. 7
- Cooperative Box-Pushing provides a benchmark that, at the time of the paper, only improved MBDP could solve.The authors report that good solutions for reasonably hard problems can be computed efficiently despite DEC-POMDPs’ double-exponential complexity.Source: §7 · pp. 7–8
- A complete error bound remains unavailable because the analysis does not bound error from selecting policy trees through belief-space sampling.The paper identifies this part of the error analysis as challenging.Source: §7 · p. 8