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 studies regret minimization in infinite-horizon average-reward MDPs. They propose a new algorithm based on Indexed Minimum Empirical Divergence (IMED) bandit algorithm, and show that the new algorithm achieves a regret matching the asymptotic problem-dependent lower bounds.
strengths_and_weaknesses: Strength: the paper is clearly written. The proposed algorithm has strong theoretical guarantee and competitive empirical performance.

Weakness: Many important details are hidden in the Appendix (for example, the limitation of existing work is deferred to Appendix G). Thus, the contribution of this paper is not clear at first glance compared to existing works. I think more highlight s on the 
questions: 1. How should I compare the asymptotic problem-dependent lower bound with the $\sqrt{T}$-type minimax lower bound? Does the algorithm also ensures a $\sqrt{T}$ finite time regret?
2. What's the difficulty of extending current analysis to the communicating setting?
3. The regret definition is different from the one used in UCRL paper: $R_T = \sum_t (g_{\pi^{\star}} - r_t)$. How should I compare these two types of definitions?
4. Do you see a direct way to extend to linear function approximation?
limitations: See "Strengths And Weaknesses"
review_title: null

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: The paper considers ergodic MDPs and proposed an index policy IMED-RL. The IMED-RL index is built on the IMED policy for multi-armed stochastic bandits. Regret bound for IMED-RL is provided and shown to match the lower bound for ergodic RL problems.
strengths_and_weaknesses: Strengths:
- The proposed policy is based on the IMED-RL index which is new for RL and different from commonly used optimism based  algorithms.

- Regret bounds of IMED-RL are provided for ergodic MDPs and the upper bound and lower bound match.

- Numerical experiments show better performance of IMED-RL compared with prior algorithms with certain regret guarantees.

Weaknesses:
- The ergodic assumption is very strong. Most MDPs including RiverSwim in the numerical experiment are not ergodic. The ergodic assumption is not typical and there are many RL algorithms with performance guarantees without the ergodic assumption. Results requiring the ergodic assumption seem very limited. 

- The provided justification for focusing on ergodic MDPs is that it's the only class of MDPs with regret lower bounds. However, in Jaksch et al. [2010b], has a regret lower bound for the much more general class of communicating MDPs.

- Minor: the definitions of several notations are hard to find, making the paper not easy to follow. For examples, the definition of the count number N_{s,a}(T) is hidden in the statement of Lemma 1, and the definition of \phi_M is a bit hidden within lines.
questions: - It looks like one could compute the IMED-RL index for communicating MDPs. Would it be possible to apply IMED-RL to communicating MDPs with (possibly weaker) regret bounds?
- Are there any connection between the IMED-RL index and some optimistic values?
limitations: The assumptions and limitations are clearly stated in the paper.
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 considers regret minimization in ergodic undiscounted MDPs under the average-reward criterion. It builds upon the classic results by Burnetas and Katehakis (1997) for this setting, and provides an adaptation of the IMED bandit algorithm (Honda and Takemura, 2015) to this setting. This algorithm, called IMED-RL, matches asymptotically the lower bound by Burnetas and Katehakis, and can thus be considered optimal. The theoretical results are complemented by numerical simulations showing that IMED-RL is very efficient in practice.
strengths_and_weaknesses: The paper is well written and clear. The authors do a great job in explaining the theoretical framework, which is classic but is also a notoriously complicated one. The difference between existing results and original contributions is also well explained. I would only spend more words on describing the original IMED (bandit) algorithm of which IMED-RL is an adaptation to MDPs.

Originality is limited, since the work builds upon a well established theoretical framework and an existing algorithmic idea. However, there is some originality in the theoretical analysis, for instance in how the concept of skeleton.

The results are significant for the area of efficient exploration in RL. As mentioned by the authors, it is not easy to match the lower bound by B&K with a reasonably practical algorithm. Instead, besides its strong theoretical guarantees, IMED-RL shows good performance in practice too.
questions: 1. How would the worst-case regret of IMED-RL compare with the one of UCRL and PSRL?
2. What do you think is the advantage of IMDEL-RL over the other exploration algorithms in practice?

Minor:
- line 19: communicative -> communicating
- Definition 1: s_1 should be s or vice-versa
- line 92: why is UCB "infamous"?
- line 124: communication -> communicating
- Footnote 2: square bracket
- line 258: "numerical issues" is an odd choice of words, it usually refers to numerical problems in the implementation. I think you mean something like "empirical aspects"
- line 273: missing space after PSRL
limitations: Limitations should be discussed more. For instance, how does IMED-RL scale to problems with many states and actions?
review_title: null

Meta-review: metareview: Regret theory for ergodic undiscounted infinite-horizon MDP was largely an open problem. The authors made an effort to fill in this gap. All reviewers see merits of the analysis, and the rebuttal has addressed most of the reviewers' concerns. Please make sure to incorporate necessary changes and add missing citations while preparing the final paper.
confidence: Certain
Decision: Accept