Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a new memory-efficient model-free algorithm for online episodic RL that achieves near-optimal regret with improved sample size requirement. It exploits reference-advantage decomposition for variance reduction and a double estimator for bias reduction to achieve the improvement.
main_review: This work significantly improves the sample complexity barrier for memory-efficient RL algorithms. The use of double estimator to mitigate bias is very interesting and novel as far as I know, and can have implication for other studies.

The paper is very well written and easy to follow. The authors explain the key ideas and intuition of related work and the construction clearly. The theoretical derivations seem correct, though I didn't fully check them all in the supplementary materials.
limitations_and_societal_impact: Considering the specific setting this paper focuses on, the derivation looks solid and I don't see obvious limitations of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a modified model-free reinforcement learning algorithm for time-inhomogeneous tabular MDP, in which it presents the novel technique of *Double Advantage*. It achieves nearly optimal regret and more importantly, the required sample size of being nearly optimal is significantly smaller than previous works if we require the algorithm to also be space-efficient.
main_review: Overall, I consider the technique of *Double Advantage* developed by this paper is novel in the sense that using two reference value functions circumvents the need of using the unknown $V^\star_h$. Meanwhile, the whole paper is also well-written with lots of intuitive explanation and clear proof sketch in the appendix.

However, I feel hesitant about the significance of its result. In particular, an improvement of space complexity in order of $O(S)$ does not look so valuable compared to a sacrifice of sample complexity in order of $O\left(H^4\right)$.

Questions:
- How does the choice of constant "1" affects the final result in Line 13 of Algorithm 1?
- Is there any more direct intuitive explanation on why the updating rule (13) at the bottom of page 6 decreases the necessary sample size of being optimal?
- At line 221, it says that as long as $V^{\mathsf{R}}_h(s_h)<V^\star_h(s_h)+2$ is satisfied, there will not be any further updates for $V^{\mathsf{R}}_h$. Does this imply that $V^{\mathsf{R}}_h$ decreases monotonically (through *update-ucb-q-advantage*) as episode index $k$ increases? That is, will we have $V^{\mathsf{R}}_h(s_h)\ge V^\star_h(s_h)+2$ in future?
- Although the problem formulation and analysis assumes a time-inhomogeneous MDP, the algorithm itself seems to be applicable for time-homogeneous MDP also. Is there any intuition on how it will perform on a time-homogeneous MDP?
- Does the sample complexity dependency on $S$ and $A$ more important than $H$?

Suggestions on writing:
- $W_h^{\mathsf{R}_i}$ appears without initialization in Algorithm 1.
- It seems better to give a precise mathematical definition of $B^{\mathsf{R}}_h(s, a)$.
- It is probably better to roughly describe in the main text about how you use two reference value functions to avoid the need of using $V^\star_h$, the part of *step 3* in Section B.3.

---

Score increased after rebuttal.
limitations_and_societal_impact: The authors adequately addressed the limitations of their work in Section 4 by presenting them as potential future works. 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: This paper addresses the problem of designing a memory-efficient and sample-efficient algorithm for episodic MDPs with smaller initial warm-up phase. The paper proposes a new model-free algorithm "UCB-Q-Double-Advantage" that extends the optimistic Q-learning and the reference-advantage decomposition for variance reduction using two reference-advantage functions, i.e. the updated reference-advantage function and the old reference-advantage function. Use of these two functions with a well-curated update rule leads to near-optimal regret with SAH^2 warm-up actions, O(SAH) memory complexity, \tilde{O}(optimal x H) sample complexity, and O(T) time complexity. The final performance is O(H) worse than optimal in terms of sample and warm-up complexities.
main_review: Originality: 
The observations following Equation 13 and its role in reducing updates of the advantage function is original and impactful. Also, the idea of using new and old reference-advantage functions as a proxy of checking the update condition derived from Eq 13 is quite interesting and effective.

Quality:
+ The paper proposes a new algorithm that juggles with warmup and sample complexities as well as space and time complexities quite efficiently with a simple (implementation wise) trick of using a new and an updated reference-advantage function. The proposed trick and its effective use opens up future developments.

- The paper has two main issues. Firstly, though it explains the algorithm and the contributions in light of related work pretty well, the proof technique is never summarised intuitively and briefly. This poses hardness in pointing reasons of limitations and improvements in the proof structure. Secondly, the paper never really implements the algorithm and show its applicability. Such an implementation always increase its usability and testability by readers and practitioners. But this a common issue of most of the papers in this category.


Clarity:
+ In general, the paper presentation is good. The contribution of the paper with respect to the existing literature is well posed in the introduction itself. Also, the formulation of the problem and the existing tricks in literature on which the paper is built are well explained and recognised. The intuition of early settlement and Eqn 13 is also well understood. 

- The only problem is that the proof technique is not clear in the main paper. The reader keeps on wondering why the presented intuition exactly improves the warmup or sample complexities. A brief summary of the flow of proof as in App. B.3 along with the points where it deviates from the nearest relative, i.e. UCB-Q-Advantage, will be interesting and insightful. it may also help to understand why still the sample and warmup complexities are suboptimal by H.

Significance:
The paper proposes an effective algorithm design technique that improves performance: the warm-up and sample complexities, and effectiveness: the space and time complexities, of existing algorithms (except UCBMQ, which has better performance but S times more space and time complexities). The use of double advantage functions and their effectiveness may invoke future research in designing more efficient and deployable RL algorithms.
limitations_and_societal_impact: 1. The final performance is O(H) worse than optimal in terms of sample and warm-up complexities. It would be helpful for future developments if authors include a comment on why is it so and whether there is any part of the proof that they think can be improved.
2. The algorithm is in general presented intuitively but the proof technique is not clear in the main paper. The reader keeps on wondering why the presented intuition exactly improves the bound. Is it only the number of reference function updates or is it more than that? If the first is true, then how much than single advantage function?
3. Another point is that authors mentioned similar and even better warm-up complexity and regret is achieved by UCB-M-Q as "at a price of a higher storage burden". The statement seems a bit loose, and as if it is fundamentally necessary to have such larger space complexity to achieve UCB-M-Q's improvements. Explaining whether it is authors intuition or only a way of presenting the result or they think it is fundamental by construction will make the argument rigorous.
review_title: null

Meta-review: Dear authors,

Following the rebuttal, the reviewers reached a consensus to positively evaluate the contribution.



Decision: Accept (Spotlight)