Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a novel approach to abstraction in Reinforcement Learning in discrete action spaces by construction a homomorphic representation through equivalent effect state-action pairs. The approach constructs forward and backward models which allow it to reduce the complexity of the value function representation by mapping equivalent state-action sets to canonical entries. The aim is to increase sample efficiency in subsequent learning tasks and the potential benefits are demonstrated in a number of standard experiments in maze and simple control environments. 
The main contributions of the paper are the introduction of the new approach which allows the construction of a homomorphic abstraction (although a somewhat limited one) largely on-line from simple transition experiences without prior knowledge of the complete transition dynamics. While somewhat limited in its applicability due to its limitation to deterministic transition tasks, it introduces an interesting concept and illustrates its potential benefits in a number of experiment domains.
strength_and_weaknesses: The paper presents an approach to constructing a homomorphic abstraction by identifying equivalent effect state-action pairs and using these to map to a canonical element, thus reducing the complexity of the value function and thus potentially accelerating learning of policies on the abstract representations. The strengths of this approach lie in the ability to derive the abstraction form a set of environmental experiences without the need for a prior model. In addition, the presented model only requires one step equivalences for its construction, making it more applicable for on-line learning settings. However, the significance of this is somewhat limited by the prior assumptions on the task, namely that rewards are purely a function of the state (making it difficult to account for variable action costs, except by embedding them in the state through something like a remaining/consumed energy value), the need for deterministic transitions, and the assumption that an inverse model exists in most situations (i.e. that in most situations a state can be reached using every action), which seems to potentially significantly limit the application domain of the method.
While the authors include a discussion of some of the limitations at the end of the paper, it would be useful if some more general discussion could be included earlier on that detailed the effect of these limitations and in particular what it implies for the types of problems that the method is applicable to. Also, it might be worth discussing and considering whether some of the assumptions can be softened to extend the applicability of the approach. 

Another limitation of the homomorphism approach in this paper compared to the more general homomorphism framework seems to be that it can not easily abstract in situations where different regions of the state space have similar dynamics, i.e. where different task instances exist within the overall state space. This is an important property to extract if the learning agent might be placed into different versions of an environment and asked to solve the same task as shown in previous Homomorphism work for policy generalization such as [Ravindran, Balaraman, and Andrew G. Barto. "Model minimization in hierarchical reinforcement learning." International Symposium on Abstraction, Reformulation, and Approximation. Springer, Berlin, Heidelberg, 2002.] of [Rajendran, Srividhya, and Manfred Huber. "Learning to generalize and reuse skills using approximate partial policy homomorphisms." 2009 IEEE International Conference on Systems, Man and Cybernetics. IEEE, 2009.]. While alluded to in the limitations section, a further discussion of how the presented approach might be combined with other homomorphism concepts would be useful to the reader to assess the full potential of the technique.

There is a typo in the first paragraph of Section 4.3: ""...an agent much chase..." should be "...an agent must chase..." 
clarity,_quality,_novelty_and_reproducibility: The paper is overall well written and easy to understand. There are, however, a few smaller issues. The first is that it is unclear why both the Algorithm I and the results for the Minatar experiments have been moved into the appendix while their description and the reference to them are in the main text. In particular the absence of the algorithm in the main text near the reference (without explicitly stating that it is in the Appendix) may cause the reader to pause. It would be better if both of these items would be moved in line with the text and the descriptions to make it easier for the reader.
The approach is novel and while somewhat limited in its application in the current form (see comments above), it provides an interesting direction for on-line increase of sample efficiency in RL.
The paper does provide a good description of the experimental settings and listing of the hyper parameters in the Appendix make it easier to reproduce the results. 
summary_of_the_review: The paper presents a novel approach to learn a simple (and somewhat limited) homomorphic representation for a problem using equivalent effect state-action pairs in order to reduce small efficiency in RL. This approach allows the abstraction to be learned efficiently on-line form a small number of transition experiences, making it easily applicable to some practical problems. While the underlying assumptions on the problem (reward only depends on state, deterministic transitions, existence of an inverse transition function in most states) somewhat limits the applicability (and thus the significance), the approach points out a potentially useful direction for abstraction work and could thus lead to beneficial follow-up work. This make it, in my view, of sufficient interest to the community to warrant publication.
The experiments in the paper illustrate the potential benefit of the technique.
The paper also includes a discussion of limitations and potential extensions. This discussion should be slightly further extended (and part of it moved earlier in the paper) to make sure that readers can fully understand the limitations of the presents part but also be able to assess possible extensions in the future to mitigate these limitations.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper attempts to learn a state abstraction based on MDP homomorphism. The goal is to reduce the size of state-action space and allow for faster RL. The proposed approach learns a backward model $(B)$ and a forward model $(F)$. The forward model $F(s, a)$ is trained to predict the next state given the current state $s$ and action $a$. The backward model $B(s', a)$ is trained to predict the previous state given the current state $s'$ and last action $a$. The state abstraction mechanism maps a state (or a state-action?) pair to a value $\sigma(s)$ such that:

$\sigma(s) = B(F(s, a), \bar{a})$,

where $\bar{a}$ is an action called canonical action. Algorithm 1 shows that this action is chosen arbitrarily.  Using this approach, one can do Q-learning on $\sigma(s), \bar{a}$ values instead of $s, a$. A series of experiments on tabular and function approximation settings are presented that show promise of this approach. 
strength_and_weaknesses: Strength:

1. State abstraction is an important topic
2. This paper presents experiments on both tabular and non-tabular settings.

Weakness:

1. It is unclear what is being learned by $\sigma(s)$? Does it satisfy Equation 3? What is the intuitive idea of $\bar{a}$? Why is it chosen arbitrarily? What theoretical properties does $\sigma(s)$ satisfy? There appears to be a conceptual gap in the motivations in the first two pages, and the way $\sigma$ is extracted from combining the forward and backward model. I hope the discussion period will help make this clearer. 

Further, the paper currently lists handwavy statements such as:
Figure 2 caption, _"we take advantage of the fact that state-action pairs that lead to the same state usually have equivalent values."_
and the paragraph before Section 4 says _"Lastly, we have assumed that for every state-action pair at least one equivalent canonical state-action exists, which is often true but not guaranteed"_

Can these conditions be expressed formally? and in what realistic settings are these conditions satisfied? 

2. The proposed objective performs generative modeling which requires more samples to learn accurately. A more sample-efficient approach would be to do multi-class classification over a small label space, as it done by action-prediction or contrastive learning-style approaches.

3. The paper ignores related work on learning state abstraction with function approximation including autoencoders, contrastive-learning approaches. A few examples are listed below, but there are many more:

- (Autoencoder) #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning, Tang et al. NeurIPS 2017
- (Contrastive Learning) Kinematic state abstraction and provably efficient rich-observation reinforcement learning, Misra et al., ICML 2020
- (Generative Modeling) FLAMBE: Structural Complexity and Representation Learning of Low-Rank MDPs, Agarwal et al., NeurIPS 2020
- (Action prediction) Planning from Pixels using Inverse Dynamics Models, Paster et al., ICLR 2021

The paper also misses related work that learn mapping between a given MDP and an abstract MDP. For example, see

- Provably Efficient Model-based Policy Adaptation, Song et al., ICML 2020
- Provably Sample-Efficient RL with Side Information about Latent Dynamics, Liu et al, NeurIPS 2022

While the proposed approach is new, it will nevertheless benefit readers to situate the work in the literature. 

4. Algorithm 1 is very hard to understand. See clarity below.
clarity,_quality,_novelty_and_reproducibility: Clarity: 

1. Clarity is needed on whether it is $\sigma(s)$ or $\sigma(s, a)$ in Equation 6. The right-hand side has $a$ but left-hand side has $s$. The main text says $\sigma(s)$ but Algorithm 1 uses $\sigma(s, a)$. Tying the examples presented on the first two page to Equation 6 will help a lot.

2. What is the idea of canonical action? 

3. In Algorithm 1, when will the condition $\bar{s} = \sigma(s, a) \in S$ not be true? Doesn't $\sigma$ always output a value in $S$? And how does this generalize to function approximation setting?

4. The GreedyPolicy takes $s$ as input but the function definition of GreedyPolicy takes $s$ and $a$ as input.

Presentation

1. Consider moving a short pseudocode, particularly, for function approximation to the main paper.
2. Why do we set $s_t = s_{t+1}$ in Alg 1, when there is a for loop over $t$. 
summary_of_the_review: Lack of clarity is the main reason for my current score of reject. Based on author response and discussion period, I'll consider changing my score. In particular, clarity on what $\sigma$ is learning will be most helpful.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a new way to construct homomorphism for MDPs by a forward model and a backward model. Using the forward and backward models and a canonical action, a state-action pair is mapped to an equivalent canonical state-action pair and the effective size of state-action space is reduced. Empirical experiments demonstrate that the proposed method could learn faster than the baselines.
strength_and_weaknesses: Strength
- The idea of aggregating state-action pairs to an equivalent state using a canonical action is very interesting. For some simple problems this can indeed efficiently reduce the size of the equivalent state space for RL algorithms.

- Experiments show that the proposed method could potentially learn faster.

Weakness
- Although the idea of using the forward and backward models makes sense in simple deterministic environments, one cannot get these models for typical stochastic environments. Furthermore, even in deterministic environments, since multiple state-action pairs could lead to the same state, the inverse image of the next state is not a singleton in general. When the inverse image of the system dynamics is not a singleton, it is impossible to learn such a backward model as described in the paper. There may be conditions under which the described forward and backward models exist, but there are no discussions about in which cases is it possible to learn the forward and backward models in the paper.

- The main feature of the approach is to learn a MDP homomorphism with a smaller state space, but there is no analysis on whether the resulting learned model actually provides a simpler MDP homomorphism by either analytical or numerical evaluation. For example, in the tabular maze experiment, what is the equivalent size of state space after the homomorphism map compared with original size?

- Half of the numerical experiments are done with the assumption of the given environment model. It is perfectly fine to consider the situation when the model is given and try to learn a good performing policy. But in this case, comparison with prior methods with the knowledge of model is then necessary, and none is provided in the paper.

- For the predator prey environment, since the proposed method uses 170 episodes to learn the forward and backward models, it is actually not fair to claim that the method outperforms vanilla DQN. When compared with prior homomorphism methods like PRAE, since the number of samples used in learning the homomorphism are different for the methods, one cannot draw the conclusion that the proposed method is indeed more sample efficient.
clarity,_quality,_novelty_and_reproducibility: The paper is generally well written and easy to follow, but the limitations of the method are not clearly discussed.
summary_of_the_review: The idea of using forward and backward models to construct MDP homomorphism is interesting, but no details discussion on when is it possible to learn these forward and backward models, and the numerical experiments may not be enough in demonstrating the benefits of the proposed method.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an approach to MDP state abstraction based on the idea of forming equivalence classes of state-action pairs that must have the same value function, and thus can be limped into a single abstract state, thus improving the sample complexity and speed of solving the resulting abstract MDP. The criterion for grouping state-action pairs into an equivalence class is whether they lead to the same successor state. Empirical verification on several well-known benchmark problems demonstrate that indeed learning on the thus abstracted MDP is faster than on the original one. 
strength_and_weaknesses: The paper addresses the problem of automatic abstraction of MDPs, which is a form of representation learning, and is thus very appropriate for the conference. The general approach of looking for equivalence classes is certainly sound, with a long tradition in AI and OR, and the empirical verification looks encouraging. However, I am not sure the chosen criterion for state abstraction is very widely applicable. In Section 3, on page 3, the authors state that "state-action pairs that lead to the same next state have equivalent reward functions (by definition)". This statement is questionable, and would be true only if the reward depends only on the successor state, as in the example with the mouse given. But, this is not how the reward function is defined in Section 2 - there, it depends on both the starting state and the action applied. One other special circumstance where this statement would be true is when the instantaneous reward (respectively, cost) of every transition is the same. This is true for minimum-time optimal control/decision problems, but definitely not always true. Outside of these special cases, the value function of several state-action pairs with the same successor state is not the same, so how could this approach work in such cases?

Furthermore, the method makes use of forward and backward models, which are trained by minimizing prediction errors, according to Equations 4 and 5. This also looks highly problematic. What happens if the transition probability of the original MDP is multimodal for a given state-action pair? It is well known that by minimizing MSE, the model could learn to predict a successor state that is even impossible according to the original transition distribution, because it lies somewhere between the modes of that distribution. If my understanding is correct, all environment the proposed algorithm has been tested on are deterministic, so this would not be a problem for them, but what happens when they are stochastic, with multimodal transition distributions?

The same argument applies to the backward model - in case of stochastic environments, it would be possible to have multiple origin states s that, if action a is applied, will result in the same successor state s'. If all such experienced transitions are used for training the backward model for the pair s',a using MSE, it will learn to predict the average of the origin states s, which might not coincide with any of them. Wouldn't that distort significantly the transition function of the abstracted MDP?

          
clarity,_quality,_novelty_and_reproducibility: I believe the idea is novel and interesting, and certainly appealing due to its simplicity. I have significant doubts about how general it is, though. The empirical verification seems to be reproducible, as all Python code for the models and algorithms has been provided.
summary_of_the_review: I find the idea of using the principle of equivalent effect abstraction quite appealing, but am not convinced that it is applicable to general MDPs with stochastic transition functions. It would be helpful if this is investigated empirically. Nevertheless, even if the method is applicable only to problems with deterministic dynamics, it would still be a valuable addition to the toolbox of practitioners. (But, its limitations should be clearly stated.)
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The reviewers have brought up issues regarding the restriction of assumptions, the clarity of the paper, as well as several other issues. The authors have significantly revised the paper to answer the reviewers' comments. Although some of the concerns are addressed or explained, a more careful reevaluation by several reviewers is needed.

At the end, we have two positive reviews with the score of 6 and two negative reviews with score of 3.

Given the current scores, the volume of revisions in the paper, and the restriction of the assumptions and the setting when the method works, I believe the paper is not suitable for publication at the moment.
justification_for_why_not_higher_score: The method is based on very restrictive assumptions. The scores are quite low.
Decision: Reject