$\eta_{t}\leq\eta_{\max}<\infty$ for all $t\in[1\colon T]$. $\blacksquare$

###  A.3 Radon-Nikodym Derivatives (Lemma A.3)

######  Lemma A.3 (Radon-Nikodym Derivatives).

For any $\beta_{t-1}\in{}^{d_{t-1}}$, conditional on any $S_{t}^{(i)}$,
$\mu(\,\cdot\,)\triangleq\pi_{t}\big{(}\,\cdot\,,S_{t}^{(i)};\beta_{t-1}\big{)}$
defines a probability measure on the sigma-algebra $\sigma(A_{t}^{(i)})$. Also
conditional on any $\mathcal{H}_{t-1}^{(1:n)}$ and $S_{t}^{(i)}$, the policy
$\nu(\,\cdot\,)\triangleq\hat{\pi}_{t}^{(n)}\big{(}\,\cdot\,,S_{t}^{(i)}\big{)}$
defines a probability measure on the sigma-algebra $\sigma(A_{t}^{(i)})$.

Under Condition 2, conditionally on almost every $\mathcal{H}_{t-1}^{(1:n)}$
and $S_{t}^{(i)}$,
$g(\,\cdot\,)\triangleq\frac{\pi_{t}(\,\cdot\,,S_{t}^{(i)};\beta_{t-1})}{\hat{\pi}_{t}^{(n)}(\,\cdot\,,S_{t}^{(i)})}$
is a Radon-Nikodym derivative, i.e., for any measurable subset
$\bar{A}\subseteq\mathcal{A}$, conditionally on almost every
$\mathcal{H}_{t-1}^{(1:n)}$ and $S_{t}^{(i)}$,
$\mu(\bar{A})=\int_{\bar{A}}g~{}d\nu$.

Proof of Lemma A.3. We first show that that conditionally on almost every
$\mathcal{H}_{t-1}^{(1:n)}$ and $S_{t}^{(i)}$,
$\mu(\,\cdot\,)=\pi_{t}\big{(}\,\cdot\,,S_{t}^{(i)};\beta_{t-1}\big{)}$ is
absolutely continuous with respect to
$\nu(\,\cdot\,)=\hat{\pi}_{t}^{(n)}\big{(}\,\cdot\,,S_{t}^{(i)}\big{)}$.

By exploration Condition 2 we have that for any measurable subset measurable
subset $\bar{A}\subseteq\mathcal{A}$,
$\hat{\pi}_{t}^{(n)}\big{(}\bar{A},S_{t}^{(i)}\big{)}\geq\pi_{\min}>0$ a.s.
This means that for any measurable subset $\bar{A}\subseteq\mathcal{A}$,
$\hat{\pi}_{t}^{(n)}\big{(}\bar{A},S_{t}^{(i)}\big{)}\geq\pi_{\min}>0$
conditionally on almost every $\mathcal{H}_{t-1}^{(1:n)}$ and $S_{t}^{(i)}$.
Thus we have that conditional on almost every $\mathcal{H}_{t-1}^{(1:n)}$ and
$S_{t}^{(i)}$,
$\mu(\,\cdot\,)=\pi_{t}\big{(}\,\cdot\,,S_{t}^{(i)};\beta_{t-1}\big{)}$ is
absolutely continuous with respect to
$\nu(\,\cdot\,)=\hat{\pi}_{t}^{(n)}\big{(}\,\cdot\,,S_{t}^{(i)}\big{)}$.

Thus, for some function $g:\mathcal{A}\mapsto[0,\infty)$, conditionally on
almost every $\mathcal{H}_{t-1}^{(1:n)}$ and $S_{t}^{(i)}$,
$\mu(\bar{A})=\int_{\bar{A}}g~{}d\nu$ for any measurable subset
$\bar{A}\subseteq\sigma(\mathcal{A})$. This means that conditionally on almost
every $\mathcal{H}_{t-1}^{(1:n)}$ and $S_{t}^{(i)}$,

$\pi_{t}\big{(}\bar{A},S_{t}^{(i)};\beta_{t-1}\big{)}=\int_{\bar{A}}g~{}d\hat{\pi}_{t}^{(n)}(\,\cdot\,,S_{t}^{(i)}).$

For
$g(\,\cdot\,)=\frac{\pi_{t}(\,\cdot\,,S_{t}^{(i)};\beta_{t-1})}{\hat{\pi}_{t}^{(n)}(\,\cdot\,,S_{t}^{(i)})}$,
the above equality is satisfied. $\blacksquare$

###  A.4 Bracketing Numbers

####  A.4.1 Definition of Bracketing Numbers

Following the notation used in Chapter 19 of Van der Vaart [2000], for any
function class $\mathcal{F}$ of real-valued functions of
$\mathcal{H}_{T}^{(i)}$, we use
$N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}$ to
denote the number of brackets of size $\epsilon$ in
$L_{P}(\mathcal{P}_{\pi^{*}})$ norm needed to cover $\mathcal{F}$. Formally,
this means we can find $N_{\epsilon}\triangleq
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}$
number of brackets or pairs of real-valued functions of
$\mathcal{H}_{T}^{(i)}$,
$\big{\\{}(l_{k},u_{k})\big{\\}}_{k=1}^{N_{\epsilon}}$, such that (i) all
brackets together cover $\mathcal{F}$, i.e., for any $f\in\mathcal{F}$ we can
find some bracket $(l_{k},u_{k})$ such that $l_{k}(\mathcal{H}_{T}^{(i)})\leq
f(\mathcal{H}_{T}^{(i)})\leq u_{k}(\mathcal{H}_{T}^{(i)})$ a.s., and (ii) the
brackets have size less than $\epsilon$, i.e.,
$\mathbb{E}_{\pi_{2:T}^{*}}\big{[}\big{|}u_{k}(\mathcal{H}_{T}^{(i)})-l_{k}(\mathcal{H}_{T}^{(i)})\big{|}^{p}\big{]}^{1/p}<\epsilon$.
As done in Chapter 19 of Van der Vaart [2000], we assume that the bracketing
functions themselves also have finite $L_{p}(\mathcal{P}_{\pi^{*}})$ norm,
i.e., for any $\epsilon>0$ and $k\in[1\colon N_{\epsilon}]$,
$\mathbb{E}_{\pi_{2:T}^{*}}\big{[}|u_{k}(\mathcal{H}_{T}^{(i)})|^{p}\big{]}^{1/p}<\infty$
and
$\mathbb{E}_{\pi_{2:T}^{*}}\big{[}|l_{k}(\mathcal{H}_{T}^{(i)})|^{p}\big{]}^{1/p}<\infty$.

####  A.4.2 Product of Lipschitz Policy Functions are Lipschitz (Lemma A.4)

######  Lemma A.4 (Product of Lipschitz Policy Functions are Lipschitz).

Let $t\in[3\colon T-1]$. Under Condition 3 (Lipschitz Policy Function), for
any $\beta_{1:t-1},\tilde{\beta}_{1:t-1}\in B_{1:t-1}$,

$\bigg{|}\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}\big{)}-\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\tilde{\beta}_{t^{\prime}-1}\big{)}\bigg{|}\\\
\leq\bigg{\\{}\sum_{t^{\prime}=2}^{t}\dot{\pi}_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)}\big{)}\bigg{\\}}\big{\|}\beta_{1:t-1}-\tilde{\beta}_{1:t-1}\big{\|}_{2}\textnormal{~{}~{}~{}a.s.}$
(A.12)

Proof of Lemma A.4. Note that by telescoping series,

$\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}\big{)}-\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\tilde{\beta}_{t^{\prime}-1}\big{)}$
$=\left[\pi_{2}(A_{2}^{(i)},S_{2}^{(i)};\beta_{1})-\pi_{2}(A_{2}^{(i)},S_{2}^{(i)};\tilde{\beta}_{1})\right]\bigg{\\{}\prod_{t^{\prime}=3}^{t}\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1})\bigg{\\}}\\\
+\left\\{\pi_{2}(A_{2}^{(i)},S_{2}^{(i)};\tilde{\beta}_{1})\right\\}\left[\pi_{3}(A_{3}^{(i)},S_{3}^{(i)};\beta_{2})-\pi_{3}(A_{3}^{(i)},S_{3}^{(i)};\tilde{\beta}_{2})\right]\bigg{\\{}\prod_{t^{\prime}=4}^{t}\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1})\bigg{\\}}\\\
+\ldots\\\
+\bigg{\\{}\prod_{t^{\prime}=2}^{t-1}\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\tilde{\beta}_{t^{\prime}-1})\bigg{\\}}\left[\pi_{t}(A_{t}^{(i)},S_{t}^{(i)};\beta_{t-1})-\pi_{t}(A_{t}^{(i)},S_{t}^{(i)};\tilde{\beta}_{t-1})\right]$
$=\sum_{t^{\prime}=2}^{t}\bigg{\\{}\prod_{k=2}^{t^{\prime}-1}\pi_{k}(A_{k}^{(i)},S_{k}^{(i)};\tilde{\beta}_{k-1})\bigg{\\}}\left[\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1})-\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\tilde{\beta}_{t^{\prime}-1})\right]\\\
\bigg{\\{}\prod_{k=t^{\prime}+1}^{t}\pi_{k}(A_{k}^{(i)},S_{k}^{(i)};\beta_{k-1})\bigg{\\}}$

By slight abuse of notation, above we use
$\prod_{k=2}^{1}\pi_{k}(A_{k}^{(i)},S_{k}^{(i)};\tilde{\beta}_{k-1})=1$ and
$\prod_{k=t+1}^{t}\pi_{k}(A_{k}^{(i)},S_{k}^{(i)};\beta_{k-1})=1$.

Using the above result and triangle inequality,

$\bigg{|}\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}\big{)}-\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\tilde{\beta}_{t^{\prime}-1}\big{)}\bigg{|}$
$\leq\sum_{t^{\prime}=2}^{t}\bigg{|}\prod_{k=2}^{t^{\prime}-1}\pi_{k}(A_{k}^{(i)},S_{k}^{(i)};\tilde{\beta}_{k-1})\bigg{|}\left|\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1})-\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\tilde{\beta}_{t^{\prime}-1})\right|\\\
\bigg{|}\prod_{k=t^{\prime}+1}^{t}\pi_{k}(A_{k}^{(i)},S_{k}^{(i)};\beta_{k-1})\bigg{|}$

Since the terms $\big{|}\pi_{k}(A_{k}^{(i)},S_{k}^{(i)};\beta_{k-1})\big{|}$
and $\big{|}\pi_{k}(A_{k}^{(i)},S_{k}^{(i)};\tilde{\beta}_{k-1})\big{|}$ are
less than or equal to $1$ a.s.,

$\leq\sum_{t^{\prime}=2}^{t}\left|\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1})-\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\tilde{\beta}_{t^{\prime}-1})\right|$

By Condition 3 (Lipschitz Policy Function),

$\leq\sum_{t^{\prime}=2}^{t}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\big{\|}\beta_{t^{\prime}-1}-\tilde{\beta}_{t^{\prime}-1}\big{\|}_{2}$
$\leq\bigg{\\{}\sum_{t^{\prime}=2}^{t}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\bigg{\\}}\big{\|}\beta_{1:t-1}-\tilde{\beta}_{1:t-1}\big{\|}_{2}$

By the above argument, we have that

$\bigg{|}\prod_{t^{\prime}=2}^{t}\pi_{t}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1})-\prod_{t^{\prime}=2}^{t}\pi_{t}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\tilde{\beta}_{t^{\prime}-1})\bigg{|}\\\
\leq\bigg{\\{}\sum_{t^{\prime}=2}^{t}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\bigg{\\}}\big{\|}\beta_{1:t-1}-\tilde{\beta}_{1:t-1}\big{\|}_{2}\textnormal{~{}~{}~{}a.s.}~{}\blacksquare$
(A.13)

####  A.4.3 Bracketing Number for Product of Function Classes (Lemma A.5)

######  Lemma A.5 (Bracketing Number for Product of Function Classes).

Let $t\in[2\colon T-1]$. Let $\mathcal{F}$ be a class of real-valued functions
of $\mathcal{H}_{t}^{(i)}$ indexed by $\lambda\in L\subseteq{}^{d_{L}}$, i.e.,
$\mathcal{F}\triangleq\big{\\{}f(\,\cdot\,;\lambda):\lambda\in L\big{\\}}$.
Also let
$\Pi_{2:t}\triangleq\big{\\{}\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}\,\cdot\,;\beta_{t^{\prime}-1}\big{)}\textnormal{~{}~{}s.t.~{}~{}}\beta_{1:t-1}\in
B_{1:t-1}\big{\\}}$. Finally, also let

$\Pi_{2:t}\cdot\mathcal{F}\triangleq\bigg{\\{}\bigg{[}\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}\,\cdot\,;\beta_{t^{\prime}-1}\big{)}\bigg{]}f(\,\cdot\,;\lambda)\textnormal{~{}~{}s.t.~{}~{}}\beta_{1:t-1}\in
B_{1:t-1},\lambda\in L\bigg{\\}}.$

For any $p\geq 1$,
$N_{[~{}]}\big{(}\epsilon,\Pi_{2:t}\cdot\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
for all $\epsilon>0$ under the following conditions:

  1. (i)

Condition 3 (Lipschitz Policy Function) holds; if $p>2$, then Condition 3 must
hold for $\alpha=p-2$.

  2. (ii)

$N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
for all $\epsilon>0$.

  3. (iii)

There exists a real-valued, measurable function $F$ of $\mathcal{H}_{t}^{(i)}$
such that (a) $\big{|}f(\mathcal{H}_{t}^{(i)})\big{|}\leq
F(\mathcal{H}_{t}^{(i)})$ a.s. for all $f\in\mathcal{F}$, and (b)
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}F(\mathcal{H}_{t}^{(i)})\dot{\pi}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}^{p}\big{]}<\infty$
for all $t^{\prime}\in[2\colon t]$, where the functions
$\dot{\pi}_{t^{\prime}}$ are from Condition 3.

Furthermore, $\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon,\Pi_{2:t}\cdot\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon<\infty$
under the additional condition that

  1. (iv)

$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon<\infty$

Note that assumption (iv) above implies that assumption (ii) holds.

######  Remark 8 (Bracketing Number for the Product of Policy and Estimating
Functions).

Let $\mathcal{F}_{\Pi
c^{\top}\psi}\big{(}B_{1:T-1},K_{\theta})\triangleq\left\\{\big{[}\prod_{t=2}^{T}\pi_{t}(\,\cdot\,;\beta_{t-1})\big{]}c^{\top}\psi(\,\cdot\,;\theta\big{)}\textnormal{~{}s.t.~{}}\beta_{1:T-1}\in
B_{1:T-1},\theta\in K_{\theta}\right\\}$ for any compact set
$K_{\theta}\subseteq{}^{d_{\theta}}$ and any $c\in{}^{d_{\theta}}$. By Lemma
A.5, we have the following results:

  1. (a1)

Under Condition 3 and assumption (C3), $\mathcal{F}_{\Pi
c^{\top}\psi}\big{(}B_{1:T-1},K_{\theta})$ has a finite bracketing number,
i.e., that $N_{[~{}]}\left(\epsilon,~{}\mathcal{F}_{\Pi
c^{\top}\psi}(B_{1:T-1},K_{\theta}),~{}L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\right)<\infty$
for any $\epsilon>0$.

  2. (a2)

Under Condition 3 and assumption (N4), $\mathcal{F}_{\Pi
c^{\top}\psi}\big{(}B_{1:T-1},\Theta)$ has a finite bracketing integral, i.e.,
that $\int_{0}^{1}\sqrt{\log N_{[~{}]}\left(\epsilon,~{}\mathcal{F}_{\Pi
c^{\top}\psi}(B_{1:T-1},\Theta),~{}L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon<\infty$
for any $\epsilon>0$.

Let $\mathcal{F}_{\Pi
c^{\top}\phi_{t}}(B_{1:t-1},K_{t})\triangleq\left\\{\big{[}\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}(\,\cdot\,;\beta_{t^{\prime}-1})\big{]}c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}\big{)}\textnormal{~{}s.t.~{}}\beta_{1:t-1}\in
B_{1:t-1},\beta_{t}\in K_{t}\right\\}$ for any compact set
$K_{t}\subseteq{}^{d_{t}}$ and any $c\in{}^{d_{t}}$. By Lemma A.5, we have the
following results:

  1. (b1)

Under Condition 3 and assumption (CP3), $\mathcal{F}_{\Pi
c^{\top}\phi_{t}}\big{(}B_{1:t-1},K_{t})$ has a finite bracketing number,
i.e., that $N_{[~{}]}\left(\epsilon,~{}\mathcal{F}_{\Pi
c^{\top}\phi_{t}}(B_{1:t-1},K_{t}),~{}L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\right)<\infty$
for any $\epsilon>0$.

  2. (b2)

Under Condition 3 and assumption (NP1), $\mathcal{F}_{\Pi
c^{\top}\phi_{t}}\big{(}B_{1:t})$ has a finite bracketing integral, i.e., that
$\int_{0}^{1}\sqrt{\log N_{[~{}]}\left(\epsilon,~{}\mathcal{F}_{\Pi
c^{\top}\phi_{t}}(B_{1:t}),~{}L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon<\infty$
for any $\epsilon>0$.

Proof of Lemma A.5. For notational convenience, let

$\pi_{2:t}(\mathcal{H}_{t}^{(i)};\beta_{1:t-1})\triangleq\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}\big{)}.$

By Lemma A.4 (Product of Lipschitz Policy Function are Lipschitz) for any
$\beta_{1:t-1},\tilde{\beta}_{1:t-1}\in B_{1:t-1}$,

$\big{|}\pi_{2:t}(\mathcal{H}_{t}^{(i)};\beta_{1:t-1})-\pi_{2:t}(\mathcal{H}_{t}^{(i)};\beta_{1:t-1})\big{|}\leq\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)})\big{\|}\beta_{1:t-1}-\tilde{\beta}_{1:t-1}\big{\|}_{2}$
(A.14)

where
$\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)})\triangleq\sum_{t^{\prime}=2}^{t}\dot{\pi}_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)}\big{)}$.
Note that by assumption (i) (that Condition 3 holds),
$\|\dot{\pi}_{2:t}\|_{\mathcal{P}_{\pi^{*}},p}\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\big{[}|\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)})|^{p}\big{]}^{1/p}<\infty$.

Constructing bracketing functions that cover $\Pi_{2:t}$. Let $\epsilon>0$. We
now use the approach from Lemma 19.7 of Van der Vaart [2000]. Since
$B_{1:t-1}$ is compact, the size of $B_{1:t-1}$ in every fixed dimension is at
most $\textnormal{diam}(B_{1:t-1})<\infty$. We can cover $B_{1:t-1}$ with
$\big{[}\textnormal{diam}(B_{1:t-1})/\epsilon\big{]}^{d_{1:t-1}}$ or fewer
cubes of with edges of size $\epsilon$; recall that
$d_{1:t-1}\triangleq\sum_{t^{\prime}=1}^{t-1}d_{t^{\prime}}$. Let the
projection of the centers of each of these finitely many cubes onto
$B_{1:t-1}$ be the points $\mathcal{B}_{1:t-1}\subset B_{1:t-1}$. Note that
$|\mathcal{B}_{1:t-1}|=\big{[}\textnormal{diam}(B_{1:t-1})/\epsilon\big{]}^{d_{1:t-1}}$.
For each of these cubes, consider the circumscribed ball that contains the
cube; each of these balls has radius of $c\epsilon$ for some constant
$0<c<\infty$.

We now construct a collection of bracketing functions that cover $\Pi$. These
bracketing functions are

$\left\\{\left[\pi_{2:t}\big{(}\,\cdot\,;\beta_{1:t-1}\big{)}-\epsilon\dot{\pi}_{2:t}(\,\cdot\,),~{}\pi_{2:t}\big{(}\,\cdot\,;\beta_{1:t-1}\big{)}+\epsilon\dot{\pi}_{2:t}(\,\cdot\,)\right]\right\\}_{\beta_{1:t-1}\in\mathcal{B}_{1:t-1}}.$
(A.15)

The above brackets are of size at most
$2\epsilon\|\dot{\pi}_{2:t}\|_{\mathcal{P}_{\pi^{*}},p}$ in
$L_{p}(\mathcal{P}_{\pi^{*}})$ norm by assumption (i) (that Condition 3
holds).

We now discuss why the brackets from display (A.15) cover $\Pi_{2:t}$.
Consider any $\beta_{1:t-1}\in B_{1:t-1}$. Since the grid of cubes that cover
$B_{1:t-1}$ whose projected centers form the collection of points
$\mathcal{B}_{1:t-1}$ have edges of length $\epsilon$, thus there must exists
some $\beta_{1:t-1}^{(k)}\in\mathcal{B}_{1:t-1}$ such that
$\big{\|}\beta_{1:t-1}-\beta_{1:t-1}^{(k)}\big{\|}_{2}\leq\epsilon$. By
display (A.14),

$\pi_{2:t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{1:t-1}\big{)}\in\big{[}\pi_{2:t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{1:t-1}^{(k)}\big{)}-\epsilon\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)}),\pi_{2:t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{1:t-1}^{(k)}\big{)}+\epsilon\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)})\big{]}\textnormal{~{}~{}a.s.}$

Thus, we have that

$N_{[~{}]}\left(2\epsilon\|\dot{\pi}_{2:t}\|_{\mathcal{P}_{\pi^{*}},p},\Pi_{2:t}\cdot\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\right)\leq|\mathcal{B}_{1:t-1}|=\big{[}\textnormal{diam}(B_{1:t-1})/\epsilon\big{]}^{d_{1:t-1}}.$
(A.16)

Additionally, note that
$0\leq\pi_{2:t}(\mathcal{H}_{t}^{(i)};\beta_{1:t-1})\leq 1$ a.s. since this
function is a product of probabilities. Thus the brackets from display (A.15)
can be modified such that the bracketing functions are in $[0,1]$ w.p. $1$
while maintaining coverage of $\Pi_{2:t}$ and not increasing the size of the
brackets. Specifically, these brackets are:

$\big{\\{}\big{(}l_{\Pi,k},u_{\Pi,k}\big{)}\big{\\}}_{k=1}^{|\mathcal{B}_{1:t-1}|}\triangleq\\\
\bigg{\\{}\bigg{[}\max\big{\\{}0,\pi_{2:t}\big{(}\,\cdot\,;\beta_{1:t-1}\big{)}-\epsilon\pi_{2:t}(\,\cdot\,)\big{\\}},\min\big{\\{}1,\pi_{2:t}\big{(}\,\cdot\,;\beta_{1:t-1}\big{)}+\epsilon\pi_{2:t}(\,\cdot\,)\big{\\}}\bigg{]}\bigg{\\}}_{\beta_{1:t-1}\in\mathcal{B}_{1:t-1}}.$
(A.17)

Constructing bracketing functions that cover $\Pi_{2:t}\cdot\mathcal{F}$. By
assumption (ii), we can find $N_{\mathcal{F},\epsilon}\triangleq
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
bracketing functions which cover $\mathcal{F}$. We will call these bracketing
functions
$\big{\\{}\big{[}l_{\mathcal{F},k},u_{\mathcal{F},k}\big{]}\big{\\}}_{k=1}^{N_{\mathcal{F},\epsilon}}$.
We now show that we can construct a finite collection of bracketing functions
which cover $\Pi_{2:t}\cdot\mathcal{F}$ using the bracketing functions for
$\mathcal{F}$ and $\Pi_{2:t}$.

Consider any function
$\pi_{2:t}(\,\cdot\,;\beta_{1:t-1})f(\,\cdot\,)\in\Pi_{2:t}\cdot\mathcal{F}$.

  * •

From display (A.17), we can find some bracket
$\big{[}l_{\Pi,k},u_{\Pi,k}\big{]}$ for $k\in[1\colon|\mathcal{B}_{1:t-1}|]$
such that $0\leq
l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq\pi_{2:t}(\mathcal{H}_{t}^{(i)};\beta_{1:t-1})\leq
u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq 1$ a.s.

  * •

Additionally, we can find some bracket
$\big{[}l_{\mathcal{F},j},u_{\mathcal{F},j}\big{]}$ for $k\in[1\colon
N_{\mathcal{F},\epsilon}]$ such that
$l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\leq f(\mathcal{H}_{t}^{(i)})\leq
u_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})$ a.s.

Now note the following observations for any particular
$\mathcal{H}_{t}^{(i)}$:

  * •

If for a particular $\mathcal{H}_{t}^{(i)}$, $f(\mathcal{H}_{t}^{(i)})\geq 0$,
then since $0\leq l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq
u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq 1$, then

$l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\leq\pi_{2:t}(\mathcal{H}_{t}^{(i)};\beta_{1:t-1})f(\mathcal{H}_{t}^{(i)})\leq
u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
u_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)}).$

  * •

If for a particular $\mathcal{H}_{t}^{(i)}$, $f(\mathcal{H}_{t}^{(i)})<0$,
then since $0\leq l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq
u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq 1$, then

$u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\leq\pi_{2:t}(\mathcal{H}_{t}^{(i)};\beta_{1:t-1})f(\mathcal{H}_{t}^{(i)})\leq
l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
u_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)}).$

By the above two observations, we have that

$\min\left\\{l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)}),u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\right\\}\leq\pi_{2:t}(\mathcal{H}_{t}^{(i)};\beta_{1:t-1})f(\mathcal{H}_{t}^{(i)})\\\
\leq\max\left\\{u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
u_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)}),l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
u_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\right\\}\textnormal{~{}~{}a.s.}$

Thus, the following bracketing functions cover $\Pi_{2:t}\cdot\mathcal{F}$:

$\big{\\{}\big{(}l_{\Pi_{2:t}\cdot\mathcal{F},k},u_{\Pi_{2:t}\cdot\mathcal{F},k}\big{)}\big{\\}}_{k=1}^{|\mathcal{B}_{1:t-1}|\cdot
N_{\mathcal{F},\epsilon}}\\\
\triangleq\bigg{\\{}\bigg{[}\min\big{(}l_{\Pi,k}\cdot
l_{\mathcal{F},j},u_{\Pi,k}\cdot
l_{\mathcal{F},j}\big{)},\max\big{(}u_{\Pi,k}\cdot
u_{\mathcal{F},j},l_{\Pi,k}\cdot
u_{\mathcal{F},j}\big{)}\bigg{]}\bigg{\\}}_{k=1;j=1}^{k=|\mathcal{B}_{1:t-1}|;j=N_{\mathcal{F},\epsilon}}.$
(A.18)

Note that there are $|\mathcal{B}_{1:t-1}|\cdot N_{\mathcal{F},\epsilon}$
brackets above.

We now derive the size of the above brackets for $\Pi_{2:t}\cdot\mathcal{F}$.

$\left|\max\big{(}u_{\Pi,k}\cdot u_{\mathcal{F},j},l_{\Pi,k}\cdot
u_{\mathcal{F},j}\big{)}-\min\big{(}l_{\Pi,k}\cdot
l_{\mathcal{F},j},u_{\Pi,k}\cdot l_{\mathcal{F},j}\big{)}\right|$

Since $\big{|}\max(a,b)-c\big{|}\leq|a-c|+|b-c|$,

$\leq\left|u_{\Pi,k}\cdot u_{\mathcal{F},j}-\min\big{(}l_{\Pi,k}\cdot
l_{\mathcal{F},j},u_{\Pi,k}\cdot l_{\mathcal{F},j}\big{)}\right|\\\
+\left|l_{\Pi,k}\cdot u_{\mathcal{F},j}-\min\big{(}l_{\Pi,k}\cdot
l_{\mathcal{F},j},u_{\Pi,k}\cdot
l_{\mathcal{F},j}\big{)}\right|\textnormal{~{}~{}a.s.}$
$\leq\left|u_{\Pi,k}\cdot u_{\mathcal{F},j}-l_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|+\left|u_{\Pi,k}\cdot u_{\mathcal{F},j}-u_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|\\\ +\left|l_{\Pi,k}\cdot
u_{\mathcal{F},j}-l_{\Pi,k}\cdot l_{\mathcal{F},j}\right|+\left|l_{\Pi,k}\cdot
u_{\mathcal{F},j}-u_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|\textnormal{~{}~{}a.s.}$

Since $0\leq u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq 1$ a.s. and $0\leq
l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq 1$ a.s.,

$=\left|u_{\Pi,k}\cdot u_{\mathcal{F},j}-l_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|+\left|l_{\Pi,k}\cdot u_{\mathcal{F},j}-u_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|\\\
+u_{\Pi,k}\left|u_{\mathcal{F},j}-l_{\mathcal{F},j}\right|+l_{\Pi,k}\left|u_{\mathcal{F},j}-l_{\mathcal{F},j}\right|$

Again since $0\leq u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq 1$ a.s. and $0\leq
l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\leq 1$,

$\leq\left|u_{\Pi,k}\cdot u_{\mathcal{F},j}-l_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|+\left|l_{\Pi,k}\cdot u_{\mathcal{F},j}-u_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|+2\left|u_{\mathcal{F},j}-l_{\mathcal{F},j}\right|\textnormal{~{}~{}a.s.}$

By triangle inequality,

$\leq\left|u_{\Pi,k}\cdot u_{\mathcal{F},j}-u_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|+\left|u_{\Pi,k}\cdot l_{\mathcal{F},j}-l_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|\\\ +\left|l_{\Pi,k}\cdot
u_{\mathcal{F},j}-l_{\Pi,k}\cdot l_{\mathcal{F},j}\right|+\left|l_{\Pi,k}\cdot
l_{\mathcal{F},j}-u_{\Pi,k}\cdot
l_{\mathcal{F},j}\right|+2\left|u_{\mathcal{F},j}-l_{\mathcal{F},j}\right|\textnormal{~{}~{}a.s.}$

Using the same arguments as used above,

$\leq\left|u_{\mathcal{F},j}-l_{\mathcal{F},j}\right|+\left|u_{\Pi,k}-l_{\Pi,k}\right||l_{\mathcal{F},j}|+\left|u_{\mathcal{F},j}-l_{\mathcal{F},j}\right|+\left|l_{\Pi,k}-u_{\Pi,k}\right||l_{\mathcal{F},j}|+2\left|u_{\mathcal{F},j}-l_{\mathcal{F},j}\right|\textnormal{~{}a.s.}$
$=2\left|u_{\Pi,k}-l_{\Pi,k}\right||l_{\mathcal{F},j}|+4\left|u_{\mathcal{F},j}-l_{\mathcal{F},j}\right|$

Thus,

$\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{|}\max\big{\\{}u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
u_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)}),l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
u_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\big{\\}}\\\
-\min\big{\\{}l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)}),u_{\Pi,k}(\mathcal{H}_{t}^{(i)})\cdot
l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\big{\\}}\bigg{|}^{p}\bigg{]}$
$\leq\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{|}2\big{|}u_{\Pi,k}(\mathcal{H}_{t}^{(i)})-l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\big{|}|l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})|+4\big{|}u_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})-l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\big{|}\bigg{|}^{p}\bigg{]}$

By Lemma B.2 (Inequality using Binomial Theorem), for some constant
$c_{p}<\infty$,

$\leq
2^{p}c_{p}\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|u_{\Pi,k}(\mathcal{H}_{t}^{(i)})-l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\right|^{p}|l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})|^{p}\right]\\\
+4^{p}c_{p}\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|u_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})-l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\right|^{p}\right]$

Since brackets $[l_{\mathcal{F},j},u_{\mathcal{F},j}]$ are of size $\epsilon$
or less in $L_{p}(\mathcal{P}_{\pi^{*}})$ norm by construction,

$\leq
2^{p}c_{p}\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|u_{\Pi,k}(\mathcal{H}_{t}^{(i)})-l_{\Pi,k}(\mathcal{H}_{t}^{(i)})\right|^{p}\big{|}l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})\big{|}^{p}\right]+4^{p}c_{p}\epsilon^{p}$

By the definition of brackets $[l_{\Pi,k},u_{\Pi,k}]$ from display (A.17),

$\leq
2^{p}c_{p}\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|2\epsilon\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)})\right|^{p}|l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})|^{p}\right]+4^{p}c_{p}\epsilon^{p}$

Recall that by assumption of the Lemma, $F$ is a function such that
$|f(\mathcal{H}_{t}^{(i)})|\leq F(\mathcal{H}_{t}^{(i)})$ a.s. for all
$f\in\mathcal{F}$. Thus, the brackets
$\big{[}l_{\mathcal{F},k},u_{\mathcal{F},k}\big{]}$ can always be chosen such
that $|l_{\mathcal{F},j}(\mathcal{H}_{t}^{(i)})|\leq F(\mathcal{H}_{t}^{(i)})$
a.s. Thus,

$\leq
2^{p}c_{p}\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|2\epsilon\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)})\right|^{p}|F(\mathcal{H}_{t}^{(i)})|^{p}\right]+4^{p}c_{p}\epsilon^{p}$

Since $\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)})\geq 0$ and
$F(\mathcal{H}_{t}^{(i)})\geq 0$ by definition,

$=2^{2p}c_{p}\epsilon^{p}\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)})F(\mathcal{H}_{t}^{(i)})\right|^{p}\right]+4^{p}c_{p}\epsilon^{p}$

Since
$\dot{\pi}_{2:t}(\mathcal{H}_{t}^{(i)})=\sum_{t^{\prime}=2}^{t}\dot{\pi}_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)}\big{)}$
by definition,

$=2^{2p}c_{p}\epsilon^{p}\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{|}\sum_{t^{\prime}=2}^{t}\dot{\pi}_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)}\big{)}F(\mathcal{H}_{t}^{(i)})\bigg{|}^{p}\bigg{]}+4^{p}c_{p}\epsilon^{p}$

By repeatedly applying Lemma B.2 (Inequality using Binomial Theorem), for some
positive constant $k_{p}$,

$=\epsilon^{p}\bigg{\\{}2^{2p}c_{p}k_{p}^{t}\sum_{t^{\prime}=2}^{t}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}\dot{\pi}_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)}\big{)}F(\mathcal{H}_{t}^{(i)})\big{|}^{p}\right]+4^{p}c_{p}\bigg{\\}}.$

The term
$2^{2p}c_{p}k_{p}^{t}\sum_{t^{\prime}=2}^{t}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}\dot{\pi}_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)}\big{)}F(\mathcal{H}_{t}^{(i)})\big{|}^{p}\right]+4^{p}c_{p}$
above is bounded by assumption (iii).

Let
$c_{\Pi\cdot\mathcal{F}}\triangleq\left\\{2^{2p}c_{p}k_{p}^{t}\sum_{t^{\prime}=2}^{t}\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|\dot{\pi}_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)}\big{)}F(\mathcal{H}_{t}^{(i)})\right|^{p}\right]+4^{p}c_{p}\right\\}^{1/p}$.
By the above result, the brackets for $\Pi_{2:t}\cdot\mathcal{F}$ from display
(A.18) have size at most $\epsilon c_{\Pi\cdot\mathcal{F}}$ in
$L_{p}(\mathcal{P}_{\pi^{*}})$ norm. Thus,

$N_{[~{}]}\left(\epsilon
c_{\Pi\cdot\mathcal{F}},\Pi_{2:t}\cdot\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\right)\leq\underbrace{|\mathcal{B}_{1:t-1}|}_{\textnormal{Upper~{}bounds~{}}N_{[~{}]}\left(\epsilon,\Pi_{2:t},L_{p}(\mathcal{P}_{\pi^{*}})\right)}\cdot
N_{\mathcal{F},\epsilon}\\\
=\big{[}\textnormal{diam}(B_{1:t-1})/\epsilon\big{]}^{d_{1:t-1}}N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}.$

The final equality above holds by display (A.16).

The above implies that

$N_{[~{}]}\left(\epsilon,\Pi_{2:t}\cdot\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\right)\leq\big{[}\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon\big{]}^{d_{1:t-1}}\cdot
N_{[~{}]}\big{(}\epsilon/c_{\Pi\cdot\mathcal{F}},\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}.$
(A.19)

Note that by assumption (ii),
$N_{[~{}]}\big{(}\epsilon/c_{\Pi\cdot\mathcal{F}},\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$,
so the above implies that
$N_{[~{}]}\big{(}\epsilon,\Pi_{2:t}\cdot\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
for all $\epsilon>0$.

Bracketing integral result. We now work on showing the second part of the
Lemma, i.e., that $\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon,\Pi_{2:t}\cdot\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon<\infty$.

$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\left(\epsilon,\Pi_{2:t}\cdot\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon$

By display (A.19),

$\leq\int_{0}^{1}\sqrt{\log\left\\{\big{[}\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon\big{]}^{d_{1:t-1}}N_{[~{}]}\big{(}\epsilon/c_{\Pi\cdot\mathcal{F}},\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}\right\\}}d\epsilon$

Using properties of $\log$,

$=\int_{0}^{1}\sqrt{d_{1:t-1}\log\big{[}\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon\big{]}+\log
N_{[~{}]}\big{(}\epsilon/c_{\Pi\cdot\mathcal{F}},\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon$

Note that $\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon\geq 1$
since $\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon$ upper
bounds the bracketing number
$N_{[~{}]}\left(\epsilon,\Pi_{2:t},L_{p}(\mathcal{P}_{\pi^{*}})\right)$ (which
must be at least $1$). Thus,
$\log\big{[}\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon\big{]}\geq
0$. Since $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any numbers $a,b>0$ (to see
this, square both sides of the inequality),

$=\sqrt{d_{1:t-1}}\int_{0}^{1}\sqrt{\log\big{[}\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon\big{]}}d\epsilon+\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon/c_{\Pi\cdot\mathcal{F}},\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon.$
(A.20)

We now discuss why the quantity in the display above is finite:

  * •

Regarding the first term in display (A.20), note that since
$\log\big{[}\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon\big{]}\geq
0$, we have that
$\log\big{[}\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon\big{]}\leq\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon$.
Thus,

$\int_{0}^{1}\sqrt{\log\big{[}\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon\big{]}}d\epsilon\leq\int_{0}^{1}\sqrt{\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}/\epsilon}d\epsilon\\\
=\sqrt{\textnormal{diam}(B_{1:t-1})c_{\Pi\cdot\mathcal{F}}}\int_{0}^{1}\epsilon^{-2}d\epsilon<\infty.$

  * •

For the second term in display (A.20) above, note that

$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon/c_{\Pi\cdot\mathcal{F}},\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon=c_{\Pi\cdot\mathcal{F}}\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon/c_{\Pi\cdot\mathcal{F}},\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}c_{\Pi\cdot\mathcal{F}}^{-1}d\epsilon$

By integration by substitution, for $u=\epsilon/c_{\Pi\cdot\mathcal{F}}$,

$=c_{\Pi\cdot\mathcal{F}}\int_{0}^{c_{\Pi\cdot\mathcal{F}}^{-1}}\sqrt{\log
N_{[~{}]}\big{(}u,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}du<\infty.$
(A.21)

The above term is finite since $\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon<\infty$
by assumption (iv). If $c_{\Pi\cdot\mathcal{F}}^{-1}\leq 1$ display (A.21)
holds straightforwardly. If $c_{\Pi\cdot\mathcal{F}}^{-1}\geq 1$, display
(A.21) holds because
$N_{[~{}]}\big{(}1,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}\geq
N_{[~{}]}\big{(}u,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}$ for all
$u\geq 1$ by the definition of bracketing numbers.

We have shown that $\int_{0}^{1}\sqrt{\log
N_{[~{}]}\left(\epsilon,\Pi_{2:t}\cdot\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon<\infty$,
so we have now shown the second result of the Lemma. $~{}~{}\blacksquare$

##  Appendix B Policy Parameter Results

Overview of Supplement B Results.

  * •

Section B.1: Consistency of Policy Parameters (Sufficient Assumptions for
Condition 1; Theorem B.1)

  * •

Section B.2: Inequality Using Binomial Theorem (Helper Lemma B.2)

  * •

Section B.3: Stochastic Equicontinuity for Policy Parameters (Theorem B.3)

  * •

Section B.4: Invertibility of $\dot{\Phi}_{1:t}^{*}$ (Lemma B.4)

###  B.1 Consistency of Policy Parameters (Theorem B.1)

######  Theorem B.1 (Consistency of Policy Parameters).

We assume Conditions 2 (Minimum Exploration) and 3 (Lipschitz Policy Function)
hold. Condition 1 holds (i.e.,
$\hat{\beta}_{t}^{(n)}\overset{P}{\to}\beta_{t}^{*}$ for each $t\in[1\colon
T-1]$), under the following additional assumptions:

  1. (CP1)

Well-Separated Solutions: For each $t\in[1\colon T-1]$, for any $\epsilon>0$,
there exists some $\eta>0$ such that

$\inf_{\beta_{t}\in{}^{d_{t}}\textnormal{~{}s.t.~{}}\|\beta_{t}-\beta_{t}^{*}\|_{1}>\epsilon}\left\|\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\big{]}\right\|_{1}>\eta>0.$

  2. (CP2)

Asymptotically Tight: For each $t\in[1\colon T-1]$, for any $\epsilon>0$,
there exists some $k<\infty$ such that

$\limsup_{n\to\infty}\mathbb{P}\big{(}\big{\|}\hat{\beta}_{t}^{(n)}\big{\|}_{1}>k\big{)}\leq\epsilon.$

  3. (CP3)

Finite Bracketing Number: Let $\alpha>0$ be a constant. For each $t\in[1\colon
T-1]$ and any compact subset $K_{t}\subset{}^{d_{t}}$,

    1. (i)

For any $\epsilon>0$ and any vector $c\in{}^{d_{t}}$, the bracketing number

$N_{[~{}]}\left(\epsilon,~{}\big{\\{}c^{\top}\phi_{t}(\,\cdot\,;\beta_{t})\big{\\}}_{\beta_{t}\in
K_{t}},~{}L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\right)<\infty.$

    2. (ii)

There exists a function $F_{\phi_{t}}$ such that for all $\beta_{t}\in K_{t}$,
$\big{\|}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\big{\|}_{1}\leq
F_{\phi_{t}}(\mathcal{H}_{t}^{(i)})$ a.s. and

$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}F_{\phi_{t}}(\mathcal{H}_{t}^{(i)})\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\big{|}^{1+\alpha}\right]<\infty$

for all $t^{\prime}\in[2\colon t]$; the functions $\dot{\pi}_{t^{\prime}}$ are
from Condition 3.

Proof of Theorem B.1 (Consistency of Policy Parameters). We use an induction-
based argument. For the base case, we show that
$\hat{\beta}_{1}^{(n)}\overset{P}{\to}\beta_{1}^{*}$. For the induction step,
we show that $\hat{\beta}_{t}^{(n)}\overset{P}{\to}\beta_{t}^{*}$, given that
$\hat{\beta}_{1:t-1}^{(n)}\overset{P}{\to}\beta_{1:t-1}^{*}$.

Base Case. Note that
$\mathcal{H}_{1}^{(1)},\mathcal{H}_{1}^{(2)},\mathcal{H}_{1}^{(3)},\dots,\mathcal{H}_{1}^{(n)}$
are i.i.d. (data from the first time-step; no adaptive sampling yet). This
type of consistency proof is standard for Z-estimators; we include it for
completeness since the induction step uses similar techniques.

We first define the following useful functions:

$\Phi_{1}\big{(}\beta_{1}\big{)}\triangleq\mathbb{E}\big{[}\phi_{1}\big{(}\mathcal{H}_{1}^{(i)};\beta_{1}\big{)}\big{]}~{}~{}~{}~{}~{}~{}\textnormal{and}~{}~{}~{}~{}~{}~{}\hat{\Phi}_{1}^{(n)}\big{(}\beta_{1}\big{)}\triangleq\frac{1}{n}\sum_{i=1}^{n}\phi_{1}\big{(}\mathcal{H}_{1}^{(i)};\beta_{1}\big{)}.$

Let $\epsilon>0$. By assumption (CP1), there exists some $\eta>0$ such that if
$\beta_{1}\in{}^{d_{1}}$ satisfies
$\big{\|}\beta_{1}-\beta_{1}^{*}\big{\|}_{1}>\epsilon$, then
$\big{\|}\Phi_{1}\big{(}\beta_{1}\big{)}\big{\|}_{1}=\big{\|}\mathbb{E}\big{[}\phi_{1}\big{(}\mathcal{H}_{1}^{(i)};\beta_{1}\big{)}\big{]}\big{\|}_{1}>\eta>0$.
Thus,
$\mathbb{I}_{\|\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\|_{1}>\epsilon}\leq\mathbb{I}_{\|\Phi_{1}(\hat{\beta}_{1}^{(n)})\|_{1}>\eta}$,
so

$\mathbb{P}\left(\big{\|}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{\|}_{1}>\epsilon\right)\leq\mathbb{P}\left(\big{\|}\Phi_{1}\big{(}\hat{\beta}_{1}^{(n)}\big{)}\big{\|}_{1}>\eta\right).$

By the definition of $\hat{\beta}_{1}^{(n)}$ from display (3.9),
$\hat{\Phi}_{1}^{(n)}\big{(}\hat{\beta}_{1}^{(n)}\big{)}=\frac{1}{n}\sum_{i=1}^{n}\phi_{1}\big{(}\mathcal{H}_{1}^{(i)};\hat{\beta}_{1}^{(n)}\big{)}\\\
=o_{P}(1/\sqrt{n})=o_{P}(1)$. Thus,

$=\mathbb{P}\left(\big{\|}\hat{\Phi}_{1}^{(n)}\big{(}\hat{\beta}_{1}^{(n)}\big{)}-\Phi_{1}\big{(}\hat{\beta}_{1}^{(n)}\big{)}\big{\|}_{1}>\eta-
o_{P}(1)\right).$

By assumption (CP2), for any $\delta>0$, there exists some $k<\infty$ such
that
$\limsup_{n\to\infty}\mathbb{P}\big{(}\big{\|}\hat{\beta}_{1}^{(n)}\big{\|}_{1}>k\big{)}\leq\delta$.
We use this $k$ below:

$=\mathbb{P}\left(\big{\|}\hat{\Phi}_{1}^{(n)}\big{(}\hat{\beta}_{1}^{(n)}\big{)}-\Phi_{1}\big{(}\hat{\beta}_{1}^{(n)}\big{)}\big{\|}_{1}\left\\{\mathbb{I}_{\|\hat{\beta}_{1}^{(n)}\|_{1}>k}+\mathbb{I}_{\|\hat{\beta}_{1}^{(n)}\|_{1}\leq
k}\right\\}>\eta-o_{P}(1)\right)$
$\leq\mathbb{P}\left(\big{\|}\hat{\Phi}_{1}^{(n)}\big{(}\hat{\beta}_{1}^{(n)}\big{)}-\Phi_{1}\big{(}\hat{\beta}_{1}^{(n)}\big{)}\big{\|}_{1}~{}\mathbb{I}_{\|\hat{\beta}_{1}^{(n)}\|_{1}\leq
k}>\eta/2-o_{P}(1)\right)\\\
+\mathbb{P}\left(\big{\|}\hat{\Phi}_{1}^{(n)}\big{(}\hat{\beta}_{1}^{(n)}\big{)}-\Phi_{1}\big{(}\hat{\beta}_{1}^{(n)}\big{)}\big{\|}_{1}~{}\mathbb{I}_{\|\hat{\beta}_{1}^{(n)}\|_{1}>k}>\eta/2-o_{P}(1)\right)$
$\leq\mathbb{P}\left(\big{\|}\hat{\Phi}_{1}^{(n)}\big{(}\hat{\beta}_{1}^{(n)}\big{)}-\Phi_{1}\big{(}\hat{\beta}_{1}^{(n)}\big{)}\big{\|}_{1}~{}\mathbb{I}_{\|\hat{\beta}_{1}^{(n)}\|_{1}\leq
k}>\eta/2-o_{P}(1)\right)+\mathbb{P}\left(\big{\|}\hat{\beta}_{1}^{(n)}\big{\|}_{1}>k\right)+o(1)$
$\leq\underbrace{\mathbb{P}\bigg{(}\sup_{\beta_{1}\in{}^{d_{1}}\textnormal{~{}s.t.~{}}\|\beta_{1}\|_{1}\leq
k}\big{\|}\hat{\Phi}_{1}^{(n)}\big{(}\beta_{1}\big{)}-\Phi_{1}\big{(}\beta_{1}\big{)}\big{\|}_{1}>\eta/2-o_{P}(1)\bigg{)}}_{=o(1)}\\\
+\underbrace{\mathbb{P}\left(\big{\|}\hat{\beta}_{1}^{(n)}\big{\|}_{1}>k\right)}_{\leq\delta}+o(1).$
(B.1)

For the second term above, by assumption (CP2),
$\limsup_{n\to\infty}\mathbb{P}\big{(}\big{\|}\hat{\beta}_{1}^{(n)}\big{\|}_{1}>k\big{)}\leq\delta$
and $\delta$ can be made arbitrarily small.

For the first term above, we can apply the Uniform Weak Law of Large Numbers
result for i.i.d. data [Van Der Vaart and Wellner, 1996, Theorem 2.4.1] to get
that it converges to zero as $n\to\infty$. Specifically, note that

$N_{[~{}]}\left(\epsilon,~{}\big{\\{}c^{\top}\phi_{1}(\,\cdot\,;\beta_{1})\big{\\}}_{\beta_{1}\in{}^{d_{1}}\textnormal{~{}s.t.~{}}\|\beta_{1}\|_{1}\leq
k},~{}L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\right)<\infty,$

for any $c\in{}^{d_{1}}$ and any $\epsilon>0$ by assumption (CP3). Thus, by
the Uniform Weak Law of Large Numbers, we have that

$\sup_{\beta_{1}\in{}^{d_{1}}\textnormal{~{}s.t.~{}}\|\beta_{1}\|_{1}\leq
k}\left|c^{\top}\hat{\Phi}_{1}^{(n)}\big{(}\beta_{1}\big{)}-c^{\top}\Phi_{1}\big{(}\beta_{1}\big{)}\right|\overset{P}{\to}0,$

for any $c\in{}^{d_{1}}$. Thus, by Cramer Wold device we have that

$\sup_{\beta_{1}\in{}^{d_{1}}\textnormal{~{}s.t.~{}}\|\beta_{1}\|_{1}\leq
k}\big{\|}\hat{\Phi}_{1}^{(n)}\big{(}\beta_{1}\big{)}-\Phi_{1}\big{(}\beta_{1}\big{)}\big{\|}_{1}\overset{P}{\to}0.$

Thus, the expression in display (B.1) above converges to zero.

Induction Step. For our induction assumption, we assume that
$\hat{\beta}_{1:t-1}^{(n)}\overset{P}{\to}\beta_{1:t-1}^{*}$. Given this
assumption, we will show that
$\hat{\beta}_{t}^{(n)}\overset{P}{\to}\beta_{t}^{*}$.

We now define the following useful functions:

$\Phi_{t}\big{(}\beta_{1:t}\big{)}\triangleq\mathbb{E}_{\pi(\beta_{1:t-1})}\left[\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}\big{)}\right]=\mathbb{E}\left[W_{2:t}^{(i)}\big{(}\beta_{1:t-1},\hat{\beta}_{1:t-1}^{(n)}\big{)}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}\big{)}\right]$
(B.2)

and

$\hat{\Phi}_{t}^{(n)}\big{(}\beta_{1:t}\big{)}\triangleq\frac{1}{n}\sum_{i=1}^{n}W_{2:t}^{(i)}\big{(}\beta_{1:t-1},\hat{\beta}_{1:t-1}^{(n)}\big{)}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}\big{)}.$
(B.3)

For now, we take as given that display (B.4) below holds; we will show this
result holds at the end of this proof.

$\left\|\Phi_{t}\big{(}\hat{\beta}_{1:t-1}^{(n)},\beta_{t}^{*}\big{)}-\Phi_{t}\big{(}\beta_{1:t-1}^{*},\beta_{t}^{*}\big{)}\right\|_{1}=o_{P}(1).$
(B.4)

Let $\epsilon>0$. By assumption (CP1), there exists some $\eta>0$ such that if
$\beta_{t}\in{}^{d_{t}}$ satisfies
$\big{\|}\beta_{t}-\beta_{t}^{*}\big{\|}_{1}>\epsilon$, then
$\big{\|}\Phi_{t}\big{(}\beta_{1:t-1}^{*},\beta_{t}\big{)}\big{\|}_{1}=\big{\|}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\big{]}\big{\|}_{1}>\eta>0$.
Thus,

$\mathbb{P}\left(\big{\|}\hat{\beta}_{t}^{(n)}-\beta_{t}^{*}\big{\|}_{1}>\epsilon\right)\leq\mathbb{P}\left(\big{\|}\Phi_{t}\big{(}\beta_{1:t-1}^{*},\hat{\beta}_{t}^{(n)}\big{)}\big{\|}_{1}>\eta\right)$

Note
$\big{\|}\Phi_{t}\big{(}\beta_{1:t-1}^{*},\hat{\beta}_{t}^{(n)}\big{)}\big{\|}_{1}=\big{\|}\Phi_{t}\big{(}\beta_{1:t-1}^{*},\hat{\beta}_{t}^{(n)}\big{)}-\Phi_{t}\big{(}\hat{\beta}_{1:t-1}^{(n)},\hat{\beta}_{t}^{(n)}\big{)}+\Phi_{t}\big{(}\hat{\beta}_{1:t-1}^{(n)},\hat{\beta}_{t}^{(n)}\big{)}\big{\|}_{1}\\\
\leq\big{\|}\Phi_{t}\big{(}\beta_{1:t-1}^{*},\hat{\beta}_{t}^{(n)}\big{)}-\Phi_{t}\big{(}\hat{\beta}_{1:t-1}^{(n)},\hat{\beta}_{t}^{(n)}\big{)}\big{\|}_{1}+\big{\|}\Phi_{t}\big{(}\hat{\beta}_{1:t-1}^{(n)},\hat{\beta}_{t}^{(n)}\big{)}\big{\|}_{1}=\big{\|}\Phi_{t}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}\big{\|}_{1}+o_{P}(1)$;
the last equality holds by display (B.4) and the definition of
$\hat{\beta}_{t}^{(n)}$ from display (3.9). Thus,

$\leq\mathbb{P}\left(\big{\|}\Phi_{t}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}\big{\|}_{1}>\eta-
o_{P}(1)\right)$

Note
$\hat{\Phi}_{t}^{(n)}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}=\frac{1}{n}\sum_{i=1}^{n}W_{2:t}^{(i)}\big{(}\hat{\beta}_{1:t-1}^{(n)},\hat{\beta}_{1:t-1}^{(n)}\big{)}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\hat{\beta}_{t}^{(n)}\big{)}=\frac{1}{n}\sum_{i=1}^{n}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\hat{\beta}_{t}^{(n)}\big{)}\\\
=o_{P}(1/\sqrt{n})=o_{P}(1)$; the second to last equality holds by the
definition of $\hat{\beta}_{t}^{(n)}$ from display (3.9). Thus,

$=\mathbb{P}\left(\big{\|}\hat{\Phi}_{t}^{(n)}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}-\Phi_{t}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}\big{\|}_{1}>\eta-
o_{P}(1)\right)$

By assumption (CP2), for any $\delta>0$, there exists some $k<\infty$ such
that
$\limsup_{n\to\infty}\mathbb{P}\big{(}\big{\|}\hat{\beta}_{t}^{(n)}\big{\|}_{1}>k\big{)}\leq\delta$.
We use this $k$ below:

$=\mathbb{P}\left(\big{\|}\hat{\Phi}_{t}^{(n)}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}-\Phi_{t}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}\big{\|}_{1}\left\\{\mathbb{I}_{\|\hat{\beta}_{t}^{(n)}\|_{1}>k}+\mathbb{I}_{\|\hat{\beta}_{t}^{(n)}\|_{1}\leq
k}\right\\}>\eta-o_{P}(1)\right)$
$\leq\mathbb{P}\left(\big{\|}\hat{\Phi}_{t}^{(n)}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}-\Phi_{t}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}\big{\|}_{1}~{}\mathbb{I}_{\|\hat{\beta}_{t}^{(n)}\|_{1}\leq
k}>\eta/2-o_{P}(1)\right)\\\
+\mathbb{P}\left(\big{\|}\hat{\Phi}_{t}^{(n)}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}-\Phi_{t}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}\big{\|}_{1}~{}\mathbb{I}_{\|\hat{\beta}_{t}^{(n)}\|_{1}>k}>\eta/2-o_{P}(1)\right)$
$\leq\mathbb{P}\left(\big{\|}\hat{\Phi}_{t}^{(n)}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}-\Phi_{t}\big{(}\hat{\beta}_{1:t}^{(n)}\big{)}\big{\|}_{1}~{}\mathbb{I}_{\|\hat{\beta}_{t}^{(n)}\|_{1}\leq
k}>\eta/2-o_{P}(1)\right)+\mathbb{P}\left(\big{\|}\hat{\beta}_{t}^{(n)}\big{\|}_{1}>k\right)+o(1)$
$\leq\mathbb{P}\bigg{(}\sup_{\beta_{t}\in{}^{d_{t}}\textnormal{~{}s.t.~{}}\|\beta_{t}\|_{1}\leq
k}\big{\|}\hat{\Phi}_{t}^{(n)}\big{(}\hat{\beta}_{1:t-1}^{(n)},\beta_{t}\big{)}-\Phi_{t}\big{(}\hat{\beta}_{1:t-1}^{(n)},\beta_{t}\big{)}\big{\|}_{1}>\eta/2-o_{P}(1)\bigg{)}\\\
+\mathbb{P}\left(\big{\|}\hat{\beta}_{t}^{(n)}\big{\|}_{1}>k\right)+o(1)$
(B.5)

Recall $\hat{\beta}_{1:t-1}^{(n)}\overset{P}{\to}\beta_{1:t-1}^{*}$ by our
induction assumption; thus, $\mathbb{I}_{\hat{\beta}_{1:t-1}^{(n)}\in
B_{1:t-1}}\overset{P}{\to}1$, where recall that
$B_{1:t-1}\subset{}^{d_{1:t-1}}$ is a compact subset whose interior contains
$\beta_{1:t-1}^{*}$. Thus,

$\leq\underbrace{\mathbb{P}\bigg{(}\sup_{\beta_{t}\in{}^{d_{t}}\textnormal{~{}s.t.~{}}\|\beta_{t}\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}\big{\|}\hat{\Phi}_{t}^{(n)}\big{(}\beta_{1:t-1},\beta_{t}\big{)}-\Phi_{t}\big{(}\beta_{1:t-1},\beta_{t}\big{)}\big{\|}_{1}>\eta/2-o_{P}(1)\bigg{)}}_{=o(1)}\\\
+\underbrace{\mathbb{P}\left(\big{\|}\hat{\beta}_{t}^{(n)}\big{\|}_{1}>k\right)}_{\leq\delta}+o(1)$

Note that the above converges to zero as $n\to\infty$ for the following
reasons:

  * •

By assumption (CP2),
$\limsup_{n\to\infty}\mathbb{P}\big{(}\big{\|}\hat{\beta}_{t}^{(n)}\big{\|}_{1}>k\big{)}\leq\delta$
and $\delta$ can be made arbitrarily small.

  * •

Note that by Cramer Wold device, to show that

$\sup_{\beta_{t}\in{}^{d_{t}}\textnormal{~{}s.t.~{}}\|\beta_{t}\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}\left\|\hat{\Phi}_{t}^{(n)}\big{(}\beta_{1:t-1},\beta_{t}\big{)}-\Phi_{t}\big{(}\beta_{1:t-1},\beta_{t}\big{)}\right\|_{1}\overset{P}{\to}0,$

it is sufficient to show that for any vector $c\in{}^{d_{t}}$,

$\sup_{\beta_{t}\in{}^{d_{t}}\textnormal{~{}s.t.~{}}\|\beta_{t}\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}c^{\top}\left\\{\hat{\Phi}_{t}^{(n)}\big{(}\beta_{1:t-1},\beta_{t}\big{)}-\Phi_{t}\big{(}\beta_{1:t-1},\beta_{t}\big{)}\right\\}\overset{P}{\to}0.$

Also, note that

$\sup_{\beta_{t}\in{}^{d_{t}}\textnormal{~{}s.t.~{}}\|\beta_{t}\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}c^{\top}\left\\{\hat{\Phi}_{t}^{(n)}\big{(}\beta_{1:t-1},\beta_{t}\big{)}-\Phi_{t}\big{(}\beta_{1:t-1},\beta_{t}\big{)}\right\\}$
$=\sup_{\beta_{t}\in{}^{d_{t}}\textnormal{~{}s.t.~{}}\|\beta_{t}\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}W_{2:t}^{(i)}\big{(}\beta_{1:t-1},\hat{\beta}_{1:t-1}^{(n)}\big{)}c^{\top}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\\\
-\mathbb{E}\left[W_{2:t}^{(i)}\big{(}\beta_{1:t-1},\hat{\beta}_{1:t-1}^{(n)}\big{)}c^{\top}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\right]\bigg{\\}}\overset{P}{\to}0.$

The above convergence result holds by Theorem D.2 (Weighted Martingale
Triangular Array Uniform Weak Law of Large Numbers). Specifically we are able
to apply Theorem D.2 because Condition 2 holds and
$N_{[~{}]}\left(\epsilon,\mathcal{F}_{\Pi
c^{\top}\phi_{t}}(B_{1:t-1},k),L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\right)<\infty$
for all $c\in{}^{d_{t}}$ and all $\epsilon>0$, where

$\mathcal{F}_{\Pi
c^{\top}\phi_{t}}(B_{1:t-1},k)\triangleq\bigg{\\{}\bigg{[}\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}(\,\cdot\,;\beta_{t^{\prime}-1})\bigg{]}c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}\big{)}\bigg{\\}}_{\beta_{1:t-1}\in
B_{1:t-1},~{}\beta_{t}\in{}^{d_{t}}\textnormal{~{}s.t.~{}}\|\beta_{t}\|_{1}\leq
k}.$

The above finite bracketing number result holds since using assumption (CP3)
and Condition 3, we can apply by Lemma A.5 (specifically see Remark 8 part
(b1)).

We now show that display (B.4) holds. Let $\beta_{1:t-1}\in B_{1:t-1}$.

$\left\|\Phi_{t}\big{(}\beta_{1:t-1},\beta_{t}^{*}\big{)}-\Phi_{t}\big{(}\beta_{1:t-1}^{*},\beta_{t}^{*}\big{)}\right\|_{1}$
$=\bigg{\|}\mathbb{E}\bigg{[}\left\\{W_{2:t}^{(i)}\big{(}\beta_{1:t-1},\hat{\beta}_{1:t-1}^{(n)}\big{)}-W_{2:t}^{(i)}\big{(}\beta_{1:t-1}^{*},\hat{\beta}_{1:t-1}^{(n)}\big{)}\right\\}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\bigg{]}\bigg{\|}_{1}$
$=\bigg{\|}\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\left\\{W_{2:t}^{(i)}\big{(}\beta_{1:t-1},\beta_{1:t-1}^{*}\big{)}-W_{2:t}^{(i)}\big{(}\beta_{1:t-1}^{*},\beta_{1:t-1}^{*}\big{)}\right\\}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\bigg{]}\bigg{\|}_{1}$

By Jensen’s inequality,

$\leq\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\left|W_{2:t}^{(i)}\big{(}\beta_{1:t-1},\beta_{1:t-1}^{*}\big{)}-W_{2:t}^{(i)}\big{(}\beta_{1:t-1}^{*},\beta_{1:t-1}^{*}\big{)}\right|\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{1}\bigg{]}$

By definition of
$W_{t^{\prime}}^{(i)}\big{(}\beta_{t^{\prime}-1},\beta_{t^{\prime}-1}^{*}\big{)}$
from display (5.5),

$=\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{|}\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}\big{)}-\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}^{*}\big{)}\bigg{|}\\\
\bigg{\\{}\prod_{t^{\prime}=2}^{t}\frac{1}{\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}^{*}\big{)}}\bigg{\\}}\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{1}\bigg{]}$

By Condition 2 (Minimum Exploration),
$\pi_{t^{\prime}}\big{(}A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}^{*}\big{)}^{-1}\leq\pi_{\min}^{-1}$
a.s. Thus,

$\leq\pi_{\min}^{-(t-1)}\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{|}\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1})-\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}^{*})\bigg{|}\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{1}\bigg{]}$
(B.6)

By Condition 3, we can apply Lemma A.4 (Product of Lipschitz Policy Functions
are Lipschitz) to get that

$\leq\pi_{\min}^{-(t-1)}\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{1}\bigg{\\{}\sum_{t^{\prime}=2}^{t}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\bigg{\\}}\big{\|}\beta_{1:t-1}-\beta_{1:t-1}^{*}\big{\|}_{2}\bigg{]}$

By linearity of expectations,

$=\pi_{\min}^{-(t-1)}\bigg{\\{}\sum_{t^{\prime}=2}^{t}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{1}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\right]\bigg{\\}}\big{\|}\beta_{1:t-1}-\beta_{1:t-1}^{*}\big{\|}_{2}.$

Thus, by consolidating the above results, we have that

$\big{\|}\Phi_{t}\big{(}\hat{\beta}_{1:t-1}^{(n)},\beta_{t}^{*}\big{)}-\Phi_{t}\big{(}\beta_{1:t-1}^{*},\beta_{t}^{*}\big{)}\big{\|}_{1}\\\
\leq\pi_{\min}^{-(t-1)}\bigg{\\{}\sum_{t^{\prime}=2}^{t}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{1}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\right]\bigg{\\}}\big{\|}\hat{\beta}_{1:t-1}^{(n)}-\beta_{1:t-1}^{*}\big{\|}_{2}=o_{P}(1).$

The last limit above holds because

  * •

$\big{\|}\hat{\beta}_{1:t-1}^{(n)}-\beta_{1:t-1}^{*}\big{\|}_{2}=o_{P}(1)$
since $\hat{\beta}_{1:t-1}^{(n)}\overset{P}{\to}\beta_{1:t-1}^{*}$ by our
induction assumption.

  * •

By assumption (CP3) (Finite Bracketing Number for Policy Functions), there
exists a function $F_{\phi_{t}}$ such that
$\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}\big{)}\big{\|}_{1}\leq
F_{\phi_{t}}(\mathcal{H}_{t}^{(i)})$ a.s. and for all $t^{\prime}\in[2\colon
t]$,
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}F_{\phi_{t}}\big{(}\mathcal{H}_{t}^{(i)}\big{)}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\big{]}<\infty$.
Thus,

$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{1}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\right]\leq\mathbb{E}_{\pi_{2:t}^{*}}\left[F_{\phi_{t}}\big{(}\mathcal{H}_{t}^{(i)}\big{)}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\right]<\infty.$

We have now shown that display (B.4) holds. $\blacksquare$

###  B.2 Inequality Using Binomial Theorem (Helper Lemma B.2)

######  Lemma B.2 (Inequality Using Binomial Theorem).

For any $\eta\geq 1$ and any $a,b\in\real$, we have that $|a+b|^{\eta}\leq
c_{\eta}(|a|^{\eta}+|b|^{\eta})$ for some constant $c_{\eta}<\infty$.

Proof of Lemma B.2. Note that

$|a+b|^{\eta}\leq\begin{cases}|a-b|^{\lfloor\eta\rfloor}&\textnormal{ if
}|a+b|<1\\\ |a-b|^{\lceil\eta\rceil}&\textnormal{ if }|a+b|\geq 1\\\
\end{cases}$

Above we use $\lfloor\eta\rfloor$ to round $\eta$ down to the nearest integer
and we use $\lceil\eta\rceil$ to round $\eta$ up to the nearest integer. Let

$k\triangleq\begin{cases}\lfloor\eta\rfloor&\textnormal{ if }|a+b|<1\\\
\lceil\eta\rceil&\textnormal{ if }|a+b|\geq 1\end{cases}.$

Note $k\geq 1$ since that $\lceil\eta\rceil\geq\lfloor\eta\rfloor\geq 1$
because $\eta\geq 1$. Since $k$ is a positive integer, by the Binomial
theorem,

$|a+b|^{k}=\big{|}(a+b)^{k}\big{|}=\bigg{|}\sum_{j=0}^{k}{k\choose
j}a^{j}~{}b^{k-j}\bigg{|}=\sum_{j=0}^{k}{k\choose j}|a|^{j}~{}|b|^{k-j}$

Note that $|a|^{j}~{}|b|^{k-j}\leq\max\big{(}|a|^{k},|b|^{k}\big{)}$ for all
$j\in[0\colon k]$. Thus,

$\leq\bigg{\\{}\sum_{j=0}^{k}{k\choose
j}\bigg{\\}}\max\big{(}|a|^{k},|b|^{k}\big{)}\leq\bigg{\\{}\sum_{j=0}^{k}{k\choose
j}\bigg{\\}}\big{(}|a|^{k}+|b|^{k}\big{)}.$

Thus we can choose $c_{\eta}=\left\\{\sum_{j=0}^{k}{k\choose j}\right\\}$.
$\blacksquare$

###  B.3 Asymptotic Equicontinuity for Policy Parameters (Theorem B.3)

######  Theorem B.3 (Asymptotic Equicontinuity for Policy Parameters).

We assume that Conditions 1-4 on the adaptive sampling algorithm hold.
Consider the following results:

$\sqrt{n}\left\\{\hat{\Phi}_{1:T-1}^{(n)}(\hat{\beta}_{1:T-1}^{(n)})-\Phi_{1:T-1}(\hat{\beta}_{1:T-1}^{(n)})\right\\}\\\
=\sqrt{n}\left\\{\hat{\Phi}_{1:T-1}^{(n)}(\beta_{1:T-1}^{*})-\Phi_{1:T-1}(\beta_{1:T-1}^{*})\right\\}+o_{P}(1)$
(B.7)

and

$\sqrt{n}\big{(}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\big{)}=O_{P}(1).$

The above results hold under the following additional assumptions:

  1. (NP1)

Finite Bracketing Integral: Let $\alpha>0$ be a constant. For each
$t\in[1\colon T-1]$, for any vector $c\in{}^{d_{t}}$,

$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\left(\epsilon,~{}\big{\\{}c^{\top}\phi_{t}(\,\cdot\,;\beta_{t})\big{\\}}_{\beta_{t}\in
B_{t}},~{}L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon<\infty.$ (B.8)

Additionally, there exists a function $F_{\phi_{t}}$ such that for all
$\beta_{t}\in B_{t}$,
$\big{\|}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\big{\|}_{1}\leq
F_{\phi_{t}}(\mathcal{H}_{t}^{(i)})$ a.s. and

$\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}F_{\phi,t}(\mathcal{H}_{t}^{(i)})\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\big{|}^{2+\alpha}\right]<\infty$
(B.9)

for all $t^{\prime}\in[2\colon T]$; the functions $\dot{\pi}_{t^{\prime}}$
above are from Condition 3.

  2. (NP2)

Continuity Condition: For each $t\in[1\colon T-1]$, the following mapping is
continuous at $\beta_{t}=\beta_{t}^{*}$:

$\beta_{t}\mapsto\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}\big{)}-\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{2}^{2}\right].$

######  Remark 9 (Condition 5 implies assumptions (NP1) and (NP2) above hold).

As we discussed in the Remark below Condition 5 (Lipschitz Policy Estimating
Function), Condition 5 can be replaced by more general assumptions; these are
assumptions (NP1) and (NP2) above.

  * •

Condition 5 implies assumption (NP1) because

    * –

Example 19.7 of Van der Vaart [2000] shows that Lipschitz property of
Condition 5 and the compactness of $B_{t}$ implies that the bracketing
integral condition from display (B.8) holds.

    * –

We now show why Condition 5 implies that display (B.9) holds. Since $B_{t}$ is
compact, let $\textnormal{diam}(B_{t})<\infty$ be the diameter of $B_{t}$ in
Euclidian distance. Note the following inequality for all $\beta_{t}\in
B_{t}$,

$\big{\|}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\big{\|}_{1}\leq\sqrt{d_{t}}\big{\|}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\big{\|}_{2}\\\
\leq\sqrt{d_{t}}\left\\{\big{\|}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t}^{*})\big{\|}_{2}+\dot{\phi}_{t}(\mathcal{H}_{t}^{(i)})\textnormal{diam}(B_{t})\right\\}\textnormal{~{}~{}a.s.}$

The first inequality above holds by property of norms and the second
inequality above holds by display (5.18) of Condition 3. Furthermore, note
that

$\mathbb{E}_{\pi_{2:T}^{*}}\left[\left|\sqrt{d_{t}}\left\\{\big{\|}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t}^{*})\big{\|}_{2}+\dot{\phi}_{t}(\mathcal{H}_{t}^{(i)})\textnormal{diam}(B_{t})\right\\}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\right|^{2+\alpha}\right].$

By Lemma B.2 (Inequality Using Binomial Theorem), for some positive constant
$c_{2+\alpha}<\infty$,

$\leq
c_{2+\alpha}\mathbb{E}_{\pi_{2:T}^{*}}\left[\left|\sqrt{d_{t}}\big{\|}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t}^{*})\big{\|}_{2}\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\right|^{2+\alpha}\right]\\\
+c_{2+\alpha}\mathbb{E}_{\pi_{2:T}^{*}}\left[\left|\sqrt{d_{t}}\dot{\phi}_{t}(\mathcal{H}_{t}^{(i)})\textnormal{diam}(B_{t})\dot{\pi}_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\right|^{2+\alpha}\right]<\infty.$

The final inequality holds by Condition 5. The above implies that display
(B.9) holds.

  * •

We now discuss why Condition 5 implies assumption (NP2) holds. Let
$\epsilon>0$. We want to show that there exists some $\delta>0$ such that
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}\big{)}-\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{2}^{2}\right]\leq\epsilon$
whenever $\big{\|}\beta_{t}-\beta_{t}^{*}\big{\|}_{2}\leq\delta$. By Condition
5, for any $\beta_{t}\in B_{t}$,

$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\|}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}\big{)}-\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\big{\|}_{2}^{2}\right]\leq\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\dot{\phi}_{t}(\mathcal{H}_{t}^{(i)})^{2}\big{]}\big{\|}\beta_{t}-\beta_{t}^{*}\big{\|}_{2}^{2}.$

Recall
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\dot{\phi}_{t}(\mathcal{H}_{t}^{(i)})^{2}\big{]}<\infty$
by Condition 5. Thus,
$\delta=\epsilon^{1/2}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\dot{\phi}_{t}(\mathcal{H}_{t}^{(i)})^{2}\big{]}^{-1/2}$
is sufficient.

Proof of Theorem B.3. Recall in displays (5.8) and (5.9), we defined the
functions $\Phi_{1:T-1}(\beta_{1:T-1})$ and
$\hat{\Phi}_{1:T-1}^{(n)}(\beta_{1:T-1})$ respectively. More generally, we now
define for any $t\in[1\colon T-1]$ the following functions:

$\Phi_{1:t}(\beta_{1:t})\triangleq\mathbb{E}\begin{bmatrix}\phi_{1}(\mathcal{H}_{1}^{(i)};\beta_{1})\\\
W_{2}^{(i)}(\beta_{1},\hat{\beta}_{1}^{(n)})\phi_{2}(\mathcal{H}_{2}^{(i)};\beta_{2})\\\
W_{2:3}^{(i)}(\beta_{1:2},\hat{\beta}_{1:2}^{(n)})\phi_{3}(\mathcal{H}_{3}^{(i)};\beta_{3})\\\
\vdots\\\
W_{2:t}^{(i)}(\beta_{1:t-1},\hat{\beta}_{1:t-1}^{(n)})\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\end{bmatrix}$

and

$\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t})\triangleq\frac{1}{n}\sum_{i=1}^{n}\begin{bmatrix}\phi_{1}(\mathcal{H}_{1}^{(i)};\beta_{1})\\\
W_{2}^{(i)}(\beta_{1},\hat{\beta}_{1}^{(n)})\phi_{2}(\mathcal{H}_{2}^{(i)};\beta_{2})\\\
W_{2:3}^{(i)}(\beta_{1:2},\hat{\beta}_{1:2}^{(n)})\phi_{3}(\mathcal{H}_{3}^{(i)};\beta_{3})\\\
\vdots\\\
W_{2:t}^{(i)}(\beta_{1:t-1},\hat{\beta}_{1:t-1}^{(n)})\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\end{bmatrix}.$

We use an induction argument.

  * •

For the base case, $t=1$, we will show that
$\sqrt{n}\big{(}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{)}=O_{P}(1)$ and that

$\sqrt{n}\left\\{\hat{\Phi}_{1}^{(n)}(\hat{\beta}_{1}^{(n)})-\Phi_{1}(\hat{\beta}_{1}^{(n)})\right\\}=\sqrt{n}\left\\{\hat{\Phi}_{1}^{(n)}(\beta_{1}^{*})-\Phi_{1}(\beta_{1}^{*})\right\\}+o_{P}(1).$

  * •

For the induction step, $t>1$, we assume that
$\sqrt{n}\big{(}\hat{\beta}_{1:t-1}^{(n)}-\beta_{1:t-1}^{*}\big{)}=O_{P}(1)$
and will show that
$\sqrt{n}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}=O_{P}(1)$ and
that

$\sqrt{n}\left\\{\hat{\Phi}_{1:t}^{(n)}(\hat{\beta}_{1:t}^{(n)})-\Phi_{1:t}(\hat{\beta}_{1:t}^{(n)})\right\\}=\sqrt{n}\left\\{\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\right\\}+o_{P}(1).$

To show that the Theorem holds, it is sufficient to show the above results
hold.

Base Case. Note that since
$\mathcal{H}_{1}^{(1)},\mathcal{H}_{1}^{(2)},\mathcal{H}_{1}^{(3)},\dots,\mathcal{H}_{1}^{(n)}$
are i.i.d., we can use an asymptotic normality argument for Z-estimators on
i.i.d. data.

Stochastic Equicontinuity Result. First, we will apply Lemma D.6 (Stochastic
Equicontinuity) to get that for any fixed vector $c\in{}^{d_{1}}$,

$\sqrt{n}c^{\top}\left\\{\hat{\Phi}_{1}^{(n)}(\hat{\beta}_{1}^{(n)})-\Phi_{1}(\hat{\beta}_{1}^{(n)})\right\\}=\sqrt{n}c^{\top}\left\\{\hat{\Phi}_{1}^{(n)}(\beta_{1}^{*})-\Phi_{1}(\beta_{1}^{*})\right\\}+o_{P}(1).$
(B.10)

We are able to apply Lemma D.6 (Stochastic Equicontinuity) because the
following assumptions hold:

  * •

Conditions 2 (Minimum Exploration) and 3 (Lipschitz Policy Functions) hold.

  * •

By assumption (NP1) (Finite Bracketing Integral), for any vector
$c\in{}^{d_{1}}$,

$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\left(\epsilon,~{}\big{\\{}c^{\top}\phi_{1}(\,\cdot\,;\beta_{1})\big{\\}}_{\beta_{1}\in
B_{1}},~{}L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon<\infty.$

  * •

$\hat{\beta}_{1}^{(n)}\overset{P}{\to}\beta_{1}^{*}$ by Condition 1. Thus, by
assumption (NP2) and continuous mapping theorem we have that for any vector
$c\in{}^{d_{1}}$,
$\nu\big{(}c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}),~{}c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}^{*})\big{)}\overset{P}{\to}0$,
where

$\nu\bigg{(}c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}),~{}c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}^{\prime})\bigg{)}\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\left[\left\\{c^{\top}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}\big{)}-c^{\top}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{\prime}\big{)}\right\\}^{2}\right]^{1/2}.$

By display (B.10) and Cramer Wold device, we have that

$\sqrt{n}\left\\{\hat{\Phi}_{1}^{(n)}(\hat{\beta}_{1}^{(n)})-\Phi_{1}(\hat{\beta}_{1}^{(n)})\right\\}=\sqrt{n}\left\\{\hat{\Phi}_{1}^{(n)}(\beta_{1}^{*})-\Phi_{1}(\beta_{1}^{*})\right\\}+o_{P}(1).$
(B.11)

With the above result, for the base case of the induction argument, we now
just need to show that
$\sqrt{n}\big{(}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{)}=O_{P}(1)$.

Showing that
$\sqrt{n}\big{(}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{)}=O_{P}(1)$. By the
definitions of $\hat{\beta}_{1}^{(n)}$ and $\beta_{1}^{*}$ from displays (3.9)
and (3.7) respectively, we can rewrite the left-hand side of the display
(B.11) above:

$\sqrt{n}\big{\\{}\underbrace{\hat{\Phi}_{1}^{(n)}(\hat{\beta}_{1}^{(n)})}_{=o_{P}(1/\sqrt{n})}-\Phi_{1}(\hat{\beta}_{1}^{(n)})\big{\\}}=\sqrt{n}\big{\\{}\underbrace{\Phi_{1}(\beta_{1}^{*})}_{=0}-\Phi_{1}(\hat{\beta}_{1}^{(n)})\big{\\}}+o_{P}(1).$

By Condition 4 (Differentiability of Policy Parameter Estimating Functions),
the mapping $\beta_{1}\mapsto\Phi_{1}(\beta_{1})$ is differentiable at
$\beta_{1}=\beta_{1}^{*}$ with derivative matrix
$\dot{\Phi}_{1}^{*}\triangleq\frac{\partial{}}{\partial{\beta_{1}}}\Phi_{1}(\beta_{1})\big{|}_{\beta_{1}=\beta_{1}^{*}}$.
So,

$=-\sqrt{n}\dot{\Phi}_{1}^{*}\big{(}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{)}+\sqrt{n}o_{P}\big{(}\big{\|}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{\|}_{2}\big{)}+o_{P}(1).$

In summary, we have that

$\sqrt{n}\left\\{\hat{\Phi}_{1}^{(n)}(\beta_{1}^{*})-\Phi_{1}(\beta_{1}^{*})\right\\}+o_{P}(1)=-\sqrt{n}\dot{\Phi}_{1}^{*}\big{(}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{)}+\sqrt{n}o_{P}\big{(}\big{\|}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{\|}_{2}\big{)}.$

By Condition 4 (Differentiability of Policy Parameter Estimating Functions),
$\dot{\Phi}_{1}^{*}$ is invertible, so
$\big{[}\dot{\Phi}_{1}^{*}\big{]}^{-1}=O(1)$ and

$\sqrt{n}\big{[}\dot{\Phi}_{1}^{*}\big{]}^{-1}\left\\{\hat{\Phi}_{1}^{(n)}(\beta_{1}^{*})-\Phi_{1}(\beta_{1}^{*})\right\\}+o_{P}(1)\\\
=-\sqrt{n}\big{(}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{)}+\sqrt{n}O(1)o_{P}\big{(}\big{\|}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{\|}_{2}\big{)}.$
(B.12)

By the central limit theorem (for i.i.d. data),

$\sqrt{n}\big{[}\dot{\Phi}_{1}^{*}\big{]}^{-1}\big{\\{}\hat{\Phi}_{1}^{(n)}(\beta_{1}^{*})-\underbrace{\Phi_{1}(\beta_{1}^{*})}_{=0}\big{\\}}=\frac{1}{\sqrt{n}}\big{[}\dot{\Phi}_{1}^{*}\big{]}^{-1}\sum_{i=1}^{n}\phi_{1}\big{(}\mathcal{H}_{1}^{(i)};\beta_{1}^{*}\big{)}+o_{P}(1)\\\
\overset{D}{\to}\mathcal{N}\left(0,~{}\big{[}\dot{\Phi}_{1}^{*}\big{]}^{-1}\Sigma_{1}\big{[}\dot{\Phi}_{1}^{*}\big{]}^{-1,\top}\right),$
(B.13)

where
$\Sigma_{1}=\mathbb{E}\big{[}\phi_{1}\big{(}\mathcal{H}_{1}^{(i)};\beta_{1}^{*}\big{)}^{\otimes
2}\big{]}$.

By displays (B.12) and (B.13) we have that
$-\sqrt{n}\big{(}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{)}+\sqrt{n}O(1)o_{P}\big{(}\big{\|}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{\|}_{2}\big{)}=O_{P}(1)$.
This implies that
$\sqrt{n}\big{(}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{)}=O_{P}(1)$; thus,
$\sqrt{n}O(1)o_{P}\big{(}\big{\|}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{\|}_{2}\big{)}=o_{P}(1)$.
Using these results, we have that

$\sqrt{n}\big{(}\hat{\beta}_{1}^{(n)}-\beta_{1}^{*}\big{)}=-\sqrt{n}\big{[}\dot{\Phi}_{1}^{*}\big{]}^{-1}\left\\{\hat{\Phi}_{1}^{(n)}(\beta_{1}^{*})-\Phi_{1}(\beta_{1}^{*})\right\\}+o_{P}(1)=O_{P}(1).$

Induction Step. For the induction step, for a given $t>1$, we make the
induction assumption that
$\sqrt{n}\big{(}\hat{\beta}_{1:t-1}^{(n)}-\beta_{1:t-1}^{*}\big{)}=O_{P}(1)$.
We then show that
$\sqrt{n}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}=O_{P}(1)$ and
$\sqrt{n}\big{\\{}\hat{\Phi}_{1:t}^{(n)}(\hat{\beta}_{1:t}^{(n)})-\Phi_{1:t}(\hat{\beta}_{1:t}^{(n)})\big{\\}}=\sqrt{n}\big{\\{}\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\big{\\}}+o_{P}(1)$.

Stochastic Equicontinuity Result. First, we will apply Lemma D.6 (Stochastic
Equicontinuity) to get that for any fixed vector $c\in{}^{d_{1:t}}$ (we use
$d_{1:t}\triangleq\sum_{t^{\prime}=1}^{t}d_{t^{\prime}}$),

$\sqrt{n}c^{\top}\left\\{\hat{\Phi}_{1:t}^{(n)}(\hat{\beta}_{1:t}^{(n)})-\Phi_{1:t}(\hat{\beta}_{1:t}^{(n)})\right\\}=\sqrt{n}c^{\top}\left\\{\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\right\\}+o_{P}(1).$
(B.14)

We are able to apply Lemma D.6 (Stochastic Equicontinuity) because the
following assumptions hold:

  * •

Conditions 2 (Minimum Exploration) and 3 (Lipschitz Policy Functions) hold.

  * •

$\hat{\beta}_{1:t-1}^{(n)}-\beta_{1:t-1}^{*}=O_{P}(1/\sqrt{n})$ by our
induction assumption.

  * •

Since assumption (NP1) (Finite Bracketing Integral) and Condition 3 (Lipschitz
Policy Function) hold, we can apply Lemma A.5 (Finite Bracketing Integral) to
get that for any vector $c\in{}^{d_{t}}$,

$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\left(\epsilon,~{}\big{\\{}\pi_{2:t}(\,\cdot\,;\beta_{1:t-1})c^{\top}\phi_{t}(\,\cdot\,;\beta_{t})\big{\\}}_{\beta_{1:t}\in
B_{1:t}},~{}L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon<\infty,$

where
$\pi_{2:t}(\,\cdot\,;\beta_{1:t-1})\triangleq\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}(\,\cdot\,;\beta_{t^{\prime}-1})$;
specifically see the result in Remark 8 part (b2) below the statement of Lemma
A.5.

  * •

$\hat{\beta}_{1:t}^{(n)}\overset{P}{\to}\beta_{1:t}^{*}$ by Condition 1. Thus,
by assumption (NP2) and continuous mapping theorem we have that for any vector
$c\in{}^{d_{t}}$,
$\nu\left(\pi_{2:t}(\,\cdot\,;\hat{\beta}_{1:t-1}^{(n)})c^{\top}\phi_{t}(\,\cdot\,;\hat{\beta}_{t}^{(n)}),~{}\pi_{2:t}(\,\cdot\,;\beta_{1:t-1}^{*})c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}^{*})\right)\overset{P}{\to}0$,
where

$\nu\bigg{(}\pi_{2:t}(\,\cdot\,;\beta_{1:t-1})c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}),~{}\pi_{2:t}(\,\cdot\,;\beta_{1:t-1}^{\prime})c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}^{\prime})\bigg{)}\\\
\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\left[\left\\{\pi_{2:t}(\,\cdot\,;\beta_{1:t-1})c^{\top}\phi_{t}(\,\cdot\,;\beta_{t})-\pi_{2:t}(\,\cdot\,;\beta_{1:t-1}^{\prime})c^{\top}\phi_{t}(\,\cdot\,;\beta_{t}^{\prime})\right\\}^{2}\right]^{1/2}.$

By display (B.14) and Cramer Wold device, we have that

$\sqrt{n}\left\\{\hat{\Phi}_{1:t}^{(n)}(\hat{\beta}_{1:t}^{(n)})-\Phi_{1:t}(\hat{\beta}_{1:t}^{(n)})\right\\}=\sqrt{n}\left\\{\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\right\\}+o_{P}(1).$
(B.15)

With the above result, for the induction step of the induction argument, we
now just need to show that
$\sqrt{n}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}=O_{P}(1)$.

Showing that
$\sqrt{n}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}=O_{P}(1)$. By
the definitions of $\hat{\beta}_{1:t}^{(n)}$ and $\beta_{1:t}^{*}$ from
displays (3.9) and (3.7) respectively, we can rewrite the left-hand side of
the display (B.15) above:

$\sqrt{n}\big{[}\underbrace{\hat{\Phi}_{1:t}^{(n)}(\hat{\beta}_{1:t}^{(n)})}_{=o_{P}(1/\sqrt{n})}-\Phi_{1:t}(\hat{\beta}_{1:t}^{(n)})\big{]}=\sqrt{n}\big{[}\underbrace{\Phi_{1:t}(\beta_{1:t}^{*})}_{=0}-\Phi_{1:t}(\hat{\beta}_{1:t}^{(n)})\big{]}+o_{P}(1).$

By Condition 4 (Differentiability of Policy Parameter Estimating Functions),
the mapping $\beta_{1:t}\mapsto\Phi_{1:t}(\beta_{1:t})$ is differentiable at
$\beta_{1:t}=\beta_{1:t}^{*}$ with the derivative matrix
$\dot{\Phi}_{1:t}^{*}\triangleq\frac{\partial{}}{\partial{\beta_{1:t}}}\Phi_{1:t}(\beta_{1:t})\big{|}_{\beta_{1:t}=\beta_{1:t}^{*}}$.
So,

$=-\sqrt{n}\dot{\Phi}_{1:t}^{*}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}+\sqrt{n}o_{P}\big{(}\big{\|}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{\|}_{2}\big{)}+o_{P}(1).$

In summary, we have that

$\sqrt{n}\left\\{\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\right\\}+o_{P}(1)=-\sqrt{n}\dot{\Phi}_{1:t}^{*}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}+\sqrt{n}o_{P}\big{(}\big{\|}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{\|}_{2}\big{)}.$

By Condition 4, we can apply Lemma B.4 (Invertibility of
$\dot{\Phi}_{1:t}^{*}$) to get that $\dot{\Phi}_{1:t}^{*}$ is invertible; so
$\big{[}\dot{\Phi}_{1:t}^{*}\big{]}^{-1}=O(1)$ and

$\sqrt{n}\big{[}\dot{\Phi}_{1:t}^{*}\big{]}^{-1}\left\\{\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\right\\}+o_{P}(1)\\\
=-\sqrt{n}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}+\sqrt{n}O(1)o_{P}\big{(}\big{\|}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{\|}_{2}\big{)}.$
(B.16)

For now, we take as given that the following result in display (B.17) holds;
we prove this at the end of this proof.

$\sqrt{n}\big{[}\dot{\Phi}_{1:t}^{*}\big{]}^{-1}\left\\{\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\right\\}=O_{P}(1).$
(B.17)

By displays (B.16) and (B.17) we have that
$-\sqrt{n}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}+\sqrt{n}O(1)o_{P}\big{(}\big{\|}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{\|}_{2}\big{)}=O_{P}(1)$.
This implies that
$\sqrt{n}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}=O_{P}(1)$;
thus,
$\sqrt{n}O(1)o_{P}\big{(}\big{\|}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{\|}_{2}\big{)}=o_{P}(1)$.
Using these results, we have that

$\sqrt{n}\big{(}\hat{\beta}_{1:t}^{(n)}-\beta_{1:t}^{*}\big{)}=-\sqrt{n}\big{[}\dot{\Phi}_{1:t}^{*}\big{]}^{-1}\left\\{\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\right\\}+o_{P}(1)=O_{P}(1).$

We now show that display (B.17) holds.. For any fixed vector
$c=[c_{1},c_{2},\cdots,c_{t}]\in{}^{d_{1:t}}$,

$\sqrt{n}c^{\top}\big{\\{}\hat{\Phi}_{1:t-1}^{(n)}(\beta_{1:t}^{*})-\underbrace{\Phi_{1:t}(\beta_{1:t}^{*})}_{=0}\big{\\}}\\\
=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\sum_{k=1}^{t}c_{k}^{\top}W_{2:k}^{(i)}(\beta_{1:k-1}^{*},\hat{\beta}_{1:k-1}^{(n)})\phi_{k}(\mathcal{H}_{k}^{(i)};\beta_{k}^{*})\overset{D}{\to}\mathcal{N}\left(0,c^{\top}\Sigma_{1:t}c\right),$
(B.18)

where

$\Sigma_{1:t}\triangleq\mathbb{E}_{\pi_{2}^{*}}\left[\begin{pmatrix}\phi_{1}(\mathcal{H}_{1}^{(i)};\beta_{1}^{*})\\\
\phi_{2}(\mathcal{H}_{2}^{(i)};\beta_{2}^{*})\\\ \vdots\\\
\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t}^{*})\end{pmatrix}^{\otimes
2}\right].$

The asymptotic normality result above holds by Theorem D.4 (Weighted
Martingale Triangular Array Central Limit Theorem). Specifically we can apply
Theorem D.4 because:

  * •

Conditions 2 (Minimum Exploration) and 3 (Lipschitz Policy Functions) hold.

  * •

By our induction assumption,
$\hat{\beta}_{t^{\prime}}^{(n)}-\beta_{t^{\prime}}^{*}=O_{P}(1/\sqrt{n})$ for
all $t^{\prime}\in[1\colon t-1]$.

  * •

$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}\sum_{t^{\prime}=1}^{t}\phi_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)};\beta_{t^{\prime}}^{*})\big{|}^{2+\alpha}\big{]}<\infty$
by the Finite Bracketing Integral assumption (NP1).

Thus, by Cramer-Wold device and display (B.18) we have that

$\sqrt{n}\left\\{\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\right\\}\overset{D}{\to}\mathcal{N}(0,\Sigma_{1:t}).$

By Condition 4, we can apply Lemma B.4 (Invertibility of
$\dot{\Phi}_{1:t}^{*}$) to get that $\dot{\Phi}_{1:t}^{*}$ is invertible.
Thus, by continuous mapping theorem,

$\sqrt{n}\big{[}\dot{\Phi}_{1:t}^{*}\big{]}^{-1}\left\\{\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\right\\}\overset{D}{\to}\mathcal{N}\left(0,\big{[}\dot{\Phi}_{1:t}^{*}\big{]}^{-1}\Sigma_{1:t}\big{[}\dot{\Phi}_{1:t}^{*}\big{]}^{-1,\top}\right).$

The above implies that display (B.17) holds, i.e., that
$\sqrt{n}\big{[}\dot{\Phi}_{1:t}^{*}\big{]}^{-1}\big{\\{}\hat{\Phi}_{1:t}^{(n)}(\beta_{1:t}^{*})-\Phi_{1:t}(\beta_{1:t}^{*})\big{\\}}=O_{P}(1)$.
$\blacksquare$

###  B.4 Invertibility of $\dot{\Phi}_{1:t}^{*}$ (Lemma B.4)

######  Lemma B.4 (Invertibility of $\dot{\Phi}_{1:t}^{*}$).

Under Condition 4 (Differentiability of Policy Parameter Estimating
Functions), for each $t\in[1\colon T-1]$, $\dot{\Phi}_{1:t}^{*}$ is
invertible.

In the proof of Lemma B.4 we will use the following proposition:

######  Proposition 1 (Blockwise Inversion of Matrix).

Let $A\in{}^{k\times k}$, $B\in{}^{k\times j}$, $C\in{}^{j\times k}$, and
$D\in{}^{j\times j}$. If $A$ and $D-CA^{-1}B$ are invertible then

$\begin{bmatrix}A&&B\\\
C&&D\end{bmatrix}^{-1}=\begin{bmatrix}A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1}&&-A^{-1}B(D-CA^{-1}B)^{-1}\\\
-(D-CA^{-1}B)^{-1}CA^{-1}&&(D-CA^{-1}B)^{-1}\end{bmatrix}.$

Furthermore, in the special case that $B=0$,

$\begin{bmatrix}A&&0\\\ C&&D\end{bmatrix}^{-1}=\begin{bmatrix}A^{-1}&&0\\\
-D^{-1}CA^{-1}&&D^{-1}\end{bmatrix}.$

This is a result is proved in Proposition 3.9.7 of Bernstein [2018].

Proof of Lemma B.4. By Condition 4 (Differentiability of Policy Parameter
Estimating Functions), the mapping $\beta_{1:t}\mapsto\Phi_{1:t}(\beta_{1:t})$
is differentiable at $\beta_{1:t}=\beta_{1:t}^{*}$. Let
$\dot{\Phi}_{1:t}^{*}\triangleq\frac{\partial{}}{\partial{\beta_{1:t}}}\Phi_{t}(\beta_{1:t})\big{|}_{\beta_{1:t}=\beta_{1:t}^{*}}$
Specifically,

$\dot{\Phi}_{1:t}^{*}=\frac{\partial{}}{\partial{\beta_{1:t}}}\mathbb{E}_{\pi(\beta_{1:t-1})}\begin{bmatrix}\phi_{1}(\mathcal{H}_{1}^{(i)};\beta_{1})\\\
\phi_{2}(\mathcal{H}_{2}^{(i)};\beta_{2})\\\ \vdots\\\
\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\end{bmatrix}\bigg{|}_{\beta_{1:t}=\beta_{1:t}^{*}}=\begin{bmatrix}\dot{\Phi}_{1}^{*}&&0&&0&&\ldots&&0\\\
V_{2,1}&&\dot{\Phi}_{2}^{*}&&0&&\ldots&&0\\\
V_{3,1}&&V_{3,2}&&\dot{\Phi}_{3}^{*}&&\ldots&&0\\\
\vdots&&\vdots&&\vdots&&\ddots&&\vdots\\\
V_{t,1}&&V_{t,2}&&V_{t,3}&&\ldots&&\dot{\Phi}_{t}^{*}\end{bmatrix},$

where
$V_{t,s}\triangleq\frac{\partial{}}{\partial{\beta_{s}}}\mathbb{E}_{\pi_{2:t}^{*}}\left[\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t}^{*})W_{s+1}^{(i)}(\beta_{s},\beta_{s}^{*})\right]\big{|}_{\beta_{s}=\beta_{s}^{*}}\in{}^{d_{t}\times
d_{s}}$ and
$\dot{\Phi}_{t}^{*}\triangleq\frac{\partial{}}{\partial{\beta_{t}}}\Phi_{t}(\beta_{1:t-1}^{*},\beta_{t})\big{|}_{\beta_{t}=\beta_{t}^{*}}\triangleq\frac{\partial{}}{\partial{\beta_{t}}}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t})\big{]}\big{|}_{\beta_{t}=\beta_{t}^{*}}$.

Note that by repeatedly applying Proposition 1 we can show that
$\dot{\Phi}_{1:t}^{*}$ is invertible. Moreover, we will show that the inverse
of $\dot{\Phi}_{1:t}^{*}$ is lower block triangular. To see this, consider the
following induction argument:

  * •

Base case: By Condition 4 (Differentiability of Policy Parameter Estimating
Functions), $\dot{\Phi}_{1}^{*}$ and $\dot{\Phi}_{2}^{*}$ are both invertible.
Thus, by Proposition 1, the matrix $\begin{bmatrix}\dot{\Phi}_{1}^{*}&0\\\
V_{2,1}&\dot{\Phi}_{2}^{*}\end{bmatrix}$ is invertible; moreover, its inverse
is lower block triangular.

  * •

Induction step: Suppose we know that for some $t\geq 2$, the inverse of the
following lower block triangular matrix is invertible:

$\begin{bmatrix}\dot{\Phi}_{1}^{*}&0&0&\ldots&0\\\
V_{2,1}&\dot{\Phi}_{2}^{*}&0&\ldots&0\\\
V_{3,1}&V_{3,2}&\dot{\Phi}_{3}^{*}&\ldots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
V_{t-1,1}&V_{t-1,2}&V_{t-1,3}&\ldots&\dot{\Phi}_{t-1}^{*}\end{bmatrix}.$
(B.19)

By Condition 4 (Differentiability of Policy Parameter Estimating Functions),
$\dot{\Phi}_{t}^{*}$ is invertible. By Proposition 1 we can conclude that the
following matrix is invertible and lower block triangular:

$\begin{bmatrix}\dot{\Phi}_{1}^{*}&0&0&\ldots&0&0\\\
V_{2,1}&\dot{\Phi}_{2}^{*}&0&\ldots&0&0\\\
V_{3,1}&V_{3,2}&\dot{\Phi}_{3}^{*}&\ldots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
V_{t-1,1}&V_{t-1,2}&V_{t-1,3}&\ldots&\dot{\Phi}_{t-1}^{*}&0\\\
V_{t,1}&V_{t,2}&V_{t,3}&\ldots&V_{t,t-1}&\dot{\Phi}_{t}^{*}\end{bmatrix}.$

When applying Proposition 1, take the matrix from display (B.19) (upper left-
hand side of the matrix above) to be matrix $A$; take $\dot{\Phi}_{t}^{*}$ to
be matrix $D$; take
$\begin{bmatrix}V_{t,1}&V_{t,2}&V_{t,3}&\ldots&V_{t,t-1}\end{bmatrix}$ to be
matrix $C$; and take the block of zeros above $\dot{\Phi}_{t}^{*}$ to be
matrix $B$.

By the above argument, $\dot{\Phi}_{1:t}^{*}$ is invertible for any
$t\in[1\colon T-1]$. $~{}\blacksquare$

##  Appendix C Main Asymptotic Results

Overview of Supplement C Results.

  * •

Section C.1: Consistency of $\hat{\theta}^{(n)}$ (Theorem 5.1)

  * •

Section C.2: Equivalent Formulations for the Adaptive Sandwich Variance (Lemma
C.1)

  * •

Section C.3: Asymptotic Normality of $\hat{\theta}^{(n)}$ (Theorem 5.2)

###  C.1 Consistency of $\hat{\theta}^{(n)}$ (Theorem 5.1)

Proof of Theorem 5.1. Note that this argument is extremely similar to the
proof for Theorem B.1. The proof will use the estimating functions
$\Psi\big{(}\beta_{1:T-1},\theta\big{)}$ and
$\hat{\Psi}^{(n)}\big{(}\beta_{1:T-1},\theta\big{)}$ defined earlier in
displays (5.6) and (5.7) respectively.

For now, we take as given that display (B.4) below holds; we will show this
result holds at the end of this proof.

$\left\|\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\theta^{*}\big{)}-\Psi{}\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}\right\|_{1}=o_{P}(1).$
(C.1)

Let $\epsilon>0$. By assumption (C1), there exists some $\eta>0$ such that if
$\theta\in{}^{d_{\theta}}$ satisfies
$\big{\|}\theta-\theta^{*}\big{\|}_{1}>\epsilon$, then
$\big{\|}\Psi{}\big{(}\beta_{1:T-1}^{*},\theta\big{)}\big{\|}_{1}=\big{\|}\mathbb{E}_{\pi_{2:T}^{*}}\big{[}\psi(\mathcal{H}_{T}^{(i)};\theta)\big{]}\big{\|}_{1}>\eta>0$.
Thus,

$\mathbb{P}\left(\big{\|}\hat{\theta}^{(n)}-\theta^{*}\big{\|}_{1}>\epsilon\right)\leq\mathbb{P}\left(\big{\|}\Psi{}\big{(}\beta_{1:T-1}^{*},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}>\eta\right).$

Note
$\big{\|}\Psi{}\big{(}\beta_{1:T-1}^{*},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}=\big{\|}\Psi{}\big{(}\beta_{1:T-1}^{*},\hat{\theta}^{(n)}\big{)}-\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}+\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}\\\
\leq\big{\|}\Psi{}\big{(}\beta_{1:T-1}^{*},\hat{\theta}^{(n)}\big{)}-\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}+\big{\|}\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}\\\
=\big{\|}\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}+o_{P}(1)$;
the last equality holds by display (C.1). Thus,

$\leq\mathbb{P}\left(\big{\|}\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}>\eta-
o_{P}(1)\right).$

Note that
$\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}=\frac{1}{n}\sum_{i=1}^{n}W_{2:T}^{(i)}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\beta}_{1:T-1}^{(n)}\big{)}\psi\big{(}\mathcal{H}_{T}^{(i)};\hat{\theta}^{(n)}\big{)}\\\
=\frac{1}{n}\sum_{i=1}^{n}\psi\big{(}\mathcal{H}_{T}^{(i)};\hat{\theta}^{(n)}\big{)}=o_{P}(1/\sqrt{n})=o_{P}(1)$;
the second to last equality holds by the definition of $\hat{\theta}^{(n)}$
from display (3.2). Thus,

$=\mathbb{P}\left(\big{\|}\hat{\Psi}^{(n)}{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}-\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}>\eta-
o_{P}(1)\right).$

By assumption (C2), for any $\delta>0$, there exists some $k<\infty$ such that
$\limsup_{n\to\infty}\mathbb{P}\big{(}\big{\|}\hat{\theta}^{(n)}\big{\|}_{1}>k\big{)}\leq\delta$.
We use this $k$ below:

$=\mathbb{P}\left(\big{\|}\hat{\Psi}^{(n)}{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}-\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}\left\\{\mathbb{I}_{\|\hat{\theta}^{(n)}\|_{1}>k}+\mathbb{I}_{\|\hat{\theta}^{(n)}\|_{1}\leq
k}\right\\}>\eta-o_{P}(1)\right)$
$\leq\mathbb{P}\left(\big{\|}\hat{\Psi}^{(n)}{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}-\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}~{}\mathbb{I}_{\|\hat{\theta}^{(n)}\|_{1}\leq
k}>\eta/2-o_{P}(1)\right)\\\
+\mathbb{P}\left(\big{\|}\hat{\Psi}^{(n)}{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}-\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}~{}\mathbb{I}_{\|\hat{\theta}^{(n)}\|_{1}>k}>\eta/2-o_{P}(1)\right)$
$\leq\mathbb{P}\left(\big{\|}\hat{\Psi}^{(n)}{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}-\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\big{\|}_{1}~{}\mathbb{I}_{\|\hat{\theta}^{(n)}\|_{1}\leq
k}>\eta/2-o_{P}(1)\right)\\\
+\mathbb{P}\left(\big{\|}\hat{\theta}^{(n)}\big{\|}_{1}>k\right)+o(1)$
$\leq\mathbb{P}\bigg{(}\sup_{\theta\in{}^{d_{\theta}}\textnormal{~{}s.t.~{}}\|\theta\|_{1}\leq
k}\big{\|}\hat{\Psi}^{(n)}{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\theta\big{)}-\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\theta\big{)}\big{\|}_{1}>\eta/2-o_{P}(1)\bigg{)}\\\
+\mathbb{P}\left(\big{\|}\hat{\theta}^{(n)}\big{\|}_{1}>k\right)+o(1)$

Since $\hat{\beta}_{1:T-1}^{(n)}\overset{P}{\to}\beta_{1:T-1}^{*}$ by
Condition 1, thus $\mathbb{I}_{\hat{\beta}_{1:T-1}^{(n)}\in
B_{1:T-1}}\overset{P}{\to}1$; recall that $B_{1:T-1}\subset{}^{d_{1:T-1}}$ is
a compact subset whose interior contains $\beta_{1:T-1}^{*}$. Thus,

$\leq\underbrace{\mathbb{P}\bigg{(}\sup_{\theta\in{}^{d_{\theta}}\textnormal{~{}s.t.~{}}\|\theta\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}\big{\|}\hat{\Psi}^{(n)}{}\big{(}\beta_{1:T-1},\theta\big{)}-\Psi{}\big{(}\beta_{1:T-1},\theta\big{)}\big{\|}_{1}>\eta/2-o_{P}(1)\bigg{)}}_{=o(1)}\\\
+\underbrace{\mathbb{P}\left(\big{\|}\hat{\theta}^{(n)}\big{\|}_{1}>k\right)}_{\leq\delta}+o(1).$

Note that the above converges to zero as $n\to\infty$ for the following
reasons:

  * •

By assumption (CP2),
$\limsup_{n\to\infty}\mathbb{P}\big{(}\big{\|}\hat{\theta}^{(n)}\big{\|}_{1}>k\big{)}\leq\delta$
and $\delta$ can be made arbitrarily small.

  * •

Note that by Cramer Wold device, to show that

$\sup_{\theta\in{}^{d_{\theta}}\textnormal{~{}s.t.~{}}\|\theta\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}\left\|\hat{\Psi}^{(n)}{}\big{(}\beta_{1:T-1},\theta\big{)}-\Psi{}\big{(}\beta_{1:T-1},\theta\big{)}\right\|_{1}\overset{P}{\to}0,$

it is sufficient to show that for any vector $c\in{}^{d_{\theta}}$,

$\sup_{\theta\in{}^{d_{\theta}}\textnormal{~{}s.t.~{}}\|\theta\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}c^{\top}\left\\{\hat{\Psi}^{(n)}{}\big{(}\beta_{1:T-1},\theta\big{)}-\Psi{}\big{(}\beta_{1:T-1},\theta\big{)}\right\\}\overset{P}{\to}0.$

Also note that

$\sup_{\theta\in{}^{d_{\theta}}\textnormal{~{}s.t.~{}}\|\theta\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}c^{\top}\left\\{\hat{\Psi}^{(n)}{}\big{(}\beta_{1:T-1},\theta\big{)}-\Psi{}\big{(}\beta_{1:T-1},\theta\big{)}\right\\}$
$=\sup_{\theta\in{}^{d_{\theta}}\textnormal{~{}s.t.~{}}\|\theta\|_{1}\leq
k}~{}\sup_{\beta_{1:t-1}\in
B_{1:t-1}}\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}W_{2:T}^{(i)}(\beta_{1:T-1},\hat{\beta}_{1:T-1}^{(n)})c^{\top}\psi(\mathcal{H}_{T}^{(i)};\theta)\\\
-\mathbb{E}\left[W_{2:T}^{(i)}(\beta_{1:T-1},\hat{\beta}_{1:T-1}^{(n)})c^{\top}\psi(\mathcal{H}_{T}^{(i)};\theta)\right]\bigg{\\}}\overset{P}{\to}0.$

The above convergence result holds by Theorem D.2 (Weighted Martingale
Triangular Array Uniform Weak Law of Large Numbers). Specifically we are able
to apply Theorem D.2 because Condition 2 holds and
$N_{[~{}]}\left(\epsilon,\mathcal{F}_{\Pi
c^{\top}\psi}(B_{1:T-1},k),L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\right)<\infty$
for any $c\in{}^{d_{\theta}}$ and any $\epsilon>0$, where

$\mathcal{F}_{\Pi
c^{\top}\psi}(B_{1:T-1},k)\triangleq\bigg{\\{}\bigg{[}\prod_{t=2}^{T}\pi_{t}(\,\cdot\,;\beta_{t-1})\bigg{]}c^{\top}\psi(\,\cdot\,;\theta\big{)}\bigg{\\}}_{\beta_{1:T-1}\in
B_{1:T-1},~{}\theta\in{}^{d_{\theta}}\textnormal{~{}s.t.~{}}\|\theta\|_{1}\leq
k}.$

The above finite bracketing number result holds since using assumption (CP3)
and Condition 3, we can apply by Lemma A.5 (specifically see Remark 8 part
(a1)).

We now show that display (C.1) holds. Let $\beta_{1:T-1}\in B_{1:T-1}$.

$\left\|\Psi{}\big{(}\beta_{1:T-1},\theta^{*}\big{)}-\Psi{}\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}\right\|_{1}$
$=\bigg{\|}\mathbb{E}\bigg{[}\bigg{\\{}\prod_{t=2}^{T}W_{t}^{(i)}\big{(}\beta_{t-1},\hat{\beta}_{t-1}^{(n)}\big{)}-W_{t}^{(i)}\big{(}\beta_{t-1}^{*},\hat{\beta}_{t-1}^{(n)}\big{)}\bigg{\\}}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\bigg{]}\bigg{\|}_{1}$
$=\bigg{\|}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\bigg{\\{}\prod_{t=2}^{T}W_{t}^{(i)}\big{(}\beta_{t-1},\beta_{t-1}^{*}\big{)}-W_{t}^{(i)}\big{(}\beta_{t-1}^{*},\beta_{t-1}^{*}\big{)}\bigg{\\}}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\bigg{]}\bigg{\|}_{1}$

By Jensen’s inequality,

$\leq\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\bigg{|}\prod_{t=2}^{T}W_{t}^{(i)}\big{(}\beta_{t-1},\beta_{t-1}^{*}\big{)}-W_{t}^{(i)}\big{(}\beta_{t-1}^{*},\beta_{t-1}^{*}\big{)}\bigg{|}\big{\|}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\big{\|}_{1}\bigg{]}$

By definition of $W_{t}^{(i)}\big{(}\beta_{t-1},\beta_{t-1}^{*}\big{)}$ from
display (5.5),

$=\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\bigg{|}\prod_{t=2}^{T}\pi_{t}\big{(}A_{t}^{(i)},S_{t}^{(i)};\beta_{t-1}\big{)}-\prod_{t=2}^{T}\pi_{t}\big{(}A_{t}^{(i)},S_{t}^{(i)};\beta_{t-1}^{*}\big{)}\bigg{|}\\\
\bigg{\\{}\prod_{t=2}^{T}\frac{1}{\pi_{t}^{*}(A_{t}^{(i)},S_{t}^{(i)})}\bigg{\\}}\big{\|}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\big{\|}_{1}\bigg{]}$

By Condition 2 (Minimum Exploration),
$\pi_{t}^{*}\big{(}A_{t}^{(i)},S_{t}^{(i)}\big{)}^{-1}\leq\pi_{\min}^{-1}$
a.s. Thus,

$\leq\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\bigg{|}\prod_{t=2}^{T}\pi_{t}\big{(}A_{t}^{(i)},S_{t}^{(i)};\beta_{t-1}\big{)}-\prod_{t=2}^{T}\pi_{t}\big{(}A_{t}^{(i)},S_{t}^{(i)};\beta_{t-1}^{*}\big{)}\bigg{|}\big{\|}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\big{\|}_{1}\bigg{]}$

By Condition 3 and Lemma A.4 (Product of Lipschitz Policy Functions are
Lipschitz),

$\leq\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\big{\|}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\big{\|}_{1}\bigg{\\{}\sum_{t=2}^{T}\dot{\pi}_{t}(A_{t}^{(i)},S_{t}^{(i)})\bigg{\\}}\big{\|}\beta_{1:T-1}-\beta_{1:T-1}^{*}\big{\|}_{2}\bigg{]}$

By linearity of expectations,

$=\pi_{\min}^{-(T-1)}\bigg{\\{}\sum_{t=2}^{T}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\|}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\big{\|}_{1}\dot{\pi}_{t}(A_{t}^{(i)},S_{t}^{(i)})\right]\bigg{\\}}\big{\|}\beta_{1:T-1}-\beta_{1:T-1}^{*}\big{\|}_{2}.$

Thus, by consolidating the above results, we have that

$\big{\|}\Psi{}\big{(}\hat{\beta}_{1:T-1}^{(n)},\theta^{*}\big{)}-\Psi{}\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}\big{\|}_{1}\\\
\leq\pi_{\min}^{-(T-1)}\bigg{\\{}\sum_{t=2}^{T}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\|}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\big{\|}_{1}\dot{\pi}_{t}(A_{t}^{(i)},S_{t}^{(i)})\right]\bigg{\\}}\big{\|}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\big{\|}_{2}=o_{P}(1).$

The last limit above holds because

  * •

$\big{\|}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\big{\|}_{2}=o_{P}(1)$
since $\hat{\beta}_{1:T-1}^{(n)}\overset{P}{\to}\beta_{1:T-1}^{*}$ by
Condition 1.

  * •

By assumption (C3) (Finite Bracketing Number for Policy Functions), there
exists a function $F_{\psi}$ such that
$\big{\|}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\big{\|}_{1}\leq
F_{\psi}(\mathcal{H}_{t}^{(i)})$ a.s. and for all $t\in[2\colon T]$,
$\mathbb{E}_{\pi_{2:T}^{*}}\big{[}F_{\psi}\big{(}\mathcal{H}_{T}^{(i)}\big{)}\dot{\pi}_{t}(A_{t}^{(i)},S_{t}^{(i)})\big{]}<\infty$.
Thus,

$\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\|}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}\big{\|}_{1}\dot{\pi}_{t}(A_{t}^{(i)},S_{t}^{(i)})\right]\leq\mathbb{E}_{\pi_{2:T}^{*}}\left[F_{\psi}\big{(}\mathcal{H}_{T}^{(i)}\big{)}\dot{\pi}_{t}(A_{t}^{(i)},S_{t}^{(i)})\right]<\infty.$

We have now shown that display (C.1) holds. $\blacksquare$

###  C.2 Equivalent Formulations for the Adaptive Sandwich Variance (Lemma
C.1)

######  Lemma C.1 (Equivalent Formulations for the Adaptive Sandwich
Variance).

Let Condition 4 (Differentiability of Policy Parameter Estimating Functions)
and assumptions (N1) and (N2) from Theorem 5.2 (Asymptotic Normality hold).
Also let $\Sigma_{1:T}$ as defined in display (5.11) be finite.

Then, the lower-right $d_{\theta}\times d_{\theta}$ block of limiting variance
from display (5.10), i.e.,

$\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1}\Sigma_{1:T}\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1,\top},$ (C.2)

equals the adaptive sandwich variance, i.e.,
$[\dot{\Psi}^{*}]^{-1}\Sigma^{\mathrm{adapt}}[\dot{\Psi}^{*}]^{-1,\top}$ from
display (5.3).

Proof of Lemma C.1. By the definition of $\Sigma^{\mathrm{adapt}}$ from
display (5.3), it is sufficient to show that the lower-right $d_{\theta}\times
d_{\theta}$ block of the the limiting variance from display (C.2) above equals
the following

$[\dot{\Psi}^{*}]^{-1}\Sigma^{\mathrm{adapt}}[\dot{\Psi}^{*}]^{-1,\top}\\\
=[\dot{\Psi}^{*}]^{-1}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\bigg{\\{}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}+\dot{\Psi}^{*}\sum_{t=1}^{T-1}M_{t}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\bigg{\\}}^{\otimes
2}\bigg{]}[\dot{\Psi}^{*}]^{-1,\top}.$

Consider the following matrix from display (C.2) (the terms in the matrix
below are derivatives that exist by Condition 4, and assumptions (N1) and
(N2)):

$\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}.$ (C.3)

By Proposition 1 (Blockwise Inversion of Matrix), we have that for a block
matrix $\begin{bmatrix}A&&0\\\ C&&D\end{bmatrix}$, if square matrices $A$ and
$D$ are invertible, then the whole matrix is invertible and

$\begin{bmatrix}A&&0\\\ C&&D\end{bmatrix}^{-1}=\begin{bmatrix}A^{-1}&&0\\\
-D^{-1}CA^{-1}&&D^{-1}\end{bmatrix}.$

By Condition 4 and Lemma B.4 (Invertibility of $\dot{\Phi}_{1:t}^{*}$),
$\dot{\Phi}_{1:t}^{*}$ is invertible and $\dot{\Psi}^{*}$ is invertible by
assumption (N1). Thus the matrix from display (C.3) is invertible and

$\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1}=\begin{bmatrix}\big{\\{}\dot{\Phi}_{1:T-1}^{*}\big{\\}}^{-1}&&\bm{0}\\\
-\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\bm{V}_{T,1:T-1}\big{\\{}\dot{\Phi}_{1:T-1}^{*}\big{\\}}^{-1}&&\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\end{bmatrix}.$

Recall in display (5.32) we defined the following matrices:

$M_{1:T-1}\triangleq\big{[}M_{1},M_{2},\dots,M_{T-1}\big{]}\triangleq-\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\bm{V}_{T,1:T-1}\big{\\{}\dot{\Phi}_{1:T-1}^{*}\big{\\}}^{-1}\in{}^{d_{\theta}\times
d_{1:T-1}}.$ (C.4)

Above we use $d_{1:T-1}\triangleq\sum_{t=1}^{T-1}d_{t}$. Thus,

$\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1}\Sigma_{1:T}\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1,\top}$
$=\begin{bmatrix}\big{\\{}\dot{\Phi}_{1:T-1}^{*}\big{\\}}^{-1}&&\bm{0}\\\
M_{1:T-1}&&\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\end{bmatrix}\begin{bmatrix}\Sigma_{1:T-1}&U_{1:T-1,T}\\\
U_{T,1:T-1}&\Sigma\end{bmatrix}\begin{bmatrix}\big{\\{}\dot{\Phi}_{1:T-1}^{*}\big{\\}}^{-1}&&\bm{0}\\\
M_{1:T-1}&&\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\end{bmatrix}^{\top}.$ (C.5)

Above
$\Sigma\triangleq\mathbb{E}_{\pi_{2:T-1}^{*}}\left[\psi(\mathcal{H}_{T}^{(i)};\theta^{*})^{\otimes
2}\right]$,
$\Sigma_{1:T-1}\triangleq\mathbb{E}_{\pi_{2:T-1}^{*}}\left[\phi_{1:T-1}(\mathcal{H}_{T-1}^{(i)};\beta_{1:T-1}^{*})^{\otimes
2}\right]$,
$U_{T,1:T-1}\triangleq\mathbb{E}_{\pi_{2:T}^{*}}\left[\psi(\mathcal{H}_{T}^{(i)};\theta^{*})\phi_{1:T-1}(\mathcal{H}_{T-1}^{(i)};\beta_{1:T-1}^{*})^{\top}\right]$,
and $U_{1:T-1,T}\triangleq U_{T,1:T-1}^{\top}$, where

$\phi_{1:T-1}(\mathcal{H}_{T-1}^{(i)};\beta_{1:T-1}^{*})\triangleq\begin{pmatrix}\phi_{1}(\mathcal{H}_{1}^{(i)};\beta_{1}^{*})\\\
\phi_{2}(\mathcal{H}_{2}^{(i)};\beta_{2}^{*})\\\ \vdots\\\
\phi_{T-1}(\mathcal{H}_{T-1}^{(i)};\beta_{T-1}^{*})\end{pmatrix}.$ (C.6)

Thus display (C.5) equals the following:

$=\begin{bmatrix}\big{\\{}\dot{\Phi}_{1:T-1}^{*}\big{\\}}^{-1}\Sigma_{1:T-1}&&~{}\big{\\{}\dot{\Phi}_{1:T-1}^{*}\big{\\}}^{-1}U_{1:T-1,T}\\\
M_{1:T-1}\Sigma_{1:T-1}+\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}U_{T,1:T-1}&&~{}M_{1:T-1}U_{1:T-1,T}+\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\Sigma\end{bmatrix}\\\
\begin{bmatrix}\big{\\{}\dot{\Phi}_{1:T-1}^{*}\big{\\}}^{-1,\top}&&M_{1:T-1}^{\top}\\\
\bm{0}&&\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1,\top}\end{bmatrix}$

Thus, the lower-right $d_{\theta}\times d_{\theta}$ block of the product of
matrices above equals the following:

$M_{1:T-1}\Sigma_{1:T-1}M_{1:T-1}^{\top}+\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}U_{T,1:T-1}M_{1:T-1}^{\top}\\\
+M_{1:T-1}U_{1:T-1,T}\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1,\top}+\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\Sigma\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1,\top}$
$=\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\bigg{[}\dot{\Psi}^{*}M_{1:T-1}\Sigma_{1:T-1}M_{1:T-1}^{\top}\big{\\{}\dot{\Psi}^{*}\\}^{\top}+U_{T,1:T-1}M_{1:T-1}^{\top}\big{\\{}\dot{\Psi}^{*}\\}^{\top}\\\
+\dot{\Psi}^{*}M_{1:T-1}U_{1:T-1,T}+\Sigma\bigg{]}\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1,\top}$
$=\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\bigg{\\{}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}+\dot{\Psi}^{*}M_{1:T-1}\phi_{1:T-1}\big{(}\mathcal{H}_{T-1}^{(i)};\beta_{1:T-1}^{*}\big{)}\bigg{\\}}^{\otimes
2}\bigg{]}\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1,\top}$

By the definition of $M_{1:T-1}$ from display (C.4) and the definition of
$\phi_{1:T-1}$ from display (C.6),

$=\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\bigg{\\{}\psi\big{(}\mathcal{H}_{T}^{(i)};\theta^{*}\big{)}+\dot{\Psi}^{*}\sum_{t=1}^{T-1}M_{t}\phi_{t}\big{(}\mathcal{H}_{t}^{(i)};\beta_{t}^{*}\big{)}\bigg{\\}}^{\otimes
2}\bigg{]}\big{\\{}\dot{\Psi}^{*}\big{\\}}^{-1,\top}.$

We have now shown the desired result. $\blacksquare$

###  C.3 Asymptotic Normality of $\hat{\theta}^{(n)}$ (Theorem 5.2)

Proof of Theorem 5.2. By Lemma C.1 (Equivalent Formulations for the Adaptive
Sandwich Variance) above, it is sufficient to show that

$\sqrt{n}\begin{pmatrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{pmatrix}\overset{D}{\to}\mathcal{N}\left(0,\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1}\Sigma_{1:T}\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1,\top}\right).$

This proof will use the estimating functions
$\Psi\big{(}\beta_{1:T-1},\theta\big{)}$,
$\hat{\Psi}^{(n)}\big{(}\beta_{1:T-1},\theta\big{)}$,
$\Phi_{1:T-1}(\beta_{1:T-1})$, and $\hat{\Phi}_{1:T-1}^{(n)}(\beta_{1:T-1})$
defined earlier in displays (5.6), (5.7), (5.8), and (5.9) respectively.

We now state several equalities and discuss why they hold below:

$-\sqrt{n}\begin{bmatrix}\hat{\Phi}_{1:T-1}^{(n)}\big{(}\hat{\beta}_{1:T-1}^{(n)}\big{)}-\Phi_{1:T-1}\big{(}\hat{\beta}_{1:T-1}^{(n)}\big{)}\\\
\makebox[0.0pt][l]{$\smash{\underbrace{\phantom{\begin{matrix}\hat{\Psi}^{(n)}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\end{matrix}}}_{\text{$=o_{P}(1/\sqrt{n})$}}}$}\hat{\Psi}^{(n)}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}-\Psi\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\end{bmatrix}\\\
~{}~{}\\\
\underbrace{=}_{(a)}-\sqrt{n}\begin{bmatrix}\Phi_{1:T-1}\big{(}\beta_{1:T-1}^{*}\big{)}-\Phi_{1:T-1}\big{(}\hat{\beta}_{1:T-1}^{(n)}\big{)}\\\
\makebox[0.0pt][l]{$\smash{\underbrace{\phantom{\begin{matrix}\Psi\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}\end{matrix}}}_{\text{$=0$}}}$}\Psi\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}-\Psi\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\end{bmatrix}+o_{P}(1)\\\
~{}~{}\\\
\underbrace{=}_{(b)}\sqrt{n}\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}\begin{bmatrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{bmatrix}+\sqrt{n}o_{P}\left(\left\|\begin{matrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{matrix}\right\|_{2}\right)+o_{P}(1).$ (C.7)

Equality (a). Equality (a) above holds since
$\hat{\Psi}^{(n)}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}=o_{P}(1/\sqrt{n})$
and $\Psi\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}=0$ by the definitions of
$\hat{\theta}^{(n)}$ and $\theta^{*}$ from displays (3.2) and (3.1)
respectively; also since
$\hat{\Phi}_{1:T-1}^{(n)}\big{(}\hat{\beta}_{1:T-1}^{(n)}\big{)}=o_{P}(1/\sqrt{n})$
and $\Phi_{1:T-1}\big{(}\beta_{1:T-1}^{*}\big{)}=0$ by the definitions of
$\hat{\beta}_{t}^{(n)}$ and $\beta_{t}^{*}$ from displays (3.9) and (3.7).

Equality (b). Equality (b) above holds by a Taylor series expansion.
Specifically by assumptions (N1) and (N2), the mapping
$\big{(}\beta_{1:T-1},\theta\big{)}\mapsto\Psi(\beta_{1:T-1},\theta)$ is
differentiable at
$\big{(}\beta_{1:T-1},\theta\big{)}=\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}$.
Additionally the mapping $\beta_{1:T-1}\mapsto\Phi_{1:T-1}(\beta_{1:T-1})$ is
differentiable at $\beta_{1:T-1}=\beta_{1:T-1}^{*}$ by Condition 4. Thus,

$\frac{\partial{}}{\partial{(\beta_{1:T-1},\theta)}}\begin{bmatrix}\Phi_{1:T-1}(\beta_{1:T-1})\\\
\Psi{}(\beta_{1:T-1},\theta)\end{bmatrix}\bigg{|}_{(\beta_{1:T-1},\theta)=(\beta_{1:T-1}^{*},\theta^{*})}\\\
=\begin{bmatrix}\frac{\partial{}}{\partial{\beta_{1:T-1}}}\Phi_{1:T-1}(\beta_{1:T-1})\big{|}_{\beta_{1:T-1}=\beta_{1:T-1}^{*}}&&\frac{\partial{}}{\partial{\theta}}\Phi_{1:T-1}(\beta_{1:T-1}^{*})\big{|}_{\theta=\theta^{*}}\\\
\frac{\partial{}}{\partial{\beta_{1:T-1}}}\Psi{}(\beta_{1:T-1},\theta^{*})\big{|}_{\beta_{1:T-1}=\beta_{1:T-1}^{*}}&&\frac{\partial{}}{\partial{\theta}}\Psi{}(\beta_{1:T-1}^{*},\theta)\big{|}_{\theta=\theta^{*}}\end{bmatrix}=\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}.$

As mentioned below display (5.12),
$\frac{\partial{}}{\partial{\theta}}\Phi_{1:T-1}(\beta_{1:T-1}^{*})\big{|}_{\theta=\theta^{*}}=\bm{0}$
since $\Phi_{1:T-1}(\beta_{1:T-1}^{*})$ is not a function of $\theta$.

We now state the next set of results and discuss why they hold below:

$-\sqrt{n}\begin{bmatrix}\hat{\Phi}_{1:T-1}^{(n)}\big{(}\hat{\beta}_{1:T-1}^{(n)}\big{)}-\Phi_{1:T-1}\big{(}\hat{\beta}_{1:T-1}^{(n)}\big{)}\\\
\hat{\Psi}^{(n)}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}-\Psi\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\end{bmatrix}\\\
\underbrace{=}_{(c)}-\sqrt{n}\begin{bmatrix}\hat{\Phi}_{1:T-1}^{(n)}\big{(}\beta_{1:T-1}^{*}\big{)}-\Phi_{1:T-1}\big{(}\beta_{1:T-1}^{*}\big{)}\\\
\hat{\Psi}^{(n)}\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}-\Psi\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}\end{bmatrix}+o_{P}(1)\underbrace{\overset{D}{\to}}_{(d)}\mathcal{N}\big{(}0,\Sigma_{1:T}\big{)}.$
(C.8)

Equality (c). Equality (c) above is an asymptotic equicontinuity result. We
now discuss why equality (c) holds. First note that by Conditions 1-5 and
Remark 9 (which shows that Condition 5 implies that assumptions (NP1) and
(NP2) hold), we can apply Theorem B.3 (Asymptotic Equicontinuity for Policy
Parameters) to get the following results:

$\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}=O_{P}(1/\sqrt{n})$ (C.9)

and

$\sqrt{n}\left\\{\hat{\Phi}_{1:T-1}^{(n)}(\hat{\beta}_{1:T-1}^{(n)})-\Phi_{1:T-1}(\hat{\beta}_{1:T-1}^{(n)})\right\\}\\\
=\sqrt{n}\left\\{\hat{\Phi}_{1:T-1}^{(n)}(\beta_{1:T-1}^{*})-\Phi_{1:T-1}(\beta_{1:T-1}^{*})\right\\}+o_{P}(1).$
(C.10)

We now apply Lemma D.6 (Stochastic Equicontinuity) to get that

$\sqrt{n}\left\\{\hat{\Psi}^{(n)}\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}-\Psi\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\right\\}\\\
=\sqrt{n}\left\\{\hat{\Psi}^{(n)}\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}-\Psi\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}\right\\}+o_{P}(1),$
(C.11)

We are able to apply Lemma D.6 (Stochastic Equicontinuity) because the
following assumptions hold:

  * •

Conditions 2 (Minimum Exploration) and 3 (Lipschitz Policy Functions) hold.

  * •

Note that $\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}=O_{P}(1/\sqrt{n})$ by
display (C.9).

  * •

Since assumption (N4) (Finite Bracketing Integral) and Condition 3 (Lipschitz
Policy Function) hold, we can apply Lemma A.5 (specifically see Remark 8 part
(a2)) to get that for any $c\in{}^{d_{\theta}}$,

$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\left(\epsilon,~{}\big{\\{}\pi_{2:T}(\,\cdot\,;\beta_{1:T-1})c^{\top}\psi(\,\cdot\,;\theta)\big{\\}}_{\beta_{1:T-1}\in
B_{1:T-1},\theta\in\Theta},~{}L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon<\infty,$

where
$\pi_{2:T}(\,\cdot\,;\beta_{1:T-1})\triangleq\prod_{t^{\prime}=2}^{T}\pi_{t^{\prime}}(\,\cdot\,;\beta_{t^{\prime}-1})$.

  * •

$\big{(}\hat{\beta}_{1:T-1}^{(n)},\hat{\theta}^{(n)}\big{)}\overset{P}{\to}\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}$
by Slutsky’s theorem since
$\hat{\beta}_{1:T-1}^{(n)}\overset{P}{\to}\beta_{1:T-1}^{*}$ by Condition 1
and since $\hat{\theta}^{(n)}\overset{P}{\to}\theta^{*}$ by assumption. Thus,
by assumption (N3) and continuous mapping theorem we have that for any
$c\in{}^{d_{\theta}}$,
$\nu\left(c^{\top}\pi_{2:T}(\,\cdot\,;\hat{\beta}_{1:T-1}^{(n)})\psi(\,\cdot\,;\hat{\theta}^{(n)}),~{}c^{\top}\pi_{2:T}(\,\cdot\,;\beta_{1:T-1}^{*})\psi(\,\cdot\,;\theta^{*})\right)\overset{P}{\to}0$,
where

$\nu\bigg{(}\pi_{2:T}(\,\cdot\,;\beta_{1:T-1})c^{\top}\psi(\,\cdot\,;\theta),~{}\pi_{2:T}(\,\cdot\,;\beta_{1:T-1}^{\prime})c^{\top}\psi(\,\cdot\,;\theta^{\prime})\bigg{)}\\\
\triangleq\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}(\,\cdot\,;\beta_{1:T-1})c^{\top}\psi(\,\cdot\,;\theta)-\pi_{2:T}(\,\cdot\,;\beta_{1:T-1}^{\prime})c^{\top}\psi(\,\cdot\,;\theta^{\prime})\big{\\}}^{2}\right]^{1/2}.$

Equality (c) holds since by Slutsky’s Theorem, we can combine the results
above from displays (C.10) and (C.11).

Asymptotic normality result (d). Equality (d) above holds by Theorem D.4
(Weighted Martingale Triangular Array Central Limit Theorem). Specifically
note that for any fixed vector
$c=[c_{1},c_{2},\dots,c_{T}]\in{}^{d_{1:T-1}+d_{\theta}}$,

$-\sqrt{n}c^{\top}\begin{bmatrix}\hat{\Phi}_{1:T-1}^{(n)}\big{(}\beta_{1:T-1}^{*}\big{)}-\Phi_{1:T-1}\big{(}\beta_{1:T-1}^{*}\big{)}\\\
\hat{\Psi}^{(n)}\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}-\Psi\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}\end{bmatrix}$
$=-\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\sum_{t=1}^{T-1}c_{t}^{\top}W_{2:t}^{(i)}(\beta_{1:t-1}^{*},\hat{\beta}_{1:t-1}^{(n)})\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t}^{*})\\\
-\frac{1}{\sqrt{n}}\sum_{i=1}^{n}c_{T}^{\top}W_{2:T}^{(i)}(\beta_{1:T-1}^{*},\hat{\beta}_{1:T-1}^{(n)})\psi(\mathcal{H}_{T}^{(i)};\theta^{*})\overset{D}{\to}\mathcal{N}\big{(}0,c^{\top}\Sigma_{1:T}c\big{)}$
(C.12)

where

$\Sigma_{1:T}\triangleq\mathbb{E}_{\pi_{2:T}^{*}}\left[\begin{pmatrix}\phi_{1}(\mathcal{H}_{1}^{(i)};\beta_{1}^{*})\\\
\phi_{2}(\mathcal{H}_{2}^{(i)};\beta_{2}^{*})\\\ \vdots\\\
\phi_{T-1}(\mathcal{H}_{T-1}^{(i)};\beta_{T-1}^{*})\\\
\psi(\mathcal{H}_{T}^{(i)};\theta^{*})\end{pmatrix}^{\otimes 2}\right].$

The final asymptotic normality result above holds by Theorem D.4 (Weighted
Martingale Triangular Array Central Limit Theorem). Specifically we can apply
Theorem D.4 because:

  * •

Conditions 2 (Minimum Exploration) and 3 (Lipschitz Policy Functions) hold.

  * •

$\hat{\beta}_{t^{\prime}}^{(n)}-\beta_{t^{\prime}}^{*}=O_{P}(1/\sqrt{n})$ for
all $t^{\prime}\in[1\colon T-1]$ by display (C.9).

  * •

$\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}c_{T}^{\top}\psi(\mathcal{H}_{T}^{(i)};\theta^{*})\big{|}^{2+\alpha}\right]<\infty$
by Finite Bracketing Integral assumption (N4). Also,
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}c_{t}^{\top}\phi_{t}(\mathcal{H}_{t}^{(i)};\beta_{t}^{*})\big{|}^{2+\alpha}\right]<\infty$
for each $t\in[1\colon T-1]$ by Condition 5.

Thus, by Cramer-Wold device and display (C.12) we have that

$-\sqrt{n}\begin{bmatrix}\hat{\Phi}_{1:T-1}^{(n)}\big{(}\beta_{1:T-1}^{*}\big{)}-\Phi_{1:T-1}\big{(}\beta_{1:T-1}^{*}\big{)}\\\
\hat{\Psi}^{(n)}\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}-\Psi\big{(}\beta_{1:T-1}^{*},\theta^{*}\big{)}\end{bmatrix}\overset{D}{\to}\mathcal{N}(0,\Sigma_{1:T}).$
(C.13)

Thus, we have shown that asymptotic normality result (d) holds.

Consolidating Results. By consolidating the results from displays (C.7) and
(C.8) above, and applying Slutsky’s theorem we get the following result:

$\sqrt{n}\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}\begin{bmatrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{bmatrix}+\sqrt{n}o_{P}\left(\left\|\begin{matrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{matrix}\right\|_{2}\right)\overset{D}{\to}\mathcal{N}\big{(}0,\Sigma_{1:T}\big{)}.$
(C.14)

Note that $\dot{\Psi}^{*}$ is invertible by assumption (N1) and
$\dot{\Phi}_{1:T-1}^{*}$ is invertible by Condition 4 and Lemma B.4. By
Proposition 1 (Block Inversion of Matrices), this is sufficient for
$\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}$ to be invertible. Thus, by
continuous mapping theorem, and display (C.14),

$\sqrt{n}\begin{bmatrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{bmatrix}+\sqrt{n}O(1)o_{P}\left(\left\|\begin{matrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{matrix}\right\|_{2}\right)+o_{P}(1)\\\
\overset{D}{\to}\mathcal{N}\left(0,\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1}\Sigma_{1:T}\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1,\top}\right).$ (C.15)

The asymptotic normality result above in display (C.15) implies that

$\sqrt{n}\begin{bmatrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{bmatrix}+\sqrt{n}O(1)o_{P}\left(\left\|\begin{matrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{matrix}\right\|_{2}\right)=O_{P}(1).$

This implies that
$\sqrt{n}\begin{bmatrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{bmatrix}=O_{P}(1)$. Thus, we have that

$\sqrt{n}O(1)o_{P}\left(\left\|\begin{matrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{matrix}\right\|_{2}\right)=o_{P}(1).$

So, by display (C.15) and Slutsky’s Theorem we have that

$\sqrt{n}\begin{bmatrix}\hat{\beta}_{1:T-1}^{(n)}-\beta_{1:T-1}^{*}\\\
\hat{\theta}^{(n)}-\theta^{*}\end{bmatrix}\overset{D}{\to}\mathcal{N}\left(0,\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1}\Sigma_{1:T}\begin{bmatrix}\dot{\Phi}_{1:T-1}^{*}&&\bm{0}\\\
\bm{V}_{T,1:T-1}&&\dot{\Psi}^{*}\end{bmatrix}^{-1,\top}\right).~{}\blacksquare$

##  Appendix D Limit Theorems for Adaptively Sampled Data

Overview of Appendix D Results.

  * •

Section D.1: Weighted Martingale Triangular Array Law of Large Numbers
(Theorem D.1)

  * •

Section D.2: Weighted Martingale Triangular Array Uniform Law of Large Numbers
(Theorem D.2)

  * •

Section D.3: Showing Terms are $O_{P}(1)$ (Lemma D.3)

  * •

Section D.4: Weighted Martingale Triangular Array Central Limit Theorem
(Theorem D.4)

  * •

Section D.5: Functional Asymptotic Normality under Finite Bracketing Integral
(Theorem D.5)

  * •

Section D.6: Stochastic Equicontinuity (Lemma D.6)

###  D.1 Weighted Martingale Triangular Array Law of Large Numbers (Theorem
D.1)

######  Theorem D.1 (Weighted Martingale Triangular Array Weak Law of Large
Numbers).

Let $f$ be a real-valued function of $\mathcal{H}_{t}^{(i)}$ such that for
some $\alpha>0$,
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}f\big{(}\mathcal{H}_{t}^{(i)}\big{)}\big{|}^{1+\alpha}\right]<\infty$.
Under Condition 2 (Minimum Exploration),

$\frac{1}{n}\sum_{i=1}^{n}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})\overset{P}{\to}\mathbb{E}_{\pi_{2:t}^{*}}\left[f(\mathcal{H}_{t}^{(i)})\right].$
(D.1)

Moreover,

$\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\overset{P}{\to}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\right].$
(D.2)

Proof of Theorem D.1.

Proving display (D.1) holds. To show display (D.1) holds it is sufficient to
show that for any $t\in[1\colon T]$,

$\frac{1}{n}\sum_{i=1}^{n}\left\\{W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\left[f(\mathcal{H}_{t}^{(i)})\right]\right\\}\overset{P}{\to}0.$
(D.3)

Above we use $W_{1}^{(i)}=1$ and
$W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\triangleq
W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})$.

For the $t=1$ case,
$\mathcal{H}_{1}^{(1)},\mathcal{H}_{1}^{(2)},\mathcal{H}_{1}^{(3)},\dots,\mathcal{H}_{1}^{(n)}$
are i.i.d.; in this case, display (D.3) holds by the Weak Law of Large numbers
for i.i.d. data.

Note that for $t\geq 2$, the distribution of $\mathcal{H}_{t}^{(i)}$ is
changing with the number of users $n$, since it is depends on policy parameter
$\hat{\beta}_{t-1}^{(n)}$. Thus, we need to consider triangular array
asymptotics.

The first task is to rewrite the left-hand side of display (D.3) as a sum of
triangular array martingale differences. Note that we can rewrite the left-
hand side of display (D.3) as follows:

$\frac{1}{n}\sum_{i=1}^{n}\left\\{W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})-\mathbb{E}\left[W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})\right]\right\\}$

Above the expectation $\mathbb{E}$ is with respect to the data distribution
used to collect the data, thus,
$\mathbb{E}\left[W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})\right]=\mathbb{E}_{\pi_{2:t}^{*}}\left[f(\mathcal{H}_{t}^{(i)})\right]$.

Let $X_{t}^{(i)}\triangleq
W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})$. Also let
$\mathcal{H}_{0}^{(1:n)}\triangleq\emptyset$ and
$S_{T+1}^{(1:n)}\triangleq\emptyset$ (the second definition is only used for
the $t=T$ case). By telescoping series,

$=\frac{1}{n}\sum_{i=1}^{n}\left\\{X_{t}^{(i)}-\mathbb{E}\left[X_{t}^{(i)}\right]\right\\}$
$=\frac{1}{n}\sum_{i=1}^{n}\underbrace{\left\\{\mathbb{E}\left[X_{t}^{(i)}\big{|}\mathcal{H}_{0}^{(1:n)},S_{1}^{(1:n)}\right]-\mathbb{E}\left[X_{t}^{(i)}\right]\right\\}}_{\triangleq
Z_{0}^{(i)}}\\\
+\sum_{t^{\prime}=1}^{t}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}\underbrace{\left\\{\mathbb{E}\left[X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}}^{(1:n)},S_{t^{\prime}+1}^{(1:n)}\right]-\mathbb{E}\left[X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\right]\right\\}}_{\triangleq
Z_{t^{\prime}}^{(i)}}\bigg{]}.$ (D.4)

Note above that
$X_{t}^{(i)}=\mathbb{E}\left[X_{t}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]$,
since $X_{t}^{(i)}$ is a constant given $\mathcal{H}_{t}^{(1:n)}$.

Using the $Z_{t^{\prime}}^{(i)}$ notation defined in display (D.4) above,

$=\underbrace{\frac{1}{n}\sum_{i=1}^{n}Z_{0}^{(i)}}_{=o_{P}(1)}+\frac{1}{n}\sum_{i=1}^{n}\sum_{t^{\prime}=1}^{t}Z_{t^{\prime}}^{(i)}$
(D.5)

Note above that
$\frac{1}{n}\sum_{i=1}^{n}Z_{0}^{(i)}=\frac{1}{n}\sum_{i=1}^{n}\left\\{\mathbb{E}\big{[}X_{t}^{(i)}\big{|}\mathcal{H}_{0}^{(1:n)},S_{1}^{(1:n)}\big{]}-\mathbb{E}\big{[}X_{t}^{(i)}\big{]}\right\\}\\\
=\frac{1}{n}\sum_{i=1}^{n}\left\\{\mathbb{E}\big{[}f(\mathcal{H}_{1}^{(i)})\big{|}S_{1}^{(1:n)}\big{]}-\mathbb{E}\big{[}f(\mathcal{H}_{1}^{(i)})\big{]}\right\\}\\\
=\frac{1}{n}\sum_{i=1}^{n}\left\\{\mathbb{E}\big{[}f(\mathcal{H}_{1}^{(i)})\big{|}S_{1}^{(i)}\big{]}-\mathbb{E}\big{[}f(\mathcal{H}_{1}^{(i)})\big{]}\right\\}\overset{P}{\to}0$
by the weak law of large numbers for i.i.d. random variables.

Regarding the second summation in display (D.5), note that
$\big{\\{}Z_{t^{\prime}}^{(i)}\big{\\}}_{i=1;t^{\prime}=1}^{i=n;t^{\prime}=t}$
is a martingale difference triangular array with respect to the filtration
$\big{\\{}\sigma\big{(}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\big{)}\big{\\}}_{t^{\prime}=1}^{t}$.
This is the case because for any $i\in[1\colon n]$ and $t^{\prime}\in[0\colon
t]$,

$\mathbb{E}\left[Z_{t^{\prime}}^{(i)}\big{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\right]=\mathbb{E}\left[\mathbb{E}\left[X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}}^{(1:n)},S_{t^{\prime}+1}^{(1:n)}\right]-\mathbb{E}\left[X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\right]\bigg{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\right]$
(D.6)
$=\mathbb{E}\left[\mathbb{E}\left[X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}}^{(1:n)},S_{t^{\prime}+1}^{(1:n)}\right]\bigg{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\right]-\mathbb{E}\left[X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\right]=0.$

The final equality above holds by the law of iterated expectations.

The next step will be to apply Theorem 2(a) of Andrews [1988] (Weak Law of
Large Numbers for Triangular Array Mixingales). Theorem 2(a) ensures that
$\frac{1}{n}\sum_{i=1}^{n}\sum_{t^{\prime}=1}^{t}Z_{t^{\prime}}^{(i)}\overset{P}{\to}0$
if we can show the following hold:

  1. (i)

$\mathbb{E}\big{[}Z_{t^{\prime}}^{(i)}\big{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\big{]}=0$
for all $i\in[1\colon n]$ and $t^{\prime}\in[1\colon t]$. (Note that since we
have a martingale difference triangular array, the mixing constant $c_{n,i}$
in Theorem 2(a) is satisfied for $c_{n,i}=0$.)

  2. (ii)

For some $\alpha>0$,
$\mathbb{E}\big{[}|Z_{t^{\prime}}^{(i)}|^{1+\alpha}\big{]}<\infty$ for all
$i\in[1\colon n]$ and $t^{\prime}\in[1\colon t]$. Note that by Exercise 5.5.1
of Durrett [2019] this implies $Z_{t^{\prime}}^{(i)}$ are uniformly
integrable.

We already showed that property (i) above holds earlier in display (D.6). All
that remains is to show that property (ii) above holds.

Consider any $t^{\prime}\in[1\colon t]$ and any $i\in[1\colon n]$,

$\mathbb{E}\big{[}\big{|}Z_{t^{\prime}}^{(i)}\big{|}^{1+\alpha}\big{]}=\mathbb{E}\bigg{[}\left|\mathbb{E}\big{[}X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}}^{(1:n)},S_{t^{\prime}+1}^{(1:n)}\big{]}-\mathbb{E}\big{[}X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\big{]}\right|^{1+\alpha}\bigg{]}$

By Lemma B.2, for some positive constant $c_{1+\alpha}<\infty$,

$\leq
c_{1+\alpha}\bigg{\\{}\mathbb{E}\bigg{[}\left|\mathbb{E}\big{[}X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}}^{(1:n)},S_{t^{\prime}+1}^{(1:n)}\big{]}\right|^{1+\alpha}\bigg{]}+\mathbb{E}\bigg{[}\left|\mathbb{E}\big{[}X_{t}^{(i)}\big{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\big{]}\right|^{1+\alpha}\bigg{]}\bigg{\\}}$

By Jensen’s inequality

$\leq
c_{1+\alpha}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[\big{|}X_{t}^{(i)}\big{|}^{1+\alpha}\bigg{|}\mathcal{H}_{t^{\prime}}^{(1:n)},S_{t^{\prime}+1}^{(1:n)}\right]\bigg{]}+\mathbb{E}\bigg{[}\mathbb{E}\left[\big{|}X_{t}^{(i)}\big{|}^{1+\alpha}\bigg{|}\mathcal{H}_{t^{\prime}-1}^{(1:n)},S_{t^{\prime}}^{(1:n)}\right]\bigg{]}\bigg{\\}}$

By the law of iterated expectations,

$=c_{1+\alpha}\bigg{\\{}\mathbb{E}\left[\big{|}X_{t}^{(i)}\big{|}^{1+\alpha}\right]+\mathbb{E}\left[\big{|}X_{t}^{(i)}\big{|}^{1+\alpha}\right]\bigg{\\}}=c_{1+\alpha}2\mathbb{E}\left[\big{|}X_{t}^{(i)}\big{|}^{1+\alpha}\right]$

Since $X_{t}^{(i)}\triangleq
W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})$,

$=c_{1+\alpha}2\mathbb{E}\left[\big{|}W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})\big{|}^{1+\alpha}\right]$

Since $W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\leq\pi_{\min}^{-(t-1)}$ by
Condition 2 (Minimum Exploration),

$\leq
c_{1+\alpha}2\pi_{\min}^{-(t-1)(1+\alpha)}\mathbb{E}\left[\big{|}f(\mathcal{H}_{t}^{(i)})\big{|}^{1+\alpha}\right]<\infty.$

The final inequality holds since
$\mathbb{E}\left[\big{|}f(\mathcal{H}_{t}^{(i)})\big{|}^{1+\alpha}\right]<\infty$
by assumption of this Theorem. We have now shown that property (ii) holds. We
have now shown that display (D.1) holds.

Proving Display (D.2) holds.

$\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\overset{P}{\to}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\right].$
(D.7)

Note that

$\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})=W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)}).$

By Condition 2,
$\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}\leq\pi_{\min}^{-(t-1)}$ a.s. Thus,
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\big{|}^{1+\alpha}\right]\\\
\leq\pi_{\min}^{-(t-1)}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}f(\mathcal{H}_{t}^{(i)})\big{|}^{1+\alpha}\right]<\infty$;
the final inequality holds by the assumption that
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}f\big{(}\mathcal{H}_{t}^{(i)}\big{)}\big{|}^{1+\alpha}\right]<\infty$.
Thus, using the result from display (D.1),

$\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})=\frac{1}{n}\sum_{i=1}^{n}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\\\
\overset{P}{\to}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\right].~{}~{}~{}\blacksquare$

###  D.2 Weighted Martingale Triangular Array Uniform Law of Large Numbers
(Theorem D.2)

######  Theorem D.2 (Weighted Martingale Triangular Array Uniform Weak Law of
Large Numbers).

Let $\mathcal{F}$ be a class of real-valued, measurable functions such that
for some $\alpha>0$,
$N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
for any $\epsilon>0$. Under Condition 2 (Minimum Exploration),

$\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\left\\{W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\big{[}f(\mathcal{H}_{t}^{(i)})\big{]}\right\\}\bigg{|}\overset{P}{\to}0.$
(D.8)

Moreover,

$\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\big{]}\right)\bigg{|}\overset{P}{\to}0.$
(D.9)

Proof of Theorem D.2.

Showing display (D.8) holds. Let $\epsilon>0$. For convenience, let
$N_{\epsilon}\triangleq
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}$.
Since
$N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
by assumption, we can finitely many brackets
$\big{\\{}(l_{k},u_{k})\big{\\}}_{k=1}^{N_{\epsilon}}$ that cover
$\mathcal{F}$ with
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u_{k}(\mathcal{H}_{t}^{(i)})-l_{k}(\mathcal{H}_{t}^{(i)})\big{|}^{1+\alpha}\big{]}^{1/(1+\alpha)}\leq\epsilon$.
Thus,

$\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\left\\{W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\big{[}f(\mathcal{H}_{t}^{(i)})\big{]}\right\\}$
$\leq\max_{k\in[1\colon
N_{\epsilon}]}\frac{1}{n}\sum_{i=1}^{n}\left\\{W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})u_{k}(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\big{[}l_{k}(\mathcal{H}_{t}^{(i)})\big{]}\right\\}$

By Theorem D.1 (Weighted Martingale Triangular Array Weak Law of Large
Numbers), for any $k\in[1\colon N_{\epsilon}]$,
$\frac{1}{n}\sum_{i=1}^{n}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})u_{k}(\mathcal{H}_{t}^{(i)})\overset{P}{\to}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}u_{k}(\mathcal{H}_{t}^{(i)})\big{]}$.
Since there are finitely many brackets, by Slutsky’s theorem this result holds
simultaneously for all brackets $k\in[1\colon N_{\epsilon}]$.

$=o_{P}(1)+\max_{k\in[1\colon
N_{\epsilon}]}\left\\{\mathbb{E}_{\pi_{2:t}^{*}}\big{[}u_{k}(\mathcal{H}_{t}^{(i)})\big{]}-\mathbb{E}_{\pi_{2:t}^{*}}\big{[}l_{k}(\mathcal{H}_{t}^{(i)})\big{]}\right\\}$

By Jensen’s inequality

$\leq o_{P}(1)+\max_{k\in[1\colon
N_{\epsilon}]}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}|u_{k}(\mathcal{H}_{t}^{(i)})-l_{k}(\mathcal{H}_{t}^{(i)})|^{1+\alpha}\big{]}^{1/(1+\alpha)}\leq
o_{P}(1)+\epsilon.$

The last inequality above holds because our brackets were chosen to be at most
of size $\epsilon$, in $L_{1+\alpha}(\mathcal{P}_{\pi^{*}})$ norm. The above
converges to zero because $\epsilon$ can be chosen to be arbitrarily small.

The final result display (D.8) holds by using the same argument above to show
that
$\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\left\\{\mathbb{E}_{\pi_{2:t}^{*}}\big{[}f(\mathcal{H}_{t}^{(i)})\big{]}-W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f(\mathcal{H}_{t}^{(i)})\right\\}\overset{P}{\to}0$.

Showing display (D.9) holds. Note that

$\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})=W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\\\
=W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\bigg{\\{}\prod_{t^{\prime}=2}^{t}\frac{1}{\pi_{t^{\prime}}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)};\beta_{t^{\prime}-1}^{*})}\bigg{\\}}f(\mathcal{H}_{t}^{(i)}).$

By the result from display (D.8), to show display (D.9) holds it is sufficient
to show that the function class

$\mathcal{F}_{\pi}\triangleq\bigg{\\{}\bigg{(}\prod_{t^{\prime}=2}^{t}\frac{1}{\pi_{t^{\prime}}(\,\cdot\,;\beta_{t^{\prime}-1}^{*})}\bigg{)}f(\,\cdot\,)\textnormal{~{}~{}s.t.~{}~{}}f\in\mathcal{F}\bigg{\\}}$

is such that
$N_{[~{}]}\big{(}\epsilon,\mathcal{F}_{\pi},L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
for all $\epsilon>0$.

Since $N_{\epsilon}\triangleq
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
by conditions of the theorem, we can find brackets
$\big{\\{}(l_{k},u_{k})\big{\\}}_{k=1}^{N_{\epsilon}}$ that cover
$\mathcal{F}$ and
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u_{k}(\mathcal{H}_{t}^{(i)})-l_{k}(\mathcal{H}_{t}^{(i)})\big{|}^{1+\alpha}\big{]}^{1/(1+\alpha)}\leq\epsilon$
for each bracket $(l_{k},u_{k})$. Let $f\in\mathcal{F}$. We can find one of
these brackets $(l_{k},u_{k})$ such that $l_{k}(\mathcal{H}_{t}^{(i)})\leq
f(\mathcal{H}_{t}^{(i)})\leq u_{k}(\mathcal{H}_{t}^{(i)})$ a.s.

Since $\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}>0$ a.s., thus,

$\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}l_{k}(\mathcal{H}_{t}^{(i)})\leq\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\leq\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}u_{k}(\mathcal{H}_{t}^{(i)}).$

So the brackets
$\big{\\{}\big{(}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}l_{k},\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}u_{k}\big{)}\big{\\}}_{k=1}^{N_{\epsilon}}$
cover $\mathcal{F}_{\pi}$.

Moreover, since
$\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}\leq\pi_{\min}^{-(t-1)}$ a.s. by
Condition 2, thus

$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}u_{k}(\mathcal{H}_{t}^{(i)})-\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}l_{k}(\mathcal{H}_{t}^{(i)})\big{|}^{1+\alpha}\big{]}^{1/(1+\alpha)}\leq\pi_{\min}^{-(t-1)}\epsilon.$

Thus, we have that
$N_{[~{}]}\big{(}\pi_{\min}^{-(t-1)}\epsilon,\mathcal{F}_{W},L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}=N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}$.
Thus, since
$N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
for any $\epsilon>0$ (by assumption of the Theorem), thus we have that
$N_{[~{}]}\big{(}\epsilon,\mathcal{F}_{W},L_{1+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}<\infty$
for any $\epsilon>0$. $\blacksquare$

###  D.3 Showing Terms are $O_{P}(1)$ (Helper Lemma D.3)

######  Lemma D.3 (Showing Terms are $O_{P}(1)$ (Helper Lemma)).

Let $g$ be a real-valued, function of $\mathcal{H}_{t}^{(i)}$ such that
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}g(\mathcal{H}_{t}^{(i)})\big{|}\big{]}<\infty$.
Under Condition 2, we have that $g(\mathcal{H}_{t}^{(i)})=O_{P}(1)$.

Proof of Lemma D.3. Let $\epsilon>0$. By Condition 2 (Minimum Exploration),

$W_{t^{\prime}}^{(i)}\big{(}\beta_{t^{\prime}-1}^{*},\hat{\beta}_{t^{\prime}-1}^{(n)}\big{)}=\frac{\pi_{t^{\prime}}^{*}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})}{\hat{\pi}_{t^{\prime}}^{(n)}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})}\geq\frac{\pi_{t^{\prime}}^{*}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})}{1}\geq\pi_{\min}~{}~{}~{}\textnormal{a.s.}$

By the above result and Markov inequality, for any $c_{\epsilon}>0$,

$\mathbb{P}\big{(}\big{|}g(\mathcal{H}_{t}^{(i)})\big{|}>c_{\epsilon}\big{)}\leq
c_{\epsilon}^{-1}\mathbb{E}\big{[}\big{|}g(\mathcal{H}_{t}^{(i)})\big{|}\big{]}\\\
\leq
c_{\epsilon}^{-1}\pi_{\min}^{-(t-1)}\mathbb{E}\left[W_{2:t}^{(i)}\big{(}\beta^{*},\hat{\beta}^{(n)}\big{)}\big{|}g(\mathcal{H}_{t}^{(i)})\big{|}\right]=c_{\epsilon}^{-1}\pi_{\min}^{-(t-1)}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}g(\mathcal{H}_{t}^{(i)})\big{|}\right].$
(D.10)

The above is less than or equal to $\epsilon$ by choosing
$c_{\epsilon}>\epsilon^{-1}\pi_{\min}^{-(t-1)}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}g(\mathcal{H}_{t}^{(i)})\big{|}\big{]}$.
This is sufficient by the definition of $O_{P}(1)$. $\blacksquare$

###  D.4 Weighted Martingale Triangular Array Central Limit Theorem (Theorem
D.4)

######  Theorem D.4 (Weighted Martingale Triangular Array Central Limit
Theorem).

Let $f_{1},f_{2},...,f_{t}$ be real-valued, measurable functions of
$\mathcal{H}_{1}^{(i)},\mathcal{H}_{2}^{(i)},...,\mathcal{H}_{t}^{(i)}$
respectively such that
$\mathbb{E}_{\pi_{2:t^{\prime}}^{*}}\left[\big{|}f_{t^{\prime}}\big{(}\mathcal{H}_{t^{\prime}}^{(i)}\big{)}\big{|}^{2+\alpha}\right]<\infty$
for some $\alpha>0$, for each $t^{\prime}\in[1\colon t]$. We show that (below
we use $W_{1}^{(i)}=1$)

$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bigg{\\{}\sum_{t^{\prime}=1}^{t}W_{1:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\sum_{t^{\prime}=1}^{t}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\bigg{]}\bigg{\\}}\\\
\overset{D}{\to}\mathcal{N}\bigg{(}0,\textnormal{Var}_{\pi_{2:t}^{*}}\bigg{(}\sum_{t^{\prime}=1}^{t}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\bigg{)}\bigg{)}$
(D.11)

for
$\textnormal{Var}_{\pi_{2:t}^{*}}\left(\sum_{t^{\prime}=1}^{t}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\right)\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\sum_{t^{\prime}=1}^{t}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{\\}}^{2}\right]-\mathbb{E}_{\pi_{2:t}^{*}}\left[\sum_{t^{\prime}=1}^{t}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\right]^{2}$
under the following conditions:

  1. (A)

Conditions 2 (Minimum Exploration) and 3 (Lipschitz Policy Functions) hold.

  2. (B)

$\hat{\beta}_{t^{\prime}}^{(n)}-\beta_{t^{\prime}}^{*}=O_{P}(1/\sqrt{n})$ for
all $t^{\prime}\in[1\colon t-1]$.

Proof of Theorem D.4. We want to show that display (D.11) holds for any