Structural Results for Cooperative Decentralized Control Models

1 Introduction

Decentralized partially observable Markov decision processes (Dec-POMDPs) have emerged as the standard framework for sequential decentralized decision-making [Radner, 1962; Yoshikawa and Kobayashi, 1978; Bernstein et al., 2002]. This general model involves multiple agents with different observations that cooperate to achieve a common objective, but cannot communicate with one another. Unfortunately, its worst-case complexity has limited its applicability. The finite-horizon case is in NEXP [Bernstein et al., 2002]. The infinite-horizon case is undecidable, and �- approximations remain intractable [Rabinovich et al., 2003]. These negative complexity results are mainly due to the exponential growth in the size of both optimal policy and value function spaces with time. This results in limited scalability and applicability [Hansen et al., 2004; Szer et al., 2005; Oliehoek et al., 2008; Bernstein et al., 2009].

To allow further scalability and applicability, much attention has been devoted to cooperative decentralized control models with restrictive assumptions [Goldman and Zilberstein, 2004; Becker et al., 2004; Nair et al., 2005; Melo and Veloso, 2011]. These assumptions concern restrictions on both the dynamics and the rewards. In particular, [Goldman and Zilberstein, 2004] demonstrated that the complexity goes down from NEXP to NP when agents influence one

Olivier Simonin

Inria - CITI Lyon, France olivier.simonin@insa-lyon.fr

another only through rewards, and are otherwise fully independent. Unfortunately, not all restrictions result in scalability gains, let alone complexity drops. So far, the asymptotic complexity analysis suggests that memory reductions due to restrictions on rewards are unlikely, if not impossible [Bernstein et al., 2002; Goldman and Zilberstein, 2004; Allen and Zilberstein, 2009]. This negative complexity has limited the attractiveness of models involving reward restrictions.

This paper introduces a general methodology referred to as structural analysis, which helps designing optimalitypreserving concise policies and value functions for the cooperative decentralized control problem at hand. For the first time, we show that memory requirements for policies and value functions may be asymmetric, resulting in significant memory reduction on certain models. Another novel and important result is the proof that under mild conditions on rewards, the optimal value function consists of linear functions from hidden states to reals. To allow a wide applicability, the structural analysis builds upon a recent theory to solving DecPOMDPs by recasting them as a continuous-state deterministic Markov decision process with a piecewise-linear and convex optimal value function [Dibangoye et al., 2013a]. Overall, it seems like the asymptotic complexity analysis provides a useful hierarchy of problems, while the structural analysis is geared to guide the automatic characterization of optimalitypreserving concise policies and value functions, which will eventually lead to the development of scalable, applicable and widely adaptable theory and algorithms.

The remainder of this paper is organized as follows. Section 2 focuses on Dec-POMDPs and the recent approach to solving them. Next, we introduce the criteria we rely on to characterize optimality-preserving concise policies and value functions. Next, we discuss certain subclasses of DecPOMDPs with mild conditions, demonstrating the usefulness of the structural analysis.

2 Cooperative Decentralized Control Models

We consider a decentralized partially observable Markov decision process (Dec-POMDP) involving n cooperative agents

Here, S is a finite set of hidden states; Ai is a finite set of private actions of agent i; and Zi is a finite set of private observations of agent i. Given any hidden state and joint action, s and a, the probability of each possible next hidden state and joint observation, s 0 and o, is P as (s 0 ; o). Similarly, given any current state and joint action, s and a, the reward is R a (s). This model is parametrized by � 0 the initial state distribution and T the planning horizon.

The goal of optimal decentralized decision-making is to find a joint policy � = (�i) maximizing the expected sum of rewards starting in initial distribution � 0 . A joint policy � = (�i) is an n-tuple of agent policies �i, one for each agent. Alternatively, a joint policy � = (� t ) is a sequence of T joint decision rules, one for each time step. Similarly, an agent policy �i = (� t i )t2f0;1;:::;T�1g is a sequence of T agent decision rules. A step-t agent decision rule � t i is a mapping from length-t private (observation) history �i = (a 0 i ; z 1 i ; : : : ; a t�1 i ; z t i ) to private actions � t i (�i) 2 Ai.

Example 1. To illustrate the main result of this paper, consider a simple cooperative, decentralized control problem in which three agents must navigate to their terminal locations (denoted sG) as soon as possible. Agents need to coordinate since they affect each other through both rewards and dynamics. In this world, possible actions for each agent include moving north, south, west, east and staying in the same place. Each time, agents take an action, they receive a reward and a noisy observation about the current state of the world. The penalty is 0 if the current state is sG and +1 otherwise.

For simplicity, in the remainder of the paper, we use majuscule bold symbols to denote random variables, and minuscule symbols to denote associated realizations - e.g., for any action-observation histories, we use � and � to denote random variable and its realization, respectively.

2.1 OccupancyMarkov Decision Process

The reformulation relies on a common assumption in decentralized decision-making that planning can be achieved in a centralized manner while still preserving decentralized execution [Szer et al., 2005; Oliehoek et al., 2008; 2013]. Building on this insight, [Dibangoye et al., 2013a] introduced the concept of occupancy state, denoted �, to represent a distribution over hidden states and joint histories.

Occupancy states � t (S t ;� t ) def = P � 0 ;� 0:t�1 (S t ;� t ) are sufficient statistics of data (� 0 ; � 0:t�1 ) for the characterization of optimal joint policy � 0:t�1 starting in initial occupancy � 0 . Before proceeding any further, let us provide a formal definition of a sufficient statistics by [Fisher, 1922].

Definition 1. A statistic �(X) is sufficient for parameter Y precisely if the conditional probability of Y, given the statistic �(X), does not depend on data X - i.e.,

where X, Y and �(X) are random variables.

Intuitively, a sufficient statistic captures all important information contained in data about a given parameter to be estimated, no further information can be obtained from the data. Notice, however, that sufficient statistics pertain to data reduction, not merely parameter estimation. As an example, in MDPs, the current joint observation is sufficient for the estimate of the current state. Once the current joint observation is known, no further information about the current state can be obtained from the history of an MDP - i.e., P(S t jZ 1 ; : : : ; Z t ) = P(S t jZ t ) [Puterman, 1994].

Unfortunately, similarly to the joint policy space, in the worst case the occupancy-state space (denoted 4) grows exponentially as time goes on. In particular, the next-step occupancy states � t+1 = P � t � t is updated at each time-step t to incorporate the latest joint decision rule � t :

Not surprisingly, in the worst case the space of joint decision rules (denoted �) grows exponentially with time as well. From the Bayesian update-rule in (2), occupancy states describe a process that is Markov.

The immediate reward R � t � t obtained by taking joint decision rule � t at any occupancy state � t is written:

Equations (2) and (3) directly lead to the definition of the occupancy-state Markov decision process (OMDP):

of the following meaning: 4 is a continuous-state space; � is a multidimensional action space; R � t is the immediate reward vector for joint decision rule � t ; and P � t the deterministic transition-matrix for joint decision rule � t . The goal then is to find a joint policy � whose value function is the solution of the [Bellman, 1957] optimality equation: 8� t 2 4,

with boundary condition V t M (�) = 0. Interestingly, [Dibangoye et al., 2013a] demonstrate the optimal value function (V t M )t2f0;1;:::;T�1g solution of (5) is a piecewise-linear and convex function of occupancy states. In other words, there exists a finite set of high-dimensional vectors (called �-vectors), (� t = f� t g)t2f0;1;:::;T�1g, such that the optimal value at any occupancy state � t 2 4 is:

This property is particularly important as it allows the value function to generalize over the entire occupancy space. The step-t set of �-vectors � t can be built from the next-step set � t+1 using the [Bellman, 1957] backup operator, denoted H. We shall use notation H(� t ; � t+1 ) = � t � to denote the exact point-based backup:

A repeated application of the point-based backup over reachable occupancy states ensures optimality of algorithms.

Algorithm 1: The OHSVI algorithm.

function EXPLORE (� t )

if GAP(� t ) > 0 then

action-selection given U t+1 and � t yields � t � . update upper-bound U t at occupancy state � t . EX P L O R E(P � t � � t ).

update lower-bound L t at occupancy state � t .

2.2 Optimally Solving Dec-POMDPs as OMDPs

[Dibangoye et al., 2013a] demonstrate an optimal joint policy for ˆM is also optimal for M. Hence, we focus on optimally solving ˆM. Since ˆM is essentially a continuous-state MDP with a piecewise-linear and convex optimal value function, methods for solving POMDPs can also solve ˆM.

In particular, [Dibangoye et al., 2013a] extend the heuristic search value iteration (HSVI) algorithm for POMDPs [Smith and Simmons, 2004] to solving for OMDPs. The resulting OHSVI algorithm 1 is a trial-based algorithm, which proceeds by generating trajectories of occupancy states, starting at occupancy state � 0 . It maintains both upper and lower bounds over the optimal value function, we denote (L t ) and (U t ), respectively. It guides exploration towards occupancy states that are more relevant to the upper bounds by greedily selecting joint decision rules with respect to the upper bounds, which reduces the difference between bounds at those points. The algorithm terminates when the gap at the initial occupancy state � 0 is zero. In such a case, the algorithm has converged.

The OHSVI algorithm has demonstrated impressive results on medium-sized problems from the literature of DecPOMDPs [Dibangoye et al., 2013a], but its scalability remains a serious challenge. There are two reasons for the limited scalability of methods to solving ˆM due to the dimensionality of joint decision rules � t , occupancy state � t and �-vectors � t+1 . Computing � t , R � t � t and P � t � t requires time complexities polynomial in the dimensionality of � t , which itself grows exponentially with time. Even more importantly, the exponential complexity requirement of H(� t ; � t+1 ) is the major source of the intractability of ˆM. This highlights the impetus for automatic and general purpose methods for designing optimality-preserving concise policies, occupancy states and �-vectors. To date, determining structural results (e.g., sufficient statistics) seems more like an art than a science [Goldman and Zilberstein, 2004; Dibangoye et al., 2012; 2013a; Oliehoek, 2013]. We will distinguish between four categories of sufficient statistics ranging along two dimensions: objective and perspective dimensions.

3 Separation of Policy and Value Statistics

Along the objective dimension, this section investigates the separation of sufficient statistics for the estimation of expected cumulated rewards and those for the design of optimal joint policies - namely, policy- and value-sufficient statistics, respectively. Along the perspective dimension, we will differentiate between data provided from an agent to that of a centralized planner point of views - namely, agent- and planner-centric sufficient statistics.

3.1 Separation Principle

The goal of planning in cooperative, decentralized control models is to find an optimal joint policy - i.e., the one that maximizes the long-term expected cumulated rewards. Since the design of optimality-preserving concise policies and the estimation of expected cumulated rewards are interconnected objectives, a common assumption is that both share the same sufficient statistic. But this common assumption is not always true. Notice that any agent policy depends on agent actionobservation histories (in the worst case):

where Ai and �i denote random variables associated to agent actions and histories. Instead, the immediate expected reward depends on agent action-observation histories and actions,

where R = R �j(�j);Ai (S) denotes random variable associated to immediate reward agents received upon agent i taking action Ai in action-observation history �i. Hence, while being interdependent, policy- and value-sufficient statistics are possibly different, as stated in the following.

Lemma 1 (Separation Principle). In cooperative, decentralized control models, the expected value V � M (� 0 ) of any arbitrary joint policy � starting at initial state � 0 depends on two possibly different sufficient statistics:

where �(�i) and � 0 (�(�i); Ai) denote policy- and valuesufficient statistics, respectively.

Lemma 1 provides a useful characterization of agentcentric policy- and value-sufficient statistics. It further suggests that value-sufficient statistics have a dimensionality lower than or equal to policy-sufficient statistics. This is a major discovery as, so far, we assumed both were identical. The immediate implication of this property is the ability to improve (1) the scalability of operations P � t � t , R � t � t and even more importantly H(� t ; � t+1 ); and (2) the estimation accuracy by enhancing the generalization between policysufficient statistics that share the same corresponding (lowerdimensional) value-sufficient statistics.

Example 2. Clearly, example 1 is a three-agent goal-directed Dec-POMDP [Amato and Zilberstein, 2009; Goldman and Zilberstein, 2004]. In practice, [Amato and Zilberstein, 2009] used the complete history of actions and observations

�i for each agent i 2 N as policy- and value-sufficient statistics in such a setting. However, the separation principle suggests a value-sufficient statistic can be made significantly different than a policy-sufficient statistic. Based on the reward function, one can indeed show that if the probability of being in sG is psG then the immediate expected reward will be (1 � psG ) = 0 � psG + (+1) � (1 � psG ). Hence, the conditional probability of being in sG, denoted P � 0 ;�j (sGj�i; ai), is a sufficient statistic for the estimation of immediate expected reward R � 0 ;� j (�i; ai) - i.e., R � 0 ;� j (�i; ai) = 1 � P � 0 ;� j (sGj�i ; ai). Once the conditional probability P � 0 ;� j (sGj�i; ai) of being in sG is known, no further information can be obtained from agent history and action, �i and ai, respectively.

4 Policy-Sufficient Statistics

The previous section demonstrated that policy- and valuesufficient statistics are possibly different. This section introduces criteria that provide a convenient characterization of concise, if not minimal, policy-sufficient statistics required to solving M (respectively ˆM).

4.1 Markov Property

Here, we define the property, that is a necessary condition for the characterization of policy-sufficient statistics.

Criterion 1. For any arbitrary cooperative, decentralized control model M, agent i and teammates j, a statistic �(�i) satisfies the Markov property if, and only if, the future statistics depend solely on the current one:

where � 0 i denotes the next-step random variable of �i.

Informally, a statistic satisfies the policy criterion if, and only if, it contains all information about its offsprings, no further information can be obtained from the complete history. It is worth noticing that the Markov property is not sufficient for the design of an optimal agent policy. But all policy-sufficient statistics satisfies the policy criterion. So, one can use this criterion to check whether or not a statistic is a good candidate policy-sufficient statistic, as discussed below.

Example 3. Consider our running example 1. We showed in example 2 that a concise value-sufficient statistic is the probability of being in the terminal state. Using policy criterion, one can show that this statistic cannot serve as a policy-sufficient statistic. This is mainly because the current probability of being in the terminal state discarded important information for an accurate estimation of the next-step probability of being in the terminal state. As a consequence this statistic does not satisfy the policy criterion, and this cannot be a policy-sufficient statistic. Examples of statistics that are Markovian include: the complete action-observation history �(�i) = �i; or the current observation �(�i) = zi, etc. Markov property trivially holds when using complete actionobservation histories. Similarly, it holds when using the current observation, since the next-step observation does not depend on the complete history.

4.2 Value-Preserving Property

Here, we define the value-preserving property, that is a necessary condition for the characterization of agent-centric policy- and value-sufficient statistics.

Criterion 2. For any arbitrary cooperative, decentralized control model M, agent i and teammates j, a statistic �(�i) satisfies the value-preserving property if, and only if, there exists agent-centric value-sufficient statistic � 0 (�(�i); Ai):

Intuitively, this criterion requires statistic �(�i) along with Ai to be an agent-centric value-sufficient statistic themselves. Similarly to the Markov property, statistics that are valuepreserving need not be policy-sufficient. Yet, all policysufficient statistics need to be value-preserving in order the preserve ability of being policy-sufficient, as illustrated next.

Example 4. Back to our running example 1, we know from example 3 that the current observation zi is Markovian and the probability of being in the terminal state P � 0 ;� j (sGj�i ; ai) describes the minimal value-sufficient statistic. A natural question then is whether the current observation is valuepreserving. In other words, does the current observation describes a sufficient statistic for the probability of being in the terminal state starting given the complete action-observation history? The answer is negative since the history contains additional information than are crucial in estimating this probability. Hence, the current observation is Markovian but it is not value-preserving, which precludes zi from being a policysufficient statistic.

4.3 Characterizing Policy-Sufficient Statistics

We are now ready to state and provide a convenient characterization of agent- and planner-centric policy-sufficient statistics based on Markov and value-preserving properties.

Theorem 1. For any arbitrary cooperative, decentralized control model M, agent i and teammates j, a statistic �(�i) is an agent-centric policy-sufficient statistic if it satisfies both Markov and value-preserving properties.

An immediate implication of this theorem is a useful characterization of a minimal sufficient statistic for policies. A minimal sufficient statistic for policies is the lowestdimensional statistic that satisfies the transition criterion. This characterization will eventually lead to the design of efficient automatic methods for identifying minimal sufficient statistics for policies of any decentralized control application at hand, as demonstrated in Section 6. Theorem 1 focuses on policy-sufficient statistics from each agent's perspective. Another important implication pertains to the design of the minimal policy-sufficient statistic from the centralized planner's perspective. This is still an open problem, but the following provides a convenient way to build good planner-centric policy-sufficient statistics.

Corollary 1. For any arbitrary cooperative, decentralized control model M, joint policy � and initial state � 0 , a statistic �(� 0 ; �) is a planner-centric policy-sufficient statistic if, and only if, it describes a probability distribution over hidden states and agent-centric policy-sufficient statistics (�1(�1); � � � ; �N(�N)):

where �i(�i) denotes a policy-sufficient statistic of agent i.

The total information available to the centralized planner is joint policy � and initial state � 0 . Hence, a planner-centric policy-sufficient statistic summarizes data � and � 0 . The primary goal of Theorem 1 and Corollary 1 is to provide a convenient way to check whether a statistic is actually a policysufficient statistic, as illustrated below.

Example 5. Consider statistics �i(�i) = P � 0 ;� j M (S;�jj�i) describing the conditional probability of hidden states and other agent histories given history of agent i. One can show that statistic �i(�i) is Markovian, since P � 0 ;� j M (S 0 ; � 0 j j�i; Ai; Zi) = P � 0 ;� j M (S 0 ; � 0 j j�i(�i); Ai; Zi). Moreover, statistic P � 0 ;� j M (S;�jj�i) is value-preserving because P � 0 ;� j M (sGj�i; Ai) is obtained by marginalizing out over nonterminal states and other agent histories. Hence, �i(�i) is a policy-sufficient statistic. Similarly, one can demonstrate that an occupancy state �(S; �) = P � 0 ;� (S; �) is a policy-sufficient statistic from the centralized planner's perspective if we let �i(�i) = �i and apply Corollary 1.

5 Value-Sufficient Statistics

This section introduces criteria that provide a convenient characterization of concise, if not minimal, agent- and planner-centric value-sufficient statistics required to solving M (respectively ˆM). We distinguish betweenmodels inwhich agents have independent rewards to those in which agents influence each other through rewards. The following lemma builds upon the definition of a sufficient statistic to prove that if agents have independent rewards, then the central planner requires only an agent-centric value-sufficient statistic.

Lemma 2. For any arbitrary cooperative, decentralized control model M, agent i and teammates j, a statistic � 0 (�(�i); Ai) is agent-centric value-sufficient if, and only if, there exists an agent-centric policy-sufficient statistic �(�i) such that: R � 0 ;� j M (�i; Ai) = R � 0 ;� j M (� 0 (�(�i); Ai)).

Intuitively, this lemma states that under independent rewards, the centralized planner needs to maintain one value function for each agent, hence only agent-centric valuesufficient statistics are required. Section 6.3 provides structural results for an important subclass of models with independent rewards. Next, we consider a much broader settings in which agents have a common reward function.

Lemma 3. For any arbitrary cooperative, decentralized control model M, joint policy � and initial state � 0 , a statistic �(� 0 ; �) is planner-centric value-sufficient if, and only if, it is sufficient for any agent-centric value-sufficient statistic � 0 i (�i(�i); Ai).

Intuitively, this lemma states that a statistic that is sufficient for agent-centric value-sufficient statistic for all agents is a planner-centric value-sufficient statistic.

6 New Structural Results

This section presents a general automatic method, referred to as a structural analysis, which eases the design of concise, if not minimal, sufficient statistics for policies and �- vectors. We apply the methodology on a selection of decentralized control models, on which asymptotic complexity analysis suggests significant memory gains were unlikely, if not impossible. Surprisingly, our structural analysis demonstrates that significant memory gains can be achieved.

6.1 Structural Analysis

Algorithm 2 describes the structural analysis method. It starts with the selection of a subset of possible statistics ˜� from the unknown set of all possible statistics �. Each statistic ˜O from the subset is an observable random variable of the decentralized control application at hand. The methodology proceeds by testing statistics in the order of increasing dimensionality. The test consists in checking whether the given sufficient criterion C, depending on the type of sufficient statistic we target, is satisfied. The methodology terminates when there are no more statistics to be tested, or one statistic passed the test; in the latter case, a concise, if not minimal, sufficient statistic has been found.

Algorithm 2: The Structural Analysis.

function SA(� ; C)

1. Select subset ˜� � � of statistics ˜O.
2. Extract the lower-dimensional one ˜O � .
3. If ˜O � fails on criterion C, go back to (2).
4. Otherwise return sufficient statistic ˜O � .

The selection of a representative subset of statistics is not a trivial task as many subsets may end up with no sufficient statistics. As an example, one can select sufficient statistics in the space of histories as did [Dibangoye et al., 2013a] with success. Though preliminary, this method enhances automatic characterization of concise sufficient statistics, policies and value functions (via �-vectors). Of course, the method could also help verifying previously exhibited statistics were indeed sufficient [Goldman and Zilberstein, 2004; Becker et al., 2004; Nair et al., 2005; Oliehoek, 2013; Dibangoye et al., 2012; 2013b; 2014].

In demonstrating the practical usefulness of the methodology, the following exhibits sufficient statistics for general decentralized control models under mild restrictions on the system rewards.

6.2 Action-Independent Rewards

We start with decentralized control models with actionindependent rewards. The system rewards (R a ) are actionindependent iff, there exists a function R, for any arbitrary joint action a, such that R a = R. This mild condition appears in a number of important applications ranging from robotics (e.g., collective information gathering tasks) to network security (e.g., intrusion detection problems) [Blin et al., 2006]. In such a setting, the structural analysis reveals that the empty history is the sufficient statistic of any private history for optimality-preserving and concise �-vectors, which leads to the following lemma.

Lemma 4. Under action-independent rewards, the distribution over hidden states P �0;� (S) is a planner-centric valuesufficient statistic.

From the above lemma, it directly follows that �-vectors are mappings from hidden states to reals, as stated in the following theorem.

Theorem 2. Under action-independent rewards, optimalitypreserving concise �-vectors are jS j-dimensional real vectors: ˜� ˜� t:T�1 (S) = E˜� t:T �1 [ P T �1 =t R(S)].

�

In general, �-vectors � � t:T�1 have dimensionality exponential with time, � � t:T�1 (S; �) = E� t:T �1 [ P T �1 =t R � � (�) (S)].

� Theorem 2 reveals that the resources needed to accurately maintain value functions through �-vectors is exponentially smaller than that of the general setting. Even more importantly, under action-independent rewards, the dimensionality of �-vectors is bounded by the number of hidden states. Notice that this result goes beyond the scope of Dec-POMDPs. It can apply on all subclasses of Dec-POMDPs with actionindependent rewards - e.g., POMDPs [Kaelbling et al., 1998] with action-independent rewards. Besides the enormous memory savings, this property can significantly enhance generalization and evaluation of the value function, as previously discussed.

6.3 Additive Rewards

Another important condition pertains to the additivity of agent rewards. The system rewards R are fully additive iff there exists n functions R1; R2; : : : ; Rn, such that: 8s 2 S; a = (ai) 2 A, R a (s) = R a1 1 (s) + R a2 2 (s) + : : : + R an n (s). A notable example of this family is the foraging problem, in which agents collaborate to search for disseminated resources. The reward is often defined as the sum of resources agents transport back to home.

In such a setting, the structural analysis reveals that a value-sufficient statistic �i(�i) of any private history �i for optimality-preserving and concise �-vectors is both a statedistribution P �0;�j (Sj�i; Ai) and independent of histories of other agents. This leads to the following lemma.

Lemma 5. Under additive rewards, state-distribution P �0;�j (Sj�i; Ai) is an agent-centric value-sufficient statistic.

Another important result pertaining to the characterization of optimality-preserving concise value functions follows from the above lemma.

Theorem 3. Under additive rewards, optimality-preserving concise value functions consist of tuples of private value functions (� t i )i2f1;2;:::;ng;t2f0;1;:::;Tg, one for each time step and agent. Even more importantly, each �-vector ˜� ˜� t:T �1 �i 2 � t i is an jS jdimensional real vector: ˜� ˜� t:T �1 �i (S) = E˜� t:T �1 � P T �1 � =t R � � i (�i) i (S) � .

In general, �-vectors � � t:T �1 �i have dimensionality exponential with time, � � t:T �1 �i (S;�j) = E� t:T �1 [ P T �1 � =t R � � (�) (S)]. This theorem shows that, in models with additive rewards, each agent holds its private value function although they jointly optimize the sum of these functions. Even more importantly, each optimality-preserving concise private value function is represented by a set of jS j-dimensional real vectors. Nonetheless, agents cannot choose their private actions on their own as value-sufficient statistics also depend on the choices of the other agents.

7 Discussion and Conclusion

This paper introduces a general methodology, referred to as structural analysis, as a means of characterizing a concise if not minimal, model for the applications at hand - demonstrating adaptability. Under mild conditions, the structural analysis of optimality-preserving concise policies and value functions often results in exponential reductions in memory and time requirements - demonstrating scalability gains. We developed the structural analysis as an analysis tool on top of occupancy-state Markov decision processes, a general model to represent a large variety of Markov models - demonstrating the wide applicability.

The structural analysis aims at characterizing concise sufficient statistics for decentralized control models. The idea of describing minimal sufficient statistics is not new. It can be traced back to Fisher-Neyman factorization [Fisher, 1922], since then numerous authors applied this method to derive sufficient statistics for optimal decision-making: [Smallwood and Sondik, 1973] demonstrate the belief state (distribution over hidden states) is a sufficient statistic of the history of agent for characterizing an optimal policy in general POMDPs; similarly, [Dibangoye et al., 2012] show that the distribution over states is a sufficient statistic of the initial belief and past joint policy for the design of concise and optimal policies in transitional and observational DecMDPs; and [Dibangoye et al., 2013a; Oliehoek, 2013] prove that the distribution over hidden states and joint histories is a sufficient statistic for initial belief and past policies; similar results hold for ND-POMDPs [Nair et al., 2005; Dibangoye et al., 2014]. To date, however, determining sufficient statistics seems more like an art than a science, explaining the importance of the structural analysis. Overall, it looks like the asymptotic complexity analysis provides a useful hierarchy of problems, while the structural analysis is geared to guide the automatic characterization of optimalitypreserving concise policies and value functions, which will eventually lead to the development of scalable, applicable and widely adaptable theory and algorithms.