Then, for any $\zeta>0$,

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\exists
f^{\prime}\in\mathcal{F}_{t}:\|f^{\prime}(x_{t})-{f^{\star}}(x_{t})\|\geq\zeta\\}\leq\left(\frac{\beta^{2}}{\zeta^{2}}+1\right)\mathfrak{E}(\mathcal{F},\zeta;{f^{\star}}).$

##  Appendix C Selective Sampling: Learning from Single Expert

###  C.1 Proof of Theorem 1

Before delving into the proof, we recall the relevant notation. In Algorithm
1,

  1. $\bullet$

The label $y_{t}\sim\phi({f^{\star}}(x_{t}))$, where $\phi$ denotes the link-
function given in (2).

  2. $\bullet$

The function
$\mathtt{SelectAction}(f_{t}(x_{t}))\vcentcolon={}\operatorname*{argmax}_{k}\phi(f_{t}(x_{t}))[k]$.

  3. $\bullet$

For any vector $v\in\mathbb{R}^{K}$, the margin is given by the gap between
the value at the largest and the second largest coordinate, i.e.

$\displaystyle\mathtt{Margin}(v)=\phi(v)[k^{\star}]-\max_{k\neq
k^{\star}}\phi(v)[k],$

where $k^{\star}\in\operatorname*{argmax}_{k\in[K]}\phi(v)[k]$.

  4. $\bullet$

We also define
$T_{\varepsilon}=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
to denote the number of samples within $T$ rounds of interaction for which the
margin w.r.t. ${f^{\star}}$ is smaller than $\varepsilon$.

  5. $\bullet$

We define the function
$\mathrm{Gap}:\mathbb{R}^{K}\times[K]\mapsto\mathbb{R}^{+}$ as

$\displaystyle\mathrm{Gap}(v,k)=\max_{k^{\prime}}\phi(v)[k^{\prime}]-\phi(v)[k],$
(16)

to denote the gap between the largest and the $k$-th coordinate of $v$.

####  C.1.1 Supporting Technical Results

######  Lemma 9.

For any $u$, and $k^{\prime}\neq\operatorname*{argmax}_{k}\phi(u)[k]$,

$\displaystyle\mathtt{Margin}(u)\leq\mathrm{Gap}(u,k^{\prime}).$

###### Proof.

Let $k^{\star}=\operatorname*{argmax}_{k}\phi(u)[k]$. By definition,

$\displaystyle\mathrm{Gap}(u,k^{\prime})$
$\displaystyle=\phi(u)[k^{\star}]-\phi(u)[k^{\prime}]$
$\displaystyle\geq\phi(u)[k^{\star}]-\max_{k^{\prime}\neq
k}\phi(u)[k^{\prime}]=\mathtt{Margin}(u).$

∎

The following technical result establishes a certain favorable property for
the function ${f^{\star}}$, whose proof follows from the regret bound of the
online oracle used in Algorithm 1.

######  Lemma 10.

With probability at least $1-\delta$, the function ${f^{\star}}\in\mathcal{F}$
satisfies the following for all $t\leq T$:

$\displaystyle\sum_{s=1}^{t}Z_{s}\|{f^{\star}}(x_{s})-f_{s}(x_{s})\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)},$

where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}\vcentcolon={}\frac{4}{\lambda}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}+\frac{112}{\lambda^{2}}\log(4\log^{2}(T)/\delta)$.

###### Proof.

The desired result follows from an application of Lemma 5, where we note that
we do not query oracle when $Z_{s}=0$, and thus do not count the time steps
for which $Z_{s}=0$. ∎

Throughout the proof, we condition on the $1-\delta$ probability event that
Lemma 10 holds. The next technical lemma allows us to bound the number of
times when we query for the label and $\Delta_{t}(x_{t})\geq\zeta$ in terms of
the eluder dimension (normed version) of the function class $\mathcal{F}$.
Note that Lemma 11 holds even if the sequence $\\{x_{t}\\}_{t\leq T}$ could be
adversarially generated.

######  Lemma 11.

Let ${f^{\star}}$ satisfy Lemma 10, and let $\Delta_{t}(x_{t})$ be defined in
(5) in Algorithm 1. Then, for any $\zeta>0$, with probability at least
$1-\delta$,

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{t}(x_{t})\geq\zeta\right\\}$
$\displaystyle\leq\widetilde{O}\left(\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}}{\zeta^{2}}\cdot\mathfrak{E}(\mathcal{F},\nicefrac{{\zeta}}{{2}};{f^{\star}})\right).$

where $\mathfrak{E}$ denotes the eluder dimension is given in Definition 1.

###### Proof.

Let $f^{\star}_{t}$ denote the maximizer of (5) at round $t$ on point $x_{t}$.
Thus,

$\displaystyle\Delta_{t}(x_{t})=\|f^{\star}_{t}(x_{t})-f_{t}(x_{t})\|,\qquad\text{and}\qquad\sum_{s=1}^{t-1}Z_{s}\left\|f^{\star}_{t}(x_{s})-f_{s}(x_{s})\right\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}.$
(17)

However, recall that Lemma 10 implies that, with probability at least
$1-\delta$, the function ${f^{\star}}$ satisfies the bound

$\displaystyle\sum_{s=1}^{t-1}Z_{s}\left\|{f^{\star}}(x_{s})-f_{s}(x_{s})\right\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}.$
(18)

Using (17), (18) and Triangle inequality, we get that

$\displaystyle\sum_{s=1}^{t-1}Z_{s}\left\|f^{\star}_{t}(x_{s})-{f^{\star}}(x_{s})\right\|^{2}$
$\displaystyle\leq
2\sum_{s=1}^{t-1}Z_{s}\left\|f^{\star}_{t}(x_{t})-f_{s}(x_{s})\right\|^{2}+2\sum_{s=1}^{t-1}Z_{s}\left\|{f^{\star}}(x_{t})-f_{s}(x_{s})\right\|^{2}$
$\displaystyle\leq
4{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}.$
(19)

Next, note that, an application of Triangle inequality implies that
$\|f^{\star}_{t}(x_{t})-f_{t}(x_{t})\|\leq\|f^{\star}_{t}(x_{t})-{f^{\star}}(x_{t})\|+\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$.
Thus,

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{t}(x_{t})\geq\zeta\right\\}$
$\displaystyle=\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\|f^{\star}_{t}(x_{t})-f_{t}(x_{t})\|\geq\zeta\right\\}$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\|f^{\star}_{t}(x_{t})-{f^{\star}}(x_{t})\|+\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|\geq\zeta\right\\}$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\|f^{\star}_{t}(x_{t})-{f^{\star}}(x_{t})\|\geq\frac{\zeta}{2}\right\\}+\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|\geq\frac{\zeta}{2}\right\\}$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\|f^{\star}_{t}(x_{t})-{f^{\star}}(x_{t})\|\geq\frac{\zeta}{2}\right\\}+\frac{4}{\zeta^{2}}\sum_{t=1}^{T}Z_{t}(f_{t}(x_{t})-{f^{\star}}(x_{t}))^{2}$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\|f^{\star}_{t}(x_{t})-{f^{\star}}(x_{t})\|\geq\frac{\zeta}{2}\right\\}+\frac{4{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}}{\zeta^{2}},$
(20)

where in the last line we used Lemma 10 to bound the second term. In the
following, we show how to bound the first term. Recall that for any $t\leq T$,
the function $f^{\star}_{t}$ satisfies (19). Thus, we wish to bound

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\|f^{\star}_{t}(x_{t})-{f^{\star}}(x_{t})\|\geq\frac{\zeta}{2}\right\\}\quad\text{s.t.}\quad\sum_{s=1}^{t-1}Z_{s}(f^{\star}_{t}(x_{s})-{f^{\star}}(x_{s}))^{2}$
$\displaystyle\leq
4{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)},$

for all $t\leq T$. An application of Lemma 8 in the above implies that

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\|f^{\star}_{t}(x_{t})-{f^{\star}}(x_{t})\|\geq\frac{\zeta}{2}\right\\}$
$\displaystyle\leq\frac{17{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}}{\zeta^{2}}\cdot\mathfrak{E}(\mathcal{F},\nicefrac{{\zeta}}{{2}};{f^{\star}}).$
(21)

where in the last line, we used the fact that
$\nicefrac{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}}}{{\zeta^{2}}}\geq
1$, for our parameter setting.

Plugging in the bound (21) in (20), and using the fact that
$\mathfrak{E}(\mathcal{F},\nicefrac{{\zeta}}{{2}};{f^{\star}})\geq 1$, we get
that

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{t}(x_{t})\geq\zeta\right\\}$
$\displaystyle\leq\frac{20{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}}{\zeta^{2}}\cdot\mathfrak{E}(\mathcal{F},\nicefrac{{\zeta}}{{2}};{f^{\star}}).$

∎

The next two technical lemma’s relate the margin to the gap between functions,
and are useful in the analysis for regret / total number of queries.

######  Lemma 12.

Suppose the functions $\pi_{1}$ and $\pi_{2}$ are defined such that
$\pi_{i}(x)=\operatorname*{argmax}_{k\in[K]}\phi(f_{i}(x))[k]$. Then, for any
$x$ for which $\pi_{1}(x)\neq\pi_{2}(x)$, we have

$\displaystyle\mathtt{Margin}(f_{1}(x))\leq\phi(f_{1}(x))[\pi_{1}(x)]-\phi(f_{1}(x))[\pi_{2}(x)]\leq
2\gamma\|f_{1}(x)-f_{2}(x)\|_{2},$

where $\gamma$-denotes the Lipschitz parameter of the link function $\phi$.

###### Proof.

First note $\phi(f_{2}(x))[\pi_{2}(x)]\geq\phi(f_{2}(x))[\pi_{1}(x)]$ by the
definition of $\pi_{2}$. Thus,

$\displaystyle\phi(f_{1}(x))[\pi_{1}(x)]-\phi(f_{1}(x))[\pi_{2}(x)]$
$\displaystyle\leq\phi(f_{1}(x))[\pi_{1}(x)]-\phi(f_{2}(x))[\pi_{1}(x)]+\phi(f_{2}(x))[\pi_{2}(x)]-\phi(f_{1}(x))[\pi_{2}(x)]$
$\displaystyle\leq 2\|\phi(f_{1}(x))-\phi(f_{2}(x))\|_{\infty}$
$\displaystyle\leq 2\|\phi(f_{1}(x))-\phi(f_{2}(x))\|_{2}.$

Using the fact that $\phi$ is $\gamma$-Lipschitz, we immediately get that

$\displaystyle\phi(f_{1}(x))[\pi_{1}(x)]-\phi(f_{1}(x))[\pi_{2}(x)]$
$\displaystyle\leq 2\gamma\|f_{1}(x)-f_{2}(x)\|_{2}.$

∎

######  Lemma 13.

For any two function $f_{1},f_{2}\in\mathcal{F}$, and $x\in\mathcal{X}$,

$\displaystyle\mathtt{Margin}(f_{1}(x))-\mathtt{Margin}(f_{2}(x))$
$\displaystyle\leq 2\gamma\|f_{1}(x)-f_{2}(x)\|.$

###### Proof.

For the ease of notation, define

$\displaystyle
k_{1}=\operatorname*{argmax}_{k\in[k]}\phi(f_{1}(x))[k]\qquad\text{and}\qquad
k^{\prime}_{1}=\operatorname*{argmax}_{k^{\prime}\neq
k_{1}}\phi(f_{1}(x))[k^{\prime}],$ where ties are broken arbitrarily but
consistently. Similarly, we define $\displaystyle
k_{2}=\operatorname*{argmax}_{k\in[k]}\phi(f_{2}(x))[k]\qquad\text{and}\qquad
k^{\prime}_{2}=\operatorname*{argmax}_{k^{\prime}\neq
k_{2}}\phi(f_{2}(x))[k^{\prime}].$ (22)

Thus, we have that

$\displaystyle\mathtt{Margin}(f_{1}(x))=\phi(f_{1}(x))[k_{1}]-\phi(f_{1}(x))[k^{\prime}_{1}],$
and
$\displaystyle\mathtt{Margin}(f_{2}(x))=\phi(f_{2}(x))[k_{2}]-\phi(f_{2}(x))[k^{\prime}_{2}].$
(23)

Finally, also note that for any coordinate $k$,

$\displaystyle\phi(f_{1}(x))[k]-\phi(f_{2}(x))[k]\leq\|\phi(f_{2}(x))-\phi(f_{1}(x))\|.$
(24)

We now proceed with the proof. Plugging in the form in (23), we get that

$\displaystyle\mathtt{Margin}(f_{1}(x))-\mathtt{Margin}(f_{2}(x))$
$\displaystyle=\phi(f_{1}(x))[k_{1}]-\phi(f_{1}(x))[k^{\prime}_{1}]-\left(\phi(f_{2}(x))[k_{2}]-\phi(f_{2}(x))[k^{\prime}_{2}]\right)$
$\displaystyle=\left(\phi(f_{1}(x))[k_{1}]-\phi(f_{2}(x))[k_{2}]\right)+\left(\phi(f_{2}(x))[k^{\prime}_{2}]-\phi(f_{1}(x))[k^{\prime}_{1}]\right)$
$\displaystyle\leq\left(\phi(f_{1}(x))[k_{1}]-\phi(f_{2}(x))[k_{1}]\right)+\left(\phi(f_{2}(x))[k^{\prime}_{2}]-\phi(f_{1}(x))[k^{\prime}_{1}]\right)$
$\displaystyle\leq\|\phi(f_{2}(x))-\phi(f_{1}(x))\|+(\phi(f_{2}(x))[k^{\prime}_{2}]-\phi(f_{1}(x))[k^{\prime}_{1}]),$

where the first inequality uses the fact that $k_{2}$ is the maximizer
coordinate of $\phi(f_{2}(x))$ and the last inequality uses (24). In the
following, we bound the second term in the right hand side above under the
following three cases:

  1. $\bullet$

Case 1: $k^{\prime}_{2}\neq k_{1}$: Since $k^{\prime}_{2}\neq k_{1}$, we note
that replacing $k_{1}^{\prime}$ by $k^{\prime}_{2}$ in the second term will
only increase the value (see the definition in (22)). Thus,

$\displaystyle\phi(f_{2}(x))[k^{\prime}_{2}]-\phi(f_{1}(x))[k^{\prime}_{1}]$
$\displaystyle\leq\phi(f_{2}(x))[k^{\prime}_{2}]-\phi(f_{1}(x))[k^{\prime}_{2}]$
$\displaystyle\leq\|\phi(f_{2}(x))-\phi(f_{1}(x))\|,$

where the last line uses (24).

  2. $\bullet$

Case 2a: $k^{\prime}_{2}=k_{1},k_{2}=k^{\prime}_{1}$: Using definition of
$k_{2}$ in (22), we note that

$\displaystyle\phi(f_{2}(x))[k^{\prime}_{2}]-\phi(f_{1}(x))[k^{\prime}_{1}]$
$\displaystyle=\phi(f_{2}(x))[k^{\prime}_{2}]-\phi(f_{1}(x))[k_{2}]$
$\displaystyle\leq\phi(f_{2}(x))[k_{2}]-\phi(f_{1}(x))[k_{2}]$
$\displaystyle\leq\|\phi(f_{2}(x))-\phi(f_{1}(x))\|,$

where the last line uses (24).

  3. $\bullet$

Case 2b: $k^{\prime}_{2}=k_{1},k_{2}\neq k^{\prime}_{1}$: Using the fact that
$k^{\prime}_{2}=k_{1}$ and that $k_{2}\neq k^{\prime}_{2}$, we get that
$k_{2}\neq k_{1}$. Thus using the definition of $k_{1}^{\prime}$ along with
the fact that $k_{2}\neq k_{1}$, we get that

$\displaystyle\phi(f_{2}(x))[k^{\prime}_{2}]-\phi(f_{1}(x))[k^{\prime}_{1}]$
$\displaystyle\leq\phi(f_{2}(x))[k^{\prime}_{2}]-\phi(f_{1}(x))[k_{2}]$
$\displaystyle\leq\phi(f_{2}(x))[k_{2}]-\phi(f_{1}(x))[k_{2}]$
$\displaystyle\leq\|\phi(f_{2}(x))-\phi(f_{1}(x))\|,$

where the second last line uses definition of $k_{2}$ and the last line uses
(24).

Combining all the above bounds together implies that

$\displaystyle\mathtt{Margin}(f_{1}(x))-\mathtt{Margin}(f_{2}(x))$
$\displaystyle\leq 2\|\phi(f_{2}(x))-\phi(f_{1}(x))\|.$

The final statement follows since $\phi$ is $\gamma$-Lipschitz. ∎

####  C.1.2 Regret Bound

For the ease of notation, for the rest of the proof in this section we define
the function ${\pi^{\star}}$ such that

$\displaystyle{\pi^{\star}}(x)=\operatorname*{argmax}_{k}\phi({f^{\star}}(x))[k].$

Additionally, we recall that for any time $t$,
$\widehat{y}_{t}=\mathtt{SelectAction}(f_{t}(x_{t}))=\operatorname*{argmax}_{k}\phi(f_{t}(x))[k]$.
Starting from the definition of the regret, we have

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}\operatorname{Pr}\left(\widehat{y}_{t}\neq
y_{t}\right)-\operatorname{Pr}\left({\pi^{\star}}(x_{t})\neq y_{t}\right)$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}\cdot\left\lvert\operatorname{Pr}\left(y_{t}={\pi^{\star}}(x_{t})\right)-\operatorname{Pr}\left(y_{t}=\widehat{y}_{t}\right)\right\rvert$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}\cdot\left\lvert\phi({f^{\star}}(x_{t}))[{\pi^{\star}}(x_{t})]-\phi({f^{\star}}(x_{t}))[\widehat{y}_{t}]\right\rvert$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}\cdot\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t}),$

where the second last line uses the probabilistic model from which labels are
generated, and the last inequality plugs in the definition of $\mathrm{Gap}$
from (59). Let $\varepsilon>0$ be a free parameter. We can decompose the above
regret bound further as:

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})\leq\varepsilon\\}\cdot\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})$

Using the fact that
$\mathsf{y}_{t}(x_{t})=\operatorname*{argmax}_{k\in[K]}\phi(f_{t}(x))[k]$
along with the definition of $\mathrm{Gap}$ and Lemma 12, we get that

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})\leq\varepsilon\\}\cdot\varepsilon$
$\displaystyle\hskip
72.26999pt+2\gamma\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}\cdot\varepsilon$
$\displaystyle\hskip
72.26999pt+2\gamma\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}\cdot\varepsilon$
$\displaystyle\hskip
72.26999pt+2\gamma\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\hskip
72.26999pt+2\gamma\sum_{t=1}^{T}\bar{Z}_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
(25) $\displaystyle=T_{\varepsilon}\cdot\varepsilon+2\gamma\cdot
T_{A}+2\gamma\cdot T_{B}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|,$

where the second inequality holds because
$\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})\leq\varepsilon$ implies that
$\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon$ whenever
$\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})$. In the last line above, we plugged
in the definition of $T_{\varepsilon}$, and defined $\mathtt{T}_{A}$ and
$\mathtt{T}_{B}$ as the second term and the last term respectively (upto
constants). We bound them separately below:

  1. $\bullet$

Bound on $\mathtt{T}_{A}$: We note that

$\displaystyle\mathtt{T}_{A}$
$\displaystyle=\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|>\varepsilon/2\gamma\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$

where the second line follows from Lemma 12 and because
$\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})$. Using the fact that
$\mathbf{1}\\{a\geq b\\}\leq\nicefrac{{a}}{{b}}$ for all $a,b\geq 0$, we get
that

$\displaystyle\mathtt{T}_{A}\leq
4\gamma\sum_{t=1}^{T}Z_{t}\frac{\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|^{2}}{\varepsilon}.$
(26)

  2. $\bullet$

Bound on $\mathtt{T}_{B}$: Fix any $t\leq T$, and note that Lemma 10 implies
that
$\sum_{s=1}^{t}\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}$.
Thus ${f^{\star}}$ satisfies the constraint in the definition of $\Delta_{t}$
in (5) and we must have that

$\displaystyle\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|\leq\Delta_{t}(x_{t}).$ (27)

Plugging in the definition of $Z_{t}$, we note that

$\displaystyle\mathtt{T}_{B}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))>2\gamma\Delta_{t}(x_{t}),\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|>\Delta_{t}(x_{t})\\},$

where the second inequality is due Lemma 12. However, note that the term
inside the indicator contradicts (27) (which always holds). Thus,

$\displaystyle\mathtt{T}_{B}$ $\displaystyle=0.$ (28)

Combining the bounds (26) and (28), we get that

$\displaystyle\mathrm{Reg}_{T}$ $\displaystyle\leq\varepsilon
T_{\varepsilon}+8\gamma^{2}\sum_{t=1}^{T}Z_{t}\frac{\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|^{2}}{\varepsilon}$
$\displaystyle\leq\varepsilon
T_{\varepsilon}+\frac{8\gamma^{2}}{\varepsilon}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)},$

where the last inequality is due to Lemma 10.

Since $\varepsilon$ is a free parameter above, the final bound follows by
choosing the best parameter $\varepsilon$, and by plugging in the form of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}$.

####  C.1.3 Total Number of Queries

We use the notation $N_{T}$ to denote the total number of expert queries made
by the learner within $T$ rounds of interactions. Let $\varepsilon>0$ be a
free parameter. Using the definition of $Z_{t}$, we have that

$\displaystyle N_{T}$ $\displaystyle=\sum_{t=1}^{T}Z_{t}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t})\\}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})>\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
(29) $\displaystyle=T_{\varepsilon}+\mathtt{T}_{D}+\mathtt{T}_{E},$

where in the last line we use the definition of $T_{\varepsilon}$, and defined
$\mathtt{T}_{D}$ and $\mathtt{T}_{E}$ respectively. We bound them separately
below:

  1. $\bullet$

Bound on $\mathtt{T}_{D}$. Recall (27) which implies that ${f^{\star}}$
satisfies the bound
$\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|\leq\Delta_{t}(x_{t})$. Thus, using Lemma
13, we get that

$\displaystyle\mathtt{Margin}({f^{\star}}(x_{t}))\leq
2\gamma\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|+t\mathtt{Margin}(f_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t})+\mathtt{Margin}(f_{t}(x_{t})).$

The above implies that

$\displaystyle\mathtt{T}_{D}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq
4\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
$\displaystyle\leq 0,$

where the last line follows from the fact that all the conditions inside the
indictor can not hold simultaneously.

  2. $\bullet$

Bound on $\mathtt{T}_{E}$. We note that

$\displaystyle\mathtt{T}_{E}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})>\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{t}(x_{t})\geq\nicefrac{{\varepsilon}}{{4\gamma}}\right\\}$
$\displaystyle\leq\frac{320{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}}{\varepsilon^{2}}\cdot\mathfrak{E}(\mathcal{F},\nicefrac{{\varepsilon}}{{4\gamma}};{f^{\star}}).$

where the last line follows from setting $\zeta=\varepsilon/4\gamma$ in Lemma
11.

Gathering the bounds above, we get that

$\displaystyle N_{T}$ $\displaystyle\leq
T_{\varepsilon}+\frac{640\gamma^{2}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}}{\varepsilon^{2}}\cdot\mathfrak{E}(\mathcal{F},\nicefrac{{\varepsilon}}{{4\gamma}};{f^{\star}}).$

Since $\varepsilon$ is a free parameter above, the final bound follows by
choosing the best parameter $\varepsilon$, and by plugging in the form of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}$.

###  C.2 Proof of Theorem 2

1:Parameters $\delta,\gamma,\lambda,T$, function class $\mathcal{F}$, and
online regression oracle $\mathsf{Oracle}$ w.r.t $\ell_{\phi}$.

2:Set
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}=\frac{4}{\lambda}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}+\frac{112}{\lambda^{2}}\log(4\log^{2}(T)/\delta)$,
Compute $f_{1}\leftarrow\text{$\mathsf{Oracle}$}_{1}(\emptyset)$.

3:Set $E=\left\lceil\log(T)\right\rceil$ and $\tau_{e}=2^{e-1}$ for $e\leq E$.

4:for $e=1,\dots,E-1$ do

5: Learner constructs the feasible set of optimal functions $\mathcal{F}_{e}$
as
$\displaystyle\mathcal{F}_{e}=\left\\{f\in\mathcal{F}\mid\sum_{s=1}^{\tau_{e}-1}Z_{s}\left\|f(x_{s})-f_{s}(x_{s})\right\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}\right\\}.$
(30)

6: for $t$ $\leftarrow\tau_{e}$ to $\tau_{e+1}-1$ do

7: Nature samples $x_{t}$ from an (unknown) distribution $\mu$.

8: Learner computes  $\displaystyle
g_{t}\in\operatorname*{argmin}_{g\in\mathcal{F}_{e}}\leavevmode\nobreak\
\mathtt{Margin}(g(x_{t})),\quad\text{and,}\quad\Delta_{e}(x_{t})\vcentcolon={}\max_{f,f^{\prime}\in\mathcal{F}_{e}}\leavevmode\nobreak\
\|f(x_{t})-f^{\prime}(x_{t})\|.$ (31)

9: Learner decides whether to query:
$Z_{t}=\mathbf{1}\\{\mathtt{Margin}(g_{t}(x_{t}))\leq
2\gamma\Delta_{e}(x_{t})\\}$.

10: if $Z_{t}=1$ then

11: Learner plays the action
$\widehat{y}_{t}=\mathtt{SelectAction}(f_{t}(x_{t}))$.

12: Learner queries the label $y_{t}$ on $x_{t}$.

13: $f_{t+1}\leftarrow\text{$\mathsf{Oracle}$}_{t}(\\{x_{t},y_{t}\\})$.

14: else

15: Learner plays the action
$\widehat{y}_{t}=\mathtt{SelectAction}(g_{t}(x_{t}))$.

16: $f_{t+1}\leftarrow f_{t}$.

Algorithm 4 Selective Sampling with Expert Feedback for Stochastic Contexts

Before delving into the proof, we recall the relevant notation. In Algorithm
4,

  1. $\bullet$

The label $y_{t}\sim\phi({f^{\star}}(x_{t}))$, where $\phi$ denotes the link-
function given in (2).

  2. $\bullet$

The function
$\mathtt{SelectAction}(f_{t}(x_{t}))\vcentcolon={}\operatorname*{argmax}_{k}\phi(f_{t}(x_{t}))[k]$.

  3. $\bullet$

For any vector $v\in\mathbb{R}^{K}$, the margin is given by the gap between
the value at the largest and the second largest coordinate, i.e.

$\displaystyle\mathtt{Margin}(v)=\phi(v)[k^{\star}]-\max_{k\neq
k^{\star}}\phi(v)[k],$

where $k^{\star}\in\operatorname*{argmax}_{k\in[K]}\phi(v)[k]$.

  4. $\bullet$

We also define
$T_{\varepsilon}=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
to denote the number of samples within $T$ rounds of interaction for which the
margin w.r.t. ${f^{\star}}$ is smaller than $\varepsilon$.

  5. $\bullet$

We define the function
$\mathrm{Gap}:\mathbb{R}^{K}\times[K]\mapsto\mathbb{R}^{+}$ as

$\displaystyle\mathrm{Gap}(v,k)=\max_{k^{\prime}}\phi(v)[k^{\prime}]-\phi(v)[k],$
(32)

to denote the gap between the largest and the $k$-th coordinate of $v$. Recall
that Lemma 9 holds.

  6. $\bullet$

Additionally, we define the function $Z^{e}$ to denote the query condition

$\displaystyle
Z^{e}(x)=\mathbf{1}\\{\inf_{g\in\mathcal{F}_{e}}\mathtt{Margin}(g(x))\leq
2\gamma\sup_{f,f^{\prime}\in\mathcal{F}_{e}}\|f(x)-f^{\prime}(x)\|\\}.$ (33)

The definition in (33) suggests that for all $t\in[\tau_{e},\tau_{e+1})$,
$Z_{t}=Z^{e}(x_{t})$, for all $e\leq E-1$.

##### Intuition for epoching.

We next provide intuition on why epoching in needed in Algorithm 4 to get the
improved query complexity bound. From the proof sketch in Section 3, the term
$\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\Delta_{t}(x_{t})\geq\varepsilon\\}$
appearing in the query complexity bound is handled using the eluder dimension
of $\mathcal{F}$. When $x_{t}$ is sampled i.i.d. we wish to bound this using
disagreement-coefficient instead. However, note that in Algorithm 1 the query
condition $Z_{t}$ depends on the samples $\\{x_{s}\\}_{s<t}$ drawn in all
previous time steps and the corresponding query conditions
$\\{Z_{s}\\}_{s<t}$. This introduces a bias, and thus the terms
$Z_{t}\mathbf{1}\\{\Delta_{t}(x_{t})\geq\varepsilon\\}$ are no longer
independent to each other. Thus, we can not directly used distributional
properties like the disagreement coefficient to bound the query complexity.
Algorithm 4 fixes this issue by defining epochs of doubling length such that
the query condition in epoch $e$ only depends on the samples presented to the
learner at time steps before this epoch (i.e. in time steps $1\leq
t\leq\tau_{e}-1$. Thus, the terms
$Z_{t}\mathbf{1}\\{\Delta_{t}(x_{t})\geq\varepsilon\\}$ for $\tau_{e}\leq
t<\tau_{e+1}$ are i.i.d. allowing us to get bounds in terms of distributional
properties like the disagreement coefficient of $\mathcal{F}$.

However, note that whenever we query in Algorithm 4, we still choose the
labels according to the estimate from the online regression oracle and thus
the regret bound remains unchanged.

####  C.2.1 Supporting Technical Results

The following lemma establishes useful technical properties of the function
${f^{\star}}$ and the sets $\mathcal{F}_{e}$.

######  Lemma 14.

Suppose Algorithm 4 is run on the sequence $\\{x_{t}\\}_{t\leq T}$ drawn
i.i.d. from the unknown distribution $\mu$. Then, with probability at least
$1-\delta$, each of the following holds:

  1. $(a)$

For all $t\leq T$, the function ${f^{\star}}\in\mathcal{F}$ satisfies

$\displaystyle\sum_{s=1}^{t}Z_{s}\|{f^{\star}}(x_{s})-f_{s}(x_{s})\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)},$

where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}=\frac{4}{\lambda}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}+\frac{112}{\lambda^{2}}\log(4\log^{2}(T)/\delta)$.

Thus, ${f^{\star}}\in\mathcal{F}_{e}$ for all $e\leq E-1$, and
$\|{f^{\star}}(x_{t})-g_{t}(x_{t})\|\leq\Delta_{e}(x_{t})$ for all
$\tau_{e}\leq t\leq\tau_{e+1}-1$.

  2. $(b)$

For any function $f\in\mathcal{F}_{e}$, we have

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{s=1}^{\tau_{e}-1}Z_{s}\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)},$

where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}\vcentcolon={}2{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}+4c_{2}\left(\log^{4}(T)\sup_{\tau\leq
T}\left(\tau\mathsf{Rad}^{2}_{\tau}(\mathcal{F})\right)+2\log(T)\log(E/\delta)\right)$.

  3. $(c)$

For any $e\leq E$, and any function $f\in\mathcal{F}_{e}$, we have

$\displaystyle\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\bar{\nu}_{e}}$
$\displaystyle\leq\sqrt{\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\tau_{e}-1}}$

where the sub-distributions
$\bar{\mu}_{\bar{e}}(x)\vcentcolon={}Z^{\bar{e}}(x)\mu(x)$ and
$\bar{\nu}_{e}\vcentcolon={}\frac{1}{\tau_{e}-\tau_{1}}\sum_{\bar{e}=1}^{e-1}(\tau_{{\bar{e}}+1}-\tau_{\bar{e}})\bar{\mu}_{\bar{e}}$.

  4. $(d)$

For any ${\bar{e}}<e$, the corresponding sets $\mathcal{F}_{e}$ and
$\mathcal{F}_{{\bar{e}}}$ satisfy the relation
$\mathcal{F}_{e}\subseteq\mathcal{F}_{{\bar{e}}}$.

  5. $(e)$

For any ${\bar{e}}\leq e$, we have
$\bar{\mu}_{e}\preccurlyeq\bar{\mu}_{{\bar{e}}}$.

###### Proof.

We prove each part separately below:

  1. $(a)$

An application of Lemma 5, where we note that we do not query oracle when
$Z_{s}=0$, and thus do not count the time steps for which $Z_{s}=0$, implies
that

$\displaystyle\sum_{s=1}^{t}Z_{s}\|{f^{\star}}(x_{s})-f_{s}(x_{s})\|^{2}\leq\frac{4}{\lambda}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}+\frac{112}{\lambda^{2}}\log(4\log^{2}(T)/\delta)=\vcentcolon{}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}$

for all $t\leq T$ with probability at least $1-\delta$. Using the above for
$t=\tau_{e+1}-1$ implies that ${f^{\star}}\in\mathcal{F}_{e}$ for all $e\leq
E-1$. Since, we also have that $g_{t}\in\mathcal{F}_{e}$ (by construction) for
all $\tau_{e}\leq t\leq\tau_{e+1}-1$, plugging in the definition of
$\Delta_{e}(x_{t})$, we immediately get that
$\|{f^{\star}}(x_{t})-g_{t}(x_{t})\|\leq\Delta_{e}(x_{t})$.

  2. $(b)$

Fix any epoch number ${\bar{e}}\leq E-1$, and consider the time steps
$\tau_{\bar{e}}\leq t<\tau_{{\bar{e}}+1}$. Define the loss function

$\displaystyle\ell_{\bar{e}}(f(x),{f^{\star}}(x))=Z^{\bar{e}}(x)\left\|f(x)-{f^{\star}}(x)\right\|^{2}$

where $Z^{\bar{e}}$ denotes the query conditions at epoch ${\bar{e}}$ (defined
in (33)), and recall that $Z^{\bar{e}}$ does not depend on any samples that
are drawn at epoch ${\bar{e}}$ (by definition). Furthermore, note that
$\ell_{\bar{e}}$ is $2$-smooth w.r.t. $f$ and satisfies
$\ell_{\bar{e}}(f(x),{f^{\star}}(x))\leq 4$ for all
$f,{f^{\star}}\in\mathcal{F}$ and $x$. Thus using Lemma 2, we get that for any
$f\in\mathcal{F}_{e}$, with probability at least $1-\delta/E$,

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{s=\tau_{\bar{e}}}^{\tau_{{\bar{e}}+1}-1}Z^{\bar{e}}(x_{s})\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle\leq
2\sum_{s=\tau_{\bar{e}}}^{\tau_{{\bar{e}}+1}-1}Z^{\bar{e}}(x_{s})\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}+c_{2}\left(2{\tau_{e}}\log^{3}(\tau_{e})\mathsf{Rad}^{2}_{\tau_{e}}(\mathcal{F}_{e})+4\log(E/\delta)\right)$
$\displaystyle\leq
2\sum_{s=\tau_{\bar{e}}}^{\tau_{{\bar{e}}+1}-1}Z^{\bar{e}}(x_{s})\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}+2c_{2}\left(\log^{3}(T)\sup_{\tau\leq
T}\left(\tau\mathsf{Rad}^{2}_{\tau}(\mathcal{F})\right)+2\log(E/\delta)\right),$

where in the last line we used the fact that
$\mathcal{F}_{e}\subseteq\mathcal{F}$. Summing the above for all $\bar{e}\leq
e-1$, we get that for any $f\in\mathcal{F}_{e}$,

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{t=1}^{\tau_{e}-1}Z^{e}(x_{s})\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle\leq
2\sum_{t=1}^{\tau_{e}-1}Z^{e}(x_{s})\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}+4c_{2}E\left(\log^{3}(T)\sup_{\tau\leq
T}\left(\tau\mathsf{Rad}^{2}_{\tau}(\mathcal{F})\right)+2\log(E/\delta)\right)$
$\displaystyle\leq
2{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}+4c_{2}\left(\log^{4}(T)\sup_{\tau\leq
T}\left(\tau\mathsf{Rad}^{2}_{\tau}(\mathcal{F})\right)+2\log(T)\log(E/\delta)\right),$

where the last line follows by using the definition of $\mathcal{F}_{e}$, and
that $E\leq\lceil\log(T)\rceil$, and that
$\mathcal{F}_{e}\subseteq\mathcal{F}$.

  3. $(c)$

Starting from part-$(b)$, we first note that

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{s=1}^{\tau_{e}-1}Z_{s}\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}.$
(34)

Additionally, also note that

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{s=1}^{\tau_{e}-1}Z_{s}\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{\bar{e}=1}^{e-1}\sum_{s=\tau_{\bar{e}}}^{\tau_{\bar{e}+1}-1}Z_{s}\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle=\operatorname{\mathbb{E}}\left[\sum_{\bar{e}=1}^{e-1}\sum_{s=\tau_{\bar{e}}}^{\tau_{\bar{e}+1}-1}Z^{\bar{e}}(x_{s})\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle=\sum_{\bar{e}=1}^{e-1}\sum_{s=\tau_{\bar{e}}}^{\tau_{\bar{e}+1}-1}\operatorname{\mathbb{E}}_{x_{s}\sim\mu}\left[Z^{\bar{e}}(x_{s})\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle=\sum_{\bar{e}=1}^{e-1}\left(\tau_{\bar{e}+1}-\tau_{\bar{e}}\right)\operatorname{\mathbb{E}}_{x\sim\mu}\left[Z^{\bar{e}}(x)\left\|f(x)-{f^{\star}}(x)\right\|^{2}\right],$

where the last two lines use the fact that the query condition $Z^{\bar{e}}$
does not depend on the samples from rounds $t=\tau_{\bar{e}}$ to
$\tau_{\bar{e}+1}-1$. Plugging in the definition of $\bar{\mu}_{\bar{e}}$ in
the above, we get that

$\displaystyle\operatorname{\mathbb{E}}\left[\sum_{s=1}^{\tau_{e}-1}Z_{s}\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle=\sum_{\bar{e}=1}^{e-1}\left(\tau_{\bar{e}+1}-\tau_{\bar{e}}\right)\cdot\operatorname{\mathbb{E}}_{x\sim\bar{\mu}_{\bar{e}}}\left[\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle=(\tau_{e}-\tau_{1})\cdot\operatorname{\mathbb{E}}_{x\sim\bar{\nu}_{e}}\left[\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}\right]$
$\displaystyle=(\tau_{e}-\tau_{1})\cdot\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|^{2}_{\bar{\nu}_{e}},$
(35)

where in the second line, we used the fact that the sub-distribution
$\bar{\nu}_{e}\vcentcolon={}\frac{1}{\tau_{e}-\tau_{1}}\sum_{\bar{e}=1}^{e-1}(\tau_{{\bar{e}}+1}-\tau_{\bar{e}})\bar{\mu}_{\bar{e}}$.

Combining (34) and (35), we get that

$\displaystyle\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\bar{\nu}_{e}}$
$\displaystyle\leq\sqrt{\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\tau_{e}-1}}$

  4. $(d)$

The argument follows from the definition of the set $\mathcal{F}_{e}$ as any
function $f\in\mathcal{F}_{e}$ that satisfies

$\displaystyle\sum_{s=1}^{\tau_{e}-1}Z_{s}\left\|f(x_{s})-f_{s}(x_{s})\right\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)},$

also satisfies the constraint

$\displaystyle\sum_{s=1}^{\tau_{\bar{e}}-1}Z_{s}\left\|f(x_{s})-f_{s}(x_{s})\right\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)},$

for any $\bar{e}\leq e$, since the left hand side consists of lesser number of
terms and all terms are non-negative. Thus,
$\mathcal{F}_{e}\subseteq\mathcal{F}_{\bar{e}}$.

  5. $(e)$

Recall that for any $e\leq E-1$, the sub-probability measure
$\bar{\mu}_{e}(x)\vcentcolon={}Z^{e}(x)\mu(x)$ where
$Z^{e}(x)=\mathbf{1}\\{\min_{g\in\mathcal{F}_{e}}\|g(x)\|\leq\Delta_{e}(x)\\}$,
and $\Delta_{e}(x)=\max_{f^{\prime},f\in\mathcal{F}_{e}}\leavevmode\nobreak\
\|f(x)-f^{\prime}(x)\|$. First note that for any $\bar{e}\leq e$,

$\displaystyle\Delta_{e}(x)=\max_{f^{\prime},f\in\mathcal{F}_{e}}\leavevmode\nobreak\
\|f(x)-f^{\prime}(x)\|\leq\max_{f^{\prime},f\in\mathcal{F}_{\bar{e}}}\leavevmode\nobreak\
\|f(x)-f^{\prime}(x)\|=\Delta_{\bar{e}}(x),$

where the inequality above holds because
$\mathcal{F}_{e}\subseteq\mathcal{F}_{{\bar{e}}}$ due to part-(d) above.
Furthermore,

$\displaystyle\min_{g\in\mathcal{F}_{e}}\|g(x)\|$
$\displaystyle\geq\min_{g\in\mathcal{F}_{{\bar{e}}}}\|g(x)\|,$

again because $\mathcal{F}_{e}\subseteq\mathcal{F}_{{\bar{e}}}$. Thus,

$\displaystyle Z^{e}(x)$
$\displaystyle=\mathbf{1}\\{\min_{g\in\mathcal{F}_{e}}\|g(x)\|\leq\Delta_{e}(x)\\}\leq\mathbf{1}\\{\min_{g\in\mathcal{F}_{\bar{e}}}\|g(x)\|\leq\Delta_{\bar{e}}(x)\\}\leq
Z^{\bar{e}}(x).$

The above implies that $\bar{\mu}_{e}\leq\bar{\mu}_{\bar{e}}$.

∎

######  Lemma 15.

Let $\varepsilon_{0},\gamma_{0}\geq 0$, and ${f^{\star}}\in\mathcal{F}$. Then,
for any sub distribution $\bar{\mu}$ such that
$\operatorname{\mathbb{E}}_{x\sim\bar{\mu}}\left[\mathbf{1}\\{x\in\mathcal{X}\\}\right]>0$,
$\varepsilon\geq\varepsilon_{0}$ and $\gamma\geq\gamma_{0}$,

$\displaystyle\frac{\varepsilon^{2}}{\gamma^{2}}\operatorname{Pr}_{x\sim\bar{\mu}}\left(\exists
f\in\mathcal{F}\leavevmode\nobreak\ :\leavevmode\nobreak\
\|f(x)-{f^{\star}}(x)\|>\varepsilon,\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\bar{\mu}}\leq\gamma\right)\leq\theta^{\mathrm{val}}\left(\mathcal{F},\varepsilon_{0},\gamma_{0};{f^{\star}}\right).$

###### Proof.

The key idea in the proof is to go from sub distributions to distributions,
and then invoking the definition of $\theta$ from Definition 2. Define
$\kappa=\operatorname{\mathbb{E}}_{x\sim\bar{\mu}}\left[\mathbf{1}\\{x\in\mathcal{X}\\}\right]$.
Since $0<\kappa\leq 1$, we can define a probability measure $\mu$ such that
$\mu(x)=\nicefrac{{\bar{\mu}(x)}}{{\kappa}}$. Thus, for any
$\varepsilon\geq\varepsilon_{0}$ and $\gamma\geq\gamma_{0}$,

$\displaystyle\frac{\varepsilon^{2}}{\gamma^{2}}\operatorname{Pr}_{x\sim\bar{\mu}}\left(\exists
f\in\mathcal{F}\leavevmode\nobreak\ :\leavevmode\nobreak\
\|f(x)-{f^{\star}}(x)\|>\varepsilon,\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\bar{\mu}}\leq\gamma\right)$
$\displaystyle=\frac{\varepsilon^{2}}{\nicefrac{{\gamma^{2}}}{{k}}}\operatorname{Pr}_{x\sim\mu}\left(\exists
f\in\mathcal{F}\leavevmode\nobreak\ :\leavevmode\nobreak\
\|f(x)-{f^{\star}}(x)\|>\varepsilon,\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\bar{\mu}}\leq\gamma\right)$
$\displaystyle\leq\frac{\varepsilon^{2}}{\nicefrac{{\gamma^{2}}}{{k}}}\operatorname{Pr}_{x\sim\mu}\left(\exists
f\in\mathcal{F}\leavevmode\nobreak\ :\leavevmode\nobreak\
\|f(x)-{f^{\star}}(x)\|>\varepsilon,\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\mu}\leq\nicefrac{{\gamma}}{{\sqrt{k}}}\right)$
$\displaystyle=\frac{\varepsilon^{2}}{\bar{\gamma}^{2}}\operatorname{Pr}_{x\sim\mu}\left(\exists
f\in\mathcal{F}\leavevmode\nobreak\ :\leavevmode\nobreak\
\|f(x)-{f^{\star}}(x)\|>\varepsilon,\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\mu}\leq\bar{\gamma}\right)$
$\displaystyle\leq\sup_{\varepsilon\geq\varepsilon_{0},\bar{\gamma}\geq\gamma_{0}}\frac{\varepsilon^{2}}{\bar{\gamma}^{2}}\operatorname{Pr}_{x\sim\mu}\left(\exists
f\in\mathcal{F}\leavevmode\nobreak\ :\leavevmode\nobreak\
\|f(x)-{f^{\star}}(x)\|>\varepsilon,\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\mu}\leq\bar{\gamma}\right),$

where in the second last line, we defined
$\bar{\gamma}=\nicefrac{{\gamma}}{{\sqrt{k}}}$, and the last line used the
fact that both $\varepsilon\geq\varepsilon_{0}$ and
$\bar{\gamma}\geq\gamma_{0}$. The final statement follows by noting the fact
that $\mu$ is a distribution and the definition of the disagreement
coefficient $\theta^{\mathrm{val}}\left(;\right)$ from Definition 2. ∎

The following technical result will be useful in bounding the query complexity
for Algorithm 4.

######  Lemma 16.

For any $t\leq T$, let $e(t)$ denotes the epoch number such that
$\tau_{e(t)}\leq t<\tau_{e(t)+1}$. Let ${f^{\star}}\in\mathcal{F}$ satisfy
Lemma 14, and let $\Delta_{e(t)}(x_{t})$ be defined in Algorithm 4. Then, for
any $\zeta>0$, with probability at least $1-\delta$,

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{e(t)}(x_{t})\geq\zeta\right\\}$
$\displaystyle\leq
12\log(T)\cdot\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\zeta^{2}}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\zeta}{2},\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{T};f^{\star}\right)+4\log(2/\delta).$

###### Proof.

Recall the definition of the query rule $Z^{e}$ given in (33), and note that
the function $Z^{e}$ is independent of the samples
$\\{x_{t}\\}_{t=\tau_{e}}^{\tau_{e+1}-1}$ chosen by the nature for time steps
at epoch $e$. Additionally, also recall that at every time step, $x_{t}$ is
sampled independently from the distribution $\mu$. Thus, using the query
condition $Z^{e}$, we can define the sub-probability measure

$\displaystyle\bar{\mu}_{e}\vcentcolon={}\mu(x)Z^{e}(x),$ (36)

such that $\bar{\mu}_{e}(x)=\mu(x)$ whenever $Z_{e}(x)=1$ and is $0$
otherwise. Furthermore, for any $e\in E-1$, we define the sub-probability
measure $\bar{\nu}_{e}$ as

$\displaystyle\bar{\nu}_{e}$
$\displaystyle=\frac{1}{\tau_{e}-\tau_{1}}\sum_{\bar{e}=1}^{e-1}(\tau_{{\bar{e}}+1}-\tau_{{\bar{e}}})\bar{\mu}_{\bar{e}}.$
(37)

We now move to the main proof. First fix any epoch $e\leq E-1$, and consider
any round $t\in[\tau_{e},\tau_{e+1}-1]$. Using the definition of
$\Delta_{e}(x_{t})$ and definition of $Z^{e}$ from (33) in the above, we get
that

$\displaystyle\operatorname{\mathbb{E}}_{x_{t}\sim\mu}\left[Z_{t}\mathbf{1}\left\\{\Delta_{e}(x_{t})>\zeta\right\\}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{x\sim\mu}\left[Z^{e}(x_{t})\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{e}}\|f(x_{t})-f^{\prime}(x_{t})\|>\zeta\right\\}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x\sim\mu}\left[Z^{e}(x_{t})\mathbf{1}\left\\{\sup_{f\in\mathcal{F}_{e}}\|f(x_{t})-{f^{\star}}(x_{t})\|>\frac{\zeta}{2}\right\\}\right]$

where the second line follows because ${f^{\star}}\in\mathcal{F}_{e}$, and
because
$\sup_{f,f^{\prime}\in\mathcal{F}_{e}}\|f(x_{t})-f^{\prime}(x_{t})\|\leq
2\sup_{f\in\mathcal{F}_{e}}\|f(x_{t})-{f^{\star}}(x_{t})\|$ due to Triangle
inequality. Plugging in the definition of $\bar{\mu}_{e}$ from (36) in the
above we get that

$\displaystyle\operatorname{\mathbb{E}}_{x_{t}\sim\mu}\left[Z_{t}\mathbf{1}\left\\{\Delta_{e}(x_{t})>\zeta\right\\}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x\sim\bar{\mu}_{e}}\left[\mathbf{1}\left\\{\sup_{f\in\mathcal{F}_{e}}\|f(x_{t})-{f^{\star}}(x_{t})\|>\frac{\zeta}{2}\right\\}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x\sim\bar{\mu}_{\bar{e}}}\left[\mathbf{1}\left\\{\sup_{f\in\mathcal{F}_{e}}\|f(x_{t})-{f^{\star}}(x_{t})\|>\frac{\zeta}{2}\right\\}\right].$
(38)

for all $\bar{e}\leq e$, where the last inequality follows from Lemma
14-$(e)$. Since the above holds for all $\bar{e}\leq e$, we immediately get
that

$\displaystyle\operatorname{\mathbb{E}}_{x_{t}\sim\mu}\left[Z_{t}\mathbf{1}\left\\{\Delta_{e}(x_{t})>\zeta\right\\}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x\sim\bar{\nu}_{\bar{e}}}\left[\mathbf{1}\left\\{\sup_{f\in\mathcal{F}_{e}}\|f(x_{t})-{f^{\star}}(x_{t})\|>\frac{\zeta}{2}\right\\}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{x\sim\bar{\nu}_{\bar{e}}}\left[\mathbf{1}\left\\{\exists
f\in\mathcal{F}_{e}\leavevmode\nobreak\ :\leavevmode\nobreak\
\|f(x)-{f^{\star}}(x)\|>\frac{\zeta}{2}\right\\}\right],$ (39)

where the sub-probability measure $\bar{\nu}_{\bar{e}}$ is defined in (37).
Additionally, recall that Lemma 14-$(b)$ implies that with probability at
least $1-\delta$ any $f\in\mathcal{F}_{e}$ satisfies

$\displaystyle\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\bar{\nu}_{e}}$
$\displaystyle\leq\sqrt{\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\tau_{e}-1}}.$
(40)

Conditioning on the above event, and plugging it in (39), we get that

$\displaystyle\operatorname{\mathbb{E}}_{x_{t}\sim\mu}\left[Z_{t}\mathbf{1}\left\\{\Delta_{e}(x_{t})>\zeta\right\\}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{x\sim\bar{\nu}_{\bar{e}}}\left[\mathbf{1}\left\\{\exists
f\in\mathcal{F}_{e}\leavevmode\nobreak\ :\leavevmode\nobreak\
\|f(x)-{f^{\star}}(x)\|>\frac{\zeta}{2},\left\|f(x_{s})-{f^{\star}}(x_{s})\right\|_{\bar{\nu}_{e}}\leq\sqrt{\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\tau_{e}-1}}\right\\}\right]$
$\displaystyle\leq
4\cdot\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{(\tau_{e}-1)\zeta^{2}}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\zeta}{2},\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\tau_{e}-1};f^{\star}\right),$
(41)

where the last inequality uses Lemma 15.

Summing up the bound in (41) for each term $t=1$ to $T$, we get that

$\displaystyle\sum_{t=1}^{T}\operatorname{\mathbb{E}}_{x_{t}}\left[Z_{t}\mathbf{1}\left\\{\Delta_{e}(x_{t})>\zeta\right\\}\right]$
$\displaystyle=\sum_{e=1}^{E-1}\sum_{t=\tau_{e}}^{\tau_{e+1}-1}\operatorname{\mathbb{E}}_{x_{t}}\left[Z_{t}\mathbf{1}\left\\{\Delta_{e}(x_{t})>\zeta\right\\}\right]$
$\displaystyle\leq
4\sum_{e=1}^{E-1}\left(\tau_{e+1}-\tau_{e}\right)\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{(\tau_{e}-1)\zeta^{2}}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\zeta}{2},\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\tau_{e}-1};f^{\star}\right)$
$\displaystyle\leq
8\sum_{e=1}^{E-1}\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\zeta^{2}}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\zeta}{2},\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\tau_{e}-1};f^{\star}\right)$
$\displaystyle\leq
8\sum_{e=1}^{E-1}\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\zeta^{2}}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\zeta}{2},\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{T};f^{\star}\right)$
$\displaystyle\leq
8\log(T)\cdot\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\zeta^{2}}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\zeta}{2},\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{T};f^{\star}\right)$

where the second inequality uses the fact that $\tau_{e+1}=2\tau_{e}$ and that
$\tau_{1}=1$, the third inequality holds due to monotonicity of
$\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\zeta}{2},\cdot;f^{\star}\right)$
and the last line simply plugs in the value of $E=\log(T)$.

Using Lemma 4 with the above bound for the sequence of random variable
$X_{t}=Z_{t}\mathbf{1}\left\\{\Delta_{e}(x_{t})>\zeta\right\\}$, we get that
with probability at least $1-\delta$,

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{e}(x_{t})>\zeta\right\\}$
$\displaystyle\leq\frac{3}{2}\sum_{t=1}^{T}\operatorname{\mathbb{E}}_{x_{t}}\left[Z_{t}\mathbf{1}\left\\{\Delta_{e}(x_{t})>\zeta\right\\}\right]+4\log(2/\delta)$
$\displaystyle\leq
12\log(T)\cdot\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\zeta^{2}}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\zeta}{2},\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{T};f^{\star}\right)+4\log(2/\delta).$

The final result follows by taking a union bound of the above and the event in
(40). ∎

####  C.2.2 Regret Bound

For the ease of notation, through the proofs in this section we define the
operators ${\pi^{\star}}$ as

$\displaystyle{\pi^{\star}}(x)=\operatorname*{argmax}_{k}\phi({f^{\star}}(x))[k].$

Furthermore, recall that $\widehat{y}_{t}$ denotes the action chosen by the
learner at round $t$ of interaction. Starting from the definition of the
regret, we get that

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}\operatorname{Pr}\left(\widehat{y}_{t}\neq
y_{t}\right)-\operatorname{Pr}\left({\pi^{\star}}(x_{t})\neq y_{t}\right)$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}\cdot\left\lvert\operatorname{Pr}\left(y_{t}={\pi^{\star}}(x_{t})\right)-\operatorname{Pr}\left(y_{t}=\widehat{y}_{t}\right)\right\rvert$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}\cdot\left\lvert\phi({f^{\star}}(x_{t}))[{\pi^{\star}}(x_{t})]-\phi({f^{\star}}(x_{t}))[\widehat{y}_{t}]\right\rvert$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}\cdot\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t}),$

where the last inequality plugs in the definition of $\mathrm{Gap}$ from (59).
Let $\varepsilon>0$ be a free parameter. We can decompose the above regret
bound further as:

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})\leq\varepsilon\\}\cdot\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})$

Using the fact that
$\mathsf{y}_{t}(x_{t})=\operatorname*{argmax}_{k\in[K]}\phi(f_{t}(x))[k]$ in
the above along with the definition of $\mathrm{Gap}$ and Lemma 12, we get
that

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})\leq\varepsilon\\}\cdot\varepsilon$
$\displaystyle\hskip
72.26999pt+2\gamma\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}\cdot\varepsilon$
$\displaystyle\hskip
72.26999pt+2\gamma\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}\cdot\varepsilon$
$\displaystyle\hskip
72.26999pt+2\gamma\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\hskip
72.26999pt+2\gamma\sum_{t=1}^{T}\bar{Z}_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle=T_{\varepsilon}\cdot\varepsilon+2\gamma\cdot T_{A}+2\gamma\cdot
T_{B}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|,$

where the second inequality holds because
$\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})\leq\varepsilon$ implies that
$\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon$ whenever
$\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})$. In the last line we plugged in the
definition of $T_{\varepsilon}$, and defined $\mathtt{T}_{A}$ and
$\mathtt{T}_{B}$ as the second term and the last term respectively. We bound
term separately below:

  1. $\bullet$

Bound on $\mathtt{T}_{A}$: Note that whenever $Z_{t}=1$, we choose
$\widehat{y}_{t}=\operatorname*{argmax}_{k}\phi(f_{t}(x_{t}))[k]$. Thus,

$\displaystyle\mathtt{T}_{A}$
$\displaystyle=\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathrm{Gap}({f^{\star}}(x_{t}),\widehat{y}_{t})>\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|>\varepsilon/2\gamma\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$

where the second line follows from Lemma 12 and because
$\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})$. Using the fact that
$\mathbf{1}\\{a\geq b\\}\leq\nicefrac{{a}}{{b}}$ for all $a,b\geq 0$, we get
that

$\displaystyle\mathtt{T}_{A}\leq
4\gamma\sum_{t=1}^{T}Z_{t}\frac{\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|^{2}}{\varepsilon}.$
(42)

  2. $\bullet$

Bound on $\mathtt{T}_{B}$: Fix any $t\leq T$, and let $e$ be such that
$\tau_{e}\leq t<\tau_{e+1}$. Next, note that from Lemma 14, we have

$\displaystyle\|{f^{\star}}(x_{t})-g_{t}(x_{t})\|\leq\Delta_{e}(x_{t}).$ (43)

Plugging in the definition of $Z_{t}$, we note that

$\displaystyle\mathtt{T}_{B}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(g_{t}(x_{t}))>2\gamma\Delta_{e}(x_{t}),\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\|g_{t}(x_{t})-{f^{\star}}(x_{t})\|>\Delta_{e}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon\\},$

where the second inequality is due Lemma 12 and by noting that
$\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})$ and that when $Z_{t}=0$, we choose
$\widehat{y}_{t}=\operatorname*{argmax}_{k}\phi(g_{t}(x_{t}))[k]$. However,
note that the term inside the indicator contradicts (43) (which always holds).
Thus,

$\displaystyle\mathtt{T}_{B}$ $\displaystyle=0.$ (44)

Combining the bounds (42) and (44), we get that:

$\displaystyle\mathrm{Reg}_{T}$ $\displaystyle\leq\varepsilon
T_{\varepsilon}+8\gamma^{2}\sum_{t=1}^{T}Z_{t}\frac{\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|^{2}}{\varepsilon}$
$\displaystyle\leq\varepsilon
T_{\varepsilon}+\frac{8\gamma^{2}}{\varepsilon}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)},$

where the last inequality is due to Lemma 14.

Since $\varepsilon$ is a free parameter above, the final bound follows by
choosing the best parameter $\varepsilon$, and by plugging in the form of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{\ell_{\phi}}_{\delta}(\mathcal{F},T)}$.

####  C.2.3 Total Number of Queries

Let $N_{T}$ denote the total number of expert queries made by the learner
within $T$ rounds of interactions. For the ease of notation, define
$\Delta_{t}(x_{t})=\Delta_{e(t)}(x_{t})$ where $e(t)$ denotes the epoch number
for which $\tau_{e(t)}\leq t<\tau_{e(t)+1}$. Additionally, let $\varepsilon>0$
be a free parameter. Thus,

$\displaystyle N_{T}$ $\displaystyle=\sum_{t=1}^{T}Z_{t}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(g_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t})\\}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(g_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(g_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(g_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(g_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})>\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
$\displaystyle=T_{\varepsilon}+\mathtt{T}_{D}+\mathtt{T}_{E},$

where in the last line we used the definition of $T_{\varepsilon}$ and defined
$\mathtt{T}_{D}$ and $\mathtt{T}_{E}$ respectively, which we bound separately
below.

  1. $\bullet$

Bound on $\mathtt{T}_{D}$. From Lemma 14 recall that
$\|{f^{\star}}(x_{t})-g_{t}(x_{t})\|\leq\Delta_{e}(x_{t})$. Thus, for any
$x_{t}$ for which $\|g_{t}(x_{t})\|\leq\Delta_{e}(x_{t})$, Lemma 13 implies
that

$\displaystyle\mathtt{Margin}({f^{\star}}(x_{t}))\leq
2\gamma\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|+\mathtt{Margin}(g_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t})+\mathtt{Margin}(f_{t}(x_{t})).$

The above implies that

$\displaystyle\mathtt{T}_{D}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(g_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq
4\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
$\displaystyle\leq 0,$

where the last line follows from the fact that all the conditions inside the
indictor can not hold simultaneously for any $\varepsilon>0$.

  2. $\bullet$

Bound on $\mathtt{T}_{E}$. We note that

$\displaystyle\mathtt{T}_{E}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(g_{t}(x_{t}))\leq
2\gamma\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})>\nicefrac{{\varepsilon}}{{4\gamma}}\\}$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{t}(x_{t})\geq\nicefrac{{\varepsilon}}{{4\gamma}}\right\\}$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{e(t)}(x_{t})\geq\nicefrac{{\varepsilon}}{{4\gamma}}\right\\}.$

Using Lemma 16 with $\zeta=\nicefrac{{\varepsilon}}{{4\gamma}}$ to bound the
term on the right hand side above, we get that with probability at least
$1-2\delta$,

$\displaystyle\mathtt{T}_{E}$ $\displaystyle\leq
O\left(\log(T)\gamma^{2}\cdot\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\varepsilon^{2}}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\varepsilon}{8\gamma},\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{T};f^{\star}\right)+\log(2/\delta)\right).$

Gathering the bounds above, we get that

$\displaystyle N_{T}\leq
T_{\varepsilon}+O\left(\log(T)\gamma^{2}\cdot\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{\varepsilon^{2}}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\frac{\varepsilon}{8\gamma},\frac{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}}{T};f^{\star}\right)+\log(2/\delta)\right).$

Since $\varepsilon$ is a free parameter above, the final bound follows by
choosing the best parameter $\varepsilon$, and by plugging in the form of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\Psi}^{\ell_{\phi}}_{\delta}(\mathcal{F};T)}$.

###  C.3 Proof of Corollary 1

Note that the Tsybakov noise condition implies that there exists constants
$c,\rho\geq 0$ such that for all $\varepsilon\in(0,1)$:

$\displaystyle\operatorname{Pr}_{x\sim\mu}\left(\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\right)\leq
c\varepsilon^{\rho}.$

Thus, using Lemma 4, we get that

$\displaystyle T_{\varepsilon}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
$\displaystyle\leq\frac{3T}{2}\operatorname{Pr}_{x\sim\mu}\left(\mathtt{Margin}({f^{\star}}(x))\leq\varepsilon\right)+4\log(2/\delta)$
$\displaystyle\leq 2cT\varepsilon^{\rho}+4\log(2/\delta).$

Using the above in the bound for Theorem 2, we get that for any
$\varepsilon>0$,

$\displaystyle\mathrm{Reg}_{T}$ $\displaystyle\lesssim
cT\varepsilon^{\rho+1}+\frac{\gamma^{2}}{\lambda\varepsilon}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}+\log(1/\delta),$

Setting $\varepsilon=\left(\frac{\gamma^{2}}{\lambda
CT}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}\right)^{\frac{1}{\rho+2}}$
in the above implies that

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle\lesssim\left(\frac{\gamma^{2}}{\lambda}c^{\frac{1}{\rho+1}}\right)^{\frac{\rho+1}{\rho+2}}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}\right)^{\frac{\rho+1}{\rho+2}}\cdot(T)^{\frac{1}{\rho+2}}+\log(1/\delta).$

Similarly, we can bound the query complexity bound for any $\varepsilon>0$ as:

$\displaystyle N_{T}$ $\displaystyle\lesssim
T\varepsilon^{\rho}+\frac{\gamma^{2}}{\lambda\varepsilon^{2}}\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\nicefrac{{\varepsilon}}{{8\gamma}},\nicefrac{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}}}{{T}};f^{\star}\right)+\log(1/\delta).$

Setting $\varepsilon=\left(\frac{\gamma^{2}}{\lambda
T}\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\nicefrac{{\varepsilon}}{{8\gamma}},\nicefrac{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}}}{{T}};f^{\star}\right)\right)^{\frac{1}{\rho+2}}$
in the above implies that

$\displaystyle
N_{T}\leq\left(\frac{\gamma^{2}}{\lambda}\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}\cdot\theta^{\mathrm{val}}\left(\mathcal{F},\nicefrac{{\varepsilon}}{{8\gamma}},\nicefrac{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{\ell_{\phi}}}(\mathcal{F};T)}}}{{T}};f^{\star}\right)\right)^{\frac{\rho}{\rho+2}}\cdot
T^{\frac{2}{\rho+2}}.$

###  C.4 Proof of Theorem 4

Before delving into the proof, we recall the relevant notation. In Algorithm
2,

  1. $\bullet$

The label $y_{t}\sim{f^{\star}}(x_{t})$ as given in (2). 888Throughout the
proof of Theorem 4, we use the link function $\phi(z)=z$, and observe that
$\lambda=\gamma=1$ for this choice of $\phi$. This corresponds to
$\ell_{\phi}$ being the square loss.

  2. $\bullet$

The function
$\mathtt{SelectAction}(f_{t}(x_{t}))=\operatorname*{argmax}_{k}f_{t}(x_{t})[k]$.

  3. $\bullet$

For any vector $v\in\mathbb{R}^{K}$, the margin is given by the gap between
the value at the largest and the second largest coordinate, i.e.

$\displaystyle\mathtt{Margin}(v)=v[k^{\star}]-\max_{k\neq k^{\star}}v[k],$

where $k^{\star}\in\operatorname*{argmax}_{k\in[K]}v[k]$.

  4. $\bullet$

We also define
$T_{\varepsilon}=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
to denote the number of samples within $T$ rounds of interaction for which the
margin w.r.t. ${f^{\star}}$ is smaller than $\varepsilon$.

  5. $\bullet$

The Inverse Gap Weighting (IGW) distribution
$p_{t}=\mathrm{IGW}_{\varepsilon}(f_{t}(x_{t}))$ is given by:

$\displaystyle
p_{t}[y]=\begin{cases}\frac{1}{K+\varepsilon\left(f_{t}(x_{t})[y_{t}^{\star}]-f_{t}(x_{t})[y]\right)}&\text{if}\leavevmode\nobreak\
y\neq y_{t}^{\star}\\\ 1-\sum_{y\neq
y_{t}^{\star}}p_{t}[y]&\text{if}\leavevmode\nobreak\
y=y_{t}^{\star}\end{cases},$

where $y_{t}^{\star}=\operatorname*{argmax}f_{t}(x_{t})[y]$.

  6. $\bullet$

We define the function
$\mathrm{Gap}:\mathbb{R}^{K}\times[K]\mapsto\mathbb{R}^{+}$ as

$\displaystyle\mathrm{Gap}(u,k)=\max_{k^{\prime}}u[k^{\prime}]-u[k].$ (45)

to denote the gap between the largest and the $k$-th coordinate of $v$.

  7. $\bullet$

For ease of notation, we define the functions ${\pi^{\star}}$ such that

$\displaystyle{\pi^{\star}}(x)=\operatorname*{argmax}_{k}\phi({f^{\star}}(x))[k].$

####  C.4.1 Supporting Technical Results

######  Lemma 17.

With probability at least $1-\delta$, the function ${f^{\star}}\in\mathcal{F}$
satisfies the following for all $t\leq T$:

$\displaystyle\sum_{s=1}^{t}Z_{s}(f_{s}(x_{s})[\widehat{y}_{s}]-{f^{\star}}(x_{s})[\widehat{y}_{s}])^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}$

where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}=2{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{sq}}(\mathcal{F};T)}+8\log(T/\delta)$.
Thus, for all $t\leq T$, ${f^{\star}}\in\mathcal{F}_{t}$.

###### Proof.

We first note that we do not query oracle when $Z_{s}=0$. Hence, we will
ignore the terms for which $Z_{s}=0$. Now note that the regret guarantee for
the oracle, given in (9) ensures that

$\displaystyle\sum_{s=1}^{t}Z_{s}(f_{s}(x_{s})[\widehat{y}_{s}]-\mathbb{Q}_{s})^{2}-\sum_{s=1}^{t}Z_{s}({f^{\star}}(x_{s})[\widehat{y}_{s}]-\mathbb{Q}_{s})^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{sq}}(\mathcal{F};T)}.$

Taking expectation on both sides yields

$\displaystyle\mathbb{E}\left[\sum_{s=1}^{t}Z_{s}(f_{s}(x_{s})[\widehat{y}_{s}]-\mathbb{Q}_{s})^{2}-\sum_{s=1}^{t}Z_{s}({f^{\star}}(x_{s})[\widehat{y}_{s}]-\mathbb{Q}_{s})^{2}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{s=1}^{t}Z_{s}\Big{(}(f_{s}(x_{s})[\widehat{y}_{s}])^{2}-2\cdot\mathbb{Q}_{s}\cdot
f_{s}(x_{s})[\widehat{y}_{s}]+2\cdot\mathbb{Q}_{s}\cdot{f^{\star}}(x_{s})[\widehat{y}_{s}]-({f^{\star}}(x_{s})[\widehat{y}_{s}])^{2}\Big{)}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{s=1}^{t}Z_{s}(f_{s}(x_{s})[\widehat{y}_{s}]-{f^{\star}}(x_{s})[\widehat{y}_{s}])^{2}\right]$
$\displaystyle\leq$
$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{sq}}(\mathcal{F};T)}$

where in the third line we use the fact that
$\operatorname{\mathbb{E}}\left[\mathbb{Q}_{s}\right]={f^{\star}}(x_{s})[\widehat{y}_{s}]$.
Applying the concentration result (Lemma 4), we arrive at

$\displaystyle\sum_{s=1}^{t}Z_{s}(f_{s}(x_{s})[\widehat{y}_{s}]-{f^{\star}}(x_{s})[\widehat{y}_{s}])^{2}\leq
2{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{sq}}(\mathcal{F};T)}+8\log(1/\delta).$

We complete the proof by taking a union bound for all $t\in[T]$. ∎

For the rest of the proof, we condition on the $1-\delta$ probability event
that Lemma 17 holds. We first recall the following property of the Inverse Gap
Weighting (IGW) sampling distribution.

######  Lemma 18 (Foster and Rakhlin (2020)).

Let $K\geq 2$, $u,v\in[0,1]^{K}$, and suppose
$\widehat{y}\sim\mathrm{IGW}_{\varepsilon}(v)$. Then, we have

$\operatorname{\mathbb{E}}_{\widehat{y}}\left[{\max_{y}u[y]-u[\widehat{y}]}\right]\leq\frac{K}{\varepsilon}+\varepsilon\operatorname{\mathbb{E}}_{\widehat{y}}\left[\left(u[\widehat{y}]-v[\widehat{y}]\right)^{2}\right].$

######  Lemma 19.

Let ${f^{\star}}$ satisfy Lemma 17, and let $w_{t}$ be defined in (10) in
Algorithm 2. Then, for any $\zeta>0$,

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[\widehat{y}_{t}]-f^{\prime}(x_{t})[\widehat{y}_{t}]\geq\zeta\right\\}$
$\displaystyle=\left(\frac{4{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{\zeta^{2}}+1\right)\check{\mathfrak{E}}(\mathcal{F},\zeta/2;f^{\star}).$

where $\check{\mathfrak{E}}$ denotes the eluder dimension given in Definition
8.

###### Proof.

We have

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[\widehat{y}_{t}]-f^{\prime}(x_{t})[\widehat{y}_{t}]\geq\zeta\right\\}$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\sup_{f\in\mathcal{F}_{t}}f(x_{t})[\widehat{y}_{t}]-f^{\star}(x_{t})[\widehat{y}_{t}]\geq\zeta/2\right\\}$
$\displaystyle\leq$
$\displaystyle\left(\frac{4{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{\zeta^{2}}+1\right)\check{\mathfrak{E}}(\mathcal{F},\zeta/2;f^{\star}).$

where the last inequality follows from Lemma 7. ∎

######  Lemma 20.

For any $t\in[T]$, assume $f^{\star}\in\mathcal{F}_{t}$ and
$\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon$. Then we have
$w_{t}\geq\varepsilon/2$ whenever $|\mathcal{A}_{t}|>1$.

###### Proof of Lemma 20.

When $|\mathcal{A}_{t}|>1$, we know there exists a function
$f^{\prime}\in\mathcal{F}_{t}$ for which the maximizer of $f^{\prime}(x_{t})$,
denoted by $y^{\prime}\in\mathcal{A}_{t}$, differs from $\pi^{\star}(x_{t})$.
Hence, we have

$\displaystyle\varepsilon$ $\displaystyle\leq
f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\star}(x_{t})[y^{\prime}]$
$\displaystyle=f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\prime}(x_{t})[\pi^{\star}(x_{t})]+f^{\prime}(x_{t})[\pi^{\star}(x_{t})]-f^{\star}(x_{t})[y^{\prime}]$
$\displaystyle\leq
f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\prime}(x_{t})[\pi^{\star}(x_{t})]+f^{\prime}(x_{t})[y^{\prime}]-f^{\star}(x_{t})[y^{\prime}]$
$\displaystyle\leq 2w_{t}$

from which we conclude $w_{t}\geq\varepsilon/2$. ∎

######  Lemma 21.

Assume $f^{\star}\in\mathcal{F}_{t}$ for all $t\in[T]$. Suppose there exists
some $t^{\prime}\in[T]$ such that $\xi_{t}=0$ for all $t\leq t^{\prime}$. Then
we have

$\displaystyle\sum_{t=1}^{t^{\prime}}Z_{t}w_{t}\leq
T_{\varepsilon}+112K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log(4/(\delta\varepsilon)),$

for any fixed $\varepsilon$ with probability at least $1-\delta$.

###### Proof.

We first note that

$\displaystyle\sum_{t=1}^{t^{\prime}}Z_{t}w_{t}=$ $\displaystyle\
\sum_{t=1}^{t^{\prime}}Z_{t}w_{t}\mathbf{1}\left\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\right\\}+\sum_{t=1}^{t^{\prime}}Z_{t}w_{t}\mathbf{1}\left\\{\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon\right\\}.$

The first term is exactly $T_{\varepsilon}$. Now we consider the second term.
Since $f^{\star}\in\mathcal{F}_{t}$, we always have
$\pi^{\star}(x_{t})\in\mathcal{A}_{t}$ for all $t\in[T]$. Hence, whenever
$Z_{t}$ is zero, we have $\mathcal{A}_{t}=\\{\pi^{\star}(x_{t})\\}$ and thus
we do not incur any regret. Hence, we know
$Z_{t}w_{t}\mathbf{1}\left\\{\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon\right\\}$
is either 0 or at least $\varepsilon/2$ by Lemma 20. We denote
$\varepsilon^{\prime}\coloneqq\varepsilon/2$ for notational simplicity. Let us
fix an integer $m>1/\varepsilon^{\prime}$, whose value will be specified
later. We divide the interval $[\varepsilon^{\prime},1]$ into bins of width
$1/m$ and conduct a refined study:

$\displaystyle\sum_{t=1}^{t^{\prime}}Z_{t}w_{t}\mathbf{1}\left\\{\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon\right\\}$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{t^{\prime}}\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}Z_{t}w_{t}\cdot\mathbf{1}\left\\{Z_{t}w_{t}\in\left[\varepsilon^{\prime}+\frac{j}{m},\,\varepsilon^{\prime}+\frac{j+1}{m}\right]\right\\}$
$\displaystyle\leq$
$\displaystyle\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}\left(\varepsilon^{\prime}+\frac{j+1}{m}\right)\sum_{t=1}^{t^{\prime}}Z_{t}\mathbf{1}\left\\{w_{t}\geq\varepsilon^{\prime}+\frac{j}{m}\right\\}$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}\left(\varepsilon^{\prime}+\frac{j+1}{m}\right)\sum_{t=1}^{t^{\prime}}Z_{t}\mathbf{1}\left\\{\sup_{y\in\mathcal{A}_{t}}\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[y]-f^{\prime}(x_{t})[y]\geq\varepsilon^{\prime}+\frac{j}{m}\right\\}$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}\left(\varepsilon^{\prime}+\frac{j+1}{m}\right)\sum_{t=1}^{t^{\prime}}Z_{t}\sup_{y\in\mathcal{A}_{t}}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[y]-f^{\prime}(x_{t})[y]\geq\varepsilon^{\prime}+\frac{j}{m}\right\\}$
$\displaystyle\leq$
$\displaystyle\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}\left(\varepsilon^{\prime}+\frac{j+1}{m}\right)\sum_{t=1}^{t^{\prime}}Z_{t}\sum_{y}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[y]-f^{\prime}(x_{t})[y]\geq\left(\varepsilon^{\prime}+\frac{j}{m}\right)\right\\}$
$\displaystyle\leq$
$\displaystyle\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}\left(\varepsilon^{\prime}+\frac{j+1}{m}\right)K\underbrace{\sum_{t=1}^{t^{\prime}}Z_{t}\mathbb{E}_{y\sim
p_{t}}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[y]-f^{\prime}(x_{t})[y]\geq\left(\varepsilon^{\prime}+\frac{j}{m}\right)\right\\}}_{(*)}$

where in the third inequality we replace the supremum over $a$ by the
summation, and in the last inequality we further replace it by the
expectation. Here recall that $p_{t}(a)$ is uniform when $\xi_{t}=0$, leading
to the extra $K$ factor. To deal with $(*)$, we first apply Lemma 4 to recover
the empirical $a_{t}$, and then apply Lemma 19 to get an upper bound via the
eluder dimension:

$\displaystyle(*)\leq$ $\displaystyle
2\sum_{t=1}^{t^{\prime}}Z_{t}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[\widehat{y}_{t}]-f^{\prime}(x_{t})[\widehat{y}_{t}]\geq\left(\varepsilon^{\prime}+\frac{j}{m}\right)\right\\}+8\log(\delta^{-1})$
$\displaystyle\leq$ $\displaystyle
2\left(\frac{4{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{\left(\varepsilon^{\prime}+\frac{j}{m}\right)^{2}}+1\right)\check{\mathfrak{E}}(\mathcal{F},\varepsilon^{\prime}/2;f^{\star})+8\log(\delta^{-1})$
$\displaystyle\leq$
$\displaystyle\frac{10{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{\left(\varepsilon^{\prime}+\frac{j}{m}\right)^{2}}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)+8\log(\delta^{-1})$

with probability at least $1-\delta$. Plugging $(*)$ back, we obtain

$\displaystyle\sum_{t=1}^{t^{\prime}}Z_{t}w_{t}\leq$
$\displaystyle\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}\left(\varepsilon^{\prime}+\frac{j+1}{m}\right)\cdot\frac{10K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{\left(\varepsilon^{\prime}+\frac{j}{m}\right)^{2}}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)+8mK\log(\delta^{-1})$
$\displaystyle=$ $\displaystyle
10K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}\frac{\varepsilon^{\prime}+\frac{j+1}{m}}{\left(\varepsilon^{\prime}+\frac{j}{m}\right)^{2}}+8mK\log(\delta^{-1})$
$\displaystyle\leq$ $\displaystyle
10K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)\left(\frac{\varepsilon^{\prime}+1/m}{\varepsilon^{\prime
2}}+\sum_{j=1}^{\left(1-\varepsilon^{\prime}\right)m-1}\frac{2}{\varepsilon^{\prime}+\frac{j}{m}}\right)+8mK\log(\delta^{-1})$
$\displaystyle\leq$ $\displaystyle
10K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}\frac{2}{\varepsilon^{\prime}+\frac{j}{m}}+8mK\log(\delta^{-1})$
$\displaystyle\leq$ $\displaystyle
20K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)\sum_{j=0}^{\left(1-\varepsilon^{\prime}\right)m-1}\int_{j-1}^{j}\frac{1}{\varepsilon^{\prime}+\frac{x}{m}}\mathrm{d}x+8mK\log(\delta^{-1})$
$\displaystyle=$ $\displaystyle
20K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)\int_{-1}^{(1-\varepsilon^{\prime})m-1}\frac{1}{\varepsilon^{\prime}+\frac{x}{m}}\mathrm{d}x+8mK\log(\delta^{-1})$
$\displaystyle=$ $\displaystyle
20K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)\cdot
m\log\left(\frac{1}{\varepsilon^{\prime}-m^{-1}}\right)+8mK\log(\delta^{-1})$

where for the second inequality, we use the fact that $(j+1)/m\leq 2j/m$ for
any $j\geq 1$; for the third inequality, we assume $m>1/\varepsilon^{\prime}$.
Setting $m=2/\varepsilon^{\prime}$, we arrive at

$\displaystyle\sum_{t=1}^{t^{\prime}}Z_{t}w_{t}\leq$ $\displaystyle
40K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)}{\varepsilon^{\prime}}\cdot\log(2/\varepsilon^{\prime})+16K\log(\delta^{-1})/\varepsilon^{\prime}$
$\displaystyle\leq$ $\displaystyle
56K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon^{\prime}/2;f^{\star}\right)}{\varepsilon^{\prime}}\cdot\log(2/(\delta\varepsilon^{\prime})),$

which completes the proof. Recall that we have set
$\varepsilon^{\prime}=\varepsilon/2$. ∎

######  Lemma 22.

For any $t\in[T]$ and any arm $y\in\mathcal{A}_{t}$, we have
$f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\star}(x_{t})[y]\leq 2w_{t}$.

###### Proof of Lemma 22.

For any $y\in\mathcal{A}_{t}$, by the definition of $\mathcal{A}_{t}$, there
must exists a function $f$ for which $y$ is the maximizer of ${f}(x_{t})$.
Hence,

$\displaystyle f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\star}(x_{t})[y]$
$\displaystyle=$ $\displaystyle
f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f(x_{t})[y]+f(x_{t})[y]-f^{\star}(x_{t})[y]$
$\displaystyle\leq$ $\displaystyle
f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f(x_{t})[\pi^{\star}(x_{t})]+f(x_{t})[y]-f^{\star}(x_{t})[y]$
$\displaystyle\leq$ $\displaystyle 2w_{t}.$

∎

######  Lemma 23.

Whenever

$T_{\varepsilon}+112K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log(4/(\delta\varepsilon))<\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}},$

we have $\xi_{1}=\xi_{2}=\dots=\xi_{T}=0$ with probability at least
$1-\delta$.

###### Proof of Lemma 23.

We prove it via contradiction. Assume the inequality holds but there exists
$t^{\prime}$ for which $\xi_{t^{\prime}}=1$. Without loss of generality, we
assume that $\xi_{t}=0$ for all $t<t^{\prime}$, namely that $t^{\prime}$ is
the first time that $\xi_{t^{\prime}}$ is 1. Then by definition of
$\xi_{t^{\prime}}$, we have

$\displaystyle\sum_{s=1}^{t^{\prime}-1}Z_{s}w_{s}\geq\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}.$

On the other hand, by Lemma 21, we have

$\displaystyle\sum_{s=1}^{t^{\prime}-1}Z_{s}w_{s}\leq
T_{\varepsilon}+112K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log(4/(\delta\varepsilon)).$

The combination of the above two inequalities contradicts with the conditions.
∎

####  C.4.2 Regret Bound

We begin by showing the worst-case regret upper bound.

##### Worst-Case Regret Upper Bound.

We observe the definition of $\xi_{t}$ in Algorithm 2: the left term
$\sum_{s=1}^{t-1}Z_{s}w_{s}$ in the indicator is non-decreasing in $t$ while
the right term remains constant. This means that there exists a particular
time step $t^{\prime}\in[T]$ dividing the time horizon into two phases:
$\xi_{t}=0$ for all $t\leq t^{\prime}$ and $\xi_{t}=1$ for all $t>t^{\prime}$.
Now, we proceed to examine these two phases individually.

For all rounds before $t^{\prime}$, we can compute the expected partial regret
as

$\displaystyle\sum_{t=1}^{t^{\prime}}\operatorname{Pr}\left(\widehat{y}_{t}\neq
y_{t}\right)-\operatorname{Pr}\left({\pi^{\star}}(x_{t})\neq y_{t}\right)$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{t^{\prime}}\big{(}1-\operatorname{Pr}\left(\widehat{y}_{t}=y_{t}\right)\big{)}-\big{(}1-\operatorname{Pr}\left({\pi^{\star}}(x_{t})=y_{t}\right)\big{)}$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{t^{\prime}}\big{(}f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\star}(x_{t})[\widehat{y}_{t}]\big{)}$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{t^{\prime}}Z_{t}\Big{(}f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\star}(x_{t})[\widehat{y}_{t}]\Big{)}$
$\displaystyle\leq$ $\displaystyle\sum_{t=1}^{t^{\prime}}2Z_{t}w_{t}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{KT{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}$
(46)

where the third equality holds since we have
$\mathcal{A}_{t}=\\{\pi^{\star}(x_{t})\\}$ whenever $Z_{t}=0$ under the
condition that $f^{\star}\in\mathcal{F}_{t}$. The first inequality is Lemma
22, and the second inequality holds by the definition of $\xi_{t}$ and the
condition that $\xi_{t}=0$.

On the other hand, for all rounds after $t^{\prime}$, we have

$\displaystyle\sum_{t=t^{\prime}+1}^{T}\operatorname{Pr}\left(\widehat{y}_{t}\neq
y_{t}\right)-\operatorname{Pr}\left({\pi^{\star}}(x_{t})\neq y_{t}\right)$
$\displaystyle=$
$\displaystyle\sum_{t=t^{\prime}+1}^{T}Z_{t}\Big{(}f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\star}(x_{t})[\widehat{y}_{t}]\Big{)}$
$\displaystyle\leq$
$\displaystyle\sum_{t=t^{\prime}+1}^{T}Z_{t}\left(\frac{K}{\alpha_{t}}+\alpha_{t}\cdot\mathbb{E}_{a,b\sim
p_{t}}\Big{[}\big{(}f^{\star}(x_{t})[y]-f_{t}(x_{t})[y]\big{)}^{2}\Big{]}\right)$
$\displaystyle=$
$\displaystyle\sum_{t=t^{\prime}+1}^{T}Z_{t}\left(\frac{K}{\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}}+\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}\cdot\mathbb{E}_{a,b\sim
p_{t}}\Big{[}\big{(}f^{\star}(x_{t})[y]-f_{t}(x_{t})[y]\big{)}^{2}\Big{]}\right)$
$\displaystyle\leq$
$\displaystyle\sqrt{KT{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}+\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}\sum_{t=t^{\prime}+1}^{T}Z_{t}\mathbb{E}_{a,b\sim
p_{t}}\Big{[}\big{(}f^{\star}(x_{t})[y]-f_{t}(x_{t})[y]\big{)}^{2}\Big{]}$
$\displaystyle\leq$
$\displaystyle\sqrt{KT{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}+\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}\sum_{t=t^{\prime}+1}^{T}Z_{t}\big{(}f^{\star}(x_{t})[\widehat{y}_{t}]-f_{t}(x_{t})[\widehat{y}_{t}]\big{)}^{2}+8\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}\cdot\log(4\delta^{-1})$
$\displaystyle\leq$
$\displaystyle\sqrt{KT{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}+\sqrt{KT{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}+8\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}\cdot\log(4\delta^{-1}).$
(47)

where the first inequality holds by Lemma 18, the second equality is by the
definition of $\alpha_{t}$, the third inequality is by Lemma 4, and the last
inequality holds by our assumption on
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}$.

Combining the two parts, we conclude that

$\displaystyle\mathrm{Reg}_{T}=\sum_{t=1}^{T}\operatorname{Pr}\left(\widehat{y}_{t}\neq
y_{t}\right)-\operatorname{Pr}\left({\pi^{\star}}(x_{t})\neq y_{t}\right)\leq
12\sqrt{KT{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}\cdot\log(4\delta^{-1}).$
(48)

##### Instance-Dependent Regret Upper Bound.

We fix any $\varepsilon>0$ and consider two cases. First, when

$T_{\varepsilon}+112K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log(4/(\delta\varepsilon))<\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}},$
(49)

we invoke Lemma 23 and get that $\xi_{t}=0$ for all $t\in[T]$. Hence, we have

$\displaystyle\mathrm{Reg}_{T}=$
$\displaystyle\sum_{t=1}^{T}\operatorname{Pr}\left(\widehat{y}_{t}\neq
y_{t}\right)-\operatorname{Pr}\left({\pi^{\star}}(x_{t})\neq y_{t}\right)$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\star}(x_{t})[\widehat{y}_{t}]$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}Z_{t}\Big{(}f^{\star}(x_{t})[\pi^{\star}(x_{t})]-f^{\star}(x_{t})[\widehat{y}_{t}]\Big{)}$
$\displaystyle\leq$ $\displaystyle 2\sum_{t=1}^{T}Z_{t}w_{t}$
$\displaystyle\leq$ $\displaystyle
T_{\varepsilon}+112K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log(4/(\delta\varepsilon))$
$\displaystyle\leq$ $\displaystyle T_{\varepsilon}\cdot
12{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\log(4\delta^{-1})+1344K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{2}_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log^{2}(4/(\delta\varepsilon))$

where the first inequality is by Lemma 22 and the fact that we incur no regret
when $Z_{t}=0$ since $f^{\star}\in\mathcal{F}_{t}$. The second inequality is
by Lemma 21.

On the other hand, when the contrary of (49) holds, i.e.,

$T_{\varepsilon}+112K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log(4/(\delta\varepsilon))\geq\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}},$
(50)

applying the worst-case regret upper bound (48), we have

$\displaystyle\mathrm{Reg}_{T}\leq$ $\displaystyle
12\sqrt{KT{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}\cdot\log(4\delta^{-1})$
$\displaystyle=$ $\displaystyle
12{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\log(4\delta^{-1})\cdot\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}$
$\displaystyle\leq$ $\displaystyle T_{\varepsilon}\cdot
12{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\log(4\delta^{-1})+12{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\log(4\delta^{-1})\cdot
112K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log(4/(\delta\varepsilon))$
$\displaystyle\leq$ $\displaystyle T_{\varepsilon}\cdot
12{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\log(4\delta^{-1})+1344K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{2}_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log^{2}(4/(\delta\varepsilon))$

where we apply the condition (50) in the second inequality.

Hereto, we obtain the instance-dependent upper bound for regret in both cases
given a fixed $\varepsilon$. Recall that the choice of $\varepsilon$ is
arbitrary. Hence, we can take the infimum on $\varepsilon$ and complete the
proof.

####  C.4.3 Total Number of Queries

The upper bound of $T$ is trivial since our algorithm clearly will not make
more than $T$ queries. Now we prove the instance-dependent upper bound. We
first fix an arbitrary $\varepsilon$.

We also consider two cases. First, when

$\displaystyle
T_{\varepsilon}+112K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log(4/(\delta\varepsilon))<\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}},$
(51)

we can invoke Lemma 23 and get that $\xi_{t}=0$ for all $t\in[T]$. Hence,

$\displaystyle N_{T}=$
$\displaystyle\sum_{t=1}^{T}Z_{t}=T_{\varepsilon}+\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon\right\\}$
$\displaystyle=$ $\displaystyle
T_{\varepsilon}+\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{w_{t}\geq\varepsilon/2\\}$
$\displaystyle=$ $\displaystyle
T_{\varepsilon}+\sum_{t=1}^{T}Z_{t}\sup_{y\in\mathcal{A}_{t}}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[y]-f^{\prime}(x_{t})[y]\geq\varepsilon/2\right\\}$
$\displaystyle\leq$ $\displaystyle
T_{\varepsilon}+\sum_{t=1}^{T}Z_{t}\sum_{y\in\mathcal{A}_{t}}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[y]-f^{\prime}(x_{t})[y]\geq\varepsilon/2\right\\}$
$\displaystyle\leq$ $\displaystyle
T_{\varepsilon}+K\underbrace{\sum_{t=1}^{T}Z_{t}\mathbb{E}_{y\sim
p_{t}}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[y]-f^{\prime}(x_{t})[y]\geq\varepsilon/2\right\\}}_{(*)}$

where the second equality is by Lemma 20, the last step holds as $p_{t}(a)$ is
uniform for any $a$ when $\xi_{t}=0$. We apply Lemma 3 and Lemma 19 to $(*)$
and obtain

$\displaystyle(*)\leq$ $\displaystyle
2\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\sup_{f,f^{\prime}\in\mathcal{F}_{t}}f(x_{t})[\widehat{y}_{t}]-f^{\prime}(x_{t})[\widehat{y}_{t}]\geq\varepsilon/2\right\\}+8\log(\delta^{-1})$
$\displaystyle\leq$ $\displaystyle
2\left(\frac{4{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{(\varepsilon/2)^{2}}+1\right)\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)+8\log(\delta^{-1})$
$\displaystyle\leq$
$\displaystyle\frac{10{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{(\varepsilon/2)^{2}}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)+8\log(\delta^{-1}).$

Plugging this back, we obtain

$\displaystyle N_{T}\leq$ $\displaystyle
T_{\varepsilon}+\frac{10K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{(\varepsilon/2)^{2}}\cdot\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)+8K\log(\delta^{-1})$
$\displaystyle\leq$ $\displaystyle
2T_{\varepsilon}^{2}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}/K+25088K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{3}_{\delta}(\mathcal{F},T)}\frac{\check{\mathfrak{E}}^{2}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon^{2}}\cdot\log^{2}(4/(\delta\varepsilon)).$

On the other hand, when the contrary of (51) holds, i.e.,

$\displaystyle
T_{\varepsilon}+112K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}\cdot\frac{\check{\mathfrak{E}}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon}\cdot\log(4/(\delta\varepsilon))\geq\sqrt{KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}.$

Squaring both sides and using the fact that $(a+b)^{2}\leq 2a^{2}+2b^{2}$ for
any $a,b$, we obtain

$\displaystyle
2T_{\varepsilon}^{2}+25088K^{2}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{2}_{\delta}(\mathcal{F},T)}\frac{\check{\mathfrak{E}}^{2}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon^{2}}\cdot\log^{2}(4/(\delta\varepsilon))\geq
KT/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}$

which leads to

$T\leq
2T_{\varepsilon}^{2}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}/K+25088K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{3}_{\delta}(\mathcal{F},T)}\frac{\check{\mathfrak{E}}^{2}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon^{2}}\cdot\log^{2}(4/(\delta\varepsilon)).$

We note that we always have $N_{T}\leq T$, and thus,

$N_{T}\leq T\leq
2T_{\varepsilon}^{2}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}/K+25088K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi^{3}_{\delta}(\mathcal{F},T)}\frac{\check{\mathfrak{E}}^{2}\left(\mathcal{F},\varepsilon/4;f^{\star}\right)}{\varepsilon^{2}}\cdot\log^{2}(4/(\delta\varepsilon)).$

Hence, we complete the proof for a fix $\varepsilon$. Recall that the choice
of $\varepsilon$ is arbitrary. Hence, we can take the infimum and thus
complete the proof.

###  C.5 Proof of Theorem 5

In this section, we consider selective sampling with bandit feedback where on
every query, the learner chooses two actions $\widehat{y}_{t}$ and
$\widetilde{y}_{t}$ and receives back bandit feedback

$\displaystyle\widehat{\mathbb{Q}}_{t}=\mathbf{1}\\{\widehat{y}_{t}=y_{t}\\},\qquad\text{and,}\qquad\widetilde{\mathbb{Q}}_{t}=\mathbf{1}\\{\widetilde{y}_{t}=y_{t}\\},$

where $y_{t}$ is the action chosen by the noisy expert. In Theorem 5, we
consider the link function $\phi(z)=z$ corresponding to which, we have
$\ell_{\phi}(u,v)=(u-v)^{2}/2$ denotes the square loss, and
$\lambda=\gamma=1$. We present our selective sampling algorithm in Algorithm
5, and note that it builds on access to a square-loss regression oracle
$\mathsf{Oracle}$.

In the following, we recall the other notation used in Algorithm 5,

  1. $\bullet$

The label $y_{t}\sim{f^{\star}}(x_{t})$ as given in (2).

  2. $\bullet$

The function
$\mathtt{SelectAction}(f_{t}(x_{t}))=\operatorname*{argmax}_{k}f_{t}(x_{t})[k]$.

  3. $\bullet$

For any vector $v\in\mathbb{R}^{K}$, the margin is given by the gap between
the value at the largest and the second largest coordinate, i.e.

$\displaystyle\mathtt{Margin}(v)=v[k^{\star}]-\max_{k\neq k^{\star}}v[k],$

where $k^{\star}\in\operatorname*{argmax}_{k\in[K]}\phi(v)[k]$.

  4. $\bullet$

For any $\varepsilon>0$, we define
$T_{\varepsilon}=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
to denote the number of samples within $T$ rounds of interaction for which the
margin w.r.t. ${f^{\star}}$ is smaller than $\varepsilon$.

  5. $\bullet$

We define the function
$\mathrm{Gap}:\mathbb{R}^{K}\times[K]\mapsto\mathbb{R}^{+}$ as

$\displaystyle\mathrm{Gap}(u,k)=\max_{k^{\prime}}u[k^{\prime}]-u[k].$ (52)

to denote the gap between the largest and the $k$-th coordinate of $v$.

Algorithm 5 Selective Sampling with Multiple Bandit Queries

1:Parameters $\delta,\gamma,\lambda$, $T$, function class $\mathcal{F}$, and
online square loss regression oracle $\mathsf{Oracle}$.

2:Define
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}=2K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{sq}}(\mathcal{F};T)}+8K\log(T/\delta).$

3:Learner computes $f_{1}\leftarrow\text{$\mathsf{Oracle}$}_{1}(\emptyset)$.

4:for $t=1$ to $T$ do

5: Nature chooses $x_{t}$.

6: Learner plays the action
$\widehat{y}_{t}=\mathtt{SelectAction}(f_{t}(x_{t}))$.

7: Learner computes  $\displaystyle\Delta^{2}_{t}(x_{t})$
$\displaystyle\vcentcolon={}\max_{f\in\mathcal{F}}\leavevmode\nobreak\
\left\|f(x_{t})-f_{t}(x_{t})\right\|^{2},\qquad\text{s.t.}\quad\sum_{s=1}^{t-1}Z_{s}\left\|f(x_{s})-f_{s}(x_{s})\right\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}.\qquad$
(53)

8: Learner decides whether to query:
$Z_{t}=\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq 2\Delta_{t}(x_{t})\\}$.

9: if $Z_{t}=1$ then

10: Learner chooses the exploration action
$\widetilde{y}_{t}\sim\mathrm{Uniform}([K])$.

11: Learner queries for the actions $\widehat{y}_{t}$ and $\widetilde{y}_{t}$
and receives back the bandit feedback
$\displaystyle\widehat{\mathbb{Q}}_{t}=\mathbf{1}\\{\widehat{y}_{t}=y_{t}\\},\qquad\text{and}\qquad\widetilde{\mathbb{Q}}_{t}=\mathbf{1}\\{\widetilde{y}_{t}=y_{t}\\}.$

12:
$f_{t+1}\leftarrow\text{$\mathsf{Oracle}$}_{t}(\\{(x_{t},\widetilde{y}_{t}),\widetilde{\mathbb{Q}}_{t}\\})$.

13: else

14: Learner plays the action
$\widehat{y}_{t}=\mathtt{SelectAction}(f_{t}(x_{t}))$.

15: $f_{t+1}\leftarrow f_{t}$.

####  C.5.1 Supporting Technical Results

######  Lemma 24.

With probability at least $1-\delta$, the function ${f^{\star}}\in\mathcal{F}$
satisfies the following for all $t\leq T$:

$\displaystyle\sum_{s=1}^{t}Z_{s}\|f_{s}(x_{s})-{f^{\star}}(x_{s})\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}$

where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}=2K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{sq}}(\mathcal{F};T)}+8K\log(T/\delta)$.
Thus, for all $t\leq T$, ${f^{\star}}\in\mathcal{F}_{t}$.

###### Proof.

We first note that we do not query oracle when $Z_{s}=0$. Hence, we will
ignore the terms for which $Z_{s}=0$. Now note that the regret guarantee for
the oracle, given in (9) ensures that

$\displaystyle\sum_{s=1}^{t}Z_{s}(f_{s}(x_{s})[\widetilde{y}_{s}]-\widetilde{\mathbb{Q}}_{s})^{2}-\sum_{s=1}^{t}Z_{s}({f^{\star}}(x_{s})[\widetilde{y}_{s}]-\widetilde{\mathbb{Q}}_{s})^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{sq}}(\mathcal{F};T)}.$

Taking expectation on both sides yields

$\displaystyle\mathbb{E}\left[\sum_{s=1}^{t}Z_{s}(f_{s}(x_{s})[\widetilde{y}_{s}]-\widetilde{\mathbb{Q}}_{s})^{2}-\sum_{s=1}^{t}Z_{s}({f^{\star}}(x_{s})[\widetilde{y}_{s}]-\widetilde{\mathbb{Q}}_{s})^{2}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{s=1}^{t}Z_{s}\Big{(}(f_{s}(x_{s})[\widetilde{y}_{s}])^{2}-2\cdot\widetilde{\mathbb{Q}}_{s}\cdot
f_{s}(x_{s})[\widetilde{y}_{s}]+2\cdot\widetilde{\mathbb{Q}}_{s}\cdot{f^{\star}}(x_{s})[\widetilde{y}_{s}]-({f^{\star}}(x_{s})[\widetilde{y}_{s}])^{2}\Big{)}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{s=1}^{t}Z_{s}(f_{s}(x_{s})[\widetilde{y}_{s}]-{f^{\star}}(x_{s})[\widetilde{y}_{s}])^{2}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{K}\cdot\mathbb{E}\left[\sum_{s=1}^{t}Z_{s}\|f_{s}(x_{s})-{f^{\star}}(x_{s})\|^{2}\right]$
$\displaystyle\leq$
$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{sq}}(\mathcal{F};T)}$

where in the third line we use the fact that
$\operatorname{\mathbb{E}}\left[\widetilde{\mathbb{Q}}_{s}\right]={f^{\star}}(x_{s})[\widetilde{y}_{s}]$,
and the fourth line follows from the fact that
$\widetilde{y}_{s}\sim\mathrm{Uniform}([K])$. Applying the concentration
result (Lemma 4), we arrive at

$\displaystyle\sum_{s=1}^{t}Z_{s}\|f_{s}(x_{s})-{f^{\star}}(x_{s})\|^{2}\leq
2K{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathrm{Reg}^{\mathrm{sq}}(\mathcal{F};T)}+8K\log(1/\delta).$

We complete the proof by taking a union bound for all $t\in[T]$. ∎

For the rest of the proof, we condition on the $1-\delta$ probability event
that Lemma 24 holds. Additionally, we will use Lemma 11 and Lemma 12 from the
proof of Theorem 1 in Appendix C.1, which we will invoke by setting $\gamma=1$
for the link function $\phi(z)=z$.

We finally note the following technical lemma which allows us to bound the
number of times for which we query for the label and $\Delta_{t}(x_{t})$ is
larger than a constant in terms of the eluder dimension.

######  Lemma 25.

Let ${f^{\star}}$ satisfy Lemma 24, and let $\Delta_{t}(x_{t})$ be defined in
(53) in Algorithm 5. Then, for any $\zeta>0$, with probability at least
$1-\delta$,

$\displaystyle\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{t}(x_{t})\geq\zeta\right\\}$
$\displaystyle\leq\frac{20{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{\zeta^{2}}\cdot\mathfrak{E}(\mathcal{F},\nicefrac{{\zeta}}{{2}};{f^{\star}}).$

where $\mathfrak{E}$ denotes the eluder dimension given in Definition 1.

The proof of Lemma 25 is identical to the proof of Lemma 11, so we skip it for
conciseness.

####  C.5.2 Regret Bound

For the ease of notation, through the proof, we define the function
${\pi^{\star}}$ such that

$\displaystyle{\pi^{\star}}(x)=\operatorname*{argmax}_{k}{f^{\star}}(x)[k].$

Furthermore, recall that $\widehat{y}_{t}$ denotes the action chosen by the
learner at round $t$ of interaction. The proof follows along the lines of the
proof of Theorem 1 in Appendix C.1. Let $\varepsilon>0$ be a free parameter.
Following the identical steps till (25), we get that

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}\cdot\varepsilon$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\bar{Z}_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle=T_{\varepsilon}\cdot\varepsilon+T_{A}+T_{B}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|,$

where in the last line we plugin the definition of $T_{\varepsilon}$, and
define $\mathtt{T}_{A}$ and $\mathtt{T}_{B}$ as the second term and the last
term respectively. We bound them separately below:

  1. $\bullet$

Bound on $\mathtt{T}_{A}$: We note that

$\displaystyle\mathtt{T}_{A}$
$\displaystyle=\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\widehat{y}_{t}\neq{\pi^{\star}}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|>\varepsilon/2\\}\cdot\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|$

where the last line follows from Lemma 12 (when invoked with $\phi(z)=z$ for
which $\gamma=1$) and because $\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})$. Using
the fact that $\mathbf{1}\\{a\geq b\\}\leq\nicefrac{{a}}{{b}}$ for all
$a,b\geq 0$, we get that

$\displaystyle\mathtt{T}_{A}\leq
4\sum_{t=1}^{T}Z_{t}\frac{\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|^{2}}{\varepsilon}.$

  2. $\bullet$

Bound on $\mathtt{T}_{B}$: Fix any $t\leq T$, and first note that Lemma 24
implies that
$\sum_{s=1}^{t}\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|^{2}\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}$,
and thus ${f^{\star}}$ satisfies the constraint in the definition of
$\Delta_{t}$ in (5) and we must have that

$\displaystyle\|{f^{\star}}(x_{t})-f_{t}(x_{t})\|\leq\Delta_{t}(x_{t}).$ (54)

Plugging in the definition of $Z_{t}$, we note that

$\displaystyle\mathtt{T}_{B}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))>2\Delta_{t}(x_{t}),\widehat{y}_{t}\neq{\pi^{\star}}(x_{t})\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|>\Delta_{t}(x_{t})\\},$

where the second inequality is due Lemma 12 (where we set $\gamma=1$ for the
square loss $\phi(z)=z$). However, note that the term inside the indicator
contradicts (54) (which always holds). Thus,

$\displaystyle\mathtt{T}_{B}$ $\displaystyle=0.$

Gathering the two bounds above, we get that

$\displaystyle\mathrm{Reg}_{T}$ $\displaystyle\leq\varepsilon
T_{\varepsilon}+8\sum_{t=1}^{T}Z_{t}\frac{\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|^{2}}{\varepsilon}$
$\displaystyle\leq\varepsilon
T_{\varepsilon}+\frac{8}{\varepsilon}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)},$

where the last inequality is due to Lemma 24.

Since $\varepsilon$ is a free parameter above, the final bound follows by
choosing the best parameter $\varepsilon$, and by plugging in the form of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}$.

####  C.5.3 Total Number of Queries

Let $\varepsilon>0$ be a free parameter. Repeating the steps in the proof of
Theorem 1 till (29), we get that

$\displaystyle N_{T}=\sum_{t=1}^{T}Z_{t}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq\varepsilon\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{4}}\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})>\nicefrac{{\varepsilon}}{{4}}\\}$
$\displaystyle=T_{\varepsilon}+\mathtt{T}_{D}+\mathtt{T}_{E},$

where in the last line we used the definition of $T_{\varepsilon}$, and
defined $\mathtt{T}_{D}$ and $\mathtt{T}_{E}$ respectively. We bound them
separately below.

  1. $\bullet$

Bound on $\mathtt{T}_{D}$. Recall (54) which implies that ${f^{\star}}$
satisfies the bound
$\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|\leq\Delta_{t}(x_{t})$. Thus, using Lemma
13 (with $\gamma=1$ for the link function $\phi(z)=z$), we get that

$\displaystyle\mathtt{Margin}({f^{\star}}(x_{t}))\leq
2\|f_{t}(x_{t})-{f^{\star}}(x_{t})\|+\mathtt{Margin}(f_{t}(x_{t}))\leq
2\Delta_{t}(x_{t})+\mathtt{Margin}(f_{t}(x_{t})).$

The above implies that

$\displaystyle\mathtt{T}_{D}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{4}}\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}({f^{\star}}(x_{t}))\leq
4\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{4}}\\}$
$\displaystyle\leq 0,$

where the last line follows from the fact that all the conditions inside the
indictor can not hold simultaneously.

  2. $\bullet$

Bound on $\mathtt{T}_{E}$. We note that

$\displaystyle\mathtt{T}_{E}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Margin}(f_{t}(x_{t}))\leq
2\Delta_{t}(x_{t}),\mathtt{Margin}({f^{\star}}(x_{t}))>\varepsilon,\Delta_{t}(x_{t})>\nicefrac{{\varepsilon}}{{4}}\\}$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\left\\{\Delta_{t}(x_{t})\geq\nicefrac{{\varepsilon}}{{4}}\right\\}$
$\displaystyle\leq\frac{320{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{\varepsilon^{2}}\cdot\mathfrak{E}(\mathcal{F},\nicefrac{{\varepsilon}}{{4}};{f^{\star}}).$

where the last line follows from setting $\zeta=\varepsilon/4$ in Lemma 25.

Gathering the bounds above, we get that

$\displaystyle N_{T}$ $\displaystyle\leq
T_{\varepsilon}+\frac{640{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}}{\varepsilon^{2}}\cdot\mathfrak{E}(\mathcal{F},\nicefrac{{\varepsilon}}{{4}};{f^{\star}}).$

Since $\varepsilon$ is a free parameter above, the final bound follows by
choosing the best parameter $\varepsilon$, and by plugging in the form of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Psi_{\delta}(\mathcal{F},T)}$.

###  C.6 Proofs for Lower Bounds in Section 3.2

The proof of Theorem 3 below follows along the lines of the proof of the lower
bound in Theorem 28 of Foster et al. (2020) with minor changes.

###### Proof of Theorem 3.

Let $\beta\leq\zeta/2$ be the largest number such that
$\beta^{2}\leq\min\\{\zeta^{2}/\mathfrak{s}^{\mathrm{val}}(\mathcal{F},\zeta,\beta),\zeta^{2}/16\\}$.
Given the function class $\mathcal{F}$, assume that
$m=\mathfrak{s}^{\mathrm{val}}(\mathcal{F},\zeta,\beta)>0$ (the lower bound is
obvious when the star number is $0$). Let the target function $f^{\star}$, the
data sequence $x^{1},\ldots,x^{m}$, and the function
$f_{1},\ldots,f_{m}\in\mathcal{F}$ be the witnesses for the fact that the star
number is $m$ (see Definition 3). First, for any $i\in[m]$, we have that
$|f^{\star}(x^{i})|>\zeta$ by definition of the star number. Next note that,
for each $f_{i}$, we have that, for any $j\neq i$,

$\displaystyle|f_{i}(x^{j})|\geq|f^{\star}(x^{j})|-|f_{i}(x^{j})-f^{\star}(x^{j})|\geq\zeta-\beta\geq\zeta/2$

On the other hand, from our definition of star number we have that,

$|f_{i}(x^{i})|\geq\zeta/2.$

Hence we are guaranteed that each $f_{i}$ has a margin of at least $\zeta/2$
on $x^{1},\ldots,x^{m}$. Now consider the distribution $\mu$ over the context
to be the uniform distribution over $\\{x^{1},\ldots,x^{m}\\}$. Also let
$P^{i}(y=1\mid x)=\nicefrac{{1+f_{i}(x)}}{{2}}$ be the conditional probability
of label given context $x$. Let $D_{i}$ denote the joint distribution over
$\mathcal{X}\times\\{\pm 1\\}$ given by drawing $x$’s from $\mu$ and labels
from $P^{i}$. Additionally, let $D_{0}$ be given by drawing $x$’s from $\mu$
and $y$ conditioned on $x$ as $P(y=1\mid x)=\nicefrac{{1+f^{\star}(x)}}{{2}}$.
Finally, let $\nu=0$ with probability $1/2$ and $\nu\sim\mathrm{Uniform}([m])$
with probability $1/2$. Note that by our premise,

$\displaystyle\frac{1}{2}\mathbb{E}_{D_{0}}\left[\mathrm{Reg}_{T}\right]+\frac{1}{2m}\sum_{i=1}^{m}\mathbb{E}_{{}_{D_{i}}}\left[\mathrm{Reg}_{T}\right]=\mathbb{E}_{\nu}\left[\mathbb{E}_{D_{\nu}}\left[\mathrm{Reg}_{T}\right]\right]\leq
c\frac{\zeta T}{m},$ (55)

where the value of the constant $c$ will be set later. Furthermore, let
$p_{t}:\mathcal{X}\mapsto\Delta(\mathcal{Y})$ denote the distribution over the
label chosen by the given algorithm at round $t$ given the history
$\left(x_{1},y_{1},\dots,x_{t-1},y_{t-1}\right)$. We note that for any
$i\in[m]$,

$\displaystyle\mathbb{E}_{{}_{D_{i}}}\left[\mathrm{Reg}_{T}\right]$
$\displaystyle\geq\mathbb{E}_{{}_{D_{i}}}\left[\sum_{t=1}^{T}\frac{\zeta}{2}\mathbb{E}_{x\sim\mu}\mathbb{E}_{\hat{y}\sim
p_{t}(x)}\left[\mathbf{1}\\{f_{i}(x)\hat{y}<0\\}\right]\right]$
$\displaystyle=\frac{T\zeta}{2}\mathbb{E}_{{}_{D_{i}}}\left[\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{x\sim\mu}\operatorname{\mathbb{E}}_{\hat{y}\sim
p_{t}(x)}\mathbf{1}\\{\text{\rm sign}(f_{i}(x))\neq\hat{y}\\}\right]$
$\displaystyle\geq\frac{T\zeta}{4}\mathbb{E}_{{}_{D_{i}}}\left\|\frac{1}{T}\sum_{t=1}^{T}p_{t}-\text{\rm
sign}(f_{i})\right\|_{L_{1}(\mu)}$

where in the first inequality we used that $f_{i}$ has a margin of at least
$\zeta/2$ for any $x\in\\{x^{1},\dots,x^{m}\\}$ as shown above, and the last
inequality simply follows from the fact that

$\displaystyle\lvert\operatorname{\mathbb{E}}_{\hat{y}\sim
p_{t}(x)}\mathbf{1}\\{\text{\rm
sign}(f_{i}(x))\neq\hat{y}\\}\rvert=\lvert\operatorname{\mathbb{E}}_{\hat{y}\sim
p_{t}(x)}\left(\mathbf{1}\\{\text{\rm
sign}(f_{i}(x))=1\\}-\mathbf{1}\\{\widehat{y}=0\\}\right)\rvert=\frac{1}{2}\lvert
p_{t}(x)-f_{i}(x)\rvert,$

and via an application of the Jensen’s inequality. Using the property that for
any distribution with margin at least $\nicefrac{{\zeta}}{{2}}$, the algorithm
satisfies
$\operatorname{\mathbb{E}}_{D_{i}}\left[\mathrm{Reg}_{T}\right]\leq\nicefrac{{c\zeta
T}}{{m}}$, the above implies that

$\displaystyle\mathbb{E}_{{}_{D_{i}}}\left\|\frac{1}{T}\sum_{t=1}^{T}p_{t}-\text{\rm
sign}(f_{i})\right\|_{L_{1}(\mu)}\leq\frac{8c}{m},$

which implies that

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}_{{}_{D_{i}}}\left\|\frac{1}{T}\sum_{t=1}^{T}p_{t}-\text{\rm
sign}(f_{i})\right\|_{L_{1}(\mu)}\leq\frac{8c}{m}.$ (56)

Hence, setting $c=64$ and using Markov’s inequality, we have that

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\operatorname{Pr}_{{}_{D_{i}}}\left(\left\|\frac{1}{T}\sum_{t=1}^{T}p_{t}-\text{\rm
sign}(f_{i})\right\|_{L_{1}(\mu)}>\frac{2}{m}\right)\leq\frac{1}{16}.$

Further note that $\left\|\text{\rm sign}(f_{j})-\text{\rm
sign}(f_{i})\right\|_{L_{1}(\mu)}>\frac{4}{m}$ and thus, condition on the fact
that $\nu$ is not equal to $0$, we can can identify $\nu$ correctly with
probability at least $1-1/16$. Thus, considering the reference measure $D_{0}$
and using Fano’s inequality, we must have that

$\log(2)\leq\frac{1}{m}\sum_{i=1}^{m}\mathrm{KL}{\left(D_{0}\|D_{i}\right)}$

Now we are left with bounding $\mathrm{KL}{\left(D_{0}\|D_{i}\right)}$. To
this end, we first make a simple observation that the distribution on the
$x_{t}$’s is the same under $D_{0}$ and $D_{i}$. Hence on rounds $t$ where
$Z_{t}=0$ we do not query for the labels in these rounds, and thus we do not
glean any new information to distinguish $D_{i}$ from $D_{0}$. In other words,
we only need to consider rounds when $Z_{t}=1$. Hence we have:

$\mathrm{KL}{\left(D_{0}\|D_{i}\right)}=\mathbb{E}_{D_{0}}\left[\sum_{t=1}^{T}Z_{t}\cdot\mathrm{kl}{\left(P_{0}(y_{t}=1|x_{t})\|P_{i}(y_{t}=1|x_{t})\right)}\right]$

Assuming $\zeta>1/4$ and using the bound on KL between Bernoulli variables we
get,

$\mathrm{KL}{\left(D_{0}\|D_{i}\right)}\leq\mathbb{E}_{D_{0}}\left[32N_{i}\zeta^{2}+8\left(\max_{j\neq
i}N_{j}\right)\beta^{2}\right]$

where $N_{i}=|\\{t:Z_{t}=1,x_{t}=x^{i}\\}$, and we used
item-$\boldsymbol{(3)}$ in the definition of star number for the $\zeta^{2}$
term and item-$\boldsymbol{(1)}$ for the $\beta^{2}$ term. Hence we have that,

$\displaystyle\log(2)$
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}_{D_{0}}\left[32N_{i}\zeta^{2}+8\left(\max_{j\neq
i}N_{j}\right)\beta^{2}\right]$
$\displaystyle\leq\frac{32}{m}\mathbb{E}_{D_{0}}\left[\sum_{i=1}^{m}N_{i}\right]\zeta^{2}+8\mathbb{E}_{D_{0}}\left[\max_{j}N_{j}\right]\beta^{2}$
$\displaystyle\leq\frac{32}{m}\mathbb{E}_{D_{0}}\left[N_{T}\right]\zeta^{2}+8\mathbb{E}_{D_{0}}\left[N_{T}\right]\beta^{2}$

Since $\beta^{2}\leq\zeta^{2}/m$, we have that

$\displaystyle\log(2)$
$\displaystyle\leq\frac{40}{m}\mathbb{E}_{D_{0}}\left[N_{T}\right]\zeta^{2}$

Hence we conclude that,

$\displaystyle\mathbb{E}_{D_{0}}\left[N_{T}\right]\geq\frac{\log(2)m}{40\zeta^{2}}$

which yields the desired lower bound. ∎

###### Proof of Corollary 2.

Consider the function class
$\mathcal{F}=\\{f_{0},f_{1},\ldots,f_{\sqrt{T}}\\}$ where
$f_{0}(x_{i})=1/2+\zeta$ for every $x_{1},\ldots,x_{\sqrt{T}}$, and where
$f_{i}(x_{i})=1/2-\zeta$ and $f_{i}(x_{j})=1/2+\zeta$ for any $j\neq i$. Note
that selecting $f^{\star}=f_{0}$ and $f_{1},\ldots,f_{m}$ on
$x_{1},\ldots,x_{\sqrt{T}}$, we can show that the star number
$\mathfrak{s}^{\mathrm{val}}(\mathcal{F},1/8,1/2)=O(\sqrt{T})$ (the
disagreement coefficient of $\mathcal{F}$ is also $O(\sqrt{T})$). Thus, using
the converse of Theorem 3 we get that if the number of queries is smaller than
$\sqrt{T}$, then there must exist some data distribution under which the
regret bound of the algorithm is larger that $\sqrt{T}$. ∎

##  Appendix D Imitation Learning: Learning from Single Expert

###  D.1 Imitation Learning Tools

We first recall useful additional notation. Recall that a policy $\pi$ is a
mapping from the states $\mathcal{X}$ to actions $\mathcal{A}$. For any $h\leq
H$, and random variable $\mathsf{Z}(x_{h},a_{h})$, we use the notation
$\operatorname{\mathbb{E}}_{\pi}\left[\mathsf{Z}(x_{h},a_{h})\right]$ to
denote the expectation w.r.t. trajectories
$\\{x_{1},a_{1}\dots,x_{H},a_{H}\\}$ sampled using the policy $\pi$.

The following lemma is the standard performance difference lemma, well known
in the imitation learning and reinforcement learning literature.

######  Lemma 26 (Performance Difference Lemma; Kakade and Langford (2002);
Ross and Bagnell (2014)).

For any MDP $M$, and any two arbitrary stationary policies $\pi$ and
$\widetilde{\pi}$, we have

$\displaystyle
V^{\pi}-V^{\widetilde{\pi}}=\sum_{h=1}^{H}\operatorname{\mathbb{E}}_{x_{h},a_{h}\sim
d^{\widetilde{\pi}}_{h}}\left[-A_{h}^{\pi}(x_{h},a_{h})\right],$

where $A^{\pi}$ is the advantage function of the policy $\pi$ in MDP $M$,
i.e., $A_{h}^{\pi}(x,a)=Q_{h}^{\pi}(x,a)-V_{h}^{\pi}(x)$.

###  D.2 Proof of Proposition 1

##### MDP construction.

The underlying MDP is a binary tree of depth $H$. In particular, we construct
the deterministic MDP $M=(\mathcal{X},\mathcal{A},P,r,x_{1})$ where state
space $\mathcal{X}=\cup_{h=1}^{H}\mathcal{X}_{h}$ with
$\mathcal{X}_{h}=\\{x_{h,i}\\}_{i=1}^{2^{h-1}}$ (we assume that
$x_{1}=x_{1,1}$), action space $\mathcal{A}=\\{0,1\\}$, reward $r$ is such
that
$r(x,a)=\mathrm{Bern}\left(\frac{1}{2}+\frac{1}{4}\mathbf{1}\\{x=x^{\star}\\}\right)$
for some special state $x^{\star}\in\mathcal{X}_{H}$. The transition dynamics
$P$ is deterministic and defines a binary tree over $\mathcal{X}$, i.e. for
any $h$ and $x_{h,i}$, $P(x^{\prime}\mid x_{h,i},a)=1$ if
$x^{\prime}=x_{h+1,2i-1}$ and $a=0$, or $x^{\prime}=x_{h+1,2i+1}$ and $a=1$,
else $P(x^{\prime}\mid x,a)=0$.

We next define the expert policy ${\pi^{\star}}$, expert model ${f^{\star}}$
and the class $\mathcal{F}$. First, for any path
$\tau=(x_{1},a_{1},\dots,x_{H},a_{H})$ from the root state $x_{1}$ to a