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

HAL
open science

# Asymptotically optimal regret in communicating Markov decision processes

Victor Boone

► To cite this version:

Victor Boone. Asymptotically optimal regret in communicating Markov decision processes. 2026. [https://hal.science/hal-05454353v1](https://hal.science/hal-05454353v1)

HAL Id: hal-05454353

[https://hal.science/hal-05454353v1](https://hal.science/hal-05454353v1)

Preprint submitted on 12 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Asymptotically optimal regret in communicating Markov decision processes

Victor Boone

VICTOR.BOONE@IRIT.FR

Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France.

IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France

## Abstract

In this paper, we present a learning algorithm that achieves asymptotically optimal regret for Markov decision processes in average reward under a communicating assumption. That is, given a communicating Markov decision process $M$, our algorithm has regret $K(M) \log(T) + o(\log(T))$ where $T$ is the number of learning steps and $K(M)$ is the best possible constant. This algorithm works by explicitly tracking the constant $K(M)$ to learn optimally, then balances the trade-off between exploration (playing sub-optimally to gain information), co-exploration (playing optimally to gain information) and exploitation (playing optimally to score maximally). We further show that the function $K(M)$ is discontinuous, which is a consequent challenge for our approach. To that end, we describe a regularization mechanism to estimate $K(M)$ with arbitrary precision from empirical data.

**Keywords:** Markov decision processes, Average reward, Regret, Reinforcement learning.

## 1 Introduction

There is a Markov decision process, and there is a learning algorithm doing its best at picking actions to gather as much reward as possible. The algorithm is learning, in that it is unaware of the structure of the Markov decision process; The algorithm learns forever and there is no reset mechanism whatsoever, in that the time horizon is infinite and that rewards are not discounted. As such, the so-described system is a Markov decision process in average reward of which the reward and transition functions are unknown to the algorithm. In this paper, we measure the learning performance by the **regret**, that compares the amount of reward collectible by an ominous algorithm that knows the Markov decision process in advance and plays optimal actions, to the learning algorithm that has to learn everything. Following Auer et al. (2009) and all the subsequent works on regret minimization in average reward Markov decision processes, we define the regret after $T$ learning steps as

$$Tg^* - \sum_{t=1}^{T} R_t \qquad (1)$$

where $g^*$ is the optimal gain of the unknown Markov decision process Puterman (2014) and $R_t$ is the reward earned by the learning algorithm at time $t$. The smaller the regret is, the better the algorithm performs.

In this work, we are interested in **asymptotic** regret guarantees in the **model dependent** setting and in **expectation**. That is, the unknown Markov decision process $M$ is fixed and we want to design a learning algorithm $\Lambda$ such that the expectation of (1) under $M$ and $\Lambda$, denoted $\text{Reg}(T; M, \Lambda)$, is as small as possible when $T \to \infty$. This very problem goes back
to the bandit literature, especially to the seminal paper of Lai and Robbins (1985). Despite an immense literature in the surroundings of bandit problems, where the problem is mostly solved—see the book of Lattimore and Szepesvári (2020) for instance, gaping holes are left in the more general world of Markov decision processes. Existing works either stick to a strong ergodic assumption Agrawal et al. (1988); Burnetas and Katehakis (1997); Graves and Lai (1997); Auer and Ortner (2006); Pesquerel and Maillard (2022), or provide partial solutions Tranos and Proutiere (2021), or have no proof of asymptotic optimality Auer et al. (2009); Filippi et al. (2010); Saber et al. (2024). It was only recently Boone and Maillard (2025) that a general lower bound for the asymptotic regret of “reasonable” algorithms (see Section 2.2.2 and Definition 3) has been described under the weaker communicating assumption (Assumption 2): For every reasonable learning algorithm, we have

$$ \mathrm{Reg}(T; M, \Lambda) \geq K(M) \log(T) + o(\log(T)) \quad \text{as } T \to \infty \quad (2) $$

where $K(M) \in \mathbb{R}_+$ is a constant that describes the learning difficulty of $M$ and that we recall in Theorem 1.

In this paper, we show that the bound of (2) is tight: We describe an algorithm $\Lambda$ such that $\mathrm{Reg}(T; M, \Lambda) = K(M) \log(T) + o(\log(T))$ for all communicating Markov decision process $M$ simulatenously, therefore solving the regret minimization problem at first order under the communicating assumption.

## 2 Preliminaries

In this section, we provide some background on average reward Markov decision processes and the associated regret minimization problem.

**General notations.** Given a set $\mathcal{X}$, we denote $\mathcal{P}(\mathcal{X})$ the set of probability distributions over $\mathcal{X}$. We write $p \ll q$ if $p \in \mathcal{P}(\mathcal{X})$ is absolutely continuous with respect to $q \in \mathcal{P}(\mathcal{X})$ and $p \sim q$ if $p \ll q$ and $q \ll p$. Given two finite sets $\mathcal{X}$ and $\mathcal{Y}$, a transition kernel from $\mathcal{X}$ to $\mathcal{Y}$, or **kernel**, is a map $k: \mathcal{X} \to \mathcal{P}(\mathcal{Y})$ and we write $k(y|x)$ the probability that $Y = y$ under $Y \sim k(x)$. Given $k: \mathcal{X} \to \mathcal{P}(\mathcal{Y})$ a transition kernel, we write $\|k\|_{\infty} := \sup_{x \in \mathcal{X}} \|k(x)\|_1$ its infinity norm. We write $\mathrm{KL}(p||q) := \int \log(\frac{dp}{dq}) dp$ the Kullback-Leibler divergence from distribution $q$ to distribution $p$. Given a vector $u \in \mathbb{R}_+^d$, we write $\mathrm{dmin}(u) := \min\{u_i : u_i > 0\}$ its definite minimum. The span of a vector $u \in \mathbb{R}^d$ is denoted $\mathrm{sp}(u) := \max(u) - \min(u)$.

### 2.1 Markov decision processes in average reward

A Markov decision process (or model) is a tuple $M = (S, A, p, \nu)$ where $S$ is the state space and $A = \prod_{s \in S} A(s)$ is the action space, together forming the pair space $Z := \prod_{s \in S} \{s\} \times A(s)$; $p: Z \to \mathcal{P}(S)$ is the transition kernel and $\nu: Z \to \mathcal{P}([0, 1])$ is the reward function. Its mean reward function is $r: Z \to [0, 1]$ and is given by $r(z) := \int x d\nu(z)(x)$. We write $S_t, A_t, R_t$ the t-th step state, action and reward observed when interacting with $M$, and we further denote $Z_t := (S_t, A_t)$ the played state-action pair at time $t$. By definition,

$$ S_{t+1} \sim p(Z_t) \quad \text{and} \quad R_t \sim \nu(Z_t) $$

are sampled independently of each other and independently of the previous history of play, given by $H_t := (S_1, A_1, R_1, \dots, S_t)$, making the system memoryless. The space of histories
is denoted $\mathcal{H} := \bigcup_{t \ge 1} ((\mathcal{Z} \times [0, 1])^{t-1} \times \mathcal{S})$. Given $\mathcal{Z}' \subseteq \mathcal{Z}$ a subset of pairs, we write $\mathcal{S}(\mathcal{Z}') := \{s \in \mathcal{S} : \{s\} \times \mathcal{A}(s) \cap \mathcal{Z}' \neq \emptyset\}$ the projection of $\mathcal{Z}'$ onto $\mathcal{S}$. All throughout the paper, we will assume that $M$ has a finite state-action space, see Assumption 1 below.

**Assumption 1.** The pair space $\mathcal{Z}$ is fixed and finite.

### 2.1.1 RANDOMIZED POLICIES, THEIR GAIN, BIAS & GAP FUNCTIONS

While new states and rewards are generated by the Markov decision process, actions are chosen by an exterior mechanism, and the simplest way to choose actions are policies. A (stationary) randomized policy is a kernel $\pi: \mathcal{S} \to \mathcal{P}(\mathcal{A})$ from states to probabilities over legal actions, and it is said deterministic if of the form $\pi: \mathcal{S} \to \mathcal{A}$. We write $\Pi^{\text{SR}}$ and $\Pi$ the respective sets of randomized and deterministic policies.

Once a policy $\pi \in \Pi^{\text{SR}}$, a model $M$ and an initial state $s_0 \in \mathcal{S}$ are fixed, the distribution of $H_t$ is completely determined for $t \ge 1$ and we write $\mathbf{E}_{s_0}^{M, \pi}(-)$ and $\mathbf{E}_{s_0}^{M, \Lambda}[-]$ the probability and expectation operators over the induced probability space on $\mathcal{H}$. Note that a fixed policy defines a Markov reward process on $\mathcal{S}$, and in particular a Markov chain. We say that a policy is **ergodic**, **recurrent** or **unichain** if the associated Markov chain is respectively ergodic (irreducible and aperiodic), irreducible or if it has a unique stationary probability distribution (unique recurrent component), see (Levin and Peres, 2017, §1) for more details on the terminology.

Given a policy $\pi \in \Pi^{\text{SR}}$, its **gain** $g^\pi$ is the amount of reward that the policy collects in average and in the long run; Its **bias** $b^\pi$ is the amount of reward that it collects in addition to the gain, visually:

$$g^\pi(s; M) := \lim_{T \to \infty} \mathbf{E}_s^{M, \pi} \left[ \frac{1}{T} \sum_{t=1}^{T} R_t \right] \quad \text{and} \quad b^\pi(s; M) := \text{Clim}_{T \to \infty} \mathbf{E}_s^{M, \pi} \left[ \sum_{t=1}^{T} (R_t - g^\pi(S_t; M)) \right] \quad (3)$$

where Clim is the Cesàro-limit. The **gap function** of a policy $\pi \in \Pi^{\text{SR}}$ is $\Delta^\pi(s, a; M) := g^\pi(s; M) + b^\pi(s; M) - r(s, a) - p(s, a)b^\pi(M)$. When too heavy to carry, the dependence on $M$ may be dropped in notations to lighten up everything. Following standard Markov decision process theory, all these objects are well-defined, see (Puterman, 2014, §9) for e.g.

### 2.1.2 COMMUNICATING MARKOV DECISION PROCESSES AND DIAMETER

A central assumption that is adopted in the following pages is the communicativity of the underlying model (Assumption 2), meaning that one can travel from any state to any other in finite time under the right policy, i.e., that the diameter is finite. Equivalently, it can be shown that the diameter is finite if, and only if every policy $\pi \in \Pi^{\text{SR}}$ of full support, i.e., every policy such that $\pi(a|s) > 0$ for all $(s, a) \in \mathcal{Z}$, is recurrent. The space of fully supported randomized policies, or **fully randomized policies**, is denoted $\Pi^{\text{SFR}}$.

**Assumption 2.** The model $M$ is communicating, i.e., it has finite diameter:

$$D(M) := \max_{s \neq s'} \min_{\pi \in \Pi} \mathbf{E}_s^{M, \pi} [\inf\{t \ge 1 : S_t = s'\}] < \infty. \quad (4)$$

Assumption 2 is fairly standard in the literature on regret minimization for average reward Markov decision processes, and it can be found in Auer et al. (2009); Filippi et al.
(2010); Tossou et al. (2019); Bourel et al. (2020); Fruit et al. (2020); Zhang and Ji (2019); Boone and Gaujal (2023); Saber et al. (2024); Boone and Gaujal (2025) for example. This assumption is much weaker than the well-known ergodic assumption, found in Agrawal et al. (1988); Burnetas and Katehakis (1997) for e.g.. Indeed, if a Markov decision process is ergodic, every state is recurrent under every policy, so that the diameter (Assumption 2) is automatically finite. The converse is wrong: All the examples of Markov decision processes that we provide in this work (see Figures 1 to 3 and 4) are communicating but not ergodic.

### 2.1.3 OPTIMAL POLICIES, GAIN, BIAS AND THE BELLMAN GAPS

Given a model $M$, a policy $\pi^* \in \Pi^{SR}$ is said **gain optimal**, written $\pi^* \in \Pi^*(M)$, if it achieves maximal gain over all possible policies, i.e.,

$$g^{\pi^*}(s; M) = g^*(s; M) := \max_{\pi \in \Pi^{SR}} g^{\pi}(s; M) \quad (5)$$

regardless of the initial state $s \in S$. The vector $g^*(M) \in \mathbb{R}^S$ is the optimal gain vector. A policy $\pi^*$ is said **bias optimal** if it maximizes the bias among gain optimal policies, i.e., if $\pi^* \in \Pi^*(M)$ and $b^{\pi^*}(s; M) = b^*(s; M) := \max_{\pi \in \Pi^*(M)} b^{\pi}(s; M)$ for all initial state $s \in S$. The vector $b^*(M) \in \mathbb{R}^S$ is the optimal bias vector. According to standard theory (Puterman, 2014, §9), deterministic gain and bias optimal policies exist. Lastly, the **Bellman gaps** are the gaps of bias optimal policies, given by

$$\Delta^*(s, a; M) := g^*(s; M) + b^*(s; M) - r(s, a) - p(s, a)b^*(M). \quad (6)$$

Under the communicating assumption (Assumption 2), it is well-known that the optimal gain does not depend on the initial state with $\text{sp}(g^*(M)) = 0$ and that Bellman gaps are non-negative.

### 2.1.4 OPTIMAL AND WEAKLY OPTIMAL STATE-ACTION PAIRS

We borrow the classification of pairs from Boone and Maillard (2025).

**Definition 1** (Optimal, weakly optimal and sub-optimal pairs). Let $M \equiv (\mathcal{Z}, p, \nu)$ be a communicating model (Assumption 2). A pair $z \in \mathcal{Z}$ is said **weakly optimal** if $\Delta^*(z) = 0$, written $z \in \mathcal{Z}^*(M)$; A pair $z \equiv (s, a) \in \mathcal{Z}$ is said **optimal** if it is recurrent under some gain optimal policy, i.e., there exists $\pi \in \Pi^*(M)$ such that $\mathbf{P}_{s}^{M,\pi}(\forall n, \exists m \ge n : Z_m = z) = 1$, and in that case we write $z \in \mathcal{Z}^{**}(M)$.

When a model $M$ is communicating, it is known that $\mathcal{Z}^{**}(M) \subseteq \mathcal{Z}^*(M)$ with equality if, and only if there exists a recurrent gain optimal policy Boone and Maillard (2025). In spirit, optimal pairs are all the pairs that are played infinitely often by gain optimal policies, while weakly optimal pairs that are not optimal correspond to their transient counterparts. Weakly optimal pairs are pairs that can be played without increasing the regret, see Definition 2 and the discussion on (7). In light of this property, a pair $z \notin \mathcal{Z}^*(M)$ is said **sub-optimal**.

## 2.2 Learning algorithms, regret minimization and lower bounds

Formally, a **learning algorithm** is a kernel $\Lambda: \mathcal{H} \to \mathcal{P}(\mathcal{A})$, mapping histories to probabilities over actions. Similarly to policies, the choice of a learning algorithm $\Lambda$, a Markov decision
process $M$ and an initial state $s_0 \in S$ completely determines the distribution of the history $H_t$ for all $t \ge 1$; We write $\mathbf{P}_{s_0}^{M,\Lambda}(-)$ and $\mathbf{E}_{s_0}^{M,\Lambda}[-]$ the probability and expectation operators over the induced probability space on $\mathcal{H}$. The **visit count** at time $t \ge 1$ of a pair $z \in \mathcal{Z}$ is the number of time this pair has been visited prior to time $t$, denoted $N_t(z) := \sum_{i=1}^{t-1} \mathbf{1}(Z_i = z)$.

### 2.2.1 THE EXPECTED REGRET

In this paper, we measure the learning performance of learning algorithms with the regret.

**Definition 2** (Regret, Auer et al. (2009)). The **expected regret** of a learning algorithm $\Lambda$ in the model $M$ at horizon $T \ge 1$ and from the initial state $s_0 \in S$ is given by

$$ \text{Reg}(T; M, \Lambda, s_0) := \mathbf{E}_{s_0}^{M,\Lambda} \left[ T g^*(s_0; M) - \sum_{t=1}^{T-1} R_t \right]. $$

Under the communicating assumption (Assumption 2), it appears that the initial state $s_0 \in S$ is not important conceptually, and we will often willingly forget it in equations.

The idea behind the definition of the regret Definition 2 is that by writing $\mathbf{E}[R_t|S_t, A_t] = g^*(S_t) + b^*(S_t) - b^*(S_{t+1}) - \Delta^*(S_t, A_t)$ and summing for $t \ge 1$, we have

$$ \mathbf{E}_{s_0}^{M,\Lambda} \left[ \sum_{t=1}^{T} R_t \right] = T g^*(s_0) + b^*(s_0) - \mathbf{E}_{s_0}^{M,\Lambda} [b^*(S_{T+1})] - \mathbf{E}_{s_0}^{M,\Lambda} \left[ \sum_{t=1}^{T} \Delta^*(Z_t) \right]. \quad (7) $$

In (7), the quantity $\sum_{t=1}^{T} \Delta^*(Z_t)$ is non-negative by non-negativity of Bellman gaps. It follows that for every learning algorithm $\Lambda$, we have $\mathbf{E}^{M,\Lambda}[\sum_{t=1}^{T} R_t] \le T g^* + \text{sp}(b^*)$. Similarly, we obtain that $\mathbf{E}^{M,\pi}[\sum_{t=1}^{T} R_t] \ge T g^* - \text{sp}(b^*)$ for every bias optimal policy $\pi$. So, $T g^*$ is a good comparison proxy for the performance of the optimal policy—hence the definition of the regret. Note that (7) also shows that the expected regret is the sum of the Bellman gaps up to a bounded error, with $\text{Reg}(T; M, \Lambda, s_0) = \mathbf{E}_{s_0}^{M,\Lambda}[\sum_{t=1}^{T} \Delta^*(Z_t)] + O(1)$, meaning that the regret only grows when sub-optimal pairs are played.

### 2.2.2 CONSISTENT ALGORITHMS AND LOWER BOUND OF BOONE AND MAILLARD (2025)

Every regret lower bound requires a form of assumption on the class of learning algorithms that we consider. The point is to discard algorithms that overspecialize their performance to a happy few Markov decision processes. Following a large panel of the literature, we restrict the focus to **consistent** algorithms (see Definition 3), also known as strong consistency or uniformly fast convergence, see Lattimore and Szepesvári (2020) for e.g.

**Definition 3** (Consistency). A learning algorithm $\Lambda$ is said **consistent** on a space of Markov decision processes $\mathcal{M}$ if, for all $\eta > 0$, all $M \in \mathcal{M}$ and $s_0 \in S$, $\text{Reg}(T; M, \Lambda, s_0) = o(T^\eta)$.

Consistency is the assumption under which Boone and Maillard (2025) state their regret lower bound $\text{Reg}(T; M, \Lambda) \ge K(M) \log(T) + o(\log(T))$ that we recall in Theorem 1.

The constant $K(M) \in [0, \infty)$ is the solution of an optimization problem that is about gathering a sufficient amount of information for a minimal cost. That optimization problem goes over $\mu$ within the polytope of invariant measures $\text{Inv}(M)$ (Definition 4); The objective function is $\sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z)$, that is directly related to the regret; And $\mu \in \text{Inv}(M)$ must
further satisfy an information constraint, consisting in that $\sum_{z \in \mathcal{Z}} \mu(z)KL(M(z)||M^{\dagger}(z)) \ge 1$ for every model $M^{\dagger} \in \text{Cnf}(M)$. In that information constraint, $\text{Cnf}(M)$ is the confusing set (Definition 5), which is in the collection of models that coincide with $M$ on optimal pairs $\mathcal{Z}^{**}(M)$ and such that $M$ and $M^{\dagger}$ do not share any gain optimal policy. That information constraint can be interpreted as a rejection principle: Enough information must be gathered in order to “reject” every confusing model.

**Definition 4 (Invariant measures).** An invariant measure of a Markov decision process $M$ is a vector $\mu \in \mathbb{R}_{+}^{\mathcal{Z}}$ such that, for all $s \in S$, we have $\sum_{a \in \mathcal{A}(s)} \mu(s, a) = \sum_{z \in \mathcal{Z}} \mu(z)p(s|z)$.

**Definition 5 (Confusing set, Boone and Maillard (2025)).** Fix $\mathcal{M}$ a space of Markov decision process. The confusing set of a communicating model $M \in \mathcal{M}$ is

$$ \text{Cnf}(M) := \{ M^{\dagger} \in \mathcal{M} : M^{\dagger} \gg M, M^{\dagger} = M \text{ on } \mathcal{Z}^{**}(M) \text{ and } \Pi^{*}(M^{\dagger}) \cap \Pi^{*}(M) = \emptyset \} $$

where $M^{\dagger} \gg M$ means that $\nu^{\dagger}(z) \gg \nu(z)$ and $p^{\dagger}(z) \gg p(z)$ for all $z \in \mathcal{Z}$, or equivalently, that $\text{supp}(\nu^{\dagger}(z)) \supseteq \text{supp}(\nu(z))$ and $\text{supp}(p^{\dagger}(z)) \supseteq \text{supp}(p(z))$ for all $z \in \mathcal{Z}$.

With Definition 4 and Definition 5 in hand, we can state the lower bound of Boone and Maillard (2025).

**Theorem 1 (Boone and Maillard (2025)).** Fix $\mathcal{M}$ a space of Markov decision process. For every learning algorithm $\Lambda$ that is consistent on $\mathcal{M}$, for all $M \in \mathcal{M}$ that is communicating (Assumption 2) and $s_0 \in S$, we have $\text{Reg}(T; M, \Lambda, s_0) \ge K(M) \log(T) + o(\log(T))$ where $K(M) \in [0, \infty]$ is given by

$$ \inf \left\{ \sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z) : \mu \in \text{Inv}(M) \text{ and } \inf_{M^{\dagger} \in \text{Cnf}(M)} \left\{ \sum_{z \in \mathcal{Z}} \mu(z) KL(M(z)||M^{\dagger}(z)) \right\} \ge 1 \right\} \quad (8) $$

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

Any measure $\mu \in \text{Inv}(M)$ achieving $K(M)$ is called an **optimal exploration measure**.<fnref n="1" />

In the remaining of this paper, we show that the lower bound described in Theorem 1 is tight. We provide a consistent learning algorithm $\Lambda$ such that $\text{Reg}(T; M, \Lambda) \le K(M) \log(T) + o(\log(T))$ under mild condition on the ambient space $\mathcal{M}$. As a consequence, the constant $K(M)$ given above is the right measure of the learning difficulty of the communicating model $M$ in the asymptotic regime $T \to \infty$.

### 3 A framework of asymptotically optimal algorithms: ECoE

To begin our paper, we present the framework of ECoE, standing for Exploration-Coexploration-Exploitation. That framework of algorithms is inspired from the lower bound of Theorem 1 and from intermediate results of Boone and Maillard (2025). We will start by describing the framework from a high level perspective, then provide an instance $\Lambda$ of ECoE in Section 5 that we prove to be asymptotically optimal. More specifically, we prove that our algorithm $\Lambda$ satisfies $\text{Reg}(T; M, \Lambda, s_0) \le K(M) \log(T) + o(\log(T))$ for all communicating model $M$ and initial state $s_0 \in S$.

The ECoE framework combines three main components:

<footnote n="1">1. We show that such measures exist in Appendix B.</footnote>
(1) **Exploration**, that is about playing sub-optimal pairs (Section 2.1.4) to obtain information. It turns out the cost of exploration is of order $log(T)$ and accounts for the dominant part of the regret lower bound. Accordingly, $K(M)$ and the associated optimization problem (8) describe the optimal way to explore the environment $M$. In Section 3.1, we explain how to obtain an optimal exploration policy from (8).

(2) **Co-Exploration**, that makes sure that all optimal pairs (Definition 1) are visited over-logarithmically. The cost of co-exploration is $o(\log(T))$, that is negligible in front of the cost of exploration. For general communicating Markov decision processes, co-exploration brings new challenges that are absent from the ergodic setting and multi-armed bandits. They are discussed in more details in Section 3.2.

(3) **Exploitation**, that is about scoring maximally when there is no apparent need to collect information. In Section 3.3, we explain how to choose the exploitation policy and how to determine whether information is lacking or not.

## 3.1 Retrieving a good exploration policy by estimating $K(M)$

The regret lower bound of Theorem 1 is only about gathering information outside of $\mathcal{Z}^{**}(M)$; Indeed, as the information constraint “$\inf_{M^\dagger \in \text{Cnf}(M)} \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^\dagger(z)) \ge 1$” only involves models $M^\dagger$ that coincide with $M$ on $\mathcal{Z}^{**}(M)$ by definition, the bound of Theorem 1 tells nothing about the behavior of consistent learning algorithms outside of $\mathcal{Z}^{**}(M)$. So, essentially, Theorem 1 claims that the dominant part of the regret is scaling logarithmically and is due to exploration exclusively.

In fact, it also says *how* to explore optimally.

Indeed, Equation (8) can be rewritten in terms of an optimization problem over policies. The policy obtained by solving it can be used to explore optimally; Such a policy is called an optimal exploration policy. The precise alternative form for $K(M)$ is found in Proposition 2, where we show that the computation of the lower bound is about finding a policy $\pi$ that optimizes the ratio of the gain-loss $g^*(M) - g^\pi(M)$ and of the amount of gathered information $\inf_{M^\dagger \in \text{Cnf}(M)} \sum_{z \in \mathcal{Z}} \mu^\pi(z) \text{KL}(M(z) || M^\dagger(z))$ under that policy.

**Proposition 2** (Policy-wise formulation of $K(M)$). Fix $\mathcal{M}$ a space of Markov decision processes. Let $M \in \mathcal{M}$ be a communicating model. For $\pi \in \Pi^{\text{SFR}}$ a fully randomized policy (Section 2.1.2), denote by $\mu^\pi$ its unique probability invariant measure in $M$ (i.e., the unique probability invariant measure of the Markov chain that $\pi$ induces on $\mathcal{Z}$, see Proposition A.5 (1)). We have

$$ K(M) = \inf_{\pi \in \Pi^{\text{SFR}}} \left\{ \frac{g^*(M) - g^\pi(M)}{\inf_{M^\dagger \in \text{Cnf}(M)} \sum_{z \in \mathcal{Z}} \mu^\pi(z) \text{KL}(M(z) || M^\dagger(z))} \right\} \quad (9) $$

with the convention $x/0 = +\infty$ for $x \in \mathbf{R}_+$.

Note that for $\pi \in \Pi^{\text{SFR}}$, we have $\mu^\pi(s, a) = \lim_{T \to \infty} \frac{1}{T} \mathbf{E}_s^{M, \pi}[\sum_{t=1}^T \mathbf{1}(Z_t = (s, a))]$.

The infimum in (9) is not a minimum in general, meaning that optimal exploration is not guaranteed to be reached by fully uniform policies. This concern is minor, because the learning algorithm will only have access to a noisy version of $M$, so getting an approximation of $K(M)$ is fine anyway—provided that the approximation can be arbitrarily precise. The take-away is that Equation (9) encourages a natural approach: Compute a fully randomized
exploration policy that optimizes the cost/information gain trade-off well enough and use it to explore efficiently. So, provided that we can solve (9), the problem of optimal exploration is dealt with.

**Proof of Proposition 2** If $K(M) = +\infty$, there is nothing to prove. Assume $K(M) < \infty$.

Denote $C(\mu; M) := \inf_{M^\dagger \in \text{Cnf}(M)} \sum_{z \in \mathcal{Z}} \mu(z)\text{KL}(M(z) || M^\dagger(z))$ the amount of information gathered by a measure $\mu \in \mathbf{R}_+$. Note that every element $\mu \in \text{Inv}(M)$ is of the form $\lambda\mu'$ with $\lambda \in \mathbf{R}_+$ and $\mu' \in \text{Inv}(M) \cap \mathcal{P}(\mathcal{Z})$. So, from (8), we have

$$K(M) = \inf_{\mu \in \text{Inv}(M) \cap \mathcal{P}(\mathcal{Z})} \left\{ \frac{\sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z)}{C(\mu; M)} \right\}$$

with the convention $x/0 = +\infty$ for $x \in \mathbf{R}_+$. Now, we replace $\text{Inv}(M) \cap \mathcal{P}(\mathcal{Z})$ by $\mathcal{I}_{>0}(M) := \{\mu \in \text{Inv}(M) : \mu \in \mathcal{P}(\mathcal{Z}) \text{ and } \text{supp}(\mu) = \mathcal{Z}\}$ the set of fully supported probability invariant measures of $\mu$. It is obvious that $K(M) \le \inf_{\mu \in \mathcal{I}_{>0}(M)} \{\sum_{z \in \mathcal{Z}} \mu(z)\Delta^*(z)/C(\mu; M)\}$ and we focus on the reverse inequality, that is obtained by approximating probability invariant measures by fully supported ones using Theorem A.6. Given $\varepsilon > 0$, let $\mu_\varepsilon \in \text{Inv}(M) \cap \mathcal{P}(\mathcal{Z})$ be such that $\sum_{z \in \mathcal{Z}} \mu_\varepsilon(z)\Delta^*(z)/C(\mu_\varepsilon; M) \le K(M) + \varepsilon$. By Theorem A.6, for all $\varepsilon' > 0$, there exists $\mu_{\varepsilon, \varepsilon'} \in \mathcal{I}_{>0}(M)$ such that $\|\mu_{\varepsilon, \varepsilon'} - \mu_\varepsilon\|_\infty \le \varepsilon'$ and $\mu_{\varepsilon, \varepsilon'} \ge (1 - \varepsilon')\mu_\varepsilon$. So,

$$
\begin{align*}
\inf_{\mu \in \mathcal{I}_{>0}(M)} \left\{ \frac{\sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z)}{C(\mu; M)} \right\} &\le \inf_{\varepsilon > 0} \inf_{\varepsilon' > 0} \left\{ \frac{\sum_{z \in \mathcal{Z}} \mu_{\varepsilon, \varepsilon'}(z) \Delta^*(z)}{\inf_{M^\dagger \in \text{Cnf}(M)} \mu_{\varepsilon, \varepsilon'}(z) \text{KL}(M(z) || M^\dagger(z))} \right\} \\
&\le \inf_{\varepsilon > 0} \inf_{\varepsilon' > 0} \left\{ \frac{\sum_{z \in \mathcal{Z}} \mu_\varepsilon(z) \Delta^*(z) + \varepsilon' \|\Delta^*\|_\infty}{(1 - \varepsilon') \inf_{M^\dagger \in \text{Cnf}(M)} \mu_\varepsilon(z) \text{KL}(M(z) || M^\dagger(z))} \right\} \\
&\le \inf_{\varepsilon > 0} \inf_{\varepsilon' > 0} \left\{ \frac{1}{1 - \varepsilon'} \left( K(M) + \varepsilon + \frac{\varepsilon' \|\Delta^*\|_\infty}{C(\mu_\varepsilon; M)} \right) \right\} \\
&\stackrel{(\S)}{=} \inf_{\varepsilon > 0} \{K(M) + \varepsilon\} = K(M)
\end{align*}
$$

where $(\dagger)$ follows by definition of $\mu_{\varepsilon, \varepsilon'}$; $(\ddagger)$ follows by definition on $\mu_\varepsilon$; and $(\S)$ follows from $C(\mu_\varepsilon; M) > 0$, that holds because $\sum_{z \in \mathcal{Z}} \mu_\varepsilon(z)\Delta^*(z)/C(\mu_\varepsilon; M) < \infty$.

We conclude using Proposition A.5 to rewrite the optimization problem over $\Pi^{\text{SFR}}$:

$$
\begin{align*}
\inf_{\mu \in \mathcal{I}_{>0}(M)} \left\{ \frac{\sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z)}{C(\mu; M)} \right\} &\stackrel{(\dagger)}{=} \inf_{\pi \in \Pi^{\text{SFR}}} \left\{ \frac{\sum_{z \in \mathcal{Z}} \mu^{\pi}(z) \Delta^*(z)}{C(\mu^{\pi}; M)} \right\} \\
&\stackrel{(\ddagger)}{=} \inf_{\pi \in \Pi^{\text{SFR}}} \left\{ \frac{\lim_{s_0} \mathbf{E}_{s_0}^{M, \pi} \left[ \frac{1}{T} \sum_{z \in \mathcal{Z}} \sum_{t=1}^T \mathbf{1}(Z_t = z) \Delta^*(z) \right]}{C(\mu^{\pi}; M)} \right\} \\
&\stackrel{(\S)}{=} \inf_{\pi \in \Pi^{\text{SFR}}} \left\{ \frac{\lim_{s_0} \mathbf{E}_{s_0}^{M, \pi} \left[ \frac{1}{T} \sum_{t=1}^T (g^* + b^*(S_t) - b^*(S_{t+1}) - R_t) \right]}{C(\mu^{\pi}; M)} \right\} \\
&\stackrel{(\S)}{=} \inf_{\pi \in \Pi^{\text{SFR}}} \left\{ \frac{g^*(s_0) - g^*(s_0)}{C(\mu^{\pi}; M)} \right\} \stackrel{(\#)}{=} \inf_{\pi \in \Pi^{\text{SFR}}} \left\{ \frac{g^* - g^\pi}{C(\mu^{\pi}; M)} \right\}
\end{align*}
$$

where $(\dagger)$ follows from Proposition A.5 (2); $(\ddagger)$ follows from Proposition A.5 (1) and introduces $s_0 \in \mathcal{S}$ arbitrary; $(\S)$ expands the gaps as $\Delta^*(Z_t) = g^*(S_t) + b^*(S_t) - r(Z_t) - p(Z_t)b^*$; $(\#)$ follows by definition of the gain of $\pi$; and $(\#)$ uses that $s_0 \in \mathcal{S}$ is arbitrary. ■
## 3.2 Co-exploration: Traveling between components of optimal pairs

By construction of $K(M)$, exploration is not meant to gather information on optimal pairs. Boone and Maillard (2025) show that optimal pairs are treated differently than others, in that they are visited over-logarithmically. They show that, for all optimal pair $z \in \mathcal{Z}^{**}(M)$, all consistent learning algorithm $\Lambda$ and provided that $M$ is rich enough, we have

$$ \liminf_{T \to \infty} \frac{\mathbf{E}_{s_0}^{M, \Lambda}[N_T(z)]}{\log(T)} = +\infty. \quad (10) $$

To guarantee that (10) is satisfied, ECoE is careful at its choice for the exploitation policy, for how long it iterates it, and when it iterates it, for the consequence of (10) is that during play, $\mathcal{Z}^{**}(M)$ must be covered uniformly fast. That motivates the ideas thereafter.

(I) The exploitation policy $\pi^+$ must be of maximal support among $\mathcal{Z}^{**}(M)$. Ideally, we want to pick $\pi^+(-|s|)$ uniform on $\{a \in \mathcal{A}(s) : (s, a) \in \mathcal{Z}^{**}(M)\}$.

(II) The exploitation policy is iterated up to regeneration, i.e., we wait for a return to the initial state it was first iterated from. By doing so, we guarantee that all the states of the current recurrent classes are visited with positive probability.

### 3.2.1 AN ISSUE: THE NUMBER OF TRAVELS

One difficulty arise—one that does not exist for ergodic Markov decision processes: The set of optimal pairs $\mathcal{Z}^{**}(M)$ may be split into several components that may only be accessible by playing sub-optimal pairs (see Definition 6 for a formal definition of components). One such example is provided in Figure 1.

<figure><img src="image_3.png" /><figcaption>Figure 1: A class of Markov decision processes with deterministic transitions parameterized by $\theta$ where co-exploration is troublesome. Arrows are choices of actions that deterministically lead to the pointed state and labels are rewards.</figcaption></figure>

Consider the class of Markov decision processes $M := \{M_\theta : |\theta| \le \frac{1}{2}\}$ where $M_\theta$ is the model with Bernoulli rewards described Figure 1. Note that the policy alternating between the states 1 and 2 is never gain optimal for $M_\theta \in M$. Now, consider $M_0 \in M$ and let $\Lambda^*$ be an asymptotically optimal algorithm for $M$, i.e., assume that $\Lambda^*$ is such that $\text{Reg}(T; M_\theta, \Lambda^*) \le K(M_\theta) \log(T) + o(\log(T))$ for all $\theta \in \Theta$. In $M_0$, optimal pairs consists in the two loops $\mathcal{Z}^{**}(M_0) = \{(1, 1), (2, 2)\}$ and are separated by sub-optimal transitions of null reward. In the first hand, the algorithm $\Lambda^*$ must alternate infinitely often between the states 1 and 2 because (10) is satisfied. On the second hand, we see that the confusing set of $M_0$ relatively to $M$ is empty, so that $K(M_0) = 0$. Accordingly, $\text{Reg}(T; M_0, \Lambda^*) = o(\log(T))$. So,

$$ \mathbf{E}^{M_0, \Lambda^*}[N_T(1, 2) + N_T(2, 1)] = o(\log(T)). $$
Interestingly, $M_0$ is the same example as in (Ortner, 2010, Figure 2) that is used to motivate the use of episodes in UCYCLE Ortner (2010), UCRL2 Auer et al. (2009) and all the algorithms that followed. These algorithms make $\Omega(\log(T))$ episodes, and because of it, we see that on $M_0$ above, they switch $\Omega(\log(T))$ times between the loops on the states 1 and 2. Therefore, the regret of these algorithms is $\Omega(\log(T))$ on $M_0$ and they are not asymptotically optimal— provided that Theorem 1 is tight, which is yet to be shown.

**Definition 6 (Component of pairs).** Let $M \equiv (\mathcal{Z}, p, \nu)$ be a model and let $\mathcal{Z}' \subseteq \mathcal{Z}$ be a subset of pairs. A communicating component of $\mathcal{Z}'$, or just **component**, is a maximal set $\mathcal{Z}'' \subseteq \mathcal{Z}'$ such that the restrained model $M'' := (\mathcal{Z}'', p|_{\mathcal{Z}''}, \nu|_{\mathcal{Z}''})$ is well-defined<fnref n="2" /> and communicating.

### 3.2.2 REDUCING THE NUMBER OF TRAVELS WITH THE SQUARE TRICK

To reduce the number of travels between the several possibles components (Definition 6) of $\mathcal{Z}^{**}(M)$, ECoE uses a variant of the doubling trick (see Auer et al. (2009)) that we call the **square trick (ST).**

(III) Before exploiting, we check if it is worth traveling to another component of $\mathcal{Z}^{**}(M)$: We decompose $\mathcal{Z}^{**}(M)$ into components $\mathcal{Z}_1, \dots, \mathcal{Z}_c$, and denote $\mathcal{Z}_0 \in \{\mathcal{Z}_1, \dots, \mathcal{Z}_c\}$ the component the algorithm is currently on. If

$$ \min_{1 \le i \le c} \min_{z \in \mathcal{Z}_i} N(z) < \sqrt{\min_{z \in \mathcal{Z}_0} N(z)}, \qquad (\text{ST}) $$

then, we travel to the least visit component of $\mathcal{Z}^{**}(M)$; Otherwise, we exploit on the current component $\mathcal{Z}_0$ as described in points (1) and (2) upstream.

Note the ressemblance of (ST) with the forced exploration rule of the D-Tracking rule of (Garivier and Kaufmann, 2016, §3.1) in the setting of best-arm identification. Similarly to the D-Tracking rule, the square root of the square trick (ST) is not really important, and $\sqrt{\min_{z \in \mathcal{Z}_0} N(z)}$ in (ST) could be replaced by $(\min_{z \in \mathcal{Z}_0} N(z))^{\alpha}$ for arbitrary $\alpha \in (0, 1)$.

### 3.3 The exploration test: Testing if information is lacking or not

The last component that we need to discuss is how the algorithm should decide whether information is lacking or not. By (Boone and Maillard, 2025, Corollary 7), provided that $\Lambda$ is a consistent learning algorithm, for all $M^{\dagger} \in \text{Cnf}(M)$, we have

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

Equation (11) translates the idea that consistent learning algorithms must gather enough information in order to “reject” confusing model. The term $\mathbf{E}^{M,\Lambda}[\sum_{z \in \mathcal{Z}} N_T(z) \text{KL}(M(z) || M^{\dagger}(z))]$ is an expected log-likelihood ratio. One recognizes in $\sum_{z \in \mathcal{Z}} N_T(z) \text{KL}(M(z) || M^{\dagger}(z))$ the dominant term in the likelihood that $M^{\dagger}$ is to generate empirical data resembling $M(z)$ after

<footnote n="2">2. By **well-defined**, we mean that by writing $\mathcal{Z}'' \equiv \prod_{s'' \in S''} \{s''\} \times \mathcal{A}''(s'')$, we have $\text{supp} p(z'') \subseteq S''$ for all $z'' \in \mathcal{Z}''$ and $\mathcal{A}''(s'') \neq \emptyset$ for all $s'' \in S''$.</footnote>
$N_T(z)$ samples at the pair $z \in \mathcal{Z}$ for every $z \in \mathcal{Z}$, as stated by Sanov's theorem. Overall, a good proxy for the above is to state that $\Lambda$ lacks information under history $H_T$ if

$$ \inf_{M^{\dagger} \in \text{Cnf}(M)} \left\{ \sum_{z \in \mathcal{Z}} N_T(z) \text{KL}(M(z) || M^{\dagger}(z)) \right\} < (1 + f(H_T)) \log(T) \quad (12) $$

where $f: \mathcal{H} \to \mathbb{R}_+$ is some well-chosen vanishing function that accounts for second order errors in Sanov's theorem. Therefore, we will require ECoE to explore “often enough” whenever information is lacking in the sense of (12).

### 3.4 The algorithmic scheme of ECoE

Combining the ideas of Sections 3.1 to 3.3, we end up with an algorithmic scheme that we name ECoE and summarize in Algorithm 1.

<caption>**Algorithm 1** The ECoE framework, informal.</caption>

1: **for** phases $k = 1, 2, \dots$ **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;Estimate optimal pairs $\mathcal{Z}^{**}(M)$ out of empirical data;
3: &nbsp;&nbsp;&nbsp;&nbsp;Compute the exploitation policy $\pi^+$ as uniform over $\mathcal{Z}^{**}(M)$, see Section 3.3, (1);
4: &nbsp;&nbsp;&nbsp;&nbsp;Compute the exploration policy $\pi^-$ by estimating $K(M)$ as in (9);
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $S_t$ is not recurrent under $\pi^+$ or lacking information in the sense of (12) **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Explore with $\pi^-$ one step; ▷ Vanilla exploration
7: &nbsp;&nbsp;&nbsp;&nbsp;**else if** (ST) one component of $\mathcal{Z}^{**}(M)$ is sub-visited **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Explore with $\pi^-$ one step; ▷ Exploration travel triggered by co-exploration
9: &nbsp;&nbsp;&nbsp;&nbsp;**else**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Exploit by iterating $\pi^+$ until regeneration, see Section 3.3 (2); ▷ Exploitation
11: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
12: **end for**

The algorithm ECoE works into phases. For every phase, ECoE estimates the set of optimal pairs $\mathcal{Z}^{**}(M)$, an exploitation policy $\pi^+$ and an exploration policy $\pi^-$. If ECoE is outside of the recurrent components of $\pi^+$, it explores. Otherwise, ECoE checks if it is lacking information, in which case it explores by iterating $\pi^-$ once. Otherwise, ECoE checks if information is unbalanced on $\mathcal{Z}^{**}(M)$, in which case it tries to reach the least visited component using the exploration policy $\pi^-$—it would be better to use a specifically designed policy $\pi^\pm$ that travels within the environment more efficiently than $\pi^-$, and this is definitively something to take into consideration for any serious implementation of ECoE, but the regret analysis will be easier this way. Otherwise, the current amount of information is considered to be enough everywhere, and ECoE exploits by playing $\pi^+$ until regeneration.

### 4 Estimating the regret lower bound $K(M)$ out of noise

There is a fundamental issue with the algorithmic scheme ECoE described in Algorithm 1.

Algorithm 1 aims for asymptotically optimal regret by approximating the regret lower bound frontally. At the beginning of every phase, ECoE estimates the optimal pairs $\mathcal{Z}^{**}(M)$ that it later splits into communicating components, computes an exploitation policy and
computes an exploration policy by estimating $K(M)$. This is where the issue lies: Obviously, ECoE does not have access to $M$, so all these estimations must be done out of empirical data.

The naive approach is to estimate $\mathcal{Z}^{**}(M)$ and $K(M)$ via the maximum likelihood estimator of $M$, i.e., as $\mathcal{Z}^{**}(\hat{M})$ and $K(\hat{M})$ respectively. This approach fails completely. Indeed, the set of optimal pairs $\mathcal{Z}^{**}(M)$ and the regret lower bound $K(M)$ are both discontinuous functions of $M$ and $M \approx \hat{M}$ does not guarantee that $\mathcal{Z}^{**}(M) \approx \mathcal{Z}^{**}(\hat{M})$ nor $K(M) \approx K(\hat{M})$. So, in order to estimate optimal pairs $\mathcal{Z}^{**}(M)$ and the regret lower bound $K(M)$ out of the empirical estimate $\hat{M}$, we need smooth approximates of these two; This is the aim of this section. We begin by describing the discontinuity issue in Section 4.1, then define regularized versions of $\mathcal{Z}^{**}(M)$ and $K(M)$ in Sections 4.2 and 4.3. The well-behavior of our regularized lower bound is described in Section 4.4.

## 4.1 Difficulties due to the discontinuity of the lower bound

The discontinuity of the lower bound is due to the discontinuity of $\mathcal{Z}^*(M)$, the set of weakly optimal pairs (Definition 1), therefore producing discontinuities of optimal pairs $\mathcal{Z}^{**}(M)$ and of the confusing set Cnf($M$). To be fair, such discontinuities are already present in the simpler settings of multi-armed bandits and ergodic Markov decision processes. Yet, nobody ever complained about it. As a matter of fact, algorithms such as IMED of Honda and Takemura (2015), KLUCB of Cappé et al. (2013) or TS of Thompson (1933); Agrawal and Goyal (2012); Kaufmann et al. (2012) (for bandits) and IMED-RL Pesquerel and Maillard (2022) (for ergodic Markov decision processes) all are asymptotically optimal and none need to handle the discontinuity of $K(M)$ like we do in this work. But because of the design of ECoE, we have no choice. Indeed, ECoE requires the computation of $K(M)$ and $\mathcal{Z}^{**}(M)$ for every of its three components. For exploration purposes, ECoE approximates a near-optimal exploration policy using (9) via the computation of $K(M)$; For co-exploration purposes, ECoE explicitly needs $\mathcal{Z}^{**}(M)$ to balance the visits counts on components of $\mathcal{Z}^{**}(M)$ via the square trick (ST); For exploitation purposes, ECoE explicitly needs $\mathcal{Z}^{**}(M)$ because its exploitation policy is uniform on $\mathcal{Z}^{**}(M)$.

So, these discontinuities must be dealt with by regularizing $K(M)$ and $\mathcal{Z}^{**}(M)$. In Section 4.1.1, we discuss an example of discontinuity to motivate our regularization solution. Especially, we stress that it all boils down to the smoothing of $\mathcal{Z}^{**}(M)$. The regularization principle is stated in Section 4.1.2 and is extensively discussed in the next Section 4.2.

### 4.1.1 AN EXAMPLE OF DISCONTINUITY WITH DETERMINISTIC TRANSITIONS

In this paragraph, we provide an explicit example with a discontinuity of $\mathcal{Z}^{**}(M)$ and of $K(M)$, see Figure 2.

In Figure 2, we present two models $M$ and $M_\theta$ that are statistically indistinguishable when $\theta \to 0$. On $M \equiv M_0$, the optimal pairs are $\mathcal{Z}^{**}(M) = \{(1, *), (2, \dagger), (2, \ddagger)\}$ and are displayed in red. On $M_\theta$ for $\theta > 0$, the optimal pairs are $\mathcal{Z}^{**}(M_\theta) = \{(2, \dagger)\}$, also displayed in red. So, we observe a discontinuity of $\mathcal{Z}^{**}$ at $\theta = 0$. Note that this discontinuity drastically changes the way the model can be navigated. For $M \equiv M_0$, the state 1 can be reached at any time with zero-cost but for $M_\theta$, it can only be reached by playing sub-optimal pairs. In addition, this discontinuity of optimal pairs produces a discontinuity in confusing sets, since $M_\theta \notin \text{Cnf}(M)$ but $M \in \text{Cnf}(M_\theta)$. Taking the ambient set $\mathcal{M} := \{M_\theta : \theta \in [-0.5, 0.5]\}$ with
<figure><img src="image_4.png" /><figcaption>Figure 2: An example of discontinuity of the regret lower bound. The displayed transitions are deterministic and the labels represent the means of the attached Bernoulli rewards. Actions are distinguished by unique symbols for better readability of the contraction. Optimal pairs are colored in red.</figcaption></figure>

Bernoulli rewards, we can derive the regret lower bounds in closed form:

$$K(M) = \frac{4}{10 \text{kl}(0.1, 0.5)} \quad \text{and} \quad K(M_{\theta}) \underset{\theta \to 0^{+}}{\sim} \frac{\theta}{\text{kl}(0.5 - \theta, 0.5)} \underset{\theta \to 0^{+}}{\sim} \frac{1}{2\theta}$$

where $kl(x, y) := x \log(\frac{x}{y}) + (1-x) \log(\frac{1-x}{1-y})$ is the Kullback-Leibler divergence between $Ber(x)$ and $Ber(y)$. So, $K$ is discontinuous at $M \equiv M_0$. Because $M$ and $M_\theta$ are indistinguishable as $\theta \to 0$, it follows that when the underlying model is $M$, no learner is capable of claiming that the current model isn't $M_\theta$ for $\theta > 0$ with overwhelming confidence. Yet, in this example, when one is doubting about whether the model is $M_\theta$ or $M$, it means that the pairs $(1, *)$ and $(2, \dagger)$ are nearly optimal. In that case, these pairs can arguably be used to navigate the model more easily while scoring near optimally. After all, if the true model is some $M_\theta$ for $\theta > 0$ rather than $M_0$, then the optimality of $(1, *)$ and $(2, \dagger)$ will be ruled out at some point.

### 4.1.2 A NEED FOR A NOTION OF NEAR-OPTIMAL PAIRS

From this discussion, we make the following observations.

(I) If the optimality of a pair is uncertain, it should be considered optimal: Navigation is made easier and if the pair is actually sub-optimal, its optimality will be rejected eventually.

By following the above principle, we will solve the discontinuity problems due to the navigation constraints as well as those due to the discontinuity of the confusing set.

## 4.2 Retrieving optimal pairs under noise via the leveling transform

To smooth the regret lower bound, the central technique is to level the Markov decision process to make all near-optimal pairs simultaneously optimal, so that $Z^{**}(M)$ can be retrieved from $M' \approx M$. The idea of the leveling operation (Definition 7) is to increase the rewards at pairs that are nearly optimal by just the right amount. By “nearly optimal”, we mean pairs with Bellman gaps below a given threshold $\epsilon > 0$.

**Definition 7 (Leveling transform).** Let $M \equiv (Z, p, r)$ a Markov decision process and fix $\epsilon > 0$. The $\epsilon$-leveled transform of $M$ is the model $[M]_\epsilon \equiv (Z, p, [r]_\epsilon)$ with reward function

$$[r]_{\epsilon}(z) := r(z) + \mathbf{1}(\Delta^{*}(z; M) < \epsilon)\Delta^{*}(z; M).$$
An example of the leveling operation is provided in Figure 3. For the model $M$ on Figure 3, the two optimal pairs correspond to the two loops $1 \to 1$ and $2 \to 2$ with associated gain $g^* = 0.5$. In the noisy copy $M'$, only the left loop $1 \to 1$ is optimal with gain $g^* = 0.52$. After leveling $M'$ with threshold $\epsilon = 0.05$, the right loop $2 \to 2$ becomes optimal again and the optimal gain is $g^* = 0.52$. So, $M$ and $[M]_\epsilon$ have the same optimal pairs and gain optimal policies. On this example, we observe that leveling with the right threshold recovers the set of optimal pairs and of gain optimal policies.

<figure><img src="image_5.png" /><figcaption>Figure 3: An example of leveling transform. On the left, a Markov decision process $M$ with two states and two actions per state. Transitions are deterministic and represented by arrows. Labels are rewards. The model $M'$ is a noisy version of $M$.</figcaption></figure>

Motivated by this example, we define the $\epsilon$-leveled optimal pairs as the optimal pairs of the $\epsilon$-leveled transform.

**Definition 8 (Leveled optimal pairs).** Let $M \equiv (\mathcal{Z}, p, r)$ be a Markov decision process and fix $\epsilon > 0$. The $\epsilon$-leveled optimal pairs of $M$ are $Z_\epsilon^{**}(M) := \mathcal{Z}^{**}([M]_\epsilon)$.

In Proposition 3, we show that this leveling operation works as intended. Provided that $\epsilon > 0$ is small enough, that $M'$ is close enough to $M$ relatively to a well-chosen metric (Definition 9) and that $\epsilon$ is large enough relatively to the distance between $M'$ and $M$, then the optimal structure of the $\epsilon$-leveled transform of $M'$ is the same as $M$ at first order: $[M']_\epsilon$ and $M$ have same gain optimal policies and the same optimal pairs.

**Definition 9 (Distances between models).** For $M \equiv (\mathcal{Z}, p, \nu)$ and $M' \equiv (\mathcal{Z}, p', \nu')$ two Markov decision processes with the same pair space, we introduce the following distances:

$$ \|M' - M\| := \max_{z \in \mathcal{Z}} \{|r'(z) - r(z)| + \|p'(z) - p(z)\|_1\}; \quad \text{and} $$

$$ \|M' - M\|^* := \max_{z \in \mathcal{Z}} \{|r'(z) - r(z)| + \|p'(z) - p(z)\|_1 + \infty \cdot \mathbf{1}(p'(z) \not\sim p(z))\}. $$

The operator $\|-\|^*$ will be called the **support-aware norm**.

In Proposition 3 downstream, we express the properties of the leveling transform relatively to two classical quantities of the Markov decision process. The first is the **gain gap**, given by $\Delta^g(M) := \text{dmin}\{\|g^*(M) - g^\pi(M)\|_\infty : \pi \in \Pi\}$, that is the smallest gap between the gain of optimal policies and the gain of sub-optimal policies. The second if the **worst diameter** $D^*(M) := \max_{\pi \in \Pi} D(\pi; M)$ where $D(\pi; M)$ is the policy diameter of $\pi$ (Definition D.1), that is the largest diameter over all possible policies.
**Proposition 3 (Fundamental properties of leveling).** For every communicating Markov decision process $M \equiv (\mathcal{Z}, p, \nu)$, there exists a quantity $C(M) \in \mathbf{R}_+$, that is a rational function of $\Delta^g(M)$ and $D^*(M)$, such that for all $\varepsilon > 0$ and $M' \in \mathcal{M}$ satisfying

$$ \varepsilon + 2C(M)\|M' - M\|^* < \Delta^g(M) \quad \text{and} \quad C(M)\|M' - M\|^* < \varepsilon, \qquad (13) $$

we have

(1) $[M']_\varepsilon$ and $M$ have the same gain optimal policies;

(2) $\mathcal{Z}^{**}([M']_\varepsilon) = \mathcal{Z}^{**}(M)$, i.e., $\mathcal{Z}_\varepsilon^{**}(M') = \mathcal{Z}^{**}(M)$;

The proof of Proposition 3 is deferred to Appendix B.1.

## 4.3 The regularized lower bound $K_\varepsilon(M)$

With the properties of the leveling transform in hand, we can describe the regularized lower bound $K_\varepsilon(M)$, see Definition 12. We combine three regularization mechanisms.

(I) Approximating the confusing set by the $\varepsilon$-leveled confusing set (Definition 11) via the leveling transform: While the confusing set cannot be estimated under noise because of discontinuity issues, its leveled version is continuous.

(II) Approximating invariant measures by $\varepsilon$-uniform invariant measures (Definition 10): Optimizing over uniform invariant measures is encouraged by the formulation (9) of $K(M)$ and is key to the smoothness properties of the regularized $K_\varepsilon(M)$. Also, using fully supported exploration policies guarantees that during exploration, the set of pairs is uniformly covered, which is helpful in the regret analysis.

(III) Adding a strongly convex regularizer to the objective function $\sum_{z \in \mathcal{Z}} \mu(z)\Delta^*(z)$ of (8): This makes the optimizer unique. This one is rather useful than necessary.

Uniform invariant measures and leveled confusing sets are defined as follows.

**Definition 10 (Uniform invariant measure).** For $\varepsilon > 0$, an $\varepsilon$-uniform invariant measure of a model $M$ is an element $\mu \in \text{Inv}(M)$ such that $\mu(s, a) \ge \varepsilon \sum_{a' \in \mathcal{A}(s)} \mu(s, a')$ for all $s \in \mathcal{S}$. The set of $\varepsilon$-uniform invariant measures is denoted $\text{Inv}(\varepsilon; M)$.

**Definition 11 (Leveled confusing set).** Fix $\mathcal{M}$ a space of Markov decision processes and fix $\varepsilon > 0$. The $\varepsilon$-leveled confusing set of a communicating model $M \in \mathcal{M}$ is

$$ \text{Cnf}(\varepsilon; M) \equiv \text{Cnf}_{\varepsilon}(M) := \left\{ M^{\dagger} \in \mathcal{M} : \begin{array}{l} M^{\dagger} \gg M, M^{\dagger} = M \text{ on } \mathcal{Z}_{\varepsilon}^{**}(M) \\ \text{and } \Pi^{*}(M^{\dagger}) \cap \Pi^{*}(M) = \emptyset \end{array} \right\}. $$

It can be shown that uniform invariant measures of communicating Markov decision processes are fully supported, see Appendix A.3. Also, note that only difference between the leveled confusing set $\text{Cnf}_\varepsilon(M)$ and the vanilla version $\text{Cnf}(M)$ is that elements of $\text{Cnf}_\varepsilon(M)$ are required to coincide with $M$ on $\mathcal{Z}_\varepsilon^{**}(M)$ rather than $\mathcal{Z}^{**}(M)$. As one can show that $\mathcal{Z}_\varepsilon^{**}(M)$ satisfies $\mathcal{Z}_\varepsilon^{**}(M) \supseteq \mathcal{Z}^{**}(M)$, we have $\text{Cnf}_\varepsilon(M) \subseteq \text{Cnf}(M)$ for all $\varepsilon \ge 0$. Moreover, by Proposition 3, for $\varepsilon < \Delta^g(M)$, we have $\mathcal{Z}_\varepsilon^{**}(M) = \mathcal{Z}^{**}(M)$ so that $\text{Cnf}_\varepsilon(M) = \text{Cnf}(M)$.

We have everything in hand to give a complete description of the regularized regret lower bound. The regularized version (Definition 12) uses a **regularization hyperparameter**
$\bar{\epsilon} \equiv (\epsilon_{\text{lvl}}, \epsilon_{\text{unif}}, \epsilon_{\text{conv}}) \in \mathbf{R}_+^3$ to tune the different regularization components (I–III). (I) The first $\epsilon_{\text{lvl}}$ is the **leveling regularizer** and tunes the leveling threshold used to estimate the confusing set; (II) The second $\epsilon_{\text{unif}}$ is the **uniformization regularizer** and tunes how uniform are the invariant measures that we are optimizing over; and (III) The third $\epsilon_{\text{conv}}$ is the **convexification regularizer** that makes the objective function $\epsilon_{\text{conv}}$-strongly convex.

**Definition 12 (Regularized regret lower bound).** Fix $\mathcal{M}$ a space of Markov decision processes and fix $\bar{\epsilon} \equiv (\epsilon_{\text{lvl}}, \epsilon_{\text{unif}}, \epsilon_{\text{conv}}) \in \mathbf{R}_+^3$ a regularization hyperparameter. The $\bar{\epsilon}$-regularized regret lower bound is the solution $K_{\bar{\epsilon}}(M) \in [0, \infty]$ of the optimization problem below:

$$ \inf \sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z) + \epsilon_{\text{conv}} \|\mu\|_2^2 \quad \text{s.t.} \quad \left\{ \begin{array}{l} \mu \in \text{Inv}(\epsilon_{\text{unif}}; M), \quad \text{and} \\ \inf_{M^\dagger \in \text{Cnf}(\epsilon_{\text{lvl}}; M)} \left\{ \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^\dagger(z)) \right\} \ge 1. \end{array} \right. $$

Observe that $K_{\bar{\epsilon}}(M)$ is the solution of a convex optimization problem, where the objective function is $\epsilon_{\text{conv}}$-strongly convex and the constraints spawn a closed convex cone of $\mathbf{R}_+^\mathcal{Z}$. Using these properties, we show in Appendices B.3.1 and B.3.2 that $K_{\bar{\epsilon}}(M) < \infty$ and that there exists an optimizer in $\text{Inv}(\epsilon_{\text{unif}}; M)$. When the convexification is strict with $\epsilon_{\text{conv}} > 0$, that optimizer is unique, called the $\bar{\epsilon}$-**optimal exploration measure** and denoted $\mu_{\bar{\epsilon}}^*$.

### 4.4 Properties of the regularized lower bound

In this paragraph, we overview the different properties of the regularized regret lower bound. In Proposition 4, we state that $K_{\bar{\epsilon}}(M)$ converges to $K(M)$ as $\bar{\epsilon} \to 0$, meaning that the regularized lower bound is a good approximation of the true lower bound when the regularizer is small enough. In Proposition 5, we state that the associated optimizer $\mu_{\bar{\epsilon}}^*$ converges to a special optimizer of $K(M)$ (in the formulation of (8)) as the components of the regularizer $\bar{\epsilon}$ vanish at the right speed; In particular, the uniformization regularizer must vanish faster than the convexification regularizer.

**Proposition 4 (Approximation of $K(M)$).** Let $\mathcal{M}$ be a space of Markov decision processes. For all $M \in \mathcal{M}$ that is communicating, we have

$$ K(M) \le K_{\bar{\epsilon}}(M) \le K(M) + O(\|\epsilon\|) \quad \text{as} \quad \|\bar{\epsilon}\| \to 0. $$

**Proposition 5 (Convergence of $\mu_{\bar{\epsilon}}^*$).** Let $\mathcal{M}$ be a space of Markov decision processes and let $M \in \mathcal{M}$ be a communicating model. Let $\mu^*(M) \in \text{Inv}(M)$ be the (unique) optimizer of $K(M)$ in the sense of (8) that further minimizes $\|\mu\|_2$ among optimizers. We have

$$ \|\mu_{\bar{\epsilon}}^*(M) - \mu^*(M)\|_2 \to 0 \quad \text{as} \quad \frac{\epsilon_{\text{unif}}}{\epsilon_{\text{conv}}} + \epsilon_{\text{conv}} + \epsilon_{\text{lvl}} \to 0. $$

More precise statements of Proposition 4 and Proposition 5, together with proofs, can be bound in Appendix B.3, see Proposition B.17 and Proposition B.16 respectively.

Regarding the continuity properties of $K_{\bar{\epsilon}}(M)$ with respect to $M$, we add further assumptions on the structure of the ambient space of Markov decision processes $\mathcal{M}$. Firstly, we assume that $\mathcal{M}$ is a space of models with Bernoulli rewards (Assumption 3). Doing so, the simple stated norm $\|-\|^*$ from Definition 9 is adequate and we do not run into topological
troubles—the result is probably easy to generalize to single parameter exponential families, but we have chosen to keep everything as simple as possible. Secondly, we assume that $\mathcal{M}$ is in product form $\mathcal{M} = \prod_{z \in \mathcal{Z}} (\mathcal{P}'_z \times \mathcal{R}'_z)$ (Assumption 4), where $\mathcal{P}'_z \subseteq \mathcal{P}(\mathcal{S})$ and $\mathcal{R}'_z = (0, 1)$. That is, $\mathcal{M}$ is a product and all rewards are (0, 1). Under these two assumptions, we show in Proposition 6 that $K_{\bar{\epsilon}}(M)$ and $\mu_{\bar{\epsilon}}^*(M)$ are both continuous relatively to the topology induced by $\|\cdot\|^*$.

**Assumption 3.** For all $M \in \mathcal{M}$, $M$ has Bernoulli rewards.

**Assumption 4.** The space $\mathcal{M}$ is of the form $\mathcal{M} = \prod_{z \in \mathcal{Z}} (\mathcal{P}'_z \times (0, 1))$ where $\mathcal{P}'_z \subseteq \mathcal{P}(\mathcal{S})$.

**Proposition 6** (Continuity of $K_{\bar{\epsilon}}(M)$ and $\mu_{\bar{\epsilon}}^*$). Let $\mathcal{M}$ be a space of Markov decision processes and let $M \in \mathcal{M}$ be a communicating model. Assume that rewards are Bernoulli (Assumption 3) and that $\mathcal{M}$ is in product form (Assumption 4). Let $\bar{\epsilon} = (\epsilon_{\text{lvl}}, \epsilon_{\text{unif}}, \epsilon_{\text{conv}}) \in (\mathbf{R}_+^*)^3$ be a positive regularization hyperparameter. If $\epsilon_{\text{conv}} < \Delta^g(M)$, then, in $\mathcal{M}$, we have

$$K_{\bar{\epsilon}}(M) = \lim_{\|M'-M\|^* \to 0} K_{\bar{\epsilon}}(M') \quad \text{and} \quad \mu_{\bar{\epsilon}}^*(M) = \lim_{\|M'-M\|^* \to 0} \mu_{\bar{\epsilon}}^*(M')$$

A more precise statement can be found in Appendix B.3, see Proposition B.18.

Combining Propositions 4 to 6, it means that given an approximation $\hat{M}$ of $M$ and a regularizer $\bar{\epsilon} \ll 1$ such that $\|\hat{M} - M\|^* \ll \|\bar{\epsilon}\|$, we have $K_{\bar{\epsilon}}(\hat{M}) \approx K_{\bar{\epsilon}}(M) \approx K(M)$ and $\mu_{\bar{\epsilon}}^*(\hat{M}) \approx \mu_{\bar{\epsilon}}^*(M) \approx \mu^*(M)$. Accordingly, we can estimate the lower bound $K(M)$ and a good exploration policy out of empirical data.

Now, we can provide a complete description of ECoE.

## 5 ECoE*, an algorithm with asymptotically optimal regret

For the clarity of the exposition, we focus on an instance of ECoE that ignores the computational weight of its subroutines. Ideally, ECoE eventually estimate the regret lower bound $K(M)$, an optimal exploration measure $\mu^*$ and check dynamically when information is lacking. All three problems are computationally difficult (NP-hard in some cases) and solving them requires a dedicated care that is too heavy to carry for a first regret analysis. That is why, for this “oracle-based” version of ECoE called ECOE*, we shall assume that we are able to compute the regret lower bound $K(-)$, optimal exploration measures $\mu^*$ and to run exploration tests (12) just by snapping fingers.

The pseudo-code of ECoE* is provided in Algorithm 2.

### 5.1 Overview of ECoE*

First, ECoE* requires a regularization hyperparameter $\bar{\epsilon} = (\epsilon_{\text{lvl}}, \epsilon_{\text{unif}}, \epsilon_{\text{conv}}, \epsilon_{\text{tst}}) : \mathbf{N} \to \mathbf{R}_+^4$ that is a slowly decreasing function. This hyperparameter is essential to the regularization of the lower bound $K(M)$, that is discontinuous in $M$ and that cannot be estimated under noise. In comparison to the regularization of $K(M)$ in Definition 12, note the presence of a fourth hyperparameter $\epsilon_{\text{tst}}$, called the **test hyperparameter**, that controls the power of exploration tests (see Section 3.1). The choice of $\bar{\epsilon}$ is discussed in Section 5.2.

Algorithm 2 works in phases $k = 1, 2, 3, \dots$ that are very short.

At the beginning of a phase, it first updates the regularization parameter to a floored regularization $\epsilon'$ described in Section 5.2 and (17). Then, it updates the maximum likelihood
**Algorithm 2 ECoE\*, an instantiation of ECoE (Algorithm 1)**

**Parameters:**

A family of regularization parameters functions $\epsilon_{\text{lvl}}$, $\epsilon_{\text{unif}}$, $\epsilon_{\text{conv}}$, $\epsilon_{\text{tst}}$;

1: Initialize $\mathcal{T}^-$, $\mathcal{T}^{\pm}$, $\mathcal{T}^{+}$, $\mathcal{T}_0^+$ and $\mathcal{T}^1$ to $\emptyset$;

2: Initialize $t \leftarrow 1$;

3: **for** $k = 1, 2, \dots$ **do**

4: Set $t_k \leftarrow t$;

5: Update floored hyperparameters $\bar{\epsilon}'(t)$, see (17);

6: Update maximum likelihood estimator $\hat{M}_t$ for $M$;

7: Update co-exploration structure $\mathcal{Z}_{\epsilon_{\text{lvl}'}(t)}^{**}(\hat{M}_t)$, split the structure into components $\mathfrak{Z}_t := (\mathcal{Z}_t^1, \dots, \mathcal{Z}_t^{c(t)})$, and let $i(t)$ be the component containing $S_t$ (current component);

8: Update exploitation policy $\pi_{t_k}^+$ as given by (14);

9: Update exploration measure $\mu_{t_k} \leftarrow \mu_{\bar{\epsilon}'(t)}^*(\hat{M}_t)$ by computing $K_{\bar{\epsilon}'(t)}(\hat{M}_t)$ using an oracle;

10: Update exploration policy by setting $\pi_{t_k}^-(a|s) \propto \mu_{t_k}(s, a)$;

11: Update skeleton $\mathcal{Z}_t^{\text{skel}} \leftarrow \{z \in \mathcal{Z} : N_t(z) \ge \log^2(t)\}$;

12: **if** $S_t$ is not recurrent under $\pi_t^+$ in $\hat{M}_t$ or GLR($H_t$) holds, see (16) **then**

13: Play $A_t \sim \pi_t^-(|-S_t)$; ▷ vanilla exploration

14: Increment $t \leftarrow t + 1$, add $t - 1$ in $\mathcal{T}^-$;

15: **else if** (ST) $(\min\{N_t(z) : z \in \mathcal{Z}_t^{i(t)}\})^{1/2} \ge \min\{N_t(z) : z \in \mathcal{Z}_{\epsilon_{\text{lvl}'}(t)}^{**}(\hat{M}_t)\}$ **then**

16: Play $A_t \sim \pi_t^-(|-S_t)$; ▷ co-exploration

17: Increment $t \leftarrow t + 1$, add $t - 1$ in $\mathcal{T}^-$ and in $\mathcal{T}^{\pm}$;

18: **else**

19: Add $t$ in $\mathcal{T}_0^+$; ▷ exploitation until regeneration

20: **repeat**

21: Play $A_t \sim \pi_t^+(|-S_t)$;

22: Increment $t \leftarrow t + 1$;

23: **if** $S_t \notin S(\mathcal{Z}_t^{i(t)})$ **then** add $t - 1$ in $\mathcal{T}^1$ and **break**; ▷ transition discovery

24: **else** add $t - 1$ in $\mathcal{T}^+$;

25: **until** $S_t = S_{t_k}$; ▷ regeneration

26: **end if**

27: **end for**

estimator for $M$, denoted $\hat{M}_t$, as described in Section 5.3 and (19), and computes the leveled optimal pairs $\mathcal{Z}_{\epsilon_{\text{lvl}'}(t)}^{**}(\hat{M}_t)$ using the leveling threshold of $\epsilon_{\text{lvl}'}(t)$ and deduces an exploitation policy $\pi_t^+$ and an exploration policy $\pi_t^-$. As motivated in Section 3.2, ECoE\* chooses its exploitation policy as the policy playing leveled optimal pairs uniformly at random, if any, and actions uniformly at random if no element of $\mathcal{Z}_{\epsilon_{\text{lvl}'}(t)}^{**}(\hat{M}_t)$ can be played right away, i.e.,

$$ \pi_t^+(|-s) := \begin{cases} \text{Unif}(\{a \in \mathcal{A}(s) : (s, a) \in \mathcal{Z}_{\epsilon_{\text{lvl}'}(t)}^{**}(\hat{M}_t)\}) & \text{if } s \in \mathcal{S}(\mathcal{Z}_{\epsilon_{\text{lvl}'}(t)}^{**}(\hat{M}_t)) \\ \text{Unif}(\mathcal{A}(s)) & \text{if } s \notin \mathcal{S}(\mathcal{Z}_{\epsilon_{\text{lvl}'}(t)}^{**}(\hat{M}_t)) \end{cases} \quad (14) $$
where we wrote $S(Z') := \{s \in S : \exists a \in A(s), (s, a) \in Z'\}$ for $Z' \subseteq Z$. The exploration policy of ECoE* is the policy induced by the measure achieving $K_{\bar{\epsilon}}(\hat{M}_t)$, i.e.,

$$ \pi_t^-(a|s) := \frac{\mu_{\bar{\epsilon}'}(s, a; \hat{M}_t)}{\sum_{a' \in A(s)} \mu_{\bar{\epsilon}'}(s, a'; \hat{M}_t)} \quad (15) $$

where $\mu_{\bar{\epsilon}'}(t)$ is the unique probability invariant measure of $\hat{M}_t$ achieving $K_{\bar{\epsilon}'}(\hat{M}_t)$. Then, the algorithm decides whether (1) it explores, i.e., plays $\pi_t^-$ once to gather information on presumed sub-optimal pairs; or (2) it coexplores, i.e., plays $\pi_t^-$ to reach a sub-visited components of nearly optimal pairs; or (3) it exploits, i.e., plays $\pi_t^+$ to score as much as possible. More precisely:

(0) **BY-DEFAULT EXPLORATION ($t \in T^-$)**: If the algorithm is not on a component of the set of leveled optimal pairs $Z_{\bar{\epsilon}|\text{lvl}'}^{**}(\hat{M}_t)$, it iterates $\pi_t^-$ and ends the phase. Otherwise, the algorithm moves to the exploration GLR test.

(1) **EXPLORATION ($t \in T^-$)**: Following the ideas in Section 3.3, the algorithm checks first if there is a lack of information on sub-optimal pairs by running a **generalized log-likelihood ratio test** (GLR) that is truncated to a **skeleton $Z_t^{\text{skel}}$**, that contains the pairs visited more than $\log^2(t)$ times. The GLR test for exploration is GLR($H_t$) given by

$$ \text{GLR}(H_t) : \exists M^\dagger \in \text{Cnf}(\hat{M}_t) \text{ s.t. } \left\{ \begin{array}{l} M^\dagger = \hat{M}_t \text{ on } Z_t^{\text{skel}} \cup Z_{\bar{\epsilon}|\text{lvl}'}^{**}(\hat{M}_t); \text{ and} \\ \sum_{z \in Z} N_t(z) \text{KL}(\hat{M}_t(z) || M^\dagger(z)) \le (1 + \epsilon'_{\text{tst}}(t)) \log(t) \end{array} \right. \quad (16) $$

where $\epsilon_{\text{tst}}: \mathbf{N} \to \mathbf{R}_+$ is a well-chosen vanishing function. If (16) is true, the algorithm iterates $\pi_t^-$ once and the phase ends. Otherwise, the algorithm deals with co-exploration.

(2) **COEXPLORATION ($t \in T^\pm \cap T^-$)**: As motivated in Section 3.2, to avoid missing information on nearly optimal pairs, the algorithms synchronizes the visit counts on all the communicating components of leveled optimal pairs $Z_{\bar{\epsilon}|\text{lvl}'}^{**}(\hat{M}_t)$. Following the square trick (ST), if one component is visited less than the square root of the current component, the algorithm decides that this sub-visited component should be reached and attempts to do so by exploring: It iterates $\pi_t^-$ once and the phase ends. The idea is to explore by the meantime and to reconsider the exploration-exploitation trade-off once another component of $Z_{\bar{\epsilon}|\text{lvl}'}^{**}(\hat{M}_t)$ has been reached. Otherwise, the amount of information on components of $Z_{\bar{\epsilon}|\text{lvl}'}^{**}(\hat{M}_t)$ is considered to be balanced enough, and the algorithm moves to exploitation.

(3) **EXPLOITATION ($t \in T^+$)**: The algorithm iterates $\pi_t^+$ until regeneration.

(!) **PANIC ($t \in T^!$)**: When the algorithm iterates the policy $\pi_t^+$ until regeneration, the regeneration may never come if the algorithm is wrong about the support of transition kernels. In that case, at some point, the algorithm will observe a transition $(S_t, A_t, S_{t+1})$ that it has never seen before, with $S_{t+1}$ outside of the current component of estimated optimal pairs. We call these time-instants **panic times**. The algorithm deals with them by aborting the current phase right away.

## 5.2 The regularization hyperparameter $\bar{\epsilon}$

The regularization hyperparameter $\bar{\epsilon} \equiv (\epsilon_{\text{lvl}}, \epsilon_{\text{unif}}, \epsilon_{\text{conv}}, \epsilon_{\text{tst}}): \mathbf{N} \to (\mathbf{R}_+)^4$ regularizes the estimation of optimal pairs, the computation of the exploration policy and the exploration
GLR tests. Every component of $\bar{\epsilon}$ has a specific purpose and although they are all maps $N \to R_+$, they do not take the same input.

* $\epsilon_{\text{lvl}}$ is the **leveling** parameter: It determines the threshold beyond which a sub-optimal state-action pair of $\hat{M}_t$ is considered optimal because it is near-optimal enough; It is a function of the global time $t$;

* $\epsilon_{\text{unif}}$ is the **uniformization** parameter: It makes sure that exploration is slightly uniform and is key bounding the probability that ECoE* blunders the estimation of the hidden model, or that ECoE* purposely avoids regions of the environment that should be explored, but that aren't because the empirical data is completely off; It is a function of the exploration time $|T^-|$;

* $\epsilon_{\text{conv}}$ is the **convexification** parameter: It comes from the way the regret lower bound is being regularized (Definition 12) and makes sure that the estimated exploration measure converges; It is a function of the exploration time $|T^-|$;

* $\epsilon_{\text{tst}}$ is the **test power** parameter: It controls the power of the exploration test that regulates second order errors in exploration tests. It is a function of the global time $t$;

Note that not all regularizers take the same input, as some are functions of the global time $t$ in Algorithm 2 and others are functions of the number of exploration phases $|T^-|$. Also, the regularization is **floored** into $\bar{\epsilon}'$ during play to stabilize the algorithm:

$$ \begin{aligned} \epsilon_{\text{lvl}}'(t) &:= \epsilon_{\text{lvl}}(t) & \epsilon_{\text{tst}}'(t) &:= \epsilon_{\text{tst}}(t) \\ \epsilon'_{\text{unif}}(t) &:= \epsilon_{\text{unif}}(2^{\lfloor \log_2 |T^-| \rfloor}), & \epsilon'_{\text{conv}}(t) &:= \epsilon_{\text{conv}}(2^{\lfloor \log_2 |T^-| \rfloor}). \end{aligned} \quad (17) $$

Moreover, for ECoE* to be asymptotically optimal, the regularization hyperparameter $\bar{\epsilon}$ must be carefully be tuned. We move the technical discussion on the set of assumptions (Assumption 6) that $\bar{\epsilon}$ must satisfy to the appendix. For now, we will assume that the regularization hyperparameters are chosen as follows:

$$ \begin{aligned} \epsilon_{\text{lvl}}(t) &:= \frac{1}{\max(1, \log \log(t))}, & \epsilon_{\text{tst}}(t) &:= \frac{1}{\max(1, \log \log(t))}, \\ \epsilon_{\text{unif}}(m) &:= \frac{1}{\max(1, \log \log(m))}, & \epsilon_{\text{conv}}(m) &:= \frac{1}{\max(1, \log(m))}. \end{aligned} \quad (18) $$

We can finally provide the regret guarantees of ECoE*.

## 5.3 Maximum likelihood estimator of $M$ and structure of the ambient space

The maximum likelihood estimator of $M$ under history $H_t$ is the unique model $\hat{M}_t \equiv (\mathcal{Z}, \hat{p}_t, \hat{v}_t)$ that maximizing the likelihood of $H_t$. Formally,

$$ \hat{M}_t \in \underset{M' \in \text{cl}(M)}{\operatorname{argmax}} \prod_{i=1}^{t-1} \hat{p}_t(S_{i+1} | Z_i) \hat{p}_t(R_i | Z_i). \quad (19) $$

It is preferable for the optimizer in (19) to be unique and easy to compute. Also, the regret analysis of ECoE* requires $\hat{M}_t$ to be well-behaved relatively to $M$, with $\text{supp}(\hat{p}_t) \subseteq \text{supp}(p)$ for instance. For that purpose, we will strengthen our set of assumptions (Assumption 4) on the structure of the ambient space of models $M$, see Assumption 5 below.
**Assumption 5.** The space $\mathcal{M}$ is of the form $\mathcal{M} = \prod_{z \in \mathcal{Z}} (\mathcal{P}_z \times (0, 1))$ where $\mathcal{P}_z = \mathcal{P}(S)$ or $\mathcal{P}_z = \{p(z)\}$ for some $p(z) \in \mathcal{P}(S)$. We write $\text{cl}(\mathcal{M}) := \prod_{z \in \mathcal{Z}} (\mathcal{P}_z \times [0, 1])$.

Under Assumption 5 and for $M \in \mathcal{M}$, the maximum likelihood estimator $\hat{M}_t$ is the model with reward function and transition kernel given by

$$ \hat{r}_t(z) = \frac{\sum_{i=1}^{t-1} R_i \mathbf{1}(Z_i = z)}{N_t(z)} \quad \text{and} \quad \hat{p}_t(s|z) = \begin{cases} \frac{\sum_{i=1}^{t-1} \mathbf{1}(Z_i = z, S_{i+1} = s)}{N_{t-1}(z)} & \text{if } \mathcal{P}_z = \mathcal{P}(S); \\ p(z) & \text{if } \mathcal{P}_z = \{p(z)\}. \end{cases} $$

That is, $\hat{r}_t$ is the empirical mean of the rewards observed when playing $z$ and $\hat{p}_t(s|z)$ is the number of transitions to $s$ observed when playing $z$. Note that $\hat{M}_t(z) \ll M(z)$ for all $t \ge 1$ a.s. as soon as $N_t(z) \ge 1$.

## 5.4 The regret guarantees of ECoE*

ECoE* tuned with $\bar{\epsilon}$ chosen as in Equation (18) is asymptotically optimal.

**Theorem 7 (Asymptotic optimality).** Assume that the regularization hyperparameter $\bar{\epsilon}$ is chosen as in (18), and that the ambient space $\mathcal{M}$ has Bernoulli rewards (Assumption 3) and strong product structure (Assumption 5). For all $M \in \mathcal{M}$ communicating and all initial state $s_0 \in S$, ECoE* satisfies

$$ \text{Reg}(T; M, \text{ECoE}^*, s_0) \le K(M) \log(T) + o(\log(T)) $$

as $T \to \infty$. Accordingly, ECoE* is asymptotically optimal.

The proof of Theorem 1 is difficult and is deferred to Appendix C. We bound the expected regret $\text{Reg}(T; M, \Lambda, s_0)$ by upper-bounding the pseudo regret $\sum_{t=1}^T \Delta^*(Z_t)$ in expectation. As $\Delta^*(Z_t) > 0$ only for $Z_t \notin \mathcal{Z}^*(M)$, this is about upper-bounding the number of visits $N_T(z)$ in expectation for sub-optimal pairs $z \notin \mathcal{Z}^*(M)$. We show that there exists a special optimizer $\mu^* \in \text{Inv}(M)$ of (8) such that, for all sub-optimal pairs $z \notin \mathcal{Z}^*(M)$, we have

$$ \mathbf{E}[N_T(z)] \le \mu^*(z) \log(T) + o(\log(T)) $$

when $T \to \infty$. Because $\mu^*$ is an optimizer of the optimization problem (8) associated to $K(M)$, it immediately follows that ECoE* is asymptotically optimal.

Therefore, the regret lower bound of Theorem 1 is tight.

## 6 Open directions and future research

In this paper, we have shown that under reasonable assumptions on the space of ambient Markov decision processes $\mathcal{M}$, then

$$ \min_{\Lambda \text{ consistent}} \sup_{M \in \mathcal{M} \text{ communicating}} \limsup_{T \to \infty} \left\{ \frac{\text{Reg}(T; M, \Lambda)}{\log(T)} - K(M) \right\} = 0. $$

In other words, we have provided a learning algorithm $\Lambda$ with $\text{Reg}(T; M, \Lambda) \le K(M) \log(T) + o(\log(T))$ for all communicating model $M \in \mathcal{M}$ simultaneously, while every reasonable
(i.e., consistent) learning algorithm $\Lambda'$ satisfies $\text{Reg}(T; M, \Lambda') \ge K(M) \log(T) + o(\log(T))$. Accordingly, our algorithm is universally asymptotically optimal with $\text{Reg}(T; M, \Lambda) = K(M) \log(T) + o(\log(T))$ and the regret lower bound of Boone and Maillard (2025) is tight. From there, many directions open up.

**Tractable algorithms.** Our algorithm ECoE* is not easy to implement, because the computation of $K(M)$ is difficult. In fact, even the exploration tests (16) are computationally difficult in general, see Boone and Maillard (2025). Nonetheless, we believe that this computational difficulties can be avoided and that an asymptotically optimal version of ECoE that runs in reasonable time is doable—if the size of the pair space stays small, at least.

**More general settings.** To simplify the exposition, we have assumed that rewards are Bernoulli (Assumption 3). This assumption can be dropped for another. Our proof is likely to hold for reward distributions among a single parameter exponential family, but this is yet to prove. More interestingly, there is the question of dropping the communicating assumption (Assumption 2) and of dropping the a priori knowledge on the structure of the finite pair space $\mathcal{Z}$ (Assumption 1). Indeed, not only ECoE is only designed to work for communicating Markov decision processes, but some a priori knowledge on $\mathcal{Z}$ is hard-coded in $M$, because every element of $M$ has pair space $\mathcal{Z}$. This raises the following question:

*What can we say about the regret lower bound when $M$ is the space of all Markov decision processes with Bernoulli rewards and arbitrary finite state space?*

We believe that the above is essentially the same problem as dealing with weakly communicating Markov decision processes with fixed finite pair space.
All this is left for future work.

**Acknowledgements**

This work has been supported by the PEPR FOUNDRY (ANR-23-PEIA-0003) and the AI Interdisciplinary Institute ANITI (ANR-23-IACL-0002).
# Appendix A. Additional notions on Markov decision processes

In this appendix, we provide various complementary results on Markov decision processes. In Appendix A.1, we provide a refresher on Bellman optimality that comes back for the proof of Proposition 3. In Appendix A.2, we define the worst diameter and the gain gap. The last consequent Appendix A.3 is dedicated to the analysis of invariant measures (Definition 4) of Markov decision processes.

**Definition A.1 (Definite minimum of a model).** Let $M \equiv (\mathcal{Z}, p, \nu)$ be a Markov decision process with Bernoulli rewards. Its definite minimum is $\text{dmin}(M) := \min\{\text{dmin}(p), \text{dmin}(\nu)\}$

## A.1 Refresher on gain, Bellman and bias optimalities

At several places in this paper, we will use the notion of Bellman optimality. Bellman optimality sits in-between gain and bias optimalities. We recall its definition below.

**Definition A.2 (Bellman optimal).** Let $M \equiv (\mathcal{Z}, p, r)$ be a communicating Markov decision process. A policy is said **Bellman optimal**, written $\pi \in \Pi_{\text{Bell}}^*(M)$, if $\text{sp}(g^\pi(M)) = 0$ and $\pi$ satisfies the first order Bellman equations:

$$ \forall s \in \mathcal{S}, \quad g^\pi(s; M) + b^\pi(s; M) = \max_{a \in \mathcal{A}(s)} \{r(s, a) + p(s, a)b^\pi(M)\}. \quad (A.1) $$

In other words, Bellman optimal policies are fixpoints of the Policy Iteration algorithm, see (Puterman, 2014, §8.6). It is linked to gain and bias optimalities as follows.

**Proposition A.1.** In the space of communicating Markov decision processes, every Bellman optimal policy is gain optimal, and every bias optimal policy is Bellman optimal; The converse statements are wrong in general.

A proof of Proposition A.1 can be found in (Boone, 2024, Theorem I.3).

## A.2 Worst diameter and gain-gap of a communicating Markov decision process

At several places in this work, we rely on the **worst diameter** and the **gain-gap** of a communicating Markov decision process. They are defined in this paragraph for further reference. The worst diameter $D^*(M)$ is involved in gain deviations inequalities (see Appendix D) that are uniform over the space of policies. The gain-gap is related to how small the leveling threshold must be so that the leveling transform $[M]_\epsilon$ is well-behaved, see Appendix B and Proposition 3 more specifically.

**Definition A.3 (Worst diameter).** The **worst diameter** $D^*(M) \in \mathbb{R}_+$ of a communicating Markov decision process $M$ is the largest policy diameter (Definition D.1) of its deterministic stationary policies, visually,

$$ D^*(M) := \max_{\pi \in \Pi} D(\pi; M). $$

**Definition A.4 (Gain gap).** The **gain-gap** $\Delta^g(M) \in \mathbb{R}_+$ of a communicating Markov decision process $M$ is the difference between the optimal gain and the gain of the best sub-optimal policy, visually,

$$ \Delta^g(M) := \min_{\pi \notin \Pi^*(M)} \|g^*(M) - g^\pi(M)\|_{\infty}. \quad (A.2) $$
### A.3 Invariant measures of Markov decision processes

In this section, we provide a collection of results on the invariant measures of a Markov decision process. Recall that $\mu$ is an **invariant measure** of $M \equiv (\mathcal{Z}, p, \nu)$ if

$$ \forall s \in \mathcal{S}, \quad \sum_{a \in \mathcal{A}(s)} \mu(s, a) = \sum_{z \in \mathcal{Z}} p(s|z)\mu(z). $$

We write $\mu \in \text{Inv}(M)$. The set of **probability invariant measures** is written

$$ \mathcal{I}(M) := \text{Inv}(M) \cap \mathcal{P}(\mathcal{Z}). \qquad (A.3) $$

An invariant measure $\mu \in \text{Inv}(M)$ is said **$\varepsilon$-uniform** (Definition 10) if it is the (unique) invariant measure of some $\varepsilon$-uniform policy, i.e., if $\mu(s, a) \ge \varepsilon \sum_{a' \in \mathcal{A}(s)} \mu(s, a')$ for all $(s, a) \in \mathcal{Z}$. We write $\mu \in \text{Inv}(\varepsilon; M)$ their space and $\mathcal{I}(\varepsilon; M) := \text{Inv}(\varepsilon; M) \cap \mathcal{P}(\mathcal{Z})$.

**Outline.** In Appendix A.3.1, we draw the link between invariant measures and the asymptotic behavior of learning algorithms by showing that the normalized visit vector $\frac{1}{t}N_t$ converges to the space of invariant measures as $t \to \infty$. Using this property, we show that there exists a stationary randomized policy that covers all pairs uniformly fast with respect to the diameter in Appendix A.3.2. In Appendix A.3.3, we link fully supported randomized policies to fully supported probability invariant measures by describing the natural one-to-one mapping between $\Pi^{\text{SFR}}$ and $\cup_{\varepsilon>0} \mathcal{I}(\varepsilon; M)$. In Appendix A.3.4, we show that elements of $\text{Inv}(M) \equiv \text{Inv}(0; M)$ can be approximated with arbitrary precision by elements of $\text{Inv}(\varepsilon; M)$ as $\varepsilon \to 0$. In Appendix A.3.5, we provide properties on the minimum and the diameter of $\varepsilon$-uniform invariant measures, then deduce a bound of the variations of $\mathcal{I}(M)$ when $M$ vary. In the last Appendix A.3.6, we show that every element of $\text{Inv}(M)$ can be written as a convex combination of invariant measures of unichain policies and provide several useful consequences of this result.

#### A.3.1 LINKS BETWEEN INVARIANT MEASURES AND LEARNING ALGORITHMS

We begin this appendix by showing that the average visit counts $\frac{1}{t}N_t$ converges to the space of invariant measures almost surely, whatever the learning algorithm is.

**Proposition A.2** (Asymptotic flow property of $N_t$). Let $M \equiv (\mathcal{Z}, p, \nu)$ be a communicating Markov decision process and let $\Lambda$ be a learning algorithm. Then $\frac{1}{t}N_t \to \text{Inv}(M)$ a.s. when $t \to \infty$, i.e., every limit point of $(\frac{1}{t}N_t)_{t \ge 1}$ is an invariant measure with probability one.

**Proof** This follows from a direct computation. Denote $\hat{\mu}_t := \frac{1}{t}N_t$ and let $\mu^*$ be a limit point of $\hat{\mu}_t$ when $t \to \infty$. There exists a sequence $t_n \to \infty$ such that $\lim_{n \to \infty} \hat{\mu}_{t_n} = \mu^*$. Let $s \in \mathcal{S}$. We check that $\sum_{a \in \mathcal{A}(s)} \mu^*(s, a) = \sum_{z \in \mathcal{Z}} \mu^*(z)p(s|z)$ as follows:

$$ \sum_{a \in \mathcal{A}(s)} \mu^*(s, a) \stackrel{(\dagger)}{=} \frac{1}{t_n} \left( \sum_{a \in \mathcal{A}(s)} N_{t_n}(s, a) + o(t_n) \right) \\ \stackrel{(\ddagger)}{=} \frac{1}{t_n} \left( \sum_{z \in \mathcal{Z}} N_{t_n}(s|z) + O(1) + o(t_n) \right) $$
$$
\begin{align*}
\stackrel{(\$)}{=} \frac{1}{t_n} \left( \sum_{z \in \mathcal{Z}} (\hat{p}_{t_n}(s|z) - p(s|z)) N_{t_n}(z) + \sum_{z \in \mathcal{Z}} p(s|z) N_{t_n}(z) + o(t_n) \right) \\
\stackrel{(\$)}{=} \frac{1}{t_n} \left( \sum_{z \in \mathcal{Z}} p(s|z) N_{t_n}(z) + o(t_n) \right) \\
\stackrel{(\#)}{=} \sum_{z \in \mathcal{Z}} \mu^*(z) p(s|z)
\end{align*}
$$

where (†) holds by assumption; (‡) uses the notation $N_t(s|z) := \sum_{i=1}^{t-1} \mathbf{1}(Z_i = z, S_{i+1} = s)$ and uses the quasi-flow property of $N_{t_n}$, which is $|\sum_a N_{t_n}(s, a) - \sum_z N_{t_n}(s|z)| \le 2$; (§) uses that the empirical transition kernel satisfies $\hat{N}_{t_n}(s|z)N_{t_n}(z) = N_{t_n}(s|z)$ by definition; (§) follows from the strong law of large numbers; and (#) holds by definition of $(t_n)$. ■

**Corollary A.3.** Let $M \equiv (\mathcal{Z}, p, \nu)$ be a communicating Markov decision process. Let $\Lambda$ a learning algorithm such that $\frac{1}{t}N_t(z) \to \mu(z)$ a.s., for all $z \in \mathcal{Z}$. Then $\mu \in \text{Inv}(M)$.

### A.3.2 A CONVENIENT FAST COVERING POLICY

In this paragraph, we show that there exists a policy $\pi$ that covers all pairs uniformly fast, with $\min(\mu^\pi) \ge |\mathcal{Z}|^{-1}D(M)^{-1}$. This policy is obtained as the limit of average behavior of a non-stationary policy that navigates as fast as possible between pairs in a round-robin fashion, see Lemma A.4 below. The existence of that limit average behavior is guaranteed by the flow properties of the visit vector shown upstream, see Corollary A.3.

This covering policy plays an important part in the approximation of invariant measures by $\varepsilon$-uniform invariant measures when $\varepsilon \to 0$, see Theorem A.6. It also provides a simple bound on $K(M)$ in terms of $D(M)$, see Theorem B.12.

**Lemma A.4 (Fast covering policy).** Let $\mathcal{M} \equiv (\mathcal{Z}, p, \nu)$ a communicating Markov decision process. There exists a stationary fully-randomized policy $\pi \in \Pi^{\text{SR}}$ such that its unique probability invariant measure $\mu^\pi$ (Proposition A.5) satisfies

$$ \min(\mu^\pi) \ge \frac{1}{|\mathcal{Z}|D(M)}. $$

**Proof** Enumerate $\mathcal{Z}$ as $\mathcal{Z} = \{z_0, \dots, z_{m-1}\}$. Given $z_i \in \mathcal{Z}$, pick $\pi_i \in \Pi$ a policy achieving

$$ \min_{\pi \in \Pi} \max_{s \in \mathcal{S}} \mathbf{E}_s^{M, \pi} [\inf\{t \ge 1 : Z_t = z_i\}]. $$

By definition, $\mathbf{E}_s^{M, \pi_i}[\inf\{t \ge 1 : Z_t = z_i\}] \le D(M)$ for $i = 0, \dots, m-1$. Consider the non-stationary policy $\Lambda$ given by the following pseudo-code:

1. Set $t \leftarrow 1$;

2. **for** $n = 0, 1, 2, \dots$ **do**

3. Set $t_n \leftarrow t$;

4. Let $i \leftarrow n \bmod m$ and $\pi_n \leftarrow \pi_i$;

5. Iterate $\pi_i$ until $Z_t = z_i$;

6. **end for**
Assume throughout that we iterate $\Lambda$ on $M$.

First, we argue that $\frac{1}{t}N_t(z)$ converges almost-surely as $t \to \infty$ for all $z \in \mathcal{Z}$.

Fix $z \in \mathcal{Z}$. The idea is that, by design of $\Lambda$, the random states $S_{t_{km+i}}$ and $S_{t_{k'm+i}}$ are identically distributed for $k, k' \ge 1$ and $i \in \{0, \dots, m-1\}$. Denote $\mu_i$ their common distribution. Then, for all $k \ge 1$ and regardless of $s_0 \in \mathcal{S}$, we have

$$ \mathbf{E}_{s_0}^{M,\Lambda}[t_{km+i+1} - t_{km+i}] = \mathbf{E}_{\mu_i}^{M,\pi_i}[\inf\{t \ge 1 : Z_t = z_i\}] =: T_i \in \mathbf{R}. $$

Denoting $T := \sum_{i=0}^{m-1} T_i$, we deduce from the Strong Law that $t_n \sim \frac{nT}{m}$ as $n \to \infty$. Let

$$ \alpha_i(z) := \mathbf{E}^{M,\Lambda} \left[ \sum_{t=t_{km+i}}^{t_{km+1+i}-1} \mathbf{1}(Z_t = z) \right] $$

the expected number of times the pair $z$ is played when $\Lambda$ iterates $\pi_i$ over the episode $n = km + i$ for $k \ge 1$. Denothing $\alpha(z) := \sum_{i=0}^{m-1} \alpha_i(z)$, we deduce from the Strong Law that $N_{t_n}(z) \sim \frac{n\alpha(z)}{m}$ as $n \to \infty$. All together, we obtain

$$ N_t(z) \sim \frac{tm}{T} \cdot \frac{\alpha(\alpha)}{m} = \frac{\alpha(z)t}{T} \quad \text{a.s.} $$

as $t \to \infty$. Hence $\frac{1}{t}N_t(z) \sim \frac{\alpha(z)}{T} =: \mu(z)$.

Second, we argue that (I) $\mu(z) \ge |\mathcal{Z}|^{-1}D(M)^{-1}$ and that (II) $\mu \in \text{Inv}(M) \cap \mathcal{P}(\mathcal{Z})$. The assertion (I) is immediate from the observation that $\alpha_i(z_i) \ge 1$ and that $T_i \le D(M)$. The assertion (II) is a consequence of the flow property of the visit vector $N_t$, see Corollary A.3.

Conclude using that the randomized policy induced by $\mu$, which is given by $\pi^\mu(a|s) := \mu(s, a)(\sum_{a' \in \mathcal{A}(s)} \mu(s, a'))^{-1}$, is fully randomized (because $\mu$ is fully supported) and has unique probability invariant measure $\mu$ (Proposition A.5). $\blacksquare$

### A.3.3 LINKS BETWEEN FULLY SUPPORTED POLICIES AND FULLY SUPPORTED MEASURES

In this paragraph, we show that fully supported invariant measures can be thought as fully supported policies, because $\cup_{\varepsilon>0} \mathcal{I}(\varepsilon; M) \cong \Pi^{\text{SFR}}$. Indeed, in Proposition A.5 below, we state that from a fully randomized probability invariant measure $\mu$, we can construct a policy $\pi^\mu$ and that by iterating that policy, expected visit rates converge to $T\mu(z) + o(T)$. This further encourages the computation of $K(M)$ via (9) in the first place, because a near optimal solution $\pi \in \Pi^{\text{SFR}}$ provides a policy that, if iterated, makes visit rates converge to the optimal rates in the sense of (8), hence $\pi$ gathers information near optimally.

For later convenience, we provide a notation for the set of invariant measures of a policy.

**Definition A.5 (Invariant measures of a policy).** Let $M$ a Markov decision process. The set of invariant measures of $\pi \in \Pi$ in $M$, denoted $\text{Inv}(\pi; M)$, is the collection of $\mu \in \text{Inv}(M)$ such that $\mu(s, a) = \pi(a|s) \sum_{a' \in \mathcal{A}(s)} \mu(s, a')$ for all $(s, a) \in \mathcal{Z}$.

It is to be noted that $\text{Inv}(\pi; M)$ is isomorphic to $\text{Inv}(M_\pi)$ where $M_\pi = (\mathcal{S}, p_\pi, r_\pi)$ is the single-action Markov decision process (hence is a Markov reward process) with kernel $p_\pi(s) := \sum_{a \in \mathcal{A}(s)} \pi(a|s)p(s, a)$ and reward function $r_\pi(s) := \sum_{a \in \mathcal{A}(s)} \pi(a|s)r(s, a)$, where the isomorphism maps $\mu \in \text{Inv}(\pi; M)$ to $\mu' \in \mathbf{R}^S$ given by $\mu'(s) := \mu(s, \pi(s))$.
**Proposition A.5** (Randomized policies and invariant measures). Assume that $M$ is a communicating Markov chain. There is a one-to-one correspondence between probability invariant measures of full support and fully supported randomized policies $\Pi^{\text{SFR}}$, with

(1) A policy $\pi \in \Pi^{\text{SFR}}$ is associated to a unique probability invariant measure $\mu^{\pi}$, given by $\mu^{\pi}(z) := \lim_{\pi \in \Pi^{\text{SFR}}} \mathbf{E}_{s_0}^{M,\pi}[\frac{1}{T} \sum_{t=1}^{T} \mathbf{1}(Z_t = z)]$, regardless of the initial state $s_0 \in S$; In other words, $\text{Inv}(\pi; M) = \mathbf{R}_+ \mu^{\pi}$;

(2) A fully supported invariant measure $\mu$ is associated to a unique fully randomized policy $\pi^{\mu}$, given by $\pi^{\mu}(a|s) := \mu(s, a)(\sum_{a' \in A(s)} \mu(s, a'))^{-1}$;

(3) We have $\pi^{\mu^{\pi}} = \pi$ for all $\pi \in \Pi^{\text{SFR}}$.

The correspondence described in Proposition A.5 cannot be generalized easily to non-fully supported invariant measures. If every probability invariant measure is a probability invariant measure of some policy, it is not the unique one when that policy is multi-chain; And as matter of fact, the iterates of a multi-chain policy $\pi$ converge to a specific invariant measure of $\pi$ that depend on the initial state. When policies and invariant measures are of full support, we don't need to take such considerations into account.

**Proof of Proposition A.5** Assertion (1) is a result about Markov chains. If $\pi$ is fully randomized and $M$ is communicating, then it is easy to see that the Markov chain that $\pi$ induces on $\mathcal{Z}$ is irreducible, so that it has a unique probability invariant measure from classical results, see (Levin and Peres, 2017, Corollary 1.17). The fact that this measure is found as the asymptotic presence probability is also standard.

Assertion (2) is immediate, because $\pi^{\mu}$ satisfies $\pi^{\mu}(a|s) \ge \varepsilon$ by definition of $\text{Inv}(\varepsilon; M)$. Then, it is easy to check that $\mu$ is an invariant measure of $\pi^{\mu}$; It is the unique one, because the Markov chain induced by $\pi$ on $\mathcal{Z}$ is irreducible since $\pi^{\mu}$ is fully supported and $M$ is communicating.

For Assertion (3), we have $\mu^{\pi}(s, a) \propto \pi(a|s)$ so $\pi^{\mu^{\pi}}(a|s) = \pi(a|s)$ is immediate. ■

### A.3.4 APPROXIMATION OF INVARIANT MEASURES WITH UNIFORM INVARIANT MEASURES

In this paragraph, we show that uniform invariant measures can approximate invariant measures with arbitrary precision. In Theorem A.6 below, we show that provided that the required uniformization $\varepsilon$ is small enough, an invariant measure can be made $\varepsilon$-uniform by blending it with the invariant measure of the fast covering policy of Lemma A.4.

**Theorem A.6** (Approximation of invariant measures). Let $\mu \in \mathcal{I}(M)$ be a probability invariant measure. For all $\varepsilon < |\mathcal{Z}|^{-1}D(M)^{-1}$, there exists $\mu_{\varepsilon} \in \mathcal{I}(\varepsilon; M)$ such that

$$ \|\mu_{\varepsilon} - \mu\|_{\infty} \le |\mathcal{Z}|D(M)\varepsilon. $$

**Proof** Fix $\mu \in \mathcal{I}(M)$ a probability invariant measure. Let $\mu_c$ be the (unique) probability invariant measure of the fast covering policy given by Lemma A.4, satisfying $\min(\mu_c) \ge |\mathcal{Z}|^{-1}D(M)^{-1}$. As $\mathcal{I}(M)$ is obtained as the intersection of finitely many hyperplanes, it is convex. In particular, for every $\lambda \in [0, 1]$, $(1-\lambda)\mu + \lambda\mu_c \in \mathcal{I}(M)$ and $(1-\lambda)\mu + \lambda\mu_c \in \mathbf{R}_+^2$. It follows that

$$ \min((1 - \lambda)\mu + \lambda\mu_c) \ge \lambda \min(\mu_c). $$
Let $\lambda_{\varepsilon} := \min(\mu_c)^{-1}\varepsilon$. Since $\varepsilon < \min(\mu_c)$, $\mu_{\varepsilon} := (1 - \lambda_{\varepsilon})\mu + \lambda_{\varepsilon}\mu_c$ is a probability invariant measure. Moreover, we see that for all $(s, a) \in \mu_{\varepsilon}$, we have

$$ \mu_{\varepsilon}(s, a) \geq \lambda_{\varepsilon} \min(\mu_c) \geq \varepsilon \geq \varepsilon \sum_{a' \in \mathcal{A}(s)} \mu_{\varepsilon}(s, a') $$

so that $\mu_{\varepsilon}$ is $\varepsilon$-uniform. Moreover, we have $\|\mu_{\varepsilon} - \mu\|_{\infty} = \lambda_{\varepsilon}\|\mu - \mu_c\|_{\infty} \leq \lambda_{\varepsilon}$. ■

### A.3.5 PROPERTIES OF POLICIES INDUCED BY UNIFORM INVARIANT MEASURES

In this paragraph, we provide a few properties on uniform probability invariant measures. In Lemma A.7, we provide a lower bound of the minimums of $\varepsilon$-uniform invariant measures as well as the diameters of their induced policies. In Lemma A.8, we show that the projection of $\mu \in \mathcal{I}(\varepsilon; M)$ onto $\mathcal{I}(\varepsilon; M')$ is close to $\mu$, leading to a bound on the Hausdorff distance between $\mathcal{I}(\varepsilon; M)$ and $\mathcal{I}(\varepsilon; M')$ in Corollary A.9. In turn, Corollary A.9 plays an important part in proving that $K_{\varepsilon}(M') \to K_{\varepsilon}(M)$ when $\|M' - M\|^* \to 0$, see Proposition B.18.

**Lemma A.7.** Let $M \in \mathcal{M}$ be a communicating Markov decision process and $\varepsilon > 0$. For all $\varepsilon$-uniform invariant measure $\mu \in \text{Inv}(\varepsilon; M)$, the following holds:

(1) We have $\min(\mu) \geq \varepsilon^{|S|-1}\min(p)^{|S|-1}\|\mu\|_1$;

(2) Its induced policy has small diameter with $D(\pi_{\mu}; M) \leq \varepsilon^{1-|S|}\min(p)^{1-|S|}(|S| - 1)$.

**Proof** Up to normalizing $\mu$, we assume that $\|\mu\|_1 = 1$.

We start with assertion (1). Pick $z \in \mathcal{Z}$ and let $s \in S$ maximizing $\sum_{a \in \mathcal{A}(s)} \mu(s, a)$. In particular, we have $\sum_{a \in \mathcal{A}(s)} \mu(s, a) \geq |S|^{-1}$. Because $M$ is communicating, there exists a path from $s$ to $z$ of length at most $|S|$, i.e., $(s_1, a_1, \dots, s_n, a_n)$ such that (I) $s_1 = s$, (II) $(s_n, a_n) = z$, (III) $p(s_{i+1}|s_i, a_i) > 0$ for $i = 1, \dots, n-1$, and (IV) $n \leq |S|$. Then,

$$ \begin{aligned} \mu(z) &\geq \left( \prod_{i=1}^{n-1} \frac{p(s_{i+1}|s_i, a_i)\mu(s_i, a_i)}{\sum_{a'_i \in \mathcal{A}(s_i)} \mu(s_i, a'_i)} \right) \sum_{a' \in \mathcal{A}(s)} \mu(s, a') \\ &\stackrel{(\dagger)}{=} \left( \prod_{i=1}^{n-1} p(s_{i+1}|s_i, a_i)\pi_{\mu}(a_i|s_i) \right) \sum_{a' \in \mathcal{A}(s)} \mu(s, a') \\ &\stackrel{(\ddagger)}{\geq} \left( \prod_{i=1}^{n-1} p(s_{i+1}|s_i, a_i)\varepsilon \right) \frac{1}{|S|} \geq \frac{\min(p)^{n-1}\varepsilon^{n-1}}{|S|} \geq \frac{\min(p)^{|S|-1}\varepsilon^{|S|-1}}{|S|} \end{aligned} $$

where $(\dagger)$ follows by definition of the induced policy, and $(\ddagger)$ uses that $\pi_{\mu}$ is $\varepsilon$-uniform and $\sum_{a' \in \mathcal{A}(s)} \mu(s, a') \geq |S|^{-1}$.

We continue with assertion (2). Let $s, s' \in S$ and denote $T(s, s') := E_s^{\pi_{\mu}, M}[\inf\{t \geq 0 : S_t = s'\}]$ the reaching time to $s'$ from $s$. Since $\pi_{\mu}$ is recurrent, by definition, we have $D(\pi_{\mu}; M) = \max_{s \neq s'} T(s, s')$. Let $(s, s') \in S^2$ achieving the maximum of $T$. Using Markov's property, we find that

$$ \begin{aligned} T(s, s') &\leq |S| - 1 + (1 - \mathbf{P}_s^{\pi_{\mu}, M}(\exists t \leq |S| : S_t = s'))T(s, s') \\ &\leq |S| - 1 + (1 - \min(p)^{|S|-1}\varepsilon^{|S|-1})T(s, s') \end{aligned} $$

where $(\dagger)$ follows with the same argument as for assertion (1). Solve in $T(s, s')$. ■
**Lemma A.8.** Let $M, M' \in \mathcal{M}$ be a pair of communicating Markov decision processes and fix $\varepsilon > 0$. For all $\mu \in \mathcal{I}(\varepsilon; M)$, there is $\mu' \in \mathcal{I}(\varepsilon; M')$ such that

$$ \|\mu' - \mu\|_{\infty} \le \min\{D(\pi_{\mu}; M), D(\pi_{\mu}; M')\} \|p' - p\|_{\infty}. $$

**Proof** As $\mu$ is a $\varepsilon$-uniform invariant measure, its induced policy $\pi_{\mu}$ is $\varepsilon$-uniform. Moreover, $M'$ is communicating, so $\pi_{\mu}$ is recurrent on $M'$. Let $\mu'$ be the unique probability invariant measure of $\pi_{\mu}$ in $M'$. By Lemma D.9, we have

$$ \|\mu' - \mu\|_{\infty} \le \min\{D(\pi_{\mu}; M), D(\pi_{\mu}; M')\} \|p' - p\|_{\infty} $$

hence the result.

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

Combining Lemma A.7 and Lemma A.8, we can express the variations of the set of $\varepsilon$-uniform probability invariant measures $\mathcal{I}(\varepsilon)$ in Hausdorff distance as follows.

**Corollary A.9.** Let $M, M' \in \mathcal{M}$ be a pair of communicating Markov decision processes and fix $\varepsilon > 0$. The Hausdorff distance (in $\ell_{\infty}$-norm) between $\mathcal{I}(\varepsilon; M)$ and $\mathcal{I}(\varepsilon; M')$ is bounded by

$$ d_{\infty}(\mathcal{I}(\varepsilon; M'), \mathcal{I}(\varepsilon; M)) \le \frac{|S| \cdot \|p' - p\|_{\infty}}{\varepsilon^{|S|-1} \min(p) |S|-1}. $$

### A.3.6 DECOMPOSITION OF INVARIANT MEASURES WITH UNICHAIN POLICIES

In this paragraph, we show that every invariant measure can be expressed as a convex combination of invariant measures of unichain policies, see Proposition A.10. This result is analogous to the decomposition of flow into simple cycles in Graph Theory. Proposition A.10 has several interesting consequences. The first that we present is a bound on the variations (in Hausdorff distance) of the space of probability invariant measures $\mathcal{I}(M) := \text{Inv}(M) \cap \mathcal{P}(\mathcal{Z})$ as $M$ varies, see Lemma A.11 downstream. Combined with Theorem A.6, we further obtain a bound on the variations (in Hausdorff distance) of the space of $\varepsilon$-uniform probability invariant measures $\mathcal{I}(\varepsilon; M) := \text{Inv}(\varepsilon; M) \cap \mathcal{P}(\mathcal{Z})$ as $M$ varies, see Lemma A.12—A bound that can be compared with Corollary A.9. Proposition A.10 is also used to prove that optimal exploration measures exist, see Theorem B.13.

**Proposition A.10.** Let $M$ be a communicating Markov decision process. Let $\Pi_u$ be the set of unichain policies in $M$. We have $\text{Inv}(M) = \text{conv}(\{\text{Inv}(\pi; M) : \pi \in \Pi_u\})$, where $\text{conv}(\cdot)$ denotes the convex hull.

**Proof** Because $\text{Inv}(\pi; M) \subseteq \text{Inv}(M)$ and that $\text{Inv}(M)$ is convex, we have $\text{conv}(\{\text{Inv}(\pi; M) : \pi \in \Pi_u\}) \subseteq \text{Inv}(M)$.

We show the reverse inclusion.

Let $\mu \in \text{Inv}(M)$. If $\mu = 0$, there is nothing to prove, so we assume $\text{supp}(\mu) \neq \emptyset$. Let $(s_1, a_1, s_2, a_2, \dots, s_n) \in \mathcal{Z}^{n-1} \times S$ a closed path in $M$ such that (I) $p(s_{i+1}|s_i, a_i) > 0$, (II) $\mu(s_i, a_i) > 0$, (III) $s_1 = s_n$ and (IV) $n \ge 2$. The condition (III) states that the path is closed and (IV) that the path is non-trivial. Up to simplifying that path, we can assume that (V) it is simple in the sense that $s_i \neq s_j$ for all $i \neq j < n$. Then, the set of pairs
$\mathcal{Z}_0 := \{(s_i, a_i) : i < n\}$ is the set of recurrent pairs of the policy given by

$$ \pi_0(a|s) := \begin{cases} 1 & \text{if } s = s_i \text{ and } a = a_i; \\ 0 & \text{if } s = s_i \text{ and } a \neq a_i; \\ |\mathcal{A}(s)|^{-1} & \text{if } s \neq s_i. \end{cases} $$

Note that $\pi_0$ is unichain. Let $\mu_0$ the unique probability invariant measure of $\pi_0$. We have $\text{supp}(\mu_0) = \mathcal{Z}_0$. By construction of the path, we have $\mathcal{Z}_0 \subseteq \text{supp}(\mu)$, see (II). Therefore, the set $\{\lambda > 0 : \lambda\mu_0 < \mu\}$ is non-empty; Let $\lambda_0 > 0$ be its supremum. Consider the measure $\mu'$ given by

$$ \mu' := \mu - \lambda_0\mu_0. $$

By choice of $\lambda_0$, we see that $\mu' \in \mathbf{R}_+^Z$. Note that $\mu' \in \text{Inv}(M)$. Indeed, $\text{Inv}(M)$ is the intersection

$$ \text{Inv}(M) = \mathbf{R}_+^Z \cap \mathcal{F} \quad \text{where} \quad \mathcal{F} := \bigcap_{s \in \mathcal{S}} \left\{ \mu'' \in \mathbf{R}^Z : \sum_{a \in \mathcal{A}(s)} \mu''(s, a) = \sum_{z \in \mathcal{Z}} \mu''(z)p(s|z) \right\} $$

and $\mathcal{F}$ is a linear space, so that $\mu' := \mu - \lambda_0\mu_0 \in \mathcal{F}$. As $\mu' \in \mathbf{R}_+^Z$ as explained above, we have $\mu' \in \text{Inv}(M)$. But by choice of $\lambda_0$, the support of $\mu'$ is strictly smaller than the support of $\mu$, because $\text{supp}(\mu') \subseteq \text{supp}(\mu)$ and there must be at least one $z_0 \in \mathcal{Z}_0$ such that $z_0 \notin \text{supp}(\mu_0)$.

So, by induction on the size of the support of $\mu$, we find a sequence $(\lambda_i, \mu_i, \pi_i)_{i \le m}$ with $\lambda_i > 0$, $\mu_i \in \text{Inv}(\pi_u; M)$ and $\pi_i \in \Pi_u$ such that

$$ \mu = \lambda_0\mu_0 + \dots + \lambda_m\mu_m. $$

Note that we can ensure $m + 1 \le |\mathcal{Z}|$. This concludes the proof. ■

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

Follow Proposition A.10, we show that $\mathcal{I}(M)$ is locally $D^*(M)$-Lipschitz continuous where $D^*(M)$ is the worst diameter (Definition A.3).

**Lemma A.11** (Variations of $\mathcal{I}(M)$). Let $M \equiv (\mathcal{Z}, p, r), M' \equiv (\mathcal{Z}, p', r') \in \mathcal{M}$ be a pair of communicating Markov decision processes with the same kernel supports, i.e., $p \sim p'$. The Hausdorff distance (in $\ell_\infty$-norm) between $\mathcal{I}(M)$ and $\mathcal{I}(M')$ is bounded by

$$ d_\infty(\mathcal{I}(M), \mathcal{I}(M')) \le D^*(M)\|p' - p\|_\infty $$

where $D^*(M)$ is the worst diameter (Definition A.3).

**Proof** Because $M$ and $M'$ have the same kernel supports, they have the same space of unichain policies $\Pi_u$. Given $\pi \in \Pi_u$, we write $\mu_\pi$ and $\mu'_\pi$ the unique invariant probability measure of $\pi$ in $M$ and $M'$ respectively. For all $\pi \in \Pi_u$, we bound $\|\mu'_\pi - \mu_\pi\|_\infty$ using Lemma D.9 as

$$ \|\mu'_\pi - \mu_\pi\|_\infty \le D(\pi; M)\|p' - p\|_\infty \le D^*(M)\|p' - p\|_\infty \quad (A.4) $$

where the second inequality follows by definition of the worst diameter.
Let $\mu \in \mathcal{I}(M)$. By Proposition A.10, there exists $\lambda \in \mathcal{P}(\Pi_u)$ such that $\mu = \sum_{\pi \in \Pi_u} \lambda_{\pi} \mu_{\pi}$. Introduce $\mu' := \sum_{\pi \in \Pi_u} \lambda_{\pi} \mu'_{\pi}$. By Proposition A.10, we have $\mu' \in \mathcal{I}(M')$. So, using (A.4), we deduce that

$$ \inf_{\mu'' \in \mathcal{I}(M')} \|\mu'' - \mu\|_{\infty} \le \|\mu' - \mu\|_{\infty} \le \sum_{\pi \in \Pi_u} \lambda_{\pi} \|\mu'_{\pi} - \mu_{\pi}\|_{\infty} \le D^*(M) \|p' - p\|_{\infty}. $$

Similarly, we show that for all $\mu' \in \mathcal{I}(M)$, we have $\inf_{\mu'' \in \mathcal{I}(M)} \|\mu'' - \mu'\|_{\infty} \le D^*(M) \|p' - p\|_{\infty}$. This concludes the proof. ■

**Lemma A.12 (Variations of $\mathcal{I}(\varepsilon; M)$).** Let $M \equiv (\mathcal{Z}, p, r)$, $M' \equiv (\mathcal{Z}, p', r') \in \mathcal{M}$ be a pair of communicating Markov decision processes with the same kernel supports, i.e., $p \sim p'$. Let $\varepsilon < \frac{1}{2}|\mathcal{Z}|^{-1}D(M)^{-1}$ be the required uniformization. The Hausdorff distance (in $\ell_{\infty}$-norm) between $\mathcal{I}(\varepsilon; M)$ and $\mathcal{I}(\varepsilon; M')$ is bounded by

$$ d_{\infty}(\mathcal{I}(\varepsilon; M), \mathcal{I}(\varepsilon; M')) \le D^*(M) \|p' - p\|_{\infty} + 2|\mathcal{Z}|D(M)\varepsilon $$

where $D^*(M)$ is the worst diameter (Definition A.3).

**Proof** Since $\mathcal{I}(\varepsilon; -) \subseteq \mathcal{P}(\mathcal{Z})$, we have $d_{\infty}(\mathcal{I}(\varepsilon; M), \mathcal{I}(\varepsilon; M')) \le 1$ trivially. So, the bound of Lemma A.12 is only interesting when $\|p' - p\|_{\infty} \le D^*(M)^{-1}$. By Proposition D.2, we have $D(M) \le D^*(M)$ so that we can assume that $\|p' - p\|_{\infty} \le D(M)^{-1}$. So, by Lemma D.7, we have

$$ D(M') \le 2D(M). \qquad (A.5) $$

Let $\mu \in \mathcal{I}(\varepsilon; M)$. By Lemma A.11 and because $\mathcal{I}(\varepsilon; M')$ is compact, there exists $\mu' \in \mathcal{I}(\varepsilon; M')$ such that $\|\mu' - \mu\|_{\infty} \le D^*(M)\|p' - p\|_{\infty}$. Following (A.5), we have $\varepsilon < |\mathcal{Z}|^{-1}D(M')^{-1}$. So, by uniformizing $\mu'$ into $\mu'_{\varepsilon} \in \mathcal{I}(\varepsilon; M')$ via Theorem A.6, we have $\|\mu' - \mu_{\varepsilon}\|_{\infty} \le \varepsilon|\mathcal{Z}|D(M')$. So, by triangular inequality, we get

$$ \|\mu' - \mu_{\varepsilon}\| \le D^*(M)\|p' - p\|_{\infty} + \varepsilon|\mathcal{Z}|D(M') \stackrel{(\dagger)}{\le} D^*(M)\|p' - p\|_{\infty} + 2|\mathcal{Z}|D(M)\varepsilon $$

where $(\dagger)$ follows from (A.5).

When starting with $\mu' \in \mathcal{I}(\varepsilon; M')$, we proceed similarly. ■

Note that Corollary A.9 and Lemma A.12 bound the same quantity, $d_{\infty}(\mathcal{I}(\varepsilon; M), \mathcal{I}(\varepsilon; M'))$. Their respective bounds are

$$ \frac{|\mathcal{S}| \cdot \|p' - p\|_{\infty}}{\varepsilon^{|\mathcal{S}|-1} \mathrm{dmin}(p)^{|\mathcal{S}|-1}} \quad \text{V.S.} \quad D^*(M) \|p' - p\|_{\infty} + 2|\mathcal{Z}|D(M)\varepsilon. $$

It is to be noted that the second is not better than the first; The two bounds are rather of a different nature. Since $D(M)$, $D^*(M) \le |\mathcal{S}|\mathrm{dmin}(p)^{1-|\mathcal{S}|}$, it is clear that the second bound is much better than the first when $\varepsilon$ and $\|p' - p\|_{\infty}$ are of the same order. However, when $\|p' - p\|_{\infty} \ll \varepsilon^{|\mathcal{S}|}$ as in the proof of Proposition B.17, the first bound is better. As a matter of fact, the second introduces a flat error $2|\mathcal{Z}|D(M)\varepsilon$ that does not vanish when $\|p' - p\|_{\infty} \to 0$, although $d_{\infty}(\mathcal{I}(\varepsilon; M), \mathcal{I}(\varepsilon; M')) \to 0$.
# Appendix B. Regularized lower bound and approximate optimalities

In this appendix, we provide proof details on approximate optimalities, leveled Bellman gaps and near optimal pairs, as well as the regularized regret lower bound.

**Outline.** Appendix B.1 is dedicated to the proof of Proposition 3, that establishes the most important properties of the leveling transform (Definition 7). In the remaining Appendices B.2 and B.3, we investigate the continuity properties of the regularized regret lower bound (Definition 12). In Appendix B.2, we introduce and study the properties of the concept of information value (Definition B.1), that is central to the GLR exploration tests (16) and to the regret lower bound. In the last Appendix B.3, we focus on the properties of the regularized regret lower bound and establish Propositions 4 to 6.

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

The goal of this paragraph is to provide a proof of Proposition 3 in the main text (the statement is recalled below for better readability). Proposition 3 states that if $||M' - M||^*$ is small with respect to the leveling threshold $\epsilon > 0$, then the $\epsilon$-leveled transform of $M'$ (Definition 7) has the same gain optimal policies and optimal pairs as $M$. Moreover, the required ratio between $||M' - M||^*$ and $\epsilon$ is shown to be rational in the gain-gap $\Delta^g(M)$ (Definition A.4) and the worst diameter $D^*(M)$ (Definition A.3).

**Proposition 3.** For every communicating Markov decision process $M \equiv (\mathcal{Z}, p, \nu)$, there exists a quantity $C(M) < \infty$, that is a rational function of $\Delta^g(M)$ and $D^*(M)$, for all $\epsilon > 0$ and $M' \in \mathcal{M}$ satisfying

$$ \epsilon + 2C(M) ||M' - M||^* < \Delta^g(M) \quad \text{and} \quad C(M) ||M' - M||^* < \epsilon \quad (B.1) $$

we have

(1) $[M']_\epsilon$ and $M$ have the same gain optimal policies;

(2) $\mathcal{Z}_\epsilon^{**}(M) = \mathcal{Z}^{**}(M)$;

**Proof outline.** The remaining of this paragraph is dedicated to the proof of Proposition 3. In Lemma B.1, we show that bias optimal policies of $M'$ are Bellman optimal (Definition A.2) in $[M']_\epsilon$. In turn, we prove Lemma B.2, that consists in the assertion (1) of Proposition 3: by leveling a noisy model, we recover the set of gain optimal policies. Once (1) is established, the other assertion (2) is immediate by definition of $\mathcal{Z}^{**}(M)$.

**Lemma B.1.** Let $M' \in \mathcal{M}$ and $\epsilon > 0$. Every bias optimal policy of $M'$ is Bellman optimal (Definition A.2) in $[M']_\epsilon$, i.e., for all $\pi \in \Pi$ that is bias optimal policy in $M'$, we have

(1) $\text{sp}(g^\pi([M']_\epsilon)) = 0$; and

(2) $[r']_\epsilon(s, a) + [p']_\epsilon(s, a)b^\pi([M']_\epsilon) \le g^\pi(s; [M']_\epsilon) + b^\pi(s; [M']_\epsilon)$ for all $(s, a) \in \mathcal{Z}$.

In particular, $\Pi^*(M') \subseteq \Pi^*([M']_\epsilon)$ and $g^*(M') = g^*([M']_\epsilon)$.

**Proof** Let $\pi^*$ be a bias optimal policy of $M'$, so that $g^\pi^*([M']_\epsilon) = g^*(M')$ and $b^\pi^*([M']_\epsilon) = b^*(M')$. By construction, we have $[r']_\epsilon(z) = r'(z) + \mathbf{1}(\Delta^*(z; M') < \epsilon)\Delta^*(z; M')$ for $z \in \mathcal{Z}$, so

$$ g^\pi^*([M']_\epsilon) = g^\pi^*(M') = g^*(M') \quad \text{and} \quad b^\pi^*([M']_\epsilon) = b^\pi^*(M') = b^*(M'). $$
Therefore, sp(g$^{π*}$([M']$_{ε}$)) = 0 and π* satisfies the Bellman equations (A.1) in [M']$_{ε}$, i.e., it is Bellman optimal (Definition A.2) in [M']$_{ε}$; Hence the assertions (1) and (2). ■

In Appendix D, we investigate the sensibility of the gain and bias functions to changes of reward function and transition kernel. Following Lemma D.12 and Lemma D.14, for every policy π ∈ Π and provided that ||p' - p||* ≤ D*(M)^-1, we have

$$
\begin{align}
\|g^{\pi}(M') - g^{\pi}(M)\|_{\infty} &\le C_g(M)\|M' - M\|^* \nonumber \\
\|b^{\pi}(M') - b^{\pi}(M)\|_{\infty} &\le C_b(M)\|M' - M\|^* \tag{B.2} \\
\|\Delta^{\pi}(M') - \Delta^{\pi}(M)\|_{\infty} &\le C_{\Delta}(M)\|M' - M\|^* \nonumber
\end{align}
$$

where C_g(M), C_b(M), C_Δ(M) are polynomial in D*(M) and of respective orders D*(M), D*(M)², D*(M)².

**Lemma B.2.** Fix ε > 0 a leveling parameter. For every pair of communicating Markov decision processes M, M' ∈ M such that

$$
\epsilon + 2C_g(M)\|M' - M\|^* < \Delta^g(M) \quad \text{and} \quad C_\Delta(M)D^*(M)\|M' - M\|^* < \epsilon \quad (B.3)
$$

we have Π*([M']_ε) = Π*(M).

**Proof** We proceed by double inclusion.

Assume that π ∈ Π*([M']_ε). By Lemma B.1, bias optimal policies of M' are Bellman optimal (Definition A.2) in [M']_ε. In particular, they are gain optimal. In the mean time, bias optimal policies are supported in weakly optimal actions, so by construction of [M']_ε, the gain of bias optimal policies of M' is the same in M' and [M']_ε. Combined, we conclude that g*([M']_ε) = g*(M'). Now, since M' and [M']_ε only differ in their reward function with ||r' - [r']_ε||_∞ ≤ ε, it follows that

$$
g^{\pi}(M') \geq g^{\pi}([M']_{\epsilon}) - \epsilon e = g^{*}(M') - \epsilon e
$$

where e is the unitary vector. By (B.2), we further have g$^{π}$(M) ≥ g$^{π}$(M') - C$_{g}$(M) ||M' - M||*e and g$^{*}$(M') ≥ g$^{*}$(M) - C$_{g}$(M) ||M' - M||*e. All together,

$$
g^{\pi}(M) \geq g^{*}(M) - (\epsilon + 2C_{g}(M)\|M' - M\|^{*})e
$$

so π ∈ Π*(M) if ε + 2C_g(M) ||M' - M||^* < Δ^g(M). This is indeed the case by assumption.

Conversely, let π ∈ Π*(M). Let Z₁, ..., Z_m be the recurrent components of π and let μᵢ be the unique probability invariant measure of π supported in Zᵢ. Fix π' a bias optimal policy of M', so that Δπ'(M') ≥ 0. So,

$$
\Delta^{\pi'}(z; M) \geq -C_{\Delta}(M) \|M' - M\|^{*} \quad (B.4)
$$

for every pair z ∈ Z. We have already shown that Π*([M']_ε) ⊆ Π*(M). Since Π*(M') ⊆ Π*([M']_ε) by Lemma B.1, we have Π*(M') ⊆ Π*(M). So, π' ∈ Π*(M).

We deduce that g$^{π'}$(M) = g$^{π}$(M). Now, for i ∈ {1, ..., m}, we have g$^{π}$(M) = g$^{π'}$(M) - ∑z∈Z μᵢ(z)Δ$^{π'}$(z; M), so together with g$^{π}$(M) = g$^{π'}$(M), we get ∑z∈Z[μᵢ(z)Δ$^{π'}$(z; M)]⁺ = ∑z∈Z[μᵢ(z)Δ$^{π'}$(z; M)]⁻ for all i ∈ {1, ..., m}. Combined with (B.4), we obtain

$$
\max_{z \in \mathcal{Z}} \mu(z) \Delta^{\pi'}(z; M) \leq C_{\Delta}(M) \|M' - M\|^{*}. \qquad (B.5)
$$
By Lemma D.1, we have $\min(\mu_i) \ge D(\pi; M|_{Z_i})^{-1}$. Together with $D(\pi; M|_{Z_i}) \ge D(\pi; M)^{-1}$ and (B.5), we conclude that

$$ \Delta^{\pi'}(z; M) \le C_{\Delta}(M)D(\pi; M)\|M' - M\|^* \le C_{\Delta}(M)D^*(M)\|M' - M\|^* $$

for all $z \in \mathcal{Z}$ that is recurrent under $\pi$. So, provided that $C_{\Delta}(M)D^*(M)\|M' - M\|^* < \varepsilon$— which is indeed the case by assumption, we have $\Delta^{\pi'}(z; [M]_{\varepsilon}) = 0$ for every $z \in \mathcal{Z}$ that is recurrent under $\pi$ in $M$. Now, note that the recurrent pairs of $\pi$ are the same on $M, M'$, $[M']_{\varepsilon}$. So, again using the formula $g^{\pi'}([M]_{\varepsilon}) = g^{\pi'}([M]_{\varepsilon}) - \sum_{z \in \mathcal{Z}} \mu(z)\Delta^{\pi'}(z; [M]_{\varepsilon})$ that holds for every probability invariant measure of $\pi$ in $[M']_{\varepsilon}$, we conclude that $g^{\pi'}([M]_{\varepsilon}) = g^{\pi'}([M]_{\varepsilon})$.<fnref n="3" /> By Lemma B.1, $\pi'$ is Bellman optimal (Definition A.2) in $[M']_{\varepsilon}$ hence is gain optimal in $[M']_{\varepsilon}$ in particular. We conclude that $g^{\pi'}([M]_{\varepsilon}) = g^*(M)$, i.e., $\pi \in \Pi^*(M)$. ■

With Lemma B.2 in hand, we can prove Proposition 3.

**Proof of Proposition 3** Assume that $M' \in \mathcal{M}$ satisfies $\varepsilon + 2C_g(M)\|M' - M\|^* < \Delta^g(M)$. By Lemma B.2, we have $\Pi^*([M']_{\varepsilon}) = \Pi^*(M)$, hence proving (1). Together with the fact that the transition kernels of $M$ and $[M']_{\varepsilon}$ have the same support, it follows that $\mathcal{Z}^{**}(M) = \mathcal{Z}^{**}([M']_{\varepsilon})$, hence proving (2). This concludes the proof. ■

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

In this section, we discuss the notion of the **information value** (Definition B.1), that quantifies how efficient is a measure on $\mathcal{Z}$ to reject the leveled confusing set. Information values provide an alternative view on information constraints, are key in the derivation of the continuity properties of the regularized lower bound. In association with the information value, we introduce **critical models** (Definition B.2) as the confusing Markov decision processes that are the hardest to reject under a measure on $\mathcal{Z}$.

**Additional notations.** In this section, we write $P_\delta(\mathcal{Z})$ the set of probability distributions $\mu$ on $\mathcal{Z}$ such that $\min(\mu) \ge \delta$. We write $e := \sum_{z \in \mathcal{Z}} e_z$ the unit measure on $\mathcal{Z}$ and $(e_z)_{z \in \mathcal{Z}}$ the canonical basis of $\mathbb{R}^{\mathcal{Z}}$. For $M' \subseteq \mathcal{M}$, we denote $\text{cl}(M')$ the closure of $M'$ for the topology induced by $\|\cdot\|$.

**Definition B.1 (Information value).** Fix $\varepsilon > 0$ a leveling parameter. The $\varepsilon$-leveled information value of a measure $\mu \in \mathbb{R}^{\mathcal{Z}}$ in $M$ is given by

$$ C_{\varepsilon}(\mu, M) := \inf_{M^{\dagger} \in \text{Cnf}_{\varepsilon}(M)} \left\{ \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^{\dagger}(z)) \right\} \in [0, \infty]. $$

Note that the regret lower bound can be written as

$$ K(M) = \inf_{\mu \in \text{Inv}(M)} \left\{ \frac{\sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z; M)}{C_0(\mu, M)} \right\}. $$

As a matter of fact, given $\mu \in \text{Inv}(M)$, the quantity $C_0(\mu, M)^{-1}$ is the scalar $\lambda \in [0, \infty]$ with which $\mu$ must be normalized so that it properly rejects all confusing models, in the sense of $\inf_{M^{\dagger} \in \text{Cnf}(M)} \sum_{z \in \mathcal{Z}} \lambda\mu(z) \cdot \text{KL}(M(z) || M^{\dagger}(z)) \ge 1$.

<footnote n="3">3. To see this, note that this already holds for $\mu = \mu_i$ with $i \in \{1, \dots, m\}$ and use that every probability invariant measure of $\pi$ is a convex combination of $\mu_1, \dots, \mu_m$.</footnote>
**Definition B.2 (Critical models).** Fix $\varepsilon > 0$ a leveling parameter and $\mu \in \mathbb{R}^{\mathcal{Z}}$ a measure. A Markov decision process $M^\dagger \in \text{cl}(\text{Cnf}_\varepsilon(M))$ is said $(\mu, \varepsilon, M)$-**critical** if $M^\dagger$ achieves the $\varepsilon$-leveled information value of $\mu$ in $M$, i.e.,

$$C_{\varepsilon}(\mu, M) = \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^{\dagger}(z)).$$

For $\varepsilon = 0$, we talk more simply of information value and $(\mu, M)$-critical models. Unfortunately, the case $\varepsilon = 0$ is not well-behaved relatively to $M$ in general. It is among the reasons why the regret lower bound is discontinuous with respect to $M$. This is quite inconvenient when one has only access to noisy copies of $M$, as it is the case in learning. Thankfully, when the leveling parameter satisfies $\varepsilon > 0$ and when $\mu$ is fully supported, the leveled information value is continuous in both $M$ (Lemma B.11) and $\mu$ (Lemma B.10). Accordingly, it can be correctly estimated even in the presence of noise.

## B.2.1 PROPERTIES OF THE CONFUSING SET AND OF CRITICAL MODELS

In this paragraph, we provide a few useful properties of leveled confusing sets and critical models. In Lemma B.3, we rephrase the definition of the $\varepsilon$-confusing set in terms of the gain function. In Corollary B.5, we show that all critical models have small bias span and that their gain optimal policies are unichain.

**Lemma B.3 (Characterization of confusing models).** Let $M \in \mathcal{M}$ be a communicating model and $\varepsilon > 0$. Fix $M' \gg M$ such that $M'(z) = M(z)$ for all $z \in \mathcal{Z}_\varepsilon^{**}(M)$. The following assertions are equivalent:

(1) $M^\dagger \in \text{Cnf}_\varepsilon(M)$, i.e., $\Pi^*(M^\dagger) \cap \Pi^*(M) = \emptyset$;

(2) $g^*(M^\dagger) > g^\pi(M^\dagger)$ for all $\pi \in \Pi^*(M)$;

(3) $g^*(M^\dagger) > g^*(M)$.

**Proof** Let $M' \gg M$ be such that $M'(z) = M(z)$ for all $z \in \mathcal{Z}_\varepsilon^{**}(M)$. Because $M' \gg M$ and $M$ is communicating, $M'$ is communicating as well.

Let $\pi \in \Pi^*(M)$. If $\mathcal{Z}_\pi$ denotes the recurrent pairs of $\pi$ in $M$, then since $p' \gg p$, we have $\mathbf{P}_{\pi,M'}^*(\forall m, \exists n \ge m : Z_n \in \mathcal{Z}_\pi) = 1$ regardless of the initial state $s \in \mathcal{S}$. In other words, the iterates of $\pi$ hit $\mathcal{Z}_\pi$ infinitely often in $M'$. But $M' = M$ on $\mathcal{Z}^{**}(M)$ and $\mathcal{Z}_\pi \subseteq \mathcal{Z}^{**}(M)$ since $\pi \in \Pi^*(M)$; So, every recurrent pair of $\pi$ in $M'$ belongs to $\mathcal{Z}^{**}(M)$ and in particular,

$$g^\pi(M') = g^\pi(M) = g^*(M). \qquad (B.6)$$

Following (B.6), the equivalence between the assertions (2) and (3) in Lemma B.3 is immediate; and $\Pi^*(M^\dagger) \cap \Pi^*(M) = \emptyset$ as soon as $\pi \notin \Pi^*(M^\dagger)$, i.e., as soon as $g^*(M^\dagger) > g^\pi(M)$. ■

**Lemma B.4 (Simplification of confusing models).** Assume that $\mathcal{M}$ is in product form, i.e., that $\mathcal{M} = \prod_{z \in \mathcal{Z}} (\mathcal{R}_z \times \mathcal{P}_z)$. Let $M \in \mathcal{M}$ a communicating model and fix $\varepsilon \ge 0$. For every $M^\dagger \in \text{Cnf}_\varepsilon(M)$, there exists $M^\ddagger \in \text{Cnf}_\varepsilon(M)$ such that

(1) $M^\ddagger$ is communicating;
(2) sp(b*(M†)) ≤ D(M);

(3) M†(z) = M(z) for all z ∈ Z ∗∗ (M) ∪ Z ∗∗ (M†) c ;

(4) For all z ∈ Z , KL(M(z)||M†(z)) ≤ KL(M(z)||M†(z));

(5) ‖M† − M‖ ≤ ‖M† − M‖.

**Proof** We consider the extended Markov decision process M' = M† ∪ M where, from the state s ∈ S , a choice of action consists in choosing whether the transition is done in M or in M†, i.e., choosing a ∈ A (s), then a reward among { ν ( s, a ) , ν † ( s, a ) } and a transition kernel among { p ( s, a ) , p † ( s, a ) } . Note that M' is communicating with D ( M' ) ≤ D ( M ) . Moreover,

$$
g^*(M') \geq g^*(M) \quad \text{and} \quad g^*(M') \geq g^*(M^\dagger).
$$

An (extended) policy achieving optimal bias in M' defines a policy π' on M together with a model M† such that g*(M†) = g*(M') = gπ'(M†) and sp(b*(M†)) = sp(b*(M')) ≤ D(M') ≤ D(M), see Lemma B.20. So M† satisfies (1). By construction, we also have

$$
\sum_{z \in \mathcal{Z}} \mu(z) \mathrm{KL}(M(z) || M^{\dagger}(z)) \leq \sum_{z \in \mathcal{Z}} \mu(z) \mathrm{KL}(M(z) || M^{\dagger}(z)). \quad (B.7)
$$

To conclude, we show that M ‡ ∈ Cnf$_{ε}$( M ) as follows. Because M † ∈ Cnf$_{ε}$( M ), it follows that M ‡ coincides with M on Z ∗∗ ε ( M ) . In particular, every gain optimal policy π ∈ Π $^{∗}$( M ) has at least one recurrent component within Z $^{∗∗}$( M ) ⊆ Z ∗∗ ε ( M ) hence satisfies g $^{π}$( s ; M $^{‡}$) = g $^{∗}$( s ; M ) for some s ∈ S . But g $^{∗}$( M $^{‡}$) ≥ g $^{∗}$( M $^{†}$) > g $^{∗}$( M ) by Lemma B.3, so by Lemma B.3 again, we have M ‡ ∈ Cnf$_{ε}$( M ) .

Following Lemma B.4, we obtain that critical models have small bias span, see Corol-
lary B.5 below.

**Corollary B.5 (Structure of critical models).** Assume that M is in product form, i.e., that M = ∏ z ∈Z ( R$_{z}$ × P$_{z}$ ) . Let M ∈ M a communicating model, ε > 0 and fix µ ∈ ( R ∗ $_{+}$) Z a fully supported measure. Every ( µ, ε, M )-critical model M † is such that

(1) sp(b*(M†)) ≤ D(M);

(2) M $^{†}$( z ) = M ( z ) for all z ∈ Z ∗∗ ε ( M ) ∪ Z ∗∗ ( M $^{†}$) c .

Another consequence of Lemma B.4 is that every model is bounded away (in norm) from
its confusing set relatively to its gain-gap and its diameter, see Lemma B.6 below.

**Lemma B.6 (Distance to confusing set).** Every communicating model $M \in \mathcal{M}$ is bounded away from its confusing set (in norm), i.e.,

$$
\inf_{M^{\dagger} \in \text{Cnf}(M)} \|M^{\dagger} - M\| \geq \frac{\Delta^g(M)}{4D(M)} > 0
$$

where Δ<sup>g</sup>(M) is the gain-gap of M, see Definition A.4.

**Proof** Let $M^\dagger \in \text{Cnf}(M)$. By Lemma B.4, there exists $M^\dagger \in \text{Cnf}(M)$ such that $\|M^\dagger - M\| \le$ \\ $\|M^\dagger - M\|$ and $\text{sp}(b^*(M^\dagger)) \le D(M)$. By Lemma B.20, we also have $\text{sp}(b^*(M)) \le D(M)$.
Both $M$ and $M^\ddag$ are communicating, so $\text{sp}(g^*(M)) = \text{sp}(g^*(M^\ddag)) = 0$, so by Lemma D.8,

$$ \begin{aligned} \|g^\pi(M^\ddag) - g^\pi(M)\|_\infty &\le \|r^\ddag - r\|_\infty + \frac{1}{2}D(M)\|p^\ddag - p\|_\infty; \\ \|g^{\pi^\ddag}(M^\ddag) - g^{\pi^\ddag}(M)\|_\infty &\le \|r^\ddag - r\|_\infty + \frac{1}{2}D(M)\|p^\ddag - p\|_\infty \end{aligned} \qquad (B.8) $$

where $\pi$ and $\pi^\ddag$ are bias optimal policies of $M$ and $M^\ddag$ respectively.

By assumption, we have $\pi^\ddag \notin \Pi^*(M)$, so

$$ \begin{aligned} \Delta^g(M) &\le \|g^{\pi^\ddag}(M) - g^\pi(M)\|_\infty = \max(g^\pi(M) - g^{\pi^\ddag}(M)) \\ &\le \max(g^\pi(M) - g^\pi(M^\ddag)) + \max(g^\pi(M^\ddag) - g^{\pi^\ddag}(M^\ddag)) + \max(g^\pi(M^\ddag) - g^{\pi^\ddag}(M)) \\ &\stackrel{(\dagger)}{\le} \max(g^\pi(M) - g^\pi(M^\ddag)) + \max(g^\pi(M^\ddag) - g^{\pi^\ddag}(M)) \\ &\stackrel{(\ddag)}{\le} 2(\|r^\ddag - r\|_\infty + D(M)\|p^\ddag - p\|_\infty) \le 4 \max\{1, D(M)\}\|M^\ddag - M\| \end{aligned} $$

where $(\dagger)$ follows from $\pi^\ddag \in \Pi^*(M^\ddag)$ and $(\ddag)$ follows from (B.9). Note that $D(M) \ge 1$ by definition. We conclude by solving the above in $\|M^\ddag - M\|$ and using that $\|M^\ddag - M\| \ge \|M^\ddag - M\|$. ■

For the last result of this paragraph, we provide a variant of Lemma B.6, see Lemma B.7. This result generalized the lower bound of Lemma B.6 from confusing set to a weak version of the alternative set. The alternative set of $M$ is the collection of $M^\dagger \gg M$ such that $\Pi^*(M^\dagger) \cap \Pi^*(M) = \emptyset$. In Lemma B.7 below, the absolute continuity condition “$M^\dagger \gg M$” is strengthened to a mutual absolute continuity condition on supports, i.e., to “$p^\dagger \sim p$”.

**Lemma B.7 (Distance to alternative set, weak version).** Given a communicating model $M \equiv (\mathcal{Z}, p, r) \in \mathcal{M}$, if $M^\dagger \equiv (\mathcal{Z}, p^\dagger, r^\dagger)$ is such that (1) $p^\dagger \sim p$ and (2) $\Pi^*(M^\dagger) \setminus \Pi^*(M) \ne \emptyset$, then

$$ \|M^\dagger - M\| \ge \frac{\Delta^g(M)}{4D(M)} $$

where $\Delta^g(M)$ is the gain-gap of $M$, see Definition A.4.

**Proof** By (2), $p^\dagger$ and $p$ have the same support, so $M^\dagger$ is communicating as well. Assume that $\|p^\dagger - p\|_\infty \le D(M)^{-1}$. Then, by Lemma D.7, we have $D(M^\dagger) \le 2D(M)$ so $\text{sp}(b^*(M^\dagger)) \le 2D(M)$. By Lemma B.20, we also have $\text{sp}(b^*(M)) \le D(M)$.

Let $\pi^\dagger \in \Pi^*(M^\dagger) \setminus \Pi^*(M)$. In particular, $g^{\pi^\dagger}(M) < g^*(M)$ so $\pi^\dagger$ has a recurrent class of pairs $\mathcal{Z}^\dagger \subseteq \mathcal{Z}$ (in $M$) on which it has sub-optimal gain (in $M$). By (2), $p^\dagger$ and $p$ have the same support, so the recurrent classes of policies are the same under $M$ and $M^\dagger$. In particular, $\mathcal{Z}^\dagger$ is also a recurrent class of $\pi^\dagger$ in $M^\dagger$. Now, up to an infinitesimal perturbation of $r^\dagger$ of the form $r^\dagger(z) + \epsilon \mathbf{1}(z \in \mathcal{Z}^\dagger)$ with $\epsilon > 0$, we can assume that $\mathcal{Z}^\dagger$ is the unique optimal recurrent class of $M^\dagger$; In other words, that all gain optimal policies of $M^\dagger$ are unichain with recurrent class $\mathcal{Z}^\dagger$. In particular, all bias optimal policies of $M^\dagger$ with unique recurrent class $\mathcal{Z}^\dagger$, so are sub-optimal in $M$. Let $\pi^\dagger$ a bias optimal policy of $M^\dagger$.

From then, the proof is mostly similar to the one of Lemma B.6.
Both $M$ and $M^\dagger$ are communicating, so $\text{sp}(g^*(M)) = \text{sp}(g^*(M^\dagger)) = 0$, so by Lemma D.8,

$$ \begin{aligned} \|g^\pi(M^\dagger) - g^\pi(M)\|_\infty &\le \|r^\dagger - r\|_\infty + \frac{1}{2}D(M)\|p^\dagger - p\|_\infty; \\ \|g^{\pi^\dagger}(M^\dagger) - g^{\pi^\dagger}(M)\|_\infty &\le \|r^\dagger - r\|_\infty + D(M)\|p^\dagger - p\|_\infty \end{aligned} \qquad (B.9) $$

where $\pi$ and $\pi^\dagger$ are bias optimal policies of $M$ and $M^\dagger$ respectively.

As argued upstream, we have $\pi^\dagger$ has sub-optimal gain in $M$, so

$$ \begin{aligned} \Delta^g(M) &\le \|g^{\pi^\dagger}(M) - g^\pi(M)\|_\infty = \max(g^\pi(M) - g^{\pi^\dagger}(M)) \\ &\le \max(g^\pi(M) - g^{\pi^\dagger}(M)) + \max(g^\pi(M^\dagger) - g^{\pi^\dagger}(M^\dagger)) + \max(g^\pi(M^\dagger) - g^{\pi^\dagger}(M)) \\ &\stackrel{(\dagger)}{\le} \max(g^\pi(M) - g^{\pi^\dagger}(M)) + \max(g^\pi(M^\dagger) - g^{\pi^\dagger}(M)) \\ &\stackrel{(\dagger)}{\le} 2(\|r^\dagger - r\|_\infty + D(M)\|p^\dagger - p\|_\infty) \le 4\max\{1, D(M)\}\|M^\dagger - M\| \end{aligned} $$

where $(\dagger)$ follows from $\pi^\dagger \in \Pi^*(M^\dagger)$ and $(\dagger)$ follows from (B.9). Conclude using $D(M) \ge 1$.

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

### B.2.2 REGULARITY PROPERTIES OF THE INFORMATION VALUE

In this paragraph, we show that for $\varepsilon > 0$ and when working away from the boundary of $\mathcal{P}(\mathcal{Z})$, the information value $C_\varepsilon(\mu, M)$ is bounded relatively to the reference value $C_\varepsilon(e, M)$ (Lemma B.8) that itself is bounded below (Lemma B.9), and is continuous relatively to $\mu \in \mathcal{P}_\delta(\mathcal{Z})$ (Lemma B.10) and $M \in \mathcal{M}$ (Lemma B.11).

**Lemma B.8.** Fix $M \in \mathcal{M}$, a leveling parameter $\varepsilon \ge 0$ and $\delta > 0$. The leveled information value of $\mu \in \mathcal{P}_\delta(\mathcal{Z})$ is lower and upper bounded as

$$ \delta C_\varepsilon(e, M) \le C_\varepsilon(\mu, M) \le C_\varepsilon(e, M). $$

**Proof** By definition, $\min(\mu) \ge \delta$ for all $\mu \in \mathcal{P}_\delta(\mathcal{Z})$. So,

$$ \begin{aligned} C_\varepsilon(\mu, M) &:= \inf_{M^\dagger \in \text{Cnf}_\varepsilon(M)} \left\{ \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^\dagger(z)) \right\} \\ &\ge \delta \inf_{M^\dagger \in \text{Cnf}_\varepsilon(M)} \left\{ \sum_{z \in \mathcal{Z}} 1 \cdot \text{KL}(M(z) || M^\dagger(z)) \right\} = \delta C_\varepsilon(e, M). \end{aligned} $$

Using that $\max(\mu) \le 1$, the upper bound follows from a similar computation.

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

**Lemma B.9 (Gap bound of information value).** For all $M \in \mathcal{M}$ and whatever the leveling parameter $\varepsilon \ge 0$, we have

$$ C_\varepsilon(e, M) \ge \left( \frac{\Delta^g(M)}{4D(M)} \right)^2. $$
**Proof** The result follows from a straight forward computation. We have

$$
\begin{align*}
C_{\varepsilon}(M) &= \inf_{M^{\dagger} \in \text{Cnf}_{\varepsilon}(M)} \left\{ \sum_{z \in \mathcal{Z}} \text{KL}(M(z) || M^{\dagger}(z)) \right\} \\
&\overset{(\dagger)}{\ge} \inf_{M^{\dagger} \in \text{Cnf}(M)} \left\{ \sum_{z \in \mathcal{Z}} \text{KL}(M(z) || M^{\dagger}(z)) \right\} \\
&\overset{(\ddagger)}{\ge} \inf_{M^{\dagger} \in \text{Cnf}(M)} \max_{z \in \mathcal{Z}} \left\{ \text{KL}(M(z) || M^{\dagger}(z)) \right\} \\
&\overset{(\ddagger)}{\ge} \inf_{M^{\dagger} \in \text{Cnf}(M)} \max_{z \in \mathcal{Z}} \left\{ \left( \|r^{\dagger}(z) - r(z)\|_{\infty} + \|p^{\dagger}(z) - p(z)\|_{1} \right)^2 \right\} \\
&= \inf_{M^{\dagger} \in \text{Cnf}(M)} \|M^{\dagger} - M\|^2 \\
&\overset{(\S)}{\ge} \left( \frac{\Delta^g(M)}{4D(M)} \right)^2
\end{align*}
$$

where (†) follows from Cnf(ε; M) ⊆ Cnf(M); (‡) follows from Pinsker's inequality; and (§) follows from Lemma B.6. ■

**Lemma B.10 (Continuity in μ).** Fix $M \in \mathcal{M}$, a leveling parameter $\varepsilon \ge 0$ and $\delta > 0$. For all $\mu, \mu' \in \mathcal{P}_{\delta}(\mathcal{Z})$ such that $\|\mu' - \mu\|_{\infty} < \frac{1}{2}\delta$, we have

$$
|C_{\varepsilon}(\mu', M) - C_{\varepsilon}(\mu', M)| \le \frac{2C_{\varepsilon}(\mu, M)}{\delta} \cdot \|\mu' - \mu\|_{\infty}.
$$

**Proof** Let $\mu, \mu' \in \mathcal{P}_\delta(\mathcal{Z})$. By Lemma B.8, $C_\epsilon(\mu, M)$ and $C_\epsilon(\mu', M)$ are either both finite or infinite. If $\text{Cnf}(M) = \emptyset$, then these quantities are infinite and there is nothing to be said; Let us assume that $C_\epsilon(\mu, M)$, $C_\epsilon(\mu', M) < \infty$. Accordingly, there exist $M_\mu^\dagger$ and $M_{\mu'}^\dagger$ that are a $(\mu, \epsilon, M)$-critical and a $(\mu', \epsilon, M)$-critical model respectively. Note that since $\|\mu' - \mu\|_\infty < \frac{1}{2}\delta$ with $\mu \in \mathcal{P}_\delta(\mathcal{Z})$, we can write $\mu' = \mu + u\mu$ with $\|u\|_\infty \le \frac{1}{2}\delta^{-1}\|\mu' - \mu\|_\infty$. Therefore,

$$
\begin{align*}
C_{\varepsilon}(\mu', M) &:= \inf_{M^{\dagger} \in \text{Cnf}_{\varepsilon}(M)} \left\{ \sum_{z \in \mathcal{Z}} \mu'(z) \text{KL}(M(z) || M^{\dagger}(z)) \right\} \\
&\le \sum_{z \in \mathcal{Z}} \mu'(z) \text{KL}(M(z) || M_{\mu}^{\dagger}(z)) \\
&\le (1 + \|u\|_{\infty}) \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M_{\mu}^{\dagger}(z)) \le \left(1 + \frac{\|\mu' - \mu\|_{\infty}}{\delta}\right) C_{\varepsilon}(\mu, M).
\end{align*}
$$

As $\mu$ and $\mu'$ play a symmetric role in the proof, they can be interchanged. This immediately provides a lower bound of $C_\epsilon(\mu', M)$ with respect to $C_\epsilon(\mu, M)$. We conclude by using $(1 + \frac{\|\mu' - \mu\|_\infty}{\delta})^{-1} \ge 1 - \frac{2\|\mu' - \mu\|_\infty}{\delta}$, that holds because $\|\mu' - \mu\|_\infty < \frac{1}{2}\delta$. ■

**Lemma B.11 (Continuity in M).** Let $\mathcal{M}$ be an ambient space with Bernoulli rewards (Assumption 3) in product form (Assumption 4). Fix $M \in \mathcal{M}$ a communicating model. There exist functions $\alpha, \beta_1, \beta_2, \beta : \mathcal{M} \to \mathbf{R}_+^*$ that are polynomial in $|\mathcal{Z}|, D, \text{dmin}(M)$ and
$C(e, M)$, such that, for all leveling parameter $\varepsilon > 0$ with $\text{Cnf}_\varepsilon(M) = \text{Cnf}(M)$ and all $\delta > 0$, if $M' \in \mathcal{M}$ satisfies

$$ \|M' - M\|^* \le \min\left\{\frac{\varepsilon}{\alpha(M)}, \exp\left(-\frac{1}{\delta}\beta_1(M) - \beta_2(M)\right)\right\} \quad (B.10) $$

then for all $\mu \in \mathcal{P}_\delta(M)$, we have

$$ |C_\varepsilon(\mu, M') - C_\varepsilon(\mu, M)| \le \exp(\beta(M)) \|M' - M\|^*. $$

**Proof idea.** The proof is difficult. We start by introducing $\mathcal{M}_\varepsilon$, a well-behaved neighborhood of $M$ for the support-aware norm $\|\cdot\|^*$, given by

$$ \mathcal{M}_\varepsilon := \left\{ M' : \|M' - M\|^* < \min\left\{\frac{1}{D(M)}, \frac{\Delta^g(M)}{4\max\{1, D(\pi_u; M)\}}, \frac{1}{2}\mathrm{dmin}(p), \frac{\varepsilon}{\alpha(M)}\right\} \right\} \quad (B.11) $$

where (I) the condition with $D(M)^{-1}$ is to make sure that $D(M') \le 2D(M)$, see Lemma D.7; (II) the condition with $\frac{1}{4}D(M)^{-1}\Delta^g(M)$ is to make sure that $M' \notin \text{Cnf}(M)$, see Lemma B.7; (III) the condition with $\frac{1}{2}\mathrm{dmin}(p)$ is a bit technical, and is to obtain uniform bounds on escaping probabilities; and (IV) the condition with $\frac{\varepsilon}{\alpha(M)}$ follows from Proposition 3, stating that there exists $\alpha(M) < \infty$ such that if the leveling parameter $\varepsilon > 0$ is small enough, every model $M' \in \mathcal{M}$ that satisfies

$$ \|M' - M\|^* \le \frac{\varepsilon}{\alpha(M)} \quad (B.12) $$

is such that $\mathcal{Z}^{**}([M']_\varepsilon) = \mathcal{Z}^{**}(M)$. Note that by Lemma B.3, such a model $M'$ satisfies

$$ \text{Cnf}_\varepsilon(M') = \{ M'^{\dagger} \gg M : M'^{\dagger} = M' \text{ on } \mathcal{Z}^{**}(M) \text{ and } g^*(M'^{\dagger}) > g^*(M') \}. \quad (B.13) $$

Fix $\hat{M}, \widetilde{M} \in \mathcal{M}_\varepsilon$ generic Markov decision processes in the neighborhood of $M$. The goal is to upper-bound the information value of $\hat{M}$ relatively to the information value of $\widetilde{M}$. We will conclude by instantiating $\hat{M}$ and $\widetilde{M}$ as $M = \hat{M}, M' = \widetilde{M}$ and $M = \widetilde{M}, M' = \hat{M}$.

Let $\widetilde{M}^\dagger$ be a $(\mu, \varepsilon, \widetilde{M})$-critical model. We introduce $\hat{M}^\dagger$ the model given by

$$ \hat{M}^{\dagger}(z) := \begin{cases} \hat{M}(z) & \text{if } z \in \mathcal{Z}^{**}(M); \\ \widetilde{M}^{\dagger}(z) & \text{if } z \notin \mathcal{Z}^{**}(M). \end{cases} \quad (B.14) $$

In general, we have $\hat{M}^\dagger \notin \text{Cnf}_\varepsilon(\hat{M})$ because the condition $g^*(\hat{M}^\dagger) > g^*(\hat{M})$ is false—barely false, but false nonetheless. But if it is false, then because $g^*(\widetilde{M}^\dagger) > g^*(\widetilde{M})$ and $\hat{M} \approx \widetilde{M}$, there is a slight modification of $\hat{M}^\dagger$ that belongs to $\text{Cnf}_\varepsilon(\hat{M})$. In the first place, the condition “$g^*(\hat{M}^\dagger) > g^*(\hat{M})$” may be false because by going from $\widetilde{M}^\dagger$ to $\hat{M}^\dagger$, the optimal pairs of $\widetilde{M}^\dagger$ may be degraded while the (leveled) optimal pairs of $\widetilde{M}$ may be improved. Naturally, the idea of the proof is to **repair** $\hat{M}^\dagger$ into $\hat{M}^\ddagger \approx \hat{M}^\dagger$ with $\hat{M}^\ddagger \in \text{Cnf}_\varepsilon(M)$ by increasing the reward function at well-chosen pairs.

Given $\eta > 0$, we introduce the repaired model as

$$ \hat{M}_\eta^\ddagger \equiv \hat{M}^{\dagger\eta} \equiv (\mathcal{Z}, \hat{r}^\dagger + \eta e_{\mathcal{Z}^\dagger}, \hat{p}^\dagger) \quad \text{where} \quad \mathcal{Z}^\dagger := \mathcal{Z}^{**}(\widetilde{M}^\dagger) \setminus \mathcal{Z}^{**}(M), \quad (B.15) $$
i.e., as the copy of $\hat{M}^\dagger$ where the reward function is increased by $\eta$ at every pair of $\mathcal{Z}^\dagger$. The difficulty of the proof consists in choosing $\eta > 0$ correctly.

**Proof of Lemma B.11** We proceed with the Markov decision processes $\hat{M}, \tilde{M}, \tilde{M}^\dagger, \hat{M}^\dagger$ and $\hat{M}_\eta^\dagger = \hat{M}^\dagger \eta$ defined upstream. The proof is organized as follows.

We begin by the end. We show in (STEP 1) that if $\hat{M}^\dagger \eta$ is an $\varepsilon$-confusing model and if $\eta$ is small enough, then $C_\varepsilon(\mu, \hat{M})$ is upper bounded with respect to $C_\varepsilon(\mu, M)$; and that is the desired conclusion. The remaining steps consist in tuning $\eta > 0$. In (STEP 2), we show that $\hat{M}^\dagger \eta$ is well-defined if $\eta$ is small enough relatively to $M$ and $\varepsilon$. In (STEP 3) and (STEP 4), we detail how the optimal gain of $\hat{M}^\dagger \eta$ is influenced by the choice of $\eta$. The point is to derive, in (STEP 5), a lower bound $c(M, \varepsilon) > 0$ on $\eta$ that is sufficient to guarantee that $\hat{M}^\dagger \eta \in \text{Cnf}_\varepsilon(M)$. The final result is obtained by choosing $\eta = c(M, \varepsilon)$, that makes sure that $\hat{M}^\dagger \eta$ is well-defined, and to inject this expression in (STEP 1).

(STEP 1) For every $\eta > 0$ with $\eta < \min\{1 - \max(\tilde{r}^\dagger), \frac{1}{2} \max(\tilde{r}^\dagger)\}$ and $\hat{M}_\eta^\dagger \in \text{Cnf}_\varepsilon(M)$, we have

$$C_{\varepsilon}(\mu, \hat{M}) \le C_{\varepsilon}(\mu, \tilde{M}) + 2\beta_0 (C_{\varepsilon}(\mu, \tilde{M}) + 2\log(2e|\mathcal{S}|)) \quad (B.16)$$

where $\beta_0 := \max\{\max(\tilde{r}^\dagger)^{-1}\eta, \min(M)^{-1}\|\hat{M} - \tilde{M}\|^*\}$.

**Proof** Unfolding the definition of $C_\varepsilon(\mu, \hat{M})$, we have

$$C_{\varepsilon}(\mu, \hat{M}) := \inf_{\hat{M}' \in \text{Cnf}_{\varepsilon}(\hat{M})} \left\{ \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(\hat{M}(z) || \hat{M}'(z)) \right\} \\ \stackrel{(\dagger)}{\le} \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(\hat{M}(z) || \hat{M}_{\eta}^{\dagger}(z)) \\ \stackrel{(\ddagger)}{=} \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(\hat{p}(z) || \hat{p}_{\eta}^{\dagger}(z)) + \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(\hat{v}(z) || \hat{v}_{\eta}^{\dagger}(z))$$

where $(\dagger)$ uses that $\hat{M}_\eta^\dagger \in \text{Cnf}_\varepsilon(\hat{M})$. Both sums in $(\ddagger)$ are reworked using Lemma B.21.

We begin with the sum involving kernels. Note that for $\gamma := \min(\hat{p})^{-1}\|\tilde{p} - \hat{p}\|_\infty^*$, we have $(1 - \gamma)\hat{p}(s|z) \le \tilde{p}(s|z) \le (1 + \gamma)\hat{p}(s|z)$ for all $z \in \mathcal{Z}$ and $s \in \text{supp}(\tilde{p}(z))$. By assumption, we further have $\min(M)^{-1}\|\hat{M} - \tilde{M}\|^* < \frac{1}{2}$, so we can bound the variaitions of $\text{KL}(-||-)$ by invoking Lemma B.21 to obtain

$$\sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(\hat{p}(z) || \hat{p}_{\eta}^{\dagger}(z)) \stackrel{(\dagger)}{=} \sum_{z \notin \mathcal{Z}^{**}(M)} \mu(z) \text{KL}(\hat{p}(z) || \hat{p}^{\dagger}(z)) \\ \stackrel{(\ddagger)}{=} \sum_{z \notin \mathcal{Z}^{**}(M)} \mu(z) \text{KL}(\hat{p}(z) || \tilde{p}^{\dagger}(z)) \\ \stackrel{(\S)}{\le} (1 + \beta) \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(\tilde{p}(z) || \tilde{p}^{\dagger}(z)) + \beta \log(e|\mathcal{Z}|)$$

where $(\dagger)$ uses that $\hat{p}^{\dagger \eta} = \hat{p}^\dagger$ by definition and that $\hat{M}$ and $\hat{M}^{\dagger \eta}$ only differ outside of $\mathcal{Z}^{**}(M)$; $(\ddagger)$ uses that $\hat{p}^\dagger(z) = \tilde{p}^\dagger(z)$ for $z \notin \mathcal{Z}^{**}(M)$; and $(\S)$ introduces $\beta := 2 \min(M)^{-1}\|\hat{M} - \tilde{M}\|^*$ and invokes Lemma B.21.
Continuing with the sum involving rewards, we note that for $\gamma := \min(r)^{-1}\|\tilde{r} - r\|_{\infty}^{*}$, we have $(1 - \gamma)\hat{\nu}(i|z) \le \tilde{\nu}(i|z) \le (1 + \gamma)\hat{\nu}(i|z)$ for all $z \in \mathcal{Z}$ and $i = 0, 1$. Introduce the shorthand $\alpha := \max\{\max(\hat{r}^{\dagger})^{-1}\eta, \min(M)^{-1}\|\tilde{M} - \hat{M}\|^{*}\}$. Note that $\alpha < \frac{1}{2}$. We have

$$
\begin{align*}
\sum_{z \in \mathcal{Z}} \mu(z) \mathrm{KL}(\hat{\nu}(z) \| \hat{\nu}_{\eta}^{\dagger}(z)) &= \sum_{z \in \mathcal{Z}} \mu(z) \mathrm{kl}(\hat{r}(z) \| \hat{r}^{\dagger}(z) + \eta \mathbf{1}(z \in \mathcal{Z}^{\dagger})) \\
&\stackrel{(\dagger)}{=} \sum_{z \notin \mathcal{Z}^{**}(M)} \mu(z) \mathrm{kl}(\hat{r}(z) \| \hat{r}^{\dagger}(z) + \eta \mathbf{1}(z \in \mathcal{Z}^{\dagger})) \\
&\stackrel{(\ddagger)}{=} \sum_{z \notin \mathcal{Z}^{**}(M)} \mu(z) \mathrm{kl}(\hat{r}(z) \| \tilde{r}^{\dagger}(z) + \eta \mathbf{1}(z \in \mathcal{Z}^{\dagger})) \\
&\stackrel{(\S)}{\le} \sum_{z \notin \mathcal{Z}^{**}(M)} \mu(z) \mathrm{kl}\left(\hat{r}(z) \left\| \left(1 + \frac{\eta}{\max(\tilde{r}^{\dagger})}\right) \tilde{r}^{\dagger}(z) \right\|\right) \\
&\stackrel{(\S)}{\le} (1 + 2\alpha) \sum_{z \in \mathcal{Z}} \mu(z) \mathrm{KL}(\tilde{\nu}(z) \| \tilde{\nu}^{\dagger}(z)) + 2\alpha \log(2e)
\end{align*}
$$

where $(\dagger)$ follows from $\mathcal{Z}^{**}(M) \cap \mathcal{Z}^{\dagger} = \emptyset$; $(\ddagger)$ follows by construction of $\hat{M}^{\dagger}$; $(\S)$ follows by monotonicity of $v \mapsto \mathrm{kl}(\hat{r}(z) \| v)$ for $v \ge \hat{r}(z)$; and $(\S)$ follows by Lemma B.21.

Conclude by combining everything together, with $\beta \le \alpha$ and $1 \le |\mathcal{S}|$.

□

(STEP 2) We have

$$
\max(\hat{r}^{\dagger}) \le 1 - \exp\left(-\frac{\frac{C_{\varepsilon}(e, \tilde{M})}{\delta} + \log(2)}{1 - \max(r) - \|\tilde{r} - r\|_{\infty}}\right).
$$

In particular, $\hat{M}_{\eta}^{\dagger}$ is well-defined for all $\eta$ satisfying

$$
0 < \eta < \exp\left(-\frac{\frac{C_{\epsilon}(e, \tilde{M})}{\delta} + \log(2)}{1 - \max(r) - \|\tilde{r} - r\|_{\infty}}\right) - \|\hat{r} - \tilde{r}\|_{\infty}.
$$

**Proof** Using the bound on $C_{\epsilon}(e, \tilde{M})$ from Lemma B.8, we obtain

$$
\begin{align*}
C_{\epsilon}(\mu, \tilde{M}) &\ge \delta C_{\epsilon}(e, \tilde{M}) \\
&\ge \delta \max_{z \in \mathcal{Z}} \{\mathrm{KL}(\tilde{M}(z) \| \tilde{M}^{\dagger}(z))\} \\
&\ge \delta \max_{z \in \mathcal{Z}} \{\mathrm{KL}(\tilde{\nu}(z) \| \tilde{\nu}^{\dagger}(z))\} \\
&\ge \delta \max_{z \in \mathcal{Z}} \left\{-\mathrm{Ent}(\tilde{r}(z)) + \tilde{r}(z) \log\left(\frac{1}{\tilde{r}^{\dagger}(z)}\right) + (1 - \tilde{r}(z)) \log\left(\frac{1}{1 - \tilde{r}^{\dagger}(z)}\right)\right\}.
\end{align*}
$$

In particular, for all $z \in \mathcal{Z}$, $(1 - \tilde{r}(z)) \log\left(\frac{1}{1 - \tilde{r}^{\dagger}(z)}\right) \le \mathrm{Ent}(\tilde{r}(z)) + \frac{1}{\delta} C_{\epsilon}(e, M)$. We obtain the desired result by solving in $\hat{r}^{\dagger}(z)$ and using $\max(\tilde{r}) \le \max(r) + \|\tilde{r} - r\|_{\infty}$. $\square$

(STEP 3) Assume that $\|\tilde{M} - M\|^* < D(M)^{-1}$. Let $\tilde{\pi}^{\dagger}$ be a bias optimal policy of $\tilde{M}^{\dagger}$. For all $\pi \in \Pi^{*}(M)$, we have

$$
g^{\tilde{\pi}^{\dagger}}(\hat{M}_{\eta}^{\dagger}) \geq g^{*}(\tilde{M}^{\dagger}) - (1 + 2D(M)) \|\hat{M} - \tilde{M}\|^{*} e_{\mathcal{Z}} + \eta \cdot g^{\tilde{\pi}^{\dagger}}(e_{\mathcal{Z}^{\dagger}}, \hat{p}^{\dagger}); \quad (B.17)
$$
$$g^{\pi}(\hat{M}_{\eta}^{\ddagger}) \leq g^{*}(\widetilde{M}^{\dagger}) + (1 + 2D(M))\|\hat{M} - \widetilde{M}\|^{*}. \qquad (B.18)$$

**Proof** Because $\|\widetilde{M} - M\|^{*} < D(M)^{-1}$, we have $D(\widetilde{M}) \leq 2D(M)$ by Lemma D.7.

For $\pi \in \Pi$, the Cesàro-limit of $p_{\pi}^t$ is denoted $\mu_{\pi} := \lim T^{-1} \sum_{t=0}^{T-1} p_{\pi}^t$. We further denote $\hat{r}_{\pi}^{\dagger}$, $\hat{r}_{\pi}^{\dagger}$ and $\hat{r}_{\pi}^{\ddagger}$ the reward functions of $\pi$ in $\widetilde{M}^{\dagger}$, $\hat{M}^{\dagger}$ and $\hat{M}_{\eta}^{\dagger}$ respectively.

Starting with the first inequality, writing $\pi \equiv \tilde{\pi}^{\dagger}$ for short, we have

$$\begin{align*}
g^{\pi}(\hat{M}_{\eta}^{\ddagger}) &= \hat{\mu}_{\pi}^{\ddagger\eta} \cdot \hat{r}_{\pi}^{\ddagger\eta} \stackrel{(\ddagger)}{=} \hat{\mu}_{\pi}^{\dagger} \cdot (\hat{r}_{\pi}^{\dagger} + \eta e_{\mathcal{Z}^{\dagger}}) \\
&\stackrel{(\ddagger)}{\geq} g^{\pi}(\widetilde{M}) - \left(1 + \frac{1}{2}\mathrm{sp}(b^{\pi}(\widetilde{M}^{\dagger}))\right) \|\hat{M}^{\dagger} - \widetilde{M}^{\dagger}\|^{*} + \eta g^{\pi}(e_{\mathcal{Z}^{\dagger}}, \hat{p}^{\dagger}) \\
&\stackrel{(\ddagger)}{\geq} g^{\pi}(\widetilde{M}) - \left(1 + \frac{1}{2}\mathrm{sp}(b^{\pi}(\widetilde{M}^{\dagger}))\right) \|\hat{M} - \widetilde{M}\|^{*} + \eta g^{\pi}(e_{\mathcal{Z}^{\dagger}}, \hat{p}^{\dagger}) \\
&\stackrel{(\S)}{\geq} g^{\pi}(\widetilde{M}) - (1 + D(\widetilde{M})) \|\hat{M} - \widetilde{M}\|^{*} + \eta g^{\pi}(e_{\mathcal{Z}^{\dagger}}, \hat{p}^{\dagger}) \\
&\stackrel{(\S)}{\geq} g^{\pi}(\widetilde{M}) - (1 + 2D(M)) \|\hat{M} - \widetilde{M}\|^{*} + \eta g^{\pi}(e_{\mathcal{Z}^{\dagger}}, \hat{p}^{\dagger})
\end{align*}$$

where in $(\dagger)$ we wrote $e_{\mathcal{Z}^{\dagger}} := \sum_{z \in \mathcal{Z}^{\dagger}} e_z$; $(\ddagger)$ follows from Lemma D.8; $(\S)$ follows from $\mathrm{sp}(b^{\pi}(\widetilde{M}^{\dagger})) \leq D(\widetilde{M})$, because $\pi \equiv \tilde{\pi}^{\dagger}$ is a bias optimal in $\widetilde{M}^{\dagger}$ which is a critical model, hence $\mathrm{sp}(b^{\pi}(\widetilde{M}^{\dagger})) = \mathrm{sp}(b^{*}(\widetilde{M}^{\dagger})) \leq D(\widetilde{M})$ by Corollary B.5, assertion (1); and $(\S)$ follows from $D(\widetilde{M}) \leq 2D(M)$.

For the second inequality, first note that since $\|\widetilde{M} - M\| < \frac{1}{4}(\max\{1, D(\pi_u; M)\})^{-1}\Delta^g(M)$ where $\pi_u$ is the uniform policy, all gain optimal policies of $\widetilde{M}$ are gain optimal in $M$ by Lemma B.6. As $\|\widetilde{M} - M\|^{*} < \infty$, we further have $\widetilde{M} \sim M$ so $\mathcal{Z}^{**}(\widetilde{M}) \subseteq \mathcal{Z}^{**}(M)$. So, for all $\pi \in \Pi^{*}(M)$, we have

$$\begin{align*}
g^{\pi}(\hat{M}_{\eta}^{\ddagger}) &= \hat{\mu}_{\pi}^{\ddagger\eta} \cdot \hat{r}_{\pi}^{\ddagger\eta} \stackrel{(\ddagger)}{=} \hat{\mu}_{\pi} \cdot \hat{r}_{\pi} \\
&\stackrel{(\ddagger)}{\geq} g^{\pi}(\widetilde{M}) - \left(1 + \frac{1}{2}\mathrm{sp}(b^{*}(\widetilde{M}))\right) \|\hat{M} - \widetilde{M}\|^{*} \\
&\stackrel{(\S)}{\geq} g^{\pi}(\widetilde{M}) - (1 + D(\widetilde{M})) \|\hat{M} - \widetilde{M}\|^{*} \\
&\stackrel{(\S)}{\geq} g^{\pi}(\widetilde{M}) - (1 + 2D(M)) \|\hat{M} - \widetilde{M}\|^{*},
\end{align*}$$

where $(\dagger)$ follows from $\hat{M}^{\ddagger\eta} \sim \widetilde{M}$ and $\hat{M}^{\ddagger\eta}(z) = \hat{M}(z)$ for $z \in \mathcal{Z}^{**}(\widetilde{M})$; $(\ddagger)$ follows from the gain deviation inequality of Lemma D.8; $(\S)$ follows from Lemma B.20 and $(\S)$ follows from $D(\widetilde{M}) \leq 2D(M)$. $\square$

(STEP 4) Assume that $\hat{p}(s'|s, a) \geq \frac{1}{2}p(s'|s, a)$ for all $s, a, s'$. Writing $e := \sum_{s \in \mathcal{S}} e_s$, we have

$$g^{\tilde{\pi}^{\dagger}}(e_{\mathcal{Z}^{\dagger}}, \hat{p}^{\dagger}) \geq \frac{\mathrm{dmin}(\hat{p})^{|\mathcal{S}|-1}}{|\mathcal{S}|} e \geq \frac{\mathrm{dmin}(p)^{|\mathcal{S}|-1}}{2^{|\mathcal{S}|-1}|\mathcal{S}|} e.$$

**Proof** For conciseness, we write $\pi \equiv \tilde{\pi}^{\dagger}$.
Recall that (1) $\mathcal{Z}^{\dagger} = \mathcal{Z}^{**}(\tilde{M}^{\dagger}) \setminus \mathcal{Z}^{**}(M)$, (2) $\pi \equiv \tilde{\pi}^{\dagger}$ is a bias optimal policy of $\tilde{M}^{\dagger}$; and that (3) $\tilde{M}$ and $\tilde{M}^{\dagger}$ are identical on $\mathcal{Z}^{**}(M)$ by (B.13) and $\tilde{M}^{\dagger} \in \text{Cnf}_{\varepsilon}(\tilde{M})$. By mutual absolute continuity of $\tilde{M}^{\dagger}$ and $\hat{M}^{\dagger}$, recurrent components of $\pi$ are the same in $\tilde{M}^{\dagger}$ and $\hat{M}^{\dagger}$. They are denoted $\mathcal{Z}_1, \dots, \mathcal{Z}_m$. Let $\hat{\mu}_i^{\dagger}$ be the unique probability invariant measure of $\pi$ in $\hat{M}^{\dagger}$ that is supported in $\mathcal{Z}_i$. Given $s \in \mathcal{S}$, note that $g^{\tilde{\pi}^{\dagger}}(s; e_{\mathcal{Z}^{\dagger}}, \hat{p}^{\dagger})$ is a convex combination of $(\hat{\mu}_i^{\dagger} \cdot e_{\mathcal{Z}^{\dagger}})_{1 \le i \le m}$. Accordingly, it is enough to show that for all $i = 1, \dots, m$, we have

$$ \sum_{z \in \mathcal{Z}^{\dagger}} \hat{\mu}_{i}^{\dagger}(z) \geq \frac{\operatorname{dmin}(\hat{p})^{|\mathcal{S}|-1}}{|\mathcal{S}|}. \qquad (B.19) $$

We focus on showing (B.19) for an arbitrary $i \in \{1, \dots, m\}$.

Let $(s_0, a_0) \in \mathcal{Z}_i$ maximizing $\hat{\mu}_i^{\dagger}(s_0)$, where we use the writing shorthand $\hat{\mu}_i^{\dagger}(s) := \sum_{a \in \mathcal{A}(s)} \hat{\mu}_i^{\dagger}(s, a)$; In particular, $\hat{\mu}_i(s_0) \ge |\mathcal{S}|^{-1}$.

If $(s_0, a_0) \in \mathcal{Z}^{\dagger}$, there is nothing left to prove.

Let us assume otherwise, i.e., $(s_0, a_0) \notin \mathcal{Z}^{\dagger}$. Because $\pi$ is gain optimal in $\tilde{M}^{\dagger} \in \text{Cnf}(\tilde{M})$, it is not gain optimal in $M$, so $\mathcal{Z}_i \cap \mathcal{Z}^{\dagger} \neq \emptyset$. By considering all the paths in $\mathcal{Z}_i$ of length $n = 1, \dots, |\mathcal{S}|$ starting from $s_0$, at least one must hit $\mathcal{Z}^i \cap \mathcal{Z}^{\dagger}$. So, there exist $(s'_0, a'_0) \in \mathcal{Z}_i \cap \mathcal{Z}^{\dagger}$ together with a path $(s_1, a_1, \dots, s_n)$ of length $n \le |\mathcal{S}|$ such that $s_1 = s_0$, $s_n = s'_0$, $p(s_{j+1}|s_j, a_j) > 0$ and $(s_j, a_j) \in \mathcal{Z}_i \setminus \mathcal{Z}^{\dagger}$. In particular, $(s_j, a_j) \in \mathcal{Z}^{**}(\tilde{M})$ for $j \le n-1$, hence $\hat{p}^{\dagger}(s_j, a_j) = \hat{p}(s_j, a_j)$ by definition of $\hat{M}^{\dagger}$. We get

$$ \begin{aligned} \hat{\mu}_i^{\dagger}(s', a'_0) &\ge \pi(a'_0|s'_0) \left( \prod_{j=1}^{n-1} \pi(a_j|s_j) \hat{p}^{\dagger}(s_{j+1}|s_j, a_j) \right) \hat{\mu}_i^{\dagger}(s_0) \\ &\ge \pi(a'_0|s'_0) \left( \prod_{j=1}^{n-1} \pi(a_j|s_j) \hat{p}(s_{j+1}|s_j, a_j) \right) \hat{\mu}_i^{\dagger}(s_0) \stackrel{(\dagger)}{\ge} \frac{\operatorname{dmin}(\hat{p})^{n-1}}{|\mathcal{S}|} \stackrel{(\ddagger)}{\ge} \frac{\operatorname{dmin}(p)^{n-1}}{2^{n-1}|\mathcal{S}|} \end{aligned} $$

where $(\dagger)$ follows from the observation that $\pi$ is deterministic and $(\ddagger)$ that $\hat{p}(s'|s, a) \ge \frac{1}{2}p(s'|s, a)$ for all $s, a, s'$. Using that $n \le |\mathcal{S}|$, this shows (B.19) and concludes the proof. $\square$

(STEP 5) Assume that $\hat{p}(s'|s, a) \ge \frac{1}{2}p(s'|s, a)$ for all $s, a, s'$ and that $\|\tilde{M} - M\|^* < D(M)^{-1}$. We have $\hat{M}^{\ddagger} \in \text{Cnf}_{\varepsilon}(\hat{M})$ for every

$$ \eta > \frac{2^{|\mathcal{S}|}(1 + 2D(M))\|\hat{M} - \tilde{M}\|^*}{\operatorname{dmin}(p)^{|\mathcal{S}|-1}|\mathcal{S}|} $$

**Proof** By definition, $\hat{M}^{\ddagger} \in \text{Cnf}_{\varepsilon}(\hat{M})$ if, and only if (I) $\hat{M}^{\ddagger} = \hat{M}$ on $\mathcal{Z}_{\varepsilon}^{**}(M)$ and (II) $\hat{M}^{\ddagger}$ belongs to the confusing set of $\hat{M}$, i.e., $\Pi^{*}(\hat{M}^{\ddagger}) \cap \Pi^{*}(\hat{M}) = \emptyset$.

For (I), note that $\mathcal{Z}_{\varepsilon}^{**}(\hat{M}) = \mathcal{Z}^{**}(M)$ because $\|\hat{M} - M\|^* \le \alpha(M)^{-1}\varepsilon$, see (B.12); And $\hat{M}^{\ddagger} = \hat{M}$ on $\mathcal{Z}^{**}(M)$ by construction, see (B.14) and (B.15).

We derive a sufficient condition for (II) following (STEP 3) and (STEP 4). By Lemma B.3, $\hat{M}^{\ddagger} \in \text{Cnf}_{\varepsilon}(M)$ if, and only if $g^{*}(\hat{M}^{\ddagger}) > g^{*}(\hat{M})$.

Because $\|\hat{M} - M\|^* < \frac{1}{4}D(M)^{-1}\Delta^g(M)$, all gain optimal policies of $\hat{M}$ are gain optimal in $M$ by Lemma B.7. In (STEP 3) Equation (B.18), we provide a bound of $g^{\pi}(\hat{M}^{\ddagger})$ for all $\pi \in \Pi^{*}(M)$ and as a matter of fact, we have $g^{\pi}(\hat{M}^{\dagger}) = g^{\pi}(\hat{M})$ for all $\pi \in \Pi^{*}(M)$. Indeed,
$\hat{p} \sim p$ so the recurrent classes of policies are the same on $\hat{M}$ and $M$; And $\hat{p}^\dagger \gg \hat{p}$ so gain optimal policies of $M$ have their recurrent classes contained in $\mathcal{Z}^{**}(M)$ in $\hat{M}^{\ddagger\eta}$, on which $\hat{M}^{\ddagger\eta} = \hat{M}$. Together with (B.18), we find:

$$g^*(\hat{M}) \leq g^*(\widetilde{M}^\dagger) + (1 + 2D(M)) \|\hat{M} - \widetilde{M}\|^*.$$

So, by (STEP 3) Equation (B.17), $\pi^\dagger$ satisfies $g^{\pi^\dagger}(\hat{M}^{\ddagger\eta}) > g^*(\hat{M})$ when

$$\eta > \frac{2(1 + 2D(M))\|\hat{M} - \widetilde{M}\|^*}{g^{\pi^\dagger}(e_{\mathcal{Z}^\dagger}, \hat{p}^\dagger)} \stackrel{(\dagger)}{\ge} \frac{2^{|\mathcal{S}|}(1 + 2D(M))\|\hat{M} - \widetilde{M}\|^*}{\mathrm{dmin}(p)^{|\mathcal{S}|-1}|\mathcal{S}|}$$

in particular, where $(\dagger)$ follows from (STEP 4). This concludes the proof. $\square$

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

We may now conclude. We proceed by upper bounding the information value of $\hat{M}$ with respect to the information value of $\widetilde{M}$. First, we pick some $\eta > 0$ such that (I) $\hat{M}^{\ddagger\eta}$ is well-defined and (II) $\hat{M}^{\ddagger\eta} \in \mathrm{Cnf}_\epsilon(M)$. (STEP 2) and (STEP 5) provide sufficient conditions so that (I) and (II) are satisfied respectively. For the conditions given by (STEP 2) and (STEP 5) to be compatible, we need

$$\frac{2^{|\mathcal{S}|}(1 + 2D(M))\|\hat{M} - \widetilde{M}\|^*}{\mathrm{dmin}(p)^{|\mathcal{S}|-1}|\mathcal{S}|} < \exp\left(-\frac{\frac{C_\epsilon(e, \widetilde{M})}{\delta} + \log(2)}{1 - \max(r) - \|\widetilde{r} - r\|_\infty}\right) - \|\hat{r} - \widetilde{r}\|_\infty.$$

Provided that $\|\widetilde{r} - r\|_\infty \le \frac{1}{2}(1 - \max(r))$ and using the upper bound $\|\hat{r} - \widetilde{r}\|_\infty \le \|\hat{M} - \widetilde{M}\|^*$, we solve the above in $\|\hat{M} - \widetilde{M}\|^*$ and find the sufficient condition:

$$\|\hat{M} - \widetilde{M}\|^* < \exp\left(-\frac{2\left(\frac{C_\epsilon(e, \widetilde{M})}{\delta} + \log(2)\right)}{1 - \max(r)} + \log\left(\frac{\mathrm{dmin}(p)^{|\mathcal{S}|-1}|\mathcal{S}|}{\mathrm{dmin}(p)^{|\mathcal{S}|-1}|\mathcal{S}| + 2^{|\mathcal{S}|}(1 + 2D(M))}\right)\right).$$

Together with the condition $\hat{M}, \widetilde{M} \in \mathcal{M}_\epsilon$ as given by (B.11), we retrieve indeed a condition in the form as given by (B.10) in Lemma B.11. Conclude with (STEP 1) by taking $\eta = \mathrm{dmin}(p)^{1-|\mathcal{S}|} |\mathcal{S}|^{-1} 2^{|\mathcal{S}|} (1 + 2D(M)) \|\hat{M} - \widetilde{M}\|^*$ as allowed by (STEP 5), to obtain an bound of the form

$$C_{\epsilon}(\mu, \hat{M}) \le C_{\epsilon}(\mu, \widetilde{M}) + \exp(\beta(M)) \|\hat{M} - \widetilde{M}\|^* \quad (B.20)$$

where $\beta(M)$ is polynomial in $|\mathcal{Z}|, D(M), \mathrm{dmin}(M), \Delta^q(M)$ and $C(e, M)$.

Take $M = \hat{M}, M' = \widetilde{M}$ to upper bound the information value of $M$ relatively to $M'$, and $M = \widetilde{M}, M' = \hat{M}$ to lower bound the information value of $M$ relatively to $M'$. $\blacksquare$

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

## B.3 Properties of the regularized lower bound

In this section, we study the properties of the regularized lower bound $K_{\bar{\epsilon}}(M)$ (Definition 12) which is given as the solution of the optimization problem below:

$$\min \sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z; M) + \epsilon_{\mathrm{conv}} \|\mu\|_2^2 \quad \text{s.t.} \quad \begin{cases} \mu \in \mathrm{Inv}(\epsilon_{\mathrm{unif}}; M) \\ \inf_{M^\dagger \in \mathrm{Cnf}(\epsilon_{\mathrm{lvl}}; M)} \sum_{z \in \mathcal{Z}} \mu(z) \mathrm{KL}(M(z) || M^\dagger(z)) \ge 1 \end{cases}$$
where $\bar{\epsilon} = (\epsilon_{\text{lvl}}, \epsilon_{\text{unif}}, \epsilon_{\text{conv}}) \in \mathbb{R}_+^3$ is the regularization hyperparameter. The goal of this section is to show that the above has a solution $\mu_{\bar{\epsilon}}^*(M)$ called an $\bar{\epsilon}$-optimal exploration measures, and study the continuity and convergence properties of $K_{\bar{\epsilon}}(M)$ and $\mu_{\bar{\epsilon}}^*(M)$ as $\bar{\epsilon}$ and $M$ vary.

**Outline.** We begin by providing a simple bound on $K(M)$ and $K_{\bar{\epsilon}}(M)$ in Appendix B.3.1. In Appendix B.3.2, we show that $\bar{\epsilon}$-optimal exploration measures exist, even when $\bar{\epsilon} = 0$, and that $\mu_{\bar{\epsilon}}^*$ is unique when the convexification $\epsilon_{\text{conv}}$ is strict. The remaining of the appendix is dedicated to the continuity properties of $K_{\bar{\epsilon}}(M)$ and $\mu_{\bar{\epsilon}}^*(M)$. In Appendix B.3.3, we present an alternative way of writing $K_{\bar{\epsilon}}(M)$ that is adequate for that purpose. In Appendix B.3.4, we show that the sequence of $\bar{\epsilon}$-optimal exploration measures ($\mu_{\bar{\epsilon}}^*$) converges to a special optimal exploration $\mu^*$ when $\bar{\epsilon} \to 0$ at the adequate rate (Proposition B.16). In Appendix B.3.5, we show that as $\bar{\epsilon} \to 0$, we have $K_{\bar{\epsilon}}(M) \downarrow K(M)$ (Proposition B.17), meaning that the regularized lower bound can approximates the true lower bound with arbitrary precision as the regularization vanishes. Then, in Appendix B.3.6, we show that if $\|M' - M\|^*$ is small relatively to $\bar{\epsilon}$, then $K_{\bar{\epsilon}}(M')$ is close to $K_{\bar{\epsilon}}(M)$. Qualitatively, it means that

$$K(M) = \lim_{\bar{\epsilon} \to 0} \lim_{\|M' - M\|^* \to 0} K_{\bar{\epsilon}}(M'). \qquad (B.21)$$

The precise rates of convergence in (B.21) are given in Proposition B.18.

### B.3.1 A SIMPLE BOUND ON THE REGRET LOWER BOUND

In this paragraph, we provide an upper-bound of $K(M)$ of order $|\mathcal{Z}|D(M)^3\Delta^g(M)^{-2}$, see Theorem B.12 where $D(M)$ is the diameter and $\Delta^g(M)$ is the gain-gap (Definition A.4). Our bound is of the same kind as (Auer et al., 2009, Theorem 4), that indirectly provide a bound of order $|\mathcal{Z}||S|D(M)^2\Delta^g(M)^{-1}$ by showing that UCRL2 has regret growing as $|\mathcal{Z}||S|D(M)^2\Delta^g(M)^{-1}\log(T)$ in the asymptotic. Their bound is better than our own in most cases—as soon as $|S| \le D^2(M)\Delta^g(M)^{-1}$ in fact, but requires the construction and the analysis of a complete learning algorithm.

Overall, we believe that bounds on $K(M)$ in terms of $D(M)$ and $\Delta^g(M)$ can be improved up to $|\mathcal{Z}|D(M)^2\Delta^g(M)^{-1}$. This is left for future work.

**Theorem B.12 (Simple upper bound of $K(M)$).** Let $\mathcal{M}$ be an ambient space with Bernoulli rewards (Assumption 3). For every communicating model $M \equiv (\mathcal{Z}, p, \nu) \in \mathcal{M}$, the regret lower bound is upper-bounded as

$$K(M) \le \frac{16|\mathcal{Z}|D(M)^3}{\Delta^g(M)^2}.$$

where $D(M)$ is the diameter of $M$ (Assumption 2) and $\Delta^g(M)$ its gain-gap (Definition A.4). In particular, $K(M) < \infty$.

**Proof** Let $\pi \in \Pi^{\text{SR}}$ the fast covering policy provided by Lemma A.4, of which the unique probability invariant measure satisfies $\min(\mu^\pi) \ge |\mathcal{Z}|^{-1}D(M)^{-1}$. By combining Lemma B.9 and Lemma B.8, the information value of $\mu$ is lower bounded as

$$C(\mu^\pi, M) \ge \frac{C(e, M)}{|\mathcal{Z}|D(M)} \ge \frac{\Delta^g(M)^2}{16|\mathcal{Z}|D(M)^3}. \qquad (B.22)$$
Using the formulation of the regret lower bound in terms of policies (Proposition 2, see (9)), we deduce that

$$K(M) \leq \frac{g^*(M) - g^\pi(M)}{C(\mu^\pi, M)} \stackrel{(\dagger)}{\leq} \frac{16|\mathcal{Z}|D(M)^3}{\Delta^g(M)^2}$$

where $(\dagger)$ invokes (B.22) and uses that rewards are $[0, 1]$, so that $g^*(M) - g^\pi(M) \leq 1$. ■

### B.3.2 EXISTENCE OF OPTIMAL AND $\bar{\epsilon}$-OPTIMAL EXPLORATION MEASURES

In this paragraph, we show that $K(M)$ and $K_{\bar{\epsilon}}(M)$ are achieved by invariant measures. More specifically, we show that there exists $\mu^* \in \text{Inv}(M)$ with $\sum_{z \in \mathcal{Z}} \mu(z)\text{KL}(M(z) || M^\dagger(z)) \geq 1$ for all $M^\dagger \in \text{Cnf}(M)$ and $\sum_{z \in \mathcal{Z}} \mu^*(z)\Delta^*(z) = K(M)$—with a similar result for the regularized lower bound. This shows that the concepts of optimal exploration measure (Section 2.2.2) and $\bar{\epsilon}$-optimal exploration measure (Section 4.3) are well-defined.

**Theorem B.13 (Existence of optimal exploration measures).** Let $\mathcal{M}$ be an arbitrary ambient space of Markov decision processes. Let $M \in \mathcal{M}$ be a communicating model. Then the infemum of (8) is a minimum, i.e., $K(M)$ is equal to

$$\min \left\{ \sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z) : \mu \in \text{Inv}(M) \text{ and } \inf_{M^\dagger \in \text{Cnf}(M)} \left\{ \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^\dagger(z)) \right\} \geq 1 \right\}.$$

**Proof** The idea of the proof is to write $K(M)$ as the solution of an optimization problem over a compact region. This task is not that easy because invariant measures contain irrelevant information; For instance, it can be shown that if $\mu^* \in \text{Inv}(M)$ is an optimizer of (8) achieving $K(M)$, then for every gain optimal unichain policy $\pi^*$ and every of its invariant measure $\mu' \in \text{Inv}(\pi^*; M)$, the invariant measure $\mu^* + \mu'$ is also an optimizer of (8). This makes the set of optimizers of (8) unbounded.

To remove the irrelevant information contained by invariant measures, we write $K(M)$ in an alternative form.

Let $\Pi_u$ be the set of policies that are unichain in $M$ and denote $\Pi_u^- := \Pi_u \setminus \Pi^*(M)$. We denote $\mu_\pi$ the unique probability invariant measure of $\pi \in \Pi_u$ in $M$. By Proposition A.10, every invariant measure $\mu \in \text{Inv}(M)$ can be written as $\mu = \sum_{\pi \in \Pi_u} \lambda_\pi \mu_\pi$ for some $(\lambda_\pi) \in \mathbb{R}_+^{\Pi_u}$. Now, note the information value of $\mu = \sum_{\pi \in \Pi_u} \lambda_\pi \mu_\pi$ satisfies

$$C(\mu, M) := \inf_{M^\dagger \in \text{Cnf}(M)} \left\{ \sum_{\pi \in \Pi_u} \sum_{z \in \mathcal{Z}} \lambda_\pi \mu_\pi(z) \text{KL}(M(z) || M^\dagger(z)) \right\} \\ \stackrel{(\dagger)}{=} \inf_{M^\dagger \in \text{Cnf}(M)} \left\{ \sum_{\pi \in \Pi_u^-} \sum_{z \in \mathcal{Z}} \lambda_\pi \mu_\pi(z) \text{KL}(M(z) || M^\dagger(z)) \right\}$$

where $(\dagger)$ holds following from the observation that $\text{supp}(\mu_\pi) \subseteq \mathcal{Z}^{**}(M)$ for all $\pi \in \Pi_u \cap \Pi^*(M)$ and that every confusing model coincide with $M$ on $\mathcal{Z}^{**}(M)$ by definition. Accordingly, in the optimization problem of (8), the optimization region $\text{Inv}(M)$ can be changed as

$K(M)$
$$ = \inf_{\lambda \in \mathbf{R}_+^{\Pi_u^-}} \left\{ \sum_{\pi \in \Pi_u^-} \sum_{z \in \mathcal{Z}} \lambda_{\pi} \mu_{\pi}(z) \Delta^*(z) : \inf_{M^{\dagger} \in \text{Cnf}(M)} \left\{ \sum_{\pi \in \Pi_u^-} \sum_{z \in \mathcal{Z}} \lambda_{\pi} \mu_{\pi}(z) \text{KL}(M(z) || M^{\dagger}(z)) \right\} \ge 1 \right\} \\ = \inf_{\lambda \in \mathbf{R}_+^{\Pi_u^-}} \left\{ \sum_{\pi \in \Pi_u^-} \lambda_{\pi} (g^* - g^{\pi}) : \inf_{M^{\dagger} \in \text{Cnf}(M)} \left\{ \sum_{\pi \in \Pi_u^-} \sum_{z \in \mathcal{Z}} \lambda_{\pi} \mu_{\pi}(z) \text{KL}(M(z) || M^{\dagger}(z)) \right\} \ge 1 \right\} $$

where $(\dagger)$ follows from the observation that $\sum_{z \in \mathcal{Z}} \mu_{\pi}(z) \Delta^*(z) = g^* - g^{\pi}$ for every unichain policy $\pi \in \Pi_u$, which can be shown using that $\mathbf{E}_s^{\pi}[\sum_{t=1}^T \mathbf{1}(Z_t = z)] = T\mu_{\pi}(z) + O(1)$ for all $z \in \mathcal{Z}$ and initial state $s \in \mathcal{S}$.

We now restrict $(\mathbf{R}_+)^{\Pi_u^-}$ to a compact sub-region as follows. By Theorem B.12, we know that $K(M) \le 16|\mathcal{Z}|D(M)^3\Delta^g(M)^{-2}$. As every policy $\pi \in \Pi_u^-$ is sub-optimal, we have $g^* - g^{\pi} \ge \Delta^g(M)$. So, if $(\lambda_{\pi}) \in (\mathbf{R}_+)^{\Pi_u^-}$ is such that $\|\lambda\|_{\infty} > 16|\mathcal{Z}|D(M)^3\Delta^g(M)^{-3}$, we know that the invariant measure $\sum_{\pi \in \Pi_u^-} \lambda_{\pi} \mu_{\pi}$ does not achieve $K(M)$. In other words, setting

$$ \mathcal{F} := \left\{ \lambda \in (\mathbf{R}_+)^{\Pi_u^-} : \begin{array}{l} \|\lambda\|_{\infty} \le 16|\mathcal{Z}|D(M)^3\Delta^g(M)^{-3} \text{ and} \\ \forall M^{\dagger} \in \text{Cnf}(M), \sum_{\pi \in \Pi_u^-} \sum_{z \in \mathcal{Z}} \lambda_{\pi} \mu_{\pi}(z) \text{KL}(M(z) || M^{\dagger}(z)) \ge 1 \end{array} \right\} $$

we have

$$ K(M) = \inf_{\lambda \in \mathcal{F}} \left\{ \sum_{\pi \in \Pi_u^-} \lambda_{\pi} (g^* - g^{\pi}) \right\}. \qquad (B.23) $$

Because $\mathcal{F}$ is compact and that the objective function in (B.23) is continuous, the infemum of (B.23) is a minimum. Let $\lambda^* \in \mathcal{F}$ achieving that minimum. The invariant measure $\mu^* := \sum_{\pi \in \Pi_u^-} \lambda_{\pi}^* \mu_{\pi}$ is an optimal invariant measure of $M$, concluding the proof. ■

With the same proof, the result is generalized to $K_{\bar{\epsilon}}(M)$.

**Theorem B.14** (Existence of $\bar{\epsilon}$-optimal exploration measures). Let $\mathcal{M}$ be an arbitrary ambient space of Markov decision processes. Let $M \in \mathcal{M}$ be a communicating model and $\bar{\epsilon} \equiv (\epsilon_{\text{lvl}}, \epsilon_{\text{unif}}, \epsilon_{\text{conv}}) \in \mathbf{R}_+^3$ be a regularization hyperparameter. Then the infemum of the optimization problem associated to $K_{\bar{\epsilon}}(M)$ (see Definition 12) is a minimum, i.e., $K_{\bar{\epsilon}}(M)$ is equal to

$$ \min \sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z) + \epsilon_{\text{conv}} \|\mu\|_2^2 \quad \text{s.t.} \quad \left\{ \begin{array}{l} \mu \in \text{Inv}(\epsilon_{\text{unif}}; M), \quad \text{and} \\ \inf_{M^{\dagger} \in \text{Cnf}(\epsilon_{\text{lvl}}; M)} \left\{ \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^{\dagger}(z)) \right\} \ge 1. \end{array} \right. $$

Moreover, if the convexification is strict with $\epsilon_{\text{conv}} > 0$, then the minimum $\mu_{\bar{\epsilon}}^*$ is unique.

**Proof** The existence of the minimum is shown similarly to Theorem B.13. The uniqueness of $\mu_{\bar{\epsilon}}^*$ is guaranteed by strong convexity of the objective function. ■
### B.3.3 A CONVENIENT FORM FOR THE $\bar{\epsilon}$-REGULARIZED LOWER BOUND

To prepare the analysis of the continuity properties of $K_{\bar{\epsilon}}(M)$ and $\mu_{\bar{\epsilon}}^*(M)$, we start by rewriting the $\bar{\epsilon}$-regularized lower bound with respect to information values as follows:

$$ K_{\bar{\epsilon}}(M) = \inf_{\mu \in \mathcal{I}(\epsilon_{\text{unif}}; M)} \left\{ \frac{\sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z; M)}{C_{\epsilon \text{lvl}}(\mu, M)} + \frac{\epsilon_{\text{conv}} \|\mu\|_2^2}{C_{\epsilon \text{lvl}}(\mu, M)^2} \right\} \quad (B.24) $$

where $\mathcal{I}(\epsilon_{\text{unif}}; M) := \text{Inv}(\epsilon_{\text{unif}}; M) \cap \mathcal{P}(\mathcal{Z})$ is the space of $\epsilon_{\text{unif}}$-uniform probability invariant measures of $M$. The issue in (B.24) is that Bellman gaps $\Delta^*(z; M)$ are discontinuous in $M$ even regarding the support-aware norm $\|\cdot\|^*$. A simple example of discontinuity point of $\Delta^*(-)$ is provided in Figure 4.

<figure><img src="image_12.png" /><figcaption>Figure 4: A discontinuity of $\Delta^*(M)$. A class of Bernoulli reward models with deterministic transitions parameterized by $\theta \in \Theta \equiv [-\frac{1}{2}, \frac{1}{2}]$. Arrows are choices of actions that deterministically lead to the pointed state and labels are mean rewards.</figcaption></figure>

This discontinuity is actually artificial. If $\Delta^*(-)$ is discontinuous indeed, the inner product between an invariant measure and the Bellman gaps $\sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z; M)$ is not, because it can be rewritten as $\sum_{z \in \mathcal{Z}} \mu(z)(g^*(M) - r(z))$ using Lemma B.15 below, and $g^* - r$ can be shown to be a continuous function of $M$.

**Lemma B.15.** For every communicating Markov decision process $M \equiv (\mathcal{Z}, p, r)$ and all invariant measure $\mu \in \text{Inv}(M)$, we have

$$ \sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z; M) = \sum_{z \in \mathcal{Z}} \mu(z)(g^*(M) - r(z)). $$

**Proof** Let $\mu \in \text{Inv}(M)$. This follows from the direct computation:

$$ \begin{align*} & \sum_{z \in \mathcal{Z}} \mu(z)(g^*(M) - r(z)) \\ & \stackrel{(\dagger)}{=} \sum_{z \equiv (s,a) \in \mathcal{Z}} \mu(z)(\Delta^*(z; M) + (e_s - p(z))b^*(M)) \\ & = \sum_{z \in \mathcal{Z}} \mu(z)\Delta^*(z; M) + \sum_{s \in \mathcal{S}} b^*(s; M) \sum_{a \in \mathcal{A}(s)} \mu(s, a) - \sum_{s' \in \mathcal{S}} b^*(s'; M) \sum_{z \in \mathcal{Z}} \mu(z)p(s'|z) \\ & \stackrel{(\ddagger)}{=} \sum_{z \in \mathcal{Z}} \mu(z)\Delta^*(z; M) + \sum_{s \in \mathcal{S}} b^*(s; M) \sum_{a \in \mathcal{A}(s)} \mu(s, a) - \sum_{s' \in \mathcal{S}} b^*(s'; M) \sum_{a' \in \mathcal{A}(s')} \mu(s', a') \\ & = \sum_{z \in \mathcal{Z}} \mu(z)\Delta^*(z; M) \end{align*} $$

where $(\dagger)$ follows by definition of $\Delta^*(z; M)$ and $(\ddagger)$ holds because $\mu \in \text{Inv}(M)$. $\blacksquare$

<figure><img src="image_13.png" /></figure>
### B.3.4 CONVERGENCE OF REGULARIZED OPTIMAL EXPLORATION MEASURES

In this section, we provide convergence guarantees for the unique solution $\mu_{\bar{\epsilon}}^*$ of the regularized lower bound $K_{\bar{\epsilon}}(M)$. Informally, we show that the optimal $\bar{\epsilon}$-regularized exploration measure $\mu_{\bar{\epsilon}}^*$ converges to the optimal exploration measure $\mu^*$ that further minimized the $l_2$-norm, provided that $\epsilon_{\text{unif}}/\epsilon_{\text{conv}} + \epsilon_{\text{conv}} \to 0$, see Proposition B.16 below. Under the same conditions, this shows that the optimal $\bar{\epsilon}$-regularized exploration policy converges to a unique randomized policy when $\mu^*$ puts positive mass on every state $\sum_{a \in A(s)} \mu^*(s, a) > 0$ for all $s \in S$—or, equivalently, if there exists an optimal exploration policy that is state-recurrent.

**Proposition B.16.** Let $M \in \mathcal{M}$ be a communicating Markov decision process. Given a regularization hyperparameter $\bar{\epsilon} \equiv (\epsilon_{\text{lvl}}, \epsilon_{\text{unif}}, \epsilon_{\text{conv}})$, we write $\mu_{\bar{\epsilon}}^*(M)$ the optimal $\bar{\epsilon}$-regularized exploration measure. Let $\mu^* \in \text{Inv}(M)$ be the (unique) optimizer of $K(M)$ as in (8) that further minimizes $\|\mu\|_2^2$ among optimizers. There exists a function $\psi: \mathbf{R}_+ \to \mathbf{R}_+$ such that

$$ \forall \bar{\epsilon}, \quad \|\mu_{\bar{\epsilon}}^* - \mu^*\|_2^2 \le \psi\left(\frac{\epsilon_{\text{unif}}}{\epsilon_{\text{conv}}} + \epsilon_{\text{conv}} + \epsilon_{\text{lvl}}\right) \quad (B.25) $$

with $\psi(x) = O(x)$ as $x \to 0$.

Therefore, Proposition B.16 shows that one optimal exploration measure of $M$ is a bit more special than the others regarding our regularization scheme, that we call the **central** optimal exploration measure, see Definition B.3. We use the terminology “central” for that measure maximizes the support over optimal exploration measures.

**Definition B.3 (Central measure).** The **central** optimal exploration probability measure of $M$ is the unique optimal exploration probability measure $\mu^* \in \mathcal{P}(\mathcal{Z})$ that achieves $K(M)$ and that further minimizes $\|\mu\|_2^2$ among optimizers of $K(M)$.

**Proof** For $\bar{\epsilon} \ge 0$, we write $f_{\bar{\epsilon}}(\mu) := \sum_{z \in \mathcal{Z}} \mu(z)\Delta^*(z; M) + \epsilon_{\text{conv}}\|\mu\|_2^2$ the objective function and $\mathcal{F}_{\bar{\epsilon}}$ the feasible set associated to $K_{\bar{\epsilon}}(M)$ seen as an optimization problem, i.e.,

$$ \mathcal{F}_{\bar{\epsilon}} := \left\{ \mu \in \text{Inv}(\epsilon_{\text{unif}}; M) : \forall M^{\dagger} \in \text{Cnf}(\epsilon_{\text{lvl}}; M), \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^{\dagger}(z)) \ge 1 \right\}. $$

Assume throughout that $\epsilon_{\text{lvl}}$ is small enough so that $\text{Cnf}(\epsilon_{\text{lvl}}; M) = \text{Cnf}(M)$, say $\epsilon_{\text{lvl}} < \Delta^g(M)$ for e.g., see Proposition 3.

Let $\tilde{\mu}_{\bar{\epsilon}}^*$ be the optimizer of $f_{\bar{\epsilon}}$ in $\mathcal{F}_0$ and let $\tilde{\mu}_{\bar{\epsilon}}'$ be its projection on $\mathcal{F}_{\bar{\epsilon}}$. By Theorem A.6 and provided that $\epsilon_{\text{unif}} < |\mathcal{Z}|^{-1}D(M)^{-1}$, we have

$$ \|\tilde{\mu}_{\bar{\epsilon}}' - \tilde{\mu}_{\bar{\epsilon}}^*\|_{\infty} \le |\mathcal{Z}| D(M) \epsilon_{\text{unif}} \|\tilde{\mu}_{\bar{\epsilon}}^*\|_1. \quad (B.26) $$

For conciseness, denote $\alpha := |\mathcal{Z}|D(M)$. Now, we have

$$ \begin{aligned} & f_{\bar{\epsilon}}(\mu_{\bar{\epsilon}}^*) \\ & \stackrel{(\dagger)}{\ge} \sum_{z \in \mathcal{Z}} \tilde{\mu}_{\bar{\epsilon}}^*(z) \Delta^*(z) + \epsilon_{\text{conv}} \|\tilde{\mu}_{\bar{\epsilon}}^*\|_2^2 \\ & \stackrel{(\ddagger)}{\ge} \sum_{z \in \mathcal{Z}} \tilde{\mu}_{\bar{\epsilon}}'(z) \Delta^*(z) + \epsilon_{\text{conv}} \|\tilde{\mu}_{\bar{\epsilon}}'\|_2^2 - \alpha \epsilon_{\text{unif}} \|\tilde{\mu}_{\bar{\epsilon}}'\|_1 (\|\Delta^*\|_1 + \epsilon_{\text{conv}}(2\|\tilde{\mu}_{\bar{\epsilon}}^*\|_1 + \alpha \epsilon_{\text{unif}} |\mathcal{Z}| \|\tilde{\mu}_{\bar{\epsilon}}^*\|_1)) \end{aligned} $$
$$ \stackrel{(\S)}{\ge} f_{\bar{\epsilon}}(\mu_{\bar{\epsilon}}^*) + \epsilon_{\text{conv}} \|\tilde{\mu}_{\bar{\epsilon}}' - \mu_{\bar{\epsilon}}^*\|_2^2 - \alpha \epsilon_{\text{unif}} \|\tilde{\mu}_{\bar{\epsilon}}'\|_1 \left( \|\Delta^*\|_1 + \epsilon_{\text{conv}}(2\|\tilde{\mu}_{\bar{\epsilon}}^*\|_1 + \alpha \epsilon_{\text{unif}} |\mathcal{Z}| \|\tilde{\mu}_{\bar{\epsilon}}^*\|_1) \right) $$

where (†) follows by definition of $\tilde{\mu}_{\bar{\epsilon}}^*$ and $\mu_{\bar{\epsilon}}^* \in \mathcal{F}_{\bar{\epsilon}} \subseteq \mathcal{F}_0$; (‡) follows from (B.26) and a bit of algebra; and (§) holds because $f_{\bar{\epsilon}}(\mu) \ge f_{\bar{\epsilon}}(\mu_{\bar{\epsilon}}^*) + \epsilon_{\text{conv}} \|\mu - \mu_{\bar{\epsilon}}^*\|_2^2$ for all $\mu \in \mathcal{F}_{\bar{\epsilon}}$. Together with (B.26), we conclude that

$$ \|\tilde{\mu}_{\bar{\epsilon}}^* - \mu_{\bar{\epsilon}}^*\| \le \frac{\epsilon_{\text{unif}} \|\tilde{\mu}_{\bar{\epsilon}}^*\|_1}{1/\alpha} + \frac{\epsilon_{\text{unif}} \|\tilde{\mu}_{\bar{\epsilon}}'\|_1}{\epsilon_{\text{conv}}/\alpha} \left( \|\Delta^*\|_1 + \epsilon_{\text{conv}} \left( 2\|\tilde{\mu}_{\bar{\epsilon}}^*\|_1 + \frac{\epsilon_{\text{unif}} |\mathcal{Z}| \|\tilde{\mu}_{\bar{\epsilon}}^*\|_1}{1/\alpha} \right) \right) \quad (B.27) $$

Note that $\|\tilde{\mu}_{\bar{\epsilon}}'\|_1 = \|\tilde{\mu}_{\bar{\epsilon}}^*\|_1 + O(\epsilon_{\text{unif}})$ by (B.26).

We finish the proof by showing that $\mu^* = \tilde{\mu}_{\bar{\epsilon}}^*$ when $\epsilon_{\text{conv}}$ is small enough.

In the remaining of the proof, we more simply write $\epsilon$ in place of $\epsilon_{\text{conv}}$. Consider the relaxation of the optimization problem $\min_{\mu \in \mathcal{F}_0} \|\mu\|_2^2$ s.t. $f_0(\mu) \le K(M)$ given by

$$ \min_{\mu \in \mathcal{F}_0} \|\mu\|_2^2 + \lambda(f_0(\mu) - K(M)) $$

for $\lambda \ge 0$. Note that Slater's condition is satisfied. Indeed, the constraints "$\mu \in \text{Inv}(M)$" and "$f_0(\mu) = K(M)$" are polytopes, while the constraint "$\sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^{\dagger}(z)) \ge 1$ for all $M^{\dagger} \in \text{Cnf}(M)$" is equivalently written in the form of "$\psi(\mu) \le 0$" where $\psi(\mu) := 1 - \sup_{M^{\dagger} \in \text{Cnf}(M)} \sum_{z \in \mathcal{Z}} \mu(z) \text{KL}(M(z) || M^{\dagger}(z))$ that is convex. By taking $\mu_0 \in \mathcal{P}(\mathcal{Z})$ the unique probability invariant measure of the uniform policy $\pi_0(a|s) := |\mathcal{A}(s)|^{-1}$ and considering $\lambda_0 \mu_0 \in \text{Inv}(M)$ for $\lambda_0 > 0$ large enough such that $\sum_{z \in \mathcal{Z}} \lambda_0 \mu_0(z) \text{KL}(M(z) || M^{\dagger}(z)) \ge 2$ for all $M^{\dagger} \in \text{Cnf}(M)$, we obtain a point in the relative interior of the feasible region $\mathcal{F}_0$. So strong duality holds, see (Boyd et al., 2004, §5.2.3). We deduce that

$$ \max_{\lambda \ge 0} \min_{\mu \in \mathcal{F}_0} \left( \|\mu\|_2^2 + \lambda(f_0(\mu) - K(M)) \right) = \min_{\mu \in \mathcal{F}_0} \max_{\lambda \ge 0} \left( \|\mu\|_2^2 + \lambda(f_0(\mu) - K(M)) \right). \quad (B.28) $$

By definition, $\mu^*$ is the unique solution of $\min_{\mu \in \mathcal{F}_0} \|\mu\|_2^2$ s.t. $f_0(\mu) \le K(M)$. Let $\lambda^* \equiv \frac{1}{\epsilon^*}$ be the associated Lagrange multiplier. By definition again, $\tilde{\mu}_{\bar{\epsilon}}^*$ is the unique solution of $\min_{\mu \in \mathcal{F}_0} f_0(\mu) + \epsilon \|\mu\|_2^2$, so $\tilde{\mu}_{\bar{\epsilon}}^*$ is the unique solution of $\min_{\mu \in \mathcal{F}_0} \|\mu\|_2^2 + \frac{1}{\bar{\epsilon}}(f_0(\mu) - K(M))$. Let $\epsilon \in (0, \epsilon^*]$. Note that for $\mu \in \mathcal{F}_0$, we have $\|\mu\|_2^2 + \frac{1}{\bar{\epsilon}}(f_0(\mu) - K(M)) \ge \|\mu\|_2^2 + \frac{1}{\epsilon^*}(f_0(\mu) - K(M))$, so that taking the minimum for $\mu \in \mathcal{F}_0$, we obtain

$$ \|\tilde{\mu}_{\bar{\epsilon}}^*\|_2^2 + \frac{1}{\bar{\epsilon}}(f_0(\tilde{\mu}_{\bar{\epsilon}}^*) - K(M)) \ge \|\tilde{\mu}_{\bar{\epsilon}^*}^*\|_2^2 + \frac{1}{\epsilon^*}(f_0(\tilde{\mu}_{\bar{\epsilon}^*}^*) - K(M)) = \|\tilde{\mu}_{\bar{\epsilon}^*}^*\|_2^2 = \|\mu^*\|_2^2. $$

It follows that $(\tilde{\mu}_{\bar{\epsilon}}^*, \frac{1}{\bar{\epsilon}})$ is a solution of (B.28), so $\tilde{\mu}_{\bar{\epsilon}}^* = \mu^*$ by uniqueness of $\mu^*$.

Accordingly, we have $\tilde{\mu}_{\bar{\epsilon}}^* = \mu^*$ for $\epsilon_{\text{conv}} \le \epsilon^*$. It further follows that $\|\tilde{\mu}_{\bar{\epsilon}}'\|_1 = \|\mu^*\|_1 + O(\epsilon_{\text{unif}}) + O(\epsilon_{\text{conv}})$. Combined with (B.27), we conclude. ■

### B.3.5 THE REGULARIZED LOWER BOUND APPROXIMATES THE LOWER BOUND

In this paragraph, we prove that the regularized lower bound $K_{\bar{\epsilon}}(M)$ converges to the true lower bound $K(M)$ as $\bar{\epsilon} \to 0$ and provide the rate of convergence at first order, see Proposition B.17 below. This result is a straight forward consequence of the approximation properties of the leveling operation $[-]\epsilon$ described by Proposition 3 and of the possibility of approximating invariant measures by uniform invariant measures, see Theorem A.6.
**Proposition B.17.** Let $M \in \mathcal{M}$ be a communicating Markov decision process. Then, as the regularization hyperparameter $\bar{\varepsilon} \equiv (\varepsilon_{\text{lvl}}, \varepsilon_{\text{unif}}, \varepsilon_{\text{conv}})$ vanishes, we have

$$K(M) \leq K_{\bar{\varepsilon}}(M) \leq K(M) + O(\|\bar{\varepsilon}\|_{\infty}).$$

More precisely, if $\varepsilon_{\text{lvl}} < \Delta^g(M)$ and $\varepsilon_{\text{unif}} < \frac{1}{2}\text{dmin}(\mu^*)|\mathcal{Z}|D(M)\|\mu^*\|_1^{-1}$ where $\mu^*$ is an arbitrary optimizer of $K(M)$, then

$$K(M) \leq K_{\bar{\varepsilon}}(M) \\ \leq K(M) + O\left(\|\mu^*\|_1 |\mathcal{Z}| D(M) \left(\frac{K(M)}{\text{dmin}(\mu^*)} + \|\Delta^*(M)\|_{\infty}\right) \varepsilon_{\text{unif}} + \|\mu^*\|_2^2 \varepsilon_{\text{conv}} + \varepsilon_{\text{lvl}}\right).$$

**Proof** We begin with the upper bound. Following Proposition 3, if $\varepsilon_{\text{lvl}} < \Delta^g(M)$, then $\mathcal{Z}_{\varepsilon_{\text{lvl}}}(M) = \mathcal{Z}^{**}(M)$ and in particular Cnf($\varepsilon_{\text{lvl}}; M) = \text{Cnf}(M)$. Moreover, we have $\text{Inv}(\varepsilon_{\text{unif}}; M) \subseteq \text{Inv}(M)$. So, if $\mu_{\bar{\varepsilon}}^*$ is the optimum of $K_{\bar{\varepsilon}}(M)$, then $\mu_{\bar{\varepsilon}}^* \in \text{Inv}(M)$ and $\sum_{z \in \mathcal{Z}} \mu_{\bar{\varepsilon}}^*(z)\text{KL}(M(z)\|M^{\dagger}(z)) \geq 1$ for all $M^{\dagger} \in \text{Cnf}(M)$. Accordingly, $\mu_{\bar{\varepsilon}}^*$ is within the feasible region of the optimization problem associated to $K(M)$, so

$$K(M) \leq \sum_{z \in \mathcal{Z}} \mu_{\bar{\varepsilon}}^*(z) \Delta^*(z; M) \leq \sum_{z \in \mathcal{Z}} \mu_{\bar{\varepsilon}}^*(z) \Delta^*(z; M) + \varepsilon_{\text{conv}} \|\mu_{\bar{\varepsilon}}^*\|_2^2 = K_{\bar{\varepsilon}}^*(M).$$

We continue with the lower bound. Let $\mu^*$ be an optimum of $K(M)$. As $\mu^*\|\mu^*\|_1^{-1} \in \text{Inv}(M) \cap \mathcal{P}(\mathcal{Z})$, by Theorem A.6, there exists $\mu_{\bar{\varepsilon}} \in \text{Inv}(\varepsilon_{\text{unif}}; M)$ such that

$$\|\mu^* - \mu_{\bar{\varepsilon}}\|_{\infty} \leq |\mathcal{Z}|D(M)\varepsilon_{\text{unif}}\|\mu^*\|_1. \qquad (B.29)$$

By Proposition 3 again, if $\varepsilon_{\text{lvl}} < \Delta^g(M)$, then $\mathcal{Z}_{\varepsilon_{\text{lvl}}}(M) = \mathcal{Z}^{**}(M)$, so $\text{Cnf}(\varepsilon_{\text{lvl}}; M) = \text{Cnf}(M)$. Introduce the quantity $\alpha := \text{dmin}(\mu^*)^{-1}|\mathcal{Z}|D(M)\|\mu^*\|_1 > 0$ and note that $\mu_{\bar{\varepsilon}} \geq (1 - \alpha\varepsilon_{\text{unif}})\mu^*$. So, if $\alpha\varepsilon_{\text{unif}} < 1$, we have $(1 - \alpha\varepsilon_{\text{unif}})^{-1}\mu_{\bar{\varepsilon}} \geq \mu^*$. Following $\text{Cnf}(\varepsilon_{\text{lvl}}; M) = \text{Cnf}(M)$, we find that $(1 - \alpha\varepsilon_{\text{unif}})^{-1}\mu_{\bar{\varepsilon}}$ is within the feasible region of the optimization problem associated to $K_{\bar{\varepsilon}}(M)$. So, writing $\beta := \text{min}(\mu_0)^{-1}\|\mu^*\|_1$, we have

$$K_{\bar{\varepsilon}}(M) \leq \frac{1}{1 - \alpha\varepsilon_{\text{unif}}} \sum_{z \in \mathcal{Z}} \mu_{\bar{\varepsilon}}(z) \Delta^*(z; M) + \frac{\varepsilon_{\text{conv}} \|\mu_{\bar{\varepsilon}}\|_2^2}{(1 - \alpha\varepsilon_{\text{unif}})^2} \\ \leq \frac{1}{1 - \alpha\varepsilon_{\text{unif}}} \sum_{z \in \mathcal{Z}} (\mu^*(z) + \beta\varepsilon_{\text{unif}}) \Delta^*(z; M) + \frac{2\varepsilon_{\text{conv}} (\|\mu^*\|_2^2 + \beta^2\varepsilon_{\text{unif}}^2 |\mathcal{Z}|^2)}{(1 - \alpha\varepsilon_{\text{unif}})^2} \\ = K(M) + O(\|\bar{\varepsilon}\|_{\infty})$$

where $(\dagger)$ invokes (B.29) together with $\|u + v\|_2^2 \leq 2(\|u\|_2^2 + \|v\|_2^2)$. ■

### B.3.6 PROPERTIES OF THE REGULARIZED LOWER BOUND

The most difficult part are continuity properties. In this paragraph, we show that for a fixed regularization hyperparameter $\bar{\varepsilon} \in (\mathbf{R}_+^*)^3$, we have $K_{\bar{\varepsilon}}(M') \to K(M)$ and $\mu_{\bar{\varepsilon}}^*(M') \to \mu_{\bar{\varepsilon}}^*(M)$ as $\|M' - M\| \to 0$. In other words, we show that both the regularized lower bound $K_{\bar{\varepsilon}}(-)$ and its optimizer $\mu_{\bar{\varepsilon}}^*(-)$ are continuous with respect to the support-aware norm $\|-\|^*$.
<figure><img src="image_14.png" /><figcaption>Figure 5: A discontinuity of $K_{\bar{\epsilon}}(M)$ when the product form (Assumption 4) is dropped. A set of Bernoulli reward models with deterministic transitions parameterized by $\theta \in \Theta \equiv [0, 1]^5$ (to the left). Arrows are choices of actions that deterministically lead to the pointed state and labels are mean rewards.</figcaption></figure>

Our proof requires a few technical assumptions on the structure of the ambient space $\mathcal{M}$. The first is that $\mathcal{M}$ is a space of Bernoulli reward Markov decision processes (Assumption 3). This assumption can probably be generalized to Gaussian rewards or, more generally, to rewards among a single parameter exponential family. The second is that $\mathcal{M}$ is in product form (Assumption 4). Without this assumption, the set of leveled confusing models $\text{Cnf}_{\bar{\epsilon}}(M)$ can be discontinuous in $M$ and information values (Definition B.1) can be discontinuous, provoking discontinuities of $K_{\bar{\epsilon}}(M)$ that cannot be addressed easily.

A simple example of discontinuity is provided in Figure 5. Consider the ambient spaces $\mathcal{M} := \{M_\theta : \theta \in \Theta\}$ (in product form) and $\mathcal{M}' := \{M_\theta : \theta_1 = \theta_2 = \theta_4 = \theta_5\}$ (not in product form) and the model $M^x \in \mathcal{M} \cap \mathcal{M}'$ as given to the right of Figure 5. Fix $\bar{\epsilon} \ge 0$ a small enough regularizer (possibly 0). As soon as $|x|$ is small enough, we always have $\text{Cnf}_{\bar{\epsilon}}(M^x; \mathcal{M}) \neq \emptyset$ by considering the confusing model with $\theta_2 \approx \theta_3 \approx 1$, so that $K_{\bar{\epsilon}}(M^x; \mathcal{M}) > 0$—In fact, $K_{\bar{\epsilon}}(M^x; \mathcal{M})$ is a continuous function of $x$ as shown by Proposition B.18 below. When the ambient space is $\mathcal{M}'$ however, this confusing model doesn't exist in $\mathcal{M}'$ and we find

$$ \text{Cnf}_{\bar{\epsilon}}(M^x; \mathcal{M}') = \begin{cases} \emptyset & \text{if } x \ge 0; \\ \{M_\theta : \theta_1 = \theta_2 = 0.1, \theta_4 = \theta_5 = 0.55 - x \text{ and } \theta_3 \ge 1 - 2x\} & \text{if } x < 0. \end{cases} $$

So, we have $\inf_{x<0} K_{\bar{\epsilon}}(M^x; \mathcal{M}') > 0$ while $K_{\bar{\epsilon}}(M^x; \mathcal{M}') = 0$ if $x \ge 0$, so $K_{\bar{\epsilon}}(M^x; \mathcal{M}')$ is not continuous at $x = 0$. Accordingly, the product form assumption (Assumption 4) on the ambient space cannot be dropped in general.

**Proposition B.18.** Let $\mathcal{M}$ be an ambient space with Bernoulli rewards (Assumption 3) in product form (Assumption 4). Let $M \in \mathcal{M}$ be a communicating model. The regularized lower bound is continuous in the follow sense: There exist functions $\psi_K, \psi_\mu : \mathbf{R}_+ \to [0, \infty]$ such that for all regularization hyperparameter $\bar{\epsilon} \equiv (\varepsilon_{\text{lvl}}, \varepsilon_{\text{unif}}, \varepsilon_{\text{conv}}) \in (\mathbf{R}_+^*)^3$ and all model $M' \in \mathcal{M}$, the errors $|K_{\bar{\epsilon}}(M') - K_{\bar{\epsilon}}(M)|$ and $\|\mu_{\bar{\epsilon}}^*(M') - \mu_{\bar{\epsilon}}^*(M)\|_{\infty}$ are respectively bounded by

$$ \psi_K \left( \frac{\|M' - M\|^*}{(\varepsilon_{\text{unif}})^{3|S|}} + \mathbf{1} \left( \|M' - M\| > \beta_1 \min \left\{ \varepsilon_{\text{lvl}}, \exp \left( -\frac{\beta_2}{(\varepsilon_{\text{unif}})^{|S|}} \right) \right\} \right) \right) $$

and

$$ \psi_\mu \left( \sqrt{\frac{\|M' - M\|^*}{(\varepsilon_{\text{unif}})^{3|S|} \varepsilon_{\text{conv}}}} + \mathbf{1} \left( \|M' - M\| > \beta_1 \min \left\{ \varepsilon_{\text{lvl}}, \exp \left( -\frac{\beta_2}{(\varepsilon_{\text{unif}})^{|S|}} \right) \right\} \right) \right) $$
with $\psi_K(x) = O(x)$ and $\psi_\mu(x) = O(x)$ when $x \to 0$, and $\beta_1, \beta_2 \in \mathbf{R}_+$ depend on $M$.

**Proof** Let $M_1, M_2$ be in the neighborhood of $M$, denoting $M_i = (\mathcal{Z}, p_i, r_i)$ for $i = 1, 2$, with $M \in \{M_1, M_2\}$. The result will follow by upper-bounding $K_{\bar{\epsilon}}(M_2)$ relatively to $K_{\bar{\epsilon}}(M_1)$. Using Lemma B.15 and Equation (B.24), for $i = 1, 2$, the $\bar{\epsilon}$-regularized regret lower bound of $M_i$ is rewritten with respect to information values as follows:

$$K_{\bar{\epsilon}}(M_i) = \inf_{\mu \in \mathcal{I}(\varepsilon_{\text{unif}}; M_i)} \left\{ \frac{\sum_{z \in \mathcal{Z}} \mu(z)(g^*(M) - r_i(z))}{C_{\varepsilon \text{lvl}}(\mu, M)} + \frac{\varepsilon_{\text{conv}} \|\mu\|_2^2}{C_{\varepsilon \text{lvl}}(\mu, M)^2} \right\}.$$

The dot product $\sum_{z \in \mathcal{Z}} \mu(z)(g^*(M) - r(z))$ will be more concisely written $\mu(g^* - r)$. Let $\mu_1^* \in \mathcal{I}(\varepsilon_{\text{unif}}; M)$ the optimum of $K_{\bar{\epsilon}}(M_1)$ and let $\mu_2$ be its projection onto $\mathcal{I}(\varepsilon_{\text{unif}}; M_2)$ as given by Theorem A.6. We introduce the following short-hand notations:

$$ \begin{aligned} d\mu &:= \mu_2 - \mu_1^* \\ d\Delta &:= g^*(M_2) + r(M_1) - g^*(M_1) - r(M_2) \\ dC &:= C_{\varepsilon \text{lvl}}(\mu_2, M_2) - C_{\varepsilon \text{lvl}}(\mu_1, M_1) \\ dM &:= \|M_2 - M_1\|^* \end{aligned} \qquad (B.30) $$

Using these notations, we have

$$ \begin{aligned} K_{\bar{\epsilon}}(M_2) &\le \frac{\mu_2(g_2^* - r_2)}{C_{\varepsilon_{\text{lvl}}}(\mu_2, M_2)} + \frac{\varepsilon_{\text{conv}} \|\mu_2\|_2^2}{C_{\varepsilon_{\text{lvl}}}(\mu_2, M_2)^2} \\ &= \frac{(\mu_1 + d\mu)(g_1^* - r_1 + d\Delta)}{C_{\varepsilon_{\text{lvl}}}(\mu_1, M_1) + dC} + \frac{\varepsilon_{\text{conv}} \|\mu_1 + d\mu\|_2^2}{(C_{\varepsilon_{\text{lvl}}}(\mu_1, M_1) + dC)^2}. \end{aligned} \qquad (B.31) $$

Roughly speaking, when $dM \ll \min(\bar{\epsilon})$, then all the variational quantities $d\mu$, $d\Delta$ and $dC$ are of order $dM$. By injecting that in (B.31), we find $K_{\bar{\epsilon}}(M_2) \le K_{\bar{\epsilon}}(M_1) + O(dM)$ and conclude accordingly. The point is that to make this argument precise.

### (STEP 1) BOUNDING THE VARIATIONAL QUANTITIES

All variational quantities of (B.30) are bounded relatively to $dM$. We find:

$$ \begin{aligned} \|d\mu\|_{\infty} &\le \frac{|S|}{(\varepsilon_{\text{unif}})^{|S|-1} \min(p)^{|S|-1}} dM \\ \|d\Delta\|_{\infty} &\le (1 + 2D(M)) dM \\ |dC| &\le \left( \frac{2(C_{\varepsilon_{\text{lvl}}}(e, M) + e^{\beta(M)} dM)|S|}{(\varepsilon_{\text{unif}})^{|S|} \min(p)^{|S|-1}} + e^{\beta(M)} \right) dM. \end{aligned} \qquad (B.32) $$

The various upper-bounds in (B.32) require conditions on $dM$ and $\bar{\epsilon}$. The bound on $\|d\mu\|_{\infty}$ is obtained directly using Corollary A.9 and holds uniformly for $\varepsilon_{\text{unif}}$ and $dM$. The bound on $\|d\Delta\|_{\infty}$ is obtained with a combination of Lemmas B.19 and B.20; Indeed, by Lemma B.19,

$$ \|d\Delta\|_{\infty} \le 2\|r' - r\|_{\infty} + \frac{1}{2} \min\{\text{sp}(b^*(M_1)), \text{sp}(b^*(M_2))\} \|p' - p\| $$
$$
\begin{align*}
\stackrel{(\dagger)}{\le} 2\|r' - r\|_{\infty} + \frac{1}{2}\mathrm{sp}(b^*(M))\|p' - p\| \\
\stackrel{(\ddagger)}{\le} 2\|r' - r\|_{\infty} + \frac{1}{2}D(M)\|p' - p\| \le (2 + D(M))dM
\end{align*}
$$

where (†) follows from $M \in \{M_1, M_2\}$ and (‡) follows from Lemma B.20. The resulting bound holds uniformly for $dM$ and $\bar{\epsilon}$.

Lastly, the bound on dC in (B.32) is obtained with a combination of Lemmas B.8, B.10 and B.11 as follows:

$$
\begin{align*}
|dC| &\stackrel{(\dagger)}{=} |C_{\varepsilon\text{lvl}}(\mu', M') - C_{\varepsilon\text{lvl}}(\mu, M)| \\
&\le |C_{\varepsilon\text{lvl}}(\mu', M') - C_{\varepsilon\text{lvl}}(\mu', M)| + |C_{\varepsilon\text{lvl}}(\mu', M) - C_{\varepsilon\text{lvl}}(\mu, M)| \\
&\stackrel{(\ddagger)}{\le} e^{\beta(M)} dM + \frac{2C_{\varepsilon\text{lvl}}(\mu, M)d\mu}{\varepsilon_{\text{unif}}} \\
&\stackrel{(\S)}{\le} e^{\beta(M)} dM + \frac{2C_{\varepsilon\text{lvl}}(e, M)d\mu}{\varepsilon_{\text{unif}}} \\
&\stackrel{(\S)}{\le} \left( e^{\beta(M)} + \frac{2C_{\varepsilon\text{lvl}}(e, M)|S|}{(\varepsilon_{\text{unif}})^{|S|}\min(p)^{|S|-1}} \right) dM
\end{align*}
$$

where (†) rewrite $C_{\varepsilon\text{lvl}}(\mu_2, M_2) - C_{\varepsilon\text{lvl}}(\mu_1, M_1)$ by using that $M \in \{M_1, M_2\}$ and introducing $M' \in \{M_1, M_2\} \setminus \{M\}$; (‡) bound the first term using Lemma B.11 and the second using Lemma B.10; (§) bounds $C_{\varepsilon\text{lvl}}(\mu, M) \le C_{\varepsilon\text{lvl}}(e, M)$ using Lemma B.8; and (§) unfolds the upper bound of $d\mu$. Note that for Lemmas B.10 and B.11 to be applicable in (‡), we need $d\mu \le \frac{1}{2}\varepsilon_{\text{unif}}$, $\text{Cnf}(\varepsilon_{\text{lvl}}; M) = \text{Cnf}(M)$ and $dM \le \min\{\varepsilon_{\text{lvl}}\alpha(M)^{-1}, \exp(-(\varepsilon_{\text{unif}})^{-1}\beta_1(M) - \beta_2(M))\}$ where $\alpha, \beta_1, \beta_2$ are polynomial functions $|\mathcal{Z}|, D, \min(M)$ and $C(e, M)$ as given in Lemma B.11. We obtain the conditions

$$
\begin{equation}
\begin{split}
& \varepsilon_{\text{lvl}} + \alpha(M)dM < \Delta^g(M) \\
& dM \le \min \left\{ \frac{\varepsilon_{\text{lvl}}}{\alpha(M)}, \exp\left(-\frac{\beta_1(M)}{(\varepsilon_{\text{unif}})^{|S|}} - \beta_2(M)\right), \frac{(\varepsilon_{\text{unif}})^{|S|}\min(p)^{|S|-1}}{2|S|} \right\}
\end{split}
\tag{B.33}
\end{equation}
$$

Under (B.33), all the bounds of (B.32) hold and in particular, the variational quantities $d\mu$, $d\Delta$ and $dC$ are of order $O(dM)$; Hence are vanishing with $dM$.

(STEP 2) BOUNDING THE VARIATIONS OF $K_{\bar{\epsilon}}$

When $dM$ is vanishing, only keeping the terms of first order, we find

$$
\begin{align*}
K_{\bar{\epsilon}}(M_2) &\le \frac{1}{1 + \frac{dC}{C_{\varepsilon\text{lvl}}(\mu_1, M_1)}} \frac{(\mu_1 + d\mu)(g_1^* - r_1 + d\Delta)}{C_{\varepsilon\text{lvl}}(\mu_1, M_1)} + \left( \frac{1}{1 + \frac{dC}{C_{\varepsilon\text{lvl}}(\mu_1, M_1)}} \right)^2 \frac{\varepsilon_{\text{conv}} \|\mu_1 + d\mu\|_2^2}{C_{\varepsilon\text{lvl}}(\mu_1, M_1)^2} \\
&\stackrel{(\dagger)}{\lesssim} K_{\bar{\epsilon}}(M_1) + \frac{(g_1^* - r_1)d\mu + \mu_1 d\Delta + (1 + 2\varepsilon_{\text{conv}})dC}{C_{\varepsilon\text{lvl}}(\mu_1, M_1)} + \frac{2\varepsilon_{\text{conv}}\mu_1 d\mu}{C_{\varepsilon\text{lvl}}(\mu_1, M_1)^2} \\
&\stackrel{(\ddagger)}{\le} K_{\bar{\epsilon}}(M_1) + \frac{(g_1^* - r_1)d\mu + \mu_1 d\Delta + (1 + 2\varepsilon_{\text{conv}})dC}{f(\varepsilon_{\text{unif}})C_{\varepsilon\text{lvl}}(e, M_1)} + \frac{2\varepsilon_{\text{conv}}\mu_1 d\mu}{f(\varepsilon_{\text{unif}})^2 C_{\varepsilon\text{lvl}}(e, M_1)^2}
\end{align*}
$$
$$
\begin{align*}
\stackrel{(\S)}{\lesssim} K_{\bar{\epsilon}}(M_1) &+ \frac{\|d\mu\|_1 + \|d\Delta\|_{\infty} + 3|dC|}{f(\varepsilon_{\text{unif}})C_{\varepsilon\text{lvl}}(e, M)} + \frac{2\varepsilon_{\text{conv}}\|d\mu\|_{\infty}}{f(\varepsilon_{\text{unif}})^2 C_{\varepsilon\text{lvl}}(e, M)^2} \\
\stackrel{(\S)}{\le} K_{\bar{\epsilon}}(M_1) &+ O\left(\frac{1}{f(\varepsilon_{\text{unif}})}\left(\frac{|S|(1 + \frac{\varepsilon_{\text{conv}}}{C_{\varepsilon\text{lvl}}(e, M)}f(\varepsilon_{\text{unif}}))}{C_{\varepsilon\text{lvl}}(e, M)f(\varepsilon_{\text{unif}})} + \frac{1}{f(\varepsilon_{\text{unif}})} + e^{\beta(M)}\right)dM\right) \\
\stackrel{(\#)}{=} K_{\bar{\epsilon}}(M_1) &+ O\left(\frac{|S|}{f(\varepsilon_{\text{unif}})}\left(\frac{1 + f(\varepsilon_{\text{unif}})C_{\varepsilon\text{lvl}}(e, M)^2}{C_{\varepsilon\text{lvl}}(e, M)^2 f(\varepsilon_{\text{unif}})^2} + e^{\beta(M)}\right)dM\right)
\end{align*}
$$

where (†) is obtained by seeing every variational quantity dμ, dΔ and dC as an infinitesimal quantity and developping at first order—Note that to do so, we need C<sub>εlvl</sub>(μ<sub>i</sub>, M) to be bounded below in a neighborhood of M, which is indeed the case by combining Lemmas B.8 and B.9; (‡) follows by combining Lemma A.7 assertion (1) and Lemma B.8 while introducing the shorthand f(ε) := ε<sup>|S|-1</sup>dmin(p)|S|-1; (§) follows by relating C<sub>εlvl</sub>(e, M) and C<sub>εlvl</sub>(e, M<sub>1</sub>) using Lemma B.11 and expanding at first order; and (§) follows by expanding everything using (B.32) and D(M) ≤ |S|f(ε<sub>unif</sub>)-1; and (#) follows by rearranging terms.

In the end, by keeping only the dominant terms, we find a bound of the form

$$
K_{\bar{\epsilon}}(M_2) \leq K_{\bar{\epsilon}}(M_1) + O\left( \frac{\|M_2 - M_1\|^*}{(\varepsilon_{\text{unif}})^{3|S|}} \right)
$$

under a condition of the form

$$
\|M' - M\| \le \beta_1 \min \left\{ \varepsilon_{\text{lvl}}, \exp \left( -\frac{\beta_2}{(\varepsilon_{\text{unif}})^{|S|}} \right) \right\} \quad (B.34)
$$

which is obtained by keeping the dominant terms in (B.33). Hence the bound on the variations of K<sub>ε</sub> described in Proposition B.18.

(STEP 3) DEDUCING THE VARIATIONS OF μ\*\_ε

By symmetry of the previous argument, $K_{\bar{\epsilon}}(M_2)$ is also upper-bounded by $K_{\bar{\epsilon}}(M_1)$. For short, introduce $K_{\bar{\epsilon}}(\mu; M) := \sum_{z \in \mathcal{Z}} \mu(z) \Delta^*(z; M) + \varepsilon_{\text{conv}} \|\mu\|_2^2$ the objective function in the optimization problem associated with $K_{\bar{\epsilon}}(M)$. Setting $\mu'_2 = C_{\bar{\epsilon}}(\mu_2, M_2)\mu_2$ the re-scaled version of $\mu_2$, we have shown that $K_{\bar{\epsilon}}(M_2) \le K_{\bar{\epsilon}}(\mu'_2; M_2) \le K_{\bar{\epsilon}}(M_2) + B$ where $\mu'_2$ is a feasible point of $K_{\bar{\epsilon}}(M_2)$ and B is of order

$$
B = O\left( \frac{|S|}{f(\varepsilon_{\text{unif}})} \left( \frac{1 + f(\varepsilon_{\text{unif}})C_{\varepsilon\text{lvl}}(e, M)^2}{C_{\varepsilon\text{lvl}}(e, M)^2 f(\varepsilon_{\text{unif}})^2} + e^{\beta(M)} \right) dM \right)
$$

where $f(\varepsilon) := \operatorname{dmin}(p)^{|S|} \varepsilon^{|S|}$.

A direct computation shows $K_{\bar{\epsilon}}(\mu'; M) = K_{\bar{\epsilon}}(\mu; M) + \nabla_{\mu} K_{\bar{\epsilon}}(\mu; M)(\mu' - \mu) + \varepsilon_{\text{conv}} \|\mu' - \mu\|_2^2$
for all $\mu, \mu' \in \mathbb{R}^Z$. As $\mu'_2$ is in the feasible region of $K_{\bar{\epsilon}}(M_2)$ and $\mu_{\bar{\epsilon}}^*(M_2)$ is the associated
minimizer, we have $\nabla_{\mu} K_{\bar{\epsilon}}(\mu_{\bar{\epsilon}}^*(M_2); M_2)(\mu'_2 - \mu_{\bar{\epsilon}}(M_2)) \ge 0$, so

$$
\| \mu'_2 - \mu_{\bar{\epsilon}}^*(M_2) \|_2^2 \le \frac{K_{\bar{\epsilon}}(\mu'_2; M_2) - K_{\bar{\epsilon}}(M_2)}{\varepsilon_{\text{conv}}} \le (\varepsilon_{\text{conv}})^{-1} B. \quad (B.35)
$$

Now, at first order, we have

$$
\| \mu'_2 - \mu_{\bar{\epsilon}}^*(M_1) \|_{\infty} = \| C_{\bar{\epsilon}}(\mu_2, M_2)(\mu_1^* + d\mu) - C_{\bar{\epsilon}}(\mu_1^*, M_1)\mu_1^* \|_{\infty}
$$