Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Summary: This paper adapts the UCB Q-learning method to the inifinite-horizon discounted MDP setting. With an analysis similar to that of Jin et al (2018), it shows that this algorithm achieves a PAC bound of (1-gamma)^-7 |S||A|/eps^2, improving previous best-known bound (Delayed Q-learning, Strehlet et al, 2006, (1-gamma)^-8 |S||A|/eps^4) for this case.

Evaluation: As I see this paper a direct extension of that of Jin et al (2018), I am afraid I have to recommend a rejection. 

Here are some more detailed comments:

Significance: 
This paper studies the RL problem for the infinite-horizon discounted MDP setting. This is an important setting in reinforcement learning. However, the bound is not optimal as the dependence of (1-gamma) is significantly larger than the lower bound. Moreover, both the algorithm and analysis are direct extensions of that of Jin et al, I do not see a huge technique improvement. 

Technique Novelty:
As stated in the paper, the major difficulty is that the inf-horizon case does not have a set of "consecutive episodes". Therefore the "learning error at time t cannot be decomposed as errors from a set of consecutive time
steps before t, but errors from a set of non-consecutive time steps without any structure." However, I do not see a major technological innovation is needed to get around this issue. As a result, the analysis and algorithm in this paper are very similar to that of Jin et al 2018, who nearly implicitly contain the results in this paper.

Furthermore, I would think there is a (likely) very simple reduction from the inf-horizon to finite-horizon: break the inifinite horizon into episodes of length R = O((1-\gamma)^-1 log(eps^-1)). Now, although the MDP does not restart, but it can be treated as restarting at a history-dependent initial state distribution at the beginning of every episode. So, an optimal finit-horizon algorithm in this setting is at most epsilon worse than the optimal inf-horizon algorithm, no matter where/when you start. With little to no modification, we can see that Jin et al work in this setting. Thus, we obtain an algorithm for the inf-horizon as well.

A good match for this conference?
As this paper is an adaptation of a previously known Q-learning algorithm to a slightly different setting in RL, I do not see how it fits the "learning representation" paradigm. Of course, Q-function can be argued as a representation of the MDP model, but this Q-function itself is not a new concept in this paper.




review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: This paper extends Jin et al. (2018)'s idea to infinite horizon and improves the best known sample complexity to $\tilde{O}(\frac{SA}{\epsilon^2 (1-\gamma)^7})$. The derivation is similar to Jin's paper except a very careful selection on the pseudo-horizon length $H$, where $H$ is given in finite horizon and work as the decaying rate for $\alpha_k$, but for infinite horizon when we need to decide how to pick $H$.

Theoretical Soundness: I didn't check every step of the proof, but I the steps I check is correct and I can feel that the derivation is solid.

Novelty: In section 3.2, the authors discuss the difference between finite case and infinite case. I don't agree with the example if the starting state $s_1$ is with leaving probability less than $T^{-1}$. In this case, the latter rewards counted for $V(s_1)$ will multiply by $\gamma^t$ which is pretty small, and will not contribute too much on the error. But I do agree that the case of infinite horizon is different since we need to carefully decide the decaying rate of $\alpha_k$, which is definitely related to $\frac{1}{1-\gamma}$ but we need to figure out the relation. I think that is the most difficult part of the whole proof and this is the main technical contribution for the paper.

Minor issue: In algorithm box I didn't see $V^{\pi_t}, \hat{Q}_t$ which occurs a lot in the derivation. Maybe change $\hat{V}$ and $\hat{Q}$ in the way align to the derivation?

Overall I think this paper is sufficient to get in the conference. But to be honest since I lack the background of PAC-RL, I would remain a conservative of weak accept and would like to hear more discussions from other reviewers and authors to finalize my decision.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: Summary:
In this paper, the authors extend the UCB Q-learning algorithm by Jin et al. (2018) to infinite horizon discounted MDPs, and prove a PAC bound of \tilde{O}(SA/\epsilon^2 (1-\gamma)^7) for the resulting algorithm. This bound improves the one for delayed Q-learning by Strehl et al. (2006) and matches the lower-bound in terms of \epsilon, S, and A. 


Comments:
- Overall, the paper is well-written and well-structured. Although most of the results are in the appendix, the authors have done a good job in what they reported in the paper and what they left for the appendix. 
- I personally think ICLR is not a good venue for this kind of papers. Places like COLT and journals are better because they allow the authors to report most of the results in the main paper, and give more time to the reviewers to go over all the proofs. 
- I did not have time to go over all the proofs in the appendix but I checked those in the paper. I did not find any error, but the math can be written more rigorously. 
- The algorithm is quite similar to the one by Jin et al. (2018), which is for finite-horizon problems. The authors discuss on Page 4 that why despite the similarity of the algorithms, the techniques in Jin et al. (2018) cannot be directly applied to their case. It would be good if the authors have a discussion on the novelty of the techniques used in their analysis, not only w.r.t. Jin et al. (2018), but w.r.t. other analysis of model free algorithms in infinite-horizon discounted problems. 
- What makes this work different than Jin et al. (2018), and is its novelty, is obtaining a PAC bound. The resulting regret bound is similar to the one in Jin et al. (2018), but the PAC bound is new. It would be good if the authors mention this on Page 4. This makes it more clear in which sense this work is different than that by Jin et al. (2018). 
- It is important to write in the statement of Condition 2 that "i" changes between 0 and \log_2 R. 

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper considered a Q-learning algorithm with UCB exploration policy for infinite-horizon MDP, and derived the sample complexity of exploration bound. The bound was shown to improve the existing results and matched the lower bound up to some log factors. The problem considered is interesting and challenging. However, I have a few major concerns.

1. Assumptions: The Condition 2 is on the term $X_t^{(i)}$ which is the i-th largest item of the gap $\Delta_t$ (the difference between the value function and the Q function fo the optimal policy). How to verify this condition in practice? Do you need this condition for all $t$? Does this condition depend on the choice of length $R$? The conditions are listed without any discussions.  

2. Algorithm: The Algorithm depends on the choice of the parameter $R$. How to choose $R$ in practice?

3. Writing: This paper is not well written. There are many typos and grammar errors. In addition, the key components Sections 3.3 and 3.4 are very hard to follow. For instance, in Section 3.3, the authors first introduced Condition 1 and then Condition 2, and then claimed that Condition 2 implied Condition 1. Similarly, in Section 3.4, Lemma 1 was introduced before Lemma 2. Then the authors claimed that Lemma 2 implies Lemma 1. If would be easier to follow if the authors only introduced the latter result, and then discuss the former result as a remark.  

~~~~~~~~~~~~~~~~~~~~~~
After rebuttal: Thanks the authors for addressing my questions. My first two major concerns have been nicely addressed. Therefore, I would like to increase my rating to 6.

review_title: Official Blind Review #1

Meta-review: In this paper, the authors extended Q-learning with UCB exploration bonus by Jin et al. to infinite-horizon MDP with discounted rewards without accessing a generative model, and proved nearly optimal regret bound for finite-horizon episodic MDP. The authors also proved PAC-type sample complexity of exploration, which matches the lower bound up to logarithmic factors. Overall this is a solid theoretical reinforcement learning work.  After author response, we reached a unanimous agreement to accept this paper.
Decision: Accept (Poster)