Navigating to the Best Policy in Markov Decision Processes
Authors: Aymen Al Marjani
Aurélien Garivier
Alexandre Proutiere
Venue: NeurIPS 2021 Poster (2021)
Keywords: Markov Decision Processes
Sample Complexity
Pure Exploration
Instance-dependent bounds.

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-\delta$. 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 \emph{generative setting}~\cite{pmlr-v139-marjani21a}, 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 \emph{navigation constraints}, induced by the \emph{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.

Navigating to the Best Policy in Markov Decision Processes
Aymen Al Marjani UMPA, ENS Lyon Lyon, France aymen aa__aallmaaaaaaa jani @anaannninnoon.ff
Aurélien Garivier
Alexandre Proutiere EECS and Digital Futures
UMPA, CNRS, INRIA, ENS Lyon Lyon, France aurelien.gare waw.iiirrrrieseiyoooo.
KTH Royal Institute of Technology, Sweden alepro@kth.se
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 problem-dependent lower bound the average number of steps required before a correct answer can be given with probability at least 1 - 5. We further provide the first algorithm with instance-specifee sample complexity in this setting. This algorithm addresses the general case of communicating MDPs; we also propose a variant with reduced exploration rate (and hence faster convergence) under 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 non-homogeen aon-homogeneous Markov chains which we consider of wide interest the analysis of Markov Decision Processes.
Introduction
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, I.22] and references therein). Regret minimization (see e.g. [AJO09, FCG10J) is particularly relevant when the rewards accumulated during the learning phase are important. This is however not always the case: for example, when learning 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 the training of robot prototypes in the factory: reasonably good policy is first searched, regardless of the losses incurred, that can serve as an initialization for second phase pegret-minimizann
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, 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 s-optimal policy with probability at least 6. Crucially, the algorithm halts random time step, determined by
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

stopping rule which guarantees that the probability of returning a wrong answer is less that 8. 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 crrimax-opiimality.. 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 generative model [ZKB19, MP21], 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 infereiaion-thhorrttiall complexity analysis for MDPs in the case of access to 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 generative model. A natural first step consists in understanding how the first order term T* log(1/5) changes. Thus we only focus on the asymptotic regime 8 - O. 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 setting' with instance instance-dependent bounds on its sample complexity in the asymptotic regime - (Theorem 6). A major challenge lies in the design of a sampling rule that guarantees that the sampling frequency of state-action pairs (Nsa(Q (t)/t).... converges to some target oracle allocation w' E ((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 plug- in estimate of the oracle policy (the policy whose stationary state-action distribution is w") and prove that 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/ / 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. m+T, where mn 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 [MP21], can be used to perform 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 2
"Before publication of this work, but after a preprint was available online, [WSJ21] proposed another algorithm with pestance-depender guarantees.
"Note that the stopping rule is independent of the sampling rule and thus can be used both the generative and the online settings. Furthermore, one may even obtain an improved factor of 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.
2

---

1.1 Related work
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], [MD]+20] proposed algorithms that identify an e-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 [LbC+20b] or policy gradient algorithms [AHKS20], [FYAY21], [ZCA21]. Their results typically state that if the algorithm is fed with the appropriate hyperparameters, can return an e-optimal policy w.h.p. after collecting a polynomial number of samples. In practice, a pure exploration agent needs 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 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], 20a], [LCC-21] 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 ceormation-thooretiio
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, 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-6 5. 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-dependeen guarantees in the online setting. Most technical results and proofs are given in the appendix.
2 Setting and notation
Discounted MDPs. We consider infinite horizon MDPs with discount and finite state and ac- tion spaces S and A. Such an MDP M is defined through its transition and reward distribu- tions (.M(-ss,a) a) and qu((-s,, a) for all (s, a). For simplicity, gM((ls, a) will denote the density of the reward distribution w.r.t. positive measure À with support included in [0, 1]. Specifically, (8'(8'ss, a) denotes the probability of transitioning to state s' after playing action a at state while R(s,a) a) is the random instantancous reward that is collected. Finally, ? E [0, 1) is a dis- counting factor. We look for an optimal control policy π : S + A maximizing the long-term discounted reward: V (s) E,M= Er= 7 R(s,, (()))], where EM,= denotes the expectation w.r.t the randomness
the rewards and the trajectory when the policy æ is used. Classically, we denote by V4 the optimal value function of M and by QiM the optimal Q-value function of M. II (M) = f A, VM- = Vir denotes the set of optimal policies for M.
Problem-dependent quantities. The sub-optimality gap of action a in state 8 is defined as A.. (5) (s, Let Amin =min Asa be the minimum gap and sp(V)) max,,s' (s) VM (s') be the span of VYM- Finally, we introduce the variance of the value function in (8, a) as Varp(..)) [VM] = Var, [VM (s')).
Active pure exploration with fixed confidence. When M is unknown, we wish to devise 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) sampling rule, selecting in each round in an adaptive manner the action 0e to be played; a, depends on past observations,
$ 'Here we chose not to mention works that investigate the sample complexity in the PAC-MDP framework [Kkk03]. Indeed, in this framework the sample complexity is rather defined as the the number of episodes where the algorithm does not play an e-optimal policy. As explained in [DMKV21], this objective is closer to regret minimization than pure exploration.
3

---

is F -e-masuure where F = a ao Ro..., St....,,-11..4 01-1, -t is the o-algebra generated by observations up to time 1; (ii) stopping rule т8. a stopping time w.r.t. the filtration (F+ Jezo. deciding when to stop collecting observations; (iii) a decision rule returning #7, an estimated optimal policy.
An algorithm A is d-Probably Correct (ô-PC) over some set M of MDPs, if for any M E M, it returns (in finite time) an optimal policy with probability at least 1 - 6. In this paper, we aim to devise a 5-PC algorithm A with minimal sample complexity [M,a(Ts). We make the following assumption.
Assumption 1. We consider the set 14 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 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 policy'. (ii) About the uniqueness of the optimal policy, treating the case of MDPs with multiple optimal policies, or that of s-optimal policy identification, requires the use of more involved Overlapping Hypothesis tests, which is already challenging in multi- armed bandits (MDPs with a single state) [GK19]. We will analyze how to remove this assumption in future work.
2 S x A is the state-action space. E fw E RR Es Wan = 1}. the simplex of dimension SA - 1. (ea(t) denotes the number of times the state-action pair (s, a) has been visited up the end of round t. We also introduce (t) Eeea No (f). Similarly, for vector w E Σ we will denote Ws -EEE Wsa- For a matrix A E R=xx, the infinity norm is defined as |||| maxigign ΣØ= |s,ي-- The KL divergence between two probability distributions P and Q on some discrete space S is defined as: (L(P)IQ & EeEs P(s) log( P(a)). 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 g w.r.t some positive measure X, the KL divergence is:
Notation.
KL (I(pl))) A S p(z) log ((()) A(dx). M denotes the set of communicating MDPs with unique optimal policy. For two MDPs M,M' E M. we say that M < M' if for all (s, a). P-M(-1s, a) < (-1s, a) and q-((-s, a) < (-1s, 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 (L.M)N((ss a) KL(pm(-Is
a)) + KLLLM(( (l (-)s,)).
Sample complexity lower bound
In this section, we first derive lower bound on the expected sample complexity satisfied by any 6-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 generative model [MP21]. The problem has however additional constraints, referred to as the navigation constraints, due the fact that the learner has access to single system trajectory.
The expected sample complexity of an algorithm A is EM.A [Ts] = E.. eNe Lower bounds on the sample complexity are derived by identifying constraints that the various No. (Tx)'ss need satisfy so as to get 6-PC algorithm. We distinguish here two kinds of constraints:
Information constraints. These are constraints on E.M.([Nes (NNs(())) so that the algorithm can learn the optimal policy with probability at least 1 ö. They are the same those derived [MP21] when the learner has access to a generative model and are recalled in Lemma in Appendix C.
Navigation constraints. Observations come from single (but controlled) system trajectory which imposes additional constraints on the Noa (Ts)'sss. These are derived by just writing the Chapman- Kolmogorov equations of the controlled Markov chain (refer to Appendix C for proof).
Lemma 1. For any algorithm A, and for any state s, we have:
[M,A(N.(TT)]]
< 1.
s',a'
Putting all constraints together, we obtain the following sample complexity lower bound.
Unless we modify the objective to finding the optimal policy in this subchain.

---

Proposition 2. Define the set of navigation-conntraaiinn allocation vectors:
9(M) = {we EE:: E: E w. =EPM(s|s' J')wyar
d'
Further define ()) = {M' MDP: : - < (M) instances. Then the expected sample complexity E,M. [T8) of any 6-PC algorithm & satisfies:
= =0 the set of alternative
EMAAAT]
lim 8 log (1/6)
2 To(M), where T(
sup T(M,W)- WED(M)
(2)
and
T(M,W)-'= inf Σ .M'EAL(M)
(3)
8.0
Remark 1. common interpretation of shange-of-measure lower bounds like the one above the following: the optimization problem in the definition of( can be seen as the value of two- player zero-sum game between an algorithm which samples each state-action (s. a) proportionally to wsa and adversary who chooses an alternative instance M' that is difficult to distinguish from M under the algorithm's '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 the entire simplex.
3.1 Proxy for the optimal allocation and the characteristic time
As shown in [MP21], even without accounting for the navigation constraints, computing the char- acteristic time (M and in particular, the optimal allocation leading to it is not easy. Indeed, the sub sub-problem corresponding to computing (M, non-convex, This makes it difficult to design an algorithm that targets the optimal weights arg max T(M,w)- Instead, we use tractable upper bound of ((M, w) from [MP21]:
Lemma 3. (Theorem 1, [MP21]) For vectors w E E, T(M, S (U(,,w where
Hoa +
H*
w),
max
(4)
(s.0)aaf"" (s) Wsa
Smin Wa (+)
2
16 p(a.a) VVll
H
+ max
and
2
2
A
sa
4/3
(5)
25
S
H
+
min (1 7
A (1 7)
Using U(M,w) w), we obtain the following upper bound on the characteristic time (2):
T.(M) s U.(M)
inf U(M,w). WEfl(M)
The advantages of the above upper bound (M( are that: (i) it is problem-specific quantity 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 compute
wn (M) A arg min U(M, arg max WED(M)
U(M,w)-!
WER(M)
which will be used our algorithm as a proxy for arg max T(M,w)-1
Thee exact definition of " is given in Appendix C.
"Note 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 wt (M) by this optimal allocation. Our algorithm will then be asymptotically optimal factor of 2.
5

---

4 Algorithm
We propose MDP-NaS (MDP Navigate-and-Stan 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 propose two sampling rules which ensure that the former statement holds in the long term (see Section 4.1 and Theorem for rigorous formulation). Our sampling rules are combined with Generalized Likelihood Ratio (GLR) test (or rather a proxy of the GLR test, see Section 4.2 for details), that stops soon we are confident that #5 with probability least 6. The pseudo-code for MDP-NaS is given in Algorithm 1.
w (M). We
Algorithm 1: MDP Navigate and Stop (MDP-NaS)
Input:
Confidence level 6, ERGODIC boolean variable, communication parameter m or an upper bound.
ERGODIC then
Set (ct))21 (1/V0)/21
else
Set (Et)121 = (t m+r 121
5 end
Set & < and (ta + for all (s,a).
Initialize empirical estimate Mo by drawing an arbitrary MDP from M.
8 Compute पे < POLICY-ITERATION,
while Stopping condition (13) is not satisfied do
Compute w² (MM) according to (7) and x (M.) according (8).
10
11
if 0 then
12
Play dp ~ Uni
13
else
14
Play de ~ (T())s)), where m, is determined by either (9) or (10).
15
end
16
Observe (Re, ~ ((-18,, a.) @ p(11s,, a.). + 1.
18
Update M, and (N (t))
Compute रे < POLICY+ITERATIONN...)
end Output: Empirical optimal policy न.
4.1 Sampling rule
We introduce few definitions simplify the presentation, Any stationary policy i induces a Markov chain on Z whose transition kernel is defined by Ps ((s, a), (s', a²)) - P(s'ls, (a')() With some abuse of notation, we will use P. to refer to both the Markov chain and its kernel. We denote by Tu the uniform random policy, i.e., T. (als)) 1/A for all pairs (s, a). Finally, we define the vector of visit-frequencies N (1)/t 2 (t)
In contrast with pure exploration in Aimti-Armed Bandits and MDPs with a generative model where any allocation vector in the simplex is achievable, here the agent can only choose sequence of actions and follow the resulting trajectory. Therefore, one might ask if the oracle allocation can be achieved by following simple policy. A natural candidate is the oracle policy defined by
v(s,a) E 2,
x (als)
W
W
(8)
ΣLEA w
It is immediate to check that wt is the stationary distribution of P.o. Denote by x the above oracle policy defined through " (MM. Policy (MM) 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 (1)/t converges w (M). The following two sampling rules satisfy these requirements.

---

D-Navigation rule: At time step t, the learner plays the policy
at = Tu + (1 Ex) (Me);
(9)
C-Navigation rule: At time step t, the learner plays
my = E + (1 Et)
Σ n (M,,)/ 1=1
(10)
where is decreasing exploration rate to be tuned later. In the second case, the agent navigates using a Cesàro-mean oracle policies instead of the current estimate of the oracle policy, which makes the navigation more stable.
4.1.1 Tuning the forced exploration parameter
The mixture with the uniform policy' helps the agent to explore all state-action pairs often enough in the initial phase. This particularly necessary in the case where the empirical weight win (Mr) 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 E, that ensures 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 M: m - max(s,)))Es= min 2 1 3x S + A, P 8') > 0}. Then C-Navigation or D-Navigation with any decreasing sequence (ex)e21 such that 4I 1, E L m41
satisfies: P P.M (v((,, a) Z, lim Nta(t) = =0)==
Remark 3. When the parameter m is unknown to the learner, one can replace it by its worst case value Myaax S 1. However, when prior knowledge is available, using faster- decreasin sequence & = t w.. instead of can be useful to accelerate convergence, especially when the stutes of M are densely connected (m & S 1).
Minimal exploration rate: Communicating MDPs. The forced exploration rate -ー vanishes quite slowly. One may wonder if this rate is necessary to guarantee sufficient exploration in com- municating MDPs: the answer is yes in the worst case, as the following example shows. Consider variant of the classical RiverSwim MDP with state (resp. action) space S [|1, (resp. A = {LEFTI, LEFT2, RIGHT)). LEFTI and LEFT2 are equivalent actions inducing the same re- wards and transitions. After playing RIGHT the agent makes a transition of one step the right, while playing LEFTI (or LEFT2) moves the agent all the way back to state 1. The rewards are null everywhere but in states S) where R(1, LEFTI). LEFT2) are equal to 0.01 almost surely and R(S, RIGHT) is Bernoulli with mean 0.02.
When y is close 1, the optimal policy consists in always playing RIGHT as to reach state S and stay there indefinitely. Now suppose that the agent starts at 8 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 (LEFTI, LEFT2). Under this scenario she ends up playing sequence of policies that scales like मe 22, + (1 (LEFTI + LEFT2)/2 This induces the non- non-homoggenous Markov Chain depicted in Figure For the exploration rate E = t- we show that if the agent uses any a > S-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 8. The proof is deferred to Appendix D.
Minimal exploration rate: Ergodic MDPs. For such MDPs, we can select E, 1/ta where < without compromising the conclusion of Lemma 4. The proof is deferred to Appendix D.
4.2 Stopping rule
To implement GLR test, define (Me(t), the likelihood of the observations under some MDP M' < M: (t)
II (1pp)((5411 ax) (M) (Rylsk, ax), where step k the algorithm is in
Our results still hold mu is replaced by any other policy и which has an ergodic kernel. practice, this can helpful especially when we have prior knowledge of fast-mixing policy w. Modulo re-scaling of e, by constant factor of 1/2.
7

---

-
E7
Et
S
1
Et
Figure I: Non-homogeneous Markov Chain. An exploration rate of at least t s-1 is needed.
state sg. plays action a₃ and observes the reward Rx and 8k+1 (the next state). Performing a GLR test in step consists in computing the optimal policy मे for the estimated MDP MM, and in comparing the likelihood of observations under the most likely model where मे optimal to the likelihood under the most likely model where मद is sub-optimal. Following the standardized form of the GLR for multi-armed bandits in [DKM19] we write:
sup EII
(()
(, (t)
inf log LM, (t)
G (t) log
log sup MrEAh(M)
sup M (MM)
(M)
(M.(t) MrEAR(M.)
(t
inf
Σ
as) KL(Faa(t), (s, (11)
McEAl(Ma) M (s,a)
=t (,,N(())))
(12)
The hypothesis (5) # TT) is then rejected as soon as the ratio of likelihoods becomes greater than the threshold ((1, 6). properly tuned to ensure that the algorithm is 8-PC. Note that the likelihood ratio Gæ; (1) 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 the following proposition:
Proposition 5. Define the random thresholds for the transitions and rewards respectively:
() log(1/5) -1-1) E log (e[1+ Nna( 11]]
(8,0)
(,( A SA (log(((10/////55 (16))/SA) + > log [1 + log (1))
s,a
where xpx) x + log(x) is defined in the appendix. Then the stopping rule:
T4 f inf t t 1: (M.,,
(13)
8-PC, i.e., P(T8 < xc, 2; + = 5
Main results and sample complexity analysis
First state our main results, which take the form of asymptotic upper bounds the sample complexity of MDP-NaS, under slightly more conservative exploration rate than in Lemma Then 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 e Rmiry and the stopping rule (13): (i) MDP-Nab NaS stops almost surely and its stopping time satisfies
B[Ts] P lim sups-so log(i/o; S (M)) 1, where U,(M) was defined in (6);
(ii) the stopping time of MDP-NaS has a finite expectation for all (0, 1), and
lim sups-p-00 log(1/0] S (M).
8

---

5.1 Proof sketch
Concentration of empirical MDPs: The starting point of our proof is a concentration event
of the empirical estimates MM, around M. For & 0 and T 2 1, we define (E)
NErr (I MMl s < ( - T s where
||-II is semi-norn on MDPs.
Then we prove in Lemma 18 that (E) holds with high probability in the sense that for all T 2 1:
(()(()) 21 11 -1-0(1/T²)
(14)
For this purpose we derive, for all pairs (s, a), a lower bound on Naa stating that": P(V(s, a) E 2, VI 2 1, (1) 2 (1/A.)2/4 - 1) 2 1 1 a where Xa x log (1g"(1= + SA/a) is a
parameter that depends on the mixing properties of M under the uniform policy. These lower bounds on (!) 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. Pr., is aperiodic
Under Assumptions and 2 the kernel P..., and consequently also Pro,, becomes ergodic. Hence the iterates of Pa converge to (MM) 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 (Pr))22 that 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-Carke (MCMC) algorithms to get the following result.
Theorem 7. Using the C-Navigation or D-Navigation we have: lim N(t)/t = (MM almost surely.
Lemma 4 and Theorem 7 combined prove Theorem 6 (i) in a straightforward fashion. The proof of Theorem 6 (fi) is more involved. Again, we adapt the proof method from [FMP11] to derive finite-time version of Proposition 12 which results into the following proposition.
Proposition 8. Under C-Navigation, for all >> O, there exists time Tę such that for all T 2 Te. all t 2 T3/4 and all functions f Z + R+, we have:
Ekmn f(kk ax)
Bya,a)nw- [[(s, a)] 2 Kg I1
< 2exp (- (-152).
t.
where & + Kg is a mapping with values in (1) such that simpupp-o Kg < oc.
< Ke E). Then Proposition 8 and Eq. (14) combined imply that for T large enough, the event (+) n (E) holds w.h.p. so that the expected stopping time is finite on the complementary event: E[ [ (E) < co. Now given the 2 L/o), we may informally
Now define CE = NT (NN())ttww(l
asymptotic shape of the thresholds: (t, + Bp(t,
8-50
write:
E 1 (Ct(E) (((()))((()
3 (1g(
sup (M'
U,(M'uu')
8-0
where B& ((M' IMM -M] < E, ||'' w (M)ll S Kg G.. Taking the limits when d and & go to zero respectively concludes the proof.
Using the method in our proof one can derive a lower bound of the type for any < < 1/2 and any 1 and Ç = 1/4 because they enable us exploration rate e, = - with < 1/(m 1mm+1 1). We chose 0 2(m+1) have an explicit formula for A., See Lemma 11 in the appendix. Thiis assumption is mild as it is enough to have only one state 3 and one action à such that (3 ā) > 0 for it to be satisfied, Furthermore, Assumptions and 2 combined are still less restrictive than the usual ergodicity assumption, which requires that the Markov chains of all policies are ergodic.

---

6 Comparison with MOCA
Recall from Lemma 3 and Theorem 6 that our sample complexity bound writes as:
o
1 + Varp(s.a) [V
inf max WED(M) (s,a)=ap/""( (+)
minw (a) 4 min 7)3 log(1/0).
Wsa
Hence, in the asymptotic regime 8 + O, MDP-NaS finds the optimal way to balance exploration between state-action pairs proportionally to their hardness: (1+ Varp(s.a) [V)l// A for sub-optimal pairs (resp. 1/4 (1 - -)² 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 s-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, ie when E < e+'l_ in the asymptotic regime ò - O. In this case, by carefully inspecting the proofs of [WSJ21], we see that MOCA's sample complexity writes 22:
H
log(1/5) polylog(S, A, H, log(e")) log (1/8)
max WEDIMM s,aदém (s) Wsa (aa(Waaaaa,.a (h) (h)²
inf
Am
where H is the horizon and Asa(h) is the sub-optimality gap of (8, 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 A Instead, MDP-NaS pays a double worst-case cost corresponding state min
s,ay(n((s)
of the smallest visitation probability multiplied by the minimum gap min, (s) A min As pointed out by [WSJ21] the former scaling is better, especially when the state where the minimum gap is achieved different from the one that 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 remove this double worst-case dependency.
2. The sample complexity of MOCA divided by log(1/6) still explodes when d goes to zero, contrary to MDP-NaS's s bound.
3. The sample complexity of MDP-NaS is variance- seriaice-sensitvee for sub-optimal state-action pairs, while MOCA's bound depends on a worst-case factor of H², Indeed as the rewards are in
[0, 1]. we always have VM= S H and Varp(s.a) [VM] H² in the episodic setting.
We conclude this section by noting that MDP-NaS has a simple design and can easily implemented.
Conclusion
To the best of our knowledge, this paper is the first to propose algorithm with instance-dependen 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 Mulli-Armed Bandits and MDPs with a generative model. 2) That, provided access an optimization oracle that solves the noommation-thorretiio lower bound (resp. some convex relaxation of the lower bound), asymptotic optimal (resp. metrmol 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 the problem of finding s-optimal policy, which is of more practical interest than identifying the best policy.
"!g* is defined in their work the threshold value for such that the only s-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 e without prior knowledge of the ground truth instance.
The (1/8) term comes from the sample complexity of their sub-routine FINDEXPI.OR CWAPPOORRBBBLSSA..S BETS.
10

---

Broader Impact
This paper tries advance our theoretical understanding of the sample complexity of finding 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 wider broader impact discussion is not applicable.
A Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers whose comments and questions helped improve the clarity of this manuseript. 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' d'venr (ANR-16 IDEX-0005), and Chaire SeQ (ANR-20-CHIA-0022)
References
[AHKS20]
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. In H. Larochelle, M. Ran- zato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 13399-13412. Curran Associates, Inc., 2020.
[AJO09]
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2009.
[AKY20]
Alekh Agarwal, Sham Kakade, and Lin Yang. Model-based reinforcement learning with generative model is minimax optimal. volume 125 of Proceedings of Machine Learning Research, pages 67-83. PMLR, 09-12 Jul 2020.
[AMK13]
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91(3):225-34) 2013.
[BK97]
Apostolos N. Burnetas and Michael N. Katehakis. Optimal adaptive policies for markov decision processes. Mathematics of Operations Research, 22(1):222-22 1997.
[CT06]
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, USA, 2006.
[DKM19]
Rémy Degenne, Wouter M. Koolen, and Pierre Ménard. Non-asymptotic pure explo- ration by solving games. NeurlPS, 2019.
[DMKV21]
O. D. Domingues, Pierre M' enard, E. Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In ALT, 2021.
[DTC13] Thomas Dietterich, Majid Taleghan, and Mark Crowley. Pac optimal planning for invasive species management: : Improved exploration for reinforcement learning from simulator-defined mdps. 01 2013.
[EDMM06] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7:1079-1100 1105, 06 2006.
[FCG10]
Sarah Filippi, Olivier Cappé, and Aurélien Garivier. Optimism in reinforcement learning and kullback-leibler divergence. Allerton Conference on Communication, Control, and Computing, pages 115-122, Sep. 2010.
[Fie94]
C. Fiechter. Efficient reinforcement learning. In COLT '94, 1994.
[FMP11]
G. Fort, É. Moulines, and P. Priouret. Convergence of adaptive and interacting markov chain monte carlo algorithms. Annals of Statistics, 39:3262-3289, 2011.
[FYAY21]
Fei Feng, W. Yin, Alekh Agarwal, and Lin F. Yang. Provably correct optimization and exploration with non-linear policies. ArXiv, abs/2103. 11559, 2021.

---

[GK16]
Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learn- ing Research, pages 998-1027, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR.
[GK19] A. Garivier and Emilie Kaufmann. Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models. arXiv preprint, Statistics Theory, 1905, .0..000395222 2019.
[HH80)
Hall and C.C. Heyde. inequalities and laws of large numbers. In Hall and C.C. Heyde, editors, Martingale Limit Theory and its Application, Probability and Mathematical Statistics: A Series of Monographs and Textbooks, pages 13-50. Academic Press, 1980.
[JKM+20] 20] Anders Jonsson, Emilie Kaufmann, Pierre Menard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1253-1263. Curran Associates, Inc., 2020.
[Kak03]
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of London, England, 2003.
[KCG16]
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best- arm identification multi- bandit models. The Journal of Machine Learning Research, 17(1):1 -42 2016.
[KK18]
Emilie Kaufmann and Wouter M. Koolen. Mixture martingales revisited with applica- tions to sequential tests and confidence intervals. arXiv preprint, 1.1i::8111111411 2018.
[KMDD+21] Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Vitaly Feld- man, Katrina Ligett, and Sivan Sabato, editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 865-891. PMLR, 16-19 Mar 2021.
[KMN99]
Michael Kearns, Yishay Mansour, and Andrew Y. Ng. A sparse sampling algorithm for oparmoptimal planning in large markov decision processes. In Proceedings of the 16th International Joint Conference on Artificial Intelligence Volume IJCAI'99, page 1324-1331, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.
[KS98]
Michael Kearns and Satinder Singh. Finite-sample convergence rates for g-learning and indirect algorithms. In Proceedings of the 11th International Conference Neural Information Processing Systems, NIPS'98, page 19621002,00 Cambridge, MA, USA, 1998. MIT Press.
[LCC+21] Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejie Chi. Is q-learning minimax optimal? a tight sample complexity analysis, 2021.
(LPW06] David A. Levin, Yuval Peres, and Elizabeth I.. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006.
[LR85]
T.I. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):42,, 1985.
[LS20]
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[LWC+200]
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model- reinforcement learning with generative model. arXiv preprint, arXiv:2005.1 120000059999.,... 2020.
[LWC+220b] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learing: Sharper analysis and variance reduction, 2020.
[MD]+20] Pierre M' Wenard, O. D. Domingues, Anders Jonsson, E. Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. ArXiv, abs/2007. 13442, 2020.
12

---

[MP21]
Aymen Al Marjani and Alexandre Proutiere. Adaptive sampling for best policy identification in markov decision processes. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 7459-7468. PMLR, 18-24 Jul 2021.
[Rus16]
D. Russo. Simple bayesian algorithms for best arm identification. In Proceedings of the 29th Conference On Learning Theory, 2016.
[SB18]
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[Sch68]
Schweitzer. Perturbation theory and finite markov chains. Journal of Applied Probability, 5:401-413 1968.
[SL08]
Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 309-31100- 2008.
[SWW+18] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances Neural Information Processing Systems 31, pages 5186-5196. Curran Associates, Inc., 2018.
[Sze10]
Csaba Szepesvari. Algorithms for Reinforcement Learning. Morgan and Claypool Publishers, 2010.
[Wan17]
Mengdi Wang. Randomized Linear Programming Solves the Discounted Markov Decision Problem Dearly-Linear (Sometimes Sublinear) Running Time. arXiv é-prints, page 100.00 869, April 2017.
[WSJ21] Andrew Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond No Re- gret: Instance--eepnndent PAC Reinforcement Learning. arXiv e-prints, page arXiv:2108.02711, August 2021.
[ZCA21] Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. ArXiv, 1 2021.
[2KB19]
Andrea Zanette, Mykel Kochenderfer, and Emma Brunskill. Almost horizon-free structure-aware best policy identification with a generative model. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 5625-5634. Curran Associates, Inc., 2019.
13


Reviews:
[{"review_id": "wwAFTUzcoWD", "reviewer": "Reviewer_rSqS", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### originality\nThe paper is original for discussing BPI. \n\n### quality\nThe paper is generally of good quality for having consistent setting and explanations. \n\n### clarity\nThe paper is well written and easy to follow. \n\n### significance\nThe paper is significant on the theory side, but I am not quite sure how the results can be applied. \n\n### minor issues\n\n1. Can the author also compare with Dong, Kefan, et al. ?\n\n2. typo: line 80 \\gamma \\in (0, 1]\n\nDong, Kefan, et al. \"Q-learning with ucb exploration is sample efficient for infinite-horizon mdp.\" arXiv preprint arXiv:1901.09311 (2019).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "eswqlUBoHPA", "reviewer": "Reviewer_ewHn", "summary": "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. \n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is heavily theoretical. I find the topic interesting and relevant but had difficulties following the results. Part of this that this style of PAC analysis is not my area of expertise, but I think the authors could have been a bit clearer in their writing.\n\nOn a high level, they could motivate the need to deal with an online setting (rather than a generative/episodic setting a bit better). In particular, assuming an online setting will typically mean the agent will be interacting with the real environment. In such a setting, it seems to be that it is crucial to ensure safety of the learning process, and this paper doesn't discuss that at all. For example, I think works like [1] could be mentioned and a more clear motivation about the setting and problem would be worth it here.\n\nIn terms of the technical presentation, I think there's a lot of room for improvement, the paper assumes a whole lot of background knowledge. Some points that could be clarified:\n\n* Is the term \"navigation constraints\" used in the literature? It is used in the abstract but not defined, and I could only understand what it meant after reading the paper further and understanding the setup. I think its meaning should be spelled out to the reader earlier.\n\n* PAC acronym is undefined\n\n* The authors mention the minimax framework but don't say what it is\n\n* What is the difference between a generative setting and an episodic one? I don't find the term generative very intuitive...\n\n* I don't think sigma in line 92 is defined\n\n* I don't get the condition in line 114 for M << M'. If p(.|s,a) and p'(.|s,a) are two distributions over S, what does it mean for one to be << the other?\n\nMinor:\nLine 237 uses \"pretty slowly\", which is pretty informal for a research paper.\n\n\n[1] Turchetta, M., Berkenkamp, F. and Krause, A., 2016. Safe exploration in finite markov decision processes with gaussian processes. Advances in Neural Information Processing Systems, 29, pp.4312-4320.\n\nPOST RESPONSE\nAfter reading the other reviews and rebuttals, my feeling is that the paper needs a bit more work to iron out some kinks and make its main messages clearer. I encourage the authors to do so.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A brief discussion on limitation is provided in te Conclusions. Societal Impacts are not mentioned.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "btuy2yy5la8", "reviewer": "Reviewer_yb3J", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- (Organization) I had some troubles in reading the appendix, particularly when looking for the proofs of the results presented in the main paper. I couldn't find the proof of Proposition 4. I understand that it is a quite direct extension of Proposition 1 of [1], but I suggest stating it clearly, to avoid confusion. Moreover, I couldn't find the proof of Corollary 1 and Proposition 7.\n- (About the upper bound to the lower bound sample complexity) The authors derive the lower bound to the sample complexity in Proposition 3, whose computation requires the solution of a non-convex optimization problem. Lemma 5 provides an upper bound to the sample complexity of Proposition 5, that can be solved with convex optimization. Therefore, I believe that the sample complexity of Lemma 5 is *not* a lower bound to the sample complexity of the problem. I suggest stating it clearly, because, in some sentences, I perceived some confusion. For instance, in the abstract, the authors refer to \"relaxed lower bound\" whose meaning is unclear to me.\n- I read the appendix only partially\n\n***Minor*** \n- line 80: ([0,1) - > [0,1)\n- line 92: (ii) A - > (ii) a\n- Line 186: Shouldn't that be an argmin?\n- Line 195: too many closed paranthesis\n\n\n***Overall***\nThe paper represents an interesting contribution to the theoretical understanding of the BPI problem in a more realistic setting compared with the generative model setting. The derivation of the lower bound seems a quite direct extension of [1]. Instead, the algorithm is novel. Therefore, I am inclined towards acceptance.\n\n\n[1] Al Marjani, Aymen, and Alexandre Proutiere. \"Adaptive sampling for best policy identification in Markov decision processes.\" In International Conference on Machine Learning, pp. 7459-7468. PMLR, 2021.\n\n\n***Post Discussion***\nI thank the authors for the feedback. I have read the reviews and the authors' responses. I still think that the paper addresses a relevant problem and that the proposed solution and corresponding analysis are interesting. I agree on the limitations about the asymptotic-regime bound and the forced exploration, although I think they are not a decisive factor. Nevertheless, I agree that the paper needs a quite deep revision to highlight the contributions, technical novelties, and results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper, I do not forsee any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Z21co3Jqz5p", "reviewer": "Reviewer_1sx6", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Significance, novelty, and relevance\n---\n\nThe paper considers a relevant problem. I found this contribution interesting and significant. To my knowledge, this is the first work to provide problem-dependent sample complexity bounds for BPI in the online setting (i.e., without generative model). In particular, I appreciated the authors' efforts in describing the main complications that arise in the online setting (e.g., how to handle the navigation constraints).\n\nSoundness of the claims\n---\n\nAll claims seem sound, though I did not check all proofs in detail.\n\n\nRelation with prior work\n---\n\nRelevant prior works are discussed. The paper could also mention recent works on asymptotically-optimal algorithms for pure-exploration/regret-minimization in bandits which remove the need for forced exploration and for oracles for computing the lower bound (see detailed comments below).\n\n\nClarity of writing\n---\n\nThe first part of the paper is very well-written, while I found Sec. 4 quite hard to follow. I think the main issue is that the proposed algorithm is only briefly sketched in few lines of text, while no detailed pseudo-code is provided. This made it hard for me to understand what algorithm is actually analyzed (see also detailed comments below). Then, the section tries to explain the algorithm's components in detail, though, again, these are slightly difficult to understand since no reference pseudo-code is provided.\n\n\nDetailed comments/questions\n---\n\nI have two major concerns about this work:\n\n1. Only an asymptotic sample complexity bound is provided for the proposed algorithm. This, in my view, has two main limitations. (1) Having only an asymptotic result might be of limited significance since it might not describe well the behavior of an algorithm in the moderate-confidence setting, which is typically used in practice. (2) An asymptotic bound is typically quite \"implicit\". Hiding low-order (in log(1/delta)) terms makes it hard to understand the role played by each component in determining the final sample complexity. Please note that I am not advocating against asymptotic optimality. I think it is very good to have an algorithm that is asymptotically optimal, but I also think that the asymptotic result should be a special case of an explicit sample-complexity bound for the moderate-confidence setting which clearly shows the impact of each component.\n\n2. The proposed algorithm uses forced exploration to guarantee a minimum level of estimation accuracy for the true underlying MDP. While forced exploration is a simple trick to guarantee asymptotic optimality for this kind of algorithms, even in the simpler MAB case it is known that when facing \"hard instances\" in the moderate-confidence setting the actual sample complexity observed in practice might be significantly affected (if not dominated) by forced-exploration (I think [1] provides examples of this). I believe this might be even amplified in MDPs, where there might be states that are very hard to reach with a uniform policy (which I guess partially explains the very slow theoretical rate for decaying forced exploration). Recent papers on building algorithms from lower bounds in the bandit literature removed the need for forced exploration by using confidence-intervals/optimism, see e.g. [1,2,3] for pure exploration and [4,5,6] for regret minimization. I think the proposed algorithm would significantly benefit from adopting such techniques.\n\nOther comments:\n\n3. I believe the assumption of unique optimal policy might be quite restrictive in the MDP setting. Is the assumption needed only for the analysis of the algorithm or also for the derivation of the lower bound? Any intuition on how to remove it?\n\n4. The last paragraph of Sec. 3 mentions that a projected gradient-descent algorithm is used to compute the optimal allocation, while from Sec. 4 it seems that the algorithm has access to an oracle providing the optimal allocation for the empirical MDP at each time step. Which one is used in the algorithm and in its analysis?\n\n5. While the algorithm design and analysis for the online setting is novel, it is also true that the paper builds on top of the recent work [7]. It would be good to clearly describe, at a technical level, how the two contributions differ (e.g., what components of the algorithm are similar/different, where the analysis is similar/different, etc.)\n\n6. What policy does the \\mu_min of Corollary 1 refer to? Also, do you think that the minimum state-action visitation probability of some policy really affects the sample complexity or that might be an artifact of the upper bound derived there and in Lemma 5?\n\n7. Why is the sample complexity derived in Theorem 8 optimal only up to a factor of 2? Is it because two concentration inequalities are used in the analysis of the GLR test (one for p and one for q)? Any idea how to reduce that factor to 1?\n\nMinor:\n\n- Line 58: MDPs -> MDP\n- Line 95: Acronym \\delta-PC not introduced \n- Line 114: do you need also absolute continuity of the reward kernels?\n- Line 211: remove \"a\"\n- Eq.(13): is there no dependence on \\xi in the rhs?\n\n[1] Degenne, Rémy, Wouter M. Koolen, and Pierre Ménard. \"Non-asymptotic pure exploration by solving games.\" NeurIPS (2019).\n[2] Degenne, Rémy, et al. \"Gamification of pure exploration for linear bandits.\" International Conference on Machine Learning. PMLR, 2020.\n[3] Zaki, Mohammadi, Avi Mohan, and Aditya Gopalan. \"Explicit best arm identification in linear bandits using no-regret learners.\" arXiv preprint arXiv:2006.07562 (2020).\n[4] Degenne, Rémy, Han Shao, and Wouter Koolen. \"Structure adaptive algorithms for stochastic bandits.\" International Conference on Machine Learning. PMLR, 2020.\n[5] Tirinzoni, Andrea, et al. \"An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits.\" NeurIPS (2020).\n[6] Kirschner, Johannes, et al. \"Asymptotically Optimal Information-Directed Sampling.\" arXiv preprint arXiv:2011.05944 (2020).\n[7] Marjani, Aymen Al, and Alexandre Proutiere. \"Adaptive sampling for best policy identification in Markov decision processes.\" arXiv preprint arXiv:2009.13405 (2020).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations of their algorithm and leave their solution to future work. I do not see any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "LdPXji-8meM", "reviewer": "Reviewer_Vy8C", "summary": "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.\nIts main contributions are:\n\n(i)  A problem-dependent lower bound on the sample complexity that takes into account navigation constraints;\n\n(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;\n\n(iii) An algorithm whose upper bound matches the relaxed lower bound up to a factor 2.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe paper studies a significant problem in reinforcement learning: the one of deriving sample complexity bounds and algorithms for best policy identification that work in an online setting and that are able to adapt to the structure of the MDP. It extends the results of [MP20] to the online setting.\n\nWith respect to the assumptions and the algorithm, I found the limitations below: \n\n(1)  It is assumed that the MDP has a single optimal policy, which is quite strong.\n\n(2)  The proposed algorithm relies on forced exploration based on a mixture with a uniformly random policy, and knowledge about the MDP structure is required to determine the optimal exploration rate. Without such knowledge, we must either use a very conservative rate, or rely on heuristics, or make the stronger assumption that the MDP is ergodic to use a minimal exploration rate.\n\n(3)  Replacing the non-convex optimization problem by a convex relaxation is a very interesting approach, however, it leaves open the question of whether the “true” lower bound can be matched. If we assume that we have an oracle that gives the solution to the non-convex problem, would the same algorithm match the lower bound?  If so, it might be nice to add this remark in the paper. \n\nAlso, I believe that the paper has some points to be improved with respect to the presentation and discussion:\n\n(i) It would be interesting to include a more detailed discussion about what are the main theoretical and algorithmic challenges that arise in the online setting, when compared to the generative setting studied by [MP20]. For instance, the lower bound seems to follow almost directly from the one in [MP20] and I think the challenges to derive the algorithm could be better explained.\n\n(ii) It would be helpful to include a short description of the algorithm. In the current version, the description of the algorithm is mixed with theoretical results and discussion in Section 4.\n\n(iii) In the experiments (Table 2), it seems that the empirical sample complexity of MDP-NaS is compared to an upper bound on the sample complexity of VRQL. However, it is possible that VRQL achieves the optimal policy with fewer samples than what is stated by the upper bound. I understand that this was done to compensate for the fact that VRQL has no stopping rule, but it would be interesting to see how many samples are actually required by VRQL to achieve the optimal policy in the MDPs that were tested. It might also be interesting to compare the algorithm to other BPI algorithms such as BPI-UCRL [KMDD+21].\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Since this is a theoretical work, I believe there are no societal impacts to be addressed.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although the scores for this paper make it a borderline case, after the discussion it seems that the only remaining issue is that the paper does not highlight better the contributions, technical novelties, and results. Further, the description of the algorithm was considered to be improvable. I think that these points should be manageable when preparing the final version, so that I recommend to accept the paper. The authors are expected to revise the paper taking into account the reviewers's comments and in particular paying attention to the points mentioned above.
Decision: Accept (Poster)