Decentralized Stochastic Control with Partial History Sharing: A Common Information Approach

I Introduction

Stochastic control theory provides analytic and computational techniques for centralized decision making in stochastic systems with noisy observations. For specific models such as Markov decision processes and linear quadratic and Gaussian systems, stochastic control gives results that are intuitively appealing and computationally tractable. However, these results are derived under the assumption that all decisions are made by a centralized decision maker who sees all observations and perfectly recalls past observations and actions. This assumption of a centralized decision maker is not true in a number of modern control applications such as networked control systems, communication and queuing networks, sensor networks, and smart grids. In such applications, decisions are made by multiple decision makers who have access to different information. In this paper, we investigate such problems of decentralized stochastic control.

The techniques from centralized stochastic control cannot be directly applied to decentralized control problems. Nonetheless, two general solution approaches that indirectly use techniques from centralized stochastic control have been used in the literature: (i) the person-by-person approach which takes the viewpoint of an individual decision maker (DM); and (ii) the designer’s approach which takes the viewpoint of the collective team of DMs.

The person-by-person approach investigates the decentralized control problem from the viewpoint of one DM, say DM $i$ and proceeds as follows: (i) arbitrarily fix the strategy of all DMs except DM $i$; and (ii) use centralized stochastic control to derive structural properties for the optimal best-response strategy of DM $i$. If such a structural property does not depend on the choice of the strategy of other DMs, then it also holds for globally optimal strategy of DM $i$. By cyclically using this approach for all DMs, we can identify the structure of globally optimal strategies for all DMs.

A variation of this approach may be used to identify person-by-person optimal strategies. The variation proceeds iteratively as follows. Start with an initial guess for the strategies of all DMs. At each iteration, select one DM (say DM $i$), and change its strategy to the best response strategy given the strategy of all other DMs. Repeat the process until a fixed point is reached, i.e., when no DM can improve performance by unilaterally changing its strategy. The resulting strategies are person-by-person optimal , and in general, not globally optimal.

In summary, the person-by-person approach identifies structural properties of globally optimal strategies and provides an iterative method to obtain person-by-person optimal strategies. This method has been successfully used to identify structural properties of globally optimal strategies for various applications including real-time communication , decentralized hypothesis testing and quickest change detection , and networked control systems . Under certain conditions, the person-by-person optimal strategies found by this approach are globally optimal .

The designer’s approach, which is developed in , investigates the decentralized control problem from the viewpoint of the collective team of DMs or, equivalently, from the viewpoint of a system designer who knows the system model and probability distribution of the primitive random variables and chooses control strategies for all DMs. Effectively, the designer is solving a centralized planning problem. The designer’s approach proceeds by: (i) modeling this centralized planning problem as a multi-stage, open-loop stochastic control problem in which the designer’s decision at each time is the control law for that time for all DMs; and (ii) using centralized stochastic control to obtain a dynamic programming decomposition. Each step of the resulting dynamic program is a functional optimization problem (in contrast to centralized dynamic programming where each step is a parameter optimization problem).

The designer approach is often used in tandem with the person-by-person approach as follows. First, the person-by-person approach is used to identify structural properties of globally optimal strategies. Then, restricting attention to strategies with the identified structural property, the designer’s approach is used to obtain a dynamic programming decomposition for selecting the globally optimal strategy. Such a tandem approach has been used in various applications including real-time communication , decentralized hypothesis testing , and networked control systems .

In addition to the above general approaches, other specialized approaches have been developed to address specific problems in decentralized systems. Decentralized problems with partially nested information structure were defined and studied in . Decentralized linear quadratic Gaussian (LQG) control problems with two controllers and partially nested information structure were studied in . Partially nested decentralized LQG problems with controllers connected via a graph were studied in . A generalization of partial nestedness called stochastic nestedness was defined and studied in . An important property of LQG control problems with partially nested information structure is that there exists an affine control strategy which is globally optimal. In general, the problem of finding the best affine control strategies may not be a convex optimization problem. Conditions under which the problem of determining optimal control strategies within the class of affine control strategies becomes a convex optimization problem were identified in .

Decentralized stochastic control problems with specific models of information sharing among controllers have also been studied in the literature. Examples include systems with delayed sharing information structures , systems with periodic sharing information structure , control sharing information structure , systems with broadcast information structure , and systems with common and private observations .

In this paper, we present a new general model of decentralized stochastic control called partial history sharing information structure. In this model, we assume that: (i) controllers sequentially share part of their past data (past observations and control) with each other by means of a shared memory; and (ii) all controllers have perfect recall of commonly available data (common information). This model subsumes a large class of decentralized control models in which information is shared among the controllers.

For this model, we present a general solution methodology that reformulates the original decentralized problem into an equivalent centralized problem from the perspective of a coordinator. The coordinator knows the common information and selects prescriptions that map each controller’s local information to its control actions. The optimal control problem at the coordinator is shown to be a partially observable Markov decision process (POMDP) which is solved using techniques from Markov decision theory. This approach provides (a) structural results for optimal strategies, and (b) a dynamic program for obtaining optimal strategies for all controllers in the original decentralized problem. Thus, this approach unifies the various ad-hoc approaches taken in the literature.

A similar solution approach is used in for a model that is a special case of the model presented in this paper. We present an information state (Eq. (51)) for the model of that is simpler than that presented in [36, Theorem 2]. A preliminary version of the general solution approach presented here was presented in for a model that had features (e.g., direct but noisy communication links between controllers) that are not necessary for partial history sharing. However, it can be shown that by suitable redefinition of variables, the model in can be recast as an instance of the model in this paper and vice versa (see Appendix C). The information state for partial history sharing that is presented in this paper (see Thereom 4) is simpler than that presented in [1, Eq. (39)].

We first illustrate how common information can be used in a static team problem with two controllers. Let $X$ denote the state of nature and $Y^{*}$, $Y^{1}$, $Y^{2}$ be three correlated random variables that depend on $X$. Assume that the joint distribution of $(X,Y^{*},Y^{1},Y^{2})$ is given.

Controller $i$, $i=1,2$, observes $(Y^{*},Y^{i})$ and chooses a control action $U^{i}=g^{i}(Y^{*},Y^{i})$. The system incurs a cost $l(X,U^{1},U^{2})$. The control objective is to choose $(g^{1},g^{2})$ to minimize

If all the system variables are finite valued, we can solve the above optimization problem by a brute force search over all control strategies $(g^{1},g^{2})$. For example, if all variables are binary valued, we need to compute the performance of $2^{4}\times 2^{4}=256$ control strategies and choose the one with the best performance.

In this example, both controllers have a common observation $Y^{*}$. One of the main ideas of this paper is to use such common information among the controllers to simplify the search process as follows. Instead of specifying the control strategies $(g^{1},g^{2})$ directly, we consider a coordinated system in which a coordinator observes the common information $Y^{*}$ and chooses prescriptions $(\Gamma^{1},\Gamma^{2})$ where $\Gamma^{i}$ is a mapping from $Y^{i}$ to $U^{i}$, $i=1,2$. Hence, $(\Gamma^{1},\Gamma^{2})=d(Y^{*})$, where $d$ is called the coordination strategy. The coordinator then communicates these prescriptions to the controllers who simply use them to choose $U^{i}=\Gamma^{i}(Y^{i})$, $i=1,2$.

It is easy to verify (see Proposition 3 for a formal proof) that choosing the control strategies $(g^{1},g^{2})$ in the original system is equivalent to choosing a coordination strategy $d$ in the coordinated system. The problem of choosing the best coordination strategy, however, is a centralized problem in which the coordinator is the only decision-maker.

For example, consider the case when all system variables are binary valued. For any coordination strategy $d$, let $(\gamma_{0}^{1},\gamma_{0}^{2})=d(0)$ and $(\gamma_{1}^{1},\gamma_{1}^{2})=d(1)$. Then, the cost associated with this coordination strategy is given as:

To minimize the above cost, we can minimize the two terms separately. Therefore, to find the best coordination strategy $d$, we can search for optimal prescriptions for the cases $Y^{*}=0$ and $Y^{*}=1$ separately. Searching for the best prescriptions for each of these cases involves computing the performance of $2^{2}\times 2^{2}=16$ prescription pairs and choosing the one with the best performance. Thus, to find the best coordination strategy, we need to evaluate the performance of $16+16=32$ prescription pairs. Contrast this with the $256$ strategies whose costs we need to evaluate to solve the original problem by brute force.

The above example described a static system and illustrates that common information can be exploited to convert the decentralized optimization problem into a centralized optimization problem involving a coordinator. In this paper, we build upon this basic idea and present a solution approach based on common information that works for dynamical decentralized systems as well. Our approach converts the decentralized problem into a centralized stochastic control problem (in particular, a partially observable Markov decision process), identifies structure of optimal control strategies, and provides a dynamic program like decomposition for the decentralized problem.

I-B Contributions of the Paper

We introduce a general model of decentralized stochastic control problem in which multiple controllers share part of their information with each other. We call this model the partial history sharing information structure. This model subsumes several existing models of information sharing in decentralized stochastic control as special cases (see Section II-B). We establish two results for our model. Firstly, we establish a structural property of optimal control strategies. Secondly, we provide a dynamic programming decomposition of the problem of finding optimal control strategies. As in , our results are derived using a common information based approach (see Section III). This approach differs from the person-by-person approach and the designer’s approach mentioned earlier. In particular, the structural properties found in this paper cannot be found by the person-by-person approach described earlier. Moreover, the dynamic programming decomposition found in this paper is distinct from —and simpler than— the dynamic programming decomposition based on the designer’s approach. For a general framework for using common information in sequential decision making problems, see .

I-C Notation

For a singleton $a$ and a set $B$, $\{a,B\}$ denotes the set $\{a\}\cup B$. For two sets $A$ and $B$, $\{A,B\}$ denotes the set $A\cup B$. For two finite sets $\mathcal{A},\mathcal{B}$, $F(\mathcal{A},\mathcal{B})$ is the set of all functions from $\mathcal{A}$ to $\mathcal{B}$. Also, if $\mathcal{A}=\emptyset$, $F(\mathcal{A},\mathcal{B}):=\mathcal{B}$. For a finite set $\mathcal{A}$, $\Delta(\mathcal{A})$ is the set of all probability mass functions over $\mathcal{A}$. For the ease of exposition, we assume that all state, observation and control variables take values in finite sets.

For two random variables (or random vectors) $X$ and $Y$ taking values in $\mathcal{X}$ and $\mathcal{Y}$, $\mathds{P}(X=x|Y)$ denotes the conditional probability of the event $\{X=x\}$ given $Y$ and $\mathds{P}(X|Y)$ denotes the conditional PMF (probability mass function) of $X$ given $Y$, that is, it denotes the collection of conditional probabilities $\mathds{P}(X=x|Y),x\in\mathcal{X}$. Finally, all equalities involving random variables are to be interpreted as almost sure equalities (that is, they hold with probability one).

I-D Organization

The rest of this paper is organized as follows. We present our model of a decentralized stochastic control problem in Section II. We also present several special cases of our model in this section. We prove our main results in Section III. We apply our result to some special cases in Section III-B. We present a simplification of our result and a generalization of our model in Section IV. We consider the infinite time-horizon discounted cost analogue of our problem in Section V. Finally, we conclude in Section VI.

II Problem Formulation

Consider a dynamic system with $n$ controllers. The system operates in discrete time for a horizon $T$. Let $X_{t}\in\mathcal{X}_{t}$ denote the state of the system at time $t$, $U^{i}_{t}\in\mathcal{U}^{i}_{t}$ denote the control action of controller $i$, $i=1,\dots,n$ at time $t$, and $\mathbf{U}_{t}$ denote the vector $(U^{1}_{t},\dots,U^{n}_{t})$.

The initial state $X_{1}$ has a probability distribution $Q_{1}$ and evolves according to

where $\{W^{0}_{t}\}_{t=1}^{T}$ is a sequence of i.i.d. random variables with probability distribution $Q^{0}_{W}$.

II-A2 Data available at the controller

At any time $t$, each controller has access to three types of data: current observation, local memory, and shared memory.

Current local observation: Each controller makes a local observation $Y^{i}_{t}\in\mathcal{Y}^{i}_{t}$ on the state of the system at time $t$,

where $\{W^{i}_{t}\}_{t=1}^{T}$ is a sequence of i.i.d. random variables with probability distribution $Q^{i}_{W}$. We assume that the random variables in the collection $\{X_{1},W^{j}_{t},t=1,\dots,T,j=0,1,\dots,n\}$, called primitive random variables, are mutually independent.

Local memory : Each controller stores a subset $M^{i}_{t}$ of its past local observations and its past actions in a local memory:

At $t=1$, the local memory is empty, $M^{i}_{1}=\emptyset$.

Shared memory: In addition to its local memory, each controller has access to a shared memory. The contents $C_{t}$ of the shared memory at time $t$ are a subset of the past local observations and control actions of all controllers:

where $\mathbf{Y}_{t}$ and $\mathbf{U}_{t}$ denote the vectors $(Y^{1}_{t},\dots,Y^{n}_{t})$ and $(U^{1}_{t},\dots,U^{n}_{t})$ respectively. At $t=1$, the shared memory is empty, $C_{1}=\emptyset$.

Controller $i$ chooses action $U^{i}_{t}$ as a function of the total data $(Y^{i}_{t},M^{i}_{t},C_{t})$ available to it. Specifically, for every controller $i$, $i=1,\dots,n$,

where $g^{i}_{t}$ is called the control law of controller $i$. The collection $\mathbf{g}^{i}=(g^{i}_{1},\dots,g^{i}_{T})$ is called the control strategy of controller $i$. The collection $\mathbf{g}^{1:n}=(\mathbf{g}^{1},\dots,\mathbf{g}^{n})$ is called the control strategy of the system.

II-A3 Update of local and shared memories

Shared memory update: After taking the control action at time $t$, the local information at controller $i$ consists of the contents $M^{i}_{t}$ of its local memory, its local observation $Y^{i}_{t}$ and its control action $U^{i}_{t}$. Controller $i$ sends a subset $Z^{i}_{t}$ of this local information $\{M^{i}_{t},Y^{i}_{t},U^{i}_{t}\}$ to the shared memory. The subset $Z^{i}_{t}$ is chosen according to a pre-specified protocol. The contents of shared memory are nested in time, that is, the contents $C_{t+1}$ of the shared memory at time $t+1$ are the contents $C_{t}$ at time $t$ augmented with the new data $\mathbf{Z}_{t}=(Z^{1}_{t},Z^{2}_{t},\ldots,Z^{n}_{t})$ sent by all the controllers at time $t$:

Local memory update: After taking the control action and sending data to the shared memory at time $t$, controller $i$ updates its local memory according to a pre-specified protocol. The content $M^{i}_{t+1}$ of the local memory can at most equal the total local information $\{M^{i}_{t},Y^{i}_{t},U^{i}_{t}\}$ at the controller. However, to ensure that the local and shared memories at time $t+1$ don’t overlap, we assume that

Figure 1 shows the time order of observations, actions and memory updates.

We refer to the above model as the partial history sharing information structure.

II-A4 The optimization problem

At time $t$, the system incurs a cost $l(X_{t},\mathbf{U}_{t})$. The performance of the control strategy of the system is measured by the expected total cost

where the expectation is with respect to the joint probability measure on $(X_{1:T},\mathbf{U}_{1:T})$ induced by the choice of $\mathbf{g}^{1:n}$.

We are interested in the following optimization problem.

For the model described above, given the state evolution functions $f_{t}$, the observation functions $h^{i}_{t}$, the protocols for updating local and share memory, the cost function $l$, the distributions $Q_{1}$, $Q^{i}_{W}$, $i=0,1,\dots,n$, and the horizon $T$, find a control strategy $\mathbf{g}^{1:n}$ for the system that minimizes the expected total cost given by (8).

II-B Special Cases: The Models

In the above model, although we have not specified the exact protocols by which controllers update the local and shared memories, we assume that pre-specified protocols are being used. Different choices of this protocol result in different information structures for the system. In this section, we describe several models of decentralized control systems that can be viewed as special cases of our model by assuming a particular choice of protocol for local and shared memory updates.

Consider the following special case of the model of Section II-A.

The shared memory at the beginning of time $t$ is $C_{t}=\{\mathbf{Y}_{1:t-s},\mathbf{U}_{1:t-s}\}$, where $s\geq 1$ is a fixed number. The local memory at the beginning of time $t$ is $M^{i}_{t}=\{Y^{i}_{t-s+1:t-1},U^{i}_{t-s+1:t-1}\}$.

At each time $t$, after taking the action $U^{i}_{t}$, controller $i$ sends $Z^{i}_{t}=\{Y^{i}_{t-s+1},U^{i}_{t-s+1}\}$ to the shared memory and the shared memory at $t+1$ becomes $C_{t+1}=\{\mathbf{Y}_{1:t-s+1},\mathbf{U}_{1:t-s+1}\}$.

After sending $Z^{i}_{t}=\{Y^{i}_{t-s+1},U^{i}_{t-s+1}\}$ to the shared memory, controller $i$ updates the local memory to $M^{i}_{t+1}=\{Y^{i}_{t-s+2:t},U^{i}_{t-s+2:t}\}$.

In this spacial case, the observations and control actions of each controller are shared with every other controller after a delay of $s$ time steps. Hence, the above special case corresponds to the delayed sharing information structure considered in .

II-B2 Delayed State Sharing Information Structure

A special case of the delayed sharing information structure (which itself is a special case of our basic model) is the delayed state sharing information structure . This information structure can be obtained from the delayed sharing information structure by making the following assumptions:

The state of the system at time $t$ is a $n$-dimensional vector $X_{t}=(X^{1}_{t},X^{2}_{t},\ldots,X^{n}_{t})$.

At each time $t$, the current local observation of controller $i$ is $Y^{i}_{t}=X^{i}_{t},$ for $i=1,2,\ldots,n$.

In this spacial case, the complete state vector $X_{t}$ is available to all controllers after a delay of $s$ time steps.

II-B3 Periodic Sharing Information Structure

Consider the following special case of the model of Section II-A where controllers update the shared memory periodically with period $s\geq 1$:

For time $ks<t\leq(k+1)s$, where $k=0,1,2,\ldots$, the shared memory at the beginning of time $t$ is $C_{t}=\{\mathbf{Y}_{1:ks},\mathbf{U}_{1:ks}\}.$ The local memory at the beginning of time $t$ is $M^{i}_{t}=\{Y^{i}_{ks+1:t-1},U^{i}_{ks+1:t-1}\}.$

At each time $t=(k+1)s$, $k=1,2,\dots$, after taking the action $U^{i}_{t}$, controller $i$ sends $Z^{i}_{t}=\{Y^{i}_{ks+1:(k+1)s},U^{i}_{ks+1:(k+1)s}\}$ to the shared memory. At other times, each controller does not send anything (thus $Z^{i}_{t}=\emptyset$).

After sending $Z^{i}_{t}$ to the shared memory, controller $i$ updates the local memory to $M^{i}_{t+1}=\{M^{i}_{t},Y^{i}_{t},U^{i}_{t}\}\setminus Z^{i}_{t}$.

In this spacial case, the entire history of observations and control actions are shared periodically between controllers with period $s$. Hence, the above special case corresponds to the periodic sharing information structure considered in .

II-B4 Control Sharing Information Structure

Consider the following special case of the model of Section II-A.

The shared memory at the beginning of time $t$ is $C_{t}=\{\mathbf{U}_{1:t-1}\}$. The local memory at the beginning of time $t$ is $M^{i}_{t}=\{Y^{i}_{1:t-1}\}$.

At each time $t$, after taking the action $U^{i}_{t}$, controller $i$ sends $Z^{i}_{t}=\{U^{i}_{t}\}$ to the shared memory.

After sending $Z^{i}_{t}=U^{i}_{t}$ to the shared memory, controller $i$ updates the local memory to $M^{i}_{t+1}=Y^{i}_{1:t}$.

In this spacial case, the control actions of each controller are shared with every other controller after a delay of $1$ time step. Hence, the above special case corresponds to the control sharing information structure considered in .

II-B5 No Shared Memory with or without finite local memory

Consider the following special case of the model of Section II-A.

The shared memory at each time is empty, $C_{t}=\emptyset$ and the local memory at the beginning of time $t$ is $M^{i}_{t}=\{Y^{i}_{t-s:t-1},U^{i}_{t-s:t-1}\}$, where $s\geq 1$ is a fixed number.

Controllers do not send any data to shared memory, $Z^{i}_{t}=\emptyset$.

At the end of time $t$, controllers update their local memories to $M^{i}_{t+1}=\{Y^{i}_{t-s+1:t},U^{i}_{t-s+1:t}\}$.

In this special case, the controllers don’t share any data. The above model is related to the finite-memory controller model of . A related special case is the situation where the local memory at each controller consists of all of its past local observations and its past actions, that is, $M^{i}_{t}=\{Y^{i}_{1:t-1},U^{i}_{1:t-1}\}$.

All the special cases considered above are examples of symmetric sharing. That is, different controllers update their local memories according to identical protocols and the data sent by a controller to the shared memory is selected according to identical protocols. However, this symmetry is not required for our model. Consider for example, the delayed sharing information structure where at the end of time $t$, controller $i$ sends $Y^{i}_{t-s_{i}},U^{i}_{t-s_{i}}$ to the shared memory, with $s_{i},i=1,2,\ldots,n,$ being fixed, but not necessarily identical, numbers. This kind of asymmetric sharing is also a special case of our model. □

III Main Results

For centralized systems, stochastic control theory provides two important analytical results. Firstly, it provides a structural result. This result states that there is an optimal control strategy which selects control actions as a function only of the controller’s posterior belief on the state of the system conditioned on all its observations and actions till the current time. The controller’s posterior belief is called its information state. Secondly, stochastic control theory provides a dynamic programming decomposition of the problem of finding optimal control strategies in centralized systems. This dynamic programming decomposition allows one to evaluate the optimal action for each realization of the controller’s information state in a backward inductive manner.

In this section, we provide a structural result and a dynamic programming decomposition for the decentralized stochastic control problem with partial information sharing formulated above (Problem 1). The main idea of the proof is to formulate an equivalent centralized stochastic control problem; solve the equivalent problem using classical stochastic-control techniques; and translate the results back to the basic model. For that matter, we proceed as follows:

Formulate a centralized coordinated system from the point of view of a coordinator that observes only the common information among the controllers in the basic model, i.e., the coordinator observes the shared memory $C_{t}$ but not the local memories $(M^{i}_{t}$, $i=1,\dots,n)$ or local observations $(Y^{i}_{t}$, $i=1,\dots,n)$. The coordinator chooses prescriptions $\mathbf{\Gamma}_{t}=(\Gamma^{1}_{t},\dots,\Gamma^{n}_{t})$, where $\Gamma^{i}_{t}$ is a mapping from $(Y^{i}_{t},M^{i}_{t})$ to $U^{i}_{t}$, $i=1,\dots,n$.

Show that the coordinated system is a POMDP (partially observable Markov decision process).

For the coordinated system, determine the structure of an optimal coordination strategy and a dynamic program to find an optimal coordination strategy.

Show that any strategy of the coordinated system is implementable in the basic model with the same value of the total expected cost. Conversely, any strategy of the basic model is implementable in the coordinated system with the same value of the total expected cost. Hence, the two systems are equivalent.

Translate the structural results and dynamic programming decomposition of the coordinated system (obtained in stage 3) to the basic model.

Consider a coordinated system that consists of a coordinator and $n$ passive controllers. The coordinator knows the shared memory $C_{t}$ at time $t$, but not the local memories $(M^{i}_{t}$, $i=1,\dots,n)$ or local observations $(Y^{i}_{t}$, $i=1,\dots,n)$. At each time $t$, the coordinator chooses mappings $\Gamma^{i}_{t}:\mathcal{Y}^{i}_{t}\times\mathcal{M}^{i}_{t}\mapsto\mathcal{U}^{i}_{t}$, $i=1,2,\ldots,n$, according to

where $\mathbf{\Gamma_{t}}=(\Gamma^{1}_{t},\Gamma^{2}_{t},\ldots,\Gamma^{n}_{t})$. The function $d_{t}$ is called the coordination rule at time $t$ and the collection of functions $\mathbf{d}\coloneqq(d_{1},\dots,d_{T})$ is called the coordination strategy. The selected $\Gamma^{i}_{t}$ is communicated to controller $i$ at time $t$.

The function $\Gamma^{i}_{t}$ tells controller $i$ how to process its current local observation and its local memory at time $t$; for that reason, we call $\Gamma^{i}_{t}$ the coordinator’s prescription to controller $i$. Controller $i$ generates an action using its prescription as follows:

For this coordinated system, the system dynamics, the observation model and the cost are the same as the basic model of Section II-A: the system dynamics are given by (1), each controller’s current observation is given by (2) and the instantaneous cost at time $t$ is $l(X_{t},\mathbf{U}_{t})$. As before, the performance of a coordination strategy is measured by the expected total cost

where the expectation is with respect to a joint measure on $(X_{1:T},\mathbf{U}_{1:T})$ induced by the choice of $\mathbf{d}$.

In this coordinated system, we are interested in the following optimization problem:

For the model of the coordinated system described above, find a coordination strategy $\mathbf{d}$ that minimizes the total expected cost given by (11).

Stage 2: The coordinated system as a POMDP

We will now show that the coordinated system is a partially observed Markov decision process. For that matter, we first describe the model of POMDPs .

A partially observable Markov decision process consists of a state process $S_{t}\in\mathcal{S}$, an observation process $O_{t}\in\mathcal{O}$, an action process $A_{t}\in\mathcal{A}$, $t=1,2,\ldots,T$, and a single decision-maker where

The action at time $t$ is chosen by the decision-maker as a function of observation and action history, that is,

$d_{t}$ is the decision rule at time $t$.

After the action at time $t$ is taken, the new state and new observation are generated according to the transition probability rule

The optimization problem for the decision-maker is to choose a decision strategy $\mathbf{d}:=(d_{1},\ldots,d_{T})$ to minimize a total cost given as

The following well-known results provides the structure of optimal strategies and a dynamic program for POMDPs. For details, see .

Let $\Theta_{t}$ be the conditional probability distribution of the state $S_{t}$ at time $t$ given the observations $O_{1:t}$ and actions $A_{1:t-1}$,

$\Theta_{t+1}=\eta_{t}(\Theta_{t},A_{t},O_{t+1})$, where $\eta_{t}$ is the standard non-linear filter: If $\theta_{t},a_{t},o_{t+1}$ are the realizations of $\Theta_{t},A_{t}$ and $O_{t+1}$, then the realization of $s^{th}$ element of the vector $\Theta_{t+1}$ is

and $\eta_{t}(\theta_{t},a_{t},o_{t+1})$ is the vector $(\eta^{s}_{t}(\theta_{t},a_{t},o_{t+1}))_{s\in\mathcal{S}}$.

There exists an optimal decision strategy of the form

Further, such a strategy can be found by the following dynamic program:

We will now show that the coordinated system can be viewed as an instance of the above POMDP model by defining the state process as $S_{t}:=\{X_{t},\mathbf{Y}_{t},\mathbf{M}_{t}\},$ the observation process as $O_{t}:=\mathbf{Z}_{t-1},$ and the action process $A_{t}:=\mathbf{\Gamma}_{t}.$

Thus, the objective of minimizing (11) is same as minimizing

Recall that the coordinator is choosing its actions according to a coordination strategy of the form

Equation (23) and Lemma 1 imply that the coordinated system is an instance of the POMDP model described above.

Stage 3: Structural result and dynamic program for the coordinated system

Since the coordinated system is a POMDP, Theorem 1 gives the structure of the optimal coordination strategies. For that matter, define coordinator’s information state

For Problem 2, there is no loss of optimality in restricting attention to coordination rules of the form

Furthermore, an optimal coordination strategy of the above form can be found using a dynamic program. For that matter, observe that we can write

where $\eta_{t}$ is the standard non-linear filtering update function (see Appendix A). We denote by $\mathcal{B}_{t}$ the space of possible realizations of $\Pi_{t}$. Thus,

Recall that $F(\mathcal{Y}^{i}_{t}\times\mathcal{M}^{i}_{t},\mathcal{U}^{i}_{t})$ is the set of all functions from $\mathcal{Y}^{i}_{t}\times\mathcal{M}^{i}_{t}$ to $\mathcal{U}^{i}_{t}$ (see Section I-C). Then, we have the following result.

For all $\pi_{t}$ in $\mathcal{B}_{t}$, define

Then the $\arg\inf$ at each time step gives the coordinator’s optimal prescriptions for the controllers when the coordinator’s information state is $\pi$. □

Proposition 2 gives a dynamic program for the coordinator’s problem (Problem 2). Since the coordinated system is a POMDP, it implies that computational algorithms for POMDPs can be used to solve the dynamic program for the coordinator’s problem as well. We refer the reader to and references therein for a review of algorithms to solve POMDPs.

Stage 4: Equivalence between the two models

We first observe that since $C_{s}\subset C_{t}$, for all $s<t$, under any given coordination strategy $\mathbf{d}$, we can use $C_{t}$ to evaluate the past prescriptions by recursive substitution. For example, for $t=2,3$, the past prescriptions can be evaluated as functions of $C_{2}$, $C_{3}$ as follows:

The basic model of Section II-A and the coordinated system are equivalent. More precisely:

Given any control strategy $\mathbf{g}^{1:n}$ for the basic model, choose a coordination strategy $\mathbf{d}$ for the coordinated system of stage 1 as

Then $\hat{J}(\mathbf{d})=J(\mathbf{g}^{1:n})$.

Conversely, for any coordination strategy for the coordinated system, choose a control strategy $\mathbf{g}^{1:n}$ for the basic model as

where $\mathbf{\Gamma}_{k}=d_{k}(C_{k},\mathbf{\Gamma}_{1:k-1})$, $k=1,2,\ldots,t-1$ and $d^{i}_{t}(\cdot)$ is the $i$-th component of $d_{t}(\cdot)$ (that is, $d^{i}_{t}(\cdot)$ gives the coordinator’s prescription for the $i$-th controller). Then, $J(\mathbf{g}^{1:n})=\hat{J}(\mathbf{d})$.

Stage 5: Structural result and dynamic program for the basic model

Combining Proposition 1 with Proposition 3, we get the following structural result for Problem 1.

In Problem 1, there exist optimal control strategies of the form

where $\Pi_{t}$ is the conditional distribution on $X_{t},\mathbf{Y}_{t},\mathbf{M}_{t}$ given $C_{t}$, defined as

for all possible realizations $(x,\mathbf{y},\mathbf{m})$ of ($X_{t},\mathbf{Y}_{t},\mathbf{M}_{t}$). □

We call $\Pi_{t}$ the common information state. Recall that $\Pi_{t}$ takes values in the set $\mathcal{B}_{t}$ defined in (27).

Consider a control strategy $\mathbf{\hat{g}^{i}}$ for controller $i$ of the form specified in Theorem 2. The control law $\hat{g}^{i}_{t}$ at time $t$ is a function from the space $\mathcal{Y}^{i}_{t}\times\mathcal{M}^{i}_{t}\times\mathcal{B}_{t}$ to the space of decisions $\mathcal{U}^{i}_{t}$. Equivalently, the control law $\hat{g}^{i}_{t}$ can be represented as a collection of functions $\{\hat{g}^{i}_{t}(\cdot,\cdot,\pi)\}_{\pi\in\mathcal{B}_{t}}$, where each element of this collection is a function from $\mathcal{Y}^{i}_{t}\times\mathcal{M}^{i}_{t}$ to $\mathcal{U}^{i}_{t}$. An element $\hat{g}^{i}_{t}(\cdot,\cdot,\pi)$ of this collection specifies a control action for each possible realization of $Y^{i}_{t},M^{i}_{t}$ and a fixed realization $\pi$ of $\Pi_{t}$. We call $\hat{g}^{i}_{t}(\cdot,\cdot,\pi)$ the partial control law of controller $i$ at time $t$ for the given realization $\pi$ of the common information state $\Pi_{t}$.

We now use Proposition 2 to describe a dynamic programming decomposition of the problem of finding optimal control strategies. This dynamic programming decomposition allows us to evaluate optimal partial control laws for each realization $\pi$ of the common information state in a backward inductive manner. Recall that $\mathcal{B}_{t}$ is the space of all possible realizations of $\Pi_{t}$ (see (27)) and $F(\mathcal{Y}^{i}_{t}\times\mathcal{M}^{i}_{t},\mathcal{U}^{i}_{t})$ is the set of all functions from $\mathcal{Y}^{i}_{t}\times\mathcal{M}^{i}_{t}$ to $\mathcal{U}^{i}_{t}$ (see Section I-C).

Define the functions $V_{t}:\mathcal{B}_{t}\mapsto\mathds{R}$ , for $t=1,\dots,T$ as follows:

where $\eta_{t}$ is a $\mathcal{B}_{t+1}$-valued function defined in (26) and Appendix A.

III-A Comparison with Person by Person and Designer Approaches

The common information based approach adopted above differs from the person-by-person approach and the designer’s approach mentioned in the introduction. In particular, the structural result of Theorem 2 cannot be found by the person-by- person approach. If we fix strategies of all but the $i$th controller to an arbitrary choice, then it is not necessarily optimal for controller $i$ to use a strategy of the form in Theorem 2. This is because if controller $j$’s strategy uses the entire common information $C_{t}$, then controller $i$, in general, would need to consider the entire common information to better predict controller $j$’s actions and hence controller $i$’s optimal choice of action may too depend on the entire common information. The use of common information based approach allowed us to prove that all controllers can jointly use strategies of the form in Theorem 2 without loss of optimality.

The dynamic programming decomposition of Theorem 3 is simpler than any dynamic programming decomposition obtained using the designer’s approach. As described earlier, the designer’s approach models the decentralized control problem as an open-loop centralized planning problem in which a designer at each stage chooses control laws $g^{i}_{t}$ that map $(Y^{i}_{t},M^{i}_{t},C_{t})$ to $U^{i}_{t}$, $i=1,\dots,n$. On the other hand, the common-information approach developed in this paper models the decentralized control problem as a closed-loop centralized planning problem in which a coordinator at each stage chooses the partial control laws $\gamma^{i}_{t}$ that map $(Y^{i}_{t},M^{i}_{t})$ to $U^{i}_{t}$, $i=1,\dots,n$. The space of partial control laws is always smaller than the space of full control laws; if the common information is non-empty, then they are strictly smaller. Thus, the dynamic programming decomposition of Theorem 3 is simpler than that obtained by the designer’s approach. This simplification is best illustrated by the example of Section IV-C1 where all controllers receive a common observation $Y^{com}_{t}$. For this example, we show that our information state (and hence our dynamic program) reduce to $\mathds{P}(X_{t}|Y^{com}_{1:t})$, which is identical to the information state of centralized stochastic control. In contrast, the information state $\mathds{P}(X_{t},Y^{com}_{1:t})$ obtained by the designer’s approach is much more complicated.

III-B Special Cases: The Results

In Section II-B, we described several models of decentralized control problems that are special cases of the model described in Section II-A. In this section, we state the results of Theorems 2 and 3 for these models.

In the delayed sharing information structure of section II-B1, there exist optimal control strategies of the form

Moreover, optimal control strategies can be obtained by a dynamic program similar to that of Theorem 3. □

The above result is analogous to the result in .

III-B2 Delayed State Sharing Information Structure

In the delayed state sharing information structure of section II-B2, there exist optimal control strategies of the form

Moreover, optimal control strategies can be obtained by a dynamic program similar to that of Theorem 3. □

The above result is analogous to the result in .

III-B3 Periodic Sharing Information Structure

In the periodic sharing information structure of section II-B3, there exist optimal control strategies of the form

Moreover, optimal control strategies can be obtained by a dynamic program similar to that of Theorem 3. □

The above result gives a finer dynamic programming decomposition that . In , the dynamic programming decomposition is only carried out at the times of information sharing, $t=ks$, $s=1,2,\dots$; and at each step the partial control laws until the next sharing instant are chosen. In contrast, in the above dynamic program, the partial control laws of each step are chosen sequentially.

III-B4 Control Sharing Information Structure

In the control sharing information structure of section II-B4, there exist optimal control strategies of the form

Moreover, optimal control strategies can be obtained by a dynamic program similar to that of Theorem 3. □

III-B5 No Shared Memory with or without finite local memory

In the information structure of Section II-B5, there exist optimal control strategies of the form

Moreover, optimal control strategies can be obtained by a dynamic program similar to that of Theorem 3. □

This result is redundant since all control laws are of the above form. Nonetheless, Corollary 5 gives a procedure of finding such control laws using the dynamic program of Theorem 3.

The above result is similar to the results in for the case of one controller with finite memory and to those in for the case of two controllers with finite memories.

IV Simplifications and Generalizations

Theorems 2 and 3 identify the conditional probability distribution on $(X_{t},\mathbf{Y}_{t},\mathbf{M}_{t})$ given $C_{t}$ as the common information state for our problem. In the following lemma, we make the simple observation that in our model the conditional distribution on $(X_{t},\mathbf{Y}_{t},\mathbf{M}_{t})$ given $C_{t}$ is completely determined by the conditional distribution on $(X_{t},\mathbf{M}_{t})$ given $C_{t}$.

For any choice of control laws $\hat{g}^{1:n}_{1:t-1}$, define the conditional distribution on $X_{t},\mathbf{M}_{t}$ given $C_{t}$ as

for all possible realizations $(x,\mathbf{m})$ of ($X_{t},\mathbf{M}_{t}$). Also define $\mathcal{B}^{new}_{t}:=\Delta(\mathcal{X}_{t}\times\mathcal{M}^{i}_{t}\times\ldots\times\mathcal{M}^{n}_{t})$. Then,

Therefore, $\Pi^{new}_{t}=\chi_{t}(\Pi_{t})$, where each component of the $\mathcal{B}^{new}_{t}$- valued function $\chi_{t}$ is determined by the right hand side of (45). Also,

where the second term on right hand side of (46) is determined by the fixed distribution of the observations noises. Therefore, $\Pi_{t}=\zeta_{t}(\Pi^{new}_{t})$, where each component of the $\mathcal{B}_{t}$- valued function $\zeta_{t}$ is determined by the right hand side of (46). □

Lemma 2 implies that the results of Theorems 2 and 3 can be written in terms of $\Pi^{new}_{t}$.

In Problem 1, there exist optimal control strategies of the form

Further, define the functions $V^{new}_{t}:\mathcal{B}^{new}_{t}\mapsto\mathds{R}$ , for $t=1,\dots,T$ as follows:

where $\zeta_{t},\chi_{t}$ are defined in Lemma 2, and $\eta_{t}$ is defined in (26) and Appendix A.

For any $\pi^{new}\in\mathcal{B}^{new}_{t}$ and any $\pi\in\mathcal{B}_{t}$, it is straightforward to establish using a backward induction argument that $V^{new}_{t}(\pi^{new})=V_{t}(\zeta_{t}(\pi^{new}))$ and $V_{t}(\pi)=V^{new}_{t}(\chi_{t}(\pi))$, where $V_{t}(\cdot)$ is the value function from the dynamic program in Theorem 3. The optimality of the new dynamic program then follows from the optimality of the dynamic program in Theorem 3. ■

The result of Theorem 4 is conceptually the same as the results in Theorems 2 and 3. Theorem 4 implies that the Corollaries of Section III-B can be restated in terms of new information states by simply removing $Y_{t}$ from the definition of original information states. For example, the result of Corollary 1 for delayed sharing information structure is also true when $\Pi_{t}$ is replaced by

This result is simpler than that of [36, Theorem 2].

IV-B Generalization of the Model

The methodology described in Section III relies on the fact that the shared memory is common information among all controllers. Since the coordinator in the coordinated system knows only the common information, any coordination strategy can be mapped to an equivalent control strategy in the basic model (see Stage 4 of Section III). In some cases, in addition to the shared memory, the current observation (or if the current observation is a vector, some components of it) may also be commonly available to all controllers. The general methodology of Section 2 can be easily modified to include such cases as well.

Consider the model of Section II-A with the following modifications:

In addition to their current local observation, all controllers have a common observation at time $t$.

where $\{V_{t},t=1,\dots,T\}$ is a sequence of i.i.d. random variables with probability distribution $Q_{V}$ which is independent of all other primitive random variables.

The shared memory $C_{t}$ at time $t$ is a subset of $\{Y^{com}_{1:t-1},\mathbf{Y}_{1:t-1},\mathbf{U}_{1:t-1}\}$.

Each controller selects its action using a control law of the form

After taking the control action at time $t$, controller $i$ sends a subset $Z^{i}_{t}$ of $\{M^{i}_{t},Y^{i}_{t},U^{i}_{t},Y^{com}_{t}\}$ that necessarily includes $Y^{com}_{t}$. That is,

This implies that the history of common observations is necessarily a part of the shared memory, that is, $Y^{com}_{1:t-1}\subset C_{t}$.

The rest of the model is same as in Section II-A. In particular, the local memory update satisfies (7), so the local memory and shared memory at time $t+1$ don’t overlap. The instantaneous cost is given by $l(X_{t},U_{t})$ and the objective is to minimize an expected total cost given by (8).

The arguments of Section III are also valid for this model. The observation process in Lemma 1 is now defined as $R_{t+1}=\{\mathbf{Z}_{t},Y^{com}_{t+1}\}$. The analysis of Section III leads to structural results and dynamic programming decompositions analogous to Theorems 2 and 3 with $\Pi_{t}$ now defined as

Using an argument similar to Lemma 2, we can show that the result of Theorem 4 is true for the above model with $\Pi^{new}_{t}$ defined as

IV-C Examples of the Generalized Model

Consider the following special case of the above generalized model.

All controllers only make the common observation $Y^{com}_{t}$; controllers have no local observation or local memory.

The shared memory at time $t$ is $C_{t}=Y^{com}_{1:t-1}$. Thus, at time $t$, all controllers have identical information given as $\{C_{t},Y^{com}_{t}\}=Y^{com}_{1:t}$.

After taking the action at time $t$, each controller sends $Z^{i}_{t}=Y^{com}_{t}$ to the shared memory.

Recall that the coordinator’s prescription $\Gamma^{i}_{t}$ in Section III are chosen from the set of functions from $\mathcal{Y}^{i}_{t}\times\mathcal{M}^{i}_{t}$ to $\mathcal{U}^{i}_{t}$. Since, in this case $\mathcal{Y}^{i}_{t}=\mathcal{M}^{i}_{t}=\emptyset$, we interpret the coordinator’s prescription as prescribed actions. That is, $\Gamma^{i}_{t}\equiv U^{i}_{t}$. With this interpretation, the common information state becomes

and the dynamic program of Theorem 3 becomes

Since all the controllers have identical information, the above results correspond to the centralized dynamic program of Theorem 1 with a single controller choosing all the actions.

IV-C2 Coupled subsystems with control sharing information structure

Consider the following special case of the above generalized model.

The state of the system at time $t$ is a $(n+1)$-dimensional vector $X_{t}=(X^{1}_{t},X^{2}_{t},\dots,X^{n}_{t},X^{*}_{t})$, where $X^{i}_{t}$, $i=1,\dots,n$ corresponds to the local state of subsystem $i$, and $X^{*}_{t}$ is a global state of the system.

The state update function is such that the global state evolves according to

while the local state of subsystem $i$ evolves according to

where $\{N^{0}_{t},t=1,\dots T\},\ldots,\{N^{n}_{t},t=1,\dots T\}$ are mutually independent i.i.d noise processes that are independent of the initial state, $X_{1}=(X^{1}_{1},X^{2}_{1},\dots,X^{n}_{1},X^{*}_{1})$.

At time $t$, the common observation of all controllers is given by $Y^{com}_{t}=X^{*}_{t}$.

At time $t$, the local observation of controller $i$ is given by $Y^{i}_{t}=X^{i}_{t}$, $i=1,\dots,n$.

The shared memory at time $t$ is $C_{t}=\{X^{*}_{1:t-1},\mathbf{U}_{1:t-1}\}$. At each time $t$, after taking the action $U^{i}_{t}$, controller $i$ sends $Z^{i}_{t}=\{X^{*}_{t},U^{i}_{t}\}$ to the shared memory.

The above special case corresponds to the model of coupled subsystems with control sharing considered in , where several applications of this model are also presented. It is shown in that there is no loss of optimality in restricting attention to controllers with no local memory, i.e., $M_{t}=\emptyset$. With this additional restriction, the result of Theorems 1 and 2 apply for this model with $\Pi_{t}$ defined as

Note that $\Pi_{t}$ can be evaluated from $X^{*}_{t}$ and $\mathds{P}^{g^{1:n}_{1:t-1}}(X^{1}_{t},\ldots,X^{n}_{t}|X^{*}_{1:t},\mathbf{U}_{1:t-1})$. It is shown in that $X^{1}_{t},X^{2}_{t},\ldots,X^{n}_{t}$ are conditionally independent given $X^{*}_{1:t},\mathbf{U}_{1:t-1}$, hence the joint distribution $\mathds{P}^{g^{1:n}_{1:t-1}}(X^{1}_{t},\ldots,X^{n}_{t}|X^{*}_{1:t},\mathbf{U}_{1:t-1})$ is a product of its marginal distributions.

IV-C3 Broadcast information structure

Consider the following special case of the above generalized model.

The state of the system at time $t$ is a $n$-dimensional vector $X_{t}=(X^{1}_{t},X^{2}_{t},\dots,X^{n}_{t})$, where $X^{i}_{t}$, $i=1,\dots,n$ corresponds to the local state of subsystem $i$. The first component $i=1$ is special and called the central node. Other components, $i=2,\dots,n$, are called peripheral nodes.

The state update function is such that the state of the central node evolves according to

while the state of the peripheral nodes evolves according to

where $\{N^{i}_{t},i=1,2,\ldots n;t=1,\dots\}$ are noise processes that are independent across time and independent of each other.

At time $t$, the common observation of all controllers is given by $Y^{com}_{t}=X^{1}_{t}$.

At time $t$, the local observation of controller $i$, $i>2$, is given by $Y^{i}_{t}=X^{i}_{t}$. Controller 1 does not have any local observations.

No controller sends any additional data to the shared memory. Thus, the shared memory consists of just the history of common observations, i.e., $C_{t}=Y^{com}_{1:t-1}=X^{1}_{1:t-1}$.

The above special case corresponds to the model of decentralized systems with broadcast structure considered in . It is shown in that there is no loss of optimality in restricting attention to controllers with no local memory, i.e., $M_{t}=\emptyset$. With this additional restriction, the result of Theorems 1 and 2 apply for this model with $\Pi_{t}$ defined as

Note that $\Pi_{t}$ can be evaluated from $X^{1}_{t}$ and $\mathds{P}^{g^{1:n}_{1:t-1}}(X^{2}_{t},\ldots,X^{n}_{t}|X^{1}_{1:t})$. It is shown in that $X^{2}_{t},\ldots,X^{n}_{t}$ are conditionally independent given $X^{1}_{1:t}$, hence the joint distribution $\mathds{P}^{g^{1:n}_{1:t-1}}(X^{2}_{t},\ldots,X^{n}_{t}|X^{1}_{1:t})$ is a product of its marginal distributions.

V Extension to infinite horizon

In this Section, we consider the basic model of Section II-A with an infinite time horizon. Assume that

The state of the system, the observations and the control actions take value in time-invariant sets $\mathcal{X},\mathcal{Y}^{i},\mathcal{U}^{i}$, respectively.

The local memories $M^{i}_{t}$ and the updates to the shared memory $Z^{i}_{t}$ take values in time-invariant sets $\mathcal{M}^{i}$ and $\mathcal{Z}^{i}$ respectively.

The dynamics of the system (equation (1)) and the observation model (equation (2)) are time-homogeneous. That is, the functions $f_{t}$ and $h_{t}$ in equations (1) and (2) do not vary with time.

Let the cost of using a strategy $\mathbf{g}^{1:n}$ be defined as

where $\beta\in[0,1)$ is a discount factor. We can follow the arguments of Section III to formulate the problem of the coordinated system with an infinite time horizon. As in Section III, the coordinated system is equivalent to a POMDP. The time-homogeneous nature of the coordinated system and its equivalence to a POMDP allows us to use known POMDP results (see ) to conclude the following theorem for the infinite time horizon problem.

Consider Problem 1 with infinite time horizon and the objective of minimizing the expected cost given by equation (59). Then, there exists an optimal time-invariant control strategy of the form:

Furthermore, consider the fixed point equation,

Then, for any realization $\pi$ of $\Pi_{t}$, the optimal partial control laws are the choices of $\gamma^{i}$ that achieve the infimum in the right hand side of (61). □

All the special cases of our information structure considered in Sections II-B and IV-C can be extended to infinite horizon problems if the state, observation and actions spaces are time-invariant and the systems dynamics and observation equations are time homogeneous. The only exception is the control sharing information structure of section II-B4 where the local memory takes values in sets that are increasing with time.

VI Discussion and Conclusions

In centralized stochastic control, the controller’s belief on the current state of the system plays a fundamental role for predicting future costs. If the control strategy for the future is fixed as a function of future beliefs, then the current belief is a sufficient statistic for future costs under any choice of current action. Hence, the optimal action at the current time is only a function of current belief on the state. In decentralized problems where different controllers have different information, using a controller’s belief on the state of the system presents two main difficulties: (i) Since the costs depend both on system state as well as other controllers’ actions any prediction of future costs must involve a belief on system state as well as some means of predicting other controllers’ actions. (ii) Secondly, since different controllers have different information, the beliefs formed by each controller and their predictions of future costs cannot be expected to be consistent.

The approach we adopted in this paper tries to address these difficulties by using the fact that sharing of data among controllers creates common knowledge among the controllers. Beliefs based on this common knowledge are necessarily consistent among all controllers and can serve as a consistent sufficient statistic. Moreover, while controllers cannot accurately predict each other’s control actions, they can know, for the observed realization of common information, the exact mapping used by each controller to map its local information to control action. These considerations suggest that common information based beliefs and partial control laws should play an important role in a general theory of decentralized stochastic control problems. The use of a fictitious coordinator allows us to make these considerations mathematically precise. Indeed, the coordinator’s beliefs are based on common information and the coordinator’s decision are the partial control laws. The results of the paper then follow by observing that the coordinator’s problem can be viewed as a POMDP by identifying a new state that includes both the state of the dynamic system as well as the local information of the controllers.

The specific model of shared and local memory update that we assumed is crucial for connecting the coordinator’s problem to POMDPs and centralized stochastic control. A key assumption in centralized stochastic control is perfect recall, that is, the information obtained at any time is remembered at all future times. This is essential for the update of the beliefs in POMDPs. Our assumption that the shared memory is increasing in time ensures that the perfect recall property is true for the coordinator’s problem. If the shared memory did not have perfect recall (that is, if some past contents were lost over time), then the update of common information state in (26) would not hold and the results of Theorems 2 and 3 would not be true.

Another key factor in our result is that $S_{t}:=\{X_{t},\mathbf{Y}_{t},\mathbf{M}_{t}\}$ serves as a state for the coordinator’s problem. If the system state, observations and local memories take value in a time-invariant space, we have a state for the coordinator’s problem which takes value in a time-invariant space. Hence, the common information state is a belief on a time-invariant space. The local memory update in (7) ensures that $S_{t}$ is a state. If local memory update depended on shared memory as well, that is, if (7) were replaced by

then $S_{t}$ would no longer suffice as a state for the coordinator. In particular, the state update equations in Lemma 1 would no longer hold. The only recourse then would be to include $C_{t}$ as a part of the state which would necessarily mean that the state space keeps increasing with time. This is undesirable not only because large state spaces imply increased complexity, but the increasing size of state spaces also makes extensions of finite horizon results to infinite horizon problems conceptually difficult.

The connection between the coordinator’s problem and POMDPs can be used for computational purposes as well. The dynamic program of Theorem 3 is essentially a POMDP dynamic program. In particular, just as in POMDP, the value-functions are piecewise linear and concave in $\pi_{t}$. This characterization of value functions is utilized to find computationally efficient algorithms for POMDPs. Such algorithmic solutions to general POMDPs are well-studied and can be employed here. We refer the reader to and references therein for a review of algorithms to solve POMDPs.

While our results apply to a broad class of models, it would be worthwhile to identify special cases where the specific model features can be exploited to simplify our structural result. Examples of such simplification appear in . A common theme in many centralized dynamic programming solutions is to identify a key property of the value functions and use it to characterize the optimal decisions. Since our results also provide a dynamic program, an important avenue for future work would be to identify cases where properties of value functions can be analyzed to deduce a solution or to reduce the computational burden of finding the solution.

Our approach in this paper illustrates that common information provides a common conceptual framework for several decentralized stochastic control problems. In our model, we explicitly included a shared memory which naturally served the purpose of common information among the controllers. More generally, we can define common information for any sequential decision-making problem and then address the problem from the perspective of a coordinator who knows the common information. Such a common information based approach for general sequential decision-making problems is presented in .

VII Acknowledgments

This work was supported by NSERC through the grant NSERC-RGPIN 402753-11, by NSF through the grant CCF-1111061 and by NASA through the grant NNX09AE91G.

References

Consider a realization $c_{t+1}$ of the shared memory $C_{t+1}$ at time $t+1$. Let $(\mathbf{\gamma}_{1:t})$ be the corresponding realization of the coordinator’s prescriptions until time $t$. We assume the realization $(c_{t+1},\pi_{1:t},\mathbf{\gamma}_{1:t})$ to be of non-zero probability. Then, the realization $\pi_{t+1}$ of $\Pi_{t+1}$ is given by

Use Lemma 1 to simplify the above expression as

Since $c_{t+1}=(c_{t},\mathbf{z}_{t})$, write the last term of (63) as

Use Lemma 1 and the sequential order in which the system variables are generated to write the numerator as

where we dropped $\mathbf{\gamma}_{t}$ from conditioning in (65) since under the given coordinator’s strategy, it is a function of the rest of the terms in the conditioning. Substitute (66), (64), and (63) into (62), to get

where $\eta_{t}^{s}(\cdot)$ is given by (62), (63), (64), and (66). $\eta_{t}(\cdot)$ is the vector $(\eta^{s}_{t}(\cdot))_{s\in\mathcal{S}}$.

Appendix B Proof of Proposition 3

(a) For any given control strategy $\mathbf{g}^{1:n}$ in the basic model, define a coordinated strategy $\mathbf{d}$ for the coordinated system as

Consider Problems 1 and 2. Use control strategy $\mathbf{g}^{1:n}$ in Problem 1 and coordination strategy $\mathbf{d}$ given by (67) in Problem 2. Fix a specific realization of the primitive random variables $\{X_{1},W^{j}_{t},t=1,\dots,T,j=0,1,\dots,n\}$ in the two problems. Equation (2) implies that the realization of $\mathbf{Y}_{1}$ will be the same in the two problems. Then, the choice of $\mathbf{d}$ according to (67) implies that the realization of the control actions $\mathbf{U}_{1}$ will be the same in the two problems. This implies that the realization of the next state $X_{2}$ and the memories $\mathbf{M}_{2}$, $C_{2}$ will be the same in the two problems. Proceeding in a similar manner, it is clear that the choice of $\mathbf{d}$ according to (67) implies that the realization of the state $\{X_{t};\allowbreak t=1,\dots,T\}$, the observations $\{\mathbf{Y}_{t};\allowbreak t=1,\dots,T\}$, the control actions $\{\mathbf{U}_{t};\allowbreak t=1,\dots,T\}$ and the memories $\{\mathbf{M}_{t};\allowbreak t=1,\dots,T\}$ and $\{C_{t};\allowbreak t=1,\dots,T\}$ are all identical in Problem 1 and 2. Thus, the total expected cost under $\mathbf{g}^{1:n}$ in Problem 1 is same as the total expected cost under the coordination strategy given by (67) in Problem 2. That is, $J(\mathbf{g}^{1:n})=\hat{J}(\mathbf{d})$.

(b) The second part of Proposition 3 follows from similar arguments as above.

Appendix C Equivalence between the model of this paper and the model of [1]

We refer to the model of this paper as the PHS (partial history sharing) model and the model of as the CO (common observation) model. First, we describe the CO model and then show the both models are equivalent by showing that the PHS model is a special case of CO model and vice versa.

The following model was presented in ; we use a slightly different notation so that the notation matches with that of our paper.

Consider a system with $n$ controllers. Let $X_{t}$ denote the state of the system, $Z_{t}$ denote the common observation of all controllers, $Y^{i}_{t}$ denote the private observation of controller $i$, $M^{i}_{t}$ the contents of the memory of controller $i$, and $U^{i}_{t}$ the control action of controller $i$, $i=1,\dots,n$.

The system dynamics and observation equations are given by

where $\{X_{1},Q_{t},W^{i}_{t},i=0,\dots,n,t=1,\dots,T\}$ are independent random variables.

At time $t$, controller $i$ generates a control action and updates its memory as follows:

At each time an instantaneous cost $l_{t}(X_{t},U^{1:n}_{t})$ is incurred. The system objective is to choose a control strategy $g^{1:n}_{1:T}$ and a memory update strategy $r^{1:n}_{1:T}$ to minimize a total expected cost.

The PHS model is a special case of CO model

Consider the PHS model described in Sec II-A of the paper and define

The CO model is a special case of PHS model

In the CO model, the local observations $Y^{i}_{t}$ of controller $i$ depends on the control action $U^{1:i-1}_{t}$. This feature is not present in PHS model. Nonetheless, we can show that CO model is a special case of the PHS model by splitting time and assuming that in the PHS model only one controller acts at each time.

Define the following system variables for $\tau=1,\dots,nT$. For ease of notation, when $tn<\tau\leq(t+1)n$, we will write $\tau$ as $tn+i$. Thus, the system variables are defined for $t=1,\dots,T$ and $i=1,\dots,n$: