$\displaystyle\qquad\qquad-3\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}}\Bigg{]}\operatorname{\mathds{1}}\bigg{(}\frac{\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}}\leq
36\bigg{)}$ $\displaystyle\qquad\geq
3\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}}\Bigg{]}-108SH$
$\displaystyle\qquad\geq
2\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}}\Bigg{]},$
(91)

where the first inequality follows from the choice (26) of $\pi^{(k)}$, the
second inequality is a consequence of the relation (88), and the last line
makes use of (90). This in turn allows one to demonstrate that

$\displaystyle\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\big{(}\widehat{d}_{h}^{\pi^{(k)}}(s,a)-\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}^{2}}\Bigg{]}$
$\displaystyle=\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\big{(}\frac{1}{KH}+\widehat{d}_{h}^{\pi^{(k)}}(s,a)\big{)}\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}^{2}}\bigg{]}-\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\bigg{[}\frac{\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}^{2}}\Bigg{]}$
$\displaystyle\geq\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}}\Bigg{]}>108SH,$

where the last line results from (91) and the condition (90). We can then
readily derive

$\displaystyle\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}}\Bigg{]}-\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k+1)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}}\Bigg{]}$
$\displaystyle=\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\big{(}\mathbb{E}_{\pi^{\prime}\sim\mu^{(k+1)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}-\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k+1)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}}\Bigg{]}$
$\displaystyle=\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\alpha\big{(}\widehat{d}_{h}^{\pi^{(k)}}(s,a)-\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k+1)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}}\Bigg{]}$
$\displaystyle=\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\alpha\big{(}\widehat{d}_{h}^{\pi^{(k)}}(s,a)-\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}^{2}}\Bigg{]}$
$\displaystyle\qquad\qquad-\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\Bigg{[}\frac{\alpha^{2}\big{(}\widehat{d}_{h}^{\pi^{(k)}}(s,a)-\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}^{2}\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}^{2}\big{(}\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu^{(k+1)}}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}\big{)}}\Bigg{]}$
$\displaystyle\geq 108\alpha
SH-\alpha^{2}(K^{3}H^{4})=\frac{108S^{2}}{K^{3}H^{2}}-\frac{S^{2}}{K^{3}H^{2}}=\frac{107S^{2}}{K^{3}H^{2}},$
(92)

where the third line relies on the update rule (29), and the last line
utilizes the choice (30) of $\alpha$.

In summary, the above argument reveals that: before the stopping criterion is
met, each iteration is able to make progress at least as large as in (92).
Recognizing the crude bound

$\displaystyle
0\leq\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\bigg{[}\frac{\widehat{d}_{h}^{\mathsf{off}}(s,a)}{\frac{1}{KH}+\mathbb{E}_{\pi^{\prime}\sim\mu}\big{[}\widehat{d}_{h}^{\pi^{\prime}}(s,a)\big{]}}\bigg{]}\leq
KH\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\mathbb{E}_{a\sim\pi_{h}^{t+1}(\cdot|s)}\big{[}\widehat{d}_{h}^{\mathsf{off}}(s,a)\big{]}\leq
KH^{2}$

that holds for any $\mu\in\Delta(\Pi)$, one can combine this with (92) to
conclude that: the proposed procedure terminates within
$O\big{(}\frac{K^{4}H^{4}}{S^{2}}\big{)}$ iterations, as claimed.

##  Appendix C Proofs of technical lemmas

###  C.1 Proof of Lemma 2

The Bernstein inequality combined with the union bound tells us that, with
probability at least $1-\delta/3$,

$\displaystyle\bigg{|}\frac{2N_{h}^{\mathsf{off}}(s,a)}{K^{\mathsf{off}}}-d^{\mathsf{off}}_{h}(s,a)\bigg{|}$
$\displaystyle\leq
6\sqrt{\frac{d^{\mathsf{off}}_{h}(s,a)\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}}+\frac{6\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}$
$\displaystyle\leq\frac{d^{\mathsf{off}}_{h}(s,a)}{2}+\frac{24\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}$
(93)

holds simultaneously for all
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, where the last line invokes
the AM-GM inequality. This in turn reveals that

$\displaystyle\frac{4N_{h}^{\mathsf{off}}(s,a)}{3K^{\mathsf{off}}}-\frac{16\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}\leq
d^{\mathsf{off}}_{h}(s,a)\leq\frac{4N_{h}^{\mathsf{off}}(s,a)}{K^{\mathsf{off}}}+\frac{48\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}.$
(94)

As a result, we can show that:

  * •

If $\frac{N_{h}^{\mathsf{off}}(s,a)}{K^{\mathsf{off}}}\geq
c_{\mathsf{off}}\big{(}\frac{\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}+\frac{H^{4}S^{4}A^{4}\log\frac{HSA}{\delta}}{N}+\frac{SA}{K^{\mathsf{on}}}\big{)}$
for some $c_{\mathsf{off}}\geq 48$, then one has

$\displaystyle\frac{2N_{h}^{\mathsf{off}}(s,a)}{3K^{\mathsf{off}}}$
$\displaystyle\leq
d^{\mathsf{off}}_{h}(s,a)\leq\frac{6N_{h}^{\mathsf{off}}(s,a)}{K^{\mathsf{off}}}\qquad\text{and}\qquad\widehat{d}^{\mathsf{off}}_{h}(s,a)=\frac{2N_{h}^{\mathsf{off}}(s,a)}{K^{\mathsf{off}}}$
(95a)
$\displaystyle\Longrightarrow\qquad\frac{1}{3}\widehat{d}^{\mathsf{off}}_{h}(s,a)\leq
d^{\mathsf{off}}_{h}(s,a)\leq 3\widehat{d}^{\mathsf{off}}_{h}(s,a).$ (95b)

  * •

If instead
$\frac{N_{h}^{\mathsf{off}}(s,a)}{K^{\mathsf{off}}}<c_{\mathsf{off}}\big{(}\frac{\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}+\frac{H^{4}S^{4}A^{4}\log\frac{HSA}{\delta}}{N}+\frac{SA}{K^{\mathsf{on}}}\big{)}$,
then one has $\widehat{d}^{\mathsf{off}}_{h}(s,a)=0$, and therefore,

$\displaystyle d_{h}^{\mathsf{off}}(s,a)$ $\displaystyle\geq
0=\frac{1}{3}\widehat{d}_{h}^{\mathsf{off}}(s,a),$ $\displaystyle
d_{h}^{\mathsf{off}}(s,a)$
$\displaystyle\leq\frac{4N_{h}^{\mathsf{off}}(s,a)}{K^{\mathsf{off}}}+\frac{48\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}<5c_{\mathsf{off}}\bigg{\\{}\frac{\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}+\frac{H^{4}S^{4}A^{4}\log\frac{HSA}{\delta}}{N}+\frac{SA}{K^{\mathsf{on}}}\bigg{\\}}$
$\displaystyle=\widehat{d}_{h}^{\mathsf{off}}(s,a)+5c_{\mathsf{off}}\bigg{\\{}\frac{\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}+\frac{H^{4}S^{4}A^{4}\log\frac{HSA}{\delta}}{N}+\frac{SA}{K^{\mathsf{on}}}\bigg{\\}}.$

Taken collectively, these inequalities demonstrate that

$\displaystyle\frac{1}{3}\widehat{d}_{h}^{\mathsf{off}}(s,a)\leq
d^{\mathsf{off}}_{h}(s,a)\leq\widehat{d}_{h}^{\mathsf{off}}(s,a)+5c_{\mathsf{off}}\bigg{\\{}\frac{\log\frac{HSA}{\delta}}{K^{\mathsf{off}}}+\frac{H^{4}S^{4}A^{4}\log\frac{HSA}{\delta}}{N}+\frac{SA}{K^{\mathsf{on}}}\bigg{\\}},$
(96)

provided that $c_{\mathsf{off}}>0$ is sufficiently large.

###  C.2 Proof of Lemma 6

Before embarking on the proof, let us introduce several notation. For each
$1\leq h\leq H$, define $P_{h}^{\pi^{\star}}\in\mathbb{R}^{S\times S}$ and
$d_{h}^{\pi^{\star}}\in\mathbb{R}^{S}$ such that: for all $s\in\mathcal{S}$,

$P_{h}^{\pi^{\star}}(s,\cdot)=P_{h}\big{(}\cdot|s,\pi^{\star}(s)\big{)}\qquad\text{and}\qquad
d_{h}^{\pi^{\star}}(s)=d_{h}^{\pi^{\star}}\big{(}s,\pi^{\star}(s)\big{)}.$
(97)

To begin with, it can be easily seen from (60) and the basic fact
$\mathsf{Var}_{P_{h}(\cdot|s,a)}\big{(}\widehat{V}_{h+1}\big{)}\leq H^{2}$
that

$\displaystyle\big{\langle}d_{j}^{\pi^{\star}},V_{j}^{\star}-V_{j}^{\widehat{\pi}}\big{\rangle}$
$\displaystyle\leq\underbrace{8H\sum_{h:h\geq
j}\sum_{s}\max_{a:(s,a)\in\mathcal{I}_{h}}\sqrt{2d_{h}^{\star}(s,a)C^{\star}(\sigma)\widehat{d}_{h}^{\mathsf{off}}(s,a)}\sqrt{\frac{c_{\mathsf{b}}\log\frac{K}{\delta}}{N_{h}^{\mathsf{trim}}(s,a)+1}}}_{\eqqcolon\gamma_{3}}$
$\displaystyle\quad+\underbrace{4H\sum_{h:h\geq
j}\sum_{(s,a)\in\mathcal{T}_{h}}\widehat{d}_{h}^{\pi^{\star}}(s,a)\sqrt{\frac{c_{\mathsf{b}}\log\frac{K}{\delta}}{N_{h}^{\mathsf{trim}}(s,a)+1}}}_{\eqqcolon\gamma_{2}}+\frac{61c_{\xi}H^{6}S^{4}A^{4}}{N}\log\frac{K}{\delta}$
(98)

holds for any $j\in[H]$.Note that we have bounded $\gamma_{2}$ in (70). We
then need to bound $\gamma_{3}$.

With regards to the term $\gamma_{3}$: invoking similar arguments as for (63)
leads to

$\displaystyle\gamma_{3}$ $\displaystyle\leq 64c_{\mathsf{b}}H\sum_{h:h\geq
j}\sum_{s}\max_{a}\sqrt{2d_{h}^{\pi^{\star}}(s,a)C^{\star}(\sigma)\widehat{d}_{h}^{\mathsf{off}}(s,a)}\sqrt{\frac{\log\frac{K}{\delta}}{1/H+\frac{1}{72}K^{\mathsf{on}}\mathbb{E}_{\pi\in\mu^{\mathsf{imitate}}}\big{[}\widehat{d}_{h}^{\pi}(s,a)\big{]}}}+4H^{2}SC^{\star}(\sigma)\Big{(}\frac{\xi}{N}+\frac{1}{K^{\mathsf{on}}H}\Big{)}$
$\displaystyle\leq 64c_{\mathsf{b}}H\sqrt{2\sum_{h:h\geq
j}\sum_{s,a}d_{h}^{\pi^{\star}}(s,a)}\cdot\sqrt{\sum_{h:h\geq
j}\sum_{s}\max_{a}\frac{C^{\star}(\sigma)\widehat{d}_{h}^{\mathsf{off}}(s,a)\log\frac{K}{\delta}}{1/H+\frac{1}{72}K^{\mathsf{on}}\mathbb{E}_{\pi\in\mu^{\mathsf{imitate}}}\big{[}\widehat{d}_{h}^{\pi}(s,a)\big{]}}}+4H^{2}SC^{\star}(\sigma)\Big{(}\frac{\xi}{N}+\frac{1}{K^{\mathsf{on}}H}\Big{)}$
$\displaystyle\leq
768c_{\mathsf{b}}\sqrt{\frac{13H^{4}SC^{\star}(\sigma)}{K^{\mathsf{on}}}\log\frac{K}{\delta}}+4H^{2}SC^{\star}(\sigma)\Big{(}\frac{\xi}{N}+\frac{1}{K^{\mathsf{on}}H}\Big{)},$
(99)

where the second step invokes the Cauchy-Schwartz inequality, and the last
line comes from (58). Similarly, repeating the above argument but focusing on
the offline dataset, we can derive (which we omit for the sake of brevity)

$\displaystyle\gamma_{3}$ $\displaystyle\leq 64c_{\mathsf{b}}H\sum_{h:h\geq
j}\sum_{s}\max_{a}\sqrt{2d_{h}^{\pi^{\star}}(s,a)C^{\star}(\sigma)\widehat{d}_{h}^{\mathsf{off}}(s,a)}\sqrt{\frac{\log\frac{K}{\delta}}{1/H+\frac{1}{72}K^{\mathsf{off}}d_{h}^{\mathsf{off}}(s,a)\big{]}}}+4H^{2}SC^{\star}(\sigma)\Big{(}\frac{\xi}{N}+\frac{1}{K^{\mathsf{off}}H}\Big{)}$
$\displaystyle\leq 64c_{\mathsf{b}}H\sqrt{2\sum_{h:h\geq
j}\sum_{s,a}d_{h}^{\pi^{\star}}(s,a)}\cdot\sqrt{\sum_{h:h\geq
j}\sum_{s}\max_{a}\frac{C^{\star}(\sigma)\widehat{d}_{h}^{\mathsf{off}}(s,a)\log\frac{K}{\delta}}{1/H+\frac{1}{72}K^{\mathsf{off}}d_{h}^{\mathsf{off}}(s,a)}}+4H^{2}SC^{\star}(\sigma)\Big{(}\frac{\xi}{N}+\frac{1}{K^{\mathsf{off}}H}\Big{)}$
$\displaystyle\leq
768c_{\mathsf{b}}\sqrt{\frac{6H^{4}SC^{\star}(\sigma)}{K^{\mathsf{off}}}\log\frac{K}{\delta}}+4H^{2}SC^{\star}(\sigma)\Big{(}\frac{\xi}{N}+\frac{1}{K^{\mathsf{off}}H}\Big{)},$
(100)

where the last line makes use of (87).

Combining (99), (100) and (70) with (98), we can show that

$\displaystyle\big{\langle}d_{j}^{\pi^{\star}},V_{j}^{\star}-V_{j}^{\widehat{\pi}}\big{\rangle}$
$\displaystyle\leq\min\left\\{768c_{\mathsf{b}}\sqrt{\frac{13H^{4}SC^{\star}(\sigma)}{K^{\mathsf{on}}}\log\frac{K}{\delta}}+4H^{2}SC^{\star}(\sigma)\Big{(}\frac{\xi}{N}+\frac{1}{KH}\Big{)},\,768c_{\mathsf{b}}\sqrt{\frac{6H^{4}SC^{\star}(\sigma)}{K^{\mathsf{off}}}\log\frac{K}{\delta}}\right\\}$
$\displaystyle\qquad+96c_{\mathsf{b}}\sqrt{\frac{2H^{3}SA(2\widehat{\sigma}+HS\xi/N)}{K^{\mathsf{on}}}\log\frac{HK}{\delta}}+436H^{2}SA\Big{(}\frac{\xi}{N}+\frac{1}{\min\\{K^{\mathsf{on}},K^{\mathsf{off}}\\}H}\Big{)}$
$\displaystyle\qquad+\frac{61c_{\xi}H^{6}S^{4}A^{4}}{N}\log\frac{K}{\delta}$
$\displaystyle\leq 1$ (101)

for all $1\leq j\leq H$, with the proviso that

$\displaystyle\frac{H^{7}S^{5}A^{4}}{K^{\mathsf{on}}}\log^{2}\frac{K}{\delta}$
$\displaystyle\leq c_{10}$
$\displaystyle\frac{H^{5}S^{4}A^{3}C^{\star}(\sigma)\log\frac{K}{\delta}}{K^{\mathsf{on}}}$
$\displaystyle\leq c_{10}$
$\displaystyle\frac{HSC^{\star}(\sigma)\log\frac{K}{\delta}}{K^{\mathsf{off}}}$
$\displaystyle\leq c_{10}$
$\displaystyle\frac{HSA\log\frac{K}{\delta}}{K^{\mathsf{off}}}$
$\displaystyle\leq c_{10}$

for some sufficiently small constant $c_{10}>0$. As a consequence, we can
demonstrate that

$\displaystyle\sum_{h:h\geq
j}\sum_{s,a}d_{h}^{\pi^{\star}}(s,a)\mathsf{Var}_{P_{h}(\cdot|s,a)}(\widehat{V}_{h+1})$
$\displaystyle\qquad\leq\sum_{h:h\geq
j}2\sum_{s,a}d_{h}^{\pi^{\star}}(s,a)\Big{(}\mathsf{Var}_{P_{h}(\cdot|s,a)}(V_{h+1}^{\star})+\mathsf{Var}_{P_{h}(\cdot|s,a)}(V_{h+1}^{\star}-\widehat{V}_{h+1})\Big{)}$
$\displaystyle\qquad\leq 4H^{2}+H\sum_{h:h\geq
j}\sum_{s}d_{h}^{\pi^{\star}}\big{(}s,\pi^{\star}(s)\big{)}\mathbb{E}_{P_{h}(\cdot|s,\pi^{\star}(s))}\big{[}V_{h+1}^{\star}-\widehat{V}_{h+1}\big{]}$
$\displaystyle\qquad=4H^{2}+H\sum_{h:h\geq
j}\big{(}d_{h}^{\pi^{\star}}\big{)}^{\top}P_{h}^{\pi^{\star}}\big{[}V_{h+1}^{\star}-\widehat{V}_{h+1}\big{]}$
$\displaystyle\qquad=4H^{2}+H\sum_{h\geq
j}\big{(}d_{h+1}^{\pi^{\star}}\big{)}^{\top}\big{[}V_{h+1}^{\star}-\widehat{V}_{h+1}\big{]}\leq
5H^{2}$ (102)

for all $1\leq j\leq H$. Here, the third line in (102) applies the following
fact

$\displaystyle\sum_{h}\sum_{s,a}d_{h}^{\pi^{\star}}(s,a)\mathsf{Var}_{P_{h}(\cdot|s,a)}(V_{h+1}^{\star})$
$\displaystyle\qquad=\sum_{h}\sum_{s}d_{h}^{\pi^{\star}}\big{(}s,\pi^{\star}(s)\big{)}\Big{[}\big{\langle}P_{h}^{\pi^{\star}}(s,\cdot),V_{h+1}^{\star}\circ
V_{h+1}^{\star}\big{\rangle}-\big{(}\big{\langle}P_{h}^{\pi^{\star}}(s,\cdot),V_{h+1}^{\star}\big{\rangle}\big{)}^{2}\Big{]}$
$\displaystyle\qquad=\sum_{h}\sum_{s}d_{h}^{\pi^{\star}}\big{(}s,\pi^{\star}(s)\big{)}\Big{[}\big{\langle}P_{h}^{\pi^{\star}}(s,\cdot),V_{h+1}^{\star}\circ
V_{h+1}^{\star}\big{\rangle}-\big{(}V_{h}^{\star}(s)-r_{h}^{\star}\big{(}s,\pi^{\star}(s)\big{)}\big{)}^{2}\Big{]}$
$\displaystyle\qquad\leq\sum_{h}\sum_{s}d_{h}^{\pi^{\star}}\big{(}s,\pi^{\star}(s)\big{)}\Big{[}\big{\langle}P_{h}^{\pi^{\star}}(s,\cdot),V_{h+1}^{\star}\circ
V_{h+1}^{\star}\big{\rangle}-\big{(}V_{h}^{\star}(s)\big{)}^{2}+2H\Big{]}$
$\displaystyle\qquad=\sum_{h}\big{(}d_{h}^{\pi^{\star}}\big{)}^{\top}P_{h}^{\pi^{\star}}\big{(}V_{h+1}^{\star}\circ
V_{h+1}^{\star}\big{)}-\sum_{h}\big{(}d_{h}^{\pi^{\star}}\big{)}^{\top}\big{(}V_{h}^{\star}\circ
V_{h}^{\star}\big{)}\Big{]}+2H^{2}$
$\displaystyle\qquad=\sum_{h}\big{(}d_{h+1}^{\pi^{\star}}\big{)}^{\top}\big{(}V_{h+1}^{\star}\circ
V_{h+1}^{\star}\big{)}-\sum_{h}\big{(}d_{h}^{\pi^{\star}}\big{)}^{\top}\big{(}V_{h}^{\star}\circ
V_{h}^{\star}\big{)}+2H^{2}$ $\displaystyle\qquad\leq 2H^{2},$

where the second identity comes from the Bellman equation; the third relation
uses the fact that $V_{h}^{\star}(s)\leq H$, and the penultimate line holds
since
$\big{(}d_{h}^{\pi^{\star}}\big{)}^{\top}P_{h}^{\pi^{\star}}=\big{(}d_{h+1}^{\pi^{\star}}\big{)}^{\top}$;
the penultimate step in (102) is due to (101); and the line in (102) holds
true since
$\big{(}d_{h}^{\pi^{\star}}\big{)}^{\top}P_{h}^{\pi^{\star}}=\big{(}d_{h+1}^{\pi^{\star}}\big{)}^{\top}$.