Optimal and Approximate Q-value Functions for Decentralized POMDPs

By Frans Adriaan Oliehoek, Matthijs T. J. Spaan, Nikos A. Vlassis. 2008

582 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Reinforcement Learning, Game & Decision Theory

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

  1. Shimon Whiteson
  2. Chongjie Zhang
  3. Wendelin Böhmer
  4. Jakob N. Foerster
  5. Tabish Rashid
  6. Christian Schröder de Witt
  7. Filippos Christianos
  8. Bei Peng

In Reinforcement Learning

  1. Shimon Whiteson
  2. Chongjie Zhang
  3. Wendelin Böhmer
  4. Tabish Rashid
  5. Christian Schröder de Witt
  6. Jakob N. Foerster
  7. Bei Peng
  8. Tonghan Wang

In Game & Decision Theory

  1. Shimon Whiteson
  2. Christian Schröder de Witt
  3. Jakob N. Foerster
  4. Tabish Rashid
  5. Hengyuan Hu
  6. Chongjie Zhang
  7. Adam Lerer
  8. Wendelin Böhmer

Citations in the corpus