following the policy-update rule of ProST-T (Algorithm F.2 in Appendix F.2),
suppose for given $g\in[G]$, we got inexact soft $Q$-function value of the
policy $\widehat{\pi}^{(\Delta_{\pi})}$ as
$\widetilde{Q}^{\widehat{\pi}^{(\Delta_{\pi})}}_{\tau}$ where
$\widehat{Q}^{\widehat{\pi}^{(\Delta_{\pi})}}_{\tau}$ denotes exact soft
$Q$-function value. The approximation gap
$|\widetilde{Q}^{\widehat{\pi}^{(\Delta_{\pi})}}_{\tau}-\widehat{Q}^{\widehat{\pi}^{(\Delta_{\pi})}}_{\tau}|$
can come from computing $Q$ using finite samples. For choosen hyperparameter
$\delta$, Let the maximum of approximation gap over $(s,a)$ is smaller than
$\delta$, namely
$||\widetilde{Q}_{\tau}^{\widehat{\pi}^{(\Delta_{\pi})}}-\widehat{Q}_{\tau}^{\widehat{\pi}^{(\Delta_{\pi})}}||_{\infty}\leq\delta$
holds. Then, the policy-update rule of ProST-T can be written as follows :

$\displaystyle\widehat{\pi}^{(g+1)}(\cdot|s)=\frac{1}{Z^{(\Delta_{\pi})}}\cdot\left(\widehat{\pi}^{(\Delta_{\pi})}(\cdot|s)\right)^{1-\frac{\eta\tau}{1-\gamma}}\exp{\left(\frac{\eta\widetilde{Q}_{\tau}^{\widehat{\pi}^{(\Delta_{\pi})}}(s,a)}{1-\gamma}\right)}$
$\displaystyle\text{where}~{}~{}||\widetilde{Q}_{\tau}^{\widehat{\pi}^{(\Delta_{\pi})}}(s,a)-\widehat{Q}_{\tau}^{\widehat{\pi}^{(\Delta_{\pi})}}(s,a)||_{\infty}\leq\delta~{}~{}\text{for}~{}~{}\forall(s,a)\in\mathcal{S}\times\mathcal{A}$

where
$Z^{(\Delta_{\pi})}(s)=\sum_{a\in\mathcal{A}}\left(\widehat{\pi}^{(\Delta_{\pi})}(a|s)\right)^{1-\frac{\eta\tau}{1-\gamma}}\exp{\left((\eta\widehat{Q}_{\tau}^{\widehat{\pi}^{(\Delta_{\pi})}}(s,a))/(1-\gamma)\right)}$

From the Theorem 2 of the paper [21], when the learning rate satisfies
$0\leq\eta\leq(1-\gamma)/\tau$, then the approximate entropy-regularized NPG
method satisfies the linear convergence theorem as follows:

$||\widehat{Q}^{\bigast,k+1}_{\tau}-\widehat{Q}^{\widehat{\pi}^{(\Delta_{\pi})}}_{\tau}||_{\infty}\leq\gamma\left[(1-\eta\tau)^{\Delta_{\pi}-1}C_{1}+C_{2}\right]$
(D.27)
$||\log\widehat{\pi}^{\bigast,k+1}-\log\widehat{\pi}^{(\Delta_{\pi})}||_{\infty}\leq
2\tau^{-1}\left[(1-\eta\tau)^{\Delta_{\pi}-1}C_{1}+C_{2}\right]$ (D.28)

where $C_{1},C_{2}$ is given by

$\displaystyle C_{1}$
$\displaystyle=||\widehat{Q}^{\bigast,k+1}_{\tau}-\widehat{Q}^{\widehat{\pi}^{(0)}}_{\tau}||_{\infty}+2\tau\left(1-\frac{\eta\tau}{1-\gamma}\right)||\log\widehat{\pi}^{\bigast,k+1}-\log\widehat{\pi}^{(0)}||_{\infty}$
$\displaystyle=||\widehat{Q}^{\bigast,k+1}_{\tau}-\widehat{Q}^{\pi^{k}}_{\tau}||_{\infty}+2\tau\left(1-\frac{\eta\tau}{1-\gamma}\right)||\log\widehat{\pi}^{\bigast,k+1}-\log\widehat{\pi}^{k}||_{\infty}$
(D.29) $\displaystyle C_{2}$
$\displaystyle=\frac{2\delta}{1-\gamma}\left(1+\frac{\gamma}{\eta\tau}\right)$
(D.30)

The equation (D.29) holds since the policy that the agent executes at the
episode $k$, i.e. $\pi^{k}$ or $\widehat{\pi}^{(k-1)+1}$, is same as the
initial policy of the policy iteration, i.e. $\widehat{\pi}^{(0)}$ at the
episode $k$. Also, the policy that the agent executes at the episode $k+1$,
i.e. $\widehat{\pi}^{k+1}$, is same as the policy after $G$ steps of soft
policy iteration, i.e. $\widehat{\pi}^{(\Delta_{\pi})}$ at the episode $k$.

Then, the term 2.2 can be bounded as follows.

2.2
$\displaystyle=||\widehat{V}^{\bigast,k+1}_{\tau}-\widehat{V}^{\widehat{\pi}^{k+1}}_{\tau}||_{\infty}$
$\displaystyle=||\widehat{V}^{\bigast,k+1}_{\tau}-\widehat{V}^{\widehat{\pi}^{(\Delta_{\pi})}}_{\tau}||_{\infty}$
$\displaystyle\leq||\widehat{Q}^{\bigast,k+1}_{\tau}-\widehat{Q}^{\widehat{\pi}^{(\Delta_{\pi})}}_{\tau}||_{\infty}+\tau||\log\widehat{\pi}^{\bigast,k+1}-\log\widehat{\pi}^{(\Delta_{\pi})}||_{\infty}$
$\displaystyle\leq\left(\gamma+2\right)\left[(1-\eta\tau)^{\Delta_{\pi}-1}C_{1}+C_{2}\right]$
(D.31)

Then combining the equation (D.23,D.26,D.31) offers the upper bound of the
term 2’s $k^{(th)}$ term as follows,

$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\text{'s}~{}(k)^{th}~{}\text{term}$
$\displaystyle=\widehat{V}^{\widehat{\pi}^{\bigast,k+1},k+1}(s_{0})-\widehat{V}^{\widehat{\pi}^{k+1},k+1}(s_{0})$
$\displaystyle\leq\left(\gamma+2\right)\left[(1-\eta\tau)^{\Delta_{\pi}-1}C_{1}+C_{2}\right]+\frac{2\gamma^{H}\widehat{r}_{\text{max}}}{1-\gamma}+\frac{2\tau\log|\mathcal{A}|}{1-\gamma}$
(D.32)

and the upper bound of the term 2.

2
$\displaystyle=\sum_{k=1}^{K-1}\left(\widehat{V}^{\widehat{\pi}^{\bigast,k+1},k+1}(s_{0})-\widehat{V}^{\widehat{\pi}^{k+1},k+1}(s_{0})\right)$
$\displaystyle\leq(K-1)\left(\left(\gamma+2\right)\left[(1-\eta\tau)^{\Delta_{\pi}-1}C_{1}+C_{2}\right]+\frac{2\gamma^{H}\widehat{r}_{\text{max}}}{1-\gamma}+\frac{2\tau\log|\mathcal{A}|}{1-\gamma}\right)$
(D.33)

where the equation (D.32), (D.33) only holds when
$0\leq\eta\leq(1-\gamma)/\tau$

3\. Upper bound of 3.

Recall from the Definition (C.3), note that
$\iota^{k+1}_{h}(\widehat{s}^{k+1}_{h},\widehat{a}^{k+1}_{h})$ is a empirical
estimated model prediction error, the gap between $\mathcal{M}_{(k+1)}$ and
$\widehat{\mathcal{M}}_{(k+1)}$. Specifically, at episode $k$, the meta-
algorithm creates the future MDP $\widehat{\mathcal{M}}_{(k+1)}$ and evaluates
$\widehat{V},\widehat{Q}$ using $\widehat{\pi}^{k+1}$, then at episode $k+1$,
the agent uses $\widehat{\pi}^{k+1}$ to rollout a trajectory
$\\{s^{k+1}_{0},a^{k+1}_{0},s^{k+1}_{1},a^{k+1}_{1},...,s^{k+1}_{H-1},a^{k+1}_{H-1},s^{k+1}_{H}\\}$.
Its term can be expanded as follows,

$\displaystyle\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})=$ $\displaystyle
R^{(k+1)}(s^{k+1}_{h},a^{k+1}_{h})+\gamma(P^{(k+1)}\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1})(s^{k+1}_{h},a^{k+1}_{h})-\widehat{Q}^{\widehat{\pi}^{k+1},k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle=$ $\displaystyle
R^{(k+1)}(s^{k+1}_{h},a^{k+1}_{h})+\gamma(P^{(k+1)}\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1})(s^{k+1}_{h},a^{k+1}_{h})-Q^{\widehat{\pi}^{k+1},k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle+Q^{\widehat{\pi}^{k+1},k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})-\widehat{Q}^{\widehat{\pi}^{k+1},k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle=$ $\displaystyle\gamma
P^{(k+1)}(\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}-V^{\widehat{\pi}^{k+1},k+1}_{h+1})(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle+Q^{\widehat{\pi}^{k+1},k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})-\widehat{Q}^{\widehat{\pi}^{k+1},k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$
(D.34)

Equation (D.34) holds from the future-bellman equation (C.1) holds for
$(s,a)$. Now, define the operator $\widehat{\mathfrak{I}}^{k+1}$ for any
function $f:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ as follows.

$\displaystyle(\widehat{\mathfrak{I}}^{k+1}f)(s)\coloneqq\langle
f(s,\cdot),\widehat{\pi}^{k+1}(\cdot|s)\rangle_{\mathcal{A}}$

Recall that
$\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h}(s)=\big{<}\widehat{Q}^{\widehat{\pi}^{k+1},k+1}_{h},\widehat{\pi}^{k+1}\big{>}_{\mathcal{A}}$
and
$V^{\widehat{\pi}^{k+1},k+1}_{h}(s)=\big{<}Q^{\widehat{\pi}^{k+1},k+1}_{h},\widehat{\pi}^{k+1}\big{>}_{\mathcal{A}}$
holds from equation (C.1) and (C.4) respectively. Then, the gap between
$\widehat{V}_{h+1}^{\widehat{\pi}^{k+1},k+1}(s^{k+1}_{h})$ and
$V^{\widehat{\pi}^{k+1},k+1}_{h+1}(s^{k+1}_{h})$ can be expanded as follows,

$\displaystyle\widehat{V}_{h}^{\widehat{\pi}^{k+1},k+1}(s^{k+1}_{h})-V^{\widehat{\pi}^{k+1},k+1}_{h}(s^{k+1}_{h})$
$\displaystyle=\left(\widehat{\mathfrak{I}}^{k+1}\left(\widehat{Q}_{h}^{\widehat{\pi}^{k+1},k+1}-Q^{\widehat{\pi}^{k+1},k+1}_{h}\right)\right)(s^{k+1}_{h})$
$\displaystyle=\left(\widehat{\mathfrak{I}}^{k+1}\left(\widehat{Q}_{h}^{\widehat{\pi}^{k+1},k+1}-Q^{\widehat{\pi}^{k+1},k+1}_{h}\right)\right)(s^{k+1}_{h})-\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle\text{ }+\gamma
P^{(k+1)}(\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}-V^{\widehat{\pi}^{k+1},k+1}_{h+1})(s^{k+1}_{h},a^{k+1}_{h})+\left(Q^{\widehat{\pi}^{k+1},k+1}_{h}-\widehat{Q}^{\widehat{\pi}^{k+1},k+1}_{h}\right)(s^{k+1}_{h},a^{k+1}_{h})$

Now, we define two sequences $\\{D^{k+1}_{h,1}\\},\\{D^{k+1}_{h,1}\\}$ where
$(k,h)=(0,0),(0,1),...,(K-1,H)$. We define $D^{k+1}_{h,1},D^{k+1}_{h,2}$ as
follows.

$\displaystyle D^{k+1}_{h,1}$
$\displaystyle\coloneqq\gamma^{h}\left(\widehat{\mathfrak{I}}^{k+1}\left(\widehat{Q}_{h}^{\widehat{\pi}^{k+1},k+1}-Q^{\widehat{\pi}^{k+1},k+1}_{h}\right)\right)(s^{k+1}_{h})-\gamma^{h}\left(\widehat{Q}^{\widehat{\pi}^{k+1},k+1}_{h}-Q^{\widehat{\pi}^{k+1},k+1}_{h}\right)(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle D^{k+1}_{h,2}$
$\displaystyle\coloneqq\gamma^{h+1}P^{(k+1)}(\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}-V^{\widehat{\pi}^{k+1},k+1}_{h+1})(s^{k+1}_{h},a^{k+1}_{h})-\gamma^{h+1}\left(\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}-V^{\widehat{\pi}^{k+1},k+1}_{h+1}\right)(s^{k+1}_{h+1})$

Therefore, we have the following recursive formula over $h$,

$\displaystyle\gamma^{h}\left(\widehat{V}_{h}^{\widehat{\pi}^{k+1},k+1}-V^{\widehat{\pi}^{k+1},k+1}_{h}\right)(s^{k+1}_{h})$
$\displaystyle=D^{k+1}_{h,1}+D^{k+1}_{h,2}+\gamma^{h+1}\left(\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}-V^{\widehat{\pi}^{k+1},k+1}_{h+1}\right)\left(s^{k+1}_{h+1}\right)-\gamma^{h}\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$

and summation over $h=0,1,..,H-1$ yields the following expression,

$\displaystyle\widehat{V}_{0}^{\widehat{\pi}^{k+1},k+1}(s^{k+1}_{0})-V^{\widehat{\pi}^{k+1},k+1}_{0}(s^{k+1}_{0})$
$\displaystyle=\sum_{h=0}^{H-1}\left(D^{k+1}_{h,1}+D^{k+1}_{h,2}\right)-\sum_{h=0}^{H-1}\gamma^{h}\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$

.Now, for every $(k,h)\in[K]\times[H]$, we define $\mathcal{F}^{k}_{h,1}$ as a
$\sigma-$algebra generated by state-action sequences
$\\{(s^{\tau}_{i},a^{\tau}_{i})\\}_{(\tau,i)\in[k-1]\times[H]}\cup\\{(s_{i}^{k},a_{i}^{k})\\}_{i\in[h]}$
and define $\mathcal{F}^{k}_{h,2}$ as an $\sigma$-algebra generated by
$\\{(s^{\tau}_{i},a^{\tau}_{i})\\}_{(\tau,i)\in[k-1]\times[H]}\cup\\{(s_{i}^{k},a_{i}^{k})\\}_{i\in[h]}\cup\\{s^{k}_{h+1}\\}$.
A filtration $\\{\mathcal{F}^{k}_{h,m}\\}_{(k,h,m)\in[K]\times[H]\times[2]}$
is a sequence of $\sigma$\- algebras in a terms of the time index
$t(k,h,m)=2(k-1)H+2h+m$ such that
$\mathcal{F}^{k}_{h,m}\subset\mathcal{F}^{k^{\prime}}_{h^{\prime},m^{\prime}}$
for every $t(k,h,m)\leq t(k^{\prime},h^{\prime},m^{\prime})$. The estimated
$\widehat{V}^{\pi,k+1}_{h},\widehat{Q}^{\pi,k+1}_{h}$ are
$\mathcal{F}^{k+1}_{1,1}$ measurable since they are forecasted from past $k$
historical trajectories. Now, since $D^{k+1}_{h,1}\in\mathcal{F}^{k+1}_{h,1}$
and $D^{k+1}_{h,2}\in\mathcal{F}^{k+1}_{h,2}$ holds,
$\mathbb{E}[D^{k+1}_{h,1}|\mathcal{F}^{k+1}_{h-1,2}]=0$ and
$\mathbb{E}[D^{k+1}_{h,2}|\mathcal{F}^{k+1}_{h,1}]=0$ holds. Notice that
$t(k,0,2)=t(k-1,H,2)$ and $\mathcal{F}^{k}_{0,2}=\mathcal{F}^{k-1}_{H,2}$ for
$\forall k\geq 2$. Therefore, we can define the martingale sequence which is
adapted to the filtration
$\\{\mathcal{F}^{k}_{h,m}\\}_{(k,h,m)\in[K]\times[H]\times[2]}$ ,

$\displaystyle
S^{k+1}_{h,j}=\sum_{k^{\prime}=1}^{k}\sum_{h^{\prime}=0}^{H-1}\left(D^{k^{\prime}}_{h^{\prime},1}+D^{k^{\prime}}_{h^{\prime},2}\right)+\sum_{h^{\prime}=0}^{h}\left(D^{k+1}_{h^{\prime},1}+D^{k+1}_{h^{\prime},2}\right)+\sum_{(k^{\prime},h^{\prime},j)\in[K]\times[H]\times[2]}D^{k^{\prime}}_{h^{\prime},j}$

Then let

$\displaystyle\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\left(D^{k+1}_{h,1}+D^{k+1}_{h,2}\right)=S^{K-1}_{H,2}$

Since
$\gamma^{h}\widehat{Q}_{h}^{\widehat{\pi}^{k+1},k+1},\gamma^{h+1}\widehat{V}_{h+1}^{\widehat{\pi}^{k+1},k+1}\in[0,\hat{r}_{\text{max}}/(1-\gamma)]$
and
$\gamma^{h}Q_{h}^{\widehat{\pi}^{k+1},k+1},\gamma^{h+1}V_{h+1}^{\widehat{\pi}^{k+1},k+1}\in[0,r_{\text{max}}/(1-\gamma)]$.
Then
$|D^{k+1}_{h,1}|,~{}|D^{k+1}_{h,s}|\leq(r_{\text{max}}\vee\hat{r}_{\text{max}})/(1-\gamma)$
holds for $\forall(k,h)\in[K-1]\times[H]$. Then, by the Azuma-Hoeffding
inequlaity, the following inequality holds.

$\mathbb{P}\left(|S^{K-1}_{H,2}|\leq s\right)\geq
2\exp\left(\frac{-s^{2}}{16\left(\frac{r_{\text{max}}\vee\hat{r}_{\text{max}}}{1-\gamma}\right)^{2}\cdot(K-1)H}\right)$

For any $p\in(0,1)$, if we set
$s=4(r_{\text{max}}\vee\hat{r}_{\text{max}})(1-\gamma)^{-1}\sqrt{(K-1)H\log(4/p)}$,
then the inequality holds with probability at least $1-p/2$.

Finally, for given $p\in(0,1)$, the term 3 can be bounded as follows,

3
$\displaystyle=\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\left(D^{k+1}_{h,1}+D^{k+1}_{h,2}\right)-\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\gamma^{h}\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle\leq\frac{4(r_{\text{max}}\vee\hat{r}_{\text{max}})}{1-\gamma}\sqrt{(K-1)H\log(4/p)}-\iota^{K-1}_{H}$
(D.35)

where we have defined
$\iota^{K-1}_{H}=\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\gamma^{h}\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$

4\. Upper bound of dynamic regret.

4.1. Upper bound of dynamic regret - without entropy regularization.

Finally, for the entropy-regularized case, combining the equations (D.21),
(D.25), (D.35) gives us the upper bound of dynamic regret of future policy
$\\{\widehat{\pi}\\}$ that holds with probability $1-p/2$.

$\displaystyle\mathfrak{R}\left(\\{\widehat{\pi}^{k+1}\\}_{1:K-1},K)\right)$
$\displaystyle=\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to9.93pt{\vbox to9.93pt{\pgfpicture\makeatletter\hbox{\hskip
4.9644pt\lower-4.9644pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to9.93pt{\vbox to9.93pt{\pgfpicture\makeatletter\hbox{\hskip
4.9644pt\lower-4.9644pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leq(K-1)\cdot\frac{\gamma^{H}}{1-\gamma}(r_{\text{max}}+\hat{r}_{\text{max}})+\frac{1}{1-\gamma}\bar{\iota}_{\infty}^{K}$
$\displaystyle+(K-1)\left(\frac{1}{(1-\gamma)^{2}\Delta_{\pi}}+\frac{\log{|\mathcal{A}|}}{\eta\Delta_{\pi}}+\frac{2\gamma^{H}\widehat{r}_{\text{max}}}{1-\gamma}\right)$
$\displaystyle+\frac{4(r_{\text{max}}\vee\hat{r}_{\text{max}})}{1-\gamma}\sqrt{(K-1)H\log(4/p)}-\iota^{K-1}_{H}$

Taking a upper bound of $r_{\text{max}},~{}\hat{r}_{\text{max}}$ using
$(r_{\text{max}}\vee\hat{r}_{\text{max}})$ yields the following final upper
bound that holds with probability $1-p/2$,

$\displaystyle\mathfrak{R}\left(\\{\widehat{\pi}^{k+1}\\}_{1:K-1},K)\right)$
$\displaystyle\leq(K-1)\bigg{(}\frac{1}{(1-\gamma)^{2}\Delta_{\pi}}+\frac{\log{|\mathcal{A}|}}{\eta\Delta_{\pi}}+\frac{4\gamma^{H}(\widehat{r}_{\text{max}}\vee
r_{\text{max}})}{1-\gamma}$
$\displaystyle+\frac{4(r_{\text{max}}\vee\hat{r}_{\text{max}})}{1-\gamma}\sqrt{\frac{H\log(4/p)}{K-1}}\bigg{)}+\frac{1}{1-\gamma}\bar{\iota}_{\infty}^{K}-\iota^{K-1}_{H}$

4.2. Upper bound of dynamic regret - with entropy regularization.

Finally, for the entropy-regularized case, combining the equations (D.21),
(D.33), (D.35) gives us the upper bound of dynamic regret of future policy
$\\{\widehat{\pi}\\}$ that holds with probability at least $1-p/2$.

$\displaystyle\mathfrak{R}\left(\\{\widehat{\pi}^{k+1}\\}_{1:K-1},K)\right)$
$\displaystyle=\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to9.93pt{\vbox to9.93pt{\pgfpicture\makeatletter\hbox{\hskip
4.9644pt\lower-4.9644pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to9.93pt{\vbox to9.93pt{\pgfpicture\makeatletter\hbox{\hskip
4.9644pt\lower-4.9644pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leq(K-1)\cdot\frac{\gamma^{H}}{1-\gamma}(r_{\text{max}}+\hat{r}_{\text{max}})+\frac{1}{1-\gamma}\bar{\iota}_{\infty}^{K}$
$\displaystyle+(K-1)\left(\left(\gamma+2\right)\left[(1-\eta\tau)^{\Delta_{\pi}-1}C_{1}+C_{2}\right]+\frac{2\gamma^{H}\widehat{r}_{\text{max}}}{1-\gamma}+\frac{2\tau\log|\mathcal{A}|}{1-\gamma}\right)$
$\displaystyle+\frac{4(r_{\text{max}}\vee\hat{r}_{\text{max}})}{1-\gamma}\sqrt{(K-1)H\log(4/p)}-\iota^{K-1}_{H}$

Taking a upper bound of $r_{\text{max}},~{}\hat{r}_{\text{max}}$ using
$(r_{\text{max}}\vee\hat{r}_{\text{max}})$ yields the following final upper
bound that holds with probability at least $1-p/2$,

$\displaystyle\mathfrak{R}\left(\\{\widehat{\pi}^{k+1}\\}_{1:K-1},K)\right)$
$\displaystyle\leq(K-1)\bigg{(}\left(\gamma+2\right)\left[(1-\eta\tau)^{\Delta_{\pi}-1}C_{1}+C_{2}\right]+\frac{4\gamma^{H}(\widehat{r}_{\text{max}}\vee
r_{\text{max}})}{1-\gamma}+\frac{2\tau\log|\mathcal{A}|}{1-\gamma}$
$\displaystyle+\frac{4(r_{\text{max}}\vee\hat{r}_{\text{max}})}{1-\gamma}\sqrt{\frac{H\log(4/p)}{K-1}}\bigg{)}+\frac{1}{1-\gamma}\bar{\iota}_{\infty}^{K}-\iota^{K-1}_{H}$

Then, combining 4.1, 4.2 provides the following expression,

$\mathfrak{R}\left(\\{\widehat{\pi}^{k+1}\\}_{1:K-1},K)\right)\leq\mathfrak{R}_{\mathcal{I}}+\mathfrak{R}_{\maltese}$

where

$\displaystyle\mathfrak{R}_{\mathcal{I}}=\frac{1}{1-\gamma}\bar{\iota}_{\infty}^{K}-\iota^{K}_{H}+C_{p}\sqrt{K-1}$
$\displaystyle\mathfrak{R}_{\texttt{Alg}}=C_{\texttt{Alg}}(\Delta_{\pi})\cdot(K-1)$
$\displaystyle\mathfrak{R}_{\texttt{Alg}_{\tau}}=C_{\texttt{Alg}_{\tau}}(\Delta_{\pi})\cdot(K-1)$

and corresponding constants are

$\displaystyle
C_{p}=\frac{4(r_{\text{max}}\vee\hat{r}_{\text{max}})}{1-\gamma}\sqrt{H\log(4/p)},~{}~{}C_{\texttt{Alg}}(\Delta_{\pi})=\left(\frac{1}{(1-\gamma)^{2}}+\frac{\log{|\mathcal{A}|}}{\eta}\right)\cdot\frac{1}{\Delta_{\pi}}+\frac{4\gamma^{H}(\widehat{r}_{\text{max}}\vee
r_{\text{max}})}{1-\gamma}$ $\displaystyle
C_{\texttt{Alg}_{\tau}}(\Delta_{\pi})=\left(\gamma+2\right)\left[(1-\eta\tau)^{\Delta_{\pi}-1}C_{1}+C_{2}\right]+\frac{4\gamma^{H}(\widehat{r}_{\text{max}}\vee
r_{\text{max}})}{1-\gamma}+\frac{2\tau\log|\mathcal{A}|}{1-\gamma}$

∎

######  Lemma 1 (Conditions on $\Delta_{\pi},H$ to guarantee the optimal
threshold $2\epsilon$ of 2 without entropy regularization).

Let us estimate the conditions on $\tau,\eta,\Delta_{\pi},H$ when the each
terms of RHS of the equation (D.32) is bounded by $\epsilon$ as follows,

$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\text{'s}~{}(k)^{th}~{}\text{term}=\underbrace{\frac{1}{(1-\gamma)^{2}\Delta_{\pi}}+\frac{\log{|\mathcal{A}|}}{\eta\Delta_{\pi}}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to6.43pt{\vbox to6.43pt{\pgfpicture\makeatletter\hbox{\hskip
3.21562pt\lower-3.21562pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.01563pt}{0.0pt}\pgfsys@curveto{3.01563pt}{1.6655pt}{1.6655pt}{3.01563pt}{0.0pt}{3.01563pt}\pgfsys@curveto{-1.6655pt}{3.01563pt}{-3.01563pt}{1.6655pt}{-3.01563pt}{0.0pt}\pgfsys@curveto{-3.01563pt}{-1.6655pt}{-1.6655pt}{-3.01563pt}{0.0pt}{-3.01563pt}\pgfsys@curveto{1.6655pt}{-3.01563pt}{3.01563pt}{-1.6655pt}{3.01563pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-1.50694pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{a}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}~{}\leq~{}\epsilon}+\underbrace{\frac{2\gamma^{H}\widehat{r}_{\text{max}}}{1-\gamma}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to8.02pt{\vbox to8.02pt{\pgfpicture\makeatletter\hbox{\hskip
4.0081pt\lower-4.0081pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.8081pt}{0.0pt}\pgfsys@curveto{3.8081pt}{2.10318pt}{2.10318pt}{3.8081pt}{0.0pt}{3.8081pt}\pgfsys@curveto{-2.10318pt}{3.8081pt}{-3.8081pt}{2.10318pt}{-3.8081pt}{0.0pt}\pgfsys@curveto{-3.8081pt}{-2.10318pt}{-2.10318pt}{-3.8081pt}{0.0pt}{-3.8081pt}\pgfsys@curveto{2.10318pt}{-3.8081pt}{3.8081pt}{-2.10318pt}{3.8081pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.94444pt}{-2.43054pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{b}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}~{}\leq~{}\epsilon}$

The term $\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to8.4pt{\vbox to8.4pt{\pgfpicture\makeatletter\hbox{\hskip
4.2pt\lower-4.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.0pt}{0.0pt}\pgfsys@curveto{4.0pt}{2.20917pt}{2.20917pt}{4.0pt}{0.0pt}{4.0pt}\pgfsys@curveto{-2.20917pt}{4.0pt}{-4.0pt}{2.20917pt}{-4.0pt}{0.0pt}\pgfsys@curveto{-4.0pt}{-2.20917pt}{-2.20917pt}{-4.0pt}{0.0pt}{-4.0pt}\pgfsys@curveto{2.20917pt}{-4.0pt}{4.0pt}{-2.20917pt}{4.0pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-2.15277pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{a}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox
to10.67pt{\vbox to10.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.33574pt\lower-5.33574pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.13574pt}{0.0pt}\pgfsys@curveto{5.13574pt}{2.83643pt}{2.83643pt}{5.13574pt}{0.0pt}{5.13574pt}\pgfsys@curveto{-2.83643pt}{5.13574pt}{-5.13574pt}{2.83643pt}{-5.13574pt}{0.0pt}\pgfsys@curveto{-5.13574pt}{-2.83643pt}{-2.83643pt}{-5.13574pt}{0.0pt}{-5.13574pt}\pgfsys@curveto{2.83643pt}{-5.13574pt}{5.13574pt}{-2.83643pt}{5.13574pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{b}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ provides the
following conditions,

$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to8.4pt{\vbox to8.4pt{\pgfpicture\makeatletter\hbox{\hskip
4.2pt\lower-4.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.0pt}{0.0pt}\pgfsys@curveto{4.0pt}{2.20917pt}{2.20917pt}{4.0pt}{0.0pt}{4.0pt}\pgfsys@curveto{-2.20917pt}{4.0pt}{-4.0pt}{2.20917pt}{-4.0pt}{0.0pt}\pgfsys@curveto{-4.0pt}{-2.20917pt}{-2.20917pt}{-4.0pt}{0.0pt}{-4.0pt}\pgfsys@curveto{2.20917pt}{-4.0pt}{4.0pt}{-2.20917pt}{4.0pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-2.15277pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{a}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle:\Delta_{\pi}\geq\left(\frac{1}{(1-\gamma)^{2}}+\frac{\log{|\mathcal{A}|}}{\eta}\right)\cdot\frac{1}{\epsilon}$
$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to10.67pt{\vbox to10.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.33574pt\lower-5.33574pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.13574pt}{0.0pt}\pgfsys@curveto{5.13574pt}{2.83643pt}{2.83643pt}{5.13574pt}{0.0pt}{5.13574pt}\pgfsys@curveto{-2.83643pt}{5.13574pt}{-5.13574pt}{2.83643pt}{-5.13574pt}{0.0pt}\pgfsys@curveto{-5.13574pt}{-2.83643pt}{-2.83643pt}{-5.13574pt}{0.0pt}{-5.13574pt}\pgfsys@curveto{2.83643pt}{-5.13574pt}{5.13574pt}{-2.83643pt}{5.13574pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{b}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle:H\geq\frac{\log(\frac{1-\gamma}{2\widehat{r}_{\text{max}}}\epsilon)}{\log(\gamma)}$
$\displaystyle:H\geq\frac{1}{1-\gamma}\log\left(\frac{2\widehat{r}_{\text{max}}}{(1-\gamma)\epsilon}\right)$

######  Lemma 2 (Conditions on $\tau,\Delta_{\pi},H$ to guarantee the optimal
threshold $4\epsilon$ of 2 with entropy regularization).

Let us estimate the conditions on $\tau,\eta,\Delta_{\pi},H$ when the each
terms of RHS of the equation (D.32) is bounded by $\epsilon$ as follows,

$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\text{'s}~{}(k)^{th}~{}\text{term}=\underbrace{\left(\gamma+2\right)\left[(1-\eta\tau)^{\Delta_{\pi}-1}C_{1}\right]}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to6.43pt{\vbox to6.43pt{\pgfpicture\makeatletter\hbox{\hskip
3.21562pt\lower-3.21562pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.01563pt}{0.0pt}\pgfsys@curveto{3.01563pt}{1.6655pt}{1.6655pt}{3.01563pt}{0.0pt}{3.01563pt}\pgfsys@curveto{-1.6655pt}{3.01563pt}{-3.01563pt}{1.6655pt}{-3.01563pt}{0.0pt}\pgfsys@curveto{-3.01563pt}{-1.6655pt}{-1.6655pt}{-3.01563pt}{0.0pt}{-3.01563pt}\pgfsys@curveto{1.6655pt}{-3.01563pt}{3.01563pt}{-1.6655pt}{3.01563pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-1.50694pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{a}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}~{}\leq~{}\epsilon}+\underbrace{\left(\gamma+2\right)C_{2}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to8.02pt{\vbox to8.02pt{\pgfpicture\makeatletter\hbox{\hskip
4.0081pt\lower-4.0081pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.8081pt}{0.0pt}\pgfsys@curveto{3.8081pt}{2.10318pt}{2.10318pt}{3.8081pt}{0.0pt}{3.8081pt}\pgfsys@curveto{-2.10318pt}{3.8081pt}{-3.8081pt}{2.10318pt}{-3.8081pt}{0.0pt}\pgfsys@curveto{-3.8081pt}{-2.10318pt}{-2.10318pt}{-3.8081pt}{0.0pt}{-3.8081pt}\pgfsys@curveto{2.10318pt}{-3.8081pt}{3.8081pt}{-2.10318pt}{3.8081pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.94444pt}{-2.43054pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{b}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}~{}\leq~{}\epsilon}+\underbrace{\frac{2\gamma^{H}\widehat{r}_{\text{max}}}{1-\gamma}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to6.15pt{\vbox to6.15pt{\pgfpicture\makeatletter\hbox{\hskip
3.07549pt\lower-3.07549pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.87549pt}{0.0pt}\pgfsys@curveto{2.87549pt}{1.5881pt}{1.5881pt}{2.87549pt}{0.0pt}{2.87549pt}\pgfsys@curveto{-1.5881pt}{2.87549pt}{-2.87549pt}{1.5881pt}{-2.87549pt}{0.0pt}\pgfsys@curveto{-2.87549pt}{-1.5881pt}{-1.5881pt}{-2.87549pt}{0.0pt}{-2.87549pt}\pgfsys@curveto{1.5881pt}{-2.87549pt}{2.87549pt}{-1.5881pt}{2.87549pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.55556pt}{-1.50694pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{c}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}~{}\leq~{}\epsilon}+\underbrace{\frac{2\tau\log|\mathcal{A}|}{1-\gamma}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to8.02pt{\vbox to8.02pt{\pgfpicture\makeatletter\hbox{\hskip
4.0081pt\lower-4.0081pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.8081pt}{0.0pt}\pgfsys@curveto{3.8081pt}{2.10318pt}{2.10318pt}{3.8081pt}{0.0pt}{3.8081pt}\pgfsys@curveto{-2.10318pt}{3.8081pt}{-3.8081pt}{2.10318pt}{-3.8081pt}{0.0pt}\pgfsys@curveto{-3.8081pt}{-2.10318pt}{-2.10318pt}{-3.8081pt}{0.0pt}{-3.8081pt}\pgfsys@curveto{2.10318pt}{-3.8081pt}{3.8081pt}{-2.10318pt}{3.8081pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.94444pt}{-2.43054pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{d}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}~{}\leq~{}\epsilon}$

The term $\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to10.67pt{\vbox to10.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.33574pt\lower-5.33574pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.13574pt}{0.0pt}\pgfsys@curveto{5.13574pt}{2.83643pt}{2.83643pt}{5.13574pt}{0.0pt}{5.13574pt}\pgfsys@curveto{-2.83643pt}{5.13574pt}{-5.13574pt}{2.83643pt}{-5.13574pt}{0.0pt}\pgfsys@curveto{-5.13574pt}{-2.83643pt}{-2.83643pt}{-5.13574pt}{0.0pt}{-5.13574pt}\pgfsys@curveto{2.83643pt}{-5.13574pt}{5.13574pt}{-2.83643pt}{5.13574pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{b}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox
to7.97pt{\vbox to7.97pt{\pgfpicture\makeatletter\hbox{\hskip
3.98735pt\lower-3.98735pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.78735pt}{0.0pt}\pgfsys@curveto{3.78735pt}{2.09172pt}{2.09172pt}{3.78735pt}{0.0pt}{3.78735pt}\pgfsys@curveto{-2.09172pt}{3.78735pt}{-3.78735pt}{2.09172pt}{-3.78735pt}{0.0pt}\pgfsys@curveto{-3.78735pt}{-2.09172pt}{-2.09172pt}{-3.78735pt}{0.0pt}{-3.78735pt}\pgfsys@curveto{2.09172pt}{-3.78735pt}{3.78735pt}{-2.09172pt}{3.78735pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.22221pt}{-2.15277pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{c}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox
to10.67pt{\vbox to10.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.33574pt\lower-5.33574pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.13574pt}{0.0pt}\pgfsys@curveto{5.13574pt}{2.83643pt}{2.83643pt}{5.13574pt}{0.0pt}{5.13574pt}\pgfsys@curveto{-2.83643pt}{5.13574pt}{-5.13574pt}{2.83643pt}{-5.13574pt}{0.0pt}\pgfsys@curveto{-5.13574pt}{-2.83643pt}{-2.83643pt}{-5.13574pt}{0.0pt}{-5.13574pt}\pgfsys@curveto{2.83643pt}{-5.13574pt}{5.13574pt}{-2.83643pt}{5.13574pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{d}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ provides the
following conditions as follows,

$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to10.67pt{\vbox to10.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.33574pt\lower-5.33574pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.13574pt}{0.0pt}\pgfsys@curveto{5.13574pt}{2.83643pt}{2.83643pt}{5.13574pt}{0.0pt}{5.13574pt}\pgfsys@curveto{-2.83643pt}{5.13574pt}{-5.13574pt}{2.83643pt}{-5.13574pt}{0.0pt}\pgfsys@curveto{-5.13574pt}{-2.83643pt}{-2.83643pt}{-5.13574pt}{0.0pt}{-5.13574pt}\pgfsys@curveto{2.83643pt}{-5.13574pt}{5.13574pt}{-2.83643pt}{5.13574pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{b}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle:\delta\leq\frac{\epsilon}{(\gamma+2)\cdot\frac{2}{1-\gamma}\cdot(1+\frac{\gamma}{\eta\tau})}$
(D.36) $\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to7.97pt{\vbox to7.97pt{\pgfpicture\makeatletter\hbox{\hskip
3.98735pt\lower-3.98735pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.78735pt}{0.0pt}\pgfsys@curveto{3.78735pt}{2.09172pt}{2.09172pt}{3.78735pt}{0.0pt}{3.78735pt}\pgfsys@curveto{-2.09172pt}{3.78735pt}{-3.78735pt}{2.09172pt}{-3.78735pt}{0.0pt}\pgfsys@curveto{-3.78735pt}{-2.09172pt}{-2.09172pt}{-3.78735pt}{0.0pt}{-3.78735pt}\pgfsys@curveto{2.09172pt}{-3.78735pt}{3.78735pt}{-2.09172pt}{3.78735pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.22221pt}{-2.15277pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{c}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle:H\geq\frac{\log(\frac{1-\gamma}{2\widehat{r}_{\text{max}}}\epsilon)}{\log(\gamma)}$
$\displaystyle:H\geq\frac{1}{1-\gamma}\log\left(\frac{2\widehat{r}_{\text{max}}}{(1-\gamma)\epsilon}\right)$
(D.37) $\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to10.67pt{\vbox to10.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.33574pt\lower-5.33574pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.13574pt}{0.0pt}\pgfsys@curveto{5.13574pt}{2.83643pt}{2.83643pt}{5.13574pt}{0.0pt}{5.13574pt}\pgfsys@curveto{-2.83643pt}{5.13574pt}{-5.13574pt}{2.83643pt}{-5.13574pt}{0.0pt}\pgfsys@curveto{-5.13574pt}{-2.83643pt}{-2.83643pt}{-5.13574pt}{0.0pt}{-5.13574pt}\pgfsys@curveto{2.83643pt}{-5.13574pt}{5.13574pt}{-2.83643pt}{5.13574pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{d}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle:\tau\leq\frac{1-\gamma}{2\log|\mathcal{A}|}\epsilon$ (D.38)

and the term $\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to8.4pt{\vbox to8.4pt{\pgfpicture\makeatletter\hbox{\hskip
4.2pt\lower-4.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.0pt}{0.0pt}\pgfsys@curveto{4.0pt}{2.20917pt}{2.20917pt}{4.0pt}{0.0pt}{4.0pt}\pgfsys@curveto{-2.20917pt}{4.0pt}{-4.0pt}{2.20917pt}{-4.0pt}{0.0pt}\pgfsys@curveto{-4.0pt}{-2.20917pt}{-2.20917pt}{-4.0pt}{0.0pt}{-4.0pt}\pgfsys@curveto{2.20917pt}{-4.0pt}{4.0pt}{-2.20917pt}{4.0pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-2.15277pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{a}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ offers the lower
bound of iteration $\Delta_{\pi}$ as follows.

$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to8.4pt{\vbox to8.4pt{\pgfpicture\makeatletter\hbox{\hskip
4.2pt\lower-4.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.0pt}{0.0pt}\pgfsys@curveto{4.0pt}{2.20917pt}{2.20917pt}{4.0pt}{0.0pt}{4.0pt}\pgfsys@curveto{-2.20917pt}{4.0pt}{-4.0pt}{2.20917pt}{-4.0pt}{0.0pt}\pgfsys@curveto{-4.0pt}{-2.20917pt}{-2.20917pt}{-4.0pt}{0.0pt}{-4.0pt}\pgfsys@curveto{2.20917pt}{-4.0pt}{4.0pt}{-2.20917pt}{4.0pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-2.15277pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{a}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle:\Delta_{\pi}\geq\frac{\log\left(\frac{\epsilon}{C_{1}(\gamma+2)}\right)}{\log(1-\eta\tau)}+1$
$\displaystyle:\Delta_{\pi}\geq\frac{1}{\eta\tau}\log\left(\frac{C_{1}(\gamma+2)}{\epsilon}\right)+1$
(D.39)

The equation (D.37), (D.39) holds by applying first order Taylor series on
$\log(\gamma),~{}\log(1-\eta\tau)$ since
$\gamma\in(0,1],~{}\eta\in(0,(1-\gamma)/\tau]$. The equation (D.36), (D.39)
implies that if the learning rate $\eta$ is fixed in the admissible range,
then the iteration complexity scales inversely proportional with $\tau$, and
the approximation gap bound ($\delta_{\text{max}}$) also scales proportional
with $\tau$.

Now, the best convergence guaranteed is achieved when
$\eta^{*}=(1-\gamma)/\tau$ (The $\eta$ that minimizes the equation (D.29)),
the condition of hyperparameters $\Delta_{\pi,\eta^{*}},\delta_{\eta^{*}}$ are
given as follows,

$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to8.4pt{\vbox to8.4pt{\pgfpicture\makeatletter\hbox{\hskip
4.2pt\lower-4.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.0pt}{0.0pt}\pgfsys@curveto{4.0pt}{2.20917pt}{2.20917pt}{4.0pt}{0.0pt}{4.0pt}\pgfsys@curveto{-2.20917pt}{4.0pt}{-4.0pt}{2.20917pt}{-4.0pt}{0.0pt}\pgfsys@curveto{-4.0pt}{-2.20917pt}{-2.20917pt}{-4.0pt}{0.0pt}{-4.0pt}\pgfsys@curveto{2.20917pt}{-4.0pt}{4.0pt}{-2.20917pt}{4.0pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-2.15277pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{a}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle:\Delta_{\pi,\eta^{*}}\geq\frac{1}{1-\gamma}\log\left(\frac{||\widehat{Q}^{\bigast,k+1}_{\tau}-\widehat{Q}^{\widehat{\pi}^{(0)}}_{\tau}||_{\infty}(\gamma+2)}{\epsilon}\right)+1$
$\displaystyle\leavevmode\hbox to9.93pt{\vbox
to9.93pt{\pgfpicture\makeatletter\hbox{\hskip 4.9644pt\lower-4.9644pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.7644pt}{0.0pt}\pgfsys@curveto{4.7644pt}{2.63133pt}{2.63133pt}{4.7644pt}{0.0pt}{4.7644pt}\pgfsys@curveto{-2.63133pt}{4.7644pt}{-4.7644pt}{2.63133pt}{-4.7644pt}{0.0pt}\pgfsys@curveto{-4.7644pt}{-2.63133pt}{-2.63133pt}{-4.7644pt}{0.0pt}{-4.7644pt}\pgfsys@curveto{2.63133pt}{-4.7644pt}{4.7644pt}{-2.63133pt}{4.7644pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\leavevmode\hbox
to10.67pt{\vbox to10.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.33574pt\lower-5.33574pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.13574pt}{0.0pt}\pgfsys@curveto{5.13574pt}{2.83643pt}{2.83643pt}{5.13574pt}{0.0pt}{5.13574pt}\pgfsys@curveto{-2.83643pt}{5.13574pt}{-5.13574pt}{2.83643pt}{-5.13574pt}{0.0pt}\pgfsys@curveto{-5.13574pt}{-2.83643pt}{-2.83643pt}{-5.13574pt}{0.0pt}{-5.13574pt}\pgfsys@curveto{2.83643pt}{-5.13574pt}{5.13574pt}{-2.83643pt}{5.13574pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.77779pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{b}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle:\delta_{\eta^{*}}\leq\frac{\epsilon(1-\gamma)^{2}}{2(\gamma+2)}$

When $\eta^{*}=(1-\gamma)/\tau$, the iteration complexity is now proportional
to the effective horizon $1/(1-\gamma)$ modulo some log factor, and iteration
complexity and $\delta_{\text{max}}$ is now independent of the choice of the
regularization parameter $\tau$

######  Lemma 3 (Sample complexity to guarantee the optimal threshold
$4\epsilon$ of 2 ).

The authors of the paper [39] showed that for any policy $\pi$,
$||\widetilde{Q}_{\tau}^{\widehat{\pi}^{(\Delta_{\pi})}}-\widehat{Q}_{\tau}^{\widehat{\pi}^{(\Delta_{\pi})}}||_{\infty}\leq\delta$
holds with high probability with model-based policy evaluation, as long as the
number of samples per state-action pairs exceeds the order of
$1/((1-\gamma)^{3}\delta^{2})$ up to some logarithmic factor.

Then, set $\delta_{\text{max}}$ as RHS of the equation (D.36), then if we have
the number of samples per state-action pairs at least the order of

$\frac{1}{(1-\gamma)^{3}\delta^{2}_{\text{max}}}$

up to some logarithmic factor, then the $\delta\leq\delta_{\text{max}}$ holds
with high probability, and we can guarantee the optimal threshold $4\epsilon$
with high probability if all corresponding conditions, equation (D.37),
(D.38), (D.39), holds.

###### Proof of Theorem 2.

1\. ProST-T $\iota^{K}_{H}$ :

The empirical estimated model prediction error
$\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$ is represented as follows
(Definition (C.3)).

$\displaystyle-\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})=$
$\displaystyle-R^{(k+1)}(s^{k+1}_{h},a^{k+1}_{h})-\gamma(P^{(k+1)}\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1})(s^{k+1}_{h},a^{k+1}_{h})+\widehat{Q}^{\widehat{\pi}^{k+1},k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$
(D.40) $\displaystyle=$
$\displaystyle-R^{(k+1)}(s^{k+1}_{h},a^{k+1}_{h})-\gamma(P^{(k+1)}\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1})(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle+\widehat{R}^{(k+1)}(s^{k+1}_{h},a^{k+1}_{h})+\gamma(\widehat{P}^{(k+1)}\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1})(s^{k+1}_{h},a^{k+1}_{h})$
(D.41) $\displaystyle=$
$\displaystyle\left(\widehat{R}^{(k+1)}-R^{(k+1)}\right)(s^{k+1}_{h},a^{k+1}_{h})+\gamma\left(\left(\widehat{P}^{(k+1)}-P^{(k+1)}\right)\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}\right)(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle\leq$
$\displaystyle\bar{\Delta}^{Bonus,r}_{k,h}+\gamma\left|\left|\left(\widehat{P}^{(k+1)}-P^{(k+1)}\right)(\cdot~{}|~{}s^{k+1}_{h},a^{k+1}_{h})\right|\right|_{1}\left|\left|\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}(\cdot)\right|\right|_{\infty}$
$\displaystyle\leq$
$\displaystyle\bar{\Delta}^{Bonus,r}_{k,h}+\gamma\bar{\Delta}^{p}_{k,h}\frac{\gamma^{H-h}\hat{r}_{\text{max}}}{1-\gamma}$
(D.42) $\displaystyle\leq$
$\displaystyle\bar{\Delta}^{r}_{k,h}+2\Gamma^{k}_{w}(s^{k+1}_{h},a^{k+1}_{h})+\gamma\bar{\Delta}^{p}_{k,h}\frac{\gamma^{H-h}\hat{r}_{\text{max}}}{1-\gamma}$
(D.43)

The equation (D.41) holds due to the future bellman equation (C.1), the
equation (D.42) holds since
$\left|\left|\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}(\cdot)\right|\right|_{\infty}\leq\sum_{h^{\prime}=h+1}^{H}\gamma^{h^{\prime}-(h+1)}\hat{r}_{\text{max}}\leq\gamma^{H-h}\hat{r}_{\text{max}}/(1-\gamma)$,
and the equation (D.43) holds since
$\Delta^{Bonus,1}_{r,k}(s,a)\leq\left|\left(R^{(k+1)}-\widetilde{R}^{(k+1)}\right)(s,a)\right|+|2\Gamma^{k}_{w}(s,a)|=\Delta^{1}_{r,k}(s,a)+2\Gamma^{k}_{w}(s,a)$
holds for $(s,a)$. Then the summation of pseudo empirical model prediction
error over all episodes and all steps is bounded as follows,

$\displaystyle-\iota^{K}_{H}=\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}-\gamma^{h}\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})\leq\underbrace{\bar{\Delta}^{r}_{K}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}+\underbrace{\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}2\Gamma^{k}_{w}(s^{k+1}_{h},a^{k+1}_{h})}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}\underbrace{\bar{\Delta}^{p}_{K}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ (D.44)

We use the Lemma 8 to bound the term 1, Lemma 9 and equation (D.13) to bound
the term 2, and Lemma 11(or Lemma 10) to bound the term 3. Then, each terms
can be finally bounded as

1 $\displaystyle\leq wHB_{r}(\Delta_{\pi})+\lambda
r_{\text{max}}\cdot(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$
(D.45) 2 $\displaystyle\leq
2\beta(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$
(D.46) 3
$\displaystyle\leq\left(|\mathcal{S}|\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\lambda\right)(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}+wHB_{p}(\Delta_{\pi})$
(D.47)

where equation (D.47) holds with probability $1-\delta$, $\delta\in(0,1)$.Now,
combine (D.45), (D.46), (D.47) yields the following results.

$\displaystyle-\iota^{K}_{H}=$
$\displaystyle-\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle\leq$
$\displaystyle\underbrace{\bar{\Delta}^{r}_{K}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}+\underbrace{\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}2\Gamma^{k}_{w}(s^{k+1}_{h},a^{k+1}_{h})}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}\underbrace{\bar{\Delta}^{p}_{K}}_{\leavevmode\hbox
to7.49pt{\vbox to7.49pt{\pgfpicture\makeatletter\hbox{\hskip
3.74467pt\lower-3.74467pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.54468pt}{0.0pt}\pgfsys@curveto{3.54468pt}{1.95769pt}{1.95769pt}{3.54468pt}{0.0pt}{3.54468pt}\pgfsys@curveto{-1.95769pt}{3.54468pt}{-3.54468pt}{1.95769pt}{-3.54468pt}{0.0pt}\pgfsys@curveto{-3.54468pt}{-1.95769pt}{-1.95769pt}{-3.54468pt}{0.0pt}{-3.54468pt}\pgfsys@curveto{1.95769pt}{-3.54468pt}{3.54468pt}{-1.95769pt}{3.54468pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$ $\displaystyle\leq$
$\displaystyle wHB_{r}(\Delta_{\pi})+\lambda
r_{\text{max}}\cdot(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}+2\beta(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$
$\displaystyle+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}\left(\left(|\mathcal{S}|\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\lambda\right)(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}+wHB_{p}(\Delta_{\pi})\right)$
$\displaystyle\leq$ $\displaystyle
wH\left(B_{r}(\Delta_{\pi})+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}B_{p}(\Delta_{\pi})\right)$
$\displaystyle+(K-1)\sqrt{H}\left(\lambda
r_{\text{max}}+2\beta+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}\left(|\mathcal{S}|\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\lambda\right)\right)\sqrt{\frac{1}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$
(D.48)

2\. ProST-T $\bar{\iota}^{K}_{\infty}$ :

Recall that
$\bar{\iota}^{K}_{\infty}=\sum_{k=1}^{K-1}\bar{\iota}^{k+1}_{\infty}$. For
same $\delta$ that we used in the previous proof of [1.ProST-T
$\iota^{K}_{H}$] (see equation (D.48)), $\bar{\iota}^{k}_{\infty}$ can be
bounded as follows with probability $1-\delta$.

$\displaystyle\bar{\iota}^{k+1}_{\infty}$ $\displaystyle=R^{(k+1)}+\gamma
P^{(k+1)}\widehat{V}^{\bigast,k+1}_{\infty}-\widehat{Q}^{\bigast,k+1}_{\infty}$
$\displaystyle=R^{(k+1)}+\gamma
P^{(k+1)}\widehat{V}^{\bigast,k+1}_{\infty}-\left(\widehat{R}^{(k+1)}+\gamma\widehat{P}^{(k+1)}\widehat{V}^{\bigast,k+1}_{\infty}\right)$
(D.49) $\displaystyle=R^{(k+1)}+\gamma
P^{(k+1)}\widehat{V}^{\bigast,k+1}_{\infty}-\left(\widetilde{R}^{(k+1)}+2\Gamma^{k}_{w}(s,a)+\gamma\widehat{P}^{(k+1)}\widehat{V}^{\bigast,k+1}_{\infty}\right)$
(D.50) $\displaystyle=R^{(k+1)}+\gamma
P^{(k+1)}\widehat{V}^{\bigast,k+1}_{\infty}-\left(\widetilde{R}^{(k+1)}+2\beta(\Lambda^{k}_{w}(s,a))^{1/2}+\gamma\widehat{P}^{(k+1)}\widehat{V}^{\bigast,k+1}_{\infty}\right)$
(D.51)
$\displaystyle=\left(R^{(k+1)}-\widetilde{R}^{(k+1)}\right)-\beta(\Lambda^{k}_{w}(s,a))^{1/2}+\gamma\left(P^{(k+1)}-\widehat{P}^{(k+1)}\right)\widehat{V}^{\bigast,k+1}_{\infty}-\beta(\Lambda^{k}_{w}(s,a))^{1/2}$
(D.52)
$\displaystyle\leq|R^{(k+1)}-\widetilde{R}^{(k+1)}|-\beta(\Lambda^{k}_{w}(s,a))^{1/2}+\gamma||P^{(k+1)}-\widehat{P}^{(k+1)}||_{1}||\widehat{V}^{\bigast,k+1}_{\infty}||_{\infty}-\beta(\Lambda^{k}_{w}(s,a))^{1/2}$
$\displaystyle\leq\left(B^{k}_{r,w}(\Delta_{\pi})+\lambda\Lambda^{k}_{w}(s,a)r_{\text{max}}\right)-\beta(\Lambda^{k}_{w}(s,a))^{1/2}$
(D.53)
$\displaystyle+\gamma\cdot\left(B^{k}_{p,w}(\Delta_{\pi})+(\Lambda^{k}_{w}(s,a))^{1/2}\cdot|\mathcal{S}|\cdot\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\lambda\Lambda^{k}_{w}(s,a)\right)\cdot\frac{\hat{r}_{\text{max}}}{1-\gamma}-\beta(\Lambda^{k}_{w}(s,a))^{1/2}$
(D.54)
$\displaystyle\leq\left(B^{k}_{r,w}(\Delta_{\pi})+\lambda(\Lambda^{k}_{w}(s,a))^{1/2}r_{\text{max}}\right)-\beta(\Lambda^{k}_{w}(s,a))^{1/2}$
(D.55)
$\displaystyle+\gamma\cdot\left(B^{k}_{p,w}(\Delta_{\pi})+(\Lambda^{k}_{w}(s,a))^{1/2}\cdot|\mathcal{S}|\cdot\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\lambda(\Lambda^{k}_{w}(s,a))^{1/2}\right)\cdot\frac{\hat{r}_{\text{max}}}{1-\gamma}-\beta(\Lambda^{k}_{w}(s,a))^{1/2}$
(D.56) $\displaystyle\leq B^{k}_{r,w}(\Delta_{\pi})+\gamma
B^{k}_{p,w}(\Delta_{\pi})+\underbrace{\left(\lambda
r_{\text{max}}-\beta+\gamma|\mathcal{S}|\cdot\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\frac{\lambda\hat{r}_{\text{max}}}{1-\gamma}-\beta\right)}_{\leq
0}(\Lambda^{k}_{w}(s,a))^{1/2}$ (D.57) $\displaystyle\leq
B^{k}_{r,w}(\Delta_{\pi})+\gamma B^{k}_{p,w}(\Delta_{\pi})$ (D.58)

The equation (D.49) holds by the future bellman equation (C.9) when
$h=\infty$, the equations (D.50) and (D.51) hold by the definition of
$\widehat{R}^{(k+1)}$, equation (D.13). The equations (D.53), (D.54) hold by
lemma 7, lemma 10, equation (D.8), equation (D.9). The equations (D.55),
(D.56) hold since $0\leq\Lambda^{k}_{w}(s,a)<1$. Now, the equation (D.58)
holds if the under-brace term of equation (D.57) is equal or smaller than
zero. That gives us the additional following condition of $\beta$ to obtain
the final inequality (D.58). Recall that $\hat{r}_{\text{max}}$ is defined as
$\tilde{r}_{\text{max}}+\frac{2\beta}{\sqrt{\lambda}}$ where
$\widetilde{r}_{\text{max}}$ is a constant, but $\hat{r}_{\text{max}}$ is
still function of $\beta,\lambda$ (equation (D.14)).

$\lambda
r_{\text{max}}-\beta+\gamma|\mathcal{S}|\cdot\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\frac{\lambda}{1-\gamma}\cdot\left(\widetilde{r}_{\text{max}}+\frac{2\beta}{\sqrt{\lambda}}\right)-\beta\leq
0$

solving above condition yield the condition of $\beta$ .

$\beta\geq\left(2+\frac{2\sqrt{\lambda}}{1-\gamma}\right)^{-1}\left(\lambda
r_{\text{max}}+\gamma|\mathcal{S}|\cdot\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}\right)$
(D.59)

Since equation (D.58) holds for all $(s,a)$, if $\beta$ satisfies the equation
(D.59), then
$\sum_{k=1}^{K-1}\bar{\iota}^{K}_{\infty}=||\bar{\iota}^{k}_{\infty}||_{\infty}$
is bounded as

$\displaystyle\bar{\iota}^{K}_{\infty}\leq\sum_{k=1}^{K-1}\left(B^{k}_{r,w}(\Delta_{\pi})+\gamma
B^{k}_{p,w}(\Delta_{\pi})\right)\leq w(B_{r}(\Delta_{\pi})+\gamma
B_{p}(\Delta_{\pi}))$

because
$\sum_{k=1}^{K-1}B^{k}_{p,w}(\Delta_{\pi})=\sum_{\mathcal{E}=1}^{\left\lfloor\frac{K-1}{w}\right\rfloor}\sum_{k=(\mathcal{E}-1)w}^{\mathcal{E}w}B^{k}_{p,w}(\Delta_{\pi})=wB_{p}(\Delta_{\pi})$
and same as $B_{r}$

Then, the model prediction errors $-\iota^{K}_{H},\bar{\iota}^{K}_{\infty}$
when utilizing the forecaster $f$ as SW-LSE are

$\displaystyle-\iota^{K}_{H}\leq$ $\displaystyle
wH\left(B_{r}(\Delta_{\pi})+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}B_{p}(\Delta_{\pi})\right)$
$\displaystyle+(K-1)\sqrt{H}\left(\lambda
r_{\text{max}}+2\beta+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}\left(|\mathcal{S}|\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\lambda\right)\right)\sqrt{\frac{1}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$
$\displaystyle\bar{\iota}^{K}_{\infty}\leq$ $\displaystyle
w(B_{r}(\Delta_{\pi})+\gamma B_{p}(\Delta_{\pi}))$

Finally, the upper bound of $\mathfrak{R}_{\mathcal{I}}$ can be bounded as
follows,

$\displaystyle\mathfrak{R}_{\mathcal{I}}$
$\displaystyle=\frac{1}{1-\gamma}\bar{\iota}_{\infty}^{K}-\iota^{K}_{H}+C_{p}\sqrt{K-1}$
$\displaystyle\leq\frac{1}{1-\gamma}\left(w(B_{r}(\Delta_{\pi})+\gamma
B_{p}(\Delta_{\pi}))\right)+wH\left(B_{r}(\Delta_{\pi})+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}B_{p}(\Delta_{\pi})\right)$
$\displaystyle+(K-1)\sqrt{H}\left(\lambda
r_{\text{max}}+2\beta+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}\left(|\mathcal{S}|\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\lambda\right)\right)\sqrt{\frac{1}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$
$\displaystyle+C_{p}\sqrt{K-1}$
$\displaystyle\leq\left(\left(\frac{1}{1-\gamma}+H\right)B_{r}(\Delta_{\pi})+\frac{(1+H\hat{r}_{\text{max}})\gamma}{1-\gamma}B_{p}(\Delta_{\pi})\right)w$
$\displaystyle+(K-1)\sqrt{H}\left(\lambda
r_{\text{max}}+2\beta+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}\left(|\mathcal{S}|\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\lambda\right)\right)\sqrt{\frac{1}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$
$\displaystyle+C_{p}\sqrt{K-1}$

Now, we let the $B(\Delta_{\pi})$ as the conic combination of
$B_{r}(\Delta_{\pi}),B_{p}(\Delta_{\pi})$ as follows.

$\displaystyle B(\Delta_{\pi})$
$\displaystyle=\left(\frac{1}{1-\gamma}+H\right)B_{r}(\Delta_{\pi})+\frac{(1+H\hat{r}_{\text{max}})\gamma}{1-\gamma}B_{p}(\Delta_{\pi})$
$\displaystyle=\left(\frac{1}{1-\gamma}+H\right)\Delta_{\pi}^{\alpha_{r}}B_{r}(1)+\frac{(1+H\hat{r}_{\text{max}})\gamma}{1-\gamma}\Delta_{\pi}^{\alpha_{p}}B_{p}(1)$
$\displaystyle=C_{B_{r}}\Delta_{\pi}^{\alpha_{r}}+C_{B_{p}}\Delta_{\pi}^{\alpha_{p}}$

where we denote
$C_{B_{r}}=\left(\frac{1}{1-\gamma}+H\right)B_{r}(1),~{}C_{B_{p}}=\frac{(1+H\hat{r}_{\text{max}})\gamma}{1-\gamma}B_{p}(1)$
where those are constants related with total variation budget with reward and
transition probability, respectively.

Recall the definition of $B_{r}(\Delta_{\pi}),B_{p}(\Delta_{\pi})$ and
$B_{r}(\Delta_{\pi})=\Delta_{\pi}^{\alpha_{r}}B_{r}(1),B_{p}(\Delta_{\pi})=\Delta_{\pi}^{\alpha_{p}}B_{p}(1)$
holds. We denote $B_{p}(1),B_{r}(1)$ as time-elapsing variation budget for one
policy iteration. We also let the constant $C_{k}$ to be defined as follows.

$\displaystyle C_{k}$ $\displaystyle=(K-1)\sqrt{H}\left(\lambda
r_{\text{max}}+2\beta+\frac{\gamma\hat{r}_{\text{max}}}{1-\gamma}\left(|\mathcal{S}|\sqrt{\frac{H^{2}}{2}\log{\left(\frac{H}{\delta\lambda}\right)}}+\lambda\right)\right)$

Then, the upper bound of $\mathfrak{R}_{\mathcal{I}}$ is represented as
follows.

$\displaystyle\mathfrak{R}_{\mathcal{I}}\leq
B(\Delta_{\pi})w+C_{k}\sqrt{\frac{1}{w}\log{\left(\frac{\lambda+wH}{\lambda}\right)}}+C_{p}\sqrt{K-1}$

∎

###### Proof of Proposition 2.

Now, let’s set the sliding window length $w$ which is adaptive to
$\Delta_{\pi}$ as follows.

$\displaystyle\widetilde{w}(\Delta_{\pi})=\left(\frac{C_{k}}{B(\Delta_{\pi})}\right)^{2/3}$

Then, we have

$\displaystyle
B(\Delta_{\pi})\widetilde{w}(\Delta_{\pi})+C_{k}\sqrt{\frac{1}{\widetilde{w}(\Delta_{\pi})}}\sqrt{\log{\left(\frac{\lambda+\widetilde{w}(\Delta_{\pi})H}{\lambda}\right)}}$
$\displaystyle=$ $\displaystyle
C_{k}^{2/3}B(\Delta_{\pi})^{1/3}+C_{k}^{2/3}B(\Delta_{\pi})^{1/3}\sqrt{\log{\left(1+\frac{H}{\lambda}\left(\frac{C_{k}}{B(\Delta_{\pi})}\right)^{2/3}\right)}}$

Since $C_{k}$ is linear to $K-1$, the function $\mathfrak{R}_{\mathcal{I}}$
satisfies the following

$\mathfrak{R}_{\mathcal{I}}=\mathcal{O}\left(B(\Delta_{\pi})^{1/3}\left(K-1\right)^{2/3}\cdot\sqrt{\log{\left(\frac{K-1}{B(\Delta_{\pi})}\right)}}\right)$
(D.60)

Now, if $B(\Delta_{\pi})=o(K)$, then $\mathfrak{R}_{\mathcal{I}}$ is sublinear
to $K$. The corresponding condition is
$B_{r}(1)+\frac{\hat{r}_{\text{max}}}{1-\gamma}B_{p}(1)=o(K)$ and $G<K$ since

$\displaystyle
C_{B_{r}}\Delta_{\pi}^{\alpha_{r}}+C_{B_{p}}\Delta_{\pi}^{\alpha_{p}}=o(K)$
$\displaystyle\left(C_{B_{r}}+C_{B_{p}}\right)\cdot\Delta_{\pi}^{\max\left(\alpha_{r},\alpha_{p}\right)}=o(K)$
$\displaystyle\left(\left(\frac{1}{1-\gamma}+H\right)B_{r}(1)+\left(\frac{1+H\hat{r}_{\text{max}}}{1-\gamma}+\right)B_{p}(1)\right)\cdot\Delta_{\pi}^{\max\left(\alpha_{r},\alpha_{p}\right)}=o(K)$
$\displaystyle\left(\frac{1}{1-\gamma}\left(B_{r}(1)+B_{p}(1)\right)+H\left(B_{r}(1)+\frac{\hat{r}_{\text{max}}}{1-\gamma}B_{p}(1)\right)\right)\cdot\Delta_{\pi}^{\max\left(\alpha_{r},\alpha_{p}\right)}=o(K)$

holds. ∎

###### Proof of Theorem 3.

We prove the followings,

1\. $\mathfrak{R}_{\texttt{Alg}_{\tau}}(\Delta_{\pi})$ is a non-increasing
function, $\mathfrak{R}_{\mathcal{I}}(\Delta_{\pi})$ is an non-decreasing
function , and both are convex function in a region
$\mathcal{G}_{\texttt{Alg}_{\tau}}\cap\mathcal{G}_{\mathcal{I}}$

$\displaystyle\frac{\partial\mathfrak{R}_{A_{\tau}}(\Delta_{\pi})}{\partial\Delta_{\pi}}$
$\displaystyle=\frac{\partial}{\partial\Delta_{\pi}}\left(C_{1}(K-1)(\gamma+2)\left[(1-\eta\tau)^{\Delta_{\pi}-1}\right]\right)$
$\displaystyle=\log{\left(1-\eta\tau\right)}C_{1}(K-1)(\gamma+2)\left[(1-\eta\tau)^{\Delta_{\pi}-1}\right]\leq
0$
$\displaystyle\frac{\partial^{2}\mathfrak{R}_{A_{\tau}}(\Delta_{\pi})}{\partial^{2}\Delta_{\pi}}$
$\displaystyle=\frac{\partial^{2}}{\partial^{2}\Delta_{\pi}}\left(C_{1}(K-1)(\gamma+2)\left[(1-\eta\tau)^{\Delta_{\pi}-1}\right]\right)$
$\displaystyle=\left(\log{\left(1-\eta\tau\right)}\right)^{2}C_{1}(K-1)(\gamma+2)\left[(1-\eta\tau)^{\Delta_{\pi}-1}\right]\geq
0$

since $G\in\mathcal{G}_{\texttt{Alg}_{\tau}}\cap\mathcal{G}_{\mathcal{I}}$
satisfies $G>1$ and $\log(1-\eta\tau)\leq 0$ holds from the hyperparameter
assumption $0\leq\eta\leq(1-\gamma)/\tau$ from the Proposition 1.

$\displaystyle\frac{\partial\mathfrak{R}_{\mathcal{I}}(\Delta_{\pi})}{\partial\Delta_{\pi}}$
$\displaystyle=\frac{\partial}{\partial\Delta_{\pi}}\left(C_{B_{r}}\Delta_{\pi}^{\alpha_{r}}+C_{B_{p}}\Delta_{\pi}^{\alpha_{p}}\right)$
$\displaystyle=\alpha_{r}C_{B_{r}}\Delta_{\pi}^{\alpha_{r}-1}+\alpha_{p}C_{B_{p}}\Delta_{\pi}^{\alpha_{p}-1}\geq
0$
$\displaystyle\frac{\partial^{2}\mathfrak{R}_{\mathcal{I}}(\Delta_{\pi})}{\partial^{2}\Delta_{\pi}}$
$\displaystyle=\frac{\partial^{2}}{\partial^{2}\Delta_{\pi}}\left(C_{B_{r}}\Delta_{\pi}^{\alpha_{r}}+C_{B_{p}}\Delta_{\pi}^{\alpha_{p}}\right)$
$\displaystyle=\alpha_{r}(\alpha_{r}-1)C_{B_{r}}\Delta_{\pi}^{\alpha_{r}-2}+\alpha_{p}(\alpha_{p}-1)C_{B_{p}}\Delta_{\pi}^{\alpha_{p}-2}\geq
0$

holds only $\alpha_{r},\alpha_{p}\geq 1$.

2\. Optimal $G_{\texttt{Alg}}^{*},G_{\texttt{Alg}_{\tau}}^{*}$ for
$\texttt{Alg},\texttt{Alg}_{\tau}$

For the optimal $G$, we slightly relax
$\mathfrak{R}_{\mathcal{I}}(\Delta_{\pi})=C_{B_{r}}\Delta_{\pi}^{\alpha_{r}}+C_{B_{p}}\Delta_{\pi}^{\alpha_{p}}$
to
$\mathfrak{R}^{\prime}_{\mathcal{I}}(\Delta_{\pi})=\left(C_{B_{r}}+C_{B_{p}}\right)\Delta_{\pi}^{\max{\left(\alpha_{r},\alpha_{p}\right)}}$
and get the optimal $\Delta_{\pi}^{*}$ of the dynamic regret
$\mathfrak{R}_{\maltese}(\Delta_{\pi})+\mathfrak{R}^{\prime}_{\mathcal{I}}(\Delta_{\pi})$.
We omit the proof of that $\mathfrak{R}^{\prime}_{\mathcal{I}}(\Delta_{\pi})$
is also non-decreasing function (simliar process to 1.).

  1. 1.

$\boldsymbol{\max{(\alpha_{r},\alpha_{p})}}=0$ : this means
$\mathfrak{R}_{\mathcal{I}}(\Delta_{\pi})=C_{B_{r}}+C_{B_{p}}$ that
$\mathfrak{R}_{\mathcal{I}}$ is now independent to $G$. Then, for both
baseline algorithm $\texttt{Alg},\texttt{Alg}_{\tau}$, infinite number of $G$
guarantees small dynamic regret $\mathfrak{R}_{\mathcal{I}}$, that leads to
small $\mathfrak{R}$. We can check $\mathfrak{R}_{\texttt{Alg}}$ decreases in
a $1/G$ scale, and $\mathfrak{R}_{\texttt{Alg}_{\tau}}$ decreases in a
$\exp{(\Delta_{\pi})}$ scale. So using entropy-regularization guarantees
faster convergence.

For the remaining case, let’s first compute the gradient of the term
$\mathfrak{R}_{\texttt{Alg}_{\tau}}(\Delta_{\pi})+\mathfrak{R}^{\prime}_{\mathcal{I}}(\Delta_{\pi})$,

$\displaystyle\frac{\partial\mathfrak{R}_{A_{\tau}}(\Delta_{\pi})+\mathfrak{R}^{\prime}_{\mathcal{I}}(\Delta_{\pi})}{\partial\Delta_{\pi}}$
$\displaystyle=\max{(\alpha_{r},\alpha_{p})}\left(\alpha_{r}C_{B_{r}}+\alpha_{p}C_{B_{p}}\right)\Delta_{\pi}^{\max{(\alpha_{r},\alpha_{p})}-1}-\log{\left(\frac{1}{1-\eta\tau}\right)}C_{1}(K-1)(\gamma+2)\left[(1-\eta\tau)^{\Delta_{\pi}-1}\right]$
$\displaystyle=k_{B}\Delta_{\pi}^{\max{(\alpha_{r},\alpha_{p})}-1}-k_{\texttt{Alg}_{\tau}}\left[(1-\eta\tau)^{\Delta_{\pi}-1}\right]$

and the term
$\mathfrak{R}_{\texttt{Alg}}(\Delta_{\pi})+\mathfrak{R}^{\prime}_{\mathcal{I}}(\Delta_{\pi})$,

$\displaystyle\frac{\partial\mathfrak{R}_{A}(\Delta_{\pi})+\mathfrak{R}^{\prime}_{\mathcal{I}}(\Delta_{\pi})}{\partial\Delta_{\pi}}$
$\displaystyle=\max{(\alpha_{r},\alpha_{p})}\left(\alpha_{r}C_{B_{r}}+\alpha_{p}C_{B_{p}}\right)\Delta_{\pi}^{\max{(\alpha_{r},\alpha_{p})}-1}-\left(\frac{1}{(1-\gamma)^{2}}+\frac{\log{|\mathcal{A}|}}{\eta}\right)\cdot\frac{1}{\Delta_{\pi}^{2}}$
$\displaystyle=k_{B}\Delta_{\pi}^{\max{(\alpha_{r},\alpha_{p})}-1}-k_{\texttt{Alg}}\frac{1}{\Delta_{\pi}^{2}}$

  1. 2.

$\boldsymbol{\max{(\alpha_{r},\alpha_{p})}=1}$ : Then
$(1-\eta\tau)^{\Delta_{\pi}-1}=k_{B}/k_{\texttt{Alg}_{\tau}}$ and
$\Delta_{\pi}^{-2}=k_{B}/k_{\texttt{Alg}}$ should be satisfied, respectively.
Then, the optimal
$G_{\texttt{Alg}_{\tau}}^{*}=\log_{1-\eta\tau}(k_{B}/k_{\texttt{Alg}_{\tau}})+1$
and the optimal $G_{\texttt{Alg}}^{*}=\sqrt{k_{\texttt{Alg}}/k_{B}}$

Now, for the case of $A_{\tau}$, if
$k_{\texttt{Alg}_{\tau}}=(1-\eta\tau)k_{B}$ is satisfied,
$\frac{\partial\mathfrak{R}_{\texttt{Alg}_{\tau}}(\Delta_{\pi})+\mathfrak{R}^{\prime}_{\mathcal{I}}(\Delta_{\pi})}{\partial\Delta_{\pi}}=0$
is equals to solving
$\Delta_{\pi}^{\max{(\alpha_{r},\alpha_{p})}-1}=(1-\eta\tau)^{G}$. Now, using
the lambert W function to get $G$ as follows.

$\displaystyle\Delta_{\pi}^{\max{(\alpha_{r},\alpha_{p})}-1}=(1-\eta\tau)^{G}$
$\displaystyle\left(\max{(\alpha_{r},\alpha_{p})}-1\right)\log{G}=G\log{(1-\eta\tau)}$
$\displaystyle\Delta_{\pi}^{-1}\cdot\log{G}=\frac{\log{(1-\eta\tau)}}{\max{(\alpha_{r},\alpha_{p})}-1}$
$\displaystyle-\log{G}\cdot
e^{-\log{G}}=-\frac{\log{(1-\eta\tau)}}{\max{(\alpha_{r},\alpha_{p})}-1}$
$\displaystyle W\left[-\log{G}\cdot
e^{-\log{G}}\right]=W\left[-\frac{\log{(1-\eta\tau)}}{\max{(\alpha_{r},\alpha_{p})}-1}\right]$
$\displaystyle W\left[-\log{G}\cdot
e^{-\log{G}}\right]=W\left[-\frac{\log{(1-\eta\tau)}}{\max{(\alpha_{r},\alpha_{p})}-1}\right]$
$\displaystyle-\log{G}=W\left[-\frac{\log{(1-\eta\tau)}}{\max{(\alpha_{r},\alpha_{p})}-1}\right]$
$\displaystyle\Delta_{\pi}^{*}=\exp{\left(-W\left[-\frac{\log{(1-\eta\tau)}}{\max{(\alpha_{r},\alpha_{p})}-1}\right]\right)}=\exp{\left(-W\left[x\right]\right)}$

  1. 3.

$\boldsymbol{0<\max{(\alpha_{r},\alpha_{p})}<1}$ :

     * •

Alg:
$\Delta_{\pi}^{*}=(k_{B}/k_{\texttt{Alg}})^{1/(\max{(\alpha_{r},\alpha_{p})}+1)}$

     * •

$\texttt{Alg}_{\tau}$ : Then
$x=-\frac{\log{(1-\eta\tau)}}{\max{(\alpha_{r},\alpha_{p})}-1}<0$, then small
$|x|$ have large $-W(x)>0$ value, which leads to large
$G_{\texttt{Alg}_{\tau}}^{*}$.

  2. 4.

$\boldsymbol{\max{(\alpha_{r},\alpha_{p})}>1}$ :

     * •

Alg:
$\Delta_{\pi}^{*}=(k_{B}/k_{\texttt{Alg}})^{1/(\max{(\alpha_{r},\alpha_{p})}+1)}$

     * •

$\texttt{Alg}_{\tau}$: Then $x>0$ satisfies and $-W(x)<0$ satisfied. Then
$\Delta_{\pi}^{*}<1$ which means 1 iteration is enough.

∎

From the proof of theorem 2, we can come up with Lemma 4, Lemma 5, Lemma 6
that upperbound two model prediction errors $-\iota^{k}_{h}$,
$\bar{\iota}_{\infty}^{k}$

######  Lemma 4 (Upper bound of $-\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})$ by
$\bar{\Delta}^{1}_{r,k,h},~{}\bar{\Delta}^{1}_{p,k,h}$).

$-\iota^{k+1}_{h}(s^{k+1}_{h},a^{k+1}_{h})\leq\bar{\Delta}^{r}_{k,h}+2\Gamma^{k}_{w}(s,a)+\gamma\bar{\Delta}^{p}_{k,h}\frac{\gamma^{H-h}\hat{r}_{\text{max}}}{1-\gamma}$

###### Proof of Lemma 4.

The equations (D.40)$\sim$(D.43) in the theorem 2 replace the proof. ∎

######  Lemma 5 (Upper bound of $-\iota^{k+1}_{h}(s,a)$ by
$\Delta^{1}_{r,k},~{}\Delta^{1}_{p,k}$).

For any $(s,a)\in\mathcal{S}\times\mathcal{A}$, the following holds.

$-\iota^{k+1}_{h}(s,a)\leq\Delta^{1}_{r,k}(s,a)+\gamma\Delta^{p}_{k}(s,a)\frac{\gamma^{H-h}\hat{r}_{\text{max}}}{1-\gamma}+2\Gamma^{k}_{w}(s,a)$

###### Proof of Lemma 5.

$\displaystyle-\iota^{k+1}_{h}(s,a)=$
$\displaystyle-R^{(k+1)}(s,a)-\gamma(P^{(k+1)}\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1})(s,a)+\widehat{Q}^{\widehat{\pi}^{k+1},k+1}_{h}(s,a)$
$\displaystyle=$
$\displaystyle-R^{(k+1)}(s,a)-\gamma(P^{(k+1)}\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1})(s,a)$
$\displaystyle+\widehat{R}^{(k+1)}(s,a)+\gamma(\widehat{P}^{(k+1)}\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1})(s,a)$
$\displaystyle=$
$\displaystyle\left(\widehat{R}^{(k+1)}-R^{(k+1)}\right)(s,a)+\gamma\left(\left(\widehat{P}^{(k+1)}-P^{(k+1)}\right)\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}\right)(s,a)$
$\displaystyle\leq$
$\displaystyle\Delta^{1}_{r,k}(s,a)+2\Gamma^{k}_{w}(s,a)+\gamma\left|\left|\left(\widehat{P}^{(k+1)}-P^{(k+1)}\right)(\cdot~{}|~{}s,a)\right|\right|_{1}\left|\left|\widehat{V}^{\widehat{\pi}^{k+1},k+1}_{h+1}(\cdot)\right|\right|_{\infty}$
$\displaystyle\leq$
$\displaystyle\Delta^{1}_{r,k}(s,a)+2\Gamma^{k}_{w}(s,a)+\gamma\Delta^{p}_{k}(s,a)\frac{\gamma^{H-h}\hat{r}_{\text{max}}}{1-\gamma}$

∎

######  Lemma 6 (Upper bound of $\bar{\iota}^{k}_{\infty}$ by
$\Delta^{1}_{r,k},~{}\Delta^{1}_{p,k}$).

For any $(s,a)\in\mathcal{S}\times\mathcal{A}$, the following holds.

$\bar{\iota}^{k+1}_{\infty}(s,a)\leq\Delta^{1}_{r,k}(s,a)+\Delta^{1}_{p,k}(s,a)\frac{\gamma\hat{r}_{max}}{1-\gamma}-2\Gamma^{k}_{w}(s,a)$

###### Proof of Lemma 6.

Starting from the equation (D.52),

$\displaystyle\bar{\iota}^{k+1}_{\infty}$
$\displaystyle=\left(R^{(k+1)}-\widetilde{R}^{(k+1)}\right)-\beta(\Lambda^{k}_{w}(s,a))^{1/2}+\gamma\left(P^{(k+1)}-\widehat{P}^{(k+1)}\right)\widehat{V}^{\bigast,k+1}_{\infty}-\beta(\Lambda^{k}_{w}(s,a))^{1/2}$
$\displaystyle\leq\left|R^{(k+1)}-\widetilde{R}^{(k+1)}\right|-\beta(\Lambda^{k}_{w}(s,a))^{1/2}+\gamma\left|\left|P^{(k+1)}-\widehat{P}^{(k+1)}\right|\right|_{1}\left|\left|\widehat{V}^{\bigast,k+1}_{\infty}\right|\right|_{\infty}-\beta(\Lambda^{k}_{w}(s,a))^{1/2}$
$\displaystyle\leq\Delta^{1}_{r,k}(s,a)-\beta(\Lambda^{k}_{w}(s,a))^{1/2}+\gamma\Delta^{1}_{p,k}(s,a)\frac{\hat{r}_{max}}{1-\gamma}-\beta(\Lambda^{k}_{w}(s,a))^{1/2}$
$\displaystyle=\Delta^{1}_{r,k}(s,a)+\Delta^{1}_{p,k}(s,a)\frac{\gamma\hat{r}_{max}}{1-\gamma}-2\Gamma^{k}_{w}(s,a)$

∎

######  Lemma 7 (Upper bound of $\Delta^{1}_{r,k}(s,a)$).

For any $(s,a)\in\mathcal{S}\times\mathcal{A}$, $\Delta^{1}_{r,k}(s,a)$ is
bounded as follows.

$\Delta^{1}_{r,k}(s,a)\leq
B^{k}_{r,w}(\Delta_{\pi})+\lambda\Lambda^{k}_{w}(s,a)r_{\text{max}}$

###### Proof of Lemma 7.

We directly utilize the proof of the lemma (35) of the paper [31]. Then, for
any $(s,a)\in\mathcal{S}\times\mathcal{A}$, $\Delta^{1}_{r,k}(s,a)$ can be
represented as follows,

$\displaystyle\Delta^{1}_{r,k}(s,a)$ (D.61)
$\displaystyle=|R^{(k+1)}(s,a)-\widetilde{R}^{(k+1)}(s,a)|$ (D.62)
$\displaystyle=|o^{r}_{(k+1)}(s,a)-\widetilde{o}^{r}_{(k+1)}(s,a)|$ (D.63)
$\displaystyle=\left|\frac{\sum_{t=(1\wedge
k-w+1)}^{k}\sum_{h=0}^{H-1}\mathbbm{1}\left[(s,a)=(s^{t}_{h},a^{t}_{h})\right]\cdot
r^{t}_{h}}{\lambda+\sum_{t=(1\wedge
k-w+1)}^{k}n_{t}(s,a)}-o^{r}_{(k+1)}(s,a)\right|$ (D.64)
$\displaystyle=\Lambda^{k}_{w}(s,a)\left|\sum_{t=(1\wedge
k-w+1)}^{k}\sum_{h=0}^{H-1}\mathbbm{1}\left[(s,a)=(s^{t}_{h},a^{t}_{h})\right]\cdot
r^{t}_{h}-\left(\lambda+\sum_{t=(1\wedge
k-w+1)}^{k}n_{t}(s,a)\right)o^{r}_{(k+1)}(s,a)\right|$ (D.65)
$\displaystyle=\Lambda^{k}_{w}(s,a)\left|\sum_{t=(1\wedge
k-w+1)}^{k}\sum_{h=0}^{H-1}\left(\mathbbm{1}\left[(s,a)=(s^{t}_{h},a^{t}_{h})\right]\left(r^{t}_{h}-o^{r}_{(k+1)}(s,a)\right)\right)-\lambda\cdot
o^{r}_{(k+1)}(s,a)\right|$ (D.66)
$\displaystyle\leq\Lambda^{k}_{w}(s,a)\left(\sum_{t=(1\wedge
k-w+1)}^{k}\sum_{h=0}^{H-1}\mathbbm{1}\left[(s,a)=(s^{t}_{h},a^{t}_{h})\right]\cdot\left|r^{t}_{h}-o^{r}_{(k+1)}(s,a)\right|\right)+\lambda\Lambda^{k}_{w}(s,a)\left|o^{r}_{(k+1)}(s,a)\right|$
(D.67) $\displaystyle\leq\Lambda^{k}_{w}(s,a)\left(\sum_{t=(1\wedge
k-w+1)}^{k}n_{t}(s,a)\left(\left|r^{t}(s,a)-o^{r}_{(k+1)}(s,a)\right|\right)\right)+\lambda\Lambda^{k}_{w}(s,a)r_{\text{max}}$
(D.68) $\displaystyle\leq\max_{(1\wedge k-w+1)\leq t\leq
k}\left(\left|r^{t}(s,a)-o^{r}_{(k+1)}(s,a)\right|\right)\Lambda^{k}_{w}(s,a)\left(\sum_{t=(1\wedge
k-w+1)}^{k}n_{t}(s,a)\right)+\lambda\Lambda^{k}_{w}(s,a)r_{\text{max}}$
$\displaystyle\leq\max_{(1\wedge k-w+1)\leq t\leq
k}\left(\left|r^{t}(s,a)-o^{r}_{(k+1)}(s,a)\right|\right)+\lambda\Lambda^{k}_{w}(s,a)r_{\text{max}}$
$\displaystyle\leq
B^{k}_{r,w}(\Delta_{\pi})+\lambda\Lambda^{k}_{w}(s,a)r_{\text{max}}$ (D.69)

Equations (D.63) and (D.64) hold by the definition of
$o^{r}_{k+1},\widetilde{o}^{r}_{k+1}$ (definition (D.7)), equation (D.65)
holds by the definition (D.12), equation (D.66) holds since
$n_{t}(s,a)\coloneqq\sum_{h=0}^{H-1}\mathbbm{1}\left[(s,a)=(s_{h}^{t},a_{h}^{t})\right]$,
equation (D.69) holds since $\max_{(1\wedge k-w+1)\leq t\leq
k}\left(\left|r^{t}(s,a)-o^{r}_{(k+1)}(s,a)\right|\right)\leq|r^{(1\wedge
k-w+1)}(s,a)-r^{(1\wedge
k-w+1)+1}(s,a)|+...+|R^{(k)}(s,a)-R^{(k+1)}(s,a)|=B^{k}_{r,w}(\Delta_{\pi})$.
∎

######  Lemma 8 (Upper bound of $\bar{\Delta}^{1}_{r,K}$).

For any $(s,a)\in\mathcal{S}\times\mathcal{A}$, the following holds,

$\displaystyle\bar{\Delta}^{r}_{K}\leq wHB_{r}(\Delta_{\pi})+\lambda
r_{\text{max}}\cdot(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$

###### Proof of Lemma 8.

The total empirical forecasting model error up to $K-1$ is given as

$\displaystyle\bar{\Delta}^{r}_{K}$
$\displaystyle=\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\bar{\Delta}^{r}_{k,h}$
$\displaystyle=\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\bar{\Delta}^{r}_{K}(s^{k+1}_{h},a^{k+1}_{h})$
$\displaystyle\leq\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\left(B^{k}_{r,w}(\Delta_{\pi})+\lambda\Lambda^{k}_{w}(s^{k+1}_{h},a^{k+1}_{h})r_{\text{max}}\right)$
(D.70) $\displaystyle=wHB_{r}(\Delta_{\pi})+\lambda
r_{\text{max}}\cdot\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\left(\Lambda^{k}_{w}(s^{k+1}_{h},a^{k+1}_{h})\right)$
(D.71) $\displaystyle\leq wHB_{r}(\Delta_{\pi})+\lambda
r_{\text{max}}\cdot\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\left(\sqrt{\Lambda^{k}_{w}(s^{k+1}_{h},a^{k+1}_{h})}\right)$
$\displaystyle\leq wHB_{r}(\Delta_{\pi})+\lambda
r_{\text{max}}\cdot(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$
(D.72)

The equation (D.70) holds by lemma 7, the equation (D.71) holds since
$\sum_{k=1}^{K-1}B^{k}_{r,w}(\Delta_{\pi})=\sum_{\mathcal{E}=1}^{{\left\lfloor\frac{K-1}{w}\right\rfloor}}\sum_{k=(\mathcal{E}-1)w}^{\mathcal{E}w}B^{k}_{r,w}(\Delta_{\pi})=wB_{r}(\Delta_{\pi})$,
the equation (D.72) holds by lemma 9. ∎

######  Lemma 9 (Upper bound of the term
$\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\sqrt{\Lambda^{k}_{w}(s^{k+1}_{h},a^{k+1}_{h})}$).

$\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\left(\sqrt{\Lambda^{k}_{w}(s^{k+1}_{h},a^{k+1}_{h})}\right)\leq(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$

###### Proof of lemma 9.

We denote $\bar{\Lambda}_{w}^{k}=\lambda\mathbb{I}+\sum_{t=(1\wedge
k-w+1)}^{k}\sum_{h=0}^{H-1}\varphi(s_{h}^{t},a_{h}^{t})\varphi(s_{h}^{t},a_{h}^{t})^{\top}$.
Also, we denote
$(\bar{\Lambda}_{w}^{k})^{(1)}=\lambda\mathbb{I}+\varphi(s_{h}^{(1\wedge
k-w+1)},a_{h}^{(1\wedge k-w+1)})\varphi(s_{h}^{(1\wedge
k-w+1)},a_{h}^{(1\wedge k-w+1)})^{\top}$ Then, for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$,
$\Lambda^{k}_{w}(s,a)=\varphi(s,a)(\bar{\Lambda}^{k}_{w})^{-1}\varphi(s,a)^{\top}$
holds.

Now, the following term can be bounded as follows.

$\displaystyle\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\sqrt{\Lambda^{k}_{w}(s^{k+1}_{h},a^{k+1}_{h})}$
$\displaystyle=\sum_{k=1}^{K-1}\sum_{h=0}^{H-1}\sqrt{\varphi(s^{k+1}_{h},a^{k+1}_{h})(\bar{\Lambda}^{k}_{w})^{-1}\varphi(s^{k+1}_{h},a^{k+1}_{h})^{\top}}$
$\displaystyle=\sum_{\mathcal{E}=1}^{\left\lfloor\frac{K-1}{w}\right\rfloor}\sum_{k=(\mathcal{E}-1)w+1}^{\mathcal{E}w}\sum_{h=0}^{H-1}\sqrt{\varphi(s^{k+1}_{h},a^{k+1}_{h})(\bar{\Lambda}^{k}_{w})^{-1}\varphi(s^{k+1}_{h},a^{k+1}_{h})^{\top}}$
$\displaystyle\leq\sum_{\mathcal{E}=1}^{\left\lfloor\frac{K-1}{w}\right\rfloor}\sqrt{Hw}\sqrt{\sum_{k=(\mathcal{E}-1)w+1}^{\mathcal{E}w}\sum_{h=0}^{H-1}\varphi(s^{k+1}_{h},a^{k+1}_{h})(\bar{\Lambda}^{k}_{w})^{-1}\varphi(s^{k+1}_{h},a^{k+1}_{h})^{\top}}$
(D.73)
$\displaystyle\leq\sum_{\mathcal{E}=1}^{\left\lfloor\frac{K-1}{w}\right\rfloor}\sqrt{Hw}\sqrt{\log{\left(\frac{\text{det}\left(\Lambda^{\mathcal{E}w+1}_{w}\right)}{\text{det}\left((\Lambda^{(\mathcal{E}-1)w+2}_{w})^{(1)}\right)}\right)}}$
(D.74)
$\displaystyle\leq\left\lfloor\frac{K-1}{w}\right\rfloor\sqrt{Hw}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$
(D.75)
$\displaystyle\leq(K-1)\sqrt{\frac{H}{w}}\sqrt{\log{\left(\frac{\lambda+wH}{\lambda}\right)}}$

Equation (D.73) holds by Cauchy–Schwarz inequality, equation (D.74) holds by
the lemma (D.1) and (D.2) of the paper [40], the equation (D.75) holds since