NeoRL: Efficient Exploration for Nonepisodic RL

Authors: bhavya  sukhija
lenart  treven
florian  dörfler
stelian  coros
andreas  krause
eth  zurich
  switzerland
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 09:52:42

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.

Main paper: 
 introduction: 
 In recent years, data-driven control approaches, such as reinforcement learning (RL), have demonstrated remarkable achievements. However, most RL algorithms are devised for an episodic setting, where during each episode, the agent interacts in the environment for a predetermined episode length or until a 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 (Åström & Wittenmark, 2013) , where classical works focus on controller design (Lai & Wei, 1982 , 1987; Krstić et al., 1992 Krstić et al., , 1995;; Annaswamy, 2023) and not on the exploration/learning aspect of the problem. Only a few works consider these two aspects jointly (Abbasi-Yadkori & Szepesvári, 2011; Cohen et al., 2019; Dean et al., 2020; Simchowitz & Foster, 2020; Zhao et al., 2024) . However, these works study linear systems with quadratic costs, i.e., 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 & Tennenholtz, 2002; Jaksch et al., 2010) and the extension to nonlinear systems with continuous spaces is much less understood. In our work, we address this gap and propose a practical RL 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.2. We show that when the dynamics lies in a reproducing kernel Hilbert space (RKHS) of kernel k, NEORL exhibits a regret of O(β T √ T Γ T ), where the regret, akin to prior work, is measured w.r.t to the optimal average cost under known dynamics, T is the number of environment steps, β T the calibration coefficient (Chowdhury & Gopalan, 2017; Srinivas et al., 2012) and Γ T 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 et 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 to 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.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 in the abstract and introduction. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in 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. fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
problem setting: 
 We consider a discrete-time dynamical system with running costs c.x t+1 = f * (x t , u t ) + w t , (x t , u t ) ∈ X × U, x(0) = x 0 (1) c(x, u) ∈ R ≥0 (Running cost)Here x t ∈ X ⊆ R dx is the state, u t ∈ U ⊆ R du the control input, and w t ∈ W ⊆ R w the process noise. The dynamics f * are unknown and the cost c is assumed to 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 problemEQUATIONMoreover, we consider the nonepisodic RL setting where the system starts at an initial state x 0 ∈ X but never resets back during learning, that is, we seek to learn online from a single trajectory. After each step t in the environment, the RL system receives a transition tuple (x t , u t , x t+1 ) and updates its policy based on the data D t collected thus far during learning. The average cost formulation is common for the nonepisodic setting (Jaksch et al., 2010; Abbasi-Yadkori & Szepesvári, 2011; Cohen et al., 2019; Dean et al., 2020; Simchowitz & Foster, 2020) , and the cumulative regret for the learning algorithm in this case is defined asEQUATIONStudying 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.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, we make the following assumption. Assumption 2.1 (Continuity of f * and π). The dynamics model f * and all π ∈ Π are continuous.Next, we make an assumption on the system's stochastic disturbances. Assumption 2.2 (Process noise distribution). The process noise is i.i.d. Gaussian with variance σ 2 , i.e., w t i.i.d∼ N (0, σ 2 I).Our analysis can be extended for the more general heteroscedastic case, where σ depends on x. However, for simplicity, we focus on the homoscedastic setting. In the following, we make assumptions on our policy class. To this end, we first introduce the class of K ∞ functions.Definition 2.3 (K ∞ -functions). The function ξ : R ≥0 → R ≥0 is of class K ∞ , if it is continuous, strictly increasing, ξ(0) = 0 and ξ(s) → ∞ for s → ∞. Assumption 2.4 (Policies with bounded energy). We assume there exists κ, ξ ∈ K ∞ , positive constants K, C u , C l with C u > C l , and γ ∈ (0, 1) such that for each π ∈ Π we have, Bounded energy: There exists a Lyapunov functionV π : X → [0, ∞) for which ∀x, x ′ ∈ X , |V π (x) -V π (x ′ )| ≤ κ(∥x -x ′ ∥) (uniform continuity) C l ξ(∥x∥) ≤ V π (x) ≤ C u ξ(∥x∥) (positive definiteness) E x+|x,π [V π (x + )] ≤ γV π (x) + K (drift condition)wherex + = f * (x, π(x)) + w.Bounded norm of cost:sup x∈X c(x, π(x)) 1 + V π (x) < ∞Boundedness of the noise with respect to κ:E w [κ(∥w∥)] < ∞, E w κ 2 (∥w∥) < ∞The drift condition states that the energy between two timesteps can increase at most by K. In particular, the Lyapunov function V π 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 et 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, 2011) , which is crucial for our analysis of the infinite horizon behavior of the system. Moreover, for a very rich class of problems, the drift condition is satisfied. We highlight this in the corollary below. Lemma 2.5. Assume f * is uniformly continuous and for all π ∈ Π, x ∈ X , ∥π(x)∥ ≤ u max . Further assume, there exists π s ∈ Π such that we have constantsK, C u , C l with C u > C l , γ ∈ (0, 1), κ, α ∈ K ∞ and a Lyapunov function V : X → [0, ∞) for which ∀x, x ′ ∈ X , |V (x) -V (x ′ )| ≤ κ(∥x -x ′ ∥) C l ξ(∥x∥) ≤ V (x) ≤ C u ξ(∥x∥) E x+|x,πs [V (x + )] ≤ γV (x) + K,where x + = f * (x, π(x)) + w. Then, V also satisfies the drift condition for all π ∈ Π, i.e., is a 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 is 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 Π satisfies the drift condition.The boundedness assumptions for the cost and the noise in Assumption 2.4 are satisfied for a rich class of cost and K ∞ 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 -2.4 hold. Consider any π ∈ Π and let P π denote its transition kernel, i.e., P π (x, A) = P(x + ∈ A|x, π(x)) for A ⊆ X . Then P π admits a unique invariant measure P π , and there exists C 2 , C 3 ∈ (0, ∞), λ ∈ (0, 1) such that Average Cost;A(π) = lim T →∞ 1 T E π T -1 t=0 c(x t , u t ) = E x∼ P π [c(x, π(x))] Bias Cost; Letting B(π, x 0 ) = lim T →∞ E π T -1 t=0 c(x t , u t ) -A(π) denote the bias, we have |B(π, x 0 )| ≤ C 2 (1 + V π (x 0 )) 1 1 -λ for all x 0 ∈ 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 x 0 . Furthermore, it also shows that the bias is bounded. The average cost criterion satisfies the following Bellman equation (Puterman, 2014) belowEQUATIONAccordingly, the bias term plays an important role in the regret analysis (also notice its similarity to our regret term in Equation ( 3)).Thus far, we 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 n we learn a mean estimate µ n of f * and can quantify our uncertainty σ n over the estimate. More formally, we learn a well-calibrated statistical model of f * as defined below. Definition 2.7 (Well-calibrated statistical model of f * , Rothfuss et al. ( 2023)). Let Z def = X × U. An all-time well-calibrated statistical model of the function f * is a sequence {M n (δ)} n≥0 , whereM n (δ) def = f : Z → R dx | ∀z ∈ Z, ∀j ∈ 1, . . . , d x : |µ n,j (z) -f j (z)| ≤ β n (δ)σ n,j (z) , if, with probability at least 1 -δ, we have f * ∈ n≥0 M n (δ).Here, f j , µ n,j and σ n,j denote the j-th element in the vector-valued functions f , µ n and σ n respectively, and β n (δ) ∈ R ≥0 is a scalar function that depends on the confidence level δ ∈ (0, 1] and which is monotonically increasing in n.Next, we assume that f * resides in a Reproducing Kernel Hilbert Space (RKHS) of vector-valued functions and show that this is sufficient for us to obtain a well-calibrated model. Assumption 2.8. We assume that the functions f * j , j ∈ 1, . . . , d x lie in a RKHS with kernel k and have a bounded norm B, that is f * ∈ H dx k,B , with H dx k,B = {f | ∥f j ∥ k ≤ B, j = 1, . . . , d x }. Moreover, we assume that k(x, x) ≤ σ max for all x ∈ X . Assumption 2.8 allows us to model f * with GPs for which the mean and epistemic uncertainty (µ n (z) = [µ n,j (z)] j≤dx , and σ n (z) = [σ n,j (z)] j≤dx ) have an analytical formulaEQUATIONHere, y j 1:n corresponds to the noisy measurements of f * j , i.e., the observed next state from the transitions datasetD 1:n , k n = [k(z, z i )] i≤nT , z i ∈ D 1:n , and K n = [k(z i , z l )] i,l≤nT , z i , z l ∈ D 1:nis the data kernel matrix. The restriction on the kernel k(x, x) ≤ σ max implies boundedness of f * and has also appeared in works studying the episodic setting for nonlinear systems (Mania et al., 2020; Kakade et al., 2020; Curi et al., 2020; Sukhija et al., 2024; Wagenmaker et al., 2023) . We can also define f * such thatx k = x k-1 + f * (x k-1 , u k-1 ) + w k-1 inwhich 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 * ∈ H dx k,B . Suppose µ n and σ n are the posterior mean and variance of a GP with kernel k, c.f., Equation (5). There exists β n (δ) ∝ √ Γ n , for which the tuple (µ n , σ n , β n (δ)) is a well-calibrated statistical model of f * .In summary, in the RKHS setting, a GP is 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 well-calibrated models similar to Curi et al. (2020) . A(π, f ) ➤ Prepare policyH n = 2H n-1 ➤ Set horizon D n ← ROLLOUT(π n ) ➤ Collect measurements for horizon H n Update (µ n , σ n , β n ) ← D n ➤ Update statistical model M n end forQuestion: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: In Section 2 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, in ?? 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 a 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 well-specification, 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 on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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, or 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 or the standard error of the mean. 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
neorl: 
 In the following, we present our algorithm: Nonepisodic Optimistic RL (NEORL) for efficient nonepisodic exploration in 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.t. the dynamics within our calibrated statistical model as followsEQUATIONHere, f n is a dynamical system such that the cost by controlling f n with its optimal policy π n is the lowest among all the plausible systems from M n-1 ∩ M 0 . Note, from Lemma 2.9 we have that f * ∈ M n-1 ∩ M 0 (with high probability) and therefore the solution to Equation ( 6) gives an optimistic estimate for the average cost. We take the intersection of M n-1 with M 0 to ensure that we 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 to Jaksch et al. (2010) , we bin the total time T the agent spends interacting in the environment into N "artificial" episodes. At each episode, we pick a policy according to Equation ( 6) and roll it out for H n steps on the system. Next, we use the data collected during the rollout to update our statistical model. Finally, we double the horizon H n+1 = 2H n , akin to Simchowitz & Foster (2020) , and continue to the next episode without resetting the system back to the initial state x 0 . Intuitively, in the beginning, when our model estimate is not accurate, we update our model more frequently, and with more episodes as our model gets better we reduce the frequency of updates. The algorithm is summarized in Algorithm 1.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 k (Srinivas et al., 2012) , defined asΓ T (k) = max A⊂X ×U ;|A|≤T 1 2 log I + σ -2 K T .Γ T represents the complexity of learning f * from T data points and is sublinear for a very rich class of kernels (e.g., O(log dx+du+1 (T )) for the exponential (RBF) kernel, O((d x + d u ) log(T )) for the linear kernel). In Appendix A, we report the dependence of Γ T on T in Table 1 . Theorem 3.1 (Cumulative Regret of NEORL). Let Assumption 2.1 -2.8 hold, and define H 0 as the smallest integer such thatH 0 > log ( Cu /C l ) log ( 1 /γ) .Then with probability at least 1δ, we have the following regret for NEORLEQUATION)with D 4 (x 0 , K, γ), D 5 (x 0 , K, γ) being bounded constants for bounded ∥x 0 ∥, K, and γ < 1.From Lemma 2.9 we have that β T ∝ √ Γ T and therefore Theorem 3.1 gives sublinear regret for a rich class of RKHS functions. Moreover, it also gives a minimal horizon H 0 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 in our case by having a minimal horizon of H 0 . Theorem 3.1 can also be derived beyond the RKHS setting for a 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. Proof sketch 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 π ∈ Π 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), retains 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 f n are at most β n σ n apart. Finally, in the third step, we show that as we update our model and policy every H n steps, the doubling of the horizon retains the system properties from above, and our accumulated model uncertainties across T environment steps grow with the rate Γ T . For the latter, we use the analysis from Kakade et al. (2020) for the episodic case, to bound the deviation between the optimistic average cost and the true average cost.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 H n we pick a fixed horizon H during the experiment. This makes the planning and training of the agent easier. Next, we use a 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 M n ∩ M 0 , we optimize directly over M n . This allows us to use the reparameterization trick from Curi et al. (2020) and obtain a simple and tractable optimization problem. In summary, for each step t in the environment, we solve the following optimization problemEQUATION.t. xh+1 = µ n-1 ( xh , u h ) + β n-1 (δ)σ n-1 ( xh , u h )η h + w h and x0 = x t .Here H MPC is the MPC horizon. We take the first input from the solution of the problem above, i.e., u * 0 , and execute this in the system. We then repeat this procedure for H steps and then update our statistical model M n . The resulting optimization above considers a larger action space as it includes the hallucinated controls η as additional input variables. The hallucinated controls are introduced through the reparameterization trick from (Curi et al., 2020) and are used to directly optimize over models in f ∈ M n-1 . 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. 
experiments: 
 We evaluate NEORL on the Pendulum-v1 and MountainCar environment from the OpenAI 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 28-dimensional state and 5-dimensional action space, and the soft arm Figure 1: Average reward A(π) and cumulative regret R T over ten different seeds for all environments. 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 probabilistic ensembles, except in the Pendulum-GP experiment, where GPs are used instead. NEORL significantly outperforms all baselines and converges to the optimal average reward, A(π * ) = 0, showing sublinear cumulative regret R T for all environments.is represented by a 58-dimensional state and has a 12-dimensional action space. All environments are never reset during learning. Moreover, the Pendulum-v1, MountainCar, CartPole, and Reacher environments operate within a 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 x t and a 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 to 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 to the task at hand. Moreover, the agent has to follow an uninterrupted chain of experience, which makes the nonepisodic setting the most challenging one in RL (Kakade, 2003) . Accordingly, there are only a 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 (iii) 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) , and Thompson 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 TS1 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.e., 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.2 Convergence to the optimal average cost In Figure 1 we report the normalized average cost and cumulative regret of NEORL, NEMEAN, NEPETS, and NETS. The normalized average cost is defined such that A(π * ) = 0 for all environments. We observe that NEMEAN fails to converge to the optimal average cost for the Pendulum-v1 environment for both probabilistic ensembles and a 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) . NEPETS performs better than the mean, however still significantly worse than NEORL. Even in the episodic setting, PETS tends to underexplore (Curi et al., 2020) . We observe the same for the nonepisodic case, especially for the MountainCar 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 ∼ 10 3 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 1 considered the nonepisodic setting where the system was never reset during learning. A special case of our theoretical analysis is the class of policies Π 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 to 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. 
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 3 (Kearns & Singh, 2002) and R-max (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 to 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. Their result is extended for weakly-communicating MDPs by REGAL (Bartlett & Tewari, 2012) , similar results are derived for Thompson sampling based exploration (Ouyang et al., 2017) , and for factored-MDP (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 is a large body of work for nonepisodic learning with linear systems (Abbasi-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 quadratic-Gaussian (LQG), has a closed-form solution which is obtained via the Riccati equations (Anderson & Moore, 2007) . Moreover, for LQG, stability and optimality are intertwined, 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 et 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 s 0 (or initial state distribution) and interacts with the environment for a fixed horizon H. It uses the data collected from the interactions to update its model. After each episode, the agent is reset back to s 0 . The works mentioned above theoretically study this setting for finite-horizon MDPs and establish regret bounds for general nonlinear systems. 2024) also use an optimism-based approach similar to ours. Compared to the nonepisodic case, the analysis of episodic RL methods is simpler as resets restrict the agent's exploration around the initial state s 0 and prevent the system from blowing up or visiting states from which the agent cannot recover. However, as 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/singletrajectory case. For instance, a line of work studies data-driven MPC approaches focusing mostly on establishing system-theoretic guarantees such as closed-loop stability and robustness (Berberich & Allgö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 a single trajectory. Lale et 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 Φ t Φ ⊺ t . This assumption is generally tough to verify and common excitation strategies such as random exploration often don'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 NEMEAN. Additionally, the algorithm requires the feature size D to increase with the horizon T . They give a regret bound of O T 2 /3 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-output stability of the system to avoid blow-up during exploration. Our work considers more general RKHS, naturally trades-off exploration and exploitation, does not require apriori knowledge of persistently exciting inputs and gives a regret bound of O(β T √ T Γ T ) 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, we are the first to give such a regret bound for nonlinear systems.Nonepisodic Deep RL Standard deep RL approaches often fail in the nonepisodic setting (Sharma et 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 RL 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 average-reward optimizers can be used in combination with NEORL to directly minimize the average cost in a model-based 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 epistemic uncertainty to perform optimistic exploration. Similar to the episodic case (Kakade et al., 2020; Curi et al., 2020) , we provide a regret bound for NEORL of O(β T √ T Γ T ) 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 on standard deep RL benchmarks. Our experiments demonstrate that NEORL, converges to the optimal average cost of A(π * ) = 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 ∼ 10 3 samples for learning. Future work may consider deriving lower bounds on the regret of NEORL, studying different assumptions on f * and Π, and investigating different notions of optimality such as bias optimality in the nonepisodic setting (Mahadevan, 1996) . 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This paper proposes a method to improve exploration in reinforcement learning in the nonepisodic setting, and is not tied to specific applications. As such, it shares the many potential societal consequences that are associated with reinforcement learning and automation as a whole, spanning from environmental impact to concerns on ethics and alignment.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or 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 out 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 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 by 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 a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? 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 use existing assets.• 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 a 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 (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be 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 a 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 was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 as the institution conducting the review. 
 
 Appendix: In this section, we prove Theorem 2.6 and Theorem 3.1. First, we start with the proof of Lemma 2.5.Proof of Lemma 2.5. We first analyze the following termE w [V (f * (x, π(x)) + w) - V (f * (x, π s (x)) + w)] for any π ∈ Π. E w [V (f * (x, π(x)) + w) -V (f * (x, π s (x)) + w)] ≤ E w [κ(∥f * (x, π(x)) + w -(f * (x, π s (x)) + w)∥)] (Uniform continuity of V ) = κ(∥f * (x, π(x)) -f * (x, π s (x))∥) ≤ κ(κ f * (∥π(x) -π s (x)∥)) (Uniform continuity of f * ) ≤ κ(κ f * (2u max )).(Bounded inputs)Therefore,E x ′ |π,x [V (x ′ )] = E w [V (f * (x, π(x)) + w)] ≤ E w [V (f * (x, π s (x)) + w)] + κ(κ f * (2u max )) = E x ′ |πs,x [V (x ′ )] + κ(κ f * (2u max )) ≤ γV (x) + K + κ(κ f * (2u max )) = γV (x) + K ( K = K + κ(κ f * (2u max )))Hence, V satisfies the drift condition for π. Furthermore, since V also satisfies positive definiteness by assumption, the bounded energy condition holds for all π ∈ Π.A.1 Proof of Theorem 2.6For 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 a 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 Assumption 2.1 -2.4 hold. Let P π denote the transition kernel for the policy π ∈ Π, i.e., P π (x, A) = P(x + ∈ A|x, π(x)) . Then, for all π ∈ Π, exists a constant α ∈ (0, 1) and a probability measureζ(•) s.t., inf x∈C P π (x, •) ≥ αζ(•) (9) with C def = {x ∈ X ; V π (x) ≤ R} for some R > 2K /1-γProof. We prove it in 3 steps. First, we show that C is contained in a compact domain. From the Assumption 2.4 we pick the function ξ ∈ K ∞ . Since C l ξ(0) = 0, lim s→∞ ξ(s) = +∞ and C l ξ is continuous, there exists M such that C l ξ(M ) = R. Then for ∥x∥ > M we have:V π (x) ≥ C l ξ(∥x∥) > ξ(M ) = R.Therefore we have:C ⊆ B(0, M ) def = {x | ∥x -0∥ ≤ M }.In the second step we show that f (C, π(C)) is bounded, in particular we show that there exists B > 0 such that: f (C, π(C)) ⊆ B(0, B). This is true since continuous image of compact set is compact and the observation:C ⊆ B(0, M ) =⇒ f (C, π(C)) ⊆ f (B(0, M ), π(B(0, M ))).Since f (B(0, M ), π(B(0, M ))) is compact there exists B such that f (C, π(C)) ⊆ B(0, B). In the last step we prove that α def = 2 -dx e -B 2 /σ 2 and ζ with law of N 0, σ 2 2 satisfy condition of Lemma A.1. It is enough to show that ∀µ ∈ B(0, B), ∀x ∈ R dx we have:α 1 (2π) dx 2 σ 2 2 dx 2 e -∥x∥ 2 σ 2 ≤ 1 (2π) dx 2 (σ 2 ) dx 2 e -∥x-µ∥ 2 2σ 2which can be proven with simple algebraic manipulations.Through the minorisation condition and Assumption 2.4, we can prove the ergodicity of the closedloop system for a given policy π ∈ Π. Theorem A.2 (Ergodicity of closed-loop system). Let Assumption 2.1 -2.4, consider any probability measures ζ 1 , ζ 2 , and θ > 0, define P π ζ, ∥φ∥ 1+θV π , ρ π θ as(P π ζ) (A) = X P π (x, A)ζ(dx) ∥φ∥ 1+θV π = sup x∈X |φ(x)| 1 + θV π (x) ρ π θ (ζ 1 , ζ 2 ) = sup φ:∥φ∥ 1+θV π ≤1 X φ(x)(ζ 1 -ζ 2 )(dx) = X (1 + θV π (x))|ζ 1 -ζ 2 |(dx).We have for all π ∈ Π, that P π admits a unique invariant measure P π . Furthermore, there exist constants C 1 > 0, θ > 0, λ ∈ (0, 1) such thatEQUATION)holds for every measurable function φ : X → R with ∥φ∥ 1+V π < ∞. Here (P π ) t denotes the t-step transition kernel under the policy π.Moreover, θ = α0 /K, andEQUATIONfor any α 0 ∈ (0, α) and γ 0 ∈ (γ + 2 K /R, 1).Proof. From Assumption 2.4, we have a 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 ∥•∥ 1+θV π represents a family of equivalent norms for any θ > 0. Now we prove Theorem 2.6.Proof of Theorem 2.6. From Theorem A.2, we have ρ π θ ((P π ) t+1 , (P π ) t ) = ρ π θ (P π (P π ) t , P π (P π ) t-1 ) ≤ λ t ρ π θ (P π δ x0 , δ x0 ), where δ x0 is the dirac measure. Therefore, (P π ) t is a Cauchy sequence. Furthermore, ρ π θ is complete for the set of probability measures integrating V , thus ρ π θ ((P π ) t , P π ) → 0 for t → ∞ (c.f., Hairer & Mattingly (2011) for more details). In particular, we have for φ such that ∥φ∥1+θV π ≤ 1, lim t→∞ X φ(x)(P π ) t (dx) = X φ(x) P π (dx). Note that since all ∥•∥ 1+θV π norms are equivalent for θ > 0, if ∥c∥ 1+V π ≤ C (Assumption 2.4), then ∥c∥ 1+θV π ≤ C ′ for some C ′ ∈ (0, ∞). Furthermore, note that c(•) ≥ 0. Therefore, X c(x) P π (dx) = lim t→∞ X c(x)(P π ) t (dx) ≤ C lim t→∞ X (1 + V π (x))(P π ) t (dx) = C + C lim t→∞ E x∼(P π ) t [V π (x)] = C + C lim t→∞ E x∼(P π ) t-1 [E x ′ ∼(P π ) [V π (x ′ )|x]] ≤ C + C lim t→∞ γE x∼(P π ) t-1 [V π (x)] + K (Assumption 2.4) ≤ C + C lim t→∞ γ t V π (x 0 ) + K 1 -γ t 1 -γ = C 1 + K 1 1 -γIn summary, we haveE x∼ P π [c(x)] ≤ C 1 + K 1 1-γConsider any t > 0, and note that from Theorem A.2 we haveE x∼(P π ) t [c(x)] -E x∼ P π [c(x)] 1+V π = sup x0∈X |E x∼(P π ) t [c(x)] -E x∼ P π [c(x)] | 1 + V π (x 0 ) ≤ C 1 λ t ∥c -E x∼ P π [c(x)]∥ 1+V π (Theorem A.2) ≤ C 1 λ t ∥c∥ 1+V π + C 1 λ t E x∼ P π [c(x)] = C 2 λ t ,whereC 2 = C 1 (∥c∥ 1+V π + CK 1 1-γ ).Moreover, since the inequality holds for all x 0 , we have|E x∼(P π ) t [c(x)] -E x∼ P π [c(x)] | 1 + V π (x 0 ) ≤ C 2 λ t .In summary,|E x∼(P π ) t [c(x)] -E x∼ P π [c(x)] | ≤ C 2 (1 + V π (x 0 ))λ t .Consider any T ≥ 0, and define with c =E x∼ P π [c(x, π(x))]. E π T -1 t=0 c(x t , u t ) -c = T -1 t=0 E (P π ) t [c(x t , u t )] - c ≤ T -1 t=0 E (P π ) t [c(x t , u t )] -c ≤ C 2 (1 + V π (x 0 )) T -1 t=0 λ t = C 2 (1 + V π (x 0 )) 1 -λ T 1 -λ Hence, we have lim T →∞ E π T -1 t=0 c(x t , u t ) -c ≤ C 2 (1 + V π (x 0 )) 1 1 -λ ,and for any x 0 in a compact subset of X limT →∞ 1 T E π T -1 t=0 c(x t , u t ) -c = 0. Moreover, |B(π, x 0 )| ≤ C 2 (1 + V π (x 0 )) 1 1 -λ .Another interesting, inequality that follows from the proof above is the difference in bias inequality.|E x0∼ζ1 [B(π, x 0 )] -E x0∼ζ2 [B(π, x 0 )]| ≤ C 3 1 -λ X (1 + V π (x)) |ζ 1 -ζ 2 | (dx)for all probability measures ζ 1 , ζ 2 . To show this holds, define C ′ = max π∈Π ∥c(x, π(x))∥ 1+θV π . Furthermore, note that C ′ < ∞ from Assumption 2.4 and ∥ c(x,π(x)) /C ′ ∥ 1+θV π ≤ 1.E x∼(P π ) t ζ1 c(x, π(x)) -E x∼(P π ) t ζ2 c(x, π(x)) = X c(x, π(x))((P π ) t ζ 1 -(P π ) t ζ 2 )(dx) = C ′ X 1 C ′ c(x, π(x))((P π ) t ζ 1 -(P π ) t ζ 2 )(dx) ≤ C ′ sup φ:∥φ∥ 1+θV π ≤1 X φ(x)((P π ) t ζ 1 -(P π ) t ζ 2 )(dx) = C ′ ρ π θ ((P π ) t ζ 1 , (P π ) t ζ 2 ) ≤ C ′ λρ π θ ((P π ) t-1 ζ 1 , (P π ) t-1 ζ 2 ) (Theorem A.2) ≤ C ′ λ t ρ π θ (ζ 1 , ζ 2 ). Also, note that there exists C θ ∈ (0, ∞) such that C θ ∥φ∥ 1+θV π ≥ ∥φ∥ 1+V π due to the equivalence of the two norms.ρ π θ (ζ 1 , ζ 2 ) = sup φ:∥φ∥ 1+θV π ≤1 X φ(x)(ζ 1 -ζ 2 )(dx) ≤ sup φ:∥φ∥ 1+V π ≤C θ X φ(x)(ζ 1 -ζ 2 )(dx) = C θ sup φ:∥φ∥ 1+V π ≤1 X φ(x)(ζ 1 -ζ 2 )(dx) = C θ ρ π 1 (ζ 1 , ζ 2 ) Therefore, for the bias we have |E x0∼ζ1 [B(π, x 0 )] -E x0∼ζ2 [B(π, x 0 )]| ≤ lim T →∞ T -1 t=0 E x∼(P π ) t ζ1 c(x, π(x)) -E x∼(P π ) t ζ2 c(x, π(x)) ≤ C ′ ρ π θ (ζ 1 , ζ 2 ) lim T →∞ T -1 t=0 λ t = C ′ 1 -λ ρ π θ (ζ 1 , ζ 2 ) ≤ C ′ C θ 1 -λ ρ π 1 (ζ 1 , ζ 2 ) = C ′ C θ 1 -λ X (1 + V π (x)) |ζ 1 -ζ 2 | (dx) Set C 3 = C ′ C θ .A.2 Proof of bounded average cost for the optimistic systemIn 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.1 -2.8 hold. Consider any n > 0 and let π n , f n denote the solution to Equation (6), P π,fn its transition kernel. Then P π,fn admits a unique invariant measure P πn,fn and there exists C 2 , C 3 ∈ (0, ∞), λ ∈ (0, 1) such that Average Cost;A(π n , f n ) = lim T →∞ 1 T E πn,fn T -1 t=0 c(x t , u t ) = E x∼ P πn ,fn [c(x, π n (x))]Bias Cost;|B(π n , f n , x 0 )| = lim T →∞ E πn,fn T -1 t=0 c(x t , u t ) -A(π n , f n ) ≤ C 2 (1 + V πn (x 0 )) 1 1 - λ for all x 0 ∈ X .Difference in Bias;|E x0∼ζ1 [B(π n , f n , x 0 )] -E x0∼ζ2 [B(π n , f n , x 0 )]| ≤ C 3 1 -λ X (1 + V π (x)) |ζ 1 -ζ 2 | (dx)for all probability measures ζ 1 , ζ 2 .Theorem A.3 shows that the optimistic dynamics f n retain the boundedness property from the true dynamics f * and give a 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.1 -2.8 hold, then we have with probability at least1 -δ for all n ≥ 0, π ∈ Π, f ∈ M n ∩ M 0 , that there exists a constant K > 0 such that E x+|x,f ,π [V π (x + )] ≤ γV π (x) + K, where x + = f (x, π(x) + w. Proof. Note, that V π is uniformly continuous w.r.t. κ |V π (x) -V π (x ′ )| ≤ κ(∥x -x ′ ∥).Furthermore, since f ∈ M n ∩ M 0 and therefore f ∈ M 0 , we have that there exists some η ∈[-1, 1] dx such that f (x, π(x)) = µ 0 (x.π(x)) + β 0 σ 0 (x, π(x))η(x). E w [V π (µ 0 (x.π(x)) + β 0 σ 0 (x, π(x))η(x) + w)] -E w [V π (f * (x.π(x)) + w)] ≤ κ (∥µ 0 (x.π(x)) + β 0 σ 0 (x, π(x))η(x) -f * (x.π(x))∥) ≤ κ (∥µ 0 (x.π(x)) -f * (x.π(x))∥ + ∥β 0 σ 0 (x, π(x))η(x)∥) ≤ κ 1 + d x β 0 d x σ max . (Assumption 2.8)Therefore,E x+|x,f ,π [V π (x + )] ≤ E x+|x,f * ,π [V π (x * + )] + κ 1 + d x β 0 d x σ max = E x+|x,f * ,π [V π (x * + )] + κ 1 + d x β 0 d x σ max ≤ γV π (x) + K + κ 1 + d x β 0 d x σ max , (Assumption 2.4)where we denotedx * + = f * (x, π(x) + w. Define K = K + κ 1 + √ d x β 0 √ d x σ max .Lemma A.5 (Minorisation condition optimistic ystem). Consider the systemx + = f (x.π(x)) + wfor any n ≥ 0, π ∈ Π and f ∈ M n ∩ M 0 . Let Assumption 2.1 -2.8 hold. Let P π,f denote the transition kernel for the policy π ∈ Π i.e., P π,f (x, A) = P(x + ∈ A|x, π(x), f ). Then, there exists a constant α ∈ (0, 1) and a probability measure ζ(•) independent of n s.t.,inf x∈C P π,f (x, •) ≥ αζ (•) (11) with C def = {x ∈ X ; V π (x) < R} for some R > 2 K /1-γProof. First, we show that C is contained in a compact domain. From the Assumption 2.4 we pick the function ξ ∈ K ∞ . Since C l ξ(0) = 0, lim s→∞ ξ(s) = +∞ and C l ξ is continuous, there exists M such that C l ξ(M ) = R. Then for ∥x∥ > M we have:V π (x) ≥ C l ξ(∥x∥) > ξ(M ) = R.Therefore we have:C ⊆ B(0, M ) def = {x | ∥x -0∥ ≤ M }. Since for any x ∈ C we have ∥f (x, π(x))∥ ≤ ∥f * (x, π(x))∥ + β 0 σ max . Since f * is continuous, there exists a B such that f * (C, π(C)) ⊂ B(0, B). Therefore we have: f (C, π(C)) ⊂ B(0, B 1 ), where B 1 = B + β 0 σ max .In the last step we prove that α def = 2 -dx e -B 2 1 /σ 2 and ζ with law of N 0, σ 2 2 satisfy condition of Lemma A.1. It is enough to show that ∀µ ∈ B(0, B 1 ), ∀x ∈ R dx we have:α 1 (2π) dx 2 σ 2 2 dx 2 e -∥x∥ 2 σ 2 ≤ 1 (2π) dx 2 (σ 2 ) dx 2 e -∥x-µ∥ 2 2σ 2which 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 minorisation 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.Since NEORL works in artificial episodes n ∈ {0, N -1} of varying horizons H n . We denote withx n k the state visited during episode n at time step k ≤ H n . Crucial, to our regret analysis is bounding the first and second moment of V πn (x n k ) for all n, 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 {S n } n≥0 with S n ≥ 0 for all n. Let the following holdS n ≤ ρS n-1 + Cfor ρ ∈ (0, 1) and C > 0. Then we haveS n ≤ ρ n S 0 + C 1 1 -ρ .Proof.S n ≤ ρS n-1 + C ≤ ρ 2 S n-2 + C(1 + ρ) ≤ ρ n S 0 + C n i=0 ρ i ≤ ρ n S 0 + C 1 1 -ρ .Lemma A.7. Let Assumption 2.1 -2.8 hold and let H 0 be the smallest integer such thatH 0 > log ( Cu /C l ) log ( 1 /γ) .Moreover, define ν = Cu C l γ H0 . Note, by definition of H 0 , ν < 1. Then we have for all k ∈ {0, . . . , H n } and n > 0 Bounded expectation over horizonEQUATION)Bounded expectation over episodesEQUATION)Moreover, we haveEQUATION) with D(x 0 , K, γ, ν) = V π0 (x 0 ) + K/(1 -γ) Cu C l 1 1-ν + 1Proof. We start with proving the first claimE x n k ,...,x 0 1 |x0 [V πn (x n k )] = E x n k-1 ,...,x 0 1 |x0 [E x n k |x n k-1 [V πn (x n k )]] ≤ E x n k-1 ,...,x 0 1 |x0 [γV πn (x n k-1 ) + K] (Assumption 2.4) = γE x n k-1 ,...,x 0 1 |x0 [V πn (x n k-1 )] + KWe can apply Corollary A.6 to prove the claim. For the second claim, we note that for any π, π ′ and x ∈ X we have from Assumption 2.4V π (x) ≤ C u α(∥x∥) ≤ C u C l V π ′ (x).Therefore,E x n 0 ,...,x 0 1 |x0 [V πn (x n 0 )] ≤ C u C l E x n 0 ,...,x 0 1 |x0 [V πn-1 (x n 0 )] = C u C l E x n-1 Hn ,...,x 0 1 |x0 [V πn-1 (x n-1 Hn )] (Since x n 0 = x n-1 Hn ) ≤ C u C l γ Hn E x n-1 0 ,...,x 0 1 |x0 [V πn-1 (x n-1 0 )] + C u C l K/(1 -γ) (Equation (12))For our choice of H 0 , we have for all n ≥ 0 that Cu C l γ Hn ≤ Cu C l γ H0 ≤ ν < 1. From Corollary A.6, we getE x n 0 ,...,x 0 1 |x0 [V πn (x n 0 )] ≤ C u C l γ Hn E x n-1 0 ,...,x 0 1 |x0 [V πn-1 (x n-1 0 )] + C u C l K/(1 -γ) ≤ νE x n-1 0 ,...,x 0 1 |x0 [V πn-1 (x n-1 0 )] + C u C l K/(1 -γ) ≤ ν n V π0 (x 0 ) + C u C l K/(1 -γ) 1 1 -ν . (Corollary A.6) E x n k ,...,x 0 1 |x0 [V πn (x n k )] ≤ γ k E x n 0 ,...,x 0 1 |x0 [V πn (x n 0 )] + K/(1 -γ) (Equation (12)) ≤ E x n 0 ,...,x 0 1 |x0 [V πn (x n 0 )] + K/(1 -γ) ≤ ν n V π0 (x 0 ) + C u C l K/(1 -γ) 1 1 -ν + K/(1 -γ) (Equation (13)) ≤ V π0 (x 0 ) + C u C l K/(1 -γ) 1 1 -ν + K/(1 -γ)Lemma A.8. Let Assumption 2.1 -2.8 hold and let H 0 be the smallest integer such thatH 0 > log ( Cu /C l ) log ( 1 /γ) .Moreover, define ν = Cu C l γ H0 . Note, by definition of H 0 , ν < 1. Then we have for all k ∈ {0, . . . , H n } and n > 0 Bounded second moment over horizonE x n k ,...,x 0 1 |x0 (V πn (x n k )) 2 ≤ γ 2k E x n 0 ,...,x 0 1 |x0 (V πn (x n 0 )) 2 + D 2 (x 0 , K, γ, ν) 1 -γ 2 (15) with D 2 (x 0 , K, γ, ν) = 2KγD(x 0 , K, γ, ν) + K 2 + C w , and C w = E w κ 2 (∥w∥) + 3(E w [κ(∥w∥)]) 2 .Bounded second moment over episodesE x n 0 ,...,x 0 1 |x0 (V πn (x n 0 )) 2 ≤ ν 2n (V π0 (x 0 )) 2 + C u C l 2 D 2 (x 0 , K, γ, ν) 1 -γ 2 1 1 -ν 2 . (16) Moreover, let D 3 (x 0 , K, γ, ν) = (V π0 (x 0 )) 2 + D 2 (x 0 , K, γ, ν) Cu C l 2 1 1-γ 2 1 1-ν 2 + 1 1-γ 2 . E x n k ,...,x 0 1 |x0 (V πn (x n k )) 2 ≤ D 3 (x 0 , K, γ, ν)Proof. Note that,E x n k |x n k-1 (V πn (x n k )) 2 = E x n k |x n k-1 [V πn (x n k )] 2 + E x n k |x n k-1 V πn (x n k ) -E x n k |x n k-1 [V πn (x n k )] 2 .We first bound the second term. Letxn k = f * (x n k-1 , π n (x n k-1)), i.e., the next state in the absence of transition noise.E x n k |x n k-1 V πn (x n k ) -E x n k |x n k-1 [V πn (x n k )] 2 = E x n k |x n k-1 V πn (x n k ) -V πn ( xn k ) + V πn ( xn k ) -E x n k |x n k-1 [V πn (x n k )] 2 = E x n k |x n k-1 V πn (x n k ) -V πn ( xn k ) + E x n k |x n k-1 [V πn ( xn k ) -V πn (x n k )] 2 ≤ E w (κ(∥w∥) + E w [κ(∥w∥)]) 2 (uniform continuity of V πn ) = E w κ 2 (∥w∥) + 3(E w [κ(∥w∥)]) 2 = C w (Assumption 2.4)Therefore we haveE x n k |x n k-1 (V πn (x n k )) 2 = E x n k |x n k-1 [V πn (x n k )] 2 + C w ≤ (γV πn (x n k ) + K) 2 + C w = γ 2 V πn (x n k-1 ) 2 + 2KγV πn (x n k-1 ) + K 2 + C w . E x n k ,...,x 0 1 |x0 (V πn (x n k )) 2 = E x n k-1 ,...,x 0 1 |x0 E x n k |x n k-1 (V πn (x n k )) 2 ≤ γ 2 E x n k-1 ,...,x 0 1 |x0 V πn (x n k-1 ) 2 + 2KγE x n k-1 ,...,x 0 1 |x0 V πn (x n k-1 ) + K 2 + C w ≤ γ 2 E x n k-1 ,...,x 0 1 |x0 V πn (x n k-1 ) 2 + 2KγD(x 0 , K, γ, ν) + K 2 + C w . (Lemma A.7) Let D 2 (x 0 , K, γ, ν) = 2KγD(x 0 , K, γ, ν) + K 2 + C w . Applying Corollary A.6 we get E x n k ,...,x 0 1 |x0 (V πn (x n k )) 2 ≤ γ 2k E x n 0 ,...,x 0 1 |x0 (V πn (x n 0 )) 2 + D 2 (x 0 , K, γ, ν) 1 -γ 2Similar to the first moment, we leverage that V πn (x) ≤ Cu C l V πn-1 (x) for all x ∈ X , Cu C l γ Hn-1 ≤ ν, and get,E x n 0 ,...,x 0 1 |x0 (V πn (x n 0 )) 2 ≤ C u C l 2 E x n 0 ,...,x 0 1 |x0 (V πn-1 (x n 0 )) 2 = C u C l 2 E x n-1 Hn ,...,x 0 1 |x0 V πn-1 (x n-1 Hn ) 2 (Since x n 0 = x n-1 Hn ) ≤ C u C l γ Hn 2 E x n-1 0 ,...,x 0 1 |x0 V πn-1 (x n-1 0 ) 2 + C u C l 2 D 2 (x 0 , K, γ, ν) 1 -γ 2 (Equation (15)) ≤ ν 2 E x n-1 0 ,...,x 0 1 |x0 V πn-1 (x n-1 0 ) 2 + C u C l 2 D 2 (x 0 , K, γ, ν) 1 -γ 2 ≤ ν 2n (V π0 (x 0 )) 2 + C u C l 2 D 2 (x 0 , K, γ, ν) 1 -γ 2 1 1 -ν 2 (Corollary A.6)Moreover,E x n k ,...,x 0 1 |x0 (V πn (x n k )) 2 ≤ γ 2k E x n 0 ,...,x 0 1 |x0 (V πn (x n 0 )) 2 + D 2 (x 0 , K, γ, ν) 1 -γ 2 (Equation (15)) ≤ E x n 0 ,...,x 0 1 |x0 (V πn (x n 0 )) 2 + D 2 (x 0 , K, γ, ν) 1 -γ 2 ≤ ν 2n (V π0 (x 0 )) 2 + C u C l 2 D 2 (x 0 , K, γ, ν) 1 -γ 2 1 1 -ν 2 + D 2 (x 0 , K, γ, ν) 1 -γ 2 (Equation (16)) ≤ (V π0 (x 0 )) 2 + D 2 (x 0 , K, γ, ν) C u C l 2 1 1 -γ 2 1 1 -ν 2 + 1 1 -γ 2Finally, we prove the regret bound of NEORL.Proof of Theorem 3.1. In the following, let xn k+1 = f n (x n k , π n (x n k ))+w n k denote the state predicted under the optimistic dynamics andx n k+1 = f * n (x n k , π n (x n k )) + w n k the true state. E N -1 n=0 Hn-1 k=0 c(x n k , π n (x n k )) -A(π * ) ≤ E N -1 n=0 Hn-1 k=0 c(x n k , π n (x n k )) -A(π n , f n ) (Optimism) = E N -1 n=0 Hn-1 k=0 B(π n , f n , x n k ) -B(π n , f n , xn k+1 ) (Bellman equation ( Equation (4))) = E N -1 n=0 Hn-1 k=0 B(π n , f n , x n k ) -B(π n , f n , x n k+1 ) + B(π n , f n , x n k+1 ) -B(π n , f n , xn k+1 ) = N -1 n=0 Hn-1 k=0 E B(π n , f n , x n k+1 ) -B(π n , f n , xn k+1 ) (A) + N -1 n=0 Hn-1 k=0 E B(π n , f n , x n k ) -B(π n , f n , x n k+1 ) (B)First, we study the term (A).Proof for (A): Note that becausef n ∈ M n , there exists a η ∈ [-1, 1] dx such that xn k+1 = µ n (x n k , π n (x n k )) + β n σ n (x n k , π n (x n k ))η(x n k ) + w n k . Furthermore, x n k+1 = f * (x n k , π n (x n k )) + w n kand the transition noise is Gaussian. Let ζ n 2,k and ζ n 1,k denote the respective distributions of the two random variables, i.e.,ζ n 1,k ∼ N (f * (x n k , n (x n k )), σ 2 I) and ζ n 2,k ∼ N (f n (x n k , π n (x n k )), σ 2 I). Next, define B = E x∼ζ n 2,k [B(π n , f n , x)],and consider the function h(x) = B(π n , f n , x) -B. Then we have E w n k B(π n , f n , x n k+1 ) -B(π n , f n , xn k+1 ) = E x∼ζ n 1,k [B(π n , f n , x)] -E x∼ζ n 2,k [B(π n , f n , x)] = E x∼ζ n 1,k B(π n , f n , x) -B -E x∼ζ n 2,k B(π n , f n , x) -B = E x∼ζ n 1,k [h(x)] -E x∼ζ n 2,k [h(x)]. Note that E x∼ζ n 2,k [h(x)] = 0 by the definition of h and thus,EQUATIONIn the following, we bound the term above w.r.t. the Chi-squared distance Kakade et al., 2020, Lemma C.2.,) )E w n k B(π n , f n , x n k+1 ) -B(π n , f n , xn k+1 ) = E x∼ζ n 1,k [h(x)] -E x∼ζ n 2,k [h(x)] = X h(x) 1 - ζ n 2,k ζ n 1,k ζ n 1,k (dx) ≤ E x∼ζ n 1,k [h 2 (x)] d χ (ζ n 2,k , ζ n 1,k ) ((EQUATIONSince both bounds from Equation ( 17) and bound we got by applying (Kakade et al., 2020, Lemma C.2 .,), we can apply minimum and have:E w n k B(π n , f n , x n k+1 ) -B(π n , f n , xn k+1 ) ≤ E x∼ζ n 1,k [h 2 (x)] min d χ (ζ n 2,k , ζ n 1,k ), 1Therefore, following Kakade et al. (2020, Lemma C.2.,) we get Sukhija et al., 2024, Cor. 3))E w n k B(π n , f n , x n k+1 ) -B(π n , f n , xn k+1 ) ≤ E x∼ζ n 1,k [h 2 (x)] min { 1 /σ ∥f * (x n k , π n (x n k )) -f n (x n k , π n (x n k ))∥ , 1} ≤ E x∼ζ n 1,k [h 2 (x)](1 + √ d x ) βn /σ ∥σ n (x n k , π n (x n k ))∥ . ((Therefore, we haveN -1 n=0 Hn-1 k=0 E x n k ,...x 0 1 |x0 E w n k B(π n , f n , x n k+1 ) -B(π n , f n , xn k+1 ) ≤ N -1 n=0 Hn-1 k=0 E x n k ,...x 0 1 |x0 E x∼ζ n 1,k [h 2 (x)](1 + √ d x ) βn /σ ∥σ n (x n k , π n (x n k ))∥ ≤ N -1 n=0 Hn-1 k=0 (1 + √ d x ) βn /σ E x n k ,...x 0 1 |x0 E x∼ζ n 1,k [h 2 (x)] E x n k ,...x 0 1 |x0 ∥σ n (x n k , π n (x n k ))∥ 2 ≤ (1 + √ d x ) β T /σ N -1 n=0 Hn-1 k=0 E x n k ,...x 0 1 |x0 E x∼ζ n 1,k [h 2 (x)] × N -1 n=0 Hn-1 k=0 E x n k ,...x 0 1 |x0 ∥σ n (x n k , π n (x n k ))∥Here, for the second and third inequality, we use Cauchy-Schwarz. Now we bound the two above individually. First we bound E x∼ζ n 1,k h 2 (x) .E x∼ζ n 1,k h 2 (x) = E x∼ζ n 1,k (B(π n , f n , x) -B) 2 = E x∼ζ n 1,k (B(π n , f n , x) -E x∼ζ n 2,k [B(π n , f n , x)]) 2 ≤ C 2 1 -λ 2 E x∼ζ n 1,k (2 + V πn (x) + E x∼ζ n 2,k [V πn (x)]) 2 (Theorem A.3) ≤ C 2 1 -λ 2 E x∼ζ n 1,k (2 + V πn (x) + γV πn (x n k ) + K) 2 (Lemma A.4) ≤ √ 2C 2 1 -λ 2 E x∼ζ n 1,k (V πn (x)) 2 + (2 + γV πn (x n k ) + K) 2 ≤ √ 2C 2 1 -λ 2 E x n k+1 |x n k (V πn (x k+1 )) 2 + 2γ 2 (V πn (x n k )) 2 + 2(2 + K) 2Furthermore, we have from Lemma A.8.E x n k ,...x 0 1 |x0 E x n k+1 |x n k (V πn (x k+1 )) 2 + 2γ 2 (V πn (x n k )) 2 = E x n k+1 ,...x 0 1 |x0 (V πn (x k+1 )) 2 + 2γ 2 E x n k ,...x 0 1 |x0 (V πn (x n k )) 2 ≤ (1 + 2γ 2 )D 3 (x 0 , K, γ, ν).In the end, we getN -1 n=0 Hn-1 k=0 E x n k ,...x 0 1 |x0 E x∼ζ n 1,k [h 2 (x)] ≤ √ 2C 2 1 -λ N -1 n=0 Hn-1 k=0 (1 + 2γ 2 )D 3 (x 0 , K, γ, ν) + 2(2 + K) 2 = √ 2C 2 1 -λ (1 + 2γ 2 )D 3 (x 0 , K, γ, ν) + 2(2 + K) 2 N -1 n=0 H n = √ 2C 2 1 -λ (1 + 2γ 2 )D 3 (x 0 , K, γ, ν) + 2(2 + K) 2 √ T .Next, we use the bound from Curi et al. (2020, Lemma 17.) for the second term.N -1 n=0 Hn-1 k=0 E x n k ,...x 0 1 |x0 ∥σ n (x n k , π n (x n k ))∥ 2 ≤ C ′ Γ THere Γ T is the maximum information gain.If we set D 4 (x 0 , K, γ)= C ′ (1+ √ dx) σ √ 2C2 1-λ (1 + 2γ 2 )D 3 (x 0 , K, γ, ν) + 2(2 + K) 2 , we have N -1 n=0 Hn-1 k=0 E x n k ,...x 0 1 |x0 E w n k B(π n , f n , x n k+1 ) -B(π n , f n , xn k+1 ) ≤ (1 + √ d x ) β T /σ N -1 n=0 Hn-1 k=0 E x n k ,...x 0 1 |x0 E x∼ζ n 1,k [h 2 (x)] × N -1 n=0 Hn-1 k=0 E x n k ,...x 0 1 |x0 ∥σ n (x n k , π n (x n k ))∥ 2 ≤ (1 + d x ) β T /σ √ 2C 2 1 -λ (1 + 2γ 2 )D 3 (x 0 , K, γ, ν) + 2(2 + K) 2 √ T C ′ Γ T ≤ D 4 (x 0 , K, γ)β T T Γ TProof for (B):N -1 n=0 Hn-1 k=0 E B(π, f n , x n k ) -B(π, f n , x n k+1 ) = N -1 n=0 E B(π, f n , x n 0 ) -B(π, f n , x n Hn ) ≤ C 2 1 - λ N -1 n=0 2 + E V π (x n 0 ) + V π (x n Hn ) (Theorem A.3) ≤ 2C 2 1 - λ N -1 n=0 (1 + D(x 0 , K, γ)) (Lemma A.7) = 2C 2 1 - λ (1 + D(x 0 , K, γ))N = D 5 (x 0 , K, γ)N.HereD 5 (x 0 , K, γ) = 2C2 1- λ (1 + D(x 0 , K, γ)).Finally, for our choice, H n = H 0 2 n , we getN -1 n=0 H n = H 0 N -1 n=0 2 n = H 0 (2 N -1) = T.Therefore, N = log 2 T H0 + 1 . To this end, we get for our regretR T = E N -1 n=0 Hn-1 k=0 c(x n k , π n (x n k )) -A(π * ) ≤ D 4 (x 0 , K, γ)β T T Γ T + D 5 (x 0 , K, γ)N ≤ D 4 (x 0 , K, γ)β T T Γ T + D 5 (x 0 , K, γ) log 2 T H 0 + 1This regret is sublinear for a very rich class of functions. We summarize bounds on Γ T from Vakili et al. (2021) in Table 1 . Furthermore, note that D 4 (x 0 , K, γ) ∈ (0, ∞) for all x 0 ∈ X with ∥x 0 ∥ < ∞, K < ∞, γ ∈ (0, 1). The same holds for D 5 (x 0 , K, γ). Moreover, sinceV π (x) is Θ(ζ(∥x∥)), both D 4 and D 5 are Θ(ζ(∥x 0 ∥)).Table 1 : Maximum information gain bounds for common choice of kernels.Kernel k(x, x ′ ) Γ T Linear x ⊤ x ′ O (d log(T )) RBF e -∥x-x ′ ∥ 2 2l 2 O log d+1 (T ) Matèrn 1 Γ(ν)2 ν-1 √ 2ν∥x-x ′ ∥ l ν B ν √ 2ν∥x-x ′ ∥ l O T d 2ν+d log 2ν 2ν+d (T )NeurIPS Paper Checklist* Correspondence to sukhijab@ethz.ch 38th Conference on Neural Information Processing Systems (NeurIPS 2024).https://github.com/lasgroup/opax/tree/neorlbased on the environment 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: - Is there any comment on the tightness of the regret?
- How well does NeoRL scale to high-dimensional environments such as Humanoid?
limitations: limitations: The paper discuss the limitation of the theoretical results. I do not see any potential negative societal impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

2. 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].

3. 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.

[1] Treven, L., Hübotter, J., Dorfler, F. and Krause, A., 2024. Efficient 
exploration in continuous-time model-based reinforcement learning. *Advances in Neural Information Processing Systems*, *36*.

[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.

[3]Hafner D, Pasukonis J, Ba J, Lillicrap T. Mastering diverse domains through world models. arXiv preprint arXiv:2301.04104. 2023 Jan 10.

[4] Hansen N, Wang X, Su H. Temporal difference learning for model predictive control. arXiv preprint arXiv:2203.04955. 2022 Mar 9.

[5] Hansen N, Su H, Wang X. Td-mpc2: Scalable, robust world models for continuous control. arXiv preprint arXiv:2310.16828. 2023 Oct 25.

[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.

[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.
questions: questions: 1. Could the author provide a more intuitive explanation about which part of the algorithm improves performance in non-episodic settings?

2. Could the author explain why the planning horizon needs to be doubled after each “artificial episode”?

3. Is NeoRL extendable to problems with unknown rewards (cost functions)?
limitations: limitations: The limitations and assumptions for the theory results are discussed in section 2
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The optimization problem in Equation (6) for policy selection may be computationally expensive, especially for high-dimensional systems. 
2. 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.
3. The authors can discuss some data-driven MPC framework, like [1,2].

[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.

[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.
questions: 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?
2. Can the bounded energy assumption be relaxed or replaced with alternative assumptions to broaden the applicability of NEORL?
limitations: limitations: The authors have discussed the limitations.

Comments: title: Official Comment
Official Comment
Follow up on the rebuttal
Response to reviewer
comment: Thank you also for your engagement in the review process and the constructive feedback!
Thanks a lot for your active engagement in the review process. We will adapt the paper based on the feedback and discussion from the rebuttal period.
Thank you very much for the rebuttal! I acknowledge that I read it.
Thanks to the author for the detailed response. For the open topics mentioned, I hope the authors will add some discussions in the final version to attract researchers from different fields. I will keep my score.
Dear Reviewer,

We hope this message finds you well. We have noticed that our detailed rebuttal, addressing each of the concerns raised in your review, has not yet received any feedback. Please let us know if our responses address your concerns or if you have any other concerns. We hope with our response we could further reinforce your confidence and positive evaluation of our work.

Thank you,

Authors
Thanks a lot for the active engagement in the review process and for increasing our score. We are glad we could adeptly address your concerns. If there are any other questions, that we can address to to further improve your score or confidence in our work, please let us know.
I thank the authors for their very detailed response, which addressed most of my concerns and made the contribution of this work clear. I raised my score from 4 to 6.