Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

main_review: 
The 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.

With respect to the assumptions and the algorithm, I found the limitations below: 

(1)  It is assumed that the MDP has a single optimal policy, which is quite strong.

(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.

(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. 

Also, I believe that the paper has some points to be improved with respect to the presentation and discussion:

(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.

(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.

(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].

limitations_and_societal_impact: Since this is a theoretical work, I believe there are no societal impacts to be addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.
- (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.
- I read the appendix only partially

***Minor*** 
- line 80: ([0,1) - > [0,1)
- line 92: (ii) A - > (ii) a
- Line 186: Shouldn't that be an argmin?
- Line 195: too many closed paranthesis


***Overall***
The 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.


[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.


***Post Discussion***
I 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.
limitations_and_societal_impact: This is a theoretical paper, I do not forsee any societal impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

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.

On 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.

In 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:

* 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.

* PAC acronym is undefined

* The authors mention the minimax framework but don't say what it is

* What is the difference between a generative setting and an episodic one? I don't find the term generative very intuitive...

* I don't think sigma in line 92 is defined

* 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?

Minor:
Line 237 uses "pretty slowly", which is pretty informal for a research paper.


[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.

POST RESPONSE
After 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.
limitations_and_societal_impact: A brief discussion on limitation is provided in te Conclusions. Societal Impacts are not mentioned.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: ### originality
The paper is original for discussing BPI. 

### quality
The paper is generally of good quality for having consistent setting and explanations. 

### clarity
The paper is well written and easy to follow. 

### significance
The paper is significant on the theory side, but I am not quite sure how the results can be applied. 

### minor issues

1. Can the author also compare with Dong, Kefan, et al. ?

2. typo: line 80 \gamma \in (0, 1]

Dong, Kefan, et al. "Q-learning with ucb exploration is sample efficient for infinite-horizon mdp." arXiv preprint arXiv:1901.09311 (2019).

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Significance, novelty, and relevance
---

The 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).

Soundness of the claims
---

All claims seem sound, though I did not check all proofs in detail.


Relation with prior work
---

Relevant 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).


Clarity of writing
---

The 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.


Detailed comments/questions
---

I have two major concerns about this work:

1. 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.

2. 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.

Other comments:

3. 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?

4. 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?

5. 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.)

6. 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?

7. 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?

Minor:

- Line 58: MDPs -> MDP
- Line 95: Acronym \delta-PC not introduced 
- Line 114: do you need also absolute continuity of the reward kernels?
- Line 211: remove "a"
- Eq.(13): is there no dependence on \xi in the rhs?

[1] Degenne, Rémy, Wouter M. Koolen, and Pierre Ménard. "Non-asymptotic pure exploration by solving games." NeurIPS (2019).
[2] Degenne, Rémy, et al. "Gamification of pure exploration for linear bandits." International Conference on Machine Learning. PMLR, 2020.
[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).
[4] Degenne, Rémy, Han Shao, and Wouter Koolen. "Structure adaptive algorithms for stochastic bandits." International Conference on Machine Learning. PMLR, 2020.
[5] Tirinzoni, Andrea, et al. "An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits." NeurIPS (2020).
[6] Kirschner, Johannes, et al. "Asymptotically Optimal Information-Directed Sampling." arXiv preprint arXiv:2011.05944 (2020).
[7] Marjani, Aymen Al, and Alexandre Proutiere. "Adaptive sampling for best policy identification in Markov decision processes." arXiv preprint arXiv:2009.13405 (2020).
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_title: null

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)