Year: 2021

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.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) dedicates to solve the sequential decision making problem, where an agent is interacting with an unknown environment to 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 a 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 a subclass in Markov decision processes (MDPs) (Puterman, 2014). A natural question raises:
How to design provably efficient and practical algorithm for representation learning in RL?
Here, by “provably efficient” we 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 implemented and deployed for the real-world applications. Therefore, we not only require the representation 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 representations;
ii) The learning of representation is intimately coupled with exploration. Specifically, a desired representation should be sufficiently expressive1 to capture the dynamic system, while still tractable in practice. However, in general, expressive representation leads to complicated optimization in learning. For example, the representation in the linear MDP is exponential
1For a formal definition of expressiveness, see (Agarwal et al., 2020a).
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 a regression, but with the payoff that the representations 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 a precise representation without enough experiences from a comprehensive exploration, while the exploration depends on an reliable estimation of the representation. Most of the known results depends on a policy-cover-based exploration (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 models, 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 policycover-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, our 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 stateof-the-art RL algorithms. To our knowledge, SPEDE is the first representation learning algorithm achieving statistical, computational, and memory efficiency with sufficient expressiveness.

heading: 1.1 RELATED WORK
text: There have been many great attempts to learn a 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 are 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-justified representation learning, a large body of effort focuses on policy-cover-based methods in an “explore-then-commit” strategy (Du et al., 2019; Misra et al., 2020; Agarwal et al., 2020a; Modi et al., 2021). These algorithms learn a uniformly accurate model/representation 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-
tion and memory cost: the policy-cover-based exploration requires a 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 et 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 equivalent linear MDP.

heading: 2 PRELIMINARIES
text: 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, T, µ,H), where S is the state space, A is the action space, r : S × A → R+ is the reward function2 (where R+ denotes the set of nonnegative real numbers), T : S × A → ∆(S) is the transition and µ is an initial state distribution and H is the horizon3 (i.e. the length of each episode). A (potentially non-stationary) policy π can be defined as {πh}h∈[H] where πh : S → A,∀h ∈ [H]. Following the standard notation, we define the value function V πh (sh) := ET,π [∑H−1 t=h r(st, at)|sh = s ] and the action-value function
(i.e. the Q function) Qπh(sh, ah) = ET,π [∑H−1 t=h r(st, at)|sh = s, ah = a ] , which are the expected
cumulative rewards under transition T when executing policy π starting from sh and (sh, ah). With these two definitions at hand, it is straightforward to show the following Bellman equation: Qπh(sh, ah) = r(sh, ah) + Esh+1∼T (·|sh,ah)V πh+1(sh+1). Reinforcement learning aims at finding the optimal policy π∗ = arg maxπ Es∼µV π0 (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-efficient optimism-based methods (e.g. Azar et al., 2017; Jin et al., 2018; Zhang et al., 2021) with the complexity proportion to |S||A|. 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 et al., 2021) is the most well-known reinforcement learning model that can incorporate linear function approximation with theoretical guarantee, thanks to the following assumption on the transition: T (s′|s, a) = 〈φ(s, a), µ(s′)〉H, (1) where φ : S × A → H, µ : S → H are two feature maps and H is a Hilbert space. The most essential observation for them is that, Qπh(s, a) for any policy π is linear w.r.t φ(sh, ah), due to the following observation (Jin et al., 2020):∫
V πh+1(sh+1)T (sh+1|sh, ah) dsh+1 = 〈 φ(sh, ah), ∫ V πh+1(sh+1)µ(sh+1) dsh+1 〉 H . (2)
Therefore, φ serves as a sufficient representation for the estimation of Qπh, that can provide uncertainty estimation with standard linear model analysis and eventually lead to 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 in advance4 and we need to learn the representation from the data, which constraints the applicability of the algorithms derived with fixed and known representation.

heading: 3 SPECTRAL DYNAMICS EMBEDDING
text: 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-
2In general, the reward can be stochastic. Here for simplicity we assume the reward is deterministic and known throughout the paper, which is a common assumption in the literature (e.g., Jin et al., 2018; 2020; Kakade et al., 2020).
3Our method can be generalized to infinite horizon case, see Section 3.2 for the detail. 4One exception is the tabular MDP, where we can choose φ : S ×A → R|S|
2|A| that each state-action pair has exclusive |S| non-zero element and µ : S → R|S| 2|A| correspondingly defined to make (1) hold.
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), ∫ s′ µ(s′) ds′〉 = 1) for all (s, a) ∈ S × A. Moreover, even we 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 et 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 a simple but provable efficient and practical algorithm for representation 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.

heading: 3.1 KEY OBSERVATION
text: Our most important observation is that, the density of isotropic Gaussian distribution can be expressed as the inner product of two feature maps, thanks to the reproducing property and the random Fourier transform of the Gaussian kernel5 (Rahimi & Recht, 2007):
φ(x|µ, σ2I) ∝ exp ( −‖x− µ‖ 2
2σ2 ) (Reproducing Property) =〈k(x, ·), k(µ, ·)〉H (3)
(Random Fourier Transform) = 〈ϕ(x, ω, b), ϕ(µ, ω, b)〉p(ω,b) , (4)
where k(·, ·) is the Gaussian kernel with bandwidth σ: k(x, y) = exp ( −‖x−y‖ 2 2
2σ2
) , H is the
Reproducing Kernel Hilbert Space (RKHS) associated with k, ϕ(x, ω, b) = √
2 cos(ω>x + b), 〈f, g〉p = Ep(x)[f(x)g(x)] and p(ω, b) = N (ω; 0, 1/σ2I) · U(b; [0, 2π]) with N and U denoting Gaussian and Uniform distribution, respectively.
Consider the general transition dynamics, s′ = f∗(s, a) + , ∼ N (0, σ2), equivalently T (s′|s, a) ∝ exp ( −‖s
′−f∗(s,a)‖2 2σ2
) , (5)
which is the basic setup in the empirical model-based reinforcement learning (e.g., Chua et al., 2018; Kurutach et al., 2018; Clavera et al., 2018; Wang et al., 2019), and the online (non)-linear control (e.g., Abbasi-Yadkori & Szepesvári, 2011; Mania et al., 2019; 2020; Simchowitz & Foster, 2020; Kakade et al., 2020). Here s ∈ Rd, a ∈ A that can be continuous and f∗ is a dynamic function. By applying the reproducing property (3) or random Fourier transform (4) for the transition dynamics (5), we can obtain the feature φ and µ satisfies (1) for free. Specifically, taking the reproducing property as an example, we have that T (s′|s, a) = 〈k(f∗(s, a), ·), (2πσ2)−d/2k(s′, ·))〉H, (6) which means the problem (5) is indeed a linear MDP with φ(s, a) = k(f∗(s, a), ·) and µ(s′) = (2πσ2)−d/2k(s′, ·). Following (2), we know Q(s, a) is in the linear span of the φ(s, a) that is transformed from f∗(s, a). Therefore, finding a good representation of (s, a) is equivalent to finding a good estimation of f∗. 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 a both sampleefficient and computational-efficient algorithm. Remark (Computation-free Factorizable Noise Model): We want to remark that, similar observations also hold for large amounts of distribution, e.g., the Laplace and Cauchy distribution. We refer the interested reader to Table 1 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.

heading: 3.2 PRACTICAL ALGORITHM DESCRIPTION
text: Here, we introduce a generic Thompson Sampling (TS) type algorithm in Algorithm 1 based on the OFU principle that leverage our observation at the previous section. At the beginning, we provide a
5We provide a brief review on the related definitions in Appendix A.
Algorithm 1 Thompson Sampling (TS) Algorithm Require: Number of Episodes K, Prior Distribution P(f), Reward Function r(s, a).
1: Initialize the history setH0 = ∅. 2: for episodes k = 1, 2, · · · do 3: Sample fk ∼ P(f |Hk). . Draw the Representation. 4: Find the optimal policy πk on fk with Algorithm 2. . Planning with fk. 5: for steps h = 0, 1, · · · , H − 1 do . Executing πk. 6: Execute akh ∼ πhk (skh). 7: Observe sh+1. 8: end for 9: SetHk = Hk−1 ∪ {(skh, akh, skh+1)} H−1 h=0 . . Update the History.
10: end for Algorithm 2 Planning with Dynamic Programming Require: Transition Model f , Reward Function r(s, a).
1: Initialize φ(s, a), µ(s′) with (3) or (4). VH(s) = 0,∀s. 2: for steps h = H − 1, H − 2, · · · , 0 do 3: Calculate Qh(s, a) = r(s, a) + 〈φ(s, a), ∫ Vh+1(s
′)µ(s′) ds′〉H. . Bellman Update. 4: Set Vh(s) = maxaQh(s, a), πh(s) = arg maxaQh(s, a). . Choose the Optimal Policy. 5: end for 6: return {πh}H−1h=0 .
prior distribution P(f) that reflects our prior knowledge on f∗. Then for each episode, we draw a f from the posterior, find the optimal policy with f 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 representation 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 a 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-efficient 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 is known on how to provably perform such planning efficiently. Notce that, with the feature φ(s, a) defined via (3) and (4), we know that Qπh(s, a) is exactly linear in φ(s, a), ∀h, π. Hence, we can perform a dynamic programming style algorithm that calculate Qh(s, a) with the given feature φ(s, a), and then greedily select the action at each level h, which is simple yet efficient. It 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 ∫ Vh+1(s
′)µ(s′) ds′ and take the maximum of Qh(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 lie in simple function class (e.g., linear function class) or has some derived property (e.g., conjugacy), so in practice we 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 et 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.
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 ∫ Vh+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 optimization methods (e.g., Agarwal et al., 2020b) with an 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 (Haarnoja et al., 2018) policy update, which already provides good empirical perfor-
mance. To sum up, for large state and action cases, we 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 φ(s, a) using the popular algorithms like Fitted Q-iteration (FQI) (Ernst et al., 2005; Antos et al., 2008). that still guarantees to find the optimal policy.

heading: 4 THEORETICAL GUARANTEES
text: In this section, we provide theoretical results for SPEDE, showing that SPEDE can identify informative 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 πk and observes a sequence {(skh, akh)} H−1 h=0 . We define the regret of the first K episodes (and define T := KH) as:
Regret(K) := ∑ k∈[K] [ V ∗0 (s k 0)− V πk 0 (s k 0) ]
(7) We want to provide a regret upper bound that is sublinear in T , as 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(f) [Regret(K)], which takes the prior P(f) into account.

heading: 4.1 ASSUMPTIONS
text: 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 is common in the literature (e.g. Azar et al., 2017; Jin et al., 2018; 2020). Assumption 1 (Bounded Reward). r(s, a) ∈ [0, 1], ∀(s, a) ∈ S ×A. Assumptions on the function class F In practice, we generally approximate f∗ with some complicated function approximators, so we focus on the setting where we want to find f∗ from a general function class F that need not to be linear with certain feature map. This can be helpful for MuJoCo 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 f linear. We first state some necessary definitions and assumptions on F . Definition 1 (`2-norm of functions). Define ‖f‖2 := max(s,a)∈S×A ‖f(s, a)‖2. Notice that it is not the commonly used `2 norm for the function, but it suits our purpose well. Assumption 2 (Bounded Output). We assume that ‖f‖2 ≤ C, ∀f ∈ F . Assumption 3 (Realizability). We assume the ground truth dynamic function f∗ ∈ F . We then define the notion of covering number, which will be helpful in our algorithm derivation. Definition 2 (Covering Number (Wainwright, 2019)). An -cover of F with respect to a metric ρ is a set {fi}i∈[n] ⊆ F , such that ∀f ∈ F , there exists i ∈ [n], ρ(f, fi) ≤ . The -covering number is the cardinality of the smallest -cover, denoted as N (F , , ρ). Assumption 4 (Bounded Covering Number). We assume that N (F , , ‖ · ‖2) <∞,∀ > 0. Remark Basically, Assumption 2 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 4 ensures that we can estimate f∗ with small error when we have sufficient number of observations.
Besides the bounded covering number, we also need an additional assumption on bounded eluder dimension, which is defined in the following: Definition 3 ( -dependency (Osband & Van Roy, 2014)). A state-action pair (s, a) ∈ S × A is -dependent on {(si, ai)}i∈[n] ⊆ S × A with respect to F , if ∀f, f̃ ∈ F satisfying√∑ i∈[n] ‖f(si, ai)− f̃(si, ai)‖22 ≤ satisfies that ‖f(s, a)− f̃(s, a)‖2 ≤ . Furthermore, (s, a) is said to be -independent of {(si, ai)}i∈[n] with respect toF if it is not -dependent on {(si, ai)}i∈[n]. Definition 4 (Eluder Dimension (Osband & Van Roy, 2014)). We define the eluder dimension dimE(F , ) as the length d of the longest sequence of elements in S × A, such that ∃ ′ ≥ , every element is ′-independent of its predecessors.
Remark Intuitively, eluder dimension illustrates the number of samples we need to make our prediction on unseen data accurate. If the eluder dimension is unbounded, then we cannot make any meaningful prediction on unseen data, even we have large amounts of samples. Hence, to make the learning possible, we need the following bounded eluder dimension assumption.
Assumption 5 (Bounded Eluder Dimension). We assume dimE(F , ) <∞,∀ > 0.

heading: 4.2 MAIN RESULT
text: Theorem 5 (Regret Bound). Assume Assumption 2 to 5 holds. We have that EP(f) [Regret(K)] ≤ Õ( √ H2T · logN (F , T−1/2, ‖ · ‖2) · dimE(F , T−1/2)).
where Õ represents the order up to logarithm factors.
For finite dimensional function class, logN (F , T−1/2, ‖ · ‖2) and dimE(F, T−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 EP(f) [Regret(K)] of TS algorithm.
With the optimism, we know for episode k, V ∗0 (s k 0) ≤ Ṽ πk 0,k(s k 0), where Ṽ πk h,k is the value function of
policy πk under the model f̃k introduced in the UCB algorithm. Hence, the regret at episode k can be bounded by Ṽ πk0,k(s k 0) − V πk 0 (s k 0), which is the value difference of the policy πk under the two
models f̃k and f∗, that can be bounded by √ E [∑H−1 h=0 ‖f∗(skh, akh)− f̃k(skh, akh)‖22 ] (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 f̂ will only suffer from a small regret. With Cauchy-Schwartz inequality, we only need to bound E [∑ k∈[K] ∑H−1 h=0 ‖f∗(skh, akh)− f̃k(skh, akh)‖22 ] . 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(f) [Regret(K)] for the TS algorithm.
Kernelized Non-linear Regulator Notice that, for the linear function class F = {θ>ϕ(s, a) : θ ∈ Rdϕ×d} where ϕ : S × A → Rdϕ is a fixed and known feature map of certain RKHS6, when the feature and the parameters are bounded, the logarithm covering number can be bounded by logN (F , , ‖ · ‖2) . dϕ log(1/ ), and the eluder dimension can be bounded by dimE(F , ) . dϕ log(1/ ) (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 a regret upper bound of Õ(HdϕT 1/2) for sufficient large T , that matches the results of Kakade et al. (2020)7. Moreover, for the case of linear bandits when H = 1, our bound can be translated into a regret upper bound of Õ(dϕT 1/2), 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 F 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.
6Note that, the RKHS here is the Hilbert space that contains f(s, a) with the feature from some fixed and known kernel, It is different from the RKHS we introduced in Section 3, that contains Q(s, a) with the feature k(f(s, a), ·) where k is the Gaussian kernel.
7Note that T in (Kakade et al., 2020) is the number of episodes, and Vmax in (Kakade et al., 2020) can be viewed as H2 when the per-step reward is bounded.

heading: 5 EXPERIMENTS
text: 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 gradient 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 φ(·) and a linear layer on the top. We follow the same procedure of Algorithm 1: (1) For finding the optimal policy, we run an actor-critic algorithm (SAC). (2) We update the representation network of the critic function φ(·) with a momentum from the model dynamics 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. 8
Baselines We compare our method with various model-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 handtuned hyperparameters and engineering features (e.g., ensemble of models). It is usually hard for any theoretically guaranteed model-based RL algorithm to match or surpass their performance (Kakade et 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 are interested 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 rigorously-justified representation learning algorithms are computationally intractable/inefficient, 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 transition 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 performance 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 evaluate whether our assumption on linear MDP is valid in empirical settings and study whether such assumption 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-REG 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-REG outperforms 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
8Our code is available at https://sites.google.com/view/spede.
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 comparison, 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. Performance Curves To better understand how the sample complexity of our algorithm comparing to the prior model-based RL baselines, we plot the return versus environment steps in Figure 1. 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 already show significantly better sample efficiency compared to model-free methods (e.g.PPO/TRPO). We provide additional results in Appendix E.2.

heading: 6 CONCLUSION
text: In this paper, we 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.
Ethnics Statement Our paper focus on one of the core questions in RL, i.e., developing provable and practical algorithms for representation learning in online scenarios under general settings. Although there can 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 social impact of RL. As we conduct our experiments on standard MuJoCo benchmark, our experiments should not suffer from any discrimination/bias/fairness concerns.
Reproducibility Statement Our code is 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 be easily reproduced, and our code is available at https://sites.google.com/view/spede.

heading: A BACKGROUNDS ON REPRODUCING KERNEL HILBERT SPACE
text: We briefly introduce the basic concepts of the Reproducing Kernel Hilbert Space, which is helpful on understanding our paper. To start with, we first define the inner product (Stein & Shakarchi, 2009). Definition 6 (Inner Product). A function 〈·, ·〉H : H×H → R is said to be an inner product on H if it satisfies the following conditions:
1. Positive Definiteness: ∀u ∈ H, 〈u, u〉 ≥ 0, and 〈u, u〉 = 0⇐⇒ u = 0.
2. Symmetry: ∀u, v ∈ H, 〈u, v〉 ∈ 〈v, u〉.
3. Bilinearity: ∀α, β ∈ R, u, v, w ∈ H, 〈αu+ βv,w〉 = α〈u,w〉+ β〈v, w〉.
Additionally, we can define a norm with the inner product: ‖u‖ = √ 〈u, u〉.
A Hilbert space is a space equipped with an inner product and satisfies an additional technical condition of completeness. The finite-dimension vector space with the canonical inner product is an example of the Hilbert space. We remark thatH can also be a function space, for example, the space contains all square integrable functions (i.e. ∫ R f(x)
2 dx < ∞, generally denoted as L2) is also a Hilbert space with inner product 〈f, g〉 = ∫ R f(x)g(x) dx.
We then define the kernel, and introduce the notion of positive-definite kernel (Álvarez et al., 2012). Definition 7 ((Positive-Definite) Kernel). A function k : X → X → R is said to be a kernel on nonempty set X if there exists a Hilbert space H and a feature map φ : X → H such that ∀x, x′ ∈ X , we have k(x, x′) = 〈φ(x), φ(x′)〉H. Moreover, the kernel is said to be positive definite if ∀n ≥ 1, ∀{ai}i∈[n] ⊂ R and mutually distinct set {xi}i∈[n] ⊂ X , we have that ∑
i∈[n] ∑ j∈[n] aiajk(xi, xj) > 0.
Some well-known kernels include:
• Linear Kernel: k(x, y) = 〈x, y〉, with the canonical feature map φ(x) = x. • Polynomial Kernel: k(x, y) = (〈x, y〉+ c)m, where m ∈ N+ and c ∈ R+.
• Gaussian (a.k.a radial basis function, RBF) Kernel: k(x, y) = exp ( ‖x−y‖22
2σ2
) . It’s known
that such kernel is positive definite.
Now we can define the Reproducing Kernel Hilbert space (RKHS) (Aronszajn, 1950). Definition 8 (Reproducing Kernel Hilbert Space (RKHS)). The Hilbert space H of R-valued function defined on a non-emptry set X is said to be a reproducing kernel Hilbert space (RKHS) is there is a kernel k : X × X → R, such that
1. ∀x ∈ X , k(x, ·) ∈ H.
2. ∀x ∈ X , f ∈ H, 〈f, k(x, ·)〉H = f(x) (a.k.a the reproducing property), which also implies that 〈k(x, ·), k(y, ·)〉 = k(x, y).
Here k is called a reproducing kernel ofH.
We provide an intuitive interpretation on the definition of RKHS when H is the space of linear function. Consider X = Rd and k(x, y) = 〈x, y〉. With the definition of the kernel k, we can see that k(x, ·) : X → R is a linear function, and thus lies in H. Meanwhile, ∀f ∈ H, there exists θf such that f(x) = θ>f x. We define the inner product on H via 〈f, g〉H = 〈θf , θg〉, and thus 〈f(, k(x, ·))〉H = θ>x = 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.
We state the following theorems without the proof. Theorem 9 (Moore-Aronszajn (Aronszajn, 1950)). Every positive definite kernel k is associated with a unique RKHSH.
Notice that, Moore-Aronszajn 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, as we illustrated in the main text. Theorem 10 (Bochner (Rudin, 2017)). A continuous, shift-invariant kernel (i.e. k(x, y) = k(x−y)) is positive definite if and only if k(x− y) is the Fourier transform of a non-negative measure ω, i.e.
k(x− y) = ∫ Rd exp(iω>(x− y)) dP(ω) = ∫ Rd×[0,2π] 2 cos(ω>x+ b) cos(ω>y + b) d(P(ω)× P(b)), where P(b) is a uniform distribution on [0, 2π].
Bochner’s theorem shows that any continuous positive definite shift-invariant kernel (e.g. Gaussian kernel, Laplacian kernel) can be represented as the inner product of random Fourier feature, which provides an additional way to provide a representation for certain distribution (see Rahimi & Recht, 2007; Dai et al., 2014).

heading: B AN EQUIVALENT UPPER CONFIDENCE BOUND ALGORITHM
text: In this section, we provide a generic Upper Confidence Bound (UCB) algorithm with the OFU principle, 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 3 Upper Confidence Bound (UCB) Algorithm Require: Number of Episodes K, Failure Probability δ ∈ (0, 1), Reward Function r(s, a).
1: Initialize the history setH0 = ∅. 2: for episodes k = 1, 2, · · · do 3: Compute πk via . Optimistic Planning.
(πk, f̃k) = arg max π∈Π,f̃∈Fk
Ṽ π0 (s0).
where Fk is defined in (9). 4: for steps h = 0, 1, · · · , H − 1 do . Execute πk. 5: Execute akh ∼ πhk (skh). 6: Observe sh+1. 7: end for 8: SetHk = Hk−1 ∪ {(skh, akh, skh+1)} H−1 h=0 . . Update the History. 9: end for
Notice that, the only difference between UCB algorithm and TS algorithm is the mechanism of finding f we use to plan for each episode (highlighted in blue). For UCB algorithm, we perform an optimistic planning, which finds the f̃k 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 fk 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 construction of confidence set Fk. To enable sample-efficient 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, Fk is constructed via the concentration of sub-Gaussian/sub-Gamma random variable (e.g. Azar et al., 2017; Jin et al., 2018; Zhang et al., 2021), and in the linear MDP setting, Fk is constructed via the concentration on the linear parameters. As we don’t assume any
specific structures, we instead constructed Fk via the concentration on the `2 error, following the idea of (Russo & Van Roy, 2013; Osband & Van Roy, 2014). Specifically, consider the least-square estimates defined by
f̂K = arg min f∈F L2,K(f) := ∑ k∈[K] H−1∑ h=0 ‖f(skh, akh)− skh+1‖22. (8)
As skh+1 = f ∗(skh, a k h) + k h where k h is the Gaussian noise added to the step h at the k-th episode, we know f̂K will not deviate from f∗ a lot. Meanwhile, as K increases, the estimation f̂K should become closer to f∗. Specifically, define the empirical 2-norm ‖ · ‖2,Et as
‖g‖22,EK := ∑ k∈[K] H−1∑ h=0 ‖g(skh, akh)‖22.
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 = { f ∈ F : ‖f − f̂K‖2,EK ≤ √ β∗K(F , δ, α) } , (9)
then
Pf∗ ( f∗ ∈
∞⋂ k=1 Fk
) ≥ 1− 2δ, (10)
where β∗K(F , δ, α) = 8σ2 log(N (F , α, ‖ · ‖2)/δ) + 2Hα(12C + √ 8dσ2 log(4K2H/δ)). (11)
The proof can be found in Appendix C.1. Notice that, the empirical 2-norm ‖f − f̂K‖2,EK scales linearly with K, and β∗K(F , δ, α) only scales as logK, so the confidence set shrinks. Meanwhile, Equation 10 guarantees that f∗ ∈ Fk, ∀k 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 2 to 5 holds. We have that
Regret(K) ≤ Õ( √ H2T · logN (F , T−1/2, ‖ · ‖2) · dimE(F , T−1/2)).
where Õ represents the order up to logarithm factors.

heading: C TECHNICAL PROOF

heading: C.1 PROOF FOR LEMMA 11
text: Proof. We first show the following concentration on the `2 error:
Lemma 13 (Concentration of `2 error (Russo & Van Roy, 2013; Osband & Van Roy, 2014; Wang et al., 2020)). ∀δ > 0, f : S ×A → R, we have Pf∗ ( L2,K(f) ≥ L2,K(f∗) + 1
2 ‖f − f∗‖22,EK − 4σ
2 log(1/δ), ∀K ∈ N ) ≥ 1− δ
Proof. Define the filtrationHk,h = {(sih, aih)}i∈[k−1],h=0,··· ,H−1 ∪ {(ski , aki )} h−1 h=0, and the random variable Zk,h adapted to the filtrationHk,h via: Zk,h =‖f∗(skh, akh)− skh+1‖22 − ‖f(skh, akh)− skh+1‖22
=‖f∗(skh, akh)− skh+1‖22 − ‖f(skh, akh)− f∗(skh, akh) + f∗(skh, akh)− skh+1‖22 =− ‖f(skh, akh)− f∗(skh, akh)‖22 + 2〈f(skh, akh)− f∗(skh, akh), kh〉,
where kh = s k h+1 − f∗(skh, akh). Thus, E(Zhk |Hk,h) = −‖f(skh, akh) − f∗(skh, akh)‖22, and Zhk + ‖f(skh, akh) − f∗(skh, akh)‖22 is a martingale w.r.t Hk,h. Notice that we assume is an isotropic Gaussian noise with variance σ2 on each of the dimension, thus the conditional moment generating function of Zhk + ‖f(skh, akh)− f∗(skh, akh)‖22 satisfies:
Mk,h(λ) = logE[exp(λ(Zhk + ‖f(skh, akh)− f∗(skh, akh)‖22))|Hk,h]
= logE[exp(〈2λf(skh, akh)− f∗(skh, akh), kh〉)|Hk,h] ≤2σ2λ2‖f(skh)− f∗(skh, akh)‖22.
Applying Lemma 4 in (Russo & Van Roy, 2013), we have that, ∀x, λ ≥ 0,
Pf∗  ∑ k∈[K] H−1∑ h=0 λZk,h ≤ x− λ(1− 2λσ2) ∑ k∈[K] H−1∑ h=0 ‖f(skh, akh)− f∗(skh, akh)‖22, ∀k ∈ N  ≤ 1− exp(−x). Take λ = 14σ2 , x = log 1/δ, and notice that ∑ k∈[K] ∑H−1 h=0 Zk,h = L2,K(f
∗)− L2,K(f), we have the desired result.
We construct an α-cover Fα in F with respect to ‖ · ‖2. With a standard union bound, we know that condition on f∗, with probability at least 1− δ, we have that
L2,K(f α)− L2,K(f∗) ≥
1 2 ‖fα − f∗‖22,EK − 4σ
2 log(|Fα|/δ), ∀K ∈ N, fα ∈ Fα. Thus, we have that L2,K(f)− L2,K(f∗) ≥ 1
2 ‖f − f∗‖22,EK − 4σ 2 log(|Fα|/δ)
+ min fα∈Fα
{ 1
2 ‖fα − f∗‖22,EK −
1 2 ‖f − f∗‖22,EK + L2,K(f)− L2,K(f α) } ︸ ︷︷ ︸
Discretization Error
.
We then deal with the discretization error. Assume α ≤ 2C (or otherwise we only have a trivial cover) and ‖fα(s, a)− f(s, a)‖2 ≤ α, we have that
‖fα(s, a)− f∗(s, a)‖22 − ‖f(s, a)− f∗(s, a)‖22 =‖fα(s, a)‖22 − ‖f(s, a)‖22 + 2〈f∗(s, a), f(s, a)− fα(s, a)〉 ≤ max ‖y‖2≤α {‖f(s, a) + y‖22 − ‖f(s, a)‖22}+ 2Cα
= max ‖y‖2≤α
{2〈f(s, a), y〉+ ‖y‖22}+ 2Cα
≤4Cα+ α2 ≤ 6Cα, where the inequality is by Cauchy-Schwartz inequality and α ≤ 2C. Meanwhile,
‖s′ − f(s, a)‖22 − ‖s′ − fα(s, a)‖22 =2〈s′, fα(s, a)− f(s, a)〉+ ‖f(s, a)‖22 − ‖fα(s, a)‖22 ≤2〈 , fα(s, a)− f(s, a)〉+ 2〈f∗(s, a), fα(s, a)− f(s, a)〉+ 2Cα+ α2
≤2‖ ‖2α+ 6Cα. We now consider the concentration property of ‖ ‖2. Here we simply follow (Jin et al., 2019) and notice that is √ dσ-norm-sub-Gaussian, we have that
P(‖ ‖2 > √
2dσ2 log(2/δ)) ≤ δ. By a union bound, we have that
P(∃k, ‖ ‖2 > √
2dσ2 log(4k2H/δ)) ≤ δ 2 ∞∑ k=1 H−1∑ h=0 1 k2H ≤ δ.
Sum all these up, we can see with probability 1 − δ, ∀K ∈ N, the discretization error is upper bounded by: Hα(12C + √ 8dσ2 log(4K2H/δ)). As we consider the least square estimate f̂K , we have that L2,K(f̂K) − L2,K(f∗) ≤ 0. Substitute back, we have the desired results.

heading: C.2 SIMULATION LEMMA
text: Lemma 14 (Simulation Lemma (adapted from Lemma 3.9 in (Kakade et al., 2020))). Given f̂ , ∀s ∈ S, the value function V̂ π and V π corresponding to the model f̂ and f∗ satisfies
V̂ π0 (s)− V π0 (s) ≤ H3/2 √√√√E[H−1∑
h=0
min
{ 2‖f∗(sh, ah)− f̂(sh, ah)‖22
σ2 , 1
}] .
Proof. We first show the following difference lemma:
Lemma 15 (Difference Lemma). Assume the trajectory {(sh, ah)}H−1h=0 is generated via policy π and ground truth f∗, define
Vh = H−1∑ τ=h r(sτ , aτ )
then ∀τ ∈ {1, · · · , H − 1}, we have: V̂ π0 (s0)− V0 =Es′τ∼N (f̂(sτ−1,aτ−1),σ2I) [ V̂ πτ (s ′ τ ) ] − Vτ
+ τ−1∑ h=1 [ Es′h∼N (f(sh−1,ah−1),σ2I) [ V̂ πh (s ′ h) ] − V̂ πh (sh) ] .
Proof. When τ = 1, we can obtain the result with a0 = π(s0) and V̂ π0 (s0) = r(s0, π(s0)) + Es′1∼N (f(s0,a0),σ2I)V̂ π 1 (s ′ 1). We only need to show the case when τ = 2, and the case when τ > 2 can be derived via recursion. Notice that V̂ π0 (s0)− V0 =Es′1∼N (f(s0,a0),σ2I) [ V̂ π1 (s ′ 1) ] − V1
=V̂ π1 (s1)− V1 + Es′1∼N (f(s0,a0),σ2I) [ V̂ π1 (s ′ 1) ] − V̂ π1 (s1)
=Es′2∼N (f(s1,a1),σ2I) [ V̂ π2 (s ′ 2) ] − V2 + Es′1∼N (f(s0,a0),σ2I) [ V̂ π1 (s ′ 1) ] − V̂ π1 (s1),
where the last equality is due to the fact that a1 = π(s1).
We then follow the idea of “optional stopping” used in (Kakade et al., 2020) and show the following “optional stopping” simulation lemma.
Lemma 16 (“Optional Stopping” Simulation Lemma). Consider the stochastic process over the trajectories {(sh, ah)}H−1h=0 generated via policy π and ground truth f∗, where the randomness is from the Gaussian noise in the dynamics. Define a stopping time τ w.r.t this stochastic process and a given model f̂ via: τ := min{h ≥ 0 : V̂ πh (sh) ≤ V πh (sh)}. Furthermore, define a random variable: Ṽ πh (sh) = max{V̂ πh (sh), V πh (sh)}, we have that
V̂ π0 (s0)− V π0 (s0) ≤ E [ H−1∑ h=0 1h<τ ( Es′h+1∼N (f∗(sh,ah),σ2I)Ṽ π h (s ′ h+1)− Es′h+1∼N (f̂(sh,ah),σ2I)Ṽ π h (s ′ h+1) )] , where the expectation is w.r.t the stochastic process over the trajectories.
Proof. Define the filtration Fh := { i}h−1i=0 , where i is the noise that add to the dynamics at step i. Define Mh = E[V̂ π0 (s0)− V0|Fh], which is a Doob martingale with respect to Fi (Grimmett & Stirzaker, 2020). As τ ≤ H , by Doob’s optional stopping theorem, we have that E[V̂ π0 (s0)− V0] = E[Mτ ] = E[E[V̂ π0 (s0)− V0|Fτ ]]. We then provide a bound for Mτ . By Lemma 15, we have that
Mτ =E[V̂ π0 (s0)− V0|Fτ ] =Es′τ∼N (f̂(sτ−1,aτ−1),σ2I) [ V̂ πτ (s ′ τ ) ] − V πτ (sτ )
+ Es′h∼N (f̂(sh−1,ah−1),σ2I) [ V̂ πh (s ′ h) ] − τ−1∑ h=1 V̂ πh (sh)
= τ∑ h=1 ( Es′h∼N (f̂(sh,ah),σ2) [ V̂ πh (s ′ h) ] − Ṽ πh (sh) )
≤ τ∑ h=1 ( Es′h∼N (f̂(sh,ah),σ2I) [ Ṽ πh (sh) ] − Ṽ πh (sh) ) =
H∑ h=1 1h≤τ ( Es′h∼N (f̂(sh,ah),σ2I) [ Ṽ πh (sh) ] − Ṽ πh (sh) ) ,
where the third inequality follows the definition of τ (and thus V πτ (sτ ) = Ṽ π τ (sτ ) and V̂ π h (sh) = Ṽ πh (sh) for h < τ .) The proof is then concluded via the following observation: E [ 1h≤τ ( Es′h∼N (f̂(sh,ah),σ2I) [ Ṽ πh (sh) ] − Ṽ πh (sh)
)] =E [ E [ 1h≤τ ( Es′h∼N (f̂(sh,ah),σ2I) [ Ṽ πh (sh) ] − Ṽ πh (sh)
) ∣∣∣∣Fh−1]] =E [ E [ 1h−1<τ ( Es′h∼N (f̂(sh,ah),σ2I) [ Ṽ πh (sh) ] − Ṽ πh (sh)
) ∣∣∣∣Fh−1]] =E [ 1h−1<τE [( Es′h∼N (f̂(sh,ah),σ2I) [ Ṽ πh (sh) ] − Ṽ πh (sh)
) ∣∣∣∣Fh−1]] =E [ 1h−1<τ ( Es′h∼N (f̂(sh,ah),σ2) [ Ṽ πh (sh) ] − Es′h∼N (f∗(sh,ah),σ2) [ Ṽ πh (sh) )]] ,
where the third equality is due to the fact that 1h−1<τ is measurable under Fh−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). ∀ (approximately measurable) positive function g, we have that
Ez∼N (µ1,σ2I)[g(z)]− Ez∼N (µ2,σ2I)[g(z)] ≤ min
{√ 2‖µ1 − µ2‖
σ , 1
}√ Ez∼N (µ1,σ2I)[g(z)2]

heading: Proof.
text: Ez∼N (µ1,σ2I)[g(z)]− Ez∼N (µ2,σ2I)[g(z)]
=Ez∼N (µ1,σ2I) [ g(z) ( 1− exp ( 2(µ1 − µ2)>z + ‖µ2‖2 − ‖µ1‖2
2σ2
))]
≤ √
Ez∼N (µ1,σ2I)[g(z)2] √ Ez∼N (µ1,σ2I) ( 1− exp ( 2(µ2 − µ1)>z − ‖µ2‖2 + ‖µ1‖2
2σ2 ))2 We then calculate
Ez∼N (µ1,σ2I) ( 1− exp ( 2(µ2 − µ1)>z − ‖µ2‖2 + ‖µ1‖2
2σ2 ))2 =1− 2√
2πσd/2
∫ exp ( −‖z − µ1‖22 + 2(µ2 − µ1)>z − ‖µ2‖2 + ‖µ1‖2
2σ2
) dz
+ 1√
2πσd/2
∫ exp ( −‖z − µ1‖22 + 4(µ2 − µ1)>z − 2‖µ2‖2 + 2‖µ1‖2
2σ2
) dz
=− 1 + 1√ 2πσd/2
∫ exp ( −‖z − (2µ2 − µ1)‖22 + 2‖µ2 − µ1‖22
2σ2
) dz
=− 1 + exp ( ‖µ2 − µ1‖22
σ2
) .
Also notice that, as g is positive, a simple bound is that Ez∼N (µ1,σ2I)[g(z)]− Ez∼N (µ2,σ2I)[g(z)] ≤ Ez∼N (µ1,σ2I)[g(z)] ≤ √
Ez∼N (µ1,σ2I)[g(z)2]. Thus,
Ez∼N (µ1,σ2I)[g(z)]− Ez∼N (µ2,σ2I)[g(z)] ≤ √ Ez∼N (µ1,σ2I)[g(z)2] √ min { exp ( ‖µ2 − µ1‖22
σ2
) − 1, 1 } .
Notice that, if ‖µ2 − µ1‖ ≥ σ, then exp ( ‖µ2−µ1‖22
σ2
) − 1 ≥ 1. Meanwhile, when x ∈ [0, 1],
exp(x) ≤ 1 + 2x. Thus,√ min { exp ( ‖µ2 − µ1‖22
σ2
) − 1, 1 } ≤ √ min { 1 +
2‖µ2 − µ1‖22 σ2
− 1, 1 } = min { 2‖µ2 − µ1‖2
σ2 , 1
} ,
which finishes the proof.
With Lemma 16, we have that V̂ π0 (s0)− V π0 (s0)
≤E [ 1h−1<τ ( Es′h∼N (f̂(sh,ah),σ2) [ Ṽ πh (sh) ] − Es′h∼N (f∗(sh,ah),σ2) [ Ṽ πh (sh) )]] ≤ H−1∑ h=0 E [√ Es′h+1∼N (f̂(sh,ah),σ2) [ Ṽ πh (s ′ h+1) 2 ] min {√ 2‖f∗(sh, ah)− f̂(sh, ah)2‖ σ , 1 }] ≤ H−1∑ h=0 √ E [ Es′h+1∼N (f̂(sh,ah),σ2) [ Ṽ πh (s ′ h+1) 2 ]]√√√√E[min{2‖f∗(sh, ah)− f̂(sh, ah)22‖ σ2 , 1 }]
≤ √√√√E[H−1∑ h=0 Es′h+1∼P (·|f∗(sh,ah)) [ Ṽ πh (s ′ h+1) 2 ]]√√√√E[H−1∑ h=0 min { 2‖f∗(sh, ah)− f̂(sh, ah)22‖ σ2 , 1 }]
≤H3/2 √√√√E[H−1∑
h=0
min
{ 2‖f∗(sh, ah)− f̂(sh, ah)22‖
σ2 , 1 }] where the second inequality is due to Lemma 17, and the last inequality is due to the fact that Ṽ πh (s ′ h+1) ≤ H , ∀h.

heading: C.3 SUM OF WIDTH SQUARE
text: Lemma 18 (Bound on the Sum of Width Square). Define wF (s, a) := sup
f̄ ,f∈F ‖f̄(s, a)− f(s, a)‖2.
If {β∗k}k∈[K] is a non-decreasing sequence, and ‖f‖2 < C,∀f ∈ F , then:∑ k∈[K] H−1∑ h=0 w2Ft(s k h, a k h) ≤ 1 + 4C2HdimE ( F , T−1/2 ) + 4βKdimE ( F , T−1/2 ) (1 + log T )
Proof. We first show the following lemma, which will be helpful in our proof.
Lemma 19 (Lemma 1 in (Osband & Van Roy, 2014)). If {βk}k∈[K] is a non-decreasing sequence, we have ∑
k∈[K] H−1∑ h=0 1wFk (s k h,a k h)> ≤ ( 4βK 2 +H ) dimE(F , ).
Proof. We first consider when wFk(s k h, a k h) > and is -dependent on n disjoint sub-sequences of {(sih, aih)}i∈[k−1]. By the definition of -dependent, we know ‖f̄ − f‖2,Ek > n 2. On the other hand, by triangle inequality, we know ‖f̄ − f‖2,Ek ≤ 2 √ βk ≤ 2 √ βK , thus n < 4βK 2 . Hence we know when wFk(s k h, a k h) > , then (sh, ah) is at most -dependent on 4βK 2 disjoint sub-sequences of {(sih, aih)}i∈[k−1]. We then show that, for any sequence {(si, ai)}i∈[N ], there is some element (sj , aj) that is - dependent on at least ndimE(F, ) − H disjoint sub-sequences of {(si, ai)}i∈[j−1]. Let n satisfies that ndimE(F , ) + 1 ≤ N ≤ (n+ 1)dimE(F , ), and we will construct n disjoint sub-sequences
{Bi}i∈[n]. We first let Bi = {(si, ai)},∀i ∈ [n]. If (sk+1, ak+1) is -dependent on each Bi, i ∈ [n], we have the desired results. Otherwise, we append (sk+1, ak+1) to the sub-sequence that it is - independent with. Repeat this process until some j > n + 1 is -dependent on each sub-sequence or we have reached N . In the latter case we have ∑ i∈[n] |Bi| ≥ ndimE(F , ) (here we can add at most H − 1 data to avoid the case we need a new episode of data), and since each element of a sub-sequence is -independent with its predecessors, |Bi| ≤ dimE(F , ),∀i by the definition of eluder dimension. Thus |Bi| = dimE(F , ),∀i. And in this case, (sN , aN ) must be -dependent on each sub-sequence by the definition of eluder dimension. Notice that, as our data is collected in an episodic pattern, there are at most H−1 sub-sequences that contains ”imaginary” final episode data introduced to the construction. In this case, we know that there are at least ndimE(F, ) −H disjoint sub-sequences that (sN , aN ) is -dependent, which finishes our claim.
We finally consider the sub-sequence B = {(skh, akh)} with wFk(skh, akh) > . We know that each element in B is -dependent on at most 4βK 2 disjoint sub-sequence of B, but at least -dependent on |B|
dimE(F, )−H sub-sequence ofB. Thus we know |B| ≤ ( 4βK 2 +H ) dimE(F , ), which concludes the proof.
For notation simplicity, we define wt,h := wFt(s t h, a t h). We first reorder the sequence {wt,h}k∈[K],0≤h≤H−1 → {wi}i∈[KH], such that w1 ≥ · · ·wTH . Then we have∑ k∈[K] H−1∑ h=0 w2Ft(s k h, a k h) = ∑ i∈[KH] w2i ≤ ∑ i∈[KH] w2i 1wi<T−1/2 + ∑ i∈[KH] w2i 1wi≥T−1/2 ≤ 1 + ∑ i∈[KH] w2i 1wi≥T−1/2 . As we order the sequence, wj ≥ means∑ k∈[K] H−1∑ h=0 1wFt (skh,akh)> ≥ j. Hence we know
≤ √
4βK j
dimE(F, ) −H =
√ 4βKdimE(F , ) j −HdimE(F , ) ,
which means if wi ≥ T−1/2, then wi < min { 2C, √
4βKdimE(F,T−1/2) k−HdimE(F,T−1/2) } . Hence,∑
i∈[KH]
w2i 1wi≥T−1/2 ≤4C 2HdimE
( F , T−1/2 ) + T∑ j=HdimE(F,T−1/2)+1 4βKdimE(F , T−1/2) j −HdimE(F , T−1/2)
≤4C2HdimE ( F , T−1/2 ) + 4βKdimE ( F , T−1/2 ) (1 + log T ),
which finishes the proof.

heading: C.4 PROOF FOR THEOREM 5 AND THEOREM 12
text: Proof. Define Ek = Pf∗ (f∗ ∈ Fk). When constructing the confidence set, take α = T−1/2 and δ = 0.25 in Lemma 11, which leads to
β∗k := 8σ 2 log(4N (F , T−1/2, ‖ · ‖2)) +HT−1/2(12C +
√ 8dσ2 log(16k2H)).
With our confidence set construction, we know that ∑ k∈[K] P (Ēk) ≤ 0.5. Notice that
Regret(K) = ∑ k∈[K] [ V ∗0 (s k 0)− V πk 0 (s k 0) ]
≤E  ∑ k∈[K] E [ P(Ek)[V ∗(sk0)− V πk 0 (s k 0)] ]+H ∑ k∈[K] P(Ēk)
≤E  ∑ k∈[K] E [ Ṽ πk0,k(s k 0)− V πk 0 (s k 0) ]+ 0.5H
≤H3/2 ∑ k∈K √√√√E[H−1∑ h=0 min { 2‖f̃k(skh, akh)− f∗(skh, akh)‖22 σ2 , 1 }] + 0.5H
≤ √√√√√H2TE  ∑ k∈[K] H−1∑ h=0 min { 2‖f̃k(skh, akh)− f̂∗(skh, akh)‖22 σ2 , 1 }+ 0.5H ≤ √ 2H2T
σ2 ( 1 + 4C2HdimE ( F , T−1/2 ) + 4β∗KdimE ( F , T−1/2 ) (1 + log T ) ) + 0.5H,
where the first equality is due to 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 inequality is due to Lemma 14, the fourth inequality is due to Cauchy-Schwartz 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 5.
Remark It can be undesirable that our regret bound scale with σ−1, which means our algorithm can perform pretty bad when the noise level is extremely low. It is also more or less counter-intuitive. We want to remark that, such phenomenon is only an artifact introduced by our proof strategy. The simulation lemma (Lemma 14) works well when f(s, a) − f̃(s, a) is 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 is at most H . Hence, we can use the following strategy to get rid of the dependency on σ−1. Definition 20 (Bad and Good Episodes). Define episode k as a bad episode, if ∃h ∈ {0, 1, · · · , H− 1}, such that wk,h := wFk(skh, akh) is the largest HdimE(F , σ2T 1/2) elements in the set {wk,h}k∈[K],0≤h≤H−1. Define episode k as a good episode, if it is not a bad episode.
By the definition, we know there are at most HdimE(F , σ2T−1/2) bad episodes. We then show the following lemma, that can be directly generalized from Lemma 18, by setting = σ2T−1/2 and remove the terms from bad episodes. Lemma 21. If {β∗k}k∈[K] is a non-decreasing sequence, and ‖f‖2 < C,∀f ∈ F , then:∑
k∈[K],k is good H−1∑ h=0 w2Ft(s k h, a k h) ≤ σ2 + 4βKdimE ( F , σ2T−1/2 ) (1 + log T )
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 α = σ2T−1/2 and δ = 0.25 in Lemma 11, which leads to
β∗k := 8σ 2 log(4N (F , σ2T−1/2, ‖ · ‖2)) +Hσ2T−1/2(12C +
√ 8dσ2 log(16k2H)).
We have that Regret(K) ≤ √ H2T ( 8βKσ2 + 1)dimE(F , σ2T−1/2)(1 + log T ) + 0.5H +H 2dimE(F , σ2T−1/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 β∗k ∝ σ2, our upper bound in 22 can only scale with σ−1 through the logarithm covering number log(4N (F , σ2T−1/2 and eluder dimension dimE(F , σ2T−1/2). When F is a linear function class, both term should scale with polylog(σ), that matches the result from (Kakade et al., 2020).

heading: D BOUNDS ON THE COMPLEXITY TERM UNDER LINEAR REALIZABILITY
text: We provide the upper bound on the covering number and the eluder dimension of F when F := {θ>ϕ : θ ∈ Rdϕ×d, ‖θ‖2 ≤ W} where ϕ : S × A → Rdϕ is some known feature map. We first make the following standard assumption:
Assumption 6 (Bounded Feature). ‖ϕ(s, a)‖2 ≤ B, ∀(s, a) ∈ S ×A.

heading: D.1 COVERING NUMBER
text: Theorem 23 (Covering Number Bound). We have that N (F , , ‖ · ‖2) ≤ ( 1 + 2BW )dϕ .
Proof. Notice that, by Cauchy-Schwartz inequality, we have that max
(s,a)∈S×A ‖ε>i ϕ(s, a)‖2 ≤ B‖εi‖2, ∀εi ∈ Rdϕ .
Thus, denote ε = [εi]i∈[d], we have that max
(s,a)∈S×A ‖ε>ϕ(s, a)‖22 = max (s,a)∈S×A ∑ i∈[d] ‖ε>i ϕ(s, a)‖22 ≤ B2 ∑ i∈[d] ‖εi‖22 = B2‖ε‖22.
Hence, to find an -cover for F , we just need to find an /B-cover of {θ : θ ∈ Rdϕ×d, ‖θ‖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.

heading: D.2 ELUDER DIMENSION
text: Theorem 24 (Eluder Dimension Bound). We have that
dimE(F , ) ≤ 3dϕe
e− 1 log
( 3 + 12W 2B2
2
) + 1.
Proof. Our proof follows the idea in (Russo & Van Roy, 2013). Define
wk := sup (θ1 − θ2)>ϕ(s, a) : √ ∑ i∈[k−1] ((θ1 − θ2)>ϕi(si, ai))2 ≤ ′, θ1, θ2 ∈ Rdϕ×d , ‖θ1‖ ≤W, ‖θ2‖ ≤W  . For notation simplicity, define ϕk := ϕ(si, ai), θ := θ1−θ2, and Φk := ∑ i∈[k−1] ϕiϕ > i . Obviously, we have that ‖θ‖ ≤ 2W . Moreover, by straightforward calculation, we know∑ i∈[k−1] ( (θ1 − θ2)>ϕi(si, ai) )2 = Trace(θ>ϕkθ). Define Vk := Φk + ( ′)2
4W 2 I , we start from considering the problem max θ Trace(θ>ϕkϕ > k θ), subject to Trace(θ
>Vkθ) ≤ 2 2. The Lagrangian can be formed as L(θ, γ) = −Trace(θ>ϕkϕ>k θ) + λ(Trace(θ>Vkθ)− 2 2), λ ≥ 0. The optimality condition of θ is (λVk − ϕkϕ>k )θ = 0. As Vk is of full rank, λVk − ϕkϕ>k has rank at least dϕ − 1 (as ϕkϕ>k is of rank 1). So the equation
(λVk − ϕkϕ>k )θi = 0, θi ∈ Rdϕ
only has one non-zero solution. Substitute back, we know that (define ‖x‖A := √ x>Ax):
sup{Trace(θ>ϕkϕ>k θ) : Trace(θ>Vkθ) ≤ 2} = √
2 ′‖ϕk‖V −1k . With the conclusion above, we have that wk ≤ sup{θ>ϕk : Trace(θ>Φkθ) ≤ 2, ‖θ‖ ≤ 2W} ≤ sup{θ>ϕk : Trace(θ>Vkθ) ≤ 2 2} = √ 2 ′‖ϕk‖V −1k . Hence, if wk ≥ ′, then ϕkV −1k ϕk ≥ 0.5. Moreover, with Matrix Determinant Lemma, if wi ≥ ′, ∀i < k, we have
det(Vk) = det(Vk−1)(1 + ϕ > k V −1 k ϕk) ≥ det(Vk−1)
( 3
2
) ≥ · · · ≥ det ( ( ′)2
4W 2 I
)( 3
2
)k−1 = ( ′)2d
4W 2d
( 3
2
)k−1 .
Meanwhile,
det(Vk) ≤ ( Trace(Vk)
d
)d ≤ ( B2(k − 1)
d +
( ′)2
4W 2
)d .
Hence, we know ( 3
2
)(k−1)/d ≤ 4W 2B2
( ′)2 · k − 1 d + 1.
Now we only need to find the largest k that can make this inequality hold. For notation simplicity, define α := 4W 2B2
( ′)2 , n = k−1 d . As log(1 + x) ≥ x 1+x and log x ≤ x/e, we have
n 3 ≤ n log 3/2 ≤ log(α+ 1) + log n ≤ log(α+ 1) + log 3 + log(n/3) ≤ log(α+ 1) + log 3 + n 3e . Substitute back, we can obtain the desired result.

heading: E EXPERIMENTAL DETAILS

heading: E.1 ALGORITHM SUMMARY
text: Our algorithm is easily built on SAC. The only difference we make is we decouple the critic network into a representation network φ(·) and a linear layer l(·) on top of the representation. The representation network is governed by the model dynamics loss in SPEDE, and we train a linear layer to predict the Q-value as it lies in the linear space of the representation guaranteed by our analysis. We update the representation by a momentum factor and keep the policy update the same procedure as SAC.

heading: E.2 FULL EXPERIMENTS

heading: E.3 ABLATIONS
text: Our ablation experiments are trying to study an important design choice of the practical algorithm: the momentum used to update the critic function. We summarize the results in Table 3. We can see that using a small large momentum factor such as 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.

heading: E.4 COMPARISON TO LC3
text: We provide a 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 are learning the representation while LC3 assumes a given feature, the performance of SPEDE is much better than LC3 in tasks like Mountain Car and Hopper.

heading: E.5 PERFORMANCE CURVES
text: We provide an additional performance curve including ME-TRPO in Figure 2 for a reference.

heading: E.6 HYPERPARAMETERS
text: We conclude the hyperparameter we use in our experiments in the following.

Review summaries:
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.

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.