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 work provides a unifying review of hardness measures for MDPs that have appeared in previous RL theory bounds in tabular settings. The authors have also developed a benchmark with easily estimable values for these hardness measures to be used for empirical investigation of RL theory. Performance of four standard algorithms are measured in the environments.
strengths_and_weaknesses: *Originality:*
The work provides a unifying perspective on what has thus far been seen as disparate notions of hardness, with qualitative comparison of the strengths and weaknesses of each. I think that, while no new notion of hardness is investigated here, which would make this a very strong paper, the perspective offered is novel and worthwhile. The development of a standard tabular benchmark for RL theory is again a work of synthesis from previous papers. While valuable for RL theory practitioners, there is less novel insight here, as these environments are well known.

*Quality:*
The paper is clearly well-thought through and well constructed, with unifying insight provided. I think if the environments weren't chosen from the literature, but instead chosen such that the different aspects of hardness described in the paper were easier to control independently with respect to the different policy and environment parameters described in the paper, the benchmark would lead to even more meaningful insight.

*Clarity:*
The paper is easy to follow, and plots and charts are easy to read. The visualisations of the environments give good intuition as to their structure, and the experiments give good characterisation of their hardness.

*Significance:*
The paper is significant, and well-poised to enable future work in unified hardness and empirical evaluation of RL theory results.

questions: How were environments selected from the literature? Was any attempt made to construct novel MDPs with particular relationships between hardness measures? What limited this process if so?
limitations: As suggested above, the insight here is mainly unifying, with little specific novel contributions, either in terms of environment or in terms of analysis. New measures of hardness, or previously unseen environments with useful properties would make the paper very strong.
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: The paper introduces Colosseum, a Python package that allows empirical investigation of MDP hardness along estimation complexity and visitation complexity for tabular reinforcement learning. It surveys various existing harndess measures and argues why many of these do not capture the above mentioned complexities properly. The ones which come closest to capturing these are Environmental value norm for estimation complexity and Diameter for visitation complexity as I understand from the paper. It also implements agents and implements a benchmark for what the authors claim are the four most widely studied tabular reinforcement learning settings - which I believe are: (a) Episodic ergodic. (b) Episodic communicating. (c) Continuous ergodic. (d) Continuous communicating. They also perform experiments examining the hardness measures under various changes to the MPDs (Fig. 1) as also with the agents in the mentioned settings (Tab. 1 and fig. 2).

strengths_and_weaknesses: I believe they motivate the approach well and the benchmark is more comprehensive than existing benhcmark for tabular RL. The quality of the woek also seems high. They provide code and collect it in a single package which should be of great significance to the community, esp. but not just the tabular RL communtiy. I assume the code quality is also good based on a quick walk through the Jupyter notebook: Colosseum_main_tutorial.ipynb. The analysis plots also look good. However, in respect to the clarity, I feel like the paper would be much more suited to the journal format. I feel like many of the questions I ask below are probably clarified in the Appendix (which I only glanced through), however, I feel like some of these rather belong in the main paper.

The motivations for the different MDP families was not described in the main paper

There were some statements such as:
>The ergodic settings seem generally slightly easier than the communicating settings.

But the evidence was not explicitly pointed out. I felt like this in many places and it feels this was done to save space.

Because of such space-saving measures, I feel the paper is better suited to a journal.


In various places the clarity can be improved, e.g.:

>The diameter also increases almost linearly with the number of states. When p_rand is relatively small, an approximately linear relationship can still be observed.

This was a little confusing because sub-figures being referenced are not mentioned. esp. for the 2nd sentence, I can't see the linear relationship when  p is "small" in Fig. 1a because it's not zoomed in enough. What values of p were meant "small"?


>"Sum of the reciprocals of the sub-optimality gaps": This measure of hardness is not particularly apt at capturing estimation complexity, since it focuses solely on optimal policy identification. It also underestimates the increase in hardness induced by an increase in visitation complexity.

I understand the arguments. However, in Fig. 1a-1d, tbh, "Sum of the reciprocals of the sub-optimality gaps" actually seems the closest to the cumulative regret of the tuned near-optimal agent. Could the authors please add some reasoning as to why this measure ends up being seemingly the closet to the cumulative regret of the tuned near-optimal agent even though it is not suited either for visitation complexity or estimation complexity.


>For Q-learning and PSRL (Figs. 2b and 2c), the diameter seems to have a generally smaller influence on the average cumulative regret

I cant quite see this in the figures.

>(efficiently computable) hardness measures

Adding a table with computational complexity of calculating the measures would be highly appreciated.

questions: >For instance, consider an MDP where a set of lowly rewarding states stands between an agent and a set of highly rewarding states. A regret minimization agent is heavily discouraged from visiting the lowly rewarding states, in contrast to a PAC-RL agent. Therefore, the state visitation complexity should differ across settings.

I do not quite think this is the best argument here because if, let's say, the only way to the high-rewarding states is through the lowly rewarding states, then regret would still be minised by going through them and so the agent would not be discouraged.


>The fact that current measures disregard this distinction is concerning, since they should quantify the difficulty of a specific optimization task.

What is "this distinction" here?

What is "the criterion lower bound of class M up to logarithmic factors"?

In line no. 274: "the probability p_lazy that an MDP stays in the same state instead of executing the action selected by an agent"

How can the MDP remain in the same state if an action was taken? Is there a "no-op" action as well in the action space? I saw only 3 actions in the action space and no no-op.

"which solely allows comparing trends"

why is solely italicised here?

How did the authors choose twelve and five random seeds for the experiments?

The paper mentions both cumulative regret and sample efficiency for exploration as possible performance criteria/metrics but then only experiments with cumulative regret agents are shown. Is there a reason sample efficiency for exploration was not considered for the experiments?


limitations: Yes.
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: This paper first presents a survey of existing hardness measures and results from the MDP literature. Their main contribution is the introduction of `Colosseum`, which is a benchmark for empirically validating hardness results, which they use to compare various existing hardness measures.
strengths_and_weaknesses: # Originality
It seems to me that section 2 (Hardness in Theory) is a review of existing literature, so the original contributions of this paper would be limited to the `Colosseum` package and the empirical investigations provided. For these, the work is original as far as I can tell, although some of the claims seem to be a bit inflated (e.g. "a pioneering Python package", "the most exhaustive in tabular reinforcement learning", "invaluable analysis tools", etc.).

# Quality
The authors have done a reasonably thorough survey of hardness literature and evaluated these measures using the various environments in their package. There are a few issues regarding clarity and correctness that I include in the questions below.
The code for `Colosseum` seems to be well-written and well-documented, which I consider to be a core part of this paper's contribution.

# Clarity
The paper is very well written and motivated reasonably well. Some of the plots and tables are hard to digest; specifically, it's often not clear _what_ is being said with them. There's a lot going on in Figure 1 (and even more in Table 1), and even though the main takeaways do seem to be discussed in the text, they're mostly lost in the paragraphs in page 7 (it seems that the last sentence is the main takeaway for each hardness measure). I would suggest highlighting these in a more streamlined manner (to draw the reader's attention directly to the takeaways) and leave the descriptive text until after.
Table 1 is a bit overwhelming, it's not clear what we're supposed to be looking for. I would also suggest rewriting this section so there are clear takeaways and insights for the readers; currently it reads just as a verbal description of the (many) numbers in the table.

Although it is claimed that in Figure 2 "there is generally a positive relationship between both of these hardness measures and the average cumulative regret", it seems almost like points uniformly spread on the plane (i.e. I don't see a clear relationship at all).

There are a few other issues I mention in the questions below.

# Significance
This, to me, is the weakest point of the paper. Although I appreciate the authors' effort to produce a nice package for benchmarking theoretical results, it's not clear how significant this will be. Empirical evaluations on toy environments (for theoretical results) are typically meant to highlight characteristics or subtleties of the theory introduced, but are not the end goal in itself. In particular, whether the empirical results suggest sub-linear or linear growth, say, does not in any way change the theoretical results. Thus, it is not clear what the added value would be to have a "theory benchmark".
Something that I think could make this package more impactful is to try to go beyond tabular. One suggestion would be to look at bsuite (which the authors do cite), as they include both tabular and continuous environments. In particular, it would be interesting to evaluate both as they may allow one to empirically investigate how the hardness measures vary when moving from tabular to larger systems. I acknowledge that in non-tabular systems it may not be possible to compute all of them in closed form, but there may be approximations; alternatively, continuous variants of the tabular systems considered could provide a nice middle ground (e.g. by "smoothing out" each tabular state).
Another aspect that could increase the significance of this work is to evaluate non-tabular methods, for instance with linear function approximators. A lot of RL theory does exist for linear approximators (and tabular, of course), so it would be interesting to evaluate how the dynamics of the empirical evaluations change (or not) when moving from tabular to non-tabular methods.

Along these lines, in line 366 it says "The development of such measures is theoretically and empirically important.". It would be nice to provide some concrete examples, such as a theoretical bound dependent on one of these hardness measures, or something like that. Otherwise it's not clear why these hardness measures are important.
questions: 1. Is all of section 2 just a review of existing literature? It seems like this is the case, but just wanted to confirm.
2. In line 72 it says "Given an optimization horizon $T$". What is this exactly? Is it related to episodic horizon?
3. In lines 99-100 it says there is an assumption of the existence of an optimal policy $\pi^*$ that "obtains maximum value for every state", but this policy will necessarily be dependent on time as well as state, no?
4. Why do you use the value of $0.25$ in equation (1)? This is not justified in the text.
5. Below line 186, $\gamma$ is a subscript of $C$ on the left-hand side, but it does not appear in the right hand side. Should it? Or should it be removed from $C$?
6. In lines 206-208 it says "approximating the value function ... is particularly easy when every sub-optimality gap is small." This is not necessarily the case in RL: sub-optimality gap is with respect to the optimal policy, but in RL we don't start from the optimal policy.
7. In lines 374-375 you say your empirical investigations "revealed previously undocumented weaknesses of these agents and further validated our choices of environments.". What does this say about existing empirical work evaluating these algorithms?
limitations: Some limitations are provided (mostly related to future work). It would be nice to have some discussion regarding the significance/impact (or lack thereof) of this work, in line with some of the comments I made above regarding significance.

No discussion of potential negative societal impact was provided.
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: This paper reviews and categorizes some hardness measures on tabular MDPs, and proposes a new tabular RL benchmark named "Colosseum" that enables exact computation of these measures in empirical evaluations. Extensive experiments are conducted to assess the performance of existing tabular RL methods on the proposed benchmark that spans diverse environments focusing on different hardness measures.
strengths_and_weaknesses: ### Strengths
1. The paper suggests an interesting viewpoint of connecting the theory and practice of tabular RL by taking into account the hardness measures that are typically used only in theoretical analysis when evaluating and comparing tabular RL algorithms.
2. The "Colosseum" benchmark is of high quality, flexible, and with sufficient docs and tutorials.
3. The empirical evaluations are thorough.
4. The paper is well organized and presented. 

### Weaknesses
1. The benchmark and the hardness measures only apply to tabular RL. In contrast, most of the current empirical work in RL is devoted to the non-tabular setting, and there is also an increasing number of theoretical work that explores non-tabular RL.
2. The theoretical claims made by this paper are somewhat vague (see the following for details).
questions: 1. The authors wrote in the paper "we believe our contributions are important milestones towards the future development of theoretical and empirical measures of hardness for non-tabular reinforcement learning". However, it is not clear how the measures presented in the paper can be extended to non-tabular settings (while still being computationally feasible). Adding more discussion on this point can be helpful.
2. The paper surveys existing hardness measures by dividing them into two categories, namely "Markov chain-based" which focuses on the state visitation complexity, and "value-based" which focuses on the estimation complexity of value functions. It seems like this taxonomy is closely relevant to the well-known "exploitation-exploration" dilemma with state visitation complexity capturing the difficulty in exploration, and estimation complexity capturing the difficulty in exploitation. The authors are encouraged to discuss this relation in more detail.
3. The message conveyed by Definition 2.1 is somewhat vague: it is not clear to me how this "complete measure" connects to the intuition or other theoretical arguments that capture the "hardness" of learning a near-optimal policy on an MDP, e.g., the PAC learnability. In other words, is there any conceptual/theoretical evidence implying that this hardness measure is _sufficient_ in the sense of some criteria? Also, while I can understand that existing measures may be insufficient in measuring all aspects of hardness since they either focus on the state visitation complexity or the estimation complexity, can we use Definition 2.1 to certify this?
limitations: No concern.
review_title: null

Meta-review: metareview: The reviewers' opinions are quite consistent towards a weak accept. 
I'm not confident with the big title "Hardness in Markov Decision Processes: Theory and Practice". This paper is more like a survey + benchmark review instead of a research article. Neither the theory part or the practice part is novel enough as a research article. It's a bit thin as a survey paper.
I personally tend to weak reject but I respect the reviewers' weak accept.
confidence: Less certain
Decision: Accept