Rewriting the Remaining Proof (Part 1)
Since some equations were not successfully rendered, we now rewrite the proof of this part.
**Proof of the Regret Lower Bound (Cont.)**
and by $\mathbb{E}\_{\left(i^*, a^*\right)} \triangleq \mathbb{E}\_{\operatorname{Alg}, \mathcal{M}\_{\left(i^*, a^*\right)}}$ the expectation with respect to $\mathbb{P}\_{\left(i^*, a^*\right)}$.
**Step 1: Regret of $\operatorname{Alg}$ in $\mathcal{M}\_{(i^\ast,a^\ast)}$**
For some $\mathcal{M}\_{(i^\ast,a^\ast)}$, its optimal policy $\pi^\ast_{(i^\ast,a^\ast)}:\mathcal{S}\to\mathcal{A}$ satisfies that $\pi^\ast\_{(i^\ast,a^\ast)}(s_{1,1})=a\_{i^\ast}$ and $\pi^\ast\_{(i^\ast,a^\ast)}(s\_{2,i^\ast})=a^\ast$, with the optimal value function
$$
\begin{align}
V\_{0}^*(s\_{1,1}) & =\mathbb{E}\left[\sum_{\tau=0}^{+\infty} \gamma^\tau r(s\_{\tau}, a\_\tau) \mid \pi^\ast\_{(i^\ast,a^\ast)},P^\star\_{(i^\ast,a^\ast)}, s\_0=s\_{1,1}\right]=\sum\_{\tau=2}^{+\infty} \gamma^\tau \left(\frac{1}{2}+\varepsilon\right)=\frac{\gamma^2}{1-\gamma}\left(\frac{1}{2}+\varepsilon\right).\tag{1}
\end{align}
$$
For some policy $\pi$, it is also clear that its value function satisfies
$$
\begin{align}
V_{0}^\pi(s\_{1,1}) &=\frac{\gamma^2}{1-\gamma}\left(\frac{1}{2}+\varepsilon\mathbb{P}\_{\left(i^*, a^*\right)}\left((s\_2,a\_2)=(s\_{2,i^\ast},a^\ast)\right)\right).\tag{2}
\end{align}
$$
Combining Eq. $(1)$ and Eq. $(2)$ shows that the regret of $\operatorname{Alg}$ in $\mathcal{M}\_{(i^\ast,a^\ast)}$ satisfies
$$
\begin{align*}
R\_K(\operatorname{Alg}, \mathcal{M}\_{(i^\ast,a^\ast}))&=\frac{\gamma^2\varepsilon}{1-\gamma}K\left(1-\frac{1}{K}\mathbb{E}\_{(i^\ast,a^\ast)}\left[\sum_{k=1}^K\mathbb{I}\{(s^k\_2,a^k\_2)=(s\_{2,i^\ast},a^\ast)\} \right]\right)\\
&=\frac{\gamma^2\varepsilon}{1-\gamma}K\left(1-\frac{1}{K}\mathbb{E}\_{(i^\ast,a^\ast)}\left[N^K\_{(i^\ast,a^\ast)} \right]\right)\notag,
\end{align*}
$$
where we define $N^K\_{(i^\ast,a^\ast)}= \sum\_{k=1}^K\mathbb{I}\\{(s^k\_2,a^k\_2)=(s\_{2,i^\ast},a^\ast)\\}$.
**Step 2: Maximum regret of $\operatorname{Alg}$ over all possible $\mathcal{M}\_{(i^\ast,a^\ast)}$**
With $R\_K(\operatorname{Alg}, \mathcal{M}\_{(i^\ast,a^\ast}))$ in the above equation, we can deduce that
$$
\begin{align}
\max\_{(i^\ast,a^\ast)}R\_K(\operatorname{Alg},\mathcal{M}\_{(i^\ast,a^\ast)})&\geq \frac{1}{(d-4)A}\sum\_{(i^\ast,a^\ast)}R\_K(\operatorname{Alg},\mathcal{M}\_{(i^\ast,a^\ast}))\notag\\
&\geq \frac{\gamma^2\varepsilon}{1-\gamma}K\left(1-\frac{1}{K(d-4)A}\sum\_{(i^\ast,a^\ast)}\mathbb{E}\_{(i^\ast,a^\ast)}\left[N^K\_{(i^\ast,a^\ast)} \right]\right).\tag{3}
\end{align}
$$
To lower bound the above display, it remains to upper bound $\sum\_{(i^\ast,a^\ast)}\mathbb{E}\_{(i^\ast,a^\ast)}\left[N^K\_{(i^\ast,a^\ast)} \right]$. To this end, by Lemma 1 in the work of [4] together with the fact that $N^K\_{(i^\ast,a^\ast)}/K\in[0,1]$, it holds that
$$
\begin{align*}
\operatorname{KL}\left(\operatorname{Ber}\left(\frac{1}{K}\mathbb{E}\_0\left[N^K\_{(i^\ast,a^\ast)}\right]\right),\operatorname{Ber}\left(\frac{1}{K}\mathbb{E}\_{(i^\ast,a^\ast)}\left[N^K\_{(i^\ast,a^\ast)}\right]\right)\right)\leq \operatorname{KL}\left(\mathbb{P}\_0,\mathbb{P}\_{(i^\ast,a^\ast)}\right).
\end{align*}
$$
This implies that
$$
\begin{align*}
\frac{1}{K}\mathbb{E}\_{(i^\ast,a^\ast)}\left[N^K\_{(i^\ast,a^\ast)}\right]
&\leq \frac{1}{K}\mathbb{E}\_0 \left[N^K\_{(i^\ast,a^\ast)}\right]+\sqrt{\frac{1}{2}\operatorname{KL}\left(\mathbb{P}\_0,\mathbb{P}\_{(i^\ast,a^\ast)}\right)}\\
&=\frac{1}{K}\mathbb{E}_0 \left[N^K\_{(i^\ast,a^\ast)}\right]+\varepsilon\sqrt{2}\sqrt{\mathbb{E}\_0\left[N^K\_{(i^\ast,a^\ast)}\right]},
\end{align*}
$$
where the inequality is due to Pinsker’s inequality that $(p-q)^2 \leq \frac{1}{2} \operatorname{KL}(\operatorname{Ber}(p), \operatorname{Ber}(q))$, for $p,q\in[0,1]$, and the equality comes from Lemma 15.1 of [1] and Lemma 14 of [2] as well as assuming $0\leq\varepsilon\leq\frac{1}{4}$.
Based on this, one can see that
$$
\begin{align}
\frac{1}{K}\sum\_{(i^\ast,a^\ast)}\mathbb{E}\_{(i^\ast,a^\ast)}\left[N^K\_{(i^\ast,a^\ast)}\right]
&\leq \frac{1}{K}\sum\_{(i^\ast,a^\ast)}\mathbb{E}\_0 \left[N^K\_{(i^\ast,a^\ast)}\right]+\varepsilon\sqrt{2}\sum\_{(i^\ast,a^\ast)}\sqrt{\mathbb{E}\_0\left[N^K\_{(i^\ast,a^\ast)}\right]}\notag\\
&\leq 1+\varepsilon\sqrt{2}\sqrt{(d-4)AK},\tag{4}
\end{align}
$$
where the second inequality follows from using the Cauchy-Schwartz inequality together with the fact that $N^K\_{(i^\ast,a^\ast)}\leq K$.