$\displaystyle\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l+1)}(\mathbf{y},\mathbf{y}^{\prime}))}{d_{l+1}}-{\dot{\Sigma}}^{(l+1)}(\mathbf{y},\mathbf{y}^{\prime})\right|$
$\displaystyle\leq\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))}{d_{l}}-\frac{s^{2}}{2s-1}\breve{\sigma}_{s-1}\left({\Lambda}^{(l+1)}(\mathbf{y},\mathbf{y}^{\prime})\right)\right|$
$\displaystyle\leq\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))}{d_{l}}-\frac{s^{2}}{2s-1}\breve{\sigma}_{s-1}\left({\tilde{\mathbf{G}}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\right)\right|+$
$\displaystyle\ \ \ \ \
\frac{s^{2}}{2s-1}|\breve{\sigma}_{s-1}({\tilde{\mathbf{G}}}^{(l)})-\breve{\sigma}_{s-1}({\Lambda}^{(l+1)})|$
$\displaystyle\leq
s^{2}(1+\varepsilon)^{s-1}\varphi_{s-1}(d_{l},\delta/2,\min\\{1,{\Sigma}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})+\varepsilon\\})+\frac{2s^{2}\beta_{s}\varepsilon}{2s-1},$

holds with probability $1-\delta$. The last step follows from Lemma 16. On
taking a union bound, we can conclude that

$\displaystyle\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l+1)}(\mathbf{y},\mathbf{y}^{\prime}))}{d_{l+1}}-{\dot{\Sigma}}^{(l+1)}(\mathbf{y},\mathbf{y}^{\prime})\right|$
$\displaystyle\leq
s^{2}(1+\varepsilon)^{s-1}\varphi_{s-1}(d_{l},\delta/6,1)+\frac{2s^{2}\beta_{s}\varepsilon}{2s-1},$

holds for all
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$
with probability $1-\delta$. Since we have already invoked Lemma 16, it also
gives us that

$\displaystyle\|{\boldsymbol{\Delta}}^{(l+1)}(\mathbf{x},\mathbf{x}^{\prime})\|_{2}$
$\displaystyle\leq
s^{2}\left[2\left(1+\varepsilon\right)\log\left(\frac{6d_{l}}{\delta}\right)\right]^{s-1},$

holds for all
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$
with probability $1-\delta$. Using this result along with Lemma 2 and
$\varepsilon\leq 1/s$ yields us

$\displaystyle\Pr\left[\bar{\mathcal{A}}^{l}(\varepsilon)\Rightarrow\bar{\mathcal{D}}^{l+1}\left(3s^{2}\varphi_{s-1}(d_{l},\delta/6,1)+\frac{2s^{2}\beta_{s}\varepsilon}{2s-1}\right)\land\bar{\mathcal{E}}^{l+1}\left(3s^{2}\left[2\log\left(\frac{6d_{l}}{\delta}\right)\right]^{s-1}\right)\right]\geq
1-\delta,$

as required.

###  B.8 Proof of Lemma 15

Consider,

$\displaystyle\Pr\left[\bar{\mathcal{A}}(\varepsilon)\Rightarrow\bar{\mathcal{D}}(\varepsilon^{\prime})\land\bar{\mathcal{E}}(\varepsilon^{\prime\prime})\right]$
$\displaystyle=\Pr\left[\left(\bigcap_{l=0}^{L}\bar{\mathcal{A}}^{l}(\varepsilon)\right)\Rightarrow\left(\bigcap_{l=0}^{L}\left\\{\bar{\mathcal{D}}^{l+1}(\varepsilon^{\prime})\land\bar{\mathcal{E}}^{l+1}(\varepsilon^{\prime\prime})\right\\}\right)\right]$
$\displaystyle=\Pr\left[\neg\left(\bigcap_{l=0}^{L}\bar{\mathcal{A}}^{l}(\varepsilon)\right)\lor\left(\bigcap_{l=0}^{L}\left\\{\bar{\mathcal{D}}^{l+1}(\varepsilon^{\prime})\land\bar{\mathcal{E}}^{l+1}(\varepsilon^{\prime\prime})\right\\}\right)\right]$
$\displaystyle=1-\Pr\left[\left(\bigcap_{l=0}^{L}\bar{\mathcal{A}}^{l}(\varepsilon)\right)\land\left(\bigcup_{l=0}^{L}\neg\left\\{\bar{\mathcal{D}}^{l+1}(\varepsilon^{\prime})\land\bar{\mathcal{E}}^{l+1}(\varepsilon^{\prime\prime})\right\\}\right)\right]$
$\displaystyle=1-\Pr\left[\left(\bigcup_{l=0}^{L}\left(\bigcap_{l=0}^{L}\bar{\mathcal{A}}^{l}(\varepsilon)\right)\land\neg\left\\{\bar{\mathcal{D}}^{l+1}(\varepsilon^{\prime})\land\bar{\mathcal{E}}^{l+1}(\varepsilon^{\prime\prime})\right\\}\right)\right]$
$\displaystyle\geq
1-\sum_{l=0}^{L}\Pr\left[\left(\bigcap_{l=0}^{L}\bar{\mathcal{A}}^{l}(\varepsilon)\right)\land\neg\left\\{\bar{\mathcal{D}}^{l+1}(\varepsilon^{\prime})\land\bar{\mathcal{E}}^{l+1}(\varepsilon^{\prime\prime})\right\\}\right]$
$\displaystyle\geq
1-\sum_{l=0}^{L}\Pr\left[\bar{\mathcal{A}}^{l}(\varepsilon)\land\neg\left\\{\bar{\mathcal{D}}^{l+1}(\varepsilon^{\prime})\land\bar{\mathcal{E}}^{l+1}(\varepsilon^{\prime\prime})\right\\}\right]$
$\displaystyle\geq
1-\sum_{l=0}^{L}\Pr\left[\neg\left(\bar{\mathcal{A}}^{l}(\varepsilon)\Rightarrow\bar{\mathcal{D}}^{l+1}(\varepsilon^{\prime})\land\bar{\mathcal{E}}^{l+1}(\varepsilon^{\prime\prime})\right)\right]$
$\displaystyle\geq 1-\sum_{l=0}^{L}\frac{\delta}{L+1}$ $\displaystyle\geq
1-\delta,$

where the eighth line follows from Lemma 14 and the choice of
$\varepsilon^{\prime}$ and $\varepsilon^{\prime\prime}$.

###  B.9 Proof of Lemma 16

We can rewrite
$\mathrm{tr}\left({\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\right)$
as follows:

$\displaystyle\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime}))$
$\displaystyle=\mathrm{tr}\left[{\mathbf{D}}^{(l)}(\mathbf{x}){\mathbf{D}}^{(l)}(\mathbf{x}^{\prime})\right]$
$\displaystyle=\mathrm{tr}\left[\text{diag}\left(\sigma_{s}^{\prime}\left({\mathbf{f}}^{(l)}(\mathbf{x})\right)\right)\text{diag}\left(\sigma_{s}^{\prime}\left({\mathbf{f}}^{(l)}(\mathbf{x}^{\prime})\right)\right)\right]$
$\displaystyle=\left\langle\sigma_{s}^{\prime}\left({\mathbf{f}}^{(l)}(\mathbf{x})\right),\sigma_{s}^{\prime}\left({\mathbf{f}}^{(l)}(\mathbf{x}^{\prime})\right)\right\rangle$
$\displaystyle=s^{2}\left\langle\sigma_{s-1}\left({\mathbf{W}}^{(l)}{\mathbf{h}}^{(l-1)}(\mathbf{x})\right),\sigma_{s-1}\left({\mathbf{W}}^{(l)}{\mathbf{h}}^{(l-1)}(\mathbf{x}^{\prime})\right)\right\rangle.$

Note that since all the matrices $\\{{\mathbf{W}}^{(i)}\\}_{i=1}^{l-1}$ are
fixed, ${\mathbf{h}}^{(l-1)}(\cdot)$ is a fixed function. Consequently, each
term of the vector ${\mathbf{W}}^{(l)}{\mathbf{h}}^{(l-1)}(\mathbf{x})$ is
distributed as
$\mathcal{N}\left(0,\left\langle{\mathbf{h}}^{(l)}(\mathbf{x}),{\mathbf{h}}^{(l)}(\mathbf{x})\right\rangle\right)$
and is independent of others. If $({\mathbf{w}}^{(l)}_{j})^{\top}$ denotes the
$j^{\text{th}}$ row of the matrix ${\mathbf{W}}^{(l)}$, then we can write the
inner product as

$\displaystyle\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime}))$
$\displaystyle=s^{2}\left\langle\sigma_{s-1}\left({\mathbf{W}}^{(l)}{\mathbf{h}}^{(l-1)}(\mathbf{x})\right),\sigma_{s-1}\left({\mathbf{W}}^{(l)}{\mathbf{h}}^{(l-1)}(\mathbf{x}^{\prime})\right)\right\rangle$
$\displaystyle=s^{2}\sum_{j=1}^{d_{l}}\sigma_{s-1}\left(\left({\mathbf{w}}^{(l)}_{j}\right)^{\top}{\mathbf{h}}^{(l-1)}(\mathbf{x})\right)\sigma_{s-1}\left(\left({\mathbf{w}}^{(l)}_{j}\right)^{\top}{\mathbf{h}}^{(l-1)}(\mathbf{x}^{\prime})\right)$
$\displaystyle=s^{2}\sum_{j=1}^{d_{l}}Z_{j},$

where $Z_{j}$ are all independent and identically distributed as
$\sigma_{s-1}(X)\sigma_{s-1}(Y)$ where
$(X,Y)\sim\mathcal{N}\left(0,{\tilde{\mathbf{G}}}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime})\right)$.
If we define $\tilde{Z}_{j}:=(G_{11}G_{22})^{-\frac{(s-1)}{2}}$, then
$\tilde{Z}_{j}$ are all independent and identically distributed as
$\sigma_{s-1}(\tilde{X})\sigma_{s-1}(\tilde{Y})$ where
$(\tilde{X},\tilde{Y})\sim\mathcal{N}\left(0,\Sigma_{\rho_{G}}\right)$ and
$\rho_{G}=\frac{G_{12}}{\sqrt{G_{11}G_{22}}}$. From Lemma 5, we know that

$\displaystyle\left|\frac{1}{d_{l}}\sum_{j=1}^{d_{l}}\tilde{Z}_{j}-\mathbb{E}[\tilde{Z}_{1}]\right|\leq\varphi_{s-1}(d_{l},\delta,\rho_{G})$

with probability at least $1-\delta$. Consequently,

$\displaystyle\left|\frac{1}{d_{l}}\sum_{j=1}^{d_{l}}{Z}_{j}-\mathbb{E}[Z_{1}]\right|\leq(G_{11}G_{22})^{\frac{(s-1)}{2}}\varphi_{s-1}(d_{l},\delta,\rho_{G})$

with probability at least $1-\delta$. Note that
$\mathbb{E}[Z_{1}]=\underset{(X,Y)\sim\mathcal{N}\left(0,{\tilde{\mathbf{G}}}^{(h)}(\mathbf{x},\mathbf{x}^{\prime})\right)}{\mathbb{E}}[\sigma_{s-1}(X)\sigma_{s-1}(Y)]=\frac{1}{c_{s-1}}\breve{\sigma}_{s-1}\left({\tilde{\mathbf{G}}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\right)$
and $c_{s-1}=c_{s}(2s-1)$. On combining this with the previous result, we can
conclude that,

$\displaystyle\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime}))}{d_{l}}-\frac{s^{2}}{2s-1}\breve{\sigma}_{s-1}\left({\mathbf{G}}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime})\right)\right|$
$\displaystyle\leq
s^{2}\left|\frac{1}{d_{l}}\sum_{j=1}^{d_{l}}{Z}_{j}-\mathbb{E}[Z_{1}]\right|$
$\displaystyle\leq
s^{2}(G_{11}G_{22})^{\frac{(s-1)}{2}}\varphi_{s-1}(d_{l},\delta/2,\rho_{G}),$

holds with probability $1-\delta/2$. For the spectral norm of
${\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})$, we have,

$\displaystyle\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\|_{2}$
$\displaystyle=s^{2}\max_{j\in
d_{l}}Z_{j}=s^{2}(G_{11}G_{22})^{\frac{(s-1)}{2}}\max_{j\in
d_{l}}\tilde{Z}_{j}.$

Using (26), we can show that

$\displaystyle\Pr\left(\max_{j\in
d_{l}}\tilde{Z}_{j}>\left[(1+\rho_{G})\log\left(\frac{d_{l}}{\delta}\right)\right]^{s-1}\right)$
$\displaystyle\leq
d_{l}\Pr\left(\tilde{Z}_{1}>\left[(1+\rho_{G})\log\left(\frac{d_{l}}{\delta}\right)\right]^{s-1}\right)$
$\displaystyle\leq
d_{l}\exp\left(-\frac{1+\rho_{G}}{1+\rho_{G}}\log\left(\frac{d_{l}}{\delta}\right)\right)\leq\delta.$

Consequently,

$\displaystyle\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\|_{2}$
$\displaystyle=s^{2}(G_{11}G_{22})^{\frac{(s-1)}{2}}\max_{j\in
d_{l}}\tilde{Z}_{j}$ $\displaystyle\leq
s^{2}(G_{11}G_{22})^{\frac{(s-1)}{2}}\left[(1+\rho_{G})\log\left(\frac{2d_{l}}{\delta}\right)\right]^{s-1}$

holds with probability $1-\delta/2$. Thus, both the hold simultaneously with
probability at least $1-\delta$.

###  B.10 Proof of Lemma 18

We will prove the claim for
$\mathbf{y}\in\\{\mathbf{x},\mathbf{x}^{\prime}\\}$. Recall that
${\mathbf{G}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})=[{\mathbf{h}}^{(l)}(\mathbf{y})\
\ {\mathbf{h}}^{(l)}(\mathbf{y}^{\prime})]\in\mathbb{R}^{d_{l}\times 2}$. For
simplicity, we drop the arguments from ${\mathbf{h}}^{(l)}$ and
${\mathbf{b}}^{(l+1)}$. Define
$\boldsymbol{\Pi}_{\mathbf{h}}=\mathbf{h}\mathbf{h}^{\top}$ and
$\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}=\boldsymbol{\Pi}_{\mathbf{G}}-\boldsymbol{\Pi}_{\mathbf{h}}$.
Note that $\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}$ is still a projection
matrix of rank $0$ or $1$.

Recall that ${\mathbf{b}}^{(l+1)}$ is the gradient with respect to the pre-
activation layer $l+1$ given by
${\mathbf{f}}^{(l+1)}={\mathbf{W}}^{(l+1)}{\mathbf{h}}^{(l)}$. If we view the
output $f$ as a function of
${\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)}$, then we
have the following relation:

$\displaystyle\frac{\partial}{\partial{\mathbf{h}}^{(l)}}f({\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)})=\left({\mathbf{b}}^{(l+1)}\right)^{\top}{\mathbf{W}}^{(l+1)}.$

Recall that $\sigma_{s}$ is $s$-homogeneous,that is, $\sigma_{s}(\lambda
x)=\lambda^{s}\sigma_{s}(x)$ for any $\lambda>0$. Using this recursion
repeatedly, we have,

$\displaystyle
f(\lambda{\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)})$
$\displaystyle=\lambda^{s^{L-l}}f({\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)})$
$\displaystyle\implies\frac{\partial}{\partial\lambda}f(\lambda{\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)})$
$\displaystyle=s^{L-l}\lambda^{(s^{L-l}-1)}f({\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)}).$

Using this, we can write,

$\displaystyle
f({\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)})$
$\displaystyle=s^{l-L}\frac{\partial}{\partial\lambda}f(\lambda{\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)})\bigg{|}_{\lambda=1}$
$\displaystyle=s^{l-L}\frac{\partial}{\partial(\lambda{\mathbf{h}}^{(l)})}f(\lambda{\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)})\bigg{|}_{\lambda=1}\frac{\partial(\lambda{\mathbf{h}}^{(l)})}{\partial\lambda}\bigg{|}_{\lambda=1}$
$\displaystyle=s^{l-L}\frac{\partial}{\partial(\lambda{\mathbf{h}}^{(l)})}f(\lambda{\mathbf{h}}^{(l)},{\mathbf{W}}^{(l+1)},\dots,{\mathbf{W}}^{(L+1)})\bigg{|}_{\lambda=1}{\mathbf{h}}^{(l)}$
$\displaystyle=s^{l-L}\left({\mathbf{b}}^{(l+1)}\right)^{\top}{\mathbf{W}}^{(l+1)}{\mathbf{h}}^{(l)}.$

By definition of $\boldsymbol{\Pi}_{\mathbf{h}}$, we have,

$\displaystyle\left\|\boldsymbol{\Pi}_{\mathbf{h}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right\|$
$\displaystyle=\left\|\frac{1}{\|{\mathbf{h}}^{(l)}\|^{2}}\cdot{\mathbf{h}}^{(l)}\left({\mathbf{h}}^{(l)}\right)^{\top}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right\|$
$\displaystyle=s^{L-l}\frac{|f(\mathbf{y};\mathbf{W})|}{\|{\mathbf{h}}^{(l)}\|}.$

Since
$\bar{\mathcal{A}}^{L}(\varepsilon_{1}/2)\land\bar{\mathcal{C}}(\varepsilon_{3})$,
$\|{\mathbf{h}}^{(l)}\|\geq 1-\varepsilon_{1}/2\geq 1/2$ and
$|f(\mathbf{y};\mathbf{W})|\leq\varepsilon_{3}$. Consequently,

$\displaystyle\left\|\boldsymbol{\Pi}_{\mathbf{h}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right\|$
$\displaystyle\leq s^{L-l}\varepsilon_{3}\sqrt{2}.$

Similar to the proof of Lemma 11, we note that for a fixed $\mathbf{h}$ and
conditioned on ${\mathbf{f}}^{(l+1)}$ and ${\mathbf{b}}^{(l+1)}$ Lemma 3 gives
us that

$\displaystyle{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{h}}^{\perp}\overset{d}{=}_{{\mathbf{f}}^{(l+1)}={\mathbf{W}}^{(l+1)}{\mathbf{h}}^{(l)}}\widetilde{\mathbf{W}}\boldsymbol{\Pi}_{\mathbf{h}}^{\perp},$

where $\widetilde{\mathbf{W}}$ is a i.i.d. copy of ${\mathbf{W}}^{(l+1)}$.
From the definition of $\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}$, we can
conclude that
$\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}^{\top}\boldsymbol{\Pi}_{\mathbf{h}}=0$.
Thus, combining this with the previous equation, we can conclude that

$\displaystyle{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}\overset{d}{=}_{{\mathbf{f}}^{(l+1)}={\mathbf{W}}^{(l+1)}{\mathbf{h}}^{(l)}}\widetilde{\mathbf{W}}\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}.$

If $\text{rank}(\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}})=1$, then
$\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}=\mathbf{u}\mathbf{u}^{\top}$ for
some unit vector $\mathbf{u}$. Thus,

$\displaystyle\left\|\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right\|$
$\displaystyle=\left\|\mathbf{u}\mathbf{u}^{\top}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right\|$
$\displaystyle=\left|\mathbf{u}^{\top}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right|$
$\displaystyle\overset{d}{=}\left|\mathbf{u}^{\top}\widetilde{\mathbf{W}}^{\top}{\mathbf{b}}^{(l+1)}\right|=|t|,$

where $t\sim\mathcal{N}(0,\|{\mathbf{b}}^{(l+1)}\|^{2})$. Therefore, with
probability at least $1-\delta/2$,

$\displaystyle|t|\leq\|{\mathbf{b}}^{(h+1)}\|\sqrt{2\log\left(\frac{4}{\delta}\right)}\leq(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{4}{\delta}\right)}.$

In the above step, we used similar arguments as used in Appendix. B.7 to bound
$\|{\mathbf{b}}^{(l+1)}\|$. If
$\text{rank}(\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}})=0$,
$\left\|\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right\|=0$.
On combining this with the previous result, we obtain that with probability
$1-\delta$

$\displaystyle\left\|\boldsymbol{\Pi}_{\mathbf{G}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right\|$
$\displaystyle\leq\left\|\boldsymbol{\Pi}_{\mathbf{G}/\mathbf{h}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right\|+\left\|\boldsymbol{\Pi}_{\mathbf{h}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}\right\|$
$\displaystyle\leq(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{4}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}.$

Taking the union bound over the two possible choices of $\mathbf{y}$ gives us
the final result.

##  Appendix C Proof of Theorem 2

The proof of Theorem 2 involves combining several smaller results, some of
which follow from Theorem 1 and the others are minor modifications of existing
results. We being with stating these results along with proofs, if needed, and
then combine them to prove Theorem 1.

Firstly, using Theorem 1 along with Lemma 5.1 from Zhou et al. [2020], we can
conclude that for
$m\geq\text{poly}(T,L,K,\lambda^{-1},\lambda_{0}^{-1},S^{-1},\log(1/\delta))$,
there exists a $\mathbf{W}^{*}$ such that
$h(\mathbf{x})=\left\langle\mathbf{g}(\mathbf{x};\mathbf{W}_{0}),\mathbf{W}^{*}-\mathbf{W}_{0}\right\rangle$
with probability at least $1-\delta$ for all
$\mathbf{x}\in\mathcal{Z}=\\{\\{\mathbf{x}_{t,a}\\}_{a=1}^{K}\\}_{t=1}^{T}$.
Furthermore, $\|\mathbf{W}^{*}-\mathbf{W}_{0}\|_{2}\leq S$.

Secondly, using Lemma 4 and 8, along with (12), we can conclude that for
$m\geq\text{poly}(T,L,K,\lambda^{-1},\lambda_{0}^{-1},S^{-1},\log(1/\delta))$,
$\|\mathbf{g}(\mathbf{x};\mathbf{W}_{0})\|\leq\mathcal{O}(s^{L})$, independent
of $m$.

Thirdly, we know that the spectral norm of the Hessian of the neural net is
$\mathcal{O}(m^{-1/2})$ [Liu et al., 2020, Theorem 3.2] for all $\mathbf{W}$
such that $\|\mathbf{W}-\mathbf{W}_{0}\|\leq R$, where $R$ is some finite
radius. Here the implied constant depends on $s,L$ and $R$. Thus, by choosing
$m$ to be sufficiently large, we can conclude that for all
$\|\mathbf{W}-\mathbf{W}_{0}\|\leq\sqrt{T/\lambda}$,
$\|\tilde{\mathbf{H}}(\mathbf{W})\|\leq C_{s,L}m^{-1/3}$. Here
$\tilde{\mathbf{H}}$ denotes the Hessian and $C_{s,L}$ denotes a constant that
depends only on $s$ and $L$. Using this relation, we can conclude that for any
$\|\mathbf{W}-\mathbf{W}_{0}\|\leq\sqrt{T/\lambda}$, we have

$\displaystyle|f(\mathbf{x};\mathbf{W})-f(\mathbf{x};\mathbf{W}_{0})-\left\langle\mathbf{g}(\mathbf{x};\mathbf{W}_{0}),\mathbf{W}-\mathbf{W}_{0}\right\rangle|$
$\displaystyle\leq C_{s,L}m^{-1/3}T/\lambda$
$\displaystyle\implies|f(\mathbf{x};\mathbf{W})-\left\langle\mathbf{g}(\mathbf{x};\mathbf{W}_{0}),\mathbf{W}-\mathbf{W}_{0}\right\rangle|$
$\displaystyle\leq C_{s,L}\lambda^{-1}m^{-1/6},$

where the last step follows by choosing a sufficiently large $m$ and
Assumption 1. Moreover, the above result holds for any
$\mathbf{x}\in\mathcal{Z}$.

Lastly, using the relation
$h(\mathbf{x})=\left\langle\mathbf{g}(\mathbf{x};\mathbf{W}_{0}),\mathbf{W}^{*}-\mathbf{W}_{0}\right\rangle$
along with the result from Vakili et al. [2021a, Theorem 1] on the kernel
defined by neural net at initialization, i.e.
$\hat{k}(\mathbf{x};\mathbf{x}^{\prime})=\left\langle\mathbf{g}(\mathbf{x};\mathbf{W}_{0}),\mathbf{g}(\mathbf{x}^{\prime};\mathbf{W}_{0})\right\rangle$,
we can conclude that

$\displaystyle|h(\mathbf{x})-\mathbf{g}^{\top}(\mathbf{x};\mathbf{W}_{0})\mathbf{V}_{t}^{-1}\mathbf{r}|\leq\left(S+\nu\sqrt{\frac{2}{\lambda}\log(1/\delta)}\right)\hat{\sigma}_{t}(\mathbf{x}).$

In the above equation, $\mathbf{V}_{t}$ and $\hat{\sigma}_{t}$ are defined
with respect to the dataset $\mathcal{D}$ and
$\mathbf{r}=\sum_{i=1}^{t}y_{i}\mathbf{g}(\mathbf{x}_{i};\mathbf{W}_{0})$.
Also, we have used the independence of dataset from noise sequence to invoke
the above theorem.

Using these results we can prove our main result. For any
$\mathbf{x}\in\mathcal{Z}$, we have,

$\displaystyle|h(\mathbf{x})-f(\mathbf{x};\mathbf{W}_{t})|$
$\displaystyle\leq|h(\mathbf{x})-\mathbf{g}^{\top}(\mathbf{x};\mathbf{W}_{0})\mathbf{V}^{-1}\mathbf{r}|+|\mathbf{g}^{\top}(\mathbf{x};\mathbf{W}_{0})\mathbf{V}^{-1}\mathbf{r}-f(\mathbf{x};\mathbf{W}_{t})|$
$\displaystyle\leq\left(S+\nu\sqrt{\frac{2}{\lambda}\log(1/\delta)}\right)\hat{\sigma}_{t}(\mathbf{x})+|\mathbf{g}^{\top}(\mathbf{x};\mathbf{W}_{0})\mathbf{V}_{t}^{-1}\mathbf{r}-f(\mathbf{x};\mathbf{W}_{t})|$
$\displaystyle\leq\frac{C_{s,L}}{\lambda
m^{1/6}}+\left(S+\nu\sqrt{\frac{2}{\lambda}\log(1/\delta)}\right)\hat{\sigma}(\mathbf{x})+|\mathbf{g}^{\top}(\mathbf{x};\mathbf{W}_{0})\mathbf{V}_{t}^{-1}\mathbf{r}-\left\langle\mathbf{g}(\mathbf{x};\mathbf{W}_{0}),\mathbf{W}_{t}-\mathbf{W}_{0}\right\rangle|$
$\displaystyle\leq\frac{C_{s,L}}{\lambda
m^{1/6}}+\left(S+\nu\sqrt{\frac{2}{\lambda}\log(1/\delta)}\right)\hat{\sigma}(\mathbf{x})+\|\mathbf{W}_{t}-\mathbf{W}_{0}-\mathbf{V}_{t}^{-1}\mathbf{r}\|\|\mathbf{V}_{t}\|\hat{\sigma}(\mathbf{x})$
$\displaystyle\leq\frac{C_{s,L}}{\lambda
m^{1/6}}+\left(S+\nu\sqrt{\frac{2}{\lambda}\log(1/\delta)}+(1-\eta\lambda)^{J/2}\sqrt{t/\lambda}+\frac{C_{s,L}^{\prime}}{\lambda
m^{1/6}}\right)(\lambda+C_{s,L}^{\prime\prime}t)\hat{\sigma}(\mathbf{x}),$

as required. As before $C_{s,L},C_{s,L}^{\prime}$ and $C_{s,L}^{\prime\prime}$
represent constants that depend only on $s$ and $L$. In the last but one step,
we used the fact that for any positive definite matrix
$\mathbf{A}\in\mathbb{R}^{d\times d}$ and
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$,
$\left\langle\mathbf{x},\mathbf{y}\right\rangle\leq(\mathbf{x}^{T}\mathbf{A}^{-1}\mathbf{x})\cdot(\mathbf{y}^{T}\mathbf{A}\mathbf{y})\leq(\mathbf{x}^{T}\mathbf{A}^{-1}\mathbf{x})\|\mathbf{A}\|_{2}\|\mathbf{y}\|_{2}$.
And in the last step, we used the results from Zhou et al. [2020, Lemmas
B.3,B.5,C.2] along with the bound on gradient established earlier.

##  Appendix D Additional Details on NeuralGCB

We first provide all the pseudo codes for NeuralGCB followed by proof of
Theorem 3.

###  D.1 Pseudo Codes

Algorithm 2 NeuralGCB

1: Require: Time horizon $T$, maximum initial variance $\sigma_{0}$, error
probability $\delta$

2: Initialize: $R\leftarrow\lceil\log_{2}T\rceil$, Ensemble of $R$ Neural Nets
with $\mathbf{W}_{0}^{(r)}=\mathbf{W}_{0}$,
$\Psi_{0}^{(r)}\leftarrow\emptyset,\ \ \forall\ r\in[R]$,
$\mathcal{H}\leftarrow\emptyset$, arrays ctr, max_mu, fb of size $R$ with all
elements set to $0$, batch sizes $\\{q_{r}\\}_{r=1}^{R}$

3: for $t=1,2,3,\dots T$ do

4: $r\leftarrow 1,\hat{A}_{r}(t)=[K]$

5: while True do

6: Receive the context-action pairs $\\{\mathbf{x}_{t,a}\\}_{a=1}^{K}$

7:
$\\{f(\mathbf{x}_{t,a};\mathbf{W}_{t}^{(r)}),\hat{\sigma}_{t-1}^{(r)}(\mathbf{x}_{t,a})\\}_{a=1}^{K},\mathbf{W}_{t}^{(r)},\texttt{fb}[r]\leftarrow$
GetPredictions$\left(\mathcal{H},\Psi_{t-1}^{(r)},\\{\mathbf{x}_{t,a}\\}_{a=1}^{K},\texttt{fb}[r],\mathbf{W}_{t-1}^{(r)},q_{r}\right)$

8:
$\tilde{\sigma}_{t-1}^{(r)}\leftarrow\max_{a\in\hat{A}_{r}(t)}\hat{\sigma}_{t-1}^{(r)}(x_{t,a})$,
$\texttt{max\\_mu}[r]\leftarrow\operatorname*{arg\,max}_{a\in\hat{A}_{r}(t)}f(x_{t,a};\mathbf{W}_{t-1}^{(r)})$

9: if $\tilde{\sigma}_{t-1}^{(r)}\leq\sigma_{0}2^{-r}$ then

10:
$a_{\text{UCB}}\leftarrow\operatorname*{arg\,max}_{a\in\hat{A}_{r}(t)}\text{UCB}_{t-1}^{(r)}(\mathbf{x}_{t,a})$

11: if ${\sigma}_{t-1}^{(r)}(x_{t,a_{\text{UCB}}})\leq\eta_{0}/\sqrt{t}$ then

12: Choose $a_{t}\leftarrow a_{\text{UCB}}$ and set $\upsilon_{t}\leftarrow 1$

13: Receive $y_{t}=h(\mathbf{x}_{t,a_{t}})+\xi_{t}$ and update
$\mathcal{H}\leftarrow\mathcal{H}\cup\\{(x_{t,a_{t}},y_{t})\\}$

14: Set
$\Psi_{t}^{(r+1)}\leftarrow\Psi_{t-1}^{(r+1)}\cup\\{(t,\upsilon_{t})\\}$ and
$\Psi_{t}^{(r^{\prime})}\leftarrow\Psi_{t-1}^{(r^{\prime})}$ for all
$r^{\prime}\in[R]\setminus\\{r+1\\}$

15: break

16: else

17:
$\hat{A}_{r+1}(t)\leftarrow\\{a\in\hat{A}_{r}(t):\text{UCB}_{t-1}^{(r)}(\mathbf{x}_{t,a})\geq\max_{a^{\prime}\in\hat{A}_{r}(t)}\text{LCB}_{t-1}^{(r)}(\mathbf{x}_{t,a^{\prime}})\\}$,
$r\leftarrow r+1$

18: end if

19: else

20: if $r=1$ or$\ \texttt{ctr}[r]>\alpha_{0}4^{r}$ then

21: Choose any $a_{t}\in\hat{A}_{r}(t)$ such that
$\hat{\sigma}_{t-1}^{(r)}(x_{t,a})>\sigma_{0}2^{-r}$ and set
$\upsilon_{t}\leftarrow 2$

22: else

23: Choose $a_{t}\leftarrow\texttt{max\\_mu}[r-1]$ and set
$\upsilon_{t}\leftarrow 3$

24: end if

25: Receive $y_{t}=h(\mathbf{x}_{t,a_{t}})+\xi_{t}$ and update
$\mathcal{H}\leftarrow\mathcal{H}\cup\\{(x_{t,a_{t}},y_{t})\\}$,
$\texttt{ctr}[r]\leftarrow\texttt{ctr}[r]+1$

26: Set $\Psi_{t}^{(r)}\leftarrow\Psi_{t-1}^{(r)}\cup\\{(t,\upsilon_{t})\\}$
and $\Psi_{t}^{(r^{\prime})}\leftarrow\Psi_{t-1}^{(r^{\prime})}$ for all
$r^{\prime}\in[R]\setminus\\{r\\}$

27: break

28: end if

29: end while

30: end for

In Alg. 2, $\text{UCB}_{t}^{(r)}$ and $\text{LCB}_{t}^{(r)}$ refer to the
upper and lower confidence scores respectively at time $t$ corresponding to
index $r$ and are defined as
$\text{UCB}_{t}^{(r)}(\cdot)=f(\cdot;\mathbf{W}_{t}^{(r)})+\beta_{t}\hat{\sigma}_{t}^{(r)}(\cdot)$
and
$\text{LCB}_{t}^{(r)}(\cdot)=f(\cdot;\mathbf{W}_{t}^{(r)})-\beta_{t}\hat{\sigma}_{t}^{(r)}(\cdot)$.
The arrays ctr, max_mu and fb are used to store the exploitation count,
maximizer of the neural net output and feedback time instants respectively.
The exploitation count is tracked to ensure that the exploitation budget is
not exceeded. Similarly, the maximizer of the neural net output is stored to
guide the algorithm in exploitation at the next level and the feedback time
instants are used to keep track of last time instant when the neural net was
retrained, or equivalently obtained a feedback. Lastly, $\upsilon_{t}$’s
provide analytical and notational convenience and are not crucial to the
working of the algorithm.

GetPredictions is a local routine that calculates the predictive mean and
variance after appropriately retraining the neural net and described in Alg. 3
and used as a sub-routine in NeuralGCB. We would like to emphasize that
NeuralGCB computes only the mean with the trained parameters. The predictive
variance is computed using the gradients at initialization. This is made
possible by having an additional ad hoc neural net which is just use to
compute the gradients for calculating the variance. This is similar to the
setup used in [Kassraie and Krause, 2022].

After computing the predictive variance for the set of current actions, the
GetPredictions routine decides whether the neural net needs to be retrained
based on the previous feedback instant $t_{\texttt{fb}}$ and batch parameter
$q$. In particular, we consider two training schemes, fixed and adaptive. The
fixed frequency scheme retrains the neural net if there are an additional of
$q$ points in $\Psi$ after $t_{\texttt{fb}}$. Consequently, the neural
corresponding to the $r^{\text{th}}$ subset in the partition is retrained
after every $q_{r}$ points are added to the subset. On the other hand, in the
adaptive scheme, inspired by the rarely switching bandits Abbasi-Yadkori et
al. [2011], Wang et al. [2021], the neural net is retrained whenever
$\det(\mathbf{V})>q\det(\mathbf{V}_{\texttt{fb}})$ where $\mathbf{V}$ and
$\mathbf{V}_{\texttt{fb}}$ are as defined in line 2 and 3 of Alg. 3. Since
$\log(\det(\mathbf{V})/\det(\lambda\mathbb{I}))$ is a measure of information
gain, the neural net is effectively retrained only once sufficient additional
information has been obtained since the last time the neural net was trained.
We would like to point out that in the main text, we only refer to the fixed
training scheme due to space constraints. However, our NeuralGCB works even
with the adaptive scheme and the regret guarantees under this training
schedule are formalized in Appendix D.

Lastly, TrainNN is another local routine that carries out the training of
neural net for a given dataset using gradient descent for $J$ epochs with a
step size of $\eta$ starting with $\mathbf{W}_{0}$.

Algorithm 3 GetPredictions

1: Input: Set of past actions and their corresponding rewards $\mathcal{H}$,
Index set $\Psi$, Current set of actions $\\{\mathbf{x}_{t,a}\\}_{a=1}^{K}$,
Previous feedback instant $t_{\texttt{fb}}$, $\mathbf{W}_{t_{\texttt{fb}}}$,
Batch choice parameter $q$

2:
$\mathbf{Z}\leftarrow\lambda\mathbb{I}+\frac{1}{m}\sum_{i\in\Psi}\mathbf{g}(\mathbf{x}_{i};\mathbf{W}_{0})\mathbf{g}(\mathbf{x}_{i};\mathbf{W}_{0})^{\top}$

3:
$\mathbf{Z}_{\texttt{fb}}\leftarrow\lambda\mathbb{I}+\frac{1}{m}\sum_{i\in\Psi,i\leq
t_{\texttt{fb}}}\mathbf{g}(\mathbf{x}_{i};\mathbf{W}_{0})\mathbf{g}(\mathbf{x}_{i};\mathbf{W}_{0})^{\top}$

4: Set
$\sigma^{2}(\mathbf{x}_{t,a})\leftarrow\mathbf{g}(\mathbf{x}_{t,a};\mathbf{W}_{0})^{\top}\mathbf{Z}^{-1}\mathbf{g}(\mathbf{x}_{t,a};\mathbf{W}_{0})/m$
for all $a\in[K]$

5: For fixed batch size: $\texttt{to\\_train}=(|\Psi|-t_{\texttt{fb}}==q)$

6: For adaptive batch size:
$\texttt{to\\_train}=(\det(\mathbf{Z})>q\det(\mathbf{Z}_{\texttt{fb}}))$

7: if to_train then

8: $\mathbf{W}\leftarrow$
TrainNN$(m,L,J,\eta,\lambda,\mathbf{W}_{0},\\{(x_{r},y_{r})\in\mathcal{H}:r\in\Psi\\})$,
$t_{\texttt{fb}}\leftarrow|\Psi|$

9: else

10: $\mathbf{W}\leftarrow\mathbf{W}_{t_{\texttt{fb}}}$

11: end if

12: return
$\\{f(\mathbf{x}_{t,a};\mathbf{W}),\sigma(\mathbf{x}_{t,a})\\}_{a=1}^{K},\mathbf{W},t_{\texttt{fb}}$.

Algorithm 4
TrainNN($m,L,J,\eta,\lambda,\mathbf{W}_{0},\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{n}$)

1: Define
$\mathcal{L}(\mathbf{W})=\sum_{i=1}^{n}(f(\mathbf{x}_{i};\mathbf{W})-y_{i})^{2}+m\lambda\|\mathbf{W}-\mathbf{W}_{0}\|^{2}$

2: for $j=0,1,\dots,J-1$ do

3:
$\mathbf{W}_{j+1}=\mathbf{W}_{j}-\eta\nabla_{\mathbf{W}}\mathcal{L}(\mathbf{W}_{j})$

4: end for

5: return $\mathbf{W}_{J}$

###  D.2 Proof of Theorem 3

To analyse the regret of NeuralGCB, we divide the time horizon into three
disjoint sets depending on how the action at that time instant was chosen. In
particular, for $i=\\{1,2,3\\}$, we define

$\displaystyle\mathcal{T}_{i}(s)$
$\displaystyle:=\\{t\in\psi_{T}^{(r)}:\upsilon_{t}=i\\}$
$\displaystyle\mathcal{T}_{i}$
$\displaystyle:=\bigcup_{r=1}^{R}\mathcal{T}_{i}(r).$

Thus, $\mathcal{T}_{1},\mathcal{T}_{2}$ and$\mathcal{T}_{3}$ consist of all
the points chosen by the chosen algorithm at line $12,21$ and $23$
respectively. We consider the regret incurred at time instants in each of
these sets separately. We begin with $\mathcal{T}_{1}$. For any
$t\in\mathcal{T}_{1}(r)$,

$\displaystyle h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq
f(\mathbf{x}_{t,a^{*}_{t}};\mathbf{W}_{t-1}^{(r)})+\tilde{\beta}+\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a^{*}_{t}})-(f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t-1}^{(r)})-\tilde{\beta}-\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}}))$
$\displaystyle\leq
f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t-1}^{(r)})+\tilde{\beta}+\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})-f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t-1}^{(r)})+\tilde{\beta}+\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq
2\tilde{\beta}+2\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq 2\tilde{\beta}+\frac{2\eta_{0}\beta_{t-1}}{\sqrt{t}},$

where we use Theorem 2 in the first step,
$\tilde{\beta}=\frac{C_{s,L}}{\lambda m^{1/6}}$ and
$\beta_{t}=\left(S+\nu\sqrt{\frac{2}{\lambda}\log(1/\delta)}+(1-\eta\lambda)^{J/2}\sqrt{t/\lambda}+\frac{C_{s,L}^{\prime}}{\lambda
m^{1/6}}\right)(\lambda+C_{s,L}^{\prime\prime}t)$. Since this is independent
of $r$, this relation holds for all $t\in\mathcal{T}_{1}$. Consequently, the
regret incurred over the time instants in $\mathcal{T}_{1}$ can be bounded as

$\displaystyle\sum_{t\in\mathcal{T}_{1}}h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq\sum_{t\in\mathcal{T}_{1}}\left[2\tilde{\beta}+\frac{2\eta_{0}\beta_{t-1}}{\sqrt{t}}\right]$
$\displaystyle\leq
2\tilde{\beta}|\mathcal{T}_{1}|+2\eta_{0}\beta_{T}\sqrt{T}.$

We now consider a time instant in $\mathcal{T}_{2}$ or $\mathcal{T}_{3}$. Fix
any $r>1$ and $t\in\mathcal{T}_{2}(r)\cup\mathcal{T}_{3}(r)$ which implies
that $a_{t}\in\hat{A}_{r}(t)$. Consequently, $\mathbf{x}_{t,a_{t}}$ satisfies
the following relation:

$\displaystyle
f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t-1}^{(r-1)})+\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})$
$\displaystyle\geq\max_{a^{\prime}\in\hat{A}_{r}(t)}f(\mathbf{x}_{t,a^{\prime}};\mathbf{W}_{t-1}^{(r-1)})-\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a^{\prime}})$

Note that output of the neural net is based on the parameters evaluated during
the last time the neural net was trained, which we denote by
$t_{\texttt{fb}}$. In other words,
$f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t-1}^{(r-1)})=f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t_{\texttt{fb}}}^{(r-1)})$.
However, $\hat{\sigma}_{t-1}^{(r-1)}$ is evaluated using all the points in
$\Psi_{t-1}^{(r)}$. We can account for the discrepancy using Lemma 12 from
Abbasi-Yadkori et al. [2011] which states that for any two positive definite
matrices $\mathbf{A}\succeq\mathbf{B}\in\mathbb{R}^{d\times d}$ and
$\mathbf{x}\in\mathbb{R}^{d}$, we have
$\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\leq\mathbf{x}^{\top}\mathbf{B}\mathbf{x}\cdot\sqrt{\det(\mathbf{A})/\det(\mathbf{B})}$.
Using this result along with noting that
$\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a})=\mathbf{g}^{\top}(\mathbf{x}_{t,a};\mathbf{W}_{0})\mathbf{V}_{t-1}^{-1}\mathbf{g}(\mathbf{x}_{t,a};\mathbf{W}_{0})$,
$\hat{\sigma}_{t_{\texttt{fb}}}^{(r-1)}(\mathbf{x}_{t,a})=\mathbf{g}^{\top}(\mathbf{x}_{t,a};\mathbf{W}_{0})\mathbf{V}_{t_{\texttt{fb}}}^{-1}\mathbf{g}(\mathbf{x}_{t,a};\mathbf{W}_{0})$
and $\mathbf{V}_{t-1}\succeq\mathbf{V}_{\texttt{fb}}$, we can conclude that
$\hat{\sigma}_{t_{\texttt{fb}}}^{(r-1)}(\mathbf{x}_{t,a})\leq\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a})\cdot\sqrt{\det(\mathbf{V}_{t-1})/\det(\mathbf{V}_{\texttt{fb}})}$.

For any batch such that
$\det(\mathbf{V}_{t})/\det(\mathbf{V}_{\texttt{fb}})\leq 4$, we have,
$\hat{\sigma}_{t_{\texttt{fb}}}^{(r-1)}(\mathbf{x}_{t,a})\leq
2\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a})$ for all $a\in[K]$.
Consequently,
$|h(\mathbf{x}_{t,a})-f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t_{\texttt{fb}}}^{(r-1)})|\leq\tilde{\beta}+\beta_{t_{\texttt{fb}}}\hat{\sigma}_{t_{\texttt{fb}}}^{(r-1)}(\mathbf{x}_{t,a})\leq\tilde{\beta}+2\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a})$.
Thus, for any such batch and a time instant $t\in\mathcal{T}_{2}(r)$, using
Theorem 2 we have,

$\displaystyle
f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t-1}^{(r-1)})+\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})$
$\displaystyle\geq\max_{a^{\prime}\in\hat{A}_{r}(t)}f(\mathbf{x}_{t,a^{\prime}};\mathbf{W}_{t-1}^{(r-1)})-\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a^{\prime}})$
$\displaystyle\implies
f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t_{\texttt{fb}}}^{(r-1)})+\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})$
$\displaystyle\geq
f(\mathbf{x}_{t,a^{*}_{t}};\mathbf{W}_{t_{\texttt{fb}}}^{(r-1)})-\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a^{*}})$
$\displaystyle\implies
h(\mathbf{x}_{t,a_{t}})+3\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})+\tilde{\beta}$
$\displaystyle\geq
h(\mathbf{x}_{t,a^{*}})-3\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(x_{t,a^{*}})-\tilde{\beta}.$

Since $\hat{A}_{r}(t)\subseteq\hat{A}_{r-1}(t)$,
$\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a})\leq\tilde{\sigma}_{t-1}^{(r-1)}\leq\sigma_{0}2^{1-r}$
for all $a\in\hat{A}_{r}(t)$. Thus,

$\displaystyle h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq
3\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a})+3\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a^{*}_{t}})+2\tilde{\beta}\leq
12\sigma_{0}\beta_{t-1}\cdot 2^{-r}+2\tilde{\beta}.$

Similarly, for a time instant $t\in\mathcal{T}_{3}(r)$, we have,

$\displaystyle h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq
f(\mathbf{x}_{t,a^{*}_{t}};\mathbf{W}_{t_{\texttt{fb}}}^{(r-1)})+\tilde{\beta}+2\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a^{*}_{t}})-f(\mathbf{x}_{t,a_{t}};\mathbf{W}_{t_{\texttt{fb}}}^{(r-1)})+\tilde{\beta}+2\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq
3\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a^{*}_{t}})+3\beta_{t-1}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a})+2\tilde{\beta}\leq
12\sigma_{0}\beta_{t-1}\cdot 2^{-r}+2\tilde{\beta}$ $\displaystyle\leq
12\sigma_{0}\beta_{t-1}\cdot 2^{-r}+2\tilde{\beta},$

where the first step uses Theorem 2 and the last step uses the fact that
$\mathbf{x}_{t,a_{t}}\in\hat{A}_{r-1}(t)$. For any
$t\in\mathcal{T}_{2}(1)\cup\mathcal{T}_{3}(1)$, we use the trivial bound
$h(\mathbf{x}_{t,a^{*}})-h(\mathbf{x}_{t,a_{t}})\leq 2$.

We now bound $|\mathcal{T}_{2}(r)|$ using similar techniques outlined in Valko
et al. [2013], Auer [2002]. Fix any $r\geq 1$. Using the fact that for all
$t\in\mathcal{T}_{2}(r)$,
$\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})\geq\sigma_{0}2^{-r}$ and the
bound on the sum of posterior standard deviations from Chowdhury and Gopalan
[2017, Lemma 4], we can write

$\displaystyle\sigma_{0}2^{-r}|\mathcal{T}_{2}(r)|$
$\displaystyle\leq\sum_{t\in
T_{2}(r)}\hat{\sigma}_{t-1}^{(r-1)}(\mathbf{x}_{t,a_{t}})\leq\sqrt{8|\mathcal{T}_{2}(r)|(\lambda\Gamma_{k}(T)+1)}$
$\displaystyle\implies|\mathcal{T}_{2}(r)|$ $\displaystyle\leq
2^{r}\sqrt{8\sigma_{0}^{-2}|\mathcal{T}_{2}(r)|(\lambda\Gamma_{k}(T)+1)}$

We also used the fact that the information gain of the kernel induced by the
finite neural net is close to that of NTK for sufficiently large $m$ [Kassraie
and Krause, 2022, Lemma D.5]. This also provides a guideline for setting the
length of the exploration sequence. Specifically, we can set $\alpha_{0}$ such
that $|\mathcal{T}_{3}(r)|$ also satisfies $|\mathcal{T}_{3}(r)|\leq
2^{r}\sqrt{8\sigma_{0}^{-2}|\mathcal{T}_{3}(r)|(\lambda\Gamma_{k}(T)+1)}$, or
equivalently, $\alpha_{0}=\mathcal{O}(\Gamma_{k}(T))$. In general, we have
$|\mathcal{T}_{3}(r)|\leq\alpha_{0}4^{r}\implies|\mathcal{T}_{3}(r)|\leq
2^{r}\sqrt{\alpha_{0}|\mathcal{T}_{3}(r)|}$.

We can use these conditions to bound the regret incurred for
$t\in\mathcal{T}_{2}^{\prime}$, the subset of $\mathcal{T}_{2}$ that consists
only of batches that satisfy the determinant condition. We have,

$\displaystyle\sum_{t\in\mathcal{T}_{2}^{\prime}}h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq\sum_{r=1}^{R}\sum_{t\in\mathcal{T}_{2}^{\prime}(r)}h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq|\mathcal{T}_{2}(1)|+\sum_{r=2}^{R}\sum_{t\in\mathcal{T}_{2}(r)}\left[12\sigma_{0}\beta_{t-1}\cdot
2^{-r}+2\tilde{\beta}\right]$
$\displaystyle\leq|\mathcal{T}_{2}(1)|+\sum_{r=2}^{R}\left[12\sigma_{0}\beta_{t-1}\cdot
2^{-r}+2\tilde{\beta}\right]|\mathcal{T}_{2}(r)|$
$\displaystyle\leq|\mathcal{T}_{2}(1)|+2\tilde{\beta}|\mathcal{T}_{2}|+\sum_{r=2}^{R}(12\sigma_{0}\beta_{t-1}\cdot
2^{-r})\cdot
2^{r}\sqrt{8\sigma_{0}^{-2}|\mathcal{T}_{2}(r)|(\lambda\Gamma_{k}(T)+1)}$
$\displaystyle\leq|\mathcal{T}_{2}(1)|+2\tilde{\beta}|\mathcal{T}_{2}|+12\beta_{T}\sqrt{8|\mathcal{T}_{2}|R(\lambda\Gamma_{k}(T)+1)},$

where we used Cauchy-Schwarz inequality in the last step. Using a similar
analysis, we can bound the regret incurred for $t\in\mathcal{T}_{3}^{\prime}$,
which is defined similarly to $\mathcal{T}_{2}^{\prime}$, to obtain,

$\displaystyle\sum_{t\in\mathcal{T}_{3}^{\prime}}h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq|\mathcal{T}_{3}(1)|+2\tilde{\beta}|\mathcal{T}_{3}|+12\beta_{T}\sqrt{8|\mathcal{T}_{3}|R\alpha_{0}}.$

Now, for batches for which the determinant condition is not satisfied, the
regret incurred in any batch corresponding to subset index $r$ can be
trivially bounded as $q_{r}$. We show that the number of such batches is
bounded by $\mathcal{O}(\Gamma_{k}(T))$. Fix a $r\geq 1$. Let there be $B_{r}$
such batches for which the determinant condition is not satisfied and
$\mathcal{T}^{\prime}(r)$ denote the set of time instants at which such
batches begin. Then,

$\displaystyle
4^{B_{r}}\leq\prod_{t\in\mathcal{T}^{\prime}(r)}\frac{\det(\mathbf{V}_{t+q_{r}})}{\det(\mathbf{V}_{t})}\leq\frac{\det(\mathbf{V}_{T+1})}{\det(\lambda\mathbb{I})}.$

Since $\log\left(\det(\mathbf{V}_{T+1})/\det(\lambda\mathbb{I})\right)$ is
$\mathcal{O}(\Gamma_{k}(T))$, we can conclude that $B_{r}$ is also
$\mathcal{O}(\Gamma_{k}(T))$. Thus, regret incurred in all such batches can be
bounded as $\mathcal{O}(\max_{r}q_{r}\Gamma_{k}(T)\log T)$ as there are
$R=\log T$ batches.

We can combine the two cases to obtain the regret incurred over
$\mathcal{T}_{2}$ and $\mathcal{T}_{3}$ as

$\displaystyle\sum_{t\in\mathcal{T}_{2}}h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq|\mathcal{T}_{2}(1)|+2\tilde{\beta}|\mathcal{T}_{2}|+12\beta_{T}\sqrt{8|\mathcal{T}_{2}|R(\lambda\Gamma_{k}(T)+1)}+\mathcal{O}(\max_{r}q_{r}\Gamma_{k}(T)\log
T)$
$\displaystyle\sum_{t\in\mathcal{T}_{3}}h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq|\mathcal{T}_{3}(1)|+2\tilde{\beta}|\mathcal{T}_{3}|+12\beta_{T}\sqrt{8|\mathcal{T}_{3}|R\alpha_{0}}+\mathcal{O}(\max_{r}q_{r}\Gamma_{k}(T)\log
T).$

The overall regret is now obtained by adding the regret incurred over
$\mathcal{T}_{1}$, $\mathcal{T}_{2}$ and $\mathcal{T}_{3}$. We have,

$\displaystyle R(T)$
$\displaystyle=\sum_{t=1}^{T}h(\mathbf{x}_{t,a^{*}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle=\sum_{t\in\mathcal{T}_{1}}h(\mathbf{x}_{t,a^{*}})-h(\mathbf{x}_{t,a_{t}})+\sum_{t\in\mathcal{T}_{2}}h(\mathbf{x}_{t,a^{*}})-h(\mathbf{x}_{t,a_{t}})+\sum_{t\in\mathcal{T}_{3}}h(\mathbf{x}_{t,a^{*}})-h(\mathbf{x}_{t,a_{t}})$
$\displaystyle\leq
2\tilde{\beta}(|\mathcal{T}_{1}|+|\mathcal{T}_{2}|+|\mathcal{T}_{3}|)+|\mathcal{T}_{2}(1)|+|\mathcal{T}_{3}(1)|+2\eta_{0}\beta_{T}\sqrt{T}+12\beta_{T}\sqrt{8|\mathcal{T}_{3}|R\alpha_{0}}$
$\displaystyle\ \ \ \ \
+12\beta_{T}\sqrt{8|\mathcal{T}_{2}|R(\lambda\Gamma_{k}(T)+1)}+\mathcal{O}(\max_{r}q_{r}\Gamma_{k}(T)\log
T)$ $\displaystyle\leq
2\tilde{\beta}T+2\eta_{0}\beta_{T}\sqrt{T}+12\beta_{T}\sqrt{8T(\lambda\Gamma_{k}(T)+1+\alpha_{0})}+\mathcal{O}(\max_{r}q_{r}\Gamma_{k}(T)\log
T),$

where we again use the Cauchy Schwarz inequality in the last step along with
the fact that $|\mathcal{T}_{2}(1)|$ and $|\mathcal{T}_{3}(1)|$ satisfy
$\mathcal{O}(\Gamma_{k}(T))$. Since $m\geq\mathrm{poly}(T)$, the first term
$\tilde{\beta}{T}$ is $\mathcal{O}(1)$ and using the values of $J$ and $\eta$
specified in Assumption 2 along with the bound on $m$, we have
$\beta_{T}\leq\beta\leq 2S+\nu\sqrt{2\lambda^{-1}\log(1/\delta)}$.
Consequently, the regret incurred by NeuralGCB satisfies
$\mathcal{O}(\sqrt{T\Gamma_{k}(T)\log(1/\delta)}+\sqrt{T\Gamma_{k}(T)}+\sqrt{T\log(1/\delta)}+\max_{r}q_{r}\Gamma_{k}(T)\log
T)$.

The above analysis carries through almost as is for the case of adaptive batch
sizes. Since the batches always satisfy the determinant condition with $q_{r}$
instead of $4$, we do not need to separately consider the case where the
determinant condition is not met. Using the same steps as above, we can
conclude that the regret incurred by NeuralGCB when run with adaptive step
sizes is
$\mathcal{O}(\sqrt{T\Gamma_{k}(T)\log(1/\delta)}\cdot\max_{r}\sqrt{q_{r}})$.
Thus for the adaptive case, we incur an additional multiplicative factor. This
can be explained by the fact that in the adaptive batch setting, the number of
times the neural nets are retrained is $\mathcal{O}(\Gamma_{k}(T))$. However,
in the fixed batch setting, even if we use the optimal batch size of
$\sqrt{T/\Gamma_{k}(T)}$, we end up retraining the neural nets about
$\mathcal{O}(\sqrt{T\Gamma_{k}(T)})$ times, which is more than in the case of
the adaptive batch setting. The more frequent of retraining of neural nets
helps us achieve a tighter regret bound in the case of fixed batch setting.

##  Appendix E Empirical Studies

In this section, we provide further details of the setup used during our
experiments. For completeness, we first restate the construction and
preprocessing of the datasets followed by the experimental setup. We then
provide the complete array of results for the all the algorithm on different
datasets.

###  E.1 Datasets

For each of the synthetic datasets, we construct a contextual bandit problem
with a feature dimension of $d=10$ and $K=4$ actions per context running over
a time horizon of $T=2000$ rounds. The set of context vectors
$\\{\\{\mathbf{x}_{t,a}\\}_{a=1}^{K}\\}_{t=1}^{T}$ are drawn uniformly from
the unit sphere. Similar to Zhou et al. [2020], we consider the following
three reward functions:

$\displaystyle h_{1}(\mathbf{x})=4|\mathbf{a}^{\top}\mathbf{x}|^{2};\quad\
h_{2}(\mathbf{x})=4\sin^{2}(\mathbf{a}^{\top}\mathbf{x});\quad\
h_{3}(\mathbf{x})=\|\mathbf{A}\mathbf{x}\|_{2}.$ (27)

For the above functions, the vector $\mathbf{a}$ is drawn uniformly from the
unit sphere and each entry of matrix $\mathbf{A}$ is randomly generated from
$\mathcal{N}(0,0.25)$.

We also consider two real datasets for classification namely Mushroom and
Statlog (Shuttle), both of which are available on the UCI repository [Dua and
Graff, 2017].

##### Mushroom:

The Mushroom dataset consists of $8124$ samples with $22$ features where each
data point is labelled as an edible or poisonous mushroom, resulting in a
binary classification problem. For the purpose of the experiments, we carry
out some basic preprocessing on this dataset. We drop the attributed labeled
“veil-type" as it is the same for all the datapoints resulting in a $d=21$
dimensional feature vector. Furthermore, we randomly select $1000$ points from
each class to create a smaller dataset of size $2000$ to run the experiements.

##### Statlog:

The Statlog (Shuttle) dataset consists of $58000$ entries with $d=7$
attributes (we do not consider time as an attribute) each. The original
dataset is divided into $7$ classes. Since the data is skewed, we convert this
into a binary classification problem by combining classes. In particular, we
combine the five smallest classes, namely, $2,3,5,6,7$ and combine them to
form a single class and drop class $4$ resulting in a binary classification
problem, with points labelled as $1$ forming the first class and ones with
labels in $\\{2,3,5,6,7\\}$ forming the second. Once again, we select a subset
of $2000$ points by randomly choosing $1000$ points from each class to use for
the experiments. Lastly, we normalize the features of this dataset.

The classification problem is then converted into a contextual bandit problem
using techniques outlined in Li et al. [2010], which is also adopted in Zhou
et al. [2020] and Gu et al. [2021]. Specifically, each datapoint in the
dataset $(\mathbf{x},y)\in\mathbb{R}^{d}\times\mathbb{R}$ is transformed into
$K$ vectors of the form
${\mathbf{x}}^{(1)}=(\mathbf{x},\mathbf{0},\dots,\mathbf{0})\dots,{\mathbf{x}}^{(K)}=(\mathbf{0},\dots,\mathbf{0},\mathbf{x})\in\mathbb{R}^{Kd}$
corresponding to the $K$ actions associated with context $\mathbf{x}$. Here
$K$ denotes the number of classes in the original classification problem. The
reward function is set to $h({\mathbf{x}}^{(k)})=\mathbbm{1}\\{y=k\\}$, that
is, the agent receives a reward of $1$ if they classify the context correctly
and $0$ otherwise. As mentioned above, we have $d=21$ for Mushroom dataset and
$d=7$ for the Shuttle dataset and $K=2$ for both of them.

###  E.2 Experimental Setting

For all the experiments, the rewards are generated by adding zero mean
Gaussian noise with a standard deviation of $0.1$ to the reward function. All
the experiments are run for a time horizon of $T=2000$. We report the regret
averaged over $10$ Monte Carlo runs with different random seeds along with an
error bar of one standard deviation on either side. For all the datasets, we
generate new rewards for each Monte Carlo run by changing the noise.
Furthermore, for the real datasets, we also shuffle the context vectors for
each Monte Carlo run.

##### Setting the hyperparameters:

For all the algorithms, the parameter $\nu$, the standard deviation proxy for
the sub-Gaussian noise, to $0.1$, the standard deviation of the Gaussian noise
added. Also, the RKHS norm of the reward, $S$ to $4$ for synthetic functions,
and $1$ for real datasets in all the algorithms. For all the experiments, we
perform a grid search for $\lambda$ and $\eta$ over $\\{0.05,0.1,0.5\\}$ and
$\\{0.001,0.01,0.1\\}$, respectively, for each algorithm and choose the best
ones for the corresponding algorithm and reward function. The exploration
parameter $\beta_{t}$ is set to the value prescribed by each algorithm. For
NeuralUCB and NeuralTS, the prescribed value for the exploration parameter in
the original work was given as:

$\displaystyle\beta_{t}$
$\displaystyle=\beta_{0}\left(\nu\sqrt{\log\left(\frac{\det(\mathbf{V}_{t})}{\det(\lambda\mathbb{I})}\right)+C_{2}m^{-1/6}\sqrt{\log
m}L^{4}t^{5/3}\lambda^{-1/6}+2\log(1/\delta)}+S\right)$
$\displaystyle+(\lambda+C_{3}tL)\left[(1-\eta
m\lambda)^{J/2}\sqrt{t/\lambda}+m^{-1/6}\sqrt{\log
m}L^{7/2}t^{5/3}\lambda^{-5/3}(1+\sqrt{t/\lambda})\right],$

where $\beta_{0}=\sqrt{1+C_{1}m^{-1/6}\sqrt{\log
m}L^{4}t^{7/6}\lambda^{-7/6}}$. We ignore the smaller order terms and set
$\beta_{t}=2S+\nu\sqrt{\log\left(\frac{\det(\mathbf{V}_{t})}{\det(\lambda\mathbb{I})}\right)+2\log(1/\delta)}$
as $(\lambda+C_{3}tL)(1-\eta m\lambda)^{J/2}\sqrt{t/\lambda}\leq S$ for given
choice of parameters as shown in Zhou et al. [2020]. For NeuralGCB and
SupNNUCB, we apply the same process of ignoring the smaller order terms and
bounding the additional constant term by $S$ to obtain
$\beta_{t}=2S+\nu\sqrt{\frac{2}{\lambda}\log(1/\delta)}$, which is used in the
algorithms. Also for NeuralGCB, $\eta_{0}$ was set to $0.2$ and $\alpha_{0}$
to $20\log T$, as suggested in Sec. D, for all experiments. The number of
epochs is set to $200$ for synthetic datasets and Mushroom, and to $400$ for
Statlog.

##### Neural Net architecture:

We consider a 2 layered neural net as described in Equation (2) for all the
experiments. We perform two different sets of experiments with two different
activation functions, namely $\sigma_{1}$ (or equivalently, ReLU) and
$\sigma_{2}$. For the experiments with $\sigma_{1}$ as the activation, we set
the number of hidden neurons to $m=20$ and $m=50$ for synthetic and real
datasets respectively. For those with $\sigma_{2}$, $m$ is set to $30$ and
$80$ for synthetic and real datasets, respectively.

##### Training Schedule:

For the experiments with sequential algorithms, we retrain the neural nets at
every step, including NeuralGCB. For the batched algorithms, we consider a
variety of training schedules. Particularly, for each setting (i.e., dataset
and activation function) we consider two fixed and two adaptive batch size
training schedules, which are denoted by $F1,F2$ and $A1,A2$ respectively. We
specify the training schedules below for different dataset and activation
functions beginning with those for $\sigma_{1}$ (ReLU). These were chosen to
ensure that both algorithms have roughly the same running time to allow for a
fair comparison.

  1. 1.

For Batched NeuralUCB run on a synthetic function:

     * •

$F1$: 200 batches, or equivalently retrain after every $10$ steps.

     * •

$F2$: 300 batches, or equivalently retrain after every $6-7$ steps.

     * •

$A1$: $q=2$

     * •

$A2$: $q=3$

  2. 2.

For Batched NeuralUCB run on Mushroom:

     * •

$F1$: 100 batches, or equivalently retrain after every $20$ steps.

     * •

$F2$: 200 batches, or equivalently retrain after every $10$ steps.

     * •

$A1$: $q=500$

     * •

$A2$: $q=700$

  3. 3.

For Batched NeuralUCB run on Shuttle:

     * •

$F1$: 100 batches, or equivalently retrain after every $20$ steps.

     * •

$F2$: 200 batches, or equivalently retrain after every $10$ steps.

     * •

$A1$: $q=5$

     * •

$A2$: $q=10$

  4. 4.

For NeuralGCB run on a synthetic function:

     * •

$F1$: $q_{1}=4,q_{2}=20,q_{r}=40$ for $r\geq 3$ (i.e., retrain after $q_{r}$
steps)

     * •

$F2$: $q_{1}=2,q_{2}=10,q_{r}=20$ for $r\geq 3$.

     * •

$A1$: $q_{1}=1.2,q_{2}=1.8,q_{r}=2.7$ for $r\geq 3$.

     * •

$A2$: $q_{1}=1.5,q_{2}=2.25,q_{r}=3.375$ for $r\geq 3$.

  5. 5.

For NeuralGCB run on Mushroom:

     * •

$F1$: $q_{1}=20,q_{2}=40,q_{r}=80$ for $r\geq 3$ (i.e., retrain after $q_{r}$
steps)

     * •

$F2$: $q_{1}=10,q_{2}=20,q_{r}=40$ for $r\geq 3$.

     * •

$A1$: $q_{1}=300,q_{2}=1200,q_{r}=4800$ for $r\geq 3$.

     * •

$A2$: $q_{1}=500,q_{2}=2000,q_{r}=8000$ for $r\geq 3$.

  6. 6.

For NeuralGCB run on Shuttle:

     * •

$F1$: $q_{1}=20,q_{2}=40,q_{r}=80$ for $r\geq 3$ (i.e., retrain after $q_{r}$
steps)

     * •

$F2$: $q_{1}=10,q_{2}=20,q_{r}=40$ for $r\geq 3$.

     * •

$A1$: $q_{1}=5,q_{2}=12.5,q_{r}=31.25$ for $r\geq 3$.

     * •

$A2$: $q_{1}=10,q_{2}=25,q_{r}=62.5$ for $r\geq 3$.

(a) $h_{1}(x)$ with $\sigma_{1}(x)$

(b) $h_{1}(x)$ with $\sigma_{2}(x)$

(c) $h_{1}(x)$ with fixed batch and $\sigma_{1}(x)$

(d) $h_{1}(x)$ with adaptive batch and $\sigma_{1}(x)$

(e) $h_{1}(x)$ with fixed batch and $\sigma_{2}(x)$

(f) $h_{1}(x)$ with adaptive batch and $\sigma_{2}(x)$

Figure 2: Plots with reward function $h_{1}(x)$

(a) $h_{2}(x)$ with $\sigma_{1}(x)$

(b) $h_{2}(x)$ with $\sigma_{2}(x)$

(c) $h_{2}(x)$ with fixed batch and $\sigma_{1}(x)$

(d) $h_{2}(x)$ with adaptive batch and $\sigma_{1}(x)$

(e) $h_{2}(x)$ with fixed batch and $\sigma_{2}(x)$

(f) $h_{2}(x)$ with adaptive batch and $\sigma_{2}(x)$

Figure 3: Plots with reward function $h_{2}(x)$

Similarly, for $\sigma_{2}$, the training schedules are given as follows:

  1. 1.

For Batched NeuralUCB run on a synthetic function:

     * •

$F1$: 200 batches, or equivalently retrain after every $10$ steps.

     * •

$F2$: 300 batches, or equivalently retrain after every $6-7$ steps.

     * •

$A1$: $q=3$

     * •

$A2$: $q=4$

  2. 2.

For Batched NeuralUCB run on Mushroom:

     * •

$F1$: 100 batches, or equivalently retrain after every $20$ steps.

     * •

$F2$: 200 batches, or equivalently retrain after every $10$ steps.

     * •

$A1$: $q=500$

     * •

$A2$: $q=700$

  3. 3.

For Batched NeuralUCB run on Shuttle:

     * •

$F1$: 50 batches, or equivalently retrain after every $40$ steps.

     * •

$F2$: 100 batches, or equivalently retrain after every $20$ steps.

     * •

$A1$: $q=5$

     * •

$A2$: $q=10$

  4. 4.

For NeuralGCB run on a synthetic function:

     * •

$F1$: $q_{1}=4,q_{2}=20,q_{r}=40$ for $r\geq 3$ (i.e., retrain after $q_{r}$
steps)

     * •

$F2$: $q_{1}=2,q_{2}=10,q_{r}=20$ for $r\geq 3$.

     * •

$A1$: $q_{1}=1.2,q_{2}=1.8,q_{r}=2.7$ for $r\geq 3$.

     * •

$A2$: $q_{1}=1.5,q_{2}=2.25,q_{r}=3.375$ for $r\geq 3$.

  5. 5.

For NeuralGCB run on Mushroom:

     * •

$F1$: $q_{1}=10,q_{2}=30,q_{r}=60$ for $r\geq 3$ (i.e., retrain after $q_{r}$
steps)

     * •

$F2$: $q_{1}=10,q_{2}=20,q_{r}=40$ for $r\geq 3$.

     * •

$A1$: $q_{1}=300,q_{2}=1200,q_{r}=4800$ for $r\geq 3$.

     * •

$A2$: $q_{1}=500,q_{2}=2000,q_{r}=8000$ for $r\geq 3$.

  6. 6.

For NeuralGCB run on Shuttle:

     * •

$F1$: $q_{1}=5,q_{2}=12,q_{r}=31$ for $r\geq 3$ (i.e., retrain after $q_{r}$
steps)

     * •

$F2$: $q_{1}=5,q_{2}=10,q_{r}=20$ for $r\geq 3$ (i.e., retrain after $q_{r}$
steps)

     * •

$A1$: $q_{r}=3$ for all $r$

     * •

$A2$: $q_{r}=4$ for all $r$

We use this notation of $F1,F2,A1$ and $A2$ to refer to the training schedules
in the plots shown in the next section.

(a) $h_{3}(x)$ with $\sigma_{1}(x)$

(b) $h_{3}(x)$ with $\sigma_{2}(x)$

(c) $h_{3}(x)$ with fixed batch and $\sigma_{1}(x)$

(d) $h_{3}(x)$ with adaptive batch and $\sigma_{1}(x)$

(e) $h_{3}(x)$ with fixed batch and $\sigma_{2}(x)$

(f) $h_{3}(x)$ with adaptive batch and $\sigma_{2}(x)$

Figure 4: Plots with reward function $h_{3}(x)$

###  E.3 Plots

In this section, we plot the performance of NeuralGCB against several
baselines for different experimental setups and reward functions. For each
reward function, we plot the following $6$ figures:

  * •

Fig. (a): We plot the cumulative regret against time (number of rounds) for
various baselines for the case where the activation function of the underlying
neural net is $\sigma_{1}$, or equivalently, ReLU.

  * •

Fig (b): We plot the cumulative regret against time (number of rounds) for
various baselines for the case where the activation function of the underlying
neural net is $\sigma_{2}$.

  * •

Fig (c)-(f): We compare the regret and running time (in seconds) between the
batched and the sequential versions of NeuralUCB and NeuralGCB. We plot the
regret incurred against time taken (running time, in seconds) for Batched-
NeuralUCB (BNUCB), (Batched)-NeuralGCB (BNGCB), NeuralUCB (NUCB-seq),
(Sequential) NeuralGCB (NGCB-seq) under different training schedules for $10$
different runs. In particular, in (c) and (e), we consider fixed batch sizes
with $\sigma_{1}$ and $\sigma_{2}$ as activation functions respectively and in
(d) and (f) with consider adaptive batch sizes with $\sigma_{1}$ and
$\sigma_{2}$ as activation functions respectively. The batch sizes used in the
plots are described in the previous section.

(a) Mushroom with $\sigma_{1}(x)$

(b) Mushroom with $\sigma_{2}(x)$

(c) Mushroom with fixed batch and $\sigma_{1}(x)$

(d) Mushroom with adaptive batch and $\sigma_{1}(x)$

(e) Mushroom with fixed batch and $\sigma_{2}(x)$

(f) Mushroom with adaptive batch and $\sigma_{2}(x)$

Figure 5: Plots for the dataset Mushroom

(a) Statlog with $\sigma_{1}(x)$

(b) Statlog with $\sigma_{2}(x)$

(c) Statlog with fixed batch and $\sigma_{1}(x)$

(d) Statlog with adaptive batch and $\sigma_{1}(x)$

(e) Statlog with fixed batch and $\sigma_{2}(x)$

(f) Statlog with adaptive batch and $\sigma_{2}(x)$

Figure 6: Plots for the dataset Statlog (Shuttle)

From the above figures, it is evident that NeuralGCB outperforms all other
existing algorithms on variety of datasets, including both synthetic and real
world datasets. Moreover, the conclusion holds equally well for different
activation functions, further bolstering the practical efficiency of the
proposed algorithm. Additionally, it can be noted that the regret incurred by
the algorithms in experiments with $\sigma_{2}$ as the activation is less than
that for the experiments with $\sigma_{1}$ as the activation, thereby
demonstrating the effect of smooth kernels on the performance of the
algorithms in practice.

Lastly, the extensive study with different training schedules shows that
batched version performs almost as well as the fully sequential version in
terms of regret on all the datasets while having a considerably smaller
running time. It can be noted from the plots that NeuralGCB has a superior
performance compared to Batched-NeuralUCB in terms of regret for comparable
running times on different datasets and with different activation functions
which further strengthens the case of NeuralGCB as a practically efficient
algorithm.

All the experiments were carried out using Python3 on a computer (CPU) with 12
GB RAM and Intel i7 processor (3.4 GHz) with an overall compute time of around
250-300 hours.