Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies representation learning in the context of reinforcement learning, and observes that under some noise assumption, the linear spectral feature of corresponding Markov transition operator can be obtained in closed-form. Then the paper proposes the so-called SPEDE algorithm that enjoys good theoretical guarantee and empirical results.
main_review: The paper studies an important problem in reinforcement learning, and shows some interesting observations. Here are some of my comments and questions.
1. In my opinion, this paper is more like one on model-based learning since Equation (5) is the main structure studied in the paper. It is remarked that "similar observations also hold for large amounts of distribution". I am wondering whether the theoretical results could be straightforwardly extended for other distributions other than Gaussian distribution.
2. I think a more detailed comparison to [1] in terms of technical novelty might be necessary. In my opinion, [1] focuses on frequentist regret bound, and thus proposes a UCB-like algorithm that requires an oracle. For computational efficiency, [1] also proposes a Thompson sampling (TS)-like algorithm that does not need such an oracle. In my opinion, it might be straightforward to show the Bayesian regret bound for this TS-like algorithm using the results in [1] and the standard and well-known results in [2]. In terms of proving Bayesian regret bound, could the authors elaborate more on the technical contributions beyond the existing literature?
3. In terms of the transition dynamics, I think it would be beneficial to the readers if the authors could say more on the dynamics that covered by the paper but not covered by [1]. In my opinion, providing some (simple) examples could be helpful.
4. Could the authors elaborate more on why the proposed algorithm decouples the exploration and representation learning since I think there is still longitudinal coupling across time-steps? Is this decoupling similar to that of Neural Linear algorithm in [3]?


[1] Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, Wen Sun. Information Theoretic Regret Bounds for Online Nonlinear Control. NeurIPS 2020.
[2] Daniel Russo and Benjamin Van Roy. Learning to Optimize via Posterior Sampling, Mathematics of Operations Research, 2014.
[3] Carlos Riquelme, George Tucker, Jasper Snoek, Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling, ICLR 2018.
summary_of_the_review: I think this is an interesting paper, and I would like to understand better the technical novelty.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed a practical exploration algorithm for finite-horizon RL problems and provided a theoretical guarantee for its algorithm when the transition kernel of the RL problem can be encoded with RKHS. It also conducted experiments to validate its algorithm.
main_review: Strength. This paper extended the model in LC3[1] to kernel setting, and it also used Lemma 16 to remove the dependability on the global Lipschitz constant. It also conducted experiments to show that its algorithm is practical and efficient.

Weakness. After going through the proof, I notice that the regret bound is proportion to $\sigma^{-1}$, which means that the bound will be bigger when the noise level decrease and should be emphasized in Theorem 5. Here $\sigma$ is the noise level.

Although there are some details in Section 3.2, there should be more detail about the posterior sampling in the experiments section since this paper claimed to provide a practical algorithm and this part is not trivial. 

[1]. Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Information-theoretic regret bounds for online nonlinear control. arXiv preprint arXiv:2006.12466,
2020.
summary_of_the_review: This paper is significant, in the sense that it extends LC3[1] and provides a theoretical guarantee for a setting that is more complicated than [1]. It also uses a novel technique to utilize the noise in transition to remove the dependability on the global Lipschitz constant. Although the dependency on noise might have room for improvement, I think it is a good paper and could be accepted.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of learning representations for RL. On the theory side, the paper considers the setting where the state-transition is a nonlinear function of the past state-action plus additive noise, and develops a no-regret algorithm. On the empirical side, the paper shows that an adaptation of this algorithm on real-world RL tasks could perform better than existing model-based algorithms.
main_review: **Strengths**

I think overall this paper considers an interesting problem (learning representations) that is of interest to the community, given that a major part of the RL theory literature focuses on learning with a known linear representation or structured function class, and much less is known when it comes to learning the representation. 

It is a plus that this paper contains empirical results too on real RL benchmarks, which I do appreciate as for a paper with a bulk part being theoretical contributions. The experimental results seem mostly convincing to me.

**Weaknesses**

One of my main concerns about the theory part is that this theory may be a somewhat cute but very specific consequence of the Gaussian noise assumption. It is kind of hard to tell how generalizable this result is (or how significant it is as a representation learning result), as the Gaussian structure (density of the noise admits this very form) is critically used instead of just for some concentration purposes. Though, I should remark from a more practical perspective I’m not that worried about using it for real-world problems, where it is hard to justify most structural assumptions anyway. 

Also, from the current paper’s presentations, I find it quite hard to situate the current contributions in the context of representation learning theory in RL, and compare with related work. As concrete examples,

--- Section 3 (before 3.1) makes caveats of two prior techniques for representation learning: MLE, and policy cover technique. These techniques are discussed quite vaguely and not presented in math. Consequently I couldn’t find the key observation in 3.1 very motivated (since I do not see what the prior methods exactly are). 

--- The real problem setting considered in this paper appears only in equation (5) and is not emphasized as a problem setting. I suggest maybe Section 3 could begin with talking about this setting, then talk about the existing approaches (with some math that at least hints what those methods are and why the authors think they are not sufficient), and then come to Section 3.1. 

--- The authors discussed Theorem 5 in the context when $\mathcal{F}$ is a linear class; in this case I believe the model is *not* equivalent to linear MDP, could the authors comment more on what the difference is? Also, how does the present result compare with Agarwal et al. (2020) and Modi et al. (2021)?

--- Theorem 5 uses a Thompson sampling algorithm but the proof sketch mentions connection to a certain UCB algorithm. Are there reasons for not using UCB directly in Algorithm 1?

--- Could the authors discuss a bit more in detail how the proof compares with the standard Eluder Dimension proof (e.g. of Wang et al.)? Currently the proof sketch does not say much where the bounded Eluder dimension is used, and how is the application different from the existing Eluder dimension proof. 

--- (This one is about experiments) When deployed into practice, the main difference between SPEDE and existing model-based algorithms is just that the parametrization (3) and (4) is used? (aside from SGLD as for approximate Bayesian inference + Gaussian policy parametrization, as the authors mentioned).

With the above questions in mind, I am left confused about the concrete novelty in the proof techniques or problem settings, and at most left with the impression that the result may be new but not sure how exactly it compares with prior work. 

**Other comments**

--- The “practical issues in implementing the proposed SPEDE”: maybe this paragraph can form a standalone section after Section 4, since logically, the practical implementation tricks are not used in the theoretical results?

--- “expected regret” I believe it is usually called the Bayes regret in the thompson sampling literature?

--- Table 1, SPEDE-REG on MountainCar, the number should not be bolded?

summary_of_the_review: Overall, I think this paper makes interesting contributions on both the theoretical and empirical end of representation learning within RL. However, significant work needs to be done in order to clarify its problem setting, results, and position within related work.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the single reward episodic MDP problem with the model-based TS algorithm. Assuming the given model class satisfies realizability, regularization property, bounded Eluder dimension, low covering number, and the true dynamics is the stochastic control model under gaussian noise transition (eq 5), the authors show the polynomial Bayesian regret guarantee. In addition, experiments on OPENAI MuJoCo is conducted.
main_review: # Clarity and writing #

My first major comment is about clarity and writing. This paper emphasizes that the algorithm is doing representation learning. However, I believe that model-based learning might be more suitable for this paper. One major difference between the current paper and the prior representation learning/reward-free learning work is that the algorithm in this paper can only handle a single reward while previous model-based or model-free works can learn a representation that tackles multitasks (multiple rewards). I think such differences should be discussed in the paper. Since the algorithm can only a handle single reward, I do not see the significance and advantage of learning the "representation" (model). It belongs to the model-based algorithm where the TS agent tries to learn a model to address the reward-aware RL problem.

Moreover, some claims are not accurate. It is mentioned that “These algorithms learn a uniformly accurate model through a reward-free exploration, upon which decouple the learning from the exploration”, but Modi et al., 2021 is a model-free algorithm and does not try to learn a model. 

Modi et al., 2021 first proposes to solve min-max-min optimization instead of min-max-min-max optimization as one operator has a closed-form solution. The min-max-min optimization is furthered solved in a more computationally efficient way by considering squared loss minimization and saddle-point problem.

For the theoretical part, the assumptions are not written clearly. For example, I believe equation (5) is a crucial assumption, but it is not discussed explicitly in Section 4.1. 

The regret bound is about the Bayesian regret, and such guarantee is much weaker than the frequentist regret/worst case regret. The related discussion about the Bayesian regret and the definition of Bayesian regret E_{Pf} are missing.

I feel the title "a free lunch from the noise" oversells the paper. Indeed, it is a restricted assumption and the theoretical guarantee is obtained under such strong assumption.

# Technical analysis and algorithmic framework #
My second comment is about technical and algorithmic novelty. The algorithm is the standard model-based TS algorithm. Intuitively, given the model class, TS algorithm will identify the true model given a large amount of data. In addition, the authors make a strong assumption on the transition dynamics (eq 5) and the analysis is directly adapted from prior work (Russo & Van Roy (2013; 2014); Osband & Van Roy (2014)). I feel the technical contribution is rather limited.

# Experiments #
I think the most significant contribution of this paper is the experimental results. However, I'm not confident in evaluating the empirical results, and I feel there are a bunch of related model-based algorithms that achieve good empirical performance. 

In the experimental part, it’s unclear how the algorithm is implemented. How do you choose the function class F and the prior distribution p(f)?
summary_of_the_review: I believe the clarity of the writing can be improved. It might not be a good idea to emphasize the algorithm is conducting representation learning and using the model-based learning might be more suitable.

The theoretical contribution is rather limited, and most significant contribution seems to be on the empirical side (I have to say I'm not familiar with the empirical work). The authors make a strong assumption on the true model. The algorithm and the analysis seems to be directly adapted from prior work, e.g., Russo & Van Roy (2013; 2014); Osband & Van Roy (2014). 

It seems that there is a gap between the theoretical part and the experiment and it’s unclear how the experiment is conducted.
review_title: null

Meta-review: The AC summarizes the major strengths and weaknesses of the paper pointed out by the reviewers (with possible omissions, and additions by the AC)

Strengths:
1. The paper makes an important observation that the linear MDP assumptions can be met when the true dynamics has additive noise 
2. Inspired by the theory, the paper proposes a new algorithm that empirical outperforms SAC. The success of the algorithm is very interesting (and surprising to some degree.) 

Weaknesses
3. Most of the reviewers and the AC thinks the representation learning perspective is questionable. If one strongly believes that the $\phi, \mu$ in the linear MDP assumption should be interpreted as representations, then yes, this paper is about representation learning in RL and the representation learning is a free lunch. However, suppose one ignores the linear MDP perspective for the moment, and only looks at the modeling assumption $s' = f^*(s,a) +\epsilon$, then $f^*$ can only be interpreted as a "dynamics model" and has nothing to do with the term "representation" that is commonly used in practice. (representation means the penultimate layer of the neural nets typically in emprical RL.)  Moreover, in the theory part of the paper, the dynamics model is learned via a (standard) model-based approach---fitting $f(s,a)$ to $s'$---which also suggests that $f$ should be interpreted as a dynamics model instead of a representation. How to reconcile these two perspectives? The AC's own opinion is that this suggests we shouldn't blindly call the $\phi$ in the linear MDP formulation a representation in all scenarios. But regardless of AC's own opinion, I suspect that the paper needs to very explicitly discuss and clarify these discrepancies (instead of somewhat sweeping it under the rug and claiming the paper is about representation learning without a stronger justification.) 

4. The sample efficiency depends on the Eluder dimension, which is only known to be polynomial for linear models. Recent works have shown that the Eluder dimension for even simple nonlinear models can be exponential. The analysis seems to be also quite related to previous analysis that uses the Eluder dimension. I think this fact limits the theoretical contribution of the paper. 

5. There could be a better exposition of the empirical implementation in the paper. It appears that the implemented algorithm still has some major differences from the theoretical algorithms. 

6. It's unclear if the paper should only compare with model-free algorithms. At least the theoretical algorithm fits $f(s,a)$ to $s'$ explicitly (in the definition of confidence region). Therefore, it does not seem to be quite fair to compare with model-free algorithms. 

Given these considerations, and given that the majority of the reviewers express some concerns about various subsets of these concerns (3-6), the AC would recommend the authors revise the paper and resubmit to another top ML venue. The AC thinks that the paper contains really interesting and novel observations, but the interpretation of the observation might require more thoughts and clarification.
Decision: Reject