Navigating to the Best Policy in Markov Decision Processes
Year: 2021

Abstract:
We investigate the classical active pure exploration problem in Markov Decision Processes, where the agent sequentially selects actions and, from the resulting system trajectory, aims at identifying the best policy as fast as possible. We propose a problem-dependent lower bound on the average number of steps required before a correct answer can be given with probability at least 1− δ. We further provide the first algorithm with an instance-specific sample complexity in this setting. This algorithm addresses the general case of communicating MDPs; we also propose a variant with a reduced exploration rate (and hence faster convergence) under an additional ergodicity assumption. This work extends previous results relative to the generative setting [MP21], where the agent could at each step query the random outcome of any (state, action) pair. In contrast, we show here how to deal with the navigation constraints, induced by the online setting. Our analysis relies on an ergodic theorem for non-homogeneous Markov chains which we consider of wide interest in the analysis of Markov Decision Processes.

heading: 1 Introduction
text: Somewhat surprisingly, learning in a Markov Decision Process is most often considered under the performance criteria of consistency or regret minimization (see e.g. [SB18, Sze10, LS20] and references therein). Regret minimization (see e.g. [AJO09, FCG10]) is particularly relevant when the rewards accumulated during the learning phase are important. This is however not always the case: for example, when learning a game (whether Go, chess, Atari, or whatever), winning or losing during the learning phase does not really matter. One may intuitively think that sometimes getting into difficulty on purpose so as to observe unheard situations can significantly accelerate the learning process. Another example is the training of robot prototypes in the factory: a reasonably good policy is first searched, regardless of the losses incurred, that can serve as an initialization for a second phase regret-minimization mode that starts when the robot is deployed. It is hence also of great practical importance to study the sample complexity of learning, and to work on strategies that might improve, in this perspective, on regret minimizing algorithms.
In this work, we are interested in the best policy identification (BPI) problem for infinite-horizon discounted MDPs. This framework was introduced by [Fie94] under the name of PAC-RL. In BPI the algorithm explores the MDP until it has gathered enough samples to return an ε-optimal policy with probability at least 1− δ. Crucially, the algorithm halts at a random time step, determined by a
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
stopping rule which guarantees that the probability of returning a wrong answer is less that δ. The optimality of BPI algorithms is measured through their sample complexity, defined as their expected stopping time. Best policy identification in MDPs has been mostly investigated under the lens of minimax-optimality. The minimax framework may be overly pessimistic by accounting for the worst possible MDP, whereas an algorithm with instance-specific guarantees can adapt its exploration procedure to the hardness of the MDP instance that it faces. Recently, a few works made the first attempts towards understanding the instance-specific sample complexity of reinforcement learning. However, they typically either make simplifying assumptions such as access to a generative model [ZKB19, MP21], or restrict their attention to episodic MDPs [WSJ21]. In practice however, the samples gathered rather correspond to a single, possibly infinite, trajectory of the system that we wish to control. This motivates our study of the full online setting where observations are only obtained by navigating in the MDP, that is by sequential choices of actions and following the transitions of the MDP.
Our contributions. [MP21] recently proposed an information-theoretical complexity analysis for MDPs in the case of access to a generative model. Here we extend their results to the online setting. Our main goal is to understand how the online learning scheme affects the sample complexity compared to the easier case where we have a generative model. A natural first step consists in understanding how the first order term T � log(1/δ) changes. Thus we only focus on the asymptotic regime δ → 0. Our key contributions can be summarized as follows:
• First, we adapt the lower bound of [MP21] to the online setting (Proposition 2). The new bound also writes as the value of a zero-sum two-player game between nature and the algorithm, where the loss function remains the same, but where the set of possible strategies for the algorithm is restricted to a subset Ω(M) of the simplex of dimension SA− 1. We refer to the constraints defining Ω(M) as the navigation constraints.
• We propose MDP-NaS, the first algorithm for the online setting1 with instance-dependent bounds on its sample complexity in the asymptotic regime δ → 0 (Theorem 6). A major challenge lies in the design of a sampling rule that guarantees that the sampling frequency of state-action pairs � Nsa(t)/t � s,a
converges to some target oracle allocation ω� ∈ Ω(M). Indeed, since we can no longer choose the next state of the agent, the tracking procedure which was developed by [GK16] for multi-armed bandits and used in [MP21] for MDPs with a generative model can no longer be applied in our setting. We propose a new sampling rule which performs exploration according to a mixture of the uniform policy and a plugin estimate of the oracle policy (the policy whose stationary state-action distribution is ω�) and prove that it satisfies the requirement above. The analysis of our sampling rule relies on an ergodic theorem for non-homogeneous Markov chains of independent interest (Proposition 12).
• We investigate, depending on the communication properties of the ground-truth instance M, what is the minimal forced-exploration rate in our sampling rule that guarantees the consistency of the plug-in estimator of the oracle policy. Our findings imply that when M is ergodic, an exploration rate as low as 1/ √ t is sufficient. However, when M is only assumed
to be communicating, one is obliged to resort to a much more conservative exploration rate of t− 1 m+1 , where m is a parameter defined in Lemma 4 that may scales as large as S − 1 in the worst case.
• Finally, our stopping rule represents the first implementation of the Generalized Likelihood Ratio test for MDPs. Notably, we circumvent the need to solve the max-min program of the lower bound exactly, and show how an upper bound of the best-response problem, such as the one derived in [MP21], can be used to perform a GLR test. This improves upon the sample complexity bound that one obtains using the KL-Ball stopping rule of [MP21] by at least a factor of 22.
1Before publication of this work, but after a preprint was available online, [WSJ21] proposed another algorithm with instance-dependent guarantees.
2Note that the stopping rule is independent of the sampling rule and thus can be used in both the generative and the online settings. Furthermore, one may even obtain an improved factor of 4 by using a deviation inequality for the full distribution of (reward, next-state) instead of a union bound of deviation inequalities for each marginal distribution.

heading: 1.1 Related work
text: Minimax Best-Policy Identification. BPI in the online setting has been investigated recently by a number of works with minimax sample complexity bounds. In the case of episodic MDPs [KMDD+21], [MDJ+20] proposed algorithms that identify an ε-optimal policy at the initial state w.h.p. In contrast, in the case of infinite-horizon MDPs one is rather interested in finding a good policy at every state. Recent works provide convergence analysis for Q-learning [LWC+20b] or policy gradient algorithms [AHKS20], [FYAY21], [ZCA21]. Their results typically state that if the algorithm is fed with the appropriate hyperparameters, it can return an ε-optimal policy w.h.p. after collecting a polynomial number of samples. In practice, a pure exploration agent needs a stopping rule to determine when to halt the learning process. In particular, the question of how to tune the number of iterations of these algorithms without prior knowledge of the ground truth instance remains open.3
Generative Model. A large body of literature focuses on the so-called generative model, where in each step, the algorithm may query a sample (i.e., observe a reward and a next-state drawn from the rewards and transitions distributions respectively) from any given state-action pair [KS98],[KMN99], [EDMM06], [AMK13],[DTC13], [Wan17], [SWW+18], [ZKB19], [AKY20], [LWC+20a], [LCC+21], [MP21].
Instance-specific bounds. Instance-optimal algorithms for Best Arm Identification in multi armed bandits (MDPs with one state) have been obtained independently by [GK16],[Rus16]. Here, we extend their information-theoretical approach to the problem of Best Policy Identification in MDPs. More recently, [WSJ21] provided an algorithm for BPI in episodic MDPs with instance-specific sample complexity. A more detailed comparison with [WSJ21] can be found in Section 6.
Outline. The rest of the paper is organized as follows: After introducing the setting and giving some notation and definitions in Section 2, we derive in Section 3 a lower bound on the time required by any algorithm navigating the MDP until it is able to identify the best policy with probability at least 1− δ. The algorithm is presented in Section 4. Section 5 contains our main results along with a sketch of the analysis. Finally, in Section 6 we compare our results with MOCA, the only other algorithm (to the best of our knowledge) with problem-dependent guarantees in the online setting. Most technical results and proofs are given in the appendix.

heading: 2 Setting and notation
text: Discounted MDPs. We consider infinite horizon MDPs with discount and finite state and action spaces S and A. Such an MDP M is defined through its transition and reward distributions pM(·|s, a) and qM(·|s, a) for all (s, a). For simplicity, qM(·|s, a) will denote the density of the reward distribution w.r.t. a positive measure λ with support included in [0, 1]. Specifically, pM(s�|s, a) denotes the probability of transitioning to state s� after playing action a at state s while R(s, a) is the random instantaneous reward that is collected. Finally, γ ∈ [0, 1) is a discounting factor. We look for an optimal control policy π� : S → A maximizing the long-term discounted reward: V πM(s) = EM,π[ �∞ t=0 γ
tR(st,π(st))], where EM,π denotes the expectation w.r.t the randomness in the rewards and the trajectory when the policy π is used. Classically, we denote by V �M the optimal value function of M and by Q�M the optimal Q-value function of M. Π�(M) = {π : S → A, V πM = V �M} denotes the set of optimal policies for M. Problem-dependent quantities. The sub-optimality gap of action a in state s is defined as Δsa = V � M(s) − Q�M(s, a). Let Δmin = mins,a�=π�(s) Δsa be the minimum gap and sp(V �M) = maxs,s� |V �M(s) − V �M(s�)| be the span of V �M. Finally, we introduce the variance of the value function in (s, a) as Varp(s,a)[V �M] = Vars�∼pM(.|s,a)[V � M(s �)].
Active pure exploration with fixed confidence. When M is unknown, we wish to devise a learning algorithm A identifying, from a single trajectory, an optimal policy as quickly as possible with some given level of confidence. Formally, such an algorithm consists of (i) a sampling rule, selecting in each round t in an adaptive manner the action at to be played; at depends on past observations, it
3Here we chose not to mention works that investigate the sample complexity in the PAC-MDP framework [Kak03]. Indeed, in this framework the sample complexity is rather defined as the the number of episodes where the algorithm does not play an ε-optimal policy. As explained in [DMKV21], this objective is closer to regret minimization than to pure exploration.
is FAt -measurable where FAt = σ(s0, a0, R0 . . . , st−1, at−1, Rt−1, st) is the σ-algebra generated by observations up to time t; (ii) a stopping rule τδ, a stopping time w.r.t. the filtration (FAt )t≥0, deciding when to stop collecting observations; (iii) a decision rule returning π̂�τδ an estimated optimal policy.
An algorithm A is δ-Probably Correct (δ-PC) over some set M of MDPs, if for any M ∈ M, it returns (in finite time) an optimal policy with probability at least 1 − δ. In this paper, we aim to devise a δ-PC algorithm A with minimal sample complexity EM,A[τδ]. We make the following assumption. Assumption 1. We consider the set M of communicating MDPs with a unique optimal policy.
We justify the above assumption as follows. (i) We restrict our attention to the case where M is communicating, for otherwise, if it is Multichain there would be a non-zero probability that the algorithm enters a subclass of states from which there is no possible comeback. In this case it becomes impossible to identify the global optimal policy4. (ii) About the uniqueness of the optimal policy, treating the case of MDPs with multiple optimal policies, or that of ε-optimal policy identification, requires the use of more involved Overlapping Hypothesis tests, which is already challenging in multiarmed bandits (MDPs with a single state) [GK19]. We will analyze how to remove this assumption in future work. Notation. Z � S × A is the state-action space. Σ � {ω ∈ RS×A+ : �
s,a ωsa = 1}, the simplex of dimension SA − 1. Nsa(t) denotes the number of times the state-action pair (s, a) has been visited up to the end of round t. We also introduce Ns(t) = � a∈A Nsa(t). Similarly, for a vector
ω ∈ Σ we will denote ωs � �
a∈A ωsa. For a matrix A ∈ Rn×m, the infinity norm is defined as �A�∞ � max1≤i≤n �m j=1 |ai,j |. The KL divergence between two probability distributions P and Q on some discrete space S is defined as: KL(P�Q) � �s∈S P (s) log( P (s) Q(s) ). For Bernoulli distributions of respective means p and q, the KL divergence is denoted by kl(p, q). For distributions over [0, 1] defined through their densities p and q w.r.t. some positive measure λ, the KL divergence is: KL(p�q) � �∞ −∞ p(x) log � p(x) q(x) � λ(dx). M denotes the set of communicating MDPs with a unique optimal policy. For two MDPs M,M� ∈ M, we say that M � M� if for all (s, a), pM(·|s, a) � pM�(·|s, a) and qM(·|s, a) � qM�(·|s, a). In that case, for any state (action pair) (s, a), we define the KL divergence of the distributions of the one-step observations under M and M� when starting at (s, a) as KLM|M�(s, a) � KL(pM(·|s, a)�pM�(·|s, a)) +KL(qM(·|s, a)�qM�(·|s, a)).

heading: 3 Sample complexity lower bound
text: In this section, we first derive a lower bound on the expected sample complexity satisfied by any δ-PC algorithm. The lower bound is obtained as the solution of a non-convex optimization problem, as in the case where the learner has access to a generative model [MP21]. The problem has however additional constraints, referred to as the navigation constraints, due the fact that the learner has access to a single system trajectory. The expected sample complexity of an algorithm A is EM,A[τδ] = � s,a EM,A[Nsa(τδ)]. Lower bounds on the sample complexity are derived by identifying constraints that the various Nsa(τδ)’s need to satisfy so as to get a δ-PC algorithm. We distinguish here two kinds of constraints:
Information constraints. These are constraints on EM,A[Nsa(τδ)], so that the algorithm can learn the optimal policy with probability at least 1− δ. They are the same as those derived [MP21] when the learner has access to a generative model and are recalled in Lemma 9 in Appendix C.
Navigation constraints. Observations come from a single (but controlled) system trajectory which imposes additional constraints on the Nsa(τδ)’s. These are derived by just writing the ChapmanKolmogorov equations of the controlled Markov chain (refer to Appendix C for a proof). Lemma 1. For any algorithm A, and for any state s, we have:���EM,A[Ns(τδ)]− �
s�,a�
pM(s|s�, a�)EM,A[Ns�a�(τδ)] ��� ≤ 1. (1)
Putting all constraints together, we obtain the following sample complexity lower bound. 4Unless we modify the objective to finding the optimal policy in this subchain.
Proposition 2. Define the set of navigation-constrained allocation vectors:
Ω(M) = � ω ∈ Σ : ∀s ∈ S, ωs = �
s�,a�
pM(s|s�, a�)ωs�a� � .
Further define Alt(M) = {M� MDP : M � M�,Π�(M) ∩ Π�(M�) = ∅} the set of alternative instances. Then the expected sample complexity EM,A[τδ] of any δ-PC algorithm A satisfies:
lim inf δ→0 EM,A[τ ] log(1/δ) ≥ To(M), where To(M)−1 = sup ω∈Ω(M) T (M,ω)−1 (2)
and T (M,ω)−1 = inf
M�∈Alt(M)
�
s,a
ωsaKLM|M�(s, a). (3)
Remark 1. A common interpretation of change-of-measure lower bounds like the one above is the following: the optimization problem in the definition of To(M) can be seen as the value of a twoplayer zero-sum game between an algorithm which samples each state-action (s, a) proportionally to ωsa and an adversary who chooses an alternative instance M� that is difficult to distinguish from M under the algorithm’s sampling strategy. This suggests that an optimal algorithm should play the optimal allocation that solves the optimization problem (2) and, as a consequence, rules out all alternative instances as fast as possible. Remark 2. Note that compared to the lower bound of the generative setting in [MP21], the only change is in the set of sampling strategies that the algorithm can play, which is no longer equal to the entire simplex.

heading: 3.1 Proxy for the optimal allocation and the characteristic time
text: As shown in [MP21], even without accounting for the navigation constraints, computing the characteristic time To(M) and in particular, the optimal allocation leading to it is not easy. Indeed, the sub-problem corresponding to computing T (M,ω)−1 is non-convex. This makes it difficult to design an algorithm that targets the optimal weights argmaxω∈Ω(M) T (M,ω)−1. Instead, we use a tractable upper bound of T (M,ω) from [MP21]: Lemma 3. (Theorem 1, [MP21]) For all vectors ω ∈ Σ, T (M,ω) ≤ U(M,ω), where5
U(M,ω) = max (s,a):a �=π�(s) Hsa ωsa + H�
Smin s
ωs,π�(s) , (4)
and    Hsa = 2 Δ2sa +max � 16Varp(s,a)[V � M] Δ2sa , 6 sp(V �M) 4/3 Δ 4/3 sa � , H� = 2S
[Δmin(1− γ)]2 +O
� S Δ2min(1− γ)3 � .
(5)
Using U(M,ω), we obtain the following upper bound on the characteristic time (2): To(M) ≤ Uo(M) � inf
ω∈Ω(M) U(M,ω). (6)
The advantages of the above upper bound Uo(M) are that: (i) it is a problem-specific quantity as it depends on the gaps and variances of the value function in M; (ii) the corresponding allocation (that solves (6)) can be easily computed, and hence targeted. Indeed, the optimization problem in (6) has convex objective and constraints. Therefore, we can use the projected subgradient-descent algorithm to compute
ω�(M) � argmin ω∈Ω(M) U(M,ω) = argmax ω∈Ω(M) U(M,ω)−1, (7)
which will be used in our algorithm as a proxy6 for argmaxω∈Ω(M) T (M,ω)−1. 5The exact definition of H� is given in Appendix C. 6Note that if we have access to an optimization oracle that, given a MDP M, returns the optimal allocation solution to (2), then we can replace ω�(M) by this optimal allocation. Our algorithm will then be asymptotically optimal up to a factor of 2.

heading: 4 Algorithm
text: We propose MDP-NaS (MDP Navigate-and-Stop), a model-based algorithm that is inspired by the lower bound. The lower bound suggests that to identify the best policy in a sample-efficient manner, the algorithm must collect samples from state-action pair (s, a) proportionally to ω�sa(M). We propose two sampling rules which ensure that the former statement holds in the long term (see Section 4.1 and Theorem 7 for a rigorous formulation). Our sampling rules are combined with a Generalized Likelihood Ratio (GLR) test (or rather a proxy of the GLR test, see Section 4.2 for details), that stops as soon as we are confident that �π�t = π� with probability at least 1 − δ. The pseudo-code for MDP-NaS is given in Algorithm 1.
Algorithm 1: MDP Navigate and Stop (MDP-NaS) Input: Confidence level δ, ERGODIC boolean variable, communication parameter m or an
upper bound. 1 if ERGODIC then 2 Set (εt)t≥1 = (1/ √ t)t≥1. 3 else 4 Set (εt)t≥1 = (t− 1 m+1 )t≥1. 5 end 6 Set t ← 0 and Nsa(t) ← 0, for all (s,a). 7 Initialize empirical estimate �M0 by drawing an arbitrary MDP from M. 8 Compute �π�t ← POLICY-ITERATION(�Mt). 9 while Stopping condition (13) is not satisfied do 10 Compute ω�(�Mt) according to (7) and πo(�Mt) according to (8). 11 if t = 0 then 12 Play a0 ∼ Unif([|1, A|]). 13 else 14 Play at ∼ πt(.|st), where πt is determined by either (9) or (10). 15 end 16 Observe (Rt, st+1) ∼ q(.|st, at)⊗ p(.|st, at). 17 t ← t+ 1. 18 Update �Mt and (Nsa(t))s,a. 19 Compute �π�t ← POLICY-ITERATION(�Mt). 20 end
Output: Empirical optimal policy �π�τ .

heading: 4.1 Sampling rule
text: We introduce a few definitions to simplify the presentation. Any stationary policy π induces a Markov chain on Z whose transition kernel is defined by Pπ((s, a), (s�, a�)) � P (s�|s, a)π(a�|s�). With some abuse of notation, we will use Pπ to refer to both the Markov chain and its kernel. We denote by πu the uniform random policy, i.e., πu(a|s) = 1/A for all pairs (s, a). Finally, we define the vector of visit-frequencies N(t)/t � � Nsa(t)/t � (s,a)∈Z .
In contrast with pure exploration in Multi-Armed Bandits and MDPs with a generative model where any allocation vector in the simplex is achievable, here the agent can only choose a sequence of actions and follow the resulting trajectory. Therefore, one might ask if the oracle allocation can be achieved by following a simple policy. A natural candidate is the oracle policy defined by
∀(s, a) ∈ Z, πo(a|s) � ω � sa
ω�s = ω�sa� b∈A ω � sb . (8)
It is immediate to check that ω� is the stationary distribution of Pπo . Denote by πo(M) the above oracle policy defined through ω�(M). Policy πo(M) is the target that we would like to play, but since the rewards and dynamics of M are unknown, the actions must be chosen so as to estimate consistently the oracle policy while at the same time ensuring that N(t)/t converges to ω�(M). The following two sampling rules satisfy these requirements.
D-Navigation rule: At time step t, the learner plays the policy
πt = εtπu + (1− εt)πo(�Mt), (9) C-Navigation rule: At time step t, the learner plays
πt = εtπu + (1− εt) t�
j=1
πo(�Mj)/t, (10)
where εt is a decreasing exploration rate to be tuned later. In the second case, the agent navigates using a Cesàro-mean of oracle policies instead of the current estimate of the oracle policy, which makes the navigation more stable.

heading: 4.1.1 Tuning the forced exploration parameter
text: The mixture with the uniform policy7 helps the agent to explore all state-action pairs often enough in the initial phase. This is particularly necessary in the case where the empirical weight ω�sa(�Mt) of some state-action pair (s, a) is under-estimated, which may cause that this pair is left aside and hence the estimation never corrected. The next result in this section gives a tuning of the rate εt that ensures a sufficient forced exploration: Lemma 4. Let m be the maximum length of the shortest paths (in terms of number of transitions) between pairs of states in M: m � max(s,s�)∈S2 min{n ≥ 1 : ∃π : S → A, Pnπ (s, s�) > 0}. Then C-Navigation or D-Navigation with any decreasing sequence (εt)t≥1 such that ∀t ≥ 1, εt ≥ t− 1 m+1
satisfies: PM,A � ∀(s, a) ∈ Z, limt→∞ Nsa(t) = ∞ � = 1.
Remark 3. When the parameter m is unknown to the learner, one can replace it by its worst case value mmax = S − 1. However, when prior knowledge is available, using a faster-decreasing sequence εt = t− 1 m+1 instead of t− 1 S can be useful to accelerate convergence, especially when the states of M are densely connected (m � S − 1).
Minimal exploration rate: Communicating MDPs. The forced exploration rate t− 1S vanishes quite slowly. One may wonder if this rate is necessary to guarantee sufficient exploration in communicating MDPs: the answer is yes in the worst case, as the following example shows. Consider a variant of the classical RiverSwim MDP with state (resp. action) space S = [|1, S|], (resp. A = {LEFT1, LEFT2, RIGHT}). LEFT1 and LEFT2 are equivalent actions inducing the same rewards and transitions. After playing RIGHT the agent makes a transition of one step to the right, while playing LEFT1 (or LEFT2) moves the agent all the way back to state 1. The rewards are null everywhere but in states {1, S} where R(1, LEFT1), R(1, LEFT2) are equal to 0.01 almost surely and R(S, RIGHT) is Bernoulli with mean 0.02.
When γ is close to 1, the optimal policy consists in always playing RIGHT so as to reach state S and stay there indefinitely. Now suppose that the agent starts at s = 1 and due to the small probability of observing the large reward in state S, she underestimates the value of this state in the first rounds and focuses on distinguishing the best action to play in state 1 among {LEFT1, LEFT2}. Under this scenario she ends up playing a sequence of policies that scales like πt = 2εtπu + (1− 2εt)(LEFT1 + LEFT2)/28. This induces the non-homogeneous Markov Chain depicted in Figure 1. For the exploration rate εt = t−α, we show that if the agent uses any α > 1S−1 , with non-zero probability she will visit state S only a finite number of times. Therefore she will fail to identify the optimal policy for small values of the confidence level δ. The proof is deferred to Appendix D.
Minimal exploration rate: Ergodic MDPs. For such MDPs, we can select εt = 1/tα where α < 1 without compromising the conclusion of Lemma 4. The proof is deferred to Appendix D.

heading: 4.2 Stopping rule
text: To implement a GLR test, we define �M�(t), the likelihood of the observations under some MDP M� � M: �M�(t) = �t−1 k=0 pM�(sk+1|sk, ak)qM�(Rk|sk, ak), where at step k the algorithm is in
7Our results still hold if πu is replaced by any other policy π which has an ergodic kernel. In practice, this can be helpful especially when we have prior knowledge of a fast-mixing policy π.
8Modulo a re-scaling of εt by a constant factor of 1/2.
state sk, plays action ak and observes the reward Rk and sk+1 (the next state). Performing a GLR test in step t consists in computing the optimal policy �π�t for the estimated MDP �Mt and in comparing the likelihood of observations under the most likely model where �π�t is optimal to the likelihood under the most likely model where �π�t is sub-optimal. Following the standardized form of the GLR for multi-armed bandits in [DKM19] we write:
G�π�t (t) = log
sup M�:�π�t ∈Π�(M�) �M�(t)
sup M�:�π�t /∈Π�(M�)
�M�(t) = log
��Mt(t)
sup M�∈Alt( �Mt)
�M�(t) = inf M�∈Alt( �Mt) log
��Mt(t)
�M�(t)
= inf M�∈Alt( �Mt)
�
(s,a)∈Z Nsa(t)
� KL(�qs,a(t), qM�(s, a)) + KL(�ps,a(t), pM�(s, a)) � (11)
= t T � �Mt,N(t)/t �−1 . (12)
The hypothesis (�π�t �= π�) is then rejected as soon as the ratio of likelihoods becomes greater than the threshold β(t, δ), properly tuned to ensure that the algorithm is δ-PC. Note that the likelihood ratio G�π�t (t) itself can be difficult to compute for MDPs, since it is equivalent to solving (3), we lower bound it using (12) and Lemma 3. This leads to the following proposition: Proposition 5. Define the random thresholds for the transitions and rewards respectively:
βp(t, δ) � log(1/δ) + (S − 1) �
(s,a)
log � e � 1 +Nsa(t)/(S − 1) ��
βr(t, δ) � SA ϕ � log(1/δ)/SA � + 3 �
s,a
log � 1 + log(Nsa(t)) �
where ϕ(x) ∼ ∞ x+ log(x) is defined in the appendix. Then the stopping rule:
τδ � inf � t ≥ 1 : t U � �Mt,N(t)/t �−1 ≥ βr(t, δ/2) + βp(t, δ/2) � (13)
is δ-PC, i.e., P(τδ < ∞, �π�τδ �= π�) ≤ δ.

heading: 5 Main results and sample complexity analysis
text: First we state our main results, which take the form of asymptotic upper bounds on the sample complexity of MDP-NaS, under a slightly more conservative exploration rate than in Lemma 4. Then we present the most important ingredients in their proof. The complete proof is provided in Appendix F. Theorem 6. Using the C-Navigation sampling rule with εt = t− 1 2(m+1) and the stopping rule (13): (i) MDP-NaS stops almost surely and its stopping time satisfies P � lim supδ→0 τδ log(1/δ) ≤ 2Uo(M) � = 1, where Uo(M) was defined in (6); (ii) the stopping time of MDP-NaS has a finite expectation for all δ ∈ (0, 1), and lim supδ→0 E[τδ] log(1/δ) ≤ 2Uo(M).

heading: 5.1 Proof sketch
text: Concentration of empirical MDPs: The starting point of our proof is a concentration event of the empirical estimates �Mt around M. For ξ > 0 and T ≥ 1, we define C1T (ξ) = �T
t=T 1/4
���� �Mt −M ��� ≤ ξ, ���πo(�Mt)− πo(M) ��� ∞ ≤ ξ �
, where �.� is a semi-norm on MDPs. Then we prove in Lemma 18 that C1T (ξ) holds with high probability in the sense that for all T ≥ 1:
P � C1T (ξ) � ≥ 1−O � 1/T 2 � . (14)
For this purpose we derive, for all pairs (s, a), a lower bound on Nsa(t) stating that9: P � ∀(s, a) ∈ Z, ∀t ≥ 1, Nsa(t) ≥ (t/λα)1/4 − 1 � ≥ 1 − α where λα ∝ log2(1 + SA/α) is a parameter that depends on the mixing properties of M under the uniform policy. These lower bounds on Nsa(t) w.h.p. contrast with their deterministic equivalent obtained for C-tracking in [GK16].
Concentration of visit-frequencies: Before we proceed, we make the following assumption.
Assumption 2. Pπu is aperiodic10.
Under Assumptions 1 and 2 the kernel Pπu , and consequently also Pπo , becomes ergodic. Hence the iterates of Pπo converge to ω�(M) at a geometric speed. Also note that the Markov chains induced by playing either of our sampling rules are non-homogeneous, with a sequence of kernels (Pπt)t≥1 that is history-dependent. To tackle this difficulty, we adapt a powerful ergodic theorem (see Proposition 12 in the appendix) from [FMP11] originally derived for adaptive Markov Chain Monte-Carlo (MCMC) algorithms to get the following result.
Theorem 7. Using the C-Navigation or D-Navigation we have: lim t→∞ N(t)/t = ω�(M) almost surely.
Lemma 4 and Theorem 7 combined prove Theorem 6 (i) in a straightforward fashion. The proof of Theorem 6 (ii) is more involved. Again, we adapt the proof method from [FMP11] to derive a finite-time version of Proposition 12 which results into the following proposition.
Proposition 8. Under C-Navigation, for all ξ > 0, there exists a time Tξ such that for all T ≥ Tξ, all t ≥ T 3/4 and all functions f : Z −→ �+, we have:
P ����� �t k=1 f(sk, ak)
t − E(s,a)∼ω� [f(s, a)]
���� ≥ Kξ �f�∞ ξ ����C1T (ξ) � ≤ 2 exp � − tξ2 � .
where ξ �→ Kξ is a mapping with values in (1,∞) such that lim supξ→0 Kξ < ∞.
Now define C2T (ξ) = �T t=T 3/4 ���N(t)/t − ω�(M) �� ≤ Kξ ξ � . Then Proposition 8 and Eq. (14) combined imply that for T large enough, the event C1T (ξ) ∩ C2T (ξ) holds w.h.p. so that the expected stopping time is finite on the complementary event: E[τδ�{C1T (ξ) ∪ C2T (ξ)}] < ∞. Now given the asymptotic shape of the thresholds: βr(t, δ/2) + βp(t, δ/2) ∼
δ→0 2 log(1/δ), we may informally
write:
E � τδ�{C1T (ξ) ∩ C2T (ξ)} � �
δ→0 2 log(1/δ) sup (M�,ω�)∈Bξ Uo
� M�,ω� � ,
where Bξ = {(M�,ω�) : �M� −M� ≤ ξ, �ω� − ω�(M)�∞ ≤ Kξ ξ}. Taking the limits when δ and ξ go to zero respectively concludes the proof.
9Using the method in our proof one can derive a lower bound of the type tζ for any ζ < 1/2 and any exploration rate εt = t−θ with θ < 1/(m+ 1). We chose θ = 12(m+1) and ζ = 1/4 because they enable us to have an explicit formula for λα. See Lemma 11 in the appendix.
10This assumption is mild as it is enough to have only one state s̃ and one action ã such that PM(s̃|s̃, ã) > 0 for it to be satisfied. Furthermore, Assumptions 1 and 2 combined are still less restrictive than the usual ergodicity assumption, which requires that the Markov chains of all policies are ergodic.

heading: 6 Comparison with MOCA
text: Recall from Lemma 3 and Theorem 6 that our sample complexity bound writes as:
O �
inf ω∈Ω(M) max (s,a):a �=π�(s)
1 + Varp(s,a)[V � M]
ωsaΔ2sa +
1
min s
ωs,π�(s)Δ 2 min(1− γ)3
� log(1/δ).
Hence, in the asymptotic regime δ → 0, MDP-NaS finds the optimal way to balance exploration between state-action pairs proportionally to their hardness: (1+Varp(s,a)[V �M])/Δ 2 sa for sub-optimal pairs (resp. 1/Δ2min(1− γ)3 for optimal pairs). After a preprint of this work was published, [WSJ21] proposed MOCA, an algorithm for BPI in the episodic setting. MOCA has the advantage of treating the more general case of ε-optimal policy identification with finite-time guarantees on its sample complexity. The two papers have different and complementary objectives but one can compare with their bound for exact policy identification, i.e when ε < ε�11, in the asymptotic regime δ → 0. In this case, by carefully inspecting the proofs of [WSJ21], we see that MOCA’s sample complexity writes as12:
O � H�
h=1
inf ω∈Ω(M) max s,a�=π�(s)
H2
ωsa(h)Δsa(h)2
� log(1/δ) +
polylog(S,A,H, log(ε∗)) log3(1/δ) ε∗
where H is the horizon and Δsa(h) is the sub-optimality gap of (s, a) at time step h. We make the following remarks about the bounds above:
1. MOCA only pays the cost of worst-case visitation probability multiplied by the gap of the corresponding state min
s,a�=π�(s) ωsaΔ
2 sa. Instead, MDP-NaS pays a double worst-case cost
of the smallest visitation probability multiplied by the minimum gap mins ωs,π�(s)Δ2min. As pointed out by [WSJ21] the former scaling is better, especially when the state where the minimum gap is achieved is different from the one that is hardest to reach. This is however an artefact of the upper bound in Lemma 3 that MDP-NaS uses as a proxy for the characteristic time. Using a more refined bound, or an optimization oracle that solves the best-response problem, one can remove this double worst-case dependency.
2. The sample complexity of MOCA divided by log(1/δ) still explodes when δ goes to zero, contrary to MDP-NaS’s bound.
3. The sample complexity of MDP-NaS is variance-sensitive for sub-optimal state-action pairs, while MOCA’s bound depends on a worst-case factor of H2. Indeed as the rewards are in [0, 1], we always have V �M ≤ H and Varp(s,a)[V �M] ≤ H2 in the episodic setting.
We conclude this section by noting that MDP-NaS has a simple design and can easily be implemented.

heading: 7 Conclusion
text: To the best of our knowledge, this paper is the first to propose an algorithm with instance-dependent sample complexity for Best Policy identification (BPI) in the full online setting. Our results are encouraging as they show: 1) How the navigation constraints of online RL impact the difficulty of learning a good policy, compared to the more relaxed sampling schemes of Multi-Armed Bandits and MDPs with a generative model. 2) That, provided access to an optimization oracle that solves the information-theoretical lower bound (resp. some convex relaxation of the lower bound), asymptotic optimal (resp. near-optimal) sample complexity is still possible through adaptive control of the trajectory. This opens up exciting new research questions. First, it is intriguing to understand how the mixing times -and not just the stationary distributions- of Markov chains induced by policies impact the sample complexity of BPI in the moderate confidence regime. A second direction would be to extend our contributions to the problem of finding an ε-optimal policy, which is of more practical interest than identifying the best policy.
11ε� is defined in their work as the threshold value for ε such that the only ε-optimal policy is the best policy. However, when the objective is to find the optimal policy, it is not clear from their paper how one can determine such a value of ε without prior knowledge of the ground truth instance.
12The log3(1/δ) term comes from the sample complexity of their sub-routine FINDEXPLORABLESETS.
Broader Impact This paper tries to advance our theoretical understanding of the sample complexity of finding a good policy in Markov Decision Processes, which can be interesting for both theoreticians and practitioners. However, this paper is not oriented towards a specific application, so a wider broader impact discussion is not applicable.
Acknowledgments and Disclosure of Funding The authors would like to thank the anonymous reviewers whose comments and questions helped improve the clarity of this manuscript. A. Proutiere’s research is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. A. Garivier and A. Al Marjani acknowledge the support of the Project IDEXLYON of the University of Lyon, in the framework of the Programme Investissements d’Avenir (ANR-16IDEX-0005), and Chaire SeqALO (ANR-20-CHIA-0020).

Review summaries:
This paper deals with online learning of policies for MDPs. Its main novelty is considering the "navigation constraints" related to this online setting where, in contrast with an episodic setting, the system must learn the policy in a single episode without being able to reset to an initial state. Bounds on sample complexity are derived and an algorithm for learning the best policy by exploiting the lower bounds is proposed.  

The paper studies the best policy identification (BPI) problem in Markov Decision Processes, under navigation constraints, i.e., when accessing a single trajectory from the environment, as opposed to the generative model setting. The paper focuses first on a lower bound on the sample complexity obtained by extending existing results. Then, an algorithm is introduced, and the corresponding sample complexity is analyzed. The contribution is mainly theoretical.

The paper studies best-policy identification in discounted MDPs with online interaction. The authors first derive an information-theoretic lower bound on the sample complexity of any \delta-correct algorithm for this problem. The lower bound is given as the solution to a non-convex optimization problem for which a convex relaxation is provided. The authors then design an algorithm using the standard template for building pure exploration strategies from asymptotic lower bounds (GLR test + tracking + forced exploration). For this algorithm, the authors derive an asymptotic (as \delta -> 0) upper bound on the sample complexity that matches the value of the relaxed optimization problem up to a factor 2.

The paper studies problem-dependent sample complexity bounds for best policy identification (BPI) in finite MDPs under the infinite horizon discounted criterion. The agent interacts sequentially (online) with the MDP, a weaker assumption than the generative model required by previous work in the same setting. Its main contributions are:  (i)  A problem-dependent lower bound on the sample complexity that takes into account navigation constraints;  (ii) Since the lower bound is defined as the solution to a non-convex optimization problem, the paper uses a convex relaxation introduced by [MP20] to derive a relaxed lower bound;  (iii) An algorithm whose upper bound matches the relaxed lower bound up to a factor 2. 

This work talks about best policy identification problem in discounted infinite MDP. Instead of assuming a generator, this work is on the online setting of MDP, where the agent can only collect state action pairs through online interaction with the environment. In theory, the work provides a lower bound of the BPI problem. Then the work provides a model-based algorithm MDP-NaS, which is shown to converge to the optimal policy.