Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper revisits the regret of undiscounted reinforcement learning in MDPs with a birth and death structure. Specifically, they consider a controlled queue with impatient jobs and the main objective is to optimize a trade-off between energy consumption and user-perceived performance. They exploit the structure of the MDP and give a tighter upper bound on the regret of a slightly-tweaked version of the classical learning algorithm UCRL2.  Their bound is asymptotically independent of the number of states and of the diameter. 
strengths_and_weaknesses: Strengths:
Over all, this paper studies a special case of MDP with a birth and death structure. The MDP case is commonly used in practice, and is worth studying. In theoretical analysis, the authors studies a slightly-tweaked version of the classical learning algorithm UCRL2, which is relatively simple and widely used. By exploiting the structure of the MDP, they provide a much tighter upper bound on the performance of UCRL2, which, surprisingly, is independent of the number of states, and improves previous naive results which exponentially depends on S. This paper is interesting, and is important to RL theory.

Weaknesses:
1. There are no corresponding lower bounds, so we do not know whether the upper bound is tight or not.
2. It will be better if the authors can provide experiment results to support their algorithm.
questions: 1. Are there any lower bounds on the setting considered in this paper?
2. Can the authors conduct numerical experiments to shoe the effectiveness of the method?
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies RL in undiscounted MDPs. The authors break the minimax lower bound which depends on the MDP diameter (shown to be as large as $\Omega(S^S)$) by restricting the MDPs to a structured class of birth-death processes and showing that a tweaked version of the classic UCRL2 algorithm achieves an upper bound independent of the diameter and state size. This bound is obtained by carefully analyzing the stationary measure for this restricted MDP class and exploiting its high non-uniformity.
strengths_and_weaknesses: **Strengths** 

- The problem studied in this paper is related to finding structures in RL that facilitate efficient learning is an important topic. Many existing works in finite-sample analysis of RL have focused on algorithms that are nearly optimal in a minimax sense, where the optimality is measure w.r.t. the most difficult MDP. However, this does not explain why RL works well in certain environments. Studying structed RL is important to bridge the gap between theory and practice and this paper contributes to this line of research.
- The paper considers a specific structure (birth death) related to queueing systems, which itself has important applications and seems to be motivated by practical implications. Moreover, this structure is different from usual structures considered in RL theory literature such as low rank MDPs. Although the minimax lower bound depends on diameter (which is large for birth death process), the paper carefully analyzes regret for this restricted class of MDPs to identify whether there is a diameter or state size dependency. The authors show that a variant of UCRL2 achieves a regret independent of these parameters. 
- The technical contributions are insightful and may inspire future work. For instance, although UCRL2 does not exploit the parameteric form of MDP, it still achieves a regret independent of diameter and state size. Another technique used in the regret guarantee is exploiting the highly non-uniform stationary measure in the restricted MDP class.
- The paper is very well-written and thorough comparison with prior related theoretical results and their implications is provided. 

**Weaknesses**

- The structure considered in this work may be more limited compared to other structures in prior works such as factored MDPs, which may limit the significance and impact of this work.
- The paper shows that a variation of UCRL2 achieves a regret independent of diameter and state size. It remains unclear whether the tweak was necessary, the regret is optimal, and other popular methods such as UCB also enjoy similar guarantees. Additional theoretical and/or empirical results can strengthen the work. 
questions: Why did you consider UCRL instead of UCB?
limitations: The work is theoretical.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposed a new undiscounted MDP setting with a birth and death structure. Then the authors modified the classical UCRL2 algorithm to achieve an $\widetilde{O}(\sqrt{E_2AT})$, which has no dependence on the number of the states and the diameter. This is achieved by leveraging the special structure of the queueing system. 
strengths_and_weaknesses: Strengths:
- This paper formulated queueing as an MDP with birth and death structure and proposed an efficient algorithm, which is important as the queueing system is widely applied in many different areas. 
- The regret bound has no dependence on the number of states or the diameter thanks to the special structure. On the other hand, it depends on $E_2$, which is a weighted second moment of the stationary measure of a reference policy. This result is interesting as it is specialized to the problem structure. 

Weakness:
- The writing part can be improved. I didn't understand why $E_2$ can be interpreted as the second moment and why dependence on the number of states or the diameter can be removed. As a result, I am not certain about the correctness o this paper. 
questions: - I didn't see why $E_2$ can be interpreted as the second moment from the definition in Line 225. Can the authors elaborate more on this point?
- What is the upper bound on $E_2$?
limitations: I am not aware of any potential negative societal impact
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work studies RL on a special class of MDPs called the birth and death process (BDP for short). The authors claim that by applying the UCRL2 algorithm to BDP, a state-independent regret can be obtained, which improves the existing best-known regret bounds that depend on the state space cardinality explicitly. 
strengths_and_weaknesses: Strengths:

+ The presentation is clear. 
+ The theoretical results are technically sound. 

Weaknesses:

+ The importance of this work remains unclear. This work does not propose either a new algorithm or a new proof approach. It seems that the only difference between their algorithm and proof and those of [10] is some more refined analysis which depends on the quantity $r_{max}$, as they showed in (12, 13). However, the difficulty to analyze it is unknown, and I feel it is not important enough to be the main contribution of a NeurIPS paper. 

+ The comparison of some highly related works lacks. In Section 4.2, the authors claim that BDPs can be regarded as a special class of linear mixture MDPs, and existing algorithms for linear mixture MDPs are for discounted MDPs and can not be directly applied to BDPs . It is not true since Wu et al., 2022 have already studied linear mixture MDPs with average rewards. Given the existing results, it is hard to judge the contribution of this work. 


Wu, Y., Zhou, D., & Gu, Q. (2022, May). Nearly minimax optimal regret for learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics (pp. 3883-3913). PMLR.
questions: + Can the authors highlight their theoretical contributions?
+ Can the authors compare their work and Wu et al., 2022? 
limitations: Yes.
review_title: null

Meta-review: metareview: This paper studies reinforcement learning in a restrictive set of MDPs. It showed that a tweaked version of the classic UCRL2 algorithm achieves an upper bound independent of the diameter and state size. This bound is obtained by carefully analyzing the stationary measure for this restricted MDP class and exploiting its high non-uniformity. It is an important problem to identify structure in the MDP that enables efficient learning. 
confidence: Less certain
Decision: Accept