$a \in \mathcal{A}(s)$ such that $(s, a) \in \mathcal{Z}^*(M)$) under reward function $f$ and kernel $p(M)$. Remark that $g^f(s) = 1$ for all $s \in \mathcal{S}$ and that, by construction of $\pi^*$, $\Delta^f(z) = 0$ for all $z \in \mathcal{Z}^*(M)$. Denote $H^f := \text{sp}(h^f) \lor \max_z |\Delta^f(z)|$. We have:

$$
\begin{align*}
& \sum_{z \in \mathcal{Z}^{**}(M)} N_z(T) \\
&= \sum_{t=1}^{T} f(Z_t) \\
&\stackrel{(\dagger)}{=} \sum_{t=1}^{T} (1 + (e_{S_t} - p(Z_t))h^f - \Delta^f(Z_t)) \\
&\geq T - H^f - \sum_{t=1}^{T} \Delta^f(Z_t) + \sum_{t=1}^{T} (e_{S_{t+1}} - p(Z_t))h^f \\
&\stackrel{(\ddagger)}{\geq} T - H^f - H^f \sum_{t=1}^{T} \mathbf{1}(Z_t \notin \mathcal{Z}^*(M)) + \sum_{t=1}^{T} \mathbf{1}(Z_t \notin \mathcal{Z}^{**}(M)) (e_{S_{t+1}} - p(Z_t))h^f
\end{align*}
$$

where $(\dagger)$ uses the Bellman equation $1 + h^f(s) = f(s, a) + p^f(s, a)h^f + \Delta^f(s, a)$, and $(\ddagger)$ that $h^f(s) = 0$ for all $(s, \pi^*(s)) \in \mathcal{Z}^{**}(M)$. For $\mathcal{Z}' \subseteq \mathcal{Z}$, denote $N_T(\mathcal{Z}') := \sum_{z \in \mathcal{Z}'} N_T(z)$. The first sum is equal to $\sum_{t=1}^T \mathbf{1}(Z_t \notin \mathcal{Z}^*(M)) = N_T(\mathcal{Z}^-(M))$. The RHS of the above equation is bounded using a time-uniform Azuma-Hoeffding inequality (see (Bourel et al., 2020, Lemma 5)), showing that:

$$
\mathbf{P} \left( \exists T \ge 1 : \begin{array}{l} \sum_{t=1}^{T} \mathbf{1}(Z_t \notin \mathcal{Z}^{**}(M)) (e_{S_{t+1}} - p(Z_t)) h^f \\ < -H^f \sqrt{N_T(\mathcal{Z}^{**}(M)^c) \log\left(\frac{4N_T(\mathcal{Z}^{**}(M)^c)^T}{\delta}\right)} \end{array} \right) \le \frac{1}{4}\delta
$$

Using that $N_T(\mathcal{Z}^{**}(M)^c) = T - N_T(\mathcal{Z}^{**}(M))$, we obtain that, with probability at least $\frac{1}{4}\delta$, for all $T \ge 1$, we have:

$$
\begin{align*}
T - N_T(\mathcal{Z}^{**}(M)^c) & \\
&\geq T - H^f(1 + N_T(\mathcal{Z}^{-}(M))) - H^f \sqrt{N_T(\mathcal{Z}^{**}(M)^c) \log\left(\frac{4N_T(\mathcal{Z}^{**}(M)^c)}{\delta}\right)} \\
&\geq T - H^f(1 + m) - H^f \sqrt{N_T(\mathcal{Z}^{**}(M)^c) \log\left(\frac{4N_T(\mathcal{Z}^{**}(M)^c)}{\delta}\right)}.
\end{align*}
$$

Rearranging terms, we get that with probability at least $\frac{1}{4}\delta$, for all $T \ge 1$, we have:

$$
\begin{align*}
& N_T(\mathcal{Z}^{**}(M)^c) \\
\leq & H^f \left( 1 + m + \sqrt{N_T(\mathcal{Z}^{**}(M)^c) \log(N_T(\mathcal{Z}^{**}(M)^c))} + \sqrt{N_T(\mathcal{Z}^{**}(M)^c) \log(\frac{4}{\delta})} \right).
\end{align*}
$$

Denoting $n := N_T(\mathcal{Z}^{**}(M))$, we have an equation of the form $n \le \alpha + \beta\sqrt{n \log(n)} + \gamma\sqrt{n}$. For $n \ge 3$, $n \log(n) \ge n$ hence we can simplify the upper-bound to $n \le \alpha + (\beta + \gamma)\sqrt{n \log(n)}$.
Dividing by $\log(n) \ge 1$ and setting $m := n/\log(n)$, we get $m \le \alpha + (\beta + \gamma)\sqrt{m}$, and simple algebra leads to:

$$ \frac{n}{\log(n)} = m \le 2(\alpha + (\beta + \gamma)^2). $$

Further using $\log(n) \le \sqrt{n}$, we get $n \le 4(\alpha + (\beta + \gamma)^2)^2$. We conclude that there exists a constant $m'$ such that:

$$ \mathbf{P}^M \left( \forall t \ge 1, \sum_{z \notin \mathcal{Z}^{**}(M)} N_t(z) \le m' \right) \ge \frac{1}{4}\delta. \qquad (65) $$

Now that (65) is established, we finally derive a contradiction by relying on a change of measure argument. Let $M^\dagger \in \text{Cnf}(M)$, which is non-empty by assumption. For short, the transition kernels and reward distributions of $M$ (respectively $M^\dagger$) are denoted $p$ and $r$ (respectively $p^\dagger$ and $r^\dagger$). We introduce the log-likelihood-ratio of observations $H_t := (S_t, A_t, R_1, \dots, A_{t-1}, R_{t-1}, S_t)$ as:

$$ L(t) \equiv L(H_t) := \sum_{s,a} \sum_{i<t-1} \mathbf{1}(S_i = s, A_t = a) \log \left( \frac{r_{s,a}(R_i) p_{s,a}(S_{i+1})}{r_{s,a}^\dagger(R_i) p_{s,a}^\dagger(S_{i+1})} \right). $$

It is known since Marjani et al. (2021) that if $\mathcal{E}$ is a $\sigma(H_t)$-measurable event, then $\mathbf{P}^{M^\dagger}(\mathcal{E}) = \mathbf{E}^M[\mathbf{1}(\mathcal{E}) \exp(-L(t))]$. Since $M \ll M^\dagger$, there exists a constant $c > 0$ such that, for all $z \in \mathcal{Z}$, we have $\log[(r_z(\alpha)/r_z^\dagger(\alpha)) \cdot (p_z(s')/p_z^\dagger(s'))] \le \log(c)$ with the convention $0/0 = 0$. For $z \in \mathcal{Z}^{**}(M)$, the LHS logarithm is null. Therefore, we have:

$$ \begin{aligned} & \mathbf{P}^{M^\dagger} \left( \sum_{z \notin \mathcal{Z}^{**}(M)} N_t(z) \le m' \right) \\ &= \mathbf{E}^M \left[ \mathbf{1} \left( \sum_{z \notin \mathcal{Z}^{**}(M)} N_t(z) \le m' \right) \exp(-L(t)) \right] \\ &\ge \mathbf{E}^M \left[ \mathbf{1} \left( \sum_{z \notin \mathcal{Z}^{**}(M)} N_t(z) \le m' \right) \exp \left( - \sum_{z \notin \mathcal{Z}^{**}(M)} N_t(z) \log(c) \right) \right] \\ &\ge c^{-m'} \mathbf{P}^M \left( \sum_{z \notin \mathcal{Z}^{**}(M)} N_t(z) \le m' \right) \ge c^{-m'} \delta := \delta' > 0. \end{aligned} $$

Accordingly, the algorithm has probability at least $\delta'$ to spend at most $m'$ visits outside $\mathcal{Z}^{**}(M)$ when running on $M^\dagger$. This will be in contradiction $M^\dagger \in \text{Cnf}(M)$ and the consistency of the algorithm. Indeed, since $M^\dagger \gg M$ coincides with $M$ on $\mathcal{Z}^{**}(M)$, we see that the optimal policy $\pi^*$ of $M$ has unique recurrent class $\mathcal{Z}^{**}(M)$ in $M^\dagger$. Yet, $\pi^* \notin \Pi^*(M^\dagger)$, hence $\mathcal{Z}^{**}(M) \cap \mathcal{Z}^-(M^\dagger) \ne \emptyset$, i.e., there exists $z \in \mathcal{Z}^{**}(M)$ such that $\Delta^*(z; M^\dagger) > 0$. We further link the number of visits of this $z$ to the total number of visits of $\mathcal{Z}^{**}(M)$ with the same technique that the one used to convert (64) to (65).
Introduce the reward function $f(z') := 1(z' = z)$, and let $g^f, h^f, \Delta^f$ be the gain, bias and gaps functions of the policy $\pi^*$ in $M^\dagger$. There exists $\epsilon > 0$ such that $g^f(s) = \epsilon$ for all $s \in S$. Letting $C := \text{sp}(h^f) \lor \max_{z'} |\Delta^f(z')| < \infty$. For all $T \ge 1$, we have

$$
\begin{align*}
N_T(z) &= \sum_{t=1}^{T} f(Z_t) = \sum_{t=1}^{T} (\epsilon + (e_{S_t} - p(Z_t))h^f - \Delta^f(Z_t)) \\
&\ge T\epsilon - C - C N_{\mathcal{Z}^{**}(M)^c}(T) + \sum_{t=1}^{T} (e_{S_{t+1}} - p(Z_t))h^f \\
&\stackrel{(\dagger)}{\ge} T\epsilon - C(1 + m') - C\sqrt{T \log(\frac{2T}{\delta'})} \sim T\epsilon.
\end{align*}
$$

where $(\dagger)$ holds with probability $\frac{1}{2}\delta' > 0$ uniformly for $T \ge 1$, by invoking a time-uniform Azuma-Hoeffding (see (Bourel et al., 2020, Lemma 5)) to lower-bound the right-hand martingale. We accordingly obtain, when $T \to \infty$,

$$
\mathrm{Reg}(T; M^{\dagger}) \geq \frac{1}{2}\epsilon\delta'\Delta^{*}(z; M^{\dagger})T = \Omega(T). \quad (66)
$$

So (66) is in contradiction with the consistency of the algorithm.

(STEP 4) If the algorithm is no-regret, has sub-linearly many episodes, then for all $M \in \mathcal{M}$ such that $\text{Cnf}(M) \neq \emptyset$, we have:

$$
\mathbf{P}^M (\forall T, \exists t \ge T : g^*(M) = g^{\pi_{t-1}}(S_{t-1}, M) \text{ and } \text{Reach}(\pi_t, S_t, M) \cap \mathcal{Z}^-(M) \neq \emptyset) = 1. \tag{67}
$$

Moreover, the stopping times $t$ enumerating times such that $g^*(S_{t-1}, M) = g^{\pi_{t-1}}(S_{t-1}, M)$ and $\text{Reach}(\pi_t, S_t, M) \cap \mathcal{Z}^-(M) \neq \emptyset$ are exploration times; Hence there are infinitely many of them with probability one.

**Proof** This is obtained by combining (62) of (STEP 2) and (63) of (STEP 3). We have:

$$
\mathbf{P}^M (\forall T, \exists t \ge T : g^*(S_{t-1}, M) = g^{\pi_t}(S_t, M) \text{ and } S_t \in \text{Rec}(\pi_t)) = 1, \text{ and} \quad (68)
$$

$$
\mathbf{P}^M (\forall T, \exists t \ge T : \text{Reach}(\pi_t, S_t, M) \cap \mathcal{Z}^-(M) \neq \emptyset) = 1. \quad (69)
$$

By non-degeneracy of $M$, if $g^*(S_t, M) = g^{\pi_t}(S_t, M)$ and $S_t \in \text{Rec}(\pi_t)$, then $\text{Reach}(\pi_t, S_t, M) = \mathcal{Z}^{**}(M)$ which is disjoint from $\mathcal{Z}^-(M)$. Define:

$$
\begin{align*}
\tau_1 &:= \inf\{t \ge 1 : g^*(S_t, M) = g^{\pi_t}(S_t, M) \text{ and } S_t \in \text{Rec}(\pi_t)\}, \\
\tau_{2i} &:= \inf\{t > \tau_{2i-1} : \text{Reach}(\pi_t, S_t, M) \cap \mathcal{Z}^-(M) \neq \emptyset\}, \\
\tau_{2i+1} &:= \inf\{t > \tau_{2i} : g^*(S_t, M) = g^{\pi_t}(S_t, M) \text{ and } S_t \in \text{Rec}(\pi_t)\}
\end{align*}
$$

Then $(\tau_i)$ is an increasing sequence of stopping times, and by (68) (69) applied in tandem, we show by induction that $\mathbf{P}^M(\tau_i < \infty) = 1$ for all $i \ge 1$. By non-degeneracy of $M$, at $t = \tau_{2i+1}$, the current policy is gain optimal and the process is currently on the optimal class $\mathcal{Z}^{**}(M)$. Because $\mathcal{Z}^{**}(M)$ is the disjoint union of sink components of $\mathcal{Z}^*(M)$, hence the only way to exit $\mathcal{Z}^{**}(M)$ is by playing a $z \in \mathcal{Z}^-(M)$. Therefore, we see that for $t = \tau_{2i}$, we must have $g^*(S_{t-1}, M) = g^{\pi_{t-1}}(S_{t-1}, M)$ with $\pi_{t-1} \ne \pi_t$. Accordingly, every $\tau_{2i}$ are change of episodes that are exploration episodes.

$\blacksquare$

This proves Proposition 38.
### G.3. Instance (in)dependent regrets for MDPs with non-empty confusing sets

In this section, we show (3.) ⇒ (2.) and (4.) ⇒ (2.) in Theorem 36 by showing the transpositions ¬(2.) ⇒ ¬(3.) in Proposition 39 and ¬(2.) ⇒ ¬(4.) in Proposition 40. In the statements below, we borrow the terminology introduced by Theorem 36. A learning algorithm $\Lambda$ is said **consistent** (on $\mathcal{M}$) if $\text{Reg}(T; M, \Lambda) = o(T^\epsilon)$ for all $\epsilon > 0$ and $M \in \mathcal{M}$. A learning algorithm $\Lambda$ is said **robust** (relatively to $\mathcal{M}$) if $\sup_{M' \in \mathcal{M}} \text{Reg}(T; M', \Lambda) = o(T)$.

**Proposition 39 (Consistent algorithms)** Let $M \in \mathcal{M}$ be such that $\text{Cnf}(M) \neq \emptyset$. Then every consistent learning algorithm $\Lambda$ satisfies $\text{Reg}(T; M, \Lambda) = \Omega(\log(T))$.

**Proof** This is a consequence of (Boone and Maillard, 2025, Corollary 7), that shows that every consistent learning algorithm $\Lambda$ is such that, for all $M^\dagger \in \text{Cnf}(M)$, we have:

$$ \mathbf{E}^{M,\Lambda} \left[ \sum_{z \in \mathcal{Z}} N_z(T) \text{KL}(q(z) || q^{\dagger}(z)) \right] \geq \log(T) + o(\log(T)) $$

where $q(z) = (r(z), p(z))$ is the reward-kernel tuple.

Fix $M^\dagger \in \text{Cnf}(M)$. Let $c := \max\{\text{KL}(q(z)||q^\dagger(z)) : q(z) \neq q^\dagger(z)\}$, that satisfies $c < \infty$ since $M \ll M^\dagger$. By definition of $\text{Cnf}(M)$, $M = M^\dagger$ coincide on $\mathcal{Z}^{**}(M)$, so $\text{KL}(q(z)||q^\dagger(z)) = 0$ for all $z \in \mathcal{Z}^{**}(M)$. Together with $\mathbf{E}[\sum_{z \in \mathcal{Z}} N_z(T) \text{KL}(q(z)||q^\dagger(z))] \leq |\mathcal{Z}| \max_{z \in \mathcal{Z}} \mathbf{E}[N_z(T)] \text{KL}(q(z)||q^\dagger(z))$, we deduce that:

$$ \forall T \geq 1, \quad \max_{z \notin \mathcal{Z}^{**}(M)} \mathbf{E}^{M,\Lambda}[N_z(T)] \geq \frac{\log(T) + o(\log(T))}{|\mathcal{Z}|c}. $$

Now, by (Boone and Maillard, 2025, Lemma 8), there exist constants $\alpha, \beta > 0$ such that $\mathbf{E}^{M,\Lambda}[\sum_{t=1}^T 1(Z_t \notin \mathcal{Z}^{**}(M))] \leq \alpha \text{Reg}(T; M, \Lambda) + \beta$ for all $T \geq 1$, so

$$ \text{Reg}(T; M, \Lambda) \geq \frac{\max_{z \notin \mathcal{Z}^{**}(M)} \mathbf{E}^{M,\Lambda}[N_z(T)] - \beta}{\alpha} \geq \frac{\log(T) + o(\log(T))}{|\mathcal{Z}|c\alpha}, $$

hence $\text{Reg}(T; M, \Lambda) = \Omega(\log(T))$. ■

**Proposition 40 (Robust algorithms)** Let $M \in \mathcal{M}$ be such that $\text{Cnf}(M) \neq \emptyset$. Then every robust learning algorithm $\Lambda$ satisfies $\text{Reg}(T; M, \Lambda) = \omega(1)$, i.e., $\text{Reg}(T; M, \Lambda) \to \infty$.

**Proof** This is a direct consequence of (STEP 3) of the proof of Proposition 38, see (63). Indeed, robust algorithms are by no-regret. So, by (63), the function given by

$$ f(T) := \inf_{T' \geq T} \left\{ \mathbf{P}^{M,\Lambda} \left( \exists t \in \{T, \dots, T' - 1\} : \Delta^*(Z_t) > 0 \right) \geq \frac{1}{2} \right\} $$

satisfies $T + 1 \leq f(T) < \infty$ for all $T \geq 0$. Introduce the (deterministic) sequence $T_1 := 1$ and $T_{k+1} := f(T_k)$, and introduce its pseudo-inverse $g(T) := \sup\{k \geq 1 : T_{k+1} \leq T\}$. Since $f(T) < \infty$, we have $T_k \to \infty$ and $g(T) \to \infty$. For $T \geq T_2$, we have:

$$ \text{Reg}(T; M, \Lambda) = \mathbf{E}^{M,\Lambda} \left[ \sum_{t=1}^{T} \Delta^*(Z_t) \right] $$
$$
\begin{align*}
&\geq \sum_{k=1}^{g(T)} \mathbf{E}^{M,\Lambda} \left[ \sum_{t=T_k}^{T_{k+1}-1} \Delta^*(Z_t) \right] \\
&\overset{(\dagger)}{\geq} \sum_{k=1}^{g(T)} c \mathbf{P}^{M,\Lambda} (\exists t \in \{T_k, \dots, T_{k+1}-1\} : \Delta^*(Z_t) > 0) \overset{(\ddagger)}{\geq} \frac{c \cdot g(T)}{2}
\end{align*}
$$

where $c := \min\{\Delta^*(z) : \Delta^*(z) > 0\} > 0$ is the minimum positive Bellman gap. We have $\frac{cg(T)}{2} \to \infty$ when $T \to \infty$, hence the conclusion. ■

G.4. MDPs with empty confusing sets are non-explorative

In this section, we show that if Cnf($M$) = $\emptyset$, then $M$ is non-explorative, there exists a consistent learning algorithm $\Lambda$ such that Reg($T$; $M$, $\Lambda$) = $o(\log(T))$ and there exists a robust learning algorithm $\Lambda'$ such that Reg($T$; $M$, $\Lambda'$) = $O(1)$. This corresponds to (2.) $\Rightarrow$ (1.), (3.), and (4.) in Theorem 36 hence completing the proof of all the equivalences. The implication (2.) $\Rightarrow$ (4.), stating the existence of a robust learning algorithm $\Lambda$ with Reg($T$; $M$, $\Lambda$) = $O(1)$ is done first, with Proposition 41. The proof is constructive, as we introduce a biased variant of KLUCRL Filippi et al. (2010) that is specialized to have bounded regret on $M$, see Algorithm 3. We prove (2.) $\Rightarrow$ (1.), i.e., that $M$ is non-explorative, in Proposition 42 and with the same algorithm. For (2.) $\Rightarrow$ (1.) and the proof of the existence of a consistent learning algorithm $\Lambda$ such that Reg($T$; $M$, $\Lambda$) = $o(\log(T))$, we provide the construction of the algorithm and simply sketch the proof.

G.4.1. A ROBUST ALGORITHM SPECIALIZED TO A NON-EXPLORATIVE MODEL

We begin by providing a robust algorithm $\Lambda$ such that $\text{Reg}(T; M, \Lambda) = O(1)$ for $M$ specifically.

**Proposition 41** *Consider a convex ambient space $M^* \equiv \prod_{z \in \mathcal{Z}} (R_z^* \times P_z^*)$ in product form and let $M \in M^*$ be non-degenerate. If $\text{Cnf}(M) = \emptyset$, there exists a learning algorithm $\Lambda$ that (1) is robust, (2) makes sub-linearly many episodes and (3) satisfies $\text{Reg}(T; M, \Lambda) = O(1)$.*

The algorithm that we consider is a variant of KLUCRL managing episodes with (DT), that is specialized for $M$. Also, we have to take into account that $M^*$ may not be the whole set of Markov decision processes with pair space $\mathcal{Z}$, i.e., we may have $M^* \neq \prod_{z \in \mathcal{Z}} ([0, 1] \times \mathcal{P}(S))$. It must be taken into account by the learning algorithm, as the property “$\text{Cnf}(M) = \emptyset$” depends on $M^*$—by definition (57), $\text{Cnf}(M) \subseteq M^*$ so if one increases $M^*$ to $M'$, the confusing set of $M$ relatively to $M'$ may become non-empty. So, the confidence region of KLUCRL, $\mathcal{M}(t)$, is constrained to $M^*$ to eventually exploit that $\text{Cnf}(M) = \emptyset$ relatively to $M^*$.

**Notations** We introduce the natural optimal policy of $M$, given by $\pi^*(s) = a$ where $a \in \mathcal{A}(s)$ is the unique element such that $(s, a) \in \mathcal{Z}^*(M)$. Further introduce:

$$
\begin{align*}
\mathcal{R}_z(t; M^*) &:= \{ \tilde{r}_z \in \mathcal{R}_z^* : N_z(t) \text{KL}(\hat{r}_z(t) || \tilde{r}_z) \le \log(2t) + \log(e(1 + N_z(t))) \} \\
\mathcal{P}_z(t; M^*) &:= \left\{ \tilde{p}_z \in \mathcal{P}_z^* : N_z(t) \text{KL}(\hat{p}_z(t) || \tilde{p}_z) \le \log(2t) + |S| \log \left( e \left( 1 + \frac{N_z(t)}{|S|-1} \right) \right) \right\}
\end{align*}
$$
Note that unlike (5) of the vanilla KLUCRL, $\log(t)$ is changed to $\log(2t)$. This is done so that $\mathbf{P}(\exists t \ge T : M \notin \mathcal{M}(t; \mathcal{M}^*)) = \mathcal{O}(T^{-2})$ instead of $\mathcal{O}(T^{-1})$ as in the vanilla version. The confidence region for $\pi^*$ is $\mathcal{M}_{\pi^*}(t; \mathcal{M}^*) := \prod_{s \in S}(\mathcal{R}_{s, \pi^*(s)}(t; \mathcal{M}^*) \times \mathcal{P}_{s, \pi^*(s)}(t; \mathcal{M}^*))$. Similarly to the whole confidence region $\mathcal{M}(t; \mathcal{M}^*)$, it can be seen as a Markov decision process with compact action space by extending its action space (see Section B.1) and EVI can be run on $\mathcal{M}_{\pi^*}(t; \mathcal{M}^*)$ to compute the optimistic gain of $\pi^*$, written $g^{\pi^*}(\mathcal{M}(t; \mathcal{M}^*))$.

**Idea of the algorithm** The designed algorithm is working by epochs of doubling sizes. Given an epoch $\{2^m, \dots, 2^{m+1} - 1\}$, it starts by iterating $\pi^* (2^m)^{2/3}$ times in a row. After that initial phase, the algorithms runs an altered version of KLUCRL that uses EVI specifically biased for $\pi^*$, that, when several policies are nearly optimistically optimal, prioritizes $\pi^*$.

<caption>**Algorithm 3 KLUCRL($\pi^*$, $\mathcal{M}^*$)**</caption>

1: **for** epochs $m = 0, 1, 2, \dots$ **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;Iterate $\pi^*$ for $t = 2^m, \dots, 2^m + 2^{2m/3}$;
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $t = 2^m + 2^{2m/3}, \dots, 2^{m+1}$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** (DT) triggers **or** $t = 2^m + 2^{2m/3}$
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow k + 1, t_k \leftarrow t$;
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\pi_{t_k} \leftarrow \text{EVI-b}_{\pi^*}(\mathcal{M}(t; \mathcal{M}^*), t)$;
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Set $\pi_t \leftarrow \pi_{t_k}$ and play $A_t \leftarrow \pi_t(S_t)$.
9: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
10: **end for**

<caption>**Algorithm 4 EVI-b$_\pi(\tilde{\mathcal{M}}, t)$**</caption>

1: Compute $\tilde{\pi} \leftarrow \text{EVI}(\tilde{\mathcal{M}})$;
2: Compute $\tilde{g}^* \leftarrow g^*(\tilde{\mathcal{M}})$;
3: Compute $\tilde{g}^\pi \leftarrow g^\pi(\tilde{\mathcal{M}})$;
4: **if** $\tilde{g}^* > \tilde{g}^\pi + \frac{\log(t)}{t^{1/3}}$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;**return** $\tilde{\pi}$;
6: &nbsp;&nbsp;&nbsp;&nbsp;**else**
7: &nbsp;&nbsp;&nbsp;&nbsp;**return** $\pi$.
8: **end if**

**Proof of Proposition 41** Proving that the algorithm is robust on $\mathcal{M}^*$ follows a similar line that Appendix B, that we won't detail here. The idea is that the forced exploration with $\pi^*$ last for at most $T^{2/3}$ time steps of the learning process, accounting for a regret of order $T^{2/3}$ if $\pi^*$ is not optimal. Later, the algorithm deploys policy that are $\frac{\log(T)}{T^{1/3}}$-optimistically optimal, inducing an extra cost of $T^{2/3} \log^2(T)$ compared to the vanilla analysis of KLUCRL. Therefore, the model independent regret is KLUCRL($\pi^*$, $\mathcal{M}^*$) is of order $T^{2/3} \log^2(T) = o(T)$.

Meanwhile, KLUCRL($\pi^*$, $\mathcal{M}^*$) makes $\mathcal{O}(\log(T))$ episodes: one for each epoch when playing $\pi^*$, and the others are triggered by (DT) that is known to produce logarithmically many episodes, see Auer et al. (2009) or Section B.5.

Last but not least, we argue that $\text{Reg}(T; M) = \mathcal{O}(1)$. Because this is an instance dependent result, the argument is different from Appendix B. The idea is to show that

$$ \mathbf{P}^M(\exists t \in \{2^m, \dots, 2^{m+1} - 1\} : \pi_t \neq \pi^*) = \mathcal{O}(4^{-m}). \quad (70) $$

Following (70), we have:

$$ \text{Reg}(T; M) \le \sum_{m=0}^{\infty} \mathbf{E}^M \left[ \sum_{t=2^m}^{2^{m+1}-1} \Delta^*(Z_t) \right] $$
$$
\begin{align*}
&\le \sum_{m=0}^{\infty} 2^m \max(\Delta^*) \mathbf{P}^M (\exists t \in \{2^m, \dots, 2^{m+1} - 1\} : \pi_t \ne \pi^*) \\
&\stackrel{(\dagger)}{\le} \max(\Delta^*) \sum_{m=0}^{\infty} \mathcal{O}(2^{-m}) = \mathcal{O}(1)
\end{align*}
$$

where (†) follows from (70). We now explain how (70) is established.

(STEP 1) There exists $c > 0$ such that, for $m$ large enough and $z \in \mathcal{Z}^{**}(M)$, we have:

$$
\mathbf{P}^M \left( \exists t \in \{2^m + 2^{2m/3}, \dots, 2^{m+1} - 1\} : N_z(t) < c 2^{2m/3} \right) = \mathcal{O}(4^{-m}).
$$

**Proof** The recurrent pairs of $\pi^*$ are precisely $\mathcal{Z}^{**}(M)$, i.e., $\mathbf{P}^{M,\pi^*}\{\forall m, \exists n \ge m : Z_n = z\} = 1$. Because the state space is finite, it follows that $\min_{z \in \mathcal{Z}^{**}(M)} \mathbf{E}^{M,\pi^*}[N_z(t)] \ge ct$ for some $c > 0$ when $t \to \infty$. It means that under $\pi^*$, every optimal pair is visited linearly many times in expectation. Fixing $z_0 \in \mathcal{Z}^{**}(M)$ and setting $f(z) = \mathbf{1}(z = z_0)$, we show that $N_{z_0}(t) \ge ct$ holds in probability as well. This is done as follows. Seeing $f$ as a reward function, $\pi^*$ has an associated gain and bias functions that we denote $g^f$ and $h^f$. These satisfy a Poisson equation $f(s, \pi(s)) + p(s, \pi(s))h^f = g^f(s) + h^f(s)$. By non-degeneracy, $\pi^*$ is unichain so $\text{sp}(g^f) = 0$, and we see that $g^f(s) \ge c$ for all $s \in S$. We continue as follows: If we only iterate $\pi^*$, then

$$
\begin{align*}
N_{z_0}(t) &= \sum_{i=1}^{t} f(Z_t) \\
&= \sum_{i=1}^{t} (g^f(S_t) + h^f(S_t) - p(Z_t)h^f) \ge ct - \text{sp}(h^f) + \sum_{i=1}^{t} (e_{S_{t+1}} - p(Z_t))h^f.
\end{align*}
$$

The RHS is a martingale and each term is almost surely bounded by sp(h^f). By Azuma-
Hoeffding’s inequality, it is therefore bounded by sp(h^f)√t log(αt)/2 = o(t) with probability
1 − 1/t^α. So, provided that t is large enough, we have N_z(t) ≥ 1/2 ct with probability 1 − 1/t^α.

Now, we know that on the time range {2^m, ..., 2^m + 2^{2m/3}}, the algorithm exclusively
iterates π*, so π* is iterate t = 2^{2m/3} times. Pick α = 3. ■

(STEP 2) There exists $C > 0$ such that for all $z \in \mathcal{Z}^{**}(M)$, we have

$$
\mathbf{P}^M \left( \begin{array}{l} \exists t \in \{2^m + 2^{2m/3}, \dots, 2^{m+1} - 1\} \\ \quad \exists \tilde{M}_t \equiv (\mathcal{Z}, \tilde{r}_t, \tilde{p}_t) \in \mathcal{M}(t; \mathcal{M}^*) \end{array} : \|\tilde{p}_t(z) - p(z)\|_1 + |\tilde{r}_t(z) - r(z)| > \frac{C\sqrt{\log(t)}}{t^{1/3}} \right) \\
= \mathcal{O}(4^{-m})
$$

**Proof** Fix $z \in \mathcal{Z}^{**}(M)$. By (STEP 1), we know that $N_z(t) > c2^{2m/3}$ with probability $1 - O(4^{-m})$ uniformly for $t \in \{2^m + 2^{2m/3}, \dots, 2^{m+1} - 1\}$. Using (Jonsson et al., 2020, Proposition 1) we find that for $m$ large enough,

$$
\mathbf{P}^M \left( \exists t \ge 1 : N_z(t) \ge c 2^{2m/3} \text{ and } \text{KL}(\hat{r}_t(z) || r(z)) > \frac{\log(2e \cdot 4^m)}{c 2^{2m/3}} \right) \le 4^{-m}.
$$
So, by Pinsker's inequality, it follows that for $m$ large enough, we have $|\hat{r}_t(z) - r(z)| \le C_r \sqrt{\log(t)t^{-1/3}}$ with probability $1 - O(4^{-m})$ uniformly for $t = 2^m + 2^{2m/3}, \dots, 2^{m+1} - 1$, where $C_r > 0$ is some constant. Now, by design of the confidence region $\mathcal{R}_z(t; \mathcal{M}^*)$, every $\tilde{r}_t(z) \in \mathcal{R}_z(t; \mathcal{M}^*)$ satisfies $|\tilde{r}_t(z) - \hat{r}_t(z)| \le \frac{1}{N_z(t)} \log(4et)$. By triangular inequality, we conclude that, for $z \in \mathcal{Z}^{**}(M)$, the inequality

$$|\tilde{r}_t(z) - r(z)| \le \frac{C\sqrt{\log(t)}}{t^{1/3}}$$

holds uniformly for $t = 2^m + 2^{2m/3}, \dots, 2^{m+1} - 1$ with probability $1 - O(4^{-m})$. Transition kernels are treated similarly. ■

(STEP 3) There exists a constant $C > 0$ such that

$$\mathbf{P}\left(\exists t = 2^m + 2^{2m/3}, \dots, 2^{m+1} - 1 : g^{\pi^*}(\mathcal{M}(t; \mathcal{M}^*)) + \frac{C\sqrt{\log(t)}}{t^{1/3}} \le g^*(\mathcal{M}(t; \mathcal{M}^*))\right) = O(4^{-m}).$$

**Proof** This is where we use that $C\mathcal{N}(M) = \emptyset$.

Let $\mathcal{E}_m$ be the event under which $M \in \mathcal{M}(t; \mathcal{M}^*)$ and $\|\tilde{p}_t(z) - p_z\|_1 + |\tilde{r}_t(z) - r(z)| \le C\sqrt{\log(t)t^{-1/3}}$ for all optimal pair $z \in \mathcal{Z}^{**}(M)$, uniformly for $t = 2^m + 2^{2m/3}, \dots, 2^{m+1} - 1$ and $\tilde{M}_t \equiv (\mathcal{Z}, \tilde{r}_t, \tilde{p}_t) \in \mathcal{M}(t; \mathcal{M}^*)$, where $C > 0$ is given by (STEP 2). Then, following (STEP 2) and the design of $\mathcal{M}(t; \mathcal{M}^*)$, we have $\mathbf{P}(\mathcal{E}_m) = 1 - O(4^{-m})$.

Fix $t \in \{2^m + 2^{2m/3}, \dots, 2^{m+1} - 1\}$ and let $\tilde{M} \in \mathcal{M}(t; \mathcal{M}^*)$ be a plausible model. Since $\mathcal{M}^*$ is convex, we can assume that $\tilde{M} \gg M$ up to changing $\tilde{M}$ to $(1 - \lambda)\tilde{M} + \lambda M$ for some arbitrarily small $\lambda > 0$. We show that, on $\mathcal{E}_m$,

$$g^{\pi^*}(M) + \frac{C_g \sqrt{\log(t)}}{t^{1/3}} \ge g^*(\tilde{M}) \quad (71)$$

for $C_g > 0$ some constant, independent from $\tilde{M}$ and $m$. Since, on $\mathcal{E}_m$ again, we further have $g^{\pi^*}(\mathcal{M}(t; \mathcal{M}^*)) \ge g^*(M)$, the result will follow from $\mathbf{P}(\mathcal{E}_m) = 1 - O(4^{-m})$.

We now show (71). Let $M \cup \tilde{M}$ be the Markov decision process with states $\mathcal{S}$ where the choice of an action from $s$ consists in (1) choosing $a \in \mathcal{A}(s)$ in the vanilla sense and (2) choosing whether the transition is made using $(r(s, a), p(s, a))$ or $(\tilde{r}(s, a), \tilde{p}(s, a))$. Note that $M \cup \tilde{M}$ is still a MDP with finite action space, that $g^*(M \cup \tilde{M}) \ge \max\{g^*(M), g^*(\tilde{M})\}$ and $D(M \cup \tilde{M}) \le D(M)$. In particular, $M \cup \tilde{M}$ is communicating and $\text{sp}(h^*(M \cup \tilde{M})) \le D(M)$. Using EVI on $M \cup \tilde{M}$ (see Section B.1) to compute its optimal gain, we extract a MDP $M^\dagger$ such that $g^*(M^\dagger) = g^*(M \cup \tilde{M})$ and $\text{sp}(h^*(M^\dagger)) \le D(M)$. By construction, $M^\dagger$ is a blend of $M$ and $\tilde{M}$, in the sense that $r^\dagger(z) \in \{r(z), \tilde{r}(z)\}$ and $p^\dagger(z) \in \{p(z), \tilde{p}(z)\}$. Let $M_0^\dagger$ be obtained from $M^\dagger$ by setting

$$M_0^\dagger(z) := \begin{cases} M(z) & \text{if } z \in \mathcal{Z}^{**}(M); \\ M^\dagger(z) & \text{if } z \notin \mathcal{Z}^{**}(M). \end{cases}$$
Note that since $\mathcal{M}^*$ is in product form and $\mathcal{M}(t; \mathcal{M}^*) \subseteq \mathcal{M}^*$, we have $M_0^\dagger \in \mathcal{M}^*$. It follows that $M_0^\dagger \in \mathcal{M}^*$ and $M_0^\dagger = M$ on $\mathcal{Z}^{**}(M)$. Moreover, since $\tilde{M} \gg M$, we have $M^\dagger \gg M$ and $M_0^\dagger \gg M$. So, because $\text{Cnf}(M) = \emptyset$, we have $\pi^* \in \Pi^*(M_0^\dagger)$. Accordingly,

$$g^{\pi^*}(M_0^\dagger) = g^*(M_0^\dagger) = g^*(M) \qquad (72)$$

where the second equality follows from the observation that $M_0^\dagger$ is a copy of $M$ on $\mathcal{Z}^{**}(M)$. Now, by construction $\mathcal{E}_m$, we know that the width of the confidence region is $O(\sqrt{\log(t)}t^{-1/3})$ on pairs of $\mathcal{Z}^{**}(M)$. Using the gain deviation inequality of Lemma 32, we conclude that on $\mathcal{E}_m$,

$$\begin{align}
\|g^{\pi^*}(M) - g^{\pi^*}(M^\dagger)\|_{\infty} &\le (1 + \text{sp}(h^*(M^\dagger))) O\left(\frac{\sqrt{\log(t)}}{t^{1/3}}\right) = O\left(\frac{\sqrt{\log(t)}}{t^{1/3}}\right) \tag{73} \\
\|g^*(M_0^\dagger) - g^*(M^\dagger)\|_{\infty} &\le (1 + \text{sp}(h^*(M^\dagger))) O\left(\frac{\sqrt{\log(t)}}{t^{1/3}}\right) = O\left(\frac{\sqrt{\log(t)}}{t^{1/3}}\right) \nonumber
\end{align}$$

where every $O(-)$ hides constants that are independent of $\tilde{M}$ and $m$. Since $g^*(M^\dagger) \ge g^*(\tilde{M})$, we conclude accordingly. ■

Finally, (70) is an immediate consequence of ((STEP 3)). ((STEP 3)) states that, uniformly for $t = 2^m + 2^{2m/3}, \dots, 2^{m+1} - 1$, we have:

$$g^{\pi^*}(\mathcal{M}(t; \mathcal{M}^*)) + \frac{C\sqrt{\log(t)}}{t^{1/3}} > g^*(\mathcal{M}(t; \mathcal{M}^*)) \qquad (74)$$

with probability $1 - O(4^{-m})$, where $C > 0$ is some constant independent of $m$. Now, by design of EVI-b$_{\pi^*}$ (Algorithm 4), if at $t = t_k \in \{2^m + 2^{2m/3}, \dots, 2^{m+1}\}$, we have $g^{\pi^*}(\mathcal{M}(t; \mathcal{M}^*)) + \log(t)t^{-1/3} \ge g^*(\mathcal{M}(t; \mathcal{M}^*))$, then EVI-b$_{\pi^*}$ outputs $\pi^*$. So, on the event prescribed by (74) and for $t \ge \exp(C^2)$, EVI-b$_{\pi^*}$ outputs $\pi^*$. Hence (70). ■

### G.4.2. MODELS WITH NON-EMPTY CONFUSING SET ARE NON-EXPLORATIVE

With the same algorithm, we show that non-degenerate Markov decision processes with empty confusing set are non-explorative.

**Proposition 42** Consider a convex ambient space $\mathcal{M}^* \equiv \prod_{z \in \mathcal{Z}} (\mathcal{R}_z^* \times \mathcal{P}_z^*)$ in product form and let $M \in \mathcal{M}^*$ be non-degenerate. If $\text{Cnf}(M) = \emptyset$, then $M$ is non-explorative, i.e., there exists a learning algorithm $\Lambda$ (1) with sub-linearly many episodes, (2) which is no-regret on $\mathcal{M}^*$ and (3) that has finitely many exploration episodes.

**Proof** We consider the algorithm KLUCRL($\pi^*$, $\mathcal{M}^*$) (Algorithm 3), introduced for the proof of Proposition 41. Following (70), we have:

$$\mathbf{P}^M(\exists t \ge 2^m : \pi_t \ne \pi^*) \le \sum_{n=m}^{\infty} \mathbf{P}^M(\exists t \in \{2^n, \dots, 2^{n+1} - 1\} : \pi_t \ne \pi^*)$$
$$= O\left(\sum_{n=m}^{\infty} 4^{-n}\right) = O(4^{-m}) = o(1).$$

So $\mathbf{P}^M(\exists T, \forall t \ge T : \pi_t = \pi^*) = 1$. Because every pair $z$ that $\pi^*$ can reach satisfies $\Delta^*(z; M) = 0$ by construction of $\pi^*$, it follows that $\mathbf{P}^M(\exists T, \forall t \ge T : \Delta^*(Z_t) = 0) = 1$. So necessarily, the number of exploration times (Definition 2) is almost-surely finite. ■

### G.4.3. A CONSISTENT ALGORITHM SPECIALIZED TO A NON-EXPLORATIVE MODEL

We conclude by arguing that the robust algorithm of [Proposition 41, KLUCRL($\pi^*$, $\mathcal{M}^*$)], can be adapted into a consistent learning algorithm $\Lambda'$ such that $\text{Reg}(T; M, \Lambda') = o(\log(T))$.

**Proposition 43** Consider a convex ambient space $\mathcal{M}^* \equiv \prod_{z \in \mathcal{Z}} (\mathcal{R}_z^* \times \mathcal{P}_z^*)$ in product form and let $M \in \mathcal{M}^*$ be non-degenerate. If $\text{Cnf}(M) = \emptyset$, there exists a learning algorithm $\Lambda$ that (1) is consistent; and (2) satisfies $\text{Reg}(T; M, \Lambda) = o(\log(T))$.

The considered algorithm is a reworked version of KLUCRL($\pi^*$, $\mathcal{M}^*$) (Algorithm 3). When tuning Algorithm 3 and Algorithm 4 to provide a robust algorithm, Algorithm 3 forces $\Omega(T^{2/3})$ iterations of the policy $\pi^*$. This is incompatible with consistency, as the latter implies that the model dependent regret is $\Omega(T^{2/3})$ when $\pi^*$ is not gain optimal. Instead, the algorithm will force $O(\log^3(T))$ iterations of $\pi^*$, losing robustness but achieving consistency. Then, the biased EVI adds a bonus to favor the selection of $\pi^*$, compensating the noise on the estimation of $g^{\pi^*}$.

**Algorithm 5** KLUCRL'($\pi^*$, $\mathcal{M}^*$)

1: **for** epochs $m = 0, 1, 2, \dots$ **do**

2: Set $\psi(2^m) \leftarrow \log(2^m)$;

3: Play $\pi^*$ for $t = 2^m, \dots, 2^m + \psi(2^m)$

4: **for** $t = 2^m + \psi(2^m), \dots, 2^{m+1}$ **do**

5: **if** (DT) triggers **or** $t = 2^m + \psi(2^m)$ **then**

6: $k \leftarrow k + 1, t_k \leftarrow t$;

7: $\pi_{t_k} \leftarrow \text{EVI-b}_{\pi^*}(\mathcal{M}(t; \mathcal{M}^*), t)$;

8: **end if**

9: Set $\pi_t \leftarrow \pi_{t_k}$ and play $A_t \leftarrow \pi_t(S_t)$.

10: **end for**

11: **end for**

**Algorithm 6** EVI-b'($\tilde{\mathcal{M}}$, $t$)

1: Compute $\tilde{\pi} \leftarrow \text{EVI}(\tilde{\mathcal{M}})$;

2: Compute $\tilde{g}^* \leftarrow g^*(\tilde{\mathcal{M}})$;

3: Compute $\tilde{g}^\pi \leftarrow g^\pi(\tilde{\mathcal{M}})$;

4: **if** $\tilde{g}^* > \tilde{g}^\pi + \sqrt{\frac{1}{\log(t)}}$ **then**

5: **return** $\tilde{\pi}$;

6: **else**

7: **return** $\pi$.

8: **end if**

**Sketch of proof** Proving Proposition 43 in full detail is, again, tedious. As the proof follows from techniques that are quite similar to Proposition 41, we only leave the main ideas. We fix $M' \in \mathcal{M}^*$ and look at whether $M' = M$ or $M' \neq M$.

If $M' \neq M$, we prove that $\text{Reg}(T; M') = O(\log^3(T))$ when $T \gg \exp\{(g^*(M') - g^{\pi^*}(M'))^{-1}\}^2$. $T$ needs to be large in order to compensate for the bonus that Algorithm 6 puts on the optimistic gain of $\pi^*$, that intentionally overshoots the empirical noise on $g^{\pi^*}$, i.e., the value of $|g^{\pi^*}(\hat{M}_t) - g^{\pi^*}(M)|$. Beyond that subtlety, we enumerate $z \notin \mathcal{Z}^*(M)$ and we
distinguish the cases where $Z_t = z$ depending on whether (1) $z$ is transient under the currently deployed policy or (2) $z$ is recurrent under the currently deployed policy and (3) $z$ is a recurrent pair of $\pi^*$ and $t \in \bigcup_m \{2^m, \dots, 2^m + \psi(m)\}$ is within a forced exploration phase. The first is proportionally to the number of episodes, which is $O(\log(T))$, while the second implies that confidence regions are wrong. As discussed above, when taking account of the bonus in Algorithm 6, confidence regions start to be correct when $T \gg \exp\{(g^*(M') - g^{\pi^*}(M'))^{-1}\}^2$, leading to an error that sums as $O(1)$ overall. The third accounts for $O(\log^3(T))$ which is eventually the dominant term in the regret bound.

If $M' = M$, we prove that $\text{Reg}(T; M) = \text{O}(1)$ with the exact same proof technique as Proposition 41, by establishing an equation in the style of (70) with the same proof strategy (STEP 1, 2, 3), adapted to a forced exploration of $\Theta(\log^3(T))$ rather than $\Theta(T^{1/3})$. ■

### G.5. Interior Markov decision processes are universally explorative

We conclude the discussion on explorative spaces by discussing examples of explorative spaces, and how common the property "$M \in \mathcal{M}^+$" may be. As shown in Section G.1, when the ambient space $\mathcal{M}$ is a fixed kernel space (i.e., is of the form $\mathcal{M} = \prod_{z \in \mathcal{Z}} (\mathcal{R}_z \times \{p(z)\})$ for some fixed $p \in \mathcal{P}(\mathcal{S})^\mathcal{Z}$) and $\mathcal{R}_z \subseteq [0, 1]$, large portions of $\mathcal{M}$ may be non-explorative. For instance, taking

$$ \mathcal{M} := \{ M \equiv (\mathcal{Z}, r, p) : r \in [0, 1]^\mathcal{Z} \text{ and } \forall z \in \mathcal{Z}, \forall s \in \mathcal{S}, p(s|z) \in \{0, 1\} \} $$

the space of deterministic transition Markov decision processes with pair space $\mathcal{Z}$, one can generalize the example of Section G.1 to show that as soon as $|\mathcal{Z}| > |\mathcal{S}|$, a model picked in $\mathcal{M}$ uniformly at random is non-explorative with positive probability.

The take-away of this observation is that if $\mathcal{M}$ is structured, then $\mathcal{M}^+$ can be large. In Proposition 44 below, we prove a complementary result: If $\mathcal{M}$ has no structure, then every (non-degenerate) model in the interior (see Assumption 4) of $\mathcal{M}$ is explorative. It follows (see Corollary 45) that if the ambient space $\mathcal{M}$ has no structure and if $M \in \mathcal{M}$ is picked uniformly at random, then $M$ is explorative almost surely. This property is very convenient for experiments: Any Markov decision processes that is generated randomly is a good environment to investigate regret of exploration guarantees.

**Proposition 44 (Interior implies explorative)** Let $\mathcal{M} = \prod_{z \in \mathcal{Z}} ([0, 1] \times \mathcal{P}(\mathcal{S}))$ be the space of all Markov decision processes with pair space $\mathcal{Z}$, with $|\mathcal{Z}| > |\mathcal{S}|$. Then every non-degenerate (n.d.) interior model is explorative, i.e.,

$$ \{M \equiv (\mathcal{Z}, r, p) \text{ n.d. : } \forall z \in \mathcal{Z}, \text{supp}(r(z)) = \{0, 1\} \text{ and } \text{supp}(p(z)) = \mathcal{S}\} \subseteq \mathcal{M}^+. $$

**Proof** Let $M \in \mathcal{M}$ be a non-degenerate interior model. We show that $\text{Cnf}(M) \neq \emptyset$. Because $|\mathcal{Z}| > |\mathcal{S}|$ and $M$ is non-degenerate, there exists $z_0 \in \mathcal{Z} \setminus \mathcal{Z}^*(M)$. By definition, $\Delta^*(z_0; M) > 0$ so that this pair cannot be recurrent under any gain optimal policy of $M$. For $\epsilon > 0$, define $M_\epsilon \equiv (\mathcal{Z}, r_\epsilon, p_\epsilon)$ the Markov decision process given by:

$$ p_{\epsilon}(z) := \begin{cases} p(z) & \text{if } z \neq z_0 \\ (1 - \epsilon)e_{s_0} + \epsilon \cdot p(z) & \text{if } z = z_0 \end{cases} \quad \text{and} \quad r_{\epsilon}(z) := \begin{cases} r(z) & \text{if } z \neq z_0 \\ 1 - \epsilon + \epsilon \cdot r(z) & \text{if } z = z_0 \end{cases} $$
where $z_0 \equiv (s_0, a_0)$ and $e_{s_0}$ is the Dirac at $s_0$. By construction, $M_\epsilon \gg M$ for all $\epsilon > 0$. Let $\pi$ be the (randomized) policy that picks actions uniformly at random from $s \neq s_0$ and with $\pi(s_0) = a_0$. It is clear that as $\epsilon \to 0$, we have $g^\pi(M_\epsilon) \to 1$ because $\pi$ converges to a unichain policy that converges to a loop on $s_0$ where it scores $1 - \epsilon$. Now, if $\pi^* \in \Pi^*(M)$, we have $g^{\pi^*}(M_\epsilon) = g^{\pi^*}(M)$ since $\pi^*$ does not pick $a_0$ from $s_0$. So, for $\epsilon > 0$ small enough, we have $g^\pi(M_\epsilon) > g^{\pi^*}(M_\epsilon)$ for all $\pi^* \in \Pi^*(M)$. For such $\epsilon > 0$, we have $\Pi^*(M_\epsilon) \cap \Pi^*(M) = \emptyset$ and it follows that $M_\epsilon \in \text{Cnf}(M)$. So $\text{Cnf}(M) \neq \emptyset$ and $M$ is explorative from Theorem 36. $\blacksquare$

**Corollary 45** Let $\mathcal{M} \equiv \prod_{z \in \mathcal{Z}} ([0, 1] \times \mathcal{P}(\mathcal{S}))$ be the space of all Markov decision processes with pair space $\mathcal{Z}$, with $|\mathcal{Z}| > |\mathcal{S}|$. Let $\mathcal{M} \equiv (\mathcal{Z}, r, \mathcal{Z})$ where $r(z) \sim \text{U}[0, 1]$ and $p(z) \sim \text{U}(\mathcal{P}(\mathcal{S}))$ are sampled independently. Then $\mathcal{M} \in \mathcal{M}^+$ almost surely.

**Proof** If $\mathcal{M}$ is picked at random as described above, then $\mathcal{M}$ is interior with probability one. Meanwhile, the set of degenerate models of a fixed arbitrary kernel $p \in \mathcal{P}(\mathcal{S})$ is of measure zero, see Corollary 35. Integrating, the set of degenerate models is negligible in $\mathcal{M}$ for the Lebesgue measure. Hence, if $\mathcal{M}$ is picked at random described, then $\mathcal{M}$ is non-degenerate with probability one. $\blacksquare$