terminal state $x_{H}$ at the layer $H$, define the policy $\pi_{\tau}$ as

$\displaystyle\pi_{\tau}(x_{h})$
$\displaystyle=\begin{cases}a_{h}&\text{if}\quad(x_{h},a_{h})\in\tau\\\
\bar{a}_{h}\leftarrow\text{Uniform}(\\{0,1\\})&\text{otherwise}\end{cases}.$

In particular, $\pi_{\tau}$ is defined such that for any state on the path
$\tau$, we choose the corresponding action in $\tau$, and for any state
outside of $\tau$, we choose an arbitrary (deterministic) action. Let
$\mathcal{T}$ denote the set of all $2^{H}$ many paths from the root note
$x_{1}$ to a leaf node $x_{H}\in\mathcal{X}_{H}$. We define the class
$\Pi=\\{\pi_{\tau}\mid\tau\in\mathcal{T}\\}$, and
$\mathcal{F}=\\{f_{\tau}\mid\tau\in\mathcal{T}\\}$, where for any $\tau$, we
define $f_{\tau}:\mathcal{X}\mapsto\mathbb{R}^{2}$ as

$\displaystyle f_{\tau}(x)$
$\displaystyle=\begin{cases}(\nicefrac{{3}}{{4}},\nicefrac{{1}}{{4}})&\text{if}\qquad\pi_{\tau}(x)=0\\\
(\nicefrac{{1}}{{4}},\nicefrac{{3}}{{4}})&\text{if}\qquad\pi_{\tau}(x)=1\\\
\end{cases}.$

Next, let
$\tau^{\star}=(x_{1},a^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{H-1},a^{\prime}_{H-1},x^{\star})$
be the path from the root $x_{1}$ to the special state
$x^{\star}\in\mathcal{X}_{H}$ on the underlying binary tree. We finally define
${\pi^{\star}}=\pi_{\tau^{\star}}$ and ${f^{\star}}=f_{\tau^{\star}}$.

##### Lower bound.

Given the MDP construction, the class $\mathcal{F}$, ${f^{\star}}$ and
${\pi^{\star}}$ above, we now proceed to the desired lower bound for non-
interactive imitation learning. First, note that
${\pi^{\star}}(x)=\operatorname*{argmax}_{a}({f^{\star}}(x)[a])$ for any
$x\in\mathcal{X}$. Furthermore,
$\mathtt{Margin}({f^{\star}}((x))=\frac{1}{2}\lvert
f(x)[0]-f(x)[1]\rvert=\frac{1}{4}$ for all $x\in\mathcal{X}$. Thus, for any
$\varepsilon\leq\frac{1}{4}$, $T_{\varepsilon,h}=0$.

Next, for any policy $\pi$, note that
$V^{\pi}=\frac{1}{2}+\frac{1}{4}\mathbf{1}\\{\pi={\pi^{\star}}\\}$. Thus,
${\pi^{\star}}$ is the unique $1/8$-suboptimal policy. Additionally, consider
a noisy expert that draws its label according to (2) with the link function
$\phi(z)=z$, i.e. on the state $x$, the expert draws its label from $a\sim
f^{\star}(x)$. Now, suppose that the learner is given a dataset $\mathcal{D}$
of $m$ many trajectories drawn this noisy expert. There are two scenarios:
either $\mathcal{D}$ does not contain $\tau^{*}$, or $\mathcal{D}$ contains
the trajectory $\tau^{*}$.

  1. $\bullet$

In the first case, the learner is restricted to finding ${\pi^{\star}}$ by
eliminating all other $\pi\neq{\pi^{\star}}$ using the observations
$\mathcal{D}$. Since, $\lvert\Pi\rvert=2^{H}$ and each policy in the class is
associated with a different path on the tree, we must have that $m=O(2^{H})$.

  2. $\bullet$

In the second case, we need $\tau^{\star}\in\mathcal{D}$. However, note that
probability of observing the trajectory $\tau^{\star}$ when following the
actions proposed by the noisy expert is $\operatorname{Pr}(\tau^{\star}\mid
a_{h}\sim{f^{\star}}(x_{h}))=\left({3}/{4}\right)^{H}$. Thus, in order to
observe $\tau^{\star}$ with probability at least $3/4$ in the dataset
$\mathcal{D}$, we need $m=O((4/3)^{H})$.

In both the scenarios above, we need to collect exponentially many samples.

###  D.3 Proof of Theorem 6

Before delving into the proof, we recall the relevant notation. In Algorithm
3, for any $h\leq H$,

  1. $\bullet$

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

  2. $\bullet$

The function
$\mathtt{SelectAction}(f_{t,h}(x_{t,h}))=\operatorname*{argmax}_{k}\phi(f_{t,h}(x_{t,h}))[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 (under the link
function $\phi$), 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 define
$T_{\varepsilon}=\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbf{1}\\{\mathtt{Margin}({f^{\star}_{h}}(x_{t,h}))\leq\varepsilon\\}$
to denote the number of samples within $T$ rounds of interaction for which the
margin w.r.t. ${f^{\star}_{h}}$ is smaller than $\varepsilon$.

  5. $\bullet$

The trajectory at round $t$ is generated using the dynamics
$\\{\mathbb{T}_{t,h}\\}_{h\leq H}$ to determine the states that the learner
observes, starting from the state $x_{1}$.

  6. $\bullet$

At round $t$, the learner collects data using the policy $\pi_{t}$ such that
at time $h$, and state $x$, the action
$\pi_{t}(x)=\mathtt{SelectAction}(f_{t,h}(x_{t,h}))$.

  7. $\bullet$

For any policy $\pi$, let $\tau^{\pi}_{t}$ denote the (counterfactual)
trajectory that one would obtain by running $\pi$ on the deterministic
dynamics $\\{\mathbb{T}_{t,h}\\}_{h\leq H}$ with the start state $x_{t,1}$,
i.e.

$\displaystyle\tau^{\pi}_{t}=\left\\{x_{t,1}^{\pi},\pi(x_{t,1}^{\pi}),\dots,x_{t,H}^{\pi},\pi(x_{t,H}^{\pi})\right\\}$
(57)

where $x_{t,1}^{\pi}=x_{t,1}$ and
$x_{t,h+1}^{\pi}=\mathbb{T}_{t,h}(x_{t,h}^{\pi},\pi(x_{t,h}^{\pi}))$.

  8. $\bullet$

For a trajectory $\tau=\\{x_{1},a_{1},\dots,x_{H},a_{H}\\}$, we define the
total return

$\displaystyle R(\tau)$ $\displaystyle=\sum_{h=1}^{H}r(x_{h},a_{h}).$ (58)

  9. $\bullet$

Additionally, for any policy $\pi$ and dynamics $\\{\mathbb{T}_{h}\\}_{h\leq
H}$, we define the trajectory obtained by running the policy $\pi$ as

$\displaystyle\tau^{\pi}=\\{x_{1}^{\pi},\pi_{1}(x_{1}^{\pi}),x_{2}^{\pi},\dots\\}.$

  10. $\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],$
(59)

to denote the gap between the largest and the $k$-th coordinate of $v$, and
note that $\mathtt{Margin}(v)\leq\mathrm{Gap}(v,k)$ for all $k\neq k^{\star}$
(due to Lemma 9).

####  D.3.1 Supporting Technical Results

We first define a useful technical lemma which allows us to bound the gap
between the total returns for policies ${\pi_{1}}$ and ${\pi_{2}}$, under the
dynamics $\\{\mathbb{T}_{h}\\}_{h\leq H}$. Recall that for a policy $\pi$, we
define the trajectory $\tau^{\pi}$ under $\\{\mathbb{T}_{h}\\}_{h\leq H}$ and
the start state $x_{1}$ as the trajectory
$\\{x_{1}^{\pi},\pi(x_{1}^{\pi}),\dots,x_{H}^{\pi},\pi(x_{H}^{\pi})\\}$ where
$x^{\pi}_{1}=x_{1}$, and
$x^{\pi}_{h+1}\leftarrow\mathbb{T}_{h}(x^{\pi}_{h},\pi(x^{\pi}_{h}))$.

######  Lemma 27.

Let $\\{\mathbb{T}_{h}\\}_{h\leq H}$ be a deterministic dynamics, and let
$x_{1}$ be the start state. Let $\pi_{1}$ and $\pi_{2}$ be any two
deterministic policies, and let
$\tau^{\pi_{1}}=\\{x_{1}^{\pi_{1}},\pi_{1}(x_{1}^{\pi_{1}}),x_{2}^{\pi_{1}},\dots\\}$
and
$\tau^{\pi_{2}}=\\{x_{1}^{\pi_{2}},\pi_{1}(x_{1}^{\pi_{2}}),x_{2}^{\pi_{2}},\dots\\}$
be two trajectories drawn using $\pi_{1}$ and $\pi_{2}$ on
$\\{\mathbb{T}_{h}\\}_{h\leq H}$ with start state $x_{1}$. Then, for any set
$\mathtt{X}\subseteq\mathcal{X}$, the total trajectory rewards satisfy

$\displaystyle R(\tau^{\pi_{1}})-R(\tau^{\pi_{2}})$ $\displaystyle\leq
2H\sum_{h=1}^{H}\mathbf{1}\\{x_{h}^{\pi_{1}}\in\mathtt{X}\\}+2H\sum_{h=1}^{H}\mathbf{1}\\{\pi_{2}(x_{h}^{\pi_{2}})\neq\pi_{1}(x_{h}^{\pi_{2}}),x_{h}^{\pi_{2}}\notin\mathtt{X}\\}.$

###### Proof.

Let $\mathfrak{h}\leq H$ denote the first timestep at which the policies
$\pi_{1}$ and $\pi_{2}$ choose different actions under
$\\{\mathbb{T}_{h}\\}_{h\leq H}$. Since the trajectories
$\tau^{\pi_{1}}=\\{x_{1}^{\pi_{1}},\pi_{1}(x_{1}^{\pi_{1}}),x_{2}^{\pi_{1}},\dots\\}$
and
$\tau^{\pi_{2}}=\\{x_{1}^{\pi_{2}},\pi_{1}(x_{1}^{\pi_{2}}),x_{2}^{\pi_{2}},\dots\\}$
are obtained by evolving through (the deterministic dynamics)
$\\{\mathbb{T}_{h}\\}_{h\leq H}$ using policies $\pi_{1}$ and $\pi_{2}$
respectively, and with the same state state $x_{1}$, we have that

$\displaystyle x_{h}^{\pi_{1}}=x_{h}^{\pi_{2}}\qquad\qquad$
$\displaystyle\text{for all $h\leq\mathfrak{h}$},$ and
$\displaystyle\pi_{1}(x_{h}^{\pi_{1}})=\pi_{2}(x_{h}^{\pi_{2}})\qquad\qquad$
$\displaystyle\text{for all $h\leq\mathfrak{h}-1$}.$ (60)

Starting from the definition of the cumulative reward $R(\cdot)$, we have that

$\displaystyle R(\tau^{\pi_{1}})-R(\tau^{\pi_{2}})$
$\displaystyle=\sum_{h=1}^{H}\left(r(x_{h}^{\pi_{1}},\pi_{1}(x_{h}^{\pi_{1}}))-r(x_{h}^{\pi_{2}},\pi_{2}(x_{h}^{\pi_{2}}))\right)$
$\displaystyle=\sum_{h=1}^{\mathfrak{h}-1}\left(r(x_{h}^{\pi_{1}},\pi_{1}(x_{h}^{\pi_{1}}))-r(x_{h}^{\pi_{2}},\pi_{2}(x_{h}^{\pi_{2}}))\right)+\sum_{h=\mathfrak{h}}^{H}\left(r(x_{h}^{\pi_{1}},\pi_{1}(x_{h}^{\pi_{1}}))-r(x_{h}^{\pi_{2}},\pi_{2}(x_{h}^{\pi_{2}}))\right)$
$\displaystyle=\sum_{h=\mathfrak{h}}^{H}\left(r(x_{h}^{\pi_{1}},\pi_{1}(x_{h}^{\pi_{1}}))-r(x_{h}^{\pi_{2}},\pi_{2}(x_{h}^{\pi_{2}}))\right),$

where the last line uses the fact that the trajectories (and thus the rewards)
$\tau^{\pi_{1}}$ and $\tau^{\pi_{2}}$ are identical for the first
$\mathfrak{h}-1$ states and actions (see (60)). Since (60) also implies that
$x_{\mathfrak{h}}^{\pi_{1}}=x_{\mathfrak{h}}^{\pi_{2}}$, for the ease of
notation we define
$x_{\mathfrak{h}}=x_{\mathfrak{h}}^{\pi_{1}}=x_{\mathfrak{h}}^{\pi_{2}}$.
Using the fact that $\lvert r(x,a)\rvert\leq 1$ and that
$\pi_{1}(x_{\mathfrak{h}})\neq\pi_{2}(x_{\mathfrak{h}})$ (by definition of
$\mathfrak{h}$), we can bound the above as

$\displaystyle R(\tau^{\pi_{1}})-R(\tau^{\pi_{2}})$ $\displaystyle\leq
2(H-\mathfrak{h}+1)\mathbf{1}\\{\pi_{1}(x_{\mathfrak{h}})\neq\pi_{2}(x_{\mathfrak{h}})\\}$
$\displaystyle\leq
2H\mathbf{1}\\{\pi_{1}(x_{\mathfrak{h}})\neq\pi_{2}(x_{\mathfrak{h}})\\}$
$\displaystyle=2H\mathbf{1}\\{\pi_{1}(x_{\mathfrak{h}})\neq\pi_{2}(x_{\mathfrak{h}}),x_{\mathfrak{h}}\in\mathtt{X}\\}+2H\mathbf{1}\\{\pi_{1}(x_{\mathfrak{h}})\neq\pi_{2}(x_{\mathfrak{h}}),x_{\mathfrak{h}}\notin\mathtt{X}\\}$
$\displaystyle\leq
2H\mathbf{1}\\{x_{\mathfrak{h}}\in\mathtt{X}\\}+2H\mathbf{1}\\{\pi_{1}(x_{\mathfrak{h}})\neq\pi_{2}(x_{\mathfrak{h}}),x_{\mathfrak{h}}\notin\mathtt{X}\\}$
$\displaystyle=2H\mathbf{1}\\{x_{\mathfrak{h}}^{\pi_{1}}\in\mathtt{X}\\}+2H\mathbf{1}\\{\pi_{2}(x_{\mathfrak{h}}^{\pi_{2}})\neq\pi_{1}(x_{\mathfrak{h}}^{\pi_{2}}),x_{\mathfrak{h}}^{\pi_{2}}\notin\mathtt{X}\\}$
$\displaystyle\leq
2H\sum_{h=1}^{H}\mathbf{1}\\{x_{h}^{\pi_{1}}\in\mathtt{X}\\}+2H\sum_{h=1}^{H}\mathbf{1}\\{\pi_{2}(x_{h}^{\pi_{2}})\neq\pi_{1}(x_{h}^{\pi_{2}}),x_{h}^{\pi_{2}}\notin\mathtt{X}\\},$

where the equality in second last line plugs in the fact that
$x_{\mathfrak{h}}=x_{\mathfrak{h}}^{\pi_{1}}=x_{\mathfrak{h}}^{\pi_{2}}$, and
the last inequality is a straightforward upper bound. ∎

We will also be using Lemma 9 and Lemma 13 from Appendix C.1 for bounding the
$\mathtt{Margin}$ in the regret bound proofs. Finally, we note the following
properties of the function ${f^{\star}_{h}}$.

######  Lemma 28.

With probability at least $1-\delta$, the function ${f^{\star}_{h}}$ satisfies
for any $h\leq H$ and $t\leq T$,

  1. $(a)$

$\sum_{s=1}^{t-1}Z_{s,h}\|{f^{\star}_{h}}(x_{s,h})-f_{s,h}(x_{s,h})\|^{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}_{h},T)},$

  2. $(b)$

$\|{f^{\star}_{h}}(x_{t,h})-f_{t,h}(x_{t,h})\|\leq\Delta_{t,h}(x_{t,h}),$

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}_{h},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}_{h};T)}+\frac{112}{\lambda^{2}}\log(4H\log^{2}(T)/\delta)$.

###### Proof.

  1. $(a)$

We first note that we do not query oracle when $Z_{s,h}=0$, and thus we can
ignore the time steps for which $Z_{s,h}=0$. Hence, for each $h\in[H]$,
applying Lemma 5 along with the fact that $\sup_{x,f\in\mathcal{F}_{h}}\lvert
f(x)\rvert\leq 1$ yields

$\sum_{s=1}^{t-1}Z_{s,h}\|{f^{\star}_{h}}(x_{s,h})-f_{s,h}(x_{s,h})\|^{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}_{h};T)}+\frac{112}{\lambda^{2}}\log(4\log^{2}(T)/\delta)$

for all $t\leq T$. Then, we take the union bound for all $h\in[H]$, which
completes the proof.

  2. $(b)$

The second part follows from using the observation in part-(a) that
${f^{\star}_{h}}$ satisfies the constraint in the definition of $\Delta_{t,h}$
given in (12), and thus
$\|{f^{\star}_{h}}(x_{t,h})-f_{t,h}(x_{t,h})\|\leq\Delta_{t,h}(x_{t,h})$.

∎

The next technical lemma bounds the number of times when
$\Delta_{t,h}(x_{t,h})\geq\zeta$ and we query the expert. Note that Lemma 29
holds even if the sequence $\\{x_{t,h}\\}_{t\leq T}$ was adversarially
generated.

######  Lemma 29.

Let ${f^{\star}}$ satisfy Lemma 28, and let $\Delta_{t,h}(x_{t})$ be defined
in (12). Suppose we run Algorithm 3 on data sequence $\\{\\{x_{t,h}\\}_{h\leq
H}\\}_{t\leq T}$, and let $Z_{t,h}$ be as defined in line 10. Then, for any
$\zeta>0$, with probability at least $1-H\delta$, for any $h\leq H$,

$\displaystyle\sum_{t=1}^{T}Z_{t,h}\mathbf{1}\left\\{\Delta_{t,h}(x_{t,h})\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}_{h},T)}}{\zeta^{2}}\cdot\mathfrak{E}(\mathcal{F}_{h},\frac{\zeta}{2};{f^{\star}_{h}}),$

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

###### Proof.

The proof is identical to the proof of Lemma 11 by replacing all
$\lvert\cdot\rvert$ with $\|\cdot\|$, and substitute the corresponding bounds
for ${f^{\star}_{h}}$ via Lemma 28 (instead of using Lemma 10). We skip the
proof for conciseness. ∎

####  D.3.2 Regret Bound

Recall that the trajectory at round $t$ is generated using the dynamics
$\\{\mathbb{T}_{t,h}\\}_{h\leq H}$. Define the policy ${\pi_{t}}$ and
${\pi^{\star}}$ such that for any $h\leq H$ and $x\in\mathcal{X}_{h}$,

$\displaystyle{\pi_{t}}(x_{h})=\mathtt{SelectAction}(f_{t,h}(x_{h})),\quad\text{and,}\quad{\pi^{\star}}(x_{h})=\mathtt{SelectAction}({f^{\star}_{h}}(x_{h})).$
(61)

Furthermore, for any policy $\pi$, let $\tau^{\pi}_{t}$ denote the trajectory
that one would obtain by running $\pi$ on the deterministic dynamics
$\\{\mathbb{T}_{t,h}\\}_{h\leq H}$ with the start state $x_{t,1}$, i.e.

$\displaystyle\tau^{\pi}_{t}=\left\\{x_{t,1}^{\pi},\pi(x_{t,1}^{\pi}),\dots,x_{t,H}^{\pi},\pi(x_{t,H}^{\pi})\right\\}$
(62)

where $x_{t,1}^{\pi}=x_{t,1}$ and
$x_{t,h+1}^{\pi}=\mathbb{T}_{t,h}(x_{t,h}^{\pi},\pi(x_{t,h}^{\pi}))$. Note
that Algorithm 3 collects trajectories using the policy ${\pi_{t}}$ at round
$t$. Thus, we have that

$\displaystyle x_{t,h}^{{\pi_{t}}}=x_{t,h},$ (63)

where $x_{t,h}$ denotes the state at time step $h$ in round $t$ of Algorithm
3. Finally, let $\varepsilon>0$ be a free parameter. We now have all the
notation to proceed to the proof on our regret bound.

Step 1: Bounding the difference in return at round $t$. Fix any $t\leq T$, and
let $\tau_{t}^{{\pi_{t}}}$ and $\tau_{t}^{\pi^{\star}}$ denote the
trajectories that would have been sampled using the policies ${\pi_{t}}$ and
the policy ${\pi^{\star}}$ at round $t$. Furthermore, define the set
$\mathtt{X}_{\varepsilon}$ as

$\displaystyle\mathtt{X}_{\varepsilon}\vcentcolon={}\bigcup_{h=1}^{H}\\{x\in\mathcal{X}_{h}\mid{}\mathtt{Margin}({f^{\star}_{h}}(x))\leq\varepsilon\\}$
(64)

Using Lemma 27 for the policies ${\pi_{t}}$ and ${\pi^{\star}}$, and the set
$\mathtt{X}_{\varepsilon}$ defined above, we get that999The key advantage of
using Lemma 27 is that the first term
$\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}$
accounts for the number steps at which a counterfactual trajectory sampled
using ${\pi^{\star}}$ goes to the state space with margin less than
$\varepsilon$. Thus, we only pay for the number of times when the comparator
policy ${\pi^{\star}}$ would go to states with $\varepsilon$-margin (instead
of when ${\pi_{t}}$ does to such states).

$\displaystyle R(\tau_{t}^{{\pi^{\star}}})-R(\tau_{t}^{{\pi_{t}}})$
$\displaystyle\leq
2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{h=1}^{H}\mathbf{1}\\{{\pi_{t}}(x_{t,h}^{{\pi_{t}}})\neq{\pi^{\star}}(x_{t,h}^{{\pi_{t}}}),x_{t,h}^{{\pi_{t}}}\notin\mathtt{X}_{\varepsilon}\\}$
(65)
$\displaystyle=2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{h=1}^{H}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle\hskip
130.08621pt+2H\sum_{h=1}^{H}\bar{Z}_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle\leq
2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle\hskip
130.08621pt+2H\sum_{h=1}^{H}\bar{Z}_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h})\\}$
$\displaystyle=2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\mathtt{T}_{A}+2H\mathtt{T}_{B},$
(66)

where the second line is obtained by plugging in (63) and the last line simply
defines $\mathtt{T}_{A}$ and $\mathtt{T}_{B}$ to be the second and the third
terms in the previous line without the $2H$ multiplicative factor.

We bound $\mathtt{T}_{A}$ and $\mathtt{T}_{B}$ separately below.

  1. $\bullet$

Bound on term $\mathtt{T}_{A}$. Using the definition of
$\mathtt{X}_{\varepsilon}$ from (64), we note that

$\displaystyle\mathtt{T}_{A}$
$\displaystyle=\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),\mathtt{Margin}({f^{\star}_{h}}(x_{t,h}))>\varepsilon\\}$
$\displaystyle\leq\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{{\pi^{\star}}(x_{t,h})\neq{\pi_{t}}(x_{t,h}),\phi({f^{\star}_{h}}({x_{t,h}}))[{\pi^{\star}}({x_{t,h}})]-\phi({f^{\star}_{h}}({x_{t,h}}))[{\pi_{t}}({x_{t,h}})]\geq\varepsilon\\}$
$\displaystyle\leq\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{\phi({f^{\star}_{h}}({x_{t,h}}))[{\pi^{\star}}({x_{t,h}})]-\phi({f^{\star}_{h}}({x_{t,h}}))[{\pi_{t}}({x_{t,h}})]\geq\varepsilon\\},$

where in the second last line we used the definition of
$\mathtt{Margin}({f^{\star}_{h}}(x_{t,h}))$ along with the fact that
${\pi^{\star}}(x_{t,h})\neq{\pi_{t}}(x_{t,h})$. Using the relation in Lemma 12
for the term inside the indicator, we can further bound the above as

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

where in the second inequality we used: $\mathbf{1}\\{a\geq
b\\}\leq\nicefrac{{a^{2}}}{{b^{2}}}$ for any $a,b\geq 0$.

  2. $\bullet$

Bound on term $\mathtt{T}_{B}$. Before delving into the proof, first note that
Lemma 28-$(b)$ implies that

$\displaystyle\|{f^{\star}_{h}}(x_{t,h})-f_{t,h}(x_{t,h})\|\leq\Delta_{t,h}(x_{t,h}).$
(67)

Next, note that

$\displaystyle\mathtt{T}_{B}$
$\displaystyle=\sum_{h=1}^{H}\bar{Z}_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h})\\}$
$\displaystyle=\sum_{h=1}^{H}\mathbf{1}\\{\mathtt{Margin}(f_{t,h}(x_{t,h}))>2\gamma\Delta_{t,h}(x_{t,h}),{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h})\\},$

where in the last line we just plugged in the query condition under which
$Z_{t,h}=0$. However note that the above two conditions inside the indicator
imply that

$\displaystyle 2\gamma\Delta_{t,h}(x_{t,h})$
$\displaystyle<\mathtt{Margin}(f_{t,h}(x_{t,h}))$
$\displaystyle\leq\phi(f_{t,h}(x_{t,h}))[\pi_{t}(x_{t,h})]-\phi(f_{t,h}(x_{t,h}))[{\pi^{\star}}(x_{t,h})]$
$\displaystyle\leq 2\gamma\|f_{t,h}(x_{t,h})-{f^{\star}_{h}}(x_{t,h})\|,$

where the second line uses the definition of $\mathtt{Margin}(\cdot)$ and the
fact that ${\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h})$, the last line is due
to Lemma 12 . Thus,

$\displaystyle\mathtt{T}_{B}\leq\sum_{h=1}^{H}\mathbf{1}\\{\|f_{t,h}(x_{t,h})-{f^{\star}_{h}}(x_{t,h})\|>\Delta_{t,h}(x_{t,h})\\},$

but the conditions inside the indicator in the above contradicts (67) (which
holds with probability $1-\delta$). Thus, with probability at least
$1-\delta$,

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

Plugging in the bounds on $\mathtt{T}_{A}$ and $\mathtt{T}_{B}$ in (66), we
get that with probability at least $1-\delta$,

$\displaystyle R(\tau_{t}^{{\pi^{\star}}})-R(\tau_{t}^{{\pi_{t}}})$
$\displaystyle\leq
2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+\frac{8H\gamma^{2}}{\varepsilon^{2}}\sum_{h=1}^{H}Z_{t,h}\|{f^{\star}_{h}}(x_{t,h})-f_{t,h}(x_{t,h})\|^{2}.$
(69)

Step 2: Bound on total regret. Using the bound in (69) for each round $t$, we
get that

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}\left(R(\tau_{t}^{{\pi^{\star}}})-R(\tau_{t}^{{\pi_{t}}})\right)$
$\displaystyle\leq
2H\sum_{h=1}^{H}\sum_{t=1}^{T}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+\frac{8H\gamma^{2}}{\varepsilon^{2}}\sum_{h=1}^{H}\sum_{t=1}^{T}Z_{t,h}\|{f^{\star}_{h}}(x_{t,h})-f_{t,h}(x_{t,h})\|^{2}$
$\displaystyle\leq
2H\sum_{h=1}^{H}T_{\varepsilon,h}+\frac{8H\gamma^{2}}{\varepsilon^{2}}\sum_{h=1}^{H}{\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}_{h},T)},$
(70)

where in the last line we use the definition of $T_{\varepsilon,h}$, and plug
in the bound in Lemma 28. Recall that $T_{\varepsilon,h}$ denotes the number
of times when the comparator policy ${\pi^{\star}}$ enters the region
$\mathtt{X}_{\varepsilon}$ of states of small expert margin. Using 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}_{h},T)}$
and ignoring $\log$ factors and constants, we get

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\widetilde{\mathcal{O}}\left(H\sum_{h=1}^{H}T_{\varepsilon,h}+\frac{H\gamma^{2}}{\lambda\varepsilon^{2}}\sum_{h=1}^{H}{\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}_{h};T)}+\frac{H\gamma^{2}}{\lambda^{2}\varepsilon^{2}}\log(1/\delta)\right).$

Since $\varepsilon$ is a free parameter above, the final bound follows by
taking $\inf$ over all feasible $\varepsilon$.

####  D.3.3 Total Number of Queries

Let $N_{T}$ denote the total number of expert queries made by the learner
within $T$ rounds of interaction (with $H$ steps per round). For $t\leq T$,
let $h_{t}$ denote the first timestep at which $Z_{t,h_{t}}=1$ at round $t$.
Additionally, let $\varepsilon>0$ be a free parameter. Thus, we have that

$\displaystyle N_{T}$ $\displaystyle=\sum_{t=1}^{T}\sum_{h=1}^{H}Z_{t,h}$ (71)
$\displaystyle\leq H\sum_{t=1}^{T}Z_{t,h_{t}}$
$\displaystyle=H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}+H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle\leq
H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}+H\sum_{t=1}^{T}\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}+H\sum_{t=1}^{T}\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{x_{t,h}\notin\mathtt{X}_{\varepsilon},\Delta_{t,h}(x_{t,h})\leq\frac{\varepsilon}{4\gamma}\\}$
$\displaystyle\hskip
130.08621pt+H\sum_{t=1}^{T}\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{x_{t,h}\notin\mathtt{X}_{\varepsilon},\Delta_{t,h}(x_{t,h})>\frac{\varepsilon}{4\gamma}\\}$
$\displaystyle=\mathtt{T}_{C}+H\mathtt{T}_{D}+H\mathtt{T}_{E},$

where $\mathtt{T}_{C}$, $\mathtt{T}_{D}$ and $\mathtt{T}_{E}$ are the first,
second and the third term respectively in the previous line. We bound them
separately below:

  1. $\bullet$

Bound on $\mathtt{T}_{C}$. Fix any $t\leq T$, and note that

$\displaystyle(\mathtt{T}_{C})_{t}$
$\displaystyle=HZ_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=HZ_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}\mathbf{1}\\{\forall
h<h_{t}:{\pi^{\star}}(x_{t,h})=\pi_{t}(x_{t,h})\\}$ $\displaystyle\hskip
108.405pt+HZ_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}\mathbf{1}\\{\exists
h<h_{t}:{\pi^{\star}}(x_{t,h})\neq\pi_{t}(x_{t,h})\\}.$ (72)

For the second term, note that

$\displaystyle
Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}\mathbf{1}\\{\exists
h<h_{t}:{\pi^{\star}}(x_{t,h})\neq\pi_{t}(x_{t,h})\\}$
$\displaystyle\leq\sum_{h=1}^{h_{t}}Z_{t,h_{t}}\mathbf{1}\\{{\pi^{\star}}(x_{t,h})\neq\pi_{t}(x_{t,h})\\}$
$\displaystyle\leq\sum_{h=1}^{h_{t}}Z_{t,h_{t}}\bar{Z}_{t,h}\mathbf{1}\\{{\pi^{\star}}(x_{t,h})\neq\pi_{t}(x_{t,h})\\}$
$\displaystyle\leq\sum_{h=1}^{h_{t}}\bar{Z}_{t,h}\mathbf{1}\\{{\pi^{\star}}(x_{t,h})\neq\pi_{t}(x_{t,h})\\}$

where in second inequality above, we used the fact that $Z_{t,h}=0$ (and thus
$\bar{Z}_{t,h}=1$) for all $h\leq h_{t}$, by the definition of $h_{t}$.
However note that the right hand side in the last inequality is equivalent to
the term $\mathtt{T}_{B}$ defined above (where sum is now till $h_{t}$ instead
of $H$). Thus, using the bound in (68) in the above, we immediately get that

$\displaystyle
Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}\mathbf{1}\\{\exists
h<h_{t}:{\pi^{\star}}(x_{t,h})\neq{\pi_{t}}(x_{t,h})\\}=0.$

For the first term in (72), using the condition that
${\pi^{\star}}(x_{t,h})=\pi_{t}(x_{t,h})$ for all $h\leq h_{t}$, we get that
$x_{t,h}=x^{{\pi^{\star}}}_{t,h}$ and thus

$\displaystyle
HZ_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}\mathbf{1}\\{\forall
h\leq h_{t}:{\pi^{\star}}(x_{t,h})=\pi_{t}(x_{t,h})\\}$ $\displaystyle\leq
HZ_{t,h_{t}}\mathbf{1}\\{x^{{\pi^{\star}}}_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}$
$\displaystyle\leq
H\mathbf{1}\\{x^{{\pi^{\star}}}_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}$
$\displaystyle\leq
H\sum_{h=1}^{H}\mathbf{1}\\{x^{{\pi^{\star}}}_{t,h}\in\mathtt{X}_{\varepsilon}\\}.$

Gathering the two terms above, and plugging in the definition of
$T_{\varepsilon,h}$, we get that

$\displaystyle\mathtt{T}_{C}\leq
H\sum_{h=1}^{H}\sum_{t=1}^{T}\mathbf{1}\\{x^{{\pi^{\star}}}_{t,h}\in\mathtt{X}_{\varepsilon}\\}=H\sum_{h=1}^{H}T_{\varepsilon,h}.$

  2. $\bullet$

Bound on $\mathtt{T}_{D}$. Using the definition of the set
$\mathtt{X}_{\varepsilon}$ and $Z_{t,h}$, we note that

$\displaystyle(\mathtt{T}_{D})_{t}$
$\displaystyle=\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{x_{t,h}\notin\mathtt{X}_{\varepsilon},\Delta_{t,h}(x_{t,h})\leq\frac{\varepsilon}{4\gamma}\\}$
$\displaystyle=\sum_{h=1}^{H}\mathbf{1}\\{\mathtt{Margin}(f_{t,h}(x_{t,h}))\leq
2\gamma\Delta_{t,h}(x_{t,h}),\mathtt{Margin}({f^{\star}_{h}}(x_{t,h}))>\varepsilon,\Delta_{t,h}(x_{t,h})\leq\frac{\varepsilon}{4\gamma}\\}$
(73)

Recall that Lemma 28 implies that with probability at least $1-\delta$,

$\displaystyle\|{f^{\star}_{h}}(x_{t,h})-f_{t,h}(x_{t,h})\|\leq\Delta_{t,h}(x_{t,h}),$

using which with Lemma 13 implies that

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

Using the above bound with the conditions in (73) implies that

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

where the last equality holds because the two conditions in the indicator in
the previous line can never occur simultaneously.

  3. $\bullet$

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

$\displaystyle\mathtt{T}_{E}$
$\displaystyle=\sum_{t=1}^{T}\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{x_{t,h}\notin\mathtt{X}_{\varepsilon},\Delta_{t,h}(x_{t,h})>\frac{\varepsilon}{4\gamma}\\}$
$\displaystyle\leq\sum_{h=1}^{H}\sum_{t=1}^{T}Z_{t,h}\mathbf{1}\\{\Delta_{t,h}(x_{t,h})>\frac{\varepsilon}{4\gamma}\\}.$

An application of Lemma 29 in the above for each $h\leq H$ implies that

$\displaystyle\mathtt{T}_{E}$
$\displaystyle\leq\sum_{h=1}^{H}\frac{320\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}_{h},T)}}{\varepsilon^{2}}\cdot\mathfrak{E}(\mathcal{F}_{h},\frac{\varepsilon}{8\gamma};{f^{\star}_{h}}).$

Gathering the bound above, we get that

$\displaystyle N_{T}$ $\displaystyle\leq
H\sum_{h=1}^{H}T_{\varepsilon,h}+\frac{320H\gamma^{2}}{\varepsilon^{2}}\sum_{h=1}^{H}{\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}_{h},T)}\cdot\mathfrak{E}(\mathcal{F}_{h},\frac{\varepsilon}{8\gamma};{f^{\star}_{h}}).$

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}_{h},T)}$
and ignoring $\log$ factors and constants, we get that

$\displaystyle N_{T}$
$\displaystyle\leq\widetilde{\mathcal{O}}\left(H\sum_{h=1}^{H}T_{\varepsilon,h}+\frac{H\gamma^{2}}{\lambda\varepsilon^{2}}\sum_{h=1}^{H}{\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}_{h};T)}\cdot\mathfrak{E}(\mathcal{F}_{h},\nicefrac{{\varepsilon}}{{8\gamma}};{f^{\star}_{h}})+\frac{H\gamma^{2}}{\lambda^{2}\varepsilon^{2}}\log(1/\delta)\right).$

Notice that $\varepsilon$ is a free parameter above so the final bound follows
by taking $\inf$ over all feasible $\varepsilon$. s

###  D.4 Proof for the Stochastic Setting

Algorithm 3 considers arbitrary deterministic dynamics
$\\{\\{\mathbb{T}_{t,h}\\}_{h\leq H}\\}_{t\leq T}$. When the underlying
dynamics $\mathscr{T}$ is stochastic, we can simply simulate Algorithm 3,
where we set $\\{\mathbb{T}_{t,h}\\}_{h\leq H}=\mathscr{T}(\cdot;\iota_{t})$
where $\iota_{t}$ is drawn i.i.d. for every $t\leq T$. In the following, we
provide regret and query complexity bounds for stochastic dynamics.

##### Regret bound.

Note that Theorem 6 bounds the difference of cumulative rewards of
trajectories drawn using the policies ${\pi_{t}}$ and ${\pi^{\star}}$ on the
adversarially chosen deterministic dynamics $\\{\mathbb{T}_{t,h}\\}_{h=1}^{H}$
respectively. In particular, we bound

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}\left(R(\tau^{{\pi^{\star}}}_{t})-R(\tau^{{\pi_{t}}}_{t})\right).$

On the other hand, when the dynamics is stochastic, we aim to bound the gap
between the expected values $V^{{\pi^{\star}}}-V^{{\pi_{t}}}$ obtained under
the stochastic dynamics $\mathscr{T}$. We obtain this bound by pushing all the
stochasticity into the choice of random seed $\iota$. Fix any $t\leq T$, and
consider the deterministic dynamics
$(\mathbb{T}_{t,1},\dots,\mathbb{T}_{t,H})$ obtained by setting the random
seed to be $\iota_{t}$ in the stochastic dynamics $\mathscr{T}$, i.e.
$(\mathbb{T}_{t,1},\dots,\mathbb{T}_{t,H})\vcentcolon={}\mathscr{T}(\leavevmode\nobreak\
;\leavevmode\nobreak\ \iota_{t})$. Thus, for any policy $\pi$

$\displaystyle V^{\pi}$
$\displaystyle=\operatorname{\mathbb{E}}_{\iota_{t}}\left[R(\tau^{\pi}_{t})\mid(\mathbb{T}_{t,1},\dots,\mathbb{T}_{t,H})=\mathscr{T}(\leavevmode\nobreak\
;\leavevmode\nobreak\ \iota_{t})\right].$

In the following, we will bound the difference in the value function
$V^{\pi}-V^{{\pi_{t}}}$, by appealing to the regret bound in the proof of
Theorem 6 using appropriate concentration inequalities. First, recall that in
Algorithm 3, the dynamics $\\{\mathbb{T}_{t,h}\\}_{h\leq H}$ is chosen before
the round $t$, and that the policy ${\pi_{t}}$ only depends on the interaction
till round $t-1$. Thus,

$\displaystyle\sum_{t=1}^{T}V^{\pi}-V^{{\pi_{t}}}$
$\displaystyle=\sum_{t=1}^{T}\operatorname{\mathbb{E}}_{\iota_{t}}\left[R(\tau^{\pi}_{t})-R(\tau^{\pi^{\star}}_{t})\right]$
$\displaystyle\leq\sum_{t=1}^{T}\operatorname{\mathbb{E}}_{\iota_{t}}\left[2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{h=1}^{H}\mathbf{1}\\{{\pi_{t}}(x_{t,h}^{{\pi_{t}}})\neq{\pi^{\star}}(x_{t,h}^{{\pi_{t}}}),x_{t,h}^{{\pi_{t}}}\notin\mathtt{X}_{\varepsilon}\\}\right],$

where the last holds due to Lemma 27 and the set $\mathtt{X}_{\varepsilon}$ is
defined in (64). An application of Lemma 4 in the above implies that with
probability at least $1-\delta$,

$\displaystyle\sum_{t=1}^{T}V^{\pi}-V^{{\pi_{t}}}$ $\displaystyle\leq
4H\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+4H\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbf{1}\\{{\pi_{t}}(x_{t,h}^{{\pi_{t}}})\neq{\pi^{\star}}(x_{t,h}^{{\pi_{t}}}),x_{t,h}^{{\pi_{t}}}\notin\mathtt{X}_{\varepsilon}\\}+32H^{2}\log(2/\delta).$

The rest of the proof is identical to the proof of Theorem 6 from (65)
onwards. They query complexity can be similarly computed.

##  Appendix E Learning from Multiple Experts

We next provide the proofs for learning from multiple experts. We first
consider the selective sampling setting, and provide the setup, relevant
notation and our algorithm for selective sampling with multiple experts in
Appendix E.1. We then move to the imitation learning with multiple experts.

###  E.1 Selective Sampling

1:Parameters $\delta,\gamma,\lambda,T,M$, function classes
$\\{\mathcal{F}^{m}\\}_{m\leq M}$, and online oracles
$\\{\text{$\mathsf{Oracle}$}^{m}\\}_{m\leq M}$.

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}^{m},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}^{m};T)}+\frac{112}{\lambda^{2}}\log(4M\log^{2}(T)/\delta).$

3:Learner computes
$f^{m}_{1}\leftarrow\text{$\mathsf{Oracle}$}^{m}_{1}(\emptyset)$ for every
$m\in[M]$.

4:Learner defines
$F_{t}(x_{t})=\left[f^{1}_{t}(x_{t}),\dots,f^{M}_{t}(x_{t})\right]$.

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

6: Nature chooses $x_{t}$.

7: Learner plays the action
$\widehat{y}_{t}=\mathtt{SelectAction}(F_{t}(x_{t}))$

8: For every $m\in[M]$, learner computes
$\displaystyle\Delta^{m}_{t}(x_{t})\vcentcolon={}\max_{f\in\mathcal{F}^{m}}\leavevmode\nobreak\
\|f(x_{t})-f^{m}_{t}(x_{t})\|\quad\text{s.t.}\quad\sum_{s=1}^{t-1}Z_{s}\left\|f(x_{s})-f^{m}_{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}^{m},T)},$
(74) and sets
${\vec{\Delta}}_{t}(x_{t})=[\Delta^{1}_{t}(x_{t}),\dots,\Delta^{M}_{t}(x_{t})]$.

9: Learner decides whether to query:
$Z_{t}=\mathtt{Query}(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t}))$.

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

11: for $m=1$ to $M$ do

12: Learner queries the $m$-th expert for its action $y^{m}_{t}$

13:
$f^{m}_{t+1}\leftarrow\text{$\mathsf{Oracle}$}^{m}_{t}(\\{x_{t},y^{m}_{t}\\})$.

14: else

15: $f^{m}_{t+1}\leftarrow f^{m}_{t}$ for all $m\in[M]$.

Algorithm 6 Selective SAmplinG with QuEries to $\boldsymbol{M}$ Experts
(SAGE$-\mathsf{M}$)

We first discuss the setup and the relevant notation. The learner has access
to feedback from $M$ experts, each with their ground truth models
$\\{{f^{\star,m}}\\}_{m\in[M]}$ respectively. At round $t$, on the given
context $x_{t}$, the learner plays the action $\widehat{y}_{t}\in[K]$.
Additionally, the learner can choose to query the experts, and receive
feedback $y_{t}^{m}\sim\phi({f^{\star,m}}(x_{t}))$ for each expert $m\in[M]$.
The learner suffers a loss if the chosen action does not match with the
actions $\\{y_{t}\\}_{t\leq T}$ sampled jointly using the noisy experts, e.g.
we may have

$\displaystyle y_{t}\sim\mathscr{A}\left(\phi(F^{\star}(x_{t}))\right),$ (75)

where $F^{\star}(x_{t})=[f^{\star,1}(x_{t}),\dots,f^{\star,M}(x_{t})]$ denotes
the concatenation of the scores predicted by each expert, and
$\mathscr{A}:\mathbb{R}^{K\times M}\mapsto\mathbb{R}^{K}$ denotes an
aggregation function (known to the learner) that maps the predictions of the
estimated experts to distributions over actions. Some illustrative examples of
$\mathscr{A}$ are given in Section 5 under (14). The goal of the learner is to
minimize its regret w.r.t. the comparator policy ${\pi^{\star}}$ that knows
the expert models $F^{\star}$ and is defined such that

$\displaystyle{\pi^{\star}}(x)=\operatorname*{argmax}_{k\in[K]}\mathscr{A}\left(\phi(F^{\star}(x_{t}))[k]\right).$
(76)

Thus, we wish to bound

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\widehat{y}_{t}\neq
y_{t}\\}-\mathbf{1}\\{{\pi^{\star}}(x_{t})\neq y_{t}\\}.$ (77)

Additionally, in Algorithm 6, for any round $t\in[T]$, we have

  1. $\bullet$

The function $\mathtt{SelectAction}:\mathbb{R}^{K\times M}\mapsto[K]$ chooses
the action to play at round $t$, and is defined as:

$\displaystyle\mathtt{SelectAction}(F_{t}(x_{t}))=\operatorname*{argmax}_{k}\mathscr{A}\left(\phi(F_{t}(x_{t}))\right)[k].$
(78)

  2. $\bullet$

Each expert computes the width $\Delta^{m}_{t}(x_{t})$ by solving (74).

  3. $\bullet$

Given the context $x_{t}$ and the function
$F_{t}:\mathcal{X}\mapsto\mathbb{R}^{K\times M}$, the learner decided whether
to query via $Z_{t}=\mathtt{Query}(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t}))$
where we define the function $\mathtt{Query}:\mathbb{R}^{K\times
M}\times\mathbb{R}^{M}$ as

$\displaystyle\mathtt{Query}(U;\vec\Delta)$
$\displaystyle\vcentcolon={}\sup_{V\in\mathbb{R}^{K\times
M}}\leavevmode\nobreak\
\mathbf{1}\\{\mathtt{SelectAction}(U)\neq\mathtt{SelectAction}(V)\\}\quad$
$\displaystyle\hskip
36.135pt\text{s.t.}\quad\|U[:,m]-V[:,m]\|_{2}\leq\vec\Delta[m]\qquad\forall
m\leq M.$ (79)

  4. $\bullet$

For the ease of notation, given a $F(x)\in\mathbb{R}^{K\times M}$, we define
the set $\mathbb{B}_{\infty}(F(x),{\vec{\Delta}})$ to denote the set of all
matrices $F^{\prime}\in\mathbb{R}^{K\times M}$ such that
$\|F(x)[:,m]-F^{\prime}(x)[:,m]\|\leq{\vec{\Delta}}[m]$ for all $m\leq M$.

Finally, our bounds depend on the notation of margin defined w.r.t.
$\mathtt{Query}$. In particular, for a sequence of contexts
$\\{x_{s}\\}_{s\leq t}$, we define

$\displaystyle
T_{\varepsilon}=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}(F^{\star}(x_{t}),\vec{\mathbbm{1}})=1\\}.$
(80)

####  E.1.1 Supporting Technical Results

The following technical lemma is useful in analyzing the constraints in the
computation of $\Delta^{m}_{t}$ in Algorithm 6.

######  Lemma 30.

With probability at least $1-{}\delta$, for any $t\leq T$ and $m\leq M$, the
function ${f^{\star,m}}$ satisfies

  1. $(a)$

$\sum_{s=1}^{t-1}Z_{s}\|f^{\star,m}(x_{s})-f^{m}_{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}^{m},T)},$

  2. $(b)$

$\|f^{\star,m}(x_{t})-f^{m}_{t}(x_{t})\|\leq\Delta^{m}_{t}(x_{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}^{m},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}^{m};T)}+\frac{112}{\lambda^{2}}\log(4M\log^{2}(T)/\delta).$

###### Proof.

  1. $(a)$

The part-(a) follows from an application of Lemma 5 for each $m\in[M]$, 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$. Each expert $m\in[M]$ can be bound
independently, and then a union bound gives the desired result.

  2. $(b)$

The second part follows from using the observation in part-(a) in (74).

∎

For the rest of the proof, we condition on the $1-\delta$ probability event
under which Lemma 30 holds.

######  Lemma 31.

Let ${f^{\star,m}}$ satisfy Lemma 30, and let $\Delta^{m}_{t}(x_{t})$ be
defined in Algorithm 6. Suppose we run Algorithm 6 on data sequence
$\\{x_{t}\\}_{t\leq 1}$, and let $Z_{t}$ be as defined in line 9. Then, for
any $\zeta>0$, with probability at least $1-M\delta$, for any $m\in[M]$,

$\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}^{m},T)}}{\zeta^{2}}\cdot\mathfrak{E}(\mathcal{F}^{m},\frac{\zeta}{2};{f^{\star,m}}),$

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

###### Proof.

The proof is identical to the proof of Lemma 11 where we handle each $m\in[M]$
separately, and substitute the corresponding bounds for ${f^{\star,m}}$ via
Lemma 30 (instead of using Lemma 10). We skip the proof for conciseness. ∎

####  E.1.2 Regret Bound

Recall that the policy ${\pi_{t}}$ is given by
${\pi_{t}}(x)=\mathtt{SelectAction}(F_{t}(x_{t}))$. Furthermore, the
comparator policy ${\pi^{\star}}$ given in (76) is
${\pi^{\star}}(x)=\mathtt{SelectAction}(F^{\star}(x))$.

In the following, we measure regret w.r.t. any arbitrary ground truth actions
$\\{y_{1},\dots,y_{T}\\}$, i.e. we make no assumptions on the process that
generates $\\{y_{1},\dots,y_{T}\\}$101010In Appendix E.1.4, we provide an
improvement over the bounds in this section when $\\{y_{1},\dots,y_{T}\\}$ are
generated according to (75), and when $\mathscr{A}$ is $\eta$-Lipschitz..
Starting from the definition of regret,

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}\operatorname{Pr}\left({\pi_{t}}(x_{t})\neq
y_{t}\right)-\operatorname{Pr}\left({\pi^{\star}}(x_{t})\neq y_{t}\right)$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t})\\}\cdot\left\lvert\operatorname{Pr}\left(y_{t}={\pi^{\star}}(x_{t})\right)-\operatorname{Pr}\left(y_{t}={\pi_{t}}(x_{t})\right)\right\rvert$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t})\\}.$

Let $\varepsilon>0$ be a free parameter. We can further decompose the above
into the following three terms:

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=1\\}$
$\displaystyle\hskip
36.135pt+\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0\\}$
$\displaystyle\hskip
36.135pt+\sum_{t=1}^{T}\bar{Z}_{t}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0\\}$
$\displaystyle=\mathtt{T}_{A}+\mathtt{T}_{B}+\mathtt{T}_{C},$

where $\mathtt{T}_{A},\mathtt{T}_{B}$ and $\mathtt{T}_{C}$ are defined to be
the first term, second term and the third term in the previous line
respectively, which we bound separately below:

  1. $\bullet$

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

$\displaystyle\mathtt{T}_{A}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=1\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=1\\}=T_{\varepsilon},$

where the last line uses the definition of $T_{\varepsilon}$.

  2. $\bullet$

Bound on $\mathtt{T}_{B}$: Using the definition of the function
$\mathtt{Query}$, we note that if ${\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t})$
and $\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0$, then
there must exists an $m\in[M]$ for which

$\displaystyle\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon.$ (81)

Thus, we have that

$\displaystyle(\mathtt{T}_{B})_{t}$ $\displaystyle\leq
Z_{t}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0\\}$
$\displaystyle\leq Z_{t}\mathbf{1}\\{\exists
m\in[M]:\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}$
$\displaystyle\leq\sum_{m=1}^{M}Z_{t}\mathbf{1}\\{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}$
$\displaystyle\leq\sum_{m=1}^{M}Z_{t}\frac{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}}{\varepsilon^{2}},$
(82)

where the second line plugs in (81), and the last line uses the fact that
$\mathbf{1}\\{a\geq b\\}\leq\nicefrac{{a^{2}}}{{b^{2}}}$ for all $a,b\geq 0$.
Gathering the above bound for all $t\leq T$ implies that

$\displaystyle\mathtt{T}_{B}$
$\displaystyle\leq\sum_{m=1}^{M}\sum_{t=1}^{T}Z_{t}\frac{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}}{\varepsilon^{2}}$
$\displaystyle\leq\frac{1}{\varepsilon^{2}}\sum_{m=1}^{M}{\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}^{m},T)},$

where the last line follows from an application of Lemma 30 for each
$m\in[M]$.

  3. $\bullet$

Bound on $\mathtt{T}_{C}$: Recall that

$\displaystyle\mathtt{T}_{C}$
$\displaystyle\leq\sum_{t=1}^{T}\bar{Z}_{t}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}(F^{\star}(x_{t}),{\vec{\Delta}}_{t}(x_{t}))=0,{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t})\\},$
(83)

where the last line just plugs in the condition under which $\bar{Z}_{t}=1$,
and removes the condition
$\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0$ from the
indicator. Next, note that for any $t\leq T$, an application of Lemma 30
implies that with probability at least $1-\delta$, for all $m\in M$,

$\displaystyle\left\|f^{\star,m}(x_{t})-f^{m}_{t}(x_{t})\right\|\leq\Delta^{m}_{t}(x_{t}).$
(84)

However, if $\mathtt{Query}(F^{\star}(x_{t}),{\vec{\Delta}}_{t}(x_{t}))=0$
then we must have that for all $F^{\prime}$ that satisfy
$\|F^{\prime}[:,m]-f^{m}_{t}(x_{t})\|\leq\Delta^{m}_{t}(x_{t})$ for all
$m\in[M]$, we must have that
$\mathtt{SelectAction}(F_{t}(x_{t}))=\mathtt{SelectAction}(F^{\prime}(x_{t}))$.
However, since $F^{\star}$ satisfies (84), we get that
$\mathtt{SelectAction}(F^{\star}(x_{t}))$
$=\mathtt{SelectAction}(F^{\prime}(x_{t}))$ or equivalently
${\pi_{t}}(x_{t})={\pi^{\star}}(x_{t})$. This contradicts the conditions in
(83), implying that

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

Gathering the bounds above, we get that

$\displaystyle\mathrm{Reg}_{T}\leq
T_{\varepsilon}+\frac{1}{\varepsilon^{2}}\sum_{m=1}^{M}{\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}^{m},T)}.$

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}^{m},T)}$
from Lemma 30, and ignoring $\log(1/\delta)$ factors and constants, we get

$\displaystyle\mathrm{Reg}_{T}\lesssim
T_{\varepsilon}+\frac{1}{\lambda\varepsilon^{2}}\sum_{m=1}^{M}{\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}^{m};T)}.$
(85)

Since $\varepsilon$ is a free parameter above, the final bound follows by
choosing the best parameter $\varepsilon$.

####  E.1.3 Total Number of Queries

Let $N_{T}$ denote the total number of expert queries made by the learner in
$T$ rounds of interactions, and let $\varepsilon>0$ be a free parameter. We
have:

$\displaystyle N_{T}$ $\displaystyle=\sum_{t=1}^{T}Z_{t}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}\left(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t})\right)=1\\}$
$\displaystyle=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}\left(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t})\right)=1,\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=1\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}\left(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t})\right)=1,\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=1\\}+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}\left(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t})\right)=1,\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0\\}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=1\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}\left(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t})\right)=1,\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0,\|{\vec{\Delta}}_{t}(x_{t})\|_{\infty}\leq\nicefrac{{\varepsilon}}{{3}}\\}$
$\displaystyle\hskip
72.26999pt+\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}\left(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t})\right)=1,\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0,\|{\vec{\Delta}}_{t}(x_{t})\|_{\infty}>\nicefrac{{\varepsilon}}{{3}}\\}$
$\displaystyle=\mathtt{T}_{\varepsilon}+\mathtt{T}_{D}+\mathtt{T}_{E},$

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

  1. $\bullet$

Bound on $\mathtt{T}_{D}$. Recall that the $t$-th term in $(T_{D})_{t}$ is

$\displaystyle(\mathtt{T}_{D})_{t}$
$\displaystyle=\mathbf{1}\\{\mathtt{Query}\left(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t})\right)=1,\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0,\sup_{m\in[M]}\Delta^{m}_{t}(x_{t})\leq\nicefrac{{\varepsilon}}{{3}}\\}.$

In the following, we will show that for any $t\leq T$, all the conditions in
the above indicator can not hold simultaneously. First note that if
$\mathtt{Query}\left(F_{t}(x_{t}),{\vec{\Delta}}_{t}(x_{t})\right)=1$, then
there exists an $\widetilde{F}$ such that

$\displaystyle\mathtt{SelectAction}(\widetilde{F}(x_{t})))\neq\mathtt{SelectAction}(F_{t}(x_{t}))$
(86)

and

$\displaystyle\forall
m\in[M]:\qquad\|\widetilde{F}(x_{t})[:,m]-F_{t}(x_{t})[:,m]\|\leq\Delta_{t}^{m}(x_{t}).$
(87)

On the other hand, recall Lemma 30, which implies that

$\displaystyle\forall
m\in[M]:\qquad\|F^{\star}(x_{t})[:,m]-F_{t}(x_{t})[:,m]\|\leq\Delta_{t}^{m}(x_{t}).$
(88)

Triangle inequality along with the bounds (87) and (88) implies that

$\displaystyle\forall
m\in[M]:\qquad\|F^{\star}(x_{t})[:,m]-\widetilde{F}(x_{t})[:,m]\|\leq
2\Delta_{t}^{m}(x_{t})<\varepsilon,$ (89)

where the second inequality holds whenever
$\sup_{m}\Delta_{t}^{m}(x_{t})\leq\nicefrac{{\varepsilon}}{{3}}$.

However, note that (89) contradicts the fact that
$\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0$ since both
$\widetilde{F}$ and $F_{t}$ satisfy the norm constraints in the definition of
$\mathtt{Query}$, but we can not simultaneously have that

$\displaystyle\mathtt{SelectAction}(F^{\star}(x_{t})))=\mathtt{SelectAction}(F_{t}(x_{t}))=\mathtt{SelectAction}(\widetilde{F}(x_{t})),$

due to (86). This implies that

$\displaystyle(\mathtt{T}_{D})_{t}$ $\displaystyle=0.$

  2. $\bullet$

Bound on $\mathtt{T}_{E}$. Again using the definition of $Z_{t}$, we note that

$\displaystyle\mathtt{T}_{E}$
$\displaystyle\leq\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\|{\vec{\Delta}}_{t}(x_{t})\|_{\infty}>\nicefrac{{\varepsilon}}{{3}}\\}$
$\displaystyle=\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\exists
m\in[M]:\Delta^{m}(x_{t})>\nicefrac{{\varepsilon}}{{3}}\\}$
$\displaystyle\leq\sum_{m=1}^{M}\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{\Delta^{m}(x_{t})>\nicefrac{{\varepsilon}}{{3}}\\}$

Using Lemma 34 to bound the term in the right hand side for each $m\in[M]$, we
get that

$\displaystyle\mathtt{T}_{E}$
$\displaystyle\leq\frac{180{\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}^{m},T)}}{\varepsilon^{2}}\sum_{m=1}^{M}\mathfrak{E}(\mathcal{F}^{m},\nicefrac{{\varepsilon}}{{3}};{f^{\star,m}})$

Gathering the bounds above, we have

$\displaystyle N_{T}$ $\displaystyle\leq
T_{\varepsilon}+\frac{180}{\varepsilon^{2}}\sum_{m=1}^{M}{\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}^{m},T)}\cdot\mathfrak{E}(\mathcal{F}^{m},\nicefrac{{\varepsilon}}{{3}};{f^{\star,m}}).$

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}^{m},T)}$,
we get that

$\displaystyle N_{T}$
$\displaystyle=\widetilde{\mathcal{O}}\left(T_{\varepsilon}+\frac{1}{\lambda\varepsilon^{2}}\sum_{m=1}^{M}{\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}^{m};T)}\cdot\mathfrak{E}(\mathcal{F}^{m},\nicefrac{{\varepsilon}}{{3}};{f^{\star,m}})+\frac{1}{\lambda^{2}\varepsilon^{2}}\log(1/\delta)\right).$

Since $\varepsilon$ is a free parameter above, the final bound follows by
choosing the best parameter $\varepsilon$.

####  E.1.4 Improved Bound when Aggregator $\mathscr{A}$ is $\eta$-Lipschitz

In this section, we show that the $1/\varepsilon^{2}$ term in the regret bound
(85) can be improved under additional modeling assumptions. Firstly, we assume
that corresponding to the contexts $\\{x_{t}\\}_{t\leq T}$, the labels
$\\{y_{t}\\}_{t=1}^{T}$ that we compare to in the regret definition in (77)
are sampled according to
$y_{t}\sim\mathscr{A}\left(\phi(F^{\star}(x_{t}))\right)$ (See (75) for more
details.). Secondly, we assume that the aggregator function $\mathscr{A}$ that
combines experts models is $\eta$-Lipschitz.

######  Assumption 2 (Lipschitzness).

For any $U,V\in\mathbb{R}^{K\times M}$, the function
$\mathscr{A}:\mathbb{R}^{K\times M}\mapsto\Delta(K)$ satisfies

$\|\mathscr{A}(U)-\mathscr{A}(V)\|\leq\eta\|U-V\|_{F}.$

We first provide a useful technical lemma that is crucial for our improved
bound.

######  Lemma 32.

Suppose that for any $x$, the labels $y$ are generated from
$y\sim\mathscr{A}(\phi(F^{\star}(x)))$. Then, for any $x\in\mathcal{X}$ and
function $F\in\mathcal{F}^{M}:\mathcal{X}\mapsto\mathbb{R}^{K\times M}$, we
have

$\displaystyle\lvert\operatorname{Pr}[y={\pi^{\star}}(x)]-\operatorname{Pr}[y=\pi(x)]\rvert\leq
2\eta\gamma\|F^{\star}(x)-F(x)\|_{{}_{F}}$

where
$\pi(x)=\mathtt{SelectAction}(F(x))=\operatorname*{argmax}_{k}\mathscr{A}(\phi(F(x))[k]$,
and
${\pi^{\star}}(x)=\mathtt{SelectAction}(F^{\star}(x))=\operatorname*{argmax}_{k}\mathscr{A}(\phi(F^{\star}(x)))[k]$.

###### Proof.

Assume that ${\pi^{\star}}(x)\neq\pi(x)$. Recalling that ${\pi^{\star}}(x)$
satisfies the condition
${\pi^{\star}}(x)=\operatorname*{argmax}_{k}\mathscr{A}(F^{\star}(k))$, we get
that

$\displaystyle 0$
$\displaystyle\leq\operatorname{Pr}[y_{t}={\pi^{\star}}(x)]-\operatorname{Pr}[y_{t}=\pi(x)]$
$\displaystyle=\mathscr{A}\left(\phi(F^{\star}(x))\right)[{\pi^{\star}}(x)]-\mathscr{A}\left(\phi(F^{\star}(x))\right)[\pi(x)]$
$\displaystyle\leq\mathscr{A}\left(\phi(F^{\star}(x))\right)[{\pi^{\star}}(x)]-\mathscr{A}\left(\phi(F^{\star}(x))\right)[\pi(x)]+\mathscr{A}\left(\phi(F(x))\right)[\pi(x)]-\mathscr{A}\left(\phi(F(x))\right)[{\pi^{\star}}(x)]$
$\displaystyle\leq
2\|\mathscr{A}\left(\phi(F^{\star}(x))\right)-\mathscr{A}\left(\phi(F(x))\right)\|$
$\displaystyle\leq 2\eta\|F^{\star}(x)-F(x)\|_{{}_{F}},$

where in the third line we used the fact that
$\mathscr{A}\left(\phi(F(x))\right)[\pi(x)]\geq\mathscr{A}\left(\phi(F(x))\right)[{\pi^{\star}}(x)]$,
and the last line holds because $\mathscr{A}$ is $\eta$-Lipschitz and $\phi$
is $\gamma$-Lipschitz. ∎

##### Improved Regret Bound.

Starting from the definition of regret, we note that:

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}\operatorname{Pr}\left({\pi_{t}}(x_{t})\neq
y_{t}\right)-\operatorname{Pr}\left({\pi^{\star}}(x_{t})\neq y_{t}\right)$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t})\\}\cdot\left\lvert\operatorname{Pr}\left(y_{t}={\pi^{\star}}(x_{t})\right)-\operatorname{Pr}\left(y_{t}={\pi_{t}}(x_{t})\right)\right\rvert$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t})\\}\cdot
2\eta\gamma\|F^{\star}(x_{t})-F_{t}(x_{t})\|_{F},$

where the last line plugs in Lemma 32. Let $\varepsilon>0$ be a free
parameter. We can further decompose the above as

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=1\\}\cdot
2\eta\gamma\|F^{\star}(x_{t})-F_{t}(x_{t})\|_{F}$ $\displaystyle\hskip
36.135pt+\sum_{t=1}^{T}Z_{t}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0\\}\cdot
2\eta\gamma\|F^{\star}(x_{t})-F_{t}(x_{t})\|_{F}$ $\displaystyle\hskip
36.135pt+\sum_{t=1}^{T}\bar{Z}_{t}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0\\}\cdot
2\eta\gamma\|F^{\star}(x_{t})-F_{t}(x_{t})\|_{F}$
$\displaystyle=\mathtt{T}_{A}+\mathtt{T}_{B}+\mathtt{T}_{C},$ (90)

where $\mathtt{T}_{A},\mathtt{T}_{B}$ and $\mathtt{T}_{C}$ are the first term,
second term and the third term in the previous line, respectively. Using the
identical analysis as in Appendix E.1.2, we can show that

$\displaystyle\mathtt{T}_{A}\leq
T_{\varepsilon}\qquad\text{and,}\qquad\mathtt{T}_{C}=0.$

We next provide the improved bound for $\mathtt{T}_{B}$. Using the definition
of the function $\mathtt{Query}$, we note that if
${\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t})$ and
$\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0$, then there
must exists an $m\in[M]$ for which

$\displaystyle\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon.$ (91)

Thus, considering only the $t$-th item in $\mathtt{T}_{B}$, we get that

$\displaystyle(\mathtt{T}_{B})_{t}$ $\displaystyle\leq
Z_{t}\mathbf{1}\\{{\pi_{t}}(x_{t})\neq{\pi^{\star}}(x_{t}),\mathtt{Query}(F^{\star}(x_{t}),\varepsilon\vec{\mathbbm{1}})=0\\}\cdot
2\eta\gamma\|F^{\star}(x_{t})-F_{t}(x_{t})\|_{F}$ $\displaystyle\leq
2\eta\gamma Z_{t}\mathbf{1}\\{\exists
m\in[M]:\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}\|F^{\star}(x_{t})-F_{t}(x_{t})\|_{F}.$
(92)

Let
$\mathcal{M}_{t}\vcentcolon={}\\{m\in[M]:\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}$,
and note that

$\displaystyle\|F^{\star}(x_{t})-F_{t}(x_{t})\|_{F}$
$\displaystyle=\sqrt{\sum_{m=1}^{M}\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}}$
$\displaystyle\leq\sqrt{(M-\lvert\mathcal{M}_{t}\rvert)\varepsilon^{2}+\sum_{m\in\mathcal{M}_{t}}\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}}$
$\displaystyle\leq\sqrt{M}\varepsilon+\sum_{m\in\mathcal{M}_{t}}\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|,$
(93)

where the second line uses the definition of $\mathcal{M}_{t}$ and the last
line is due to subadditivity of $\sqrt{\cdot}$. Using the definition of
$\mathcal{M}_{t}$ and the bound (93) in (92), we get that

$\displaystyle(\mathtt{T}_{B})_{t}$ $\displaystyle\leq 2\eta\gamma
Z_{t}\mathbf{1}\\{\forall
m\in\mathcal{M}_{t}:\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}\|F^{\star}(x_{t})-F_{t}(x_{t})\|_{F}$
$\displaystyle\leq 2\eta\gamma\sqrt{M}Z_{t}\mathbf{1}\\{\forall
m\in\mathcal{M}_{t}:\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}\varepsilon$
$\displaystyle\hskip
36.135pt+2\eta\gamma\sum_{m\in\mathcal{M}_{t}}Z_{t}\mathbf{1}\\{\forall
m\in\mathcal{M}_{t}:\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|.$

For the first term in the above,

$\displaystyle Z_{t}\mathbf{1}\\{\forall
m\in\mathcal{M}_{t}:\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}\varepsilon$
$\displaystyle\leq Z_{t}\mathbf{1}\\{\exists
m\in[M]:\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}\varepsilon$
$\displaystyle\leq\sum_{m=1}^{M}Z_{t}\mathbf{1}\\{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}\varepsilon$
$\displaystyle\leq\sum_{m=1}^{M}Z_{t}\frac{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}}{\varepsilon^{2}}\cdot\varepsilon$

where the last line follows by using the fact that $\mathbf{1}\\{a\geq
b\\}\leq\frac{a^{2}}{b^{2}}$ for all $a,b\geq 0$. For the second term,

$\displaystyle\sum_{m\in\mathcal{M}_{t}}Z_{t}\mathbf{1}\\{\forall
m\in\mathcal{M}_{t}:\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|$
$\displaystyle\leq\sum_{m\in\mathcal{M}_{t}}Z_{t}\mathbf{1}\\{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|>\varepsilon\\}\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|$
$\displaystyle\leq\sum_{m\in\mathcal{M}_{t}}Z_{t}\frac{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}}{\varepsilon}$
$\displaystyle\leq\sum_{m=1}^{M}Z_{t}\frac{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}}{\varepsilon},$

where second last line uses that $\mathbf{1}\\{a\geq
b\\}\leq\nicefrac{{a}}{{b}}$ for all $a,b\geq 0$. Taking the two together, we
get

$\displaystyle(\mathtt{T}_{B})_{t}$ $\displaystyle\leq
2\eta\gamma\left(\sqrt{M}+1\right)\sum_{m=1}^{M}Z_{t}\frac{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}}{\varepsilon}$
$\displaystyle\leq
4\eta\gamma\sqrt{M}\sum_{m=1}^{M}Z_{t}\frac{\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}}{\varepsilon}.$
(94)

The above implies that

$\displaystyle\mathtt{T}_{B}=\sum_{t=1}^{T}(\mathtt{T}_{B})_{t}$
$\displaystyle\leq\frac{4\eta\gamma\sqrt{M}}{\varepsilon}\sum_{m=1}^{M}\sum_{t=1}^{T}Z_{t}\|f_{t}^{m}(x_{t})-f^{\star,m}(x_{t})\|^{2}$
$\displaystyle\leq\frac{4\eta\gamma\sqrt{M}}{\varepsilon}\sum_{m=1}^{M}{\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}^{m},T)},$

where the last line plugs in the bound in Lemma 30.

Using the above derived bounds on $\mathtt{T}_{A}$, $\mathtt{T}_{B}$ and
$\mathtt{T}_{C}$ in (90), we get that:

$\displaystyle\mathrm{Reg}_{T}\leq
T_{\varepsilon}+\frac{4\eta\gamma\sqrt{M}}{\varepsilon}\sum_{m=1}^{M}{\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}^{m},T)}.$

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}^{m},T)}$
from Lemma 30, and ignoring $\log$ factors and constants, we get that

$\displaystyle\mathrm{Reg}_{T}\lesssim
T_{\varepsilon}+\frac{4\eta\gamma\sqrt{M}}{\lambda\varepsilon}\sum_{m=1}^{M}{\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}^{m};T)}+\frac{4\eta\gamma
M^{3/2}}{\lambda^{2}\varepsilon}\log(1/\delta).$

We finally note that the regret bound in Appendix E.1.2 also holds
simultaneously (since it holds even when we do not make the assumption 2).
Thus,

$\displaystyle\mathrm{Reg}_{T}\lesssim
T_{\varepsilon}+\min\\{\frac{1}{\lambda\varepsilon^{2}},\frac{4\eta\gamma\sqrt{M}}{\lambda\varepsilon}\\}\sum_{m=1}^{M}{\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}^{m};T)}.$

Notice that $\varepsilon$ is a free parameter above so the final bound follows
by taking $\inf$ over all feasible $\varepsilon$. The query complexity bound
remains identical to the one shown in Appendix E.1.3.

###  E.2 Imitation Learning (Proof of Theorem 7)

We next proceed to imitation learning with multiple experts.

1:Parameters $\delta,\gamma,\lambda,T$, function classes
$\\{\mathcal{F}^{m}_{h}\\}_{h\leq H,m\leq M}$, online oracles
$\\{\text{$\mathsf{Oracle}$}^{m}_{h}\\}_{h\leq H,m\leq M}$ 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}^{m}_{h},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}^{m}_{h};T)}+\frac{112}{\lambda^{2}}\log(4MH\log^{2}(T)/\delta).$

3:Compute $f^{m}_{1,h}=\text{$\mathsf{Oracle}$}_{1,h}(\emptyset)$ for each
$h\in[H]$ and $m\in[M]$.

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

5: Nature chooses the state $x_{t,1}$.

6: for $h=1$ to $H$ do

7: Define $F^{m}_{t,h}(x)\vcentcolon={}[f^{1}_{t,h}(x),\dots,f^{M}_{t,h}(x)]$.

8: Learner plays $\widehat{y}_{t,h}=\mathtt{SelectAction}(F_{t,h}(x_{t,h}))$.

9: Learner transitions to the next state in this round
$x_{t,h+1}\leftarrow\mathbb{T}_{t,h}(x_{t,h},\widehat{y}_{t,h})$.

10: For each $m\in[M]$, learner computes
$\displaystyle\Delta^{m}_{t,h}(x_{t,h})$
$\displaystyle\vcentcolon={}\max_{f\in\mathcal{F}^{m}_{h}}\leavevmode\nobreak\
\|f(x_{t,h})-f^{m}_{t,h}(x_{t,h})\|$ $\displaystyle\hskip
36.135pt\quad\text{s.t.}\quad\sum_{s=1}^{t-1}Z_{s,h}\left\|f(x_{s,h})-f^{m}_{s,h}(x_{s,h})\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}^{m}_{h},T)}.$
(95) and defines
${\vec{\Delta}}_{t,h}(x_{t,h})=[\Delta^{1}_{t,h}(x_{t,h}),\dots,\Delta^{M}_{t,h}(x_{t,h})]$.

11: Learner decides whether to query:
$Z_{t,h}=\mathtt{Query}(F_{t,h}(x_{t,h}),{\vec{\Delta}}_{t,h}(x_{t,h}))$

12: if $Z_{t,h}=1$ then

13: for $m=1$ to $M$ do

14: Learner queries expert $m$ for its label $y^{m}_{t,h}$ for $x_{t,h}$.

15:
$f^{m}_{t+1,h}\leftarrow\text{$\mathsf{Oracle}$}^{m}_{t+1,h}(\\{x_{t,h},y_{t,h}\\})$

16: else

17: $f^{m}_{t+1,h}\leftarrow f^{m}_{t,h}$ for each $m\in[M]$.

Algorithm 7 InteRActiVe ImitatiOn Learning VIa Active Queries to
$\boldsymbol{M}$ Experts (RAVIOLI$-\mathsf{M}$)

We first discuss the setup and the relevant notation. We are in the imitation
learning setup introduced in Appendix D.3. In particular, the learner
interacts with $M$ experts in $T$ episodes/rounds, each consisting of $H$
timesteps. For any $h\leq H$, each of the $M$ experts have a ground truth
model ${f^{\star,m}_{h}}$ respectively. Given the context $x_{t,h}$ for time
step $h$ in round $t$, the learner plays the actions
$\widehat{y}_{t,h}\in[K]$, and can additionally choose to query the experts
(by setting $Q_{t,h}=1$) to receive noisy feedback
$y_{t,h}^{m}\sim\phi({f^{\star,m}_{h}}(x_{t}))$ from each expert $m\in[M]$.
After playing the chosen action $\widehat{y}_{t,h}$, the learner then
transitions to state
$x_{t,h+1}\leftarrow\mathbb{T}_{t,h}(x_{t,h},\widehat{y}_{t,h})$ where
$\\{\mathbb{T}_{t,h}\\}_{h\in[H]}$ is a sequence of deterministic dynamics
(unknown to the learner).

The setup for imitation learning builds on the notation introduced for
selective sampling with multiple experts in Appendix E.1. In particular, in
Algorithm 7, for any round $t\leq T$ and $h\leq H$:

  1. $\bullet$

The aggregation function $\mathscr{A}:\mathbb{R}^{K\times
M}\mapsto\mathbb{R}^{K}$, known to the learner, maps the predictions of the
estimated experts to distributions over actions. Some illustrative examples
are given in Section 5 under (14).

  2. $\bullet$

The function $\mathtt{SelectAction}{}:\mathbb{R}^{K\times M}\mapsto[K]$
chooses the action to play at round $t$, and is defined as:

$\displaystyle\mathtt{SelectAction}(F_{t,h}(x_{t,h}))=\operatorname*{argmax}_{k}\mathscr{A}\left(\phi(F_{t,h}(x_{t,h}))\right)[k],$
(96)

where $F_{t,h}(x_{t,h}))=[f^{1}_{t,h}(x_{t,h})),\dots,f^{M}_{t,h}(x_{t,h}))]$,
and $\phi$ denotes the link-function given in (2).

  3. $\bullet$

Our goal in Algorithm 7 is to compete with the policy ${\pi^{\star}}$ defined
such that for any $x\in\mathcal{X}_{h}$,

$\displaystyle{\pi^{\star}}(x)=\mathtt{SelectAction}(F_{h}^{\star}(x))$ (97)

where
$F_{h}^{\star}(x)=[f^{\star,1}_{h}(x),\dots,f^{\star,1}_{h}(x)]\in\mathbb{R}^{K\times
M}$.

  4. $\bullet$

Given the context $x_{t,h}$ and the function
$F_{t,h}:\mathcal{X}\mapsto\mathbb{R}^{K\times M}$, the learner decided
whether to query via
$Z_{t,h}=\mathtt{Query}(F_{t,h}(x_{t,h}),{\vec{\Delta}}_{t,h}(x_{t,h}))$ where
we define the function $\mathtt{Query}:\mathbb{R}^{K\times
M}\times\mathbb{R}^{M}$ as

$\displaystyle\mathtt{Query}(U;\vec\varepsilon)$
$\displaystyle\vcentcolon={}\sup_{V\in\mathbb{R}^{K\times
M}}\leavevmode\nobreak\
\mathbf{1}\\{\mathtt{SelectAction}(U)\neq\mathtt{SelectAction}(V)\\}\quad$
$\displaystyle\hskip
36.135pt\text{s.t.}\quad\|U[:,m]-V[:,m]\|_{2}\leq\vec\varepsilon[m]\qquad\forall
m\leq M.$ (98)

At round $t$, the learner interactions with transition dynamics
$\\{\mathbb{T}_{t,h}\\}_{h\leq H}$ and collects data. Without loss of
generality, we assume that the learner always starts from the state $x_{t,1}$.
We next recall the interaction at round $t$:

  1. $\bullet$

The learner collects data using the policy $\pi_{t}$, defined such that

$\displaystyle\pi_{t}(x)=\mathtt{SelectAction}(f_{t,h}(x_{t,h})).$

for any $h\leq H$, and state $x\in\mathcal{X}_{h}$.

  2. $\bullet$

For any policy $\pi$, we use the notation $\tau^{\pi}_{t}$ to denote the
(counterfactual) trajectory that would have been generated by running $\pi$ on
the deterministic dynamics $\\{\mathbb{T}_{t,h}\\}_{h\leq H}$ with the start
state $x_{t,1}$, i.e.

$\displaystyle\tau^{\pi}_{t}=\left\\{x_{t,1}^{\pi},\pi(x_{t,1}^{\pi}),\dots,x_{t,H}^{\pi},\pi(x_{t,H}^{\pi})\right\\},$
(99)

where $x_{t,1}^{\pi}=x_{t,1}$ and
$x_{t,h+1}^{\pi}=\mathbb{T}_{t,h}(x_{t,h}^{\pi},\pi(x_{t,h}^{\pi}))$.

  3. $\bullet$

For any trajectory $\tau=\\{x_{1},a_{1},\dots,x_{H},a_{H}\\}$, we define the
total return

$\displaystyle R(\tau)$ $\displaystyle=\sum_{h=1}^{H}r(x_{h},a_{h}).$ (100)

The goal of the learner is to minimize its regret which is given by

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}R(\tau^{\pi^{\star}}_{t})-\sum_{t=1}^{T}R(\tau^{{\pi_{t}}}_{t}).$
(101)

Finally, our bounds depend on the notation of margin defined w.r.t. the
function $\mathtt{Query}$ defined above. In particular, for a sequence of
contexts $\\{\\{T_{t,h}\\}_{h\leq H}\\}_{t\leq T}$, we define
$T_{\varepsilon,h}$ as

$\displaystyle
T_{\varepsilon,h}=\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}(F_{h}^{\star}(x_{t,h}^{\pi^{\star}}),\varepsilon\vec{\mathbbm{1}})=1\\}.$
(102)

In the above we count for the number of time steps when the counterfactual
states $\\{x_{t,h}^{\pi^{\star}}\\}_{t\leq T}$, reached under the given
dynamics if we had executed ${\pi^{\star}}$, are within the
$\varepsilon$-margin region. Note that even though the observed states
$\\{\\{x_{t,h}\\}_{h\leq H}\\}_{t\leq T}$ are such that
$\sum_{t=1}^{T}\mathbf{1}\\{\mathtt{Query}(F_{h}^{\star}(x_{t,h}),\varepsilon\vec{\mathbbm{1}})=1\\}$
is large, we would not pay for this in our margin term $T_{\varepsilon,h}$.

####  E.2.1 Supporting Technical Results

######  Lemma 33.

With probability at least $1-{}\delta$, for any $m\leq M$, and $t\leq T$ and
$h\leq H$, the function ${f^{\star,m}}$ satisfies

  1. $(a)$

$\sum_{s=1}^{t-1}Z_{s,h}\|{f^{\star,m}_{h}}(x_{s,h})-f^{m}_{s,h}(x_{s,h})\|^{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}^{m}_{h},T)}$
,

  2. $(b)$

$\|{f^{\star,m}_{h}}(x_{t,h})-f^{m}_{t,h}(x_{t,h})\|\leq\Delta^{m}_{t,h}(x_{t,h})$,

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}^{m}_{h},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}^{m}_{h};T)}+\frac{112}{\lambda^{2}}\log(4MH\log^{2}(T)/\delta).$

###### Proof.

  1. $(a)$

We first note that we do not query oracle when $Z_{s,h}=0$, and thus we can
ignore the time steps for which $Z_{s,h}=0$. Hence, for each $h\in[H]$ and
$m\in[M]$, applying Lemma 5 yields

$\sum_{s=1}^{t-1}Z_{s,h}\|{f^{\star,m}_{h}}(x_{s,h})-f_{s,h}(x_{s,h})\|^{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}^{m}_{h};T)}+\frac{112}{\lambda^{2}}\log(4\log^{2}(T)/\delta)$

for all $t\leq T$. Then, we take the union bound for all $h\in[H]$ and
$m\in[M]$, which completes the proof.

  2. $(b)$

The second part follows from using part-(a) along with the definition in (95).

∎

The next lemma bound the number of times when
$\Delta^{m}_{t,h}(x_{t,h})\geq\zeta$, and we query. Note that Lemma 34 holds
even if the sequence $\\{x_{t,h}\\}_{t\leq T}$ was adversarially generated.

######  Lemma 34.

Let ${f^{\star,m}}$ satisfy Lemma 33 , and let $\Delta^{m}_{t,h}(x_{t,h})$ be
defined in Algorithm 7. Suppose Algorithm 7 is run on the data sequence
$\\{x_{t,h}\\}_{t\leq 1}$, and let $Z_{t,h}$ be defined in line 11. Then, for
any $\zeta>0$, with probability at least $1-M\delta$, for any $m\in[M]$, and
$h\leq H$,

$\displaystyle\sum_{t=1}^{T}Z_{t,h}\mathbf{1}\left\\{\Delta^{m}_{t,h}(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}^{m}_{h},T)}}{\zeta^{2}}\cdot\mathfrak{E}(\mathcal{F}^{m}_{h},\nicefrac{{\zeta}}{{2}};{f^{\star,m}_{h}}),$

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

###### Proof.

The proof is identical to the proof of Lemma 11 where we handle each $m\in[M]$
and $h\in[H]$ separately, and substitute the corresponding bounds for
${f^{\star,m}_{h}}$ via Lemma 33 (instead of using Lemma 10). We skip the
proof for conciseness. ∎

####  E.2.2 Regret Bound

Suppose the trajectories at round $t$ are generated using the deterministic
dynamics
$\\{\mathbb{T}_{t,1},\dots,\mathbb{T}_{t,H}\\}=\mathscr{T}(\cdot\leavevmode\nobreak\
;\leavevmode\nobreak\ \iota_{t})$ where $\iota_{t}$ denotes the random seed
that captures all of the stochasticity at round $t$ 111111We use random seed
$\iota_{t}$ to capture all the stochasticity in the choice of
$\\{\mathbb{T}_{t,h}\\}_{h\leq H,t\leq T}$. However, all our proofs extend to
IL learning with an arbitrary, and possibly adversarial, choice of
$\\{\mathbb{T}_{t,h}\\}_{h\leq H,t\leq T}$.

Recall that the policies ${\pi^{\star}}$ and ${\pi_{t}}$ such that for any
$h\leq H$ and $x\in\mathcal{X}_{h}$,
${\pi^{\star}}(x)=\mathtt{SelectAction}(F_{h}^{\star}(x)),$
and,${\pi_{t}}(x)=\mathtt{SelectAction}(F_{t,h}(x)).$ Note that Algorithm 7
collects trajectories using the policy ${\pi_{t}}$ at round $t$. Thus, we have

$\displaystyle x_{t,h}^{{\pi_{t}}}=x_{t,h},$ (103)

where $x_{t,h}$ denotes the state at time step $h$ in round $t$ of Algorithm
7. Finally, let $\varepsilon>0$ be a free parameter. We start with the bound
on the regret at time $t$.

##### Step 1: Bounding the difference in cumulative return at round $t$.

Fix any $t\leq T$, and let $\tau_{t}^{{\pi_{t}}}$ and $\tau_{t}^{\pi^{\star}}$
denote the trajectories that would have been sampled using the policies
${\pi_{t}}$ and the policy ${\pi^{\star}}$ at round $t$. Furthermore, define
the set $\mathtt{X}_{\varepsilon}$ as

$\displaystyle\mathtt{X}_{\varepsilon}\vcentcolon={}\bigcup_{h=1}^{H}\\{x\in\mathcal{X}_{h}\mid{}\mathtt{Query}(F_{h}^{\star}(x),\varepsilon\vec{\mathbbm{1}})=1\\}$
(104)

Using Lemma 27 for the policies ${\pi_{t}}$ and ${\pi^{\star}}$, and the set
$\mathtt{X}_{\varepsilon}$ defined above, we get that

$\displaystyle R(\tau_{t}^{{\pi^{\star}}})-R(\tau_{t}^{{\pi_{t}}})$
$\displaystyle\leq
2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{h=1}^{H}\mathbf{1}\\{{\pi_{t}}(x_{t,h}^{{\pi_{t}}})\neq{\pi^{\star}}(x_{t,h}^{{\pi_{t}}}),x_{t,h}^{{\pi_{t}}}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{h=1}^{H}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle\hskip
130.08621pt+2H\sum_{h=1}^{H}\bar{Z}_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\mathtt{T}_{A}+2H\mathtt{T}_{B},$
(105)

where the second line is obtained by using the relation (103) in the second
line. The last line simply defines $\mathtt{T}_{A}$ and $\mathtt{T}_{B}$ to be
the second and the third term in the previous line, respectively, without the
$2H$ multiplicative factor. We bound these two terms separately below:

  1. $\bullet$

Bound on $\mathtt{T}_{A}$. Using the definition of $\mathtt{X}_{\varepsilon}$
from (104), we note that

$\displaystyle\mathtt{T}_{A}$
$\displaystyle=\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),x_{t,h}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h}),\mathtt{Query}(F_{h}^{\star}(x_{t,h}),\varepsilon\vec{\mathbbm{1}})=0\\}$
$\displaystyle=\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{\exists
m\in[m]\leavevmode\nobreak\ :\leavevmode\nobreak\
\|f^{m}_{t,h}(x_{t,h})-{f^{\star,m}_{h}}(x_{t,h})\|>\varepsilon\\},$

where the last line follows from the fact that the definition of
$\mathtt{Query}$ and the fact that
${\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h})$ implies that there exists some
$m\in[M]$ for which
$\|f^{m}_{t,h}(x_{t,h})-{f^{\star,m}_{h}}(x_{t,h})\|>\varepsilon$. The above
implies that

$\displaystyle\mathtt{T}_{A}$
$\displaystyle\leq\sum_{m=1}^{M}\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{\|f^{m}_{t,h}(x_{t,h})-{f^{\star,m}_{h}}(x_{t,h})\|>\varepsilon\\}.$

  2. $\bullet$

Bound on $\mathtt{T}_{B}$. First note that Lemma 33 implies that with
probability at least $1-\delta$, for all $m\leq M$ and $h\leq H$,

$\displaystyle\|{f^{\star,m}_{h}}(x_{t,h})-f^{m}_{t,h}(x_{t,h})\|\leq\Delta^{m}_{t,h}(x_{t,h}).$
(106)

Next, note that

$\displaystyle\mathtt{T}_{B}$
$\displaystyle\leq\sum_{h=1}^{H}\bar{Z}_{t,h}\mathbf{1}\\{{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h})\\}$
(107)
$\displaystyle=\sum_{h=1}^{H}\mathbf{1}\\{\mathtt{Query}(F_{t,h}(x_{t,h}),{\vec{\Delta}}_{t,h}(x_{t,h}))=0,{\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h})\\},$

where in the last line follows from plugging in the query condition under
which $Z_{t,h}=0$. However note that for any $h\leq H$ for which
$\mathtt{Query}(F_{t,h}(x_{t,h}),{\vec{\Delta}}_{t,h}(x_{t,h}))=0$, by the
definition of $\mathtt{Query}$ and the fact that
${\pi_{t}}(x_{t,h})\neq{\pi^{\star}}(x_{t,h})$, there must exist some
$m\in[M]$ such that

$\displaystyle\|{f^{\star,m}_{h}}(x_{t,h})-f^{m}_{t,h}(x_{t,h})\|>\Delta^{m}_{t,h}(x_{t,h}).$

However, the above contradicts (106), and thus with probability at least
$1-\delta$,

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

Plugging the above bounds on $\mathtt{T}_{A}$ and $\mathtt{T}_{B}$ in (105),
we get that

$\displaystyle R(\tau_{t}^{{\pi^{\star}}})-R(\tau_{t}^{{\pi_{t}}})$
$\displaystyle\leq
2H\sum_{h=1}^{H}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{m=1}^{M}\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{\|f^{m}_{t,h}(x_{t,h})-{f^{\star,m}_{h}}(x_{t,h})\|>\varepsilon\\}.$
(109)

##### Step 2: Aggregating over all time steps.

Using the bound in (109) for each round $t$, we get that

$\displaystyle\mathrm{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}\left(R(\tau_{t}^{{\pi^{\star}}})-R(\tau_{t}^{{\pi_{t}}})\right)$
$\displaystyle\leq
2H\sum_{h=1}^{H}\sum_{t=1}^{T}\mathbf{1}\\{x_{t,h}^{{\pi^{\star}}}\in\mathtt{X}_{\varepsilon}\\}+2H\sum_{t=1}^{T}\sum_{m=1}^{M}\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{\|f^{m}_{t,h}(x_{t,h})-{f^{\star,m}_{h}}(x_{t,h})\|>\varepsilon\\}.$

Using the fact that $\mathbf{1}\\{a\geq b\\}\leq\nicefrac{{a^{2}}}{{b^{2}}}$
for any $a,b\geq 0$, and the definition of $T_{\varepsilon,h}$ in the above,
we get that

$\displaystyle\mathrm{Reg}_{T}$ $\displaystyle\leq
2H\sum_{h=1}^{H}T_{\varepsilon,h}+2H\sum_{t=1}^{T}\sum_{m=1}^{M}\sum_{h=1}^{H}Z_{t,h}\frac{\|f^{m}_{t,h}(x_{t,h})-{f^{\star,m}_{h}}(x_{t,h})\|^{2}}{\varepsilon^{2}}$
$\displaystyle\leq
2H\sum_{h=1}^{H}T_{\varepsilon,h}+\frac{2H}{\varepsilon^{2}}\sum_{m=1}^{M}\sum_{h=1}^{H}{\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}^{m}_{h},T)}.$
(110)

where the last line follows from using the bound in Lemma 33.

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}^{m}_{h},T)}$
and ignoring $\log$ factors and constants, we get that

$\displaystyle\mathrm{Reg}_{T}\lesssim
H\sum_{h=1}^{H}T_{\varepsilon,h}+\frac{H}{\lambda\varepsilon^{2}}\sum_{m=1}^{M}\sum_{h=1}^{H}{\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}^{m}_{h};T)}+\frac{MH^{2}}{\lambda^{2}\varepsilon^{2}}\log(1/\delta).$

Notice that $\varepsilon$ is a free parameter above so the final bound follows
by taking $\inf$ over all feasible $\varepsilon$.

####  E.2.3 Total Number of Queries

Fix any $t\leq T$, and let $h_{t}$ denote the first time step at round $t$ for
which $Z_{t,h_{t}}=1$, if such a time-step exists (and is set to be $H+1$
otherwise). We first observe that for all $h\leq h_{t}$, we have
${\pi^{\star}}(x_{t,h})={\pi_{t}}(x_{t,h})$. To see this, note that

$\displaystyle Z_{t,h_{t}}\mathbf{1}\\{\exists
h<h_{t}:{\pi^{\star}}(x_{t,h})\neq\pi_{t}(x_{t,h})\\}$
$\displaystyle\leq\sum_{h=1}^{h_{t}-1}Z_{t,h_{t}}\mathbf{1}\\{{\pi^{\star}}(x_{t,h})\neq\pi_{t}(x_{t,h})\\}$
$\displaystyle\leq\sum_{h=1}^{h_{t}-1}Z_{t,h_{t}}\bar{Z}_{t,h}\mathbf{1}\\{{\pi^{\star}}(x_{t,h})\neq\pi_{t}(x_{t,h})\\}$
$\displaystyle\leq\sum_{h=1}^{h_{t}-1}\bar{Z}_{t,h}\mathbf{1}\\{{\pi^{\star}}(x_{t,h})\neq\pi_{t}(x_{t,h})\\}$

where in second inequality above, we used the fact that $Z_{t,h}=0$ (and thus
$\bar{Z}_{t,h}=1$) for all $h<h_{t}$, by the definition of $h_{t}$. Observe
that the right hand side in the last inequality above is equivalent to the
term (107) in the bound on $\mathtt{T}_{B}$ above (where sum is now till
$h_{t}$ instead of $H$). Thus, using the bound in (108), we get that

$\displaystyle Z_{t,h_{t}}\mathbf{1}\\{\exists
h<h_{t}:{\pi^{\star}}(x_{t,h})\neq{\pi_{t}}(x_{t,h})\\}=0,$

and thus

$\displaystyle{\pi^{\star}}(x_{t,h})={\pi_{t}}(x_{t,h})\qquad\text{for all
$h\leq h_{t}$}.$ (111)

Next, let $\varepsilon>0$ be a free parameter, and note that plugging in the
definition of $h_{t}$, we get that the total number of samples is bounded as:

$\displaystyle N_{T}$ $\displaystyle=\sum_{t=1}^{T}\sum_{h=1}^{H}Z_{t,h}$
$\displaystyle\leq H\sum_{t=1}^{T}Z_{t,h_{t}}$
$\displaystyle=H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}+H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\notin\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}+H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\notin\mathtt{X}_{\varepsilon},\|\Delta^{m}_{t,h_{t}}(x_{t,h_{t}})\|_{\infty}\leq\frac{\varepsilon}{4}\\}$
$\displaystyle\hskip
108.405pt+H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\notin\mathtt{X}_{\varepsilon},\|\Delta^{m}_{t,h_{t}}(x_{t,h_{t}})\|_{\infty}>\frac{\varepsilon}{4}\\}$
$\displaystyle=\mathtt{T}_{C}+\mathtt{T}_{D}+\mathtt{T}_{E},$

where $\mathtt{T}_{C}$, $\mathtt{T}_{D}$ and $\mathtt{T}_{E}$ are the first,
second and the third term respectively in the previous line. We bound them
separately below.

  1. $\bullet$

Bound on $\mathtt{T}_{C}$. Fix any $t\leq T$. Using the relation in (111),
note that ${\pi^{\star}}(x_{t,h})={\pi_{t}}(x_{t,h})$ for all $h<h_{t}$. Thus,
the corresponding trajectories would be identical till time step $h_{t}$,
which implies that $x_{t,h_{t}}=x^{{\pi^{\star}}}_{t,h_{t}}$. Using this
property in the $\mathtt{T}_{C}$, we get that

$\displaystyle(\mathtt{T}_{C})_{t}$
$\displaystyle=H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{x^{{\pi^{\star}}}_{t,h_{t}}\in\mathtt{X}_{\varepsilon}\\}$
$\displaystyle\leq
H\sum_{t=1}^{T}\sum_{h=1}^{H}Z_{t,h}\mathbf{1}\\{x^{{\pi^{\star}}}_{t,h}\in\mathtt{X}_{\varepsilon}\\}$
$\displaystyle=H\sum_{h=1}^{H}T_{\varepsilon,h},$

where the last line plugs in the definition of $T_{\varepsilon,h}$.

  2. $\bullet$

Bound on $\mathtt{T}_{D}$. First note that

$\displaystyle(\mathtt{T}_{D})_{t}$
$\displaystyle=H\mathbf{1}\\{\mathtt{Query}\left(F_{t,h_{t}}(x_{t,h_{t}}),{\vec{\Delta}}_{t,h_{t}}(x_{t,h_{t}})\right)=1,\mathtt{Query}(F^{\star}(x_{t,h_{t}}),\varepsilon\vec{\mathbbm{1}})=0,\sup_{m\in[M]}\Delta^{m}_{t}(x_{t,h_{t}})\leq\nicefrac{{\varepsilon}}{{4}}\\}.$

In the following, we will show that all the conditions in the above indicator
can not hold simultaneously. First note that since
$\mathtt{Query}\left(F_{t,h_{t}}(x_{t,h_{t}}),{\vec{\Delta}}_{t,h_{t}}(x_{t,h_{t}})\right)=1$,
there exists an $\widetilde{F}$ such that

$\displaystyle\mathtt{SelectAction}(\widetilde{F}(x_{t,h_{t}})))\neq\mathtt{SelectAction}(F_{t,h_{t}}(x_{t,h_{t}}))$
(112)

and

$\displaystyle\forall
m\in[M]:\qquad\|\widetilde{F}(x_{t,h_{t}})[:,m]-F_{t,h_{t}}(x_{t,h_{t}})[:,m]\|\leq\Delta_{t,h_{t}}^{m}(x_{t,h_{t}}).$
(113)

On the other hand, recall that Lemma 33 implies that

$\displaystyle\forall
m\in[M]:\qquad\|F^{\star}(x_{t,h_{t}})[:,m]-F_{t,h_{t}}(x_{t,h_{t}})[:,m]\|\leq\Delta_{t,h_{t}}^{m}(x_{t,h_{t}}).$
(114)

Since,
$\sup_{m}\Delta_{t,h_{t}}^{m}(x_{t,h_{t}})\leq\nicefrac{{\varepsilon}}{{4}}$,
an application of Triangle inequality along with the bounds (113) and (114)
imply that

$\displaystyle\forall
m\in[M]:\qquad\|F^{\star}(x_{t,h_{t}})[:,m]-\widetilde{F}(x_{t,h_{t}})[:,m]\|\leq
2\Delta_{t,h_{t}}^{m}(x_{t,h_{t}})<\varepsilon.$ (115)

But the above contradicts the fact that
$\mathtt{Query}(F^{\star}(x_{t,h_{t}}),\varepsilon\vec{\mathbbm{1}})=0$ since
both $\widetilde{F}$ and $F_{t}$ satisfy the norm constraints in the
definition of $\mathtt{Query}$, but we can not simultaneously have that

$\displaystyle\mathtt{SelectAction}(F^{\star}(x_{t,h_{t}})))=\mathtt{SelectAction}(F_{t,h_{t}}(x_{t,h_{t}}))=\mathtt{SelectAction}(\widetilde{F}(x_{t,h_{t}})),$

due to (112). Thus, we must have that

$\displaystyle(\mathtt{T}_{D})_{t}$ $\displaystyle=0.$

  3. $\bullet$

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

$\displaystyle\mathtt{T}_{E}$ $\displaystyle\leq
H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{\|{\vec{\Delta}}_{t,h_{t}}(x_{t,h_{t}})\|_{\infty}>\nicefrac{{\varepsilon}}{{4}}\\}$
$\displaystyle=H\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{\exists
m\in[M]:\Delta^{m}_{t,h_{t}}(x_{t,h_{t}})>\nicefrac{{\varepsilon}}{{4}}\\}$
$\displaystyle\leq
H\sum_{m=1}^{M}\sum_{t=1}^{T}Z_{t,h_{t}}\mathbf{1}\\{\Delta^{m}_{t,h_{t}}(x_{t,h_{t}})>\nicefrac{{\varepsilon}}{{4}}\\}$
$\displaystyle\leq
H\sum_{h=1}^{H}\sum_{m=1}^{M}\sum_{t=1}^{T}Z_{t,h}\mathbf{1}\\{\Delta^{m}_{t,h}(x_{t,h})>\nicefrac{{\varepsilon}}{{4}}\\},$

where the last line simply upper bound the term for $h_{t}$ by the
corresponding terms for all $h\leq H$.

Using Lemma 34 to bound the term in the right hand side for each $m\in[M]$ and
$h\leq H$, we get that

$\displaystyle\mathtt{T}_{E}$
$\displaystyle\leq\sum_{h=1}^{H}\sum_{m=1}^{M}\frac{320H{\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}^{m}_{h},T)}}{\varepsilon^{2}}\cdot\mathfrak{E}(\mathcal{F}^{m}_{h},\frac{\varepsilon}{8};{f^{\star,m}_{h}}).$

Gathering the bound above, we get that

$\displaystyle N_{T}$ $\displaystyle\leq
H\sum_{h=1}^{H}T_{\varepsilon,h}+\frac{320H}{\varepsilon^{2}}\sum_{h=1}^{H}\sum_{m=1}^{M}{\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}^{m}_{h},T)}\cdot\mathfrak{E}(\mathcal{F}^{m}_{h},\frac{\varepsilon}{8};{f^{\star,m}_{h}}).$

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}^{m}_{h},T)}$
and ignoring $\log$ factors and constants, we get that

$\displaystyle N_{T}$ $\displaystyle\lesssim
H\sum_{h=1}^{H}T_{\varepsilon,h}+\frac{H}{\lambda\varepsilon^{2}}\sum_{h=1}^{H}\sum_{m=1}^{M}{\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}^{m}_{h};T)}\cdot\mathfrak{E}(\mathcal{F}^{m}_{h},\nicefrac{{\varepsilon}}{{8}};{f^{\star,m}_{h}})+\frac{MH^{2}}{\lambda^{2}\varepsilon^{2}}\log(1/\delta).$

Notice that $\varepsilon$ is a free parameter above so the final bound follows
by taking $\inf$ over all feasible $\varepsilon$.