Proof of Asymptotic Lower Bound for the Recentred N-Agent Cost by the Fluctuation LQG Value, under Injection Certificates

Claim 1.

The initial covariance. By hypothesis (I) the matrix $\Pi_{0}$ is symmetric. Suppose it were not positive semidefinite, so that $x\cdot(\Pi_{0}x)=-2\eta_{0}<0$ for some $x\in\mathbb{R}^{l}$. Put $\zeta=\eta_{0}/\bigl(1+\sum_{\gamma,\delta}|x^{\gamma}x^{\delta}|\bigr)>0$. By hypothesis (I) and the definition of the limit of a real sequence, applied to each of the finitely many sequences $\bigl(\mathbb{E}[\mathfrak{s}^{\gamma}_{0}\mathfrak{s}^{\delta}_{0}]\bigr)_{N\ge1}$, there is $N'$ such that $\bigl|\mathbb{E}[\mathfrak{s}^{\gamma}_{0}\mathfrak{s}^{\delta}_{0}]-\Pi^{\gamma\delta}_{0}\bigr|\le\zeta$ for all $\gamma,\delta$ and all $N\ge N'$. For such $N$, by the linearity of the integral,

$$\mathbb{E}\bigl[(x\cdot\mathfrak{s}_{0})^{2}\bigr]=\sum_{\gamma,\delta}x^{\gamma}x^{\delta}\,\mathbb{E}[\mathfrak{s}^{\gamma}_{0}\mathfrak{s}^{\delta}_{0}]\ \le\ \sum_{\gamma,\delta}x^{\gamma}x^{\delta}\,\Pi^{\gamma\delta}_{0}+\zeta\sum_{\gamma,\delta}|x^{\gamma}x^{\delta}|\ \le\ -2\eta_{0}+\eta_{0}<0,$$

contradicting the nonnegativity of the expectation of the nonnegative random variable $(x\cdot\mathfrak{s}_{0})^{2}$. Hence $\Pi_{0}$ is positive semidefinite.

The coefficient families. Every entry of $t\mapsto E_{t}=\mathcal{E}_{t}$ is continuous on $[0,T]$ by conclusion (a) of the completion-of-squares theorem. Every entry of $t\mapsto\Theta^{\star}_{t}$ is continuous by clause (c) of the covariance deviation lemma, and every $\Theta^{\star}_{t}$ is positive semidefinite, hence symmetric, by claim 3 of the covariance positivity lemma.

Under (OC) each $\tilde{\Theta}^{\star}_{t}$ is the diagonal matrix with diagonal entries $\tilde{b}^{\upsilon}(S_{t})\ge\tilde{\beta}_{\min}>0$; the diagonal matrix with diagonal entries $1/\tilde{b}^{\upsilon}(S_{t})$ is its inverse, as the index formula for the matrix product shows, and its entries are continuous in $t$ by the continuity of the reciprocal of a nonvanishing continuous function. Consequently

$$\tilde{D}^{\gamma\delta}_{t}=\sum_{\upsilon=1}^{\tilde{l}}\frac{\tilde{\mathcal{E}}^{\upsilon\gamma}_{t}\,\tilde{\mathcal{E}}^{\upsilon\delta}_{t}}{\tilde{b}^{\upsilon}(S_{t})},$$

which is symmetric in $(\gamma,\delta)$ and continuous in $t$ by the continuity of sums and products; and for $x\in\mathbb{R}^{l}$,

$$x\cdot(\tilde{D}_{t}x)=\sum_{\upsilon=1}^{\tilde{l}}\frac{\bigl((\tilde{\mathcal{E}}_{t}x)^{\upsilon}\bigr)^{2}}{\tilde{b}^{\upsilon}(S_{t})}\ \ge\ 0,$$

so every $\tilde{D}_{t}$ is positive semidefinite. The Riccati existence theorem therefore applies on $[0,T]$ with $k$ there equal to $l$, $A=\mathcal{E}$, $C=\Theta^{\star}$, $D=\tilde{D}$ and $P_{0}=\Pi_{0}$, and yields the unique $\Pi$ with continuous entries, every $\Pi_{t}$ being symmetric and satisfying $0\preceq\Pi_{t}$, that is, positive semidefinite.

The weight $\Xi$. Every $\Xi_{t}$ is symmetric positive semidefinite with continuous entries by claim 2 of the cascade filtering lemma. Fix $t$. Under (H1), conclusion (a) of the completion-of-squares theorem gives that $R_{t}$ is symmetric positive definite, so $R_{t}^{-1}$ is symmetric positive definite by Invertibility of Symmetric Positive Definite Matrices, and by the Cholesky factorisation there is a real matrix $L_{t}$ with $m$ rows and $m$ columns and $R_{t}^{-1}=L_{t}L_{t}^{\top}$. Put $B_{t}=W_{t}L_{t}$, a real matrix with $l$ rows and $m$ columns, and let $b_{t,1},\dots,b_{t,m}\in\mathbb{R}^{l}$ be its columns, so that $(B_{t})_{\gamma j}=b^{\gamma}_{t,j}$. Then

$$\Xi_{t}=W_{t}L_{t}L_{t}^{\top}W_{t}^{\top}=B_{t}B_{t}^{\top},\qquad\text{that is}\qquad\Xi^{\gamma\delta}_{t}=\sum_{j=1}^{m}b^{\gamma}_{t,j}b^{\delta}_{t,j},$$

by the index formula for the matrix product and the transpose. Hence, for every real matrix $\mathcal{M}$ with $l$ rows and $l$ columns,

$$\sum_{\gamma=1}^{l}\sum_{\delta=1}^{l}\Xi^{\gamma\delta}_{t}\,\mathcal{M}^{\gamma\delta}=\sum_{j=1}^{m}\sum_{\gamma,\delta}b^{\gamma}_{t,j}b^{\delta}_{t,j}\mathcal{M}^{\gamma\delta}=\sum_{j=1}^{m}b_{t,j}\cdot\bigl(\mathcal{M}\,b_{t,j}\bigr),$$

called the column identity below. Taking $\mathcal{M}=\Pi_{t}$ shows $\sum_{\gamma,\delta}\Xi^{\gamma\delta}_{t}\Pi^{\gamma\delta}_{t}\ge0$, every $\Pi_{t}$ being positive semidefinite. That function of $t$ is a finite sum of products of continuous functions, hence continuous, and therefore Lebesgue integrable on $[0,T]$ by claim 3 of Restricted Lebesgue Measure and Integral Toolkit on a Compact Interval. This proves claim 1.

Claim 2. Fix $\pi$, $k$, $s\in[t_{k},t_{k+1}]$, $c$ and $\eta>0$, and put $\kappa=c\cdot(\Pi_{s}c)$, a nonnegative real by claim 1.

Apply Adjoint Energy Identity for the Kalman Covariance Riccati Equation with $a=0$, $b=T$, $k$ there equal to $l$, the data $\mathcal{E}$, $\Theta^{\star}$, $\tilde{D}$, $\Pi_{0}$ and $\Pi$ of claim 1, the time $s$ and the vector $x=c$. It produces an assignment $\lambda$ with continuous components and $\lambda(s)=c$, and by its claim 2 the assignment $u\mapsto\Pi_{u}\lambda(u)$ has continuous components and satisfies the integral equation defining $\psi_{\lambda}$; by the uniqueness in claim 3 of the variation of constants theorem, $\psi_{\lambda}(u)=\Pi_{u}\lambda(u)$ for every $u$. Its claim 3 then gives

$$c\cdot\psi_{\lambda}(s)=c\cdot(\Pi_{s}c)=\kappa\qquad\text{and}\qquad\mathcal{A}_{s}(\lambda)=\kappa,$$

the second because the energy displayed there is exactly $\mathcal{A}_{s}(\lambda)$ once $\psi_{\lambda}=\Pi\lambda$ is substituted.

Suppose first $\kappa=0$. Apply (VT) with this $\lambda$ and with $\epsilon=1$, obtaining $N_{2}$; for $N\ge N_{2}$ the data of (VT) exist, and taking $\varkappa=0$, which satisfies (C4) because $(\alpha\cdot z)^{2}\ge0=0\cdot\bigl(z\cdot(\mathcal{I}z)\bigr)$, they form a van Trees certificate; claim 1 of Localized Filtering Lower Bound from a Mixture-Weight van Trees Certificate is therefore available (only the presence of a certificate is used here, not its tolerance or its value) and gives

$$\mathbb{E}\Bigl[\mathbf{1}_{\mathcal{T}^{\mathrm{nr}}_{k}(s)}\sum_{\gamma,\delta}c^{\gamma}c^{\delta}\varepsilon^{\gamma}_{s}\varepsilon^{\delta}_{s}\Bigr]=\mathbb{E}\bigl[\mathbf{1}_{\mathcal{T}^{\mathrm{nr}}_{k}(s)}(c\cdot\varepsilon_{s})^{2}\bigr]\ \ge\ 0=\kappa\ \ge\ \kappa-\eta,$$

the inequality being the nonnegativity of the expectation of a nonnegative random variable. Take $N_{3}=N_{2}$.

Suppose now $\kappa>0$, and put

$$\epsilon=\min\Bigl\{\frac{\kappa}{8},\ \frac{\sqrt{\kappa}}{2},\ \frac{\eta}{3+2\sqrt{\kappa}}\Bigr\}>0,\qquad \varkappa=\frac{(\kappa-\epsilon)^{2}}{\kappa+\epsilon},$$

with $\sqrt{\cdot}$ the nonnegative square root. Apply (VT) with this $\lambda$ and this $\epsilon$, obtaining $N_{2}$, and let $N\ge N_{3}=N_{2}$ and let $d$, $(\mathsf{Y},\mathcal{Y})$, $\varrho_{0}$, $\mathsf{D}$, $\Theta$, $\alpha$, $z$ be a certificate. Then

$$\alpha\cdot z\ \ge\ \kappa-\epsilon\ >\ 0,\qquad z\cdot(\mathcal{I}z)\ \le\ \kappa+\epsilon,$$

so $(\alpha\cdot z)^{2}\ge(\kappa-\epsilon)^{2}=\varkappa\,(\kappa+\epsilon)\ge\varkappa\,\bigl(z\cdot(\mathcal{I}z)\bigr)$, which is condition (C4) with this $\varkappa$; here $\varkappa\ge0$ and $z\cdot(\mathcal{I}z)>0$ by claim 1 of Rank-One Lower Bound for the Inverse of a Positive Definite Matrix.

Three elementary estimates follow from $0<\epsilon\le\kappa/8$ and $\epsilon\le\sqrt{\kappa}/2$. First, $(\kappa-3\epsilon)(\kappa+\epsilon)=\kappa^{2}-2\kappa\epsilon-3\epsilon^{2}\le\kappa^{2}-2\kappa\epsilon+\epsilon^{2}=(\kappa-\epsilon)^{2}$, so $\varkappa\ge\kappa-3\epsilon$. Second, $\epsilon\le3\kappa$ gives $\epsilon^{2}\le3\kappa\epsilon$, hence $(\kappa-\epsilon)^{2}=\kappa^{2}-2\kappa\epsilon+\epsilon^{2}\le\kappa^{2}+\kappa\epsilon=\kappa(\kappa+\epsilon)$ and therefore $\varkappa\le\kappa$ and $\sqrt{\varkappa}\le\sqrt{\kappa}$. Third, $\varkappa\ge\kappa-3\epsilon\ge\kappa-3\kappa/8\ge\kappa/4\ge\epsilon^{2}$, so $\sqrt{\varkappa}\ge\epsilon$.

Claim 2 of Localized Filtering Lower Bound from a Mixture-Weight van Trees Certificate is therefore available and gives, together with its claim 1,

$$\mathbb{E}\Bigl[\mathbf{1}_{\mathcal{T}^{\mathrm{nr}}_{k}(s)}\sum_{\gamma,\delta}c^{\gamma}c^{\delta}\varepsilon^{\gamma}_{s}\varepsilon^{\delta}_{s}\Bigr]\ \ge\ \bigl(\sqrt{\varkappa}-\epsilon\bigr)^{2}=\varkappa-2\epsilon\sqrt{\varkappa}+\epsilon^{2}\ \ge\ \varkappa-2\epsilon\sqrt{\kappa}\ \ge\ \kappa-3\epsilon-2\epsilon\sqrt{\kappa}\ \ge\ \kappa-\eta,$$

the last step by the choice $\epsilon\le\eta/(3+2\sqrt{\kappa})$. This proves claim 2.

Claim 3. Fix $\pi$ and $\eta>0$, and for $k\in\{0,\dots,K-1\}$ and $N\ge1$ define

$$f^{(k)}_{N}(s)=\mathbb{E}\bigl[\mathbf{1}_{\mathcal{T}^{\mathrm{nr}}_{k}(s)}\,u_{s}\cdot R_{s}u_{s}\bigr]\qquad(s\in[t_{k},t_{k+1}]).$$

Each $f^{(k)}_{N}$ is nonnegative, because $u_{s}\cdot R_{s}u_{s}\ge r|u_{s}|^{2}\ge0$ by (H1), and is measurable on $[t_{k},t_{k+1}]$ by hypothesis (MS); its integral over that block is the $k$-th summand appearing in claim 7 of the ledger lemma.

Fix $k$ and $s\in[t_{k},t_{k+1}]$. The event $\mathcal{H}=\mathcal{T}^{\mathrm{nr}}_{k}(s)$ belongs to $\mathcal{G}_{s}$ by claim 2 of the ledger lemma, so claim 3 of the cascade filtering lemma gives

$$f^{(k)}_{N}(s)\ \ge\ \sum_{\gamma,\delta}\Xi^{\gamma\delta}_{s}\,\mathbb{E}\bigl[\mathbf{1}_{\mathcal{H}}\varepsilon^{\gamma}_{s}\varepsilon^{\delta}_{s}\bigr]=\sum_{j=1}^{m}\mathbb{E}\Bigl[\mathbf{1}_{\mathcal{H}}\sum_{\gamma,\delta}b^{\gamma}_{s,j}b^{\delta}_{s,j}\varepsilon^{\gamma}_{s}\varepsilon^{\delta}_{s}\Bigr],$$

the equality by the column identity of claim 1 applied to the matrix $\mathcal{M}^{\gamma\delta}=\mathbb{E}[\mathbf{1}_{\mathcal{H}}\varepsilon^{\gamma}_{s}\varepsilon^{\delta}_{s}]$ and by the linearity of the integral. Let $\eta'>0$. Applying claim 2 to each of the $m$ vectors $c=b_{s,j}$ with tolerance $\eta'/m$ and taking the largest of the resulting thresholds, there is $N''$ such that for every $N\ge N''$

$$f^{(k)}_{N}(s)\ \ge\ \sum_{j=1}^{m}\Bigl(b_{s,j}\cdot(\Pi_{s}b_{s,j})-\frac{\eta'}{m}\Bigr)=\sum_{\gamma,\delta}\Xi^{\gamma\delta}_{s}\Pi^{\gamma\delta}_{s}-\eta',$$

again by the column identity. As $\eta'>0$ was arbitrary, the sequence $\bigl(f^{(k)}_{N}(s)\bigr)_{N\ge1}$ satisfies

$$\liminf_{N\to\infty}f^{(k)}_{N}(s)\ \ge\ \sum_{\gamma,\delta}\Xi^{\gamma\delta}_{s}\Pi^{\gamma\delta}_{s}\qquad(s\in[t_{k},t_{k+1}]).$$

By Fatou's lemma, applied to the nonnegative measurable functions $f^{(k)}_{N}$ on $[t_{k},t_{k+1}]$ with the restricted Lebesgue measure, and then by the monotonicity of the integral together with claim 1,

$$\liminf_{N\to\infty}\int_{[t_{k},t_{k+1}]}f^{(k)}_{N}(s)\,ds\ \ge\ \int_{[t_{k},t_{k+1}]}\liminf_{N\to\infty}f^{(k)}_{N}(s)\,ds\ \ge\ \int_{[t_{k},t_{k+1}]}\sum_{\gamma,\delta}\Xi^{\gamma\delta}_{s}\Pi^{\gamma\delta}_{s}\,ds .$$

Hence for each $k$ there is $N^{(k)}$ with $\int_{[t_{k},t_{k+1}]}f^{(k)}_{N}\,ds\ge\int_{[t_{k},t_{k+1}]}\sum_{\gamma,\delta}\Xi^{\gamma\delta}_{s}\Pi^{\gamma\delta}_{s}\,ds-\eta/K$ for every $N\ge N^{(k)}$. Let $N_{4}$ be the largest of $N^{(0)},\dots,N^{(K-1)}$ and sum over $k$. Since $t_{0}=0$, $t_{K}=T$ and $t_{k}<t_{k+1}$ for $k\le K-1$ (the number of blocks $K$ being least with $KT_{0}\ge T$), the intervals $[t_{k},t_{k+1}]$ are adjacent with union $[0,T]$, so by the additivity of the Lebesgue integral of a continuous function over adjacent compact intervals (Restricted Lebesgue Measure and Integral Toolkit on a Compact Interval) the sum of the right-hand sides is $\int_{[0,T]}\sum_{\gamma,\delta}\Xi^{\gamma\delta}_{s}\Pi^{\gamma\delta}_{s}\,ds-\eta$. This proves claim 3.

Claim 4. Let $\varepsilon''>0$. By conclusion (b) of the asymptotic lower bound theorem, applied with $\varepsilon'=\varepsilon''/2$, there are an admissible parameter vector $\pi$ and a natural number $N_{0}$ such that for every $N\ge N_{0}$

$$\mathcal{J}_{N}\ \ge\ V_{0}+\sum_{k=0}^{K-1}\int_{[t_{k},t_{k+1}]}\mathbb{E}\bigl[\mathbf{1}_{\mathcal{T}^{\mathrm{nr}}_{k}(s)}u_{s}\cdot R_{s}u_{s}\bigr]\,ds-\frac{\varepsilon''}{2},$$

the blocks and near-field tracked events being those formed from $\pi$. Apply claim 3 to this $\pi$ with $\eta=\varepsilon''/2$, obtaining $N_{4}$, and put $N_{5}=\max(N_{0},N_{4})$. For $N\ge N_{5}$ the two displays combine to

$$\mathcal{J}_{N}\ \ge\ V_{0}+\int_{[0,T]}\sum_{\gamma,\delta}\Xi^{\gamma\delta}_{s}\Pi^{\gamma\delta}_{s}\,ds-\frac{\varepsilon''}{2}-\frac{\varepsilon''}{2},$$

which is claim 4.