NeoRL: Efficient Exploration for Nonepisodic RL
Authors: Bhavya Sukhija
Lenart Treven
Florian Dorfler
Stelian Coros
Andreas Krause
Venue: NeurIPS 2024 spotlight (2024)
Keywords: reinforcement learning
single trajectory
nonepisodic setting
average cost MDP
Primary area: reinforcement_learning

Abstract: We study the problem of nonepisodic reinforcement learning (RL) for nonlinear dynamical systems, where the system dynamics are unknown and the RL agent has to learn from a single trajectory, i.e., without resets. We propose **N**on**e**pisodic **O**ptistmic **RL** (NeoRL), an approach based on the principle of optimism in the face of uncertainty. NeoRL uses well-calibrated probabilistic models and plans optimistically w.r.t. the epistemic uncertainty about the unknown dynamics. Under continuity and bounded energy assumptions on the system, we
provide a first-of-its-kind regret bound of  $\mathcal{O}(\beta_T \sqrt{T \Gamma_T})$ for general nonlinear systems with Gaussian process dynamics. We compare NeoRL to other baselines on several deep RL environments and empirically demonstrate that NeoRL achieves the optimal average cost while incurring the least regret.

NEORL: Efficient Exploration for Nonepisodic RL
Bhavya Sukhija", Lenart Treven, Florian Dörfler, Stelian Coros, Andreas Krause ETH Zurich, Switzerland
Abstract
We study the problem of nonepisodic reinforcement learning (RL) for nonlinear dynamical systems, where the system dynamics are unknown and the RL agent has learn from a single trajectory, i.e. adapt online and without resets. This setting ubiquitous in the real world, where resetting is impossible or requires human inter- vention. We propose Nonepisodic Optimistic RI. (NEORL.), an approach based on the principle of optimism in the face of uncertainty. NEORL. uses well-calibrated probabilistic models and plans optimistically w.r.t. the epistemic uncertainty about the unknown dynamics. Under continuity and bounded energy assumptions on the system, we provide first-of-its-king kind regret bound of (3TVVTTT) for general nonlinear systems with Gaussian process dynamics. We compare NEoRL other baselines on several deep RL environments and empirically demonstrate that NEORL achieves the optimal average cost while incurring the least regret.
Introduction
In recent years, data-driven control approaches, such as reinforcement learning (RL), have demon- strated remarkable achievements. However, most RL algorithms are devised for an episodic setting, where during each episode, the agent interacts in the environment for predetermined episode length or until termination condition is met. After the episode, the agent is reset back to an initial state from where the next episode commences. Episodes prevent the system from blowing up, i.e., maintain stability, while also restricting exploration to states that are relevant to the task at hand. Moreover, resets ensure that the agent explores close to the initial states and does not end up at undesirable parts of the state space that exhibit low reward. In simulation, resetting is typically straightforward. However, if we wish to enable agents to learn and adapt by interacting online with the real world, resets are often prohibitive since they typically involve manual intervention. Instead, agents should be able to learn autonomously (Sharma et al., 2021b) i.e., from a single trajectory. This problem is extensively studied in adaptive control (Aström & Wittenmark, 2013), where classical works focus on controller design (Lai & Wei, 1982, 1987; Krstić et al., 1992, 1995; Annaswamy, 2023) and not on the exploration/ccariing aspect of the problem. Only a few works consider these two aspects jointly (Abbasi-Yadkori & Szepesvári, 2011; Cohen al., 2019; Dean al., 2020; Simchowitz & Foster, 2020; Zhao et al., 2024). However, these works study linear systems with quadratic costs, i.c., the LQR setting. While several works in the Deep RL community have also studied this problem, (c.f., Section 5), the theoretical results for this setting are fairly limited. In particular, theoretical results mostly exist for the finite state and action spaces (Kearns & Singh, 2002; Brafman & Tennen- holtz, 2002; Jaksch et al., 2010) and the extension to nonlinear systems with continuous spaces is much less understood. In work, address this gap and propose practical RI. algorithm that is grounded in theory. In particular, we make the following contributions. Contributions
1.
We propose, NEORL,, a novel model-based RL algorithm based on the principle of optimism in the face of uncertainty. NEORL operates in a nonepisodic setting and picks average cost optimal policies optimistically w.r.t. to the model's epistemic uncertainty.
"Correspondence sukhi jabeth.ah
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

2. We show that when the dynamics lies in reproducing kernel Hilbert space (RKHS) of kernel k, NEORL exhibits a regret of (3TVVTTT) where the regret, akin prior work, is measured w.r.t to the optimal average cost under known dynamics, T is the number of environment steps, fr the calibration coefficient (Chowdhury & Gopalan, 2017; Srinivas et al., 2012) and r the maximum information gain of kernel k (Srinivas et al., 2012). Our regret bound is similar to the ones obtained in the episodic setting (Kakade et al., 2020; Curi et al., 2020; Sukhija et al., 2024; Treven et al., 2024) and Gaussian process (GP) bandit optimization (Srinivas al., 2012; Chowdhury & Gopalan, 2017: Scarlett et al., 2017) and is sublinear for common kernel such as the exponential kernel. To the best of our knowledge, we are the first obtain regret bounds for the setting.
3. We evaluate NEORL on several RL benchmarks against common model-based RL baselines. Our experimental results demonstrate that NEORL consistently achieves sublinear regret, also when neural networks are employed instead of GPs for modeling dynamics. Moreover, in all our experiments, NEORL converges to the optimal average cost.
2 Problem Setting
We consider a discrete-time dynamical system with running costs C.
1++1 = f (az,, u+) - Wh, (I2,, Ut) E X' x U, 2(0) = Zo
(1)
c(x:, u) Rg0
(Running cost)
Here Ft E X' C Rd= is the state, u, EU C Ré the control input, and w, W C R the process noise. The dynamics f are unknown and the cost e assumed be known.
Task In this work, we study the average cost RL problem (Puterman, 2014), i.e., we want to learn the solution to the following minimization problem
1
A(T", (0o) min A(T, mo) = min lim
Hell T-+000 T Ex
Σ clar, u.)
Moreover, consider the nonepisodic RL setting where the system starts an initial state we X but never resets back during learning, that is, we seek to learn online from a single trajectory. After each step / in the environment, the RL system receives transition tuple (ax,, ue #z+1) and updates its policy based on the data D, collected thus far during learning. The average cost formulation is common for the nonepisodic setting (Jaksch et al., 2010; Abbasi-Yadii & Szepesvári, 201 I: Cohen et al., 2019; Dean et al., 2020; Simchowitz & Foster, 2020), and the cumulative regret for the learning algorithm in this case is defined
T-1 R
Σ 1=
Ex, u Ing [c(2,, l u.) - A(T"., x.)]]
Studying the average cost criterion for general continuous state-action spaces is challenging even when the dynamics are known, since the average cost exists only for special classes of nonlinear systems (Arapostathis et al., 1993). In the following, we impose assumptions on the dynamics and policy class that enable our theoretical analysis.
2.1 Assumptions
Imposing continuity on f is quite common in the control theory (Khalil, 2015) and reinforcement learning literature (Curi et al., 2020; Sussex et al., 2023; Sukhija et al., 2024). To this end, for our analysis, make the following assumption.
Assumption 2.1 (Continuity of f and тT) The dynamics model f and all π E II are continuous.
Next, we make assumption the system's stochastic disturbances.
Assumption 2.2 (Process noise distribution). The process noise is i.i.d. Gaussian with variance o², i.e., we
i.i.d ~ (0,,
Our analysis can be extended for the more general heteroscedastic case, where depends on ar. However, for simplicity, we focus on the homoscedastic setting. In the following, we make assumptions policy class. To this end, we first introduce the class of XCoo functions.

---

Definition 2.3 (Kxs-funntionns) The function & R20 + Rzo is of class Ko if it is continuous, strictly increasing, {(0) 0 and {(s) + oo for - oC. Assumption 2.4 (Policies with bounded energy), We assume there exists K, Koo positive constants K, C.. Ct with C > C₁. and y E (0, 1) such that for each π E II we have,
Bounded energy: There exists a Lyapunov function V : X - [0, oo) for which Va, x' E A,
|V (z) - V (z')) - k(1 x - æ'I)
(uniform continuity)
CrE([==I]) 2 V CuE((==])
(positive definiteness) (drift condition)
Em (V [x+)] - 7V (x))++++
where 2.4 = (ar (m=) + u.
Bounded norm of cost:
dx, π (2:)
sup
<
#EX 1 + V (x)
Boundedness of the noise with respect to
En [<][[[]]]]] < xo, En [x=2(1=0]]] <0
The drift condition states that the energy between particular, the Lyapunov function ! can be viewed as an energy function for the dynamical system, and the bounded energy condition above ensures that the system is not "blowing up". We do not perceive this as restrictive for real-world engineered systems. Other works that study learning nonlinear dynamics (Foster al., 2020; Sattar Oymak, 2022: Lale et al., 2021) in the nonepisodic setting also make stability assumptions such as global exponential stability for their analysis. In similar spirit, we make the bounded energy assumption for our policy class. The drift condition on the Lyapunov function is also used to study the ergodicity of Markov chains for continuous state spaces (Meyn & Tweedie, 2012; Hairer & Mattingly. 201 1), which is crucial for our analysis of the infinite horizon behavior of the system. Moreover, for very rich class of problems, the drift. condition satisfied. We highlight this in the corollary below.
timesteps increase most by K. In
Lemma 2.5. Assume f is uniformly continuous and for all π I1, X. || < Umax- Further assume, there exists n, E 11 such that we have constants K, Cu. Ci with Cu > C₁ 7 E (0, K. a E Koo and a Lyapunov function V X - [0, 20) for which Vaz, x' E X,
V(x) V(x') ) S n<[1=x - =x1l)
CEE(|= () S V(w) S C=E((==]) Ex 1., (V (x++) S (v)))++++
where x+ fx, + w. Then, V also satisfies the drift condition for all π E II, i.e. is Lyapunov function for all policies.
We prove this lemma in Appendix A. Intuitively, if the inputs are bounded, the energy inserted into the system by another policy also bounded. Nearly all real-world systems have bounded inputs due to the physical limitations of actuators. For these systems, it suffices if only one policy in II satisfies the drift condition.
The boundedness assumptions for the cost and the noise in Assumption 2.4 are satisfied for rich class of cost and ACso functions.
Under these assumptions, we can show the existence of the average cost solution.
Theorem 2.6 (Existence of Average Cost Solution). Let Assumption 2.1 --1-2. -2.4 hold. Consider any E II and let pd denote its transition kernel, i.e., pn (a. P2 Alaæ, π (z)) for C X. Then pa admits a unique invariant measure P", and there exists Cz, C33 co), X E (0,1) such that
Average Cost;
T
A(T) = lim E
Σ 1=0
cla,, uz)
= Ex- [c(æ, π (x))]
T- T
3

---

Bias Cost; Letting (TT, xo) limy +00 En -t= cez, uz)
A(T)
denote the bias, we have
1
BTTT S S2 V (xo))
for all æo X.
Theorem 2.6 is a crucial result for our analysis since it implies that the average cost is bounded and independent of the initial state Vn. Furthermore, it also shows that the bias is bounded. The average cost criterion satisfies the following Bellman equation (Puterman, 2014) below
( x) A(T) c(x, π (<)) + E., [B(T, 2x)] T]
Accordingly, the bias term plays important role in the regret analysis (also notice its similarity our regret term in Equation (3)).
Thus far, have only made assumptions that make the average cost problem tractable. In the following, we make an assumption on the dynamics that allow us to learn it from data. Moreover, we assume that at each step we learn mean estimate JAn of f and can quantify our uncertainty o over the estimate. More formally, we learn a well-calibrated statistical model f as defined below.
Definition 2.7 WWell-calibrated statistical model of f", Rothfuss et al. (2023)). Let 2 def X U. An all-time well-calibrated statistical model of the function f is sequence (.M, n20 where
(5) def {f 2 d Vz Vj d,....dz dz (2) f,(=)1 - B, ())
if, with probability at least 8, we have f E 0 Mn Here, fn. Pn.j and on.j denote the j-th element in the vector-valued functions f. fln and o respectively, and 8, E Rzo is scalar function that depends the confidence level 5 E (0, 1] and which is monotonically increasing in
Next, we assume that f" resides in Reproducing Kernel Hilbert Space (RKHS) of vector- valued functions and show that this is sufficient for us obtain a well-calibrated model.
Assumption 2.8. We assume that the functions fj.j 1,..., dy lie in RKHS with kernel and have a bounded norm B, that is f E BRB. with H = {f l1fll S B.j I,..., d Moreover, assume that k(æ, æ)) S Tmax for all x X.
Assumption 2.8 allows us to model fr with GPs for which the mean and epistemic uncertainty (1,,(2)= = [In. and (2)) ) no (())(2))))))) (z)lisa,) have an analytical formula
(z) k (z) Kn + +=21)= "i... (2.(2) k(x, ω) k.T (K), + 1- kn,),,
Here, yin corresponds to the noisy measurements of fj. i.e., the observed next state from the transitions dataset Dı.,, kn = [k(z, 2. )isssr 2, Di.n. and K, [k(z,, (((z,,,)]l..ee =1)l,.snT 2,, E Din the data kernel matrix. The restriction on the kernel k(x x) S maxx implies boundedness of f and has also appeared in works studying the episodic setting for nonlinear systems (Mania et al., 2020; Kakade al., 2020; Curi et al., 2020; Sukhija al., 2024; Wagenmaker et al., 2023). We can also define f such that Øy = Ix-1 + f (# - 11 + = in which case the boundedness. of f" captures many real-world systems.
Lemma 2.9 (Well calibrated confidence intervals for RKHS, Rothfuss et al. (2023)). Let f E H Suppose phn and on are the posterior mean and variance of a GP with kernel k, cff, Equation (5). There exists (5) x for which the tuple (p Bn (r())) is a well-calibrated statistical model of f
In summary, in the RKHS setting, a GP a well-calibrated model. For more general models like Bayesian neural networks (BNNs), methods such as Kuleshov et al. (2018) can be used for calibration. Our results can also be extended beyond the RKHS setting to other classes of call-calibrated models similar to Curi et al. (2020).

---

Algorithm NEORL: NONEPISODIC OPTIMISTIC RL
Init: Aleatoric uncertainty Probability 6, Statistical model (Ho. oo, Ba())), Ho
for 1,..., N do
n arg mim min A(T, f) *E JEM, inMo
Prepare policy
Hn -HHn11
Set horizon
D, f ROLLOUT(T.))
Collect measurements for horizon H
Update (Kes Nn. Bp) Dn
Update statistical model Mn
end for
3 NEORL
In the following, we present our algorithm: Nonepisodic Optimistic RL (NEORL) for efficient nonepisodic exploration continuous state-action spaces. NEORL builds on recent advances in episodic RL (Kakade et al., 2020; Curi et al., 2020; Sukhija et al., 2024; Treven et al., 2024) and leverages the optimism in the face of uncertainty paradigm to pick policies that are optimistic w.r.f. the dynamics within our calibrated statistical model as follows
(Tns
def
min A).,
(6)
TETT, FEM, 1nMo
Here, fu is a dynamical system such that the cost by controlling fn with its optimal policy л, is the lowest among all the plausible systems from M, n Mn- Note, from Lemma 2.9 have that f E M, MM (with high probability) and therefore the solution to Equation (6) gives an optimistic estimate for the average cost. We take the intersection of M,-1 with Mo ensure that maintain at least the same confidence about our model as at the beginning, i.e., n = 0, during learning.
NEORL proceeds in the following manner. Similar Jaksch et al. (2010), the agent spends interacting in the environment into N "artificial" episodes. At each episode, we pick policy according to Equation (6) and roll it out for Hn steps on the system. Next, the data collected during the rollout to update our statistical model. Finally, we double the horizon Hn+1 n.H,. akin Simchowitz & Foster (2020), and continue the next episode without resetting the system back to the initial state Ho. Intuitively, in the beginning, when our model estimate is not accurate, update our model more frequently, and with more episodes our model gets better reduce the frequency of updates. The algorithm is summarized in Algorithm 1.
bin the total time T
3.1 Theoretical Results
In the following, we study the theoretical properties for NEORL and provide a first-of-its-kind bound on the cumulative regret for the average cost criterion for general nonlinear dynamical systems. Our bound depends on the maximum information gain of kernel l (Srinivas et al., 2012), defined as
(k(k) =
max
2 log T
ACAXU:LA|ST A
TT represents the complexity of learning f from 7 data points and is sublinear for a very rich class of kernels (e.g., (1oga=+da++ (TT) for the exponential (RBF) kernel, O(dd + d.,) log(T)) for the linear kernel), In Appendix A, report the dependence of IT on T in Table 1.
Theorem 3.1 (Cumulative Regret of NEORL). Let Assumption 2. - 2,8 hold, and define Ho the smallest integer such that
log (Cu/c:)
Ho
log (1/7)
Then with probability at least
8, we have the following regret NEORL
Ho +1).
I
RT < D1(xo. K, 7) VTTT+ Dz(xo. K, log2
(7)
with Di(wo, K, 7). D5(xo, K,y) being bounded constants for bounded ||zo|], K, and 1.
5

---

From Lemma 2.9 we have that By x vTr and therefore Theorem 3.1 gives sublinear regret for rich class of RKHS functions. Moreover, it also gives minimal horizon Ho that we need to maintain before switching to the next policy. Even for the linear case, fast switching between stable controllers can destabilize the closed-loop system. We ensure this does not happen our case by having a minimal horizon of Ho. Theorem 3.1 can also be derived beyond the RKHS setting for more general class of well-calibrated models. In this case, the maximum information gain is replaced by the model complexity from Curi et al. (2020) (c.f., Curi et al. (2020); Sukhija et al. (2024) for further detail). In the following, we give an intuitive proof sketch for Theorem 3.1. The detailed proof is provided in Appendix A.
The proof can be split into three main steps. First, we show the ergodicity of the closed-loop system, a sufficient condition for showing the existence of the average cost and bias term, i.e., Theorem 2.6, for every policy π E IT under Assumption 2.1 - 2.4. For this, we use elementary results on Markov chains in measurable spaces from Meyn & Tweedie (2012); Hairer & Mattingly (2011), Second, we show that under Assumption 2.8, the optimistic system selected in Equation (6), re- tains the same properties as the true system f e.g., stability, and therefore also is ergodic. Crucial to show this is that the true system f and the optimistic system fn are at most 3,, o, apart. Finally, in the third step, show that as we update our model and policy every H,, steps, the doubling of the horizon retains the system properties from above, and our accumulated model uncertainties across T environ- ment steps grow with the rate Ty For the latter, episodic case, to bound the deviation between the optimistic average cost and the true average cost.
Proof sketch
the analysis from Kakade et al. (2020) for the
3.2 Practical Modifications
For testing NEORL, we make three modifications that simplify its deployment in practice in terms of implementation and computation time. First, instead of doubling the horizon Hn we pick fixed horizon H during the experiment. This makes the planning and training of the agent easier. Next, we use receding horizon controller, i.e., model predictive control (MPC) (García et al., 1989). instead of directly optimizing for the average cost in Equation (6). MPC is widely used to obtain a feedback controller for the infinite horizon setting. Moreover, while for linear systems, the Riccati equations (Anderson & Moore, 2007) provide an analytical solution to Equation (2), no such solution exists for the nonlinear case and MPC is commonly used as an approximation. Further, under additional assumptions on the cost and dynamics, MPC also obtains a policy with bounded average cost, which is crucial for the nonepisodic case (c.f., Assumption 2.4). We use the iCEM optimizer for planning (Pinneri et al., 2021). Finally, instead of optimizing over Mn n.Mo, we optimize directly over Mn. This allows to use the reparameterization trick from Curi et al. (2020) and obtain simple and tractable optimization problem. In summary, for each step in the environment, we solve the following optimization problem
Hure Σ h=
min
E
el c(it, up)
(8)
MAD: HyPe
HMPC
s.t. 01411 = 1n- (0h, un) + 3n- (0) ( uh M + Wh and à. xt--
Here HMPC is the MPC horizon. We take the first input from the solution of the problem above, i.e., uÿ. and execute this in the system. We then repeat this procedure for H steps and then update our statistical model Mn. The resulting optimization above considers larger action space as it includes the hallucinated controls 77 as additional input variables. The hallucinated controls are introduced through the reparameterizatioo trick from (Curi et al., 2020) and are used to directly optimize over models in f E Mn Moreover, the final algorithm can be seen as a natural extension to H- UCRL (Curi et al., 2020) for the nonepisodic setting. We summarize the algorithm in Appendix B Algorithm 2. Note while these modifications deviate from our theoretical analysis, empirically they work well for GP and BNN models, c.f., Section 4.
4 Experiments
We evaluate NEORL on the Pendulum-vl and MountainCar environment from the OpenAl gym benchmark suite (Brockman et al., 2016), Cartpole Reacher, and Swimmer from the DeepMind control suite (Tassa et al., 2018), the racecar simulator from Kabzan et al. (2020), and a soft robotic arm from Tekinalp et al. (2024). The swimmer and the soft robotic arm are fairly high-dimensional systems the swimmer has a 18-dimensional state and 5-dimensional action space, and the soft arm

---

Pendulum-GG
Pendulum
MountainCar Car
Reacher
10
101
A(
0..2
50-
0-
0-
0-
0.00
0
200
400
0
500
1000
0
500
1000
1000
2000
110
X
110"
x100
=10*
1.0
3-
0.5
2-
2
1-
0-
0-
0.0
0
.200
400
500 Eay Steps
1000
500 Dny Steps T
1000
1000 Eny Steps T
2000
Cnv Stops
Cart
Swimmer
Soft.Arm
RaceCar
40-
5.0
Airx
20-
0.5
0.5
2.5+
0-
0.0
0.0
0.0
1000
2000
10000
200000
1000
2000
1000
x10
x10
x10
=10*
1.0
1.0
15-
0.5
0.5
0.0
0.0
0
1000
2000
0
10000
20000
0
1000
2000
1000 Eny Steps T
Env Stops
Eny Steps
Eay Steps
NETS
NEMRAN
NoPETS
REO
Figure 1: Average reward A(T) and cumulative regret Rr over ten different seeds for all environ- ments. We report the mean performance with one standard error as shaded regions. During all experiments, the environment is never reset. For all baselines, we model the dynamics with proba- bilistic ensembles, except the Pendulum- significantly outperforms all baselines and converges to the optimal average reward, A(T*) = 0, showing sublinear cunulative regret Ry for all environments.
experiment, where GPs are used instead. NEORL
is represented by 58-dimensional state and has 12-dimensional action space. All environments are never reset during learning. Moreover, the Pendulum-vi MountainCar, CartPole, and Reacher environments operate within bounded domain and thus inherently satisfy Assumption 2.4. The swimmer, racecar, and soft arm can operate in an unbounded domain but have a cost function that penalizes the distance between the system's state æ; and target state x²" Therefore, the cost encourages the system to move towards the target and remain within a bounded domain.
Baselines In the episodic setting, resets can be used control the exploration space for the agent. However, in the absence of resets, the agent can explore arbitrarily and end up in states that are irrelevant the task at hand. Moreover, the agent has follow an uninterrupted chain of experience, which makes the nonepisodic setting the most challenging one in RI. (Kakade, 2003). Accordingly, there are only few algorithms that consider this setting (c.f., Section 5). In this work, we focus on model-based RL (MBRL) algorithms due to their sample efficiency. In particular, we adopt common MBRL methods for our setting. MBRL algorithms typically differentiate in three ways: (i) propagating dynamics for planning (Chua et al., 2018; Osband & Van Roy, 2017; Kakade et al., 2020; Curi et al., 2020), (ii) representation of the dynamics model (Ha & Schmidhuber, 2018; Hafner et al., 2019; Kipf et al., 2019), and (iil) types of planners (Williams et al., 2017; Hafner et al., 2020; Pinneri et al., 2021). NEORL is independent to the choice of representation or planners. Therefore, we focus on (i) and use probabilistic ensembles (Lakshminarayanan et al., 2017) and GPs for modeling our dynamics and MPC with iCEM (Pinneri et al., 2021) as the planner. Common techniques to propagate the dynamics for planning are using the mean, trajectory sampling (Chua et al., 2018), 8)), and Thompson
7

---

sampling (Osband & Van Roy, 2017). We adapt these three for our setting similar to as discussed in Section 3.2. For all experiments with probabilistic ensembles. we consider TSI from Chua et al. (2018) for trajectory sampling, and for the GP experiment, we use distribution sampling from Chua et al. (2018). We call the three baselines NEMEAN (nonepisodic mean), NEPETS (nonepisodic PETS), and NETS (nonepisodic Thompson sampling). NEMEAN and NEPETS are greedy w.r.t. the current estimate of the dynamics, i.c., do not explicitly encourage exploration. In our experiments, we show that being greedy does not suffice to converge to the optimal average cost, that is, obtain sublinear regret. The code for our experiments is available online.?
Convergence to the optimal average cost In Figure we report the normalized average cost and cumulative regret of NEORL, NEMEAN, NEPETS, and NETS. The normalized average cost is defined such that A(x*) 0 for all environments. We observe that NEMEAN fails to converge to the optimal average cost for the Pendulum-vl environment for both probabilistic ensembles and GP model. It also fails to solve the MountainCar environment and is unstable for the Reacher and CartPole. In general, NEMEAN performs the worst among all methods. This is similar to the episodic case, where using the mean model often leads to the policy "overfitting" to the model inaccuracies (Chua et al., 2018), 8). NEPETS performs better than the mean, however still significantly worse than NEORL. Even in the episodic setting, PETS tends underexplore (Curi al., 2020). We observe the same for the nonepisodic case, especially for the Mountain task, which is a challenging RL environment with a sparse cost. Here NEPETS is also not able to achieve the optimal average cost and thus does not have sublinear cumulative regret. NETS performs similarly to NEPETS and is also not able to solve the MountainCar task.
NEORL performs the best among the baselines for all experiments and converges to the optimal average cost achieving sublinear cumulative regret using only 10x environment interactions. Moreover, this observation is consistent between different dynamics models (GPs and probabilistic ensembles) and environments. Even in environments that are unbounded, i.e., Swimmer, SoftArm, and RaceCar, we observe that NEORL converges to the optimal average cost the fastest. We believe this is due to the feedback control from MPC, which has a stabilizing effect.
Calling reset when needed All the experiments in Figure I considered the nonepisodic setting where the system was never reset during learning. A special case of our theoretical analysis the class of policies II that may call for a reset/ / "ask for help" whenever they end up in an undesirable part of the state space. In this setting, the system is typically restricted a compact subset of the state space X, and the policy class satisfies Assumption 2.4. For many real-world applications, such a policy class can be derived. To simulate this experiment, we consider the CartPoleBalance task in Figure 2, where the goal is to balance the pole in the upright position. A reset is triggered whenever the pole drops. We again observe that NEORL achieves the best performance, i.e., lowest cumulative regret and thus learns to solve the task the fastest. Moreover, it also requires fewer resets than NEMEAN, NEPETS, and NETS.
5 Related Work
Average cost RL for finite state-action spaces A significant amount of work studies the average cost/reward RL setting for finite-state action spaces. Moreover, seminal algorithms such as E² (Kearns & Singh, 2002) and R- maxax (Brafman & Tennenholtz, 2002) have established PAC bounds for the nonepisodic setting. These bounds are further improved for communicating MDPs by the UCRL2 (Jaksch et al., 2010) algorithm, which, similar NEORL, is based on the optimism in the face of uncertainty paradigm and picks policies that are optimistic w.r.t. to the estimated dynamics. MDPs by REGAL (Bartlett & Tewari, 2012),
Their result is extended for similar results are derived for Thompson sampling based exploration (Ouyang et al., 2017), and for factored-MDI -DDP (Xu & Tewari, 2020). Albeit the significant amount of work for the finite case, progress for continuous state-action spaces has mostly been limited to linear dynamical systems.
Nonepisodic RL for linear systems There a large body of work for nonepisodic learning with linear systems (Abbasi- Yadkori-Yadkori & Szepesvári, 2011; Cohen et al., 2019; Simchowitz & Foster, 2020; Dean et al., 2020; Lale et al., 2020; Faradonbeh et al., 2020; Abeille & Lazaric 2020; Treven et al., 2021). For linear systems with quadratic costs, the average reward problem, also known as the linear Smadratie-Gaussian (LQG), has a closed-form solution which obtained via the Riccati equations (Anderson & Moore, 2007). Moreover, for LQG, stability and optimality are intertwined,
8

---

Cartlooe
x10
Total Rosets
1.0
Ry
2
0.5
0-
0.0
0
1000
2000
1000
2000
Env Steps T
Env Steps T
NETS
NEMEAN
NEPETS
NEORL
Figure 2: Total number of resets and cumulative regret Ry for the cart pole balancing task over ten different seeds. We report the mean performance with one standard errors as the shaded region. The environment is automatically reset whenever the agent drops the pole. All baselines solve the task, but NEORL converges the fastest requiring fewer resets and suffering smaller regret.
making studying linear systems much easier than their nonlinear counterpart. For studying nonlinear systems, additional assumptions on their stability are usually made.
Episodic RL for nonlinear systems In the case of nonlinear systems, guarantees have mostly been established for the episodic setting (Mania et al., 2020; Kakade et al., 2020; Curi al., 2020; Wagenmaker et al., 2023; Sukhija et al., 2024; Treven et al., 2024). In this setting, the agent begins each episode from an initial state 8n (or initial state distribution) and interacts with the environment for fixed horizon H. It uses the data collected from the interactions to update its model. After each episode, the agent is reset back to 8g- The works mentioned above theoretically study this setting for finite-horizon MDPs and establish regret bounds for general nonlinear systems. Particularly Kakade et al. (2020); Curi et al. (2020); Sukhija et al. (2024); Treven et al. (2024) also use an optimism- basee approach similar ours. Compared to the nonepisodic case, the analysis of episodic RL methods is simpler as resets restrict the agent's 's exploration around the initial state su and prevent the system from blowing up visiting states from which the agent cannot recover. However, discussed in Section 1, resets are often prohibitive and RL agents that learn non-episodically are preferred for many real-world applications.
Nonepisodic RL beyond linear systems Only a few works consider the nonepisodic/single- trajectory case. For instance, line of work studies data-driven MPC approaches focusing mostly on establishing system-theoretic guarantees such as closed-loop stability and robustness (Berberich & All- göwer, 2024). From the learning side, Foster et al. (2020); Sattar & Oymak (2022) study the problem of system identification of a closed-loop globally exponentially stable dynamical system from single trajectory. Lale al. (2021) study the nonepisodic setting for nonlinear systems with MPC. Moreover, they consider finite-order or exponentially fading NARX systems that lie in the RKHS of infinitely smooth functions, which they further approximate with random Fourier features (Rahimi & Recht, 2007) & with feature size D. Further, they assume access to bounded persistently exciting inputs w.r.t. the feature matrix $ Φ7. This assumption generally tough to verify and common excitation strategies such as random exploration often don't 't perform well for nonlinear systems (Sukhija et al., 2024). The algorithm also operates in two stages, where in the first stage it performs pure exploration for system identification and in the second stage exploitation, i.e., acting greedily w.r.t. the estimated dynamics, akin to NEMRAN. Additionally, the algorithm requires the feature size 1 increase with the horizon T. They give a regret bound of O (1r))) where the regret is measured w.r.t. to the oracle MPC with access to the true dynamics. Lale et al. (2021) also assume exponential input-to-outpen stability of the system to avoid blow-up during exploration. Our work considers more general RKHS, naturally trades-off off exploration and exploitation. does not require apriori knowledge of persistently exciting inputs and gives a regret bound of O (BTT)TT) w.r.t. the optimal average cost criterion. Moreover, our regret bound is similar to the ones obtained for nonlinear systems in the episodic case and Gaussian process bandits (Srinivas et al., 2012; Chowdhury & Gopalan, 2017; Scarlett et al., 2017). To the best of our knowledge, are the first to give such regret bound for nonlinear systems.
stabiilit

---

Nonepisodic Deep RL Standard deep RL approaches often fail in the nonepisodic setting (Sharma al., 2021b). To this end, deep RL algorithms have also been developed for the nonepisodic case. Mostly, these works focus on learning to reset and formulate it from the perspective of safety (Eysenbach et al., 2018) (avoiding undesirable states), chaining multiple controllers (Han et al., 2015), skill discovery/intrinsic exploration (Zhu et al., 2020; Xu et al., 2020), curriculum learning (Sharma et al., 2021a), and learning initial state distributions from demonstrations (Sharma et al., 2022). However, in contrast to us, none of the works above provide any theoretical guarantees.
There are several extensions of model-free deep RI. algorithms to the average reward setting (TRPO (Zhang & Ross, 2021), PPO (Ma et al., 2021), and DDPG (Saxena et al., 2023)). However, they mostly focus on maximizing the long-term behavior of the RL agent and allow for resets during learning. Overall, extending RL algorithms for the discounted case to the average one is still an open problem (Dewanto et al., 2020). However, future work in this direction will benefit NEORL. Since pverage-rewane optimizers can be used in combination with NEORL to directly minimize the average cost in a model- basee policy optimization (Janner et al., 2019) manner.
Conclusion
We propose, NEORL, a novel model-based RL algorithm for the nonepisodic setting with nonlinear dynamics and continuous state and action spaces. NEORL seeks for average-cost optimal policies and leverages the model's 's epistemic uncertainty to perform optimistic exploration. Similar to the episodic case (Kakade et al., 2020; Curi et al., 2020), we provide regret bound for NEoRL of (BTvTTT for Gaussian process dynamics. To our knowledge, we are the first to obtain this result in the nonepisodic setting. We compare NEORL to other model-based RL methods deep RL. benchmarks. Our experiments demonstrate that NEORL, converges to the optimal average cost of A(x*) = 0 across all environments, suffering sublinear regret even when Bayesian neural networks are used to model the dynamics. Moreover, NEORL outperforms all our baselines across all environments requiring only ~ 10x samples for learning.
standard
Future work may consider deriving lower bounds on the regret of NEORL, studying different assumptions f" and II, and investigating different notions of optimality such as bias optimality in the nonepisodic setting (Mahadevan, 1996).
Acknowledgments and Disclosure of Funding
We would like to thank Mohammad Reza Karimi, Scott Sussex, and Armin Lederer for the insightful discussions and feedback on this work. This project has received funding from the Swiss National Science Foundation under NCCR Automation, grant agreement S1NF40 180545, and the Microsoft Swiss Joint Research Center.
References
Abbasi- Abbasi-Yadkori, Y. and Szepesvári, C. Regret bounds for the adaptive control of linear quadratic systems. In Conference on Learning Theory, 2011.
Abeille, M. and Lazaric, A. Efficient optimistic exploration in linear-quadratic regulators via lagrangian relaxation, In International Conference on Machine Learning, 2020.
Anderson, B. D. and Moore, J. B. Optimal control: linear quadratic methods. Courier Corporation, 2007.
Annaswamy, A. M. Adaptive control and intersections with reinforeement lcarning. Annual Review of Control, Robotics, and Autonomous Systems, 2023.
Arapostathis, A., Borkar, V. S., Grmnändez-Gaucheraan F.., Ghosh, M. K., and Marcus, S. I. Discrete-time controlled markov processes with average cost criterion: A survey. SIAM Journal on Control and Optimization. 1993.
Åström, K. J. and Wittenmark, B. Adaptive Control. Courier Corporation, 2013.
Bartlett, P. L. and Tewari, A. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint / 2012.
Berberich, J. and Allgöwer, F. An overview of systems- theoretic guarantees in data-driver model predictive control, 2024. URL attps:///arxe org/abs /406 04130.
10

---

Brafman, R. I. and Tennenholtz, M. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 2002.
Brockman, G., Cheung, V., Pettersson, L.., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. Openai gym. arXiv preprint ar.iv:6606.01555.. 2016.
Chowdhury, S. R. and Gopalan, A. On kemelized multi-armed bandits. In ICML, 2017.
Chua, K., Calandra, R., McAllister, R., and Levine, S. Deep reinforcement learning in handful of trials using probabilistic dynamics models. In NeurlPS, 2018.
Cohen, A., Koren, T., and Mansour, Learming linear-quadratic regulators efficiently with only /T regret. In International Conference on Machine Learning, 2019.
Curi, S.. Berkenkamp, F., and Krause, A. Efficient model- based reinforcement learning through optimistic policy search and planning. NeurlPS, 33:14156-14170 2020.
Dean, S., Mania, H., Matni, N., Recht, B., and Tu, S. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-6) 679, 2020.
Dewanto, V., Dunn, G., Eshragh, A., Gallagher, M., and Roosta, F. Average-reward model-free reinforcement learning: systematic review and literature mapping. arXiv preprint arXiv:2010..89900, 2020.
Eysenbach, B., Gu, S., Ibarz, J., and Levine, S. Leave no trace: Learning to reset for safe and autonomous reinforcement learning. International Conference Learning Representations, 2018.
Faradonbeh, M. K. S.. Tewari, A., and Michailidis, G. Optimism- based adaptive regulation of finear-quadratic systems. IEEE Transactions Automatic Control, 2020.
Foster, D., Sarkar, T., and Rakhlin, A. Learning nonlinear dynamical systems from single trajectory. In Learning for Dynamics and Control, 2020.
Gareía, C. E., Prett, D. M., and Morari, M. Model predictive control: Theory and practice survey, Automatica, pp. 335-348, 1989.
Ha, D. and Schmidhuber, J. Recurrent world models facilitate policy evolution. Advances in neural information processing systems, 31, 2018.
Hafner, D., Lillicrap. T., Fischer, I., Villegas. R., Ha, D., Lee, H. and Davidson. J. Learning latent dynamics for planning from pixels. International conference on machine learning, 2019.
Hafner, Lillicrapp T., Ba, and Norouzi, M. Dream to control: Learning behaviors by latent imagination. ICLR, 2020.
Hairer, M. Mattingly, J. C. another look harris' ergodic theorem markov chains. In Seminur on Stochastic Analysis, Random Fields and Applications VI: Centro Stefano Franscini, Ascona, May 2008, pp- 109-117, Springer, 2011.
Han, W., Levine, S.. and Abbeel, P. Learning compound multi-step controllers under unknown dynamics. In Intelligent Robots and Systems (IROS), 2015.
Jakseh, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 2010.
Janner. M.. Fu, J.. Zhang. M.. and Levine, S.
When to trust your model: Model-based policy optimization. Advonces in neural information processing systems, 2019.
Kabzan, J., Valls, M. I., Reijgwart, V. J., Hendrikx, H. F., Ehmke, C., Prajapat, M., Bühler, A., Gosala, N., Gupta, M., Sivanesan, R., et al. Amz driverless: The full autonomous racing system. Journal of Field Robotics, 2020.
Kakade, S., Krishnamurthy, A., Lowrey, K., Ohnishi, M., and Sun, W. Information theoretic regret bounds for online nonlinear control. NeurIPS, 33:15312- 15325, 2020.
Kakade, S. M. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
Kearns, M. and Singh, S. Near-optimal reinforcement learning in polynomial time. Machine learning, 2002.
Khalil, H. K. Nonlinear control, volume 406. Pearson New York, 2015.

---

Kipf, T. Van der Pol, E., and Welling, M. Contrastive learning of structured world models. arXiv preprint arXiv:1911.1223 2019.
Krstić, M., Kanellakopoulos, I., and Kokotović, P. Adaptive nonlinear control without overparametrriattoon Systems Control Letters, 1992.
Krstić, M., Kokotovic, P. V., and Kanellakopoulos, I. Nonlinear and adaptive control design. John Wiley & Sons, Inc., 1995.
Kuleshov, V., Fenner, N., and Ermon, S. Accurate uncertainties for deep learning using calibrated regression. In ICML. pp. 2796-2804 PMLR, 2018.
Lai, L. and Wei, C. Least squares estimates in stochastic regression models with applications identification and control dynamic systems. The Annals of Statisticx, 1982.
Lai, T. L.. and Wei, C.-Z. Asymptotically efficient self-tuning regulators. SIAM Journal on Control and Optimization, 1987.
Lakshminarayanan, B., Pritzel, A., and Blundell, C. Simple and scalable predictive uncertainty estimation using deep ensembles, 2017.
Lale, S., Azizzadenesheli, K., Hassibi, B., and Anandkumar, A. Logarithmic regret bound in partially observable linear dynamical systems. Advances in Neural Information Processing Systems, 2020.
Lale, S., Azizzadenesheli, K., Hassibi, B., and Anandkumar, A. Model learning predictive control in nonlinear dynamical systems. In Conference on Decision and Control (CDC). IEEF, 2021.
Ma, X., Tang, X., Xia, L., Yang, J., and Zhao, Q. Average-reward reinforcement learning with trust region methods. International Joint Conference on Artificial Intelligence, 2021.
Mahadevan, S. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine learning, 1996.
Mania, H., Jordan, M. L., and Recht, B. Active learning for nonlincar system identification with guarantees. arXiv preprint arXiv:2006. 10277, 2020.
Meyn. S. P. and Tweedie, R. L. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
Oshand, I. and Van Roy, B. Why is posterior sampling better than optimism for reinforcement learning? In International conference machine learning. 2017.
Ouyang, Y., Gagrani, M., Nayyar, A., and Jain, R. Learning unknown markov decision processes: A thompson
sampling approach. Advances in neural information processing systems, 30, 2017.
Pinneri, C., Sawant, S., Blaes, S., Achterhold, J.. Stueckler, J.. Rolinek, M., and Martius, G. Sample-efficient cross-entropy method for real-time planning. In CORL, Proceedings of Machine Learning Research, pp. 1049-1065, 2021.
Puterman, M. Markoy decision processes: discrete stochastic dynamic programming. John Wiley Sons, 2014.
Rahimi, A. and Recht, B. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Rothfuss, J., Sukhija, B., Birchler, T., Kassraic, P., and Krause, A. Hallucinated adversarial control for conservative offline policy evaluation. UAI, 2023.
Sattar. Y. and Oymak. S. Non-asymptotic and accurate learning of nonlinear dynamical systems. Journal of Machine Learning Research, 2022.
Saxena, N., Khastagir, S., Kolathaya, S., and Bhatnagar, S. Off-policy average reward actor-critic with deterministic policy search. In International Conference on Machine Learning, 2023,
Scarlett, J., Bogumovic, I., and Cevher, V. Lower bounds on regret for noisy Gaussian process bandit optimization. In Conference on Leurning Theory, 2017.
Sharma, A., Gupta, A., Levine. S., Hausman, K. and Finn, C. Autonomous reinforcement learning via subgoal curricula. Advances in Neural Information Processing Systems, 2021a.
12

---

Sharma, A., Xu, K., Sardana, N., Gupla, A.. Hausman, K.. Levine, S., and Finn, C. Autonomous reinforvement learning: Formalism and benchmarking. arXiv preprint arXiv:2112.06005, 2021b.
Sharma, A., Ahmad, R., and Finn, C. A state-distribution matching approach to non-episodic reinforcement learning. International Conference Machine Learning, 2022.
Simchowitz, M. and Foster, D. Naive exploration is optimal for online lqr. In International Conference on Machine Learning. PMLR, 2020.
Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. W. Information-theoretie regret bounds for gaussian process optimization the bandit setting. IEEE Transactions Information Theory, 2012.
Sukhija, B., Treven, I.., Sancaktar, C., Blaes, S., Coros, S., and Krause, A. Optimistic active exploration of dynamical systems. NeurlPS, 2024.
Sussex, S., Makarova, A., and Krause, A. Model-based causal bayesian optimization. /CLR, May 2023.
Tassa, Y., Doron, Y., Muldal, A., Frez, T., Li, Y., Casas, D. d I.., Budden, D., Abdolmaleki, A., Merel, J., Lefraneq, A., et al. Deepmind control suite, arXiv preprint arXiv: /81.0000, 2018.
Tekinalp, A., Kim, S. H., Bhosale, Y., Parthasarathy, T., Naughton, N., Albazroun, A., Joon, R., Cui, S., Nasiriziba, I., Stölzle, M., Shih, C.H. C., and Gazzola, M. Gazzolllab/pyycaattia:: v0.3.2, 2024.
Treven, I.,, Curi, S., Mutný, M., and Krause, A. Learning stabilizing controllers for unstable linear quadratic regulators from a single trajectory. In Learning for Dynamics and Control, 2021.
Treven, L., Hübotter, J., Sukhija, B., Dörfler, F,, and Krause, A. Efficient exploration in continuous time model-based reinforcement learning. Neur/PS, 2024.
Vakili, S., Khezeli, K., and Picheny, V. On information gain and regret bounds in gaussian process bandits. In AISTATS, 2021.
Wagenmaker, A., Shi, G., and Jamieson, K. Optimal exploration for model-based rl in nonlinear systems. arXiv preprint arXiv:2306.092220 2023.
Williams, G., Wagener, N., Goldfain, B., Drews, P., Rehg. J. M., Boots, B., and Theodorou, E. A. Information theoretic mpe for model-based reinforcement Icarning. In ICRA, 2017.
Xu, K., Verma, S., Finn, C., and Levine, S. Continual learning of control primitives: Skill discovery via reset-games. Advances in Neural Information Processing Systems, 2020.
Xu, Z. and Tewari, A. Reinforcement learning in factored mdps: Oracle-efficient algorithms and tighter regret bounds for the non-episodic setting. Advances in Neural Information Processing Systems, 2020.
Zhang, Y. and Ross, K. W. On-policy deep reinforcement learning for the average-reward criterion. In International Conference on Machine Learning. 2021.
Zhao, F.. Dörfter, F., Chiuso, A., and You, K. Data-enabled policy optimization for direct adaptive learning of the lqr. arXiv preprint 2xXx:22401118771 2024.
Zhu, H., Yu, J.. Gupta, A., Shah, D.. Hartikainen, K., Singh, A., Kumar, V., and Levine, S. The ingredients of real- world robotic reinforcement leaming, arXiv preprint arXiv:2004.12571 2020.
13

---

Appendices
A Proofs
In this section, we prove Theorem 2.6 and Theorem 3.1. First, we start with the proof Lemma 2.5.
Proof of Lemma 2.5. We first analyze the following term Ev[V (2, (T))) Vff (ar, TT, + w)] for any π E II.
w)
Em [V( (ar, T (a)) + w) V(f (z, (x)) + ww] (2, + w)ll
s Eulk(l (())) ((()) w w-
(Uniform continuity of V)
*(llf* (2, (x)))
S n(Kig- (1 (|](())) - xx) (x)
(Uniform continuity of f*)
< ni(ig f- (2umaxx)
(Bounded inputs)
Therefore,
| [V(z')] = Ew (V T (x)) + w))
I (V (z, (x)) + w)] + K(Kgg- (2umax))
a a (V(x') )} k((5g- (21maxx)
I (x)()) + K + k( (24maxx)
-<(()) K
(K= (2umax))
Hence, V satisfies the drift condition for π. Furthermore, since V also satisfies positive definiteness by assumption, the bounded energy condition holds for all II.
A.1 Proof of Theorem 2.6
For proving Theorem 2.6, we invoke the results from (Hairer & Mattingly, 2011, Theorem 1.2 1.3). For this we require that the Markov chain induced by policy π satisfies the drift condition. In our setting, this corresponds to Assumption 2.4. Next, we show that the chain satisfies the following minorisation condition.
Lemma A.1 (Minorisation condition). Consider the system in Equation (1) and let Assump- tion 2.1 - 2.4 hold. Let p" denote the transition kernel for the policy π E 11, i.e. p (x, A) = P( E Alæ, ((x)). Then, for all π E 11, exists constant E (0, 1) and probability measure (())s... s.t.,
inf PT (x,)))
aEC
with C def E EX S R} for some 2K/1-7
Proof. We prove it in 3 steps. First, show that C is contained in compact domain. From the Assumption 2.4 we pick the function & Koo. Since Cε((0) = 0, lim E(s) = too and Ggg is continuous, there exists M such that CiE(M)= R. Then for ||0||| > M have:
(T(x)) 2 CrE([==]]) > {(M) = R.
Therefore have: C C B(O, M)
del {x: | Oll M). In the second step show that f(C, (C)) is bounded, in particular we show that there exists B > such that: f(C, x(C)) S B(0, B). This true since continuous image of compact set is compact and the observation:
C B(0, = (C)) C f(B(O, M), π (B(O0,)))
Since f(8(,, M), (B((, M))) is compact there exists B such that f(C, (C)) C ( B). In the last step we prove that 2-dae--d- -B² and Ç with law of N 0,
satisfy condition of o² 2
Lemma A.1. It is enough to show that Vu e B(0, B), Vx E Id we have:
1x1l
(2x) 4 (
(2T))
which can be proven with simple algebraic manipulations.
14

---

Through the minorisation condition and Assumption 2.4, we can prove the ergodicity of the closed- loop system for a given policy π II. Theorem A.2 (Ergodicity of closed-loop system). Lei Assumption 2.4, consider any probability measures Ç1, S2, and 0 > O, define P"s, || Pā
(P* (A) / pM A))((x))
x
[p(( 11ell sup #EX 1 AV (x)
((x) - (2)(dx)) = -1+ Ca (dxx)
Pō (21; = sup
9:llell+oov=
We have for all II, that p admits unique invariant measure Px Furthermore, there exist constants 0 0, > 0, X (0,1) such that
p (P" S1. PT (2) I A
(1)
[Pay [x(())] - Pa
1+V= S C22s 110 Ba-px [=(x+)]]]+++=
(2)
holds for every measurable function up X with || < co. Here (PTY denotes the t-step transition kernel under the policy π.
Moreover, 8 o0/ K, and
À = max { - (a - ao); 2 R/K00%
(10)
2 R/K00
for any oo E (0 and to E (7 + 2K/R,
Proof. From Assumption 2.4, we have value function for each policy that satisfies the drift condition.
Furthermore, in Lemma A.1 we show that our system also satisfies the minorisation condition for all policies. Under these conditions, we can use the results from Hairer & Mattingly (2011, Theorem 1.2. 1.3.).
Note that 11l1 represents a family of equivalent norms for any 0. Now we prove Theo- rem 2.6.
Proof of Theorem 2.6. From Theorem A.2, we have
p ((P")(+1 (PP"))+)(PP")) = p (PT (P*)', PM (P*)'-1) s (P 6wo)
where 6ag is the dirac measure. Therefore, (PT)' is a Cauchy sequence. Furthermore, P3 is complete for the set probability measures integrating V, thus p ((PT), (P)) + 0 30 (c.f., Hairer & Mattingly (2011) for more details). In particular, we have for to such that ||el| S
lim / ((x) t
[ (x(x)
Note that since all ||=V|++ov= norms are equivalent for 0 > 0. if [|cl S C (Assumption 2.4), then ||c|]+ov= S C' for some C' E (0, oo). Furthermore, note that c(.) 2 Therefore,
/ c(x) = lim /
(450 x
S C lim
(1 + V (z)
t-+00 X'
C + C lim Ea pmp V (x))
C C lim E Ep-(P prj [Br' V (x')|=]] (2))))]
< CC+ (iinn K)
(Assumption 2.4)
(1-400
15

---

K 1 1-7 yd
SC+ C lim (VV)(au))
100
1-7
=c 1 1-1
1
In summary, we have Bn- pa le(x:) S C (1 (1+
Consider any O, and note that from Theorem A.2 we have
E Ba [c(x)] Ban [c(x)]
(Pay [c(a:)] Be- lc(x))ll
= sup
1 (x0))
#xEX
- C1 ||e
Bx -
[c(x))]l (Theorem A.2)
- Ci [|ll2++ C Po [c(x)]
C2d',
where C2 - Ci + +L
Moreover, since the inequality holds for all Zu. have
(px [c(x)) Ban [c(2))]
S C222 1 1 VT (20p)
In summary,
I (Pary [c(=:] Pe [c(x)]] S C2(1 V (2o)) (2)))))
Consider any T 2 0, and define with Ex [c(x,TT())) (x))]-
T
T-1
E
c Us) - c
=
E(rry (c( - ē
T
Bpppy (c(2z), -
t=
< C2(1+ V (xx)) Σ X
X
V (2o))
Hence, we have
1
lim +-000
E
cl ux)
5 C2(( + V (20o))
1 1- X
and for any Be in compact subset of X
T
lim
E
Σ
c(a,, uz) - - =
700
T
Moreover,
B(T, S C2((1 (T((x))) 1-X
Another interesting, inequality that follows from the proof above is the difference in bias inequality.
EE [B(TT, xoo) - Eag [B(T,, æ0)1l S 1- x / (1 + V (x)) [4i C2l (dæ:
C3
16

---

for all probability measures (1. S2. To show this holds, define C' = max |c(,, T( Furthermore, note that C' < oc from Assumption 2.4 and | 1
1/x x c(z, m()) - (Pm) (2)
(pa B (T),,((())))))))) = -c (l) - (()
/ x
c² sup
((z)( (d=)) (1
s:: 01ll14oov
S CO ((P Si, (Pm))-
(Theorem A.2)
I C' (2).
Also, note that there exists Ca (0, 0o) such that Co l1 1| due to the equivalence of the two norms
/ ( (2)(
Pg (S1, (2)
sup
so: 1ove
sup
(0x)((1 - (dx)
rl11l vilvll SC x
= Co sup
((x)((1 (dx(
51
= CG,
Therefore, for the bias we have
Ex [B(T,
Exg [B(TT
T-1
lim
Epn c(z, (xx)) de
T 70000
T-1
C²
s C p0 (S1, (2) lim
Σ
X'
1- PE
T
1=0
C'Co (4, = 1-A
C.C,
(1 (=+ |4 C2 (dx)
Set C3 C' Co-
A.2 Proof of bounded average cost for the optimistic system
In this section, we show that the results from Theorem 2.6 also transfer over to the optimistic dynamics.
Theorem A.3 (Existence of Average Cost Solution for the Optimistic System). Let Assumption 2. 2.8 hold. Consider any n > 0 and let nas fn denote the solution to Equation (6), pa Sn its transition kernel. Then f admits a unique invariant measure projo and there exists Cz, Cs E (0)..).
E 1) such that Average Cost;
A(Trn fr)
lim T-000 T
E Er..
Σ 1=0
cl uz)
Prn. [c( n (x))
Bias Cost:
[B(Tn 2b)) =
lim Err T
Σ c(E, us) - A(TanIJ)
S + tTh v==())))
1 1-X
for all xo X.
17

---

Difference in Bias;
C3 1- / (1 V (a)) [ C2l (dar)
[e [B( fnz mn)] Ca [B(Tn, fnz m2))1 s
for all probability measures Ç1: S2.
Theorem A.3 shows that the optimistic dynamics fn retain the boundedness property from the true dynamics f and give well-defined solution w.r.t. average cost and the bias cost. To prove Theorem A.3 we show that the optimistic system also satisfies the drift and minorisation condition. Then we can invoke the result from Hairer & Mattingly (2011) similar to the proof of Theorem 2.6.
Lemma A.4 (Stability of optimistic system). Let Assumption 2./ 2.8 hold, then have with E
probability at least 8 for all π II. f M, Mo. that there exists a constant K such that
Es |e [ (x- S 7V (x)+
where x4 f(z π (x) + w.
Proof. Note, that v is uniformly continuous
[V'(x) - V (=')) S <(Iæ a'Il).
Furthermore, since f E Mn n Mo and therefore E Mo. we have that there exists some 77 E [-1, 1|dr such that
f(æ, (()) = (o(a.T(x))
E.
+ Sn [o) k (() + -
- -w]
(o). ff (x. (2)0(
(1 v ddz Bo / d=x
(Assumption 2.8)
Therefore,
En (x+)) S Em Im (VT + ((1+ dzz
Bo du d
)1 + (11+ vdz Buy dz dmx
= =E 1a.f
2/V~ + K k (1 v dx) Bo Vo d
(Assumption 2.4)
where we denoted 2 = (a, ा (a: w. Define R = K + ((1 vd,) Bo Bo
Lemma A.5 (Minorisation condition optimistic ystem). Consider the system
= f(xxT(()) + w0
for any 2 0, π E Il and f E Mn M Let Assumption 2.1 - 2.8 hold. Let px.f denote the transition kernel for the policy π E II ie.,, p A) P(x+ E AAax, (x), f).. Then, there exists a constant E (0, 1) and a probability measure Č(-) independent of S.I.,
inf pmd (x, 2 ac(-)
(1I)
with C del
X: VT < R. for some R 28/1-7
Proof. First, we show that C is contained in a compact domain. From the Assumption 2.4 we pick the function & E Kox. Since Cig(O) O, lim {(s) +oo and Ciê continuous, there exists
M such that C.(M)= = R. Then for ||>||| > M we have:
(x) 2 C](([==])) > {(M) R.
18

---

Therefore we have: C S B M) = f - 0 v M). Since for any a E C we have (lf (x))) (x, (x)) + max. Since f continuous, there exists a B such that (C, C (0 B). Therefore we have: f(C, (C)) C B(0, B1), where B1 = B + max- In the last step we prove that a def 2- Baile-BBloo Bi/0² and with law of N (o, 2 satisfy condition of
Lemma A.1. It is enough to show that vp E B(0, B1), Van E Rede we have:
(2xh (o
(2T))
which can be proven with simple algebraic manipulations.
Proof of Theorem A.3. As for the true system, the drift condition from Lemma A.4 and the mi- norisation condition from Lemma A.5 are sufficient to show ergodicity of the optimistic system (c.f., Theorem A.2 or Hairer & Mattingly (2011)). The rest of the proof is similar to Theorem 2.6.
A.3 Proof of Theorem 3.1
Since NEORL. works in artificial episodes E {0, N 1} of varying horizons Hn. We denote with o the state visited during episode n at time step h < Hn, Crucial, to our regret analysis bounding the first and second moment of V*= (x²) for all k. Given the nature of Assumption 2.4, this requires analyzing geometric series. Thus, we start with the following elementary result of geometric series.
Corollary A.6. Consider the sequence {Sn)n20 with Sn 2 0, for all n. Let the following hold
Sn S pSn- C
for p E 10,1) and C > 0. Then we have
Sn S p0 So + C
1-p
Proof.
Sn S pp p + C(1 + +1) S + S +
Σ
+C p' S +
1-
1=0
Lemma A.7. Let Assumption 2.1 2.8 hold and let Ho be the smallest integer such that
Ho log (Cw/ci)
log (1/²
Moreover, define v C. Ho. Note, by definition of Ho. < Then we have for all k e Ci
Hn} and n > 0
Bounded expectation over horizon
E Dag.....llaa V (xxii) < B.g....... TT [x=)))))) + K/(1 7)-
(12)
Bounded expectation over episodes
Cu K/(1 - -7) 1- 1
E Eag Bag.....
V ah
(x/i) S (
(13)
C
Moreover, we have
Bng y.. mo TT [x=x(())) < D( K,
(14)
with D(wo, K,7; v) VT (20) K/(1 77) 1- +
19

---

Proof. We start with proving the first claim
B un elo0 |V TH
(x+)]
= Buy mfl. [ leg_ 7m (xx )]
I B wf 120 [/V 7" (2 1) + K]
(Assumption 2.4)
y ef 2ff az [V (1 + K
We can apply Corollary A.6 to prove the claim. For the second claim, we note that for any 'T' and X' we have from Assumption 2.4
(=(()) S C,a(I1=1)) - Cu V (x)
C2
Therefore,
TT (2%)
2 ..... ley
C
E m0 .... 1mp
(van-l (x%))
C1
C
E
V (xx"HTm
(Since zi "HH
G
-...,
lan
Cu
C K/(1 - 7) C
E Beg--
V (2x []]
(Fquation (12))
For our choice of Ho, we have for n 2 0 that Gig Hn S CugHo Ho S v < From Corollary A.6, we get
C₁
Co Hn
C 1K(1-110) C
2g ...... 1o [V (x%))
B
I.... lan [ (xx (xx-1))
Ci
C K/(K 1-7) C
S 1/l0
....,09100 [Van (2)) (207-1)] +
vn (xn) + Cu
1
K/(1 -
(Corollary A.6)
Ci
1-v
E Rgg Tf. uff mo
TM (ar
< 7 Bagg m. |V (xx)) + K/(1 7)
(Fquation (12))
Fugg 1l10 TT (xx) )] K/(1 -7)
nア V to (20) + Kk/(1 <| -
C.
1
+ K/(11 7)
(Equation (13)
C
Cu
S (*o) +
K/(1 7) 1 - + KK/(1- (1
a.
Lemma A.8. Let Assumption 2.1 2.8 hold and let Hy be the smallest integer such that
log (Cw/ci)
Ho Moreover, define Co,HHo, Note, by definition of Ho. 1.
log (2/7)
Then we have for all (O....,HA3 H,} and n. > 0 Bounded second moment horizon
<> 2 Eag aef (( + D2 D2 K,y,v)
E Beg..... of æo (vTm
(15)
1- 1-72
with D2 K. k.y,)) 2K>D( K.7,v) + K² + Cu. and Cun 3(Ew [x]()
E. [x² [[[w]]]]
+
20

---

Bounded second moment over episodes
Egg ................................ 29100 (vT= S 22n (zo) +
Cu
2 D2(evo, k,7,v)
1
(16)
Ci
1 1-
1 12
Moreover, let Dz Kolao,,,,,, v) = (0 (xxo) + D2 K, K, ((#)
+ T
T-p T
Exg 2pl (z s D2(w0, K,7
Proof. Note that,
Baylar [- [(VT (xh))²
(Batlerr [V [x=m()))) 2
+ Bogllat 1 (V Bayler (1*(()))) 21
)
We first bound the second term. Let 2 (2x In (2( i.e., the next state in the absence of transition noise.
( (x²E)
(x+t - Bayler- [V=m(x)))) 27
= -eggla
(vTo Vmn (iffi + V (xx)
Eag le
[V (2:2(
= -Beglleg
(V (x+) - V (x + Beg leg
[V (i+)
V (2x
S Enw (M<(1 + EE [1 11))
(uniform continuity of lT*.)
Esw [[[e([]]))) + 3(w [^(1] w 1)))
Cw
(Assumption 2.4)
Therefore we have
Eugler 1ay
(VTT
2
+ Cw
S (~ (xx)) + K)² - Cr
= 2² (V (*% )))² 2KKKV= (x7 K2 + C..-
E Fe 20/200 (V (x))))
-Eay inmeefll
(V (2:2))
< 7 2 EEg But_.r..,e!le
(V (o% 1)
+ +2Ky ug_ p 29120 [vTH (x% 1)] K² +2+ CC
< 7 Bag u0 =........
(V (xx%_1)) ))²
21
+ +2K +2K>D(arg K, + K2 + Cun.
(Lemma A.7)
1mgg
Let D2(xo, K,7, K,7,D) = (K>D(an K, k, K2 + Cw. Applying Corollary A.6 we get
K2
[V S " #9.20 (zT)))
+ Dz(1u, K, 7,V.
E 2f.0
1-72
Similar to the first moment, we leverage that /TT (2x) < Cg (2) x E X, Gi Con S v, and get,
Ci
Eng Peloo
21

---

C
Bag.... 19/000000
Ca
2
[VVTn- (20))=1))
B m--
(Since tij = Hn
Mi
Cu
Ci ? Hi
E Bay-1 09/200
(V (x00 (20-11))
Cu
D2 D2(xv, k, 1-
(Equation (15))
C
I 2² Bag n-1
..... m2
(1 2
+
Ci
C
D2 k,
70
Cn
2
D2(10o K,Y, v)
I 2n (V (x=0)) +
(x00))²
(Corollary A.6)
Ci
1 7-
1 v2
Moreover,
F2 2f10a alpr (V=n((=)))*
EE
D2 K, 7,4,
< 7 2 Be 2P 2e (VTT
(Equation (15))
1 1-
+ D2 D2(x0, K,Y,V)
< E Exg 29/200
(V (x
1 --
S 2 (V To (200))
+
Cu
D2(wro K,
1
(2 K,,,y, v)
(Equation (16)
Ci
1-
1
u2
72
2
1
1
S (xo)))))) + D2 K, k,
C1
722
u2
72
L
Finally, we prove the regret bound of NEORL.
Proof of Theorem 3.1. the following, let 2b4 = fn (2f TI (xx)) + +w denote the state predicted under the optimistic dynamics and #b+1 = (a Th (xxt) + 206 the true state.
N-
Ha
E
cxa n.. (xx))) A(TT))
n=0
0=0
N
<
c( T (xx)) A A(TTn fn)
(Optimism)
R
B(mn, 2 B( B(Tn. fn, $2
(Bellman equation (Equation (4)))
E
B(T fn, x+) B(Tn. 2 + B(TT, fnr xb+1) B(TT, fn. 20 k++1
N H.
E B( Tay Jny 2x+1) B(T Sn, &b
(A)
H
E [ fn. xx)) B(TT. fr, xb+1)
(B)
First, we study the term (A).
Proof for (A): Note that because fa E Mn, there exists a 17 E ||1,1] such that क = un(a (xx)) + B,, (2ng nu (mz)))(())) + un. Furthermore, m f* + un and the transition noise is Gaussian. Let ( and ST denote the respective distributions of the
22

---

two random variables, i.e.. f7,x ~ ~ Tn( r²1) and 22 ~ ~f(n ( 021)) Next, define B B2 [B Sn; m)}, and consider the function h(x)) = B( Jn, x)) B. Then have
(TT, fnn 2 xb+11 B(TT Sns 0b++2)]
E [B( (T fn. x)] Ex-CEa [B(TT fn, x)]
nw, fn; x) - -B] - (T Snz x)) -B) Ea (T
E [1(z))] Em- [1(xz)]
Note that Exwey [1(x)] = 0 by the definition of and thus,
E E [1(2))] Eg [m(x))] Eg [h(x)] S Be (x)
(17)
In the following, we bound the term above w.r.t. the Chi- Chi-squared distance
Bug [T fn. xb+1) B(T fns (b++1)) BE [h(x)] - Ba [h(z)]
= =/ h(x))
2
[
Sr, (dx) S BBanct. [(2(z)] dx dx St,e)
((Kakade et al., 2020, Lemma C.2..)
With dy (C2,k: (P,x) being the Chi-squared distance.
(Six- - (2, )²
(5
(S ST,ce)
(dx:
Si,
Since both bounds from Equation (17) and bound we got by applying (Kakade et al., 2020, Lemma C.2..), we can apply minimum and have:
Eug [B(TT: xb+1) B(T,. fn. 24 +1] $ Beess, [1((z)] min { (dx(SE) (P.).
Therefore, following Kakade et al. (2020, Lemma C.2..) we get
Eug B(TT. fnr x) - B(T,, fn. +))
V EuasT, [12(x)) min min (4/ [ff (x)))) (2()))
E [13(z)] d.) ( n. (xx)))
((Sukhija et al., 2024, Cor. 3))
Therefore, have
E m 1l.0
[Luz
[B(Tns Sns 2h 1 (TT, fn. fn.4k41) +]]]]]]
0=0
k=0
N-1 H
[ [x]())]](1 Vdd) (n n. (a+)
E 1l.0
N-1 H.
(1+ v Vd
Ex ae.
Exncy [x2(2)]
|Io (x) T.. (xx)))))
R=0 k=
N-1 H
(1 VdL) 8T/0
Σ
Σ
E Egg ..... xo
E
Exe [x2(2)]]
N-1 H
Σ Σ
Pug_..
[I n (x
23

---

Here, for the second and third inequality, we use Cauchy- Sahhhy-Schhwrz... Now we bound the two terms above individually. First we bound ET [x))-
Ex-CT [>)()))] = Bu-
(1; [)]
Em-ef
(B(TT:: In. -Bn-cy, [B (Tn Jny In, x)))?
C2
2
(2+17m VTT Ex [V (ar)))
(Theorem A.3)
1 X
C2
E
(2 1T+V(=()) + ym (xx)) + k))a
(Lemma A.4)
1 1- -
2
V2C₂
(ITm + (2 R){]
1 1-
2
V2C₂
( (Eeggn [(*** (2 (x,))² + + +R)²)
1- X
Furthermore, we have from Lemma A.8.
Egg.....f Bar (1 log [(VTH(xX+++] (I + 27 2 (2x)))²
= Eag mf. lew [(V (xx- + + Beg..... low (x)))) s (1 (1+2))) K,y,v).
In the end, we get
N H Σ
Begg... x 29/00
Exwer, [x)(
A=
V2C₂
N-1 H.
(1+ (x),) + + + R)2
1-
R=U k=
V2C2
N-1
V(1+ +
R)²
Σ R=0
Hn
1 1-
V2C₂
(1 + 272) Do. 7, + 2(2 + R33VT.
1
Next, we use the bound from Curi et al. (2020, Lemma 17.) for the second term.
N H
E
[Ion(2]. [Ia.( (+[[))) s SC'
k=
Here PT is the maximum information gain. If we set D1 k, = c'(++v)))
V20 1-X
V(1 Ds K,,,v) + 2(2 + RT2, we have
N H 1
Σ
[Eng [B(Tn= fnr xx B B(T,, fn. 2b 1)]]
un ..... Ino
k=
N- Ho
< (1 Br/o
E B
20000
Ex-sr [x)(2]]]
m=0
k=
24

---

N Hu
Bay 10000 09l00
(2 T (2x))))
==0
k=0
V2C2
(1 Vdr/
VL+ (1+2,)))(((00,,,),)))))1
R)22+ VTr
1-
$ DDi K, 7/8TV/I
Proof for (B):
N-1 H 1
N-1
E B( xn.
B(T, Sn. 2b+1)
Σ
B B( B(T, Sn HHH))
1=0
k=0
C
N-1
Σ
(2+ E (x)) + (*
(Theorem A.3)
1 n=0
202
Σ
(1 D(vo: K,)))
(Lemma A.7)
1
2C2
(1 + D( K 7))
1-
= D5(a0o: K, N.
Here D5(mo, K,7)
202 1-X
+ D(vo, K,))). Finally, for choice, H₂ Ho2", we get
N-1
N-1
Σ
Hn Ho
Σ 2 Ho(2" - -1) =T.
Therefore, N = llog2
T + 1).
To this end, we get for our regret
Ho
N H
Rr
Σ
c(xy n (xx))) A(T*)
< Da(Zo. K, k,,)8r / TTr D5 K, 7)
T Ho +1)
Di(Zo. K, 7) / TTT Ds(0o K, log2
This regret is sublinear for very rich class of functions. We summarize bounds on Py from Vakili et al. (2021) in Table 1. Furthermore, note that (2 K, x) E (0) for all zu E X with ||xl|| < 0o, K < 00, 7 E (0, 1). The same holds for D K, Moreover, since v=(x) is (((()=)))) both D4 and D5 are @({([==))))
Table I: Maximum information gain bounds for common choice of kernels.
Kernel
k( x²)
lT
Linear
x' x
(d log(?))
2-=/||
log (TT)+((T))
RBF
Matèrn
V2u v2 x
By
22 x
Twaa log Ioln
25

---

Algorithm 2 Practical NEORL:
Init: Aleatoric uncertainty Probability 8, Statistical model (Mo. oo, Po())) for 1,..., N do for h = H do
Humc-1
min
c( un)
; 2%
Solve MPC problem
Mo 77000 H
(oe uis xx ROLLOUT(()))
Collect transition
end for Update (Kh, nn Br) Dn end for
Practical algorithm and Experimental Details
In this section, we provide the practical algorithm Algorithm 2, provide all hyperparameters used in our experiments in Table 2, and the cost function for the environments. All our experiments within 1-8 hours on a GPU (NVIDIA GeForee RTX 2080 Ti). For NEORL, we use 8n, for all the experiments, except for the Swimmer and the SoftArm environment where we use 3,, = 1.
Table 2: Hyperparameters for results in Section 4.
Environment
iCEM parameters
Model training purmetees
Number
Number
Optimizer
Hure
Partcless
Number of ensembles.
Network
Leaming
Hatch Namber speclss
samples
stops
Pordulum-CiP
Pendulum
MountainCarr
Reacher
1800
256
CarPPole
1000
10
30
10
256 2
0.001
10
Swimmer
500
10
30
10
256 x
DJ0000S
64
100
200
SoflArm
500
30
10
20
10
256 x
0,00005
64
50
20
RaceClar
1000
100
10
50
10
256 x
0,001
64
50
10
Table 3: Cost function for the environments presented in Section 4.
Environment
Cost c(z,, Up)
Pendulum
0 + 0.10, + 0.1
MountainCar
0.1uţ + 100 (1, & Fgoal })
Reacher
||=;
Fuaret
+ + l|u,
CartPole
pos
Farget
+ 10(cos(0)) (0.)
1)2 + 0.2 |
Swimmer
|x; Dtargel
SoftArm
xt Fiaggl
RaceCar
Ltarget
based the environment
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We highlight the problem setting, algorithm, and theoretical and empirical results the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section we highlight the assumptions of our work, which also correspond to the limitations of our theoretical analysis and also the setting for which our algorithm
yields theoretical guarantees. Further, ?? we discuss an alternative set of assumptions to the one made in the main paper. Limitations to the theoretical algorithm are discussed in Section 3.2, where also practical modifications are proposed. In our experiments (Section 4) we evaluate our algorithm on settings where the assumptions are not necessarily satisfied.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
27

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are accompanied by the relevant assumptions that are listed in Section 2 and we provide all proofs in Appendix A.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We use open-source benchmarks, disclose all hyperparameters in Appendix B, and the practical algorithm is explained in Section 3.2. Furthermore, we provide the code as supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
28

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the code supplementary material and the hyperparameters used in our experiments in Appendix B.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
public/gun public/guides/// Saaiiees/oodSSumiii wetammisssooooiiyoyo. for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
//ipp. wttpccccpppcccccctccc.cccc.cclct haaool/c/guddes/odeuuutiinn /wwo///ooossssiieeoeee ssionioiicy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experiment details are explained thoroughly in Section 3.2 and Section 4. Furthermore, all hyperparameters are listed in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All experiments are run with 10 seeds and mean performance with standard error is reported in all our plots.
Guidelines:
29

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We give details on computation time Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: bttts://neuurjee httpppppcccppppppppceeeeeeeeceee celuiiiieeese
Answer: [Yes]
Justification:
Our research conforms, in every respect, the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
30

---

Justification: This paper proposes method to improve exploration in reinforcement learning in the nonepisodic setting, and not tied to specific applications. As such, shares the many potential societal consequences that are associated with reinforcement learning and automation as whole, spanning from environmental impact concerns on ethics and alignment.
Guidelines:
The answer NA means that there is no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release high-risk data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We cite all creators whose code we used in our experiments in Section 4.
Guidelines:
The answer NA means that the paper does not existing assets.
31

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide the code as supplementary material including readme that explains how to install and run the code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
32

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
33


Reviews:
[{"review_id": "OsFtiA7q04", "reviewer": "Reviewer_zoj1", "summary": "The paper proposes NeoRL for non-episodic RL with nonlinear dynamical systems. NeoRL has a first-of-its-kind regret bound for general nonlinear systems with Gaussian process dynamics. The paper also proposes a practical implementation of NeoRL with MPC, which significantly outperforms baseline algorithms.", "questions": "- Is there any comment on the tightness of the regret?\n- How well does NeoRL scale to high-dimensional environments such as Humanoid?", "limitations": "The paper discuss the limitation of the theoretical results. I do not see any potential negative societal impact.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper paper proposes NeoRL, which has a first-of-its-kind regret bound for general nonlinear systems with Gaussian process dynamics.\n\nThe paper also proposes a practical implementation of NeoRL with MPC, which significantly outperforms baseline algorithms.\n\nThe paper is very well-written and easy to follow.\n\nWhile the basic idea of the algorithm is not novel, the paper considers a very important topic of average RL and has a large impact on the theory of average RL, I think.", "weaknesses": "I do not see any particular weakness in this paper. Maybe one weakness is that the tightness of the derived bound is unclear because there is no lower bound for the considered setting, as the authors also mentioned in Conclusion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their invaluable feedback. We are happy to hear that they also appreciate the significance of our work. Below, we have our responses to the questions. \n\n**Q1**: Is there any comment on the tightness of the regret?\n\n**A1**: We would have loved to give a lower bound, but as acknowledged by the reviewer, lower bounds do not exist for this and in fact even for the simpler episodic setting (c.f, [1, 2] for example). However, we are actively working towards bridging this gap. Particularly, there is some hope that the upper bound is tight. This is motivated from results on Gaussian process bandit optimization [3], where the tightness of the regret is shown by providing similar order lower bounds. Since our upper bounds are of similar order, and motivated through a similar analysis, as the ones derived in GP bandits, we have some hope that they are also tight (with respect to T). However, overall, this is still an open problem. \n\n**Q2**: How well does NeoRL scale to high-dimensional environments such as Humanoid?\n\n**A2**: NeoRL has the same limitations as any model-based RL algorithm such as planning in high-dimensional input spaces. Particularly, NeoRL has to, in addition to the control inputs, optimize over the hallucinated controls $\\eta$. There are heuristics to replace a direct optimization over $\\eta$ with a sampling-based approach (c.f., [1, 4]), which scales much better (e.g., [4] evaluate it on a 58D system). Lastly, we use the iCEM [5] optimizer for planning, which has demonstrated scalability on the humanoid task.\n\n\n**References**\n1. Kakade, Sham, et al. \"Information theoretic regret bounds for online nonlinear control.\" Advances in Neural Information Processing Systems 33 (2020)\n\n2. Curi, Sebastian, Felix Berkenkamp, and Andreas Krause. \"Efficient model-based reinforcement learning through optimistic policy search and planning.\" Advances in Neural Information Processing Systems 33 (2020)\n\n3. Scarlett, Jonathan, Ilija Bogunovic, and Volkan Cevher. \"Lower bounds on regret for noisy gaussian process bandit optimization.\" Conference on Learning Theory. PMLR, 2017.\n\n4. Sukhija, Bhavya, et al. \"Optimistic active exploration of dynamical systems.\" Advances in Neural Information Processing Systems 36 (2023)\n\n5. Pinneri, Cristina, et al. \"Sample-efficient cross-entropy method for real-time planning.\" Conference on Robot Learning. PMLR, 2021.", "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": "", "extra_scores": {}}, {"review_id": "ovxgs4u324", "reviewer": "Reviewer_17bq", "summary": "This work introduces a novel model-based RL algorithm, named NeoRL, for nonepisodic RL problems with unknown system dynamics and known costs. A cumulative regret bound is provided for NeoRL with well-calibrated dynamic models. The proposed method achieved lower accumulative regret and average cost compared with baselines in several continuous control tasks. In the end, NeoRL shows it needs less reset before convergence in a reverted pendulum task with automatic reset.", "questions": "1. Could the author provide a more intuitive explanation about which part of the algorithm improves performance in non-episodic settings?\n\n2. Could the author explain why the planning horizon needs to be doubled after each “artificial episode”?\n\n3. Is NeoRL extendable to problems with unknown rewards (cost functions)?", "limitations": "The limitations and assumptions for the theory results are discussed in section 2", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. the research question this paper tries to address is important and interesting, as the difficulty of resetting the environment is a notorious blocker for deploying RL agents in the real world.\n\n2. A bound for cumulative regret is provided for the proposed algorithm when certain conditions are satisfied.\n\n3. The proposed algorithms show lower average cost and cumulative regret than baselines in the empirical evaluation.", "weaknesses": "1. The paper is difficult to follow for readers without much control theory background (such as me), and it is difficult to distinguish the algorithmic contributions of this work. Could the author provide a more intuitive explanation about how NeoRL is connected and different from [1,2] and which part of the algorithm actually improves performance in a non-episodic setting?\n\n2. Another major concern of mine is the selection of baseline algorithms, which are not compared to other recent model-based RL algorithms, such as [3-5] and RL algorithms designed to deal with non-episodic problems [6, 7].\n\n3. No analyses were presented to understand how critical design choices influence the proposed methods' performance, such as the choice of planning horizon H_0 and whether to double the planning horizon.\n\n[1] Treven, L., Hübotter, J., Dorfler, F. and Krause, A., 2024. Efficient \nexploration in continuous-time model-based reinforcement learning. *Advances in Neural Information Processing Systems*, *36*.\n\n[2]Curi S, Berkenkamp F, Krause A. Efficient model-based reinforcement learning through optimistic policy search and planning. Advances in Neural Information Processing Systems. 2020;33:14156-70.\n\n[3]Hafner D, Pasukonis J, Ba J, Lillicrap T. Mastering diverse domains through world models. arXiv preprint arXiv:2301.04104. 2023 Jan 10.\n\n[4] Hansen N, Wang X, Su H. Temporal difference learning for model predictive control. arXiv preprint arXiv:2203.04955. 2022 Mar 9.\n\n[5] Hansen N, Su H, Wang X. Td-mpc2: Scalable, robust world models for continuous control. arXiv preprint arXiv:2310.16828. 2023 Oct 25.\n\n[6] Sharma A, Ahmad R, Finn C. A state-distribution matching approach to non-episodic reinforcement learning. arXiv preprint arXiv:2205.05212. 2022 May 11.\n\n[7] Chen A, Sharma A, Levine S, Finn C. You only live once: Single-life reinforcement learning. Advances in Neural Information Processing Systems. 2022 Dec 6;35:14784-97.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. In the following, we respond to the weaknesses and questions raised by the reviewer.\n\n**W1**: Difficult to follow for people with limited knowledge of control theory and connection to other prior work on optimistic exploration.\n\n**A1**: While control theory plays a crucial role in our analysis, we understand that it can be tough to follow with limited prior knowledge. We’d be happy to address any specific questions on the manuscript regarding this or provide additional explanations in the parts of the papers if the reviewer believes they might help the reader. On the comparison to [1, 2], both algorithms leverage the concept of optimism but consider very different settings. [1] studies the episodic setting in discrete time, whereas [2] for continuous time. As the reviewer zoj1 also highlights, we are not the first to propose optimistic exploration for model-based RL, but, to the best of our knowledge, we are the first to study it in the context of nonlinear systems and nonepisodic RL/average cost criterion. Algorithmically, a key difference is that [1] optimizes the policy for a finite horizon, [2] for continuous-time and finite horizon, and both reset the environment after every episode. In both cases, the horizon $H$ is fixed. We optimize for the average cost criterion, where there is no notion of a horizon. Since the settings/problems are very different, we cannot quantify the difference in performance among the different methods. NeoRL in essence leverages the same idea of optimism as [1,2] but studies the much more challenging non-episodic setting.\n\n**W2**: Baselines\n\n**A2**: In our experimental evaluation, we focus only on model-based methods due to their sample efficiency. As we highlight in section 4, MBRL methods vary mostly in how the model is represented (GPs, BNNs, world models etc), the choice of policy optimizer, and how the dynamics are propagated to facilitate exploration. Methods [3-5] study the first two axes (representation, e.g., RSSMs or policy optimization TDMPC). Furthermore, they are developed for the episodic/discounted reward setting with POMDPs, we study (theoretically and practically) the average cost criterion with MDPs, therefore these methods significantly diverge from our setting.  Crucially, our contribution is for the third axis of differentiation, i.e., we show that the celebrated principle of optimism works for many cases in the nonepisodic setting. To this end, we study different dynamics propagation approaches such as mean sampling (this is also used in [3-5] where no epistemic uncertainty is considered), trajectory sampling (PETS), and Thompson sampling. To the best of our knowledge, these are the only approaches (along the third axis) typically considered in MBRL. \nLastly, note that [6, 7] both assume access to prior data, which we do not. Furthermore, they are model-free methods whereas we focus on model-based approaches.\n\n**Q1**: Intuitive explanation about which part of the algorithm improves performance in non-episodic settings\n\n**A1**: We are unsure about what the reviewer means by “which part of the algorithm improves performance in non-episodic settings”. We would appreciate it if the reviewer could elaborate on the question further. However, we also provide a tentative response;\nThe key contribution of our work is to show that optimism, which is often used in bandit optimization and episodic RL, also yields theoretical guarantees and good empirical performance for the non-episodic case. Hence, akin to the episodic setting [1, 2, 8] optimism is crucial for NeoRL's theoretical guarantees. We also refer the reviewer to our response to W1. \n\n**W3/Q2**: Doubling of the planning horizon.\n\n**A2**: Note that it is not the planning horizon, but the model update horizon that is doubled, i.e., the frequency of our model update is reduced as we run the algorithm for longer. The intuitive explanation for this is that the longer we run the algorithm, the more data we collect and our model gets more accurate. Thus it requires less regular updates. Also, by doubling the horizon, we also improve the quality of the data by reducing transient effects in the collected trajectories. In practice, we observe that having a fixed horizon also works very well. In this case, the choice of the horizon depends on the available compute, the shorter the horizon, the more often you update your model. Furthermore, note that also other algorithms for the non-episodic setting increase the “artificial horizon/episode length” [9, 10]. This is also common for bandit optimization (see [11]).\n\n**Q3**: Extension to unknown rewards (costs).\n\n**A3**: Yes, NeoRL can in principle be extended to this setting. This can be simply done by including the cost “as part of your dynamics”. Moreover, given $x_t, a_t$ our model predicts the augmented $x_{t+1}, c_{t}$ and the last elemented of the augmented is used in our cost function. Under similar continuity assumptions on the cost as for the dynamics, we can extend our analysis to this setting. \n\nHaving addressed the reviewer’s questions, we would appreciate it if the reviewer would increase their score for our paper. For any remaining questions, we are happy to provide further clarification. \n\n**References**\n\n[1] -- [7] as listed by the reviewer.\n\n[8] Kakade, Sham, et al. \"Information theoretic regret bounds for online nonlinear control.\" Advances in Neural Information Processing Systems 33 (2020)\n\n[9] Simchowitz, Max, and Dylan Foster. \"Naive exploration is optimal for online lqr.\" International Conference on Machine Learning. PMLR, 2020.\n\n[10]  Auer, Peter, Thomas Jaksch, and Ronald Ortner. \"Near-optimal regret bounds for reinforcement learning.\" Advances in neural information processing systems 21 (2008).\n\n[11] Besson, Lilian, and Emilie Kaufmann. \"What doubling tricks can and can't do for multi-armed bandits.\" arXiv preprint arXiv:1803.06971 (2018).", "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": "", "extra_scores": {}}, {"review_id": "IoG6tPD3BD", "reviewer": "Reviewer_WMig", "summary": "This paper proposes a model-based RL algorithm NeoRL  for continuous state-action spaces in the nonepisodic setting, where the agent learns from a single trajectory without resets.", "questions": "1. How sensitive is the performance of NeoRL to the choice of kernel and the maximum information gain? What guidance can be provided for selecting appropriate kernels in practice?\n2. Can the bounded energy assumption be relaxed or replaced with alternative assumptions to broaden the applicability of NEORL?", "limitations": "The authors have discussed the limitations.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides the first regret bound for nonepisodic RL in general nonlinear systems, addressing a gap in the literature.\n2. NeoRL is grounded in the optimism principle and leverages well-calibrated probabilistic models, providing a theoretically justified exploration strategy.\n3. The experiments demonstrate the practical effectiveness of NEORL, achieving sublinear regret and converging to the optimal average cost in various environments.", "weaknesses": "1. The optimization problem in Equation (6) for policy selection may be computationally expensive, especially for high-dimensional systems. \n2. While the experiments demonstrate the efficacy of NEORL, a more comprehensive evaluation across a diverse set of environments and comparisons with state-of-the-art methods would strengthen the empirical results.\n3. The authors can discuss some data-driven MPC framework, like [1,2].\n\n[1] Berberich J, Köhler J, Müller M A, et al. Data-driven model predictive control with stability and robustness guarantees[J]. IEEE Transactions on Automatic Control, 2020, 66(4): 1702-1717.\n\n[2] Berberich J, Allgöwer F. An overview of systems-theoretic guarantees in data-driven model predictive control[J]. arXiv preprint arXiv:2406.04130, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and are happy to see the reviewer acknowledge how our work bridges a significant gap in RL theory. In the following, we respond to the weaknesses and questions raised by the reviewer.\n\n**W1**: Expensive computation.\n\n**A1**: Thanks for raising this concern. Indeed the optimization problem in (6) may fair infavourably for high-dimensional systems. However, there are heuristic approximations that can be made that favor much better for the high dimensional case (c.f., [1, 2] or our response to reviewer zoj1’s second question).\n\n**W2**: Comparisons with state-of-the-art methods.\n\n**A2**:  In our experimental evaluation, we focus only on model-based methods due to their sample efficiency. As we highlight in section 4, MBRL methods vary mostly in how the model is represented (GPs, BNNs, world models, etc), the choice of policy optimizer, and how the dynamics are propagated to facilitate exploration. Our contribution is for the third axis of differentiation, i.e., we show that the celebrated principle of optimism works for many cases in the nonepisodic setting. Thereby we compare our method to other approaches of dynamics propagation such as mean (which is most widely used), trajectory sampling (PETS [3]), and Thompson sampling. To the best of our knowledge, these are the only approaches (along the third axis) typically considered in MBRL. \n\n**W3**: Discuss some data-driven MPC framework.\n\n**A3**: Thanks for pointing us to these references, we have added them to our related work.\n\n\n**Q1**: Sensitivity to the choice of kernel.\n\n**A1**: In theory, the choice of the kernel has an effect on the convergence guarantees/max info gain (c.f., Table 1 in Appendix A). Practically, we used the most common kernel, the Gaussian kernel, in our experiments which worked completely fine. However, according to the theory, choosing the right kernel can affect the performance/convergence of the underlying algorithm. One way to make this choice is to use some offline/pre-recorded data on the system for kernel selection or meta-learn the kernel parameters from other data sources (c.f., Rothfuss, Jonas, et al. \"Meta-learning priors for safe Bayesian optimization.\" Conference on Robot Learning. PMLR, 2023)\n\n**Q2**:  Bounded energy assumption.\n\n**A2**: Thanks for this very interesting question. The bounded energy assumption stems from the classical results on Markov chains (Meyn, Sean P., and Richard L. Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.), therefore we are unsure if this can be further relaxed. Nonetheless, we are currently looking into possible ways to relax this assumption. However, as highlighted in Corollary 2.5., for many practical problems, where the control input is bounded and we have at least 1 policy with bounded energy, this assumption is satisfied. If the system is linear, having a stabilizing controller is enough [4], so perhaps something like this could be enough also for our case.\n\n\n\n\n\n**References**\n1. Kakade, Sham, et al. \"Information theoretic regret bounds for online nonlinear control.\" Advances in Neural Information Processing Systems 33 (2020)\n\n2. Sukhija, Bhavya, et al. \"Optimistic active exploration of dynamical systems.\" Advances in Neural Information Processing Systems 36 (2023)\n\n3. Chua, K., et al. (2018) Deep reinforcement learning in a handful of trials using probabilistic dynamics models. Advances in neural information processing systems.\n\n4. Simchowitz, Max, and Dylan Foster. \"Naive exploration is optimal for online lqr.\" International Conference on Machine Learning. PMLR, 2020.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Solid result on non-episodic learning in the control setting with Gaussian dynamics. Reviewers like it, and I would mainly suggest that the authors try and improve the presentation for the broader RL (or at least RL theory) audience, given that they position it as an RL result. Also, while I appreciate the authors describing the differences in setting in great detail to position their contributions, a similar overview of the new technical aspects would be very useful, since optimisitic planning, truncation to an effective horizon for stable systems etc are relatively standard techniques, and it would be useful for a reader to get a proof overview with the main novel components.
Decision: Accept (spotlight)