Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work studies the problem of learning stochastic discounted infinite-horizon Markov Decision Processes (MDPs) with unknown transition. The authors propose an algorithm UCBVI-gamma based on recent advances in episodic MDPs (e.g. Azar et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019) and specifically the Bernstein-type exploration bonus. Besides, the authors provide a lower bound which indicates that UCBVI-gamma matches the minimax lower bound up to logarithmic factors. 
main_review: 1. Contribution

In this work, the authors propose the model-based algorithm UCBVI-gamma which achieves O(sqrt(SAT)/ (1-gamma)^1.5) regret, which matches the lower bound on the expected regret O(sqrt(SAT)/(1-gamma)^1.5). This is the first algorithm that matches the lower bound. The algorithm design is inspired from UCBVI-BF of Azar et al. (2017), which adopts a specific Bernstein-type exploration bonus. 

On the other hand, although based on the hard two-state instance of Liu and Su (2020), the proof of the lower bound in Theorem 4.4 is novel and inspiring.  

2. Weaknesses

The proving techniques and algorithm design of the upper bound are quite similar to that of previous works such as Azar et al. (2017) for UCBVI-BF. I am willing to reconsider my score if the authors could emphasize their own technical contributions in the proof of the upper bound. 

Besides, the third term in Theorem 4.2 and the decomposition of Eq (5.1) would benefit from more high-level explanations.

3. Writing Issues

line 262-336, the format of reference seems incorrect. It should not be numbered. 

limitations_and_societal_impact: This work is pure theoretical and does not have any potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new model-based algorithm for tabular MDPs, and proves a upper bound and a lower bound on regret. 
main_review: Pros:
The newly proposed algorithm enriches the collection of model-based algorithms. The power of $T$ in the upper bound on regret is decreased to 0.5 by this paper.

Cons: 
In Section 6, it says "There is still a gap between the upper and lower bounds when $T\leq\max\{S^3A/(1-\gamma)^4,SA/(1-\gamma)\}$." But Theorem 4.2 and Theorem 4.4 respectively require $T\geq S^3A^2/(1-\gamma)^4$ and $T\geq SA/(1-\gamma)^4$. Hence only when $T\geq S^3A^2/(1-\gamma)^4$, the upper bound matches the lower bound. In this case, where does $T\leq\max\{S^3A/(1-\gamma)^4,SA/(1-\gamma)\}$ in Section 6 come from? Furthermore, how restrictive is this condition on $T$? There seems no discussion about this in the paper.

I've read the authors' response and updated my score accordingly. 
limitations_and_societal_impact: This paper focuses on theoretical analysis. It's expected that the paper does not have direct negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper closes the gap betewwn upper and lower bounds for regret of tabular discounted MDPs. In particular, it proposes UCBVI-$\gamma$ algorithm that achieves regret of $\widetilde{O}\left(\frac{\sqrt{SAT}}{(1-\gamma)^{1.5}}\right)$ and constructs a class of hard MDPs such that any algorithm will have expected regret at least $\widetilde{\Omega}\left(\frac{\sqrt{SAT}}{(1-\gamma)^{1.5}}\right)$.
main_review: Overall, although the techniques used do not seem to be very novel, I consider the results of this paper as a significant progress on tabular disconted MDPs. Meanwhile, the writing of this paper is also clear and easy to follow.

Questions:
- On page 9, how you show that $$\mathbb{E}\left[\sum_{i=K+1}^{T_j}V^*(X_{j, i})-\frac{r(X_{j, i}, A_{j, i})}{1-\gamma}\mid T_j>K\right]\geq -T,$$ or more specifically, $V^*(X_{j, i})-\frac{r(X_{j, i}, A_{j, i})}{1-\gamma}\geq -1$?

---

Good paper. Score remains the same after rebuttal.
limitations_and_societal_impact: The authors adequately addressed the limitation of their work in Section 6 by pointing out the requirement on $T$ for their algorithm to be nearly optimal. The potential negative social impact is not addressed, which is not so needed for a purely theoretical analysis on tabular MDPs.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study the problem of learning a discounted tabular-MDP. They adopt a notion of regret that is closely related to policy identification problem.

The authors make two main contributions:
1. They show how to adapt UCBVI to discounted MDP. This lead to an algorithm called UCBVI-\gamma algorithm. This model-based algorithm uses OFU principle by computing Bernstein-type bonus for empirical Q-function. The policy of the algorithm is updated every time step (online algorithm).  The author prove that its regret is upper bounded by \tilde{O}(\sqrt{SAT}/(1-\gamma)^1.5) where \gamma is the discount factor.

2. The authors also derive a minimax lower bound for the problem that essentially match the upper bound of the algorithm {\Omega}(\sqrt{SAT}/(1-\gamma)^1.5). This shows that their algorithm is minimax-optimal.

main_review: In summary, I found that the main result is strong but the paper is a bit incremental. I find the result strong because compared to previous work, the paper closes the gap between the lower and upper bound for discounted MDPs (more precisely, the the order of the two bounds provided are the same up to logarithmic factors and [huge] constants). That being said, the algorithm to obtain the upper bound is essentially a variant of UCBVI. I found the counter-example for the lower bound more original.

The definition of the regret seems adapted for disconted MDP. It is the sum over time steps of the differences between the optimal expected return of an optimal policy and the expected return of the computed policy, both at current states. As indicated it is closely related to policy identification but only for those states. I am wondering if it make sense as those states might not be representative of the whole MDP. Would it make sense to restart the MDP from time to time (for instance after a geometrically distributed time?).

Also, there is no numerical simulations comparing the algorithm with other existing algorithms and no detail about algorithm's computational complexity.  My guess is that it is probably because, in practice, the proposed algorithm is not efficient: despite having order-optimal regret, the hidden constant in the O(.) are just huge. Hence, this algorithm has mostly a theoretical interest but not really a practical interest.

The sketches of proof for both theorems are convincing. The exposition of the paper is clear and the obtained result is nearly minimax optimal for tabular discounted MDPs. The literature review is well described.

limitations_and_societal_impact: The authors could comment on the practical use of the algorithm (numerical complexity and performance compared to related work).

Apart from the regret proof, is there a big difference with UCB-VI? It seems to be that UCBVI-\gamma does not use episode. Is it the main difference?

The regret definition impliees that only the visited states will be well identified. Would an episodic approach with restart be more appropriate here?
review_title: null

Meta-review: This paper studies the sample complexity of tabular (finite state/action) reinforcement learning in the infinite-horizon discounted setting, which is a fundamental problem in reinforcement learning theory. The main contribution is to provide improved upper and lower bounds on the optimal sample complexity (w.r.t, the dependence on the horizon parameter (1-gamma)^(-1)) which resolve the optimal sample complexity. The reviewers found these results to be interesting and technically non-trivial and recommend acceptance, but the authors are encouraged to take their suggestions into account and update the paper to better emphasize what the key analysis ideas and why they are novel.
Decision: Accept (Poster)