$\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),\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=\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),\min\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=\min\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. 47, at (4) we use Eq. 46 and the Bellman’s
equation, at (5) we use the definition of $r$ and the inductive hypothesis.

This concludes the proof. ∎

####  F.4.1 Lemmas for Theorem F.18

We can exploit Lemma F.12 to bound the error for the subset.

######  Lemma F.14 (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)+4H^{4}\max\limits_{(s,h)\in\mathcal{S}^{p,\pi^{E}}}b_{h}(s,a^{E}).$

###### Proof.

We can write:

$\displaystyle\begin{split}\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widetilde{\mathcal{R}}^{\cap})&\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})\\}\\\
&\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})\\\
&\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}\biggl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\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{|}\biggr{)}\\\
&\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}\biggl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}+\underbrace{\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}\bigl{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}}_{=0}\biggr{)}\\\
&=\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{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}\end{split}$
(48)

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

In the following, it is useful to denote, for any $h\in\llbracket
H\rrbracket$:

$\displaystyle
X_{h}\coloneqq\max\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)\bigr{|}.$

Let us consider any $(s,h)\in\mathcal{S}^{p,\pi^{E}}$. The difference between
the rewards of expert’s action can be bounded by:

$\displaystyle\bigl{|}\widehat{r}_{h}(s,a^{E})-r_{h}(s,a^{E})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\leq}\bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim\widetilde{p}^{m}_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\qquad+\bigl{|}\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)\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim\widetilde{p}^{m}_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\pm\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}$
$\displaystyle\qquad+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\max\limits_{s^{\prime}\in\mathcal{S}}}\bigl{|}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}MH\bigl{|}\bigl{|}p_{h}(\cdot|s,a^{E})-\widetilde{p}^{m}_{h}(\cdot|s,a^{E})\bigr{|}\bigr{|}_{1}+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}\bigl{|}V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}+X_{h}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}2MHb_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}\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{|}+X_{h}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{=}2MHb_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}\bigl{|}\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+2}(s^{\prime\prime};p^{M},r)-\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}+X_{h}$
$\displaystyle\leq
2MHb_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}\bigl{[}X_{h+1}\bigr{]}+X_{h}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(6)}}}{=}2MHb_{h}(s,a^{E})+X_{h}+X_{h+1},$

where at (1) we use the definition of $\widehat{r}$ in Lemma F.12 and triangle
inequality, at (2) we use that, for any pair $f,g$ of real-valued functions,
it holds that $|\max_{x}f(x)-\max_{x}g(x)|\leq\max_{x}|f(x)-g(x)|$, at (3) we
apply triangle inequality twice, we recognize the definition of $X_{h}$, we
upper bound the value function by $MH$, and we recognize the definition of
$\ell_{1}$ norm, at (4) we first use triangle inequality
$\|p_{h}(\cdot|s,a^{E})-\widetilde{p}^{m}_{h}(\cdot|s,a^{E})\|_{1}\leq\|p_{h}(\cdot|s,a^{E})-\widehat{p}_{h}(\cdot|s,a^{E})\|_{1}+\|\widetilde{p}^{m}_{h}(\cdot|s,a^{E})-\widehat{p}_{h}(\cdot|s,a^{E})\|_{1}$,
then we use Pinsker’s inequality, event $\mathcal{E}_{3}$ from Lemma F.2, and
the definition of $b_{h}(s,a^{E})$; at (5) we use the definition of
$\widehat{r}$ in Lemma F.12 in the form of Eq. 45, by noticing that the
support of $p_{h}(\cdot|s,a^{E})$ is contained in $\mathcal{S}^{p,\pi^{E}}$,
and at (6) we realize that $X_{h+1}$ depends only on $h$ and not on
$s^{\prime}$.

In order to upper bound the term $X_{h}$, we write:

$\displaystyle X_{h}$
$\displaystyle\coloneqq\max\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\max\biggl{\\{}\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{M},\widehat{r})-\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r)\Bigr{|},$
$\displaystyle\qquad\qquad\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}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})-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)\Bigr{|}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\max\biggl{\\{}\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\max\limits_{a^{\prime}\in\mathcal{A}}}\Bigl{|}Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{M},\widehat{r})-Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r)\Bigr{|},$
$\displaystyle\qquad\qquad\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)\pm
Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})\Bigr{|}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{=}\max\biggl{\\{}\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}}}\Bigl{|}\underbrace{Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{M},\widehat{r})-Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r)}_{=0}\Bigr{|},$
$\displaystyle\qquad\qquad\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}\Bigl{|}Q^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{M},\widehat{r})-Q^{\pi^{M}}_{h+1}(s^{\prime},a^{\prime};p^{M},r)\Bigr{|}\Bigr{\\}},$
$\displaystyle\qquad\qquad\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})+\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})-\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+2}(s^{\prime};p^{M},r)\Bigr{|}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}\max\biggl{\\{}\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}\Bigl{|}\underbrace{\widehat{r}_{h+1}(s^{\prime},a^{\prime})-r_{h+1}(s^{\prime},a^{\prime})}_{=0}+\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{M}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})-\max\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\pi^{M}}_{h+2}(s^{\prime\prime};p^{M},r)\Bigr{|},$
$\displaystyle\qquad\qquad\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})\Bigr{|}+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X_{h+1}}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{\leq}\max\biggl{\\{}X_{h+1},\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{(}\Bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{M}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})-\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\Bigr{|}+X_{h+1}\Bigr{)}\biggr{\\}}$
$\displaystyle=X_{h+1}+\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{M}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})-\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\pm\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\Bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(6)}}}{\leq}X_{h+1}+\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\biggl{(}MH\Bigl{\|}\widetilde{p}^{M}_{h+1}(\cdot|s^{\prime},a^{E})-\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})\Bigr{\|}_{1}+\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}\Bigl{|}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})-V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\Bigr{|}\biggr{)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(7)}}}{\leq}X_{h+1}+\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\biggl{(}2MHb_{h+1}(s^{\prime},a^{E})$
$\displaystyle\qquad\qquad+\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}\Bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime\prime}\sim\widetilde{p}^{M}_{h+2}(\cdot|s^{\prime\prime},a^{E})}V^{\pi^{E}}_{h+3}(s^{\prime\prime\prime};\widetilde{p}^{M},\widehat{r})-\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime\prime}\sim\widetilde{p}^{m}_{h+2}(\cdot|s^{\prime\prime},a^{E})}V^{\pi^{E}}_{h+3}(s^{\prime\prime\prime};\widetilde{p}^{m},\widehat{r})\Bigr{|}\biggr{)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(8)}}}{\leq}X_{h+1}+2MH\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\sum\limits_{h^{\prime}\in\llbracket
h+1,H-1\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{\widetilde{p}^{m},\pi^{E}}_{h^{\prime}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(9)}}}{\leq}2MH\sum\limits_{h^{\prime}\in\llbracket
h,H-1\rrbracket}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h^{\prime}+1}}\sum\limits_{h^{\prime\prime}\in\llbracket
h^{\prime}+1,H-1\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{\widetilde{p}^{m},\pi^{E}}_{h^{\prime\prime}}(\cdot|s_{h^{\prime}+1}=s^{\prime})}b_{h^{\prime\prime}}(s^{\prime\prime},a^{E})$
$\displaystyle\leq
2MH^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}),$

where at (1) we apply the Bellman’s equation and the definition of
$\widetilde{\pi}^{M}$ and $\pi^{M}$, at (2) we use that
$|\max_{x}f(x)-\max_{x}g(x)|\leq\max_{x}|f(x)-g(x)|$, at (3) we use the
definition of $\widehat{r}$ in the form of Eq. 44 and Eq.45, at (4) we apply
the Bellman’s equation and the definition of $\widehat{r}$ to recognize that
$\widehat{r}_{h+1}(s^{\prime},a^{\prime})-r_{h+1}(s^{\prime},a^{\prime})=0$;
moreover, we apply triangle inequality along with the usual bound
$|\max_{x}f(x)-\max_{x}g(x)|\leq\max_{x}|f(x)-g(x)|$, and we recognize the
definition of $X_{h+1}$. At (5) we proceed similarly as (4) and we use the
Bellman optimality equation, and we observe that $X_{h+1}$ does not depend on
$s^{\prime}$; at (6) we upper bound the value function by $HM$ and recognize
the $\ell_{1}$-norm, at (7) we use the concentration bound of event
$\mathcal{E}_{3}$ in Lemma F.2 (both $\widetilde{p}^{M}$ and
$\widetilde{p}^{m}$ lie at a “distance” of $b$ from $\widehat{p}$). At (8) we
have unfolded the recursion to bound the difference of value functions between
transition models $\widetilde{p}^{m}$ and $\widetilde{p}^{M}$, at (9) we have
unfolded the recursion on the $X$ terms.

Thanks to this expression, we can upper bound the difference of rewards in
expert’s action as:

$\displaystyle\bigl{|}\widehat{r}_{h}(s,a^{E})-r_{h}(s,a^{E})\bigr{|}$
$\displaystyle\leq
2MHb_{h}(s,a^{E})+4MH^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}).$

With regards to visited
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\setminus\mathcal{Z}^{p,\pi^{E}}$, we can
write:

$\displaystyle\bigl{|}\widehat{r}_{h}(s,a)-r_{h}(s,a)\bigr{|}$
$\displaystyle=\bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim\widetilde{p}^{M}_{h}(\cdot|s,a)}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a)}V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)\bigr{|}$
$\displaystyle\leq
2MHb_{h}(s,a)+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim\widetilde{p}^{M}_{h}(\cdot|s,a)}\Bigl{|}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)\Bigr{|}$
$\displaystyle\leq
2MHb_{h}(s,a)+\max\limits_{s^{\prime}\in\mathcal{S}}\Bigl{|}V^{\widetilde{\pi}^{M}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})-V^{\pi^{M}}_{h+1}(s^{\prime};p^{M},r)\Bigr{|}$
$\displaystyle=2MHb_{h}(s,a)+X_{h}$ $\displaystyle\leq
2MHb_{h}(s,a)+2MH^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})$
$\displaystyle\leq
2MHb_{h}(s,a)+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}MH^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}).$

Obviously, for $(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$, we have:

$\displaystyle\bigl{|}\widehat{r}_{h}(s,a)-r_{h}(s,a)\bigr{|}$
$\displaystyle=0.$

Therefore, by Eq. 48, we can write:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cap},\widetilde{\mathcal{R}}^{\cap})$
$\displaystyle\leq\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{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\biggl{(}2Hb_{h}(s,a)+4H^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{)}$
$\displaystyle=2H\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)+4H^{3}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})$
$\displaystyle=2H\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)+4H^{3}\sum\limits_{h\in\llbracket
H\rrbracket}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})$
$\displaystyle=2H\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)+4H^{4}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}).$

This concludes the proof w.r.t. the subset. ∎

Now we can exploit Lemma F.13 to bound the error for the superset.

######  Lemma F.15 (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)+4H^{4}\max\limits_{(s,h)\in\mathcal{S}^{p,\pi^{E}}}b_{h}(s,a^{E}).$

###### Proof.

We can write:

$\displaystyle\begin{split}\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cup},\widetilde{\mathcal{R}}^{\cup})&\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})\\}\\\
&\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})\\\
&\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}\biggl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\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{|}\biggr{)}\\\
&\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}\biggl{(}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}+\underbrace{\max\limits_{(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}}\bigl{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}}_{=0}\biggr{)}\\\
&=\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\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{|}r_{h}(s,a)-\widetilde{r}_{h}(s,a)\bigr{|}\end{split}$
(49)

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

In the following, it is useful to denote, for any $h\in\llbracket
H\rrbracket$:

$\displaystyle
Y_{h}\coloneqq\max\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)\bigr{|}.$

Let us consider any $(s,h)\in\mathcal{S}^{p,\pi^{E}}$. The difference between
the rewards of expert’s action can be bounded by:

$\displaystyle\bigl{|}\widehat{r}_{h}(s,a^{E})-r_{h}(s,a^{E})\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\leq}\bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim\widetilde{p}^{M}_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\qquad+\bigl{|}\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)\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim\widetilde{p}^{M}_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\pm\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}$
$\displaystyle\qquad+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\max\limits_{s^{\prime}\in\mathcal{S}}}\bigl{|}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}MH\bigl{|}\bigl{|}p_{h}(\cdot|s,a^{E})-\widetilde{p}^{M}_{h}(\cdot|s,a^{E})\bigr{|}\bigr{|}_{1}+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}\bigl{|}V^{\pi^{E}}_{h+1}(s^{\prime};p,r)-V^{\pi^{E}}_{h+1}(s^{\prime};\widetilde{p}^{M},\widehat{r})\bigr{|}+Y_{h}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}2MHb_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}\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{|}+Y_{h}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{=}2MHb_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}\bigl{|}\min\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+2}(s^{\prime\prime};p^{m},r)-\min\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\bigr{|}+Y_{h}$
$\displaystyle\leq
2MHb_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}\bigl{[}Y_{h+1}\bigr{]}+Y_{h}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(6)}}}{=}2MHb_{h}(s,a^{E})+Y_{h}+Y_{h+1},$

where at (1) we use the definition of $r$ in Lemma F.13 and triangle
inequality, at (2) we use that, for any pair $f,g$ of real-valued functions,
it holds that $|\min_{x}f(x)-\min_{x}g(x)|\leq\max_{x}|f(x)-g(x)|$, at (3) we
apply triangle inequality twice, we recognize the definition of $X_{h}$, we
upper bound the value function by $MH$, and we recognize the definition of
$\ell_{1}$ norm, at (4) we first use triangle inequality
$\|p_{h}(\cdot|s,a^{E})-\widetilde{p}^{M}_{h}(\cdot|s,a^{E})\|_{1}\leq\|p_{h}(\cdot|s,a^{E})-\widehat{p}_{h}(\cdot|s,a^{E})\|_{1}+\|\widetilde{p}^{M}_{h}(\cdot|s,a^{E})-\widehat{p}_{h}(\cdot|s,a^{E})\|_{1}$,
then we use Pinsker’s inequality, event $\mathcal{E}_{3}$ from Lemma F.2, and
the definition of $b_{h}(s,a^{E})$; at (5) we use the definition of
$\widehat{r}$ in Lemma F.13 in the form of Eq. 47, by noticing that the
support of $p_{h}(\cdot|s,a^{E})$ is contained in $\mathcal{S}^{p,\pi^{E}}$,
and at (6) we realize that $Y_{h+1}$ depends only on $h$ and not on
$s^{\prime}$.

In order to upper bound the term $Y_{h}$, we write:

$\displaystyle Y_{h}$
$\displaystyle\coloneqq\max\limits_{s^{\prime}\in\mathcal{S}}\bigl{|}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)\bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}\max\biggl{\\{}\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{m},\widehat{r})-\max\limits_{a^{\prime}\in\mathcal{A}}Q^{\pi^{m}}_{h+1}(s^{\prime},a^{\prime};p^{m},r)\Bigr{|},$
$\displaystyle\qquad\qquad\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}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})-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)\Bigr{|}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\max\biggl{\\{}\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\max\limits_{a^{\prime}\in\mathcal{A}}}\Bigl{|}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{m},\widehat{r})-Q^{\pi^{m}}_{h+1}(s^{\prime},a^{\prime};p^{m},r)\Bigr{|},$
$\displaystyle\qquad\qquad\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};p,r)\pm
Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})\Bigr{|}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{=}\max\biggl{\\{}\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}}}\Bigl{|}\underbrace{Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{m},\widehat{r})-Q^{\pi^{m}}_{h+1}(s^{\prime},a^{\prime};p^{m},r)}_{=0}\Bigr{|},$
$\displaystyle\qquad\qquad\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}\Bigl{|}Q^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime},a^{\prime};\widetilde{p}^{m},\widehat{r})-Q^{\pi^{m}}_{h+1}(s^{\prime},a^{\prime};p^{m},r)\Bigr{|}\Bigr{\\}},$
$\displaystyle\qquad\qquad\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})+\min\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})-\min\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+2}(s^{\prime};p^{m},r)\Bigr{|}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}\max\biggl{\\{}\max\limits_{s^{\prime}\notin\mathcal{S}^{p,\pi^{E}}_{h+1}}\max\limits_{a^{\prime}\in\mathcal{A}:(s^{\prime},a^{\prime},h+1)\notin\mathcal{Z}^{p,\pi^{b}}}\Bigl{|}\underbrace{\widehat{r}_{h+1}(s^{\prime},a^{\prime})-r_{h+1}(s^{\prime},a^{\prime})}_{=0}+\min\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\widetilde{\pi}^{m}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})-\min\limits_{s^{\prime\prime}\in\mathcal{S}}V^{\pi^{m}}_{h+2}(s^{\prime\prime};p^{m},r)\Bigr{|},$
$\displaystyle\qquad\qquad\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{M},\widehat{r})-Q^{\pi^{E}}_{h+1}(s^{\prime},a^{E};\widetilde{p}^{m},\widehat{r})\Bigr{|}+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y_{h+1}}\biggr{\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{\leq}\max\biggl{\\{}Y_{h+1},\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{(}\Bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{M}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})-\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\Bigr{|}+Y_{h+1}\Bigr{)}\biggr{\\}}$
$\displaystyle=Y_{h+1}+\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\Bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{M}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})-\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\pm\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})\Bigr{|}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(6)}}}{\leq}Y_{h+1}+\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\biggl{(}MH\Bigl{\|}\widetilde{p}^{M}_{h+1}(\cdot|s^{\prime},a^{E})-\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})\Bigr{\|}_{1}+\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}\Bigl{|}V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{M},\widehat{r})-V^{\pi^{E}}_{h+2}(s^{\prime\prime};\widetilde{p}^{m},\widehat{r})\Bigr{|}\biggr{)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(7)}}}{\leq}Y_{h+1}+\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\biggl{(}2MHb_{h+1}(s^{\prime},a^{E})$
$\displaystyle\qquad\qquad+\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\widetilde{p}^{m}_{h+1}(\cdot|s^{\prime},a^{E})}\Bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime\prime}\sim\widetilde{p}^{M}_{h+2}(\cdot|s^{\prime\prime},a^{E})}V^{\pi^{E}}_{h+3}(s^{\prime\prime\prime};\widetilde{p}^{M},\widehat{r})-\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime\prime}\sim\widetilde{p}^{m}_{h+2}(\cdot|s^{\prime\prime},a^{E})}V^{\pi^{E}}_{h+3}(s^{\prime\prime\prime};\widetilde{p}^{m},\widehat{r})\Bigr{|}\biggr{)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(8)}}}{\leq}Y_{h+1}+2MH\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h+1}}\sum\limits_{h^{\prime}\in\llbracket
h+1,H-1\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{\widetilde{p}^{m},\pi^{E}}_{h^{\prime}}(\cdot|s_{h+1}=s^{\prime})}b_{h^{\prime}}(s^{\prime\prime},a^{E})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(9)}}}{\leq}2MH\sum\limits_{h^{\prime}\in\llbracket
h,H-1\rrbracket}\max\limits_{s^{\prime}\in\mathcal{S}^{p,\pi^{E}}_{h^{\prime}+1}}\sum\limits_{h^{\prime\prime}\in\llbracket
h^{\prime}+1,H-1\rrbracket}\operatorname*{\mathbb{E}}\limits_{s^{\prime\prime}\sim\rho^{\widetilde{p}^{m},\pi^{E}}_{h^{\prime\prime}}(\cdot|s_{h^{\prime}+1}=s^{\prime})}b_{h^{\prime\prime}}(s^{\prime\prime},a^{E})$
$\displaystyle\leq
2MH^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}),$

where at (1) we apply the Bellman’s equation and the definition of
$\widetilde{\pi}^{m}$ and $\pi^{m}$, at (2) we use that
$|\min_{x}f(x)-\min_{x}g(x)|\leq\max_{x}|f(x)-g(x)|$, at (3) we use the
definition of $r$ in the form of Eq. 46 and Eq.47, at (4) we apply the
Bellman’s equation and the definition of $r$ to recognize that
$r_{h+1}(s^{\prime},a^{\prime})-\widehat{r}_{h+1}(s^{\prime},a^{\prime})=0$;
moreover, we apply triangle inequality along with the usual bound
$|\min_{x}f(x)-\min_{x}g(x)|\leq\max_{x}|f(x)-g(x)|$, and we recognize the
definition of $X_{h+1}$. At (5) we proceed similarly as (4) and we use the
Bellman’s equation, and we observe that $Y_{h+1}$ does not depend on
$s^{\prime}$; at (6) we upper bound the value function by $HM$ and recognize
the $\ell_{1}$-norm, at (7) we use the concentration bound of event
$\mathcal{E}_{3}$ in Lemma F.2 (both $\widetilde{p}^{M}$ and
$\widetilde{p}^{m}$ lie at a “distance” of $b$ from $\widehat{p}$). At (8) we
have unfolded the recursion to bound the difference of value functions between
transition models $\widetilde{p}^{m}$ and $\widetilde{p}^{M}$, at (9) we have
unfolded the recursion on the $Y$ terms.

Thanks to this expression, we can upper bound the difference of rewards in
expert’s action as:

$\displaystyle\bigl{|}\widehat{r}_{h}(s,a^{E})-r_{h}(s,a^{E})\bigr{|}$
$\displaystyle\leq
2MHb_{h}(s,a^{E})+4MH^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}).$

With regards to visited
$(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\setminus\mathcal{Z}^{p,\pi^{E}}$, we can
write:

$\displaystyle\bigl{|}\widehat{r}_{h}(s,a)-r_{h}(s,a)\bigr{|}$
$\displaystyle=\bigl{|}\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim\widetilde{p}^{m}_{h}(\cdot|s,a)}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a)}V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)\bigr{|}$
$\displaystyle\leq
2MHb_{h}(s,a)+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim\widetilde{p}^{m}_{h}(\cdot|s,a)}\Bigl{|}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)\Bigr{|}$
$\displaystyle\leq
2MHb_{h}(s,a)+\max\limits_{s^{\prime}\in\mathcal{S}}\Bigl{|}V^{\widetilde{\pi}^{m}}_{h+1}(s^{\prime};\widetilde{p}^{m},\widehat{r})-V^{\pi^{m}}_{h+1}(s^{\prime};p^{m},r)\Bigr{|}$
$\displaystyle=2MHb_{h}(s,a)+Y_{h}$ $\displaystyle\leq
2MHb_{h}(s,a)+2MH^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})$
$\displaystyle\leq
2MHb_{h}(s,a)+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}MH^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}).$

Obviously, for $(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$, we have:

$\displaystyle\bigl{|}\widehat{r}_{h}(s,a)-r_{h}(s,a)\bigr{|}$
$\displaystyle=0.$

Therefore, by Eq. 49, we can write:

$\displaystyle\mathcal{H}_{d}(\mathcal{R}_{p,\pi^{E}}^{\cup},\widetilde{\mathcal{R}}^{\cup})$
$\displaystyle\leq\sup\limits_{\widetilde{r}\in\widetilde{\mathcal{R}}^{\cup}}\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{|}r_{h}(s,a)-\widehat{r}_{h}(s,a)\bigr{|}$
$\displaystyle\leq\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\biggl{(}2Hb_{h}(s,a)+4H^{3}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})\biggr{)}$
$\displaystyle=2H\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)+4H^{3}\sum\limits_{h\in\llbracket
H\rrbracket}\operatorname*{\mathbb{E}}\limits_{(s,a)\sim\rho_{h}^{p,\pi^{b}}(\cdot,\cdot)}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})$
$\displaystyle=2H\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)+4H^{3}\sum\limits_{h\in\llbracket
H\rrbracket}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E})$
$\displaystyle=2H\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)+4H^{4}\max\limits_{(s^{\prime},h^{\prime})\in\mathcal{S}^{p,\pi^{E}}}b_{h^{\prime}}(s^{\prime},a^{E}).$

This concludes the proof w.r.t. the superset. ∎

####  F.4.2 Lemmas for Theorem F.19

######  Lemma F.16 (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^{4}\max\limits_{(s,h)\in\mathcal{S}^{p,\pi^{E}}}b_{h}(s,a^{E}).$

###### Proof Sketch.

The proof is analogous to that of Lemma F.14. We can reuse the bounds for the
difference between rewards proved in there and insert them into
$\mathcal{H}_{\infty}$ to get the result. ∎

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

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^{4}\max\limits_{(s,h)\in\mathcal{S}^{p,\pi^{E}}}b_{h}(s,a^{E}).$

###### Proof Sketch.

The proof is analogous to that of Lemma F.15. We can reuse the bounds for the
difference between rewards proved in there and insert them into
$\mathcal{H}_{\infty}$ to get the result. ∎

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

Thanks to Lemma F.14 and Lemma F.15, we can conclude the proof of the main
theorem for $d$.

######  Theorem F.18.

Under the conditions of Theorem 6.1, PIRLO is $(\epsilon,\delta)$-PAC for
$d$-IRL with a sample complexity at most:

$\displaystyle\tau^{b}$
$\displaystyle\leq\widetilde{\mathcal{O}}\Biggl{(}\frac{H^{3}Z^{p,\pi^{b}}\ln\frac{1}{\delta}}{\epsilon^{2}}\biggl{(}\ln\frac{1}{\delta}+S_{\max}^{p,\pi^{b}}\biggr{)}$
$\displaystyle+\frac{H^{8}\ln\frac{1}{\delta}}{\rho_{\min}^{\pi^{b},\mathcal{Z}^{p,\pi^{E}}}\epsilon^{2}}\biggl{(}\ln\frac{1}{\delta}+S_{\max}^{p,\pi^{b}}\biggr{)}+\frac{\ln\frac{1}{\delta}}{\ln\frac{1}{1-\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}}\Biggr{)},$

and $\tau^{E}$ is bounded as in Theorem 5.1. Furthermore, PIRLO is inclusion
monotonic.

###### Proof Sketch.

The proof for the subset and superset is completely analogous. Thanks to Lemma
F.14 and Lemma F.15, we realize that we have to bound the sum of two terms,
which are completely analogous to those in the proof of Theorem 6.1, with the
only difference of $H^{4}$ instead of $H^{3}$. By proceeding similarly, we get
the result. ∎

Thanks to Lemma F.16 and Lemma F.17, we can conclude the proof of the main
theorem for $d_{\infty}$.

######  Theorem F.19.

Under the conditions of Theorem 6.1, PIRLO is $(\epsilon,\delta)$-PAC for
$d_{\infty}$-IRL with a sample complexity at most:

$\displaystyle\tau^{b}$
$\displaystyle\leq\widetilde{\mathcal{O}}\Bigg{(}\frac{H^{4}\ln\frac{1}{\delta}}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}\epsilon^{2}}\biggl{(}\ln\frac{1}{\delta}+S^{p,\pi^{b}}_{\max}\biggr{)}$
$\displaystyle+\frac{H^{8}\ln\frac{1}{\delta}}{\rho_{\min}^{\pi^{b},\mathcal{Z}^{p,\pi^{E}}}\epsilon^{2}}\biggl{(}\ln\frac{1}{\delta}+S^{p,\pi^{b}}_{\max}\biggr{)}+\frac{\ln\frac{1}{\delta}}{\ln\frac{1}{1-\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}}\Bigg{)},$

and $\tau^{E}$ is bounded as in Theorem 5.1. Furthermore, PIRLO is inclusion
monotonic.

###### Proof Sketch.

The proof for the subset and superset is completely analogous. Thanks to Lemma
F.16 and Lemma F.17, we realize that we have to bound the sum of two terms,
which are completely analogous to those in the proof of Theorem 6.2, with the
only difference of $H^{4}$ instead of $H^{3}$. By proceeding similarly, we get
the result. ∎

###  F.5 A note on the superset without relaxation

In this section, we show that, if we use the superset definition
$\widehat{\mathcal{R}}^{\cup}$ of Eq. 8, i.e., the definition without
relaxation, then we are able to obtain the same performance decomposition
result (see Lemma F.5) that we had for the case without pessimism, and, thus,
we end up with the same sample complexity result, which is much smaller than
those computed for the relaxations. Observe that we are not able to have an
analogous result for the subset definition $\widehat{\mathcal{R}}^{\cap}$ of
Eq. 8. Indeed, differently from the relaxations defined in Eq. 6, the subset
and the superset definitions of Eq. 8 are not exactly simmetric. While
$r\in\widehat{\mathcal{R}}^{\cup}$ entails, by definition, the existence of
(at least) one transition model in $\mathcal{C}(\widehat{p},b)$ in which $r$
induces an optimal policy
$\pi^{*}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}$, this is not true for
$r^{\prime}\in\widehat{\mathcal{R}}^{\cap}$. Indeed, potentially, there might
exist a (worst)181818Worst because there is a universal quantifier $\forall$
over transition models in the definition of $\widehat{\mathcal{R}}^{\cap}$.
transition model for every
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times\llbracket H\rrbracket$.
Therefore, intuitively, in the reward choice lemma, we cannot make a choice of
a single (worst) transition model, but we have to choose many of them. This
fact “breaks” the recursion and it does not allow us to perform
$\ell_{1}$-norm bounds. Instead, since the superset is of different nature, we
can. It should be remarked that a membership checker algorithm for superset
$\widehat{\mathcal{R}}^{\cup}$ is inefficient to implement in practice because
it requires to solve a bilinear optimization problem (see Appendix G).

We will denote by $\widehat{\mathcal{R}}^{\cup}$ the superset definition of
Eq. 8.

######  Lemma F.20 (Reward Choice).

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

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

where $\widecheck{p}$ is some transition model in
$\mathcal{C}(\widehat{p},b)$, belongs to $\mathcal{R}_{p,\pi^{E}}^{\cup}$.

###### Proof.

By definition of $\widehat{\mathcal{R}}^{\cup}$, we have that
$\widehat{r}\in\widehat{\mathcal{R}}^{\cup}$ if and only if there exists a
transition model $\bar{p}\in\mathcal{C}(\widehat{p},b)$ such that
$\widehat{r}\in\mathcal{R}^{\cup}_{\bar{p},\pi^{E}}$. Let us construct $r$ by
choosing $\widecheck{p}=\bar{p}$. To show that
$r\in\mathcal{R}_{p,\pi^{E}}^{\cup}$, we are going to show that the transition
model $\widetilde{p}$ defined as:

$\displaystyle\begin{cases}\widetilde{p}_{h}(\cdot|s,a)=p_{h}(\cdot|s,a),\quad\forall(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}\\\
\widetilde{p}_{h}(\cdot|s,a)=\bar{p}_{h}(\cdot|s,a),\quad\forall(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}\\\
\end{cases},$

belongs to $[p]_{\equiv_{\mathcal{Z}^{p,\pi^{b}}}}$ and is such that, for all
$(s,h)\in\mathcal{S}^{p,\pi^{E}}$, for all
$a\in\mathcal{A}\setminus\\{a^{E}\\}$:

$\displaystyle Q^{*}_{h}(s,a;\widetilde{p},r)\leq
Q^{*}_{h}(s,a^{E};\widetilde{p},r).$

Then, by Lemma E.1, we can conclude that $r\in\mathcal{R}_{p,\pi^{E}}^{\cup}$.

Trivially, notice that $\widetilde{p}\equiv_{\mathcal{Z}^{p,\pi^{b}}}p$. We
proceed by induction to show that, for all
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times\llbracket H\rrbracket$, the
following identity holds:

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

Then, since $\widehat{r}\in\widehat{\mathcal{R}}^{\cup}$, for all
$(s,h)\in\mathcal{S}^{p,\pi^{E}}$ and for all
$a\in\mathcal{A}\setminus\\{a^{E}\\}$, the inequality
$Q^{*}_{h}(s,a;\bar{p},\widehat{r})\leq
Q^{*}_{h}(s,a^{E};\bar{p},\widehat{r})$ (Lemma E.1) entails
$Q^{*}_{h}(s,a;\widetilde{p},r)\leq Q^{*}_{h}(s,a^{E};\widetilde{p},r)$, and
the thesis follows.

As case base, consider stage $H$. For any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, thanks to the definition of $r$, we
can write:

$\displaystyle Q^{*}_{H}(s,a;\widetilde{p},r)$ $\displaystyle=r_{H}(s,a)$
$\displaystyle=\widehat{r}_{H}(s,a)$
$\displaystyle=Q^{*}_{H}(s,a;\bar{p},\widehat{r}).$

Now, make the inductive hypothesis that for all
$(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}$, it holds that
$Q^{*}_{h+1}(s^{\prime},a^{\prime};\widetilde{p},r)=Q^{*}_{h+1}(s^{\prime},a^{\prime};\bar{p},\widehat{r})$,
and consider stage $h$. For any $(s,a)\in\mathcal{Z}^{p,\pi^{b}}_{h}$, we can
write:

$\displaystyle Q^{*}_{h}(s,a;\widetilde{p},r)$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}_{h}(s^{\prime}|s,a)\max\limits_{a^{\prime}\in\mathcal{A}}Q^{*}_{h+1}(s^{\prime},a^{\prime};\widetilde{p},r)$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{=}r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}_{h}(s^{\prime}|s,a)\max\limits_{a^{\prime}\in\mathcal{A}}Q^{*}_{h+1}(s^{\prime},a^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bar{p},\widehat{r}})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{=}\widehat{r}_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}(\widecheck{p}_{h}(s^{\prime}|s,a)-p_{h}(s^{\prime}|s,a))\max\limits_{a^{\prime}\in\mathcal{A}}Q^{*}_{h+1}(s^{\prime},a^{\prime};\widecheck{p},\widehat{r})+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}_{h}(s^{\prime}|s,a)\max\limits_{a^{\prime}\in\mathcal{A}}Q^{*}_{h+1}(s^{\prime},a^{\prime};\bar{p},\widehat{r})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{=}\widehat{r}_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bar{p}}_{h}(s^{\prime}|s,a)\max\limits_{a^{\prime}\in\mathcal{A}}Q^{*}_{h+1}(s^{\prime},a^{\prime};\bar{p},\widehat{r})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{=}Q^{*}_{h}(s,a;\bar{p},\widehat{r}),$

where at (1) we have applied the Bellman’s optimality equation, at (2) we have
used the inductive hypothesis, at (3) we have inserted the definition of
$r_{h}(s,a)$ along with the fact that $(s,a,h)\in\mathcal{Z}^{p,\pi^{b}}$, at
(4) we have noticed that $\widecheck{p}=\bar{p}$ (by choice) and that
$\widetilde{p}_{h}(\cdot|s,a)=p_{h}(\cdot|s,a)$ (by definition); finally, at
(5), we have applied again the Bellman’s optimality equation.

On the other side, for any $(s,a)\notin\mathcal{Z}^{p,\pi^{b}}_{h}$, we can
write:

$\displaystyle Q^{*}_{h}(s,a;\widetilde{p},r)$
$\displaystyle=r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}_{h}(s^{\prime}|s,a)\max\limits_{a^{\prime}\in\mathcal{A}}Q^{*}_{h+1}(s^{\prime},a^{\prime};\widetilde{p},r)$
$\displaystyle=r_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}\widetilde{p}_{h}(s^{\prime}|s,a)\max\limits_{a^{\prime}\in\mathcal{A}}Q^{*}_{h+1}(s^{\prime},a^{\prime};{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bar{p},\widehat{r}})$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{=}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\widehat{r}}_{h}(s,a)+\sum\limits_{s^{\prime}\in\mathcal{S}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bar{p}}_{h}(s^{\prime}|s,a)\max\limits_{a^{\prime}\in\mathcal{A}}Q^{*}_{h+1}(s^{\prime},a^{\prime};\bar{p},\widehat{r})$
$\displaystyle=Q^{*}_{h}(s,a;\bar{p},\widehat{r}),$

where at (1) we have used both the definition of $r_{h}(s,a)$ and that
$\widetilde{p}_{h}(\cdot|s,a)=\bar{p}_{h}(\cdot|s,a)$, for
$(s,a,h)\notin\mathcal{Z}^{p,\pi^{b}}$.

This concludes the proof. ∎

Thanks to the reward choice lemma just presented, we obtain the following
sample complexity result.

######  Theorem F.21.

Let $\mathcal{M}$ be an MDP without reward and let $\pi^{E}$ be the expert’s
policy. Let $\mathcal{D}^{E}$ and $\mathcal{D}^{b}$ be two datasets of
$\tau^{E}$ and $\tau^{b}$ trajectories collected with policies $\pi^{E}$ and
$\pi^{b}$ in $\mathcal{M}$, respectively. Under Assumption 2.1, any algorithm
$\mathfrak{A}$ that outputs $\widehat{\mathcal{R}}^{\cup}$ (defined as in Eq.
8) is such that, for any $\epsilon,\delta\in(0,1)$:

$\displaystyle\mathop{\mathbb{P}}_{(p,\pi^{E},\pi^{b})}\bigl{(}\bigl{\\{}\mathcal{H}_{c}(\mathcal{R}_{p,\pi^{E}}^{\cup},\widehat{\mathcal{R}}^{\cup})\leq\epsilon\bigr{\\}}\wedge\\{\mathcal{R}_{p,\pi^{E}}^{\cup}\subseteq\widehat{\mathcal{R}}^{\cup}\\}\bigr{)}\geq
1-\delta,$

with a sample complexity at most:

$\displaystyle\tau^{b}\leq\widetilde{\mathcal{O}}\Bigg{(}\frac{H^{3}Z^{p,\pi^{b}}\ln\frac{1}{\delta}}{\epsilon^{2}}\biggl{(}\ln\frac{1}{\delta}+S^{p,\pi^{b}}_{\max}\biggr{)}+\frac{\ln\frac{1}{\delta}}{\ln\frac{1}{1-\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}}\Bigg{)},$
$\displaystyle\tau^{E}\leq\widetilde{\mathcal{O}}\Bigg{(}\frac{\ln\frac{1}{\delta}}{\ln\frac{1}{1-\rho^{\pi^{E},\mathcal{Z}^{p,\pi^{E}}}_{\min}}}\Bigg{)}.$

if $c=d$, and a sample complexity at most:

$\displaystyle\tau^{b}\leq\widetilde{\mathcal{O}}\Bigg{(}\frac{H^{4}\ln\frac{1}{\delta}}{\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}\epsilon^{2}}\biggl{(}\ln\frac{1}{\delta}+S^{p,\pi^{b}}_{\max}\biggr{)}+\frac{\ln\frac{1}{\delta}}{\ln\frac{1}{1-\rho^{\pi^{b},\mathcal{Z}^{p,\pi^{b}}}_{\min}}}\Bigg{)},$
$\displaystyle\tau^{E}\leq\widetilde{\mathcal{O}}\Bigg{(}\frac{\ln\frac{1}{\delta}}{\ln\frac{1}{1-\rho^{\pi^{E},\mathcal{Z}^{p,\pi^{E}}}_{\min}}}\Bigg{)}.$

if $c=d_{\infty}$.

###### Proof Sketch.

Observe that, thanks to Lemma F.20, we are able to obtain a performance
decomposition lemma analogous to Lemma F.5 for distance $d$ (or analogous for
distance $d_{\infty}$). Next, following the steps in the proof of Theorem 5.1
(Theorem 5.2), we obtain the result. ∎

##  Appendix G Implementation

In this appendix, we provide some comments on the implementation of membership
checker algorithms for IRLO, PIRLO, and some comments about the subset and
superset defined in Eq. 8. In Section G.1, we present the pseudocode of the
membership checker algorithms. In Section G.2, we provide more details on the
definitions of the relaxations $\widetilde{\mathcal{R}}^{\cap}$ and
$\widetilde{\mathcal{R}}^{\cup}$. In Section G.3 we show that the
implementation of a membership checker algorithm for the subset and superset
defined in Eq. 8 is inefficient. Finally, in Section G.4, we give the
intuition that a straightforward relaxation of the representation of the sets
provided by Lemma E.1 is worse than that obtained by relaxing the
representation in Theorem 3.1.

###  G.1 Algorithm

The pseudocode of the membership checker algorithms for IRLO and PIRLO is
provided in Algorithm 2.

Algorithm 2 Membership checker for IRLO and PIRLO.

Input :

Datasets $\mathcal{D}^{E}=\\{\langle
s_{h}^{E,i},a_{h}^{E,i}\rangle_{h}\\}_{i}$, $\mathcal{D}^{b}=\\{\langle
s_{h}^{b,i},a_{h}^{b,i}\rangle_{h}\\}_{i}$, candidate reward function
$r\in\mathfrak{R}$

Output :

$\mathsf{True}$ if
$r\in(\widehat{\mathcal{R}}^{\cup},\widehat{\mathcal{R}}^{\cap})$

Run lines 1-1 of Algorithm 1

Define $\mathcal{C}$ as in Eq. (6) for IRLO and as in Eq. (7) for PIRLO

Extended value iteration:
$\mathcal{A}_{h}(s)\leftarrow\text{{ if
}}(s,h)\in\widehat{\mathcal{S}}^{p,\pi^{E}}\text{{ then
}}\\{\widehat{\pi}^{E}_{h}(s)\\}\text{ {else}
}\mathcal{A},\;\forall(s,h)\in\mathcal{S}\times\llbracket H\rrbracket$

$Q_{H}^{+}(s,a),Q_{H}^{-}(s,a)\leftarrow r_{H}(s,a)$
$\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times\llbracket H\rrbracket$

for  _$h=H-1$ to $1$_ do

11 for  _$(s,a)\in\mathcal{S}\times\mathcal{A}$_ do

12 $Q_{h}^{+}(s,a)\leftarrow
r_{h}(s,a)+\max\limits_{p^{\prime}\in\mathcal{C}}\sum\limits_{s^{\prime}\in\mathcal{S}}{p}^{\prime}_{h}(s^{\prime}|s,a)\max\limits_{a^{\prime}\in\mathcal{A}_{h+1}(s)}Q_{h+1}^{+}(s^{\prime},a^{\prime})$
$Q_{h}^{-}(s,a)\leftarrow
r_{h}(s,a)+\min\limits_{p^{\prime}\in\mathcal{C}}\sum\limits_{s^{\prime}\in\mathcal{S}}{p}^{\prime}_{h}(s^{\prime}|s,a)\max\limits_{a^{\prime}\in\mathcal{A}_{h+1}(s)}Q_{h+1}^{-}(s^{\prime},a^{\prime})$

13 end for

14

15 end for

16 Membership test:
in${}^{\cup}\leftarrow\mathsf{True}$, in${}^{\cap}\leftarrow\mathsf{True}$ for
_$(s,h)\in\widehat{\mathcal{S}}^{p,\pi^{E}}$_ do

17 for  _$a\in\mathcal{A}\setminus\\{\widehat{\pi}^{E}(s)\\}$_ do

18 IRLO if  _$Q_{h}^{+}(s,\widehat{\pi}_{h}^{E}(s)) <Q_{h}^{+}(s,a)$_ then

19 in${}^{\cup}\leftarrow\mathsf{False}$

20 end if

21 if  _$Q_{h}^{-}(s,\widehat{\pi}_{h}^{E}(s)) <Q_{h}^{-}(s,a)$_ then

22 in${}^{\cap}\leftarrow\mathsf{False}$

23 end if

24 PIRLO if  _$Q_{h}^{+}(s,\widehat{\pi}_{h}^{E}(s)) <Q_{h}^{-}(s,a)$_ then

25 in${}^{\cup}\leftarrow\mathsf{False}$

26 else if  _$Q_{h}^{-}(s,\widehat{\pi}_{h}^{E}(s)) <Q_{h}^{+}(s,a)$_ then

27 in${}^{\cap}\leftarrow\mathsf{False}$

28 end if

29

30 end for

31

32 end for

return (in∪, in∩)

The idea is to find the worst (resp. best) transition model for the subset
(resp. superset) among all those feasible. In practice, what we do is to
exploit the representation provided in Eq. 22 for IRLO and the representation
provided in Eq. 27 for PIRLO.

Observe that, inside the support $(s,h)\in\widehat{\mathcal{S}}^{p,\pi^{E}}$,
we use the estimated expert’s action $\widehat{\pi}^{E}_{h}(s)$, while outside
the support we always play the action that maximizes the Q-function (both
$Q^{+}$ and $Q^{-}$). Concerning the transition model, notice that, for
$Q^{+}$, we consider the $p^{\prime}\in\mathcal{C}$ that maximizes the
expected $Q^{+}$, while for $Q^{-}$ we consider the $p^{\prime}\in\mathcal{C}$
that minimizes the expected $Q^{-}$. Observe also that, for IRLO, because of
the definition of $\mathcal{C}$, inside the support
$\widehat{\mathcal{Z}}^{p,\pi^{b}}$ we use $p^{\prime}=\widehat{p}$, and
outside the support we consider
$p^{\prime}=\operatorname*{arg\,max}_{s^{\prime}\in\mathcal{S}}$ for $Q^{+}$
and $p^{\prime}=\operatorname*{arg\,min}_{s^{\prime}\in\mathcal{S}}$ for
$Q^{-}$.

Finally, we check the Bellman optimality conditions to assess the membership
of the candidate reward $r$ in the estimated sets
$\widehat{\mathcal{R}}^{\cup}$ (boolean variable in∪) and
$\widehat{\mathcal{R}}^{\cap}$ (boolean variable in∩) (line 2).

###  G.2 A better understanding of the relaxations

To get a better understanding of why
$\widetilde{\mathcal{R}}^{\cap}\subseteq\mathcal{R}_{p,\pi^{E}}^{\cap}$ and
$\mathcal{R}_{p,\pi^{E}}^{\cup}\subseteq\widetilde{\mathcal{R}}^{\cup}$, under
the hypothesis (good event) that the true transition model
$p\in\mathcal{C}(\widehat{p},b)$ and that $\widehat{\pi}^{E}=\pi^{E}$ in all
$\mathcal{S}^{p,\pi^{E}}$, observe that, for the subset:

$\displaystyle\mathcal{R}_{p,\pi^{E}}^{\cap}$
$\displaystyle\supseteq\bigcap\limits_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}\mathcal{R}_{p^{\prime},\pi^{E}}^{\cap}$
$\displaystyle=\\{r\in\mathfrak{R}\,|\,\forall
p^{\prime}\in\mathcal{C}(\widehat{p},b),\forall\bar{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}},\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\;Q^{\pi^{E}}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)\geq
Q^{\bar{\pi}}_{h}(s,a;p^{\prime},r)\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\supseteq}\\{r\in\mathfrak{R}\,|\,\forall\bar{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}},\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\;\min_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\pi^{E}}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)\geq\max_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\bar{\pi}}_{h}(s,a;p^{\prime},r)\\}$
$\displaystyle=\\{r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\;\min_{\bar{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}}\Bigl{(}\min_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\pi^{E}}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)-\max_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\bar{\pi}}_{h}(s,a;p^{\prime},r)\Bigr{)}\geq
0\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{=}\\{r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\;\min_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\pi^{E}}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)\geq\max_{\bar{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}}\max_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\bar{\pi}}_{h}(s,a;p^{\prime},r)\\}$
$\displaystyle\eqqcolon\widetilde{\mathcal{R}}^{\cap},$

where at (1) we have exchanged the order of the quantifiers, and we can do so
because they all are of the same type, and then we have observed that
$\min_{x}(f(x)-g(x))\geq\min_{x}f(x)-\max_{x}g(x)$, and at (2) we recognize
that the first term does not depend on $\bar{\pi}$. W.r.t. the superset, in an
analogous manner, observe that:

$\displaystyle\mathcal{R}_{p,\pi^{E}}^{\cup}$
$\displaystyle\subseteq\bigcup\limits_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}\mathcal{R}_{p^{\prime},\pi^{E}}^{\cup}$
$\displaystyle=\\{r\in\mathfrak{R}\,|\,\exists
p^{\prime}\in\mathcal{C}(\widehat{p},b),\forall\bar{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}},\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\;Q^{\pi^{E}}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)\geq
Q^{\bar{\pi}}_{h}(s,a;p^{\prime},r)\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\subseteq}\\{r\in\mathfrak{R}\,|\,\forall\bar{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}},\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\;\max_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\pi^{E}}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)\geq\min_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\bar{\pi}}_{h}(s,a;p^{\prime},r)\\}$
$\displaystyle=\\{r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\;\min_{\bar{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}}\Bigl{(}\max_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\pi^{E}}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)-\min_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\bar{\pi}}_{h}(s,a;p^{\prime},r)\Bigr{)}\geq
0\\}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{=}\\{r\in\mathfrak{R}\,|\,\forall(s,h)\in\mathcal{S}^{p,\pi^{E}},\forall
a\in\mathcal{A}:\;\max_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\pi^{E}}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)\geq\max_{\bar{\pi}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}}\min_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{\bar{\pi}}_{h}(s,a;p^{\prime},r)\\}$
$\displaystyle\eqqcolon\widetilde{\mathcal{R}}^{\cup},$

where at (1) we have relaxed and at (2) we recognize that the first term does
not depend on $\bar{\pi}$.

###  G.3 Testing the membership without relaxations

We show that the problem of testing the membership to the subset and superset
defined as in Eq. 8 is equivalent to solving a bilinear optimization problem,
which is in general hard. We will denote the expert’s action by $a^{E}$ and we
use the representation provided by Lemma E.1.

Let us begin with the subset $\widehat{\mathcal{R}}^{\cap}$. A given reward
$r$ belongs to $\widehat{\mathcal{R}}^{\cap}$ if and only if:

$\displaystyle\forall
p^{\prime}\in\mathcal{C}(\widehat{p},b),\forall(s,h)\in\widehat{\mathcal{S}}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:\;Q^{*}_{h}(s,a;p^{\prime},r)\leq
Q^{*}_{h}(s,a^{E};p^{\prime},r),$

where $\mathcal{C}(\widehat{p},b)$ is defined in Eq. 7. By applying the
Bellman optimality equation, changing the order of the quantifiers, and
considering the worst possible transition model, we obtain:

$\displaystyle\forall(s,h)\in\widehat{\mathcal{S}}^{p,\pi^{E}},$
$\displaystyle\forall a\in\mathcal{A}\setminus\\{a^{E}\\}:$ $\displaystyle
r_{h}(s,a)\leq
r_{h}(s,a^{E})+\min\limits_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}\biggl{(}\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}^{\prime}(s^{\prime}|s,a^{E})V^{*}_{h+1}(s^{\prime};p^{\prime},r)-\sum\limits_{s^{\prime}\in\mathcal{S}}p_{h}^{\prime}(s^{\prime}|s,a)V^{*}_{h+1}(s^{\prime};p^{\prime},r)\biggr{)}.$

It should be remarked that, differently from IRLO and PIRLO, to check whether
a given reward $r$ belongs to $\widehat{\mathcal{R}}^{\cap}$, we cannot
optimize the value function, but we have to optimize the advantage function.
Therefore, for all $(\bar{s},\bar{h})\in\widehat{\mathcal{S}}^{p,\pi^{E}}$,
and for all $\bar{a}\in\mathcal{A}\setminus\\{a^{E}\\}$, we have to solve the
optimization problem:

$\displaystyle\min\limits_{p^{\prime}}\sum\limits_{s^{\prime}\in\mathcal{S}}\Bigl{(}p_{\bar{h}}^{\prime}(s^{\prime}|\bar{s},a^{E})-p_{\bar{h}}^{\prime}(s^{\prime}|\bar{s},\bar{a})\Bigr{)}V^{*}_{\bar{h}+1}(s^{\prime};p^{\prime},r)$
$\displaystyle\text{s.t.
}\|p_{h}^{\prime}(\cdot|s,a)-\widehat{p}_{h}(\cdot|s,a)\|_{1}\leq
b_{h}(s,a)\quad\quad\forall(s,a,h)\in\widehat{\mathcal{Z}}^{p,\pi^{b}}$
$\displaystyle\quad\quad\;p_{h}^{\prime}(\cdot|s,a)\in\Delta^{\mathcal{S}}\quad\quad\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times\llbracket
H\rrbracket$
$\displaystyle\quad\quad\;p_{h}^{\prime}(s^{\prime}|s,a)=0\quad\quad\forall(s,a,h)\in\widehat{\mathcal{Z}}^{p,\pi^{E}}\wedge
s^{\prime}\notin\big{(}\widehat{\mathcal{S}}^{p,\pi^{E}}_{h+1}\cup\text{supp
}\widehat{p}_{h}(\cdot|s,a^{E})\big{)}.$

Observe that, while the set of constraints define a convex set, the objective
involves the product of optimization variables. We can introduce $H$ variables
$\\{V_{s}\\}_{s\in\llbracket S\rrbracket}$ to replace
$V^{*}_{\bar{h}+1}(s^{\prime};p^{\prime},r)$ by adding suitable constraints
that keep into account also the presence of the maximum operator inside
$V^{*}$ (because of the Bellman’s optimality equation). In this way, due to
the product between variables $p^{\prime}$ and $V$, we can conclude that this
is a bilinear optimization problem, which is in general difficult to solve.

W.r.t. the superset, we have that a reward $r$ belongs to
$\widehat{\mathcal{R}}^{\cup}$ if and only if:

$\displaystyle\exists
p^{\prime}\in\mathcal{C}(\widehat{p},b),\forall(s,h)\in\widehat{\mathcal{S}}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}:\;Q^{*}_{h}(s,a;p^{\prime},r)\leq
Q^{*}_{h}(s,a^{E};p^{\prime},r).$

This time, we cannot bring the transition model inside because we have
different quantifiers. We can formulate the problem as a feasibility problem
by adding constraints because of the presence of
$\forall(s,h)\in\widehat{\mathcal{S}}^{p,\pi^{E}},\forall
a\in\mathcal{A}\setminus\\{a^{E}\\}$. In practice, the presence of the product
between “optimization” variables is now in the constraints, so the problem is
again a bilinear problem.

###  G.4 Relaxing the representation provided by Lemma E.1

We have seen that we can represent the feasible set by using Theorem 3.1 or
Lemma E.1. While the two representations are equivalent, observe that a
straightforward relaxation of the constraints present in Lemma E.1 provides a
different relaxation of the subset and superset w.r.t.
$\widetilde{\mathcal{R}}^{\cap}$ and $\widetilde{\mathcal{R}}^{\cup}$ (which
are obtained by relaxing the representation in Theorem 3.1). Indeed, by
relaxing the representation with the $Q^{*}$ (Lemma E.1), we would obtain
constraints of the form (ex. subset):

$\displaystyle\min_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{*}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)\geq\max_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{*}_{h}(s,a;p^{\prime},r)$
$\displaystyle\iff\quad\min_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}\max\limits_{\pi\in\Pi}Q^{\pi}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)\geq\max_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}\max\limits_{\pi\in\Pi}Q^{\pi}_{h}(s,a;p^{\prime},r).$
(50)

Clearly, this is different from $\widetilde{\mathcal{R}}^{\cap}$, whose
constraints can be written as:

$\min_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}Q^{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi^{E}}}_{h}(s,\pi_{h}^{E}(s);p^{\prime},r)\geq\max_{p^{\prime}\in\mathcal{C}(\widehat{p},b)}\max\limits_{\pi\in{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}}}Q^{\pi}_{h}(s,a;p^{\prime},r).$

Indeed, $\widetilde{\mathcal{R}}^{\cap}$ puts the additional constraint that
the $Q^{*}$ is achieved by a policy in
$[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}$, which is not present in Eq.
G.4.

An analogous reasoning can be carried out also for the superset.

##  Appendix H Proofs of Section 8

In this section, we provide the missing proofs of Section 8.

See 8.1

###### Proof.

Let $r$ be an arbitrary reward function of $\mathcal{R}_{p,\pi^{E}}^{\cap}$.
Consider a certain $(s,h)\in\mathcal{S}^{p,\pi^{E}}$, with expert’s action
$\pi^{E}_{h}(s)=a^{E}$, and let $a\in\mathcal{A}$ be a non-expert’s action. By
Lemma E.1, we know that, for any
$p^{\prime}\in[p]_{\equiv_{\mathcal{Z}^{p,\pi^{E}}}}$, it must hold:

$\displaystyle r_{h}(s,a)$ $\displaystyle\leq
r_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}^{\prime}(\cdot|s,a^{E})}V_{h+1}^{*}(s^{\prime};p^{\prime},r)-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}^{\prime}(\cdot|s,a)}V_{h+1}^{*}(s^{\prime};p^{\prime},r)$
$\displaystyle=r_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V_{h+1}^{*}(s^{\prime};p,r)-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}^{\prime}(\cdot|s,a)}V_{h+1}^{*}(s^{\prime};p^{\prime},r),$

where we have used the definition of $[p]_{\equiv_{\mathcal{Z}^{p,\pi^{E}}}}$.
Since $(s,a,h)\notin\mathcal{Z}^{p,\pi^{E}}$, then the constraint must hold
$\forall p_{h}^{\prime}(\cdot|s,a)\in\Delta^{\mathcal{S}}$. In particular, it
must hold for the transition model such that:

$\displaystyle r_{h}(s,a)\leq
r_{h}(s,a^{E})+\underbrace{\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V_{h+1}^{*}(s^{\prime};p,r)-\max\limits_{s^{\prime}\in\mathcal{S}}V_{h+1}^{*}(s^{\prime};p^{\prime},r)}_{\leq
0},$

from which the thesis follows. ∎

See 8.2

###### Proof.

Let $a^{E}\coloneqq\pi^{E}_{h}(s)$. Similarly to the proof of Proposition 8.1,
we can write: $p_{h}(\cdot|s,a)$:

$\displaystyle r_{h}(s,a)$ $\displaystyle\leq
r_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}^{\prime}(\cdot|s,a^{E})}V_{h+1}^{*}(s^{\prime};p^{\prime},r)-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}^{\prime}(\cdot|s,a)}V_{h+1}^{*}(s^{\prime};p^{\prime},r)$
$\displaystyle=r_{h}(s,a^{E})+\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V_{h+1}^{*}(s^{\prime};p,r)-\operatorname*{\mathbb{E}}\limits_{s^{\prime}\sim
p_{h}(\cdot|s,a)}V_{h+1}^{*}(s^{\prime};p^{\prime},r),$

where we have used that we have access to samples about $p_{h}(\cdot|s,a)$. By
hypothesis, $p_{h}(\cdot|s,a)\neq p_{h}(\cdot|s,a^{E})$, therefore, by taking
$r$ such that $\operatorname*{\mathbb{E}}_{s^{\prime}\sim
p_{h}(\cdot|s,a^{E})}V_{h+1}^{*}(s^{\prime};p,r)>\operatorname*{\mathbb{E}}_{s^{\prime}\sim
p_{h}(\cdot|s,a)}V_{h+1}^{*}(s^{\prime};p^{\prime},r)$, we can obtain a reward
$r$ in $\mathcal{R}_{p,\pi^{E}}^{\cap}$ such that
$r_{h}(s,\pi^{E}_{h}(s))<r_{h}(s,a)$.

∎

##  Appendix I A relaxed triangle inequality

In this section, we show that both our notions of distance $d,d_{\infty}$,
defined in Section 4, are semimetrics, and that they satisfy a $\rho$-relaxed
triangle inequality (see Fagin & Stockmeyer, 1998) with finite $\rho>1$ for
any pair of rewards $r,r^{\prime}\in\mathfrak{R}$. Furthermore, we show that
the Hausdorff distance $\mathcal{H}$, when applied to the sets of rewards
considered in this work, inherits the relaxed triangle inequality property. It
should be remarked that we need the $\rho$-relaxed triangle inequality
property with finite $\rho$ just for the _learnability_ proofs of Appendix C.
Moreover, notice that we do not care about a tight value of $\rho$, but only
that it is finite. Instead, if we wanted to compute a minimax lower bound,
then we would need a tight value of $\rho$ in order to obtain a tight lower
bound.

###  I.1 $d$ and $d_{\infty}$ satisfy a relaxed triangle inequality

In the following, for the sake of simplicity, we denote reward functions by
vectors $x,y,z,\dotsc\in\mathbb{R}^{k}$. Moreover, for any pair
$x,y\in\mathbb{R}^{k}$, we will consider distance $d$ for some distribution
$q\in\Delta^{\llbracket k\rrbracket}$ as:

$\displaystyle d(x,y)=\frac{\sum\limits_{i\in\llbracket
k\rrbracket}q_{i}|x_{i}-y_{i}|}{\max\\{\|x\|_{\infty},\|y\|_{\infty}\\}},$

and distance $d_{\infty}$ as:

$\displaystyle
d_{\infty}(x,y)=\frac{\|x-y\|_{\infty}}{\max\\{\|x\|_{\infty},\|y\|_{\infty}\\}}.$

First of all, let us see that neither $d$ nor $d_{\infty}$ are metrics:

######  Proposition I.1.

Both the functions $d$ and $d_{\infty}$ do not satisfy the triangle
inequality.

###### Proof.

To show that the triangle inequality property is not satisfied, we simply
provide some counterexamples. For the sake of simplicity, let $k=2$.

W.r.t. distance $d$, let the vectors $x,y,z\in\mathbb{R}^{2}$ be defined as:

$\displaystyle\begin{cases}x=[1,0]^{\intercal}\\\ y=[-1,-1]^{\intercal}\\\
z=[-2,-1]^{\intercal}\end{cases},$

and observe that, for any $q\in\Delta^{\llbracket 2\rrbracket}$ such that
$q_{2}>0$:

$\displaystyle
d(x,y)=2q_{1}+q_{2}\overset{\textup{\makebox[0.0pt]{?}}}{\leq}d(x,z)+d(y,z)=3/2q_{1}+q_{2}/2+q_{1}/2=2q_{1}+q_{2}/2$
$\displaystyle\iff\,q_{2}\leq 0.$

If $q_{2}=0$, we can take the second component of $z$ to be arbitrary large so
that the inequality is not verified.

As far as $d_{\infty}$ is concerned, let $x,y,z\in\mathbb{R}^{2}$ be the
vectors defined as:

$\displaystyle\begin{cases}x=[0,2]^{\intercal}\\\ y=[2,2]^{\intercal}\\\
z=[1,3]^{\intercal}\end{cases}.$

We have:

$\displaystyle
d_{\infty}(x,y)=\frac{2}{2}=1\overset{\textup{\makebox[0.0pt]{?}}}{\leq}d_{\infty}(x,z)+d_{\infty}(y,z)=1/3+1/3=2/3$
$\displaystyle\,\iff 1\leq 2/3,$

which is clearly false.

Notice that it is possible to generate counterexamples for higher dimensions
$k>2$ by using a simple script of code. ∎

Having verified that distances $d,d_{\infty}$ do not satisfy the triangle
inequality, we can conclude that they are semimetrics, as it is easy to check
the other three properties of positivity, simmetry, and that the distance
between two points is zero if and only if the two points coincide. We are
interested in verifying whether they satisfy a relaxed form of triangle
inequality (Fagin & Stockmeyer, 1998). Specifically, for any finite
$\rho\in\mathbb{R}$ with $\rho>1$, we say that a function $d$ satisfies the
$\rho$-relaxed triangle inequality if, for any $x,y,z\in\mathbb{R}^{k}$:

$\displaystyle d(x,y)\leq\rho\bigl{(}d(x,z)+d(y,z)\bigr{)}.$

We aim to show that both $d$ and $d_{\infty}$ satisfy the $\rho$-relaxed
triangle inequality for some $\rho$. Let us begin with a useful lemma.

######  Lemma I.2.

Let $d_{2}:\mathbb{R}^{k}\times\mathbb{R}^{k}\rightarrow\mathbb{R}$ be the
function that, for any pair $x,y\in\mathbb{R}^{k}$, it returns:

$\displaystyle d_{2}(x,y)$
$\displaystyle\coloneqq\frac{\|x-y\|_{2}}{\max\\{\|x\|_{2},\|y\|_{2}\\}}.$

Then, $d_{2}$ is a metric.

###### Proof.

It is easy to observe that $d_{2}(x,y)=0$ if and only if $x=y$. Moreover,
notice that $d_{2}(x,y)\geq 0$ for all $x,y\in\mathbb{R}^{k}$, and also that
$d_{2}(x,y)=d_{2}(y,x)$.

It remains to prove that $d_{2}$ satisfies the triangle inequality property,
i.e., for any $x,y,z\in\mathbb{R}^{k}$, it satisfies:

$\displaystyle d_{2}(x,y)\leq d_{2}(x,z)+d_{2}(y,z).$

We distinguish two cases, one in which
$\max\\{\|x\|_{2},\|y\|_{2},\|z\|_{2}\\}\neq\|z\|_{2}$ and the other in which
$\max\\{\|x\|_{2},\|y\|_{2},\|z\|_{2}\\}=\|z\|_{2}$.

Let us begin with the former case. W.l.o.g., assume that
$\operatorname*{arg\,max}\\{\|x\|_{2},\|y\|_{2},\|z\|_{2}\\}=y$. Then, we can
write:

$\displaystyle d_{2}(x,y)$
$\displaystyle\coloneqq\frac{\|x-y\|_{2}}{\max\\{\|x\|_{2},\|y\|_{2}\\}}$
$\displaystyle=\frac{\|x-y\|_{2}}{\max\\{\|x\|_{2},\|y\|_{2},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\|z\|_{2}\\}}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\leq}\frac{\|x-z\|_{2}}{\max\\{\|x\|_{2},\|y\|_{2},\|z\|_{2}\\}}+\frac{\|y-z\|_{2}}{\max\\{\|x\|_{2},\|y\|_{2},\|z\|_{2}\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{=}\frac{\|x-z\|_{2}}{\max\\{\|x\|_{2},\|y\|_{2},\|z\|_{2}\\}}+\frac{\|y-z\|_{2}}{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\max\\{\|y\|_{2},\|z\|_{2}\\}}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}\frac{\|x-z\|_{2}}{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\max\\{\|x\|_{2},\|z\|_{2}\\}}}+\frac{\|y-z\|_{2}}{\max\\{\|y\|_{2},\|z\|_{2}\\}}$
$\displaystyle\eqqcolon d_{2}(x,z)+d_{2}(y,z),$

where at (1) we apply triangle inequality of the $\|\cdot\|_{2}$ norm, at (2)
we use that
$\max\\{\|x\|_{2},\|y\|_{2},\|z\|_{2}\\}=\max\\{\|y\|_{2},\|z\|_{2}\\}=\|y\|_{2}$,
at (3) we use that, since $\max\\{\|x\|_{2},\|y\|_{2},\|z\|_{2}\\}=\|y\|_{2}$,
then
$\max\\{\|x\|_{2},\|y\|_{2},\|z\|_{2}\\}\geq\max\\{\|x\|_{2},\|z\|_{2}\\}$.

Now, w.l.o.g., consider the case in which
$\|x\|_{2}\leq\|y\|_{2}\leq\|z\|_{2}$. Since the normed vector space
$\mathbb{R}^{k}$ with $\|\cdot\|_{2}$ is an inner product space, then the
Ptolemy’s inequality (Steele, 2004) holds:

$\displaystyle\|x-y\|_{2}\|z\|_{2}$
$\displaystyle\leq\|x-z\|_{2}\|y\|_{2}+\|y-z\|_{2}\|x\|_{2}$
$\displaystyle\leq\|x-z\|_{2}\|y\|_{2}+\|y-z\|_{2}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\|y\|_{2}}$
$\displaystyle=\|y\|_{2}\bigl{(}\|x-z\|_{2}+\|y-z\|_{2}\bigr{)}.$

By dividing both sides of the inequality by $\|z\|_{2}$ and $\|y\|_{2}$, we
can write:

$\displaystyle\frac{\|x-y\|_{2}}{\|y\|_{2}}\leq\frac{\|x-z\|_{2}}{\|z\|_{2}}+\frac{\|y-z\|_{2}}{\|z\|_{2}}$
$\displaystyle\iff\frac{\|x-y\|_{2}}{\max\\{\|x\|_{2},\|y\|_{2}\\}}\leq\frac{\|x-z\|_{2}}{\max\\{\|x\|_{2},\|z\|_{2}\\}}+\frac{\|y-z\|_{2}}{\max\\{\|y\|_{2},\|z\|_{2}\\}}.$

This concludes the proof. ∎

It should be remarked that the Ptolemy’s inequality holds in inner product
spaces only, and that the unique $p$-normed vector space to be an inner
product space is that with $p=2$. This is why our proof of Lemma I.2 works for
function $d_{p}$ defined as:

$\displaystyle
d_{p}(x,y)\coloneqq\frac{\|x-y\|_{p}}{\max\\{\|x\|_{p},\|y\|_{p}\\}},$

if and only if $p=2$. Thanks to Lemma I.2, we are able to prove the main
theorem of this section.

######  Theorem I.3.

Let $q\in\Delta^{\llbracket k\rrbracket}$ such that $q_{i}>0$ for all
$i\in\llbracket k\rrbracket$, and denote
$q_{\min}\coloneqq\min_{i\in\llbracket k\rrbracket}q_{i}$. Then, both the
semimetrics $d$ and $d_{\infty}$ satisfy the $\rho$-relaxed triangle
inequality with $\rho$ upper bounded, respectively, by $k/q_{\min}^{2}$ and
$k$.

###### Proof.

First, we prove the statement of the theorem for $d_{\infty}$, and then we use
it to prove the statement for $d$.

Observe that, for any $x\in\mathbb{R}^{k}$:

$\displaystyle\|x\|_{\infty}\leq\|x\|_{2}\leq\sqrt{k}\|x\|_{\infty}.$ (51)

Let us consider any three vectors $x,y,z\in\mathbb{R}^{k}$. If
$\operatorname*{arg\,max}\\{\|x\|_{\infty},\|y\|_{\infty},\|z\|_{\infty}\\}\neq
z$, then we can proceed as in the first part of the proof of Lemma I.2 to show
that $d_{\infty}(x,y)\leq d_{\infty}(x,z)+d_{\infty}(y,z)$. Therefore,
w.l.o.g., we consider the case in which
$\operatorname*{arg\,max}\\{\|x\|_{\infty},\|y\|_{\infty},\|z\|_{\infty}\\}=z$.
We can write:

$\displaystyle d_{\infty}(x,y)$
$\displaystyle=\frac{\|x-y\|_{\infty}}{\max\\{\|x\|_{\infty},\|y\|_{\infty}\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\leq}\frac{\|x-y\|_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}}}{\max\\{\|x\|_{\infty},\|y\|_{\infty}\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(2)}}}{\leq}\frac{\sqrt{k}\|x-y\|_{2}}{\max\\{\|x\|_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}},\|y\|_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}}\\}}$
$\displaystyle=\sqrt{k}d_{2}(x,y)$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(3)}}}{\leq}\sqrt{k}d_{2}(x,z)+\sqrt{k}d_{2}(y,z)$
$\displaystyle=\sqrt{k}\frac{\|x-z\|_{2}}{\max\\{\|x\|_{2},\|z\|_{2}\\}}+\sqrt{k}\frac{\|y-z\|_{2}}{\max\\{\|y\|_{2},\|z\|_{2}\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(4)}}}{\leq}\sqrt{k}\frac{\|x-z\|_{2}}{\max\\{\|x\|_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\infty}},\|z\|_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\infty}}\\}}+\sqrt{k}\frac{\|y-z\|_{2}}{\max\\{\|y\|_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\infty}},\|z\|_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\infty}}\\}}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(5)}}}{\leq}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}k}\frac{\|x-z\|_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\infty}}}{\max\\{\|x\|_{\infty},\|z\|_{\infty}\\}}+{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}k}\frac{\|y-z\|_{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\infty}}}{\max\\{\|y\|_{\infty},\|z\|_{\infty}\\}}$
$\displaystyle=k\bigl{(}d_{\infty}(x,z)+d_{\infty}(y,z)\bigr{)},$

where at (1) and at (2) we use Eq. 51, at (3) we use the result in Lemma I.2,
and at (4) and at (5) we use again Eq. 51.

Now, we move to prove the statement concerning $d$. In a similar way as in the
proof of Proposition E.2, we have that, for any $x,y\in\mathbb{R}^{k}$:

$\displaystyle d(x,y)\leq d_{\infty}(x,y)$
$\displaystyle\coloneqq\frac{\|x-y\|_{\infty}}{\max\\{\|x\|_{\infty},\|y\|_{\infty}\\}}$
$\displaystyle=\frac{\max\limits_{i\in\llbracket
k\rrbracket}\frac{q_{i}}{q_{i}}|x_{i}-y_{i}|}{\max\\{\|x\|_{\infty},\|y\|_{\infty}\\}}$
$\displaystyle\leq\frac{\max\limits_{i\in\llbracket
k\rrbracket}\frac{q_{i}}{q_{\min}}|x_{i}-y_{i}|}{\max\\{\|x\|_{\infty},\|y\|_{\infty}\\}}$
$\displaystyle\leq\frac{\sum\limits_{i\in\llbracket
k\rrbracket}q_{i}|x_{i}-y_{i}|}{q_{\min}\max\\{\|x\|_{\infty},\|y\|_{\infty}\\}}$
$\displaystyle=\frac{d(x,y)}{q_{\min}}.$

By using this relation in place of that in Eq. 51, we can carry out the same
derivation made for $d_{\infty}$ using $d_{2}$ for the semimetric $d$ using
$d_{\infty}$. ∎

It should be remarked that we are not claiming here that the values of $\rho$
provided in Theorem I.3 are tight191919 Indeed, we do not believe so. By using
a script to generate a large number of vectors, and using the intuition that
the diagonal of the unit square ($\|\cdot\|_{\infty}$) is $\sqrt{2}$ the
radius of the unit circle ($\|\cdot\|_{2}$), we conjecture that a tighter
value of $\rho$ for $d_{\infty}$ is $\rho=2$, irrespective of the dimension. .

###  I.2 The Hausdorff distance inherits the relaxed triangle inequality
property

First, we show that, thanks to the definitions of $d$ and $d_{\infty}$, if we
apply the Hausdorff distance to _closed_ sets, then the (relaxed) triangle
inequality property is satisfied. Next, we show that the sets of rewards we
work with are _closed_.

Let us begin with the following proposition.

######  Proposition I.4.

Let $\mathcal{H}_{d}$ and $\mathcal{H}_{\infty}$ be defined as in Section 4.
The _closedness_ of the sets to which these distances are applied is a
sufficient condition for the (relaxed) triangle inequality property to hold.

###### Proof Sketch.

We will not provide an exhaustive proof, since it is completely analogous to
the proof that shows that _compactness_ is a sufficient condition for the
Hausdorff distance with inner metric to satisfy triangle inequality. Instead,
we simply give an idea of why for $d$ and $d_{\infty}$ _closedness_ (instead
of _compactness_) suffices.

In practice, the compactness requirement is just needed to guarantee that the
_infimum_ is actually a _minimum_ over the sets in input to the Hausdorff
distance. For a generic notion of inner distance, closedness is not sufficient
because the infimum might be at $\infty$ and, thus, the minimum would not
exist. However, observe that both $d$ and $d_{\infty}$ contain the
normalization term $1/M$ (see Section 4), therefore, for any finite vector
$x\in\mathbb{R}^{k}$, getting to infinity
$\lim_{y\to\infty}\|x-y\|_{\infty}/M=1$ worsens the distance to $x$ w.r.t. any
other finite $z$ in the set containing $y$. This shows that boundedness is not
required anymore, but closedness suffices. This concludes the proof. ∎

In this work we consider unbounded sets of rewards, so clearly compactness
does not hold. The following proposition shows the closedness of some sets of
rewards.

######  Proposition I.5.

The following sets are closed:

$\displaystyle\overline{\mathcal{R}}_{p,\pi^{E}},\mathcal{R}_{p,\pi^{E}},\mathcal{R}_{p,\pi^{E}}^{\cap},\mathcal{R}_{p,\pi^{E}}^{\cup},\widetilde{\mathcal{R}}^{\cap},\widetilde{\mathcal{R}}^{\cup}.$

###### Proof.

From Theorem 3 of Ng & Russell (2000), we observe that the old feasible set
$\overline{\mathcal{R}}_{p,\pi^{E}}$ is closed because it is defined by linear
less than or _equal to_ $\leq$ inequalities.

The new feasible set $\mathcal{R}_{p,\pi^{E}}$ can be expressed, from
Corollary D.1, as an arbitrary union of closed sets
$\mathcal{R}_{p,\pi^{E}}=\bigcup_{\pi^{\prime}\in[\pi^{E}]_{\equiv_{\mathcal{S}^{p,\pi^{E}}}}}\overline{\mathcal{R}}_{p,\pi^{\prime}}$.
However, observe that the feasible sets
$\overline{\mathcal{R}}_{p,\pi^{\prime}}$ with stochastic $\pi^{\prime}$ are
contained in the feasible sets of some deterministic policies. Since there is
a finite number of deterministic policies, then $\mathcal{R}_{p,\pi^{E}}$ can
be expressed as a finite union of closed sets, so it is closed.

The subset $\mathcal{R}_{p,\pi^{E}}^{\cap}$ is an arbitrary intersection of
$\mathcal{R}_{p,\pi^{E}}$, i.e., closed sets, thus it is closed.

The superset $\mathcal{R}_{p,\pi^{E}}^{\cup}$ is an arbitrary union of
$\mathcal{R}_{p,\pi^{E}}$, so, potentially, it might not be non-closed.
However, thanks to the definitions of $p^{m}$ and $\pi^{m}$ in Eq. 20 and Eq.
21, we know that the arbitrary union representing
$\mathcal{R}_{p,\pi^{E}}^{\cup}$ coincides with the feasible set
$\mathcal{R}_{p^{m},\pi^{m}}$, which is closed, thus
$\mathcal{R}_{p,\pi^{E}}^{\cup}$ is closed.

In an analogous manner, by using Eq. 25 and Eq. 26, we observe that the
relaxations $\widetilde{\mathcal{R}}^{\cap}$ and
$\widetilde{\mathcal{R}}^{\cup}$ can be expressed by a finite number of linear
less than or _equal to_ $\leq$ constraints, thus they are closed. ∎

##  Appendix J Technical Lemmas

In this section, we report some technical lemmas that are useful in the
analysis of the sample complexity of IRLO and PIRLO (see Appendix F). Lemma
J.1 and Lemma J.2 are taken from other works, while Lemma J.3 takes
inspiration from Lemma B.9 of (Metelli et al., 2021).

######  Lemma J.1 (Lemma A.1 of (Xie et al., 2021)).

Suppose that $N\sim\text{Bin}(n,p)$ is a binomially distributed random
variable, with $n\geq 1$ and $p\in[0,1]$. Then, with probability at least
$1-\delta$, we have that:

$\frac{p}{N\vee 1}\leq\frac{8\ln\frac{1}{\delta}}{n}.$

######  Lemma J.2 (Lemma 8 of (Kaufmann et al., 2021)).

Let $X_{1},X_{2},\dotsc,X_{n},\dotsc$ be i.i.d. samples from a distribution
supported over $\llbracket m\rrbracket$, of probabilities given by
$p\in\Delta^{\llbracket m\rrbracket}$. We denote by $\widehat{p}_{n}$ the
empirical vector of probabilities, i.e., for all $k\in\llbracket m\rrbracket$:

$\widehat{p}_{n,k}=\frac{1}{n}\sum\limits_{l=1}^{n}\mathbbm{1}\\{X_{l}=k\\}.$

For all $p\in\Delta^{\llbracket m\rrbracket}$, for all $\delta\in[0,1]$:

$\mathbb{P}\biggl{(}\exists n\in\mathbb{N}_{\geq
0},\,nKL(\widehat{p}_{n}\|p)>\ln(1/\delta)+(m-1)\ln\bigl{(}e(1+n/(m-1))\bigr{)}\biggr{)}\leq\delta.$

######  Lemma J.3.

Let $a,b,c,d>0$ such that $2bc>e$. Then, the inequality $x\geq a+b\ln(cx+d)$
is satisfied by all $x\geq 2a+3b\ln(2bc)+d/c$.

###### Proof.

Observe that, since function $x$ grows faster than function $a+b\ln(cx+d)$,
then there exists $\bar{x}$ such that, for all $x\geq\bar{x}$, the inequality
is satisfied. Our goal here is to show that such $\bar{x}$ can be upper
bounded by $2a+3b\ln(2bc)+d/c$.

Let us consider any $x\geq 2a+d/c$. We can write:

$\displaystyle x\geq a+b\ln(cx+d)\quad$
$\displaystyle\Longleftrightarrow\quad\frac{x-a}{b}\geq\ln(c(x\pm a)+d)$
$\displaystyle\Longleftrightarrow\quad e^{\frac{x-a}{b}}\geq c(x-a)+ca+d$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\Longleftarrow}\quad
e^{\frac{x-a}{b}}\geq 2c(x-a)$
$\displaystyle\Longleftrightarrow\quad\frac{a-x}{b}e^{\frac{a-x}{b}}\geq-\frac{1}{2bc},$
(I)

where at (1) we have used that, since $x\geq 2a+d/c$, then $c(x-a)\geq ca+d$,
and thus we have replaced the constraint with a stronger one.

Hypothesis $2bc>e$ entails that $-\frac{1}{2bc}\geq-\frac{1}{e}$, thus we can
apply the Lambert function, which provides as solution to inequality I all the
$x$ such that:

$\frac{a-x}{b}\leq W_{-1}\biggl{(}-\frac{1}{2bc}\biggr{)}\quad\text{ or
}\quad\frac{a-x}{b}\geq W_{0}\biggl{(}-\frac{1}{2bc}\biggr{)},$

where $W_{0}$ is the principal component of the Lambert W function. Consider
the first inequality. We can write:

$\displaystyle x$ $\displaystyle\geq
a-bW_{-1}\biggl{(}-\frac{1}{2bc}\biggr{)}$
$\displaystyle\overset{\textup{\makebox[0.0pt]{(1)}}}{\leq}a+b+b\sqrt{2\ln(2bc)-2}+b\ln(2bc)-b$
$\displaystyle\leq a+3b\ln(2bc),$

where at (1) we have applied the inequality
$W_{-1}(-e^{-u-1})\geq-1-\sqrt{2u}-u$ from (Chatzigeorgiou, 2013).

To obtain the result, we use that $\max\\{a,b\\}\leq a+b$ for any $a,b\geq 0$
to upper bound:

$\displaystyle\max\bigl{\\{}2a+d/c,a+3b\ln(2bc)\bigr{\\}}=a+\max\bigl{\\{}a+d/c,3b\ln(2bc)\bigr{\\}}\leq
2a+3b\ln(2bc)+d/c.$

∎

##  Appendix K Illustrative Experiment

We have applied PIRLO to the highway driving application domain. To this aim,
we have used the data202020 The data is publicly available at
https://github.com/amarildolikmeta/irl_real_life/tree/main/datasets/highway.
gathered by Likmeta et al. (2021).

##### Data Description

The dataset consists of trajectories of $H=400$ stages collected by $10$
different human experts driving in a simulator. The highway has 3 lanes. The
goal of each expert is to change lane in order to drive safely and to minimize
the trip time. The action space $\mathcal{A}$ is made of 3 actions: Turn left,
turn right, continue forward. The state space $\mathcal{S}$ is continue, and
it is represented by $25$ features, keeping into account the speed and
position of the car, and the speed and position of the surrounding cars.

##### Data Preprocessing

We have to transform the data to obtain a tabular MDP. To this aim, we
construct $5$ discrete features from the $25$ present in the original data: We
use three binary features, free left, free right, free forward, that say
whether there is a vehicle on the left, on the right, or in front of our car;
next, we use a binary feature that says whether the car is changing lane, and
a discrete feature with $5$ possible values for the speed of the vehicle. In
this way, we obtain a tabular MDP with $S=80$.

##### Experiments Design

As mentioned by Likmeta et al. (2021), this lane-change scenario represents a
multi-objective task, because humans consider several objectives while
driving. We manually design some reward functions coherent with the most
common driving objectives and we use PIRLO to verify whether they are
compatible w.h.p. with the demonstrations of behavior provided by the 10
experts in the dataset. First, we construct a single behavioral dataset
$\mathcal{D}^{b}$ by joining the trajectories of all the 10 experts, and then
we consider one expert at a time to construct $\mathcal{D}^{E}$. Next, we
design the reward functions and we give them in input to the membership
checker implementation of PIRLO.

##### Experiments Results

We design 3 kinds of reward functions:

  * •

reward $r_{\text{BC}}$, i.e., the “behavioral cloning” reward, which is the
reward that assigns positive values to actions played by the expert’s policy;

  * •

reward $r$, which is coherent with the observations provided in Section 5.3 of
Likmeta et al. (2021). In words, it assigns negative reward when ($i$) the
right lane is not free, ($ii$) there is a car in front of us (and so it
decreases our speed), ($iii$) we change lane;

  * •

reward $\overline{r}$, which is $-r$, i.e., it assigns positive reward to all
the bad actions;

We provide the output of PIRLO in Table 2.

| Alice | Bob | Carol | Chuck | Craig | Dan | Erin | Eve | Grace | Judy
---|---|---|---|---|---|---|---|---|---|---
$r_{\text{BC}}$ | Y,Y | Y,Y | Y,Y | Y,Y | Y,Y | Y,Y | Y,Y | Y,Y | Y,Y | Y,Y
$r$ | N,N | Y,N | Y,N | Y,N | N,N | Y,N | Y,N | N,N | N,N | Y,N
$\overline{r}$ | N,N | N,N | N,N | N,N | N,N | N,N | N,N | N,N | N,N | N,N

Table 2: The output of PIRLO when fed with the rewards designed for the
highway driving task. The first letter refers to the superset, while the
second letter refers to the subset. “N” means that the reward does not belong
to the set, while “Y” means that it belongs to the set.

Some comments are in order. First, our reduction to a smaller state space has
caused the policies of the agents to be (more) stochastic. Moreover, this
reduction has increased the number of times that the corner case described in
Appendix D.5 takes place. Since this corner case is outside the good event, we
have removed such data from $\mathcal{D}^{b}$; in this way, we improve the
performances of PIRLO.

Observe that the behavioral cloning reward $r_{\text{BC}}$ belongs to the
subset and superset for all the experts. This is reasonable since it assigns
positive reward only to expert’s actions in the support of the expert’s
policy. However, it should be remarked that if we had not removed the “corner-
case” samples, then $r_{\text{BC}}$ would not belong to the subsets.

The reward $r$ compatible with the analysis provided in Likmeta et al. (2021)
belongs to the superset of some experts only. Specifically, for the experts
Alice, Eve, Grace, and Craig, that belong to the clusters 1 and 3 of Table 1
of Likmeta et al. (2021), the reward $r$ is not in the superset. However, it
should be remarked that reward $r$ is not exactly the same as the reward
described by Likmeta et al. (2021), and also that we are working with a more
aggregated state space.

Notice that, as expected, reward $\overline{r}=-r$, which rewards “bad”
actions, does not belong neither to the subset nor to the superset of any
expert.