Venue: ICLR 2021 Conference

Reviews:

final_score: rating: null
review_content: First of all, I honestly sympathize with you having been getting contradictory feedback on several iterations of this work.

At the same time, having read other reviews and re-read my own, I see one common theme jump out at me, although different reviewers talk about it slightly differently. I bet that if you were to address this criticism somehow, reviewers' reaction to this work will be very different.

This criticism is that MDP Playground MDP's don't *feel* realistic/relatable.  Sorry to be blunt here, but long explanations about why these MDPs are still useful don't help much in addressing this, and numerous statements about how disappointed you are to read reviewers' reactions don't either. MDPs modeling real problems are points or small clusters in the vast space of hardness dimensions. Most of this hardness space is uninteresting, and finding these interesting clusters by twisting separate knobs for each hardness dimension is almost impossible. Complaints about there being "too many" hardness dimensions are a reflection of this -- the more independent knobs there are, the harder it is to find practically interesting problem instances.

Here is another way to look at this: most practically impactful RL algorithms are those that work well on problems that *feel* realistic/relatable. Of course, each such algorithm will have its failure modes. However, even among failure modes there are "interesting" and "uninteresting" ones. Most failure modes corresponding to random hard MDPs are uninteresting.

I see at least two ways of dealing with this issue:

- Redesigning MDP Playground to keep the same or even larger number of hardness dimensions, but drastically reduce the number of knobs, so that variations across sets of hardness dimensions become correlated.

- "Selling" this work in a different way, so that the lack of realistic *feel* of MDP Playground's MDPs isn't a problem.

review_title: Key issue: high-level response to the authors' rebuttal 

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper describes a new benchmark for evaluating reinforcement learning techniques (MDP-playground). It can be seen as a toolbox allowing to generate different MDPs with different characteristics. Each MDP will then be used to probe a particular ability of learning algorithms, resulting in a comparison of methods over multiple dimensions. Proposed dimensions are reward sparsity, stochasticity, delayed reward, etc....  In addition to this toolbox, the authors also evaluate some of the classical algorithms in the domain. 

== Comments

First of all, the idea of evaluating RL techniques over multiple dimensions is very interesting, since right now the comparison of RL techniques is very weak, and providing simple tools in that direction is crucial to make  advances in the field. The MDP-playground approach is a good approach toward this goal and proposes a large number of different metrics on both continuous and discrete MDPs, making this platform the most complete in the domain. 

But I identify two drawbacks in the proposed toolbox: first of all, if many metrics are proposed, it is very difficult to know which of these metrics are really relevant, and which are not. Said otherwise, the methodology would gain if these metrics could be connected to real use-cases e.g what are the relevant dimensions underlying atari environments, robotics ones, etc... Right now, imagine I evaluate my model over all the different metrics, and compare my model to other models, I still don't know which model I have to choose for solving a concrete use-case. A second drawback is readability: the approach is somehow proposing too many metrics such that being able to understand which model is good and which model is bad is very difficult. I would propose the authors to think about organizing these metrics in a way that they can be easily presented to users (e.g using spider plots ? by using a hierarchy ? ) At last, the paper is just comparing a few models over these metrics, while I would expect to have a more complete benchmark of existing models. 

To conclude, if I really like the approach proposed in this paper, and if I think that it is a nice step toward a better evaluation of RL algorithms, I find that the paper is lacking some important characteristics to make MDP-playground really usable: i) a good way to summarize the performance of RL algorithms too many metrics allowing a good understanding of the methods ii) a comparison of more algorithms and iii) a  link between the proposed metrics and classical benchmarks.

== 
Considering the modifications made on the paper, I increase my score 

review_title: Review -- after rebuttal

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper presents "MDP Playground", a family of procedurally generated MDPs that can be used to benchmark certain dimension of difficulty considered by the authors to be challenging to current RL algorithms.  The paper presents the effects of the various perturbations to the MDP on state-of-the-art learning algorithms and discusses particular dimension of interest in the paper.  A full and exhaustive analysis of results is presented in the appendix.  The "MDP Playground" is slated to be open-sourced so that the community can benchmark against it.


Pros:
I think that high-level difficulties of MDPs are under-studied and that the over-reliance on benchmarks such as Atari or Mujoco make people look more at per-environment/game performance instead of thinking about high-level issues with the MDPs (exploration, delays et.c). Although this is done in a hand-wavy manner, all attempts at formalising this seem essential to better understand what the actual degrees of difficulty are for particular tasks and whether novel proposed approaches are really tackling the challenge they claim to be tackling.

I find the use of two procedurally generated MDP, one continuous and the other discreet, in a very simple task setup to be a good design choice, and also allows for quick iteration.

Cons:
Although this is an opinionated position, I'm not super happy with the choice of perturbations. Some are very general, such as delays or stochasticity, while others are very specific such as target radius, action max, or action loss weight.  I feel the nomenclature around the dimensions of 'hardness' (nit, perhaps 'difficulty' would be a better word here) is not very clear.  The proposed dimensions seemed to be inspired by some tasks the authors are working with, but in that case it would make more sense to ground their choice by describing the tasks and arguing why these are particularly important.  For example, target radius seems to be completely arbitrary, I could define an infinite number of reward functions that describe a goal and use all sorts of topologies to window my reward and shape it as the agent nears the goal, is this really a general problem for RL though?  I remain unconvinced.

With relation to bsuite I would have also like to see more discussion on why the additional dimensions of difficulty make sense.  For example bsuite already proposes noise as an evaluation dimension, how does MDP Playground's noise differ?  

More generally, not all dimensions were clearly described, in particular stochasticity, it wasn't clear to me how this was defined.  I would have appreciated more time spent on describing the challenges rather than the analysis of the results on all sorts of environments, in the end the core contribution here is the framework and its structure, the analysis is slightly out of scope given the length of the paper.

There seems to also be very similar work in this space [https://arxiv.org/abs/2003.11881] that also proposes an open-source benchmark, it would be interesting to compare the choice of hardness dimensions to the ones used here.

Conclusion:
Overall I think this is a good direction of work, but it is a bit too unprincipled, and the paper structure kind of confusing.  I would prefer perhaps less degrees of hardness, or perhaps a couple 'families' to make your thought process easier to understand.  Then, further discussion and grounding for each family of tasks would be great, to understand where these dimensions of hardness would manifest themselves.  Finally, spending more time on describing each hardness dimension clearly instead of compacting it all into the end of Section 2 would also make this an easier read.  

I think this will be hard to achieve for the rebuttal phase, but I encourage continued work in this domain and look forward to seeing the authors' response.

review_title: Interesting framework but choice of perturbations seems arbitrary.

final_score: rating: 5: Marginally below acceptance threshold
review_content: --------------------------------------

POST-REBUTTAL COMMENTS

As a result of the discussion the paper has improved, so I'm increasing my score. However, the core issue, that the proposed benchmarks don't seem to capture the difficulty structure of either real problems or more complex benchmarks, remains.

--------------------------------------


SUMMARY:

The paper introduces MDP Playground, a parameterized suite of MDPs with low computational requirements that nonetheless present significant challenges for existing RL algorithms. The authors argue that MDP Playground is a valuable testbed for developing and evaluating ne RL algorithms. The paper also assess how the identified dimensions of hardness that can be exercised in MDP Playground transfer to more complex benchmarks. The paper also uses MDP Playground to evaluate several rllib algorithms.


HIGH-LEVEL COMMENTS:

This work has a lot of potential. It targets an important problem in RL research: studying the behavior of RL algorithms as an environment changes along various dimensions of hardness. It is valuable to have a benchmark suite of the sort this work aims to deliver, one that allows varying these dimensions in a controlled way and consists of problems that are simple enough for debugging. 

However, in its current form this work has non-trivial weaknesses in contribution and presentation that make publication at ICLR or similar conferences premature:


1) MDP Playground's problems are completely unintuitive. They are randomly generated and aren't inspired by any real scenarios. This raises the question of how meaningful they are. In ML, it is understood from results such as the no-free-lunch theorem that no learner can do well across all possible tasks, and the sensible approach is to make ML algorithms work well on meaningful data distributions that are encountered in reality. Unfortunately, RL as a field hasn't been good at sticking to this principle: many of its existing benchmarks, such as videogames, look "interesting" and difficult, but in a very different way that real decision-making scenarios are. MDP Playground exacerbates this issue -- since its MDPs are randomly generated and don't have a natural interpretation, it's difficult to get even an intuition for a good behavior in them, and difficult to understand how to generate problems that that have a combination of hardness along different dimensions that is representative of realistic scenarios.

A case in point is the paper's omission of MDP non-ergodicity (and presence of constraints on the desired policy as a common real factor that causes non-ergodicity) from its list of hardness dimensions. In reality, and even in some existing benchmarks, the learner can reach irrecoverable (absorbing) failure states, such as robots damaging themselves or objects they interact with, unless they are very careful. There are goal-directed MDP models with such states -- see, e.g., reference [a] at the end of the review -- and learning in their presence in realistic scenarios requires costly resets -- see, e.g., reference [b]. MDP Playground doesn't help with researching this aspect, e.g., by having knobs for probabilities of entering such states, penalties for doing so and the cost of recovery, despite it being ubiquitous in reality.

Another major omission is the fact that in reality agent actions have durations that can make it very hard to learn a policy within a given time budget. The existing benchmark doesn't allow studying the effects of action duration on learning time. 

Given these gaps, I doubt that MDP Playground in its current form adds much value over the existing RL benchmarks, which have some drawbacks but have interpretability as a big asset for debugging.


2) The paper's analysis of dimensions of hardness is quite unprincipled, contrary to the paper's claims. What makes many decision-making problems (both existing ones and those introduced in MDP Playground) hard is partial observability, but the paper never formally states what POMDPs are, nor even mentions this term. If it defined POMDPs formally, the incorrectness of some of the statements the paper makes about problems with partial observability (see the detailed comments below) would become obvious, and the connections between partial observability and hardness would become much clearer mathematically. See, e.g., reference [c] for a formal but accessible treatment of POMDPs.



TECHNICAL ISSUES/RELATED WORK:

-- In the intro, the paper claims that "partial observability [is] when the underlying environment is assumed to be an MDP, however, the state formulation, i.e., the observation used by the agent is not Markovian". This is an extremely inaccurate statement at best. In POMDPs, observations are Markovian -- their probability depends only on the current (hidden) state. "State formulation" is also Markovian, as it is fully observable MDPs. So are the belief states. What is non-Markovian in POMDPs is the optimal policy w.r.t. the observations: an optimal policy can depend on the entire observation history. However, again, each observation history maps to a belief state, and in the belief state space the optimal policies are Markovian.


-- The same goes for several other statements, e.g. "performance degrades in environments where the delayed reward induces partial observability and hence makes the state used by the algorithm non-Markovian". How can delayed reward introduce partial observability? How can partial observability make "the state used by the algorithm" (an imprecise term in its own right) non-Markovian?


-- Out of the dimensions of hardness the paper does identify, why is "sequence length" a distinct dimension, rather than being an instance of reward delay or reward sparsity?


-- In the related work, a notable omission is reference [d], which looks at aspects that MDP hard and analyzes existing benchmarks w.r.t. those aspects.


-- I wasn't sure what the benefit of the "varying reprsentations" experiment that tries to enforce various kinds of invariances was. First of all, the experiment is about applying various types of data augmentation to images, not about varying representations. Second, the conclusion that "this indicates that shift and other types of invariance do not come for free and that one needs to have sufficient amount of samples for the algorithm to become invariant to the transforms we desire." is rather obvious and well-known.


-- A similar remark goes for several other experiments: varying time units, target variance, irrelevant features. Their results are completely expected, and while they might be a useful sanity check, the results description can be condensed to 1 line each and placed in the figure captions.


-- A similar comment goes for the entire content of Section 4.3 as well-- it is very verbose and can be greatly condensed and structured into a short list with bullet points summraizing the findings. 


Typos:

"Very low cost execution" --> "Very low cost of execution"


[a] Kolobov, Mausam, Weld, "A Theory of Goal-Oriented MDPs with Dead Ends", UAI-2012

[b] Eysenbach, Gu, Ibarz, Levine,  "Leave no Trace: Learning to Reset for Safe and Autonomous Reinforcement Learning", ICLR-2018

[c] Kochenderfer, "Decision Making Under Uncertainty: Theory and Application", MIT Press, 2015

[d] Maillard, Mann, Mannor "“How hard is my MDP?” The distribution-norm to the rescue", NIPS-2014
review_title: Tries to address an important issue but falls short. The presented analysis is unprincipled and incomplete.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes a suite of benchmark tasks designed to test (and possibly debug) reinforcement learning algorithms. Deemed the MDP Playground, these environments are applicable to both discrete and continuous RL agents and allow tuning of various dimensions of complexity - reward delays, reward sparsity, stochasticity, etc. The authors demonstrate their framework by evaluating the performance of many well-known RL agents across a variety of these playground environments. Additionally they conduct similar experiments on Atari and Mujoco tasks and observe similar trends in agent performance when injecting noise, reward delays, and varying action max values. Finally, the MDP Playground is very quick to run and facilitates fast experimentation.

It's my view that the efficacy of a testing and debugging suite like MDP Playground is measured by the actionable insights that can be generated with it. To this end the authors describe some findings that may be applicable in the design of new environments (such as action max needing tuning in continuous action environments), but little is shown about new insights gained toward understanding shortcomings of existing algorithms or routes for building better RL agents.

Additionally, why do we believe that the structure of the MDPs generated by MDP Playground will resemble that of the problems that RL practitioners in the community are interested in solving? Specifically for discrete environments having a completely connected transition function consisting of 8 states and 8 actions seems like it may not resemble more complicated environments like Atari. Similarly, moving a pointmass in a 2D plane likely has many differences from learning how to locomote a multi-jointed robot. It's not clear that insights gained from Playground environments will transfer to more complex environments.

Tangentially, it might be interesting to have a tool that could analyze a particular complex environment and automatically generate a corresponding Playground MDP that would somehow capture the same measures of difficulty, such that agents could be debugged/optimized in this low-cost environment before being transferred back to the complex environment.

I have read the author response and stand by my original score of the paper.
review_title: What insights can be gained?

Meta-review: I thank the authors for their submission and very active participation in the author response period. The reviewers and I acknowledge the importance of designing toy environments that allow the community to systematically investigate strengths and weaknesses of RL approaches. That said, the reviewers have criticized that it is unclear whether experiments on the proposed toy MDPs would transfer to more complex standard RL benchmarks (such as Atari) [R1 & R2], and that the proposed metrics and axes of variation seem not well motivated or systematic [R1,R2,R3 & R4], thus casting doubts regarding what insights the community will be able to gain from experiments on MDP Playground. In particular, I agree with the reviewers R1's and R4's assessment that proposing many dimensions of variation, even if they are orthogonal, without a well formulated motivation and grounding in actual tasks the community cares about is not particularly helpful for advancing our understanding of current challenges in RL. Post rebuttal, R2 and R4 stand by their strong stance against acceptance; and R1 has increased their score as a result of the improvements of the updated paper, but they still lean towards rejection. Thus, I recommend rejection.
Decision: Reject