Latent Variable Representation for Reinforcement Learning
Authors: Tongzheng Ren
Chenjun Xiao
Tianjun Zhang
Na Li
Zhaoran Wang
sujay sanghavi
Dale Schuurmans
Bo Dai
Venue: ICLR 2023 poster (2023)
Keywords: Latent Variable Model
Markov Decision Processes
Reinforcement Learning

Abstract: Deep latent variable models have achieved significant empirical successes in model-based reinforcement learning (RL) due to their expressiveness in modeling complex transition dynamics. On the other hand, it remains unclear theoretically and empirically how latent variable models may facilitate learning, planning, and exploration to improve the sample efficiency of RL. In this paper, we provide a representation view of the latent variable models for state-action value functions, which allows both tractable variational learning algorithm and effective implementation of the optimism/pessimism principle in the face of uncertainty for exploration. In particular, we propose a computationally efficient planning algorithm with UCB exploration by incorporating kernel embeddings of latent variable models. Theoretically, we establish the sample complexity of the proposed approach in the online and offline settings. Empirically, we demonstrate superior performance over current state-of-the-art algorithms across various benchmarks.

Published as a conference paper at ICLR 2023
LATENT VARIABLE REPRESENTATION FOR REINFORCE- MENT LEARNING
Tongzheng Ren Chenjun Xiao Tianjun Zhang
Na Li
Zhaoran Wang
Sujay Sanghavi² Dale Schuurmans Bo Dai
'Google Research, Brain Team UT Austin *University of Alberta
*UC Berkeley
'Harvard University Northwestern University "Georgia Tech tongzheng@utexas. edu, chen chenjun@ www.uuuaaabbbaa.ca..a bodai bodaiggpogleecom
ABSTRACT
Deep latent variable models have achieved significant empirical successes in model- based reinforcement learning (RL) due to their expressiveness modeling complex transition dynamics. On the other hand, it remains unclear theoretically and empiri- cally how latent variable models may facilitate learning, planning, and exploration improve the sample efficiency of RL. In this paper, provide a representa- tion view of the latent variable models for state-action value functions, which allows both tractable variational learning algorithm and effective implementation of the optmissm/pesiimism principle in the face of uncertainty for exploration. particular, we propose computationally efficient planning algorithm with UCB exploration by incorporating kernel embeddings of latent variable models. The- oretically, we establish the sample complexity of the proposed approach in the online and offline settings. Empirically, we demonstrate superior performance over current state-of-the-an algorithms across various benchmarks.
INTRODUCTION
Reinforcement learning (RL) seeks an optimal policy that maximizes the expected accumulated rewards by interacting with an unknown environment sequentially. Most research in RL is based on the framework of Markov decision processes (MDPs) (Puterman, 2014). For MDPs with finite states and actions, there is already a clear understanding with sample and computationally efficient algorithms (Auer et al., 2008; Dann & Brunskill, 2015; Osband & Van Roy, 2014; Azar et al., 2017; Jin et al., 2018). However, the cost of these RL algorithms quickly becomes unacceptable for large or infinite state problems. Therefore, function approximation or parameterization is a major tool to tackle the curse of dimensionality. Based on the parametrized component to be learned, RL algorithms can roughly be classified into two categories: model-free and model-based RL, where the algorithms the former class directly learn a value function or policy to maximize the cumulative rewards, while algorithms in the latter class learn model to mimic the environment and the optimal policy is obtained by planning with the learned simulator.
Model-free RL algorithms exploit end-to- learning paradigm for policy and value function training, and have achieved empirical success in robotics (Peng et al., 2018), video-games (Mnih et al., 2013), and dialogue systems (Jiang al., 2021), to parameterizations. The flexibility of such parameterizations, however, also comes with a cost in optimization and exploration. Specifically, it is well-known that lemporal-difference methods become unstable or even divergent with general nonlinear function approximation (Boyan & Moore, 1994; Tsitsiklis & Van Roy, 1996). Uncertainty quantization for general nonlinear function approximators is also underdeveloped. Although there are several theoretically interesting model-free exploration algorithms with general nonlinear function approximators (Wang et al., 2020; Kong al., 2021; Jiang et al., 2017), a computationally-fiinn
few, thanks to flexible deep neural network
exploration method for model-free RI. is still missing.
Model- based RL algorithms, on the other hand, exploit more information from the environment during learning, and are therefore considered to be more promising in terms of sample efficiency (Wang et al., 2019). Equipped with powerful deep models, model-based RL can successfully reduce
"Equal Contribution. Project Website:

---

Published as a conference paper at ICLR 2023
approximation error, and have demonstrated strong performance in practice (Hafner et al., 2019a;b; Wu et al., 2022), following with some theoretical justifications (Osband & Van Roy, 2014; Foster et al., 2021). However, the reduction of approximation error brings new challenges in planning and exploration, which have not been treated seriously from the empirical and theoretical aspects. Specifically, with general nonlinear models, the planning problem itself is already no longer tractable, and the problem becomes more difficult with an exploration mechanism introduced. While theoretical analysis typically assumes a planning oracle providing an optimal policy, some approximations are necessary in practice, including dyna-style planning (Chua et al., 2018; Luo et al., 2018), random shooting (Kurutach al., 2018; Hafner al., 2019a), and policy search with backpropagation through time (Deisenroth & Rasmussen, 2011 I; Heess et al., 2015). These may lead to sub-optimal policies, even with perfect models, wasting potential modeling power.
In sum, for both model-free and model-based algorithms, there has been insufficient work consid- ering both statistical and computation tractability and efficiency terms of learning, planning and exploration in unified and coherent perspective for algorithm design. This raises the question:
Is there a way to design provable and practical algorithm to remedy both the statistical and computational difficulties of RL?
Here, by "provable" we mean the statistical complexity of the algorithm can be rigorously character- ized without explicit dependence on the number of states but instead the fundamental complexity of the parameterized representation space; while by "practical" we mean the learning, planning and exploration components in the algorithm are computationally tractable and can be implemented in real-world scenarios.
This work provides an affirmative answer to the question above by establishing the representation view of latent variable dynamics models through a connection to linear MDPs. Such connection immediately provides computationally tractable approach to planning and exploration in the linear space constructed by the flexible deep latent variable model. Such a latent variable model view also provides variational learning method that remedies the intractbility of MLE for general linear MDPs (Agarwal et al,, 2020; Uehara et al., 2022). Our main contributions consist of the following:
We establish the representation view of latent variable dynamics models in RL, which naturally induces Latent Variable Representation (LV-Rep) for lincarly representing the state-action value function, and paves the way for a practical variational method for representation learning (Section 3);
We provide computation efficient algorithms to implement the principle of optimistm and pes- simism in the face of uncertainty with the learned LV-Rep for online and offline RI. (Section 3.1);
We theoretically analyze the sample complexity of LV-Rep in both online and offline settings, which reveals the essential complexity beyond the cardinality of the latent variable (Section 4); and model-
We empirically demonstrate LV-Rey Rep outperforms the sate-of-the--ad free RL algorithms on several RL benchmarks (Section 6)
PRELIMINARIES
In this section, we provide brief introduction to MDPs and linear MDP, which play important roles in the algorithm design and theoretical analysis. We also provide the required background knowledge on functional analysis in Appendix D.
2.1 MARKOV DECISION PROCESSES
We consider the infinite horizon discounted Markov decision process (MDP) specified by the tuple M = AS,A, r, r,7, do), where S is the state space, .A is a discrete action space, T x A + ASS) is the transition,
S x A - [0, 1] is the reward, 7 (0, 1) is the discount factor and do E A(S) is the initial state distribution. Following the standard convention (e.g. Jin et al., 2020), we assume r(s, a) and do are known to the agent. We aim find the policy : A(A), that maximizes the following discounted cumulative reward:
V
E /rr(s,,
80 do
2

---

Published as a conference paper at ICLR 2023
1 00, 1->
We define the state value function V S
and state-action value function Q:S. x A -
1 1-7 following the standard notation: 0,
(s, = Eisu 70r(8;,
az) az) = 00 a
Vg. (s) E (. 197., (s, a)]
It is straightffrward to that Vi.,, Egndo vr,,((s)
well as the following Bellman equation:
(s, a) = r(s, a) + T [V'),.(+')]
We also define the discounted occupancy measure d of policy as follows:
d7- (s. = Ey ,
Ei=0 7 =
00
do
By the definition of the discounted occupancy measure, we can see Vi-..- B(o.a)ma7. Ir Furthermore, with the property of the Markov chain, we can obtain d (s, a) = (1 - 7)do T[als) + "B (e.a) [T (s(3, x T(a|s)]
2.2
LINEAR MDP
In the tabular MDP, where the state space [S] is finite, there exist lots of work on sample- and computation-effiiiee RL algorithms (e.g. Azar et al., 2017; Jin et al., 2018). However, such methods can still be expensive when |S] becomes large or even infinite, which is quite common for in real- world applications. To address this issue, we would like to introduce function approximations into RL algorithms alleviate the statistical and computational bottleneck. The linear MDP (Jin et al., 2020; Agarwal et al., 2020) is promising subclass admits special structure for such purposes.
Definition (Linear MDP (Jin et al., 2020; Agarwal al., 2020)). An MDP is called linear MDP if there exists o² S x A - H and μ² S > H for some proper Hilbert space H. such that T ("15's,, a) (6" (s, a). (s')
The complete definition of linear MDPs require o² and μ² satisfy certain normalization conditions, which we defer to Section 4 for the ease of presentation. The most significant benefit for linear MDP that, for any policy æ S A. (7, a) is linear with respect [r(s, a), oz (' (s),)), thanks to the following observation:
@F.,r(s,a) ( a) r(s. [V'] r(( =(s..))
(F (s')ds)
H
Plenty of sample-efficient algorithms have been developed based on the linear MDP structure with known d² (e.g. Yang & Wang, 2020; Jin et al., 2020; Yang et al., 2020). This requirement limits their practical applications.
fact, in most cases, we do not have access to 6² and we need to perform representation learning to obtain estimate of o², However, the learning of ø relies on efficient exploration for the full-coverage data, while the design of exploration strategy relies on the accurate estimation of Φ. The coupling between exploration and learning induces extra difficulty.
Recently, Uchara et al. (2022) designed UCB-style exploration for iterative diite-dimension repre- sentation updates with theoretical guarantees. The algorithm requires the computaiton oracle for the maximum likelihood estimation (MLE) to the conditional density estimation.
(o(s,.), a). u(s'jas')
max
log(o(s;, az), ((())) s.t. ((s,)),
=
(2)
which is difficult we generally do not have specific realization of (b,1z) pairs to make the constraints hold for arbitrary (s, a) pairs, and therefore, impractical for real-world applications.
LATENT VARIABLE MODELS AS LINEAR MDPS
In this section, we first reveal the linear representation view of the transitions with latent vari- able structure. This essential connection brings several benefits for learning. planning and ex- ploration/exxlooitatio.. More specifically, the latent variable model view provides us tractable variational learning scheme, while the linear representation view inspires cetpuuttatioallfffffieeeee planning and exploration/exploitaion mechanism.
3

---

Published as a conference paper at ICLR 2023
We focus on the transition operator T 8 - A(S) with latent variable structure, i.e., there exist latent space and two conditional probability measure p" (z|ss a) and p" ps((2)), such that
T (5'1,,,, a) p" (=|s, a)p" (s)),)
(3)
where j is the Lebesgue measure on Z when 2 is continuous and μ is the counting measure on Z when discrete.
Assume that p" (-1s, E (0((') E L2(n), we have the equivalent formulation of (3) as (s (p" (-Is, p"() (s'1))))
which obviously demonstrates the linear MDP structure following Defintion 1, and immediately implies 6* (s, a) = p (-1s,a), and μ² (s') = ps('))). We call p (+|s, a) Latent Variable Repre- sentation (LV-Rep).
Connection to Ren et al. (2022b). To provide a concrete example of LV-rep, we consider the stochastic nonlinear control model with Gaussian noise (Ren et al., 2022b), which is widely used in most of model-based RL algorithms. Such model can be understood as a special case of LV-Rep. In Ren et al. (2022b), the transition operator is defined
T (s'1s,a) = (2Ta") -d/2 exp (- 8"
(s,, (s,,))l ((,a0))) = (p" (1),,)). (s'1:)) (4)
where p" (zls, a) x exp (-2 1 (s, a)ll /o²) and p" (s'[z) x exp (-2 s'1 /02) both following the Gaussian distributions. The proposed LV-Rep can exploit more general distributions beyond Gaussian for p" (-|s, a) and p* (s'[z), that introduces more flexibility in transition modeling.
Our definition of LV-Rep is more general than the original definition (Definition 2) in Agarwal et al. (2020), which assumes | is finite. As shown by Agarwal et al. (2020). block MDPs (Du al., 2019; Misra et al., 2020) with finite latent state space E have latent variable representation where corresponds to the set of observation, 2 corresponds to the set of latent state, and p* (2'|s, a) is a composition of deterministic p(z[s) and a transition p(z'|z, 2z, a). Agarwal et al. (2020) also remarks that, compared with the latent variable representation, the original low-rank representation relaxes the simplex constraint However, the ambient dimension may not be a proper measure of the representation complexity. As will show in Section 4, even work the infinite Z, as long as p(2|s, a) E H4 and k satisfies standard regularity conditions, we can still perform sample-efficient learning. A proper measure of the representation complexity is still open problem to the whole community.
the p" (z|ss a), and thus, be more compact with fewer dimensions.
The LV-Rep with p" (-|s, a) and p" (s"l.) naturally satisfies the distribution requirements, which brings the benefits of efficient sampling and learning.
Efficient Simulation from LV-Rep. Specifically, we can easily draw samples from the learned model ()) S& p(z|s, ())(s'(z)d) by first sampling
p(z(s,a), a), then sampling & ~ p[)) without the need to call other complicated samplers, e.g., MCMC, for the general un- normalized transition operator linear MDPs. Such a property is important for computation-effiient planning on the learned model.
Variational Learning of LV-Rep. Another significant benefit the LV-Rep is that, we can leverage the variational method obtain tractable surrogate objective of MLE, which is also known the evidence lower bound (ELBO) (Kingma et al., 2019), that can be derived as follows:
log T(s'ls, a) = log /
p² (#|s, (s'12)dz = log p" acls,a)p"(s(11 (=1|,, a, d')
a,)
max LE (E [logp" (s'1z)] - DKL (q(2|s, a, s ''lp" (2)s, (22(2)
(5)
where q(2)s, s') is an auxiliary distribution. The last equality comes from Jensen's inequality, and the equality only holds when q (z|s, a, s') = p (2]ss, a, s') x (2(s,a) (s'1z).
Compared with the standard MLE used in (Agarwal et al., 2020; Uchara et al., 2022), maximizing the ELBO is more computation-effiiien as it avoids the computation of integration at any time. Meanwhile, if the family of variational distribution is sufficient flexible that contains the optimal p(z|s, a, s') for any possible (p(z|s, a), p(s' [z)) pair, then maximizing the ELBO is equivalent to perform MLE, Le., they share the same solution,
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 Online Exploration with LV-Rep
1: Input: Model class P = [[p(z]s,0g a), p(s"(2))) 2 {q(z|s, a, s')}. Iteration N.
2: Initialize (s) = ((A) where ((A) denotes the uniform distribution on A: Do - 0: D/ 0.
3: for episode n 1, 1,...... NN do
4: Collect the transition (s, a', a', 8) where U(AA), $ ~ T (-Is', a²). D = Dn-1 U fs, a, s'], D' = = a-1
dT. dr--).
U(A),
(-)s,
5:
Learn the latent variable model pn(2118 with Dn U'D, via maximizing the ELBO in (5),
and obtain the learned model F,,
6: Set the exploration bonus (s,ssa) (7).
7:
Update policy Tn arg max, V Tnrtthn'
8: end for
9: Return T1,-" -.
3.1 REINFORCEMENT LEARNING WITH LV-REP
As the transition operator is linear with respect LV-Rep, the state-action function for arbitrary policy can be linearly represented by LV-Rep. Once the LV-Rep is learned, we can execute planning and exploration in the linear space formed by LV-Rep. Due to the space limit, we mainly consider online exploration setting, and the offline policy optimization is explained in Appendix B.
Practical Parameterization of Q function. With the linear factorization of dynamics through latent variable models (I), we have
Q (s, r(s, a) + (alpa [=)[;
(6)
where (s)= (=)s") (s')ds' can be viewed a value function of latent state. When the latent variable is in finite dimension, i.e., |2] is finite, we have [u[[)]<Ez E , and the expectation (=]s,a)) [w= (=)] can be computed exactly by enumerating over Z.
However, when 2 is not a finite set, generally we can not exactly compute the expectation, which makes the representation of Q function through p" (2] s, a) hard. Particularly, under our normalization condition Assumption 2 shown later, have w E H4 where H4 is reproducing kernel Hilbert space with kernel k. When i admits a random feature representation (see Definition 13), we can then express th
(z) THTT (E(()EEE)))))P)))
where the concrete P(E) depends on kernel k. Plug this representation of (=))) into (6), we obtain the approximated representation of Q7- (s,a) as:
(s,,n(s,a) = r(s, +
w- (=)x
(s)ss(s) a2)s
= r({,, +
(())(=;;))PP (=ls,
= r(8
7 Σ (Z..).
m xE(m)
which shows that we can approximate Q7-, with linear function on top of the random feature ppss, a) = (2; ke) where 2; p² (2]s, a) and & P(E). This can be viewed two-layer neural network with fixed first layer weight & and activation & and trainable second layer weight (w)))) m
Planning and Exploration with LV-Rep. Following the idea of REP-UCB (Uehara et al., 2022), we introduce additional bonus to implement the principle of optimism in the face of uncertainty. We use the standard elliptical potential for the upper confidence bound, which can be computed efficiently below,
Pn a) [v(z (i)lee(m)
where (Z)temm) pn(21ssa),
[EHeejm) ~ P(E),
(, a) a))
with Σ, = Σ
(n (,),,,a)) + Al, (7)
where On, and À some constants, and D,, is the collected dataset.
5

---

Published as a conference paper at ICLR 2023
The planning can be then completed by Bellman recursion with bonus, i.e.,
(8) We can exploit the augmented feature [r(s, a), co(s, a). 8n (s, a)] to linearly represented Q" after bonus introduced. However, there will be an extra O (m²² due to the bonus in feature. There- fore, we consider a two-layer MLP upon to parametrize Q(s, = wor(s, a) + wi co(s, a) + Wh a (wg (pss a)), where o (-) is a nonlinear activation function, used for complement the effect of the nonlinear b,. We finally conduct approximate dynamic programming style algorithm (e.g. Munos & Szepesvári, 2008) with the Q parameterization.
Q" (s. = (s, a) + bn (s, a) + +.by [V* (5'].
The Complete Algorithm. We show the complete algorithm for the online exploration with LV-Rep in Algorithm 1. Our algorithm follows the standard protocol for sequential decision making. In each episode, the agent first executes the exploratory policy obtained from the last episode and collects the data (Line 4). The data are later used for training the latent variable model by maximizing the ELBO defined in equation 5 (Line 5). With the newly learned (=]s,, a), we add the exploration bonus defined in equation 7 to the reward (Line 6), and obtain the new exploratory policy by planning on the learned model with the exploration bonus (Line 7), that will be used in the next episode. Note that, in Line 4, requires to sample s ~ d--- which can be obtained by starting from Su de, executing Tn- stopping with probability 1 - y at each time step t 2 O and returning st. LV-Rep can also be used for offline exploitation, and we defer the corresponding algorithm to Appendix B.
THEORETICAL ANALYSIS
In this section, we provide the theoretical analysis of representation learning with LV-Rep. Before we start, we introduce the following two assumptions, that are widely used in the community (e.g. Agarwal et al., 2020; Uchara al., 2022).
Assumption 1 (Finite Candidate Class with Realizability), [P] < oo and Meanwhile, for all (p(2)s, a). ()) E P. p(2)s, Q
(s1=)) E..
Remark 1. The assumption on P is widely used in the community (e.g. Agarwal et al., 2020; Uehara et al., 2022), while the assumption on Q is to guarantee the estimator obtained by maximizing the ELBO defined in equation 5 is identical to the estimator obtained by MLE. We would like to remark that, the extension to other anta-independent function class complexity (e.g. Rademacher complexity (Bartlett & Mendelson, 2002)) can be straightforward with a refined non-asymptotic generalization bound of MLE.
Assumption 2 (Normalization Conditions). VP P, (s. E A, lepp(p((,s, (000-ss.a)]lz a)l S 1. Further- more, Vg S + TR. such that || < 1, we have Ils (isspsss)))))) (1((')))(s''))d))) Hee S.G. C.
Remark 2. Our assumptions normalization conditions is substantially differentt from standard linear MDPs. Specifically, standard linear MDPs assume that the representation Φ(s, a) and pus') are of finite dimension d, with [|o(s, a)ll2 S and V|[g|lo I 1, |lSs ((s'))(s')dds")) [|2 S d. When |2] is finite, as [[fll & || our normalization conditions are more general than the counterparts of the standard linear MDPs and
use the identical normalization conditions the standard linear MDPs. However, when |2| is infinite, if we assume [|p(2|s a) [a(u)) S 1, we cannot provide a sample complexity bound without polynomial dependency on [P), which can be unsatisfactory. Furthermore, we would like to note that, the assumption f& p( (=)g(s"))) )'s'' E Hr is mild, which is necessary for justifying the estimation from the approximate dynamic programming algorithm.
Theorem 1 (PAC Guarantee for Online Exploration, Informal). Assume the reproducing kernel k satisfies the regularity conditions in Appendix E.I. If we properly choose the exploration bonus (1 a), we can obtain an e-optimal policy with probability at least 1 - ô after we interact with the environments for N = poly (C, AA, (1- -,,, (/))) episodes.
Remark 3. Although | may not finite, we can still obtain sample complexity independent w.r.t. |S], while has polynomial dependency on C. [A]. (1 (1-7)-1 and and log [P] with the assumption that p(-1s, a) E Hy and some standard regularity conditions for the kernel k. This means that we do not really need to assume discrete Z with finite cardinality, but only need to properly control the complexity of the representation class, by either the ambient dimension (Z), or some "effective dimension" that can be derived from the eigendecay of the kernel & (see Appendix E. for the details). The formal statement for Theorem and the proof is deferred to Appendix E.2. We also provide the PAC guarantee for offline exploitation with LV-Rep in Appendix F.3.

---

Published as a conference paper at ICLR 2023
Remark 4. Our proof strategy is based on the analysis of REP-REUU UCB (Uehara et al., 2022). However, there are substantial differences between our analysis and the analysis of REP-UCB, as the representa- tion we consider can be infinitediimesiionall and hence the analysis of REP-UCB, which assumes that the feature is finite-dimensional, cannot be directly applied in our case. As we mentioned, to address the infinite dimension issue, we assume the representation p(z|s, a) E Hr and prove two novel lemmas, one for the concentration of bonus (Lemma 17) and one for the ellipsoid potential bound (Lemma 19) when the representation lies in the RKHS, We further note that, different from the work on the kernelized bandit and kernelized MDP (Srinivas et al., 2010; Valko et al., 2013; Yang et al., 2020) that assume the reward function and Q function lies in some RKHS, we assume the condition density of the latent random variable lies in the RKHS and the Q function is the (2(2) inner product of two functions in RKHS. As a result, the techniques used in their work cannot be directly adapted to our setting, and their regret bounds depend on the alternative notions of maximum information gain and effective dimension of the specific kernel, which can be implicd by the eigendecay conditions we assume in Appendix 1 (see Yang et al. (2020) for the details).
5 RELATED WORK
There are several other theoretically grounded representation learning methods under the assumption of linear MDP. However, most of these work either consider more restricted model or totally ignore the computation issue. Du et al. (2019); Misra et al. (2020) focused on the representation learning in block MDPs, which is special case of linear MDP (Agarwal et al., 2020), and proposed to learn the representation via the regression. However, both of them used policy-cover based exploration that need to maintain large amounts of policies in the training phase, which induces significant computation bottleneck. Uchara et al. (2022) and Zhang et al. (2022b) exploit UCB upon learned representation to resolve this issue. However, their algorithms depend on some computational oracles, i.e., MLE for unnormalized conditional distribution in (2) or max- - min max optimization solver motivated from Modi al. (2021), respectively, that can be hard to implement in practice.
A variety of recent work have been proposed to replace the computational oracle with more tractable estimators. For example, Ren al. (2022b) exploited representation with the structure of Gaussian noise in nonlinear stochastic control problem with arbitrary dynamics, which restricts the flexibility. Zhang al. (2022a); Qiu al. (2022) proposed to use a contrastive learning approach as an alternative. However, similar to other contrastive learning approach, both of their methods require the access to negative distribution supported on the whole state space, and their performance highly depends on the quality of the negative distribution. Ren et al. (2022a) designed new objective based on the idea of the spectral decomposition. But the solution for their objective is not necessarily to be a valid distribution, and the generalization bound is worse than the MLE when the state space is finite.
A Algorithmically, many representation learning methods have been developed for different purposes, such as state extractor from vision-based based features (Laskin et al., 2020a;b; Kostrikov et al., 2020), bi-simulation (Ferns et al., 2004; Gelada et al., 2019; Zhang et al., 2020), successor feature (Dayan, 1993; Barreto al., 2017; Kulkarni et al., 2016), spectral representation from transition operator decomposition (Mahadevan & Maggioni, 2007; Wu et al., 2018; Duan et al., 2019), contrastive learning (Oord et al., 2018: Nachum & Yang, 2021; Yang et al., 2020), and so on. However, most of these methods are designed for state-only feature, ignoring the action dependency. and learning from pre-collected datasets, without taking the planning and exploration in to account and ignoring the coupling between representation learning and exploratin. Therefore, there is no rigorously theoretical characterization provided.
We would like to emphasize that the proposed LV-Rep is the algorithm which achieves both statistical efficiency theoretically and computational tractability empirically. For more related work on model- based RL, please refer to Appendix A.
EXPERIMENTS
We extensively test our algorithm the Mujoco (Todorov et al., 2012) and DeepMind Control Suite (Tassa et al., 2018). Before presenting the experiment results, we first discuss some details towards a practical implementation of LVV-Rep.
7

---

Published as a conference paper at ICLR 2023
Table I: Performance on various MuJoCo control tasks. All the results averaged across random seeds and a window size 10K, Results marked with is adopted from MBBI.. LV-Rep-C and LV-Rep-D use continuous and discrete latent variable model respectively. L LV-Rep achieves strong performance compared with baselines.
HaltChoctah
Reacher
Humanoid-ET
Pendulum
I-Pendulam
ME-TRPO"
2283,7=900.4
-13.425,2
72.9#8.9
177.3+119
126.24:6666
Model-Based RI.
PETS RS*
966.91471.88
40.1
109.6110200 102.6
167.91335.8
-1.11:255.1
PETS-CEM"
879.9
-12.345.2
110.:190.11
167.44:53.0
-20.5:22.9
Best MBBL
3639.0=11354.
4.1:0011
1377.0=t:30.4
177,3+1999
0.0:00.0
PPO"
17.2488444
-17.240099
39.
163.448.00
-008:221.0 0
Model-Free RL
TRPO
-2.00485.5
-10.1+00.6
289.8455.2
166.747.3
-27.6+15.8
SAC' (3-aaeer)
4000.7+:002.1
-6.420055
1794,4:1458..
168.249955
+0.2::011
DeepSF
1180
-1684336
168.6+511
168. 6.1.1
+0.++0..3
SPEDE
4210.3+-92.6
-7.2111
886.9:195.22
169.5::0.66
0.0:2:.00
Representation
LN-Rep-C LV-Rep-D
439.55
1088.2
167.11.3.1
0.0
2616.5=:61.5
-6.0=:0.2
1359.2 1998.6
170.2 = 4.2
0.0:=0.0
Ant-ET
Hopper-ET
S-Humanoid-ET
CartPolc
Walker-ET
ME-TRPO'
42.64221.1
1272.5+:500.9
154.9=534.3
160. (9:
16679,36657.5
PETS-RS"
130,0=#48.11
205 00:365566.5
320.7++182.2
195. 08.28.0
312.5=493.4
Model-Based RL
PETS-CEM"
81.6=145.88
129,34.36.0
355.1=:157.1
195.5::3.0
536.2=536.9
Best MBBL
275.4.3009.1
1272.5...00.9
1084.3.1.7.0
20000.1000
312.5 11 493.4
PPO
80.1
758.0:162.U
454.3-136.7
86.5
306.1
Model.
TRPO
116.8147.3
237.41333.5
281.311:0.9
47.31.1.77
229.5:1:7711
SAC" (3-layer)
2012.7
1855.5-2655.1
834.6:3313.11
199.4:10.4
2216.411678.77
DeepSF
768.1:144.1
548.9.12553
533.8:1154.9
194.51...8
165.6.1127.9
SPEDE
806:2::60.2
732.21263.9
986,4 986.4:1154.7
138. 138.244.3..5
201.6-2204.0
Representation RL
LV-Rep-C
2511.81460.
1946.8
963.11145.1
2.0
2323,511:33.9
Re-
603..0.603.1
2187.5:1453.6
956.8:1: 87.5
198.5 + 2.0
2209.011.58..2
6.1 IMPLEMENTATION DETAILS
As discussed, the latent variable representation learned by minimizing the ELBO (5). We consider two practical implementations. The first one applies a continuous latent variable model, where the distributions are approximated using Gaussian with parameterized mean and variance, similarly to (Hafner et al., 2019b). We call this method LV-Rep-C. The second implementation considers using discrete sparse latent variable model (Hafner et al., 2019b), which we call LV-Rep-D. D. As discussed in line 7 of Algorithm 1, we apply a planning algorithm with the learned latent representation to improve the policy. We use Soft Actor Critic (SAC) (Haarnoja et al., 2018) as our planner, where the critic is parameterized as shown in (6). In practice, we find that is beneficial have more updates for the latent variable model than critic. We also use target network for the latent variable model to stabilize training.
6.2 DENSE-REWARD REWARD MUJoCo BENCHMARKS
We first conduct experiments on dense-reward Mujoco locomotion control tasks, which are commonly used test domains for both model-free and model-based algorithms, including ME-TRPO (Kurutach et al., 2018), PETS (Chua et al., 2018), and the best model-based results from (Wang et al., 2019), among baselines (Luo et al., 2018; Deisenroth & Rasmussen, 2011; Heess al., 2015; Clavera et al., 2018; Nagabandi et al., 2018; Tassa et al., 2012; 2; Levine & Abbeel, 2014), as well as model-free algorithms, including PPO (Schulman al., 2017), TRPO (Schulman al., 2015) and SAC (Haarnoja al., 2018).
RL algorithms. We compare LV-Rep with
We compare all algorithms after running 200 environment steps. Table presents all experiment results, where all results are averaged over 4 random seeds. In practice we found LV-Rep-C provides comparable or better performance (see Figure for example), so that we report its result for LV-Rep in the table. We present the best model- RL. performance for comparison. The results clearly show that LV-Rep provides significant better or comparable performance compared to all model-based algorithms. In particular, in the most challenging domains such as Walker and Ant, most model- based methods completely fail the task. while LV-Rep achieves the otate-of-the-art performance in contrast. Furthermore, LV-Rep show dominant performance in all domains comparing to two representative representation learning based RL methods, Deep Successor Feature (DeepSF) (Barreto et al., 2017) and SPEDE (Ren et al., 2022b). LV-Rep also achieves better performance than the strongest model-free algorithm SAC in most challenging domains except Humanoid.
8

---

Published as a conference paper at ICLR 2023
Table 2: Performance of various Deepmind Suite Control tasks. All the results averaged across four random seeds and window size 10K. Comparing with SAC, our method achieves even better performance on sparse-reward tasks.
choctah run
walker run
humanoid run
hopper hop
Model-Based RL
Dreamer
542.0 = 27.7
337.7=67.22
I 1.0+0.22
17.3
PRO
227.71:57.99
51.6:1:55
1.1:1.00
0.7.1..88
Model-Pree RL
SAC
453.4:1:7.99
488.5
1.1:0.1
10.8:66.6
DeepSF
295.3++433.5
27.9:+2.2
0.9+0011
0.3++0.1
Representation RL
Proto RL.
305.5::37.9
433.5+4:56.8
0.3:::066
1,0=0.2
LN-Rep
639.312245
724.2.137.8
11.8
72.91140.6
Finally, we provide learning curves of LV-Rep-C and LV-Rep-D in comparison to SAC in Figure 1, which clearly shows that comparing the SOTA model-free baseline SAC, I.VRRe enjoys great sample efficiency in these tasks.
2000
2000
300
200
1000
1000
20
15
23
10
(155)
barning Alp
Figure 1: We show the learning curves in Mujoco control compared to the baseline algorithms. The r-axis shows the training iterations and y-axis shows the performance. All plots are averaged over random seeds. The shaded area shows the standard error. We only compare SAC as it has the best overall performance in all baseline methods.
6.3 REWARD DEEPMIND CONTROL SUITE
In this experiment we show the effectiveness our proposed methods in sparse reward problems. We compare LV-Rep with the offe--of-the-art model-free RL methods including SAC and PPO. Since the proposed LV-Rep significantly dominates the model- RL algorithms in MuJoCo from Wang al. (2019), we consider different model-based RL method, i.e., Dreamer (Hafner et al,,, 2019b), and add another representation-basee RL. methods, i.e., Proto-RL (Yarats et al., 2021), besides DeepSF (Barreto al., 2017).
We compare all algorithms after running 200K environment steps across 4 random seeds. Results are presented in Table 2. We report the result of LV-Rep-C for LV-Rep as gives better empirical performance. We can clearly observe that LV-Rep dominates the performance across all domains. In relatively dense-reward problems, cheetah-run and walker-run, LV-Rep outperforms all baselines by large margin. Remarkably, for sparse reward problems, hopper-hop and humanoid-rur, LV-Rep provides reasonable results while other methods do not even start learning.
We also plot the learning curves of LV-Rep with all competitors in Figure 2. This shows that LV-Rep outperforms other baselines in terms of both sample efficiency and final performance.
hamanoli
50
LVChao
SkC
2012
PRO
FPO
Dveerar
Dreane
Provit
240
80
braning Mapa (155)
braming (tp
baiiigg shaa (1a2)
tuihing Mazs (145)
We show the results in DeepMind Control Suite compared to the baseline algorithms. The r-axis shows the training iterations and y-axis shows the performance. All plots are averaged over random seeds. The shaded area shows the standard error.
Figure 2:

---

Published as a conference paper at ICLR 2023
7 CONCLUSION
In this paper, we reveal the representation view of latent variable dynamics model, which induces the Latent Variable Representation (LV-Rep). Based on the LV-Rep, new provable and practical algorithm for reinforcement learning is proposed, achieving the balance between flexibility and efficiency in terms of statistical complexity, with tractable learning, planning and exploration. We provide rigorous theoretical analysis, which is applicable for LV-Rep with both finite- and infinite- dimension and comprehensive empirical justification, which demonstrates the superior performances.
REFERENCES
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-201007 2020.
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68(3):337-404, 1950.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning, Advances neural information processing systems, 21, 2008.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pp. 263-272 PMLR, 2017.
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. Advances in neural information processing systems, 30, 2017.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):4634482, 2002.
Justin Boyan and Andrew Moore. Generalization in reinforcement learning: Safely approximating the value function. Advances in neural information processing systems, 7, 1994.
Bernd Carl and Inmtraud Stephani. Entropy. Compactness and the Approximation of Opera- tors. Cambridge Tracts in Mathematics. Cambridge University Press, 1990. doi: 10.1017/ CBO978051 1897467.
Jonathan Chang, Masatoshi Uehara, Dhruv Sreenivas, Rahul Kidambi, and Wen Sun. Mitigating covariate shift in imitation learning via offline data with partial coverage. Advances in Neural Information Processing Systems, 34:965-979, 2021.
Krzysztof Choromanski, Mark Rowland, Tamás Sarlós, Vikas Sindhwani, Richard Turner, and Adrian Weller. The geometry of random features. In International Conference on Artificial Intelligence and Statistics, pp. 1-9, PMLR, 2018
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in handful of trials using probabilistic dynamics models. Advances in neural information processing systems, 31, 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.
Bo Dai, Bo Xie, Niao He, Yingyu Liang, Anant Raj, Maria-Florina F Balcan, and Le Song. Scalable kernel methods via doubly stochastic gradients. Advances in neural information processing systems, 27, 2014.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. Advances in Neural Information Processing Systems, 28, 2015.
Peter Dayan. Improving generalization for temporal difference learning: The successor representation. Neural computation, 5(4):613-624 1993.
10

---

Published as a conference paper at ICLR 2023
Mare Deisenroth and Carl E Rasmussen. Pilco: A model- and data-efficient approach policy search. In Proceedings of the 28th International Conference on machine learning (ICML-11), pp- 465-472. Citeseer, 2011.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pp. 1665-1674. PMLR, 2019.
Yaqi Duan, Tracy Ke, and Mengdi Wang. State aggregation learning from markov transition data. Advances in Neural Information Processing Systems, 32, 2019.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes. In UAI, volume pp. 162-169, 2004.
Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.1348/ 2021.
Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Marc G Bellemare. Deepmdp: Learning continuous latent space models for representation learning, In International Conference on Machine Learning. pp. 2170-2179, PMLR, 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pp. 1861-1870. PMLR, 2018.
Danijar Hafner, Timothy Lillicrap. Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. In International Conference on Learning Representations, 2019a.
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, 2019b.
Danijar Hafner, Timothy P Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. In International Conference on Learning Representations, 2020.
Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learn- ing continuous control policies by stochastic value gradients. Advances in neural information processing systems, 28, 2015.
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 11X2x:2102.10242. 2021.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pp. 7704-1713 PMLR, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Diederik Kingma, Max Welling, et al. introduction to variational autoencoders. Foundations and Trends@ in Machine Learning, 12(4)3307-322, 2019.
Dingwen Kong, Ruslan Salakhutdinov, Ruosong Wang, and Lin F Yang. Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint 1=Xi::2106.07203, 2021.
Ilya Kostrikov, Denis Yarats, and Rob Fergus. Image augmentation is all you need: Regularizing deep reinforcement learning from pixels. arXiv preprint arXiv:2004 13649, 2020.
11

---

Published as a conference paper at ICLR 2023
Tejas D Kulkarni, Ardavan Saeedi, Simanta Gautam, and Samuel J Gershman. Deep successor reinforcement learning. arXiv preprint 1o06v:1606.02555 0239,, 2016.
Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. In International Conference Learning Representations, 2018.
Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Curl: Contrastive unsupervised representations for reinforcement learning. In International Conference on Machine Learning, pp. 5639-5650. PMLR, 2020a.
Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto. Pieter Abbeel. and Aravind Srinivas. Rein- forcement learning with augmented data. Advances in neural information processing systems, 33: 19884-19895, 2020b.
Alex X Lee, Anusha Nagabandi, Pieter Abbeel, and Sergey Levine. Stochastic latent actor-critic: Deep reinforcement learning with a latent variable model. Advances in Neural Information Processing Systems, 33:741-752, 2020.
Sergey Levine and Pieter Abbeel. Learning neural network policies with guided policy search under unknown dynamics. Advances in neural information processing systems, 27, 2014.
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorithmic framework for model-based deep reinforcement learning with theoretical guarantees. arXiv preprint arXiv: 2018.
Sridhar Mahadevan and Mauro Maggioni. Proto-value functions: A laplacian framework for learning representation and control in markov decision processes. Journal of Machine Learning Research, 8(10), 2007.
Stanislav Minsker. On some extensions of bernstein' 's inequality for self-adjoint operators. Statistics & Probubility Letters, 127:111-119 2017.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning, pp. 6961-6971. PMLR, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprins 1rXiv:1312.5602, 2013.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprins urXiv:2102.0700 2021.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 955), 2008
Ofir Nachum and Mengjiao Yang. Provable representation learning for imitation with contrastive fourier features. Advances in Neural Information Processing Systems, 34:30100-30122 2021.
Anusha Nagabandi, Gregory Kahn, Ronald Fearing, and Sergey Levine. Neural network dynam- ics for model-based deep reinforcement learning with model-free fine-tuning. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 7559-7566. IEEE, 2018.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprini / 03748, 2018.
Ian Osband and Benjamin Van Roy. Model-basee reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Vern I Paulsen and Mrinal Raghupathi. An introduction to the theory of reproducing kernel Hilbert spaces, volume 152. Cambridge university press, 2016.
Xue Bin Peng Marcin Andrychowicz, Wojeiech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international conference on robotics and automation (ICRA). pp. 3803-3810. IEEE, 2018
12

---

Published as a conference paper at ICLR 2023
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Shuang Qiu, Lingxiao Wang, Chenjia Bai, Zhuoran Yang, and Zhaoran Wang. Contrastive ucb: Prov- ably efficient contrastive self-supervised learning in online reinforcement learning. In International Conference Machine Learning, pp. 53168-18266 PMLR, 2022.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Tongzheng Ren, Tianjun Zhang, Lisa Lee, Joseph E Gonzalez, Dale Schuurmans, and Bo Dai. Spectral decomposition representation for reinforcement learning. arXiv preprint arXiv:2208. 09515, 2022a.
Tongzheng Ren, Tianjun Zhang, Csaba Szepesvári, and Bo Dai. A free lunch from the noise: Provable and practical exploration for representation learning. In Uncertainty Artificial Intelligence, pp- 1686-1696. PMLR, 2022b.
Frigyes Riesz and Béla Sz Nagy. Functional analysis. Courier Corporation, 2012.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.067777 2017.
Matthias W Seeger, Sham M Kakade, and Dean Foster. Information consistency of nonparametric gaussian process methods. IEEE Transactions on Information Theory, 54(5):2376-2382, 2008.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process opti-
mization the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pp. 1015-1022, 2010.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science Business Media, 2008.
Ingo Steinwart and Clint Scovel. Mercer's theorem on general domains: On the interaction between measures, kernels, and rkhss. Constructive Approximation, 35(3):363-417, 2012.
Ingo Steinwart, Don R Hush, Clint Scovel, et al. Optimal rates for regularized least squares regression. In COLT, pp. 79- 99999,,2220 2009.
Yuval Tassa, Tom Erez, and Emanuel Todorov. Synthesis and stabilization of complex behaviors through online trajectory optimization. In 2012 JEEE/RSJ International Conference Intelligent Robots and Systems, pp. 4906-4913. IEEE, 2012.
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, et al. Deepmind control suite. arXiv preprint 17Xiv:1807.00690 2018
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model based control. In 2012 JEEE/RSJ international conference on intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffferene learning with function approximation. Advances in neural information processing systems. 9, 1996.
Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline rl in low-rank mdps. In International Conference Learning Representations, 2022.
Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristiamini. Finite-time analysis of kemelised contextual bandits. In Uncertainty in Artificial Intelligence, pp. 654. Citeseer, 2013.
13

---

Published as a conference paper at ICLR 2023
Ruosong Wang. Russ R 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:6123-611 6135,,,6,421 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 reinforcement learning. arXiv preprint 1907vv0000.00000 2019.
Philipp Wu, Alejandro Escontrela, Danijar Hafner, Ken Goldberg, and Pieter Abbeel. Daydreamer: World models for physical robot learning. arXiv preprint arXiv:2206. 14176, 2022.
Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in rl: Learning representations with efficient approximations. arXiv preprint 10 2018.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kemells, and regret bound. In International Conference on Machine Learning, pp. 10746-10756. PMLR, 2020.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. Provably efficient
reinforcement learning with kernel and neural function approximations. Advances in Neural Information Processing Systems, 33:13903-1391, 2020.
Denis Yarats and Ilya Kostrikov. Soft actor-critic (sac) implementation in pytorch. https:// 2020.
github. com/ deni cctmm//ee.yyarrtttt/y.rrro.o
Denis Yarats, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. Reinforcement learning with prototypical representations. In International Conference on Machine Learning, pp. 11920-11931. PMLR, 2021.
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. In Conference Learning Theory, pp. 4473-4525. PMLR, 2021.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. arXiv preprint arXiv:2006. 10742, 2020.
Tianjun Zhang, Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making linear mdps practical via contrastive representation learning. In International Conference on Machine Learning, pp. 26447-26466 PMLR, 2022a.
Xuezhou Zhang, Yuda Song. Masatoshi Uchara, Mengdi Wang, Alekh Agarwal, and Wen Sun. Efficient reinforcement learning in block mdps: A model-free representation learning approach. In International Conference Machine Learning, pp. (6517-26547. PMLR, 2022b.
14

---

Published as a conference paper at ICLR 2023
A MORE RELATED WORK
Our method is also closely related to the model-based reinforcement learning. These methods maintain an estimation of the dynamics and reward from the data, and extract the optimal policy via planning modules. The major differences among these methods are in terms of i), model parameterization and leaming objectives, and ii), the approximated algorithms used for planning.
Specifically, Gaussian processes are exploited in (Deisenroth & Rasmussen, 2011). A stochastic deep dynamics with restricts Gaussian noise assumption widely used (Heess et al., 2015; Kurutach et al., 2018; Chua et al., 2018; Clavera et al., 2018; Nagabandi et al., 2018). Hafner et al. (2019a;b; 2020); Lee al. (2020) recently exploits recurrent latent state space model, but focused on Partially Observable MDP setting, which is beyond the scope of our paper. Different approximated planning algorithms, including Dyna-style, shooting, and policy search with backpropagation through time, have been tailored in these methods. Please refer to (Wang et al., 2019) for detailed discussion.
As we discussed in Section I, these algorithms did not balance the flexibility modeling and tractability in planning and exploration, which may lead to sub-optimal performances. While the proposed LV-Rep not only is more flcxible beyond Gaussian noise assumption, but also lead to provable and tractable learning, planning, and exploration, and thus, achieving better empirical performances.
B ALGORIHTMS AND THEORETICAL ANALYSIS FOR OFFLINE EXPLOITATION
Algorithm 2 Offline Exploitation with LV-Rep
1: Input: Model class P = [[p(2]s, a), p(s' [=)], Q = (1(2|s, a, s')} Offline Dataset Dn--
2: Learn the latent variable model [[=|s,0) a) with D, via maximizing the ELBO defined in equation and obtain the learned mode! T.
3: Set the exploitation penalty b(s, a) as equation 7.
4: Obtain policy â = arg max, V T
5: Return म.
In this section, we show the algorithms for offline exploitation. For offline exploitation, we have the access to offline dataset, which we assume is collected from the stationary distribution of the fixed behavior policy Ta, which we will denote as p. And we are not allowed to interact with the environments to collect new data. The only difference between the algorithms for offline exploitation and online exploration is that, we do not have access to the new data from the environment, we cannot further explore the state-action pair that the offline dataset do not cover. Hence, we need to penalize the visitation to the unseen state action pair to avoid the risky behavior.
C IMPLEMENTATION DETAILS
Our algorithm is implemented using Pytorch. For DeepMind control, we open source implementation as our SAC baseline (Yarats & Kostrikov, 2020). As discussed in Section 6. we find it is beneficial to have more updates for the latent variable model than critic in practice. We use a parameter catporr--ddaat--ppree
that decides how many updates are performed for the latent variable model at each training step. For all Mujoco and DeepMind Control experiments, we tune this parameter from {1, 3, 5, 10, 20} and report the best result. Finally, in Table 3, we list all other hyperparameters and network architecture we use for our experiments.
For evaluation in Mujoco, in each evaluation (every 5K steps) we test our algorithm for 10 episodes. We average the results over the last 4 evaluations and 4 random seeds. For Dreamer and Proto-RL. we change their network from CNN to 3-layer MLP and disable the image data augmentation part (since we test on the state space). We tune some of their hyperparameters (e.g., exploration steps in Rr) and report the best number across our runs.
15

---

Published as a conference paper at ICLR 2023
Table 3: Hyperparameters used for L.VRRep in all the environments in MuJoCo and DM Control Suite.
Hyperparameter Value
Actor Ir
0.0003
Model Ir
0.0003
Actor Network Size (MuJoCo)
(256, 256)
Actor Network Size (DM Control)
(1024, 1024)
LV-Rep Feature Embedding Dim (MuloCo)
LV-Rep Feature Embedding Dim (DM Control)
1024
ERP Embedding Network Size (DM Control)
(1024, 1024, 1024)
Critic Network Size (MuJoCo)
(256, 256, 1)
Critic Network Size (DM Control)
(1024, 1024, 1)
Discount
0.99
Critic Target Update Tau
0.005
Latent Variable Target Updatc Tau
0.005
Batch Size
256
D TECHNICAL BACKGROUNDS
In this section, we introduce several important concepts from functional analysis that will be repeat- edly used in our theoretical analysis. We start from the concept of the R-vector space.
Definition 2 (R-vector space (Steinwart & Christmann, 2008)), An Revector space is defined as triple (E, )) where E non-emply sel, E E and .R E - E satisfies the
following properties:
Vx,U, E (x v) +== (y+
Vz, E, x +
E an element E F, such that Vx Fr, x + 0 x.
Vx E, 3 E, such that x + (-x) = 0.
Va, IR, E, (a3) x = (B.x).
Vx E E.1.x=a.
Ya, E. B) x == a x.
Ya VR a (x + = a + a
The denotes the scalar multiplication will be omitted if there will be confusion.
Definition (Norm and Banach Space (Steinwart & Christmann, 2008)). Let E be a R-vector space. E [0, oo) a norm on E if
A map
||||| 0 + r O.
. Va E R. x E E, || |||=[]]
Nx. E F., I|r vll S ||-||| + ||v||-
In this case, the pair (F, II) called a Banach space, and we use F. to denote the Banach space for simplicity if there will be no confusion.
Definition (Bounded Linear Operator (Steinwart Christmann, 2008)). Let E and be two Banach spaces. A map S E F is bounded linear operator if
Vz, De,yEL S1 E, + y) = Sx + Sy.
Ya E RR E, S(ax) = a(Sx).
= =0 0.
Furthermore, S satisfies the following properties
16

---

Published as a conference paper at ICLR 2023
3c [0, ool, such that Vz E E, ||S c||a||e.
Note that, all of the bounded linear operator itself can define an R-vector space, and we can define an operator norm of ||S||op Supre8g [[ where Bg {I E E: || [1} is the unit ball of E.
Definition 5 (Compact Operator (Steinwart & Christmann, 2008)), A bounded linear operator S: + F is compact if the closure of SBg is compact in F.
Definition (Inner Product and Hilbert Space (Steinwart & Christmann, 2008)), map (:)
H x H + R on a Revector space is an inner product if
vn,y, E H. (x y. 2) (xr (y, 2).
Va E a, y H. (ocr, v) axx, v)-
Vx,y E H. (x. 1) = (y, x))
Vx E H. (x) 2 O. and (I, =
If the norm induced by the inner product || =- / (xr, xt) is complete, the pair (H, (5--)) is called Hilbert spuce. We sometimes use H denote the Hilbert space and use (-- distinguish between different imner products. Note that, the inner product satisfies the following Cauchy-Schan Schwartz inequality:
Va,y E H, 1(,, vl & ||<||x|lv||æx
Definition 7 ((doift)Adjoint Operator (Steinwart & Christmann, 2008)). Let H1 and H₂ be two Hilbert spaces, For the operator $ : Hi + H2, the adjoint operator S H2 - H2 is defined by Vz E H1,y E H2. VHH, = (x. U'Ha.
Furthermore, S is a self-adjoint operator, S Hi + H1, and
Var y Hi; (Sx, u) = (x, Sy)H. For self-adjoint operator S, if (Sx.x) x) 2
called positive semi-definite operator, and if (Sx, .) > 0, S is called a positive definite operator.
Remark 5. Note that, the definition the adjoint operator can be generalized to Banach spaces. But adjoint operators for Hilbert spaces are sufficient for our purposes. So omit the definition of the adjoint operators on Banach spaces.
Definition (Orthonormal System and Orthonormal Basis (Steinwart & Christmann, 2008)). For the Hilbert space H. the family {er)ier,e, E H is an orthonormal system if (e;, ei) = 1, and (c), [ if f Furthermore, if the closure of the linear span of {eihier equals to H, is an orthonormal basis. Note that, each Hilbert space H has an orthonormal basis, and if H. is separable, H. has countable orthonormal basis. Furthermore, Vx E H, we have
E( SET
Theorem 2 (Spectral Theorem (Steinwart & Christmann, 2008)). Let H be Hilbert space and T: H. - is compact and self-adjoint. Then their exists at most countable {T)(T))er converging to such that (yr(T) Z (P2(T)) 2 0 and orthonormal system {esliet, such that Va E H, Tx Tx= Tx=Eu( (.) ei)He
Sel
Here (u((T))ir can be viewed as the set of rigen-value of as Te, (T))))
Definition 9 (Trace and Trace class (Steinwart & Christmann, 2008)), For compact and self-adjoint operator T. if E (T") < say T is nuclear of trace class, and define the nuclear norm and the trace as:
|T-- Tr(T) = Σ (T).
KET
Definition 10 (Hilbert-Schmidt Operator (Steinwart & Christmann, 2008)). Let Hi, H2 be two Hilbert spaces. An operator S: Hi H2 is SilbbertSSchidt if
1/2
||5 |H1
Σ
See 1
00,
17

---

Published as a conference paper at ICLR 2023
where her is arbitrary orthonormal basis of H2. Furthermore, the set of Fillbert-chhiie operators defined on H. + HH. where H. a Hilbert space indeed a Hilbert space with the following inner product:
(Ti, HS)
((eee, T2e3) T2,22 HS(H),
iE1
where festrer is an arbitrary orthonormal basis o..
Definition 11 (p) space). Let (X A. μ)) be measure space. The (2)) space is defined as the Hilbert space consists of square-integrable function with respect to μs with inner product
(S, (S.9) = f Igdp,
and the norm
lIflles()) = (.PPa 1/2
Throughout the paper, μa is specified as the Lebesgue measure for continuous X and the counting represent f as sequence [f())) norm is identical to the l inner product and
measure for discrete X. Specifically, when X is discrete, and the corresponding L2(p) inner product and L2((s) (² norm, which is defined
If (EP())) 1/2
(f = = f())(())
that is closely related to the inner product and norm of the Euclidean space.
Definition 12 (Kernel and Reproducing Kernel Hilbert Space (RKHS) (Aronszajn, 1950; Paulsen & Raghupathi, 2016)). function &o X x X -> R is a kernel on non-empty set X, if there exists a Hilbert space H and a feature map X H. such that Vx, x' E X, b(x,x') (o(x), 6(x))) Furthermore, vn 2 1, {a: (EEN C R and mulually distinct (rihee]
ΣΣ a;a;k(11, 2 O, dE(m)
the kernel k is said to be positive semi-definite. And if the inequality is strict, the kernel ls is said to be positive definite.
Given the kernel k, the Hilbert space Hy consists of R-valued function on non-empty set X is said to be a reproducing kernel Hilbert space associated with l if the following two conditions hold:
Vz X, k(x,-) Hk.
*
RReproducing Property: Vx E X, E Hu, H(x) ((,k((,)))
Here k is also called the reproducing kernel of Hy. The RKHS norm of f H4, is defined as || M/, = VU,,f)
Some of the well-known kernels include:
Linear Kernel: k(z, x') = x T x', where x, x' Rd; Polynomial Kernel: k(x,x') ) (1 + TTx x')", where x, x' Rd. n N
exp (- ||---|| where x, E Rdd a > 0 is the scale Gaussian Kernel: k(xxx²)
parameter.
Matérn Kernel: k(xxx') = r" By where x, x' E Rd. v is the smoothness parameter, 1 > 0 is the scale parameter, v2u - r'11, [(.) is the Gamma function and B-(-) the modified Bessel function of the second kind.
Theorem 3 (Mercer's Theorem (Riesz & Nagy, 2012; Steinwart & Scovel, 2012)). Let (X, A, p)) be measure space with compact support X and strictly positive Borel measure k is continuous positive definite kernel defined on X x X. Then there exists at most countable {Jiheer with μi 2 #2 2 ... > O and (eiftel where {eilier is the set of orthonormal basis of L2(H), such that
Yx X, (x,,x') Σ (e,(())e,(a'), iel
18

---

Published as a conference paper at ICLR 2023
where the convergence is absolute and uniform.
Remark 6 (Spectral Characterization RKHS). With the representer property, we know that
Σ prex(r)es = k( Hg. iE!
Note that, for 3-finite spectrum, can choose I such that μ4 > 0. If we define the inner product
a;b:
Σ a.)(()), Σ
b.ea(t)
Σ
As
Hk
iET
then we have the reproducing property
Σ
(,,(();
Σ a,)e))
Σ
(rer())e;())
= -age((x)
(z)(()).
IET
iET
iET
With the spectral characterization, we know that
Eier ot
Σ
()se(()
Hence, we know vf Hr. f Hh
YES
14g
141
111
L2(H). Furthermore, note that
x(I,x)=
Σ (ee(()));))), Σ (ee(()))s()) iES
Σ (e)(
IE1
iE!
Hence,
Σ-= ( Eme
Σm=
k(æ, x)dp.
NEl
Sel
The following Hilbert-Schhie integral operator is useful in analysis:
Ty : L2(H) L2(p), Tef Tef= = - k(x, x') (f()))))
xx
Obviously, Ti is self-adjoint. Use the fact that b(x,x')= = = Eier (z)e(z))((1)) we know The: p4sss which means e; is the eigenfunction of T4 with the corresponding eigenvalue p4.
With the spectral characterization of T&. we can define the power operator Ta, by
T f L2(1) + L2(n), TES- = Σ Eu (eee)e
REI
And these power operators are all self-adjoint. Note that, Ilf = Tf fggnn) Throughout the paper, we work on the (2() space, and all of the operators are defined on L2(14) + L2(u). As Hys C. L2 (H), all of these operators can also operator the elements from H4.
The power RKHS induced by the following kernel will helpful in our analysis:
Va, x' E X, k(xx x') Σ (())).)
iel
And it is straightforward to see || - Dislo) which will be useful in the proof.
Definition 13 (Kernel with Random Feature Representation). A kernel k X X - R is said to have a random feature representation if there exists a function vp : X x E + and a probability measure P over E such that
k(x,I')= - (
We then show that, Hl coincides with the following TR-valued function space
{: f(z)
L2
with the inner product defined as (f,9) Hr = (())(())P(E)) Note that, Te(x, (b::: E). Hence, it is straightforward to show that Vx E X, 1(xx.)) )) E H4. Furthermore, we have
f(x) F(EW(I;;
(())k(z,-)dPP)) (f, -))
19

---

Published as a conference paper at ICLR 2023
which shows the reproducing property. As result, obtain equivalent representation of the RKHS Hg, which means ff E HH,, we can obtain a random feature representation.
Examples of such kernel includes the Gaussian kernel and the Matérn kernel. See Rahimi & Recht (2007); Dai et al. (2014); Choromanski et al. (2018) for the details.
Definition 14 (s-net and e-covering number and i-th (dyadic) entropy number (Steinwart & Christ- mann, 2008)), Let (T,d) be a metric space. d(s, t) I e. Furthermore, the E-covering number (T, d) is defined as the minimum cardinality of the S-net for under metric d, and the i-th entropy number e, (T, d) is the minimum that there exists an cover of cardinality 2
T is an E-net for > 0, if E T, 3s E S, such that
E
MAIN PROOF
E.1 TECHNICAL CONDITIONS
Assumption (Regularity Conditions for Kernel). Z is compact metric space with the Lebesgue measure μ if Z is contintous, and Jz ((2,2)dg $
Remark Assumption is mainly for the ease of presentation. The assumption that compact when Z is continuous can be relaxed to Z is general domain but requires much more involved techniques from e.g. Steinwart & Scovel (2012). Furthermore, with Mercer's theorem (see Theorem and Remark 6 for the details), M1 < 1, and || < |l, without any other absolute constant, that can keep the eventual to S2 k(2, 2)dp
know Eier 14, J& ==,,=)dd z)d 1, As Vi p4 0, know
result clean. We relax the assumption fz k(2,2)du constant 1, at the cost of additional terms at most poly(c) in the sample complexity.
for some positive
Assumption 4 (Eigendecay Conditions for Kernel). For the reproducing kernel k we assume ps. the i-th eigenvalue of the operator Tg (2) L2(1), T&J Jz f(z')h(z, 2 d')dd)("), satisfies one of the following conditions:
8-finite spectrum: = O. Vi 3, where B is positive integer.
3-polynomial decay: μ4 S - where Co is an absolute constant and 3 1.
B-exponential decay: p S C1 C1ex((C2zt) where C1 and C2 are absolute constants and 0>0.
For ease of presentation, we use Opoly to denote constants appeared in the analysis of 3-polynomial decay that only depends on Co and 3, and Ceep to denote constants appeared in the analysis of 3-exponential decay that only depends on C₁ O2 and B. Both of them can be varied step by step.
Remark 8. We remark that, most of the existing kernels satisfy one of these cigendecay conditions. Specifically, as discussed in Seeger al. (2008); Yang al. (2020), the linear kernel and the polynomial kernel satisfy the 9-finite spectrum condition, the Matérn kernel satisfies the 3-polynomial decay and the Gaussian kernel satisfies the 3-exponential decay. Furthermore, for discrete 2, we can directly observe that it corresponds to the case of f-finite spectrum with 3 < /2
E.2 PROOF FOR THE ONLINE SETTING
Theorem 4 (PAC Guarantee for Online Exploration, Formal). If we choose the bonus d, (s, a) as: (n a) min { 11 ())l, .2
where
Sm.p.: L2(p) + L2(H), Inpp.
Σ
(2 az)d az) XT=
(sLa)))D
ll IIflle. = / tala) self adjoint operator E, for different eigendecay conditions is given by:
8-finite spectrum: X 0 N log(N(Pl/8))
8-polynomial decay: X O(Gpoly (1/(119) Log(NNPP///)
20

---

Published as a conference paper at ICLR 2023
B-exponential decay: À (lCexp(log N) 1og((N/1//0)
and On, = V
then with probability at least - 6, After interacting with the environments for episodes where
CB (1g(1P)/6)
1 log(1P1/) (1-7)-
)) for B-finite spectrum;
N
log"
(1-7)-8"
N
θ
Cpoly
(A (1-7)92
lo2
3/2
(01/11)g((P110))) (1-y)+s
for 8-polynomial de-
cay;
Caxp C/AA/ (P/8)
(Cld)" 1og(1116)) for B-exponential decay; (1-7) (1-))-)
log
(1-7)
we can obtain an s-optimal policy with probability at least - 6.
Notation
Following the notation of Uchara et al. (2022), we define
pa(s)
and with slight abuse of notation, we overload the above notation and define
Pa pm(8, == Σ (s,
Furthermore, we define (s") as the marginal distribution of s' for the following joint distribution
(s, a, s') ~ Pn(s) U(A) T Ts' (s'ls,
Finally, we define the following operators in the space of L2(u) + L2(x): Enp xU(A), =n U(A) (((s,a) (s, a)] + +T==
Σ Pp = (s,)),p [d(s,a)o (s, (s,
XT=
Note that, by the spectral theorem, if [irI|T ||T-1/20 Lz(u) S oo for a' E L2(1),, we have the following Cauchy-Schwartz inequality for weighted (2( norm: Vo E L2(u),
(x,, a') Le(u) = /2)
( T
S [| || (2(W))
Lz(H)
Lemma 5 (One Step Back Inequality for the Learned Model), Assume S x A - R such that
|| S. B, then conditioning on the event that the following MLE generalization bound holds:
(T(.sa) (issa)-T"(sssoi (s, S Sn,
Vn, have
B(oa))ad [g(s,a)]
<n SyBaaayydy (111, ()) E
ml/ABB milll) (g2(s, + XB2C nB²C.
+ V1 71 A Aerea 1
Proof. We start from the following equality:
E( [g(8, a)] = 71 (2,))= Sw (1) (1 (=
which is obtained by the property of the stationary distribution. For the second term, with Jensen's inequality and an importance sampling step, we have that
7) E Bard
orx( ()(((,,))
Va o
21

---

Published as a conference paper at ICLR 2023
Now consider the first term. With Stuchy-Schward inequality of L2(p) inner product, we have that
7/8 (3,0))a (+ (1)
Σ
aEd
L2(a)
E E [mdss))a((bblllss.o
SyBaaa (px((13, (o sncaiin
REA
L2(1), 2a
Note that
1 Σ (u(s))a(ass)s((ss)) a)ds REA
La(u) La( xulA)))
2 [o(s,a))] =nD()) (1)))) +
/ Σ Pa (n(ss)rlaasgg(seddd
AEA
He
EnBgmpn (nll(()) (BeNT- [0(5, m))} AB + GB
<nErspnn (A) ( + AB²C nB
(13.0) 9 (8, =n|_A[Esmpph_a-a (-M()) [o" as. +B Substitute back, we obtain the desired result.
<n| <n|AABB Simp
+ nB
Lemma 6 (One Step Back Inequality for the True Model), Assume 9 S A - R such that lIglloo S B, then
(( la(a,a))
(1 (o²(s, BB
B2C
+ (
Proof. By the property of the stationary distribution, we have
(s,a) (g(s, a}] (B, ,-* (-13,""(1111))) (1100), a)] + (1 - By (1) a)).
(10)
For the second term, we still use the following upper bound:
(1 B) l) s,, a)] V( (1-110 -
For the first term, with the Cauchy-Schwand Schwartz inequality, we have
BB WTT (1)
pº ('(1,,,), a) / Σ p² (s)))((as))(ss))dd
aEA
L2(#)
SyBasaaya (-6, 1 E/ EI
aed
L2(N) E?
Note that
1 Σ p" ( a)ds
aeA
=nBigaaypp (BarT (((s))))] + +2
(mal))))(assalsss aEA
Σ
Hx
ST (s,)) + ABCC
<n|A Pp. < [g) XB²C
22

---

Published as a conference paper at ICLR 2023
n2|A||
aM [g a)] + ABCC
Substitute back, we obtain the desired result.
Lemma 7 (Almost Optimism at the Initial Distribution). Consider an episode n E [N), if we set Sn = θ [P/()))1/))) (such that the MLE generalization bound holds by Lemma 16), X for different
eigendecay condition as follows:
3-finite spectrum: (Bllog N + log(([(1/66)
B P-oolnomiill decay: X = D[Cpoly-VV/(01 +
B-exponential decay:
(Ceexp (log N) + Log(NN)1//8)
and an
log(n 0 11 log PI/8) XC).
the following events hold with probability at least
1 6:
LA|Gn
Vn [N], VT,
VT Ta.rth - VF.,++ 2 -V (1 (1-7)3-
Proof. With Lemma 17 and a union bound over P, we know using the chosen X, Vf, E P, with probability at least 1 5,
11 (l)) @ (1b
With Lemma 18, we have that (1-
V Turrth. - V.T...)
= =B(ss))dy
(n) 7BB (s)] ((E(())))))) [VG (5']
> (s,)) An
min {an llān (-1s, a) (l0 xm 22 (B (V
- -yB [VF-, [V'],
Denote (s TV(T (s' (s'(s, a). F,, (s') a)) with fl S 2. with Hölder's inequality, we have that
[a((s
B(ea)aay ( [5), Er- [V,,('')]]] E(s.ajnd7
1 1-7
With Lemma 5, we have that
(s)
[((.))=d 7m
ny? LA Eenpl a-)((A)
(82 a)l 71-
4x²²0 (1 71-
+ 4nv2Cn
<E (3,0)--d5 (-1a, (itlssa))lln ())llss (n)) (onAaa
(1 7)2
+ an a))
42yPC
472n5a
AAlsn
<Bpaa-ab, (-Is, a))l (-) on ku
(1 72
+
(1 7)²
+
(1 7)-
+
V 1-7
Note that, we set oa such that
ny LAI
42y20 (1 (1-7)²
+ Anr26n S an:
+
7)²
(1 7)2
which concludes the proof.
Lemma 8 (Regret). With probability at least 1 8, have that
23

---

Published as a conference paper at ICLR 2023
For B-finite spectrum, we have
/ LAP 33/2|AAlVON CAN log (N111/8)
VI Vi
(1 7)²
For B-polynomial decay, we have
Opoly VCJAIN M8क log (og(N1))/))
V
T
(1-7)²
For B-exponential decay, we huve
N
CixplAlVN(loon N)
3428 log( N PI/0)
T
T
(1 7)
==
Proof.
With Lemma and Lemma 18, we have that
V
T
Alla
SVz' Tnn
+
Vi
(1 (1-733
AAlsn
<v Pni
+
V
(1 7)3
ViJa,y
1 E (sa))dn (n((,a) a) (e FT. rn, (6)1-~BB (611,)) (V Fni (d)]] +
LA|Go
1-7
(1-
Applying Lemma 6 and note that b, O(1,, we have that B( [b,(s, a)]
< {B(c0)) min { an 11 a)) a))l x...)... 2]]
SE <Z lpp" (-13, aلاا= p. mnl a |I a)ll a)) xmann,.
+ +
(1- Bam [1,n a)ll a)ll) Spieacation sp
Note that,
n.Beopnanell [| (18,, a)l La(a).
=Tr nE, (NEsppnar(LA)) [Dm (118, (118
(nEsupn (pm(-1s, (1) + +
=Tr (EEspp T 12 pm (-s,
(nEesppann((A) T 1 (11s, T + M1) )r)
<log det I n X
(B
Th 1/2
/1 (- a) an(
where the first equality is due to the definition of Hilbert-Schmidf inner product and the expecta- tion operator is linear operator, the second equality is due to the fact that Tr(A(A + B)-1)
Tr (BB (B-1/2AB-1/23 112) (I
(I+ -) for positive semi-definite operator A and posi- tive definite operator B, and the last inequality is due to the fact that if has the eigensystem {us ei). then A(A A1)-1 has the eigensystem { ( e.). and
log(1 + x). Here det denotes the Fredholm determinant. Note that, if x BHG T BHN, and know Ex-ph [T (-Is,, a)T pa(-Is, /) is in the trace class and the Fredholm determinant is well-defined. Invoking Lemma 19, we have that
For --finite spectrum, 0 log N (N(P///)))) have n/X O(n) n log det [ "BampaarelAA 1/2 1/2 (n(sss, T)T TT (... aT /²) = lolon),
24

---

Published as a conference paper at ICLR 2023
which means
B(s,a) A log(n) + Ay2C E (+3, -)اا) Propp
(1 7) Al,, log(n))
For 3-polynomial decay, À OCCpoly + log((N and n S N, we have
n/X = O (Coolyn and
log det (1 +
n2 18 X (ampa) (n pn(+ss,) ( = =0 (Cpory 2otis log(n))
This leads to
E (a (n((,a)) SV plalppa कां logn + Xy2C Biz.ayaana (-13 (),,))1x=1
+Va- -Vd-3)ld/(popy 24 log(n)a
For B-exponential decay, as X = (Coxp1)) and
we have n/A
log det (1 +
n2 E (ut
(n a) () 0 (Cexp(logn))1 +1188)
X
This leads to
E (s.a)-di (s, a)] SV 7 (lgg) + Xy2C http:///)))////oo/-//--/------rr B(zay-at l1p" (11, a) x pn.
Cexp (logn) 1+// (logg))1188)00
n
For the remaining terms, denote fs( = (s a), (s's,,,,, (n')sssss (T()))) with Iffullo S 2. With Hölder's inequality, we have
E (saa)=aj [rr,
S B (3 VEa Fnrrtbon (d)]] V Virteo, (s)) - -r
fu(s, a)
1
With Lemma 6, we have that
fa(ssa) a) 1 1-77
ny my|AAE Emm ((-(A) (f((s a)]
4xy20
B(eaa)=d7a
<B <Bg.a)az7. (1awaa)l F.
71-
(1 71
| (
+
4Ny2C
AA
<B( (1) po.pt
(1 7)2
(1 7)²
1-7
Alls 1-7
Ean 1|p" (.33, (.
Combine with the previous results and take the dominating terms out, we have that
For f-nintt spectrum,
V
V
AAaa log n + Xy²C - Bez,ay~azo 1pp (-33, a) x
Ala B logn n (1 7)n
LA
V (1 (1-7)3'
For 9-polynomial decay,
VTT.-
25

---

Published as a conference paper at ICLR 2023
Vol ylAlC a 50433 logn + C2 Baza)da (1)(((3,))
Alopo 11 ((ो.) log n
|A|Gn
1-7
(1 (1-7)3'
For 8-exponential decay,
VT-
7
(ll + ATP2 Biaaayd; (1"(
AlCoxp o (logn)
LA
(1-7)n
V (1 (1-
Finally, with Sauchy-Schwarlee inequality, we have
Σ Bazayaaze |p"(),, (L_
N
Σ B3aaya (p'
Sp.p. D ('(3, 12(1))
Note that
E B(z (p" (-1,, a), p. (-13,))) L2(n)
=E =B(gaa=dfn
(p" (-13,, (nE 1p"
+ + p0 p²(13,,
(z(H)
1/2 p" (-1,,)), (nl(ssaavpp [TL2 (1ss, a) T / + +11)
T/ T// 20 (-13,
B(za))afi
L2(m)
T2// p² (-13,a)²* (-13, ()
E B3
=Tr ("Eaas)oon
[T (-1s,, a.p's Tx//2] +
S
log det
("BBeaaapp (T p (1sss (11 p1
T 1/2
+ +1))
- --- E(s.a)an..
[ 2 (-|s, a)p (-ss,a)pp(((ss)) T
+1)
logg det
where in the last inequality, we use the fact that log (X) is concave with positive definite operators X and dlog det(X) dX
Telescoping and applying Lemma 19, we have that:
For B-finite spectrum: as N/X O(N), we have
(3a (p'(11, E-1 pp p" ()) Lo(K) 0133 N).
For 3-polynomial decay: as À = OCppoly N 1/(4+3) + +log(A) (og(N(P1/6)) we have N/A O (Cpoly NoolyyNi4 N
and
N
E Bazayaaa (1,,) E- p-(3,))(((13))) Lic(u) =0 (Cpaly NN anttr log N
1=1
* For 8-exponential decay:
Σ Ba (1,{) P (-11,, Lz(n) n=1
=0 (log NY1+1/8)
Hence, after we substitute on and X back and take the dominating term out, conclude that:
26

---

Published as a conference paper at ICLR 2023
For 3-finite spectrum, we have
N
/// NN /CN log PP/0))
x
(1-
==1
For 6-polynomial decay, we have
Apoty-A|NN rte log N /Cloog(NPP///
V
VIT X
(1 y1-
For B-exponential decay, we have
T VT CexpLAly CN (og(NV/P//)(llog
3+28
(1 7)-
This finishes the proof.
Theorem 9 (PAC Guarantee for Online Setting). After interucting with the environments for N episodes where
C3 LAI log PP/6)) N =
log
(C0" Al 1og(11/88) for 8-finite spectrum;
71-7)"²"
(1-7)²c²
204 3-1
N = +
Cpoly
(IICC1O(((118)) (1-7)² log
3/2
for B-polynomial
(1-7)ag
decay;
N
( ConpC1a12 (og((Pl/))
log
8438
(CRA) (1-7)-0*
)) for B-exponential decay;
(1 (1-7)=22
we can obtain an e-optimal policy with high probability.
Note that, log log x = O(log x). We consider the case with different cigendecay conditions separately.
Proof.
For 3-finite spectrum, by taking the output policy the uniform policy over {Te]ve(n)) can obtain a policy with the sub-optimality gap
33/2 LAI log N /Clog(NNP)//
(1 VN
Take N 0
LaP 188 (1-3)"e"
log
CC8 (oR((P/A) we can see the sub-optimality
(1 (1-7)*e"
gap smaller than e, which finishes the proof for 3-finite spectrum.
For 8-polynomial decay, by taking the output policy as the uniform policy over { (e])) obtain policy with the sub-optimality gap
Cpoly N - log N C' Coolo((N)) (|
(1 71
20143) 8-1
[AI/CloR([P]]] (1)8)
3/2 (VC) [VCAAloo (1-y)²
Take N
Cpoly
(1-7)'8
we can see
the sub-optimality gap is smaller than which finishes the proof for B-exponential decay.
For B-exponential decay, by taking the output policy the uniform policy over (Tehe we can obtain a policy with the sub-optimality gap
Coxp Al log( (NTP) N) 3+24 2B
- V
27

---

Published as a conference paper at ICLR 2023
Take N θ CCmpCl/Ai log [P)/ (1-7)te²
8130
CCA (P
log
we can see the sub-
(1 (1-7)422
optimality gap smaller than e, which finishes the proof for 3-exponential decay.
As result, we finish the proof for the PAC guarantee.
E.3 PROOF FOR THE OFFLINE SETTING
Similar to the online exploration case, we can obtain the upper bound of the statistical error for म, which is stated in the following:
Theorem 10 (PAC Guarantee for Offline Exploitation). Define == maxo, Tb (als). and
((s.)) (p'(-1s,)) a), x²) L2(N)
C
sup #E (2())) ((aaa)= (1ss (-1s, a), x)) Lo((H)
If the penalty and its corresponding parameters are identical to the bonus we define in Theorem 4, then with probability at least 6. any competitor policy т including non-Markovian history-dependen policy, we have
For B-finite spectrum, we have
w//3/2 log (1 (1-
CC (P/(())/))
V T
V
For B-polynomial decay, have
Opolywm 20143) log ny CC; log (PI/5)
VT
(1 (1-
For B-exponential decay, we have
Clxpw(logg) 2 7)
CO2 log (P)
VF-,r
V
We start by showing that C can be viewed as measure of the offline data quality, which can be demonstrated by the following lemma, that was first introduced in Chang et al. (2021):
Lemma 11 (Distribution Shift Lemma). For any positive definite operator T2((1)) I2(1s), we have that
(s (p" (-1s,a),
a), Ap" Ap" (1s, C) ()s, (-|s, a)) 1260)-
Proof. We denote the eigendecomposition of A as = UEU where for, us} is the eigensystem of A. Then have
B( (p' (11s,))) Ap" (-|s, a2) (2(m)
Σ
og (B (u, p" (.15, a) }/,(()
iel
<C
o; B (e (-18, )L
SET
C B( (118, (118, Ap" (-18, a)) L2(0)
which finishes the proof.
We also define the E.s L2( + L2(u):
Ep.o == (s a)o (s, AT
where p is the stationary distribution of TT.
Lemma 12 (One Step Back Inequality for the Learned Model in Offline Setting). Assume S A P, such that l|g]loc _ B. Then conditioning on the following generalization bound:
B(s.))<pTT(S (s) T a)l < C.
28

---

Published as a conference paper at ICLR 2023
we have that V'
E dy (((ssaa)] a)]
I (3, Ilp(- s,
L2(a)) a V (nunB(aa)> (s)(s.)) + AB2C + tBB2s
+ (
Proof. We still start from the following inequality:
((s,a)=dy [s(s, a)] " .0 s~B. (-1..)) () a)] + (1 - Ee aende 1- a)].
For the second term, with Jensen's inequality and an importance sampling step. we have that
a)] v(1 ()) a)}-
an do
For the first term, with Cauchy-Schward Schwartz inequality of L2(4) inner product, we have that T( (0 (s)
y yB -
p(-1,,a),
Σ ((ss))s(ass
La(H)
By (6(-15, (1
Σ aEA
Note that
V. Σ plss)a(als
AEA
L2()),D..
}) ?
/ Σ
=nE B
+ >
pls))a(alsso(sso)d
AEA
He
<nB(s,0)m BBNT (1r0)
(a(s a)]} 011²
AB nB²
<nBizaa~
10² a)) XB C nB²r
SnwEEs,a) { (1))) (s, a]]}
XBCC +nB²3
nw E 112 (s2 (s, a)] + CBCC+nll
Substitute back, we have the desired result.
Lemma 13 (One Step Back Inequality for the True Model in Offline Setting). Assume SSx A + R. such that |1 B. Then we have that Va.
((aa))aaz [g(s, a)
S Sy 11p (-13, 2) E, ( V nwnlBBss.a (g2(s (13pE(ssa))pp((((00))) B²C
+ V - ()
Proof. The proof for this lemma is nearly identical to the previous lemma, and we omit it for simplicity.
Lemma 14 (Almost Pessimism at the Initial Distribution). If we 2 different eigendecay condition as follows:
(log( pl:a)) ). for
3-finite spectrum: X = 1o,l log((P(/5))
B-polynomial decay: X ( 1/(++/) + log((P)/)))
B-exponential decay: (Coopp (log 1/8 log((P)/5))
29

---

Published as a conference paper at ICLR 2023
and a = (12 / wlog(( (P/66) ( + Xy²C).
the following events hold with probability at least 1
WC
VT,
V T.r-b
Vi- S V (1-
Proof. Note that, with the proof of Lemma 17 and a union bound over P (but not over n), we know using the chosen X, Vी E P, with probability at least 8,
[1p(1ss, a) 12 θ (18((11s. a) (200)))))))))))))
With Lemma 18, have that
(1-7)
[ Pir- V
b(s,a) + 7 (( ( (e [VT (s')]
(s,0)
(B( min {a (1ć(-1s. a) a))l 2) + +.Bp(s))a))) [VT (5')]
(s [VF [+(]]
Denote (8, TV a), T a)), we know 11/1 S 2. With Hölder's inequality, we can obtain that
(s,,a)
E (T [V (5') (o) [V') S (s.))dd
1 1-
With Lemma 12, we have that
f(s,a)
B(o,a)nd3
1
nwr ? (f2
4X-2C (1 7)2
4n725
< <B(zaaaay |5(-13, ()ll
+ (1 71-
(1 1 7)2
+ WE (f
1-9
2 7)2
4X72C (1-
An72C
wc
BBaayaa |0(-13, 2) 2,(
(1 (1-
+
V
With the choice of can conclude the proof.
Theorem 15 (PAC Guarantee for Offline Setting). With probability least 1 5, for any competitor policy n including non Markovann history-dependen policy, we have
For B-finite spectrum, we have
w/33/210g /CC log((P1/6)
V
V
(1 71
For B-polynomial decay, have
V Opolylmait 20143) log n CC2 log (P1/5)
V
(1 (1-
For B-exponential decay, we have
(oxpw(logn)
2138 7)2
CC* log /0)
VF- V
Proof.
With Lemma 14 and Lemma 18, have that V V
wc
SVT
Tr,r V + V (1 733
30

---

Published as a conference paper at ICLR 2023
wc
<VT Vi D + V (1 71
1
(x.)) b(s, a) + TBT (s)lsa)) [s'] - (o [V [6)],
ws
+
(1- ((1-
As = (1), with Lemma 13, we have that E (s,a)aa [b(s,a]
< min { a (lp((-ss, a) a) .23]
E (3,))au
1|" (1" ( V y (srnaup
|1((11s (لl + 2222
||0(-1s, (1=
a))l
With the reasoning similar to the proof in Lemma 8, we have that
For 3-finite spectrum,
(G)))~ (illiass) O (8logg log
which leads
((s,a)=d7, [b(s, a)l SB IIp (-33, (13,,
VwyBaa log + Xy20
(1 7) 1og
n
For 8-polynomial decay,
(ssa)>> (1(-)ss | O (Cpalynxtioo logn).
which leads
E
(a.a) [b(s, a)) S (z.a)aaa 1|p" (-13, (1) ppp
VunCpoly zii logn + 22
+ (1 - (1-7)wOpolyo' +20t0 logn. n.
For B-exponential decay,
E Ess,a)~p ( =0 =0
(Cxx)(logg))
which leads to E (s,ajad,, [b(s, a)) SBaraaydag 1|03 (1 pp (log) + Xr²C
(1 - w)waa>aaaaa (log 1) 1-1/3
+
Furthermore, denote f(s, = TV) a)), we have II < 2. With Hölder's inequality,
have
[(s
((e.a) (Er(o11a))
- E ( [VT [[T=(((')]]]
< E (s.a)
1-
With Lemma 13, we have
a) B(s,a)aff 1-7
( (s)
42y2C
< BBz,aya4 1p (-(3,))) S
+
(1-))
(1 (1
WE [F(sa))p(((ss0) +
1-7
nw>s
4x7²0
WC
<B(ga)ed (-33, () (L
V
(1- (1 (1-
(1-7)
31

---

Published as a conference paper at ICLR 2023
V
/ 3c 1-
Son (3.)) Ilp" (-13,
Combine with the previous results and take the dominating terms out, we have that
For 3-finite spectrum,
Vi. V
E (3,0)
1p" (1
VwyBa? logn + Cy²C
wBO log
wc
V (1-))3 (1 7)m
For 3-polynomial decay,
Vi
Vi-.
E Baaayt l|p" (13,,)))) bal pip
(
V VunCpolya 20ter logn + 2r
1
Opoly azn I ttat log n
wc
1 1-7
+ +1
V (1- (1-7)3'
For 3-exponential decay, Vi...
Vi...
B B(E (-((,))) mal (lnga log log n Xr
W WCep a² (logn)
+ 1
wc
(1- 7
(1-733
We now deal with the term B( I|p" (13,,)
Lo(r). (1,,
With Lemma 11, we know
E Braayd 1|p" (-13, à) Lo(w))
B (-1 a) i1
CE (-33, L
Applying the identical method used in the proof of Lemma 8, we have that:
For 3-finite spectrum, we have
E(g,a)~p [1le (13, = O O33 (31ogg no
For 3-polynomial decay, we have
E(,,a)~p [Ip= a1 -
=0 - logn)
For 3-exponential decay, we have B(,,ay~ (11" = 0 (Cexp (log ()11))))))
Substitute and À back, we have that:
For 3-finite spectrum, we have
w/33/2 log n
CC log (P)
V V
(1 (1-
32

---

Published as a conference paper at ICLR 2023
For 3-polynomial decay, have
VT. V Pollyum शगमकक log n CC2 log( (PI/5)
(1 71-
For B-exponential decay, we have
3428 (log))
2a
CC log /0)
VI..r Vir
(1 11-
This finishes the proof.
F AUXILLARY LEMMAS
We first state the MLE generalization bound from (Agarwal et al., 2020). Note that, when Assump- tion I holds, the MLE generalization bound only depends on the complexity of P.
Lemma 16 (MLE Generalization Bound (Agarwal et al., 2020)), For fixed episode with probability at least 6, we have that
[[Tn(s,a) - ( (
lo/(()
E E.50. 4...0.5p......ppp.. (u)A))
With union bound, with probability at least - 8, we have that
[| - (s) -T. log(n|P1/6)
Vn N+, E.000.00. 40.5pf ((A)
n
Lemma 17 (Concentration of the Bonuses). Let μs be the conditional distribution of & given the sampled .i, -i-i,, define E L2(u) + L2(u), En := = Ligin) Bg ob Assume 1 I for any realization of d. If satisfies the following conditions for each eigendecay condition:
B- 3-finite spectrum: X = O(Blog N log(N/6)):
3-polynomial decay: A (V1(+)) log(N/))))
B-exponential decay: X = O(Cexp (log (ogg//) where C3 is constant depends on C2 and Czi
then there exists absolute constant ej and cz such that Vo E Ha. the following event holds with probability at least 1 -8: 8:
Vn [N], ei (1,, (wEn xT=2) x²) La(u)
5(x, x, Σ
5
driet + +XTT x
iE(m]
Lz(a)
and
Σ 2 +
XT
x
Sez (x, + AT x) Ea(a)"
iE(M)
La(z))
In the same event above, the following event must hold as well:
Vn [N],
1 1 xx (nE.
xT= x.)
x, Σ
2Φ0. AT
C2
Lz(N)
(E(m)
L2(H)
-1
and
I,
Σ
T + -Xx=
x. (nEn C1
x)==1) x) I2(1))
[ein]
Lz(p)
11 < 1. Hence, the operator norm of operators Σ,, Proof. Note that, || 1/2 (a(
T- 1/2 T-1/22 ",,,,, T 1/2 that maps from (z((1) to (1)) upper bounded by 1. For notation simplicity,
33

---

Published as a conference paper at ICLR 2023
define क := Tx= Note that Vx E Hr. Tx E Hzg We now prove the following equivalent form of the claim: do E Mz. An 2 1,
1/2 1/21 & and ji denotes the conditional distribution of given the sampled "1,-.. .0---
-9:-1-
a (z, (nÊn xTx²) 2)
Σ /E/ml
00 + xTxx
S S (z,, (nEn XIx x)) Lz(N)
I,
Lo(H)
T(2(1))
It is sufficient to consider with ||0l| Note that, we have
2 20 La(u) = (I, Lz(u) S || [|=]122(0)
Denote D":= = Eeona Φ6
We have
Vargaum (1, 2mo) S || Ba (,, ()
11=1ll (n)) (z, E' ()))
we can invoke a Bernstein styll martingale concentration inequality (Lemma 45, Zanette et al., 2021), and obtain that with probability at least 5
( (ar, La(M) logm)/ log(2/0) (c. (1r.a (x, Ex) baww) so so(v [belBiotw
|| (wll log(2/0)
n
3n
where is an absolute constant. We then show that, we have (((lo((1/))) we have that [ (2/))
| (in (z. (2()) l2/(2
C
(s, (o,
n
n
where < an absolute constant, following the similar reasoning the proof of Lemma 39 in (Zanette et al., 2021):
S (rr, Ex)) La(n)) I A It's sufficient show that ey A log(2/0)
CA 2 and clog(2/8)
CA
2, which can be achieved by A = St(log 1/8).
(c. Exx) L2(n) 2 Melllii It's sufficient to show that
A log(2/5) and CV ( log(2/0)
I v (1, E1xe) bz(n)-
As (x. L 2 Alalll2g0 when A 2 max { 2 {
() log(2/0), these two conditions
hold simultaneously.
Hence, for any fixed with ||,|| 1, we have
Σ (z, 22a00)))))) (x, Ex) La(w) vE(m)
<c(2, E (1+
SC(I, x,
(5+
1==2 La(u)
x
L2(u))
ni
Now, assume such condition holds for e-net B. of SHe. the unit sphere of RKHS H2 (i.e.
for : || 1}), under || [[))())- Then Va satisfies | 1, let x' be the closest point of xr in B. under || (1))()) (note that x' E Hg by the definition of e-net). We have that
(x,, Ex) (x', Ex²)
<2e
x,
Σ
x
x',
x'
<2e
n2
72
ve(m)
34

---

Published as a conference paper at ICLR 2023
With triangle inequality, Vn, A|[zI| I 1, we have
X TT_2
X
F
Φ
x.
T
x
n
in(n
n
L2(1)
n
L2((N)
SC
D +
-
Tx
+ (C+
(2(())
Hence, we can choose
0
(H)
to guarantee that
(I,(E++
T c Σ n
[ TT=2 Iz((1)
+ +C4+2C) C
x
2,
x
T2(0)
n
where C' is an absolute constant.
Now we consider the covering number MS |l (lIz(a)))). E). We start from the entropy number ei(SH,:ll Il (lL2(a))) From (A.36) in Steinwart & Christmann (2008), we know ea |l (1ي)( S ei(SH; ll (I(a()) S 2e;(BH, (I-
where Big is the unit ball in RKHS Mg (i.e. {a : || I 1))). With Carl's inequality' (Carl & Stephani, 1990) (also see (Steinwart et al., 2009)), vp > 0,m E N+, we have
sup /1/ e H - [2(1n)
iE/m]
1/2 (I L2(4) + L2(1)) //1 14;
Scp sup
iE ml
Cp sup i/p p4 (Tk L2(u)= L2(n))
ic ml
where C2- = (28 denotes a constant only depending on We then consider the entropy number under different eigendecay conditions:
. For A-finite spectrum, as we have Eier 14 S 1 from Assumption 3, and Vi > 1, L2(1) + L2(4)) = O, we know for fixed
e; Hg - [2(n)) I 128 ((32 + 16/p)) (B/1))
(3/
Take p B/i, we know that
es(id: Hz + L2(u)) < 128 + 16/
For 3-polynomial decay, take p 2/3 and obtain that e;(id: Hg + L2(2) < 128Co(32 + 3/200-
For 3-exponential decay, note that, for fixed p. direct computation shows the maximum of ///9 expeexp(C222 is achieved when 1 C2pp' Furthermore, /t/r exp(-C2i is monoton- Capn while monotonically decreasing with
ically increasing with respect i when 1 respect to i when ;8 and obtain that
Cg Hence, for given i, we can choose such that i Capp
(idi H - L2(n)) < 128 //C) exp(-C2
As we can take p - oo, we have that
(idi Hs + L2(1)) < 128C; exp(- -C2i)).
We now convert the entropy number bound for different eigendecay conditions the covering number bound accordingly.
A more formal claim is on the approximation number of the bounded linear operator, which, as shown in Steinwart & Christmann (2008), is identical to the eigenvalue of the bounded linear operator if the bounded linear operator is compact, self-adjoint and positive.
35

---

Published as a conference paper at ICLR 2023
For 3-finite spectrum, we fix d (0. 1) and E (0, 128), and assume the integer 2 1
satisfies the condition:
128(1 + 6)228 + 16) (1-11// < S 128(1 + (32, + 16)-
By the definition of the entropy number and covering number, we know
(B || (l
$ WB (laa(n)) 128(1 6)(323 + 16) (++1)/)
1ilog(2)
128(1 + 6)
I,1og(() log
256
3.3 log
= =0 (3 log(1/e))
For 3-polynomial decay, with Lemma 6.21 in (Steinwart & Christmann, 2008), we have that
1/8
log (Bg |l- [llz(n), <) < log(4) 128Co + 83)
=0 (Cpolye-1/89
For 3-exponential decay, fix (0, and an E (0, 12,CC] and assume the integer 2 1 satisfies the condition
128C, (1 + 6) exp(-C2(i + 1) I S 128C) (1 + 8) exp(-C2i))
By the definition of the entropy number and covering number, know (lzz(m).
logNN
S log.V(BH, || -ll2(1)), 128C| (1 + exp( 1)0))
<ig((22)
log (28C((1+))
1/8
1og((2)
C2
1/3
log 256C1)
< <log(2)
=0 (Coop log( (og(1/e)2/0))
C2
where C3 is constant depends on C11 and C2.
Note that n S N. Hence, we can choose e for different eigendecay conditions and lead the first claim as follows:
For ß-finite spectrum: we choose e O(n-)), and obtain the first claim with À θ (8lo + log(1/6)) using union bound over B3 and [N].
For 3-polynomial decay: choose O(n ((n-9/(1++))) and obtain the first claim with X O NC log(N/6)) using union bound over B and [N].
For ß-exponential decay: we choose O(n-*), and obtain the first claim with A θ (Cexp (log N/3/3 log(N/5)) using union bound over Bg and [N].
For the second claim, note that,
En + XT
1
Tx
1/2
1/2 x,TT
(nEnT
+ XTx
x,
Σ
T.OT T + -Tx=1
x
T
1/2 x,
T
12 Σ
श.のe + xIT=
T2/21,111 1/2
36

---

Published as a conference paper at ICLR 2023
Note that, {Tx I He} spans the (p),, when the first claim holds, have that, Vo' E L2(1)).
1/2
Vn E [N]
d' T 1/2
(n + AIW) -Iw) -'m
2/11-112
1/2
Σ kE(n)
didi + +XTx"
Ts 1/2 x
C2
Lz(())
Lo(K))
and
x', TxThl
1/2
Σ VE(m]
::00 + AT
Th 1/1
1 x' (nE
T 1-1/22'
C1
Tn(
12(1))
As Va: E Ha. TRat Tz((1) and we can choose x' = Ty. which shows the second claim holds when the first claim holds.
Remark 9. Here follow the idea of Zanette al. (2021, Lemma 45) and present a less involved proof. However, it also possible to use the Bernstein inequality for matrix martingale with intrinsic dimension (e.g. Minsker, 2017) to prove the similar results.
P,r, du, 7) and Lemma 18 (Simulation Lemma). Suppose we have two MDP instances M = AS.A. M' = (S,A, r + b, do. 7). Then for any policy n,, we have that
V VG,r
1 ? E (e ()) + + (Epr)))))) (VP VV (+)(')))))) - p VV r+)()
VPrr+b Vi.r 1 (l (8s + [P (V7, Ep(e' a.0)) [V7,, (s')]]
Proof. See Uehara et al. (2022, Lemma 20).
Lemma 19 (Potential Function Lemma for RKHS). If a = 2(11, then for any distribution supported on the unit ball of Hg. we have that,
For B-finite spectrum:
(0(+)=00(100)))) log det (alEw (á (1o =0 Blogg 1+ 11) )
For B-polynomial decay:
log del (alEs (660) ( [] 0
(22/) = (Croty log a
For B-exponential decay:
log det (oilE, 100 1 + = =Ceepp (lllgg))+//00/ 1+110)
where operators are in the space of L2(n) L2(n).
Meanwhile, when a = O(), any eigendecay conditions, we have that
log (aTE, (66 1 + r) = 0(1).
Proof. We consider the optimization problem:
sup log det (I +I+ aTEga [l
We first consider the optimality condition of v. Note that, log det(X) ()) is concave with respect to positive definite X and Egr [ is linear with respect to v. Direct computation shows that d log det (1 + alE--n [d6
Tr (xx (I + a.Eoo [00 "]) Φeb
du(o")
= =(00 (a-17- Baw 100 T)) -1 (6¹)
La(u)
37

---

Published as a conference paper at ICLR 2023
1) -1 al. Hence, the inner product is well-defined. As is probability measure over the Byg and if c 2 1,
Note that, (a- Eag 1
00l (a 1 + -Ezao [d0)] ']) og6) [2(a))
=2² ( (a (I- I Betrr (sbs) [)) -1
05
(2(1)
2 ( 0' -a-1I Boow [00 'I)
Iz(a))
Hence, we can focus on the v supported on SH:- Furthermore, with the optimality condition of the probability measure, we know the optimal should satisfy that Vo' E supp(r),
(a' II+ Enw [
C,
l2((1)
and Vá' SHy we have
( (a-1111-0 1 Esr [oo ()= d')
SC,
L2(11)
where C' is some constant.
We first show that, C 2 optimization problem
ogj (Tt)² ouf +
which can be shown by consider the following constraint
inf 8 (2. Bepwo [dre) [
05'
Lz(a)
where is from the space of probability measure supported Stg. As (Ir, A-1x)) is convex with respect to positive definite and EpreldoT]] is linear with respect to v, straightforward computation shows that
00,, (2 Egwe (oo -1 d') La(k) = --(---00) (8'
(2.(21+
Eepn [oba)]]
du
La(a)
With the optimality condition, the optimal v should satisfy that Vo E supp(v),
(0', (a-1I++ -I + Exwe [Oo -1 x) La(K)
= C².
and Vo SH. we have
(0, (a--1 II Berre (00
SC',
Lg(N)
where C" is an absolute constant. With Cauchy-Schwarrd Schwartz inequality, we have
(0', (a II [00 ()) -1
Lz(n)
Th (a
-1-1++ E Expe [00 [) -1 0'
1T (ollate))))
12(u)
The (a- Eggu (0 7)) where the maximum only achieves when
Lz(n))
c' (a 1 Eepnu (db)) [)) 25
where e' is an absolute constant to make sure || = 1. Hence, the optimal y is point measure supported on क which further leads
(a-'1+ 1 06
T 2 0 (T-1T, +1)
Take o' u1= (T (Tk)es, as e; is the eigenfunction of T we know v should only support on yi (Ti) Je, and
app(TTe)
inf 0', (a- 1 + Egrn 100 1]) ()= d')
Lz(#)
app(Ti) +1
ap (pr(1)) )2
which means C²
(7
38

---

Published as a conference paper at ICLR 2023
Now consider the constraint optimization problem ( (a II Eegn (sie) "]" -1 d²), s.l. 11011114 1.
max &
With the method of Lagrange multiplier, we know that CTØ² - (a- - Bow [) ž 0. and for all Φ in the support of v, we have (CTØ² (a-11 + Eønn [0o] T) 1)= 1
0. Note that
(a (a- 1 + Begno [T) "1 op
With Weyl's inequality, we know that,
(i(TT) (
(uf((T)) +1 -1).
Ms 2CTx²
Edany (00 7) ")- 2 Cpi(Th)=²
which means the (T))) P(Tk) S (
of v is at most io dimension, where in is the largest integer that +
When = ((), with Assumption 3, we know (Tt+ S 1 and in = O(1). Combined with Jensen's inequality, we finish the proof of the second claim.
We then consider the case when a 22(1) under different eigendecay conditions:
3-finite spectrum: know to
As (a(a) With Jensen's 's inequality, we have
1 1|
have
ESn Io0 [llp I
( (Blog 1 0
=)))
log det (T + -aBauw [ =0
3-polynomial decay: we know io = O (Cpoly (228)) dimension. As [ S
|,,,,, = 1, we have ||E [sbe T]llop < With Jensen's inequality, we have
log det (I + a'Err [do (Cpoty 1/(8)) log loga)
3-exponential decay: know the support of is most O (Cexp aolllogg)/44 1/3) dimension. As (,)))) $ || 1, we have |E [ I 1, With Jensen's inequality, have
log det (1 + aBgnv [0o (Cexp (log (log 1)1//
Hence, we obtain the desired results.
G ADDITIONAL EXPERIMENT RESULT
G.1 TRAINING WITH 1M STEPS
This section provides the learning curves with training steps compared to SAC in four Mujoco control problems. We only tune the cature-updates best result to save computations and running time. The results clearly demonstrate that LV-Rep also achieves significantly better performance in the long run.
parameter from 3,, and report the
H6l0 eatah
2500
Happer
2000
2000
1000
100
5.5
10 60 02
02
02
0.4
03
300
20
10
Figure 3: We show the learning curves in Mujoco control compared to SAC. The x-axis shows the training iterations and y-axis shows the performance. All plots are averaged over random seeds. The shaded area shows the standard error.
39

---

Published as a conference paper at ICLR 2023
G.2 ABLATION STUDY ON LATENT REPRESENTATION SIZE
In this section, we provide an ablation study on the latent representation dimension to show this parameter affects the performance of LV-Rep. In all our experiments the latent feature dimension is set to 256. We compare to latent feature dimension 64 and 128 in HalfCheetah. The results are reported in Figure
feature
7000
LV-Rap-04
6000
LV Rop 128
LV- LV-Rep-216 256
0003
4003
0.0
0.5
1.0
1.5
2.0
training steps (1e5)
Figure 4: Ablation study on the dimension of latent representations.
40


Reviews:
[{"review_id": "xGNKB4YiLQ6", "reviewer": "Reviewer_F7os", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a provable reinforcement learning algorithm for low-rank MDPs. The key difference from past work on this literature is that the transition model $T(s' \\mid s, a)$ has a decomposition $<\\mu(s'), \\phi(s, a)>$ which can be an infinite-dimensional inner product, however, it is required that $\\phi$ and $\\mu$ are both probability measures. This is viewed as a latent variable model where $\\phi(s, a)$ denotes the vector $(p(z \\mid s, a))_{z}$ and $\\phi(s')$ denotes the vector $(\\mu(s' \\mid z))_z$. The transition dynamics can then be expressed as $\\int p(s' \\mid z) p(z \\mid s, a) dz. \n\nIt is claimed that the above decomposition, in addition to more flexibility due to infinite-dimensional $z$, offers a flexibility of computationally-efficient maximum-likelihood estimation through ELBO and a simple-sampling scheme for $T$ obtained via $z \\sim p(\\cdot \\mid, s, a)$ and $s' \\sim p(\\cdot \\mid z)$. However, infinite-dimensionality of $z$ complicates things as well, in particular, requiring $Q$ function to be approximated using a kernel (or a two-layer neural network).\n\nThe presented algorithm LV-REP follows previous work (REP-UCB, FLAMBE), and estimates the model based on data collected so far, and then plans with an optimism-based elliptic bonus to find the next policy to collect data from. PAC results are presented for online learning (and a similar result for the offline case). Experiments are presented on Mujoco tasks showing comparable performance to prior work, while the presented approach also has theoretical guarantees. ", "summary_of_the_review": "I lean towards a weak acceptance. My two main concerns are (i) clarity on how and when is LV-REP MLE more efficient than FLAMBE, (ii) how the trade-off work with FLAMBE that assumes finite-rank but allows the decomposition into $\\mu, \\phi$ to take negative values, and (iii) the two wrong assertions stated above. ", "strength_and_weaknesses": "Strength:\n\n1. Generalization to infinite-dimensional $z$ adds more flexibility, however, there is also constraints on the decomposition restricted to probability measures.\n2. PAC guarantees\n3. Experimental results showing comparable results\n\nWeakness:\n\n1. The paper seems to make two wrong assertions regarding prior work:\n\n- _\"Our definition of LV-Rep is more general than the original definition in Agarwal et al. (2020), which assumes |Z| is finite.\"_ This seems wrong. While FLAMBE assumes a finite rank, the features are not restricted to probability measures, in particular, features can take negative values. They also argue that the non-negative rank can be much larger than the rank of $T(s' \\mid s, a)$. I would like to understand how this trade-off works.\n\n- Regarding block MDP _\"p∗(z|s, a) is a deterministic measure supported on the latent state that generates the next observation.\"_. This is not correct. The block MDP algorithms mentioned also handle stochastic transitions. I believe this is a typo and $p(z \\mid s, a)$ is a stochastic measure that generates the next state and $p(s' \\mid z)$ is the emission distribution for generating an observation $s'$ based on latent state $z$. \n\n2. It is not clear to me when is the ELBO approach more computationally-efficient than the MLE approach in FLAMBE, etc. that the paper criticizes. Doesn't the ELBO approach also require maximizing over $q$? What is the empirical optimization that is being performed in the code? If this can be described clearly in a pseudocode and the advantage over MLE is more clearly described, then it would be helpful.\n\n3. Representing the Q function requires approximation using kernel or neural network. This requires certain conditions to be satisfied that I am not sure, how easy, it will be to satisfy in practice. Experiments, however, show that this is possible at times which makes this less concerning.\n", "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": "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": "iJmfbWjTycG", "reviewer": "Reviewer_Y1QJ", "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": "", "summary_of_the_paper": "The article proposes a new RL algorithm where the idea is to model the dynamics of the system by using a latent representation space. Using a latent representation to capture the dynamics, it allows one to use\nvariational methods (and ELBO optimization) for doing representation learning over the MDP (Section 3). This is done by connecting latent representation models to Linear MDPs. In Section 3.1, the authors then use the maximization of ELBO approach to learning representations while simultaneously learning the policy (see Algorithm 1). The proposed approach is to alternate between representation learning steps and policy updates, these policy updates being made by planning on the learned model. One of the main points in the algorithm is to add an exploration bonus similar to the one proposed in REP-UCB. Section 4 provides a theoretical analysis of the algorithm. Section 5 describes experimental results obtained in the online RL setting over different classical control benchmarks. In that section, the proposed approach (with both discrete and continuous representations) is compared to classical RL (model-free and model-based) methods. It demonstrates a high efficiency on many of the tasks.\n", "summary_of_the_review": "In conclusion, the paper explores the use of a VAE as a representation model learned together with the policy. One of the interests of the VAE is that it allows the definition of an exploration bonus to guide the learning, which is certainly the critical reason for the good performance of the approach. The paper is interesting to the community, with theoretical and practical contributions (I did not check the proofs), but the writing makes the paper quite hard to follow. ", "strength_and_weaknesses": "First of all, the paper is very dense, providing both theoretical results and practical algorithms. As a consequence, it is sometimes difficult to understand exactly what the contributions presented are -- for instance in Section 4, the theoretical analysis is quite short (regarding the dozens of appendix pages) and it is hard to understand what to conclude exactly on the approach from the provided theorem which is very hard to catch without providing more explanations. Similarly, when describing the algorithms, many different aspects are still unclear to me (and not better detailed in the appendix). So I have mixed feelings about the article, and I think that the authors have to update the writing to make the paper more pedagogical and to clearly state the critical aspects of their approach. This is the type of paper that better fits in a journal than in a conference. \n\nHere are some concrete questions: \nPage 4: Connection to Ren: many different notions arise in this section like representation complexity, We understand that it is related to sample complexity (and Section 4). The last sentence \"The LV-Rep with....and learning\" is completely unclear at this moment in the article. I would suggest moving this paragraph into Section 4 instead since, at this point, it does not really bring relevant information to the reader, and make the message unclear. \nConcerning the ELBO approach which defines a variational encoder for the transitions, this approach has already been proposed in different papers like \"Temporal Difference Variational Auto-Encoder - Karol Gregor et al.\" for instance. Can you discuss the differences between this paper for instance ?  Is it really new ? \nOn page 5, the w^pi(z) notation appears without any clear definition. If we understand that it is a rewriting of the value function by using the latent representation, it would be nice to give a clear definition, and to comment a little bit more.\nThe use of random feature representation (described in the appendix only) is crucial to understand how you handle continuous representations. And the paper does not give clear definitions of this particular aspect. I would recommend providing more explanations about this point directly in the paper. It is not clear for instance how you choose the value of 'm', the distribution P(xsi_i) and what is the impact of these choices (Note that, in the experimental section, these choices are not detailed). \nEquation 8: the bellman equation is rewritten with an exploration bonus. This equation is connected to the notion of 'planning' in the paper and in the algorithm where (line 7) a new policy is obtained by planning using the exploration bonus. I don't understand exactly how this step is done. Moreover, in Section 6, you state that SAC is used as your planner in LV-Rep. Maybe it is just a matter of semantics, but in my mind, SAC is not a planning algorithm. Can you make this point more clear ?  I think that depending on the background of the reader, the use of the term planning can be misleading.\nSection 4 is actually too short to capture the theoretical contribution you are making in the paper. For a reader which is not specialized in theory, I would suggest better explain the content of Theorem 1, and providing a small insights about the steps to obtain such a theorem\nOn the experimental side, I would be happy to have more information about the impact of the representation size on the performance. Experiments with a high-dimensional space would also be interesting to evaluate if the approach is also able to capture a relevant representation space when observations are in high dimension -- this is not a critical remark but would strengthen the paper. \n", "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": "DkI8hK7lGjk", "reviewer": "Reviewer_9PEm", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This submission proposes a new model-based RL method grounded in representation learning. It seems like the central idea is to impose linearity on the transition function, which is formulated as the dot product between $p(z|s.a)$ and $p(s'|z)$, which are both parameterized as neural networks.", "summary_of_the_review": "As admitted above, this is a low-confidence review. However, I don't see the claims made in the introduction that suggest a fundamentally more efficient RL algorithm supported by the evidence presented in the experimental section. Yes, the learning curves are equal or better than SAC, but evaluation is limited to the first 200k environment steps. I think that the paper could definitely benefit from more exhaustive experimental analysis, even if it's placed in the Appendix.", "strength_and_weaknesses": "Honestly, I had a hard time reading this paper and believe that my understanding is somewhat limited (cf confidence score) due to scarce exposure to relevant prior work. I'll hence focus my review on the experimental section and am happy to adjust my score in the rebuttal if necessary.\n\nThe paper opens with a (quite bold) claim that the proposed algorithm remedies the computation difficulties of RL; in particular, the authors claim sample complexity (I assume this is what is referred to with \"statistical complexity\") independent of the number of states. While the theoretical analysis suggests that this is the case, I would have liked to see this demonstrated in experiments more clearly.\n\nThe experiments themselves are performed with common MuJoCo tasks, either as defined in gym or in dm_control. Generally, I think that learning curves for up to 1M steps should at least be shown in the Appendix; the plotted learning curves clearly indicate that further learning progress can be anticipated (according to the MBBL paper). The MBBL paper mentions that they limited their experiments to 200k steps since model-based methods are often slow to run and converge much earlier than model-free algorithms. What is the wall-clock time in your case? Besides, assuming that the authors ran the Dreamer and Proto-RL baselines themselves, could you add them to plotted the learning curves?\n\nFor Table 1, maybe the authors could provide more exhaustive evaluation by training on both ET and non-ET variants, for the sake of completeness?\n\nRe the dm_control experiments: my understanding is that `hopper_hop` and `humanoid_run` are not sparse-reward; the writing should be adjusted accordingly.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7Ug3LGjHzC", "reviewer": "Reviewer_F81s", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper provides a representation view of latent variable models in linear MDPs, and further propose a computationally efficient algorithm to implement it for both online and offline RL. The authors also theoretically and empirically demonstrate the proposed approach.", "summary_of_the_review": "The paper builds a nice bridge between latent variable models and linear MDPs, with well supports on both theory and practice. ", "strength_and_weaknesses": "**Strength:**\n\n+ The paper is well organised and well written. \n+ The idea is reasonable and also well supported both theoretically and empirically.\n\n**Weaknesses:**\n\nI only have some minor concerns:\n\n+ Theorem 1 shows that the sample complexity largely depends on $|\\mathcal{A}|$. This seemingly implies that the proposed approach might struggle in the environments with continuous action space. Is it right?\n+ I understand that the factorization in (3) is consistent with the linear MDP setting. I am wondering how this could be extended to the nonlinear MDP setting? In my opinion, a more straightforward and general factorization should be $T^*(s'|s, a)=\\int_{\\mathcal{Z}}\\int_{\\mathcal{Z}} p^*(z|s)p^*(z'|z,a)p^*(s'|z')dzdz'$, which explicitly models an MDP over the latent space. Is there any insight over this?", "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": "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:

Decision: Accept: poster