Factored Upper Bounds for Multiagent Planning Problems under Uncertainty with Non-Factored Value Functions

1 Introduction

Planning for multiagent systems (MASs) under uncertainty is an important open research problem in artificial intelligence. The decentralized partially observable Markov decision process (Dec-POMDP) is a framework for addressing such problems. Many recent approaches to solving Dec-POMDPs propose to exploit locality of interaction [Nair et al., 2005], also referred to as value factorization [Kumar et al., 2011]. However, without making very strong assumptions, such as transition and observation independence [Becker et al., 2003], there is no strict locality: in general the actions of any agent may affect the rewards received in a different part of the system. For large MASs, several heuristic approaches have been proposed [Yin and Tambe, 2011; Kumar et al., 2011; Velagapudi et al., 2011; Varakantham et al., 2012; Oliehoek et al., 2013b; Wu et al., 2013; Varakantham et al., 2014], which come without guarantees, however.

In this work, we mitigate this issue by proposing a novel family of techniques that can be used to provide upper bounds on the performance of large factored Dec-POMDPs. In addition to 1) quantifying the performance gap of heuristic methods, computing upper bounds is important for other reasons:

∗An extended version of this paper is available on ArXiv [Oliehoek et al., 2015].

Stefan J. Witwicki

Swiss Federal Institute of Technology (EPFL) stefan.witwicki@epfl.ch

Knowledge of performance gaps 2) is crucial for researchers to direct their focus to promising areas and 3) sheds light on which problems are easier to approximate than others. 4) Last, but not least, these bounds serve as admissible heuristics for current and future branch&bound search methods.

Computing upper bounds on the achievable value of a planning problem typically involves relaxing the original problem by making some optimistic assumptions. By exploiting the fact that transition and observation dependence leads to a value function that is additively factored into a number of small components, researchers have designed techniques for computing upper bounds in so-called Networked Distributed POMDPs (ND-POMDPs) with many agents [Varakantham et al., 2007; Marecki et al., 2008; Dibangoye et al., 2014]. Unfortunately, the assumption of factored value functions narrows down the applicability of such models, and no techniques for computing upper bounds for more general factored Dec-POMDPs with many agents are currently known.

We address this problem by proposing a general technique for computing what we call influence-optimistic upper bounds. These are upper bounds on the achievable value in large-scale MASs formed by computing local influenceoptimistic upper bounds on the value of sub-problems that consist of small subsets of agents and state factors. The key idea is that if we make optimistic assumptions about how the rest of the system will influence a sub-problem, we can decouple it from the rest of the problem, and effectively compute a local upper bound on the achievable value. Finally, we show how these local bounds can be combined into a global upper bound. In this way, a major contribution of this paper is that it shows how we can compute factored upper bounds for models that do not admit factored value functions.

We empirically evaluate the quality guarantees the bounds provide for heuristic methods and, in an extended version [Oliehoek et al., 2015], use our bounds to prune in an A* search. The proposed bounds give meaningful quality guarantees for factored Dec-POMDPs with hundreds of agents. This is a major accomplishment since previous approaches that provide guarantees 1) have required value factorization [Becker et al., 2003; 2004; Varakantham et al., 2007; Dibangoye et al., 2014] or specific interaction topologies [Witwicki, 2011], and 2) have not scaled beyond 50 agents. In contrast, this paper demonstrates quality bounds in settings of hundreds of agents that all influence each others' actions.

2 Background

We focus on Dec-POMDPs where the transition and observation models can be represented compactly as a two-stage dynamic Bayesian network (2DBN) [Boutilier et al., 1999]:

Definition 1. A factored Dec-POMDP is a tuple M = 〈D, A, O, X , T, O, R, b0 〉, where:

• D = {1, . . . , |D|} is the set of agents.
• A = ⊗i∈D Ai is the set of joint actions a.
• O = ⊗i∈D Oi is the set of joint observations o.
• X = {X1 , . . . , Xm} is a set of state variables, or factors, that determine the set of states S = ⊗mk=1 Xk .
• T(s′ |s, a), the transition model specified by a set of conditional probability tables (CPTs), one for each factor.
• O(o|a, s′ ), the observation model: a CPT per agent.
• R is a set of local reward function.
• b0 is the (factored) initial state distribution.

Each local reward function Rl has a state factor scope X(l) ⊆ X and agent scope D(l) ⊆ D over which is it is defined: Rl (xX(l) , aD(l), x′X(l) ) ∈ R. These local reward functions form the global immediate reward function via addition. We slightly abuse notation and overload l to denote both an index into the set of reward functions, as well as the corresponding scopes:

For instance, Fig. 1 shows the FIREFIGHTINGGRAPH (FFG) problem [Oliehoek et al., 2013b], which we adopt as a running example. This problem defines a set of |D| + 1 houses, each with a particular 'fire level' indicating if the house is burning and with what intensity. Each agent can fight fire at the house to its left or right, making observations of flames (or no flames) at the visited house. Each house has a local reward function associated with it, which depends on the next-stage fire-level, 1 as illustrated in Fig. 3(left) which shows the 2DBN for a 4-agent instantiation of FFG. The figure shows that the connections are local but there is no transition independence [Becker et al., 2003] or value factorization [Kumar et al., 2011]: all houses and agents are connected such that, over time, actions of each agent can influence the entire system. While FFG is a stylized example, such locallyconnected systems can be found in applications as traffic control or communication networks.

This paper focuses on problems with a finite horizon h such that t = 0, . . . , h - 1. A policy πi for an agent i specifies an action for each observation history ⃗o t i = (o1i , . . . , oti ). The task of planning for a factored Dec-POMDP entails finding a joint policy π = 〈π1, . . . , π|D|〉 with maximum value, i.e., a maximum expected sum of rewards: V (π) ≜ E[∑h-1 t=0 R(s, a, s′ ) | b0 , π]. Such an optimal joint policy is denoted π∗ . 2

1 FFG has rewards of form Rl (x′l), but we support Rl (xl, al, x′l) in general.

As explained in the introduction, computing upper bounds is useful for many reasons. For ND-POMDPs, this is tractable for problems with many agents [Varakantham et al., 2007; Dibangoye et al., 2014]. 3 However, these methods rely on the true value function being factored as the sum of a set E of local value components: V (π) = ∑e∈E Ve(πe), where πe is the local joint policy of the agents that participate in component e. An upper bound is easily constructed as the sum of local upper bounds: ˆ V = ∑e∈E ˆ Ve. The key point is that computing the local upper bounds ˆ Ve is easy because the original problem has a factored value function: each component e can be upper bounded in isolation.

3 Global Upper Bounds

In this paper, we propose a class of factored upper bounds, which we call influence-optimistic upper bounds (IO-UBs), for factored Dec-POMDPs that do not have a factored value function. This is an important contribution, since currently no methods to compute upper bounds for such problems are available. The overall approach that we take is to divide the problem into sub-problems (SPs, defined in Section 4), compute overestimations of the achievable value for each of these sub-problems and combine those into a global upper bound.

Combining the local bounds into a global bound is similar to existing methods for computing upper bounds for NDPOMDPs. The basic idea is to apply a non-overlapping decomposition C (i.e., a partitioning) of the reward functions R of the original factored Dec-POMDP into SPs c ∈ C, and to compute a local IO-UB ˆ V IO c for each (with the methods proposed in Section 4). The global influence-optimistic upper bound is then given by: ˆ V IO ≜ ∑c∈C ˆ V IO c .

We illustrate the construction of a global upper bound ˆ V for the 6-agent FFG in Fig. 2, which shows the original problem (top row) and two possible decompositions in SPs. The second row specifies a decomposition into two SPs, while the third row uses three SPs. The illustration clearly shows how (in this problem) a decomposition eliminates certain agents completely and replaces them with optimistic assumptions: E.g., in the second row, during the computation of ˆ V IO c for both SPs (c = 1, 2) the assumption is made that agent 3 will always fight fire in SP c. Effectively, the bounds assume that agent 3 fights fire at both house 3 and house 4 simultaneously (and hence is represented by a superhero figure). Fig. 2 also illustrates that, due to the line structure of FFG, there are two types of SPs: 'internal' SPs which make optimistic assumptions on two sides, and 'edge' SPs that are optimistic on just one side.

2 We omit the '*' on values; all values are assumed to be optimal with respect to their given arguments.

3 It would also be possible to compute UBs for TD-POMDPs [Witwicki and Durfee, 2010] with many agents, but here too, existing techniques would require a factored value function, which in turn requires very specific restrictions: interactions must be directed and agents can only have a few interaction ancestors.

To prove correctness of this upper bounding scheme, we define Vc(π) as the value realized for Rc, the reward components modeled in SP c, under joint policy π. Given the policies of other agents π-c, the best-response value of c is V BR c (π-c)≜maxπc Vc(πc, π-c). Finally, the locallyoptimal value for an SP c,

is the local value, considering only the rewards Rc, that can be achieved when all agents use a policy selected to optimize this local value. We denote the maximizing argument by πLO -c .

Theorem 1. Let C be a partitioning of R into SPs. If ∀c∈C ˆ V IO c ≥ V LO c then the global IO-UB is in fact an upper bound to the optimal value ˆ V IO ≥ V ∗ .

Proof. We have ˆ V IO ≜ ∑c∈C ˆ V IO c ≥ ∑c∈C V LO c ≜ ∑c∈C maxπ-c V BR c (π-c) = ∑c∈C maxπ Vc(πc, π-c)≥ maxπ ∑c∈C Vc(πc, π-c) = V (π∗ ). The last equality holds because C is a partitioning of the reward functions.

4 Local Upper Bounds

In this section we present our main technical contribution: the machinery to compute a number of influence-optimistic upper bounds (IO-UBs) for the value of sub-problems. We first introduce sub-problems formally and then move to techniques for upper bounding their local values, based on theory from influence-based abstraction. While not further explored in this paper, we point out that these techniques can be trivially modified to compute 'pessimistic' influence (i.e., lower) bounds, which could be useful in competitive settings, or for risk-sensitive planning [Marecki and Varakantham, 2010].

Here we introduce two local bounds, based on combining influence-optimism with solution methods for multiagent POMDPs (MPOMDPs) [Messias et al., 2011] and DecPOMDPs respectively. In the extended version, we also introduce a bound based on multiagent MDPs [Oliehoek et al., 2015]. While this latter bound can be less tight (as demonstrated in the experiments), it is computationally cheaper.

4.1 Sub-Problems

The notion of an SP generalizes the concept of a localform model [Oliehoek et al., 2012] to multiple agents: A sub-problem (SP) Mc of a factored Dec-POMDP M is a tuple Mc = 〈M,D′ ,X ′ ,R′ 〉, where D′ ⊂ D, X ′ ⊂ X, R′ ⊂ R denote subsets of agents, state factors and local reward functions, respectively. An SP inherits many features from M: we can define local states xc ∈ ⊗X∈X ′ and the subsets D′ ,X ′ ,R′ induce local joint actions Ac = ⊗i∈D′ Ai, observations Oc = ⊗i∈D′ Oi, and rewards Rc(xc, ac, x′c ) ≜ ∑l∈R′ Rl (xl, al, x′l ).

However, this is generally not enough to end up with a fully specified (smaller) factored Dec-POMDP. This is illustrated in Fig. 3(left), which shows an SP of FFG involving two agents: state factors X ∈ X ′ (in this case Xi and Xi+2 ) can be the target of arrows pointing into the sub-problem from the non-modeled (dashed) part. 4 We refer to such factors as non-locally affected factors (NLAFs) and denote them xnkc , where k indexes the factor. The other state factors in X ′ are referred to as only-locally affected factors (OLAFs) xlkc . The figure shows that the transitions are not well-defined since the NLAFs depend on the sources of the highlighted influence links. We refer to these as influence sources uc = 〈yu , au 〉 (in this case yu = 〈Xi-1 , Xi+3 〉 and au = 〈ai-1 , ai+2 〉).

4.2 Influence-Augmented SPs

A local-form model can be transformed to an influenceaugmented local model, which captures the influence of nonmodeld parts of the environment [Oliehoek et al., 2012]. We extend this approach to SPs, leading to influence-augmented sub-problems (IASPs). The construction of an IASP consists of two steps: 1) capturing the influence of the non-modeled parts (given π-c, the policies of non-modeled agents) in an incoming influence point I→c(π-c), and 2) using this I→c to create a model with a transformed transition model TI→c and no further dependence on the external problem.

4 We assume that the scopes of the observation CPTs for the included agents are fully contained within the SP, and similarly for the included reward factors. This is not a strong assumption, since situations with arrows pointing to rewards or observations can be modeled by introducing auxiliary state variables. These restrictions generalize previous notions of observation and reward independence [Becker et al., 2003; Nair et al., 2005] (we allow overlap on state factors that can be influenced by the agents themselves). We do not assume transition independence, nor do we assume any of the transition-decoupling (i.e., TD-POMDP [Witwicki and Durfee, 2010]) restrictions.

Step 1) An incoming influence point can be specified as an incoming influence I t→c for each stage: I→c = (I 1→c , . . . , I h→c ). Each such I t+1 →c corresponds to the influence that the SP experiences at stage t + 1, and thus specifies the conditional probability distribution of the influence sources uc = 〈yu , au 〉 at stage t. Assuming that the influencing agents use a deterministic policy πu, I t+1 →c is given by I(uc |Dc ) = ∑⃗ou 1{au=πu(⃗ou )} Pr(yu , ⃗ou |Dc , b0 , π-c), with 1{·} the Kronecker Delta function, and Dc the d-separating set for I t+1 →c : the history of a subset of all the modeled variables that d-separates the modeled variables from the nonmodeled ones (see [Oliehoek et al., 2012] for details).

Step 2) defines the IASP MIA c = 〈Mc, I→c〉 for an SP Mc = 〈M,D′ ,X ′ ,R′ 〉 as a factored Dec-POMDP with the following components. The set of state factors ¯ X = X ′ ∪ {Dc } is such that states ¯xc = 〈xc ,Dc 〉 specify a local state of the SP, as well as the d-separating set Dc for the next-stage influences. Only the agents (implying their actions and observations) and rewards from c participate: ¯D = D′ and ¯R = R′ . For all OLAFs xkc we take the CPTs from the factored Dec-POMDP M, but for all NLAFs we take their induced CPTs [Oliehoek et al., 2012], leading to an influence-augmented transition model which is the product of CPTs of OLAFs and NLAFS:

(Note that xc , ac , x′c and Dc together uniquely specify D′c ). The observation model ¯O follows directly fromO (fromM). Fig. 3(right) illustrates the IASP for FFG.

Theorem 2. Vc(I→c(π-c)), the value of an optimal solution of the IASP for influence point I→c(π-c), equals the bestresponse value: V BR c (π-c) = Vc(I→c(π-c)).

Proof. The proof by Oliehoek et al. [2012] extends to multiagent SPs.

4.3 AnMPOMDP-Based Upper Bound

Via (1), it is clear that V LO c corresponds to the value of the locally optimal influence: V LO c = Vc(I→c(πLO -c )). As such, it is optimistic about the influence, but maintains that the influence is feasible. Computing this value can be difficult, since computing influences and subsequently constructing and optimally solving an IASP can be very expensive due to the large number of augmented states ¯xc = 〈xc ,Dc 〉. However, it turns out computing upper bounds to V LO c can be done more efficiently, without even constructing the IASPs: we can directly use the (under-specified) SPs and modify the 'backup operators' used to compute the optimal value function to make optimistic assumptions about the non-specified influence sources.

The first such upper bounding method we introduce, influence-optimistic Q-MPOMDP (IO-Q-MPOMDP), treats the SP under concern as an (under-specified) multiagent POMDP (MPOMDP) [Messias et al., 2011]. An MPOMDP is partially observable, but assumes that the agents can freely communicate their observations, such that the problem reduces to a centralized one in which a single decision maker (representing the team of agents) takes joint actions, and receives joint observations. The optimal value for an MPOMDP is analogous to that of a POMDP: Q(b, a) = R(b, a) + ∑o Pr(o|b, a)V (b′ ), where b′ is the joint belief resulting from a Bayes update of b given a and o.

In case that the influence on an SP is fully specified, POMDP techniques can be readily applied to the IASP. However, we want to deal with the case where this influence is not specified. To accomplish this, IO-Q-MPOMDP adds optimistic assumptions on the influences. We propose a formulation that makes use of 'back-projected value vectors': ν ao (s)≜ ∑s′ O(o|a, s′ )T(s′ |s, a)ν(s′ ). (See, e.g., [Spaan, 2012; Shani et al., 2013] for more details.)

The key insight that enables applying influence-optimism to the MPOMDP case is that in this back-projected form we can take the maximum with respect to unspecified influences. We define the influence-optimistic back-projection as:

Comparing this equation to (2), it is clear that this equation is optimistic with respect to the influence: it selects the sources uc in order to select the most beneficial transition probabilities. Since this equation does not depend in any way on the d-separating sets and influence, we can completely avoid generating large IASPs. When combined with an exact POMDP solver, such influence-optimistic back-ups will lead to an upper bound ˆ V P c on the locally-optimal value.

Theorem 3. IO-Q-MPOMDP yields an upper bound on the locally-optimal value: V LO c ≤ ˆ V P c .

Sketch of Proof. The proof shows that for any fixed joint policy πc, the value vectors νP ∈ V and νIO ∈ VIO (computed under regular- and IO back-projections respectively) satisfy: ∀xc maxDc ν(〈xc ,Dc 〉) ≤ νIO(xc ). This implies that, for any I→c, V P I→c (¯bI→c ) ≤ V IO (¯bIO ), provided that the marginal of ¯bI→c coincides with ¯bIO : ∑Dc ¯bI→c (〈xc , Dc 〉) = ¯bIO (xc ), a condition that is satisfied for the initial beliefs.

4.4 ADec-POMDP-Based Upper Bound

The previous approach computes upper bounds by, apart from the IO assumption, additionally making optimistic assumptions on communication capabilities. Here we present a method for computing Dec-POMDP-based upper bounds that, other than the optimistic assumptions about neighboring SPs, makes no additional assumptions. The approach builds on the recent insight [MacDermed and Isbell, 2013; Dibangoye et al., 2013; Oliehoek et al., 2013a] that a DecPOMDP can be converted to a special case of POMDP, 5 and that therefore we can leverage the IO back-projection (3) to compute an UB, ˆ V D c , that we refer to as IO-Q-Dec-POMDP.

5 Oliehoek and Amato [2014] give an overview of this reduction.

In particular, we define the plan-time sub-problem MPT c as the (under-specified) POMDP with states of the form ˇ s = 〈xc , ⃗oc 〉. Each ˇ a corresponds to a local joint decision rule δc in the SP (composed of individual decision rules that map observation histories to actions). Rewards are given by ˇR(ˇ s, ˇ a) = Rc(xc , δc (⃗oc )). There is a single observation ˇO = {NULL} that is received with probability 1 irrespective of the state and action. The horizon is unmodified: ˇh = h. Finally, the transition model is underspecified, since it depends on the non-specified influence sources: ˇ T (ˇ s′ |ˇ s, ˇ a) = Tuc (x′c |xc , δc (⃗oc ), uc )O(oc |δc (⃗oc ), x′c ).

Since this model is a special case of a POMDP, the theory developed in Section 4.3 applies: we can write down the IO back-projection (3) which in this case translates to 6

Theorem 4. IO-Q-Dec-POMDP yields an upper bound to the locally-optimal value: V LO c ≤ ˆ V D c .

Proof. Directly from the applying Theorem 3 toMPT c .

4.5 Complexity Analysis

Due to the maximization in (3) and (4), IO back-projections are more costly than regular (non-IO) back-projections. In particular, the complexity of each backup is multiplied by the number of influence source instantiations |uc |. As such, the relative overhead, when compared to solving the SPs as regular (non-IO) MPOMDPs and Dec-POMDPs, is equal for both methods [Oliehoek et al., 2015].

5 Empirical Evaluation

In order to test the potential impact of the proposed influenceoptimistic upper bounds, we present numerical results in the context of a number of benchmark problems. We compare the influence-optimistic MPOMDP and Dec-POMDP UBs, ˆ V P c and ˆ V D c , as well as the IOmultiagent MDP (MMDP) bound, ˆ V M c , based on the same technique [Oliehoek et al., 2015]. While we focus on the (relative) values found by these heuristics, as the analysis of Section 4.5 indicates that relative timing results follow those of regular (non-IO) MPOMDP and Dec-POMDP methods, we do provide some indicative running times. 7 The extended version [Oliehoek et al., 2015] provides preliminary evidence that our bounds can be used to improved heuristic influence search [Witwicki et al., 2012].

Comparison of Different Bounds. Although the approach described in the paper is general, in the numerical evaluation here we exploit the benchmarks' property that the optimistic influences are easily identified off-line, which allows for the construction of small 'optimistic Dec-POMDPs' (respectively MPOMDPs or MMDPs) without sacrificing in bound quality. E.g., in order to compute the local IQ-QDec-POMDP upper bound for a 3-house FFG 'edge' SP, we define a regular 3-house Dec-POMDP where the transition model for the first house (say Xi in Fig. 3) is modified to account for the optimistic assumption that another (superhero) agent fights fire there and that its neighbor is not burning (i.e., ai-1 = right and Xi-1 = not burning in Fig. 3).

6 Note that O(o′i|ai, x′i) in (3) corresponds to the NULL observation in the PT model, but since the observation histories are in the states, Pr(oc|δc(⃗oc), x′c) comes out of the transition model.

7 All experiments are run on an Intel Xeon E5-2650L, 32GB system making use of one core only.

Fig. 4(top) shows the values for such 'edge' problems. Missing bars indicate time-outs (>4h). As an indication of run time, the |D′ | = 3, h = 5 problem took 2.21s for IO-QMMDP, and 995.28s for IO-Q-Dec-POMDP. The shown values indicate that ˆ V D c , ˆ V P c can be tighter than ˆ V M c in practice. In most cases, the difference between ˆ V D c and ˆ V P c is small, but these could become larger for longer horizons. The same analysis for the ALOHA benchmark [Oliehoek et al., 2013b] gave similar results.

We also compare different types of SPs (internal and edge cases, see Fig. 2) encountered in FFG (h = 4). In addition, Fig. 4(left) also includes-if computable within the allowed time-values of SPs that are 'full' problems (i.e., the regular optimal Dec-POMDP value for the full FFG instance with the indicated number of agents.) These results demonstrate a potentially large effect of influence-optimism: being optimistic at one edge more than halves the optimal cost, and the IO assumption at both edges of the SP leads to another significant reduction of that cost. This is to be expected: the optimistic problems assume that there always will be another agent fighting fire at the house at an optimistic edge, while the full problem never has another agent at that same house. When also taking into account the transition probabilitiestwo agents at a house will completely extinguish a fire-it is clear that the IO assumption should have a high impact on the local value; FFG has a high influence strength.

We devise a modification of FFG where the influence strength can be controlled. In particular, we parameterize the probability that a fire is extinguished completely when 2 agents visit the same house, which is set to 1 in the original problem definition. Lower values of this probability mean that optimistically assuming there is another agent at a house will lead to less advantage, and thus lower influence strength. Fig. 4(right) shows that there is a clear relation between the fire-extinguish probability when two agents fight fire at a house, and the ratio between the 'full' value (the DecPOMDP value) and optimistic value.

Bounding the Error of Heuristic Methods. Here we investigate the ability to provide informative global upper bounds. While the previous analysis shows that the overestimation is quite significant at the true edges of the problem (where no agents exist), this is not necessarily informative of the overestimation at internal edges in decompositions of larger problems (where other agents do exist, even if not superheros). As such, besides investigating the upper bounding capability, the analysis here also provides a better understanding of such internal overestimations.

We use the tightest upper bound we could find by considering different SP partitions, with sizes ranging from |D′ | = 25, and investigate the guarantees that it can provide for transfer planning (TP) [Oliehoek et al., 2013b], one of the methods capable of providing solutions for large factored DecPOMDPs. Since this heuristic method does not provide the exact value of the reported joint policy, the value of TP, V TP , is determined using 10.000 simulations of the found joint policy leading to accurate estimates. To put the results into context, we also show the value of a random policy. Finally, we show (second y-axis in Fig. 5) what we call the empirical approximation factor (EAF): max{ˆ V IO /V TP , V TP / ˆ V IO }, a number comparable to the approximation factors of approximation algorithms [Vazirani, 2001].

Following this methodology, we computed upper bounds for large, horizon h = 4, FFG instances. The computation of the local upper bounds for the largest SPs used (i.e., |D′ | = 5) took 3.31 secs for IO-Q-MMDP and 2696.23s for IO-Q-DecPOMDP. Fig. 5 shows the results that indicate that the upper bound is relatively tight: the solutions found by TP are not far from the upper bound. In particular, the EAF lies typically between 1.4 and 1.7, thus demonstrating that IO-UBs can provide firm guarantees for solutions of factored Dec-POMDPs with up to 700 agents. Moreover, we see that we see that the EAF stays roughly constant for the larger problem instances indicating that relative guarantees do not degrade as the number of agents increase.

Table 1 shows results obtained for ALOHA with up to |D| = 250 agents making use of SPs involving up to |D′ | = 6 agents. The numbers clearly illustrate that it is possible to provide very strong guarantees for problems up to 250 agents (beyond which memory forms the bottleneck for TP); the solution for the |D| = 50 instance is essentially optimal, indicating also a very tight bound for this problem.

6 Related and FutureWork

One way or another, all upper bounds in the literature make some optimistic assumption, but influence-optimistic UBs are novel. While the idea of being optimistic with respect to influences has been considered by Kumar and Zilberstein [2009a], they do not provide an upper bound the global value. Instead they employ optimistic assumptions on transitions in an NDPOMDP to derive an MMDP-based policy which is used to sample belief points. Kumar and Zilberstein [2009b] present the only previous method that delivers scalability with respect to the number of agents without assuming value factorization by exploiting submodular function maximization for a specific class of sensor network problems.

Upper bounds for ND-POMDPs (e.g., [Varakantham et al., 2007; Dibangoye et al., 2014]) resemble our global IO upper bound. The crucial distinction is that for value factorized settings computing ˆ Ve does not require any influence-optimism: the reason that value-factorization holds is precisely because there are no influence sources for the components. As such, our influence-optimistic upper bounds can be seen as a strict generalization of the upper bounds that have been employed for settings with factored value functions. A promising idea is to employ our factored upper bounds in combination with the heuristic search methods by Dibangoye et al. While it is not possible to directly use that method since it additionally requires a factored lower bound function, pessimistic-influence bounds could provide those.

Finally, our upper-bounding method contributes a useful precursor for techniques that automatically search the space of possible upper bounds decompositions, efficient optimal influence-space heuristic search methods (for which we provide preliminary evidence in the extended version of this paper [Oliehoek et al., 2015]), and A* methods for a large class of factored Dec-POMDPs (as mentioned above).

7 Conclusions

We presented a family of influence-optimistic upper bounds for the value of sub-problems of factored Dec-POMDPs, together with a partition-based decomposition approach that enables the computation of global upper bounds for very large problems. The approach builds upon the framework of influence-based abstraction [Oliehoek et al., 2012], but-in contrast to that work-makes optimistic assumptions on the incoming 'influences', which makes the sub-problems easier to solve. An empirical evaluation compares the proposed upper bounds and demonstrates that it is possible to achieve guarantees for problems with hundreds of agents, showing that found heuristic solution are in fact close to optimal (empirical approximation factors of < 1.7 in all cases and sometimes substantially better). This is a significant contribution, given the (NEXP-complete [Rabinovich et al., 2003]) complexity of computing ϵ-approximate solutions and the fact that tight global upper bounds are of crucial importance to interpret the quality of heuristic solutions.

Acknowledgments

• F.O. is supported by NWO Innovational Research Incentives Scheme Veni #639.021.336.