Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence of Q-learning with two popular empirical heuristics (a) online target learning and (b) experience replay. The analysis in this paper is established upon the off-policy setting along with fast-mixing and minimum reachability assumptions. Main convergence results are provided for the linear MDP where all relevant quantities (transition, reward, and Q functions) can be represented as linear functions. The authors propose two variations of Q-learning, namely, Q-Rex and Q-RexDaRe. Convergence results are also given for two algorithms with the sample-optimality guarantee for Q-RexDaRe. 
main_review: I start by saying that I agree with the motivation of the paper to study practically successful algorithms. However, I am not very convinced with the significance of the results or techniques. 

- The paper does not study Q-learning as it is, but uses a fixed-policy to remove correlations between Q-estimate and actions. 

- Algorithm 1 seems like a minor variation of variance-reduction technique. I think that the formulation of (reverse) experience-replay or online target Q-learning should be more explicitly described before Algorithm 1. 

- Assumption 3 with Assumption 4 is quite strong and crucial for the analysis. With this assumption, I think the analysis should be similar to previous analysis on Q-learning or SARSA (e.g., Zou et al., 2019). 

- In Theorem 3, by the sample complexity do you mean $\Theta(NKB)$? 
summary_of_the_review: Overall, I agree that it is important to study practically successful and well-used algorithms (even if they do not have any particular benefits from a theoretical standpoint). However, considering the theoretical nature of the paper, I think the contribution of this paper is marginal given a long line of work in the convergence analysis of practical RL algorithms. I lean toward rejections.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides sample complexity bounds for a Q-learning based algorithm with target Q and experience replay.
Contributions: The authors provide an algorithm with proven sample complexity for linear MDPs and the tabular setting bridging the current state of the art. The analysis relies on common heuristics of experience replay buffer and using a target network given these some theoretical grounding.
main_review: Strengths:
1. The paper provides solid novel analysis combining the recently proposed reverse experience replay. 
2. I could not find no typos and the writing was good.

Weaknesses:
3. Much of the paper is in the appendix (all proofs, the experiments). On the other hand, the paper holds 2 options inside the algorithm (that doesn't seem to be part of the core message but more of a technical point) and 3 algorithms where only one is given and considered in the theory. This makes things unnecessarily complex in the paper itself, while actually missing some of the more interesting complexities of the proofs, or the empirical results.

4. I'm missing some understanding regarding the reverse experience replay. Usually experience replay buffers are used to reduce correlations in the updates of the Q, but when samples are taken serially backwards - won't the correlations be very strong? The observation regarding super-martingale might important here - perhaps it would be better to state it in the paper itself in a more clear way (since this does seem like part of the core of the paper). 

5. As a follow-up - I understand the gaps are there to make the buffers independent (also could be made clearer in the paper). But why do we need the buffers to be independent? Is this just as a technicality to make the analysis easier?
summary_of_the_review: I think the paper provides interesting theoretical results and analysis. The idea of using a reverse experience replay buffer sounds interesting for practical use, though I'm not entirely sold there as mentioned in the main review. The work is not groundbreaking but is a solid advancement in its niche.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the sample efficiency of the Q-learning algorithm in both tabular and linear setting. They propose efficient algorithms which can provably converge to the optimal policy with near-optimal sample complexity bounds.
main_review: In this paper, the authors study the sample efficiency of the Q-learning algorithm, which is a popular approach with broad applications in RL. Based on the standard Q-learning approach, they propose several algorithms called Q-Rex and Q-RexDaRe. With the mixing-time assumption and access to an exploration policy with good coverage, they prove that their algorithms can converge to the optimal policy with near-optimal sample complexity bounds. Their results highlight the benefits of online target learning and experience replay. 

Assumption 3 ensures that the Markov chain induced by the policy $\pi$ can quickly converge to a stationary distribution after $O(\tau_{mix})$ steps, and Assumption 4 indicates that the stationary distribution has a good coverage in the feature space. These assumptions simplify the problem since the agent can collect i.i.d. samples from a stationary distribution with good coverage by executing the policy $\pi$. I wonder whether there are concrete examples in which these assumptions hold, or whether these assumptions can be further weaken with other techniques. Besides, I remember that the lower bound proposed in Azar et al. (2013) is proved in the generative-model setting without such assumptions. In other words,  the lower bound in Azar et al. (2013) may not hold with further assumptions in this work, which means that the sample complexity of Q-RexDaRe may not be minimax optimal as claimed by the authors.

The sample complexity (regret) of Q-learning algorithm in the tabular setting has also been studied by Jin et al. [1]. They obtained the near-optimal sample complexity $O(H^4SA/\epsilon^2)$ in the online-exploration setting without access to the exploration policy $\pi$ or any generative model. More comparison between the tabular results in this work and that in [1] is necessary in the related work section.

minor comments:
1. The parameter $\kappa$ may implicitly depends on the feature dimension in the linear setting. Therefore, the sample complexity bounds in the theorems still have implicit dependence on the dimension $d$.
2. Several techniques in this work have also been used in the algorithmic design and complexity analysis of previous related results. For example, the design of gaps with length $u$ between buffers has been applied in [2] to obtain near-optimal regret in the infinite-horizon average-reward setting, and the benefits of experience replay has also been observed in [3] for policy optimization methods. It would be better if these relevant references are added in the paper.

[1] Is Q-learning Provably Efficient?

[2] Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes

[3] Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
summary_of_the_review: Overall, the paper is clear with solid theoretical bounds. Their results show that the Q-learning algorithm with online target learning and experience replay can provably converge to the optimal policy with near-optimal sample complexity. One concern is that the assumptions may simplify the analysis of the problem. Besides, more discussion on the related works needs to be added.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper connects Q-learning with online target learning and reverse experience replay and also obtain the result for linear MDPs. Those results are the first of its kind and are shown to be near-optimal in their respective regime. In particular, for asynchronous setting the Q-REX has order $\frac{|\mathcal{S}||\mathcal{A}|}{\epsilon^{2}(1-\gamma)^{4}}$ and Q-REXDARE has order $\frac{\max \left(\bar{d}, \frac{1}{\epsilon^{2}}\right)}{\mu_{\min }(1-\gamma)^{3}}$. The latter one nearly matches the standard lower bound.
main_review: Strengths: This paper studies the sample complexity of asynchronous learning. Especially, the new algorithm Q-REX achieves the sample complexity $\frac{|\mathcal{S}||\mathcal{A}|}{\epsilon^{2}(1-\gamma)^{4}}$ and Q-REXDARE achieves complexity $\frac{\max \left(\bar{d}, \frac{1}{\epsilon^{2}}\right)}{\mu_{\min }(1-\gamma)^{3}}$.

Weaknesses:

1. Although Q-learning is known to be sub-optimal, the variant of Q-learning are optimal in a couple of setting. For instance, [1] in online setting and [2] in finite horizon offline setting. Since Q-REXDARE is also a variant of q-learning, I think the improvement is a little bit limited comparing to [2] (which uses variance-reduction for Q-learning with $d_m\approx \mu_\min$). I do notice the there is a theorem 1 which holds for linear MDPs, but I cannot see whether this is optimal. (By the way, the paper did not include the related literature [1],[2])

[1] Zhang et al., Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition, NeurIPS 2020,
[2] Yin et al. Near-optimal offline reinforcement learning via double variance reduction, NeurIPS 2021.

2. Another major weakness is the current algorithm can only guarantee Q-function learning, which cannot guarantee $\epsilon$-optimal policy with the same complexity since it is known $\epsilon$-optimal Q-function learning can only imply $(1-\gamma)^{-1}\epsilon$-optimal policy. Therefore, the current result cannot guarantee $\epsilon$-optimal policy with near-optimal sample complexity.



summary_of_the_review: Overall, due to the weaknesses I mentioned above, I think this paper does not cross the bar due to the high selective of ICLR. Since the theorems are correct from my point of view, I will choose weak reject.
review_title: null

Meta-review: The paper analyzes a variant of the Q-Learning algorithm with two modifications: Online Target Learning (OTL), and Reverse Experience Replay (REP). OTL is essentially the same as using the target network. REP is a new modification of ER, which instead of randomly selecting samples from the buffer, replays them in the reverse order.

Most reviewers are positive about this paper, so I am going to recommend acceptance. There are, however, several concerns that have been raised by the reviewers. As the authors have not revised the paper during the discussion period, my acceptance recommendation is under the good faith expectation that the authors make a serious effort in improving their work based on the reviews. Some of the concerns are:

- The intuition of why REP breaks the correlation is not clear enough. This has been brought up several times by the reviewers.
- What are the technical differences in the analysis compared to previous work such as Zou et al., 2019?
- The kappa appearing in Assumption 4, and showing up in the error bounds, can be dimension dependent. Please clarify this and its effect on the results.
- Much of the paper is in the appendix. It helps if the authors can include more about the proof technique in the main body of the paper.
- Describe the relation between the error in the value function vs. the performance of its greedy policy.
Decision: Accept (Poster)