Proof of Convergence of the Optimal N-Agent Value to the Optimal Mean-Field Value and Concentration of Asymptotically Optimal Controls

Throughout, $\mathbb{N}$ is the set of natural numbers, and we use freely the elementary order arithmetic of Elementary Order Arithmetic in an Ordered Field and the properties of the absolute value of Properties of the Absolute Value in an Ordered Field.

Step 0. Four elementary devices.

(a) Eventual lower bounds and the limit inferior. Let $(a_{n})_{n\in\mathbb{N}}$ be a bounded sequence of real numbers, let $M$ be a real number, and let $N_{1}\in\mathbb{N}$ be such that $M\le a_{m}$ for every $m\ge N_{1}$. Then $M\le\liminf_{n}a_{n}$.

In the notation of the definition of the limit inferior, write $A_{k}=\{a_{m}:m\in\mathbb{N},\ m\ge k\}$. The number $M$ is a lower bound of $A_{N_{1}}$, so part (ii) of the definition of the greatest lower bound gives $M\le\inf A_{N_{1}}$. The number $\inf A_{N_{1}}$ belongs to the set $\{\inf A_{k}:k\in\mathbb{N}\}$, whose least upper bound is by definition $\liminf_{n}a_{n}$; a least upper bound is in particular an upper bound, so $\inf A_{N_{1}}\le\liminf_{n}a_{n}$. Transitivity of the order gives the assertion.

(b) Removing a doubled epsilon. Let $a$ and $b$ be real numbers such that $a\le b+\varepsilon+\varepsilon$ for every real $\varepsilon>0$. Then $a\le b$.

Suppose not, so 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/2$ is positive and $\delta/2<\delta$; applying that claim to $\delta/2$ shows that $\varepsilon=\delta/4$ is positive and satisfies $\varepsilon+\varepsilon=\delta/2$. The hypothesis applied to this $\varepsilon$ gives $a\le b+\delta/2<b+\delta=a$, which is impossible.

(c) Changing the policy does not change the law of the initial empirical state. Let $N\in\mathbb{N}$ and let two solutions of the controlled $N$-agent dynamics on $[0,T]$ for $\beta$, $\tilde{\beta}$ and the $N$-th driving system be given, for policies in $\mathcal{H}$, with regular events $\Omega_{0}$ and $\Omega_{0}'$ and empirical state measures $\Sigma$ and $\Sigma'$. Then $\Sigma_{0}$ and $\Sigma'_{0}$ agree at every point of an event of probability $1$, and they have the same law as random elements of $(\Delta^{l},d_{\Delta})$.

Write $\varsigma^{1}_{0},\dots,\varsigma^{N}_{0}$ for the initial states of the driving system. Condition 1 of the definition of a solution holds at every point of the regular event, so $\sigma^{i}_{0}(\omega)=\varsigma^{i}_{0}(\omega)$ for every $i$ and every $\omega\in\Omega_{0}$, and the same identity holds for the second solution at every $\omega\in\Omega'_{0}$. The empirical state measure at time $0$ is determined by the states at time $0$ through the formula recalled in that definition, so $\Sigma_{0}(\omega)=\Sigma'_{0}(\omega)$ for every $\omega$ in $E=\Omega_{0}\cap\Omega'_{0}$, and $E\in\mathcal{F}^{N}$ because a $\sigma$-algebra is closed under finite intersections. Since $P^{N}(\Omega_{0})=P^{N}(\Omega'_{0})=1$, claim 3 of the basic properties of a measure gives $P^{N}(\Omega^{N}\setminus\Omega_{0})=P^{N}(\Omega^{N}\setminus\Omega'_{0})=0$. The complement of $E$ is the union of those two sets, so claim 4 there (countable subadditivity), applied to the sequence whose first two terms are those sets and all of whose further terms are empty, gives $P^{N}(\Omega^{N}\setminus E)=0$, and claim 3 again gives $P^{N}(E)=1$.

Let $\Gamma$ be a Borel set of $(\Delta^{l},d_{\Delta})$. Then $\Sigma_{0}^{-1}(\Gamma)\cap E=(\Sigma'_{0})^{-1}(\Gamma)\cap E$. The sets $\Sigma_{0}^{-1}(\Gamma)\cap E$ and $\Sigma_{0}^{-1}(\Gamma)\setminus E$ are disjoint with union $\Sigma_{0}^{-1}(\Gamma)$, so claim 1 of the basic properties (finite additivity) gives $P^{N}(\Sigma_{0}^{-1}(\Gamma))=P^{N}(\Sigma_{0}^{-1}(\Gamma)\cap E)+P^{N}(\Sigma_{0}^{-1}(\Gamma)\setminus E)$, and the last term vanishes by claim 2 (monotonicity) applied to the inclusion $\Sigma_{0}^{-1}(\Gamma)\setminus E\subseteq\Omega^{N}\setminus E$. The same computation applies to $\Sigma'_{0}$, so the two probabilities agree; by the definition of the law, the laws coincide.

Consequently, since $(\Sigma^{N}_{0})_{N\in\mathbb{N}}$ converges in distribution to $Y_{x_{0}}$, and convergence in distribution is by definition weak convergence of the laws, the same convergence holds for the empirical state measures at time $0$ of any family consisting, for each $N$, of a solution for the $N$-th driving system and some policy in $\mathcal{H}$.

(d) Composites of strictly increasing sequences. If $(N_{j})_{j\in\mathbb{N}}$ and $(j_{k})_{k\in\mathbb{N}}$ are strictly increasing sequences of natural numbers, then $k\mapsto N_{j_{k}}$ is strictly increasing: an induction shows that $p<q$ implies $N_{p}<N_{q}$, and $j_{k}<j_{k+1}$ for every $k$.

Step 1. Proof of claim 1. By the preamble, $\mathcal{J}_{N}$ is a nonempty set of real numbers of which $-C(T+1)$ is a lower bound, and $V_{N}=\inf\mathcal{J}_{N}$. Part (ii) of the definition of the greatest lower bound gives $-C(T+1)\le V_{N}$. By part (i) the number $V_{N}$ is a lower bound of $\mathcal{J}_{N}$; since $h^{N}\in\mathcal{H}$ we have $J^{N}[h^{N}]\in\mathcal{J}_{N}$, so $V_{N}\le J^{N}[h^{N}]$. Moreover $|J^{N}[h^{N}]|\le C(T+1)$, so $J^{N}[h^{N}]\le C(T+1)$ by claim 6 of the absolute-value lemma, and $V_{N}\le C(T+1)$ by transitivity. From $-C(T+1)\le V_{N}\le C(T+1)$ and claim 6 again, $|V_{N}|\le C(T+1)$.

Step 2. The open-loop policy is admissible. By claim 1 of the optimal-set structure lemma the set $\mathcal{M}^{*}_{x_{0}}$ is nonempty. Let $\xi^{*}\in\mathcal{M}^{*}_{x_{0}}$ and let $A^{*}$ be an admissible representative of $\xi^{*}$, which exists by claim 2 of the flow stability lemma; thus $A^{*}_{t}\in\mathcal{A}$ for every $t\in[0,T]$, and, being a representative of an element of the Lebesgue space of square-integrable vector-valued functions on $[0,T]$, the map $A^{*}$ has components measurable with respect to the trace Borel $\sigma$-algebra on $[0,T]$ and the Borel $\sigma$-algebra of the real line. Hence the open-loop policy lemma applies, and its claim 1 shows that $h^{A^{*}}$ is an observation-driven control policy with horizon $T$, control dimension $m$ and $\tilde{l}$ channels. By the formulas defining it in that lemma, every value of $h^{A^{*}}$ is of the form $A^{*}_{t}$ with $t\in[0,T]$, hence lies in $\mathcal{A}$; this is exactly the requirement of the definition of an $\mathcal{A}$-valued policy. Therefore $h^{A^{*}}\in\mathcal{H}$, and in particular $J^{N}[h^{A^{*}}]$ is a real number lying in $\mathcal{J}_{N}$ for every $N$.

Step 3. The initial states converge in mean square. For $\omega\in\Omega^{N}$ put $Z_{N}(\omega)=|\Sigma^{N}_{0}(\omega)-x_{0}|^{2}$.

First, $Z_{N}$ is a random variable. Indeed $\Sigma^{N}_{0}$ is a random element of $(\Delta^{l},d_{\Delta})$ by claim 5 of the realized-control lemma; the coordinate projections are Borel measurable by claim 1 of the lemma on Borel measurability in Euclidean space, so each component of $\Sigma^{N}_{0}$ is measurable by claim 4 (composition) of the Borel toolkit on a metric space; and the map sending $x\in\Delta^{l}$ to $|x-x_{0}|^{2}$ is sequentially continuous, so the lemma on sequentially continuous functions of measurable Euclidean maps applies.

Second, $0\le Z_{N}\le4$ everywhere: for every $\omega$ both $\Sigma^{N}_{0}(\omega)$ and $x_{0}$ lie in $\Delta^{l}$, so they have Euclidean norm at most $1$ by claim 1 of the compactness lemma, and claims 5 and 6 of the lemma on the Euclidean norm give $|\Sigma^{N}_{0}(\omega)-x_{0}|\le|\Sigma^{N}_{0}(\omega)|+|x_{0}|\le2$; if $0\le u\le2$ then $u\cdot u\le u\cdot 2\le 2\cdot 2$ by two applications of claim 10 of the order-arithmetic lemma in the nonstrict form obtained by adjoining the case of equality, the multipliers $u$ and $2$ being nonnegative.

Now let $\varepsilon>0$ be real and put $E_{N,\varepsilon}=\{\omega\in\Omega^{N}:\varepsilon\le d_{\Delta}(\Sigma^{N}_{0}(\omega),x_{0})\}$. By claims 2 and 3 of the lemma on convergence in distribution to a constant, each $E_{N,\varepsilon}$ is an event and the sequence $(P^{N}(E_{N,\varepsilon}))_{N\in\mathbb{N}}$ converges to $0$; and $d_{\Delta}(\Sigma^{N}_{0}(\omega),x_{0})=|\Sigma^{N}_{0}(\omega)-x_{0}|$, because $d_{\Delta}$ is the restriction to $\Delta^{l}$ of the Euclidean distance on $\mathbb{R}^{l}$, as fixed in the compactness lemma, and that distance is expressed through the norm by claim 2 of the norm lemma. Let $\mathbf{1}_{E_{N,\varepsilon}}$ be the function equal to $1$ on $E_{N,\varepsilon}$ and to $0$ elsewhere. For $\omega\in E_{N,\varepsilon}$ we get $Z_{N}(\omega)\le4=4\,\mathbf{1}_{E_{N,\varepsilon}}(\omega)\le\varepsilon^{2}+4\,\mathbf{1}_{E_{N,\varepsilon}}(\omega)$; for $\omega\notin E_{N,\varepsilon}$ we get $|\Sigma^{N}_{0}(\omega)-x_{0}|<\varepsilon$ and hence, by the same two applications of claim 10, $Z_{N}(\omega)\le\varepsilon^{2}=\varepsilon^{2}+4\,\mathbf{1}_{E_{N,\varepsilon}}(\omega)$. Thus $Z_{N}\le\varepsilon^{2}+4\,\mathbf{1}_{E_{N,\varepsilon}}$ at every point of $\Omega^{N}$.

Both sides are random variables bounded everywhere, so claim 1 of the lemma on almost sure inequalities between bounded random variables gives $\mathbb{E}^{N}[Z_{N}]\le\mathbb{E}^{N}[\varepsilon^{2}\mathbf{1}_{\Omega^{N}}+4\,\mathbf{1}_{E_{N,\varepsilon}}]$, and claim 2 of the linearity and monotonicity theorem for the integral together with the lemma on the integral of an indicator function gives

$$\mathbb{E}^{N}[Z_{N}]\le\varepsilon^{2}P^{N}(\Omega^{N})+4P^{N}(E_{N,\varepsilon})=\varepsilon^{2}+4P^{N}(E_{N,\varepsilon}).$$

Let $\delta>0$ be real. Choose $\varepsilon$ to be the smaller of $1$ and $\delta/4$, a positive real number; then $\varepsilon^{2}\le\varepsilon\le\delta/4$, the first inequality by claim 10 in the nonstrict form applied to $\varepsilon\le1$ with the nonnegative multiplier $\varepsilon$. Choose $N_{1}$ with $P^{N}(E_{N,\varepsilon})<\delta/16$ for every $N\ge N_{1}$. For such $N$ we get $0\le\mathbb{E}^{N}[Z_{N}]\le\delta/4+\delta/4=\delta/2<\delta$, the lower bound because $0\le Z_{N}$ everywhere. As $\delta>0$ was arbitrary, $(\mathbb{E}^{N}[Z_{N}])_{N\in\mathbb{N}}$ converges to $0$.

Step 4. Proof of claim 2. Retain $\xi^{*}$, $A^{*}$ and $h^{A^{*}}$ from Step 2. By part (ii) of the existence, uniqueness and regularity theorem, for every $N$ the set of solutions of the controlled $N$-agent dynamics on $[0,T]$ for $\beta$, $\tilde{\beta}$, the $N$-th driving system and the policy $h^{A^{*}}$ is nonempty; these sets all lie in the set of all such solutions for all $N$, so Axiom of Countable Choice provides one for every $N$. Write $\Sigma^{A,N}$ for the empirical state measure of the chosen solution. By device (c) the maps $\Sigma^{A,N}_{0}$ and $\Sigma^{N}_{0}$ agree at every point of an event of probability $1$; the map $\Sigma^{A,N}_{0}$ is a random element of $(\Delta^{l},d_{\Delta})$ by claim 5 of the realized-control lemma, so $|\Sigma^{A,N}_{0}-x_{0}|^{2}$ is a random variable by the argument of Step 3, and $|\Sigma^{A,N}_{0}-x_{0}|^{2}$ and $Z_{N}$ agree at every point of that event; both are bounded everywhere, so claim 2 of the almost sure expectation lemma gives $\mathbb{E}^{N}[|\Sigma^{A,N}_{0}-x_{0}|^{2}]=\mathbb{E}^{N}[Z_{N}]$, and by Step 3 this converges to $0$.

By claim 2 of the flow stability lemma the mean-field flow $S(x_{0},\xi^{*})$ is the map furnished by claim 1 of the existence and uniqueness theorem for the generalized mean-field trajectory applied to the initial value $x_{0}$ and the control $A^{*}$; hence $(S(x_{0},\xi^{*}),A^{*})$ is the generalized mean-field trajectory pair with value $x_{0}$ at $t=0$ that appears in the setting of the mean-square tracking proposition. All the data required there are now in place, with $S_{0}=x_{0}$ and with the map $A^{*}$ and the open-loop policy $h^{A^{*}}$ of Step 2. Therefore claim 2 of the corollary on convergence of the $N$-agent cost under an open-loop control applies and shows that $(J^{N}[h^{A^{*}}])_{N\in\mathbb{N}}$ converges to the generalized mean-field cost of that pair. (The cost $J^{N}[h^{A^{*}}]$ has the same value for every solution, as recorded in the definition of the $N$-agent cost, so no ambiguity arises from the choice made above.)

Finally, by the definition of the mean-field cost of a control from an initial state, evaluated with the admissible representative $A^{*}$ of $\xi^{*}$, that generalized mean-field cost is $F(x_{0},\xi^{*})$; and $F(x_{0},\xi^{*})=J^{*}_{x_{0}}$ because $\xi^{*}\in\mathcal{M}^{*}_{x_{0}}$. This proves claim 2.

Step 5. Claim 3: the upper estimate. The sequences $(V_{N})_{N\in\mathbb{N}}$ and $(J^{N}[h^{A^{*}}])_{N\in\mathbb{N}}$ are bounded, both being bounded in absolute value by $C(T+1)$, so that $C(T+1)+1$ is a strictly positive bound as the definition of a bounded sequence requires. For every $N$ the number $J^{N}[h^{A^{*}}]$ lies in $\mathcal{J}_{N}$, of which $V_{N}$ is a lower bound, so $V_{N}\le J^{N}[h^{A^{*}}]$. Claim 2 of the basic properties of the limit inferior and the limit superior therefore gives $\limsup_{N}V_{N}\le\limsup_{N}J^{N}[h^{A^{*}}]$, while claim 5 there, applied to the sequence $(J^{N}[h^{A^{*}}])_{N\in\mathbb{N}}$, which converges to $J^{*}_{x_{0}}$ by claim 2, gives $\limsup_{N}J^{N}[h^{A^{*}}]=J^{*}_{x_{0}}$. Hence $\limsup_{N}V_{N}\le J^{*}_{x_{0}}$.

Step 6. Claim 3: the lower estimate. Let $\varepsilon>0$ be real. Fix $N$. By claim 1 of the order-arithmetic lemma $V_{N}<V_{N}+\varepsilon$, so $V_{N}+\varepsilon$ is not a lower bound of $\mathcal{J}_{N}$: otherwise part (ii) of the definition of the greatest lower bound would give $V_{N}+\varepsilon\le V_{N}$. Hence there is a policy $h\in\mathcal{H}$ with $J^{N}[h]<V_{N}+\varepsilon$, and, by part (ii) of the existence theorem, a solution for the $N$-th driving system and that policy. The set $\mathcal{P}_{N}$ of all pairs consisting of such a policy and such a solution is therefore nonempty, and these sets lie in a common set; so Axiom of Countable Choice provides a pair for every $N$. Write $\tilde{h}^{N}$ for the chosen policy and $\tilde{\Sigma}^{N}$ for the empirical state measure of the chosen solution, so that $J^{N}[\tilde{h}^{N}]<V_{N}+\varepsilon$ for every $N$.

By device (c) the sequence $(\tilde{\Sigma}^{N}_{0})_{N\in\mathbb{N}}$ converges in distribution to $Y_{x_{0}}$. Hence every hypothesis of the asymptotic lower bound theorem is met by the data consisting of the given driving systems, the policies $\tilde{h}^{N}$ and the chosen solutions, and claim 3 there gives that $(J^{N}[\tilde{h}^{N}])_{N\in\mathbb{N}}$ is bounded with

$$J^{*}_{x_{0}}\le\liminf_{N}J^{N}[\tilde{h}^{N}].$$

By claim 3 of the basic properties of the limit inferior and the limit superior there is $N_{1}\in\mathbb{N}$ with $\liminf_{n}J^{n}[\tilde{h}^{n}]-\varepsilon<J^{m}[\tilde{h}^{m}]$ for every $m\ge N_{1}$. For such $m$,

$$J^{*}_{x_{0}}-\varepsilon\le\liminf_{n}J^{n}[\tilde{h}^{n}]-\varepsilon<J^{m}[\tilde{h}^{m}]<V_{m}+\varepsilon ,$$

so $J^{*}_{x_{0}}-\varepsilon<V_{m}+\varepsilon$ and hence, adding $\varepsilon$ to both sides by claim 1 of the order-arithmetic lemma, $J^{*}_{x_{0}}<V_{m}+\varepsilon+\varepsilon$; in particular $J^{*}_{x_{0}}-\varepsilon-\varepsilon\le V_{m}$ for every $m\ge N_{1}$. Device (a), applied to the bounded sequence $(V_{N})_{N\in\mathbb{N}}$, gives $J^{*}_{x_{0}}-\varepsilon-\varepsilon\le\liminf_{N}V_{N}$, that is, $J^{*}_{x_{0}}\le\liminf_{N}V_{N}+\varepsilon+\varepsilon$. Since $\varepsilon>0$ was arbitrary, device (b) gives $J^{*}_{x_{0}}\le\liminf_{N}V_{N}$.

Step 7. Proof of claim 3. By claim 1 of the basic properties of the limit inferior and the limit superior, $\liminf_{N}V_{N}\le\limsup_{N}V_{N}$. With Steps 5 and 6 this yields

$$J^{*}_{x_{0}}\le\liminf_{N}V_{N}\le\limsup_{N}V_{N}\le J^{*}_{x_{0}},$$

so both the limit inferior and the limit superior equal $J^{*}_{x_{0}}$, and claim 5 there shows that $(V_{N})_{N\in\mathbb{N}}$ converges to $J^{*}_{x_{0}}$.

For the second sequence, claim 1 and the hypothesis on $(\eta_{N})_{N\in\mathbb{N}}$ give $0\le J^{N}[h^{N}]-V_{N}\le\eta_{N}$, hence $|J^{N}[h^{N}]-V_{N}|\le\eta_{N}$ by claim 6 of the absolute-value lemma. Claim 5 of that lemma (the triangle inequality) then gives

$$\bigl|J^{N}[h^{N}]-J^{*}_{x_{0}}\bigr|\le\bigl|J^{N}[h^{N}]-V_{N}\bigr|+\bigl|V_{N}-J^{*}_{x_{0}}\bigr|\le\eta_{N}+\bigl|V_{N}-J^{*}_{x_{0}}\bigr| .$$

The sequence $(|V_{N}-J^{*}_{x_{0}}|)_{N\in\mathbb{N}}$ converges to $0$, directly by the definition of the limit applied to $(V_{N})_{N\in\mathbb{N}}$, and $(\eta_{N})_{N\in\mathbb{N}}$ converges to $0$ by hypothesis, so their sum converges to $0$ by claim 1 of the arithmetic of limits of real sequences. Claim 3 of the order properties of limits of real sequences now gives that $(J^{N}[h^{N}])_{N\in\mathbb{N}}$ converges to $J^{*}_{x_{0}}$.

Step 8. Claim 4: measurability. By claim 4 of the optimal-set structure lemma the function $D$ on $X$ is sequentially continuous: if $(y_{j})_{j\in\mathbb{N}}$ is a sequence in $X$ converging to $x$ in $(X,d_{X})$, then $(D(y_{j}))_{j\in\mathbb{N}}$ converges to $D(x)$; by claim 3 of the arithmetic of limits, $(-D(y_{j}))_{j\in\mathbb{N}}$ converges to $-D(x)$. Consequently both $D$ and $-D$ are lower semicontinuous on $X$: given such a sequence and a real $\varepsilon>0$, the definition of the limit provides $N$ with $|D(y_{j})-D(x)|<\varepsilon$ for $j\ge N$, whence $D(x)-\varepsilon<D(y_{j})$ by claim 6 of the absolute-value lemma, and similarly for $-D$; claims 1 and 3 of the sequential characterization of lower semicontinuity, applied with the subset $X$ of $X$, give the assertion.

By claim 5 of the Borel toolkit the function $D$ is measurable with respect to $\mathcal{B}(X)$ and the Borel $\sigma$-algebra of the real line. By claim 5 of the realized-control lemma the pair $(\Sigma^{N}_{0},\hat{\alpha}^{N})$ is a random element of $(X,d_{X})$, that is, measurable with respect to $\mathcal{F}^{N}$ and $\mathcal{B}(X)$. Claim 4 (composition) of the Borel toolkit therefore shows that $D_{N}$ is measurable, that is, a random variable.

Fix a real $\varepsilon>0$ and put $D^{\uparrow}_{\varepsilon}=\{x\in X:\varepsilon\le D(x)\}$. Since $D^{\uparrow}_{\varepsilon}=\{x\in X:-D(x)\le-\varepsilon\}$ and $-D$ is lower semicontinuous on $X$, claim 3 of the lemma on sublevel and superlevel sets, applied with the subset $X$ of $X$, shows that $D^{\uparrow}_{\varepsilon}$ is closed in the topology of open subsets of $(X,d_{X})$; hence $D^{\uparrow}_{\varepsilon}\in\mathcal{B}(X)$ by claim 1 of the Borel toolkit. Moreover $\{\omega\in\Omega^{N}:\varepsilon\le D_{N}(\omega)\}$ is the preimage of $D^{\uparrow}_{\varepsilon}$ under $(\Sigma^{N}_{0},\hat{\alpha}^{N})$, so by the definition of the law

$$a_{N}:=P^{N}\bigl(\{\omega\in\Omega^{N}:\varepsilon\le D_{N}(\omega)\}\bigr)=\mu^{N}(D^{\uparrow}_{\varepsilon}).$$

Step 9. Claim 4: the limit. Suppose, for a contradiction, that $(a_{N})_{N\in\mathbb{N}}$ does not converge to $0$. Since $0\le a_{N}$ for every $N$, negating the definition of the limit provides a real $\varepsilon_{0}>0$ such that for every $K\in\mathbb{N}$ there is $m\ge K$ with $\varepsilon_{0}\le a_{m}$.

Let $S=\{n\in\mathbb{N}:\varepsilon_{0}\le a_{n}\}$, which is nonempty by the case $K=1$, and let $R$ be the set of pairs $(n,n')\in S\times S$ with $n<n'$. For $n\in S$ the case $K=n+1$ provides $n'\in S$ with $n<n'$, so $(n,n')\in R$; thus $R$ is a binary relation on $S$ such that every element of $S$ is related to some element of $S$. Let $s$ be an element of $S$, which exists because $S$ is nonempty. Then Axiom of Dependent Choice, applied to $S$, $R$ and $s$, provides a sequence $(N_{j})_{j\in\mathbb{N}}$ in $S$ with $N_{1}=s$ and $(N_{j},N_{j+1})\in R$, that is $N_{j}<N_{j+1}$, for every $j$. It is strictly increasing and satisfies $\varepsilon_{0}\le a_{N_{j}}$ for every $j$.

By claim 1 of the asymptotic lower bound theorem each $\mu^{N}$ is a Borel measure on $(X,d_{X})$ with $\mu^{N}(X)=1$, and by claim 4 of the compactness lemma $(X,d_{X})$ is compact. Hence the weak sequential compactness theorem applies to $(\mu^{N_{j}})_{j\in\mathbb{N}}$ and provides a strictly increasing sequence $(j_{k})_{k\in\mathbb{N}}$ of natural numbers and a Borel measure $\mu$ on $(X,d_{X})$ with $\mu(X)=1$ such that $(\mu^{N_{j_{k}}})_{k\in\mathbb{N}}$ converges weakly to $\mu$. By device (d) the sequence $(N_{j_{k}})_{k\in\mathbb{N}}$ is strictly increasing.

By claim 3 the sequence $(J^{N}[h^{N}])_{N\in\mathbb{N}}$ converges to $J^{*}_{x_{0}}$, so claim 4 of the asymptotic lower bound theorem applies to the strictly increasing sequence $(N_{j_{k}})_{k\in\mathbb{N}}$ and to $\mu$: the set $\Pi=\{x_{0}\}\times\mathcal{M}^{*}_{x_{0}}$ belongs to $\mathcal{B}(X)$ and $\mu(\Pi)=1$.

The sets $D^{\uparrow}_{\varepsilon}$ and $\Pi$ are disjoint: for $\xi^{*}\in\mathcal{M}^{*}_{x_{0}}$ claim 2 of the optimal-set structure lemma gives $D(x_{0},\xi^{*})=0$, and $\varepsilon\le0$ is false because $\varepsilon>0$. Hence $D^{\uparrow}_{\varepsilon}\subseteq X\setminus\Pi$. Since $\mu(X)=1$ is finite, claim 3 of the basic properties of a measure gives $\mu(X\setminus\Pi)=\mu(X)-\mu(\Pi)=0$, and claim 2 (monotonicity) gives $\mu(D^{\uparrow}_{\varepsilon})\le0$; as a measure takes values in $[0,\infty]$, this forces $\mu(D^{\uparrow}_{\varepsilon})=0$.

The measures $\mu^{N_{j_{k}}}$ and $\mu$ are probability measures on $(X,\mathcal{B}(X))$ and $X$ is nonempty, so claim 4 of the portmanteau theorem, applied to the closed set $D^{\uparrow}_{\varepsilon}$, gives

$$\limsup_{k}\mu^{N_{j_{k}}}(D^{\uparrow}_{\varepsilon})\le\mu(D^{\uparrow}_{\varepsilon})=0 .$$

On the other hand $\varepsilon_{0}\le a_{N_{j_{k}}}=\mu^{N_{j_{k}}}(D^{\uparrow}_{\varepsilon})$ for every $k$, and the sequence $(\mu^{N_{j_{k}}}(D^{\uparrow}_{\varepsilon}))_{k\in\mathbb{N}}$ is bounded, with strictly positive bound $2$, because $0\le\mu^{N}(D^{\uparrow}_{\varepsilon})\le\mu^{N}(X)=1$ by monotonicity. Hence claim 2 of the basic properties of the limit inferior and the limit superior gives $\varepsilon_{0}\le\liminf_{k}\mu^{N_{j_{k}}}(D^{\uparrow}_{\varepsilon})$, and claim 1 there gives $\liminf_{k}\mu^{N_{j_{k}}}(D^{\uparrow}_{\varepsilon})\le\limsup_{k}\mu^{N_{j_{k}}}(D^{\uparrow}_{\varepsilon})$. Combining, $\varepsilon_{0}\le0$, contradicting $\varepsilon_{0}>0$.

Therefore $(a_{N})_{N\in\mathbb{N}}$ converges to $0$, which completes the proof of claim 4 and of the theorem.