In any case, since $n \ge 3$ and $A_{m'} \ge 2$,

$$ \log(v_{m'}) \le 4 \log(n) \log(A_{m'}). $$

By Lemma 12 and 13, using the definition of $\Sigma$, for $x \ge 0$, it holds with probability at least $1 - 24 \log(n) \Sigma e^{-x}$, for all $m' \in \mathcal{M}'$,

$$ -\nu(g_{\hat{\theta}_{m'}}^{m'}) \le 80(2\eta_{m'} + \eta_{m'}^2 \hat{A}_{m'}) \left(32(F_{m'}^{\infty})^2 \mathbf{K}_n(p_{\hat{\theta}_{m'}}^{m'}) + \frac{1}{n} y_{m'}^2\right) $$

and

$$ \nu(g_{\hat{\theta}_m}^m) \le 80(2\eta_m + \eta_m^2 \hat{A}_m) \left(32(F_m^\infty)^2 \mathbf{K}_n(p_{\hat{\theta}_m}^m) + \frac{1}{n} y_m^2\right). $$

Injecting this result in (10), since the event $A$ is of probability at least $1 - q_n$, it holds with probability at least $1 - q_n - 24 \log(n) \Sigma e^{-x}$ that for all $m' \in \mathcal{M}'$,

$$ \begin{aligned} & \left(1 - 2560(F_m^\infty)^2(2\eta_{m'} + \eta_{m'}^2 \hat{A}_{m'})\right) \mathbf{K}_n(p_{\hat{\theta}_{m'}}^m) \\ & \le \left(1 + 2560(F_m^\infty)^2(2\eta_m + \eta_m^2 \hat{A}_m)\right) \mathbf{K}_n(p_{\hat{\theta}_m}^m) + \text{Res}(m) + \text{Res}(m') \\ & \quad + 80 \left(\frac{2}{\eta_m} + \hat{A}_m\right) \frac{1}{n}(\sigma_m^2 + x + D_m) + \text{pen}(m) \\ & \quad + 80 \left(\frac{2}{\eta_{m'}} + \hat{A}_{m'}\right) \frac{1}{n}(\sigma_{m'}^2 + x + D_{m'}) - \text{pen}(m'). \end{aligned} \quad (14) $$

Let $\kappa \in (0, 1]$ and for all $m' \in \mathcal{M}$, let

$$ \eta_{m'} = \frac{c\kappa}{\hat{A}_{m'} F_{m'}^\infty} \quad (15) $$

for some numerical constant $c > 0$ to be determined. Let us focus on the first multiplicative term on the left hand side of (14). With that choice of $\eta_{m'}$,

$$ \begin{aligned} 2560(F_{m'}^{\infty})^2(2\eta_{m'} + \eta_{m'}^2 \hat{A}_{m'}) &= 2560(F_{m'}^{\infty})^2 \left( \frac{2c\kappa}{\hat{A}_{m'} F_{m'}^{\infty}} + \frac{c^2\kappa^2}{\hat{A}_{m'}^2 (F_{m'}^{\infty})^2} \hat{A}_{m'} \right) \\ &= 2560 \left( \frac{2c\kappa F_{m'}^{\infty}}{\hat{A}_{m'}} + \frac{c^2\kappa^2}{\hat{A}_{m'}} \right) \\ &\le 2560 (2c\kappa + c^2\kappa^2) \quad \text{since } F_{m'}^{\infty} \le \hat{A}_{m'} \quad \text{and} \quad \hat{A}_{m'} \ge 2 \\ &\le 2560 (2c + c^2) \kappa \quad \text{since } \kappa \in (0, 1]. \end{aligned} $$

Pick $c$ small enough so that $2560(2c + c^2) \le 1$. Therefore,

$$ 2560(F_{m'}^{\infty})^2(2\eta_{m'} + \eta_{m'}^2 \hat{A}_{m'}) \le \kappa. \quad (16) $$

Let us now turn on the penalty term choice in (14). By the definition of $\sigma_{m'}$ in (12), it is smaller than the solution $\sigma'_{m'}$ of

$$ \sigma = \sqrt{D_{m'} \left(1 + \frac{1}{\beta_{m'}} \log \left(\frac{v_{m'} \vee e}{\sigma}\right)\right) + \frac{\hat{A}_{m'}}{\sigma} D_{m'} \left(1 + \frac{1}{\beta_{m'}} \log \left(\frac{v_{m'} \vee e}{\sigma}\right)\right)}, $$
which satisfies

$$ \sigma'_{m'} \geq \sqrt{\hat{A}_{m'} D_{m'} \left(1 + \frac{1}{\beta_{m'}}\right)} $$

and therefore

$$ \begin{aligned} \sigma'_{m'} &\le \sqrt{D_{m'} \left( 1 + \frac{1}{\beta_{m'}} \log \left( \frac{\sqrt{2n\hat{A}_{m'}}}{\sqrt{D_{m'}\left(1+\frac{1}{\beta_{m'}}\right)}} \vee e \right) \right)} \\ &\quad + \sqrt{\frac{\hat{A}_{m'} D_{m'}}{1+\frac{1}{\beta_{m'}}}} \left( 1 + \frac{1}{\beta_{m'}} \underbrace{\log \left( \frac{\sqrt{2n\hat{A}_{m'}}}{\sqrt{D_{m'}\left(1+\frac{1}{\beta_{m'}}\right)}} \vee e \right)}_{\mathbf{T}} \right) \\ &= \sqrt{D_{m'}\left(1+\frac{1}{\beta_{m'}}\right)} \left( \sqrt{\frac{1+\frac{1}{\beta_{m'}}\mathbf{T}}{1+\frac{1}{\beta_{m'}}}} + \sqrt{\hat{A}_{m'}\frac{1+\frac{1}{\beta_{m'}}\mathbf{T}}{1+\frac{1}{\beta_{m'}}}} \right). \end{aligned} $$

Since $\mathbf{T} \ge 1$ by its definition and $\hat{A}_{m'} \ge 1$ by assumption,

$$ \begin{aligned} \sigma'_{m'} &\le 2\sqrt{D_{m'} \hat{A}_{m'} \left(1 + \frac{1}{\beta_{m'}}\right) \frac{1 + \frac{1}{\beta_{m'}}\mathbf{T}}{1 + \frac{1}{\beta_{m'}}}} \\ &\le 2\sqrt{\hat{A}_{m'} D_{m'}} \left( \sqrt{1 + \frac{1}{\beta_{m'}}} \vee \frac{1 + \frac{1}{\beta_{m'}} \log \left( \sqrt{2n\hat{A}_{m'}} \right)}{\sqrt{1 + \frac{1}{\beta_{m'}}}} \right). \end{aligned} $$

Because $\log(2n\hat{A}_{m'}) \ge 1$,

$$ \begin{aligned} \sigma'_{m'} &\le 2\sqrt{\frac{\hat{A}_{m'} D_{m'}}{1+\frac{1}{\beta_{m'}}}} \left( 1 + \frac{1}{\beta_{m'}} \log(2n\hat{A}_{m'}) \right) \\ &\le 2\sqrt{\hat{A}_{m'} D_{m'}} \sqrt{1+\frac{1}{\beta_{m'}}} \log(2n\hat{A}_{m'}) \\ &\le 4\sqrt{\hat{A}_{m'} D_{m'}} \sqrt{1+\frac{1}{\beta_{m'}}} \log(n\hat{A}_{m'}). \end{aligned} $$

There exist numerical constants $C_{\text{pen}}$ and $C$ such that if for all $m' \in \mathcal{M}'$,

$$ \text{pen}(m') \ge \frac{C_{\text{pen}}}{\kappa} \hat{A}_{m'}^2 F_{m'}^{\infty} \left(1 + \frac{1}{\beta_{m'}}\right) \log(n\hat{A}_{m'})^2 \frac{D_{m'}}{n}, \quad (17) $$

with the choice of $\eta_{m'}$ in (15) and (16), and taking into account that (17) ensures that the term $\text{Res}(m')$ and $\text{Res}(m)$ are absorbed by the penalty terms (recall
with Lemma 11 that $\mathrm{Res}(m') = 6F_m^{\infty}n^{-(1+\alpha)}$, (14) becomes, for all $x \ge 0$, with probability at least $1 - q_n - 24\log(n)\Sigma e^{-x}$, for all $m' \in \mathcal{M}'$,

$$ (1-\kappa)\mathbf{K}_n(p_{\theta_{m'}}^{m'}) \le (1+\kappa)\mathbf{K}_n(p_{\theta_m}^m) + 2\mathrm{pen}(m) + \frac{C}{\kappa} [\hat{A}_{m'} F_{m'}^{\infty} + \hat{A}_m F_m^{\infty}] \frac{x}{n}. \quad (18) $$

Let us distinguish the final result between Theorem 2 and 4.

* For Theorem 2, (17) reads

$$ \mathrm{pen}(m') \ge \frac{C_{\mathrm{pen}}}{\kappa} A_{m'}^2 \log(\varepsilon^{-1}) \left(1 + \frac{1}{\beta_{m'}}\right) \log(nA_{m'})^2 \frac{D_{m'}}{n} $$

and (18) becomes: for all $x \ge 0$, with probability at least $1-24\log(n)\Sigma e^{-x}$, for all $m' \in \mathcal{M}'$,

$$ (1-\kappa)\mathbf{K}_n(p_{\theta_{m'}}^{m'}) \le (1+\kappa)\mathbf{K}_n(p_{\theta_m}^m) + 2\mathrm{pen}(m) + \frac{2C}{\kappa}(A_{m'} + A_m) \log(\varepsilon^{-1}) \frac{x}{n}. $$

* For Theorem 4, up to a multiplicative constant, since $\hat{A}_{m''} = A_{m''} \log n$, (17) reads

$$ \mathrm{pen}(m') \ge \frac{(1+\alpha)C_{\mathrm{pen}}}{\kappa} A_{m'}^2 B_{m'} (\log n)^3 \left(1 + \frac{1}{\beta_{m'}}\right) \log(nA_{m'})^2 \frac{D_{m'}}{n} $$

and (18) becomes: for all $x \ge 0$, with probability at least $1 - 2n^{-\alpha} - 24\log(n)\Sigma e^{-x}$, for all $m' \in \mathcal{M}'$,

$$ (1-\kappa)\mathbf{K}_n(p_{\theta_{m'}}^{m'}) \le (1+\kappa)\mathbf{K}_n(p_{\theta_m}^m) + 2\mathrm{pen}(m) + \frac{(1+\alpha)C}{\kappa}(A_{m'}B_{m'} + A_m B_m) \frac{x(\log n)^2}{n}. $$

## B Proof of Corollaries 3 and 5

Corollary 3 follows directly from the fact that $\mathbb{E}[Z] \le a \int_{t \ge 0} \mathbb{P}(Z \ge at)dt$ for any positive random variable $Z$, and any $a > 0$.

Under Assumptions 1bis, let us first show that $\mathbf{K}_n(p_{\delta}^{m'})$ is bounded for all $\delta$ and $m'$ almost surely. By Assumption 1bis, almost surely, for any $m' \in \mathcal{M}$ and $\delta \in \Theta_{m'}$,

$$ \begin{aligned} \mathbf{K}_n(p_{\delta}^{m'}) &\le \frac{1}{n} \sum_{t=1}^n \mathbb{E} \left[ \left| \log \frac{p_t^*(X_t | \mathcal{F}_{t-1})}{p_{\delta,t}^{m'}(X_t | \mathcal{F}_{t-1})} \right| \mathcal{F}_{t-1} \right] \\ &\le \frac{1}{n} \sum_{t=1}^n \left( B_{m'} + B_{m'} \int_1^{+\infty} \mathbb{P} \left( \left| \log \frac{p_t^*(X_t | \mathcal{F}_{t-1})}{p_{\delta,t}^{m'}(X_t | \mathcal{F}_{t-1})} \right| \ge B_{m'} y \mid \mathcal{F}_{t-1} \right) dy \right) \\ &\le 2B_{m'}. \end{aligned} \quad (19) $$

To conclude, assume that there exist $A(n), B(n)$ such that $\sup_{m \in \mathcal{M}} B_m \le B(n)$, $\sup_{m \in \mathcal{M}} A_m \le A(n)$, so that by Theorem 4, with probability at least
$$1 - 2n^{-\alpha} - 24 \log(n) \Sigma e^{-x},$$

$$ (1 - \kappa)\mathbf{K}_n(\tilde{p}) \le \inf_{m \in \mathcal{M}} \left( (1 + \kappa) \inf_{\theta \in \Theta^{D_m}} \mathbf{K}_n(p_{\theta}^m) + 2\mathrm{pen}(m) \right) + \frac{2(1 + \alpha)C'}{\kappa} A(n)B(n)^2 \frac{(\log n)^2 x}{n}, $$

and use that for any random variable $Z$ such that $Z \le M$ a.s. for some constant $M > 0$, $\mathbb{E}[Z] \le \int_{t=0}^{M} \mathbb{P}(Z \ge t)dt$, so that for all $\kappa \in (0, 1]$,

$$ (1 - \kappa)\mathbb{E}[\mathbf{K}_n(p_{\theta^{\hat{m}}})] \le \mathbb{E}\left[\inf_{m \in \mathcal{M}} \left( (1 + \kappa) \inf_{\theta \in \Theta^{D_m}} \mathbf{K}_n(p_{\theta}^m) + 2\mathrm{pen}(m) \right)\right] + 4B(n)n^{-\alpha} + \frac{48(1 + \alpha)C'}{\kappa}\Sigma A(n)B(n)^2 \frac{(\log n)^3}{n}, $$

and the last term dominates the second to last one when $\alpha \ge 1$.

# C Proof of the Lemmas

## C.1 Proof of Lemma 11

For any $m' \in \mathcal{M}$ and $\theta \in \Theta_{m'}$

$$ |\mathbf{K}_n(p_{\theta}^{m'}) - \tilde{\mathbf{K}}_n(p_{\theta}^{m'})| \le \frac{1}{n} \sum_{t=1}^{n} \mathbb{E} \left[ \left| \log \frac{p_t^*(X_t)}{p_{\theta,t}^{m'}(X_t)} \right| \mathbf{1}_{f_A^t(X_t) \ge 1} \middle| \mathcal{F}_{t-1} \right]. $$

Let $y \ge 0$ to be determined later. Let $Y_t = \left| \log \frac{p_t^*(X_t)}{p_{\theta,t}^{m'}(X_t)} \right|$. Then,

$$ \begin{aligned} \mathbb{E}[Y_t \mathbf{1}_{f_A^t(X_t) \ge 1} | \mathcal{F}_{t-1}] &= \mathbb{E}[Y_t \mathbf{1}_{f_A^t(X_t) \ge 1} \mathbf{1}_{B_{m'}^{-1}Y_t > y} | \mathcal{F}_{t-1}] + \mathbb{E}[Y_t \mathbf{1}_{f_A^t(X_t) \ge 1} \mathbf{1}_{B_{m'}^{-1}Y_t \le y} | \mathcal{F}_{t-1}] \\ &\le \mathbb{E}[Y_t \mathbf{1}_{B_{m'}^{-1}Y_t > y} | \mathcal{F}_{t-1}] + B_{m'} y \mathbb{E}[\mathbf{1}_{f_A^t(X_t) \ge 1} | \mathcal{F}_{t-1}] \\ &= B_{m'} \left( \mathbb{E}[B_{m'}^{-1}Y_t \mathbf{1}_{B_{m'}^{-1}Y_t > y} | \mathcal{F}_{t-1}] + y \mathbb{E}[\mathbf{1}_{f_A^t(X_t) \ge 1} | \mathcal{F}_{t-1}] \right). \end{aligned} $$

By Assumption 1bis, conditionally to $\mathcal{F}_{t-1}$, $B_{m'}^{-1}Y_t$ is stochastically dominated by $1 \vee E$ where $E$ is an exponentially distributed random variable with parameter 1. Therefore, for $y \ge 1$, a.s.,

$$ \mathbb{E}[B_{m'}^{-1}Y_t \mathbf{1}_{B_{m'}^{-1}Y_t > y} | \mathcal{F}_{t-1}] \le \mathbb{E}[(E \vee 1) \mathbf{1}_{E \vee 1 \ge y} | \mathcal{F}_{t-1}] = \mathbb{E}[E \mathbf{1}_{E \ge y} | \mathcal{F}_{t-1}] \le (1+y)e^{-y}. $$

Finally, since $\mathbb{P}(f_A^t(X_t) \ge 1 | \mathcal{F}_{t-1}) \le 2n^{-(1+\alpha)}$ a.s. by assumption, it holds almost surely that

$$ \begin{aligned} \mathbb{E}[Y_t \mathbf{1}_{f_A^t(X_t) \ge 1} | \mathcal{F}_{t-1}] &\le B_{m'} \left( (1+y)e^{-y} + y \mathbb{P}(f_A^t(X_t) \ge 1 | \mathcal{F}_{t-1}) \right) \\ &\le B_{m'} \left( (1+y)e^{-y} + \frac{2y}{n^{1+\alpha}} \right). \end{aligned} $$
Pick $y = \log\left(\frac{n^{1+\alpha}}{2}\right) \ge 1$. Thus,

$$
\begin{aligned}
\mathbb{E} \left[ Y_t \mathbf{1}_{f_A^t(X_t) \ge 1} \middle| \mathcal{F}_{t-1} \right] &\le \frac{2B_{m'}}{n^{1+\alpha}} \left( 1 + 2 \log \left( \frac{n^{1+\alpha}}{2} \right) \right) \\
&\le 6B_{m'} (1+\alpha) \frac{\log n}{n^{1+\alpha}}.
\end{aligned}
$$

Therefore, $|\mathbf{K}_n(p_\theta^{m'}) - \tilde{\mathbf{K}}_n(p_\theta^{m'})| \le 6B_{m'}(1+\alpha) \frac{\log n}{n^{1+\alpha}}$.

## C.2 Proof of Lemma 12

Fix $m' \in \mathcal{M}$. Recall that for any $\delta, \eta \in \Theta_{m'}$,

$$ \nu(g_{\delta}^{m'}) - \nu(g_{\eta}^{m'}) = \frac{1}{n} \sum_{t=1}^{n} \int \log \left( \frac{p_{\eta,t}^{m'}(x_t|\mathcal{F}_{t-1})}{p_{\delta,t}^{m'}(x_t|\mathcal{F}_{t-1})} \right) \mathbf{1}_{f_A^t(x_t)<1} (d\delta_{X_t}(x_t) - p_t^*(x_t|\mathcal{F}_{t-1})d\mu(x_t)), $$

where $\delta_a$ is the Dirac measure in $a$.

We extend $\Theta_{m'}$ into $\Theta_{m'} \cup \{\star\}$ by defining $p_{\star}^{m'} = p^{\star}$, so that when $\eta = \star$, $\nu(g_{\eta}^{m'}) = 0$ and the formula above becomes $\nu(g_{\delta}^{m'})$. We want to control this uniformly over $\delta, \eta \in \Theta_{m'} \cup \{\star\}$.

Fix $\delta, \eta \in \Theta_{m'} \cup \{\star\}$. For any $t \in [n]$, let

$$ \Delta_t = \int \log \left( \frac{p_{\eta,t}^{m'}(x_t|\mathcal{F}_{t-1})}{p_{\delta,t}^{m'}(x_t|\mathcal{F}_{t-1})} \right) \mathbf{1}_{f_A^t(x_t)<1} (d\delta_{X_t}(x_t) - p_t^*(x_t|\mathcal{F}_{t-1})d\mu(x_t)). $$

For any $t \in [n+1]$, let $M_t = \sum_{s=1}^{t-1} \Delta_s$ (in particular, $M_1 = 0$), so that $\frac{1}{n}M_{n+1} = \nu(g_{\delta}^{m'}) - \nu(g_{\eta}^{m'})$.

$(M_t)_{t \ge 1}$ is a $(\sigma(\mathcal{F}_{t-1}))_{t \ge 1}$-martingale. For $\ell \ge 2$, let $C_1^{\ell} = 0$ and for $t \ge 2$, let

$$ C_t^{\ell} = \sum_{s=1}^{t-1} \mathbb{E}[\Delta_s^{\ell} | \mathcal{F}_{t-1}]. $$

Note that for all $s \in [n]$,

$$ |\Delta_s| \le 2 \int \left| \log \frac{p_{\eta,s}^{m'}(x_s|\mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(x_s|\mathcal{F}_{s-1})} \right| \mathbf{1}_{f_A^s(x_s)<1} \frac{d\delta_{X_s}(x_s) + p_s^*(x_s|\mathcal{F}_{s-1})d\mu(x_s)}{2}, $$

so that by convexity of $x \mapsto |x|^{\ell}$,

$$
\begin{aligned}
|C_t^\ell| &\le \sum_{s=1}^{t-1} \mathbb{E} \left[ 2^\ell \int \left| \log \frac{p_{\eta,s}^{m'}(x_s|\mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(x_s|\mathcal{F}_{s-1})} \right|^\ell \mathbf{1}_{f_A^s(x_s)<1} \frac{d\delta_{X_s}(x_s) + p_s^*(x_s|\mathcal{F}_{s-1})d\mu(x_s)}{2} \middle| \mathcal{F}_{s-1} \right] \\
&= 2^\ell \sum_{s=1}^{t-1} \int \left| \log \frac{p_{\eta,s}^{m'}(x_s|\mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(x_s|\mathcal{F}_{s-1})} \right|^\ell \mathbf{1}_{f_A^s(x_s)<1} p_s^*(x_s|\mathcal{F}_{s-1})d\mu(x_s). \quad (20)
\end{aligned}
$$
Let

$$
R_{\infty,n}(\delta, \eta) = \max_{1 \le s \le n} \sup_{x \in \mathcal{X}} \left( \left| \log \frac{p_{\eta,s}^{m'}(x|\mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(x|\mathcal{F}_{s-1})} \right| \mathbf{1}_{f_A^s(x)<1} \right) \quad (21)
$$

and

$$
R_{2,n}(\delta, \eta)^2 = 2 \sum_{s=1}^{n} \mathbb{E} \left[ \left( \log \frac{p_{\eta,s}^{m'}(X_s | \mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(X_s | \mathcal{F}_{s-1})} \right)^2 \mathbf{1}_{f_A^s(X_s) < 1} \middle| \mathcal{F}_{s-1} \right].
$$

Under Assumptions **1**, **2** and **4**, almost surely, for all $x \in \mathcal{X}$ and $s \in [n]$,
$\mathbf{1}_{f_A^s(x)<1} = 1$ and therefore

$$
R_{\infty,n}(\delta, \eta) = \max_{1 \le s \le n} \sup_{x \in \mathcal{Q}} \left| \log \frac{p_{\theta,s}^{m}(x)}{p_{\delta,s}^{m}(x)} \right| \text{ almost surely.}
$$

In what follows, when using the notation $R_\infty(\delta, \eta)$, we will actually mean the
right hand term, which is $\mathcal{F}_{n-1}$-measurable as a supremum of a countable family
of measurable functions.

Secondly, under Assumptions **1bis**, **2bis** and **4bis**, for all $x \in \mathcal{X}$ and $s \in [n]$, with $O_x$ the open set of Assumption **4bis**, the restriction of the function $f_A^s$ to $O_x \cup \{x\}$ is continuous at $x$. Therefore, for all $s \in [n]$, if $f_A^s(x) < 1$ for all $s \in [n]$, the function

$$
y \in O_x \cup \{x\} \mapsto \left| \log \frac{p_{\eta,s}^{m'}(y|\mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(y|\mathcal{F}_{s-1})} \right| \mathbf{1}_{f_A^s(y)<1}
$$

is continuous at $x$. Thus, for any dense countable subset $\mathcal{Q}$ of $\mathcal{X}$ and any $y \in \mathcal{X}$
and $s \in [n]$, if $f_A^s(y) < 1$,

$$
\sup_{x \in \mathcal{Q}} \left( \left| \log \frac{p_{\eta,s}^{m'}(x|\mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(x|\mathcal{F}_{s-1})} \right| \mathbf{1}_{f_A^s(x)<1} \right) \ge \left| \log \frac{p_{\eta,s}^{m'}(y|\mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(y|\mathcal{F}_{s-1})} \right| \mathbf{1}_{f_A^s(y)<1},
$$

and if $f_A^s(y) \ge 1$, then the right hand side is zero and so the inequality still
holds. Therefore, (21) can be rewritten as

$$
R_{\infty,n}(\delta, \eta) = \max_{1 \le s \le n} \sup_{x \in \mathcal{Q}} \left( \left| \log \frac{p_{\eta,s}^{m'}(x|\mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(x|\mathcal{F}_{s-1})} \right| \mathbf{1}_{f_A^s(x)<1} \right),
$$

for any dense countable subset $\mathcal{Q}$ of $\mathcal{X}$. Since this is a supremum of a countable family of $\mathcal{F}_{n-1}$-measurable functions, $R_{\infty,n}(\delta, \eta)$ is $\mathcal{F}_{n-1}$-measurable.

Injecting these quantities into (20) shows that

$$
|C_t^\ell| \le 2^{\ell-1} R_{\infty,n}(\delta, \eta)^{\ell-2} R_{2,n}(\delta, \eta)^2,
$$

and since $2^{\ell-1} \le \ell!$ for all $\ell \ge 2$,

$$
|C_{n+1}^{\ell}| \le \frac{\ell!}{2} R_{2,n}(\delta, \eta)^2 R_{\infty,n}(\delta, \eta)^{\ell-2}. \quad (22)
$$

The next proposition is a direct consequence of Lemma 3.3 in [36] and can be
found in [4],
**Proposition 14.** Let $(M_t)_{t \ge 0}$ be a $(\mathcal{F}_t)_{t \ge 0}$-martingale with $M_0 = 0$. Let $t \ge 1$ and assume that there exists nonnegative random variables $R_2$ and $R_\infty$ such that for all $\ell \ge 2$,

$$ \sum_{s=1}^{t} \mathbb{E} \left[ (M_s - M_{s-1})^{\ell} \mid \mathcal{F}_{s-1} \right] \le \frac{\ell!}{2} R_2^2 R_{\infty}^{\ell-2}. $$

Then, for all $\sigma, \sigma', x \ge 0$,

$$ \mathbb{P} \left( M_t \ge \sigma \sqrt{2x} + \sigma'x, R_2 \le \sigma \text{ and } R_\infty \le \sigma' \right) \le e^{-x}. \quad (23) $$

*Proof of Proposition 14.* Let $C_0^\ell = 0$ and $C_s^\ell = \sum_{u=1}^s \mathbb{E}[(M_u - M_{u-1})^\ell | \mathcal{F}_{u-1}]$ for all $t \ge s \ge 1$ and $\ell \ge 2$. Lemma 3.3 of [36] gives that for all $\lambda > 0$, the sequence $(\mathcal{E}_s)_{s \ge 0}$ defined by

$$ \mathcal{E}_s = \exp \left( \lambda M_s - \sum_{\ell \ge 2} \frac{\lambda^\ell}{\ell!} C_s^\ell \right) $$

is a supermartingale. In particular, $\mathbb{E}(\mathcal{E}_t) \le \mathbb{E}(\mathcal{E}_0) = 1$. Therefore,

$$ \forall \lambda \ge 0 \quad \mathbb{E} \left[ \exp \left( \lambda M_t - \frac{(\lambda R_2)^2}{2} \sum_{k \ge 0} (\lambda R_\infty)^k \right) \right] \le 1. \quad (24) $$

By (24), for all $\sigma, \sigma', \lambda \ge 0$,

$$ \mathbb{E} \left[ \exp \left( \lambda M_t - \frac{(\lambda R_2)^2}{2} \sum_{k \ge 0} (\lambda R_\infty)^k \right) \mathbf{1}_{R_2 \le \sigma} \mathbf{1}_{R_\infty \le \sigma'} \right] \le 1, $$

and therefore for all $\lambda \in [0, (\sigma')^{-1})$,

$$ \mathbb{E}[\exp(\lambda M_t) \mathbf{1}_{R_2 \le \sigma} \mathbf{1}_{R_\infty \le \sigma'}] \le \exp \left( \frac{\lambda^2 \sigma^2}{2(1 - \lambda \sigma')} \right). \quad (25) $$

Finally, for $y \ge 0$, for all $\lambda \ge 0$,

$$ \begin{aligned} \mathbb{P}(M_t \ge y, R_2 \le \sigma \text{ and } R_\infty \le \sigma') &= \mathbb{P}(e^{\lambda M_t} \ge e^{\lambda y}, R_2 \le \sigma \text{ and } R_\infty \le \sigma') \\ &= \mathbb{P}(e^{\lambda M_t} \mathbf{1}_{R_2 \le \sigma} \mathbf{1}_{R_\infty \le \sigma'} \ge e^{\lambda y}) \end{aligned} $$

where the last equality holds because $e^{\lambda M_t}$ and $e^{\lambda y}$ are positive. Therefore, by the Markov inequality and (25), for all $\lambda \in [0, (\sigma')^{-1})$,

$$ \mathbb{P}(M_t \ge y, R_2 \le \sigma \text{ and } R_\infty \le \sigma') \le \exp \left( \frac{\lambda^2 \sigma^2}{2(1 - \lambda \sigma')} - \lambda y \right). $$
Classic Bernstein inequality's proofs show that an optimal choice of $\lambda$ leads to

$$ \mathbb{P}(M_t \ge y, R_2 \le \sigma \text{ and } R_\infty \le \sigma') \le \exp\left(-\frac{\sigma^2}{(\sigma')^2} h\left(\frac{\sigma'y}{\sigma^2}\right)\right), $$

where $h$ is the function defined by $h(u) = 1 + u - \sqrt{1 + 2u}$ for all $u \ge 0$. Since, its inverse function $h^{-1}$ is such that $h^{-1}(u) = u + \sqrt{2u}$ for all $u \ge 0$, choosing $y$ so that

$$ \frac{\sigma^2}{(\sigma')^2} h\left(\frac{\sigma'y}{\sigma^2}\right) = x $$

leads to

$$ y = \frac{\sigma^2}{\sigma'} h^{-1}\left(\frac{(\sigma')^2 x}{\sigma^2}\right) = \sigma'x + \sigma\sqrt{2x}. $$

Hence the result.

□

Applying Proposition 14 to the martingale $M_t$ ensures that for all $\sigma, \sigma', x \ge 0$ and for all $\delta, \eta \in \Theta_{m'} \cup \{\star\}$,

$$ \mathbb{P} \left( n\nu(g_{\delta}^{m'}) - n\nu(g_{\eta}^{m'}) \ge \sigma\sqrt{2x} + \sigma'x, R_2(\delta, \eta) \le \sigma \text{ and } R_{\infty}(\delta, \eta) \le \sigma' \right) \le e^{-x}. $$

From this control of the increments of the process $\nu$, we aim to apply the following slight modification of Theorem 5 of [4], to account for a Hölder relation between $R_2$, $R_\infty$ and the norms over $\Theta_{m'}$.

**Theorem 15.** Let $(Y_t)_{t \in S}$ be a family of real-valued random variables, indexed by a countable subset $S$ of a linear space $E$ of finite dimension $D$. Let $R_2$ and $R_\infty$ be two nonnegative random functions on $S \times S$ that satisfy the triangle inequality. Assume that the increments $Y_s - Y_u$ satisfy

$$ \begin{array}{l} \forall \sigma, \sigma', x \ge 0, \quad \forall s, u \in S, \\ \mathbb{P}(Y_s - Y_u \ge \sigma\sqrt{2x} + \sigma'x, R_2(s, u) \le \sigma \text{ and } R_\infty(s, u) \le \sigma') \le e^{-x}. \end{array} \quad (26) $$

Assume that there exists two deterministic seminorms $N_2$ and $N_\infty$ on $E$, a positive constant $\beta$ and nonnegative constants $v, w$, such that for all $s, u \in S$,

$$ \left\{ \begin{array}{l} R_2(s, u) \le N_2(s-u)^\beta \le v^\beta, \\ R_\infty(s, u) \le N_\infty(s-u)^\beta \le w^\beta. \end{array} \right. \quad (27) $$

Let $c \ge 0$. Define for all $x, \sigma \ge 0$,

$$ \Psi(\sigma, x) = 30 \left[ (\sigma \wedge v^\beta) \sqrt{x + D + \frac{D}{\beta} \log \left( \frac{v^\beta \vee (cw^\beta)}{\sigma} \vee e \right)} \right. \\ \left. + \left( \frac{\sigma}{c} \wedge w^\beta \right) \left( x + D + \frac{D}{\beta} \log \left( \frac{v^\beta \vee (cw^\beta)}{\sigma} \vee e \right) \right) \right] $$
with the convention $\frac{\sigma}{0} = +\infty$. Finally, define for all $t, t_0 \in S$, $\Delta_c(t, t_0) = R_2(t, t_0) \vee (cR_\infty(t, t_0))$. Then, for any $t_0 \in S$, $x \ge 0$ and $\sigma > 0$,

$$ \mathbb{P} \left( \sup_{t \in S} \frac{Y_t - Y_{t_0}}{\Delta_c(t, t_0)^2 + \sigma^2} \ge 4\sigma^{-2} \Psi(\sigma, x) \right) \le 2 \left( \log \left( \frac{v^\beta \vee (cw^\beta)}{\sigma} \right) \vee 0 + 1 \right) e^{-x}. \quad (28) $$

The salient differences in the proof of this Theorem compared to Theorem 5 of [4] are detailed in Section C.4.

We take $S$ as either $\Theta_{m'}$ or a dense countable subset of $\Theta_{m'}$; the two choices are equivalent under Assumption 3. Such a dense countable subset always exists since $\Theta_{m'}$ is parametric. Let us now check the assumptions of the theorem.

By definition,

$$ \left\{ \begin{array}{ll} \forall \delta, \eta \in \Theta_{m'} \cup \{\star\}, & R_{2,n}(\delta, \eta) \le F_{m'}^{\infty} \sqrt{2n}, \\ \forall \delta, \eta \in \Theta_{m'}, & R_{2,n}(\delta, \eta) \le F_{m'}^{\text{höl}} \|\delta - \eta\|_{m'}^{\beta_{m'}} \sqrt{2n}. \end{array} \right. \quad (29) $$

Since $R_{2,n}(\delta, \eta)$ is the Euclidean norm of the vector whose coordinate $s \in [n]$ is the $\mathbf{L}^2(\mathcal{X}, p_s^*(\cdot | \mathcal{F}_{s-1})d\mu)$ distance between $\log p_{\eta,s}^{m'}(\cdot | \mathcal{F}_{s-1})\mathbf{1}_{f_{\mathcal{A}}^s(\cdot) < 1}$ and $\log p_{\delta,s}^{m'}(\cdot | \mathcal{F}_{s-1})\mathbf{1}_{f_{\mathcal{A}}^s(\cdot) < 1}$, it satisfies the triangular inequality: for all $\eta, \delta, \theta \in \Theta_{m'} \cup \{\star\}$,

$$ R_{2,n}(\delta, \eta) \le R_{2,n}(\delta, \theta) + R_{2,n}(\theta, \eta). \quad (30) $$

Likewise,

$$ \left\{ \begin{array}{ll} \forall \delta, \eta \in \Theta_{m'} \cup \{\star\}, & R_{\infty,n}(\delta, \eta) \le F_{m'}^{\infty}, \\ \forall \delta, \eta \in \Theta_{m'}, & R_{\infty,n}(\delta, \eta) \le F_{m'}^{\text{höl}} \|\delta - \eta\|_{m'}^{\beta_{m'}}, \end{array} \right. \quad (31) $$

and for all $\eta, \delta, \theta \in \Theta_{m'} \cup \{\star\}$

$$ R_{\infty,n}(\delta, \eta) \le R_{\infty,n}(\delta, \theta) + R_{\infty,n}(\theta, \eta). \quad (32) $$

Identify $\Theta_{m'} \cup \{\star\}$ with the subset $\tilde{\Theta}_{m'}$ of the vector space $\mathbb{R}^{D_{m'}+1}$ of generic element $(\delta, u)$ with $\delta \in \mathbb{R}^{D_{m'}}$ and $u \in \mathbb{R}$, defined as

$$ \tilde{\Theta}_{m'} = \{(\theta, 0) : \theta \in \Theta_{m'}\} \cup \{(\bar{\theta}^{m'}, 1)\}, $$

for some fixed $\bar{\theta}^{m'} \in \Theta_{m'}$. Endow the vector space $\mathbb{R}^{D_{m'}+1}$ with the norms

$$ \tilde{N}_{\infty}((\delta, u)) = (F_{m'}^{\text{höl}} \|\delta\|_{m'}^{\beta_{m'}} + F_{m'}^{\infty} |u|^{\beta_{m'}})^{1/\beta_{m'}} \quad \text{and} \quad \tilde{N}_2((\delta, u)) = (2n)^{1/(2\beta_{m'})} \tilde{N}_{\infty}((\delta, u)). $$

Under Assumption 2bis, for any $\delta, \eta \in \Theta_{m'}$, by (29) and (31),

$$ \left\{ \begin{array}{ll} R_{2,n}(\delta, \eta) \le F_{m'}^{\text{höl}} \|\delta - \eta\|_{m'}^{\beta_{m'}} \sqrt{2n} = \tilde{N}_2((\delta, 0) - (\eta, 0))^{\beta_{m'}} & \\ R_{\infty,n}(\delta, \eta) \le F_{m'}^{\text{höl}} \|\delta - \eta\|_{m'}^{\beta_{m'}} = \tilde{N}_{\infty}((\delta, 0) - (\eta, 0))^{\beta_{m'}}, & \end{array} \right. $$
and both inequalities extend to $\eta = \star$ since, for $R_{2,n}$,

$$
\begin{align*}
R_{2,n}(\delta, \star) &\le F_{m'}^{\infty} \sqrt{2n} \\
&\le \left[ (F_{m'}^{\text{höl}})^{1/\beta_{m'}} \|\delta - \bar{\theta}^{m'}\|_{m'} (2n)^{1/(2\beta_{m'})} + (F_{m'}^{\infty})^{1/\beta_{m'}} (2n)^{1/(2\beta_{m'})} \right]^{\beta_{m'}} \\
&= \tilde{N}_2((\delta, 0) - (\bar{\theta}^{m'}, 1))^{\beta_{m'}}
\end{align*}
$$

and likewise for $\delta = \star$ and for $R_{\infty,n}$. Recall that we defined

$$
\hat{A}_{m'} = F_{m'}^{\text{höl}} M_{m'}^{\beta_{m'}} + F_{m'}^{\infty} \quad \text{and} \quad v_{m'} = \hat{A}_{m'} \sqrt{2n},
$$

in (11), so that $\tilde{N}_2(\delta - \eta)^{\beta_{m'}} \le v_{m'}$ and $\tilde{N}_\infty(\delta - \eta)^{\beta_{m'}} \le \hat{A}_{m'}$ for all $\delta, \eta \in \tilde{\Theta}_{m'}$.

We may now apply Theorem 15 to the process $Y_\delta = n\nu(g_\delta^{m'})$ indexed by
$\delta \in \Theta_{m'} \cup \{\star\}$, with $c=0$: for all $\sigma > 0$ and $x \ge 0$, let

$$
\Psi(\sigma, x) = 30 \left[ (\sigma \wedge v_{m'}) \sqrt{x + D_{m'} + \frac{D_{m'}}{\beta_{m'}} \log\left(\frac{v_{m'}}{\sigma} \vee e\right)} \right. \\
\left. \qquad + \hat{A}_{m'} \left(x + D_{m'} + \frac{D_{m'}}{\beta_{m'}} \log\left(\frac{v_{m'}}{\sigma} \vee e\right)\right) \right].
$$

Then, for all $\theta \in \Theta_{m'} \cup \{\star\}$, $\sigma > 0$ and $x \ge 0$,

$$
\mathbb{P} \left( \sup_{\delta \in \Theta_{m'} \cup \{\star\}} \frac{Y_{\delta} - Y_{\theta}}{R_{2,n}(\delta, \theta)^2 + \sigma^2} \ge 4\sigma^{-2} \Psi(\sigma, x + D_{m'}) \right) \\
\le \left( 2 \log \left( \frac{v_{m'}}{\sigma} \right) \vee 0 + 1 \right) e^{-(x+D_{m'})}.
$$

In particular, by taking the union bound over $m' \in \mathcal{M}$ for $\theta = \star$, for any fam-
ily of positive numbers $(y_{m'})_{m' \in \mathcal{M}}$, with probability at least $1 - e^{-x} \sum_{m' \in \mathcal{M}} \left( 2 \log \left( \frac{v_{m'}}{y_{m'}} \right) \vee 0 + 1 \right) e^{-D_{m'}}$,
for all $m' \in \mathcal{M}$,

$$
\sup_{\delta \in \Theta_{m'}} \left( \frac{n \nu(g_{\delta}^{m'})}{R_{2,n}(\delta, \star)^2 + y_{m'}^2} \right) \\
\le \frac{120}{y_{m'}^2} \left[ y_{m'} \sqrt{x + D_{m'}} + (y_{m'} \wedge v_{m'}) \sqrt{D_{m'} \left( 1 + \frac{1}{\beta_{m'}} \log \left( \frac{v_{m'}}{y_{m'}} \vee e \right) \right)} \right. \\
\left. \qquad + \hat{A}_{m'}(x + D_{m'}) + \hat{A}_{m'} D_{m'} \left( 1 + \frac{1}{\beta_{m'}} \log \left( \frac{v_{m'}}{y_{m'}} \vee e \right) \right) \right].
$$
For each $m' \in \mathcal{M}$, let $\sigma_{m'}$ be the solution of the equation

$$ \sigma = \left(1 \wedge \frac{v_{m'}}{\sigma}\right) \sqrt{D_{m'} \left(1 + \frac{1}{\beta_{m'}} \log \left(\frac{v_{m'}}{\sigma} \vee e\right)\right)} \\ + \frac{\hat{A}_{m'}}{\sigma} D_{m'} \left(1 + \frac{1}{\beta_{m'}} \log \left(\frac{v_{m'}}{\sigma} \vee e\right)\right)} $$

which exists since the right hand side is positive and non-increasing on $(0, +\infty)$. For any family $(y_{m'})_{m' \in \mathcal{M}}$ such that $y_{m'} \ge \sigma_{m'}$ for all $m' \in \mathcal{M}$, for any $x \ge 0$, it holds with probability at least $1 - e^{-x} \sum_{m' \in \mathcal{M}} \left(2 \log \left(\frac{v_{m'}}{y_{m'}}\right) \vee 0 + 1\right) e^{-D_{m'}}$ that for all $m' \in \mathcal{M}$,

$$ \sup_{\delta \in \Theta_{m'}} \left( \frac{n\nu(g_{\delta}^{m'})}{R_{2,n}(\delta, \star)^2 + y_{m'}^2} \right) \le \frac{120}{y_{m'}} \left( \sigma_{m'} + \sqrt{x + D_{m'}} + \frac{\hat{A}_{m'}}{y_{m'}}(x + D_{m'}) \right). $$

Let $\eta \in (0, 1)$ and $x \ge 0$ and fix for each $m' \in \mathcal{M}$

$$ y_{m'} = \eta^{-1} \sqrt{\sigma_{m'}^2 + x + D_{m'}}, $$

then with probability at least $1 - e^{-x} \sum_{m' \in \mathcal{M}} \left(2 \log \left(\frac{v_{m'}}{y_{m'}}\right) \vee 0 + 1\right) e^{-D_{m'}}$, for all $m' \in \mathcal{M}$,

$$ \sup_{\delta \in \Theta_{m'}} \left( \frac{\nu(g_{\delta}^{m'})}{\frac{1}{n} R_{2,n}(\delta, \star)^2 + \frac{1}{n} y_{m'}^2} \right) \le 120(2\eta + \eta^2 \hat{A}_{m'}), $$

where

* the first term on the right hand side is due to the concavity of $x \in (0, +\infty) \mapsto \sqrt{x}$,

* the second term on the right hand side holds because $x + D_{m'} \le x + D_{m'} + \sigma_{m'}^2 = \eta^2 y_{m'}^2$.

By definition $y_{m'} \ge \eta^{-1}\sqrt{D_{m'}} \ge 1$, and $v_{m'} = \hat{A}_{m'}\sqrt{2n} \ge e$. Therefore,

$$ 2 \log \left( \frac{v_{m'}}{y_{m'}} \right) \vee 0 + 1 \le 3 \log v_{m'}. $$

The control of $-\nu(g_{\delta}^{m'})$ is identical, hence we may control all $|\nu(g_{\delta}^{m'})|$ with probability at least $1 - 6e^{-x} \sum_{m' \in \mathcal{M}} \log(v_{m'})e^{-D_{m'}}$ by union bound. To conclude the proof of the Lemma, note that $\frac{1}{n}R_{2,n}(\delta, \star)^2 = 2V_n(p_{\delta})$.
### C.3 Proof of Lemma 13

Let's begin with a result proved in [46] which we slightly adapt to our situation. It is proved at the end of this section.

**Lemma 16 (Adaptation of Lemma 4 in [46]).** For any probability measures $\mathbb{P}$ and $\mathbb{Q}$ with densities $p$ and $q$, and any $\lambda \in (0, 1/2]$,

$$ \mathbb{P}\left\{\left(\log \frac{p}{q}\right)^2 \mathbf{1}_{|\log\left(\frac{p}{q}\right)| \le \log\left(\frac{1}{\lambda}\right)}\right\} \le 8 \left(1 + \left(\log \frac{1}{\lambda}\right)^2\right) \mathbb{P}\left\{\left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^2 \mathbf{1}_{|\log\left(\frac{p}{q}\right)| \le \log\left(\frac{1}{\lambda}\right)}\right\}. $$

Let us apply Lemma 16 to $p = p_s^*$ and $q = p_{\delta,s}^{m'}$ with $\lambda = \exp(-F_{m'}^{\infty})$ for all $s \in [n]$ and $\delta \in \Theta_{m'}$. By definition of $F_{m'}^{\infty}$, $\lambda \le 1/2$, so that for all $s \in [n]$ and $\delta \in \Theta_{m'}$,

$$ \begin{aligned} & \int \left| \log \frac{p_s^*(x_s | \mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(x_s | \mathcal{F}_{s-1})} \right|^2 \mathbf{1}_{f_A^s(X_s) < 1} p_s^*(x_s | \mathcal{F}_{s-1}) d\mu(x_s) \\ & \le \int \left| \log \frac{p_s^*(x_s | \mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(x_s | \mathcal{F}_{s-1})} \right|^2 \mathbf{1}_{\left| \log \frac{p_s^*(x_s | \mathcal{F}_{s-1})}{p_{\delta,s}^{m'}(x_s | \mathcal{F}_{s-1})} \right| < F_{m'}^{\infty}} p_s^*(x_s | \mathcal{F}_{s-1}) d\mu(x_s) \\ & \le 16h^2 (p_s^*(\cdot | \mathcal{F}_{s-1}), p_{\delta,s}^{m'}(\cdot | \mathcal{F}_{s-1}) | \mathcal{F}_{s-1}) (1 + (F_{m'}^{\infty})^2), \end{aligned} $$

where

$$ h^2(p_t(\cdot | \mathcal{F}_{t-1}), q_t(\cdot | \mathcal{F}_{t-1}) | \mathcal{F}_{t-1}) = \frac{1}{2} \int \left( \sqrt{p_t(x_t | \mathcal{F}_{t-1})} - \sqrt{q_t(x_t | \mathcal{F}_{t-1})} \right)^2 d\mu(x_t). $$

Let us recall a classical relation between the Hellinger distance and the Kullback-Leibler divergence, see for instance in [42, Lemma 7.23]: for any probability measures $P$ and $Q$,

$$ 2h^2(P, Q) \le KL(P, Q). $$

Applying this inequality to the probability measures $P = p_t^*(\cdot | X_1^{t-1})$ and $Q = p_{t,\delta^{m'}}^{m'}(\cdot | X_1^{t-1})$ conditionally to $X_1^{t-1}$ for all $t \in [n]$ shows that

$$ \mathbf{V}_n(p_{\delta}^{m'}) \le 8(1 + (F_{m'}^{\infty})^2)\mathbf{K}_n(p_{\delta}^{m'}) \le 16(F_{m'}^{\infty})^2\mathbf{K}_n(p_{\delta}^{m'}) $$

since $F_{m'}^{\infty} \ge 1$.

**Proof of Lemma 16.** The proof follows exactly the same steps as [46]. Let $r: (0, +\infty) \to \mathbb{R}$ be the function defined implicitly by

$$ \log(x) = 2(x^{1/2} - 1) - r(x)(x^{1/2} - 1)^2. $$
The function $r$ is non-negative, decreasing, and $r(x) \le 2\log(1/x)$ for all $x \in (0, 1/2]$ (see e.g. [34]). Let $\lambda \in (0, 1/2]$. Since for any $x \ge 1$, $|\log(x)| \le 2|x^{1/2} - 1|$,

$$ \mathbb{P}\left\{\left(\log \frac{p}{q}\right)^2 \mathbf{1}_{1 \le \frac{q}{p} \le \frac{1}{\lambda}}\right\} \le 4\mathbb{P}\left\{\left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^2 \mathbf{1}_{1 \le \frac{q}{p} \le \frac{1}{\lambda}}\right\}. $$

Moreover, by definition of $r$,

$$ \begin{aligned} & \mathbb{P}\left\{\left(\log \frac{p}{q}\right)^2 \mathbf{1}_{\lambda \le \frac{q}{p} \le 1}\right\} \\ & \le 8\mathbb{P}\left\{\left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^2 \mathbf{1}_{\lambda \le \frac{q}{p} \le 1}\right\} + 2\mathbb{P}\left\{r^2\left(\frac{q}{p}\right)\left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^4 \mathbf{1}_{\lambda \le \frac{q}{p} \le 1}\right\} \\ & \le 8\mathbb{P}\left\{\left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^2 \mathbf{1}_{\lambda \le \frac{q}{p} \le 1}\right\} + 2r^2(\lambda)\mathbb{P}\left\{\left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^2 \mathbf{1}_{\lambda \le \frac{q}{p} \le 1}\right\} \\ & \le 8\mathbb{P}\left\{\left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^2 \mathbf{1}_{\lambda \le \frac{q}{p} \le 1}\right\} + 8\left(\log \frac{1}{\lambda}\right)^2 \mathbb{P}\left\{\left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^2 \mathbf{1}_{\lambda \le \frac{q}{p} \le 1}\right\}, \end{aligned} $$

where

* the first inequality holds because for any $a, b \in \mathbb{R}$, $(a+b)^2 \le 2a^2 + 2b^2$,

* the second inequality holds because $r$ is decreasing and since $0 \le \frac{q}{p} \le 1$,

$$ \left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^2 \le 1, $$

* the third inequality holds because $r(x) \le 2\log(1/x)$ for $x \in (0, 1/2]$.

All in all,

$$ \mathbb{P}\left\{\left(\log \frac{p}{q}\right)^2 \mathbf{1}_{\lambda \le \frac{q}{p} \le \frac{1}{\lambda}}\right\} \le 8\left(1 + \left(\log \frac{1}{\lambda}\right)^2\right) \mathbb{P}\left\{\left(\frac{q^{1/2}}{p^{1/2}} - 1\right)^2 \mathbf{1}_{\lambda \le \frac{q}{p} \le \frac{1}{\lambda}}\right\}. $$

□

### C.4 Proof of Theorem 15

The proof follows the same lines as the proof of Theorem 5 of [4]. The main difference is that their Proposition 8 is changed into the following one:

**Proposition 17.** Let $(Y_t)_{t \in S}$ be a family of real-valued random variables, indexed by a countable subset $S$ of a linear space $E$ of finite dimension $D$. Let $R_2$ and $R_\infty$ be two nonnegative random functions on $S \times S$ that almost surely satisfy the triangle inequality. Assume that, for all $s, u \in S$, the increments $Y_s - Y_u$
satisfy (26) with respect to $R_2$ and $R_\infty$. Assume that there exists two deterministic seminorms $N_2$ and $N_\infty$ on $E$, a positive constant $\beta$ and nonnegative constants $v, w$ satisfying (27). Fix $t_0 \in S$. For $\sigma, \sigma' \ge 0$, let

$$ \mathcal{B}(\sigma, \sigma') = \{s \in S : R_2(s, t_0) \le \sigma \text{ and } R_\infty(s, t_0) \le \sigma'\}. $$

Then, there exists a numerical constant $\kappa > 0$ (for instance $\kappa = 30$) such that for all $x \ge 0$ and $\sigma, \sigma' > 0$,

$$ \mathbb{P} \left( \sup_{t \in \mathcal{B}(\sigma, \sigma')} (Y_t - Y_{t_0}) \ge \kappa \left[ (\sigma \wedge v^\beta) \sqrt{x + D + \frac{D}{\beta} \log \left( \frac{v^\beta}{\sigma} \vee \frac{w^\beta}{\sigma'} \vee e \right)} + (\sigma' \wedge w^\beta) \left( x + D + \frac{D}{\beta} \log \left( \frac{v^\beta}{\sigma} \vee \frac{w^\beta}{\sigma'} \vee e \right) \right) \right] \right) \le e^{-x}. $$

Following this, the same peeling argument is enough to conclude. Let us now prove this proposition.

Without loss of generality, we may assume that $S$ is finite (see [4]). Note that $\mathcal{B}(\sigma, \sigma') = \mathcal{B}(\sigma \wedge v^\beta, \sigma' \wedge w^\beta)$ by (27), so, in what follows, we assume $\sigma \le v^\beta$ and $\sigma' \le w^\beta$.

**Lemma 18.** There exists a sequence of finite partitions $(A_k)_{k \in \mathbb{N}}$ of $S$ satisfying $A_0 = \{S\}$ and

$$ \left\{ \begin{array}{l} \forall k \in \mathbb{N}, \ A_{k+1} \subset A_k \text{ in the sense that: } \forall B \in A_{k+1}, \exists C \in A_k \text{ s.t. } B \subset C, \\ \forall k \ge 1, \ \forall B \in A_k, \ \forall s, u \in B, \ N_2(s-u) \le 2^{-k/\beta} \sigma^{1/\beta} \quad \text{and} \quad N_\infty(s-u) \le 2^{-k/\beta} (\sigma')^{1/\beta}, \\ \forall k \ge 1, \ |A_k| \le \left( \frac{vw}{(\sigma\sigma')^{1/\beta}} \right)^D 4^{(3+1/\beta)Dk}. \end{array} \right. $$

*Proof of Lemma 18.* Let us recall a result from [14, Lemma 4.5] also used by [7]. This result is originally formulated for norms, but extends naturally to seminorms by applying it to the quotient of $E$ by the kernel of the seminorm.

**Lemma 19.** Let $N$ be an arbitrary seminorm on $S$ and $B_N(0, 1)$ its corresponding unit ball. For all $\delta \in (0, 1]$, the minimum number of balls of radius $\delta$ which is necessary to cover $B_N(0, 1)$ is at most $(1 + 2\delta^{-1})^D$.

In the following proof, we build separately for each seminorm $N_j$ a sequence of partitions $(A_{j,k})_{k \in \mathbb{N}}$ with $j \in \{2, +\infty\}$. The sequence of partitions of Lemma 18 is then obtained by choosing, for $k \ge 0$, the partition $A_k$ defined by

$$ A_k = \{A_2 \cap A_\infty, A_2 \in A_{2,k}, A_\infty \in A_{\infty,k}\}. $$

**For the seminorm $N_2$** let $A_{2,0} = S$. By (27), $S \subset B_{N_2}(0, v)$. Applying Lemma 19 to the norm $v^{-1}N_2$ and $\delta = 2^{-1-1/\beta}v^{-1}\sigma^{1/\beta}$ means that the minimum number of balls of radius $2^{-1-1/\beta}\sigma^{1/\beta}$ which are necessary to cover $B_{N_2}(0, v)$ is upper bounded by $(1 + 2^{2+1/\beta}v\sigma^{-1/\beta})^D \le (2^{3+1/\beta}v\sigma^{-1/\beta})^D$. Let
$(B_1, \dots, B_p)$ be such a minimal covering. Let $C_1 = B_1$ and for $j \in \{2, \dots, p\}$, define the set $C_j$ as

$$C_j = B_j \setminus \bigcup_{i<j} B_i.$$

The sequence $A_{2,1} = (C_j)_{j \in \{1, \dots, p\}}$ forms a partition of $S$, each set of which has a diameter at most $2^{-1/\beta}\sigma^{1/\beta}$.

For $k \ge 1$, proceed by induction using Lemma 19. Assume that there exists a partition $A_{2,k}$ such that $|A_{2,k}| \le (2^{3+1/\beta}v\sigma^{-1/\beta})^D \cdot 2^{(2+1/\beta)D(k-1)}$ and such that each element of $A_{2,k}$ is a subset of a ball of radius $2^{-k/\beta-1}\sigma^{1/\beta}$ for the norm $N_2$. By applying Lemma 19 to $2^{k/\beta+1}\sigma^{-1/\beta}N_2$ and $\delta = 2^{-1/\beta}$, each element of $A_{2,k}$ can be covered by at most $(1+2^{1+1/\beta})^D \le 2^{(2+1/\beta)D}$ balls of radius $2^{-(k+1)/\beta-1}\sigma^{1/\beta}$, and therefore be partitioned into at most $2^{(2+1/\beta)D}$ sets of diameter $2^{-(k+1)/\beta}\sigma^{1/\beta}$, each contained in a ball of radius $2^{-(k+1)/\beta-1}\sigma^{1/\beta}$. $A_{2,k+1}$ is therefore a partition containing at most $(2^{3+1/\beta}v\sigma^{-1/\beta})^D \cdot 2^{(2+1/\beta)Dk}$ elements.

**For the seminorm $N_\infty$** the reasoning is the same and produces a partition $A_{\infty,k+1}$ containing at most $(2^{3+1/\beta}w(\sigma')^{-1/\beta})^D \cdot 2^{(2+1/\beta)Dk}$ element for all $k \ge 0$.

**Final partition** By construction, for all $k \in \mathbb{N}$, $A_{k+1} \subset A_k$. Moreover, for all $k \ge 1$, $A \in A_k$ and $s, u \in A$, $N_2(s-u) \le 2^{-k/\beta}\sigma^{1/\beta}$ and $N_\infty(s-u) \le 2^{-k/\beta}(\sigma')^{1/\beta}$, and finally,

$$ \begin{aligned} |A_k| &\le |A_{2,k}| \cdot |A_{\infty,k}| \\ &\le (2^{3+1/\beta}v\sigma^{-1/\beta})^D (2^{3+1/\beta}w(\sigma')^{-1/\beta})^D \cdot 4^{(2+1/\beta)D(k-1)} \\ &\le \left( \frac{vw}{(\sigma\sigma')^{1/\beta}} \right)^D 4^{(3+1/\beta)Dk} \end{aligned} $$

□

Let $(A_k)_{k \ge 0}$ be a sequence of partitions as in Lemma 18. For all $k \in \mathbb{N}^*$ and all $A \in A_k$, pick a (deterministic) element $t_k(A) \in A$. For any $t \in S$ and $k \ge 1$, there exists a unique $A \in A_k$ such that $t \in A$. Let $\pi_k(t) = t_k(A)$. Let also $\pi_0(t) = t_0$. Since $S$ is finite, the following decomposition holds and contains a finite number of non-zero terms:

$$Y_t - Y_{t_0} = \sum_{k \ge 0} (Y_{\pi_{k+1}(t)} - Y_{\pi_k(t)}).$$

For $k \ge 0$, let $E_k = \{(\pi_k(t), \pi_{k+1}(t)), t \in S\}$ and for $k \ge 1$, let

$$ \begin{cases} z_0 = \frac{3}{2}\sigma\sqrt{2(x + \log(2|E_0|))} + \frac{3}{2}\sigma'(x + \log(2|E_0|)), \\ z_k = 2^{-k}\left(\sigma\sqrt{2(x + \log(2^{k+1}|E_k|))} + \sigma'(x + \log(2^{k+1}|E_k|))\right). \end{cases} $$
Let

$$
\begin{align*}
H &= \frac{3}{2}\sigma\sqrt{2\log(2|E_0|)} + \frac{3}{2}\sigma'\log(2|E_0|) + \sum_{k \ge 1} 2^{-k} \left( \sigma\sqrt{2\log(2^{k+1}|E_k|)} + \sigma'\log(2^{k+1}|E_k|) \right) \\
&= \frac{1}{2}\sigma\sqrt{2\log(2|E_0|)} + \frac{1}{2}\sigma'\log(2|E_0|) + \sum_{k \ge 0} 2^{-k} \left( \sigma\sqrt{2\log(2^{k+1}|E_k|)} + \sigma'\log(2^{k+1}|E_k|) \right).
\end{align*}
$$

Finally, let

$$
z = H + \frac{5}{2}\sigma\sqrt{2x} + \frac{5}{2}\sigma'x, \quad (33)
$$

so that $z \ge \sum_{k \ge 0} z_k$. By definition,

$$
\begin{align*}
\mathbb{P}\left(\sup_{t \in \mathcal{B}(\sigma, \sigma')} (Y_t - Y_{t_0}) \ge z\right) &\le \mathbb{P}\left(\exists t \in \mathcal{B}(\sigma, \sigma'), \exists k \ge 0, Y_{\pi_{k+1}(t)} - Y_{\pi_k(t)} \ge z_k\right) \\
&\le \mathbb{P}\left(\sup_{t \in \mathcal{B}(\sigma, \sigma')} (Y_{\pi_1(t)} - Y_{t_0}) \ge z_0\right) + \sum_{k \ge 1} \mathbb{P}\left(\sup_{t \in S} (Y_{\pi_{k+1}(t)} - Y_{\pi_k(t)}) \ge z_k\right).
\end{align*}
$$

The first term must be handled carefully, since even if $t \in \mathcal{B}(\sigma, \sigma')$, there is no
guarantee that $\pi_1(t) \in \mathcal{B}(\sigma, \sigma')$. However, if $t$ is in $\mathcal{B}(\sigma, \sigma')$, since $\pi_1(t)$ and $t$
are in the same element of $\mathcal{A}_1$, by the triangle inequality,

$$
R_2(\pi_1(t), t_0) \le R_2(\pi_1(t), t) + R_2(t, t_0) \le \frac{3}{2}\sigma,
$$

and likewise $R_\infty(\pi_1(t), t_0) \le \frac{3}{2}\sigma'$. Therefore,

$$
\begin{align*}
\mathbb{P}\left(\sup_{t \in \mathcal{B}(\sigma, \sigma')} (Y_t - Y_{t_0}) \ge z\right) &\le \mathbb{P}\left(\sup_{\substack{u \text{ s.t. } (t_0, u) \in E_0 \text{ and } u \in \mathcal{B}(3\sigma/2, 3\sigma'/2)}} (Y_u - Y_{t_0}) \ge z_0\right) \\
&\quad + \sum_{k \ge 1} \mathbb{P}\left(\sup_{(s, u) \in E_k} (Y_u - Y_s) \ge z_k\right) \\
&\le \sum_{u \text{ s.t. } (t_0, u) \in E_0} \mathbb{P}((Y_u - Y_{t_0}) \ge z_0 \text{ and } u \in \mathcal{B}(3\sigma/2, 3\sigma'/2)) \\
&\quad + \sum_{k \ge 1} \mathbb{P}\left(\sup_{(s, u) \in E_k} (Y_u - Y_s) \ge z_k\right) \\
&\le \sum_{u \text{ s.t. } (t_0, u) \in E_0} \mathbb{P}((Y_u - Y_{t_0}) \ge z_0 \text{ and } u \in \mathcal{B}(3\sigma/2, 3\sigma'/2)) \\
&\quad + \sum_{k \ge 1} \sum_{(s, u) \in E_k} \mathbb{P}(Y_u - Y_s \ge z_k).
\end{align*}
$$
For $k=0$ Using (26) and the definition of $z_0$,

$$
\begin{align*}
& \mathbb{P}(Y_u - Y_{t_0} \ge z_0 \text{ and } u \in \mathcal{B}(3\sigma/2, 3\sigma'/2)) \\
&= \mathbb{P}\left(Y_u - Y_{t_0} \ge \frac{3}{2}\sigma\sqrt{2(x + \log(2|E_0|))} + \frac{3}{2}\sigma'(x + \log(2|E_0|))\right) \\
&\text{and } R_2(u, t_0) \le \frac{3}{2}\sigma, R_\infty(u, t_0) \le \frac{3}{2}\sigma'\right) \le \frac{1}{2|E_0|}e^{-x}.
\end{align*}
$$

For $k \ge 1$ Since $\mathcal{A}_{k+1} \subset \mathcal{A}_k$, $\pi_k(t)$ and $\pi_{k+1}(t)$ belong to the same set in $\mathcal{A}_k$. Therefore, for all $(s, u) \in E_k$, $N_2(s-u) \le 2^{-k/\beta}\sigma^{1/\beta}$ and $N_\infty(s-u) \le 2^{-k/\beta}(\sigma')^{1/\beta}$. By assumption, $R_2(s, u) \le N_2(s-u)^\beta$ and $R_\infty(s, u) \le N_\infty(s-u)^\beta$. Thus, for $(s, u) \in E_k$, $R_2(s, u) \le 2^{-k}\sigma$ and $R_\infty(s, u) \le 2^{-k}\sigma'$ almost surely. By definition of $z_k$ and (23), for all $(s, u) \in E_k$,

$$
\mathbb{P}(Y_u - Y_s \ge z_k) \le 2^{-(k+1)} |E_k|^{-1} e^{-x}.
$$

Summing on all $(s, u) \in E_k$ and all $k \ge 0$ leads to

$$
\mathbb{P} \left( \sup_{t \in \mathcal{B}(\sigma, \sigma')} (Y_t - Y_{t_0}) \ge z \right) \le e^{-x}.
$$

It remains to compute $H$ in (33). By construction of $\mathcal{A}_k$, the choice of $\pi_{k+1}(t)$ entirely determines the choice of $\pi_k(t)$. Therefore, $|E_k| \le |\mathcal{A}_{k+1}|$, that is

$$
2^{k+1} |E_k| \le 2^{k+1} \left( \frac{vw}{(\sigma\sigma')^{1/\beta}} \right)^D 4^{(3+1/\beta)D(k+1)} \le \left( 4^{(4+1/\beta)(k+1)} \frac{vw}{(\sigma\sigma')^{1/\beta}} \right)^D
$$

and thus

$$
H \le \underbrace{\frac{1}{2}\sigma \sqrt{2D \log \left( 4^{4+1/\beta} \frac{vw}{(\sigma\sigma')^{1/\beta}} \right)}}_{E} + \frac{1}{2}\sigma' D \log \left( 4^{4+1/\beta} \frac{vw}{(\sigma\sigma')^{1/\beta}} \right) \\
+ \underbrace{\sum_{k \ge 0} 2^{-k}\sigma \sqrt{2D \log \left( 4^{(4+1/\beta)(k+1)} \frac{vw}{(\sigma\sigma')^{1/\beta}} \right)}}_{F} + \underbrace{\sum_{k \ge 0} 2^{-k}\sigma' D \log \left( 4^{(4+1/\beta)(k+1)} \frac{vw}{(\sigma\sigma')^{1/\beta}} \right)}_{G}.
$$

Let us calculate the three terms separately. Firstly,

$$
\begin{align*}
E &\le \frac{\sigma}{2} \sqrt{2D \left( \left(4 + \frac{1}{\beta}\right) \log 4 + \frac{1}{\beta} \log\left(\frac{(vw)^\beta}{\sigma\sigma'}\right) \right)} + \frac{\sigma'}{2} D \left( \left(4 + \frac{1}{\beta}\right) \log 4 + \frac{1}{\beta} \log\left(\frac{(vw)^\beta}{\sigma\sigma'}\right) \right) \\
&\le \frac{\sigma}{2} \sqrt{2D \left( 6 + \frac{1}{\beta} \log\left(\frac{4(vw)^\beta}{\sigma\sigma'}\right) \right)} + \frac{\sigma'}{2} D \left( 6 + \frac{1}{\beta} \log\left(\frac{4(vw)^\beta}{\sigma\sigma'}\right) \right).
\end{align*}
$$
Secondly,

$$
\begin{align*}
G &= \sigma' D \sum_{k \ge 0} 2^{-k} \left( (k+1)(4+\frac{1}{\beta}) \log 4 + \frac{1}{\beta} \log(\frac{vw)^{\beta}}{\sigma\sigma'}) \right) \\
&= 2\sigma' D \left( 2(4+\frac{1}{\beta}) \log 4 + \frac{1}{\beta} \log(\frac{vw)^{\beta}}{\sigma\sigma'}) \right) \\
&\le 2\sigma' D \left( 12 + \frac{1}{\beta} \log(\frac{16(vw)^{\beta}}{\sigma\sigma'}) \right).
\end{align*}
$$

Thirdly, by concavity of $x \mapsto \sqrt{x}$ and Jensen's inequality,

$$
F \le 2\sigma \sqrt{\sum_{k \ge 0} 2^{-k} D \log \left( 4^{\left(4+1/\beta\right)(k+1)} \frac{vw}{(\sigma\sigma')^{1/\beta}} \right)} \le 2\sigma \sqrt{2D \left( 12 + \frac{1}{\beta} \log \left( \frac{16(vw)^\beta}{\sigma\sigma'} \right) \right)}.
$$

Thus,

$$
H \le \frac{5}{2}\sigma\sqrt{2D\left(12+\frac{1}{\beta}\log\left(\frac{16(vw)^{\beta}}{\sigma\sigma'}\right)\right)} + \frac{5}{2}\sigma'D\left(12+\frac{1}{\beta}\log\left(\frac{16(vw)^{\beta}}{\sigma\sigma'}\right)\right).
$$

Finally, using the concavity of $x \mapsto \sqrt{x}$ again,

$$
\begin{align*}
z &= H + \frac{5}{2}\sigma\sqrt{2x} + \frac{5}{2}\sigma'x \\
  &\le 5\sigma\sqrt{x + 12D + \frac{D}{\beta}\log\left(\frac{16(vw)^{\beta}}{\sigma\sigma'}\right)} + \frac{5}{2}\sigma'\left(x + 12D + \frac{D}{\beta}\log\left(\frac{16(vw)^{\beta}}{\sigma\sigma'}\right)\right) \\
  &\le 30\left[\sigma\sqrt{x + D + \frac{D}{\beta}\log\left(\frac{v^{\beta}}{\sigma} \lor \frac{w^{\beta}}{\sigma'} \lor e\right)}\right. \\
  &\phantom{\le 30\left[\right.} \left.\qquad + \sigma'\left(x + D + \frac{D}{\beta}\log\left(\frac{v^{\beta}}{\sigma} \lor \frac{w^{\beta}}{\sigma'} \lor e\right)\right)\right].
\end{align*}
$$

This concludes the proof of Proposition 17.

D Proof of Section 4.2

*Proof of Lemma 6.* Let $m \in \mathcal{M}$. For any $t > k \ge 0$, any probability distribution $\lambda$ on $[h_m]$ and any $\theta \in \Theta_m$, let

$$
L_{t,k,\lambda}(\theta) = \log \mathbb{E}_{S_{t-k} \sim \lambda} [p_{\theta}^{m}(X_t | X_{t-k}^{t-1}, S_{t-k})],
$$

where $p_{\theta}^m$ is the conditional distribution according to the parameters of the HMM model $m$. This can be seen as the log of the conditional density of a HMM initialized at time $t-k$ with initial distribution $\lambda$. For $k=0$, we use the convention $p_{\theta}^m(X_t|X_{t-0}^{t-1}, S_{t-0}) = p_{\theta}^m(X_t|S_t)$.
Let $\rho = 1 - (C_Q)^{-2}$. Recall that we assumed $\pi_{\theta}^m, Q_{\theta}^m \in [(C_Q)^{-1}h_m^{-1}, C_Q h_m^{-1}]$ for all $\theta \in \Theta_m$. As a consequence, by Lemma 3 of [29], for all $t, k, k', \lambda$ and $\lambda'$, almost surely,

$$ \sup_{\theta \in \Theta_m} |L_{t,k,\lambda}(\theta) - L_{t,k',\lambda'}(\theta)| \le \rho^{k \wedge k' - 1} / (1 - \rho). $$

In particular, for all $t > k \ge 0$, almost surely,

$$ \sup_{\theta \in \Theta_m} |\log p_{\theta,t}^m(X_t) - L_{t,k,\pi_{\theta}^m}(\theta)| \le \rho^{k-1} / (1 - \rho). $$

Let $t > k \ge 0$. For all $\theta \in \Theta_m$, $x_{t-k}^t \in \mathcal{X}^{k+1}$ and $i \in [h_m]$, let $f_{\theta,i}$ be defined as

$$ f_{\theta,i}(x_{t-k}^t) = p_{\theta}^m(S_k = i, X_t = x_t | X_{t-k}^{t-1} = x_{t-k}^{t-1}, S_{t-k} \sim \pi_{\theta}^m). $$

Note that $L_{t,k,\pi_{\theta}^m}(\theta) = \log \sum_{i \in [h_m]} f_{\theta,i}(X_{t-k}^t)$, so that for any $\theta, \delta \in \Theta_m$,

$$ |\log p_{\theta,t}^m(X_t) - \log p_{\delta,t}^m(X_t)| \le |\log \sum_{i \in [h_m]} (f_{\theta,i}(X_{t-k}^t) - f_{\delta,i}(X_{t-k}^t))| + 2\rho^{k-1} / (1-\rho). $$

Note that if $t = k + 1$, a simpler equality holds:

$$ |\log p_{\theta,t}^m(X_t) - \log p_{\delta,t}^m(X_t)| = |\log \sum_{i \in [h_m]} (f_{\theta,i}(X_{t-k}^t) - f_{\delta,i}(X_{t-k}^t))|. $$

**Lemma 20.** Assume $\|\theta - \delta\|_m \le \log 2$, then for all $x_0^k \in \mathcal{X}^{k+1}$,

$$ \left| \log \sum_{i \in [h_m]} (f_{\theta,i}(x_0^k) - f_{\delta,i}(x_0^k)) \right| \le 7(2C_Q^2)^{k+3} \|\theta - \delta\|_m. $$

To simplify this formula, there exists two constants $C_1, C_2 > 1$ such that

$$ \left| \log \sum_{i \in [h_m]} (f_{\theta,i}(x_0^k) - f_{\delta,i}(x_0^k)) \right| \le \|\theta - \delta\|_m C_1 C_2^k. $$

Therefore, up to changing $C_1$, almost surely,

$$ |\log p_{\theta,t}^m(X_t) - \log p_{\delta,t}^m(X_t)| \le C_1 \min(\inf_{k \in \mathbb{N}: 0 \le k < t} C_2^k \|\theta - \delta\|_m + \rho^k, C_2^{t-1} \|\theta - \delta\|_m). $$

A possible choice is $C_2 = 2C_Q^2$ and $C_1 = 56C_Q^6$.

Solving $C_2^k \|\theta - \delta\|_m = \rho^k$ results in the trade-off $k^* = \lceil \log(1/\|\theta - \delta\|_m) / \log(C_2/\rho) \rceil$, which ensures that as long as $\|\theta - \delta\|_m \le \log 2$, almost surely,

$$ \begin{aligned} |\log p_{\theta,t}^m(X_t) - \log p_{\delta,t}^m(X_t)| &\le 2C_1 C_2^{k^*} \|\theta - \delta\|_m \\ &\le 2C_1 C_2 \|\theta - \delta\|_m^{1-\frac{\log C_2}{\log(C_2/\rho)}}. \end{aligned} $$
so we may take

$$ 
\begin{aligned}
\beta_m^{-1} = 1 - \frac{\log C_2}{\log(C_2/\rho)} &= \frac{\log \rho^{-1}}{\log C_2 + \log \rho^{-1}} = \frac{-\log(1 - (C_Q)^{-2})}{\log(2C_Q^2) - \log(1 - (C_Q)^{-2})} \\
&\sim_{C_Q \to +\infty} \frac{C_Q^{-2}}{2 \log C_Q}
\end{aligned}
$$

and since $L_m \ge (2C_1C_2)$, it proves that Assumption 2 holds when $\|\theta - \delta\|_m \le \log 2$. When $\|\theta - \delta\|_m \ge \log 2$, we always have

$$ |\log p_{\theta,t}^m(X_t) - \log p_{\delta,t}^m(X_t)| \le 2 \log C_m^g \le 3 \log C_m^g \|\theta - \delta\|_m^{\beta_m}, $$

and thus Assumption 2 holds. □

## D.1 Proof of Lemma 20

Let $x_0^k \in \mathcal{X}^{k+1}$. Using the approach of Appendix A of [25], one can write $f_{\theta,i}$ as the product of matrices

$$ f_{\theta,i}(x_0^k) = \left( \mu_{0|k-1}^{\theta} F_{1|k-1}^{\theta} \cdots F_{k-1|k-1}^{\theta} Q_{\theta}^{m} \right)_i \nu_{\theta,i}^{m}(x_k) \quad (34) $$

where

$$ \beta_{u|k}^{\theta}(s_u) = \sum_{s_{u+1}^k \in [h_m]^{k-u}} Q_{\theta}^{m}(s_u, s_{u+1}) \nu_{\theta,s_{u+1}}^{m}(x_{u+1}) \cdots Q_{\theta}^{m}(s_{k-1}, s_k) \nu_{\theta,s_k}^{m}(x_k), $$

for $0 \le u \le k-1$ and $\beta_{k|k}^{\theta}(i) = 1$ for all $i \in [h_m]$,

$$ \mu_{0|k}^{\theta}(i) = \frac{\pi_{\theta}^{m}(i) \beta_{0|k}^{\theta}(i) \nu_{\theta,i}^{m}(x_0)}{\sum_{j \in [h_m]} \pi_{\theta}^{m}(j) \beta_{0|k}^{\theta}(j) \nu_{\theta,j}^{m}(x_0)} $$

$$ \text{and } F_{u|k}^{\theta}(s_{u-1}, s_u) = \frac{\beta_{u|k}^{\theta}(s_u) Q_{\theta}^{m}(s_{u-1}, s_u) \nu_{\theta,s_u}^{m}(x_u)}{\sum_{i \in [h_m]} \beta_{u|k}^{\theta}(i) Q_{\theta}^{m}(s_{u-1}, i) \nu_{\theta,i}^{m}(x_u)}. $$

An intuition of these quantities, and a way to check (34), is given by the identities

$$ \beta_{u|k}^{\theta}(s_u) = p_{\theta}^{m}(X_{u+2}^{k+1} = x_{u+1}^{k} | S_{u+1} = s_u), $$

$$ \mu_{0|k}^{\theta}(i) = p_{\theta}^{m}(S_1 = i | X_1^{k+1} = x_0^k), $$

$$ F_{u|k}^{\theta}(s_{u-1}, s_u) = p_{\theta}^{m}(S_{u+1} = s_u | X_{u+1}^{k+1} = x_u^k, S_u = s_{u-1}), $$

(keeping in mind that under $p_{\theta}^m$, $S_1 \sim \pi_{\theta}^m$), so that

$$ \left( \mu_{0|k}^{\theta} F_{1|k}^{\theta} \cdots F_{k|k}^{\theta} \right)_i = p_{\theta}^{m}(S_{k+1} = i | X_1^{k+1} = x_0^k). $$

The following Lemmas follow the proofs of Appendix B.2.2 of [40].
**Lemma 21.** Assume $\|\theta - \delta\|_m \le \log 2$, then

$$ \sup_{0 \le u \le k} \frac{\sum_{i \in [h_m]} |\beta_{u|k}^{\theta}(i) \nu_{\theta,i}^{m}(x_u) - \beta_{u|k}^{\delta}(i) \nu_{\delta,i}^{m}(x_u)|}{\sum_{i \in [h_m]} \beta_{u|k}^{\theta}(i) \nu_{\theta,i}^{m}(x_u)} \le \|\theta - \delta\|_m (C_Q^{-1} + (\log 2)^{-1})(2C_Q^2)^{k+1}. $$

*Proof.* Using minimalist notations,

$$ \sum_{i \in [h_m]} |\beta_{u|k}^{\theta}(i) \nu_{\theta,i}^{m}(x_u) - \beta_{u|k}^{\delta}(i) \nu_{\delta,i}^{m}(x_u)| \\ = \sum_{s_u \in [h_m]} \left| \left( \sum_{s_{u+1} \in [h_m]^{k-u}} Q_{u,u+1}^{\theta} \nu_{u+1}^{\theta} Q_{u+1,u+2}^{\theta} \dots \nu_k^{\theta} \right) \nu_u^{\theta} \right. \\ \left. - \left( \sum_{s_{u+1} \in [h_m]^{k-u}} Q_{u,u+1}^{\delta} \nu_{u+1}^{\delta} Q_{u+1,u+2}^{\delta} \dots \nu_k^{\delta} \right) \nu_u^{\delta} \right| \\ \le \sum_{j=u+1}^{k} \sum_{s_u^k \in [h_m]^{k-u+1}} \nu_u^{\theta} Q_{u,u+1}^{\theta} \nu_{u+1}^{\theta} \dots \nu_{j-1}^{\theta} |Q_{j-1,j}^{\theta} - Q_{j-1,j}^{\delta}| \nu_j^{\delta} \dots Q_{k-1,k}^{\delta} \nu_k^{\delta} \\ \left. + \sum_{j=u}^{k} \sum_{s_u^k \in [h_m]^{k-u+1}} \nu_u^{\theta} Q_{u,u+1}^{\theta} \nu_{u+1}^{\theta} \dots Q_{j-1,j}^{\theta} |\nu_j^{\theta} - \nu_j^{\delta}| Q_{j,j+1}^{\delta} \dots Q_{k-1,k}^{\delta} \nu_k^{\delta} \right| $$

Keep in mind in what follows that Assumption 4-HMM and the definition of $\|\cdot\|_m$ entail, for all $j$,

$$ |\nu_j^\theta - \nu_j^\delta| \le \nu_j^\theta (e^{\|\theta-\delta\|_m} - 1) \quad \text{and} \quad \nu_j^\delta \le \nu_j^\theta e^{\|\theta-\delta\|_m}. \quad (35) $$

By definition of $\|\cdot\|_m$, for all $j \in \{u+1, \dots, k\}$,

$$ \sum_{s_u^k \in [h_m]^{k-u+1}} \nu_u^\theta Q_{u,u+1}^\theta \dots Q_{j-2,j-1}^\theta \nu_{j-1}^\theta |Q_{j-1,j}^\theta - Q_{j-1,j}^\delta| \nu_j^\delta \dots Q_{k-1,k}^\delta \nu_k^\delta \\ \le \|\theta - \delta\|_m h_m^{-1} (C_Q h_m^{-1})^{k-j} \sum_{s_u^{j-1} \in [h_m]^{j-u}} \nu_u^\theta Q_{u,u+1}^\theta \dots Q_{j-2,j-1}^\theta \nu_{j-1}^\theta \sum_{s_j \in [h_m]} \nu_j^\delta \dots \sum_{s_k \in [h_m]} \nu_k^\delta $$

and for all $j \in \{u, \dots, k\}$

$$ \sum_{i \in [h_m]} \beta_{u|k}^{\theta}(i) \nu_{\theta,i}^{m}(x_u) = \sum_{s_u^k \in [h_m]^{k-u+1}} \nu_u^{\theta} Q_{u,u+1}^{\theta} \dots Q_{j-2,j-1}^{\theta} \nu_{j-1}^{\theta} Q_{j-1,j}^{\theta} \nu_j^{\theta} \dots Q_{k-1,k}^{\theta} \nu_k^{\theta} \\ \ge (C_Q h_m)^{-(k-j+1)} \sum_{s_u^{j-1} \in [h_m]^{j-u}} \nu_u^{\theta} Q_{u,u+1}^{\theta} \dots Q_{j-2,j-1}^{\theta} \nu_{j-1}^{\theta} \sum_{s_j \in [h_m]} \nu_j^{\theta} \dots \sum_{s_k \in [h_m]} \nu_k^{\theta}, $$

so that

$$ \frac{\sum_{s_u^k \in [h_m]^{k-u+1}} \nu_u^\theta Q_{u,u+1}^\theta \dots \nu_{j-1}^\theta |Q_{j-1,j}^\theta - Q_{j-1,j}^\delta| \nu_j^\delta \dots \nu_k^\delta}{\sum_{s_u^k \in [h_m]^{k-u+1}} \nu_u^\theta Q_{u,u+1}^\theta \dots \nu_{j-1}^\theta Q_{j-1,j}^\theta \nu_j^\theta \dots \nu_k^\theta} \\ \le \|\theta - \delta\|_m e^{(k-j+1)\|\theta - \delta\|_m} (C_Q)^{2(k-j)+1}. $$
Likewise, for all $j \in \{u, \dots, k\}$,

$$ \frac{\sum_{s_u^k \in [h_m]^{k-u+1}} \nu_u^\theta Q_{u,u+1}^\theta \cdots Q_{j-1,j}^\theta |\nu_j^\theta - \nu_j^\delta| Q_{j,j+1}^\delta \cdots Q_{k-1,k}^\delta \nu_k^\delta}{\sum_{s_u^k \in [h_m]^{k-u+1}} \nu_u^\theta Q_{u,u+1}^\theta \cdots Q_{j-1,j}^\theta \nu_j^\theta Q_{j,j+1}^\theta \cdots Q_{k-1,k}^\theta \nu_k^\theta} \le e^{(k-j)\|\theta-\delta\|_m} (e^{\|\theta-\delta\|_m} - 1) C_Q^{2(k-j)}. $$

Therefore,

$$ \begin{align*} & \frac{\sum_{i \in [h_m]} |\beta_{u|k}^\theta(i) \nu_{\theta,i}^m(x_u) - \beta_{u|k}^\delta(i) \nu_{\delta,i}^m(x_u)|}{\sum_{i \in [h_m]} \beta_{u|k}^\theta(i) \nu_{\theta,i}^m(x_u)} \\ & \le \|\theta - \delta\|_m C_Q^{-1} \sum_{j=u}^{k-1} e^{(k-j)\|\theta-\delta\|_m} (C_Q)^{2(k-j)} + (e^{\|\theta-\delta\|_m} - 1) \sum_{j=u}^{k} e^{(k-j)\|\theta-\delta\|_m} C_Q^{2(k-j)} \\ & \le (\|\theta - \delta\|_m C_Q^{-1} + (e^{\|\theta-\delta\|_m} - 1)) \sum_{j=u}^{k} (e^{\|\theta-\delta\|_m} C_Q^2)^{k-j} \\ & \le \|\theta - \delta\|_m (C_Q^{-1} + (\log 2)^{-1}) \frac{(2C_Q^2)^{k-u+1} - 1}{2C_Q^2 - 1} \quad \text{when } \|\theta - \delta\|_m \le \log 2 \\ & \le \|\theta - \delta\|_m (C_Q^{-1} + (\log 2)^{-1}) (2C_Q^2)^{k-u+1} \quad \text{since } C_Q \ge 1. \end{align*} $$

□

**Lemma 22.** Assume $\|\theta - \delta\|_m \le \log 2$, then

$$ \|\mu_{0|k}^\theta - \mu_{0|k}^\delta\|_1 \le 3(2C_Q^2)^{k+2}\|\theta - \delta\|_m $$

and

$$ \sup_{0 \le u \le k} \sup_{i \in [h_m]} \|F_{u|k}^\theta(i, \cdot) - F_{u|k}^\delta(i, \cdot)\|_1 \le 3(2C_Q^2)^{k+2}\|\theta - \delta\|_m. $$

*Proof.* With minimalist notations,

$$ \begin{align*} \sum_i |\mu_i^\theta - \mu_i^\delta| &= \sum_i \left| \frac{\pi_i^\theta \beta_i^\theta \nu_i^\theta}{\sum_j \pi_j^\theta \beta_j^\theta \nu_j^\theta} - \frac{\pi_i^\delta \beta_i^\delta \nu_i^\delta}{\sum_j \pi_j^\delta \beta_j^\delta \nu_j^\delta} \right| \\ &\le \frac{\sum_j |\pi_i^\theta \beta_i^\theta \nu_i^\theta - \pi_i^\delta \beta_i^\delta \nu_i^\delta|}{\sum_j \pi_j^\theta \beta_j^\theta \nu_j^\theta} + \left| \frac{1}{\sum_j \pi_j^\theta \beta_j^\theta \nu_j^\theta} - \frac{1}{\sum_j \pi_j^\delta \beta_j^\delta \nu_j^\delta} \right| \sum_j \pi_j^\delta \beta_j^\delta \nu_j^\delta \\ &\le 2 \frac{\sum_j |\pi_i^\theta \beta_i^\theta \nu_i^\theta - \pi_i^\delta \beta_i^\delta \nu_i^\delta|}{\sum_j \pi_j^\theta \beta_j^\theta \nu_j^\theta} \\ &\le 2C_Q h_m \frac{\sum_j |\pi_i^\theta \beta_i^\theta \nu_i^\theta - \pi_i^\delta \beta_i^\delta \nu_i^\delta|}{\sum_j \pi_j^\theta \beta_j^\theta \nu_j^\theta}. \end{align*} $$
Thus,

$$
\begin{align*}
\sum |\mu^\theta - \mu^\delta| &\le 2C_Q h_m \left( \frac{\sum |\pi^\theta - \pi^\delta| |\beta^\theta \nu^\theta|}{\sum \beta^\theta \nu^\theta} + \frac{\sum \pi^\delta |\beta^\theta \nu^\theta - \beta^\delta \nu^\delta|}{\sum \beta^\theta \nu^\theta} \right) \\
&\le 2C_Q h_m \left( \|\theta - \delta\|_m h_m^{-1} + C_Q h_m^{-1} \frac{\sum |\beta^\theta \nu^\theta - \beta^\delta \nu^\delta|}{\sum \beta^\theta \nu^\theta} \right) \\
&\le \|\theta - \delta\|_m 2C_Q \left( 1 + C_Q (C_Q^{-1} + (\log 2)^{-1}) (2C_Q^2)^{k+1} \right) \quad \text{by Lemma 21} \\
&\le 3(2C_Q^2)^{k+2} \|\theta - \delta\|_m.
\end{align*}
$$

The control of $\sum_{j \in [K]} |F_{u|k}^{\theta}(i,j) - F_{u|k}^{\delta}(i,j)|$ is exactly the same after replacing $\pi_{\theta}^{m}$ by $Q_{\theta}^{m}(i, \cdot)$ and likewise for $\delta$. $\square$

We now have the tools to prove Lemma 20. We again use minimalist notations. First,

$$
\sum_{i \in [h_m]} |(\mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta)_i - (\mu^\delta F_{1|k}^\delta \dots F_{k|k}^\delta)_i| \le \sum_{i \in [h_m]} |((\mu^\theta - \mu^\delta) F_{1|k}^\theta \dots F_{k|k}^\theta)_i| \\
+ \sum_{u=1}^k \sum_{i \in [h_m]} |(\mu^\delta F_{1|k}^\delta \dots F_{u-1|k}^\delta (F_{u|k}^\delta - F_{u|k}^\theta) F_{u+1|k}^\theta \dots F_{k|k}^\theta)_i|.
$$

Then, since $F_{u|k}^{\theta}$ and $F_{u|k}^{\delta}$ are transition matrices (and thus are 1-Lipschitz linear operators of $\mathbf{L}^1([h_m]))$,

$$
\| \mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta - \mu^\delta F_{1|k}^\delta \dots F_{k|k}^\delta \|_1 \le \| \mu^\delta - \mu^\theta \|_1 + \sum_{u=1}^k \sup_{i \in [h_m]} \| F_{u|k}^\theta(i, \cdot) - F_{u|k}^\delta(i, \cdot) \|_1.
$$

By Lemma 22, both $\|\mu^\delta - \mu^\theta\|_1$ and $\sup_{1\le u\le k} \sup_{i\in[h_m]} \|F_{u|k}^\theta(i,\cdot) - F_{u|k}^\delta(i,\cdot)\|_1$ are upper bounded by $C_F \|\theta - \delta\|_m$ for $C_F = 3(2C_Q^2)^{k+2}$, so that

$$
\| \mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta - \mu^\delta F_{1|k}^\delta \dots F_{k|k}^\delta \|_1 \le 2C_F \|\theta - \delta\|_m.
$$

Therefore,

$$
\begin{align*}
& \frac{\sum_{i \in [h_m]} |(\mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta Q^\theta)_i \nu_i^\theta - (\mu^\delta F_{1|k}^\delta \dots F_{k|k}^\delta Q^\delta)_i \nu_i^\delta|}{\sum_{i \in [h_m]} (\mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta Q^\theta)_i \nu_i^\theta} \\
& \le \frac{\sum_i (\mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta Q^\theta)_i |\nu_i^\theta - \nu_i^\delta|}{\sum_{i \in [h_m]} (\mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta Q^\theta)_i \nu_i^\theta} \\
& \qquad + \frac{\sum_i |(\mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta Q^\theta)_i - (\mu^\delta F_{1|k}^\delta \dots F_{k|k}^\delta Q^\delta)_i| \nu_i^\delta}{\sum_{i \in [h_m]} (\mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta Q^\theta)_i \nu_i^\theta} \\
& \le \|\theta - \delta\|_m (\log 2)^{-1} + 2 \sup_i \frac{|(\mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta Q^\theta)_i - (\mu^\delta F_{1|k}^\delta \dots F_{k|k}^\delta Q^\delta)_i|}{(\mu^\theta F_{1|k}^\theta \dots F_{k|k}^\theta Q^\theta)_i}
\end{align*}
$$
by (35) when $\|\theta-\delta\|_m \le \log 2$. Then, for any $i \in [h_m]$, since $(\mu^\theta F_{1|k}^\theta \cdots F_{k|k}^\theta Q^\theta)_i \ge (C_Q h_m)^{-1}$,

$$ \frac{|(\mu^\theta F_{1|k}^\theta \cdots F_{k|k}^\theta Q^\theta)_i - (\mu^\delta F_{1|k}^\delta \cdots F_{k|k}^\delta Q^\delta)_i|}{(\mu^\theta F_{1|k}^\theta \cdots F_{k|k}^\theta Q^\theta)_i} \\ \le C_Q h_m \sum_j |(\mu^\theta F_{1|k}^\theta \cdots F_{k|k}^\theta)_j - (\mu^\delta F_{1|k}^\delta \cdots F_{k|k}^\delta)_j| Q_{j,i}^\delta \\ + C_Q h_m \sum_j (\mu^\theta F_{1|k}^\theta \cdots F_{k|k}^\theta)_j |Q_{j,i}^\theta - Q_{j,i}^\delta| \\ \le C_Q^2 \sum_j |(\mu^\theta F_{1|k}^\theta \cdots F_{k|k}^\theta)_j - (\mu^\delta F_{1|k}^\delta \cdots F_{k|k}^\delta)_j| \\ + C_Q \|\theta - \delta\|_m \sum_j (\mu^\theta F_{1|k}^\theta \cdots F_{k|k}^\theta)_j \\ \le 2C_Q^2 C_F \|\theta - \delta\|_m + C_Q \|\theta - \delta\|_m. $$

As a consequence, by symmetry of the roles of $\theta$ and $\delta$,

$$ \left| \log \sum_{i \in [h_m]} (f_{\theta,i}(x_0^k) - f_{\delta,i}(x_0^k)) \right| \le \frac{\sum_{i \in [h_m]} |f_{\theta,i}(x_0^k) - f_{\delta,i}(x_0^k)|}{\left(\sum_{i \in [h_m]} f_{\theta,i}(x_0^k)\right) \wedge \left(\sum_{i \in [h_m]} f_{\delta,i}(x_0^k)\right)} \\ \le \|\theta - \delta\|_m [12C_Q^2 (2C_Q^2)^{k+2} + 2C_Q + (\log 2)^{-1}] \le 7(2C_Q^2)^{k+3} \|\theta - \delta\|_m. $$

## E Proof of Section 4.3

*Proof of Lemma 7.* For $u \in \mathbb{R}$, let $\phi(u) = e^u - u - 1$. Let $t \in [n]$. By definition,

$$ \mathbb{E} \left[ \log \left( \frac{p_t^*(X_t)}{p_t(X_t)} \right) \mid \mathcal{F}_{t-1} \right] = \mathbb{E} \left[ \phi \left( \log \left( \frac{p_t(X_t)}{p_t^*(X_t)} \right) \right) \mid \mathcal{F}_{t-1} \right]. $$

Let $x = \log \left( \frac{p_t(X_t)}{p_t^*(X_t)} \right)$. By hypothesis

$$ |x| = \log \left( \frac{p_t(X_t)}{p_t^*(X_t)} \right) \mathbf{1}_{x \ge 0} + \log \left( \frac{p_t^*(X_t)}{p_t(X_t)} \right) \mathbf{1}_{x < 0} $$

If $x \ge 0$, then $\varepsilon \le p_t^*(X_t) \le p_t(X_t) \le \varepsilon^{-1}$, so that $\log \left( \frac{p_t(X_t)}{p_t^*(X_t)} \right) \le \log(\varepsilon^{-2})$. The same inequality holds by symmetry when $x < 0$. Therefore,

$$ |x| \le \log(\varepsilon^{-2}). $$

By convexity, note that $\phi$ is non negative. Let us apply the Taylor Lagrange formula in 0. There exists $c \in [0, u]$ such that

$$ \phi(u) = \phi(0) + \phi'(0)u + \phi''(c) \frac{u^2}{2}. $$
Since, $\phi(0) = \phi'(0) = 0$, the previous equation simply reads $\phi(u) = \phi''(c) \frac{u^2}{2}$. Since the function $u \to \phi''(u) = e^u$ is increasing, it holds that for all $u \in [-\log(\epsilon^{-2}), \log(\epsilon^{-2})]$

$$ \phi''(-\log(\epsilon^{-2})) \frac{u^2}{2} = \frac{\epsilon^2}{2} u^2 \le \phi(u) \le \phi''(\log(\epsilon^{-2})) \frac{u^2}{2} = \frac{1}{2\epsilon^2} u^2. $$

That is,

$$ \frac{\epsilon^2}{2} \mathbb{E} \left[ \log \left( \frac{p_t^*(X_t)}{p_t(X_t)} \right)^2 \mid \mathcal{F}_{t-1} \right] \le \mathbb{E} \left[ \log \left( \frac{p_t^*(X_t)}{p_t(X_t)} \right) \mid \mathcal{F}_{t-1} \right] \le \frac{1}{2\epsilon^2} \mathbb{E} \left[ \log \left( \frac{p_t^*(X_t)}{p_t(X_t)} \right)^2 \mid \mathcal{F}_{t-1} \right]. \quad \square $$

# F Proof of Section 4.4

## F.1 Proof of Section 4.4.1

*Proof of Lemma 8.* In [42, Lemma 7.23], the author shows that for two densities $f$ and $g$, it holds that

$$ 2H^2(f,g) \le KL(f,g) $$

where $H$ is the Hellinger distance defined by,

$$ H^2(f,g) = \frac{1}{2} \int (\sqrt{f} - \sqrt{g})^2. $$

Let us apply this result to $p_t^*$ and $p_t$:

$$ \sum_{k=1}^{K} p_t^*(k) \log \frac{p_t^*(k)}{p_t(k)} \ge \frac{1}{2} \sum_{k=1}^{K} \left( \sqrt{p_t^*(k)} - \sqrt{p_t(k)} \right)^2 \ge \frac{1}{8} \sum_{k=1}^{K} (p_t^*(k) - p_t(k))^2, $$

where the last inequality holds because, by the Taylor-Lagrange formula, for all $x, y \in [\epsilon, 1]$,

$$ |\sqrt{x} - \sqrt{y}| \ge \frac{1}{2}|x - y|. $$

Therefore,

$$ \mathbf{K}_n(p) \ge \frac{1}{8T_\epsilon} \sum_{t=1}^{T_\epsilon} \sum_{k=1}^{K} (p_t^*(k) - p_t(k))^2. $$

$\square$

## F.2 Proofs of Section 4.4.2

### F.2.1 Unbiased estimator

Let's first verify the following claim.
**Proposition 23.** In the procedure described in Section 4.4.2, $\hat{L}_t^m(J)$ is an unbiased estimator of the loss $g_J^m$ with respect to the distribution $p_s$.

*Proof.* Given the past $\sigma(X_1^{t-1})$, taking the conditional expectation with respect to $p_t$

$$ 
\begin{aligned}
\mathbb{E}[\hat{L}_t^m(J)|X_1^{t-1}] &= \frac{g_J^m}{p_t(J)} \mathbb{P}(X_t \in J|X_1^{t-1}) \\
&= \frac{g_J^m}{p_t(J)} \left( \mathbb{P}(X_t \in J, I_t = J|X_1^{t-1}) + \underbrace{\mathbb{P}(X_t \in J, I_t \neq J|X_1^{t-1})}_{=0} \right) \\
&= \frac{g_J^m}{p_t(J)} \mathbb{P}(I_t = J|X_1^{t-1}) \underbrace{\mathbb{P}(X_t \in J|I_t = J, X_1^{t-1})}_{=1} \\
&= \frac{g_J^m}{p_t(J)} p_t(J) = g_J^m.
\end{aligned}
$$

□

### F.2.2 Proof of Proposition 9

Equation (8) can be written

$$ p_{\theta^{m},t+1}(I) = \frac{p_{\theta^{m},t}(I) \exp\left(-\frac{\theta_{I}^{m}/\sqrt{T}}{p_{\theta^{m},t}(I)}\right) \mathbf{1}_{X_t \in I}}{1 - p_{\theta^{m},t}^m(I) + p_{\theta^{m},t}^m(I) \exp\left(-\frac{\theta_{I}^{m}/\sqrt{T}}{p_{\theta^{m},t}(I)}\right)} + \sum_{J \neq I} \frac{p_{\theta^{m},t}^m(I) \mathbf{1}_{X_t \in J}}{1 - p_{\theta^{m},t}^m(J) + p_{\theta^{m},t}^m(J) \exp\left(-\frac{\theta_{J}^{m}/\sqrt{T}}{p_{\theta^{m},t}(J)}\right)} $$

Since for all $q > 0$, $1 - q + q \exp\left(-\frac{\theta_I^m/\sqrt{T}}{q}\right) \le 1$,

$$ p_{\theta^{m},t+1}^{m}(I) \ge p_{\theta^{m},t}^{m}(I) \exp\left(-\frac{\theta_{I}^{m}/\sqrt{T}}{p_{\theta^{m},t}(I)}\right) \mathbf{1}_{X_t \in I} + p_{\theta^{m},t}^{m}(I) \sum_{J \neq I} \mathbf{1}_{X_t \in J}, $$

so that

$$ p_{\theta^{m},t+1}^{m}(I) \ge p_{\theta^{m},t}^{m}(I) \exp\left(-\frac{\theta_{I}^{m}/\sqrt{T}}{p_{\theta^{m},t}(I)}\right). $$

Using that $e^{-x} \ge 1 - x$ for all $x \in \mathbb{R}$, leads to, for all $\theta_I^m \in [r, R]$,

$$ p_{\theta^{m},t+1}^{m}(I) \ge p_{\theta^{m},t}^{m}(I) - \frac{\theta_{I}^{m}}{\sqrt{T}} \ge p_{\theta^{m},t}^{m}(I) - \frac{R}{\sqrt{T}}. $$

Summing for $s \in [t]$ leads to,

$$ p_{\theta^{m},t}^{m}(I) \ge \frac{1}{D_m} - \frac{R}{\sqrt{T}} t \ge \frac{1}{D} - \frac{R}{\sqrt{T}} t. $$
Therefore, letting $T_{\varepsilon} = \lfloor (\frac{1}{D} - \varepsilon) \frac{\sqrt{T}}{R} \rfloor$ leads to, for all $t \in [T_{\varepsilon}]$,

$$p_{\theta^{m},t}^{m}(I) \geq \frac{1}{D} - \frac{R}{\sqrt{T}} T_{\varepsilon} \geq \varepsilon.$$

### F.2.3 Proof of Proposition 10

Let $m \in \mathcal{M}$, and let $\theta, \delta \in [r, R]^{D_m}$. The function softmax is 1-Lipschitz with respect to the $\| \cdot \|_2$-norm in $\mathbb{R}^{D_m}$ (see [33] for a proof). Therefore,

$$\|p_{\theta,t+1}^{m} - p_{\delta,t+1}^{m}\|_{2} \le \left\| \sum_{s=1}^{t} \hat{L}_{\theta,s}^{m} - \sum_{s=1}^{t} \hat{L}_{\delta,s}^{m} \right\|_{2} \le \sum_{s=1}^{t} \|\hat{L}_{\theta,s}^{m} - \hat{L}_{\delta,s}^{m}\|_{2}.$$

Thus,

$$\|p_{\theta,t+1}^{m} - p_{\delta,t+1}^{m}\|_{2} \le \frac{1}{\sqrt{T}} \sum_{s=1}^{t} \left\| \left( \frac{\theta}{p_{\theta,s}^{m}} - \frac{\delta}{p_{\delta,s}^{m}} \right) \mathbf{1}_{X_s} \right\|_{2}$$

where

$$\left\| \left( \frac{\theta}{p_{\theta,s}^{m}} - \frac{\delta}{p_{\delta,s}^{m}} \right) \mathbf{1}_{X_s} \right\|_{2}^{2} = \sum_{J \in \mathcal{I}^{m}} \left( \frac{\theta_{J}}{p_{\theta,s}^{m}(J)} - \frac{\delta_{J}}{p_{\delta,s}^{m}(J)} \right)^{2} \mathbf{1}_{X_s \in J}.$$

With the triangle inequality, for all $t \in [T_{\varepsilon}]$

$$\begin{aligned}
\|p_{\theta,t+1}^{m} - p_{\delta,t+1}^{m}\|_{2} & \le \frac{1}{\sqrt{T}} \sum_{s=1}^{t} \left\| \left( \frac{\theta}{p_{\theta,s}^{m}} - \frac{\theta}{p_{\delta,s}^{m}} \right) \mathbf{1}_{X_s} \right\|_{2} + \frac{1}{\sqrt{T}} \sum_{s=1}^{t} \left\| \left( \frac{\theta}{p_{\delta,s}^{m}} - \frac{\delta}{p_{\delta,s}^{m}} \right) \mathbf{1}_{X_s} \right\|_{2} \\
& \le \frac{R}{\varepsilon^2 \sqrt{T}} \sum_{s=1}^{t} \left\| (p_{\theta,s}^{m} - p_{\delta,s}^{m}) \mathbf{1}_{X_s} \right\|_{2} + \frac{1}{\sqrt{T}} \sum_{s=1}^{t} \left\| \left( \frac{\theta}{p_{\delta,s}^{m}} - \frac{\delta}{p_{\delta,s}^{m}} \right) \mathbf{1}_{X_s} \right\|_{2} \\
& \le \frac{R}{\varepsilon^2 \sqrt{T}} \sum_{s=1}^{t} \|p_{\theta,s}^{m} - p_{\delta,s}^{m}\|_{2} + \frac{Rt}{\varepsilon \sqrt{T}} \|\theta - \delta\|_{\infty} \\
& \le \frac{1}{D\varepsilon} \|\theta - \delta\|_{\infty} + \frac{R}{\varepsilon^2 \sqrt{T}} \sum_{s=1}^{t} \|p_{\theta,s}^{m} - p_{\delta,s}^{m}\|_{2}.
\end{aligned}$$

where

* the first inequality holds because of the triangle inequality,

* the second inequality holds because $x \to 1/x$ is $1/\varepsilon^2$-Lipschitz on $(\varepsilon, 1]$ and for all $J \in \mathcal{I}^m$, $\theta_J \in [r, R]$,

* the third inequality holds because for all $J \in \mathcal{I}^m$, for all $t \in [T_{\varepsilon}]$ and all $k \in [K]$, $p_{\delta^{m},t}(k) \ge \varepsilon$ and because $\|\mathbf{1}_{X_s} \cdot \|_2^2 = \sum_{J \in \mathcal{I}^m} \mathbf{1}_{X_s} \cdot J = 1$,

* the last inequality holds since $t \le T_{\varepsilon} \le \frac{\sqrt{T}}{DR}$.
By the discrete version of Gronwall's Lemma [21], for all $t \in [T_\epsilon]$,

$$ \|p_{\theta,t}^m - p_{\delta,t}^m\|_2 \le \frac{1}{D\epsilon} \|\theta - \delta\|_{\infty} \exp\left(\frac{Rt}{\epsilon^2\sqrt{T}}\right) \le \frac{1}{D\epsilon} \exp\left(\frac{1}{D\epsilon^2}\right) \|\theta - \delta\|_{\infty}. $$

To conclude, note that log is $1/\epsilon$-Lipschitz on $[\epsilon, 1]$ and that $\|p_{\theta,t}^m - p_{\delta,t}^m\|_{\infty} \le \|p_{\theta,t}^m - p_{\delta,t}^m\|_2$.