A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
Authors: Tongzheng Ren
Tianjun Zhang
Csaba Szepesvari
Bo Dai
Venue: ICLR 2022 Submitted (2022)
Keywords: representation learning
reinforcement learning

Abstract: Representation learning lies at the heart of the empirical success of deep learning for dealing with the curse of dimensionality. However, the power of representation learning has not been fully exploited yet in reinforcement learning (RL), due to i), the trade-off between expressiveness and tractability; and ii), the coupling between exploration and representation learning. In this paper, we first reveal the fact that under some noise assumption in the stochastic control model, we can obtain the linear spectral feature of its corresponding Markov transition operator in closed-form for free. Based on this observation, we propose Spectral Dynamics Embedding (SPEDE), which breaks the trade-off and completes optimistic exploration for representation learning by exploiting the structure of the noise. We provide rigorous theoretical analysis of SPEDE, and demonstrate the practical superior performance over the existing state-of-the-art empirical algorithms on several benchmarks.


Under review as a conference paper at ICLR 2022
A FREE LUNCH FROM THE NOISE: PROVABLE AND PRACTICAL EXPLORATION FOR REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Representation learning lies at the heart of the empirical success of deep learning for dealing with the curse of dimensionality. However, the power of representa- tion learning has not been fully exploited yet in reinforcement learning (RL), due to i), the trade-off between expressiveness and tractability; and ii), the coupling between exploration and representation learning. In this paper, we first reveal the fact that under some noise assumption in the stochastic control model, we can ob- tain the linear spectral feature of its corresponding Markov transition operator closed-form for free. Based on this observation, we propose Spectral Dynamics Embedding (SPEDE), which breaks the trade-off and completes optimistic explo- ration for representation learning by exploiting the structure of the noise. We pro- vide rigorous theoretical analysis of SPEDE, and demonstrate the practical supe- rior performance over the existing state-of-the-art empirical algorithms several benchmarks.
INTRODUCTION
Reinforcement learning (RL) dedicates to solve the sequential decision making problem, where an agent is interacting with an unknown environment find the best policy that maximizes the expected cumulative rewards (Sutton & Barto, 2018). It is known that the tabular algorithms direct controlling over the original state and action achieve the minimax-optimal regret depending on the cardinality of the state and action space (Jaksch et al., 2010; Osband & Van Roy, 2016; Azar et al., 2017; Jin et al., 2018). However, these algorithms become intractable for the real-world problems with an enormous number of states, due to the curse of dimensionality. Learning with function approximation upon good representation is a natural idea to tackle the curse and serving as the key for the success of deep learning (Bengio et al., 2013). In fact, representation learning lies at the heart of the empirical successes of deep RL in video games (Mnih et al., 2013), robotics (Levine et al., 2016), Go (Silver et al., 2017), dialogue systems (Jiang et al., 2021) to name few. Meanwhile, the importance and benefits of the representation in RL is rigorously justified (Jin et al., 2020; Yang Wang, 2020), which quantifies the regret in terms of the dimension of the known representation based on subclass in Markov decision processes (MDPs) (Puterman, 2014). A natural question raises:
How to design provably efficient and practical algoritium for representation learning in RL?
Here, by "provably efficient" mean the sample complexity of the algorithm can be rigorously characterized only in terms of the complexity of representation class, without explicit dependency on the number of states and actions, while by "practical" we mean the algorithm can be imple- mented and deployed for the real-world applications. Therefore, we not only require the representa- tion learned is expressive enough for handling complex practical environments, but also require the operations in the algorithm tractable and computation/memory efficient. The major difficulty of this question lies in two-fold:
i) The trade-off between the expressiveness and the tractability in the design of the represen- tations;
ii) The learning of representation is intimately coupled with exploration.
Specifically, a desired representation should be sufficiently expressive' to capture the dynamic sys- tem, while still tractable in practice. However, in general, expressive representation leads com- plicated optimization in learning. For example, the representation in the linear MDP exponential
For formal definition of expressiveness, see (Agarwal al., 2020a).

---

Under review as a conference paper at ICLR 2022
stronger than the latent variable MDPs in terms of expressiveness (Agarwal et al., 2020a). However, its representation learning is either depending on a MLE oracle that is computational intractable due to the constraint on the regularity of conditional density (Agarwal et al., 2020a), or a complicated constrained min-max-min-max optimization (Modi et al., 2021). On the other hand, Misra et al. (2020) considers the representation introduced by an encoder in block MDP (Du et al., 2019), in which the learning problem can be completed by regression, but with the payoff that the represen- tations in block MDP is even weaker than latent variable MDP (Agarwal et al., 2020a).
Meanwhile, the coupling of the learning of representation and exploration induces the difficulty in practical algorithm design and analysis. One cannot learn precise representation without enough experiences from a comprehensive exploration, while the exploration depends on an reliable es- timation of the representation. Most of the known results depends on a policy-cover-based explo- ration (Du et al., 2019; Misra et al., 2020; Agarwal et al., 2020a; Modi et al., 2021), which maintains and samples a set of policies during training for systematic exploration, that significant increases the computation and memory cost in implementation.
In this work, we propose Spectral Dynamics Embedding (SPEDE), bypassing the aforementioned difficulties and answering the question affirmatively. SPEDE is established on an observation that connects the stochastic control dynamics (Osband & Van Roy, 2014; Kakade et al., 2020) with linear MDPs in Section 3. Specifically, by exploiting the property of the noise in the stochastic control dynamics, we can recover the factorization of its corresponding Markov transition operator in closed-form without extra computation. This equivalency immediately overcome the computational intractability in the model estimation in Agarwal et al. (2020a), which breaks the trade-off between expressiveness and tractability.
More importantly, the connection unifies two highly-related but commonly- known different mod- els, i.e., stochastic nonlinear control models (Kakade et al., 2020) and linear MDPs (Jin et al., 2020), therefore, provides the opportunity to share benefits from both sides: i), it sheds the light on exploiting optimistic control for exploratory representation learning, instead of expensive policy- cover-based exploration; and ii), it introduces the linear sufficient feature from the spectral space of Markov operator, in which the planning can be completed efficiently.
We rigorously characterize the statistical property of SPEDE in terms of regret w.r.t. the complexity of representation class in Section 4, without explicit dependence on the raw feature of state and action. With the established unified view, results generalize online control (Kakade et al., 2020) and linear MDP (Jin et al., 2020) beyond known features. We finally demonstrate the superior of SPEDE on the MuJoCo benchmarks in Section 5. It significantly outperforms the empirical state- oh-the-art RL algorithms. To our knowledge, SPEDE is the first representation learning algorithm achieving statistical, computational, and memory efficiency with sufficient expressiveness.
1.1 RELATED WORK
There have been many great attempts to learn variety of algorithmic representation learning in RL designed for different purposes, e.g., bisimulation (Ferns et al., 2004; Gelada et al., 2019; Castro, 2020), reconstruction (Watter et al., 2015; Hafner et al., 2019). Recently, there also several works considering the spectral features based on decomposing different variants of the transition operator, including successor features (Dayan, 1993; Kulkarni et al., 2016), proto-value functions (Mahadevan & Maggioni, 2007; Wu et al., 2018), spectral state-aggregation (Duan et al., 2018; Zhang & Wang, 2019), and contrastive fourier features (Nachum & Yang, 2021). These works are highly-related to the proposed SPEDE. Besides these features focus on state-only representation, the major difference between SPEDE and these spectral features lies in i), the target operators in existing spectral features are state-state transition, which cancel the effect of action; ii). the target operators are estimated based on empirical data from a fixed behavior policy under the implicit assumption that the estimated operator is uniformly accurate, ignoring the major difficulty in exploration, while SPEDE carefully designed the systematic exploration with theoretical guarantee; iii), most of the existing spectral features rely on explicitly decomposion of the operators, while SPEDE obtains the spectral for free.
Turning to the rigorously-justifie representation learning, a large body of effort focuses on policy-cover-based methods in "explore-then commmmmmt strategy (Du et al., 2019; Misra et al., 2020; Agarwal et al., 2020a; Modi et al., 2021). These algorithms learn a uniformly accurate modes/reprrssettation through a reward-free exploration, upon which decouple the learning from the exploration. Then, the representation from the learned model can be used for optimal policy seeking for the particular reward. The major difficulty impedes their practical application is the computa-
2

---

Under review as a conference paper at ICLR 2022
tion and memory cost: the belicy-cover-baseer exploration requires set of exploratory polices to be maintained and sampled from during training, which can be extremely expensive.
Another two related lines of research are model-based RL and online control, which are commonly known overlapped but separate communities considering different formulations of the dynamics. Our finding establishes the equivalency among the model, so that bridges these communities. Osband & Van Roy (2014) and Kakade et al. (2020) are the most related to our work in each community. These models generalize their corresponded linear models, i.e., Jin al. (2020) and Cohen et al. (2019), with general nonlinear model and kernel function within a known RKHS, respectively. The regret of the optimstic (pessimistic) algorithm has been carefully characterized for these models. However, both of the proposed algorithms in Osband & Van Roy (2014) and Kakade et al. (2020) require an planning oracle to seek the optimal policy, which might be computational intractable. In SPEDE, this is easily handled in the equívalent linear MDP.
2 PRELIMINARIES
Markov Decision Process (MDP) is one of the most standard models studied in the reinforcement learning that can be denoted by the tuple M = (S, A, r, H, If), where is the state space, A is the action space, S x A Rt is the reward function" (where R+ denotes the set of non- negative real numbers), T : S x A + A(S) is the transition and j is an initial state distribution and H is the horizon (i.e. the length of each episode). A (potentially non-stationary) policy can be defined as {TA. ] where Th : :S- + A, E [M]. Following the standard notation, we
define the value function (sh) == ET, Etth r(s,, ss) s and the action-value function
(i.e. the Q function) (sh, an) = ET,, EET r(8,, (s)ls 8, as =a]. which are the expected cumulative rewards under transition 7 when executing policy π starting from 8% and (8%, an). With these two definitions at hand, it is straightforward to show the following Bellman equation: 27((s) aA)) = r(sh, an) + Ex,, (1~T(()=%..))) V ($++1).
Reinforcement learning aims at finding the optimal policy x² = arg max, Eenu (s). It is well known that in the tabular setting when the state space and action space are finite, we can provably identify the optimal policy with both sample-efficient and computational-efficiee methods (e.g. Azar et al., 2017; Jin et al., 2018; Zhang et al., 2021) with the complexity proportion to [S|Iss However, in practice, the cardinality of state and action space can be large or even infinite. Hence, we need to incorporate function approximation into the learning algorithm when we deal with such cases. The linear MDP (Jin et al., 2020) or low-rank MDP (Agarwal et al., 2020a; Modi al., 2021) is the most well well-known reinforcement learning model that can incorporate linear function approximation with theoretical guarantee, thanks the following assumption the transition: T(s' |s, a) = (Ø(s. a); p(s'))
optimism-base -based
(1)
where S x A - H. p S H are two feature maps and H. is Hilbert space. The most essential observation for them is that, QT, (s, a) for any policy π is linear w.r. Φ(sh, an), due to the following observation (Jin et al., 2020):
V (S (11+1114111 on) dsa+1 - (ss,, an), / ViLi (sn+ ())(()))(()))) dss+1
7
Therefore, & serves as a sufficient representation for the estimation of Q that can provide uncer- tainty estimation with standard linear model analysis and eventually lead sample-efficient learning when é is fixed and known to the agent (see Theorem 3.1 in Jin et al., 2020). However, we in general do not have such representation advance* and we need to learn the representation from the data, which constraints the applicability of the algorithms derived with fixed and known representation.
3 SPECTRAL DYNAMICS EMBEDDING
It is naturally to consider how to perform sample-efficient representation learning (and hence sample-efficient reinforcement learning) that satisfies (1) in an online manner. The most straight-
II general, the reward he stochastic. Here for simplicity we assume the reward is deterministic and known throughout the paper, which is a common assumption the literature (e.g., Jin et al., 2018; 2020; Kakade et al., 2020).
*Our method be generalized to infinite horizon case, see Section 3.2 for the detail.
*One exception is the tabular MDP, where can choose a: S A -> I2 (S that each state-action pair
has exclusive |S] non-zero element and μ : S R| Al correspondingly defined to make (1) hold.
3

---

Under review as a conference paper at ICLR 2022
forward idea is performing the maximum likelihood estimation (MLE) in the representation space (e.g., Agarwal et al., 2020a). Unfortunately, for general cases, such MLE is intractable, due to the constraints on the regularity of marginal distribution (i.e., (Ø(s, a), Sg p(s') = 1) for all (s.a) E S x A. Moreover, even can perform MLE for certain cases (for example, the block MDP), as the representation is estimated from the data, which can be inaccurate, all of the existing work apply the policy cover technique (Du et al., 2019; Misra et al., 2020; Agarwal al., 2020a; Modi et al., 2021) to enforce exploration. However, such procedure can be both computational and memory expansive when we need amounts of exploratory policy to guarantee the coverage of whole state space, which makes it not a good practical choice.
To overcome these issues, we introduce Spectral Dynamics Embedding (SPEDE), which leverages the noise structure to provide simple but provable efficient and practical algorithm for represen- tation learning in RL. We first introduce our key observation, which provides us a practical way to implement the optimism in the face of uncertainty (OFU) principle.
3.1 KEY OBSERVATION
Our most important observation is that, the density of isotropic Gaussian distribution can be ex- pressed as the inner product of two feature maps, thanks to the reproducing property and the random Fourier transform of the Gaussian kernel (Rahimi & Recht, 2007):
|| 1ll2
o(zlu, 1) x exp
202
(Reproducing Property) = (k( k, 1)
(3) (4)
(Random Fourier Transform) = (so(ar, w, b), (0 w. p(w.)))
where ((:,)) is the Gaussian kernel with bandwidth k(x,, y) = exp (-
غاا H is the
Reproducing Kernel Hilbert Space (RKHS) associated with k, pfx, b) v2 cos (w Jr + b). (f. = Ep(z) [f (x)) and p(w, b) = (N 0, 1/1 u(b; 10, 2TT) with N and U denoting Gaussian and Uniform distribution, respectively.
Consider the general transition dynamics,
s' f==f(s;,) a) te,e~ NNO o²), equivalently T(s'(s, a) x exp (- [ -I'''' 2
(5)
which is the basic setup in the empirical model-based reinforcement learning (e.g., Chua al., 2018; Kurutach et al., 2018; Clavera et al., 2018; Wang et al., 2019), and the online (non)-linear control (e.g.. Abbasi-Yadke Yadkori & Szepesvári, 2011; Mania al., 2019; 2020; Simchowitz & Foster, 2020; Kakade et al., 2020). Here E Rd E A that can be continuous and I" is a dynamic function. By applying the reproducing property (3) or random Fourier transform (4) for the transition dynam- ics (5), we can obtain the feature á and satisfies (1) free. Specifically, taking the reproducing property as an example, we have that
T(s'Is, a) - (s{(f"s,, a), -), (2z0²)-d/²kk( )))
which means the problem (5) is indeed a linear MDP with ((s,a) = k(f (s. (s. a). and pus') k(s,,)) .). Following (2), we know Q(s, a) is in the linear span of the o(s, a) that is transformed from (s, a). Therefore, finding a good representation of (s,a) is equivalent to finding a good estimation of fr. In the next section, we will show that, with the well-known optimism in the face of uncertainty (OFU) principle, we can estimate f in an online manner with both sample- efficient and computationall-fficiennn algorithm.
Remark (Computation-frre Factorizable Noise Model): We want remark that, similar obser- vations also hold for large amounts of distribution, e.g., the Laplace and Cauchy distribution. We refer the interested reader to Table in Dai et al. (2014) for the known transformation of kernels and features. Here we focus on the Gaussian noise, as Gaussian distribution is the most natural continuous distribution we should work on.
3.2 PRACTICAL ALGORITIMM DESCRIPTION
Here, we introduce a generic Thompson Sampling (TS) type algorithm in Algorithm based on the OFU principle that leverage our observation at the previous section. At the beginning, we provide
We provide brief review on the related definitions in Appendix A.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Thompson Sampling (TS) Algorithm
Require: Number of Episodes K, Prior Distribution IP()), Reward Function r(s, a).
1: Initialize the history set Ho = Ø.
2: for episodes = 1,2, do
3: Sample f* P(f H.s).
b Draw the Representation. b Planning with fi- Executing ma-
4: Find the optimal policy T3 on f& with Algorithm 2.
5: for steps h = 0, 1,.... H 1 do
6: Execute 0 ~ (*))
7: Observe Sh+1-
8: end for
9: Set 74x = H4-1 ((8)) on sh 1
Update the History.
10: end for
Algorithm 2 Planning with Dynamic Programming
Require: Transition Model f. Reward Function r(s, a).
I: Initialize ((s, a), ju(') with (3) or (4). (s) = 0, vs.
2: for steps h = H 1, H- - 2, ,0 do
3: Calculate Q (n, a) r(s, a) + (o(s, a),_ V (s")((s)) do') H- > Bellman Update.
4: Set (s) max. Qn(s,a) (s) = arg max, Qu a). Choose the Optimal Policy.
5: end for
6: return (Th)
H-1 )
prior distribution P(f)) that reflects our prior knowledge on f*. Then for each episode, draw a from the posterior, find the optimal policy with I using the planning algorithm, execute this policy and eventually inference the posterior with the new observation. Notice that, we choose the policy optimistically with an sampled f. which enforces the exploration following the principle of OFU. Meanwhile, we only learn the dynamic with posterior inference and directly obtain the representa- tion with Equation (3) or (4), which avoids additional error from the representation learning step. As all of our data is collected with f", our posterior will shrink to point mass of f*, which guarantees we can identify good representation and good policy with sufficient number of data.
One significant part of SPEDE is the computational -effftttti planning with fk. thanks to the linear MDP formulation (6). Prior work assumes an oracle (e.g., Kakade et al., 2020) for such planning problem, but little known on how to provably perform such planning efficiently. Notce that, with the feature é(s, a) defined via (3) and (4), we know that (T, (s, a) is exactly linear in o(s, a). Yh, n. Hence, we can perform a dynamic programming style algorithm that calculate Qa (s, a) with the given feature (ss, a), and then greedily select the action at each level h which is simple yet efficient. is straightforward to show that the policy obtained with this dynamic programming algorithm is optimal with the mathematical induction. We illustrate the detailed algorithm in Algorithm 2.
In such planning algorithm, we need to calculate the term f (s')('")((')) ds' and take the maxi- mum of Q (s, a) over a, which can be problematic when the number of states and actions can be large or even infinite. We will provide more discussion on this issue later.
We then address several practical issues in implementing the proposed SPEDE:
Posterior Sampling The exact posterior inference can be hard if f doesn't 't lie in simple function class (e.g., linear function class) or has some derived property (e.g., conjugacy), apply the existing mature approximate inference methods like Markov Chain Monte Carlo (MCMC) (e.g., Neal et al., 2011) and variational inference (e.g., Blei al., 2017: Kingma & Welling, 2013). In our implementation, we used Stochastic Gradient Langevin Dynamics (Welling & Teh, 2011; Cheng & Bartlett, 2018) to train an ensemble of models for achieving the purpose.
in practice we
Large State and Action Space In general, we need to handle the case when the number of states and actions can be large, or even infinite. Notice that, when the state space is large, we can estimate the term f V++1 (s (²))(s')) ) ds' with regression based method using the samples from f (Ernst et al., 2005; Antos et al., 2008). For the continuous action space, we can apply principled policy opti- mization methods (e.g., Agarwal et al., 2020b) with energy-based model (EBM) parametrized policy (Nachum et al., 2017; Dai et al., 2018), treat the linear Q= (s, a) as the gradient and perform mirror descent and eventually obtain the optimal policy. However, this is at the cost of an additional sampling step from the EBM policy. In practice, we introduce a Gaussian policy and perform soft actor-critic (Haarnjja et al., 2018) policy update, which already provides good empirical perfor-
5

---

Under review as a conference paper at ICLR 2022
mance. To sum up. for large state and action cases, learn the critic in the learned representation space by regression, and obtain the Gaussian parametrized actor with SAC policy update step. in Line 3 and 4 in Algorithm 2, respectively.
Infinite Horizon Case Our algorithm can be provably extended to the infinite horizon case with specific termination condition for each episode (e.g,, see Jaksch et al., 2010). And in practice, for the planning part we can solve the linear fixed-point equation with the feature (88,, a) using the popular algorithms like Fitted Q Q-iteration (FQI) (Ernst et al., 2005; Antos et al., 2008). that still guarantees to find the optimal policy.
THEORETICAL GUARANTEES
In this section, provide theoretical results for SPEDE, showing that SPEDE can identify informa- tive representation and as a result, near-optimal policy in a sample-efficient way. We first define the notation of regret. Assume at episode k, the learner chooses the policy лæ and observes a sequence H-1 ((* ()) h= We define the regret of the first K episodes (and define T == KH) as:
Regret (K) [ke [Vi (=h) V vsb)
We want provide regret upper bound that is sublinear in T. when T increases, we collect more data that can help us build a much more accurate estimation on the representation, which should decrease the per-step regret and make the overall regret scale sublinear in T' As we consider the Thompson Sampling algorithm, we would like to study the expected regret Ep(s) [Regrot(K] which takes the prior If)) into account.
4.1 ASSUMPTIONS
Before we start, we first state the assumptions we use to derive our theoretical results. Assumptions on the environment We make the following assumption on the environment, which common in the literature (e.g. Azar et al., 2017: Jin et al., 2018; 2020).
Assumption (Bounded Reward). r(s, a) E [0, 1J. V(s,a) a) E 8 18xx4 A.
Assumptions on the function class F In practice, we generally approximate f with some com- plicated function approximators, function class FF that need not to be linear with certain feature map. This can be helpful for Mu- JoCo benchmarks that have angle, angular velocity and torque of the agent in the raw state, which we don't know how to construct the feature map to make ʃ linear. We first state some necessary definitions and assumptions on
focus on the setting where we want to find f from general
Definition (e-nnorm of functions). Define |l : (a) (s] a)ll2. Notice that it is not the commonly used l2 norm for the function, but suits our purpose well.
Assumption 2 (Bounded Output). We assume that || C. V. F.
Assumption (Realizability). We assume the ground truth dynamic function f E F.
We then define the notion of covering number, which will be helpful in our algorithm derivation. Definition 2 (Covering Number ( (Wainwright, 2019)). An e-cover of F with respect to a metric is a set {fthee(m] S F, such that of E F, there exists i [n], p(f. f.) S e. The e-covering number the cardinality of the smallest e-cover, denoted as (F,,e.p).
Assumption 4 (Bounded Covering Number). We assume that (FF Remark Basically, Assumption means the the transition dynamic never pushes the state far from the origin, which holds widely in practice. Assumption 3 guarantees that we can find the exact f in F. or we will always suffer from the error induced by model mismatch. Assumption ensures that can estimate f with small error when we have sufficient number of observations.
<o, > 0.
Besides the bounded covering number, we also need an additional assumption on bounded eluder dimension, which is defined in the following:
Definition (e-dependency (Osband & Van Roy, 2014)). A state-action pair (s,a) E A is e-dependent on {(*t, 4:)]sem S x A with respect to F. if VS,J E F satisfying Eielo [lf(s;, u.) f(s,, a.) < satisfies that a)(ss S Furthermore, (s, is said to be e-independent of {(s;, a:) Hiem)) with respect to F if not e-dependent on ((s ai) Definition 4 (Eluder Dimension (Osband & Van Roy, 2014)). We define the eluder dimension dimg(F,d <) as the length d of the longest sequence of elements in S x A. such that 3e' 2 every element is e' é--inependeen of predecessors.

---

Under review as a conference paper at ICLR 2022
Remark Intuitively, eluder dimension illustrates the number of samples we need to make prediction on unseen data accurate. If the eluder dimension is unbounded, then we cannot make any meaningful prediction unseen data, even have large amounts of samples. Hence, to make the learning possible, we need the following bounded eluder dimension assumption.
Assumption (Bounded Eluder Dimension). We assume dimg (F, < co, Ve > 0.
4.2
MAIN RESULT
Theorem (Regret Bound), Assume Assumption 2 to 5 holds. We have that
Ee(f) [Regret(K)] & Ö(VH2T H²T [F, 11 112) dimg (F, where Ô represents the order up to logarithm factors.
For finite dimensional function class, log || I12) and dimg(F, (imm(FFT-1/2)) should be scaled like polylog (T), hence our upper bound is sublinear in T. The proof is in Appendix C. Here we briefly sketch the proof idea.
Proof Sketch. We first construct an equivalent UCB algorithm (see Appendix B) and bound Regret(K) () for it. Then by the conclusion from Russo & Van Roy (2013; 2014); Osband & Van Roy (2014), we can directly translate the upper bound on Regret(K) from UCB algorithm to an upper bound on Ez()) [Regret(K) [K)] of TS algorithm.
With the optimism, we know for episode k V% S Vo. (st). where Vi is the value function of policy Ty under the model f/ introduced in the UCB algorithm. Hence, the regret at episode k can be bounded by VOTA (sğ) - VOTh (sō), which is the value difference of the policy under the two
- (s at) (sh at 111] (see Lemma 14 for the details), which means when the estimated model f is close to the real model f*, the policy obtained by planning on ʃ will only suffer from small regret. With Schwar-Sc inequality, we only need to bound E [ke[K] Ex-o (sh a (u aB311 This term can be handled via Lemma 18. With some additional technical steps, we can obtain the upper bound on Regret (K) for the UCB algorithm, and hence the upper bound on Ep(,) [Regret (K)) for the TS algorithm. O
models I& and f", that can be bounded by
E
Kernelized Non-linear Regulator Notice that, for the linear function class F = (0TTp(s, a) :
0 E Xd] where & S x A + Rd is fixed and known feature map of certain RKHS when the feature and the parameters are bounded, the logarithm covering number can be bounded by log,N(F,e,
1122) S dep log(1/e), and the eluder dimension can be bounded by dim e) S de log(1/e) (see Appendix D for the detail, notice that we provide a tighter bound of the eluder dimension compared with the one derived in Osband & Van Roy (2014)). Hence, for linear function class, Theorem 5 can be translated into regret upper bound of Ö(H,, for sufficient large T. that matches the results of Kakade et al. (2020)?, Moreover, for the case of linear bandits when H = 1, our bound can be translated into a regret upper bound of Ö(d,T that matches the lower bound (Dani et al., 2008) up to logarithmic terms.
Compared with Kakade et al. (2020) and Osband & Van Roy (2014) Our results have some connections with the results from Kakade et al. (2020) and Osband & Van Roy (2014). However, in Kakade et al. (2020), the authors only considers the case when J only contains linear functions w.r.t some known feature map, which constrains its application in practice. We instead, consider the general function approximation, which makes our algorithm applicable for more complicated models like deep neural networks. Meanwhile, the regret bound from Osband & Van Roy (2014) depends on a global Lipschitz constant for the value function, which can be hard to quantify with either theoretical or empirical method. Instead, our regret bound gets rid of such dependency on the Lipschitz constant with the simulation lemma that carefully exploit the noise structure.
'Note that, the RKHS here is the Hilbert space that contains f(s, a) with the feature from some tixed and known kernel, is different from the RKHS we introduced in Section 3. that contains Q(s, a) with the feature k(f(ss a), where is the Gaussian kernel.
Nooe that T in (Kakade et al., 2020) is the number of episodes, and Vnax in (Kakade et al., 2020) can be viewed 2 when the per-step reward is bounded.
7

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTS
In this section, we study the empirical performance of SPEDE in the OpenAI MuJoCo control suite (Brockman et al., 2016). We use the environments from MBBL (Wang et al., 2019), which varies slightly from the original environments in terms of modifying the reward function so its gra- dient w.r.t. the states exists and introducing early termination (ET). Note that the set of environments contains various control and manipulation tasks, which are commonly used for benchmarking both model-free and model-based RL algorithms (Yu et al., 2020; Kakade et al., 2020; Luo et al., 2018; Haarnoja et al., 2018). As aforementioned, for practical implementation, our critic network consists of a representation network Φ6-) and a linear layer on the top. We follow the same procedure of Algorithm I: (1) For finding the optimal policy, we run an actor-critic algorithm (SAC). (2) We update the representation network of the critic function o(-) with a momentum from the model dy- namics network f(-). We found this prevent updating the representation of too fast. We provide the full set of experiments in Appendix E.2, an ablation on the momentum in Appendix E,3 and the hyperparameter we use in Appendix E.6.
Baselines We compare our method with various model-based based RL baselines: PETS (Chua et al., 2018) with random shooting (RS) optimizer, PETS with cross entropy method (CEM) optimizer and ME-TRPO (Kurutach et al., 2018). Note that these are strong empirical baselines with many hand- tuned hyperparameters and engineering features (e.g., ensemble of models). It is usually hard for any theoretically guaranteed model- -ased RL algorithm to match or surpass their performance (Kakade al., 2020). Another natural baseline is the successor feature (Dayan, 1993), which is one of the representative spectral features. We compare with the deep successor feature (DeepSF) (Kulkarni et al., 2016), and for a fair comparison, we only swap the representation objective of SPEDE with DeepSF and keep the other parts of the algorithm exactly the same.
SPEDE: Performance with the Learned Representation Following Algorithm 1, we inter- ested in how SPEDE performs when we conduct planning on top of the representation induced by the dynamics model in each episode. As most of the rigorouslyjjustffee representation learning algo- rithms are computationally imtractable/inefffiiennt to demonstrate the effectiveness of representation used in SPEDE. we compare SPEDE with the deep successor features, which is one representative empirical representation learning algorithm. Moreover, as our method essentially models transi- tion dynamics, we compare our methods with the state-of-the-art model-based RL algorithms. We summarize the results of our method in Table 2. We see that our method achieves impressive per- formance comparing to model-based RL methods. Even in some hard environments that baselines fail to reach positive reward (e.g., MountainCar, Walker-ET), SPEDE manage to achieve a reward of 52.6 and 501.6 respectively. We also evaluate our representation by comparing SPEDE to the usage of deep successor feature (DeepSF). Results show that on hard tasks like Humanoid and Walker, SPEDE manages to achieve 452.6 and 336.0 higher reward respectively.
SPEDE-REG: Policy Optimization with SPEDE Representation Regularizer In order to eval- uate whether our assumption on linear MDP is valid in empirical settings and study whether such as- sumption can help improve the performance, we add our model dynamics representation objective as a regularizer in addition to the original SAC algorithm for learning the Q-function. Specifically, the algorithm SPEDE-RES consists of vanilla SAC objective with an additional loss putting constraints on the representation learned by the critic function, due to the intuition that the representation should satisfy the linear MDP dynamics. We compare its performance with the vanilla SAC algorithm to show the benefits of dynamic representation. Results in Table 2 show that adding such constraint significantly improve the performance of SAC: on hard tasks like Hopper-ET, S-Humanoid-ET) and Humanoid- ET, SPEDE-REG improves the performance of SAC by 694.8, 1875.7 and 2000.4.
Discussion of the Results We observe that in the environments with relatively simple dynamics (top row of Table 2), the proposed SPEDE achieves the SoTA even comparing with SAC. However, when the model dynamics of the environment become harder (bottom row of Table 2), the difference of the performance between the two approaches begin to enlarge. Interestingly, our SPEDE achieves strong results comparing to model-based approaches, while the joint learning SPEDE-REC outper- forms model-free algorithm by a huge margin. The performance promotion of SPEDE indicates the importance on learning a good representation based on model dynamics and again shows the effectiveness of our approach in both settings.
In fact, the differences in the SoTA usage of SPEDE in easy environments and difficult environments also reveals the important direction for our future work. The current rigorous representation learning
*Our code is available at
8

---

Under review as a conference paper at ICLR 2022
Table 1: Performance of SPEDE various MuloCo control tasks. All the results averaged across random seeds and a window size 10K. Results marked with is directly adopted from MBBL (Wang et al., 2019). Our method achieves strong performance compared to pure empirical baselines (e.g., PETS). We also compare BEDEEREGG which regularizes the critic using the model dynamics loss with several model-free RL method. SPEDE-REG significantly improves the performance of the SoTA method SAC.
Swimmer
MountainCar
Peodulum
I-Pendulum
ME-TRPO" 30.1499.7
-134455.2
22.54466.
177,3-199
-126,2486.6
PETS-RS"
42.14:20.2
40.1166.
-78.5+2.1
167.9=35.8
-12.1=25511
PETS CEM"
22.1::25.2
-12.3::522
-57.91:3.6
167.==33.0
-20.5::28.9
DeepSF
23.5:1:3.5
-16.813366
-17.0:12344
168.6_5.11
-0.2:10.3
SPEDE
42.6:1..2
-7221.1
10,3:
169.5=0.6
0.0:20.0
PPO"
38.0:11.
-17.2.10.9
23.1
163.4=8.00
40.8.122.0
TRPO"
37,9:2200
-10.1::0.6
-37.241164
166.7=7.3
-27.6:::15.8
TD3
40.4.18.3
11..0..99
6..0.1:.22
161.4 14.4
-2.4.5110.4
SAC'
41.2:1:.66
-6.420.5
$2.610.6
168. 168.2-9.5
-0.24:01
SPEDE-REG
40.0=t3.8
-5.8=0.6
40.0==388
168.5=4.3
0.0:0.1
An-ETT
Hopper:
S S-Hummnnid
Humanoid ET
Walker
ME-TRPO"
42.6:221.1
4.91:400
76.1188
72.9:8.9
9.5:14666
PETS RS"
130.01 148.1
205.8.1.1..5
320.9:1822.2
106.9 106.9
..8.1...2
PETS-CEM"
129.3-36.0
355, 1517.1
110.-91..0
-2.5--6.8
DeepSF
768.1=4441
548.9=253.3
533.8++554.9
168.6=5.1
165.6=t:27.5
SPEDE
806.2:::0.2
732.2--233.9
986.411154.7
886.9=95.2
501.6:::24.00
PPO"
80.1+17733
158.0=62.00
454.3+4:6.7
451A=39.
306, 106.1-17..2
TRPO'
116.8447.3
237.4-133.5
281.3:4:0.9
229.5-1.7.11
TD3"
159.7=+1.0
205
1070.0=168)
147.7=0.7
3299.7=1951.5
SAC"
2012.74:571.
6555.1
834.6+:313.1
1794.41-458.3
2216.4=678.7
SPEDE-REG
2073.111119.7
25
277..3::77.5
3747,811078.1
2170
SPARE
DeepSE-0e A-A
PETS-CIN
FETSRS
50
150
-50
-50
-150-
50-
-100
-200
Erwionmmnt Stops
145
Eswfroitiint Stoas
165
Ensiromment Steno
1
Encronment Stops
145
We show curves of the return versus the training steps for SPEDE and modcl-based RL baselines. Results show that in these tasks, our method enjoys better sample efficiency even compared SoTA empirical model-based RL baselines.
Figure 1: Experiments on MuJoCo:
methods, e.g., Du et al. (2019); Misra et al. (2020); Agarwal et al. (2020a) and the proposed SPEDE, all rely on some model assumption. When the assumptions are satisfied, e.g., Pendulum, Reacher, and others, our theoretically derived SPEDE variant works extremely well, even better than current SoTA. However, when the assumption is not fully satisfied, although the decoupled SPEDE achieves best performance among existing model- based RL and representation learning under fair compari- son, the joint learned variant of SPEDE is more robust and promote the current SoTA with significant margin. An interesting question is whether we can rigorously justify the regularized SPEDE, which we leave as our future work.
To better understand how the sample complexity of our algorithm compar- ing to the prior model-based RI. baselines, we plot the return versus environment steps Figure We see that comparing to prior model-based baselines, SPEDE enjoys great sample efficiency in these tasks. We want to emphasize that from MBBL (Wang et al., 2019), model-based methods al- ready show significantly better sample efficiency compared to model-free methods (...PPPOOTRPO, We provide additional results in Appendix E.2.
Performance Curves
6 CONCLUSION
In this paper, introduce SPEDE, which, to the best of our knowledge, is the first provable and efficient representation learning algorithm for RL, by exploiting the benefits from noise. We provide thorough theoretical analysis for SPEDE and strong empirical results demonstrate the effectiveness of our algorithm. There are still several open problems, e.g. how to rigorously justify the regularized SPEDE. We leave these problems as interesting future work.

---

Under review as a conference paper at ICLR 2022
Ethnics Statement Our paper focus of the questions in RL, i.e., developing prov- able and practical algorithms for representation learning in online scenarios under general settings. Although there be several potential application of our work in the future, currently we cannot foresee any positive/negative social impact of our work other than the original positive/negative so- cial impact of RI.. As conduct experiments standard MuloCo benchmark, our experiments should not suffer from any discrimination// discrinination/iassfaiaesss concerns.
Reproducibility Statement Our code directly adapted from the open-sourced code base from (Wang et al., 2019) and we have introduced our implementation details in Section 5 and Appendix E. We believe our results can easily reproduced, and our code is available at http:://sitss.ooggle..o www.gggg....o/oooiww/eeeee...eee
REFERENCES
Yasin Yadksi-Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 1- 26. JMLR Workshop and Conference Proceedings, 2011.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complex- ity and representation learning of low rank mdps. arXiv preprint arXiv:2006. /08/4, 2020a.
Alekh Agarwal, Sham M Kakade, Jason D) Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods markov decision processes. In Conference on Learning Theory, pp. 64 66. PMLR, 2020b.
Mauricio A Álvarez, Lorenzo Rosasco, and Neil D Lawrence. Kernels for vector-valued functions: A review. Foundations and Trends@ in Machine Learning, 433):195-266, 2012.
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted q-iteration in continuous action-space mdps. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008.
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68(3)3337-404 1950.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 3588):1798-1888, 2013.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: review for statisti- cians. Journal of the American statistical Association, 112(518):859- 2017.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Pablo Samuel Castro. Scalable methods for computing state similarity in deterministic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10069-10076, 2020.
Xiang Cheng and Peter Bartlett. Convergence of langevin meme in kl-divergence. In Algorithmic Learning Theoory pp. 186-211. PMLR, 2018.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learn- ing in handful of trials using probabilistic dynamics models. arXiv preprint arXiv:1805.1 12114, 2018.
Ignasi Clavera, Jonas Rothfuss, John Schulman, Yasuhiro Fujita, Tamim Asfour, and Pieter Abbeel. Model-based reinforcement learning via meta-policy optimization. In Conference on Robot Learning, pp. 617-629. PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2022
Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only vl regret. In International Conference on Machine Learning, pp. 1300-1309. PMLR, 2019.
Bo Dai, Bo Xie, Niao He. Yingyu Liang, Anant Raj. Maria-Florina F Balcan, and Le Song. Scal- able kernel methods via doubly stochastic gradients. Advances in Neural Information Processing Systems, 27:3041-3049, 2014.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Con- ference on Machine Learning, pp. 1125-1134. PMLR, 2018.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.
Peter Dayan. Improving generalization for temporal difference learning: The successor representa- tion. Neural Computation, 5(4):613-6244 1993.
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 Machine Learning, pp. 1665-1674 PMLR, 2019.
Yaqi Duan, Zheng Tracy Ke, and Mengdi Wang. State aggregation learning from markov transition data. arXiv preprint arXiv: / 1.02619, 2018.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes. In UAI, volume 4, pp. 162-169, 2004.
Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Mare G Bellemare. Deepmdp: Learning continuous latent space models for representation learning. In International Conference Machine Learning, pp. 2170-2179. PMLR, 2019.
Geoffrey Grimmett and David Stirzaker. Probability and random processes. Oxford university press, 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learming, pp. 1861-1870. PMLR, 2018.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In International Conference on Machine Learning, pp. 2555-2565. PMLR, 2019.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1 14), 2010.
Haoming Jiang, Bo Dai, Mengjiao Yang. Tuo Zhao, and Wei Wei. Towards automatic evaluation of dialog systems: A model-free off-policy evaluation approach. arXiv preprint 20X 2021.
Chi Jin, Zeyuan Allen-Zhu Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 4868 4878, 2018.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03336. 2019.
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.
11

---

Under review as a conference paper at ICLR 2022
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Infor- mation theoretic regret bounds for online nonlinear control. arXiv preprint Ski::2006.12660 2020.
Diederik Kingma and Max Welling. arXiv:1312.61 14, 2013.
Auto-encoding variational bayes.
arXiv preprint
Tejas D Kulkarni, Ardavan Saeedi, Simanta Gautam, and Samuel J Gershman. Deep successor reinforcement learning. arXiv preprint
2016.
Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. arXiv preprint 1802. 2018.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuo- motor policies. The Journal of Machine Learning Research, 17(1):1334-1373, 2016.
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorith- mic framework for model-based deep reinforcement learning with theoretical guarantees. arXiv preprint 100.001807..0888, 2018
Sridhar Mahadevan and Mauro Maggioni. Proto-value functions: A laplacian framework for learn- ing representation and control in markov decision processes. Journal of Machine Learning Re- search, 8(10). 2007.
Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. In Proceedings of the 33rd International Conference Neural Information Processing Systems, pp. 10154-10164, 2019.
Horia Mania, Michael Jordan, and Benjamin Recht. Active learning for nonlinear system identifi- cation with guarantees. arXiv preprint arXiv:2006. 10277, 2020.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state ab- straction and provably efficient rich-observatie reinforcement learning. In International confer- ence on machine learning. pp. 1671- PMLR, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 131.v:1112.5600 2013.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint a7X0v22102.07035, 2021.
Ofir Nachum and Mengjiao Yang. Provable representation learning for imitation with contrastive fourier features. arXiv preprint 12X2:22105.12272, 2021.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. arXiv preprint 1702.0/702.0882. 2017.
Radford M Neal al. Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(1 (112);2 2011.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27:1466-144 -174,,117,, 2014.
Ian Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. arXiv preprint X1v.16608000732 2016.
Martin I. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceedings of the 20th International Conference on Neural Information Processing Systems, pp. 1177-1184, 2007.
12

---

Under review as a conference paper at ICLR 2022
Walter Rudin. Fourier analysis on groups. Courier Dover Publications, 2017.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 2013.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-1243; 2014.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis 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-355 2017.
Max Simchowitz and Dylan Foster. Naive exploration is optimal for online lqr. In International Conference Machine Learning, pp. 8937-8948. PMLR, 2020.
Elias M Stein and Rami Shakarchi. Real analysis. Princeton University Press, 2009.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Martin Wainwright. High-dimenssonal statistics: non-asymptotic viewpoint, volume 48. Cam bridge University Press, 2019.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020.
Tingwu Wang, Xuchan Bao, Ignasi Clavera, Jerrick Hoang, Yeming Wen, Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel, and Jimmy Ba. Benchmarking model-based reinforce- ment learning. arXiv preprint arXiv: 190.002077 2019.
Manuel Watter, Jost Tobias Springenberg, Joschka Boedecker, and Martin Riedmiller. Embed to control: A locally linear latent dynamics model for control from images. arXiv preprint arXiv:1506.07366, 2015.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-II), pp. 681-688 Citeseer, 2011.
Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in rl: Learning representations with efficient approximations. arXiv preprint arXiv:1810.04530 2018.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning, pp. 10746-10756. PMLR, 2020.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. arXiv preprint arXiv:2005. 13239, 2020.
Anru Zhang and Mengdi Wang. Spectral state compression of markov processes. IEEE transactions information theory, 66(5):3202-33 3231, 2019.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp- 4528 4521- PMLR, 2021.
13

---

Under review as a conference paper at ICLR 2022
A BACKGROUNDS ON REPRODUCING KERNEL HILBERT SPACE
We briefty introduce the basic concepts of the Reproducing Kernel Hilbert Space, which is helpful understanding paper. To start with, first define the inner product (Stein & Shakarchi, 2009).
Definition 6 (Inner Product). function (s H H - said to be an inner product on H if it satisfies the following conditions:
1. Positive Definiteness: Vu H. (u, u) 2 O, and (u, u) = a
2. Symmetry: Yu, U E H. (u, 1) E (v, u).
3. Bilinearity: Ya, 3 E R, u, U, E H. (aru + Bu, w) = ae(u, t, w) + B(w, w).
Additionally, we can define a norm with the inner product: ||u|| = V(u, (u,u,, u).
Hilbert space is a space equipped with an inner product and satisfies an additional technical condition of completeness. The finite-dimensin vector space with the canonical inner product is an example the Hilbert space. We remark that can also be a function space, for example, the space contains all square integrable functions (i.c. fR f(x)² dæ < oc, generally denoted as L2) is also Hilbert space with inner product (f. g) JR fxx)((x) dr.
We then define the kernel, and introduce the notion of positive-definit kernel (Álvarez al., 2012). Definition ((Positive-Dece Deettite- Kernel). function k X X + R. is said to be kernel non- empty set X if there exists a Hilbert space H and a feature map Φ X - H. such that Va, x' E X, we have
=xxx')=(( (0(x), (()))(())))))))))))))))))
Moreover, the kernel is said be positive definite if Vn 2 Vaaihejj) R and mutually distinct set (re hee(n) C. X, we have that
(;azk(m),)))) 0. SE|m
Some well-known kernels include:
Linear Kernll: k(x, y) (z. v). with the canonical feature map (xx)
Polynomial Kernel: k(r, v) = ((x, u) + c)m, where m E N+ and c E R+
Gaussian (a.k.a radial basis function, RBF) Kernel: k(x, exp that such kernel is positive definite.
- 20
It's known
Now we can define the Reproducing Kernel Hilbert space (RKHS) (Aronszajn, 1950).
Definition (Reproducing Kernel Hilbert Space (RKHS)). The Hilbert space H. of R-valued func- tion defmned a non-emptry set X is said be reproducing kernel Hilbert space (RKHS) is there a kernel x X - IR, such that
1. Vx X, k(x,-) E H.
2. Vo E Xx H. (f. ((, k(2,))))) - f(x (a.ka the reproducing property), which also implies that (k(z, -), k(y. -)) = k(z.v).
Here is called reproducing kernel of H.
We provide intuitive interpretation on the definition of RKHS when H. is the space of linear function. Consider = Rd and k(I, 3) = (I. y). With the definition the kernel k we can see that k(xr,)) X - R is linear function, and thus lies in H. Meanwhile, yʃ H. there exists Of such that f(x) = 07 x. We define the inner product on H via (f.g) = (0,, 0g), and thus f(x), which demonstrates the reproducing property. and shows that the space of linear function on any finite-dimensional vector space is an RKHS with linear kernel as the corresponding reproducing kernel.
(f(, (o -)))x = TT
14

---

Under review as a conference paper at ICLR 2022
We state the following theorems without the proof. Theorem 9 with unique RKHS H.
(Aronszajn, 1950)). Every positive definite kernel is associated
Notice that, Moore-Aronszan theorem guarantees that all of the positive kernel can be represented as the inner product in certain Hilbert space, hence we can have a linear representation of the Gaussian distribution induced by the reproducing property of Gaussian kernel, we illustrated in the main text.
Theorem 10 (Bochner (Rudin, 2017)). A continuous, shift-invarianl kernel (i.e. k(r, y) k(@ y)) positive definite and only k(z y) is the Fourier transform of a non-negative measure w. i.c.
k(x y) expliw] (x y)) dI) =
2cos(w x b) cos(w y - b) d(F(w) x P(6)),
Rd where P(b) is uniform distribution [0, 2..
2d [0.
Bochner's 's theorem shows that any continuous positive definite shift- infftriivariant kernel (e.g. Gaussian kernel, Laplacian kernel) can be represented as the inner product of random Fourier feature, which provides additional way to provide representation for certain distribution (see Rahimi & Recht, 2007; Dai et al., 2014).
B AN EQUIVALENT UPPER CONFIDENCE BOUND ALGORITHM
In this section, we provide generic Upper Confidence Bound (UCB) algorithm with the OFU prin- ciple, and show the connections and differences between the UCB algorithm and the TS algorithm. The prototype for our UCB algorithm is illustrated in Algorithm 3.
Algorithm Upper Confidence Bound (UCB) Algorithm
Require: Number of Episodes K, Failure Probability 8 (0, 1), Reward Function r(s,a).
I: Initialize the history set Mo = 0.
2: for episodes 2, do
3:
Compute Tg via
>> Optimistic Planning.
(Tk, fa)=
arg max ViJ (sp)- fEll,fEF.
where Fi defined in (9).
4:
for steps h = 1, 1 do
Execute TT.
5: Execute a ~ n (s
6: Observe 8h+1-
7: end for
8: Set Hr Ha-1 U (10 an #
Update the History.
9: end for
Notice that, the only difference between UCB algorithm and TS algorithm is the mechanism of finding we use to plan for each episode (highlighted in blue). For UCB algorithm, perform optimistic planning, which finds the fü that potentially has the largest cumulative reward. However, such constrained optimization problem is NP-hard even for the simplest linear bandits (Dani et al., 2008). Instead, for TS algorithm, we only sample the fa from the posterior distribution, which gets rid of the complicated constraint optimization. We are interested in the UCB algorithm, as the worst case regret bound of the UCB algorithm can be directly translated to the expected regret bound of the TS algorithm without the need of explicit manipulation of the prior and the posterior(Russo & Van Roy, 2013; 2014; Osband Van Roy, 2014).
Confidence Set Construction Perhaps the most important part in OFU-style algorithm is the con- struction of confidence set Fg. To enable sample-efficien learning, the confidence set should
1. contain f with high probability, so that we can identify f* eventually;
2. shrink as fast as possible, so that we can identify f" efficiently.
In the tabular setting, F& is constructed via the concentration of www.saaaasuuu--aaaaaaa Gamma random variable (e.g. Azar et al., 2017; Jin et al., 2018; Zhang et al., 2021), and in the linear MDP set- ting, Fr is constructed via the concentration the linear parameters. As don't assume any
15

---

Under review as a conference paper at ICLR 2022
specific structures, instead constructed Fk via the concentration the lp error, following the idea of (Russo & Van Roy, 2013; Osband & Van Roy, 2014). Specifically, consider the least-square estimates defined by
H fK arg min (2, == E Σ KE[K] A=
llfsh
a.) s11111
fEF
As h/11 (s% a + o where o is the Gaussian noise added to the step h at the k-th episode, we know fK will not deviate from f a lot. Meanwhile, as K increases, the estimation fx should become closer to fr. Specifically, define the empirical 2-norm || 11,,,,
Σ
l9 a
[E(K]] h==
We can construct the confidence set based on the following lemma:
Lemma 11 (Confidence Set Construction (Russo & Van Roy, 2013; Osband & Van Roy, 2014)).
Define
FK fEF: F: 11f -fkll2,e I &VR(F,0.00)
(9)
then
p f n F& 2 1-26. 20,
(10)
k=1
where
() = 80² log( a, 112)/8) + 2Ha(12C /8d 1og(4K>H/88).
(11)
The proof can be found in Appendix C.I. Notice that, the empirical 2-norm |lf - 1l,,2, scales linearly with K, and 3k (F,8, 8, only scales log K, so the confidence set shrinks. Meanwhile, Equation 10 guarantees that f E Fx. vk with high probability. Hence, it satisfies our requirement for the confidence set.
Regret Upper Bound We have the following upper bound of the regret for the UCB algorithm: Theorem 12 (Regret Bound), Assume Assumption 5 holds. We have that Regret( (K) S Ö(V /H2T 1 No, 1/2 |I l12) dimg(FF (a,,e(FFF/1/1 T-1/2)).
where Ô represents the order to logarithm factors.
C TECHNICAL PROOF
C.1 PROOF FOR LEMMA
Proof. We first show the following concentration on the le error:
Lemma (Concentration of l2 error (Russo & Van Roy, 2013; Osband et al., 2020)). Y8 0,f S A R, we have
Van Roy, 2014; Wang
py (2 (2x + マ || 111f-1111.00 1'
- 40 log(1/0)) VKEN) 2 -
Proof. Define the filtration HA. {(st at,) )iE H-. U [(5 at ) and the random variable Zk.h adapted to the filtration Har via:
Zu. = =IIf" (s a
+ [s on)
k - k
1
= (s a s 12- [s ah) - ( a + (sh -
l at) - ( 11 + 2f att - (s) at)) et))
where ot st (* 15k.a.. at) Thus, E(Z (a,,)) -If(s at) f (st, af and z +
(s) a)) - (* 11 is martingale w.r.t He Notice that we assume an isotropic
Gaussian noise with variance o² on each of the dimension, thus the conditional moment generating function of zh + [sf at) - )l satisfies:
(A) log (A(E)(A(Zk [s att 1 (* at) (2)) He.A)
16

---

Under review as a conference paper at ICLR 2022
= Elexpl (2Xf ob) f ah), 22)
<20 >2 1f - f 1l..
Applying Lemma 4 in (Russo & Van Roy, 2013), we have that, Vx, A 120 0,
H-1
Pr-
Σ
Aus, S A(1 - 2X0²)
Σ
(5 al) - 8 (sh af)1l.. vk VhEN s 21-expe ex-exp(-x))
kE[K] A=U
[E(K]
A=D
Take À x x = log 1/5, and notice that Eke(K] the desired result.
H-1 2 Zn. L2xx(f-) - (2)x(f), we have
We construct an a-cover Fa in with respect to || 112. With standard union bound, we know that condition on f", with probability at least - 6, we have that
k2 L2,x((*) 2
111
1'1,, 4 log([1"*1188 1/8), AK E
Thus, we have that T22 (22 2
1
2
40 log(( (og((F()/5)
min P
12
2 -11 + I22 12,
I22x()-1ax((()) (Sa)
Discretization Error
We then deal with the discretization error. Assume a 2C (or otherwise we only have a trivial cover) and (s, a(s,a)ll2 I a, we have that _ (lf(s. - f as)
= (s. ()) 1/ 2 [s) (
max (1] + + (s a)l 2Ca
max (2(f (s. a). 11 2Ca Ivl
<4Ca + a² < 60a,
where the inequality is by Cauchy -chwwrtt inequality and 2C. Meanwhile, ||s ff || - (s,
-2(s', - [(,, [1[[s, (1
+ ((s.)) 2(f ff) - f(s, + 2Ca + <11 + 6Ca.
We now consider the concentration property of ||]||. Here we simply follow (Jin et al., 2019) and notice that is V wwt---oomm----ooe nomm-sub-Gaussan, we have that
IP([|e]|2 > / 22 (2/8)) d.
By a union bound, we have that
α 11
1
P(ak; ||e||2 > 2do (422H/8)
k= h=0 Sum all these up, we can see with probability 1 8, AK E N. the discretization error is upper bounded by:
Ha(12C + / (og42
As we consider the least square estimate fK. we have that (fx) L2,K S 0. Substitute back, we have the desired results.
C.2 SIMULATION LEMMA
Lemma 14 (Simulation Lemma (adapted from Lemma 3.9 in (Kakade et al., 2020))). Given f. Vss S, the value function 1 and V corresponding to the model and f" satisfies
H-1
2 (Sh, an) f(sh, arh 113
Vo (s) < 3/2
E
Σ
min
h=0
17

---

Under review as a conference paper at ICLR 2022
Proof. We first show the following difference lemma:
Lemma 15 (Difference Lemma). Assume the Irajectory {(sh) an) is generated via policy π and ground truth fr, define
VA
Σ a()
then VT (1,.., ,H 1}, have: Vo Vo =I ~ (f 1022))
[V:((+)] Vi
E L 1),02)) [sh V77 (sw)
Proof.
When 1, we obtain the result with ap (50) and (sa) r(sg. (ss))) + (o0 V1T (s4)
We only need to show the case when == 2, and the case when >> 2 can be derived via recursion. Notice that VoT (#o) - Vo -BBssoN(SS(e0.aa....
(I((1)) - -V
(11 V1 + - (1T()1))
17 (s1)
VT -Bsg,-N(((e,.a))00))
1/2 + Eeg- 077
(T(()) - (s1),,
where the last equality due to the fact that d1 (s1).
We then follow the idea of "optional stopping" used in (Kakade al., 2020) and show the following "optional stopping" simulation lemma.
Lemma 16 ("Optional Stopping" Simulation Lemma). Consider the stochastic process over the trajectories {sh, as) [ 1 generated via policy and ground truth f", where the randomness is from the Gaussian noise in the dynamics. Define a stopping time & warl this stochastic process and a given model f via:
:: min(h 2 0: (su) S (sw)
Furthermore, define random variable:
VI (*() max m (8:), V (sh)),
we have that
Σ Jeet (Behjs (i VI (8h41) - B ((fftnaa)))) VI (hhr))
ViT VJ (80) <R E
h=
where the expectation is w.r.f the stochastic process over the trajectories.
Proof. Define the filtration Fú, = (Eil/-) where is the noise that add to the dynamics at step i. Define
MA B (so) Fol
which is Doob martingale with respect to F, (Grimmett & Stirzaker, 2020). As S H, by Doob's
optional stopping theorem, we have that
VIV² (sa) Vol [[[M]] = E[ - VolF.ll.
We then provide a bound for M,. By Lemma 15, we have that
M, =E(V; (so) - [o[F.]
-E -Eg- NNi 2) (T+( -V
T-1
+ B N 12 [T((s))) - (sW)
A=1
Σ (Bs,
(shh)
Vi (SN)
18

---

Under review as a conference paper at ICLR 2022
Vi (sa)) V/ (sh))
Ba ((((en
H lagt (Bsg,NW(((en.a))oo))
Vi (Sa))
1/2 (3h))
km1
where the third inequality follows the definition of (and thus (+-)) (Tr) and (5h) VE (8)) for h < 7.)
The proof is then concluded via the following observation:
AsT (Feg.-Wi(ttnna))).. Vi (+n) V. (sh))
=I
E lAsT [ ((o,,NN(((ennn)))0)))
(sn))
V/ (+n))
Fr
(Bs, [i5(( (sn) - V/ (sh))
E
1n-i<r
Fh-
=E
1^-1<,
E
(Esg (sn)
V% (3a))
Fn-11
=I
inr (E (N)
V. (sw) - Egg (a))))))
V% (5x)
]]]
where the third equality is due the fact that 1 1Kr is measurable under Fn-1-
Before we finally provide the proof of Lemma 14, we state the following lemma that bound the expectation under two isotropic Gaussian distribution with different mean:
Lemma 17 (Difference of Expectation under Different Mean Isotropic Gaussian). V (approximately measurable) positive function g. we have that
<2]lmm #2ll, 1) o
o2) of S min
o
Proof. E oa (Ba0)))))ExxWWecocc
-Ez-N(m. g(2) (1 (e-exp exp
2(11 - (12) T + |12 12 | 1|
20
Sv 1r EE-NiuiiaM (1 11-cxp cxp We then calculate
2( M1) To
|| 1 |1 1|2 )) 2
202
2(#12 - -11) == =-1)==11100 11112211++ ||||| 112 ))²
+1|21112)
E Ez-N(mian))
exp
20"
|| - 11113 + +(2 - 111)T== 1112|| 2 |1
=1
4/1
exp
20
dz
1
2 - M1 12 + 4( 111) T z - -2111221 + 211 112 de
exp
v 2/o
20
1 -11)p) 13
211 -1113
+
V2Tod/2
exp
20²
dz
|122
1111
=- exp
Also notice that, as is positive, simple bound is that
Be-wWw. - Bew.((s s o71 < (00=))))))))
Thus,
|1 n 11
Ez-N(r [1)(())] Ee-N [o(=))] /BnNmmmeen((()))))
min
exp
1.1 -1,1
o²
19

---

Under review as a conference paper at ICLR 2022
o. then exp [102 (1laz
Notice that, if 1 Mill
2 1. Meanwhile, when
[0, 1/,
exp(x) < 1 2x. Thus,
|122 Mi 11
min { 1 +
211122 ii l1
2 22
M1 112 1
min
exp
1.1
1,
min
o²
0²
r²
which finishes the proof.
With Lemma 16, we have that Vor (sa) V/ (80)
<B
-n-
(E (Le, as)
Vi (5h)
H-1
/2ll (sh, an)
f(sk. an
( (8/++)))
h=0
#1
2|lf* an) fsn, an)3l
IE
E [e (iiinn
Vi (sh++
E
min
σ²
h=0
H
H
211f* an) ) - f(s an)3l
E
E s PP( (sniaa))) (sh+1)))
E
min
o²
A=
A=
H-1 Σ h=
2 (sh. and f(s an1
a(sh.an)
5/3
E
min
where the second inequality is due Lemma 17, and the last inequality is due to the fact that (6h+1)) < H, Vh.
C.3
SUM OF WIDTH SQUARE
Lemma 18 (Bound on the Sum of Width Square). Define
wF(s,a) == sup [[ a) f((s a)ll2-
f.feF
If heekk is non-decreasing sequence, and |fll < <C,ff e F, then:
H
Σ
) S 1 4C Hdimg 4Cdimg
(FTT
4ix (F,T (1 + log
kE[K]
h=0
Proof.
We first show the following lemma, which will be helpful in our proof.
Lemma 19 (Lemma in (Osband & Van Roy, 2014)). If [8x]ke[k] is a non-decreasing sequence,
have
#-1
1,3K + +H) (i,
Σ RE[R]
Σ h=o
Way Cok a S
Proof. We first consider when WF, (sh at) > and is e-dependent disjoint sub-sequences of (s hejk---- By the definition of e-dependent, we know || fll2,F, > ne?. On the other hand, by triangle inequality, we know ||f - fl12,E, < 2\/Br < 2//3K. thus n < 48xx Hence we 48x know when wr, (s), at) > c, then (sh, an) is most e-dependent on 2 disjoint sub-sequences of ((f,, of )EEkk-ll
We then show that, for any sequence ((s,, a;) (e)ee there is some element (sj,a)) that is e- dependent on at least dime(F.r H disjoint sub-sequences of {(s, (,,,aa))ien-1 Let n satisfies that ndim (F,im +1 N < (n + () e), and will construct disjoint sub-sequences
20

---

Under review as a conference paper at ICLR 2022
(Bi We first let B, ass,, [n]. If ($k+1, (x+1) is e-dependent each B a E [n], we have the desired results. Otherwise, we append (8k-1, 0k++) to the sub-sequence that it is 6- independent with. Repeat this process until some j n + e-dependent on each sub-sequence or we have reached N. In the latter we have - [B 2 nddimg e) (here
add episode of data), and since each element of
at most H 1 data to avoid the case need a sub-sequence is e-independent with its predecessors, [ I dimg(F,
Vi by the definition of eluder dimension. Thus [B,] dim (FF, <), Vi. And in this case, (NN,aN) must be e-dependent each sub-sequence by the definition of eluder dimension. Notice that, as our data is collected in an episodic pattern, there introduced to the construction. In this case, we know that there are at least dimm((Fe) H disjoint sub-sequences that (SN, (NN) is e-dependent, which finishes our claim.
most H sub-sequences that contains "imaginary" final episode data
We finally consider the sub-sequence = {(5], a with wyy (s% axt) > c. We know that each element in B is e-dependent on at most 40x disjoint sub-sequence of B, but at least e-dependent on
dimgt/.c H sub-sequence of B. Thus we know |B| < (A H) (F which concludes the proof.
For notation simplicity, we define wich == wy, (5h a.))) We first reorder the sequence (win [e(k + (wi
such that w 2 ... WTH- Then we have
ΣΣ
5 (sh, a
Σ wf
Σ {E|KH]
w wF
Σ (E[KH]
w
>T
1/2 S1+
Σ
w 1w,, 17-1/2
kE(K]
(E(KH]
kE|KH]
As we order the sequence, wj 2
c means
H-1
Σ
1 wy, (o) (of Z.j.
kE|K]
[]] h=
Hence know
48K
43 43 (F,e)
e
H
j H Himm (F, (F,e)*
(Fne(FFe))
which means if w; 1-1/2 then wi min 2C,
13 of F-T 1/2-1/22
Hence,
1- H x (F,T
T
4 (F,
Σ with 2T
(F,T-1/2) +
HddiddaaaaFrccmm 1/1)+1 j Hdim (F
iE KH]
Hdimg (F,T-112) + 4,8xdimm (F.T-1/2) (1 + log T),
which finishes the proof.
C.4 PROOF FOR THEOREM 5 AND THEOREM 12
Proof. Define & P-- (f* E Fe). When constructing the confidence set, take a T 1/2 and 8 0.25 in Lemma 11, which leads to
B 80² log(4N 1-1/2 || (l2)) HT-1/2 + /8do² log(16k2
With our confidence set construction, we know that EkE[K] P(εx) I 0.5. Notice that Regret [K)
Σ KE(K]
(+)
Vo (st)
<
E [VE))(V
ViTh (st0
+ H Σ P(EL) RETK]
RE KE(K]
<B
E
Te (st) 10- (o8)]
+ 0.5H
KE|K]
21

---

Under review as a conference paper at ICLR 2022
#-1
211 ( a8t) - f 1
<H312
E
min
+ 0.5H
0²
KEK
h=0
H-1
2 21 ab) - (st of
1 1
HºTE
min
+ +..5H
a2
KE[K]
h=
2HºT o² (1 4C Hdimæ (F,T-1/3) 4, dime (F,T-1/2) (1 + log T)) + 0.5H,
where the first equality is due the fact that the total reward for each episode is bounded in [0, H], the second inequality is due to the optimism and our confidence set construction, the third inequal- ity is due to Lemma 14, the fourth inequality due to Cauchy-Schwarth inequality and the final inequality is due to Lemma 18, which concludes the proof of Theorem 12. Following the idea of (Russo & Van Roy, 2013; 2014; Osband & Van Roy, 2014), we can translate the worst-case regret bound for UCB algorithm into the expected regret bound for TS algorithm, that conclude the proof of Theorem
Remark It can be undesirable that our regret bound scale with 0-1, which means our algorithm can perform pretty bad when the noise level is extremely low. is also more or less counter-intuitive We want to remark that, such phenomenon only an artifact introduced by our proof strategy. The simulation lemma (Lemma 14) works well when f(s, a) f(s, a) small. However, we need to tolerate some bad episodes to collect sufficient samples, that can eventually make the error small. Fortunately, the regret of such bad episode at most H. Hence, we can use the following strategy to get rid of the dependency on o-!
Definition 20 (Bad and Good Episodes). Define episode is as a bad episode, if E (0,1,-.. .H 1}, such that wki = WF, (sh, a the largest Hdimg [F,, g2T2/2) elements in the set {Wk,A I- Define episode k as a good episode, it is not a bad episode.
By the definition, we know there are at most Hdimp( oFo22/1//2 bad episodes. We then show the following lemma, that can be directly generalized from Lemma 18, by setting = 22 and remove the terms from bad episodes.
Lemma 21. If ( bE[KK]
(8%.ke[KK is non-decreusing sequence, and || < CCVJ F then:
H-1
Σ
En
(s ah S 0 + 43gg (F,02T-1/3) (1 log
kE[K] &s good h==
Eventually, we can obtain the following regret bound, by setting the regret of bad episodes as H, and bounding the regret of good episodes with Lemma 21.
Theorem 22 (Improved Regret Bound). Assume Assumption 2 to 5 holds. Take = o2T and 6 0.25 in Lemma 11, which leads
== S0² log(AN(F,, o
1/2 |l (12)) Ho2 + v Sdd lon (16122
We have that Regret(K)
H 80g + 1)dime(F -- 1/2) log + 0.5H + He -2
We would like to remark, that the definition of bad and good episodes is only used for the proof. We don't need to make any modification on the algorithm. Notice that, as Sg oc o², our upper bound in 22 can only scale with -1 through the logarithm covering number log(4N((F, o2T-/11// and eluder dimension dF 112)) When JF is linear function class, both term should scale with po)) ), that matches the result from (Kakade et al., 2020).
D BOUNDS ON THE COMPLEXITY TERM UNDER LINEAR REALIZABILITY
We provide the upper bound on the covering number and the eluder dimension of J when F := {0 ip 9 E R.. xd ||0||2 < W} where yp S x A + Rd. is some known feature map. We first make the following standard assumption:
22

---

Under review as a conference paper at ICLR 2022
Assumption 6 (Bounded Feature).
(iP(s, 5 e A.
D.1
COVERING NUMBER
Theorem 23 (Covering Number Bound). We have that
N(F e, l1l) (1 (1+ 2BW
4e
Proof. Notice that, by Cauchy- Cauchy-Schwartz inequality, we have that
||= sp(s, a)lla s Bleaill, Ve; E R2
max
(a.a)ESxA
Thus, denote = [Ei]ie(d] we have that
||s T (0)8
Σ lle (0s a) S B
Σ
||::112 = B² |e11
max (
max (s.0)ESxAA
*E|d
ve(d
Hence, to find an e-cover for F. we just need to find an c/ B-cover of (0:0 R4,x4 xd |101/2 - W). By standard argument on the covering number of Euclidean space (e.g. Lemma 5.7 in (Wainwright, 2019)), we can conclude the desired result.
D.2 ELUDER DIMENSION
Theorem 24 (Eluder Dimension Bound). We have that
3dpp
12W B² e²
dimg(F,c) 5 e log 3
+ 1.
Proof. Our proof follows the idea in (Russo & Van Roy, 2013). Define
Wk : sup (01 T2)0T(((ss ass
Σ
((0) - 02) (s())))))) (000-0)TT((saa))))) S 00,0 E Rdxxa |0 S W, 11221 S W
1elk-11
For notation simplicity, define sou: == ppss, az), A == 01 0, and t Exeu- Pipp. Obviously, we have that ||0]| < 2W. Moreover, by straightforward calculation, we know
Σ ((1 02) ax)) Trace(f) (xx)).
KEIK-11
(e')
Define Vy = 4x 4W2 I, start from considering the problem
max Trace(# T 0), subject to Trace(# V/8) (g/0) 262.
8
The Lagrangian can formed as
C(O, - TraceeO" (0 ( + X(Trace(O - 26²); A 2 0. The optimality condition of 0 is
(AV, - / )0 0. As V3 is of full rank, AV P has rank at least d. - 1 (as puppl is of rank 1). So the equation (AV: * )0 0, 0, E Rdy
only has one non-zero solution. Substitute back, we know that (define ||a||a = Val Ar):
sup(Traco(( (ppl 8) Traco V&0)= s 2²) = /2c'll /22/|1pxllv.- With the conclusion above, we have that wk < sup 4 Trace(0" 02 < 2 ||0|| s 2W3 S sup you Trace( TJ Vi0) S 26²} = /2e /2e||1pxlly,."
Hence, if we 2 c', then V pk 0.5. Moreover, with Matrix Determinant Lemma, if uw; 2 ',
Vi < k. we have
3 ② (V.) det (Va-VV op VE pxx) 2 (Vt
(e))
3 k-1
(e')2d
3 k-1
> det
T
4W2
2
2d
2
Meanwhile,
det(Vi) < (Trace(Vs))
(2
(e')2
d
d
d
4
23

---

Under review as a conference paper at ICLR 2022
Hence, we know
3 (k-1)/4
4 1-1
+1.
(e')²
Now we only need to find the largest k that can make this inequality hold. For notation simplicity,
define a
g2 ==1. As log(1 x) प and log x S z/e, have S n log < log(a + 1) + log - log(a + 1) + log + log(n/3) s log(a + 1) + log 3 +
(e)
n
n
3
3e
Substitute back, we can obtain the desired result.
24

---

Under review as a conference paper at ICLR 2022
E EXPERIMENTAL DETAILS
E ALGORITHM SUMMARY
Our algorithm easily built SAC. The only difference we make we decouple the critic network into a representation network ((-) and a linear layer I(-) on top of the representation. The represen- tation network governed by the model dynamics loss in SPEDE, and train a linear layer to predict the Q-value it lies in the linear space of the representation guaranteed by our analysis. We update the representation by momentum factor and keep policy update the same procedure as SAC.
E.2 FULL EXPERIMENTS
Table 2: Performance SPEDE on various MuJoCo control suite tasks. Our method achieve strong performance even comparing to pure empirical baselines. To be specific, in hard tasks like Humanoid-ET and Ant-ET, SPEDE outperforms the baselines significantly. Results with are di- rectly adopted from MBBL (Wang al., 2019). We also provide the SoTA model-free RL method SAC as reference.
Swimmer
Ant-ET
Hopper-ET
Pendulum
ME-TRPO"
30.119.7
42.6:22.11
4,944.0
177.31199
PETS-RS'
42.1=20.2
130.01148.1
205.81:36.5
167.9135.8
PETS-CEM"
22.1=25.2
81.61155.8
129.3=136.0
167.4153.0
DeepSF
13.5
768.1+444.1
548.9++253.3
168.6+5.1
SPEDE
42.6+4.2
806.2++60.2
732.2+226399
169.5+0.6
SAC"
41.2-14.6
2012.71571.3
6855.
168.2:9.55
Reacher
Cartpole
I-pendulum
Walker-ET
ME-TRPO"
-13.41:5.2
160. +
-126.2486.6
99.5+4.6
PETS-RS'
40.116.9
195.01228.0
-12.1:25.11
-0,81:3.2
PETS-CEM"
-12.315.2
199.5133.0
-20.51128.9
-2.516.8
DeepSF
-16.813366
194.515.8
-0.2.10.3
165.611
SPEDE
-7.21.11
338.2++39.5
0.0+00.0
501.58++204.0
SAC"
-6.4.0.5
199.410.44
-0.2.10.1
2216.441678.7
MountainCar
Acrobot
SlimHumanoiddEr
Humanoid-ET
ME-TRPO"
42.54426.6
68.1+6.7
76.1+8.8
776.8
PETS-RS'
-78.512.1
-71.5114..6
320.7-118.2
106.911024,
PETS-CEM"
-57.913.6
12.51129.0
355.11115..1
110.8.191.0
DeepSF
-17.0113.4
-74.411..2
533.8.114.9
241.11116.6
SPEDE
50.3#1.1
-69.013.3
986.4+154.7
886.91-95.2
SAC"
52.6-10.6
-52.942.00
843.64313.1
1794.4:1458.3
E.3
ABLATIONS
Our ablation experiments are trying to study important design choice of the practical algorithm: the momentum used to update the critic function. We summarize the results Table 3. We can see that using small large momentum factor such 0.999 shows better performance. This is intuitively understandable: large momentum factor slows down the update speed of the representation of the critic function and thus stabilize the training. Such phenomenon illustrates the importance of slowly update the representation.
Table 3: Ablation Suty of SPEDE on MuJoCo tasks. We see that a small momentum factor help stabilize the performance, especially in environments like Huamoid and Hopper-ET.
Hopper-ET
Ant-ET
S-Humanoid-ET
Humanoid-Fi ET
SPEDE-0.9 SPEDE-0.99 SPEDE-0.999
393.2.137.4
877.7.145.9
881.61335.22
232.91163.4
30..9=13.4
707.9
629.3+106.9
818. 088.+1330.
732.2+226.99
806.2+6002
986.4=154.7
886.9-95.2
25

---

Under review as a conference paper at ICLR 2022
E.4 COMPARISON TO LC3
We provide comparison of empirical results with LC3 (Kakade et al., 2020), which is also an algorithm with rigorous theoretical guarantees. Despite the major difference that we learning the representation while LC3 assumes a given feature, the performance of SPEDE much better than LC3 in tasks like Mountain Car and Hopper.
Table 4: Comparison of SPEDE with LC3 MuJoCo tasks. LC3 only achieves good performance on relatively easy tasks like Reacher. However, their performance on Hopper and Mountain Car is much worse than SPEDE.
Reacher
MountainCar
Hopper
SPEDE LC3
-7.21111 4.111.
50.3+11 27.3#8.1
732.2++26.99
-1016.5=607.4
E.5 PERFORMANCE CURVES
We provide an additional performance curve including ME-TRPO Figure for reference.
SPEDE
DeepST-SAC
PETS-CEM
RE
ME-TAPO
50
-50
-10
-100
-150
-50
220
-100
0.5
1.0
15
2.0
0.5
1.5
2.0
0.5 Ernfronment Stods
0.5 2.5
Eivisnmon Staps
165
Enstro-tment Steps
1e5
Emvroomment Staps
Figure 2: Experiments on MuJoCo: We show curves of the return versus the training steps for SPEDE and model-based RL baselines. We also include the final performance of ME-TRPO from (Wang et al., 2019) for reference.
E.6 HYPERPARAMETERS
We conclude the hyperparameter we use in our experiments in the following.
Table 5: Hyperparameters used for SPEDE in all the environments in MuJoCo.
Hyperparameter Value
Actor Ir
0,0003
Model Ir
0.0001
Actor Network Size
(1024, 1024, 1024)
Fourier Feature Size
1024
Discount
0,99
Target Update Tau
0,005
Model Update Tau
0.001
Batch Size
256
26


Reviews:
[{"review_id": "W_lQb24mGr", "reviewer": "Reviewer_amjV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "The paper studies an important problem in reinforcement learning, and shows some interesting observations. Here are some of my comments and questions.\n1. In my opinion, this paper is more like one on model-based learning since Equation (5) is the main structure studied in the paper. It is remarked that \"similar observations also hold for large amounts of distribution\". I am wondering whether the theoretical results could be straightforwardly extended for other distributions other than Gaussian distribution.\n2. I think a more detailed comparison to [1] in terms of technical novelty might be necessary. In my opinion, [1] focuses on frequentist regret bound, and thus proposes a UCB-like algorithm that requires an oracle. For computational efficiency, [1] also proposes a Thompson sampling (TS)-like algorithm that does not need such an oracle. In my opinion, it might be straightforward to show the Bayesian regret bound for this TS-like algorithm using the results in [1] and the standard and well-known results in [2]. In terms of proving Bayesian regret bound, could the authors elaborate more on the technical contributions beyond the existing literature?\n3. In terms of the transition dynamics, I think it would be beneficial to the readers if the authors could say more on the dynamics that covered by the paper but not covered by [1]. In my opinion, providing some (simple) examples could be helpful.\n4. Could the authors elaborate more on why the proposed algorithm decouples the exploration and representation learning since I think there is still longitudinal coupling across time-steps? Is this decoupling similar to that of Neural Linear algorithm in [3]?\n\n\n[1] Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, Wen Sun. Information Theoretic Regret Bounds for Online Nonlinear Control. NeurIPS 2020.\n[2] Daniel Russo and Benjamin Van Roy. Learning to Optimize via Posterior Sampling, Mathematics of Operations Research, 2014.\n[3] Carlos Riquelme, George Tucker, Jasper Snoek, Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling, ICLR 2018.", "summary_of_the_paper": "This paper studies representation learning in the context of reinforcement learning, and observes that under some noise assumption, the linear spectral feature of corresponding Markov transition operator can be obtained in closed-form. Then the paper proposes the so-called SPEDE algorithm that enjoys good theoretical guarantee and empirical results.", "summary_of_the_review": "I think this is an interesting paper, and I would like to understand better the technical novelty.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Nts9OFjkqDU", "reviewer": "Reviewer_azcj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strength. This paper extended the model in LC3[1] to kernel setting, and it also used Lemma 16 to remove the dependability on the global Lipschitz constant. It also conducted experiments to show that its algorithm is practical and efficient.\n\nWeakness. After going through the proof, I notice that the regret bound is proportion to $\\sigma^{-1}$, which means that the bound will be bigger when the noise level decrease and should be emphasized in Theorem 5. Here $\\sigma$ is the noise level.\n\nAlthough there are some details in Section 3.2, there should be more detail about the posterior sampling in the experiments section since this paper claimed to provide a practical algorithm and this part is not trivial. \n\n[1]. Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Information-theoretic regret bounds for online nonlinear control. arXiv preprint arXiv:2006.12466,\n2020.", "summary_of_the_paper": "This paper proposed a practical exploration algorithm for finite-horizon RL problems and provided a theoretical guarantee for its algorithm when the transition kernel of the RL problem can be encoded with RKHS. It also conducted experiments to validate its algorithm.", "summary_of_the_review": "This paper is significant, in the sense that it extends LC3[1] and provides a theoretical guarantee for a setting that is more complicated than [1]. It also uses a novel technique to utilize the noise in transition to remove the dependability on the global Lipschitz constant. Although the dependency on noise might have room for improvement, I think it is a good paper and could be accepted.", "strength_and_weaknesses": "", "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": "MU-_dm4znXA", "reviewer": "Reviewer_8eEv", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "# Clarity and writing #\n\nMy first major comment is about clarity and writing. This paper emphasizes that the algorithm is doing representation learning. However, I believe that model-based learning might be more suitable for this paper. One major difference between the current paper and the prior representation learning/reward-free learning work is that the algorithm in this paper can only handle a single reward while previous model-based or model-free works can learn a representation that tackles multitasks (multiple rewards). I think such differences should be discussed in the paper. Since the algorithm can only a handle single reward, I do not see the significance and advantage of learning the \"representation\" (model). It belongs to the model-based algorithm where the TS agent tries to learn a model to address the reward-aware RL problem.\n\nMoreover, some claims are not accurate. It is mentioned that “These algorithms learn a uniformly accurate model through a reward-free exploration, upon which decouple the learning from the exploration”, but Modi et al., 2021 is a model-free algorithm and does not try to learn a model. \n\nModi et al., 2021 first proposes to solve min-max-min optimization instead of min-max-min-max optimization as one operator has a closed-form solution. The min-max-min optimization is furthered solved in a more computationally efficient way by considering squared loss minimization and saddle-point problem.\n\nFor the theoretical part, the assumptions are not written clearly. For example, I believe equation (5) is a crucial assumption, but it is not discussed explicitly in Section 4.1. \n\nThe regret bound is about the Bayesian regret, and such guarantee is much weaker than the frequentist regret/worst case regret. The related discussion about the Bayesian regret and the definition of Bayesian regret E_{Pf} are missing.\n\nI feel the title \"a free lunch from the noise\" oversells the paper. Indeed, it is a restricted assumption and the theoretical guarantee is obtained under such strong assumption.\n\n# Technical analysis and algorithmic framework #\nMy second comment is about technical and algorithmic novelty. The algorithm is the standard model-based TS algorithm. Intuitively, given the model class, TS algorithm will identify the true model given a large amount of data. In addition, the authors make a strong assumption on the transition dynamics (eq 5) and the analysis is directly adapted from prior work (Russo & Van Roy (2013; 2014); Osband & Van Roy (2014)). I feel the technical contribution is rather limited.\n\n# Experiments #\nI think the most significant contribution of this paper is the experimental results. However, I'm not confident in evaluating the empirical results, and I feel there are a bunch of related model-based algorithms that achieve good empirical performance. \n\nIn the experimental part, it’s unclear how the algorithm is implemented. How do you choose the function class F and the prior distribution p(f)?", "summary_of_the_paper": "This paper studies the single reward episodic MDP problem with the model-based TS algorithm. Assuming the given model class satisfies realizability, regularization property, bounded Eluder dimension, low covering number, and the true dynamics is the stochastic control model under gaussian noise transition (eq 5), the authors show the polynomial Bayesian regret guarantee. In addition, experiments on OPENAI MuJoCo is conducted.", "summary_of_the_review": "I believe the clarity of the writing can be improved. It might not be a good idea to emphasize the algorithm is conducting representation learning and using the model-based learning might be more suitable.\n\nThe theoretical contribution is rather limited, and most significant contribution seems to be on the empirical side (I have to say I'm not familiar with the empirical work). The authors make a strong assumption on the true model. The algorithm and the analysis seems to be directly adapted from prior work, e.g., Russo & Van Roy (2013; 2014); Osband & Van Roy (2014). \n\nIt seems that there is a gap between the theoretical part and the experiment and it’s unclear how the experiment is conducted.", "strength_and_weaknesses": "", "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": "2R3-78Bilf", "reviewer": "Reviewer_e9su", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "**Strengths**\n\nI think overall this paper considers an interesting problem (learning representations) that is of interest to the community, given that a major part of the RL theory literature focuses on learning with a known linear representation or structured function class, and much less is known when it comes to learning the representation. \n\nIt is a plus that this paper contains empirical results too on real RL benchmarks, which I do appreciate as for a paper with a bulk part being theoretical contributions. The experimental results seem mostly convincing to me.\n\n**Weaknesses**\n\nOne of my main concerns about the theory part is that this theory may be a somewhat cute but very specific consequence of the Gaussian noise assumption. It is kind of hard to tell how generalizable this result is (or how significant it is as a representation learning result), as the Gaussian structure (density of the noise admits this very form) is critically used instead of just for some concentration purposes. Though, I should remark from a more practical perspective I’m not that worried about using it for real-world problems, where it is hard to justify most structural assumptions anyway. \n\nAlso, from the current paper’s presentations, I find it quite hard to situate the current contributions in the context of representation learning theory in RL, and compare with related work. As concrete examples,\n\n--- Section 3 (before 3.1) makes caveats of two prior techniques for representation learning: MLE, and policy cover technique. These techniques are discussed quite vaguely and not presented in math. Consequently I couldn’t find the key observation in 3.1 very motivated (since I do not see what the prior methods exactly are). \n\n--- The real problem setting considered in this paper appears only in equation (5) and is not emphasized as a problem setting. I suggest maybe Section 3 could begin with talking about this setting, then talk about the existing approaches (with some math that at least hints what those methods are and why the authors think they are not sufficient), and then come to Section 3.1. \n\n--- The authors discussed Theorem 5 in the context when $\\mathcal{F}$ is a linear class; in this case I believe the model is *not* equivalent to linear MDP, could the authors comment more on what the difference is? Also, how does the present result compare with Agarwal et al. (2020) and Modi et al. (2021)?\n\n--- Theorem 5 uses a Thompson sampling algorithm but the proof sketch mentions connection to a certain UCB algorithm. Are there reasons for not using UCB directly in Algorithm 1?\n\n--- Could the authors discuss a bit more in detail how the proof compares with the standard Eluder Dimension proof (e.g. of Wang et al.)? Currently the proof sketch does not say much where the bounded Eluder dimension is used, and how is the application different from the existing Eluder dimension proof. \n\n--- (This one is about experiments) When deployed into practice, the main difference between SPEDE and existing model-based algorithms is just that the parametrization (3) and (4) is used? (aside from SGLD as for approximate Bayesian inference + Gaussian policy parametrization, as the authors mentioned).\n\nWith the above questions in mind, I am left confused about the concrete novelty in the proof techniques or problem settings, and at most left with the impression that the result may be new but not sure how exactly it compares with prior work. \n\n**Other comments**\n\n--- The “practical issues in implementing the proposed SPEDE”: maybe this paragraph can form a standalone section after Section 4, since logically, the practical implementation tricks are not used in the theoretical results?\n\n--- “expected regret” I believe it is usually called the Bayes regret in the thompson sampling literature?\n\n--- Table 1, SPEDE-REG on MountainCar, the number should not be bolded?\n", "summary_of_the_paper": "This paper studies the problem of learning representations for RL. On the theory side, the paper considers the setting where the state-transition is a nonlinear function of the past state-action plus additive noise, and develops a no-regret algorithm. On the empirical side, the paper shows that an adaptation of this algorithm on real-world RL tasks could perform better than existing model-based algorithms.", "summary_of_the_review": "Overall, I think this paper makes interesting contributions on both the theoretical and empirical end of representation learning within RL. However, significant work needs to be done in order to clarify its problem setting, results, and position within related work. ", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

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

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

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

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

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

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

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