Spectral Decomposition Representation for Reinforcement Learning
Authors: Tongzheng Ren
Tianjun Zhang
Lisa Lee
Joseph E. Gonzalez
Dale Schuurmans
Bo Dai
Venue: ICLR 2023 poster (2023)
Keywords: Spectral Representation
Markov Decision Processes
Reinforcement Learning

Abstract: Representation learning often plays a critical role in avoiding the curse of dimensionality in reinforcement learning. A representative class of algorithms exploits spectral decomposition of the stochastic transition dynamics to construct representations that enjoy strong theoretical properties in idealized settings. However, current spectral methods suffer from limited applicability because they are constructed for
state-only aggregation and are derived from a policy-dependent transition kernel, without considering the issue of exploration. To address these issues, we propose an alternative spectral method, Spectral Decomposition Representation (SPEDER), that extracts a state-action abstraction from the dynamics without inducing spurious dependence on the data collection policy, while also balancing the exploration-versus-exploitation trade-off during learning. A theoretical analysis establishes the sample efficiency of the proposed algorithm in both the online and offline settings. In addition, an experimental investigation demonstrates superior performance over current state-of-the-art algorithms across several RL benchmarks.

Published as a conference paper at ICLR 2023
SPECTRAL DECOMPOSITION REPRESENTATION FOR REINFORCEMENT LEARNING
Tongzheng R Tianjun Zhang!.3 Lisa Lee'
Joseph Gonzalez
Dale Schuurmans Bo Dail.
'Google Research, Brain Team UT Austin UC Berkeley Uniieersity of Alberta
GGeoriia Tech
tongzhenggutexxs.eduu tianjunz@berkellyy edu, bodai@google..om
ABSTRACT
Representation learning often plays critical role in avoiding the curse of dimen- sionality in reinforcement learning. A representative class of algorithms exploits spectral decomposition of the stochastic transition dynamics to construct representa- tions that enjoy strong theoretical properties idealized settings. However, current spectral methods suffer from limited applicability because they are constructed for state-only aggregation and are derived from a policy-dependen transition kernel, without considering the issue of exploration. To address these issues, we propose an alternative spectral method, Spectral Decomposition Representation (SPEDER), that extracts state-action abstraction from the dynamics without inducing spurious dependence on the data collection policy, while also balancing the exploration- versus-exploitation trade-off during learning. A theoretical analysis establishes the sample efficiency of the proposed algorithm in both the online and offline settings. In addition, an experimental investigation demonstrates superior performance over current state-of oitte--f-th-artt the-art algorithms across several RL benchmarks.
INTRODUCTION
Reinforcement learning (RL) seeks to learn an optimal sequential decision making strategy by interacting with unknown environment, usually modeled by a Markov decision process (MDP). For MDPs with finite states and actions, RL can be performed in a sample efficint and computationally efficient way; however, for large or infinite state spaces both the sample and computational complexity increase dramatically. Representation learning is therefore a major tool to combat the implicit curse of dimensionality in such spaces, contributing to several empirical successes in deep RL., where policies and value functions are represented deep neural networks and trained end-to-end (Mnih et al, 2015; Levine al., 2016; Silver et al., 2017; Bellemare al., 2020). However, an inappropriate representation can introduce approximation error that grows exponentially in the horizon (Du et al., 2019b), or induce redundant solutions to the Bellman constraints with large generalization eиror (Xiao et 202, Consequently, ensuring the quality of representation learning has become an increasingly important consideration in deep RI..
In prior work, many methods have been proposed to ensure alternative properties of learned representation, such as reconstruction (Watter et al., 2015), bi-simulation (Gelada et al., 2019; Zhang al., 2020), and contrastive learning (Zhang et al., 2022a; Qiu et al., 2022; Nachum Yang, 2021). Among these methods, a family of representation learning algorithms has focused on constructing features by exploiting the spectral decomposition of different transition operators, including successor features (Dayan, 1993; Machado et al., 2018), proto-value functions (Mahadevan & Maggioni, 2007; Wu et al., 2018), spectral state aggregation (Duan al., 2019; Zhang & Wang, 2019). and Krylov bases (Petrik, 2007; Parr et al., 2008). Although these algorithms initially appear distinct, they all essentially factorize variant of the transition kernel. The most attractive property of such representations is that the value function can be linearly represented in the learned features, thereby reducing the complexity of subsequent planning. Moreover, spectral representations are compatible with deep neural networks (Barreto al., 2017), which makes them easily applicable to optimal policy learning (Kulkarni et al., 2016b) in deep RL.
"Equal Contribution.

---

Published as a conference paper at ICLR 2023
However, despite their elegance and desirable properties, current spectral representation algorithms ex- hibit several drawbacks. One drawback is that current methods generate state-only features, which are heavily influenced by the behavior policy and can fail to generalize well to alternative polices. More- over, most existing spectral representation learning algorithms omit the intimate coupling between representation learning and exploration, and instead learn the representation from pre-collected static dataset. This is problematic as effective exploration depends on having a good representation, while learning the representation requires comprehensively-coveeed experiences-fallinee to properly manage this interaction can lead to fundamentally sample-inefficien data collection (Xiao et al., 2022). These limitations lead to suboptimal features and limited empirical performance.
In this paper, we address these important but largely ignored issues, and provide novel spectral representation learning method that generates volicy-independent features that provably manage the delicate balance between exploration and exploitation. In summary:
We provide spectral decomposition view of several current representation learning methods, and identify the cause of spurious dependencies in state-only spectral features (Section 2.2).
We develop novel model-free objective, Spectral Decomposition Representation (SPEDER), that factorizes the while revealing the connection between model-free and model-based representation learning (Section 3).
transition kernel to eliminate policy-induced -induced dependencies.
We provide algorithms that implement the principles of optimism and pessimism in the face of uncertainty using the SPEDER features for online and offline RL (Section 3.1), and equip behavior cloning with SPEDER for imitation learning (Section 3.2).
We analyze the sample complexity of SPEDER in both the online and offline settings, to justify the achieved balance between exploration versus exploitation (Section 4).
We demonstrate that SPEDER outperforms state-of-the tfrtt model-based and model-free RL algorithms on several benchmarks (Section 6).
2
PRELIMINARIES
In this section, we briefly introduce Markov Decision Processes (MDPs) with low-rank structure, and reveal the spectral decomposition view of several representation learning algorithms, which motivates our new spectral representation learning algorithm.
2.1 LOW-RANK MARKOV DECISION PROCESSES
Markov Decision Processes (MDPs) are a standard sequential decision-making model for RL, and can be described as a tuple M = (S, A, r, P. p,
7),)), 7), where S is the state space, A is the action space,
r S x A + [0, 1] is the reward function, P S x A + A(S) is the transition operator with (SS) as the family of distributions over S. p E ASS) the initial distribution and y E (0, 1) the discount factor. The goal of RL is to find policy π S + ((A) that maximizes the cumulative discounted reward V7,,- := Esoxpi - 7'r(s, a:) sso] by interacting with the MDP. The value function is defined as (s) Ex Dioorrii a.) so s]. and the action-value function is (s, a) = Ex, E 0 (r( a:) = 8, a0 = =a]. These definitions imply the following recursive
relationships:
(s) E.r (s,)), (s, r(s,a) + 7Ep [F)
We additionally define the state visitation distribution induced by policy π as dz((s) (1 >) 12r= 1'1( = s)]o where 1(.) is the indicator function.
When (S] and [A] are finite, there exist sample-effciient algorithms that find the optimal policy by maintaining an estimate of P or Q7,-- (Azar et al., 2017; Jin et al., 2018). However, such methods cannot be scaled up when |S] and [A] are extremely large or infinite. In such cases, function approximation is needed to exploit the structure of the MDP while avoiding explicit dependence on [S] and [A]. The low rank MDP is one of the most prominent structures that allows for simple yet effective function approximation in MDPs, which is based on the following spectral structural assumption P and r:
Assumption (Low Rank MDP, (Jin et al., 2020; Agarwal et al., 2020)). An MDP M is a low rank MDP if there exists a low rank spectral decomposition of the transition kernel P(s (s, a), such that
P(s'(s, = (0(s, u(s))) r(s,a) ()(s,a);0.)
(1)
2

---

Published as a conference paper at ICLR 2023
with two spectral maps é S S x A - R and μs p - R and vector 0, R.. The & and μ also
satisfy the following normalization conditions:
V(s,a), [Ø a)l2 < 1. |10,11a & Vd.
R. l < & IIss H(s') (g(d))ss)) < Vd. (2)
The low rank MDP allows for linear representation of Qp,,, for any arbilrary policy n, since
(s, = r(s,)) ( a)ds'' = (o(s, a). 0, + (
(3)
Hence, we can provably perform compuutaiionlll--fffccenn planning and sample-efficient exploration in a low-rank MDP given ø(s, a), as shown in (Jin et al., 2020). However, ((s, a) is generally unknown to the reinforcement learning algorithm, and must be learned via representation learning to leverage the structure of low rank MDPs
2.2 SPECTRAL FRAMEWORK FOR REPRESENTATION LEARNING
Representation learning based on spectral decomposition of the transition dynamics was investigated as early as Dayan (1993), although the explicit study began with Mahadevan & Maggioni (2007), which constructed features via eigenfunctions from Laplacians of the transitions. This inspired a series of subsequent work on spectral decomposition representations. including the Krylov basis (Petrik, 2007; Parr et al., 2008), continuous Laplacian Wu et al. (2018), and spectral state aggregation (Duan et al., 2019; Zhang & Wang. 2019). We summarize these algorithms in Table to reveal their commonality from unified perspective, which motivates the development of new algorithm. A similar summary has also been provided in (Ghosh & Bellemare, 2020).
These existing spectral representation methods construct features based on the spectral space of the state transition probability pM (s'ls)
Table 1: A unified spectral decomposition view of existing related representations. Here, r de- notes the reward function, A denotes some di- agonal reweighting operator, and p* (5'1ss)
f P(ss'ss, a) (a)ssd) induced by some policy æ.
Such transition operator introduces inter-state de- pendency from the specific æ, and thus injects an inductive bias into the state-only spectral represen- tation, resulting in features that might not be gener- alizable to other policies. To make the state-feature generalizable, some work has resorted incorporat- ing a linear action model (e.g. Yao & Szepesvári, 2012; Gehring al., 2018) where action information is stored in the linear weights. However, this work requires known state-features, and it is not clear how to combine the linear action model with the spectral feature framework. Moreover, these existing spectral representation methods completely ignore the problem of exploration, which affects the composition of the dataset for representation learning and is conversely affected by the learned representation during the data collection procedure. These drawbacks have limited the performance of spectral representations in practice.
J P(s (s a) (T s da.
Representation
Decomposed Dynamics
Successor Feature
svd (I --pp)-)) eig (AP + (Pr) A) ((Pr) ro avd
Proto-Value Function
Krylov Basis
Spectral State-Aggregution
SPECTRAL DECOMPOSITION REPRESENTATION LEARNING
To address these issues, we provide a novel spectral representation learning method, which we call SPEctral DEcomposition Representation (SPEDER). SPEDER is compatible with stochastic gradient updates, and is therefore naturally applicable to general practical settings. We will show that SPEDER can be easily combined with the principle optimism in the face of uncertainty to obtain sample efficient online exploration, and can also be leveraged to perform latent behavioral cloning.
As discussed in Section 2, the fundamental cause of the spurious dependence state-only spectral features arises from the state transition operator px (s')s), which introduces inter-state dependence induced by a specific behavior policy л. To resolve this issue, we extract the spectral feature from P(s'|s, a) alone, which is invariant to the policy, thereby resulting in more stable spectral representation.
Assume we are given set of observations {(s;, ags $f) sampled from po(s,a) x P(s'ls, a). and want to learn spectral features Φ(8 a) E Rd and uus') E Rd, which are produced by function approximators like deep neural nets, such that:
P(8l)s,)) a) a)s,a) inss).
3

---

Published as a conference paper at ICLR 2023
Such representation allows for simple linear parameterization of Q for any policy n, making the planning step efficient, as discussed section 2.1. Based on (4), one can exploit density estimation techniques, e.g., maximum likelihood estimation (MLE), to estimate ø and μ.C
1 T0. = arg max - NEW ==1
log d(s; a;) ((ss)) - log ((s
(5)
where (x) = (8, a) p(s')ds' In fact, (Agarwal et al., 2020; Uehara et al., 2022) provide rigorous theoretical guarantees when a computation oracle for solving (5) is provided. However, such a computation for MLE is highly nontrivial. Mcanwhile, the MLE (5) is invariant to the scale of Φ and μú that is, if (ø, μ1) is a solution of (5), then (c16, ) is also a solution of (5) for any C1 0. Hence, generally do not have ((s, a)
for any as, and
only use to linearly represent the
T
P()1(8,a)
((s.a) ((s,a)
((6'). Therefore, we need to use (0 a) == ((s.a) ((s,a)
Q-function, which incurs an extra estimation requirement for (s,, a).
Recall that the pair ((s, a) and pas') actually form the subspace of transition operator P(s'|s, a). so instead of MLE for the factorization of P(s'|s [s, a), we can directly apply singular value decomposi- tion (SVD) to the transition operator to bypass the computation difficulties in MLE. Specifically, the SVD of transition operator can be formulated as
max E(do Il
P [P(s'ls, a))((,
(6)
max 2Trace Epp If ((s))((ssss
1/d u(s') m(d')ds max p x [Ø(s,)) T (s') EEp (p(s')u' (s') (() /d.
max
Eldo Iladd
P
(7)
E(do Ila/d,
where |1-1l2 denotes the L2(1) norm where μ denotes the Lebesgue measure for continuous case and counting measure for discrete case, the second equality comes from the Fenchel duality of I1-112 with up-scaling of by vd, and the third equality comes from reparameterization ju(x)) = p()'((()))))))))))) ((' (s") with some parametrized probability measure p(s') supported on the state space S.
As (7) can be approximated with the samples, it can be solved via stochastic gradient updates, where the constraint is handled via the penalty method as in (Wu et al., 2018). This algorithm starkly contrasts with existing deeeeddde methods for spectral features via explicit eigendecomposition of state transition matrices (Mahadevan & Maggioni, 2007; Machado et al., 2017; 2018).
Remark (equivalent model-based view of (7)): We emphasize that the SVD variational formu- lation in (6) is model-free, according the categorization in Modi et al. (2021), without explicit modeling of μ. Here, is only introduced only for tractability. This reveals an interesting model-based perspective on representation learning.
We draw inspiration from spectral conditional density estimation (Grünewälder et al., 2012):
min (e,))o |[-|s a) - á(s u(-))l²
P(s'|s, a), thus it can be used as This objective (8) has a unique global minimum, a) an alternative representation learning objective.
However, the objective (8) is still intractable when we only have access samples from P. To resolve the issue, we note that
L(o p.) (( || ( u(
=C 2 (d(s,a) a) m(s')] Beeaa Us (((())))T(<()) do/ (9)
where C = Esp [ (P(s')s, a))² is problem--deendden constant. For the third term, we turn to an approximation method by reparameterization p(s') = (('))
Exe Us (0(s.0) m(s'))² (((s)) ds' Trace (B [ a)d(,, a) ED (o()))n((())(()))))
4

---

Published as a conference paper at ICLR 2023
Algorithm Online Exploration with SPEDER
1: Input: Regularizer Ano parameter On. Model class F= ((o, μ)) o + v. Iteration N
2: Initialize To 8) to be uniform; set Do 6, Di = 0
1,.... N do 4: Collect the transition (8,a,8', "',,','',, where 8 ~ dp a ~ U(A), 8 ~ P*(1)s,a),a' ~
3: for episode
U(AA). 3 P* (-ls', .'). where (A) denotes the uniform distribution on A.
5:
D, = Dn- U {s, a, 5' D = - U a' 55.
6:
Learn representation ((s, a) with Dn U.D via equation 10.
7:
Update the empirical covariance matrix
Σn = EM.ED, (s) + Ar
Set the exploration bonus B (s, an V (s) En ( 9: Update policy Tn arg max V Pr,,+
8:
end for
11:
Return AN
Under the constraint that Ex,a (os, a] = Ia/d, we have
Trace (E(s,a)>oo [ō(s, ())(s, T] Ep (s"'")" = [p()') (')))' (1)))))
Hence, Equation can be written equivalently
min - -(s.nn""))) [Ø(s.0) (e00)"((ss')) ('(s')((s)) + (Emor) (p(s)) (1(s)) /(2d) 0,10
s.t. (s,a))p [0(s, ()s,a))(s, a) [] Ia/d, (10)
which exact as the dual form of the SVD in (7). Such an equivalence reveals an interesting connection between model-free and model-based representation learning, obtained through duality, which indicates that the spectral representation learned via SVD is implicitly minimizing the model error in L2 norm. This connection paves the way for theoretical analysis.
3.1 ONLINE EXPLORATION AND OFFLINE POLICY OPTIMIZATION WITH SPEDER
Unlike existing spectral representation learning algorithms, where the features are learned based on a pre-collected static dataset,
SPEDER to perform sample efficient online exploration. In Algorithm 1, we show how to use the representation obtained from the solution to (10) to perform sample efficient online exploration under the principle of optimism in the face of uncertainty. Central to the algorithm is the newly proposed representation learning procedure (Line 6 in Algorithm 1), which learns the representation Φ(s, a) and the model P(s'|s, a) 0(s, a) T (s()) with adaptively collected exploratory data. After recovering the representation, we use the standard elliptical poten- tial (Jin et al., 2020; Uehara et al., 2022) as the bonus (Line 8 in Algorithm 1) to enforce exploration. We then plan using the learned model P., with the reward bonus b, to obtain new policy that is used to collect additional exploratory data. These procedures iterate, comprising A Algorithm 1.
SPEDER can also be combined with the pessimism principle to perform sample efficient offline policy optimization. Unlike the online setting where we enforce exploration by adding a bonus to the reward, we now subtract the elliptical potential from the reward avoid risky behavior. For completeness, we include the algorithm for offline policy optimization in Appendix C.
On the requirements of P.,. As we need to plan with the learned model Pn.. we generally require Pn, to be a valid transition kernel, but the representation learning objective (10) does not explicitly enforce this. Therefore in our implementations, we use the data from the replay buffer collected during the past executions to perform planning. We can also enforce that P., is a valid probability by adding the following additional regularization term Ma & Collins (2018):
E (e.,)) [log Is 0(s, a) p
(11)
which can he approximated with samples from p(s'). Obviously, the regularization is non-negative and achieves zero when fs o(s,o) a) ( (ss'dds'
5

---

Published as a conference paper at ICLR 2023
Practical Implementation We parameterize Φ(s, a) and (s(s') separate MLP networks, and train them by optimizing objective (10). Instead of using a linear Q on top of o(s, a), as suggested by the low-rank MDP, parameterize the critic network representation (88, a) to support the nonlinear exploration bonus and entropy regularization, Unlike other representation learning methods in RL, do not backpropagate the gradient from TD-learning to the representation network (s,, a). To train the policy, we use the Soft Actor-Critic (SAC) algorithm (Haarnoja al., 2018), and alternate between policy optimization and critic training.
two-layer MLP on top of the learned
3.2 SPECTRAL REPRESENTATION FOR LATENT BEUIVIORAL CLONING
We additionally expand the use of the learned spectral representation ( a) as skills for downstream imitation learning, which seeks to mimic given set of expert demonstrations. Specifically, recall the correspondence between the max-entropy policy and Q-function, i.e.
(a(a = exp(Q(s, a))
arg max Ex [Q(s, a)] + H (T) =(()))A(A)
(12)
DEEA exp(((s,a)
where (T) : Ene log Therefore, given a set of linear basis functions for Q, { the we can construct the policy basis, or skill sets, based on ø according to (12), which induces the policy family (als) x exp(w" T 0(s, a)). We emphasize that the policy construction to use latent variable composition to approximate policy construction, ie., (a]as) = J Ta ma((a {a)8, , 2 2) 2 (218)d2, with x = Φ(8, a) to insert the learned representation. The policy decoder aa S x Z (AA) and the policy encoder æz S A(Z)
from the skills is longer linear. This inspires
can be composed to form the final policy.
We assume access to a fixed set of expert transitions D = {(s,, at, $(+1) : St dp ~ I (s:), S141 ~ P(s' st, a.}}. In practice, while expert demonstrations can be expensive to acquire, non-expert data of interactions in the same environment can be more accessible collect at scale, and provide additional information about the transition dynamics of the environment. We denote the offline transitions D {(s, s')} from the same MDP, which is collected by non-expert policy with suboptimal performance (e.g.. an exploratory policy). We follow latent behavioral cloning (Yang al., 2021; Yang & Nachum, 2021) where learning is separated into a pre-training phase, where a representation & S x A + Z and a policy decoder Tx S x Z - ((A) are learned on the basis of the suboptimal dataset D and downstream imitation phase that learns latent policy T2 + A(Z) using the expert dataset D With SPEDER, perform latent behavior cloning
as follows:
1. Pretraining Phase:
We pre-train o(s, a) and pus') Deff by minimizing the objective (10). Additionally, we train a policy decoder Ta (a s, ((s, a)) that maps latent action representations to actions in the original action space, by minimizing the action decoding error:
E Eg |- log (a s, 0. a))]
2. Downstream Imitation Phase: We train latent policy πW S A(Z) by minimizing the latent behavioral cloning error:
E (r.a)aap"" [- log #2 (0(, a) $)]
At inference time, given the current state s E S, we sample latent action representation = ~ =2())) then decode the action Ta(aa 2)
4 THEORETICAL ANALYSIS
In this section, we establish generalization properties of the proposed representation learning algo- rithm, and provide sample complexity and error bounds when the proposed representation learning algorithm is applied to online exploration and offline policy optimization.
4.1 NON-ASYMPTOTIC GENERALIZATION BOUND
We first state a performance guarantee on the representation learned with the proposed objective.
Theorem 1. Assume the size of candidate model class |F| < Co, P F, and for any P E F. (()'(s,)) & C for all (8,a, s'). Given the dataset D {(sis di, 8 where (8i, Po-

---

Published as a conference paper at ICLR 2023
& P(-|s;; 0i), the estimator P obtained by empirical surrogate of (9) satisfies the following inequality with probability at least 1
p (P - P(-Is, a)ll C' log FF/8
(13)
where C' is a constant that only depends on C, which we will omit in the following analysis.
Note that the data assumption can be relaxed an assumption that the data generating process is martingale process. This is essential for proving the sample complexity of online exploration, as the data are collected in an adaptive manner. The proof' are deferred to Appendix D.
4.2 SAMPLE COMPLEXITIES OF ONLINE EXPLORATION AND OFFLINE POLICY OPTIMIZATION
Next, we establish sample complexities for the online exploration and offline policy optimization problems. We still assume P E F. As the generalization bound equation 13 only guarantees the expected L2 distance, need to make the following additional assumptions the representation and reward:
Assumption (Representation Normalization), Vó E we have Is (Sa (l a)lla da) 2 ds d.
Assumption 3 (Reward Normalization). Is r(s, da)² ds & d, where is the reward function.
A simple example that satisfies both Assumption 2 and 3 is tabular MDP with features o(s, a) forming the canonical basis in R|S||AA| In this case, we have |S|| hence Assumption 2 naturally holds. Furthermore, since r(s, a) e [0, 1], it is also straightforward to verify that Assumption 3 holds for tabular MDP. Such an assumption can also be satisfied for continuous state space where the volume of the state space satisfies μ(S) < d. valid transition kernel. With Assumptions and 3 in hand, we are now ready to provide the sample complexities of online exploration and offline policy optimization. The proof's are deferred to Appendix D.2 and D.3.
T Since we need plan on P. we also assume P
Theorem (PAC Guarantee for Online Exploration). Assume |A| co. After interacting with the environment for N θ (1-7)52) episodes, where O omits log-factors, obtain a policy
- <
with high probabilit, where x" is the optimal policy. Furthermore, note that, we can obtain a sample from the state visitation distribution d7, via terminating with probability 1 y each step. Hence, for each episode, we can terminate within @(1/(1- steps with high probability
Theorem 3 (PAC Guarantee for Offline Policy Optimization). Let w min,,0 su(als) where To is the behavior policy. With probability 1 for all baseline policies æ including history-dependent non-Markovian policies, we have that
w²d log([=1/8)
VØ,
(1-7)6
where C is the relative conditional number under o² which measures the quality of the offline data:
x. E(,.a) (0 a) a) (s.a)
C = sup SER E E. (s a)
RELATED WORK
Aside from the family of spectral decomposition representation methods reviewed in Section 2, there have been many attempts to provide algorithmic representation learning algorithms for RL. in different skills,
problem settings. Learning action representations, or abstractions, such as temporally-extendl has been a long-standing focus of hierarchical RL (Dietterich et al., 1998; Sutton et al., 1999; Kulkarni tasks. Recently, many algorithms
et al., 2016a; Nachum et al., 2018) for solving temporally-extende have been proposed for online unsupervised skill discovery, which can reduce the cost of exploration and sample complexity of online RL algorithms. A class of methods extract caaporally-extnnder skills by maximizing mutual information objective (Eysenbach et al., 2018; Sharma et al., 2019; Lynch al., 2020) or minimizing divergences (Lee al., 2019). Unsupervised skill discovery has
7

---

Published as a conference paper at ICLR 2023
been also studied in offline settings, where the goal is to pre-train useful skill representations from offline trajectories, in order to accelerate learning on downstream RL tasks (Yang & Nachum, 2021). Such methods include OPAL (Ajay et al., 2020), SPiRL (Pertsch et al., 2020), and SkiLD (Pertsch et al., 2021), which exploit a latent variable model with an autoencoder for skills acquisition; and PARROT (Singh al., 2020), which learns behavior prior with flow-based models. Another offiin representation learning algorithm, TRAIL (Yang et al., 2021), uses a contrastive implementation of the MIE for an energy-based model to learn state-action features. These algorithms achieve empirical improvements in different problem settings, such as imitation learning, policy transfer, etc. However, as far as we know, the coupling between exploration and representation learning has not been well handled, and there is no rigorous characterization yet for these algorithms.
Another line of research focuses on theoretically guaranteed representation learning in RI., either by limiting the flexibility of the models or by ignoring the practical issue of computational cost. For example, (Du et al., 2019a; Misra et al., 2020) considered representation learning in block MDPs, where the representation can be learned via regression. However, the corresponding representation ability is exponentially weaker than low-rank MDPs (Agarwal et al., 2020). Ren et al. (2021) I) exploited representation from arbitrary dynamics models, but restricted the noise model to be Gaussian. On the other hand, (Agarwal et al., 2020; Modi et al., 2021; Uchara et al., 2022; Zhang et al., 2022b; Chen et al., 2022) provably extracted spectral features in low-rank MDPs with exploration, but these methods rely on a strong computation oracle, which is difficult to implement in practice.
In contrast, SPEDER enjoys both theoretical and empirical advantages. We provide tractable surrogate with an efficient algorithm for spectral feature learning with exploration in low-rank MDPs. We have established its sample complexity and next demonstrate its superior empirical performance.
6 EXPERIMENTS
We evaluate SPEDER on the rewse-reward MuJoCo tasks (Brockman et al., 2016) and sparse-reward DeepMind Control Suite tasks (Tassa et al., 2018). In MuJoCo tasks, we compare with model-based (e.g., PETS (Chua et al., 2018), 8), ME-TRPO (Kurutach et al., 2018)) and model-free baselines (e-g., SAC (Haarnoja al., 2018), PPO (Schulman et al., 2017)), showing strong performance compared to SoTA RL algorithms. In particular, we find that in the sparse reward DeepMind Control tasks, the optimistic SPEDER significantly outperforms the SoTA model-free RL algorithms. We also evaluate the method on offline behavioral cloning tasks in the AntMaze environment using the D4RL benchmark (Fu et al., 2020), and show comparable results to state-of ffate-of-thh-assd the--art representation learning methods. Additional details about the experiment setup are described in Appendix F.
6.1 ONLINE PERFORMANCE WITH THE SPECTRAL REPRESENTATION
We evaluate the proposed algorithm on the dense-reward MuJoCo benchmark from MBBL (Wang et al., 2019). We compare SPEDER with several model-based RL baselines (PETS (Chua et al., 2018), ME-TRPO (Kurutach et al., 2018)) and SoTA model-free RL baselines (SAC (Haarnoja et al., 2018), PPO (Schulman et al., 2017)). As a standard evaluation protocol in MBBL, we ran all the algorithms for 200K environment steps. The results averaged across four random seeds with window size 20K.
In Table 2, we show that SPEDER achieves SoTA results among all model-based RI. algorithms and significantly improves the prior baselines. We also compare the algorithm with the SoTA model-free RL method SAC. The proposed method achieves comparable or better performance in most of the tasks. Lastly, compared to two representation learning baselines (Deep SF (Kulkarni al., 2016b) and SPEDE (Ren et al., 2021)), SPEDER also shows superior performance, which demonstrates the proposed SPEDER is able to overcome the aforementioned drawback of vanilla spectral representations.
6.2 EXPLORATION IN SPARSE-REWARD DEEPMIND CONTROL SUITE
To evaluate the exploration performance of SPEDER, we additionally run experiments on the DeepMind Control Suite. We compare the proposed method with SAC, (including 2-layer, 3-layer and 5-layer MLP for critic network), PPO, Dreamer-v2 (Hafner et al., 2020), Deep SF (Kulkamn et al., 2016b) and Proto-RL (Yarats et al., 2021). Since the original Dreamer and Proto-RI RL are designed for image-based control tasks, we adapt them to run the state- based tasks and details can be found at Appendix. F. We run all the algorithms for 200K environment steps across four random seeds
8

---

Published as a conference paper at ICLR 2023
Table 2: Performance various MuJoCo control tasks. All the results averaged across 4 random seeds and window size of 20K. Results marked with is adopted from MBBL (Wang et al., 2019). SPEDER achieves strong performance compared with baselines.
HallCheetah
Reacher
Humamoid ET
Pemdulum
I-Pendulum
ME-TRPO" PETS RS"
2283.7=900.4
-13.4:::22
72.9:8.9
177.3:1:9
-126.24:6.6
966.9: 966.9:1471.6
400.1:16.9
109.6.1:02.6
167.9:135.8
-12.1:125.1
Model Based RL
8799
-12.3:55.2
110.8:4:0.11
167.41:53.0
.20.5-128.9
Best MBBL
3639.0=11355
4.1+20.1
1377.0= 150.4
177.::119
0.0:::.00
PPO
17.2:184.4
-17.2.1099
391.4
163.4.8.00
4008:112..
Model-Free RL
TRPO"
-12.0485.5
-10.1:00.6
289.8::5.2
166.747.33
-27 17..0=
SAC" (3-layer)
4000.7:1:02.1
6.41...5
1794.41458.1
168.2.9.55
-022.0.11
DeepSI
4180
-16.8:3366
168.64::.1
168.6:5:.1
-0.2::033
Representation RI
SPEDE
4210.3.1.2.6
7.211.1
886.9115,22
169.5.1..66
0.0.1...
SPEDER
5407.9-813.0
-5.0020.33
1774.755:1199
167.4334
0.0:10.0
Hopper-FT
S.Humanoid-FT
CamPrle
Walker-FT
ME- ME-TRPO
42.61:2111
5000
5344.91534.3
160.1 16..1.169.11
16099.3:16677.5
PETS-RS"
130.0:1:48 148.1
205.8:1.36.5
182.2
195.0:1-28.0
312.5:1-993.4
Model-Based
PETS-CEM"
81.6=145.8
129.3
355, 1517.11
195 3.00
260.2::536.
MBBL
375.4:::09.1
1272.5+:500.9
1084.3=77.00
200.0::0.0
312.5:t-993.4
PPO
80.1
758.0=62.00
454.3-36.7
86.4778
106.1=17..2
Model-Free RL
TRPO
116.82:7.33
237.4::33,5
281.3+10.99
47,3
229.5::277.1
SAC' (3-layer)
2012.7=571..
1815.5:6655.1
834.6::313.1
19944:0
2216.44678.7
DeepST
:1..1:144.1
248.9.1.53.11
$13.81154.9
194.5.1..88
165.6.1.277
SPEDE
8:6.24-000.2
732.2-1263.9
954.44154.7
138.24439.55
201.6::204.0
Representation RL
SPEDER
1806.8:+1488..
5267.6=554.3
944,8+3354.3
20012::110
2411.5==115.6
Table 3: Performance on various DeepMind Suite Control tasks. All the results are averaged across four random seeds and window size of 20K. Comparing with SAC, our method achieves even better performance on sparse-reward tasks. Results presented in mean + standard deviation across different random seeds.
chectah_ron
chectah.ruv run sparse walker,run
walker_run sparce
humanoid run
hopper.hop
Model-Rased RI.
Dreamer
542.0 +: 27.7
499.9-17..3
337.7:667.2
95.41:4.77
1.0:0.22
46. 17.33
PPO
227.7:1.57.9
5.4.1
51.61::55
0.0.10.0
1.1.0,0
0.7.10..8
(2-layer)
222.244-1.00
32.44-27.8
181.0-1-3..4
53.5-169.3
1.340.1
Model-Free RL
SAC (3-layer)
595.2:t-9.0
419.5=73.3
700.9=36.6
311.5:+361.4
1.2+0..1
28.6 19.5
SAC (S-layer)
566.311123.5
364. 14:22.1
716.9:135.0
276.11:319.3
8.2:13388
31.11:1.8
DeepSI
295.3:1:3..5
0.0:10.0
27.9 2.2
0.1:10.1
0.3:10.1
Representation RI.
305.54437.99
0.0:10000
433.5-556.8
46.9::34.1
SPEDER
593.7=995.1
425.5 # 42.8
690,4:220.5
683,2::96.0
11.5=5.4
119.8+89.66
with a window size of 20K. From Table 3, we see that SPEDER achieves superior performance compared SAC using the 2-layer critic network. Compared to SAC and PPO with deeper critic networks, SPEDER has significant gain in tasks with sparse reward (e.g., wal werkeer--u---e run-ssaseee sparse and hopper-hop).
6.3 IMITATION LEARNING PERFORMANCE ON ANTMAZE NAVIGATION
We additionally experiment with using SPEDER features for downstream imitation learning. We consider the challenging AntMaze navigation domain (shown in Figure 3) from the D4RL (Fu et al., 2020), which consists of a 8-DoF quadraped robot whose task is to navigate towards a goal position in the maze environment. We compare SPEDER to several recent state-of-the-arr for pre-training representations from suboptimal offline data, including OPAL (Ajay et al., 2020), SPiRL (Pertsch et al., 2020), SkiLD (Pertsch et al., 202 1), and TRAIL (Yang et al., 2021). For OPAL, SPiRL, and SkiLD, we use horizons of t = 1 and f 10 for learning temporally we report the performance of the TRAIL energy-basee model (EBM) as well as the TRAIL Linear model with random Fourier features (Rahimi & Recht, 2007).
skills. For TRAIL,
Following the behavioral cloning setup in (Yang et al., 2021), we use a set of 10 expert trajectories of the agent navigating from one corner of the maze to the opposite corner as the expert dataset D= For the suboptimal dataset Dell" we use the "diverse" datasets from D4RL (Fu et al., 2020), which consist of 1M samples of the agent navigating from different initial locations to different goal positions. We report the average return AntMaze tasks, and observe that SPEDER achieves comparable performance as other state-of- the-the-rt representations on downstream imitation learning in Figure 4. The comparison and experiment details can be found in Appendix F.

---

Published as a conference paper at ICLR 2023
7 CONCLUSION
We have proposed a novel objective, Spectral Decomposition Representation (SPEDER), that factor- izes the state-action transition kernel to obtain policy- indeepenennt spectral features. We show how to use the representations obtained with SPEDER to perform sample efficient online and offline RL, as well imitation learning. We provide a thorough theoretical analysis of SPEDER and empirical comparisons on multiple RL benchmarks, demonstrating the effectiveness of SPEDER.
REFERENCES
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 13:20095-20109 2020.
Anurag Ajay, Aviral Kumar, Pulkit Agrawal, Sergey Levine, and Ofir Nachum. Opal: Offline primitive discovery for accelerating offline reinforcement learning. arXiv preprint arXiv:2010. 13610,,311,... 1, 2020.
Ankesh Anand, Evan Racah, Sherjil Ozair, Yoshua Bengio, Marc-Alexandre Côté, and R Devon Hjelm. Unsupervised state representation learning in atari. Advances in Neural Information Processing Systems, 32, 2019.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay, Advances in neural information processing systems, 30, 2017.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference Machine Learning, pp. 263-272. PMLR, 2017.
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado P van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. Advances in neural information processing systems, 30, 2017.
Marc G Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos C Machado, Sub- hodeep Moitra, Sameera S Ponda, and Ziyu Wang. Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588(7836):77-82, 2020.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv: 2016.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. On the statistical efficiency of reward-free exploration in non-linear rl. arXiv preprint arXiv:2206 2022.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in a handful of trials using probabilistic dynamics models. Advances in neural information processing systems, 31, 2018.
Peter Dayan. Improving generalization for temporal difference learning: The successor representation. Neural Computation, 5(4):613-624, 1993.
Thomas G Dietterich al. The maxq method for hierarchical reinforcement learning. In ICMI., volume 98, pp. 118-126. Citeseer, 1998.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pp. 1665-1674, PMLR, 2019a.
Simon S Du. Sham M Kakade, Ruosong Wang. and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2019b.
Yaqi Duan, Tracy Ke, and Mengdi Wang. State aggregation learning from markov transition data. Advances in Neural Information Processing Systems, 32, 2019.
10

---

Published as a conference paper at ICLR 2023
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint arXiv: 2018.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning, 2020.
Clement Gehring, Leslie Pack Kaelbling, and Tomas Lozano-Pene Perez. Adaptable replanning with compressed linear action models for learning from demonstrations. In Conference on Robot Learning, pp. 432-442. PMLR, 2018.
Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Marc G Bellemare. Deepmdp: Learning continuous latent space models for representation learning. In International Conference on Machine Learning, pp. 2170-2179. PMLR, 2019.
Dibya Ghosh and Mare G Bellemare. Representations for stable off- ooflcy reinforcement learning. In International Conference on Machine Learning, pp. 3556-3565. PMLR, 2020.
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal- conditioned policies. arXiv preprint arXiv:1811.07811 2018
Steffen Grünewälder, Guy Lever, Luca Baldassarre, Sam Patterson, Arthur Gretton, and Massimilano Pontil. Conditional mean embeddings as regressors. In Proceedings of the 29th International Cofer- ence on International Conference on Machine Learning, ICML' 12, pp. 1803-1810. Omnipress. 2012.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et Soft actor-critic algorithms and applications. arXiv preprint 1812:v881..050000 2018.
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. arXiv preprint 1922:0991220003, 2019.
Danijar Hafner, Timothy Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. arXiv preprint arXiv:2010.02/93,, 2020.
Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv: 1.05997, 2016.
Chi Jin, Zeyuan Allen-Zhi ZZu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Leslie Pack Kaelbling. Learning to achieve goals. In IJCAI, volume 2, pp. 1094-8. Citeseer, 1993.
Tejas D Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. Advances in neural information processing systems, 29, 2016a.
Tejas D Kulkarni, Ardavan Sacedi, Simanta Gautam, and Samuel J Gershman. Deep successor reinforcement learning. arXiv preprint 1o06vv1606.000 02396, 2016b.
Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. arXiv preprint arXiv: 10592, 2018
Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Rein- forcement learning with augmented data. Advances in Neural Information Processing Systems, 33: 19884-19895, 2020.
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint arXiv: /906. 05274, 2019.
11

---

Published as a conference paper at ICLR 2023
Lisa Lee, Ben Eysenbach, Russ R Salakhutdinov, Shixiang Shane Gu, and Chelsea Finn. Weakly- supervised reinforeement learning for controllable behavior. Advances in Neural Information Processing Systems, 33:2661-2673 2020.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334-137, 2016. 2016.
Corey Lynch, Mohi Khansari, Ted Xiao, Vikash Kumar, Jonathan Tompson, Sergey Levine, and Pierre Sermanet. Learning latent plans from play. In Conference on robot learning, pp. 1113-1132. PMLR, 2020.
Zhuang Ma and Michael Collins. Noise contrastive estimation and negative sampling for conditional models: Consistency and statistical efficiency. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 3698--377777 2018
Marlos C Machado, Mare G Bellemare, and Michael Bowling. laplacian framework for option discovery in reinforcement learning. In International Conference on Machine Learning, pp. 2295-2304. PMLR, 2017.
Marlos C. Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. In International Con- ference on Learning Representations, 2018. URL http::///peeeevvveeveeeeooooomes
Sridhar Mahadevan and Mauro Maggioni. Proto-value functions: A laplacian framework for learning representation and control in markov decision processes. Journal of Machine Learning Research, 8(10), 2007.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning. pp. 6961-6971. PMLR, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 518(7540):529-333 2015.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07083 2021.
Ofir Nachum and Mengjiao Yang. Provable representation learning for imitation with contrastive fourier features. Advances in Neural Information Processing Systems, 34:30100-30112, 2021.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in neural information processing systems, 31, 2018.
Ashvin V Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. Visual reinforcement learning with imagined goals. Advances in neural information processing systems, 31, 2018
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. Advances in neural information processing systems, 30, 2017.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv: 1807.0374, 2018
Ronald Parr, Lihong Li, Gavin Taylor, Christopher approximation, and feature selection for An analysis of linear models, linear reinforcement learning. In Proceedings of the 25th international conference Machine learning, pp. 752-759, 2008
and Michael L Littman.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International conference on machine learning, pp. 2778-2787. PMLR, 2017.
12

---

Published as a conference paper at ICLR 2023
Karl Pertsch, Youngwoon Lee, and Joseph Lim. Accelerating reinforcement learning with learned skill priors. arXiv preprint arXiv:2010.11944 2020.
Karl Pertsch, Youngwoon Lee, Yue Wu, and Joseph J Lim. Guided reinforcement learning with learned skills. arXiv preprint arXiv:2107.10253, 2021.
Marek Petrik. An analysis of laplacian methods for value function approximation in mdps. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, UCAI'07, pp. 2574-2579, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.
D Pomerleau. An autonomous land vehicle in neural network. Advances in Neural Information Processing Systems, 1998.
Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit: State-covering supervsee reinforcement learning. arXiv preprint arXiv:1903.03698, 2019.
Shuang Qiu, Lingxiao Wang, Chenjia Bai, Zhuoran Yang, and Zhaoran Wang. Contrastive ueb: Prov- ably efficient contrastive sele-supervised learning in online reinforcement learning. In International Conference on Machine Learning, pp. 18210. PMLR, 2022.
Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adrià Puigdomènech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, et al. Imagination-augmeen agents for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Prajit Ramachandran, Barret Zoph, and Quoe V Le. Searching for activation functions. arXiv preprint 11X.vv1710.05941, 2017.
Tongzheng Ren, Tianjun Zhang, Csaba Szepesvári, and Bo Dai. A free lunch from the noise: Provable and practical exploration for representation learning. arXiv preprint arXiv:2111.11885 2021.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators.
In International conference machine learning, pp. 1312-1320. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Pierre Sermanet, Corey Lynch, Yevgen Chebotar, Jasmine Hsu, Eric Jang, Stefan Schaal, Sergey Levine, and Google Brain. Time-contrastive networks: Self-supervised learning from video. In 2018 IEEE international conference on robotics and automation (ICRA), pp. 1134-1141. IEEE, 2018.
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-aware unsupervised discovery of skills. arXiv preprint 1xXxv:9977001577 2019.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-50 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144, 2018.
Avi Singh, Huihan Liu, Gaoyue Zhou, Albert Yu, Nicholas Rhinchart, and Sergey Levine. Parrot: Data-driven behavioral priors for reinforcement learning. arXiv preprint 1xiv:20111110224, 2020.
Aravind Srinivas, Michael Laskin, and Pieter Abbeel. Curl: Contrastive unsupervised representations for reinforcement learning. arXiv preprint 3411:32004001166, 2020.
13

---

Published as a conference paper at ICLR 2023
Adam Stooke, Kimin Lee, Pieter Abbeel, and Michael Laskin. Decoupling representation learning from reinforcement learning. In International Conference on Machine Learning pp. 9870-9877 PMLR. 2021.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2) (12(1-2):181-11 1999.
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, et al. Deepmind control suite. arXiv preprint arXiv: 00690, 2018.
Ahmed Touati and Yann Ollivier. Learning one representation optimize all rewards. Advances in Neural Information Processing Systems, 34:13-23, 2021.
Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. In International Conference on Learning Representations, 2022.
Tingwu Wang. Xuchan Bao, Ignasi Clavera, Jerrick Hoang, Yeming Wen, Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel, and Jimmy Ba. Benchmarking model- based reinforcement learning. arXiv preprint arXiv: 1000::907.00000 2019.
Manuel Watter, Jost Springenberg. Joschka Boedecker, and Martin Riedmiller. Embed to control: locally linear latent dynamics model for control from raw images. Advances in neural information processing systems, 28, 2015.
Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in rl: Learning representations with efficient approximations. In International Conference on Learning Representations, 2018.
Chenjun Xiao, Bo Dai, Jincheng Mei, Oscar A Ramirez, Ramki Gummadi, Chris Harris, and Dale Schuurmans. Understanding and leveraging overparameterization in recursive value estimation. In International Conference on Learning Representations, 2021.
Chenjun Xiao, Ilbin Lee, Bo Dai, Dale Schuurmans, and Csaba Szepesvari. The curse of passive data collection in batch reinforcement learning. In International Conference Artificial Intelligence and Statistics, pp. 8413 8438. PMLR, 2022.
Mengjiao Yang and Ofir Nachum. Representation matters: Offline pretraining for sequential decision making. In International Conference on Machine Learning, pp. 11784-11794, PMLR, 2021.
Mengjiao Yang, Sergey Levine, and Ofir Nachum, Trail: Near-optimal imitation learning with suboptimal data. arXiv preprint arXiv:21100 14770, 2021.
Hengshuai Yao and Csaba Szepesvári. Approximate policy iteration with linear action models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pp. 1212-1218. 2012.
Denis Yarats, Rob Fergus, Alessandro Lazaric, and Letrel Pinto. Reinforcement learning with prototypical representations. In International Conference on Machine Learning, pp. 11920-11931. PMLR, 2021.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. arXiv preprint arXiv:2006. 10742, 2020.
Anru Zhang and Mengdi Wang. Spectral state compression of markov processes. IEEE transactions information theory, 6665):3202-3231 2019.
Tianjun Zhang, Tongzheng Ren, Mengjiao Yang. Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making linear mdps practical via contrastive representation learning. In International Conference Machine Learning. pp. 26447-26466. PMLR, 2022a.
Tong Zhang. Information-theorcii upper and lower bounds for statistical estimation. IEEE Transac- tions on Information Theory, 52(4): 2006.
Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block mdps: A model-free representation learning approach. In International Conference Machine Learning, pp. 26517-26547. PMLR, 2022b.
14

---

Published as a conference paper at ICLR 2023
A MORE RELATED WORK
Representation learning in RL has attracted more attention in recent years. Within model-based RL (MBRL), many methods for learning representations of the reward and the dynamics have been proposed. Several recent MBRL methods learn latent state representations to be used for planning in latent space as a way to improve model-based policy optimization (Oh et al., 2017; Silver et al., 2018; Racaniere et al., 2017; Hafner et al., 2019).
Beyond MBRL, there also exist many algorithms for learning useful state representations to accelerate RL. For example, recent works have introduced unsupervised auxiliary losses to significantly improve RL performance (Pathak et al., 2017; Oord et al., 2018; Laskin et al., 2020; Jaderberg et al., 2016). Contrastive losses (Oord et al., 2018; Anand et al., 2019; Srinivas et al., 2020; Stooke et al., 202 1), which encourage similar states to be closer in embedding space, where the notion of similarity usually defined in terms of temporal distance (Anand al., 2019; Sermanet al., 2018) or image-based data augmentations (Srinivas et al., 2020), also show promising performance. Within goal-conditioned RL (Kaelbling, 1993; Schaul al., 2015; Andrychowicz et al., 2017), various representation learning algorithms have been proposed to handle high- digeesiimnsional observation and goal spaces, such as using variational autoencoder (Nair et al., 2018; Pong et al., 2019), or representations that explicitly capture useful information for control, while ignoring irrelevant factors of variation in the observation (Ghosh et al., 2018; Lee et al., 2020).
Beyond these representations on the state space, there are other kinds of representations that are designed for specific tasks. For example, Touati & Ollivier (2021) proposed to deal with the reward transfer task by learning reward-dependees feature F(s, r) such that the greedy policy with respect to F F(s, a,r) r optimal under r.
B IMPLEMENTATION DETAILS
In this section, we provide more implementation details of SPEDER for online exploration.
Representation Learning. We parameterize the representation network the (s, a) and u(s"), and optimize the representation in Line in Algorithm with the data collected the replay buffer D, via minimizing the following objective:
L(),)) = [D]
Σ (#2,0..9441)ED
(0(s; ( ((s:+))((sH+))) +
Σ D
[p(s))A(ss)T (((s))
2d Dbasel
Aontha
Σ
Σ
Σ Likelld
836 d
(
8gk d
+
DD
(s,,a))- (d/iatiiD
27
+ Aprob
Σ
log
Σ By Eroon
o(si, m(0;))
[D]
Drasel
(ELD
where p(s) is a base measure on the state space and |resel = { where sj p(s), Aotho and Aprob are coefficients of the regularizers that can help enforce & to be orthogonal (see Wu al. (2018) for more details) and ø(s, a) (us') to be valid conditional density (see Ma & Collins (2018) for more details) accordingly.
Planning module. We implement Line 9 in Algorithm I with SAC algorithm (Haamoja et al., 2018) upon the learned feature. Specifically,
- We parameterize the critic network Qo as a two-layer MLP on top of the representation (s(s,, a), whose parameter will be frozen.
The critic network and the actor network SAC are both updated with the samples collected in the replay buffer.
Exploration bonus. We can optionally add the exploration bonus (Line 8 in Algorithm 1) discussed the main text.
15

---

Published as a conference paper at ICLR 2023
C ALGORITHM FOR OFFLINE POLICY OPTIMIZATION
For completeness, we include the algorithm for offline policy optimization with SPEDER here.
Algorithm Offline Policy Optimization with SPEDER
1: Input: Regularizer X, Parameter a, Model class F, Dataset sampled from the stationary
distribution of the behavior policy
2: Learn representation ö(s, a) with D via equation 10.
3: Set the empirical covariance matrix
Σ
((s,a)o(s.0) AI. (s,a)ED
Σ
4: Set the reward penalty: / -
5: Solve से arg max, V P.
6: Return
D PROOF DETAILS
D.1 NON-ASYMPTOTIC GENERALIZATION BOUND
In this subsection, we consider the non-asymptotic generalization bound for the & minimization. which is necessary for the proof of series of key lemmas (Lemma and Lemma 15) that are used the PAC guarantee of the online and offline reinforcement learning. For simplicity, we denote the instance space as X' and the target space as Y and we want to estimate the conditional density p(ylx) = (x, y). Assume we are given function class F; (X x J + I with f E F, as well as the data D := (I.,, 4:){= where r; Di( V1s-1), Vi p(-12;) and D; is some data generating process that depends on the previous samples (a.k.a a martingale process). We define the tangent sequence D' {0/. v/)} where x ~ (21:1-1 V1a-11 and y p(-(x(). Consider the estimator obtained by following minimization problem:
f = arg min feF
2f( 91) + Σ
Σ DEY
P(x.))
(14)
where the summation over the counting measure y for discrete case can be replaced by the integration over the Lebesgue measure of y for continuous case. We first prove the following decoupling inequality motivated by Lemma 24 of (Agarwal et al., 2020).
Lemma 4. Let L(J.D) E ElS. U:),, D' is tangent sequence of D and F(D) be any estimator taking random variable D as input with range F. Then
ED exp (-L((DD), D) - log
D'II] log (51) 11
Proof. Let ग be the uniform distribution over FF and F -> RR be any function. Define the following
exp probability measure over p(f) = Excrexp(otfi) Then for any probability distribution Ω over F.
have:
(L
Σ log R(f)
p(f)
FEF
Σ
log + *(f)([]) + log Σ exp(g(f))
JEF
fEF
16

---

Published as a conference paper at ICLR 2023
[T( log + log [F]]
Σ
#{Dg(s) + log Ey-o exp(
JEF
JEF
=L((f| - #ff)((f) + log Bynr ex)(g(f))
FEF
< FI - Σ
Bo exp(g(f))
JEF
Re-arranging, we have that
Σ - log |F| < log y~x exp(o(f)).
Take g -)(, - log lexp(- [')]], # f(D) obtain that for any D,
-L(F(D), log Ep exp( L(F()L(((D), D))) log | < log EST exp( (xp(-L((D)..D)
ED exp( exp(-L(f(D),
We exponentiate both sides and take the expectation over D, which gives
exp( - L(F(D)) D))
Ep exp (-L(f(D), D) - log ED. [exp(= D()) log (F1) < Es En
Ep exp
-L(F(D), D D))
Note that, conditioned on D, the samples in the tangent sequence D' are independent, which leads to
ED exp [-((()) = II
exp (B(ess)>D, [-[[, (ri, m.)i)) ==1
As result, we can peel off terms from down and cancel out terms in the numerator. Hence, we have
ED [-op (I(F(D). - log Ep
exp (-I((D)) - log [F1)] < 1,
which concludes the proof.
Theorem 5. Assume |F| < co. fo F and lf C. F. Then with probability at
least 1 - 8, we have
E. ERNDD - < lolog|F1/1.
where C' only depends on C.
With Chernoff's method, we have that
[exp (-L((D))Dii) L(F(D)) log [F| + log 1/6.
log EDi
Take
(2., (xf f(x,,v)) + Σ
(f(x.1)² fz(xx.1)))
yEy
and
I(f.D) =p
Σ ((: - f(x.. vi)) +
(f(zi,)2 ((an))3-'(xrru))))
DEY
where p 0 is constant determine later. As F(D) is obtained by minimizing L(f, D), and f E F. we have L(f(D), & L(f*,D) < 0. Furthermore, as D' the tangent sequence of D, direct computation shows
FF - log Ep (exp (-L(F(D),D1) < log 8
17

---

Published as a conference paper at ICLR 2023
D1)] with our target Ei= E 1I f (2i, )12 using the method introduced in Zhang (2006).
-L(F(D)))))
We now relate the term - log Ep exp
Note that Eyey f(z, v) 1, as lo & C, with straightforward application of Hölder's inequality, we have that Evey f(z,)) y)² C. We then consider the term
E ((x3) [tf, ()) + E ((ma))))))) [1ff. (I,, (:))
()(())))) + f (x)))))) - 3
v) -1(x,)))
NEY
WEY
((f(m)))) - 8C +3 3..3EE(ee E(f(r,))) (cx.))))
VEy
yEY
200C
Σ ((f(x))) - (x,,
vEY
=,0CB,, [CS, (11, v:l)ll
As ((,) [I(f, (m, v: E O, we can conclude that
(x [(ff, (at, u,)) & (20CB [Vf,, (rx, v.))
Furthermore, it straightforward to see [I(S, v.)) & 3C. With the last bound in Proposition 1.2 in Zhang (2006), we have that
log ED exp (-I.((D), D')]
log E (a..))) [exp(- - ppl(ppp(s (xi, 9:)))]
BL [[f,, (o,, vi)) + exp(3pC) 3pC
E (B [[(f, (a,, v:))
902
0 20(exp(3/C) - 3/C - 1)
E (a: (n) D. [If())))) - (x1,
9C
As exp(x) x 1 0.5x 0, know there exists sufficiently small p that only depends on C, such that 9pC > 20(exp(3pCC) - -3pC 1). Hence, we know that,
9C
F
Be (f(,,,) (xx, )12 9pC - 20(xx(33pC) 3pC 1) log
Compared with the MLE guarantee For discrete domain, as L2 norm is always bounded by L norm, guarantee is weaker than the guarantee of MLE used in (Agarwal et al., 2020; Uchara et al., 2022). However, for general cases, L, and L2 does not imply each other, and hence we cannot directly compare theoretical guarantee with the MLE guarantee. Nevertheless, method is easier to optimize compared to the MLE, which makes it a preferable practical choice.
D.2 PAC BOUNDS FOR ONLINE REINFORCEMENT LEARNING
Before we start, we first state some basic properties of MDP that can be obtained from the definition of the related terms. For the state visitation distribution, straightforward computation shows that
ds(s) = (1 7)s(s) + VEsaag (()(3,)).
Meanwhile, we have that
1
V P,r 1- -
B Se a (1)()))
18

---

Published as a conference paper at ICLR 2023
For now, we assume (- :) is valid probability measure, P F, and the following two inequalities hold Vn E N+ with probability at least 1 - ò:
E Bgrpa (( (l P(|s,, a)ll <<n
Es ((A) (.),, P(+|s, a)ll <Gn
Proof Sketch
Our proof is organized as follows:
Based on Theorem 5, prove one-step back inequality for the learned model (Lemma 7), which is further used to show the optimisticity. i.e., the policy planning on the learned model with the additional bonus upper bound the optimal value up some term (Lemma 9).
We then bound the cumulative regret of the adaptive chosen policy (Lemma 13) based on the established optimisticity, and further exploit a one-step back inequality for the true model (Lemma 10) and standard elliptical potential lemma (Lemma 20).
With standard regret to PAC conversion, we obtain the final PAC guarantee (Theorem 14).
We first state the following basic property for the value function:
Lemma (L2 norm of VT,), For any policy n, we have that
IVP.-ll2 & 2d (1+
dr2 (1 7)3
1 -
Proof. From the properties of low-rank MDP, know there exists w", | Q7, = o² (s, wx. Then we have
vd
and
1 vm (s)) ds
| 11
= -/6 (J1 x(abb) da 2
ds
(J r(s,a) (2) ds
ds 2y² V (p, ds
2
r(s,a) da
(1 -1-98 --2 Js (LA 110"
2dy
]² ds
2dd
+
(s) a) da
dy2
<dd
1+ (1 21-
d
< (1 7)2
which concludes the proof.
Before we proceed the proof, we first define the following terms. Let -s) = =
With slightly abuse of notation, we also use Pa a) = 1 Σ" dp. (s, a). and use P/, to denote the marginal distribution of s' for the triple (s, a, 8') Pm (s)U Pd a). For notation simplicity, we denote
Ep, xU(A), =nd = pm (()) (() T) + AnI,
Pp =n
(s.a) .p.. [ + Xnl,
Σ.. =n [o(s, ()) AxI.
The following lemmas will be helpful when demonstrate the effectiveness of our bonus:
19

---

Published as a conference paper at ICLR 2023
Lemma 7 (One-step back inequality for the learned model), Assume g : A IR satisfies that l & Bx I.fAa(,,0) dal12 & B2, then we have that
(( ()(s, v A) (
|
B (s) Bzncn An Bgd B(s,a)ndy
Proof. Note that
((s.a)=d Pe (g(s,a)} = (3, .n (0) + (1 (at. (/ A
For the second term, note that (7)()) 2 - 7))(),, hence
(1 7 ) [0
<(1 7) (mmpar((1)(0((ss00)
p(s)t(a|s)[A (z((,a))
-(1 1) Bomppaanll)))
(x(
< V (1 L) (...))))
For the first term, we have that
E (3,0)= sn ( (1) {g(s.a)}
= =B (5)
I ( a) ds
<Basaaya
on xu.on
where for the inequality we use the generalized Schwartz inequality. Note
16 a)
Pr
(Son
An 111 sxA (
=n =nEropnnee(A)))
(21BBsppiinn((A) (Von de 27
(ol Uxx (IS
2 /
+ ++2nB +2nBgupaaneeln
Mo, B2 d.
With Jensen's inequality, we have
[U. P(sls, ds da
E Exephase((A))
an b (s)(),)))
E. Eanph awm (0)
A B Ben ((d) axll {g (s,a))
Meanwhile,
(Pa(s)3,)) P(433,a)7(als)g(e (B: a) ds da )
Esppa
20

---

Published as a conference paper at ICLR 2023
2
Pa(-18,0) P(11,,
x(al-)g(;:0) da
2
//- 1/1./A g(: a) da
- P()3.
<Bg
where the last inequality is due to Theorem 5. Substitute back, we obtain the desired result. Lemma 8 (Concentration of the bonus term). Lef An ((dlog(r)F(/6)), and define: P.n x =nBorpp a)Φ(,, a) + An
En
Σ (1),, uz) + AnI.
<E[m]
Then there exists absolute constant 6₁ and Cz. such that
Vn E N+ Vo C. (iclll(sss, a))ss pi < {lld(s,0)ll_} & callØ((s a)ll which holds with probability at least 1- 5.
Pre x41.
Proof. See (Uehara et al., 2022, Lemma 11).
With these lemmas, we are now ready to show the optimism. Lemma (Optimism). Let
dd ddILAAn
an =0
1 1-7
An = (rlog(nlFFF/
then for any policy we have
2|Ald
dd (1+
[T-783
Sn
V Par
> Vprr
(1-
Proof. With the simulation lemma (i.e., Lemma 19), we have that
V
the
VPr
1
B(sa)aay [bn(s, a) ((o0)+++)) (e'laa) [V), ((s [V7, (5')]
Consider the function g on S A defined follows:
g(s, a) == (P( (s'] E (p [VE,('')] With Hölder's inequality, we have that lloloc < 1-y. Furthermore, as
g(s,a) as I a (s') + an( [ ( (s, / || // (TTT))22
< (10 + (s.
Vd
where the first inequality is due to the triangle incquality; the second inequality is from the Cauchy- Schwartz inequality; and the last inequality comes from the fact that |l & 1-y. Thus, we have
- | ( g(s,a) (( ds
1/, a(. ()
2
21

---

Published as a conference paper at ICLR 2023
d
Is ( (s,))) / 11 (8, a)ll a))l ds
7)²
4d
(1-7)3
where the last inequality is due to Assumption and the fact that (a + bb² 2 + bb). Invoking Lemma 7, we have that
B(aa)aa [1(s,a)} & (11- 7) Al an (s,
+7 + P an {s)( + (1 - (0--))26mm + 4dpd
4d2
(1 (]- BBaaa |
on xMx
Note that
(0 a)}
=B =Bmpp, ( Pa(
-P(61))))) VT (5') 2
<B <Bx-pr p()|s, Pa 1 /
dy2
2dd
1 (1 1--
(1-2)²) S..
where the first incquality is due to the Hölder's inequality and the last inequality is due to Lemma 6. With the selected hyperparameters and Lemma 8, conclude the proof.
L
To further provide the regret bound, we need the following analog of Lemma Note that, here we don't 't require P'a.
Lemma 10 (One-step back inequality for the true model). Assume S x A - IR satisfies that lIg|loo & Bxx then we have that
(a(8) a)} & 7))-))ABBBB + V
B(naaaa (o(s))))(((s,))))
(1-)))/ alLA) (s)
(s) B d. ((. (5, mi.""
Proof. Note that
B( {g(s,
-, an P( (1 (9(5, a)} + (1 - Eo 6) (g(s,)))
For the second term, note that (s) > (1 - 7)pss,, hence
(1 7) E Erppaar a)}
<(1 7) (1
((s))(a)s)(A) 0((s.a))
=(1 N/ Bampaaan((A))
Pn(s)
V/C (1->) (1
For the first term, have that
((3,))d (o (00
=E(g,a)ap 6² (3,a)
U/ 4 (")))((a)))((s a) ds da
22

---

Published as a conference paper at ICLR 2023
1/ " (s)))((a))))( a) ds da
BBsayyar (3, Pri
where for the inequality we use the generalized Cauchy-Sehie Schwartz inequality. Note
Me SXA 1 (s) a) ds da
[VON P(ola, da + An
(8, B,
where in the last inequality we Jensen's inequality. Note that (1 (s, E ((a.)) (12.)) (s.
Espp a (s)
Substituting this back, we obtain the desired result.
We also need the following properties on the bonus and the value function when we plan on the learned model with the bonus.
Lemma 11 (Norm the Bonus). We have that
AAA
On vd
dvIA 1-7
[bn(s, & an
Vxn
1->²
Vin
Proof. Note that, Σ n 2 A, and as a result, we have
5-11 n.on op
Recall bn a) =
Am
on ( we know
a (s,
a Ay
(s. = 23, as)
<
n,
An
as well
1.1 bn a)
I/A 1 13, da
=03
- / (/A ( (.l.)aa))ss on da ds
a
/ (/ (I da) ds
An
a,3 d
An
d|A
Combined with the fact that
we conclude the proof.
VAn
Lemma 12 (Lg norm of V
For any policy have that
+t. b..
2
V
<
$1300
3d
+
3a d Xn
+
3d222
[ 1
Vha
On
d1.5 AIA
(1 7)2
(1 7)
23

---

Published as a conference paper at ICLR 2023
Proof. We have
Pon ||
?
1
VT Pni (8) 2
ds
1 (L ((als) (((s,))+bn(s)) + +08 r., (s,aa) da ds
< / (/A (r(s, (((s +) + P.. (s,a) da ds
2
<3 / (1, [r(s, [)(s,a)) da ds +3
/
an ()
1-1 da da ds
s
pnión
rh, (s, +3²² / (11198 Phi
2
2
da ds
3 3d (1+ ann)
Vin
<3d
An
(1 (1-7)²
d3 |Al
- 7)
which concludes the proof.
Now we are ready to prove the following regret bounds and obtain the final PAC guarantee. Lemma 13 (Regret). With probability at least 8, we have that
|A (log(NNNF) (N(F1/8) log (1
N
Σ
VV
Vp. S
71
NN F1/8)
Proof. Standard decomposition shows
Vp Vp.
7d 2|Ald [ [T-]]²
Sn
V Pb, +
Vp,rr
(1 (1
2|Al [I -2d Sn
VTa Par
(1-
1
7 B(o,a)aaT" (bn(s.a) + + (V. V P.. (8') >E
(V P. Por4 (6))
72d 2|Ald (1
Cn [--))²
(1-?)
Applying Lemma 10 to B( (s, a)}, we have that
E (s.0))dd (s)
(1 AB s aill()) (s,
+ / An (i (b) a)} +
[1I [5,)(
24

---

Published as a conference paper at ICLR 2023
Note that
(n(ss (8. w)
E (e((A)
Andon
= =Bs-pnaad((A))
(en(s,0) () - @u(s,a))
=Tr ((LA)) (on(s,a) (nE (nEemp..o () + +dm1) -)
hence, with the concentration of the bonus, we have
(1 (1-7) dL
(e (b)
va A + 72 ((a |1 (3. a) بلاة
We then consider the remaining term. van
With slightly abuse of notation, define g(s.a) With Hölder's inequality, know that
(a Partbo (s') Ep(s Puirtbn (
v
(1((s & 2 VTn
Pa. l.
Van
Applying Lemma 10 to
B(ra))ap (g(8. a)), we have that
((, a)}
<V(1 (1 })A S-. MAA
472dd (vTn + +aa)² (1-
+ +V ww
B (5, aل
Note that
E a (s,a))
(1 (P)(5'ssa)-P((11)
Vin Printon (6') )6t))
27
-E
(alppaand(AA) (a((1s,a)= P(-|s.a)
Van
129
17
Pairtba
1+ a
dy² (1+
an vin
A3
<3d
+
Sn S
dn
(1 71-
(1 7)-
Hence,
B(sa)aaf' (g(8,a)) S (1 LARG.
d3 L d3 |
E B(rra)ya [100 (8.8))ls=--))
V (1-7)4 +
(1 7)4
Finally, with Lemma 20 and notice that \ & A2 E ... & Av. we have that
Σ E ((..)~apo (3."(,,))
NTr (B (3, (6))) Ep100 <V
An N
Nd
X1
25

---

Published as a conference paper at ICLR 2023
Combine the previous terms and take the dominating terms out, we have that
|A lo
(N(F1/6)
N (1 (1+ dollg(N F1/8)
Σ VV VP &
log
(1 71-
which concludes the proof.
Theorem 14 (PAC Guarantee). After interacting with the environments for θ 1
(1-7)%²2
episodes, we can obtain an e-optimal policy with high probability. Furthermore, with high probability, for each episode, we can terminate within (11((1 7)) steps.
Proof. It directly follows from the standard regret to PAC reduction. See Jin et al. (2018); Uehara et al. (2022) for the detail.
D.3 PAC BOUNDS FOR OFFLINE REINFORCEMENT LEARNING
Proof Sketch
Similar the online counterpart, our proof for offline setting is organized follows:
We show the policy obtained by planning on the learned model with additional penalty lower bound the optimal value up to some error term (Lemma 16), with the help of an analog of the one-step back inequality for the learned model in the offline setting (Lemma 15) based on Theorem 5.
We then show the PAC guarantee (Theorem 18) with an analog of the one-step back inequality for the true model in the offline setting (Lemma 17).
We first prove the analog of Lemma 7 in the offline setting. Lemma 15 (One-step back inequality for the learned model in the offline setting). Let max,,a (L/To(als) Assume g S x A + R satisfies that I| & B. ll II 9(: a) dallz & B2.
then we have that
B(saa)a (0(s,a)} & (1 E (o (8,
+ TV (sa a)} + Bÿnca + Xx B2dd Esand |
Proof. Note that
()) ((,,))=d3 (g(s, a)} 7 (n (olss + (1 (1-7)BBaag)) (11)))))t(1o00ooomoe/ 7)
For the second term, we have that
(1 7)B s (1)
<(1 - v)v E Bempanrt(1o
((s)T(als)
=(1 /// Bpmpo
(b(s))((as)) ( (f, (s)
For the first term, we have that
E (I (1s
I/ ISXA M()77(l))))
-B (3,
<R(gaa)dd3
((3500) a)
I-1 111 ())
26

---

Published as a conference paper at ICLR 2023
Note that
1/ Sxx
(s)
27 (Von P
+
((5)r(als)g(ssa)
ox
(Vor (((3,,))rddslg(sssddddddd
27
<2nl(ssa)
+ (z,appp [Vona ( T(als)g(s, addo))
+ AB
With Jensen's ' inequality, we have
E( (Von ((sls, ds
( (ha
B(o (s)
On the other hand,
(Vora (P(s)3,a)- P(s)3,a)) (a))s))(s, 27
P((),,)) |((15,) P(13, -P(1B,)) / m(al)))(,
(3,ā)))
-
/| | a( da
<B3Ga, where the last inequality is due to Theorem 5. Substituting this back, obtain the desired result. Lemma 16 (Pessimism). Let w max,,a {TT(als)}
/dvwGn
an =
1-7
then have
2wd
1 - 6n
y2d
{1-7}3
VD, + V VD,
(1-7)
Proof. With the simulation Lemma (iee,, Lemma 19), we have
VTr
P Pb
B(r,))mdp [bb(s,a) +
[ (o (s'] - Ep(elsa) [s)]]]
Consider g(s,a) [Ep.leleaa) (s'] EPG()a) [v]]
With Hölder's inequal-
ity, llg|loo <
- Furthermore, with the derivation in the proof of Lemma 9, we know (() da dal12 < 1- Applying Lemma 15, we have that
v2d
E (sa))=d (o(s. a)} < ((1 (--)) (no) B (92 (s)
27

---

Published as a conference paper at ICLR 2023
2d² no I (s)(s)))}+ +
(1 - 7)² log((F1/o) + 42nd
(1 (1- B(a.))a
0 a
With Lemma 6, we know
dy²
(e. (8, < 2d(1 + (1 7)² )m.
Then, with the selected hyperparameters and Lemma we conclude the proof.
Lemma 17 (One-step back inequality for the true model in the offline setting). Let w max,,a {T)()))) assume S x A + R satisfies |19 & Boo. then we have
E a(s
dl (g(3,))) < v () (s)(s,))}
+ (aa
B2 ((aa))d (50
Proof. The proof is identical to the proof of Lemma 7.
now provide the PAC guarantee for the offline setting.
Theorem 18 (PAC Guarantee). With probability 1-ô, V baseline policy including history-dependent non-Markovian policies, we have that
VT
V Pp
(1-7)6
where C is the relative conditional number under 6¹, defined as
x: T TE 19 10 (s, (s, 1r
C sup wERd x (( (8,
(8, a) (s, a) T/
Proof. Standard decomposition shows
Vp, V
2wd
1 + (I--25) Sml)
2dd
<VPr 1/2 prr +
(1 7)
2wd
1
(1-12))
2dd
Sr
<VPr - V Vir +
(1 7)
=B(e,amdp ((ssaa) + +Bpro s.0)
V7 [V,ro(66]
-BB [+))
2wd
72d + [1-93
Gn
+ - 7)
With Lemma 17 and the identical method used the proof Lemma 13, we have that
dw di
E(s,a)aap, (b)(s,)) <
yo + a B(a,a)d3
(3)"(5,)) a> 10.)
Furthermore, define g(s, a) (e'ssa) and the identical method used in the proof of Lemma 13, we can obtain
v Poo, (8') Ep())) V Pro (6')
With Lemma 17
ddunnon
(o(tsa) S (11 - 72) + V (1 (1- (s,a)/dd
110 a) ال
28

---

Published as a conference paper at ICLR 2023
Finally, by the definition of C*, we have that
(( (8,))(,
Braayaaz
(3, a)]l PSii
Phi0"
(30
Ced
d
n
Combining the previous terms and taking the dominating terms out, conclude the proof.
E TECHNICAL LEMMAS
Lemma 19 (Simulation Lemma), With slightly abuse of notation, we have
1 V Pu,r+b Vp,, 1- 7 [(o,a)ndz b(s.a) + (R. (V P.. (V ( (6.
V VP,,, 1 γ Pair
1
E (ssaaaay
((s,a) +2 ( (V,, - Er(g [,,
Proof. Note that
Esndy. x (1
=(1 B) (a
+ (
Take f = O Puin+ we have that
Pa.r4h = = =Bspppanr((ss) O7 (o
E Eand
@ (9 -
O (s.)))
1- Es Bond
@ ( (5,, (BBu))-Bowwwpae "Bo 0 (6..)t6(6'
Substitute back, we have that
VP,r
r
1
E Eswdy a-
Q7 (3. - -(s [ (s'
(5', ad)]
rss,a)
([s a) + + [ (. (V P.rts (8') F. RP V Po.r+o
Eanay (-1))
The second equation can be obtained with similar method, which concludes the proof.
Lemma 20 (Elliptical Potential Lemma). Let My Alaxa- M, = Mn-1 + Gn where G is
symmetric positive definite matrix with |G lop then we have that
Tr(G,MM.)) < log det(Mx) 2d A < dlog (1+
Nc
Proof. By the concavity of log det(-) function and d letg))((X) dx
= -1,, we know
log (M) < log (et(Mn)) Tr(M, 11MMM,1MMMM11 (Mn-1
Mn))
loo det (M,,) Tr(M,
Telescoping, we can obtain the first incquality. For the second inequality, note that, with Jensen's inequality, we have
Tr(Ma)
log Medeet(MM
Σ log a, dlog d
& dlog(A Nc)
where o; is the i-th eigenvalue of M..
29

---

Published as a conference paper at ICLR 2023
F EXPERIMENT DETAILS
F.1 ONLINE SETTING
We list all the hyperparameter and network architecture we use for our experiments. For online MuJoCo and DM Control tasks, the hyperparameters can be found at Table 4. Therefore, set bonus scaling term to O for MuJoCo tasks. However, this bonus is critical to the success of DM Control Suite (especially sparse reward environments). Note that critic network architecture for all the algorithms in the DM Control Suite experiment.
exactly the same actor and
For evaluation in Mujoco, in each evaluation (every 5K steps) test algorithm for 10 episodes. We average the results over the last 4 evaluations and random seeds. For Dreamer and Proto-RI., we change their network from CNN 3-layer MLP and disable the image data augmentation part (since we test on the state space). We tried to tune some of their hyperparameter (e.g., exploration steps in Proto-RL) and report the best number across our runs. However, due to the short time, is also possible that we didn't tt tune the hyperparameter enough.
Table 4: Hyperparameters used for SPEDER in all the environments in MuJoCo and DM Control Suite.
Hyperparameter Value
C
1.0
regularization coef
1.0
Bonus Coefficient (MuJoCo)
0.0
Bonus Coefficient (DM Control)
5.0
Actor Ir
0.0003
Model Ir
0.0003
Actor Network Size (MuJoCo)
(256. 256)
Actor Network Size (DM Control)
(1024, 1024)
SVD Emhedding Network Size (MuJaCo)
(1024, 1024, 1024)
SVD Emheeding Network Size (DM Control)
(1024, 1024, 1024)
Critic Network Size (MuJoCo)
(1024, 1)
Critic Network Size (DM Control)
(1024. 1)
Discount
0.99
Target Update Tau
0,005
Model Update Tau
0.005
Batch Size
256
F.2 PERFORMANCE CURVES
We provide the performance curves for online DM Control Suite experiments in figure 1. As we can see in the figures, the proposed SPEDER converges faster and achieve the state-of-the-art performances in most of the environments, demonstrating the sample efficiency and the ability to balance of exploration vs. exploitation of SPEDER.
F.3 TRANSITION ESTIMATION VIA SPECTRAL DECOMPOSITION
We show that the SPEDER objective can learn valid tran- sitions of the environment. We environment, where the state is the position of the agent and the action is the velocity. The transition can be ex- pressed as s' = + at + e, where is fixed time interval and AO( I). We run SPEDER for 100K steps and the learned transition heatmap is visualized in Figure 2. The blue region the heatmap estimation via spectral de- composition and S1 is the target position of the agent. The high density region is centered around the red dot (target position S1), which means the representation learned by our objective captures the environment transition. This shows the spectral decomposition can learn a good transition function.
empty-room
Figure 2: Estimated Transition via SPEDER.
F.4 IMITATION LEARNING
30

---

Published as a conference paper at ICLR 2023
For all methods, we use latent behavioral cloning as de- scribed Section 3.2 to pre-train representations on a sub- optimal dataset D then finetune the expert dataset DF for downstream imitation learning. We also compare with baseline behavioral cloning (BC) (Pomerleau, 1998), which directly learns a policy from the expert dataset (without latent representations) by maximizing the log- likelihood objectíve, (ss,)))P((D=*) log TT s)]-
+
Figure 3: AntMaze navigation domains mazes of medium (left) and large (right) sizes.
We report the average return on AntMaze tasks, and ob- serve that SPEDER achieves comparable performance as other state-of-the-are representations downstream imitation learning (Figure 4). We also observe that the normalized marginalization regularization equation 11 helps performance (Figure 5). We provide the performance curves for imitation learning in Figures 6 and 7.
For TRAIL. OPAL, SPIRL, SKiLD, and BC, we used the same hyperparameters as reported in Yang et al. (2021). For all methods, we pre- pre-trained the representations for 200K steps using Adam optimizer with a learning rate of 3e-4 and batch size 256. For latent behavioral cloning, we train the latent policy æz for IM iterations using learning rate of le-4 for BC, SPiRL, Skil.D, and OPAL, and 3e-5 for SPEDER and TRAIL (both EBM and Linear). We found that decaying the BC learning rate helped prevent overfitting for all methods. We evaluate the policy every 10K iterations by rolling out the policy in the environment for 10 episodes, and recording the average return. The representations and action decoder a were frozen during downstream behavioral cloning. All imitation learning results are reported over 4 seeds.
Both the action decoder Ta and the latent policy z2 parameterized multivariate Gaussian distribution, with the mean and variance approximated using a two-layer MI. network with hidden layer size 256.
For SPEDER and TRAIL, & and are parameterized as a 2-layer MLP with hidden layer size 256, and Swish activation function (Ramachandran al., 2017) the end of each hidden layer. We ran sweep of embedding dimensions d E {64, 256} and found that d = 64 worked best for TRAIL, and d = 256 worked best for SPEDER. For SPEDER, in equation 10, and summarize the coefficients used in Table 5. For TRAIL Linear, we used a Fourier dimension of 8 8992, which has been provided more preference, while still performing worse.
sweep of coefficients for each loss term
For SPiRL, SkiLD and OPAL, we used an embedding dimension of 8, which was reported to work best (Yang et al., 2021). The trajectory encoder is parameterized as bidirectional RNN, and the skill prior is parameterized as Gaussian network following (Ajay et al., 2020). SPiRL and SkiLD are adapted for downstream behavioral cloning by minimizing the KL divergence between the latent policy and the skill prior.
SPEDER
Deep5F
SAC 12-layeri
SAC (3-layer)
PPO (3-layer)
cheetah_nn
500
cheetsh
hepper
600
150
300
100
100
0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
145
1
humanold
walker
12.5
600
600
7.5
500
400
5.0
200
200
2,5
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
Environment Steps
145
Environment Steps
165
Envrronmnn Stops
165
Figure 1: Performance Curves for online DM Control Suite.
31

---

Published as a conference paper at ICLR 2023
Table Loss coefficients used for SPEDER equation 10. We denote the loss coefficients aj for the ppia") [u((²) /=s')] /(dd) term; for the (s.a))<pp [0(s, a))(s, = Ta/ term; and dg for the additional normalization regularization term in equation 11.
SPEDER w/o normalization
SPEDER w/ normalization equation 11
Domain
41
d2
d1
d2
43
caamaaze-arge-diieee
0.1
0.1
0.01
0.01
antmaze-large- larneezp-a
0.01
0.01
1.
0.01
untmaze-meddum-divert
0.01
0.1
1.
0.1
autmaze-meddimm-lly
1.
0.01
1.
0.1
1.
antmaae large diversevv
antmaze- antmaanelaagge large play-vi
antraaze medium diverse-vl
antmare medium play
SKILD (t=10)
SPRLL (t-1)
Methotis
(t-1)
OPNL (t-10)
(Linear)
SPEDER (Ouns)
Figure 4: Average return on imitation learning tasks from D4RL AntMaze (Fu et al., 2020). BC corresponds to behavioral cloning on the expert dataset without latent representations. All other methods pre-train representations on a suboptimal dataset, and then finetune on an expert dataset.
Methoes
Hammaze-large-divesse
Harmmaze-largepllaae pla---l
antmaaze-mediinn
SPEDER wio
return
return
Figure 5: Ablation of SPEDER with vs. without normalized marginalization regularization equa-
tion 11.
100
100
300
100
80
50
80
SOLD [=1]
SELD (w010)
60
C0
mutumn
60
SPILL (=1]
SNAL (t-10)
GSU I--3
20
(lw10)
0.00
0.25
0.50
0.75
1.00
0.00
0.25
D.00
0.75
2.00
0.00
0.25
0.50
0.75
2.00
0.00
0.25
0.50
0.75
1.00
30805
Figure 6: After pre-training, train latent behavioral cloning on top of the learned representations for 1M iterations. BC refers to direct behavioral cloning on the expert dataset without latent representations. The corresponding barplot of the final performance provided in Figure
200
100
SPEDER TOSTOO SPEDDh AT www.haiio.....o
0.00
0.25
0.30
0.75
140
0/00
0.25
0150
15:55
140
0000
0.25
0150
0.75
2.00
0.00
0.5
2.50
0.75
2.00
Figure 7: Performance curve of downstream behavioral cloning for SPEDER with without normalized marginalization regularization equation 11. The corresponding barplot of the final performance is provided in Figure 5.
32


Reviews:
[{"review_id": "wHLSYOScSpj", "reviewer": "Reviewer_uUqZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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.", "strength_and_weaknesses": "Strength:\n\n1. Low-rank MDPs are widely studied and the present paper proposes a new approach that claims to be more computationally-efficient\n2. Experiments and theoretical statements show promise of this approach\n\nWeakness:\n\n1. 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.  \n\n2. 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. \n\n3. 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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bv3_nk1dBtw", "reviewer": "Reviewer_PTm5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.\nOverall, the paper is well written, and it clearly compares the proposed method with existing ones through numerical examples. \n", "strength_and_weaknesses": "The paper seems to contain interesting results. \nSome typos need to be corrected, for example, \"sample\" => \"simple in Introduction.\nThe presentation can be modified in order for the reader who is not familier with representation learning. \nFor example, what is the difference between representatoin learning and RL with function approximation? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YOtFTjvAuc", "reviewer": "Reviewer_jSW9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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 \n\nA key novelty is that inter-state dependence is avoided by extracting spectral features some a policy independent state transition operator.\n\nThe paper provides analyses generalization bounds and sample complexities of the method.\n", "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.", "strength_and_weaknesses": "### Strengths\n- There is a good introduction to the spectral decomposition view. \n- Good theoretical analyses.\n- Fair literature review, with a description of why the present work is needed.\n- Remark on model based variant of this work was interesting to see.\n- Algorithmic steps are well clearly.\n\n\n### Weaknesses\n- The paper can be a little dense to read, but this could be because of the subject matter at hand. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster