Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose an approach to abstraction in reinforcement learning. The proposed approach starts with a coarse state abstraction and iteratively refines it. The basis for the refinement is the dispersion in the Q-values as the agent continues to learn. The approach is empirically evaluated in three grid-based domains (Office World, Taxi World, Wumpus World) and one domain with continuous state variables (Water World).

strength_and_weaknesses: Strengths: Abstraction in reinforcement learning is an important area of research; the general approach explored here (iterative course-to-fine refinement of the state space) is plausible.

Weaknesses:

-- Some critical parts of the algorithms are not fully specified. These include how to determine whether M needs refinement (line 11 in Algorithm 2), how to determine whether a state is unstable (the authors note that this is "based on the dispersion of Q-values"), and how to determine which variables are accountable for the unstable state. These issues are very briefly discussed at the end of Section 4 but are not fully specified. 

-- The experimental results do little more than present performance metrics. Furthermore, they treat the proposed algorithm as a monolithic structure, without any exploration of its individual components, of the impact of specific algorithmic choices (versus plausible alternatives), and the sensitivity to any parameters. 

-- While experimental results are presented in four different domains, three of these domains are very similar to each other (grid-based environments with additional variables). 

-- The computational complexity of the approach has not been explored.

clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is generally clear. 

Originality: The general idea (iterative course-to-fine refinement of the state space) is an old one. The main contribution of the paper is the specific approach taken but I find that some critical elements of the approach is not fully clear. These include how to determine whether M needs refinement (line 11 in Algorithm 2), how to determine whether a state is unstable (the authors note that this is "based on the dispersion of Q-values"), and how to determine which variables are accountable for the unstable state. These issues are very briefly discussed at the end of Section 4 but are not fully specified. 

Quality: Experimental evaluation is on a rather narrow range of environments and does not go into much depth. 

The experimental results do little more than present performance metrics. Furthermore, they treat the proposed algorithm as a monolithic structure, without any exploration of its individual components. 

For example, it would be useful to see more detail on how to determine whether a state is unstable. The authors note that this is "based on the dispersion of Q-values" and very briefly discuss a possible approach at the end of Section 4. It would be useful to study this aspect of the algorithm in isolation, testing a variety of candidate mechanisms. 

While experimental results are presented in four different domains, three of these domains are structurally similar to each other (grid-based environments with additional variables). In order to evaluate how widely useful the proposed approach might be, it would be useful to see experiments in a broad range of domains. 
summary_of_the_review: The paper presents a plausible approach to an important problem in reinforcement learning. However, important algorithmic components are not fully specified. Furthermore, the experimental evaluation is narrow in scope, both in the types of domains tested and in the analyses conducted in each domain. As a result, the strengths and weaknesses of the algorithm are not adequately understood.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a method which divides the state space into discrete “abstractions”, based on variance of the state action values.  They compare their method to several baselines.

strength_and_weaknesses: Minor nitpick: in the definition of \mathcal V, doesn’t the notation i \in [1, n] imply that i takes a continuous range of real values in that range?  Wouldn’t it be more correct to write {1, 2, …, n}?  (Please ignore this if I’m incorrect.)

Definition 5: I think there may be a few errors here.  After the first “denoted as”, there are two a’s (shouldn’t there be an “a” and a “b”?).  Also, are l_a and l_b defined?  I’m aware of the definition above where they are a scalar lower bound of an interval for a theta_i, but that does not seem their usage in this definition.

Strengths:
- This paper was exceptionally clear and well-written.
- The included code is a nice addition; it appears to be well-organized.

Weaknesses:
1. Minor weakness: I believe the paper overstates the general utility of this approach.  For example, consider a task in a 3-D world where the observation is pixel input.  Clearly, the authors’ approach will not be helpful in this case, since DAR+RL will attempt to divide the world up based on uninformative ranges of individual pixels.  This concern is not limited to pixel input.  This is not to say that this approach is not a valuable contribution, but I wonder whether many real-world problems with high-dimensional state spaces can be made more tractable by this approach.  Weakness 4 below is closely related to this. I am concerned that the authors are overselling their approach and sweeping its limitations under the rug.  Instead, I’d advise frankly discussing these limitations, discussing future work which might allow one to overcome them, and evaluating on more diverse environments (again, see weakness 4).
    - Of course, DAR+RL will be more effective if the state/observation is designed to be more suitable to it (e.g., use x/y coordinates rather than pixel inputs), but hand-designing the state/observation like this defeats the intended purpose of DAR+RL.
2. Minor weakness: Given the well-known high variance between RL runs, 10 trials is not ideal to demonstrate the claims being made.  However, I am not overly concerned about this in this case, given the plots (which seem to show clear trends) and the more pressing concerns below.
3. Major weakness: Not all hyperparameters are included (particularly the architectures’ hyperparameters, but also details about the optimizers, etc.).  This is closely related to weakness 5.
4. Major weakness: All domains are some variety of 2-D gridworlds.  This limits the convincingness of the empirical work and is closely related to weaknesses 1 and 5.  It also makes the paper’s claims about “high-dimensional tasks” unconvincing, since these environments all seem to have 1-2 dozen state dimensions at most, while a large proportion of modern RL focuses on tasks with hundreds or thousands of state or observation dimensions.  One fix for a future submission would be to include higher-dimensional (non-gridworld) tasks such as mujoco domains to the experiments.
5. Major weakness: Some important details about the baselines are unclear to me.  Particularly, the details of the architectures used are missing.  I’m not sure any of the baselines are fair because:
    - The tabular Q-learning approach will, of course, not perform well given so many possible states.
    - The following bullet points assume that the other methods all took real-valued x and y inputs to the neural nets (the same type of inputs that DAR+RL received), and used some standard deep architecture from stablebaselines3.  I believe all baselines other than tabular Q-learning fall into this category.  If this is not the case, the situation could be better or worse, depending on the details:
        - The deep RL approaches will not perform well without hyperparameter tuning (which seems to have been done for DAR+RL, but not the baselines).
        - Worse, these architectures are designed for much more complex environments, and so will perform relatively poorly in terms of data efficiency compared to a “quasi-tabular” approach such as DAR+RL, since their networks are excessively large and overparameterized for these type of problems.  Better baselines might be linear function approximators (see the Sutton and Barto book, 2nd edition, for a good list of effective ones) or perhaps very small neural networks, since these approaches can be expected to learn these these simple environments, with their relatively-small-number-of “continuous” state dimensions (most are not truly continuous, but the agents observe continuous values), more efficiently than large deep nets.
6. Minor weakness: I do not believe the details of the UnstableState function (line 14 of algorithm 2) used in the experiments were given.  These details, including relevant hyperparameters, should be provided.

clarity,_quality,_novelty_and_reproducibility: This paper was very clearly written.  It is novel to the best of my knowledge.  However, I have concerns about the quality; see above.
summary_of_the_review: This paper is very well-written.  However, despite all the notation, its contribution is entirely empirical, and I have concerns about the quality of the empirical work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper aims at iteratively computing an abstraction based on the dispersion of Q-values for states that have been aggregated together.  The paper describes the algorithm with a formalization and some pseudo-codes. The algorithm is tested on different discrete and deterministic grid-world environements.
strength_and_weaknesses: Strengths:
- The paper makes use of simple examples to motivate the approach.

I have two main concerns. 
- My first concern is related to the writing of the paper and the lack of clarity with respect to some of the key components.
- Second, I have doubts about the actual procedure that the paper describes.
clarity,_quality,_novelty_and_reproducibility: CLARITY/QUALITY:
The paper lacks clarity in the description of the approach. 

A few key strange elements:
-The paper is unclear about how the interleave between Q-learning and refinement should happen. This is also not clear in the description of the algorithms. For instance "Then, the learning phase of DAR+RL starts by employing the Q-learning routine (Lines 2 to 10 in Alg. 2)" does not seem to actually describe what is going on in the algorithm from lines 2 to 10 where we can't see any information about Q-values.
-It is also unclear why this whole procedure would be faster than learning directly without state abstractions. It seems that learning the Q-values for every refinement of the state space is a costly approach.
-The formalization of the approach (mainly starting from the top of page 5) is not clearly written. The formalization is interleaved with examples that only help moderately to understand what is actually done.

Some examples of details that are wrong or not clear:
- (section 3) The paper writes "$\mathcal T :S \times A \rightarrow [0,1]$ is a transition probability function". Mapping a state-action pair into $[0,1]$ does not look like a well-defined transition function.
- (algorithm 1) I can't understand what is supposed to mean by "1: if (∀vi ∈ s)(vi ∈ θstart) then"

NOVELTY:
-The paper does not compare with any of the methods that actually aim at doing state abstraction (it compares with Option-critic , JIRP, tabular Q-learning, DQN, A2C and PPO. 
-The authors discuss the related work, however they do not highlight why their method is different/better. For instance, the authors mention in the end of the related work section that "These methods do not consider the problem of building abstractions for stochastic planning or reinforcement learning." It seems that this paper has some of the same limitations (deterministic environment) but nothing is said about it.

REPRODUCIBILITY:
Source code does not seem to be provided. Based on the paper, I don't think reproducibility is feasible.

summary_of_the_review: I have two main concerns. 
- The writing of the paper and the lack of clarity with respect to some of the key components.
- I have doubts about the actual procedure that the paper describes (the formalization and the pseudo code do not provide enough details).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper describes a method for constructing abstraction for reinforcement-learning problems online, during learning, by pursuing a coarse-to-fine search for good partitions of state variables, which yield efficient and accurate learning.

The reviewers found the paper to provide interesting ideas, but had a number of concerns along various lines, including:
- relative similarity of test domains
- a lack of clear articulation of what properties of a problem would make it amenable to these techniques

Fundamentally, the method seems similar in spirit to a line of old work in RL, starting with Moore (PartiGame, NeurIPS 1993), and running through Will Uther's PhD thesis on tree-based approximations (CMU, 2002; or see "TreeBased Discretization for Continuous State Space RL, Uther and Veloso, AAAI98) and surely beyond.  It would be important to compare and contrast your method to these strategies.
justification_for_why_not_higher_score: None of the reviewers was enthusiastic, the paper didn't seem conceptually hugely novel, and there were concerns about validation.
Decision: Reject