$\mathcal{R}_{p,\pi^{E}}$ satisfies:

$\displaystyle\mathcal{R}_{p,\pi^{E}}=\\{$ $\displaystyle
r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\;Q^{*}_{h}(s,\pi^{E}_{h}(s);p,r)\geq Q^{*}_{h}(s,a;p,r)\\}.$

###### Proof.

The statement of the theorem is equivalent to the necessary and sufficient
condition:

$\displaystyle
J(\pi^{E};\mu_{0},p,r)=\max\limits_{\pi\in\Pi}J(\pi;\mu_{0},p,r)\iff\forall(s,h)\in\mathcal{S}^{p,\pi^{E}}:\,Q^{*}_{h}(s,\pi^{E}_{h}(s);p,r)=\max\limits_{a\in\mathcal{A}}Q^{*}_{h}(s,a;p,r).$

We split the proof in two parts. First we show the sufficiency, then the
necessity.

Let us start with the sufficiency. Let $r$ be any reward in $\mathfrak{R}$ and
$p$ any transition model in $\mathcal{P}$. By contradiction, suppose that
there exists a policy
$\pi^{\prime}\in\operatorname*{arg\,max}_{\pi\in\Pi}J(\pi;\mu_{0},p,r)$ for
which there exists a $(s^{\prime},h^{\prime})$ in the union of the supports of
the $h\in\llbracket H\rrbracket$ distributions
$\rho_{h}^{p,\pi^{\prime}}(\cdot)$ in which
$Q^{*}_{h^{\prime}}(s^{\prime},\pi_{h^{\prime}}^{\prime}(s^{\prime});p,r)<\max_{a^{\prime}\in\mathcal{A}}Q^{*}_{h^{\prime}}(s^{\prime},a^{\prime};p,r)$
(the notation refers to a deterministic $\pi^{\prime}$ but it can be taken
stochastic by computing the expected value). Let
$\pi^{*}\in\operatorname*{arg\,max}_{\pi\in\Pi}V^{\pi}_{h}(s;p,r)\;\forall(s,h)\in\mathcal{S}\times\llbracket
H\rrbracket$ be an auxiliary optimal policy whose existence is a widely-known
result in RL (see Puterman, 1994). By hypothesis, it holds that:

$\displaystyle
J(\pi^{\prime};\mu_{0},p,r)=\max\limits_{\pi\in\Pi}J(\pi;\mu_{0},p,r)=J(\pi^{*};\mu_{0},p,r).$

From the performance difference lemma (Kakade & Langford, 2002), by denoting
the advantage function by $A_{h}^{\pi}(s,a;p,r)\coloneqq
Q_{h}^{\pi}(s,a;p,r)-V_{h}^{\pi}(s;p,r)$, we can write:

$\displaystyle J(\pi^{\prime};\mu_{0},p,r)-J(\pi^{*};\mu_{0},p,r)$
$\displaystyle=\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{\prime}}(\cdot,\cdot)}\bigl{[}A_{h}^{\pi^{*}}(s,a;p,r)\bigr{]}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\rho_{h^{\prime}}^{p,\pi^{\prime}}(s^{\prime})A_{h^{\prime}}^{\pi^{*}}(s^{\prime},\pi_{h^{\prime}}^{\prime}(s^{\prime});p,r)$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{<}0,$

where at (1) we have used that in all $(s,h)\in\mathcal{S}\times\llbracket
H\rrbracket\setminus\\{(s^{\prime},h^{\prime})\\}$ the policy $\pi^{\prime}$
prescribes the action greedy w.r.t. $Q^{*}$, and thus the advantage is 0, and
(2) holds by (contradiction) hypothesis. However, by hypothesis, we know that
$J(\pi^{*};\mu_{0},p,r)-J(\pi^{\prime};\mu_{0},p,r)=0$, thus we have obtained
a contradiction, so the sufficiency holds.

As far as the necessity is concerned, let us consider again an auxiliary
optimal policy $\pi^{*}$ and a policy $\pi^{\prime}$ such that
$Q^{*}_{h^{\prime}}(s^{\prime},\pi_{h^{\prime}}^{\prime}(s^{\prime});p,r)=\max_{a^{\prime}\in\mathcal{A}}Q^{*}_{h^{\prime}}(s^{\prime},a^{\prime};p,r)$
in the support of the $h\in\llbracket H\rrbracket$ distributions
$\rho_{h}^{p,\pi^{\prime}}(\cdot)$. By applying the performance difference
lemma, we can write:

$\displaystyle J(\pi^{\prime};\mu_{0},p,r)-J(\pi^{*};\mu_{0},p,r)$
$\displaystyle=\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s\sim\rho_{h}^{p,\pi^{\prime}}(\cdot)}\bigl{[}A_{h}^{\pi^{*}}(s,a;p,r)\bigr{]}$
$\displaystyle=\sum\limits_{h\in\llbracket
H\rrbracket}\sum\limits_{(s,a)\in\mathcal{S}\times\mathcal{A}:\rho_{h}^{p,\pi^{\prime}}(s,a)>0}\rho_{h}^{p,\pi^{\prime}}(s,a)\underbrace{A_{h}^{\pi^{*}}(s,a;p,r)}_{=0}$
$\displaystyle=0,$

where we have simply used the hypothesis.

By setting $\pi^{E}\equiv\pi^{\prime}$, we get the result. ∎

Now, we are ready to prove Theorem 3.1: See 3.1

###### Proof.

Thanks to Lemma E.1, to prove the statement of the theorem we have to show the
equivalence of the constraints:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\quad Q^{*}_{h}(s,\pi^{E}_{h}(s);p,r)\geq Q^{*}_{h}(s,a;p,r)$
(14) $\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\iff$
$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A},\forall\overline{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}:\quad
Q^{\overline{\pi}}_{h}(s,\pi^{E}_{h}(s);p,r)\geq
Q^{\overline{\pi}}_{h}(s,a;p,r),$ (15)

where we have exchanged the order of the quantifiers (because they all are of
the same type). Observe that Eq. 14 can be rewritten as:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\quad Q^{\pi^{*}}_{h}(s,\pi^{E}_{h}(s);p,r)\geq
Q^{\pi^{*}}_{h}(s,a;p,r),$

because of the existence of some optimal policy $\pi^{*}$ (see Puterman,
1994). Now, by induction over $h\in\llbracket H\rrbracket$, it is easy to show
that Eq. 14 entails the existence of an optimal policy
$\pi^{*}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}$. Therefore, we can
rewrite the constraint as:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\quad
Q^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h}(s,\pi^{E}_{h}(s);p,r)\geq
Q^{\pi^{*}}_{h}(s,a;p,r),$

since playing $\pi^{*}$ from $\mathcal{S}^{p,\pi^{E}}$ brings again into
$\mathcal{S}^{p,\pi^{E}}$. By definition of $\pi^{*}$, we have:

$\displaystyle Q^{\pi^{*}}_{h}(s,a;p,r)$
$\displaystyle=Q^{*}_{h}(s,a;p,r)\coloneqq\max\limits_{\pi\in\Pi}Q^{\pi}_{h}(s,a;p,r)\geq
Q^{\overline{\pi}}_{h}(s,a;p,r),$

for all $\overline{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}$. Since
$\pi^{*}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}$, then we have shown
that the two conditions in Eq. 14 and Eq. 15 are equivalent. ∎

As a direct consequence of Theorem 3.1, we have the following corollary. See
D.1

###### Proof.

Let $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times\llbracket H\rrbracket$ and
let $p$ be a transition model in $\mathcal{P}$. Define:

$\displaystyle\mathfrak{R}_{a}\coloneqq\\{r\in\mathfrak{R}\,|\,Q_{h}^{*}(s,a;p,r)=\max\limits_{a^{\prime}\in\mathcal{A}}Q^{*}_{h}(s,a^{\prime};p,r)\\},$

i.e., the set of rewards satisfying the constraint on the optimality of action
$a$ in a single $(s,h)$ pair. It is well known (see Puterman, 1994) that,
given a reward function and a transition model, there always exists an optimal
policy whose Q-function coincides, by definition, with the optimal Q-function.
In other words, for any $p\in\mathcal{P}$ and any $r\in\mathfrak{R}$, the
optimal Q-function is “well-defined”. Therefore, it holds that:

$\displaystyle\bigcup\limits_{a\in\mathcal{A}}\mathfrak{R}_{a}=\mathfrak{R},$

because we are making the union of the rewards that induce action $a$ to be
optimal in $(s,h)$ for any $a\in\mathcal{A}$. To put it simple, if we add the
constraint that at pair $(s,h)\in\mathcal{S}\times\llbracket H\rrbracket$
there _exists_ an optimal action, we are not actually adding a constraint.
Notice that we can do the same with policies $\pi\in\Pi$ instead of actions
$a\in\mathcal{A}$. Thanks to Lemma E.1 and the property just highlighted, we
can write:

$\displaystyle\mathcal{R}_{p,\pi^{E}}$
$\displaystyle=\\{r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}}:\,Q_{h}^{*}(s,\pi_{h}^{E}(s);p,r)=\max\limits_{a\in\mathcal{A}}Q^{*}_{h}(s,a;p,r)\\}$
$\displaystyle=\\{r\in\mathfrak{R}\,|\,\exists\pi^{\prime}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}:\,\forall(s,h)\in\mathcal{S}\times\llbracket
H\rrbracket:\,Q_{h}^{*}(s,\pi_{h}^{\prime}(s);p,r)=\max\limits_{a\in\mathcal{A}}Q^{*}_{h}(s,a;p,r)\\}$
$\displaystyle=\bigcup\limits_{\pi^{\prime}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}}\overline{\mathcal{R}}_{p,\pi^{\prime}}.$

In this way, the constraints are defined only for
$(s,h)\in\mathcal{S}^{p,\pi^{E}}$. ∎

With regards to Section 4, we provide the following proposition.

######  Proposition E.2.

For any $r,r^{\prime}\in\mathfrak{R}$, it holds that:

$\displaystyle d(r,r^{\prime})\leq
2d_{\infty}(r,r^{\prime})\leq\frac{2}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\text{min}}}d(r,r^{\prime}).$

###### Proof.

The first inequality is straightforward. For the second, observe that:

$\displaystyle d_{\infty}(r,\widehat{r})$
$\displaystyle\coloneqq\frac{1}{M}\sum\limits_{h\in[H]}\max\limits_{(s,a)\in\mathcal{S}\times\mathcal{A}}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|$
$\displaystyle=\frac{1}{M}\sum\limits_{h\in[H]}\max\bigl{\\{}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|,\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|\bigr{\\}}$
$\displaystyle=\frac{1}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}\frac{1}{M}\sum\limits_{h\in[H]}\max\bigl{\\{}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|,\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|\bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\leq}\frac{1}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}\frac{1}{M}\sum\limits_{h\in[H]}\max\bigl{\\{}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\rho_{h}^{p,\pi^{b}}(s,a)|r_{h}(s,a)-\widehat{r}_{h}(s,a)|,\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|\bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\frac{1}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}\frac{1}{M}\sum\limits_{h\in[H]}\max\bigl{\\{}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\rho_{h}^{p,\pi^{b}}(s,a)|r_{h}(s,a)-\widehat{r}_{h}(s,a)|,\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|\bigr{\\}}$
$\displaystyle=\frac{1}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}\frac{1}{M}\sum\limits_{h\in[H]}\max\bigl{\\{}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|,\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|\bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}\frac{1}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}\frac{1}{M}\sum\limits_{h\in[H]}\biggl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|+\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}|r_{h}(s,a)-\widehat{r}_{h}(s,a)|\biggr{)}$
$\displaystyle=:\frac{1}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}d(r,\widehat{r}),$

where at (1) we have upper bounded
$\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}\leq\rho_{h}^{p,\pi^{b}}(s,a)$
for $(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}$, and
$\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}\leq 1$, and at (2) and (3) we
have used that $\max\\{a,b\\}\leq a+b$ for $a,b\geq 0$. ∎

##  Appendix F Sample Complexity Analysis

In this section, we present our results on the sample complexity of IRLO
(Algorithm 1 \- IRLO box) and PIRLO (Algorithm 1 \- PIRLO box) with both
distances $d$ and $d_{\infty}$.

The section is organized into various subsections. We begin with Section F.1,
in which we present the concentration results that will be used in all the
sample complexity proofs. Section F.2 contains the proofs of sample complexity
of IRLO w.r.t. distances $d$ and $d_{\infty}$. Analogously, Section F.3
contains the proofs of sample complexity of PIRLO w.r.t. distances $d$ and
$d_{\infty}$. In Section F.4, we present additional sample complexity results
for PIRLO w.r.t. $d,d_{\infty}$ under additional requirements. We conclude
with Section F.5, in which we present a result of sample complexity on the
estimation problem of the superset only, as defined in Equation (8).

###  F.1 Concentration Lemmas

We define good event $\mathcal{E}$ as the intersection of four events
$\mathcal{E}_{1},\mathcal{E}_{2},\mathcal{E}_{3},\mathcal{E}_{4}$. Events
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ allow to obtain exact estimates of
$\mathcal{Z}^{p,\pi^{b}}$ and $\mathcal{S}^{p,\pi^{E}}$ w.h.p., while events
$\mathcal{E}_{3}$ and $\mathcal{E}_{4}$ allow to concentrate the estimates of
the transition models around their means.

######  Lemma F.1 (Coverage Events).

Let $\mathcal{M}$ be an MDP without reward and let $\pi^{E}$ be the expert’s
policy. Let $\mathcal{D}^{b}=\\{\langle
s_{h}^{b,i},a_{h}^{b,i}\rangle_{h\in\llbracket
H\rrbracket}\\}_{i\in\llbracket\tau^{b}\rrbracket}$ and
$\mathcal{D}^{E}=\\{\langle s_{h}^{E,j},a_{h}^{E,j}\rangle_{h\in\llbracket
H\rrbracket}\\}_{j\in\llbracket\tau\rrbracket^{E}}$ be datasets of $\tau^{b}$
and $\tau^{E}$ trajectories collected by executing policies $\pi^{b}$ and
$\pi^{E}$ in $\mathcal{M}$. Denote with $N_{h}^{b}(s,a)$ the visitation count
of triple $(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$ computed using
$\mathcal{D}^{b}$, and by $N_{h}^{E}(s,a)$ the analogous for
$\mathcal{D}^{E}$. For any $\delta\in(0,1)$, define events
$\mathcal{E}_{1},\mathcal{E}_{2}$ as:

$\displaystyle\mathcal{E}_{1}$
$\displaystyle\coloneqq\Biggl{\\{}N_{h}^{b}(s,a)\geq
1,\;\forall(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\quad\text{when }\tau^{b}\geq
c_{1}\frac{\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\ln\frac{1}{1-\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}}\Biggr{\\}},$
$\displaystyle\mathcal{E}_{2}$
$\displaystyle\coloneqq\Biggl{\\{}N^{E}_{h}(s,a)\geq
1,\;\forall(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}\quad\text{when }\tau^{E}\geq
c_{2}\frac{\ln\frac{|\mathcal{S}^{p,\pi^{E}}|}{\delta}}{\ln\frac{1}{1-\rho^{\pi^{E},\mathcal{Z}^{p,\pi^{E}}}_{\min}}}\Biggr{\\}},$

where $c_{1}$ and $c_{2}$ are universal constants. Then, event
$\mathcal{E}_{1}\cap\mathcal{E}_{2}$ holds with probability at least
$1-\delta/2$.

###### Proof.

Let us begin with event $\mathcal{E}_{1}$. We observe that
$N_{h}^{b}(s,a)\sim\text{Bin}(\tau^{b},\rho_{h}^{p,\pi^{b}}(s,a))$. In an
analogous manner as Lemma E.5 of Metelli et al. (2023), we can write:

$\displaystyle\mathop{\mathbb{P}}\limits_{p,\pi^{b}}(\mathcal{E}_{1}^{\complement})$
$\displaystyle=\mathop{\mathbb{P}}\limits_{p,\pi^{b}}(\exists(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}:\;N_{h}^{b}(s,a)=0)$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\leq}\sum\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}\mathop{\mathbb{P}}\limits_{p,\pi^{b}}(N_{h}^{b}(s,a)=0)$
$\displaystyle=\sum\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}(1-\rho_{h}^{p,\pi^{b}}(s,a))^{\tau^{b}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\sum\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}(1-\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min})^{\tau^{b}}$
$\displaystyle=|\mathcal{Z}^{p,\pi^{b}}|(1-\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min})^{\tau^{b}}\leq\frac{\delta}{4},$

where at (1) we used a union bound, and at (2) the definition of
$\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}\coloneqq\min_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}\rho_{h}^{p,\pi^{b}}(s,a)$.
Solving w.r.t. $\tau^{b}$ we get:

$\displaystyle\tau^{b}\geq\frac{\ln\frac{4|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\ln\frac{1}{1-\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}},$

from which the bound for event $\mathcal{E}_{1}$ holds for some uninteresting
constant $c_{1}$.

Observe that, by following a similar reasoning, we can prove the bound for
event $\mathcal{E}_{2}$, by recalling that, by hypothesis, the expert’s policy
is deterministic, so $|\mathcal{Z}^{p,\pi^{E}}|=|\mathcal{S}^{p,\pi^{E}}|$.
The statement of the theorem follows by an application of the union bound. ∎

Before presenting the next lemma, we introduce the symbols:

$\displaystyle{b}_{h}(s,a)\coloneqq\sqrt{\frac{2{\beta}(N_{h}^{b}(s,a),\delta)}{\max\\{N^{b}_{h}(s,a),1\\}}},$
(16)

and

$\displaystyle{\beta}(n,\delta)\coloneqq\ln(4{Z}^{p,\pi^{b}}/{\delta})+({S}^{p,\pi^{b}}_{\max}-1)\ln(e(1+n/{({S}^{p,\pi^{b}}_{\max}-1)})),$
(17)

with ${Z}^{p,\pi^{b}}\coloneqq|{\mathcal{Z}}^{p,\pi^{b}}|$ and
${S}^{p,\pi^{b}}_{\max}\coloneqq\max_{h\in\llbracket
H\rrbracket}|{\mathcal{S}}_{h}^{p,\pi^{b}}|$. The corresponding counterparts
with the estimated quantities are given as follows:

$\displaystyle\widehat{b}_{h}(s,a)\coloneqq\sqrt{\frac{2\widehat{\beta}(N_{h}^{b}(s,a),\delta)}{\max\\{N^{b}_{h}(s,a),1\\}}},$
(18)

and

$\displaystyle\widehat{\beta}(n,\delta)\coloneqq\ln(4\widehat{Z}^{p,\pi^{b}}/{\delta})+(\widehat{S}^{p,\pi^{b}}_{\max}-1)\ln(e(1+n/{(\widehat{S}^{p,\pi^{b}}_{\max}-1)})),$
(19)

with $\widehat{Z}^{p,\pi^{b}}\coloneqq|\widehat{\mathcal{Z}}^{p,\pi^{b}}|$ and
$\widehat{S}^{p,\pi^{b}}_{\max}\coloneqq\max_{h\in\llbracket
H\rrbracket}|\widehat{\mathcal{S}}_{h}^{p,\pi^{b}}|$. Clearly, under the good
event $\mathcal{E}_{1}\cap\mathcal{E}_{2}$, the two versions coincide.

######  Lemma F.2 (Concentration).

Let $\mathcal{M}$ be an MDP without reward and let $\pi^{E}$ be the expert’s
policy. Let $\mathcal{D}^{b}=\\{\langle
s_{h}^{b,i},a_{h}^{b,i}\rangle_{h\in\llbracket
H\rrbracket}\\}_{i\in\llbracket\tau^{b}\rrbracket}$ and
$\mathcal{D}^{E}=\\{\langle s_{h}^{E,j},a_{h}^{E,j}\rangle_{h\in\llbracket
H\rrbracket}\\}_{j\in\llbracket\tau\rrbracket^{E}}$ be datasets of $\tau^{b}$
and $\tau^{E}$ trajectories collected by executing policies $\pi^{b}$ and
$\pi^{E}$ in $\mathcal{M}$. Denote with $\widehat{p}_{h}(\cdot|s,a)$ the
empirical transition model of triple $(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$
computed using $\mathcal{D}^{b}$. For any $\delta\in(0,1)$, define events
$\mathcal{E}_{3},\mathcal{E}_{4}$ as:

$\displaystyle\mathcal{E}_{3}$
$\displaystyle\coloneqq\Biggl{\\{}N_{h}^{b}(s,a)KL(\widehat{p}_{h}(\cdot|s,a)\|p_{h}(\cdot|s,a))\leq\beta(N_{h}^{b}(s,a),\delta),\quad\forall\tau^{b}\in\mathbb{N},\,\forall(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\Biggr{\\}},$
$\displaystyle\mathcal{E}_{4}$
$\displaystyle\coloneqq\Biggl{\\{}\frac{1}{N_{h}^{b}(s,a)\vee 1}\leq
c_{4}\frac{\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau^{b}\rho_{h}^{p,\pi^{b}}(s,a)},\quad\forall(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\Biggr{\\}},$

where $c_{4}$ is a universal constant. Then, event
$\mathcal{E}_{3}\cap\mathcal{E}_{4}$ holds with probability at least
$1-\delta/2$.

###### Proof.

We show that both events $\mathcal{E}_{3},\mathcal{E}_{4}$ hold with
probability at least $1-\frac{\delta}{4}$. The thesis follows through the
application of a union bound.

Let us begin with event $\mathcal{E}_{3}$. Similarly to the proof of Lemma 10
in Kaufmann et al. (2021), we apply Lemma J.2 and a union bound to get:

$\displaystyle\mathop{\mathbb{P}}\limits_{p,\pi^{b}}(\mathcal{E}_{3}^{\complement})$
$\displaystyle=\mathop{\mathbb{P}}\limits_{p,\pi^{b}}\biggl{(}\exists(s,a,h)\in\mathcal{Z}^{p,\pi^{b}},\,\exists\tau^{b}\in\mathbb{N}:\;N_{h}^{b}(s,a)KL(\widehat{p}_{h}(\cdot|s,a)\|p_{h}(\cdot|s,a))>\beta(N_{h}^{b}(s,a),\delta)\biggr{)}$
$\displaystyle\leq\sum\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}\mathop{\mathbb{P}}\limits_{p,\pi^{b}}\biggl{(}\exists\tau^{b}\in\mathbb{N}:\;N_{h}^{b}(s,a)KL(\widehat{p}_{h}(\cdot|s,a)\|p_{h}(\cdot|s,a))>\beta(N_{h}^{b}(s,a),\delta)\biggr{)}$
$\displaystyle\leq\sum\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}\frac{\delta}{4|\mathcal{Z}^{p,\pi^{b}}|}=\frac{\delta}{4}.$

It should be remarked that, in the definition of $\beta$ (Equation 17), we
have used $|\mathcal{S}^{p,\pi^{b}}_{\max}|$ instead of $\mathcal{S}$ because
it better represents the support of the transition model in triples
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$.

As far as event $\mathcal{E}_{4}$ is concerned, consider an arbitrary triple
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$. Observe that the visitation count
$N_{h}^{b}(s,a)$ is binomially distributed, i.e.,
$N_{h}^{b}(s,a)\sim\text{Bin}(\tau,\rho_{h}^{p,\pi^{b}}(s,a))$. Therefore,
similarly to Lemma B.1 of (Xie et al., 2021), by applying Lemma J.1 with
confidence $\delta/(4|\mathcal{Z}^{p,\pi^{b}}|)$, we can concentrate the
binomial as:

$\frac{\rho_{h}^{p,\pi^{b}}(s,a)}{N_{h}^{b}(s,a)\vee
1}\leq\frac{8\ln\frac{4|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau},$

from which we get:

$\mathop{\mathbb{P}}\limits_{p,\pi^{b}}\Bigl{(}\frac{1}{N_{h}^{b}(s,a)\vee
1}\leq\frac{8\ln\frac{4|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau\rho_{h}^{p,\pi^{b}}(s,a)}\Bigr{)}\geq
1-\frac{\delta}{4|\mathcal{Z}^{p,\pi^{b}}|}.$

We can perform a union bound over $(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$ to get:

$\mathop{\mathbb{P}}\limits_{p,\pi^{b}}\Bigl{(}\exists(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}:\;\frac{1}{N_{h}^{b}(s,a)\vee
1}>\frac{8\ln\frac{4|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau\rho_{h}^{p,\pi^{b}}(s,a)}\Bigr{)}\leq\frac{\delta}{4}.$

By choosing $c_{4}$ appropriately, we get the result. ∎

Since
$\mathcal{E}\coloneqq\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3}\cap\mathcal{E}_{4}$,
then, by combining Lemma F.1 with Lemma F.2 through a union bound, we get that
$\mathcal{E}$ holds w.p. $1-\delta$.

###  F.2 Proof of Theorem 5.1 and Theorem 5.2

The next lemmas show that, for any reward in $\mathcal{R}_{p,\pi^{E}}^{\cap}$
($\mathcal{R}_{p,\pi^{E}}^{\cup}$), it is possible to find a “similar” reward
in the estimate $\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cap}$
($\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cup}$). Notice that, under events
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ we have that, respectively,
$\widehat{\mathcal{Z}}^{p,\pi^{b}}=\mathcal{Z}^{p,\pi^{b}}$ and
$\widehat{\mathcal{S}}^{p,\pi^{E}}=\mathcal{S}^{p,\pi^{E}}$. For the sake of
simplicity, we provide here the (recursive) definitions of
$p^{m},p^{M}\in[p]_{\equiv_{\mathcal{Z}^{p,\pi^{b}}}}$ for any
$r\in\mathfrak{R}$:

$\displaystyle\begin{split}p^{M}&\coloneqq\begin{cases}p^{M}_{h}(\cdot|s,a)=p_{h}(\cdot|s,a),\qquad\forall(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\\\
p^{M}_{h}(\cdot|s,a)=\mathbbm{1}\\{\cdot=\operatorname*{arg\,max}\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r\\},\qquad\text{otherwise}\end{cases},\\\
p^{m}&\coloneqq\begin{cases}p^{m}_{h}(\cdot|s,a)=p_{h}(\cdot|s,a),\qquad\forall(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\\\
p^{m}_{h}(\cdot|s,a)=\mathbbm{1}\\{\cdot=\operatorname*{arg\,min}\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r\\},\qquad\text{otherwise}\end{cases},\end{split}$
(20)

where we have used the following (recursive) policy definitions
$\pi^{M},\widetilde{\pi}^{m}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}$:

$\displaystyle\begin{split}\pi^{M}&\coloneqq\begin{cases}\pi^{M}_{h}(s)=\pi^{E}_{h}(s),\;\text{if
}(s,h)\in\mathcal{S}^{p,\pi^{E}}\\\
\pi^{M}_{h}(\cdot|s)=\mathbbm{1}\\{\cdot=\operatorname*{arg\,max}\limits_{a\in\mathcal{A}}Q^{\pi^{M}}_{h}(s,a;p^{M},r)\\},\;\text{if
}(s,h)\notin\mathcal{S}^{p,\pi^{E}}\\\ \end{cases},\\\
\pi^{m}&\coloneqq\begin{cases}\pi^{m}_{h}(s)=\pi^{E}_{h}(s),\;\text{if
}(s,h)\in\mathcal{S}^{p,\pi^{E}}\\\
\pi^{m}_{h}(\cdot|s)=\mathbbm{1}\\{\cdot={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\operatorname*{arg\,max}\limits_{a\in\mathcal{A}}}Q^{\pi^{m}}_{h}(s,a;p^{m},r)\\},\;\text{if
}(s,h)\notin\mathcal{S}^{p,\pi^{E}}\\\ \end{cases}.\end{split}$ (21)

Thanks to these definitions, we can rewrite $\mathcal{R}_{p,\pi^{E}}^{\cap}$
and $\mathcal{R}_{p,\pi^{E}}^{\cup}$ as:

$\displaystyle\begin{split}\mathcal{R}_{p,\pi^{E}}^{\cap}&=\\{r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};p,r)\geq
Q^{\pi^{M}}_{h}(s,a;p^{M},r)\\},\\\
\mathcal{R}_{p,\pi^{E}}^{\cup}&=\\{r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};p,r)\geq
Q^{\pi^{m}}_{h}(s,a;p^{m},r)\\}.\end{split}$ (22)

We will denote by
$\widehat{p}^{M},\widehat{p}^{m},\widehat{\pi}^{M},\widehat{\pi}^{m}$ the
transition models and policies defined as in Eq. 20 and Eq. 21 but for
transition model $\widehat{p}$.

######  Lemma F.3 (Reward Choice Subset).

Let $\mathcal{R}_{p,\pi^{E}}^{\cap}$ be the subset of the feasible set
$\mathcal{R}_{p,\pi^{E}}$ estimated through
$\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cap}$ outputted by Algorithm 1. Under
event $\mathcal{E}$, for any $r\in\mathcal{R}_{p,\pi^{E}}^{\cap}$, the reward
$\widehat{r}$ constructed as:

$\displaystyle\begin{cases}\widehat{r}_{h}(s,a)=r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widehat{p}_{h}(s^{\prime}|s,a)V^{\widehat{\pi}^{M}}_{h+1}(s^{\prime};\widehat{p}^{M},\widehat{r}),\quad\forall(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\\\
\widehat{r}_{h}(s,a)=r_{h}(s,a),\quad\forall(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}\\\
\end{cases},$

belongs to $\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cap}$. Moreover, for any
reward $\widehat{r}\in\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cap}$, we can
construct in the same manner a reward $r$ that belongs to
$\mathcal{R}_{p,\pi^{E}}^{\cap}$.

###### Proof.

The idea of the proof is to show that
$Q^{\pi^{M}}_{h}(s,a;p^{M},r)=Q^{\widehat{\pi}^{M}}_{h}(s,a;\widehat{p}^{M},\widehat{r})$
for all $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times\llbracket H\rrbracket$.
Indeed, in this way, since $r\in\mathcal{R}_{p,\pi^{E}}^{\cap}$, then it holds
that:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};\widehat{p},\widehat{r})-Q^{\widehat{\pi}^{M}}_{h}(s,a;\widehat{p}^{M},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)-Q^{\pi^{M}}_{h}(s,a;p^{M},r)\geq
0.$

Let us begin with any $(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$. By definition of
$\widehat{r}$ and by rearranging the terms, we obtain:

$\displaystyle\widehat{r}_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widehat{p}_{h}(s^{\prime}|s,a)V^{\widehat{\pi}^{M}}_{h+1}(s^{\prime};\widehat{p}^{M},\widehat{r})=r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)$
$\displaystyle\iff
Q^{\widehat{\pi}^{M}}_{h}(s,a;\widehat{p}^{M},\widehat{r})=Q^{\pi^{M}}_{h}(s,a;p^{M},r).$
(23)

In particular, observe that, by Assumption 2.1, it holds
$\mathcal{Z}^{p,\pi^{E}}\subseteq\mathcal{Z}^{p,\pi^{b}}$; moreover, by
definition of $\widehat{p}^{M}$ and $p^{M}$, playing an expert’s action from
$\mathcal{S}^{p,\pi^{E}}$ brings again into $\mathcal{S}^{p,\pi^{E}}$,
therefore, for $(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}$, this means:

$\displaystyle
Q^{\pi^{E}}_{h}(s,a^{E};\widehat{p},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r).$

Now, we show by induction that, for any
$(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$, it holds that:

$\displaystyle
Q^{\widehat{\pi}^{M}}_{h}(s,a;\widehat{p}^{M},\widehat{r})=Q^{\pi^{M}}_{h}(s,a;p^{M},r).$

As case base, consider stage $H$. Clearly, for any
$(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{H}$, we have:

$\displaystyle Q^{\widehat{\pi}^{M}}_{H}(s,a;\widehat{p}^{M},\widehat{r})$
$\displaystyle=\widehat{r}_{H}(s,a)$ $\displaystyle=r_{H}(s,a)$
$\displaystyle=Q^{\pi^{M}}_{h}(s,a;p^{M},r),$

where we have used the definition of $\widehat{r}$. Make the inductive
hypothesis that, at stage $h+1$, for any
$(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h+1}$, it holds that
$Q^{\widehat{\pi}^{M}}_{h+1}(s,a;\widehat{p}^{M},\widehat{r})=Q^{\pi^{M}}_{h+1}(s,a;p^{M},r)$,
and consider stage $h$:

$\displaystyle Q^{\widehat{\pi}^{M}}_{h}(s,a;\widehat{p}^{M},\widehat{r})$
$\displaystyle=\widehat{r}_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widehat{p}^{M}_{h}(s^{\prime}|s,a)V_{h+1}^{\widehat{\pi}^{M}}(s^{\prime};\widehat{p}^{M},\widehat{r})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r_{h}(s,a)}+\sum\limits_{s^{\prime}\in\mathcal{S}}\widehat{p}^{M}_{h}(s^{\prime}|s,a)V_{h+1}^{\widehat{\pi}^{M}}(s^{\prime};\widehat{p}^{M},\widehat{r})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{=}r_{h}(s,a)+\max\limits_{s^{\prime}\in\mathcal{S}}V_{h+1}^{\widehat{\pi}^{M}}(s^{\prime};\widehat{p}^{M},\widehat{r})$
$\displaystyle=r_{h}(s,a)+\max\bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{\widehat{\pi}^{M}}(s^{\prime};\widehat{p}^{M},\widehat{r}),\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{\widehat{\pi}^{M}}(s^{\prime};\widehat{p}^{M},\widehat{r})\bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{=}r_{h}(s,a)+\max\bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{M}}}(s^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{M},r}),\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{\widehat{\pi}^{M}}(s^{\prime};\widehat{p}^{M},\widehat{r})\bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{=}r_{h}(s,a)+\max\bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{\pi^{M}}(s^{\prime};p^{M},r),\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{M}}}(s^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{M},r})\bigr{\\}}$
$\displaystyle=r_{h}(s,a)+\max\limits_{s^{\prime}\in\mathcal{S}}V_{h+1}^{\pi^{M}}(s^{\prime};p^{M},r)$
$\displaystyle=Q_{h}^{\pi^{M}}(s,a;p^{M},r),$

where at (1) we use the definition of $\hat{r}$ outside
$\mathcal{Z}^{p,\pi^{b}}$, at (2) we use the definition of $\widehat{p}^{M}$,
at (3) we use Eq. F.2, and at (4) we use the inductive hypothesis.

Notice that the same passages can be carried out if we exchanged $p$ and
$\widehat{p}$. This concludes the proof. ∎

Notice that the reward function chosen in Lemma F.3 can be interpreted, in an
analogous manner as in the proof of Theorem 3.1 of Metelli et al. (2021), as
the reward that provides, in transition model $\widehat{p}$, the same
Q-function provided by the given reward in $p$.

We can prove an analogous result for the superset
$\mathcal{R}_{\widehat{p},\widehat{\pi}^{E}}^{\cup}$.

######  Lemma F.4 (Reward Choice Superset).

Let $\mathcal{R}_{p,\pi^{E}}^{\cup}$ be the subset of the feasible set
$\mathcal{R}_{p,\pi^{E}}$ estimated through
$\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cup}$ outputted by Algorithm 1. Under
event $\mathcal{E}$, for any $r\in\mathcal{R}_{p,\pi^{E}}^{\cup}$, the reward
$\widehat{r}$ constructed as:

$\displaystyle\begin{cases}\widehat{r}_{h}(s,a)=r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widehat{p}_{h}(s^{\prime}|s,a)V^{\widehat{\pi}^{m}}_{h+1}(s^{\prime};\widehat{p}^{m},\widehat{r}),\quad\forall(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\\\
\widehat{r}_{h}(s,a)=r_{h}(s,a),\quad\forall(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}\\\
\end{cases},$

belongs to $\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cup}$. Moreover, for any
reward $\widehat{r}\in\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cup}$, we can
construct in the same manner a reward $r$ that belongs to
$\mathcal{R}_{p,\pi^{E}}^{\cup}$.

###### Proof.

The idea of the proof is analogous to that of Lemma F.3, and is reported here
for completeness. We aim to show that
$Q^{\pi^{m}}_{h}(s,a;p^{m},r)=Q^{\widehat{\pi}^{m}}_{h}(s,a;\widehat{p}^{m},\widehat{r})$
for all $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times\llbracket H\rrbracket$.
Indeed, in this way, since $r\in\mathcal{R}_{p,\pi^{E}}^{\cup}$, then it holds
that:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};\widehat{p},\widehat{r})-Q^{\widehat{\pi}^{m}}_{h}(s,a;\widehat{p}^{m},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)-Q^{\pi^{m}}_{h}(s,a;p^{m},r)\geq
0.$

Let us begin with any $(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$. By definition of
$\widehat{r}$ and by rearranging the terms, we obtain:

$\displaystyle\widehat{r}_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widehat{p}_{h}(s^{\prime}|s,a)V^{\widehat{\pi}^{m}}_{h+1}(s^{\prime};\widehat{p}^{m},\widehat{r})=r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)$
$\displaystyle\iff
Q^{\widehat{\pi}^{m}}_{h}(s,a;\widehat{p}^{m},\widehat{r})=Q^{\pi^{m}}_{h}(s,a;p^{m},r).$
(24)

In particular, observe that, by Assumption 2.1, it holds
$\mathcal{Z}^{p,\pi^{E}}\subseteq\mathcal{Z}^{p,\pi^{b}}$; moreover, by
definition of $\widehat{p}^{m}$ and $p^{m}$, playing an expert’s action from
$\mathcal{S}^{p,\pi^{E}}$ brings again into $\mathcal{S}^{p,\pi^{E}}$,
therefore, for $(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}$, this means:

$\displaystyle
Q^{\pi^{E}}_{h}(s,a^{E};\widehat{p},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r).$

Now, we show by induction that, for any
$(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$, it holds that:

$\displaystyle
Q^{\widehat{\pi}^{m}}_{h}(s,a;\widehat{p}^{m},\widehat{r})=Q^{\pi^{m}}_{h}(s,a;p^{m},r).$

As case base, consider stage $H$. Clearly, for any
$(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{H}$, we have:

$\displaystyle Q^{\widehat{\pi}^{m}}_{H}(s,a;\widehat{p}^{m},\widehat{r})$
$\displaystyle=\widehat{r}_{H}(s,a)$ $\displaystyle=r_{H}(s,a)$
$\displaystyle=Q^{\pi^{m}}_{h}(s,a;p^{m},r),$

where we have used the definition of $\widehat{r}$. Make the inductive
hypothesis that, at stage $h+1$, for any
$(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h+1}$, it holds that
$Q^{\widehat{\pi}^{m}}_{h+1}(s,a;\widehat{p}^{m},\widehat{r})=Q^{\pi^{m}}_{h+1}(s,a;p^{m},r)$,
and consider stage $h$:

$\displaystyle Q^{\widehat{\pi}^{m}}_{h}(s,a;\widehat{p}^{m},\widehat{r})$
$\displaystyle=\widehat{r}_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widehat{p}^{m}_{h}(s^{\prime}|s,a)V_{h+1}^{\widehat{\pi}^{m}}(s^{\prime};\widehat{p}^{m},\widehat{r})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r_{h}(s,a)}+\sum\limits_{s^{\prime}\in\mathcal{S}}\widehat{p}^{m}_{h}(s^{\prime}|s,a)V_{h+1}^{\widehat{\pi}^{m}}(s^{\prime};\widehat{p}^{m},\widehat{r})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{=}r_{h}(s,a)+\min\limits_{s^{\prime}\in\mathcal{S}}V_{h+1}^{\widehat{\pi}^{m}}(s^{\prime};\widehat{p}^{m},\widehat{r})$
$\displaystyle=r_{h}(s,a)+\min\bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{\widehat{\pi}^{m}}(s^{\prime};\widehat{p}^{m},\widehat{r}),\min\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{\widehat{\pi}^{m}}(s^{\prime};\widehat{p}^{m},\widehat{r})\bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{=}r_{h}(s,a)+\min\bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{m}}}(s^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{m},r}),\min\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{\widehat{\pi}^{m}}(s^{\prime};\widehat{p}^{m},\widehat{r})\bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{=}r_{h}(s,a)+\min\bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{\pi^{m}}(s^{\prime};p^{m},r),\min\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{b}}_{h+1}}V_{h+1}^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{m}}}(s^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{m},r})\bigr{\\}}$
$\displaystyle=r_{h}(s,a)+\max\limits_{s^{\prime}\in\mathcal{S}}V_{h+1}^{\pi^{m}}(s^{\prime};p^{m},r)$
$\displaystyle=Q_{h}^{\pi^{m}}(s,a;p^{m},r),$

where at (1) we use the definition of $\hat{r}$ outside
$\mathcal{Z}^{p,\pi^{b}}$, at (2) we use the definition of $\widehat{p}^{m}$,
at (3) we use Eq. F.2, and at (4) we use the inductive hypothesis.

Notice that the same passages can be carried out if we exchanged $p$ and
$\widehat{p}$. This concludes the proof. ∎

From the proofs of Lemma F.3 and Lemma F.4, we notice that proving the result
for the superset is “easier”, because we simply have to consider a single
transition model; instead, for the subset, we have to consider all the
transition models in the equivalence class. Luckily, we can single out a
“worst” transition model from this class and provide the proof only for it. We
will see in the proofs of the results with pessimism how to cope with the
trickier problem in which there exist many “worst” transition models, and thus
the recursion cannot be applied directly.

Thanks to Lemma F.3 and Lemma F.4, we can upper bound the distance between
sets of rewards by a term that depends on the distance between the transition
models. We do not have error for the policy because, under good event
$\mathcal{E}$, we have that $\widehat{\pi}^{E}=\pi^{E}$ in
$\widehat{\mathcal{S}}^{p,\pi^{E}}=\mathcal{S}^{p,\pi^{E}}$.

######  Lemma F.5 (Performance Decomposition Subset and Superset).

Let
$\widehat{\mathcal{R}}^{\cap}\coloneqq\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cap}$
and
$\widehat{\mathcal{R}}^{\cup}\coloneqq\mathcal{R}_{\hat{p},\hat{\pi}^{E}}^{\cup}$
be the output of IRLO (Algorithm 1). Under the good event $\mathcal{E}$, it
holds that:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widehat{\mathcal{R}}^{\cap})\leq
H\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}b_{h}(s,a),$

and:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cup},\widehat{\mathcal{R}}^{\cup})\leq
H\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}b_{h}(s,a).$

###### Proof.

By Definition 4.2, we can write:

$\displaystyle\mathcal{H}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widehat{\mathcal{R}}^{\cap})$
$\displaystyle\coloneqq\max\\{\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\inf\limits_{\widehat{r}\in\widehat{\mathcal{R}}^{\cap}}d(r,\widehat{r}),\sup\limits_{\widehat{r}\in\widehat{\mathcal{R}}^{\cap}}\inf\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}d(r,\widehat{r})\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\leq}\max\\{\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}d(r,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widetilde{r}^{1}}),\sup\limits_{\widehat{r}\in\widehat{\mathcal{R}}^{\cap}}d({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widetilde{r}^{2}},\widehat{r})\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{=}\max\Biggl{\\{}\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\biggl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\bigl{|}r_{h}(s,a)-\widetilde{r}^{1}_{h}(s,a)\bigr{|}+\underbrace{\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}\bigl{|}r_{h}(s,a)-\widetilde{r}^{1}_{h}(s,a)\bigr{|}}_{=0}\biggr{)},$
$\displaystyle\quad\quad\quad\sup\limits_{\widehat{r}\in\widehat{\mathcal{R}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\biggl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\bigl{|}\widehat{r}_{h}(s,a)-\widetilde{r}^{2}_{h}(s,a)\bigr{|}+\underbrace{\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}\bigl{|}\widehat{r}_{h}(s,a)-\widetilde{r}^{2}_{h}(s,a)\bigr{|}}_{=0}\biggr{)}\Biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{=}\max\biggl{\\{}\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}(p_{h}(s^{\prime}|s,a)-\widehat{p}_{h}(s^{\prime}|s,a))V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)\bigr{|},$
$\displaystyle\quad\quad\quad\sup\limits_{\widehat{r}\in\widehat{\mathcal{R}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}(\widehat{p}_{h}(s^{\prime}|s,a)-p_{h}(s^{\prime}|s,a))V^{\widehat{\pi}^{M}}_{h+1}(s^{\prime};\widehat{p}^{M},\widehat{r})\bigr{|}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}\max\biggl{\\{}\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\sum\limits_{s^{\prime}\in\mathcal{S}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bigl{|}}(p_{h}(s^{\prime}|s,a)-\widehat{p}_{h}(s^{\prime}|s,a))V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bigr{|}},$
$\displaystyle\quad\quad\quad\sup\limits_{\widehat{r}\in\widehat{\mathcal{R}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\sum\limits_{s^{\prime}\in\mathcal{S}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bigl{|}}(\widehat{p}_{h}(s^{\prime}|s,a)-p_{h}(s^{\prime}|s,a))V^{\widehat{\pi}^{M}}_{h+1}(s^{\prime};\widehat{p}^{M},\widehat{r}){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bigr{|}}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{\leq}\max\biggl{\\{}\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\sum\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}(p_{h}(s^{\prime}|s,a)-\widehat{p}_{h}(s^{\prime}|s,a)){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}H}\bigr{|},$
$\displaystyle\quad\quad\quad\sup\limits_{\widehat{r}\in\widehat{\mathcal{R}}^{\cap}}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\sum\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}(\widehat{p}_{h}(s^{\prime}|s,a)-p_{h}(s^{\prime}|s,a)){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}H}\bigr{|}\biggr{\\}}$
$\displaystyle=\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\sum\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}(p_{h}(s^{\prime}|s,a)-\widehat{p}_{h}(s^{\prime}|s,a))H\bigr{|}$
$\displaystyle=\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}H\bigl{\|}p_{h}(\cdot|s,a)-\widehat{p}_{h}(\cdot|s,a)\bigr{\|}_{1}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(6)}}}{\leq}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}H\sqrt{2KL\bigl{(}p_{h}(\cdot|s,a)\|\widehat{p}_{h}(\cdot|s,a)\bigr{)}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(7)}}}{\leq}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}H\sqrt{2\frac{\beta(N_{h}^{b}(s,a),\delta)}{N_{h}^{b}(s,a)}}$
$\displaystyle=H\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}b_{h}(s,a),$

where at (1) we have applied Lemma F.3, denoting by
$\widetilde{r}^{1}\in\widehat{\mathcal{R}}^{\cap}$ and
$\widetilde{r}^{2}\in\mathcal{R}_{p,\pi^{E}}^{\cap}$ the choices of rewards,
and used that $\inf_{x\in\mathcal{X}}f(x)\leq f(\bar{x})$ for any
$\bar{x}\in\mathcal{X}$; at (2) we have used the definition of distance $d$,
at (3) we have inserted the definitions of $\widetilde{r}^{1}$ and
$\widetilde{r}^{2}$ as provided by Lemma F.3, in particular using that
$Q^{\pi^{M}}_{h}(s,a;p^{M},r)=Q^{\widehat{\pi}^{M}}_{h}(s,a;\widehat{p}^{M},\widehat{r})$,
at (4) we have applied triangle inequality, to bring the absolute value inside
the summation, at (5) we upper bound
$V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)\leq H\|r\|_{\infty}$ and
$V^{\widehat{\pi}^{M}}_{h+1}(s^{\prime};\widehat{p}^{M},\widehat{r})\leq
H\|\widehat{r}\|_{\infty}$, and since $M\coloneqq
1/\max\\{\|r\|_{\infty},\|\widehat{r}\|_{\infty}\\}$, we obtain
$H\|r\|_{\infty}/M\leq H$ and $H\|\widehat{r}\|_{\infty}/M\leq H$; at (6) we
have applied Pinsker’s inequality, and at (7) we have applied the bound of
$\mathcal{E}_{3}\supseteq\mathcal{E}$ noticing that $N_{h}^{b}(s,a)\geq 1$
because of event $\mathcal{E}_{1}\supseteq\mathcal{E}$.

A similar procedure can be carried out also for the supersets, using Lemma F.4
instead of Lemma F.3. ∎

Finally, we have all the tools we need to prove Theorem 5.1. See 5.1

###### Proof.

First, observe that, thanks to Lemma F.1 and Lemma F.2, we have that good
event $\mathcal{E}$ holds w.p. $1-\delta$ with a number of trajectories
$\tau^{E}$ and $\tau^{b}$ upper bounded as in events $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$. Now, under good event $\mathcal{E}$, the idea of the proof
is to compute the number of trajectories $\tau^{b}$ needed to have a distance
between sets of rewards smaller than $\epsilon$. Then, we combine it with the
number of trajectories required by event $\mathcal{E}$ through
$\max\\{a,b\\}\leq a+b$ for $a,b\geq 0$.

Let us begin with the subset. Thanks to Lemma F.5, we can write:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widehat{\mathcal{R}}^{\cap})$
$\displaystyle\leq H\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}b_{h}(s,a)$
$\displaystyle=H\sum\limits_{h\in\llbracket
H\rrbracket}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)b_{h}(s,a)$
$\displaystyle=H\sum\limits_{h\in\llbracket
H\rrbracket}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)\sqrt{2\frac{\beta(N^{b}_{h}(s,a),\delta)}{N^{b}_{h}(s,a)}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\leq}\sqrt{2}H\sum\limits_{h\in\llbracket
H\rrbracket}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)\sqrt{\frac{\beta(\tau^{b},\delta)}{N^{b}_{h}(s,a)}}$
$\displaystyle=\sqrt{2\beta(\tau^{b},\delta)}H\sum\limits_{h\in\llbracket
H\rrbracket}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)\sqrt{\frac{1}{N^{b}_{h}(s,a)}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\sqrt{2\beta(\tau^{b},\delta)}H\sum\limits_{h\in\llbracket
H\rrbracket}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)\sqrt{c_{4}\frac{\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau^{b}\rho_{h}^{p,\pi^{b}}(s,a)}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{=}c_{5}\sqrt{\frac{\beta(\tau^{b},\delta)\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau^{b}}}H\sum\limits_{h\in\llbracket
H\rrbracket}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\sqrt{\rho_{h}^{p,\pi^{b}}(s,a)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}c_{5}\sqrt{\frac{\beta(\tau^{b},\delta)\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau^{b}}}H\sum\limits_{h\in\llbracket
H\rrbracket}\sqrt{|\mathcal{Z}^{p,\pi^{b}}_{h}|}\sqrt{\sum_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\rho_{h}^{p,\pi^{b}}(s,a)}$
$\displaystyle=c_{5}\sqrt{\frac{\beta(\tau^{b},\delta)\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau^{b}}}H\sum\limits_{h\in\llbracket
H\rrbracket}\sqrt{|\mathcal{Z}^{p,\pi^{b}}_{h}|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{\leq}c_{5}\sqrt{\frac{\beta(\tau^{b},\delta)\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau^{b}}}H\sqrt{H|\mathcal{Z}^{p,\pi^{b}}|}\leq\epsilon,$

where at (1) we have used that $\tau^{b}\geq N^{b}_{h}(s,a)$ for all
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$, and that function $\beta(\cdot,\delta)$
is monotonically increasing; at (2) we have applied the result in Lemma F.2
for event $\mathcal{E}_{4}$, at (3) we define constant
$c_{5}\coloneqq\sqrt{2c_{4}}$, and at (4) and (5) we have applied the Cauchy-
Schwarz’s inequality.

To compute an upper bound to the number of trajectories required to have
$\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widehat{\mathcal{R}}^{\cap})\leq\epsilon$,
we compute the smallest $\tau^{b}$ that satisfies:

$\displaystyle
c_{5}\sqrt{\frac{\beta(\tau^{b},\delta)\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau^{b}}}H\sqrt{H|\mathcal{Z}^{p,\pi^{b}}|}\leq\epsilon.$

By using the definition of $\beta(\tau^{b},\delta)$ from Eq. 17 and
rearranging the terms, this is equivalent to finding the smallest $\tau^{b}$
such that:

$\displaystyle\tau^{b}\geq
c_{6}\frac{H^{3}|\mathcal{Z}^{p,\pi^{b}}|\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}\bigl{(}\ln\frac{4|\mathcal{Z}^{p,\pi^{b}}|}{\delta}+(|\mathcal{S}^{p,\pi^{b}}_{\max}|-1)\ln\bigl{(}e(1+\tau^{b}/(|\mathcal{S}^{p,\pi^{b}}_{\max}|-1))\bigr{)}\bigr{)}}{\epsilon^{2}},$

where $c_{6}\coloneqq c_{5}^{2}$. If we define:

$\displaystyle a$ $\displaystyle\coloneqq
c_{6}\frac{H^{3}|\mathcal{Z}^{p,\pi^{b}}|\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}\ln\frac{4|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\epsilon^{2}},$
$\displaystyle b$ $\displaystyle\coloneqq
c_{6}\frac{H^{3}|\mathcal{Z}^{p,\pi^{b}}|\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}(|\mathcal{S}^{p,\pi^{b}}_{\max}|-1)}{\epsilon^{2}},$
$\displaystyle c$
$\displaystyle\coloneqq\frac{e}{|\mathcal{S}^{p,\pi^{b}}_{\max}|-1},$
$\displaystyle d$ $\displaystyle\coloneqq e,$

then we can rewrite the previous expression as:

$\displaystyle\tau^{b}\geq a+b\ln(c\tau^{b}+d).$

To solve it, we can notice that $a,b,c,d>0$ and $2bc>e$, thus we can apply
Lemma J.3171717 It should be remarked that the adoption of Lemma 15 of
(Kaufmann et al., 2021) provides the same asymptotical dependence on the
quantities of interest. However, Lemma J.3 is more concise.  to obtain:

$\displaystyle\tau^{b}\geq 2a+3b\ln(2bc)+d/c.$

Replacing $a,b,c,d$ with their values, we get:

$\displaystyle\tau^{b}$ $\displaystyle\geq
2c_{6}\frac{H^{3}|\mathcal{Z}^{p,\pi^{b}}|\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}\ln\frac{4|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\epsilon^{2}}+\bigl{(}|\mathcal{S}^{p,\pi^{b}}_{\max}|-1\bigr{)}$
$\displaystyle\qquad+3c_{6}\frac{H^{3}|\mathcal{Z}^{p,\pi^{b}}|\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}(|\mathcal{S}^{p,\pi^{b}}_{\max}|-1)}{\epsilon^{2}}\ln\biggl{(}2c_{6}e\frac{H^{3}|\mathcal{Z}^{p,\pi^{b}}|\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\epsilon^{2}}\biggr{)}$
$\displaystyle\leq\widetilde{\mathcal{O}}\Biggl{(}\frac{H^{3}|\mathcal{Z}^{p,\pi^{b}}|\ln\frac{1}{\delta}}{\epsilon^{2}}\biggl{(}\ln\frac{1}{\delta}+|\mathcal{S}^{p,\pi^{b}}_{\max}|\biggr{)}\Biggr{)}.$

Now, observe that an upper bound to the number of trajectories needed to have
$\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cup},\widehat{\mathcal{R}}^{\cup})\leq\epsilon$
can be obtained with an identical derivation, and, thus, it is of the same
order. The statement of the theorem follows by the considerations at the
beginning of the proof. ∎

We provide here the proof of Theorem 5.2. The proof is analogous to that of
Theorem 5.1. See 5.2

###### Sketch of proof.

The proof is exactly the same as that of Theorem 5.1. First, observe that it
is possible to prove a lemma analogous to Lemma F.5, so that:

$\displaystyle\mathcal{H}_{\infty}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widehat{\mathcal{R}}^{\cap})$
$\displaystyle\leq H\sum\limits_{h\in\llbracket
H\rrbracket}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}b_{h}(s,a).$

Next, when applying Lemma J.1, we simply notice that, for all $h\in\llbracket
H\rrbracket$:

$\displaystyle\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}\sqrt{\frac{1}{\rho_{h}^{p,\pi^{b}}(s,a)}}\leq\sqrt{\frac{1}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}}.$

We can do the same also for the superset. Following the derivation in the
proof of Theorem 5.1, the result can be obtained. ∎

###  F.3 Proof of Theorem 6.1 and Theorem 6.2

We will denote by $a^{E}\coloneqq\pi^{E}_{h}(s)$ for all
$(s,h)\in\mathcal{S}^{p,\pi^{E}}$, the expert’s action. Given any reward
$r\in\mathfrak{R}$, it is useful to define (recursively) the transition models
$\widetilde{p}^{M}$ and $\widetilde{p}^{m}$ as:

$\displaystyle\begin{split}\widetilde{p}^{M}&\coloneqq\begin{cases}\widetilde{p}^{M}_{h}(\cdot|s,a)=\operatorname*{arg\,max}\limits_{\begin{subarray}{c}p^{\prime}:\|p^{\prime}_{h}(\cdot|s,a)-\widehat{p}_{h}(\cdot|s,a)\|_{1}\leq
b_{h}(s,a)\\\ \wedge\forall
s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}:\,p^{\prime}_{h}(s^{\prime}|s,a)=0\end{subarray}}\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}^{\prime}(\cdot|s,a)}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},r)\\},\;\text{if
}(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\\\
\widetilde{p}^{M}_{h}(\cdot|s,a)=\mathbbm{1}\\{\cdot=\operatorname*{arg\,max}\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},r)\\},\;\text{if
}(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}\\\ \end{cases},\\\
\widetilde{p}^{m}&\coloneqq\begin{cases}\widetilde{p}^{m}_{h}(\cdot|s,a)=\operatorname*{arg\,min}\limits_{\begin{subarray}{c}p^{\prime}:\|p^{\prime}_{h}(\cdot|s,a)-\widehat{p}_{h}(\cdot|s,a)\|_{1}\leq
b_{h}(s,a)\\\ \wedge\forall
s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}:\,p^{\prime}_{h}(s^{\prime}|s,a)=0\end{subarray}}\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}^{\prime}(\cdot|s,a)}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},r)\\},\;\text{if
}(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\\\
\widetilde{p}^{m}_{h}(\cdot|s,a)=\mathbbm{1}\\{\cdot=\operatorname*{arg\,min}\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},r)\\},\;\text{if
}(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}\\\ \end{cases},\end{split}$ (25)

where we have used the following (recursive) policy definitions
$\widetilde{\pi}^{M},\widetilde{\pi}^{m}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}$:

$\displaystyle\begin{split}\widetilde{\pi}^{M}&\coloneqq\begin{cases}\widetilde{\pi}^{M}_{h}(s)=\pi^{E}_{h}(s),\;\text{if
}(s,h)\in\mathcal{S}^{p,\pi^{E}}\\\
\widetilde{\pi}^{M}_{h}(\cdot|s)=\mathbbm{1}\\{\cdot=\operatorname*{arg\,max}\limits_{a\in\mathcal{A}}Q^{\widetilde{\pi}^{M}}_{h}(s,a;\widetilde{p}^{M},r)\\},\;\text{if
}(s,h)\notin\mathcal{S}^{p,\pi^{E}}\\\ \end{cases},\\\
\widetilde{\pi}^{m}&\coloneqq\begin{cases}\widetilde{\pi}^{m}_{h}(s)=\pi^{E}_{h}(s),\;\text{if
}(s,h)\in\mathcal{S}^{p,\pi^{E}}\\\
\widetilde{\pi}^{m}_{h}(\cdot|s)=\mathbbm{1}\\{\cdot={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\operatorname*{arg\,max}\limits_{a\in\mathcal{A}}}Q^{\widetilde{\pi}^{m}}_{h}(s,a;\widetilde{p}^{m},r)\\},\;\text{if
}(s,h)\notin\mathcal{S}^{p,\pi^{E}}\end{cases}.\end{split}$ (26)

Thanks to these definitions, we can rewrite $\widetilde{\mathcal{R}}^{\cap}$
and $\widetilde{\mathcal{R}}^{\cup}$ as:

$\displaystyle\begin{split}\widetilde{\mathcal{R}}^{\cap}&=\\{r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widetilde{p}^{m}},r)\geq
Q^{\widetilde{\pi}^{M}}_{h}(s,a;{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widetilde{p}^{M}},r)\\},\\\
\widetilde{\mathcal{R}}^{\cup}&=\\{r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widetilde{p}^{M}},r)\geq
Q^{\widetilde{\pi}^{m}}_{h}(s,a;{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widetilde{p}^{m}},r)\\}.\end{split}$
(27)

Both Theorem 6.1 and Theorem 6.2 uses $d_{\infty}$ instead of $d$ use the same
reward choice lemmas, but differ for the performance decomposition lemmas.

######  Lemma F.6 (Reward Choice Subset).

For any $r\in\mathcal{R}_{p,\pi^{E}}^{\cap}$, the reward $\widehat{r}$
constructed as:

$\displaystyle\begin{cases}\widehat{r}_{h}(s,a^{E})=r_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r}),\quad\forall(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}\\\
\widehat{r}_{h}(s,a)=r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}p^{M}_{h}(s^{\prime}|s,a)V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r}),\quad\text{otherwise},\end{cases},$

belongs to $\widetilde{\mathcal{R}}^{\cap}$.

###### Proof.

Consider any $(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}$. By definition of
$\widehat{r}$, by rearranging the terms, we have that:

$\displaystyle\widehat{r}_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})=r_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)$
$\displaystyle\iff
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r).$
(28)

Now, consider any other triple $(s,a,h)\notin\mathcal{Z}^{p,\pi^{E}}$.
Similarly, by rearranging the terms, we obtain:

$\displaystyle
Q^{\widetilde{\pi}^{M}}_{h}(s,a;\widetilde{p}^{M},\widehat{r})=Q^{\pi^{M}}_{h}(s,a;p^{M},r).$
(29)

By hypothesis, $r\in\mathcal{R}_{p,\pi^{E}}^{\cap}$, therefore:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};p,r)\geq
Q^{\pi^{M}}_{h}(s,a;p^{M},r),$

from which it follows that:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})\geq
Q^{\widetilde{\pi}^{M}}_{h}(s,a;\widetilde{p}^{M},\widehat{r}).$

∎

For the superset, we have an analogous result.

######  Lemma F.7 (Reward Choice Superset).

For any $\widehat{r}\in\widetilde{\mathcal{R}}^{\cup}$, the reward $r$
constructed as:

$\displaystyle\begin{cases}r_{h}(s,a^{E})=\widehat{r}_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r),\quad\forall(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}\\\
r_{h}(s,a)=\widehat{r}_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-\sum\limits_{s^{\prime}\in\mathcal{S}}p^{m}_{h}(s^{\prime}|s,a)V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r),\quad\text{otherwise},\end{cases},$

belongs to $\mathcal{R}_{p,\pi^{E}}^{\cup}$.

###### Proof.

Consider any $(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}$. By definition of $r$, by
rearranging the terms, we have that:

$\displaystyle\widehat{r}_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})=r_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)$
$\displaystyle\iff
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r).$
(30)

Now, consider any other triple $(s,a,h)\notin\mathcal{Z}^{p,\pi^{E}}$.
Similarly, by rearranging the terms, we obtain:

$\displaystyle
Q^{\widetilde{\pi}^{m}}_{h}(s,a;\widetilde{p}^{m},\widehat{r})=Q^{\pi^{m}}_{h}(s,a;p^{m},r).$
(31)

By hypothesis, $\widehat{r}\in\widetilde{\mathcal{R}}^{\cup}$, therefore:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r})\geq
Q^{\widetilde{\pi}^{m}}_{h}(s,a;\widetilde{p}^{m},\widehat{r}),$

from which it follows that:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};p,r)\geq
Q^{\pi^{m}}_{h}(s,a;p^{m},r).$

Since $p^{m}\in[p]_{\equiv_{\mathcal{Z}^{p,\pi^{b}}}}$ and $\pi^{m}$ is the
worst policy in $[\pi^{E}]_{\equiv_{\mathcal{Z}^{p,\pi^{b}}}}$ for $p^{m}$,
then we have $r\in\mathcal{R}_{p,\pi^{E}}^{\cup}$. ∎

####  F.3.1 Lemmas for Theorem 6.1

######  Lemma F.8 (Performance Decomposition Subset).

Under good event $\mathcal{E}$, it holds that:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widetilde{\mathcal{R}}^{\cap})$
$\displaystyle\leq 2H\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}b_{h}(s,a)+8H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a).$

###### Proof.

Observe that:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widetilde{\mathcal{R}}^{\cap})$
$\displaystyle\coloneqq\max\\{\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\inf\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cap}}d(r,\widetilde{r}),\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cap}}\inf\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}d(r,\widetilde{r})\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\inf\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cap}}d(r,\widetilde{r})$
$\displaystyle\eqqcolon\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\inf\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\Bigl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}+\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}\Bigr{)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\Bigl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}+\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}\Bigr{)},$
(32)

where at (1) we have used that, under event $\mathcal{E}$, we have
$\widetilde{\mathcal{R}}^{\cap}\subseteq\mathcal{R}_{p,\pi^{E}}^{\cap}$, and
at (2) we have applied Lemma F.6, denoting with $\widehat{r}$ the reward
chosen from $\widetilde{\mathcal{R}}^{\cap}$.

Now, we consider the various triples
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times\llbracket H\rrbracket$
differently according to the definition of $\widehat{r}$ in Lemma F.6. Let us
begin with any $(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}$. Thanks to Eq. F.3, we
know that, for any $(s,h)\in\mathcal{S}^{p,\pi^{E}}$, it holds that
$Q^{\pi^{E}}_{h}(s,a^{E};p,r)=Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})$.
Since any expert’s action when played from $\mathcal{S}^{p,\pi^{E}}$ brings to
$\mathcal{S}^{p,\pi^{E}}$ (even under $\widetilde{p}^{m}$, by definition) ,
then we can write:

$\displaystyle\bigl{|}r_{h}(s,a^{E})-\widehat{r}_{h}(s,a^{E})\bigr{|}$
$\displaystyle=\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle=\bigl{|}\sum\limits_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}s^{\prime}\in\mathcal{S}^{p,\pi^{E}}}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\sum\limits_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}s^{\prime}\in\mathcal{S}^{p,\pi^{E}}}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p,r})\bigr{|}$
$\displaystyle=\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}(p_{h}(s^{\prime}|s,a^{E})-\widetilde{p}^{m}_{h}(s^{\prime}|s,a^{E}))V^{\pi^{E}}_{h+1}(s^{\prime};p,r)\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\sum\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}(p_{h}(s^{\prime}|s,a^{E})-\widetilde{p}^{m}_{h}(s^{\prime}|s,a^{E}))HM\bigr{|}$
$\displaystyle\leq
HM\bigl{\|}p_{h}(\cdot|s,a^{E})-\hat{p}_{h}(\cdot|s,a^{E})\bigr{\|}_{1}+HM\bigl{\|}\widetilde{p}^{m}_{h}(\cdot|s,a^{E})-\hat{p}_{h}(\cdot|s,a^{E})\bigr{\|}_{1}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}2MHb_{h}(s,a^{E}),$
(33)

where at (1) we use Eq. F.3, at (2) we use triangle inequality and we upper
bound the value function by $H$ times the maximum reward, and at (3) we use
the event in Lemma F.2 twice.

Now, let us consider any triple
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\setminus\mathcal{Z}^{p,\pi^{E}}$. Thanks to
Lemma F.6, we can write:

$\displaystyle\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}$
$\displaystyle=\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p^{M}_{h}(s^{\prime}|s,a)V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p_{h}}(s^{\prime}|s,a)V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})$
$\displaystyle\qquad\pm\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}(p_{h}(s^{\prime}|s,a)-\widetilde{p}^{M}_{h}(s^{\prime}|s,a))V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\qquad+\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)\bigl{(}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}2MHb_{h}(s,a)+\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)\bigl{(}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}2MHb_{h}(s,a)+\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\bigl{(}Q^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h+1}(s^{\prime},a^{E};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p},r)-Q^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\qquad+\bigl{|}\sum\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\bigl{(}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r)-\max\limits_{a^{\prime\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime\prime};\widetilde{p}^{M},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{\leq}2MHb_{h}(s,a)+\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\bigl{(}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\qquad+\bigl{|}\sum\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\bigl{(}\underbrace{\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r)-\max\limits_{a^{\prime\prime}\in\mathcal{A}}Q^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{M}}}_{h+1}(s^{\prime},a^{\prime\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{M},r})}_{=0}\bigr{)}\bigr{|}$
$\displaystyle\leq
2MHb_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\underbrace{\bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})\bigr{|}}_{\eqqcolon
X_{h+1}(s^{\prime})},$

where at (1) we have used that, since $(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$,
then $p^{M}_{h}(\cdot|s,a)=p_{h}(\cdot|s,a)$, at (2) we have applied triangle
inequality, at (3) we upper bound the value function by $H$ times the maximum
reward and we use the event in Lemma F.2 twice, at (4) we use triangle
inequality and the Bellman’s equation and that the expert’s action $a^{E}$ is
played by both $\pi^{M}$ and $\widetilde{\pi}^{M}$ in any
$(s,h)\in\mathcal{S}^{p,\pi^{E}}$, at (5) we apply Eq. 29.

Now, having defined terms $X_{h}(s)$ for all $(s,h)\in\mathcal{S}^{p,\pi^{E}}$
as above, we recursively bound term $X_{h+1}(s^{\prime})$.

$\displaystyle X_{h+1}(s^{\prime})$
$\displaystyle\coloneqq\bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(6)}}}{=}\bigl{|}r_{h+1}(s^{\prime},a^{E})-\widehat{r}_{h+1}(s^{\prime},a^{E})\bigr{|}$
$\displaystyle\qquad+\bigl{|}\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};p,r)-\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}\widetilde{p}^{M}_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(7)}}}{\leq}2MHb_{h+1}(s^{\prime},a^{E})+\bigl{|}\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};p,r)-\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}\widetilde{p}^{M}_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\bigr{)}$
$\displaystyle\qquad\pm\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(8)}}}{\leq}2MHb_{h+1}(s^{\prime},a^{E})+\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}\bigl{|}\bigl{(}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})-\widetilde{p}^{M}_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})\bigr{)}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\qquad+\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})\bigl{|}V^{\pi^{E}}_{h+2}(s^{\prime\prime};p,r)-V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(9)}}}{\leq}4MHb_{h+1}(s^{\prime},a^{E})+\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})\underbrace{\bigl{|}Q^{\pi^{E}}_{h+2}(s^{\prime\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+2}(s^{\prime\prime},a^{E};\widetilde{p}^{M},\widehat{r})\bigr{|}}_{\eqqcolon
X_{h+2}(s^{\prime\prime})},$

where at (6) we use the definition of Q function, and we apply triangle
inequality; at (7) we use again triangle inequality and Eq. F.3.1, at (8) we
apply triangle inequality, and at (9) we use again the event in Lemma F.2
twice. The recursion on the $X$ terms tells us that:

$\displaystyle X_{h}(s)\leq
4MHb_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}X_{h+1}(s^{\prime}).$ (34)

Therefore, we can upper bound the difference between rewards in
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\setminus\mathcal{Z}^{p,\pi^{E}}$ as:

$\displaystyle\begin{split}\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}&\leq
2MHb_{h}(s,a)+4MH\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho_{h^{\prime}}^{p,\pi^{E}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E}).\end{split}$
(35)

Now, the only missing triples to consider are those
$(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$. Similarly to the triples just
considered, we can write:

$\displaystyle\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}$
$\displaystyle=\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p^{M}_{h}(s^{\prime}|s,a)V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\bigl{|}\max\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\max\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{=}\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\bigl{|}V^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h+1}(s^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p},r)-V^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|},$
$\displaystyle\qquad\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\bigl{|}\underbrace{V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})}_{=0}\bigr{|}\Bigr{\\}}$
$\displaystyle=\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\eqqcolon\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}X_{h+1}(s^{\prime})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}4MH\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{(}b_{h+1}(s^{\prime},a^{E})+\sum\limits_{h^{\prime}\in\llbracket
h+2,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{p,\pi^{E}}_{h^{\prime}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})\Bigr{)},$
(36)

where at (1) we have used that $(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$ and the
definitions of $p^{M}$ and $\widetilde{p}^{M}$, at (2) we have used that for
any pair of real-valued functions $f,g$ it holds that
$|\max_{x}f(x)-\max_{x}g(x)|\leq\max_{x}|f(x)-g(x)|$, at (3) we use Eq. 29 to
realize that in $(s,h)$ outside $\mathcal{S}^{p,\pi^{E}}_{h+1}$ we have an
equality of Q-functions, and thus the difference is 0, at (4) we have unfolded
the recursion on the $X$ terms by using Eq. 34.

By combining Eq. F.3.1 with Eq. F.3.1, Eq. 35, and Eq. F.3.1, we get:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widetilde{\mathcal{R}}^{\cap})$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\biggl{(}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)2Hb_{h}(s,a)$
$\displaystyle\qquad+\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)\Bigl{(}2Hb_{h}(s,a)+4H\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho_{h^{\prime}}^{p,\pi^{E}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})\Bigr{)}$
$\displaystyle\qquad+\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}4H\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{p,\pi^{E}}_{h^{\prime}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})\biggr{)}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\biggl{(}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)2Hb_{h}(s,a)$
$\displaystyle\qquad+\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)\Bigl{(}2Hb_{h}(s,a)+4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\Bigr{)}$
$\displaystyle\qquad+\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{)}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\biggl{(}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)2Hb_{h}(s,a)$
$\displaystyle\qquad+\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)2Hb_{h}(s,a)+8H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{)}$
$\displaystyle\leq 2H\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}b_{h}(s,a)+8H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a).$

∎

######  Lemma F.9 (Performance Decomposition Superset).

Under good event $\mathcal{E}$, it holds that:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cup}\widetilde{\mathcal{R}}^{\cup})$
$\displaystyle\leq 2H\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}b_{h}(s,a)+8H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a).$

###### Proof.

Observe that:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cup},\widetilde{\mathcal{R}}^{\cup})$
$\displaystyle\coloneqq\max\\{\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cup}}\inf\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}d(r,\widetilde{r}),\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\inf\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cup}}d(r,\widetilde{r})\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\inf\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cup}}d(r,\widetilde{r})$
$\displaystyle\eqqcolon\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\inf\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cup}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\Bigl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}+\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}\Bigr{)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\Bigl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}+\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}\Bigr{)},$
(37)

where at (1) we have used that, under event $\mathcal{E}$, we have
$\mathcal{R}_{p,\pi^{E}}^{\cup}\subseteq\widetilde{\mathcal{R}}^{\cup}$, and
at (2) we have applied Lemma F.7, denoting with $r$ the reward chosen from
$\mathcal{R}_{p,\pi^{E}}^{\cup}$.

Now, we consider the various triples
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times\llbracket H\rrbracket$
differently according to the definition of $r$ in Lemma F.7. Let us begin with
any $(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}$. We can write:

$\displaystyle\begin{split}\bigl{|}r_{h}(s,a^{E})-\widehat{r}_{h}(s,a^{E})\bigr{|}&=\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\\\
&=\bigl{|}\sum\limits_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\sum\limits_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}\\\
&=\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p,r})\bigr{|}\\\
&\leq\bigl{\|}p_{h}(\cdot|s,a^{E})-\widetilde{p}^{M}_{h}(\cdot|s,a^{E})\bigr{\|}_{1}MH\\\
&\leq\bigl{\|}p_{h}(\cdot|s,a^{E})-\hat{p}_{h}(\cdot|s,a^{E})\bigr{\|}_{1}MH+\bigl{\|}\hat{p}_{h}(\cdot|s,a^{E})-\widetilde{p}^{M}_{h}(\cdot|s,a^{E})\bigr{\|}_{1}MH\\\
&\leq 2MHb_{h}(s,a^{E}).\end{split}$ (38)

Now, let us consider any triple
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\setminus\mathcal{Z}^{p,\pi^{E}}$. Thanks to
Lemma F.7, we can write:

$\displaystyle\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}$
$\displaystyle=\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p^{m}_{h}(s^{\prime}|s,a)V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p_{h}(s^{\prime}|s,a)}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})$
$\displaystyle\qquad\pm\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}(p_{h}(s^{\prime}|s,a)-\widetilde{p}^{m}_{h}(s^{\prime}|s,a))V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\qquad+\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)\bigl{(}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}2MHb_{h}(s,a)+\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a)\bigl{(}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}2MHb_{h}(s,a)+\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\bigl{(}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\qquad+\bigl{|}\sum\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\bigl{(}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\pi^{m}}_{h+1}(s^{\prime},a^{\prime};p^{m},r)-\max\limits_{a^{\prime\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime\prime};\widetilde{p}^{m},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{\leq}2MHb_{h}(s,a)+\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\bigl{(}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\qquad+\bigl{|}\sum\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\bigl{(}\underbrace{\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\pi^{m}}_{h+1}(s^{\prime},a^{\prime};p^{m},r)-\max\limits_{a^{\prime\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{m},r})}_{=0}\bigr{)}\bigr{|}$
$\displaystyle\leq
2MHb_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\underbrace{\bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})\bigr{|}}_{\eqqcolon
Y_{h+1}(s^{\prime})},$

where at (1) we have used that, since $(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$,
then $p^{m}_{h}(\cdot|s,a)=p_{h}(\cdot|s,a)$, at (2) we have applied triangle
inequality, at (3) we upper bound the value function by $H$ times the maximum
reward and we use the event in Lemma F.2 twice, at (4) we use triangle
inequality and the Bellman optimality equation and that the expert’s action
$a^{E}$ is optimal in any $(s,h)\in\mathcal{S}^{p,\pi^{E}}$, at (5) we apply
Eq. 31.

Now, having defined terms $\\{Y_{h}(s)\\}_{h}$ for all
$s\in\mathcal{S}^{p,\pi^{E}}$ as above, we recursively bound term
$Y_{h+1}(s^{\prime})$. It should be remarked that
$(s^{\prime},h+1)\in\mathcal{S}^{p,\pi^{E}}$.

$\displaystyle Y_{h+1}(s^{\prime})$
$\displaystyle\coloneqq\bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(6)}}}{=}\bigl{|}r_{h+1}(s^{\prime},a^{E})-\widehat{r}_{h+1}(s^{\prime},a^{E})\bigr{|}$
$\displaystyle\qquad+\bigl{|}\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};p,r)-\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}\widetilde{p}^{m}_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\bigr{)}\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(7)}}}{\leq}2MHb_{h+1}(s^{\prime},a^{E})+\bigl{|}\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};p,r)-\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}\widetilde{p}^{m}_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\bigr{)}$
$\displaystyle\qquad\pm\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(8)}}}{\leq}2MHb_{h+1}(s^{\prime},a^{E})+\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}\bigl{|}\bigl{(}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})-\widetilde{p}^{m}_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})\bigr{)}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\qquad+\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})\bigl{|}V^{\pi^{E}}_{h+2}(s^{\prime\prime};p,r)-V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(9)}}}{\leq}4MHb_{h+1}(s^{\prime},a^{E})+\sum\limits_{s^{\prime\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+2}}p_{h+1}(s^{\prime\prime}|s^{\prime},a^{E})\underbrace{\bigl{|}Q^{\pi^{E}}_{h+2}(s^{\prime\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+2}(s^{\prime\prime},a^{E};\widetilde{p}^{m},\widehat{r})\bigr{|}}_{\eqqcolon
Y_{h+2}(s^{\prime\prime})},$

where at (6) we use the definition of Q function, and we apply triangle
inequality; at (7) we use again triangle inequality and Eq. 38, at (8) we
apply triangle inequality, and at (9) we use again the event in Lemma F.2
twice. The recursion on the $Y$ terms tells us that:

$\displaystyle Y_{h}(s)\leq
4MHb_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}Y_{h+1}(s^{\prime}).$ (39)

Therefore, we can upper bound the difference between rewards in
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\setminus\mathcal{Z}^{p,\pi^{E}}$ as:

$\displaystyle\begin{split}\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}&\leq
2MHb_{h}(s,a)+4MH\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho_{h^{\prime}}^{p,\pi^{E}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E}).\end{split}$
(40)

Now, the only missing triples to consider are those
$(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$. Similarly to the triples just
considered, we can write:

$\displaystyle\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}$
$\displaystyle=\bigl{|}\sum\limits_{s^{\prime}\in\mathcal{S}}p^{m}_{h}(s^{\prime}|s,a)V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\bigl{|}\min\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-\min\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\max\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{=}\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\bigl{|}V^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h+1}(s^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p},r)-V^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|},$
$\displaystyle\qquad\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\bigl{|}\underbrace{V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})}_{=0}\bigr{|}\Bigr{\\}}$
$\displaystyle=\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\eqqcolon\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Y_{h+1}(s^{\prime})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}4MH\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{(}b_{h+1}(s^{\prime},a^{E})+\sum\limits_{h^{\prime}\in\llbracket
h+2,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{p,\pi^{E}}_{h^{\prime}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})\Bigr{)},$
(41)

where at (1) we have used that $(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$ and the
definitions of $p^{m}$ and $\widetilde{p}^{m}$, at (2) we have used that for
any pair of real-valued functions $f,g$ it holds that
$|\min_{x}f(x)-\min_{x}g(x)|\leq\max_{x}|f(x)-g(x)|$, at (3) we use Eq. 31 to
realize that in $(s,h)$ outside $\mathcal{S}^{p,\pi^{E}}_{h+1}$ we have an
equality of Q-functions, and thus the difference is 0, and that in
$\mathcal{S}^{p,\pi^{E}}$ the optimal action is always the expert’s action, at
(4) we have unfolded the recursion on the $Y$ terms by using Eq. 39.

By combining Eq. F.3.1 with Eq. 38, Eq. 40, and Eq. F.3.1, we get:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cup},\widetilde{\mathcal{R}}^{\cup})$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\biggl{(}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)2Hb_{h}(s,a)$
$\displaystyle\qquad+\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)\Bigl{(}2Hb_{h}(s,a)+4H\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho_{h^{\prime}}^{p,\pi^{E}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})\Bigr{)}$
$\displaystyle\qquad+\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}4H\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{p,\pi^{E}}_{h^{\prime}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})\biggr{)}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\biggl{(}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)2Hb_{h}(s,a)$
$\displaystyle\qquad+\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)\Bigl{(}2Hb_{h}(s,a)+4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\Bigr{)}$
$\displaystyle\qquad+\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{)}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\biggl{(}\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)2Hb_{h}(s,a)$
$\displaystyle\qquad+\sum\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}\rho^{p,\pi^{b}}_{h}(s,a)2Hb_{h}(s,a)+8H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{)}$
$\displaystyle\leq 2H\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}b_{h}(s,a)+8H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a).$

∎

####  F.3.2 Lemmas for Theorem 6.2

######  Lemma F.10 (Performance Decomposition Subset).

Under good event $\mathcal{E}$, it holds that:

$\displaystyle\mathcal{H}_{\infty}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widetilde{\mathcal{R}}^{\cap})$
$\displaystyle\leq
2H^{2}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}b_{h}(s,a)+4H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a).$

###### Proof.

Observe that:

$\displaystyle\mathcal{H}_{\infty}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widetilde{\mathcal{R}}^{\cap})$
$\displaystyle\coloneqq\max\\{\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\inf\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cap}}d_{\infty}(r,\widetilde{r}),\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cap}}\inf\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}d_{\infty}(r,\widetilde{r})\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\inf\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cap}}d_{\infty}(r,\widetilde{r})$
$\displaystyle\eqqcolon\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\inf\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\max\limits_{(s,a)\in\mathcal{S}\times\mathcal{A}}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cap}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\max\limits_{(s,a)\in\mathcal{S}\times\mathcal{A}}\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|},$
(42)

where at (1) we have used that, under event $\mathcal{E}$, we have
$\widetilde{\mathcal{R}}^{\cap}\subseteq\mathcal{R}_{p,\pi^{E}}^{\cap}$, and
at (2) we have applied Lemma F.6, denoting with $\widehat{r}$ the reward
chosen from $\widetilde{\mathcal{R}}^{\cap}$.

By combining Eq. F.3.2 with Eq. F.3.1, Eq. 35, and Eq. F.3.1, we get:

$\displaystyle\mathcal{H}_{\infty}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widetilde{\mathcal{R}}^{\cap})$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\max\biggl{\\{}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a),$
$\displaystyle\qquad\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a)+4H\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho_{h^{\prime}}^{p,\pi^{E}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E}),$
$\displaystyle\qquad\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}4H\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{p,\pi^{E}}_{h^{\prime}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})\biggr{\\}}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\max\biggl{\\{}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a),$
$\displaystyle\qquad\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a)+4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}),$
$\displaystyle\qquad\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{\\}}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\max\biggl{\\{}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a),\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a)+4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{\\}}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}2Hb_{h}(s,a)+\sum\limits_{h\in\llbracket
H\rrbracket}4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{\\}}$
$\displaystyle\leq
2H^{2}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}b_{h}(s,a)+4H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a).$

∎

######  Lemma F.11 (Performance Decomposition Superset).

Under good event $\mathcal{E}$, it holds that:

$\displaystyle\mathcal{H}_{\infty}(\mathcal{R}_{p,\pi^{E}}^{\cup}\widetilde{\mathcal{R}}^{\cup})$
$\displaystyle\leq
2H^{2}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}b_{h}(s,a)+4H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a).$

###### Proof.

Observe that:

$\displaystyle\mathcal{H}_{\infty}(\mathcal{R}_{p,\pi^{E}}^{\cup},\widetilde{\mathcal{R}}^{\cup})$
$\displaystyle\coloneqq\max\\{\sup\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cup}}\inf\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}d_{\infty}(r,\widetilde{r}),\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\inf\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cup}}d_{\infty}(r,\widetilde{r})\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\inf\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cup}}d_{\infty}(r,\widetilde{r})$
$\displaystyle\eqqcolon\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\inf\limits_{r\in\mathcal{R}_{p,\pi^{E}}^{\cup}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\max\limits_{(s,a)\in\mathcal{S}\times\mathcal{A}}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\frac{1}{M}\sum\limits_{h\in\llbracket
H\rrbracket}\max\limits_{(s,a)\in\mathcal{S}\times\mathcal{A}}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|},$
(43)

where at (1) we have used that, under event $\mathcal{E}$, we have
$\mathcal{R}_{p,\pi^{E}}^{\cup}\subseteq\widetilde{\mathcal{R}}^{\cup}$, and
at (2) we have applied Lemma F.7, denoting with $r$ the reward chosen from
$\mathcal{R}_{p,\pi^{E}}^{\cup}$.

By combining Eq. F.3.2 with Eq. 38, Eq. 40, and Eq. F.3.1, we get:

$\displaystyle\mathcal{H}_{\infty}(\mathcal{R}_{p,\pi^{E}}^{\cup},\widetilde{\mathcal{R}}^{\cup})$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\max\biggl{\\{}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a),$
$\displaystyle\qquad\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a)+4H\sum\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}p_{h}(s^{\prime}|s,a)\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho_{h^{\prime}}^{p,\pi^{E}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E}),$
$\displaystyle\qquad\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}4H\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\sum\limits_{h^{\prime}\in\llbracket
h+1,H\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{p,\pi^{E}}_{h^{\prime}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})\biggr{\\}}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\max\biggl{\\{}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a),$
$\displaystyle\qquad\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a)+4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}),$
$\displaystyle\qquad\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{\\}}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\max\biggl{\\{}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a),\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}\setminus\mathcal{Z}^{p,\pi^{E}}_{h}}2Hb_{h}(s,a)+4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{\\}}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\max\limits_{(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}}2Hb_{h}(s,a)+\sum\limits_{h\in\llbracket
H\rrbracket}4H^{2}\max\limits_{(s^{\prime},a^{E},h^{\prime})\in\mathcal{Z}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{\\}}$
$\displaystyle\leq
2H^{2}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}b_{h}(s,a)+4H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a).$

∎

####  F.3.3 Proofs of the main theorems

Thanks to Lemma F.8 and Lemma F.9, we can conclude the proof of Theorem 6.1.
See 6.1

###### Proof.

The proof for the subset and superset is completely analogous. Under good
event $\mathcal{E}$, the performance decomposition lemma for the subset (Lemma
F.8) tells us that:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widetilde{\mathcal{R}}^{\cap})$
$\displaystyle\leq 2H\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho^{p,\pi^{b}}_{h}(\cdot,\cdot)}b_{h}(s,a)+8H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a)\leq\epsilon.$

We upper bound both the terms of the sum by $\epsilon/2$. The bound of the
first term is analogous to the bound of the term provided in the proof of
Theorem 5.1, so we will not rewrite it here; with regards to the other term,
we have:

$\displaystyle
8H^{3}\max\limits_{(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a^{E}))$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}8H^{3}\max\limits_{(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}}\sqrt{2\frac{\beta(N_{h}^{b}(s,a^{E}),\delta)}{N_{h}^{b}(s,a^{E})}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}8\sqrt{2}H^{3}\sqrt{\beta(\tau^{b},\delta)}\max\limits_{(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}}\sqrt{\frac{1}{N_{h}^{b}(s,a^{E})}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}8\sqrt{2}H^{3}\sqrt{\beta(\tau^{b},\delta)}\max\limits_{(s,a^{E},h)\in\mathcal{Z}^{p,\pi^{E}}}\sqrt{c_{4}\frac{\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau^{b}\rho_{h}^{p,\pi^{b}}(s,a^{E})}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{=}c_{5}H^{3}\sqrt{\frac{\beta(\tau^{b},\delta)\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\tau^{b}\rho_{\min}^{\pi^{b},\mathcal{Z}^{p,\pi^{E}}}}}\leq\epsilon/2,$

where at (1) we have used the definition of the $b$ terms, at (2) we have
upper bounded
$\beta(N_{\bar{h}}^{b}(\bar{s},a^{E}),\delta)\leq\beta(\tau^{b},\delta)$ for
all $(\bar{s},\bar{h})\in\mathcal{S}^{p,\pi^{E}}$, at (3) we use event
$\mathcal{E}_{4}$, at (4) we define $c_{5}\coloneqq 8\sqrt{2c_{4}}$ and we use
the definition of $\rho_{\min}^{\pi^{b},\mathcal{Z}^{p,\pi^{E}}}$.

Similarly to the proof of Theorem 5.1, we apply Lemma J.3 to ($c_{6}\coloneqq
4c_{5}^{2}$):

$\displaystyle\tau^{b}\geq
c_{6}\frac{H^{6}\ln\frac{|\mathcal{Z}^{p,\pi^{b}}|}{\delta}}{\rho_{\min}^{\pi^{b},\mathcal{Z}^{p,\pi^{E}}}\epsilon^{2}}\bigl{(}\ln\frac{4|\mathcal{Z}^{p,\pi^{b}}|}{\delta}+(|\mathcal{S}^{p,\pi^{b}}_{\max}|-1)\ln\bigl{(}e(1+\tau^{b}/(|\mathcal{S}^{p,\pi^{b}}_{\max}|-1))\bigr{)}\bigr{)},$

to obtain:

$\displaystyle\tau^{b}$
$\displaystyle\leq\widetilde{\mathcal{O}}\Biggl{(}\frac{H^{6}\ln\frac{1}{\delta}}{\rho_{\min}^{\pi^{b},\mathcal{Z}^{p,\pi^{E}}}\epsilon^{2}}\biggl{(}\ln\frac{1}{\delta}+|\mathcal{S}^{p,\pi^{b}}_{\max}|\biggr{)}\Biggr{)}.$

We can do the same for the superset through Lemma F.9. By combining the
various bounds, we get the result. ∎

Thanks to Lemma F.10 and Lemma F.11, we can conclude the proof of Theorem 6.2.
See 6.2

###### Proof Sketch.

The proof is analogous to that of Theorem 6.1. The only difference is that we
use Lemma F.10 and Lemma F.10, and that we follow the proof of Theorem 5.2
instead of that of Theorem 5.1 to bound the first term of:

$\displaystyle
2H^{2}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}}b_{h}(s,a)+4H^{3}\max\limits_{(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}}b_{h}(s,a)\leq\epsilon.$

∎

###  F.4 Sample complexity for PIRLO with additional requirements

In the proofs of Theorem 6.1 and Theorem 6.2, we have used reward choice
lemmas that set $\widehat{r}_{h}(s,a)\neq r_{h}(s,a)$ in
$(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$. However, it might be interesting to
relate directly the error in the estimation of the transition model with the
difference in the reward functions, so that where we do not have samples we
have zero error. We would like to have $\widehat{r}_{h}(s,a)=r_{h}(s,a)$ in
$(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$. Notice that this property is satisfied
in the proofs of Theorem 5.1 and Theorem 5.2. Moreover, for a notion of
distance other than $d$ or $d_{\infty}$, the condition
$\widehat{r}_{h}(s,a)=r_{h}(s,a)$ in $(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$
might even be needed. Therefore, in this section, we provide reward choice
lemmas that satisfy this property, and we show that this selection ends up in
a $H^{8}$ dependence in the sample complexity instead of $H^{6}$.

######  Lemma F.12 (Reward Choice Subset).

Under good event $\mathcal{E}$, for any $r\in\mathcal{R}_{p,\pi^{E}}^{\cap}$,
the reward $\widehat{r}$ constructed (recursively) as:

$\displaystyle\begin{cases}\widehat{r}_{h}(s,a^{E})=r_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\\\
\qquad\qquad\qquad+\max\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-\max\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r),\qquad\forall(s,h)\in\mathcal{S}^{p,\pi^{E}}\\\
\widehat{r}_{h}(s,a)=r_{h}(s,a),\quad\forall(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}\\\
\widehat{r}_{h}(s,a)=r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}p^{M}_{h}(s^{\prime}|s,a)V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r}),\quad\text{otherwise}\\\
\end{cases},$

belongs to $\widetilde{\mathcal{R}}^{\cap}$.

###### Proof.

By definition of $\widetilde{\mathcal{R}}^{\cap}$, the reward $\widehat{r}$
belongs to $\widetilde{\mathcal{R}}^{\cap}$ if and only if:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})\geq
Q^{\widetilde{\pi}^{M}}_{h}(s,a;\widetilde{p}^{M},\widehat{r}).$

By hypothesis, $r\in\mathcal{R}_{p,\pi^{E}}^{\cap}$, therefore:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};p,r)\geq
Q^{\pi^{M}}_{h}(s,a;p^{M},r),$

thus, if we show that $\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}$, it holds that:

$\displaystyle
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})-Q^{\widetilde{\pi}^{M}}_{h}(s,a;\widetilde{p}^{M},\widehat{r})\geq
Q^{\pi^{E}}_{h}(s,a^{E};p,r)-Q^{\pi^{M}}_{h}(s,a;p^{M},r),$

then we are done.

Let us begin with triples $(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$ such that
$(s,h)\in\mathcal{S}^{p,\pi^{E}}$. By rearranging the terms in the definition
of $\widehat{r}$, we observe that:

$\displaystyle\widehat{r}_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})=r_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)$
$\displaystyle\qquad\qquad+\max\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-\max\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)$
$\displaystyle\iff
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)+\max\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-\max\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pm\widehat{r}_{h}(s,a)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\iff}Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)+\widehat{r}_{h}(s,a)+\max\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-\bigl{(}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r_{h}(s,a)}+\max\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)\bigr{)}$
$\displaystyle\iff
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)+Q^{\widetilde{\pi}^{M}}_{h}(s,a;\widetilde{p}^{M},\widehat{r})-Q^{\pi^{M}}_{h}(s,a;p^{M},r)$
$\displaystyle\implies
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})-Q^{\widetilde{\pi}^{M}}_{h}(s,a;\widetilde{p}^{M},\widehat{r})\geq
Q^{\pi^{E}}_{h}(s,a^{E};p,r)-Q^{\pi^{M}}_{h}(s,a;p^{M},r),$

where at (1) we have used that $\widehat{r}_{h}(s,a)=r_{h}(s,a)$ by
definition.

Now, consider any other triple
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\setminus\mathcal{Z}^{p,\pi^{E}}$ such that
$(s,h)\in\mathcal{S}^{p,\pi^{E}}$. By rearranging the terms, we obtain:

$\displaystyle
Q^{\widetilde{\pi}^{M}}_{h}(s,a;\widetilde{p}^{M},\widehat{r})=Q^{\pi^{M}}_{h}(s,a;p^{M},r),$
(44)

therefore, it suffices to show that

$\displaystyle Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})\geq
Q^{\pi^{E}}_{h}(s,a^{E};p,r).$

By using again the definition of $\widehat{r}$ for
$(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}$, we know that:

$\displaystyle
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{m},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)+\max\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-\max\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r),$
(45)

therefore, if we show that

$\displaystyle\max\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\geq\max\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r),$

then we are done. We do it by induction. At stage $H-1$, we have that:

$\displaystyle\max\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{H}(s^{\prime};\widetilde{p}^{M},\widehat{r})$
$\displaystyle=\max\limits_{s^{\prime}\in\mathcal{S}}\operatorname*{\mathbb{E}}\limits_{a^{\prime}\sim\widetilde{\pi}^{M}_{H}(\cdot|s^{\prime})}\widehat{r}_{H}(s^{\prime},a^{\prime})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\max\limits_{s^{\prime}\in\mathcal{S}}\operatorname*{\mathbb{E}}\limits_{a^{\prime}\sim\pi^{M}_{H}(\cdot|s^{\prime})}r_{H}(s^{\prime},a^{\prime})$
$\displaystyle=\max\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{H}(s^{\prime};p^{M},r),$

where at (1) we have used the definition of $\widehat{r}$ at stage $H$, and
the definitions of $\widetilde{\pi}^{M}$ and $\pi^{M}$. We make the inductive
hypothesis that, at stage $h+1$, it holds that
$\max_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+2}(s^{\prime};\widetilde{p}^{M},\widehat{r})\geq\max_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+2}(s^{\prime};p^{M},r)$,
and we consider stage $h$:

$\displaystyle\max\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r}),\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{M},\widehat{r})\Bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\geq}\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widetilde{p}^{m}},\widehat{r}),\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{M},\widehat{r})\Bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\geq}\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r}),\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{M},\widehat{r})\Bigr{\\}}$
$\displaystyle=\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r),$
$\displaystyle\qquad\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\bigl{\\{}\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\in\mathcal{Z}^{p,\pi^{b}}}Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{M},\widehat{r}),\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{\\}}\Bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{=}\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r),$
$\displaystyle\qquad\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\bigl{\\{}\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\in\mathcal{Z}^{p,\pi^{b}}}Q^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{M}}}_{h+1}(s^{\prime},a^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{M}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r}),$
$\displaystyle\qquad\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}\widehat{r}_{h+1}(s^{\prime},a^{\prime})+\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\bigr{\\}}\Bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{\geq}\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r),$
$\displaystyle\qquad\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\bigl{\\{}\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\in\mathcal{Z}^{p,\pi^{b}}}Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r),$
$\displaystyle\qquad\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r}_{h+1}(s^{\prime},a^{\prime})+\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+2}(s^{\prime\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{M}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r})\bigr{\\}}\Bigr{\\}}$
$\displaystyle=\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r),$
$\displaystyle\qquad\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\bigl{\\{}\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\in\mathcal{Z}^{p,\pi^{b}}}Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r),\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r)\bigr{\\}}\Bigr{\\}}$
$\displaystyle=\max\Bigl{\\{}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r),\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r)\Bigr{\\}}$
$\displaystyle=\max\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r),$

where at (1) we use the definition of $\widetilde{\pi}^{M}$, at (2) we use the
definition of $\widetilde{p}^{m}$ and $\widetilde{p}^{M}$, at (3) we use the
inductive hypothesis along with Eq. 45, at (4) we use Eq. 44 and the
definition of Q-function, at (5) we use the definition of $\widehat{r}$ and
the inductive hypothesis.

This concludes the proof. ∎

######  Lemma F.13 (Reward Choice Superset).

Under good event $\mathcal{E}$, for any
$\widehat{r}\in\widetilde{\mathcal{R}}^{\cup}$, the reward $r$ constructed
(recursively) as:

$\displaystyle\begin{cases}r_{h}(s,a^{E})=\widehat{r}_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)\\\
\qquad\qquad\qquad+\min\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)-\min\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r}),\qquad\forall(s,h)\in\mathcal{S}^{p,\pi^{E}}\\\
r_{h}(s,a)=\widehat{r}_{h}(s,a),\quad\forall(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}\\\
r_{h}(s,a)=\widehat{r}_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{m}_{h}(s^{\prime}|s,a)V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-\sum\limits_{s^{\prime}\in\mathcal{S}}p^{m}_{h}(s^{\prime}|s,a)V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r),\quad\text{otherwise}\\\
\end{cases},$

belongs to $\mathcal{R}_{p,\pi^{E}}^{\cup}$.

###### Proof.

By definition of $\mathcal{R}_{p,\pi^{E}}^{\cup}$, a sufficient condition for
having the reward $r$ belong to $\mathcal{R}_{p,\pi^{E}}^{\cup}$ is:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};p,r)\geq
Q^{\pi^{m}}_{h}(s,a;p^{m},r).$

By hypothesis, $r\in\widetilde{\mathcal{R}}^{\cup}$, therefore:

$\displaystyle\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r})\geq
Q^{\widetilde{\pi}^{m}}_{h}(s,a;\widetilde{p}^{m},\widehat{r}),$

thus, if we show that $\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}$, it holds that:

$\displaystyle Q^{\pi^{E}}_{h}(s,a^{E};p,r)-Q^{\pi^{m}}_{h}(s,a;p^{m},r)\geq
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r})-Q^{\widetilde{\pi}^{m}}_{h}(s,a;\widetilde{p}^{m},\widehat{r}),$

then we are done.

Let us begin with triples $(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$ such that
$(s,h)\in\mathcal{S}^{p,\pi^{E}}$. By rearranging the terms in the definition
of $r$, we observe that:

$\displaystyle\widehat{r}_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}^{M}_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})=r_{h}(s,a^{E})+\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}(s^{\prime}|s,a^{E})V^{\pi^{E}}_{h+1}(s^{\prime};p,r)$
$\displaystyle\qquad\qquad+\min\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-\min\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)$
$\displaystyle\iff
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)+\min\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-\min\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r){\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pm
r_{h}(s,a)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\iff}Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widehat{r}_{h}(s,a)}+\min\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-\bigl{(}r_{h}(s,a)+\min\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)\bigr{)}$
$\displaystyle\iff
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)+Q^{\widetilde{\pi}^{m}}_{h}(s,a;\widetilde{p}^{m},\widehat{r})-Q^{\pi^{m}}_{h}(s,a;p^{m},r)$
$\displaystyle\implies
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r})-Q^{\widetilde{\pi}^{m}}_{h}(s,a;\widetilde{p}^{m},\widehat{r})\geq
Q^{\pi^{E}}_{h}(s,a^{E};p,r)-Q^{\pi^{m}}_{h}(s,a;p^{m},r),$

where at (1) we have used that $r_{h}(s,a)=\widehat{r}_{h}(s,a)$ by
definition.

Now, consider any other triple
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\setminus\mathcal{Z}^{p,\pi^{E}}$ such that
$(s,h)\in\mathcal{S}^{p,\pi^{E}}$. By rearranging the terms, we obtain:

$\displaystyle
Q^{\widetilde{\pi}^{m}}_{h}(s,a;\widetilde{p}^{m},\widehat{r})=Q^{\pi^{m}}_{h}(s,a;p^{m},r),$
(46)

therefore, it suffices to show that

$\displaystyle Q^{\pi^{E}}_{h}(s,a^{E};p,r)\geq
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r}).$

By using again the definition of $\widehat{r}$ for
$(s,a,h)\in\mathcal{Z}^{p,\pi^{E}}$, we know that:

$\displaystyle
Q^{\pi^{E}}_{h}(s,a^{E};\widetilde{p}^{M},\widehat{r})=Q^{\pi^{E}}_{h}(s,a^{E};p,r)+\min\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-\min\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r),$
(47)

therefore, if we show that

$\displaystyle\min\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\leq\min\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r),$

then we are done. We do it by induction. At stage $H-1$, we have that:

$\displaystyle\min\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{H}(s^{\prime};\widetilde{p}^{m},\widehat{r})$
$\displaystyle=\min\limits_{s^{\prime}\in\mathcal{S}}\operatorname*{\mathbb{E}}\limits_{a^{\prime}\sim\widetilde{\pi}^{m}_{H}(\cdot|s^{\prime})}\widehat{r}_{H}(s^{\prime},a^{\prime})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\min\limits_{s^{\prime}\in\mathcal{S}}\operatorname*{\mathbb{E}}\limits_{a^{\prime}\sim\pi^{m}_{H}(\cdot|s^{\prime})}r_{H}(s^{\prime},a^{\prime})$
$\displaystyle=\min\limits_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{H}(s^{\prime};p^{m},r),$

where at (1) we have used the definition of $\widehat{r}$ at stage $H$, and
also the definitions of $\widetilde{\pi}^{m}$ and $\pi^{m}$. We make the
inductive hypothesis that, at stage $h+1$, it holds that
$\min_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+2}(s^{\prime};\widetilde{p}^{m},\widehat{r})\leq\min_{s^{\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+2}(s^{\prime};p^{m},r)$,
and we consider stage $h$:

$\displaystyle\min\limits_{s^{\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\min\Bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r}),\min\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{m},\widehat{r})\Bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\min\Bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widetilde{p}^{M}},\widehat{r}),\min\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{m},\widehat{r})\Bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}\min\Bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r}),\min\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{m},\widehat{r})\Bigr{\\}}$
$\displaystyle=\min\Bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r),$
$\displaystyle\qquad\min\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\bigl{\\{}\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\in\mathcal{Z}^{p,\pi^{b}}}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{m},\widehat{r}),\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{\\}}\Bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{=}\min\Bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r),$
$\displaystyle\qquad\min\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\bigl{\\{}\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\in\mathcal{Z}^{p,\pi^{b}}}Q^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{m}}}_{h+1}(s^{\prime},a^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{m}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r}),$
$\displaystyle\qquad\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}\widehat{r}_{h+1}(s^{\prime},a^{\prime})+\min\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\bigr{\\}}\Bigr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{\leq}\min\Bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r),$
$\displaystyle\qquad\min\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\bigl{\\{}\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\in\mathcal{Z}^{p,\pi^{b}}}Q^{\pi^{m}}_{h+1}(s^{\prime},a^{\prime};p^{m},r),$
$\displaystyle\qquad\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r}_{h+1}(s^{\prime},a^{\prime})+\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+2}(s^{\prime\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p^{m}},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}r})\bigr{\\}}\Bigr{\\}}$
$\displaystyle=\min\Bigl{\\{}\min\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r),$