Abstract
Decision-theoretic planning is a popular approach to sequential decision making problems, because it treats uncertainty in sensing and acting in a principled way. In single-agent frameworks like MDPs and POMDPs, planning can be carried out by resorting to Q-value functions: an optimal Q-value function $Q^*$ is computed in a recursive manner by dynamic programming, and then an optimal policy is extracted from $Q^*$. In this paper we study whether similar Q-value functions can be defined for decentralized POMDP models (Dec-POMDPs), and how policies can be extracted from such value functions. We define two forms of the optimal Q-value function for Dec-POMDPs: one that gives a normative description as the Q-value function of an optimal pure joint policy and another one that is sequentially rational and thus gives a recipe for computation. This computation, however, is infeasible for all but the smallest problems. Therefore, we analyze various approximate Q-value functions that allow for efficient computation. We describe how they relate, and we prove that they all provide an upper bound to the optimal Q-value function $Q^*$. Finally, unifying some previous approaches for solving Dec-POMDPs, we describe a family of algorithms for extracting policies from such Q-value functions, and perform an experimental evaluation on existing test problems, including a new firefighting benchmark problem.
Introduction
In single-agent environments, such as Markov Decision Processes (MDPs) or Partially Observable MDPs (POMDPs), agents use optimal Q-value functions ($Q^*$) to determine the best action for any given state or belief. However, in a Decentralized POMDP (Dec-POMDP), multiple agents must coordinate their actions based solely on their local, private histories of observations and actions. Without a central controller or free communication, the "state" of the system from an individual's perspective is elusive, making Dec-POMDPs notoriously difficult to solve—specifically, they are NEXP-complete.
As shown in Figure 1, the decentralized nature of the problem stems from the fact that each agent's action $a_n^t$ depends only on its local observation history $o_n^t$, while the global state $s^t$ evolves based on the joint actions of all agents. This paper bridges the gap in multi-agent theory by defining optimal and approximate Q-functions for these systems.
Formalizing Q-values for Dec-POMDPs
The authors approach the problem by modeling a Dec-POMDP as a series of Bayesian Games (BGs). Each time step in the planning horizon is treated as a game where agents' "types" are their action-observation histories. They propose two forms of the optimal Q-function:
- Normative Description: A Q-function of an optimal pure joint policy.
- Sequential Rationality: A version that explicitly incorporates the past joint policy to make the Q-values computable via dynamic programming. By "fixing" the past, they turn an impossible coordination problem into a computable one.
Approximate Q-functions and the Hierarchy of Bounds
Since computing $Q^*$ is often infeasible, the paper analyzes three approximations based on varying assumptions of information sharing:
- $Q_{MDP}$: Assumes the state is fully observable in the next step.
- $Q_{POMDP}$: Assumes agents can pool their observations (centralized control).
- $Q_{BG}$: A new approximation assuming agents know the joint history up to the previous step but are uncertain about the current step's observations.
A key insight of this work is the proof of a Hierarchy of Bounds: $Q^* \leq Q_{BG} \leq Q_{POMDP} \leq Q_{MDP}$. Because these are all upper bounds, they can serve as "admissible heuristics" in search algorithms.
GMAA: Generalized Multiagent A
The authors introduce GMAA*, a unified heuristic search framework that builds joint policies stage-by-stage. By using the approximate Q-functions as heuristics, the algorithm can prune sub-optimal branches of the search tree. For example, a tighter bound like $Q_{BG}$ allows for much more aggressive pruning than a loose bound like $Q_{MDP}$.
Experimental Evaluation
The approach was evaluated on standard benchmarks (Dec-Tiger, BroadcastChannel, Meeting on a Grid) and a new FireFighting problem where agents coordinate to extinguish spreading fires based on noisy observations.
Key Results: * Pruning Efficiency: In the Dec-Tiger problem (horizon 4), $Q_{BG}$ reduced the number of partial policies evaluated from over 37 billion (with $Q_{MDP}$) to just 301 million. * Speedups: On the "Meeting on a Grid" task, GMAA with $Q_{BG}$ was nearly 20x faster than using $Q_{MDP}$. * Policy Quality:* Fast, non-optimal approaches (Forward-Sweep Policy Computation) often found the true optimal policy when guided by the tighter $Q_{BG}$ or $Q_{POMDP}$ heuristics.
Conclusion
This work provides the first rigorous theoretical foundation for Q-value functions in decentralized settings. While Dec-POMDPs remain fundamentally difficult due to their double-exponential complexity, the introduction of the $Q_{BG}$ heuristic and the GMAA* framework significantly extends the horizon of problems that can be solved optimally. Future work includes extending these theories to Partially Observable Stochastic Games (POSGs) and exploring heuristics based on multi-step communication delays.
Summary updated