Sufficient Plan-Time Statistics for Decentralized POMDPs

1 Introduction

Multiagent planning under uncertainty has attracted considerable attention in the last decade. In many applications, a team of agents will be facing a great number of uncertaintiese.g., due to unpredictable outcomes of actions, limited and noisy sensors, and failing or absence of communicationthat have to be dealt with in a principled manner. Decentralized partially-observable Markov decision processes (DecPOMDPs) [Seuken and Zilberstein, 2008; Oliehoek, 2012] have been put forward as a framework for such problems. However, optimal decentralized decision making for a team of cooperative agents as formalized in the framework is a notoriously hard problem [Bernstein et al., 2002].

A major obstacle is that the agents only have access to their individual observations during execution. It is currently not known, however, if such individual observation histories can be summarized using more compact (sufficient) statistics, without fixing the policies of the other agents. This means that even if we perform the planning in advance (i.e., in an off-line planning phase) we need to assume that agents base their actions on their entire histories of observations. A consequence is that even during off-line planning the choice of decision rules for different stages is tightly interwoven: as in (single-agent) MDPs [Puterman, 1994], the best future decisions affect optimal decisions for earlier stages, but in DecPOMDPs decisions of earlier stages affect how to act optimally at later stages. That is, the optimal value function for a stage t is known to have a dependence on the policies followed at stages 0, . . . ,t - 1.

This paper makes a contribution to the theory of decentralized POMDPs by showing how this dependence on the 'past joint policy' can be replaced by a probability distribution over joint action-observation histories, or a joint distribution over joint observation histories and states. Thereby, it introduces sufficient plan-time statistics for the past joint policy. We show how the optimal value functions can be formulated in terms of these statistics and prove their correctness, hence establishing the sufficiency of the statistics. Moreover, we also show how these results can be extended to settings with kstep delayed communication. In an empirical evaluation, we investigate the potential for practical implications in a number of benchmark problems, showing that in certain problems the use of sufficient statistics can allow for a much more compact representation of the optimal value function. Additionally, a new sufficient statistic-based pruning technique for heuristic search methods is shown to have the potential to improve planning efficiency, although it does not directly address the bottleneck of current state-of-the-art methods. Finally, we discuss avenues for future research opened by the identification of the proposed plan-time statistics.

This paper is organized as follows. First, in Section 2, we provide the necessary background on Dec-POMDPs and their value functions. The main contribution, the identification of sufficient statistics is presented in Section 3. Section 4 extends these results delayed-communication settings. The empirical evaluation is described in Section 5. Finally, Section 6 discusses opportunities for future work, and Section 7 concludes.

2 Background

Here we provide a concise review of the necessary background on Decentralized POMDPs and their value functions. For a more extensive introduction see [Oliehoek, 2012].

2.1 Dec-POMDPs

A Dec-POMDP is a model for multiagent planning under uncertainty, in which, at every time step or stage, each agent selects an action based on its individual observations (we assume no communication unless mentioned explicitly).

Definition 1 (Dec-POMDP). A decentralized partially observable Markov decision process (Dec-POMDP) is a tuple 〈D,S,A,T,R,O,O,h,b0〉, where

• D = {1, . . . ,n} is the set of n agents,
• S is the finite set of states s,
• A is the set of joint actions a = 〈a1, . . . an〉,
• T is the transition function that specifies Pr(st+1|st,at),
• R(s,a) is the immediate reward function,
• O is the set of joint observations o = 〈o1, . . . ,on〉,
• O the observation function: Pr(ot+1|at,st+1),
• h is the horizon of the problem,
• b0 ∈ △(S), is the initial state distribution at time t = 0.

The goal in Dec-POMDPs is to find an optimal joint policy π∗ that maximizes the expected sum (over stages) of rewards. A key difficulty that sets Dec-POMDPs apart from frameworks as multiagent MDPs [Boutilier, 1996], is that this joint policy is decentralized: it is a tuple 〈πi, . . . ,πn〉 such that the individual policy πi of every agent i maps individual observations histories (OH) ⃗oi, t = (oi,1, . . . ,oi,t) to actions πi(⃗oi, t) = ai,t. The joint OH is denoted ⃗ot = 〈⃗o1, t, . . . ,⃗on, t〉. We also consider stochastic policies, which map from action-observation histories (AOH) ⃗ θi, t = (ai,0,oi,1, . . . ,ai,t-1,oi,t) to probability distributions over actions: πi(ai,t|⃗ θi, t). Joint AOHs are denoted ⃗ θt .

A policy is a sequence πi = (δi,0, . . . ,δi,h-1) of decision rules that map length-t observation histories to actions δi,t(⃗oi, t) = ai,t. We also consider stochastic decision rules δi,t(ai,t|⃗ θi, t). A joint decision rule δt specifies a decision rule for each agent. We define a joint policy that is partially specified ϕt = (δ0, . . . ,δt-1) as the past joint policy at stage t.

2.2 Optimal Value Functions

As for MDPs [Puterman, 1994; Bertsekas, 2005] and POMDPs [Kaelbling et al., 1998; Spaan, 2012], for DecPOMDPs, it is possible to identify optimal value functions. To define them, we will need the following preliminary definitions:

Theorem 1 ([Oliehoek et al., 2008b]). The optimal value function for a Dec-POMDP is defined as

(for the last stage the second term is omitted) with ϕt+1 = (ϕt,δt) the past joint policy formed by concatenating ϕt and δt. This equation in turn defines the optimal decision rule via

A number of remarks are in order:

• Note that (2.5) defines δ∗ t+1 in (2.3).
• In contrast to other descriptions, this set of equations, referred to as the 'sequentially rational' optimal value function, determines the optimal value also for joint AOHs that will never be realized under an optimal joint policy [Oliehoek et al., 2008b].
• Here, we follow the notation of [Oliehoek, 2010; 2012], which makes explicit the dependence on b0. The definitions of (2.1), (2.2) used here are modified to allow for stochastic policies.
• While the above formulations do not resemble traditional Q-function for MDPs, the use of the letter 'Q' can understood by interpreting δt as an action in a meta-level MDP for the planning process [Oliehoek, 2010]. This meta-MDP has 'states' (b0,ϕt) with values Vt(b0,ϕt) corresponding to the maximum of (2.5).

Even though the above description is (relatively) concise, using these equations to compute the optimal joint policy is cumbersome, as it requires evaluating (2.4), (2.5) for all past joint policies ϕh-1 at the last stage. As such, even if the maximization in (2.5) could be performed efficiently, this algorithm would at best gain one horizon on brute force search. Therefore, in practice, researchers have resorted to heuristic search over this space of joint policies [Szer et al., 2005; Oliehoek et al., 2013], dynamic programming [Hansen et al., 2004; Boularias and Chaib-draa, 2008; Amato et al., 2009] or approximate methods [Nair et al., 2003; Emery-Montemerlo et al., 2004; Oliehoek et al., 2008a; Seuken and Zilberstein, 2008; Kumar and Zilberstein, 2010; Wu et al., 2010].

3 Sufficient Plan-Time Statistics

In this section we present our main contribution: the identification of sufficient statistics of the past joint policy for DecPOMDPs. That is, we show how the equations in Theorem 1 can be reformulated such that they no longer depend on the past joint policy ϕt, but rather on a sufficient statistic σt that summarizes it. Since many ϕt may correspond to the same statistic, this can lead to substantially more compact representations of the optimal value function.

3.1 Statistics for General Policies

Although it is well-known that a Dec-POMDP has at least one deterministic optimal joint policy, there is no reason to exclude the more general case of stochastic policies from the description of optimal value functions. Moreover, this assumption will lead to simplest description of a sufficient statistic σt as follows.

Definition 2 (Sufficient statistic for general policies). The sufficient statistic for a general ϕt, assuming b0 is known, is a the distribution over joint AOHs: σt(⃗ θt) ≜ Pr(⃗ θt|b0,ϕt).

Given this definition, we will now posit the equations that are the equivalent of Theorem 1. The proof of their correctness follows. The optimal value can be expressed as

with the updated statistic-note ⃗ θt+1 = (⃗ θt,at,ot+1)-

Optimal decision rules can be derived from

We formally proof the correctness of the above equations, starting with the sufficiency of σt for predicting the optimal value Qt(b0,ϕt,⃗ θt,δt).

Theorem 2. For all ϕt, the distribution over AOHs σt(⃗ θt) is sufficient to predict the optimal value:

Proof. The proof is listed in the appendix.

The following conclusions follow immediately.

Corollary 1. The non-history-based 'meta MDP' Q-functions given by (2.4) and (3.3) are identical: Qt(b0,ϕt,δt) = Qt(b0,σt,δt).

Proof. This follows directly from Theorem 2 and the definitions of the 'meta MDP' Q-functions in (2.4) and (3.3).

Corollary 2. The system of equations given by (3.1) and (3.4) express the optimal value function.

Proof. This follows directly from their equality to equations (2.3) and (2.5).

3.2 Deterministic Policies

The above definition of the statistic σt leads to the most straightforward formulation. However, in the context of deterministic policies the statistic is not directly useful; when restricting to deterministic policies, per definition, each ϕt induces a different σt(⃗ θt). In this sub-section, we fix this problem by introducing a second statistic that additionally takes away the dependence on the initial belief b0.

Definition 3 (Sufficient statistic for deterministic policies). The sufficient statistic for a tuple (b0,ϕt), with ϕt deterministic, is a the distribution over joint OHs and states: σt(st,⃗ot) ≜Pr(st,⃗ot|b0,ϕt).

In the following, we will also write σt(st|⃗ot) and σt(⃗ot) for the conditional and marginal computed from σt. Again, we will need preliminary definitions for the rewards and observation probabilities:

(3.6)

The next statistic (a function of σt and δt) is given by

We are now in a position to give optimal value functions based on this new sufficient statistic.

Theorem 3. Using the sufficient statistic for deterministic past joint policies, the optimal value function of a finitehorizon Dec-POMDP can be written as

where optimal decision rules are defined via

Proof. The proof is similar to that of Theorem 2. A sketch of the proof is in the appendix.

3.3 Restricted-length Policies

In the equations for the optimal value function, the role of the observation history is purely in terms of providing accurate distributions over states σt(st|⃗ot) and providing the basis for action selection. In cases where it is possible to restrict the class of considered policies to policies that map from the last k observations, it is possible to maintain more compact statistics σt(st,⃗o k t ) over length-k observation histories. 1

For Dec-POMDPs, such a restriction in general is suboptimal: the most accurate distribution σt(st|⃗ot) over states is given by the complete history, and as such, policies should in general condition on the entire history. Nevertheless, there may be situations where we can prove that conditioning on full history is not necessary. An example is the sub-class of transition independent Dec-MDPs (TI-Dec-MDPs) [Becker et al., 2003]. For such problems, it can be shown that an optimal joint policy exists in decentralized mappings from

1 The technicalities of such a statistic are similar to the situation of k-step delayed communication (treated in the next section) with the difference that ot-k+1 is not observed, but must be averaged over: σt+1(st+1,⃗o k t+1) = ∑st ∑ot-k+1 Pr(st+1,ot+1|st,δk t (⃗o k t ))σt(st,⃗o k t ).

the last (k = 1) observation to actions. As such, it is possible to maintain a more compact statistic σt(st,ot). Furthermore, since in TI-Dec-MDPs the joint observation identifies the state and vice versa, this statistic simply reduces to a distribution over states σt(st), and therefore corresponds exactly to the so-called state-occupancy that was recently identified as a sufficient statistic for planning for TI-Dec-MDPs and that has led to significant improvements in their solutions [Dibangoye et al., 2012].

4 Delayed Communication

In this section we consider Dec-POMDPs with k-step delayed communication. That is, we assume that, at every stage t, all the agents broadcast their individual observations, but that this information only arrives at stage t+k. The descriptions of optimal value functions introduced in Section 3 can be generalized to delayed communication. Essentially, this integrates the insight of the previous section in existing descriptions of optimal value functions for delayed communication [Ooi and Wornell, 1996; Oliehoek et al., 2008b]. In this section we will concentrate on the deterministic past joint policy formulation, but extension to stochastic policies follows trivially.

Delayed Communication Value Functions. We will follow the description of value functions given in [Oliehoek et al., 2008b]. The main idea behind the descriptions of value functions for Dec-POMDPs with k-step delayed communication is that every stage t is similar to a horizon-k DecPOMDP: since the communicated individual observations of stage t-k will have arrived, each agent knows the joint AOH ⃗ θt-k and can compute bt-k, the distribution over states at that stage:

This distribution serves the same role as the initial belief b0 in a Dec-POMDP without communication. In addition, each agent will know the sequence ⃗o k i,t = (oi,t-k+1, . . . ,oi,t) of its last k private observations. Therefore, to act at stage t, the agents have to use a joint decentralized decision rule δk t = 〈δk 1,t , . . . ,δkn,t 〉 that maps length-k observation histories to joint actions δk t (⃗o k t ) = at. However, the optimal δk t depends on ϕkt , the past joint policy since stage t - k. This ϕkt fulfills the same role as ϕt in the normal Dec-POMDP formulation and also has similar shape: it simply is a tuple of horizon-k policy trees, one for each agent.

Note that we still assume that planning takes place in advance, so each agent will be able to determine what ϕkt is (given ⃗ θt-k). This means that we can form the length-(k+1) policy ϕk+1 t = (ϕkt ,δk t ) in exactly the same way as for normal Dec-POMDPs. The difference, however, is in the way it will be used, rather than directly plugging ϕk+1 t in the value function for stage t + 1 (cf. equation 2.3), it will be used to track the length-k past joint policy at the next stage. In particular, at the next stage, each agent will receive ot-k+1 (via communication). Therefore they will know which part of ϕk+1 t has been executed during the last k stages t-k+1, . . . ,t and they discard the part not needed further. We will write discarding the part of ϕk+1 t that is not consistent with ot-k+1 as

The optimal value function for a finite-horizon DecPOMDP with k-step delayed, cost and noise free communication [Oliehoek et al., 2008b] is given by:

where bt is the joint belief that results from bt-k and ⃗ θkt , and where the definitions of R(. . . ) and Pr(ot+1| . . . ) follow from trivial adaptations of equations (2.1) and (2.2). The next-stage length-k past joint policy is ϕkt+1 is given by (4.1). To better interpret (4.2), it is informative to compare this equation to the equation for Dec-POMDPs without communication (2.3). Analogous to that setting, also in the case of k-step delayed communication, we can define the optimal decision rules via:

(4.3)

Sufficient Statistics. While the number of past joint policies considered is only doubly exponential in k and not the full horizon, this number is very large for longer delays. As such, also in this case, having descriptions of value functions based on sufficient plan-time statistics can be valuable.

Definition 4 (Sufficient statistic for k-step delayed communication). A sufficient statistic for a tuple 〈bt-k,ϕkt 〉, with ϕkt deterministic, is the distribution over joint OHs and states: σt(st,⃗o k t )≜Pr(st,⃗o k t |bt-k,ϕkt ).

This allows us to define R(σt,⃗o k t ,δk t ) and Pr(ot+1|σt,⃗o k t ,δk t ), analogous to (3.5), (3.6). The next statistic is a function of σt, δt and the communicated joint observation ot-k+1. Let ⃗o k t = (ot-k+1,⃗o k-1 t ) and ⃗o k t+1 = (⃗o k-1 t ,ot+1), then the updated statistic is given by

with P(ot-k+1|σt) a normalization constant.

Theorem 4. The optimal value function of a Dec-POMDP with k-step delayed communication can be written as

where the next-stage statistic σt+1 is as defined above, and where optimal decision rules are defined via

Proof. The proof-omitted due lack of space-shows that Qt (σt,⃗o k t ,δk t ) = Qt (bt-k,ϕkt ,δk t ) following the the same steps as the proof of Theorem 2.

5 Experiments

Here we report on an empirical evaluation directed at investigating the potential practical impact of the proposed sufficient statistics. A potential important consequence of using sufficient statistics is that it allows representing the optimal value function more compactly. However, the extent to which this is the case depends on how many ϕt map to the same distribution σt(st,⃗ot). Therefore, to investigate this potential in practice, we have examined the number of unique distributions σt(st,⃗ot) in a number of standard benchmark problems. 2

The results are shown in Table 1. It shows the number of past joint policies ϕt for different stages t, as well as the number of unique distributions σt(st,⃗ot) that those histories induce, given the initial belief b0. Entries marked '-' ran out of time (>1h), and marked 'X' ran out of memory (2GB). This clearly indicates a limitation of using sufficient statistics: caching the distributions themselves can take a considerable amount of memory. However, the results also show that there can be considerable reductions in size, although this is very much problem dependent. For instance, firefighting (FF) does not allow for any reduction: every ϕt induces a unique statistic σt. In contrast, tiger and hotel1 allow for a reductions of respectively three and four orders of magnitude. Note that these result clearly illustrate that the reduction due to sufficient statistics is quite different from the clustering technique used in [Oliehoek et al., 2009]: it is not necessarily the case that problems that exhibit high clustering (such as broadcast channel and recycling) also lead to the highest reductions by using sufficient statistics. 3

Since certain problems (tiger and hotel1) give large reductions, we examined whether it is possible to use these statistics to increase performance of policy search for these problems. In particular, we augmented the state-of-the-art GMAA*-ICE solver [Oliehoek et al., 2013] with sufficient statistic-based pruning (SSBP): a procedure that checks if the statistic σt induced by the current ϕt was already encountered, allowing for pruning in the search. Effectively this transforms the GMAA* search tree into a DAG: when reaching a node that was visited before, it is only further expanded if the value along the new path is higher than before (i.e., the cost of reaching it is lower). We compare the number of nodes that are created when pruning based on σt versus when not.

2 Available from http://www.masplan.org/.

3 Clustering tests if P (s,⃗o-i|⃗oi,ϕ) = P (s,⃗o-i|⃗o ′ i ,ϕ) and merges OHs, thereby collapsing many extensions of ϕ. SSBP tests P(s,⃗o|ϕ) = P(s,⃗o|ϕ′ ) and avoids going down a branch ϕ completely, provided that it went down an equivalent branch ϕ′ earlier.

The results are shown in Table 2. It clearly shows that when using QMDP, many nodes can be pruned. This translates to improvements in run time, e.g., 1.5s vs 39.9s for QMDP horizon 4. When using tighter heuristics as QBG, however, we see that these are already perform very well at guiding the search over past joint policies, such that the effect of using sufficient statistics is limited. For longer horizons, however, these heuristics are often difficult to compute and lose their tightness, meaning that there might still be a practical role for sufficient statistics in heuristic search algorithms. However, the current bottleneck that these methods experiencethe complexity of expansion of the nodes for later stageswill need to be tackled with a different approach.

6 FutureWork

This work lies the foundation for a number of future research directions. Potentially a great advantage of using sufficient statistics over past joint policies is that the difference between two statistics can be measured. An important direction of research is therefore to see if a bound on the difference in statistics can imply a bound on difference in value. This would directly provide a starting point for developing approximate versions of Dec-POMDP algorithms, which can give guarantees on the error. In fact, [Dibangoye et al., 2013] simultaneously to this work identified a similar statistic of the form σt(s,⃗ θt), and showed that the value function is piecewise linear and convex over this space, a property they show that can be exploited very effectively by adapting POMDP solution methods. Future work, should determine whether exploiting the same property of the more compact σt(s,⃗ot) statistic presented here can lead to further improvements.

Another promising direction of research is enabled by the insight that restricted-length policies allow for more compact statistics. This means that not only the maximization (3.10) becomes more tractable, but also that there is a larger chance that past joint policies will result in the same statistic. As such, artificially restricting the complexity of the policies gains traction in two complementary ways. Future research should investigate if this can be leveraged by searching in spaces of policies of incrementally increasing complexity.

7 Conclusions

This paper introduced sufficient plan-time statistics for DecPOMDPs that allow for more compact description of the optimal value function. We formally proved that these descriptions are correct, i.e., the proposed statistics are indeed sufficient to predict the future value, and extended these descriptions to the case of k-step delayed communication in DecPOMDPs. An empirical evaluation investigated the numerical impact on the description of optimal value functions for a number of benchmark problems, showing a potentially large, but problem-dependent reduction in size. Moreover, it was demonstrated that using sufficient statistic-based pruning can potentially speed up heuristic search for Dec-POMDPs, but that they do not address the current bottleneck for such methods. Finally, we discussed a number of promising directions of future work that are enabled by this work.

Acknowledgments

I want to thank Christopher Amato for valuable comments. Supported in part by NWO CATCH project #640.005.003.

A Appendix

Proof of Theorem 2

The proof is by induction over the stages of the problem.

Base Case. For the last stage t = h-1, we have that

Induction Hypothesis. Per induction hypothesis, we assume that, for stage t + 1, σt+1 is a sufficient statistic. I.e., 'past-joint-policy form' Q-values are equal to 'statistic form':

Induction Step. We need to show that for stage t, σt is a sufficient statistic. That is, if Pr(⃗ θt|b0,ϕt) = σt(⃗ θt) then the Q-values are equal:

Proof: We assume that ∀⃗ θt [Pr(⃗ θt|b0,ϕt) = σt(⃗ θt)] (Assumpt.1). Now we need to show the identity of the Q-values of the r.h.s. of (A.2). Using their respective definitions (2.3) and (3.1), we need to show

This is the case if

1. the optimal next decision rule under 'past-joint-policy form', δpp∗ t+1 , and the optimal one under 'sufficientstatistic form', δsg∗ t+1 , are equal.

since then the IH applies. We first proof item 2):

Using this result, we prove item 1) via the I.H.: δpp∗ t+1 ≜

Therefore (A.3) holds true, proving the induction step.

Proof Sketch of Theorem 3

The proof strategy is-similarly to that of Theorem 2to show that, for all deterministic ϕt, for all b0,δt, Qt(σt,⃗ot,δt) = Qt(b0,ϕt,⃗ θt,δt), with ⃗ θt the joint AOH resulting from ⃗ot and ϕt. In this case, to show the equality of (2.3) and (3.8) it is necessary to additionally show that the immediate reward terms (2.1), (3.5), and observation probability terms (2.2), (3.6) are equal. This requires showing that, for all ⃗ot, for the ⃗ θt resulting from ⃗ot and ϕt, Pr(st|b0,⃗ θt) = σt(st|⃗ot). Moreover, to prove the induction step we will need to show that Pr(⃗ θt|b0,ϕt) = σt(⃗ot). We prove these additional requirements here, starting with the latter. For a deterministic ϕt we can write Pr(⃗ θt|b0,ϕt) = Pr(⃗ot|b0,ϕt)C(⃗ θt,ϕt), where C(⃗ θt,ϕt) is a term that is 1 iff ⃗ θt is consistent with ϕt. Clearly, since σt(⃗ot)≜Pr(⃗ot|b0,ϕt) and since (for ⃗ θt resulting from⃗ot) C(⃗ θt,ϕt) = 1 we can conclude Pr(⃗ θt|b0,ϕt) = σt(⃗ot). Using this result, we can write the joint distribution Pr(st,⃗ θt|b0,ϕt)

from which we can deduce that Pr(st|b0,⃗ θt)

for all ⃗ θt consistent with ϕt. Given these results, the remainder of the proof follows the proof of Theorem 2.