Sequential Empirical Coordination Under an
Output Entropy Constraint

arXiv:1710.10255v1 [] 27 Oct 2017

Ehsan Shafieepoorfard and Maxim Raginsky, Senior Member, IEEE

Abstract
This paper considers the problem of sequential empirical coordination, where the objective is to achieve a given
value of the expected uniform deviation between state-action empirical averages and statistical expectations under
a given strategic probability measure, with respect to a given universal Glivenko–Cantelli class of test functions. A
communication constraint is imposed on the Shannon entropy of the resulting action sequence. It is shown that the
fundamental limit on the output entropy is given by the minimum of the mutual information between the state and
the action processes under all strategic measures that have the same marginal state process as the target measure
and approximate the target measure to desired accuracy with respect to the underlying Glivenko–Cantelli seminorm.
The fundamental limit is shown to be asymptotically achievable by tree-structured codes.

I. I NTRODUCTION
Decision-making in the presence of limited communication or information acquisition resources has long been a major topic of interest in the study of both networked control systems
[1]–[5] and economics [6]–[12]. The problem becomes more intricate when causality constraints
are imposed, and decisions must be made in real time. There are many recent works on this
topic dealing with various types of information constraints and structural assumptions about the
source (see, e.g., [13]–[20]).
E. Shafieepoorfard and M. Raginsky are with the Department of Electrical and Computer Engineering and
the

Coordinated

Science

Laboratory,

University

of

Illinois

at

Urbana–Champaign,

Urbana,

IL

61801,

USA;

{shafiee1,maxim}@illinois.edu.
Research supported in part by the NSF under CAREER award no. CCF- 1254041, and by the Center for Science of Information
(CSoI), an NSF Science and Technology Center, under grant agreement CCF-0939370. Prelminary version of this work was
presented at the IEEE Conference on Decision and Control, Las Vegas, NV, December 2016.

2

Reconstruction of an information source from its compressed version subject to a fidelity
criterion is the focus of rate-distortion theory [21]; there is also a sequential generalization of
rate-distortion theory [22, Ch. 5] to reconstruction problems with causality constraints. Moreover,
when the reconstruction is fed into a controller that can act on the information source, and if one
can establish some form of the separation principle between estimation and control, the methods
of sequential rate-distortion theory can be brought to bear on the problem of optimal quantizer
design for this problem of control under communication constraints [4], [23]–[31].
However, there is an alternative perspective on the problem of compressed representations in
networked control systems – that of empirical coordination under communication constraints.
The problem of coordination, first introduced in the information theory literature by Cuff et
al. [32] (see also [33]), can be stated as follows: Consider a finite collection of decision makers (or
DM’s, for short), who wish to generate actions in response to a random state variable according
to some prescribed policy, but can only receive information about the state over finite-capacity
noiseless digital links. Suppose that we have a large number of independent and identically
distributed (i.i.d.) copies of the state, and let the DM’s generate a sequence of actions based on
the information they receive about this state sequence. What are the minimal communication
requirements (in bits per copy), to guarantee that the long-term empirical frequencies of realized
states and actions approximate, to desired accuracy, the ideal joint probability law of states and
actions induced by the marginal law of the state and the policy?
Cuff et al. [32] assume that both the state and the actions take values in finite sets, and measure
the quality of approximation by the total variation distance between the empirical distribution
of states and actions and the target joint distribution. However, this criterion is inapplicable
to continuous-valued states and/or actions with nonatomic probability laws because the total
variation distance between any nonatomic probability measure and any discrete probability
measure attains its maximal value. To resolve this issue, Raginsky [34] proposed a relaxed
approximation criterion: Fix a suitable class of bounded real-valued test functions on the space
of all state-action pairs and consider the worst-case deviation between their empirical averages
and their expectations with respect to the target measure. Under the regularity assumption that
the class of test functions has the so-called universal Glivenko–Cantelli property (cf. [35] and
references therein, as well as Section II for definitions), Raginsky [34] obtained a full informationtheoretic characterization of the minimal communication requirements for empirical coordination.

October 30, 2017

DRAFT

3

Since any uniformly bounded class of real-valued functions on a finite set is universal Glivenko–
Cantelli, the framework of [32] emerges as a special case.
In this paper, we present an extension of the empirical coordination framework of [34] to the
sequential setting: We consider a two-terminal network consisting of a sender and a decisionmaker (DM). The sender observes N independent copies of a discrete-time state process of
fixed finite duration T . There is a fixed causal policy for generating actions contingent on the
states, and the DM must implement this policy on each copy of the state process. However, the
DM has no direct access the state process. Instead, the sender can communicate with the DM
over a finite-capacity noiseless digital channel. We are interested in the minimal communication
requirements that are needed to guarantee that, in the limit as N → ∞, the empirical distribution
of states and actions at each time t ∈ [T ] can approximate the state-action distribution induced
by the state process law and by the policy specification. The coding scheme employed by the
sender must satisfy the sequentiality constraint: The signal transmitted by the sender to the DM
at time t may only depend on the realizations of the state processes up to time t. Following
Tatikonda [22], we quantify the communication resources by the Shannon entropy of the signal
process. Entropy constraints on the quantizer output are commonly used in causal source coding
problems, where the compressed representation of the source at time t may depend on the present
and on the past source samples, but not on the future ones [36].
Our main contribution is a full information-theoretic characterization of the fundamental limit
on the amount of communication from the sender to the DM in the setting of sequential empirical
coordination. We refer to this fundamental limit as the sequential rate-distortion function for
empirical coordination. Specifically, we show that, for all large enough N, this fundamental
limit can be achieved by means of tree-structured codes of the kind employed by Tatikonda
[22], and that no sequential scheme for empirical coordination can beat this fundamental limit.1
While we do not make any structural assumptions on the state process (e.g., it is not assumed
1

The reference policy for generating actions contingent on the states may be randomized. However, we restrict the sequential

encoder used by the sender and the sequential decoder used by the DM to be deterministic. The reason for this is that, when
randomized strategies are used in the absence of a noiseless feedback channel from the DM to the sender, the sender has to form
beliefs about the actions taken by the DM, who will in turn form beliefs about the beliefs by the sender about the actions taken
by the DM, and so on, leading to the so-called infinite regress of expectations (see, e.g., [37]). This lack of precise knowledge
on the part of the sender will accumulate over time. Restricting to deterministic strategies removes this problem: at any time t,
the sender is strictly better informed than the receiver and can perfectly reconstruct the actions taken by the receiver.

October 30, 2017

DRAFT

4

to be memoryless, Markov, ergodic, etc.), we assume that the target policy is feedforward (i.e.,
there is no functional dependence of future states on current and past actions).
It is worth mentioning that, like other set-ups that include the interplay between information
acquisition and decision-making, the sequential coordination problem considered here can also
be interpreted in the framework of economics. It arises when a finite number of economic
agents (or sectors) with constrained cognitive (or communication) resources [6] are subject to
idiosyncratic economic shocks. A better-informed information sender – such as a central bank
or monetary authorities – wishes to recommend optimal actions to all the agents through a
common public signal. On average, though, the sender’s optimal signaling strategy must take into
account the limits on information-processing capacities of all of the agents. Our paper addresses
several features of this set-up as well; however, we do not consider situations involving strategic
motives, in which different players involved in the information exchange have biased or opposing
objectives. Strategic considerations have been addressed recently, both in economics [38]–[40]
and in information theory [41].

A. Contents of the paper
The organization of the paper is as follows. We introduce the notation and basic concepts (in
particular, Glivenko–Cantelli classes and the corresponding notion of typicality) in Section II.
The precise formulation of the sequential empirical coordination problem is given in Section III.
The main results are presented in Section IV, with some examples discussed in Section V.
Appendix A contains some technical lemmas needed in the proof of the main theorem.
II. P RELIMINARIES

AND

N OTATIONS

All spaces in this paper are assumed to be standard Borel spaces, as defined below (for
detailed treatments, see the lecture notes of Preston [42] or Chapter 4 of Gray [43]).
Definition 1. A measurable space (X, B(X)) is standard Borel if it can be metrized with a metric
d, such that: 1) (X, d) is a complete separable metric space, and 2) B(X) is the Borel σ-algebra,
i.e., the smallest σ-algebra containing all open sets in (X, d).
Given such a space (X, B(X)), we define the following additional spaces:
1) S(X) is the space of all finite signed Borel measures on X.

October 30, 2017

DRAFT

5

2) P(X) ⊂ S(X) is the space of all Borel probability measures on X.
3) M(X) is the space of all measurable functions f : X → R.
4) Mb (X) ⊂ M(X) is the normed space of all bounded measurable functions f : X → R with
the sup norm
||f ||∞ , sup |f (x)|,
x∈X

and Mb1 (X) := {f ∈ Mb (X) : ||f ||∞ ≤ 1}.
5) Cb (X) ⊂ Mb (X) is the space of all bounded continuous functions on X.
We use the standard inner-product notation for integrals: given any ν ∈ S(X) and f ∈ M(X),
Z
hν, f i :=
f (x) ν(dx).
X

When ν is a probability measure, we will also use the standard expectation notation Eν [f (X)].
A Markov (or stochastic) kernel with input space X and output space Y is a mapping K(·|·) :
B(Y) × X → [0, 1], such that K(·|x) ∈ P(Y) for every x ∈ X and K(B|·) ∈ M(X) for every
B ∈ B(Y). We denote the space of all such kernels by M(Y|X). Any K ∈ M(Y|X) acts on
functions f ∈ M(Y) from the left and on probability measures µ ∈ P(X) from the right:
Z
Kf (·) :=
f (y)K(dy|·),
Y
Z
µK(·) :=
K(·|x)µ(dx),
X

such that Kf ∈ M(X) for any f ∈ M(Y) and µK ∈ P(Y) for any µ ∈ P(X). Given a probability
measure µ ∈ P(X) and a Markov kernel K ∈ M(Y|X), we denote by µ ⊗ K the probability
measure on the product space (X × Y, B(X) ⊗ B(Y)) uniquely specified by its values on the
rectangles A × B, A ∈ B(X), B ∈ B(Y):
(µ ⊗ K)(A × B) :=

Z

K(B|x)µ(dx).

A

If we let A = X in the above definition, then we end up with with µK(B). Note that product
measures µ ⊗ ν, where ν ∈ P(Y), arise as a special case of this construction, since any ν ∈
P(Y) can be realized as a Markov kernel (B, x) 7→ ν(B). Conversely, given a random element
(X, Y ) of X × Y, its probability law ν ∈ P(X × Y) can be disintegrated as µ ⊗ K, where
µ(·) = ν(· × Y) ∈ P(X) is the marginal distribution of X and K ∈ M(Y|X) is a version of the
conditional distribution of Y given X.

October 30, 2017

DRAFT

6

Finally, given a class of measurable functions F ⊆ Mb1 (X), we define the following seminorm
on S(X):
kνkF := sup |hν, f i| .
f ∈F

Notice that if F ≡ Mb1 (X), then k · kF coincides with the total variation norm
kνkTV := 2 sup |ν(A)| .

(1)

A∈B(X)

A. Information-theoretic preliminaries
Throughout the paper, we will need some basic definitions and notions from information theory. The relative entropy (or information divergence) [44] between any two probability measures
µ, ν ∈ P(X) is



dµ

 µ, log
,
dν
D(µkν) :=

+∞,

if µ ≺ ν
otherwise,

where ≺ denotes absolute continuity of µ w.r.t. ν, and dµ/dν is the Radon–Nikodym derivative.
It is always nonnegative, and is equal to zero if and only if µ ≡ ν. The Shannon mutual
information [44] in (µ, K) ∈ P(X) × M(Y|X) is defined as
I(µ, K) := D(µ ⊗ Kkµ ⊗ µK).

(2)

If (X, Y ) is a pair of random objects with Law(X, Y ) = µ ⊗ K, then we will also write
Iµ,K (X; Y ) to denote (2).
Mutual information can be also expressed in terms of entropy and conditional entropy [45].
If X is a random element of X with a purely atomic probability law µ, then its Shannon entropy
is defined as
H(X) := −

X

µ[X = x] log µ[X = x],

x

where the sum is over the atoms of µ. For an arbitrary random element Y jointly distributed
with X, the conditional entropy of X given Y is given by
Z
H(X|Y ) :=
PY (dy)H(X|Y = y),
Y

where H(X|Y = y) is the Shannon entropy of X w.r.t. the regular conditional probability
distribution PX|Y =y . Mutual information can then be expressed as
I(X, Y ) = H(X) − H(X|Y ).

October 30, 2017

(3)

DRAFT

7

Given a random triple (X, Y, Z) ∈ X × Y × Z which admit a joint probability distribution, the
conditional mutual information between X and Y given Z is defined as
Z
I(X; Y |Z) := PZ (dz)D(PXY |Z=z ||PX|Z=z ⊗ PU |Z=z ),
Z

where PZ ∈ P(Z) denote the marginal law of Z, PXY |Z=z denotes the regular conditional
probability distribution of (X, Y ) given Z = z. Moreover, we have (Theorem 3.6.1 of [44])
I(X; Y, Z) = I(X; Z) + I(X; Y |Z).

(4)

We work with natural logarithms throughout the paper, so all entropies and mutual information
is measured in nats.

B. Universal Glivenko-Cantelli classes
The notion of a universal Glivenko-Cantelli class [35] (or uGC class for short) plays a central
role in this paper. The main reason for adopting this notion is that it leads to a fruitful extension
of the notion of typical sequences in standard Borel spaces [34]. We briefly summarize the key
concepts here to keep the presentation self-contained.
Let [N] := {1, . . . , N}, for N ∈ N, and let x[N ] = (x1 , . . . , xN ) denote an N-tuple of elements
of X. The empirical measure of x[N ] is an element of P(X), defined as2
1 X
δxn (·),
Px[N] (·) =
N
n∈[N ]

where δx is the Dirac measure centered at x. If X1 , . . . , XN are i.i.d. random elements of X with
common marginal law µ, then for any f ∈ Mb1 (X) the empirical means
1 X
hPX[N] , f i =
f (Xn ), N ∈ N
N
n∈[N ]

converge to the mean hµ, f i almost surely, by the Strong Law of Large Numbers (SLLN). By
the union bound, this statement carries over to any finite family of functions. Thus, for any
F ⊂ Mb1 (X) with |F | < ∞,
PX[N] − µ

N →∞

F

−−−→ 0,

µ-a.s.

(5)

In general, (5) is referred to as the Uniform Law of Large Numbers (ULLN) over F – that is, the
worst-case absolute deviation between empirical and true means converges to zero uniformly over
2

Since X is a standard Borel space, all singletons are measurable and belong to B(X).

October 30, 2017

DRAFT

8

the function class F . However, ULLN may not hold for an arbitrary infinite class of functions
F on a general Borel space. Specifically, it fails to hold on F ≡ Mb1 (X) if µ has a density.
This observation shows that properly defining the notion of a typical sequence over an abstract
Borel alphabet requires some care. Let us recall the usual definition:
Definition 2. Given a finite set X and a probability distribution µ ∈ P(X) on it, the typical set
(N )

T∆ (µ), for ∆ > 0, is the set of all N-tuples x[N ] ∈ X[N ] whose empirical distributions PX[N]
are ∆-close to µ in the total variation norm:
n
(N )
T∆ (µ) := x[N ] ∈ X[N ] : PX[N] − µ

o
<∆ .

TV

In this case, we have the following implication of (5) with F = Mb1 (X): If X1 , X2 , . . . are i.i.d.
elements of a finite alphabet X with common marginal µ, then


N →∞
(N )
P X[N ] ∈
/ T∆ (µ) −−−→ 0.

(6)

In order to extend the intuitive notion of typicality to general Borel alphabets, we restrict the
class F to be a universal Glivenko–Cantelli class:
Definition 3. A function class F ⊂ Mb1 (X) is a universal Glivenko–Cantelli class (or a uGC
class, for short) if
PX[N] − µ

N →∞

F

−−−→ 0,

µ-a.s.

for any µ ∈ P(X), where X1 , X2 , . . . is stationary memoryless random process with marginal
distribution µ.
Now, typical sequences on general Borel spaces can be defined in the spirit of Definition 2:
Definition 4. Fix a uGC function class F on X. Given a probability measure µ ∈ P(X), the
(N )

typical set T∆,F (µ), for ∆ > 0, is the set of all N-tuples x[N ] ∈ X[N ] whose empirical distributions
PX[N] are ∆-close to µ in the k·kF seminorm:
n
(N )
T∆,F (µ) := x[N ] ∈ X[N ] : PX[N] − µ
(N )

F

o
<∆ .

In other words, the typical set T∆,F (µ) consists of all x[N ] , whose empirical distributions are
∆-consistent with µ on the class F . For example, if X = R, then the class

F := fz = 1(−∞,z] : z ∈ R
October 30, 2017

DRAFT

9

of indicator functions of semi-infinite intervals is a uGC class (this is the well-known Glivenko–
Cantelli theorem, which explains the origin of the name “universal Glivenko–Cantelli”). We then
have the following counterpart of (6):
Proposition 1. Consider a Borel space X and a uGC class F ⊂ Mb1 (X). If X1 , X2 , . . . is a
sequence of i.i.d. random elements of X with common law µ, then for any ∆ > 0
(N )

N →∞

P(X[N ] ∈
/ T∆,F (µ)) −−−→ 0.

(7)

Proof. Immediate from Definitions 3 and 4.
III. P ROBLEM

FORMULATION

We now provide the precise formulation of the problem of sequential empirical coordination
informally stated in Section I. The objective is for the sender to use minimal communication
resources, so that the joint empirical distributions of the states observed by the sender and the
actions generated by the receiver can mimic a given process law subject to a fidelity criterion.
Since this problem involves causality considerations, we need to introduce the definition of a
directed stochastic kernel (for a more detailed presentation in the context of control, see [22]):
Definition 5. Let Y1 , . . . , YM be a collection of Borel spaces. For any any I ⊆ [M], let
Q
YI := i∈I Yi . Fix any set I = {i1 , . . . , iK } with i1 < i2 < . . . < iK , and let I c denote
the complementary set [M] \ I. A directed stochastic kernel between YI c and YI is an element

of M(YI |Y[iK −1] ) that has the form
K(dyI |y[iK −1] ) =

K
O

Tk (dyik |y[ik −1] )

k=1

for a given collection of Markov kernels Tk ∈ M(Yik |Y[ik −1] ), k = 1, . . . , K. We will denote the
−
→
space of all such kernels by M(YI |YI c ).
This definition naturally incorporates causality constraints. If we think of the index i ∈ [M] as
time and let the times ik ∈ I denote the instants when an action must be taken, then the Markov
kernel Tk prescribes the stochastic law for taking a random action at time ik on the basis of the
‘past’ data y1 , y2 , . . . , yik −1 . The stochastic kernel K describes the overall sequential process of
taking actions. A canonical way in which such stochastic kernels arise is to start with a random
element Y[M ] = (Y1 , . . . , YM ) of Y[M ] with probability law P and, for each k ∈ [K], take Tk to be

October 30, 2017

DRAFT

10

the regular conditional probability distribution PYik |Y[ik −1] . This construction yields the directed
stochastic kernel
K( dyI |y[iK −1] ) :=

K
O

PYik |Y[ik −1] (dyik |y[ik −1] ).

k=1

For the problem of empirical coordination, fix the state space X, the action space U, and the
time horizon T . For each t ∈ [T ], introduce the copies Xt and Ut of X and U, respectively. Let
µ ∈ P(X[T ] ) denote the probability law of the state process X[T ] = (X1 , . . . , XT ), which can be
disintegrated as the product of T factors µ(t) ∈ M(Xt |X[t−1] ):
µ(dx[T ] ) =

T
O

µ(t) (dxt |x[t−1] ).

t=1

−
→
Furthermore, let π ∈ M(U[T ] |X[T ] ) denote the directed stochastic kernel whose factors π (t) ∈
M(U|X[t] × U[t−1] ) prescribe the causal policy, according to which the DM takes target actions
in U based on the past history of states and actions. The resulting joint probability law of states
and actions, the so-called strategic measure Pπµ ∈ P(X[T ] × U[T ] ), is given by
O
Pπµ (dx[T ] , du[T ]) := µ(dx[T ] ) ⊗
π (t) (dut |x[t] , u[t−1] )
t∈[T ]

=

O

µ(t) (dxt |x[t−1] ) ⊗ π (t) (dut |x[t] , u[t−1] ).

t∈[T ]

The marginal law of Xt under Pπµ will be denoted by µt ∈ P(X), and the marginal conditional
law of Ut given Xt by πt ∈ M(U|X).
Let X[T ],[N ] := {Xt,n : t ∈ [T ], n ∈ [N]} be a T × N array of random elements of X, where
t ∈ [T ] denotes the time index, while n ∈ [N] enumerates the copies of µ. For all A ⊂ [T ]
and B ⊂ [N], we will denote by XA,B the sub-array (Xt,n : t ∈ A; n ∈ B). For each n ∈ [N]
the columns X[T ],n = (Xt,n )t∈[T ] are i.i.d. copies of the state process with law µ. Similarly, let
{Ut,n : t ∈ [T ]; n ∈ [N]}, denoted with U[T ],[N ], be an array of random elements of U such
that for n ∈ [N] the pair process (X[T ],n , U[T ],n) are i.i.d. copies of the state-action process with
law Pπµ . Notice that both arrays X[T ],[N ] and U[T ],[N ] are independent across [N] while correlated
across [T ]. The empirical distribution of state-action pairs at time t is given by
1 X
δXt,n ,Ut,n .
PXt,[N] ,Ut,[N] :=
N
n∈[N ]

Then, for any uGC class F ⊂ Mb1 (X × U),

PXt,[N] ,Ut,[N] − µt ⊗ πt

October 30, 2017

a.s.

F

−−→ 0

as N → ∞.

(8)

DRAFT

11

Since (8) holds for every t ∈ [T ], we have
T
1X
PXt,[N] ,Ut,[N] − µt ⊗ πt
T t=1

a.s.

F

−−→ 0

as N → ∞.

That is, the realized empirical distributions of states and actions will be asymptotically consistent
with the strategic measure Pπµ , uniformly over F .
We now consider the following sequential coding problem involving an information sender
(IS) and a decision-maker (DM). The IS can transmit messages to the DM over a finite-capacity
channel. At each time t, the IS observes the state realizations X[t],[N ] and sends a message to the
DM who will use this message and all previously received messages to generate the new N-tuple
of actions Ut,[N ] using a deterministic policy. The goal is to ensure that the realized empirical
distributions of states and actions approximate the strategic measure Pπµ to a given accuracy,
while minimizing the communication resources. We will assess the quality of approximation
using a fixed uGC class of test functions, while the communication resources will be measured
in terms of the overall Shannon entropy of the messages sent by the IS to the DM.
Definition 6. A sequential N-code is a collection γ = (γt )t∈[T ] of measurable mappings
γt : X[t],[N ] → Ut,[N ]
with countable ranges.
Given a state process law µ ∈ P(X[T ] ) and an N-code γ, we let Pγµ ∈ P(X[T ],[N ] × U[T ],[N ])
denote the induced strategic measure, i.e., joint probability law of the states observed by the IS
and the actions generated by the DM:
Pγµ (dx[T ],[N ], du[T ],[N ]) =

O

n∈[N ]

µ(dx[T ],n ) ⊗

O

δγt (x[t],[N] ) (dut,[N ] ).

(9)

t∈[T ]

We are interested in the minimum information transmission rate needed by a sequential N-code
in order to ensure that the realized sequence of states observed by the sender and actions taken
by the decision-maker is ∆-consistent (in expectation) with the target measure Pπµ on a fixed
but arbitrary uGC class F ⊂ Mb1 (X × U). That is, we wish to design γ, so that
T
1X γ
E PXt,[N] ,Ut,[N] − µt ⊗ πt
T t=1 µ

October 30, 2017

F

≤ ∆,

(10)

DRAFT

12

while minimizing the total Shannon entropy of the messages U1,[N ] = γ1 (X1,[N ] ), . . . , U[T ],N =
γT (X[T ],[N ]). Let



1 X γ
N
Eµ PXt,[N] ,Ut,[N] − µt ⊗ πt
Γµ,π (∆) := γ = (γt )t∈[T ] :

T
t∈[T ]

F



≤∆


(11)

be the set of all sequential N-codes that meet the criterion in (10). With this, we define the
operational sequential rate-distortion function for empirical coordination:

H U[T ],[N ]
b
,
RT,N (∆) , inf
NT
γ∈ΓN
µ,π (∆)

(12)

where H(U[T ],[N ]) is the joint Shannon entropy of the actions generated by the IR using γ.
IV. M AIN

RESULTS

Our main result addresses two questions pertaining to the operational rate-distortion function
defined in (12):
1) What is the minimum information transmission rate needed for IS to induce an empirical
state-action distribution that is ∆-consistent (in expectation) with the target measure Pπµ ?
2) Can this minimum rate can be achieved by sequential N-codes?
In order to address these questions, we first introduce an information-theoretic counterpart of
(12), which we refer to as the sequential rate-distortion function for empirical coordination.
−
→
Consider the subset of M(U[T ] |X[T ] ) consisting of those directed stochastic kernels whose
induced marginal distributions of (Xt , Ut ) at each t ∈ [T ] are ∆-consistent with Pπµ , on average:
)
(
T
−
→
1X
kµt ⊗ π̃t − µt ⊗ πt kF ≤ ∆ ;
Πµ,π (∆) := π̃ ∈ M(U[T ] |X[T ] ) :
T t=1

−
→
here, given some π̃ ∈ M(U[T ] |X[T ] ), π̃t ∈ M(U|X) denotes the induced conditional distribution

of Ut given Xt . Then, the sequential rate-distortion function for empirical coordination is defined
as
RT (∆) :=

October 30, 2017

Iµ,π̃ (X[T ] ; U[T ] )
.
π̃∈Πµ,π (∆)
T
inf

(13)

DRAFT

13

−
→
Remark 1. For any π̃ ∈ M(U[T ] |X[T ] ), Ut and (Xt+1 , . . . , XT ) are conditionally independent
given (X[t] , U[t−1] ) for each t ∈ [T ]. Using this fact and the chain rule for mutual information
(4), we can write
Iµ,π̃ (X[T ] ; U[T ] ) =

X

Iµ,π̃ (X[T ] ; Ut |U[t−1] )

t∈[T ]

=

X

Iµ;π̃ (X[t] , Ut |U[t−1] ),

(14)

t∈[T ]

where the quantity in (14) is the directed information Iµ,π̃ (X[T ] → U[T ] ) [22]. Thus, we can
express the rate-distortion function in (13) as
RT (∆)

Iµ,π̃ (X[T ] → U[T ] )
.
π̃∈Πµ,π (∆)
T
inf

(15)

Thus, RT (∆) is the empirical coordination counterpart of the sequential rate-distortion function
[22]. Equation (15) conveys an important intuitive concept, beyond the common information content embodied in the concept of mutual information. In a stochastic dynamical system, past states
and actions convey information about the current state. Each of the terms Iµ,π̃ (X[t] ; Ut |U[t−1] )
denotes the amount of information that needs to be conveyed about the state history X[t] beyond
what is contained in U[t−1] in order to pin down the current action Ut .



The rate-distortion function RT (∆) gives the smallest amount of information that any causal
policy must convey about the sequence of states, on average per unit time, in order for the
resulting joint measure to be ∆-consistent (in expectation) with the postulated target measure
Pπµ on the class F . Theorems 1 and 2 below state that the sequential rate-distortion function
for empirical coordination defined in (13) is the asymptotic fundamental limit of the empirical
coordination problem formulated in Section III.
Theorem 1 (Achievability). Suppose RT (∆) < ∞. Then, for each ε > 0, there exists N(ε) ∈ N,
such that
bT,N (∆ + ε) ≤ RT (∆) + ε.
R

In other words, under the conditions of the theorem, for each sufficiently large N, we can find a
sequential N-code in ΓN
µ,π (∆ + ε), whose output entropy (normalized by NT ) is approximately
bounded by RT (∆).
Proof. The proof relies on two technical lemmas, cf. Appendix A.

October 30, 2017

DRAFT

14

Since RT (∆) < ∞, there exists some π̃ ∈ Πµ,π (∆ + 2ε ) such that
1
ε
Iµ;π̃ (X[T ] , U[T ] ) < RT (∆) + .
T
2
For each t, define the function
ψt,N (xt,[N ] ; ut,[N ] ) := Pxt,[N] ,ut,[N] − µt ⊗ π̃t

F

.

Since F is a uGC class and since (Xt,1 , Ut,1 ), . . . , (Xt,N , Ut,N ) are i.i.d. under Pπ̃µ , we have


max lim Eπ̃µ ψt,N (Xt,[N ] , Ut,[N ] ) = 0.
t∈[T ] N →∞

ε
Then by Lemma 1 in Appendix A, there exists a sequential N-code γ ∈ ΓN
µ,π̃ ( 2 ), such that, for

U[T ],[N ] = γt (X[t],[N ]) t∈T , we have

H(U[T ],[N ])
1
ε
≤ Iµ,π̃ (X[T ] ; U[T ] ) + < RT (∆) + ε.
NT
T
2

Moreover, using the triangle inequality, we can estimate
1 X γ
Eµ PXt,[N] ,Ut,[N] − µt ⊗ πt
T
F
t∈[T ]

≤

1 X γ
Eµ PXt,[N] ,Ut,[N] − µt ⊗ π̃t
T
t∈[T ]

F

+

1 X
kµt ⊗ π̃t − µt ⊗ πt kF
T
t∈[T ]

≤ ∆ + ε.
b
Thus, γ ∈ ΓN
µ,π (∆ + ε), and therefore, from the definition of RT,N (·), it follows that
bT,N (∆ + ε) ≤ H(U[T ],[N ]) ≤ RT (∆) + ε.
R
NT

Theorem 2 (Converse). For any N, T and ∆,
bT,N (∆) ≥ RT (∆).
R

In other words, the average output entropy of any N-code γ ∈ ΓN
µ,π (∆) must be at least as large
as RT (∆).
Proof. The proof uses the techniques from [34]. Fix an arbitrary sequential N-code γ ∈ ΓN
µ,π (∆),
and let (X[T ],[N ], U[T ],[N ]) the state-action process with process law Pγµ . Let J be a random variable
uniformly distributed on [N], independently of (X[T ],[N ], U[T ],[N ]). Consider the random couple
(X[T ],J , U[T ],J ). From symmetry and independence, it follows that the marginal distribution of
October 30, 2017

DRAFT

15

X[T ],J is equal to µ. For each t ∈ [T ], let π̃ (t) ∈ M(U|X[t] × U[t−1] ) be the induced conditional
law of Ut,J given (X[t],J , U[t−1],J ), and let π̃t ∈ M(U|X) denote the induced conditional law of
Ut,J given Xt,J . Then we have the following chain of equalities and inequalities:

H (γt (X[t],[N ]))t∈[T ] =H(U[T ],[N ])
(a)

=I(X[T ],[N ]; U[T ],[N ])

(b)

≥

X

I(X[T ],n ; U[T ],n)

n∈[N ]
(c)

=NI(X[T ],J ; U[T ],J |J)

(d)

=NI(X[T ],J ; U[T ],J , J)
≥NIµ,π̃ (X[T ] , U[T ] ),

where:
•

(a) follows from the fact that the map X[T ],[N ] → U[T ],[N ] is deterministic;

•

(b) is a standard information-theoretic fact: if X[N ] is a sequence of independent random
variables, then for any sequence Y[N ] of random variables jointly distributed with the Xn ’s,
X
I(Xn ; Yn ) ≤ I(X[N ] ; Y[N ] );
n∈[N ]

•

(c) follows from the construction of J;

•

(d) follows from the fact that, since {X[T ],1, . . . , X[T ],N } are i.i.d., J and X[T ],J are independent (see Appendix B in [34]), and from equation (4).

The remaining steps are consequences of definitions and of standard information-theoretic identities. Dividing both sides by NT , we obtain the bound


H U[T ],[N ]
Iµ,π̃ (X[T ] ; U[T ] )
≤
.
T
NT

Now, for each t ∈ [T ], Xt,J is independent of J, and has the same law as Xt,1 , namely µt .
Moreover, (cf. Appendix B in [34]), the expected empirical distribution Eγµ PXt,[N] ,Ut,[N] is equal

October 30, 2017

DRAFT

16

to µt ⊗ π̃t . Then we have
X

kµt ⊗ πt − µt ⊗ π̃t kF

t∈[T ]

=

X

Eγµ PXt,[N] ,Ut,[N] − µt ⊗ π̃t

t∈[T ]

≤

X

Eγµ PXt,[N] ,Ut,[N] − µt ⊗ π̃t

t∈[T ]

F

F

≤ ∆,
where the first inequality is by convexity, while the second inequality is by assumption on γ.

Therefore, π̃ = π̃ (t) t∈[T ] ∈ Πµ,π (∆), and consequently

H U[T ],[N ]
Iµ,π̃ (X[T ] ; U[T ] )
≤
,
RT (∆) ≤
T
NT
bT,N (∆).
by definition. Since this holds for every γ ∈ ΠN (∆), it follows that RT (∆) ≤ R
µ,π

V. I MPLICATIONS

Although Theorems 1 and 2 provide a full characterization of the fundamental limits on
the minimal rate of communication for sequential empirical coordination, the computation of
the sequential rate distortion function RT (∆) is a complicated infinite-dimensional optimization
problem already in the static (T = 1) case, which was addressed in [34]. Below, we provide
two examples that illustrate the difficulty of explicitly computing RT (∆) even for T = 1.
A. Kolmogorov-Smirnov criterion for one-step costs
While we have remained silent on the nature of the target strategic measure Pπµ , it may have
been selected based on considerations of expected cost. Thus, suppose that we have a function
c ∈ M(X × U), such that c(x, u) gives the cost of taking action u in response to state x. Let F
be the class of indicator functions of the level sets of c:
f (x, u) , 1{c(x, u) ≤ a},

a ∈ R.

(16)

Then we have the following:
Proposition 2. Let F denote the class of all f of the form (16). Then for any two P, Q ∈
P(X × U),
kP − QkF = dKS(FP ◦c−1 , FQ◦c−1 ),
October 30, 2017

(17)

DRAFT

17

where Fµ denotes the cumulative distribution function (cdf) of a Borel probability measure µ on
the reals, and
′

′

dKS (F, F ) := sup |F (a) − F (a)|

(18)

a∈R
′

is the Kolomogorov-Smirnov distance between cdf’s F and F . The class F is a universal
Glivenko-Cantelli class.
Proof. Fix any pair P, Q ∈ P(X × U). Then the chain of equalities
kP − QkF = sup |P [c(X, U) ≤ a] − Q[c(X, U) ≤ a]|
a∈R

= sup |FP ◦c−1 (a) − FQ◦c−1 (a)|
a∈R

=dKS (FP ◦c−1 , FQ◦c−1 )
follows from definitions. By the classical Glivenko-Cantelli theorem [14, Prop. 4.24], the class
of all indicator functions r 7→ 1{r ≤ a}, a ∈ R, is a uGC class on (R, B(R)). Therefore, since
{P ◦ c−1 : P ∈ P(X × U)} ⊂ P(R), F is a uGC class of functions on X × U.
The following is immediate from the above proposition:
Theorem 3.
RT (ε) =

inf

−
→
π̃∈M(UT |XT )


Iµ,π̃ (X[T ] ; U[T ] ) :

)
T
1X
dKS (F(µt ⊗π̃t )◦c−1 , F(µt ⊗πt )◦c−1 ) ≤ ∆ .
T t=1

(19)

In other words, RT (∆) is the smallest mutual information between the state process X[T ] with
law µ ∈ P(X[T ] ) and any action process U[T ] generated from X[T ] by a causal policy π̃, such that
the time average of the Kolmogorov-Smirnov distances between the state-action costs under π̃
and the target policy π is bounded from above by ∆. Evaluating this quantity exactly is difficult
even for T = 1.
B. Weak convergence and Wasserstein distances
Another example concerns approximation of the target strategic measure Pπµ in a certain metric
that metrizes the topology of weak convergence of probability measures. Suppose that X × U is
a Polish space with a given metric d. For any f ∈ Mb (X × U), define the Lipschitz norm
kf kLip :=

October 30, 2017

|f (x, u) − f (y, v)|
(x,u),(y,v)∈X×U d((x, u), (y, v))
sup

(20)

DRAFT

18

and the bounded Lipschitz norm
kf kBL , kf k∞ + kf kLip

(21)

Proposition 3. Consider the function class F = {f ∈ Mb1 (X × U) : kf kBL ≤ 1}. Then, for any
two P, Q ∈ P(X × U),
||P − Q||F = dBL (P, Q),

(22)

the bounded Lipschitz metric on P(X × U) that metrizes the topology of weak convergence of
probability measures. The class F is a universal Glivenko-Cantelli class.
Proof. Eq. (22) is the definition of the bounded Lipschitz metric [46, Sec. 11.3], which
metrizes the topology of weak convergence of probability measures [46, Thm. 11.3.3]. Now, let
(X1 , U1 ), (X2 , U2 ), ... be a sequence of i.i.d. random elements of X × U with common marginal
law P . Then
n→∞

dBL (P(X[n] ,U[n] ) , P) −−−→ P, a.s.

(23)

by Varadarajan’s theorem [46, Thm. 11.4.1]. Since this holds for any P ∈ P(X), and in light of
(22), we conclude that F is a uGC class.
Under an additional moment condition, the bounded Lipschitz metric can be upper-bounded
by the so-called Wasserstein metric. Let P0 (X × U) ⊂ P(X × U) be the set of all probability
measures P for which there exists some (x0 , u0 ) ∈ X × U, such that hP, d(·, (x0, u0 ))i < ∞.
The Wasserstein metric between any two P, Q ∈ P0 (X × U) is
Wd (P, Q) ,

sup |hP, f i − hQ, f i|.

(24)

kf kLip ≤1

We can now give the following upper bound on the sequential rate-distortion function RT (∆)
w.r.t. F :
Theorem 4. Suppose that Pπµ ∈ P0 (X × U). Then

RT (∆) ≤ −→ inf
Iµ,π̃ (X[T ] ; U[T ] ) :
π̃∈M(U[T ] |X[T ] )



X
1
Wd (µt ⊗ π̃, µt ⊗ πt ) ≤ ∆ .

T

(25)

t∈[T ]

Again, despite the clean conceptual interpretation of RT (∆) in terms of approximating strategic
measures by empirical distributions of state-action pairs under the bounded Lipschitz metric, it
does not admit closed-form expressions even for T = 1.

October 30, 2017

DRAFT

19

A PPENDIX A
T ECHNICAL

LEMMAS FOR THE PROOF OF

T HEOREM 1

Lemma 1 below is at the heart of the proof of Theorem 1. It states that, for any sequence of
functions on N-blocks of state-action pairs whose expected values vanish asymptotically under
a given strategic measure, one may construct a sequence of sequential N-codes, under which the
expected value of the time-average of these functions can be made arbitrarily small, and whose
output entropy is upper-bounded by the mutual information of the source and action under the
given probability measure.
−
→
Lemma 1. Consider a pair (µ, π̃) ∈ P(X[T ] ) × M(U[T ] |X[T ] ), such that Iµ,π̃ (X[t] ; Ut |U[t−1] ) < ∞
for each t ∈ [T ]. Let (X[T ],n, U[T ],n )n∈[N ] be N i.i.d. copies of the state-action processes with
process law Pπ̃µ . Let ψt,N be a sequence of bounded measurable functions ψt,N : Xt,[N ] ×Ut,[N ] →
[0, 1] obeying


lim Eπ̃µ ψt,N (Xt,[N ] , Ut,[N ] ) = 0.

N →∞

Then, for any ε > 0, there exists N0 = N0 (ε), such that, for every N > N0 , we can find T
mappings γt,N : X[t],[N ] → U[N ] , t ∈ [T ], satisfying


1 X
Eµ ψt,N (Xt,[N ] , γt,N (X[t],[N ] )) ≤ ε,
T

(A.1)

t∈[T ]

while

Proof. Let δt,N

n

o
1
1
H
γt,N (X[t],[N ])
≤ Iµ,π̃ (X[T ] ; U[T ] ) + ε.
NT
T
t∈[T ]


:= Eπ̃µ ψt,N (Xt,[N ] , Ut,[N ] ) and define the set
o
n
p
At,N := (xt,[N ] , ut,[N ]) : ψt,N (xt,[N ] , ut,[N ] ) ≤ δt,N .

(A.2)

(A.3)

By Markov’s inequality,

p
δt,N
N →∞
Pπ̃µ [Act,N ] ≤ p
= δt,N −−−→ 0.
δt,N

This implies that, for each t ∈ [T ], the state-action tuple (Xt,[N ] , Ut,[N ] ) generated according to
(µ, π̃) belongs to At,N with high probability. By Lemma 2 below, for all large enough N, there
exist measurable mappings γt,[N ] : X[t],[N ] → Ut,[N ] , t ∈ [T ], such that3
Mt := γt,[N ] (X[t],[N ] ) − 1 = eN (Rt +ε) ,
3

By adjusting ε, we can ensure that Mt is an integer.

October 30, 2017

DRAFT

20

where Rt = Iµ,π̃ (X[t] ; Ut |U[t−1] ), and


max Pµ (Xt,[N ] , γt (X[t],[N ] )) 6∈ At,N
t∈[T ]
n 

≤ T max Pπ̃µ (Xt,[N ] , Ut,[N ] ) 6∈ At,N
t∈[T ]



+ Pπ̃µ it (X[t],[N ] , U[t],[N ] ) > N(Rt + ε/2)
o
−N (Rt +ε/2)
+ exp (−Mt e
)
np

o
π̃
N ε/2
δt,N + Pµ it (X[t],[N ], U[t],[N ] ) > N(Rt + ε/2) ,
≤ T exp(−e
) + T max
t∈[T ]

where

is (x[s],[N ], u[s],[N ]) := log

dPµ,π̃
Us,[N] |(X[s],[N] ,U[s−1],[N] )=(x[s],[N] ,u[s−1],[N] )
dPµ,π̃
Us,[N] |U[s−1],[N] =u[s−1],[N]

(us,[N ]).

are the conditional information densities. Now, since ψt,N takes values in [0, 1], we can write


1 X
Eµ ψt,N (Xt,[N ] , γt,N (Xt,[N ] ))
T
t∈[T ]

≤ max Pµ [(Xt,[N ] , γt (X[t],[N ] )) 6∈ At,N ] + max
t∈[T ]

t∈[T ]

p

δt,N ,

(A.4)

For all sufficiently large N, the right hand side of (A.4) can be made smaller than ε. To see
this, notice that max δt,N → 0 as N → ∞ by assumption. Moreover, since
t∈[T ]

it (X[t],[N ], U[t],[N ] ) := log

=

X

dPµ,π̃
Ut,[N] |X[t],[N] ,U[t−1],[N]
dPµ,π̃
Ut,[N] |U[t−1],[N]
log

(X[t],[N ] , U[t],[N ])

dPµ,π̃
Ut,n |X[t],n ,U[t−1],n

n∈[N ]

dPµ,π̃
Ut,n |U[t−1],n

(X[t],n , U[t],n ),

is a sum of i.i.d. random variables, and
Rt =Iµ,π̃ (X[t] ; Ut |U[t−1] ) =
the quantity


1 π̃ 
Eµ it (X[t],[N ] , U[t],[N ] ) ,
N



max Pπ̃µ it (X[t],[N ] , U[t],[N ]) > N(Rt + ε/2)
t∈[T ]

can be made as small as desired for all large N, according to the law of large numbers. Therefore,
we can find a sufficiently large N0 = N(ε) and a sequential code γ = (γt,N )t∈[T ] , such that
Eq. (A.1) holds.

October 30, 2017

DRAFT

21

Towards verifying Eq. (A.2), let Pγµ be the joint probability law of X ∼ µ and the output of
γ. For (X, U) ∼ Pγµ , we have

n

o
1
H
γt,N (X[t],[N ])
NT
t∈[T ]
H(U)
=
NT
1
H(U1,[N ] , U2,[N ] , . . . , UT,[N ] )
=
NT
(a) 1 X
=
H(Ut,[N ] |Ut−1,[N ] )
NT
t∈[T ]

(b)

≤

1 X
log(Mt + 1)
NT
t∈[T ]

(c)

≤

1 X
N(Rt + ε)
NT
t∈[T ]

=

1 X
(Rt + ε)
T
t∈[T ]

=

1 X
(Iµ,π̃ (X[t] , Ut |U[t−1] ) + ε)
T
t∈[T ]

1
Iµ,π̃ (X[T ] ; U[T ] ) + ε
T
where (a) is by the chain rule for entropy; (b) uses the fact that conditioning reduces entropy
(d)

=

and the fact that Ut,[N ] can take at most Mt + 1 values by construction of γt,N ; (c) is by the
choice of Mt ’s; and (d) uses the chain rule for mutual information.
Lemma 2. Let X and U be standard Borel spaces, and consider a pair (µ, π̃) ∈ P(X[T ] ) ×
−
→
M(U[T ] |X[T ] ), such that Rt = Iµ,π̃ (X[t] ; Ut |U[t−1] ) < ∞ for all t ∈ [T ]. Let (X[T ],n, U[T ],n )n∈[N ]
be N i.i.d. draws from the strategic measure Pπ̃µ . Let At ∈ B(Xt,[N ] × Ut,[N ] ), t ∈ [T ], be a
collection of Borel sets. Then, for a given ε > 0 and any sequence of positive integers Mt , there
exist measurable mappings gt : X[t],[N ] → Ut,[N ] , t ∈ [T ], such that for each t ∈ [T ] and each
x[t−1],[N ] , gt (x[t−1],]N , ·) takes at most Mt + 1 values, and

 X n π̃ 

Pµ (Xt,[N ] , gt (X[t],[N ] )) ∈ At ≤
Pµ (Xs,[N ], Us,[N ] ) ∈ As
s∈[t]



+ Pπ̃µ is (X[s],[N ], U[s],[N ]) > N(Rs + ε)
o
+ exp −Ms e−N (Rs +ε) ,

October 30, 2017

(A.5)

DRAFT

22

where
is (x[s],[N ], u[s],[N ]) := log

dPµ,π̃
Us,[N] |(X[s],[N] ,U[s−1],[N] )=(x[s],[N] ,u[s−1],[N] )
dPµ,π̃
Us,[N] |U[s−1],[N] =u[s−1],[N]

(us,[N ]).

are the conditional information densities.
Proof. We will use a random sequential selection procedure to construct the sequence of mappings g1 , g2 , . . . , gT . The overall idea is a generalization of the proof of the achievability part of
the lossy source coding theorem (see, e.g., [47] or [43]).
Given Pπ̃µ , let ν ∈ P(U[T ] ) denote the marginal distribution of the action process and disintegrate it as
ν(du[T ] ) =

O

νt (dut |u[t−1] ).

t∈[T ]

For each t ∈ [T ], define the Markov kernel νt,[N ] ∈ M(Ut,[N ] | U[t−1],[N ] ) via
O
νt,[N ] (dut,[N ] |u[t−1],[N ]) ,
νt (dut,n |u[t−1],n ).
n∈[N ]

In order to construct the finite-range mappings gt (·) : X[t],[N ] → U[N ] , we first choose the elements
of U[N ] to make up the range of gt and then specify how to assign one of these elements to each
x[t],[N ] in the domain X[t],[N ] .
For the first step, pick an arbitrary tuple u[N ] (0) ∈ U[N ] . Then let u[N ] (1), . . . , u[N ](M1 ) be
i.i.d. draws from ν1,[N ] , and take the set {u[N ] (0), . . . , u[N ] (M1 )} as the finite range of g1 . For
the second step and for each i1 ∈ [M1 ], let u[N ] (i1 , 1), . . . , u[N ](i1 , M2 ) be M2 i.i.d. draws from
ν2,[N ] (·|u[N ](i1 )), and take the set
{u[N ] (i1 , i2 )}i1 ∈[M1 ],i2 ∈[M2 ] ∪ {u[N ](0)}
as the range of g2 . This process is continued inductively at each t: for each (i1 , . . . , it−1 ), we let
u[N ](i1 , . . . , it−1 , 1), . . . , u[N ] (i1 , . . . , it−1 , Mt )
be Mt i.i.d. draws from νt,[N ] (·|u[N ](i1 , . . . , it−1 )), and take
{u[N ](i1 , . . . , it−1 , it )}i1 ∈[M1 ],...,it ∈[Mt ] ∪ {u[N ] (0)}
as the range of gt . Evidently, the range of each gt is selected at random conditionally on the
realizations of the ranges of g1 , . . . , gt−1 . The resulting collection of elements of U[N ] can be
arranged on a rooted tree of depth T , where the root has M1 children, each depth-1 node has
M2 children, etc. Following Tatikonda [22], we refer to this construction as a tree code.
October 30, 2017

DRAFT

23

We now complete the construction of the gt ’s. To that end, we use the following recursive
procedure. For t ∈ [T ] and x[t],[N ] , suppose that g1 , . . . , gt−1 have already been specified.
Given x[t],[N ] , if gt−1 (x[t−1],[N ] ) = u[N ] (0), then we let gt (x[t],[N ] ) = u[N ] (0). Otherwise, if
gt−1 (x[t−1],[N ] ) = u[N ] (i1 , . . . , it−1 ), consider the set
Gt (x[t],[N ] ) := {u[N ](i1 , . . . , it−1 , j) : (xt,[N ] , u[N ](i1 , . . . , it , j)) ∈
/ At }.
If it is empty, then let gt (x[t],[N ] ) = u[N ] (0); otherwise, let
gt (x[t],[N ] ) = u[N ] (i1 , . . . , it−1 , j ∗ )
where j ∗ ∈ [Mt ] is the smallest index j of all u[N ] (i1 , . . . , it−1 , j) ∈ G(x[t],[N ] ).
For each t, let Et denote the event that gt (X[t],[N ]) = u[N ] (0). We upper-bound the probability
of Et , with respect to both µ and the random choice of the ranges of g1 , . . . , gT . By construction
of gt ’s, Et will occur if either Et−1 has occurred or if Gt (x[t],[N ] ) = ∅ and none of E1 , . . . , Et−1
have occurred. Therefore,
c
P[Et ] ≤ P[Et−1 ] + P[{Gt (X[t],[N ]) = ∅} ∩ E1c ∩ · · · ∩ Et−1
].

(A.6)

By symmetry and independence in the generation of the ranges of gt , we can estimate the second
term on the right-hand side of (A.6) by
c
P[{Gt (X[t],[N ] ) = ∅} ∩ E1c ∩ · · · ∩ Et−1
]
Z
≤ Pπ̃µ (dx[t],[N ] )Pπ̃µ (du[t−1],[N ])(1 − νt,[N ] ((xt,[N ] , Ut,[N ] ) ∈ Act | u[t−1],[N ]))Mt .

(A.7)

Moreover, if we define the sets

At (xt,[N ] ) := ut,[N ] : (xt,[N ] , ut,[N ] ) ∈ At ,

Bt (x[t],[N ] , u[t−1],[N ]) := ut,[N ] : it (x[t],[N ] , u[t],[N ]) > N(Rt + ε) ,

October 30, 2017

DRAFT

24

then, performing a change of measure, we get
νt,[N ] ((xt,[N ] , Ut,[N ] ) ∈ Act | u[t−1],[N ])
≥ νt,[N ] (Act (xt,[N ] ) ∩ Btc (x[t],[N ] , u[t−1],[N ]) | u[t−1],[N ] )
Z
= PUt,[N]|X[t],[N],U[t−1],[N] (dut,[N ] |x[t],[N ] , u[t−1],[N ]))
1{ut,[N] ∈(Act (xt,[N] )∩Btc (x[t],[N],u[t−1],[N] )} exp[−it (x[t],[N ] , u[t],[N ])]
≥ e−N (Rt +ε)
Z
PUt,[N]|X[t],[N],U[t−1],[N] (dut,[N ] |X[t],[N ], U[t−1],[N ] ))
1{ut,[N] ∈(Act (xt,[N] )∩Btc (x[t],[N] ,u[t−1],[N])} .
Using the inequality (1 − ab)M ≤ 1 − b + e−M a for a, b ∈ [0, 1] , we can estimate
 Mt
1 − νt,[N ] ((xt,[N ] , Ut,[N ] ) ∈ At | u[t−1],[N ])

≤ 1 − Pπ̃µ [(Xt,[N ] , Ut,[N ] ) ∈ Act , it (X[t],[N ] , U[t],[N ]) ≤ N(Rt + ε) | x[t],[N ] , u[t−1],[N ]]

+ exp −Mt e−N (Rt +ε) .

(A.8)

From Eqs. (A.6)–(A.8), it therefore follows that



P[Et ] ≤ P[Et−1 ] + Pπ̃µ (Xt,[N ] , Ut,[N ] ) ∈ At


+Pπ̃µ it (X[t],[N ] , U[t],[N ]) > N(Rt + ε)

+ exp −Mt e−N (Rt +ε) .

Solving this recursion, we obtain the bound
X 

P[Et ] ≤
Pπ̃µ (Xt,[N ] , Ut,[N ] ) ∈ At
t∈[T ]



+Pπ̃µ it (X[t],[N ] , U[t],[N ]) > N(Rt + ε)

+ exp −Mt e−N (Rt +ε) .

for every t ∈ [T ]. By construction,

P[(Xt,[N ] , gt (X[t],[N ])) ∈ At ] ≤ P[Et ],

t ∈ [T ],

where the probability is w.r.t. the joint law of X and the randon selections of g1 , . . . , gT .
Therefore, there exists at least one choice of g1 , . . . , gT satisfying (A.5).

October 30, 2017

DRAFT

25

R EFERENCES
[1] H. Witsenhausen, “On the structure of real-time source coders,” Bell Systems Technical Journal, vol. 58, no. 6, pp. 1437–
1451, 1979.
[2] D. Teneketzis, “Communication in decentralized control,” Ph.D. dissertation, Massachusetts Institute of Technology, 1980.
[3] J. C. Walrand and P. Varaiya, “Optimal causal coding-decoding problems,” IEEE Transactions on Information Theory,
vol. 29, no. 6, pp. 814–820, 1983.
[4] S. K. Mitter, “Control with limited information,” European Journal of Control, vol. 7, no. 2, pp. 122–131, 2001.
[5] E. Shafieepoorfard, M. Raginsky, and S. P. Meyn, “Rationally inattentive control of Markov processes,” SIAM Journal on
Control and Optimization, vol. 54, no. 2, pp. 987–1016, 2016.
[6] C. Sims, “Implications of rational inattention,” Journal of Monetary Economics, vol. 50, no. 3, pp. 665–690, 2003.
[7] Y. Luo et al., Rational Inattention, Portfolio Choice, and the Equity Premium.

School of Economics and Finance,

University of Hong Kong, 2006.
[8] L. Huang and H. Liu, “Rational inattention and portfolio selection,” The Journal of Finance, vol. 62, no. 4, pp. 1999–2040,
2007.
[9] S. Van Nieuwerburgh and L. Veldkamp, “Information acquisition and under-diversification,” The Review of Economic
Studies, vol. 77, no. 2, pp. 779–805, 2010.
[10] A. Tutino, “Rationally inattentive consumption choices,” Review of Economic Dynamics, vol. 1, no. 2006, pp. 1–19, Apr.
2012. [Online]. Available: http://linkinghub.elsevier.com/retrieve/pii/S1094202512000208
[11] F. Matějka, “Rationally inattentive seller: Sales and discrete pricing,” The Review of Economic Studies, vol. 83, no. 1,
pp. 1125–1155, 2016.
[12] D. Martin, “Strategic pricing and rational inattention to quality,” Games and Economic Behavior, vol. 104, pp. 131–145,
2017.
[13] V. S. Borkar, S. K. Mitter, and S. Tatikonda, “Optimal sequential vector quantization of markov sources,” SIAM journal
on Control and Optimization, vol. 40, no. 1, pp. 135–148, 2001.
[14] V. Borkar, S. Mitter, A. Sahai, and S. Tatikonda, “Sequential source coding: an optimization viewpoint,” in 44th IEEE
Conference on Decision and Control and European Control Conference, CDC-ECC’05. IEEE, 2005, pp. 1035–1042.
[15] D. Teneketzis, “On the structure of optimal real-time encoders and decoders in noisy communication,” IEEE Transactions
on Information Theory, vol. 52, no. 9, pp. 4017–4035, 2006.
[16] S. Yuksel, T. Basar, and S. P. Meyn, “Optimal causal quantization of Markov sources with distortion constraints,” in
Information Theory and Applications Workshop, 2008.

IEEE, 2008, pp. 26–30.

[17] C. D. Charalambous, P. Stavrou, N. U. Ahmed et al., “Nonanticipative rate distortion function and relations to filtering
theory,” IEEE Transactions on Automatic Control, vol. 59, no. 4, pp. 937–952, 2014.
[18] T. Linder and S. Yuksel, “On optimal zero-delay coding of vector Markov sources,” IEEE Transactions on Information
Theory, vol. 60, no. 10, pp. 5975–5991, 2014.
[19] T. Tanaka, K.-K. K. Kim, P.A. Parrilo, and S.K. Mitter, “Semidefinite programming approach to Gaussian sequential
rate-distortion tradeoffs,” IEEE Transactions on Automatic Control, vol. 62, no. 4, pp. 1896–1910, 2017.
[20] P. A. Stavrou, J. Ostergaard, C. D. Charalambous, and M. Derpich, “Zero-delay rate distortion via filtering for unstable
vector Gaussian sources,” arXiv preprint arXiv:1701.06368, 2017.
[21] T. Berger, Rate Distortion Theory, A Mathematical Basis for Data Compression, Prentice Hall, 1971.
[22] S. Tatikonda, “Control under communication constraints,” Ph.D. dissertation, MIT, Cambridge, MA, August 2000.

October 30, 2017

DRAFT

26

[23] H. S. Witsenhausen, “Separation of estimation and control for discrete time systems,” Proceedings of the IEEE, vol. 59,
no. 11, pp. 1557–1566, 1971.
[24] P. Varaiya and J. Walrand, “Causal coding and control for Markov chains,” Systems & Control Letters, vol. 3, no. 4, pp.
189–192, 1983.
[25] R. Bansal and T. Başar, “Simultaneous design of measurement and control strategies for stochastic systems with feedback,”
Automatica, vol. 25, no. 5, pp. 679–694, 1989.
[26] T. Başar and R. Bansal, “Optimum design of measurement channels and control policies for linear-quadratic stochastic
systems,” European journal of Operations Research, vol. 73, no. 2, pp. 226–236, 1994.
[27] V. Borkar, S. Mitter, and S. Tatikonda, “Markov control problems under communication constraints,” Communications in
information and Systems, vol. 1, no. 1, pp. 15–32, 2001.
[28] S. Tatikonda, A. Sahai, and S. Mitter, “Control of LQG systems under communication constraints,” in Proceedings of the
American Control Conference, vol. 4. IEEE, 1999, pp. 2778–2782.
[29] A. S. Matveev and A. V. Savkin, “The problem of LQG optimal control via a limited capacity communication channel,”
Systems & Control Letters, vol. 53, no. 1, pp. 51–64, 2004.
[30] S. Yüksel and T. Başar, “Stochastic networked control systems,” AMC, vol. 10, p. 12, 2013.
[31] T. Tanaka, P. M. Esfahani, and S. K. Mitter, “LQG Control with minimum directed information: semidefinite programming
approach,” to appear in IEEE Transactions on Automatic Control, 2017.
[32] P. W. Cuff, H. H. Permuter, and T. M. Cover, “Coordination capacity,” IEEE Transactions on Information Theory, vol. 56,
no. 9, pp. 4181–4206, 2010.
[33] M. H. Yassaee, A. Gohari, and M. R. Aref, “Channel simulation via interactive communications,” IEEE Transactions on
Information Theory, vol. 61, no. 6, pp. 2964–2982, 2015.
[34] M. Raginsky, “Empirical processes, typical sequences, and coordinated actions in standard Borel spaces,” IEEE Transactions
on Information Theory, vol. 59, no. 3, pp. 1288–1301, 2013.
[35] R. van Handel, “The universal Glivenko–Cantelli property,” Probability Theory and Related Fields, vol. 155, no. 3-4, pp.
911–934, 2013.
[36] D. L. Neuhoff and R. K. Gilbert, “Causal source codes,” IEEE Trans. Inform. Theory, vol. IT-28, no. 5, pp. 701–713,
September 1982.
[37] T. J. Sargent, “Equilibrium with signal extraction from endogenous variables,” Journal of Economic Dynamics and Control,
vol. 15, no. 2, pp. 245–273, 1991.
[38] V. P. Crawford and J. Sobel, “Strategic information transmission,” Econometrica: Journal of the Econometric Society, pp.
1431–1451, 1982.
[39] L. Rayo and I. Segal, “Optimal information disclosure,” Journal of Political Economy, vol. 118, no. 5, pp. 949–987, 2010.
[40] M. Gentzkow and E. Kamenica, “Bayesian persuasion,” American Economic Review, vol. 101, no. 6, pp. 2590–2615, 2011.
[41] E. Akyol, C. Langbort, and T. Basar, “Information-theoretic approach to strategic communication as a hierarchical game,”
Proceedings of the IEEE, Special Issue on Principles and Applications of Science of Information, vol. 105, no. 2, pp. 205–
218, 2017.
[42] C. Preston, “Some notes on standard borel and related spaces,” arXiv preprint arXiv:0809.3066, 2008.
[43] R. M. Gray, Entropy and Information Theory.

Springer Science & Business Media, 2011.

[44] M. S. Pinsker, Information and Information Stability of Random Variables and Processes.
[45] T. M. Cover and J. A. Thomas, Elements of Information Theory.

Holden-Day, 1964.

John Wiley & Sons, 2012.

[46] R. M. Dudley, Real Analysis and Probability. Cambridge University Press, 2002, vol. 74.
[47] R. G. Gallager, Information Theory and Reliable Communication.

October 30, 2017

Springer, 1968, vol. 2.

DRAFT

