Update $\widehat{\Gamma}_{k}$ by  on $\cbr{Z_{k,0,\ell}\cup Z_{k,1,\ell}, X_{k,0,\ell}\cup X_{k,1,\ell}}$, $\ell\leftarrow \ell+1$
Output: $\widehat{\Gamma}_{k}$

Input $\mc{W}_k, \delta, \zeta_k, \widehat{\Gamma}_{k}, \omega,L_{\nu},k$
$N_{k,2}=\ur{2(1+\omega)\zeta_k^{-2}\rho(\mc{W}_k)L_{\nu}\log\rbr{\fr{4k^2\abr{\mc{W}}}{\delta}}}\vee r(\omega)$
get $N_{k,2}$ samples per design $\widehat{\lambda}_k$ denoted as $\cbr{Z_{k,2},X_{k,2},Y_{k,2}}$ via ROUND
update $\widehat{\theta}_{\texttt{P-2SLS}}^k=(\widehat{\Gamma}_k^{\top}Z_{k,2}^{\top}Z_{k,2}\widehat{\Gamma}_k)^{-1}\widehat{\Gamma}_k^{\top}Z_{k,2}^{\top}Y_{k,2}$
Output: $\widehat{\theta}_{\texttt{P-2SLS}}^k$

Algorithm <ref> and $N_{k,1,\ell}, N_{k,0,\ell}$ guarantees three properties:

* Property 1: $N_{k,1,\ell}\ge N_{k,0,\ell}$.

* Property 2: $\fr{1}{2}\rbr{N_{k,0,\ell}+N_{k,1,\ell}}\le N_{k,0,\ell-1}+N_{k,1,\ell-1}$.

* Property 3: $\fr{N_{k,1,1}}{8d \ln\del{1 + \fr{N_{k,1,1}L_{z}^2}{d} } + 16\ln\del{\fr{2\cd6^dk^2}{\dt}}}\le M\ln\rbr{dM}$.

For Property 1, recall that $N_{k,0,\ell}$ and $N_{k,1,\ell}$ are defined as

\begin{align*}
N_{k,0,\ell}=\urd{2gdM\ln\del{M\rbr{d+N_{k,1,\ell}+L_z^2}}+4M\ln\del{\fr{2\cd6^d}{\dt_{k,\ell}}}\vee r(\omega)}
\end{align*}

\begin{align*}
N_{k,1,\ell}=2^\ell\drd{4gdM\ln\del{1+2M\rbr{d+L_z^2}+2M2gdM}+8M\ln\del{\fr{2\cd6^d}{\dt_{k,1}}}\vee r(\omega)}.
\end{align*}

We prove the result by induction. For the result for $\ell=1$, note that $N_{k,1,1}$ is of the form $N_{k,1,1}=2a + 2b \ln(1 + 2c + 2bd)$ and $N_{k,0,1}$ is of the form $N_{k,0,1}=a + b \ln(c + dr)$, where

* $a = 4M\ln\del{\fr{2\cd6^d}{\dt_{k,1}}}$

* $b = 2gdM$

* $c = M\rbr{d+L_z^2}$

* $d = M$

* $r = N_{k,1,\ell}$.

By the contraposition of <ref>, we have

\begin{align*}
r > 2a + 2b \ln(1 + 2c + 2bd)\implies   r > a + b\ln(c + dr).
\end{align*}

Thus we have $N_{k,1,1} \ge N_{k,0,1}$. Now we assume the result holds for $\ell$, i.e., $N_{k,1,\ell}\ge N_{k,0,\ell}$ and prove that it holds for $\ell+1$. We have

\begin{align*}
N_{k,1,\ell+1}=2N_{k,1,\ell}\ge 2N_{k,0,\ell}.
\end{align*}

It suffices to prove that

\begin{align*}
2N_{k,0,\ell}\ge N_{k,0,\ell+1}.
\end{align*}

We have

\begin{align*}
=&2\urd{2gdM\ln\del{M\rbr{d+N_{k,1,\ell}+L_z^2}}+4M\ln\del{\fr{2\cd6^d}{\dt_{k,\ell}}}\vee r(\omega)}\\
\ge&2gdM\ln\del{M^2\rbr{d+N_{k,1,\ell}+L_z^2}^2}+8M\ln\del{\fr{2\cd6^d\ell^2}{\dt_{k,1}}}\vee r(\omega)\\
\ge&2gdM\ln\del{M^2\rbr{d+N_{k,1,\ell}+L_z^2}^2}+8M\rbr{\ln\del{\fr{2\cd6^d}{\dt_{k,1}}}+2\ln\rbr{\ell}}\vee r(\omega)\\
\ge&2gdM\ln\del{M^2\rbr{d+N_{k,1,\ell}+L_z^2}^2}+4M\rbr{\ln\del{\fr{2\cd6^d}{\dt_{k,1}}}+2\ln\rbr{\ell+1}}\vee r(\omega) \tag{$2\ln{\ell}\ge\ln\rbr{\ell+1}$ for $\ell\ge2$}\\
\ge&2gdM\ln\del{M\rbr{d+2N_{k,1,\ell}+L_z^2}}+4M\ln\del{\fr{2\cd6^d\rbr{\ell+1}^2}{\dt_{k,1}}}\vee r(\omega)\\
\end{align*}

For Property 2, it suffices to prove that

\begin{align*}
\fr{1}{2}N_{k,0,\ell} \le N_{k,0,\ell-1}.
\end{align*}

This is equivalent to prove that

\begin{align*}
\fr{1}{2}\rbr{a+b\ln(c+2dr)}\le a+b\ln(c+dr).
\end{align*}

We have

\begin{align*}
&\fr{1}{2}\rbr{a+b\ln(c+2dr)}\le a+b\ln(c+dr)\\
\iff&\fr{1}{2}b\ln(c+2dr)\le \fr{1}{2}a+b\ln(c+dr)\\
\iff&b\ln\rbr{\sqrt{c+2dr}}\le\fr{1}{2}a+b\ln(c+dr)\\
\impliedby&\sqrt{c+2dr}\le c+dr\\
\iff&c+2dr\le c^2+2cdr+d^2r^2\\
\iff&dr\rbr{dr+2c-2}+c^2-c\ge0.
\end{align*}

The last inequality holds because $c=M>1$.

For Property 3, we have,

\begin{align*}
&\fr{4dM\ln\del{1+2M\rbr{d+L_z^2}+2MdM}+8M\ln\del{\fr{2\cd6^dk^2}{\dt}}}{8d \ln\del{1 + \fr{N_{k,1,1}L_{z}^2}{d} } + 16\ln\del{\fr{2\cd6^dk^2}{\dt}}}\\
\le&\fr{4dM\ln\del{1+2M\rbr{d+L_z^2}+2MdM}}{8d \ln\del{1 + \fr{N_{k,1,1}L_{z}^2}{d} } + 16\ln\del{\fr{2\cd6^dk^2}{\dt}}}+\fr{8M\ln\del{\fr{2\cd6^dk^2}{\dt}}}{8d \ln\del{1 + \fr{N_{k,1,1}L_{z}^2}{d} } + 16\ln\del{\fr{2\cd6^dk^2}{\dt}}}\\
\le&\fr{M\ln\del{1+2M\rbr{d+L_z^2}+2MdM}}{2 \ln\del{1 + ML_{z}^2 }}+\fr{M}{2} \tag{loosely apply $N_{k,1,1}\ge dM$}\\
\le&M\ln\rbr{dM}.
\end{align*}

Algorithm <ref> guarantees that with probability at least $1-\delta$, the best arm is returned, and the algorithm terminates in at most

\begin{align*}
\end{align*}

pulls, ignoring both of the additive and multiplicative logarithms of $\Delta, \abr{\mc{W}}, \rho^*, \rho_0, M$, where

\begin{align*}
\rho^*=\min_{\lambda\in\Delta(\mc{Z})}\max_{w\in \mathcal{W}\setminus \{w^{\ast}\}}\frac{\|w^{\ast}-w\|^2_{(\sum_{z\in \mathcal{Z}}\lambda_z\Gamma^{\top} zz^{\top}\Gamma)^{-1}}}{\langle w^{\ast}-w, \theta\rangle ^2},
\end{align*}

\begin{align*}
\rho_0=\max_{w\in \mathcal{W}\setminus \{w^{\ast}\}}\|w^{\ast}-w\|^2_{(\sum_{z\in \mathcal{Z}}\lambda_{E,z}\Gamma^{\top} zz^{\top}\Gamma)^{-1}},
\end{align*}

\begin{align*}
M=\fr{32L_\eta}{\gammin^2\sigma_{\min}\rbr{A(\lambda_E, I)}}\vee1.
\end{align*}

Note that $\rho_0$ does not get hurt by $\langle w^{\ast}-w, \theta\rangle$. It comes from the fact that in the first phase, we initialize that algorithm with E-optimal design.

Part 1: correctness of the algorithm

The idea of the proof is similar to the proof of <ref>.

Recall that the confidence interval of  can be break down into two terms (<ref>).

\begin{align*}
\ibr{\widehat{\theta}_{\texttt{P-2SLS}}-\theta}{w}=\sum_{q=1}^{T_2}\ibr{\rbr{\sum_{t=1}^{T_2}z_{I_t}z_{I_t}^\top\widehat{\Gamma}}^{-1}z_{I_q}}{w}\nu_q+\ibr{\rbr{\widehat{\Gamma}^{-1}-\Gamma^{-1}}\Gamma\theta}{w}.
\end{align*}

Given $\widehat{\Gamma}$, for a $w\in\mc{W}$, with probability at least $1-\fr{\delta}{2}$ the first term satisfies

\begin{align*}
\sum_{q=1}^{T_2}\ibr{\rbr{\sum_{t=1}^{T_2}z_{I_t}z_{I_t}^\top\widehat{\Gamma}}^{-1}z_{I_q}}{w}\nu_q\le\vcn{w}_{\bar{A}(Z_{T_2}, \widehat{\Gamma})^{-1}}\sqrt{2\sigma_{\nu}^2\log\rbr{\fr{4}{\delta}}}.
\end{align*}

For any $w\in\mc{W}$, with probability at least $1-\fr{\delta}{2}$, the second term satisfies

\begin{align*}
\ibr{\rbr{\widehat{\Gamma}^{-1}-\Gamma^{-1}}\Gamma\theta}{w}\le\vcn{w}_{\bar{A}(Z_{T_1}, \widehat{\Gamma})^{-1}}\vcn{\theta}_2\sqrt{\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta/4}}.
\end{align*}

Note that by <ref>, the above inequality holds for all $w\in\mc{W}$, and the RHS is essentially a result of

\begin{align*}
\vcn{V^{-1/2}Z_{T}^\top S}_{\text{op}}\le\sqrt{\sigma_{\eta}^2\overline{\log}\rbr{Z_{T},\delta/4}}.
\end{align*}

In the vanilla form of the confidence of , we can define good events as

* for the first term, for any $w\in\mc{W}$,

\begin{align*}
\sum_{q=1}^{T_2}\ibr{\rbr{\sum_{t=1}^{T_2}z_{I_t}z_{I_t}^\top\widehat{\Gamma}}^{-1}z_{I_q}}{w}\nu_q\le\vcn{w}_{\bar{A}(Z_{T_2}, \widehat{\Gamma})^{-1}}\sqrt{2\sigma_{\nu}^2\log\rbr{16k^2\abr{\mc{W}}/\delta}}.
\end{align*}

* for the second term, $\vcn{V^{-1/2}Z_{T}^\top S}_{\text{op}}\le\sqrt{\sigma_{\eta}^2\overline{\log}\rbr{Z_{T},\delta/4}}$.

For our algorithm design, since we use the doubling trick for the first sub-phase, we need to define the good event for the first sub-phase as the samples from each doubling trick iteration satisfies the self-normalized concentration inequality of <ref>.

We define the good event for $\ell$-th doubling trick iteration in the first sub-phase of phase $k$ as

\begin{align*}
\mc{E}^1_{k, \ell}=\cbr{\vcn{V_{k,\ell}^{-1/2}Z_{k,\ell}^\top S_{k,\ell}}^2_{\text{op}}\le\sigma_{\eta}^2\overline{\log}\rbr{Z_{k,\ell},\fr{\delta}{4k^2(\ell+1)^2}}},
\end{align*}

where $Z_{k,\ell}=Z_{k,0,\ell}\cup Z_{k,1,\ell}$, $V_{k,\ell}=Z_{k,\ell}^{\top}Z_{k,\ell}$ and $S_{k,\ell}$ is stacked noise matrix during collecting samples $Z_{k,\ell}$ per the model $X=Z\Gamma+S$. By a union bound, we have

\begin{align*}
\pp{\rbr{\bigcap_{k=1}^{\infty}\bigcap_{\ell=1}^{\infty}\mc{E}_{k,\ell}^1}^c}\le\sum_{k=1}^{\infty}\sum_{\ell=1}^{\infty}\pp{\mc{E}_{k,\ell}^1}\le\delta/2.
\end{align*}

For the second sub-phase in phase $k$, we define the good event for the second sub-phase in phase $k$ and $w\in\mc{W}$ as

\begin{align*}
\mc{E}^2_{k, w}=\cbr{\sum_{q=1}^{N_{k,2}}\ibr{\rbr{\sum_{t=1}^{N_{k,2}}z_{I_t}z_{I_t}^\top\widehat{\Gamma}}^{-1}z_{I_q}}{w}\nu_q\le\vcn{w}_{\bar{A}(Z_{k,2}, \widehat{\Gamma})^{-1}}\sqrt{2\sigma_{\nu}^2\log\rbr{16k^2\abr{\mc{W}}/\delta}}}.
\end{align*}

By a union bound, we have

\begin{align*}
\pp{\rbr{\bigcap_{k=1}^{\infty}\bigcap_{w\in\mc{W}_k}\mc{E}_{k,w}^2}^c}\le\sum_{k=1}^{\infty}\sum_{w\in\mc{W}}\pp{\mc{E}_{k,w}^2}\le\delta/2.
\end{align*}

Under the good event $\rbr{\bigcap_{k=1}^{\infty}\bigcap_{\ell=1}^{\infty}\mc{E}_{k,\ell}^1}\bigcap\rbr{\bigcap_{k=1}^{\infty}\bigcap_{w\in\mc{W}_k}\mc{E}_{k,w}^2}$, we have with probability at least $1-\delta$, for all $k$ and $w\in\mc{W}$,

\begin{align*}
\abr{\ibr{\widehat{\theta}_{\texttt{P-2SLS}}^k-\theta}{w-w^*}}\le\zeta_k.
\end{align*}

The rest of proof is same as the proof of <ref>.

Part 2: sample complexity of algorithm

Sample complexity for first sub-phase

Recall that $\lambda_E = \arg\max_{\lambda\in\Delta(\mc{Z})}\sig_{\min}\rbr{\sum_{z\in \mathcal{Z}}\lambda_z zz^{\top}}$ is the E-optimal design to maximize the minimum singular value of $\sum_{z\in \mathcal{Z}}\lambda_z zz^{\top}$ and $\kappa_0=\max_{\lambda}\sigmin(\sum_{z\in\cZ}\lambda_zzz^\T)$ is the maximum minimum singular value of $\sum_{z\in\cZ}\lambda_zzz^\T$. At the beginning of first sub-phase in phase $k$, the algorithm first samples $N_{k,0,0}$ arms according to $\lambda_E$.

Before we proceed to the main proof of the sample complexity, we first address a minor technique issue to avoid cumbersomeness. For the logarithmic term that appears in the algorithm and confidence interval,

\begin{align*}
\overline{\log}\rbr{Z_{T},\delta}:=8d \ln\del{1 + \fr{2TL_z^2}{d(2\wed \sigmin(Z_{T}^{\top}Z_{T}))} } + 16\ln\del{\fr{2\cd6^d}{\dt}\cd \log^2_2\del{\fr{4}{2\wed \sigmin(Z_{T}^{\top}Z_{T})} }  },
\end{align*}

when $2\wed \sigmin(V)=2$, it is equivalent to

\begin{align*}
\widetilde{\log}\rbr{T,\delta}:=8d \ln\del{1 + \fr{TL_z^2}{d} } + 16\ln\del{\fr{2\cd6^d}{\dt}}.
\end{align*}

Our algorithm design guarantees that $2\wed \sigmin(V)=2$ is always true whenever we need to use the logarithmic term $\overline{\log}\rbr{Z_{T},\delta}$, given that the samples of our interest always includes the E-optimal design samples $Z_{k,0,\ell}$ and the number of samples from the E-optimal design $\abr{Z_{k,0,\ell}}$ is always larger than $\fr{2}{\kappa_0}$. So for the remaining part of the proof, we will use $\widetilde{\log}\rbr{N,\delta}$ instead of $\overline{\log}\rbr{Z_{T},\delta}$.

Denote the samples of E-optimal design that mixed into the samples from $\ell$-th doubling trick iteration in the first sub-phase of phase $k$ as $Z_{k,0,\ell}$ and $\abr{Z_{k,0,\ell}}=N_{k,0,\ell}$.
By <ref>, our choice of $N_{k,0,\ell}$

\begin{align*}
N_{k,0,\ell}\ge\fr{64g d\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\ln\rbr{\fr{32g\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\rbr{d+N_{k,1,\ell}L_z^2+L_z^2} }+\fr{128g\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\ln\rbr{\fr{2\cd6^d}{\dt}},
\end{align*}

is a sufficient condition to guarantee

\begin{align}
N_{k,0,\ell}\ge \fr{4g\sigma_{\eta}^2\widetilde{\log}\rbr{N_{k,0,\ell}+N_{k,1,\ell},\delta_{k,\ell}}}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\vee r(\omega). \label{ieq:cond_nk0ell}
\end{align}

Multiply both sides of (<ref>) by $\fr{N_{k,0,\ell}+N_{k,1,\ell}}{N_{k,0,\ell}}$ and we have

\begin{align*}
N_{k,0,\ell}+N_{k,1,\ell} \ge \rbr{\fr{4g\sigma_{\eta}^2\widetilde{\log}\rbr{N_{k,0,\ell}+N_{k,1,\ell},\delta_{k,\ell}}}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}} \vee r(\omega)}\fr{N_{k,0,\ell}+N_{k,1,\ell}}{N_{k,0,\ell}}.
\end{align*}

By Property 1 of <ref>, we have $\alpha_{k,\ell} := \fr{N_{k,0,\ell}}{N_{k,0,\ell}+N_{k,1,\ell}}<1/2$, then

\begin{align}
N_{k,0,\ell}+N_{k,1,\ell}&\ge \fr{1}{\alpha_{k,\ell}}\rbr{\fr{4g\sigma_{\eta}^2\widetilde{\log}\rbr{N_{k,0,\ell}+N_{k,1,\ell},\delta_{k,\ell}}}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}} \vee r(\omega)}\nn\\
&=\fr{4g\sigma_{\eta}^2\widetilde{\log}\rbr{N_{k,0,\ell}+N_{k,1,\ell},\delta_{k,\ell}}}{\sigma_{\min}\rbr{A(\alpha_{k,\ell}\lambda_E, \Gamma)}} \vee \fr{r(\omega)}{\alpha_{k,\ell}}\nn\\
&\ge\fr{4g\sigma_{\eta}^2\widetilde{\log}\rbr{N_{k,0,\ell}+N_{k,1,\ell},\delta_{k,\ell}}}{\sigma_{\min}\rbr{A(\alpha_{k,\ell}\lambda_E+(1-\alpha_{k,\ell})\tilde{\lambda}_k, \Gamma)}} \vee r(\omega). \label{ieq:cond_Nk0Nk1_ell}
\end{align}

These condition on $N_{k,0,\ell}$ and $N_{k,0,\ell}+N_{k,1,\ell}$ are needed for the proof.

Denote the total number of doubling trick iterations as $L_k$ for phase $k$. In the case of $L_k=1$, the samples from the first doubling trick iteration satisfies stopping condition of the first sub-phase already, and the algorithm will not enter the second doubling trick iteration. Thus the total number of samples for the first sub-phase is

\begin{align*}
N_{k,0,1}+N_{k,1,1}\le& 2N_{k,1,1}\nn \tag{Property 1 of \cref{lem: Nk0<Nk1}}\\
\le&8gdM\ln\del{1+2M\rbr{d+L_z^2}+2M2gdM}+16M\ln\del{\fr{2\cd6^d}{\dt_{k,1}}}\vee r(\omega).
\end{align*}

In the case of $L_k>1$, for $\ell\in\cbr{1,\cdots,L_k}$, denote $\widehat{\Gamma}^\ell$ as the estimate of $\Gamma$ at the end of the $\ell$-th doubling trick iteration. With these notations, we have

* At the end of $L_k$-th doubling trick iteration, the stopping condition is satisfied, i.e.,

\begin{align}
\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{\bar{A}(Z_{k,0,L_k}\cup Z_{k,1,L_k}, \widehat{\Gamma}^{L_k})^{-1}}\vcn{\theta}^2_2L_{\eta}\widetilde{\log}\rbr{N_{k,0,L_k}+N_{k,1,L_k},\delta_{k,L_k}}\le\zeta^2_k.
\end{align}

We short $\widetilde{\log}\rbr{N_{k,0,\ell}+N_{k,1,\ell},\delta_{k,\ell}}=\widetilde{\log}_{k,\ell}$.

* At the end of $(L_k-1)$-th doubling trick iteration, the stopping condition is not satisfied, i.e.,

\begin{align}
\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{\bar{A}(Z_{k,0,L_k-1}\cup Z_{k,1,L_k-1}, \widehat{\Gamma}^{L_k-1})^{-1}}\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k,L_k-1}>\zeta^2_k.
\end{align}

Denote $\xi_{L_k}$ as the empirical distribution of $Z_{k,0,L_k}\cup Z_{k,1,L_k}$. Then above two conditions imply that the number of samples for $L_k$-th and $(L_k-1)$-th doubling trick iterations respectively satisfy

\begin{align}
N_{k,0,L_k}+N_{k,1,L_k}&\ge\fr{\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k,L_k}}{\zeta^2_k}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_k}, \widehat{\Gamma}^{L_k})^{-1}}. \label{ieq:b0}
\end{align}

\begin{align}
N_{k,0,L_k-1}+N_{k,1,L_k-1}&<\fr{\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k,L_k-1}}{\zeta^2_k}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_k-1}, \widehat{\Gamma}^{L_k-1})^{-1}}. \label{ieq:cond_not_stop}
\end{align}

Note that by Property 2 of <ref>,

\begin{align*}
\fr{1}{2}\rbr{N_{k,0,L_k}+N_{k,1,L_k}}\le N_{k,0,L_k-1}+N_{k,1,L_k-1}.
\end{align*}

\begin{align}
N_{k,0,L_k}+N_{k,1,L_k}<\fr{2\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k,L_k-1}}{\zeta^2_k}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_k-1}, \widehat{\Gamma}^{L_k-1})^{-1}}. \label{ieq:b0_1}
\end{align}

For any $\ell\in\cbr{1,\ldots,L_k}$, by <ref>, the factor of $\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \widehat{\Gamma}^{\ell})^{-1}}$ can be upper bounded by

\begin{align}
&\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \widehat{\Gamma}^{\ell})^{-1}} \nn\\
\le& 3\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \widehat{\Gamma}^{L_{k-1}})^{-1}} + 2\max_{w,w'\in\mc{W}_k}\vcn{((\widehat{\Gamma}^{\ell})^{-\top}-(\widehat{\Gamma}^{L_{k-1}})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\xi_{\ell}zz^\top}^{-1}} \nn\\
\le& 3\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \widehat{\Gamma}^{L_{k-1}})^{-1}} + 2\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{\ell})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\xi_{\ell}zz^\top}^{-1}} \nn\\
&+2\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k-1}})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\xi_{\ell}zz^\top}^{-1}}. \label{ieq:b1}
\end{align}

We will upper bound the three terms in the RHS of (<ref>) separately.

For the first term, by <ref>,

\begin{align}
\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \widehat{\Gamma}^{L_{k-1}})^{-1}}\le4\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\tilde{\lambda}_{k}, \widehat{\Gamma}^{L_{k-1}})^{-1}}, \label{ieq:b1_1}
\end{align}

where $\tilde{\lambda}_{k}$ is the optimal design for $\mc{W}_k$ in the first sub-phase of phase $k-1$ (based on the last doubling trick iteration), i.e.,

\begin{align*}
\tilde{\lambda}_{k}=\arg\min_{\lambda\in\Delta(\mc{Z})}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda, \widehat{\Gamma}^{L_{k-1}})^{-1}}.
\end{align*}

Then for any $\lambda$,

\begin{align}
&\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\tilde{\lambda}_{k}, \widehat{\Gamma}^{L_{k-1}})^{-1}} \nn\\
\le&3\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda, \Gamma)^{-1}}+2\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k-1}})^{-\top})\rbr{w-w'}}^2_{A(\lambda, I)^{-1}} \tag{\cref{lem:approx any Gamma}}\nn\\
\stackrel{b_{1}}{\le}&3\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda'_k, \Gamma)^{-1}}+2\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k-1}})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda'_k zz^\top}^{-1}} \nn\\
\stackrel{b_{2}}{\le}&6\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}+2\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k-1}})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda'_k zz^\top}^{-1}}. \label{ieq:b2}
\end{align}

where for $(b_{1})$, we plug in $\lambda'_k:=\alpha^*_k\lambda_E+(1-\alpha^*_k)\lambda^*_k$, with $\alpha^*_k\le1/2$ will be defined later and $\lambda^*_k$ is the optimal design for $\mc{W}_k$ given $\Gamma$, i.e.,

\begin{align*}
\lambda^*_k=\arg\min_{\lambda\in\Delta(\mc{Z})}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda, \Gamma)^{-1}}.
\end{align*}

$(b_{2})$ is due to the fact that $\alpha^*_k\le1/2$. For the second term in the RHS of (<ref>), given the condition (<ref>), i.e.,

\begin{align*}
N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}\ge\fr{4gL_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}{\sig_{\min}\rbr{A(\xi_{L_{k-1}}, \Gamma)}}
\end{align*}

by <ref> we have,

\begin{align}
&\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k-1}})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda'_k zz^\top}^{-1}} \nn\\
\le&\fr{2L_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}{\sig_{\min}\rbr{A(\lambda'_k, \Gamma)}}\fr{1}{N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \Gamma)^{-1}} \nn\\
\le&\fr{1}{N_{k-1,0,L_{k-1}}}\fr{2L_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}{\sig_{\min}\rbr{A(\lambda'_k, \Gamma)}}\fr{N_{k-1,0,L_{k-1}}}{N_{k-1,0,L_{k-1}+N_{k-1,1,L_{k-1}}}}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \Gamma)^{-1}} \nn\\
\le&\fr{1}{N_{k-1,0,L_{k-1}}}\fr{2L_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}{\sig_{\min}\rbr{A(\alpha^*_k\lambda_E, \Gamma)}}\fr{N_{k-1,0,L_{k-1}}}{N_{k-1,0,L_{k-1}+N_{k-1,1,L_{k-1}}}}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \Gamma)^{-1}} \nn\\
\le&\fr{1}{N_{k-1,0,L_{k-1}}}\fr{2L_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}{\sig_{\min}\rbr{A(\lambda_E, \Gamma)}}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \Gamma)^{-1}} \tag{set $\alpha^*_k=\alpha_{k-1}$} \nn\\
\stackrel{b_{1}}{\le}&\fr{1}{4g}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \Gamma)^{-1}} \nn\\
\stackrel{b_{2}}{\le}&\fr{6}{4g}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \widehat{\Gamma}^{L_{k-1}})^{-1}}. \label{ieq:b3}
\end{align}

where for $(b_{1})$, we use the condition (<ref>) on $N_{k-1,0,L_{k-1}}$, and $(b_{2})$ is due to <ref>. Plug (<ref>) into (<ref>), we have

\begin{align}
\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\tilde{\lambda}_{k}, \widehat{\Gamma}^{L_{k-1}})^{-1}}\le6\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}+\fr{3}{g}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \widehat{\Gamma}^{L_{k-1}})^{-1}}. \label{ieq:b4}
\end{align}

Plug (<ref>) into (<ref>), we have the first term in the RHS of (<ref>) can be upper bounded by

\begin{align}
&\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \widehat{\Gamma}^{L_{k-1}})^{-1}} \nn\\
&\le24\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}+\fr{12}{g}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \widehat{\Gamma}^{L_{k-1}})^{-1}}\nn\\
&\le 24\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}+\fr{12}{g}\fr{\zeta^2_{k-1}}{\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}(N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}),\label{ieq:b5}
\end{align}

where for the last inequality we use the fact that the stopping condition is satisfied at the end of $(L_{k-1})$-th doubling trick iteration for phase $k-1$ per (<ref>).

For the second term in the RHS of (<ref>), by <ref>, when the condition (<ref>) is satisfied, i.e., when

\begin{align*}
N_{k,0,\ell}+N_{k,1,\ell}\ge \fr{4gL_{\eta}\widetilde{\log}_{k,\ell}}{\sig_{\min}\rbr{A(\xi_{\ell}, \Gamma)}},
\end{align*}

we have

\begin{align}
\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{\ell})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\xi_{\ell}zz^\top}^{-1}} \le& \fr{1}{g}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \Gamma)^{-1}}\nn\\
\le&\fr{6}{g}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \widehat{\Gamma}^{\ell})^{-1}}, \label{ieq:b6}
\end{align}

where the last inequality is due to <ref>.

For the third term in the RHS of (<ref>), by <ref>, when the condition (<ref>) is satisfied, i.e., when

\begin{align*}
N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}\ge\fr{4gL_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}{\sig_{\min}\rbr{A(\xi_{L_{k-1}}, \Gamma)}}
\end{align*}

we have

\begin{align}
&\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k-1}})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\xi_{\ell}zz^\top}^{-1}} \nn\\
\le&\fr{2L_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}{\sig_{\min}\rbr{A(\xi_\ell, \Gamma)}}\fr{1}{N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \Gamma)^{-1}} \nn\\
\le&\fr{2L_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}{\sig_{\min}\rbr{A(\alpha_\ell\lambda_E, \Gamma)}}\fr{1}{N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_{k-1}}, \widehat{\Gamma}^{L_{k-1}})^{-1}} \nn\\
\stackrel{b_{1}}{\le}&\fr{N_{k,0,\ell}+N_{k,1,\ell}}{N_{k,0,\ell}}\fr{1}{N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}}\fr{2\widetilde{\log}_{k-1,L_{k-1}}}{\sig_{\min}\rbr{A(\lambda_E, \Gamma)}}(N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}})\fr{\zeta^2_{k-1}}{\vcn{\theta}^2_2\widetilde{\log}_{k-1,L_{k-1}}} \nn\\
\le&\fr{N_{k,0,\ell}+N_{k,1,\ell}}{N_{k,0,\ell}}\fr{2}{\sig_{\min}\rbr{A(\lambda_E, \Gamma)}}\fr{\zeta^2_{k-1}}{\vcn{\theta}^2_2} \nn\\
\stackrel{b_{2}}{\le}&\fr{N_{k,0,\ell}+N_{k,1,\ell}}{4gL_{\eta}\widetilde{\log}_{k,\ell}}\fr{\zeta^2_{k-1}}{\vcn{\theta}^2_2} \label{ieq:b7}
\end{align}

where $(b_1)$ is due to (<ref>), $(b_2)$ is due to (<ref>). Plug (<ref>), (<ref>) and (<ref>) into (<ref>), we have

\begin{align}
&\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \widehat{\Gamma}^{\ell})^{-1}} \nn\\
\le&72\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}+\fr{36}{g}\fr{\zeta^2_{k-1}}{\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}(N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}) \nn\\
&+\fr{12}{g}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{\ell}, \widehat{\Gamma}^{\ell})^{-1}}+\fr{2}{g}\fr{N_{k,0,\ell+1}+N_{k,1,\ell+1}}{L_{\eta}\widetilde{\log}_{k,\ell}}\fr{\zeta^2_{k-1}}{\vcn{\theta}^2_2}.  \label{ieq:b10}
\end{align}

With $\ell=L_{k}-1$ and the fact that $g>24$ whose exact value will be set later, we can rearrange (<ref>) as

\begin{align}
&\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_{k}-1}, \widehat{\Gamma}^{L_{k}-1})^{-1}} \nn\\
\le&144\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}+\fr{72}{g}\fr{\zeta^2_{k-1}}{\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k-1,L_{k-1}}}(N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}) \nn\\
&+\fr{1}{g}\fr{N_{k,0,L_{k}}+N_{k,1,L_{k}}}{L_{\eta}\widetilde{\log}_{k,L_{k}-1}}\fr{\zeta^2_{k-1}}{\vcn{\theta}^2_2}. \label{ieq:b8}
\end{align}

Note that the LHS of above can be lower bounded by (<ref>),

\begin{align}
\fr{\zeta^2_{k}}{2\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k,L_k-1}}(N_{k,0,L_k}+N_{k,1,L_k})<\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_k-1}, \widehat{\Gamma}^{L_k-1})^{-1}}. \label{ieq:b8_1}
\end{align}

Rearrange the terms in (<ref>) and (<ref>) and setting $g$ to be larger enough and using the fact that $\zeta_k=\zeta_{k-1}/2$, we have

\begin{align*}
N_{k,0,L_k}+N_{k,1,L_k}\le&\fr{576}{\zeta_k^2}\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k,L_k-1}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}} + \fr{72}{g}\fr{\widetilde{\log}_{k,L_k-1}}{\widetilde{\log}_{k-1,L_{k-1}}}(N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}).
\end{align*}

Note that by definition $\widetilde{\log}_{k,L_k-1}<\widetilde{\log}_{k,L_k}$, thus

\begin{align*}
N_{k,0,L_k}+N_{k,1,L_k}\le&\fr{576}{\zeta_k^2}\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k,L_k}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}} + \fr{72}{g}\fr{\widetilde{\log}_{k,L_k}}{\widetilde{\log}_{k-1,L_{k-1}}}(N_{k-1,0,L_{k-1}}+N_{k-1,1,L_{k-1}}).
\end{align*}

Denote $D_k:=N_{k,0,L_k}+N_{k,1,L_k}$ and divide both sides of above by $\widetilde{\log}_{k,L_k}$, we have

\begin{align*}
\fr{D_k}{\widetilde{\log}_{k,L_k}}\le \fr{576}{\zeta_k^2}\vcn{\theta}^2_2L_{\eta}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}} + \fr{72}{g}\fr{D_{k-1}}{\widetilde{\log}_{k-1,L_{k-1}}}.
\end{align*}

In the case of $L_k=1$, by Property 3 of <ref>, we have

\begin{align*}
\fr{D_k}{\widetilde{\log}_{k,L_k}}=\fr{N_{k,1,1}}{8d \ln\del{1 + \fr{N_{k,1,1}L_{z}^2}{d} } + 16\ln\del{\fr{2\cd6^dk^2}{\dt}}}\le M\ln\rbr{dM}.
\end{align*}

Thereby we have

\begin{align}
\fr{D_k}{\widetilde{\log}_{k,L_k}}\le\max\cbr{M\ln\rbr{dM}, \fr{576}{\zeta_k^2}\vcn{\theta}^2_2L_{\eta}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}} + \fr{72}{g}\fr{D_{k-1}}{\widetilde{\log}_{k-1,L_{k-1}}}}. \label{ieq:b9}
\end{align}

Taking a summation over $k$ on both sides of (<ref>), we have

\begin{align}
\sum_{k=1}^{K^*}\fr{D_k}{\widetilde{\log}_{k,L_k}}=&\fr{D_1}{\widetilde{\log}_{1,L_1}}+\sum_{k=2}^{K^*}\fr{D_k}{\widetilde{\log}_{k,L_k}}\\
\le&\fr{D_1}{\widetilde{\log}_{1,L_1}}+\sum_{k=2}^{K^*}\max\cbr{M\ln\rbr{dM}, \fr{576}{\zeta_k^2}\vcn{\theta}^2_2L_{\eta}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}} + \fr{72}{g}\fr{D_{k-1}}{\widetilde{\log}_{k-1,L_{k-1}}}}\\
\le&\fr{D_1}{\widetilde{\log}_{1,L_1}}+\sum_{k=2}^{K^*}M\ln\rbr{dM}+\sum_{k=2}^{K^*}\rbr{\fr{576}{\zeta_k^2}\vcn{\theta}^2_2L_{\eta}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}} + \fr{72}{g}\fr{D_{k-1}}{\widetilde{\log}_{k-1,L_{k-1}}}}\\
\le&\fr{D_1}{\widetilde{\log}_{1,L_1}}+\sum_{k=2}^{K^*}M\ln\rbr{dM}+\sum_{k=2}^{K^*}\fr{576}{\zeta_k^2}\vcn{\theta}^2_2L_{\eta}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}} + \sum_{k=2}^{K^*}\fr{72}{g}\fr{D_{k-1}}{\widetilde{\log}_{k-1,L_{k-1}}}. \label{ieq:sumD/log}
\end{align}

Thus by setting $g=72\times2$ and rearranging the terms, we have

\begin{align}
\sum_{k=1}^{K^*}\fr{D_k}{\widetilde{\log}_{k,L_k}}\le \fr{2D_1}{\widetilde{\log}_{1,L_1}}+2\sum_{k=2}^{K^*}M\ln\rbr{dM}+2\sum_{k=2}^{K^*}\fr{576}{\zeta_k^2}\vcn{\theta}^2_2L_{\eta}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}. \label{ieq:b18}
\end{align}

For $D_1$, which corresponds to the first sub-phase where we use E-optimal design with doubling trick, we have the stopping condition,

\begin{align*}
\max_{w,w'\in\mc{W}_1}\vcn{w-w'}^2_{\bar{A}(Z_{1,0,L_1}, \widehat{\Gamma}^{L_1})^{-1}}\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{1,L_1}\le\zeta^2_1.
\end{align*}

This implies that when the stopping condition is met

\begin{align}
N_{1,0,L_1}\ge \fr{\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{1,L_1}}{\zeta^2_1}\max_{w,w'\in\mc{W}_1}\vcn{w-w'}^2_{A(\xi_{L_1}, \widehat{\Gamma}^{L_1})^{-1}}. \label{ieq:b12}
\end{align}

\begin{align}
N_{1,0,L_1-1}<\fr{2\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{1,L_1-1}}{\zeta^2_1}\max_{w,w'\in\mc{W}_1}\vcn{w-w'}^2_{A(\xi_{L_1-1}, \widehat{\Gamma}^{L_1-1})^{-1}}.  \label{ieq:b12_1}
\end{align}

Since we use E-optimal design for the first phase,
the factor of $\vcn{w-w'}^2_{A(\xi_{L_1-1}, \widehat{\Gamma}^{L_1-1})^{-1}}$ can be upper bounded by

\begin{align}
&\vcn{w-w'}^2_{A(\xi_{L_1-1}, \widehat{\Gamma}^{L_1-1})^{-1}} \nn\\
\le& 3\vcn{w-w'}^2_{A(\xi_{L_1-1}, \Gamma)^{-1}} + 2\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_1-1})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\xi_{L_1-1}zz^\top}^{-1}} \tag{\cref{lem:approx any Gamma}}\nn\\
\le& 3\vcn{w-w'}^2_{A(\lambda_E, \Gamma)^{-1}} + 2\vcn{w-w'}^2_{A(\lambda_E, \Gamma)^{-1}} \tag{\cref{lem:upperbound Gamma inv_hat}}\nn\\
\le& 6\vcn{w-w'}^2_{A(\lambda_E, \Gamma)^{-1}}. \label{ieq:b13}
\end{align}

Plug (<ref>) into (<ref>), and use the fact that $2N_{1,0,L_1-1}=N_{1,0,L_1},\zeta_1=1$, we have

\begin{align}
N_{1,0,L_1}\le 24\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{1,L_1-1}\max_{w,w'\in\mc{W}_1}\vcn{w-w'}^2_{A(\lambda_E, \Gamma)^{-1}}\le 24\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{1,L_1}\max_{w,w'\in\mc{W}_1}\vcn{w-w'}^2_{A(\lambda_E, \Gamma)^{-1}}. \label{ieq:b14}
\end{align}

Thus we have,

\begin{align*}
\fr{D_1}{\widetilde{\log}_{1,L_1}}\le\fr{2N_{1,0,L_1}}{\widetilde{\log}_{1,L_1}}\le 48\vcn{\theta}^2_2L_{\eta}\max_{w,w'\in\mc{W}_1}\vcn{w-w'}^2_{A(\lambda_E, \Gamma)^{-1}}=:\rho_1.
\end{align*}

By the same calculation as (<ref>) and (<ref>), we have

\begin{align*}
\vcn{\theta}^2_2L_{\eta}\sum_{k=2}^{K^*}\fr{1}{\zeta_k^2}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}\le c\vcn{\theta}^2_2L_{\eta}K^\ast\rho^{\ast}=:\rho_2,
\end{align*}

where $c$ is an absolute constant. Next we lower bound the left hand side of (<ref>). To do this, we first upper bound $\widetilde{\log}_{k,L_k}$ as

\begin{align}
\widetilde{\log}_{k,L_k}=&8d \ln\del{1 + \fr{D_kL_{z}^2}{d} } + 16\ln\del{\fr{2\cd6^dk^2L_k^2}{\dt}} \nn\\
\le&8d \ln\del{1 + \fr{D_kL_{z}^2}{d} } + 32\ln\rbr{L_k}+16\ln\del{\fr{2\cd6^dk^2}{\dt}} \nn\\
\le&8d \ln\del{1 + \fr{D_kL_{z}^2}{d} } + 32\ln\rbr{\log_2\rbr{\fr{D_k}{d}}}+16\ln\del{\fr{2\cd6^dk^2}{\dt}} \nn\\
\le&32d \ln\del{1 + \fr{D_kL_{z}^2}{d} }+16\ln\del{\fr{2\cd6^dk^2}{\dt}}, \label{ieq:logkLk}
\end{align}

where the inequality above uses the fact that $L_k$ is the index of the last doubling trick iteration for phase $k$, by the design of the doubling trick, we have $L_k\le\log_2\rbr{\fr{D_k}{d}}$.

\begin{align*}
\sum_{k=1}^{K^*}\fr{D_k}{\widetilde{\log}_{k,L_k}}=&\sum_{k=1}^{K^*}\fr{D_k}{8d \ln\del{1 + \fr{D_kL_{z}^2}{d} } + 16\ln\del{\fr{2\cd6^dk^2L_k^2}{\dt}}}\\
\ge&\sum_{k=1}^{K^*}\fr{D_k}{32d \ln\del{1 + \fr{D_kL_{z}^2}{d} }+16\ln\del{\fr{2\cd6^dK^{\ast^2}}{\dt}}}\tag{due to \eqref{ieq:logkLk}}\\
\ge&\sum_{k=1}^{K^*}\fr{D_k}{32d \ln\del{1 + \fr{\sum_{k=1}^{K^*}D_kL_{z}^2}{d} }+16\ln\del{\fr{2\cd6^dK^{\ast2}}{\dt}}}\\
=&\fr{1}{32d \ln\del{1 + \fr{\sum_{k=1}^{K^*}D_kL_{z}^2}{d} }+16\ln\del{\fr{2\cd6^dK^{\ast^2}}{\dt}}}\sum_{k=1}^{K^*}D_k.
\end{align*}

Denote $\rho_3:=K^{\ast}M\ln\rbr{dM}$, looking back at (<ref>), we have

\begin{align*}
\sum_{k=1}^{K^*}D_k\le\rbr{32d \ln\del{1 + \fr{\sum_{k=1}^{K^*}D_kL_{z}^2}{d} }+16\ln\del{\fr{2\cd6^dK^{\ast2}}{\dt}}}\rbr{\rho_1+\rho_2+\rho_3}.
\end{align*}

By <ref>, we have

\begin{align}
\sum_{k=1}^{K^*}D_k\le 32\rbr{\rho_1+\rho_2+\rho_3}\ln\rbr{\fr{2\cd6^dK^{\ast2}}{\dt}}+64d\rbr{\rho_1+\rho_2+\rho_3}\ln\del{3 + \rbr{\rho_1+\rho_2+\rho_3}\fr{2L_{z}^2}{d}}. \label{sample complexity 1}
\end{align}

Sample complexity for second sub-phase

The design for the second sub-phase of phase $k$ is based on $\widehat{\Gamma}^{L_k}$, the estimate of $\Gamma$ at the end of the $L_k$-th doubling trick iteration in the first sub-phase of phase $k$,

\begin{align*}
\hat{\lambda}_{k}=\arg\min_{\lambda\in\Delta(\mc{Z})}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda, \widehat{\Gamma}^{L_{k}})^{-1}}.
\end{align*}

Then for any $\lambda$, by <ref> we have

\begin{align*}
&\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\hat{\lambda}_{k}, \widehat{\Gamma}^{L_{k}})^{-1}}\\
\le&3\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda, \Gamma)^{-1}}+2\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k}})^{-\top})\rbr{w-w'}}^2_{A(\lambda, I)^{-1}}
\end{align*}

We plug in $\lambda''_k:=\alpha^*_k\lambda_E+(1-\alpha^*_k)\lambda^*_k$, with $\alpha^*_k\le1/2$ will be defined later and $\lambda^*_k$ is the optimal design for $\mc{W}_k$,

\begin{align}
&\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\hat{\lambda}_{k}, \widehat{\Gamma}^{L_{k}})^{-1}} \nn\\
\le&3\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda''_k, \Gamma)^{-1}}+2\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k}})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda''_k zz^\top}^{-1}} \nn\\
\le&6\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}+2\max_{w,w'\in\mc{W}_k}\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k}})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda''_k zz^\top}^{-1}}, \label{ieq:b15}
\end{align}

where the last inequality is due to the fact that $\alpha^*_k\le1/2$. For the second term in the RHS of above, by <ref> we have,

\begin{align}
&\vcn{(\Gamma^{-\top} - (\widehat{\Gamma}^{L_{k}})^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda''_k zz^\top}^{-1}} \nn\\
\le&\fr{4L_{\eta}\widetilde{\log}_{k,L_{k}}}{\sig_{\min}\rbr{A(\lambda''_k, \Gamma)}}\vcn{w-w'}^2_{\bar{A}(Z_{k,0}\cup Z^{L_k}, \Gamma)^{-1}} \nn\\
\le&\fr{1}{N_{k,0,L_{k}}}\fr{4L_{\eta}\widetilde{\log}_{k}}{\sig_{\min}\rbr{A(\lambda''_k, \Gamma)}}\fr{N_{k,0,L_{k}}}{N_{k,0,L_{k}}+N_{k,1L_k}}\vcn{w-w'}^2_{A(\xi_{L_{k}}, \Gamma)^{-1}} \nn\\
\le&\fr{1}{N_{k,0,L_{k}}}\fr{4L_{\eta}\widetilde{\log}_{k,L_{k}}}{\sig_{\min}\rbr{A(\alpha^*_k\lambda_E, \Gamma)}}\fr{N_{k,0,L_{k}}}{N_{k,0,L_{k}}+N_{k,1,L_k}}\vcn{w-w'}^2_{A(\xi_{L_{k}}, \Gamma)^{-1}} \nn\\
\le&\fr{1}{N_{k,0,L_{k}}}\fr{4L_{\eta}\widetilde{\log}_{k,L_{k}}}{\sig_{\min}\rbr{A(\lambda_E, \Gamma)}}\vcn{w-w'}^2_{A(\xi_{L_{k}}, \Gamma)^{-1}} \tag{set $\alpha^*_k=\alpha_{k}$} \nn\\
\stackrel{b_{1}}{\le}&\fr{1}{g}\vcn{w-w'}^2_{A(\xi_{L_{k}}, \Gamma)^{-1}} \nn\\
\stackrel{b_{2}}{\le}&\fr{1}{g}\vcn{w-w'}^2_{A(\xi_{L_{k}}, \widehat{\Gamma}^{L_{k}})^{-1}},  \label{ieq:b16}
\end{align}

where for $(b_{1})$, we have $N_{k,0,L_{k}}\ge \fr{4gL_{\eta}\widetilde{\log}_{k,L_{k}}}{\sig_{\min}\rbr{A(\lambda_E, \Gamma)}}$, and $(b_{2})$ is due to <ref>. Plug (<ref>) into (<ref>), we have

\begin{align}
\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\hat{\lambda}_{k}, \widehat{\Gamma}^{L_{k}})^{-1}}\le&6\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}+\fr{2}{g}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\xi_{L_{k}}, \widehat{\Gamma}^{L_{k}})^{-1}}\nn\\
\le&6\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}+\fr{2}{g}\fr{\zeta^2_{k}}{\vcn{\theta}^2_2L_{\eta}\widetilde{\log}_{k,L_{k}}}(N_{k,0,L_{k}}+N_{k,1,L_k}), \label{ieq:b17}
\end{align}

where the last inequality is due to (<ref>). According to the algorithm design, the number of samples in the second sub-phase of phase $k$ is defined as

\begin{align*}
N_{k,2}=\ur{2(1+\omega)\zeta_k^{-2}\rho(\mc{W}_k)L_{\nu}\log\rbr{\fr{4k^2\abr{\mc{W}}}{\delta}}}\vee r(\omega),
\end{align*}

with $\rho(\mc{W}_k)=\min_{\lambda\in\Delta(\mc{Z})}\max_{w,w'\in\mc{W}_k}\|w-w'\|^2_{A(\lambda, \widehat{\Gamma}^{L_{k}})^{-1}}$. Then we have, by setting $g\ge4$,

\begin{align*}
N_{k,2}\lessapprox(1+\omega)\zeta_k^{-2}L_{\nu}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}\log\rbr{\fr{4k^2\abr{\mc{W}}}{\delta}}+(1+\omega)(N_{k,0,L_{k}}+N_{k,1,L_k}),
\end{align*}

where '$\lessapprox$' hides logarithmic factors of $\abr{\mc{W}}$ for the second term and constants for simplicity. Plug (<ref>) into the above inequality. Also note that by <ref>, we can always set $L_{\nu}=2(\vcn{\theta}^2_2L_{\eta}+1)$.

\begin{align*}
\sum_{k=1}^{K^*} N_{k,2}\lessapprox&(1+\omega)\sum_{k=1}^{K^*}\zeta_k^{-2}L_{\nu}\max_{w,w'\in\mc{W}_k}\vcn{w-w'}^2_{A(\lambda^*_k, \Gamma)^{-1}}\log\rbr{\fr{4k^2\abr{\mc{W}}}{\delta}}+(1+\omega)\sum_{k=1}^{K^*}(N_{k,0,L_{k}}+N_{k,1,L_k}) \\
\lessapprox&(1+\omega)K^*L_{\nu}\rho^*\log\rbr{\fr{4K^{*2}\abr{\mc{W}}}{\delta}}+(1+\omega)\sum_{k=1}^{K^*}(N_{k,0,L_{k}}+N_{k,1,L_k}). \label{sample complexity 2}
\end{align*}

This essentially means that the sample complexity for the second sub-phase $\sum N_{k,2}$ can be upper bounded by summation of the sample complexity we pay for Algorithm <ref> and the sample complexity of the first sub-phase $\sum_{k=1}^{K^*}(N_{k,0,L_{k}}+N_{k,1,L_k})$. Combine (<ref>) and (<ref>), we conclude the result.

\begin{align*}
\widetilde{\log}\rbr{N_{k,0},\delta_{k,0}}=8d \ln\del{1 + \fr{N_{k,0}L_z^2}{d} } + 16\ln\del{\fr{2\cd6^d}{\dt}}.
\end{align*}

A sufficient condition for

\begin{align}
N_{k,0,\ell}\ge \fr{g\sigma_{\eta}^2\widetilde{\log}\rbr{N_{k,0,\ell}+N_{k,1,\ell},\delta_{k,\ell}}}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\vee r(\omega).
\end{align}

to hold is

\begin{align*}
N_{k,0,\ell}\ge \fr{16gd\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\ln\rbr{\fr{8g}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\rbr{d+N_{k,1,\ell}L_z^2+L_z^2} }+\fr{32g\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\ln\rbr{\fr{2\cd6^d}{\dt}}.
\end{align*}

\begin{align*}
\widetilde{\log}\rbr{N_{k,0,\ell}+N_{k,1,\ell},\delta_{k,\ell}}=8d \ln\del{1 + \fr{(N_{k,0,\ell}+N_{k,1,\ell})L_z^2}{d} } + 16\ln\del{\fr{2\cd6^d}{\dt}}.
\end{align*}

By <ref>, for the formula

\begin{align*}
X\ge A\ln\del{D+BX}+C
\end{align*}

we have

* $A=\fr{8gd\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}$,

* $B=\fr{L_z^2}{d}$,

* $C=\fr{16g\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\ln\del{\fr{2\cd6^d}{\dt}}$,

* $D=1+\fr{N_{k,1,\ell}L_z^2}{d}$.

Thus a sufficient condition for the inequality to hold is

\begin{align*}
N_{k,0,\ell}\ge &\fr{16gd\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\ln\rbr{\fr{8gd\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\rbr{1+\fr{N_{k,1,\ell}L_z^2}{d}+\fr{L_z^2}{d}} }+\fr{32g\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\ln\rbr{\fr{2\cd6^d}{\dt}}\\
=&\fr{16gd\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\ln\rbr{\fr{8g\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\rbr{d+N_{k,1,\ell}L_z^2+L_z^2} }+\fr{32g\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda_E, \Gamma)}}\ln\rbr{\fr{2\cd6^d}{\dt}}.
\end{align*}

Let $X\ge1, A, B\ge0$, then a sufficient condition for $X\ge A\ln\del{D+BX}+C$ is

\begin{align*}
X\ge 2A\ln\rbr{AD+AB}+2C.
\end{align*}

The proof is motivated by Gales et al., 2022. Let $f\in(0,1)$, then

\begin{align*}
&X\ge A\ln\del{D+BX}+C\\
\Leftrightarrow&X\ge A\ln\rbr{\fr{fX}{A}}+A\ln\rbr{\fr{A}{f}\rbr{\fr{D}{X}+B}}+C\\
\Leftarrow&X\ge A\rbr{\fr{fX}{A}-1}+A\ln\rbr{\fr{A}{f}\rbr{\fr{D}{X}+B}}+C \tag{since $\ln(x)\le x-1$}\\
\Leftarrow&X(1-f)\ge A\ln\rbr{\fr{A}{2f}\rbr{\fr{D}{X}+B}}+C\\
\Leftrightarrow&X\ge \fr{1}{1-f}A\ln\rbr{\fr{A}{2f}\rbr{\fr{D}{X}+B}}+\fr{c}{1-f}.
\end{align*}

Set $f=1/2$ and by the fact $X\ge1$, we have

\begin{align*}
X\ge 2A\ln\rbr{AD+AB}+2C.
\end{align*}

Suppose that we have a data set $\cbr{Z_T, X_T}$. Denote the empirical distribution of $Z_T$ as $\xi$. The number of samples satisfies

\begin{align*}
T\ge\fr{8\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\xi, \Gamma)}}\overline{\log}\rbr{Z_T,\delta}\vee r(\omega).
\end{align*}

$\widehat{\Gamma}$ is the OLS estimate of $\Gamma$ based on $\cbr{Z_T, X_T}$. Then

\begin{align*}
\vcn{w}^2_{A(\xi, \Gamma)^{-1}}\le 6\vcn{w}^2_{A(\xi, \widehat{\Gamma})^{-1}}.
\end{align*}

By <ref>, we have

\begin{align*}
\vcn{w}^2_{A(\xi, \Gamma)^{-1}}\le&3\vcn{w}^2_{A(\xi, \widehat{\Gamma})^{-1}} + 2\vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})w}^2_{A(\xi, I)^{-1}}\\
\le&3\vcn{w}^2_{A(\xi, \widehat{\Gamma})^{-1}} + \fr{1}{2}\vcn{w}^2_{A(\xi, \Gamma)^{-1}},
\end{align*}

where the last inequality is due to <ref> with $g=2$. Rearranging the terms, we have

\begin{align*}
\vcn{w}^2_{A(\xi, \Gamma)^{-1}}\le6\vcn{w}^2_{A(\xi, \widehat{\Gamma})^{-1}}.
\end{align*}

Suppose that we use ROUND to sample $N_{0}$ arms according to $\lambda_E$ denoted as $Z_0$, and $N_{1}$ arms according to $\lambda_1$ denoted as $Z_1$, with $N_{1}\ge N_{0}$. Denote the empirical distribution of all the collected samples as $\xi$, then

\begin{align*}
\vcn{w}^2_{A(\xi,\Gamma)}\le4\vcn{w}^2_{A(\lambda_1, \Gamma)^{-1}}.
\end{align*}

Denote the empirical distribution of $Z_0$ as $\xi_0$, and the empirical distribution of $Z_1$ as $\xi_1$, then we have

\begin{align*}
\vcn{w}^2_{\bar{A}(Z_{0}\cup Z_{1}, \Gamma)^{-1}}=&w^\top\rbr{\sum_{z\in Z_{0}\cup Z_{1}}\Gamma^{\top}zz^{\top}\Gamma}^{-1}w\\
=&w^\top\rbr{\sum_{z\in Z_{0}}\Gamma^{\top}zz^{\top}\Gamma+\sum_{z\in Z_{1}}\Gamma^{\top}zz^{\top}\Gamma}^{-1}w\\
=&w^\top\rbr{N_{0}\sum_{z\in \mc{Z}}\xi_{z,0}\Gamma^{\top}zz^{\top}\Gamma+N_{1}\sum_{z\in \mc{Z}}\xi_{z,1}\Gamma^{\top}zz^{\top}\Gamma}^{-1}w\\
=&\fr{1}{N_{0}+N_{1}}w^\top\rbr{\fr{N_{0}}{N_{0}+N_{1}}\sum_{z\in \mc{Z}}\xi_{z,0}\Gamma^{\top}zz^{\top}\Gamma+\fr{N_{1}}{N_{0}+N_{1}}\sum_{z\in \mc{Z}}\xi_{z,1}\Gamma^{\top}zz^{\top}\Gamma}^{-1}w\\
\le&\fr{1}{N_{0}+N_{1}}w^\top\rbr{\fr{N_{1}}{N_{0}+N_{1}}\sum_{z\in \mc{Z}}\xi_{z,1}\Gamma^{\top}zz^{\top}\Gamma}^{-1}w\\
\le&\fr{2}{N_{0}+N_{1}}w^\top\rbr{\sum_{z\in \mc{Z}}\xi_{z,1}\Gamma^{\top}zz^{\top}\Gamma}^{-1}w \tag{$N_{1}\ge N_{0}$}\\
\le&\fr{4}{N_{0}+N_{1}}w^\top\rbr{\sum_{z\in \mc{Z}}\lambda_{1}\Gamma^{\top}zz^{\top}\Gamma}^{-1}w\\
=&\fr{4}{N_{0}+N_{1}}\vcn{w}^2_{A(\lambda_1, \Gamma)^{-1}}.
\end{align*}

The result follows by noting that

\begin{align*}
\vcn{w}^2_{\bar{A}(Z_{0}\cup Z_{1}, \Gamma)^{-1}}=\fr{1}{N_{0}+N_{1}}\vcn{w}^2_{A(\xi,\Gamma)}.
\end{align*}

Suppose that we have an estimate $\widehat{\Gamma}$ that is invertible, for any $x\in\mathbb{R}^d$ and covariance matrix $V$, we have

\begin{align}
\vcn{x}^2_{(\Gamma^\top V \Gamma)^{-1}}
&\leq 3 \vcn{x}^2_{(\widehat{\Gamma}^\top V \widehat{\Gamma})^{-1}} + 2 \vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}^2_{V^{-1}}.
\end{align}

Suppose we have an estimate $\widehat{\Gamma}$.

\begin{align*}
\vcn{x}^2_{(\Gamma^\top V\Gamma)^{-1}}
&= \vcn{x}^2_{(\widehat{\Gamma}^\top V\widehat{\Gamma})^{-1}} + \vcn{x}^2_{(\Gamma^\top V\Gamma)^{-1}} - \vcn{x}^2_{(\widehat{\Gamma}^\top V\widehat{\Gamma})^{-1}}.
\end{align*}

Note that

\begin{align*}
(\Gamma^\top V \Gamma)^{-1} - (\widehat{\Gamma}^\top V \widehat{\Gamma})^{-1}
&= \Gamma^{-1} V^{-1} \Gamma^{-\top} - \widehat{\Gamma}^{-1} V^{-1} \widehat{\Gamma}^{-\top}
\\&= \Gamma^{-1} V^{-1} \Gamma^{-\top} - \widehat{\Gamma}^{-1} V^{-1} \widehat{\Gamma}^{-\top} + \Gamma^{-1} V^{-1} \widehat{\Gamma}^{-\top} - \Gamma^{-1} V^{-1} \widehat{\Gamma}^{-\top}
\\&= \Gamma^{-1} V^{-1} (\Gamma^{-\top} - \widehat{\Gamma}^{-\top}) + (\Gamma^{-1} - \widehat{\Gamma}^{-1})V^{-1} \widehat{\Gamma}^{-\top}.
\end{align*}

\begin{align*}
\vcn{x}^2_{(\Gamma^\top V \Gamma)^{-1}}
&= \vcn{x}^2_{(\widehat{\Gamma}^\top V \widehat{\Gamma})^{-1}} + x^\top \Gamma^{-1} V^{-1} (\Gamma^{-\top} - \widehat{\Gamma}^{-\top}) x + x^\top (\Gamma^{-1} - \widehat{\Gamma}^{-1}) V^{-1} \widehat{\Gamma}^{-\top} x
\\&\leq \vcn{x}^2_{(\widehat{\Gamma}^\top V \widehat{\Gamma})^{-1}} + \vcn{x}_{(\Gamma^\top V \Gamma)^{-1}} \vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}_{V^{-1}} + \vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}_{V^{-1}}\vcn{x}_{(\widehat{\Gamma}^\top V \widehat{\Gamma})^{-1}}
\\&\leq \vcn{x}^2_{(\widehat{\Gamma}^\top V \widehat{\Gamma})^{-1}} + \frac{1}{2}\vcn{x}^2_{(\Gamma^\top V \Gamma)^{-1}} +  \frac{1}{2}\vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}^2_{V^{-1}} + \frac{1}{2}\vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}^2_{V^{-1}} + \frac{1}{2}\vcn{x}^2_{(\widehat{\Gamma}^\top V \widehat{\Gamma})^{-1}}\tag{AM-GM}.
\end{align*}

This implies that

\begin{align*}
\vcn{x}^2_{(\Gamma^\top V \Gamma)^{-1}}
&\leq 3 \vcn{x}^2_{(\widehat{\Gamma}^\top V \widehat{\Gamma})^{-1}} + 2 \vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}^2_{V^{-1}}.\label{ieq:GammaVShat1}
\end{align*}

Suppose $\lambda_f=\arg\min f(\lambda)$ and $\lambda_g=\arg\min g(\lambda)$ and $f(\lambda)\le g(\lambda)+h(\lambda)$, then

\begin{align*}
f(\lambda_f)\le g(\lambda_g)+h(\lambda_g).
\end{align*}

\begin{align*}
f(\lambda_f)\le \min_{\lambda}\rbr{g(\lambda)+h(\lambda)}\le g(\lambda_g)+h(\lambda_g).
\end{align*}

Define $\lambda_z^*$ and $\tilde{\lambda}_z$

\begin{align*}
\lambda_z^*:=\arg\min_{\lambda\in\Delta(\mc{Z})}\max_{w,w'\in\mc{W}} \vcn{w-w'}^2_{A(\lambda_z, \Gamma)^{-1}},
\end{align*}

\begin{align*}
\tilde{\lambda}_z:=\arg\min_{\lambda\in\Delta(\mc{Z})}\max_{w,w'\in\mc{W}}\vcn{w-w'}^2_{A(\lambda_z, \widehat{\Gamma})^{-1}}
\end{align*}

as the optimal design regarding $\Gamma$ and that regarding its estimate $\widehat{\Gamma}$ respectively. Then, we have

\begin{align*}
\max_{w,w'\in\mc{W}}\vcn{w-w'}^2_{A(\tilde{\lambda}_z, \widehat{\Gamma})^{-1}}\leq \max_{w,w'\in\mc{W}}3 \vcn{w-w'}^2_{A(\lambda_z^*, \Gamma)^{-1}} + \max_{w,w'\in\mc{W}}2 \vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda_z^*zz^\top}^{-1}}.
\end{align*}

By Lemma <ref>, for any $w,w'\in\mc{W}$ and $\lambda_z\in\Delta_{\mc{Z}}$,

\begin{align*}
\vcn{w-w'}^2_{A(\lambda_z, \widehat{\Gamma})^{-1}}\leq 3 \vcn{w-w'}^2_{A(\lambda_z, \Gamma)^{-1}} + 2 \vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda_zzz^\top}^{-1}}.
\end{align*}

\begin{align*}
\max_{w,w'\in\mc{W}}\vcn{w-w'}^2_{A(\lambda_z, \widehat{\Gamma})^{-1}}\leq \max_{w,w'\in\mc{W}}3 \vcn{w-w'}^2_{A(\lambda_z, \Gamma)^{-1}} + \max_{w,w'\in\mc{W}}2 \vcn{(\Gamma^{-\top} - \widehat{\Gamma}_k^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda_zzz^\top}^{-1}}.
\end{align*}

By <ref>,

\begin{align*}
\max_{w,w'\in\mc{W}}\vcn{w-w'}^2_{A(\tilde{\lambda}_z, \widehat{\Gamma})^{-1}}\leq \max_{w,w'\in\mc{W}}3 \vcn{w-w'}^2_{A(\lambda_z^*, \Gamma)^{-1}} + \max_{w,w'\in\mc{W}}2 \vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})\rbr{w-w'}}^2_{\rbr{\sum_{z}\lambda_z^*zz^\top}^{-1}}.
\end{align*}

Suppose that we have $\widehat{\Gamma}$ that is an OLS estimate from an offline dataset $\cbr{Z_{T_1}, X_{T_1}}$ collected non-adaptively through a fixed design $\lambda$ and the efficient rounding procedure $\text{ROUND}$. Let $V=Z_{T_1}^\top Z_{T_1}$. Then, for any $x\in\mathbb{R}^d$ and $g\ge1$, we have, with probability $1-\delta$,

\begin{align*}
\vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}^2_{V^{-1}}\le\fr{1}{g}\vcn{x}^2_{\bar{A}(Z_{_{T_1}}, \Gamma)^{-1}},
\end{align*}

\begin{align}
T_1\ge\fr{4g\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda, \Gamma)}}\overline{\log}\rbr{Z_{T_1},\delta}\vee2p,
\end{align}

where $p$ is the cardinality of support of $\lambda$.

We first show that

\begin{align*}
&\vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}^2_{V^{-1}}\\
=&\vcn{\Gamma^{-\top} S^\top Z_{T_1} V^{-1} (\Gamma + V^{-1} Z_{T_1}^\top S)^{-\top}x}^2_{V^{-1}}\tag{Lemma \ref{lem:estimateGamma inverse}}\\
\stke{1}&\vcn{V^{-\fr{1}{2}}\Gamma^{-\top} S^\top Z_{T_1} V^{-1} (\Gamma + V^{-1} Z_{T_1}^\top S)^{-\top}x}^2_{2}\tag{$\vcn{Ax}_{V}^2=\vcn{V^{\fr{1}{2}}Ax}^2_2$}\\
\le&\opn{V^{-\fr{1}{2}}\Gamma^{-\top} S^\top Z_{T_1} V^{-\fr{1}{2}} }^2\vcn{V^{-\fr{1}{2}}(\Gamma + V^{-1} Z_{T_1}^\top S)^{-\top}x}^2_2\tag{$\vcn{Ax}\le\vcn{A}_{\mathrm{op}}\vcn{x}$}\\
\le&\opn{V^{-\fr{1}{2}}\Gamma^{-\top}}^2\opn{S^\top Z_{T_1} V^{-\fr{1}{2}} }^2\vcn{V^{-\fr{1}{2}}(\Gamma + V^{-1} Z_{T_1}^\top S)^{-\top}x}^2_2\tag{$\opn{AB}\le\opn{A}\opn{B}$}\\
=&\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}_{\mathrm{op}}^2\vcn{V^{-1/2}\rbr{\Gamma+V^{-1}Z_{T_1}^\top S}^{-\top}x}^2_2\tag{$\opn{A^\top A}=\opn{A}^2$}\\
=&\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}^2_{\mathrm{op}}\vcn{V^{-1/2}\Gamma^{-\top}x-V^{-1/2}\Gamma^{-\top}\rbr{V^{-1}Z_{T_1}^\top S}^{\top}\rbr{\Gamma+V^{-1}Z_{T_1}^\top S}^{-\top}x}^2_2\tag{Lemma \ref{lem:(A+B)^{-1}}: $\rbr{A+B}^{-1}
=A^{-1} - \rbr{A+B}^{-1} B A^{-1}$}\\
\stkl{2}&\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}_{\mathrm{op}}^2\rbr{\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2+\vcn{V^{-1/2}\Gamma^{-\top}\rbr{V^{-1}Z_{T_1}^\top S}^{\top}\rbr{\Gamma+V^{-1}Z_{T_1}^\top S}^{-\top}x}^2_2}.
\end{align*}

We can upper bound the the term $\vcn{V^{-1/2}\Gamma^{-\top}\rbr{V^{-1}Z_{T_1}^\top S}^{\top}\rbr{\Gamma+V^{-1}Z_{T_1}^\top S}^{-\top}x}^2_2=:\mathfrak{V}$ by noticing that it appears in both of $a_1,a_2$ above. Thus we have the inequality

\begin{align*}
\mathfrak{V}\le \vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}_{\mathrm{op}}^2\rbr{\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2+\mathfrak{V}}.
\end{align*}

By rearranging the terms, we have

\begin{align*}
\mathfrak{V}\le \fr{1}{1-\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}_{\mathrm{op}}^2}\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}_{\mathrm{op}}^2\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2.
\end{align*}

By <ref>, with probability $1-\delta$, we have

\begin{align*}
\vcn{V^{-1/2}Z_{T_1}^\top S}_{\text{op}}^2\le\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta}.
\end{align*}

Thus, with probability $1-\delta$, we have

\begin{align*}
\mathfrak{V}\le \fr{1}{1-\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta}}\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta}\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2.
\end{align*}

To further upper bound $\mathfrak{V}$, we first find a sufficient condition on $T_1$ such that $\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta}\le\fr{1}{2g}$, $g\ge1$.
By <ref>, when $T_1\ge2p$,

\begin{align*}
\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta}\le\fr{2\sigma_{\eta}^2}{T_1\sigma_{\min}\rbr{\sum_{z\in \mathcal{Z}}\lambda_z \Gamma^{\top} zz^{\top}\Gamma}}\overline{\log}\rbr{Z_{T_1},\delta}.
\end{align*}

To upper bound the right hand side by $\fr{1}{2g}$, we need

\begin{align}
T_1\ge\fr{4g\sigma_{\eta}^2}{\sigma_{\min}\rbr{\sum_{z\in \mathcal{Z}}\lambda_z \Gamma^{\top} zz^{\top}\Gamma}}\overline{\log}\rbr{Z_{T_1},\delta}.\label{ieq:T1 condition}
\end{align}

With this condition (<ref>), we have with probability $1-\delta$,

\begin{align}
\mathfrak{V}\le&\fr{1}{1-\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta}}\vcn{\Gamma^{-1}V^{-1}\Gamma^{-\top}}_{\mathrm{op}}\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta}\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2\nn\\
\le& \fr{1}{1-\fr{1}{2g}}\fr{1}{2g}\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2\nn\\
\le&\fr{1}{g}\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2. \label{ieq:frakV}
\end{align}

Suppose that we have $\widehat{\Gamma}$ that is an OLS estimate from an offline dataset $\cbr{Z_{T_1}, X_{T_1}}$ collected non-adaptively through a fixed design $\lambda$ and the efficient rounding procedure $\text{ROUND}$. Let $\dot{V}$ be any positive definite matrix. Then, for any $x\in\mathbb{R}^d$, we have, with probability $1-\delta$,

\begin{align*}
\vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}^2_{\dot{V}^{-1}}\le2\vcn{\Gamma^{-1}\dot{V}^{-1}\Gamma^{-\top}}_{\mathrm{op}}\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta}\vcn{x}^2_{\bar{A}(Z_{_{T_1}}, \Gamma)^{-1}},
\end{align*}

\begin{align*}
T_1\ge\fr{4\sigma_{\eta}^2}{\sigma_{\min}\rbr{A(\lambda, \Gamma)}}\overline{\log}\rbr{Z_{T_1},\delta}\vee2p,
\end{align*}

where $p$ is the cardinality of support of $\lambda$.

\begin{align*}
&\vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}^2_{\dot{V}^{-1}}\\
=&\vcn{\Gamma^{-\top} S^\top Z_{T_1} V^{-1} (\Gamma + V^{-1} Z_{T_1}^\top S)^{-\top}x}^2_{\dot{V}^{-1}}\tag{Lemma \ref{lem:estimateGamma inverse}}\\
\stke{1}&\vcn{\dot{V}^{-\fr{1}{2}}\Gamma^{-\top} S^\top Z_{T_1} V^{-1} (\Gamma + V^{-1} Z_{T_1}^\top S)^{-\top}x}^2_{2}\tag{$\vcn{Ax}_{V}^2=\vcn{V^{\fr{1}{2}}Ax}^2_2$}\\
\le&\opn{\dot{V}^{-\fr{1}{2}}\Gamma^{-\top} S^\top Z_{T_1} V^{-\fr{1}{2}} }^2\vcn{V^{-\fr{1}{2}}(\Gamma + V^{-1} Z_{T_1}^\top S)^{-\top}x}^2_2\tag{$\vcn{Ax}\le\vcn{A}_{\mathrm{op}}\vcn{x}$}\\
\le&\opn{\dot{V}^{-\fr{1}{2}}\Gamma^{-\top}}^2\opn{S^\top Z_{T_1} V^{-\fr{1}{2}} }^2\vcn{V^{-\fr{1}{2}}(\Gamma + V^{-1} Z_{T_1}^\top S)^{-\top}x}^2_2\tag{$\opn{AB}\le\opn{A}\opn{B}$}\\
=&\vcn{\Gamma^{-1}\dot{V}^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}_{\mathrm{op}}^2\vcn{V^{-1/2}\rbr{\Gamma+V^{-1}Z_{T_1}^\top S}^{-\top}x}^2_2\tag{$\opn{A^\top A}=\opn{A}^2$}\\
=&\vcn{\Gamma^{-1}\dot{V}^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}^2_{\mathrm{op}}\vcn{V^{-1/2}\Gamma^{-\top}x-V^{-1/2}\Gamma^{-\top}\rbr{V^{-1}Z_{T_1}^\top S}^{\top}\rbr{\Gamma+V^{-1}Z_{T_1}^\top S}^{-\top}x}^2_2\tag{Lemma \ref{lem:(A+B)^{-1}}: $\rbr{A+B}^{-1}
=A^{-1} - \rbr{A+B}^{-1} B A^{-1}$}\\
\stkl{2}&\vcn{\Gamma^{-1}\dot{V}^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}_{\mathrm{op}}^2\rbr{\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2+\vcn{V^{-1/2}\Gamma^{-\top}\rbr{V^{-1}Z_{T_1}^\top S}^{\top}\rbr{\Gamma+V^{-1}Z_{T_1}^\top S}^{-\top}x}^2_2}.
\end{align*}

Given the condition (<ref>) holds, we have with probability $1-\delta$,

\begin{align*}
&\vcn{(\Gamma^{-\top} - \widehat{\Gamma}^{-\top})x}^2_{\dot{V}^{-1}}\\
\stkl{1}&\vcn{\Gamma^{-1}\dot{V}^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}_{\mathrm{op}}^2\rbr{\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2+\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2}\\
=&2\vcn{\Gamma^{-1}\dot{V}^{-1}\Gamma^{-\top}}_{\mathrm{op}}\vcn{V^{-1/2} Z_{T_1}^\top S}_{\mathrm{op}}^2\vcn{V^{-1/2}\Gamma^{-\top}x}^2_2\\
\le&2\vcn{\Gamma^{-1}\dot{V}^{-1}\Gamma^{-\top}}_{\mathrm{op}}\sigma_{\eta}^2\overline{\log}\rbr{Z_{T_1},\delta}\vcn{x}^2_{(\Gamma^\top V \Gamma)^{-1}},
\end{align*}

where $(a_1)$ is due to (<ref>) and setting $g=1$.

For a least square estimate $\widehat{\Gamma}$ that is estimated through a design matrix $Z$ and $\widehat{\Gamma}$ is invertible, we have

\begin{align*}
\widehat{\Gamma}^{-1}-\Gamma^{-1}=-\rbr{\Gamma+V^{-1}Z^\top S}^{-1}V^{-1}Z^\top S\Gamma^{-1}.
\end{align*}

Since $\widehat{\Gamma}$ is a least square estimator, we have

\begin{align*}
\widehat{\Gamma}=\Gamma+V^{-1}Z^\top S.
\end{align*}

By Lemma <ref>, we have

\begin{align*}
\widehat{\Gamma}^{-1}-\Gamma^{-1}=&\rbr{\Gamma+V^{-1}Z^\top S}^{-1} - \Gamma^{-1}\\
=&-\rbr{\Gamma+V^{-1}Z^\top S}^{-1}V^{-1}Z^\top S\Gamma^{-1}.
\end{align*}

For two invertible matrixes $A, B\in\mathbb{R}^{d\times d}$, we have

\begin{align*}
\rbr{A+B}^{-1}
&=A^{-1} - \rbr{A+B}^{-1} B A^{-1}.
\end{align*}

We have

\begin{align*}
\rbr{A+B}^{-1}
&= A^{-1} + \rbr{A+B}^{-1} - A^{-1} \notag
\\&= A^{-1} + \rbr{\rbr{A+B}^{-1} A - I} A^{-1} \notag
\\&= A^{-1} + \rbr{A+B}^{-1}\rbr{A - \rbr{A+B}} A^{-1} \notag
\\&= A^{-1} - \rbr{A+B}^{-1} B A^{-1}.
\end{align*}

Suppose that we have a design matrix $Z_T$ that is sampled from a distribution $\lambda\in\Delta_{\mc{Z}}$, with the efficient rounding procedure ROUND. Let $p$ represent the cardinality of support of $\lambda$. We have, if $T\ge2p$,

\begin{align*}
\opn{\rbr{\Gamma^\top Z_T^\top Z_T\Gamma}^{-1}}\le\fr{2}{T\sigma_{\min}\rbr{\sum_{z\in \mathcal{Z}}\lambda_z \Gamma^{\top} zz^{\top}\Gamma}}.
\end{align*}

where $\sigma_{\min}\rbr{\cdot}$ is the smallest singular value of a matrix.

Suppose that each arm $z\in\mc{Z}$ is sampled $t_z$ times, the empirical distribution of $Z_T$ is $\xi:=\rbr{\fr{t_z}{T}}_{z\in\mc{Z}}$. Thus, we have

\begin{align*}
\opn{\rbr{\Gamma^\top Z_T^\top Z_T\Gamma}^{-1}}&=\fr{1}{\sigma_{\min}\rbr{\Gamma^\top Z_T^\top Z_T\Gamma}}\\
&=\fr{1}{\sigma_{\min}\rbr{T\sum_{z\in \mathcal{Z}}\xi_z \Gamma^{\top} zz^{\top}\Gamma}}\\
&=\fr{1}{T\sigma_{\min}\rbr{\sum_{z\in \mathcal{Z}}\xi_z \Gamma^{\top} zz^{\top}\Gamma}}.
\end{align*}

By <cit.>, we have

\begin{align*}
\sum_{z\in \mathcal{Z}}\xi_z \Gamma^{\top} zz^{\top}\Gamma\succeq\alpha\sum_{z\in \mathcal{Z}}\lambda_z \Gamma^{\top} zz^{\top}\Gamma,
\end{align*}

where $\alpha\in[\fr{T}{T+2p},1]$ when $T\ge2p$. Given the fact that both of $\sum_{z\in \mathcal{Z}}\xi_z \Gamma^{\top} zz^{\top}\Gamma$ and $\sum_{z\in \mathcal{Z}}\lambda_z \Gamma^{\top} zz^{\top}\Gamma$ are positive definite, we have $\sigma_{\min}\rbr{\sum_{z\in \mathcal{Z}}\xi_z \Gamma^{\top} zz^{\top}\Gamma}\ge\alpha\sigma_{\min}\rbr{\sum_{z\in \mathcal{Z}}\lambda_z \Gamma^{\top} zz^{\top}\Gamma}$. Thus, we have

\begin{align*}
\opn{\rbr{\Gamma^\top Z_T^\top Z_T\Gamma}^{-1}}\le\fr{1}{\alpha T\sigma_{\min}\rbr{\sum_{z\in \mathcal{Z}}\lambda_z \Gamma^{\top} zz^{\top}\Gamma}}.
\end{align*}

When $T\ge2p$, we have $\alpha\ge1/2$, which implies the result.

§ ESTIMATING

In this section, we introduce a simple adaptive procedure that finds a high probability lower bound on $\gammin^* := \lammin(\Gam)$ that is sufficiently accurate (i.e., within a constant factor of $\gammin^*$).
For simplicity, we assume $\|z_t\|\le 1, \forall t$ in this section.

Our algorithm leverages confidence bounds to adaptively determine how many samples we like to take.
Let $\hGam_t := (Z^\T Z)^{-1} Z^\T X$ be the least square estimate of $\Gam$ after sampling $t$ times to obtain $\{(z_s, x_s)\}_{s=1}^t$ where $Z \in \RR^{t\times d}$ and $X \in \RR^{t \times d}$ are the design matrices.
Let $V_t := \sum_{s=1}^t z_s z_s^\T$.
We define the lower and upper confidence bound for $\gammin^*$ as follows:

\begin{align*}
\LCB(t) := \lammin(\hGam_t) - \sqrt{\fr{\psi_t}{t} },~~~~~
\UCB(t) := \lammin(\hGam_t)  + \sqrt{\fr{\psi_t}{t} }
\end{align*}

\begin{align*}
\psi_t = \sigmin^{-1}\del[2]{\fr1t V_t} \cd \del[4]{8d \ln\del{1 + \fr{2 t }{d(2\wed \sigmin(V_t))} } + 16\ln\del{\fr{2\cd6^d}{\dt}\cd \log^2_2\del{\fr{4}{2\wed \sigmin(V_t)} }  } }~.
\end{align*}

and $\LCB(0) := -\infty$ and $\UCB(0) := \infty$.

The following lemma shows that $\LCB(t)$ and $\UCB(t)$ form a valid anytime confidence bound for $\gammin^*$.

(Correctness of the confidence bounds)

\begin{align*}
1-\dt \le \PP(\forall t\ge1, \LCB(t) \le  \gammin^* \le \UCB(t))
\end{align*}

Equipped with the confidence bounds, we are now ready to describe our algorithm for learning $\gammin^*$ (see <ref>).
Since the tightness of the confidence bounds depends on the smallest eigenvalue of $V_t$, it is natural to use the E-optimal design as defined in <ref>.
Recall that the solution of the E-optimal design is $\lam_E^*$ and $\kappa_0$ is the smallest singular value achieved by $\lam_E^*$.
We take in a rounding procedure for the E-optimal design $\text{ROUND}_E(\lam, t)$ that takes in $t$ samples and design $\lam$ and outputs integer sample count assignments $\{N_z\}_{z\in\cZ}$ so that if we sample according to these counts then we have

\begin{align}\label{eq:rounding-guarantee}
\sigmin^{-1}(\fr1t V_t) \le (1+\omega)\kappa_0^{-1}
\end{align}

After determining the base sample counts $\{m_z\}_{z\in\cZ}$ by $\text{ROUND}(\lam^*_E, \lcl r(\omega) \rcl, \omega)$, we start doubling the sample size until we satisfy the condition $\LCB(t) > \fr12 \UCB(t)$.
Note that the sampling scheme in the while loop is designed such that the total number of samples collected up to (and including) $j$-th iteration is $2^{j-1} \lcl r(\omega) \rcl$.
Once the loop stops, we return $\LCB(t)$ as the claimed lower approximation of the $\gammin^*$.

Learning $\lammin(\Gam)$

Input: Arm set $\cZ$, rounding procedure $\text{ROUND}_E$ for the E-optimal design, rounding accuracy $\omega$
Initialize: $j = 1$, $t=0$.
Compute the E-optimal design $\lam^*_E$ for $\cZ$.
Compute $\{m_z\}_{z\in \cZ}$ by $\text{ROUND}_E(\lam^*_E, \lcl r(\omega) \rcl)$.
$\LCB(t) \le \fr12 \UCB(t)$
$t \larrow 2^{j-1} \lcl r(\omega) \rcl$.
For each arm $z\in\cZ$, sample $2^{j-1}m_z - \onec{j \neq 1} 2^{j-2}m_z$ times.
Estimate $\hGam_t$ using all samples collected so far (total $t$ data points)
$j \larrow j + 1$.
Output: $\LCB(t)$

Let $N_w$ be the total number of samples we used in <ref>.
Then, the next theorem shows that the estimate returned by our algorithm is both a valid lower bound to $\gammin^*$ and sufficiently accurate.

(Correctness of <ref>)
The total number of samples denoted by $N_w$ used in <ref> satisfies that, with probability at least $1-\dt$,

\begin{align*}
\fr{\gammin^*}{2} < \LCB(N_w) \le \gammin^*
\end{align*}

We next analyze the sample complexity of the algorithm, which essentially shows the scaling of $\frac{1}{(\gammin^*)^{2} \kappa_0}$ even if the algorithm does not need knowledge of $\gammin^*$.

(Sample complexity of <ref>) Then, with $\omega = 1$, we have, with probability at least $1-\dt$,

\begin{align*}
N_w = O\del{r(1) + (\gammin^*)^{-2} \kappa_0^{-1} \cd \del{d \cd \polylog((\gammin^*)^{-2},\kappa_0^{-1},d) + \ln(2/\dt)} }
\end{align*}

We remark that Allen-Zhu et al., 2021 provides a rounding procedure with $r(\eps) = O(d/\eps^2)$.

Note that $\hGam = \Gam + V_t^{-1} Z^\T S$ where $Z,S \in \RR^{t\times d}$ is the design matrices with $s$-th row being $z_s^\T$ and $\eta_s^\T$ respectively.
Using <ref>, we have, with probability at least $1-\dt$,

\begin{align*}
\forall t\ge 1, \normz{\hGam_t - \Gam}^2_\op
&= \normz{V_t^{-1} Z^\T S}^2_\op
\\&\le \normz{V_t^{-1/2}}^2_\op \normz{V_t^{-1/2} Z^\T S}^2_\op
\\&= \fr{1}{t \sigmin(\fr1t V_t)} \normz{V_t^{-1/2} Z^\T S}_\op ^2
\\&\le \fr{1}{t \sigmin(\fr1t V_t)} \cd \del{8d \ln\del{1 + \fr{2 t}{d(2\wed \sigmin(V_t))} } + 16\ln\del{\fr{2\cd6^d}{\dt}\cd \log^2_2\del{\fr{4}{2\wed \sigmin(V_t)} }  } } \tag{  \cref{lem:covering+martingale}}
\\&= \fr{1}{t} \psi_t
\end{align*}

The well-known Weyl's theorem implies that $\max_k |\lam_k(\hGam_t) - \lam_k(\Gam)| \le \normz{\hGam_t - \Gam}_\op$ where $\lam_k(A)$ is the $k$-th largest singular value of the matrix $A$.
Choosing $k=d$ and combining it with the display above conclude the proof.

We assume $\forall t\ge1, \LCB(t) \le  \gammin^* \le \UCB(t)$, which happens with probability at least $1-\dt$.
Then, it is trivial to see that $\LCB(N_w) \le \gammin^*$.

For the other inequality, we use the fact that the stopping condition was satisfied with $N_w$:

\begin{align*}
\LCB(N_w) > \fr12\UCB(N_w) \ge \fr{\gammin^*}{2} ~.
\end{align*}

This concludes the proof.

We assume $\forall t\ge1, \LCB(t) \le  \lammin(\Gam) \le \UCB(t)$, which happens with probability at least $1-\dt$.
In this proof, we let $\hgammin := \lammin(\hGam_{N_w})$ and $\gammin^* := \lammin(\Gam)$ for brevity.

If $N_w = \lcl r(1) \rcl$, then there is nothing to prove.
Otherwise, the loop in the algorithm was iterated more than once.
Then, since the stopping condition was satisfied with $N_w$, we have that in the previous iteration where $t = N_w/2$ the stopping condition was not satisfied.

\begin{align*}
2 \LCB(N_w/2) \le \UCB(N_w / 2)~.
\end{align*}

Using the following two inequalities:

\begin{align*}
2 \LCB(N_w/2)
&\ge 2\del{\hgammin - \sqrt{\fr{\psi_{N_w/2}}{N_w/2}}}
\ge 2\del{\gammin^* - 2\sqrt{\fr{\psi_{N_w/2}}{N_w/2}}}
\\
\UCB(N_w/2)
&\le \hgammin + \sqrt{\fr{\psi_{N_w/2}}{N_w/2}}
\le \gammin^* + 2 \sqrt{\fr{\psi_{N_w/2}}{N_w/2}}~,
\end{align*}

we have

\begin{align*}
\gammin^* \le 6 \sqrt{\fr{\psi_{N_w/2}}{N_w/2}}
\implies
N_w \le \fr{72}{(\gammin^*)^2} \psi_{N_w/2} ~.
\end{align*}

On the other hand, with the rounding procedure, we have

\begin{align*}
\sig^{-1}_\tmin\del[2]{\sum_{t=1}^N z_t z_t^\T}
= \fr1N\sig^{-1}_\tmin\del[2]{\fr1N\sum_{t=1}^N z_t z_t^\T}
= \fr1N\sigmax\del[3]{\del[3]{\fr1N\sum_{t=1}^N z_t z_t^\T}^{-1}}
\le \fr1N(1+\omega)\kappa_0^{-1}
= \fr{2}{N} \kappa_0^{-1}
\end{align*}

since $\omega = 1$.
Using this and the fact that $N_w \ge d$, it is easy to see that there exists an absolute constant $c_1$ such that

\begin{align*}
\psi_{N_w/2} \le c_1\kappa_0^{-1}\del{d \ln \del{1 + N_w + \kappa_0^{-1}} +  \ln\del{\fr{2}{\dt} } }~.
\end{align*}

Then, there exists an absolute constant $c_2$ such that

\begin{align*}
N_w \le (\gammin^*)^{-2} \cd c_2 \kappa_0^{-1} \del{d \ln \del{1 + N_w + \kappa_0^{-1}} +  \ln\del{\fr{2}{\dt} } }.
\end{align*}

We have $N_w$ on both sides.
We invoke <ref> with $r = 1 + N_w$ to obtain

\begin{align*}
N_w \le 1 + 2 c_2 (\gammin^*)^{-2}\kappa_0^{-1} \del{d \ln(1 + 2\kappa_0^{-1}(1 + c_2 d (\gammin^*)^{-2})) + \ln\del{\fr{2}{\dt}}}~.
\end{align*}

Let $A, \Gam \in \RR^{d\times d}$ where $A$ is symmetric positive semi-definite.

\begin{align*}
\sigmin\rbr{\Gamma^\top A\Gamma}\ge\sigmin\rbr{\Gamma}^2\sigmin\rbr{A}.
\end{align*}

\begin{align*}
(\sigmin(\Gam^\T A \Gam))^{-1}
&= \normz{\Gam^{-1} A^{-1} \Gam^{-T}}_\op
\\&\le \normz{\Gam^{-1}}_\op \normz{A^{-1}}_{\op} \normz{\Gam^{-T}}_\op \tag{submultiplicity of the operator norm}
\\&= \sigmin(\Gam)^{-2} \sigmin(A)^{-1}.
\end{align*}

Taking the inverse on both sides concludes the proof.

§.§ Proof of <ref>

Define $\Lambda = \sum_{i=1}^d \lambda_i e_ie_i^{\top}$, i.e. the diagonal matrix with $\lambda$ on the diagonal.

Note that

\begin{align*}
\min_{\lambda} \max_{i,j} (e_i^{\top} - e_j)^{\top}(\Gamma \Lambda \Gamma^{\top})^{-1} (e_i - e_j)
&= \min_{\lambda}\max_{i,j} \sum_{k=1}^d \frac{(\Gamma_{k,i}^{-1} - \Gamma_{k,j}^{-1})^2}{\lambda_{k}}.
\end{align*}

So for an upper bound, we consider $\lambda = 1/d 1$,

\begin{align*}
\min_{\lambda} \max_{i,j} (e_i^{\top} - e_j)^{\top}(\Gamma \Lambda \Gamma^{\top})^{-1} (e_i - e_j)
&\leq d \max_{i,j} \|\Gamma^{-1}(e_i - e_j)\|_2^2.
\end{align*}

The result about $\rho^{\ast}$ follows immediately.

When $\Gamma = (1-\epsilon)/d 11^{\top} + \epsilon I$, a computation using Sherman-Morrison shows that $\Gamma^{-1} = 1/\epsilon[I - (1-\epsilon)/d 11^{\top}]$. Thus

\begin{align*}
\min_{\lambda} \max_{i,j} (e_i^{\top} - e_j)^{\top}(\Gamma \Lambda \Gamma^{\top})^{-1} (e_i - e_j)
&= \epsilon^{-2}\min_{\lambda} \max_{i,j} (e_i - e_j)^{\top}\Lambda^{-1}(e_i- e_j)\\
&= \epsilon^{-2}\min_{\lambda} \max_{i,j} e_i{\top}\Lambda^{-1}e_i+ e_j\Lambda^{-1}e_j\\
&= \epsilon^{-2}\min_{\lambda} \max_{i,j} e_i{\top}\Lambda^{-1}e_i+ e_j\Lambda^{-1}e_j\\
&\geq \epsilon^{-2}\min_{\lambda}\max_i e_i{\top}\Lambda^{-1}e_i\\
& = \epsilon^{-2}d,
\end{align*}

where the last line follows from the Kiefer-Wolfowitz Theorem [Lattimore and Szepesvári, 2020].

§.§ Lemma for solving x less than ln(x)

Let $a,b,c,d>0$.
Then, for every $r$,

\begin{align*}
r \le a + b\ln(c + dr) \implies  r \le 2a + 2b \ln(1 + 2c + 2bd).
\end{align*}

If $dr \le c$, then

\begin{align*}
\le a + b\ln(2c)
&\le a + b\ln(1 + 2c).
\end{align*}

If $dr > c$, then,

\begin{align*}
&\le a + b\ln(2dr)
\\&= a + b\ln(2d\fr{r}{2b} \cd 2b)
\\&\le a + b\del{\fr{r}{2b} - 1 + \ln(4bd)  } \tag{$\ln(x) \le x - 1$}
\\ \implies
&\le 2a + 2b\ln\del{\fr{4}{e} bd}
\\&\le 2a + 2b\ln(2 bd).
\end{align*}

Either case, we have

\begin{align*}
\le 2a + 2b \ln((1 + 2c) \vee 2bd)
\le 2a + 2b \ln(1 + 2c + 2bd).
\end{align*}

Let $\alpha,\beta > 0$.
Then, for any $r$,

\begin{align*}
r \le \alpha \ln(1 + r) + \beta
\implies r \le 2\alpha\ln(e + \alpha) + 2\beta.
\end{align*}

\begin{align*}
&\le \alpha \ln(r(\fr1r + 1)) + \beta
\\&\le \alpha \ln(\fr{r}{2\alpha}\cd 2\alpha(\fr1r + 1)) + \beta
\\&\le \alpha \del{\fr{r}{2\alpha} - 1 + \ln(2 \alpha(\fr1r + 1 ))} + \beta \tag{$\forall x, \ln(x) \le x - 1$}
\\\implies
r &\le 2\alpha \ln(\fr{2}{e} \alpha(\fr1r + 1)) + \beta.
\end{align*}

If $r \le 2\alpha$, then there is nothing to prove.
If $r > 2\alpha$, then $r \le 2\alpha \ln(1 + \alpha) + 2\beta$.
Either case, we have $r \le 2\alpha \ln(e + \alpha) + 2\beta$.