Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies representation learning in low-rank MDPs. In low-rank MDPs, the transition model $T(s' \mid s, a)$ can be expressed as a low-rank decomposition $T(s' \mid s, a) = \mu(s')^\top \phi(s, a)$ and similarly the reward model $R(s, a) = \theta^\top \phi(s, a)$. The proposed approach SPEDER takes an SVD approach to learn the representation $\phi$ as opposed to performing maximum-likelihood estimation used in prior work. The paper claims that this leads to a simpler optimization. Once $\phi$ is learned, the approach closely mimics existing work in using elliptic bonus, and planning a policy using the learned model with bonus. 
strength_and_weaknesses: Strength:

1. Low-rank MDPs are widely studied and the present paper proposes a new approach that claims to be more computationally-efficient
2. Experiments and theoretical statements show promise of this approach

Weakness:

1. It is unclear if the proposed approach is more efficient than RepUCB. For example, RepUCB does not use partition function since the model class is assumed to be normalized. Is that not possible in practice? The objective proposed in the paper seems quite complex and hard to optimize. While experiments show that it can be optimized, certain gaps exists between theory and practice which makes it hard to understand to what extent, Algorithm 1 is tried empirically. E.g., Algorithm 1 says that policy is found by using model-based planning on $\hat{P}$, but the paragraph on the requirement on $\hat{P}$ suggests that planning is done somehow using the replay memory data. A pseudocode of the algorithm that was run experimentally would be helpful.  

2. The paper does not present all details which makes it hard to verify certain claims. To begin with, the main contribution is the SVD approach described in Equations 6 and 7. However, the very first line uses a notation that is not defined. Specifically, what is meant by $\langle P(s' \mid s, a), \phi(s, a) \rangle_{\rho_0}$. Normally, one uses $\langle x, y \rangle_A$ to denote $x^\top A y$ which is an inner product if $A$ is a positive definite.  However, I am not sure how $\rho_0$ is represented as a $S \times A$ matrix. Is it diagonal with $\rho(s, a)$ as diagonal entries? Similarly, the explanation of Equation 7 can be further expanded. 

3. Lastly, even though the paper aims to improve upon algorithms like RepUCB, FLAMBE, and MOFFLE; not even one of these algorithms is experimentally tried. If these algorithms are impossible to try experimentally, then the paper should discuss why this is the case. Otherwise, including their performance will help understand the effectiveness of SPEDER. 
clarity,_quality,_novelty_and_reproducibility: Clarity/Quality/Question:

1. Adding a pseudocode of the algorithm that was ran experimentally would improve clarity. At the least, the empirical version of Equation 10 that was tried should be included. 

2. Adding more details for Equation 6 and Equation 7, and defining notations would also help clarity.

3. Please explain how adding Equation 11 ensures that $\hat{P}$ is a valid probability distribution?

4. How is planning performed? If $\hat{P}$ is not used for planning, as it may not be a valid distribution, then how is the replay dataset used to perform planning? 

Novelty:
The paper is very close to prior work on low-rank MDPs such as RepUCB in how the data is collected and elliptic bonus-based planning is done. However, the proposed representation learning approach as given by Equation 10 is novel. Further, the paper includes experiments unlike prior work. 

summary_of_the_review: I am currently leaning towards a tentative score of weak reject due to a lack of clarity about the algorithm that was empirically run, and questions regarding both empirical and conceptual differences between RepUCB and SPEDER. Including empirical performance of RepUCB, or adding clarity on why Equation 10 is easier to optimize than the MLE objective in RepUCB, would most influence the score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides a novel method of spectral representation learning that is compatible with stochastic gradient descent, allows for sample efficient online exploration, and 

A key novelty is that inter-state dependence is avoided by extracting spectral features some a policy independent state transition operator.

The paper provides analyses generalization bounds and sample complexities of the method.

strength_and_weaknesses: ### Strengths
- There is a good introduction to the spectral decomposition view. 
- Good theoretical analyses.
- Fair literature review, with a description of why the present work is needed.
- Remark on model based variant of this work was interesting to see.
- Algorithmic steps are well clearly.


### Weaknesses
- The paper can be a little dense to read, but this could be because of the subject matter at hand. 
clarity,_quality,_novelty_and_reproducibility: ### Clarity
The paper is sufficiently clear given the density of the problems it tackles.

### Quality
The paper and research is of good quality. Some questions:

### Novelty
This is novel analysis, to the best of my knowledge.

### Reproducibility
Hyperparameters and experimental setup seem to have been provided. However, open sourced code would have been nice to see (I couldn't find any links in the paper).
summary_of_the_review: Based on my limited understanding of the related work in this line of thinking, I believe that this is good research. The background theory is well described, along with a good literature review. The algorithmic details of the method, as well as the theoretical analysis are presented well. I did not check the correctness of these analyses however.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a novel objective, Spectral Decomposition Representation (SPEDER), that factorizes the state-action transition kernel to obtain policy-independent spectral features. The authors show how to use the representations obtained with SPEDER to perform sample efficient online and offline RL, as well as imitation learning. Moreover, the paper provides a thorough theoretical analysis of SPEDER and empirical comparisons on multiple RL benchmarks, demonstrating the effectiveness of SPEDER.
strength_and_weaknesses: The paper seems to contain interesting results. 
Some typos need to be corrected, for example, "sample" => "simple in Introduction.
The presentation can be modified in order for the reader who is not familier with representation learning. 
For example, what is the difference between representatoin learning and RL with function approximation? 
clarity,_quality,_novelty_and_reproducibility: The paper seems to contain interesting results. 
The paper needs to be clarified more in order to improve the readability.
Overall, the paper is well written, and it clearly compares the proposed method with existing ones through numerical examples. 
summary_of_the_review: The paper proposes a novel objective, Spectral Decomposition Representation (SPEDER), that factorizes the state-action transition kernel to obtain policy-independent spectral features.
Overall, the paper is well written, and it clearly compares the proposed method with existing ones through numerical examples.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The main contribution of this work lies in proposing the Spectral Decomposition Representation that can extract a state-action abstraction from the dynamics to obtain policy-independent spectral features. This work provides rigorous theoretical analyses and sufficiently extensive empirical evaluation. 

After reviewing the authors' rebuttal, the reviewers agree that (A) the contribution of this work is novel and interesting.

The reviewers have also raised (B) the concern of readability/clarity of presentation, especially from Reviewer uUqZ. The authors have since revised their manuscript to address the reviewers' concern adequately.
justification_for_why_not_higher_score: See the concern (B) above.
justification_for_why_not_lower_score: See the reason (A) above.
Decision: Accept: poster