Optimal and Approximate Q-value Functions for Decentralized POMDPs

Frans A. Oliehoek, Matthijs T. J. Spaan, Nikos Vlassis

TL;DR

This paper establishes a formal theory of optimal and approximate Q-value functions for Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs), proving they can be represented as sequences of Bayesian games. The authors establish a theoretical hierarchy of upper-bound heuristics ($Q^* \le Q_{\text{BG}} \le Q_{\text{POMDP}} \le Q_{\text{MDP}}$) and introduce Generalized MAA* ($\text{GMAA}^*$), a unifying framework that bridges exact heuristic search with fast approximate forward-sweep policy methods.

What Problem Does This Paper Address?

Dec-POMDPs model cooperative multi-agent teams operating in stochastic, partially observable environments without communication during execution. While single-agent MDPs and POMDPs rely heavily on dynamic programming with action-value ($Q$) functions, a comparable theory has been absent for Dec-POMDPs because agents lack a shared Markovian belief state—each agent only observes its own local action-observation history.

As Dec-POMDPs are provably NEXP-complete, prior algorithms primarily relied on policy iteration, dynamic programming with tree pruning, or heuristic forward search. The challenge is defining what an "optimal Q-value function" even means when future decisions depend on joint histories that decentralized agents cannot collectively track.

Methods

  • Normative & Sequentially Rational $Q^*$:
  • Normative form: Evaluates the expected return of an optimal joint policy $\pi^*$. Forward-sweep policy computation (FSPC) using this $Q^*$ yields an optimal policy by solving a series of Bayesian games.
  • Sequentially rational form: The authors show that an action value $Q^*(\vec{\theta}^t, a^t)$ is ill-defined without an assumed past joint policy $\varphi^{t+1}$ (which induces the belief over past histories). They define $Q^*(\vec{\theta}^t, \varphi^{t+1})$, which considers off-equilibrium paths and is computable via backward dynamic programming.
  • $k$-Step Delayed Communication Models & Approximate $Q$-Functions:
  • $Q_{\text{MDP}}$: Assumes state becomes fully observable at the next step (standard MDP).
  • $Q_{\text{POMDP}}$: Assumes agents can pool observations centrally with 0-step delay.
  • $Q_{\text{BG}}$: Assumes agents share history with a 1-step delay; actions are chosen by solving a Bayesian game over the most recent local observation.
  • The paper frames these approximations as $k$-step delayed communication models to prove the bound hierarchy: $$Q^* \le Q_{\text{BG}} \le Q_{\text{POMDP}} \le Q_{\text{MDP}}$$
  • Generalized $\text{MAA}^*$ ($\text{GMAA}^*$):
  • Unifies heuristic tree search ($\text{MAA}^*$) and forward-sweep policy computation (FSPC).
  • Introduces $k$-$\text{GMAA}^*$, which retains the $k$-best joint policies at each stage, recovering greedy FSPC when $k=1$ and exact $\text{MAA}^*$ when $k=\infty$.

Datasets & Benchmark Domains

The authors evaluate algorithms across several established and newly introduced domains:

  1. Dec-Tiger: Classic 2-agent hallway benchmark where agents must listen or open doors.
  2. Skewed Dec-Tiger: Dec-Tiger with an asymmetric initial belief ($P(s_l) = 0.8$).
  3. BroadcastChannel: 2-node shared transmission channel problem.
  4. Meeting on a Grid: 2 robots navigating a $2 \times 2$ grid (using the 2-observation variant).
  5. FireFighting (New Benchmark): Two agents navigate a row of $n_h$ houses (each with discrete fire levels $f \in \{0, \dots, n_f-1\}$) to extinguish spreading fires. Tested configurations include $\langle n_h=3, n_f=3 \rangle$ and $\langle n_h=4, n_f=3 \rangle$.

Key Insights and Ideas

  • Bayesian Game Equivalence: Dec-POMDP planning across time steps can be mapped directly to solving a sequence of Bayesian games with identical payoffs, where agent types are action-observation histories.
  • Why Single-Agent Backups Fail: Unlike MDPs/POMDPs where the future can be optimized independently of the past, a Dec-POMDP agent's optimal decision rule at stage $t+1$ depends on the distribution over joint histories, which itself is dictated by the past joint policy $\varphi^{t+1}$.
  • Delay as an Information Relaxation: Viewing centralized POMDPs (delay 0), $Q_{\text{BG}}$ (delay 1), and Dec-POMDPs (delay $h$) through the lens of delayed communication provides an elegant, formal proof that tighter communication delays strictly upper-bound looser ones.
  • Tighter Heuristics Accelerate Exact Search: Using $Q_{\text{BG}}$ over $Q_{\text{MDP}}$ dramatically tightens admissible bounds, pruning vast swaths of the policy pool in $\text{MAA}^*$.

Key Results

  • Pruning in Exact $\text{MAA}^*$:
  • On Dec-Tiger ($h=4$), $\text{MAA}^*$ using $Q_{\text{MDP}}$ evaluated $\approx 3.75 \times 10^{10}$ policies taking $431,776\text{ s}$ ($\sim 5$ days). Switching to $Q_{\text{BG}}$ evaluated $3.01 \times 10^8$ policies and ran in $3,208\text{ s}$ (over a $130\times$ speedup).
  • On Skewed Dec-Tiger ($h=4$), $Q_{\text{BG}}$ solved the problem in $919\text{ s}$ compared to $8,908\text{ s}$ for $Q_{\text{POMDP}}$ and $388,894\text{ s}$ for $Q_{\text{MDP}}$.
  • On BroadcastChannel ($h=5$), $Q_{\text{MDP}}$ failed to finish within 5 days, while both $Q_{\text{POMDP}}$ and $Q_{\text{BG}}$ solved it in $\approx 5.2\text{ s}$.
  • Approximate Search ($k$-$\text{GMAA}^*$):
  • For $k$-$\text{GMAA}^*$ with $Q_{\text{BG}}$ and $Q_{\text{POMDP}}$, retaining just $k \le 2$ policies was sufficient to find the optimal policy across nearly all benchmark instances, presenting an effective anytime/sub-optimal planning trade-off.

Limitations and Future Work

  • Doubly Exponential Complexity of Exact $Q^*$: Computing the sequentially rational $Q^*$ still requires dynamic programming over all possible past joint policies, making exact computation intractable for larger horizons.
  • Approximate Bayesian Game Solvers: Solving large stage Bayesian games remains a bottleneck; efficient approximate BG solvers are needed to scale.
  • Tighter Delays: Extending bounds to $k$-step delayed communication where $k \ge 2$ could provide even tighter heuristics, though efficient methods to compute them must be developed.
  • Extension to Competitive Settings: The paper focuses on cooperative teams; extending these Q-value formulations to partially observable stochastic games (POSGs) with competing objectives remains an open problem.

Summary updated

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.
BibTeX
@article{oliehoek2008optimal,
  author = {Frans A. Oliehoek and Matthijs T. J. Spaan and Nikos Vlassis},
  title = {{Optimal and Approximate Q-value Functions for Decentralized POMDPs}},
  journal = {J. Artif. Intell. Res.},
  year = {2008},
  url = {https://openreview.net/forum?id=IMx2LV0ZCy},
}

Loading related content...

Figure