Victor Boone

Bruno Gaujal

Identification of Blackwell Optimal Policies for Deterministic MDPs

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Blackwell optimality [START_REF] Blackwell | Discrete dynamic programming[END_REF] is arguably the most refined optimality criterion that exists on Markov Decision Processes (MDPs). Indeed, Blackwell optimal policies optimize the gain, the bias, higher order biases, as well as β-discounted scores for high enough discount factors β, see [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. Despite its properties, Blackwell optimality drew very little attention from reinforcement learning communities. There are actually several hurdles that make learning Blackwell optimal policies difficult. First, the computation of Blackwell optimal policies is already tedious, even when the MDP is fully known [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF], and its complexity is still open. Also, there is no concept of "near" Blackwell optimality because of the hierarchy involved in its definition so that one cannot gradually approach Blackwell optimal policies. This makes learning even harder. To our knowledge, this paper is the first to investigate the Blackwell optimal policy identification problem within the PAC-RL framework [START_REF] Fiechter | Efficient reinforcement learning[END_REF]; [START_REF] Strehl | Probably approximately correct (PAC) exploration in reinforcement learning[END_REF]. We focus on the generative model setting [START_REF] Kearns | Finite-sample convergence rates for Q-learning and indirect algorithms[END_REF], where the learner is allowed to sample state-action pairs without restriction and halts according to a stopping time. This random time is such that the algorithm is able to produce an optimal policy with an a priori fixed confidence. This work focuses on MDPs with deterministic transitions where unlike general MDPs, the transition structure is easily determined by a learner. Learning such MDPs is analogue to learning on graphs with unknown probabilistic arc-weights; albeit learning Blackwell optimality is nothing alike a routing problem. Together with the generative model assumption, the problem resembles best arm identification in the multi-armed bandit case with exponentially many correlated arms.

Our contributions. We show that learning a Blackwell optimal policy is possible if and only if the maximal mean weight cycle is unique (H1) and the bias optimal policy is unique (H2). Under these assumptions, Blackwell optimality collapses to bias optimality, which means that optimalities of higher orders cannot be identified on MDPs when they strictly refine bias optimality. We provide a learning algorithm scheme based on generalized Bellman coefficients, together with explicit bounds on its asymptotic expected number of transition samples. We further show that when rewards are Gaussian, then up to multiplicative constants, the performances of our methods compare to lower bounds of possible performances. Related Work. Regret minimization is a popular way to address learning on MDPs. For example, UCRL2 Auer et al. (2009) is an unavoidable milestone in that direction, with its contemporary UCYCLE [START_REF] Ortner | Online regret bounds for Markov decision processes with deterministic transitions[END_REF] analogue which is specific to deterministic MDPs. For a more recent review of the state-of-the-art, refer to [START_REF] Wei | Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes[END_REF]. In spite of this abundant literature, the design of a no-regret learning setting for Blackwell optimality is still missing and arguably conceptually difficult. Instead, another way to learn is to measure how likely it is that a learner may identify an optimal policy after a given number of samples, leading to policy search problems, e.g. instant regret [START_REF] Bubeck | Pure Exploration in Multi-armed Bandits Problems[END_REF] and probably approximately correct [START_REF] Fiechter | Efficient reinforcement learning[END_REF] settings.

For the special case of multi-armed bandits, [START_REF] Bubeck | Pure Exploration in Multi-armed Bandits Problems[END_REF] argues that efficient policy search and regret minimization are orthogonal learning tasks.

As far as policy identification with generative model is concerned, the minimax approach is the most common, with a major focus on the discounted settings, see [START_REF] Azar | Speedy Q-learning[END_REF]; Gheshlaghi [START_REF] Gheshlaghi Azar | Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model[END_REF]; Li et al. (2021) and references therein. The finite horizon case is dealt in [START_REF] Dann | Sample complexity of episodic fixed-horizon reinforcement learning[END_REF]; [START_REF] Wang | Is long horizon reinforcement learning more difficult than short horizon reinforcement learning?[END_REF]; [START_REF] Domingues | Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited[END_REF]; [START_REF] Li | Settling the horizon-dependence of sample complexity in reinforcement learning[END_REF]. Worth mentioning is the work of [START_REF] Tarbouriech | Sample complexity bounds for stochastic shortest path with a generative model[END_REF] dedicated to the stochastic shortest path problem (SSP) on a type of MDP with zero-reward absorbing state, where optimal policies are de facto bias optimal ones. Although their work may be considered as a first step toward the learning of higher order optimalities, it doesn't cover the general class of (deterministic) MDPsand is not motivated as such. As far as the minimax setting is concerned, the performances of the learner are bounded by her performances for the worst possible MDP; by performances, understand the number of samples the learner asks to guess an optimal policy. For pure identification without ϵ-tolerance on the suboptimality of policies, there exist MDPs for which the lower bounds of achievable runtimes can be made arbitrarily big. In this case, the minimax approach is irrelevant. This is especially the case for Blackwell optimality, as, to our knowledge, there is no notion of ϵ-Blackwell optimality. In the present paper, the expected sample complexity is compared to instance specific lower bounds of the possible performances in the line of the works of [START_REF] Kaufmann | On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models[END_REF] and [START_REF] Garivier | Optimal Best Arm Identification with Fixed Confidence[END_REF] who provide information-theoretical lower bounds of the expected sample complexity in the best arm identification problem for multi-armed bandits. Recently, this approach has been extended to discounted MDPs with generative model by Marjani and Proutiere (2021) and with navigation constraints by Marjani et al. (2021). Our methods were inspired by this line of work [START_REF] Kaufmann | On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models[END_REF]; Marjani and Proutiere (2021); Marjani et al. (2021), especially for the derivation of lower bounds and the exploration methods (D-tracking rule).

BLACKWELL OPTIMALITY AND DETERMINISTIC MDPS

Throughout the paper vectors are column vectors by default. We use the infinity-norm on matrices ∥(A ij ) ij ∥ = max i j |A ij |. Accordingly, we use the infinity-norm on column vectors and the one-norm on row vectors. For p > 0 and (a i ) a non-negative vector, we denote ∥(a i )∥ p := ( i a p i ) 1/p . KL(-∥-) denotes the Kullback-Leibler divergence and kl (u, v) is the divergence between Bernoulli distributions of parameters u and v. The simplex of R m is denoted ∆ m .

Let us consider a finite Markov decision process (MDP) M with n states and A actions M = (S, A, P, q), where S is the state space (of size n), A := x∈S A x is the action space, P is the transition kernel and q the reward distribution (each time action a is taken in state x, it gets a random real reward with distribution q(x, a)). Reward distributions are assumed to be sub-Gaussian 1 with means r(x, a) and standard deviation σ. A policy is a stationary deterministic decision rule π : S → A that, for each state x ∈ S, selects a legal action a ∈ A x . We write π ∈ Π. Also, a policy π defines a) a Markov chain on S with transition kernel P π given by P π (x, y) := P (y|x, π(x)); and b) a reward vector r π of coordinates r π (x) := r(x, π(x)).

Blackwell optimality

The performances of a policy can be measured in various ways. Some performance measures only depend on the transient behavior of the MDP, such as the sum of the rewards over a finite horizon, or the discounted infinite sum of the rewards. For instance, the β-discounted value of a given policy π, starting from state x 0 , is

v π β (x 0 ) := E π ∞ t=0 β t r(X t , π(X t )) (1)
where X t denotes the visited (random) state at time t under the iterations of π. Other performance measures only depend the stationary behavior of the MDP, such as the long run average gain. The long run average gain in state x 0 of a policy π is

g π (x 0 ) := lim T →∞ 1 T T -1 t=0 r(X t , π(X t )). (2)
As for Blackwell optimality, it depends on both the transient and the stationary behaviors of the MDP and therefore may supersede both discounted optimality and average gain optimality. Blackwell optimality was historically defined using that transient approach [START_REF] Blackwell | Discrete dynamic programming[END_REF]:

Definition 1. A policy π * is Blackwell optimal if it satisfies v π * β ≥ v π
β for all policies π and all 1 > β > β ∞ , for some threshold discount factor β ∞ < 1. The set of Blackwell optimal policies will be denoted Π * ∞ (M ).

Another possible definition of Blackwell optimal policies uses the average gain and biases. The set of gain-optimal policies (maximizing (2)) is denoted Π * -1 (M ). Now, two policies with the same gain may be distinguished by a second order quantity, namely their 0-bias (or simply bias). If

1 A random variable R is sub-Gaussian with mean r ∈ R and standard deviation σ > 0 if P {|R -r| > t} ≤ exp -t 2 2σ 2 .
P * π is the Cesàro limit of the sequence (P n π ) n∈N , then the bias is defined as

h π := ∞ t=0 [P t π -P * π ]r π . (3)
A policy π is bias-optimal if it achieves maximal bias in addition to maximal gain, i.e. for all π ′ ∈ Π and x ∈ S,

either g π ′ (x) ≤ g π (x) or h π ′ (x) ≤ h π (x) with g π (x) = g π ′ (x).
Their set is denoted Π * 0 (M ). This refinement can be pushed further. The k-bias of π, for n ≥ 1 is

h (k) π := - ∞ t=0 [P t π -P * π ]h (k-1) π , (4)
where h

π stands for h π . A policy that optimizes the gain and all biases up to the k-bias is said k-bias optimal. Their set is denoted Π * k (M ). It has been shown (see [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF], for example) that this refinement stops when k = S (i.e. Π * k (M ) = Π * S (M ) for all k ≥ S) and this set coincides with Π * ∞ (M ) in Definition 1.

Deterministic MDPs

Definition 2. A MDP M is deterministic if its transition kernels P (•|x, a) are degenerate; Specifically, if ∀x, y ∈ S, ∀a ∈ A x , P (y|x, a) ∈ {0, 1}. From a given state x, the choice of an action a ∈ A x uniquely determines a successor s(x, a) such that P (s(x, a)|x, a) = 1. This way, a DMDP is naturally endowed with a multidirected graph structure whose multi-arc spaces is identifiable by Z the set of state-action pairs (x, a). In the sequel, m denotes the size of Z. The elements of a family M of DMDPs that share the same transition structure P can be identified by their mean reward vector (r(z) : z ∈ Z) that belongs to R m . M hence inherits the topology of R m , making it a topological space.

Actually, many important examples of MDPs are deterministic, for example games such as Chess, Go, grid games and more, see [START_REF] Shah | Non-Asymptotic Analysis of Monte Carlo Tree Search[END_REF] for more. Already mentioned in the introduction is also the example of routing problems. Trying to learn, on a network with random delays on transitions, how to route a packet to a fixed destination, is a subcase of learning Blackwell optimality (yet on such problems, only the transient costs matter). Overall, the properties of Blackwell optimality in the deterministic setting are strikingly graph friendly, as explained below.

Gain and bias on DMDPs. When transitions are deterministic, the iterates (X t : t ≥ 0) of π starting from x ∈ S are no more random. To insist on their deterministic nature, these are lowercased as x t . Those iterates eventually converge in finite time to a terminal cycle C π x ⊆ S and the gain is the average reward on that cycle. Visually,

g π (x) = g(C π x ) := 1 |C π x | u∈C π x r(u, π(u)).
(5) Also, the bias h π (x) takes a particular form in DMDPs:

Proposition 1. Let π : S → A a policy and x ∈ S. Denote x t the state at time t under the iterations of π (from x = x 0 ), and let z t := (x t , π(x t )). If T ≥ 0 is such that x T ∈ C π x , then the bias expands as

h π (x) = T -1 t=0 [r(z t ) -g(C π x )] (transient) + 1 |C π x | |C| ℓ=1 ℓ-1 t=0 [r(z T +t ) -g(C π x )]. (recurrent)
This formula indicates that the bias is, roughly speaking, the normalized weight of the path to the terminal cycle. It will be useful to assess the performance of the identification algorithm presented later.

POLICY IDENTIFICATION IN DMDPS

The very purpose of this paper is the identification of Blackwell optimal policies in the generative model, in a similar fashion to best arm identification for stochastic bandits in [START_REF] Kaufmann | On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models[END_REF]. By generative model, we mean that at each time step, the algorithm is allowed to sample any edge. An identification algorithm I consists in three components :

• an allocation rule that chooses the next sampled state-action pair Z t := (X t , A t ), then observes the transition R t ∼ q(X t , A t ), Y t ∼ P (•|X t , A t ) and is measurable with respect to the usual filtration F t-1 of the history

(X 1 , A 1 , R 1 , Y 1 , . . . , X t-1 , A t-1 , R t-1 , Y t-1 );
• a stopping rule τ δ that must be a stopping time with respect to (F t | t ≥ 0), where δ > 0 is a confidence parameter;

• a recommendation rule to return a policy π I τ δ when the algorithm stops, which is F τ δ -measurable. 2 Definition 3. An identification algorithm I (see above) is said δ-probably correct (δ-PC) on M if

P M,I τ δ < ∞ and π I τ δ ∈ Π * ∞ (M ) ≥ 1 -δ.
Its expected sample complexity is E M,I [τ δ ].

2 i.e., for all T ≥ 1 and π ∈ Π,

{τ δ = n} ∩ {πτ δ = π} ∈ FT
Visits and empirical model. Let t ≥ 1 a time instant.

The visit count of a state-action pair z ∈ Z is denoted N t (z) := t-1 i=1 1 Zi=z and by N t is meant their vector. The DMDP of empirical observations up to time t is the DMDP of maximum likelihood, i.e., the DMDP Mt with reward distributions qt (z) := N t (z) -1 t-1 i=1 1 Zi=z Dirac(R i ). The associated mean reward vector rt is called the empirical mean reward vector.

A mandatory set of assumptions

We make the following assumptions.

Assumptions. First, it is reasonable to assume that the transition structure P is fixed and known to the learner because can be learned in O(m). The underlying multigraph is refered to as G. We assume that G has a unique final strongly connected component. This corresponds to the usual weakly communicating assumption made on MDPs. The two following hypothesis replace the uniqueness of the optimal policy used in Marjani and Proutiere (2021) for the discounted case.

H1 M has a unique optimal cycle: the cycle C * maximizing the average expected reward

1 |C * | (x,a)∈C * r(x, a) is unique.
H2 M has a unique bias-optimal policy π * M .

These assumptions are independent: there exists DMDPs where H2 is satisfied but H1 is not (and vice-versa), see Figure 1.

0 3 2 2
Figure 1: A DMDP where H2 is satisfied but H1 is not. The identification of Blackwell optimal policy is impossible by Theorem 1.

Optimal policy, gain and bias. The uniqueness of the bias-optimal policy implies that Blackwell optimality collapses to bias optimality, that is Π * ∞ (M ) = Π * 0 (M ), and we denote by π * M (or π * ) the unique element of Π * 0 (M ). Also, the optimal gain and bias are respectively g * = g π * M and h * = h π * M . Outside H1 and H2, the identification of Blackwell optimal policies may be impossible. Here is why.

Let H denote the class of DMDPs with graph G that satisfies H1 and H2.

Outside the domain spawned by H1-H2, the PAC-RL setting isn't sound: no algorithm can correctly identify Blackwell optimal policies with arbitrarily high confidence and stop almost surely on every entry, apart from H. The space H is thus the largest set on which Blackwell identification is possible. The precise statement is given below: Theorem 1. Let I be an identification algorithm and let δ ∈ (0, 1 4 n -n ). Let D I be the set of DMDPs on which I is δ-probably correct. The two following assertions hold:

(i) The interior of D I is in H: DI ⊆ H; (ii) If D I contains H, D I = H.
Sketch of the proof. (i) Assume on the contrary that DI ∩ H ∁ ̸ = ∅ and choose M a member of the intersection. By definition, there exists B ⊆ D I open that contains M . For M , there exists a policy π that the algorithm returns with probability greater than n -n . If M / ∈ H, one can find arterial close copies of M such that π / ∈ Π * (M ′ ). Then, the algorithm can be fooled by choosing M ′ arbitrary close to M , so that when running on M ′ , the algorithm returns π with probability approximately n -n . In particular, we can choose M ′ ∈ B; Yet I isn't δ-PAC on M ′ . A contradiction.

(ii) With a similar proof, one can show that if D I contains H, then D I = H, whence the maximality of H regarding identification.

Remark 1. Theorem 1 implies that there is no universal δ-PC algorithm, that is, no I such that D I = M. Remark 2. The assertion (i) cannot be improved to D I ⊆ H for all I, because for every M and π any of its Blackwell optimal policy, the algorithm I(M ) that stops at time 1 and returns π is correct on M .

We'd like to insist on the fact that under H1-H2, Π * 0 (M ) is a singleton, so that Π * ∞ (M ) = Π * 0 (M ). In particular, the identification of k-discounted optimalities Puterman (1994) of order k ≥ 1 is impossible unless they collapse to bias optimality. We end up with the following principle:

Probably correct identification cannot go beyond bias optimality.

As a final remark, while H1-H2 certainly restrict the class of DMDPs where Blackwell optimality can be identified, they are also generic in Baire categories sense. Proposition 2. [•] VB: check the proof H is generic in Baire categories sense. In particular, M \ H has null Lebesgue measure.

This says that a DMDP whose expected rewards are chosen randomly (continuously w.r.t the Lebesgue measure) will be in H with probability one.

Characterization of bias optimal policies on H

Bias optimality is unique under H1 and H2. There is more to it; It is pretty easy to tell whether or not π ∈ Π * 0 (M )

when M ∈ H. It is well-known, see [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF], that a policy is bias optimal if it satisfies three nested Bellman optimality equations. In the deterministic setting, these equations take the simpler form: for all x ∈ S and a ∈ A x :

P (x, a) • g π ≤ g π (x) r(x, a) -g π (x) + P (x, a) • h π ≤ h π (x) -h π (x) + P (x, a) • h (1) π ≤ h (1) π (x),
with equality when a = π(x). Besides, a policy satisfying these equations achieves optimal gain and bias. The converse is false in general, so what about policies that only satisfy the two first conditions? In general, they may fail to achieve optimal bias. On H, the story is different.

Proposition 3. Let M ∈ H a DMDP. A policy π ∈ Π is bias optimal if, and only if g π (x) does not depend on x ∈ S and

∀(x, a) / ∈ π, r(x, a) -g π (x) + P (x, a)h π < h π (x).
In particular, π * M is the unique policy with unique terminal cycle such that this equation holds. Moreover, a DMDP satisfies H1 and H2 if, and only if there is a policy satisfying this equation with unique terminal cycle.

This provides a characterization of suboptimal policies: if g π is a constant vector, then π / ∈ Π * 0 (M ) iff it contains a sub-optimal transition: ∃x ∈ S, r(x, π(x)) -g * (x) + P π (•|x)h * < h * (x). (6) For (x, a) ∈ Z, the quantity

∆(x, a) = h * (x)-[r(x, a)-g * (x)+P (x, a)h * ] > 0 (7)
measures by how much (x, a) is suboptimal. These quantities, called Bellman gaps, do play an important part in the design of identification algorithms. Equation ( 6) is also of interest for effective computations of Blackwell optimal policies, providing a node-to-node criterion to determine whether or not a policy is bias optimal. Under H1, this leads to the computation of bias optimal policies in O(nm) execution time, see Appendix E.1 for more details.

THE LSTS METHOD

In this section, we present a general method to design identification algoritms that are δ-probably correct on H for all δ > 0. The performances of our methods, if well-tuned, are comparable to lower bounds up to explicit multiplicative factor in the asymptotic regime.

D-tracking Scheme

The standard way to estimate the plausible parameters of the MDP is to construct individual confidence intervals for the estimates of the mean rewards' values, leading to confidence sets in product form, see for e.g. the literature on regret minimization [START_REF] Auer | Near-optimal Regret Bounds for Reinforcement Learning[END_REF]; [START_REF] Filippi | Optimism in Reinforcement Learning and Kullback-Leibler Divergence[END_REF]; [START_REF] Fruit | Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning[END_REF]; [START_REF] Bourel | Tightening Exploration in Upper Confidence Reinforcement Learning[END_REF] or PAC-RL on discounted MDPs [START_REF] Azar | Speedy Q-learning[END_REF]; Gheshlaghi [START_REF] Gheshlaghi Azar | Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model[END_REF]; Li et al. (2021).

From a frequentist viewpoint, that confidence set is centered at the model of maximum likelihood Mt = (r t ) where rt is the vector of empirical mean rewards. The confidence set is hence of the form

M δ t = Mt + Λ δ t . (8)
Here, Λ δ t is a product of confidence intervals. Specifically,

Λ δ t := (-ϵ δ (N t (x, a), t), ϵ δ (N t (x, a), t)) with ϵ δ (s, t) := 2σ 2 log( 4mt 3 δ ) max(1, s) 1/2 . ( 9
)
The confidence value ϵ δ is tuned in order to provide timeuniform confidence sets, see the result below.

Proposition 4. For all I, t P M,I {M / ∈ M δ t } ≤ δ.

The set M δ t is refered to as the set of plausible MDPs. It appears natural to stop the learning phase whenever all plausible MDPs share the same optimal policy. Regarding policy identification, boxes of special interest are those centered at M in the style of (8) such that every alternative MDP inside that box has the same optimal policy than M . This motivates the following definition. Definition 4. A box is any element of the family generated by Γ : H → R m + → 2 H , defined as follows:

Γ(M, ℓ) := M + x,a (-ℓ(x, a), ℓ(x, a)). A box B is said Π * ∞ -constant if ∀M, M ′ ∈ B, Π * ∞ (M ) = Π * ∞ (M ′ ). A family B = {B(M ) : M ∈ H} is (1) Π *
∞constant if all its boxes are; and (2) is continuous if it is continuous with respect to the topology on boxes given by the Hausdorff distance between closed sets in R m . Also, write ℓ B = ℓ the half-width vector of B = Γ(M, ℓ).

Let us consider an identification algorithm whose estimate at time t is Mt . If B is a Π * ∞ -constant family, then whenever " M δ t ⊆ B( Mt )" holds, the set of plausible MDPs (including M with probability 1 -δ) have the same optimal policy than Mt . This provides a natural stopping time. Of course, the algorithm should explore efficiently to guarantee that M δ t ⊆ B( Mt ) holds for t as small as possible. The thing is that if Mt is guaranteed to converge to M almost surely, and if B is continuous, then B( Mt ) will resemble B(M ) in the long run. In that scenario, B( Mt ) will stabilize eventually. This suggests that exploration can be done with respect to one target box. In the following algorithmic scheme, the exploration is driven by a frequency parameter ω : H → ∆ m , so that t • ω t (z) is the target value of the number of visits N t (z). Some extra forced exploration is added to keep good convergence properties. It is fixed to the D-tracking rule of Marjani et al. (2021) for simplicity.

Algorithm 1 D-tracking scheme with boxes. Require: confidence parameter δ ∈ (0, 1), continuous exploration coefficients ω :

H → ∆ m , never-empty con- tinuous Π * ∞ -constant family B : H → {boxes}. Ensure: returns a policy π δ ∈ Π * ∞ (M ) with probability 1 -δ. 1: Sample independent u t ∼ U([-1, 1] m ) (t ≥ 1); 2: for t = 1, 2, . . . , do 3: if M δ t ⊆ B( Mt ) then 4: return π * ( Mt ) 5: end if 6: compute sampling rates ω t ← ω((1 -1 t )r t + 1 t u t ); 7: set U t ← (x, a) ∈ Z | N t (x, a) < √ t -m/2 ; 8:
the D-tracking rule Marjani et al. (2021) selects

(X t , A t ) among argmin x,a [N t (x, a)] if U t ̸ = ∅, argmin x,a [N t (x, a) -t • ω t (x, a)] if U t = ∅; 9:
observe reward R t ∼ q(X t , A t ); 10: end for Proposition 5 (Correctedness). Every D-tracking scheme is δ-probably correct on DMDPs in H.

Sketch of the proof. We show in the appendix that following B(M ) ̸ = ∅, we have P M {τ δ < ∞} ≥ 1 -δ. Then, by Proposition 4, the probability that for all t,

M δ t contains M , is at least 1 -δ. Also, if M δ t ⊆ B( Mt ), then for all M ∈ M δ t , we have Π * ∞ ( M ) = Π * ∞ ( Mt ). All together, P τ δ < ∞, π * ( Mτ δ ) / ∈ Π * ∞ (M ) ≤ P τ δ < ∞, M / ∈ B( Mτ δ ) ≤ t≥1 P τ δ = t, M / ∈ M δ t ≤ t≥1 P M / ∈ M δ t ≤ δ.
Proposition 6 (Performances). A D-tracking scheme stops on M ∈ H a.s.; Also,

lim inf δ→0 E M [τ δ ] log(1/δ) ≥ z 2σ 2 ℓ B(M ) (z) 2 . Moreover, if exploration parameters are ω ∝ ℓ -2 B(•) , then lim δ→0 E M [τ δ ] log(1/δ) = z 2σ 2 ℓ B(M ) (z) 2 .
Sketch of the proof. Termination is guaranteed because the D-tracking rule ensures that every edge is visited Ω( √ t) times hence infinitely often. Therefore, Mt → M a.s., so B( Mt ) → B(M ) by continuity. Finally, we show that Ω( √ t) visits are enough to guarantee that the set of plausible MDPs gets within the box B(M ) eventually, and regardless of the confidence parameter δ.

Ignoring logarithmic factors, we rewrite the stopping criterion as

∀(x, a) ∈ Z, 2σ 2 log(4m/δ) N τ δ (x, a) ≤ ℓ B( Mt) (x, a).
For the performance bounds, by property of the D-tracking rule and continuity of ω • , visit counts satisfy N t (x, a) = ω M (x, a)t + o(t) when t goes to infinity. Similarly, we approximate B( Mt ) with B(M ) for large values of t. Accordingly, the previous inequality is asymptotically equivalent to:

∀(x, a) ∈ Z, 2σ 2 log(4m/δ) τ δ ω M (x, a) ≤ ℓ B(M ) (x, a).
Reorganizing terms provides a the lower bound on τ δ :

∀(x, a) ∈ Z, 2σ 2 log(4m/δ) ω M (x, a)ℓ B(M ) (x, a) 2 ≤ τ δ .
Taking the limit when δ → 0, we obtain max

(x,a)∈Z 2σ 2 ω M (x, a)ℓ B(M ) (x, a) 2 ≤ lim δ→0 τ δ log(1/δ)
.

The left-hand term is a convex function of ω M ∈ ∆ m that can be minimized using KKT-conditions. We retrieve the lower bound of the main statement together with the optimal choice of parameters

ω M ∝ ℓ B(M ) (•) -2 .
Construction of good familys. Lemma 6 answers one fundamental question: how does a learner choose exploration coefficients ω • with respect to a continuous Π * ∞constant family? Namely, this solves the problem of (asymptotically) efficient exploration. How familys shall be chosen is an orthogonal task.

Lower Bounds

We deviate the from main story to deal with the computation of a general lower ground of a learner's possible performances. This will serve as a reference ground for our next algorithms to come. This bound generalizes exiting results and techniques from the multi-armed bandit settings (Kaufmann et al., 2016, Theorem 4). The transport of these information-theoretical results to MDPs is not new and already exist in the context of discounted optimality identification (Marjani and Proutiere, 2021, Proposition 1), (Marjani et al., 2021, Lemma 1) and regret minimization on deterministic MDPs (Tranos and Proutiere, 2021, Proposition 3). Proposition 7. Let M, M ′ ∈ H two DMDPs with different bias-optimal policies such that q(x, a) and q ′ (x, a) are mutually absolutely continuous for all edges. Every δ-PC algorithm satisfies

z∈Z E M [N τ δ (z)] KL(q(z)∥q ′ (z)) ≥ kl(δ, 1 -δ).
For the sake of self-containedness, we explain how to shift the proof of (Kaufmann et al., 2016, Theorem 4) to fit Proposition 7 in the appendix.

The next section address the issue of efficient stopping times. In the light of Proposition 6, this is about the design of continuous Π * ∞ -constant familys such that x,a ℓ B(M ) (x, a) -2 is small. As the learning effort should not be uniform of transitions, the question is how the difficulty of a specific transition should be quantified.

A local suboptimality gap method

The local suboptimality gap method presented in the sequel attaches to each transition a difficulty related to how easily the optimal policy is subject to change under unilateral perturbations of the associated mean reward value. Because these quantities are defined by looking at edges in isolation, we refer to them as local suboptimality gaps. Definition 5 (Local suboptimality gap). Let M a DMDP and r ∈ R m its mean reward vector. The local suboptimality gap at (x, a) ∈ Z is given by

L M (x, a) := sup    ϵ > 0 : Π * ∞ (r + ϵe xa ) = Π * ∞ (r) and Π * ∞ (r -ϵe xa ) = Π * ∞ (r)    .
These local suboptimality gaps are continuous on H. Roughly speaking, these are "generalized" Bellman coefficients. Indeed, L M (x, a) = ∆ M (x, a) when (x, a) is not a transition of the optimal policy; Otherwise, ∆ M (x, a) = 0 while L M (x, a) > 0 can be expressed with respect to other ∆ M (y, b) and traveling times in M , see Lemma 11 in the Appendix. Also, the collection (L M (x, a) : (x, a) ∈ Z) can be computed in time O(nm), see Lemma 14 in the Appendix.

Notice that for multi-armed bandits, this definition readily converts to mean reward differences between optimal and suboptimal arms. That last observation, together with the ideas from [START_REF] Kaufmann | On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models[END_REF], leads to a simplification of the lower bound given by Lemma 7 that relies on local suboptimality gaps -thus a tractable lower bound. This is especially striking when rewards are Gaussian. Proposition 8 (Edgewise Lower Bound). Let M ∈ H with Gaussian rewards of standard deviation σ > 0. For all δ-PC identification algorithm,

E M [τ δ ] kl(δ, 1 -δ) ≥ σ 2 z∈Z 1 L M (z) 2 .
The lower bound is basically σ 2 ∥(L -1

x,a )∥ 2 2 . By definition, local suboptimality gaps are about the local deviations of mean rewards that leave the optimal policy invariant. The next result provides a condition to shift these local deviations to global ones, hence explains how to build Π * ∞constant familys from local suboptimality gaps. Proposition 9. Let ρ :

H → R m + a continuous function. The family B ρ : H → Γ given by M + z∈Z (-ρ M (z)L M (z), ρ M (z)L M (z)) is a continuous family. If in addition, a) ρ M (z) > 0 for all z ∈ Z; and b) ∀M , ∀π ∈ Π, z∈π∪π * M ρ M (z) ≤ 1, then B ρ is Π *
∞ -constant and is never empty.

Namely, set B ρ (M ) = Γ(M, ℓ) with ℓ(z) = ρ M (z)L M (z).
In the continuity of Lemmas 5 and 6, we already know how to choose sampling parameters in order to accelerate the stopping time with respect to a family B ρ . We get the result below.

Theorem 2 (LSTS methods). Algorithms following the scheme 1 with familys of the form B ρ and exploration parameters ω ∝ (ρL) -2 , where ρ satisfies the conditions a) and b from Lemma 9, are called LSTS algorithms (Local Suboptimality based Track&Stop). These algorithms are δ-probably correct and have asymptotic performances:

lim δ→0 E M [τ δ ] log(1/δ) = 2σ 2 z∈Z 1 ρ M (z) 2 L M (z) 2 .
for M ∈ H with sub-Gaussian rewards of standard deviations σ > 0.

What is left is to optimize ρ. Example 1 (LSTS-cst). Choosing constant coefficients ρ M (z) := 1 2n . The associated exploration parameters are ω ∝ L -2 , with a performance bound

lim δ→0 E M [τ δ ] log(1/δ) = 8n 2 • σ 2 z∈Z 1 L M (z) 2 .
In comparison with the lower bound from Lemma 8, this method is 8n 2 -asymptotically optimal when rewards follow Gaussian distributions of standard deviations σ. Example 2 (LSTS-imp). In general, the computation of the optimal coefficients ρ M (x, a) is difficult. Regarding condition b) from Lemma 9 and the performance bound from Theorem 2, the optimal choices of ρ are solution of the convex optimization problem below:

min ρ z∈Z 1 ρ M (z) 2 L M (z) 2 s.t. ∀π, z∈π∪π * ρ M (z) ≤ 1. (10)
Although the optimization problem is convex, the number of constraints is exponential and from it arises combinatorial difficulties related to the graph structure G. To make the problem tractable, the constraints (10) are strengthened to z ρ M (z) ≤ 1 so the simplified problem becomes:

min ρ z∈Z 1 ρ M (z) 2 L M (z) 2 s.t. z∈Z ρ M (z) ≤ 1. (11)
Proposition 10. The solution of Eq. ( 11) is ρ M ∝ L -2/3 . The induced family B ρ is Π * ∞ -constant and can be improved easily. Indeed, since ρ M satisfies the condition z ρ M (z) ≤ 1, there is some slackness left with respect to the weaker conditions from (10) that can be removed without changing the ratios ρ M (z)/ρ M (z ′ ). It means that this improvement won't change the exploration parameters of the LSTS-method but will induce wider boxes, thus will terminate quicker. This is done like this: Denote ρ the element of the simplex such that ρ ∝ L -2/3 , then pick the largest α ≥ 1 such that αρ satisfies:

∀π ∈ Π, z∈π∪π * αρ M (z) ≤ 1.
Then solve in α:

α = max π̸ =π * z∈π∪π * ρ M (z) -1 . ( 12
)
This value is can be shown to be tractable, inducing the following result.

Theorem 3 (LSTS-imp). Let ρ ∝ L -2/3 . Let α be given by Equation (12). The coefficients ρ ⋆ := αρ satisfy the conditions a) and b) from Proposition 9. The LSTS method with such ρ ⋆ is denoted LSTS-imp (standing for improved LSTS) and achieves:

lim δ→0 E M [τ δ ] log(1/δ) ≤ 8σ 2 n 4/3 m 2/3 z 1 L M (z) 2 .
When rewards are Gaussian with standard deviations σ, LSTS-imp is 8n 4/3 m 2/3 -asymptotically optimal. Sketch of the proof. Check that

α ≥ 2 x max a ρ M (z) -1 . Recall that ρ ∝ L -2/3 then apply Theorem 2. Denote K := lim δ→0 E M [τ δ ]
log(1/δ) for short. Simple algebra leads to:

K ≤ 8σ 2 z L M (z) -2/3 x max a L M (x, a) -2/3 2 .
The function t ≥ 0 → t 1/3 is increasing, so max a L M (x, a) -2/3 = (max a L M (x, a) -2 ) 1/3 . Bound both terms with Hölder's inequality with parameters (3, 3

2 ), we bound K by

8σ 2 m 2/3 ∥L -1 ∥ 2/3 2   n 2/3 x max a L(x, a) -2 1/3   2 .
Bounding max a by a yields the result.

Benefits of LSTS-imp

When all local suboptimality gaps are equal, LSTS-imp and LSTS-cst perform the same, as they explore according to the same exploration coefficients. In general, Theorem 3 only guarantees 8n 4/3 m 2/3 optimality, which is worse than 8n 2 of LSTS-cst. So, was the optimization attempt of ρ worth the shot? One observation is that the 8n 2 factor in LSTS-cst's performances is model agnostic. Specifically, it is always 8n 2 away from the lower bound given by Proposition 7, while LSTS-imp's performance bounds relies on Hölder's inequality which is pessimistic in many scenarios. In opposition to LSTS-cst, LSTS-imp can take advantage of instances where the number of critical edges is small, as in the following example.

Example 3. Consider the family of DMDPs (M n ) given by Figure 2.

1 2 . . . n 1 1 -(2n) -3/2 1 0 1 0 1 0 Figure 2: Family (M n ), n ≥ 1.
Rewards are Gaussian with standard deviation σ. Check that g Mn * (i) = 1 and h Mn * (i) = 0 for all i ≤ n. Also, for all action a, L Mn (i, a) = 1 for i ≥ 2 and L Mn (1, a) = (2n) -3/2 . The graph is 2-regular, so we know that LSTS-imp is 12.7n 2 -optimal, so performs a priori worse than LSTS-cst. In fact, LSTS-imp is much better. Local suboptimality gaps are all equal to 1, excepted for the edges from 1 to 2, where gaps are (2n) -3/2 . The lower bound given by Lemma 7 is

z σ 2 L Mn (z) 2 = 2σ 2 ((2n) 3 + n -1) ≥ 2 4 • σ 2 n 3 .
Ignoring the improvement of LSTS-imp due to the scaling in α, we know by the conjugation of Proposition 10 and Theorem 2 that LSTS-imp's performances are bounded by

z 2σ 2 ρ Mn (z) 2 L Mn (z) 2 = 2σ 2 z 1 L Mn (z) 2/3 3 . Simple algebra leads to lim δ→0 E M [τ δ ] log(1/δ) = 2σ 2 (3n -1) 3 ≤ 2 7 • σ 2 n 3 .
This compares to the lower bound up to a constant factor equal to 8. Namely, LSTS-imp is 8-asymptotically optimal on the family (M n ), thus completely outperforms the 8n 2asymptotical optimality of LSTS-cst.

The last result below generalizes the method used in the previous example by providing a general template to bound the performances of LSTS-imp when few state-action pairs are critical.

Proposition 11. Assume M ∈ H have sub-Gaussian rewards with standard deviation σ > 0. Assume that there exist ϵ > 0 together with a family of distinct state-action pairs

(z i ) k i=1 such that z∈Z L M (z) -2 ≤ (1 + ϵ) k i=1 L M (z i ) -2 .
Thus, if rewards are Gaussian with standard deviations σ, LSTS-imp is 8(k 2 + ϵm 2 )-asymptotically optimal.

PERSPECTIVES

Among possible future research directions, in addition to the general non-deterministic case, the search for improvements of the LSTS scheme is interesting. A first promising direction is the investigation of algorithms relying on more refined confidence sets, e.g. ellipsoid-shaped rather than square-shaped. The latter is seemingly critical and may lead to a significant improvement in performances. See [START_REF] Kaufmann | Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals[END_REF] for a discussion on the disadvantage of square-shaped confidence sets in the case of multi-armed bandits. Another promising direction is to find a convincing way to quantify near-Blackwell optimality. This would open new directions, with new learning problems such as higher order undiscounted regret minimization and minimax PAC Blackwell optimality learning.

This appendix contains the proofs of all the propositions and theorems of the paper (they are restated in the appendix) as well as the proofs of additional lemmas needed in the main proofs or with an interest of their own.

General Notations. transition probability from x to y using a s(x, a)

SYMBOL

successor of x by using a Definition 2 q(x, a) reward distribution on (x, a) ∈ Z Section 2 r(x, a) mean reward on (x, a) ∈ Z Section 2 π, π ′ , π ′′ policy Sections 2 and 2.2

Π, Π(M ) set of policies Section 2 Π ∞ , Π ∞ (M ) set of Blackwell optimal policies Definition 1 Π -1 , Π -1 (M )
set of gain optimal policies Section 2.1 Π 0 , Π 0 (M ) set of bias optimal policies Section 2.1

Π k , Π k (M ) set of k-discounted optimal policies, k ≥ -1 Section 2.1 r π , r π (x), r π x (M ) mean reward vector of π, mean reward of π from x in M Section 2 v π β (x), v π β (x, M ) discounted score of π from x in M Equation (1) C π x
terminal cycle of the iterates of π from x Equation (5) g π , g π (x), g π x (r) gain vector of π, gain of π from x under rewards r Equations ( 2) and (5) h π , h π (x), h π x (r) bias vector of π, bias of π from x under rewards r Equation (3),Proposition 1 h A APPENDIX: GAIN AND BIAS Proposition 1. Let π : S → A a policy and x ∈ S. Denote x t the state at time t under the iterations of π (from x = x 0 ), and let z t := (x t , π(x t )). If T ≥ 0 is such that x T ∈ C π x , then the bias expands as

(k) π , h (k) π (x) k-
h π (x) = T -1 t=0 [r(z t ) -g(C π x )] (transient) + 1 |C π x | |C| ℓ=1 ℓ-1 t=0 [r(z T +t ) -g(C π x )]. (recurrent)
Proof. From the definition of the bias, that is

h π (x) := C -lim E M,π x [ T -1 t=0 [r t -g(C π x )]], follows that h π (x 0 ) = T -1 t=0 [r(z t ) -g(C π x )] + h π (x T ).
Let u 0 = x T and denote u t := π t (u 0 ) the t-th state reached by π from u 0 and let z ′ t := (u t , π(u t )). Introduce the partial sums

S t = t-1 τ =0 [r(z ′ τ ) -g(C * π )]. Remark that for c := |C π x | and all t ≥ 0, z ′ t = z ′ t-⌊t/c⌋c .
Together with the observation S c = 0, we see that

S t = S t-⌊t/c⌋c . Moreover, h π (u 0 ) = lim t→∞ 1 t t-1 τ =0 S τ by definition, hence h π (u 0 ) = lim t→∞ 1 t c ℓ=1 S ℓ t-1 τ =0 1 τ ≡ℓ[c] = c ℓ=1 S ℓ lim t→∞ 1 t t-1 τ =0 1 τ ≡ℓ[c] . Thus h π (u 0 ) = 1 c c ℓ=1 S ℓ . Combine the previous identity with h π (x 0 ) = T -1 t=0 [r(z t ) -g(C π x )] + h π (u 0 ) to get the result.
From H1, all gain optimal policies have the same terminal cycle C * over which they coincide. In particular, we see from Lemma 1 that they share the same bias on C * . Specifically, for (u 0 , u 1 , . . . , u c-1 ) the decomposition of C * introduced in H2, for every gain optimal policy π and i

≤ c -1, h π (u i ) = h * (u i ) := 1 c c ℓ=1 l-1 k=0 [r(u i+k , π(u i+k )) -g(C * )]. Therefore, if π ∈ Π *
-1 (M ) and x 0 ∈ S, for k the smallest integer such that x k ∈ C * , we have

h π (x 0 ) = k-1 i=0 [r(x i , π(x i )) -g(C * )] + h * (x k ).
Accordingly, from H2 follows the uniqueness of π * ∈ Π * 0 (M ) thus bias optimal policies are Blackwell optimal on H. Lemma 1. Let r ∈ R m and π ∈ Π. Recall that C π

x denotes the terminal cycle reached by iterating π from x. For all x,

g π x (r) = |C π x | -1 z∈C π x r(z).
Proof. This is a direct consequence of the fact that under any policy π, a DMDP is a weighted directed graph. All infinite trajectories end up cycling over one simple cycle3 and their average weight is the average weight of this terminal cycle.

Lemma 2. Let r ∈ R m and π ∈ Π. Recall that C π x denotes the terminal cycle reached by iterating π from x. Denote x t the state visited at time t by iterating π from the initial state x = x 0 ∈ S. Introduce the reaching times: x , expand the bias h π x (r) according to Lemma 1 with T such that x T ∈ C π x . Then

τ π x (y) := inf {t ≥ 0 : x t = y} ∈ N ∪ {∞} . Write x ⇝ * π y when τ π x (y) < ∞. For all x ∈ Z, h π x (r) = (y,b)∈π\C π x 1 x⇝ * π y r(y, b) + (y,b)∈C π x 1 - |C π x | + 1 2|C π x | - τ π x (y) |C π x | r(
h π x (αe y,b ) = T -1 t=0 [αe y,b (x t , π(x t )) -g π x (αe y,b )] + h π x T (αe y,b ) = T -1 t=0 αe y,b (x t , π(x t )) = α1 x⇝ * π y . If (y, b) ∈ C π x , choose T = τ π
x (y) i.e. the smallest t such that x t = y. Using Lemma 1 again,

h π x (αe y,b ) = - τ π x (u) t=1 g π x (αe y,b ) + 1 |C π x | |C π x | ℓ=1 ℓ-1 t=0 [αe y,b (x t , π(x t )) -g π x (αe y,b )] = - τ π x (y) |C π x | α + 1 |C π x | |C π x | ℓ=1 1 - ℓ |C π x | α = 1 - |C π x | + 1 2|C π x | - τ π x (y) |C π x | α.
We conclude by linearity of r → h π x (r).

B APPENDIX: ASSUMPTIONS H1 AND H2

Theorem 1. Let I be an identification algorithm and let δ ∈ (0, 1 4 n -n ). Let D I be the set of DMDPs on which I is δ-probably correct. The two following assertions hold:

(i) The interior of D I is in H: DI ⊆ H; (ii) If D I contains H, D I = H.
Proof. Let I be an ϵ-PC identification algorithm that stops almost surely on M ∈ DI \ H with ϵ ∈ (0, 1 4 n -n ). There exists T > 0 such that P M,I {τ ϵ < T } > 1 2 . The total number of policies is bounded by n n , so there must exist a policy π such that P M,I τ ϵ < T, π

I τϵ = π > 1 2 n -n . Since I is ϵ-PC with ϵ < 1 2 n -n , π ∈ Π * ∞ (M ). Now, we construct a MDP M ′ such that (1) π / ∈ Π * ∞ (M ′ ) and
(2) for all D ∈ F T , we have

P M ′ ,I H min(T,τϵ) ∈ D ≥ 1 2 P M,I H min(T,τϵ) ∈ D ,
where H T denotes the history up to time T , that is H

T := (X 0 , Y 0 , R 0 , . . . , X t-1 , Y t-1 , R t-1 ). Let A = 1 + max (x,a)∈Z r(x, a).
H1 Assume that M does not satisfy H1 and write π 1 := π ∈ Π * -1 (M ). Because H1 does not hold, there must exists x ∈ S and π 2 ∈ Π * -1 (M ) such that the terminal cycle C 1 from x by using π 1 and the terminal cycle C 2 from x by using π 2 are different. Let (u, v) ∈ C 2 \C 1 and define M ′ the copy of M such that q ′ (u, a) = (1-( 12 ) 1/T )δ A +( 1 2 ) 1/T q(u, a)), meaning that for any Borelian set U ∈ B([0, 1]),

q ′ (u, v)(U) = 1 -1 2 1 T δ A (U) + 1 2 1 T q(u, v)(U)
as probability measures (δ A is the Dirac at A). Then by construction r ′ (u, a) > r(u, a) so g ′ π2 (x) > g ′ π1 (x). Therefore, π 1 / ∈ Π * -1 (M ′ ). In addition, if Z 1 , . . . , Z T are i.i.d. random variables with laws q ′ (u, v), then for all t ≤ T and

(U 1 , . . . , U T ) ∈ T i=1 B([0, 1]), P (Z 1 , . . . , Z t ) ∈ t i=1 U i = t i=1 P {Z i ∈ U i } ≥ 1 2 t i=1 q(u, v)(U i ).
It follows that for any event D ∈ F T ,

P M ′ ,I {H T ∈ D} ≥ 1 2 P M,I {H T ∈ D} .
This is for the construction when M does not satisfy H1.

H2 The construction is similar when M does not satisfy H2. Find x ∈ S such that π 1 (x) ̸ = π 2 (x) and change q(x, π 2 (x))

to q ′ (x, π 2 (x)) := (1 -( 1 2 ) 1/T )δ A + ( 1 2 ) 1/T q(x, π 2 (x)). If x belongs to a terminal cycle of π 2 , then g ′ π2 (x) > g ′ π1 (x) so π 1 / ∈ Π * -1 (M ); otherwise x is transient for π 2 and we get h ′ π2 (x) > h π2 (x) with h ′ π1 (x) = h π1 (x), so π 1 / ∈ Π * 0 (M ).
Then, by taking D := {H T such that τ ϵ < T and π I τϵ = π}, we obtain

P M ′ ,I π I τϵ = π > 1 4 n -n . As π / ∈ Π * ∞ (M ′ ), follows P M ′ ,I π I τϵ / ∈ Π * ∞ (M ′ ) > 1 4 n -n
. This proves the Theorem.

B.1 Topological properties of H

To be accurate, the property M ∈ H does not depend on the reward distributions q(x, a) but rather on their means r(x, a). Denote R(H) the set of mean reward vectors that correspond to a DMDP of H. As a subset of R Z , R(H) inherits its natural topology.

Lemma 3. R(H) is open.
Proof. Let M ∈ H with mean reward vector r and let π its bias-optimal policy. To emphasize that the gain and the bias of π from a given state x ∈ S are functions of r ∈ R Z , we write g π x (r) and h π x (r). From Theorem 3, π remains optimal under reward profile r ′ , and its terminal is the unique maximal mean weight cycle if and only if

∀(x, a) / ∈ π, r ′ (x, a) -g π x (r ′ ) + h π y (r ′ ) < h π x (r ′ ). Recall that ∆ x,a (r) = h π x (r) -[r(x, a) -g π x (r) + h π y (r)]. Denote dr := r ′ -r.
Using the linearity of the gain and the bias with respect to r, we obtain that π is the unique bias optimal policy under reward profile r ′ if, and only if for all (x, a) / ∈ π * , dr(x, a) -g π x (dr) + h π y (dr) -h π x (dr) < ∆ x,a (r).

The function dr → dr(x, a) -g π x (dr) + h π y (dr) -h π x (dr) is a continuous function of dr and ∆ x,a (r) > 0, thus the set of dr satisfying the equation ( 13) is an open set U x,a ⊆ R Z . One obtains the set of r ′ such that π is the bias unique optimal policy and its terminal cycle the unique maximal mean weight cycle as r + (x,a) / ∈π U x,a , which is open.

Proposition 2. [•] VB: check the proof H is generic in Baire categories sense. In particular, M \ H has null Lebesgue measure.

Proof. Let λ be the Lebesgue measure on R Z . Let C and C ′ two (different) simple cycles of G. The difference between their mean weight under reward profile r ∈ R Z is given by

f (r) := 1 |C| (x,a)∈C r(x, a) - 1 |C ′ | (x,a)∈C ′ r(x, a)
which is a non-trivial linear function of r. Thus, C and C ′ have the same mean weights if, and only if r ∈ ker f which is an hyperplane of R Z . Its Lebesgue measure is null. The set of simple cycles being finite, the set Γ of mean rewards such that at least two simple cycles have the same mean weights satisfies λ(Γ) = 0.

Let r /

∈ Γ and for C a simple cycle, let Π C the set of policy with terminal cycle C. Let π ̸ = π ′ ∈ Π C . There is some x ∈ S such that π(x) ̸ = π ′ (x). Then with the same notations as in the proof of Lemma 3, again, h π x (r) -h π ′ x (r) is a non-trivial linear function of r. Hence h π x (r) = h π ′ x (r) if, and only if r belongs to some hyperplane H π,π ′

x of R Z which has null Lebesgue measure. Finally,

R(H) ∁ = Γ ∪ C simple x∈S π,π ′ ∈Π C π(x)̸ =π ′ (x) H π,π ′
x is a finite union of sets of null Lebesgue measure. Thus λ(R(H) ∁ ) = 0. This means that if r is chosen randomly according to a probability measure µ ≪ λ, then r ∈ R(H) with probability one.

B.2 Characterization of the bias optimal policy

Proposition 3. Let M ∈ H a DMDP. A policy π ∈ Π is bias optimal if, and only if g π (x) does not depend on x ∈ S and ∀(x, a) / ∈ π, r(x, a) -g π (x) + P (x, a)h π < h π (x).

In particular, π * M is the unique policy with unique terminal cycle such that this equation holds. Moreover, a DMDP satisfies H1 and H2 if, and only if there is a policy satisfying this equation with unique terminal cycle.

Proof. The proof is done in several steps.

Characterization of bias optimality on H. Let us assume M ∈ H and let π ∈ Π with g π (x) independent of x ∈ S and such that

∀(x, a) ∈ π * , r(x, a) -g π (x) + h π (y) < h π (x) (14)
where y := s(x, a).

For (x, a) ∈ Z, define ∆ π (x, a) := h π (x) -[r(x, a) -g π (x) + h π (y)]
. By definition of h π (x), we have ∆ π (x, a) = 0 for all (x, a) ∈ π and ∆ π (x, a) > 0 everywhere else. By assumption, we may write g π instead of

g π (x). Let (u 0 , a 1 , u 1 , a 2 , u 2 , . . . , a k , u k ) be a path in G. One checks by induction on k ≥ 1 that k-1 i=0 [r(u i , a i ) -g π ] = h π (u 0 ) -h π (u k ) - k-1 i=0 ∆ π (u i , a i ).
Choose (u 0 , a 0 , . . . , u c-1 , a c-1 , u c ) any cycle C of G i.e. u 0 = u c . From the formula above follows

- c-1 i=0 ∆ π (u i , u i+1 ) = c-1 i=0 [r(u i , u i+1 ) -g π ] = |C|[g(C) -g π ].
As all ∆ π (x, a) are non-negative, applying the formula with C = C * the optimal cycle of M , we get that g π = g * . In particular, π has C * for unique terminal cycle so π ∈ Π * -1 (M ). To show that π ∈ Π * 0 (M ), compare the bias of π to the one of the optimal policy π * . Let x ∈ S and k minimal such that x k := π * k (x) ∈ C * . We have

h * (x 0 ) -h * (x k ) = k-1 i=0 [r(x i , a i ) -g * ] = h π (x 0 ) -h π (x k ) - k-1 i=0 ∆ π (x i , a i ) ≤ h π (x 0 ) -h π (x k ).
But x k belongs to C * , thus starting from x k , the iterates of π and π * coincide. Thus

h π (x k ) = h * (x k ). Whence h * (x 0 ) ≤ h π (x 0 ). Accordingly, π ∈ Π * 0 (M ).
Characterization of H. If M ∈ H, we know that the bias optimal policy has constant gain vector and is such that ( 14) holds. The proof of the converse statement is very similar to the previous argument. So, conversely, assume that there exists π with unique terminal cycle satisfying ( 14). The formula

∀(x, a) ∈ π * , r(x, a) -g π (x) + h π (y) < h π (x)
is still valid. Thus for (u 0 , a 0 , . . . , u c-1 , a c-1 , u c ) any cycle C, we have

|C|[g(C) -g π ] = - c-1 i=0 ∆ π (u i , a i ). Any cycle C ̸ = C π is such that c-1 i=0 ∆ π (u i , a i ) > 0, i.e., g(C) < g π = g(C π
). This means that the optimal cycle is unique, so M satisfies H1. Finally, to show that π is the unique bias optimal policy, consider π ′ ∈ Π * -1 (M ) different from π and show that there exists x ∈ S such that h π ′ (x) < h π (x). There exists (x, a) ∈ π ′ \ π, so that ∆ π (x, a) > 0. Let k minimal such that x k := π ′k (x) ∈ C * . Then,

h π ′ (x 0 ) -h π ′ (x k ) = k-1 i=0 [r(x i , a i ) -g π ] = h π (x 0 ) -h π (x k ) - k-1 i=0 ∆ π (x i , a i ) < h π (x 0 ) -h π (x k ). But since x k ∈ C * = C π = C π ′ , h π (x k ) = h π ′ (x k ). Thus h π ′ (x 0 ) < h π (x 0 ).

C APPENDIX: ANALYSIS OF LSTS

To settle notations, the noisy perturbation vector of rt is denoted

r t := (1 -1 t )r t + 1 t u t ( 15
)
where

u t ∼ U([-1, 1] Z ).
A comment first: in order to have a well-defined scheme, one have to check that ω • (the sampling parameters) are well-defined other time. 4 Let R(H) := M ∈H r M the set of mean reward vectors of elements of H. Proposition 2 shows that for all r M and ϵ > 0,

P {r M + ϵu t ∈ R(H)} = 1.
Now, u t and rt are independent, thus for all t,

P (1 -1 t )r t + 1 t u t ∈ R(H) = 1.
Thanks to that perturbation, exploration coefficients are almost surely well-defined, since:

P {∃t, r t / ∈ R(H)} ≤ t P { r t / ∈ R(H)} = 0.

C.1 Time uniform confidence sets

Recall that the confidence sets are of the form

M δ t := Mt + Λ δ t
where Λ δ t is the product of confidence intervals

Λ δ t := z∈Z (-ϵ δ (N t (z), t), ϵ δ (N t (z), t))
where ϵ δ (N t (z), t) is given as per Equation ( 9), namely

ϵ δ (s, t) := 2σ 2 log( 4mt 3 δ ) s 1/2
As claimed in the main body of this paper, this construction provides time uniform confidence sets.

Proposition 4. For all I, t P M,I {M / ∈ M δ t } ≤ δ.

Proof of Proposition 4. Fix z ∈ Z. Let V 1 , V 2 , . . . i.i.d. random variables of distribution q(z). By Hoeffding's Lemma, for all s, t ≥ 1, we have

P 1 s s i=1 V i -r(z) > ϵ δ (s, t) ≤ 2 exp -s 2σ 2 2σ 2 log(4mt 3 /δ) s = δ 2mt 3 .
Thus for all t ≥ 1, by union bound,

P M,I {|r t (z) -r(z)| > ϵ δ (N t (z), t)} ≤ t-1 s=0 P M,I |r t (z) -r(z)| > ϵ δ (N t (z), t) and N t (z) = s ≤ t • δ 2mt 3 = δ 2mt 2 .
Finally, we get that M ∈ M δ t uniformly in time in the following way:

P M ∃t, M / ∈ M δ t ≤ t P M M / ∈ M δ t ≤ δ 2 ∞ t=1 1 t 2 < δ.

C.2 The D-tracking rule

The D-tracking scheme heavily relies on the D-tracking rule in the style of [START_REF] Garivier | Optimal Best Arm Identification with Fixed Confidence[END_REF]; Marjani et al. (2021) -just like the name suggested.

Lemma 4 (D-tracking rule). The D-tracking rule ensures:

1. For all z ∈ Z, N t (z) ≥ ( √ t -m/2) + -1;
2. For all ϵ > 0, ∃t ϵ > 0, s.t. ∀t 0 > 0:

sup t≥t0 ∥ω rt -ω r ∥ ∞ ≤ ϵ =⇒ sup t≥max(t0,tϵ) N(t) t -ω r ∞ ≤ 2(m -1)ϵ
About the proof. This result has nothing to do with DMDPs, and is rather a result about "sequences that concentrates" (Garivier and Kaufmann, 2016, p.22). Apply Lemma 17 from [START_REF] Garivier | Optimal Best Arm Identification with Fixed Confidence[END_REF] with g(k

) := ( √ k - m/2) + .
The choice to rely on D-tracking rule is arbitrary. Many other tracking methods exist in the literature; That many that would also work here. As these are not the main focus, such discussions are excluded from this paper for the sake of conciseness.

C.3 Proof of Proposition 5: The D-tracking scheme is δ-PC The δ-probably correctedness is proved using the continuity of B(M ) together with the Π * ∞ -constant property. In more details, B(M ) ̸ = ∅ and continuity ensures finite stopping time with high probability, while the Π * ∞ -constant property guarantees that the recommended policy is correct.

Proposition 5 (Correctedness). Every D-tracking scheme is δ-probably correct on DMDPs in H.

Proof of Proposition 5. It follows from Lemma 4 that for all z and t, N t (z) ≥ √ t -m. Therefore, for a fixed δ > 0, the confidence width ϵ δ (N t (z), t) → 0 a.s. when t → ∞. In particular, for all η > 0, there exists t η > 0 a constant such that for all t > t η , Λ δ t ⊆ z [-η, η]. Accordingly, conditioned on the event

E := ∀t, M ∈ M δ t , we have ∀η > 0, ∀t > t η , d(M, Mt ) ≤ 2η.
So, by continuity of B(•), there exists t B such that on E, for t > t B , B(M ) and B( Mt ) look alike in that:

ℓ B( Mt) ≥ 1 2 ℓ B(M ) > 0.
Set η := 1 8 min z ℓ B(M ) (z) > 0. Let t ′ = max(t B , t η ). On E, for all t > t ′ , we have:

d( Mt , M ) < 1 2 ℓ B( Mt) (z) ( * ) Λ δ t ⊆ z [-η, η] ⊆ z [-1 2 ℓ B( Mt) (z), 1 2 ℓ B( Mt) (z)] ( * * )
The combination of ( * ) and ( * * ) yields that on E, for t > t ′ , we have M δ t ⊆ B( Mt ). So τ δ is upper bounded by t ′ on E; hence finite. By Proposition 4,

P {τ δ < ∞} ≥ P (E ∩ {τ δ < ∞}) = P(E) ≥ 1 -δ.
Finally, we show that under {τ δ < ∞} the algorithm returns an optimal policy with probability δ. By construction of the set of plausible MDPs, the probability that for all t, M δ t contains M , is at least

1 -δ. Also, if M δ t ∈ B( Mt ), then for all M ∈ M δ t , we have Π * ∞ ( M ) = Π * ∞ ( Mt ). All together, P τ δ < ∞, π * ( Mτ δ ) / ∈ Π * ∞ (M ) ≤ P τ δ < ∞, M / ∈ B( Mτ δ ) ≤ t≥1 P τ δ = t, M / ∈ M δ t ≤ t≥1 P M / ∈ M δ t ≤ δ.
C.4 Proof of Proposition 6: Performances of the D-tracking scheme

We switch the focus to the proof of:

Proposition 6 (Performances). A D-tracking scheme stops on M ∈ H a.s.; Also,

lim inf δ→0 E M [τ δ ] log(1/δ) ≥ z 2σ 2 ℓ B(M ) (z) 2 . Moreover, if exploration parameters are ω ∝ ℓ -2 B(•) , then lim δ→0 E M [τ δ ] log(1/δ) = z 2σ 2 ℓ B(M ) (z) 2 .
The performances of the D-tracking schemes described by Proposition 6 can, in fact, be described in much more precision as given by the result below.

Lemma 5 (Performances of D-tracking schemes). Let M ∈ H with mean reward vector r. Then

lim δ→0 E M,I [τ δ ] log(1/δ) = max z 2σ 2 ω r (z)ℓ B(r) (z) 2 L r (z) 2 .
The right-hand term is proved to be an upper bound and a lower bound of the asymptotic expected sampling complexity growth rate separately.

C.4.1 The upper bound

The main steps of the upper-bound part of the proof of Lemma 5 are summarized below.

• Step 1: Properties of the D-tracking rule, see Lemma 4;

• Step 2: Quantify on how much local gaps L z (•), boxes B(•) and exploration coefficients ω • w.r.t. r, rt , r t all are close to each over in the run;

• Step 3: Relate the actual visit counts N t to t • ω r ;

• Step 4: Pseudo-inverse of ϵ δ (κ • t, t) in t, in order to quantify how small time needs to be for the confidence set to collapse;

• Step 5: Steps 2-3 define a high probability good event, on which τ δ can be accurately approximated thanks to Step 4.

The conclusion follows quickly from step 5. As step 1 is done already (see Lemma 4), we skip to step 2.

By continuity of L z (-) at r ∈ R(H), for all ϵ > 0, there exists α(ϵ) > 0 such that for ∥r -r ′ ∥ ∞ < α(ϵ), we have

max z |L r ′ (z) -L r (z)| < ϵ (16) max z |ω r ′ (z) -ω r (z)| < min z ′ ∈Z ω z ′ (r) 2(m-1) ϵ (17) max z |ℓ B(r ′ ) (z) -ℓ B(r) (z)| < ϵ. ( 18
)
The set of such r ′ is denoted B(r, α(ϵ)). Introduce

F ϵ (T ) := T t=T 1/4 {r t , r t ∈ B(r, α(ϵ))} .
We show that this event hold with high probability.

Lemma 6 (Step 2). There exist constants B ϵ , C ϵ > 0 such that

∀T > 0, P M,I F ϵ (T ) ∁ ≤ B ϵ T exp(-C ϵ T 1/8 ).
Proof of Lemma 6. By definition of r t (z), for all z ∈ Z, r t (z) -r(z) unfolds as

1 -1 t [r t (z) -r(z)] + 1 t [u t (z) -r(z)] .
There exists A ϵ > 0 such that if t ≥ A ϵ then for all z ∈ Z and z ∈

[0, 1], | 1 t (u t (z) -r(z))| ≤ 1 2 α(ϵ).
In addition, we know that t ≥ N t (z) ≥ √ t -m, so for t ≥ A ϵ and z ∈ Z,

P {|r t (z) -r(z)| > α(ϵ) and | r t (z) -r(z)| > α(ϵ)} ≤ P |r t (z) -r(z)| > 1 2 α(ϵ), N z (t) ≥ √ t -m ≤ 2 t s= √ t-m exp - sα(ϵ) 2 8σ 2 ≤ 2 exp -α(ϵ) 2 ( √ t -m)/8σ 2 1 -exp(-α(ϵ) 2 /8σ 2 )
.

So by union bound and Hoeffding's Lemma,

P F ϵ (T ) ∁ = P    z∈Z t∈[T 1/4 ,T ] |r t (z) -r(z)| > α(ϵ)    ≤ m |T 1/4 -A ϵ | + + 2 T t=T 1/4 e -α(ϵ) 2 ( √ t-m)/8σ 2 1 -e -α(ϵ) 2 /8σ 2 ≤ m|T 1/4 -A ϵ | + 2me mα(ϵ) 2 /8σ 2 1 -e -α(ϵ) 2 /8σ 2 • T • e -α(ϵ) 2 T 1/8 /8σ 2 .
Last but not least, |T 1/4 -A ϵ | + = 0 for T ≥ A 4 ϵ , so m|T 1/4 -A ϵ | is negligible in comparison to the right term when T goes to infinity.

On F ϵ (T ), the actual ratio of visits is closed to ω r up to ϵ min z ω r (z) when T is high enough. It puts the informal statement N t = tω r + o(t) in a formal way.

Lemma 7 (Step 3). For all ϵ > 0, there exists T ϵ > 0 such that for all T ≥ 0, on F ϵ (T ),

∀t ∈ [max(T 1/4 , T ϵ ), T ], N t t -ω r ∞ ≤ ϵ min z∈Z ω r (z).
Proof. On F ϵ (T ), for all t ≥ T 1/4 , we have ∥ω rt -ω r ∥ ∞ ≤ ϵ min ω r (x, a)/2(m -1) by construction, see Equation ( 17). So, from Lemma 4 (2), for t ≥ max(T 1/4 , t ϵ ),

N (t) t -ω r ∞ ≤ ϵ min z∈Z ω r (z).
Set T ϵ := t ϵ .

The next result provides a way to invert ϵ δ (•). This will give information on how fast the confidence set shrink. Recall that ϵ δ (s, t) := ( 2σ 2 s log( 4mt 3 δ )) 1/2 is the precision that the algorithm assumes to have on a reward with s samples at time t. Lemma 8 (Step 4). Let α, κ > 0. For all β < 1 2 , there exists a constant D α,β,κ > 0, independent of δ, such that if

t ≥ 2σ 2 log(1/δ) κ(1 -2β)α 2 + D α,β,κ (19)
then for all s ≥ κ • t, ϵ δ (s, t) ≤ α.
Proof of Lemma 8. Assume that κ • t ≤ s. We are searching for a sufficient condition on t such that ϵ δ (s, t) ≤ α. Observe that it boils down to

log(1/δ) + log(4m) + 3 log t ≤ κα 2 2σ 2 • t
Using the global upper bound log t ≤ √ t, we get the three sufficient conditions

     log(1/δ) ≤ (1 -2β) κα 2 2σ 2 • t log(4m) ≤ β κα 2 2σ 2 • t 3 √ t ≤ β κα 2 2σ 2 • t.
Solving in t and using max {a, b, c} ≤ a + b + c for a, b, c ≥ 0, the condition above reduces to

2σ 2 log(1/δ) κ(1 -2β)α 2 + 2σ 2 log(4m) βκα 2 + 36σ 4 β 2 κ 2 α 4 ≤ t
where we identify D α,β,κ := (βκα 2 ) -1 2σ 2 log(4m) + 36σ 4 (β 2 κ 2 α 4 ) -1 .

The last lemma basically bounds τ δ on F ϵ (T ) provided by T is large enough. It is the last major step of the proof. Lemma 9 (Step 5). For all ϵ > 0, there exist constants H ϵ , D ϵ ≥ 0 such that denoting

T 0 (ϵ, δ) := D ϵ + max z∈Z 2σ 2 log(1/δ) (1 -ϵ) 2 ω r (z)(ℓ B(r) (z) -ϵ) 2 (L r (z) -ϵ) 2 ,
then for all T ≥ max(H ϵ , (1 + ϵ)T 0 (δ, ϵ)), then on F ϵ (T ):

τ δ ≤ T 1/4 + T 0 (ϵ, δ) ≤ T
Proof of Lemma 9. By definition of the stopping time, on F ϵ (T ), if for all z ∈ Z, we have

ϵ δ (N x,a (t), t) ≤ (ℓ B(r) (z) -ϵ)(L r (z) -ϵ),
then ϵ δ (N t (z), t) ≤ ℓ rt (z)L z (r t ), so the scheme stops. Introduce the following random time:

T upper (δ, T ) := inf{t ∈ [max(T 1/4 , T ϵ ), T ] | ∀z ∈ Z, ϵ δ (N t (z), t) ≤ (ℓ B(r) (z) -ϵ)(L r (z) -ϵ)}
with the convention that T upper (δ, T ) = +∞ if the infimum goes over an empty set. From the previous discussion follows F ϵ (T ) ⊆ {τ δ ≤ T upper (δ, T )}. Namely, if F ϵ (T ) holds then T upper (δ, T ) is an upper bound of τ δ . From Lemma 7, on F ϵ (T ) and for t ∈ [max(T 1/4 , T ϵ ), T ], we have

∀z ∈ Z, N t (z) t -ω r (z) ≥ -ω r (z)ϵ Thus N t (z) ≥ (1 -ϵ)ω r (z)t.
We provide an upper bound of T upper (δ, T ) by applying Lemma 8 with

κ z := (1 -ϵ)ω r (z), α z := (ℓ B(r) (z) -ϵ)(L r (z) -ϵ) and β = ϵ/2. Define T 0 (ϵ, δ) := T ϵ + max z∈Z 2σ 2 (1 -ϵ) -2 log(1/δ) ω r (z)(ℓ B(r) (z) -ϵ) 2 (L r (z) -ϵ) 2 + D αz, ϵ 2 ,κz .
When T ≥ T 1/4 + T 0 (ϵ, δ), we get T upper (δ, T ) ≤ T 0 (ϵ, δ) + T 1/4 on F ϵ (T ).

To conclude the proof, observe that the condition

"T ≥ T 1/4 + T 0 (ϵ, δ) ′′ is satisfied as soon as T ≥ max((1 + 1 ϵ ) 4/3 , (1 + ϵ)T 0 (ϵ, δ)). Indeed, if this is the case, then T (1 -1 1+ϵ ) ≥ T 1/4 , so T 0 (ϵ, δ) + T 1/4 ≤ 1 1+ϵ T + T 1/4 ≤ T ( 1 1+ϵ + 1 -1 1+ϵ ) = T.
Set D ϵ := T ϵ + max z∈Z D αz,ϵ/2,κz and H ϵ := (1 + 1 ϵ ) 4/3 . This proves Lemma 9.

The final step. Following Lemma 9 (step 5), if

T ≥ max(H ϵ , (1 + ϵ)T 0 (δ, ϵ)), then F ϵ (T ) ⊆ {τ δ ≤ T }. So, P M,I {τ δ > T } ≤ P M,I F ϵ (T ) ∁ ≤ B ϵ T exp(-C ϵ T 1/8 ).
Then, we compute the expected sampling complexity has:

E M,I [τ δ ] = ∞ T =1 P M,I {τ δ ≥ T } ≤   Hϵ+(1+ϵ)T0(ϵ,δ) T =1 P M,I {τ δ ≥ T, F ϵ (T )}   + ∞ T =1 P M,I F ϵ (t) ∁ ≤ H ϵ + (1 + ϵ)T 0 (ϵ, δ) + ∞ T =1 B ϵ T exp(-C ϵ T 1/8 ).
Divide by log(1/δ) and take the supremum limit. Expanding T 0 (ϵ, δ), we obtain:

lim sup δ→0 E M,I [τ δ ] log(1/δ) ≤ max z∈Z (1 + ϵ)2σ 2 (1 -ϵ) 2 ω r (z)(ℓ B(r) (z) -ϵ) 2 (L r (z) -ϵ) 2 .
This holds for all ϵ > 0 sufficiently small, so letting ϵ goes to 0 yields

lim sup δ→0 E M,I [τ δ ] log(1/δ) ≤ max z∈Z 2σ 2 ω r (z)ℓ B(r) (z) 2 L r (z) 2 . (20)
Finally, as kl(δ, 1 -δ) ∼ log(1/δ) when δ → 0, log(1/δ) can be changed to kl(δ, 1 -δ) in Equation ( 20).

C.4.2 The lower bound

Equation ( 20) is seemingly an upper bound. This is in fact an equality. The proof of the reverse equality is mainly similar and in particular, it shares the technical aspect of the upper bound's proof. Details are spared; we focus on the main idea. We rely an additional crucial property: specifically that when the targeted confidence is high, the probability that the algorithm stops early is small. More precisely: Lemma 10. Consider a D-tracking scheme I and DMDP M ∈ H. For all T, η > 0, there exists δ T,η > 0 such that if δ < δ T,η , then P M,I {τ δ < T } < η.

Proof. Let T, η > 0.

Denote ϵ t := ϵ δ ( √ t -m, t)
For δ < η, the event

E := {∀z, ∀t ≥ m, ϵ δ (N t (z), t) < ϵ t }
is almost sure by Lemma 4. Let U(M, ϵ t ) the closed ball of M centered at M of radius ϵ t . By Hoeffding's Lemma (refer to the proof of Proposition 4), if δ < η, we get

P ∀t, Mt ∈ U(M, ϵ t ) ≥ 1 -P ∃t, Mt / ∈ U(M, ϵ t ) ≥ 1 -P {∃t, ∃z, |r t (z) -r(z)| > ϵ t } ≥ 1 -δ ≥ 1 -η.
The sequence of sets given by U(M, ϵ t ) is compact and non-increasing. The quantity

ℓ η := sup M ′ ∈U (M,ϵt) sup z∈Z ℓ B(M ′ ) (z)
is, by continuity of the family and compacity of U(M, ϵ 1 ), finite. Let δ η,T ∈ (0, η) such that for all δ < δ η,T , ϵ δ (T, 1) > ℓ η .

On the event E ′ := {∀t, Mt ∈ Ū(M, ϵ t )} and for δ < δ η,T , we are guaranteed that for t < T , M δ t ̸ ⊆ B( Mt ); Indeed, for t < T ,

P M δ t ⊆ B( Mt ) | E ′ ≤ P ∃z, ϵ δ (N t (z), t) ≤ ℓ B( Mt) (z) | E ′ ≤ P {∃z, ϵ δ (N t (z), t) ≤ ℓ η } ≤ P {∃z, ϵ δ (T, 1) ≤ ℓ η } = 0.
Accordingly, {τ δ > T } ⊇ E ′ for δ < δ η,T . So, for such δ,

P {τ δ > T } ≥ P(E ′ ) ≥ 1 -η.
With that in mind, the general idea to prove the lower bound

lim inf δ→0 E M,I [τ δ ] log(1/δ) ≥ max z∈Z 2σ 2 ω r (z)ℓ B(r) (z) 2 L r (z) 2 (21)
is the following: choose T such that once t > T , B( Mt ) and B(M ) are very similar (in the same fashion as F ϵ (T ) in the proof of the upper bound). Choose η > 0. Then with confidence parameter δ < δ T,η , the event E ′ := {τ δ > T } holds with probability at least 1 -η. On that event, with a similar analysis than the one of the upper bound, show that most of the expected sample complexity is waiting for Λ δ t to shrink, so that on E ′ ,

τ δ < T ′ =⇒ M δ t ⊆ B ′
where B ′ is a box that very much resembles B(M ). Specifically, with the same computations as in Appendix C.4, we find that under {τ δ > T }, τ δ is of order

max z∈Z 2σ 2 ω r (z)ℓ B(r) (z) 2 L r (z) 2 • log(1/δ).
Since for δ < δ T,η , {τ δ > T } holds with probability at least 1 -η, we get:

lim inf δ→0 E M,I [τ δ ] log(1/δ) ≥ (1 -η) max z∈Z 2σ 2 ω r (z)ℓ B(r) (z) 2 L r (z) 2 .
Make η go to 0 and conclude that

lim inf δ→0 E M,I [τ δ ] log(1/δ) ≥ max z∈Z 2σ 2 ω r (z)ℓ B(r) (z) 2 L r (z) 2 . (22)
C.5 Proof of Proposition 6: Optimal exploration coefficients

On our way to prove Proposition 6, what is left is to compute the optimal ω for a given family B(•). Fix r ∈ R m . We wish to solve the following minimization problem:

min ω max z∈Z 1 ω z α z s.t. z ω z = 1.
where

α z := ℓ B(r) (z) 2 L r (z) 2 > 0. This problem is equivalent to min ω,t t s.t. z ω z -1 = 0 ∀z, 1 ωzαz -t ≤ 0
The Lagrangian of this convex optimization problem is:

L(ω, t; µ, λ) := t + z µ z 1 ω z α z -t + λ z ω z -1 .
• Case (x, a) / ∈ π * . Then, both the gain and the bias are unchanged. The only non-trivial condition from ( 23) is given for (y, b) = (x, a). Subsequently,

Π * 0 (r + dr) = Π * 0 (r) ⇐⇒ α < ∆ M (x, a)
Accordingly, L M (x, a) = ∆ M (x, a).

• Case (x, a) ∈ π \ C. For the same reason, g π u (r ′ ) = g π u (r) for all u ∈ S. For the bias, from Lemma 2, we have

h π u (dr) = 1 u⇝ * x α.
L M (z) = min (y,b) / ∈π ∆ M (y, b) 1 s(y,b)⇝ * x -1 y⇝ * x .
• Case (u, v) ∈ C. This time, both the gain and the bias will be subject to variations. By Lemma 1, for all u ∈ S,

g π u (dr) = α|C| -1 .
For the bias, Lemma 2 provides

h π u (dr) = α 1 -|C|+1 2|C| -τu(x)

|C|

Injecting those expressions into ( 23 This settles the correspondence between L M (x, a) and ∆ M (x, a) on H. These quantities are also used to design Π ∞constant familys, see Proposition 9 that we restate and prove below.

Proposition 9. Let ρ : H → R m + a continuous function. The family B ρ : H → Γ given by

M + z∈Z (-ρ M (z)L M (z), ρ M (z)L M (z)) is a continuous family. If in addition, a) ρ M (z) > 0 for all z ∈ Z; and b) ∀M , ∀π ∈ Π, z∈π∪π * M ρ M (z) ≤ 1, then B ρ is Π * ∞ -constant
and is never empty.

Proof. We show the equivalent following statement: Assume that ρ : H → R m + satisfies the assumptions a) and b) of Proposition 9. Let M ∈ H with mean reward vector r. Let M ′ ∈ M with mean reward vector r ′ such that:

∀z ∈ Z, |r ′ (z) -r(z)| < ρ M (z)L M (z). Then M ′ ∈ H and Π * ∞ (M ) = Π * ∞ (M ′ ).
For π ∈ Π and x ∈ S, the gain g π (x) and the bias h π (x) are linear functions of the mean reward vector r that we shall write g π x (r) and h π x (r) respectively. Let π * ∈ Π * 0 (r) and π ̸ = π * . We show that for all x ∈ S, g π * x (r ′ ) ≥ g π x (r ′ ); and, if there is equality for all x in the preceding equations, that h π * x (r ′ ) > h π x (r ′ ) for at least one x. Then π * ∈ Π * 0 (r ′ ) will follow by definition of bias optimality and by cardinality, Π * 0 (r ′ ) = {π * } will hold. Accordingly, by Proposition 3, we will get

M ′ ∈ H with Π * ∞ (M ′ ) = Π * ∞ (M ).
Let x ∈ S. Denote dr = r ′ -r. We know that for all z ∈ Z, | dr(z)| < ρ M (z)L M (z), so there exists α(z) ∈ (-1, 1) such that dr(z) = α(z)ρ M (z)L M (z).

We have dr = z∈Z dr(z)e z . Let C ̸ = C * a cycle which is different from the terminal cycle of the optimal policy. Because M satisfies H1, g C (r) < g C * (r). Both g C and g C * are linear functions of r, so

g C * (r ′ ) -g C (r ′ ) = [g C * (r) -g C (r)] + [g C * (dr) -g C (dr)]
The quantities g C * (•) and g C (•) only depend on the coordinates z ∈ C ∪ C * . Because g C * (r) -g C (r) ≥ 0 and by assumption b), z∈π∪π * ρ M (z) ≤ 1, one can factorize the following way (L z and ρ z are shorthands for L M (z) and ρ M (z)):

g C * (r ′ ) -g C (r ′ ) b) ≥ z∈C∪C * ρ z g C * (r) -g C (r) + g C * (α z L z e z ) -g C (α z L z e z ) = z∈C∪C * ρ z (g C * (r z + α z L z e z ) -g C (r z + α z L z e z )) .
As |α z L z | < L z , by definition of L z = L M (z), all terms in the sum above are non-negative -in fact, these are positive. It means that g C * (r ′ ) > g C (r ′ ). Accordingly, a policy π that doesn't have terminal cycle C * is not gain-optimal for M ′ . Therefore, unless π

∈ Π * -1 (M ), π / ∈ Π * ∞ (M ′ ) * .
So, what if π ∈ Π * -1 (M )? It then has the same terminal cycle than π * , and we can do the same computation for h π * x (r ′ )h π

x (r ′ ), and find that it has to be positive again unless the iterate of π and π * coincide from x. But for at least one x, they do not, since π ̸ = π * .

In the end, π * appears to be the only bias optimal policy of M ′ and its terminal cycle is unique. From Proposition 3 follows that

M ′ ∈ H. Overall, M ′ ∈ H and Π * ∞ (M ) = Π * ∞ (M ′ ).

C.7 Details for LSTS-imp

This section provides details for the proof of Proposition 10, Proposition 11 and Theorem 3. Recall that LSTS-imp starts by improving on the ρ that are solution of the following optimization problem:

min ρ z∈Z 1 ρ M (z) 2 L M (z) 2 s.t. z∈Z ρ M (z) ≤ 1. (11)
Proposition 10. The solution of Eq. ( 11) is ρ M ∝ L -2/3 .

Proof. The DMDP M is fixed, so write ρ z and L z instead of ρ M (z) and L M (z). The Lagrangian of the optimization problem is

L(ρ; µ) := z 1 ρ 2 z L 2 z + µ z ρ z -1 .
The KKT conditions give:

∂ ρz : 2 ρ 3 z L 2 z = µ C.S. : z ρ z = 1.
In particular, we see that

ρ 3 z ∝ L -2 z , hence ρ z ∝ L -2/3 z
. Because ρ ∈ ∆ m , this uniquely determines ρ.

To paraphrase the main document, LSTS-imp is build from ρ ∝ L -2/3 with an additional scaling. Specifically, denote simply ρ the element of ∆ m such that ρ ∝ L -2/3 . This element is pullbacked to an approximate solution of Equation ( 10) by picking the largest possible α ≥ 1 such that ∀π ∈ Π,

z∈π∪π * αρ(z) ≤ 1. It is equivalent to ∀π ∈ Π, α -1 ≥ z∈π∪π * ρ(z).
We deduce that α is

α = max π∈Π z∈π∪π * ρ(z) -1
.

Theorem 3 (LSTS-imp). Let ρ ∝ L -2/3 . Let α be given by Equation (12). The coefficients ρ ⋆ := αρ satisfy the conditions a) and b) from Proposition 9. The LSTS method with such ρ ⋆ is denoted LSTS-imp (standing for improved LSTS) and achieves:

lim δ→0 E M [τ δ ] log(1/δ) ≤ 8σ 2 n 4/3 m 2/3 z 1 L M (z) 2 .
When rewards are Gaussian with standard deviations σ, LSTS-imp is 8n 4/3 m 2/3 -asymptotically optimal.

There isn't much more to say that the provided sketch of the proof from the main body.

Proof. We have

max π∈Π z∈π∪π * ρ(z) ≤ max π∈Π x∈S (ρ(x, π(x)) + ρ(x, π * (x))) ≤ x∈S 2 max a∈Ax ρ(x, a).
We get the claimed:

α ≥ 2 x max a ρ M (z) -1
Recall that ρ ∝ L -2/3 then apply Theorem 2. Simple algebra leads to:

lim δ→0 E M [τ δ ] log(1/δ) ≤ 8σ 2 z L M (z) -2/3 x max a L M (x, a) -2/3 2
The function t ≥ 0 → t 1/3 is increasing, so max a L M (x, a) -2/3 = (max a L M (x, a) -2 ) 1/3 . Bound both terms with Hölder's inequality with parameters (3, 3 2 ):

lim δ→0 E M [τ δ ] log(1/δ) ≤ 8σ 2 m 2/3 ∥L -1 ∥ 2/3 2   n 2/3 x max a L -2
x,a

1/3   2
Bounding max a by a yields the result.

Finally, we prove the generalization of the method used in Example 3.

Proposition 11. Assume M ∈ H have sub-Gaussian rewards with standard deviation σ > 0. Assume that there exist ϵ > 0 together with a family of distinct state-action pairs

(z i ) k i=1 such that z∈Z L M (z) -2 ≤ (1 + ϵ) k i=1 L M (z i ) -2 .
Thus, if rewards are Gaussian with standard deviations σ, LSTS-imp is 8(k 2 + ϵm 2 )-asymptotically optimal.

Proof. We show that if (a i ) i≤m is a family of non-negative coefficients such that m i=1

a i ≤ (1 + ϵ) k j=1 a j , then   m j=1 a 1/3 j   3 ≤ 4(k 2 + ϵm 2 ) m i=1 a i .
Enumerating Z as (z i ) m i=1 in the right order, with m := |Z| and a i = L M (z i ) -2 , we will get the result. By Hölder's inequality,

m i=1 a 1/3 i = k i=1 a 1/3 i + m j=k+1 a 1/3 j ≤ k 2/3 k i=1 a i 1/3 + m j=k+1 a 1/3 i . Using that m j=k+1 a j ≤ ϵ k i=1 a i together with Hölder's inequality gives m j=k+1 a 1/3 j ≤ (m -k) 2/3   m j=k+1 a j   1/3 ≤ (m -k) 2/3 ϵ 1/3 k i=1 a i 1/3
. By merging the two equations together, we get

m i=1 a 1/3 i 3 ≤ k 2/3 + ϵ 1/3 (m -k) 2/3 3 m i=1 a i .
Again, for x, y ≥ 0, by Hölder's inequality,

a 1/3 + b 1/3 ≤ 4 1/3 (a + b) 1/3 . Applied to a := k 2 and b := ϵ(m -k) 2 , it provides m i=1 a 1/3 i 3 ≤ 4 k 2 + ϵ(m -k) 2 m i=1 a i ≤ 4 k 2 + ϵm 2 m i=1 a i .
D APPENDIX: LOWER BOUNDS Proposition 7. Let M, M ′ ∈ H two DMDPs with different bias-optimal policies such that q(x, a) and q ′ (x, a) are mutually absolutely continuous for all edges. Every δ-PC algorithm satisfies

z∈Z E M [N τ δ (z)] KL(q(z)∥q ′ (z)) ≥ kl(δ, 1 -δ).
Proof of Proposition 7. The original result of [START_REF] Kaufmann | On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models[END_REF] relies on a change of distributions argument. Recall the definition of

F t+1 := σ(X 1 , A 1 , R 1 , Y 1 , . . . , X t , A t , R t , Y t ).
Assume that q(x, a) and q ′ (x, a) are mutually absolutely continuous, so that we can find a common measure λ x,a on R for which q(x, a) and q ′ (x, a) have the respective densities f x,a and f ′ x,a . Define the log-likelihood of observations up to time t under the execution of an algorithm I as

L t := L t (X 1 , A 1 , R 1 , Y 1 , . . . , X t , A t , R t , Y t ) := z∈Z t i=1 1 Zi=z log f z (R i ) f ′ z (R i )
.

Their proof of Lemma 7 is based on the following Lemma, which generalizes the change of measure argument with almost surely constant stopping time5 to general stopping times.

Lemma 12. Let τ be any almost surely finite stopping time w.r.t. F t . For every event U ∈ F τ (i.e. {τ = t} ∩ U ∈ F t ),

E M ′ ,I [L τ ] ≥ kl(P M,I (U), P M ′ ,I (U)).
This Lemma is a mere restatement of the Lemma 19 from [START_REF] Kaufmann | On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models[END_REF]. Although the later is stated for identification algorithms for multi-armed bandits, the stochastic process underlying to an identification algorithm for a DMDP M with edge space Z, rewards q(x, a) and generative model is the same as to the stochastic process corresponding to a Z-multi-armed bandits with the same rewards. This is thanks to the generative model assumption; The DMDP setting is actually an instance of multi-armed bandits with arms Z -but with a much subtler notion of optimality.6

An application of Wald's Lemma to L τ produces

E M,I [L τ ] := z∈Z E M,I [N z (τ )] KL(q(z)∥q ′ (z)).
To get Lemma 7, apply Lemma 12 with U :

= τ δ < ∞, π I τ δ ̸ = π * M . We have π * M ∈ Π * 0 (M ), π * M / ∈ Π * 0 (M ′ ) and I is δ-PC, so P M,I (U) ≤ δ, and
P M ′ ,I (U) ≥ 1 -δ.
So overall, kl(P M,I (U), P M ′ ,I (U)) ≥ kl(δ, 1 -δ).

Although the lower bound provided by Proposition 7 is very powerful, it isn't tractable in general. Albeit weaker, the edgewise lower bound variant of Proposition 8 is fairly easy to compute in practice.

Proposition 8 (Edgewise Lower Bound). Let M ∈ H with Gaussian rewards of standard deviation σ > 0. For all δ-PC identification algorithm,

E M [τ δ ] kl(δ, 1 -δ) ≥ σ 2 z∈Z 1 L M (z) 2 .
Proof. Let ϵ > 0 and z ∈ Z. There is σ ∈ {±1} such that Π * 0 (r + σ(1 + ϵ)L r (z)e z ) ̸ = Π * 0 (r). Let M ′ the DMDP with Gaussian rewards of standard deviation σ and mean reward vector r ′ := r + σ(1 + ϵ)L r (z)e z . Since H is dense in the whole set of DMDPs and that q

′ → z ′ ∈Z E M,I [N z ′ (τ δ )] KL(q(z ′ )∥q ′ (z ′ ))
is continuous, we may assume that M ′ ∈ H up to an infinitesimal perturbation of r ′ . Then by Lemma 7, we have

z ′ ∈Z E M,I [N z ′ (τ δ )] KL(q(z ′ )∥q ′ (z ′ )) ≥ kl(δ, 1 -δ). By construction, z ′ ∈Z E M,I [N z ′ (τ δ )] KL(q(z ′ )∥q ′ (z ′ )) = E M,I [N z (τ δ )] KL(q(z)∥q ′ (z)). Moreover, KL(q(z)∥q ′ (z)) = (1 + ϵ) 2 L r (z) 2 σ 2 .
Therefore,

E M,I [N z (τ δ )] kl(δ, 1 -δ) ≥ 1 KL(q(z)∥q ′ (z)) = σ 2 (1 + ϵ) 2 L M (z) 2 .
This holds for all ϵ > 0. Letting ϵ go to 0, we obtain the announced lower bound. For the sake of self-containedness, we provide an ad-hoc proof of the termination of HPI-BO.

E APPENDIX: COMPUTATIONS

π ′ t (x) := a ∈ G t x if πt(x) / ∈ G t x πt(x) if πt(x) ∈ G t x (24) 8: if π ′ t = πt then 9: choose for all x ∈ S H-rule π ′ t (x) := a ∈ H t x if πt(x) / ∈ H t x πt(x) if πt(x) ∈ H t x ( 25
Lemma 13. Let (π t ) t≥1 the sequence of policies generated by HPI-BO. For all x ∈ S, g πt (x) is non-decreasing with t and on time-steps such that g πt = g πt+1 , we have ∀x, h πt (x) ≤ h πt+1 (x) with strict inequality for at least one x ∈ S. Made short, using the product order on R S , the pair of vectors (g πt , h πt ) is increasing for the lexicographic order.

Proof. To begin with, because the transition structure of a DMDP is deterministic, we abuse of notations and denote π k (x) the k-th states reached by π starting from x. In particular, π 0 (x) = x and π 1 (x) = s(x, π(x)).

The proof distinguishes two cases : updates of the current policy π t under the G-rule and under the H-rule. Under the G-rule, terminal cycles do not change, but π t (x) may be modified to another a ∈ A x that leads to a better terminal cycle.

Under the H-rule, terminal cycles may change. Specifically, if a new cycle is created, its value is higher than the previous ones ; if no cycle emerges under H-rule, the gain is unchanged and the bias increases at some vertex. The proof of these statements goes by induction on S with respect to the following quantities. For t ≥ 1 and x ∈ S, define k t x := ℓ : π 1 t+1 (π ℓ t+1 (x)) ̸ = π 1 t (π ℓ t+1 (x))

the number, possibly infinite, of successors of x by π t+1 from which π t and π t+1 take different decisions. Define also d t , that is

d t x := inf ℓ ≥ 0 | π ℓ t+1 (x) ∈ C πt+1 x < ∞.
When a non-trivial G-rule is applied, it means there exists (x, a) ∈ Z such that g πt (π 1 t (x)) < g πt (s(x, a)), so that under π t , s(x, a) leads to a better cycle of π t than π t (x). By induction on (k t x , d t x ) for the lexicographic order, we show that ∀x ∈ S, g πt+1 (x) ≥ g πt+1 (x). Moreover, for x ∈ S such that k t x = 1, we have g πt+1 (x) = g πt (π 1 t+1 (x)) > g πt (π 1 t (x)) = g πt (x).

Therefore, the gain increases for the product order on R S .

When a non-trivial H-rule is applied, it means that for all (x, a) ∈ Z, g πt (x) ≥ g πt (s(x, a)). A quick induction shows that if there exists a path from u to v, then g πt (u) ≥ g πt (v). Now, remark that k t x < ∞ if, and only if C πt+1 x is a cycle of π. We start by investigating the case k t x = ∞ where under π t+1 , x converges to a cycle C which is not a cycle of π. Expand C as a sequence of states-actions (u 0 , a 0 , . . . , u c-1 , a c-1 ). For all i ≤ c -1, we have r(u i , a i ) -g πt (u i ) + h πt (u i+1 ) ≥ h πt (u i ) with strict inequality for at least one i. Hence, summing over i,

1 c i=0 r(u i , a i ) + 1 c c i=1 h πt (u i ) > 1 c c-1 i=0 g πt (u i ) + 1 c c-1 i=0 h πt (u i ).
Since all u i are connected, g πt (u i ) does not depend on i. Moreover, the terms involving the bias cancel out. It leaves ∀j ≤ c -1, g πt+1 (u j ) = g(C) > g πt (u j ).

Hence, if k t x = ∞, then C πt+1 x
is not a cycle of π t and g πt+1 (x) > g πt (x).

In the case k t x < ∞, x converges (under π t+1 ) to a cycle of π t and by construction of the H-sets, g πt+1 (x) = g πt (x). We prove by induction over (k t x , d t x ) for the lexicographic order that h πt+1 (x) ≥ h πt (x). For k t x = 0, this is obvious because π t and π t+1 coincide on their successors from x. Assume that k t x > 0. If k t π 1 t+1 (x) < k t x , it means that π 1 t (x) ̸ = π 1 t+1 (x) and r(x, π t+1 (x)) -g πt (x) + h πt (π 1 t+1 (x)) > h πt (x). By induction, h πt (π 1 t+1 (x)) ≥ h πt+1 (π 1 t+1 (x)). Moreover, g πt (x) = g πt+1 (x). In the end,

h πt+1 (x) > h πt (x). (26)
The other possible case is k t π 1 t+1 (x) = k t x . Then, d t π 1 t+1 (x) < d t x and the same argument leads to h πt+1 (x) ≥ h πt (x). Overall, we have h πt+1 (x) ≥ h πt (x) for all x ∈ S such that k t x < ∞. Furthermore, when k t x > 0, the equation (26) enlighten that there exists a successor of x which increases the bias.

To summary, if there exists k t x = ∞, the gain increases under H-rule ; otherwise, all k t x are finite and because π t ̸ = π t+1 , there must exists at least one k t

x > 0 so the bias increases for the product order of R S under H-rule. Corollary 1. HPI-BO terminates in finite time and returns a bias optimal policy. Proof. Let T ∈ [0, +∞] number of time-steps before termination. For each t < T , either the gain or the bias increases, so t ∈ [0, T -1] → π t ∈ Π is an injective map. Because Π is finite, T must be finite. Now, by definition, π T -1 = π T , so that π T satisfies the assertion 3 of Theorem 3. Therefore, π T ∈ Π * ∞ (M ).

E.1.2 Bias optimality via maximal mean cycle

Another approach is to compute the maximal mean weight cycle of G directly, using algorithms such as Karp's maximal mean cycle algorithm (see [START_REF] Karp | A characterization of the minimum cycle mean in a digraph[END_REF]). This optimal cycle is obtained in time O(nm) and once C * is known, we show next that Howard Policy Iteration computes the bias optimal policy in at most n steps.

Proposition 12. On DMDPs satisfying H1, the KMMC+HPI algorithm computes a bias-optimal policy in time O(nm).

Proof. Assume that M satisfies (H1). Require: a DMDP M = (S, A, P, r) satisfying (H1); Ensure: π is bias optimal 1: compute the maximal mean cycle C * using Karp's algorithm; 2: compute a policy π0 with unique terminal cycle C * ; 3: apply HPI-BO starting from π0 to get πt; 4: return πt.

of x to the terminal cycle C * under π t , that is d t x := inf ℓ ≥ 0 | π ℓ t (x) ∈ C * . We claim that after t steps of HPI, for all x ∈ S such that d t x ≤ t, we have (x, π t (x)) ∈ Z * and h πt (x) = h * (x). The proof goes by induction on t. Because C * is unique, the result is obvious for t = 0. Assume that t > 1. We know that the application of the G-rule increases the gain, so π t must be updated according to the H-rule. What is more, the H-rule does not change the terminating cycle. Let x such that d t x < t. By induction, π t-1 achieves optimal bias from x, so from the H-rule, π t-1 (x) = π t (x). Accordingly, π t is bias-optimal from all x at distance less than t of C * . Let x such that d t x = t. Because g πt (y) = g(C * ) for all y ∈ S, we see that π t (x) ∈ argmax a∈Ax r(x, a) + h πt-1 (s(x, a))

By definition, d t y = d t x -1 < t, so h πt-1 (y) = h * (y) and h πt (y) = h * (y). Remark that if π * is a bias-optimal policy, then for all (x, a) / ∈ Z * , we have r(x, a) + h * (s(x, a)) < r(x, π * (x)) + h * (π * (x)) by Theorem 3. Using h πt-1 (s(x, a)) ≤ h * (s(x, a)), we get that for all z ∈ S such that (x, a) / ∈ Z * , r(x, a) + h πt-1 (s(x, a)) < r(x, π t (x)) + h πt-1 (π t (x)).

In particular, (x, π t (x)) ∈ Z * . Let π * ∈ Π * 0 (M ) such that π t (x) = π * (x). Then h * (x) = r(x, π * (x)) -g * (x) + h * (π * (x))

= r(x, π t (x)) -g * (x) + h πt (π t (x)) = h πt (x).

Setting t = n -1, we obtain that ∀x ∈ S, h πt (x) = h * (x). Hence HPI terminates in at most n steps, each step running in time O(m). We end up with a total time complexity O(nm).

E.2 The computation of local suboptimality gaps is O(nm)

From the identities derived by Lemma 11, we are able to compute the local suboptimality gaps efficiently. Because the computation of bias optimal policies can be done in time O(nm) (see the previous section), the computation of local gaps are O(nm) in total.

  Proceedings of the 26 th International Conference on Artificial Intelligence and Statistics (AISTATS) 2023, Valencia, Spain. PMLR: Volume 206. Copyright 2023 by the author(s).

  probability measure under M when iterating I E M,I µ [•] expectation under M when iterating I ∆ M (x, a) Bellman gap of (x, a) for M Equation (7) L M (x, a) local suboptimality of (x, a) for M Definition 5 B(M ) box at M ∈ H Definition 4 ℓ B(M ) (x, a) half-width of box B(M ) at (x, a) Definition 4 ρ M (x, a) family extra parameters Proposition 9 ω M (x, a) exploration coefficients Algorithm 1

  y, b). Proof. Assume that r(y, b) is null everywhere excepted at some coordinate (y, b) ∈ Z, i.e., r = α • e y,b . Let x ∈ S. If (y, b) / ∈ π, then h π x (αe y,b ) = 0 since π never uses the transition. If (y, b) ∈ π \ C π

From ( 23 )

 23 follows that Π * 0 (r + dr) = Π * 0 (r) iff for all (y, b) / ∈ π, α 1 (x,a)=(y,b) + 1 s(y,b)⇝ * x -1 y⇝ * x < ∆ M (y, b).As (x, a) ∈ π, we have 1 (y,b)=(x,a) = 0. With the convention ∆ y,b /0 = +∞, we get

  ), we get that Π * 0 (r + dr) = Π * 0 (r) if, and only if for all (y, b) / ∈ π, α 1 (y,b)=(x,a) + τy(x)-τ s(y,b) (x)-1 |C| < ∆ M (y, b). Again, (x, a) ∈ π so 1 (y,b)=(x,a) = 0. Therefore, L M (z) = min (y,b) / ∈π |C|∆ M (y, b) τ y (x) -τ s(y,b) (x) -1 .

x

  the distance of x to C πt+1 x

  Karp's algorithm has execution time O(nm), and the computation of a policy π 0 with unique terminal cycle C * can be done in O(n + m). Let (π t ) the sequence of policies generated by HPI-BO. We show that HPI-BO runs at most S steps. LetZ * = {(x, a) ∈ Z | ∃π * ∈ Π * 0 (M ), a = π * (x)}. For x ∈ S,set d t x the distance Algorithm 3 Karp Maximal Mean Cycle + Howard Policy Iteration (KMMC+HPI)

Lemma 14 .

 14 Let M ∈ H a DMDP. If the optimal policy π ∈ Π * ∞ (M ) is given, the family (L M (z)) z∈Z can be computed in O(nm) time. Proof. When π ∈ Π * 0 (M ) is given, the computation of g * and h * are done in time O(n) and the Bellman gaps ∆ M (x, a) are deduced in O(1) time each, for a total of O(m) computations. We deduce L M (x, a) for (x, a) / ∈ π immediately and are left to compute the quantities L M (x, a) with (x, a) ∈ π. One starts with a preliminary computation of the relation ⇝ * π and the family of reaching times (τ π u (v)) u,v∈S for all total time O(n 2 ) by backpropagating the values from the terminal cycle of π (that can be computed in O(n)). Finally, for each (x, a) ∈ π, L M (x, a) is computed in O(m) each and there are n of them. This results in an overall O(n 2 + nm) time complexity.

  .1 The computation of bias optimal policies on H is O(nm)E.1.1 Howard's Policy IterationProposition 3 is of interest when it comes to the effective computation of Blackwell optimal policies. This section describes two algorithms to compute them in efficient time. The first one below is an adaptation Howard's Policy Iteration algorithm.

	Algorithm 2 Howard's Policy Iteration for Bias Optimality (HPI-BO)
	Require: a DMDP M = (S, A, P, r) with multigraph G;
	Ensure: return π a bias optimal policy.
	1: t ← 0
	2: initialize π0 : S → A arbitrarily
	3: while πt ̸ = πt-1 do
	4: compute gπ t (x) and hπ t (x) for x ∈ S 5: compute G t x ← argmax a∈Ax [gπ t (s, (x, a))] for x ∈ S	G-sets
	6: compute H t x ← argmax a∈Ax∩G t x [r(x, a) -gπ t (x) + hπ t (s(x, a))] for x ∈ S	H-sets
	7: choose for all x ∈ S	G-rule

E

A cycle is simple if it cannot be written as a union of cycles.

The test " M δ t ⊆ B( Mt)" isn't defined, hence is evaluated to false, when Mt / ∈ H.

Namely, most informational lower bounds come from the famous change of measure argument: for a fixedT ≥ 1, if U is FTmeasurable, then E M [U ] = E M ′ [U • LT ].

Without the generative model assumption, the selection of actions is also subject to constraints (the current state). This case has been covered by the works ofMarjani et al. (2021).

KKT-conditions provide:

Clearly, µ z ̸ = 0 for all z (or λ = 0 and we quickly derive a contradiction), so the complementary slackness condition ( * * * ) implies that t = ω z α z . Injecting that into ( * * ), we get that µ z and ω z are proportional, hence equal, as they both belong to the simplex of R m . Hence ( * * ) produces again:

. Write this element ω B * r . The D-tracking scheme with exploration coefficients ω B * r has asymptotic expected sample complexity:

This ends the proof of the Proposition 6.

C.6 Properties of local suboptimality gaps

This section is dedicated to a review of the most important properties of local suboptimality gaps L M (z) (see Definition 5). We start with the intimate relationship between local suboptimality gaps and Bellman gaps that motivates the denomination "generalized Bellman coefficients".

Lemma 11. Let M ∈ H with mean reward vector r. Let π ∈ Π * 0 (M ) and C its unique terminal cycle seen as a set of transitions {(x, a)} with x recurrent and a = π(x). Denote x t the state visited at time t ≥ 0 under the iterations of π starting from x = x 0 ∈ S. For x, y ∈ S, introduce the reaching time of y from x:

With the convention that ∆ x,a (M )/0 = +∞, for all z = (x, a) ∈ Z:

Proof. So π is the only optimal policy of M . From Theorem 3, M ′ has the same (unique) bias optimal policy if, and only if

). Writing r ′ = r + dr and using linearity, the condition above translates to: for all (y, b) / ∈ π,

Let us assume that r ′ is a unilateral deviation of r at (x, a) ∈ Z, that is to say dr = αe x,a . To express L M (x, a), we expand the variational quantities of ( 23) in the light of Lemma 1 and Lemma 2.