$t\in[2\colon T]$. For notational convenience we consider the $t$ set to $T$
case; the argument holds by the same argument for any $t\in[2\colon T]$.

The first task is to rewrite the left-hand side of display (D.11) as a sum of
triangular array martingale differences; we take an approach similar to that
we used in the proof of Theorem D.1.

Note that the left-hand side of display (D.11) can be rewritten as follows:

$\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{\\}}\\\
=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\sum_{t=1}^{T}\bigg{\\{}W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})-\mathbb{E}\left[W_{1:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})\right]\bigg{\\}}$

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)})$. Additionally, 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_{t}(\mathcal{H}_{t}^{(i)})$ and
$X_{1:T}^{(i)}\triangleq\sum_{t=1}^{T}X_{t}^{(i)}$.

$=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\sum_{t=1}^{T}\left\\{X_{t}^{(i)}-\mathbb{E}\left[X_{t}^{(i)}\right]\right\\}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left\\{X_{1:T}^{(i)}-\mathbb{E}\left[X_{1:T}^{(i)}\right]\right\\}$

Let $\mathcal{H}_{0}^{(1:n)}\triangleq\emptyset$ and
$S_{T+1}^{(1:n)}\triangleq\emptyset$. Note that
$X_{1:T}^{(i)}=\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{T}^{(1:n)},S_{T+1}^{(1:n)}\right]$
since $X_{1:T}^{(i)}$ is known given $\mathcal{H}_{T}^{(1:n)}$. By telescoping
series,

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

Note that the terms $Z_{t}^{(i)}$ above are different from those we defined in
the proof of Theorem D.1, since here the terms $X_{1:T}^{(i)}$ are a sum over
$T$ terms.

Note that
$\mathbb{E}\left[Z_{t}^{(i)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]=0$
for all $i\in[1\colon n]$ and $t\in[1\colon T]$. This is the case because for
any $i\in[1\colon n]$ and $t\in[1\colon T]$,

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

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

In the next two subsections we will show the following two results:

##### (i) Convergence of conditional variance

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\big{(}Z_{0}^{(i)}\big{)}^{2}\right]+\sum_{t=1}^{T}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\big{(}Z_{t}^{(i)}\big{)}^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
\overset{P}{\to}\textnormal{Var}_{\pi_{2:T}^{*}}\bigg{(}\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\bigg{)}.$
(D.12)

##### (ii) Conditional Lindeberg

For any $\epsilon>0$,

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\big{(}Z_{0}^{(i)}\big{)}^{2}\mathbb{I}_{|Z_{0}^{(i)}|/\sqrt{n}>\epsilon}\right]+\sum_{t=1}^{T}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\big{(}Z_{t}^{(i)}\big{)}^{2}\mathbb{I}_{|Z_{t}^{(i)}|/\sqrt{n}>\epsilon}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
\overset{P}{\to}0.$ (D.13)

With the above two results we can apply Theorem 2.2 of Dvoretzky [1972] (a
martingale central limit theorem) to conclude that our desired result holds,
i.e.,

$\frac{1}{\sqrt{n}}\sum_{t=0}^{T}\sum_{i=1}^{n}Z_{t}^{(i)}\overset{D}{\to}\mathcal{N}\bigg{(}0,\textnormal{Var}_{\pi_{2:T}^{*}}\bigg{(}\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\bigg{)}\bigg{)}.$

We first show that display (D.13) holds. We then show that display (D.12)
holds.

(ii) Conditional Lindeberg; Display (D.13). For any $\epsilon>0$, we show that
the following conditional Lindeberg term is $o_{P}(1)$:

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\big{(}Z_{0}^{(i)}\big{)}^{2}\mathbb{I}_{|Z_{0}^{(i)}|/\sqrt{n}>\epsilon}\right]+\sum_{t=1}^{T}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\big{(}Z_{t}^{(i)}\big{)}^{2}\mathbb{I}_{|Z_{t}^{(i)}|/\sqrt{n}>\epsilon}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$

Note that for $\alpha>0$,
$\mathbb{I}_{|Z|/\sqrt{n}>\epsilon}=\mathbb{I}_{|Z|/(\epsilon\sqrt{n})>1}=\mathbb{I}_{|Z|^{\alpha}/(\epsilon\sqrt{n})^{\alpha}>1}\leq|Z|^{\alpha}/(\epsilon\sqrt{n})^{\alpha}$.
Thus we can upper-bound the previous display as follows:

$\leq\frac{1}{n(\epsilon\sqrt{n})^{\alpha}}\sum_{i=1}^{n}\mathbb{E}\left[\big{|}Z_{0}^{(i)}\big{|}^{2+\alpha}\right]+\sum_{t=1}^{T}\frac{1}{n(\epsilon\sqrt{n})^{\alpha}}\sum_{i=1}^{n}\mathbb{E}\left[\big{|}Z_{t}^{(i)}\big{|}^{2+\alpha}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right].$
(D.14)

Note that for any $t^{\prime}\in[0\colon T]$,

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

Above, by slight abuse of notation, if $t^{\prime}=0$, we use
$\mathcal{H}_{-1}^{(1:n)}\triangleq\emptyset$ and
$S_{0}^{(1:n)}\triangleq\emptyset$.

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

By repeatedly applying Lemma B.2 (Inequality Using Binomial Theorem) for any
numbers $a_{1},a_{2},...,a_{K}$, $|\sum_{k=1}^{K}a_{k}|^{\eta}\leq
c_{2+\alpha}^{K}\sum_{k=1}^{K}|a_{k}|^{2+\alpha}$ for some constant
$c_{2+\alpha}>0$.

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

By Jensen’s Inequality,

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

Thus, we can upper-bound display (D.14) as follows:

$\frac{1}{n(\epsilon\sqrt{n})^{\alpha}}\sum_{i=1}^{n}\mathbb{E}\left[\big{|}Z_{0}^{(i)}\big{|}^{2+\alpha}\right]+\sum_{t=1}^{T}\frac{1}{n(\epsilon\sqrt{n})^{\alpha}}\sum_{i=1}^{n}\mathbb{E}\left[\big{|}Z_{t}^{(i)}\big{|}^{2+\alpha}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$
$\leq\frac{c_{2+\alpha}^{T}}{n(\epsilon\sqrt{n})^{\alpha}}\sum_{i=1}^{n}\sum_{s=1}^{T}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\big{|}\mathcal{H}_{0}^{(1:n)},S_{1}^{(1:n)}\right]+\mathbb{E}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\right]\bigg{]}\bigg{\\}}\\\
+\sum_{t=1}^{T}\frac{c_{2+\alpha}^{T}}{n(\epsilon\sqrt{n})^{\alpha}}\sum_{i=1}^{n}\sum_{s=1}^{T}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]\\\
+\mathbb{E}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\bigg{]}\bigg{\\}}$

By the law of itereated expectations,

$=\frac{c_{2+\alpha}^{T}}{n(\epsilon\sqrt{n})^{\alpha}}\sum_{i=1}^{n}\sum_{s=1}^{T}2\mathbb{E}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\right]\\\
+\sum_{t=1}^{T}\frac{c_{2+\alpha}^{T}}{n(\epsilon\sqrt{n})^{\alpha}}\sum_{i=1}^{n}\sum_{s=1}^{T}2\mathbb{E}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$

To show that the above is $o_{P}(1)$, it is sufficient to show that
$\mathbb{E}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$
and $\mathbb{E}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\right]$ for all
$t,s\in[1\colon T]$ are all $O_{P}(1)$. By Lemma D.3, it is sufficient to show
that
$\mathbb{E}_{\pi_{2:s}^{*}}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\right]$
and
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|\mathbb{E}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\right|\right]$
are bounded.

By Jensen’s inequality,

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

Thus, it is sufficient to show that
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\right]<\infty$
for all $s\in[1\colon T]$.

By Condition 2,
$W_{2:s}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\leq\pi_{\min}^{-(s-1)}$ a.s. so,

$\mathbb{E}_{\pi_{2:s}^{*}}\left[\big{|}X_{s}^{(i)}\big{|}^{2+\alpha}\right]=\mathbb{E}_{\pi_{2:s}^{*}}\left[\big{|}W_{2:s}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{s}(\mathcal{H}_{s}^{(i)})\big{|}^{2+\alpha}\right]$
$\leq\pi_{\min}^{-(s-1)(2+\alpha)}\mathbb{E}_{\pi_{2:s}^{*}}\left[W_{2:s}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\big{|}f_{s}(\mathcal{H}_{s}^{(i)})\big{|}^{2+\alpha}\right]$
$=\pi_{\min}^{-(s-1)(2+\alpha)}\mathbb{E}_{\pi_{2:s}^{*}}\left[\big{|}f_{s}(\mathcal{H}_{s}^{(i)})\big{|}^{2+\alpha}\right]<\infty.$

(i) Convergence of conditional variance; Display (D.12):. We now show that
display (D.12) holds. Using the definition of $Z_{t}^{(i)}$,

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\big{(}Z_{0}^{(i)}\big{)}^{2}\right]+\sum_{t=1}^{T}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[\big{(}Z_{t}^{(i)}\big{)}^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$

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

$=\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\right]^{2}\bigg{]}-\mathbb{E}\left[X_{1:T}^{(i)}\right]^{2}\bigg{\\}}\\\
+\sum_{t=1}^{T}\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\bigg{]}-\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]^{2}\bigg{\\}}.$
(D.15)

Note by re-indexing,
$-\sum_{t=1}^{T}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]^{2}=-\sum_{t=0}^{T-1}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}\\\
=-\sum_{t=1}^{T}\underbrace{\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}}_{(a)}-\underbrace{\mathbb{E}\left[X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\right]^{2}}_{(b)}+\underbrace{\big{(}X_{1:T}^{(i)}\big{)}^{2}}_{(c)}$.
By rearranging terms the terms in display (D.15),

$=\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\underbrace{\big{(}X_{1:T}^{(i)}\big{)}^{2}}_{(c)}-\mathbb{E}\left[X_{1:T}^{(i)}\right]^{2}\bigg{\\}}\\\
+\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\right]^{2}\bigg{]}-\underbrace{\mathbb{E}\left[X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\right]^{2}}_{(b)}\bigg{\\}}\\\
+\sum_{t=1}^{T}\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\bigg{]}-\underbrace{\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}}_{(a)}\bigg{\\}}.$
(D.16)

For the remainder of the proof we will show the following results, which
combined with display (D.16) above are sufficient for display (D.12):

$\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\big{(}X_{1:T}^{(i)}\big{)}^{2}-\mathbb{E}\left[X_{1:T}^{(i)}\right]^{2}\bigg{\\}}\overset{P}{\to}\textnormal{Var}_{\pi_{2:T}^{*}}\bigg{(}\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\bigg{)}$
(D.17)
$\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\right]^{2}\bigg{]}-\mathbb{E}\left[X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\right]^{2}\bigg{\\}}\overset{P}{\to}0$
(D.18)
$\sum_{t=1}^{T}\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\bigg{]}-\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}\bigg{\\}}\overset{P}{\to}0$
(D.19)

Before showing the above three results, first note the following observations:

  * •

By Condition 2 (Minimum Exploration),

$\hat{\pi}_{t}^{(n)}(A_{t}^{(i)},S_{t}^{(i)})\geq\pi_{\min}~{}~{}~{}\textnormal{a.s.}~{}~{}~{}~{}~{}~{}\textnormal{and}~{}~{}~{}~{}~{}~{}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\leq\pi_{\min}^{-(t-1)}~{}~{}~{}\textnormal{a.s.}$
(D.20)

  * •

Additionally note that

$\left|W_{t}^{(i)}(\beta_{t-1}^{*},\hat{\beta}_{t-1}^{(n)})-1\right|=\left|W_{t}^{(i)}(\beta_{t-1}^{*},\hat{\beta}_{t-1}^{(n)})-W_{t}^{(i)}(\beta_{t-1}^{*},\beta_{t-1}^{*})\right|\\\
\leq\left|\hat{\pi}_{t}^{(n)}\big{(}A_{t}^{(i)},S_{t}^{(i)}\big{)}^{-1}-\pi_{t}^{*}\big{(}A_{t}^{(i)},S_{t}^{(i)}\big{)}^{-1}\right|\leq\max_{a\in\mathcal{A}}\left|\hat{\pi}_{t}^{(n)}\big{(}a,S_{t}^{(i)}\big{)}^{-1}-\pi_{t}^{*}\big{(}a,S_{t}^{(i)}\big{)}^{-1}\right|\\\
\underbrace{\leq}_{(i)}\pi_{\min}^{-2}\max_{a\in\mathcal{A}}\left|\hat{\pi}_{t}^{(n)}\big{(}a,S_{t}^{(i)}\big{)}-\pi_{t}^{*}\big{(}a,S_{t}^{(i)}\big{)}\right|\underbrace{\leq}_{(ii)}\pi_{\min}^{-2}\max_{a\in\mathcal{A}}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}\big{\|}\hat{\beta}_{t-1}^{(n)}-\beta_{t-1}^{*}\big{\|}_{2}.$
(D.21)

Inequality (i) above holds because by Taylor Series expansion,
$\hat{\pi}^{-1}-\pi^{*,-1}=(-1)\tilde{\pi}^{-2}(\hat{\pi}-\pi^{*})$ for some
$\tilde{\pi}$ between $\hat{\pi}$ and $\pi^{*}$. By Condition 2 (Minimum
Exploration) and display (D.20),
$\tilde{\pi}\geq\min(\hat{\pi},\pi^{*})\geq\pi_{\min}>0$ a.s.

Inequality (ii) holds by Condition 3 (Lipschitz Policy Functions).

  * •

Since the action space $\mathcal{A}$ is finite
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\max_{a\in\mathcal{A}}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}\big{]}\leq\sum_{a\in\mathcal{A}}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}\big{]}<\infty$;
the last inequality holds by Condition 3. Thus, by Lemma D.3,
$\max_{a\in\mathcal{A}}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}=O_{P}(1)$.
Also since
$\big{\|}\hat{\beta}_{t-1}^{(n)}-\beta_{t-1}^{*}\big{\|}_{2}=O_{P}(1/\sqrt{n})$
by assumption, by display (D.21), we have that
$W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})=1+O_{P}(1/\sqrt{n})$. Moreover, note
that

$W_{2:t}^{(i)}\big{(}\beta_{t-1}^{*},\hat{\beta}_{t-1}^{(n)}\big{)}=\left(1+O_{P}(1/\sqrt{n})\right)^{t-1}=1+O_{P}(1/\sqrt{n}).$
(D.22)

1\. Showing Display (D.17) holds. Since
$X_{1:T}^{(i)}=\sum_{t=1}^{T}X_{t}^{(i)}=\sum_{t=1}^{T}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})$,

$\frac{1}{n}\sum_{i=1}^{n}\big{(}X_{1:T}^{(i)}\big{)}^{2}=\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\sum_{t=1}^{T}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})\bigg{\\}}^{2}$
$=\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{s=1}^{T}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})W_{2:s}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{s}(\mathcal{H}_{s}^{(i)})$
$=\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{s=1}^{T}W_{2:\max(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})f_{s}(\mathcal{H}_{s}^{(i)})W_{2:\min(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})$

Note that since
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}f_{t}(\mathcal{H}_{t}^{(i)})^{2}\big{]}$ and
$\mathbb{E}_{\pi_{2:s}^{*}}\big{[}f_{s}(\mathcal{H}_{s}^{(i)})^{2}\big{]}$ is
bounded by assumption, by Lemma D.3, $f_{t}(\mathcal{H}_{t}^{(i)})=O_{P}(1)$
and $f_{s}(\mathcal{H}_{s}^{(i)})=O_{P}(1)$.

Moreover, by display (D.22), we have that
$W_{2:\min(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})=1+O_{P}(1/\sqrt{n})$ and
$W_{2:\max(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})=1+O_{P}(1/\sqrt{n})$.

Thus,
$W_{2:\max(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})f_{s}(\mathcal{H}_{s}^{(i)})W_{2:\min(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\\\
=W_{2:\max(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})f_{s}(\mathcal{H}_{s}^{(i)})+O_{P}(1/\sqrt{n})$.
So,

$=\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}\bigg{\\{}\sum_{s=1}^{T}W_{2:\max(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})f_{s}(\mathcal{H}_{s}^{(i)})+O_{P}(1/\sqrt{n})\bigg{\\}}$
$=\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{s=1}^{T}W_{2:\max(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})f_{s}(\mathcal{H}_{s}^{(i)})+o_{P}(1).$

Note that by display (D.20),

$\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}W_{2:\max(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})f_{s}(\mathcal{H}_{s}^{(i)})\big{|}^{1+\alpha/2}\right]$
$\leq\pi_{\min}^{-\\{\max(t,s)-1\\}}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}f_{t}(\mathcal{H}_{t}^{(i)})f_{s}(\mathcal{H}_{s}^{(i)})\big{|}^{1+\alpha/2}\right]$
$\leq\pi_{\min}^{-\\{\max(t,s)-1\\}}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\max\left\\{\big{|}f_{t}(\mathcal{H}_{t}^{(i)})\big{|}^{2},~{}\big{|}f_{s}(\mathcal{H}_{s}^{(i)})\big{|}^{2}\right\\}^{1+\alpha/2}\bigg{]}$
$\leq\pi_{\min}^{-\\{\max(t,s)-1\\}}\mathbb{E}_{\pi_{2:T}^{*}}\left[\left\\{\big{|}f_{t}(\mathcal{H}_{t}^{(i)})\big{|}^{2}+\big{|}f_{s}(\mathcal{H}_{s}^{(i)})\big{|}^{2}\right\\}^{1+\alpha/2}\right]$

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

$\leq\pi_{\min}^{-\\{\max(t,s)-1\\}}c_{1+\alpha/2}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}f_{t}(\mathcal{H}_{t}^{(i)})\big{|}^{2+\alpha}+\big{|}f_{s}(\mathcal{H}_{s}^{(i)})\big{|}^{2+\alpha}\right]<\infty.$

The above is bounded because of our assumption that
$\mathbb{E}_{\pi_{2:T}^{*}}\big{[}\big{|}f_{t}(\mathcal{H}_{t}^{(i)})\big{|}^{2+\alpha}\big{]}<\infty$
and
$\mathbb{E}_{\pi_{2:T}^{*}}\big{[}\big{|}f_{s}(\mathcal{H}_{s}^{(i)})\big{|}^{2+\alpha}\big{]}<\infty$.
Thus, we can apply the Weighted Martingale Triangular Array Weak Law of Large
Numbers (Theorem D.1) to get that

$\frac{1}{n}\sum_{i=1}^{n}\big{(}X_{1:T}^{(i)}\big{)}^{2}=\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{s=1}^{T}W_{2:\max(t,s)}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})f_{s}(\mathcal{H}_{s}^{(i)})+o_{P}(1)\\\
\overset{P}{\to}\sum_{t=1}^{T}\sum_{s=1}^{T}\mathbb{E}_{\pi_{2:T}^{*}}\left[f_{t}(\mathcal{H}_{t}^{(i)})f_{s}(\mathcal{H}_{s}^{(i)})\right]=\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\bigg{\\{}\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\bigg{\\}}^{2}\bigg{]}$

Additionally, note that

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[X_{1:T}^{(i)}\right]^{2}=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\bigg{]}^{2}=\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\bigg{]}^{2}.$

Thus,

$\frac{1}{n}\sum_{i=1}^{n}\left\\{\big{(}X_{1:T}^{(i)}\big{)}^{2}-\mathbb{E}\left[X_{1:T}^{(i)}\right]^{2}\right\\}\overset{P}{\to}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\bigg{\\{}\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\bigg{\\}}^{2}\bigg{]}-\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\bigg{]}^{2}\\\
=\textnormal{Var}_{\pi_{2:T}^{*}}\bigg{(}\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\bigg{)}.$

The last equality above holds since
$\textnormal{Var}_{\pi_{2:T}^{*}}\left(\sum_{t=1}^{T}f(\mathcal{H}_{t}^{(i)})\right)=\mathbb{E}_{\pi_{2:T}^{*}}\left[\left\\{\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\right\\}^{2}\right]-\mathbb{E}_{\pi_{2:T}^{*}}\left[\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\right]^{2}$.

2\. Showing Display (D.18) holds.

Note that
$\mathbb{E}\left[\mathbb{E}\big{[}X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\big{]}^{2}\right]=\mathbb{E}\left[\mathbb{E}_{\pi_{2:T}^{*}}\left[\sum_{t=1}^{T}f_{t}(\mathcal{H}_{t}^{(i)})\big{|}S_{1}^{(i)}\right]^{2}\right]$.
Also, note the following:

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\right]^{2}=\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\sum_{t=1}^{T}\mathbb{E}\left[W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t}(\mathcal{H}_{t}^{(i)})\big{|}S_{1}^{(1:n)}\right]\bigg{\\}}^{2}$
$=\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\sum_{t=1}^{T}\mathbb{E}_{\pi_{2:t}^{*}}\left[f_{t}(\mathcal{H}_{t}^{(i)})\big{|}S_{1}^{(1:n)}\right]\bigg{\\}}^{2}=\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\sum_{t=1}^{T}\mathbb{E}_{\pi_{2:t}^{*}}\left[f_{t}(\mathcal{H}_{t}^{(i)})\big{|}S_{1}^{(i)}\right]\bigg{\\}}^{2}$

Since
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}f_{t}(\mathcal{H}_{t}^{(i)})^{2}\big{]}<\infty$
by assumption, thus by Lemma B.2,
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{\\{}\sum_{t^{\prime}=1}^{t}f_{t}(\mathcal{H}_{t}^{(i)})\big{\\}}^{2}\big{]}<\infty$.
Since $S_{1}^{(1)},S_{1}^{(2)},S_{1}^{(3)},\dots S_{1}^{(n)}$ are i.i.d., by
the weak law of large numbers,

$\frac{1}{n}\sum_{i=1}^{n}\bigg{(}\bigg{\\{}\sum_{t=1}^{T}\mathbb{E}_{\pi_{2:t}^{*}}\left[f_{t}(\mathcal{H}_{t}^{(i)})\big{|}S_{1}^{(i)}\right]\bigg{\\}}^{2}-\mathbb{E}\bigg{[}\bigg{\\{}\sum_{t=1}^{T}\mathbb{E}_{\pi_{2:T}^{*}}\left[f_{t}(\mathcal{H}_{t}^{(i)})\big{|}S_{1}^{(i)}\right]\bigg{\\}}^{2}\bigg{]}\bigg{)}\overset{P}{\to}0$

Thus, we have that

$\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\right]^{2}\bigg{]}-\mathbb{E}\left[X_{1:T}^{(i)}\big{|}S_{1}^{(1:n)}\right]^{2}\bigg{\\}}\overset{P}{\to}0.$

3\. Showing Display (D.19) holds. Note that for any $t\in[1\colon T]$,

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

Recall $X_{t^{\prime}}^{(i)}\triangleq
W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})$.

$=\bigg{\\{}\sum_{t^{\prime}=1}^{t}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})+\mathbb{E}\bigg{[}\sum_{t^{\prime}=t+1}^{T}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\bigg{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\bigg{]}\bigg{\\}}^{2}$
$=\bigg{\\{}\sum_{t^{\prime}=1}^{t}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\\\
+W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\mathbb{E}\bigg{[}\sum_{t^{\prime}=t+1}^{T}W_{t+1:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\bigg{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\bigg{]}\bigg{\\}}^{2}$
$=\bigg{\\{}\sum_{t^{\prime}=1}^{t}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})+W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\mathbb{E}_{\pi_{t+1:T}^{*}}\bigg{[}\sum_{t^{\prime}=t+1}^{T}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\bigg{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\bigg{]}\bigg{\\}}^{2}$

Note
$\mathbb{E}_{\pi_{t+1:T}^{*}}\left[\sum_{t^{\prime}=t+1}^{T}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]=\mathbb{E}_{\pi_{t+1:T}^{*}}\left[\sum_{t^{\prime}=t+1}^{T}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\right]$,
since in the expectation actions are selected using fixed target policies
$\pi_{t+1:T}^{*}$ (the first expectation conditions on
$\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}$ and the second conditions on
$\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}$).

$=\bigg{\\{}\sum_{t^{\prime}=1}^{t}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})+W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\mathbb{E}_{\pi_{t+1:T}^{*}}\bigg{[}\sum_{t^{\prime}=t+1}^{T}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\bigg{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\bigg{]}\bigg{\\}}^{2}$

For convenience, let
$\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\triangleq
f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})$ for all $t^{\prime}\in[1\colon
t-1]$ and let $\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\triangleq
f_{t}(\mathcal{H}_{t}^{(i)})+\mathbb{E}_{\pi_{t+1:T}^{*}}\left[\sum_{t^{\prime}=t+1}^{T}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\right]$.

$=\bigg{\\{}\sum_{t^{\prime}=1}^{t}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\bigg{\\}}^{2}$
$=\underbrace{\bigg{\\{}\sum_{t^{\prime}=1}^{t-1}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\bigg{\\}}^{2}}_{\triangleq(U_{1:t-1}^{(i)})^{2}}+\underbrace{\bigg{\\{}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\bigg{\\}}^{2}}_{\triangleq(U_{t}^{(i)})^{2}}\\\
+2\underbrace{\bigg{\\{}\sum_{t^{\prime}=1}^{t-1}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\bigg{\\}}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})}_{\triangleq
U_{1:t-1}^{(i)}U_{t}^{(i)}}$ (D.23)

Using the above result to rewrite
$\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}$,
we can rewrite the left-hand side of display (D.19):

$\sum_{t=1}^{T}\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\bigg{[}\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\bigg{]}-\mathbb{E}\left[X_{1:T}^{(i)}\big{|}\mathcal{H}_{t}^{(1:n)},S_{t+1}^{(1:n)}\right]^{2}\bigg{\\}}$
$=\sum_{t=1}^{T}\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\left[(U_{1:t-1}^{(i)})^{2}+(U_{t}^{(i)})^{2}+2U_{1:t-1}U_{t}^{(i)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
-(U_{1:t-1}^{(i)})^{2}-(U_{t}^{(i)})^{2}-2U_{1:t-1}^{(i)}U_{t}^{(i)}\bigg{\\}}$

Note that $(U_{1:t-1}^{(i)})^{2}$ is a constant given
$\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}$ and cancel out in the display above.
Thus,

$=\frac{1}{n}2\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\left[U_{1:t-1}^{(i)}U_{t}^{(i)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]-U_{1:t-1}^{(i)}U_{t}^{(i)}\bigg{\\}}\\\
+\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\left[(U_{t}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]-(U_{t}^{(i)})^{2}\bigg{\\}}$
(D.24)

Before we show that display (D.24) converges in probability to zero, first
note the following useful results:

  * •

We first show that for all $t^{\prime}\in[1\colon T]$,

$\mathbb{E}_{\pi_{2:t^{\prime}}^{*}}\left[\big{|}\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\big{|}^{2+\alpha}\right]<\infty.$
(D.25)

For $t^{\prime}\in[1\colon t-1]$,
$\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})=f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})$.
Since
$\mathbb{E}_{\pi_{2:t^{\prime}}^{*}}\big{[}|f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})|^{2+\alpha}\big{]}<\infty$
by assumption.

For the $t^{\prime}=t$ case, recall
$\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})=f_{t}(\mathcal{H}_{t}^{(i)})+\sum_{t^{\prime}=t+1}^{T}\mathbb{E}_{\pi_{t+1:T}^{*}}\left[f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\right]$.
By repeatedly applying Lemma B.2 (Inequality Using Binomial Theorem) for any
numbers $a_{1},a_{2},...,a_{K}$, $|\sum_{k=1}^{K}a_{k}|^{2+\alpha}\leq
c_{2+\alpha}^{K}\sum_{k=1}^{K}|a_{k}|^{2+\alpha}$ for some constant
$c_{2+\alpha}>0$. Thus,

$\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{|}f_{t}(\mathcal{H}_{t}^{(i)})+\sum_{t^{\prime}=t+1}^{T}\mathbb{E}_{\pi_{t+1:T}^{*}}\left[f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\right]\bigg{|}^{2+\alpha}\bigg{]}\\\
\leq
c_{2+\alpha}^{T-t}\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\big{|}f_{t}(\mathcal{H}_{t}^{(i)})\big{|}^{2+\alpha}+\sum_{t^{\prime}=t+1}^{T}\bigg{|}\mathbb{E}_{\pi_{t+1:T}^{*}}\left[f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\right]\bigg{|}^{2+\alpha}\bigg{]}\\\
\leq
c_{2+\alpha}^{T-t}\sum_{t^{\prime}=t}^{T}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}^{2+\alpha}\right]<\infty.$

The second to last inequality above holds by Jensen’s inequality. The last
inequality holds since
$\mathbb{E}_{\pi_{2:t^{\prime}}^{*}}\big{[}|f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})|^{2+\alpha}\big{]}<\infty$
by assumption.

  * •

We now show that for all $t^{\prime},s\in[1\colon T]$,

$\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\tilde{f}_{s}(\mathcal{H}_{s}^{(i)},S_{s+1}^{(i)})\big{|}^{1+\alpha/2}\right]<\infty.$
(D.26)

Note that for any real numbers $a,b$, that $ab\leq\frac{1}{2}(a^{2}+b^{2})$.
Thus,

$\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\tilde{f}_{s}(\mathcal{H}_{s}^{(i)},S_{s+1}^{(i)})\big{|}^{1+\alpha/2}\right]\\\
\leq\frac{1}{2}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\big{|}^{2+\alpha}+\big{|}\tilde{f}_{s}(\mathcal{H}_{s}^{(i)},S_{s+1}^{(i)})\big{|}^{2+\alpha}\right]<\infty.$

The last inequality holds by display (D.25).

We now show that
$\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})=O_{P}(1)$.

  * •

For $t^{\prime}\in[1\colon t-1]$,
$\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})=f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})$
by definition. Since
$\mathbb{E}_{\pi_{2:t^{\prime}}^{*}}\big{[}|f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})|\big{]}<\infty$
by assumption, by Lemma D.3,
$\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})=f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})=O_{P}(1)$.

  * •

Recall that
$\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})=f_{t}(\mathcal{H}_{t}^{(i)})+\sum_{t^{\prime}=t+1}^{T}\mathbb{E}_{\pi_{t+1:T}^{*}}\left[f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\right]$
by definition. By Lemma D.3, $f_{t}(\mathcal{H}_{t}^{(i)})=O_{P}(1)$ since
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}|f_{t}(\mathcal{H}_{t}^{(i)})|\big{]}<\infty$
by assumption. Also note that by Jensen’s inequality,

$\mathbb{E}_{\pi_{2:t}^{*}}\left[\bigg{|}\mathbb{E}_{\pi_{t+1:T}^{*}}\left[f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\right]\bigg{|}\right]\leq\mathbb{E}_{\pi_{2:t}^{*}}\left[\mathbb{E}_{\pi_{t+1:T}^{*}}\left[\big{|}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\big{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\right]\right]\\\
=\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{|}f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\right]<\infty.$

Thus by Lemma D.3, we have that
$\mathbb{E}_{\pi_{t+1:T}^{*}}\left[f_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)})\big{|}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\right]=O_{P}(1)$.
Combining the above results we have that
$\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})=O_{P}(1)$.

3a. First Summation in Display (D.24)

$\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\left[U_{1:t-1}^{(i)}U_{t}^{(i)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]-U_{1:t-1}^{(i)}U_{t}^{(i)}\bigg{\\}}$
$=\frac{1}{n}\sum_{i=1}^{n}\bigg{(}\mathbb{E}\bigg{[}\bigg{\\{}\sum_{t^{\prime}=1}^{t-1}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\bigg{\\}}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\bigg{]}\\\
-\bigg{\\{}\sum_{t^{\prime}=1}^{t-1}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\bigg{\\}}W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\bigg{)}$
$=\sum_{t^{\prime}=1}^{t-1}\frac{1}{n}\sum_{i=1}^{n}\bigg{(}\mathbb{E}\bigg{[}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\bigg{]}\\\
-W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\bigg{)}$

  * •

Note the following for $t^{\prime}\in[1\colon t-1]$:

$\mathbb{E}\left[W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
\underbrace{=}_{(a)}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})W_{2:t-1}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\mathbb{E}\left[W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
\underbrace{=}_{(b)}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})W_{2:t-1}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
\underbrace{=}_{(c)}W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})W_{2:t-1}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]$
(D.27)

  * •

Equality (a) above holds since $t^{\prime}<t$, so
$W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})$ and
$\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})$
are constants given $\mathcal{H}_{t-1}^{(1:n)}$.

  * •

Equality (b) above holds since the Radon-Nikodym weighting changes the policy
with which actions are chosen with in the expectation.

  * •

Regarding equality (c), note that in the expectation indexed by $\pi_{t}^{*}$
that conditions on $\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}$, the only thing
that is integrated over is the distribution of $(A_{t}^{(i)},Y_{t}^{(i)})$.
Given $\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}$, when actions are selected using
the policy $\pi_{t}^{*}$, the distribution of $(A_{t}^{(i)},Y_{t}^{(i)})$ does
not depend on the data of other users, i.e.,
$\mathcal{H}_{t-1}^{(j)},S_{t}^{(j)}$ for $j\not=i$.

By display (D.27),

$=\sum_{t^{\prime}=1}^{t-1}\frac{1}{n}\sum_{i=1}^{n}\bigg{(}W_{2:t-1}^{(i)}(\beta^{*},\hat{\beta}^{(n)})W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]\\\
-W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\bigg{)}$

By display (D.25), Jensen’s inequality, and Lemma D.3, we have that
$\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})=O_{P}(1)$,
$\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})=O_{P}(1)$ and
$\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]=O_{P}(1)$.
Additionally, by display (D.22),
$W_{2:t^{\prime}}^{(i)}(\beta^{*},\hat{\beta}^{(n)})=1+O_{P}(1/\sqrt{n})$.
Thus,

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

The final limit above holds by the Weighted Martingale Triangular Array Weak
Law of Large Numbers (Theorem D.1); note we can apply Theorem D.1 because we
assume that Condition 2 holds and because
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\big{|}^{1+\alpha/2}\right]<\infty$
and
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t^{\prime}}(\mathcal{H}_{t^{\prime}}^{(i)},S_{t^{\prime}+1}^{(i)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]\right|^{1+\alpha/2}\right]<\infty$
by display (D.26) and Jensen’s inequality.

3b. Second Summation in Display (D.24)

$\frac{1}{n}\sum_{i=1}^{n}\bigg{\\{}\mathbb{E}\left[(U_{t}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]-(U_{t}^{(i)})^{2}\bigg{\\}}$
$=\frac{1}{n}\sum_{i=1}^{n}\bigg{(}\mathbb{E}\left[\left\\{W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\right\\}^{2}\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
-\left\\{W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})\right\\}^{2}\bigg{)}$

Since $W_{2:t-1}^{(i)}(\beta^{*},\hat{\beta}^{(n)})$ is a constant
$\mathcal{H}_{t-1}^{(1:n)}$ and since by the Radon-Nikodym weighting,
$\mathbb{E}\left[W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})^{2}\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
=\mathbb{E}_{\pi_{t}^{*}}\left[W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$,

$=\frac{1}{n}\sum_{i=1}^{n}\bigg{(}W_{2:t-1}^{(i)}(\beta^{*},\hat{\beta}^{(n)})^{2}\mathbb{E}_{\pi_{t}^{*}}\left[W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
-W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})^{2}\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\bigg{)}.$

Note the following observations:

  * •

By display (D.22),
$W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})=1+O_{P}(1/\sqrt{n})$. By display
(D.26) and Lemma D.3, we have that
$\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}=O_{P}(1)$. Thus,

$W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})^{2}\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}=W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}+O_{P}(1/\sqrt{n}).$
(D.28)

  * •

Additionally, for now, we take as given that

$\mathbb{E}_{\pi_{t}^{*}}\left[W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
=\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]+O_{P}(1/\sqrt{n}).$
(D.29)

For now, we take as given that display (D.29) holds; we prove this at the end
of this proof.

By displays (D.28) and (D.29) above,

$=\frac{1}{n}\sum_{i=1}^{n}\bigg{(}W_{2:t-1}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]\\\
-W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}+O_{P}(1/\sqrt{n})\bigg{)}$
$=o_{P}(1)+\frac{1}{n}\sum_{i=1}^{n}\bigg{(}W_{2:t-1}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]\\\
-W_{2:t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\bigg{)}\overset{P}{\to}0.$

The final limit above holds by the Weighted Martingale Triangular Array Weak
Law of Large Numbers (Theorem D.1); note we can apply Theorem D.1 because we
assume that Condition 2 holds and because by display (D.26) and Jensen’s
inequality,
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}^{1+\alpha/2}\right]<\infty$
and
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\left|\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]\right|^{1+\alpha/2}\right]<\infty$.

Now all that remains is to show that display (D.29) holds. We do this below:

  * •

Note the following:

$\mathbb{E}_{\pi_{t}^{*}}\left[W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
=\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]+\mathbb{E}_{\pi_{t}^{*}}\left[\big{\\{}W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})-1\big{\\}}\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
=\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]+\mathbb{E}_{\pi_{t}^{*}}\left[\big{\\{}W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})-1\big{\\}}\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$
(D.30)

The first equality above holds by adding and subtracting
$\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$.

The second equality above holds because the expectation
$\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$
only integrates over is the distribution of $(A_{t}^{(i)},Y_{t}^{(i)})$; given
$\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}$, when actions are selected using the
policy $\pi_{t}^{*}$, the distribution of $(A_{t}^{(i)},Y_{t}^{(i)})$ does not
depend on the data of other users, i.e., $\mathcal{H}_{t-1}^{(j)},S_{t}^{(j)}$
for $j\not=i$.

  * •

Now consider just the second term in the last line of display (D.30) above:

$\mathbb{E}_{\pi_{t}^{*}}\left[\big{\\{}W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})-1\big{\\}}\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
\leq\mathbb{E}_{\pi_{t}^{*}}\left[\big{|}W_{t}^{(i)}(\beta^{*},\hat{\beta}^{(n)})-1\big{|}\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
\underbrace{\leq}_{(a)}\pi_{\min}^{-2}\max_{a\in\mathcal{A}}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\big{\|}\hat{\beta}_{t-1}^{(n)}-\beta_{t-1}^{*}\big{\|}_{2}\\\
\underbrace{=}_{(b)}O_{P}(1/\sqrt{n}).$

Above inequality (a) holds by display (D.21); we are able to move the terms
$\max_{a\in\mathcal{A}}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}$ and
$\big{\|}\hat{\beta}_{t-1}^{(n)}-\beta_{t-1}^{*}\big{\|}_{2}$ out of the
conditional expectation they are known given
$\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}$.

Above limit (b) holds because (i) $\hat{\beta}_{t-1}^{(n)}=O_{P}(1/\sqrt{n})$
by assumption,
(ii)
$\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]=\mathbb{E}_{\pi_{t}^{*}}\left[\tilde{f}_{t}(\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)})^{2}\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right]=O_{P}(1)$
by display (D.26), Jensen’s inequality, and Lemma D.3, and
(iii)
$\max_{a\in\mathcal{A}}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}=O_{P}(1)$;
this holds by Lemma D.3 since

$\mathbb{E}_{\pi_{2:t-1}^{*}}\left[\big{|}\max_{a\in\mathcal{A}}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}\big{|}\right]\underbrace{\leq}_{(a)}\sum_{a\in\mathcal{A}}\mathbb{E}_{\pi_{2:t-1}^{*}}\left[\big{|}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}\big{|}\right]\\\
=|\mathcal{A}|\sum_{a\in\mathcal{A}}\mathbb{E}_{\pi_{2:t-1}^{*}}\left[|\mathcal{A}|^{-1}\big{|}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}\big{|}\right]\underbrace{=}_{(b)}|\mathcal{A}|\mathbb{E}_{\pi_{2:t-1}^{*},\pi_{t}^{\textnormal{uniform}}}\left[\big{|}\dot{\pi}_{t}\big{(}A_{t}^{(i)},S_{t}^{(i)}\big{)}\big{|}\right]\\\
\underbrace{=}_{(c)}|\mathcal{A}|\mathbb{E}_{\pi_{2:t}^{*}}\left[\frac{\pi_{t}^{\textnormal{uniform}}(A_{t}^{(i)},S_{t}^{(i)})}{\pi_{t}^{*}(A_{t}^{(i)},S_{t}^{(i)})}\big{|}\dot{\pi}_{t}\big{(}a,S_{t}^{(i)}\big{)}\big{|}\right]\\\
\underbrace{\leq}_{(d)}|\mathcal{A}|\pi_{\min}^{-1}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}\dot{\pi}_{t}\big{(}A_{t}^{(i)},S_{t}^{(i)}\big{)}\big{|}\right]\underbrace{\leq}_{(e)}\infty.$

Inequality (a) above holds since the action space $\mathcal{A}$ is a finite
set.

Equality (b) holds for
$\pi_{t}^{\textnormal{uniform}}(A_{t}^{(i)},S_{t}^{(i)})\triangleq|\mathcal{A}|^{-1}$,
i.e., the policy that selects action uniformly over the action space
$\mathcal{A}$ for the $t^{\textnormal{th}}$ action.

Equality (c) uses Radon-Nikodym derivative weights.

Inequality (d) above holds by exploration Condition 2.

Inequality (e) holds by Condition 3. $\blacksquare$

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

######  Theorem D.5 (Functional Asymptotic Normality under Finite Bracketing
Integral for Adaptively Sampled Data).

Let $\mathcal{F}$ be any class of real-valued measurable functions of
$\mathcal{H}_{t}^{(i)}$ such that for all $f\in\mathcal{F}$, for some
$\alpha>0$, $\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon<\infty$.
Let Conditions 2 (Minimum Exploration) and 3 (Lipschitz Policy Functions) hold
and also let
$\hat{\beta}_{t^{\prime}}^{(n)}-\beta_{t^{\prime}}^{*}=O_{P}(1/\sqrt{n})$ for
all $t^{\prime}\in[1\colon t-1]$. Then for

$\mathbb{G}_{\mathcal{F}}^{(n)}(f)\triangleq\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})-\mathbb{E}\big{[}\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\big{]}\right),$

the empirical process
$\big{\\{}\mathbb{G}_{\mathcal{F}}^{(n)}(f):f\in\mathcal{F}\big{\\}}$
converges in distribution to $\mathbb{G}_{\mathcal{F}}$ a mean-zero Gaussian
process in $\ell^{\infty}(\mathcal{F})$ (the collection of all bounded
functions from $\mathcal{F}$ to ) with the following covariance function:

$\mathbb{E}\big{[}\mathbb{G}_{\mathcal{F}}(f)\mathbb{G}_{\mathcal{F}}(g)\big{]}\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\left(\big{\\{}\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)})]\right)\\\
\left(\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})\big{]}\right)\bigg{]}.$
(D.31)

Above we use
$\pi_{2:t}^{*,(i)}\triangleq\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}^{*}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})$.

Proof of Theorem D.5. By [Van der Vaart, 2000, Theorem 18.14], to show the
desired result it is sufficient to show that the following two properties
hold:

  1. (a)

Joint Convergence of Marginals For any finite number of functions
$f_{1},f_{2},...,f_{K}\in\mathcal{F}$,

$\bigg{(}\mathbb{G}_{\mathcal{F}}^{(n)}(f_{1}),\mathbb{G}_{\mathcal{F}}^{(n)}(f_{2}),...,\mathbb{G}_{\mathcal{F}}^{(n)}(f_{K})\bigg{)}\overset{D}{\to}\bigg{(}\mathbb{G}_{\mathcal{F}}(f_{1}),\mathbb{G}_{\mathcal{F}}(f_{2}),...,\mathbb{G}_{\mathcal{F}}(f_{K})\bigg{)}$

  2. (b)

Asymptotically Tight For any $\epsilon,\eta>0$, there exists a partition of
$\mathcal{F}$ into finitely many sets
$\mathcal{F}_{1},\mathcal{F}_{2},...,\mathcal{F}_{J}$ such that

$\limsup_{n\to\infty}\mathbb{P}^{*}\bigg{(}\sup_{j\in[1\colon
J]}\sup_{f,f^{\prime}\in\mathcal{F}_{j}}\left|\mathbb{G}_{\mathcal{F}}^{(n)}(f)-\mathbb{G}_{\mathcal{F}}^{(n)}(f^{\prime})\right|>\epsilon\bigg{)}\leq\eta.$

Showing (a) Joint Convergence of Marginals. We can show that (a) above holds
for the stochastic process
$\big{\\{}\mathbb{G}_{\mathcal{F}}^{(n)}(f):f\in\mathcal{F}\big{\\}}$ by the
Theorem D.4 (Weighted Martingale Triangular Array Central Limit Theorem).

Specifically, by Cramer Wold device, it is sufficient to show that for any
$c=[c_{1},c_{2},\dots,c_{K}]\in{}^{K}$ that

$\sum_{k=1}^{K}c_{k}\mathbb{G}_{\mathcal{F}}^{(n)}(f_{k})\overset{D}{\to}\mathcal{N}\left(0,c^{\top}\begin{bmatrix}\Sigma_{1,1}&\Sigma_{1,2}&\dots&\Sigma_{1,K}\\\
\Sigma_{2,1}&\Sigma_{2,2}&\dots&\Sigma_{2,K}\\\ \vdots&\vdots&\ddots&\vdots\\\
\Sigma_{K,1}&\Sigma_{K,2}&\dots&\Sigma_{K,K}\\\ \end{bmatrix}c\right)$

where
$\Sigma_{k,k^{\prime}}\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\left[\mathbb{G}_{\mathcal{F}}(f_{k})\mathbb{G}_{\mathcal{F}}(f_{k^{\prime}})\right]$.

Note that

$\sum_{k=1}^{K}c_{k}\mathbb{G}_{\mathcal{F}}^{(n)}(f_{k})=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bigg{(}\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}\sum_{k=1}^{K}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})-\mathbb{E}\bigg{[}\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}\sum_{k=1}^{K}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\bigg{]}\bigg{)}$
$=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bigg{(}W_{2:t}^{(i)}\big{(}\beta^{*},\hat{\beta}^{(n)}\big{)}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}\sum_{k=1}^{K}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\\\
-\mathbb{E}\bigg{[}W_{2:t}^{(i)}\big{(}\beta^{*},\hat{\beta}^{(n)}\big{)}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}\sum_{k=1}^{K}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\bigg{]}\bigg{)}\overset{D}{\to}\mathcal{N}\left(0,\bar{\Sigma}\right),$

where

$\bar{\Sigma}\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{(}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}\sum_{k=1}^{K}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\bigg{)}^{2}\bigg{]}-\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}\sum_{k=1}^{K}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\bigg{]}^{2}.$
(D.32)

The above weak convergence holds by Theorem D.4 (Weighted Martingale
Triangular Array Central Limit Theorem). When applying Theorem D.4, we use the
following properties:

  * •

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]$.

  * •

Recall that for some $\alpha>0$, $\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon<\infty$.
This means that for all $f\in\mathcal{F}$, we can find a bracket
$(l_{j},u_{j})$ such that $l_{j}(\mathcal{H}_{t}^{(i)})\leq
f(\mathcal{H}_{t}^{(i)})\leq u_{j}(\mathcal{H}_{t}^{(i)})$ a.s. Additionally,
recall that the brackets are such that
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}l\big{(}\mathcal{H}_{t}^{(i)}\big{)}\big{|}^{2+\alpha}\big{]}<\infty$
and
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u\big{(}\mathcal{H}_{t}^{(i)}\big{)}\big{|}^{2+\alpha}\big{]}<\infty$.
Thus, for all $f\in\mathcal{F}$,

$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}f\big{(}\mathcal{H}_{t}^{(i)}\big{)}\big{|}^{2+\alpha}\big{]}\leq\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}l\big{(}\mathcal{H}_{t}^{(i)}\big{)}\big{|}^{2+\alpha}\big{]}+\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u\big{(}\mathcal{H}_{t}^{(i)}\big{)}\big{|}^{2+\alpha}\big{]}<\infty.$

Thus, by repeatedly applying Lemma B.2, for some positive constant
$c_{2+\alpha}<\infty$, the following result holds:

$\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{|}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}\sum_{k=1}^{K}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\bigg{|}^{2+\alpha}\bigg{]}\leq
c_{2+\alpha}^{K}\sum_{k=1}^{K}\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{|}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\bigg{|}^{2+\alpha}\bigg{]}\\\
\leq
c_{2+\alpha}^{K}\sum_{k=1}^{K}\pi_{\min}^{(t-1)(2+\alpha)}|c_{k}|^{2+\alpha}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}f_{k}(\mathcal{H}_{t}^{(i)})\big{|}^{2+\alpha}\right]<\infty.$

The last inequality above holds by Condition 2.

By the definition of $\bar{\Sigma}$ from display (D.32),

$\bar{\Sigma}=\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{(}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}\sum_{k=1}^{K}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\bigg{)}^{2}\bigg{]}-\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}\sum_{k=1}^{K}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\bigg{]}^{2}$
$=\sum_{k=1}^{K}\sum_{k^{\prime}=1}^{K}\bigg{\\{}\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}c_{k^{\prime}}f_{k^{\prime}}(\mathcal{H}_{t}^{(i)})\bigg{]}\\\
-\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}c_{k}f_{k}(\mathcal{H}_{t}^{(i)})\right]\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}c_{k^{\prime}}f_{k^{\prime}}(\mathcal{H}_{t}^{(i)})\right]\bigg{\\}}$
$=\sum_{k=1}^{K}\sum_{k^{\prime}=1}^{K}c_{k}c_{k^{\prime}}\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{(}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f_{k}(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f_{k}(\mathcal{H}_{t}^{(i)})\right]\bigg{)}\\\
\bigg{(}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f_{k^{\prime}}(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f_{k^{\prime}}(\mathcal{H}_{t}^{(i)})\right]\bigg{)}\bigg{]}$

By the definition of
$\mathbb{E}\big{[}\mathbb{G}_{\mathcal{F}}(f_{k})\mathbb{G}_{\mathcal{F}}(f_{k^{\prime}})\big{]}$
from display (D.31),

$=\sum_{k=1}^{K}\sum_{k^{\prime}=1}^{K}c_{k}c_{k^{\prime}}\mathbb{E}\big{[}\mathbb{G}_{\mathcal{F}}(f_{k})\mathbb{G}_{\mathcal{F}}(f_{k^{\prime}})\big{]}=\sum_{k=1}^{K}\sum_{k^{\prime}=1}^{K}c_{k}c_{k^{\prime}}\Sigma_{k,k^{\prime}}=c^{\top}\begin{bmatrix}\Sigma_{1,1}&\Sigma_{1,2}&\dots&\Sigma_{1,K}\\\
\Sigma_{2,1}&\Sigma_{2,2}&\dots&\Sigma_{2,K}\\\ \vdots&\vdots&\ddots&\vdots\\\
\Sigma_{K,1}&\Sigma_{K,2}&\dots&\Sigma_{K,K}\\\ \end{bmatrix}c.$

The second equality above holds since recall
$\Sigma_{k,k^{\prime}}\triangleq\mathbb{E}\big{[}\mathbb{G}_{\mathcal{F}}(f_{k})\mathbb{G}_{\mathcal{F}}(f_{k^{\prime}})\big{]}$.

Thus, we have shown that $\bar{\Sigma}$ from display (D.32) is such that

$\bar{\Sigma}=c^{\top}\begin{bmatrix}\Sigma_{1,1}&\Sigma_{1,2}&\dots&\Sigma_{1,K}\\\
\Sigma_{2,1}&\Sigma_{2,2}&\dots&\Sigma_{2,K}\\\ \vdots&\vdots&\ddots&\vdots\\\
\Sigma_{K,1}&\Sigma_{K,2}&\dots&\Sigma_{K,K}\\\ \end{bmatrix}c.$

Showing (b) Asymptotically Tight. The asymptotically tight condition above
holds by the same argument used in the proof of Theorem 19.5 from Van der
Vaart [2000], but by replacing the use of maximal inequality Lemma 19.34 of
Van der Vaart [2000] in that proof with our maximal inequality from Lemma E.4
(Maximal Inequality as a Function of the Bracketing Integral). We discuss this
argument below.

Let $\epsilon,\delta>0$. Since $\mathcal{F}$ has finite bracketing integral by
assumption, we can find a partition of $\mathcal{F}$ into finitely many sets
$\mathcal{F}_{1},\mathcal{F}_{2},...,\mathcal{F}_{N_{\delta_{0}}}$ where
$N_{\delta_{0}}\triangleq
N_{[~{}]}\big{(}\delta_{0},\mathcal{F},L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}$
and $\delta_{0}\triangleq\delta\sqrt{\pi_{\min}^{-(t-1)}}$. Note that

$\mathbb{P}^{*}\bigg{(}\sup_{j\in[1\colon
N_{\delta_{0}}]}\sup_{f,f^{\prime}\in\mathcal{F}_{j}}\left|\mathbb{G}_{\mathcal{F}}^{(n)}(f)-\mathbb{G}_{\mathcal{F}}^{(n)}(f^{\prime})\right|>\epsilon\bigg{)}$

Above $\mathbb{P}^{*}$ refers to outer probabilities as defined in Section
18.2 Van der Vaart [2000].

$=\mathbb{P}^{*}\bigg{(}\sup_{j\in[1\colon
N_{\delta_{0}}]}\sup_{f,f^{\prime}\in\mathcal{F}_{j}}\left|\mathbb{G}_{\mathcal{F}}^{(n)}(f-f^{\prime})\right|>\epsilon\bigg{)}$

By Markov inequality,

$\leq\frac{1}{\epsilon}\mathbb{E}^{*}\bigg{[}\sup_{j\in[1\colon
N_{\delta_{0}}]}\sup_{f,f^{\prime}\in\mathcal{F}_{j}}\left|\mathbb{G}_{\mathcal{F}}^{(n)}(f-f^{\prime})\right|\bigg{]}.$

Let $\mathcal{G}_{\delta}$ be the function class such that
$\mathcal{G}_{\delta}\triangleq\big{\\{}f-f^{\prime}\textnormal{~{}~{}s.t.~{}~{}}f,f^{\prime}\in\mathcal{F}_{j},j\in[1\colon
N_{\delta_{0}}]\big{\\}}$. Note the following observations:

  * •

Note that for any $f,f^{\prime}\in\mathcal{F}_{j}$,
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}f(\mathcal{H}_{t}^{(i)})-f^{\prime}(\mathcal{H}_{t}^{(i)})\big{\\}}^{2}\right]\leq\delta_{0}^{2}$;
thus
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}g(\mathcal{H}_{t}^{(i)})^{2}\big{]}\leq\delta_{0}^{2}$
for any $g\in\mathcal{G}_{\delta}$. Note that by Condition 2, this implies
that
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})^{2}\right]\leq\pi_{\min}^{-(t-1)}\mathbb{E}_{\pi_{2:t}^{*}}\left[g(\mathcal{H}_{t}^{(i)})^{2}\right]\leq\pi_{\min}^{-(t-1)}\delta_{0}^{2}=\delta^{2}$
for all $g\in\mathcal{G}_{\delta}$

  * •

We take as given for now that

$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon,\mathcal{G}_{\delta},L_{2}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}}d\epsilon<\infty.$
(D.33)

We show the above holds at the end of this proof.

  * •

We also take as given that there exists a non-negative envelope function $G$
where $\big{|}g(\mathcal{H}_{t}^{(i)})\big{|}\leq G(\mathcal{H}_{t}^{(i)})$
a.s. for all $g\in\mathcal{G}_{\delta}$ and
$\mathbb{E}_{\pi_{2:t}^{*}}\left[G(\mathcal{H}_{t}^{(i)})^{2}\right]<\infty$
(we show this at the end of this proof).

Using the above observations and Condition 2, we can apply Lemma E.4 (Maximal
Inequality as a Function of the Bracketing Integral) to get that

$\lesssim\frac{1}{\epsilon}\bigg{\\{}\int_{0}^{\delta}\sqrt{\log
N_{[~{}]}\big{(}\eta,\mathcal{G}_{\delta},L_{2}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}}d\eta+\sqrt{n}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}G(\mathcal{H}_{t}^{(i)})\mathbb{I}_{G(\mathcal{H}_{t}^{(i)})>\sqrt{n}a(\delta)}\right]\bigg{\\}},$
(D.34)

where $a(\delta)\triangleq\delta/\sqrt{\log
N_{[~{}]}\big{(}\delta,\mathcal{G}_{\delta},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}}$.
Above $\lesssim$ means less than or equal to when scaled by universal positive
constants.

  * •

By display (D.33), the first term (integral term) in display (D.34) converges
to zero as $\delta\to 0$.

  * •

Regarding the second term in display (D.34), since
$\mathbb{I}_{G(\mathcal{H}_{t}^{(i)})>\sqrt{n}a(\delta)}=1$ implies that
$G(\mathcal{H}_{t}^{(i)})\big{\\{}\sqrt{n}a(\delta)\big{\\}}^{-1}>1$, thus,
$\big{|}G(\mathcal{H}_{t}^{(i)})\big{\\{}\sqrt{n}a(\delta)\big{\\}}^{-1}\big{|}\geq\mathbb{I}_{G(\mathcal{H}_{t}^{(i)})>\sqrt{n}a(\delta)}$.

$\sqrt{n}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}G(\mathcal{H}_{t}^{(i)})\mathbb{I}_{G(\mathcal{H}_{t}^{(i)})>\sqrt{n}a(\delta)}\right]\leq
a(\delta)^{-1}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}G(\mathcal{H}_{t}^{(i)})^{2}\right]\\\
\leq
a(\delta)^{-1}\pi_{\min}^{-(t-1)}\mathbb{E}_{\pi_{2:t}^{*}}\left[G(\mathcal{H}_{t}^{(i)})^{2}\right].$

The last inequality above holds by Condition 2. The above goes to zero as
$n\to\infty$ for every fixed $\delta$.

Thus, we have that display (D.34) converges to zero; this is sufficient for
the Theorem to hold. All that remains is to show that display (D.33) holds and
that we can find an envelope function $G$. We do this below.

Bracketing Functions for $\mathcal{G}_{\delta}$; display (D.33). Let $\eta>0$.
Since $\mathcal{F}$ has finite bracketing integral by assumption, we can find
$N_{\eta}\triangleq
N_{[~{}]}\big{(}\eta,\mathcal{F},L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\big{)}$
bracketing functions $\big{\\{}(l_{k},u_{k})\big{\\}}_{k=1}^{N_{\eta}}$. Note
that for any $g\in\mathcal{G}_{\delta}$, we can find some
$f,f^{\prime}\in\mathcal{F}$ such that $g=f-f^{\prime}$.

We will show that the brackets
$\big{\\{}(l_{k}-u_{k^{\prime}},~{}u_{k}-l_{k^{\prime}})\big{\\}}_{k=1;k^{\prime}=1}^{k=N_{\eta};k^{\prime}=N_{\eta}}$
will cover $\mathcal{G}_{\delta}$ and be of size $2\sqrt{c_{2}}\eta$ in
$L_{2+\alpha}(\mathcal{P}_{\pi^{*}})$ norm for a positive constant
$c_{2}<\infty$.

Covering: We can find brackets $(l_{k},u_{k})$ and
$(l_{k^{\prime}},u_{k^{\prime}})$ such that $l_{k}(\mathcal{H}_{t}^{(i)})\leq
f(\mathcal{H}_{t}^{(i)})\leq u_{k}(\mathcal{H}_{t}^{(i)})$ a.s. and
$l_{k^{\prime}}(\mathcal{H}_{t}^{(i)})\leq
f^{\prime}(\mathcal{H}_{t}^{(i)})\leq u_{k^{\prime}}(\mathcal{H}_{t}^{(i)})$
a.s. Thus,
$l_{k}(\mathcal{H}_{t}^{(i)})-u_{k^{\prime}}(\mathcal{H}_{t}^{(i)})\leq
f(\mathcal{H}_{t}^{(i)})-f^{\prime}(\mathcal{H}_{t}^{(i)})\leq
u_{k}(\mathcal{H}_{t}^{(i)})-l_{k^{\prime}}(\mathcal{H}_{t}^{(i)})$ a.s.

Size: Note that

$\sqrt{\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u_{k}(\mathcal{H}_{t}^{(i)})-l_{k^{\prime}}(\mathcal{H}_{t}^{(i)})-l_{k}(\mathcal{H}_{t}^{(i)})+u_{k^{\prime}}(\mathcal{H}_{t}^{(i)})\big{|}^{2}\big{]}}$

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

$\leq\sqrt{c_{2}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u_{k}(\mathcal{H}_{t}^{(i)})-l_{k}(\mathcal{H}_{t}^{(i)})\big{|}^{2}\big{]}+c_{2}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u_{k^{\prime}}(\mathcal{H}_{t}^{(i)})-l_{k^{\prime}}(\mathcal{H}_{t}^{(i)})\big{|}^{2}\big{]}}$

Since $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for $a,b>0$ (to see this square both
sides),

$\leq\sqrt{c_{2}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u_{k}(\mathcal{H}_{t}^{(i)})-l_{k}(\mathcal{H}_{t}^{(i)})\big{|}^{2}\big{]}}+\sqrt{c_{2}\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u_{k^{\prime}}(\mathcal{H}_{t}^{(i)})-l_{k^{\prime}}(\mathcal{H}_{t}^{(i)})\big{|}^{2}\big{]}}$
$\leq 2\sqrt{c_{2}}\eta.$

We now discuss why the last inequality above holds. By construction of our
bracketing functions,
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}u_{k}(\mathcal{H}_{t}^{(i)})-l_{k}(\mathcal{H}_{t}^{(i)})\big{|}^{2+\alpha}\big{]}^{1/(2+\alpha)}\leq\eta$.
Note that $h(x)=x^{1+\alpha/2}$ is convex. By Jensen’s inequality,

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

Thus, we have that

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

By taking the square root of both sides,

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

Bracketing Number: By the above results we have that

$N_{[~{}]}\left(2\sqrt{c_{2}}\eta,\mathcal{G}_{\delta},L_{2}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\right)\leq
N_{[~{}]}\left(\eta,\mathcal{F},L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\right)^{2}.$

Moreover,

$N_{[~{}]}\big{(}\eta,\mathcal{G},L_{2}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}\leq
N_{[~{}]}\big{(}\eta/(2\sqrt{c_{2}}),\mathcal{F},L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}^{2}.$

Thus,

$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\eta,\mathcal{G},L_{2}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}}d\eta\leq\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\eta/(2\sqrt{c_{2}}),\mathcal{F},L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}^{2}}d\eta$

By exponent property of $\log$,

$=\sqrt{2}\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\eta/(2\sqrt{c_{2}}),\mathcal{F},L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}}d\eta$

We now use integration by substitution, with $u=\eta/(2\sqrt{c_{2}})$; note
that $\frac{\partial{u}}{\partial{\eta}}=(2\sqrt{c_{2}})^{-1}$.

$=\sqrt{2}(2\sqrt{c_{2}})\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\eta/(2\sqrt{c_{2}}),\mathcal{F},L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}}(2\sqrt{c_{2}})^{-1}d\eta$
$=\sqrt{2}(2\sqrt{c_{2}})\int_{0}^{(2\sqrt{c_{2}})^{-1}}\sqrt{\log
N_{[~{}]}\big{(}u,\mathcal{F},L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}}du<\infty.$

The above is bounded by our assumption that $\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}u,\mathcal{F},L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}}du$.
Note that if $(2\sqrt{c_{2}})^{-1}\leq 1$, the result above holds directly by
this assumption. If $(2\sqrt{c_{2}})^{-1}>1$, the result above holds because
$N_{[~{}]}\big{(}\eta,\mathcal{F},L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}\leq
N_{[~{}]}\big{(}1,\mathcal{F},L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}$
for all $\eta>1$.

Envelope Function for $\mathcal{G}_{\delta}$: We can construct the envelope
function for $\mathcal{G}_{\delta}$ using the brackets for
$\mathcal{G}_{\delta}$ that we constructed above. Specifically, the envelope
function $G$ can be taken to be the supremum of the upper and lower bracketing
functions for $\mathcal{G}_{\delta}$. This envelope function will be such that
$\mathbb{E}_{\pi_{2:t}^{*}}\left[G(\mathcal{H}_{t}^{(i)})^{2}\right]<\infty$
since the brackets we constructed for $\mathcal{G}_{\delta}$ have finite
$L_{2+\alpha}\big{(}\mathcal{P}_{\pi^{*}}\big{)}$ norm (see Section A.4.1 for
more on the definition of bracketing functions we use). $\blacksquare$

###  D.6 Stochastic Equicontinuity (Lemma D.6)

######  Lemma D.6 (Stochastic Equicontinuity).

Let $t\in[1\colon T-1]$ and let $\mathcal{F}$ be a class of real-valued,
measurable functions of $\mathcal{H}_{t}^{(i)}$ such that
$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\left(\epsilon,\mathcal{F},L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon<\infty$
for some constant $\alpha>0$. Let $\hat{f}^{(n)}\in\mathcal{F}$ be a sequence
of functions such that $\nu\big{(}\hat{f}^{(n)},f_{0}\big{)}\overset{P}{\to}0$
for some $f_{0}\in\mathcal{F}$ where
$\nu(f,g)\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}f\big{(}\mathcal{H}_{t}^{(i)}\big{)}-g\big{(}\mathcal{H}_{t}^{(i)}\big{)}\big{|}^{2}\right]^{1/2}$.

Under Conditions 2 and 3, and the condition that
$\hat{\beta}_{1:t-1}^{(n)}-\beta_{1:t-1}^{*}=O_{P}(1/\sqrt{n})$ we have that

$\mathbb{G}_{\mathcal{F}}^{(n)}\big{(}\hat{f}^{(n)}\big{)}-\mathbb{G}_{\mathcal{F}}^{(n)}\big{(}f_{0}\big{)}\overset{P}{\to}0$
(D.35)

where

$\mathbb{G}_{\mathcal{F}}^{(n)}(f)\triangleq\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})-\mathbb{E}\big{[}\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\big{]}\right).$

Proof of Lemma D.6. We use an argument akin to that of Lemma 19.24 of Van Der
Vaart and Wellner [1996], which is for i.i.d. data. We use
$\ell^{\infty}(\mathcal{F})$ to refer to the collection of all bounded
functions from $\mathcal{F}$ to .

By Theorem D.5 (Functional Asymptotic Normality under Finite Bracketing
Integral), the following stochastic process converges weakly to a mean-zero
Gaussian Process $\mathbb{G}_{\mathcal{F}}\in\ell^{\infty}(\mathcal{F})$:

$\mathbb{G}_{\mathcal{F}}^{(n)}\triangleq\left\\{\mathbb{G}_{\mathcal{F}}^{(n)}(f)\textnormal{~{}~{}s.t.~{}~{}}f\in\mathcal{F}\right\\}\overset{D}{\to}\mathbb{G}_{\mathcal{F}},$
(D.36)

where the limit $\mathbb{G}_{\mathcal{F}}$ has the following covariance
function:

$\mathbb{E}\big{[}\mathbb{G}_{\mathcal{F}}(f)\mathbb{G}_{\mathcal{F}}(g)\big{]}\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\left(\big{\\{}\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)})]\right)\\\
\left(\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})\big{]}\right)\bigg{]}.$
(D.37)

We are able to apply Theorem D.5 because of our assumptions that Conditions 2
and 3 hold, and since we’ve assumed that $\int_{0}^{1}\sqrt{\log
N_{[~{}]}\left(\epsilon,\mathcal{F},L_{2+\alpha}(\mathcal{P}_{\pi^{*}})\right)}d\epsilon<\infty$
and $\hat{\beta}_{1:t-1}^{(n)}-\beta_{1:t-1}^{*}=O_{P}(1/\sqrt{n})$.

By Lemma 18.15 of Van der Vaart [2000], the weak convergence result from
display (D.36) implies that the limit $\mathbb{G}_{\mathcal{F}}$ can be
constructed to have almost all sample paths in
$\textnormal{UC}(\mathcal{F},\rho)$, the collection of all uniformly
continuous functions from $\mathcal{F}$ to ; $\rho$ is the standard deviation
semi-metric:

$\rho(f,g)\triangleq\sqrt{\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}\mathbb{G}_{\mathcal{F}}(f)-\mathbb{G}_{\mathcal{F}}(g)\big{|}^{2}\right]}$

For now, we take as given that
$\rho\big{(}\hat{f}^{(n)},f_{0}\big{)}\overset{P}{\to}0$ (we show this at the
end of this proof). Thus, we have that $\hat{f}^{(n)}\overset{P}{\to}f_{0}$.
By Slutsky’s theorem and the convergence result from display (D.36), we have
that
$\big{(}\mathbb{G}_{\mathcal{F}}^{(n)},\hat{f}^{(n)}\big{)}\overset{D}{\to}\big{(}\mathbb{G}_{\mathcal{F}},f_{0}\big{)}$.

Consider the evaluation function
$g:\ell^{\infty}(\mathcal{F})\times\mathcal{F}\mapsto\real$ where
$g(\mathbb{G},f)\triangleq\mathbb{G}(f)-\mathbb{G}(f_{0})$. Note that the
evaluation mapping $g$ is continuous at
$\big{(}z,f\big{)}\in\ell^{\infty}(\mathcal{F})\times\mathcal{F}$ if $z$ is
continuous at $f$; this is discussed in the proof of Lemma 18.15 of Van der
Vaart [2000]. Since, as discussed earlier, $\mathbb{G}_{\mathcal{F}}$ can be
constructed to have almost all sample paths in
$\textnormal{UC}(\mathcal{F},\rho)$, thus $\mathbb{G}_{\mathcal{F}}$ is at
$f_{0}$ for almost all sample paths and the evaluation mapping $g$ is
continuous at $\big{(}\mathbb{G}_{\mathcal{F}},f_{0}\big{)}$ for almost all
sample paths.

Thus, by the continuous mapping theorem, we have that

$\mathbb{G}_{\mathcal{F}}^{(n)}\big{(}\hat{f}^{(n)}\big{)}-\mathbb{G}_{0}\big{(}f_{0}\big{)}=g\big{(}\mathbb{G}_{\mathcal{F}}^{(n)},\hat{f}^{(n)}\big{)}\overset{D}{\to}g\big{(}\mathbb{G}_{\mathcal{F}},f_{0}\big{)}=\mathbb{G}_{\mathcal{F}}\big{(}f_{0}\big{)}-\mathbb{G}_{\mathcal{F}}\big{(}f_{0}\big{)}=0.$
(D.38)

Since convergence in distribution to a constant implies convergence in
probability, display (D.38) above implies the main result display (D.35)
holds.

We now show that $\rho\big{(}\hat{f}^{(n)},f_{0}\big{)}\overset{P}{\to}0$.
Note that for any functions $f,g\in\mathcal{F}$,

$\rho(f,g)^{2}=\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}\mathbb{G}_{\mathcal{F}}(f)-\mathbb{G}_{\mathcal{F}}(g)\big{|}^{2}\right]$
$=\mathbb{E}_{\pi_{2:t}^{*}}\left[\mathbb{G}_{\mathcal{F}}(f)^{2}-2\mathbb{G}_{\mathcal{F}}(f)\mathbb{G}_{\mathcal{F}}(g)+\mathbb{G}_{\mathcal{F}}(g)^{2}\right]$

Using the covariance expression from display (D.37), we have that for
$G(\mathcal{H}_{t}^{(i)};f)\triangleq\big{\\{}\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)})]$,

$=\mathbb{E}_{\pi_{2:t}^{*}}\left[G(\mathcal{H}_{t}^{(i)};f)^{2}-2G(\mathcal{H}_{t}^{(i)};f)G(\mathcal{H}_{t}^{(i)};g)+G(\mathcal{H}_{t}^{(i)};g)^{2}\right]$
$=\mathbb{E}_{\pi_{2:t}^{*}}\left[\left\\{G(\mathcal{H}_{t}^{(i)};f)-G(\mathcal{H}_{t}^{(i)};g)\right\\}^{2}\right]$

By the definition of $G(\mathcal{H}_{t}^{(i)};f)$,

$=\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\bigg{\\{}\left(\big{\\{}\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)})]\right)\\\
-\left(\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})-\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})]\right)\bigg{\\}}^{2}\bigg{]}$

Let
$X=\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})-\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})$.
Since
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}(X-\mathbb{E}_{\pi_{2:t}^{*}}[X])^{2}\big{]}=\mathbb{E}_{\pi_{2:t}^{*}}\big{[}X^{2}\big{]}-\mathbb{E}_{\pi_{2:t}^{*}}\big{[}X\big{]}^{2}$,

$=\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\left(\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})-\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})\right)^{2}\bigg{]}\\\
-\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{t}^{(i)})-\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\right]^{2}$
$\leq\mathbb{E}_{\pi_{2:t}^{*}}\bigg{[}\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-2}\left\\{f(\mathcal{H}_{t}^{(i)})-g(\mathcal{H}_{t}^{(i)})\right\\}^{2}\bigg{]}$

By Condition 2,
$\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-2}\leq\pi_{\min}^{2(t-1)}$ a.s., so

$\leq\pi_{\min}^{2(t-1)}\mathbb{E}_{\pi_{2:t}^{*}}\left[\left\\{f(\mathcal{H}_{t}^{(i)})-g(\mathcal{H}_{t}^{(i)})\right\\}^{2}\right]$

The above implies that
$\rho\big{(}\hat{f}^{(n)},f_{0}\big{)}\overset{P}{\to}0$ because by assumption
of the Lemma, we have that
$\nu\big{(}\hat{f}^{(n)},f_{0}\big{)}\overset{P}{\to}0$ where
$\nu(f,g)\triangleq\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{|}f\big{(}\mathcal{H}_{t}^{(i)}\big{)}-g\big{(}\mathcal{H}_{t}^{(i)}\big{)}\big{|}^{2}\right]^{1/2}$.
$~{}~{}~{}\blacksquare$

##  Appendix E Maximal Inequalities for Adaptively Sampled Data

Overview and Notation for Appendix E Results. In this Appendix, we will use
the following notation:

$\pi_{2:t}^{*,(i)}\triangleq\prod_{t^{\prime}=2}^{t}\pi_{t^{\prime}}^{*}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\textnormal{~{}~{}and~{}~{}}\hat{\pi}_{2:t}^{(i)}\triangleq\prod_{t^{\prime}=2}^{t}\hat{\pi}_{t^{\prime}}^{(n)}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)}).$

Consider a function class $\mathcal{F}$ whose complexity is sufficiently
controlled. In this section, our goal is to show a maximal inequality to bound
the following:

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

Above $\mathbb{E}^{*}$ refers to outer expectations as defined in Section 18.2
Van der Vaart [2000]. A bound for the above term in display (E.1) is used in
Theorem D.5 (Functional Asymptotic Normality under Finite Bracketing Integral
for Adaptively Sampled Data). This maximal inequality will be a function of
the bracketing integral $\mathcal{F}$ bracketing integral,
$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{p}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon$,
which we assume is finite.

Note that since $\\{\mathcal{H}_{T}^{(i)}\\}_{i=1}^{n}$ are not independent in
our setting, we cannot use classical maximal inequalities for i.i.d. data to
bound the term in display (E.1). See Section 19.6 of Van der Vaart [2000] for
information on maximal inequalities for i.i.d. data. Our results build on the
ideas used in these results for i.i.d. data.

Summary of Results in this Section

  * •

Weighted Martingale Bernstein Inequality (Lemma E.2) proves a Bernstein
inequality for our non-independent, adaptively sampled data type and is the
most novel step in this section. The proof leverages the conditional
independence of the action selection at each time-step and the fact that the
underlying potential outcomes are i.i.d. The proof repeatedly uses a key
helper Lemma E.1 (Moving Products out of Expectations using Weights).

  * •

Maximal Inequality for Finite Class of Functions (Lemma E.3) proves a maximal
inequality to bound the term in display (E.1) in the case that
$|\mathcal{F}|<\infty$. The proof closely follows that of Lemma 19.33 Van der
Vaart [2000], but replaces the use of a Bernstein inequality for i.i.d. data
with Lemma E.2 (Weighted Martingale Bernstein Inequality).

  * •

Maximal Inequality as a Function of the Bracketing Integral (Lemma E.4) proves
a maximal inequality to bound the term in display (E.1) as a function of the
bracketing integral for $\mathcal{F}$. The proof closely follows that of Lemma
19.34 Van der Vaart [2000], but replaces the use of a maximal inequality for
empirical processes for a finite class of functions on i.i.d. data with Lemma
E.3 (Maximal Inequality for Finite Class of Functions).

###  E.1 Moving Products out of Expectations using Weights (Lemma E.1)

######  Lemma E.1 (Moving Products out of Expectations using Weights).

For any $t\in[2\colon T]$, let $f$ be any real-valued, measurable function of
$\mathcal{H}_{t}^{(i)}$ such that
$\mathbb{E}_{\pi_{2:t}^{*}}\big{[}\big{|}f(\mathcal{H}_{t}^{(i)})\big{|}\big{]}<\infty$.
Let $c$ be fixed constants. The following equality holds for any $n\geq 1$:

$\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})+c\right)\bigg{]}=\prod_{i=1}^{n}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})+c\right].$
(E.2)

######  Remark 10 (Display (E.2) Comment).

Note that regarding the expectation terms on the right hand side above, for
any stochastic policies $\pi_{2:t}(\beta_{1:t-1})$,

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

Proof of Lemma E.1 (Conditional Independence using Weights). For notational
convenience we consider the $t$ set to $T$ case; the argument holds by the
same argument for any $t\in[2\colon T]$.

Let $t\in[2:T]$ and let $g$ be a real-valued, measurable function of
$\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}$. A key result which we will take as
given for now (we prove it at the end of this proof), is that

$\mathbb{E}\bigg{[}\prod_{i=1}^{n}\bigg{(}\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}+c\bigg{)}\bigg{]}\\\
=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\bigg{(}\big{\\{}\hat{\pi}_{2:t-1}^{(i)}\big{\\}}^{-1}\mathbb{E}_{\pi_{t}^{*}}\bigg{[}\big{\\{}\pi_{t}^{*,(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}\bigg{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\bigg{]}+c\bigg{)}\bigg{]}.$
(E.3)

We now show that the desired result holds by repeatedly applying display
(E.3). Applying display (E.3) for $t$ set to $T$ and for $g$ set to $f$, we
have that

$\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})+c\right)\bigg{]}$
$=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:T-1}^{(i)}\big{\\}}^{-1}\mathbb{E}_{\pi_{T}^{*}}\left[\big{\\{}\pi_{T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\big{|}\mathcal{H}_{T-1}^{(i)},S_{T}^{(i)}\right]+c\right)\bigg{]}$

Now, note that
$\mathbb{E}_{\pi_{T}^{*}}\left[\big{\\{}\pi_{T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\big{|}\mathcal{H}_{T-1}^{(i)},S_{T}^{(i)}\right]$
is a function of $\mathcal{H}_{T-1}^{(i)},S_{T}^{(i)}$; let this be function
be $g$ when we apply display (E.3) again for $t$ set to $T-1$.

$=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\bigg{(}\big{\\{}\hat{\pi}_{2:T-2}^{(i)}\big{\\}}^{-1}\mathbb{E}_{\pi_{T-1}^{*}}\left[\big{\\{}\pi_{T-1}^{*,(i)}\big{\\}}^{-1}\mathbb{E}_{\pi_{T}^{*}}\left[\big{\\{}\pi_{T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\big{|}\mathcal{H}_{T-1}^{(i)},S_{T}^{(i)}\right]\bigg{|}\mathcal{H}_{T-2}^{(i)},S_{T-1}^{(i)}\right]+c\bigg{)}\bigg{]}$

Since $\big{\\{}\pi_{T-1}^{*,(i)}\big{\\}}^{-1}$ is a constant given
$\mathcal{H}_{T-1}^{(i)}$,

$=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\bigg{(}\big{\\{}\hat{\pi}_{2:T-2}^{(i)}\big{\\}}^{-1}\mathbb{E}_{\pi_{T-1}^{*}}\left[\mathbb{E}_{\pi_{T}^{*}}\left[\big{\\{}\pi_{T-1:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\big{|}\mathcal{H}_{T-1}^{(i)},S_{T}^{(i)}\right]\bigg{|}\mathcal{H}_{T-2}^{(i)},S_{T-1}^{(i)}\right]+c\bigg{)}\bigg{]}$

By law of iterated expectations,

$=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:T-2}^{(i)}\big{\\}}^{-1}\mathbb{E}_{\pi_{T-1:T}^{*}}\left[\big{\\{}\pi_{T-1:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\big{|}\mathcal{H}_{T-2}^{(i)},S_{T-1}^{(i)}\right]+c\right)\bigg{]}.$

By repeatedly applying display (E.3) and the above argument for $t$ set to
$T-2,T-3,...,2$ we have that

$=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:T-3}^{(i)}\big{\\}}^{-1}\mathbb{E}_{\pi_{T-2:T}^{*}}\left[\big{\\{}\pi_{T-2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\big{|}\mathcal{H}_{3}^{(i)},S_{T-2}^{(i)}\right]+c\right)\bigg{]}$
$=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:T-4}^{(i)}\big{\\}}^{-1}\mathbb{E}_{\pi_{T-3:T}^{*}}\left[\big{\\{}\pi_{T-3:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\big{|}\mathcal{H}_{4}^{(i)},S_{T-3}^{(i)}\right]+c\right)\bigg{]}$
$=...=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\big{|}\mathcal{H}_{1}^{(i)},S_{1}^{(i)}\right]+c\right)\bigg{]}.$

Finally, recall that
$\big{\\{}\mathcal{H}_{1}^{(i)},S_{2}^{(i)}\big{\\}}_{i=1}^{n}=\big{\\{}S_{1}^{(i)},A_{1}^{(i)},Y_{1}^{(i)},S_{2}^{(i)}\big{\\}}_{i=1}^{n}$
are independent over $i\in[1\colon n]$. Thus,

$\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left\\{\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\big{|}\mathcal{H}_{1}^{(i)},S_{1}^{(i)}\right]+c\right\\}\bigg{]}\\\
=\prod_{i=1}^{n}\mathbb{E}\left[\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\big{|}\mathcal{H}_{1}^{(i)},S_{1}^{(i)}\right]+c\right]$

By law of iterated expectations,

$=\prod_{i=1}^{n}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})+c\right].$

Thus we have shown that the desired result holds and all that is left is to
show that display (E.3) holds.

Proof of display (E.3). The proof of display (E.3) leverages (i) the Radon-
Nikodym weights and (ii) conditional independence properties. Pick any
$t\in[2:T]$ and let $g$ be a real-valued, measurable function of
$\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}$. By law of iterated expectations,

$\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}+c\right)\bigg{]}$
$=\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}+c\right)\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\bigg{]}\bigg{]}$

Note that the conditional expectation
$\mathbb{E}\left[\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}+c\right)\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$
is only integrating over
$\big{\\{}A_{t}^{(i)},Y_{t}^{(i)},S_{t+1}^{(i)}\big{\\}}_{i=1}^{n}$ (the
policy parameters $\hat{\beta}_{1:t-1}^{(n)}$ used in
$\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}$ are known given
$\mathcal{H}_{t-1}^{(1:n)}$). Additionally, note that conditional on
$\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}$,
$\big{\\{}A_{t}^{(i)},Y_{t}^{(i)},S_{t+1}^{(i)}\big{\\}}$ are independent over
$i\in[1\colon n]$. Thus,

$=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]+c\right)\bigg{]}$

Since
$\big{\\{}\hat{\pi}_{2:t-1}^{(i)}\big{\\}}^{-1}=\big{(}\prod_{t^{\prime}=2}^{t-1}\hat{\pi}_{t^{\prime}}^{(n)}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\big{)}^{-1}$
is a constant given $\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}$,

$=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t-1}^{(i)}\big{\\}}^{-1}\mathbb{E}\left[\big{\\{}\hat{\pi}_{t}^{(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}\bigg{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]+c\right)\bigg{]}$

Now now show that the above equals the following:

$=\mathbb{E}\bigg{[}\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t-1}^{(i)}\big{\\}}^{-1}\mathbb{E}_{\pi_{t}^{*}}\left[\big{\\{}\pi_{t}^{*,(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}\big{|}\mathcal{H}_{T-1}^{(i)},S_{t}^{(i)}\right]+c\right)\bigg{]}.$
(E.4)

Showing the above will be sufficient for display (E.3).

Note that since
$1=\pi_{t}^{*}(A_{t}^{(i)},S_{t}^{(i)})^{-1}\pi_{t}^{*}(A_{t}^{(i)},S_{t}^{(i)})=\big{\\{}\pi_{t}^{*,(i)}\big{\\}}^{-1}\pi_{t}^{*}(A_{t}^{(i)},S_{t}^{(i)})$,

$\mathbb{E}\left[\big{\\{}\hat{\pi}_{t}^{(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{T}^{(i)},S_{t+1}^{(i)}\big{)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
=\mathbb{E}\left[\big{\\{}\hat{\pi}_{t}^{(i)}\big{\\}}^{-1}\big{\\{}\pi_{t}^{*,(i)}\big{\\}}^{-1}\pi_{t}^{*}(A_{t}^{(i)},S_{t}^{(i)})g\big{(}\mathcal{H}_{T}^{(i)},S_{t+1}^{(i)}\big{)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]\\\
=\mathbb{E}_{\pi_{t}^{*}}\left[\big{\\{}\pi_{t}^{*,(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right].$

The last equality above holds because
$\big{\\{}\hat{\pi}_{t}^{(i)}\big{\\}}^{-1}\pi_{t}^{*}(A_{t}^{(i)},S_{t}^{(i)})=W_{t}^{(i)}(\beta_{t-1}^{*},\hat{\beta}_{t-1}^{(n)})$.

Also, note that the expectation
$\mathbb{E}_{\pi_{t}^{*}}\left[\big{\\{}\pi_{t}^{*,(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]$
integrates over $\big{\\{}A_{t}^{(i)},Y_{t}^{(i)},S_{t+1}^{(i)}\big{\\}}$.
Since actions are selected using $\pi_{t}^{*}$ rather than
$\hat{\pi}_{t}^{(n)}$ in the expectation, the distribution of
$\big{\\{}A_{t}^{(i)},Y_{t}^{(i)},S_{t+1}^{(i)}\big{\\}}$ depends only on
$\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}$ through
$\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}$. This means that

$\mathbb{E}_{\pi_{t}^{*}}\left[\big{\\{}\pi_{t}^{*,(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}\big{|}\mathcal{H}_{t-1}^{(1:n)},S_{t}^{(1:n)}\right]=\mathbb{E}_{\pi_{t}^{*}}\left[\big{\\{}\pi_{t}^{*,(i)}\big{\\}}^{-1}g\big{(}\mathcal{H}_{t}^{(i)},S_{t+1}^{(i)}\big{)}\big{|}\mathcal{H}_{t-1}^{(i)},S_{t}^{(i)}\right].$

Thus we have shown display (E.4) holds. $\blacksquare$

###  E.2 Weighted Martingale Bernstein Inequality (Lemma E.2)

######  Lemma E.2 (Weighted Martingale Bernstein Inequality).

We assume Condition 2 (Minimum Exploration) holds. Let $f$ be a real-valued,
measurable function of $\mathcal{H}_{t}^{(i)}$. Then, for any $x>0$ and for
all $n\geq 1$,

$\mathbb{P}\bigg{(}\bigg{|}\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\right]\bigg{|}\geq
x\bigg{)}\\\ \leq
2\exp\bigg{(}-\frac{\pi_{\min}^{t-1}}{4}\frac{x^{2}}{\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})^{2}\right]+x\|f\|_{\infty}/\sqrt{n}}\bigg{)}.$
(E.5)

Above $\|f\|_{\infty}\triangleq\sup_{h}|f(h)|$.

Proof of Lemma E.2 (Weighted Martingale Bernstein Inequality). We follow an
argument similar to Lemma 19.32 in Van der Vaart [2000]. For notational
convenience we consider the $t$ set to $T$ case; the argument holds by the
same argument for any $t\in[2\colon T]$.

The leading 2 in display (E.5) is due to separate bounds for the upper and
lower tail bounds. It is sufficient to show the upper tail bound, because the
lower tail bound holds by the upper tail bound applied to $-f$.

Note if $\|f\|_{\infty}=0$, then
$\mathbb{P}\left(\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\right]\right)\geq
x\right)=0$, so in this case display (E.5) easily holds. Thus, for the
remainder of the proof we assume that $\|f\|_{\infty}>0$.

Let $x>0$.

$\mathbb{P}\bigg{(}\frac{1}{\
\sqrt{n}}\sum_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)\geq
x\bigg{)}$ (E.6)

Using a Chernoff bound, for any $\lambda>0$,

$\leq e^{-\lambda
x}\mathbb{E}\bigg{[}\exp\bigg{\\{}\frac{\lambda}{\sqrt{n}}\sum_{i=1}^{n}\bigg{(}\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\bigg{)}\bigg{\\}}\bigg{]}$

Using properties of exponents, we can change the summation in exponent into a
product,

$=e^{-\lambda
x}\mathbb{E}\bigg{[}\prod_{i=1}^{n}\exp\left\\{\frac{\lambda}{\sqrt{n}}\bigg{(}\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\bigg{)}\right\\}\bigg{]}$

We now apply Maclaurin series for exponential function, i.e., that
$e^{z}=\sum_{k=0}^{\infty}\frac{z^{k}}{k!}$.

$=e^{-\lambda
x}\mathbb{E}\bigg{[}\prod_{i=1}^{n}\sum_{k=0}^{\infty}\frac{1}{k!}\left(\frac{\lambda}{\sqrt{n}}\right)^{k}\bigg{(}\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\bigg{)}^{k}\bigg{]}$

By simplifying the first two terms in the inner summation,

$=e^{-\lambda
x}\mathbb{E}\bigg{[}\prod_{i=1}^{n}\bigg{\\{}1+\frac{\lambda}{\sqrt{n}}\bigg{(}\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\bigg{)}\\\
+\sum_{k=2}^{\infty}\frac{1}{k!}\left(\frac{\lambda}{\sqrt{n}}\right)^{k}\bigg{(}\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\bigg{)}^{k}\bigg{\\}}\bigg{]}$
(E.7)

Now note the following observations:

  * •

Let $\epsilon>0$. By Condition 2 (Minimum Exploration),

$\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}=\bigg{[}\prod_{t^{\prime}=2}^{t}\hat{\pi}_{t^{\prime}}^{(n)}(A_{t^{\prime}}^{(i)},S_{t^{\prime}}^{(i)})\bigg{]}^{-1}\leq\pi_{\min}^{-(t-1)}~{}~{}\textnormal{a.s.},$
(E.8)

and

$\left|\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right|\\\
\leq\left|\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right|+\left|\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right|\leq
2\pi_{\min}^{-(T-1)}\|f\|_{\infty}.$ (E.9)

  * •

We can upper bound the following:

$\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{2}$
$=\big{(}\hat{\pi}_{2:T}^{(i)}\big{)}^{-2}f(\mathcal{H}_{T}^{(i)})^{2}-2\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]+\left(\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{2}$

Note that
$\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]=\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]$.

$=\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}-2f(\mathcal{H}_{T}^{(i)})\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)\\\
+\left(\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{2}$

Since $\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}\leq\pi_{\min}^{-(T-1)}$
a.s. by display (E.8),

$\leq\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}\bigg{(}\underbrace{\pi_{\min}^{-(T-1)}f(\mathcal{H}_{T}^{(i)})^{2}-2f(\mathcal{H}_{T}^{(i)})\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]}_{\triangleq
g(\mathcal{H}_{T}^{(i)})}\bigg{)}\\\
+\left(\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{2}$

For
$g(\mathcal{H}_{T}^{(i)})\triangleq\pi_{\min}^{-(T-1)}f(\mathcal{H}_{T}^{(i)})^{2}-2f(\mathcal{H}_{T}^{(i)})\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]$,

$=\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}g(\mathcal{H}_{T}^{(i)})+\left(\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{2}.$

Thus, in summary we have that

$\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{2}\\\
\leq\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}g(\mathcal{H}_{T}^{(i)})+\left(\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{2}.$
(E.10)

  * •

By display (E.9) and (E.10), we have that for any $k\geq 2$

$\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{k}\\\
\leq\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{2}\left|\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right|^{k-2}\\\
\leq\bigg{(}\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}g(\mathcal{H}_{T}^{(i)})+\left(\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)^{2}\bigg{)}\big{\\{}2\pi_{\min}^{-(T-1)}\|f\|_{\infty}\big{\\}}^{k-2}$
(E.11)

Note that in display (E.7), each of the terms in the product over $n$ terms is
non-negative because the $i^{\textnormal{th}}$ term in the product equals
$\exp\left\\{\frac{\lambda}{\sqrt{n}}\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\right)\right\\}$
and $e^{x}\geq 0$ for all $x$. Thus, by display (E.11), we can upper bound
display (E.7) as follows:

$\leq e^{-\lambda
x}\mathbb{E}\bigg{[}\prod_{i=1}^{n}\bigg{\\{}1+\frac{\lambda}{\sqrt{n}}\bigg{(}\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\bigg{)}\\\
+\sum_{k=2}^{\infty}\frac{1}{k!}\left(\frac{\lambda}{\sqrt{n}}\right)^{k}\bigg{(}\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}g(\mathcal{H}_{T}^{(i)})+\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]^{2}\bigg{)}\left(2\pi_{\min}^{-(T-1)}\|f\|_{\infty}\right)^{k-2}\bigg{\\}}\bigg{]}$
(E.12)

Note that everything in the expectation above in display (E.12) is bounded
a.s.; we will show that this is true for the infinite summation over $k$. Let
$y=\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}g(\mathcal{H}_{T}^{(i)})+\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]^{2}$
and $z=2\pi_{\min}^{-(T-1)}\|f\|_{\infty}$. Note that both $y$ and $z$ are
bounded a.s. Thus, since $\|f\|_{\infty}>0$ by assumption (we discussed the
$\|f\|_{\infty}=0$ case at the beginning of this proof), we have that $z>0$,
so
$\sum_{k=2}^{\infty}\frac{1}{k!}\big{(}\frac{\lambda}{\sqrt{n}}\big{)}^{k}yz^{k-2}=yz^{-2}\sum_{k=2}^{\infty}\frac{1}{k!}\big{(}\frac{\lambda}{\sqrt{n}}\big{)}^{k}z^{k}=yz^{-2}\left(e^{z\lambda/\sqrt{n}}-\sum_{k=0}^{1}\frac{1}{k!}\big{(}\frac{\lambda}{\sqrt{n}}\big{)}^{k}z^{k}\right)$
is also bounded a.s.

Moreover, display (E.12) can be written as $e^{-\lambda
x}\mathbb{E}\left[\prod_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}h(\mathcal{H}_{T}^{(i)})+c\right)\right]$,
for some function $h$ and some finite constant $c$. (Note that
$\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]=\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]$)
Thus, we can apply Lemma E.1 (Moving Products out of Expectations using
Weights) to get that display (E.12) is equal to

$=e^{-\lambda
x}\prod_{i=1}^{n}\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}1+\frac{\lambda}{\sqrt{n}}\bigg{(}\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]\bigg{)}\\\
+\sum_{k=2}^{\infty}\frac{1}{k!}\left(\frac{\lambda}{\sqrt{n}}\right)^{k}\bigg{(}\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{T}^{(i)})+\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]^{2}\bigg{)}\left(2\pi_{\min}^{-(T-1)}\|f\|_{\infty}\right)^{k-2}\bigg{]}.$

Since
$\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]=\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]$,
we can cancel terms in the first line above.

$=e^{-\lambda
x}\prod_{i=1}^{n}\bigg{\\{}1+\mathbb{E}_{\pi_{2:T}^{*}}\bigg{[}\sum_{k=2}^{\infty}\frac{1}{k!}\left(\frac{\lambda}{\sqrt{n}}\right)^{k}\bigg{(}\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{T}^{(i)})+\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]^{2}\bigg{)}\\\
\left(2\pi_{\min}^{-(T-1)}\|f\|_{\infty}\right)^{k-2}\bigg{]}\bigg{\\}}$

Since everything in the expectations above are bounded a.s. (discussed below
display (E.12)), we can exchange the expectation with the infinite summation
over $k$.

$=e^{-\lambda
x}\prod_{i=1}^{n}\bigg{\\{}1+\sum_{k=2}^{\infty}\frac{1}{k!}\left(\frac{\lambda}{\sqrt{n}}\right)^{k}\bigg{(}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{T}^{(i)})\right]+\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]^{2}\bigg{)}\\\
\left(2\pi_{\min}^{-(T-1)}\|f\|_{\infty}\right)^{k-2}\bigg{\\}}.$ (E.13)

Note the following:

  * •

Recall that
$g(\mathcal{H}_{T}^{(i)})\triangleq\pi_{\min}^{-(T-1)}f(\mathcal{H}_{T}^{(i)})^{2}-2f(\mathcal{H}_{T}^{(i)})\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]$.
So,

$\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}g(\mathcal{H}_{T}^{(i)})\right]+\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]^{2}$
$=\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]-2\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]^{2}+\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]^{2}$
$=\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]-\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\right]^{2}$
$\leq\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]$

Thus display (E.13) can be upper bounded by the following:

$e^{-\lambda
x}\prod_{i=1}^{n}\bigg{\\{}1+\sum_{k=2}^{\infty}\frac{1}{k!}\left(\frac{\lambda}{\sqrt{n}}\right)^{k}\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]\left(2\pi_{\min}^{-(T-1)}\|f\|_{\infty}\right)^{k-2}\bigg{\\}}$

By i.i.d. potential outcomes,

$=e^{-\lambda
x}\bigg{\\{}1+\sum_{k=2}^{\infty}\frac{1}{k!}\left(\frac{\lambda}{\sqrt{n}}\right)^{k}\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]\left(2\pi_{\min}^{-(T-1)}\|f\|_{\infty}\right)^{k-2}\bigg{\\}}^{n}$

By rearranging terms,

$=e^{-\lambda
x}\bigg{\\{}1+\frac{1}{n}\sum_{k=2}^{\infty}\frac{1}{k!}\frac{1}{2}\lambda^{k}\underbrace{2\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]}_{\triangleq\lambda_{1}^{-1}}\bigg{(}\underbrace{2\pi_{\min}^{-(T-1)}\|f\|_{\infty}/\sqrt{n}}_{\triangleq\lambda_{2}^{-1}}\bigg{)}^{k-2}\bigg{\\}}^{n}$
$=e^{-\lambda
x}\bigg{\\{}1+\frac{1}{n}\sum_{k=2}^{\infty}\frac{1}{k!}\frac{1}{2}\lambda^{k}\left(\lambda_{1}^{-1}\lambda_{2}^{-(k-2)}\right)\bigg{\\}}^{n}$
(E.14)

Note that since $\lambda_{1}^{-1},\lambda_{2}^{-1}\geq 0$,

$\lambda\triangleq
x\left(\lambda_{1}^{-1}+x\lambda_{2}^{-1}\right)^{-1}\leq\min\left\\{x\left(\lambda_{1}^{-1}+0\right)^{-1},x\left(0+x\lambda_{2}^{-1}\right)^{-1}\right\\}=\min\left(x\lambda_{1},\lambda_{2}\right).$

Thus we have that
$\lambda^{k}\leq\lambda\min(x\lambda_{1},\lambda_{2})^{k-1}\leq\lambda
x\lambda_{1}\lambda_{2}^{k-2}$. So we can upper bound display (E.14) as
follows:

$\leq e^{-\lambda
x}\bigg{\\{}1+\frac{1}{n}\sum_{k=2}^{\infty}\frac{1}{k!}\frac{1}{2}\left(\lambda
x\lambda_{1}\lambda_{2}^{k-2}\right)\left(\lambda_{1}^{-1}\lambda_{2}^{-(k-2)}\right)\bigg{\\}}^{n}$
$=e^{-\lambda
x}\bigg{\\{}1+\frac{1}{n}\underbrace{\sum_{k=2}^{\infty}\frac{1}{k!}}_{\leq
1}\frac{1}{2}\lambda x\bigg{\\}}^{n}$

By the Maclaurin series for exponential function,
$e^{z}=\sum_{k=0}^{\infty}\frac{z^{k}}{k!}$, we have
$\sum_{k=2}^{\infty}\frac{1}{k!}=e-\frac{1}{0!}-\frac{1}{1!}=e-2\leq 1$.

$\leq e^{-\lambda x}\bigg{\\{}1+\frac{1}{n}\frac{1}{2}x\lambda\bigg{\\}}^{n}$

Again by the Maclaurin series for exponential function,
$e^{z}=\sum_{k=0}^{\infty}\frac{z^{k}}{k!}$, so for $z>0$ we have that
$1+z\leq e^{z}$. This means that $(1+z)^{n}\leq e^{zn}$.

$\leq e^{-\lambda
x}\exp\bigg{(}\frac{1}{2}x\lambda\bigg{)}=\exp\bigg{(}-\frac{1}{2}x\lambda\bigg{)}$

Recall that $\lambda\triangleq
x\left(\lambda_{1}^{-1}+x\lambda_{2}^{-1}\right)^{-1}$, so,

$=\exp\bigg{(}-\frac{1}{2}xx\left(\lambda_{1}^{-1}+x\lambda_{2}^{-1}\right)^{-1}\bigg{)}$

Recall that
$\lambda_{1}^{-1}=2\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]$
and $\lambda_{2}^{-1}=2\pi_{\min}^{-(T-1)}\|f\|_{\infty}/\sqrt{n}$. So,

$=\exp\bigg{(}-\frac{\pi_{\min}^{T-1}}{4}\frac{x^{2}}{\mathbb{E}_{\pi_{2:T}^{*}}\big{[}\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\big{]}+x\|f\|_{\infty}/\sqrt{n}}\bigg{)}.~{}~{}\blacksquare$

###  E.3 Maximal Inequality for Finite Class of Functions (Lemma E.3)

######  Lemma E.3 (Maximal Inequality for Finite Class of Functions).

Let $\mathcal{F}$ be a finite class of bounded, real-valued, measurable
functions of $\mathcal{H}_{t}^{(i)}$ with size $|\mathcal{F}|\geq 2$. For
$f\in\mathcal{F}$ we define

$\mathbb{G}_{n}(f)\triangleq\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\right]\right).$

Under Condition 2 (Minimum Exploration) for all sufficiently large $n$,

$\mathbb{E}\bigg{[}\max_{f\in\mathcal{F}}\big{|}\mathbb{G}_{n}(f)\big{|}\bigg{]}\leq
C\bigg{\\{}\pi_{\min}^{-(T-1)}\max_{f\in\mathcal{F}}\frac{\|f\|_{\infty}}{\sqrt{n}}\log(|\mathcal{F}|)\\\
+\sqrt{\pi_{\min}^{-(t-1)}}\max_{f\in\mathcal{F}}\sqrt{\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]}\sqrt{\log(|\mathcal{F}|)}\bigg{\\}},$
(E.15)

for some universal positive constant $C$ (specified in the proof).

Proof of Lemma E.3 (Maximal Inequality for Finite Class of Functions). Our
proof follows a very similar argument to Lemma 19.33 in Van der Vaart [2000].
Specifically, our proof only deviates because we use our Lemma E.2 (Weighted
Martingale Bernstein Inequality) to prove displays (E.19) and (E.21) below.

For notational convenience we consider the $t$ set to $T$ case; the argument
holds by the same argument for any $t\in[2\colon T]$.

Special cases.

  * •

Note that if $f\in\mathcal{F}$ such that $\|f\|_{\infty}=0$, then
$\mathbb{G}_{n}(f)=0$. These zero functions do not contribute to increasing
the upper bound for
$\mathbb{E}\big{[}\max_{f\in\mathcal{F}}\big{|}\mathbb{G}_{n}(f)\big{|}\big{]}$.
Thus, we assume that $\|f\|_{\infty}>0$ for all $f\in\mathcal{F}$ for the
remainder of this proof, as this is the most difficult case.

  * •

Note that $f\in\mathcal{F}$ such that
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]=0$,
then $f(\mathcal{H}_{T}^{(i)})$ is a constant function and
$\mathbb{G}_{n}(f)=0$. These constant functions do not contribute to
increasing the upper bound for
$\mathbb{E}\big{[}\max_{f\in\mathcal{F}}\big{|}\mathbb{G}_{n}(f)\big{|}\big{]}$.
Thus, we assume that
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]>0$
for all $f\in\mathcal{F}$ for the remainder of this proof, as this is the most
difficult case.

Main argument. Let $u,v$ be non-negative, real-valued functions of
$f\in\mathcal{F}$ such that

  * •

$u(f)=24\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]$

  * •

$v(f)=24\pi_{\min}^{-(T-1)}\|f\|_{\infty}/\sqrt{n}$

Note that

$\mathbb{E}\left[\max_{f\in\mathcal{F}}|\mathbb{G}_{n}(f)|\right]=\mathbb{E}\left[\max_{f\in\mathcal{F}}\bigg{\\{}|\mathbb{G}_{n}(f)|\mathbb{I}_{|\mathbb{G}_{n}(f)|>u(f)/v(f)}+|\mathbb{G}_{n}(f)|\mathbb{I}_{|\mathbb{G}_{n}(f)|\leq
u(f)/v(f)}\bigg{\\}}\right]$
$\leq\mathbb{E}\left[\max_{f\in\mathcal{F}}|\mathbb{G}_{n}(f)|\mathbb{I}_{|\mathbb{G}_{n}(f)|>u(f)/v(f)}\right]+\mathbb{E}\left[\max_{f\in\mathcal{F}}|\mathbb{G}_{n}(f)|\mathbb{I}_{|\mathbb{G}_{n}(f)|\leq
u(f)/v(f)}\right]$

Let
$\underline{\mathbb{G}_{n}}(f)\triangleq|\mathbb{G}_{n}(f)|\mathbb{I}_{|\mathbb{G}_{n}(f)|>u(f)/v(f)}$
and
$\overline{\mathbb{G}_{n}}(f)\triangleq|\mathbb{G}_{n}(f)|\mathbb{I}_{|\mathbb{G}_{n}(f)|\leq
u(f)/v(f)}$.

$=\mathbb{E}\left[\max_{f\in\mathcal{F}}\underline{\mathbb{G}_{n}}(f)\right]+\mathbb{E}\left[\max_{f\in\mathcal{F}}\overline{\mathbb{G}_{n}}(f)\right]$
$\leq\mathbb{E}\left[\max_{f\in\mathcal{F}}\underline{\mathbb{G}_{n}}(f)/v(f)\right]\left(\max_{f\in\mathcal{F}}v(f)\right)+\mathbb{E}\left[\max_{f\in\mathcal{F}}\overline{\mathbb{G}_{n}}(f)/\sqrt{u(f)}\right]\left(\max_{f\in\mathcal{F}}\sqrt{u(f)}\right)$
(E.16)

The main results show in this proof are the following:

$\mathbb{E}\left[\max_{f\in\mathcal{F}}\underline{\mathbb{G}_{n}}(f)/v(f)\right]\leq\log\left(1+|\mathcal{F}|\right)$
(E.17)
$\mathbb{E}\left[\max_{f\in\mathcal{F}}\overline{\mathbb{G}_{n}}(f)/\sqrt{u(f)}\right]\leq\sqrt{\log\left(1+|\mathcal{F}|\right)}$
(E.18)

For now we take displays (E.17) and (E.18) as given and show why the Lemma
holds. Using these two results, we have that display (E.16) can be upper
bounded by the following:

$\leq\log\left(1+|\mathcal{F}|\right)\bigg{(}\max_{f\in\mathcal{F}}\underbrace{24\pi_{\min}^{-(T-1)}\|f\|_{\infty}/\sqrt{n}}_{v(f)}\bigg{)}\\\
+\sqrt{\log\left(1+|\mathcal{F}|\right)}\bigg{(}\max_{f\in\mathcal{F}}\underbrace{\sqrt{24\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]}}_{\sqrt{u(f)}}\bigg{)}$
$=24\pi_{\min}^{-(T-1)}\left(\max_{f\in\mathcal{F}}\frac{\|f\|_{\infty}}{\sqrt{n}}\right)\log\left(1+|\mathcal{F}|\right)\\\
+\sqrt{24\pi_{\min}^{-(T-1)}}\left(\max_{f\in\mathcal{F}}\sqrt{\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]}\right)\sqrt{\log\left(1+|\mathcal{F}|\right)}$

Since $c_{\log}\triangleq\sup_{x\geq 2}\frac{\log(1+x)}{\log(x)}$ is bounded,
$\frac{\log(1+|\mathcal{F}|)}{\log(|\mathcal{F}|)}\leq c_{\log}$ so, $1\leq
c_{\log}\frac{\log(|\mathcal{F}|)}{\log(1+|\mathcal{F}|)}$.

$\leq
c_{\log}24\pi_{\min}^{-(T-1)}\left(\max_{f\in\mathcal{F}}\frac{\|f\|_{\infty}}{\sqrt{n}}\right)\log\left(|\mathcal{F}|\right)\\\
+\sqrt{c_{\log}24\pi_{\min}^{-(T-1)}}\left(\max_{f\in\mathcal{F}}\sqrt{\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]}\sqrt{\log\left(|\mathcal{F}|\right)}\right)$
$\leq
24\max\big{(}c_{\log},c_{\log}^{1/2}\big{)}\bigg{\\{}\pi_{\min}^{-(T-1)}\left(\max_{f\in\mathcal{F}}\frac{\|f\|_{\infty}}{\sqrt{n}}\right)\log\left(|\mathcal{F}|\right)\\\
+\sqrt{\pi_{\min}^{-(T-1)}}\left(\max_{f\in\mathcal{F}}\sqrt{\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]}\right)\sqrt{\log\left(|\mathcal{F}|\right)}\bigg{\\}}.$

The above implies that the desired result, display (E.15), holds. All that
remains is to prove that displays (E.17) and (E.18) hold.

Proving display (E.17) holds. Let $x>0$. We now state some results and discuss
why they hold below. For all $n\geq 1$ we have that for any $f\in\mathcal{F}$,

$\mathbb{P}\left(\left|\underline{\mathbb{G}}_{n}(f)\right|\geq
x\right)\underbrace{\leq}_{(a)}\mathbb{P}\left(\left|\underline{\mathbb{G}}_{n}(f)\right|\geq\max\big{\\{}x,u(f)/v(f)\big{\\}}\right)\\\
\underbrace{\leq}_{(b)}2\exp\bigg{(}-6\frac{\max\big{\\{}x,u(f)/v(f)\big{\\}}^{2}}{u(f)+\max\big{\\{}x,u(f)/v(f)\big{\\}}v(f)}\bigg{)}\underbrace{\leq}_{(c)}2\exp\left(-3\frac{x}{v(f)}\right).$
(E.19)

  * •

Inequality (a) holds because recall that
$\underline{\mathbb{G}_{n}}(f)\triangleq|\mathbb{G}_{n}(f)|\mathbb{I}_{|\mathbb{G}_{n}(f)|>u(f)/v(f)}$.

  * •

Inequality (b) holds by Lemma E.2 (Weighted Martingale Bernstein Inequality)
since Condition 2 holds. Recall that
$u(f)=24\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]$
and $v(f)=24\pi_{\min}^{-(T-1)}\|f\|_{\infty}/\sqrt{n}$.

  * •

Inequality (c) holds because

$6\frac{\max\big{\\{}x,u(f)/v(f)\big{\\}}^{2}}{u(f)+\max\big{\\{}x,u(f)/v(f)\big{\\}}v(f)}=6\frac{\max\big{\\{}x,u(f)/v(f)\big{\\}}}{u(f)/\max\big{\\{}x,u(f)/v(f)\big{\\}}+v(f)}\\\
\geq 6\frac{x}{u(f)/\max\big{\\{}x,u(f)/v(f)\big{\\}}+v(f)}\geq
6\frac{x}{u(f)/\big{\\{}u(f)/v(f)\big{\\}}+v(f)}=3\frac{x}{v(f)}.$

We now show that the following is less than or equal to $1$:

$\mathbb{E}\left[e^{\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)}\right]-1=\mathbb{E}\bigg{[}\int_{0}^{\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)}e^{x}dx\bigg{]}=\mathbb{E}\left[\int_{0}^{\infty}\mathbb{I}_{x\leq\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)}e^{x}dx\right]$

Note the following:

  * •

Since $f$ is bounded and since
$\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}\leq\pi_{\min}^{T-1}$ a.s. by
Condition 2, thus $\underline{\mathbb{G}_{n}}(f)$ is bounded a.s. (remember
$n$ is fixed).

  * •

Since we are consider the cases in which $\|f\|_{\infty}>0$, thus $v(f)>0$.

  * •

By the above two results, $\underline{\mathbb{G}_{n}}(f)/v(f)$ is bounded
a.s., so
$\mathbb{E}\left[\int_{0}^{\infty}\mathbb{I}_{x\leq\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)}e^{x}dx\right]$
is also bounded.

Thus, by Fubini’s theorem, we can exchange the integrals,

$=\int_{0}^{\infty}\mathbb{E}\bigg{[}\mathbb{I}_{x\leq\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)}\bigg{]}e^{x}dx=\int_{0}^{\infty}\mathbb{P}\bigg{(}\left|\underline{\mathbb{G}_{n}}(f)\right|\geq
xv(f)\bigg{)}e^{x}dx$

By display (E.19),

$\leq
2\int_{0}^{\infty}e^{-3x}e^{x}dx=2\int_{0}^{\infty}e^{-2x}dx=2\left(\lim_{x\to\infty}-\frac{1}{2}e^{-2x}+\frac{1}{2}e^{0}\right)=2\left(0+\frac{1}{2}\right)=1.$

Thus we have that for $\gamma(x)=e^{x}-1$,

$\mathbb{E}\left[\gamma\big{\\{}\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)\big{\\}}\right]=\mathbb{E}\left[\exp\big{\\{}\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)\big{\\}}\right]-1\leq
1.$ (E.20)

Note that $\gamma(x)=e^{x}-1$ is convex, so by Jensen’s inequality,

$\exp\left(\mathbb{E}\left[\max_{f\in\mathcal{F}}\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)\right]\right)-1=\gamma\left(\mathbb{E}\left[\max_{f\in\mathcal{F}}\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)\right]\right)$
$\leq\mathbb{E}\left[\gamma\left(\max_{f\in\mathcal{F}}\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)\right)\right]\leq\sum_{f\in\mathcal{F}}\mathbb{E}\left[\gamma\left\\{\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)\right\\}\right]\leq|\mathcal{F}|.$

The last inequality above holds by display (E.20). By adding $1$ and taking
the $\log$ on both sides, we have display (E.17) holds, i.e., that

$\mathbb{E}\left[\max_{f\in\mathcal{F}}\left|\underline{\mathbb{G}_{n}}(f)\right|/v(f)\right]\leq\log\left(|\mathcal{F}|+1\right).$

Proving display (E.18) holds. Let $x>0$. We now state some results and discuss
why they hold below. For all $n\geq 1$ we have that for any $f\in\mathcal{F}$,

$\mathbb{P}\left(\left|\overline{\mathbb{G}}_{n}(f)\right|\geq
x\right)\underbrace{=}_{(a)}\begin{cases}\mathbb{P}\left(\left|\overline{\mathbb{G}}_{n}(f)\right|\geq
x\right)&\textnormal{~{}if~{}}x<u(f)/v(f)\\\ 0&\textnormal{~{}if~{}}x\geq
u(f)/v(f)\end{cases}$ (E.21)
$\underbrace{\leq}_{(b)}\begin{cases}2\exp\left(-6\frac{x^{2}}{u(f)+xv(f)}\right)&\textnormal{~{}if~{}}x<u(f)/v(f)\\\
0&\textnormal{~{}if~{}}x\geq u(f)/v(f)\end{cases}$
$\underbrace{\leq}_{(c)}\begin{cases}2\exp\left(-3\frac{x^{2}}{u(f)}\right)&\textnormal{~{}if~{}}x<u(f)/v(f)\\\
0&\textnormal{~{}if~{}}x\geq u(f)/v(f)\end{cases}\leq
2\exp\left(-3\frac{x^{2}}{u(f)}\right).$

  * •

Inequality (a) holds because recall that
$\overline{\mathbb{G}_{n}}(f)\triangleq|\mathbb{G}_{n}(f)|\mathbb{I}_{|\mathbb{G}_{n}(f)|\leq
u(f)/v(f)}$.

  * •

Inequality (b) holds by Lemma E.2 (Weighted Martingale Bernstein Inequality)
since Condition 2 holds. Recall that
$u(f)=24\pi_{\min}^{-(T-1)}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]$
and $v(f)=24\pi_{\min}^{-(T-1)}\|f\|_{\infty}/\sqrt{n}$.

  * •

Inequality (c) holds because if $x<u(f)/v(f)$, then

$6\frac{x^{2}}{u(f)+xv(f)}\geq
6\frac{x^{2}}{u(f)+u(f)/v(f)v(f)}=3\frac{x^{2}}{u(f)}.$

We now show that the following is less than or equal to $1$:

$\mathbb{E}\left[e^{\left|\overline{\mathbb{G}_{n}}(f)\right|^{2}/u(f)}\right]-1=\mathbb{E}\bigg{[}\int_{0}^{\left|\overline{\mathbb{G}_{n}}(f)\right|^{2}/u(f)}e^{x}dx\bigg{]}=\mathbb{E}\left[\int_{0}^{\infty}\mathbb{I}_{x\leq\left|\overline{\mathbb{G}_{n}}(f)\right|^{2}/u(f)}e^{x}dx\right]$
$=\mathbb{E}\left[\int_{0}^{\infty}\mathbb{I}_{\sqrt{xu(f)}\leq\left|\overline{\mathbb{G}_{n}}(f)\right|}e^{x}dx\right]$

Note the following:

  * •

Since $f$ is bounded and since
$\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}\leq\pi_{\min}^{T-1}$ a.s. by
Condition 2, thus $\underline{\mathbb{G}_{n}}(f)$ is bounded a.s. (remember
$n$ is fixed).

  * •

Since are considering the cases in which
$\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\right]>0$
(see discussion of special cases at the beginning of this proof), thus
$u(f)>0$.

  * •

By the above two results, $\underline{\mathbb{G}_{n}}(f)/\sqrt{u(f)}$ is
bounded a.s., so
$\mathbb{E}\left[\int_{0}^{\infty}\mathbb{I}_{\sqrt{xu(f)}\leq\left|\overline{\mathbb{G}_{n}}(f)\right|}e^{x}dx\right]$
is also bounded.

Thus, by Fubini’s theorem, we can exchange integrals,

$=\int_{0}^{\infty}\mathbb{E}\left[\mathbb{I}_{\sqrt{xu(f)}\leq\left|\overline{\mathbb{G}_{n}}(f)\right|}\right]e^{x}dx=\int_{0}^{\infty}\mathbb{P}\left(\left|\overline{\mathbb{G}_{n}}(f)\right|\geq\sqrt{xu(f)}\right)e^{x}dx$

By display (E.21),

$\leq
2\int_{0}^{\infty}e^{-3x+x}dx=2\int_{0}^{\infty}e^{-2x}dx=2\left(\lim_{x\to\infty}-\frac{1}{2}e^{-2x}+\frac{1}{2}e^{0}\right)=2\left(0+\frac{1}{2}\right)=1.$

Thus we have that for $\gamma_{2}(x)=e^{x^{2}}-1$,

$\gamma_{2}\left(\left|\overline{\mathbb{G}_{n}}(f)\right|/\sqrt{u(f)}\right)=\mathbb{E}\left[\exp\left(\left|\overline{\mathbb{G}_{n}}(f)\right|^{2}/u(f)\right)\right]-1\leq
1.$ (E.22)

Since $\gamma_{2}(x)=e^{x^{2}}-1$ is convex, by Jensen’s inequality,

$\exp\bigg{(}\mathbb{E}\left[\max_{f\in\mathcal{F}}\left|\overline{\mathbb{G}_{n}}(f)\right|/\sqrt{u(f)}\right]^{2}\bigg{)}-1=\gamma_{2}\bigg{(}\mathbb{E}\bigg{[}\max_{f\in\mathcal{F}}\left|\overline{\mathbb{G}_{n}}(f)\right|/\sqrt{u(f)}\bigg{]}\bigg{)}$
$\leq\mathbb{E}\bigg{[}\gamma_{2}\left(\max_{f\in\mathcal{F}}\left|\overline{\mathbb{G}_{n}}(f)\right|/\sqrt{u(f)}\right)\bigg{]}\leq\sum_{f\in\mathcal{F}}\mathbb{E}\bigg{[}\gamma_{2}\left(\left|\overline{\mathbb{G}_{n}}(f)\right|/\sqrt{u(f)}\right)\bigg{]}\leq|\mathcal{F}|.$

The last inequality above holds by display (E.22). By adding $1$, taking the
$\log$ and the square-root on both sides, we have display (E.18) holds, i.e.,
that

$\mathbb{E}\bigg{[}\max_{f\in\mathcal{F}}\left|\overline{\mathbb{G}_{n}}(f)\right|/\sqrt{u(f)}\bigg{]}\leq\sqrt{\log\left(|\mathcal{F}|+1\right)}.~{}~{}~{}\blacksquare$

###  E.4 Maximal Inequality as a Function of the Bracketing Integral (Lemma
E.4)

######  Lemma E.4 (Maximal Inequality as a Function of the Bracketing
Integral).

Let $\delta>0$. Let $\mathcal{F}$ be a class of real-valued measurable
functions of $\mathcal{H}_{t}^{(i)}$ such that
$\int_{0}^{1}\sqrt{\log
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}}d\epsilon<\infty$
and
$\mathbb{E}_{\pi_{2:T}^{*}}\big{[}\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})^{2}\big{]}\leq\delta^{2}$
for all $f\in\mathcal{F}$.

Under Condition 2 (Minimum Exploration), for all $n\geq 1$,

$\mathbb{E}^{*}\bigg{[}\sup_{f\in\mathcal{F}}\big{|}\mathbb{G}_{n}(f)\big{|}\bigg{]}\lesssim\int_{0}^{\delta}\sqrt{\log
N_{[~{}]}\big{(}\delta,\mathcal{F},L_{2}\big{(}\mathcal{P}_{\pi^{*}}\big{)}\big{)}}d\epsilon\\\
+\sqrt{n}\mathbb{E}_{\pi_{2:t}^{*}}\left[\big{\\{}\pi_{2:t}^{*,(i)}\big{\\}}^{-1}F(\mathcal{H}_{t}^{(i)})\mathbb{I}_{F(\mathcal{H}_{t}^{(i)})>\sqrt{n}a(\delta)}\right],$
(E.23)

where

  * •

$a(\delta)=\delta/\sqrt{\log
N_{[~{}]}\big{(}\delta,\mathcal{F},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}}$

  * •

$\mathbb{G}_{n}(f)\triangleq\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left(\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:t}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{t}^{(i)})\right]\right)$

  * •

$F$ is an envelope where
$\sup_{f\in\mathcal{F}}|f(\mathcal{H}_{t}^{(i)})|<F(\mathcal{H}_{t}^{(i)})<\infty$
with probability $1$.

Above $\lesssim$ means less than or equal to when scaled by universal positive
constants. Above $\mathbb{E}^{*}$ refers to outer expectations as defined in
Section 18.2 Van der Vaart [2000].

Proof of Lemma E.4 (Maximal Inequality as a Function of the Bracketing
Integral). Our proof is almost identical to that of Lemma 19.34 Van der Vaart
[2000] except that we use the maximal inequality in Lemma E.3 instead of a
maximal inequality for i.i.d. data; we include the full proof for clarity and
completeness. For notational convenience we consider the $t$ set to $T$ case;
the argument holds by the same argument for any $t\in[2\colon T]$.

Note that by triangle inequality,

$\mathbb{E}^{*}\bigg{[}\sup_{f\in\mathcal{F}}\left|\mathbb{G}_{n}(f)\right|\bigg{]}\\\
\leq\mathbb{E}^{*}\bigg{[}\sup_{f\in\mathcal{F}}\left|\mathbb{G}_{n}\left(f\mathbb{I}_{F>\sqrt{n}a(\delta)}\right)\right|\bigg{]}+\mathbb{E}^{*}\bigg{[}\sup_{f\in\mathcal{F}}\left|\mathbb{G}_{n}\left(f\mathbb{I}_{F\leq\sqrt{n}a(\delta)}\right)\right|\bigg{]}.$
(E.24)

Bounding First Term in display (E.24). This term is to deal with potentially
unbounded functions $f\in\mathcal{F}$.

$\mathbb{E}^{*}\bigg{[}\sup_{f\in\mathcal{F}}\left|\mathbb{G}_{n}\left(f\mathbb{I}_{F>\sqrt{n}a(\delta)}\right)\right|\bigg{]}$

By using the definition of $\mathbb{G}_{n}$,

$=\mathbb{E}^{*}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\bigg{(}\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\mathbb{I}_{F(\mathcal{H}_{T}^{(i)})>\sqrt{n}a(\delta)}-\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\mathbb{I}_{F(\mathcal{H}_{T}^{(i)})>\sqrt{n}a(\delta)}\right]\bigg{)}\bigg{|}\bigg{]}$

By triangle inequality,

$\leq\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\mathbb{E}^{*}\bigg{[}\sup_{f\in\mathcal{F}}\left|\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\mathbb{I}_{F(\mathcal{H}_{T}^{(i)})>\sqrt{n}a(\delta)}\right|\bigg{]}\\\
+\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\sup_{f\in\mathcal{F}}\left\\{\left|\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}f(\mathcal{H}_{T}^{(i)})\mathbb{I}_{F(\mathcal{H}_{T}^{(i)})>\sqrt{n}a(\delta)}\right]\right|\right\\}$

By Jensen’s inequality,

$\leq
2\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\mathbb{E}^{*}\bigg{[}\sup_{f\in\mathcal{F}}\left(\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}\big{|}f(\mathcal{H}_{T}^{(i)})\big{|}\mathbb{I}_{F(\mathcal{H}_{T}^{(i)})>\sqrt{n}a(\delta)}\right)\bigg{]}$

Recall our envelope function $F$ satisfies
$|f(\mathcal{H}_{t}^{(i)})|<F(\mathcal{H}_{t}^{(i)})<\infty$ a.s., so

$\leq
2\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\mathbb{E}\left[\big{\\{}\hat{\pi}_{2:T}^{(i)}\big{\\}}^{-1}F(\mathcal{H}_{T}^{(i)})\mathbb{I}_{F(\mathcal{H}_{T}^{(i)})>\sqrt{n}a(\delta)}\right]$
$=2\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}F(\mathcal{H}_{T}^{(i)})\mathbb{I}_{F(\mathcal{H}_{T}^{(i)})>\sqrt{n}a(\delta)}\right]$

Since the expectation above is indexed by the deterministic policy
$\pi_{2:T}^{*}$, $\mathcal{H}_{T}^{(i)}$ within the expectation are i.i.d.

$=2\sqrt{n}\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{\\{}\pi_{2:T}^{*,(i)}\big{\\}}^{-1}F(\mathcal{H}_{T}^{(i)})\mathbb{I}_{F(\mathcal{H}_{T}^{(i)})>\sqrt{n}a(\delta)}\right]$

This us gives us the second part of the bound from display (E.23).

Bounding Second Term in display (E.24). We now focus on bounding the
following:

$\mathbb{E}^{*}\bigg{[}\sup_{f\in\mathcal{F}}\left|\mathbb{G}_{n}f\mathbb{I}_{F\leq\sqrt{n}a(\delta)}\right|\bigg{]}$

We now consider the class of functions
$\bar{\mathcal{F}}:=\left\\{f\mathbb{I}_{F\leq\sqrt{n}a(\delta)}:f\in\mathcal{F}\right\\}$.
We first show that
$N_{[~{}]}\big{(}\epsilon,\bar{\mathcal{F}},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}\leq
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}$.

  * •

By definition of bracketing numbers, we can cover $\mathcal{F}$ with
$N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}$
brackets, each with size at most $\epsilon$. Specifically, we can find
brackets $[l_{j},u_{j}]$ for
$j\in\left[1\colon
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}\right]$
that cover $\mathcal{F}$ such that
$\mathbb{E}_{\pi_{2:T}^{*}}\left[(u_{j}-l_{j})^{2}\right]^{1/2}\leq\epsilon$
for all brackets $[l_{j},u_{j}]$.

  * •

Note that brackets
$\left[l_{j}\mathbb{I}_{F\leq\sqrt{n}a(\delta)},~{}u_{j}\mathbb{I}_{F\leq\sqrt{n}a(\delta)}\right]$
for some $j\in\left[1\colon
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}\right]$
cover $\bar{\mathcal{F}}$.

  * •

Additionally, note that
$\mathbb{E}_{\pi_{2:T}^{*}}\left[\big{(}[u_{j}-l_{j}]\mathbb{I}_{F\leq\sqrt{n}a(\delta)}\big{)}^{2}\right]\leq\mathbb{E}_{\pi_{2:T}^{*}}\left[(u_{j}-l_{j})^{2}\right]\leq\epsilon^{2}$.

Thus, we have that

$N_{[~{}]}\big{(}\epsilon,\bar{\mathcal{F}},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}\leq
N_{[~{}]}\big{(}\epsilon,\mathcal{F},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}.$
(E.25)

Desiderata for Nested Partitions. We now assume the existence of nested
partitions of $\bar{\mathcal{F}}$ that satisfy certain conditions. We will
finish the proof assuming these partitions exist and conclude by constructing
these partitions.

High level, we assume we have nested partitions of $\bar{\mathcal{F}}$ that
are indexed by positive integers $q$. These partitions are designed to become
increasingly fine-grained as $q$ increases. Specifically the “size” of each
piece of the partition will be on the order of $2^{-q}$, i.e., the “size” of
the partitions will halve as $q$ increases by $1$. The partitions are nested
in that each partition piece at level $q+1$ is a subset of some partition
piece at level $q$.

We pick $q_{0}$ to be a positive integer such that

$\delta<2^{-q_{0}}\leq 2\delta.$ (E.26)

For every integer $q\geq q_{0}$ we have a partition of $\bar{\mathcal{F}}$; we
denote these partions as $\\{\bar{\mathcal{F}}_{q,j}\\}_{j=1}^{N_{q}}$. We
assume that
$N_{q_{0}}=N_{[~{}]}\big{(}2^{-q_{0}},\bar{\mathcal{F}},L_{2}(\mathcal{P}_{\pi^{*}})\big{)}$.
These partitions are nested in that for each $q\geq q_{0}+1$ and for every
$j\in[1\colon N_{q}]$, we have that the partition piece
$\bar{\mathcal{F}}_{q,j}$ is a subset of some partition piece
$\bar{\mathcal{F}}_{q-1,k}$ for some $k\in[1\colon N_{q-1}]$. Moreover, we
further assume the following:

  * •

Requirement on the “size” of partition pieces: For each partition $q$ and
partition piece $j\in[1\colon N_{q}]$, let $\Delta_{q,j}$ be a measurable
function of $\mathcal{H}_{T}^{(i)}$ such that
$\sup_{f,g\in\bar{\mathcal{F}}_{q,j}}|f-g|\leq\Delta_{q,j}$ a.s. and