$$ \lesssim C_{\bar{\epsilon}}(e, M_1) \|d\mu\|_{\infty} + |dC|. \qquad (B.36) $$

We conclude by combining (B.35) and (B.36) and by invoking the bounds of (B.32). Then, this bound can be simplified as

$$ \|\mu_{\bar{\epsilon}}^*(M_2) - \mu_{\bar{\epsilon}}^*(M_1)\|_{\infty} = O\left(\sqrt{\frac{\|M_2 - M_1\|^*}{(\epsilon_{\text{unif}})^{3|S|}\epsilon_{\text{conv}}}}\right) $$

under same condition (B.33) that we simplify as (B.34) as well. Hence the bound on the variations of $\mu_{\bar{\epsilon}}^*$ described in Proposition B.18. ■

### B.3.7 AUXILIARY RESULTS

In this paragraph, we provide a few instrumental results, starting with the sensibility of the optimal gain function to perturbation of the reward vector and of the transition kernel.

**Lemma B.19** (Variations of the optimal gain). Let $M \equiv (\mathcal{Z}, p, r)$ and $M' \equiv (\mathcal{Z}, p', r')$ be two Markov decision processes (possibly of infinite diameter). If $\text{sp}(g^*(M)) = 0$, then

$$ \|g^*(M') - g^*(M)\|_{\infty} \le \|r' - r\|_{\infty} + \frac{1}{2}\text{sp}(b^*(M))\|p' - p\|_{\infty}. $$

**Proof** Let $\pi^*$ be a bias optimal policy of $M$. We have $\text{sp}(g^*(M)) = 0$, so by Lemma D.8,

$$ \|g^{\pi^*}(M') - g^*(M)\|_{\infty} = \|g^{\pi^*}(M') - g^{\pi^*}(M)\|_{\infty} \le \|r' - r\|_{\infty} + \frac{1}{2}\text{sp}(b^*(M))\|p' - p\|. \quad (B.37) $$

Now, consider $\pi \in \Pi$ an arbitrary policy and fix $s \in S$.

$$ \begin{aligned} g^{\pi}(s; M') &= \lim_{T \to \infty} \frac{1}{T} \mathbf{E}_s^{\pi, M'} \left[ \sum_{t=1}^{T} r'(Z_t) \right] \\ &\le \lim_{T \to \infty} \frac{1}{T} \mathbf{E}_s^{\pi, M'} \left[ \sum_{t=1}^{T} r(Z_t) \right] + \|r' - r\|_{\infty} \\ &\stackrel{(\dagger)}{=} \lim_{T \to \infty} \frac{1}{T} \mathbf{E}_s^{\pi, M'} \left[ \sum_{t=1}^{T} (g^*(M) + (e_{S_t} - p(Z_t))b^*(M) - \Delta^*(Z_t; M)) \right] + \|r' - r\|_{\infty} \\ &\le \lim_{T \to \infty} \frac{1}{T} \mathbf{E}_s^{\pi, M'} \left[ \sum_{t=1}^{T} (e_{S_t} - p(Z_t))b^*(M) \right] + g^*(M) + \|r' - r\|_{\infty} \\ &\stackrel{(\ddagger)}{=} \lim_{T \to \infty} \frac{1}{T} \mathbf{E}_s^{\pi, M'} \left[ \sum_{t=1}^{T} (p'(Z_t) - p(Z_t))b^*(M) \right] + g^*(M) + \|r' - r\|_{\infty} \\ &\stackrel{(\S)}{\le} \lim_{T \to \infty} \frac{1}{T} \mathbf{E}_s^{\pi, M'} \left[ \sum_{t=1}^{T} (p'(Z_t) - p(Z_t))b^*(M) \right] + g^*(M) + \|r' - r\|_{\infty} \\ &\le g^*(M) + \|r' - r\|_{\infty} + \frac{1}{2}\text{sp}(b^*(M))\|p' - p\|_{\infty} \end{aligned} $$

where $(\dagger)$ is obtained by definition of $\Delta^*(M)$ and Doob's optional stopping theorem; $(\ddagger)$ uses that since $\text{sp}(g^*(M)) = 0$, we have $\Delta^*(M) \ge 0$; $(\S)$ uses that $\mathbf{E}_s^{\pi, M'}[\sum_{t=1}^{T}(e_{S_t} - p'(Z_t))b^*(M)] = \mathbf{E}_s^{\pi, M'}[b^*(s; M) - b^*(S_{T+1}; M)] \le \text{sp}(b^*(M))$; and $(\S)$ follows from $|(p'(z) - p(z))b^*(M)| \le \frac{1}{2}\text{sp}(b^*(M))\|p'(z) - p(z)\|_1$ for $z \in \mathcal{Z}$.

We conclude by combining the above with (B.37).

<figure><img src="image_15.png" /></figure>

In Lemma B.20 below, we recall a classical result linking the bias span to the diameter.
**Lemma B.20** (Bartlett and Tewari (2009); Fruit (2019)). Let $M \equiv (\mathcal{Z}, p, r)$ be a communicating Markov decision process. Then $\text{sp}(b^*(M)) \le \text{sp}(r)D(M)$

**Proof** This result is well-known. We provide a proof for self-containedness. Let $s \ne s'$ and let $\pi \in \Pi$ be a policy such that $\mathbf{E}_s^{M,\pi}[\tau_{s'}] < \infty$, where $\tau_{s'} := \inf\{t \ge 1 : S_t = s'\}$. We have

$$ 
\begin{aligned}
\mathbf{E}_s^{M,\pi} \left[ \sum_{t=1}^{\tau_{s'}-1} (g^* - R_t) \right] &\stackrel{(\dagger)}{=} \mathbf{E}_s^{M,\pi} \left[ \sum_{t=1}^{\tau_{s'}-1} (p(Z_t)b^* - b^*(S_t) + \Delta^*(Z_t)) \right] \\
&\stackrel{(\ddagger)}{=} \mathbf{E}_s^{M,\pi} \left[ \sum_{t=1}^{\tau_{s'}-1} (b^*(S_{t+1}) - b^*(S_t)) \right] + \mathbf{E}_s^{M,\pi} \left[ \sum_{t=1}^{\tau_{s'}-1} \Delta^*(Z_t) \right] \\
&\stackrel{(\S)}{\ge} b^*(s') - b^*(s)
\end{aligned}
$$

where $(\dagger)$ follows by definition of $\Delta^*$; $(\ddagger)$ uses that $\mathbf{E}[e_{S_{t+1}}|Z_t] = p(Z_t)$; and $(\S)$ follows from the Bellman equation $\Delta^*(Z_t) \ge 0$. On the other hand, we see that $\mathbf{E}_s^{M,\pi}[\sum_{t=1}^{\tau_{s'}-1}(g^* - R_t)] \le \text{sp}(r)\mathbf{E}[\tau_{s'}]$. Taking the infimum for $\pi \in \Pi$, we conclude. ■

In Lemma B.21 below, we bound the sensibility of KL($p||q$) to perturbations of $p$ and $q$.

**Lemma B.21.** Let $p \ll q \in \mathcal{P}[m]$ and $p' \ll q' \in \mathcal{P}[m]$ be two pairs of categorical distributions over $m$ elements. Assume that $\text{supp}(p) = \text{supp}(p')$ and that, for all $i \in \text{supp}(p)$, we have $(1 - \varepsilon)p'_i \le p_i \le (1 + \varepsilon)p'_i$ and $(1 - \varepsilon)q'_i \le q_i \le (1 + \varepsilon)q'_i$ for some $\varepsilon \le \frac{1}{2}$. Then

$$ 
\begin{aligned}
(1 - \varepsilon)\text{KL}(p' || q') - 2\varepsilon \log(em) &\le \text{KL}(p || q) \le (1 + \varepsilon)\text{KL}(p' || q') + 2\varepsilon \log(em) \\
(1 - \varepsilon)\text{KL}(p || q) - 2\varepsilon \log(em) &\le \text{KL}(p' || q') \le (1 + 2\varepsilon)\text{KL}(p || q) + 2\varepsilon \log(em)
\end{aligned}
$$

**Proof** Using that $\log(1+x) \le x$ and $\log(1-x) > -x$ for $x \in [0, \frac{1}{2}]$, we get on the one hand:

$$ 
\begin{aligned}
\sum_{i=1}^{m} p_i \log\left(\frac{p_i}{q_i}\right) &= -\sum_{i=1}^{m} p_i \log\left(\frac{1}{p_i}\right) + \sum_{i=1}^{m} p_i \log\left(\frac{1}{q_i}\right) \\
&\le -(1 - \varepsilon) \sum_{i=1}^{m} p'_i \log\left(\frac{1}{(1 + \varepsilon)p'_i}\right) + (1 + \varepsilon) \sum_{i=1}^{m} p'_i \log\left(\frac{1}{(1 - \varepsilon)q'_i}\right) \\
&= (1 + \varepsilon)\text{KL}(p' || q') + 2\varepsilon\text{Ent}(p') + (1 - \varepsilon')\log(1 + \varepsilon) - (1 + \varepsilon)\log(1 - \varepsilon) \\
&\le (1 + \varepsilon)\text{KL}(p' || q') + 2\varepsilon \log(em).
\end{aligned}
$$

On the other hand,

$$ 
\begin{aligned}
\sum_{i=1}^{m} p_i \log\left(\frac{p_i}{q_i}\right) &= -\sum_{i=1}^{m} p_i \log\left(\frac{1}{p_i}\right) + \sum_{i=1}^{m} p_i \log\left(\frac{1}{q_i}\right) \\
&\ge -(1 + \varepsilon) \sum_{i=1}^{m} p'_i \log\left(\frac{1}{(1 - \varepsilon)p'_i}\right) + (1 - \varepsilon) \sum_{i=1}^{m} p'_i \log\left(\frac{1}{(1 + \varepsilon)q'_i}\right) \\
&\ge (1 - \varepsilon)\text{KL}(p' || q') - 2\varepsilon\text{Ent}(p') + (1 + \varepsilon)\log(1 - \varepsilon) - (1 - \varepsilon)\log(1 + \varepsilon) \\
&\ge (1 - \varepsilon)\text{KL}(p' || q') - 2\varepsilon \log(em).
\end{aligned}
$$

This concludes the proof. The second pair of inequalities are derived from the first two. ■
Appendix C. Regret analysis of ECoE*

In this section, we provide a regret analysis of ECoE* (Algorithm 2) and we prove Theorem 7, that shows that Reg(T; M, ECoE*) ≤ K(M) log(T) + o(log(T)).

As ECoE* is the only algorithm of interest in the sequel, we drop the dependence in Λ ≡ ECoE* in notations. Similarly, the underlying Markov decision process will be always equal to M throughout, so that we will drop the dependent in M as well. We end up writing E[-] and P(-) in place of E[M, ECoE*[-] and P[M, ECoE*(-)

The starting point of the regret analysis is to write the expected regret as

$$
\mathrm{Reg}(T) = \mathbf{E} \left[ \sum_{z \in \mathcal{Z}} N_T(z) \Delta^*(z) \right] + \mathrm{O}(1)
$$

As Δ*(z) ≥ 0, the natural strategy is to upper-bound E[M,Λ[N<sub>T</sub>(z)]] for pairs with Δ*(z) > 0. Such pairs corresponds in particulars to non-optimal pairs z /∈ Z<sup>**</sup>(M), see Section 2.1.4. In Theorem C.1 below, we upper-bound E[N<sub>T</sub>(z)] for a large panel of choices for the regularization hyperparameter of ECoE*. The set of assumptions that the regularization must satisfy is technical and detailed in Appendix C.1, see Assumption 6.

**Theorem C.1** (Visit rates of ECoE\*, general statement). *Assume that the regularization hyperparameter *ε* satisfies Assumption 6, and that the ambient space *M* has Bernoulli rewards (Assumption 3) and strong product structure (Assumption 5). Fix *M* ∈ *M* a communicating Markov decision process. Let *μ*\* the central optimal exploration probability measure of *M* as given by Definition B.3. For every non-optimal pair *z* /∈ Z\*\*(M), its expected number of visits under ECoE\* satisfies*

$$
\mathbf{E}[N_T(z)] \le \frac{\mu^*(z) \log(T)}{C(\mu^*, M)} + O\left(\frac{1}{\varepsilon_{\text{lvl}}(T)^6} + \sum_{t=1}^{T-1} \exp\left(-\left(1 + \frac{1}{2}\varepsilon_{\text{stt}}(t)\right) \log(t)\right)\right) + o(\log(T))
$$

when T → ∞.

Theorem 7 is an immediate corollary of Theorem C.1 for the choice of regularizer described
in (18), because the second order term grows as ε<sub>lvl</sub>(T)<sup>-6</sup> + ∫<sub>t</sub><sup>T</sup> (1/t)<sup>1+ε<sub>stt</sub>(t)</sup> dt = o(log(T)).

**Outline.** The proof is tedious. The idea is to decompose the number of visits of *z* /∈ Z\*\*(M) along with the decomposition of time instants that is inherent to Algorithm 2: There are exploration times *t* ∈ T\*, co-exploration times *t* ∈ T\*, exploitation times T\* and panic times T\*. As T\* ⊆ T\*, we decompose *N*<sub>*T*</sub>(*z*) as

$$
N_T(z) = \sum_{t=1}^{T-1} \mathbf{1}(Z_t = z, t \in \mathcal{T}^-) + \sum_{t=1}^{T-1} \mathbf{1}(Z_t = z, t \in \mathcal{T}^+) + \sum_{t=1}^{T-1} \mathbf{1}(Z_t = z, t \in \mathcal{T}^!). \quad (C.1)
$$

That is, we distinguish three cases in (C.1). Either Z_t = z is played because (I) the algorithm
is exploring to collect information on presumably sub-optimal pairs; or (II) because it
is exploiting the (wrongly) presumed optimal policy; (III) the algorithm just panicked by
discovering a transition unseen so far.

We begin by (II) in Appendix C.2, i.e., by bounding the number of times a sub-optimal
pair may be played during exploitation and show that it is of order ε<sub>lvl</sub>(T)<sup>-6</sup> + ∫<sub>t</sub><sup>T</sup> exp(-(1+
$\varepsilon_{\text{tst}}(t)) \log(t))dt$. From there, simple algebra provides conditions on how small $\varepsilon_{\text{lvl}}$ and $\varepsilon_{\text{tst}}$ must be so that this term is sub-logarithmic, leading to Assumption 6. In Appendix C.3, we show that the dominant is due to exploration (I), for a total number of visits of order $\mu^*(z)C(\mu^*, M)^{-1} \log(T)$, where $\mu^*$ is central optimal exploration measure of $M$. Lastly, the number of panic times (III) is upper-bounded by $|\mathcal{Z}| |\mathcal{S}|$ in Appendix C.4.

## C.1 Required assumptions on the regularization hyperparameter

In the regret analysis, we assume that the regularization hyperparameter $\bar{\varepsilon}$ satisfies Assumption 6. These assumptions are technical and we invite the reader to only take them into consideration when necessary. It is easy to check that Assumption 6 is satisfied for $\bar{\varepsilon}$ chosen as in (18) in the main text.

**Assumption 6 (Properties of regularization hyperparameter).** The regularization hyperparameter $\bar{\varepsilon} \equiv (\varepsilon_{\text{lvl}}, \varepsilon_{\text{unif}}, \varepsilon_{\text{conv}}, \varepsilon_{\text{tst}}) : \mathbf{N} \to (0, 1]$ satisfies

(A0) The map $\bar{\varepsilon}$ is vanishing, i.e., $\bar{\varepsilon}(m) \to 0$ as $m \to \infty$;

(A1) The map $\bar{\varepsilon}$ is non-increasing for the product order $\leq$, i.e., $\bar{\varepsilon}(n) \leq \bar{\varepsilon}(m)$ for $n \geq m$;

(A2) For all $\alpha > 0$, $\varepsilon_{\text{lvl}}(T) = \omega(\log(T)^{-\alpha})$ when $T \to \infty$;

(A3) For all $\alpha > 0$, $\varepsilon_{\text{conv}}(m) = \omega(m^{-\alpha})$ when $m \to \infty$;

(A4) For all $\alpha > 0$, $\varepsilon_{\text{unif}}(m) = \omega(\log(m)^{-\alpha})$ when $m \to \infty$;

(A5) We have $\varepsilon_{\text{unif}}(m) = o(\varepsilon_{\text{conv}}(m))$ when $m \to \infty$;

(A6) For all $(\alpha_i) \geq 0$, the function $\varphi_{\alpha}(m) := \varepsilon_{\text{conv}}(m)^{\alpha_1} \varepsilon_{\text{unif}}(m)^{\alpha_2} \exp(-\alpha_3 \varepsilon_{\text{unif}}(m)^{-\alpha_4})m$ is non-decreasing asymptotically, i.e., $\exists m_{\alpha}, \forall \ell' \geq \ell \geq m_{\alpha}, \varphi_{\alpha}(\ell') \leq \varphi_{\alpha}(\ell)$;

(A7) $\varepsilon_{\text{tst}}(T) = \omega(\log \log(T) \log(T)^{-1})$ when $T \to \infty$;

## C.2 Amount of wrong exploitation

In this section, we upper-bound the number of “wrong” exploitation times, i.e., the amount of time spent playing the approximately optimal empirical policy $\pi_t^+$ while $\pi_t^+$ is a sub-optimal policy of the true hidden model $M$.

**Lemma C.2.** For all $z \notin \mathcal{Z}^{**}(M)$, we have

$$ \mathbf{E} \left[ \sum_{t=1}^{T-1} 1(Z_t = z, t \in \mathcal{T}^+) \right] = O \left( \frac{1}{\varepsilon_{\text{lvl}}(T)^6} + \sum_{t=1}^{T-1} \exp \left( - \left( 1 + \frac{1}{2} \varepsilon_{\text{tst}}(t) \right) \log(t) \right) \right) \quad (C.2) $$

All throughout, we fix a non-optimal pair $z_0 \notin \mathcal{Z}^{**}(M)$.
### C.2.1 IDEA OF THE PROOF

To begin with, note that the algorithm only takes decisions at initial exploitation times. Therefore, it is only relevant to decompose $t \in \mathcal{T}^+$ according to good events if $t \in \mathcal{T}_0^+$. Thankfully, the number of exploitation times $|\mathcal{T}^+|$ and the number of initial exploitation times $|\mathcal{T}_0^+|$ are proportional to one another, because exploitation phases are either done up to regeneration or killed by the discovery of an unseen transition; Both happen quickly in average and exploitation phases are short. This is formalized in Lemma C.3.

**Lemma C.3.** For all $z_0 \notin \mathcal{Z}^{**}(M)$, we have

$$ \mathbf{E}\left[\sum_{t=1}^{T-1} \mathbf{1}(Z_t = z_0, t \in \mathcal{T}^+)\right] = \Theta\left(\mathbf{E}\left[\sum_{t=1}^{T-1} \mathbf{1}(z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}(t)}^{**}(\hat{M}_t), t \in \mathcal{T}_0^+)\right]\right) \quad \text{as } T \to \infty. $$

The proof of Lemma C.3 relies on the notion of **co-exploration structure** and is postponed to Appendix C.2.2.

Introduce the good events

$$ \begin{aligned} \mathcal{E}_t &:= \left( \forall z \in \mathcal{Z}_t^{\text{skel}}, \kappa(M) \|\hat{M}_t(z) - M(z)\|^* < \varepsilon_{\text{lvl}}(t) < \frac{1}{3} \Delta^g(M) \right); \text{ and} \\ \mathcal{E}'_t &:= \left( \forall z \in \mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t), \kappa(M) \|\hat{M}_t(z) - M(z)\|^* < \varepsilon_{\text{lvl}}(t) < \frac{1}{3} \Delta^g(M) \right) \end{aligned} \quad (C.3) $$

where $\kappa(M) := \max\{C(M), 1 + D^*(M)\} < \infty$ is the maximum between the constant $C(M)$ given by Proposition 3 and the worst diameter (Definition A.3); and $\Delta^g(M)$ is the gain-gap of $M$ (Definition A.4). The first event $\mathcal{E}_t$ states that the data is approximately correct on the skeleton and the second $\mathcal{E}'_t$ that it is approximately correct on leveled optimal pairs. Note that under $\mathcal{E}_t \cap \mathcal{E}'_t$, we have $\|\hat{M}_t(z) - M(z)\|^* < \infty$ for every pair $z \in \mathcal{Z}_t^{\text{skel}} \cup \mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t)$, so that $\hat{M}_t(z) \sim M(z)$.

**Decomposition in good events.** Following Lemma C.3, we are left to bound the number of initial exploitation times with $\mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t) \setminus \mathcal{Z}^{**}(M) \neq \emptyset$. Under the event $(\mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t) \setminus \mathcal{Z}^{**}(M) \neq \emptyset)$, leveled optimal pairs are wrong and the algorithm may play sub-optimal pairs during exploitation. Yet, if the algorithm exploits at time $t \in \mathcal{T}_0^+$, then it has passed the exploration GLR test (16), meaning that the algorithm considers that every leveling-aware confusing model has been rejected with satisfying certainty. It means that the GLR exploration test has failed to detect a lack of information, and we account for three different scenarios for that failure, as given by the decomposition of $\mathbf{1}(z_0 \in \mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t), t \in \mathcal{T}_0^+)$ below:

$$ \mathbf{1}\left(\begin{array}{l} z_0 \in \mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t) \\ t \in \mathcal{T}_0^+ \end{array}\right) \le \mathbf{1}\left(\begin{array}{l} z_0 \in \mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t) \\ t \in \mathcal{T}_0^+, \mathcal{E}_t, \mathcal{E}'_t \end{array}\right) + \mathbf{1}\left(\begin{array}{l} z_0 \in \mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t) \\ t \in \mathcal{T}_0^+, (\mathcal{E}'_t)^c \end{array}\right) + \mathbf{1}(\mathcal{E}_t^c). \quad (C.4) $$

where $z_0$ is some fixed pair $z_0 \notin \mathcal{Z}^{**}(M)$. The first term $\mathbf{1}(z_0 \in \mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t), t \in \mathcal{T}_0^+, \mathcal{E}_t, \mathcal{E}'_t)$ accounts for exploitation times where the empirical data is approximately correct on both the skeleton $\mathcal{Z}_t^{\text{skel}}$ and leveled optimal pairs $\mathcal{Z}_{\varepsilon_{\text{lvl}}(t)}^{**}(\hat{M}_t)$; Such cases boil down to the power of the GLR exploration test (16) and the tuning of $\varepsilon_{\text{tst}}(t)$, for a total expected aggregate error of order $\int (\frac{1}{t})^{1+\varepsilon_{\text{tst}}(t)} dt$, see Lemma C.4. The third term $\mathbf{1}(\mathcal{E}_t^c)$ quantifies how likely it is for the empirical data to be wrong on the skeleton. Because visit counts are high on
the skeleton by definition, the aggregate error due to this term is bounded in expectation, see Lemma C.8. The dominant term is the second one, $\mathbf{1}(z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t), t \in \mathcal{T}^+, (\mathcal{E}')_t^c)$, and accounts for the speed at which information is gathered on leveled optimal pairs $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$ during exploitation. This term can be made sub-logarithmic thanks to the co-exploration mechanism of ECoE*. In expectation, the associated expected aggregate error term is shown to be of order $\varepsilon_{\text{lvl}}(T)^{-6}$, see Lemmas C.6 and C.7.

**The co-exploration structure $\mathfrak{Z}_t^+$.** When an exploitation phase begins, it lasts until regeneration or until regeneration is compromised by the discovery of a new transition that provokes a panic time. The possibility that the support of $\hat{M}_t$ is wrong and that components of $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$ may not be closed in $M$ has to be taken into consideration. Indeed, in the early phases of ECoE*, some transitions $(S_t, A_t, S_{t+1})$ have never been observed yet. If they are first observed during an exploitation phase, it is possible that their discovery make ECoE* exit $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$ and compromise the regenerative requirement of exploitation phases. In these regards, we introduce below the notion of **co-exploration structure** and we partition exploitation times $\mathcal{T}^+$ depending on it.

By design, the algorithm splits $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$ into components $\mathcal{Z}_t^1, \dots, \mathcal{Z}_t^{c(t)}$ that are the communicating components of $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$ under the empirically observed model $\hat{M}_t$. The decomposition itself is denoted $\mathfrak{Z}_t^+ := (\mathcal{Z}_t^1, \dots, \mathcal{Z}_t^{c(t)})$ and is called the **co-exploration structure** at time $t$. Given a co-exploration structure $\mathfrak{Z}_0$, we introduce $\mathcal{T}^+(\mathfrak{Z}_0)$ the exploitation times when the exploitation structure is $\mathfrak{Z}_0$ at the associated exploitation time, i.e.,

$$ \mathcal{T}^+(\mathfrak{Z}_0) := \bigcup \{\{t_k, \dots, t_{k+1} - 1\} : k \ge 1, t_k \in \mathcal{T}_0^+ \text{ and } \mathfrak{Z}_{t_k}^+ = \mathfrak{Z}_0\} \quad (\text{C.5}) $$

and further write $\mathcal{T}_0^+(\mathfrak{Z}_0) = \mathcal{T}^+(\mathfrak{Z}_0) \cap \mathcal{T}_0^+$ the associated initial exploitation times. Depending on whether the co-exploration structure $\mathfrak{Z}_0$ is closed in $M$ (i.e., every $\mathcal{Z}_0 \in \mathfrak{Z}_0$ is communicating in $M$) or not (see Definition C.1 below), the analysis is different, see Lemmas C.6 and C.7.

**Definition C.1 (Closed structure).** Given a Markov decision process $M \equiv (\mathcal{Z}, p, \nu)$, a set of pairs $\mathcal{Z}' \subseteq \mathcal{Z}$ is said **closed** in $M$ if $\mathcal{Z}'$ is equal to its unique communicating component (Definition 6), i.e., if the model $M|_{\mathcal{Z}'} \equiv (\mathcal{Z}', p|_{\mathcal{Z}'}, \nu|_{\mathcal{Z}'})$ is well-defined and communicating; A structure $\mathfrak{Z} \equiv (\mathfrak{Z}_1, \dots, \mathfrak{Z}_c)$ is said **closed** in $M$ if every $\mathfrak{Z}_i \subseteq \mathcal{Z}$ is closed in $M$.

### C.2.2 PROOF OF LEMMA C.3: INITIAL EXPLOITATION AND EXPLOITATION TIMES

All throughout the section, we fix $z_0 \notin \mathcal{Z}^{**}(M)$.

**Proof** Let $t_k \in \mathcal{T}_0^+(\mathfrak{Z}_0)$ be an initial exploitation time with co-exploration structure $\mathfrak{Z}_0$ such that $z_0 \in \bigcup \mathfrak{Z}_0 \equiv (\mathcal{Z}_0^1, \dots, \mathcal{Z}_0^m)$ where $\mathcal{Z}_0^i$ is the $i$-th communicating component of $\mathfrak{Z}_0$ in $\hat{M}_{t_k}$. Denote $\mathcal{Z}_0^u$ the component containing $S_{t_k}$. We introduce the reward function

$$ f_{t_k}(s, a) \equiv f(s, a) := \mathbf{1}(s = S_{t_k}) + \mathbf{1}(s \notin \mathcal{S}(\mathcal{Z}_0^u)) $$

that tracks visits to the initial state and states outside of $\mathcal{Z}_0^u$. Let $g^f, b^f$ be the gain and bias functions obtained by iterating the uniform policy $\pi^u$ on $\mathcal{Z}_0^u$, extended to the uniform policy outside of $\mathcal{S}(\mathcal{Z}_0^u)$ for the reward function $f$. Let $\Delta^f(s, a) = g^f(s) + b^f(s) - f(s, a) - p(s, a)b^f$ be the associated gap function.
If $\mathcal{Z}_0^u$ is closed in $M$, then we see that the iterates of $\pi^u$ stating from $S_{t_k}$ remain almost surely on $\mathcal{Z}_0^u$, so $\text{sp}(g^f|S(\mathcal{Z}_0^i)) = 0$; If $\mathcal{Z}_0^u$ is not closed in $M$, then $\mathcal{Z}_0^u$ is either transient or recurrent under $\pi^u$ in $M$, and in either cases $\text{sp}(g^f) = 0$. Overall, we have $\text{sp}(g^f|S(\mathcal{Z}_0^u)) = 0$, that $\alpha_{t_k} := \min(g^f|S(\mathcal{Z}_0^u)) > 0$ and that $\beta_{t_k} := \max\{\text{sp}(b^f), \|\Delta^f\|_{\infty}\} < \infty$. Let $0 < \alpha, \beta < \infty$ be the respective minimum and maximum values that $\alpha_{t_k}, \beta_{t_k}$ can take for all finitely many possible values for $\mathfrak{z}_0, u$ and $S_{t_k}$.

Now, during the phase $\{t_k, \dots, t_{k+1} - 1\}$, note that $f(Z_t) = 1$ holds only for $t = t_k$ by construction of $f$ and of exploitation phases. Therefore,

$$ 
\begin{aligned}
1 &= \sum_{t=t_k}^{t_{k+1}-1} f_{t_k}(Z_t) \\
&\stackrel{(\dagger)}{=} \sum_{t=t_k}^{t_{k+1}-1} \left( g^{f_{t_k}}(S_t) + (e_{S_t} - p(Z_t))b^{f_{t_k}} - \Delta^{f_{t_k}}(Z_t) \right) \\
&\stackrel{(\ddagger)}{\ge} \alpha(t_{k+1} - t_k) - \beta \mathbf{1}(S_{t_{k+1}} \neq S_{t_k}) + \sum_{t=t_k}^{t_{k+1}-1} \left( (e_{S_{t+1}} - p(Z_t))b^{f_{t_k}} - \Delta^{f_{t_k}}(Z_t) \right)
\end{aligned}
$$

where $(\dagger)$ follows by definition of $\Delta^f(Z_t)$; and $(\ddagger)$ follows from a telescopic sum. Note that the right-most term is a martingale, hence its expectation is zero. Indeed, $\mathbf{E}[e_{S_{t+1}}|Z_t] = p(Z_t)$ and by Poisson's equation, $\mathbf{E}[\Delta^f(Z_t)|S_t] = \sum_{a \in \mathcal{A}(S_t)} \pi^u(a|S_t)\Delta^f(S_t, a_t) = 0$.

Summing for $t_k \in \mathcal{T}_0^+$, we obtain

$$ 
\begin{aligned}
\mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1}(z_0 \in \mathcal{Z}_{\text{lvl}(t)}^{**}(\hat{M}_t), t \in \mathcal{T}_0^+) \right] \\
\stackrel{(\dagger)}{=} \mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1}(\mathcal{E}_t^0, t \in \mathcal{T}_0^+) \right] \\
\ge \mathbf{E} \left[ \sum_{k=1}^{\infty} \mathbf{1}(t_k < T, \mathcal{E}_t^0, t_k \in \mathcal{T}_0^+) \left( \alpha(\min(T, t_{k+1}) - t_k) - \beta \mathbf{1}(S_{t_{k+1}} \neq S_{t_k}) \right) \right] \\
\ge \alpha \mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1}(\mathcal{E}_t^0, t \in \mathcal{T}^+) \right] - \beta \mathbf{E} \left[ \sum_{k=1}^{\infty} \mathbf{1}(\mathcal{E}_t^0, t_k \in \mathcal{T}_0^+, S_{t_{k+1}} \neq S_{t_k}) \right] \\
= \alpha \mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1}(\mathcal{E}_t^0, t \in \mathcal{T}^+) \right] - \beta \sum_{\mathfrak{z}_0} \mathbf{E} \left[ \sum_{k=1}^{\infty} \mathbf{1}(\mathcal{E}_t^0, t_k \in \mathcal{T}_0^+(\mathfrak{z}_0), S_{t_{k+1}} \neq S_{t_k}) \right] \\
\stackrel{(\ddagger)}{\ge} \alpha \mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1}(\mathcal{E}_t^0, t \in \mathcal{T}^+) \right] - \beta |S||\mathcal{Z}|
\end{aligned}
$$

where $(\dagger)$ introduces the short-hand $\mathcal{E}_t^0 \equiv (z_0 \in \mathcal{Z}_{\text{lvl}(t)}^{**}(\hat{M}_t))$; and $(\ddagger)$ relies on the observation that the number of exploitation phases killed by a panic is at most $|S||\mathcal{Z}|$, the maximal number of times a transition may be discovered. We conclude accordingly. $\blacksquare$
### C.2.3 WRONG EXPLOITATION WITH CORRECT DATA ON LEVELED OPTIMAL PAIRS

We start by controlling the error term due to exploitation times for which $Z_t \notin \mathcal{Z}^{**}(M)$ while $\mathcal{E}_t$ and $\mathcal{E}'_t$ hold, see (C.3). In other words: The algorithm exploits a non-optimal pair, meaning that the optimal policy is wrongly estimated while the data is correct on the skeleton and on leveled optimal pairs because $\mathcal{E}_t$ and $\mathcal{E}'_t$ hold.

**Lemma C.4.** Let $z_0 \notin \mathcal{Z}^{**}(M)$ and let $\mathcal{E}_t, \mathcal{E}'_t$ be the events as given by (C.3). Then

$$ \mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1}(z_0 \in \mathcal{Z}_{\varepsilon \mathrm{lvl}(t)}^{**}(\hat{M}_t), t \in \mathcal{T}_0^+, \mathcal{E}_t, \mathcal{E}'_t) \right] \le \sum_{t=1}^{T-1} \exp \left( - \left( 1 + \frac{1}{2} \varepsilon_{\mathrm{tst}}(t) \right) \log(t) \right). $$

The idea of the proof is that if the exploration policy is not optimal, then the empirical data $\hat{M}_t(z)$ is significatively incorrect for some $z \in \mathcal{Z}$. Yet, under $\mathcal{E}_t \cap \mathcal{E}'_t$, the data is approximately correct on $\mathcal{Z}_t^{\mathrm{skel}} \cup \mathcal{Z}_{\varepsilon \mathrm{lvl}(t)}^{**}(\hat{M}_t)$; Yet, the algorithm cannot exploits unless the GLR exploration test of (16) has been passed, that is supposed to check the correctness of empirical data outside of $\mathcal{Z}_t^{\mathrm{skel}} \cup \mathcal{Z}_{\varepsilon \mathrm{lvl}(t)}^{**}(\hat{M}_t)$. So, the error term bounded by Lemma C.4 is directly related to the correctness of the exploration test.

**Proof** Introduce $M_t^\dagger$ the model given as follows:

$$ M_t^\dagger(z) := \begin{cases} \hat{M}_t(z) & \text{if } z \in \mathcal{Z}_t^{\mathrm{skel}} \cup \mathcal{Z}_{\varepsilon \mathrm{lvl}}^{**}(\hat{M}_t); \\ M(z) & \text{if } z \notin \mathcal{Z}_t^{\mathrm{skel}} \cup \mathcal{Z}_{\varepsilon \mathrm{lvl}}^{**}(\hat{M}_t). \end{cases} \qquad (C.6) $$

Note that since $\hat{M}_t \ll M$, we have $\hat{M}_t \ll M_t^\dagger$ as well.

(STEP 1) Under the event $\mathcal{E}_t \cap \mathcal{E}'_t \cap (z_0 \in \mathcal{Z}_{\varepsilon \mathrm{lvl}}^{**}(\hat{M}_t))$, the model $M_t^\dagger$ as given by (C.6) satisfies $M_t^\dagger \in \mathrm{Cnf}(\hat{M}_t)$.

**Proof** Under $\mathcal{E}_t \cap \mathcal{E}'_t$ and following Proposition 3, we have $\mathcal{Z}^{**}(M_t^\dagger) \subseteq \mathcal{Z}^{**}(M)$. Now, under the event $(z_0 \in \mathcal{Z}_{\varepsilon \mathrm{lvl}}^{**}(\hat{M}_t))$, there exists a policy $\pi \in \Pi^*([\hat{M}_t]_{\varepsilon \mathrm{lvl}(t)})$ that is (i) unichain in $\hat{M}_t$ (ii) making $z_0$ recurrent in $\hat{M}_t$ such that

$$ g^\pi(\hat{M}_t) \stackrel{(\dagger)}{\ge} g^*([\hat{M}_t]_{\varepsilon \mathrm{lvl}(t)}) - \varepsilon_{\mathrm{lvl}}(t) \stackrel{(\ddagger)}{=} g^*(\hat{M}_t) - \varepsilon_{\mathrm{lvl}}(t) \qquad (C.7) $$

where $(\dagger)$ follows by definition of the leveling transform $[-]_\varepsilon$, see Definition 7; and $(\ddagger)$ follows by Lemma B.1. Under $\mathcal{E}_t \cap \mathcal{E}'_t$, we have $\hat{M}_t(z) \sim M(z)$ for $z \in \mathcal{Z}_t^{\mathrm{skel}} \cup \mathcal{Z}_{\varepsilon \mathrm{lvl}}^{**}(\hat{M}_t)$ and $\hat{M}_t(z) \ll M(z)$ for other pairs, so $\pi$ is unichain and $z_0$ is recurrent under $\pi$ in $M$ as well. Together with $z_0 \notin \mathcal{Z}^{**}(M)$, we deduce that $g^\pi(s; M) \le g^*(s; M) - \Delta^g(M)$ for all $s \in \mathcal{S}$. Now, by design of $\kappa(M)$ in (C.3),

$$ \begin{aligned} g^\pi(s; M_t^\dagger) &\stackrel{(\dagger)}{\le} g^\pi(s; M) + \kappa(M) \|M_t^\dagger - M\|^* \\ &\stackrel{(\ddagger)}{\le} g^{\pi^*}(s; M) - \Delta^g(M) + \kappa(M) \|M_t^\dagger - M\|^* \\ &\stackrel{(\S)}{\le} g^{\pi^*}(s; M_t^\dagger) - \Delta^g(M) + 2\kappa(M) \|M_t^\dagger - M\|^* \end{aligned} \qquad (C.8) $$
for all $s \in S$, where in the above (†) follows by Lemma D.8 and by $\kappa(M) \ge 1 + D^*(M)$; (‡) introduces $\pi^*$ an arbitrary bias optimal policy of $M$ and $\Delta^g(M)$ is the gain-gap (Definition A.4); and (§) invokes Lemma D.8 and $\kappa(M) \ge 1 + D^*(M)$ again. So, if $\hat{\pi} \in \Pi^*(\hat{M}_t)$, then for all $s \in S$, we have

$$ 
\begin{aligned}
g^{\hat{\pi}}(s; M_t^{\dagger}) &\stackrel{(\ddagger)}{=} g^{\hat{\pi}}(s; \hat{M}_t) \\
&\stackrel{(\ddagger)}{\le} g^{\pi}(s; \hat{M}_t) + \varepsilon_{\text{lvl}}(t) \\
&\stackrel{(\ddagger)}{\le} g^{\pi}(s; M_t^{\dagger}) + \varepsilon_{\text{lvl}}(t) \stackrel{(\S)}{=} g^{\pi^*}(s; M_t^{\dagger}) - \Delta^g(M) + 2\kappa(M)\|M_t^{\dagger} - M\|^* + \varepsilon_{\text{lvl}}(t)
\end{aligned}
$$

where (†) follows from $M_t^\dagger = \hat{M}_t$ on $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$; (‡) follows from (C.7); (§) follows from $M_t^\dagger = \hat{M}_t$ on $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$ again; and (§) follows from (C.8). As $\|M_t^\dagger - M\|^* \le \|\hat{M}_t - M\|^*$, we conclude that if $2\kappa(M)\|M_t^\dagger - M\|^* + \varepsilon_{\text{lvl}}(t) < \Delta^g(M)$, then $\hat{\pi} \notin \Pi^*(M_t^\dagger)$.

Hence $M_t^\dagger \in \text{Cnf}(\hat{M}_t)$.

□

(STEP 2) For all $z_0 \notin \mathcal{Z}^{**}(M)$, we have

$$ \mathbf{P}\left(z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t), t \in \mathcal{T}_0^+, \mathcal{E}_t, \mathcal{E}_t'\right) \le \exp\left(-\left(1 + \frac{1}{2}\varepsilon_{\text{tst}}(t)\right)\log(t)\right). \quad (C.9) $$

**Proof** By definition of initial exploitation times, if $t \in \mathcal{T}_0^+$ then the algorithm has passed its exploration test of (16), meaning that for all $M^\dagger \in \text{Cnf}(\hat{M}_t)$ that coincides with $\hat{M}_t$ on $\mathcal{Z}_t^{\text{skel}} \cup \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$, we have

$$ \psi_{N_t}(\hat{M}_t || M^\dagger) := \sum_{z \in \mathcal{Z}} N_t(z) \text{KL}(\hat{M}_t(z) || M^\dagger(z)) \ge (1 + \varepsilon_{\text{tst}}(t)) \log(t). \quad (C.10) $$

Let $M_t^\dagger$ be the model as given by (C.6). On $\mathcal{E}_t \cap \mathcal{E}_t' \cap (t \in \mathcal{T}_0^+) \cap (z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t))$ and by (STEP 1), we have $M_t^\dagger \in \text{Cnf}(\hat{M}_t)$ so (C.10) holds in particular for $M^\dagger \equiv M_t^\dagger$ and

$$ 
\begin{aligned}
(1 + \varepsilon_{\text{tst}}(t)) \log(t) &\stackrel{(\ddagger)}{\le} \psi_{N_t}(\hat{M}_t || M_t^\dagger) \\
&\stackrel{(\ddagger)}{=} \sum_{z \notin \mathcal{Z}_t^{\text{skel}}} N_t(z) \text{KL}(\hat{M}_t(z) || M(z)) \stackrel{(\S)}{=} \psi_{N'_t}(\hat{M}_t || M)
\end{aligned}
\quad (C.11) $$

where (†) holds on $\mathcal{E}_t \cap \mathcal{E}_t' \cap (t \in \mathcal{T}_0^+) \cap (z_0 \notin \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t))$ following (C.10); (‡) follows by construction of $M_t^\dagger$; and (§) introduces $N'_t(z) := \mathbf{1}(z \notin \mathcal{Z}_t^{\text{skel}})N_t(z)$. We conclude the proof with a combinatorial argument invoking Sanov's theorem. For $n \in \mathbb{N}^\mathcal{Z}$, we denote $\hat{M}_{(n)}$ the observed model under the deterministic number of visits $N_t = n$; Note that $\hat{M}_t = \hat{M}_{(N_t)}$ by definition. Let $\mathcal{M}_{(n)}$ the discrete space of Markov decision processes where rewards and kernels at $z \in \mathcal{Z}$ are all the possible empirical distributions that can be obtained after $n(z)$ samples. Further denote $[\log^2(t)] := \{0, \dots, \lfloor \log^2(T) \rfloor\}$. We have

$$ 
\begin{aligned}
\mathbf{E}[\mathbf{1}(z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t), t \in \mathcal{T}_0^+, \mathcal{E}_t, \mathcal{E}_t')] \\
\stackrel{(\ddagger)}{\le} \mathbf{E}[\mathbf{1}(\psi_{N'_t}(\hat{M}_t || M) \ge (1 + \varepsilon_{\text{tst}}(t)) \log(t))]
\end{aligned}
$$
$$
\begin{align*}
& \stackrel{(\ddagger)}{=} \sum_{n \in [\log^2(t)]^Z} \mathbf{E} \left[ \mathbf{1} \left( \begin{array}{l} \psi_n(\hat{M}_t || M) \ge (1 + \varepsilon_{\text{tst}}(t)) \log(t), \\ (\forall z \notin \mathcal{Z}_t^{\text{skel}}, N_t(z) = n(z)), (\forall z \in \mathcal{Z}_t^{\text{skel}}, n(z) = 0) \end{array} \right) \right] \\
&= \sum_{n \in [\log^2(t)]^Z} \sum_{M' \in \mathcal{M}_{(n)}} \mathbf{E} \left[ \mathbf{1}(\psi_n(M' || M) \ge (1 + \varepsilon_{\text{tst}}(t)) \log(t)) \mathbf{1}(\hat{M}_{(n)} = M') \right] \\
&= \sum_{n \in [\log^2(t)]^Z} \sum_{M' \in \mathcal{M}_{(n)}} \mathbf{1}(\psi_n(M' || M) \ge (1 + \varepsilon_{\text{tst}}(t)) \log(t)) \mathbf{P}(\hat{M}_{(n)} = M') \\
& \stackrel{(\S)}{\le} \sum_{n \in [\log^2(t)]^Z} \sum_{M' \in \mathcal{M}_{(n)}} \mathbf{1}(\psi_n(M' || M) \ge (1 + \varepsilon_{\text{tst}}(t)) \log(t)) \exp(-\psi_n(M' || M)) \\
&\le \sum_{n \in [\log^2(t)]^Z} \sum_{M' \in \mathcal{M}_{(n)}} \exp(-(1 + \varepsilon_{\text{tst}}(t)) \log(t)) \\
& \stackrel{(\S)}{\le} (1 + [\log^2(t)])^{|\mathcal{Z}|(3+|\mathcal{S}|)} \left(\frac{1}{t}\right)^{1+\varepsilon_{\text{tst}}(t)} \\
& \stackrel{(\#)}{\le} \exp\left(-\left(1 + \frac{1}{2}\varepsilon_{\text{tst}}(t)\right) \log(t)\right).
\end{align*}
$$

In the above, (†) is obtained by invoking (C.11); (‡) follows by construction of $N'_t$; (§) is a consequence of an all-time Sanov theorem (Lemma C.27); ($) follows from classic combinatorial bounds (Lemma C.28); and (#) is obtained by using $\varepsilon_{\text{tst}}(t) \ge 4|\mathcal{Z}|(3 + |\mathcal{S}|) \log \log(t) \log(t)^{-1}$ (see Assumption 6). □

We conclude the proof of Lemma C.4 by summing (C.9) of (STEP 2) for $t \ge 1$. ■

### C.2.4 UNIFORM EXPLOITATION: FUNDAMENTAL PROPERTY OF CO-EXPLORATION

Before moving on with the control of the dominant in the decomposition (C.4), we establish a fundamental property of the exploitation mechanism of ECoE, that guarantees that all components of a co-exploration structure $\mathfrak{Z}_0$ are explored uniformly often relatively to the number of initial exploitation times with the so-called structure, see Lemma C.5. This result holds whether the structure is closed or not.

**Lemma C.5.** Let $\mathfrak{Z}_0$ be a co-exploration structure. Let $k(i)$ be the $i$-th phase with co-exploration structure $\mathfrak{Z}_0$, i.e., $\mathcal{T}_0^+(\mathfrak{Z}_0) = \{t_{k(1)}, t_{k(2)}, \dots\}$. There exists $\alpha > 0$ such that

$$ \mathbf{P}(\exists z \in \bigcup \mathfrak{Z}_0, N_{t_{k(i)}}(z) < \alpha\sqrt{i}) = o(i^{-2}) \quad \text{as } i \to \infty. \qquad (C.12) $$

**Proof** The co-exploration structure is decomposed into its communicating components (in $\hat{M}_t$) as $\mathfrak{Z}_0 \equiv (\mathcal{Z}_0^1, \dots, \mathcal{Z}_0^c)$. Remark that $\mathcal{T}_0^+(\mathfrak{Z}_0) = \{t_{k(i)} : i \ge 1\}$ and that $\mathcal{T}^+(\mathfrak{Z}_0) = \bigcup_{i=1}^\infty \{t_{k(i)}, \dots, t_{k(i)+1}-1\}$. Given a component $\mathcal{Z}_0^u$ of $\mathfrak{Z}_0$, we write $\mathcal{I}^u := \{i : S_{t_{k(i)}} \in \mathcal{S}(\mathcal{Z}_0^u)\}$ the indices of initial exploitation times starting in the component $u = 1, \dots, c$.

(STEP 1) There is $\alpha > 0$ such that for all component $u \in \{1, \dots, m\}$ and $z_u \in \mathcal{Z}_0^u$, we have

$$ \mathbf{P}(N_{t_{k(i)+1}}(z_u) < \alpha\ell \text{ and } \ell \le |\mathcal{I}^u \cap \{1, \dots, i\}|) = o(\ell^{-2}) \quad \text{as } \ell \to \infty \qquad (C.13) $$
**Proof** The proof shares many similarities with Lemma C.3.

Fix a component $u \in \{1, \dots, c\}$ and $z_u \in \mathcal{Z}_0^u$. Introduce the reward function $f(s, a) := 1((s, a) = z_u) + 1(s \notin \mathcal{S}(\mathcal{Z}_0^u))$. Let $g^f, b^f$ be the gain and bias functions for the reward function $f$ obtained by iterating the uniform policy on $\mathcal{Z}_0^u$, extended to the uniform policy outside of $\mathcal{S}(\mathcal{Z}_0^u)$. Let $\Delta^f(s, a) = g^f(s) + b^f(s) - f(s, a) - p(s, a)b^f$ be the associated gap function. Note that $\text{sp}(g^f) = 0$ regardless of whether $\mathcal{Z}_0^u$ is closed (Definition C.1) or not. Denote $\alpha := \min(g^f) > 0$ and $\beta := \max\{\text{sp}(b^f), \|\Delta^f\|_\infty\} < \infty$. Denoting $[i] := \{1, \dots, i\}$, we have

$$
\begin{align*}
& N_{t_{k(i)+1}}(z_u) \\
& \geq \sum_{j \in \mathcal{I}^u \cap [i]} \sum_{t=t_{k(j)}}^{t_{k(j)+1}-1} f(Z_t) \\
& \stackrel{(\dagger)}{=} \sum_{j \in \mathcal{I}^u \cap [i]} \sum_{t=t_{k(j)}}^{t_{k(j)+1}-1} \left( g^f(S_t) + (e_{S_t} - p(Z_t))b^f - \Delta^f(Z_t) \right) \\
& \stackrel{(\ddagger)}{\geq} \alpha \left( \sum_{j \in \mathcal{I}^u \cap [i]} (t_{k(j)+1} - t_{k(j)}) \right) - \beta + \sum_{j \in \mathcal{I}^u \cap [i]} \sum_{t=t_{k(j)}}^{t_{k(j)+1}-1} \left( (e_{S_{t+1}} - p(Z_t))b^f - \Delta^f(Z_t) \right) \\
& \stackrel{(\S)}{\geq} \alpha T_i^u - 2\beta \left( 1 + \sqrt{T_i^u \log\left(\frac{1+T_i^u}{\delta}\right)} \right)
\end{align*}
$$

where $(\dagger)$ follows by $g^f(s) + b^f(s) = f(s, a) + p(s, a)b^f + \Delta^f(s, a)$; $(\ddagger)$ uses that by design of panic times, at most one episode $k(j)$ isn't regenerative, i.e., is such that $S_{t_{k(j)}} \neq S_{t_{k(j)+1}}$; and $(\S)$ bounds the RHS martingale with a time-uniform Azuma-Hoeffding inequality (Lemma C.25) with probability $1 - \delta$, and $T_i^u$ is a short-hand for $\sum_{j \in \mathcal{I}^u \cap [i]} (t_{k(j)+1} - t_{k(j)})$. Remark that

$$
\beta \sqrt{T_i^u \log \left( \frac{1+T_i^u}{\delta} \right)} < \frac{1}{4} \alpha T_i^u \iff \delta > \exp \left( -\frac{\alpha \sqrt{T_i^u}}{4\beta} + \log(1+T_i^u) \right) \stackrel{(\dagger)}{=} o\left( |\mathcal{I}^u \cap [i]|^{-2} \right)
$$

where $(\dagger)$ holds after $T_i^u \ge |\mathcal{I}^u \cap [i]|$. We conclude accordingly. $\square$

(STEP 2) There exists a constant $\alpha > 0$ such that

$$
\forall i \ge 1, \forall z \in \bigcup \mathfrak{Z}_0, \quad \mathbf{P}(N_{t_{k(i)}} < \alpha\sqrt{i}) = o(i^{-2}). \qquad (C.14)
$$

**Proof** Since $\mathfrak{Z}_0$ has $c$ components, the more visited component $u \in \{1, \dots, c\}$ is such that $|\mathcal{I}^u \cap [i]| \ge \lceil \frac{i}{c} \rceil$. In particular and following from the square trick (ST), for some $j < i$, the component $u$ has been chosen to start an exploitation phase, i.e., there exists $j \in \{1, \dots, i-1\}$ such that

$$
\min\{N_{t_{k(j)}}(z) : z \in \mathcal{Z}_0^u\} \le \left(\min\{N_{t_{k(j)}}(z) : z \in \bigcup \mathfrak{Z}_0\}\right)^2 \quad (C.15)
$$

and such that $|\mathcal{I}^u \cap [j]| \ge \lceil \frac{i}{c} \rceil - 1$. Meanwhile, by combining $|\mathcal{I}^u \cap [j]| \ge \lceil \frac{i}{c} \rceil - 1 \ge \frac{i-c}{c}$ with (C.13) from (STEP 1), we readily get

$$
\mathbf{P}\left(\log \min\{N_{t_{k(j)+1}}(z) : z \in \mathcal{Z}_0^u\} \ge \log\left(\alpha \cdot \frac{i-m}{m}\right)\right) = 1 - o(i^{-2}). \quad (C.16)
$$
Because visit counts are monotone with respect to time, combining (C.15) and (C.16), we obtain that with probability $1 - o(i^{-2})$, we have

$$ \min\{N_{t_{k(i)}}(z) : z \in \bigcup \mathfrak{Z}_0\} \geq \min\{N_{t_{k(j)+1}}(z) : z \in \bigcup \mathfrak{Z}_0\} \\ \geq \exp\left(\frac{1}{2} \log\left(\alpha \cdot \frac{i-m}{m}\right)\right) = \Omega(\sqrt{i}). $$

This proves the claim.

<figure><img src="image_16.png" /></figure>

This concludes the proof of Lemma C.5.

<figure><img src="image_17.png" /></figure>

### C.2.5 WRONG EXPLOITATION WITH CORRECT EMPIRICAL KERNEL SUPPORTS

We continue with the dominant term of wrong exploitation, corresponding to exploitation times with $z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$, wrong data on leveled optimal pairs $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$ yet $t$ an initial exploitation time with closed co-exploration structure. Because the co-exploration mechanism guarantees that all components of $\mathfrak{Z}_0$ are explored nearly uniformly fast (up to a square root), the empirical data on $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$ becomes uniformly approximately correct quickly. Therefore, the amount of such initial exploitation times is determined by the required precision of the empirical data on $\mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t)$ in $\mathcal{E}_t'$, which is of order $\varepsilon_{\text{lvl}}(t)$.

We end up with a bound of order $\varepsilon_{\text{lvl}}(T)^{-6}$, see Lemma C.6 thereafter.

**Lemma C.6.** Let $z_0 \notin \mathcal{Z}^{**}(M)$. Let $\mathcal{E}_t, \mathcal{E}_t'$ be the good events as given by (C.3). For all closed co-exploration structure $\mathfrak{Z}_0$, we have

$$ \mathbf{E}\left[\sum_{t=1}^{T-1} 1\left(\begin{array}{l} z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}(t)}^{**}(\hat{M}_t), \\ t \in \mathcal{T}_0^+(\mathfrak{Z}_0), (\mathcal{E}_t')^c \end{array}\right)\right] = \mathbf{O}\left(\frac{1}{\varepsilon_{\text{lvl}}(T)^6}\right). $$

**Proof** Fix $\mathfrak{Z}_0 \equiv (\mathcal{Z}_0^1, \dots, \mathcal{Z}_0^c)$ a closed co-exploration structure. Recall that $\mathcal{T}_0^+(\mathfrak{Z}_0) := \mathcal{T}^+(\mathfrak{Z}_0) \cap \mathcal{T}_0^+$ denotes the initial exploitation times with co-exploration structure $\mathfrak{Z}_0$. By definition, see (C.5), $\mathcal{T}^+(\mathfrak{Z}_0)$ is a union of phases $\{t_k, \dots, t_{k+1} - 1\}$ and we denote $k(i)$ the $i$-th phase for which $t_{k(i)} \in \mathcal{T}^+(\mathfrak{Z}_0)$. We have

$$ \mathcal{T}_0^+(\mathfrak{Z}_0) = \{t_{k(i)} : i \geq 1\} \quad \text{and} \quad \mathcal{T}^+(\mathfrak{Z}_0) = \bigcup_{i=1}^{\infty} \{t_{k(i)}, \dots, t_{k(i)+1} - 1\}. $$

Given a component $\mathcal{Z}_0^u$ of $\mathfrak{Z}_0$, we write $\mathcal{I}^u := \{i : S_{t_{k(i)}} \in \mathcal{S}(\mathcal{Z}_0^u)\}$ the indices of initial exploitation times starting in the component $u = 1, \dots, c$.

(STEP 1) There exists a constant $\alpha > 0$ such that, as $T \to \infty$, we have

$$ \mathbf{E}\left[\sum_{t=1}^{T-1} 1\left(\begin{array}{l} t \in \mathcal{T}_0^+(\mathfrak{Z}_0), \\ (\mathcal{E}_t')^c \end{array}\right)\right] \leq \mathbf{E}\left[\sum_{j=1}^{\infty} \sum_{z \in \bigcup \mathfrak{Z}_0} 1\left(\begin{array}{l} C(M)\|\hat{M}_{t_{k(j)}}(z) - M(z)\|^* \geq \varepsilon_{\text{lvl}}(T), \\ N_{t_{k(j)}}(z) > \alpha\sqrt{j} \end{array}\right)\right] + \frac{1}{\alpha}. $$

**Proof** This follows from the following direction computation:

$$ \mathbf{E}\left[\sum_{t=1}^{T-1} 1(t \in \mathcal{T}_0^+(\mathfrak{Z}_0), (\mathcal{E}_t')^c)\right] $$
$$
\begin{align*}
&= \mathbf{E} \left[ \sum_{j=1}^{\infty} \mathbf{1}(t_{k(j)} < T, (\mathcal{E}'_{t_{k(j)}})^c) \right] \\
&\le \mathbf{E} \left[ \sum_{j=1}^{\infty} \mathbf{1} \left( \begin{array}{l} t_{k(j)} < T, (\mathcal{E}'_{t_{k(j)}})^c, \\ (\forall z \in \bigcup \mathfrak{Z}_0, N_{t_{k(j)}}(z) \ge \alpha \sqrt{j}) \end{array} \right) \right] + \mathbf{E} \left[ \sum_{j=1}^{\infty} \mathbf{1}(\exists z \in \bigcup \mathfrak{Z}_0, N_{t_{k(j)}}(z) < \alpha \sqrt{j}) \right] \\
&\stackrel{(\dagger)}{=} \mathbf{E} \left[ \sum_{j=1}^{\infty} \mathbf{1} \left( t_{k(j)} < T, \begin{array}{l} (\exists z \in \bigcup \mathfrak{Z}_0, \kappa(M) \|\hat{M}_{t_{k(j)}}(z) - M(z)\|^* \ge \varepsilon_{\text{lvl}}(t_{k(j)})) \\ (\forall z \in \bigcup \mathfrak{Z}_0, N_{t_{k(j)}}(z) \ge \alpha \sqrt{j}) \end{array} \right) \right] + \sum_{j=1}^{\infty} o\left(\frac{1}{j^2}\right) \\
&\stackrel{(\ddagger)}{\le} \mathbf{E} \left[ \sum_{j=1}^{\infty} \mathbf{1} \left( t_{k(j)} < T, \begin{array}{l} (\exists z \in \bigcup \mathfrak{Z}_0, \kappa(M) \|\hat{M}_{t_{k(j)}}(z) - M(z)\|^* \ge \varepsilon_{\text{lvl}}(T)) \\ (\forall z \in \bigcup \mathfrak{Z}_0, N_{t_{k(j)}}(z) \ge \alpha \sqrt{j}) \end{array} \right) \right] + O(1) \\
&\le \mathbf{E} \left[ \sum_{j=1}^{\infty} \sum_{z \in \bigcup \mathfrak{Z}_0} \mathbf{1} \left( \begin{array}{l} \kappa(M) \|\hat{M}_{t_{k(j)}}(z) - M(z)\|^* \ge \varepsilon_{\text{lvl}}(T) \\ N_{t_{k(j)}}(z) > \alpha \sqrt{j} \end{array} \right) \right] + O(1)
\end{align*}
$$

where (†) unfolds the definition of $(\mathcal{E}'_{\tau_j})^c$ and invokes Lemma C.5; and (‡) follows by monotonicity of $\varepsilon_{\text{lvl}}$. This proves the claim. □

Continuing from (STEP 1), we prove Lemma C.6. We write

$$
\begin{align*}
& \mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1}(t \in \mathcal{T}_0^+(\mathfrak{Z}_0), (\mathcal{E}_t')^c) \right] \\
&\stackrel{(\dagger)}{\le} \mathbf{E} \left[ \sum_{j=1}^{\infty} \sum_{z \in \bigcup \mathfrak{Z}_0} \mathbf{1} \left( \begin{array}{l} C(M) \|\hat{M}_{t_{k(j)}}(z) - M(z)\|^* \ge \varepsilon_{\text{lvl}}(T), \\ N_{t_{k(j)}}(z) > \alpha \sqrt{j} \end{array} \right) \right] + O(1) \\
&\stackrel{(\ddagger)}{=} \sum_{z \in \bigcup \mathfrak{Z}_0} \sum_{j=1}^{\infty} \mathbf{P} \left( \begin{array}{l} C(M) \|\hat{M}_{t_{k(j)}}(z) - M(z)\|^* \ge \varepsilon_{\text{lvl}}(T), \\ N_{t_{k(j)}}(z) > \alpha \sqrt{j} \end{array} \right) + O(1) \\
&\stackrel{(\S)}{\le} \sum_{z \in \bigcup \mathfrak{Z}_0} \sum_{j=1}^{\infty} \min \left\{ 1, \exp \left( - \frac{2\alpha\varepsilon_{\text{lvl}}(T)^2 \sqrt{j}}{\kappa(M)^2} + \frac{1}{2} \log(1 + \alpha\sqrt{j}) + (|S| + 1) \log(2) \right) \right\} + O(1)
\end{align*}
$$

where (†) follows from (STEP 1); (‡) converts $\|-\|^*$ to $\|-\|$ using Lemma C.24; and (§) follows by Corollary C.23. Setting $\lambda = 2\varepsilon_{\text{lvl}}(T)^2\kappa(M)^{-2}$, we have to upper-bound a term of the form

$$
B := \sum_{n=1}^{\infty} \min\{1, (1 + \alpha\sqrt{n}) \exp(-\lambda\sqrt{n})\}
$$

We have

$$
\begin{align*}
B &\le \frac{2}{\alpha} \sum_{n=1}^{\infty} \min\{\sqrt{n} \exp(-\lambda\sqrt{n}), 1\} \\
  &\le \frac{2}{\alpha} \left( \left\lfloor \frac{1}{\lambda^2} \right\rfloor + \sum_{n>\lfloor\lambda^{-2}\rfloor} \sqrt{n} \exp(-\lambda\sqrt{n}) \right) \\
  &\stackrel{(\ddagger)}{\le} \frac{2}{\alpha} \left( \left\lfloor \frac{1}{\lambda^2} \right\rfloor + \int_0^\infty \sqrt{x} \exp(-\lambda\sqrt{x}) dx \right) = \frac{2}{\alpha} \left( \left\lfloor \frac{1}{\lambda^2} \right\rfloor + \frac{4}{\lambda^3} \right) = O\left( \frac{1}{\varepsilon_{\text{lvl}}(T)^6} \right)
\end{align*}
$$
where (†) follows by a sum-integral comparison, using that $f(x) := \sqrt{x} \exp(-\lambda\sqrt{x})$ is decreasing on $[\lambda^{-2}, \infty)$. This concludes the proof. ■

### C.2.6 WRONG EXPLOITATION WITH WRONG EMPIRICAL KERNEL SUPPORTS

The proof of Lemma C.6 can be generalized to non-closed structures. For non-closed structures however, we can provide a better bound than $\varepsilon_{\text{lvl}}(T)^{-6}$ and show that such structures are all rejected in finite time. The idea is simple: If $\mathfrak{Z}_0$ is not closed in $M$, it has a non-closed component $\mathfrak{Z}_0$ and every time the algorithm exploits this component, it has positive probability to escape from it and to panic accordingly—and thanks to the co-exploration mechanism, (Lemma C.5), this component is visited about as many times as the algorithm exploits with co-exploration structure $\mathfrak{Z}_0$. See Lemma C.7 below.

**Lemma C.7.** Let $z_0 \notin \mathfrak{Z}^{**}(M)$. Let $\mathcal{E}_t, \mathcal{E}'_t$ be the good events as given by (C.3). For all non-closed co-exploration structure $\mathfrak{Z}_0$, we have

$$ \mathbf{E} \left[ \sum_{t=1}^{\infty} \mathbf{1} \left( \begin{array}{l} z_0 \in \mathfrak{Z}_{\text{lvl}(t)}^{**}(\hat{M}_t), \\ t \in \mathcal{T}_0^+(\mathfrak{Z}_0), (\mathcal{E}'_t)^c \end{array} \right) \right] < \infty. $$

**Proof** Fix $\mathfrak{Z}_0 = (\mathfrak{Z}_0^1, \dots, \mathfrak{Z}_0^c)$ a non closed exploration structure, meaning that there is $\mathfrak{Z}_0^u \in \mathfrak{Z}_0$ together with some $z \in \mathfrak{Z}_0^u$ such that $\text{supp}(p(z)) \not\subseteq \mathcal{S}(\mathfrak{Z}_0^u)$, i.e., playing $z \in \mathfrak{Z}_0^u$ makes one exit the states spawned by $\mathfrak{Z}_0^u$ with positive probability. Let $\mathcal{T}_0^+(\mathfrak{Z}_0) := \mathcal{T}^+(\mathfrak{Z}_0) \cap \mathcal{T}_0^+$ be the initial exploitation times with co-exploration structure $\mathfrak{Z}_0$. By definition, see (C.5), $\mathcal{T}^+(\mathfrak{Z}_0)$ is a union of phases $\{t_k, \dots, t_{k+1} - 1\}$ and we denote $k(i)$ the $i$-th phase for which $t_{k(i)} \in \mathcal{T}^+(\mathfrak{Z}_0)$. We have

$$ \mathcal{T}_0^+(\mathfrak{Z}_0) = \{t_{k(i)} : i \ge 1\} \quad \text{and} \quad \mathcal{T}^+(\mathfrak{Z}_0) = \bigcup_{i=1}^{\infty} \{t_{k(i)}, \dots, t_{k(i)+1} - 1\}. $$

Given a component $\mathfrak{Z}_0^u$ of $\mathfrak{Z}_0$, we write $\mathcal{I}^u := \{i : S_{t_{k(i)}} \in \mathcal{S}(\mathfrak{Z}_0^u)\}$ the indices of initial exploitation times starting in the component $u = 1, \dots, c$.

(STEP 1) Let $\mathfrak{Z}_0^u \in \mathfrak{Z}_0$ be a component that is not closed. There exists $C > 0$ such that, for all $x \ge 0$, we have

$$ \mathbf{P} \left( \sum_{i \in \mathcal{I}^u} (t_{k(i)+1} - t_{k(i)}) \ge x \right) \le \exp \left( -Cx + \frac{1}{C} \right) \quad (C.17) $$

**Proof** Let $T_i^u := \sum_{j \in \mathcal{I}^u \cap [i]} (t_{k(j)+1} - t_{k(j)})$ the time spent on component $\mathfrak{Z}_0^u$. Consider the reward function $f(s, a) := \mathbf{1}(s \notin \mathcal{S}(\mathfrak{Z}_0^u))$ and let $g^f, b^f$ be the gain and bias functions for the reward function $f$ obtained by iterating the uniform policy $\pi_u$ on $\mathfrak{Z}_0^u$ extended to the uniform policy on $\mathcal{A}$ outside of $\mathcal{S}(\mathfrak{Z}_0^u)$. As usual, observe that $\text{sp}(g^f) = 0$ and that $0 < \alpha := \min(g^f), \beta := \text{sp}(b^f) < \infty$. By design of panic times, we cannot have $f(Z_t) = 1$ for $t = t_{k(i)}, \dots, t_{k(i)+1} - 1$ if $i \in \mathcal{I}^u$. We deduce that

$$ 0 = \sum_{j \in \mathcal{I}^u \cap [i]} \sum_{t=t_{k(j)}}^{t_{k(j)+1}-1} f(Z_t) $$
$$ \begin{align*} & \stackrel{(\dagger)}{=} \sum_{j \in \mathcal{I}^u \cap [i]} \sum_{t=t_{k(j)}}^{t_{k(j)+1}-1} (g^f(S_t) + (e_{S_t} - p^{\pi_u}(S_t))b^f) \\ & \stackrel{(\ddagger)}{\ge} \alpha T_i^u - \beta + \sum_{j \in \mathcal{I}^u \cap [i]} \sum_{t=t_{k(j)}}^{t_{k(j)+1}-1} (e_{S_{t+1}} - p^{\pi_u}(S_t))b^f \stackrel{(\S)}{\ge} \alpha T_i^u - \beta \left(1 + \sqrt{T_i^u \log\left(\frac{1+T_i^u}{\delta}\right)}\right) \end{align*} $$

where (†) follows by the Poisson equation $g^f(s) + b^f(s) = f^{\pi_u}(s) + p^{\pi_u}(s)b^f$; (‡) uses that by design of panic times, at most one episodes $k(j)$ isn't regenerative; and (§) bounds the RHS martingale with a time-uniform Azuma-Hoeffding's inequality (Lemma C.25) and holds with probability $1 - \delta$. By letting $i$ go to infinity, we see that $T^u := \sum_{i \in \mathcal{I}^u} (t_{k(i)+1} - t_{k(i)})$ satisfies

$$ \forall \delta \ge 0, \quad \mathbf{P}\left(T^u \le \frac{\alpha}{\beta}\left(1 + \sqrt{T^u \log\left(\frac{1+T^u}{\delta}\right)}\right) \le \delta\right) \le \delta $$

and we conclude with straight-forward algebra that $T^u$ has sub-exponential tails. □

We now prove Lemma C.7. Let $u \in \{1, \dots, c\}$ be such that $\mathcal{Z}_0^u$ is not closed. We have

$$ \begin{align*} \mathbf{E}\left[\sum_{t=1}^{\infty} \mathbf{1}(t \in \mathcal{T}_0^+(\mathfrak{Z}_0))\right] &= \mathbf{E}\left[\sum_{j=1}^{\infty} \mathbf{1}(t_{k(j)} < \infty)\right] \\ &\stackrel{(\dagger)}{=} \mathbf{E}\left[\sum_{j=1}^{\infty} \mathbf{1}(t_{k(j)} < \infty, (\forall z \in \cup \mathfrak{Z}_0, N_{t_{k(j)}}(z) \ge \alpha\sqrt{j}))\right] + \mathcal{O}(1) \\ &\stackrel{(\ddagger)}{\le} \mathbf{E}\left[\sum_{j=1}^{\infty} \mathbf{1}(T^u \ge \alpha\sqrt{j})\right] + \mathcal{O}(1) \\ &\stackrel{(\S)}{\le} \sum_{j=1}^{\infty} \exp\left(-\frac{\alpha}{C}\sqrt{j} + \frac{1}{C}\right) + \mathcal{O}(1) < \infty \end{align*} $$

where (†) follows by Lemma C.5; (‡) introduces $T^u := \sum_{i \in \mathcal{I}^u} (t_{k(i)} - t_{k(i)})$; and (§) follows from (STEP 1); This concludes the proof. ■

### C.2.7 CORRECTNESS OF EMPIRICAL DATA ON THE SKELETON

In this paragraph, we bound the last term in (C.4), accounting for wrong empirical data on the skeleton. The idea of the argument is that since a pair belongs to the skeleton if, and only if $N_t(z) \ge \log^2(t)$, the associated empirical data concentrates very fast.

**Lemma C.8.** Let $\mathcal{E}_t$ be the good event as given by (C.3). We have

$$ \mathbf{E}\left[\sum_{t=1}^{\infty} \mathbf{1}(\mathcal{E}_t^c)\right] < \infty. $$

**Proof** Note that by Lemma C.24, $\|M'(z) - M(z)\|^* = \|M'(z) - M(z)\|$ if $\|M'(z) - M(z)\| < \min(M)$. Therefore, the event $\mathcal{E}_t$ holds if for all $z \in \mathcal{Z}_t^{\text{skel}}$, we have

$$ \|\hat{M}_t(z) - M(z)\| < \frac{\varepsilon_{\text{lvl}}(t)}{\kappa(M)} \quad \text{and} \quad \varepsilon_{\text{lvl}}(t) < \min\left\{\frac{\Delta^g(M)}{3}, \kappa(M)\min(M)\right\}. \quad (C.18) $$
By Assumption 6 (A0), we have $\varepsilon_{\text{lvl}}(t) \to 0$ as $t \to \infty$, so the second requirement of (C.18) is satisfied as soon as $t$ is large enough, say $t \ge \kappa_{\bar{\varepsilon}}$ for some $\kappa_{\bar{\varepsilon}} \in \mathbb{N}$. So,

$$
\begin{align*}
\mathbf{E}\left[\sum_{t=1}^{\infty} \mathbf{1}(\mathcal{E}_t^c)\right] &\stackrel{(\dagger)}{\le} \kappa_{\bar{\varepsilon}} + \sum_{t=\kappa_{\bar{\varepsilon}}}^{\infty} \mathbf{P}\left(\exists z \in \mathcal{Z}_t^{\text{skel}}, \|\hat{M}_t(z) - M(z)\| \le \frac{\varepsilon_{\text{lvl}}(t)}{\kappa(M)}\right) \\
&\stackrel{(\ddagger)}{=} \kappa_{\bar{\varepsilon}} + \sum_{t=\kappa_{\bar{\varepsilon}}}^{\infty} \mathbf{P}\left(\exists z \in \mathcal{Z}, \|\hat{M}_t(z) - M(z)\| \le \frac{\varepsilon_{\text{lvl}}(t)}{\kappa(M)} \text{ and } N_t(z) \ge \log^2(t)\right) \\
&\stackrel{(\S)}{\le} \kappa_{\bar{\varepsilon}} + |\mathcal{Z}| \sum_{t=\kappa_{\bar{\varepsilon}}}^{\infty} \exp\left(-\frac{2\log^2(t)\varepsilon_{\text{lvl}}(t)^2}{\kappa(M)^2} + \frac{1}{2}\log(1 + \log^2(t)) + \log(2^{|\mathcal{Z}|+1})\right) \\
&\stackrel{(\S)}{\le} \kappa_{\bar{\varepsilon}} + |\mathcal{Z}| \sum_{t=\kappa_{\bar{\varepsilon}}}^{\infty} \exp\left(-\log^{\frac{3}{2}}(t) + o(\log^{\frac{3}{2}}(t))\right) = \mathbf{O}(1)
\end{align*}
$$

where $(\dagger)$ follows by definition of $\kappa_{\bar{\varepsilon}}$; $(\ddagger)$ follows by definition of the skeleton $\mathcal{Z}_t^{\text{skel}} := \{z \in \mathcal{Z} : N_t(z) \ge \log^2(t)\}$; $(\S)$ follows from concentration results (Corollary C.23); and $(\S)$ follows from Assumption 6 (A2), that guarantees that $2\log^2(t)\varepsilon_{\text{lvl}}(t)^2\kappa(M)^{-2} \ge \log^{\frac{3}{2}}(t)$ for $t$ large enough. This concludes the proof. ■

### C.2.8 PROOF OF LEMMA C.2: PUTTING EVERYTHING TOGETHER

We finally prove Lemma C.2. We have

$$
\begin{align*}
& \mathbf{E}\left[\sum_{t=1}^{T-1} \mathbf{1}(Z_t = z_0, t \in \mathcal{T}^+)\right] \\
&\stackrel{(\dagger)}{=} \mathbf{O}\left(\mathbf{E}\left[\sum_{t=1}^{T-1} \mathbf{1}\left(\begin{array}{l} z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t) \\ t \in \mathcal{T}_0^+ \end{array}\right)\right]\right) \\
&\stackrel{(\ddagger)}{\le} \mathbf{O}\left(\mathbf{E}\left[\sum_{t=1}^{T-1} \mathbf{1}\left(\begin{array}{l} z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t) \\ t \in \mathcal{T}_0^+, \mathcal{E}_t, \mathcal{E}_t' \end{array}\right)\right] + \mathbf{E}\left[\sum_{t=1}^{T-1} \mathbf{1}\left(\begin{array}{l} z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t) \\ t \in \mathcal{T}_0^+, (\mathcal{E}_t')^c \end{array}\right)\right] + \mathbf{E}\left[\sum_{t=1}^{T-1} \mathbf{1}(\mathcal{E}_t^c)\right]\right) \\
&\stackrel{(\S)}{=} \mathbf{O}\left(\sum_{t=1}^{T-1} \left(\frac{1}{t}\right)^{1+\frac{1}{2}\varepsilon_{\text{tst}}(t)}\right) + \mathbf{O}\left(\sum_{\mathfrak{Z}_0} \mathbf{E}\left[\sum_{t=1}^{T-1} \mathbf{1}\left(\begin{array}{l} z_0 \in \mathcal{Z}_{\varepsilon \text{lvl}}^{**}(\hat{M}_t) \\ t \in \mathcal{T}_0^+(\mathfrak{Z}_0), (\mathcal{E}_t')^c \end{array}\right)\right]\right) + \mathbf{O}(1) \\
&\stackrel{(\S)}{=} \mathbf{O}\left(\sum_{t=1}^{T-1} \left(\frac{1}{t}\right)^{1+\frac{1}{2}\varepsilon_{\text{tst}}(t)}\right) + \mathbf{O}\left(\frac{1}{\varepsilon_{\text{lvl}}(T)^6}\right) + \mathbf{O}(1)
\end{align*}
$$

where $(\dagger)$ follows from Lemma C.3; $(\ddagger)$ invokes the decomposition from (C.4); $(\S)$ bounds the first term using Lemma C.4, the second is decomposed along the finitely many possible co-exploration structures $\mathfrak{Z}_0$ and the third using Lemma C.8; and $(\S)$ bounds the last term using Lemma C.6 and Lemma C.7 depending on whether $\mathfrak{Z}_0$ is closed or not. ■

## C.3 Amount of exploration

Let $\mu^*$ be the central optimal exploration probability measure of $M$ (Definition B.3), that is the limit point of optimal $\bar{\varepsilon}$-regularized exploration measures $\mu_{\bar{\varepsilon}}^*$ of $M$ as $\bar{\varepsilon} \to 0$ in the sense of Proposition B.16. Recall that $C(\mu^*, M)$ denotes the information value of $\mu^*$ in $M$
(Definition B.1). The whole section is dedicated to the proof Lemma C.9 below, that bounds the number of times a pair is being pulled during exploration.

**Lemma C.9.** Let $z \in \mathcal{Z}$ be an arbitrary state-action pair. As $T \to \infty$, we have

$$ \mathbf{E}\left[\sum_{t=1}^{T-1} 1(Z_t = z, t \in \mathcal{T}^-)\right] \le \frac{\mu^*(z) \log(T)}{C(\mu^*, M)} + o(\log(T)). \quad (C.19) $$

### C.3.1 IDEA OF THE PROOF

In Figure 6, we provide a high level representation of how exploration is decomposed and analyzed. Overall, the set of exploration times $\{t \in \mathcal{T}^- : t \le T\}$ is split into five periods: The “burn-in” period, the dominant “near-optimal exploration” period, the “co-exploration travels” period, a “first order failure” period and a “second order failure” period.

<figure><img src="image_18.png" /><figcaption>Figure 6: Global overview of the different exploration periods as $|\mathcal{T}^-|$ increases.</figcaption></figure>

We fix $\varepsilon_0 > 0$ a precision parameter. Then, we begin by discarding what happens prior to time $\approx \varepsilon_0 \log(T)$, during the BURN-IN period. Past the burn-in period, we show that the empirical data is quite likely to concentrate well-enough so that the algorithm approximates the exploration measure and information values correctly. This phenomenon is called the **trigger effect** (Appendix C.3.4). It is made possible by the uniform exploration guarantees of ECoE* allowed by the $\varepsilon_{\text{unif}}$-regularization of its exploration policies, that makes sure that all pairs are covered uniformly fast during exploration (Appendix C.3.3). Following the burn-in period, ECoE* enters the NEAR OPTIMAL EXPLORATION period during which it explores near-optimally (Appendix C.3.5). During this period and because of the trigger effect, ECoE* further estimates the information values well-enough so that it does not overshot the duration of exploration. After about $C(\mu^*, M)^{-1} \log(T)$ exploration times, GLR exploration tests (16) do not provoke exploration phases anymore and ECoE* enters the CO-EXPLORATION TRAVELS period. During this period, exploration phases can only be triggered by the co-exploration rule, for a total number of exploration phases that is negligible in front of $\log(T)$ (Appendix C.3.9). Combining everything so far, we deduce that the number of exploration phases is quite likely to remain below $C(\mu^*, M)^{-1} \log(T)$ (Appendices C.3.6 and C.3.9).

If $|\mathcal{T}^-|$ exceeds $C(\mu^*, M)^{-1} \log(T)$ significatively, it essentially means that the trigger effect failed to trigger after the burn-in period. This is the FIRST ORDER FAILURE period, that ECoE* only enters with probability $o(\exp(-\sqrt{\log(T)}))$. We show that at horizon $O(\log^3(T))$ and thanks to uniform exploration again, all pairs enter the skeleton $\{z \in \mathcal{Z} : N_t(z) \ge \log^2(t)\}$
and ECoE* naturally stops to explore by design. Because $log^3(T) \exp(-\sqrt{\log(T)}) \to 0$ when $T \to \infty$, the number of exploration times induced by the first order failure period is negligible in expectation (Appendix C.3.7). This is the **skeleton barrier**. Beyond that barrier, the algorithm only continues to explore if pairs failed to enter the skeleton. This is the **SEC-OND ORDER FAILURE** period, that has so little probability to happen that its is completely negligible in expectation.

Everything is compiled in Appendix C.3.8 for a proof of Lemma C.9.

### C.3.2 PRELIMINARIES: EXPLORATION VISIT COUNTS AND TRUNCATED REGULARIZATION

The **exploration visit count** of $z$ at time $t \ge 1$ is given by

$$N_t^-(z) := \sum_{i=1}^{t-1} 1(Z_i = z, i \in \mathcal{T}^-). \qquad (C.20)$$

We write $(\tau_\ell)$ the stopping-time enumeration of exploration times $\mathcal{T}^-$, i.e., $\tau_1 := \inf \mathcal{T}^-$ and $\tau_{\ell+1} := \inf\{t > \tau_\ell : t \in \mathcal{T}^-\}$. Note that $N_{\tau_\ell}^-(z) = \sum_{i=1}^{\ell-1} 1(Z_{\tau_i} = z)$ for $\ell \ge 1$. Given $T \ge 1$, we denote $\bar{\varepsilon}''$ the T-truncated regularization parameter, given by

$$\begin{aligned} \varepsilon_{\text{lvl}}''(t) &:= \max\{\varepsilon_{\text{lvl}}'(t), \varepsilon_{\text{lvl}}'(T)\}, & \varepsilon_{\text{tst}}''(t) &:= \varepsilon_{\text{tst}}'(t), \\ \varepsilon_{\text{unif}}''(m) &:= \varepsilon_{\text{unif}}'(m), & \varepsilon_{\text{conv}}''(m) &:= \varepsilon_{\text{unif}}'(m). \end{aligned} \qquad (C.21)$$

That is, $\bar{\varepsilon}''$ and $\bar{\varepsilon}'$ only differ at $\varepsilon_{\text{lvl}}$.

### C.3.3 PART I: UNIFORM EXPLORATION GUARANTEES

We begin this adventure by establishing the uniform exploration guarantees of ECoE*, that are crucial to prove lower bound the likelihood of the trigger effect in Appendix C.3.4 and control the skeleton barrier in Appendix C.3.7. In Lemma C.10 below, we provide a high probability bound of the uniform visit rates of ECoE* during exploration, as a function of the uniformization regularizer $\varepsilon_{\text{unif}}$.

**Lemma C.10.** Let $(\tau_\ell)$ be the stopping-time enumeration of $\mathcal{T}^-$, i.e., $\tau_1 := \inf \mathcal{T}^-$ and $\tau_{\ell+1} := \inf\{t > \tau_\ell : t \in \mathcal{T}^-\}$. If the regularizer $\bar{\varepsilon}$ satisfies Assumption 6, there exist constants $\alpha, \kappa_{\bar{\varepsilon}} > 0$ and a polynomial $\text{poly}(-)$ of degree $4|\mathcal{S}|$ such that

$$\mathbf{P}(\exists z \in \mathcal{Z}, \exists \ell \ge m, N_{\tau_{\ell}}(z) < \alpha \varepsilon_{\text{unif}}(\ell)^{|\mathcal{S}|\ell}) \le \exp(-\text{poly}(\varepsilon_{\text{unif}}(m))m + \kappa_{\bar{\varepsilon}}).$$

**Proof** Fix $\ell \ge m$ and denote $\eta := \eta(\ell) := \varepsilon_{\text{unif}}(\ell)$ for short. We consider the Markov decision process $M_\eta := (\mathcal{Z}, \nu, p_\eta)$ with kernel given by

$$p_{\eta}(s, a) := (1 - \eta|\mathcal{A}(s)|)p(s, a) + \eta \sum_{a' \in \mathcal{A}(s)} p(s, a').$$

The model $M_\eta$ is communicating, because the execution of the fully uniform policy $\pi_u$ on $M_\eta$ is equivalent to the execution of the uniform policy on $M$, in the sense that $\mathbf{E}^{M, \pi_u}[-] = \mathbf{E}^{M, \pi_u}[-]$. By construction, the execution of any $\eta$-uniform policy $\pi$ on $M$ can be seen as the execution of a randomized policy $\pi_\eta$ on $M_\eta$, with $\mathbf{E}^{\pi_\eta, M}[-] = \mathbf{E}^{\pi, M_\eta}[-]$.
Fix $z_0 \in \mathcal{Z}$ and introduce the reward function $f(z) := \mathbf{1}(z = z_0)$. Consider the model $M_{\eta}^{-f} = (\mathcal{Z}, -f, p_{\eta})$ with kernel $p_{\eta}$ and deterministic reward function $-f$. Introduce $g_{\eta}^{-f}$, $b_{\eta}^{-f}$ and $\Delta_{\eta}^{-f}$ the associated optimal gain, bias an gap functions of $M_{\eta}^{-f}$. Because $M_{\eta}^{-f}$ is communicating, we have $\text{sp}(g_{\eta}^{-f}) = 0$. Let $\pi_{\eta}^*$ be a deterministic bias optimal policy of $M_{\eta}^{-f}$. By construction, $\pi_{\eta}^*$ corresponds to an $\eta$-uniform policy of $M$ under which all pairs are recurrent. By Lemma A.7, we have $\min(g_{\eta}^{-f}) = \max(g_{\eta}^{-f}) \le -\alpha(\ell) := -\text{dmin}(p)^{|\mathcal{S}|\eta^{|\mathcal{S}|}}$. Consider the gaps in $M$, given by

$$ \Delta^{-f}(s, a) := g_{\eta}^{-f}(s) + b_{\eta}^{-f}(s) + f(s, a) - p(s, a)b_{\eta}^{-f}. $$

Following from the Bellman equations of $M_{\eta}^{-f}$, we check that every $\eta$-uniform policy $\pi$ satisfies

$$ \sum_{a \in \mathcal{A}(s)} \pi_{\eta}(a|s) \Delta_{\eta}^{-f}(s, a) = \sum_{a \in \mathcal{A}(s)} \pi(a|s) \Delta^{-f}(s, a) \ge 0 \quad (C.22) $$

where $\pi_{\eta}$ is the randomized policy induced by $\pi$ in $M_{\eta}$. Introduce the function $\beta(\ell) := 1 + 2|\mathcal{S}|\text{dmin}(p)^{-|\mathcal{S}|}\varepsilon_{\text{unif}}(\ell)^{-|\mathcal{S}|}$. By Lemma A.7, we have $\beta(\ell) \ge \max\{\text{sp}(b_{\eta}^{-f}), \|\Delta^{-f}\|_{\infty}\}$. We have

$$ \begin{aligned} N_{\tau_{\ell}}(z_0) &= \sum_{t=1}^{\tau_{\ell}-1} \mathbf{1}(Z_t = z_0) \ge \sum_{i=1}^{\ell-1} \mathbf{1}(Z_{\tau_i} = z_0) \\ &\stackrel{(\dagger)}{=} \sum_{i=1}^{\ell-1} (-g_{\eta}^{-f}(S_{\tau_i}) + (p(Z_{\tau_i}) - e_{S_{\tau_i}})b_{\eta}^{-f} + \Delta^{-f}(Z_{\tau_i})) \\ &= (\ell-1)\alpha(\ell) + \underbrace{\sum_{i=1}^{\ell-1} (p(Z_{\tau_i}) - e_{S_{\tau_i}})b_{\eta}^{-f}}_{A_1} + \underbrace{\sum_{i=1}^{\ell-1} \Delta^{-f}(Z_{\tau_i})}_{A_2} \end{aligned} $$

where $(\dagger)$ unfolds the definition of $\Delta^{-f}$. We control the error terms as follows, starting with $A_1$. We have

$$ \begin{aligned} A_1 &= \sum_{i=1}^{\ell-1} (b_{\eta}^{-f}(S_{\tau_{i+1}}) - b_{\eta}^{-f}(S_{\tau_i})) + \sum_{i=1}^{\ell-1} (p(Z_{\tau_i}) - e_{S_{\tau_{i+1}}})b_{\eta}^{-f} \\ &\stackrel{(\dagger)}{\ge} -|\mathcal{Z}||\mathcal{S}|\beta(\ell) + \sum_{i=1}^{\ell-1} (p(Z_{\tau_i}) - e_{S_{\tau_{i+1}}})b_{\eta}^{-f} \end{aligned} $$

where $(\dagger)$ follows from the observation that, between exploration times, the algorithm is exploiting. When it does, it does so until regeneration, hence coming back to the state where exploration was suspended; At the exception of phases killed by panicking, but there are at most $|\mathcal{Z}||\mathcal{S}|$ of them—one for each transition to be discovered, see Lemma C.21. The remaining right-hand term is a martingale that we leave for later.

We continue with $A_2$. We have

$$ A_2 := \sum_{i=1}^{\ell-1} \Delta^{-f}(Z_{\tau_i}) $$
$$
\begin{align*}
&= \sum_{i=1}^{\ell-1} \sum_{a \in \mathcal{A}(S_{\tau_i})} \pi_{\tau_i}^{-}(a|S_{\tau_i}) \Delta^{-f}(S_{\tau_i}, a) + \sum_{i=1}^{\ell-1} \sum_{a \in \mathcal{A}(S_{\tau_i})} (\mathbf{1}(A_{\tau_i} = a) - \pi_{\tau_i}^{-}(a|S_{\tau_i})) \Delta^{-f}(S_{\tau_i}, a) \\
&\stackrel{(\dagger)}{\ge} \sum_{i=1}^{\ell-1} \sum_{a \in \mathcal{A}(S_{\tau_i})} (\mathbf{1}(A_{\tau_i} = a) - \pi_{\tau_i}^{-}(a|S_{\tau_i})) \Delta^{-f}(S_{\tau_i}, a)
\end{align*}
$$

where $\dagger$ follows from the observation that $\pi_{\tau_i}^{-}$ is $\eta$-randomized (since $i \le \ell$), that $\varepsilon_{\text{unif}}$ is non-increasing by Assumption 6 (A1) combined with (C.22). We conclude that $A_1$ and $A_2$ both involve martingales obtained as the sum of $\ell - 1$ martingale differences whose terms have span at most $\beta(\ell)$. So, by a time-uniform Azuma-Hoeffing's inequality (Lemma C.25), we find that with probability $1 - \delta$ and uniformly for $\ell \ge m$, we have

$$
N_{\tau_{\ell}}(z_0) \geq \alpha(\ell - 1) - \beta(\ell) \left( |\mathcal{Z}| |\mathcal{S}| + 2 \sqrt{(\ell - 1) \log \left( \frac{1 + \ell}{\delta} \right)} \right). \quad (C.23)
$$

We conclude by solving $m\alpha(m) > 4\beta(m)\sqrt{m\log((1+m)/\delta)}$ in $\delta$. We decouple the inequality by simplifying it to the pair of conditions (C1) $m\alpha(m) > 4\beta(m)\sqrt{m\log(1+m)}$ and (C2) $m\alpha(m) > 4\beta(m)\sqrt{m\log(1/\delta)}$. We know that $\varepsilon_{\text{unif}}(\ell) = \omega(\log(\ell)^{-1})$ by assumption, so that the condition (C1) is satisfied for $m$ large enough, say $m \ge C_{\varepsilon}$. As for the condition (C2), solving in $\delta$ provides the condition

$$
\delta \geq \exp\left(-\frac{\alpha(m)^2 m}{\beta(m)^2}\right).
$$

By assumption on $\varepsilon_{\text{unif}}$ again, see Assumption 6 (A6), the function $m \mapsto \alpha(m)^2 \beta(m)^{-2}m$ is increasing provided that $m$ is large enough, so provided that $m \ge C_{\bar{\varepsilon}}$ up to increasing $C_{\bar{\varepsilon}}$. In the end, we set

$$
\delta := \exp\left(-\frac{\alpha(m)^2 m}{\beta(m)^2} + \mathbf{1}(m < C_{\varepsilon})\right) \le \exp(-\text{poly}(\varepsilon_{\text{unif}}(m))m + C_{\bar{\varepsilon}})
$$

where $\text{poly}(-)$ is of degree $4|\mathcal{S}|$.

<figure><img src="image_19.png" /></figure>

C.3.4 PART II: POST BURN-IN PROPERTIES & THE TRIGGER EFFECT

In this section, we show that after a few exploration phases called the **burn-in** exploration phases, empirical data starts to concentrate in probability so that the algorithm explores near optimally: The exploration policy is near optimal and GLR exploration tests do not overshoot the required amount of information.

We refer this phenomenon to as the **trigger effect**.

Consider the function $\beta(\ell) := 1 + 2|\mathcal{S}|\text{dmin}(p)^{-|\mathcal{S}|}\varepsilon'_{\text{unif}}(\ell)^{-|\mathcal{S}|}$ and let $\delta(\ell) := \alpha\varepsilon_{\text{unif}}(\ell)^{|\mathcal{S}|}$ where $\alpha > 0$ is an alias for constant given by Lemma C.10. Recall that $\mathcal{P}_{\delta(\ell)}(\mathcal{Z})$ is the set of probability distributions $\mu$ over $\mathcal{Z}$ such that $\min(\mu) \ge \delta(\ell)$. Given a burn-in threshold $\varepsilon_0 > 0$, we introduce the **trigger event** as

$$
\mathcal{E} \equiv \mathcal{E}_{\varepsilon_0, T} := \left( \forall \ell \ge \frac{\varepsilon_0 \log(T)}{\beta(\varepsilon_0 \log(T))} : \begin{array}{@{}l@{}}
\mathcal{Z}_{\varepsilon \text{\textit{lvl''}}(\tau_\ell)}^{**}(\hat{M}_{\tau_\ell}) = \mathcal{Z}^{**}(M) \text{ and } \hat{M}_{\tau_\ell} \sim M \text{ and} \\
\quad \|\mu_{\bar{\varepsilon}''}^*(\hat{M}_{\tau_\ell}) - \mu_{\bar{\varepsilon}''}^*(M)\|_{\infty} < \varepsilon_0 \beta(\ell)^{-2} \text{ and} \\
\quad \sup_{\mu \in \mathcal{P}_{\delta(\ell)}(\mathcal{Z})} |C_{\bar{\varepsilon}''}(\mu, \hat{M}_{\tau_\ell}) - C_{\bar{\varepsilon}''}(\mu, M)| < \varepsilon_0
\end{array} \right) \quad (C.24)
$$
where $\bar{\epsilon}''$ is the T-truncated regularization hyperparameter, see Appendix C.3.2 and (C.21). It is to be noted that for $\epsilon_{\text{unif}}(\ell) = \omega(\log^{-1}(\ell))$, we have $\beta(\ell) \ge 1$ and $\beta(\ell) = o(\log(\ell)^{|S|})$ when $\ell \to \infty$, so that $\beta(\ell)$ is negligible in front of any positive power of $\ell$.

In Lemma C.11 below, we bound the probability of error of the trigger event $\mathcal{E}$ when the exploration threshold $\epsilon_0 \log(T)/\beta(\epsilon_0 \log(T))$ is replaced by a general $m/\beta(m)$ for $m \ge 1$, see (C.25) below. For $m \ge 1$, let

$$ \mathcal{E}_m \equiv \mathcal{E}_{\epsilon_0, T, m} := \left( \forall \ell \ge \frac{m}{\beta(m)} : \begin{array}{l} \mathcal{Z}_{\epsilon \text{lvl}''(\tau_\ell)}^{**}(\hat{M}_{\tau_\ell}) = \mathcal{Z}^{**}(M) \text{ and } \hat{M}_{\tau_\ell} \sim M \text{ and} \\ \quad \|\mu_{\bar{\epsilon}''}^*(\hat{M}_{\tau_\ell}) - \mu_{\bar{\epsilon}''}^*(M)\|_{\infty} < \epsilon_0 \beta(\ell)^{-2} \text{ and} \\ \quad \sup_{\mu \in \mathcal{P}_{\delta(\ell)}(Z)} |C_{\bar{\epsilon}''}(\mu, \hat{M}_{\tau_\ell}) - C_{\bar{\epsilon}''}(\mu, M)| < \epsilon_0 \end{array} \right). \quad (C.25) $$

In Corollary C.12, we instantiate $m = \epsilon_0 \log(T)$ to obtain a final bound on $\mathbf{P}(\mathcal{E}^c)$.

**Lemma C.11.** Let $(\tau_\ell)$ be the stopping-time enumeration of $T^-$, i.e., $\tau_1 := \inf T^-$ and $\tau_{\ell+1} := \inf\{t > \tau_\ell : t \in T^-\}$. For all error level $\epsilon_0 > 0$, there exists a constant $\kappa_{\bar{\epsilon}} > 0$ such that for all $T \ge \kappa_{\bar{\epsilon}}$, the event $\mathcal{E}_m$ as given by (C.25) satisfies

$$ \mathbf{P}(\mathcal{E}_m^c) \le \exp\left(-\text{poly}(\bar{\epsilon}'') \exp\left(-\frac{\alpha}{\epsilon_{\text{unif}}(m)^{|S|}}\right) m + \kappa_{\bar{\epsilon}}\right) $$

for all $m \ge 1$, where $\text{poly}(\bar{\epsilon}'') := \alpha' \epsilon_{\text{lvl}}(T)^2 \epsilon_{\text{unif}}(m)^{11|S|} \epsilon_{\text{conv}}(m)^2$ is polynomial and $\alpha, \alpha' \in \mathbf{R}_+^*$ are constants that depend on $M$.

**Proof** Introduce the event $\mathcal{E}'_m := (\forall z \in \mathcal{Z}, \forall \ell \ge m, N_{\tau_\ell}(z) \ge \alpha_1 \epsilon_{\text{unif}}(\ell)^{|S|}\ell)$ where $\alpha_1 > 0$ is a constant given by Lemma C.10. We have

$$ \mathbf{P}(\mathcal{E}_m^c) \le \mathbf{P}(\mathcal{E}_m^c \cap \mathcal{E}'_m) + \mathbf{P}((\mathcal{E}'_m)^c) \stackrel{(\dagger)}{\le} \mathbf{P}(\mathcal{E}_m^c \cap \mathcal{E}'_m) + \exp(-\text{poly}(\epsilon_{\text{unif}}(m))m + \kappa_{\bar{\epsilon}}) $$

where $(\dagger)$ follows by Lemma C.10 again, and $\text{poly}(-)$ is a polynomial of degree $4|S|$ and $\kappa_{\bar{\epsilon}} < \infty$ is a constant.

Now, we look at conditions on $\|\hat{M}_{\tau_\ell} - M\|$ and $\bar{\epsilon}'$ under which the conditions of $\mathcal{E}_m$ are met, then we will conclude by combining $\mathcal{E}'_m$ with concentration bounds (Lemma C.22). First, by Lemma C.24, the absolute continuity condition “$\hat{M}_{\tau_\ell} \sim M$”, which is equivalent to “$\|\hat{M}_{\tau_\ell} - M\|^* = \|\hat{M}_{\tau_\ell} - M\|$”, is met as soon as

$$ \|\hat{M}_{\tau_\ell} - M\| < \text{dmin}(M). \quad (C.26) $$

By Proposition 3, the condition “$\mathcal{Z}_{\epsilon \text{lvl}'}^{**}(\hat{M}_{\tau_\ell}) = \mathcal{Z}^{**}(M)$” is met as soon as

$$ \alpha_2 \|\hat{M}_{\tau_\ell} - M\| < \frac{1}{3} \epsilon_{\text{lvl}''}(\tau_\ell) \quad \text{and} \quad \epsilon_{\text{lvl}''}(\tau_\ell) \le \frac{1}{3} \epsilon_{\text{lvl}''}(\ell) < \Delta^g(M) \quad (C.27) $$

for some model dependent constant $\alpha_2 > 0$. Note that the second condition of (C.27) is satisfied as soon as $\ell, T$ are large enough, say $T, \ell \ge \kappa_{\bar{\epsilon}}$ up to increasing $\kappa_{\bar{\epsilon}}$.

For the condition “$\|\mu_{\bar{\epsilon}''}^*(\hat{M}_{\tau_\ell}) - \mu_{\bar{\epsilon}''}^*(M)\|_{\infty} < \epsilon_0 \beta(\ell)^{-2}$”, we rely on Proposition B.18. Because the error function $\psi_\mu$ of Proposition B.18 satisfies $\psi_\mu(x) = O(x)$ when $x \to 0$, there
exists constants $\alpha_3, \alpha_4 \in \mathbf{R}_+^*$ such that $\psi_\mu(x) \le \alpha_3 x$ for $x \le \alpha_4$. Following Proposition B.18, we get the condition

$$ \sqrt{\frac{\|\hat{M}_{\tau_l} - M\|}{\varepsilon'_{\text{unif}}(\ell)^{3|S|}\varepsilon'_{\text{conv}}(\ell)}} + \mathbf{1}\left(\|\hat{M}_{\tau_l} - M\| < \alpha_5 \min\left\{\varepsilon_{\text{lvl}}''(\ell), \exp\left(-\frac{\alpha_6}{\varepsilon'_{\text{unif}}(\ell)^{|S|}}\right)\right\}\right) \le \frac{\varepsilon_0}{\alpha_3 \beta(\ell)^2} \quad (C.28) $$

where $\alpha_5, \alpha_6$ are other model dependent constants. Note that the indicator in (C.28) can be rewritten as the pair of conditions

$$ \|\hat{M}_{\tau_l} - M\| \le \alpha_5 \varepsilon_{\text{lvl}}''(\tau_l) \quad \text{and} \quad \|\hat{M}_{\tau_l} - M\| \le \alpha_5 \exp\left(-\frac{\alpha_6}{\varepsilon'_{\text{unif}}(\ell)^{|S|}}\right). \quad (C.29) $$

Note that the first condition of (C.29) is essentially the same as the first condition of (C.27) up to tuning constants.

To obtain the last condition “$\sup_{\mu \in \mathcal{P}_{\delta(\ell)}(Z)} |C_{\bar{\varepsilon}''}(\mu, \hat{M}_{\tau_l}) - C_{\bar{\varepsilon}''}(\mu, M)| < \varepsilon_0$”, we rely on Lemma B.11. Using that, for all $\alpha > 0$, $\varepsilon_{\text{unif}}(m)^{-\alpha} = o(\exp(1/\varepsilon_{\text{unif}}(m)))$ when $m \to \infty$ and that $\delta(\ell) = \Omega(\varepsilon'_{\text{unif}}(\ell)^{|S|})$, we obtain a pair of conditions where the first one is similar to (C.29) and the second is

$$ \|\hat{M}_{\tau_l} - M\| < \alpha_7 \varepsilon_0. \quad (C.30) $$

Since $\varepsilon'_{\text{unif}}(m) \to 0$ as $m \to \infty$ by Assumption 6 (A0), the condition (C.30) is already satisfied through (C.28) provided that $\ell$ is large enough, say $\ell > \kappa_{\bar{\varepsilon}}$ up to increasing $\kappa_{\bar{\varepsilon}}$. Using that $\beta(\ell) = O(\varepsilon'_{\text{unif}}(\ell)^{-|S|})$ and that $\min\{a_1, \dots, a_n\} \ge \prod_{i=1}^n a_i$ for $a_i \in [0, 1]$, we combine (C.26) to (C.30) into the single condition

$$ \|\hat{M}_{\tau_l} - M\| \le \alpha_8 \varepsilon_{\text{lvl}}''(\tau_l) \varepsilon'_{\text{unif}}(\ell)^{7|S|} \varepsilon'_{\text{conv}}(\ell) \exp\left(-\frac{\alpha_6}{\varepsilon'_{\text{unif}}(\ell)^{|S|}}\right) \quad \text{and} \quad \ell \ge \beta_{\varepsilon} $$

where $\alpha_8$ is some model dependent constant. Using that for all $\ell \ge 1$, we have $\varepsilon_{\text{lvl}}''(\tau_l) \ge \varepsilon_{\text{lvl}}(T)$, $\varepsilon'_{\text{unif}}(\ell) \ge \varepsilon_{\text{unif}}(\ell)$ and $\varepsilon'_{\text{conv}}(\ell) \ge \varepsilon_{\text{conv}}(\ell)$, we simplify the above into

$$ \|\hat{M}_{\tau_l} - M\| \le \underbrace{\alpha_8 \varepsilon_{\text{lvl}}(T) \varepsilon_{\text{unif}}(\ell)^{7|S|} \varepsilon_{\text{conv}}(\ell)}_{\varphi(\bar{\varepsilon}(\ell))} \exp\left(-\frac{\alpha_6}{\varepsilon_{\text{unif}}(\ell)^{|S|}}\right) \quad \text{and} \quad \ell \ge \beta_{\varepsilon}. \quad (C.31) $$

We conclude using concentration results (Lemma C.22). For $m \ge \kappa_{\bar{\varepsilon}}$, we have

$$ \begin{align*} & \mathbf{P}(\mathcal{E}_m^c \cap \mathcal{E}'_m) \\ & \le \mathbf{P}\left(\left(\exists \ell \ge m, \|\hat{M}_{\tau_l} - M\| \ge \varphi(\bar{\varepsilon}(\ell)) \exp\left(-\frac{\alpha_6}{\varepsilon_{\text{unif}}(\ell)^{|S|}}\right)\right), \mathcal{E}'_m, \right) \\ & = \mathbf{P}\left(\left(\exists \ell \ge m, \exists z \in \mathcal{Z}, \|(\hat{r}_{\tau_l}(z), \hat{p}_{\tau_l}(z)) - (r(z), p(z))\|_1 \ge \varphi(\bar{\varepsilon}(\ell)) \exp\left(-\frac{\alpha_6}{\varepsilon_{\text{unif}}(\ell)^{|S|}}\right)\right), \mathcal{E}'_m \right) \\ & \stackrel{(\dagger)}{\le} \sup_{\ell \ge m} \exp\left(-2\varphi(\bar{\varepsilon}(\ell))^2 \alpha_1 \varepsilon_{\text{unif}}(\ell)^{|S|} \exp\left(-\frac{2\alpha_6}{\varepsilon_{\text{unif}}(\ell)^{|S|}}\right)\right) \ell + \frac{1}{2} \log\left(1 + \alpha_1 \varepsilon_{\text{unif}}(\ell)^{2|S|} \ell\right) + \alpha_8 \\ & \stackrel{(\ddagger)}{=} \exp\left(-2\varphi(\bar{\varepsilon}(m))^2 \alpha_1 \varepsilon_{\text{unif}}(m)^{|S|} \exp\left(-\frac{2\alpha_6}{\varepsilon_{\text{unif}}(m)^{|S|}}\right)\right) m + \frac{1}{2} \log\left(1 + \alpha_1 \varepsilon_{\text{unif}}(m)^{2|S|} m\right) + \alpha_8 \end{align*} $$
$$ \stackrel{(\$)}{\le} \exp\left(-\varphi(\bar{\varepsilon}(m))^2 \alpha_1 \varepsilon_{\text{unif}}(m)^{|S|} \exp\left(-\frac{2\alpha_6}{\varepsilon_{\text{unif}(m)^{|S|}}}\right) m + \alpha_8\right) $$

where (†) follows by (C.31); (‡) follows from concentration results (Lemma C.22); (§) uses that the inner function in the exponential is decreasing for $\ell$ large enough by Assumption 6 (A6), so holds for $m \ge \kappa_{\bar{\varepsilon}}$ up to increasing $\kappa_{\bar{\varepsilon}}$; and ($) holds for $m$ large enough again, say $m \ge \kappa_{\bar{\varepsilon}}$ up to increasing $\kappa_{\bar{\varepsilon}}$ again. We conclude accordingly. ■

**Corollary C.12** (Trigger effect). Let $\mathcal{E}_{\varepsilon_0,T}$ be the trigger event as given by (C.24). For all $\alpha > 0$ and $\varepsilon_0 > 0$, we have

$$ \mathbf{P}((\mathcal{E}_{\varepsilon_0,T})^c) = o\left(\exp\left(-\log^{1-\alpha}(T)\right)\right) \quad \text{when } T \to \infty. $$

**Proof** Let $m_T := \varepsilon_0 \log(T)$ and fix $\alpha > 0$. By (A2-4) from Assumption 6, we find $\text{poly}(\bar{\varepsilon}(m_T)) \ge \log^{-\alpha}(T)$ when $T \to \infty$ and by (A4), it follows that $\exp(-\beta \varepsilon_{\text{unif}}(m_T)^{-|S|}) \ge \exp(-\alpha \beta \log \log(T))$ when $T \to \infty$. All together, we find that when $T \to \infty$,

$$ \mathbf{P}(\mathcal{E}_{m_T}^c) \le \exp\left(-\Omega\left(\log(T)^{-\alpha} \log(T)^{-\alpha\beta} \cdot \varepsilon_0 \log(T)\right)\right) = \exp\left(-\Omega\left(\log(T)^{1-\alpha(1+\beta)}\right)\right). $$

As this holds for arbitrary $\alpha > 0$, we conclude accordingly. ■

### C.3.5 PART III: POST BURN-IN QUALITY OF EXPLORATION

In this section, we show that under the trigger event (C.24), explorative visit counts concentrate around $N_{\tau_\ell}^-(z) \approx \ell \mu^*(z)$ in high probability after a burn-in time of $\sqrt{\varepsilon_0} \log(T)$ exploration phases, see Lemma C.13 below. Roughly speaking, it means that once the trigger event holds, exploration is near optimal.

**Lemma C.13.** Let $(\tau_\ell)$ be the stopping-time enumeration of $\mathcal{T}^-$, i.e., $\tau_1 := \inf \mathcal{T}^-$ and $\tau_{\ell+1} := \inf\{t > \tau_\ell : t \in \mathcal{T}^-\}$. Let $\mathcal{E} \equiv \mathcal{E}_{\varepsilon_0,T}$ be the trigger event, see (C.24). For all $\varepsilon_0 \in (0, 1]$, there exists a constant $\alpha_\varepsilon(\varepsilon_0) < \infty$ such that, for all $T \ge 1$, all $m \ge \sqrt{\varepsilon_0} \log(T) + \alpha_\varepsilon(\varepsilon_0)$ and all $z \in \mathcal{Z}$, we have

$$ \mathbf{P}\left(\exists \ell \ge m : \tau_\ell \le T \text{ and } \left|\frac{1}{\ell} N_{\tau_\ell}^-(z) - \mu^*(z)\right| \ge 8 |\mathcal{Z}| \sqrt{\varepsilon_0}, \mathcal{E}\right) \le \exp\left(-\frac{|\mathcal{Z}|^2 \varepsilon_0 m}{\beta(m)^2}\right) \quad (C.32) $$

$$ \text{where } \beta(m) := 1 + 2|S|\min(p)^{-|S|} \varepsilon_{\text{unif}}(m)^{-|S|}. $$

We start by showing the alternative statement of Lemma C.13 given by Lemma C.14 below. Then Lemma C.14 is reworked into Lemma C.13 to better fit our needs.

**Lemma C.14.** Let $(\tau_\ell)$ be the stopping-time enumeration of $\mathcal{T}^-$, i.e., $\tau_1 := \inf \mathcal{T}^-$ and $\tau_{\ell+1} := \inf\{t > \tau_\ell : t \in \mathcal{T}^-\}$. Let $\mathcal{E} \equiv \mathcal{E}_{\varepsilon_0,T}$ be the trigger event, see (C.24). There exists a function $\gamma_\varepsilon(m) = O(\sum_{n=1}^m (\varepsilon_{\text{unif}}(n)/\varepsilon_{\text{conv}}(n) + \varepsilon_{\text{conv}}(n))^{1/2}) = o(m)$ when $m \to \infty$ such that, for all $\delta > 0$, we have

$$ \mathbf{P}\left(\exists \ell \ge 1 : \tau_\ell \le T \text{ and } \left|N_{\tau_\ell}^-(z) - \ell \mu^*(z)\right| > \left(\frac{\varepsilon_0 |\mathcal{Z}| (\log(T) + 4\ell)}{\beta(\ell) \sqrt{\ell \log\left(\frac{1+\ell}{\delta}\right)}} + \gamma_\varepsilon(\ell)\right), \mathcal{E}\right) \le \delta \quad (C.33) $$

$$ \text{where } \beta(m) := 1 + 2|S|\min(p)^{-|S|} \varepsilon_{\text{unif}}(m)^{-|S|}. $$
**Discussion of Lemma C.14.** Said roughly, (C.33) states that on the good event $\mathcal{E}$, we have $N_{\tau_\ell}^-(z) \approx \ell\mu^*(z)$ up to a few error terms. The first term $\varepsilon_0|\mathcal{Z}|\log(T)$ is due to the initial burn-in phase, when the number of exploration times is less than $\varepsilon_0\log(T)$ and that the algorithm explores very badly, due to potentially wrong empirical data. The second term $4\varepsilon_0|\mathcal{Z}|\ell$ comes from the algorithm navigating following a noisy version of the optimal exploration policy. The third term $\beta(\ell)\sqrt{\ell\log((1+\ell)/\delta)}$ comes from the stochasticity of the navigation, namely, from the aggregate difference between $e_{S_{t+1}}$ and $p(Z_t)$ suffered during exploration. The last term $\gamma_{\bar{\varepsilon}}(\ell)$ encapsulates the cost of changing of exploration epochs and the cost on the quality of the exploration policy due to the regularization $\bar{\varepsilon}$.

**Proof of Lemma C.14** We begin by introducing a few notations. Because the regularization is floored as in (17), the uniformization $\varepsilon'_{\text{unif}}(\tau_\ell)$ and the convexification $\varepsilon'_{\text{conv}}(\tau_\ell)$ are constant over ranges of exploration times the form $\{\tau_{2^m}, \dots, \tau_{2^{m+1}-1}\}$. Such ranges are referred to as **exploration epochs** and exploration will be decomposed along them. Further note that for $\tau_\ell \le T$, the floored and $T$-truncated regularizers (C.21) are equal with $\bar{\varepsilon}'(\tau_\ell) = \bar{\varepsilon}''(\tau_\ell)$ and in particular, $\varepsilon_{\text{lvl}}''(\tau_\ell) \ge \varepsilon_{\text{lvl}}''(T)$. For an exploration epoch $m \ge 0$, let

$$ \mu_m \in \text{Inv}(M) \cap \mathcal{P}(\mathcal{Z}) \qquad (C.34) $$

the central optimal exploration measure (Definition B.3) of $M$ under regularization $\bar{\varepsilon}''(\tau_{2^m})$. Let $\pi_m^*$ the fully randomized policy induced by $\mu_m$ (see Proposition A.5). For $z \in \mathcal{Z}$, let $b_m^z$ and $\Delta_m^z$ the bias and gap functions of $\pi_m$ in $M$ under the reward function $f(z') := \mathbf{1}(z' = z)$. Fix $\ell_0 \ge 1$ and assume that $\tau_{2^m} \le T$ for $m = \lfloor \log_2(\ell_0) \rfloor$. We write

$$ \begin{aligned} N_{\tau_{\ell_0}}(z) &= \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) \mathbf{1}(Z_\ell = z) \\ &= \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) (\mu_m(z) + (e_{S_{\tau_\ell}} - p(Z_{\tau_\ell})) b_m^z - \Delta_m^z(Z_{\tau_\ell})). \end{aligned} \qquad (C.35) $$

By Lemma A.7, we have the two bounds $\beta(x) \ge \max_{m \le \log_2(x)} \max\{\text{sp}(b_m^z), \|\Delta_m^z\|_\infty\}$ and $\beta(x)^{-1} \le \min_{m \le \log_2(x)} \min(\mu_m)$. We continue by bounding the middle term in (C.35). We have

$$ \begin{aligned} & \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) (e_{S_{\tau_\ell}} - p(Z_{\tau_\ell})) b_m^z \\ \stackrel{(\dagger)}{=} & \pm \log_2(\ell_0)\beta(\ell_0) + \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) \left( (e_{S_{\tau_{\ell+1}}} - e_{S_{\tau_{\ell+1}}}) + (e_{S_{\tau_{\ell+1}}} - p(Z_{\tau_\ell})) \right) b_m^z \\ \stackrel{(\ddagger)}{=} & \pm \beta(\ell_0)(\log_2(\ell_0) + |\mathcal{Z}||S|) + \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) (e_{S_{\tau_{\ell+1}}} - p(Z_{\tau_\ell})) b_m^z \end{aligned} \qquad (C.36) $$

where $(\dagger)$ introduces the notation $x = \pm\alpha + y$ as a shorthand for $|y - x| \le \alpha$; and $(\ddagger)$ follows from the observation that $S_{\tau_{\ell+1}} \ne S_{\tau_{\ell+1}}$ can only hold when a panic happens, and the algorithm panics at most $|\mathcal{Z}||S|$ times, see Lemma C.21. The remaining term is a martingale that will be dealt with in time.
Moving on to the bound of the last term in (C.35), we write

$$
\begin{align*}
& \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_{\ell} < \tau_{\ell_0}) \Delta_m^z(Z_{\tau_{\ell}}) \\
&= \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_{\ell} < \tau_{\ell_0}) (\pi_m^*(S_{\tau_{\ell}}) + (\pi_m^*(S_{\tau_{\ell}}) - \pi_{\tau_{\ell}}^-(S_{\tau_{\ell}})) + (\pi_{\tau_{\ell}}^-(S_{\tau_{\ell}}) - e_{A_{\tau_{\ell}}})) \cdot \Delta_m^z \\
&\stackrel{(\dagger)}{=} \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_{\ell} < \tau_{\ell_0}) (\pi_m^*(S_{\tau_{\ell}}) - \pi_{\tau_{\ell}}^-(S_{\tau_{\ell}})) \cdot \Delta_m^z \\
&\qquad + \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_{\ell} < \tau_{\ell_0}) (\pi_{\tau_{\ell}}^-(S_{\tau_{\ell}}) - e_{A_{\tau_{\ell}}}) \cdot \Delta_m^z
\end{align*}
\tag{C.37}
$$

where (†) follows from the Poisson equation of $\pi_m^*$, stating that $\pi_m^*(s) \cdot \Delta_m^z = 0$ for all $s \in S$.
Equation (C.37) is the sum of a martingale and of an error term denoted $B_1$. We focus on
that error term. On the trigger event $\mathcal{E}$ defined in (C.24) and combined with Lemma C.15,
we see that for $\ell \in \{2^m, \dots, 2^{m+1} - 1\}$, we have $\|\pi_{\tau_\ell}^- - \pi_m^*\|_\infty \le 4\epsilon_0\beta(m)^{-2}\min(\mu_m)^{-1}$
provided that $m$ is large enough. Indeed, for $\ell \ge \epsilon_0\log(T)/\beta(\epsilon_0\log(T))$ and on the trigger
event $\mathcal{E}$, we have

$$
\| \mu_{\bar{\epsilon}''(\tau_l)}^*(\hat{M}_{\tau_l}) - \mu_{\bar{\epsilon}''(\tau_l)}^*(M) \|_{\infty} \le \epsilon_0 \beta(l)^{-2} \quad (C.38)
$$

by definition. Recall that $\bar{\epsilon}''(\tau_\ell) = \bar{\epsilon}'(\tau_\ell)$ for $\tau_\ell \le T$. Accordingly, $\bar{\epsilon}''(\tau_\ell)$ can be changed to $\bar{\epsilon}'(\tau_\ell)$ for all $\ell \le \ell_0$ since $\tau_{\ell_0} \le T$. By invoking Lemma C.15, we conclude that for all $2^m \ge \epsilon_0 \log(T)/\beta(\epsilon_0 \log(T))$ and $\ell \in \{2^m, \dots, 2^{m+1}\}$ with $\tau_\ell \le \tau_{\ell_0}$, we have

$$
\| \pi_{\tau_l}^{-} - \pi_m^* \|_{\infty} \le 4\epsilon_0\beta(m)^{-2} \min(\mu_m)^{-1} \quad (C.39)
$$

So, on $\mathcal{E}$, we have

$$
\begin{align*}
|\text{B}_1| &\stackrel{(\dagger)}{\le} \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) \|\pi_{\tau_\ell}^- - \pi_m^*\|_\infty \|\Delta_m^z\|_1 \\
&\stackrel{(\ddagger)}{\le} \frac{\epsilon_0 \log(T) \sup_{m \le \log_2(\epsilon_0 \log(T))} \|\Delta_m^z\|_1}{\beta(\epsilon_0 \log(T))} + \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) \frac{4\epsilon_0 \|\Delta_m^z\|_1}{\beta(2^m)^2 \min(\mu_m)} \\
&\stackrel{(\S)}{\le} |\mathcal{Z}| \left( \frac{\epsilon_0 \log(T) \sup_{m \le \log_2(\epsilon_0 \log(T))} \|\Delta_m^z\|_\infty}{\beta(\epsilon_0 \log(T))} + \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) \frac{4\epsilon_0 \|\Delta_m^z\|_\infty}{\beta(2^m)^2 \min(\mu_m)} \right) \\
&\stackrel{(\S)}{\le} \epsilon_0 |\mathcal{Z}| (\log(T) + 4\ell_0) \tag{C.40}
\end{align*}
$$

where (†) follows from Hölder's inequality; (‡) bounds the first $\epsilon_0 \log(T)/\beta(\epsilon_0 \log(T))$ terms
by $\|\Delta_m^z\|_1$ and invoke (C.39) for the others; (§) uses that $\|\Delta_m^z\|_1 \le |\mathcal{Z}|\|\Delta_m^z\|_\infty$; (§) follows
by bounding the first term using that $\beta(\ell) \le \beta(\epsilon_0 \log(T))$ for $\ell \le \epsilon_0 \log(T)$, then using
Lemma A.7 to obtain that $\|\Delta_m^z\|_\infty \le \beta(\epsilon_0 \log(T))$; and (§) bounds the second term with
Lemma A.7 for the bound $\|\Delta_m^z\|_\infty \le \min(\mu_m)\beta(2^m)^2$; and (§) follows from straight-forward
algebra.
Lastly, we relate $\sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mu_m(z) \mathbf{1}(\tau_\ell < \tau_{\ell_0})$ to $\ell_0 \mu^*(z)$. Let $\psi$ be the error function given by Proposition B.16, see (B.25). For all $m \ge 0$, we have

$$ \|\mu_m - \mu^*\|_{\infty} \le |\mathcal{Z}|^{\frac{3}{2}} \|\mu_m - \mu^*\|_2 \stackrel{(\dagger)}{\le} |\mathcal{Z}|^{\frac{3}{2}} \sqrt{\psi\left(\frac{\varepsilon_{\text{unif}}(2^m)}{\varepsilon_{\text{conv}}(2^m)} + \varepsilon_{\text{conv}}(2^m)\right)} $$

where $(\dagger)$ follows by definition of $\mu_m$ and Proposition B.16. Note that $\psi(x) = O(x)$ when $x \to 0$, see Proposition B.16. Therefore,

$$ \begin{align} & \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) \mu_m(z) \nonumber \\ & \stackrel{(\dagger)}{=} \ell_0 \mu^*(z) \pm |\mathcal{Z}|^{\frac{3}{2}} \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < \tau_{\ell_0}) \sqrt{\psi\left(\frac{\varepsilon_{\text{unif}}(2^m)}{\varepsilon_{\text{conv}}(2^m)} + \varepsilon_{\text{conv}}(2^m)\right)} \nonumber \\ & = \ell_0 \mu^*(z) \pm |\mathcal{Z}|^{\frac{3}{2}} \sum_{m=0}^{\lfloor \log_2(\ell_0) \rfloor} 2^m \sqrt{\psi\left(\frac{\varepsilon_{\text{unif}}(2^m)}{\varepsilon_{\text{conv}}(2^m)} + \varepsilon_{\text{conv}}(2^m)\right)} =: \ell_0 \mu^*(z) \pm \eta_{\bar{\varepsilon}}(\ell_0) \tag{C.41} \end{align} $$

where $(\dagger)$ introduces the short-hand $x = y \pm \alpha$ for $|x - y| \le \alpha$.

We have $\psi(x) = O(x)$ when $x \to 0$ and $\varepsilon_{\text{unif}}(2^m)/\varepsilon_{\text{conv}}(2^m) + \varepsilon_{\text{conv}}(2^m) \to 0$ as $m \to 0$ by Assumption 6 (A5). Now, note that if a non-negative sequence $(u_n) \in \mathbf{R}_+^N$ satisfies $u_n \to 0$, then we have $\sum_{m=0}^n 2^m u_{2^m} = o(2^n)$. So, the quantity $\eta_{\bar{\varepsilon}}(\ell_0)$ defined in (C.41) satisfies

$$ \eta_{\bar{\varepsilon}}(\ell_0) = O\left(\sum_{n=1}^{\ell_0} \sqrt{\frac{\varepsilon_{\text{unif}}(n)}{\varepsilon_{\text{conv}}(n)} + \varepsilon_{\text{conv}}(n)}\right) = o(\ell_0). \tag{C.42} $$

We finish the proof by merging everything. Combining (C.35), (C.36), (C.37), (C.40) and (C.41), we find that on the trigger event $\mathcal{E}$ and for $\tau_{\ell_0} \le T$, we have

$$ |N_{\tau_{\ell_0}}^{-}(z) - \ell_0 \mu^*(z)| \le \eta_{\bar{\varepsilon}}(\ell_0) + \beta_{\ell_0}(\log_2(\ell_0) + |\mathcal{Z}||\mathcal{S}|) + \varepsilon_0 |\mathcal{Z}|(\log(T) + 4\ell_0) + \text{MDS} $$

where MDS is the martingale difference sequence given by

$$ \sum_{m=0}^{\infty} \sum_{\ell=2^m}^{2^{m+1}-1} \mathbf{1}(\tau_\ell < t) \left( \left( e_{S_{\tau_\ell+1}} - p(Z_{\tau_\ell}) \right) b_m^z + \left( \pi_{\tau_\ell}^{-}(S_{\tau_\ell}) - e_{A_{\tau_\ell}} \right) \cdot \Delta_m^z \right), $$

which is the sum of $\ell_0$ terms that are almost surely bounded by $2\beta(\ell_0)$ because $\beta(-)$ is non-decreasing (see Assumption 6 (A1)) and $\text{sp}(b_m^z) \le D(\pi_m^*; M) \le \beta(2^m)$ by Lemmas A.7 and B.20. Therefore, using a time-uniform Azuma-Hoeffding inequality (Lemma C.25), it is bounded by $2\beta(\ell_0)\sqrt{\ell_0 \log((1 + \ell_0)/\delta)}$ with probability $1 - \delta$. To conclude the proof, we set $\gamma_{\bar{\varepsilon}}(\ell) := \eta_{\bar{\varepsilon}}(\ell) + \beta(\ell)(\log_2(\ell) + |\mathcal{Z}||\mathcal{S}|)$. Note that the definition of $\gamma_{\bar{\varepsilon}}$ does not depend on $\varepsilon_0$. Because $\beta(\ell) = \text{poly}(1/\varepsilon_{\text{unif}}(\ell))$ and $\varepsilon_{\text{unif}}(\ell)^{-\alpha} = o(\ell)$ for all $\alpha > 0$ by Assumption 6 (A4), we conclude that $\gamma_{\bar{\varepsilon}}(\ell) = o(\ell)$. ■

The proof of Lemma C.14 used the result below (Lemma C.15), relating the distances between two induced policies $\pi(\mu)$ and $\pi(\mu')$ when $\mu, \mu'$ are two fully supported measures that are close to one another.
**Lemma C.15.** Let $\mu, \mu' \in (\mathbf{R}_+^*)^Z$ be two fully supported measures on $\mathcal{Z}$ and denote $\pi(\mu), \pi(\mu')$ their respective induced policies, see Proposition A.5. If $\|\mu' - \mu\|_{\infty} \le \varepsilon \min(\mu)$ for $\varepsilon < (2|\mathcal{Z}|)^{-1}$, then

$$ \|\pi(\mu') - \pi(\mu)\|_{\infty} := \max_{(s,a) \in \mathcal{Z}} |\pi(\mu')(a|s) - \pi(\mu)(a|s)| \le 4\varepsilon. $$

**Proof** This is straight-forward algebra. For short, we write $\mu(s) := \sum_{a \in \mathcal{A}(s)} \mu(s, a)$. Recall that by definition, the policy induced by $\mu$ is $\pi(\mu)(a|s) := \mu(s, a)\mu(s)^{-1}$. For $(s, a) \in \mathcal{Z}$, we have

$$ \begin{aligned} |\pi(\mu')(a|s) - \pi(\mu)(a|s)| &\le \left| \frac{\mu(s, a) - \mu'(s, a)}{\mu(s)} \right| + \left| \mu'(s, a) \left( \frac{1}{\mu'(s)} - \frac{1}{\mu(s)} \right) \right| \\ &\le \varepsilon + \frac{\mu'(s, a)}{\mu(s)} \left| \frac{1}{1 + \frac{\mu'(s) - \mu(s)}{\mu(s)}} - 1 \right| \\ &\stackrel{(\dagger)}{\le} \varepsilon + \frac{2\mu'(s, a)\varepsilon}{\mu(s)} \le \varepsilon \left( 1 + \frac{2(\mu(s, a) + \varepsilon \min(\mu))}{\mu(s)} \right) \le 4\varepsilon \end{aligned} $$

where $(\dagger)$ uses that $|\frac{1}{1+x} - 1| \le 2|x|$ for $x \le \frac{1}{2}$. ■

We derive Lemma C.13 by reworking (C.33) from Lemma C.14 into a more convenient form.

**Proof of Lemma C.13** Borrowing the notations from Lemma C.14, it holds that with probability $1 - \delta$ and on the trigger event $\mathcal{E}$, that

$$ \begin{aligned} N_{\tau_{\ell}}(z) &\stackrel{(\dagger)}{\ge} \ell \mu^*(z) - \beta(\ell) \sqrt{\ell \log\left(\frac{1+\ell}{\delta}\right)} - \varepsilon_0 |\mathcal{Z}| (\log(T) + 4\ell) - \gamma_{\bar{\varepsilon}}(\ell) \\ &\ge \ell \left( \mu^*(z) - \beta(\ell) \sqrt{\frac{\log((1+\ell)/\delta)}{\ell}} - \varepsilon_0 |\mathcal{Z}| \left( \frac{\log(T)}{\ell} + 4 \right) - \frac{\gamma_{\bar{\varepsilon}}(\ell)}{\ell} \right) \\ &\ge \ell \left( \mu^*(z) - \frac{\beta(\ell) \left( \sqrt{\log(1+\ell)} + \sqrt{\log(1/\delta)} \right)}{\sqrt{\ell}} - \varepsilon_0 |\mathcal{Z}| \left( \frac{\log(T)}{\ell} + 4 \right) - \frac{\gamma_{\bar{\varepsilon}}(\ell)}{\ell} \right) \\ &\stackrel{(\ddagger)}{\ge} \ell (\mu^*(z) - 8\sqrt{\varepsilon_0} |\mathcal{Z}|) \end{aligned} $$

where $(\dagger)$ readily follows from Lemma C.14, see (C.33); and $(\ddagger)$ holds provided that the following equations hold:

$$ \begin{aligned} \sqrt{\varepsilon_0} |\mathcal{Z}| &\stackrel{(\dagger)}{\ge} \beta(\ell) \sqrt{\frac{\log(1+\ell)}{\ell}}, & \sqrt{\varepsilon_0} |\mathcal{Z}| &\stackrel{(\ddagger)}{\ge} \beta(\ell) \sqrt{\frac{\log(1/\delta)}{\ell}} \\ \sqrt{\varepsilon_0} |\mathcal{Z}| &\stackrel{(\S)}{\ge} \frac{\varepsilon_0 |\mathcal{Z}| \log(T)}{\ell}, & \sqrt{\varepsilon_0} |\mathcal{Z}| &\stackrel{(\S)}{\ge} \varepsilon_0 |\mathcal{Z}| \quad \text{and} \quad \sqrt{\varepsilon_0} |\mathcal{Z}| &\stackrel{(\#)}{\ge} \frac{\gamma_{\bar{\varepsilon}}(\ell)}{\ell}. \end{aligned} $$

In the above, $(\dagger)$ is of the form $\sqrt{\varepsilon_0} |\mathcal{Z}| \ge C \text{ poly}(\varepsilon_{\text{unif}}(\ell)) \sqrt{\log(1+\ell)/\ell}$, so using that $\varepsilon_{\text{unif}}(\ell) = \omega(\log^{-1}(\ell))$ by Assumption 6 (A4), so we see that $(\dagger)$ holds provided that $\ell$ is large enough with respect to $\varepsilon_0$, say $\ell \ge \alpha^{\dagger}(\varepsilon_0)$; $(\S)$ is equivalent to $\ell > \sqrt{\varepsilon_0} \log(T)$; $(\#)$ holds
provided that $\varepsilon_0 \le 1$; (#) holds provided that $\gamma_{\bar{\varepsilon}}(\ell) \le \ell\sqrt{\varepsilon_0}|\mathcal{Z}|$ so since $\gamma_{\bar{\varepsilon}}(\ell) = o(\ell)$, see Lemma C.14, so we see that (#) holds provided that $\ell$ is large enough with respect to $\varepsilon_0$, say $\ell \ge \alpha^{\#}(\varepsilon_0)$; and (‡) can be solved in $\delta > 0$, to find the condition $\delta \ge \exp(-|\mathcal{Z}|^2\varepsilon_0\ell\beta(\ell)^{-2})$. Setting $\alpha(\varepsilon_0) := \max\{\alpha^{\dagger}(\varepsilon_0), \alpha^{\#}(\varepsilon_0)\}$, we finally find the conditions

$$ \ell \ge \sqrt{\varepsilon_0 \log(T)} + \alpha(\varepsilon_0) \quad \text{and} \quad \delta \ge \exp\left(-|\mathcal{Z}|^2 \varepsilon_0 \cdot \frac{\ell}{\beta(\ell)^2}\right). \qquad (C.43) $$

Note that the condition on $\delta$ is monotone in $\ell$ when $\ell$ is large enough, see Assumption 6 (A6). So, up to increasing $\alpha(\varepsilon_0)$, if (C.43) holds for some $\ell \ge 1$, then it holds for all $\ell' \ge \ell$. The upper-bound is obtained similarly. ■

### C.3.6 PART IV: THE HIGH PROBABILITY EXPLORATION BARRIER

Following (C.32) from Lemma C.13, we have $N_{\tau_\ell}^{-}(z) \approx \ell\mu^{*}(z)$ with high probability on the trigger event $\mathcal{E}$. In other words, exploration is near optimal. Still under the trigger event, we know that the information value (Definition B.1) of exploration measures is well estimated by definition, see (C.24). Following this, we show that the number of exploration phases is quite unlikely to exceed the **exploration threshold** given by

$$ m_0 \equiv m_{\varepsilon_0, T} := \frac{(1 + \varepsilon_{\text{tst}}(T)) \log(T)}{\left(1 - \frac{8|\mathcal{Z}|\sqrt{\varepsilon_0}}{\min(\mu^*)}\right) (C(\mu^*, M) - \varepsilon_0)} \qquad (C.44) $$

where $\varepsilon_0 > 0$ quantifies the desired precision of the trigger event, see Lemma C.16.

**Lemma C.16.** Let $T^{-} := \sup\{\ell \ge 1 : \tau_\ell \le T - 1\}$ be the (random) number of exploration times prior to $T \ge 1$. Let $m_{\varepsilon_0, T}$ be as given by (C.44). There exists a constant $\kappa_{\bar{\varepsilon}} \in \mathbf{R}_+$ and a function $\psi \equiv \psi_{\varepsilon_0, \bar{\varepsilon}} : \mathbf{N} \to \mathbf{R}_+$ such that, for all $T \ge 1$, we have

$$ \mathbf{P}\left(T^{-} \ge m_{\varepsilon_0, T} + \kappa_{\bar{\varepsilon}} \log^{\frac{3}{4}}(T), \mathcal{E}\right) \le \exp(-\psi(T)) \qquad (C.45) $$

with $\psi(T) = \omega(\log(T)^{1/2-\alpha})$ as $T \to \infty$ for all $\alpha > 0$.

To establish Lemma C.16, we show first that after the exploration threshold $m_0$, exploration GLR tests (16) do not provoke exploration phases, see Lemma C.17 below.

**Lemma C.17.** Let $T^{-} := \sup\{\ell \ge 1 : \tau_\ell \le T - 1\}$ be the (random) number of exploration times prior to $T \ge 1$. Let $m_0 \equiv m_{\varepsilon_0, T}$ be as given by (C.44). There is a polynomial poly(-) of degree $4|\mathcal{S}|$ and some constant $\kappa_{\bar{\varepsilon}} \in \mathbf{R}_+$ such that, for $m_0 \equiv m_{\varepsilon_0, T} \ge \sqrt{\varepsilon_0 \log(T)} + \alpha_{\bar{\varepsilon}}(\varepsilon_0)$, we have

$$ \mathbf{P}\left(\sum_{\ell=m_0+1}^{T^{-}} 1\left(\begin{array}{l} S_{\tau_{\ell}} \in \mathcal{S}(\mathcal{Z}^{**}(M)) \\ \tau_{\ell} \notin \mathcal{T}^{\pm} \end{array}\right) > 0, \mathcal{E}\right) \le \exp\left(-\text{poly}(\varepsilon_{\text{unif}}(m_{\varepsilon_0, T}))m_{\varepsilon_0, T}\right). \qquad (C.46) $$

**Proof of Lemma C.17** Let $\beta(\ell) := 1 + 2|\mathcal{S}|\min(p)^{-|\mathcal{S}|}\varepsilon_{\text{unif}}(\ell)^{-|\mathcal{S}|}$. Note that on $\mathcal{E}$ and for $\ell \ge \varepsilon_0 \log(T)/\beta(\varepsilon_0 \log(T))$, we have $\mathcal{Z}_{\varepsilon \text{lvl}''(\tau_\ell)}^{**}(\hat{M}_{\tau_\ell}) = \mathcal{Z}^{**}(M)$ where $\bar{\varepsilon}''$ is the T-truncated
regularizer, see (C.21). We find condition on $\ell \ge 1$ such that the GLR exploration test (16) is guaranteed to fail at time $t = \tau_\ell$. Let $M^\dagger \in \text{Cnf}_{\bar{\varepsilon}}(\hat{M}_{\tau_\ell})$. We have

$$
\begin{align*}
\sum_{z \in \mathcal{Z}} N_{\tau_\ell}(z) \text{KL}(\hat{M}_{\tau_\ell}(z) || M^\dagger(z)) &\overset{(\dagger)}{\ge} (1-\lambda)\ell \sum_{z \in \mathcal{Z}} \max\{\mu^*(z), \alpha\varepsilon_{\text{unif}}(\ell)^{|S|}\} \text{KL}(\hat{M}_{\tau_\ell}(z) || M^\dagger(z)) \\
&\overset{(\ddagger)}{\ge} (1-\lambda)\ell \sum_{z \in \mathcal{Z}} ((1-\delta_\ell)\mu^*(z) + \delta_\ell) \text{KL}(\hat{M}_{\tau_\ell}(z) || M^\dagger(z)) \\
&\overset{(\S)}{\ge} (1-\lambda)\ell C_{\bar{\varepsilon}}((1-\delta_\ell)\mu^* + \delta_\ell e, \hat{M}_{\tau_\ell}) \\
&\overset{(\S)}{\ge} (1-\lambda)\ell \cdot (C_{\bar{\varepsilon}}((1-\delta_\ell)\mu^* + \delta_\ell e, M) - \varepsilon_0) \\
&\overset{(\#)}{\ge} (1-\lambda)\ell \cdot (C_{\bar{\varepsilon}}((1-\delta_\ell)\mu^*, M) - \varepsilon_0) \\
&= (1-\lambda)\ell \cdot ((1-\delta_\ell)C_{\bar{\varepsilon}}(\mu^*, M) - \varepsilon_0) \\
&\overset{(\#)}{\ge} (1-\lambda)\ell \cdot ((1-\delta_\ell)C_0(\mu^*, M) - \varepsilon_0)
\end{align*}
$$

where $(\dagger)$ introduces $\lambda := 8|\mathcal{Z}|\sqrt{\varepsilon_0}\text{dmin}(\mu^*)^{-1}$ and holds, on $\mathcal{E}$, uniformly over $\ell$ with probability $1 - \exp(-|\mathcal{Z}|^2\varepsilon_0 \cdot \beta(\ell)^{-2}\ell) - \exp(-\text{poly}(\varepsilon_{\text{unif}}(\ell))\ell + \kappa_{\bar{\varepsilon}})$, using a combination of (C.32) from Lemma C.13 to claim that $N_{\tau_\ell}(z) \gtrsim \ell\mu^*(z)$ and of the uniform exploration result of Lemma C.10 to claim that $N_{\tau_\ell}(z) \gtrsim \alpha\varepsilon_{\text{unif}}(\ell)^{|S|}$ for some $\alpha > 0$; $(\ddagger)$ introduces $\delta(\ell) := \alpha\varepsilon_{\text{unif}}(\ell)^{|S|}$; $(\S)$ holds by $M^\dagger \in \text{Cnf}_{\bar{\varepsilon}}(\hat{M}_{\tau_\ell})$ and by definition of $C_{\bar{\varepsilon}}$ (Definition B.1); $(\#)$ holds because $(1 - \delta(\ell))\mu^* + \delta(\ell)e$ is obviously $\delta(\ell)$-uniform and by definition of $\mathcal{E}$, see (C.24); and $(\#)$ holds when $\varepsilon_{\text{lvl}}(\tau_\ell)$ is small enough so that $\text{Cnf}_{\varepsilon_{\text{lvl}}}(M) = \text{Cnf}_0(M)$, i.e., when $\varepsilon_{\text{lvl}}(\tau_\ell) < \Delta^g(M)$, see Proposition 3 and Definition 11.

Solving $(\#) \ge (1 + \varepsilon_{\text{tst}}(T)) \log(T)$, we derive the definition of $m_0 \equiv m_{\varepsilon_0, T}$ in (C.44). We conclude that

$$
\begin{align*}
\mathbf{P} \left( \sum_{\ell=m_0+1}^{T-1} \mathbf{1} \left( \begin{array}{l} S_{\tau_\ell} \in \mathcal{S}(\mathcal{Z}^{**}(M)) \\ \tau_\ell \notin \mathcal{T}^\pm \end{array} \right) > 0, \mathcal{E} \right) & \\
&\le \exp \left( - \frac{|\mathcal{Z}|^2 \varepsilon_0 m_0}{\beta(m_0)^2} \right) + \exp(-\text{poly}(\varepsilon_{\text{unif}}(m_0))m_0 + \kappa_{\bar{\varepsilon}}) \\
&\le \exp \left( - \min \left\{ \frac{|\mathcal{Z}|^2 \varepsilon_0 m_0}{\beta(m_0)^2}, \text{poly}(\varepsilon_{\text{unif}}(m_0))m_0 \right\} + \kappa_{\bar{\varepsilon}} + \log(2) \right) \\
&\overset{(\dagger)}{\le} \exp(-\text{poly}(\varepsilon_{\text{unif}}(m_0))m_0 + \kappa_{\bar{\varepsilon}} + \beta' + \log(2))
\end{align*}
$$

where $(\dagger)$ follows from the observation that $\beta(\ell)^{-1} = \text{poly}(\varepsilon_{\text{unif}}(\ell))$ is a polynomial of degree $|S|$ while $\text{poly}(-)$ introduced by Lemma C.10 is of degree $4|S|$, so that $\text{poly}(\varepsilon_{\text{unif}}(m_0))m_0 \le |\mathcal{Z}|^2\varepsilon_0 \cdot \beta(m_0)^{-2}m_0$ for $m_0 > \kappa'$ where $\kappa' \in \mathbf{R}_+$ is some constant. This proves the claim. $\blacksquare$

Following (C.46) from Lemma C.17, we know that exploration GLR tests (16) do not provoke exploration phases after $m_{\varepsilon_0, T}$ exploration phases—under the good event $\mathcal{E}$ given in (C.24) at least. Beyond that threshold, exploration is mostly due to co-exploration and
the number of induced phases can be controlled using Lemma C.20, concluding the proof of Lemma C.16.

**Proof of Lemma C.16** Let $m \ge m_0 \equiv m_{\varepsilon_0,T}$ be as given in (C.44), and assume that $T \ge 1$ is large enough so that $m_{\varepsilon_0,T} \ge \sqrt{\varepsilon_0} \log(T) + \alpha_{\bar{\varepsilon}}(\varepsilon_0)$ where $\alpha_{\bar{\varepsilon}}(\varepsilon_0)$ is given by Lemma C.13. Let $\alpha > 0$ the constant given by Lemma C.20. We have

$$ 
\begin{aligned}
& \mathbf{P}\left(T^{-} \geq m + \alpha \varepsilon_{\text{unif}}(T^{-})^{-2|S|} \log \log(T), \mathcal{E}\right) \\
& \stackrel{(\dagger)}{\leq} \mathbf{P}\left(T^{-} \geq m + \alpha \varepsilon_{\text{unif}}(T^{-})^{-2|S|}\left(\log \log(T) + \sum_{\ell=m_0+1}^{T^{-}} \mathbf{1}\left(\begin{array}{l} S_{\tau_{\ell}} \in \mathcal{S}(\mathcal{Z}^{**}(M)) \\ \tau_{\ell} \notin \mathcal{T}^{\pm} \end{array}\right)\right), \mathcal{E}'\right) \\
& \qquad + \mathbf{P}\left(\sum_{\ell=m_0+1}^{T^{-}} \mathbf{1}\left(\begin{array}{l} S_{\tau_{\ell}} \in \mathcal{S}(\mathcal{Z}^{**}(M)) \\ \tau_{\ell} \notin \mathcal{T}^{\pm} \end{array}\right) > 0, \mathcal{E}\right) \\
& \stackrel{(\ddagger)}{\leq} \exp \left(-\beta_1 \varepsilon_{\text{unif}}(m)^{4|S|}(m - m_0)\right) + \exp \left(-\text{poly}(\varepsilon_{\text{unif}}(m_{\varepsilon_0,T}))m_{\varepsilon_0,T}\right) \quad (C.47)
\end{aligned}
$$

where $(\dagger)$ introduces $\mathcal{E}' := (\forall \ell \ge m_0, \mathcal{Z}_{\varepsilon_{\ell} \text{ level}}^{**}(\hat{M}_{\tau_{\ell}}) = \mathcal{Z}^{**}(M))$ where $\varepsilon_{\ell \text{ level}}''$ is the $T$-truncated leveling regularizer (C.21), and $(\dagger)$ uses that $\mathcal{E} \subseteq \mathcal{E}'$; and $(\ddagger)$ bounds the first term of $(\dagger)$ using the lemma on co-exploration travels (Lemma C.20) and the second term using (C.46) from Lemma C.17, where $\text{poly}(-)$ is a polynomial of degree $4|S|$. In the following, we we assume that $\text{poly}(x) \le \beta_1 x^{4|S|}$ up to decreasing $\text{poly}(-)$.

We set $m_T := (1 + \log(T)^{-1/2})m_{\varepsilon_0,T}$, so that $m_T - m_{\varepsilon_0,T} = \log(T)^{-1/2}m_{\varepsilon_0,T}$.

Setting $m \equiv m_T$ in (C.47), we find

$$ 
\begin{aligned}
& \mathbf{P}\left(T^{-} \geq m_{\varepsilon_0,T} + \frac{m_{\varepsilon_0,T}}{\sqrt{\log(T)}} + \varepsilon_{\text{unif}}(T^{-})^{-2|S|} \log \log(T), \mathcal{E}\right) \\
& \leq \exp\left(-\text{poly}(\varepsilon_{\text{unif}}(m_T))(m - m_{\varepsilon_0,T}) + \kappa_{\bar{\varepsilon}}\right) + \exp\left(-\text{poly}(\varepsilon_{\text{unif}}(m_{\varepsilon_0,T}))m_{\varepsilon_0,T} + \kappa'_{\bar{\varepsilon}}\right) \\
& \stackrel{(\dagger)}{\leq} \exp\left(-\omega\left(\log \log(T)^{-4|S|} \sqrt{\log(T)}\right) + \exp\left(-\omega\left(\log \log(T)^{-4|S|} \log(T)\right)\right)\right) \\
& \stackrel{(\ddagger)}{\leq} \exp\left(-\omega\left(\log(T)^{\frac{1}{2}-\alpha}\right)\right)
\end{aligned}
$$

where $(\dagger)$ uses that $m_{\varepsilon_0,T} = \Theta(\log(T))$, that $m_T - m_{\varepsilon_0,T} = \Theta(\sqrt{\log(T)})$ and that $\varepsilon_{\text{unif}}(m) = \omega(\log(m)^{-1})$, see Assumption 6 (A4); and $(\ddagger)$ holds when $T \to \infty$ for all (fixed) $\alpha > 0$.

We conclude by simplifying the bound on $T^-$. Assume that $T^- \le (1+\log(T)^{-1/2})m_{\varepsilon_0,T} + \varepsilon_{\text{unif}}(T^-)^{-2|S|} \log \log(T)$. Because $\varepsilon_{\text{unif}}(m)^{-2|S|} = o(\log(m))$ by Assumption 6 (A4), we have $\varepsilon_{\text{unif}}(T^-)^{-2|S|} \le \log(T^-)$ provided that $T^-$ is large enough, say $T^- \ge \kappa_{\bar{\varepsilon}}''$. It follows that

$$ 
\begin{aligned}
T^{-} & \le \left(1 + \frac{1}{\sqrt{\log(T)}}\right) m_{\varepsilon_0,T} + \log(T^{-}) \log \log(T) + \kappa_{\bar{\varepsilon}}'' \\
& \stackrel{(\dagger)}{\le} \inf_{\delta \in (0,1)} \left\{ \frac{1}{1-\delta} \left( \left(1 + \frac{1}{\sqrt{\log(T)}}\right) m_{\varepsilon_0,T} + \kappa_{\bar{\varepsilon}}'' \right) + \left( \frac{\log \log(T)}{\delta} \right)^2 \right\}
\end{aligned}
$$
$$
\begin{align*}
\stackrel{(\ddagger)}{\le} \inf_{\delta \in (0, \frac{1}{2})} & \left\{ (1 + 2\delta) \left( \left( 1 + \frac{1}{\sqrt{\log(T)}} \right) m_{\varepsilon_0, T} + \kappa_{\bar{\varepsilon}}'' \right) + \left( \frac{\log \log(T)}{\delta} \right)^2 \right\} \\
\stackrel{(\S)}{\le} & \left( 1 + \frac{2}{\log(T)^{1/4}} \right) \left( 1 + \frac{1}{\sqrt{\log(T)}} \right) m_{\varepsilon_0, T} + \log \log(T)^2 \sqrt{\log(T)} + 2\kappa_{\bar{\varepsilon}}'' \\
\le & \left( 1 + \frac{5}{\log(T)^{1/4}} \right) m_{\varepsilon_0, T} + \log \log(T)^2 \sqrt{\log(T)} + 2\kappa_{\bar{\varepsilon}}''
\end{align*}
$$

where (†) uses that $\log(T^-) \log \log(T)/T^- \le \delta$ for $T^- \ge (\log \log(T)/\delta)^2$; (‡) follows from
$\frac{1}{1-\delta} \le 1+2\delta$ for $\delta < \frac{1}{2}$; and (§) sets $\delta = \log(T)^{-1/4}$. This proves the claim. $\blacksquare$

### C.3.7 PART V: FIRST ORDER FAILURE AND THE SKELETON EXPLORATION BARRIER

If either the trigger event $\mathcal{E}$ fails, or if $N_{\tau_\ell}^-(z)$ drastically deviates from its expected value $\ell\mu^*(z)$, the number of exploration phases can be as big as $T$ in the worst scenario. Combining Lemmas C.11, C.13 and C.16, this can happen with probability of order $\exp(-\log(T)^{1-\alpha})$ for some $\alpha > 0$. In expectation, the associated error becomes $T \cdot \exp(-\log(T)^\alpha)$, that is $\Omega(T^{1-\beta})$ for all $\beta > 0$. One cannot afford an error term that large—bounding the number of exploration phases by $T$ when our good events fail is too rough.

That is why, in this paragraph, we show that with **very** high probability, exploration cannot go beyond a threshold of order $\log(T)^3$ (Lemma C.18 and Corollary C.19): This is the **heavy** exploration barrier motivated earlier. We start with a complete (but heavy) statement in Lemma C.18 that we simplify in Corollary C.19 under assumptions on the hyperparameter $\bar{\epsilon}$. The idea behind the exploration barrier (Lemma C.18) is that after enough exploration times, all pairs must enter the skeleton because exploration is slightly uniformized. Once that all pairs are in the skeleton, the GLR exploration test (16) never triggers exploration phases, so that all further exploration times are exclusively produced by the co-exploration mechanism. Because all the empirical data concentrates quickly on the skeleton, all the conditions are realized so that co-exploration induces very few exploration times, see Lemma C.20.

Therefore, the exploration barrier consists in showing that exploration naturally stops for good once all pairs enter in the skeleton, and quantifying how quickly this happens.

**Lemma C.18.** Let $T^- := \sup\{\ell \ge 1 : \tau_\ell \le T-1\}$ the (random) number of exploration times prior to $T \ge 1$. There exist constants $\alpha, \beta > 0$ and a function $\psi \equiv \psi_{\bar{\epsilon}} : \mathbf{N} \to \mathbf{R}_+$ such that

$$
\mathbf{P} \left( T^{-} \geq 2 \log^{3}(T) + \alpha \varepsilon_{\text{unif}} (T^{-})^{-2|S|} \log \log(T) \right) \leq \exp(-\psi(T))
$$

$$
\text{where } \psi(T) \sim -\beta \min\left\{\varepsilon_{\text{unif}}(4 \log^3(T))^{4|S|} \log^3(T), \varepsilon_{\text{lvl}}(T)^2 \log^2(T)\right\} \text{ when } T \to \infty.
$$

Under Assumption 6, the dominant term in the condition on $T^-$ is $T^- \ge 2 \log^3(T)$ and the dominant term in the error probability is $\log^2(T)\varepsilon_{\text{lvl}}(T)^{-2}$. This provides the alternative version below (Corollary C.19) that is easier to carry out.

**Corollary C.19 (Skeleton barrier).** Under Assumption 6, there exists a constant $\alpha > 0$ such that for all $\delta > 0$, we have

$$
\mathbf{P}\left(\sum_{t=1}^{T-1} \mathbf{1}(t \in \mathcal{T}^-) \ge \alpha \log^3(T)\right) \le o\left(\exp\left(-\log^{2-\delta}(T)\right)\right) = o(T^{-2}) \quad \text{when } T \to \infty. \quad (\text{C.48})
$$
**Proof of Lemma C.18** Let $(\tau_\ell)$ be the stopping-time enumeration of $\mathcal{T}^-$, i.e., $\tau_1 := \inf \mathcal{T}^-$ and $\tau_{\ell+1} := \inf\{t > \tau_\ell : t \in \mathcal{T}^-\}$. Recall that $\bar{\varepsilon}'$ denotes the floored regularizer (17) and that $\bar{\varepsilon}''$ denotes the $T$-truncated regularizer (C.21). Recall that $\varepsilon''_{\text{unif}}(\ell) = \varepsilon'_{\text{unif}}(\ell) \ge \varepsilon_{\text{unif}}(\ell)$, $\varepsilon''_{\text{conv}}(\ell) = \varepsilon'_{\text{conv}}(\ell) \ge \varepsilon_{\text{conv}}(\ell)$ and $\varepsilon''_{\text{tst}}(t) = \varepsilon'_{\text{tst}}(t) = \varepsilon_{\text{tst}}(t)$. Let $m_0 \ge 1$ to be tuned later and introduce the events

$$ \begin{aligned} \mathcal{E}_{m_0} &:= (\forall \ell \ge m_0, \mathcal{Z}_{\varepsilon \text{lvl}''(\tau_\ell)}^{**}(\hat{M}_{\tau_\ell}) \ne \mathcal{Z}^{**}(M)), \\ \mathcal{E}'_{m_0} &:= (\forall \ell \ge m_0, \forall z \in \mathcal{Z}, N_{\tau_\ell}(z) \ge \log^2(T)) \end{aligned} $$

and introduce the short-hand random variables

$$ \begin{aligned} T^{-} &:= \sum_{t=1}^{T-1} \mathbf{1}(t \in \mathcal{T}^{-}) = \sup\{\ell \ge 1 : \tau_{\ell} \le T-1\}, \\ \psi_1(m_0, T) &:= 2m_0 + \alpha_1 \varepsilon_{\text{unif}}(T^{-})^{-2|S|} \log \log(T), \\ \psi_2(m_0, T) &:= 2m_0 + \alpha_1 \varepsilon_{\text{unif}}(T^{-})^{-2|S|} \left( \log \log(T) + \sum_{\ell=2m_0+1}^{T^{-}} \mathbf{1}\left( \begin{array}{l} S_{\tau_{\ell}} \in \mathcal{S}(\mathcal{Z}^{**}(M)) \\ \tau_{\ell} \notin \mathcal{T}^{\pm} \end{array} \right) \right) \end{aligned} $$

where $\alpha_1$ is the alias for the constant $\alpha$ that appears in the co-exploration travel lemma (Lemma C.20). We have

$$ \begin{aligned} \mathbf{P}(T^{-} \ge 2m_0 + \psi_1(m_0, T)) &\le \mathbf{P}\left( \begin{array}{l} T^{-} \ge 2m_0 + \psi_1(m_0, T), \\ \mathcal{E}_{m_0}, \mathcal{E}'_{m_0} \end{array} \right) + \mathbf{P}((\mathcal{E}_{m_0})^c, \mathcal{E}'_{m_0}) + \mathbf{P}((\mathcal{E}'_{m_0})^c) \\ &\stackrel{(\dagger)}{\le} \mathbf{P}\left( \begin{array}{l} T^{-} \ge 2m_0 + \psi_1(m_0, T), \\ \mathcal{E}_{m_0}, \mathcal{E}'_{m_0} \end{array} \right) + \mathbf{P}((\mathcal{E}_{m_0})^c, \mathcal{E}'_{m_0}) + \mathbf{P}((\mathcal{E}'_{m_0})^c) \\ &\stackrel{(\ddagger)}{\le} \exp\left( \begin{array}{l} -\beta_1 \varepsilon_{\text{unif}}(2m_0)^{4|S|} m_0 \\ +2 \log(m_0) + \kappa_{\bar{\varepsilon}} \end{array} \right) + \mathbf{P}((\mathcal{E}_{m_0})^c, \mathcal{E}'_{m_0}) + \mathbf{P}((\mathcal{E}'_{m_0})^c) \end{aligned} \quad (C.49) $$

where $(\dagger)$ follows from the observation that under $\mathcal{E}'_{m_0}$ and for $t \le T-1$, all pairs are within the skeleton hence no GLR exploration test (16) may trigger an exploration phase, so that $\psi_1(m_0, T) = \psi_2(m_0, T)$; and $(\ddagger)$ follows by the co-exploration lemma (Lemma C.20) and $\beta_1, \kappa_{\bar{\varepsilon}}$ are aliases for the constants $\beta, \kappa_{\bar{\varepsilon}}$ that appear in that result.

This leaves to bound $\mathbf{P}((\mathcal{E}_{m_0})^c, \mathcal{E}'_{m_0})$ and $\mathbf{P}((\mathcal{E}'_{m_0})^c)$.

Starting with $\mathbf{P}((\mathcal{E}_{m_0})^c, \mathcal{E}'_{m_0})$, we could use the trigger effect (Lemma C.11) but this is a bit of an overshoot—instead, we specialize the argument of the proof of Lemma C.11 on the fly. By Proposition 3, the condition “$\mathcal{Z}^{**}_{\varepsilon \text{lvl}''}(\hat{M}_{\tau_\ell}) = \mathcal{Z}^{**}(M)$” is met as soon as

$$ \alpha_2 \| \hat{M}_{\tau_\ell} - M \|^* < \frac{1}{3} \varepsilon_{\text{lvl}''}(\tau_\ell) \le \frac{1}{3} \varepsilon_{\text{lvl}''}(\ell) < \Delta^g(M) \quad (C.50) $$

where $\alpha_2$ is an alias for the constant $C(M)$ that appears in Proposition 3. To convert $\|\hat{M}_{\tau_\ell} - M\|^*$ into $\|\hat{M}_{\tau_\ell} - M\|$, we rely on Lemma C.24, that provides the additional condition “$\hat{M}_{\tau_\ell} \sim M$” that is met as soon as

$$ \| \hat{M}_{\tau_\ell} - M \| < \operatorname{dmin}(M) =: \alpha_3. \quad (C.51) $$
Now, the equations (C.50) and (C.51) can be combined into a single one, of the form $\alpha_4 \|\hat{M}_{\tau_\ell} - M\| < \frac{1}{3}\varepsilon_{\text{lvl}}''(\tau_\ell)$ together with $\varepsilon_{\text{lvl}}'(\ell) < \Delta^g(M)$. The second condition is about $\ell$ and $T$ being large enough because $\varepsilon_{\text{lvl}}(\ell) \to 0$ when $\ell \to \infty$. All together, we have

$$
\begin{align}
\mathbf{P}((\mathcal{E}_{m_0})^c, \mathcal{E}'_{m_0}) &\le \mathbf{P}\left(\exists \ell \ge m_0 : \|\hat{M}_{\tau_\ell} - M\| \ge \frac{1}{3\alpha_4}\varepsilon_{\text{lvl}}''(\tau_\ell) \text{ and } \forall z \in \mathcal{Z}, N_{\tau_\ell}(z) \ge \log^2(T)\right) \nonumber \\
&\le \mathbf{P}\left(\exists \ell \ge m_0 : \|\hat{M}_{\tau_\ell} - M\| \ge \frac{1}{3\alpha_4}\varepsilon_{\text{lvl}}(T) \text{ and } \forall z \in \mathcal{Z}, N_{\tau_\ell}(z) \ge \log^2(T)\right) \nonumber \\
&\le 2|\mathcal{Z}| \exp\left(-18\alpha_4^2\varepsilon_{\text{lvl}}(T)^2 \log^2(T) + \frac{1}{2}\log(1 + \log^2(T)) + |\mathcal{S}|\log(2)\right) \nonumber \\
&= \exp\left(-18\alpha_4^2\varepsilon_{\text{lvl}}(T)^2 \log^2(T) + \mathcal{O}(\log \log(T))\right) \tag{C.52}
\end{align}
$$

where $(\dagger)$ holds when $\varepsilon_{\text{lvl}}(m_0) < \Delta^g(M)$ and $T \ge m_0$, i.e., when $T$ is large enough by Assumption 6 (A0); $(\ddagger)$ holds because $\varepsilon_{\text{lvl}}$ is decreasing; and $(\S)$ follows from concentration results (Corollary C.23).

We continue with $\mathbf{P}((\mathcal{E}'_{m_0})^c)$. Assume that $m_0$ is large enough so that, for all $\ell \ge m_0$, we have $\alpha_5\varepsilon_{\text{unif}}(\ell)^{|S|}\ell \ge \log^2(T)$ where $\alpha_5$ is an alias for the constant $\alpha$ appearing in Lemma C.10. Because $\varepsilon_{\text{unif}}(\ell)^{|S|}\ell = \omega(\ell^{1-\eta})$ for all $\eta > 0$ when $\ell \to \infty$ by Assumption 6 (A4), we see that $m_0 \asymp \alpha_4^{-1}\log^2(T)$ is asymptotically the right threshold. In the sequel, set

$$m_0 := \log^3(T)$$

and consider that $T \to \infty$. For $T$ large, we have $\alpha_5\varepsilon_{\text{unif}}(\ell)^{|S|}\ell \ge \log^2(T)$ for all $\ell \ge m_0 \equiv \log^3(T)$. So, by Lemma C.10, we find

$$\mathbf{P}((\mathcal{E}'_{m_0})^c) \le \exp\left(-\text{poly}(\varepsilon_{\text{unif}}(m_0))m_0\right) = \exp\left(-\text{poly}(\varepsilon_{\text{unif}}(\log^3(T)))\log^3(T)\right) \quad (C.53)$$

where $\kappa_{\bar{\varepsilon}}$ is the constant $\kappa_{\bar{\varepsilon}}$ appearing in Lemma C.10 and $\text{poly}(-)$ is a polynomial of degree $4|S|$. So, setting $m_0 = \log^3(T)$, we conclude by combining (C.49), (C.52) and (C.53). $\blacksquare$

### C.3.8 PART VI: PUTTING EVERYTHING TOGETHER AND PROVING LEMMA C.9

We can finally conclude the proof. Let $m_{\varepsilon_0, T}$ the exploration threshold as given by (C.44). Introduce

$$\beta_1(T) := m_{\varepsilon_0, T} + \kappa_{\bar{\varepsilon}} \log^4(T) \quad \text{and} \quad \beta_2(T) := \alpha \log^3(T) \quad (C.54)$$

where $\kappa_{\bar{\varepsilon}}$ is the constant that appears in the high probability exploration barrier (Lemma C.16) and $\alpha$ is the constant that appears in the skeleton exploration barrier (first order failure, see Corollary C.19). Introduce

$$
\begin{align}
\mathcal{E}_0 &:= (\forall \ell \ge \beta_1(T), \forall z \in \mathcal{Z}, N_{\tau_\ell}^{-}(z) \le (\mu^*(z) + 8|\mathcal{Z}|\sqrt{\varepsilon_0})\ell), \tag{C.55} \\
\mathcal{E}_1 &:= (T^- < \beta_1(T)) \quad \text{and} \quad \mathcal{E}_2 := (T^- < \beta_2(T)). \nonumber
\end{align}
$$

The event $\mathcal{E}_1^c$ corresponds to the first order failure and $\mathcal{E}_2^c$ corresponds to the second order failure in Figure 6. Recall that $\mathcal{E} \equiv \mathcal{E}_{\varepsilon_0, T}$ is the trigger event, see (C.24). We have

$$\mathbf{E}[N_T^-(z)]$$
$$
\begin{align*}
\stackrel{(\dagger)}{\le} \mathbf{E}[(\mu^*(z) + 8|\mathcal{Z}|\sqrt{\varepsilon_0})\beta_1(T) \cdot \mathbf{1}(\mathcal{E}_0 \cap \mathcal{E}_1 \cap \mathcal{E}) + \beta_2(T) \cdot \mathbf{1}(\mathcal{E}_0^c \cup \mathcal{E}_1^c \cup \mathcal{E}^c)\mathbf{1}(\mathcal{E}_2) + T \cdot \mathbf{1}(\mathcal{E}_2^c)] \\
\le (\mu^*(z) + 8|\mathcal{Z}|\sqrt{\varepsilon_0})\beta_1(T) + \beta_2(T)(\mathbf{P}(\mathcal{E}_0^c, \mathcal{E}) + \mathbf{P}(\mathcal{E}_1^c, \mathcal{E}) + \mathbf{P}(\mathcal{E}^c)) + T\mathbf{P}(\mathcal{E}_2^c) \\
\stackrel{(\ddagger)}{=} (\mu^*(z) + 8|\mathcal{Z}|\sqrt{\varepsilon_0})\beta_1(T) + \mathcal{O}\left(\log^3(T)e^{-\Omega(\sqrt{\log(T)})}\right) + \mathcal{O}\left(\log^3(T)e^{-\Omega(\log(T)^{1/4})}\right) \\
+ \mathcal{O}\left(\log^3(T)e^{-\Omega(\sqrt{\log(T)})}\right) + \mathcal{O}\left(Te^{-\Omega(\log(T)^{3/2})}\right) \\
= (\mu^*(z) + 8|\mathcal{Z}|\sqrt{\varepsilon_0})\beta_1(T) + \mathcal{o}(1)
\end{align*}
$$

where (†) follows from the observation that $N_T^-(z) = N_{\tau_{T-}}^-(z)$ and $N_T^-(z) \le T^-$ a.s.; and (†)
bounds the first error using (C.32) from Lemma C.13, the second error using (C.45) from
Lemma C.16 (exploration barrier), the third error using Corollary C.12 (trigger effect), and
the fourth error using Corollary C.19 (skeleton exploration barrier). Unfolding the definition
of $m_{\varepsilon_0,T}$, see (C.44), we obtain

$$
\mathbf{E}[N_T^-(z)] \le \frac{(\mu^*(z) + 8|\mathcal{Z}|\sqrt{\varepsilon_0})(1 + \varepsilon_{\text{tst}}(T)) \log(T)}{\left(1 - \frac{8|\mathcal{Z}|\sqrt{\varepsilon_0}}{\min(\mu^*)}\right)(C(\mu^*, M) - \varepsilon_0)} + \mathcal{O}\left(\log^{\frac{3}{4}}(T)\right) \quad \text{when } T \to \infty,
$$

where $\mu^*$ is the central optimal probability exploration measure of $M$ (Definition B.3).
Letting $T \to \infty$ then taking $\varepsilon_0$ vanishing, we conclude that

$$
\limsup_{T \to \infty} \frac{\mathbf{E}[N_T^-(z)]}{\log(T)} \le \frac{\mu^*(z)}{C(\mu^*, M)}.
$$

This concludes the proof of Lemma C.9.

C.3.9 AUXILIARY: CO-EXPLORATION TRAVELS

In this section, we provide an instrumentary result (Lemma C.20) to bound the number
of exploration phases triggered by co-exploration. In spirit, Lemma C.20 states that the
number of exploration phases triggered by co-exploration is of order log log(T).

Recall that $\tilde{\epsilon}''$ denotes the $T$-truncated regularizer, see (C.21).

**Lemma C.20.** Let $(\tau_\ell)$ be the stopping-time enumeration of $\mathcal{T}^-$, i.e., $\tau_1 := \inf \mathcal{T}^-$ and $\tau_{\ell+1} := \inf\{t > \tau_\ell : t \in \mathcal{T}^-\}$. Let $T^- := \sup\{\ell \ge 1 : \tau_\ell \le T-1\}$ be the number of exploration times prior to $T \ge 1$. There exist constants $\alpha, \beta, \kappa_\varepsilon > 0$ such that, for all $m_0$ and $T \ge 1$, introducing the event $\mathcal{E} \equiv \mathcal{E}_{m_0} := (\forall\ell \ge m_0, \mathcal{Z}_{\varepsilon\text{lvl}''}^{**}(\hat{M}_{\tau_\ell}) = \mathcal{Z}^{**}(M))$, for all $m \ge m_0$, we have

$$
\mathbf{P} \left( T^{-} \ge m + \alpha \varepsilon_{\text{unif}} (T^{-})^{-2|S|} \left( \log \log(T) + \sum_{\ell=m_0+1}^{T^{-}} \mathbf{1} \left( \begin{array}{l} S_{\tau_{\ell}} \in \mathcal{S}(\mathcal{Z}^{**}(M)) \\ \tau_{\ell} \notin \mathcal{T}^{\pm} \end{array} \right) \right), \mathcal{E} \right) \quad (\text{C.56}) \\
\le \exp \left( -\beta \varepsilon_{\text{unif}} (m)^{4|S|} (m - m_0) + \kappa_{\varepsilon} \right) \quad \text{when } m \to \infty.
$$

**Interpretation of Lemma C.20.** The statement of Lemma C.20 reads as follows: $\mathcal{E}$ is a good event, stating that beyond the exploration threshold $m_0$, the co-exploration structure is correct, with $\mathcal{Z}_{\varepsilon\text{lvl}''}^{**}(\hat{M}) = \mathcal{Z}^{**}(M)$. Then, Equation (C.56) states that beyond the
threshold $m_0$ and under $\mathcal{E}$, exploration times are due to (I) co-exploration times for a total of $O(\log \log(T))$ induced exploration times; and (II) exploration GLR tests (16) that explicitly cause exploration phases (exploration times for which $\tau_\ell \notin T^\pm$ while $S_{\tau_\ell} \in S(\mathcal{Z}^{**}(M))$). Lemma C.20 is to be applied when (II) is unlikely to happen beyond $m_0$, i.e., when the exploration GLR test is very likely to claim that enough information has been gathered beyond the exploration threshold $m_0$. In such circumstances, Equation (C.56) essentially says that there are $O(\log \log(T))$ exploration times beyond $m_0$ under the good event $\mathcal{E}$.

**Proof** Fix $m_0 \ge 1$. Let $\mathcal{Z}_1, \dots, \mathcal{Z}_{c_0}$ be the communicating components of $\mathcal{Z}^{**}(M)$, that the algorithm guesses correctly on $\mathcal{E}$ by assumption. Let $c^{-}(t) := \min\{c : \min\{N_t(z) : z \in \mathcal{Z}_c\} = \min\{N_t(z) : z \in \mathcal{Z}^{**}(M)\}\}$ be the least visited component at time $t \ge 1$. We decompose $\{\tau_{m_0}, \tau_{m_0+1}, \dots\}$ into segments alternating between least visited components. Specifically, let $(j(i))_{i \ge 1}$ be the sequence given by

$$ 
\begin{aligned}
j(1) &:= m_0, \\
j(i+1) &:= \inf\{\ell > j(i) : S_{\tau_\ell} \in \mathcal{S}(\mathcal{Z}_{c^{-}(\tau_\ell)})\}. 
\end{aligned} 
\qquad (C.57) 
$$

We relate the number of exploration times in $\{\tau_{m_0}, \tau_{m_0+1}, \dots\}$ to $j(-)$ as follows.

(STEP 1) Denote $I(m) := \inf\{i : j(i) < m\}$ the pseudo-inverse of $j(-)$. For $m \ge 1$, let $\alpha_m := \operatorname{dmin}(p)^{|S|}\varepsilon_{\operatorname{unif}}(m)^{|S|}$ and $\beta_m := 1 + 2|S|\operatorname{dmin}(p)^{-|S|}\varepsilon_{\operatorname{unif}}(m)^{-|S|}$. For all $\delta \ge 1$, we have

$$ 
\begin{aligned}
\mathbf{P} \left( \exists m \ge m_0, (1 + \beta_m) I(m) \ge \alpha_m (m - m_0) - \beta_m \left( |\mathcal{Z}| |S| + 2 \sqrt{ (m - m_0) \log\left( \frac{1 + m - m_0}{\delta} \right) } \right), \mathcal{E} \right) \\
\le \delta.
\end{aligned} 
$$

**Proof** We use a technique that is similar to the proof of the uniform exploration lemma (Lemma C.10). Given $\eta > 0$, we consider the Markov decision process $M_\eta := (\mathcal{Z}, r, p_\eta)$ with kernel given by

$$ p_\eta(s, a) := (1 - \eta|\mathcal{A}(s)|)p(s, a) + \eta \sum_{a' \in \mathcal{A}(s)} p(s, a'). $$

The model $M_\eta$ is communicating and by construction, the execution of any $\eta$-uniform policy $\pi$ on $M$ can be seen as the execution of a randomized policy $\pi_\eta$ on $M_\eta$, in the sense that $\mathbf{E}^{M_\eta, \pi}[-] = \mathbf{E}^{M, \pi_\eta}[-]$.

Given $\mathcal{Z}^i \equiv \mathcal{Z}_{c^{-}(\tau_{j(i)})}$, introduce the reward function $f_i(z) := \mathbf{1}(z \in \mathcal{Z}^i)$. Consider the model $M_\eta^{-f_i} = (\mathcal{Z}, -f_i, p_\eta)$ with kernel $p_\eta$ and deterministic reward function $-f_i$ and introduce $g_\eta^{-f_i}$, $b_\eta^{-f_i}$ and $\Delta_\eta^{-f_i}$ the associated optimal gain, bias an gap functions of $M_\eta^{-f_i}$. Because $M_\eta^{-f_i}$ is communicating, we have $\operatorname{sp}(g_\eta^{-f_i}) = 0$. Let $\pi_\eta^*$ be a deterministic bias optimal policy of $M_\eta^{-f_i}$. By construction, $\pi_\eta^*$ corresponds to an $\eta$-uniform policy of $M$ for which all pairs are recurrent. By Lemma A.7, we have $\min(g_\eta^{-f_n}) = \max(g_\eta^{-f_i}) \le -\operatorname{dmin}(p)^{|S|}\eta^{|S|}$. Consider the gaps in $M$, given by

$$ \Delta^{-f_i}(s, a) := g_\eta^{-f_i}(s) + b_\eta^{-f_i}(s) + f(s, a) - p(s, a)b_\eta^{-f_i}. \qquad (C.58) $$
Note that we also have $\max\{\text{sp}(b_{\eta}^{-f_i}), \|\Delta_{\eta}^{-f_i}\|_{\infty}\} \le \beta_{\eta} := 1+2 \min(p)^{-|S|} \eta^{-|S|}$ by Lemma A.7 again. Following from the Bellman equations of $M_{\eta}^{-f_i}$, check that every $\eta$-uniform policy $\pi$ satisfies

$$ \sum_{a \in \mathcal{A}(s)} \pi_{\eta}(a|s) \Delta_{\eta}^{-f_i}(s, a) = \sum_{a \in \mathcal{A}(s)} \pi(a|s) \Delta^{-f_i}(s, a) \ge 0 \quad (C.59) $$

where $\pi_{\eta}$ is the randomized policy induced by $\pi$ (i.e., bisimulating $\pi$) in $M_{\eta}$.

Let $m \ge m_0$ and set $\eta := \varepsilon_{\text{unif}}(m)$. For conciseness, let $j'(i) := \min\{j(i), m\}$. We have

$$ \begin{aligned} I(m) = \sum_{i=1}^{I(m)} 1 &\stackrel{(\dagger)}{=} \sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} \mathbf{1}(S_{\tau_{\ell}} \in \mathcal{S}(\mathcal{Z}_{c^{-}(\tau_{j(i)})})) \\ &\stackrel{(\ddagger)}{=} \sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} (-g_{\eta}^{-f_i}(S_{\tau_{\ell}}) + (p(Z_{\tau_{\ell}}) - e_{S_{\tau_{\ell}}})b_{\eta}^{-f_i} + \Delta^{-f_i}(Z_{\tau_{\ell}})) \\ &\ge \alpha_m(m - m_0) + \underbrace{\sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} (p(Z_{\tau_{\ell}}) - e_{S_{\tau_{\ell}}})b_{\eta}^{-f_i}}_{A_1} + \underbrace{\sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} \Delta^{-f_i}(Z_{\tau_{\ell}})}_{A_2} \end{aligned} $$

where $(\dagger)$ follows by definition of $j(i+1)$, see (C.57); and $(\ddagger)$ follows by definition of $\Delta^{-f_i}$, see (C.58). We control the error terms as follows, starting with $A_1$. We have

$$ \begin{aligned} A_1 = & \sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} (e_{S_{\tau_{\ell}+1}} - e_{S_{\tau_{\ell}}}) b_{\eta}^{-f_i} + \sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} (p(Z_{\tau_{\ell}+1}) - e_{S_{\tau_{\ell}+1}}) b_{\eta}^{-f_i} \\ & \stackrel{(\dagger)}{\ge} -\beta_m(I(m) + |\mathcal{Z}||S|) + \sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} (p(Z_{\tau_{\ell}+1}) - e_{S_{\tau_{\ell}+1}}) b_{\eta}^{-f_i} \end{aligned} $$

where $(\dagger)$ follows from the observation that for $\ell \in \{j(i), \dots, j'(i+1)-1\}$, we have $\tau_{\ell+1} = \tau_{\ell}+1$ unless $\ell \in \mathcal{T}^!$ is a panic time—and by bounding the number of panic times by $|\mathcal{Z}||S|$, the maximum number of times a new transition is discovered, see Lemma C.21. The remaining right-hand term is a martingale that we leave for later.

We continue with $A_2$. We have

$$ \begin{aligned} A_2 := & \sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} \Delta^{-f_i}(Z_{\tau_{\ell}}) \\ = & \sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} \sum_{a \in \mathcal{A}(S_{\tau_{\ell}})} (\pi_{\tau_{\ell}}^{-}(a|S_{\tau_{\ell}})\Delta^{-f_i}(S_{\tau_{\ell}}, a) + (\mathbf{1}(A_{\tau_{\ell}} = a) - \pi_{\tau_{\ell}}^{-}(a|S_{\tau_{\ell}}))\Delta^{-f_i}(S_{\tau_{\ell}}, a)) \\ \stackrel{(\dagger)}{\ge} & \sum_{i=1}^{I(m)} \sum_{\ell=j(i)}^{j'(i+1)-1} \sum_{a \in \mathcal{A}(S_{\tau_{\ell}})} (\mathbf{1}(A_{\tau_{\ell}} = a) - \pi_{\tau_{\ell}}^{-}(a|S_{\tau_{\ell}}))\Delta^{-f_i}(S_{\tau_{\ell}}, a) \end{aligned} $$

where $(\dagger)$ follows from the observation that $\pi_{\tau_{\ell}}^{-}$ is $\eta$-randomized (since $\ell \le m$) and from (C.59). We conclude that $A_1$ and $A_2$ both involve martingales obtained as the sum of $m - m_0$
martingale differences whose terms have span at most $\beta_m$. So, by a time-uniform Azuma-Hoeffding's inequality (Lemma C.25), we find that with probability $1 - \delta$ and uniformly for $m \ge m_0$, we have

$$ (1 + \beta_m)I(m) \ge \alpha_m(m - m_0) - \beta_m \left( |\mathcal{Z}| |\mathcal{S}| + 2\sqrt{(m - m_0) \log\left(\frac{1 + m - m_0}{\delta}\right)} \right). $$

This proves the claim. $\square$

(STEP 2) For short, denote $I(m) := \inf\{i: j(i) < m\}$ the pseudo-inverse of $j(-)$. There exist constants $\alpha, \alpha', \kappa_{\bar{\epsilon}} > 0$ such that, for all $m_0$, we have

$$ \begin{aligned} & \mathbf{P}(\exists m' \ge m, I(m') > \alpha \varepsilon_{\text{unif}}(m')^{2|\mathcal{S}|}(m' - m_0), \mathcal{E}) \\ & \le \exp(-\alpha' \varepsilon_{\text{unif}}(m)^{4|\mathcal{S}|}(m - m_0) + 2 \log(m_0) + \kappa_{\bar{\epsilon}}). \end{aligned} \quad (C.60) $$

**Proof** We continue from the result of (STEP 1). Recall that $\alpha_m := \text{dmin}(p)^{|\mathcal{S}|}\varepsilon_{\text{unif}}(m)^{|\mathcal{S}|}$ and $\beta_m := 1 + 2|\mathcal{S}|\text{dmin}(p)^{-|\mathcal{S}|}\varepsilon_{\text{unif}}(m)^{-|\mathcal{S}|}$. We are to solve the equation

$$ \alpha_m \cdot (m - m_0) > 4\beta_m \sqrt{(m - m_0) \log\left(\frac{1 + m - m_0}{\delta}\right)} \quad (C.61) $$

in $\delta$. We first decouple (C.61) as the pair of sufficient conditions

$$ (i) \quad \alpha_m \cdot (m - m_0) > 8\beta_m \sqrt{(m - m_0) \log(1 + m - m_0)}, \text{ and} $$

$$ (ii) \quad \alpha_m \cdot (m - m_0) > 8\beta_m \sqrt{(m - m_0) \log\left(\frac{1}{\delta}\right)}. $$

The first condition (i) is equivalent to

$$ \frac{m - m_0}{\log(1 + m - m_0)} \ge 64 \text{dmin}(p)^{-2|\mathcal{S}|} \varepsilon_{\text{unif}}(m)^{-2|\mathcal{S}|} \left(1 + 2|\mathcal{S}| \text{dmin}(p)^{-|\mathcal{S}|} \varepsilon_{\text{unif}}(m)^{-|\mathcal{S}|}\right)^2 \quad (C.62) $$

and using $\log(1+x) \le \sqrt{x}$, we deduce that there is some $c > 0$ such that (C.62) holds if $m - m_0 \ge c \varepsilon_{\text{unif}}(m)^{-8|\mathcal{S}|}$. As $\varepsilon_{\text{unif}}(m)^{-8|\mathcal{S}|} = o(\log(m))$ when $m \to \infty$ by Assumption 6 (A4), we have $\varepsilon_{\text{unif}}(m)^{-8|\mathcal{S}|} \le \log(m)/c$ provided that $m$ is large enough, say $m \ge \kappa_{\bar{\epsilon}}$. We obtain the sufficient condition $m - m_0 \ge \log(m)$ that is again satisfied provided that

$$ m - m_0 \ge 2 \log(m_0) \quad \text{and} \quad m - m_0 \ge 2 \log\left(1 + \frac{m - m_0}{m_0}\right). $$

The second is always satisfied provided that $m$ is large enough. We conclude that there is some $\kappa_{\bar{\epsilon}} \in \mathbf{R}_+$ such that (C.62) is satisfied as soon as $m \ge 2 \log(m_0) + \kappa_{\bar{\epsilon}}$.

The second condition (ii) solves as $\delta \ge \exp(-c(m - m_0)\varepsilon_{\text{unif}}(m)^{4|\mathcal{S}|})$ for some constant $c > 0$. We conclude by using that $\psi_m(x) = (x - m_0)\varepsilon_{\text{unif}}(x)^{4|\mathcal{S}|}$ is asymptotically increasing when $x \to \infty$, see Assumption 6 (A6): There exist constants $\alpha' \in (0, 1]$ and $\kappa_{\bar{\epsilon}} \in \mathbf{R}_+$ such that

$$ \mathbf{P}(\exists m' \ge m, I(m') \le \alpha \varepsilon_{\text{unif}}(m')^{2|\mathcal{S}|}(m' - m_0)) $$
$$
\begin{align*}
&\le \exp(-\mathbf{1}(m \ge 2 \log(m_0) + \kappa_{\bar{\epsilon}}) \cdot \alpha' \varepsilon_{\mathrm{unif}}(m)^{4|S|(m-m_0)}) \\
&\stackrel{(\dagger)}{\le} \exp(-\alpha' \varepsilon_{\mathrm{unif}}(m)^{4|S|(m-m_0)} + 2 \log(m_0) + \kappa_{\bar{\epsilon}})
\end{align*}
$$

where $\langle \dagger \rangle$ follows from $\alpha' \varepsilon_{\text{unif}}(m)^{4|S|} \le 1$. This proves the claim.

(STEP 3) Denote $I^{\pm}(m) := |\{i \le I(m) : \tau_{j(i)} \in \mathcal{T}^{\pm}\}|$. On $\mathcal{E}$, we have

<figure><img src="image_20.png" /></figure>

$$
I^{\pm}(m) \le c_0 + \frac{\log \log(T)}{\log(2)} \le |S| + 2 \log \log(T). \quad (C.63)
$$

**Proof** Let $c_t$ be the component of $S_t$ at time $t$, if any (if it exists, it has to be unique). For $c = 1, \dots, c_0$, further introduce

$$
L(t; c) := \log \min \{N_t(z) : z \in \mathcal{Z}_c\}
$$

the minimal visit count of component $c$ at time $t$. Note that under the event $\mathcal{E} := (\forall \ell \ge m, \mathcal{Z}_{\ell}^{**}(\hat{M}_{\tau_{\ell}}) = \mathcal{Z}^{**}(M))$ and by definition of $j(-)$, see (C.57), $c_{\tau_{j(i)}}$ is well-defined for $i \ge 2$ and $c \equiv c_{\tau_{j(i+1)}}$ is a least visited component of time $\tau_{j(i)}$. Under $\mathcal{E} \cap (\tau_{j(i+1)} \in \mathcal{T}^{\pm})$, all the time instants $t \in \{\tau_{j(i+1)-1} + 1, \tau_{j(i+1)-1} + 2, \dots, \tau_{j(i+1)-1}\}$ are exploitation times that play the uniform policy on $\mathcal{Z}_c$, and $\tau_{j(i+1)} \in \mathcal{T}^{\pm}$ means that $\mathcal{Z}_c$ is over-visited compared to other components of $\mathcal{Z}^{**}(M)$. Moreover, under $\mathcal{E}$, the algorithm cannot panic by running such a policy on $\mathcal{Z}_c$ because no transition discovery may ever lead to a state outside of $S(\mathcal{Z}_c)$. In other words, under $\mathcal{E} \cap (\tau_{j(i+1)} \in \mathcal{T}^{\pm})$, we have

$$
L(\tau_{j(i+1)}; c) > 2 \min_{c' \in \{1, \dots, c_0\}} L(\tau_{j(i+1)}; c') \ge 2 \min_{c' \in \{1, \dots, c_0\}} L(\tau_{j(i)}; c') = 2L(\tau_{j(i)}; c). \quad (C.64)
$$

From (C.64), we conclude that under $\mathcal{E}$, every time $\tau_{j(i+1)} \in \mathcal{T}^{\pm}$, the least visited component of time $\tau_{j(i)}$ has doubled its visited count by time $\tau_{j(i+1)}$. On $\mathcal{E}$, we have $\min_c L(\tau_m; c) \ge 2^{\lfloor I^{\pm}(m)/c_0 \rfloor-1}$. Moreover, for $\tau_m \le T$, we have $L(\tau_m; c) \le \log(T)$ for all $c = 1, \dots, c_0$. Solving in $I^{\pm}(m)$, we obtain the claim.

□

<figure><img src="image_21.png" /></figure>

Now, we conclude the proof of Lemma C.20 by combining (C.63) from (STEP 3) together with (C.60) from (STEP 2).

For $m \ge m_0$ and as $m \to \infty$, we have

$$
\begin{align*}
& \exp(-\beta \varepsilon_{\text{unif}}(m)^{4|S|}(m - m_0) + 2 \log(m_0) + \kappa_{\bar{\varepsilon}}) \\
& \stackrel{(\dagger)}{\ge} \mathbf{P} \left( \exists m' \ge m, m' \ge m_0 + \frac{1}{\alpha} \varepsilon_{\text{unif}}(m')^{-2|S|} I(m') \right) \\
& \stackrel{(\ddagger)}{\ge} \mathbf{P} \left( T^{-} \ge m + \frac{\varepsilon_{\text{unif}}(T^{-})^{-2|S|}}{\alpha} I(T^{-}) \right) \\
& \ge \mathbf{P} \left( T^{-} \ge m + \frac{\varepsilon_{\text{unif}}(T^{-})^{-2|S|}}{\alpha} \sum_{i=1}^{I(T^{-})} \left( \mathbf{1}(\tau_{j(i)} \in \mathcal{T}^{\pm}) + \mathbf{1}(\tau_{j(i)} \notin \mathcal{T}^{\pm}) \right), \mathcal{E} \right) \\
& \stackrel{(\S)}{\ge} \mathbf{P} \left( T^{-} \ge m + \frac{\varepsilon_{\text{unif}}(T^{-})^{-2|S|}}{\alpha} \left( |S| + 2 \log \log(T) + \sum_{i=1}^{I(T^{-})} \mathbf{1}(\tau_{j(i)} \notin \mathcal{T}^{\pm}) \right), \mathcal{E} \right)
\end{align*}
$$
$$ \stackrel{(\$)}{\ge} \mathbf{P} \left( T^{-} \ge m + \frac{\varepsilon_{\text{unif}}(T^{-})^{-2|S|}}{\alpha/2 \cdot |S|^{-1}} \left( \log \log(T) + \sum_{\ell=1}^{T^{-}} \mathbf{1} \left( \begin{array}{l} S_{\tau_{\ell}} \in \mathcal{S}(\mathcal{Z}^{**}(M)) \\ \tau_{\ell} \notin \mathcal{T}^{\pm} \end{array} \right) \right), \mathcal{E} \right) $$

where (†) follows from (STEP 2); (‡) instantiates $m' = T'$ and simplifies the expression with straight-forward algebra; (§) unfolds $I^{\pm}(m) = \sum_{j=1}^{I(m)} \mathbf{1}(\tau_{j(i)} \in \mathcal{T}^{\pm})$ then invokes (C.63) from (STEP 3); and ($\$)$ uses that by definition of $j(-)$, see (C.57), we have $S_{\tau_{j(i)}} \in \mathcal{S}(\mathcal{Z}^{**}(M))$ almost surely. This proves Lemma C.20. ■

## C.4 Amount of panic times

Bounding the amount of panic times is much easier.

**Lemma C.21.** We have $\sum_{t=1}^{T-1} \mathbf{1}(t \in \mathcal{T}^!) \le |\mathcal{Z}||\mathcal{S}|$ almost surely.

**Proof** By construction of the ECoE*, Algorithm 2 can only panic if it has discovered a transition $(S_t, A_t, S_{t+1})$ that it has never seen before. As $(S_t, A_t, S_{t+1})$ lives in the space $\mathcal{Z} \times \mathcal{S}$, we deduce that there is an injection $\mathcal{T}^! \to \mathcal{Z} \times \mathcal{S}$. So $|\mathcal{T}^!| \le |\mathcal{Z}||\mathcal{S}|$. ■

## C.5 Combining everything together and proving Theorem C.1

Now, Theorem C.1 is a direct consequence of Lemmas C.2, C.9 and C.21. Indeed, for $z \notin \mathcal{Z}^{**}(M)$ and applying Lemmas C.2, C.9 and C.21, we obtain

$$ \mathbf{E}[N_T(z)] = \mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1} \left( \begin{array}{l} Z_t = z \\ t \in \mathcal{T}^+ \end{array} \right) \right] + \mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1} \left( \begin{array}{l} Z_t = z \\ t \in \mathcal{T}^- \end{array} \right) \right] + \mathbf{E} \left[ \sum_{t=1}^{T-1} \mathbf{1} \left( \begin{array}{l} Z_t = z \\ t \in \mathcal{T}^! \end{array} \right) \right] \\ \le \frac{\mu^*(z) \log(T)}{C(\mu^*, M)} + O \left( \frac{1}{\varepsilon_{\text{lvl}}(T)^6} + \sum_{t=1}^{T-1} \exp \left( - \left( 1 + \frac{1}{2} \varepsilon_{\text{tst}}(t) \right) \log(t) \right) \right) + |\mathcal{Z}||\mathcal{S}| + o(\log(T)). $$

This proves Theorem C.1.

## C.6 Auxiliary: Adaptations of standard concentration results

In this paragraph, we adapt a few classical probability results (see Appendix C.7) into the versions that are used all along the proof of Theorem C.1.

**Lemma C.22.** Let $m \ge 1$ and $d \ge 2$. Fix $q$ a distribution on $\{1, \dots, d\}$ and denote $q^n$ the empirical distribution on $\{1, \dots, d\}$ obtained after $n$ i.i.d. samples of $q$. For every sequence $(\varepsilon_n) \in (\mathbf{R}_+^*)^N$, we have

$$ \mathbf{P}(\exists n \ge m : \|q^n - q\|_1 > \varepsilon_n) \le \sup_{n \ge m} \exp \left( -2n\varepsilon_n^2 + \frac{1}{2}\log(1+n) + d\log(2) \right). $$

**Proof** By Lemma C.26, we have

$$ \begin{aligned} \delta &\ge \mathbf{P} \left( \exists n \ge m, \|n(q^n - q)\|_1^2 \ge \frac{1}{4} n \left( 1 + \frac{1}{n} \right) \log \left( \frac{2^d \sqrt{1+n}}{\delta} \right) \right) \\ &\ge \mathbf{P} \left( \exists n \ge m, \|q^n - q\|_1^2 \ge \frac{1}{2n} \log \left( \frac{2^d \sqrt{1+n}}{\delta} \right) \right) \end{aligned} $$
$$ \stackrel{(\dagger)}{\geq} \mathbf{P} \left( \exists n \geq m, \|q^n - q\|_1^2 \geq \varepsilon_n^2 \right) $$

where $(\dagger)$ holds if $\frac{1}{2n} \log(2^d \sqrt{1+n}/\delta) \leq \varepsilon_n^2$ for all $n \geq m$. We conclude by solving in $\delta$. ■

**Corollary C.23** (Threshold concentration). Let $m \geq 1$ and $d \geq 2$. Fix $q$ a distribution on $\{1, \dots, d\}$ and denote $q^n$ the empirical distribution on $\{1, \dots, d\}$ obtained after $n$ i.i.d. samples of $q$. For all $\varepsilon > 0$, we have

$$ \mathbf{P}(\exists n \geq m : \|q^n - q\|_1 > \varepsilon) \leq \exp\left(-2m\varepsilon^2 + \frac{1}{2}\log(1+m) + d\log(2)\right). $$

**Proof** Starting from Lemma C.22, we introduce the function

$$ \varphi(n) := \exp\left(-2n\varepsilon^2 + \frac{1}{2}\log(1+n) + d\log(2)\right). $$

The function $\varphi$ is decreasing in $[\frac{1}{4\varepsilon^2} - 1, \infty)$ and satisfies $\varphi \geq 4$ on $[0, \frac{1}{4\varepsilon^2} - 1]$, so that we may set $\inf_{n \geq m} \varphi(n) = \varphi(m) = \exp(-2m\varepsilon^2 + \frac{1}{2}\log(1+m) + d\log(2))$. ■

**Lemma C.24** (Converting $\|-\|^*$ to $\|-\|$). Let $M \equiv (\mathcal{Z}, p, r)$ and $M' \equiv (\mathcal{Z}, p', r')$ be two Markov decision processes with $M' \ll M$. For all $z \in \mathcal{Z}$, if $\|M'(z) - M(z)\|^* < \min(M)$, then $\|M'(z) - M(z)\|^* = \|M'(z) - M(z)\|$.

**Proof** By definition, we have

$$ \begin{aligned} \|M'(z) - M(z)\|^* &= \|r'(z) - r(z)\|_{\infty}^* + \|p'(z) - p(z)\|_1^*, \text{ and} \\ \|M'(z) - M(z)\| &= \|r'(z) - r(z)\|_{\infty} + \|p'(z) - p(z)\|_1. \end{aligned} $$

By assumption, $M'(z) \ll M(z)$ so we just have to show that $M(z) \ll M'(z)$. Assume that $\|M'(z) - M(z)\| < \min(M)$. For kernels, we have

$$ \max_{s \in S} |p'(s|z) - p(s|z)| \leq \|p'(z) - p(z)\|_1 < \min(M) \leq \min(p(z)) $$

so $p'(s|z) > 0$ for all $s \in \text{supp}(p(z))$. So $p'(z) \gg p(z)$. With the same rationale, we show that $r'(z) \gg r(z)$ and conclude that $M'(z) \gg M(z)$. ■

## C.7 Auxiliary: Standard probability results

In this paragraph, we recall a few classical probability results.

**Lemma C.25** (Time-uniform Azuma-Hoeffding, Bourel et al. (2020)). Let $(U_t)$ be a martingale difference sequence sequence with $\sigma$-subgaussian increments, i.e., for all $\lambda \in \mathbf{R}$, we have $E[\exp(\lambda U_n) | U_1, \dots, U_{n-1}] \leq \exp(\frac{\lambda^2 \sigma^2}{2})$. Then, for all $\delta > 0$, we have

$$ \mathbf{P} \left( \exists n \geq 1, \left( \sum_{k=1}^{n} U_k \right)^2 \geq n\sigma^2 \left( 1 + \frac{1}{n} \right) \log \left( \frac{\sqrt{1+n}}{\delta} \right) \right) \leq \delta. $$
**Lemma C.26** (Time-uniform Weissman, Boone and Gaujal (2025)). Let $d \ge 2$ and $q$ be a distribution over $\{1, \dots, d\}$. Let $(U_t)$ be a sequence of i.i.d. random variables of distribution $q$. Then, for all $\delta > 0$, we have

$$ \mathbf{P}\left(\exists n \ge 1, \left\|\sum_{k=1}^{n} (e_{U_k} - q)\right\|_{1}^{2} \ge \frac{1}{4} n \left(1 + \frac{1}{n}\right) \log\left(\frac{2^{d}\sqrt{1+n}}{\delta}\right)\right) \le \delta. $$

**Proof** Note that

$$ \left\| \sum_{k=1}^{n} (e_{U_k} - q) \right\|_{1} = \max_{v \in \{-1, 1\}^d} \left\{ \sum_{k=1}^{n} (e_{U_k} - q) \cdot v \right\}. $$

Let $W_k^v := (e_{U_k} - q) \cdot v$. Then, for each $v \in \{-1, 1\}^d$, $(W_k^v)$ is a family of i.i.d. random variables with $\mathbf{E}[W_k^v] = 0$ and $-qv \le W_k^v \le 1 - qv$ a.s., so $\mathbf{E}[\exp(\lambda W_k^v)] \le \exp(\lambda^2/8)$ by Hoeffding's Lemma. So, by a time-uniform Azuma-Hoeffding inequality (Lemma C.25), we obtain

$$ \begin{aligned} & \mathbf{P}\left(\exists n \ge 1, \left\|\sum_{k=1}^{n} (e_{U_k} - q)\right\|_{1}^{2} \ge \frac{1}{4} n \left(1 + \frac{1}{n}\right) \log\left(\frac{2^{d}\sqrt{1+n}}{\delta}\right)\right) \\ &= \mathbf{P}\left(\exists v \in \{-1, 1\}^{d}, \exists n \ge 1, \left(\sum_{k=1}^{n} W_k^v\right)^2 \ge \frac{1}{4} n \left(1 + \frac{1}{n}\right) \log\left(\frac{2^{d}\sqrt{1+n}}{\delta}\right)\right) \\ &\le \sum_{v \in \{-1, 1\}^d} \mathbf{P}\left(\exists n \ge 1, \left(\sum_{k=1}^{n} W_k^v\right)^2 \ge \frac{1}{4} n \left(1 + \frac{1}{n}\right) \log\left(\frac{2^{d}\sqrt{1+n}}{\delta}\right)\right) \\ &\le \sum_{v \in \{-1, 1\}^d} \mathbf{P}\left(\exists n \ge 1, \left(\sum_{k=1}^{n} W_k^v\right)^2 \ge \frac{1}{4} n \left(1 + \frac{1}{n}\right) \log\left(\frac{\sqrt{1+n}}{2^{-d}\delta}\right)\right) \le 2^d \cdot 2^{-d}\delta = \delta. \end{aligned} $$

This concludes the proof. ■

**Lemma C.27** (All-time Sanov). Let $M \equiv (\mathcal{Z}, \nu, p)$ be a Markov decision process with Bernoulli rewards. Fix $n \in (\mathbf{N}^*)^\mathcal{Z}$ and denote $\hat{M}_{(n)}$ the empirical model obtained by sampling independently $n(z)$ times from $\nu(z) \otimes p(z)$. Let $\mathcal{M}^{(n)}$ be the discrete space of all possible values of $\hat{M}_{(n)}$. For all $M' \in \mathcal{M}^{(n)}$, we have

$$ \mathbf{P}(\hat{M}_{(n)} = M') \le \exp\left(-\sum_{z \in \mathcal{Z}} \mathrm{KL}(M'(z) || M(z))\right) $$

where $\mathrm{KL}(M'(z) || M(z)) := \mathrm{KL}(\nu'(z) || \nu(z)) + \mathrm{KL}(p'(z) || p(z))$.

**Proof** This result is conveniently obtained with the method of types, see Csiszar (2006) for example. For $m \ge 1$, write $r_{(m)}(z)$ and $p_{(m)}(z)$ the empirically observed reward and kernel after $m$ independent samples of $\nu(z) \otimes p(z)$. We have

$$ \mathbf{P}(\hat{M}_{(n)} = M') = \prod_{z \in \mathcal{Z}} \mathbf{P}(\hat{r}_{(n(z))}(z) = r'(z)) \mathbf{P}(\hat{p}_{(n(z))}(z) = p'(z)). \quad (C.65) $$
Let $z \in \mathcal{Z}$. By definition, $r'(z)$ is of the form $\text{Ber}(k(z)/n(z))$ for $k \in \{0, \dots, n(z)\}$. So,

$$ 
\begin{aligned}
\mathbf{P}(\hat{r}_{(n(z))}(z) = r'(z)) &= \binom{n(z)}{k(z)} r(z)^{k(z)} (1-r(z))^{n(z)-k(z)} \\
&= \exp(-n\text{KL}(\nu'(z)||\nu(z))) \cdot \binom{n(z)}{k(z)} \exp(-n(z)\text{Ent}(r'(z))) \\
&\stackrel{(\dagger)}{\le} \exp(-n(z)\text{KL}(\nu'(z)||\nu(z)))
\end{aligned}
\qquad (\text{C.66})
$$

where $(\dagger)$ follows from the classical inequality $(a) \le \exp(a\text{Ent}(b))$ where $\text{Ent}(-)$ is the entropy in base $e$. With the same computation for kernels, we find that

$$ \mathbf{P}(\hat{p}_{(n(z))}(z) = p'(z)) \le \exp(-n(z)\text{KL}(p'(z)||p(z))) \qquad (\text{C.67}) $$

for all $z \in \mathcal{Z}$. Combining (C.65), (C.66) and (C.67), we conclude accordingly. ■

**Lemma C.28 (Combinatorics, folklore).** Let $k \ge 1$ and denote $\mathcal{P}_n[k]$ the set of probability distributions over $\{1, \dots, k\}$ of the form $(\frac{n_1}{n}, \dots, \frac{n_k}{n})$ for $n_i \in \mathbf{N}$. We have $|\mathcal{P}_n[k]| \le (n+1)^k$.
Appendix D. Deviation bounds on MDP specific quantities

The goal of this section is to provide a complete machinery to bound the variations of various policy related quantities, such as the gain, the bias, the diameter, the invariant measure and the reaching probabilities to components of recurrent sets. One important consequence of the developed results is Proposition 3, consisting in that if M, M' are two Markov decision processes, then

$$
\mathcal{Z}_{\varepsilon}^{**}(M') = \mathcal{Z}^{**}(M) \quad \text{when} \quad C(M) \|M' - M\|^* \ll \varepsilon \qquad (\text{D.1})
$$

where $C(M)$ is directly related to $D^*(M)$, that is a notion of **worst diameter** (see Section 4.2 and Proposition 3), and $\varepsilon > 0$ is smaller than the gain gap of $M$.

All bounds are developed using a martingale technique coupled with a Poisson equation, sometimes under a transform of the initial kernel and reward function. To provide a general flavor of the technique, consider two Markov reward processes $(r_1, p_1)$ and $(r_2, p_2)$, and denote $g_j, b_j$ their respective gain and bias functions. We have the Poisson equation $g_j(s) + b_j(s) = r_j(s) + p_j(s)b_j$. We write $S_t$ the random state at time $t$, and $\mathbf{P}_s^{p_j}(-)$, $\mathbf{E}_s^{p_j}[-]$ the probability and expectation of the trajectory governed by $p_j$ initialized at $S_1 = s$. Consider a stopping time $\tau$ such that $\mathbf{E}_s^{p_2}[\tau] < \infty$. The heart of the technique lies in the following computation:

$$
\begin{align*}
& \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau-1} r_2(S_t) \right] \\
&= \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau-1} (r_2(S_t) - r_1(S_t)) \right] + \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau-1} r_1(S_t) \right] \\
&\stackrel{(\dagger)}{=} \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau-1} (r_2(S_t) - r_1(S_t)) \right] + \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau-1} (g_1(S_t) + (\mathbf{e}_{S_t} - p_1(S_t))b_1) \right] \\
&= \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau-1} g_1(S_t) \right] + \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau-1} (r_2(S_t) - r_1(S_t)) \right] + \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau-1} (p_2(S_t) - p_1(S_t))b_1 \right] \\
&\phantom{=} + \mathbf{E}_s^{p_2} [b_1(s) - b_1(S_\tau)] \\
&\stackrel{(\ddagger)}{\le} \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau-1} g_1(S_t) \right] + \mathbf{E}_s^{p_2} [b_1(s) - b_1(S_\tau)] + \mathbf{E}_s^{p_2}[\tau] \left( \|r_2 - r_1\|_{\infty} + \frac{1}{2}\text{sp}(b_1) \|p_2 - p_1\|_{\infty} \right)
\end{align*}
$$

where (†) follows from the Poisson equation of (r₁, p₁) and (‡) from standard norm bounds.
Coupled with model transformation and careful choices of stopping times, this technique
provides tight bounds for the variations of the gain, bias, diameter, reaching time and invariant
measures. The obtained bounds on the variations of gain for instance (see Lemma D.8 and
Lemma D.12) are much better than those obtained using algebraic approaches involving
the Drazin inverse with very little structural assumptions, going way beyond the scope of
ergodic Markov reward processes.
## D.1 A multichain-friendly diameter notion for Markov chains

The diameter provided in the definition is below generalizes the well-known notion of diameter in the communicating/recurrent setting. It is tuned to provide a simple bound on the span of the bias function.

**Definition D.1** (Diameter of a policy/Markov chain). Let $p$ be the kernel of a Markov chain with recurrent components $S_1, \dots, S_k$. The (policy) diameter of $p$ is given by

$$D(p) := \sup_{(s_i) \in \prod_i S_i} \sup_{s \in S} \mathbf{E}_s^p[\tau_{\{s_1, \dots, s_k\}}] < \infty. \quad (D.2)$$

For Markov decision processes, the policy diameter of $\pi \in \Pi$ in $M$ is also denoted $D(\pi; M) = D(p_\pi)$, where $p_\pi(s'|s) := \sum_{a \in A(s)} p(s'|s, a)\pi(a|s)$ is the transition kernel of $\pi$.

When the underlying chain is irreducible (i.e., recurrent), this diameter is related to return times hence providing lower bounds on invariant measures.

**Lemma D.1** (Diameter and invariant measures). The unique probability invariant measure $\mu$ of an irreducible Markov chain with kernel $p$ satisfies $\min(\mu) \ge D(p)^{-1}$.

**Proof** Let $\tau_s^+ := \inf\{t \ge 2 : S_t = s\}$ the first return time to $s \in S$. It is known, see for e.g. (Levin and Peres, 2017, Proposition 1.19), that $\mu(s) = (\mathbf{E}_s^p[\tau_s^+] - 1)^{-1}$. Now, note that

$$\mathbf{E}_s^p[\tau_s^+] \le 1 + \max_{s' \ne s} \mathbf{E}_{s'}^p[\inf\{t \ge 1 : S_t = s\}] \le 1 + D(p)$$

and conclude accordingly.

<figure><img src="image_22.png" /></figure>

### D.1.1 POLICY DIAMETER AND DIAMETERS OF MARKOV DECISION PROCESSES

The policy diameter is related to the standard notion of diameter in Markov decision processes. Recall that the **diameter** of a Markov decision process $M$ is given by $D(M) := \max_{s \ne s'} \min_{\pi \in \Pi} \mathbf{E}_s^{\pi,M}[\inf\{t \ge 1 : S_t = s'\}]$ and is finite if, and only if $M$ is communicating. Note that, for fixed $s \ne s'$, the inner minimum can be taken over the set of unichain policies, i.e., policies with a unique recurrent component on $M$; Indeed, by taking a policy $\pi$ achieving the minimum, we can modify $\pi$ into $\pi'$ by setting $\pi'(s'') = \text{Uniform}(A(s''))$ for every $s'' \in S$ from which $s'$ is not reachable, i.e., $\mathbf{P}_{s''}^{\pi,M}(\inf\{t \ge 2 : S_t = s'\}) = 0$, and check that the reaching time to $s'$ from $s$ has to be the same under $\pi$ and $\pi'$. Then, note that if $s'$ is recurrent under a unichain policy $\pi \in \Pi$, then $\mathbf{E}_s^{\pi,M}[\inf\{t \ge 1 : S_t = s'\}] \le D(\pi; M)$. This shows that the diameter of $M$ is upper-bounded relatively to the policy diameters of its unichain policies as given by

$$D(M) \le \max_{s' \in S} \min\{D(\pi; M) : \pi \text{ unichain and } s' \text{ recurrent under } \pi\}. \quad (D.3)$$

In particular, we have the following result.

**Proposition D.2** (Diameter and worst diameter). In communicating Markov decision processes, the diameter is bounded by the worst diameter, i.e., $D(M) \le D^*(M)$.
The inequality in (D.3) is strict in general; Take for instance the deterministic transition Markov decision process induced by the complete graph with 3 vertices (the undirected 3-cycle). However, if we denote $M_s$ the copy of $M$ obtained by making $s$ absorbing, then it can be shown that

$$D(M) = \max_{s' \in S} \min \{ D(\pi; M_{s'}) : \pi \text{ unichain and } s' \text{ recurrent under } \pi \text{ in } M \}. \quad (D.4)$$

Indeed, regarding (D.2), the set of recurrent states is reduced to {$s'$} because if $s'$ is recurrent under some unichain policy $\pi$, then it is the only recurrent state of $\pi$ in $M_{s'}$.

### D.1.2 POLICY DIAMETER AND BIAS FUNCTION

Following these observations, we can generalize the links between the bias function and the diameter to the policy diameter as follows.

**Lemma D.3 (Policy bias and diameter).** Let $(r, p)$ be a Markov reward process and denote $g, b$ its gain and bias functions. Then $\text{sp}(b) \le 2 \text{sp}(r)D(p)$.

**Proof** For $(s_i) \in \prod_{i=1}^k S_i$ a covering of the recurrent components, we denote $\tau \equiv \tau_{\{s_1, \dots, s_k\}}$ for short. We have $\mathbf{E}_s^p[\tau] \le D(p) < \infty$ for all $s \in S$ by construction. Because $\mu b = 0$ for every invariant measure of $p$, we see that for all $i = 1, \dots, k$, there must be $s_i \in S_i$ such that $b(s_i) \ge 0$, and another $s_i \in S_i$ such that $b(s_i) \le 0$. Assume that $b(s_i) \le 0$ for all $i = 1, \dots, k$. Then

$$ \begin{align} \max(r-g)D(p) &\ge \mathbf{E}_s^p \left[ \sum_{t=1}^{\tau-1} (r(S_t) - g(S_t)) \right] \nonumber \\ &\stackrel{(\dagger)}{=} \mathbf{E}_s^p \left[ \sum_{t=1}^{\tau-1} (\mathbf{e}_{S_t} - p(S_t))b \right] \tag{D.5} \\ &= b(s) - \mathbf{E}_s^p[b(S_\tau)] = b(s) - \sum_{i=1}^k \mathbf{P}_s^p(\tau_{S_i} < \infty) b(s_i) \stackrel{(\ddagger)}{\ge} b(s). \nonumber \end{align} $$

where $(\dagger)$ follows from the Poisson equation $g(s) + b(s) = r(s) + p(s)b$ and $(\ddagger)$ by $b(s_i) \le 0$. With similar computations, and picking $s_i$ such that $b(s_i) \ge 0$ for $i = 1, \dots, k$, we have

$$ \min(r-g)D(p) \le b(s) - \sum_{i=1}^{k} \mathbf{P}_s^p(\tau_{S_i} < \infty)b(s_i) \le b(s). \quad (D.6) $$

Combining (D.5) and (D.6), we obtain

$$ \max(b) - \min(b) \le D(p)(\max(r-g) - \min(r-g)) \le 2 \text{sp}(r)D(p) \quad (D.7) $$

where the second inequality uses that $\min(r) \le g(s) \le \max(r)$ for all $s$.

<figure><img src="image_23.png" /></figure>
### D.1.3 SENSITIVITY OF THE POLICY DIAMETER TO PERTURBATIONS

In this paragraph, we quantify the sensitivity of hitting times and of the policy diameter to perturbations of the transition kernel (Lemma D.4). For the general setting, we make an absolute continuity assumption. This assumption can be dropped completely under an ergodic assumption (Lemma D.5), and partially under a unichain assumption (Corollary D.6).

**Lemma D.4 (Variations of policy diameter).** Let $p_1 \sim p_2$ be two equivalent Markov chains with (common) recurrent components $S_1, \dots, S_k$. For all $(s_i) \in \prod_{i=1}^k S_i$ covering of the recurrent components, the variations of the hitting time $\tau \equiv \tau_{\{s_1, \dots, s_k\}}$ are bounded as:

$$ \left| \sup_s \mathbf{E}_s^{p_2}[\tau] - \sup_s \mathbf{E}_s^{p_1}[\tau] \right| \le \frac{1}{2} \sup_s \mathbf{E}_s^{p_2}[\tau] \sup_s \mathbf{E}_s^{p_1}[\tau] \|p_2 - p_1\|_{\infty}. \quad (D.8) $$

In particular $D(p_2) \le D(p_1) + \frac{1}{2} D(p_1) D(p_2) \|p_2 - p_1\|_{\infty}$.

**Proof** Let $(s_i) \in \prod_{i=1}^k S_i$ be a covering of the recurrent components and denote $\tau \equiv \tau_{\{s_1, \dots, s_k\}}$ for short. Consider the kernel $p'_j$ obtained by making every $s_i$ absorbing and consider the reward function $r'(s) := \mathbf{1}(s \notin \{s_1, \dots, s_k\})$. The gain and bias functions of the Markov reward process $(r', p'_j)$ are denoted $g'_j$ and $b'_j$ for $j = 1, 2$. Remark that $g'_j = 0$ and that the bias satisfies

$$ b'_{j}(s) = \text{Clim}_{T \to \infty} \mathbf{E}_{s}^{p'_{j}} \left[ \sum_{t=1}^{\tau \wedge T-1} (r'(S_t) - g'_{j}(S_t)) \right] = \mathbf{E}_{s}^{p'_{j}}[\tau] \quad (D.9) $$

hence $b'_j$ are the reaching times of which we want to bound the variations. We have

$$ b'_{2}(s) = \mathbf{E}_{s}^{p_{2}} \left[ \sum_{t=1}^{\tau-1} r'(S_{t}) \right] = b'_{1}(s) + \mathbf{E}_{s}^{p_{2}} \left[ \sum_{t=1}^{\tau-1} (p_{2}(S_{t}) - p_{1}(S_{t}))b'_{1} \right]. $$

The error term is bounded by $|\mathbf{E}_s^{p_2}[\sum_{t=1}^{\tau-1} (p_2(S_t) - p_1(S_t))b'_1]| \le \frac{1}{2}\text{sp}(b'_1)\mathbf{E}_s^{p_2}[\tau]\|p_2 - p_1\|_{\infty}$. By (D.9), we clearly have $\text{sp}(b'_1) = \max(b'_1) = \sup_s \mathbf{E}_s^{p_1}[\tau]$. Accordingly, we have obtained the self-bound:

$$ \left| \sup_s \mathbf{E}_s^{p_2}[\tau] - \sup_s \mathbf{E}_s^{p_1}[\tau] \right| \le \frac{1}{2} \sup_s \mathbf{E}_s^{p_2}[\tau] \sup_s \mathbf{E}_s^{p_1}[\tau] \|p_2 - p_1\|_{\infty}. \quad (D.10) $$

This concludes the proof.

<figure><img src="image_24.png" /></figure>

The assumption $p_1 \sim p_2$ is not always necessary and can be dropped under a recurrent assumption. In turn, this allows to control the deviations of reaching times to recurrent states of unichain Markov chains.

**Lemma D.5 (Variations of policy diameter, recurrent case).** Let $p_1, p_2$ be two recurrent Markov chains. We have

$$ |D(p_1) - D(p_2)| \le \frac{1}{2} D(p_1) D(p_2) \|p_2 - p_1\|_{\infty}. \quad (D.11) $$

**Proof** Same proof as Lemma D.4.

<figure><img src="image_25.png" /></figure>
**Corollary D.6 (Variations of reaching times, unichain case).** Let $p_1, p_2$ be two unichain Markov chains that share one recurrent state $s' \in S$. Then

$$ \left| \sup_{s \in S} \mathbf{E}_s^{p_2}[\tau_{s'}] - \sup_{s \in S} \mathbf{E}_s^{p_1}[\tau_{s'}] \right| \le \frac{1}{2} \sup_{s \in S} \mathbf{E}_s^{p_1}[\tau_{s'}] \sup_{s \in S} \mathbf{E}_s^{p_2}[\tau_{s'}] \|p_2 - p_1\|_{\infty}. $$

**Proof** For $i = 1, 2$, introduce $p'_i$ the copy of $p_i$ where $s'$ is made absorbing, and apply Lemma D.4 to $p'_1, p'_2$. ■

In Lemma D.5, the inequality $D(p_2) \le D(p_1) + \frac{1}{2}D(p_1)D(p_2)\|p_2 - p_1\|_{\infty}$ is a self-bound for $D(p_2)$. It can be decoupled when $\|p_2 - p_1\|_{\infty}$ is small. If $\|p_2 - p_1\|_{\infty} < \frac{2}{D(p_1)}$, we obtain

$$ D(p_2) \le \frac{1}{1 - \frac{1}{2}D(p_1)\|p_2 - p_1\|_{\infty}} D(p_1). \quad (D.12) $$

For instance, if $\|p_2 - p_1\|_{\infty} \le D(p_1)^{-1}$, then $D(p_2) \le 2D(p_1)$. The same technique can be used to untangle the inequalities of Lemma D.4 and Corollary D.6.

### D.1.4 SENSITIVITY OF THE DIAMETER OF MDPs TO PERTURBATIONS

Using the links between the diameter of Markov decision processes and the diameter of unichain policies, see (D.3) and (D.4), Lemma D.4 allows to bound the variations of the diameter in a neighborhood of $M$.

**Lemma D.7 (Variations of diameter).** Let $M \equiv (\mathcal{Z}, p, r)$ be a communicating Markov decision process. For $M' \equiv (\mathcal{Z}, p', r')$ such that $p' \sim p$, we have

$$ |D(M') - D(M)| \le \frac{1}{2} D(M') D(M) \|p' - p\|_{\infty}. \quad (D.13) $$

In particular, if $\|p' - p\|_{\infty} \le 2D(M)^{-1}$, then $D(M') \le (1 - \frac{1}{2}D(M)\|p' - p\|_{\infty})^{-1}D(M)$.

**Proof** Following (D.4), we introduce $\pi_{s'}$ the policy minimizing $D(\pi; M_{s'})$ over the set of unichain policies under which $s' \in S$ is recurrent in $M$, where $M_{s'} \equiv (\mathcal{Z}, p_{s'}, r)$ is the copy of $M$ obtained by making $s'$ absorbing. By Lemma D.4, we have

$$ |D(\pi_{s'}; M'_{s'}) - D(\pi_{s'}; M_{s'})| \le \frac{1}{2} D(\pi_{s'}; M'_{s'}) D(\pi_{s'}; M_{s'}) \|p'_{s'} - p_{s'}\|_{\infty} $$

for $s' \in S$. By construction, $\|p'_{s'} - p_{s'}\|_{\infty} \le \|p' - p\|_{\infty}$. Conclude by (D.4). ■

In particular, if $\|M' - M\| \le D(M)^{-1}$, then $D(M') \le 2D(M)$.

## D.2 Results for unichain Markov reward processes

The first lemma is the conclusion of the tutorial computations that start Appendix D.

**Lemma D.8 (Unichain gain variations).** Let $(r_1, p_1)$ and $(r_2, p_2)$ be two Markov reward processes. Denote $g_j, b_j$ the gain and bias functions of $(r_j, p_j)$ for $j = 1, 2$. Assume that $\text{sp}(g_1) = 0$. Then

$$ \|g_2 - g_1\|_{\infty} \le \|r_2 - r_1\|_{\infty} + \frac{1}{2}\text{sp}(b_1)\|p_2 - p_1\|_{\infty}. $$

If in addition, $p_1 \sim p_2$, then $\text{sp}(b_1)$ can be changed to $\text{sp}(b_1|S_1)$ where $S_1$ is the collection of recurrent states under $p_1$.
**Proof** This is direct adaptation of tutorial computations.

**Lemma D.9 (Unichain invariant measure variations).** Let $p_1 \sim p_2$ be two Markov chains and assume that $p_1$ is unichain.<fnref n="4" /> Denote $\mu_j$ the (unique) probability invariant measure under $p_j$. We have

$$ \|\mu_2 - \mu_1\|_{\infty} \le \min_{j \in \{1,2\}} D(p_j) \|p_2 - p_1\|_{\infty}. $$

**Proof** Fix $s_0 \in S$ a recurrent state. Consider the reward function $r(s) = \mathbf{1}(s = s_0)$, and denote $g_j, b_j$ the gain and bias functions of the Markov reward process $(r, b_j)$. Remark that $g_j(s) = \mu_j(s_0)$. By Lemma D.3, we have $\text{sp}(b_j) \le 2\text{sp}(r)D(p_j) \le 2D(p_j)$. Continuing with Lemma D.8, we have

$$ |\mu_2(s) - \mu_1(s)| \le D(p_j) \|p_2 - p_1\|_{\infty} $$

for both $j = 1, 2$. This concludes the proof.

**Lemma D.10 (Unichain bias variations).** Let $(r_1, p_1)$ and $(r_2, p_2)$ be two Markov reward processes, assume that $p_1$ is unichain and that $p_1 \sim p_2$. Denote $g_j$ and $b_j$ the gain and bias function of $(r_j, p_j)$ for $j = 1, 2$. We have

$$ \|b_2 - b_1\|_{\infty} \le 4D(p_2)\|r_2 - r_1\|_{\infty} + \left(2D(p_2)\text{sp}(b_1) + \frac{1}{2}\text{sp}(b_1^1)\right)\|p_2 - p_1\|_{\infty}. $$

**Proof** We start by bounding $\text{sp}(b_2 - b_1)$. Fix $s_0$ a recurrent state and consider the transform $p'_j$ that makes $s_0$ absorbing as well as the reward function $r'_j(s) := \mathbf{1}(s \ne s_0)(r_j(s) - g_j(s))$. Denote $g'_j$ and $b'_j$ the associated gain and bias functions. From direct computations, we see that $g'_j = 0$ and that $b'_j(s) = b_j(s) - b_j(s_0)$, so in particular $b'_j - b_j \in \mathbf{Re}$ so $\text{sp}(b'_j) = \text{sp}(b_j)$ and $\text{sp}(b'_2 - b'_1) = \text{sp}(b_2 - b_1)$. Moreover, $b'_2$ and $b'_1$ are related as follows:

$$ \begin{aligned} b'_2(s) &= \mathbf{E}_s^{p'_2} \left[ \sum_{t=1}^{\tau_{s_0}-1} r'_2(S_t) \right] \\ &\le \mathbf{E}_s^{p_2}[\tau_{s_0}] \|r'_2 - r'_1\|_{\infty} + \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau_{s_0}-1} (\mathbf{e}_{S_t} - p_1(S_t))b'_1 \right] \\ &\le b'_1(s) + \mathbf{E}_s^{p_2}[\tau_{s_0}] \left( \|r_2 - r_1\|_{\infty} + \|g_2 - g_1\|_{\infty} + \frac{1}{2}\text{sp}(b'_1) \|p'_2 - p'_1\|_{\infty} \right) \\ &\le b'_1(s) + \mathbf{E}_s^{p_2}[\tau_{s_0}] (2\|r_2 - r_1\|_{\infty} + \text{sp}(b_1) \|p'_2 - p'_1\|_{\infty}) \end{aligned} $$

where the last inequality is a consequence of Lemma D.8 and $\text{sp}(b'_1) \le \text{sp}(b_1)$. With the same technique, we lower bound $b'_2(s)$ by $b'_1(s)$ with the same error term. Remark that $\mathbf{E}_s^{p_j}[\tau_{s_0}] \le D(p_j)$. So:

$$ \begin{aligned} \text{sp}(b_2 - b_1) &= \text{sp}(b'_2 - b'_1) = (b'_2 - b'_1)(s_{\text{max}}) - (b'_2 - b'_1)(s_{\text{min}}) \\ &\le 2 D(p_2) (2\|r_2 - r_1\|_{\infty} + \text{sp}(b_1) \|p'_2 - p'_1\|_{\infty}). \end{aligned} \quad (D.14) $$

<footnote n="4">4. Hence $p_2$ is equally unichain with the same recurrent class.</footnote>
To transform the bound on the span to a bound on the norm, remark if **u**, **v** are two vectors and **q** is a probability distribution, then ||**u** - **v**||_∞ ≤ sp(**u** - **v**) + |**q**(**u** - **v**)|. Let µ_j be the (unique) invariant probability measure under p_j. We have

$$
\|b_2 - b_1\|_{\infty} \le \mathrm{sp}(b_2 - b_1) + |\mu_2(b_2 - b_1)|. \quad (\mathrm{D.15})
$$

The left term of (D.15) is taken care of with (D.14) and we are left to bound |μ₂(b₂ - b₁)|.
Remark that bⱼ, the 1-th higher order bias, is the bias of the Markov reward process (-bⱼ, pⱼ).
We have

$$
\begin{align*}
|\mu_2(b_2 - b_1)| &= |\mu_2 b_1| = \lim_{T \to \infty} \frac{1}{T} \left| \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{T-1} b_1(S_t) \right] \right| \\
&= \lim_{T \to \infty} \frac{1}{T} \left| \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{T-1} (\mathbf{e}_{S_t} - p_1(S_t)) b_1^1 \right] \right| \tag{D.16} \\
&= \lim_{T \to \infty} \frac{1}{T} \left| \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{T-1} (p_2(S_t) - p_1(S_t)) b_1^1 \right] \right| \le \frac{1}{2} \mathrm{sp}(b_1^1) \|p_2 - p_1\|_{\infty}.
\end{align*}
$$

Combining (D.14), (D.15) and (D.16), we obtain the desired bound.

<figure><img src="image_26.png" /></figure>

**D.3 Results for multichain Markov reward processes**

We generalize the inequalities of the unichain setting to general multichain Markov processes.
The new difficulty is that in the multichain setting, a perturbation of the kernel changes
the probability of reaching a given recurrent component. The first result below is key. It is
perhaps surprising, because it shows that the reaching probabilities vary additively and not
multiplicatively with respect to kernel modifications.

**Definition D.2 (Equivalent chains).** We say that two Markov chains are equivalent and write $p_1 \sim p_2$ if $p_1 \ll p_2 \ll p_1$.

**Lemma D.11 (Reaching probabilities variations).** Let $p_1 \sim p_2$ be two equivalent Markov chains and $S_1^1, \dots, S_1^k$ be the recurrent classes of $p_1$. Let $\tau_\infty := \inf\{t \ge 1 : S_t \in S_1^1 \cup \dots \cup S_1^k\}$ be the reaching time to one of the recurrent classes and $\tau_i := \inf\{t \ge 1 : S_t \in S_1^i\}$ be the reaching time to $S_1^i$. We have

$$
|\mathbf{P}_s^{p_1}(\tau_i < \infty) - \mathbf{P}_s^{p_2}(\tau_i < \infty)| \leq \min_{j \in \{1,2\}} \frac{1}{2} \mathbf{E}_s^{p_j}[\tau_\infty] \|p_1 - p_2\|_{\infty}.
$$

In case, the bound can be simplified using $\mathbf{E}_s^{p_j}[\tau_\infty] \le D(p_j)$.

**Proof** Consider the reward function $r(S_t, S_{t+1}) = \mathbf{1}(S_t \notin S_1^i)$ and $S_t \in S_1^i$), providing reward when the walk crosses the frontier between $S_1^i$ and its $S \setminus S_1^i$. For $j \in \{1,2\}$, we denote $g_j, b_j$ the gain and bias functions under the Markov reward process $(r, p_j)$. Since $p_1 \sim p_2$, they have the same recurrent classes, we have $\mathbf{E}^{p_j}[\tau_i] < \infty$ for $j = 1,2$ and $g_j(s) = 0$. Therefore, for $s \notin S_1^i$, we have

$$
b_j(s) := \lim_{T \to \infty} \mathbf{E}_s^{p_j} [r(S_1, S_2) + \dots + r(S_{T-1}, S_T)]
$$
$$
\begin{align*}
&= \lim_{T \to \infty} \mathbf{E}_s^{p_j} \left[ \sum_{t=1}^{T-1} \mathbf{1}(S_t \notin S_1^i \text{ and } S_{t+1} \in S_1^i) \right] \\
&= \lim_{T \to \infty} \mathbf{E}_s^{p_j} \left[ \sum_{t=1}^{T-1} \mathbf{1}(\tau_i = t+1) \right] \\
&= \lim_{T \to \infty} \sum_{t=1}^{T-1} \mathbf{P}_s^{p_j}(\tau_i = t+1) = \mathbf{P}_s^{p_j}(2 \le \tau_i < \infty) = \mathbf{P}_s^{p_j}(\tau_i < \infty)
\end{align*}
$$

where the last line use that $s \notin S_1^i$. For $s \in S_1^i$, we have $p_j(s) = 0$. Our goal is therefore to bound $b_2(s)$ with respect to $b_1(s)$. For $s \notin S_1^i$, we have

$$
\begin{align*}
b_2(s) &= \lim_{T \to \infty} \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{T-1} r(S_t, S_{t+1}) \right] \\
&\stackrel{(\dagger)}{=} \lim_{T \to \infty} \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{T-1} (\mathbf{e}_{S_t} - p_1(S_t))b_1 \right] = b_1(s) + \lim_{T \to \infty} \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{T-1} (p_2(S_t) - p_1(S_t))b_1 \right]
\end{align*}
$$

where $(\dagger)$ follows from Poisson's equation. We are left to bound the RHS. Observe that once $S_t$ belongs to one of the recurrent components of $p_1$, every state $s'$ that is reachable under $p_1$ satisfies $b_1(s') = 0$. Because $p_1 \sim p_2$, this is also true for any state that is reachable under $p_2$. Therefore

$$
\left| \lim_{T \to \infty} \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{T-1} (p_2(S_t) - p_1(S_t))b_1 \right] \right| \le \frac{1}{2} \mathbf{E}_s^{p_2}[\tau_\infty] \|p_2 - p_1\|_{\infty} \le \frac{1}{2} \mathbf{E}_s^{p_2}[\tau_\infty] \|p_2 - p_1\|_{\infty}.
$$

In other words, $|p_1(s) - p_2(s)| \le \frac{1}{2} \mathbf{E}_s^{p_2}[\tau_\infty]$. Because $j=1$ and $j=2$ play a symmetric role, $\mathbf{E}_s^{p_2}[\tau_\infty]$ can be changed to $\mathbf{E}_s^{p_1}[\tau_\infty]$. ■

**Lemma D.12** (Multichain gain variations). Let $p_1 \sim p_2$ be two equivalent Markov chains and $S_1, \dots, S_k$ be the (common) recurrent classes. Let $\tau_\infty := \inf\{t \ge 1 : S_t \in S_1 \cup \dots \cup S_k\}$ be the reaching time to one of the recurrent classes. We have

$$
\|g_2 - g_1\|_{\infty} \le \|r_2 - r_1\|_{\infty} + \min_{j \in \{1,2\}} \frac{1}{2} \left( \max_i \text{sp}(b_j|S_i) + \frac{1}{2} k \mathbf{E}_s^{p_j}[\tau_\infty] \right) \|p_2 - p_1\|_{\infty}
$$

In case, the bound can be simplified using $\frac{1}{2}(\max_i \text{sp}(b_j|S_i) + \frac{1}{2}k\mathbf{E}_s^{p_j}[\tau_\infty]) \le (1 + \frac{1}{4}k)D(p_j)$.

**Proof** Let $s \in S$. We have

$$
\begin{align*}
|g_2(s) - g_1(s)| & \le \left| \sum_{i=1}^{k} \mathbf{P}_s^{p_2}(\tau_i < \infty) g_2(S_i) - \sum_{i=1}^{k} \mathbf{P}_s^{p_1}(\tau_i < \infty) g_1(S_i) \right| \\
& \le \sum_{i=1}^{j} \mathbf{P}_s^{p_2}(\tau_i < \infty) |g_2(S_i) - g_1(S_i)| + \left| \sum_{i=1}^{j} (\mathbf{P}_s^{p_2}(\tau_i < \infty) - \mathbf{P}_s^{p_1}(\tau_i < \infty)) g_1(S_i) \right| \\
& \stackrel{(\dagger)}{\le} \sum_{i=1}^{j} \mathbf{P}_s^{p_2}(\tau_i < \infty) \left( \|r_2 - r_1\|_{\infty} + \frac{1}{2} \text{sp}(b_1|S_i) \|p_2 - p_1\|_{\infty} \right)
\end{align*}
$$
$$ + \frac{1}{2} \left\| (\mathbf{P}_s^{p_2}(\tau_i < \infty) - \mathbf{P}_s^{p_1}(\tau_i < \infty))_{i=1}^k \right\|_1 \\ \stackrel{(\dagger)}{\le} \|r_2 - r_1\|_{\infty} + \frac{1}{2} \left( \max_i \operatorname{sp}(b_1|S_i) + \frac{1}{2}k \mathbf{E}_s^{p_1}[\tau_{\infty}] \right) \|p_2 - p_1\|_{\infty} $$

where (†) follows by applying Lemma D.8 to the LHS and (‡) by applying Lemma D.11 to the RHS. ■

**Lemma D.13** (Multichain invariant measure variations). Let $p_1 \sim p_2$ be two equivalent Markov chains and $S_1, \dots, S_k$ be the (common) recurrent classes. Let $\tau_\infty := \inf\{t \ge 1: S_t \in S_1 \cup \dots \cup S_k\}$ be the reaching time to one of the recurrent classes. Denote $\mu_j(-|s)$ the asymptotic empirical distribution of visits starting from $s$ under $p_j$. We have

$$ \forall s \in S, \quad \|\mu_2(-|s) - \mu_1(-|s)\|_{\infty} \le \min_{j \in \{1, 2\}} \frac{1}{2} \left( \max_i D(p_j|S_i) + \frac{1}{2}k \mathbf{E}_s^{p_j}[\tau_{\infty}] \right) \|p_2 - p_1\|_{\infty}. $$

In case, the bound can be simplified using $\frac{1}{2}(\max_i D(p_j|S_i) + \frac{1}{2}k \mathbf{E}_s^{p_j}[\tau_\infty]) \le (1 + \frac{1}{4}k)D(p_j)$.

**Proof** This is a consequence of Lemma D.12 by considering the reward function $r(s) = 1(s = s_\infty)$ for $s_\infty \in S$ a fixed state, similarly to Lemma D.9. Denote $g_j, b_j$ denote the gain and bias function of the Markov reward process $(r, p_j)$. Remark that $g_j(s_0) = \mu_j(s_\infty|s_0)$. By Lemma D.12, we have

$$ |\mu_2(s_\infty|s_0) - \mu_1(s_\infty|s_0)| \le \min_{j \in \{1, 2\}} \frac{1}{2} \left( \max_i \operatorname{sp}(b_j|S_i) + \frac{1}{2}k \mathbf{E}_{s_0}^{p_j}[\tau_\infty] \right) \|p_2 - p_1\|_{\infty}. $$

Because $S_i$ is a recurrent class under $p_j$, it corresponds to the optimal bias of a communicating model, so by Lemma D.3, we have $\operatorname{sp}(b_j|S_i) \le \operatorname{sp}(r)D(p_j|S_i) \le D(p_j|S_i)$. This provides the desired bound. ■

**Lemma D.14** (Multichain bias variations). Let $(r_1, p_1)$ and $(r_2, p_2)$ be two Markov reward processes with $p_1 \sim p_2$ and let $S_1, \dots, S_k$ be the (common) recurrent classes. Denote $g_j, b_j$ the gain and bias functions of $(r_j, p_j)$ for $j = 1, 2$. Let $\tau_\infty := \inf\{t \ge 1: S_t \in S_1 \cup \dots \cup S_k\}$ be the reaching time to one of the recurrent classes. We have

$$ \|b_2 - b_1\|_{\infty} \le 6D(p_2)\|r_2 - r_1\|_{\infty} + \left(\left(7 + \frac{1}{2}k\right)D(p_2)D(p_1) + 2D(p_1)^2\right)\|p_2 - p\|_{\infty}. $$

Following Lemma D.4, when $\|p_2 - p_1\|_{\infty} \le D(p_1)^{-1}$, the quantity $D(p_2)$ can be changed to $2D(p_1)$.

The result can be improved by more carefully tracking the Lipschitz constants throughout. To lighten the typography—and because our application do not require an optimal result, we overshoot the error term.

**Proof** For $i = 1, \dots, k$, pick $s_0^i \in S_i$ and denote $S_0 = \{s_0^1, \dots, s_0^k\}$. For $j = 1, 2$, let $p'_j$ be the kernel obtained by copying $p_j$ while making every $s_0^i$ absorbing, and set $r'_j(s) := 1(s \notin S_0)(r_j(s) - g_j(s))$. Denote $g'_j$ and $b'_j$ the gain and bias functions of the Markov reward
process $(r'_j, p'_j)$. Observe that $g'_j = 0$ and $b'_j(s_0^i) = 0$ for all $i = 1, \dots, k$. Moreover, the biases $b_j$ and $b'_j$ are linked as follows

$$ 
\begin{aligned}
b'_j(s) &= \operatorname{Clim}_{T \to \infty} \mathbf{E}_s^{p'_j} \left[ \sum_{t=1}^{T-1} r'_j(S_t) \right] \\
&= \operatorname{Clim}_{T \to \infty} \mathbf{E}_s^{p'_j} \left[ \sum_{t=1}^{\tau_{S_0} \wedge T-1} (r_j(S_t) - g_j(S_t)) \right] \\
&= \mathbf{E}_s^{p_j} \left[ \sum_{t=1}^{\tau_{S_0}-1} (r_j(S_t) - g_j(S_t)) \right] \\
&= b_j(s) - \mathbf{E}_s^{p_j} [b(S_{\tau_{S_0}})] = b_j(s) - \sum_{i=1}^k \mathbf{P}_s^{p_j}(\tau_{S_i} < \infty) b_j(s_0^i).
\end{aligned} 
\quad (D.17) $$

In particular, $\operatorname{sp}(b'_j) \le 2 \operatorname{sp}(b_j) \le 4D(p_j)$ by Lemma D.3. We have

$$ 
\begin{aligned}
b'_2(s) &= \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau_{S_0}-1} r'_2(S_t) \right] \\
&\le \mathbf{E}_s^{p_2}[\tau_{S_0}] \|r'_2 - r'_1\|_{\infty} + \mathbf{E}_s^{p_2} \left[ \sum_{t=1}^{\tau_{S_0}-1} (\mathbf{e}_{S_t} - p_1(S_t)) b'_1 \right] \\
&\stackrel{(\dagger)}{\le} b'_1(s) + \mathbf{E}_s^{p_2}[\tau_{S_0}] \left( \|r'_2 - r'_1\|_{\infty} + \frac{1}{2}\operatorname{sp}(b'_1) \|p'_2 - p'_1\|_{\infty} \right) \\
&\stackrel{(\ddagger)}{\le} b'_1(s) + D(p_2) \left( \|r_2 - r_1\|_{\infty} + \|g_2 - g_1\|_{\infty} + 2D(p_1) \|p_2 - p_1\|_{\infty} \right) \\
&\stackrel{(\S)}{\le} b'_1(s) + D(p_2) \left( 2 \|r_2 - r_1\|_{\infty} + \left(3 + \frac{1}{4}k\right) D(p_1) \|p_2 - p_1\|_{\infty} \right).
\end{aligned} 
$$

where $(\dagger)$ follows from Poisson's equation, $(\ddagger)$ bounds bias span and hitting times by diameter and expands the definition of $r'_j$, and $(\S)$ invokes the (simplified version of) Lemma D.12 to bound $\|g_2 - g_1\|_{\infty}$. With the same computations, we upper-bound $b'_2(s)$ relatively to $b'_1(s)$, leading to the equation:

$$ |b'_2(s) - b'_1(s)| \le D(p_2) \left( 2 \|r_2 - r_1\|_{\infty} + \left(3 + \frac{1}{4}k\right) D(p_1) \|p_2 - p_1\|_{\infty} \right). \quad (D.18) $$

Combining (D.17) and (D.18), we obtain

$$ 
\begin{aligned}
& |b_2(s) - b_1(s)| \\
&\le |b'_2(s) - b'_1(s)| + \left| \sum_{i=1}^k \left( \mathbf{P}_s^{p_2}(\tau_{S_i} < \infty) b_2(s_0^i) - \mathbf{P}_s^{p_1}(\tau_{S_i} < \infty) b_1(s_0^i) \right) \right| \\
&\le |b'_2(s) - b'_1(s)| + \left| \sum_{i=1}^k \mathbf{P}_s^{p_2}(\tau_{S_i} < \infty) (b_2(s_0^i) - b_1(s_0^i)) \right| \\
&\qquad + \left| \sum_{i=1}^k (\mathbf{P}_s^{p_2}(\tau_{S_i} < \infty) - \mathbf{P}_s^{p_1}(\tau_{S_i} < \infty)) b_1(s_0^i) \right| \\
&\stackrel{(\dagger)}{\le} 6D(p_2) \|r_2 - r_1\|_{\infty} + \left( \left(7 + \frac{1}{2}k\right) D(p_2) D(p_1) + \frac{1}{2}\operatorname{sp}(b_1^1) \right) \|p_2 - p\|_{\infty} \\
&\stackrel{(\ddagger)}{\le} 6D(p_2) \|r_2 - r_1\|_{\infty} + \left( \left(7 + \frac{1}{2}k\right) D(p_2) D(p_1) + 2D(p_1)^2 \right) \|p_2 - p\|_{\infty}
\end{aligned} 
$$
where (†) is obtained by bounding the first term with (D.18), the second term with Lemma D.10 and the third term with Lemma D.11; and (‡) follows from $\text{sp}(b_1^1) \le 4D(p_1)^2$ by applying Lemma D.3 twice. ■
References

R. Agrawal, D. Teneketzis, and V. Anantharam. Asymptotically efficient adaptive allocation schemes for controlled Markov chains: finite parameter space. In *Proceedings of the 27th IEEE Conference on Decision and Control*, pages 1198-1203 vol.2, 1988. doi: 10.1109/CDC.1988.194511.

Shipra Agrawal and Navin Goyal. Analysis of Thompson Sampling for the multi-armed bandit problem, April 2012. URL http://arxiv.org/abs/1111.1797. arXiv:1111.1797 [cs].

Peter Auer and Ronald Ortner. Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning. *Proceedings of the 19th International Conference on Neural Information Processing Systems*, December 2006.

Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal Regret Bounds for Reinforcement Learning. In *Advances in Neural Information Processing Systems*, volume 21. Curran Associates, Inc., 2009.

Peter L. Bartlett and Ambuj Tewari. REGAL: a regularization based algorithm for reinforcement learning in weakly communicating MDPs. In *Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence*, UAI '09, pages 35-42, Arlington, Virginia, USA, June 2009. AUAI Press. ISBN 978-0-9749039-5-8.

Victor Boone. Optimal regrets in markov decision processes, November 2024. URL https://victor-boone.github.io/assets/pdf/VBOONE-manuscript-v1.1.pdf. PhD thesis, see victor-boone.github.io.

Victor Boone and Bruno Gaujal. The Regret of Exploration and the Control of Bad Episodes in Reinforcement Learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, *Proceedings of the 40th International Conference on Machine Learning*, volume 202 of *Proceedings of Machine Learning Research*, pages 2824-2856. PMLR, July 2023.

Victor Boone and Bruno Gaujal. Logarithmic Regret of Exploration in Average Reward Markov Decision Processes, 2025. URL https://arxiv.org/abs/2502.06480. _eprint: 2502.06480.

Victor Boone and Odalric-Ambrym Maillard. The regret lower bound for communicating Markov Decision Processes, 2025. URL https://arxiv.org/abs/2501.13013. _eprint: 2501.13013.

Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening Exploration in Upper Confidence Reinforcement Learning. In Hal Daumé III and Aarti Singh, editors, *Proceedings of the 37th International Conference on Machine Learning*, volume 119 of *Proceedings of Machine Learning Research*, pages 1056-1066. PMLR, July 2020.

Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. *Convex optimization*. Cambridge university press, 2004.
Apostolos Burnetas and Michael Katehakis. Optimal Adaptive Policies for Markov Decision Processes. Mathematics of Operations Research - MOR, 22:222-255, February 1997.

Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-leibler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, pages 1516-1541, 2013.

Imre Csiszar. A simple proof of Sanov's theorem. Bulletin of the Brazilian Mathematical Society, 37(4), 2006.

Sarah Filippi, Olivier Cappé, and Aurélien Garivier. Optimism in Reinforcement Learning and Kullback-Leibler Divergence. 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 115-122, September 2010. arXiv: 1004.5229.

Ronan Fruit. Exploration-exploitation dilemma in Reinforcement Learning under various form of prior knowledge. PhD Thesis, Université de Lille 1, Sciences et Technologies; CRISTAL UMR 9189, 2019.

Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Improved Analysis of UCRL2 with Empirical Bernstein Inequality. ArXiv, abs/2007.05456, 2020.

Aurélien Garivier and Emilie Kaufmann. Optimal Best Arm Identification with Fixed Confidence. In Conference on Learning Theory, pages 998-1027. PMLR, June 2016.

Todd L Graves and Tze Leung Lai. Asymptotically efficient adaptive choice of control laws incontrolled markov chains. SIAM journal on control and optimization, 35(3):715-743, 1997.

Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. J. Mach. Learn. Res., 16:3721-3756, 2015.

Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson Sampling: An Asymptotically Optimal Finite Time Analysis. arXiv:1205.4217 [cs, stat], July 2012. URL http://arxiv.org/abs/1205.4217. arXiv: 1205.4217.

T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, March 1985. ISSN 01968858.

Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.

David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.

Ronald Ortner. Online regret bounds for Markov decision processes with deterministic transitions. Theoretical Computer Science, 411(29):2684-2695, 2010. ISSN 0304-3975.

Fabien Pesquerel and Odalric-Ambrym Maillard. IMED-RL: Regret optimal learning of ergodic Markov decision processes. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 26363-26374. Curran Associates, Inc., 2022.
Martin L Puterman. *Markov decision processes: discrete stochastic dynamic programming.*
John Wiley & Sons, 2014.

Hassan Saber, Fabien Pesquerel, Odalric-Ambrym Maillard, and Mohammad Sadegh Talebi.
Logarithmic regret in communicating MDPs: Leveraging known dynamics with bandits.
In Berrin Yanıkoğlu and Wray Buntine, editors, *Proceedings of the 15th Asian Conference on Machine Learning*, volume 222 of *Proceedings of Machine Learning Research*, pages 1167–1182. PMLR, November 2024.

William R Thompson. On the Likelihood that One Probability Exceeds Another in View of the Evidence of Two Samples. *Biometrika*, 25(3-4):285–294, December 1933. ISSN 0006-3444.

Aristide Tossou, Debabrota Basu, and Christos Dimitrakakis. Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities. arXiv:1905.12425 [cs, stat], December 2019. arXiv: 1905.12425.

Damianos Tranos and Alexandre Proutiere. Regret Analysis in Deterministic Reinforcement Learning. arXiv:2106.14338 [cs, stat], June 2021. arXiv: 2106.14338.

Zihan Zhang and Xiangyang Ji. Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc., 2019.
Index of notations

1(-) indicator function

:= defining equality, defined as

≡ syntactical equality, equal by definition

= propositional equality, shown equal

||-||* support aware norm, Definition 9

a action

A action space

A(s) playable actions from s

A_t random action at time t ≥ 1

b^π(M) bias function of π, Section 2.1.1

b^*(M) optimal bias, Section 2.1.3

C(μ, M) information value, Definition B.1

C_ε(μ, M) ε-leveled information value, Definition B.1

Cnf(M) confusing set, Definition 5

Cnf_ε(M) ε-leveled confusing set, Definition 11

D(M) diameter, Assumption 2

D^*(M) worst diameter, Definition A.3

D(π; M) policy diameter, Definition D.1

D(p) kernel diameter, Definition D.1

dmin(-) definite minimum

dmin(M) definite minimum of M, Definition A.1

Δ^π(M) gap function of π, Section 2.1.1

Δ^*(M) Bellman gaps, Section 2.1.3

Δ^g(M) gain gap, Definition A.4

e vector full of ones, Euler constant

e_s canonical basis of R^S

e_z canonical basis of R^Z

E event

Ent(-) entropy in base e

ε̄ regularization hyperparameter, Section 5.2

ε' floored regularizer, Section 5.2

ε\_conv convexification regularizer, Section 4.3 and Section 5.2

ε\_lvl leveling regularizer, Section 4.3 and Section 5.2

ε\_tst test power, Section 5.2

ε\_unif uniformization regularizer, Section 4.3 and Section 5.2

g^π(M) gain of π, Section 2.1.1

g^*(M) optimal gain, Section 2.1.3

H_t random history at time t ≥ 1

H history space

Inv(M) invariant measures, Definition 4

Inv(ε; M) ε-uniform invariant measures, Definition 10

Inv(π; M) invariant measures of π, Definition A.5

I(M) probability invariant measures Inv(M) ∩ P(Z), Equation (A.3)

K(M) regret lower bound, Theorem 1

K̄(M) regularized regret lower bound, Definition 12

kl(x, y) Kullback-Leibler divergence from Ber(y) to Ber(x)

KL(-||-) Kullback-Leibler divergence

Λ learning algorithm, Section 2.2

M Markov decision process, model

M† confusing model, Definition 5

M ambient space of models

μ invariant measure, Definition 4

μ^π probability invariant measure of π, Proposition A.5

μ^* optimal exploration measure, Section 2.2.2

μ̄^ε-optimal exploration measure, Section 4.3

N_t(z) visit count of z, Section 2.2

ν function of reward distributions

p transition kernel

P(X) probability vectors over X

π policy

π^+ exploitation policy, Section 3.2 and (15)

π^- exploration policy, Section 3.1 and (15)

Π deterministic policies

ΠSR randomized policies

Π_u unichain deterministic policies

Π^*(M) gain optimal policies, Section 2.1.3

r mean reward function

R_t random reward at time t ≥ 1

Reg(T; M, Λ) expected regret, Definition 2

s state

S state space

S_t random state at time t ≥ 1

sp(-) span semi-norm

t time, number of learning step

T learning horizon

T^- exploration times, Section 5

T^+ exploitation times, Section 5

T^± co-exploration times, Section 5

T' panic times, Section 5

T_0^- initial exploration times, Section 5

T_0^+ initial exploitation times, Section 5

z state-action pair

Z pair space

Z_t random pair at time t ≥ 1

Z^*(M) weakly optimal pairs, Definition 1

Z^**(M) optimal pairs, Definition 1

Z^**(M) ε-leveled optimal pairs, Definition 8

3, 3^+ co-exploration structure, Appendix C.2
A.3.5 Properties of policies induced by uniform invariant measures . . . . . 28

A.3.6 Decomposition of invariant measures with unichain policies . . . . . . 29

B Regularized lower bound and approximate optimalities 32

B.1 Properties of leveled optimality and proof of Proposition 3 . . . . . . . . . . . 32

B.2 Information value of measures and critical models . . . . . . . . . . . . . . . . 34

B.2.1 Properties of the confusing set and of critical models . . . . . . . . . . 35

B.2.2 Regularity properties of the information value . . . . . . . . . . . . . . . 38

B.3 Properties of the regularized lower bound . . . . . . . . . . . . . . . . . . . . 45

B.3.1 A simple bound on the regret lower bound . . . . . . . . . . . . . . . . . 46

B.3.2 Existence of optimal and $\bar{\epsilon}$-optimal exploration measures . . . . . . 47

B.3.3 A convenient form for the $\bar{\epsilon}$-regularized lower bound . . . . . . . . 49

B.3.4 Convergence of regularized optimal exploration measures . . . . . . . 50

B.3.5 The regularized lower bound approximates the lower bound . . . . . . . 51

B.3.6 Properties of the regularized lower bound . . . . . . . . . . . . . . . . . . 52

B.3.7 Auxiliary results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

C Regret analysis of ECoE* 59

C.1 Required assumptions on the regularization hyperparameter . . . . . . . . . . 60

C.2 Amount of wrong exploitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

C.2.1 Idea of the proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

C.2.2 Proof of Lemma C.3: Initial exploitation and exploitation times . . . . 62

C.2.3 Wrong exploitation with correct data on leveled optimal pairs . . . . . 64

C.2.4 Uniform exploitation: Fundamental property of co-exploration . . . . 66

C.2.5 Wrong exploitation with correct empirical kernel supports . . . . . . . 68

C.2.6 Wrong exploitation with wrong empirical kernel supports . . . . . . . 70

C.2.7 Correctness of empirical data on the skeleton . . . . . . . . . . . . . . . . 71

C.2.8 Proof of Lemma C.2: Putting everything together . . . . . . . . . . . . 72

C.3 Amount of exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

C.3.1 Idea of the proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

C.3.2 Preliminaries: Exploration visit counts and truncated regularization 74

C.3.3 Part I: Uniform exploration guarantees . . . . . . . . . . . . . . . . . . 74

C.3.4 Part II: Post burn-in properties & the trigger effect . . . . . . . . . . . 76

C.3.5 Part III: Post burn-in quality of exploration . . . . . . . . . . . . . . . 79

C.3.6 Part IV: The high probability exploration barrier . . . . . . . . . . . . 84

C.3.7 Part V: First order failure and the skeleton exploration barrier . . . . 87

C.3.8 Part VI: Putting everything together and proving Lemma C.9 . . . . . 89

C.3.9 Auxiliary: Co-exploration travels . . . . . . . . . . . . . . . . . . . . . . . 90

C.4 Amount of panic times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

C.5 Combining everything together and proving Theorem C.1 . . . . . . . . . . . 95

C.6 Auxiliary: Adaptations of standard concentration results . . . . . . . . . . . 95

C.7 Auxiliary: Standard probability results . . . . . . . . . . . . . . . . . . . . . . 96
<table><tr><td>D</td><td>Deviation bounds on MDP specific quantities</td><td>99</td></tr><tr><td>D.1</td><td>A multichain-friendly diameter notion for Markov chains</td><td>100</td></tr><tr><td>D.1.1</td><td>Policy diameter and diameters of Markov decision processes</td><td>100</td></tr><tr><td>D.1.2</td><td>Policy diameter and bias function.</td><td>101</td></tr><tr><td>D.1.3</td><td>Sensitivity of the policy diameter to perturbations</td><td>102</td></tr><tr><td>D.1.4</td><td>Sensitivity of the diameter of MDPs to perturbations.</td><td>103</td></tr><tr><td>D.2</td><td>Results for unichain Markov reward processes</td><td>103</td></tr><tr><td>D.3</td><td>Results for multichain Markov reward processes</td><td>105</td></tr></table>