# The Regret Lower Bound for communicating Markov Decision Processes

Victor Boone, Odalric-Ambrym Maillard

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

## To cite this version:

Victor Boone, Odalric-Ambrym Maillard. The Regret Lower Bound for communicating Markov Decision Processes. 2025. hal-05421579

HAL Id: hal-05421579

https://hal.science/hal-05421579v1

Preprint submitted on 17 Dec 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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 Attribution 4.0 International License
# The Regret Lower Bound for communicating Markov Decision Processes

**Victor Boone**

Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France.
IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France

VICTOR.BOONE@IRIT.FR

**Odalric-Ambrym Maillard**

Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 - CRISTAL, F-59000, Lille, France

ODALRIC.MAILLARD@INRIA.FR

**Editor:** My editor

## Abstract

This paper is devoted to the extension of the regret lower bound beyond ergodic Markov decision processes (MDPs) in the problem dependent setting. While the regret lower bound for ergodic MDPs is well-known and has been reached by tractable algorithms recently, we prove that the regret lower bound becomes significatively more complex in communicating MDPs. Our lower bound revisits the necessary explorative behavior of consistent learning agents and further explains that all optimal regions of the environment must be overvisited compared to sub-optimal ones, a phenomenon that we refer to as co-exploration. In tandem, we show that these two explorative and co-explorative behaviors are intertwined with navigation constraints obtained by scrutinizing the navigation structure at logarithmic scale. The resulting lower bound is expressed as the solution of an optimization problem that, in many standard classes of MDPs, can be specialized to recover existing results.

**Keywords:** Markov Decision Processes, Regret Minimization, Lower Bounds, Average Reward, Instance Dependent.

## 1 Introduction

This paper considers the problem of regret minimization in discrete Markov decision processes under the average reward objective with the standard communicating assumption. We more specifically focus on the derivation of the instance dependent regret lower bound, that characterizes the performance frontier of what learning algorithms can achieve within the regret minimization framework.

**Regret minimization in MDPs.** To quantify the learning performance of a learning agent, a popular approach is to compare the amount of reward that the learning agent and an ominous agent that knows everything in advance are able to collect with the same time budget. The difference between the cumulative rewards that the two gather is known as the **regret**; the smaller the regret, the more efficient the learner. The challenging task of designing learners with theoretical and practical regret guarantees has a long history, that goes back to multi-armed bandits. In this work, we follow the path of Lai and Robbins (1985) by focusing on the **instance dependent** setting: Given a Markov decision process, what is the best regret that a learner may hope to achieve? It happens that this question is only
interesting when the focus is restricted to **consistent** learners, that, roughly speaking, have an asymptotically small regret for every environment in a given class of Markov decision processes. The seminal paper of Lai and Robbins (1985) emerges as the first model dependent regret lower bound for multi-armed bandits: for $M$ a bandit, $A$ a consistent learner and $T$ a number of learning steps, the expected regret of $A$ when running on $M$ for $T$ steps, denoted $\text{Reg}(T; M, A)$, is lower-bounded as

$$ \text{Reg}(T; M, A) \geq K(M) \log(T) + o(\log(T)), \quad (1) $$

where $K(M)$ is a known and tractable constant. Lai and Robbins (1985) also show that their bound is tight, by providing a family of consistent learners, said **asymptotically optimal**, that achieve the above lower bound.

In the more general setting of Markov decision processes, the regret lower bound of Lai and Robbins (1985) has been generalized in various directions. However, most of the literature seems to plateau at **ergodic** environments, with only very few exceptions.

**Previous work on regret lower bounds.** Regarding Markov decision processes, the dominant generalization of (Lai and Robbins, 1985) is done under an ergodic assumption. The regret lower bound for ergodic MDPs can be traced back to Agrawal et al. (1988a). The approach of Agrawal et al. (1988a) is policy-wise and every policy is treated as an arm, each explored in turn until regeneration; thus, their approach is heavily relying on the ergodic nature of the environment and is suffering from a tremendous burn-in phase, due to the immensely large number of policies. Burnetas and Katehakis (1997) circumvent this issue by decomposing the lower bound relatively to state-action pairs, and provide a pair-wisely indexed learning algorithm that is asymptotically optimal. Specifically, instead of playing policies in a round robin fashion like (Agrawal et al., 1988a), the algorithm of Burnetas and Katehakis (1997) associates an index to every playable action and play the actions with the highest index. Their solution was improved recently, by blending it with more modern bandit methods, see for instance (Pirutinsky, 2020) with DMED of (Honda and Takemura, 2010) or (Pesquerel and Maillard, 2022) with IMED of (Honda and Takemura, 2015). In parallel, Graves and Lai (1997) generalize (Lai and Robbins, 1985) to MDPs with compact state-action spaces but stick to the ergodic assumption. We have to wait for Ok et al. (2018) to find lower bounds again, generalizing Burnetas and Katehakis (1997), but keeping nonetheless the ergodic assumption. The first paper to ever escape the world of ergodic MDPs is (Tranos and Proutiere, 2021), that provides a regret lower bound for the very specific setting of deterministic transition MDPs together with algorithms that are asymptotically optimal in a few cases. To the best of our knowledge, general communicating Markov decision processes remained unsolved ever since.

**Contributions.** This article bridges this gap by deriving the regret lower bound $K(M)$ for communicating Markov decision processes, that is, MDPs in which every state is reachable from any other. As our main contribution, we unravel the delicate structure of the general regret lower bound by describing it as the solution of an optimization problem that conjugates three complementary behaviours: (1) consistent learners have to gather information on suboptimal regions (known as mandatory exploration, or information constraints); (2) they need to saturate the amount of information gathered on all optimal regions (mandatory co-exploration); (3) the two previous behaviours must be achieved while
preserving a second order structural constraint in the way they navigate their environment (second order navigation constraints). We also present multiple specifications of our lower bound in several illustrative cases, such as multi-armed bandits, ergodic MDPs, bandits with switching costs and MDPs with deterministic transition kernels.

**Related work on regret minimization.** Our paper lives in the neighborhood of a large literature of algorithms with theoretical regret guarantees for average reward Markov decision processes. These works do not aim, however, at specifically matching an instance dependent regret lower bound. In the setting of average-reward regret minimization, model-based methods include optimistic approaches Auer et al. (2009); Bartlett and Tewari (2012); Filippi et al. (2010); Talebi and Maillard (2018); Fruit et al. (2018); Zhang and Ji (2019); Bourel et al. (2020); Boone and Zhang (2024), inspired from the popular Upper Confidence Bound (UCB) strategy Auer (2002) and variants Cappé et al. (2013); Bayesian approaches Osband et al. (2013); Ouyang et al. (2017); Agrawal and Jia (2023) derived from posterior sampling Thompson (1933); Information-theoretic methods Saber et al. (2024); Pesquerel and Maillard (2022) recently derived from Honda and Takemura (2015) or Agrawal and Teneketzis (1989); Regret minimization has also been considered in model-free methods Zhang and Xie (2023) and references therein, based on Q-learning Watkins and Dayan (1992), or extended e.g. to smooth continuous MDPs Lakshmanan et al. (2015); Qian et al. (2019). Quite often, these works actually aim at reaching the celebrated **minimax** (or **instance independent**) regret lower bound of Auer et al. (2009) although many of the above mentioned are also provided with model dependent guarantees of order $O(\log(T))$ such as Auer and Ortner (2006); Auer et al. (2009); Filippi et al. (2010); Pesquerel and Maillard (2022); Saber et al. (2024). Yet, none are proven to be asymptotically optimal in the general setup.

**Outline of the paper.** In Section 2, we provide a general refresher on average reward Markov decision processes and regret minimization problems. After the warm-up, we sketch a general overview of the concepts behind our results in Section 3, and discuss the three main ingredients behind our lower bound (exploration, co-exploration and navigation constraints). The main result is stated and proved in Section 4. In our last Section 5, we detail a few instantiations of our lower bound and show that we recover and generalize existing results.

## 2 Preliminaries: Formal Setup and Notations

**General notations.** For each $k \in \mathbb{N}$, $[k]$ denotes the set $\{1, \dots, k\}$. Given a topological space $(S, \mathcal{T})$, we denote $\mathcal{P}(S)$ the set of Borel probability measures on $(S, \mathcal{T})$. Provided that $S, \mathcal{X}$ are finite, a kernel is a map $\mathbf{p}: \mathcal{X} \to \mathcal{P}(S)$ and following folklore notations, $\mathbf{p}(s|x)$ denotes the mass of $\mathbf{p}(x)$ at point $s \in S$. Given a probability distribution $\mathbf{q} \in \mathcal{P}(S)$ and a vector $f \in \mathbb{R}^S$, we denote $\mathbf{q}f$ or $\langle \mathbf{q}, f \rangle$ the expected value of $f$ under $\mathbf{q}$. We denote $\text{KL}(\mathbf{q}||\mathbf{q}')$ the Kullback-Leibler divergence between two distributions $\mathbf{q}$ and $\mathbf{q}' \in \mathbb{R}^S$. For $u \in \mathbb{R}_+^n \setminus \{0\}$ a non-negative vector, we write $\text{dmin}(u) := \min\{u_i : u_i > 0\}$ its definite minimum, which is its smallest positive entry.

For reference and reader-friendliness, an index of notations is provided in Appendix.
## 2.1 Markov Decision Processes in Average Reward

A Markov decision process (MDP) $\mathbf{M} \equiv (\mathcal{S}, \mathcal{A}, \mathbf{p}, \mathbf{r})$ consists in a four-tuple formed by a finite set of states $\mathcal{S}$, finite sets of actions indexed by states $\mathcal{A} \equiv (\mathcal{A}(s))_{s \in \mathcal{S}}$, a transition kernel $\mathbf{p}: \mathcal{X} \to \mathcal{P}(\mathcal{S})$; and a reward function $\mathbf{r}: \mathcal{X} \to \mathcal{P}(\mathbb{R})$. We denote $\mathbf{m}(x)$ the mean of $\mathbf{r}(x)$ for each $x \in \mathcal{X}$. The state and action spaces together form the pair space $\mathcal{X} := \bigcup_{s \in \mathcal{S}} \{s\} \times \mathcal{A}(s)$.

When interacting with a Markov decision process $\mathbf{M}$ by picking actions, one generates a trajectory in discrete time as follows. At time $t \ge 1$ and from the current state $S_t$, one chooses an action $A_t$ respectively to the past of the trajectory. Playing $A_t$ makes the system switch to the new state $S_{t+1} \sim \mathbf{p}(S_t, A_t)$ and produces a reward $R_t \sim \mathbf{r}(S_t, A_t)$. The generated state and reward only depends on the played pair $X_t \equiv (S_t, A_t)$ and are sampled independently of the past trajectory.

In the **average reward setting** (Puterman, 2014), the controlling agent aims at picking actions to maximize the average of all produced rewards $R_1, \dots, R_T$ when $T$ goes to infinity.

### 2.1.1 STATIONARY POLICIES, GAIN AND BIAS FUNCTIONS

A stationary policy, or **policy**, is a map $\pi: \mathcal{S} \to \mathcal{P}(\mathcal{A})$, written $\pi \in \Pi \equiv \Pi^{\text{SR}}$. Every policy $\pi \in \Pi$ induces a Markov reward process on $\mathcal{S}$ by acting on $\mathbf{M}$ with transition kernel $\mathbf{p}_{\pi}(s) := \sum_{a \in \mathcal{A}(s)} \pi(a|s)\mathbf{p}(s, a)$ and mean reward function $\mathbf{m}_{\pi}(s) := \sum_{a \in \mathcal{A}(s)} \pi(a|s)\mathbf{m}(s, a)$. The associated probability and expectation operators induced by iterating $\pi$ on $\mathbf{M}$ starting from $s_0 \in \mathcal{S}$ are respectively $\mathbb{P}_{s_0}^{\mathbf{M}, \pi}\{-\}$ and $\mathbb{E}_{s_0}^{\mathbf{M}, \pi}[-]$. It is well-known (Puterman, 2014, Chapters 8,9) that every policy $\pi \in \Pi$ has well-defined **gain** and **bias** functions, $\mathbf{g}_{\pi}$ and $\mathbf{b}_{\pi}$, given by

$$ \mathbf{g}_{\pi}(s_0; \mathbf{M}) := \lim_{T \to \infty} \frac{1}{T} \mathbb{E}_{s_0}^{\mathbf{M}, \pi} \left[ \sum_{t=1}^{T} R_t \right] = \lim_{T \to \infty} \left( \frac{1}{T} \sum_{t=1}^{T} \mathbf{p}_{\pi}^{t-1} \mathbf{m}_{\pi} \right) (s_0); $$

$$ \mathbf{b}_{\pi}(s_0; \mathbf{M}) := \text{Clim}_{T \to \infty} \mathbb{E}_{s_0}^{\mathbf{M}, \pi} \left[ \sum_{t=1}^{T} (R_t - \mathbf{g}_{\pi}(S_t; \mathbf{M})) \right] = \text{Clim}_{T \to \infty} \left( \sum_{t=1}^{T} \mathbf{p}_{\pi}^{t-1} (\mathbf{m}_{\pi} - \mathbf{g}_{\pi}) \right) (s_0) $$

where Clim denotes the Cesàro-limit. A policy $\pi$ is said **ergodic**, **recurrent** or **unichain** if the Markov chain of kernel $\mathbf{p}_{\pi}$ is respectively ergodic, recurrent or unichain, see Levin and Peres (2017); Puterman (2014). A state $s \in \mathcal{S}$ is recurrent under a policy $\pi$ if it is visited infinitely often starting from itself, i.e., $\mathbb{P}_{s}^{\mathbf{M}, \pi}\{\forall n, \exists m \ge n: S_m = s\} = 1$; or equivalently, if its return time has bounded expectation with $\mathbb{E}_{s}^{\mathbf{M}, \pi}[\inf\{t \ge 2: S_t = s\}] < \infty$. Likewise, a pair $x \equiv (s, a) \in \mathcal{X}$ is said recurrent under $\pi$ if it satisfies $\mathbb{P}_{s}^{\mathbf{M}, \pi}\{\forall n, \exists m \ge n: X_m = x\} = 1$. We write $\mathcal{S}_{\pi}^{*}(\mathbf{M})$ and $\mathcal{X}_{\pi}^{*}(\mathbf{M})$ the recurrent states and pairs of the policy $\pi$ in $\mathbf{M}$.

### 2.1.2 COMMUNICATING MARKOV DECISION PROCESSES

In the remaining of our work, we assume that all the considered Markov decision processes are **communicating**, see Assumption 1 below: A Markov decision process is communicating if it has finite diameter, i.e., if one can travel from any state to the other in finite time. Equivalently, a Markov decision process is communicating if every fully supported policy is recurrent, i.e., every policy satisfying $\pi(a|s) > 0$ for all $(s, a) \in \mathcal{X}$ is recurrent.
**Assumption 1.** All considered MDPs are communicating, i.e., every $\mathbf{M} \in \mathcal{M}$ has finite diameter:

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

Roughly speaking, Assumption 1 means that “no state is useless” and will be eventually encountered if one plays the right sequence of actions.

This assumption is fairly standard in the reinforcement learning literature, see (Auer et al., 2009; Filippi et al., 2010; Fruit et al., 2020; Tossou et al., 2019; Bourel et al., 2020) for example. It is much weaker than the ergodic assumption made in previous works on regret lower bounds (Agrawal et al., 1988a; Burnetas and Katehakis, 1996), because every ergodic environment is communicating, yet the inverse is wrong; there exists non-ergodic MDPs with finite diameter.

### 2.1.3 OPTIMAL POLICIES, BELLMAN EQUATIONS AND BELLMAN GAPS

The optimal gain $g_*(\mathbf{M})$ and bias $b_*(\mathbf{M})$ of a Markov decision process $\mathbf{M}$ are given by

$$g_*(s_0; \mathbf{M}) := \max_{\pi \in \Pi^{\text{SR}}} g_{\pi}(s_0; \mathbf{M}) \quad \text{and} \quad b_*(s_0; \mathbf{M}) := \max_{\pi \in \Pi^*(\mathbf{M})} b_{\pi}(s_0; \mathbf{M}).$$

A policy $\pi$ such that $g_{\pi}(\mathbf{M}) = g_*(\mathbf{M})$ is said **gain optimal**, written $\pi \in \Pi^*(\mathbf{M})$. When $\mathbf{M}$ is communicating (Assumption 1), the optimal gain function does not depend on $s_0$ and we will sometimes write $g_*(\mathbf{M})$ instead of $g_*(s_0; \mathbf{M})$. A gain optimal policy of which the bias reaches $b_*(s_0; \mathbf{M})$ from every initial state is further said bias optimal.

At the interplay of gain and bias optimalities stand the Bellman optimality equations:

$$\forall s \in S, \quad g_*(s; \mathbf{M}) + b_*(s; \mathbf{M}) = \max_{a \in A(s)} \{\mathbf{m}(s, a) + \mathbf{p}(s, a)\mathbf{b}_*(\mathbf{M})\}$$

that can also be written as $g_*(\mathbf{M}) + b_*(\mathbf{M}) = \max_{\pi \in \Pi^{\text{SR}}} \{\mathbf{m}_{\pi} + \mathbf{p}_{\pi}\mathbf{b}_*(\mathbf{M})\}$. Every bias optimal policy satisfies the Bellman equations; Every policy satisfying the Bellman equations is gain optimal; Both reverse statements are wrong in general (Puterman, 2014). We introduce the **Bellman gaps** $\Delta_*(s, a; \mathbf{M}) := g_*(s; \mathbf{M}) + b_*(s; \mathbf{M}) - \mathbf{m}(s, a) - \mathbf{p}(s, a)\mathbf{b}_*(\mathbf{M})$. The Bellman equations equivalently rewrite as $\Delta_*(\mathbf{M}) \ge 0$.

## 2.2 Reinforcement Learning and Regret

A learning agent, or learner, is formally a measurable map $A: \mathcal{H} \to \mathcal{P}(A)$, associating histories $H_t \equiv (S_1, A_1, R_1, \dots, S_t) \in \mathcal{H}$ to probabilities over actions. Given a Markov decision process $\mathbf{M}$ and an initial state $s_0$, a choice of learner completely determines the law of $A_t \in A(S_t)$ conditioned on $H_t$ for all $t \ge 1$, hence of $S_{t+1}$ and $R_t$ as well. We write $\mathbb{P}_{s_0}^{\mathbf{M}, A}\{-\}$ and $\mathbb{E}_{s_0}^{\mathbf{M}, A}[-\]$ the associated probability and expectation operators. The **visit vector** $N_T \in \mathbb{R}^X$ is the random variable given by $N_T(x) := \sum_{t=1}^{T-1} 1(X_t = x)$ for $x \in X$.

### 2.2.1 EXPECTED REGRET OF LEARNING AGENTS

A common benchmark to evaluate the performance of a learning agent is the **regret**, that compares the amount of reward that the learning agent gathers to the amount of reward that an ominous agent, that knows everything in advance and plays accordingly, is able
to score within the same time budget. The standard theory of Markov decision processes with average rewards Puterman (2014) explains that when only optimal actions are played, then $R_1 + \dots + R_T$ is equal to $T\mathbf{g}_*(s_0; \mathbf{M}) + O(1)$ in expectation, where $s_0 \in \mathcal{S}$ is the initial state. Following this observation, the regret compares the optimal score proxy $T\mathbf{g}_*(s_0; \mathbf{M})$ to what the learning agent actually collects, i.e., $R_1 + \dots + R_T$. As the optimal gain does not depend on the initial state in a communicating MDP, the quantity $\mathbf{g}_*(s_0; \mathbf{M})$ is changed to $\mathbf{g}_*(\mathbf{M})$. We end up with the definition considered in the seminal (Auer et al., 2009).

**Definition 1** (Expected regret, Auer et al. (2009)). The *expected regret* of a learning agent $\mathbb{A}$ in $\mathbf{M}$ at horizon $T = 1, 2, \dots$ and from the initial state $s_0 \in \mathcal{S}$ is given by

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

The smaller the regret, the better the learning agent. In particular, there is convergence to optimal play if, and only if the regret grows sublinearly.

The quantity $T\mathbf{g}_*(\mathbf{M}) - \sum_{t=1}^{T} R_t$, although easy to interpret, is a bit inconvenient because it is subject to various noises over which no learner has any control on. The so-called noise includes the stochasticity on observed rewards (i.e., $R_t$ versus $\mathbf{m}(X_t)$) as well as the stochasticity on state transitions (i.e., $S_{t+1}$ versus $\mathbf{p}(X_t)$). Several variants of **pseudo-regret** exist in the literature to circumvent this inconvenience, easing the empirical study and providing finer insight into a learner's quality of play. In this work, we use $\sum_{t=1}^{T} \Delta_*(X_t)$, as motivated by Proposition 1.

**Proposition 1.** For every communicating model $\mathbf{M}$, learner $\mathbb{A}$ and initial state $s_0 \in \mathcal{S}$, we have:

$$ \left| \mathrm{Reg}(T; \mathbb{A}, \mathbf{M}, s_0) - \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}} \left[ \sum_{t=1}^{T} \Delta_*(X_t) \right] \right| \le \mathrm{sp}(\mathbf{b}_*(\mathbf{M})) \quad (4) $$

where $\mathrm{sp}(\mathbf{b}_*(\mathbf{M})) = \max(\mathbf{b}_*(\mathbf{M})) - \min(\mathbf{b}_*(\mathbf{M}))$ is the span of the optimal bias function.

Interestingly, under Assumption 1, the bias span is always bounded with respect to the diameter as $\mathrm{sp}(\mathbf{b}_*(\mathbf{M})) \le \mathrm{sp}(\mathbf{m}) \cdot D(\mathbf{M}) < \infty$, see (Fruit, 2019, Proposition 3.6).

**Proof** Note that $\mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[\mathbf{g}_*(\mathbf{M}) - R_t|H_t] = \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[\Delta_*(X_t; \mathbf{M}) - \mathbf{b}_*(S_t; \mathbf{M}) + \mathbf{b}_*(S_{t+1}; \mathbf{M})|H_t]$ by definition of the Bellman gaps. So,

$$ \begin{aligned} \mathrm{Reg}(T; \mathbf{M}, \mathbb{A}, s_0) &\stackrel{\circ 1}{=} \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}} \left[ \sum_{t=1}^{T} \mathrm{E}[\mathbf{g}_*(\mathbf{M}) - R_t|H_t] \right] \\ &\stackrel{\circ 2}{=} \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}} \left[ \sum_{t=1}^{T} \Delta_*(X_t; \mathbf{M}) \right] + \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}} \left[ \sum_{t=1}^{T} (\mathbf{b}_*(S_{t+1}; \mathbf{M}) - \mathbf{b}_*(S_t; \mathbf{M})) \right] \\ &= \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}} \left[ \sum_{t=1}^{T} \Delta_*(X_t; \mathbf{M}) \right] + \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}} [\mathbf{b}_*(S_{T+1}; \mathbf{M}) - \mathbf{b}_*(S_1; \mathbf{M})] \end{aligned} $$

where (°1) follows from the tower property and (°2) from the definition of the Bellman gaps. The RHS of the last equation is bounded by $\mathrm{sp}(\mathbf{b}_*(\mathbf{M}))$. ■
### 2.2.2 CONSISTENT LEARNING AGENTS

Although the optimal policy depends on $\mathbf{M}$, an agent $\mathcal{A}$ is only properly learning if there is convergence to optimal play regardless of $\mathbf{M}$, that remains hidden. In opposition to an optimal policy that is specific to a single instance, a learning algorithm shall work universally for a class $\mathcal{M}$ of Markov decision processes, and therefore is a function of $\mathcal{M}$. That class $\mathcal{M}$ is viewed as the assumptions that the learning agent makes on the hidden environment. In the literature, the convergence to optimal play for every instance $\mathbf{M} \in \mathcal{M}$ is known as **consistency**, and can be stated at various degrees of strength. For $\log(T)$-rate lower bounds to be even possible, we make the strong consistency assumption of Lai and Robbins (1985), also known as uniformly fast convergence (Burnetas and Katehakis, 1996; Garivier et al., 2018; Agrawal et al., 1988a) or even simply consistency (Lattimore and Szepesvári, 2020). This assumption can hardly be weakened without degrading lower bounds, see (Salomon et al., 2013).

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

## 3 Main Ideas and Concepts Behind the Lower Bound

In this section, we provide a gentle introduction to the old and new techniques behind our regret lower bound. All existing instance dependent lower bounds from the literature are obtained by examining the mandatory behaviours induced by the consistency assumption on the learning agents. For communicating Markov decision processes, we identify three of them.

(1) **Information fetching, also known as exploration:** Consistent learning agents must try sub-optimal actions with rate of order $\log(T)$, to make sure that all seemingly sub-optimal policies are sub-optimal indeed.

(2) **Co-exploration:** We identify a set of pairs, called **optimal pairs**, that are all visited over-logarithmically by consistent learning agent. Together with the previous argument on information fetching, this means that consistent learning agents explore their environments in an unbalanced way. One set of pairs is visited with high frequency $\omega(\log(T))$ while its complementary set is visited with small frequency $O(\log(T))$.<fnref n="1" />

(3) **High order navigation structure:** In the high/low frequency dichotomy of visit frequencies, only the set of pairs visited at low frequency is responsible for the regret. In general, this lower frequency part has a structure that is imposed by the transition kernel of the underlying environment. We show that it is naturally described with invariant measures of a well-chosen **contracted** Markov decision process.

For illustration, these three concepts are now discussed over an example.

### 3.1 Fetching Information to Reject the Alternative Set

The starting point of the lower bound goes back to an argument adapted from Lai and Robbins (1985) for multi-armed bandits: Consistent learners indirectly gather information.

<footnote n="1">1. Recall that we have $f = \omega(g)$ if $f$ grows strictly faster than $g$, i.e., if $g = o(f)$.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 1: Two Markov decision processes $\mathbf{M}$ and $\mathbf{M}^\dagger$ with deterministic transitions. Every arrow represents a choice of action, that leads deterministically to the pointed state and with reduced Gaussian reward $\mathcal{N}(\alpha, 1)$, where $\alpha \in \mathbb{R}$ is the arrow label.</figcaption></figure>

Let us unravel the behavior of a consistent algorithm $\mathcal{A}$ on the two environments $\mathbf{M}$ and $\mathbf{M}^\dagger$ displayed in Figure 1. The two are communicating Markov decision processes with the same deterministic transition structure, made of an inner and an outer 5-circle. In $\mathbf{M}$, the optimal cycle is the inner one and scores 2 in average; in $\mathbf{M}^\dagger$, the optimal cycle is the outer one and scores 2.1 in average. Because the learning agent $\mathcal{A}$ has small regret, it must spend most of its time on the inner and the outer circle under $\mathbf{M}$ and $\mathbf{M}^\dagger$ respectively. This argument can be generalized as soon as $\mathbf{M}$ and $\mathbf{M}^\dagger$ do not share any gain optimal policy: because it must have small regret by consistency, the learning agent $\mathcal{A}$ commits to playing pairs of null Bellman gap. Following that, we identify patterns of visit counts (e.g., taking the transition $s_2 \to s_1$ many times) that appear with high probability in $\mathbf{M}$ and with small probability in $\mathbf{M}^\dagger$. In turn, by using changes of measures $\hat{a}$-$\hat{a}$-$\hat{a}$ Lai and Robbins (1985), it follows that the likelihood of $\mathbf{M}^\dagger$ decreases quickly when running the learning algorithm $\mathcal{A}$ on $\mathbf{M}$. We obtain:

$$ \mathbb{E}^{\mathbf{M}, \mathcal{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) \mathrm{KL}(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x)) \right] \geq \log(T) + o(\log(T)), \quad (5) $$

where $\mathrm{KL}(\mathbf{M}(x) || \mathbf{M}^\dagger(x)) := \mathrm{KL}(\mathbf{r}(x) || \mathbf{r}^\dagger(x)) + \mathrm{KL}(\mathbf{p}(x) || \mathbf{p}^\dagger(x))$ is a shorthand for the Kullback-Leibler divergence between $\mathbf{M}$ and $\mathbf{M}^\dagger$ at pair $x \in \mathcal{X}$. Because $\mathrm{KL}(\mathbf{M}(x) || \mathbf{M}^\dagger(x))$ is non-negative, Equation (5) effectively lower-bounds by a logarithmic amount the visit counts of pairs where $\mathbf{M}$ and $\mathbf{M}^\dagger$ differ. This means that consistent learner will eventually play costly actions to indirectly “reject” the model $\mathbf{M}^\dagger$.

Equation (5) can be generalized to all $\mathbf{M}^\dagger$ such that $\Pi^*(\mathbf{M}^\dagger) \cap \Pi^*(\mathbf{M}) = \emptyset$ (see Proposition 4). Such models are said alternative to $\mathbf{M}$, see Definition 3 below.

**Definition 3 (Alternative models).** Fix $\mathbf{M} \in \mathcal{M}$. The alternative set of $\mathbf{M}$ is given by

$$ \mathrm{Alt}(\mathbf{M}) := \{ \mathbf{M}^\dagger \in \mathcal{M} : \mathbf{M}^\dagger \gg \mathbf{M} \text{ and } \Pi^*(\mathbf{M}^\dagger) \cap \Pi^*(\mathbf{M}) = \emptyset \} $$
where we write $\mathbf{M}^\dagger \gg \mathbf{M}$ to mean that $\mathbf{p}(x) \ll \mathbf{p}^\dagger(x)$ and $\mathbf{r}(x) \ll \mathbf{r}^\dagger(x)$ for all $x \in \mathcal{X}$.

## 3.2 Co-exploration and Reducing the Alternative Set to the Confusing Set

In the example of Figure 1, it is clear that when run on $\mathbf{M}$, the learning agent $\mathcal{A}$ spends most of its time looping on the inner circle $\mathcal{X}_0$, with $\mathbb{E}^{\mathbf{M},\mathcal{A}}[N_{T+1}(x)] \approx \frac{1}{5}T$ for all $x \in \mathcal{X}_0$. So, if $\mathbf{M}' \in \text{Alt}(\mathbf{M})$ differs from $\mathbf{M}$ at one $x \in \mathcal{X}_0$, we have $\text{KL}(\mathbf{M}(x)\|\mathbf{M}'(x)) > 0$ and the information constraint (5) is trivially satisfied. Accordingly, a large part of the alternative set is already ruled out by another argument, stating that the learning agent automatically obtain a large amount of information for the pairs on which it spends most of its time.

<figure><img src="image_4.png" /><figcaption>Figure 2: A Markov decision process with deterministic transitions. Every arrow represents a choice of action, that leads deterministically to the pointed state and with reduced Gaussian reward $\mathcal{N}(\alpha, 1)$, where $\alpha \in \mathbb{R}$ is the label of the arrow.</figcaption></figure>

For a Markov decision process $\mathbf{M}$ as given by Figure 1, such pairs are trivially identified. When $\mathbf{M}$ is given as in Figure 2, it is a bit less clear. Indeed, gain optimal policies can either loop on $s_1$ or $s_2$, so a consistent learning agent can focus on looping on either of the two states. However, if one of the two loops were to be slightly better than the other, a consistent learning agent would focus on that one. Based on this observation and with changes of measure again, we show that for both loops $x = s_1 \to s_1$ and $x = s_2 \to s_2$,

$$ \liminf_{T \to \infty} \frac{\mathbb{E}^{\mathbf{M},\mathcal{A}}[N_{T+1}(x)]}{\log(T)} = \infty, \qquad (6) $$

i.e., $\mathbb{E}^{\mathbf{M},\mathcal{A}}[N_{T+1}(x)] = \omega(\log(T))$. For a general Markov decision process $\mathbf{M}$, Equation (6) generalizes to all $x \in \mathcal{X}$ that are recurrent under some gain optimal policy, i.e., to the whole set $\cup_{\pi \in \Pi^*(\mathbf{M})} \mathcal{X}_\pi^*(\mathbf{M})$, see Proposition 7. This motivates the following classification of pairs.

**Definition 4 (Classification of pairs).** We split the pairs of a MDP $\mathbf{M}$ as follows:

$$ \begin{align*} \textit{(Optimal pairs)} \quad & \mathcal{X}_\star(\mathbf{M}) := \bigcup \{\mathcal{X}_\pi^*(\mathbf{M}) : \pi \in \Pi^*(\mathbf{M})\} ; \\ \textit{(Weakly optimal pairs)} \quad & \mathcal{X}_\star^*(\mathbf{M}) := \{x \in \mathcal{X} : \Delta_\star(x; \mathbf{M}) = 0\} ; \\ \textit{(Suboptimal pairs)} \quad & \mathcal{X}_-(\mathbf{M}) := \mathcal{X} \setminus \mathcal{X}_\star^*(\mathbf{M}) . \end{align*} $$

We show that all optimal pairs are weakly optimal, see Lemma 2.

**Lemma 2.** Assuming $\mathbf{M}$ is communicating, we have the inclusion $\mathcal{X}_\star(\mathbf{M}) \subseteq \mathcal{X}_\star^*(\mathbf{M})$.

**Proof** Let $x \equiv (s, a) \in \mathcal{X}_\star(\mathbf{M})$. By definition, that pair is recurrent under some gain optimal policy $\pi \in \Pi^*(\mathbf{M})$. Starting from $s$ and upon iterating $\pi$, $x$ is visited infinitely many
times, so because the number of states is finite, $\mathbb{E}_{s}^{M,\pi}[\sum_{t=1}^{T} 1(X_t = x)] = \Omega(T)$. Combined with Proposition 1, we deduce that $\text{Reg}(T; \pi, \mathbf{M}, s) = \Omega(\Delta_{\star}(x; \mathbf{M})T)$. Because $\pi$ is gain optimal, we have $\text{Reg}(T; \pi, \mathbf{M}, s) = o(T)$ so $\Delta_{\star}(x; \mathbf{M}) = 0$, i.e., $x \in \mathcal{X}_{\star}(\mathbf{M})$. ■

As shown in Proposition 7, any alternative model $\mathbf{M}^{\dagger}$ that differ from $\mathbf{M}$ at some optimal pair trivially satisfies (5) because of (6). Taking coexploration into account, we reduce the alternative set to the **confusing set**, defined below (Definition 5).

**Definition 5 (Confusing models).** Fix $\mathbf{M} \in \mathcal{M}$. The confusing set of $\mathbf{M}$ is given by

$$ \text{Cnf}(\mathbf{M}) := \{ \mathbf{M}^{\dagger} \in \mathcal{M} : \mathbf{M}^{\dagger} = \mathbf{M} \text{ on } \mathcal{X}_{\star}(\mathbf{M}) \text{ and } \mathbf{M}^{\dagger} \in \text{Alt}(\mathbf{M}) \}. $$

## 3.3 Navigation: The Higher Order Navigational Structure

Exploration (Section 3.1) and coexploration (Section 3.2) are not sufficient to obtain a tight regret lower bound — this is shown in detail in Appendix A.2, drawing quite a big difference with multi-armed bandits (Lai and Robbins, 1985) and ergodic Markov decision processes (Agrawal et al., 1988a; Burnetas and Katehakis, 1997; Graves and Lai, 1997). In general, every Markov decision process has a dynamical structure, so that it cannot be freely explored, and every learner is confined within the exploration possibilities allowed by the transition kernel. On $\mathbf{M}$ as given in Figure 1, it appears clearly that the number of times $s'_{4}$ is visited is roughly equal to the number of times $s'_{3}$ is visited. Formally, the visit vector $N_{T} \in \mathbb{R}^{\mathcal{X}}$ is nearly a flow of the Markov decision process by satisfying an “entering mass equals outgoing mass” property.

In this work, we consider **invariant measures** (see Definition 6), a more adequate terminology for Markov chains and dynamical systems.

**Definition 6 (Invariant measure of a MDP).** An invariant measure $\mu \in \text{Inv}(\mathbf{M})$ of a Markov decision process $\mathbf{M}$ is a measure on $\mathcal{X}$ such that:

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

For the regret minimization problem, none of the first order structure of the visit vector nor of the associated invariant measure is actually relevant, contrasting with the literature on provably approximately correct (PAC) learning (Al Marjani et al., 2021; Tirinzoni et al., 2022; Russo and Proutiere, 2024; Al-Marjani et al., 2023). Indeed, for every consistent learner, coexploration (Section 3.2) explains the mass of $N_{T}$ provably concentrates on optimal pairs and optimal pairs do not account for the regret. Thankfully, this dominant part can be discarded with a structural operation on $\mathbf{M}$ that we call **pair space contraction**. In spirit, this operation is close to the state aggregation operation of Ortner (2013): Every communicating component of $\mathbf{M}|_{\mathcal{X}_{\star}(\mathbf{M})}$ (the original model constrained to optimal pairs) is contracted into a single state, providing a new Markov decision process denoted $\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M})$.

This operation is illustrated in Figure 3 and described formally later on, see Section 4.3 and Definition 8.

On Figure 3, the states spawned by $\mathcal{X}_{\star}(\mathbf{M})$ are merged into a single state. The visit vector $N_{T}$ satisfies a near-flow property on $\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M})$ as well, but this time all pairs of $\mathcal{X}_{\star}(\mathbf{M})$ are loops; And loops are trivial regarding flows hence are utterly discarded. What remains is
<figure><img src="image_5.png" /><figcaption>Figure 3: The contraction of $M$ by $\mathcal{X}_*(M)$. The states spawning $\mathcal{X}_*(M)$ are merged together into a single state, forming a new Markov decision process $M/\mathcal{X}_*(M)$, where the navigational behavior of a consistent learner is better understood.</figcaption></figure>

the second order structure of $N_T$, that is shown to be nearly a flow of $M/\mathcal{X}_*(M)$. It follows that the second order structure of $N_T$ converges to an invariant measure of $M/\mathcal{X}_*(M)$ up to rescaling, as formally described by Corollary 10 in Section 4.3.

## 4 An Asymptotic Regret Lower Bound

Eventually, the three components of Section 3 are combined in a single result. That is, by combining (1) the information gathering requirements from Section 3.1, (2) the reduction from the alternative set (Definition 3) to the confusing set (Definition 5) via the co-exploration mechanism from Section 3.2, and (3) the navigation constraints that consistent algorithms must follow, we obtain an asymptotic lower bound of the regret, see Theorem 3 below.

**Theorem 3 (Main result).** Let $M \in \mathcal{M}$ be communicating. The regret of every consistent learning agent on $\mathcal{M}$ satisfies $\liminf_{T \to \infty} \text{Reg}(T; \mathcal{A}, M) \log^{-1}(T) \ge K_*(M)$ where $K_*(M) \in [0, \infty]$ is given by:

$$ \inf \left\{ \sum_{x \in \mathcal{X}} \mu(x) \Delta_{*}(x) : \mu \in \text{Inv}(M) \text{ and } \inf_{M^{\dagger} \in \text{Cnf}(M)} \sum_{x \in \mathcal{X}} \mu(x) \text{KL}(M(x) || M^{\dagger}(x)) \ge 1 \right\} \quad (\text{LB}) $$

$$ = \inf \left\{ \sum_{x \in \mathcal{X}} \mu(x) \Delta_{*}(x) : \mu \in \text{Inv}(M/\mathcal{X}_{*}(M)) \text{ and } \inf_{M^{\dagger} \in \text{Cnf}(M)} \sum_{x \in \mathcal{X}} \mu(x) \text{KL}(M(x) || M^{\dagger}(x)) \ge 1 \right\} \quad (\text{LB}') $$

where $\text{KL}(M(x) || M^{\dagger}(x)) := \text{KL}(\mathbf{p}(x) || \mathbf{p}^{\dagger}(x)) + \text{KL}(\mathbf{r}(x) || \mathbf{r}^{\dagger}(x))$, for $x \in \mathcal{X}$.

We provide two expressions for the regret lower bound $K(M)$. The two are of different interest. The first (LB) is conceptually simpler, as it does not rely on minors of $M$, and is better suited to the design of asymptotically optimal algorithms. The second (LB') involves
minors and is more permissive in its navigation constraints, since $\mathrm{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M})) \supset \mathrm{Inv}(\mathbf{M})$, as shown later. That second lower bound is useful to determine when navigation constraints are actually trivial, and one such example will be thoroughly discussed in Section 5.2. Also, it is to be noticed that the confusing set $\mathrm{Cnf}(\mathbf{M})$ actually depends on the ambient class $\mathcal{M}$. Hence, so does $K_{\star}(\mathbf{M})$. When that ambient class is subject to ambiguity, we will write $K_{\star}(\mathbf{M}; \mathcal{M})$ in place of $K_{\star}(\mathbf{M})$ to make the dependency clear.

**Discussion.** The measure $\mu \in \mathbb{R}^{\mathcal{X}}$ tracks the number of times pairs are being explored (in logarithmic scale), and an element $\mu^*$ that achieves the minimum of (LB) can be interpreted as an optimal way to explore the environment and gather information. In that regard, such a $\mu^*$ will be referred to as an **optimal exploration measure** and indirectly defines a randomized policy given by $\pi(a|s) \propto \mu^*(s, a)$ that is to be used to explore optimally.

**Outline of the section.** The goal of this section is to prove Theorem 3, and mostly follow the ideas motivated in Section 3. We start with information constraints in Section 4.1, first given relatively to the alternative set (Definition 3). The resulting information constraints embody the idea that consistent learners must explore, by wandering the suboptimal regions to make sure that they do not miss the optimal policies. In Section 4.2, we show that every optimal region should be explored way more than sub-optimal regions, a phenomenon that we refer to as co-exploration. This leads to the simplification of the alternative set to the confusing set (Definition 5). In Section 4.3, we dive into navigation constraints by properly defining minors and showing that the second order structure of the visit vector converges in expectation to an invariant measure of a well-chosen minor. In Section 4.4, we mix these three ingredients together to provide a first regret lower bound with Theorem 12, given in terms of the confusing set $\mathrm{Cnf}(\mathbf{M})$ and contracted invariant measures $\mathrm{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M}))$. We finish the proof of Theorem 3 in Section 4.5 by showing that elements of $\mathrm{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M}))$ can be represented by elements of $\mathrm{Inv}(\mathbf{M})$ without changing the lower bound.

## 4.1 Exploration: Fetching Information to Reject Alternative Models

To begin with, we generalize the well-known argument of Lai and Robbins (1985) about information fetching to Markov decision processes: Consistent learning agents must explore their environment $\mathbf{M}$ so that $\mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}[\sum_{x \in \mathcal{X}} N_{T+1}(x)\mathrm{KL}(\mathbf{M}(x)||\mathbf{M}^{\dagger}(x))] \gtrsim \log(T)$ for every alternative model $\mathbf{M}^{\dagger} \in \mathrm{Alt}(\mathbf{M})$ (see Definition 3).

**Proposition 4 (Information constraint).** Let $\mathbf{M} \in \mathcal{M}$ and let $\mathbf{M}^{\dagger} \in \mathrm{Alt}(\mathbf{M})$. Whatever the initial state $s_0 \in \mathcal{S}$, every consistent learner $\mathcal{A}$ satisfies:

$$ \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) \mathrm{KL}(\mathbf{M}(x)||\mathbf{M}^{\dagger}(x)) \right] \geq \log(T) + o(\log(T)). $$

### 4.1.1 THE FUNDAMENTAL TOOL: CHANGES OF MEASURES

Obviously, a consistent learning agent has to make sure that the optimal policy is correctly guessed. That is, if $\hat{\mathbf{M}}_t$ is the empirically observed model, the agent has to make sure that there are very little chances that $\hat{\mathbf{M}}_t$ has been generated by some $\mathbf{M}^{\dagger}$ in which optimal policies of $\hat{\mathbf{M}}_t$ are far from optimal. In other words, the likelihoods of such $\mathbf{M}^{\dagger}$ have to be made small. This is properly shown using *changes of measures* and *discriminating events*.
Changes of measures are used to relate the behavior of the learning agent on $\mathbf{M}^\dagger$ to its behavior on $\mathbf{M}$; By finding a discriminating event, that holds with high probability on $\mathbf{M}$ and small probability on $\mathbf{M}^\dagger$, we can obtain upper-bounds on likelihoods.

Our starting point is to use a change of measure in the form of Theorem C.1: For every $\sigma(H_T)$-measurable random variable $U \ge 0$ and all $\mathbf{M}^\dagger \gg \mathbf{M}$, we have

$$ \mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathbb{A}}[U] \ge \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}} \left[ U \exp \left\{ -\sum_{t=1}^{T} \log \left( \frac{\mathbf{p}(S_{t+1}|S_t, A_t)}{\mathbf{p}^\dagger(S_{t+1}|S_t, A_t)} \frac{\mathbf{r}(R_t|S_t, A_t)}{\mathbf{r}^\dagger(R_t|S_t, A_t)} \right) \right\} \right]. \quad (7) $$

The quantity $L(H_T; \mathbf{M}, \mathbf{M}^\dagger) := \sum_{t=1}^T \log \left( \frac{\mathbf{p}(S_{t+1}|S_t, A_t)}{\mathbf{p}^\dagger(S_{t+1}|S_t, A_t)} \frac{\mathbf{r}(R_t|S_t, A_t)}{\mathbf{r}^\dagger(R_t|S_t, A_t)} \right)$ above is known as the log-likelihood ratio between $\mathbf{M}$ and $\mathbf{M}^\dagger$.

If Equation (7) may be used as is, such as in (Lai and Robbins, 1985), it is often transformed (Wald, 1945; Kaufmann, 2014; Maillard, 2019) to obtain an inequality that is more easy to work with. The key observation is that the expected log-likelihood ratio takes the simpler form $\mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[L(H_T; \mathbf{M}, \mathbf{M}^\dagger)] = \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[\sum_{x \in \mathcal{X}} N_{T+1}(x)KL(\mathbf{M}(x)||\mathbf{M}^\dagger(x))]$. In tandem with an application of Jensen's inequality in (7), we obtain (see Corollary C.3), for every $\sigma(H_T)$-measurable random variable $U > 0$,

$$ \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) KL(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x)) \right] \ge \mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[\log(U)] - \log(\mathbb{E}_{s_0}^{\mathbf{M}^{\dagger}, \mathbb{A}}[U]). \quad (8) $$

Accordingly, we are looking for a $U > 0$ such that $\mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[\log(U)]$ is large while $\log(\mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathbb{A}}[U])$ is small; or, such that $\mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[\log(U)]$ is small while $-\log(\mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathbb{A}}[U])$ is large. In other words, we are looking for a random variable that discriminate behaviors on $\mathbf{M}$ and $\mathbf{M}^\dagger$.

### 4.1.2 A SIMPLE EXAMPLE OF DISCRIMINATING RANDOM VARIABLE

In a few cases where $\mathbf{M}^\dagger$ satisfies more properties than merely $\mathbf{M}^\dagger \in \text{Alt}(\mathbf{M})$, the design of a discriminating random variable may be greatly simplified, so that results $\hat{\text{a-la}}$ Proposition 4 can be derived within a few lines from the change of measure inequality (8). One such example is when $\mathcal{X}_\star(\mathbf{M}^\dagger) \cap \mathcal{X}_\star(\mathbf{M}) = \emptyset$, in which case the set of sub-optimal pairs of $\mathbf{M}^\dagger$ is a superset of $\mathcal{X}_\star(\mathbf{M}) = \{x \in \mathcal{X} : \Delta_\star(x; \mathbf{M}) = 0\}$. Following this, letting

$$ U := 1 + \sum_{x \in \mathcal{X}_\star(\mathbf{M})} N_{T+1}(x) \quad (9) $$

and rewriting the expected regret as a sum of gaps with Proposition 1, we readily obtain:

$$ \begin{aligned} \text{Reg}(T; \mathbf{M}, \mathbb{A}, s_0) &\le \max(\Delta_\star(\mathbf{M}))\mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[T - U] + \text{O}(1); \text{ and} \\ \text{Reg}(T; \mathbf{M}^\dagger, \mathbb{A}, s_0) &\ge \text{dmin}(\Delta_\star(\mathbf{M}^\dagger))\mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[U] + \text{O}(1). \end{aligned} $$

What is important in the above, is to convert the consistency properties that control the expected regret to controlled inequalities on visit counts; the very value of $\max(\Delta_\star(\mathbf{M}))$ and $\text{dmin}(\Delta_\star(\mathbf{M}^\dagger))$ have very little importance asymptotically. By consistency, we get that $\mathbb{E}_{s_0}^{\mathbf{M}, \mathbb{A}}[T - U] = \text{o}(T^\eta)$ and $\mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathbb{A}}[U] = \text{o}(T^\eta)$ where $\eta > 0$ is arbitrarily small. So, by
Markov's inequality, $\mathbb{P}_{s_0}^{\mathbf{M},\mathcal{A}}(U \le T - T^{\eta}) = o(1)$ and $\mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}[\log(U)] \ge \log(T) + o(\log(T))$. Together with (8), we obtain:

$$ \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) \mathrm{KL}(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x)) \right] \ge (1 - \eta) \log(T) + o(\log(T)). $$

As $\eta > 0$ can be chosen arbitrarily small, we obtain the following result.

**Proposition 5 (Information constraint, weak version).** Let $\mathbf{M} \in \mathcal{M}$ and let $\mathbf{M}^{\dagger} \in \mathrm{Alt}(\mathbf{M})$ be such that $\mathcal{X}_{\star}(\mathbf{M}^{\dagger}) \cap \mathcal{X}_{\star}(\mathbf{M}) = \emptyset$. For all $s_0 \in \mathcal{S}$ and consistent learner $\mathcal{A}$, we have

$$ \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) \mathrm{KL}(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x)) \right] \ge \log(T) + o(\log(T)). $$

The above argument, together with the choice of discriminating random variable, is mostly similar to the proofs of Lai and Robbins (1985) for multi-armed bandits and of Agrawal et al. (1988a); Burnetas and Katehakis (1997) for ergodic environments. For general communicating environments however, it fails to capture the whole alternative set, hence Proposition 4 is not a corollary of Proposition 5, and a better choice for $U$ is required.

### 4.1.3 A GENERAL DISCRIMINATING RANDOM VARIABLE

In the general setting where $\mathbf{M}^{\dagger} \in \mathrm{Alt}(\mathbf{M})$ without any additional assumption, the choice of discriminating variable $U$ of Equation (9) is insufficient. Instead, we let $\mathcal{X}_c := \{x \in \mathcal{X}_{\star}(\mathbf{M}^{\dagger}) : \mathbf{\Delta}_{\star}(x; \mathbf{M}) > 0\}$ be the sub-optimal pairs of $\mathbf{M}$ that are optimal in $\mathbf{M}^{\dagger}$, and let

$$ U := \left( 1 + \sum_{x \in \mathcal{X}_c} N_{T+1}(x) \right)^{-1} \qquad (10) $$

be counting the time spend in $\mathcal{X}_c$. Intuitively, on $\mathbf{M}$, $U$ cannot be too small because the regret $\mathrm{Reg}(T; \mathbf{M}, \mathcal{A}, s_0)$ grows slowly, hence $\mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}[\sum_{x \in \mathcal{X}_c} N_{T+1}(x)]$ cannot be large; and, on $\mathbf{M}^{\dagger}$, $U$ must be small because $\mathrm{Reg}(T; \mathbf{M}^{\dagger}, \mathcal{A}, s_0)$ is small as well, so that $\mathbb{E}_{s_0}^{\mathbf{M}^{\dagger},\mathcal{A}}[\sum_{x \in \mathcal{X}_c} N_{T+1}(x)]$ must grow fast (linearly) with $T$. A fine control of the tails of $U$ is however required to properly spawn the $\log(T)$ factor that appears in Proposition 4.

This is made possible by Lemma 6 below.

**Lemma 6.** Let $\mathbf{M} \in \mathcal{M}$, pick $\mathbf{M}^{\dagger} \in \mathrm{Alt}(\mathbf{M})$ and let $\mathcal{X}_c := \{x \in \mathcal{X}_{\star}(\mathbf{M}^{\dagger}) : \mathbf{\Delta}_{\star}(x; \mathbf{M}) > 0\}$. There exist constants $\varepsilon_c^{\dagger}, D_c^{\dagger} > 0$ such that, whatever the learning agent $\mathcal{A}$ and the initial state $s_0$, we have:

$$ \forall u \ge 0, \quad \mathbb{P}_{s_0}^{\mathbf{M}^{\dagger},\mathcal{A}} \left( \sum_{x \in \mathcal{X}_c} N_{T+1}(x) + D_c^{\dagger} \sum_{x \in \mathcal{X}_-(\mathbf{M}^{\dagger})} N_{T+1}(x) \le \varepsilon_c^{\dagger} T - u \right) \le \exp \left( - \frac{2u^2}{T D_c^{\dagger 2}} \right). $$

What Lemma 6 essentially states is that, on $\mathbf{M}^{\dagger}$, one must either spend a lot of time in $\mathcal{X}_c$ or in $\mathcal{X}_-(\mathbf{M}^{\dagger})$. Informally, it means that the pairs $\mathcal{X}_c$ are necessary passage points for $\mathcal{X} \setminus \mathcal{X}_-(\mathbf{M}^{\dagger}) \equiv \mathcal{X}_{\star}(\mathbf{M}^{\dagger})$, in the sense that if weakly-optimal pairs of $\mathbf{M}^{\dagger}$ are played a lot, then so are pairs of $\mathcal{X}_c$. The proof of Lemma 6 is provided in Appendix B.
**Proof of Proposition 4** Let $\mathbf{M} \in \mathcal{M}$ and pick $\mathbf{M}^\dagger \in \text{Alt}(\mathbf{M})$. All along the proof, we will be using the short-hand $N_{T+1}(\mathcal{X}_0) := \sum_{x \in \mathcal{X}_0} N_{T+1}(x)$ for $\mathcal{X}_0 \subseteq \mathcal{X}$. Following the previous discussion, let $\mathcal{X}_c := \{x \in \mathcal{X}_\star(\mathbf{M}^\dagger) : \mathbf{\Delta}_\star(x; \mathbf{M}) > 0\}$ and fix $U := (1 + N_{T+1}(\mathcal{X}_c))^{-1}$.

Fix $\eta > 0$ arbitrary. The goal is to invoke Equation (8) for $U$.

We start by upper-bounding $\mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}}[U]$, which is the hard part of the proof. Let $\varepsilon_c^\dagger, D_c^\dagger > 0$ the constants provided by Lemma 6. By Proposition 1, we know for all $T \ge 1$, we have:

$$ \begin{aligned} \operatorname{sp}(\mathbf{b}_\star(\mathbf{M}^\dagger)) + \operatorname{Reg}(T; \mathbf{M}^\dagger, \mathcal{A}, s_0) &\ge \mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) \mathbf{\Delta}_\star(x; \mathbf{M}^\dagger) \right] \\ &\ge \operatorname{dmin}(\mathbf{\Delta}_\star(\mathbf{M}^\dagger)) \mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}} \left[ \sum_{x \in \mathcal{X}_-(\mathbf{M}^\dagger)} N_{T+1}(x) \right]. \end{aligned} \quad (11) $$

In particular, $\mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}}[N_{T+1}(\mathcal{X}_-(\mathbf{M}^\dagger))] = o(T^\eta)$. Then, we bound $\mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}}[U]$ as follows:

$$ \begin{aligned} \mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}}[U] &\equiv \mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}} \left[ \frac{1}{1 + \sum_{x \in \mathcal{X}_c} N_{T+1}(x)} \right] \\ &\le \inf_{v \ge 0} \left\{ \frac{1}{1+v} + \mathbb{P}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}}(N_{T+1}(\mathcal{X}_c) \le v) \right\} \\ &\le \inf_{v \ge 0} \left\{ \frac{1}{1+v} + \mathbb{P}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}} \left( D_c^\dagger N_{T+1}(\mathcal{X}_-(\mathbf{M}^\dagger)) \ge \frac{1}{2} \varepsilon_c^\dagger T \right) \right. \\ &\qquad \left. + \mathbb{P}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}} \left( N_{T+1}(\mathcal{X}_c) + D_c^\dagger N_{T+1}(\mathcal{X}_-(\mathbf{M}^\dagger)) \le v + \frac{1}{2} \varepsilon_c^\dagger T \right) \right\} \\ &\stackrel{\circ 1}{\le} \inf_{v \ge 0} \left\{ \frac{1}{1+v} + \frac{D_c^\dagger \mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}}[N_{T+1}(\mathcal{X}_-(\mathbf{M}^\dagger))]}{\frac{1}{2} \varepsilon_c^\dagger T} + \exp \left( - \frac{2 \left( \frac{1}{2} \varepsilon_c^\dagger T - v \right)^2}{T D_c^{\dagger 2}} \right) \right\} \\ &\stackrel{\circ 2}{\le} \inf_{v \ge 0} \left\{ \frac{1}{1+v} + o(T^{\eta-1}) + \exp \left( - \frac{2 \left( \frac{1}{2} \varepsilon_c^\dagger T - v \right)^2}{T D_c^{\dagger 2}} \right) \right\} \\ &\stackrel{\circ 3}{\le} \frac{1}{1 + \frac{1}{4} \varepsilon_c^\dagger T} + o(T^{\eta-1}) + \exp \left( - \frac{\varepsilon_c^\dagger T}{8 D_c^{\dagger 2}} \right) \end{aligned} $$

where (°1) is obtained by upper-bounding the first term using Markov inequality and the second using Lemma 6; (°2) bounds $\mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}}[N_{T+1}(\mathcal{X}_-(\mathbf{M}^\dagger))]$ by the regret via Equation (11) and invoke the strong consistency property; and (°3) picks $v := \frac{1}{4} \varepsilon_c^\dagger T$.

Taking the log, we conclude that $\log(\mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}}[U]) \le (\eta - 1) \log(T) + o(\log(T))$.

With similar reasoning as for Equation (11), we show that

$$ \mathbb{E}_{s_0}^{\mathbf{M}, \mathcal{A}} \left[ \sum_{x \in \mathcal{X}_c} N_{T+1}(x) \right] \le \frac{\operatorname{Reg}(T; \mathbf{M}, \mathcal{A}, s_0) + \operatorname{sp}(\mathbf{b}_\star(\mathbf{M}))}{\operatorname{dmin}(\mathbf{\Delta}_\star(\mathbf{M}))} = o(T^\eta). \quad (12) $$

We conclude as follows. By (8), we have:

$$ \mathbb{E}_{s_0}^{\mathbf{M}, \mathcal{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^\dagger(x)) \right] \ge \mathbb{E}_{s_0}^{\mathbf{M}, \mathcal{A}}[\log(U)] - \log(\mathbb{E}_{s_0}^{\mathbf{M}^\dagger, \mathcal{A}}[U]) $$
$$ \begin{aligned} & \stackrel{\circ 1}{\ge} -\log\left(1 + \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}\left[\sum_{x \in \mathcal{X}_c} N_{T+1}(x)\right]\right) + (1 - \eta)\log(T) + o(\log(T)) \\ & \stackrel{\circ 2}{\ge} (1 - 2\eta)\log(T) + o(\log(T)). \end{aligned} $$

where (°1) is obtained by applying Jensen's inequality to bound the first term and the previous computation to bound the second; and (°2) follows from Equation (12).

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

## 4.2 Co-Exploration: Simplifying Alternative Sets to Confusing Sets

Proposition 4 is our most precise result about how much information consistent learners must collect during play, and explains why the regret of such learners scales logarithmically: they must spend a logarithmic amount of time to “reject” all alternative models.

In this paragraph, we highlight another phenomenon: consistent learners play every optimal pair super-logarithmically often. In the light of Proposition 4, it means that every alternative model $\mathbf{M}^\dagger$ that differs from $\mathbf{M}$ on optimal pairs is trivially rejected. This phenomenon is to be distinguished from exploration (playing sub-optimal pairs to make sure that they are sub-optimal) because it underlines a need to play optimal (hence zero-cost) pairs in order to gather information on them rather than gathering rewards alone.

We call that co-exploration.

**Proposition 7 (Co-exploration constraint).** Let $\mathbf{M} \in \mathcal{M}$ and fix $x_* \in \mathcal{X}_*(\mathbf{M})$. Assume that, for all $\varepsilon > 0$, there exists $\mathbf{M}' \in \mathcal{M}$ such that (1) $\mathbf{M}'$ and $\mathbf{M}$ only differ with $\mathbf{r}(x_*) \neq \mathbf{r}'(x_*)$, (2) $\mathbf{m}(x_*) < \mathbf{m}'(x_*)$ and (3) $\mathrm{KL}(\mathbf{r}(x_*)||\mathbf{r}'(x_*)) < \varepsilon$. Then, for every consistent learner $\mathcal{A}$ and regardless of the initial state $s_0 \in \mathcal{S}$,

$$ \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}[N_{T+1}(x_*)] = \omega(\log(T)). $$

The proof of Proposition 7 is deferred to Appendix B — it relies again on a change of measure.

In Proposition 7, the three conditions (1-3) imply that there exist models that are arbitrarily close to $\mathbf{M}$, yet for which every gain optimal policy must use $x_*$ infinitely often. These conditions are for instance automatically satisfied when the ambient space $\mathcal{M}$ is the set of all communicating Markov decision processes with pair space $\mathcal{X}$ and if $\mathbf{M} \in \mathcal{M}$ satisfies $\max(\mathbf{m}) < 1$. In that scenario, the information constraints of Proposition 4 can be dropped to confusing models instead of alternative ones. Indeed, if $\mathbf{M}^\dagger \in \mathrm{Alt}(\mathbf{M})$ is such that there exists $x \in \mathcal{X}_*(\mathbf{M})$ with $\mathrm{KL}(\mathbf{M}(x)||\mathbf{M}^\dagger(x)) > 0$, then every consistent learner is such that

$$ \liminf_{T \to \infty} \frac{1}{\log(T)} \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) \mathrm{KL}(\mathbf{M}(x)||\mathbf{M}^\dagger(x)) \right] = \infty. $$

Therefore, the information constraint associated to $\mathbf{M}^\dagger$ in Proposition 4 is trivially met. Accordingly, the quantification “$\mathbf{M}^\dagger \in \mathrm{Alt}(\mathbf{M})$” in Proposition 4 can be changed to “$\mathbf{M}^\dagger \in \mathrm{Cnf}(\mathbf{M})$” without losing information in general.
### 4.2.1 BEYOND OPTIMAL PAIRS AND WHY Cnf(M) CANNOT BE FURTHER SIMPLIFIED

The take-away from Section 4.2 is that the alternative set can be simplified to the confusing set without losing information on how consistent learners behave. In this paragraph, we explain why it is impossible to further simplify Cnf(M) to another set with more results in the style of Proposition 7. The reason is that the amount of time spent outside of $\mathcal{X}_*(M)$ is proportional to the regret, meaning that overshooting the amount of information on some $x \notin \mathcal{X}_*(M)$ necessarily increases the regret, see Lemma 8 below. This illustrates the transient nature of $\mathcal{X} \setminus \mathcal{X}_*(M)$ and the difference between weakly optimal and optimal pairs.

**Lemma 8.** Let $M \in \mathcal{M}$. There exist $\alpha, \beta > 0$ such that, for every learner $\mathbb{A}$ and $T \ge 1$,

$$ \mathbb{E}_{s_0}^{M, \mathbb{A}} \left[ \sum_{t=1}^{T} 1(X_t \notin \mathcal{X}_*(M)) \right] \le \alpha \mathrm{Reg}(T; M, \mathbb{A}, s_0) + \beta. $$

**Proof** Consider the revised version $M_f$ of $M$ with revised reward vector $f(x) := 1(x \in \mathcal{X}_*(M))$. Let $\pi$ the policy such that $\pi(s)$ is the uniform probability distribution over $\{a \in \mathcal{A}(s) : (s, a) \in \mathcal{X}_*(M)\}$. This policy is gain-optimal, and we denote $g_f, b_f$ and $\Delta_f$ the gain, bias and gap functions of $\pi$ under the reward function $f$. We have:

$$ \begin{aligned} \sum_{x \notin \mathcal{X}_*(M)} N_{T+1}(x) &= T - \sum_{t=1}^{T} f(X_t) \stackrel{\circ 1}{=} T - \sum_{t=1}^{T} (g_f(S_t) + (e_{S_t} - \mathbf{p}(X_t))\mathbf{b}_f - \mathbf{\Delta}_f(X_t)) \\ &\stackrel{\circ 2}{\le} \mathrm{sp}(\mathbf{b}_f) + \|\mathbf{\Delta}_f\|_{\infty} \sum_{x \notin \mathcal{X}_*(M)} N_{T+1}(x) \\ &\le \mathrm{sp}(\mathbf{b}_f) + \frac{\|\mathbf{\Delta}_f\|_{\infty}}{\mathrm{dmin}(\mathbf{\Delta}_*(M))} \sum_{x \notin \mathcal{X}_*(M)} N_{T+1}(x)\mathbf{\Delta}_*(x; M) \end{aligned} $$

where (°1) unfolds the definition of $\mathbf{\Delta}_f$, and (°2) uses that since $\pi$ is gain optimal, it converges to $\mathcal{X}_*(M)$ so $g_f = 1$; and that $\mathbf{\Delta}_f(x) = 0$ for $x \notin \mathcal{X}_*(M)$. Take the expectation. ■

If no pair of $\mathcal{X} \setminus \mathcal{X}_*(M)$ may be visited without degrading the regret, then efficient learners should restrict excursions outside of $\mathcal{X}_*(M)$ to the bare minimum. In that aspect, Proposition 7 and Lemma 8 are the two sides of the same coin: efficient consistent learners shall gather over-logarithmic amounts of information on optimal pairs, but not on any other. In other words, $\mathcal{X}_*(M)$ and $\mathcal{X} \setminus \mathcal{X}_*(M)$ shall be treated differently.

### 4.2.2 REGRET BOUNDS DIRECTLY OBTAINED FROM INFORMATION CONSTRAINTS

It turns out that we can derive a regret lower bound from information constraints alone. By Proposition 1, the expected regret can be approximated by $\sum_{x \in \mathcal{X}} \mathbb{E}_{s_0}^{M, \mathbb{A}}[N_{T+1}(x)]\mathbf{\Delta}_*(x; M)$, while Proposition 4 states that $\sum_{x \in \mathcal{X}} \mathbb{E}_{s_0}^{M, \mathbb{A}}[N_{T+1}(x)]\mathrm{KL}(M(x)||M^\dagger(x)) \gtrsim \log(T)$ for all $M^\dagger \in \mathrm{Alt}(M)$. Hence, normalizing by $\log(T)$ and letting $T \to \infty$, consistent learners satisfy:

$$ \liminf_{T \to \infty} \frac{\mathrm{Reg}(T; M, \mathbb{A}, s_0)}{\log(T)} \\ \ge \inf \left\{ \sum_{x \in \mathcal{X}} \mu(x) \mathbf{\Delta}_*(x; M) : \mu \in [0, \infty]^\mathcal{X} \text{ and } \inf_{M^\dagger \in \mathrm{Alt}(M)} \sum_{x \in \mathcal{X}} \mu(x) \mathrm{KL}(M(x)||M^\dagger(x)) \ge 1 \right\}. $$
What Proposition 7 states is that in the above and under mild assumptions, Alt($\mathbf{M}$) can be changed to Cnf($\mathbf{M}$) without changing the lower bound. The resulting lower bound is of the same kind as (Lai and Robbins, 1985; Graves and Lai, 1997; Burnetas and Katehakis, 1997; Agrawal et al., 1988a) and can be seen as a generalization of their results to the more general setting of communicating Markov decision processes. It appears clearly that in such bounds however, the structure of $N_{T+1}/\log(T)$ is disregarded. In the respective settings of these works, it is reasonable to do so, because the obtained lower bound is provably reached by a learning agent. This is only possible in their particular settings however, and the lower bound that we provide downstream will provide new light into why, and when, the structure of $N_{T+1}/\log(T)$ can be “ignored”, see Sections 5.1 and 5.2.

In general and as motivated in Section 3.3, the structure of $N_{T+1}/\log(T)$ is far from arbitrary for communicating Markov decision processes, and has to be taken into account.

## 4.3 Decomposition of the Navigation of Consistent Learners and Minors

With Proposition 4, consistent learning agents have been shown to wander their environment in order to implicitly collect enough information so that alternative models are rejected. This environment, in opposition to multi-armed bandits, usually has structure. The critical lack of information on a pair $x \in \mathcal{X}$ requires the agent to compute an efficient way to reach that pair, hence the visit vector $N_{T+1}$ is not just any element of $\mathbb{N}^{\mathcal{X}}$. This all has already been discussed in Section 3.3, where we have pinpointed the importance of minors, that we shall formally define now.

### 4.3.1 FORMAL DEFINITION OF MINORS

We suggest the notion of minors as a generalization of edge contraction in graph theory. In spirit, minors are close to the state reduction/aggregation of Ortner (2013). and are obtained by contracting subsets of pairs of the initial model. In opposition to classical graph theory, we won't allow for the contraction of arbitrary subsets of pairs. The contracted subset $\mathcal{X}'$ must be **closed** (Definition 7), meaning that (1) one remains in the states spawned by $\mathcal{X}'$ by playing pairs of $\mathcal{X}'$, and (2) it does not contain transient states. The property (1) implies that $\mathbf{M}$ can be restricted to $\mathcal{X}'$ and the states it spawns, and (2) that the obtained model is a union of disjoint communicating Markov decision processes.

**Definition 7 (Closed pair subspace of M).** A subset $\mathcal{X}_0 \subseteq \mathcal{X}$ with corresponding states $S(\mathcal{X}_0)$ is a **closed set of M** if it is (1) **forward closed** meaning $\mathbf{p}(-|x)|$ is supported in $S(\mathcal{X}_0)$ for all $x \in \mathcal{X}_0$, and (2) **backward closed**, meaning the model $\mathbf{M}$ constrained to $\mathcal{X}_0^2$ is a union of communicating components (no transient states).

A simple observation is that a subset $\mathcal{X}_0$ is closed if, and only if it is the set of recurrent pairs under some randomized stationary policy. In this paper, the most important example of closed set is the set of optimal pairs $\mathcal{X}_*(\mathbf{M})$, which is obtained as the recurrent pairs of the policy $\pi^*$ given by $\pi^*(s)$ as the uniform distribution on $\{a \in \mathcal{A}(s) : (s, a) \in \mathcal{X}_*(\mathbf{M})\}$.

**Definition 8 (Minors/Contractions).** Up to re-labelling actions, assume that $\mathcal{A}(s) \cap \mathcal{A}(s') = \emptyset$ for $s \neq s'$. Let $\mathbf{M} \in \mathcal{M}$ be a model and fix $\mathcal{X}_0 \subseteq \mathcal{X}$ a closed set of $\mathbf{M}$. The **contraction of**

<footnote n="2">2. Note that the constrained model $\mathbf{M}|_{\mathcal{X}_c}$ is well-defined by forward closeness (1).</footnote>
M by $\mathcal{X}_0$ is the model $M/\mathcal{X}_0$ obtained by merging every communicating component of $\mathcal{X}_0$ into single states. More formally, letting $S_1, \dots, S_k$ the communicating components of $\mathcal{X}_0$, we have:

(1) The state space is $S(M/\mathcal{X}_0) := \{S_1, \dots, S_k\} \cup \{\{s\} : s \in S \text{ and } s \notin \bigcup_{i=1}^k S_i\}$ and contracted states are denoted $[s]$;

(2) The action space is, for $[s] \in S(M/\mathcal{X}_0)$, $A(M/\mathcal{X}_0)[s] := \bigcup_{s' \in [s]} A(s')$; because in M, the choice of an action uniquely determines a state, the state-action space $\mathcal{X}(M/\mathcal{X}_0)$ is canonically isomorphic to $\mathcal{X}(M)$, by associating $([s], a)$ to $(s', a)$ where $s'$ is the unique state such that $a \in A(s')$.

(3) The kernel is $[p]([s_1][s_0], a) := \sum_{s'_1 \in [s_1]} p(s'_1|s'_0, a)$;

(4) The reward is $[r]([s_0], a) := r(s'_0, a)$.

We also say that $M/\mathcal{X}_0$ is a minor of $M$.

### 4.3.2 DECOMPOSING EXECUTIONS USING INVARIANT MEASURES OF MINORS

Minors provide a descriptive decomposition of how a Markov decision process can be explored. Independently of the way a learner explores the model, the normalized ratio of visits outside of a closed set converges to an invariant measure of the minor induced by that closed set, provided that the outside is visited at least logarithmically often.

**Proposition 9.** Let $\pi$ a randomized policy and let $\mathcal{X}_\pi$ its recurrent pairs. Let $\mathbb{A}$ any learning agent such that $\mathbb{E}_{s_0}^{M,\mathbb{A}}[\sum_{x \notin \mathcal{X}_\pi} N_T(x)] = \Omega(\log(T))$. The vector given by

$$ \mu_t(x) := \frac{\mathbb{E}_{s_0}^{M,\mathbb{A}}[N_t(x)]1(x \notin \mathcal{X}_\pi)}{\mathbb{E}_{s_0}^{M,\mathbb{A}}[\sum_{x' \notin \mathcal{X}_\pi} N_t(x')]} $$

converges to the space of invariant measures of $M/\mathcal{X}_\pi$, i.e., every limit point of $(\mu_t)$ is an invariant measure of $M/\mathcal{X}_\pi$.

This result is coupled with a second observation. It can be shown that if the expected visits counts can be written as $\mathbb{E}^A[N_T(x)] = \alpha(x)T + o(T)$, then $\mathcal{X}_\mathbb{A} := \{x : \alpha(x) > 0\}$ is a closed set that is a subset of $\mathcal{X}_\star(M)$ when $\mathbb{A}$ is consistent. Proposition 9 supports the previously motivated idea that the “sublinear” part of visit counts is easier to understand after contracting the model by $\mathcal{X}_\star(M)$: Up to normalization, the truncation of the visit vector of a consistent learning agent to $\mathcal{X} \setminus \mathcal{X}_\star(M)$, given by $N_T1(\mathcal{X}_\star(M)^c)$, converges to a probability invariant measure of $M/\mathcal{X}_\star(M)$ in expectation.

Specifically, Proposition 9 will be used in the following form.

**Corollary 10 (Navigation constraints).** Consider a consistent algorithm $\mathbb{A}$ and let $M \in \mathcal{M}$ such that $\text{Cnf}(M) \neq \emptyset$. Then the vector given by

$$ \mu_T(x) := \frac{\mathbb{E}_{s_0}^{M,\mathbb{A}}[N_T(x)]1(x \notin \mathcal{X}_\star(M))}{\mathbb{E}_{s_0}^{M,\mathbb{A}}[\sum_{x' \notin \mathcal{X}_\star(M)} N_T(x')]} $$

converges to $\text{Inv}(M/\mathcal{X}_\star(M)) \cap \mathcal{P}(\mathcal{X})$ when $T \to \infty$.
**Proof of Corollary 10** Since Cnf(M) ≠ ∅, there exists M† ∈ Cnf(M). In particular, we have max$_{x}$$_{∈}$$_{X}$ KL(M(x)||M†(x)) < ∞. By Proposition 4, we have

$$
\begin{align*}
\log(T) &\lesssim \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) \mathrm{KL}(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x)) \right] \\
&\stackrel{\circ 1}{\le} \max_{x \in \mathcal{X}} \left\{ \mathrm{KL}(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x)) \right\} \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}} \left[ \sum_{x \notin \mathcal{X}_{\star}(\mathbf{M})} N_{T+1}(x) \right]
\end{align*}
$$

where (°1) follows from that $\mathbf{M}^{\dagger} = \mathbf{M}$ on $\mathcal{X}_{\star}(\mathbf{M})$. We deduce that $\mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}[\sum_{x \notin \mathcal{X}_{\star}(\mathbf{M})} N_T(x)] = \Omega(\log(T))$. Moreover, remark that $\mathcal{X}_{\star}(\mathbf{M})$ is closed as the set of recurrent pairs of the policy $\pi^*$ such that $\pi^*(-|s|)$ is uniform on $\{a : (s, a) \in \mathcal{X}_{\star}(\mathbf{M})\}$ if $s \in S(\mathcal{X}_{\star}(\mathbf{M}))$ and uniform on $\mathcal{A}(s)$ otherwise. Accordingly, we can apply Proposition 9, to see that

$$
\mu_T'(x) := \frac{\mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}[N_T(x)] \mathbf{1}(x \notin \mathcal{X}_\star(\mathbf{M}))}{\mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}[\sum_{x' \notin \mathcal{X}_\star(\mathbf{M})} N_T(x')]}.
$$

converges to Inv(M/X\*_M) as T → ∞. It is obviously a probability vector.

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

We now move on to the proof of Proposition 9.

We introduce a supplementary set of notations to ease the proof. We write $\mathbb{E}[-]$ in place of $\mathbb{E}_{s_0}^{\mathbf{M}}[-]$. By definition, the states of $[\mathbf{M}] := \mathbf{M}/\mathcal{X}_{\pi}$ are subsets of states of the original model $\mathbf{M}$, and its pair space is canonically identifiable to the one of $\mathbf{M}$. We introduce the $\mathcal{X}_{\pi}^c$-truncated visit counts:

$$
N'_{t}(x) := \mathbb{1}(x \notin \mathcal{X}_{\pi}) N_{t}(x) \quad (13)
$$

with the induced state-wise visits $N'_t(s) := \sum_a N'_t(s, a)$, in the minor $N'_t[s] := \sum_{s' \in [s]} N'_t(s')$, as well as the transition-wise $N'_{t+1}(x; s') := \mathbb{1}(x \notin \mathcal{X}_\pi) N_{t+1}(x; s')$. We further denote $\mu_t(s) := \sum_a \mu_t(s, a)$ and, for $[s] \in \mathcal{S}[\mathbf{M}]$ a state of the contraction, $\mu_t[s] := \sum_{s' \in [s]} \mu_t(s')$.

The starting point of the proof is that $N'_t$ satisfies a quasi-flow property on the contracted $\mathbf{M}/\mathcal{X}_\pi$ (mass that goes in equals that mass that goes out), see Lemma 11.

**Lemma 11 (Quasi-flow property).** Under the above system of notations, the $\mathcal{X}_{\pi}^c$-truncated visit counts (13) satisfy the quasi-flow property:

$$
N'_{t}[s] = \sum_{s' \in [s]} \sum_{x} N'_{t}(x; s') + \mathbb{1}(S_{0} \in [s]) - \mathbb{1}(X_{t} \in \mathcal{X}_{\pi}, S_{t} \in [s]) = \sum_{s' \in [s]} \sum_{a \in \mathcal{A}(s')} N'_{t}(s', a). \quad (14)
$$

**Proof** We proceed by induction $t \ge 0$. This is obvious for $t=0$. For $t \ge 1$, we have:

$$
\begin{align*}
& \sum_{s' \in [s]} \sum_{a \in \mathcal{A}(s')} N'_{t}(s', a) \\
& \equiv N'_{t}[s] = N'_{t-1}[s] + \mathbb{1}(S_{t} \in [s], X_{t} \notin \mathcal{X}_{\pi}) \\
& \stackrel{\circ 1}{=} \mathbb{1}(S_{0} \in [s]) - \mathbb{1}(X_{t-1} \in \mathcal{X}_{\pi}, S_{t-1} \in [s]) + \sum_{s' \in [s]} \sum_{x} N'_{t-1}(x; s') + \mathbb{1}(S_{t} \in [s], X_{t} \notin \mathcal{X}_{\pi}) \\
& = \mathbb{1}(S_{0} \in [s]) + \sum_{s' \in [s]} \sum_{x} N'_{t}(x; s')
\end{align*}
$$
$$ \underbrace{-1(X_{t-1} \in \mathcal{X}_{\pi}, S_{t-1} \in [s]) + 1(S_t \in [s], X_t \notin \mathcal{X}_{\pi}) - 1(S_t \in [s], X_{t-1} \notin \mathcal{X}_{\pi})}_{(I)} $$

where (°1) holds by induction. We focus on the RHS (I). We claim that

$$ (I) = -1(X_t \in \mathcal{X}_{\pi}, S_t \in [s]). \qquad (15) $$

Equation (15) is shown by distinguishing cases.

* If $X_{t-1} \in \mathcal{X}_{\pi}$ and $X_t \in \mathcal{X}_{\pi}$, then because the states of $\mathcal{X}_{\pi}$ are closed by playing pairs of $\mathcal{X}_{\pi}$, it follows that $[S_t] = [S_{t-1}]$ correspond to the same recurrent class of $\pi$. If $[S_t] = [S_{t-1}] \neq [s]$, then we get (15) : 0 = 0 and if $[S_t] = [S_{t-1}] = [s]$, then (15) : -1 = -1.

* If $X_{t-1} \notin \mathcal{X}_{\pi}$ and $X_t \notin \mathcal{X}_{\pi}$, then (15) : 0 = 0.

* If $X_{t-1} \in \mathcal{X}_{\pi}$ and $X_t \notin \mathcal{X}_{\pi}$, then similarly $[S_{t-1}] = [S_t]$. If equal to $[s]$ then (15) : 0 = 0 and otherwise (15) : 0 = 0.

* If $X_{t-1} \notin \mathcal{X}_{\pi}$ and $X_t \in \mathcal{X}_{\pi}$, then $[S_t]$ and $[S_{t-1}]$ can be equal or not, and we have four cases. If (i) $[S_t] = [S_{t-1}] = [s]$, we have (15) : -1 = -1; If (ii) $[S_t] = [S_{t-1}] \neq [s]$, we have (15) : 0 = 0; If (iii) $[S_t] = [s] \neq [S_{t-1}]$, we have (15) : -1 = -1; And if (iv) $[S_t] \neq [s] = [S_{t-1}]$, we have (15) : 0 = 0.

As Equation (15) is established, Equation (14) follows immediately.

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

With the quasi-flow property in hand (Lemma 11), we finally prove Proposition 9.

**Proof of Proposition 9** Let $\pi'_t$ be a policy of $[M]$ such that $\mathbb{E}[N'_t[s]]\pi'_t(a|[s]) = \mathbb{E}[N'_t([s], a)]$ — note that $\pi'_t[s]$ is uniquely defined when $\mathbb{E}[N'_t[s]] > 0$. For all $[s'] \in S[M]$, we have:

$$ \begin{align*} \sum_{\substack{x \equiv ([s], a) \\ \in \mathcal{X}[M]}} \mu_t[s] \pi'_t(x|[s]) \mathbf{p}([s']|x) &= \sum_{\substack{x \equiv ([s], a) \\ \in \mathcal{X}[M]}} \frac{\mathbb{E}[N'_t[s]] \pi'_t(x|[s])}{\mathbb{E}[\|N'_t\|_1]} \mathbf{p}([s']|x) \\ &\stackrel{\circ 1}{=} \sum_{x \notin \mathcal{X}_{\pi}} \frac{\mathbb{E}[N_t(x)]}{\mathbb{E}[\|N'_t\|_1]} \mathbf{p}([s']|x) \\ &\stackrel{\circ 2}{=} \sum_{x \notin \mathcal{X}_{\pi}} \sum_{s'' \in [s']_{\circ 1}} \frac{\mathbb{E}[N_t(x)]}{\mathbb{E}[\|N'_t\|_1]} \mathbf{p}(s''|x) \\ &= \sum_{x \notin \mathcal{X}_{\pi}} \sum_{s'' \in [s']_{\circ 1}} \frac{\mathbb{E}[N_t(x) \hat{\mathbf{p}}_t(s''|x)] + \mathbb{E}[N_t(x)(\mathbf{p}(s''|x) - \hat{\mathbf{p}}_t(s''|x))]}{\mathbb{E}[\|N'_t\|_1]} \\ &\stackrel{\circ 3}{=} \sum_{x \notin \mathcal{X}_{\pi}} \sum_{s'' \in [s']_{\circ 1}} \left( \frac{\mathbb{E}[N_{t+1}(x; s'')]}{\mathbb{E}[\|N'_t\|_1]} + o\left(1 + \frac{\mathbb{E}[N_t(x)]}{\mathbb{E}[\|N'_t\|_1]}\right) \right) \\ &= \sum_{x \notin \mathcal{X}_{\pi}} \sum_{s'' \in [s']_{\circ 1}} \left( \frac{\mathbb{E}[N_{t+1}(x; s'')]}{\mathbb{E}[\|N'_t\|_1]} + o(1) \right) \\ &\stackrel{\circ 4}{=} \sum_{x \notin \mathcal{X}_{\pi}} \sum_{s'' \in [s']_{\circ 1}} \left( \frac{\mathbb{E}[N'_{t+1}(x; s'')]}{\mathbb{E}[\|N'_t\|_1]} + o(1) \right) \end{align*} $$
$$ \stackrel{\circ 5}{=} \sum_{s'' \in [s']}{\left( \frac{\mathbb{E}[N'_{t+1}(s'')]}{\mathbb{E}[\|N'_{t}\|_1]} + o(1) \right)} \stackrel{\circ 6}{=} \mu_t[s'] + o(1) $$

where (°1) follows by definition of $\pi'_t$ and of $N'_t$, see Equation (13); (°2) unfolds the contraction; (°3) follows from a technical concentration result (Lemma A.1), that requires $\mathbb{E}[\sum_{x \notin \mathcal{X}_\pi} N_t(x)] = \Omega(\log(t))$, that is satisfied indeed by assumption; (°4) holds by definition of $N'_t$; (°5) stems from the quasi-flow property of $N'_t$ on $\mathbf{M}$ (Lemma 11); and (°6) folds back the contraction.

We have shown that for all $[s] \in \mathcal{S}[\mathbf{M}]$, $\sum_x \mu_t(x)\mathbf{p}([s]|x) = \mu_t[s] + o(1)$.

Denoting $\varphi(\mu) := \max_{[s] \in \mathcal{S}[\mathbf{M}]} |\mu[s] - \sum_x \mu(x)\mathbf{p}([s]|x)|$, we have $\varphi(\mu_t) \to 0$. The function $\varphi$ is continuous, $\mathcal{P}(\mathcal{X})$ is compact and $\varphi(\mu) = 0$ is equivalent to $\mu \in \text{Inv}(\mathbf{M}/\mathcal{X}_\pi)$. Because $\text{Inv}(\mathbf{M}/\mathcal{X}_\pi)$ is closed in $\mathcal{P}(\mathcal{X})$, we deduce that “$\varphi(\mu_t) \to 0$” implies “$\mu_t \to \text{Inv}(\mathbf{M}/\mathcal{X}_\pi)$.” $\blacksquare$

## 4.4 A First Regret Lower Bound with Contracted Invariant Measures

The components from the three previous sections are combined together into a single result. By taking account of the required exploration via information constraints (Proposition 4), neglecting the effects due to coexploration (Proposition 7) by merely simplifying the alternative set to the confusing set, and using that the structure of visit counts outside of optimal pairs converges to an invariant measure of $\mathbf{M}/\mathcal{X}_\star(\mathbf{M})$ (Corollary 10, i.e., navigation constraints), we obtain the result below. This is the first half of Theorem 3.

**Theorem 12** (Lower bound with contracted measures). Let $\mathbf{M} \in \mathcal{M}$ be a communicating MDP. Regardless of the initial state $s_0 \in \mathcal{S}$, the regret of every consistent algorithm $\mathcal{A}$ satisfies $\liminf_{T \to \infty} \text{Reg}(T; \mathcal{A}, \mathbf{M}, s_0) \log^{-1}(T) \ge K(\mathbf{M})$ where $K(\mathbf{M}) \in [0, \infty]$ is equal to:

$$ \inf \left\{ \sum_{x \in \mathcal{X}} \mu(x) \mathbf{\Delta}_\star(x) : \mu \in \text{Inv}(\mathbf{M}/\mathcal{X}_\star(\mathbf{M})) \text{ and } \inf_{\mathbf{M}^\dagger \in \text{Cnf}(\mathbf{M})} \sum_{x \in \mathcal{X}} \mu(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^\dagger(x)) \ge 1 \right\}. \quad (16) $$

**Proof** Consider a consistent algorithm $\mathcal{A}$. Introduce the quantities

$$ \mu_T(x) := \frac{\mathbb{1}(x \notin \mathcal{X}_\star(\mathbf{M})) \mathbb{E}_{s_0}^{\mathbf{M}, \mathcal{A}}[N_{T+1}(x)]}{\mathbb{E}_{s_0}^{\mathbf{M}, \mathcal{A}}[\sum_{x' \notin \mathcal{X}_\star(\mathbf{M})} N_{T+1}(x')]}, \quad \text{and} \quad \lambda_T := \frac{\mathbb{E}_{s_0}^{\mathbf{M}, \mathcal{A}}[\sum_{x \notin \mathcal{X}_\star(\mathbf{M})} N_{T+1}(x)]}{\log(T)} $$

as well as the scaled expected regret $\psi(T) := \text{Reg}(T; \mathbf{M}, \mathcal{A}, s_0) \log(T)^{-1}$.

Note that $\psi(T) = \lambda_T \sum_{x \notin \mathcal{X}_\star(\mathbf{M})} \mu_T(x) \mathbf{\Delta}_\star(x; \mathbf{M})$.

Let $\psi_\infty := \liminf_{T \to \infty} \psi(T)$ and let $(T_n) \in \mathbb{N}^\mathbb{N}$ be such that $\lim_{n \to \infty} \psi(T_n) = \psi_\infty$. Remark that $\limsup_{n \to \infty} \lambda_{T_n} \le \alpha \cdot \psi_\infty$ as a consequence of Lemma 8, where $\alpha > 0$ is the constant provided by Lemma 8. Up to extracting a subsequence of $(T_n)$, we can assume that $\lambda_{T_n}$ converges to some $\lambda_\infty \in [0, \alpha \cdot \psi_\infty]$. Similarly, since $(\mu_T)$ evolves within the compact space $[0, 1]^\mathcal{X}$, we can assume that $\mu_{T_n}$ converges to some $\mu_\infty \in [0, 1]^\mathcal{X}$ up to extracting a subsequence of $(T_n)$. By Corollary 10, every limit point of $(\mu_T)$ belongs to $\text{Inv}(\mathbf{M}/\mathcal{X}_\star(\mathbf{M}))$ which is closed, so $\mu_\infty \in \text{Inv}(\mathbf{M}/\mathcal{X}_\star(\mathbf{M}))$. By Proposition 4, the sequence $(\lambda_T, \mu_T)_{T \ge 1}$ satisfies

$$ \forall T \ge 1, \quad \inf_{\mathbf{M}^\dagger \in \text{Cnf}(\mathbf{M})} \left\{ \lambda_T \sum_{x \in \mathcal{X}} \mu_T(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^\dagger(x)) \right\} \ge 1, \quad (17) $$
so the limit $\lambda_{\infty}\mu_{\infty} \in \text{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M}))$ must satisfy (17) as well.

In tandem with $\psi_{\infty} = \lambda_{\infty} \sum_{x \in \mathcal{X}} \mu_{\infty}(x) \Delta_{\star}(x; \mathbf{M})$, we conclude that $\psi_{\infty} \ge K(\mathbf{M})$. ■

## 4.5 A Second Regret Lower Bound with Non-contracted Invariant Measures

While minors play a central role in the decomposition of the execution consistent learning agents, we show that they can eventually be dropped in the lower bound, for a conceptually simpler result. Combined with Theorem 12, Proposition 13 below provides the second half of our main result, Theorem 3.

**Proposition 13 (Removing the contraction).** *The regret lower bound $K(\mathbf{M})$ of Theorem 12 is equal to $K_{\star}(\mathbf{M})$ in Theorem 3, i.e.,

$$ K(\mathbf{M}) = K_{\star}(\mathbf{M}) \\ = \inf \left\{ \sum_{x \in \mathcal{X}} \mu(x) \Delta_{\star}(x) : \mu \in \text{Inv}(\mathbf{M}) \text{ and } \inf_{\mathbf{M}^{\dagger} \in \text{Cnf}(\mathbf{M})} \sum_{x \in \mathcal{X}} \mu(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x)) \ge 1 \right\}. \quad (18) $$

The contraction of the navigation constraint "$\mu \in \text{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M}))$" can be discarded by using that $\Delta_{\star}(x)$ is null for $x \in \mathcal{X}_{\star}(\mathbf{M})$. As such, invariant measures of the minor $\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M})$ can be represented by invariant measures of the initial model $\mathbf{M}$. This is done by Lemma 14.

**Lemma 14.** *Denote $u|_{\mathcal{X}\setminus\mathcal{X}_{\star}(\mathbf{M})}$ the truncation of $u \in \mathbb{R}^{\mathcal{X}}$ to pairs of $\mathcal{X} \setminus \mathcal{X}_{\star}(\mathbf{M})$ and extend the notations to subsets of $\mathbb{R}^{\mathcal{X}}$. Then $\text{Inv}(\mathbf{M})|_{\mathcal{X}\setminus\mathcal{X}_{\star}(\mathbf{M})} = \text{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M}))|_{\mathcal{X}\setminus\mathcal{X}_{\star}(\mathbf{M})}$.*

**Proof** By looking as $\text{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M}))$ and $\text{Inv}(\mathbf{M})$ as polytopes of $\mathbb{R}_{+}^{\mathcal{X}}$ spawned by constraints of the form $\sum_{x' \in \mathcal{X}} \mu(x')\mathbf{p}(s|x') = \sum_{a \in \mathcal{A}(s)} \mu(s, a)$ indexed by states $s$, we see that $\text{Inv}(\mathbf{M}) \subseteq \text{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M}))$; indeed, by construction of contractions (Definition 8), the constraints spawning $\text{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M}))$ are a subset of those spawning $\text{Inv}(\mathbf{M})$.

We focus on the harder inclusion, $\text{Inv}(\mathbf{M})|_{\mathcal{X}\setminus\mathcal{X}_{\star}(\mathbf{M})} \supseteq \text{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M}))|_{\mathcal{X}\setminus\mathcal{X}_{\star}(\mathbf{M})}$.

Up to iterating the process on the communicating components of $\mathcal{X}_{\star}(\mathbf{M})$, we assume that $\mathcal{X}_{0} := \mathcal{X}_{\star}(\mathbf{M})$ induces a communicating model $\mathbf{M}|_{\mathcal{X}_{0}}$. Pick $[\mu] \in \text{Inv}(\mathbf{M}/\mathcal{X}_{0})$. We claim:

$$ \exists \mu \in \text{Inv}(\mathbf{M}), \forall x \notin \mathcal{X}_0, \quad [\mu](x) = \mu(x). \quad (19) $$

We show Equation (19). Denote $\mathcal{S}_{0} := \{s : \exists a, (s, a) \in \mathcal{X}_{0}\}$ the states in which $\mathcal{X}_{0}$ is rooted. In $[\mathbf{M}] := \mathbf{M}/\mathcal{X}_{0}$, we have $[\mathbf{p}]([\mathcal{S}_{0}]|x_{0}) = 1$ for all $x_{0} \in \mathcal{X}_{0}$. So, we can assume $[\mu](x_{0}) = 0$ without loss of generality. For $s_{0} \in \mathcal{S}_{0}$, introduce

$$ \alpha(s) := \sum_{a \in \mathcal{A}(s_0)} [\mu](s_0, a) - \sum_{x \in \mathcal{X}} [\mu](x) \mathbf{p}(s_0|x). $$

Observe that $\sum_{s_{0} \in \mathcal{S}_{0}} \alpha(s_{0}) = 0$ since $[\mu]$ is an invariant measure of $[\mathbf{M}] \equiv \mathbf{M}/\mathcal{X}_{0}$. It is enough to find $\mu_{0} \in \mathbb{R}^{\mathcal{X}_{0}}$ such that

$$ \mu_0 \ge 0 \quad \text{and} \quad \forall s_0 \in \mathcal{S}_0, \quad \sum_{x_0 \in \mathcal{X}_0} \mu_0(x_0) \mathbf{p}(s_0|x_0) = \sum_{a_0:(s_0,a_0) \in \mathcal{X}_0} \mu(s_0,a_0) + \alpha(s_0); \quad (20) $$
then $\mu \in \mathbb{R}^{\mathcal{X}}$ given by $\mu(x) = \mu_0(x)$ if $x \in \mathcal{X}_0$ and $[\mu](x)$ if $x \notin \mathcal{X}_0$ will be solution. Assume that (20) has no solution. By Farkas' Lemma, there exists $\nu_0 \in \mathbb{R}^{S_0}$ such that:

$$ \sum_{s_0 \in S_0} \nu_0(s_0) \alpha(s_0) < 0 \quad \text{and} \quad \forall (s_0, a_0) \in \mathcal{X}_0, \quad \sum_{s'_0 \in S_0} \nu_0(s_0) (\mathbf{p}(s'_0|s_0, a_0) - \mathbf{1}(s'_0 = s_0)) \geq 0. \tag{21} $$

Let $\pi_0$ the policy picking its actions uniformly in $\mathcal{X}_0$ from $S_0$. The second condition can be rewritten as $\mathbf{p}_{\pi_0}(\mathbf{M}|\mathcal{X}_0)\nu_0 \geq \nu_0$ so by induction, $\bar{\mathbf{p}}_{\pi_0}(\mathbf{M}|\mathcal{X}_0)\nu_0 \geq \nu_0$ where $\bar{\mathbf{p}}_{\pi_0} := \lim_{\bar{T}} \frac{1}{\bar{T}} \sum_{t=1}^{\bar{T}} \mathbf{p}_{\pi_0}^{t-1}$. Because $\mathcal{X}_0$ is communicating, $\bar{\mathbf{p}}_{\pi_0}(\mathbf{M}|\mathcal{X}_0)$ has full support and $\text{sp}(\nu_0) = 0$. But $\sum_{s_0 \in S_0} \alpha(s_0) = 0$ so $\sum_{s_0 \in S_0} \nu_0(s_0)\alpha(s_0) = 0$, contradicting (21). Hence (19). $\blacksquare$

# 5 Instanciation of the Lower Bound in Classical Settings

In many scenarios, the environment of interest $\mathbf{M}$ and/or the class of environments $\mathcal{M}$ have special structures. Then, the regret lower bound $K_*(\mathbf{M}; \mathcal{M})$ may be easier to describe, and such alternative descriptions can ease the design of asymptotically optimal learning agents.

In this section, we discuss such examples, such as multi-armed bandits, ergodic models, known transition kernel problems and beyond. Our bound is compared to existing results in the literature, and we discuss how the optimization problems (LB) and (LB') can be decomposed both in their navigation constraint “$\mu \in \text{Inv}(\mathbf{M})$” or “$\mu \in \text{Inv}(\mathbf{M}/\mathcal{X}_*(\mathbf{M}))$” as well as in their information constraint “$\forall \mathbf{M}^\dagger \in \text{Cnf}(\mathbf{M})$, $\sum_x \mu(x)\text{KL}(\mathbf{M}(x)||\mathbf{M}^\dagger(x)) \geq 1$.”

## 5.1 Example: Multi-Armed Bandits

Instances of **multi-armed bandits** are equivalent to single-state Markov decision processes, i.e., with pair space $\mathcal{X} = \{1\} \times \{1, \dots, A\}$. In this paragraph, we fix $\mathcal{X} = \{1\} \times \{1, \dots, A\}$ and let $\mathcal{M}$ the space of MDPs with Bernoulli rewards and pair space $\mathcal{X}$, vis.,

$$ \mathcal{M}_{\text{bandits}} \approx \bigcup_{\mathbf{m} \in [0,1]^\mathcal{X}} \prod_{x \in \mathcal{X}} \{\text{Bernoulli}(\mathbf{m}(x))\}. \tag{22} $$

Instantiating our lower bound (Theorem 3), we retrieve the celebrated regret lower bound of Lai and Robbins (1985).

**Corollary 15** (Lai and Robbins (1985)). Let $\mathcal{M}_{\text{bandits}}$ the space of MDPs with Bernoulli rewards and pair space $\mathcal{X}$ as in (22). Let $\mathbf{M} \in \mathcal{M}_{\text{bandits}}$ such that $\max(\mathbf{m}) < 1$. Then:

$$ K_*(\mathbf{M}; \mathcal{M}) = \sum_{x \in \mathcal{X}} \frac{\Delta_*(x; \mathbf{M})}{\text{kl}(\mathbf{m}(x)||\max(\mathbf{m}))} \tag{23} $$

with the convention $0/0 = 0$ and $\text{kl}(x, y) := x \log(\frac{x}{y}) + (1-x) \log(\frac{1-x}{1-y})$.

**Proof** Given $\mathbf{M} \in \mathcal{M}_{\text{bandits}}$, a policy is a choice of action $a$ (usually called **arm**) and its gain $\mathbf{m}(1, a)$, so the gap associated to the pair $x \equiv (1, a)$ is $\Delta_*(x) = \max(\mathbf{m}) - \mathbf{m}(x)$. We see that $\text{Inv}(\mathbf{M}) = \mathbb{R}_+^\mathcal{X}$, so that multi-armed bandits have trivial navigational structure. Moreover, confusing models $\mathbf{M}^\dagger \in \text{Cnf}(\mathbf{M})$ are precisely models such that $\exists x \notin \mathcal{X}_*(\mathbf{M})$ with $\mathbf{m}^\dagger(x) > \max(\mathbf{m}) = \mathbf{g}_*(\mathbf{M})$. Combined, $K_*(\mathbf{M}; \mathcal{M}_{\text{bandit}})$ is equal to

$$ \inf \left\{ \sum_{x \in \mathcal{X}} \mu(x) \Delta_*(x; \mathbf{M}) : \mu \in \mathbb{R}_+^\mathcal{X} \text{ and } \forall \mathbf{M}^\dagger \in \text{Cnf}(\mathbf{M}), \sum_{x \in \mathcal{X}} \mu(x) \text{kl}(\mathbf{m}(x)||\mathbf{m}^\dagger(x)) \geq 1 \right\}. $$
Remark that any $M^\dagger \in \text{Cnf}(M)$ can be simplified into a $M^\ddag \in \text{Cnf}(M)$ where $M$ and $M^\ddag$ only differ at one pair $x$ (the suboptimal pair of $M$ that is made optimal in $M^\ddag$), consisting in any pair such that $m^\dagger(x) > \max(m)$. Also, it follows $\text{Cnf}(M) \neq \emptyset$ if, and only if $\max(m) < 1$ leading to the well-known interior condition "$\max(m) < 1$". We conclude by using the continuity of the function $m^\dagger(x) \mapsto \text{kl}(m(x) || m^\dagger(x))$ on $(0, 1)$. ■

**Discussion.** While Corollary 15 is specific to bandits with Bernoulli rewards, it can be straightforwardly generalized to larger class of bandits (single parameter exponential families or semi-bounded rewards) in which case the denominator $\text{kl}(m(x) || \max(m))$ is changed to $\inf\{\text{KL}(\mathbf{r}(x) || \mathbf{r}^\dagger(x)) : m^\dagger(x) > \max(m)\}$ where $\mathbf{r}^\dagger(x)$ goes other the possible reward distributions on the pair $x$.

Several observations can be made regarding Equation (23).

(1) The regret lower bound has a closed-form expression that can easily be evaluated.

(2) Exploration constraints are trivial in multi-armed bandits $\text{Inv}(M) = \mathbb{R}_+^\chi$.

(3) Information constraints are pair-wisely decoupled (or indexed) and are equivalent to $|\chi|$ linear constraints on $\mu$, all of the form $\mu(x) \ge (\text{kl}(m(x) || \max(m)))^{-1}$.

The properties (1-3) are not always satisfied. As a matter fact, (1) and (3) may fail when considering $K_*(M; M')$ for $M' \subsetneq M_{\text{bandits}}$ (structured bandit problems). Meanwhile, (2) only depends on $M$. All together, these properties are arguably what makes multi-armed bandits significatively easier to learn than Markov decision processes. Nonetheless, multi-armed bandits are not the only classes of model spaces with such properties.

## 5.2 Example: (Optimally) Recurrent Models, or Navigation-Free Models

The property (2) in Section 5.1 is written as $\text{Inv}(M) = \mathbb{R}_+^\chi$, but according to (LB) and (LB') in Theorem 3, we could also see it as $\text{Inv}(M/\chi_*(M)) = \mathbb{R}_+^\chi$. This property only depends on $M$ and will be referred to as the navigation-free property, because the minor $M/\chi_*(M)$ is a bandit. When the environment is navigation-free, then one can commute between any pair with zero cost. This motivates the definition below.

**Definition 9 (Optimally recurrent MDPs).** We say that a model $M$ is optimally recurrent if there exists a gain optimal policy $\pi^*$ whose recurrent states are $S$; or equivalently, if $\chi_*(M)$ covers all the states of $M$; or equivalently again, if $\chi_*(M) = \chi_*(M)$.

By definition, $M$ is optimally recurrent if, and only if $M/\chi_*$ is single state. As motivated, multi-armed bandits are optimally recurrent. Ergodic models are a more general example of optimally recurrent models, although not every optimally recurrent environment is ergodic. When the instance is optimally recurrent, the navigation and information constraints can be greatly simplified. Given an optimally recurrent model $M \in \mathcal{M}$ and $(s, a) \in \mathcal{X}_-(M)$, denote:

$$C(M, s, a) := \inf_{\tilde{\mathbf{r}}_{s,a}, \tilde{\mathbf{p}}_{s,a}} \{\text{KL}(\mathbf{r}_{s,a} || \tilde{\mathbf{r}}_{s,a}) + \text{KL}(\mathbf{p}_{s,a} || \tilde{\mathbf{p}}_{s,a}) : \tilde{\mathbf{m}}(s, a) + \tilde{\mathbf{p}}(s, a)\mathbf{b}_* > \mathbf{g}_*(s) + \mathbf{b}_*(s)\}$$

where $\mathbf{g}_*$ and $\mathbf{b}_*$ are respectively the optimal gain and bias vectors of $M$.
**Corollary 16** (Lower bound for optimally recurrent models). Assume that $\mathcal{M}$ the space of all communicating models with state-action space $\mathcal{X}$. If $\mathbf{M} \in \mathcal{M}$ is an optimally recurrent model, then

$$K_{\star}(\mathbf{M}) = \sum_{x \notin \mathcal{X}_{\star}(\mathbf{M})} \frac{\Delta_{\star}(x)}{C(\mathbf{M}, x)}.$$

**Proof** When $\mathbf{M}$ is optimally recurrent, $\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M})$ is a single-state Markov decision process, hence $\text{Inv}(\mathbf{M}/\mathcal{X}_{\star}(\mathbf{M})) = \mathbb{R}_{+}^{\mathcal{X}}$ meaning that the navigation constraints are trivial. We now simplify the information constraints using a policy improvement argument that is similar to (Burnetas and Katehakis, 1997). Let $\pi^{*} \in \Pi^{*}(\mathbf{M})$ with recurrent class $\mathcal{S}$ and pick a confusing model $\mathbf{M}^{\dagger} \in \text{Cnf}(\mathbf{M})$. We have $(s, \pi^{*}(s)) \in \mathcal{X}_{\star}(\mathbf{M})$ for all $s \in \mathcal{S}$, and because $\mathbf{M}$ and $\mathbf{M}^{\dagger}$ coincide on $\mathcal{X}_{\star}(\mathbf{M})$, it follows that the gain, bias, reward and kernel of $\pi^{*}$ are preserved in $\mathbf{M}^{\dagger}$. Yet $\pi^{*}$ is not gain optimal in $\mathbf{M}^{\dagger}$, so there must exist $(s, a) \in \mathcal{X}$ such that:

$$\mathbf{m}^{\dagger}(s, a) + \mathbf{p}^{\dagger}(s, a)\mathbf{b}_{\star}(\mathbf{M}) > \mathbf{g}_{\star}(s, \mathbf{M}) + \mathbf{b}_{\star}(s, \mathbf{M}).$$

Meanwhile, all states are recurrent under $\pi^{*}$ which is optimal in $\mathbf{M}$, so (1) $\mathcal{X}_{\star}(\mathbf{M}) = \mathcal{X}_{\star}(\mathbf{M})$ and (2) it is a fixpoint of the Bellman operator of $\mathbf{M}$, in particular $\mathbf{m}(s, a) + \mathbf{p}(s, a)\mathbf{b}_{\star}(\mathbf{M}) \le \mathbf{g}_{\star}(s, \mathbf{M}) + \mathbf{b}_{\star}(s, \mathbf{M})$. By (1), $\mathbf{M}$ and $\mathbf{M}^{\dagger}$ coincide on $\mathcal{X}_{\star}(\mathbf{M})$ so invoking (2), we must have $(s, a) \notin \mathcal{X}_{\star}(\mathbf{M})$. In the end, we obtain:

$$K(\mathbf{M}) = \inf \left\{ \sum_{x \in \mathcal{X}} \mu(x) \Delta_{\star}(x) : \mu \in \mathbb{R}_{+}^{\mathcal{X}} \text{ and } \forall (s, a) \in \mathcal{X}_{-}(\mathbf{M}), \mu(s, a)C(\mathbf{M}, s, a) \ge 1 \right\},$$

of which the solution is obvious.

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

**Discussion.** Just like for bandits indeed, we observe that when $\mathbf{M} \in \mathcal{M}$ is an optimally recurrent model, the navigation constraints become trivial $(\mu \in \mathbb{R}_{+}^{\mathcal{X}})$ and the information constraints are decoupled along sub-optimal pairs. We recover a regret lower-bound that is in closed form, navigation-free and with pair-wisely decoupled information constraints. In other words, the regret lower bound of optimally recurrent models is morally the same than the one in multi-armed bandits. Corollary 16 is a strict generalization of the well-known results of Burnetas and Katehakis (1997). The lower bound of Burnetas and Katehakis (1997) is similar to our, excepted that it only holds for **irreducible** (a.k.a. **recurrent**) $\mathbf{M}$, in the sense that all the states are recurrent under every policy in $\mathbf{M}$ — which is much stronger than the optimal recurrence assumption of Definition 9.

## 5.3 Example: Bandits with Switching Costs

We now go back to multi-armed bandits by adding switching costs. Multi-armed bandits with switching costs (Agrawal et al., 1988b; Jun, 2004; Brezzi and Lai, 2002; Ortner, 2010) consist in multi-armed bandits where a cost in induced every time the learning agent changes arm. Formally, a bandit with switching costs can be seen as a Markov decision process $\mathbf{M}$ with pair space $\mathcal{X} = \mathcal{S} \times \mathcal{S}$ where each state corresponds to an arm, and actions from a state are another choice of state. By choosing $s$ from $s$, one remains in $s$ and scores according to $\mathbf{r}(s, s)$ of positive mean; and by choosing $s' \neq s$ from $s$, one goes to $s'$ and pays a fixed
switching cost $\lambda > 0$. That is, given $s \neq s' \in S$,

$$ \mathbf{p}(s''|s, s) = \mathbf{1}(s'' = s), \quad \mathbf{p}(s''|s, s') = \mathbf{1}(s'' = s') \quad \text{and} \quad \mathbf{m}(s, s') = -\lambda. $$

For a fixed switching cost $\lambda > 0$ and a fixed set of arms $S$, we let $M_{SB}^{\lambda}$ be the collection of all multi-armed bandits with switching cost $\lambda$ and Bernoulli rewards, consisting in the set of Markov decision processes described above. With a similar rationale than in Section 5.1, we show that the regret lower bound can be put in closed form, meeting the known result of Agrawal et al. (1988b).

Indeed, just as for bandits, we can show that any confusing model $M^{\dagger} \in \text{Cnf}(M; M_{SB}^{\lambda})$ can be simplified into $M^{\ddagger}$ where $M$ and $M^{\ddagger}$ only differ at an optimal pair of $M^{\dagger}$. When rewards are Bernoulli, information constraints are therefore decoupled along states and can be written as:

$$ \forall s \in S, \quad \mu(s, s)\text{kl}(\mathbf{m}(s, s)\|\max(\mathbf{m})) \geq 1. \qquad (24) $$

Then, it is easy to see that the structure of bandits with switching cost is such that for all $\alpha \in \mathbb{R}_{+}^{S}$, there is $\mu \in \text{Inv}(M)$ such that $\mu(s, s) = \alpha(s)$. Moreover, just like for multi-armed bandit, the optimal gain is $g_{\star}(M) = \max(\mathbf{m})$ regardless of the switching cost. Combining it all with (24), we obtain Corollary 17.

**Corollary 17 (Agrawal et al. (1988b)).** Fix $\lambda > 0$ and let $M_{SB}^{\lambda}$ the space of all Bernoulli bandits with switching costs $\lambda$ and arms $S$. Let $M \in M_{SB}^{\lambda}$ such that $\max(\mathbf{m}) < 1$. Then:

$$ K_{\star}(M; M_{SB}^{\lambda}) = \sum_{x \in \mathcal{X}} \frac{\Delta_{\star}(x; M)}{\text{kl}(\mathbf{m}(x)\|\max(\mathbf{m}))}. \qquad (25) $$

**Discussion.** Remark that despite the fact that $\text{Inv}(M) \neq \mathbb{R}_{+}^{S}$, the navigation constraints do not appear in Equation (25). This is because the information constraints do not constrain $\mu$ outside of $\{(s, s) : s \in S\}$, hence the optimal exploration measure puts no mass on $\mathcal{X} \setminus \{(s, s) : s \in S\}$ which is indeed where navigation is constrained. This is linked to the surprising fact that $\lambda$ is absent from $K_{\star}(M; M_{SB}^{\lambda})$, hence that the optimal asymptotic regret does not depend on switching costs. In other words, our main regret lower bound (Theorem 3) claims that switching costs are negligible. At first sight, it is not obvious that there exists a strongly consistent algorithm with asymptotic regrets reaching $K_{\star}(M; M_{SB}^{\lambda})$, or independent of $\lambda$ at all — we refer the interested reader to (Agrawal et al., 1988b; Brezzi and Lai, 2002) for more insight on the subject.

## 5.4 Example: A Priori Known Transition Kernel

Beyond optimally recurrent models, the lower bound may be impossible to decouple in a pairwise fashion in general. It may have no closed-form expression and navigation constraints may be non-trivial. One setting in which the lower bound cannot be decoupled, and which is slightly simpler than the general setting yet, is when the transition kernel is known or deterministic. This setting is the subject of a few works (Saber et al., 2024; Ortner, 2010; Tranos and Proutiere, 2021). (Tranos and Proutiere, 2021) provides a lower bound for deterministic transition models and while (Saber et al., 2024) provides model dependent regret analysis of their method in the more general setting where only the reward function has to be learned, no lower bound was known in this more general setting.
**Definition 10** (Fixed kernel spaces). Fix a pair space $\mathcal{X}$. A set of MDPs $\mathcal{M}$ with pair space $\mathcal{X}$ is called a **fixed kernel space** if all elements of $\mathcal{M}$ have the same transition kernel, i.e., $\forall \mathbf{M}, \mathbf{M}' \in \mathcal{M}, \mathbf{p} = \mathbf{p}'$. We say that it is **deterministic kernel space** if, in addition, $\mathbf{p}(s'|s, a) \in \{0, 1\}$ for every transition triplet $(s, a, s')$.

We start by relating our results to the lower bound of Tranos and Proutiere (2021). For deterministic kernel space, (Tranos and Proutiere, 2021, Theorem 1) provides a model dependent lower bound and already make apparent the information and navigation constraints in a form that are similar to Theorem 3, although the objective function is written differently. In our set of notations, their result can be adapted as follows.

**Corollary 18** (Tranos and Proutiere (2021)). Let $\mathcal{M}$ a deterministic kernel space and fix $\mathbf{M} \in \mathcal{M}$. The regret of every strongly consistent learning agent satisfies $\text{Reg}(T; \mathcal{A}, \mathbf{M}) \gtrsim C(\mathbf{M}; \mathcal{M}) \log(T)$ where $C(\mathbf{M}; \mathcal{M})$ is:

$$ \inf \left\{ \sum_{x \in \mathcal{X}} \mu(x)(\mathbf{g}_{\star} - \mathbf{m}(x)) : \mu \in \text{Inv}(\mathbf{M}) \text{ and } \inf_{\mathbf{M}^{\dagger} \in \text{Cnf}(\mathbf{M}; \mathcal{M})} \sum_{x \in \mathcal{X}} \mu(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x)) \geq 1 \right\}. $$

**Proof** We have to show that $K_{\star}(\mathbf{M}; \mathcal{M}) = C(\mathbf{M}; \mathcal{M})$, that is, that $\mathbf{\Delta}_{\star}(\mathbf{M})$ can be changed to $\mathbf{g}_{\star} - \mathbf{m}(x)$ in Theorem 3. We have

$$ \begin{aligned} & \sum_{x \in \mathcal{X}} \mu(x)(\mathbf{g}_{\star} - \mathbf{m}(x)) \\ & \stackrel{\circ 1}{=} \sum_{(s,a) \in \mathcal{X}} \mu(s,a)(\mathbf{\Delta}_{\star}(s,a) + (\mathbf{p}(s,a) - e_s)\mathbf{b}_{\star}) \\ & = \sum_{x \in \mathcal{X}} \mu(x)\mathbf{\Delta}_{\star}(x) + \sum_{s' \in s} \mathbf{b}_{\star}(s') \sum_{(s,a) \in \mathcal{X}} \mu(s,a)\mathbf{p}(s'|s,a) - \sum_{s \in \mathcal{S}} \mathbf{b}_{\star}(s) \sum_{a \in \mathcal{A}(s)} \mu(s,a) \\ & \stackrel{\circ 2}{=} \sum_{x \in \mathcal{X}} \mu(x)\mathbf{\Delta}_{\star}(x) + \sum_{s' \in \mathcal{S}} \mathbf{b}_{\star}(s') \sum_{a \in \mathcal{A}(s')} \mu(s',a) - \sum_{s \in \mathcal{S}} \mathbf{b}_{\star}(s) \sum_{a \in \mathcal{A}(s)} \mu(s,a) \\ & = \sum_{x \in \mathcal{X}} \mu(x)\mathbf{\Delta}_{\star}(x) \end{aligned} $$

where (°1) follows from the Poisson equation and (°2) uses that $\mu \in \text{Inv}(\mathbf{M})$. ■

In particular, our results generalizes (Tranos and Proutiere, 2021) to fixed kernel spaces.

## 5.5 A Policy-wise Decomposition of the Lower Bound

In this last section, we consider a policy-wise writing-style of the lower bound, by decomposing both the confusing set (i.e., information constraints) and the set of invariant measures (i.e., navigation constraints) relatively to policies. Not only the expression of the lower bound in terms of policies has been the historical approach (Lai and Robbins, 1985; Agrawal et al., 1988a), but it also echoes an aspect of design of many model-based algorithms (Agrawal et al., 1988a; Auer et al., 2009; Ouyang et al., 2017; Saber et al., 2024): they iterate well-chosen deterministic policies for non-trivial periods of time called *episodes*. In that regard, the policy-wise lower bound is interesting in that it is very instructive regarding the idealistic way to choose policies in these algorithms, especially for exploration purposes.
We decompose the lower bound using unichain policies. Recall that a policy $\pi \in \Pi$ is **unichain** if it has a unique recurrent component, in which case its gain function $g_\pi$ does not depend on the initial state and it has a unique probability invariant measure, given by $\mu_\pi(x) := \lim_{T \to \infty} \frac{1}{T} \mathbb{E}_{s_0}^{M, \pi}[\sum_{t=1}^T 1(X_t = x)]$ independently of the initialization $s_0 \in \mathcal{S}$. Then, the idea of the revised lower bound is two-fold.

(1) Every invariant measure $\mu \in \text{Inv}(\mathbf{M})$ can be decomposed into a sum of invariant measures of unichain policies, i.e.,

$$ \text{Inv}(\mathbf{M}) = \mathbb{R}_+ \cdot \text{conv}(\{\mu_\pi : \pi \in \Pi_u\}) \qquad (26) $$

where $\text{conv}(\cdot)$ denotes the convex hull and $\Pi_u \equiv \Pi_u(\mathbf{M})$ the set of unichain policies of $\mathbf{M}$. This follows from an observation of Boone (2025), see their Proposition A.10.

(2) The confusing can be decomposed relatively to policies. Indeed, if $\mathbf{M}^\dagger$ is confusing, then there exists a policy which is optimal in $\mathbf{M}^\dagger$ and sub-optimal in $\mathbf{M}$. We show

$$ \text{Cnf}(\mathbf{M}) = \bigcup_{\pi^\dagger \notin \Pi^*(\mathbf{M})} \text{Cnf}_{\pi^\dagger}(\mathbf{M}), \quad \text{Cnf}_{\pi^\dagger}(\mathbf{M}) := \{\mathbf{M}^\dagger \in \text{Cnf}(\mathbf{M}) : \mathbf{g}_{\pi^\dagger}(\mathbf{M}^\dagger) > \mathbf{g}_*(\mathbf{M})\}. \quad (27) $$

Decomposing the confusing set (or the alternative set) relatively to policies is not an idea of our own, and can be found in many works, including (Marjani and Proutiere, 2021; Al Marjani et al., 2021; Saber et al., 2024).

For self-containedness, the assertions (1-2) are justified in Appendix A.3.

Combining the two, we obtain Theorem 19, that holds for arbitrary set of MDPs $\mathcal{M}$.

**Theorem 19 (Policy-wise lower bound).** Let $\mathbf{M} \in \mathcal{M}$ be communicating. Let $\Pi_u$ be the set of unichain policies in $\mathbf{M}$. We have

$$ K(\mathbf{M}) = \inf_{\alpha \in \mathcal{P}(\Pi_u)} \frac{\sum_{\pi \in \Pi_u} \alpha_\pi \cdot (\mathbf{g}_* - \mathbf{g}_\pi)}{\inf_{\pi^\dagger \notin \Pi^*(\mathbf{M})} \inf_{\mathbf{M}^\dagger \in \text{Cnf}_{\pi^\dagger}(\mathbf{M})} \sum_{\pi \in \Pi_u} \alpha_\pi \sum_{x \in \mathcal{X}} \mu_\pi(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^\dagger(x))} \cdot (\text{LB}_\star^\pi) $$

**Proof** Because the constraint function $\psi : \mu \mapsto \inf_{\mathbf{M}^\dagger \in \text{Cnf}(\mathbf{M})} \sum_{x \in \mathcal{X}} \mu(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^\dagger(x))$ is homogeneous of degree one, observe that the regret lower bound (LB) can be written as

$$ K(\mathbf{M}) := \inf_{\mu \in \text{Inv}(\mathbf{M})} \left\{ \frac{\sum_{x \in \mathcal{X}} \mu(x) \mathbf{\Delta}_*(x)}{\psi(\mu)} \right\} = \inf_{\mu \in \text{Inv}(\mathbf{M}) \cap \mathcal{P}(\mathcal{X})} \left\{ \frac{\sum_{x \in \mathcal{X}} \mu(x) \mathbf{\Delta}_*(x)}{\psi(\mu)} \right\}. \quad (28) $$

Since $\text{Inv}(\mathbf{M}) \cap \mathcal{P}(\mathcal{X}) = \text{conv}(\{\mu_\pi : \pi \in \Pi_u\})$ by Equation (26), for every $\mu \in \text{Inv}(\mathbf{M}) \cap \mathcal{P}(\mathcal{X})$, there exists $(\alpha_\pi) \in \mathcal{P}(\Pi_u)$ such that $\mu = \sum_{\pi \in \Pi_u} \alpha_\pi \mu_\pi$. Moreover, following (27), we have

$$ \psi(\mu) = \inf_{\pi^\dagger \notin \Pi^*(\mathbf{M})} \inf_{\mathbf{M}^\dagger \in \text{Cnf}_{\pi^\dagger}(\mathbf{M})} \sum_{x \in \mathcal{X}} \sum_{\pi \in \Pi_u} \alpha_\pi \mu_\pi(x) \cdot \text{KL}(\mathbf{M}(x) || \mathbf{M}^\dagger(x)). \quad (29) $$

By combining Equations (28) and (29), we obtain

$$ K(\mathbf{M}) = \inf_{\alpha \in \mathcal{P}(\Pi_u)} \left\{ \frac{\sum_{\pi \in \Pi_u} \alpha_\pi \sum_{x \in \mathcal{X}} \mu_\pi(x) \mathbf{\Delta}_*(x)}{\inf_{\pi^\dagger \notin \Pi^*(\mathbf{M})} \inf_{\mathbf{M}^\dagger \in \text{Cnf}_{\pi^\dagger}(\mathbf{M})} \sum_{x \in \mathcal{X}} \sum_{\pi \in \Pi_u} \alpha_\pi \mu_\pi(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^\dagger(x))} \right\}. $$
What is left to check is that $\Delta_{\pi} := \sum_{x \in \mathcal{X}} \mu_{\pi}(x) \Delta_{\star}(x) = g_{\star} - g_{\pi}$ for every unichain policy $\pi \in \Pi_u$. This is a direct consequence of the definition the Bellman gaps. Indeed, on the one hand, $\mathbb{E}^{M,\pi}[\sum_{t=1}^T \Delta_{\star}(X_t)] = \Delta_{\pi}T + o(T)$ by definition of $\mu_{\pi}$; and on the other hand, $\Delta_{\star}(X_t) = \mathbb{E}^{M,\pi}[g_{\star} - R_t + b_{\star}(S_t) - b_{\star}(S_{t+1})|X_t]$ by definition of $\Delta_{\star}$. By Tower Property, we find that $\Delta_{\pi}T = (g_{\star} - g_{\pi})T + o(T)$, hence the result. ■

**Discussion.** The lower bound of Theorem 19 readily generalizes the results of Agrawal et al. (1988a); Graves and Lai (1997) beyond the scope of ergodic Markov decision processes. The quantity $\alpha_{\pi}$ can be interpreted as the amount of time (in logarithmic scale) that the algorithm spends playing the policy $\pi$. This interpretation is especially appealing when every policy is recurrent, because then, a reference state can be used to synchronize every policy, so that no switching cost is due to switching policies — this idea is crucial to the asymptotically optimal algorithm of Agrawal et al. (1988a).

Furthermore, in the denominator of Equation (LB$^{\pi}_{\star}$), we recognize in

$$ \inf_{\mathbf{M}^{\dagger} \in \text{Cnf}_{\pi^{\dagger}}(\mathbf{M})} \sum_{\pi \in \Pi_u} \sum_{x \in \mathcal{X}} \alpha_{\pi} \mu_{\pi}(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x)) $$

the *unlikelihood of optimality* of (Pesquerel, 2023, Definition 3.1.23), which is a crucial quantity that appears in multiple state-of-the-art algorithms, such as IMED-RL (Pesquerel and Maillard, 2022) or IMED-KD (Saber et al., 2024). It is when this quantity can be computed efficiently for every policy $\pi^{\dagger}$, that the form of Theorem 19 is especially pertinent.

**Fixed kernel spaces, confusing sets and convexity.** We conclude this section highlighting a case where (LB$^{\pi}_{\star}$) is especially fruitful: when the space $\mathcal{M}$ is a convex fixed kernel space, then $\text{Cnf}_{\pi^{\dagger}}(\mathbf{M}; \mathcal{M})$ is a convex set. Furthermore, the infimum of $\sum_{x \in \mathcal{X}} \mu(x) \text{KL}(\mathbf{M}(x) || \mathbf{M}^{\dagger}(x))$ over $\mathbf{M}^{\dagger} \in \text{Cnf}_{\pi^{\dagger}}(\mathbf{M}; \mathcal{M})$ can be computed numerically as:

$$ \inf \left\{ \sum_{x \in \mathcal{X}} \mu(x) \text{KL}(\mathbf{m}(x) || \mathbf{m}^{\dagger}(x)) : \mathbf{m}|_{\mathcal{X}_{\star}(\mathbf{M})} = \mathbf{m}^{\dagger}|_{\mathcal{X}_{\star}(\mathbf{M})} \text{ and } \mathbf{g}_{\pi^{\dagger}}(\mathbf{m}^{\dagger}, \mathbf{p}) > \mathbf{g}_{\star}(\mathbf{M}) \right\}. $$

The above is a convex program with a strongly convex objective function and linear constraints, because $\mathbf{m}^{\dagger} \mapsto \mathbf{g}_{\pi}(\mathbf{m}^{\dagger}, \mathbf{p})$ is a linear function. So, although the regret lower bound $K_{\star}(\mathbf{M}; \mathcal{M})$ is the solution of an optimization program with a continuum of convex constraints (LB) in general, its policy-wise formulation becomes the solution of an optimization program with “only” exponentially many convex constraints (one per policy). As constraints are indexed by policies, good heuristics on politics are crucial to get good estimates of $K_{\star}(\mathbf{M}; \mathcal{M})$. As a matter of fact, using heuristics to select seemingly critical policies and information constraints is a key component of the algorithm of Saber et al. (2024), even though Saber et al. (2024) do not try to approach the regret lower bound perfectly.

# 6 Conclusion, Future work and Conjectures

In this paper, we provide the regret lower bound in the model dependent setting for communicating Markov decision processes. The bound is found as the solution of an optimization problem that combines the mandatory exploration, co-exploration and second order navigational structure that every consistent learner must conform to. In many classical
classes of Markov decision processes, such as bandits, switching bandits, ergodic classes or
deterministic transition classes, our bound coincide with existing ones.

**Tightness.** One obvious and immediate concern is the tightness of our bound, that we indeed conjecture to be tight. More precisely, we conjecture that there exists a consistent learning agent with theoretical regret guarantees matching the lower bound; a preprint for an asymptotically optimal learning algorithm is already available, see (Boone, 2025). We further conjecture it is possible to design asymptotically optimal algorithms that run in reasonable time (e.g. polynomial per-step complexity). Once the bound will be proven tight, will raise the classical question of the compatibility of the instance dependent setting with the instance independent setting. In multi-armed bandits, Garivier et al. (2022) design KL-UCB-Switch, reaching asymptotically optimal regret $K(M) \log(T)$ and minimax optimal regret $\sqrt{|A|T}$ simultaneously; this is the best-of-both-worlds of Bubeck and Slivkins (2012), that we conjecture to fail at communicating Markov decision processes. In addition to the best-of-both-worlds, there is the question of how asymptotic the bound is. For bandits again, Garivier et al. (2018) pointed out that simple algorithms such as Thompson Sampling (Thompson, 1933) manage to beat the lower bound $K(M) \log(T)$ even for large time horizons. Nowadays, it is known (Honda and Takemura, 2015; Garivier et al., 2018) that the second order term is a *negative* $\log \log(T)$ when the support of rewards is bounded. We conjecture that even in simple cases, the second order term is a *positive* $\log \log(T)$ for Markov decision processes and that the culprit should be co-exploration (Proposition 7).

All this is left for future work.

**Extensions.** Another immediate research direction is the generalization of our result to broader settings. Sticking to finite Markov decision processes, there is the question of dropping the communicating assumption to a weakly communicating assumption or even considering general multi-chain models. Beyond finite Markov decision processes, there is the question of countable state spaces such as in Queuing Theory, compact action spaces, compact state-action spaces or even parameterized environments such as linear MDPs or MDPs with function approximation.

**Acknowledgments**

This work has been supported by the French Ministry of Higher Education and Research, the Hauts-de-France region, Inria, the MEL, the PEPR FOUNDRY (ANR-23-PEIA-0003) and the ANR JCJC REPUBLIC project (ANR-22-CE23-0003-01) as well as the AI Interdisciplinary Institute ANITI (ANR-23-IACL-0002). O. Maillard acknowledges the Inria-Kyoto University Associate Team “RELIANT”, and the Scool research group for its outstanding working environment.
## References

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

Rajeev Agrawal and Demosthenis Teneketzis. Certainty equivalence control with forcing: revisited. *Systems & control letters*, 13(5):405-412, 1989.

Rajeev Agrawal, MV Hedge, and Demosthenis Teneketzis. Asymptotically efficient adaptive allocation rules for the multiarmed bandit problem with switching cost. *IEEE Transactions on Automatic Control*, 33(10):899-906, 1988b. Publisher: IEEE.

Shipra Agrawal and Randy Jia. Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds. *Mathematics of Operations Research*, 48(1):363-392, 2023. Publisher: INFORMS.

Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. *Advances in Neural Information Processing Systems*, 34:25852-25864, 2021.

Aymen Al-Marjani, Andrea Tirinzoni, and Emilie Kaufmann. Active coverage for pac reinforcement learning. In *The Thirty Sixth Annual Conference on Learning Theory*, pages 5044-5109. PMLR, 2023.

Peter Auer. Using Confidence Bounds for Exploitation-Exploration Trade-offs. *J. Mach. Learn. Res.*, 3:397-422, 2002.

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

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

Peter L Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. *arXiv preprint arXiv:1205.2661*, 2012.

Victor Boone. Asymptotically optimal regret in communicating markov decision processes, 2025. URL https://arxiv.org/abs/2505.18064.

Victor Boone and Zihan Zhang. Achieving Tractable Minimax Optimal Regret in Average Reward MDPs, 2024. URL https://arxiv.org/abs/2406.01234. _eprint: 2406.01234.

Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening Exploration in Upper Confidence Reinforcement Learning. In Hal Daumé III and Aarti Singh, editors, *Proceedings of the 37th International Conference on Machine Learning*, volume 119 of *Proceedings of Machine Learning Research*, pages 1056-1066. PMLR, July 2020.
Monica Brezzi and Tze Leung Lai. Optimal learning and experimentation in bandit problems. *Journal of Economic Dynamics and Control*, 27(1):87-108, 2002. Publisher: Elsevier.

Sebastien Bubeck and Aleksandrs Slivkins. The best of both worlds: stochastic and adversarial bandits, February 2012. arXiv:1202.4473 [cs].

Apostolos Burnetas and Michael Katehakis. Optimal Adaptive Policies for Markov Decision Processes. *Mathematics of Operations Research - MOR*, 22:222-255, February 1997.

Apostolos N Burnetas and Michael N Katehakis. Optimal adaptive policies for sequential allocation problems. *Advances in Applied Mathematics*, 17(2):122-142, 1996. Publisher: Elsevier.

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

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

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

Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning. *Proceedings of the 35 th International Conference on Machine Learning*, 2018.

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

Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore First, Exploit Next: The True Shape of Regret in Bandit Problems. *Mathematics of Operations Research*, 44(2):377-399, 2018.

Aurélien Garivier, Hédi Hadiji, Pierre Ménard, and Gilles Stoltz. KL-UCB-Switch: Optimal Regret Bounds for Stochastic Bandits from Both a Distribution-Dependent and a Distribution-Free Viewpoints. *Journal of Machine Learning Research*, 23(179):1-66, 2022.

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

Junya Honda and Akimichi Takemura. An asymptotically optimal bandit algorithm for bounded support models. In *COLT*, pages 67-79. Citeseer, 2010.

Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. *J. Mach. Learn. Res.*, 16:3721-3756, 2015.
Tackseung Jun. A survey on the bandit problem with switching costs. *de Economist*, 152: 513–541, 2004. Publisher: Springer.

Emilie Kaufmann. *Analyse de stratégies bayésiennes et fréquentistes pour l'allocation séquentielle de ressources*. PhD thesis, ENST Paris, France, 2014.

Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models. *Journal of Machine Learning Research*, 17 (1):1–42, 2016.

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

Kailasam Lakshmanan, Ronald Ortner, and Daniil Ryabko. Improved regret bounds for undiscounted continuous reinforcement learning. In *International conference on machine learning*, pages 524–532. PMLR, 2015.

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

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

Odalric-Ambrym Maillard. *Mathematics of statistical sequential decision making*. PhD thesis, Université de Lille, Sciences et Technologies, 2019.

Aymen Al Marjani and Alexandre Proutiere. Adaptive Sampling for Best Policy Identification in Markov Decision Processes. In *Proceedings of the 38th International Conference on Machine Learning*, pages 7459–7468. PMLR, July 2021. ISSN: 2640-3498.

Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in Structured Reinforcement Learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 31. Curran Associates, Inc., 2018.

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

Ronald Ortner. Adaptive aggregation for reinforcement learning in average reward markov decision processes. *Annals of Operations Research*, 208:321–336, 2013.

Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) Efficient Reinforcement Learning via Posterior Sampling. *arXiv:1306.0940 [cs, stat]*, December 2013. arXiv: 1306.0940.

Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning Unknown Markov Decision Processes: A Thompson Sampling Approach. *arXiv:1709.04570 [cs]*, September 2017. arXiv: 1709.04570.

Fabien Pesquerel. *Information per unit of interaction in stochastic sequential decision making*. PhD thesis, Université de Lille, 2023.
Fabien Pesquerel and Odalric-Ambrym Maillard. IMED-RL: Regret optimal learning of ergodic Markov decision processes. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems*, volume 35, pages 26363–26374. Curran Associates, Inc., 2022.

Daniel Pirutinsky. *On Asymptotically Optimal Reinforcement Learning*. PhD Thesis, Rutgers The State University of New Jersey, Graduate School-Newark, 2020.

Martin L Puterman. *Markov decision processes: discrete stochastic dynamic programming*. John Wiley & Sons, 2014.

Jian Qian, Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Exploration bonus for regret minimization in discrete and continuous average reward mdps. *Advances in Neural Information Processing Systems*, volume 32, 2019.

Alessio Russo and Alexandre Proutiere. Model-free active exploration in reinforcement learning. *Advances in Neural Information Processing Systems*, 36, 2024.

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

Antoine Salomon, Jean-Yves Audibert, and Issam El Alaoui. Lower bounds and selectivity of weak-consistent policies in stochastic multi-armed bandit problem. *Journal of Machine Learning Research*, 14(1), 2013.

Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs. *Journal of Machine Learning Research*, pages 1–36, April 2018. Publisher: Microtome Publishing.

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

Andrea Tirinzoni, Aymen Al Marjani, and Emilie Kaufmann. Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems*, volume 35, pages 8785–8798. Curran Associates, Inc., 2022.

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

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

A Wald. Sequential tests of statistical hypotheses. *The Annals of Mathematical Statistics*, 16(2):117–186, 1945.
Christopher JCH Watkins and Peter Dayan. Q-learning. *Machine learning*, 8:279–292, 1992.

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

Zihan Zhang and Qiaomin Xie. Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes. In *The Thirty Sixth Annual Conference on Learning Theory*, pages 5476–5477. PMLR, 2023.
# Appendix A. Supplementary Proofs for the Regret Lower Bound

## A.1 On self-normalized expected deviations of the empirical mean

In this paragraph, we provide a technical lemma for the proof of Proposition 9.

**Lemma A.1.** Consider $X_n \in [0, 1]$ a family of r.v. with $\mathbb{E}[X_n|\mathcal{F}_n] = \mu$. Let $\hat{\mu}_n := \frac{1}{n} \sum_{k=1}^n X_k$ their empirical mean. Let $N$ a random variable of support $\{0, 1, \dots, T\}$ where $T \ge 1$ is a fixed scalar. Then, for all $\varepsilon > 0$,

$$ \mathbb{E}[N(\hat{\mu}_N - \mu)] \le \varepsilon(\mathbb{E}[N] + \log(1 + T)) + \sqrt{\mathbb{E}[N \log(2 \lor \frac{3\sqrt{1+N \log(1+T)}}{2\varepsilon^3 \mathbb{E}[N]})]} + 1. $$

**Proof** Let $\delta > 0$ that shall be tuned later. By Hoeffding's Lemma, $X_n$ is conditionally $\sigma$-subgaussian for $\sigma = \frac{1}{2}$. By a time-uniform Azuma-Hoeffding's inequality (Bourel et al., 2020, Lemma 5), for all $m \ge 1$,

$$ \mathbb{P}\left(\exists m \le n \le T, |\hat{\mu}_n - \mu| \ge 2\sigma\sqrt{\frac{\log(T\sqrt{1+T})}{m}}\right) \le \frac{1}{T}. \quad (A.1) $$

Setting $m = m_\varepsilon := (\frac{2\sigma}{\varepsilon})^2 \log(T\sqrt{1+T})$, we have $\mathbb{P}(\exists m_\varepsilon \le n \le T, |\hat{\mu}_n - \mu| \ge \varepsilon) \le \frac{1}{T}$. The target expectation is split into two. Denoting $f(N) := N(\hat{\mu}_N - \mu)$, we write:

$$ \mathbb{E}[N(\hat{\mu}_N - \mu)] = \mathbb{E}[f(N)1(N \ge m_\varepsilon)] + \mathbb{E}[f(N)1(N < m_\varepsilon)]. \quad (A.2) $$

We start by controlling $\mathbb{E}[f(N)1(N \ge m_\varepsilon)]$. By construction of $m_\varepsilon$, we have:

$$ \begin{aligned} & \mathbb{E}[f(N)1(N \ge m_\varepsilon)] \\ & \le \mathbb{E}[f(N)1(N \ge m_\varepsilon)1(|\hat{\mu}_N - \mu| < \varepsilon)] + \mathbb{E}[f(N)1(N \ge m_\varepsilon)1(|\hat{\mu}_N - \mu| \ge \varepsilon)] \\ & \le \varepsilon\mathbb{E}[N] + T\mathbb{P}(\exists m \le n \le T, |\hat{\mu}_n - \mu| \ge \varepsilon) \\ & \stackrel{\circ 1}{\le} \varepsilon\mathbb{E}[N] + 1. \end{aligned} $$

where (°1) follows by (A.1). We continue with the other term $\mathbb{E}[f(N)1(N < m_\varepsilon)]$. Denote $\mathcal{E}_\delta := (\forall n \ge 1, n(\hat{\mu}_n - \mu)^2 \le 4\sigma^2 \log(\sqrt{1+n}/\delta))$. By a time-uniform Azuma-Hoeffding's inequality again (Bourel et al., 2020, Lemma 5), this good event has probability at least $1 - \delta$. We obtain:

$$ \begin{aligned} \mathbb{E}[f(N)1(N < m_\varepsilon)] &= \mathbb{E}[f(N)1(N < m_\varepsilon)1(\mathcal{E}_\delta)] + \mathbb{E}[f(N)1(N < m_\varepsilon)1(\mathcal{E}_\delta^c)] \\ &\le 2\sigma\mathbb{E}\left[\sqrt{N \log\left(\frac{\sqrt{1+N}}{\delta}\right)}\right] + \delta m_\varepsilon \\ &\stackrel{\circ 1}{\le} 2\sigma\sqrt{\mathbb{E}\left[N \log\left(\frac{\sqrt{1+N}}{\delta}\right)\right]} + \delta m_\varepsilon \\ &\equiv 2\sigma\sqrt{\mathbb{E}\left[N \log\left(\frac{\sqrt{1+N}}{\delta}\right)\right]} + \delta(\frac{2\sigma}{\varepsilon})^2 \log(T\sqrt{1+T}) \end{aligned} $$

where (°1) follows from Jensen's inequality. Set $\delta := \frac{\varepsilon^3 \mathbb{E}[N]}{6\sigma^2 \log(1+T)}$ and conclude. ■

Applied to sequential control, where $N_T$ is the number of triggers up to time $T$, we see that when $\mathbb{E}[N_T] + \mathbb{E}[\log(N_T)] = \Omega(\log(T))$, then $\mathbb{E}[N_T(\hat{\mu}_{N_T} - \mu)] = o(\mathbb{E}[N])$.
## A.2 Why Navigation Constraints Are Mandatory

To conclude this section, we discuss a simple example that illustrates the importance of navigation constraints.

<figure><img src="image_9.png" /><figcaption>Figure 4: An example of a two-state deterministic Markov decision process with Bernoulli rewards where the navigation constraints are necessary to obtain the right regret lower bound.</figcaption></figure>

In Figure 4, we present a two-state Markov decision process M with deterministic transitions and Bernoulli rewards. $\mathcal{X}_*(M)$ consists in the loop from $s_1$ to itself, scoring $\frac{2}{3}$ in average. The other circle, between $s_1$ and $s_2$, only scores $\frac{1}{2}$ in average. With navigation constraints, we see that every $\mu \in \text{Inv}(M)$ satisfies $\mu(s_1 \to s_2) = \mu(s_2 \to s_1)$; We can numerically evaluate $K(M)$ and obtain $\mu^*(s_1 \to s_2) \approx 7.704$ and $K(M) \approx 2.6$. Meanwhile, if one ignores navigation constraints (refer to the last paragraph of Section 4.2), then the transition $s_2 \to s_1$ can be explored arbitrarily more than $s_1 \to s_2$, while it is free to pick because it scores $\frac{2}{3} = g_*$. Therefore, one puts infinitely much mass on $s_2 \to s_1$ and has less information to gather on $s_1 \to s_2$, leading to the navigation-less lower bound of $\approx 1.4$, which is significatively far from $K(M)$.

## A.3 Complements of the Policy-wise Decomposition of the Lower Bound

In this appendix, we justify Equations (26) and (27) behind the proof of Theorem 19 in the main text. Equation (26) is proved with Lemma A.2, a result from Boone (2025) that we report in these pages for self-containedness. Equation (27) is proved with Lemma A.3.

**Lemma A.2** (Boone (2025), Proposition A.10). Let $M \in \mathcal{M}$ be communicating and denote $\Pi_u$ its set of unichain policies. The set of invariant measures satisfies

$$ \text{Inv}(M) = \mathbb{R}_+ \cdot \text{conv}(\{\mu_\pi : \pi \in \Pi_u\}) $$

**Proof** The proof is directly adapted from (Boone, 2025).

Because $\mu_\pi \in \text{Inv}(M)$ and that $\text{Inv}(M)$ is a convex positive cone, we have $\mathbb{R}_+ \cdot \text{conv}(\{\text{Inv}(\pi; M) : \pi \in \Pi_u\}) \subseteq \text{Inv}(M)$.

We focus on the reverse inclusion, which is the hard part of the proof.

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{X}^{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{X}_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{X}_0$. By construction of the path, we have $\mathcal{X}_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'$

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

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

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

and $\mathcal{F}$ is a linear space, so that $\mu' := \mu - \lambda_0\mu_0 \in \mathcal{F}$. As $\mu' \in \mathbb{R}_+^\chi$ as explained above, we have $\mu' \in \text{Inv}(\mathbf{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 $x_0 \in \mathcal{X}_0$ such that $x_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 \leq m}$ with $\lambda_i > 0$, $\mu_i \in \text{Inv}(\pi_u; \mathbf{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 \leq |\mathcal{X}|$. This concludes the proof. ■

**Lemma A.3.** Let $\mathbf{M} \in \mathcal{M}$ be communicating. Its confusing set can be decomposed as

$$ \text{Cnf}(\mathbf{M}) = \bigcup_{\pi^{\dagger} \notin \Pi^{*}(\mathbf{M})} \text{Cnf}_{\pi^{\dagger}}(\mathbf{M}), \quad \text{Cnf}_{\pi^{\dagger}}(\mathbf{M}) := \{\mathbf{M}^{\dagger} \in \text{Cnf}(\mathbf{M}) : \mathbf{g}_{\pi^{\dagger}}(\mathbf{M}^{\dagger}) > \mathbf{g}_{\star}(\mathbf{M})\}. $$

**Proof** Note that for every $\mathbf{M}' \gg \mathbf{M}$ that coincides with $\mathbf{M}$ on $\mathcal{X}_*(\mathbf{M})$, we have $\mathbf{g}_{\pi^*}(\mathbf{M}') = \mathbf{g}_{\pi^*}(\mathbf{M})$ for every $\pi^* \in \Pi^*(\mathbf{M})$. Indeed, given $\pi^* \in \Pi^*(\mathbf{M})$, its recurrent classes in $\mathbf{M}$ are a subset of $\mathcal{X}_*(\mathbf{M})$. By definition of $\mathbf{M}'$, we deduce that the recurrent classes of $\pi^*$ are the same in $\mathbf{M}$ and $\mathbf{M}'$. Because the two models coincide on $\mathcal{X}_*(\mathbf{M})$, we deduce that $\mathbf{g}_{\pi^*}(\mathbf{M}') = \mathbf{g}_{\pi^*}(\mathbf{M})$. Following from this observation ($*$), we find

$$ \begin{aligned} \text{Cnf}(\mathbf{M}) &:= \{\mathbf{M}^{\dagger} \gg \mathbf{M} : \mathbf{M}^{\dagger} = \mathbf{M} \text{ on } \mathcal{X}_{*}(\mathbf{M}) \text{ and } \Pi^{*}(\mathbf{M}^{\dagger}) \cap \Pi^{*}(\mathbf{M}) = \emptyset\} \\ &= \bigcup_{\pi^{\dagger} \notin \Pi^{*}(\mathbf{M})} \left\{ \mathbf{M}^{\dagger} \gg \mathbf{M} : \begin{array}{l} \mathbf{M}^{\dagger} = \mathbf{M} \text{ on } \mathcal{X}_{*}(\mathbf{M}) \\ \text{and } \Pi^{*}(\mathbf{M}^{\dagger}) \cap \Pi^{*}(\mathbf{M}) = \emptyset \text{ and } \pi^{\dagger} \in \Pi^{*}(\mathbf{M}^{\dagger}) \end{array} \right\} \\ &= \bigcup_{\pi^{\dagger} \notin \Pi^{*}(\mathbf{M})} \left\{ \mathbf{M}^{\dagger} \gg \mathbf{M} : \mathbf{M}^{\dagger} = \mathbf{M} \text{ on } \mathcal{X}_{*}(\mathbf{M}) \text{ and } \mathbf{g}_{\pi^{\dagger}}(\mathbf{M}^{\dagger}) > \sup_{\pi^{*} \in \Pi^{*}(\mathbf{M})} \mathbf{g}_{\pi^{*}}(\mathbf{M}^{\dagger}) \right\} \end{aligned} $$
$$ \stackrel{\circ 1}{=} \bigcup_{\pi^{\dagger} \notin \Pi^{*}(\mathbf{M})} \left\{ \mathbf{M}^{\dagger} \gg \mathbf{M} : \mathbf{M}^{\dagger} = \mathbf{M} \text{ on } \mathcal{X}_{\star}(\mathbf{M}) \text{ and } \mathbf{g}_{\pi^{\dagger}}(\mathbf{M}^{\dagger}) > \mathbf{g}_{\star}(\mathbf{M}) \right\} $$

$$ \stackrel{\circ 1}{=} \bigcup_{\pi^{\dagger} \notin \Pi^{*}(\mathbf{M})} \mathrm{Cnf}_{\pi^{\dagger}}(\mathbf{M}) $$

where (°1) follows by (*). This concludes the proof.

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

## A.4 Comments on less asymptotic regret lower bounds

The techniques used to establish Theorem 3 are all very asymptotic. This is no surprise, because the whole theory is built on a very asymptotic notion of consistency (Definition 2), that only asks that learners eventually converge to optimal play. The asymptotic speed of that convergence o(T^η) has nothing to do the possibly arbitrarily long burn-in time before the bound T^η starts to barely holds. This allows for algorithms that are asymptotically optimal in theory, but impractical because of their immense burn-in times. This is reproached by Burnetas and Katehakis (1997) to the solution of Agrawal et al. (1988a), until their very solution was itself criticized for its impracticability by Pesquerel and Maillard (2022) two decades later. The lower bound of Lai and Robbins (1985) has also been pointed out for its over-asymptotic nature by Garivier et al. (2018), with Thompson Sampling Thompson (1933) beating the asymptotic lower bound K(M) log(T) even for large time horizons.

This kind of story is common and there have been many attempts at patching the asymptotic inclination of theory: the trend for finite time bounds, second order terms of asymptotic lower bounds, or straight up modifications of the learning framework.

Properly addressing the asymptotic nature of our own Theorem 3 goes way beyond the scope of this paper, but we thought important to leave a few elements behind. Following the direction of finite time bounds, we first introduce a notion of consistency that is less asymptotic than Definition 2.

**Definition 11** (Timely-consistent learner). Let $\eta: \mathbb{N} \to [0, 1]$ a function satisfying $\eta(t) = o(1)$. A learning agent $\mathcal{A}$ is said $\eta$-timely-consistent on $\mathcal{M}$, if for all $\mathbf{M} \in \mathcal{M}$,

$$ \exists T_{\mathbf{M}} \in \mathbb{N}, \forall T \ge T_{\mathbf{M}}, \sup_{x: \Delta_{\star}(x:\mathbf{M})>0} \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}} \left[ \frac{N_{T+1}(x)}{T} \right] \le \eta(T). $$

Observe that this definition is expressed in terms of visits rather than of regret. This is done so in order to streamline the argument behind the regret lower bound. Consider an $\eta$-timely-consistent learner $\mathcal{A}$ and let us mimic the computations done for the simple example of discriminating random variable in Section 4.1. Let $\mathbf{M}^\dagger$ such that $\mathcal{X}_{\star}^\dagger(\mathbf{M}^\dagger) \cap \mathcal{X}_{\star}(\mathbf{M}) = \emptyset$ and let $U := \sum_{x \in \mathcal{X}_{\star}(\mathbf{M})} N_{T+1}(x)$. By assumption and provided that $T \ge \max\{T_{\mathbf{M}}, T_{\mathbf{M}^\dagger}\}$, we directly obtain

$$ \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}[N_{T+1}(x)] \ge (1 - |\mathcal{X}|\eta(T))T \quad \text{and} \quad \mathbb{E}_{s_0}^{\mathbf{M}^\dagger,\mathcal{A}}[N_{T+1}(x)] \le |\mathcal{X}|\eta(T)T. $$

Setting $\mathcal{E} := (U \le \frac{1}{2}T)$, we deduce that $\mathbb{P}_{s_0}^{\mathbf{M},\mathcal{A}}(\mathcal{E}) \le 2|\mathcal{X}|\eta(T)$ and $\mathbb{P}_{s_0}^{\mathbf{M}^\dagger,\mathcal{A}}(\mathcal{E}) \ge 1 - 2|\mathcal{X}|\eta(T)$. For $\eta(T) \le \frac{1}{2|\mathcal{X}|}$ and invoking Corollary C.4, we conclude that:

$$ \mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}} \left[ \sum_{x \in \mathcal{X}} N_{T+1}(x) \mathrm{KL}_x(\mathbf{M} || \mathbf{M}^{\dagger}) \right] \ge \mathrm{kl}(2|\mathcal{X}|\eta(T), 1 - 2|\mathcal{X}|\eta(T)). $$
Following the recipe described in Section 4.2 to convert the above into a regret lower bound, we normalize by $T$ and invoke Proposition 1 to obtain the finite time bound below:

**Theorem A.4.** Let $\mathbb{A}$ an $\eta$-timely-consistent learner. For all $T \ge T_M$, then $\text{Reg}(T; \mathbf{M}, \mathbb{A}, s_0)+\text{sp}(\mathbf{b}_*(\mathbf{M}))$ is lower-bounded by

$$ T \inf_{\mu \in \mathbb{R}_+^\mathcal{X}} \left\{ \sum_{x \in \mathcal{X}} \mu(x) \Delta_*(x; \mathbf{M}) : \forall \mathbf{M}^\dagger \in \text{Cnf}_* \star (\mathbf{M}), \sum_{x \in \mathcal{X}} \mu(x) \text{KL}_x(\mathbf{M} \| \mathbf{M}^\dagger) \ge 1(T_{\mathbf{M}^\dagger} < T) \frac{\text{kl}(2|\mathcal{X}|\eta(T), 1-2|\mathcal{X}|\eta(T))}{T} \right\} $$
where $\text{Cnf}_* \star (\mathbf{M}) := \{\mathbf{M}^\dagger \in \text{Alt}(\mathbf{M}) : \mathcal{X}_*(\mathbf{M}^\dagger) \cap \mathcal{X}_*(\mathbf{M}) = \emptyset\}$.

# Appendix B. Inevitable Sets and Details on Informational Constraints

This section provides technical details on the proofs of informational constraints, especially Propositions 4 and 7.

## B.1 Inevitable Sets and the Inevitability Lemma

A key idea, invoked at several places in the proofs of these statements, is the notion of inevitable set. Inevitable sets are sets of pairs that every policy of a reference set is forced to go through infinitely many times, i.e., linearly often and regardless of the initial state.

**Definition 12.** A set of pairs $\mathcal{X}_c \subseteq \mathcal{X}$ is said inevitable relatively to $\Pi^*(\mathbf{M})$ if, for all $\pi \in \Pi^*(\mathbf{M})$ and all initial state $s_0 \in \mathcal{S}$, we have $\mathbb{P}_{s_0}^{\mathbf{M},\pi}\{\forall n, \exists m \ge n : X_m \in \mathcal{X}_c\} = 1$.

Although inevitable sets could be described relatively to different sets than $\Pi^*(\mathbf{M})$, the generalization won't be required. We will speak of inevitable sets rather than inevitable sets relatively to $\Pi^*(\mathbf{M})$ in the sequel. By standard Markov chain theory Levin and Peres (2017), recurrent and positive recurrent are equivalent when the number of states is finite, hence the condition “$\forall s_0 \in \mathcal{S}, \mathbb{P}_{s_0}^{\mathbf{M},\pi}\{\forall n, \exists m \ge n : X_m \in \mathcal{X}_c\} = 1$” can be changed to “$\forall s_0 \in \mathcal{S}, \mathbb{E}_{s_0}^{\mathbf{M},\pi}[\inf\{t \ge 2 : X_t \in \mathcal{X}_c\}] < \infty$” or again to “$\forall s_0 \in \mathcal{S}, \mathbb{E}_{s_0}^{\mathbf{M},\pi}[\sum_{t=1}^T 1(X_t \in \mathcal{X}_c)] = \Omega(T)$”.

Inevitability requires that, for every $\pi \in \Pi^*(\mathbf{M})$, $\mathcal{X}_c$ is visited linearly often. This point-wise property is converted to a uniform one via the remarkable result below: In probability, the number of visits of an inevitable set $\mathcal{X}_c$ satisfies $\sum_{x \in \mathcal{X}_c} N_{T+1}(x) = \Omega(T - \text{Reg}(T; \mathbf{M}, \mathbb{A}))$.

**Lemma B.1 (Inevitability lemma).** Let $\mathbf{M} \in \mathcal{M}$ and assume that $\mathcal{X}_c \subseteq \mathcal{X}$ is inevitable. There exist constants $\varepsilon_c, D_c > 0$ such that, whatever the learning agent $\mathbb{A}$ and the initial state $s_0$, we have:

$$ \forall u \ge 0, \quad \mathbb{P}_{s_0}^{\mathbf{M},\mathbb{A}} \left( \sum_{x \in \mathcal{X}_c} N_{T+1}(x) + D_c \sum_{x \in \mathcal{X}_-(\mathbf{M})} N_{T+1}(x) \le \varepsilon_c T - u \right) \le \exp \left( - \frac{2u^2}{T D_c^2} \right). $$

$$ \text{Moreover, } \mathbb{E}_{s_0}^{\mathbf{M},\mathbb{A}}[\sum_{x \in \mathcal{X}_c} N_{T+1}(x)] + D_c \mathbb{E}_{s_0}^{\mathbf{M},\mathbb{A}}[\sum_{x \in \mathcal{X}_-(\mathbf{M})} N_{T+1}(x)] \ge \varepsilon_c T - D_c. $$

**Proof** The idea is to construct the optimal policy of that visits $\mathcal{X}_c$ as rarely as possible. Consider the reward function $f(x) := -1(x \in \mathcal{X}_c)$ and consider $\mathbf{M}_f|_{\mathcal{X}_*(\mathbf{M})}$, a copy of $\mathbf{M}$ restricted to $\mathcal{X}_*(\mathbf{M})$ and with reward function $f$. Let $\pi_f$ a bias optimal policy of $\mathbf{M}_f|_{\mathcal{X}_*(\mathbf{M})}$; It is also a policy of $\mathbf{M}$ since $\mathcal{S}(\mathcal{X}_*(\mathbf{M})) = \mathcal{S}$. Moreover, $\pi \in \Pi^*(\mathbf{M})$ because $\pi$ only picks
pairs such that $\Delta_{\star}(x; \mathbf{M}) = 0$, hence is guaranteed to have optimal gain via Proposition 1. Let $\mathbf{g}_f, \mathbf{b}_f$ and $\Delta_f$ its gain, bias and gap functions on $\mathbf{M}$ under the reward function $f$. By construction of $\pi_f$, we have $\Delta_f(x) \ge 0$ for all $x \in \mathcal{X}_{\star}(\mathbf{M})$. Let $\varepsilon_c := -\max_{s \in S} \mathbf{g}_f(s)$, and denote $D_c := \max\{\text{sp}(\mathbf{b}_f), \max_{x \in \mathcal{X}}|\Delta_f(x)|\} < \infty$. Since $\pi \in \Pi^*(\mathbf{M})$ and $\mathcal{X}_c$ is inevitable, we have $\varepsilon_c > 0$. Now,

$$
\begin{align*}
\sum_{x \in \mathcal{X}_c} N_{T+1}(x) &= -\sum_{t=1}^{T} f(X_t) \\
&\stackrel{\circ 1}{=} -\sum_{t=1}^{T} (\mathbf{g}_f(S_t) + (\mathbf{e}_{S_t} - \mathbf{p}(X_t))\mathbf{b}_f - \Delta_f(X_t)) \\
&\stackrel{\circ 2}{\ge} \varepsilon_c T + \sum_{t=1}^{T} (\mathbf{e}_{S_{t+1}} - \mathbf{p}(X_t))\mathbf{b}_f - D_c \left(1 + \sum_{x \in \mathcal{X}_-(\mathbf{M})} N_{T+1}(x)\right)
\end{align*}
$$

where (°1) invokes the Poisson equation $\mathbf{g}_f(s) + \mathbf{b}_f(s) = f(s, a) + \mathbf{p}(s, a)\mathbf{b}_f + \Delta_f(s, a)$, and (°2) that $\Delta_f(\mathbf{M}) \ge 0$ for $x \in \mathcal{X}_{\star}(\mathbf{M})$. By Azuma-Hoeffding's inequality, the MDS term satisfies:

$$
\forall u \ge 0, \quad \mathbb{P}_{s_0}^{\mathbf{M},\mathcal{A}} \left( \sum_{t=1}^{T} (\mathbf{e}_{S_{t+1}} - \mathbf{p}(X_t))\mathbf{b}_f \le -u \right) \le \exp\left(-\frac{2u^2}{T D_c^2}\right).
$$

This provides the result in probability. The result in expectation is immediately obtained by using that $\mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}[\sum_{t=1}^T (\mathbf{e}_{S_{t+1}} - \mathbf{p}(X_t))\mathbf{b}_f] = 0$. ■

**Discussion.** In Lemma B.1, what is important is that $\varepsilon_c \neq 0$. In a few scenarios, for instance when $\mathcal{X}_c = \mathcal{X}_\star(\mathbf{M})$, one can check that $\varepsilon_c = 1$. This is actually the idea behind Lemma 8, that can be seen as a simplified version of Lemma B.1 when $\mathcal{X}_c = \mathcal{X}_\star(\mathbf{M})$. Overall, Lemma B.1 is immensely useful in the proofs of Proposition 4 and Proposition 7.

## B.2 Proof of Lemma 6

We start by providing a proof of Lemma 6 which is essential to Proposition 4. We recall its statement below.

**Lemma 6.** Let $\mathbf{M} \in \mathcal{M}$, pick $\mathbf{M}^{\dagger} \in \text{Alt}(\mathbf{M})$ and let $\mathcal{X}_c := \{x \in \mathcal{X}_\star(\mathbf{M}^{\dagger}) : \Delta_\star(x; \mathbf{M}) > 0\}$. There exist constants $\varepsilon_c^{\dagger}, D_c^{\dagger} > 0$ such that, whatever the learning agent $\mathcal{A}$ and the initial state $s_0$, we have:

$$
\forall u \ge 0, \quad \mathbb{P}_{s_0}^{\mathbf{M}^{\dagger}, \mathcal{A}} \left( \sum_{x \in \mathcal{X}_c} N_{T+1}(x) + D_c^{\dagger} \sum_{x \in \mathcal{X}_-(\mathbf{M}^{\dagger})} N_{T+1}(x) \le \varepsilon_c^{\dagger} T - u \right) \le \exp \left( - \frac{2u^2}{T D_c^{\dagger 2}} \right).
$$

**Proof** We show that $\mathcal{X}_c$ is inevitable in $\mathbf{M}^{\dagger}$. The conclusion will follow by Lemma B.1. Let $\pi^{\dagger} \in \Pi^*(\mathbf{M}^{\dagger})$.

We say that a state $s_\star$ is *reachable* from $s$ in $\mathbf{M}' \in \{\mathbf{M}, \mathbf{M}^{\dagger}\}$ if $\mathbb{P}_s^{\mathbf{M}', \pi^{\dagger}}\{\exists n: S_n = s_\star\} > 0$.

Assume, by contradiction, that there is $s \in S$ with $\mathbb{P}_s^{\mathbf{M}^{\dagger}, \pi^{\dagger}}\{\forall n, \exists m \ge n: X_m \in \mathcal{X}_c\} < 1$;

There must exist $s^{\dagger} \in S$ reachable from $s$ in $\mathbf{M}^{\dagger}$ such that $\mathbb{P}_{s^{\dagger}}^{\mathbf{M}^{\dagger}, \pi^{\dagger}}\{\forall n, \exists m: X_m \in \mathcal{X}_c\} = 0$.
Let $S^\dagger$ the collection of all states that are reachable from $s^\dagger$ in $M^\dagger$. Remark that every state of $S^\dagger$ is reachable (under $\pi^\dagger$) is reachable from any other of $S^\dagger$ in $M^\dagger$. We see that for all $s \in S^\dagger$ and all $a \in A(s)$ with $\pi^\dagger(a|s) > 0$, we have $\Delta_*(s, a|M) = 0$.

From there, we construct $\pi \in \Pi^*(M^\dagger) \cap \Pi^*(M)$, as the policy given by:

$$ \pi(a|s) := \begin{cases} \pi^\dagger(a|s) & \text{if } s \in S^\dagger; \\ \frac{1}{|A(s)|} & \text{if } s \notin S^\dagger. \end{cases} $$

Because it is uniform outside of $S^\dagger$, $S^\dagger$ is reachable under $\pi$ from every state both in $M$ and $M^\dagger$. Now, observe that for all $s \in S^\dagger$ and $a \in A(s)$ with $\pi(a|s) > 0$, we have $\text{supp}(\mathbf{p}^\dagger(s, a)) \subseteq S^\dagger$. Since $\mathbf{p} \ll \mathbf{p}^\dagger$, we similarly have $\text{supp}(\mathbf{p}(s, a)) \subseteq S^\dagger$. It follows that the recurrent states of $\pi$ satisfy $S_\pi(M^\dagger) = S^\dagger$ and $S_\pi(M) \subseteq S^\dagger$. In other words, both on $M$ and $M^\dagger$, the iterates of $\pi$ are eventually confined within $S^\dagger$, whatever the initial state. Since $S_\pi(M^\dagger) = S^\dagger$ which is a component of recurrent states of $\pi^\dagger$, and that $\pi^\dagger$ satisfies $g_{\pi^\dagger}(M^\dagger) = g_*(M^\dagger)$, it follows that $g_\pi(M^\dagger) = g_*(M^\dagger)$. Since $S_\pi(M) \subseteq S^\dagger$ and that every pair $x$ that $\pi$ plays on $S^\dagger$ satisfies $\Delta_*(\pi; M) = 0$, it follows by Proposition 1 that $g_\pi(M) = g_*(M)$. So $\pi \in \Pi^*(M^\dagger) \cap \Pi^*(M)$; A contradiction with $M^\dagger \in \text{Alt}(M)$. $\blacksquare$

## B.3 Proof of Proposition 7

To conclude this section, we provide a proof of Proposition 7.

**Proposition 7.** Let $M \in \mathcal{M}$ and fix $x_* \in \mathcal{X}_*(M)$. Assume that, for all $\varepsilon > 0$, there exists $M' \in \mathcal{M}$ such that (1) $M'$ and $M$ only differ with $\mathbf{r}(x_*) \neq \mathbf{r}'(x_*)$, (2) $\mathbf{m}(x_*) < \mathbf{m}'(x_*)$ and (3) $\text{KL}(\mathbf{r}(x_*)|\mathbf{r}'(x_*)) < \varepsilon$. Then, for every consistent learner $\mathcal{A}$ and regardless of the initial state $s_0 \in S$,

$$ \mathbb{E}_{s_0}^{M, \mathcal{A}}[N_{T+1}(x_*)] = \omega(\log(T)). $$

**Proof** Let $\varepsilon > 0$ small enough (to be chosen later) and pick $M' \in \mathcal{M}$ as the above. The idea of the proof is to show that $\mathcal{X}_c := \{x_*\}$ is an inevitable set in $M'$, i.e., that every optimal policy of $M'$ plays $x_*$ infinitely often regardless of the initial state. Let $\delta := \mathbf{m}'(x_*) - \mathbf{m}(x_*) > 0$. Given a policy $\pi \in \Pi$, we denote $\mu_\pi(x|s_0) := \lim_{T \to \infty} \frac{1}{T} \mathbb{E}_{s_0}^{M, \pi}[\sum_{t=1}^T 1(X_t = x)]$ the asymptotic average number of plays of $x$ under $\pi$ in $M$ starting from $s_0$. Since $M$ and $M'$ have the same transition kernel, we obtain:

$$ g_{\pi}(s_0; M') = g_{\pi}(s_0; M) + \mu_{\pi}(x_*|s_0)\delta. $$

Provided that $\delta < \Delta_g(M) := \min\{\|g_*(M) - g_\pi(M)\|_\infty : \pi \notin \Pi^*(M)\}$, it follows that optimal policies of $M'$ are necessarily optimal in $M$. Then, optimal policies of $M'$ are found as the optimal policies of $M$ that maximize $\mu_\pi(x_*|s_0)$, i.e., such that $\mu_\pi(x_*|s_0) = \max_{\pi' \in \Pi^*(M)} \mu_{\pi'}(x_*|s_0)$. Because $x_* \in \mathcal{X}_*(M)$, it follows that this maximum is positive and that $x_*$ is visited linearly often under every optimal policy of $M'$; Hence, that $\mathcal{X}_c$ is inevitable. This all is provided that $\delta < \Delta_g(M)$. This assumption is met as soon as $\text{KL}(\mathbf{r}(x_*)|\mathbf{r}'(x_*)) \to 0$ implies $\mathbf{m}'(x_*) \to \mathbf{m}(x_*)$, which is true in particular when rewards have support within $[0, 1]$.
So, {$x_\star$} is inevitable in $\mathbf{M}'$. By Lemma B.1, there exists $\varepsilon'_c$, $D'_c > 0$ such that:

$$ \forall u \ge 0, \quad \mathbb{P}_{s_0}^{\mathbf{M}', \mathbb{A}} \left( N_{T+1}(x_\star) + D'_c \sum_{x \in \mathcal{X}_-(\mathbf{M})} N_{T+1}(x) \le \varepsilon'_c T - u \right) \le \exp \left( - \frac{2u^2}{T D'_c^2} \right). $$

The remaining of the proof is essentially similar to the one of Proposition 4. Let $\alpha := \text{sp}(\mathbf{b}_*(\mathbf{M}'))$ and introduce the quantities

$$ \varphi(T) := \sqrt{\frac{\text{Reg}(T; \mathbf{M}', \mathbb{A}, s_0) + \alpha}{T}}, $$

$$ \psi(T) := \frac{D'_c}{\text{dmin}(\mathbf{\Delta}_*(\mathbf{M}'))} \sqrt{T(\text{Reg}(T; \mathbf{M}', \mathbb{A}, s_0) + \alpha)}. $$

Combining the previous inequality with Markov's inequality, we find:

$$ \forall u \ge 0, \quad \mathbb{P}_{s_0}^{\mathbf{M}', \mathbb{A}} (N_{T+1}(x_\star) \le \varepsilon'_c T - \psi(T) - u) \le \varphi(T) + \exp \left( - \frac{2u^2}{T D_c'^2} \right). $$

To conclude, we aim at invoking Corollary C.3 with $U := \frac{1}{1+N_{T+1}(x_\star)}$. We start by upper-bounding $\mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[U]$. We have:

$$ \begin{aligned} \mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[U] &= \mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}} \left[ \frac{1}{1 + N_{T+1}(x_\star)} \right] \\ &\le \inf_{v \ge 0} \left\{ \frac{1}{1+v} + \mathbb{P}_{s_0}^{\mathbf{M}', \mathbb{A}} (N_{T+1}(x_\star) \le v) \right\} \\ &\le \inf_{v \ge 0} \left\{ \frac{1}{1+v} + \varphi(T) + \exp \left( - \frac{2(\varepsilon'_c T - \psi(T) - v)^2}{T D_c'^2} \right) \right\} \\ &\stackrel{\circ 1}{\le} \frac{1}{1 + \frac{1}{2}\varepsilon'_c T} + \varphi(T) + \exp \left( - \frac{2\left(\frac{1}{2}\varepsilon'_c T - \psi(T)\right)^2}{T D_c'^2} \right) \\ &\le \frac{1}{1 + \frac{1}{2}\varepsilon'_c T} + \varphi(T) + \exp \left( - \frac{\varepsilon_c'^2 T}{2D_c'^2} + \frac{2\varepsilon_c' \psi(T)}{D_c'^2} \right) \end{aligned} $$

where ($\circ 1$) follows by setting $v := \frac{1}{2}\varepsilon'_c T$. By strong consistency, $\psi(T) = o(T)$ and $\log \varphi(T) = -\frac{1}{2}\log(T) + o(\log(T))$. We conclude that $\log(\mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[U]) \le -\frac{1}{2}\log(T) + o(\log(T))$.

So, applying Corollary C.3, we obtain:

$$ \begin{aligned} \varepsilon \mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[N_{T+1}(x_\star)] &\ge \mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[\log(U)] + \log \left( \frac{1}{\mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[U]} \right) \\ &= -\mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[\log(1 + N_{T+1}(x_\star))] - \log \left( \mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}} \left[ \frac{1}{1 + N_{T+1}(x_\star)} \right] \right) \\ &\stackrel{\circ 1}{\ge} -\log \left( \mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[1 + N_{T+1}(x_\star)] \right) + \frac{1}{2} \log(T) + o(\log(T)) \end{aligned} $$

where ($\circ 1$) follows by Jensen's inequality, Since $\log(\mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[1 + N_{T+1}(x_\star)])$ is negligible in front of $\mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[N_{T+1}(x_\star)]$. We conclude that $\mathbb{E}_{s_0}^{\mathbf{M}', \mathbb{A}}[N_{T+1}(x_\star)] \ge \frac{1}{2\varepsilon} \log(T) + o(\log(T))$.

As this holds for $\varepsilon > 0$ arbitrarily small, we conclude accordingly.

<figure><img src="image_11.png" /></figure>
# Appendix C. Background from Information Theory

In this appendix and for the sake of self-containedness, we provide a proof of (7) and (8) that are both key to derive the regret lower bound of Theorem 3. The curious reader may also read Maillard (2019); Kaufmann (2014); Kaufmann et al. (2016).

## C.1 Change of Measures and Log-likelihood Ratios

We begin with an instance of the celebrated Radon-Nikodym' theorem, specialized for the stochastic process underlying a Markov decision process.

**Theorem C.1 (Change of measure).** Let $M \ll M'$ two Markov decision processes and fix an arbitrary learning agent $\mathbb{A}$ and $s \in S$. If $U \ge 0$ is a $\sigma(H_T)$-measurable random variable, then:

$$ \mathbb{E}_s^{M',\mathbb{A}}[U] \ge \mathbb{E}_s^{M',\mathbb{A}}[U \exp\{-L(H_t)\}]. $$

**Proof** Let $\nu_T, \nu'_T$ the distributions of $H_T$ induced by running $\mathbb{A}$ for $T$ steps from $s$ on $M, M'$ respectively. We have $\nu_T \ll \nu'_T$, so by Radon-Nikodym's theorem, for every $\sigma(H_T)$-measurable random variable $V$, we have:

$$ \mathbb{E}_s^{M',\mathbb{A}}[V] \equiv \int V(h_T) \, d\nu_T(h_T) = \int V(h_T) \frac{d\nu_T}{d\nu'_T}(h_T) \, d\nu'_T(h_T) \equiv \mathbb{E}_s^{M',\mathbb{A}}\left[V \cdot \frac{d\nu_T}{d\nu'_T}(H_T)\right] $$

where $\frac{d\nu_T}{d\nu'_T}$ is the Radon Nikodym of $\nu_T$ with respect to $\nu'_T$. By Markov's property, the Radon-Nikodym derivative can be written as:

$$ \begin{aligned} \frac{d\nu_T}{d\nu'_T}(H_T) &= \frac{\prod_{t=1}^{T-1} \mathbf{p}(S_{t+1}|S_t, A_t) \mathbf{r}(R_t|S_t, A_t) \mathbb{A}(A_t|S_1, A_1, R_1, \dots, S_t)}{\prod_{t=1}^{T-1} \mathbf{p}'(S_{t+1}|S_t, A_t) \mathbf{r}'(R_t|S_t, A_t) \mathbb{A}(A_t|S_1, A_1, R_1, \dots, S_t)} \\ &= \prod_{t=1}^{T-1} \frac{\mathbf{p}(S_{t+1}|S_t, A_t) \mathbf{r}(S_{t+1}|S_t, A_t)}{\mathbf{p}'(S_{t+1}|S_t, A_t) \mathbf{r}'(S_{t+1}|S_t, A_t)} \\ &= \exp\left\{\sum_{t=1}^{T-1} \left(\log\left(\frac{\mathbf{p}(S_{t+1}|S_t, A_t)}{\mathbf{p}'(S_{t+1}|S_t, A_t)}\right) + \log\left(\frac{\mathbf{r}(S_{t+1}|S_t, A_t)}{\mathbf{r}'(S_{t+1}|S_t, A_t)}\right)\right)\right\} \\ &=: \exp\{L(H_T)\} \end{aligned} $$

with the convention that $\log(0) = -\infty$. Set $V := U1(L(H_T) > -\infty) \exp\{-L(H_T)\}$, with the convention $0 \cdot \infty = 0$. We have:

$$ \begin{aligned} \mathbb{E}_s^{M',\mathbb{A}}[U] &\overset{\circ 1}{\ge} \mathbb{E}_s^{M',\mathbb{A}}[V \cdot \exp\{L(H_T)\}] \\ &\overset{\circ 2}{=} \mathbb{E}_s^{M',\mathbb{A}}[U \cdot 1(L(H_T) > -\infty)] \overset{\circ 3}{=} \mathbb{E}_s^{M',\mathbb{A}}[U] \end{aligned} $$

where $(\circ 1)$ uses that $U \ge V \cdot \exp\{L(H_T)\}$; $(\circ 2)$ invokes Radon-Nikodym's theorem; and $(\circ 3)$ uses that, under $M, \mathbb{A}$, we have $L(H_T) > -\infty$ almost surely. ■

**Lemma C.2.** The log-likelihood ratio satisfies

$$ \mathbb{E}_s^{M,\mathbb{A}}\left[\sum_{t=1}^{T-1}\left(\log\left(\frac{\mathbf{p}(S_{t+1}|S_t, A_t)}{\mathbf{p}'(S_{t+1}|S_t, A_t)}\cdot\frac{\mathbf{r}(S_{t+1}|S_t, A_t)}{\mathbf{r}'(S_{t+1}|S_t, A_t)}\right)\right)\right] = \mathbb{E}_s^{M,\mathbb{A}}\left[\sum_{x \in \mathcal{X}} N_T(x) \text{KL}_x(\mathbf{M} || \mathbf{M}')\right]. $$

**Proof** Direct application of the tower property. ■
## C.2 Simpler Forms of the Change of Measure's Inequality

While the inequality of Theorem C.1 can be used as is, we provide below a few alternative (weaker) form that are often more easy to work with.

**Corollary C.3.** Let $M \ll M'$ two Markov decision processes and fix an arbitrary learning agent $\mathcal{A}$ and $s \in S$. If $U \ge 0$ is a $\sigma(H_T)$-measurable random variable, then:

$$ \log \mathbb{E}_{s}^{M', \mathcal{A}}[U] + \mathbb{E}_{s}^{M, \mathcal{A}}\left[\sum_{x \in \mathcal{X}} N_{T}(x) \mathrm{KL}_{x}(\mathbf{M} || \mathbf{M}')\right] \geq \mathbb{E}_{s}^{M, \mathcal{A}}[\log(U)]. $$

**Proof** We write:

$$ \begin{aligned} \mathbb{E}_{s}^{M', \mathcal{A}}[U] &\overset{\circ 1}{\geq} \mathbb{E}_{s}^{M, \mathcal{A}}[U \exp\{-L(H_T)\}] \\ &= \mathbb{E}_{s}^{M, \mathcal{A}}[\exp\{-L(H_T) + \log(U)\}] \\ &\overset{\circ 2}{\geq} \exp\{\mathbb{E}_{s}^{M, \mathcal{A}}[-L(H_T) + \log(U)]\} \\ &\overset{\circ 3}{=} \exp\left\{-\mathbb{E}_{s}^{M, \mathcal{A}}\left[\sum_{x \in \mathcal{X}} N_{T}(x) \mathrm{KL}_{x}(\mathbf{M} || \mathbf{M}')\right] + \mathbb{E}_{s}^{M, \mathcal{A}}[\log(U)]\right\} \end{aligned} $$

where ($\circ 1$) follows by Theorem C.1; ($\circ 2$) uses Jensen's inequality; and ($\circ 3$) follows by Lemma C.2. Conclude by taking the log and rearranging terms. ■

**Corollary C.4.** Let $M \ll M'$ two Markov decision processes and fix an arbitrary learning agent $\mathcal{A}$ and $s \in S$. If $\mathcal{E}$ is a $\sigma(H_T)$-measurable event, then:

$$ \mathbb{E}_{s}^{M, \mathcal{A}}\left[\sum_{x \in \mathcal{X}} N_{T}(x) \mathrm{KL}_{x}(\mathbf{M} || \mathbf{M}')\right] \geq \mathrm{kl}\left(\mathbb{P}_{s}^{M, \mathcal{A}}(\mathcal{E}), \mathbb{P}_{s}^{M', \mathcal{A}}(\mathcal{E})\right). $$

**Proof** For conciseness, we write $\mathbb{E}[-], \mathbb{E}'[-]$ rather $\mathbb{E}_{s}^{M, \mathcal{A}}[-], \mathbb{E}_{s}^{M', \mathcal{A}}[-]$, and $\rho := \mathbb{P}(\mathcal{E})$ and $\rho' := \mathbb{P}'(\mathcal{E})$.

If $\rho = \rho'$, there is nothing to prove. Up to considering $\mathcal{E}^c$, we can assume that $\rho > \rho'$. We have:

$$ \begin{aligned} \mathbb{E}\left[\sum_{x \in \mathcal{X}} N_T(x) \mathrm{KL}_x(\mathbf{M} || \mathbf{M}')\right] &\geq \sup_{\lambda \geq 0} \left\{\mathbb{E}[\log(\lambda + 1(\mathcal{E}))] + \log \mathbb{E}'(\lambda + 1(\mathcal{E}))\right\} \\ &= \sup_{\lambda > 0} \left\{\rho \log(\lambda + 1) + (1 - \rho) \log(\lambda) - \log(\lambda + \rho')\right\} =: \sup_{\lambda > 0} \varphi(\lambda) \end{aligned} $$

The supremum of $\varphi$ is reached for $\lambda := \frac{\rho'(1-\rho)}{\rho-\rho'}$, and with a bit of algebra, we find that $\sup_{\lambda>0} \varphi(\lambda) = \mathrm{kl}(\rho, \rho')$. This concludes the proof. ■
List of notations

a action

$A_t$ played action at time $t$

$\mathcal{A}(s)$ action space from $s$

Alt($\mathbf{M}$) alternative set of $\mathbf{M}$

Ben($\pi, \mathbf{M}$) beneficial set of $\pi$ in $\mathbf{M}$

Ben$_*(\pi, \mathbf{M})$ beneficial-confusing set of $\pi$ in $\mathbf{M}$

Cnf($\mathbf{M}$) confusing set of $\mathbf{M}$

$D(\mathbf{M})$ diameter

$\mathbf{\Delta}_*$ Bellman gaps

$\min(-)$ definite minimum (minimal $> 0$ en-
try)

$\mathbb{E}_{s_0}^{\mathbf{M},\mathcal{A}}$ expectation under $\mathbf{M}$ and $\mathcal{A}$ initialized
at $s_0$

$\mathbf{g}_{\pi}$ gain vector of policy $\pi$

$\mathbf{g}_{*}$ optimal gain vector

$\mathbf{b}_{\pi}$ bias vector of policy $\pi$

$\mathbf{b}_{*}$ optimal bias vector

$H_t$ random history at time $t$

$\mathcal{H}$ history space

Inv($\mathbf{M}$) invariant measures of $\mathbf{M}$

$K(\mathbf{M})$ regret lower bound with contraction

$K_*(\mathbf{M})$ regret lower bound without contraction

KL($-||-$) Kullback-Leibler div.

KL$_x(\mathbf{M}||\mathbf{M}^\dagger)$ KL at pair $x$ between $\mathbf{M}$ and $\mathbf{M}^\dagger$

kl(-, -) KL for Bernoulli distributions

$L(H_T; \mathbf{M}, \mathbf{M}^\dagger)$ log-likelihood ratio of obser-
vations

$\mathbf{m}$ mean reward

$\mathbf{M}$ reference hidden model

$\mathbf{M}^\dagger$ alternative/confusing model

$\mathbf{M}/\mathcal{X}_0$ minor of $\mathbf{M}$ by $\mathcal{X}_0$

$\mathcal{M}$ space of MDPs

$\mu$ invariant measure

$N, N_T(s, a)$ Visit vector

$\mathbf{p}$ transition kernel

$\mathcal{P}$ kernel space

$\pi, \pi^*$ policy, optimal

$\mathcal{A}$ learning agent

$\Pi$ deterministic policies

$\Pi^{\text{SR}}$ randomized policies

$\Pi^*(\mathbf{M})$ gain optimal policies of $\mathbf{M}$

$\mathbb{P}_{s_0}^{\mathbf{M},\mathcal{A}}$ probability under $\mathbf{M}$ and $\mathcal{A}$ initialized
at $s_0$

$\mathbf{r}$ reward distributions

$R_t$ random reward at time $t$

$\mathcal{R}$ reward space

Reg(-) expected regret

$s$ state

$S_t$ random state at time $t$

$[s]$ contracted state

$\mathcal{S}$ state space

$[S]$ contracted state space

$\text{sp}(-)$ span function

$t$ time instant

$T$ time horizon

$\mathcal{U}(\pi, \mu, \mathbf{M})$ unlikelihood of optimality

$x$ state-action pair

$X_t$ pair at time $t$

$\mathcal{X}$ state-action pairs

$\mathcal{X}_-(\mathbf{M})$ sub-optimal pairs $\mathbf{M}$

$\mathcal{X}_{\star}^-(\mathbf{M})$ weakly optimal pairs $\mathbf{M}$

$\mathcal{X}_*(\mathbf{M})$ optimal pairs of $\mathbf{M}$