Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds
Authors: Zhiyong Wang
Dongruo Zhou
John C.S. Lui
Wen Sun
Venue: ICLR 2025 Poster (2025)
Keywords: reinforcement learning theory
model-based reinforcement learning
Primary area: reinforcement learning

Abstract: Learning a transition model via Maximum Likelihood Estimation (MLE) followed by planning inside the learned model is perhaps the most standard and simplest Model-based Reinforcement Learning (RL) framework. In this work, we show that such a simple Model-based RL scheme, when equipped with optimistic and pessimistic planning procedures, achieves strong regret and sample complexity bounds in online and offline RL settings. Particularly, we demonstrate that under the conditions where the trajectory-wise reward is normalized between zero and one and the transition is time-homogenous, it achieves nearly horizon-free and second-order bounds.

Published as a conference paper at ICLR 2025
MODEL-BASED RL AS A MINIMALIST APPROACH TO HORIZON-FREE AND SECOND-ORDER BOUNDS
Zhiyong Wang', Dongruo Zhou², John C.S. Lui', Wen Sun
'The Chinese University of Hong Kong
Indiana University Bloomington *Cornel University
2ywang21@cse cuhk. edu. d2130iu 2e13@iu.edu, os osludccse. cuhk. edu. hk, w84550corne ledu
ABSTRACT
Learning transition model via Maximum Likelihood Estimation (MLE) followed by planning inside the learned model is perhaps the most standard and simplest Model-based Reinforcement Learning (RL) framework. In this work, show that such a simple Model- RL scheme, when equipped with optimistic and pessimistic planning procedures, achieves strong regret and sample complexity bounds in online and offline RL settings. Particularly, we demonstrate that under the conditions where the trajectory-wise reward is normalized between and one and the transition is time-homogenous, it achieves nearly horizon-free and second-order bounds.
INTRODUCTION
The framework of model-based Reinforcement Learning (RL) often consists of two steps: fitting transition model using data and then performing planning inside the learned model. Such simple framework turns out to be powerful and has been used extensively in practice on applications such
robotics and control (e.g.. (Aboaf al. 1989 Deisenroth al.) [001] Venkatraman al. 2017
Williams et al. Chua
Chua et al. 2018 Kaiser et al. 2019 Yang et al. (023)).
The simplicity of model-based RL also attracts researchers to analyze its performance in settings such as online RL (Sun et al.] 2019) and offline RL (Uchara & Sun, (2021). Mania et al. (2019) showed that this simple scheme fitting model via data followed by optimal planning inside the model, has strong performance guarantee under the classic linear quadratic regulator (LQR) control problems. [iu et al. (2023) showed that this simple MBRL framework when equipped with optimism in the face of the uncertainty principle, can achieve strong sample complexity bounds for wide range of online RL problems with rich function approximation for the models. For offline settings where the model can only be learned from static offline dataset, Uehara & Sun (021)) showed that MBRL equipped with the pessimism principle can again achieve robust performance guarantees for large family of MDPs. Ross & Bagnell (0022) showed that in the hybrid RI setting where one has access to both online and offline data, this simple MBRL framework again achieves favorable performance guarantees without any optimism/pessimism algorithm design.
In this work, we do not create new MBRL algorithms, instead, we show that the extremely simple and standard MBRL algorithm fitting models using Maximum Likelihood Estimation (MLE), followed by optimistic/pessimisiic planning (depending on whether operating in online RL or offline RL mode), can already achieve surprising theoretical guarantees. Particularly, we show that under the conditions that trajectory-wiss reward is normalized between zero and one, and the transition is homogeoog, they can achieve nearly horizon free and iitanceedeeendenn regret and sample complexity bounds, in both online and offline RL with non-linear function approximation. Nearly horizon-free bounds mean that the regret or sample complexity bounds have no explicit polynomial de- pendence on the horizon H. The motivation for studying horizon-free RL is to see if RL problems are harder than bandits due to the longer horizon planning in RL. Our result here indicates that, even under non-linear function approximation, Longhhorizon planning is not the bottleneck of achieving statistical efficiency in RL, For instance-dee deeendent bounds, we focus on second-ore -oder bounds. A second- orderr regret bound scales with respect the variances of the returns of policies and also directly implies

---

Published as a conference paper at ICLR 2025
first-order regret bound which scales with the expected reward of the optimal policy. Thus our instance- dependent bounds can be small under situations such as wearly-determiniin policy having small value. When specializing to the case of deterministic ground truth transitions (but the algorithm does not need to know this a priori), we show that these simple MBRL algorithms demonstrate faster convergence rate than the worst-case rates. The key message of our work is
systems or the optimal
Simple and standard MLE-based MBRL algorithms are sufficient for achieving nearly horizon-free and second-orde order bounds in online and offtine RL with function approximation.
We provide a fairly standard analysis to support the above claim. Our analysis follows the standard frameworks of optimism/pessimism in the face of uncertainty. For online RL. we use & Eluder dimension (Liu et al. 2022 Wang et al., 2024a), a condition that uses both the MDP structure and the function class, to capture the structural complexity of exploration. For offline RL, we use the similar concentrability coefficient in Ye et al. (2024) to capture the coverage condition of the offline data. The key technique we leverage the Iriangular discrimination divergence that is equivalent to the squared Hellinger distance up to some universal constants. Triangular discrimination was used in contextual bandit and model-free RL for achieving first-order and second-order instance-dependent bounds (Foster& & Krishnamurthy [021] Wang et al. 2023] 2024a). Here we show that it also plays an important role in achieving horizon-free bounds. Our contributions can be summarized follows.
1. Our results extend the scope of the prior work on horizon-free RL. which only ap- plies to tabular MDPs or MDPs with linear functions. Given a finite model class P (which could be exponentially large), we show that in online RL, the agent achieves an OV VaR,+) dRi log( K H/Pl/6) daI log( (PH(H)))))) regret, where K is the number of episodes, dRL is the l Eluder dimension, VaR,+ is the variance of the total reward of pol- icy x* learned in episode and 8 e (0, denotes the failure probability. Similarly, for offline RL, the agent achieves an 0 (VC**VaR+ log((P1/5)/K + C* log((P//8)/K) performance gap in finding a comparator policy n², where C'" is the single policy concentrability coefficient over n², K denotes the number of offline trajectories, VaR... is the variance of the total reward of x², For offline RL with finite P. our result is completely horizon-free, not even with log H dependence.
2. When specializing to MDPs with deterministic ground truth transition (but rewards, and models in the model class could still be stochastic), we show that the same simple MBRL, algorithms can adapt to the deterministic environment and achieve better statistical complexity. For online RL, the regret becomes (dRL log( K HP|/))) which only depends on the number of episodes K poly-logarithmically For offline RL, the performance gap comparator policy л² becomes o C* log((Pl/8)/R3 /)) which is tighter than the worst-case 0(1/VK) K) rate. All our results can be extended to continuous model class P using bracket number as the complexity measure.
Overall, we identify the minimalist algorithms and analysis for nearly horizon-free and instance- dependent (first & second-order) online & offline RL. By saying "minimalis"" mean the algorithm designs and analysis are much simpler than previous work on horizon-free free and second-order RL.
2 RELATED WORK
Learning transition models with function approximation and planning with the learned model is standard approach RL and control. the control literature, control learns model from some data and plans using the learned model, which is simple but effective for controlling systems such as Linear Quadratic Regulators (LQRs) (Mania et al. 2019). 9). In RL, such simple model-based framework has been widely used in theory with rich function approximation, for online RL (Sun et al. 2019 Foster et al. 2021] [Sog & Sun| 2021 Zhan et all 2022 Liu et al.) 2022 [202]] Zhong et 2022). ) offline RL (Uehara Sun| 202 1), RL with representation learning (Agarwal et al. 2020; Uehara et al., 2021). and hybrid RL using both online and offline data for model fitting (Ross& & Bagnell] 2012). Our work builds on the maximun-likelihood estimation (MLE)
Model-based RL.
approach, standard method for estimating transition models in model- based RL.
Horizon-free and Instance-dependers bounds. Most existing works on horizon-free RL typically focus on tabular settings or linear settings. For instance, Wang et al. (2020) firstly studied horizon-fre -ree RL for tabular MDPs and proposed an algorithm that depends on horizon logarithmically. Several follow-up work studied horizon-frre free RL for tabular MDP with better sample complexity (Zhang
et al. 2021ab, offline RI. (Ren et al. 2021), stochastic shortest path (Tarbouriech al. 2021 and
2

---

Published as a conference paper at ICLR 2025
RL with linear function approximation Kim et al. 2022 Zhang al. 2021b Zhou & Gu 2022
Di et al. 2023; Zhang et al. 2024b 2023; Zhao et al. 2023b). Note that all these works have logarithmic dependence
the horizon H. For the tabular setting, recent work further improved the regret or sample complexity to be completely independent of the horizon (i.e., removing the
logarithmic dependence on the horizon) (Li et al.. 2022 Zhang et al.) (022) with worse dependence on the cardinality of state and action spaces and [AI. A recent work Li & Yang (2023) further
improved the dependence on [S] and [A], To compare with, we show that simple MBRL algorithms are already enough to achieve completely horizon- frreee (i.e., no log dependence) sample complexity for offline RL when the transition model class finite, and we provide simpler approach to achieve the nearly horizon- free results for tabular MDPs, compared with Zhang et al.] (2021a). A recent work (Huang et al., 2024) also studied the horizon-free and instance-dependent online RI. in the function approximation setting with small Eluder dimensions. They estimated the variances to conduct variance- weighted regression. To compare, in our online RL part, we use the simple and standard MLE-based MBRL approach and analysis to get similar guarantees. A more recent work also studied horizon-frre free behavior cloning Foster et al. (2024), which is different from our settings.
Besides horizon-free RL, another line of work aimed to provide algorithms with instance- dependent sample complexity/regret bounds, which often enjoy tighter statistical complexity compared with previous work. To mention a few, |Zanette & Brunskill (2019) proposed EULER algorithm with an instance-dependent regret which depends on the maximum variance of the policy return over all policies. Later. Wagenmaker et al. (2022); ) /Wang et al./ (2023) proposed algorithms with first-order regret bounds. A more refined second-order regret bound has been studied. The second-order regret bound is a well-studied instance-dependent bound in the online learning and bandit literature (Cesa) Bianchi et al.) 2007: Ito et al., 2020, Olkhovskaya et al. 2024 Wang et al. 2024b), and compared to the bounds that depend on the maximum variance over all policies, it can be much smaller and it also implies first-order regret bound. Zhang et al. (2024a); Zhou et al. (2023) proposed algorithms for tabular MDP with second-order regret bounds. Zhao et al. (2023b) studied the RL with linear function approximation and proposed algorithms with both horizon-free and variance- deeendddd regret bounds. The closest work to us is Wang et al.) (2023 2024a),, which used model-free distributional RL methods to achieve first-order and second-order regret bounds in RL. Their approach relies on distributional RL., a somewhat non-conventional approach for RL. Their regret bounds have explicit polynomial de- pendence the horizon. Our work focuses the more conventional model- RL algorithms and demonstrates that they are indeed sufficient to achieve horizon-free and second-order regret bounds.
3 PRELIMINARIES
Markoy Decision Processes. We consider finite horizon time-homogenous MDP M (S, A. H, P", rr,)) where S, A are the state and action space (could be large or even continuous), H E N+ is the horizon, P :Sx x r (SS) is the ground truth transition, r: S x A + TR is the reward signal which we assume is known to the learner, and sg is the fixed initial state Note that the transi- tion P* here is time- tme-hhoogeeouus For notational easiness, we denote [K- [K-1] 1] {0, 1,...,, - 1}.
We denote æ as a deterministic non- con-staiionayy policy π = {To..... - where TTy S - A maps from state to an action. Let IT denote the set of all such policies. (s) represents the expected total reward of policy æ starting at 8). 8, and Q% (x,a) is the expected total reward of the process of executing at at time step h followed by executing to the end. The optimal policy n' is defined as π = argmax, + Vú (50). For notation simplicity, we denote V := Vo" (so). We will denote di. (s, a) as the state-action distribution induced by policy at time step h. We sometimes will overload notation and denote d, (s) as the corresponding state distribution at h. Sampling s ~ dī means executing starting from so to h and returning the state at time step h.
Since we use the model-based approach for learning, we define a general model class P Pc xxxx Ar A(S). Given a transition P, we denote VT.P and Qh. as the value and Q functions of policy i under the model P. Given function f S A+ I. we denote the (Pf) Eg-P(s.))( (s'). We then denote the variance induced by one-step transition P and function I as (Vp))ss = (Pf2) (s. (P)(ss)) which is equal to Ex -BBo))/)((((((BB)aaaaaaaa5 (Bv))(s.))(('))
'For simplicity, we assume initial state 8o is fixed and known. Our analysis can he easily extended to setting where the initial state sampled from an unknown fixed distribution.
3

---

Published as a conference paper at ICLR 2025
Assumptions. We make the realizability assumption that P* E PP We assume that the rewards are normalized such that r(r) e [O, 1] for any trajectory T (su, ao.... 3H-1. 0H-1) where r(r) is short for I r(s,, an). Note that this setting is more general than assuming each one-step reward bounded, i.e. r(sh,an) [o, I, and allows to represent the sparse reward setting. Without loss of generalizability, we assume (s) E [0, for all π I1 h é [0, PE
Online RL. For the online RL setting, we focus on the episodic setting where the learner can interact with the environment for K episodes. At episode k; the learner proposes policy *² (based on the past interaction history), executes T² starting from so to time step H - 1. We measure the performance of the online learning via regret: Σks (v* - V v-* To achieve meaningful regret bounds, we often need additional structural assumptions on the MDP and the model class P. We use ej Eluder dimension (Liu et al. 2022) as the structural condition due to its ability capture non-linear function approximators (formal definition will be given in Section 4b.
Offline RL. For the offline RL setting, we assume that we have a pre-collected offline dataset D = { which contains K trajectories Fl For each trajectory, we allow to potentially be generated by an adversary, i.e., at step h in trajectory k, (i.e., sf),, the adversary can select o based on all history (the past is 6-1 trajectories and the steps before h within trajectory k) with a fixed strategy, with the only condition that the state transitions follow the underlying transition dynamics, i.e., Sh+1 P* (s): a.)). We emphasize that D is not necessarily generated by some offline trajectory distribution. Given D, we can split the data into HK many state-action-next state (s, s') tuples which we can use to learn the transition. To succeed in offline learning, we typically require the offline dataset to have good coverage over some high-quality comparator policy x. (formal definition of coverage will be given in Section 5j. Our goal here learn policy that is as good n²', and we are interested in the performance gap between and "²" i.e., V -V²
Horizon-free and Second-order Bounds Our goal is to achieve regret bounds (online RL) or per- formance gaps (offline RL) that are (nearly) horizon-free, i.e., logarithmical dependence on H. In addi- tion to the horizon- free guarantee, we also want our bounds to scale with respect to the variance of the policies. Denote VaR,, as the variance of trajectory reward, i.c., VaR,, == (r(r) rr-)r Second-order bounds in offlin RL scales with VaR,- the variance of the comparator policy. Second- order regret bound in online setting scales with respect to VEx VaR.. instead of vK. Note that in the worst case, VL, VaR,, scales in the order of VK, but can be much smaller in benign cases such as nearly deterministic MDPs. We also note that second-order regret bound immediately implies first-order regret bound in the reward maximization setting, which scales in the order / VKV= instead of just VK. The first order regret bound V /KV=" is never worse than VK since V* s 1. Thus, by achieving a second-order regret bound, our algorithm immediately achieves a first-order regret bound.
Given two distributions p A(X) and q E A(X), we denote the trian- gle discrimination Da 9 = Exex (p(x)-g(w))² and squared Hellinger distance ( 4) p(x))a(2))
Additional notations.
Exex (Vq(z)- VV(xx) (we replace sum via integral when X is continuous and p and g are pdfs).
Note that DA and IH? are equivalent up to universal constants. We will frequently use the following key lemma (Wang et al. 2024a) to control the difference between means of two distributions.
Lemma 1 (Lemma 4.3 in Wang et al. (2024a). For two distributions f A((O, 11) and g E A[O0,]);
Ex- [x]] [x]] 4/ -D 5D (f ( 9).
(1)
where VaR, == Ex-
Ex- (x-- [x])² denotes the variance of the distribution f.
The lemma plays a key role in achieving second-order bounds (Wang al.) 2024a). The intuition is the means of the two distributions can be closer if one of the distributions has a small variance. A more naive way of bounding the difference in means is [E.. [xr] Ex-g [ar] [r]| s (maxzex [=]] gil x
(r()) e [0. 1] implies Vr,p- (s) E [o, 1J. If we do not assume (s) [0. 1] for all Pe P, we can simply add a filtering step in the algorithm to only choose R with (*o) [0. 1] to get the same guarantees.
*Our algorithms and analysis can also apply to the case where the dataset only consists of transitions, as they rely solely on transition-level information from the offline dataset.
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 Optimistic Model-based RL (O-MBRL)
Imput: model class P. confidence parameter 6 (0, 1), threshold B.
2: Initialize n². initialize dataset D = Ø.
3: for k= 0 1
4: Collect a trajectory r = {80, "o..,, (1-1 from x², split into tuples (s,a, and
add D.
Construct version space 5t:
/i 3 PEP: Σ log (((ls)) 2 max Σ 5.0.5/D
log (e(bee)))))
PeP a.0.steD
Set (x*, PM) + mun (o))())). 7: end for
(max H) || g) & (max,ex DD( Such approach would have to pay the maximum range maxzex |or] and thus can not leverage the variance VaRy. - In the next sections, we show this lemma plays an important role in achieving horizon-free and second-order bounds.
ONLINE SETTING
In this section, we study the online setting. We present the optimistic model-based RL algorithm (O-MBRL) in Algorithm I] The algorithm starts from scratch, and iteratively maintains a version space Dh of model class using the historical data collected so far. Again the version space designed such that for all i [0, -- 1]. we have P ε PA with high probability. The policy x in this case is computed via the optimism principle, i.e., it selects T and 7. such that V 2 V*'
Note that the algorithm design in Algorithm is not new and in fact is quite standard in the model- based RL literature. For instance, Sun et al.[ (2019) presented similar style of algorithm except that they use min-max GAN style objective for learning models. Zhan et al. (2022) used MLE oracle with optimism planning for Partially observable systems such as Predictive State Representations (PSRs), and Liu et al. 2023) used them for both partially and fully observable systems. However, their analyses do not give horizon-free and instance-dependent bounds. We show that under structural condition that captures nonlinear function class with small eluder dimensions, AAgorithhm ] achieves horizon-fii frre and second-order bounds. Besides, since second-ordes regret bound implics first-order bound (Wang et al. 2024a), our result immediately implies first-order bound as well.
We first introduce the Ep Eluder dimension as follows.
Definition 1 (lp Eluder Dimension), (M, the eluder dimension for with function class V. when the longest e-independent sequence x² x²....,æ² S X enjoys the length less than DE, M X, e). We say that a sequence x² ....,," s X is e-independent if there exists g V such that for all [L]. Etll lg('))) s e" and (g(x') >.
We work with the l Eluder dimension DE, (D, S c, with the function class V specified as: v = II (s, P(s, PeP)
Remark 1. The & Eluder dimension has been used in previous works such as Liu et al. (2022) We have the following corollary demonstrate that the dimension generalizes the original &z dimension of Russo Van Roy 2013), it can capture tabular, linear, and generalized linear models.
Lemma (Proposition 19 in (Liu al. 2022 For any V, <> (V, X,, s DE2 (,,X, c).
We are ready to present our main theorem for the online RL setting with finite class P.
Theorem (Main theorem for online setting with finite P). For any & E (0, 1), let 8 4 log with probability at least 1 - 6, Algorithm achieves the following regret bound:
KPP
Σ (V=' 1* s 0(1
VaR DE, (V, 8 x 1/K/H log(K log(K(H)
DE (V.S A,1/KH) (tt.///K)))/K((HHHHH// (K)
(2)
5

---

Published as a conference paper at ICLR 2025
The above theorem indicates the standard and simple O-MBRL algorithm is already enough to achieve horizon-free and second-order regret bounds: our bound does not have explicit polynomial dependences on horizon H, the leading term scales with VE& VaR,* instead of the typical v K.
We have the following result about the first-order regret bound.
Corollary (Horizon-free and First-order regret bound). Let B = =4 log
KPP
with probability at
least 1 6, Algorithm 7 achieves the following regret bound:
R-1
Σ k=0
V
& O0 (VVV*' ( A,..8xx,A77 1,1/KH) logH (og(K (og(KH)
DEI (V. (V..Sx log 10g((
Proof. Note that VaR, S V V* where the first inequality is because the vajectory-wiis reward is bounded in [0, 1]. Therefore, combining with Theorem we directly obtain the first-order result. D
Note that the above bound scales with respect to VKV** instead of just vK. Since V* s 1, this bound improves the worst-case regret bound when the optimal policy has total reward less than one
Faster rates for deterministic transitions. When the underlying MDP has deterministic transitions, we can achieve smaller regret bound that only depends on the number of episodes logarithmically. Corollary 2 (log K regret bound with deterministic transitions). When the transition dynamics of the MDP are deterministic, setting / log K(P)
w.p. at least 1- 6, Algorithm I achieves:
K-1 Σ
V"'
V" S (DE Sx A,1/KH) -og( KH (P10) log(KH))
Extension to infinite class P. For infinite model class P, we have a similar result. First, we define the bracketing number of an infinite model class follows.
Definition (Bracketing Number (Geer) 2000)). Let G be a sea of functions mapping X R. Given two functions u such that ((x) 1 su(x) for all e X, the bracket u, the set of functions e G such that I(x)) & g(x) S u(x) for all x E X. We call [7, u] an e-bracket if [|u - 2ll s Then, the is the minimum number of e-bracketing number of G with respect to -1- denoted by N, II)
e-brackets needed to cover G.
As an example, according to Appendix C.2 Uehara & Sun (021). the bracketing number of Linear Mixture MDPs PI = O(1/e) We use the bracketing number of denote the complexity of the model class, similar to [P] in the finite class case. Next, propose a corollary to characterize the regret with an infinite model class.
Corollary 3 (Regret bound for Algorithh I with infinite model class P). When the model class P is infinite, let 33 = log( KNO(( (( H(S)) ,P,ll o with probability at least - 8. Algorithm achieves the following regret bound:
KHNG((KH(S))
V"a va
DED A, KH
log(
(og(KH)
K-1 Σ VaR DV, A, 1 Am
(HNG(((H((S) 1 ,,P, mmm) log K H)
log(
KH
where (n 1, the bracketing number defined in Definition 2
A specific example of the infinite model class is the tabular MDP, where P is the collection of all the conditional distributions over S x A (SS) By Corollary we also have a new regret bound for MBRL under the tabular MDP setting, which is nearly horizon-free and second-order.
*Typically a first-order regret bound makes more sense in the cost minimization setting instead of reward maximization setting. We believe that our results transferable the most-minimization setting.

---

Published as a conference paper at ICLR 2025
Example 1 (Tabular MDPs). When specializing tabular MDPs. use the fact that tabular MDP has lg Eluder dimension being most [S||AA (Section D.I in Russo & Van Roy R (2013)) dimension is upper bounded by l2 dimension (Lemma 2), and use the standard e-nei argument to show that
Nille P. || (loo) is upper-bounded by (c/e)isi (i [Al (e.g., see Uehara & Sun 2021 ), we can show that
Algorithm 1 achieves the following regret bound for tabular MDP: with probability at least 1 8.
Σv- v= 50(1s)--1A) Σ VaR
log(
KHIS
log (KH)+ || log(
KH|S|
log log(KH))
In summary, we have shown that simple MLE- MBRL algorithm is enough to achieve nearly horizon-free and second-order regret bounds under non non-linear function approximation.
4.1 PROOF SKETCH OF THEOREM
Now we ready to provide proof sketch of Theorem I with the full proof deferred to Appendiix D.I For ease of presentation, we use dRL to denote DE, (V, S x A, 1/K H), and ignore some log terms.
Overall, our analysis follows the general framework of optimism in the face of uncertainty, but with (1) careful analysis in leveraging the MI_E generalization bound and (2) more refined proof in the teining-to-testing distribution transfer via Eluder dimension.
By standard MLE analysis, we can show w.p. 1 ö, for all k [K- 1], we have P e pk, and
H-1 Σ h-0
(s.. (1) (t) (loo((((P//0)
From here, trivially applying previous works (e.g.. Wann et al. (2024a)) would cause poly-dependence H. With techniques detailed in Appendix B, which is one of our technical contributions and may be of independent interest, can get: there exists set IC [K -J such that [AC] s O(dRL log( (og(K/PP/// (K(P)))). and
distribution transfer via the Eluder dimension as
Σ Σn²(r (P' kE[K-1]JK
P' (sh, a || Ph (sh af)) s O(dAL - loool K (P|/0) log K KH)).
(4)
Recall that (T Ph) argmax, I-II, Pepi (s0), with the above realization guarantee Pa e PP we can get the following optimism guarantee: Vr S max PeB V = V 0
At this stage, straight-forwart way to proceed is to use the standard simulation lemma Leemma 7):
K-1#-1
vot O.P. 0.P.
Σ
E
[Be Val ha
(s') (s') B. (M, Vat pa (s)) (5)
s,0-d
However, from here, if we naively bound each term on the RHS via E,
",a-d;"" (s'(s P(s, a)
which is what previous works such as Uehara & Sun (202I) I did exactly, we would end up paying linear horizon dependence H due to the summation over on the RHS the above expression. Given the mnai-ne-vvrraace lemma (Lemma I). we may consider using it to bound the difference between two means (g--P((s.)) V= 1+ (s') -Eg.. V=* h+ (s'). This still can not work if we start from here, because we would eventually get Σ, Σn E, s.a-ar"" [[I (s, P) a))] terms, which can not be further upper bounded easily with the MLE generalization guarantee.
To achieve horizon- free and second-order bounds, we need a novel and more careful analysis.
First, we carefully decompose and upper bound the regret in iC == [K- N IC w.h.p. as follows using Bernstain's 's inequality (for regret in K. we simply upper bound it by (AC)
Σ Rel
k Ph (sht)
H-1 Σ
rsshi
Σ kek
Σ
rss at:)
venk
Σ pv Vxx pa at))
Σ
By Bh Vitn Ex-Pe virh
paun, (s') (0))++
Σ VaRy log( 1/6).
(6)
keR
7

---

Published as a conference paper at ICLR 2025
Vea Then, bound the difference of two means Pss. 1+1:F% Fu (6') Ex- (a) V** 1= (8)
using variances and the triangle discrimination (see Lemma I for more details), together with the fact that D& 4H2, and information processing inequality on the squared Hellinger distance, we have
Vor 1 (6') - -Byr. ot) Egg (A (of at)
Viri Vi (5')l
0 (Vr Vot M4 ) Do Do Vet
h+ (s' P (s)),,))) at)) | Vak ho (s'~ (k,s),.t))
DD +D pa p (sh. aht) Vir Viri, (sh. (h)))
s s0lv (Vpr
Vet Val ho (6 of ( (stt, a (tss
(P'(P'(( (s), P* (s))
where we denote V 15 as)) as the distribution of the random variable V (s')) with s' ~ P as) This is the key lemma used by Wang et al. (2024a) to show distributional RL can achieve second-order bounds. We show that this is also crucial for achieving horizon-free bound.
Then, summing up over k, h, with dimension in Equation 4] we have
and the MLE generalization bound via Eluder Vi
ΣΣ kcR. h.
E. BR of (
V hh (6') (.L (t) 1 (6) s 0 Σ Σ
(P
P* (sh
kcR
Σ Σ kel A
(V Vik
Ne (s ( a beek
Σ Σ
H PM (P* att (A at))
h
Var (Vp.
be (st / at deu log log(K(Pl/8) (og(K)))H))))) dai log( K (P|/6) log(k))))))
(7)
ReR
Note that we have (Vr-V V=* h= (8) ()) depending on ph. To get a second-order bound, we need to convert it to the variance under ground truth transition P and we want to do without incurring any // dependence. This is another key difference from Wang el al. (2224a).
We aim to replace (Vp- v
(sh, at) by (Vp. (sk, a which is the variance under P' (recall that V is the value function of a under P*), and want to control the difference
(Vp. (yat (v - -V (shh, a.)) To do so, we need to bound the 2m moment of the difference
vx* B V following the strategy in Zhang et al. 2021aa Zhou & Gu 2022
Zhao et al. 2023b)
Let us define the following terms:
A == kek h
Σ ΣΣ
(V
(Vr= w 1- (sh. C.m Cm
Σ ΣΣ
(Vp-
(V vort (s at))
pV h-1 (shh o1h) G= Va dAL daL log(
KPP)
K (P) log log(KH).
B Σ
log(KH) + daL log(
8
With the fact Vp (a b) pa) +V p- (b) we have A s 2B + 2Co. For Cm. we prove that + log(1/8). during which process we also leverage the above Equation 7 and some careful analysis (detailed in Appenddx D.Ip. Then, with the recursion lemma (Lemma II). we can get Co S G, which further gives us
w.h.p. it has the recursive form Cy, S 2mm 2
K [P] 8
K KPPI
K(P log K K)),
A s B + daL log(
log(KH)+ V A daL log(
log( KH) O(B daL log(
where in the last step we use the fact x S 2a + 6² if x S a b/z. Finally, we note that B S log(1/))) 1/))) w.h.p.. Plugging the upper bound of A back into Equation 7 and then to
O VaR,, + log(
Equation we conclude the proof.
OFFLINE SETTING
For the offline setting, we directly analyze the Constrained Pessimism Policy Optimization (CPPO- LR) algorithm (Agorithmm 2) proposed by [uehara & Sun (202I). We first explain the algorithm and then present its performance gap guarantee in finding the comparator policy x."
8

---

Published as a conference paper at ICLR 2025
Algorithm 2 (Uehara & Sun 2)21)) Constrained Pessimistic Policy Optimization with Likelihood- Ratio based constraints (CPPO-LR)
1: Input: dataset = (s. a, J. model class P. policy class II, confidence parameter e (0, 1), threshold
Calculate the confidence based the offline dataset:
log P(e(ls,, s).
P PEP: Σ
log ((s)(s,,)) [-1
max PoP m
3: Output: f argmaxxen pup (va)
Algorithm 2 splits the offline trajectory data that contains K trajectories into dataset of (s, s') tuples (note that in total we have n K many tuples) which is used to perform maximum likelihood estimation max Di=1 log (s a;). It then builds a version space P which contains models P P whose log data likelihood is not below by too much than that of the MLE estimator. The threshold for the version space is constructed that with high probability, P P. Once we build version space, we perform pessimistic planning to compute म.
We first define the single policy coverage condition follows. Definition 3 (Single policy coverage). Given any comparator policy x², denote the data-dependent single policy concentrability coefficient CF as follows:
E. ",ardd
TH2 (P(,,a) PT (s)
C
max P.P
I/K H²² (P(s), P at))
We assume w.p. least 8 over the randomness the generation of D, we have C% C
The existence of C*a is certainly an assumption. We now give an example in the tabular MDP where we show that if the data is generated from some fixed behavior policy x² which has non-trivial probability of visiting every state-action pair, then can show the existence of C
Example 2 (Tabular MDP with good behavior policy coverage). If the K trajectories are collected i..d. with fixed behavior policy n., and dj (s.a) 2 Pmiin Vss a, h (similar to Ren et al. 2021) then have: if K is large enough, i.e., K 2 ( w.p. at least 1 5, C5 2//Prin-
Our coverage definition (Definition 3) shares similar spirits as the one Ye et al. (2024). reflects how well the state-action samples in the offline dataset D cover the state-action pairs induced by the comparator policy n². It is different from the coverage definition in Uehara & Sun (022I) in which the denominator is E ",a-aa" a III (P(s,a) P' (s. where nO is the fixed behavior policy used
to collect D. This definition does not apply in our setting since D is not necessarily generated by some underlying fixed behavior policy. On the other hand, our horizon-free result does not hold in the setting of Uehara & Sun 22021) where D is collected with fixed behavior policy x² with the concentrability coefficient defined in their way. We leave the derivation morizon-free results in the setting from Uehara & Sun (202T) as future work.
Now we are ready to present the main theorem of Algorithmm for finite P, which provides tighter performance gap than that by Uehara & Sun (2021).
Theorem 2 (Performance gap of Algorithm with finite P). For any & (0,1), ler 9 lo)(())/)). w.p. at least 1 - 8, Algorithm 2 learns a policy मे that enjoys the following performance gap with respect to any comparator policy n=:
V v s 0
(VC VaR,. log((P/6))KK C* log((P/)))/).
Comparing to the theorem (Theorem 2) of CPPO-LR from Uehara & Sun (022). our bound has two improvements. First, our bound is horizon-free (not even any log( (7) dependence), while the bound in Uehara & Sun( (202T) has poly H) dependence. Second, our bound scales with VaR, [0. 1]. which can be small when VaR,, << 1. For deterministic system and policy π², we have VaR which means the sample complexity
scales a faster rate C /K. The proof is in Appendix E.
We show that the same algorithm can achieve 1/K rate when P is deterministic (but rewards could be random, and the algorithm does not need to know the condition that P is deterministic).

---

Published as a conference paper at ICLR 2025
Corollary 4 (C* |K performance gap of Algorithm 2 with deterministic transitions). When the ground truth transition P of the MDP is deterministic, for any á E (0. 1). let 3 4log((P1/8) w.p. at least 1- 8. Algorithm 2 learns policy ß that enjoys the following performance gap with respect to any comparator policy x=:
V" V s ( log((P1/6)/K)
For infinite model class P, have similar result in the following corollary.
Corollary 5 (Performance gap of Algorithm 2 with infinite model class P).. When the model class P is infinite, for any 10,1), ) let 3 = 7 llog(N (KK((H)))))) ((S))-1,, ,, 1/)), w.p. at least
Algorithm 2 learns a policy से that enjoys the following PAC bound w.r.t. any comparator policy n²:
V -V So
C VaR,, (KH))) 1w)))) C (og( 1/))
K
K
where N (n]((H(S))) PPI1| (lw))
is the bracketing number defined in Definition
Our next example gives the explicit performance gap bound for tabular MDPs.
Example 3 (Tabular MDPs). For tabular MDPs, have Nf(e, (lw) upper-bounded by (c/c)15AAA) (e.g.. see Uehara & Sun 2021)). Then with probability at least 1 - 6, let B Tlog(N ((KH(S)) .P. 1o0)
)o), Algorithm learns a policy R satisfying the following per- formunce gup with respect to any comparator policy x":
V V - 5O( VaR log( K | (og(KH((1/6)/K)
The closest result is from Ren al. 2022 which analyzes the MBRL for tabular MDPs and obtains a performance gap Ö(v Kd... Kdd.. where dm is the minimum visiting probability for the behavior policy visit each state and action. Note that their result not instance-dependent which makes their gap only ((1/V/() K) even when the environment deterministic and x* is deterministic. In sharp contrast, our analysis shows a better Ō(1/K) K) gap under the deterministic environment. Our result would still have the log H dependence, and we leave getting rid of this logarithmic dependence on the horizon H as an open problem.
CONCLUSION
In this work, we presented minimalist approach for achieving nearly horizon-free and second-order bounds in online and offline RL: simply train transition models via Maximum Likelihood Estimation followed by optimistic or pessimistic planning, depending on whether we operate in the online or offline learning mode. Our horizon-free bounds for function approximation look quite similar the bounds in Contextual bandits, indicating that the need for long-horizon planning does not make RL. harder than CB from statistical perspective.
Our work has some limitations. First, though our results can achieve completely horizon free (not even log H dependence) for offline RL with finite model classes, in other settings we have log H dependence. We conjecture that the log( ()) can be eliminated by using more careful analyses in dealing with the learned models' extrapolation errors via eluder dimensions, and using techniques such as peeling/chaining (Dudley) 1978, [Zhang] 2006) when tackling infinite model classes. We leave this as an important future direction. Second, our model-based framework cannot capture problems that need to be solved via model-free approaches such as linear MDPs (Jin et al., (020). An interesting future work is to see we can extend our analysis to incorporate the function classes with small distributional Eduler dimensions, and if we can develop model-free approaches that can achieve horizon-free and instance -deennded bounds for RL with general function approximation. Finally, the algorithms studied in this work are not computationally tractable. This is due to the need of performing optinism/pessimisn planning for exploration. Deriving computationally tractable RL algorithms for the rich function approximation setting is long-standing question.
10

---

Published as a conference paper at ICLR 2025
7 ACKNOWLEDGEMENT
Wen Sun acknowledges funding support from NSF IIS IIS-2154711, NSF CAREER 2339395, DARPA LANCER: LeArning Network CybERagents. The work of John C.S. Lui was supported in part by the RGC 122-1420.
REFERENCES
Eric W Aboaf, Steven Mark Drucker, and Christopher G Atkeson. Task-level robot learning: Juggling a tennis ball more accurately. In Proceedings, 1989 International Conference on Robotics and Automation, pp. 1290-1295. IEEE, 1989.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. 2019.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20100 2020.
Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for predic- tion with expert advice. Machine Learning, 66:321-352, 2007.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in handful of trials using probabilistic dynamics models. Advances in neural information processing systems, 31, 2018.
Marc Deisenroth, Carl Rasmussen, and Dieter Fox. Learning to control low-cost manipulator using data-efficient reinforcement learning. Robotics: Science and Systems VII, 2011.
Qiwei Di, Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal regret for learning linear mixture stochastic shortest path. In International Conference on Machine Learning, pp- 7837-7864. PMLR, 2023.
Richard M Dudley. Central limit theorems for empirical measures. The Annals of Probability, pp- 899-929, 1978.
Dylan J Foster and Akshay Krishnamurthy. Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. Advances in Neural Information Processing Systems, 34: 18907-18919, 2021.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13488) 2021.
Dylan Foster, Adam Block, and Dipendra Misra. behavior cloning all you need? understanding horizon in imitation learning. arXiv preprint arXiv:2407.15007 2024.
Sara A Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
Jiayi Huang, Han Zhong, Liwei Wang, and Lin Yang. Horizon-free and instance-dependent re- gret bounds for reinforcement learning with general function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 3673-3681. PMLR, 2024.
Shinji Ito, Shuichi Hirahara, Tasuku Soma, and Yuichi Yoshida. Tight first-and second-order regret bounds for adversarial linear bandits. Advances Neural Information Processing Systems, 33: 0038-2038, 2020.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-lerrning provably efficient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on learning theory, pp. 2137-2143. PMLR, 2020.
11

---

Published as a conference paper at ICLR 2025
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, et al. Model-based reinforcement learning for atari. arXiv preprint 0rXiv:1933.00377 2019.
Yeoneung Kim, Insoon Yang, and Kwang-Sung Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing Systems, 15:1060-107 2022.
Shengshi Li and Lin Yang. Horizon- free learning for markov decision processes and games: stochas- tically bounded rewards and improved bounds. In International Conference on Machine Learning. pp. 20221-20252. PMLR, 2023.
Yuanzhi Li, Ruosong Wang, and Lin F Yang. Settling the horizon-dependence of sample complexity in reinforcement learning. In 202 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pp. 965-976. IEEE, 2022.
Qinghua Liu, Alan Chung, Csaha Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? In Conference on Learning Theory, pp. 5175-5220. PMLR, 2022.
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle: A generic model- based algorithm for partially observable sequential decision making. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 363-376, 2023.
Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. Advances in Neural Information Processing Systems, 32, 2019.
Julia Olkhovskaya, Jack Mayo, Tim Erven, Gergely Neu, and Chen Yu Wei. First-and second- order bounds for adversarial linear contextual bandits. Advances in Neural Information Processing Systems, 36, 2024.
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offine reinforcement learning. Advances in neural information processing systems, 34:15621-15634, 2021.
Stephane Ross and J Andrew Bagnell. Agnostic system identification for model-based reinforcement learning, arXiv preprint arXiv: 1203. 2012.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Yuda Song and Wen Sun. Pe-mlp: Model-based reinforcement learning with policy cover guided exploration. In International Conference on Machine Learning, pp. 9801-9811. PMLR, 2021.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. Conference on learning theory, pp. 2898-2933 PMLR, 2019.
Jean Tarbouriech, Runlong Zhou, Simon S Du, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Stochastic shortest path: Minimax, parameter-free and towards horizon-free frre regret. Advances in neural information processing systems, 34:6843-688 6855, 2021.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226, 2021.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. arXiv preprint arXiv:2110.0444 2021.
Arun Venkatraman, Roberto Capobianco, Lerrel Pinto, Martial Hebert, Daniele Nardi, and J Andrew Bagnell. Improved learning of dynamics models for control. In 2016 International Symposium on Experimental Robotics, pp. 703-713. Springer, 2017.
Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pp. 22384-22429. PMLR, 2022.
12

---

Published as a conference paper at ICLR 2025
Kaiwen Wang. Kevin Zhou, Runzhe Wu, Nathan Kallus, and Wen Sun. The benefits of being distributional: Small-loss bounds for reinforcement learning. Advances in Neural Information Processing Systems, 36, 2023.
Kaiwen Wang, Owen Oertell, Alekh Agarwal, Nathan Kallus, and Wen Sun. More benefits of being distributional: Second-order bounds for reinforcement learning, arXiv preprint arXiv:2402.07118, 2024a.
Ruosong Wang, Simon S Du, Lin F Yang. and Sham M Kakade. Is long horizon reinforcement learning more difficult than short horizon reinforcement learning? arXiv preprint arXiv:2005.00527, 2020.
Zhiyong Wang. Jize Xie, Yi Chen, John Lui, and Dongruo Zhou. Sariance-dependees regret bounds for non-stationary linear bandits. arXiv preprint arXiv:2403. 10732, 2024b.
Grady Williams, Nolan Wagener, Brian Goldfain, Paul Drews, James M Rehg, Byron Boots, and Evangelos A Theodorou. Information theoretic mpe for model-based reinforcement learning. In 2017 IEEE international conference on robotics and automation (ICRA), pp. 1714-1721. IEEE, 2017.
Mengjiao Yang. Yilun Du, Kamyar Ghasemipour, Jonathan Tompson, Dale Schuurmans, and Pieter Abbeel. Learning interactive real-world simulators. arXiv preprint arXiv:2310.06/ 14, 2023.
Chenlu Ye, Rui Yang, Quanquan Gu, and Tong Zhang. Corruption-robust offline reinforcement learning with general function approximation. Advances in Neural Information Processing Systems, 36, 2024.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. Pac reinforcement learning for predictive state representations. arXiv preprint arXiv:2207.05738, 2022.
Junkai Zhang, Weitong Zhang, and Quanquan Gu. Optimal horizon-fiee reward- -ree exploration for linear mixture mdps. In International Conference on Machine Learning. pp. 41902-41930. PMLR, 2023.
Tong Zhang. From s-entropy to kl-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, pp. 2180-2180020 12000000222--1001110111022220012 2006.
Zihan Zhang, Xiangyang Ji, and Simon Du Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference Learning Theory, pp. 4528-455 4531. PMLR, 2021a.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342-4355, 2021b.
Zihan Zhang, Xiangyang Ji, and Simon Du. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference on Learning Theory, pp.
PMLR, 2022.
Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory, pp- $213-5219. PMLR, 2024a.
Zihan Zhang, Jason D Lee, Yuxin Chen, and Simon S Du. Horizon-free regret for linear markov decision processes. arXiv preprint 17X1v:2403.10738, 2024b.
Heyang Zhao, Jiafan He, and Quanquan Gu. A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation. arXiv preprint arXiv:2311.15235. 2023a.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance -ependee-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference Learning Theory, pp. 4977-5020. PMLR, 2023b.
13

---

Published as a conference paper at ICLR 2025
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang. Zhuoran Yang. and Tong Zhang. Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond. arXiv preprint arXiv:2211.01992 2022.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. Advances in neural information processing systems, 35:36337-36349, 2022.
Runlong Zhou, Zhang Zihan, and Simon Shaolei Du. Sharp variance-dependden bounds in reinforce- ment learning: Best of both worlds in stochastic and deterministic environments. In International Conference Machine Learning, pp. 12878-42914 PMLR, 2023.
14

---

Published as a conference paper at ICLR 2025
A SUMMARY OF CONTENTS IN THE APPENDIX
The Appendix is organized as follows.
In Appendix B,
we provide some new analyses for Eluder dimension, which we will use for proving the regret bounds for the online RL setting.
In Appendix C we provide some other supporting lemmas that will be used in our proofs.
Appendix we provide the detailed proofs for the online RI. setting (Section 4). Specifically, in Appendix D. we give the proof of Theorem 1; in Appendix 15.2 we show the proof of oorollaayy 2
i Appendix D.3 we give the proof of Coroolaryy 3
In Appendix D
we provide the detailed proofs for the offline RL setting (Section 5). Specifically, in Appendix E. we give the proof of Theorem 2] in Appendix E.2 we show the proof of ofroolllrry 4
Appendix E.3
we give the proof of Corollaayyy in Appendix E.4. show the proof of the claim
in Example
B ANALYSIS REGARDING THE ELUDER DIMENSION
For simplicity, denote = (5% at)).
First we have two technical lemma. The first lemma bounds the summation of "self-normalizatioon" terms by the Eluder dimension. Our result generalizes the previous result by Zhao et al. (2023a) from the l2- fz-Eluder dimension to the l case.
Lemma 3. Suppose for all g V, V.lg| S and À 1, then we have
K
H
lg(x
Σ
min
sup kk1 En 1o(x+)))++++++0+++0)) Eh (
12 lalloog(2X0 (4XKH). DE S 1/ + +x-
Proof of Lemma 3
We follow the proof steps of Theorem 4.6 in Zhao et al. (202a)). For simplicity, kH h to denote the indices and denote 5x by wt. Then need to prove
we use KH,
19(x,))
Σ
min
s,sup geV/ Σ: (x(x)) 1
12 (4XD)) DE, (V, ( A,1/(8Am)) -
(8)
Let
Ig(x;)|
9: argmax geV
(9)
Σ +((z))++>
For any 1/(An) $ s and i (log(42)) we define
19((x;)]
A/- = iE [n]:2 (x:)) 2-1
dj d DE, (10) Σt= (x:)) 2 p/2)
Next we only consider the set A where |AAi > dj. We denote A {ai..... aA). where A |A/
and {as} keeps the same order as {xxe) Next we do the following constructions. We maintain
k= ((AA((1100 1)/d,] number of queues Q1,-.., . Qk. all of them initialized as emptysets. We put a into
Q1. For a,, i 2 elements in Qt. Let imx be the smallest i when we can not put a; into any existing queue.
put a; into Qt. where Qi is the first queue where a; is 2 inndiedennne of all
We claim that ima indeed exists, i.e., our construction will stop before put all elements in A into Q1,... Qk- In fact, note the fact that the length of each Qi is always no more than dj. which is due to the fact that any 2-1-independent sequence's 's length is at most dj. Meanwhile, since we only have [(A - J, then the amount of elements in Q: U...U u Qx will be upper bounded by k dj < A. That suggests at least one element in A is not contained by Q U...u Qk. i.e., imax exists.
By the definition of imax, we know that asmav 2 deependdn to each Qt. Next we give bound of A. First, note
Dimaa 0mmae(2:)) (2x))2
Σ
1gimar (at))
Σ
Σ
[iimae (at) k 2-
(11)
LEQIU-UQk
1-1 1tte)
15

---

Published as a conference paper at ICLR 2025
where the first inequality holds since Qi are the elements that appear before Gimax the second one holds due to the following induction Eluder dimension: since aimar is 2 deeddeeede to Q₁, then we have
Vg E v, Eg((a)) s > (imm) ) 2
(12)
Therefore, given the fact 19tmae (atmax)) ) > 2 (recall the definition of A2). we must have Σteq: 19imas (at) > 2 well, which suggests the second inequality of Equation 11 holds. Second, we have
Piuas (x+1) s 2/p |9rma (#tmms)) 54
(13)
where both inequalities hold due to the definition of A2. Combining Equation 11 and Equation we have
k <<4/p= As 4d,4 p dj s 5d.
(14)
Therefore, we have that for all p.j. |4/ $ 5d./p. Finally we prove Equation 8
1/(An) $ sps and 1 I j $ [log((Arri]= J. Denote
(x:))
Ap = ( [m]
2 2/2
(15)
Σi-1 Ig (x:)) +
Then it is easy to notice that |Apl Σ3 |AAi [log(4An) 5d. Eluder dimension dj is increasing. Therefore, by the standard peeling technique, we have
where use the fact that the
19(2;)]
min
1, sup ge
=
Σ Je[llog( An) ie 1
Σ
Σ Σ
Σi=l 19(x,)))
(=[log(Am)] i A
Σ
Σ
2 1/(An)
[e(llog(An)) (A)) SEAg-1 Agg-ss
$ Σ
Σ
2-1-1
+ n- 1/())
]e[[log(An)]]
leAz-1
s [log(An))
[log(4An)) 3d, x-1
which concludes our proof.
Next lemma gives a bound bound the number of episodes where the behavior along these episodes are "bad". Intuitively speaking, our lemma suggests we only have limited number of bad episodes, therefore won't t affect the final performance of our algorithm.
Lemma 4. Given À > 1. There exists at most
13 13g (4AKH) DE,(U, x A, ((((8KH))
(16)
number of k [K] satisfying the following claim
A+ Σ Ek- H (g(
sup ge
> 4. (2(
(17)
A
- H
Proof of Lemma 4
Note that
A Σt' Σ 19(
Σ
min
2, log sup gew
k=1
X
Σk-1 19
H
A E E 1
H
lg lx(x
min
2, log
sup
k=1
h=1 9Ew
_ M- Σ |9(
+ Σ (
K
H
1g |g(xtt1
Σ
min
2, Σ
log
1 + sup
k=1
gew
lo (1/1)
Σ (9(x
16

---

Published as a conference paper at ICLR 2025
K H
l0(x%)
Σ min
sup geV
k-1 2k'=1 MN (1 + En 10( +
K H
|,(x,,1
2
Σ
min
L,sup
km himl
geV/
2k'=1 LM [x()))) Exr=
k-1 I
< 24 24 (4NKH) DE1 0 1/(8XKH))) + 2X
< 26 (4XKH) (V x A,
(18)
where the first inequality holds since sup, [g) log(1 + 2) s x, the fourth one holds due to Lemma Therefore, there are at most
sup, f(g), the second one holds since
261og 26 (4XKH) (.1
number of satisfying
A Σ k-=1 2k-=1 lg( (++++)
logsup geV
22 A =k=11 2h/=1 lx(xx))
which concludes the proof.
We next have the following lemma, which bounds the regret by the Eluder dimension.
Lemma 5 (Theorem 5.3, Wang et al. 2023). Let C := sup suspe a))l be the envelope. v. (s, ....., (M) s S A, let 3 be constant such that for all [N] we have, ( ((s,a))) s B. Then, for all [N], have
For any sequences f(1), ,.......f f(M) (()
((s))())))))) inf (DE (V, S A,C) Blog(C/)) + ne). 0segl
Given Lemma and Lemma Lemma we able prove the following key lemma.
Lemma 6 (New Eluder Pigeon Lemma). Let the event & be
: E [K],
Σ Σ HH' (s), ( sn.
(19)
2-1 h-1
Then under event E, there exists set K. E [K] such that
We have |C] s 13
DE, A, 1/(8nK11),
We have
Σ (P Ph (st
kee K h
inf (V.S log (l))) KHl) 0ces1
DE A (2 7n/log( K ( +1,
(20)
where the function class ((x,a) + म2 (P' (s.a) P(s. a)) PeP)
Proof of Lemma 6 We interchangeably use n = kH + h to denote the indices of s of We set f(() ((s,a) a)) in Lemma 5 as (2 P*
First, we prove that the 3 in Lemma can be selected as 7n under event E. To show that, let K. denote all the k stated in Lemma 4
Then for all & such that & 1 & K., h = 2, H. let = kH + h we have
kH-H
((s,)())))))
Σ 0
((,a))))))
100
17

---

Published as a conference paper at ICLR 2025
kH A ((() ((s,a)²)
Ero | ((s,)))) -A
Σ
+
1-
kH
A Σ
E(((n)
((s,)))
-
10
7n,
(21)
where the second inequality holds due to Lemma 4 the last one holds due to the definition of E Therefore, prove lemma by the conclusion of Lemma 5 with 7n.
C OTHER SUPPORTING LEMMAS
Lemma 7 (Simulation Lemma (Agarwal et al. (0119)). We have
H-1 Eg Ex [ (s,a) V (s')) By..((aa) V (
Vo
0:P
Lemma 8 (Change of Variance Lemma (Lemma C.5 in Jin et al. 2018))).
Σ E. a- Ve VaR,,
Lemma 9 (Generalization bounds of MLE for finite model class (Theorem E.4 in Wang et al. (2023 )), Let X be the contextifeature space and y be the label space, and we given dataset D= (Xi, w:) ie[n] from martingale process: for 1.2....,Th, n, sample I; Di(TTii-, (ha-1) and V: ~ p( ar). Let f (xxx)) ply x) and we are given realizable, i.e., f e F, function class F: x y + A (R) of distributions. Suppose is finite. Fix any 8 E (0,1). set B = log((F)/)) and
define
F= FEF Σ log ((r,
) 2 max Σ
12
log [(x; U:) 48
feF 1=
Then w.p. at least - 8, the following holds:
(1) The true distribution is the version space, i.e. I FF.
(2) Any function in the version space is close to the ground truth data datta-generating distribution, i.e. for all f F
Σ EE.D.. (H) (f 223.
Lemma 10 (Generalization bounds of MLE for infinite model class (Theorem E.5 in Wang et al. (203 )) Let X be the context/feature space and y be the label space, and we given dataset D (xx, y:) se|m]
be))ee from a martingale process: for i == 1,2,...,n, n, sample 2; ~ 'D; (1 V1a-1) and ~ p(- x.). Let fx y) = =py Ix) and we are given realizable, i.e., f E F. function A(R) of distributions. Suppose is finite. Fix any (0, 1), set B
class F X x
log(Nn (n) -, 1xx)/))))))) (where Nn((m)))))> _F,Il lx) is the bracketing number defined
in Definition 2) and define
F 3=(1e5: Σ Elogs(E (x;, 2 max Σ log (x), -78 78
feF
Then w.p. at least 1 - 8, the following holds:
(1) The true distribution is in the version space, i.e., f E F..
(2) Any function in the version space is close the ground truth data- data-gennrattng distribution. i.e., for all f &
Σ E..D.
288.
18

---

2. The induction step: Published as a conference paper at ICLR 2025
Lemma 11 (Recursion Lemma). Let G 0 be positive constant, < G/2 is also positive constant,
N-floga( K) be sequence of positive real numbers satisfying:
and let {Cm] m-0
1. Cm S VaCm+i for all m
2. Cm KKH.H. for all m 2 O, where K > and 0 are positive constants.
Then, it holds that:
Co 4G.
Proof of Lemma 11. We will prove by induction that for all m 2 O,
Cm 2 G. Then, for this would immediately show Co 4G.
1. The base case m = N:
Since N [log2( ( },, is obvious that 2N KH. Thus, CN KH 22+G, the inequality holds for m N.
Assume that for some m 2 0, for Cm+1, we have:
Cm+1 S =
Then, we have
Cm 52" G VaCm-1
22 G Vo2m++3++ +
2 G
22 G + ?
2
G. (2 + 22/22+ +2-1)
$ G. G2 2 2
2
(22)
Therefore, by induction, have for all m 0,
Cm m G.
And the proof follows by setting O.
D DETAILED PROOFS FOR THE ONLINE SETTING IN SECTION
D.1 PROOF OF THEOREM
The following is the full proof of Theorem 1
For notational simplicity, throughout this whole section, we denote
H-1
:=
Σ
Σ
(V p. ya+
px (sh.
ke be[K-1]-6
IJ h=D
H-1
B = Σ
(V Virt ho (st,
ke [e[R-IJEE AED
Om== =
Σ
Σ
(V (Vir - v (sth,
h+1,5a
ke[K-1JAK A=0
19

---

Published as a conference paper at ICLR 2025
G =
Σ
(V Vaa
1: ) (of DE (V,S A,1/KH) log(K(Pl/0) log( K H)
[>K h=0
DE1 ( 8 A, 1/KH) log( K (P]
1 == E. (st V 1 (s')
V 1= (s%m.)
(23)
We use I(-) to denote the indicator function. We define the following events which we will later show that they happen with high probability.
k- H-1
= = (AKE [K- 1]: P PK and
Σ Σ
(s)
22 (Moog((PP)) (P//)))).
1-0 h-0
(24)
H-1 ke[K []
H-1
==
Σ
Σ
(Vp. Vat
ha at) log(1/0) 1og(1/0))
(25)
ka[K-1] -j h=U
KH ||]
& & {Ym [0. [log2(
O. s G vlog(1/0) Cm-1 + log(1/6)),
(26)
K-1 1-1
K-1
& = Σ
Σ
V
h-
(s a/t 2
Σ VaR, + log(1/6))
(27)
l=0
K-1
K-1 a
K-1
& Σ
Σ k=O
0:pa $
Σ
VaR,+ log(1/0) log(1/)))
(28)
k-0 h-1
kmw0
= & n E n E3.
(29)
First, by the realizability assumption, the standard generalization bound for MLE Lemma 9 with simply setting D, to be the delta distribution the realized (sf, at) pairs, and union bound over K episodes, we have that w.p. at least 1 6, for any k E [0, K 1]:
(1) P E PK: (2)
111 H P* (P*(ss (sh,
(30)
This directly indicates that
P(1{E1)) 2 21
(31)
Under event ε,, with the realizability in above (1), and by the optimistic algorithm design (, argmax Pe (Su), for any k E [0, K 1]. we have the following optimism guarantee
-
Vo, S
max VOL Vx* 04
xell,
Then, under event E,, we use Lemma 6 and Equation to get the following:
There exists set [K- - 1] such that
|C| 13l (oog2((81ogg) (88log( (PP1/)))H) SAA.://NDDDEEAAAAAAAA/CCCCAAACCS
And
#-1 Σ
Σ (P ( ab)
xe[R- 1j-k h=o
$ DE, (V,Sx x A, A,1/KH) (2+ log K (P|/6) log( K KH))+
$ DE, (V,S A, 1/KH) log( K PP] 10) (K log(KH) KH).
(32)
20

---

Published as a conference paper at ICLR 2025
We upper bound the regret with optimism, and by dividing ke [K - into K. and [K - 1] Æ with the assumption that the trajectory-win -wise cumulative reward is normalized in [0.1], as follows
Σ k=0
VoP.
Σ
Σ
r
k=0 h=1
H-1
$ |C| +
Σ
Vz
Σ r(shiaat)
0,
Ne(K-1]WE
h=0
( 0,
4-1
5 log (log( (log(K()) ( (P1//))KH) (V. DE
Σ
Σ
r(ts
ve[R-Ijx
h=0
(33)
We then do the following decomposition. Note that for any h: [K 1], policy n/ is deterministic. We have that for any &e E [K- -1] 1]
H-1
Fa (+0)
0.
Σ
H-1
(G) ab) (t) - Σ
r(bh,
hm0
H-1
= =r(s. + (() Vi
Σ
ah)
h-0
H
(s') = (at 1:pu (8))
Σ at)
h-1
H
= -Bg-P-(tt 1.px (8')=
Σ
r(( att) Pa 1,pa 11 (5') - (a V (ipe (5')
h-1
#-1
( (of)
Σ
r )
P i,pe (6') - VI 1,Be (1 (sf)
+ (B VT (5') By- (i
where we use the Bellman equation for several times. Then, by doing this recursively, we can get for any K [K- 1]
FT 0.
(5
Σ
(5
at
h-O
< Σ
1 + Σ
E
J (s)
Vo ot Va pe P- A (e))
(34)
h-O
h-O
Therefore,
H-1
Σ ke[R-1JvK
(V (stt)
(5h)
Σ ass)
h=0
H-1
H-1
S Σ
Σ
Σ
By at va' (x')) (e) (x (35)
ke[K-1JKC
ke[
1
K=D
Next we bound ΣkejK-IjKe 1j Σn I Note that by Azuma Bernstein's inequality, with probability at least 1 - 5
H-1
H-1 (Vr.
2 ) at) log(1/0) 1og(1/5) (36)
Σ ke|K-
Σ +
2
Σ
Σ
V
h-O
ke[K-1J<K
h-0
21

---

Published as a conference paper at ICLR 2025
This directly indicates that
P(L{E2)) 2 81
(37)
Then, we propose the following lemma.
Lemma 12 (Bound of sum of mean value differences for online RL). Under event E,, we have
H-1 Σ
Σ
E F (s)
Va* Te (5') - Eg (st Vaa Fht (6')
Ro[K- h=0
H-1
Σ
DEi (V.8 A.1/KH) (og( H) (V V= 1 [ at3
kE[K-1JJK
DE, x A, H/KH) log( K (P] log (H).
Proof of Lemma 12
Under event ε₁, we have
Σ
Σ
E
V (5)) E. (o (x)))
ke k-
k] h=0
H-1
<
Σ
Σ
(Vp V*c
1+ (s) Do Vitti, (s' P* ast)
Vi (8' Ph (sx (sxx aft))
ke[K-1] 11-1 h=0
H-1
+5
Σ
Σ
Do Vi P P' aii) vos
Ta (sh,
vI K-O
H-1
88 Σ
Σ
V
(V Voth M (sh Ht) york
(yrt h=:: (s' P (s att) ||
Volk h+ (s' ~ (5%
ke(K 1=]K- h-o
+0
Σ
Σ
H22 VTt po (6' P (shi att) || Va Ba (6' (shh
ke kq[K-IJ<K R=D
B-1
8 Σ
Σ
P- Vx* 1- Po )x) (5h at H2 P (P at) PR (st)
ke[K- |i A=0
#-1
+ 20
Σ
Σ
H2 (shh atd TA (Pthshottt)
ke K-
#-1
58
Σ
Σ
(V V*c
h- Ba ) (8t)
Σ
Σ
H2 Pr (s% att
PM att) ]
1o[K-IJvK 1JvK h=u
se[R-1] 1J h=0
+0
Σ
Σ
H'2 Pr (shh at) | PA (oh)
ke[K- NJ R=D
H-1
$
Σ
Σ
(VP. Vot pa (s at) ( Sx.KKX...AKK))) log K (P]/6) log( K HH)
kE]K-IJNE h-O
A, (V,
log K (P]/8) log(KH),
(38)
where in the first inequality, we use Lemma to bound the difference of two means (xp.t()).e)) V** 1m (s') Et .at)) 1= (5') using variances and the triangle discrimina- tion; in the second inequality we use the fact that that triangle discrimination equivalent to squared Hellinger distance, i.e., Da 4IH²; the third inequality is via data processing inequality on the
squared Hellinger distance; the fourth inequality is by the Cauchy-Schwaad inequality; the last inequality holds under &, by Equation 32
The next lemma shows that the event Eg happens with high probability.
22

---

Published as a conference paper at ICLR 2025
Lemma 13 (Recursion Event Lemma), Event Eg happens with high probability. Specifically, we have
K KH
((T(Es))2111 (1+ nogg(
G 1)).
(39)
Proof of Lemma 13] Let h+1 V h-1:77 h+1- First, under event ε with happens with probability
least 1 - 5 by Equation 31 and also note that nt is deterministic for any h: e [K 1], can prove the following
H-1
E Ba(K-IJKK h=0
Σ
I< (sh) (P' A (ch.
(40)
H-1
E
Σ
(1 (pp0))((PPPP))) (P'V VM he (s - - (P V (s%
kelk ke[K-1]yK A=0
#-1
Σ
Σ
a/t++ 1 ( at) ($ (P' V pm ) att r(sh af)) att1]
ke 1e[ 1=0
H-1
Σ
Σ
(F h+ ( (sti - (P' - ( )
ke|k 1/ AmO
111
Σ
Σ
yoa Vort (e E Pu / ie (5')
h-O
Σ kE|K-I|NK
Σ h=
(V Vot tt ( [ (V,, x A, log(K|Pl//) log( K H)
(
log K (P
-G where the first equality is by the definition of h+1 the inequality holds under & by Lemma 12 and the last equality is by definition of A and G.
(41)
Under event ε,, with probability at least 1 - |log2(
KH C
18, for any m [0. [lgg2(
KH
)]]
Cm = Σ
Σ
(VPr (V
hti,p v ")s))) (sh
ke(K ke[K-1]<K 0=0
H-1
Σ
Σ
(P' Am))) ) - ((P' 2M
ke[K-I]vE h=0
#-1
H-1
Σ
Σ
(A 2
Σ
Σ
((P'(AA (shh "]
h+ll
le[ A=U
Re[K-1]jxx h=D
H-1
+
Σ
Σ
(BmP((ofaa)) (4 2m (s) - (A (s
kef be[K-1JsK h=0
#-1
Σ
Σ
(A (AT)) 2
((P' 2 (s (shh
be[K-1live hmO
H-1 (B-P-(ot(a)) (A 2 (s)
Σ
-(A7t)) (st))
ke[K-1]NC
H-1
S Σ
Σ
(A 2m (0/) - ((P' )²th )"tti )² 21
(sth,att))
log
ke [o- h=0
Σ
#-1
Vv pr ((VT) (1 - Vir )2m+)) ) (st at) log
ke|K-1IJK hall
23

---

Published as a conference paper at ICLR 2025
Σ Σ
H-1
Σ ?( ( (P)) ((())))))((()))))) (s)) (sh)
+ Vlog(1/6) Cm+1 + log(1/6)
E
Σ
(s (s))
(skk,at)))))))))) (PP()(()()())) (ss (sh)
ke IR h=0
Vlog(1/6) Cm+1 log(1/6)
H-1
5 Σ
Σ [(AA)) + (P (stt)att))))))))))) (
k=[K- 1/ h=O
+
Vlog(1/6) Cm+1 + log(1/6)
H-1
2
Σ
/log(1/8) Cm+1 + llg((16)
ke(K-
R=0
H-1
=2 Σ
Σ
((Aa)))))))))))))))))))))) ((A)))()))))))) (P" (*t)
ke[K-1l h=0
+ (log(1//)
Cm+1 + llg((1/))
H-1
$ 2.2 Σ
Σ
1|4 (s (P' D (5 a vlog(1/6) Cm+1 log(1/6)
kE[K-IJ<K
A=0
$ G2 Vlog(1/0)))) (/0)- Cm.1 + log(1/6),
(42)
where in the first inequality change the index, the second inequality holds with probability at
least 1-6 8 by Azuma Bernstain's 's inequality, the third inequality holds because that E[x2" m-
1
[E[X]2** mm for m 2 1 and X 2 O, the fourth inequality holds by keep using a² -2 b)+ (a-b) b), then with E[X E[X]?, and the assumption that the trajectory-wise total reward is normalized in [0, 1]. the last inequality holds under Er by Equation 41 and we take a union bound to get
this hold for all m E [0, [logo( ( ] with probability at least 1 - [log2( K1l ) (x())
(because for each
[0g ( KH
G )1] we need apply the Azuma Bernstain's 's inequality once).
The above reasoning directly implies that
KH
P(I(8))) 21 (1+ floge(
1)8. G
(43)
Under the event Exe[K-IJsk EnI
Eg. va*
we
prove the following
lemma
to
bound
[V h+
Bx (s
at)
Lemma 14 (Variance Conversion Lemma for online RL), Under event Es, we have
H-1 Σ
Σ
(Vp- v
KefK-IJve h-0
H- Σ
s s0(
Σ
V (st DE, ( -log( (K (P)/0) log//))og((F))) (gg(KH)
ke[K-1|<K
haO
Proof of Lemma 14
Under Eg, we have for any m E [0, [log (KH) )]
Om ST G Vlog(1/0) Cm+1 log (106).
(44)
Then, by Lemma 11
we have
Co $ G.
(45)
24

---

Published as a conference paper at ICLR 2025
Also note that we have A s 2B 2Co since Vp (a+ 22p (a) p (6). Therefore, we have
s 2B 2Co
& B + G
B + / DE, ( A,1/KH) -log( K (P1/))))g((HH))
(V,,V, 1, log( (P)/)) (og(H))))))))))))
(46)
Then, with the fact that 20 + b² if x aa byzz, we have
As 0 B + DE, (V, A,1/KH) log( K (PI/0) log (o((K))
(47)
which is
H-1
Σ Σ
(Vp. v h+1: (sh oft]
kE[KKIJvV h-)
H-1 Σ
Σ
(Vpr (
DE, (V,, A,1KK)) log KH)
ke[K ke[K-1jKK h=0
(48)
By the same reasoning in Lemma 26 of Zhou et al. (203)) 3. we have that with probability at least 1
H-1 Σ
K-1 H-1
Σ
(V
Vir h+1
(s ah:
Σ
(V p. V (s), att
ke[K-1]uK
h=0
k=0 h=o
s 0
Σ
VaR log((16)))
(49)
k-0
This indicates that
P(T(ET)) 21
(50)
We can use the Azuma Bernstain's 's inequality to get that with probability at least
K-1
a - K-1
Σ
r
Σ Var $
VaR log(1/8) log(1/6)
(51)
This indicates that
P(1(E()) 2 1-
(52)
Then, together with Lemma 13 Equation 31 and Equation 37
we have
KH 1-
P(({E)) 2 1- (5+ 15 [log2(
(53)
Finally, under event 8, with all the things above [Equation 33 Lemma 14), we have
Equation 35
Equation 36 Lemma 12
K-1
K-1
Σ Vū.p-
Σ
Vorp-
k-O
K-1
K-1
K-1 H
K-1 yzt
=
Σ Vi.p. Σ
Σ
( ottt+
+ Σ Σ
rs
k
Σ
k=O A=1
k=0
H-1
K Σ
$ |K]++
Σ
Vx*
0:
Σ ((h
+
VaRg log(1/5) log(1/8)
ke[K-
(vat
H-1
$ log
(lgg
(K(P/8))H)) (V, A (P/)))())))))))
Σ
0,
Σ
r(st
ke[K-1JuK
h=0
25

---

Published as a conference paper at ICLR 2025
K
+a log(1/6) log(1/6)
$ log" (log( K (P|/8)KH) (V, (K) log(1/0)
#-1
K-1
Σ
Σ
(VP.v
he (s) (10)(11))))
log(1/6)
Σ VaRza log (16)
ke[K-IJuK
h=0
Σ
(ippa(s) (8)) (st V v E C L.pa
(T) (s)
kef K-1| -/ h=0
K-1
$ log" (log( (P)/6)KH) A
Σ km
VaR log(1/8) log
#-1
Σ
Σ
(VP. (5 DE
A.1/KH) ( lPg( (xx log
kef ke[K-11<K h=0
#-1
Σ
Σ
(tt ( (agl////)-oo/(PPPPP (P/)
ke[K-1juK
$ log" (log( (log(K(P|/6)KN))) (DA.
VaR, log(1/6) log(1/6)
k=0
#-1 Σ [VV |4 (/0
Σ
(V,,
log(1/6)
ke[K-1J<K MJ h=0
#-1
Σ
Σ
( (V.5..... lo
VK ke[K-1] K l==
DE VVSS A, 1/KH) log( (P))
K-1
$ log
bogg(log (log( (PI16))H1) A
Σ
VaR log(1/0) log(1/6)
K-1
Σ VaR log(1/6) + DE,
log( K (PP)/5) (ogg(H))))))))))))))))))(()))( log(1/6)
R-0
K [P]
Σ VaR=+ + log
+ DE,
V.S x A,
-log
log K (K))
KH
5
1=0
K KP
DE
V.S A.
log
log ()
KH
s 50(1
VaR DE, (V,S A, 1/KH) log( (K (P1/8) log(KH)
K-O
DE, (V,S A. 1/KH) log( K (og))))
(54)
The final result follows by replacing be 8/(5KH) to make the event E happen with probability least 1 8.
26

---

Published as a conference paper at ICLR 2025
D.2 PROOF OF COROLLARY
Proof of Corollary 2 By Lemma 8 we have
H-1
VaR & Σ
E
(V V Vs.i)
(55)
s.and
k=D
Therefore, when P is deterministic, the E s.a-dR (VP. h+t1 (s, terms all 0 for any &
[K and h [H- 1], and then the Σk=0 VaR term in the higher order term in Theorem
0.
D.3 PROOF OF COROLLARY
Proof of @ooolllryy 3]
We follow the MLE guarantee for the infinite model class in Lemma 10 and
the same proof steps in the proof of Theorem Iin Appendix D.I
E DETAILED PROOFS FOR THE OFFLINE RL SETTING IN SECTION 5
E. PROOF OF THEOREM 2
The following the full proof Theorem 2
First, by the realizability assumption, the standard generalization bound for MLE Lemma 9) with simply setting D; to be the delta distribution the (s af) pairs in the offline dataset D, we have that w.p. at least 5::
Proof of Theorem 2
(1) P E P;
(2)
Σ Σ H' (5 (s a;)) log([o([))))) k-1 h-O
(56)
K
K
Then, with the above realizability in (1), and by the pessimistic algorithm design â argmax min minpes paP V (s)), P argmin ped V (so), we have that for any n² II
V.P. V.P.
Va*
VT
0:B
Vx
0.P
V
s F
VT
+ V
V
0:P
0,P
1/ < 0.p-
0:F
(57)
We can then bound Vo Va"
using the simulation lemma Lemma
0:P
H-1
V
V
Σ
Eg-P (x.a) V (s') (..PP(ss) V""
(58)
0.B
h=0
Then, we prove the following lemma to bound the RHS of Equation 58
Lemma 15 (Bound sum of mean value differences for offline RL). With probability at least
have
Σ
E
[E
VT (s') E ((.ee) V VIT [
#-1
22C'*' log(1Pl/0)
4400T log (P)/))
Σ
E
[Vvm Va (s,
K
h=0
27

---

Published as a conference paper at ICLR 2025
Proof of Lemma 15,
We have
H-1
(e. V (ol))(00)) ((, V [
s.andz
H-1
saand [V (V Vx
< 4
R
Va. h0 (s) (i
(r)),a)) Vx 1= P(s.a)))
H-1
5
E Bsaand
(Da V (' P'(,aa)
V h P(s,a)))
H-1
s.a-d [V (Vrr Va-
$ <8
Σ
E
(s, ( h0 (s)p(=)
V
hn P(s,a)))
H-1
20
Σ
E
spand
PM (s, V Vi P(s.a)))]
A=U
$
H-1
Σ
E
s.
(VV (e ((( (*))))) || P(s.a)) + 20
H-1
Σ h=0
E
IHP
(P((PP()))))
P( P(s.a))]
(59)
where in the first inequality, we use Lemma (x-P"(s.a) Va h- (s') -.y.-((s.a) 1 second inequality we use the fact that that triangle discrimination is equivalent to squared Hellinger distance, i.e., Da 4IH?: the third inequality is via data processing inequality on the squared Hellinger distance. Next, starting from Equation 59 with probability at least 5, we have
bound the difference of two means Vx* (ss') using variances and the triangle discrimination; in the
8
H-1
Σ
E
(VVoo.iti ((, (Pt,,) (*(
P(s.a))
+ 20
H-1
Σ h=0
B
[HF((P'(s,))) ((s,,))]
A=0
H-1
H-1 h=:1;)) (o..))
$ 8
Σ
E
8,a-d
Vx [
Σ
E
s.ard
HP (s,()) (
h+
h=0
A=0
H-1
20
E ga
H Pr (s) P(s,a))]
#-1
1 K H-11
8
Σ
E
a,--d;"'
[(Vp.Vei (s,a) C+
Σ Σ (ft
K
K
H-1
Σ
H (s (Psh
k=1
h=0
H- Σ
22C log([P)/5 15) 440C" log log([P)/8)
<
E h-0
[Vvp. V h+ v) a)
(60)
K
where the first inequality is by the Cauchy-Schwarz inequality; the second inequality is by the definition of single policy coverage (Definition 3); the last inequality holds with probability at least 1 1-8 8 with Equation 56 Substituting Equation 60 into Equation 59 ends our proof.
We denote E the event that Lemma 15 holds. Under the event E, prove the following lemma to bound #I- E, R. (Vp. V (s, with Ö(Σll)) E s. [VVp. (s,)
CFa log((P//0)/K)
Lemma (Variance Conversion Lemma for offline RL). Under event E, we have
H-1 Σ h=0
H-1
[ (zi)) -0=² loo((PP//))
E Eg
[VVp. var
s (s,
Σ
E s
K
h=0
28

---

Published as a conference paper at ICLR 2025
Proof of Lemma 16,
For notational simplicity, we denote A := EnHo E, Bs [(V p. V
h- (s,a)
and we denote
B = Eneo s. [VVp V (3, C En=o I E s.add"" [[Vp. (V h+i;5 Vir (s, then
(Va)
we have
A s 2C,
since
Vp (a+ b) 22 (c) p.
Let A h+1
V h-1:5
Vi Then, w.p. at least 1 - 6, we have
1-1
Σ
E
[P'' ( (2 - A (P')),)))
4,a-1
Σ
E
(Ant)))(s)
Σ
x.
[(P'
h=0
h=0
H-1
Σ
E
(()) -(P-(((P))) (P' 1))
s,a-a
h=O
(61) where the first equality by the definition of variance, the second equality holds as dī. is the occupancy measure also generated under P" the first inequality is just changing the index, the third equality holds as a² -b2 (a+ b) (a- - 6). Starting from Equation 61 we have
Σ
E
[((4)) (P'A ((4))
-P'A
h-0
H-1
Σ E
s.and
[1(4%) (ss) (P' A (s.,)) (s) (AA))
H-1
< 2
E
s.a-d //
(4, (s) (P'))((P''
(P'' (s,a))
h=0
H-1
((VTT))) - - (s) -PVVti)))
2
E
s.a-d5" //
h=0
2
H-1
Σ
B
Bs [[((s,0)=
( - (s..
h=0
H-1
2 B Bra-dd (s))) (P'V (P.
Σ
(62)
where the inequality holds as the value functions are all bounded by by the assumption that the total reward over any trajectory is bounded by 1, the first equality is by the definition of A the second equality is because a is drawn from π Starting from Equation 62 we have
H-1
2
Σ
E
[ (i - (P' V ViTi.))
H-1
2
E
V [60)
E (-)P()))
16
H-1
Σ
E
Be
[(Vp. Vor
(o.o))
220** log([P)/6)
8800"
log (PPl/ (P))
K
K
h=0
A 22 log((P)/))
880C""
log((P)/1 15)
= 1
(63)
K
K
where the inequality holds with probability at least 5 by Lemma 15 and the second equality is by definition of A.
Then combining Equation 61 suggests
Equation 62 and Equation 63 we obtain upper bound for C, which
A 2B 2C
29

---

Published as a conference paper at ICLR 2025
2BB 1760C" log((P1/6)
22C log( log(1P)/3 (PP1())
+ +2
VA.
K
K
Then, with the fact that 2a + ba if s a by have
3520C log( (P] 18) 22528C* log((PI/0)
C* (og((P//0)
A s 4
O(B+
K
With the above lemmas, we can now prove the final results of Theorem
We have that w.p. least
1 1-6
A. C log((Pl/0)
Cx" log((PI/6)
Vo... s0(v
0.p.
K
K
(B Cx'
log([P1/8)
C** log([P//
O log((P1/0)
$ $0(1
+
K
K
K
C'T log((P100)
C log( log((P) (P|/0) 18)
C log((Pl/0)
C Log([P)/6))
$ 50(v
B.
K
K
K
C"" log([P1/0)
C log((P1/0)
= 0
Σ
[(V p- Vir (s.
K
K
h=0
(64)
VaR C* log log((P)/))
C log(1P1/0))
= [V
K
)
27
where in the last equation we use Lemma & and VaR.. == E
Ehh r(sh. x- (8:)) (ss)) Vo¹)
E.2 PROOF OF COROLLARY 4
Proof of Corollary 4 By Lemma 8 we have
#-1 Σ
VaR,
E
(65)
h-o
Therefore, when P* is deterministic, the E s.
terms are all 0 for any k
[K 1] and h H 17111, and then the VaR,, term in the higher order term Theorem is
E.3 PROOF COROLLARY 5
Proof of Corollary 5 This claim follows the proof of Theorem 2 while we take different choice of
B3 that depends on the bracketing number and follow the MLE guarantee in Lemmma 10 for infinite model class.
E.4 PROOF THE CLAIM IN EXAMPLE
Proof. Recall that in Definition 3
we have
E Ex HP? (P(s, P" P*(ssa))
CH
max N.P
E/KE K H2 (P() att Pr at))
For each step ht define two distributions, Ph. the where (s()a d= (s,a), (1(8))) 1 IK (() (sf, a and we define f(s, a, P) HP(((s,a) || p*(sa))), then we have
K
Ega-pa Ps
CD = max
h, PeP Egaagg f a, P)
30

---

Published as a conference paper at ICLR 2025
B pa(sra)
(a(a f(s,0, P)
PeP
Bx (8, P)
(s,
max
h,s,a 9h ()
2 max ())
(66)
) Note that for all h, { 2 k== are i.dd samples drawn from d therefore, B[I at)
(s,a)} di (s, By Hoeffding's inequality and with a union bound over 8, a, h, and for 2log( (S1AiM)
K 2
w.p. at least 1 6, we have
Pona
1 Σ (n(
(( as
K
log( /I|A
dh (s,
2K
dh (8,a)
(67)
where the last inequality we use the assumption that d (s, 2 Punnn as, h, which gives us K' 2oog (SIA
20og(
(SILA
so K 2 (SILAIH
P
m,
(d (s.a))²
(s,a))
for any s, a, h.
Therefore, with K 2log( (SLAIR
we have that w.p. at least 1 5
Pain
2
S max
S max n,0,a d (8, Pmin
(68)
0,2,0 qh (8,
31


Reviews:
[{"review_id": "UpeVLi1xp5", "reviewer": "Reviewer_ttab", "summary": "This paper proposes a minimalist approach to Model-Based Reinforcement Learning (RL) that leverages Maximum Likelihood Estimation (MLE) for learning transition models and integrates optimistic and pessimistic planning. The proposed scheme achieves strong regret and sample complexity bounds in both online and offline settings. It also provides nearly horizon-free and second-order bounds under certain conditions.", "questions": "1. As I have mentioned in (2) in weaknesses, can you compare your horizon-free results with [1,2]?\n\n2. The paper discusses the use of MLE for transition modeling. How does this choice impact the trade-offs between computational efficiency and the accuracy of the learned model in comparison to other model learning techniques (e.g., Bayesian approaches)?\n\n3. How does the use of MLE for model learning affect the sensitivity of the model to noise in the environment, particularly in settings where the transitions are stochastic or partially observable? Can the methodology be adapted to handle such cases without compromising the theoretical bounds?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The authors provide solid theoretical analysis.\n\n2. The methodology stands out due to its simplicity. The authors focus on using standard techniques (MLE, version space, optimistic/pessimistic planning) without introducing complex or specialized methods.", "weaknesses": "1. While the paper mentions the simplicity and standard nature of the algorithm, it lacks a direct comparison with other recent state-of-the-art Model-Based RL methods. A more explicit comparison would help highlight the contributions and potential advantages of this approach.\n\n2. While the paper emphasizes it provides a nearly horizon-free result, I do not think it is a novel contribution with the assumption $r(s_h, a_h) \\in [0,1 / H]$. I am more interested in approaches of [1,2], which also remove $\\log T$ in their regret bound. Can you compare your work with these two papers? \n\n3. The theoretical conclusions of this article are too dense and lack discussion.\n\nReferences:\n\n[1] Zhang, Zihan, Xiangyang Ji, and Simon Du. \"Horizon-free reinforcement learning in polynomial time: the power of stationary policies.\" Conference on Learning Theory. PMLR, 2022. \n\n[2] Li, Shengshi, and Lin Yang. \"Horizon-free learning for Markov decision processes and games: stochastically bounded rewards and improved bounds.\" International Conference on Machine Learning. PMLR, 2023.", "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": "QAWh5eTqWn", "reviewer": "Reviewer_dSXD", "summary": "This paper presents a minimalist model-based RL approach focused on achieving horizon-free and second-order bounds in both online and offline RL contexts. The authors advocate for using MLE for transition model learning, combined with optimistic planning in online RL and pessimistic planning in offline RL. The primary theoretical contribution is demonstrating that this straightforward MLE-based approach, which doesn’t require complex, variance-weighted learning procedures, achieves near-horizon-free sample complexity and second-order regret bounds. The analysis shows that this approach is effective in handling scenarios with either non-linear function approximations or time-homogeneous, low-variance policies, which benefit from the instance-dependent nature of second-order bounds.", "questions": "1. Given that the current approach is theoretically sound but may be computationally intense, are there approximate methods that could retain accuracy while reducing computational demands?\n\n2. What are the implications if the assumed model class does not include the true dynamics of the environment? Could the algorithm's performance degrade, and if so, how might this be mitigated?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical results show that performance does not heavily depend on the planning horizon, making this approach comparable to contextual bandits in complexity. The second-order bounds, scaling with policy variance, are particularly advantageous for nearly deterministic systems or policies with low variance.\n\n2. The approach is designed to be versatile, working effectively in online, offline, and hybrid settings.", "weaknesses": "1. While the approach is theoretically sound, its reliance on computationally intensive MLE optimization could hinder scalability for larger or more complex model classes. To address this, it may be valuable to explore specific approximate MLE methods, such as variational inference or stochastic optimization. Alternatively, a discussion of computational complexity trade-offs could provide further clarity and practical guidance.\n\n2. The paper presents strong theoretical contributions, but the lack of empirical validation on challenging RL tasks limits its practical impact. It would be helpful to evaluate the approach to environments such as tabular MDPs. Including such experiments would significantly strengthen the paper’s practical contributions.", "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": "TNb8HJwLWx", "reviewer": "Reviewer_6vxv", "summary": "This paper identifies minimalist reinforcement learning (RL) algorithms that can achieve nearly horizon-free and instance-dependent regret and sample complexity bounds,in both online and offline RL with non-linear function approximation. Based on a leverage of triangular discrimination, it demonstrates that existing standard model-based RL algorithms, using maximum likelihood estimation (MLE) for model learning and optimistic or pessimistic planning depending on the setting (online or offline), are sufficient to achieve these performance goals.", "questions": "1. Are the assumptions listed on page 4 and in Definition 3 the only ones required for Theorem 2? I’m curious about this, as I would like to gain a better understanding of the factors contributing to the improved results compared to [1].\n\n2. What do you think is the key barrier when attempting to apply a similar analysis to model-free methods? This question is not necessary to be replied.\n\n[1] Uehara, M., & Sun, W. (2021). Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper explores horizon-free reinforcement learning (RL) within the context of general function approximations, which is a more challenging and generalized setting compared to prior work on tabular or linear MDPs. Theoretical analysis is solid, leveraging triangular discrimination to demonstrate that existing standard model-based algorithms can already achieve horizon-free regret. This analysis could be inspiring for future research in horizon-free RL. Furthermore, the paper provides a second-order instance-dependent upper bound, which can be particularly tight when the variance is low, yielding improved sample complexity in deterministic environments. Finally, the writing is logical, with ideas presented smoothly.", "weaknesses": "It's clear that this paper is purely focused on theoretical contributions. I think the primary weakness is the lack of intuitive insight into how triangular discrimination specifically assists in achieving horizon-free and second-order upper bounds. Although a proof sketch is provided, the underlying intuition remains somewhat unclear. A discussion on this would be appreciated.", "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": "dTNEU4EfMR", "reviewer": "Reviewer_XvPg", "summary": "The paper studies model-based RL in MDPs with possibly infinite state-action spaces and total returns bounded in [0,1]. The authors show that a simple approach consisting of learning a version space around the MLE of the transition kernel and performing optimistic/pessimistic planning on top of it achieves strong horizon-free and second-order bounds in online/offline RL.", "questions": "1. See clarification questions above\n2. The bound in Example 1 for tabular MDPs seems to have a worse dependence in SA that existing bounds for the same setting (see eg Jin et al. 2020 or Appendix C in Al-Marjani et al. 2023) despite having a better dependence in H. Any intuition why this happens?\n\n[Jin et al. 2020] Jin, C., Krishnamurthy, A., Simchowitz, M., & Yu, T. (2020, November). Reward-free exploration for reinforcement learning. In International Conference on Machine Learning (pp. 4870-4879). PMLR.\n[Al-Marjani et al. 2023] Al-Marjani, A., Tirinzoni, A., & Kaufmann, E. (2023, July). Active coverage for pac reinforcement learning. In The Thirty Sixth Annual Conference on Learning Theory (pp. 5044-5109). PMLR.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper presents novel and strong results. To my knowledge, the ones studied here are the simplest algorithms to be shown to achieve both horizon-free and second-order bounds (eg, most prior works required specific algorithmic tweaks to this purpose). Due to the popularity of MLE-based approaches, I think this is a relevant result\n2. The paper studies both the online and offline RL settings\n3. I particularly appreciated the corollaries for MDPs with deterministic transition kernel, which I think is an understudied setting despite its practical relevance\n4. Although I only skimmed through the proofs, they do seem sound\n5. Relevant literature is properly discussed", "weaknesses": "1. My main concern is that the paper is quite hard to follow, extremely technical, and lacks some clarity in many points. More precisely, the paper is basically a list of theorems/lemmas/corollaries/definitions without too many explanations: several terms that may only be familiar to experts in this line of works are not introduced with sufficient detail and many choices are not motivated. For example,\n- it is not clear why the assumption that trajectory returns are in [0,1] is reasonable in practice\n- for offline RL, it is not clear why the assumption that the dataset contains trajectories is needed (lines 181-191). Can't you have only transitions?\n- the definition of Eluder dimension is not clear (eg what's an epsilon-independent sequence?). It is clearer in prior works\n- not clear why the bounds use the function class \\Psi defined at lines 258-259. Eg, why not using P itself, which after all is the hypothesis space used for learning?\n- In Section 4, it is never explicitly stated that the results before the paragraph \"Extension to infinite class P\" focus on finite P (the reader has to figure it out from the definition of beta)\n- not clear why using bracketing numbers in the analysis. Eg how do they compare to the more standard covering numbers (if there is any difference)? Also, it be great to give examples of what those are for \"common\" function classes (eg when P is linear)\n- not clear how the \"single-policy coverage\" of Def. 3 compares to the more standard concentrability coefficients defined as ratios between policy visitation distributions used in the offline RL literature\n2. The algorithms studied here are both intractable due to the fact that they have to build a version space of transition kernels around the MLE. This is only tractable for simple function classes (eg finite) and limits the practical relevance of this work. Also, I feel this breaks a bit the overall story about the \"simplicity\" of the approaches. Eg, the conclusions state \"we presented a minimalist approach for achieving nearly horizon-free and second-order bounds in online and offline RL: simply train transition models via Maximum Likelihood Estimation followed by optimistic or pessimistic planning\", but I don't think this is properly correct: it gives the impression that all we have to do is MLE, but we do have to build version spaces around it, and that's not an easy thing.\n3. Lines 171-172: \"Without loss of generality, we assume V \\in [0,1]\". I don't think this is without loss of generality, as the filtering approach proposed in footnote 2 would require doing policy-evaluation for many policies and transition kernels, which is what we want to avoid during training in the first place with an MLE approach\n4. [minor] the abstract is very verbose, and I felt many details could have been omitted without altering its quality", "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)