The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective
Authors: Michael Muehlebach
Zhiyu He
Michael I. Jordan
Venue: ICLR 2026 Poster (2026)
Keywords: control theory
reinforcement learning theory
dynamical systems
learning theory
Primary area: learning theory

Abstract: We study the sample complexity of online reinforcement learning in the general non-episodic setting of nonlinear dynamical systems with continuous state and action spaces. Our analysis accommodates a large class of dynamical systems ranging from a finite set of nonlinear candidate models to models with bounded and Lipschitz continuous dynamics, to systems that are parametrized by a compact and real-valued set of parameters. In the most general setting, our algorithm achieves a policy regret of $\mathcal{O}(N \epsilon^2 + d_\mathrm{u}\mathrm{ln}(m(\epsilon))/\epsilon^2)$, where $N$ is the time horizon, $\epsilon$ is a user-specified discretization width, $d_\mathrm{u}$ the input dimension, and $m(\epsilon)$ measures the complexity of the function class under consideration via its packing number. In the special case where the dynamics are parametrized by a compact and real-valued set of parameters (such as neural networks, transformers, etc.), we prove a policy regret of $\mathcal{O}(\sqrt{d_\mathrm{u}N p})$, where $p$ denotes the number of parameters, recovering earlier sample-complexity results that were derived for *linear* *time-invariant* dynamical systems. While this article focuses on characterizing sample complexity, the proposed algorithms are likely to be useful in practice, due to their simplicity, their ability to incorporate prior knowledge, and their benign transient behaviors.

Published as a conference paper at ICLR 2026
THE SAMPLE COMPLEXITY OF ONLINE REINFORCE- MENT LEARNING: A MULTI-MODEL PERSPECTIVE
Michael Muchlebach
Zhiyu He
Max Planck Institute for Intelligent Systems Tuebingen, Germany
Max Planck Institute for Intelligent Systems Tuebingen, Germany zhi yu. heltuebingen wtw.ppp........
mi chaelm@ tubbingen mpg. de
Michael I. Jordan
Inria Paris, France
University of California, Berkeley, USA jordanêcs ber.eerreyy..... eleellyy.... edu
ABSTRACT
We study the sample complexity of online reinforcement learning in the general non-episodic setting of nonlinear dynamical systems with continuous state and action spaces. Our analysis accommodates a large class of dynamical systems ranging from finite of nonlinear candidate models models with bounded and Lipschitz continuous dynamics, to systems that are parametrized by a compact and real-valued set of parameters. In the most general setting, our algorithm achieves a policy regret of O + d.,ln (..n(m()))//²) where N is the time horizon, is a user-specified discretization width, d, the input dimension, and m(c) measures the complexity of the function class under consideration via its packing number. In the special case where the dynamics are parametrized by a compact and real-valued set of parameters (such as neural networks, transformers, etc.), we prove policy regret of ( /du.N)). where p denotes the number parameters, recovering earlier sumple-complexity results that were derived for linear time-ine iine-invariant dynamical systems. While this article focuses on characterizing sample complexity. the proposed algorithms likely be useful in practice, due their simplicity, their ability to incorporate prior knowledge, and their benign transient behaviors.
INTRODUCTION
Reinforcement learning describes the situation where decision maker chooses actions to control a dynamical system, which is unknown priori, to optimize performance measure. At the core of reinforcement learning is the fundamental dilemma between choosing actions that reveal information about the dynamics and choosing actions that optimize performance. These are typically conflicting goals. We consider an online non-episodic setting, where the decision-maker continuously and is unable to reset the state of the dynamical system. This further introduces the chal- lenge that the information received by the learner is correlated over time and hence, standard statistical tools cannot be applied directly. Despite these important challenges, reinforcement learning algorithms that build on Hedge-type updates (Cesa-Bianchi Bianchi & Lugosi 2006) and posterior sampling reinforcement learning (Osband al., 2013), while being straightforward to analyze, practically and theoretically relevant, and offering strong non-episodic, nonasymptotic, frequentist policy-regret guarantees that apply to continuous state-action systems. The algorithms sample from posterior over the different model candidates (or approximation thereof), apply the corresponding "certainty-cquivllee policies (Mania et al. 2019). while carefully introducing enough excitation to ensure that the posterior distribution over models converges sufficiently rapidly.
required to learn
provide a suite of online
We consider three different settings. In the first setting, the decision-maker has access to a finite set of nonlinear candidate models that potentially describe the system dynamics (continuous state and action spaces). This setting is relevant for many practical engineering applications, where the choice of candidate models provides natural way incorporate prior knowledge. In this setting online

---

Published as a conference paper at ICLR 2026
algorithm achieves sample complexity of ((d + In(m))/A) in terms of policy regret, where N denotes the time horizon, m the number of candidate models, du the input dimension, and A > 0 constant that characterizes the separation between models. In the second setting, we allow for any class of dynamical system, where the dynamics are given by a bounded set in a normed vector space. This includes, e.g., all bounded Lipschitz continuous functions with the supremum norm, or bounded set of square integrable functions. By applying packing and covering arguments, we relate the second setting to the first one and derive corresponding policy-regret guarantees that take the form ( + d, (m number, which measures the complexity the function class (Wainwright 2019). In the third setting, we consider systems that are parametrized by compact and real-valued set of parameters. This includes the situation where the dynamics are parametrized by neural networks, transformers, or other parametric function approximators, and we obtain a policy regret of (( Np), where p describes the number of parameters. We further note that in the common situation where our function class is given by a linear combination of nonlinear feature vectors, which also encompasses linear dynamics as a special case, our algorithm is straightforward to implement, as it only requires sampling from a (truncated) Gaussian distribution at every iteration (Cao & Katzfuss 2024).
where describes the discretization width and m(c) the packing
Our main contributions are summarized as follows:
We provide suite of algorithms with nonasymptotic policy-regret guarantees for online reinforee- ment learning over continuous state and action spaces with nonlinear dynamics. Numerical results highlight that transients are benign and that our algorithms are likely to be useful in practice.
Compared to earlier works on posterior sampling reinforcement learning (Osband et al. 2013 Abbasi-Yadkori Yadkori & Szepesvári 2015; [u et al. 2224] Ouyang et al. (2177), algorithm introduces additional exploration and achieves frequentist policy-regret guarantees. Our analysis operates under standard identifiability and persistence of excitation assumptions (Ljung 1999, Slotine & Lij
1991) suitable for continuous state-action systems even near the stability boundary, which contrasts
resampling strategies (Ouyang et al.) 2017) or mixing assumptions (Xu et al., (024).
e.g..Dean Results from earlier works on the quarr-quaraati regulator (see, e.g., Dean et al.) 2018)] Simchowitz
& Foster 2020) are recovered up to constants when specializing to linear dynamics. In contrast to the taaximum-a-posterrinn
identification principle in these works, we rely on posterior sampling, resulting in Hlddge-type algorithm that is general and tractable for analysis.
Compared to earlier work in the adaptive control community (see, e.g. Anderson et al., 2000 Hespanha et al., (001], which focuses on asymptotic stability, boundedness, and deterministic systems, we consider stochastic systems and characterize nonasymptotic performance. We provide nonasymptotic bound on the second moment of state trajectories and show that our estimation converges finite time almost surely.
The work provides a powerful separation principle that applies to nonlinear dynamics. Our algorithms separate optimal model identification and certainty-equivvlenn control, simplifying policy evaluation, c.g., through predictive control or proximal policy optimization with a simulator.
The decision Decision-making problem considered here is central to machine learning and related disciplines, and there has been a great deal of prior work. We provide a short review of recent prior work that is closely related in the following paragraphs; a more detailed literature review can be found in App. A
The fundamental exploration-exxlooiation dilemma of reinforcement learning has been elegantly addressed from many angles. Posterior sampling reinforcement learning is an algorithmic paradigm introduced by Osband et al. (2013); Osband & Van Roy (2014); Osband et al. (2016); Osband & Van Roy (0017). which draws analogies to stochastic multi-armed bandits and Thompson sampling (Russo et al. 2018). While these works initially focused on tabular Markov decision processes and
episodic settings, extensions to the non-episodic setting have been achieved by Abbasi- Yadkori & Szepesvári (2015); Ouyang et al. (2017): Theocharous et al. (2018); Xu et al. 22024p. Our algorithmic idea broadly falls into the category of posterior sampling reinforcement learning, with the distinction of introducing additional excitation and bridging insights from statistics, online learning (Hedge), and control (dissipativity) to providefrrqquem frequentist policy-regret guarantees, whereas these works provide Bayesian guarantees. We further rely on persistence of excitation assumptions, which are common in system identification and statistics (Ljung) 1999 Slotine & Li 1991). These are weaker than the mixing assumptions of earlier works (see, e.g.. Xu et al.) 2024).
Optimism in the face of uncertainty is another important principle to balance exploration and exploitation (Lattimore & Szepesvári 2020 Early works by Auer & Ortner (2006); Bartlett &
2

---

Published as a conference paper at ICLR 2026
Jaksch et al. (2010) focus the tabular setting, while plethora of recent works (Abbasi- Yadkori & Szepesvári 2 et al.) 2019 Abeille & Lazaric (2200 Croissant et al.
Tewari 2009);;
Cohen
2024; Zanette et al.) 2021) demonstrate the usefulness of this principle in handling continuous state-action systems. These approaches maintain confidence sets of parametric models and sample the most optimistic model and policy for exploration. The iterative computation of confidence sets and optimistic policies can be challenging and computationally intensive. Moreover, the resulting complexity measures affecting policy regret, such as the eluder dimension (ooterr & Rakhlin 2023 can be difficult to bound beyond linear Markov decision processes. In contrast, we decouple online best model identification and ertainty-equivalent control. This separation not only simplifies policy evaluation (e.g., offline or through model predictive control (Borrelli et al. (017)), but also facilitates explicit characterization of policy regret via packing numbers, a standard and well-studied complexity measure in statistics.
The research frontier in the domain of reinforcement learning with continuous states and actions
(Recht 2019; Meyn 2022 Hu et al. 2023) moves from linear (Hazan & Singh 2022] Tsiamis et al. 2023) to nonlinear dynamics. Prior work (see, e.g.. Kakade et al., 2020; Botfi et al. 202 1] Lin ct al. 2024) shows that sublinear O ((vN) N) regret can be achieved under structural assumptions on the dynamics, e.g., contraction or linear representations of nonlinear features, which are stronger than what is assumed herein. Our approach is also related to multi-model adaptive control, where the goal is asymptotic stabilization (Anderson & Dehghani 2008), and online switching control (Li et al., 2023; Kim & Lavaei 2024). In contrast, we provide nonasymptotic policy-regret guarantees that go beyond stabilization and scale with (In(m)) compared to O /3) obtained with switching control. Another important family of methods for learning with continuous states and actions arises from online optimization over an appropriate policy class, such as disturbance-action policies (Agarwal
al.
2019
Hazan al. 2020 Simchowitz al. 2020 Li et al.) 2021 Chen & Hazan 2021] Zhao
ct al.
2023 that are motivated from robust control for linear systems Garttka & Wets 1974 Löfberg
2003
Goulart et al. 2006). Another major approach is to directly optimize over policies, c.g.,
parametrized via linear functions, by applying zeroth-order or first-order optimization techniques (see, e.g., |Fazel et al.j [2018] Ma et al., [024]] Hu et al., 2023). Compared to the algorithms and analysis presented herein, the benchmarks in these works are typically different, and focus, for example, on the set of linear disturbance feedback policies or various policy parametrizations that are optimized subject to fixed system model. The system dynamics are known priori to the decision-maker, and a tradeoff between exploration and exploitation is absent.
The sample complexity of general interactive decision- making is captured by the - Coefficient (Foster et al. 202T 2023) Foster & Rakhlin (023). a statistical measure constituting regret lower bounds and supporting an -orratiioo-t-deiiiionn meta algorithm that achieves matching regret upper bounds. This measure generalizes previous frameworks, for instance Bellman rank (Jiang et al. 2017), bilinear classes (Du al. 2021). and Bellman eluder dimension (Jin et al.! 2021). and highlights the interplay among model estimation, model class complexity, and sample efficiency. Coefficient offers abstract characterizations applicable general classes of problems and models, we focus on online reinforcement learning problems with continuous states and actions in non-episodic regime. The challenges herein, such as dependent states, actions, Coefficient
While the Decission-Estimatii
and losses and stability, are not directly handled in the existing framework. Moreover, nonlinear dynamics may further complicate the specifications of Bellman rank and related variants, which hinge on (linear) function approximation. To address these issues, we leverage tailored tools (e.g., Hedge in online learning and dissipativity in control) and highlight the role of separating best model identification and certainty control for sample-efficient reinforcement learning with various model classes (c.g., finite, infinite, and parametric families).
All the aforementioned works provide basic treatment of online decision-making, However, achieving sublinear policy regret in an online non-episodic setting remains a critical challenge. Our work addresses this challenge in the setting of nonlinear dynamics and smooth non-quadratic stage costs, while recovering earlier (VVd,Np) regret bounds that are tailored to linear quadratic regulators (e.g.. Simchowitz & Foster 2020). avoiding structural assumptions (Kakade et al., 2020 Boffi et al.
2021 Lin et al. 2024), and greatly improving on the rates from switching control (IIn()) compared to 1/3 or worse). We also differ from previous work on posterior-sampling -aaed reinforcement learning (Osband al. (2013) in that we provide frequeniitt policy-regret guarantees and closed-loop stability in an online non-episodic setting. Our approach can further be directly integrated into nonlinear model predictive control techniques (Rawlings et al. 2017 Borrelli et al.
3

---

Published as a conference paper at ICLR 2026
Algorithm 1 RReinforcement learning ($1)
Algorithm 3 Reinforcement learning (S3)
Inputs: F== (f=....... fm) M, foox )==
Inputs: F {fo E f2 J. 17. M, {o )
compute {1² :.... 1st can be approximated by MPC, PPO on simulator* for k 1.... do
e.g. by d. p.
for k = 1,... do
I/ every Mth step if mod(k 1, M) = 0 then
*x Σj= 1 - 1
every Mth step mod(k 1, M) = 0 then
11 8₂ ~ e--eppnnssul Leen/2
اド= 1 u 11 76
Vi (m)
compute Ae corr. fo E F // e. by d. p. 1e can be approximated by MPC, PPO step*/
is exp( 1/t
else
else
i/ 1 end if
Mstay with ix-1
0₂ = O
/ssta with 0k-1
end if
//follow policy in and add excitation Ue = 1 (Ix) ) Buks Mak N(O, T)
//follow policy 02 and add excitation Us = juth (xx) + Duki Ruk ~ (0, di
end for
end for
2017) as also highlighted in App. B and avoids the computation of optimistic policies confidence
regions (Abeille & Lazaric 2020: Croissant et al. 2024)).
The article is structured as follows: Sec. 2 discusses the problem formulation and presents the main results. Sec. jillustrates our analysis, where we focus on the first setting (finite set of models) the other two settings are similar at high level and we provide detailed presentation in the appendix. Sec. Ssc.Appme provides a short conclusion, while proofs, numerical experiments, and further discussion is included in the appendix.
PROBLEM FORMULATION AND SUMMARY
We consider a reinforcement learning problem where a decision-maker chooses actions uy E Rds to control a dynamical system Fk+11 f u&) + nr, where Ih E Rdx denotes the state, f Rdd x Idd= + Rd the dynamics (unknown to the decision-maker), and ny ~ (O, a²1) 1) the process noise (independent across time; can be non-zero-mean sub- Goussaasnin, see below). Without loss of generality, we set 21 = O. We further denote the Lipschitz constant of f in (æ, u) by L.
The decision-maker aims at minimizing the expected loss, E k= (( 2x]], where ( R4 x Rd + R200 captures the stage cost, by learning and applying an appropriate and possibly random feedback policy uy= = 14 (Ix).
We consider three different settings. In the first setting (S1) the decision- maker has access to m (nonlinear) candidate models F := {ff ..... frm), fr Rd x Rd + Rd,, i = 1...., m that describe potential system dynamics. Each I I--Lipschitz (æ, u). In the second setting (S2), we allow for any class of functions F that is given by bounded set in a normed vector space, which is therefore much broader and includes, for example, all bounded L-Lipschitz functions with the usual supremum norm. In the third setting (S3), the dynamics 0, i.e., F (f u) 0 E 22), where Ω is a compact real-valued set. Without loss of generality, assume that Ω is contained in unit ball by scaling the parameters accordingly. This captures the setting where the functions fe are represented by neural or transformer architectures, or when Sa are given by linear combinations of (nonlinear) feature vectors fo(x, u) 0 Φ(x, u)). This also encompasses linear dynamics as a special case. We further assume that the system dynamics f are contained in the set of candidate models, i.c., f é F for each setting. This realizability assumption can be casily relaxed as discussed in App. G provided that there is single candidate model that is closest to f on the entire state-action space.
parametrized by the parameter
This article analyzes the decision-making strategy listed in Alg. I which can be easily adapted to the settings 52/S3 (see Alg. in App. D and Alg. (3). The algorithm keeps track of the one-step prediction error (Ljung 1999: Chua et al. 2018 Janner et al. 2019), that is,
Øj41 f' u.)
PEF.
(I)
1+ |x (1,,,,
4

---

Published as a conference paper at ICLR 2026
where b > 0 is a sufficiently large constant, and ((2y, denotes the fy-norm of a vector stacking by and ug. The normalization with 1 + (x mxx){²/8² ensures that the variables sf. remain bounded even when TR, uy become arbitrarily large, while for small Ik. ug the normalization is close to the identity. This will simplify the subsequent analysis and the resulting statement of the poliey-regret bounds. Our analysis also carries over to the limiting case where b is unbounded (i.c., b + oo), and the same regret bounds apply, is discussed in App. [ however, the constants in the resulting regret guarantees and algorithm parameters become more complex. The sum of squared distances bai+1 - (ar,, u²)]² can be interpreted as the negative log-likelihood of model i given the past trajectory (ay, uj -- due to the Gaussian process noise. Hence, from Bayesian perspective, the distribution exp( represents the probability that model I corresponds to ʃ given the past trajectory. The scaling with 7 implements softmax (for v) large we greedily pick the model that maximizes the posterior, for v) Rs we directly sample from the posterior). The update rule has close connections to Hedge or multiplicative weights, which is common decision maaiing strategy in online learning Nonetheless, our setting is mathematically distinet from Hedge due to dynamics that couple states, actions, and rewards across time, and the need for exploration. As such, existing analysis techniques do not apply. Furthermore, our analysis extends to non-zero-mean fig, since this can be captured by modifying f accordingly, and generalizes to sub-Gaussian process noises thanks to the corresponding bounds on moment generating functions.
& Lugosi 2006 Arora et al. 2012 Mourtada & Gaittas 2019).
The algorithm chooses control actions uy as
Uk th (zx) Nuk:
where nukk- (N, Luk J). and in is a random variable that is defined in the following way: If mod - M) 0, is takes the value is i with probability density p exp( // (conditional on the past), where Z denotes a normalization constant. If mod(k - 1, M) + 0, is remains fixed, i.e., in- 11- The random variable switches only every Mth step, which ensures that the excitation with nuu is rich enough, as specified precisely in Ass. below.. The feedback policy n² describes any policy associated with candidate model f², i.c., a policy that achieves the performance
1 E
limsup sup N N
Maree p (xt)) =
k=1
on the candidate model f', where o 2b41 == f' w² (zt)) ny with æ = 0. The policy je¹ can be optimal for model f", but this does not necessarily need to be the case. In practice, such policy can be obtained by solving a Bellman equation through (approximate) dynamic programming (Bertsekas) 2017), or by applying proximal policy optimization in conjunction with an offline simulator. We assume 7 (i.e., the steady-state performance of je' associated with f`) to be finite for all i. If y is infinite, then the corresponding model f' should be excluded. We will consider policy regret as our performance objective, where the policy i corresponding to the dynamics f represents the benchmark performance.
The reinforcement learning strategy has a natural interpretation: The strategy selects, at each A/th iteration, the feedback policy n²*, where the index ig sampled from distribution following softmax function of st. The system is further excited by adding the random perturbation Nuk to the feedback policy. If persistence of excitation is guaranteed, the estimation will converge at rate at least ( which yields a policy regret (compared to the strategy μ corresponding to the dynamics f) that scales logarithmically in the horizon N and the number of candidates m.
We emphasize that our analysis technique translates in straightforward ways to more general situations than the ones described herein. For example, while this article focuses on time-invariant policies. would be straightforward to also incorporate time-varying policies pdg and a corresponding finite- horizon benchmark. More precisely, we focus on steady-state performance, where the benchmark is given by the steady-state performance of policy μ (corresponding to f). However, finite-horizon objectives can be easily accommodated by measuring regret with respect to the optimal finite-horizon policy pa; the same nonasymptotic regret bounds would apply. The article also focuses on "naive" excitation signals Rukk sampled from a normal distribution. However, our analysis principle is flexible enough to also incorporate more general type of excitation strategies relying on domain- specific knowledge), as long as the excitation has finite second moments and guarantees a persistence condition similar to Ass.
5

---

Published as a conference paper at ICLR 2026
Our results summarized as follows:
Theorem 2.1 (51) Let the cost-to-go function corresponding to J and the stage cost be smooth (see Ass. Land 2). the feedback policies μ² be Lipschitz continuous, and let a persistence of excitation condition be satisfied (see Ass. 3). Then, for a constant learning rate ni and o 1/(ak) ln(m)/(Ak²) the policy regret of Alg. 1 dis bounded by
N
E (Tr un)) - NY S Gidgl((N)/A G2dgln(m)/A + Ga + Gidu/A,
for all N 2 2M, where Crt, Cr,, Gr3 are constant, "/ corresponds to the steady-state performance related to f (see (2)), and A characterizes the discrepancy between models. The precise constants are listed in Thm. 3.2
Theorem 2.2 (S2) Let the set of candidate models be a bounded set normed vector space. Let the cost-to-go go function corresponding to f and the stage cost be smooth (see Ass. A and 5
the feedback policies 2e corresponding to an f E F be Lipschitz continuous, and let a persistence
of excitation condition be satisfied (see Ass. 4). Then, for all 2 2M, any > 0. for constant
learning rate 7, and oz 1/(e2k) + In(m (c(k? bounded by
) the policy regret of Alg. 2 (see App. D is
N MIx: ug)] Ny NY No Gid, + (2d,)n(m()))22 + G3o
E
where ml(e) denotes the packing number of the set F. The precise constants are listed in Thm. D.2
Theorem 2.3 (53) Let the set of candidate models F be parametrized by 0, ie., F (So(a, u) 0 e U}, where Q C TRP is contained in a unit ball of dimension p. Let the cost-to-go function correspond- ing to f and the stage cost be smooth (see Ass. 2 and Ass. 7. the feedback policies μi corresponding to each fo E F be Lipschitz continuous, and let persistence of excitation condition be satisfied (see
Ass. 6y. Then, for all N 2 2M, for a constant learning rate n, and ohe regret of Alg. 3is bounded by
the policy
Σ ElEKR u6)l - NY ((anln(N) + Cop)d G30
The precise constants are listed in Thm. E.
The above theorems follow from Thms
and by renaming constants. We refer Sec. 3.1 and the appendix for formal proofs. The results characterize precisely how the policy regret scales with the dimension dx, dy and the time horizon N. In the setting of Thm. 2.1 we have finite class of models, and the policy regret scales with In(m), which is in line with the literature on online learning CCesa-Bianchi Lugosi 2006) Lattimore & Szepesvári 2020 Thm. 2.2 relies on a packing argument, whereby the set F is successively approximated by finite number of candidate models. The result stated in full generality; for a specific function class E and packing number mn() the right-hand side can be minimized over (the discretization width). For instance if F consists of the space of bounded L-Lipschitz functions, the packing number m(c) scales with dy cxp((L/c) dda++d.). which means that the policy regret grows roughly with no-regret learning for very large class of functions. In the special case where d. d, 1, the right-hand side grows with VN. Thm. 2.3 is of direct practical importance, since it provides an algorithm and corresponding regret bound that applies to the typical scenario where the functions F are parametrized, for example by neural networks. In the simplest setting, F consists of linear dynamical systems, which directly recovers well-known results from the literature (e.g., (e.g..Dean et al.) 2018, Mania et al. 2019 Simchowitz & Foster 2020). More precisely, if F consists of linear
= o(N), and establishes
1 'The bound depends on A, characterizing the discrepancy between models. models are arbitrarily close to each other, the bound applies asymptotically and becomes loose for small m and N. In this situation, a tighter bound of O( O(yd.N (n(mm) is achieved for small m, N. by distinguishing models to ensure A In(mm// /N. The situation is captured by Thm. 2.2 and Thm. 2.3 and is therefore not discussed further.

---

Published as a conference paper at ICLR 2026
dynamical systems, the number of parameters is given by de dzdu, which means that the resulting regret bound scales with v(dy + ded,)d,
Our algorithms are optimal up to logarithmic factors, since the formulation incorporates online regression as special case. This results in an I(d,)n(m)) lower bound for setting (S1) and O (VNNd.p) lower bound for setting (S3) (Rakhlin & Sridharan, 2014).
We conclude the summary by commenting boundedness of states. In control-theoretic applications (and in the related community) boundedness of solutions and benign transients are a primary concern. We will see that in all our results we can ensure boundedness provided that the stage cost satisfies ((, u) 2 Li | for a constant L > 0. More precisely, we can guarantee that
=E| S 2x[](xx)] S cb
for all = 1,... along the trajectories of our reinforcement learning algorithm, where refers to the cost-to-go function corresponding to the dynamics ʃ and policy μs, and > 0 is an explicit constant. Due to the fact that the dynamics are Lipschitz continuous and ng, fuk are Gaussian, 2y. uk are in fact Gau-san with mean and second moment bounded by /os/ Ln and L4, respectively, and therefore characterize tail probabilities for finite k as well as for arbitrarily large values of l under ergodicity assumptions.
SUMMARY OF THE ANALYSIS
This section discusses the technical details and insights that lead to the results presented in Thm. 2.1 The presentation focuses on setting 81, since the results in setting S2 and S3 follow analogously.
2.3
3.1
FINITE MODEL SET-UP
This section considers
F= = { ... f being finite and f E F. We denote the cost-to-go function related to the dynamics f and the policy μ by V Rd + R20. where V is any function that satisfies the following assumption:
Assumption (Bellman type inequality) The cost-to-go function V (corresponding to and p) satisfies the following inequality
V(x) Z E[((r, u) + +V[(,, u) + n)] - dubroo
(4)
for constant Ln and for all x E Rds,, where u = plz) + nu. n ~ (0000001)1...... n. ~ No,,0 and the expectation is taken over n. and Thy-
Ass. is met for linear dynamical systems Abeille & Lazaric 2020 Abbasi- Yadkori & Szepesvári 2011 Simchowitz Foster 2020; Dean et al.. 2018) and nonlinear dynamical systems under
dissipation assumptions (Khalil 2002
Ch. 5), e.g.. Boffi al. (202 Li et al. (2023). The rationale behind Ass. i is the following: From a dynamic programming point of view computing an optimal policy μ requires solving corresponding infinite-horizon a corresponding Bellman equation and cost-to-go function might not exist, as for example discussed in Bertsekas (017)) Ch. 5. The formulation via Ass. cercumments these technical difficulties, due to the fact that y is not required to correspond to the optimal infinite-horizon average cost. Indeed, from control-theoretic point of view Ass. characterizes a notion of dissipation (Willems 2007). where V represents a storage function and -1(x, u) + the supply rate (for du = O). Moreover, a Bellman equation (Bertsekas) 2017 Prop. 5.5.1) and corresponding cost-to-go function exist for the dynamics f. then Ass. is clearly satisfied for the corresponding cost-to-ge function (for
ceraage-ost-per--eeee
problem. In general,
o, = 0). The additional term Lf captures the influence of the excitation nu and is without loss of generality, since for any smooth function & Rdd + the following applies
EiE(u + m.)) E({(w)= VE(U) nu + 2" n
2 E(ū) nu Elg(u)) + O(do)))
where ny N(0, o The constant L, in Ass. [ makes the previous bound quantitative. Ass. excludes dynamics where slight perturbation the input away from the policy y leads to an unbounded cost?)
A simple example Ie exp(exp(ux)) 1(x, u) x² where =Jexp(exp(n()))) is unbounded.
7

---

Published as a conference paper at ICLR 2026
We will further require the following smoothness conditions:
Assumption The policies μ² are L Lipschitz, the stage-cost is L smooth, and the cost-to-go function V is Ly smooth and satisfies V(x) 2 -cy + /2 some Ly > 0 and Gy 2 0.
Ass. 2 is met for linear dynamical systems (Abeille & Lazaric 2020 Abbasi-Yadkori Yadkori & Szepesváni
2011 [Sicchoiiz & Foster 2020; Dean et al. 2018) and many nonlinear dynamical systems, e.g., (Khalil) 2002] Ch. 5) when is a positive deñnite quadratic. These smoothness assumptions will be needed to analyze how the cost-to-go V evolves if the feedback policy μa & μ. is applied and prevent the state from diverging finite time. We note that the quadratic lower bound on V (ax) is automatically satisfied in view of Ass. if [xx u) 2 L| for a constant L > 0.
We further require the following assumption:
Assumption There exists an integer M > O and two constants A I1 E Rd4,, On > O, and I E J.
0 and b such that for any
| (3RK, ux) (Ir, ux)l2
2 Ao
M
1+ (Ikk ux)
holds, where T++1 = fax,, ux) + nk, uk = 1 (xx) + nuk with ny N(0, 02I), nuk ~N(0, of and q m...
The previous assumption specifies persistence of excitation, which guarantees that the estimate is of the best candidate model will quickly converge to i", where f = f. and is standard in the statistics (Fisher information) and system identification literature (see, e.g., Lijng 1999 Ch. 8.2); (Slotine &
Li T991 Ly et al. 2017 Chatzikiriakos et al. 2025). Ass. Ass. generically satisfied for linear systems with M 2, whereby the constant A relates the controllability of the closed-loop dynamics and Aß
I and [ B of the different candidate models with | IP the Frobenius norm, see App. F The assumption is also met for a broad class of nonlinear dynamical systems, as shown in App. and Prop.
the accuracy |AA'
3 includes normalization with the constant b, whereas the oo. However, as discussed in App. ppp.Foour analysis also encompasses the case 6 oc; the resulting constants are more elaborate and therefore focus discussion the situation where is finite. Moreover, Ass. 3 is a more general version of the "uniformly excited
F22 Ass.
literature usually considers
feature" assumption, which is common in online reinforcement learning (Hao et al. 2021 Liu et al.)
2023
Lazic et al. 2020) and arises from f'(x, u) = ő(x, u) 8' and setting M
Our analysis of Alg. [ staatss by showing that the convergence to the best candidate model is fast, which leads to the logarithmic scaling of the policy regret with N and m. This is summarized with the following proposition:
Proposition 3.1 Let Ass. 3 be satisfied and let the step size be minn
Then, the following holds
k- M
An
Pr(ie = S Sexp
for k = 1,2.... and any i + i", where fr = f. Moreover, it holds that
M
Pr(ie #1) (k - --2
Vk M+1
4 for 2 , (1 (147Mn +
In(m) (TR/Ar))=), where [.] denotes rounding to the next higher integer.
Proof The proof can be found in App. C.I and relies on concentration of measure argument.
An immediate corollary of the fast convergence rate established with Prop. 3.1 is that the sequence éx will converge to 8t in finite time (almost surely), where f f. This is discussed in Cor. C.6 As result of Prop. 3.1 we are now ready to state and prove our first main result that characterizes the policy regret in setting $1.
8

---

Published as a conference paper at ICLR 2026
Theorem 3.2 Let Ass.
and be satisfied and choose n S min(1/(4Mo"). 1/((M) and Then, the policy regret of Alg. bounded by
Juk as in Prop. 3.1
N
ElU ux)) Ny - 4
k=1
for all N 2 2M, where the constants Co, 02 are specified in Lemma C.3 and Crl, Cr2 are given by
Cr1 = 3c, M Tw co) G224//A, Cx = 8c, (Iv T,2 T Tn)/nn
Ca = e
Proof (Sketch, details are in App. The proof relies on using V as a Lyapunov function and performing the following decomposition
E1v(1)+1 -E(V(= + PP #1)
=
(5)
The first term describes the evolution of V (xx+1) when choosing is # and in this (unfavorable) situation V may grow at most exponentially. This is captured by the following bound that relies on the continuity assumptions on V (see Lemma
E[ i"] cg + O(o² + o EEi( ui)lis * i"].
where the notation O hides continuity and dimension-related constants. The second term in (5) describes the favorable situation of choosing in i", where ((I++1) is bounded result of the Bellman-type inequality 4 This yields:
(IT++ 1) = :*) s [[V(+))] + y + ((.ik) E[((,,, un) V4- = -
where continuity and dimension-related constants again hidden. By combining the two inequalities we arrive at
([v(+++) < ((( * +1)+1)+++++
- uz)] O Pr(d, *;")o²). (6)
From Prop. 3.1
we know that Pr(is # i*) decays rate 1/k². This means that, roughly speaking, the inequality (6) gives rise to a telescoping sum (see Lemma C.4 for details), which yields
N
N E| ux)] - N & O
1 th + Pr(i + 1")o)))
A=1
The fact that Pr(is # it) is summable, due to the decay rate 1/k2, and that the sum over o² evaluates to (In(NN) + (m)) establishes the desired result up to constants (these are computed in App. C.2
The proof of Thm. 3.2 relies on using V as Lyapunov function. Provided that the stage cost (ar, u) bounded below by a quadratic the type |x| we can modify the analysis in straightforward ways to obtain explicit bounds E[V(xx) and hence on [[]æx/?], uniform over k, which is important concern the adaptive control community. Moreover, these bounds require persistence of excitation only over finite number of steps, since Pr(ie * r*) is monotonically decreasing when Ass. is not satisfied. The details are presented in App. C.4
3.2 INFINITE CARDINALITY
The ideas described in the previous section translate to the situation in which the set candidate models F is bounded subset of a normed vector space with norm || 1|. For example, F could represent the set of bounded, L-Lipschitz continuous functions that map from Rd Rdd - R with || the supremum norm. Alternativly. F could be bounded subset of the set of square integrable functions. Our purpose is to provide an upper bound on the sample complexity of online reinforcement learning in this very general setting and see the next subsection for a computationally tractable variant. As such, the results herein center on learnability guarantees rather than direct deployment of online reinforcement learning for continuum of models.
characterize computational complexity;
The key insight is that s2 can be reduced to s1 by constructing an e-packing Ft of the set F in online way, by greedily adding functions f F as long as || fll for all f Fj.

---

Published as a conference paper at ICLR 2026
As result F covers F by construction, i.e., for every f F there exists f E F such that |1 - f'l <. The cardinality of F3 is bounded by the packing number of F, which is denoted by mnc). The construction needs to be done online in order to include the minimizer argmin S& (f) in FG where sf( denotes the prediction error as before. accumulated over k - 1 steps (see (I). This means that the arguments used in deriving Prop. 3.I apply in the same way and implies that Pr(ix @ ) M2/(k- M)² before, where T denotes the set of models f FE that satisfy || f S e. As result, the same arguments in the proof of Thm. 3.2 apply, which yields the statement of Thm. 2.2 The details of the corresponding algorithm (i.e., Alg. 2 and analysis are presented in App.
3.3 PARAMETRIC MODELS
The following section discusses the situation where the set of candidate models F is parametrized by a parameter E Ω2 C IRP, where 12 is contained in a p-dimensional unit ball, that is,
F [fa Hd x Fd R |0 ?2).
The canonical example we have in mind is when So is parametrized with a large neural network, transformer, or state-space architecture, where 0 represents the parameters. As in the previous section, we assume that f E F, and without loss of generality, we set f Se=o. i.e., the parameters are centered around f.
Alg. has particularly straightforward interpretation, which also facilitates its implementation in practice. each iteration, fa, is sampled from the posterior distribution over models fe. scaled by 7) In the special case where (2x, u) = Φxx; u) 0 we note that the density corresponding to the random variable 02 is Gaussian, with mean and covariance
Zj+1 622, 00
1
6(z,, 2,),,, 24)
argmin PER
1 u,)
2nj
1+ (Tj, 1,)12/022
The Gaussian mean and covariance can be efficiently evaluated by running a recursive least squares algorithm, resulting in a per-iteration computational complexity of only Opp²). The corresponding computation of the policy μ4 for the model fe is more challenging, but can, in principle, be done offline with dynamic programming, or in an offline simulation with proximal policy optimization, for example. A notable exception is when ((x, u) is linear, in which case the corresponding (steady-state optimal) policy (1g is linear and can computed by solving a Riccati equation in ((d) steps. fo has more general structure. the sampling can, for example, be implemented with Langevin Monte-Carlo (Vempala Wibisono, 2019 Jeon et al. 2025). The regret analysis follows the same steps as in Sec. 3.1 and is included in App.
Numerical examples that illustrate Alg. D and Alg. 3 on linear and nonlinear systems are included in App. B and highlight rapid convergence of the posterior distribution over models, well as, the implementation of the policy evaluation via model predictive control. All experiments run in a few minutes laptop. For nonlinear systems, the bottleneck of Alg. is found to be in the policy evaluation, which does not depend on the number of candidate models, rather than the posterior sampling over models (even when scaling 10,000 models).
4 CONCLUSION
This article provides policy-regret guarantees for online reinforcement learning with nonlinear dynamical systems over continuous state and action spaces. We provide suite of algorithms and prove that the resulting policy regret over N steps scales as (dd,,n(()) + (nm))mmm/))))) in setting where there is finite class of m models that are separated via the constant A and as O(vd, Ny) in setting where models parametrized over compact real-valued space of dimension p. The results require persistence of excitation, and rely on continuity assumptions on the dynamics.
The results highlight important and fruitful connections between reinforcement learning and control theory and open numerous exciting future research avenues. Technical extensions include i) develop- ing computationally tractable algorithm for setting (S2) through hierarchical coverage of model classes, ii) designing exploration strategies beyond additive Gaussian noise that guarantee persistence of excitation and iii) handling partial observability and non-additive noise in dynamics.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Yasin Abbksi-Yadkori Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Conference on Learning Theory, pp. 1-26, 2011.
Yasin Abbasi-Yadkort and Csaba Szepesvári. Bayesian optimal control of smoothly parameterized systems. In Conference Uncertainty in Artificial Intelligence, pp- 1-11, 2015.
Marc Abeille and Alessandro Lazaric. Thompson sampling for linear-quadratic control problems. In International Conference on Artificial Intelligence and Statistics, pp. 1246-1254, 2017.
Mare Abeille and Alessandro Lazaric. Efficient optimistic exploration linear-quadratic regulators via Lagrangian relaxation. In International Conference on Machine Learning, pp. 23 23-31, 2020.
Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pp. 111-119, 2019.
Brian DO Anderson and Arvin Dehghani. Challenges of adaptive control pastt, permanent and future. Annual Reviews in Control, 32(2):123-133 2008
Brian DO Anderson, Thomas $ Brinsmead, Franky De Bruyne, Joao Hespanha, Daniel Liberzon, and A Stephen Morse. Multiple model adaptive control. Part I: Finite controller coverings. 2000.
International Journal of Robust and Nonlinear Control, (0(11-12):909
Joel A E Andersson, Joris Gillis, Greg Horn, James B Rawlings, and Moritz Diehl. CasADi A software framework for nonlinear optimization and optimal control. Mathematical Programming Computation, 1 11(1) 2018
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta algorithm and applications. Theory of Computing. 866):211-144, 2012.
Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. Advances in Neural Information Processing Systems, 19, 2006.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
Peter L Bartlett and Ambuj Tewari. REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs. In Conference on Uncertainty in Artificial Intelligence, pp. 35-42, 2009.
Gerald Beer and Michael J. Hoffman. The Lipschitz metric for realevalued continuous functions. Journal of Mathematical Analysis and Applications, 406(1):229 20699223662100 2013.
Dimitri Bertsekas. Dynamic Programming and Optimal Control: Volume I. Athena Scientific, 2017. 4th edition.
Nicholas M Boffi, Stephen Tu, and Jean-Jacques E Slotine. Regret bounds for adaptive nonlinear control. In Learning for Dynamics and Control Conference, pp. 471-48813 2021.
Francesco Borrelli, Alberto Bemporad, and Manfred Morari. Predictive Control for Linear and Hybrid Systems. Cambridge University Press, 2017.
Jian Cao and Matthias Katzfuss. Scalable sampling of truncated multivariate normals using sequential nearest-neighhor approximation. arXiv preprint arXiv:2406. 000:22466.73377, pp. 1-17, 2024.
Nicolò Press, 2006.
and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University
Nicolas Chatzikiriakos and Andrea lannelli. Sample complexity bounds for linear system identifica- tion from finite set. IEEE Control Systems Letters, 8:2751-2756, 2024.
Nicolas Chatzikiriakos, Kevin Jamieson, and Andrea Iannelli. High effort, low gain: Fundamental limits of active learning for linear dynamical systems. In European Workshop on Reinforcement Learning, 2025.
11

---

Published as a conference paper at ICLR 2026
Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference Learning Theory, pp. 1114-1143, 2021.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in handful of trials using probabilistic dynamics models. Advances in Neural Processing Systems, 32, 2018.
Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only VT regret. In International Conference on Machine Learning, pp. 1300-1309, 2019.
Lorenzo Croissant, Marc Abeille, and Bruno Bouchard. Near-continuous time reinforcement learning for continuous state-action spaces, International Conference on Algorithmic Learning Theory, pp. 444 498, 2024.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 31, 2018
Kenji Doya, Kazuyuki Samejima, Ken-ichi Katagiri, and Mitsuo Kawato. Multiple model-based reinforcement learning. Neural Computation, 14(6):14471166) 2002.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization RL. In International Conference Machine Learning, pp. 2826-2836 2021.
Ying Fan and Yifei Ming. Model-based reinforcement learning for continuous control with posterior sampling. In International Conference on Machine Learning, pp. 3078-3087 2021.
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, pp- 1467-1476, 2018.
Dylan Foster and Alexander Rakhlin. Foundations of reinforcement learning and interactive decision making. arXiv preprint arXiv:2312.16733 2023.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making, arXiv preprint arXiv:2112.13487, 2021.
Dylan Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimatto coefficient. In The Thirty Sixth Annual Conference on Learning Theory, pp. 3969-4043, 2023.
Stanley Gartska and Roger J.-B. Wets. On decision rules in stochastic programming. Mathematical Programming, 7:1 1111,,44, 1974.
Paul J. Goulart, Eric C. Kerrigan, and Jan M. Maciejowski. Optimization over state feedback policies for robust control with constraints. Automatica, 42(4):523-533, 2006.
Botao Hao, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Online sparse reinforcement
learning. International Conference on Artificial Intelligence and Statistics, pp. 1-30, 2021.
Elad Hazan and Karan Singh. Introduction to online nonstochastic control. arXiv preprint arXiv:2211.09619, 2022.
Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In International Conference on Algorithmic Learning Theory, pp. 408-421, 2020.
Joao Hespanha, Daniel Liberzon, A Stephen Morse, Brian DO Anderson, Thomas S Brinsmead, and Franky Bruyne Multiple model adaptive control. Part 2: Switching. International Journal of Robust and Nonlinear Control, (155):479499, 2001.
Bin Hu, Kaiqing Zhang, Na Li, Mehran Mesbahi, Maryam Fazel, and Tamer Bayar. Toward theoretical foundation of policy optimization for learning control policies. Annual Review of Control, Robotics, and Autonomous Systems, 6()58123- 2023.
12

---

Published as a conference paper at ICLR 2026
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51):1563-1600 2010.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. Advances in Neural Information Processing Systems, 33, 2019.
David Janz, Jiri Hron, Przemystaw Mazur, Katja Hofmann, José Miguel Hernández-Lotee and Sebastian T'chiatschek. Successor uncertainties: exploration and uncertainty in temporal difference learning. Advances Neural Information Processing Systems, 32, 2019.
Kijung Jeon, Michael Muchlebach, and Molei Tao. Fast non-log-concave sampling under nonconvex equality and inequality constraints with landing. Advances in Neural Information Processing Systems, 38, 2025.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low Bellman rank are PAC-leamable. In International Conference on Machine Learning, pp. 1704-1713, 2017.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman Eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Advances neural information processing systems, 34:13406-1333 13418. 2021.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation, Mathematics of Operations Research, 48(3):1496 1496 1521, 2023.
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Information theoretic regret bounds for online nonlinear control. Advances in Neural Information Processing Systems, 33, 2020.
Aren Karapetyan, Efe Balta, Andrea lannelli, and John Lygeros. Closed-loop finite-time analysis of suboptimal online control. arXiv preprint arXiv:2312.05607, 2023.
Taylan Kargin, Sahin Lale, Kamyar Azizzadenesheli, Animashree Anandkumar, and Babak Hassibi. Thompson sampling achieves Ö(VT) regret in linear quadratic control. In Conference Learning Theory, pp. 3235-3284, 2022.
Hassan K. Khalil. Nonlinear Systems. Prentice Hall, third edition, 2002.
Jihun Kim and Javad Lavaei. Online bandit nonlinear control with dynamic batch length and adaptive learning rate. arXiv preprint arXIv:2410.03230, 2024.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithuss Cambridge University Press, 2020.
Nevena Lazic, Dong Yin, Mehrdad Farajtabar, Nir Levine, Dilan Görür, Chris Harris, and Dale Schuurmans. A maximum-entroopy approach to off-policy evaluation in average-reward MDPs. Advances in Neural Information Processing Systems, 34, 2020.
Yingying Li, Subhro Das, and Na Li. Online optimal control with affine constraints. In AAAI Conference on Artificial Intelligence, pp. 8527-8537, 2021.
Yingying Li, James A Preiss, Na Li, Yiheng Lin, Adam Wierman, and Jeff $ Shamma. Online switching control with stability and regret guarantees. In Learning for Dynamics and Control Conference, pp. 1138-1151 1151, 2023.
Daniel Liberzon. Switching in Systems and Control, volume 190. Springer, 2003.
Yiheng Lin, James A Preiss, Emile Anand, Yingying Li, Yisong Yue, and Adam Wierman. On- line adaptive policy selection time-varying systems: No-regret via contractive perturbations. Advances in Neural Information Processing Systems, 36, 2024.
Fanghui Liu, Luca Viano, and Volkan Cevher. What online reinforcement learning with function approximation benefit from general coverage conditions? In International Conference on Machine Learning, pp. 1-29, 2023.
13

---

Published as a conference paper at ICLR 2026
Lennart Ljung. System Identification. Prentice Hall, second edition, 1999.
Alexander Ly, Josine Verhagen, Raoul Grasman, and Eric-Jan Wagenmakers, A tutorial on Fisher information. arXiv preprint arXiv:/705.01064, pp. 1-53, 2017.
Johan Löfberg, Approximations of closed-loop MPC. IEEE Conference on Decision and Control, pp. 1432, 2003.
Hao Ma, Melanie Zeilinger, and Michael Muehlebach. Stochastic online optimization for cyber- physical and robotic systems. arXiv preprint arXiv:2404.05318, pp. 1-46, 2024.
Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. Advances in Neural Information Processing Systems, 32, 2019.
Sean Meyn. Control Systems and Reinforcement Learning. Cambridge University Press, 2022.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. International Conference on Artificial Intelligence and Statistics, pp. 2010-2020, 2020.
Jaouad Mourtada and Stéphane Gaiffas. On the optimality of the Hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:3004-3031, 2019.
Michael Muehlebach. Adaptive decision-making with constraints and dependent losses. IPAC- PapersOnlLine, 56125557754) 2023.
Kumpati S Narendra and Jeyendran Balakrishnan. Adaptive control using multiple models. IEEE Transactions on Automatic Control, 12(2):171-187, 1997.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement
learning? In International Conference on Machine Learning, pp. 2701-2710, 2017.
Ian Oshand, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. International Conference on Machine Learning, pp. 2377-2386, 2016.
Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1 2019.
Yi Ouyang, Mukul Gagrami, Ashutosh Nayyar, and Rahul Jain. Learning unknown Markov decision processes: A Thompson sampling approach. Advances Neural Information Processing Systems, 30, 2017.
Aravind Rajeswaran, Sarvjeet Ghotra, Balaraman Ravindran, and Sergey Levine. EPOpt: Learning robust neural network policies using model ensembles. In International Conference on Learning Representations, 2017.
Alexander Rakhlin and Karthik Sridharan. Statistical Learning and Sequential Prediction. MIT Lecture Notes, 2014.
James B. Rawlings, David Q. Mayne, and Moritz M. Diehl. Model Predictive Control: Theory, Computation, and Design. Nob Hill Publishing, second edition, 2017.
Ben Recht. A tour of reinforcement learning: The view from continuous control. Annual Review of Control, Robotics, and Autonomous Systems, 2:253-279, 2019.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on Thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
14

---

Published as a conference paper at ICLR 2026
M.G. Safonov and Tung-Ching Tsao. The unfalsified control concept and learning. IEEE Transactions on Automatic Control, 42(())843 847, 1997.
Remo Sasso, Michelangelo Conserva, and Paulo Rauber. Posterior sampling for deep reinforcement learning. In International Conference Machine Learning, pp. 30042-30061, 2023.
Max Simchowitz and Dylan Foster. Naive exploration is optimal for online LQR. In International Conference on Machine Learning, pp. 3937-8948 2020.
Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pp. 3320-3436, 2020.
Slotine and W. Li. Applied Nonlinear Control. Prentice Hall, 1991.
Georgios Theocharous, Zheng Wen, Yasin Abbasi Yadkori, and Nikos Vlassis. Scalar posterior sampling with applications. Advances in Neural Information Processing Systems, 31, 2018.
Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George Pappas. Statistical learning theory for control: A sample perspective. IEEE Control Systems Magazine, 43(6))67-97,, 2023.
Tim van Erven, Peter D. Grünwald, Nishant A. Mchta, Mark D. Reid, and Robert C. Williamson. Fast rates statistical and online learning, Journal of Machine Learning Research, 16: 1793-1818,,, 2015.
Santosh Vempala and Andre Wibisono. Rapid convergence the unadjusted Langevin algorithm: Isoperimetry suffices. In Advances in Neural Information Processing Systems, 2019.
Andreas Wächter and Lorenz T Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106:25-57, 2006.
Martin J. Wainwright. High-Dimensionu Statistics. Cambridge University Press, 2019.
Jan C Willems.
Dissipative dynamical systems. European Journal of Control, 13(2-3):134-151,
2007.
Wanqiao Xu, Shi Dong, and Benjamin Van Roy. Posterior sampling for continuing environments. Reinforcement Learning Journal, 5(1):2107-2122, 2024.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pp. 10746-10756, 2020.
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal, Cautiously optimistic policy optimization and exploration with linear function approximation. In Conference on Learning Theory, pp. 1-53, 2021.
Peng Zhao, Yu-Hu Yan, Yu-Xiang Wang, and Zui-Hua Zhou. Non-stationary online learning with memory and non-stochastic control. Journal of Machine Learning Research, 24(1):9831-990) 2023.
15

---

Published as a conference paper at ICLR 2026
A
RELATED WORK
This article revolves around online reinforcement learning with multiple nonlinear candidate models. We adopt viewpoint the intersection of online decision-make reinforcement learning, and adaptive control. We review representative works along major distinct algorithmic ideas as follows.
Posterior sampling reinforcement learning has been introduced by Osband et al. (2013); : Osband & Van Roy [2sla)]Osbaadd Osband et al. (2016); Osband & Van Roy (2017). where sample complexity of online reinforcement learning is typically quantified via the eluder dimension. These works focus on episodic reinforcement learning and draw analogies to stochastic multi-armed bandits and Thompson sampling (Russo et al., 2018). The relation to Thompson sampling enables algorithms that are effective in practice and, compared to optimistic approaches discussed below, avoid the computation of confidence regions, which can be nontrivial. These initial works focus on episodic and finite-state- action settings. The resulting policy-regret guarantees Bayesian (so-called Bayesian regret), i.e., the regret bounds do not hold for any potential environment in the set of candidates, but only in expectation, when environments are sampled according to the prior. Our work establishes frequentist policy-regret guarantees by introducing additional exploration. One line of follow-up works by Abbasi-Yadkori & Szepesvári (0155); Abeille & Lazaric (007);; Kargin al. (2022) deals with continuous states and actions by exploiting linear parameterizations of dynamics and/or controllers. Another line of works by Fan & Ming (202T); [Sasso et al. (2023) leverages approximations of dynamics, rewards, or value functions to navigate through continuous state-action spaces. Model-free variants of posterior-sampliing maintain a distribution of value functions (instead of dynamics), albeit entailing challenges in explicit representations and accurate updates of such value functions. The online non-episodic scenario, most relevant to work, is addressed in Abbasi- Yadkori & Szepesvári (2015); Theocharous et al. (018);; Xu et al.] (2024). Along this line. Xu et al. (2024) augment existing posterior sampling reinforcement learning with environment resampling at random Bernoulli trials. This addition generalizes the theory to high-dimensional weakly communicating Markov decision processes and continuous state-action spaces via function approximation in non-episodic settings.
reinforcement learning (Osband al. 2016 [019 Janz et al.) 2019)
Our algorithmic paradigm falls into the category of posterior sampling reinforcement learning. Different from existing works, we bridge insights from statistics (Hedge updates) and control (dissipativity and Lyapunov analysis) to handle dependent states, actions, and losses in online non-episodic reinforcement learning with continuous states and actions. This bridge enables us to explicitly establish frequentist policy regret guarantees, closed-loop stability, and bounded losses in the presence of complex coupling arising from non-stationary and nonlinear dynamics. Our policy- regret guarantees are subject to persistence of exciiation/deenifaabllty assumption as introduced in the system identification and statistics literature (Ljung] 1999 Ch. 8.2); (Slotine & Li] 1991). which are weaker than the mixing assumptions from Xu et al. (024) that, e.g., do not apply to dynamics close to the stability boundary.
Optimism in the face of uncertainty is well-known paradigm from the multi-armed bandit literature that inherently trades off exploration with exploitation. The paradigm has been applied to online reinforcement learning in the tabular setting by Auer & Ortnerr (0066); Bartlett & Tewani (2009) Jaksch et al. (2010), and later extended to more general Markov decision processes by Yabasi-Yadkori
Abbasi- Yadkori & Szepesvári (201T); Cohen et al. 2019:: & Lazaric (020); Croissant et al. (2024): Kakade et al. (020);; Zanette et al. (2021) y Yang & Wang (2020); : Jin et al. (202)). Later approaches hinge on iteratively refining parametric models with confidence bounds and applying policies associated with the most optimistic model. The resulting frequentist regret bounds typically enjoy a square-root dependence on the time horizon (except for Zanette al. (202I)) and introduce different complexity measures that capture the function class at hand. The work by Yang & Wang (2020) Jiin al. (2023) focuses on an episodic setting with linear Markov decision processes. The bound in Kakade et al. (2020) depends on the dimension of a feature representation and is vacuous process noise is absent, Croissant et al. (2024) relies on a combination of eluder dimension and covering numbers, Cohen et al. (2019), Abeille & Lazaric (2020) focus on the linear-quadratic regulator. More generally, the challenges of the optimism in the face of uncertainty paradigm lie in i) computing confidence sets and ii) optimizing over optimistic policies on the basis of these confidence sets. The suggested complexity measures, such as the eluder dimension (Foster& & Rakhlin 2023) and variants thereof, tend to be difficult to evaluate and to assert boundedness.
16

---

Published as a conference paper at ICLR 2026
Our algorithms do not introduce optimism in the face of uncertainty, thereby avoiding the computation of confidence intervals and optimisitic policies (in Alg. [ polliiiss can even be computed offline). However, exploration must be incorporated and analyzed explicitly. and we rely on the notion of persistence of excitation to do so. Persistence of excitation has a rich history in system identification, statisties, and adaptive control (L.ungg 1999 (Slotine& & L. 199T), and is tailored to continuous state- action systems, unlike eluder dimension, Bellman-rank, etc., which are rooted in (linear) Markov decision processes and dynamic programming. We further use packing numbers, which standard and well-established, as a complexity measure for our function class. The overall policy-regme guarantees share a similar square root dependence on N with of-thetf- algorithms based on the principle of optimism, but feature a complexity measure suitable for continuous state-action systems.
The separation principle describes the algorithmic idea of separating identification and optimal control. This approach has turned out to be very effective for linear quadratic regulators (see, e.g.. Dean et al. 2018 Mania et al., 2019] Simchowitz & Foster, 2020). The earlier work by [Daan et al. (2018) incorporated model-uncertainty via robust control synthesis; however it was later found (Mania et al. 2019; Simchowitz Foster 2020) that the robust control synthesis can be replaced by solving the standard linear quadratic regulator problem, thereby simplifying control synthesis. The works by Mania et al.] (2019); (Smcchowizz & Foster (2020) offer improved policy-regret guarantees
and lower bounds (Simchowitz & Foster] 2020)).
This work shares the idea of -euiiitt--euvvllennee with Mania et al. (001)): Simchowitz & Foster (2020), but with the key difference that model candidates are sampled from a posterior over models rather than the maximum a-posteriori. The posterior sampling enables a Hedge-type analysis that facilitates generalization beyond linear systems, whereas the works mentioned rely on perturbation bounds to discrete Riccati equations, which are tailored to linear time-invariant systems. We further recover a O(vd,Np)) policy-regred guarantee for linear systems matching Simchowitz & Foster (2020).
Multi-model adaptive control emphasizes the versatility of system to handle diverse operating
conditions by switching among multiple candidate models and associated controllers (Narendra & Balakrishnan 1997, Anderson et al., 22000] |Hespanha et al., 2001] Muehlebachi 2023], Chatzikiriakos
& Iannelli 2024). There is a supervisory policy that tracks the performance of the running controller and, if necessary, applies another more appropriate one based on a switching logic. Oftentimes the switching criterion follows the model (and the corresponding controller) with the smallest estimation error integral (Liberzon) 2003) Anderson & Debghani (0088) or implements performance- based falsification (Safonov & Tssoo 1997). These works mainly focus on asymptotic stabilization, whereas this article explores online reinforcement learning characterized by nonasymptotic policy-regret.
Online control with switching policies is closely related to adaptive control with multiple models. Nonetheless, instead of tackling asymptotic stabilization, online control addresses optimal control from a modern finite-sample perspective. Specifically, [L et al. (2023); Kim & Lavaei (2024) consider regulating a nonlinear dynamical system by iteratively selecting a control input from a finite set of candidate control policies. The key principles are to use the system trajectory driven by the chosen controller as a performance criterion to remove non non-stabilizing controllers and identify the best stabilizing controller in hindsight via Exp3 (Auer et al., 2002), a classical multi-armer bandit algorithm. The regret bounds therein scale sublinearly with the time horizon, but grow exponentially with the number of non-stabilizing controllers. In contrast, in the setting with finite candidate models, our algorithm attains favorable logarithmic regret in terms of both the time horizon and the number of models. Furthermore, we extend the design and analysis to handle a continuum of nonlinear candidate models contained in a bounded subset of a normed space. Our multi-model perspective is also connected to the line of works by Doya et al. (2002); Rajeswaran et al. (2017); Modi et al.; (2020) that use dynamic convex combinations of ensemble of models to synthesize policies. In contrast, we tackle a challenging non-episodic scenario without state reset and handle more general model classes including parametric families and families with infinite cardinality.
Online optimization for continuous control is based on online performance optimization over an appropriate policy class. A frequent policy class is given by disturbance-action policies (Agarwal 2019 Hazan et al. 2020 Simchowitz et al. 2020 Li et al. 2021 Chen & Hazan 2021 Zhao
et al.
al. 2023), which are motivated by the design of robust controllers for linear systems (Gartska
& Wets| 1974; Löfberg (0033 Goulart et al. (006). These works are restricted to linear systems, although growing attention currently paid to online nonlinear control, where additional structure,
17

---

Published as a conference paper at ICLR 2026
incremental input-to-state stability (Karapetyan et al. 2023) is introduced. Another approach is to parametrize policies, e.g., via linear functions and to apply zeroth-order or first-order optimization techniques (see, e.g., Fazel et al. 2018 Ma et al. 2024 Hu et al. 2023). We refer the readers to Hazan & Singh (2022); Tsiamis et al. (023) for comprehensive reviews. Compared to the algorithms and analysis presented herein, the benchmarks in these works are typically different, and focus, for example, on the set of linear disturbance feedback policies or various policy parametrizations that are optimized subject to a fixed system model. The system dynamics are a-priori known to the decision- makerr. Hence, no tradeoff between exploration and exploitation is needed and the methods are more closely related to online or stochastic optimization, rather than reinforcement learning.
e.g., matched uncertainty (Boffi et al. 2021 )) contractive perturbation (Lin et et 2024
In summary, all the aforementioned works provide a comprehensive ground for online decision- making. Nonetheless, achieving sublinear policy regret in an online non-episodic regime encom- passing a broad class of nonlinear dynamies remains a critical challenge. In this article, we adopt a multi-model perspective and provide a suite of algorithms that identify the best candidate model and apply a certainty-equivalent policy, all equipped with nonasymptotic frequentist policy-regret guaran- tees. More precisely, for linear quadratic regulator problems we recover (V) regret bounds derived in earlier works (e.g., (Simchowitz & Foster ), but our analysis generalizes to nonlinear dynamics and smooth non-quadratic stage costs. In the nonlinear setting, prior work has established similar O (VNN results, however, under different assumptions, such parametrization via kernels (Kakade et al. 2020). dynamics linear in the parameters (Boffi et al., (021), or contraction (Lin et al. 2024). Other works, such as et et al. (2023) achieve policy regret of O (m 173 N2/3)+
in finite model setting (IM) is the number of potentially destabilizing candidate controllers), which is much worse than our result O (In( [N) + In(m)). While aligned with posterior sampling reinforcement learning (Osband et al. 2013), we tackle online non-episodic setting with dependent continuous states, actions, and losses. We further establish frequentist policy-regret guarantees, closed-loop stability, and bounded losses. Compared optimistic methods (Abeille & Lazaric 2020 Croissant al. 2024) that achieve OvvN) regret and a square-root dependence on the eluder dimension, our assumptions are explicit and encompass large set of nonlinear systems. Further, we characterize the scaling of policy regret with respect to complexity measures of the model class in the finite, nonparametric, and parametric regimes. Our approach avoids the computation of optimistic policies or confidence regions and can therefore be directly integrated in nonlinear model predictive control techniques (Rawlings et al. 2017;; Borrelli et al. (017). We envision that fruitful advances in these directions will further consolidate our multi-mode perspective on online decision- makinn...
B NUMERICAL EXAMPLE
We present results of two numerical simulations illustrate our algorithms. The first simulation consists of linear time-invariant dynamics, and implements Alg. and Alg- whereas the second simulation based on the swing-up of nonlinear pendulum-on-a- The first simulation focuses on the realizable setting, that is, the true dynamics are within the set of models, whereas in the second simulation the true dynamics are contained in the set of candidate models. In all experiments the algorithms show rapid convergence to near-optimal steady state, while having a small computational footprint.
system and implements Alg,
B. LINEAR TIME-INVARIANY DYNAMICS
We consider first a linear time- invariant dynamical system of dimension dg 20 and d, = 5 and apply the two algorithms Alg. and Alg. Ig. The stage cost is ((x, u) = |x| - |u|2 The dynamics I (unknown to the decision-maker) consist of five four-dimensional leaky integrators of the type _ = 0.8 & + 2 ++1 i 1..... 3. The dynamics are relatively challenging for control, as there is a lag of five steps until change in the input affects #t. The above dynamics are compactly written as f(x, u) Ax Bu, where x E IR is the state, u E IRdu is the input, A = Is @ Ao, B = I5 6 Bo are system matrices, Iú is an identity matrix of size 5, & denotes the Kronecker product, and
0..8
0
0
0
0
0.8
1
0
0
Ao =
0
0.8
1
Bo
0
0
0
0
0.8]
1
18

---

Published as a conference paper at ICLR 2026
It is assumed that the elements of the matrices A and B that define the dynamics unknown with respect to an absolute error of 0.1 and relative error of 20%, which gives rise to a large set of possible models including some open-loop unstable ones. For instance, the jk-th element ajk of A, is known to be in the range [0.8ayk - 0.1, 1.2azk + 0.1].
B.I.1 SETTING S1
Set-up: We generate m candidate models (r,,, u) A'x B'u random, whereby each element of A', 3* is randomly drawn from the known parameter range, e.g., the jk-th element djs of A' is sampled from the uniform distribution over [0.8ayk 0.1, 1.2ayk + 0.1]. The feedback policy p² related to candidate model f is
(x) K' where K (T B B P PiA',
and P E Rd2xdx is a positive definite matrix satisfying the discrete-time algebraic Riccati equation involving A' and 13 Bertsekas (2017). The policies 2² are computed through the built-in diqr command in MATLAB and the settings of Alg were chosen as specified in Thm. 3.2 that is
2
2
In(2m) [4/M]}>>
7 10,
ouk
M =
nM
[A/M]
Assumptions Thm. 3.2
Ass. 13 are clearly satisfied:
The cost-to-go function V is given by V(x) Ux, where P satisfies the discrete- time algebraic Riccati equation involving A and B. Hence, Ass. Dis satisfied with y = tr(P)o² Lu (P), where denotes the maximum singular value of matrix.
Ass. is satisfied with Sy = 0, Lv = g(P), where is the minimum singular value of
matrix.
Ass.
is satisfied (for any M > 0) with
Ge
min 13'
Bl
ie ml
for example, as can be seen from (14 Larger values of e can achieved when choosing M larger and factoring in the controllability Gramian W
Please note that the constants Ge Sv, Lv. only appear in the resulting policy-regret bounds and are needed for running Alg.
Computational complexity: All experiments run Laptop (Intel Core i7 processor with 2.30GHz: 32 GB of random access memory) and are executed in few minutes even when increasing the number of candidate model up to 10,000. The offline computation of the policies j² has cost ( de),,, the online computation Alg. O(dym d,dx).
B.1.2 SETTING S2
Set-up:
The parameter space Ω RRP with p de dgd, 500 covers the entire parameter range
Ω [(Ā, B) E TRP āak [0.8a,k - 0.1, 1.2n,k + 0.1), bys E [0.8b 0.1, 1.2bg + 0.1]},
where we slightly abuse notation to avoid distinguishing between different ways of stacking vectors and matrices (we will frequently do in the following the stacking is clear from context). For given set of matrices (A, B) E Ω the corresponding feedback controller ((x) = - - is given as in setting S1 and requires solving the discrete-tie time algebraic Riccati equation involving A, B. As before. the feedback policies are computed through the built-in dlqr command in MATLAB and the settings Alg. are chosen as specified in Thm. F.I that is,
2
2
1 = 10, E Vp/N,
2
+ Tk/M/²
M 5.
M
[A/M]
The posterior distribution over models in Alg. Bis updated by recursive least squares algorithm and we set b + co. The recursive implementation has the advantage that reasonable estimates A and B are already provided in the first p steps, which is important for the initial transient behavior.
19

---

Published as a conference paper at ICLR 2026
Assumptions of Thm. E.1
Ass.
Ass. and Ass. are satisfied:
The cost-to-go function is given by V(x) x: Px. where P satisfies the discrete-time algebraic Riccati equation involving and One can easily show that Ass. [ satisfied by applying Prop. (As pointed out in (Simchowitz & Foster [020] Prop. 6), for example, the policies μi are continuously dependent on the system parameters = (A, B).)
Ass. 7 is satisfied with Cv = 0, Ly = c(P).
Ass. 6 is satisfied in view of (14) in Sec. provided that M 5, which ensures that the controllability Gramian W is full rank for any feedback gain K. (The dynamics A, B give rise to decoupled four-dimensional leaky integrators, hence the Gramian Wi defined in
Sec. is guaranteed to be full rank.)
Sampling the parameter O₂ in Alg. amounts sampling from truncated Gaussian, where the mean and covariance of the Gaussian are computed via the recursive least squares algorithm. The computation of mean and covariance elementary operations at each iteration k. We then sample 9₂ by applying rejection sampling (although much more efficient approaches could be applied). The policy po, is then computed by solving the corresponding discrete-time algebraic Riccati equation, which requires at most Od + de clementary operations.
Computational complexity:
be done in at most Odd 1 d
B.1.3 RESULTS
Simulation results for the setting 51 are shown in Fig. whereas the results for setting $2 are shown in Fig-2] A rapid convergence to near-optimal steady-state behavior can be observed in both cases. note that the space parameters Alg. 3 uncountable compared to Alg. aand therefore Alg, takes about twice long converge. Alg. Alg.[acchier acchieess optimal steady-state performance very quickly (in about twenty steps). We therefore believe that Alg. I provides an algorithmic paradigm that is applicable many emerging real-world machine learning and engineering challenges, including the control of intelligent transportation systems or automated supply chains.
To showcase the scalability of our algorithms, we provide comparison results when the number of models m in Alg. [ is increased from 10 to 10, 0000000 We perform 40 independent realizations of Alg. for each value of and show the corresponding policy regret in Fig. 3a (averaged over the 40 realizations). Once again we observe a fast initial transient phase after which the policy regret stabilizes and near-optimal steady-state performance is achieved. Fig. [3b] shows the corresponding evolution of the two-norm of the state trajectory on single realization. The plots highlight that Alg. scales favorably in the number of models.
B.2 SWING-UP OF A NONLINEAR PENDUJ.M-OON-A-CAN
We showcase that our algorithms work seamlessly with nonlinear systems. Set-up:
We consider the following nonlinear continuous-time pendulum-on-a-com system dynamics:
a(t)
(g (t)) d2))(t) cos(((()) + 1,t(()) sin((((t)))(
F(t) m
+ sin()p(t))
mp
(()) (t)( a(t)
mc+m;
(g (y)()) - d2(p(t)) (p5(()) sin so(t) cos sp())
m.
my
1p( me + sin({p(t))))
a(() = max(min(u(()) F -max) d(r))
where r(t) denotes the position of the cart on the rail and (t()) the pendulum angle (p = 0 corresponds to the upright equilibrium), and parameters m. mp. 4p- g, dj, d2, and Fmax corresponding to cart mass, pendulum mass, pendulum length, gravitational constant, cart damping, pendulum damping, and force limit, respectively. The rail has a finite length of Im, that r(t) E [-0.5, 0.5), which is incorporated by modifying the above dynamics accordingly for r(t) E (-0.5, 0.5). The continuous- time dynamics are discretized with the classical Runge- Kutta method with step size 0.02. The nominal parameter values, that correspond to actual pendulum-on-a-cam system are given m 1.73kg.
20

---

Published as a conference paper at ICLR 2026
0.4
30
Ale
op
0.3
|
0.2
10
0.1
20
40
60
80
100
20
80
100
k
(a) parameter
(b) two-norm of state trajectory
Figure 1: The first panel shows the evolution of the parameter error of Alg. while the second panel shows the evolution of the two-norm of the states. The green line indicates the performance of the optimal (steady-state) policy on a different realization of ng. We note that near-optimal steady state performance reached in about 25 steps.
mp = 0.175kg. lp 0.28m, Faax 15N. d1 d2 = 0. and g 9.81m/s² We generate m 500 candidate models by randomly sampling the parameters me: mp. 4p within +00 of their nominal values and d1, d2 uniformly the range 0,, 1] and [0, 0.1] respectively. We further emphasize that the true dynamics with nominal parameter values are not contained in the set of candidate models. The stage cost is - (t)( + 0.01u(t)² + 0t1r(t)², and process noise is incorporated by perturbing the input with sequence of independent Gaussian random variables sampled at 0.02s.
The feedback policies arise from a model-predictive controller. More precisely, the policy μe is computed by solving numerical optimal control problem that minimizes the stage cost over a horizon of 50 steps with a Runge-Kutte discretization the dynamics corresponding to model i with step size 0.04. The numerical optimal control problem includes state constraints due to the finite rail length and input constraints, and is solved with IPOPT (Wächter & Biegler 2006) interfaced through CasADi (Andersson et al. 2018).
Control design:
Learning parameters: The settings of Alg 1 are chosen as specified in Thm. 3.2 that is,
10
2
In(2m)
10, ouk =
+
[
M= =
nM
[K/M]
Computational complexity: All experiments run on Laptop (Intel Core i7 processor with 2.30GHz; 32GB of random access memory) and are executed in less than two minutes. The algorithms are implemented in MATLAB and have not been optimized. The bottleneck in the execution is the numerical solution of the optimal control problem at every iteration, which is independent of the number of candidate models.
B.2.1 RESULTS
Simulation results for the setting 51 are shown in Fig. Fig. and highlight that the pendulum is seamlessly brought to upright position while taking input and state constraints into account. Compared the ground-truth swing-up. based on the true dynamics, the swing-up takes about 40 steps more (se 0.8s), due to the model identification. Even though the true dynamics are not included in the set of candidate models, the codellestimattion converges in about 100 steps. The fact that there are multiple models that approximate the underlying dynamics well (see Fig. 5b) does not pose any issues, and the pendulum can be easily balanced in upright position. Moreover, the online learning converges quickly (100 steps), despite the fact that there is large variability in the set of candidate models (m = 500). At every iteration only a single feedback policy needs to be evaluated, which amounts to solving numerical optimal control problem with input and state constraints. No difficulties were observed in the optimization and a single iteration of Alg. Alg. (including policy evaluation) carried optimized for speed.
out in about 60ms, even though the implementation
21

---

Published as a conference paper at ICLR 2026
Als $
10a
Ale
upe
10a
10
10
20
40
60
80
100
0
20
40
60
80
100
k
(a) parameter emrrr
(b) two-norm of state trajectory
The first panel shows the evolution of the parameter error of Alg. 3 while the second panel shows the evolution of the two-norm of the states. The green line indicates the performance of the optimal (steady-state) policy on different realization of ng. Compared Fig. [bb the overshoot is larger and the convergence to cparmoptimal performance requires about 60 iterations.
Figure 2:
60
10.
10
m. 100
8,000
10.
1000
10, 000
opt
policy regret
6,000
40
1,000
70 10
2,000
m 100
m
1000
m 10, 000
20
10
60
80
100
20
40
60
80
100
k
(a) policy regret
(b) The two-norm of the state trajectory
Figure 3: The first panel shows the change in policy regret of Alg. when varying m. The second panel shows the evolution of the two-norm of the state trajectory. We note that the behavior is consistent over the different values of m (from 10 to 10, 000, which amounts to three orders of magnitude). The green line indicates the performance of the optimal (steady-state) policy the same realization of nig.
pendulum angle [rad]
10
-2
S1 opt model
-4
-10
50
100
150
200
50
100
150
200
k
k
(a) angle trajectory
(b) input trajectory
Figure 4: The first panel shows the evolution of pendulum angle when running Alg. (solid black) and the pendulum angle arising from a swing-up based on the true dynamics (red dashed). The second panel shows the evolution of input when swinging up the pendulum. Alg. performs the swing-up after around 80 iterations, whereas with the true dynamics the swing-up requires about 60 iterations.
22

---

Published as a conference paper at ICLR 2026
-10-2
estimation error [%)
1.5
Pr(ix
5
0.5
0
50
100
150
200
50
100
150
200
k
(a) pendulum length estimate
(b) posterior over models
Figure 5: The first panel shows the evolution of the pendulum length estimate when running Alg. whereas the second panel shows the evolution of posterior over models. For the sake of visualization only the len most likely modely are shown, even though in the set of candidate models. Nonetheless the pendulum length is rapidly estimated to an accuracy below 5% and the posterior over models converges after about 80 steps.
500. The true dynamics are not included
C DETAILS OF SEC. 3.1
We first state and prove two intermediate lemmas that are used in the proof of Prop. 3.1 lemmas express the fact that the larger the expected model deviation f - (accumulated over past steps), the smaller the corresponding probability of selecting model i.
The two
Lemma C.1 For any step size > it holds that
Pr(is = i) = Ele n 1ostt=+)) +1),
for all s (and in particular for st st corresponding f).
Proof We note that pi. given by
pk
55k < e -0oo---0 Σ m8
S nn -666-=4)
for all j {l....,m) m), where 5k = min.e st. In addition, it holds that Pr(is = i) E[1,,=1
3g Ug n&]] Elpt]. where 1 denotes the indicator function, which yields the desired result.
Lemma C.2 Let
1. TK+1 ( u2)l
(r 22/2
where b > O is constant. Let Fú. denote the collection of random variables Tyj, Uj i4, 11 Raj to time Then, the following bound holds for all < I min(1/(4o?) 1/(222))) and for all 1 5 q k:
Ele Ele-n(h-t S exp
7
1+ (I 12/2 Fg 2)
1 1ー
fip
where I stands for [(x,, ux) and 3 for ('( ux), and where 1 corresponds to the loss of the candidate f.
Proof We note that |a*+1 (1 22 can be expressed as
If ff + nul If p4l2 2n (f - - + n nk.
and, as result, 13 1t is given by
If fil2 + 2n (f f()
1 + (2tR, uw 12/62
23

---

Published as a conference paper at ICLR 2026
Hence, conditioned Zk, uk, the randomness in 4 -1 is solely due to n (f ff) which describes sum of dx independent Gaussian random variables, weighted by the components of f - s As result, we exploit the closed-form expression for the moment generating function of Gaussian, which yields
2n -112
fi1 1 UAA ) 1?/62
1f
Ele Ele- nit (7) pxs wn]
S exp
1+ (ark, us 12/62/62
"
Thus, for n I 1/(4o²), the following bound holds
nlf - f/p -
Ele nC 42 F S E
exp (-T+
Fo)
1 + (00k, ux)) 12/22
As result of the Lipschitz continuity of f and f", the term
// - f 0 1 ( 12/22 S 4T,2,,
bounded. When deriving the previous inequality we used the fact that I (a ux) f( uz)
If ( ux2 - (0, 0)1 + [f u²) f(0,0), 2L ux)) by Lipschitz continuity of and
We can therefore apply a "Poissonian" inequality (see, e.g., Cesa- Bianchi & Lugosi 2006 App. A).
which yields
( mx 12/622 Fo 1
|f pip2
Ele
nah ne - S exp
4T,212
for all 1 S 1/(4)²). The desired result follows from the fact that (e 22? 1)/(222))) S -n/4 for all 17 S min (1/(2))44)) 1/(2L2b2))
C.I PROOF OF PROP. 3.1
We first consider the iterations = k M + 1, for k'= 0, 1,... These are the iterations where the random variable ig updated according to the distribution pi. (conditional on 2g, ux). It will be useful introduce the variables lt, as follows:
M
Σ
M+
which corresponds to of the variables H over M steps. Let Fi denote the collection of all random variables (Ik. de, ik, Rk-1, Bakk) up to time = k K'M + 1. We condition on F and conclude from Lemma
Ele
C
M U M-, M [1
(Ele
M M - 1 Fix IMM
f=1
I
M
(e
2M El
11
1f 15-
Fu 1/M
j=1
..
Sepp
ou (
(8)
4
where we have used Hölder's inequality for the first inequality, Lemma C.2 for the second inequality, and Ass. for the third inequality. As result, by unrolling the recursion for k' -'-1, 1, k' - 2, we conclude that
MMA A
nle-nlat-ei
nlst S exp
2
((M))
*We stated the inequality assuming /00,0) ((0.))=((0..00 2 (0, 0) f(0, 0) + 8T.²²² applies in
0) = 0. In the more general situation the upper bound
24

---

Published as a conference paper at ICLR 2026
By virtue of Lemma C.1 this implies
NM A
Pr(ie i) S exp
o M(M
The bound holds in fact also for + 1, 2, until k + (M 1), since, by definition, is. 46-41
+ (1) This proves the first bound of Prop. 3.1
It remains to derive the second bound, which is done by approximating the sum over o from below. We find
MMA A
(
Σ
2
In(m)
2
dj +m(m)) 2 2ln(k') + In(m),
M(M))
for k > 1. This concludes that Pr(ia i) S 1/(mk²), due to the fact that 2 We further note that '' = (k - 1)/M by our choice of k. However, in remains unchanged for the M next iterations, and therefore
M
Pr(ie+M-1=1)
m(k 1)2
which holds for all &o 2 and + it. This implies Pr( = i) S M2/(m((k: M)) for all 2 M + 1 by a change of variables. Applying a union bound yields the second inequality of Prop. 3.1 i...
M
Pr(is *1))
Σ inpl
Pr(ie =1) 5
(k M)²
C.2
PROOF OF THM. 3.2
We will use as a Lyapunov function and have
E[((4++1) -F * ir)Pi( *1) F[V( =r]Pr(i = =1)
(9)
The first term can further simplified in view of Lemma C.3 which yields
E[V (#t++1) i + ir] (xx) + /
-El((z, uR) is + (Lv Li)duouk (10)
The second term D is bounded as a result of the Bellman-type inequality 4 for the policy μ (the policy that corresponds V). It will be convenient to rewrite the bound ④ in the following way:
E[V(S(z, u) + +n] V(x) Ei((,, u)] + <(x) + Lo
where u = (((x) + Nu, (Nu. n) are independent with n. (O0, o
(O0 o²I), and ((x) is chosen such that q(x)) S y and -E(((x, u)] + q(x)) S of The function ((x) is introduced account for the fact that the policy y might in principle also achieve running cost E[[(x, u)] 7 in the short term, since y captures only the steady-state performance. As a result, we obtain
E[V(*++1) Mi = i*] S E[(( ux)l = i*] + E[V(x)) + Tk d, o
(11)
where 7% = E[g((x))] By combining (10 and IT with (9p we arrive at E[V(4x41)]
+ 1*) 7h E((( u+]]
Lidgoou + (Lvd + & i*),
where L, := L2 + Lm. As result of Prop.
3.1 we know that Pr(is fit) S M /( M)
for & 2 M + 1. We further note that E[l( ux)] invoke Lemma and conclude
7 and m S 7 (by our choice of 7s). We now
N
N
N
(E( uc)l - 7x) s ca Lnd Σ
oh + ca (Lvd co)
Σ
Pr(ix # i*),
k=1
*This can by achieved by setting q(x) (() [(a) for 2 Fll(,, p(x) + n.)) and q(=) = 7 otherwise.
((2) +na)) ] d d T.
25

---

Published as a conference paper at ICLR 2026
where we have used the fact that ((11) and the following calculation
DC
II
(c2Pr(i * + 1) I e
Co.
k=1
due to the fact that
2
M
Pr(ie + - 2M 1+ Σ
(k M)
R=2M
foe
M
S 2M +
dk S 3M.
J2M (k M)
Moreover, we bound the sum over ouk as follows
N
N
2
+ MIn(m)
uk
Mik/M]
(M/R/M]
1=1
k=1
N
Min(m)
7
1:2
(1 + In(N - 1) + Mln(m)).
n
Combining the previous inequalities and taking advantage of the fact that y $ y yields the desired result.
C.3 SUPPORTING LEMMAS IN THE PROOF OF THM.
This section contains two lemmas that support the proof of Thm.
Lemma C.3 Let Ass. 2 be satisfied. Then, there exist two constants C22 Co such that
Iv + doo²
(z)) S <o)((x) E( +
2
for all x E Rdv, and i {1, (1....,m). m.). c2 ( + I,,)² + 2T + 2/
where the constant 02 given by
and to be expressed explicit function of maxie[m] | (0)). V(0), [VV( 1(0,0).
[V0 0)), ((0),, and Cv- The random variables and are independent and satisfy n (V(000'T) nn ~(0,
Proof We exploit smoothness of V to bound ((V(f(Z, + m.) + n)) by
Lv doo
([V([(>, (x) nn))
where we used the fact that the term linear in n vanishes in expectation. We further note that the term V(J(x, (² + nn)) can be bounded in a similar way:
Lv 2 (.)mm)
(( + m.))
where we applied the mean value theorem to rewrite f(z, H²(x)) nu) f(z, p (x)) as V Vuf(E))
for some (dependent on n,)). By applying Young's inequality and taking advantage of the fact that vnf bounded above we arrive
(f + m.))) s V(((x, + 2Lv
Lv
Due to smoothness, V is guaranteed to satisfy
[V(x)) S ca Tylal, V(x) E 62 + Tr|=
26

---

Published as a conference paper at ICLR 2026
where Co1 (VV( and the constant co2 2 is similarly related to [V((0) and V(0). As result, we obtain the following upper bound on ([V( nu))l:
((V(S(z, + mm)))l S Co2 + Ea + 22,1f(E,, (x))) Lv
Lv
The fact that f(z, p (x)) is L(1 + Lp) Lipschitz can be used to conclude that If μ² (x)) =
Co3 + (1 + ) |ol. where Co3 = ((0)), which, in turn, yields the following upper bound
ca + 2Lv + 4 I 2=12 + Ly L. IN
(IV(((,, + na))l S co2
We further note that the fact that is L, smooth and (xx, u) 2 implies ((x, u) S Cot + 2 +||l? and therefore
E[(x,, 1 (x) + m.)) S Cos + E a + [A(1 +21,,,a where Cos 2 0 is related to maxie[m) I (0)). ((), 0). and Vi(0, 0)). Combining the previous two inequalities results
C2LV |z|² 2 Ei((z, p*)) + n.)] + (LvL² L2 + Lidduo
([V + nn)))] S Co6 +
2
where Coo 2 is constant and can be expressed as a function of max [m] (0)), V()), (V)))), 2(0,0), 0), VI(O, 0), and [f(0, ((0)]] The result follows by inserting Ly | /2 - ((x) + Sv in the
previous inequality.
Lemma C.4 Let the sequence
Vk+1 S + ax) + 9
9k
V2 2 0,
be given, where 1,,,...., 0g 2 0 gh and 9 2 0 arbitrary sequences such that
Ca IT (1 ax) cc. Then, the following holds for all N 2 1
N Σ
9j S
Ca
Σ
9
+V1
1=1
Proof By unrolling the linear difference equation we obtain
N
VN+1
+ V
Σ
9
91
II (1
(1+
k=1
j=++1
N
Ca
V1 +
91
i=1
t=1
where we exploited the fact that [1 (1 + ax) < Ca <0.
C.4 FINITE SECOND MOMENT
Corollary C.5 Let Ass. 2 be satisfied, let 02 be as in Prop.
3.1 let M(r, u) 2 2// for some
constant L > O, and 1 min(1/(4Mo²), ( (22)) Let Ass. be satisfied for at least the first
:o = [M (1+ /2
steps. Then, it holds that
E[V(I+)] < max(ca, 4k 11
with
C3 = + + LLvL² L2 Li)d
2Lv
(C+ (1+ + + 02 + co).
C4 L
27

---

Published as a conference paper at ICLR 2026
Proof We conclude from Prop. 3.1 that Pr(ik # i*) ) is bounded by
M
I
Pr(ia # () v
(k: - M)² I 2Lve2'
(12)
for all k 2 Kg. It important note that persistence of excitation is only required hold for ko steps, as, by our choice of Pr(ix # i*) is monotonically decreasing (see proof of Prop. 3.I. By Lemma C.3 we conclude that over the first kg steps the following holds
(x++1)) & (x + Lvdgo² + co + (Lv + Li)duokk
which implies that
(((())) < c ko co (Iv T1),
for all & 2 Ko + 1, where we have exploited that uuk is monotonically decreasing.
By following the same reasoning (case distinction between is 1" and is + i²) in the proof of Thm. 3.2 we arrive at
B[[(x++1)) < (IV()))((L((L + 1) + Ell(ZR, un]] - Ludio + Lvdwo² + Cos
for all A 2 kp. where we have used inequality 12) to bound Pr(ig + i"), 7k S 7, and the fact that Ouk is decreasing. The constant Tu is given by 7. = I2 + L4 + Im- Due to the fact that is bounded below by a quadratic we conclude that (xx, u) 2 (4 /Lv for all x E RRd,, which can be used to simplify the above inequality:
([V(+++1|| < ([V((=))(( - -2/(2v)) + Ludion + Lvdxo² co.
This readily implies
[[(()))] < TI (7 + Enduooi + IIvdx02 + co),
L
for all & 2 ko, which yields the desired result.
C.5 CONVERGENCE FINITE TIME
Corollary C.6 (Finite time convergence) Let the assumptions of Prop. 3.1 be satisfied. Then, almost surely, ) converges to i in finite time, that is,
Pr( sup izfi"
< <xx)= 200=1. =
Proof We conclude from Prop. 3.1 that Pr(íx Fi) S <M2/(K M)² for all 2 M 1. This implies for any Z M +1
Pr( sup k ÿ) 5
Σ
Pr(ix +1),
k=j
where the right-hand side is bounded above by
M
M
f
M
M
+
dl S
1+
2)²
(j
My²
(k
My²
j- M
M
Hence, the right-hand side converges to zero for large j. which yields the desired result.
D DETAILS OF SEC. 3.2
The decision-makiine strategy for S2 is listed in Alg. and proceeds follows. Alg. 2 first computes minimizer argmin fer 8& (f). denoted by f", where sp (f) denotes the prediction error as before,
2 f(z,, u/)
su
feF. F.
1
28

---

Published as a conference paper at ICLR 2026
Algorithm 2 Reinforcement learning ($2)
Inputs: F, M, {olk ] 1: for 1,-.. do every Mth step
Algorithm 4 greedyCover(F, ((",,
mod(( k - 1, M) = 0 then f < Jrr sa(l)
F F+ (f*} S Uf / F*)
+ greedyCover (F,
while S S 0 do 11 pick an element from S
(f Ej=1 3441 ( f
1-
is exp( (f=(("))) F
+ F=+Fu,f), S
compute f corr. to f F el.. by d.p.
S |f > end while return F
clse
i i
Isstay with -
end if
l/follow policy and add excitation
uk n (Ix) + Buks Ruk (O, aued)
end for
In order to apply the same proof arguments as in S1, we will construct an 6-cover of F that also includes f", by running Alg. 4 Alg. greedily adding functions ft F as long as | - fll > for all f E Fx which results in the desired cover. The algorithm then randomly samples in as before and applies the feedback policy ju'k that corresponds to model füx E F Clearly, these steps (minimization over f F. constructing the packing, and solving a dynamic programming problem at every iteration) are computationally intractable in general and one would have to resort to approximations in practice.
We provide regret guarantees next, and therefore slightly modify Ass. from setting S1 follows.
Assumption There exists an integer M > 0 and a constant Ce > such that for all xn E R&,, ou > 0, and f',f" f E F,
M M
(IK: ux) (Ik: un)l?
2 c.0 82113
1+ (x 24: 12 1//62
holds, where Ix+1 = f(r, ux)+ +ug, 4y (*xx)) + nuk with n& N' 021) and un N of.), and where P is any policy corresponding to a model f E F.
The above assumption differs from Ass. in that the left-hand side involves the discrepancy between a pair of candidate models f' and f instead of that between I and the true model f. Further, the constant coefficients on the right- side also differ. The assumption is stated for finite b 0 even though it can be relaxed to b + oc, and the same policy-regret guarantees apply although with more elaborate constants, see App. F for further discussion. For b - oc the assumption describes persistence of excitation as used in system identification and statistics (see, e.g., Ljung, 1999, Ch. 8.2). From maximum likelihooo point of view, Ass. X ensures that the dynamics f correspond a unique non-degenerate minimum of the one-step prediction error, accumulated over M steps. The assumption generically satisfied if the models f E are linear and ||- denotes the Lipschitz-norm (see, e.g., Beer & Hoffman 2013). as highlighted in Sec. A similar reasoning applies to nonlinear systems, see Sec. F
We will further strengthen the Bellman-inequaliyy from Ass. to ensure that the steady-state perfor- mance y of the policy a is stable under small policy changes that arise from models f E close to f. This notion of stability requires μ to optimize the corresponding Q-function. This is made precise as follows.
Assumption 5 (Bellman-type inequality) For all small enough >> 0 there exists a cost-to-go function V (corresponding to J and μ)) satisfying the following inequality:
V(z) E[I(x, 1d (x) n.,) + ((f (x) + nw)) n)] - 7 L,d,, L,5², for all policies p² corresponding to I fll < for all x E Rd where Lus Ly are constant, (O, T)), and n. (0)
29

---

Published as a conference paper at ICLR 2026
The following proposition provides sufficient condition for Ass. 5 hold. In particular, the proposition applies to the class of linear dynamical systems with a quadratic, positive definite stage cost, where all assumptions
satisfied (see also Prop. 6 in (Simchowitz & Foster 2020).
Proposition D.1 Lel Ass. 7 and Ass. 2 be satisfied and fix E Rdxx, If, in addition,
((r,u) 2 /2, ((x) E argmin FlL u) + (f( u) n)), and l| vollop S &T/15:
holds for all policies Jt corresponding to llf - < & and all > small enough, then Ass. 5 satisfied for and all ou small enough, where L, I, are constant and ~ -N(0, ((0,o2I). The Lipschitz-norm || llop is defined for any Lipschitz-continuuu function TR - R2 as
[g(x1) 9(22)
Iaalop == max (19(0),
sup Z1
x1 x2
Proof Let cz/ denote the smoothness constant of Eli(2, u) + (Vf((x, u) + n)] in neighbor- hood of u = (((x). From smoothness and the fact that (ux) a minimizer we conclude
Ell(Z, n² + <BM (|0p://000a.H.14///00//00//////1
S V + + + (x) x(=))
(13)
where Ass. I has been used for the second step (where set 0u 0). We further note that
[n' ((x)]= = 1 (0) - p(0) + px)) p(x) - (1' - m())) S L + E|xl),
due to the fact that || - mllop s T.,55. We multiply (33) by 4c,5² /4. define V == (1
5 / /L) V, and arrive
E[M(z, (x + (f (x)) + + s V(x) (1+ 4c,5 |1) c=/2
+c dc.2 + cc + 4c, e² ( 1x12
where have used the fact that ((x, u) L // We choose ?² / (4cx) and rearrange terms. This results in El[( n² (z)) VU((
s V(x) + (27 1)g² + -1 (1)
where the last term is non-positive. We therefore conclude that the inequality in Ass. holds for V with I,, = 2c, (2,/2// + 1). T., = c (2T and small enough on-
We are now ready prove the main result of this section:
Theorem D.2 Let Ass.
Ass. and Ass. 5 be scaisfied and choose 1) and auk as
4
(
2
+ In(m(())
min Then, the policy regret of Alg. 2 is bounded by
4M 2MT22 ).
au
Mc2
[[//]] ([k/M])2
Σ Ell(,, u+)l Ny S Gid, 3ln(N) Mln(m(e))
+ L + c22
for all N 2 2M, where m(c) denotes the packing number of F for packing of size and where the constants Ce1 and 6r2 are given by
8c, ( TLy 1.2 La T.a).
Ca 302M
C22 c= = (Lvd,
G1
nc
Proof The proof follows Thm. 3.2 At every iteration & we denote by I the set of models f P
that satisfy || flll < c. We then conclude from the same reasoning as in Prop. 3.1 that
M
Pr(is $ 1+) < (k: M)
30

---

Published as a conference paper at ICLR 2026
for all & 2 M 1. We make therefore the distinction dn I and dp & Ig which then yields by the same arguments (see
N Σ (Ell(z ux]] 7h) & NI + ca dn Σ Luk + ca (Tv /2 Co) Pr(ie & 12),
N
N
where there is an additional enror term, due the fact that f and f could be different (although I|f" -fll < for any i* li. by construction 43). The desired result follows from the previous inequality. However, compared to Thm. 3.2 we used the slightly more conservative bound
uuk
(3ln(N)= + Mln(m(+))).
1=1
which applies as long as N 2 2, and simplifies the resulting constants.
E DETAILS OF SEC. 3.3
For deriving the regret bound we will slightly adapt the persistence of excitation condition Ass. from Sec. 3 The motivation is analogous to Ass. and we refer the reader App. Dadd App. Forr further discussion.
Assumption There exists an integer > and a constant č. > such that
M Σ
Lo ( u&) [(akk ux)1 2 ?00?
M
+ (2k, u4 12/62
for all 0 E Z and all vn E TRd,, where T6+1 [ar, uk) Tig us un (n(rr) ) + nuks and figy Duk are independent random variables that satisfy Dakk ~ NO, T), ni ~ ((0,021)
Intuitively, the above uniform houneeeounde property holds if the difference between candidate parametric models is of the same order the difference between their parameters (by following similar derivation as Prop. F.2).
The second assumption, which will be important, is strengthened version of the Dellman-inequalig from Ass. M The assumption ensures that the steady-state performance 7 of the policy μ is stable under small policy changes that arise from models fo E F that close to f. The sufficient condition provided by Prop. applies here in the same way (llfe fllop reduces to [@) and we therefore conclude that the assumption below is, for example, satisfied for linear dynamical systems with quadratic, positive definite stage cost.
Assumption (Bellman-type inequality) For all small enough E > there exists a cost to go function V (corresponding to f and p)) satisfying the following inequality:
V(x) z E[((,, px()) + na) + VJfa,, u0( + na) + +
Ludy - Lyc?
for all policies pg with |0] < &, for all x e Rds, where Luy L, > 0 are constant, n. ~ NO, 0²1), and n, ~ NO I)
now prove the main result characterizing policy regret for the setting S3.
Theorem E.1 Let Ass. Ass. 6 and Ass. 7 be satisfied and choose 1i and o as
n S min 2M 2ML2
1
oh
ncMe2
4
[[/M]]
2
+
([k/M])²
P
Then, for all N 2 2M there exists large enough p. such that the policy regret of Alg. is bounded by
N
El((,e, ux)] 100-NN NNy < 2 (3ln(NN) + Mp)d,N + G22
31

---

Published as a conference paper at ICLR 2026
where the constants C-1 and Cr2 given by
Sc, (c L1 Lu)
Ca Jerds
02 - 3Mc (Ivd cc),
C+1
K/cr
with
Crt (l + Mp)
2²
L2NN
Proof We first argue that the reasoning Lemma C.I applies in very similar way to setting $3. To that extent, we first define the random variable pk follows
P& JoN11010150] e (0
where d0 denotes the Lebesgue measure, and & = minges 8% (0). However, compared to the discrete setting, where the denumerator bound the denumerator from below by [Bale-wh(8), where h(6) := max ()) Eg and B3 denotes a ball of radius with volume |Bgl centered at a minimizer of (0). From the smoothness of (f)
simply bounded below by unity, the situation is more
delicate. More precisely,
conclude that h(5) O(52) for small 8. Due to normalization, Ω is contained in a ball of unit radius and we have |Bsl/[S] 2 [Bsl/[Bi] 2 d where
p refers the dimension of J2. Hence we arrive at the following lower bound
e ( ( 2 1
where the second inequality arises from carefully choosing 5 in order to balance the the term 8 and -h(6)) This yields the following bound on pt: (which resembles the discrete setting)
eP I
e -0sx(())<())88) +8)
ps S [S2] Im
sc)
where we have also replaced 8): with o due to the fact that & is minimum. Following the same reasoning as Lemma C.I and Prop. 3.1 yields therefore
Pr(1Ok] > e) S [
[s Jox o1se)
e
Ele ((s)(()) S exp
Cell
2
k-
M
ou
4
j=1
where Fubini's theorem has been used the first step to interchange expectation and integration. In addition, due to the modification of oi compared to Thm. D.2 (where now m(c) is replaced by e²), we find that
M
Pr(10. 2 (k
My²
for all k 2 M 1. We apply the same reasoning as in the proof of Thm. 3.2
where we now have
the case distinction Pr([ex] > e) and Pr([0u] e) (corresponding Pr(tz 7 and Pr(ix = i*)). This concludes that
N
Σ (E] u&)l - 7x) s Ne + ca LaLdd Σ
uk + 2/2 co)
Pr(lOs] > >c),
where, as before,
N
Pr(1Oal > 2) 3M.
We further note that the sum over Th yields
N
8
oit < ne,c²
(1 + In(N) + Mp) <
(3l((N) + Mp),
nāge²
k=1
32

---

Published as a conference paper at ICLR 2026
where N 2 2M (and therefore In(N) 1/2) has been used in the second step. Consequently the regret bounded by
N
E|((,, un)] - Ny S L2NN + cadu 3l((N) + Mp
+ Cr2-
L
R=1
The choice of achieves optimal trade-off between the first two terms, which yields the desired result.
F RELAXING PERSISTENCE OF EXCITATION
This section discusses the situation when b + xo. We first note that when f E F are linear (see also Chatzikiriakos al. 2025), that is f u) A'r + B'u, p²(x) K x, Ass. for is straightlorward to verily and we obtain, for example, the following bound for t: 2 2:
(rr, un) f( ) 2 B' B + (olg(W)))) + - ( B
(14)
where K represents the linear feedback controller corresponding to model fr E F, and W denotes the controllability Gramian (over ls steps):
k-1 W = (A+ BK*Y" BB (A+ 1=0
where a denotes the minimum singular value. Hence, we conclude that Ass. 3 is satisfied for M = 2
with A (I...mm)) |B' BBB (WW A + (B' B)
We now derive a variant of Lemma C.2 that relies on the fact that over finite time and are sub-Gaussian random variables. To this extent, we slightly modify Ass. 3 as follows:
Assumption There exists an integer M and constant A such that for any Tı E IR,, ou > 0, and f E F, f #
M
1
E
f(xx, ux)) 2 A dxo²)
M
holds, where xk+1 = f(zk, un) + ni. us = (xxx)) + nuk with ny ~ NO, 021), nuk ~ ~N I
and g {I,...,m) m...
Lemma F.1 Let Ass. 8 be satisfied and let
1 [I F (ID,,N)))
for k = 1,....., where Zk, Ug denotes the trajectory resulting from Alg. 7 and o² is monotonically decreasing. Let 2 0 be an integer and define k k + (i.e. To is a time instance where ik switches). Then, the following bound holds for all 0 n min (1m(44MMo2) and all j = -,..., 1
....
k+M -1
Ele n EE
-E--- -0)--1(1--))00 S exp
1
Σ
(o + d2222/d)) (du))
4
j=k
where
T/o 4M + du) 128M (2L2M 2M (1 L, 2M
and fj.fz is shorthand notation for f(z,, uz) and f' Uj). respectively.
Proof Without loss of generality we set 1 and = 0 (the proof follows exactly the same steps for k' 0). We first note that the random variables xy and uy for 2 k are Lipschitz
33

---

Published as a conference paper at ICLR 2026
continuous functions of the noise variables {Mg. aug 1q=1". We define the random variable X, If(2,, m2) f((2), /2 and note that X, is sub-Gaussian with variance proxy
x² = 2L (1 + Lp)) 2M (( d, + dd
due to the fact that there are at most M steps between 21 and zj. We will simplify the notation by introducing the following variables
= M(o + ozd)). i = 2L (1 2
2M of
such that 82 = - and 128.2203% = A/(4dd.) The previous result exploits the fact that
Ly-Liscchitz function of a of p. independent standard Gaussian random variables sub-Gaussian with variance proxy Ly (see, e.g.. |Waiwwriht) 2019 Ch.2.3). By following the same argument as Prop.3..1 and Lemma. C.2
we arrive
1/M
M nM nMM
Ele (1==-
II j=1
Ele
1/M
M Ele 1
-331111
j=1
1/M5
M II Ele MMXx]
where used the shorthand notation fj f3 as in the statement of the lemma and the fact 7 S 1/(4Mo²). The random variables Xj are sub-Gaussian with variance proxy o² and therefore X² E[X}] are sub-Exponential with parameter 168?. As result, we can simplify the previous inequality to
1/M
M II
Ele 1 11 -5
since 128 < A/(4ddu) by our choice of no-- As a result of Ass. 8 we infer
M
MA + + E[X]]
j=l
and therefore
AG
A
-
E[X}]
0e
4Ld
2dh
4d
4d
J=l
This establishes
Eie n 2i
and yields the desired result.
The conclusion from the setting with linear dynamics be generalized to nonlinear systems as follows. In order to simplify the presentation we consider the situttion where the process noise is absent (a 0); the same rationale applies when o 0. The following result demonstrates that Ass. 3 is generic and holds for a broad class of nonlinear dynamics. This result also highlights close connection between controllability and the required notion of persistence of excitation.
Proposition F.2 Let E &R and E {1,...,m) be fixed. Then, there exists constant A O
such that
(x ux) f(zK, uz)l > A'
for all small enough au > 0 if either of the two inequalities are satisfied
(f nº (Tx)) [āx, nd (Tx)) 0,
a(We ((WE.) 1 AutE + |
B 0.
34

---

Published as a conference paper at ICLR 2026
where ny is defined recursively via 21 j = 1, 1....,, and
2341 (x),) + nuj) with muy (.)
A = 0
(())))()))
1
(z. p²
dr
dr
1=
x=
BB = 0
fx u)
B = du
f(r
Ou
2=
k-1
W = Σ B, A AL-2A
Moreover, Σy corresponds to the noise-free trajectory and is defined via T1 24,1 ((0),
Proof We start by considering the situation where ( (f (āx)) # f (3x)). We note that Ell (1x, (x()) + mukk) (Ix: 1 (Ik) nunkk |
continuously depends on du and converges to ( μr (ix)) - fã p (++))) 0 as + 0. Hence the desired inequality is clearly satisfied for all small enough on >
Next we consider the situation where fT na (Tx)) = f( (Tx)) and apply Taylor's theorem as follows:
fi 4 (xx) muk)) f( H (Bx)) (x rx) Ba o Tk; Ruk),
where o is a continuous function that satisfies (E)//EE + 0 for |4| - O. We therefore conclude
If (xx, u f(z,, ux)l = (A Ax)(x= - Tx) + (B} B + o(Tx
Tk. mukk)
where we slightly abused notation to redefine the reminder term (we will frequently do so throughout the remainder of the proof). We further apply Taylor's theorem express I& Σg
A 1441Bynu + olnut. Buk-1)
By combining the previous two equations, squaring, and taking expectations, we arrive at
FIlJ ux) [Ix, 2² (A As ( |B] BzI o(o
where we took advantage of the fact that nul...., are mutually independent. We further used the following reasoning: i) independence between nuy and nuj- + j. concludes
Blo(muu))an
LE rail] = 0.
ii) for = we have
E[o[[nuel [)]
o(gg)) / Rdu (V2mo,,)
1
16 16/ <
o(EE))
2
ql
dg
o
d
KE
Rdu
2m
for any integer q 2 0 large enough, where we have bounded the exponential using - < g!/5" for all & 2 0. This implies that E[o(nn, nu. [3)] o(af) (in fact E[o( mn.il [3]] decays much faster for small o.), which leads to the desired result.
G DISCUSSION OF REALIZABILITY ASSUMPTION
The realizability assumption, i.e., f E F, can relaxed in multiple ways and is an active area of research in statistical learning theory. We refer the reader to van Erven al. (2015) for detailed and thorough discussion. In the following we provide two simple conditions for relaxing the realizability condition. We begin with the Setting $1, followed by Setting 52 and s3.
35

---

Published as a conference paper at ICLR 2026
G.1 SETTING S1
Assumption (Setting S1) There exists a constant > 0 and candidate model f E (s" such that
(1 + 2c,))l((z u) - f(ar, w) E (f(z,, u) [(x,
for all (x, u) E R& and for all f E
The assumption implies that there is a single candidate model that is more accurate than the others over the entire state-action space by a fixed margin 2c,. The graphical intuition of the assumption is shown in Fig. 6 It is easy see that the assumption implie
(1, u) - [(x, (1, - (x, u)) 2
1+ (xr u) - f" u)l²
(15)
As consequence, the proof of Lemma C.2 remains valid with minor modifications. More precisely, we obtain
-1 -)
+ + 5'
1 1 [kk 1//22
G. | 14/ 2( S nk Ite.
1 (Ik: ub) 12/62
where the dependency of f. and f on (It, ux) has been omitted. The remaining part of the proof of Lemma C.2 in the same way with minor changes in the parameter 1). This also implies that the remaining results, i.e., Thm. and Thm. 3.2 follow in analogous manner, with benchmark given by the cumulative cost of any policy based on the above closest model f
G.2 SETTING S2 AND S3
For the Setting S2 and Setting 53 the realizability assumption can relaxed in the following way: Assumption (Setting 52 and $3) There exists candidate model f* F such that
(f" f(x u)) (f(x, u) f" u)) 2
holds for all (z, u) E Rd and for all f E.
The geometric interpretation of the assumption is shown in Fig. and the assumption is again slightly stronger than necessary (see 15 As result of the assumption the proof of Lemma applies in exactly the same way as
2( - +5+ pip2 2 -t) 1 (Ik. 12)12/88
1 1
|1 p2 + Tm. me
1+ (x 22)
where the dependency of f. f", and fr on (Ik, ux) has been omitted. Henee, the remaining results, ie.. Thm. 2.2.2.22mm and Thm. apply in exactly the same way, where the benchmark therein corresponds to the cumulative cost incurred by any policy associated with f*
'The converse is not true, the assumption is slightly stronger than strictly necessary. The condition 15 has clear geometric interpretation, which is, however, slightly involved.
36

---

Published as a conference paper at ICLR 2026
2c fr
r"
(a) Setting S1
(b) Setting S2 and
Figure 6: The figure provides graphical illustration on the two assumptions in App. G.1 and App. G.2 In the Setting S2 and S3 the set F' is assumed to connected, however, this does not need to be the case. Convexity of F' is a sufficient condition for the assumption in App. G.2
37


Reviews:
[{"review_id": "4NraiHolqT", "reviewer": "Reviewer_QBs5", "summary": "This paper addresses theoretical guarantees for non-episodic reinforcement learning in Euclidean state and action spaces with general nonlinear dynamics.\nThe true dynamics are the sum of a deterministic function and sub-Gaussian noise.\nThe learner is given a class $F$ of dynamics models and with each dynamics model $f^i \\in F$, a corresponding deterministic policy $\\mu^i$, that may or may not be optimal.\nRealizability is assumed: the true dynamics $f$ belong to $F$.\nThree types of model-class are studied:\n\n- S1: A finite set of Lipschitz functions.\n- S2: A bounded set in a normed function space.\n- S3: A parameterized family with a compact Euclidean parameter space.\n\nThese are general enough to subsume lots of prior work.\nThe performance criterion is policy regret against the $\\mu$ associated with the true $f$.\n\nAt a high level, the algorithms look like Hedge over the space of candidate models (i.e. possibly a continuum),\nwhere the \"loss sequence\" for each candidate model is given by a sum of normalized one-step squared prediction errors.\nHowever, one cannot use the standard Hedge analysis for this problem, because the prediction errors depend on the visited state sequence, which depends on the policies that have been deployed by the learner since the start.\n\nTo deal with the latter issue, the algorithm imposes its own episodes and holds the policy constant within each episode.\nThe algorithm adds white Gaussian noise to the policy's deterministic actions.\nTHe main challenge is to control the state magnitude while suboptimal policies are in use, and to ensure that the noise and episode length are exciting/exploratory enough to correctly evaluate the predictive accuracy of each candidate.\n\nThe central analysis is for the finite case S1.\nThe assumptions include:\n\n- a technical Assumption 1 about a particular variant of cost-to-go function.\n- typical Lipschitz/smoothness on the policies and stage costs.\n- the cost-to-go has a quadratic lower bound.\n- a \"gap\" lower bound on the (normalized) difference in predictions between the true $f$ and all other candidates $f_i \\in F$.\n  This bound appears to depend on both the properties of the class $F$ (no two candidates are too similar)\n  and the ability of the additive noise in the action space to sufficiently excite those differences.\n\nThe authors prove sublinear policy regret for each of the three settings, although in S2 the regret exponent gets very close to $1$ for high-dimensional states and/or actions.\nIn particular, the results from S3 recover some regret bounds from the literature for linear dynamical systems, i.e. much more restrictive cases.\n\nThe analysis shows that the algorithm identifies the correct candidate model in finite time almost surely.\nThis, in turn, is used for the regret bound.\n\nThe extension to S2 is not computationally tractable, but gives statistical results.\nIt is assumed we can identify the function $\\bar f$ that minimizes the \"Hedge loss sequence\" over the entire $F$.\nThen, we construct finite cover of $F$ around $\\bar f$; select from the cover using the Hedge-like rule; and synthesize the corresponding policy.\n\nThe extension to S3 assumes that we can somehow sample from the Hedge-like probability measure over the parameter space directly.\nThe authors claim a motivation from neural networks, where this is (to my knowledge) wishful thinking.\nHowever, they note that it is tractable for feature-space models of the form $f(x,u;\\theta) = \\phi(x, u)^\\top \\theta$ which are widely studied in RL theory.\nThe synthesis of the corresponding policy is still computationally difficult except in special cases.", "questions": "In Equation (1), must $\\gamma^i$ be finite for all $i$?\n\nThe discussion of Assumption 1 could use more intuition. The authors discuss technical details on how the $-\\gamma$ and $-d_u L_u \\sigma_u^2$ terms help adapt the Bellman-like condition to deal with the infinite-horizon average cost objective and the extra price of excitation. However, I am still left unsure about: **what kind of systems/policies have we ruled out by making this assumption**?\n\nTheorem 3.2 is very similar to Theorem 2.1, but not exactly the same. Why can't we have a proof sketch of Theorem 2.1 in this section instead?\n\nOne notable related line of work is the Decision-Estimation Coefficient [1, for example]. It also provides a highly general RL theory framework, uses the model-based RL paradigm, and focuses exclusively on the statistical aspect (not computational). Although (to my knowledge) that work is more abstract and further from practical, and it is an episodic setting, but it seems too closely related to skip. How does this work compare?\n\n[1] Dylan J. Foster, Noah Golowich, Yanjun Han. Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient. COLT 2023.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper studies non-episodic RL for a class of nonlinear dynamical systems that is more general than lots of related work.\nThis problem is clearly on the frontier of RL theory.\nThe proposed techniques use a nice mixture of online learning theory, Bayesian methods, and nonlinear control theory.\nThe paper should be of interest to researchers with both RL and control backgrounds.\n\nThe main assumptions (besides ignoring computational cost) are Assumption 1, which is related to Bellman optimality and dissipativity, and Assumption 3, which is related to exploration/persistent excitation. To be honest, it is hard for me to confidently say whether or not these assumptions are restrictive. It seems that we have somehow ruled out hard exploration problems, since we are able to get the regret bound with an exploration strategy that is naive compared to those required even for tabular MDPs in the worst case. However, since the setting is single-trajectory, it is clear that *some* kind of assumptions to limit the negative impact of disturbances and control the difficulty of exploration are necessary.\n\nThe framework mostly ignores computational issues and focuses on statistical guarantees, but this is standard in learning theory. The settings S2 and S3 (except for the special linear-in-features case) are possibly too general to admit efficient algorithms. It will be interesting to see if any follow-up work can instantiate those algorithms for other special cases.\n\nThe paper supports, along with other recent work, the overall idea that \"certainty equivalence\" is a good approach for RL. This is a positive result that simplifies our analysis of RL problems.\n\nI did not have time to check the proofs, but the overall proof structure is logical, and the techniques used seem appropriate.\n\nOverall, I think this is a strong contribution to the RL and learning-based control research communities.", "weaknesses": "In the Theorem 1 statement, it is a bit confusing to see the equation (1) suddenly called \"$\\mathcal{H}_2$ gain\", maybe it is equivalent to the classic $\\mathcal{H}_2$ gain for linear dynamics and $l(\\cdot,\\cdot)$ quadratic, but this version is still unfamiliar and RL audiences definitely won't know it. In general, the paper seems to assume a level of familiarity with classic control theory that the ICLR audience may not possess; it would improve the paper to do a bit more hand-holding.\n\nRecovering near-optimal regret bounds for linear systems is very nice, but there is a big gap of generality between the proposed work and linear systems.\nIt would be interesting to know if the framework is also capable of recovering regret bounds for more general frameworks like bilinear classes, Bellman eluder dimension, etc.\n\nDeferring detailed related work discussion to the appendix is unusual. I suggest to move more of the most closely related work on RL theory for continuous state+action spaces with nonlinear dynamics to the main body.\n\nI suggest to reallocate space in the main body -- the S2 case already has its algorithm pushed to the appendix, so one must flip back and forth while reading about the packing strategy in Section 3.2 -- I suggest to shorten the discussion of S2 in the main body and use that space to give a bit more detail/intuition on S1 and the related work in the main body.\n\nThe authors discuss the limitations candidly throughout the paper, so it was surprising to see the conclusion without any thoughts on how they might be improved in future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZTIubskmD7", "reviewer": "Reviewer_jN5Z", "summary": "This paper investigates the sample complexity of online RL in non-episodic settings with continuous state and action spaces. The authors develop a unified algorithmic framework that combines posterior sampling, Hedge-style model weighting, and certainty-equivalent control under persistent excitation. They provide theoretical policy-regret guarantees across three regimes:\n- finite model classes $O((\\ln N + \\ln m)/\\Delta)$, \n- general function classes via $\\varepsilon$-packing ($O(N\\varepsilon^2 + \\ln m(\\varepsilon)/\\varepsilon^2)$),\n- parameterized model families $O(\\sqrt{Np})$. \n\nThe analysis explicitly incorporates model identifiability ($\\Delta$), information complexity (packing number), and structural dimension ($p$), and demonstrates that the bounds are tight up to logarithmic factors. The work also relaxes the classical PE condition by connecting it to controllability Gramians and sub-Gaussian stability assumptions.", "questions": "1. In the weakly identifiable limit ($\\Delta \\to 0$), can one obtain a smoother adaptive transition between the $(\\ln N + \\ln m)/\\Delta$ and $\\sqrt{N\\ln m}$ regimes, possibly through hierarchical discretization or adaptive model aggregation?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The discussion of related work is exceptionally clear, and the citations appear comprehensive.\n2. The theoretical analysis is rigorous.\n3. The paper is well organized, and the narrative progresses with a coherent, reader-friendly logic.", "weaknesses": "While I do not see any glaring flaws, the following points prevent a stronger recommendation:\n1. Under the stated assumptions, the theoretical guarantees are not particularly surprising. Despite the authors’ thorough comparison with prior work, the contribution seems incremental relative to the papers referenced around line 67 of the manuscript.\n2. The problem setting is rather restricted, and its practical value is uncertain. The paper provides only simple numerical examples in the appendix, leaving real-world applicability unclear. In many practical scenarios, estimating $\\mu_\\theta$ is nontrivial, and the cardinality $|F|$ may grow exponentially with the size of the state space, which is not encouraging.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2bifCXHfCr", "reviewer": "Reviewer_XnW8", "summary": "The paper studies online reinforcement learning for non-episodic, continuous-state, continuous-action dynamical systems when the true dynamics are only known to lie in a rich model class. It proposes a family of posterior-sampling / Hedge-style algorithms that (i) keep a running, normalized one-step prediction loss for each candidate model, (ii) periodically sample a model according to a softmax over these losses, (iii) apply the corresponding certainty-equivalent controller, and (iv) inject excitation to guarantee persistence of excitation. The analysis is given for three settings: (S1) a finite set of nonlinear candidate models, where the frequentist policy regret scales as $O((\\ln N + \\ln m)/\\Delta)$; (S2) a bounded (possibly infinite) class of Lipschitz dynamical systems, controlled via an $\\varepsilon$-packing and yielding regret $O(N\\varepsilon^{2} + (\\ln N + \\ln m(\\varepsilon))/\\varepsilon^{2})$; and (S3) a compact $p$-dimensional parametric family (e.g. neural networks), where the regret becomes $O(\\sqrt{Np})$, recovering LQR-type rates as a special case. Conceptually, the work cleanly separates model identification from certainty-equivalent control, shows that simple excitation suffices to obtain nonasymptotic, frequentist guarantees, and unifies several strands of RL, online learning, and adaptive/multi-model control within a single sample-complexity framework.", "questions": "My concerns are already detailed in the cons section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper unifies three increasingly general control/learning regimes with one posterior-sampling–plus–Hedge template. It starts from a finite candidate set $\\{f_1,\\dots,f_m\\}$, where the frequentist policy regret is of order $O((\\ln N + \\ln m)/\\Delta)$, so the dependence on $m$ is logarithmic as in online learning. It then lifts this to an infinite/bounded function class by constructing an $\\varepsilon$-packing and obtains regret of the form $N\\varepsilon^2 + (\\ln N + \\ln m(\\varepsilon))/\\varepsilon^2$, which is the standard approximation vs. estimation tradeoff. Finally, for a compact $p$-dimensional parametric family it shows regret $(c_{r1}\\ln N + c_{r2}p)\\sqrt{N}$, recovering $O(\\sqrt{Np})$ for linear/LQR while still covering nonlinear dynamics. This gives a nonasymptotic, frequentist guarantee that is stronger than Bayesian-average PSRL bounds in related work. \n2. The algorithm is elegant: each round draws a model using a Hedge/posterior update, runs the corresponding certainty-equivalent policy, and injects excitation to ensure persistence-of-excitation and fast posterior concentration. This realizes a practical separation between model identification and control, avoids heavy OFU-style planning in continuous spaces, and naturally incorporates prior knowledge through the candidate set or parameter prior. \n3. The algorithm comes with solid theory. The paper gives three clear regimes of guarantees. For a finite set of models, the policy regret is $O((\\ln N+\\ln m)/\\Delta)$. For a Lipschitz class controlled by an $\\varepsilon$-packing, it becomes $O(N\\varepsilon^2+\\ln m(\\varepsilon)/\\varepsilon^2)$. For a $p$-dimensional parametric family, it is $O(\\sqrt{Np})$, matching LQR/adaptive-control rates. The bounds can be compared and tuned via $\\varepsilon$.", "weaknesses": "1. The analysis is essentially realizability-based: in all three settings (S1 with a finite set of candidates, S2 with an $\\varepsilon$-packed class, and S3 with a parametrized family) the true dynamics $f$ is assumed to lie in the modeling class $F$. In S1, Theorem 2.1 yields a policy-regret bound of order $O((\\ln N + \\ln m)/\\Delta)$, but this relies on a separation margin $\\Delta>0$ between the candidate models so that suboptimal ones can be eliminated; when the models are nearly indistinguishable the paper itself points out that one has to revert to an $O(\\sqrt{N \\ln m})$-type rate. For S2 and S3, the proposed procedures (Alg. 2 and Alg. 3) inject Gaussian excitation $n_{u,k} \\sim \\mathcal N(0,\\sigma_u^2 I)$ every $M$ steps to enforce the persistence-of-excitation requirement (Assumption 6) along the closed-loop trajectories. This condition is stated to hold uniformly over all misspecified models in the class, which makes the theory clean but may be nontrivial to verify or enforce on an actual control system.\n2. For the general setting (S2), the paper first reduces the infinite dynamics class to a finite one by taking an $\\varepsilon$-packing and then applies the same multi-model scheme as in S1. This leads to the regret bound $O(N\\varepsilon^2 + \\ln m(\\varepsilon)/\\varepsilon^2)$ in Theorem 2.2. However, using this result in practice implicitly requires (i) access to or construction of such an $\\varepsilon$-packing of the dynamics class, and (ii) the ability to run a controller for every element in the resulting finite cover. The paper also acknowledges that for Lipschitz-bounded dynamics the packing number $m(\\varepsilon)$ can grow very quickly in high dimension, so this part should be read more as an information-theoretic learnability guarantee than as a directly deployable method for high-dimensional continuous systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4fANQOuSAn", "reviewer": "Reviewer_Zps8", "summary": "This paper presents a theoretical study of the problem of online reinforcement learning in general (non-linear) continuous systems from the perspective of sample complexity. For context, this version of RL is the non-episodic setting which arose from generalising multi-armed bandits: one competes via regret with the best policy according to the ergodic/infinite horizon undiscounted cost functional (see Thm. 2.1-3). \n\nThe algorithmic solution here is a model-based exponential weights method, which applies to both finite and compact sets of models, which is appreciable. In terms of analysis, classical covering arguments on concentration inequalities of least-squares estimation are replaced by packing arguments for model classes in an expected regret analysis. The results consist in three bounds, in classical manner: the first is a gap-dependent bound, the second is scale dependent bound which depends on $\\epsilon>0$ and the packing number of the model class at scale $\\epsilon$, and finally a worst-case bound. \n\nIn the interest of full disclosure, I had the pleasure of reviewing this article before at ICML and EWRL, which allowed the authors to respond directly to some of my comments and questions and address the weaknesses I identified.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The theorems are clear and well-stated, the proofs are clear, and I haven’t found any issues with them in a superficial inspection. Technical claims are made and proven in a sound manner. The discussion of related works has grown and grown over my several encounters with the paper, and its depth and clarity really deserve commendation now!\n\nI think the contributions of the separation principle approach are deserving of dissemination, and while it is still difficult to situate the assumptions of different lines of work in online RL relative to each other,  the new set of assumptions should be of interest to others in the field.", "weaknesses": "As said above, my main criticisms of the paper have already been addressed by the authors in previous revisions. \n\nOne minor weakness which remains is that the writing has some strange repetitions that, I think, could be avoided. For instance, there are 3 persistent excitation conditions that vary slightly (and similarly for the Bellman super-solution assumption). Combining all three into a single assumption, e.g. by letting the constant take one of three values depending on the setting, would probably simplify the exposition of the appendices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)