Proof of Asymptotic Lower Bound for the N-Agent Cost and Concentration of the Limit Laws on the Optimal Mean-Field Controls

Throughout, an inequality $a\le b$ between real numbers means that $a<b$ or $a=b$, and we use the order arithmetic of Elementary Order Arithmetic in an Ordered Field both in the strict form stated there and in the nonstrict form obtained by adjoining the case of equality. Absolute values are those of Properties of the Absolute Value in an Ordered Field; we use its claim 6, by which $|a|\le c$ holds if and only if $-c\le a$ and $a\le c$.

Step 0. Two elementary devices.

(E) Let $(a_{n})_{n\in\mathbb{N}}$ be a bounded sequence of real numbers, let $M$ be a real number, and suppose there is a natural number $N_{1}$ with $a_{n}\le M$ for every $n\ge N_{1}$. Then $\liminf_{n}a_{n}\le M$. Indeed, let $\delta>0$ be real. By claim 3 of the basic properties of the limit inferior and limit superior there is a natural number $N_{2}$ such that $\liminf_{n}a_{n}-\delta<a_{p}$ for every $p\ge N_{2}$. Choosing $p$ at least $N_{1}$ and at least $N_{2}$ gives $\liminf_{n}a_{n}-\delta<a_{p}\le M$, hence $\liminf_{n}a_{n}<M+\delta$. If $M<\liminf_{n}a_{n}$, then taking $\delta=\liminf_{n}a_{n}-M$, which is positive, yields $\liminf_{n}a_{n}<\liminf_{n}a_{n}$, a contradiction. Hence $\liminf_{n}a_{n}\le M$.

(F) If $(N_{j})_{j\in\mathbb{N}}$ is a strictly increasing sequence of natural numbers, then $j\le N_{j}$ for every $j\in\mathbb{N}$. This follows by induction: $1\le N_{1}$ because $1$ is the least natural number, and if $j\le N_{j}$ then $j+1\le N_{j}+1\le N_{j+1}$.

(G) Let $a$ and $b$ be real numbers and suppose that $a\le b+\varepsilon+\varepsilon$ for every real $\varepsilon>0$. Then $a\le b$. Suppose instead that $b<a$, and put $\delta=a-b$, a positive real number. By claim 8 of Elementary Order Arithmetic in an Ordered Field the number $\delta_{1}=\delta\cdot 2^{-1}$ satisfies $0<\delta_{1}$, $\delta_{1}<\delta$ and $\delta_{1}+\delta_{1}=\delta$. Applying that claim again, now to $\delta_{1}$, the number $\varepsilon=\delta_{1}\cdot 2^{-1}$ satisfies $0<\varepsilon$ and $\varepsilon+\varepsilon=\delta_{1}$. For this $\varepsilon$ the hypothesis gives

a contradiction. Hence $a\le b$. Below we write $2\varepsilon$ for $\varepsilon+\varepsilon$.

We also record, for later use, that $-C_{F}\le J^{*}_{\sigma}\le C_{F}$. Indeed, by claim 1 of the attainment theorem we have $|F(\sigma,\xi)|\le C_{F}$, hence $-C_{F}\le F(\sigma,\xi)\le C_{F}$, for every $\xi\in\mathcal{U}_{\mathcal{A}}$. Thus $-C_{F}$ is a lower bound of the set $V_{\sigma}=\{F(\sigma,\xi):\xi\in\mathcal{U}_{\mathcal{A}}\}$ whose infimum is $J^{*}_{\sigma}$, the infimum existing by the derivation recorded in the definition of the optimal mean-field value. By part (ii) of the definition of an infimum, which makes it a greatest lower bound, we get $-C_{F}\le J^{*}_{\sigma}$; and by part (i), which makes it a lower bound of $V_{\sigma}$, we get $J^{*}_{\sigma}\le F(\sigma,\xi)$ for every $\xi\in\mathcal{U}_{\mathcal{A}}$. As $\mathcal{U}_{\mathcal{A}}$ is nonempty, choosing any $\xi_{0}\in\mathcal{U}_{\mathcal{A}}$ gives $J^{*}_{\sigma}\le F(\sigma,\xi_{0})\le C_{F}$. In particular $J^{*}_{\sigma}\le F(\sigma,\xi)$ for every $\xi\in\mathcal{U}_{\mathcal{A}}$, that is,

Step 1. Proof of claim 1.

Fix a natural number $N$. By claim 5 of the realized-control lemma the map $\omega\mapsto(\Sigma^{N}_{0}(\omega),\hat{\alpha}^{N}(\omega))$ is a random element of $(X,d_{X})$, so its law $\mu^{N}$ is the image measure of $P^{N}$ under that map. By claim 1 of that lemma $\mu^{N}$ is a measure on $(X,\mathcal{B}(X))$ with $\mu^{N}(X)=P^{N}(\Omega^{N})=1$; being a measure on the Borel $\sigma$-algebra of $(X,d_{X})$, it is a Borel measure, and it is finite.

By claim 3 of the attainment theorem the function $F$ is lower semicontinuous on $X$, hence measurable with respect to $\mathcal{B}(X)$ and the Borel $\sigma$-algebra of the real line by claim 5 of the Borel measurability toolkit. By claim 1 of the attainment theorem $|F(x)|\le C_{F}$ for every $x\in X$, so $F$ is integrable with respect to $\mu^{N}$ by claim 6(b) of that toolkit, applied with $M=C_{F}$.

By claim 2 of the comparison lemma the cost $J^{N}[h^{N}]$ is a real number and $J^{N}[h^{N}]=\mathbb{E}^{N}[W^{N}]$, where $W^{N}$ is a random variable with $|W^{N}(\omega)|\le C(T+1)$ for every $\omega\in\Omega^{N}$. Applying claim 3 of the lemma on almost sure inequalities between bounded random variables with $W^{N}$ in both random-variable slots of that lemma, with $K=c=C(T+1)$, and with the event $\Omega^{N}$ itself, which has probability $1$, gives $|J^{N}[h^{N}]|\le C(T+1)$.

By claim 2 of the comparison lemma the map $\omega\mapsto F(\Sigma^{N}_{0}(\omega),\hat{\alpha}^{N}(\omega))$ is a random variable; it is the composition of $F$ with the random element $(\Sigma^{N}_{0},\hat{\alpha}^{N})$. Since $F$ is integrable with respect to $\mu^{N}$, claim 2 of the change-of-variables lemma, applied with that random element as the measurable map and with $F$ as the integrand, gives

the last equality being the definition of the expectation. This proves claim 1.

Step 2. The sets $U_{\varepsilon}$ are open, and $A$ is Borel.

For a real number $\varepsilon>0$ put

We check that $U_{\varepsilon}$ is open in $(X,d_{X})$. Let $(x_{0},\xi)\in U_{\varepsilon}$ and put $r=d_{\Delta}(x_{0},\sigma)-\varepsilon$, a positive real number. Let $(y_{0},\eta)\in X$ satisfy $d_{X}((x_{0},\xi),(y_{0},\eta))<r$. Since $d_{X}$ is the product metric, which is the larger of the two coordinate distances, we get $d_{\Delta}(x_{0},y_{0})<r$. By the triangle inequality for the metric $d_{\Delta}$ we have $d_{\Delta}(x_{0},\sigma)\le d_{\Delta}(x_{0},y_{0})+d_{\Delta}(y_{0},\sigma)$, whence

Thus the open ball of radius $r$ about $(x_{0},\xi)$ is contained in $U_{\varepsilon}$, so $U_{\varepsilon}$ is open, and therefore $U_{\varepsilon}\in\mathcal{B}(X)$ by claim 1 of the Borel measurability toolkit.

Next, $A=X\setminus\bigcup_{k\in\mathbb{N}}U_{1/k}$. Indeed, a point $(x_{0},\xi)\in X$ lies outside every $U_{1/k}$ precisely when $d_{\Delta}(x_{0},\sigma)\le 1/k$ for every natural number $k$. If $d_{\Delta}(x_{0},\sigma)>0$, then by claim 3 of The Archimedean Property of the Real Numbers there is a natural number $k$ with $1/k<d_{\Delta}(x_{0},\sigma)$, contradicting that bound; so the condition holds precisely when $d_{\Delta}(x_{0},\sigma)=0$, that is, by the metric axioms, precisely when $x_{0}=\sigma$. Since a $\sigma$-algebra is closed under countable unions and complements, $A\in\mathcal{B}(X)$.

Step 3. The masses $\mu^{N}(U_{\varepsilon})$ tend to zero.

Fix a real $\varepsilon>0$ and a natural number $N$. Writing $\Lambda^{N}=(\Sigma^{N}_{0},\hat{\alpha}^{N})$ for the random element of Step 1, we have by the definition of the law

and this set lies in $\mathcal{F}^{N}$ because $\Lambda^{N}$ is measurable and $U_{\varepsilon}\in\mathcal{B}(X)$. Let

which lies in $\mathcal{F}^{N}$ by claim 2 of the lemma on convergence in distribution to a constant, applied to the random elements $\Sigma^{N}_{0}$ of $(\Delta^{l},d_{\Delta})$ and to the point $\sigma$. Since $(\Lambda^{N})^{-1}(U_{\varepsilon})\subseteq E_{N,\varepsilon}$, monotonicity of $P^{N}$, which is claim 2 of the basic properties of a measure, gives

By hypothesis $(\Sigma^{N}_{0})_{N\in\mathbb{N}}$ converges in distribution to the constant random element $Y_{\sigma}$, so claim 3 of that lemma shows that $(P^{N}(E_{N,\varepsilon}))_{N\in\mathbb{N}}$ converges to $0$. By claim 3 of the order properties of limits, the sequence $(\mu^{N}(U_{\varepsilon}))_{N\in\mathbb{N}}$ therefore converges to $0$ as well.

Step 4. Proof of claim 2.

That $A\in\mathcal{B}(X)$ was shown in Step 2. By claim 4 of the compactness lemma the metric space $(X,d_{X})$ is compact, and by claim 1 each $\mu^{N}$ is a Borel measure on it with $\mu^{N}(X)=1$. Hence the weak sequential compactness theorem for Borel measures of total mass one on a compact metric space provides a strictly increasing sequence $(N_{j})_{j\in\mathbb{N}}$ of natural numbers and a Borel measure $\mu$ on $(X,d_{X})$ with $\mu(X)=1$ such that $(\mu^{N_{j}})_{j\in\mathbb{N}}$ converges weakly to $\mu$. This proves the existence assertion.

Now let $(N_{j})_{j\in\mathbb{N}}$ be any strictly increasing sequence of natural numbers and let $\mu$ be a Borel measure on $(X,d_{X})$ with $\mu(X)=1$ such that $(\mu^{N_{j}})_{j\in\mathbb{N}}$ converges weakly to $\mu$. Fix a natural number $k$; we show $\mu(U_{1/k})=0$.

Since $X$ is nonempty and $U_{1/k}$ is open, claim 3 of the portmanteau theorem gives

the sequence on the right being bounded because each of its terms lies between $0$ and $1$. Let $\delta>0$ be real. By Step 3 there is a natural number $N_{1}$ with $\mu^{N}(U_{1/k})\le\delta$ for every $N\ge N_{1}$; by device (F) we have $j\le N_{j}$, so $\mu^{N_{j}}(U_{1/k})\le\delta$ for every $j\ge N_{1}$. Device (E) now gives $\liminf_{j}\mu^{N_{j}}(U_{1/k})\le\delta$, hence $\mu(U_{1/k})\le\delta$. As $\delta>0$ was arbitrary and $0\le\mu(U_{1/k})$, we conclude $\mu(U_{1/k})=0$.

By Step 2 we have $X\setminus A=\bigcup_{k\in\mathbb{N}}U_{1/k}$, so countable subadditivity, claim 4 of the basic properties of a measure, gives $\mu(X\setminus A)\le\sum_{k\in\mathbb{N}}\mu(U_{1/k})=0$. Since $\mu$ is finite, claim 3 of that lemma yields $\mu(A)=\mu(X)-\mu(X\setminus A)=1$. This proves claim 2.

Step 5. A comparison valid for all large $N$.

Let $\varepsilon>0$ be real. By claim 3 of the comparison lemma there is a natural number $N_{0}$, depending only on $l$, $B$, $T$, $\Lambda_{b}$, $\mathcal{A}$, $L$ and $G$, such that

for every $N\ge N_{0}$; the hypotheses of that claim are met because each $h^{N}$ is an $\mathcal{A}$-valued observation-driven control policy with horizon $T$, control dimension $m$ and $\tilde{l}$ channels, and each of our solutions is a solution for the corresponding data. Combining this with claim 1 and with the two-sided bound of claim 6 of Properties of the Absolute Value in an Ordered Field, we obtain

Step 6. A lower bound for the integral against any limit law.

Let $\mu$ be a Borel measure on $(X,d_{X})$ with $\mu(X)=1$ and $\mu(A)=1$. We claim that

Regard $(X,\mathcal{B}(X),\mu)$ as a probability space. The constant function on $X$ with value $J^{*}_{\sigma}$ and the function $F$ are both measurable, and both are bounded in absolute value by $C_{F}$ everywhere on $X$, by claim 1 of the attainment theorem and by Step 0. By $(\ast)$ the first is at most the second at every point of $A$, and $\mu(A)=1$. Hence claim 1 of the lemma on almost sure inequalities between bounded random variables, applied on this probability space with the event $A$, gives $\int_{X}J^{*}_{\sigma}\,d\mu\le\int_{X}F\,d\mu$. By claim 6(a) of the Borel measurability toolkit the left-hand side equals $J^{*}_{\sigma}\mu(X)=J^{*}_{\sigma}$, which is $(\ddagger)$.

Step 7. Proof of claim 3.

By claim 1 we have $|J^{N}[h^{N}]|\le C(T+1)$ for every $N$. A bound in the sense of the definition of a bounded real sequence is required to be positive, whereas $C(T+1)$ is only known to be nonnegative; we therefore use $C(T+1)+1$, which is positive and satisfies $|J^{N}[h^{N}]|\le C(T+1)<C(T+1)+1$. Thus $(J^{N}[h^{N}])_{N\in\mathbb{N}}$ is bounded and its limit inferior $\ell=\liminf_{N}J^{N}[h^{N}]$ is defined.

Let $\varepsilon>0$ be real, and let $N_{0}$ be as in Step 5 for this $\varepsilon$. By claim 4 of the basic properties of the limit inferior and limit superior there are natural numbers $n_{1}<n_{2}<n_{3}<\dots$ with

By claim 1 each $\mu^{n_{i}}$ is a Borel measure on the compact metric space $(X,d_{X})$ with total mass $1$, so the weak sequential compactness theorem provides a strictly increasing sequence $(i_{p})_{p\in\mathbb{N}}$ of natural numbers and a Borel measure $\mu$ on $(X,d_{X})$ with $\mu(X)=1$ such that $(\mu^{n_{i_{p}}})_{p\in\mathbb{N}}$ converges weakly to $\mu$. The sequence $p\mapsto n_{i_{p}}$ is strictly increasing, being a composition of strictly increasing sequences of natural numbers, so claim 2 applies and gives $\mu(A)=1$.

The function $F$ is bounded in absolute value by $C_{F}$ and lower semicontinuous on $X$, so claim 2 of the portmanteau theorem gives that $(\int_{X}F\,d\mu^{n_{i_{p}}})_{p\in\mathbb{N}}$ is bounded and

By device (F) applied twice we have $p\le i_{p}\le n_{i_{p}}$, so for every $p\ge N_{0}$ the index $n_{i_{p}}$ is at least $N_{0}$, and $(\dagger)$ together with the choice of the $n_{i}$ gives

Device (E) therefore gives $\liminf_{p}\int_{X}F\,d\mu^{n_{i_{p}}}\le\ell+2\varepsilon$, whence $\int_{X}F\,d\mu\le\ell+2\varepsilon$. Combining with $(\ddagger)$ of Step 6, which applies because $\mu(A)=1$, we obtain $J^{*}_{\sigma}\le\ell+2\varepsilon$.

This holds for every real $\varepsilon>0$, so device (G), applied with $a=J^{*}_{\sigma}$ and $b=\ell$, gives $J^{*}_{\sigma}\le\ell$. This is claim 3.

Step 8. Proof of claim 4.

Assume now that $(J^{N}[h^{N}])_{N\in\mathbb{N}}$ converges to $J^{*}_{\sigma}$, let $(N_{j})_{j\in\mathbb{N}}$ be a strictly increasing sequence of natural numbers, and let $\mu$ be a Borel measure on $(X,d_{X})$ with $\mu(X)=1$ such that $(\mu^{N_{j}})_{j\in\mathbb{N}}$ converges weakly to $\mu$. By claim 2 we have $\mu(A)=1$.

(a) The integral of $F$ against $\mu$ is at most $J^{*}_{\sigma}$. Let $\varepsilon>0$ be real and let $N_{0}$ be as in Step 5. Since $(J^{N}[h^{N}])_{N\in\mathbb{N}}$ converges to $J^{*}_{\sigma}$, there is a natural number $N_{1}$ with $J^{N}[h^{N}]<J^{*}_{\sigma}+\varepsilon$ for every $N\ge N_{1}$. Hence, by $(\dagger)$, for every $N$ at least $N_{0}$ and at least $N_{1}$ we have $\int_{X}F\,d\mu^{N}<J^{*}_{\sigma}+2\varepsilon$. By device (F), $j\le N_{j}$, so the same bound holds for $\int_{X}F\,d\mu^{N_{j}}$ for all sufficiently large $j$. Claim 2 of the portmanteau theorem, applicable because $F$ is bounded and lower semicontinuous, together with device (E), gives

As this holds for every real $\varepsilon>0$, device (G), applied with $a=\int_{X}F\,d\mu$ and $b=J^{*}_{\sigma}$, yields $\int_{X}F\,d\mu\le J^{*}_{\sigma}$.

(b) The exceptional sets are null. Fix a natural number $k$ and put

The set $[J^{*}_{\sigma}+1/k,\infty)$ is a closed subset of the real line and hence lies in its Borel $\sigma$-algebra by claims 4 and 5 of the lemma on Borel measurability in Euclidean space; since $F$ is measurable by claim 1, its preimage under $F$ lies in $\mathcal{B}(X)$. As $A\in\mathcal{B}(X)$ by Step 2 and a $\sigma$-algebra is closed under finite intersections, $E_{k}\in\mathcal{B}(X)$.

Let $\mathbf{1}_{E_{k}}$ be the indicator function of $E_{k}$, which is measurable by the lemma identifying the integral of an indicator function with the measure of the set, and define $u:X\to\mathbb{R}$ by $u(x)=J^{*}_{\sigma}+(1/k)\mathbf{1}_{E_{k}}(x)$. The map sending a real $s$ to $J^{*}_{\sigma}+(1/k)s$ is continuous, so $u$ is measurable by the lemma on compositions of a continuous map with a measurable map, and $|u(x)|\le|J^{*}_{\sigma}|+1/k$ for every $x$.

We have $u(x)\le F(x)$ for every $x\in A$: if $x\in E_{k}$ this is the defining inequality of $E_{k}$, and if $x\in A\setminus E_{k}$ then $u(x)=J^{*}_{\sigma}\le F(x)$ by $(\ast)$. Since $\mu(A)=1$ and both $u$ and $F$ are bounded everywhere, claim 1 of the lemma on almost sure inequalities between bounded random variables, applied on the probability space $(X,\mathcal{B}(X),\mu)$ with the event $A$, gives $\int_{X}u\,d\mu\le\int_{X}F\,d\mu$, hence $\int_{X}u\,d\mu\le J^{*}_{\sigma}$ by part (a).

On the other hand $\mathbf{1}_{E_{k}}$ is nonnegative, bounded by $1$ and measurable, so it is integrable with respect to $\mu$ by claim 6(b) of the Borel measurability toolkit, and by claim 6(c) of that toolkit its integral coincides with its integral as a nonnegative measurable function, which equals $\mu(E_{k})$ by the indicator lemma. Using linearity of the integral, Linearity and Monotonicity of the Lebesgue Integral, and claim 6(a) of the toolkit for the constant term, we get

Combining the two displays gives $(1/k)\mu(E_{k})\le0$. Now $\mu(E_{k})\ge0$, since $\mu$ takes values in $[0,\infty]$ and is finite. If $\mu(E_{k})>0$, then, $1/k$ being positive, claim 5 of Elementary Order Arithmetic in an Ordered Field would give $(1/k)\mu(E_{k})>0$, contradicting the previous inequality. Hence $\mu(E_{k})=0$.

(c) Identification of the remaining set. We show that

Let $x=(\sigma,\xi)$ with $\xi\in\mathcal{U}_{\mathcal{A}}$, so that $x\in A$. Then $x$ lies outside every $E_{k}$ precisely when $F(\sigma,\xi)<J^{*}_{\sigma}+1/k$ for every natural number $k$. If $J^{*}_{\sigma}<F(\sigma,\xi)$, then by claim 3 of The Archimedean Property of the Real Numbers there is a natural number $k$ with $1/k<F(\sigma,\xi)-J^{*}_{\sigma}$, that is, $J^{*}_{\sigma}+1/k<F(\sigma,\xi)$, so $x\in E_{k}$. Conversely, if $F(\sigma,\xi)\le J^{*}_{\sigma}$ then $F(\sigma,\xi)<J^{*}_{\sigma}+1/k$ for every $k$. Hence $x$ lies outside every $E_{k}$ precisely when $F(\sigma,\xi)\le J^{*}_{\sigma}$, which by $(\ast)$ holds precisely when $F(\sigma,\xi)=J^{*}_{\sigma}$, that is, precisely when $\xi\in\mathcal{M}^{*}_{\sigma}$. This proves the displayed identity, and it exhibits $\{\sigma\}\times\mathcal{M}^{*}_{\sigma}$ as the difference of $A\in\mathcal{B}(X)$ and a countable union of members of $\mathcal{B}(X)$, so $\{\sigma\}\times\mathcal{M}^{*}_{\sigma}\in\mathcal{B}(X)$.

Finally, by countable subadditivity, claim 4 of the basic properties of a measure, and by part (b),

Since every $E_{k}$ is contained in $A$ and $\mu$ is finite, claim 3 of that lemma gives

This proves claim 4, and with it the theorem.