PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal and Approximate Q-value Functions for Decentralized POMDPs

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

arXiv:1111.0062v1cs.AI

TL;DR

Dec-POMDPs lacked a corresponding theory of Q-value functions for decentralized planning under partial observability. The paper defines optimal and approximate Q-functions, develops policy-extraction algorithms, and proves an upper-bound hierarchy while showing that exact Q* computation is feasible only for the smallest problems.

  • Problem

    Dec-POMDP research lacked a theory establishing whether Q-value functions could be defined and used to extract policies as in MDPs and POMDPs.

  • Method

    The paper defines normative and sequentially rational optimal Q-functions, analyzes approximate Q-functions, and develops GMAA* for extracting policies from them.

  • Results

    Q*≤QBG≤QPOMDP≤QMDP, while experiments show tighter heuristics reduce computation time and QBG generally finds better approximate solutions in tested settings.

  • Takeaways & Limitations

    Q-value functions provide a framework for extending value-based planning and unifying several Dec-POMDP solution approaches.

  • Takeaways & Limitations

    Exact Q* computation is infeasible beyond the smallest problems, and efficient approximate methods for solving the Bayesian games remain needed.

Abstract

from arXiv · show

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.

1. Introduction

The paper asks whether Dec-POMDPs can support Q-value functions like those used in single-agent planning, and develops theory and algorithms around that question. It defines optimal and approximate Q-functions, policy-extraction procedures, and evaluates them experimentally.

  • Motivation: Dec-POMDPs add decentralized coordination to partial observability because agents lack a common signal for conditioning actions.Each agent observes only its own observations and actions, making joint planning distinct from single-agent POMDP planning.
  • Research gap: Unlike MDPs and POMDPs, Dec-POMDPs lacked a developed theory of Q-value functions and policy extraction despite their planning relevance.The paper situates this gap alongside known Q-value methods for MDPs and POMDPs and the established intractability of Dec-POMDPs.
  • Contributions: The paper defines an optimal Dec-POMDP Q-function and shows that forward-sweep policy computation can extract an optimal policy by solving Bayesian games sequentially.The construction extends forward-sweep policy computation to the exact setting using Q* as the Bayesian-game payoff.
  • Contributions: Three approximate Q-functions are analyzed as efficiently computable upper bounds, with the hierarchy Q*≤QBG≤QPOMDP≤QMDP.The paper also introduces a generalized QBG family that contains QPOMDP, QBG, and Q*.
  • Contributions: GMAA* generalizes MAA* to extract optimal or sub-optimal policies from approximate Q-functions and unifies several earlier solution approaches.Its subroutine choices recover approaches including MAA* and forward-sweep policy computation.
  • Evaluation: The evaluation compares Q-functions and GMAA* settings on established problems and a new firefighting benchmark.The experiments examine differences among QMDP, QPOMDP, QBG, and Q* and test tighter heuristics.

2. Decentralized POMDPs

A finite-horizon Dec-POMDP models cooperative agents acting from private observations in a stochastic environment. Its objective is to choose a joint policy maximizing expected cumulative reward under decentralized information.

  • Model: A finite-horizon Dec-POMDP has agents act at discrete stages, with joint actions affecting state transitions and subsequent observations.The horizon is finite, and each agent receives an observation before acting again.
  • Model: The environment is specified by states, a transition function, an observation function, and a reward function.Transitions and observations are assumed Markovian and stationary in the general finite model considered here.
  • Model: Joint actions and observations are Cartesian products of the agents’ individual action and observation sets, although each agent sees only its own components.Agents know their own actions but do not observe one another’s actions.
  • Objective: A Dec-POMDP’s objective is to find a joint policy maximizing expected cumulative reward from an initial state distribution.The return sums rewards over execution stages, with rewards determined by states and joint actions.
  • Policies: For finite-horizon Dec-POMDPs, at least one optimal pure joint policy exists.This establishes that deterministic joint policies suffice for attaining an optimum, even though randomized policies can also be considered.

3. Overview of Dec-POMDP Solution Methods

Existing finite-horizon Dec-POMDP methods search, optimize responses, or construct policies dynamically, but their representations and computational strategies differ substantially. The section highlights severe complexity and several ways methods exploit structure or heuristics.

  • Brute-force search: Brute-force enumeration can evaluate all pure joint policies, but its total cost is doubly exponential in the horizon.This follows from the number of policies and the cost of evaluating each policy.
  • JESP: JESP alternates agents’ best responses until convergence to a Nash equilibrium, guaranteeing a locally optimal joint policy.Exhaustive-JESP evaluates individual policies directly, while DP-JESP computes best responses through an augmented POMDP.
  • JESP: JESP commonly restricts computation to beliefs reachable from the known initial belief, although extensions can plan over the entire initial-belief space.This dependence on the initial belief is a methodological boundary of the standard approach.
  • MAA*: MAA* searches partially specified joint policies with admissible heuristics, pruning candidates that cannot beat the best complete policy found.It expands policies forward by appending joint decision rules at successive stages.
  • Dynamic programming: Dynamic programming constructs policies backward from last-stage actions, using sub-tree policies rather than MAA*’s forward partial-policy representation.The maintained sub-tree-policy sets grow doubly exponentially, motivating elimination of dominated sub-tree policies.
  • Dynamic programming: Figure 3 contrasts MAA*’s leaf expansion of partial policies with dynamic programming’s backup of sub-tree policies.A larger sub-tree policy is constructed from smaller policies in the dynamic-programming process.

4. Optimal Q-value Functions

This section models Dec-POMDP stages as Bayesian games and shows how optimal policies can be obtained from appropriate Q-value payoffs. It establishes the game-theoretic foundations and connects agent histories, actions, probabilities, and Q-values.

  • Modeling Dec-POMDPs with Bayesian Games: An optimal Dec-POMDP policy can be computed by solving a sequence of Bayesian games when their payoff function equals Q∗.This extends earlier approximate Bayesian-game approaches to the optimal setting.
  • Game-Theoretic Background: Bayesian games extend strategic games by allowing agents to condition actions on private information, while Nash equilibrium requires policies to be rational given the others’ policies.Strategic games provide the normal-form foundation, including pure and mixed policies and Pareto-based equilibrium selection.
  • Bayesian Games: A Bayesian game is a normal-form game with private agent types, where each policy maps an agent’s type to an action and payoffs depend on types and joint actions.Its formal representation includes agents, joint actions, joint types, a probability distribution, and payoff functions.
  • Bayesian Games: For identical-payoff Bayesian games, selecting a policy maximizing expected payoff yields a Pareto-optimal Nash equilibrium.The section proves both Nash equilibrium and Pareto optimality for this solution.
  • Modeling Dec-POMDPs with Bayesian Games: A Dec-POMDP stage maps to a Bayesian game by treating each agent’s action-observation history as its private type and preserving the agents’ action sets.The resulting game represents coordination without a shared global signal.
  • Q-values for Dec-POMDP Stages: The payoff function for a Bayesian game representing a Dec-POMDP stage is denoted Q(⃗θ^t,a), with probabilities determined by histories, prior joint policies, and the initial state distribution.This payoff must be defined consistently with the planning problem’s value function.

4.3 The Q-value Function of an Optimal Joint Policy

The paper defines Q∗ for an optimal pure joint policy and shows that forward-sweep policy computation can extract an optimal Dec-POMDP policy. However, computing Q∗ is impractical because it depends on both future and past optimal policies.

  • Q-value construction: Forward-sweep policy computation assigns a Bayesian-game payoff function at each stage to construct a joint policy sequentially.The procedure solves Bayesian games from the first stage through the last, using each stage’s joint decision rule.
  • Existence of Q∗: Q∗ is defined as the expected cumulative future reward after taking a joint action and following an optimal joint policy thereafter.For an optimal pure joint policy, the Q-value aggregates expected rewards over the remaining stages.
  • Deriving an optimal joint policy: Using Q∗ as the Bayesian-game payoff function makes each stage’s optimal decision rule identical to the corresponding optimal Bayesian-game joint policy.This equality allows the complete optimal Dec-POMDP policy to be constructed by computing decision rules for all stages.
  • Deriving an optimal joint policy: The forward construction is possible because the reachable histories at stage t depend only on the optimal joint policy from earlier stages.Previously solved Bayesian games provide the past joint policy needed to determine the next stage’s feasible histories.
  • Computing Q∗: Unlike single-agent MDPs and POMDPs, computing Q∗ in a Dec-POMDP requires dependence on both future and past optimal policies.The future-policy dependence enters Q∗ directly, while the past-policy dependence determines which histories are reachable and must be considered.

4.4 Sequential Rationality for Dec-POMDPs

Sequential rationality makes Dec-POMDP Q-values well-defined for every joint action-observation history by conditioning on a past joint policy. This yields a dynamic-programming computation and supports forward-sweep extraction of optimal future policies, although the computation is doubly exponential.

  • Computation: The sequentially rational Q* can be computed by dynamic programming from the final stage backward, evaluating histories consistent with each past joint policy.The resulting values support forward-sweep policy computation through a sequence of Bayesian games.
  • Why the original Q* is insufficient: Q*(θ_t,a_t) is undefined without a possibly randomized past policy because the induced belief over histories determines expected future rewards.Only at the final stage is the expected reward defined without assuming a past policy.
  • Sequentially rational Q*: The sequentially rational Q*(θ_t,ϕ_{t+1}) specifies the optimal value for every history-policy pair, including histories unreachable under an optimal policy.It explicitly handles off-policy histories rather than assuming that the optimal policy was followed previously.
  • Computation: Unlike the normative Q* definition, the sequentially rational formulation provides a recipe for computing values and constructing an optimal policy.The normative formulation requires knowledge of the optimal joint policy in advance.
  • Interpretation: The formulation describes sequential rationality for any past policy and may support online recomputation after an agent deviates from the prescribed policy.The paper notes that future policies can be computed for any past policy and corresponding consistent belief system.
  • Complexity: Computing sequentially rational Q* is doubly exponential and impractical for all but the smallest problems.The cost includes generating successor past policies for each joint past policy.

5. Approximate Q-value Functions

Because exact sequentially rational Q* is impractical, the paper organizes efficiently computable approximations by their information assumptions. These approximate functions include QMDP, QPOMDP, and QBG, and form a hierarchy of upper bounds on the Dec-POMDP optimum.

  • Overview: Approximate Q-value functions provide computationally cheaper alternatives to exact Q*, with differing assumptions, complexity, and approximation properties.The paper presents a taxonomy covering QMDP, QPOMDP, and QBG.
  • QMDP: QMDP approximates Dec-POMDP values using the optimal Q-function of an underlying single-agent MDP that observes the nominal state and selects joint actions.The underlying MDP preserves the original transition and reward models.
  • QMDP: QMDP undervalues information-gathering actions because it assumes the state becomes fully observable at the next time step.It is nevertheless an upper bound to the optimal Dec-POMDP value.
  • QPOMDP: QPOMDP uses the solution of an underlying single-agent POMDP, allowing actions to condition on the joint action-observation history.Its values can be computed by a backward sweep over joint action-observation histories.
  • Hierarchy of bounds: QPOMDP is an admissible upper bound and should lie between QMDP and optimal Q* because it makes fewer simplifying assumptions than QMDP.The paper formalizes this relationship through a hierarchy of delayed-communication models.
  • QBG: QBG assumes agents know the previous joint action-observation history and action but remain uncertain about one another’s latest observation.The resulting Bayesian games have single-observation types and are smaller than those based on complete histories.
  • Hierarchy of bounds: QBG and QPOMDP correspond to optimal values in delayed-communication models, yielding a hierarchy of upper bounds on Dec-POMDP Q*.The hierarchy follows from the fact that increasing communication delay preserves an upper-bound relationship.

6. Generalized Value-Based Policy Search

GMAA* generalizes value-based Dec-POMDP policy search by separating selection and expansion choices, while k-GMAA* interpolates between forward-sweep computation and exhaustive MAA*.

  • Generalized Value-Based Policy Search: GMAA* uses approximate Q-value functions as admissible heuristics for policy search.The resulting search framework can unify several Dec-POMDP solution methods.
  • Generalized Value-Based Policy Search: GMAA* iterates over a policy pool, selects a partial joint policy, and generates successor policies through configurable operators.Select determines search order, while Next constructs new partial or full policies.
  • Generalized Value-Based Policy Search: With an admissible heuristic and exhaustive MAA* expansion, GMAA* cannot prune any partial policy that extends to an optimal policy.When the policy pool becomes empty, an optimal policy has therefore been found.
  • Unification: Forward-sweep computation keeps only one policy in the pool and solves Bayesian games sequentially from time 0 through h − 1.Its Next operator returns only the highest-ranked policy at each step.
  • Unification: k-GMAA* returns the k best ranked Bayesian-game policies, reducing to forward-sweep computation at k = 1 and MAA* at k = ∞.This provides a continuum between fast one-sweep computation and exhaustive search.

7. Experiments

Experiments compare QBG, QPOMDP, and QMDP as heuristics across several Dec-POMDP benchmarks, including a new firefighting domain. Tighter bounds generally reduce search effort and often produce optimal policies with small k, though outcomes vary by problem and horizon.

  • Experimental domains: The experiments evaluate approximate Q-value heuristics on Dec-Tiger, Skewed Dec-Tiger, BroadcastChannel, Meeting on a Grid, and FireFighting.FireFighting is introduced as a new benchmark with varying numbers of houses and fire levels.
  • Q-value comparisons: Q* ≤ QBG ≤ QPOMDP ≤ QMDP holds empirically in the plotted Q-values, and the gaps can be substantial for particular problems.The experiments compare maximal Q-values over reachable joint action-observation histories.
  • MAA* evaluation: Using QPOMDP and QBG evaluated only a fraction of the policies evaluated by QMDP for Dec-Tiger at horizon 3.QBG’s heuristic computation offset its search savings at this horizon, whereas tighter heuristics mattered more at horizon 4.
  • MAA* evaluation: QBG produced a significant speedup over QPOMDP on Meeting on a Grid, while QMDP failed to solve BroadcastChannel within 5 days.Across the other reported domains, QPOMDP and QBG had roughly equal performance.
  • Forward-sweep evaluation: For horizon 4 Dec-Tiger, QPOMDP and QBG found the optimal policy with value 4.80, whereas QMDP returned expected value 3.19.The QMDP policy overestimated the value of opening the door at stage t = 2.
  • Forward-sweep evaluation: Across experiments, k-GMAA* with QBG and QPOMDP found optimal policies for k ≤2, while QMDP generally required k ≤5 with stated exceptions.The exceptions were horizon 4 Dec-Tiger and the ⟨nh = 4,nf = 3⟩ FireFighting problem.

8. Conclusions

The paper develops a Q-value framework for Dec-POMDPs and applies its theoretical insights to improve solution methods. Approximate functions support policy search, with tighter heuristics reducing computation time and QBG often producing better approximate solutions.

  • The paper fills a gap in Dec-POMDP theory by providing a framework of Q-value functions and applying its insights to solution methods.
  • An optimal joint policy induces Q*, and a sequentially rational description of Q* can be computed using dynamic programming to construct the policy.
  • The approximate functions QMDP, QPOMDP, and QBG are more efficiently computable upper bounds ordered Q* ≤ QBG ≤ QPOMDP ≤ QMDP.
  • GMAA* uses approximate Q-value functions as heuristics, unifying forward-sweep policy computation with recent Dec-POMDP solution techniques.
  • Tighter heuristics produced significant computation-time reductions for optimal policies, while QBG generally found better approximate solutions in forward-sweep and k-GMAA* methods.
  • Future work includes scaling GMAA*, establishing performance and learning bounds, evaluating tighter heuristics, and developing efficient approximate Bayesian-game methods.

A.1 There is At Least One Optimal Pure Joint Policy

A Dec-POMDP has at least one optimal pure joint policy. The proof establishes this by relating Dec-POMDP policies to actions in a strategic game and using the existence of a maximizing entry.

  • Every Dec-POMDP has at least one optimal pure joint policy.
  • The proof converts a Dec-POMDP into an extensive and then strategic game whose actions are pure Dec-POMDP policies.
  • A maximizing strategic-game entry yields a pure joint policy that cannot be outperformed by a joint stochastic policy.

A.2 Hierarchy of Q-value Functions

The hierarchy proof uses Dec-POMDPs with k-step delayed communication. It identifies QPOMDP, QBG, and Q* with specific delay cases and shows that increasing delay cannot reduce optimal expected return.

  • The proof models Dec-POMDPs with k-step delayed communication using an augmented MDP.
  • QPOMDP, QBG, and Q* correspond respectively to communication delays k = 0, k = 1, and k = h.
  • The proof shows that increasing communication delay cannot decrease optimal expected return, establishing the hierarchy of upper bounds.

A.2.1 Modeling Dec-POMDPs with k-Steps Delayed Communication

The appendix reformulates a Dec-POMDP with k-step delayed communication as an augmented MDP. Its states combine histories with policy trees, while augmented actions extend those trees and standard dynamic programming computes the resulting Q-values.

  • The augmented MDP extends prior delayed-communication formulations to the Dec-POMDP setting.
  • An augmented state consists of a joint action-observation history and a joint policy tree.
  • The contained policy tree specifies a depth-k joint policy beginning at the current stage, with fewer stages specified near the horizon.
  • For nonterminal augmented stages, an augmented action is a joint policy that implicitly maps length-k observation histories to future joint actions.
  • During the final k stages, only an empty action remains and the process is interpreted as a Markov chain solvable by standard dynamic programming.
  • Executing and observing a joint policy tree reduces it to the corresponding depth-k subtree for the observed joint observation.
  • The augmented transition and reward models update histories and policy trees while assigning the original Dec-POMDP reward for the tree's initial joint action.
  • The resulting optimal Q-function is denoted Qk and is also called the k-QBG value function.

A.2.2 Relation of k-QBG with Other Approximate Q-value Functions

The appendix relates k-QBG to earlier approximate Q-value functions by specializing the delay parameter and interpreting the resulting policies. It also connects the delayed-communication formulation to the optimal joint-policy Q-value function.

  • Relation to QPOMDP: For k = 0, k-QBG reduces to QPOMDP because the depth-0 policy is empty and βt becomes a joint action.Substitution into the k-QBG expression yields the QPOMDP-value function.
  • Relation to QBG: For k = 1, k-QBG reduces to regular QBG because the depth-1 policy component reduces to the current action at.The resulting expression is identified as the QBG-value function.
  • Relation to optimal joint-policy Q-value: With k equal to the communication delay h, evaluating all augmented start states corresponds to evaluating all joint policies, whose maximum specifies Q*.The augmented initial policy contains a full length-h joint policy, so the maximizing start state gives the optimal joint-policy value.

A.2.3 Shorter Communication Delays cannot Decrease the Value

The appendix decomposes delayed-communication Q-values into near-term rewards and later expected returns, then proves that reducing communication delay cannot lower the optimal value.

  • Evaluation: The recursive evaluation updates the delayed joint policy after each observation and aggregates observation probabilities over intermediate observations.The delayed policy is represented as a mapping from observation histories to actions.
  • Q-value decomposition: Qk is split into expected reward over stages t through t+k−1 and an expected return from stage t+k through the horizon.The latter is called the “in k-steps” expected return.
  • Theorem: The optimal Q-value Qk is an upper bound to Qk+1 for finite-horizon Dec-POMDPs with k- and k + 1-step delayed communication.Thus, allowing communication one step earlier preserves or increases the optimal value.
  • Proof strategy: The proof establishes the delay ordering by a base case and an induction step over stages.The base case uses equality of future rewards under identical policies near the horizon; the induction step propagates the inequality backward.
Loading 1111.0062v1…