1

Linear Quadratic Mean Field Teams: Optimal and
Approximately Optimal Decentralized Solutions

arXiv:1609.00056v2 [] 17 Sep 2017

Jalal Arabneydi, Student Member, IEEE, and Aditya Mahajan, Senior Member, IEEE

Abstract—We consider team optimal control of decentralized
systems with linear dynamics, quadratic costs, and arbitrary
disturbance that consist of multiple sub-populations with exchangeable agents (i.e., exchanging two agents within the same
sub-population does not affect the dynamics or the cost). Such
a system is equivalent to one where the dynamics and costs
are coupled across agents through the mean-field (or empirical
mean) of the states and actions (even when the primitive random
variables are non-exchangeable). Two information structures are
investigated. In the first, all agents observe their local state and
the mean-field of all sub-populations; in the second, all agents
observe their local state but the mean-field of only a subset of the
sub-populations. Both information structures are non-classical
and not partially nested. Nonetheless, it is shown that linear
control strategies are optimal for the first and approximately
optimal for the second; the approximation error is inversely
proportional to the size of the sub-populations whose mean-fields
are not observed. The corresponding gains are determined by the
solution of K +1 decoupled standard Riccati equations, where K
is the number of sub-populations. The dimensions of the Riccati
equations do not depend on the size of the sub-populations; thus
the solution complexity is independent of the number of agents.
Generalizations to major-minor agents, tracking cost, weighted
mean-field, and infinite horizon are provided. The results are
illustrated using an example of demand response in smart grids.
Index Terms—Stochastic dynamic teams, multi-agent systems,
decentralized control, non-classical information structures, linear
quadratic systems, team theory, large-scale systems.

I. I NTRODUCTION
A. Motivation
Team optimal control of decentralized systems has been an
important research topic since the mid 1960s. Many of the
initial research results were negative and showed that even
simple dynamical systems with two agents can be difficult
to design—even in the celebrated linear quadratic Gaussian
(LQG) framework. In particular, non-linear strategies can
outperform the best linear strategy [2]; even if attention is
restricted to linear strategies, the best linear strategy may
not have a finite dimensional representation [3]. Since then,
various solution methodologies for the optimal control of
decentralized systems have been proposed and there has been
considerable progress in understanding the nature of system
dynamics and the information structure under which these
J. Arabneydi and A. Mahajan are with the Department of Electrical and
Computer Engineering, McGill University, Montreal, Quebec, Canada. Email:
jalal.arabneydi@mail.mcgill.ca and aditya.mahajan@mcgill.ca.
This research was funded by the Natural Sciences and Engineering Research
Council of Canada through Grant NSERC-RGPIN 402753-11.
Preliminary version of this paper [1] was presented at the 54th IEEE
Conference on Decision and Control (CDC), Osaka, Japan, 2015.

methodologies work. See [4] and references therein for an
overview.
In spite of this progress, there is a big gap between the
theory and applications of optimal decentralized control. On
the one hand, the envisioned applications—which include
networked control systems, swarm robotics, and modern power
systems—often consist of multiple interconnected dynamical
systems and controllers. On the other hand, explicit optimal
solutions are available only for systems with a few (often two
or three) controllers [5]–[7]. The model and results presented
in this paper attempt to reduce the gap between theory and
applications.
In particular, we study decentralized control systems in
which the dynamics and cost satisfy a property that we call
exchangeability. In a dynamical system, we say agents i and
j are exchangeable if exchanging (or interchanging) agents i
and j does not affect the dynamics or the cost (the formal
definition is given below). Or, equivalently, the dynamics and
the cost do not depend on the index assigned to the two agents.
In many applications of decentralized systems, the system
may be partitioned into sub-populations where all agents
within a sub-population are exchangeable.1 We call such
systems as systems with partially exchangeable agents. In
this paper, we develop a framework for the design of optimal
decentralized control for such systems.
B. System with partially exchangeable agents
To formally define exchangeability, consider a multi-agent
dynamical system where N denotes the set of agents. The
state and action of agent i, i ∈ N , at time t are denoted by xit
and uit , where xit ∈ X i and uit ∈ U i . Let xt = (xit )i∈N and
ut = (uit )i∈N denote the state and action of the entire system.
The dynamics are given by
xt+1 = ft (xt , ut , wt ),

(1)

where ft is system dynamics and {wt }t≥1 , where wt =
(wti )i∈N and wti ∈ W i , is the disturbance noise process. A
per-step cost ct (xt , ut ) is incurred at each time t.
For now, we do not specify the information structure as we
want to identify the system properties that do not depend on
the information structure.
1 For example, consider an aggregator that provides demand response as
a service by controlling the air conditioners in multiple neighborhoods in a
city. The air-conditioners could be partitioned into sub-populations based on
their tonnage and type (window, split, or packages AC). To the first-level
of approximation, all air conditioners with the same tonnage and type have
same dynamics and cost—and, therefore, are exchangeable. Similar situations
arise in swarm robotics (where the subpopulations correspond to robots with
different capabilities), and other engineering applications.

2

For any state x and agents i, j ∈ N , let σi,j x denote the
state when agents i and j are exchanged. For example, if x =
(x1 , x2 , x3 , x4 , x5 ), then σ2,4 x = (x1 , x4 , x3 , x2 , x5 ). Similar
interpretation holds for σi,j u and σi,j w.
Definition 1 (Exchangeable agents) A pair (i, j) of agents
is exchangeable if the following conditions hold:
1) X i = X j , U i = U j , and W i = W j , i.e., the states,
actions, and disturbances of agents i and j have the same
dimensions.
2) For any t, and any xt , ut , and wt ,

ft (σi,j xt , σi,j ut , σi,j wt ) = σi,j ft (xt , ut , wt ) ,
i.e., exchanging agents i and j does not affect the system
dynamics.
3) For any t, and any xt and ut ,
ct (σi,j xt , σi,j ut ) = ct (xt , ut ),
i.e., exchanging agents i and j does not affect the cost.
Definition 2 (Exchangeable set of agents) A set S of
agents, S ⊆ N , is exchangeable if every pair of agents in S
is exchangeable.
Definition 3 (System with partially exchangeable agents)
The multi-agent system described above is called a
system with partially exchangeable agents if the set N
of agents can be partitioned into K disjoint subsets N k ,
k ∈ K := {1, . . . , K}, such that for each k ∈ K, the set N k
of agents is exchangeable.
In this paper, we investigate optimal decentralized control
of linear quadratic system (i.e., a system where dynamics are
linear and the per-step cost is quadratic) with partially exchangeable agents. In a subsequent paper, we will investigate
systems with controlled Markovian dynamics.
C. Notation
For a set N , |N | denotes its size. For a matrix A, A|
denotes its transpose, Tr(A) denotes its trace; if A is square,
A ≥ 0 (respectively A > 0) denotes that A is positive semidefinite (respectively positive definite). For matrices A and B
of appropriate size, A ≤ B means B − A ≥ 0, diag(A, B)
denotes
a block diagonal matrix with diagonal terms A and B,
√
A denotes a matrix C such that2 C | C = A, A ◦ B denotes
Hadamard product, and A ⊗ B denotes Kronecker product.
For matrices A, B, and C with the same number of columns,
rows(A, B, C) denotes the matrix [A| , B | , C | ]| . For vectors
x, y, and z, vec(x, y, z) denotes the vector [x| , y | , z | ]| .
Superscripts index agents (indexed by i) or sub-populations
(indexed by k). Given a set N of agents and states xi , i ∈
N , bold x denotes vec(x1 , . . . , x|N | ); when all states are
of the same dimension, h(xi )i∈N i denotes the mean-field
P|N | i
1
i
i=1 x of (x )i∈N . For vectors and matrices, we use
|N |
the short hand notation x1:t or A1:t to denote (x1 , . . . , xt )
and (A1 , . . . , At ), respectively.
√
that sometimes A is defined as a matrix C such that CC = A.
We are not using that definition here.

R, R≥0 , and R>0 denote the sets of real, non-negative real,
and positive real numbers, respectively. 1n×m denotes n × m
matrix of ones, In denotes n × n identity matrix. We omit the
subscripts when the dimensions are clear from the context.
For a random variable x, E[x] and var(x) denote its mean
and variance, respectively.
Given horizon T and matrices A1:T and Q1:T , the notation
M1:T = DLET (A1:T , Q1:T ) means that M1:T is the solution
of the finite horizon discrete Lyapunov equation, i.e., MT =
|
QT , and for t ∈ {T − 1, . . . , 1}, Mt = At Mt+1 At + Qt .
Similarly, given a horizon T and matrices A1:T ,
B1:T , Q1:T , and R1:T , the notation M1:T
=
DRET (A1:T , B1:T , Q1:T , R1:T ) means that M1:T is
the solution of the finite horizon discrete Riccati
equation, i.e., MT = QT , and for t ∈ {T − 1, . . . , 1},
−1
Mt = −A|t Mt+1 Bt (Bt| Mt+1 Bt + Rt ) Bt| Mt+1 At +
|
At Mt+1 At + Qt .
Given a discount factor β ∈ (0, 1] and matrices A, B, Q,
and R, the notation M = DALEβ (A, Q) means that M is the
solution of the discrete algebraic Lyapunov equation
|

M = βA M A + Q.
and the notation M = DAREβ (A, B, Q, R) means that M is
the solution of the discrete algebraic Riccati equation
−1 |
|
|
|
M = −βA M B B M B + β −1 R
B M A+βA M A+Q.

II. P ROBLEM FORMULATION AND LITERATURE OVERVIEW
A. Linear quadratic system with partially exchangeable
agents
1) System Model: Suppose the dynamics (1) are linear, i.e.,
xt+1 = At xt + Bt ut + wt ,

(2)

where At and Bt are matrices of appropriate dimensions
and {x1 , {wt }Tt=1 } are random variables defined on a common probability space. The cost is quadratic, i.e., for t ∈
{1, . . . , T − 1},
|

|

ct (xt , ut ) = xt Qt xt + ut Rt ut ,
and t = T ,

|

cT (xT ) = xT QT xT ,

(3)
(4)

where Qt and Rt are matrices of appropriate dimensions.
Furthermore, assume that the above system is partially exchangeable, i.e., agents N can be partitioned into K disjoint
sub-populations N k , k ∈ K := {1, . . . , K}, such that for each
k ∈ K, the agents N k are exchangeable. Moreover, for any
sub-population k ∈ K and agent i ∈ N k , state xit takes values
k
k
in Rdx and action uit takes values in Rdu .
The mean-field of states3 x̄kt of sub-population k, k ∈ K,
is defined as the empirical mean of the states of all agents in
that sub-population, i.e.,
1 X i
xt , k ∈ K.
x̄kt := h(xit )i∈N k i =
|N k |
k
i∈N

2 Note

3 In

the sequel, we refer to mean-field of the states simply as mean field.

3

Similarly, the mean-field of the actions ūkt of sub-population
k, k ∈ K, is defined as the empirical mean of the actions of
all agents in that sub-population, i.e.,
1 X i
ūkt := h(uit )i∈N k i =
ut , k ∈ K.
|N k |
k
i∈N

The mean-field of states and actions of the entire population
are denoted by x̄t and ūt respectively, i.e.,
x̄t =

vec(x̄1t , . . . , x̄K
t ),

ūt =

vec(ū1t , . . . , ūK
t ).

For ease of reference, the notation is summarized in Table I.
TABLE I
S UMMARY OF THE NOTATION USED IN THIS PAPER .
Notation used for agent i ∈ N k belonging to sub-population k ∈ K
k

xit ∈ Rdx
k
uit ∈ Rdu

Iti = (xi1:t , ui1:t−1 , x̄1:t ).

(MFS-IS)

In the second information structure, which we call partial
mean field sharing and denote by PMFS-IS, there exists a
subset S of the sub-populations K such that every agent i ∈ N
perfectly observes its local state xit and the mean-fields of subpopulations S, i.e., {x̄kt }k∈S . We use S c to denote K\S. The
data Iti available to agent i at time t is given by
Iti = (xi1:t , ui1:t−1 , (x̄k1:t )k∈S ).

State of agent i
Action of agent i

(PMFS-IS)

Under both information structures, agent i chooses uit as
follows:
uit = gti (Iti ).
(8)

Notation used for sup-population k ∈ K = {1, . . . , K}
Nk
x̄kt = h(xit )i∈N k i
ūkt = h(uit )i∈N k i

2) Observation model and information structure: We consider two information structures; in both, agents perfectly
recall all data that they observe. In the first information
structure, which we call mean field sharing and denote by
MFS-IS, every agent i ∈ N perfectly observes its local state
xit and the global mean-field x̄t . Thus, the data Iti available
to agent i at time t is given by

Entire sub-population k
Mean-field of states at time t
Mean-field of actions at time t

Notation used for entire population
S
N = k∈K N k
Entire population
xt = (xit )i∈N
Joint state of entire population at time t
ut = (uit )i∈N
Joint action of entire population at time t
x̄t = vec(x̄1t , . . . , x̄K
t ) Mean-field of states of entire population at t
ūt = vec(ū1t , . . . , ūK
t ) Mean-field of actions of entire population at t

The function gti is called the control law of agent i at time t.
The collection gi = (g1i , g2i , . . . , gTi ) is called the control
strategy of agent i. The collection g = (gi )i∈N is called the
control strategy of the system. The performance of strategy g
is given by

 TX
−1
g
ct (xt , ut , x̄t , ūt ) + cT (xT , x̄T ) ,
(9)
J(g) = E
t=1

Proposition 1 In the linear quadratic system with partially
exchangeable agents described above, there exist matrices {Akt , Btk , Dtk , Etk , Qkt , Rtk }k∈K and Ptx and Ptu such that
the dynamics of agent i ∈ N k of sub-population k, k ∈ K,
may be written as
xit+1 = Akt xit + Btk uit + Dtk x̄t + Etk ūt + wti ;

(5)

the per-step cost at time t ∈ {1, . . . , T −1}, may be written as
|

|

ct (xt , ut , x̄t , ūt ) = x̄t Ptx x̄t + ūt Ptu ūt
i
X X 1 h
i | k i
i | k i
Q
R
(x
)
x
+
(u
)
u
+
t
t t
t
t t ; (6)
|N k |
k
k∈K i∈N

and the per-step cost at time t = T , may be written as
X X 1
|
|
cT (xT , x̄T ) = x̄T PTx x̄T +
(xiT ) QkT xiT . (7)
k|
|N
k
k∈K i∈N

The proof is presented in Appendix A.
Remark 1 In general, the matrices (Akt , Btk , Dtk , Etk , Qkt , Rtk )
and (Ptx , Ptu ) may depend on the number {|N k |}k∈K of
agents in the sub-populations, but their dimensions do not.
Thus, any linear quadratic system with partial exchangeable
agents—irrespective of the information structure—is equivalent to a mean-field coupled system with the same information
structure. In the rest of this paper, we investigate the optimal
control of such systems under the following two information
structures.

where the expectation is with respect to the measure induced
on all the system variables by the choice of strategy g.
3) The optimization problem: We are interested in the
following optimization problem.
Problem 1 In the model described above, find a strategy g∗
that minimizes (9), i.e.,
J ∗ := J(g∗ ) = inf J(g),
g

where the infimum is taken over all strategies of form (8).
B. Conceptual difficulties
There are several conceptual difficulties in solving Problem 1 because it has a non-classical information structure.
Information structure refers to the set of information known
to all agents at all times. If every decision maker knows the
observations and actions of all decision makers that acted before it, then the information structure is said to be classical; if
every decision maker knows the observations and actions of all
decision makers whose actions effect its observations, then the
information structure is said to be partially nested; otherwise,
the information structure is said to be non-classical [8], [9].
For linear quadratic systems with classical or partially nested
information structures, when the primitive random variables
are jointly Gaussian, the optimal control action is a linear (or
affine) function of the observations4 . This is not necessarily
4 In classical information structure with state feedback, the optimal control
action is linear function of the state and this result holds even when the
primitive random variables are not Gaussian.

4

the case when the information structure is non-classical as
is illustrated by the Witsenhausen counterexample [2], which
presents a linear quadratic Gaussian model with non-classical
information structure where non-linear strategies outperform
the best linear strategy. The model presented in this paper is
neither classical nor partially nested nor the primitive random
variables are necessarily Gaussian, so it is not known a priori
whether there is no loss of optimality in restricting attention
to linear strategies.
Even when linear strategies are not optimal, sometimes
attention is restricted to linear strategies because they are
simple and easy to implement. For systems with non-classical
information structure, the problem of finding the best linear
strategy need not be convex; it is convex only for special
sparsity pattern such as funnel causality [10] and quadratic
invariance [11]. Furthermore, as is illustrated by the Whittle
and Rudge counterexample [3], even when the problem of
finding the best linear strategy is convex, the best linear
strategy might not have a finite dimensional representation.
Finally, the usual curse of dimensionality is exasperated
in systems with non-classical information structure. Even in
systems with finite state and action spaces, the complexity
of finding the optimal control strategy belongs to NEXP
complexity class [12].
C. Contributions of the paper
1) We show that linear control laws are team optimal
for MFS-IS (even when the noise processes are not
Gaussian). As argued earlier, MFS-IS does not fall
into the class of information structures for which linear
strategies are known to be optimal. We show that the
corresponding gains are computed by solving K + 1
decoupled Riccati equations (where K is the number of
sub-populations) (Theorem 1).
2) We propose a certainty equivalence linear strategy for
PMFS-IS and show that the error satisfies a Lyapunov
equation. The approximation error converges to zero at
a rate that is inversely proportional to the number of
agents in the sub-populations whose mean-fields are not
observed (Theorem 2).
3) The salient feature of our main results is that the solution
complexity does not depend on the number of agents
in each sub-population; rather, it only depends on the
number of sub-populations. Furthermore, the optimal
gains can be computed in a decentralized manner such
that each agent simply needs to solve at most two (rather
than all) Riccati equations.
4) We show that our results generalize to variations of the
basic model that are not partially exchangeable including: systems where the objective is to optimally track
reference trajectories (Sec. IV-C) and systems where
agents have individual weights (Sec. IV-D).
5) When the dynamics and the per-step cost are timehomogeneous, we show that our results extend to infinite
horizon setups: both for the discounted cost setup with
any discount factor in (0, 1) and for average-cost per
unit time setup. For both setups, the optimal control

strategy for MFS-IS and the approximately optimal
control strategy for PMFS-IS are time-homogeneous and
the corresponding gains are computed by solving K + 1
decoupled algebraic Riccati equations.
D. Literature overview
Our model and results for MFS-IS are similar in spirit to
those obtained in [13] under stronger modeling assumptions.
In [13], the authors consider a homogeneous population of
dynamically decoupled agents which are coupled in the cost
through a weighted mean-field term. Two models are investigated: (a) hard-constraint model where the weighted meanfield of actions must equal a pre-specified linear function
of the weighted mean-field of states; and (b) soft-constraint
model where the above hard constraint is relaxed by penalizing
it in the cost. For both models, the authors show that the
optimal centralized control laws are linear in the local state
and the mean field; the corresponding gains are computed
by two decoupled Riccati equations. In section IV-D, we
generalize our results to the case when a weighted empirical
mean field is shared. In contrast to [13], we consider multiple
sub-populations and allow agents to be coupled in dynamics.
Note that approximation results similar to those for partial
mean-field sharing were not considered in [13].
Our results have similar features to those obtained for
centralized linear quadratic mean-field control [14], [15]. In
these models, the dynamics and the cost depend on the
statistical mean-field of the state and action. Such a model
may be viewed as a special case of our model when we restrict
to a single homogeneous sub-population and consider the limit
of infinite number of agents (and therefore the empirical mean
and the statistical mean are the same). Our proof technique,
which relies on a simple change of variables, is conceptually
simpler than that of [14], [15].5 It is worth highlighting that
the linear quadratic mean-field control model is a centralized
control problem and the results of [14], [15] do not apply to
the multi-agent models that we consider.
Recently, an iterative bidding strategy was proposed in [17]
for the optimal control multi-agent systems with decoupled dynamics that are coupled through a constraint. For LQG agents,
the scheme operates as follows: at each time, a coordinator sets
a price profile for all future times; agents submit a bid profile
for all future times; the coordinator updates the prices and
the process continues until the bids have converged. Agents
choose the first value of their bid as their action and the above
process is repeated at the next time step. In this scheme, agents
do not need to know the system dynamics of other agents. In
contrast, we assume that the system dynamics are common
knowledge to all agents. However, in our model, agents only
need to share the mean-field of their states (which can be
computed using a consensus algorithm) rather than iteratively
sharing the bid profile for all future times.
A decomposition-coordination approach for optimal decentralized control of deterministic linear quadratic systems was
5 In [14], first coupled forward and backward stochastic differential equations are derived and then they are decoupled into two Riccati equations using
the four step technique of [16]. In [15], a matrix dynamical optimization
method is used.

5

proposed in [18], [19]. This is an iterative approach. Each
iteration consists of two steps: (i) a decomposition step in
which each agent assumes decoupled dynamics and costs and
computes its local control trajectory by solving an optimal
tracking problem from pre-specified linear offsets for the
dynamics and a reference trajectory for the cost; (ii) a coordination step in which the linear offsets for the dynamics and
reference trajectories for the cost are computed for all agents
from the pre-specified control trajectories. It is shown that this
iterative process converges to the optimal centralized solution.
In contrast to such decomposition-coordination methods, our
proposed solution is not iterative. The optimal gains for all
agents are computed in a single step by solving Riccati
equations. Furthermore, our solution methodology works for
deterministic as well as stochastic systems.
A related solution approach called mean-field games (MFG)
was proposed in [20]–[28] to compute approximate Nash
equilibrium for large population games. The main idea is to
assume an infinite large size of each sub-population and solve
a set of two coupled equations: a Hamilton-Jacobi-Bellman
(HJB) equation to compute the best response of a generic
agent playing against a “mass trajectory” and a Fokker-PlanckKolmogorov (FPK) equation to compute the mass trajectory
from the strategy of a generic agent. It is shown that a solution
to these equations exists under appropriate conditions. The
resulting strategies are ε-Nash when the sub-populations
are
√
finite, where the approximation error is O(1/ n), where n
denotes the size of the smallest sub-population. For linear
quadratic systems, the coupled HJB-FPK equations simplify to
K Riccati equations and two coupled forward and backward
ODEs. In contrast, in our solution there is an additional Riccati
equation instead of the coupled forward-backward equations.
The coupled equations in MFG depend on the initial meanfield while the Riccati equations in our solution do not. The
key difference between our results and the results in the
MFG literature is that we obtain team optimal strategies of a
decentralized control problem while in the MFG literature one
typically obtains either Nash or Markov perfect equilibrium
strategies of a large population dynamic game problem. These
solution concepts are different.

linear equations.6 In contrast, when the system dynamics are
coupled, the information structure is non-classical and there
is no general solution methodology to obtain a team-optimal
solution.
III. M AIN R ESULTS
A. Exact solution for MFS-IS
We impose following standard assumptions on the model
described in Proposition 1:
Assumption (A1) The
primitive
random
variables
{x1 , {wt }Tt=1 } have zero mean, finite variance, and are
mutually independent.
Remark 2 Note that we do not require the primitive random
variables to be Gaussian. Nor do we require the initial state
x1 and the disturbance wt to be independent or exchangeable
across agents.
Assumption (A2) For every t, Ptx , Ptu , Qkt , and Rtk are
symmetric matrices that satisfy
Qkt ≥ 0, ∀k ∈ K,

x
diag(Q1t , . . . , QK
t ) + Pt ≥ 0, (10)

Rtk > 0, ∀k ∈ K,

diag(Rt1 , . . . , RtK ) + Ptu > 0. (11)

Note that matrices Ptx and Ptu are not required to be positive
semi-definite as long as (10)–(11) hold.
Theorem 1 Under (A1), (A2), and (MFS-IS), we have the
following results for Problem 1.
1) Structure of optimal strategy: The optimal strategy for
Problem 1 is unique and is linear in the local state and
the mean-field of the system. In particular,
uit = L̆kt (xit − x̄kt ) + L̄kt x̄t ,

(12)

−1
are obtained by the sowhere the gains {L̆kt , L̄kt }Tt=1
lution of K + 1 Riccati equations given below: one
for computing each L̆kt , k ∈ K, and one for L̄t :=
rows(L̄1t , . . . , L̄K
t ).
2) Riccati equations: Let
1
K
Āt := diag(A1t , . . . , AK
t ) + rows(Dt , . . . , Dt ),

The approach of mean-field games was used to obtain team
optimal solution of linear quadratic systems with decoupled
dynamics in [29]. It is shown that
√ the MFG solution is εsocially optimal (with ε ∈ O(1/ n)). We obtain a similar
result for dynamically coupled agents with ε ∈ O(1/n).
It should be noted that identifying team-optimal control
laws for systems with coupled dynamics is significantly more
challenging than for systems with decoupled dynamics. This
is because, when the agent dynamics are decoupled (and
the primitive random variables are Gaussian), the information
structure is partially nested, so one may restrict attention to
linear strategies. Furthermore, for a finite horizon system,
team-optimal strategies may be obtained by solving a set of

B̄t := diag(Bt1 , . . . , BtK ) + rows(Et1 , . . . , EtK ),
Q̄t := diag(Q1t , . . . , QK
t ),

R̄t := diag(Rt1 , . . . , RK ).

Then, for t ∈ {1, . . . , T − 1}, define:

−1
|
|
k
k
L̆kt = − (Btk ) M̆t+1
Btk + Rtk
(Btk ) M̆t+1
Akt ,
−1 |
|
L̄t = − B̄t M̄t+1 B̄t + R̄t + Ptu
B̄t M̄t+1 Āt ,
6 It is shown in [9] that a finite horizon system with partially nested
information structure may be converted to a static team by an appropriate
change of variables. The optimal control laws for such a static team may
be obtained by solving a set of linear equations [30]. The key conceptual
challenge in such problem is to identify sufficient statistics such that the
optimal control laws can be computed efficiently and the results can generalize
to infinite-horizon setup.

6

where {M̆tk }Tt=1 and {M̄t }Tt=1 are the solutions of
following Riccati equations:
k
M̆1:T

=

k
k
DRET (Ak1:T , B1:T
, Qk1:T , R1:T
),
x
DRET (Ā1:T , B̄1:T , Q̄1:T + P1:T , R̄1:T

where
Stx := rows(Stx,1 , . . . , Stx,K ),

Stu := rows(Stu,1 , . . . , Stu,K ).

(13)

Remark 5 We assumed that there are no cross-terms of the
u
+ P1:T
). form x| Su in the per-step cost of (3) and (4). If such cross(14) terms are present, there will be cross-terms involving (xi , ui ),
t
t
3) Optimal performance: Let
(xit , ūt ), (x̄t , uit ), and (x̄t , ūt ) in the equivalent mean-field
model presented in Proposition 1. These cross-terms can be
1 X
var(wti − w̄tk ), Σ̄t := var(w̄t ),
Σ̆kt :=
treated in the standard manner as cross-terms are treated in
k
|N |
i∈N k
centralized LQR.
1 X
i
k
k
:=
:=
var(x1 − x̄1 ), Ξ̄
var(x̄1 ).
Ξ̆
Remark 6 Suppose in addition to (A1), we have that
|N k |
i∈N k
{xi1 , {wti }t≥1 }i∈N are independent and for any k ∈ K,
(xi1 )i∈N k is i.i.d. with variance Ξk and {wti }i∈N k is i.i.d. with
Then, the optimal cost is given by
X
variance Σkt . Then, we have
∗
k
k
J =
Tr(Ξ̆ M̆1 ) + Tr(Ξ̄M̄1 )
|N k | − 1 k
k∈K
Σt ,
Σ̄t = diag(Σ1t , . . . , ΣK
Σ̆kt =
t ),
k|


|N
T
−1
X X
k
+
Tr(Σ̆kt M̆t+1
) + Tr(Σ̄t M̄t+1 ) . (15)
|N k | − 1 k
Ξ̆k =
Ξ ,
Ξ̄ = diag(Ξ1 , . . . , ΞK ).
t=1 k∈K
|N k |
The proof is presented in Section V. Note that the dimen- The expression of total cost (15) can be simplified accordingly.
sions of Riccati equations (13) and (14) do not depend on
the sizes of the sub-populations (|N 1 |, . . . , |N K |). Hence, the
solution complexity depends only on the number K of sub- B. Approximate solution for PMFS-IS
In this section, we consider Problem 1 under PMFS-IS.
populations and it is independent of the number of agents
Based
on the results of Theorem 1, we propose a certainty
in each sub-population. To implement the optimal control
equivalence
strategy for PMFS-IS and show that the perforstrategies:
mance
of
this
strategy is close to the optimal performance
• all agents must compute L̄1:T −1 by solving the Riccati
under
MFS-IS.
We impose the following assumptions on the
equation (14),
k
model.
• agents of sub-population k must compute L̆1:T −1 by
solving the Riccati equation (13).
Assumption (A1a) In addition to (A1), for any k ∈ S and
Then, an individual agent i of sub-population k, upon observ- k 0 ∈ S c , initial states (xi1 )i∈N k are independent of (xj1 )j∈N k0 .
ing the local state xit and the global mean-field x̄t , chooses
(A1b) The
primitive
random
variables
its local control action according to (12). Note that each agent Assumption
i
i T
}
}
are
independent.
For
any
k,
k
∈ K,
{x
,
{w
i∈N
t t=1
1
needs to solve only two Riccati equations, although there are
k
k
such
that
and
c
there
exist
finite
matrices
c
w
x
K + 1 Riccati equations in Theorem 1.
i
k
sup var(x1 ) ≤ cx ,
sup var(wti ) ≤ ckw .
Remark 3 An interesting feature of the solution is that all
M̄1:T =

agents in a particular sub-population use identical control laws.
This is a feature of the linear quadratic system and not of
exchangeability.7
Remark 4 If the per-step cost has cross-terms involving
(xit , x̄t ) and (uit , ūt ), i.e.,
i
X X 1 h
i | x,k
i | u,k
(x
)
S
x̄
+
(u
)
S
ū
t
t
t
t
t
t
|N k |
k
k∈K i∈N

then, this cost can be re-written in the form of (6) and (7):
|

|

x̄t Stx x̄t + ūt Stu ūt
7 The following example (which is based on an example presented in [31])
shows that asymmetric control strategies may outperform symmetric ones
even in systems with exchangeable agents. Consider a system with 2 agents
that runs for a horizon 2. Let X = U = {1, 2} and suppose the initial
state (x11 , x21 ) is uniformly distributed over all possible values. Suppose the
dynamics are xi2 = ui1 , i ∈ {1, 2} and the costs are c1 (x1 , u1 ) = 0
and c2 (x2 , u2 ) is C when {x12 = x22 } (where C is a positive number)
and 0 otherwise. The above system is exchangeable. Any symmetric control
strategy puts positive probability on the event {u11 = u21 } (and, hence on the
event {x12 = x22 }) and, therefore, has a positive expected cost. On the other
hand, the asymmetric strategy ui1 = i has zero cost. Thus, symmetric control
strategies are not optimal.

i∈N k

t≤T,i∈N k

Assumption (A3) The dynamics {Akt , Btk , Dtk , Etk }k∈K , cost
{Qkt , Rtk , }k∈K , Ptx and Ptu , and covariance bounds
{ckx , ckw }k∈K do not depend on the sizes (|N 1 |, . . . , |N K |) of
the sub-populations.
Since we are comparing the system performance under two
information structures, we use different notation for the two.
Under MFS-IS, the state and action of agent i are denoted by
xit and uit . Assume that uit is generated as per Theorem 1.
Under PMFS-IS, the state and action of agent i are denoted
by sit and vti . The dynamics are same as (5). In particular for
agent i of sub-population k ∈ K, si1 = xi1 and
sit+1 = Akt sit + Btk vti + Dtk s̄t + Etk v̄t + wti ,

(16)

where
s̄t = vec(s̄1t , . . . , s̄K
t ),

s̄kt = h(sit )i∈N k i,

v̄t = vec(v̄t1 , . . . , v̄tK ),

v̄tk = h(vti )i∈N k i.

Define a (mean-field) approximation process {zt }Tt=1 as
follows: zt = vec(zt1 , . . . , ztK ), where for any k ∈ K,

7

k

ztk ∈ Rdx ; the initial state z1 is given by z1k is s̄k1 for k ∈ S
and is 0 for k ∈
/ S.8 The process evolves as:
(
s̄kt+1 ,
k ∈ S,
k
(17)
zt+1
=
Akt ztk + (Btk L̄kt + Dtk + Etk L̄t )zt , k ∈ S c ,
where L̄t is as defined in Theorem 1. Note that the approximation process {zt }Tt=1 is adapted to the filtration {{s̄kt }k∈S }Tt=1
which is known at all agents. Therefore, at time t, zt can be
computed at all agents.
Now, consider the following certainty equivalence strategy
for PMFS-IS: for agent i of sub-population k, k ∈ K,
vti = L̆kt (sit − ztk ) + L̄kt zt .

(18)

The above strategy is similar to the optimal strategy for
MFS-IS (given by (12) in Theorem 1) except that the mean
field {s̄kt }k∈K has been replaced byPits approximation zt .
For ease of exposition, let dx := k∈K dkx and matrix H =
rows(H 1 , . . . , H K ) be a binary matrix such that
(
0dkx ×dx , k ∈ S,
Hk =
1dkx ×dx , k ∈ S c .
Let Jˆ denote the performance of strategy (18) and J ∗ denote
the optimal performance under MFS-IS. Then, the difference
in performance Jˆ − J ∗ is bounded. In particular, we have
Theorem 2 Assume (A1a), (A2), and (PMFS-IS). Then,
1) The performance loss is given by
Jˆ − J ∗ = Tr(X̃1 M̃1 ) +

T
−1
X

Tr(W̃t M̃t+1 ),

(19)

t=1

where X̃1 = 12dx ×2dx ⊗ [H ◦ var(x̄1 )], W̃t =
12dx ×2dx ⊗ [H ◦ var(w̄t )], and M̃1:T is the solution of
following Lyapunov equation:
M̃1:T = DLET (Ã1:T , Q̃1:T ),

(20)

where

Ã =

Ã1t
0

−(1dx ×dx − H) ◦ Ã2t
H ◦ Ã2t


,

and Q̃t = diag(−Q̃1t , Q̃2t ) where Ã1t = Āt + B̄t L̄t ,
Ã2t = Āt + B̄t L̆t , Q̃1t = Ptx + Q̄t + L̄|t (Ptu + R̄t )L̄t ,
Q̃2t = Ptx +Q̄t +L̆|t (Ptu +R̄t )L̆t , and L̆t = diag(L̆1t , . . . ,
L̆K
t ).
2) Let n = mink∈S c (|N k |). Under (A1b) and (A3),
 
T
∗
ˆ
J −J ∈O
.
n
The result is proved in Section VI.
Remark 7 As the number of agents in each sub-population
k ∈ S c , becomes large, the approximation error Jˆ − J ∗ goes
to zero; therefore, PMFS-IS is as informative as MFS-IS.
Note that when the mean-field of all sub-populations are
shared, then S = K and, therefore, H is zero. Consequently,
8 If

the initial states are non-zero mean, then z1k = E(x̄k1 ) for k ∈
/ S.

the approximation error given by (19) is zero. Hence, the result
of Theorem 2 is consistent with that of Theorem 1.
Corollary 1 When the mean-field is not shared, i.e., S = ∅,
the approximation error Jˆ − J ∗ is
−1
 TX

2
1
Tr var(x̄1 )(M̃12 − M̃11 ) +
Tr(var w̄t )(M̃t+1
− M̃t+1
) ,
t=1
1
2
where M̃1:T
and M̃1:T
are the solutions of following two
decoupled Lyapunov equations:
1
M̃1:T
= DLET (Ã11:T , Q̃11:T ),

2
M̃1:T
= DLET (Ã21:T , Q̃21:T ).

Proof: When S = ∅, H is 1dx ×dx ; thus, Ãt is block
diagonal. Consequently, the Lyapunov equation (20) decouples
into the two smaller Lyapunov equations given above.
IV. S PECIAL CASES AND GENERALIZATIONS
In this section, we present two special cases and two
generalizations of Problem 1. Due to space limitations, we
only present the results for MFS-IS (i.e., the analogue of
Theorem 1); the results for PMFS (i.e., the analogue of
Theorem 2) may be derived in a similar manner.
A. Special case 1: major and minor agents
Suppose there exist M ⊆ K sub-populations with only 1
agent, i.e., |N k | = 1, k ∈ M. Then, for every k ∈ M,
x̄k1 = xkt . The rest of the dynamics and cost are the same
as in Section II-A. Since the dynamics are coupled through
the mean-field, the states of the agents of sub-populations M
directly influence the dynamics of all other agents and the
per-step cost. For this reason, such agents are called major
agents. A variation of the above model with a single major
agent was first introduced in [32] and other variations have
been investigated in [33]–[35].
For above model, result of Theorem 1 simplifies as follows.
Corollary 2 For any sub-population k ∈ K\M and minor
agent i ∈ N k , uit is given by (12). For any major agent i ∈
N k , k ∈ M, the control law is given by ukt = L̄kt x̄t .
Note that for k ∈ M, L̆kt is not needed to compute ukt ; so
k
we do not need a Riccati equation to compute M̆1:T
.
B. Special case 2: no local controls
Suppose that for all k ∈ K, Btk = 0 and Rtk = 0. Moreover
assume that there exists a vector θ t = rows(θt1 , . . . , θtK ), θtk ∈
|
Rdũ × Rdu , k ∈ K, such that Etk = Ẽtk θ t for all k ∈ K and
| u
u
k+
Pt = θ t P̃t θ t . In addition, let θt denote the right inverse
+
of θtk (i.e., θtk θtk = IRdũ ), which is assumed to exist. This
implies that the dynamics and cost are given as follows. Let
X
|
ũt := θ t ūt =
θtk ūkt .
k∈K
k

Then, for agent i ∈ N of sub-population k ∈ K, we have
xit+1 = Akt xit + Dtk x̄t + Ẽtk ũt + wti .

8

At time t ∈ {1, . . . , T − 1}, the per-step cost is given by,
|

|

F̄t = B̄t M̄t+1 B̄t + R̄t + Ptu

|

ct (xt , ut , x̄t , ũt ) = x̄t Ptx x̄t + ũt P̃tu ũt
X X
+
k∈K i∈N k

|
1
(xi ) Qt xit ,
|N k | t

cT (xT , x̄T ) =

|
x̄T PTx x̄T

+

X X
k∈K i∈N k

|
1
(xi ) QT xiT .
|N k | T

Corollary 3 For the model described above, the optimal
control law is given as follows. For all k ∈ K and i ∈ N k ,
+

uit = θtk L̃kt x̄kt .
where [L̃1t , . . . , L̃K
t ] =: L̄t is given as in Theorem 1 but with
B̄t replaced by B̃t = rows(Ẽt1 , . . . , ẼtK ) and Ptu replaced
by P̃tu .
The proof is presented in Appendix B.
Remark 8 Note that for the model defined above, each agent
only needs to observe the mean-field of its sub-population
(rather than the mean-field of entire population). Thus, this
result is similar in spirit to [36, Theorem 1].
C. Generalization 1: tracking cost function
Consider a tracking problem in which we are given a
k
tracking signal {skt }Tt=1 , skt ∈ Rdx for the mean-field of subk
population k ∈ K and a tracking signal {rti }Tt=1 , rti ∈ Rdx ,
for each agent i ∈ N k .
Define r̄tk := h(rti )i∈N k i, k ∈ K, r̄t := vec(r̄,1 . . . , r̄tK ), and
st = vec(s1t , . . . , sK
t ). The tracking cost is as follows. For
t ∈ {1, . . . , T − 1},
|

|

ct (xt , ut , x̄t , ūt ) = (x̄t − st ) Ptx (x̄t − st ) + ūt Ptu ūt
i
X X 1 h
i
i | k i
i
i | k i
+
(x
−
r
)
Q
(x
−
r
)
+
(u
)
R
u
t
t
t
t
t
t
t t ,
|N k |
k
k∈K i∈N

and for t = T ,
|

cT (xT , x̄T ) = (x̄T − sT ) PTx (x̄T − sT )
X X 1
|
(xiT − rTi ) QkT (xiT − rTi ).
+
k
|N |
k
k∈K i∈N

We assume that, in addition to MFS-IS specified in Section II-A2, agent i also knows signals {rti , r̄t , st }Tt=1 . The rest
of the model is the same as in Section II-A.
Theorem 3 Under (A1), (A2), and (MFS-IS), the optimal
strategy is unique and given by
=

L̆kt (xit

−

x̄kt )

+

L̄kt x̄t

−1
{L̆kt , L̄kt }Tt=1

+

F̆tk vti

+

F̄tk v̄t ,

(21)

where the gains
are obtained by the solution
of K + 1 Riccati equations defined in Theorem 1 and the
−1
and the correction signals {vti , v̄t }Tt=1 are
gains {F̆tk , F̄tk }Tt=1
given as follows. Let {M̆tk }Tt=1 and {M̄t }Tt=1 be the solutions
of K + 1 Riccati equations defined in Theorem 1. For t ∈
{1, . . . , T − 1}, the gains {F̆tk , F̄tk }Tt=1 are given by

−1
|
|
k
F̆tk = (Btk ) M̆t+1
Btk + Rtk
Btk ,

−1

|

B̄t .

The correction signals {vti , v̄t }Tt=1 are given recursively as
follows: for t = T ,
vTi = QkT rTi ,

and t = T ,

uit

and rows(F̄t1 , . . . , F̄tK ) := F̄t , where

v̄T = Q̄T r̄T + PTx sT ,

(22)

and for t ∈ {T − 1, . . . , 1},
|

i
vti = (Akt + Btk L̆kt ) vt+1
+ Qkt rti ,
|

v̄t = (Āt + B̄t L̄t ) v̄t+1 + Q̄t r̄t +

(23)
Ptx st .

(24)

The proof is presented in Appendix C. To implement the
optimal control strategies:
• all agents must compute L̄1:T −1 and F̄1:T −1 by solving
Riccati equation (14) and compute the global correction
signal v̄1:T by solving backward equations (22) and (24),
k
• agents of sub-population k must compute L̆1:T −1 and
k
F̆1:T −1 by solving Riccati equation (13),
• an individual agent i of sub-population k must compute
i
by solving backward equaa local correction signal v1:T
tions (22) and (23).
Then, an individual agent i of sub-population k, upon observing the local state xit and the global mean-field x̄t , chooses
its local control action according to (21).
D. Generalization 2: weighted mean-field
Suppose there are weights (ai , λi , bi ) associated with each
agent i ∈ N such that ai , λi ∈ R and bi ∈ R>0 . For each subpopulation k ∈ K define the weighted mean-field of states and
actions as follows.
1 X i i
1 X i i
k,λ
λ
x
,
ū
=
λ ut ,
x̄k,λ
=
t
t
t
|N k |
|N k |
k
k
i∈N

i∈N

x̄λt = vec(x̄1,λ , . . . , x̄K,λ ),
ūλt = vec(ū1,λ , . . . , ūK,λ ).
P
Also, define āk,λ = |N1k | i∈N k λi ai . For sub-population k ∈
K, the state of agent i ∈ N k evolves as follows.
xit+1 = Akt xit + Btk uit + ai (Dtk x̄λt + Etk ūλt ) + wti .
The per-step cost is given by
|

|

ct (xt , ut , x̄λt , ūλt ) = (x̄λt ) Ptx x̄λt + (ūλt ) Ptu ūλt
i
X X bi h
i | k i
i | k i
(x
)
Q
x
+
(u
)
R
u
+
t
t t
t
t t ,
|N k |
k
k∈K i∈N

and the terminal cost is given by
X X
|
cT (xT , x̄λT ) = (x̄λT ) PTx x̄λT +
k∈K i∈N k

bi h i | k i i
(xT ) QT xT .
|N k |

Such models arise in applications where the interaction between two homogeneous agents is not symmetric but depends
on their weights. For example, in wireless networks, the
interference caused at the base-station depends on the distance
of the agents from the base-station.
In the above model, agents are not partially exchangeable.
Nonetheless, we are able to explicitly identify optimal control
strategies under the following assumptions.

9

Assumption (A4) For each sub-population k ∈ K and each
agent i ∈ N k , ai bi = λi āk,λ .
Given a sub-population k ∈ K, examples of weights that
satisfy (A4) are: for all i ∈ N k , (i) ai =P
0, (ii) ai = 1 and
1
i
i
i
i
i
b = λ , (iii) a = λ , b = 1, and |N k | i∈N k λi = 1. To
i 2
P
simplify the exposition, define µk := 2 − |N1k | i∈N k (λbi) .

A. Step 1: A coordinate transformation
Define x̆it = xit − x̄kt and ŭit = uit − ūkt and consider the following coordinate transformation T of thestate
and action spaces: T vec (xit )i∈N ) = vec (x̆it )i∈N , x̄t and
T vec (uit )i∈N ) = vec (ŭit )i∈N , ūt . Under this transformation, the dynamics (5) may be written as

Assumption (A2a) For every t, Ptx , Ptu , Qkt , and Rtk are
symmetric matrices that satisfy
Qkt ≥ 0, ∀k ∈ K,

x
diag(µ1 Q1t , . . . , µK QK
t ) + Pt ≥ 0,

Rtk > 0, ∀k ∈ K,

diag(µ1 Rt1 , . . . , µK RtK ) + Ptu > 0.

k

Note that if µ = 1, (A2a) reduces to (A2). Each agent has
mean-field sharing information structure, i.e., agent i ∈ N k
of sub-population k ∈ K observes the local state xit and the
weighted mean-field x̄λt .
Theorem 4 Under (A1), (A2a), (A4), and (MFS-IS), the optimal strategy is unique and given by


λi
λi k,λ
i
k
i
+ i L̄kt x̄λt ,
ut = L̆t xt − i x̄t
b
b
−1
are obtained by the solution of
where the gains {L̆kt , L̄kt }Tt=1
K + 1 Riccati equations defined in Theorem 1 when Āt , B̄t ,
Q̄t , and R̄t are replaced by

Āt :=
B̄t :=

1,λ 1
diag(A1t , . . . , AK
Dt , . . . , āK,λ DtK ),
t ) + rows(ā
diag(Bt1 , . . . , BtK ) + rows(ā1,λ Et1 , . . . , āK,λ EtK ),
Q̄t := diag(µ1 Q1t , . . . , µK QK
t ),
1 1
K K
R̄t := diag(µ Rt , . . . , µ Rt ).

The proof is presented in Appendix D.
Remark 9 The optimal strategy depends on the weights and,
even within a sub-population, the gains of the mean-field terms
are different for different agents.
Remark 10 If the dynamics of the agents are decoupled, i.e.,
ai = 0 for all agents, then the results of Theorem 4 are similar
to the model with soft constraints discussed in [13].
Note that if ai = bi = λi = 1 for all agents, then
the weighted mean-field model reduces to the basic model
described in Proposition 1 and the result of Theorem 4 reduces
to that of Theorem 1.

x̆it+1 = Akt x̆it + Btk ŭit + w̆ti ,
where w̆ti := wti − w̄tk and w̄tk := h(wti )i∈N k i and
x̄t+1 = Āt x̄t + B̄t ūt + w̄t ,

(26)

where w̄t := vec(w̄t1 , . . . , w̄tK ) and Āt and B̄t are defined as
in Theorem 1.
The per-step cost ct (xt , ut , x̄t , ūt ) and terminal cost
cT (xT , x̄T ) can also be written in terms of the transformed
variables. For that matter, we need the following result that
is similar to the Parallel-Axis Theorem (or Huygens-Steiner
Theorem) in mechanics [37]:
Lemma 1 For any x = vec(x1 , . . . , xN ) and x̄ = hxi, let
x̆i = xi − x̄, i ∈ {1, . . . , N }. Then, for any matrix Q of
appropriate dimension,
N
N
1 X i | i
1 X i | i
|
(x ) Qx =
(x̆ ) Qx̆ + x̄ Qx̄.
N i=1
N i=1

Proof: The result
PNfollows from elementary algebra and
the observation that i=1 x̆i = 0.
An immediate consequence of Lemma 1 is the following:
Corollary 4 For time t, t ∈ {1, . . . , T }, there exist functions
{c̆kt }k∈K and c̄t such that
ct (xt , ut , x̄t , ūt ) = c̄t (x̄t , ūt ) +

X X

c̆kt (x̆it , ŭit ),

(27)

k∈K i∈N k

where
|

|

c̄t (x̄t , ūt ) = x̄t (Q̄t + Ptx )x̄t + ūt (R̄t + Ptu )ūt ,
i
|
1 h i | k i
(x̆t ) Qt x̆t + (ŭit ) Rtk ŭit ,
c̆kt (x̆it , ŭit ) =
k
|N |
and for t = T,

V. P ROOF OF T HEOREM 1
We start with the model presented in Proposition 1. The
proof proceeds in three steps.
• Step 1: We use a coordinate transformation to construct
a system that is isomorphic to the original system.
• Step 2: We construct an auxiliary system which is system
of Step 1 with classical information structure (i.e., all
decisions are made a single agent).
• Step 3: We show that the optimal control laws of the
auxiliary system can be implemented using MFS-IS. A
fortiori, they are also optimal for MFS-IS.

(25)

cT (xT , x̄T ) = c̄T (x̄T ) +

X

c̆kT (x̆iT ),

(28)

i∈N k ,k∈K

where
|

c̄T (x̄T ) = x̄T (Q̄T + PTx )x̄T ,

c̆kT (x̆iT ) =

|
1
(x̆i ) QkT x̆iT .
|N k | T

Since the transformation T is an isomorphism, the transformed model with dynamics (25) and (26) and the per-step
cost (27) and (28) is equivalent to the original model in
Proposition 1, irrespective of the information structure.

10

B. Step 2: An auxiliary system
Consider an auxiliary system with state x̊t
=
vec((x̆it )i∈N , x̄t ) and action ůt = vec((ŭit )i∈N , ūt ) (which is
same as the transformed model of Step 1). There is a single
centralized agent that chooses ůt based on the observations.
In particular, the centralized agent observes x̊t and chooses
ůt according to
ůt = g̊t (x̊1:t , ů1:t−1 ).

(29)

The performance of strategy g̊ := (g̊1 , . . . ,g̊T ) is given by
 TX

−1
˚ = Eg̊
J(g̊)
ct (xt , ut , x̄t , ūt ) + cT (xT , x̄T ) , (30)
t=1

where the expectation is with respect to the measure induced
on all system variables by the choice of strategy g̊. We are
interested in the following optimization problem.
Problem 2 In the auxiliary system, find strategy g̊∗ that
minimizes (30), i.e.,
˚ ∗ ) = inf J(g̊),
˚
J˚∗ := J(g̊
g̊

where the infimum is taken over all strategies of the form (29).
Let J ∗ and J˚∗ denote the optimal cost for Problem 1 and
Problem 2, respectively. Since the per-step cost is the same in
both cases, but Problem 2 is centralized, we have that
J ∗ ≥ J˚∗ .
We identify the optimal control laws for the auxiliary system
and show that these laws can be implemented in, and therefore
are optimal for, the original decentralized system.
C. Step 3: The Optimal Solution of the Auxiliary System
The auxiliary system is a stochastic linear quadratic system.
So, the optimal control laws are linear and the optimal gains
are given by the solution of an appropriate Riccati equation.
However, the dimension of the state x̊t , and therefore the dimension of the Riccati equation, increases with the number of
agents. To overcome this challenge, we present an alternative
approach that involves solving K + 1 Riccati equations that
do not depend on the number of agents.
Since the auxiliary system is a stochastic linear quadratic
system, the certainty equivalence principle [38, Theorem 6.1]
holds. Therefore, the optimal control law is identical to the
control law of the corresponding deterministic system, whose
dynamics are given as follows: for k ∈ K and i ∈ N k
x̆it+1 = Akt x̆it + Btk ŭit ,

x̄t+1 = Āt x̄t + B̄t ūt ,

and whose per-step cost is c̊t (x̊t , ůt ) given by Corollary 4.
Under (A2), the deterministic centralized linear quadratic
system is strictly convex; hence, the solution is unique [38,
Theorem 4.1].
Note that this system consists of (N + 1) components:
N components with state x̆it and action ŭit , i ∈ N , and
one component with state x̄t and action ūt . The first N
components are split into K classes of identical components—
one for each sub-population. The components have decoupled

dynamics and decoupled cost. Thus, the optimal control law
of each class may be identified separately. In particular, from
[38, Theorem 4.1], we have that
Theorem 5 The optimal control strategy of the auxiliary
system (i.e., Problem 2) is unique and given by
ūt = L̄t x̄t

and for k ∈ K, i ∈ N k ,

ŭit = L̆kt x̆it ,

−1
where the gains {L̆kt , L̄t }Tt=1
are given as in Theorem 1.

Now, we transform the optimal centralized solution, given
by Theorem 5, back to the original model (by taking the
inverse of coordinate transformation used in Step 1), to get
uit = ŭit + ūkt = L̆kt (xit − x̄kt ) + L̄kt x̄t .
Note that the above control laws are implementable under
MFS-IS. Therefore, the solution of Problem 2 coincides with
the solution of Problem 1 with MFS-IS.
VI. P ROOF OF T HEOREM 2
A. Preliminary results
We use the same transformation as Step 1 in Section V-A.
In particular, for any k ∈ K and i ∈ N k , define x̆it := xit − x̄kt ,
ŭit := uit − ūkt , s̆it := sit − s̄kt and v̆ti := vti − v̄tk . Then, we have
Lemma 2 For all t, s̆it = x̆it and ŭi = v̆ti . Consequently,
Jˆ − J ∗ =

T
X

[c̄t (s̄t , v̄t ) − c̄t (x̄t , ūt )] .

(31)

t=1

Proof: We prove the first part by induction. Note that
x̆i1 = s̆i1 and v̆1i = L̆k1 s̆i1 = L̆k1 x̆i1 = ŭi1 . This forms the basis
of induction. Now assume that s̆it = x̆it and v̆ti = ŭit and
consider time t + 1. Then,
s̆it+1 = Akt s̆it + Btk v̆ti + w̆ti = Akt x̆it + Btk ŭit + w̆ti = x̆it+1 .
i
Moreover, v̆t+1
= L̆kt+1 s̆it+1 = L̆kt+1 x̆it+1 = ŭit+1 . Thus, the
result is true by induction. Equation (31) immediately follows
from the first part and Corollary 4.
Next we simplify (31) in terms of the following relative
errors: For any k ∈ K, define

ζtk = x̄kt − ztk

and ξtk = s̄kt − ztk .

Let ζ t = vec(ζt1 , . . . , ζtK ) and ξ t = vec(ξt1 , . . . , ξtK ). For ease
of exposition, let vector h = vec(h1 , . . . , hK ) be binary such
that hk = 0dkx ×1 if k ∈ S and hk = 1dkx ×1 if k ∈ S c .
Lemma 3 Let Ãt be defined as in Theorem 2. Then, ζ 1 =
h ◦ x̄1 and ξ 1 = h ◦ x̄1 and



 

ζ t+1
ζt
h ◦ w̄t
= Ãt
+
.
ξ t+1
ξt
h ◦ w̄t
Proof: From (16) and (18), we get
s̄kt+1 = Akt s̄kt + Btk v̄tk + Dtk s̄t + Etk v̄t + w̄tk ,
v̄tk = L̆kt (s̄kt − ztk ) + L̄kt zt ,

(32)

where w̄tk := h(wti )i∈N k i. Write (32) in a vectorized form,
s̄t+1 = Āt s̄t + B̄t v̄t + w̄t ,

v̄t = L̆t ξ t + L̄t zt ,

11

where w̄t = vec(w̄k1 , . . . , w̄tK ). From Theorem 1, we can write
the dynamics under the optimal strategy as follows
x̄kt+1 = Akt x̄kt + (Btk L̄kt + Dtk + Etk L̄t )x̄t + w̄tk ,
ūkt = L̄kt x̄t ,

|

|

|

|

|

|

|

+ 2E[ξ t L̆t R̂t L̄t zt |Ft ] − 2E[ζ t L̄t R̂t L̄t zt |Ft ]
ūt = L̄t x̄t .

Thus, the dynamics of the relative errors can be written as
follows. If k ∈ S,
k
ζt+1
= Akt ζtk + (Btk L̄kt + Dtk + Etk L̄t )ζ t

− (Akt + Btk L̆kt )ξtk − (Dtk + Etk L̆t )ξ t ,
k
ξt+1
= 0,

and if k ∈ S c ,
k
ζt+1
= Akt ζtk + (Btk L̄kt + Dtk + Etk L̄t )ζ t + w̄tk ,
k
ξt+1
= (Akt + Btk L̆kt )ξtk + (Dtk + Etk L̆t )ξ t + w̄tk .

Combining these, gives the result of the Lemma.
Let Ft = {s̄k1:t }k∈S be the history of the mean-fields of
sub-populations S that are observed.
Lemma 4 For all t, E[ζ t |Ft ] = E[ξ t |Ft ] = 0.
Proof: If k ∈ S, ζ1k = ξ1k = 0 and if k ∈ S c ,
ζ1k = ξ1k = x̄k1 , and from (A1a), E[x̄k1 |F1 ] = E[x̄k1 ] = 0.
Therefore, E[ζ 1 |F1 ] = E[ξ 1 |F1 ] = 0. Thus, from Lemma 3
and E[w̄t |Ft ] = 0, we get that E[ζ t |Ft ] = E[ξ t |Ft ] = 0.
Lemma 5 zt is measurable with respect to Ft , therefore,
E[zt |Ft ] = zt .
Proposition 2 The relative loss is given
" T
X
|
∗
Jˆ − J = E
[ζ t ξ t ] Q̃t [ζ t

#
ξt ] .

Proof: Recall that c̄t (x̄t , ūt ) = x̄|t (Q̄t +Ptx )x̄t + ū|t (R̄t +
The proof follows immediately from (31) and the
following observation:
Ptu )ūt .

Lemma 6 Let Q̂t := Q̄t + Ptx and R̂t := R̄t + Ptu . Then,
|

|

|

E[s̄t Q̂t s̄t − x̄t Q̂t x̄t |Ft ] = E[ξ t Q̂t ξ t − ζ t Q̂t ζ t |Ft ],
and
|

|

|

E[v̄t R̂t v̄t − ūt R̂t ūt |Ft ] = E[ξ t L̆t R̂t L̆t ξ t |Ft ]
−

| |
E[ζ t L̄t R̂t L̄t ζ t |Ft ].

Therefore, the proof of Proposition 2 is complete.
Proof of Lemma 6:
1) Substituting s̄t = ξ t + zt and x̄t = ζ t + zt , we get
|

E[s̄t Q̂t s̄t − x̄t Q̂t x̄t |Ft ]
(a)E[ξ | Q̂ ξ − ζ | Q̂ ζ |F ] +
t t t
t t t t
=
|
− 2E[ζ t Q̂t zt |Ft ]
|
|
= E[ξ t Q̂t ξ t − ζ t Q̂t ζ t |Ft ],

|

|

2E[ξ t Q̂t zt |Ft ]

where the last two terms in (a) are zero by Lemmas 4
and 5.

|

|

|

= E[ξ t L̆t R̂t L̆t ξ t − ζ t L̄t R̂t L̄t ζ t |Ft ],
where the last two terms in (b) are zero by Lemmas 4
and 5.
B. Proof of Theorem 2
To prove part 1, note that Jˆ − J ∗ is the expected total
quadratic cost (given by Proposition 2) of a linear (uncontrolled) system (given by Lemma 3). Thus, Jˆ− J ∗ is given by
(19) where M̃1:T is the solution of the Lyapunov equation (20).
Note that the variance of the initial state and noises in
Lemma 3 are given as follows:
var(h ◦ x̄1 , h ◦ x̄1 ) = 12dx ×2dx ⊗ [H ◦ var(x̄1 )] =: X̃1 ,
var(h ◦ w̄t , h ◦ w̄t ) = 12dx ×2dx ⊗ [H ◦ var(w̄t )] =: W̃t .
To prove part 2 of Theorem 2, first observe that due to
(A3), matrices Ãt and Q̃t do not depend on (|N 1 |, . . . , |N K |);
therefore, neither does M̃1:T . Thus the only dependence on the
size of the sub-population is due to X̃1 and W̃t . Under (A1b)
and (A3), for any sub-population k ∈ K,
var(x̄k1 ) =

X
ck
1
var(xi1 ) ≤ x ,
k
2
|N |
n
k
i∈N

var(w̄tk )

t=1

|

|

= E[ξ t L̆t R̂t L̆t ξ t − ζ t L̄t R̂t L̄t ζ t |Ft ]

x̄t+1 = (Āt + B̄t L̄t )x̄t + w̄t ,

|

|

E[v̄t R̂t v̄t − ūt R̂t ūt |Ft ]
(b)

and in a vectorized form,

|

2) Substituting v̄t = L̆t ξ t +L̄t zt and ūt = L̄t x̄t = L̄t (ζ t +
zt ), we get

X
1
ck
=
var(wti ) ≤ w .
k
2
|N |
n
k
i∈N

From (A1b), var(x̄1 ) = diag(var(x̄11 ), . . . , var(x̄K
1 )) and
var(w̄t ) = diag(var(w̄t1 ), . . . , var(w̄tK )). Thus,


1
X̃1 ≤ 12dx ×2dx ⊗ H ◦ diag(c1x , . . . , cK
x ) ,
n


1
W̃t ≤ 12dx ×2dx ⊗ H ◦ diag(c1w , . . . , cK
w) .
n
Thus, X̃1 and W̃t are O( n1 ). From (19), we have
T
−1




X
|Jˆ − J ∗ | ≤ Tr X̃1 M̃1 +
Tr W̃t M̃t+1 ,
t=1

where each of above absolute values is O( n1 ). In particular,
since X̃1 and W̃t are O( n1 ) and M̃1:T do not depend on n,
| Tr(X̃1 M̃1 |) and | Tr(W̃t M̃t+1 )| are O( n1 ).
VII. I NFINITE H ORIZON
The results presented in Sections III and IV generalize to infinite horizon setup in a natural manner. Assume that the model is time-invariant, i.e., the matrices {Akt , Btk , Dtk , Etk , Qkt , Rtk , Ptx , Ptu } and covariances
{Σ̆kt , Σ̄t , Ξ̆kt , Ξ̄t } (defined in Theorem 1) do not depend on
time; hence, we remove the subscript t. The rest of the model
is as same as that in Section II-A.

12

Consider the infinite horizon discounted cost and the infinite
horizon long-term average setups as follows:
Problem 3 Given discount factor β ∈ (0, 1), find a strategy g
that minimizes the following cost:
X

∞
Jβ (g) = (1 − β)Eg
β t−1 c(xt , ut , x̄t , ūt ) ,
t=1

in Section V, which consists of |N | + 1 components with
decoupled cost and dynamics coupled only through the noise.
Since the costs are infinite-horizon discounted and infinitehorizon long run average, the optimal solution is given by
appropriate algebraic Riccati equations.9 Under (A2) and (A5),
these Riccati equations have a unique solution [38, Theorem
9.2].

where the expectation is with respect to the measure induced
on all the system variables by the choice of strategy g.

B. Approximate solution for PMFS-IS

Problem 4 Find a strategy g that minimizes the following
cost:

 X
T
g 1
c(xt , ut , x̄t , ūt ) ,
J1 (g) = lim E
T →∞
T t=1

In this section, we propose an approximately optimal
strategy for Problems 3 and 4 under PMFS-IS. Let L̆ =
diag(L̆1 , . . . , L̆K ) denote a diagonal matrix with diagonal
terms of L̆k defined as in Theorem 6. We impose the following
assumption.
√
Assumption (A6) β(Ā + B̄ L̆) is Hurwitz matrix.

where the expectation is with respect to the measure induced
on all the system variables by the choice of strategy g.
Assumption
pk ∈ K,
√
√ (A5) For each sub-population
√
( βAk , βB k ) are stabilizable and ( βAk , Qk ) are detectable.
pin Theorem 1,
√
√In addition, for Āt and B̄t defined
√
( β Ā, β B̄) are stabilizable and ( β Ā, Q̄ + P x ) are
detectable.
A. Exact solution for MFS-IS
The optimal strategy under MFS-IS is as follows.
Theorem 6 Under (A1), (A2), (A5), and (MFS-IS), the optimal strategy for Problems 3 and 4 are linear and time
homogeneous and are given by
uit = L̆k (xit − x̄kt ) + L̄k x̄t ,

(33)

where the gains {L̆k , L̄k } are obtained by the solution of K+1
algebraic Riccati equations given below: one for computing
each L̆k , k ∈ K, and one for L̄ := rows(L̄1 , . . . , L̄K ). Let
matrices Ā, B̄, Q̄, and R̄ be defined as in Theorem 1; then,
given β ∈ (0, 1],
 |
−1
|
L̆k = − B k M̆ k B k + β −1 Rk
B k M̆ k Ak ,
−1 |
|
L̄ = − B̄ M̄ B̄ + β −1 (R̄ + P u )
B̄ M̄ Ā,
where M̆ k and M̄ are the solutions of the following algebraic
Riccati equations:
M̆ k = DAREβ (Ak , B k , Qk , Rk ),
M̄ = DAREβ (Ā, B̄, Q̄ + P x , R̄ + P u ).
In addition, the optimal performance is given by
"
#

X 
Jβ∗ = (1 − β)
Tr Ξ̆k M̆ k + Tr(Ξ̄M̄ )
k∈K

"
+

X



k

Tr Σ̆ M̆

k



#

Let Jˆβ denote the performance of strategy (33) where x̄t is
replaced by zt in (17) and Jβ∗ denote the optimal performance
under MFS-IS. Then, the difference in performance Jˆβ − Jβ∗
is bounded. In particular, we have the following
Theorem 7 Assume (A1a), (A2), (A5), (A6) and (PMFS-IS).
Then, for β ∈ (0, 1], we have
1) The performance loss is given by




Jˆβ − Jβ∗ = (1 − β) Tr X̃1 M̃ + Tr W̃ M̃ , (34)
where X̃1 and W̃ are time-homogeneous and defined
as in Theorem 2 and M̃ is the solution of following
algebraic Lyapunov equation:
M̃ = DALEβ (Ã, Q̃),

(35)

where Ã and Q̃ are defined as in Theorem 2 and L̆ =
diag(L̆1 , . . . , L̆K ) and L̄ are computed as in Theorem 6.
2) Let n = mink∈S c (|N k |). Under (A1b) and (A3),
 
1
Jˆβ − Jβ∗ ∈ O
.
n
Proof: The proof follows along the same lines of the
√ proof
of Theorem 2. In particular, under (A5) and (A6), β Ã of
Proposition 2 is Hurwtiz; hence, the performance loss may be
computed by the associated algebraic Lyapunov equation given
by (35). Note that even though Q̃ is not positive semi-definite,
the algebraic Lyapunov equation has a solution [39]. The proof
of part 2 of Theorem 7 follows from (34) and observation
that (i) M̃ given by (35) does not depend on n due to (A3);
(ii) (X̃1 , W̃ ) are O(1/n) due to (A1b).
Remark 11 Assumption (A6) is always√satisfied if Dtk = 0
and Etk = 0 for all k ∈ K. In this case, β(Ā + B̄ L̆) is
p
p
diag( β(A1 + B 1 L̆1 ), . . . , β(AK + B K L̆K )),

+ Tr(Σ̄M̄ ) ,

k∈K

where Σ̆k , Σ̄, Ξ̆k , and Ξ̄ are defined as in Theorem 1.
Proof: The proof follows along the same lines of the
proof of Theorem 1. We construct an auxiliary system as

where each of the diagonal terms are Hurwitz by definition
of L̆k given in Theorem 6.
9 Note that an infinite-horizon discounted problem with 4-tuple
(A, B, Q, R) and discount
factor β is equivalent to an undiscounted
√
√
problem with 4-tuple ( βA, βB, Q, R).

13

xit+1 − xknom = ak (xit − xknom ) + bk uit + wti ,
where uit is the control input in addition to uknom and wti is
a random disturbance. We assume uknom is large enough such
that (uit + uknom ) is positive.
Let xides denote the desired temperature of user i.
It is assumed that the mean desired temperature
x̄des = vec(x̄1des , . . . , x̄K
des ) is known to everyone (e.g.,
independent system operator (ISO) could compute it and
broadcast the mean value to everyone or it could be computed
in a distributed manner using a consensus algorithm). For the
purpose of demand response, time is divided into epochs of
length T . At the beginning of each epoch, a central authority
such as an ISO generates a reference mean temperature mref
and broadcasts it to all users.
During an epoch,
PT all users collectively minimize the total
expected cost E[ t=1 ct ], where the per-step cost ct is given
by
i
t
1 Xh i
2
q(xt − xides )2 + ruit + p(mt − mref )2 ,
|N |
T
i∈N

P
i
where mt =
i∈N xt /|N |. The rationale for the perstep cost is that we penalize deviations from the desired
temperature (which corresponds to the user’s comfort level),
the control effort, and deviation of the mean temperature from
the reference prescribed by the ISO. The weight Tt is so that
we linearly add more weight to meeting global preference.
The above problem is an optimal tracking problem and the
optimal strategy is given by Theorem 3. As an example, we
consider the following values of the parameters: K = 2,
p = 30, q = 2, r = 50, xides = xi1 ∼ Normal(20, 3),
wti ∼ Normal(0, 0.01), and
|N 1 | = 40,

a1 = 0.5,

b1 = 1.5,

x1nom = 20,

|N 2 | = 100,

a2 = 0.8,

b2 = 1.0,

x2nom = 20.

and consider three epochs. In the first epoch, 1 ≤ t ≤ 50,
there is no reference signal and the space heaters are operating
around their local set temperatures; in the second epoch, 50 <
t ≤ 150, mref = 21; in the third epoch, 150 < t ≤ 250,
mref = 19. The resultant trajectories of a subset of the users
are shown in Fig. 1.

24

23

22

Temperature

VIII. N UMERICAL E XAMPLE
To illustrate our results, we consider an example that is
motivated by demand response in power systems. In demand
response, the volatility in renewable generation is compensated
by making small changes in the demand of a large number
of loads. We model the load dynamics according to a model
proposed in [40], but consider a different per-step cost.
Consider a population N of space heaters that can be
partitioned into K disjoint sub-populations N k , k ∈ K :=
{1, . . . , K}. Each sub-population corresponds to a particular
type of space heater that have similar physical characteristics
such time response and nominal temperature. For space heater
i, i ∈ N , the state xit denotes the room temperature at time t.
Consider a nominal temperature xknom for sub-population k,
k ∈ K, and let uknom be the control input needed to maintain
the room temperature at xknom . Following [40], we linearize
the dynamics of sub-population k around xknom , i.e.,

21

20

19

18

17
0

50

100

150

200

250

Time

Fig. 1. Demand response with a population of 140 space heaters consisting
of two sub-populations of size 40 and 100. In the initial phase, 1 ≤ t ≤ 50,
the system is uncontrolled. In the first epoch 50 < t ≤ 150, the system tracks
a mean reference temperature of mref = 21; in the second epoch 150 < t ≤
250, the system tracks a mean reference temperature of mref = 19. The thin
lines show the local temperature of 20 out of the 140 space heaters, where
blue lines corresponds to the first sub-population and red lines correspond to
the second sub-population. The thick black line shows the mean-temperature
achieved by the optimal strategy.

IX. C ONCLUSION
We presented team optimal control of a decentralized system
with partially exchangeable agents. Partial exchangeability
implies that such a system is equivalent to one where the
dynamics and the cost are coupled only through the meanfield. Our two main results are as follows. First, when the mean
field is observed by all agents (the MFS information structure),
the linear control laws are optimal and the corresponding
gains are computed by solving K + 1 Riccati equations,
where K is the number of sub-populations. The dimensions
of these Riccati equations are independent of the size of subpopulations; consequently, the solution complexity depends
only on the number K of sub-populations (rather than the
size of the entire population). Second, when the mean-field of
a (possibly empty) subset of sub-populations is observed by
all agents (the PMFS information structure), a linear control
law based on certainty equivalence is approximately optimal.
An important practical implication of these results is that
they do not suffer from the curse of dimensionality. In fact,
under assumption (A3), the solution does not even depend on
the number of agents and the optimal gains can be computed
without being aware of the size of each sub-population.
Consequently, the solution methodology generalizes to the
setup where the agents in a sub-population arrive and depart
according to an exogenous process (e.g. number of electric
vehicles plugged in for charging in smart grids).
The raison d’etre for investigating decentralized systems is
that it is not possible—either physically or economically—to
send all the state observation to a centralized controller. We
show that when agents are partially exchangeable, we may
circumvent the conceptual difficulties of decentralized control
and achieve the centralized performance by sharing only the
mean-field. Moreover, in view of the results of PMFS-IS, one
may even decide not to share the mean-field of large subpopulations because there is only a small loss in performance
in using the approximate value of the mean-field instead.
Throughout this paper, we assumed that when the mean-

14

field is observed, it is observed without noise. In practice
(especially if the mean-field is computed using a consensus
algorithm), the mean-field will be observed with noise (and
the noise will be different across agents). Our results show
that if all sub-populations are large, such an observation noise
will not matter. (In fact, the agents may completely ignore
the mean-field observations and use the approximate values
instead). However, if some of the sub-populations are small,
the solution approach is not obvious. In particular, in the
special case when all sub-populations have one agent, the
problem reduces to the general decentralized control problem
with non-classical information structure. Identifying a solution
methodology for this general case remains a challenging
research direction.
R EFERENCES
[1] J. Arabneydi and A. Mahajan, “Team-optimal solution of finite number
of mean-field coupled LQG subsystems,” IEEE Conference on Decision
and Control, pp. 5308 – 5313, Dec. 2015.
[2] H. Witsenhausen, “A counterexample in stochastic optimum control,”
SIAM Journal Of Cont. And Opt., vol. 6, pp. 131–147, Dec. 1968.
[3] P. Whittle and J. Rudge, “The optimal linear solution of a symmetric
team control problem,” J. of Applied Probability, pp. 377–381, 1974.
[4] A. Mahajan, N. C. Martins, M. C. Rotkowitz, and S. Yuksel, “Information structures in optimal decentralized control,” Proc. of Conf. on
Decision and Control (CDC), pp. 1291–1306, Dec. 2012.
[5] Y. Ouyang and D. Teneketzis, “Signaling for decentralized routing in a
queueing network,” Annals of Operations Research, pp. 1–39, 2015.
[6] G. M. Lipsa and N. C. Martins, “Remote state estimation with communication costs for first-order LTI systems,” IEEE Trans. Autom. Control,
vol. 56, no. 9, pp. 2013–2025, Sept 2011.
[7] L. Lessard and S. Lall, “Optimal control of two-player systems with
output feedback,” IEEE Trans. Autom. Control, vol. 60, no. 8, pp. 2129–
2144, 2015.
[8] H. Witsenhausen, “Separation of estimation and control for discrete time
systems,” Proc. of IEEE, vol. 59, no. 11, pp. 1557–1566, Nov. 1971.
[9] Y. C. Ho and K. H. Chu, “Team decision theory and information
structures in optimal control problems–part I,” IEEE Trans. Autom.
Control, vol. 17, no. 1, pp. 15–22, 1972.
[10] B. Bamieh and P. G. Voulgaris, “A convex characterization of distributed
control problems in spatially invariant systems with communication
constraints,” Sys. & Control Letters, vol. 54, no. 6, pp. 575–583, 2005.
[11] M. Rotkowitz and S. Lall, “A characterization of convex problems in
decentralized control,” IEEE Trans. Autom. Control, vol. 51, no. 2, pp.
274–286, 2006.
[12] D. S. Bernstein, S. Zilberstein, and N. Immerman, “The complexity of
decentralized control of markov decision processes,” in Conf. Uncert. in
Artificial Intelligence (UAI), Stanford, CA, Jun. 2000, pp. 32–27.
[13] D. Madjidian and L. Mirkin, “Distributed control with low-rank coordination,” IEEE Transactions on Control of Network Systems, vol. 1,
no. 1, pp. 53––63, 2014.
[14] J. Yong, “Linear-quadratic optimal control problems for mean-field
stochastic differential equations,” SIAM on Control and Optimization,
vol. 51, no. 4, pp. 2809–2838, 2013.
[15] R. Elliott, X. Li, and Y.-H. Ni, “Discrete time mean-field stochastic
linear-quadratic optimal control problems,” Automatica, vol. 49, no. 11,
pp. 3222–3233, 2013.
[16] J. Ma and J. Yong, “Forward-backward stochastic differential equations
and their applications,” Springer Science & Business Media, no. 1702,
1999.
[17] R. Singh, P. R. Kumar, and L. Xie, “The ISO problem: Decentralized
stochastic control via bidding schemes,” CoRR, vol. arXiv:1510.00983,
2015.
[18] Y. Takahara, “Multi-level approach to dynamic optimization,” Technical
report, DTIC Document, 1964.
[19] G. Cohen, “On an algorithm of decentralized optimal control,” Journal
Math. Anal. and Appl., vol. 59, no. 2, pp. 242–259, 1977.
[20] M. Huang, P. E. Caines, and R. P. Malhamé, “Individual and mass behaviour in large population stochastic wireless power control problems:
centralized and Nash equilibrium solutions,” in IEEE Conference on
Decision and Control, 2003, pp. 98–103.

[21] J.-M. Lasry and P.-L. Lions, “Jeux á champ moyen. I – le cas stationnaire,” C. R. Acad. Sci. Paris, Ser. I, vol. 343, pp. 619–625, 2006.
[22] ——, “Jeux á champ moyen. II – horizon fini et contrôle optimal,” C.
R. Acad. Sci. Paris, Ser. I, vol. 343, pp. 679–684, 2006.
[23] M. Huang, P. E. Caines, and R. P. Malhamé, “Large-population costcoupled LQG problems with nonuniform agents: Individual-mass behavior and decentralized ε-Nash equilibria,” IEEE Trans. Autom. Control,
vol. 52, no. 9, pp. 1560–1571, 2007.
[24] T. Li and J.-F. Zhang, “Asymptotically optimal decentralized control for
large population stochastic multiagent systems,” IEEE Trans. Autom.
Control, vol. 53, no. 7, pp. 1643–1660, 2008.
[25] P. Caines, “Mean-field games,” in Encyclopedia of Systems and Control,
T. Samad and J. Baillieul, Eds. Springer-Verlag, Oct. 2013.
[26] D. A. Gomes and J. Saude, “Mean field games models: A brief survey,”
Springer, Dynamic Games and Appl., vol. 4, pp. 1–45, Jun. 2014.
[27] J. Moon and T. Basar, “Linear quadratic risk-sensitive and robust mean
field games,” IEEE Trans. Autom. Control, vol. 62, no. 6, 2017.
[28] A. Bensoussan, K. C. J. Sung, S. C. P. Yam, and S. P. Yung, “Linearquadratic mean field games,” Journal of Optimization Theory and
Applications, vol. 169, no. 2, pp. 496–529, 2016.
[29] M. Huang, P. E. Caines, and R. P. Malhamé, “Social optima in mean
field LQG control: centralized and decentralized strategies,” IEEE Trans.
Autom. Control, vol. 57, no. 7, pp. 1736–1751, 2012.
[30] R. Radner, “Team decision problems,” The Annals of Mathematical
Statistics, pp. 857–881, Sept. 1962.
[31] J. Arabneydi and A. Mahajan, “Team optimal control of coupled
subsystems with mean-field sharing,” IEEE Conference on Decision and
Control, pp. 1669–1674, 2014.
[32] M. Huang, “Large-population LQG games involving a major player: the
Nash certainty equivalence principle,” SIAM Journal on Control and
Optimization, vol. 48, no. 5, pp. 3318–3353, 2010.
[33] P. E. Caines and A. C. Kizilkale, “Mean field estimation for partially
observed LQG systems with major and minor agents,” in IFAC World
Congress, 2014.
[34] J. Huang, S. Wang, and Z. Wu, “Mean field linear-quadraticGaussian LQG Games: Major and minor players,” arXiv preprint
arXiv:1403.3999, 2014.
[35] J. Arabneydi and A. Mahajan, “Team optimal control of coupled
major-minor subsystems with mean-field sharing,” in Indian Control
Conference (ICC), Jan. 2015.
[36] S. M. Asghari and A. Nayyar, “Decentralized control problems with
substitutable actions,” arXiv preprint arXiv:1601.02250, 2016.
[37] T. R. Kane and D. A. Levinson, “Dynamics, theory and applications,”
McGraw Hill, 1985.
[38] P. E. Caines, “Linear stochastic systems,” John Wiley & Sons, Inc., 1987.
[39] B. Hassibi, A. H. Sayed, and T. Kailath, “Indefinite-quadratic estimation
and control: A unified approach to H2 and H∞ theories,” SIAM, 1999.
[40] A. C. Kizilkale and R. P. Malhame, “Collective target tracking mean
field control for Markovian jump-driven models of electric water heating
loads,” in IFAC World Congress, 2014.

A PPENDIX
A. Proof of Proposition 1
Let Ai,j
denote the (i, j)-th block of matrix At . We use
t
a similar notation for other matrices as well. Fix a subpopulation k, k ∈ K. If we exchange agents i, j ∈ N k , then
j,j
property 2 of exchangeability implies that Ai,i
and
t = At
i,n
j,n
n,i
for any other agent n ∈ N , At = At and At = An,j
t .
(Similar relationships hold for Bt as well). Property 3 implies
j,j
i,n
n,i
that Qi,i
= Qj,n
= Qn,j
t = Qt , Qt
t , and Qt
t . (Similar
relationships hold for Rt as well). Define the following:
i,i
j,j
i,i
j,j
k
• For i, j ∈ N , At = At and Bt = Bt . Denote these
k
k
by at and bt , respectively.
i,n
k
l
• For i, j ∈ N and n, m ∈ N , l 6= k, At
= Aj,m
and
t
i,n
j,m
k,l
k,l
Bt = Bt . Denote these by dt and et , respectively.
i,i
j,j
i,i
j,j
k
• For i, j ∈ N , Qt = Qt and Rt = Rt . Denote these
k
k
by qt and rt , respectively.
k
• For i, j ∈ N
and n, m ∈ N l , l 6= k, Qi,n
= Qj,m
t
t
i,n
j,m
x,k,l
and Rt = Rt . Denote these by pt
and pu,k,l
,
t
respectively.

15

Now, consider the dynamics according to (2), the dynamics of
agent i of sub-population k can be written as
xit+1 = Ai· xt + B i· ut + wti ,

(36)

where Ai· and B i· denote the rows corresponding to the ith
block of At and Bt . Note that
X
X X
j
i
Ai· xt = Ai,i
Ai,j
Ai,n xnt
t xt +
t xt +
j∈N k ,j6=i

l∈K,l6=k n∈N l

X

= akt xit + dk,k
t

j∈N k ,j6=i

=

akt xit

+

X

xjt +

k k
dk,k
t (|N |x̄t

l∈K,l6=k

−

xit )

+

X

dk,l
t

X

xnt

n∈N l
l l
dk,l
t |N |x̄t

l∈K,l6=k

=:

Akt xit

+

X

Dtk,l x̄lt ,

akt

dk,k
t

where
=
−
algebra, we can define

and Dtk,l = |N l |dk,l
t .
k
Bt and Etk,l such that

Bti· ut = Btk uit +

X

By a similar

Etk,l ūlt ,

k∈K l∈K i∈N k j∈N l

X X

|
xjt
(xit ) px,k,l
t

k∈K l∈K,l6=k i∈N k j∈N l

+
+
=

X X

k

|N ||N

and c̄t (x̄t , ūt ) of Corollary 4 simplifies to
|

Thus, the N subsystems corresponding to
are uncontrolled
and we need to identify ũt to optimally control the dynamics
of mean-field x̄t with per-step cost given by (41). Hence, the
optimal solution is given by
X
ũt = L̄t x̄t =
L̃kt x̄kt ,
k∈K

where L̄t is computed as explained in Corollary 3. To complete
the proof, note that if agent i ∈ N k of sub-population k ∈ K
k+ k k
chooses action uit =
θtk ūkt = L̃kt x̄kt ;
P we get
Pθt L̃tkx̄tk, then
k k
consequently, ũt = k∈K θt ūt = k∈K L̃t x̄t .

As in the proof of Theorem 1 described in Section V, define
x̆it = xit − x̄kt , ŭit = uit − ūkt , x̊t = vec((x̆it )i∈N , x̄t ), and
ůt = vec((ŭit )i∈N , ūt ). We identify a cost function {c̆kt }k∈K
and c̄t as in Corollary 4.
Corollary 5 For time t, t ∈ {1, . . . , T }, there exist functions
{c̆kt }k∈K and c̄t such that
X
ct (xt , ut , x̄t , ūt ) = c̄t (x̄t , ūt ) +
c̆kt (x̆it , ŭit )

(xit ) px,k,k
xjt
t

l

−

X

i∈N k ,k∈K
|
(r̄tk ) Qkt r̄tk ,

k∈K

and for t = T ,

|
|(x̄kt ) px,k,l
x̄lt
t

cT (xt , x̄t ) = c̄T (x̄T ) +

X
i∈N k ,k∈K

X X X

k 2

|N |

(41)

x̆it

k∈K l∈K,l6=k

+

|

c̄t (x̄t , ūt ) = x̄t (Q̄t + Ptx )x̄t + ũt (P̃tu )ũt .

|

X

k∈K i∈N k j∈N k ,j6=i
X X
|
(xit ) qtk xit
k∈K i∈N k

X X

x̄t+1 = Āt x̄t + B̃t ũt + w̄t ,

C. Proof of Theorem 3

and Etk,l = |N l |ek,l
where Btk = bkt − ek,k
t
t . Substituting (37)
and (38) in (36), we get (5). Now consider the per-step cost
given by (3). Note that
XX X X
|
|
j
xt Qt xt =
(xit ) Qi,j
t xt
=

x̆it+1 = Akt x̆it + w̆ti ,

(38)

l∈K

X X

Under the assumptions on the model, the dynamics, given
by (25) and (26), simplify to

(37)

l∈K

Akt

B. Proof of Corollary 3

|
(x̄kt ) px,k,k
x̄kt
t

k∈K i∈N k j∈N k
X X
X X
|
|
−
(xit ) px,k,k
xit +
(xit ) qtk xit
t
k∈K i∈N k
k∈K i∈N k
XX
k
l
k | x,k,l l
=
|N ||N |(x̄t ) pt x̄t
k∈K l∈K
X X
|
+
(xit ) (qtk − px,k,k
)xit
t
k∈K i∈N k
X X 1
|
|
(xit ) Qkt xit ,
(39)
=: xt Ptx xt +
k|
|N
k∈K i∈N k

where Ptx k,l = |N k ||N l |px,k,l and Qkt = |N k |(qtk − px,k,k
).
t
By similar algebraic manipulation, we can show
X X 1
|
|
|
(uit ) Rtk uit , (40)
ut Rt ut = ut Ptu ut +
k
|N |
k
k∈K i∈N

where Ptu k,l = |N k ||N l |pu,k,l and Rtk = |N k |(rtk − pu,k,k
).
t
Substituting (39) and (40) in (3), we get (6).

c̆kT (x̆iT ) −

X

|

(r̄Tk ) QkT r̄Tk .

k∈K



t
To describe c̄t (·), define yt := x̄x̄tt −r̄
−st . Then,


0
| Q̄t
|
c̄t (x̄t , ūt ) = yt
y + ūt (R̄t + Ptu )ūt ,
0 Ptx t

c̄T (x̄T ) =

|
yT


Q̄T
0


0
y .
PTx T

Moreover,
i
1 h i
i | k i
i
i | k i
(x̆
−
r
)
Q
(x̆
−
r
)
+
(ŭ
)
R
ŭ
t
t
t
t
t
t
t t ,
|N k |
i
|
1 h i
c̆kT (x̆iT ) =
(x̆T − rTi ) QkT (x̆iT − rTi ) .
k
|N |

c̆kt (x̆it , ŭit ) =

Then, define a centralized auxiliary system where the state is
x̊t = vec((x̆it )i∈N , x̄t ), action is ůt = vec((ŭit )i∈N , ūt ), and
the per-step cost is given by Corollary 5. Note that the per-step
cost is decomposed into terms that depend only on (x̄t , ūt )
and terms that depend only on (x̆it , ŭit ) (and terms that do not
depend on the control strategy). The rest of the proof follows
along the same lines of the proof of Theorem 1. In particular,

16

we consider a deterministic dynamical system and split it into
K + 1 classes. The agents in class k, k ∈ K, are solving a
tracking problem whose solution is given by
ŭit = L̆kt x̆it + F̆tk vti .
The mean-field component is also solving a tracking problem
whose solution is given by
ūt = L̄t x̄t + F̄t v̄t .
The result of the Theorem follows from combining the above
equations. Therefore, from standard results in LQR tracking
problem, the optimal control law of agent i ∈ N k of subpopulation k ∈ K is given by
i 
h

uit = ŭit + ūkt = L̆kt (xit − x̄kt ) + F̆tk vti + L̄kt x̄t + F̄tk v̄t ,
−1
where gains {L̆kt , L̄kt , F̆tk , F̄tk }Tt=1
are identical for all agents
of sub-population k, v̄t is identical for all agents of all subpopulations, and vti may be different for each agent.

where
|

c̄T (x̄λT ) = (x̄λT ) (Q̄T + PTx )x̄λT ,
bi h i | k i i
(x̆T ) QT x̆T ,
c̆iT (x̆iT ) =
|N k |
where Q̄t and R̄t are defined as in Theorem 4.
The rest of the proof is the same as in Section V-C. We can
show that the optimal control strategy of auxiliary model is
given by
ūλt = L̄t x̄λt

and for k ∈ K, i ∈ N k ,

ŭit = L̆kt x̆it ,

−1
where the gains {L̆kt , L̄t }Tt=1
are given as in Theorem 4. To
complete the proof of Theorem 4, note that


λi k,λ
λi
λi k,λ
k
i
i
i
+ i L̄kt x̄λt .
ut = ŭt + i ūt = L̆t xt − i x̄t
b
b
b

Thus, the control laws specified in Theorem 4 are the optimal
centralized control laws, and, a fortiori, the optimal decentralized control laws.

D. Proof of Theorem 4
The proof follows the same lines as the proof of Theorem 1 with the following
The mean-field is
P differences.
1
i i
(similar
interpretations
λ
x
defined as x̄k,λ
=
k
t
t
i∈N
|N k |
k,λ
k,λ
hold for ūt and w̄t ) and the breve variables are defined
i
(similar interpretations hold for ŭit and
as x̆it = xit − λbi x̄k,λ
t
i
w̆t ). Note that due to (A4), the dynamics of x̆it and x̄λt are
still given by (25) and (26), respectively, where Āt and B̄t are
defined as in Theorem 4.
The equivalent of Lemma 1 is the following:
Lemma 7 Let (λ1 , . . . , λN ) ∈ RN and (b1 , . . . , bN ) ∈ RN
>0 .
In addition, for any x = vec(x1 , . . . , xN ) and x̄λ =
λi λ
i
i
h(λi xi )N
i=1 i, let x̆ = x − bi x̄ , i ∈ {1, . . . , N }. Then, for
any matrix Q of appropriate dimension,

Jalal Arabneydi received Ph.D. degree in Electrical
and Computer Engineering from McGill University,
Montreal, Canada in 2016. He also received B.Sc.
degree from Isfahan University of Technology, IsfaPLACE
han, Iran, in 2006 and M.Sc. degree from University
PHOTO
of Tehran, Tehran, Iran, in 2009 both in ElectriHERE
cal and Computer Engineering, majored in control
systems. He is currently a postdoctoral fellow at
Concordia University. He is the recipient of the
best student paper award at the 53rd Conference on
Decision and Control (CDC) in 2014. His research
interests include decentralized stochastic control, mean field teams, game
and team theory, large-scale system, multi-agent reinforcement learning with
applications in complex networks including smart grids, swarm robotics, and
finance.

N
N
|
1 X i i | i
1 X i i | i
b (x ) Qx =
b (x̆ ) Qx̆ + (x̄λ ) µQx̄λ ,
N i=1
N i=1

where µ := 2 −

1
N

PN

i=1

(λi )2
bi .

Consequently, the equivalent of Corollary 4 is the following
Corollary 6 For time t, t ∈ {1, . . . , T }, there exist functions
{c̆k }k∈K and c̄t such that
X X
ct (xt , ut , x̄λt , ūλt ) = c̄t (x̄λt , ūλt ) +
c̆it (x̆it , ŭit ),
k∈K i∈N k

where
|

|

c̄t (x̄λt , ūλt ) = (x̄λt ) (Q̄t + Ptx )x̄λt + (ūλt ) (R̄t + Ptu )ūλt ,
i
|
bi h i | k i
(x̆t ) Qt x̆t + (ŭit ) Rtk ŭit ,
c̆it (x̆it , ŭit ) =
k
|N |
and for t = T,
cT (xt , x̄λt ) = c̄T (x̄λT ) +

X
i∈N k ,k∈K

c̆iT (x̆iT ),

Aditya Mahajan (S’06–M’09–SM’14) received
B.Tech degree in Electrical Engineering from the
Indian Institute of Technology, Kanpur, India in
2003 and MS and PhD degrees in Electrical EngiPLACE
neering and Computer Science from the University
PHOTO
of Michigan, Ann Arbor, USA in 2006 and 2008.
HERE
He is currently Associate Professor of Electrical
and Computer Engineering at McGill University,
Montreal. In 2017, he held a visiting position at the
University of California, Berkeley. Prior to joining
McGill University, he was postdoctoral researcher at
Yale University, New Haven. He is senior member of the IEEE, member of
SIAM, and member of Professional Engineers Ontario. He currently serves
as an Associate Editor for Mathematics of Control, Signals, and Systems
(MCSS). In the past, he has served as an Associate Editor on the IEEE Control
Systems Society Conference Editorial Board.
His principal research interests include decentralized stochastic control,
team theory, reinforcement learning, multi-armed bandits, and information
theory.

