Efficient Exploration for Model-based Reinforcement Learning with Continuous States and Actions
Authors: Ying Fan
Yifei Ming
Venue:  (2021)
Keywords: Model-based reinforcement learning
posterior sampling
Bayesian reinforcement learning

Abstract: Balancing exploration and exploitation is crucial in reinforcement learning (RL). In this paper, we study the model-based posterior sampling algorithm in continuous state-action spaces theoretically and empirically. First, we improve the regret bound: with the assumption that reward and transition functions can be modeled as Gaussian Processes with linear kernels, we develop a Bayesian regret bound of $\tilde{O}(H^{3/2}d\sqrt{T})$, where $H$ is the episode length, $d$ is the dimension of the state-action space, and $T$ indicates the total time steps. Our bound can be extended to nonlinear cases as well: using linear kernels on the feature representation $\phi$, the Bayesian regret bound becomes $\tilde{O}(H^{3/2}d_{\phi}\sqrt{T})$, where $d_\phi$ is the dimension of the representation space. Moreover, we present MPC-PSRL, a model-based posterior sampling algorithm with model predictive control for action selection. To capture the uncertainty in models and realize posterior sampling, we use Bayesian linear regression on the penultimate layer (the feature representation layer $\phi$) of neural networks. Empirical results show that our algorithm achieves the best sample efficiency in benchmark control tasks compared to prior model-based algorithms, and matches the asymptotic performance of model-free algorithms. 

Under review as a conference paper at ICLR 2021
EFFICIENT EXPLORATION FOR MODEL-BASED REIN- FORCEMENT LEARNING WITH CONTINUOUS STATES AND ACTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Balancing exploration and exploitation is crucial in reinforcement learning (RL). this paper, we study the model- based posterior sampling algorithm in continuous state-action spaces theoretically and empirically. First, we improve the regret bound: with the assumption that reward and transition functions can be modeled as Gaussian Processes with linear kernels, we develop Bayesian regret bound ((H*/2d where I/ the episode length, d the dimension of the state- action space, and T indicates the total time steps. Our bound can be extended to nonlinear cases as well: using linear kernels on the feature representation Φ, the Bayesian regret bound becomes ((H3/2 do V /T), where d& is the dimension of the representation space. Moreover, we present MPC-PSRL., model-based posterior sampling algorithm with model predictive control for action selection. To capture the uncertainty in models and realize posterior sampling, we use Bayesian linear regression on the penultimate layer (the feature representation layer Φ) of neural networks. Empirical results show that our algorithm achieves the best sample efficiency in benchmark control tasks compared to prior model-based algorithms, and matches the asymptotic performance of model-free algorithms.
INTRODUCTION
In reinforcement learning (RL), an agent interacts with an unknown environment which is typically modeled Markov Decision Process (MDP). Efficient exploration has been of the main challenges in RL: the agent expected to balance between exploring unseen state-action pairs to gain more knowledge about the environment, and exploiting existing knowledge optimize rewards in the presence of known data.
To achieve efficient exploration, Bayesian reinforcement learning is proposed, where the MDP itself is treated as a random variable with prior distribution. This prior distribution of the MDP provides an initial uncertainty estimate of the environment, which generally contains distributions of transition dynamics and reward functions. The epistemic uncertainty (subjective uncertainty due to limited data) in reinforcement learning can be captured by posterior distributions given the data collected by the agent.
Posterior sampling reinforcement learning (PSRL), motivated by Thompson sampling in bandit problems (Thompson) 1933), serves as a provably efficient algorithm under Bayesian settings. In PSRL, the agent maintains posterior distribution for the MDP and follows an optimal policy with respect to single MDP sampled from the posterior distribution for interaction in each episode. Appealing results of PSRL in tabular RL were presented by both model-based (Osband et al. 2013 Osband & Van Roy 2017) and model free approaches (Osband et al. 2019) in terms of the Bayesian regret. For H -hhorizonn episodic RL, PSRL
proved to achieve regret bound of ÓH VSAT). where S and A denote the number of states and actions, respectively. However, continuous state-action spaces S and A can be infinite, hence the above results do not apply.
Although PSRL continuous spaces has also been studied in episodic RL, existing results either provide no guarantee suffer from an exponential order of H. In this paper, we achieve the first Bayesian regret bound for posterior sampling algorithms that is optimal in T (i.e. vT) and

---

Under review as a conference paper at ICLR 2021
polynomial in the episode length H for continuous state-action spaces. We will explain the limitations
of previous works in Section 1.1 then summarize our approach and contributions in Section 1.2
1.1 LIMITATIONS OF PREVIOUS BAYESIAN REGRETS IN CONTINUOUS SPACES
The exponetial order of H: In model- based settings, Osband & Van Roy 2014) derive regret bound of Ö( dx ( Rtj + [E[1."|0,, ppp /dx (dxx(P)d (P)dæ( (P)) P)), where I." is global Lipschitz constant for the future value function defined in their eq. (3). However, I.* is dependent on H: the difference between input states will propagate in H steps, which results in term dependent of H in the value function. The authors do not mention this dependency, so there is no clear dependency on H in their regret. Moreover, they use the Lipschitz constant of the underlying value function as upper bound of L" in the corollaries, which yields an exponential order in H. Take their Corollary 2 of linear quadratic systems as an example: the regret bound is O /T), where X is the largest eigenvalue of the matrix Q in the optimal value function (8) s QsQ However, the largest Even if we change the reward function from quadratic to linear.the Lipschitz constant of the optimal value function is still exponential in // F Chowdhury & Gopalan (2019) maintains the assumption of this Lipschitz property, thus there exists E[L"] with no clear dependency on H in their regret, and in their Corollary 2 of LQR, they follow the same steps as Osband & Van Roy (2014), and still maintain a term with Y1, which is actually exponential in H as discussed. Although Osband Van Roy (2014) mentions that system noise helps to smooth future values, but they do not explore it although the noise is assumed to be subgaussian. The authors directly use the Lipschitz continuity of the underlying function in the analysis of I. LQR, thus they cannot avoid the exponential term in H. Chowdhury & Gopalan (2019) do not explore how the system noise can improve the theoretical bound either. In model-free free settings, Azizzadeneshhlii et al.) (2018) develops a regret bound of Ö(d /T) using a linear function approximator in the Q-network, where de is the dimension of the feature representation vector of the state-action space, but their bound is still exponential in H as mentioned in their paper.
eigenvalue of Q is actually exponential in H R
The eluder dimension of neural networks in Osband & Van Roy (2014) can be infinite, and the information gain (Srinivas et al.) (012)) used in Chhowhhury & Gopalan (2019) yields exponential order of the state-action spaces dimension d if nonlinear kernels are used, such as SE kernels. However, linear kernels can only model linear functions, thus the representation power is highly restricted if the polynomial order of d is desired.
High dimensionality:
1.2 OUR APPROACH AND MAIN CONTRIBUTIONS
To further imporve the regret bound for PSRL in continuous spaces, especially with explicit de- pendency H, we study model- posterior sampling algorithms in episodic RL. We assume that rewards and transitions can be modeled as Gaussian Processes with linear kernels, and extend the assumption to non-linear settings utilizing features extracted by neural networks. For the linear case, develop Bayesian regret bound of ((H3/2dVT) Using feature embedding technique as mentioned in Yang & Wang (2019), we derive a bound of 0(H3/2d VT). Our Bayesian regret is the best-known Bayesian regret for posterior sampling algorithms in continuous state-action spaces, and it also matches the kestt frequentist regret (Zanette al. (2020). will be discussed in Section 2). Explicitly dependent on d, H, T, our result achieves a significant improvement in terms of the Bayesian regret of PSRL algorithms compared to previous works:
1. We significantly improved the order of H to polynomial: In our analysis, we use the property of subgaussian noise, which is already assumed in Osband & Van Roy (2014) and Chowdhury & Gopalan (2019), to develop a bound with clear polynomial dependency on H. without assuming the Lipschitz continuity of the underlying value function. More specifically, we prove Lemma and use
112 denotes the value function counting from step to H within an episode, is the initial state, reward at the i-th step r; s! Ps; + a. Ra; + εp,, and the state at the + 1-th step 8:+1 As; + Ba; + EP 'Recall the Bellman equation we have Vs(s.) = min., 8 Ps, + a. Ra, + ép. + V++1(As + Ba, + EP.), VH+i(s) (x) 0 Thus in Vi(s). there is term of (A"-2a)² "TA -P s). and the eigenvalue of the matrix (A " #- is exponential in H.
[H).
'oor example, if r, of P a. R + Ep, there would still exist term of (7) V1()).
2

---

Under review as a conference paper at ICLR 2021
it to develop clear dependency on H, thus avoid handling the Lipschitz continuity of the underlying value function.
2. Lower dimensionality compared to Osband & Van Roy (2014) and Chowdhury & Gopalan (2019): We first derive results for linear kernels, and increase the representation power of the linear model by building Bayesian linear regression model on the feature representation space instead of the original state-action space. As a result, we can use the result of linear kernels to derive a bound linear in the feature dimension. The feature dimension, which in practice is dimension of the last hidden layers in the neural networks required for learning, is much lower than exponential of the input dimension, so we avoid the exponential order of the dimension from the use of nonlinear kernels in Chowdhury & Gopalan (2019).
3. Fewer assumptions and different proof strategy compared Chowdhury & Gopalan (2019):
Although we also use kernelized MDPs like Chowdhury & Gopalan (2019), we omit their assumption A1 (Lipschitz assumption) and A2 (Regularity assumption), only use A3 (subgaussian noise). We avoid Al since it could be derived from our Lemma [ Moreover, We directly analyze the regret bound PSRL using the fact that the sampled and the real unknown MDP share the same distribution conditioned on history. In contrast, Chowwhurr & Gopalan (2019) first analyze UCRL (Upper confidence bound in RL) with an extra assumption A2, then transfer it to PSRL.
Empirically, we implement PSRL using Bayesian linear regression (BLR) the penultimate layer (for feature representation) of neural networks when fitting transition and reward models. We use model predictive control (MPC & Alba (2013) to optimize the policy under the sampled models in each episode as an approximate solution of the sampled MDP as described in Section Experiments show that our algorithm achieves more efficient exploration compared with previous model-based algorithms in control benchmark tasks.
RELATED WORK ON FREQUENIST REGRETS
Besides the aforementioned works on Bayesian regret bounds, the majority of papers in efficient RL choose the non- non-Bayesian perspective and develop frequentist regret bounds where the regret for any MDP M E .M is bounded and M E .M holds with high probability. frequentist regret bounds can be expressed in the Bayesian view: for given confidence set M, the frequentist regret bound implies an identical Bayes regret bound for any prior distribution with support on M. Note that frequentist regret is extensively studied in tabular RL (see et al. (201)). Azar et al. (2017). and Jin et al. (2018) as examples), among which the best bound for episodic settings is O(H (SA))
There is also line of work that develops frequentist bounds with feature representation. Most recently, MatrixRI. proposed by (Yang & Wang, 2019) uses low dimensional representation and achieves regret bound of Ó(1 /T), which is the best-known frequentist bound in model based settings. While our method is also model-based, we achieve a tighter regret bound when compared in
the Bayesian view. In model-free settings, Jin et al. (2020) developed bound of 0(H3/2 d VT).
Zanette et al. (020)) further improved the regret to (dd by the proposed an algorithm called ELEAAOR which achieves the best-known frequentist bound in model-free settings. They showed that it is unimprovable with the help of a lower bound established in the bandit literature. Despite that our regret developed in model-based settings, it matches their bound with the same order of H, dø and T'' in the Bayesian view. Moreover, their algorithm involves optimization over all MDPs in the confidence set, and thus can be computationally prohibitive. Our method is computationally tractable as it is much easier to optimize single sampled MDP, while matching their regret bound the Bayesian view.
PRELIMINARIES
3.1 PROBLEM FORMULATION
We model an episodic finite-horizon Markov Decision Process (MDP) M as {S, RM, PM H. H,O,, Rmaxs p}. where S Rd, and A C Rd denote state and ac- tion spaces, respectively. Each episode with length H has an initial state distribution At time step: [1, H] within episode, the agent observes 8, S, selects a, E A, receives noised
3

---

Under review as a conference paper at ICLR 2021
reward r; RM (st, a,) and transitions to noised new state 8i+1 PM (M; az). More specifically, r(5;, 0.) = fM (s,, a,) + e, and 8;+1 = ff (s,, a,) + es, where 6, ~ (O0,, o,), ey ~ NO of Variances of and of are fixed to control the noise level. Without loss of generality, we assume the expected reward an agent receives at a single step is bounded | (s. - Rmazs Vs S, a E A.Let μ: S + A be deterministic policy. Here we define the value function for state at time step with pM (sy. 0z) and aj = p(ss). With
policy μ as V (s) | (TM (s), d,)[s; s], where 8j+1
the bound expected reward, we have that [V(s] S H Rmar: vs..
We use M* to indicate the real unknown MDP which includes R and P and M itself is treated as a random variable. Thus, we can treat the real noiseless reward function F and transition function f as random processes as well. In the posterior sampling algorithm л T M is a random sample from the posterior distribution of the real unknown MDP M in the kth episode, which includes the posterior samples of R and på given history prior to the Ath episode: Hs. := { a1,1; "1,1, 1,-1,H H,, -"k..... where Sk,s; dk and Tk, indicate the state, action, and reward at time step i episode We define the the optimal policy under M as YrM Eargman, V.l (s) for all E S and E [M] In particular, 2e" indicates the optimal policy under M and μ represents the optimal policy under M Let A denote the regret over the kth episode:
A = (V,, - (
(1)
Then we can express the regret of n up to time step T as:
Regrel n" M*) == x f1
===1 As:
(2)
Let Regrel,, n=", 6) denote the Beyesian regret of Th as defined in Osband & Van Roy (211)) where & is the prior distribution of M*:
ReyesRe TP .) = E (TRegret(T, Th M')]
3.2 ASSUMPTIONS
Generally, we consider modeling an unknown target function RR + R. We are given a set of noisy samples y = [yr...., "/r"" at points X [x1:-..,,T]]] =T\² X D, where D is compact and convex, ((x,) + with 6; o0, i...d. Gaussian noise Vi E (1,"".
We model g as a sample from Gaussian Process GP(u(z), Klz,, x')), specified by the mean function ((x)= = [x]( and the covariance (kernel) function K(xx, x²) = [[((()) - u(r)(g(x') - (((((((==)(((())))))) )].
Let the prior distribution without any data as
K(x,,))) Then the posterior distribu- tion over given X and is also a GP with mean (I))). covariance KC x'), and variance (z): pr(x) = K(z, ()(((XX) + o²1) (2, x') K(x, - KXX.,) (K(X,, (.,,,,
d-1)- K(X,2)( [K((2,, x SISTTSSSS
Kr(z,x), where K((,z))
XXX,X)
We model our reward function FM as Gaussian Process with noise oF For transition models, we treat each dimension independently: each (,,s,a), 1,.., ds is modeled independently as above, and with the same noise level of in each dimension. Thus it corresponds to our formulation in the RL setting, Since the posterior covariance matrix is only dependent on the input rather than the target value, the distribution of each fi a) shares the same covariance matrice and only differs in the mean function.
BAYESIAN REGRET ANALYSIS
4.1 LINEAR CASE
Theorem In the RL problem formulated in Section 3.1 under the assumption of Section 3.2 with linear kernel F
we have Bayes RenyeeReeee((,,. (P), = ((HT/ where is the dimension of the state-action space, H is the episode length, and T the time elapsed.
*GP with linear kernel correspond to Bayesian linear regression f(x) w0 x,, where the prior distribution of the weight (0, E.p).
4

---

Under review as a conference paper at ICLR 2021
Proof
The regret in episode can be rearranged as:
D = / (V (s1) vyM, + (V (s1) - VV (s1)))dss
(4)
Note that conditioned upon history H2 for any k, M and M are identically distributed, Osband Van Roy 2014) showed that V.a. -
je_11 - is zero in expectation, and that only the second part of the regret decomposition need to be bounded when deriving the Bayesian regret of PSRL. Thus we can focus the policy (Ak, the sampled M and real environment data generated by M For clarity, the value function
yra is simplified to VE, and " to V suffices to derive bounds for any initial =
state as the regret bound will still hold through integration of the initial distribution p(s1).
We can rewrite the regret from concentration via the Bellman operator (see Section 5.1 in Osband et al. (013)):
E A [7x] == E[VE, - VE, (81))
(s1, - F" (81, + / av) - p ait [Hx]
-E (st, F" as) + > (1t + +x))))
P ('ds))))-(()) = (s'dds HHb)
(5)
where a; = (o((s)), 94t1 ~ (s, a.), (ss, F as,,,, (x)
Thus, here (st, a;) is the state-action pair that the agent encounters in the kth episode while using 14 for interaction in the real MDP M We can define VH.H-1 = 0 to keep consistency. Note that we cannot treat 8; and a; as determin- istic and only take the expectation directly random reward and transition functions. Instead, we need to bound the difference using concentration properties of reward and transition func- tions modeled as Gaussian Processes (which also applies to any state-action pair), and then derive bounds of this expectation. For all i, we have [P a.) P (s')s az)) a.)) R.44 (s")ds" ''s' < max, IV + (s)] pp (5'1s; a:)- (**'''<s (1)s ad) < H Hmar R [P (8' 1s,, a.)- - ( (s'(ss,, lds'.
DH ( ag) P*('''s;, a=
Now we present a lemma which enables us to derive a regret bound with explicit dependency on the episode length H.
Lemma For two multivariate Gaussian distribution N(u, TT),, "(4',a07) with probability density function pr (x) and p2(x:) respectively, a E TRd
f Imi(at) ppa())daa S
2
V To? |1 11
The proof is in Appendix A. Clearly, this result can also be extended sub-Gaussian noises.
Recall that pk (8'181, a;) = NN (81, az), o) and PM (8'18,, a:) = -N (81, r) By Lemma
1 we have
2 To?
as) (s(s)),, V
P*
115 (si,
(6)
Lemma (Rigollet & Hütter 2015) Let X1. XN be N sub- Gaussian random variables with variance a (not required to be independent). Then for any t > 0, P(mmxisisN [X,] > t) <
2Ne 2
Given history He, let (s) indicate the posterior mean of f a) in episode k and ( a) denotes the posterior variance of ft in each dimension. Note that f and fü share the same variance in each dimension given history Hy. as described Section 3. Consider all dimensions of the state space, by Lemma 2 have that with probability least 1 - 5, maxigisd, [f,
5

---

Under review as a conference paper at ICLR 2021
(s) & /2 24 Also, we can derive an upper bound for the norm of the state difference (s.f)) - - (s, S vd, maxigisa, (f, a) f. (s, a)l, and so does (lf a) (((sa))ll: since f" and f share the same posterior distribution. By the union bound, we have that with probability at least 26 (s, (ss. s 2 2d 2/
Then we look the sum of the differences over horizon H, without requiring each variable in the sum to be independent:
- - 2 2d log 2de)
2d.
H < (8), (s, =
2dl
a:)ll > 2/ 2d.0 a, log
(7)
No P() (s - (s,, > 2/ 2d [ a ylg 2dg
Thus, with probability at least 1 2 2d, (si, (s),;;))og 8- Let 2H6, we have that with probability 1 1 6, 5H / 11ll (st, (i)
2H8, we have 1 (si, a;) (s; d;) S
(s,,, I Σ 2 index kinaz arg max, (8;, az), i 1,.., H in episode k. Here, since the posterior distribution is only updated every H steps, we have to use data points with the max variance each episode to bound the result. Similarly, using the union bound for [ episodes, and let C
2f 2 a, aoo 2 atd S 2H / 22 akmaz Mlg LHd_ where the
-V=2? we have that with
V
probability at least x k== I S E + SH I OCHRmaas ( at) - (*, (1)ll s x! Kmm ICH2Rmaas v 2d ( Uemmaz ylo 4Td. 4Td.
In each episode k let ox² 2 a) denote the posterior variance given only subset of data points ((8 mme: 01 mm. (#k mear Ok- [k-1mm)))]] where each element has the max variance in the corre- sponding episode. By (6) in Williams & Vivarelli (2000),
know that the posterior variance reduces as the number of data points grows. Hence V(s, a), of( S (s, a). By Theorem 5 in Srrnivas et al. (2012) which provides a bound on the information gain, and Lemma 2 in Russo & Van Roy (2014) that bounds the sum of variances by the information gain, we have that
E 1 ( (lmmaz)
O(dds + dogg [ for linear kernels with bounded variances. Note that the bounded variance property for linear kernels only requires the range of all state-action pairs actually encountered in . not to expand to infinity as T grows, which holds in general episodic MDPs.
Thus with probability 1- 8, and let 8 $.
fl A (f) HN kk 2 Rmaz V od akmas Mog
4Td,
8
8CH22 OCH2Rmman do (Skmax s akemss )log(2Td.) Mg=
(8)
88CH² Rmaz v E 22 Almoaw /
T
(dglog(2Td.)
H
=CCH Rmaz VT dglog(2Tdd) x Volld, + da logl 1 = Ö((ds + da) do)Hi
where Ô ignores logarithmic factors.
Therefore, E (e) < (1 - + ( + +. + where 2H Rax is the upper bound on the difference of value functions, and = de + dg. By similar derivation, E| (r)) Ō(VarT). Finally, through the tower property we have ReyeeRR TP MM) ((H.dT))
1 22H
[ Ö(HādvT)

---

Under review as a conference paper at ICLR 2021
Algorithm I MPC-PSRL
Initialize data D with random actions for episode repeat
Sample a transition model and cost model at the beginning of each episode
for = 1 to H steps do
Obtain action using MPC with planning horizon T: Oa arg maxaget Eist R(r(s), at)
D = D J {(5s, ag, Ts. $141)
end for
Train cost and dynamics representations o, and øy using data in DD
Update (s, a), Φ (s, a) for all (s, a) collected
Perform posterior update of w, and Wy in cost and dynamics models using updated representa- tions (, a), o (s, a) for all (s, a) collected until convergence
4.2 NONLINEAR CASE VIA FEATURE REPRESENTATION
We slightly modify the previous proof derive the bound in settings that use feature representa- tions. We can transform the state-action pair (s, to ( a) Rd as the input of the transition model, and transform the newly transitioned state s' to y E Rd as the target, then the transition model can be established with respect to this feature embedding. We further assume de O(g)) as Assumption 1 in Yang & Wang 2019). Besides, we assume dø = O(dg) in the feature representation (,,8,, a) E Ra then the reward model can also be established with respect to the feature embedding. Following similar steps, we can derive Bayesian regret of 0(1 do
ALGORITHM DESCRIPTION
In this section, we elaborate proposed algorithm, MPC-PSRL, shown in Algorithm |
5.1 PREDICTIVE MODEL
When model the rewards and transitions, we use features extracted from the penultimate layer of fitted neural networks, and perform Bayesian linear regression on the feature vectors to update posterior distributions.
Feature representation: we first fit neural networks for transitions and rewards, using the same network architecture as Chua et al. 2018 Let x; denote the state-action pair (s;, az) and yı denote the target value. Specifically, we use reward r; as z4 to fit rewards, and we take the difference between two consecutive states 81+1 8; as y: fit transitions. The penultimate layer of fitted neural networks is extracted as the feature representation, denoted as Øy and o for transitions and rewards, respectively. Note that in the transition feature embedding, to extract features of state-action pairs from the penultimate layer to serve as Φ, and leave the target states without further feature representation (the general setting is discussed in Section 4.2 where feature representations are used for both inputs and outputs), so the dimension of the target in the transition model d(v)) equals to dz. Thus we have modified regret bound of 0(13//2 ((H3//2/dd.2T) ddd We do not find the necessity further extract feature representations in the target space, it might introduce additional computational overhead. Although higher dimensionality of the hidden layers might imply better representation, we find that only modifying the width of the penultimate layer to do = d. + 8a suffices in our experiments for both reward and transition models. Note that how to optimize the dimension of the penultimate layer for more efficient feature representation deserves further exploration.
only use neural network
Bayesian update and posterior sampling: here we describe the Bayesian update of transition and reward models using extracted features. Recall that Gaussian process with linear kernels is equivalent to Bayesian linear regression. By extracting the penultimate layer as feature representation ø. the target value y and the representation Φ(z) could be e is a zero-mean Gaussian noise with variance o² (which is of for the transition model and of for the reward model as defined in Section 3.1). We choose the prior distribution of weights as zero-mean
linearly related: y w d(x) + c, where
7

---

Under review as a conference paper at ICLR 2021
-100
-100
15X
-30
-17
-002
1200
190
2530
300
300
3030
20000
2008
20003
1300
200
2010
300
1900
000
120
-200
-143
1852
3022
56.5
130
830
Figure 1: Training curves of MPC-PSRL (shown in red), and other baseline algorithms in different tasks. Solid curves are the mean of five trials, shaded areas correspond to the standard deviation among trials, and the doted line shows the rewards convergence.
Gaussian with covariance matrix Ep. then the posterior distribution of is also multivariate Gaussian (Rasmussen (000)))
D(w)D) 2A 1-
where A = o 20 + +Ip' Rdx the concatenation of feature representations (ø(z;) M and Y R.N is the concatenation of target values. At the beginning of each episode, we sample w from the posterior distribution to build the model, collect new data during the whole episode, and update the posterior distribution of w at the end of the episode using all the data collected.
Besides the posterior distribution of w, the feature representation with new data collected. We adopt similar dual-update procedure as Riquulmee et al. (2018): after representations for rewards and transitions are updated, feature vectors of state-action pairs collected are re-computed. Then apply Bayesian update these feature vectors. See the description of Algorithm for details.
also updated each episode
5.2 PLANNING
During interaction with the environment, for planning. At each time step i, the controller takes state s, and an action sequence a;ri+7 {a,, a.41. (4+r) } as the input, where is the planning horizon. We transition and reward mod- els to produce the first action a, the sequence of optimized actions arg maxa..1 Σie E[r(s, at)], where the expected return of a series of actions can be approximated using the mean return of several particles propagated with noises of our sampled reward and transition models. To compute the optimal action sequence,
MPC controller (Camacho & Alba (0033)
CEM (Botev et al. (2013)), which samples actions from distribution closer to previous action samples with high rewards.
EXPERIMENTS
We compare our method with the following state-of-the art model-based and model-free algorithms on benchmark control tasks.
Model-free: Soft Actor Critic (SAC) from Haarnoja et al. (2018) is an off-policy deep actor-crite critic algorithm that utilizes entropy maximization to guide exploration. Deep Deterministic Policy Gradient
(DDPG) from Barth-Maron et al. (018) is an off-policy algorithm that concurrently learns a Q- function and policy, with discount factor to guide exploration.
8

---

Under review as a conference paper at ICLR 2021
Model-based: Probabilistic Ensembles with Trajectory Sampling (PETS) from Chua et al. (2018) models the dynamics via an ensemble of probabilistic neural networks to capture epistemic uncertainty for exploration, and uses MPC for action selection, with requirement to have access oracle rewards for planning. Model--ased Policy Optimization (MBPO) from fromJanner Janner et al. (2019) uses the same bootstrap ensemble techniques PETS in modeling, but differs from PETS in policy optimization with a large amount of short model-generated rollouts, and can cope with environments with no oracle rewards provided. We do not compare with Gal et al. (2016), which adopts single Bayesian neural network (BNN) with moment matching, as it is outperiormed by PETS that uses an ensemble of BNNs with trajectory sampling. And we don't 't compare with GP-based trajectory optimization methods with real rewards provided (Deisenroth & Rasmussen 2011 Kamthe & Deisenroth 2018)) which are not only outperformed by PETS, but also computationally expensive and thus are limited to very small state-action spaces.
We use environments with various complexity and dimensionality for evaluation. Low-dimensional environments: continuous Cartpole (d, = 4, d., = 1, H 200, with a continuous action space compared to the classic Cartpole, which makes it harder to learn) and Pendulum Swing Up (dg = 3, da = 1, H 200, modified version of Pendulum where limit the start state make it harder for exploration). Trajectory optimization with oracle rewards in these two environments is easy and there is almost no difference in the performances for all model- algorithms we compare, so we omit showing these learning curves. Higher dimensional environments: 7-DOF Reacher (d. d4 7, H 150) and 7-DOF pusher (d, 20, de = 7, H 150) are two more challenging tasks as provided in Chua et al. (2018), where we conduct experiments both with and without true rewards, to compare with all baseline algorithms mentioned.
The learning curves of these algorithms are showed in Figure I When the oracle rewards are provided in Pusher and Reacher, our method outperforms PETS and MBPO: it converges more quickly with similar performance at convergence in Pusher, while in Reacher, not only does it learn faster but also performs better at convergence. As we use the same planning method (MPC) as PETS, results indicate that our model better captures uncertainty, which is beneficial to improving sample efficiency. When exploring in environments where both rewards and transition are unknown, our method Iearns significantly faster than previous model-based and model-free methods which do no require oracle rewards. Meanwhile, it matches the performance of SAC at convergence. Moreover, the performances of our algorithm in environments with and without oracle rewards can be similar, even faster convergence (see Pusher with and without rewards), indicating that our algorithm excels at exploring both rewards and transitions.
From experimental results, it can be verified that our algorithm better captures the model uncertainty, and makes better use of uncertainty using posterior sampling. In our methods, by sampling from Bayesian linear regression on fitted feature space, and optimizing under the same sampled MDP in the whole episode instead of re-sampling every step, the performance of our algorithm is guaranteed from a Bayesian view as analysed in Section 4 While PETS and MBPO use bootstrap ensembles of models with limited ensemble size to "simulate" a Bayesian model, in which the convergence of the uncertainty is not guaranteed and is highly dependent on the training of the neural network. However, in our method there a limitation of using MPC, which might fail even higher-dimensional tasks shown in Janner et (201)). Incorporating policy gradient techniques for action-selection might further improve the performance and we leave it for future work.
7 CONCLUSION
In our paper, we derive a novel Bayesian regret for PSRL algorithm in continuous spaces with the assumption that true rewards and transitions (with or without feature embedding) can be modeled by GP with linear kernels. While matching the best-known bounds in previous works from a Bayesian view, PSRL also enjoys computational tractability. Moreover, propose MPC-PSRL in continuous environments, and experiments show that our algorithm exceeds existing model-based and model-free methods with more efficient exploration.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. arXiv preprint arXiv: 000117733444444 2017.
Kamyar Arizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through bayesian deep q-networks. In 20/8 Information Theory and Applications Workshop (TTA), pp. 1-9. IEEE, 2018.
Gabriel Barth- Martn,, Matthew W Hoffman, David Budden, Will Dabney, Dan Horgan, Dhruva Tb, Alistair Muldal, Nicolas Heess, and Timothy Lillicrap. Distributed distributional deterministic policy gradients. arXiv preprint a 1804.08617. 2018.
Zdravko I Botev, Dirk P Kroese, Reuven Y Rubinstein, and Pierre L' L'Ecuyer. The cross-entropy method for optimization. In Handbook of statistics, volume 31, pp. 35-59. Elsevier, 2013.
Eduardo Camacho and Carlos Bordons Alba. Model predictive control. Springer Science & Business Media, 2013.
Sayak Ray Chowdhury and Aditya Gopalan. Online learning in kernelized markov decision processes. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3197-3205, 2019.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in a handful of trials using probabilistic dynamics models. In Advances in Neural Information Processing Systems, pp. 4754 4765, 2018
Mare Deisenroth and Carl Rasmussen. Pilco: A model-based and data-efficient approach to policy search. In Proceedings of the 28th International Conference machine learning (ICML-II, pp. 465-472, 2011.
Yarin Gal, Rowan McAllister, and Carl Edward Rasmussen. Improving pilco with bayesian neural network dynamics models. In Data-Efficient Machine Learning workshop, ICML., volume 4, pp. 34, 2016.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maxi- mum entropy deep reinforcement learning with a stochastic actor, arXiv preprint arXiv:1801.00 01290. 2018.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563-160)) 2010.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. In Advances in Neural Information Processing Systems, pp. 12498-12509, 2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learnig provably efficient? In Advances Neural Information Processing Systems, pp. 1863348774 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143, 2020.
Sanket Kamthe and Marc Deisenroth. Data-efficient reinforcement learning with probabilistic model predictive control. In International Conference on Artificial Intelligence and Statistics, pp. 1701-1710. PMLR, 2018
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances Neural Information Processing Systems, pp. 1466-147 1474, 2014.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, pp. Australia, 2017. PMLR
International Convention Centre, Sydney,
10

---

Under review as a conference paper at ICLR 2021
Ian Osband, Van Roy Benjamin, and Russo Daniel. (More) efficient reinforcement learning via posterior sampling. In Proceedings of the 26th International Conference on Neural Information Processing Systems Volume 2, NIPS 13, pp.
USA, 2013. Curran Associates Inc.
lan Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62, 2019.
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer School on Machine Learning, pp. 63-71. Springer, 2003.
Phillippe Rigollet and Jan-Chin Christian Hütter. High dimensional statistics. Lecture notes for course 18$997, 2015.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. arXiv preprint arXiv:1802.0912 2018.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, (9(44)1221-11)) 2014.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias W Seeger. Information-theorres regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory, 3855:3250- 2012.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4) 1933.
Christopher KI Williams and Francesco Vivarelli. Upper and lower bounds on the learning curve for gaussian processes. Machine Learning. 4071)177-102, 2000.
Lin F Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. arXiv preprint arXiv:1905. 10389, 10389, 2019.
Andrea Zanette, Alessandro Lazaric. Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. arXiv preprint arXiv:2003.00153, 2020.
A
APPENDIX
A. PROOF OF LEMMA
Here provide proof of Lemma] 1
(((()) We first prove the results in Rd with d 1: pı(2) N(μ, p2(x) ~ ~N('l without loss of generality, assume μ² 2 μ. The probabilistic distribution is symmetric with regard to kty', Note that (x) = (2)) at x = 2 Thus the integration of absolute difference between pdf of pı and p2 can be simplified twice the integration of one side:
2
w)²
P2(x) (i(x)
2-
20
dx
2
let 21 ,1 22
E n1, have:
2
(1-p'12 2
-(x-1))
dx
2
3o d
é 20
dzy
nO?
TO? L'
(10)
p
6 20 dz
2
2/
20 dz
< 2/
1dz = -
Vo
2 14/.
TT2
T
11

---

Under review as a conference paper at ICLR 2021
NN'', We can rotate the coordinate system recursively to align the last axis with vector μ - μt, such that the coordinates of μ and p¹ can be written as (0, 0, ..................... 0, pt), and (0,0, ,², respectively, with 1 - j = || - 1 Without loss of generality, let j jt'.
Now extend the result to [d 2 2): (1(x) ~ M
Clearly, all points with equal distance to jí' and define hyperplane P Fd A where Pr (1:) = (2),), Vr E P. More specifically, the probabilistic distribution symmetric with regard to P. Similar the analysis R
(1)
(2) drd
00
2
100
00
- -(m-0))
2n
...e 20
20
de dridzz ... dad
(2
00
-lag- 20
... 20
dx dip ... dxd
(22))002d
(11)
2
-
0
-(ra-
2s2
20 dz1
6 2 de2 1..
dr 20
20
dea
V22Ty022
àids
-00
-2
-17
10
-2
6 2nd dr
2
dx2
e dx
e
daa
(2 (2nT)o22
ptpp
2
000
-(=a-p012
20
drd
202
dx.))
TO2
2222
let 21
f1,22 =
f,' we have:
00
(Fg=A)²
pc0
-1x
20
dr
20
dxd
6 d21
6
220
de2
R-
A-p!
(12)
2 dz
6
A
Anf
2
dz
Idz
00
50
112
f!'l
2 Thus 100 100 ... 200 (x(()) po(x))da,dar da S v No
1|I 1lll2
A.2 EXPERIMENTAL DETAILS
Here provide hyperparameters for MBPO:
12

---

Under review as a conference paper at ICLR 2021
env
cartpole
pendulum
pusher
reacher
steps
200
200
150
150
per episode
model rollouts
400
per env step
ensemble size
MLP with
MLP with 2 hidden layers size 200
MLP with
MLP with 4 hidden layers of size 200
network architecture
hidden layers
hidden layers of size 200
of size 200
policy updates
40
per env step
1->15 from episode 1->30
1->15 from episode 1->30
1->1 15 from episode 1->30
model horizon
Table 1: Hyperparamters for MBPO
And we provide hyperparamters for MPC and Neural Networks in PETS:
pusher
reacher
env steps
150
150
per episode
popsize
500
400
number
50
of elites
MLP with
network
hidden layers
architecture
of size 200
planning
30
horizon
max iter
5
ensemble size
5
Table 2: Hyperparamters for PETS
Here are hyperparameters of our algorithm, which similar with PETS, except for ensemble size(since we do not use ensembled models):
env
cartpole
pendulum
pusher
reacher
env steps
200
200
150
150
per episode
popsize
500
100
500
400
number
50
5
50
50
of elites
MLP with hidden layers of size 200
MLP with 2 hidden layers of size 200
MLP with hidden layers of size 200
MLP with hidden layers
network architecture
of size 200
planning horizon
30
20
30
30
max iter
Table 3: Hyperparamters for our method
For SAC and DDPG, we the open source code (https://github cwm comm/donminneee deep_ri) for implementation without changing their hyperparameters. We appreciate the authors for sharing the code!
13


Reviews:
[{"review_id": "tmZSR-Q_Qf", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review\nThis paper proposes a new model-based reinforcement learning algorithm named MPC-PSRL. Theoretically, the authors provide regret analysis of the proposed algorithm. The authors also provide empirical results that MPC-PSRL outperforms other previous model-based RL algorithms, such as PETS or MBPO.\nHowever, it is not clear that the main contribution of this paper. Osband & Van Roy (2014) already provides the algorithm posterior sampling RL algorithm, named PSRL for continuous domain. If posterior distribution of MDP is modeled as GP and optimal policy is computed by MPC, then it is the same as the method in this paper. They also provide regret analysis for continuous domain with sub-Gaussian noise model. What are the major difficulties / differences compared to the previous work?\nQuestions:\nIs there any reason there are no empirical results on Pendulum and Cartpole with oracle rewards?\nTo emphasize the effect of posterior sampling (maybe exploration), would you provide the results that using just mean instead of sampling? It is not clear whether both GP modeling and exploration via posterior sampling have a significant impact on performance.\nTypos:\nUse \\sigma_R with \\sigma_r / \\sigma_P with \\sigma_f\nTheorem 1 in page 3, d_\\phi should be d.\nIn proof of theorem 1, what is the definition of \\delta_k(r) and \\delta_k(f)?\n\nscore: 5 -> 6", "extra_scores": {}, "extra_text": {}}, {"review_id": "UaLb_g15XwI", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a model-based posterior sampling algorithms with regret guarantees when the model is assumed to be drawn from a distribution randomly. The authors also provide numerical evaluations of the proposed method.\n\n- The contribution of this work as theoretical work is limited. There is no study on fundamental limit. In addition, the performance guarantee seems worse than existing ones, although a fair comparison might be unavailable due to different technical assumes. However, the authors do not provide numerical comparison to existing algorithms with performance guarantee.\n\n- It is not possible to assess the contribution from numerical comparison. There is no description on the hyperparameter selection of other algorithms (PETS, MDPO, SAC, ...). Hence, it is not reproducible as well.\n\n- The definition of $BayesRegret$ seems incorrect as it takes $M^*$ as input argument. The authors need to describe what they mean by the expectation in eq. (3). In my understanding, $BayesRegret$ should take hyper-parameter to generate $M^*$ as input, while $Regret$ taking a random incidence of $M^*$ as input.\n\n- I don't understand the meaning of regret bound $\\tilde{O} (H^{3/2} d_\\phi T)$ for non-linear case as regret of any algorithm is upper-bounded by $R_{max} T$.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6wnlx6pUqJ0", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Pros\n--------\n* The paper proposes a method to balance exploration and exploitation in reinforcement learning problems whose transitions and rewards are assumed to be sampled from Gaussian processes, and provide a Bayesian regret bound. Also, the paper shows how the proposed approach can be implemented in practice using model predictive control.\n \nCons\n--------\n* It is not clear what is the novelty of the theoretical results in this paper when compared to the regret bounds by Chowdhury & Gopalan (2019), who provide both frequentist and Bayesian bounds when the transitions and rewards are in an RKHS or sampled according to a GP. The bound of Chowdhury & Gopalan (2019) seem to be polynomial in the horizon H (their paper mention a $HSA\\sqrt{T}$ bound in the particular case of finite MDPs), whereas the current paper says that \"H is still unbounded\" in their result. Hence, further clarification is needed regarding this point. \n* The method is claimed to be computationally tractable: “it can be easily implemented by only optimizing a single sampled MDP”. However, the sampled MDP is continuous, and solving a continuous MDP is hard in general. Experimentally, the paper proposes the cross entropy method (CEM) for planning: in this case, planning is not exact and the regret bound does not hold anymore. I believe this issue should be made clear in the introduction/related work section. \n* Although my main concern is the theoretical novelty, the experimental section can be improved: it would be interesting to compare the proposed approach to other strategies for exploration in deep RL, for instance\n    * Bellemare et al. (2016), Unifying Count-Based Exploration and Intrinsic Motivation\n    * Tang et al. (2017), #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning\n    * Azizzadenesheli et al. (2018), Efficient Exploration through Bayesian Deep Q-Networks;\nand also perform experiments in small simple environments that satisfy the assumptions to check if the regret is sublinear (e.g. a continuous “grid world” with noisy transitions). \n* In the nonlinear case (Section 4.2) it is not clear how to follow the steps of Yang & Wang (2019) to derive a Bayesian regret bound with feature representation, since their assumption is related to low-rank MDPs instead of Gaussian processes. In addition, it would be interesting to discuss how the model would be sampled (in Algorithm 1) in this case.\n \n \nSuggestions & remarks\n------------------------------------------------------\n* Introduction: mention which of the cited papers proves the $H \\sqrt{SAT}$ upper bound on the Bayesian regret, clarify whether $T$ is the number of episodes, or $H$ times the number of episodes. \n* Some definitions are missing:\n    * The linear kernel should be defined before Theorem 1\n    * $M^k$ is not defined before appearing in Eq. 5\n* Increase the font size of the text in Figure 1. \n* In Algorithm 1, include what are the input parameters (e.g. $\\sigma_r, \\sigma_f$). \n* Some suggestions for the proof:\n     * Write the relation between $\\Delta_k$ and $\\tilde{\\Delta}_k$.\n    * Include (possibly in the appendix) more details about the arguments in the paragraph below Eq. 9. For instance, there is an argument about a bound on the information gain, which is not defined in the paper.  Also, it might be useful (for the reader) to restate (in the appendix) the results by Williams & Vivarelli (2000), Srinivas et al. (2012) and Russo & Van Roy (2014) required for the proof.\n \nTypos\n---------\n* Abstract: $T$ instead of $\\sqrt{T}$ in the regret bound with feature representation \n* Page 9: Definition of MBPO, it should be “Model-Based Policy...” \n* Typo in integration limits in Eq. 12   (the $\\mu'-\\mu$ at the bottom should be $\\mu-\\mu'$).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1alHfZY87Hp", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the model-based reinforcement learning. They propose a posterior sampling algorithm and provide a Bayesian regret guarantee. Under the assumption that the reward and transition functions are Gaussian processes with linear kernels, the regret bound is in the order of H^1.5 d sqrt{T} where H is the episode length. The dependence that regret is in polynomial of H is a nice property. However, this advantage seems to be obtained by the assumption of Gaussian processes with linear kernels. Besides, I have the following comments.\n\n1) It seems that the result in Theorem 1 is quite straightforward from the results in Osband & Van Roy 2014. Could you justify your contribution in this result.\n\n2) What is MPC? Suppose to be model predictive control? It is not officially introduced in the context.\n\n3) In terms of computational complexity, could you elaborate more on the computational complexity of each line (component) of the algorithm. For general cases, posterior sampling could also be expensive as there are no closed-form solutions, one may need to use MCMC method.  ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a model-based posterior sampling algorithm in continuous state-action spaces theoretically and empirically. The work is interesting and the authors provide numerical evaluations of the proposed method. But the reviewers find the contribution of the work limited.

Decision: Reject