Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs

Authors: davide  maran
alberto maria metelli
matteo  papini
marcello  restelli
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 15:04:24

Abstract: Achieving the no-regret property for Reinforcement Learning (RL) problems in continuous state and action-space environments is one of the major open problems in the field. Existing solutions either work under very specific assumptions or achieve bounds that are vacuous in some regimes. Furthermore, many structural assumptions
    are known to suffer from a provably unavoidable exponential dependence on the time horizon $H$ in the regret, which makes any possible solution unfeasible in practice. 
    In this paper, we identify _local linearity_ as the feature that makes Markov Decision Processes (MDPs) both _learnable_ (sublinear regret) and _feasible_ (regret that is polynomial in $H$). 
    We define a novel MDP representation class, namely _Locally Linearizable MDPs_, generalizing other representation classes like Linear MDPs and MDPS with low inherent Belmman error. 
    Then, i) we introduce **Cinderella**, a no-regret algorithm for this general representation class, and ii) we show that all known learnable and feasible MDP families are representable in this class. 
    We first show that all known feasible MDPs belong to a family that we call _Mildly Smooth MDPs_. Then, we show how any mildly smooth MDP can be represented as a Locally Linearizable MDP by an appropriate choice of representation. This way, **Cinderella** is shown to achieve state-of-the-art regret bounds for all previously known (and some new) continuous MDPs for which RL is learnable and feasible.

Main paper: 
 introduction: 
 Reinforcement learning (RL) [35] is a paradigm of artificial intelligence in which an agent interacts with an environment, which is typically assumed to be a Markov Decision Process (MDP) [30] , to maximize a reward signal in the long term. By interacting with the environment, an RL algorithm tries to make the agent play actions leading to the highest possible expected reward; RL theory is the field that designs algorithms to be provably efficient, i.e., to work with probability close to one. This idea is formalized in a performance metric called the (cumulative) regret, which measures the cumulative difference between actions played by the algorithm and the optimal ones in terms of expected reward.For the case of episodic tabular MDPs, when both the state and the action space are finite, an optimal result was first proved by [4] , who showed a bound on the regret of order O( H 3 |S||A|K), where S is the state space, A is the action space, K is the number of episodes of interaction, and H the time horizon of every episode. This regret is minimax-optimal in the sense that no algorithm can achieve smaller regret for every arbitrary tabular MDP. This result is not useful in many real-world scenarios, where S and A are huge, or even continuous [20, 19, 15] . In fact, all applications of RL to the physical world, like robotics [20] and autonomous driving [19] , have to deal with continuous state spaces. Furthermore, the most common benchmarks used to evaluate practical RL algorithms [36, 7] have continuous state spaces.One of the first studied families of MDPs with continuous spaces is the Linear Quadratic Regulator (LQR) [5] , which goes back to control theory. LQR is a model where the state of the system evolves according to linear dynamics, and the reward is quadratic. Regret guarantees of order O( √ K)for this problem were obtained by [2] (with a computationally inefficient algorithm) and, then, by [12, 9] . Still, this parametric model of the environment is very restrictive and does not capture the vast majority of continuous MDPs. A much wider and non-parametric family is given by Lipschitz MDPs [31] , which assume that bounded differences in the state-action pair (s, a) correspond to bounded differences in the reward r(s, a) and in the transition function p(•|s, a) (e.g., in Wasserstein metric). Lipschitz MDPs have been applied to several scenarios, like policy gradient methods [29, 3, 28] , RL with delayed feedback [22] , configurable RL [27] , and auxiliary tasks for imitation learning [11, 26] . While this model is very general, its regret guarantees are weak, both in terms of dependence on K and on H. In fact, very recently, [25] showed a regret lower bound of order Ω(2 H K d+1 d+2 ), where d is the dimension of the state-action space, which makes this family of problems statistically unfeasible.Another part of the literature has focused instead on representation classes of MDPs. In this paper, we call "representation class" a family of problems that depend both on an MDP and on an exogenous element, usually a feature map. One example can be found in the popular class of Linear MDPs [40, 18] , which assumes that both the transition and the reward function can be factorized as a scalar product of a known feature map ϕ of dimension d ϕ and some unknown vectors. Regret bounds of order O(H 2 d 3/2 ϕ √ K) are possible [18] , which succeed in moving the complexity of the problem into the dimension d ϕ of the feature map. Unfortunately, this representation class is very restrictive: i) linearity is assumed on both the p h and r h functions; ii) the same linear factorization must be constant along the state-action space S × A, which goes in the opposite direction w.r.t. the locality principle introduced by Lipschitz MDPs. The first issue is solved by [42] , which significantly extends this class of process by assuming linearity on the Bellman optimality operator, which turns out to be much weaker. This representation class is known as MDPs with low inherent Bellman error, a generalization of linear MDPs that further allows for a small approximation error I.Very recently, different kinds of assumptions for continuous spaces were introduced. In Kernelized MDPs [41] , both the reward function and the transition function belong to a reproducing kernel Hilbert space (RKHS) induced by a known kernel coming from the Matérn covariance function with parameter ν > 0. The higher the value of ν, the more stringent the assumption, as the corresponding RHKS contains fewer functions. This kind of assumption enforces the smoothness of the process, which is stronger for higher values of ν. A generalization of this family can be found in Strongly smooth MDPs [25] , which require the transition and reward functions to be ν-times continuously differentiable. Although it is a wide, non-parametric family of processes, enforcing the smoothness of the transition function is rather demanding as it implies that the state s ′ is affected by a smooth noise. For this reason, [25, 24] also defines the larger family of Weakly smooth MDPs, which only requires the smoothness of the Bellman optimality operator. This model is extremely general, as it can also capture Lipschitz MDPs. Still, for the same reason, it is affected by an exponential lower bound in H. Lastly, note that for the last three kinds of MDPs, Kernelized, Strongly and Weakly Smooth, the best-known regret bounds are linear in K for some values of d and ν. As the regret is trivially bounded by K, these bounds are vacuous, not guaranteeing convergence to the performance of the optimal policy. Our contributions. In this paper, we argue that the aspect that makes many continuous RL problems both learnable and feasible is local linearity, i.e., the possibility to locally approximate the MDP as a process exhibiting some sort of linearity for a well-designed feature map. To support this thesis, in the first part of the paper, (i) we introduce Locally Linearizable MDPs, a novel representation class of MDPs depending on both a feature map ϕ h and a partition U h of the state-action space of the MDP. This class generalizes both LinearMDPs and low inherent Bellman Error while also allowing the feature map to be local. (ii) We design an algorithm, CINDERELLA, which enjoys satisfactory regret bounds for this representation class. In the second part of the paper, we explore how this approach can be compared to the state of the art on continuous MDP; (iii) we show that all families all families that were defined in the continuous RL literature, to the best of our knowledge, for which learnable and feasible RL is possible are included in a novel family of Mildly Smooth MDPs defined in this paper; (iv) we show that this family is, in turn, a special instance of our Locally Linearizable MDPs representation class, for an appropriate choice of the feature map. Therefore, CINDERELLA can be applied to learning on all these families of continuous MDPs. (v) we finally prove that the regret bound of CINDERELLA outperforms several state-of-the-art results in this field.2 Background and set-up Markov Decision processes. We consider a finite-horizon Markov decision process (MDP) [30] M = (S, A, p, r, H), where S is the state space, A is the action space,1 p = {p h } H-1 h=1 is the sequence of transition functions mapping, for each step h ∈ [H -1] := {1, . . . , H -1}, a pair z = (s, a) ∈ Z to a probability distribution p h (•|z) over S, while the initial state s 1 may be arbitrarily chosen by the environment at each episode; r = {r h } H h=1 is the sequence of reward functions, mapping, for each step h ∈ [H], a pair z = (s, a) to a real number r h (z), and H is the horizon. At each episode k ∈ [K], the agent chooses a policy π k = {π k,h } H h=1 , which is a sequence of step-dependent mappings from S to probability distributions over A. For each step h ∈ [H], the action is chosen as a h ∼ π k,h (•|s h ) and the agent gains reward of mean r h (z h ) and independent on the past, then the environment transitions to the next state s h+1 ∼ p h (•|z h ). For a summary of this notation see A.Value functions and Bellman operators. The state-action value function (or Q-function) quantifies the expected sum of the rewards obtained under a policy π, starting from a state-step pair (s, h) ∈ S × [H] and fixing the first action to some a ∈ A:EQUATIONwhere E π denotes expectation w.r.t. to the stochastic processa h ∼ π h (•|s h ) and s h+1 ∼ p h (•|z h ) for all h ∈ [H]. The state value function (or V-function) is defined as V π h (s) := E a∼π h (•|s) [Q π h (s, a)], for all s ∈ S. The supremum of the value functions across all the policies is referred to as the optimal value function:Q ⋆ h (z) := sup π Q π h (z) for the Q-function and V ⋆ h (s) := sup π V π h (s) for the V-function.In this work, as often done in the literature [43] , we make the following Assumption 1. The instantaneous reward minus its mean r h (s, a) is 1-subgaussian, and normalized so that 0 ≤ Q π h (z) ≤ 1 for every policy π, z ∈ Z and h ∈ [H].Passing to the case where the per-step reward is in [0, 1] requires multiplying all upper bounds by H.An explicit way to find the optimal value function is given by the Bellman optimality operator, which is defined, for every function f :Z → R, as T h f (s, a) := r h (s, a) + E s ′ ∼p h (•|s,a) [sup a ′ ∈A f (s ′ , a ′ )] .In fact, it is easy to show that Q ⋆ h = T h Q ⋆ h+1 at every step, while the optimal state-value function is obtained simply as V ⋆ h (a) = sup a∈A Q ⋆ h (s, a).2 Agent's regret. We evaluate the performance of an agent, i.e., of a policy π k played at episode k ∈ [K], with its expected total reward, i.e., the V-function evaluated in the initial state V π k 1 (s k 1 ). The goal of the agent is to play a sequence of policies {π k } K k=1 to minimize the cumulative difference between the optimal performance V ⋆ 1 (s k 1 ) and its performance V π k 1 (s k 1 ), given the initial state s k 1 chosen by the environment. This quantity takes the name of (cumulative) regret,R K := K k=1 V ⋆ 1 (s k 1 ) -V π k 1 (s k 1 ). This quantity is non-negative, and by the normalization condition, we can see that it cannot exceed K as every term in the sum is bounded by 1. Note that if R K = o(K), then the average performance of the chosen policies will converge to optimal performance. An algorithm choosing a sequence of policies with this property is called no-regret.Representation classes of MDPs. As anticipated in the introduction, we call "representation class" a family of MDPs that is defined through its relation with a feature map or another exogenous element. While the most popular representation class is the Linear MDP, assuming the exact factorization of both p h and r h , no-regret learning is possible for a much wider family, only requiring a form of approximate linearity on the application of Bellman's optimality operator. This class was introducedZ 1 Z 2 Z 4 Z 2 Z 3 Z 1 S A (a) Qh[θ ′ ] ThQh+1[θ] d (b)Figure 1 : In Locally Linearizable MDPs, we have that, as shown in (a), the space Z is partitioned into several regions, which do not need to be convex nor connected. On each of these regions, as shown in (b), the result of the Bellman optimality operator can be well approximated by a Q function that is linear in the feature map, with a parameter θ that may depend on the region itself. by [42] as MDPs with low inherent Bellman error. Given a sequence of compact sets B h ⊂ R d ϕ , and calling Q h [θ](s, a) the linear function ϕ h (s, a) ⊤ θ, the inherent Bellman error w.r.t. {B h } h is defined as:EQUATIONwhere the supremum norm ∥ • ∥ L ∞ indicates the maximum of the function in absolute value over Z. In the realizable case (i.e., I = 0), these processes are a strict generalization of Linear MDPs [42] .To achieve regret guarantees for continuous state-action MDPs that go beyond this linear case, we will need to borrow some concepts of smoothness from mathematical analysis, as presented below.Let Ω ⊂ [-1, 1] d and f : Ω → R. We define a multi-index α as a tuple of non-negative integers (α 1 , . . . α d ). We say that f ∈ C ν (Ω), for ν ∈ (0, +∞), if it is ν * -times continuously differentiable for ν * := ⌈ν -1⌉, and there exists a constant L ν (f ) such that:EQUATIONthe multi-index derivative is defined asD α f := ∂ α 1 +...+α d ∂x α 1 1 ...∂x α d d. The previous set becomes a normed space when endowed with a norm ∥f ∥ C ν defined asmax max |α|≤ν * ∥D α f ∥ L ∞ , L ν (f ) . Note that, when ν ∈ N, this norm reduces to ∥f ∥ C ν = max |α|≤ν ∥D α f ∥ L ∞ , since the Lipschitz constant L ν (f )of the derivatives up to order ν * = ν -1 correspond exactly to the upper bound of the derivatives of order ν (which exists as a Lipschitz function is differentiable almost everywhere). For these values of ν, the spaces defined here are equivalent to the spaces C ν-1,1 (Ω) defined in [25] .Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: every claim made in the abstract corresponds to a result proved in the paper.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
limitations: 
 Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We propose some novel algorithms and theoretical MDP setting always clarifying that these elements not include all the settings studied in the literature of theoretical RL.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
locally linearizable mdps: 
 As we have stated in the introduction, the main limitation of the low inherent Bellman error assumption is that it cannot model scenarios where the linear parameter θ changes across the state-action space.In fact, ϕ h (s, a) ⊤ θ must be an approximation of the Q-function Q h (s, a) uniformly over (s, a) ∈ Z.To overcome this limitation, we introduce a novel concept of locality to enable the feature map to be associated with different parameters θ in different regions of the state-action space.Therefore, from this point on, we are going to associate to a given Markov Decision Process M the following two entities:1. ϕ h : Z → R d h : a feature map which is allowed to depend on the current stage (also for its dimension.2. U h : a sequence of partitions of the state-action space Z in N h regions, so that U h := {Z h,n } N h n=1 . We call ρ h : Z → [N h ] the map linking every element z ∈ Z to the index of its set in the partition U h . These two elements are necessary to introduce the function class we are going to use as function approximator in this setting. Calling θ h = {θ h,n } N h n=1 a list of vectors in R d h , one for each of the regions Z h,n , we employ, as function approximator for the state-action value function, the following setEQUATIONCoherently, we will callV h := {V (s) = sup a∈A Q(s, a) : Q ∈ Q h , s ∈ S}. For fixed z, we have Q h [θ h ](z) = ϕ h (z) ⊤ θ h,ρ h (z), so that the feature map is allowed to depend directly on z, while the linear parameter only depends on ρ h (z), the function indicating in which of the N h regions we are. B h,n are arbitrary compact sets which contain the candidate values for the linear parameters θ h,n . Two relevant quantities for this model are the 2-norm of the feature map and the diameter of the setsB h,n , L ϕ := sup h∈[H],z∈Z ∥ϕ h (z)∥ 2 R h,n := diam(B h,n ),Respectively. Analog normalization constants appear in [18, 42] . The low inherent Bellman error property can be redefined in this setting as follows. Definition 1. (Inherent Bellmann Error) Given a family of compact setsB h,n ⊂ R d h depending on h ∈ [H], n ∈ [N h ],and their Cartesian productEQUATIONNote that, for N h = 1, our definition exactly reduces to Equation ( 2), as expected. As in that case, the term I plays the role of an approximation error. By assuming a bound on I(ϕ, U), we can now give a formal definition of the class of MDPs we are going to study in this paper. Definition 2. An I-Locally Linearizable MDP3 is a triple (M, {ϕ h } H h=1 , {U h } H h=1 ) where M is an MDP, ϕ h : Z → R d h is a feature map and U h a sequence of partitions of the state-action space Z in N h regions such that the corresponding inherent Bellman error (definition 1) satisfies I(ϕ, U) ≤ I.As for the class of MDPs with Low Inherent Bellmann error, ϕ (and U in our case) must be known to the agent, while I is not needed. The novel aspect this class is that, as a result of definition 1, linearity is independently enforced in separate regions of the state-action space. We provide a visualization of this concept in Figure 1 . Note that, in principle, any MDP belongs to the Locally Linearizable representation class for I = 1. In fact, if we take U h = {Z}, the trivial partition containing just the state-action space as an element, and ϕ h (z) = 0 (a feature map mapping everything to 0), Equation ( 5) is satisfied with I = 1. Nonetheless, this class is interesting only if I is small, as it is easy to show that the regret of any algorithm in this class grows at least as IK.Limitations of known approaches. Formally, no algorithm in theoretical RL literature can achieve no-regret learning on this class of problems, as it is a superclass of the low inherent Bellman error, which, to the best of our knowledge, is not included in any other setting that has been tackled. Still, a clever strategy called feature extension (example 2.1 from [18] ) may allow us to solve this class of MDPs. In fact, consider ELEANOR [42] , the only algorithm able to deal with MDPs with low inherent Bellman error. This trick employs a newly defined feature map:ϕ h (z) := [δ h,1 (z)ϕ h (z), δ h,2 (z)ϕ h (z), . . . , δ h,N h (z)ϕ h (z) N h ] ⊤ , δ h,n (z) := 1 if ρ h (z) = n 0 otherwiseso that its dimension expands from d h to N h d h . This way, any function of Q h (as defined in Equation 4) is linear in ϕ h (z), with a single θ h independent of the region Z n,h . Indeed, we have for Q h [θ h ] ∈ Q h : Algorithm 1 CINDERELLA (ConstrainedQ h [θ k h ](z) = ϕ h (z) ⊤ θ k h,ρ h (z) ∀h ∈ [H] 6: for h = 1, 2, . . . H -1 do 7: Choose action a k h ∈ arg max a∈A Q h [θ k h ](s k h , a) 8:Receive reward r k h and next state s k h+1 9: end for 10: end forQ h [θ h ](z) = ϕ h (z) ⊤ θ h,ρ h (z) = ϕ h (z) ⊤ [θ h,1 , θ h,2 , . . . , θ h,N h ].This shows every Locally Linearizable MDP with feature map ϕ h of dimension d h is also an MDP with low inherent Bellman error w.r.t. ϕ h of dimension N h d h and the same value for I. If we apply the regret bound for ELEANOR [42, Theorem 1], we obtain:EQUATIONholding with high probability. The issue is that the second term, growing linearly in K, depends on the number of regions as √ N h . As we will see in the second part of this paper, the application of this model to Smooth MDPs requires N h to be very large and also dependent on K. For this reason, in the next section, we introduce an ad hoc algorithm for Locally Linearizable MDPs to improve this dependence.As we have seen, even a wise application of the ELEANOR algorithm is not enough to solve our setting of Locally Linearizable MDPs satisfyingly. Thus, we introduce a novel algorithm, CINDERELLA (Algorithm 1). Before analyzing it, we need to introduce some notation. Let us call s k h , a k h , r k h the state, action, and reward relative to step h of episode k. Moreover, we denote z k h := (s k h , a k h ) andϕ k h = ϕ h (z k h ). At every episode k ∈ [K],we compute an optimistic estimation of the Q-function for every step h ∈ [H]. Then, we choose actions in order to maximize this function while fixing s k 1 (line 7). Clearly, what is really important is how this surrogate Q-function is computed (line 4). Here, CINDERELLA relies on solving an optimization problem (7) , which follows an idea similar to the one of [42] . We want to optimize over three sets of variables: θ h,n , ξ h,n , θ h,n , the first one representing ridge regression of the linear parameter for region n at step h, the second representing the uncertainty relative to this estimation, and the third one an "optimistic" estimate. Under this view, the objective is to maximize the surrogate V -function in the first state, and the constraints are designed so that all variables match their intuitive interpretation. Formally, the optimization problem is defined as:EQUATIONs.t. θ h,n = Λ k h,n -1 k-1 τ =1 1{ρ h (z τ h ) = n}ϕ τ h r τ h + max a∈A ϕ h+1 (s τ h+1 , a) ⊤ θ h+1,ρ(s τ h+1 ,a) θ h,n = θ h,n + ξ h,n ∥ξ h,n ∥ Λ k h,n ≤ α k h,n .WhereΛ k h,n := k τ =1 1{ρ h (z τ h ) = n}ϕ τ h ϕ τ h⊤ + λI, is the design matrix of λ-regularized ridge regression, and α k h,n is a constant determining the exploration rate which will be fixed in the analysis B.6. As it is for ELEANOR, this algorithm turns out to be computationally inefficient, an issue that we [25] .discuss in the Appendix D. The first constraint enforces that θ h,n is estimated with ridge regression having as target the (optimistic) value function estimated for step h + 1, and the second constrain θ h,n = θ h,n + ξ h,n ensures that the optimistic estimate in every region is given by its mean estimate plus the uncertainty, while the third one bounds the magnitude of ξ h,n so that this uncertainty shrinks the more data we collect.Although the structure of the algorithm is directly inherited from ELEANOR, CINDERELLA distinguishes itself by dividing the samples across the various regions of the state-action space of the MDP. This allows parameters associated with different regions to be learned independently. Despite introducing another layer of technical difficulty in proving the regret bound, this procedure is relatively natural given the characteristics of our class of problems.CINDERELLA: Regret bound. Having defined the algorithm, we can state a theorem showing a high probability regret bound in our setting.Theorem 2. Assume to be in an I-Locally Linearizable MDP withL ϕ = O(1), sup n∈[N h ] R h,n = O( √ d h )and that Assumption 1 holds. Then, with probability at least 1δ, CINDERELLA (Algorithm 1), with λ = 1 achieves a regret bound of orderR K = O H h=1 N h d h √ K + H h=1 √ d h IK .The proof of this result is long, and is deferred to sections B and C of the appendix. Note that the two normalization assumptionsL ϕ = O(1) and sup h∈[H],n∈[N h ] R h,n = O( √ d h )correspond to the ones enforced by [42] . While for N h = 1 the two reported bounds coincide, Theorem 2 proves superior to the regret bound obtained for ELEANOR in our setting (Equation 6), as it prevents the second term, which is linear in K, to depend on N h . This dramatically changes the potential of the regret bounds and, as we will see in the next sections, represents the key to achieving sub-linear regret bounds for RL in continuous state-action spaces. 
from local linearity to mildly smooth mdps: 
 Having proved that our CINDERELLA algorithm enjoys an improved regret bound on Locally Linearizable MDPs, we need to see how powerful this new class is once applied to problems with continuous state-action spaces for which a representation is not given a priori. To this aim, we are going to define a family of continuous-space MDPs, and prove that they are included in the Locally Linearizable class for a particular choice of ϕ h , U h . From now on, we assume, without loss of generality, thatS = [-1, 1] d S and A = [-1, 1] d A , so that Z = [-1, 1] d .We call Mildly Smooth MDP a process where the Bellman optimality operator outputs functions that are smooth.T h is bounded on L ∞ (Z) → C ν (Z).Boundedness over L ∞ (Z) → C ν (Z) means that the operator transforms functions that are bounded (i.e., belong to L ∞ (Z)) into functions that are ν-times differentiable (i.e., belong to C ν (Z)). Moreover, there exists a constantC T < +∞ such that ∥T h f ∥ C ν ≤ C T (∥f ∥ L ∞ + 1) for every h ∈ [H]and every function f ∈ L ∞ (Z). Intuitively, this condition means that by applying the Bellman operator to bounded (possibly non-smooth) functions, we always get functions that are smooth.In order to reduce this family of processes to Locally Linearizable MDPs, we have to design the partition of the state-action space into sets Z h,n . Since Z ⊂ [-1, 1] d , we can find, for every ε > 0, a set Z ε which is an ε-cover of Z in the infinity norm, such that |Z ε | =: N ≤ (2/ε) d . Now, for every z n ∈ Z ε , we define recursively Z n to be the set of points which are near to z n , formally:EQUATIONBy definition, every point of Z is matched with a point z n of the cover Z ε and, importantly, is assigned to exactly one subset Z n of Z. This way, we have defined a partition {Z n } N n=1 of Z, one that does not depend on the step h. Secondly, we have to choose the feature map ϕ h (•). To this end, we define ϕ h (z) as the vector of Taylor polynomials of degree ν * centered in z n ∈ Z ε for n = ρ(z) (just "Taylor feature map" in the following). This means that, fixed z ∈ Z such that ρ(z) = n, the map ϕ(z) will contain terms of the form (zz n ) α for every multi-index ∥α∥ 1 ≤ ν * . Note that the feature map does not depend on the time-step h either. The dimension of this feature map, which we call d ν * , corresponds to the number of non-negative multi-indexes such that ∥α∥ 1 ≤ ν * , which is well-known to bed ν * = ν * +d ν * ≤ ν d * .The power of this choice lies in the fact that, as it is well known from mathematical analysis, any C ν function can be approximated by a Taylor polynomial of degree ν * in a neighborhood of diameter ε with an error of order ε ν . Seeing the regions Z n we have defined as neighborhoods of the points z n of the cover, the analogy is complete. This argument is made formal in the following result. Theorem 3. Let M be a Mildly Smooth MDP, and ε ≤ 1/(2C T H) 1/ν . Then, choosing Z h,n as in Equation (8) and taking ϕ h as the Taylor feature map on the same regions, the tuple (M, {Z h,n } n,h , {ϕ h } h ) is an I-Locally Linearizable MDP withL ϕ = 1 + 2 √ d ν * , R h,n = 2 √ d ν * C T , I ≤ 2C T ε ν .This reduction shows how general the class of Locally Linearizable MDPs is and enables us to tackle Mildly Smooth MDPs with the CINDERELLA algorithm, originally designed for Locally Linearizable MDPs. By appropriately selecting the parameter ε, we can prove the following theorem, bounding the regret of a Locally Linearizable MDP with smoothness ν and state-action space of dimension d. Theorem 4. Let M be a Mildly smooth MDP of parameter ν > 0 satisfying Assumption 1. With probability at least 1δ, CINDERELLA, initialized with λ = 1, Z h,n as in Equation ( 8) and ϕ h given by the Taylor feature map on the same regions, achieves a regret bound of order:R K ≤ O Hd ν * K ν+2d 2ν+2d + H 2ν+2d ν.Before comparing our result with the state of the art, some comments are due. First note that the exponent of K is ν+2d 2ν+2d , which is always in (1/2, 1). This means that the no-regret property is achieved in every regime. Two elements in this regret bound are undesirable: i) the exponential dependence in d (as d ν * ≤ ν d * ) and ii) the lower-order term H 2ν+2d ν, which has an exponent that may be very large, albeit polynomial in H. The first issue is discussed in the appendix (Section E.5). We show that even for the much simpler continuous bandit problem, lower bounds entail that the problem is not learnable unless d = o(log(K)). Therefore, terms of order 2 d can still be seen as o(K α ) for an arbitrarily small α > 0. For the second issue, note that the exponent of H in the lower order term is significantly large only if d ≫ ν. This regime is known to be very difficult, and in the literature before this paper it was not even possible to achieve the no-regret property (even just for d > 2ν).We end this section with a simple corollary showing how to deal with the "large ν" regime. Corollary 5. Under the assumption of theorem 4, for ν > log(K) we have [25] , Lipschitz MDPs in [31] , and Kernelized MDPs in [41] . Rows correspond to algorithms with no-regret guarantees for some of the settings. [25, 34, 38] represented the state of the art for Strongly smooth MDPs, Lipschitz MDPs, and Kernelized MDPs, respectively. The last row indicates whether the corresponding setting is feasible or if there exists an exp(H) lower bound for the regret.R K = O H log(K) d K 1 2 + H 2 . Algorithm Weakly Lipschitz Mildly Strongly Kernelized [25] LEGENDRE-ELEANOR K ν+3d/2 d+2ν K 1+3d/2 2+d K ν+3d/2 2ν+d K ν+3d/2 2ν+d K ν+3d/2 2ν+d [17] GOLF K 2ν+3d 4ν K 2+3d 4 K 2ν+3d 4ν K 2ν+3d 4ν K 2ν+3d 4ν [34] NET-Q-LEARNING ✗ K 1+d 2+d ✗ K 1+d 2+d K 1+d 2+d CINDERELLA (Ours) ✗ ✗ K ν+2d 2ν+2d K ν+2d 2ν+2d K ν+2d 2ν+2d [25] LEGENDRE-LSVI ✗ ✗ ✗ K ν+2d 2ν+d K ν+2d 2ν+d [41] KOVI ✗ ✗ ✗ ✗ K ν+3d/Proof. Applying theorem 4 for ν arbitrarily large does not work, asd ν * ≈ ν d makes the bound vacuous. Still, note that, being ∥ • ∥ C ν ′ ≤ ∥ • ∥ C ν ′ for ν ′ ≤ ν,under the assumption of the theorem we can take ν = log(K). At this point, theorem 4 ensuresR K ≤ O H log(K) d K log(K)+2d 2 log(K)+2d + H 2 = O H log(K) d K 1 2 + H 2 , due to the fact that K log(K)+2d 2 log(K)+2d = K 1 2 K d 2 log(K)+2d = K 1 2 2 d log(K) 2 log(K)+2d ≤ 2 d K 1 2 .The appearance of log(K) d should not scare: this term is necessary even in the simpler case of bandits with squared exponential kernel, as the lower bound in [37] shows. 
comparison with related works: 
 Regret bounds for continuous MDPs have been an area of intense research in recent years. While many parametric families like LQRs have been shown to achieve poly(H) √ K regret bounds [2] , tackling this problem in more general cases has been proved to be very challenging.Kernelized MDPs [8, 41, 13] are a representation class of processes assuming that the transition function p h (•) as well as the reward function r h (•) belong to a Reproducing Kernel Hilbert Space (RKHS) with given kernel k(•, •). Most of the literature deals with the case of the Matérn kernel. The smoothness of this kernel is determined by a parameter ν > 0; by fixing it we can compare this family with the other families of continuous MDPs. The best-known result [41] in this setting only achieves regret O(K ν+3d/2 2ν+d ), which is vacuous if d > 2ν. Very recently [38] presented a regret bound of order O(K ν+d 2ν+d ), but we were not able to verify the correctness of this result. We discuss a possible subtle issue of the proof in Appendix F. Another family that is based on assuming that p h and r h belong to some given functional space is the Strongly Smooth MDP [25] . This family assumes that p h (s ′ |•), r h (•) ∈ C ν (Z). A subtle difference is that in [25] , the smoothness index ν was restricted to be an integer, while in our case, it is a generic real ν > 0. Regret bounds for this family were shown of order O(K ν+2d 2ν+d ), which is vacuous even for d > ν. Since, for the same ν, the Matèrn kernel RKHS is a subset of C ν (Z) (see Appendix E.3), Strongly Smooth MDPs are more general than the former family. Further increasing the generality, we have Lipschitz MDPs [31] . This is only a superset of the Strongly Smooth MDPs for ν = 1, as Lipschitz MDPs do not admit higher levels of smoothness. A regret guarantee of order O(K 1+d 2+d ), which turns out to be optimal for this setting, was achieved by different algorithms [33, 34, 32, 21] in recent years. Unfortunately, it was recently shown that an exponential dependence on the horizon H is unavoidable [25] . Therefore, the Lipschitz MDPs, as any of their generalizations, are intrinsically unfeasible.Increasing the generality even further, we find the family of Weakly Smooth MDPs [25] , which imposes the Bellman optimality operator T h to be bounded on C ν (Z) → C ν (Z). For fixed ν, this assumption generalizes Strongly smooth MDPs (with the same ν), and, for ν = 1, the Lipschitz MDPs. For this reason, also this family is affected by an exp(H) regret lower bound, while in terms of K its regret has been bounded as O(K ν+3d/2 2ν+d ), the same as Kernelized MDPs. Introducing a different notion of dimension, we can also define the family of MDPs with bounded Bellman-Eluder dimension [17] . This family is, in a certain sense, even wider, but admits worse regret bounds [25] .Key point: locality. Our approach leverages the concept of locality. We approximate the continuous problem by constructing a feature map that captures information from local neighborhoods. This is a novel approach in the context of Reinforcement Learning (RL), with only [38] employing a remotely similar idea. Nonetheless, the effectiveness of this strategy has been well-established in the field of Continuous Armed Bandits, as demonstrated by [16, 23] .Comparison with our work. As the name suggests, the family of Mildly Smooth MDPs occupies an intermediate position between Weakly and Strongly Smooth processes. In Appendix E.2, we formally prove this relation, showing that both inclusions are strict. A graphical representation of this relationship is shown in Figure 2 . Note that, even if our family is not the largest that has been studied in the literature, it is indeed the largest known one for which RL is feasible.We have summarized the comparison between the regret bound of CINDERELLA with state-of-the-art algorithms for the various MDP families in Table 1 , where settings (columns) are listed from the most general (Weakly Smooth) to the least (Kernelized). All inclusions are intended to hold for a fixed parameter ν, which is shared by all the MDP families apart from the Lipschitz one, which in some sense has fixed ν = 1. For every column, the best regret guarantee is colored in green, with ✗meaning that the algorithm (row) is unsuitable for the setting (column). As we can see, CINDERELLA i) works in every setting where there is no exp(H) lower bound for the regret, achieving the best guarantees ii) is the only algorithm to exploit smoothness fully, i.e. achieving regret √ K in the limit ν → ∞ while being non-vacuous for all finite values of d, ν. 
conclusion: 
 In this paper, we have significantly enlarged the set of MDPs for which no-regret guarantees are possible. After defining the representation class of Locally Linearizable MDPs (Section 3), we have introduced a new algorithm called CINDERELLA (Algorithm 1), which is able to achieve a strong regret guarantee on this setting, being a "local" generalization of the ELEANOR algorithm. In the second part of the paper, we have introduced a family called Mildly Smooth MDPs (Section 4), which generalizes all the known continuous MDP families where no-regret learning is feasible. Through an argument based on local Taylor polynomial approximation, we have proved that this family is a special instance of the Locally Linearizable MDPs, with a specific partition and feature map. Therefore, we were able to achieve, in Theorem 4, a regret bound for CINDERELLA in the family of Mildly Smooth MDPs, which constitutes the main result of this paper. Not only this bound surpasses the state-of-the-art in terms of generality for feasible settings, but is also able to achieve improved regret bounds for Strongly Smooth MDPs and Kernelized MDPs. Crucially, our work proves the first regret bound that is non-vacuous in any regime for these two families.  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: No experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: The work does not include crowdsourcing.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: the paper does not involve crowdsourcing.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Z h,n Element of a partition of Z at step h ρ h Mapping from Z to index in [N h ] U h {Z h,n : u = 1, . . . N h } Q h [θ h ] Q-function associated to given θ h parameter at step h. V h [θ h ] max a∈A Q h [θ h ](•, a) B h Set of candidate θ h at step h B h,n Set of candidate θ h,n at step h restricted to the region n R h,n Norm-2 radius of B h,n R h,max sup n∈[N h ] R h,n Q h , V h Space ofk h (s k h , a k h ) ϕ k h ϕ h (z k h ) Λ k h,n Ridge regression matrix for space Z h,n up to episode k ξ h,n , θ h,n , θ h,nOptimization variables of the problem in section B.2Q k h (z) Q h [θ k h ](z) V k h (s) max a∈A Q k h (s, a) η k h (V ) Bellman error at step h of episode k w.r.t. V • θ h,n (Q h+1 ) see equation 12 ∆ h (Q h+1 ) Error done approximating Q h+1 with • θ h (Q h+1 ) ρ k h,n 1{ρ h (z k h ) = n} β k h,nQuantity defined by corollary 10N (•)Covering number in infinity normE Good event Ω Generic subset of [-1, 1] d d dimension of a set (usually Z = [-1, 1] d )ν Index saying how many times a function is differentiableν * ⌈ν -1⌉ L ν (f ) Lipschitz constant of f w.r.t. the index ν α multi-index D α multi-index derivative C ν space of functions that are ν-times differentiable C T See definition 3 ∥ • ∥ L ∞ supremum norm of a function, ∥f ∥ L ∞ = sup |f | ∥ • ∥ C ν norm over C ν T ν * y [f ] Taylor polynomial of f of order ν * centered in y d ν * ν * +d ν *As stated in the main paper, Locally Linearizable MDPs are a representation class of processes that can be efficiently approximated with linear function in some predefined regions of Z.Precisely, the linearity stays in the iterations of the Bellman optimality operator, which we recall here. For a general MDP, we call S, A the state and action space, respectively, Z = S × A, and T h the Bellman optimality operator at step h, which is given, for every function f : Z → [0, 1], byT h f (z) := S p h (s ′ |z) max a ′ ∈A f (s ′ , a ′ ) ds ′ .Recalling the definition given in the main paper, in a Locally Linearizable MDP the state-action space Z is partitioned into a step-dependent number N h of regions Z h,n that we collect into U h := {Z h,n : u = 1, . . . N h }. To map every element z ∈ Z to its corresponding region we define the function functionρ h : Z → [N h ].The importance of these regions stays in the fact that there is a step-dependent feature map ϕ h : Z → R d h such that the optimal state-action value function is approximately linear in ϕ h with a parameter depending on the region. Coherently, we define our approximator functions Q h to be the set of functions on Z that are linear on the regions, namelyQ h (z) = ϕ h (z) ⊤ θ h,ρ h (z) z ∈ Z, coherently, we define V h := {V (s) = arg max a Q(s, a) : Q ∈ Q h }.By convenience, we will sometimes stack all these parameters in the list θ h = {θ h,n } N h n=1 and call Q h [θ h ] the corresponding state-action value function. In order not to allow the function set Q h to contain functions with an arbitrary large slope, we impose the θ h,n parameters to be constrained into bounded sets that we call B h,n .We define the following bounds on the parameters of the process. Definition 4. We call• L ϕ := sup h∈[H],z∈Z ∥ϕ h (z)∥ 2 . • R h,n := diam(B h,n ). Now, calling B h ⊂ R d h ×N h the sets given by B h = N h × n=1 B h,n ,The performance of our algorithm will depend on the maximum approximation error that can be done by projecting the result of the Bellman operator on our functions Q. In formula,EQUATIONNote that the low inherent Bellman error MDPs are a subclass of this problem: it is sufficient to take N h = 1 at every step.In this subsection, we create what we will call a quasi-optimal solution for the MDP. Define θ ⋆ h in the following recursive wayEQUATIONSo that θ ⋆ h is constructed by stacking these θ ⋆ h,n terms. We have the following result. Theorem 6. The approximately optimal Q-functionsatisfies ∀h ∥Q[θ ⋆ h ](•) -Q ⋆ h (•)∥ L ∞ ≤ (H -h)IProof. We perform the proof by induction, with the case h = H + 1 being trivial.∥Q[θ ⋆ h ](•) -Q ⋆ h (•)∥ L ∞ = Q[θ ⋆ h ](•) -T h Q h+1 [θ ⋆ h+1 ](•) + T h Q h+1 [θ ⋆ h+1 ](•) -Q ⋆ h (•) L ∞ = Q[θ ⋆ h ](•) -T h Q h+1 [θ ⋆ h+1 ](•) + T h Q h+1 [θ ⋆ h+1 ](•) -T h Q ⋆ h+1 (•) L ∞ ≤ Q[θ ⋆ h ](•) -T h Q h+1 [θ ⋆ h+1 ](•) L ∞ + T h Q h+1 [θ ⋆ h+1 ](•) -T h Q ⋆ h+1 (•) L ∞ ≤ Q[θ ⋆ h ](•) -T h Q h+1 [θ ⋆ h+1 ](•) L ∞ + Q h+1 [θ ⋆ h+1 ](•) -Q ⋆ h+1 (•) L ∞ ,where in the last passage we have used the non-expansivity of the Bellman operator. At this point, the second part is bounded as∥Q h+1 [θ ⋆ h+1 ](•) -Q ⋆ h+1 (•)∥ L ∞ ≤ (H -h -1)I,by inductive hypothesis, while the first one satisfies, by equations ( 9) and ( 10)∥Q[θ ⋆ h ](•) -T h Q h+1 [θ ⋆ h+1 ](•)∥ L ∞ ≤ I.Combining the two results gives the thesis.We call s k h , a k h , r k h the state, action, and reward relative to step h of episode k. Moreover, we denotez k h := (s k h , a k h ) and ϕ k h = ϕ h (z k h ).We define, for any region n step h and episode k, the ridge regression matrix asΛ k h,n := k τ =1 1{ρ h (z τ h ) = n}ϕ τ h ϕ τ h ⊤ + λI.Our algorithm, CINDERELLA (Algorithm 1), is built on top of an optimization problem (Eq. 7) which, at the start of each episode k, provides an optimistic version of the state-action value function. We recall it here:EQUATIONs.t. θ h,n = Λ k h,n -1 k-1 τ =1 1{ρ h (z τ h ) = n}ϕ τ h (r τ h + V h+1 (s τ h+1 )) V h+1 (•) := max a∈A ϕ h+1 (•, a) ⊤ θ h+1,ρ(•,a) θ h,n = θ h,n + ξ h,n ∥ξ h,n ∥ Λ k h,n ≤ α k h,nNote that, with respect to the main paper, we have given a name to the quantity V h+1 (•) := max a∈A ϕ h+1 (•, a) ⊤ θ h+1,ρ(•,a) to make the variables more interpretable. The constant α k h,n will be defined in the next sections of this appendix.We will now continue our work by proving that CINDERELLA is able to achieve a regret guarantee for this setting. First, we set up some additional notation.θ k h , θ k h and ξ k h , we define Q k h (z) := Q h [θ k h ](z), V k h (s) := max a∈A Q k h (s, a).Moreover, in the rest of the section, once fixed a function V : S → [0, 1], we define the Bellman error at step h of episode k asη k h (V ) := r k h -r h (s k h , a k h ) + V (s k h+1 ) -E s ′ ∼p h (•|s k h ,a k h ) [V (s ′ )].Furthermore, given a functionEQUATIONand, as before, we collect all these vectors in• θ h (Q h+1 ). Finally, we define ∆ h (Q h+1 )(z) := T h Q h+1 (z) -Q[ • θ h (Q h+1 )](z).We start by proving a proposition which establishes a relation between the variables of the optimization problem (11)Proposition 7. Let {ξ k h,n , θ k h,n , θ k h,n } h,n be in the feasible region of Problem (11) at episode k of the process. We haveEQUATIONEQUATIONProof. For simplicity, let us abbreviateρ k h,n := 1{ρ h (z k h ) = n}. By construction, θ k h,n = Λ k h,n -1 k-1 t=1 ρ τ h,n ϕ τ h (r τ h + V k h+1 (s τ h+1 )) = Λ k h,n -1 k-1 τ =1 ρ τ h,n ϕ τ h r h (z τ h ) + E s ′ ∼p h (•|z τ h ) [V k h+1 (s ′ )] + Λ k h,i -1 k-1 t=1 ρ τ h ϕ τ h η k h (V k h+1 (s τ h+1 )) T 3 k h,n = Λ k h,n -1 k-1 τ =1 ρ τ h,n ϕ τ h T h [Q k h+1 ](z τ h ) + T 3 k h,n ,where we have used the definition of Bellman's optimality operator. By definition, we haveT h [Q k h+1 ](z τ h ) = Q[ • θ h (Q k h+1 )](z τ h ) + ∆ h (Q k h+1 )(z τ h ),which, when multiplied by ρ τ h,n lets only the term corresponding to the region n remain. Then, by Equation ( 12), we haveρ τ h,n T h [Q k h+1 ](z τ h ) = ρ τ h,n ϕ h (z τ h ) ⊤ • θ h,n (Q k h+1 ) + ρ τ h,n ∆ h (Q k h+1 )(z τ h ).Using this fact, we haveΛ k h,n -1 k-1 τ =1 ρ τ h,n ϕ τ h T h [Q k h+1 ](z τ h ) = Λ k h,n -1 k-1 τ =1 ρ τ h,n ϕ τ h ϕ τ h ⊤ • θ h,n (Q k h+1 ) + ∆ h (Q k h+1 )(z τ h ) = Λ k h,n -1 k-1 τ =1 ρ τ h,n ϕ τ h ϕ τ h ⊤ • θ h,n (Q k h+1 ) + T 1 k h,n .For the remaining term, note thatΛ k h,n -1 k-1 τ =1 ρ τ h,n ϕ τ h ϕ τ h ⊤ • θ h,n (Q k h+1 ) = Λ k h,n -1 -λ • θ h,n (Q k h+1 ) + λ • θ h,n (Q k h+1 ) + k-1 τ =1 ρ τ h,n ϕ τ h ϕ τ h ⊤ • θ h,n (Q k h+1 ) = Λ k h,n -1 -λ • θ h,n (Q k h+1 ) + Λ k h,n • θ h,n (Q k h+1 ) = • θ h,n (Q k h+1 ) -T 2 k h,nThe objective of the next lemmas is to show that the terms arising from the previous proposition are small with high probability. Lemma 1. For any z ∈ Z, any time-step h and any n, we have|ϕ h (z) ⊤ T 1 k h,n | ≤ ∥ϕ h (z)∥ Λ k h,n -1 p k h,n I, where p k h,n := k-1 τ =1 1{ρ h (z τ h ) = n},and in particular∥T 1 k h,n ∥ Λ k h,n ≤ p k h,n I.Proof. By definition,EQUATIONAt this point, leave the first term and, in the second we rewrite the sum for the indices where the indicator function is not zero, gettingEQUATION.We can then use Lemma 8 from [42] , takinga i = ϕ τ ′ h and b i = ∆(Q k h+1 )(z τ ′ h ).As |b i | ≤ I, by the low inherent Bellman error assumption (Eq. 9), this givesp k h,n τ ′ =1 ϕ τ ′ h ∆(Q k h+1 )(z τ ′ h ) Λ k h,n -1 ≤ p k h,n I,which ends the proof of the first part. The second one comes from∥T 1 k h,n ∥ Λ k h,n = Λ k h,n -1 p k h,n τ ′ =1 ϕ τ ′ h ∆(Q k h+1 )(z τ ′ h ) Λ k h,n = p k h,n τ ′ =1 ϕ τ ′ h ∆(Q k h+1 )(z τ ′ h ) Λ k h,n -1 ≤ p k h,n I.We proceed bounding the second part of the sum. Lemma 2. For any z ∈ Z, any time-step h and any n, we have|ϕ h (z) ⊤ T 2 k h,n | ≤ ∥ϕ h (z)∥ Λ k h,n -1 λ -1 R h,n ,and, in particular∥T 2 k h,n ∥ Λ k h,n ≤ λ -1 R h,n .Proof. By definition,|ϕ h (z) ⊤ T 2 k h,n | = ϕ h (z) ⊤ Λ k h,n -1 • θ h,n (Q k h+1 ) ≤ ∥Λ k h,n -1 ϕ h (z)∥ Λ k h,n ∥ • θ h,n (Q k h+1 )∥ Λ k h,n -1 = ∥ϕ h (z)∥ Λ k h,n -1 ∥ • θ h,n (Q k h+1 )∥ Λ k h,n -1 ≤ ∥ϕ h (z)∥ Λ k h,n -1 λ -1 ∥ • θ h,n (Q k h+1 )∥ 2 ≤ ∥ϕ h (z)∥ Λ k h,n -1 λ -1 R h,n ,where the second inequality comes from the fact that Λ k h,n is the sum of λI and a positive semidefinite matrix, and the last one from the fact that• θ h,n (Q k h+1 ) ∈ B h,n . The second part comes from ∥T 2 k h,n ∥ Λ k h,n = ∥Λ k h,n -1 • θ h,n (Q k h+1 )∥ Λ k h,n = ∥ • θ h,n (Q k h+1 )∥ Λ k h,n -1 ≤ λ -1 R h,n .The last part of the sum is more complex and, in order to bound it, we need to define a failure event.For every h, k, n we define the failure event in the following way:F k h,n :=    ∃V ∈ V h : k-1 t=1 1{ρ h (z τ h ) = n}ϕ τ h η τ h (V ) Λ k h,n -1 > β k h,n    ,for a threshold β k h,n to be defined. The first step to bound the probability of this event is to compute the covering number of the function space V h Proposition 8. The ε-covering number of V h in infinity norm satisfieslog N (ε, V h ) ≤ O (N d log (R h,max /ε)) , where R h,max := sup n∈[N h ] R h,n .Proof. Note that the covering number of V h is not higher than the one of Q h . Indeed, let Q ε h be a ε-cover for Q h and defineV ε h := {V (s) = max a∈A Q(s, a) : Q ∈ Q ε h }. Then, taking any V ∈ V h there is Q ∈ Q h such that V (s) = max a∈A Q(s, a). At this point, taking V (s) = max a∈A Q(s, a), where Q ∈ Q ε h such that ∥Q -Q∥ ∞ ≤ ε, we have that V ∈ V ε h by definition and ∥Q -Q∥ ∞ ≤ ∥V -V ∥ ∞ ≤ ε.Q h . by definition, every Q h ∈ Q h takes the form Q h (z) = ϕ h (z) ⊤ θ h,ρ h (z) ,where ρ h : Z → [N h ] and every vector θ h,n is d h -dimensional with the norm bounded by R h,n . As the domain Z is partitioned into regions Z h,n , if we get a family of coverings Q ε h,n that cover each function in Q h restricted to the set Z h,n , we can obtain a covering of Q h by defining it in this wayQ ε h := Q : Q| Z h,n = Q n Q n ∈ Q ε h,n ,i.e., we cover every function Q by taking the nearest cover function on each region. As a result, the total number of elements in Q ε h corresponds to the productN h n=1 |Q ε h,n| of the elements in the smaller sets, so that we have only to estimate |Q ε h,n | for every n. To this aim, note that the functions in this set are all linear, as we are restricting to Z h,n , so that, applying a standard bound for the covering number of spaces of linear functions we can find Q ε h,n such that|Q ε h,n | = O (R h,n /ε) d h .Therefore, the total covering size amounts to|Q ε h | = O ( sup n∈[N h ] R h,n /ε) N d ,which completes the proof.Theorem 9. For a choice ofβ k h,n = O d h + log(N (1/ √ k, V h )) + log(1/δ) , we have P(F k h,n ) ≤ δ. Proof. Let V ε h be a ε cover of V h in infinity norm, so that |V ε h | = N (ε, V h ). Now, for every V ∈ V h we call V ∈ V ε h : ∥ V -V ∥ L ∞ ≤ ε.In this way, we haveEQUATION.As we have|V (s k h+1 ) -V (s k h+1 )| ≤ ε, |E s ′ ∼p h (•|s k h ,a k h ) [ V (s ′ ) -V (s ′ )]| ≤ ε, the same argument used in the proof Lemma 1, allows us to bound the last two terms with 2 p k h,n ε. The remaining term corresponds, for fixed V and indicating with F k h the filtration generated by all the events of the process up to step h of episode k, tok-1 t=1 ρ τ h,n ϕ τ h F k h -meas. r k h -r h (s k h , a k h ) + V (s k h+1 ) -E s ′ ∼p h (•|s k h ,a k h ) [ V (s ′ )] E[•|F k h ]=0 Λ k h,n -1, where the first term is an R d h -valued stochastic process which is entirely determined by the current state and current action, while the second is zero-mean conditioned on the rest of the process, and 1-subgaussian thanks to assumption 1. This last fact allows to apply Theorem 1 from [1] , obtaining with probability at least 1δ, for fixed V ,k-1 t=1 ρ τ h,n ϕ τ h r k h -r h (s k h , a k h ) + V (s k h+1 ) -E s ′ ∼p h (•|s k h ,a k h ) [ V (s ′ )] 2 Λ k h,n -1 ≤ 2 log   det λI -1/2 det Λ k h,n 1/2 δ   ≤ d h log(λ -1 ) + d h log((1 + kL ϕ )) + log(δ -1 ).Applying a union bound, it follows that the same result holds for every function in V ε h if we replace log(δ -1 ) with log(N (ε, V h )/δ). Merging this result with what we have found before, we have that, with probability at least 1δ, for all V ∈ V h , we havek-1 t=1 ρ τ h,n ϕ τ h η τ h (V ) Λ k h,n -1 ≤ d h log(λ -1 ) + d h log((1 + kL ϕ )) + log(N (ε, V h )) + log(1/δ) + 2 p k h,n ε.If we just bound p k h,n ≤ √ k, we can take ε = 1/ √ k to have that the previous is bounded byβ k h,n := d h log(λ -1 ) + d h log((1 + kL ϕ )) + log(N (1/ √ k, V h )) + log(1/δ) + 2,which completes the proof.From this theorem, a simple corollary follows by just taking a union bound over h∈ [H], n ∈ [N h ], k ∈ [K]:Corollary 10. For a choice ofβ k h,n = O d h + log(N (1/ √ k, V h ) + log(N h HK/δ)) ,we haveP   h,n,k F k h,n   ≤ δ.From now on, we are going to indicate the good event E as the opposite of the event defined in the previous corollaryE := h,n,k (F k h,n ) c ,moreover, β k h,n will always be the quantity defined by Corollary 10. We conclude the section proving the following Lemma 3. Under the event E, for any z ∈ Z, any time-step h of episode k and any n, we have|ϕ h (z) ⊤ T 3 k h,n | ≤ ∥ϕ h (z)∥ Λ k h,n -1β k h,n , and, in particular∥T 3 k h,n ∥ Λ k h,n -1 ≤ β k h,n .Proof. By definition,|ϕ h (z) ⊤ T 3 k h,n | = ϕ h (z) ⊤ Λ k h,n -1 k-1 t=1 1{ρ h (z τ h ) = n}ϕ τ h η τ h (V h+1 ) ≤ ∥Λ k h,n -1 ϕ h (z)∥ Λ k h,n k-1 t=1 1{ρ h (z τ h ) = n}ϕ τ h η τ h (V h+1 ) Λ k h,n -1 = ∥ϕ h (z)∥ Λ k h,n -1 k-1 t=1 1{ρ h (z τ h ) = n}ϕ τ h η τ h (V h+1 ) Λ k h,n -1.Under the good event E, we have that the second term is bounded by β k h,n , for the choice defined in Corollary 10. The second part comes from the fact that∥T 3 k h,n ∥ Λ k h,n = Λ k h,n -1 k-1 t=1 1{ρ h (z τ h ) = n}ϕ τ h η τ h (V h+1 ) Λ k h,n = k-1 t=1 1{ρ h (z τ h ) = n}ϕ τ h η τ h (V h+1 ) Λ k h,n -1 ≤ β k h,n .B.6 Quasi-optimal solution and good eventThanks to the previous result, we are able to show that the quasi-optimal solution is feasible with high probability.Theorem 11. Consider the optimization problem (11) , where α k h,n is set to β k h,n + p k h,n + λ -1 R h,n . Then, under the good event E, the quasi-optimal solution {θ ⋆ h } H h=1 (see (10) ) is feasible for (11) at any episode k.Proof. We perform the proof by induction on the time-step h, starting from h = H. Assuming that for every n ∈ [N h ] the choice θ ⋆ h+1,n is feasible we have that the choiceQ h+1 (z) := Q h+1 [θ ⋆ h+1](z) is also feasible. With this choice, proposition 7 ensures that, for every n,EQUATIONNow, to show that also θ ⋆ h is feasible, we have to prove that, substituting each θ h,n = θ ⋆ h,n in the previous equation, we get a value for ξ h,n such that∥ξ h,n ∥ Λ k h,n ≤ α k h,n .First note that, by definition,θ ⋆ h,n = • θ h,n (Q h+1 [θ ⋆ h+1 ]), so that the previous equation simplifies toEQUATIONEQUATIONEQUATIONEQUATION)where the second comes from Lemmas 1, 2 and 3. This completes the proves that each θ ⋆ h,n is feasible, meaning that also θ ⋆ h is, and completes the inductive step.From the feasibility of θ ⋆ h a simple corollary follows Corollary 12. Under the good event E, at each episode k, the V -function V k 1 (•) estimated from θ 1 as solution of solution of the optimization problem (11) satisfies ∀s ∈ S V ⋆ 1 (s) -V k 1 (s) ≤ (H -1)I.Proof. By design of the optimization problem, and the fact {θ ⋆ h } H h=1 is feasible under E, we haveV k 1 (s) ≥ V [θ ⋆ 1 ](s). Now, we have V ⋆ 1 (s) -V k 1 (s) ≤ V ⋆ 1 (s) -V [θ ⋆ 1 ](s) = max a∈A Q ⋆ 1 (s, a) -max a∈A Q[θ ⋆ 1 ](s, a) ≤ max a∈A Q ⋆ 1 (s, a) -Q[θ ⋆ 1 ](s, a) ≤ ∥Q ⋆ 1 (•) -Q[θ ⋆ 1 ](•)∥ L ∞ ≤ (H -1)I, where the last passage is possible by theorem 6.Moreover, we are also able to prove that the solution found by the optimization algorithm ( 11) is an "almost fixed" point of the Bellman optimiality operator. Proposition 13. Under the good event E, the Q-function computed with the optimization algorithm at each step k satisfies Outside of the failure event, we have∀z ∈ Z Q k h (z) -T h [Q k h+1 ](z) ≤ I + 2 α k h,ρ h (z) ∥ϕ h (z)∥ Λ k h,ρ h (z) -1 .Proof. By Proposition 7, we have, taking n := ρ h (z),|Q k h (z) -T h [Q k h+1 ](z)| ≤ |ϕ h (z) ⊤ θ h,n -T h [Q h+1 ](z)| + ϕ h (z) ⊤ (ξ h,n + T 1 k h,n -T 2 k h,n + T 3 k h,n ) ≤ I + ϕ h (z) ⊤ ξ h,n + ϕ h (z) ⊤ T 1 k h,n + ϕ h (z) ⊤ T 2 k h,n + ϕ h (z) ⊤ T 3 k h,n .The first term satisfies, by the constrain in the program,ϕ h (s, a) ⊤ ξ h,n ≤ ∥ξ h,n ∥ Λ k h,n ∥ϕ h (s, a)∥ Λ k h,n -1 ≤ α k h,n ∥ϕ h (s, a)∥ Λ k h,n -1 .The other terms satisfy, thanks to lemmas 1,2,3, satisfiesϕ h (z) ⊤ T 1 k h,n + ϕ h (z) ⊤ T 2 k h,n + ϕ h (z) ⊤ T 3 k h,n ≤ α k h,n ∥ϕ h (s, a)∥ Λ k h,n -1 .Using all the results that we have proved, we can finally bound the regret Theorem 14. Under event E, CINDERELLA, for λ = 1 achieves a regret bound of orderR K ≤ O H h=1 KN h (L ϕ + d h ) sup n R h,n + d h + d h log(N (1/ √ K, V h )) + KHI √ d h .Proof. By Corollary 12, the regret is bounded byR K = K k=1 V * 1 (s k 1 ) -V π k 1 (s k 1 ) ≤ KHI + K k=1 V k 1 (s k 1 ) -V π k 1 (s k 1 ).Note that, under the good event,V k h (s k h ) -V π k h (s k h ) = Q k h (z k h ) -V π k h (s k h ) Prop. 13 ≤ I + 2 α k h,ρ h (z k h ) ∥ϕ h (z k h )∥ Λ k h,ρ h (z k h ) -1 + T h [Q k h+1 ](z k h ) -V π k h (s k h ) = I + 2 α k h,ρ h (z k h ) ∥ϕ h (z k h )∥ Λ k h,ρ h (z k h ) -1 + E s ′ ∼p h (•|z k h ) [V k h+1 (s ′ ) -V π k h+1 (s ′ )].ζ k h := E s ′ ∼p h (•|s k h ,a k h ) [V k h+1 (s ′ ) -V π k h+1 (s ′ )] -V k h+1 (s k h+1 ) + V π k h+1 (s k h+1 ),we can rewrite the previous relation as a telescopic sum:V k 1 (s k 1 ) -V π k 1 (s k 1 ) ≤ I + 2 α k 1,ρ h (z k 1 ) ∥ϕ 1 (z k 1 )∥ Λ k 1,ρ 1 (z k 1 ) -1 + E s ′ ∼p1(•|z k 1 ) [V k 2 (s ′ ) -V π k 2 (s ′ )] = I + 2 α k 1,ρ h (z k 1 ) ∥ϕ 1 (z k 1 )∥ Λ k 1,ρ 1 (z k 1 ) -1 + ζ k 1 + V k 2 (s k 2 ) -V π k 2 (s k 2 )same quantity at next time step≤ HI + H h=1 2 α k h,ρ h (z k h ) ∥ϕ h (z k h )∥ Λ k h,ρ h (z k h ) -1 + ζ k h .This equation allows us to bound the regret, under the good event, asR K ≤ KHI + K k=1 H h=1 2 α k h,ρ h (z k h ) ∥ϕ h (z k h )∥ Λ k h,ρ h (z k h ) -1 + ζ k h .We start from the last term, which we rewrite, by exchanging the index of the sums asK k=1 H h=1 ζ k h = H h=1 K k=1 ζ k h .For fixed h the term ζ k h is a martingale difference and, if it is bounded almost surely in [-C, C] for some constant C > 0, we can apply Hoeffding's inequality to prove that w.p. at least 1δ,-2C K log(1/δ) ≤ K k=1 ζ k h ≤ 2C K log(1/δ).In our case, due to our problem definition we have that C may be chosen as L ϕ sup n R h,n . Imposing that the previous inequality works at every step at the same time, and summing over h, we get, w.p.EQUATIONNow, we go on bounding the other termEQUATIONWhere the last passage is due to the Cauchy-Schwartz inequality. The last sum can be rewritten by summing over the regions instead of the episodes:K k=1 4α k h,ρ h (z k h ) ∥ϕ h (z k h )∥ 2 Λ k h,ρ h (z k h ) -1 = N h n=1 p K h,n in=1 4α in h,n ∥ϕ h (z in h )∥ 2 Λ in h,n -1 ,where the index i n enumerates the episodes k where z k h ∈ Z h,n . At this point, recall that we have setα k h,n = β k h,n + p k h,n + λ -1 R h,n , so that, in particular α k h,n ≤ 3β k h,n + 3p k h,n + 3λ -1 R h,n ≤ 3p k h,n I 2 + 3d + 3 log(N (1/ √ k, V h )) + 3 log(1/δ) + 3λ -1 R h,n .This way, the previous sumN h n=1 p K h,n in=1 4α in h,n ∥ϕ h (z in h )∥ 2 Λ in h,n-1 can be again decomposed in few terms, according to the decomposition of α k h,n .12N h n=1 p K h,n in=1 p K h,n I 2 ∥ϕ h (z in h )∥ 2 Λ in h,n -1 = 12 N h n=1 p K h,n I 2 p K h,n in=1 ∥ϕ h (z in h )∥ 2 Λ in h,n -1 .Note that, by construction of the matrix Λ in h,n , we can use Lemma 11 from [1] to havep K h,n in=1 ∥ϕ h (z in h )∥ 2 Λ in h,n -1 ≤ 2d h log((λ + p K h,n L 2 ϕ /d h )) -log(det(λI))),where by fixing λ = 1 we havep K h,n in=1 ∥ϕ h (z in h )∥ 2 Λ in h,n -1 ≤ 2d h log((1 + p K h,n L 2 ϕ /d h )) ≤ 2d h log(KL 2 ϕ + 1).Therefore, we can bound the whole term asEQUATION)The remaining terms can be bounded in a simpler way: by just callingΨ := d h +log(N (1/ √ k, V h ))+ log(1/δ) + R h,n , we have N h n=1 p K h,n in=1 12Ψ∥ϕ h (z in h )∥ 2 Λ in h,n -1 = 12Ψ N h n=1 p K h,n in=1 ∥ϕ h (z in h )∥ 2 Λ in h,n -1 ≤ 12Ψ N h n=1 2d h log(KL 2 ϕ + 1) ≤ 24ΨN h d h log(KL 2 ϕ + 1),where we have used Lemma 11 by [1] as before. This result, together with Equation ( 22) can be inserted into the previous Equation ( 21) to getK k=1 H h=1 2 α k h,ρ h (z k h ) ∥ϕ h (z k h )∥ Λ k h,ρ h (z k h ) -1 ≤ H h=1 √ K K k=1 4α k h,ρ h (z k h ) ∥ϕ h (z k h )∥ 2 Λ k h,ρ h (z k h ) -1 ≤ √ 24 H h=1 √ K (KI 2 + ΨN h )d h log(KL 2 ϕ + 1) ≤ √ 24 H h=1 (KI + ΨN h K) d h log(KL 2 ϕ + 1).Therefore, the full bound on the reget can be written, also thanks to Equation (20) asR K ≤ 2 K log(H/δ) H h=1 L ϕ sup n R h,n + √ 24 H h=1 (KI + ΨN h K) d h log(KL 2 ϕ + 1).Ignoring terms that are logarithmic in K, H, L ϕ , 1/δ and passing to the O notation, we getR K ≤ O √ K H h=1 (L ϕ sup n R h,n + d h ΨN h ) + KHI √ d h .Now, note that by definitionΨ := d h + log(N (1/ √ k, V h )) + log(1/δ) + R h,n, so the previous can be rewritten asR K ≤ O √ KN H h=1 (L ϕ + d h ) sup n R h,n + d h + d h log(N (1/ √ K, V h )) + KHI √ d h .Merging the previous result with Proposition 8, which bounds the size of the covering, and the fact that the good event is designed to have probability at least 1δ (Corollary 10), we getCorollary 15. Assume that L ϕ = O(1) and sup h∈[H],n∈[N h ] R h,n = O( √ d h ).Then, with probability at least 1δ, CINDERELLA (Algorithm 1), with λ = 1 achieves a regret bound of orderR K = O H h=1 N h d h √ K + H h=1 √ d h IK .In this section, we are going to study the computational complexity of CINDERELLA (Algorithm 1).The key computational bottleneck lies in solving the constrained continuous optimization problem presented in Equation 7. Two obstacles hinder efficient solutions to this problem.1. In the first constrain, there is one term containing max a∈A ϕ h+1 (s τ h+1 , a) ⊤ θ h+1,ρ(s τ h+1 ,a) , which breaks linearity in θ h+1,n .2. In the third one, ∥ξ h,n ∥ Λ k h,n ≤ α k h,n breaks the linearity also in ξ h,n .The confluence of these two challenges renders the problem computationally intractable. This is unsurprising, as even the optimization problem in ELEANOR [42] , a simplified version of ours, is well-known for its computational difficulty. Fortunately, our setting allows for an inherent Bellman error, denoted by I. This enables us to forego an exact solution to problem 7 and instead seek an approximate solution. The resulting approximation error, denoted by ε, can be incorporated into the Bellman error term. From theorem 2 we deduce that if ε = O(K -1/2 ), its dependence in the regret bound is negligible. Therefore, a viable approach might involve constructing an ε-grid, denoted by G, over the variable space for ε ≈ K -1/2 and then to solve the problem with exhaustive search on G. This idea is not completely satisfying, as the cardinality of G would be of order|G| = O ( √ K) 3 H h=1 N h d h , since we have three optimization variables θ h,n , ξ h,n , θ h,n of dimension d h for every n ∈ [N h ].Unfortunately, at this level of generality, no strategy with polynomial computational complexity is known. As a comparison, algorithms presented in table 1 are not better. LEGENDRE-ELEANOR [25] is based on ELEANOR, so it is also intractable, GOLF [17] and NET-Q-LEARNING [34] require an optimization oracle. LEGENDRE-LSVI [25] and KOVI [41] can be implemented efficiently, but work only for simpler settings.In this section, we give our results for Mildly Smooth MDPs. First, we have to start from some notion from calculus.Let Ω ⊂ [-1, 1] d and f : Ω → R. We say that f ∈ C ν (Ω), for ν ∈ (0, +∞) if it is ν * -times continuously differentiable for ν * := ⌈ν -1⌉, and there is a constant L ν (f ) such that∀α : |α| = ν * , ∀x, y ∈ Ω, |D α f (x) -D α f (y)| ≤ L ν (f )∥x -y∥ ν-ν * ∞ ,where α is a multi-index, i.e. a tuple of non-negative integers (α 1 , . . . α d ) and the multi-index derivative is defined as followsD α f := ∂ α1+...+α d ∂x α1 1 . . . ∂x α d d .The previous set becomes a metric space when endowed with the following norm∥f ∥ C ν := max max |α|≤ν * ∥D α f ∥ L ∞ , L ν (f ) .Note that, when ν ∈ N, the previous norm simplifies as∥f ∥ C ν = max |α|≤ν ∥D α f ∥ L ∞ ,since the Lipschitz constant L ν (f ) of the derivatives up to order ν * = ν -1 corresponds exactly to the upper bound of the derivatives of order ν (which exist as a Lipschitz function is differentiable almost everywhere). For these values of ν, the spaces defined here are equivalent to the spaces C ν-1,1 (Ω) defined in [25] .The following approximation results hold true for this function space. Theorem 16. Let us consider the Taylor polynomial T ν * y [f ](•) centered in y ∈ Ω of order ν * . This can be written asT ν * y [f ](x) = ∥α∥1≤ν * D α f (y) α! (x -y) α . Then, ∀x ∈ Ω, |f (x) -T ν * y [f ](x)| ≤ L ν (f )∥x -y∥ ν ∞ .As this formulation has the form of a scalar product over ∥α∥ 1 ≤ ν * of one vector with componentsD α f (y) α!and another of components (xy) α , we rewrite it in the following formEQUATIONHere, note that the length of the two vectors corresponds to |{α ∈ N d :∥α∥ 1 ≤ ν * }| = ν * +d d ≤ ν d * .Moreover, the first only depends on f , while the second depends on x.With all this notation settled, we can define what we call a Mildly Smooth MDP.We call Mildly Smooth MDP a process where the Bellman optimality operator outputs functions that are smooth. Definition 5. (Mildly Smooth MDP). An MDPs is Mildly Smooth of order ν if, for every h ∈ [H], the Bellman optimality operator T h is bounded on L ∞ (Z) → C ν (Z).Boundedness over L ∞ (Z) → C ν (Z) means that the operator transforms functions that are bounded L ∞ (Z) into functions that are ν-times differentiable. Moreover, there exists a constantC T < +∞ such that ∥T h f ∥ C ν ≤ C T (∥f ∥ L ∞ + 1) for every h ∈ [H] and every function f ∈ C ν (Z).To determine how strong our assumptions are when compared to the literature, we prove the following considerations.ν-Kernelized ⊂ ν-Mildly Smooth. Given the definitions of the two MDP families, this point reduces to proving that the RKHS generated by the Matérn kernel of parameter ν > 0 is a subspace of C ν (Ω).Theorem 8, part (3) from [10] ensures that, for isotropic kernels, in order to have sample path ∈ C ν (Ω), a sufficient condition is for the kernel to be in C 2ν (Ω 2 ). The same theorem also shows (proof of Proposition 10) that the Matérn kernel can be written asM ν (x, y) ∝ (f 1 (∥x -y∥ 2 2 ) + ∥x -y∥ 2ν 2 f 2 (∥x -y∥ 2 2 )),wheref 1 , f 2 ∈ C ∞ (R). Note that, ∥x -y∥ 2 2 = d i=1 (x i -y i ) 2 ∈ C ∞ (Ω 2 ), so that f 1 (∥ • -• ∥ 2 2 ), f 2 (∥ • -• ∥ 2 2 ) ∈ C ∞ (Ω 2). Therefore, these two terms do not affect the overall smoothness of the kernel. This implies that the order of smoothness of M ν (x, y) corresponds to the one of ∥x -y∥ 2ν 2 which is (perhaps the most basic example of) C 2ν (Ω 2 ).For ν ∈ N, ν-Mildly Smooth ⊂ (ν -1)-Weakly Smooth. This part is obvious; indeed, as for every function we have ∥f ∥ L ∞ ≤ ∥f ∥ C ν-1,1 (where the last norm is defined in [25] ), we have∥T h f ∥ C ν-1,1 = ∥T h f ∥ C ν ≤ C T (∥f ∥ L ∞ + 1) ≤ C T (∥f ∥ C ν-1,1 + 1),where in the first passage we have used the fact that for ν integer ∥ • ∥ C ν-1,1 = ∥ • ∥ C ν and in the second we have used the definition of ν -1 Mildly-smooth MDP.For ν ∈ N, (ν -1)-Strongly Smooth ⊂ ν-Mildly Smooth. Let us assume an MDP is Strongly Smooth. Indeed, for every function f : S × A → R we have:T h f (s, a) = r h (s, a) + E s ′ ∼p h (•|s,a) [max a ′ ∈A f (s ′ , a ′ )] = r h (s, a) + S max a ′ ∈A f (s ′ , a ′ )p h (s ′ |s, a) ds ′ .By triangular inequality, this entails:∥T h f ∥ C ν ≤ ∥r∥ C ν + S max a ′ ∈A f (s ′ , a ′ )p h (s ′ |•) ds ′ C ν, where the first term ∥r∥ C ν = ∥r∥ C ν-1,1 (remember that ν is integer) is bounded by assumption and so we can focus on the second one. As all the functions involved are bounded, we can apply the theorem of exchange between integral and derivative [14] and we have, for every multi-index with |α| ≤ ν:EQUATIONUsing the abbreviation f (s ′ ) = max a ′ ∈A f (s ′ , a ′ ) we get:S f (s ′ )p h (s ′ |•) ds ′ C ν = max |α|≤ν D α S f (s ′ )p h (s ′ |•) ds ′ L ∞ = max |α|≤ν-1 L 1 D α S f (s ′ )p h (s ′ |•) ds ′ = max |α|≤ν-1 sup z1,z2∈Z D α S f (s ′ )p h (s ′ |z 1 ) ds ′ -D α S f (s ′ )p h (s ′ |z 2 ) ds ′ ∥z 1 -z 2 ∥ ∞ = max |α|≤ν-1 sup z1,z2∈Z S f (s ′ )(D α p h (s ′ |z 1 ) -D α p h (s ′ |z 2 )) ds ′ ∥z 1 -z 2 ∥ ∞ ≤ sup z1,z2∈Z S f (s ′ )C p ∥z 1 -z 2 ∥ ∞ ds ′ ∥z 1 -z 2 ∥ ∞ ≤ Vol(S)C p ∥ f ∥ L ∞Where the first step is the definition of ∥ • ∥ C ν , the second comes from the fact that, as we pointed out before, if a function f is Lipschitz the ∥ • ∥ L ∞ of its derivative corresponds to its Lipschitz constant, the third from definition of Lipschitz constant, the fourth by linearity of the derivative, the fifth one by definition of strongly (ν -1)-smooth process (the part about p h ) and the last one by just bounding the integral with the infinity norm times the measure of the set.For ν ∈ N, there is an MDP that is ν-Mildly Smooth but not (ν -1)-Strongly Smooth. Define an MDP where• S = A = [-1, 1], so that Z = [-1, 1] 2 .• r h (z) = 0 everywhere (any smooth function would have worked as well).• p h (•|s, a) = Unif(βs, βs + 1β) for some β ∈ (0, 1).Note that this transition function is well defined, as both βs, βs + 1β are in [-1, 1] but it is not even continuous, as its density corresponds top h (s ′ |s, a) = 1 [βs,βs+1-β] (s ′ ) 1 -β .Still, we can show that this process is Mildly smooth for ν = 1. Indeed, take every f ∈ L ∞ . We have∥T * h f ∥ C 1 = max max |α|≤0 ∥D α T * h f ∥ L ∞ , L ν (T * h f ) = max {∥T * h f ∥ L ∞ , L 1 (T * h f )} .The first part ∥T * h f ∥ L ∞ is bounded by ∥f ∥ L ∞ by the non-expansivity of Bellman operator. The second one corresponds toL 1 (T * h f ) = sup z1,z2∈Z T * h f (z 1 ) -T * h f (z 2 ) ∥z 1 -z 2 ∥ ∞ .We have, callingf (s ′ ) = max a ′ ∈A f (s ′ , a ′ ) (recall that reward is constant), sup z1,z2∈Z T * h f (z 1 ) -T * h f (z 2 ) ∥z 1 -z 2 ∥ ∞ = sup z1,z2∈Z S f (s ′ )p h (s ′ |z 1 ) ds ′ -S f (s ′ )p h (s ′ |z 2 ) ds ′ ∥z 1 -z 2 ∥ ∞ = sup z1,z2∈Z S f (s ′ )(p h (s ′ |z 1 ) -p h (s ′ |z 2 )) ds ′ ∥z 1 -z 2 ∥ ∞ .We can now evaluate the numerator explicitly:S f (s ′ )(p h (s ′ |s 1 , a 1 ) -p h (s ′ |s 2 , a 2 )) ds ′ = S f (s ′ ) 1 [βs1,βs1+1-β] (s ′ ) 1 -β - 1 [βs2,βs2+1-β] (s ′ ) 1 -β ds ′ = S f (s ′ ) 1 [βs1,βs1+1-β] (s ′ ) 1 -β ds ′ - S f (s ′ ) 1 [βs2,βs2+1-β] (s ′ ) 1 -β ds ′ = 1 1 -β βs1+1-β βs1 f (s ′ ) ds ′ - βs2+1-β βs2 f (s ′ ) ds ′ .Now, note that the function g(s) := βs+1-β βs f (s ′ ) ds ′ has a derivative bounded by 2∥ f ∥ L ∞ in absolute value: indeed, from the fundamental theorem of calculus,|g ′ (s)| = | f (βs + 1 -β) -f (βs)| ≤ 2∥ f ∥ L ∞ , so that it is 2∥ f ∥ L ∞ Lipschitz continuous. Substituting in the previous equation we get S f (s ′ )(p h (s ′ |s 1 , a 1 ) -p h (s ′ |s 2 , a 2 )) ds ′ ≤ 1 1 -β βs1+1-β βs1 f (s ′ ) ds ′ - βs2+1-β βs2 f (s ′ ) ds ′ = 1 1 -β (g(s 1 ) -g(s 2 )) ≤ 2∥ f ∥ L ∞ 1 -β ∥s 1 -s 2 ∥ L ∞ .This proves that sup z1,z2∈ZT * h f (z 1 ) -T * h f (z 1 ) ∥z 1 -z 2 ∥ ∞ = sup z1,z2∈Z S f (s ′ )(p h (s ′ |z 1 ) -p h (s ′ |z 2 )) ds ′ ∥z 1 -z 2 ∥ ∞ ≤ sup z1,z2∈Z 2∥ f ∥ L ∞ 1-β ∥s 1 -s 2 ∥ ∞ ∥z 1 -z 2 ∥ ∞ = 2∥ f ∥ L ∞ 1 -β ≤ 2 1 -β ∥f ∥ L ∞ .Where the passage after the first inequality holds since ∥s 1s 2 ∥ ∞ ≤ ∥z 1z 2 ∥ ∞ (equality holds taking the supremum over z 1 , z 2 as it is sufficient to have a 1 = a 2 to enforce exactly∥s 1 -s 2 ∥ ∞ = ∥z 1 -z 2 ∥ ∞) and the second is due to the fact that being f (s′ ) = max a ′ ∈A f (s ′ , a ′ ) we have ∥ f ∥ L ∞ ≤ ∥f ∥ L ∞ .This proves that the process is ν-Mildly for ν = 1, while we have seen that this is not 0-strongly smooth.The relation between the different settings is depicted in Figure2.As clarified in the main paper, we are going to see that for a proper choice of the partition U h and of the feature map ϕ h , any Mildly Smooth MDP belongs to the Locally Linearizable representation class. We start with the following consideration: as Z ⊂ [-1, 1] d we can find, for all ε, a set Z ε which forms an ε-cover of Z in infinity norm, such that|Z ε | =: N ≤ (2/ε) d .Now, we define the elements of the partition and feature map in the following way. Note that, even if we could make all the elements depend on h, we omit this dependence as it turns out not to be necessary.1. Now, for every z n ∈ Z ε , we define recursively Z n to be the set of points which are covered by z n , formally:Z 1 := {z ∈ Z : ∥z -z 1 ∥ ∞ ≤ ε}, Z n := {z ∈ Z : ∥z -z n ∥ ∞ ≤ ε} \ ∪ n-1 ℓ=1 Z ℓ .As this sets form a partition of Z, we can take U = {Z n } N n=1 . 2. Let ρ(•) be the function mapping each point of Z to the corresponding Z n . We define our feature map starting from equation (23) asEQUATIONso that its length corresponds exactly to d ν * := ν * +d d .We can prove the following fundamental result.Theorem 17. For any f ∈ C ν (Z), there are θ 1 , . . . θ n , . . . θ N , all in R dν * , such that∥f (•) -ϕ(•) ⊤ θ ρ(•) ∥ L ∞ ≤ L ν (f )ε ν .Moreover, the components of each of the vectors θ n satisfy|θ n [α]| ≤ ∥f ∥ L ∞ α = 0 ∥f ∥ C ν α ̸ = 0.Proof. Let z ∈ Z and n = ρ(z). Then, if we take θ n to be the vector with componentsθ n [α] = D α f (z n ) α! , we have, |f (z) -ϕ(z) ⊤ θ ρ(z) | = |f (z) -ϕ(z) ⊤ θ n | = f (z) - ∥α∥1≤ν * D α f (z n ) α! (x -z n ) α = |f (z) -T ν * z n [f ](z)| ,where we have used both the definitions of ϕ and θ n . Then, using Theorem 16, we have|f (z) -ϕ(z) ⊤ θ ρ(z) | = |f (z) -T ν * z n [f ](z)| ≤ L ν (f )∥z -z n ∥ ν ∞ .By definition of Z ε , we have ∥zz n ∥ ∞ = ∥zρ(z)∥ ∞ ≤ ε, which entails the first part of the thesis. For what concerns the second one, we bound the magnitude of the vectors θ n component by component:|θ n [α]| = D α f (z n ) α! ≤ |D α f (z n )| ≤ ∥f ∥ L ∞ α = 0 ∥f ∥ C ν α ̸ = 0 ,where the last comes from the definition of ∥f ∥ C ν Theorem 18. Let M be a Mildly Smooth MDP, and ε ≤ 1/(2C T H) • L ϕ = 1 + 2 √ d ν * . • R h,n = 2 √ d ν * C T . • I ≤ 2C T ε ν .Proof. Let us define the setsEQUATIONwhere L ∞ (Z n ) stands for the supremum norm restriceted to Z n . Now, let Q h+1 [θ h+1 ](z) = ϕ(z) ⊤ θ ρ(z) with θ h+1 ∈ B h+1 for a set B h+1 = × N n=1 B h+1,n . Two facts hold:1. By the non-expansivity of the Bellman optimality operator we haveEQUATION2. By the Mildly smooth assumption (Asm. 5), we haveEQUATIONNow, we can prove the low inherent Bellman error property (Eq. 9). To do this we apply Theorem 17 which guarantees that there are θ 1 , . . . θ n , . . . θ N , all in R dν * , such that∥T h Q h+1 [θ h+1 ](•) -ϕ h (•) ⊤ θ ρ(•) ∥ L ∞ ≤ L ν (T h Q[θ h+1 ])ε ν .Thus, if we take θ h as the matrix stacking all these θ 1 , . . . θ n , . . . θ N , we get that the inherent Bellman error is bounded byI ≤ L ν (T h Q[θ h+1 ])ε ν ≤ ∥T h Q[θ h+1 ]∥ C ν ε ν ≤ C T (1 + A h+1 )ε ν .What is missing is to prove that this choice satisfies θ h ∈ B h .By triangular inequality, we have the following bound on the supremum norm ∥Qh [θ h ](•)∥ L ∞ = ∥T h Q h+1 [θ h+1 ](•) -Q h [θ h ](•)∥ L ∞ + ∥T h Q h+1 [θ h+1 ](•)∥ L ∞ ≤ I + ∥T h Q h+1 [θ h+1 ](•)∥ L ∞ ≤ I + ∥Q h+1 [θ h+1 ](•)∥ L ∞ ≤ C T (1 + A h+1 )ε ν + A h+1 .We apply again Theorem 17 having that the components of the θ h,n which form θ h satisfy|θ h,n [α]| ≤ ∥T h Q h+1 [θ h+1 ]∥ L ∞ ≤ ∥T h Q h+1 [θ h+1 ]∥ C ν α = 0 ∥T h Q h+1 [θ h+1 ]∥ C ν α ̸ = 0,which means, by Equation ( 28), that|θ h,n [α]| ≤ C T (1 + A h+1 ),so that, trivially, we have ∥θ h,n ∥ ∞ ≤ C T (1 + A h+1 ). Therefore, Equation ( 26) requires the conditionA h ≥ C T (1 + A h+1 )ε ν + A h+1 A ′ h ≥ C T (1 + A h+1 ).If we set ε ≤ 1/(2C T H) 1/ν , the previous inequalities are satisfied if we setA h = H -h H A ′ h = 2C T .A h = H -h H = H -h -1 H + 1 H = A h+1 + 1 H = A h+1 + 2C T 2C T H ≥ A h+1 + 2C T ε ν ≥ A h+1 + C T (1 + H -h -1 H )ε ν = A h+1 + C T (1 + A h+1 )ε ν .For what concerns the other term we can simply writeA ′ h = 2C T ≥ C T (1 + A h+1 ).This allows us to say thatR h,n = diam(B h,n ) ≤ √ d ν * A ′ h = 2 √ d ν * C T ,where the presence of √ d ν * is needed to pass from the ∞-norm in the definition of B h,n to the norm two in the definition of diam(B h,n ). Instead, for the feature map we haveL ϕ = sup z∈Z ∥ϕ(z)∥ 2 = sup z∈Z ∥ϕ(z)∥ 2 = sup z∈Z ∥ψ ν * ρ(z) (z)∥ 2 ,as from Definition 25. Note that, looking at the precise definition of ψ ν * y (z) in ( 23), calling ρ(z) = n, this norm can be explicitly written as∥ψ ν * n (z)∥ 2 = ∥α∥1≤ν * (z -z n ) 2α ≤ 1 + 1≤∥α∥1≤ν * (z -z n ) 2α ≤ 1 + 1≤∥α∥1≤ν * 2 2 = 1 + 2 √ d ν * .Where the third passage is due to the fact that ∥zz n ∥ ∞ ≤ 2 as we have assumedZ = [-1, 1] 2 .As a consequence, merging the previous result with Theorem 14, we get the following result.Corollary 19. Under the previous assumptions, with probability at least 1δ, Algorithm 11, for λ = 1 achieves a regret bound of orderR K ≤ O HC T d ν * N √ K + HC T d 1/2 ν * ε ν K .Note that, with this choice we have N ≤ (2/ε) d and d = d ν * . Using this consideration, we can state our final regret bound, which only relies on choosing the optimal value for N in the previous result.From the previous result, if ε ≤ 1/(2C T H) 1/ν , Algorithm 11 achieves a regret bound of orderR K ≤ O HC T d ν * N √ K + HC T d 1/2 ν * ε ν K .Let us now set ε = K -β . The order of the regret bound in K corresponds toR K = O(K 1/2+βd + K 1-βν ).Imposing that the two exponents are equal corresponds to settingβd = 1/2 -βν =⇒ β = 1 2d + 2ν . Therefore, choosing ε = K -1 2d+2ν , which corresponds to N = O(K d 2d+2ν). We formalize this reasoning in our last and main theorem. . Therefore, the regret is bounded by the same quantity.R K ≤ O HC T d ν * N √ K + HC T d 1/2 ν * ε ν K = O HC T d ν * K ν+2d 2ν+2d . 2. ε > 1/(2C T H)This completes the proof.A possible criticism to our main result (Theorem 4) is that the regret bound grows linearly with the feature map dimensiond ν * = ν * + d ν * ,which is exponential in d, the dimension of Z.While this phenomenon may be scary, this dependence is negligible w.r.t. the one on K in any learnable regime. To see this, note that, in the much easier bandit setting, where H = 1 and there is no p h (•) function, [23] shows a lower bound which, for ν = 1, writes asR K = Ω K 1+d 2+d. Now, let us assume that d ≳ β log(K) for some constant β > 0. We haveR K = Ω K 1+d 2+d = Ω K 1+β log(K) 2+β log(K) = Ω K 1- 1 2+β log(K) ≥ Ω K 1-1 β log(K) = Ω K • e -log(K) β log(K) = Ω K • e -1/β = Ω (K) .This lower bound shows that our problem is not learable unless d = o(log(K)). In such case,d ν * = ν * +d ν * = o ν d = o(T β ) for every β > 0.We end the paper by making a short list of some results in the state-of-the-art for continuous MDPs that have been improved with the last theorem. All this result are valid with high probability.• For kernelized RL with Matérn kernel, the best known regret bound is [41] , which ensuresR K ≤ O H 2 K ν+3d/2 2ν+d, which is super-linear for 2d > ν.• For Strongly Smooth MDPs, Theorem 2 from [25] provided a regret bound ofR K ≤ O H 3/2 K ν+2d 2ν+d, which is super-linear for d > ν.• Mildly Smooth MDPs, although just defined in the present paper, are a subset of the Weakly Smooth family, for which Theorem 1 in [25] provided a regret bound that, in our notation, writesR K ≤ O C H ELE K ν+3d/2 2ν+d. This bound is not only super-linear for 2d > ν but also exponential in H.In all previous settings, theorem 20 ensures a regret bound for CINDERELLA ofR K ≤ O HK ν+2d 2ν+2d, which is both sub-linear in any regime and polynomial in H. In this way, we have proved for the first time that the previous settings allow for learnable and feasible Reinforcement Learning.A lower bound for the any of the previous settings has clearly to depend on all K, H, ν, d. In particular, the regret bound is known to decrease for higher ν, while it increases in the other variables. In terms of dependence on H, our bound is already optimal: in this setting we cannot obtain less that the H dependence [42] . On the other side, the optimal order in K is a major open problem in this field.is not guaranteed to belong to any specific sub-region of S. Therefore, it is not sufficient to do a cover restricted to the value functions Z ′ → [0, 1].In fact, all the approaches based on value iteration suffer from this problem. For tabular MDPs, the problem of covering the space of next state value functions was well-known to prevent achieving optimal regret, and was eventually solved by [4] , who found a way to avoid doing the covering at all. Note that tabular MDPs can be seen as an extreme case where Z is divided in regions Z ′ containing just one state-action couple, and making a cover of V h+1 (the space of candidate value functions at the next step) restricted to a single state would trivially achieve optimal regret of order |S||A|K.Still, this move is known to be wrong.For convenience, we will denote Z = S × A and with z any pair (s, a).The existence of optimal policies is more subtle than in the finite-action case[6], but this does not prevent us from defining a meaningful notion of regret.For readability, the bound I on the inherent Bellman error will be dropped when talking about this class in general. 


Decision: This paper investigates regret minimization in continuous and smooth MDPs. The authors first study a linear MDP setting where the model parameter (\theta) may change across different partitions of the state space, and the feature map (\phi) is fixed throughout the space. They design a new algorithm, Cinderella, which generalizes an existing algorithm for the linear MDP setting (Eleanor). The authors then apply their generalization to the continuous and smooth MDP setting by defining the feature space as polynomials, leveraging Taylor's expansion for smooth functions. Their results improve upon prior works for the Mildly Smooth MDP setting (Definition 3, which assumes Bellman operator smoothness). Additionally, they derive regret bounds for Cinderella in the Strongly Smooth and Kernel MDP settings.

As pointed out by the reviewers, this work has some limitations:
1. Although the paper is well-executed, it is unclear which new analysis tools the authors introduce and how other researchers can utilize these tools to enhance their results or develop new algorithms based on these findings.
2. Cinderella lacks computational efficiency, which is a common issue with optimistic algorithms.

Despite these limitations, I believe this paper makes a significant contribution by formalizing an intuitive idea and advancing our understanding of RL algorithms for continuous MDPs, hence I recommend accepting this paper. I encourage the authors to incorporate the reviewers' comments in the final draft and include the analysis mentioned in their discussion with Reviewer 1ViU.

Reviews: review: paper_summary: paper_summary: This paper studied a structural property called local linearity that makes continuous MDPs learnable. In particular, local linearity means that the continuous state-action space can be partitioned into multiple regions and in each region, the Q-function is linear w.r.t. a unique (different) parameter. The paper first proposed an algorithm to learn MDPs with local linearity and proved that the regret is sublinear. Then, the paper showed that mildly smooth MDPs, where the Bellman operator is smooth, are locally linearizable. So that it demonstrated the broadness of local linearity.
strength_weakness: strength_weakness: 1. The proposed algorithm is computationally inefficient. It needs to run over all regions while the number of regions might be exponentially large according to section 4.
questions: questions: Please see the weaknesses part.
limitations: limitations: No further limitations need to be addressed.
paper_summary: paper_summary: The paper discusses the concept of local-linear MDPs which is a general representation class of MDPs that extends previous works on learnable (sublinear regret in $K$) and feasible (polynomial regret in $H$) episodic MDPs.
strength_weakness: strength_weakness: Even though the theoretical development is sound and complete, I think the authors could do better in further highlighting their contributions which I will use the questions below to elaborate.
questions: questions: Can you give some concrete examples (can be purely constructed examples or from real-world applications) of mildly smooth MDPs that are not strongly smooth? Since I'm not very familiar with the literature, this could help me further understand what are the additional new problem instances you are able to characterize no-regret learning.

Moreover, can you discuss what the current gap between your $\tilde{O}(Hd_{\nu_*}K^{\frac{\nu+2d}{2\nu+2d}}+H^{\frac{2\nu+2d}{\nu}})$ is, especially in terms of $K$?
limitations: limitations: There is no obvious limitation in this paper.
paper_summary: paper_summary: The paper introduces the concept of Locally Linearizable MDPs, a class of MDPs that generalizes existing ones like Linear MDPs and MDPs with low inherent Bellman error. In this model, the state-action space is partitioned into $N$ regions, where the Q-functions belong to a class that allows the result of the Bellman optimality operator to be well approximated by a linear function within each region, up to some "Inherent Bellman Error." The authors propose CINDERELLA, a no-regret (computationally inefficient) algorithm designed for this class, achieving regret bound of $Nd\sqrt{K} + \sqrt{d}\mathcal{I}K$, where $N$ is the number of partitions, $d$ is the dimension of the state-action feature space, $K$ is the number of episodes and $\mathcal{I}$ is the Inherent Bellmann Error. 

Next, they present the class of "Mildly Smooth MDPs". This class is similar yet slightly less general than "Weakly Smooth MDPs," which assume that the output of the Bellman operator on a smooth function remains smooth. Still, Mildly Smooth MDPs are more general than "Strongly Smooth MDPs" and thus positioned somewhere between the two. The authors show that Mildly Smooth MDPs are Locally Linearizable for some partition and Inherent Bellmann Error and by that achieve regret of $H v^d K^{\frac{\nu+2d}{2\nu+2d}} + H^{\frac{2\nu + 2d}{\nu}}$ where $\nu$ is the smoothness parameter of the class.
strength_weakness: strength_weakness: The nature and definition of Mildly Smooth MDPs are not very natural, and it is hard to agree that learning becomes substantially more feasible compared to Weakly smooth MDPs. Specifically, the authors mention that in Weakly Smooth MDPs the regret bound must scale exponentially with $H$, which they consider "statistically unfeasible". However the proposed approach results in a regret bound that scales exponentially with $d$, the dimension of the feature space. This raises similar concerns about the practical feasibility of the setting. The authors claim that for $\nu \to \infty$ the regret becomes of order $\sqrt{K}$, but this is not clearly derived from the provided regret bounds, leaving it unclear whether the result generalizes existing results in Strongly Smooth MDPs.
questions: questions: * Does [24] also have similar dependency in $d_{v_*}$? If not, I wouldn't consider your regret as *"improved regret bounds for Strongly Smooth MDPs"*
* Could you clarify how you achieve $\sqrt{K}$ regret in the limit $\nu \to \infty$?
limitations: limitations: For the most part, the paper addresses its limitations.
paper_summary: paper_summary: This paper introduces a notion of local linearization, which is then applied to smooth MDPs. It generalizes the "Eleanor" algorithm into "Cinderella," which, by avoiding a "cardinality of N" term on the suboptimality with respect to the inherent Bellman error, gets sublinear regret for all classes of smooth problems.

EDIT: I appreciate the authors' detailed feedback. My score remains unchanged.
strength_weakness: strength_weakness: This paper is well executed and technically solid, but I believe its main weakness is that the results are not particular surprising to an expert in the area. It seems clear that one can decompose "smooth" MDPs into local linear ones (this has been done, e.g. with zooming bandits and zooming MDPs), and is rather unsurprising that a careful way of handling the analysis makes these objects learnable. I don't seem to see any particular new techniques or insights, and so it is hard for me to be incredibly excited about the result. Still, the paper is executed commendably and for that I lean towards acceptance. 

There are also some limitations with presentation. Chief among them, the authors should do more to emphasize the algorithmic differences between Eleanor and Cinderalla (as they did so well with Eleanor's limitations for regret). The extent of the discussion seems limited to the sentence "Difference with ELEANOR stays in the fact that parameters relative to different regions are learned separately", which (a) bears elaboration, (b) is somewhat hidden in the mass of text, and (c) is not grammatically correct. I would encourate the authors to explain what techniques and ideas are needed to update the algorithm and analysis for the resultant guarantees.
questions: questions: What, if any, are the new analysis techniques developed for this setting?
limitations: limitations: Novelty, somewhat incremental. Moreover, this paper has the computational inefficiency challenges associated with many algorithms in the field, and, like any non-parametric style method, solves exp(dimension, horizon). Lastly, there do not seem to be any lower bounds that characterize the correct exponents.
paper_summary: paper_summary: The paper proposes two novel classes of MDPs in the function approximation setting:
* Mildly Smooth MDPs: in which the bellman optimality operator outputs smooth functions of degree $\nu$.
* Locally Linearizable MDPs: in which there exist a state-action feature mapping into $\mathbb R^d$ and a finite partition of the state-action space that give rise to a Q function approximator class, which is linear in the feature mapping inside each of the partitions (the vector defining the linear mapping is allowed to change between partitions).

An online algorithm (CINDERELLA) is presented and a proof of sublinear regret is given for the class of Locally Linearizable MDPs. Subsequently, it is shown that for any Mildly Smooth MDP, there exist a feature mapping and a partition (of size exponential in $d$) that constitute a Locally Linearizable MDP. 
As a result, a sublinear regret bound of CINDERELLA is derived for the class of Mildly Smooth MDPs: 
$\tilde O(H \nu_*^d K^{\frac{\nu + 2d}{2\nu + 2d}}$  $ + H^{\frac{2\nu + 2d}{\nu}})$, 

where $\nu_* := \lceil \nu - 1 \rceil$.
strength_weakness: strength_weakness: * The regret bound has factors that are exponential in $d$, and sublinearity in $K$ is weak (as to be expected in this level of generality).
* Similar to other algorithms in this line of work, the CINDERELLA is not computationally efficient and far from being a practical algorithm.
* I am not sure what we really learn from such a work; the technical details are complicated even at the level of exposition, and the results are very weak (as to be expected in this level of generality).
questions: questions: - Definition 1 does not actually contain any structural assumption (for any MDP, one can pick a partitioning and feature maps if we don't require them to satisfy anything), so it doesn't make sense calling such MDPs (that have no structural properties) linearizable.
- Line 88 "(iii) we show that all families for which learnable and feasible RL is possible are included in a novel family of Mildly Smooth MDPs defined in this paper": This statement seems way to general - where did you show this?
- Does NET-Q-LEARNING indeed obtain regret bound that is independent of $\nu$ for the Strongly Smooth MDP setting? In this case is it strictly better than CINDERELLA for this MDP class?
limitations: limitations: NA

Comments: title: Reply
Official comment by authors
Reminder to address the author's rebuttal
Maintaining my score
On regret of $O(\sqrt K)$
comment: Thank you for the answer!
Thank you for the detailed rebuttal. 

To be clear, I do not contend the results in the paper did not require technical novelty. 
In addition, my complaints about the inefficiency and weak guarantees were not to say you could have improved them. 

My concerns are all with regards to the fact that the problem studied involves many technical details adding a layer of complication over a setting which is already quite niche, one that fundamentally leads to inefficient algorithms and weak guarantees.
 
Hence, I will maintain my score (but certainly do not oppose acceptance).
We thank the reviewer for this question, which allows us to highligh some future goals of this line of research on MDP with continuous state and action space.

Matching the lower bound for this setting is a challenging open problem. The best-known lower bound for the order in 
$K$ is $\frac{\nu+d}{2\nu+d}$, which is inherited from smooth bandits. Nonetheless, even achieving it for Kernelized MDPs with Matern Kernel - a problem which is a subfamily of Strongly Smooth MDPs, which are in turn a subfamily of our setting - is an open problem (see COLT 2024 Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning). Note that, for the former class of processes, a regret order of $\frac{\nu+2d}{2\nu+2d}$ was never proved before this paper; therefore, our result is novel even when restricted to the family of Kernelized MDPs.

Why is this problem so hard? The root of the issue is to be found in the so-called "covering arguments", which regularly appear in the analysis of regret for value-based methods; for an example see Lemma D.6 from the seminal paper [1] on Linear MDPs.
Indeed, as a value-based algorithm needs to estimate the value function at each step $h$ from the same function at step $h+1$, the corresponding regression problem has a stochastic target. When trying to solve a regression problem of this type, where the random target is *not* independent from the samples used for estimation, we pay a penalization term which depends on the covering number of the function class.

Unfortunately, the function class used in our problem - or in Kernelized MDPs - is very big, and this has a pernicious effect on the final regret bound. In previous papers, this led to also to superlinear regret bounds (Table 1), while here, with the idea of local linearity, we are able to get $K^{\frac{\nu+2d}{2\nu+2d}}$. Doing better than this would mean finding a way to avoid the covering argument, but we do not know if this is possible: again, the lower bound is proved for Continuous Armed Bandits, where covering arguments are not needed.

[1] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement
learning with linear function approximation. In Conference on Learning Theory,
Dear qoL4, please try to address the author's response and elaborate if it changed your opinion and score.

Thank you.
Thanks for the clarifications. By "gap"  I mean the gap between the current bound and the information-theoretic lower bound on the regret.
I thank the authors for their detailed feedback. I still don't feel that the novelty warrants a score increasing, but I do appreciate the authors' clarification.
As the reviewer correctly points, the constant in the bound diverges as $\nu \to +\infty$. 

To overcome this issue, we note that, since the smooth spaces satisfy

$$\nu_1<\nu_2\implies C^{\nu_2}\subset C^{\nu_1},$$

we can limit the magnitude of $\nu$ in case it is much bigger than $K$, and apply the regret bound for a lower value $\nu'$. Specifically, if $\nu=+\infty$, we can apply the bound for $\nu':=\log(K)<\nu$, which results in

$$R_K\le \widetilde{\mathcal O}(d_{\nu'}K^{\frac{\nu'+2d}{2\nu'+2d}})\le \widetilde{\mathcal O}(\log(K)^dK^{1/2+\frac{d}{d+\log(K)}})\to \widetilde{\mathcal O}(K^{1/2}),$$

where we have used line 253 to bound $d_{\nu'}$. The appearance of $\log(K)^d$ should not scare: this term is necessary even  in the simpler case of bandits with SE kernel, as the lower bound in [1] shows.

Before the reviewer's comment, we only considered $1/2$ to be the limit of the order, i.e. the exponent of $K$, as done in most of the works on the field. Still, we think that the result of this discussion is valuable, and we are going to add it to the final version of the papaer.


[1] Vakili et al., On Information Gain and Regret Bounds in Gaussian Process Bandits.
Thanks for the response. The second point seems reasonable. I would raise my score to 6.
The first term in your regret bound scales as $Hd_{v^{*}}K^{\frac{v+2d}{2v+2d}}$. 

$\lim_{v \to \infty} d_{v^\*} = \infty$, so how do you achieve regret $\sqrt{K}$ in the limit $v\to\infty$?