Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs
Authors: Davide Maran
Alberto Maria Metelli
Matteo Papini
Marcello Restelli
Venue: NeurIPS 2024 poster (2024)
Keywords: RL
regret
smoothness
Primary area: reinforcement_learning
TL;DR: We extend and improve several theoretical results about RL in continuous state-action spaces

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.

Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs
Davide Maran Politecnico di Milano, Milan, Italy davide maran0polimi. it
Alberto Maria Metelli Politecnico di Milano, Milan, Italy al wtt.rttmaria.mmellleeeee
Matteo Papini Politecnico di Milano, Milan, Italy matteo. matteo.papinte patieeoppppiiiippiiimi
Marcello Restelli
Politecnico di Milano, Milan, Italy marcello. restelllorrt
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 achieve bounds that are vacuous in some regimes. Furthermore, many structural assumptions known suffer from provably unavoidable exponential depen- dence on the time horizon in the regret, which makes any possible solution unfeasible in practice. In this paper, identify local linearity the feature that makes Markov Decision Processes (MDPs) both learnable (sublinear regret) and feasible (regret that is polynomial in Ht). We define novel MDP representa- tion class, namely Locally Linearizable MDPs, generalizing other representation classes like Linear MDPs and MDPS with low inherent Belmman error. Then, i) we introduce CINDERELLA, no-regret algorithm for this general representation class, and 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 Locally Linearizable MDP by 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 learnable and feasible.
Introduction
Reinforcemeni learning (RL) 35 is paradigm of artificial intelligence in which agent interacts with an environment, which is typically assumed to be a Markov Decision Process (MDP) [30], to maximize reward signal in the long term. By interacting with the environment, 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., work with probability close 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 labular MDPs, when both the state and the action space are finite, optimal where
result was first proved by (4, who showed bound the regret of order Ö /1 is the state space, A is the action space, is the number of episodes of interaction, and H the time horizon of every episode. This regret is minimax-optimal in the sense that algorithm 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
38th Conference on Ncural Information Processing Systems (NcurIPS 2024).

---

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 have continuous state spaces.
36
7
One of the first studied families of MDPs with continuous spaces is the Linear Quadratic Regulator (LQR) [S], 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 Ō V/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 ma majority of
continuous MDPs. A much wider and non- nonpparametric 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) (c.g., in Wasserstein metric). Lipschitz
MDPs have been applied to several scenarios, like policy gradient methods (29 3 228 RL with delayed feedback (22). configurable RL [27]. and auxiliary tasks for imitation learning II (66]. 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 K (F* ), where d is the dimension of the state-action space, which makes this family of problems stattistically unfeasible.
Another part of the literature has focused instead on representation classes of MDPs. In this paper, we call "representation class" 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 de and some unknown vectors. Regret bounds of order o(H²d
3/2 VK) are possible [8], which succeed in moving the complexity of the problem into the dimension de of the feature map. Unfortunately, this representation class is very restrictive: i) linearity is assumed on both the ph. and r'k 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 [1]. both the reward function and the transition function belong to reproducing kernel Hilbert space (RKHS) induced by a known kernel coming from the Matérn covariance function with parameter v > 0. The higher the value of v, the more stringent the assumption, the corresponding RHKS contains fewer functions. This kind of assumption enforces the smoothness of the process, which is stronger for higher values of v. A generalization of this family can be found in Strongly smooth MDPs [25), which require the transition and reward functions to be y y-times continuously differentiable. Although 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 v. 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 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, novel representation class of MDPs depending on both feature map 4 and a partition U4, of the state-action space of the MDP This class generalizes both LinsarMDPs 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
2

---

paper; (ie) 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 results in this field.
2 Background and set-up
Markov Decision processes. We consider a finite-horizon Markov decision process (MDP) 33
[pk)) 1 the sequence of transition functions mapping, for each step ı E [H - == {1..... . 1]. pair (8,a) a) E E to probability distribution ps (+1=) over S, while the initial state 81 may be arbitrarily chosen by the environment at each episode;
M = (S, P. p.
H), where S is the state space, A is the action space -
{ra | is the sequence of reward functions, mapping, for each step / E [H] a pair = (s, a) to a real number Ty(2), and is the horizon. At each episode k E [K] the agent chooses a policy T& (T= which is sequence of step-dependent mappings from S to probability distributions over A. For each step E [H], the action is chosen as a₃ ~ & (-(s,) and the agent gains reward of mean rh (2%) and independent the past, then the environment transitions to the next state Sh+11 ~ pr. (-)))) For a summary of this notation see
Value functions and Bellman operators. The state-action value function (or Q-function) quantifies the expected sum the rewards obtained under a policy т, starting from state-step pair (8, h) E S x [H] and fixing the first action to some a E A::
E Σ re(ze) 2n = (1. =(5.0)
(s Ex Σ (re(se,ae) Sh s, a. =
(I)
where Eg denotes expectation w.r.t to the stochastic process an ~ TA (-18%))))) and sh+1 ~ (-1za) for all h [H]. The state value function (or V-function) is defined Vī == Eawty (1ss) 1Q a)], for all E S. The supremum of the value functions across all the policies is referred to as the optimal value function: (2) := sup, Q7, (z) for the Q-function and (s) == sup, V (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 Th (s, a) is --sugaaussann, and normalized so that S (2) S 1 for every policy n, 2 E Z and h E [H].
Passing to the case where the per-step reward is in [0, 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 a) (s, a) + E Eg (1ss.)) [supa'E.A f(s a')]- In fact, it is easy to show that Q = Tx at every step, while the optimal state-value function is obtained simply as (a) = suPaE.4 (5,
Agent's regret. We evaluate the performance of an agent, i.e., of a policy Te played at episode k E [K], with its expected total reward, i.e., the V-function evaluated in the initial state (st)). The goal of the agent is to play a sequence of policies { to minimize the cumulative dif- ference between the optimal performance V/T (s4) and its performance V, (sf), given the ini- tial state sf chosen by the environment. This quantity takes the name of (cumulative) regret, RK = E (v++ VT< (s))) This quantity is non-negative, and by the normalization con- dition, we can that cannot exceed K every term in the sum is bounded by 1. Note that if Rx 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" family of MDPs that is defined through its relation with feature map or another exogenous element. While the most popular representation class is the Linear MDP, assuming the exact factorization of both pr and r,, negret learning is possible for a much wider family, only requiring a form of approximate linearity on the application of Bellman's 's optimality operator. This class was introduced
I For convenience, we denote 2 S x A and with 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 meaningful notion of regret.
3

---

21 25
Z1
Z/
21
Z4
(a)
Figure 1: In Locally Linearizable MDPs, we have that, shown in (a), the space Z is partitioned into several regions, which do not need 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 the feature map, with parameter that may depend on the region itself.
by 4 as MDPs with low inherent Bellman error. Given sequence of compact sets B₁, C. R and calling Qn (s, a) the linear function on (s, a) 8, the inherent Bellman error w.r.t. {B₁ Jn. is defined as:
I(6)
= max sup inf he[Hl BE d'EB,
- -7:9h+11000)1
where the supremum norm || || indicates the maximum of the function in absolute value over 2. In the realizable case (i.e., I = 0), these processes are 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.
Smooth functions. Let c [-1, 1]d and f Ω + We define multi-index a as tuple of non-negative integers (a1.... aa). We say that f E C" ( for E (0, +00), if is v. -imme continuously differentiable for v. == [V 17. and there exists a constant (f) such that:
Va
||a]]] Vos
Ya,y E 9:
DD DO s()) S T, vllks
the multi-index derivative is defined as D 8e1 u4 dx ".."""""""
The previous set becomes normed
space when endowed with a norm ||/||e> defined as max [maxialsv. f,l,,,, Note that, when E N, this norm reduces to ||/l|ce max | since the Lipschitz constant (f) of the derivatives up order 24 derivatives of order v (which exists as Lipschitz function is differentiable almost everywhere). For these values of the spaces defined here equivalent the spaces C"-1.1((22) defined in 25
correspond exactly to the upper bound of the
3 Locally Linearizable MDPs
As we have stated the introduction, the main limitation the low inherent Bellman error assumption is that it cannot model scenarios where the linear parameter 0 changes across the state-action space. In fact, da (s, a) 0 must be an approximation of the Q-function Q (s, a) uniformly over (s, a) Z. To overcome this limitation, we introduce novel concept of locality to enable the feature map to be associated with different parameters 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:
dh 2 - Rdd:; a feature map which is allowed depend on the current stage (also for its dimension.

---

2. UA: a sequence of partitions of the state-action space Z in M, regions, so that U4 = { 1h I==1- We call Ph. 2 + [Nx] the map linking every element E 2 to the index of set the partition 2/.
These two elements are necessary to introduce the function class we are going to use as function approximator in this setting. Calling 0, = (0h.. 1 I a list of vectors Rd,,, one for each of the regions Za employ, function approximator for the state-action value function, the following set
On = - = (0 ph.))()) where On =0hhn OR.n E BB.n
(4)
Coherently, we will call V42 = (V()) -uppee Q(s, a) Q E Qn: & E S}. For fixed z, we have Qn [=]))(<=>= = dh (=) T0 (x), so that the feature map is allowed to depend directly on 2, while the linear parameter only depends on Pr (z), the function indicating in which of the N₁, regions we are. Bh.n are arbitrary compact sets which contain the candidate values for the linear parameters f, Two relevant quantities for this model are the 2 norm of the feature map and the diameter of the sets B
sup WE HE
(=)ll2
Ru, == diam(Br,n).
Respectively. Analog normalization constants appear in 18 The low inherent Bellman error property can be redefined in this setting as follows.
Definition 1. (Inherent Bellmann Error) Given a family of compact sets BR.n CRdn depending on h E [H) E [Na,, and their Cartesian product B₁, = X Bi.n. we define:
I(
max NE[H]
sup B1++1
inf O,EB,
[[ ThQu+110 -110)))
(5)
Note that, for N₁. 1, our definition exactly reduces Equation (2). as expected. As that case, the term Z plays the role of an approximation error. By assuming a bound on [(), we can now give formal definition of the class of MDPs we are going to study in this paper.
Definition 2. An I Localyy Linearizable MDI is triple (M, {or H (M4) where M is an
MDP, on Z + Rd is a feature map and Un, sequence of partitions of the state-action space Z in N₁, regions such that the corresponding inherent Bellman error (definition 7 satisfies I(ø.U) S I.
As for the class of MDPs with Low Inherent Bellmann error, e (and UI our case) must be known to the agent, while I is not needed. The novel aspect this class is that, 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, principle, any MDP belongs to the Locally Linearizable representation class for T= 1. In fact, if we take Un = {2), the trivial partition containing just the sute-action space as an element. and (2) 0 feature map mapping everything to O), 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.
Linitations of known approaches. Formally, no algorithm in theoretical RL literature can achieve no-regret learning this class of problems, as it is 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, clever strategy called feature extension (example 2.1 from (18) may allow us 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:
6n.n(2) {o
if (z) = otherwise
Th (z) = (,. (z) 6n.N, (2)(n(2))
No
that its dimension expands from da to N₁,a. This way, any function of On (as defined in
Equation 4 linear in Φi (2), with single 9, independent of the region Zn,h- Indeed, we have for Q [ E QA:
Forr readability, the bound Z on the inherent Bellman error will be dropped when talking about this class in general.
5

---

Algorithm/ 1 CINDERELLA (Constrained INDEpendent REgressions with Local Linear Approxima-
tions)
Require: Failure probability 6, Regularization X, Region mapping Ph, Feature mapping dn
I: Initialize A AI for every i [M] E [N,]
for 2, K do
3: Receive initial state of
4: Solve optimization program in obtaining 6h.n for every E [H] and n E [Na]
5: Qn (1) (2) Th.pn (x) Vh E [M]
6: for h 2, H do
7: Choose action a arg max, Qn (s
8: Receive reward r and next state sh
end for end for
10:
Qm(On[(2) =())))))>>)))))))))))))))))))))) 0n (() 10..,, On.N..
This shows every Locally Linearizable MDP with feature map On of dimension da is also an MDP with low inherent Bellman W.r.t. dh of dimension Nz, and the same value for I. If apply the regret bound for ELEANOR 42
Theorem 1J, we obtain:
H
RK δ
Nada S
Σ VNAdAIK h=1
(6)
holding with high probability. The issue is that the second term, growing linearly in K, depends on number of regions as VNz. As we will see the second part of this paper, the application of this model to Smooth MDPs requires Nù. 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.
3.1 Algorithm
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 novel algorithm, CINDERELLA (Algorithm D. Before analyzing it, we need to introduce some notation. Let us call s of r the state, action, and reward relative to step of episode Moreover, we denote 2 = (s af) ) and
& = (= At every episode [K], we compute an optimistic estimation of the Q-function for every step h E [M] Then, we choose actions order maximize this function while fixing sf (line 7). Clearly, what is really important is how this surrogate Q-function is computed (line 4p. Here, CINDERELLA relies on solving an optimization problem (7). which follows an idea similar to the one
of [4)] We want to optimize over three sets variables: On.n: Sn. On,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 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:
max max &i (5f T (ef((a))))) En On.n aEA
k-1
Onn -hh Σ
1 (px(=x)) =30h rh max Ob+1 O aEA
Onn Onn + En.
1EnullAA... v a
Where Ain = Et= (x) = n + XI, is the design matrix of X Xeregularized ridge regression, and f is 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

---

Milll Smooth MDPs (this paper)
Kernelized MDPs
Strongly Smooth
Weakly Smooth MDPs
MDPs
Lipechitz MDPs
Figure 2: Relation between the setting described in this paper and the other settings proposed for reinforcement learning continuous state-action spaces. The dashed line means that inclusion holds, but passing to the larger family brings exp H) lower bound on the regret. As we can see, the Mildly smooth MDP is the largest known setting for which regret of order poly(H) possible. Note that the Strongly Smooth family also contains known families like LQRs and Linear MDPs with smooth feature map 25
discuss in the Appendix The first constraint enforces that 2... is estimated with ridge regression having target the (optimistic) value function estimated for step h + 1, and the second constrain Bn,n 0n,, + En ensures that the optimistic estimate in every region is given by its mean estimate plus uncertainty, while third one bounds the magnitude En.. so that this uncertainty shrinks the more data collect.
Although the structure of the algorithm directly inherited from ELEANOR, CINDERELLA distin- guishes 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 learned independently. Despite intro- ducing 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 high probability regret bound in setting.
Theorem Assume to be in an I Locolalyy Linearizable MDP with Lg O(1) SuPne[NN] Ri,n
Ol and that Assumption I holds. Then, with probability least 1 8, CINDERELLA (Algorithm with x = achieves a regret bound of order
"
H
Rk = T
Σ 1=1
NAdAVK
+
Σ VdnIK
h=1
The proof of this result long, and is deferred to sections B and C
Cf of the appendix. Note that the two normalization assumptions La = O1)) and suPre[H[),ne[N.) Ri,, = O(Vd,) correspond to the ones enforced by [42. While for N₁, superior to the regret bound obtained for ELEENOR in our setting (Equation 66. it prevents the second term, which linear in K, to depend on N₁, This dramatically changes the potential of the regret bounds and, as will see in the next sections, represents the key to achieving sub-linear regret bounds for RL in continuous state-action spaces.
the two reported bounds coincide, Theorem proves
4 From local linearity to Mildly Smooth MDPs
Having proved that our CINDERELLA algorithm enjoys an improved regret bound on Locally Lineariz- able MDPs, we need to see how powerful this new class is once applied to problems with continuous state-action spaces for which representation not given priori. To this aim, we are going define family of continuous-space MDPs, and prove that they are included in the Locally Linearizable class for a particular choice of Un, From now on, we assume, without loss of generality, that
S [-1, 1 ds and A = [-1, 1]d4, that Z []1, We call Mildly Smooth MDP a process where the Bellman optimality operator outputs functions that are smooth.
7

---

Definition 3. (Mildly Smooth MDP). An MDPs is Mildly Smooth of order v for every h E [H), the Bellman optimality operator Tr. is bounded on L (2) + (z).
Boundedness over I (2) - (2) means that the operator transforms functions that are bounded (i.e., belong to - (2)) into functions that are y-times differentiable (i.e., belong to (2).. More- over, there exists a constant CT < <00 such that [lTrfflle I Cr(lffl + 1) for every and every function f E (2). Intuitively, this condition means that by applying the Bellman operator to bounded (possibly non-smooth) functions, we always get functions that are smooth.
[H]
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 Zh Since Z [-1, 1]1 we can find, for every & 0, set ze which is an 8-cover of Z in the infinity norm, such that | = N S (2/e)4, Now, for every z" E 0r, we define recursively 2n to be the set of points which are near to z", formally:
== E 2: 1|= a1 E)
== = 2 2:
S <E} U Zz
(8)
By definition, every point of 2 is matched with point 2" of the cover 2 and, importantly, is assigned to exactly one subset Zn of Z. This way, we have defined partition [2, )rm of 2, one that does not depend on the step h. Secondly, we have to choose the feature map (+(+). To this end, we define (n.(2) as the vector of Taylor polynomials of degree v. centered in z" E 2 for n - p(=) (just "Taylor feature map" in the following). This means that, fixed = E 2 such that p(=) = nt, the map 6(2) will contain terms of the form (z z² for every multi- index ||a||] S v, Note that the feature map does not depend on the time-step h either. The dimension of this feature map, which we call dy., corresponds to the number of non- non-negative multi-indexes such that ||o|| S V2, which is well-known to be de, = -"x+t)) S vd. 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 v. in a neighborhood of diameter e with an error of order e". Seeing the regions 2, we have defined as neighborhoods of the points nn of the cover, the analogy is complete. This argument is made formal in the following result.
Theorem 3. Let M be Mildly Smooth MDP, and E S ((2CTH))// Then, choosing Zn... as in Equation (8) and taking 6% as the Taylor feature map on the same regions, the tuple (M, (Zh,nIn,b (on is an Localyl Linearizable MDP with
La = 1+ 1=
Rr = =V/dr, CT, I 20TE".
This reduction shows how general the class of Locally Linearizable MDPs and enables us to tackle Mildly Smooth MDPs with the CINDERELLA algorithm, originally designed for Locally Linearizable MDPs. By appropriately selecting the parameter E. we can prove the following theorem, bounding the regret of Locally Linearizable MDP with smoothness and state-action space of dimension d.
Theorem 4. Let M be Mildly smooth MDP of parameter v > O satisfying Assumption With probability at least 5, CINDERELLA, initialized with X = 1, Zn.n as in Equation and or. given by the Taylor feature map on the same regions, achieves a regret bound of order:
K S θ Hdy, K TPT H
Before comparing our result with the state of the art, some comments are due. First note that the exponent of K is ++2d which is always in (1/2,1). 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,, < v and ii) the lower-order term H 2u42d 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 not learnable unless d = o(log(K)). Therefore, terms of order 2d can still be seen as o(K*) for an arbitrarily small > O. For the second issue, note that the exponent of H in the lower order term significantly large only if d > v. 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 > 2v).
2v-2d"
We end this section with simple corollary showing how to deal with the "large v/" regime.
Corollary 5. Under the assumption of theorem 4 for v > log(K) we have
Rg = ō ( H log K) K)'K3 kb H?)
8

---

Algorithm
Weakly
Lipschitz
Mildly
Strongly
Kernelized
2-3d/2
1438/2
2438/22 2rrrd
2224/22
2434/2
25
LEGENDRE-ELEANOR
K
K
GOLF
K
3d
K 2
K
13d TM
K Av
K
K 1+
1t4
3
NEARQNLEA
X
K 2+d
K
CINDERELLA (Ours)
X
x
K
K 20
K Ierrid
2.1
25
LEGENDRE-LSVI
X
X
X
K
K 2PTd
KOVI
X
X
K 2012
exp H)
lower bound
Yes
Yes No
No
No
Table I: Table containing the order w.r.t. K of the regret guarantee of each algorithm for each
setting discussed in the paper. Columns correspond to different smoothness assumptions: Weakly and Strongly Smooth MDPs were defined in 225. Lipschitz MDPs in [I, and Kemelized 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.
Proof. Applying theorem 4 for arbitrarily large does not work, dy ~ v makes the bound vacuous. Still, note that, being || llow S || Ila. for v S v, under the assumption of the theorem we can take log(K). At this point, theorem ensures
Rk S Ô log(K)*K
log 24 Finglkyfe
11²) = log log( +11²)
lad due to the fact that K 2122
K K ZioR(K)+2d
K 2loxt
< k
The appearance of log(K) (d) should not scare: this term is necessary even in the simpler case of bandits with squared exponential kernel, the lower bound in (37 shows.
Comparison with related works
Regret bounds for continuous MDPs have been an area of intense research recent years. While many parametric families like LQRs have been shown to achieve poly(H) HK regret bounds 2 tackling this problem in more general cases has been proved to be very challenging.
K are representation class of processes assuming that the transition function (-) as well as the reward function (-) 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 v > 0; by fixing it we can compare this family with the other families of continuous MDPs. The best-known result [4]] in this setting
Kernelized MDPs g
only achieves regret Ō(K
addd/2
), which is vacuous if d 2v. Very recently 38 presented regret
sld bound of order Ö(K T ), but we were not able to verify the correctness of this result. We discuss possible subtle issue of the proof in Appendix F Another family that is based on assuming that Ph and Th belong to some given functional space is the Strongly Smooth MDP 25). This family assumes that Pn(s') (s(()),r(()) E (Z). subtle difference that in 225. the smoothness index was restricted to be an integer, while in our case, it is generic real P > 0. Regret bounds for this
family were shown of order Ö(K EFrd) which is vacuous even for d > v. Since, for the same v, the Matêrn kernel RKHS is 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 [I.. This is only a superset of the Strongly Smooth MDPss for и = 1, as Lipschitz MDPs do not admit higher levels of smoothness. A regret guarantee of order Õ K setting, was achieved by different algorithms recently shown that an exponential dependence on the horizon H is unavoidable (25 Therefore, the Lipschitz MDPs, any of their generalizations, are intrinsically unfeasible.
which turns out to be optimal for this 33 32 in recent years. Unfortunately, it was

---

Increasing the generality even further, we find the family of Weakly Smooth MDPs (25]. which imposes the Bellman optimality operator Th be bounded on (²) C* (2). For fixed v, this assumption generalizes Strongly smooth MDPs (with the same v), and, for v 1, the Lipschitz MDPs. For this reason, also this family affected by an exp H) regret lower bound, while in terms
of K its regret has been bounded as Ö(K -1/3d//2 ) the same as Kemnelized MDPs. Introducing a different notion of dimension, we can also define the family of MDPs with bounded Gullman-Eludde dimension [7]. This family is, certain sense, even wider, but admits worse regret bounds (55
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 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 T6 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
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-thh-ar algorithms for the various MDP families in Table 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 Xmeaning 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 vK in the limit v + oo while being non-vacuous for all finite values of d, V.
6 Conclusion
In this paper, we have significantly enlarged the set of MDPs for which no-regret guarantees possible. After defining the representation class of Locally Lincarizable MDPs (Section 3), we have introduced new algorithm called CINDERELLA (Algorithm D which is able to achieve strong regret guarantee on this setting, being a "local" generalization of the ELEANOR algorithm. In the second part of the paper, have introduced 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 special instance of the Locally Linearizable MDPs, with a specific partition and feature map. Therefore, we were able to achieve, in Theorem 4 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 of-th--o-tee-rttt in terms of generality for feasible settings, but is also able achieve improved regret bounds for Strongly Smooth MDPs and Kernelized MDPs. Crucially, our work proves the first regret bound that is non-vacuous any regime for these two families.
Acknowledgements
Funded by the European Union Next Generation EU within the project NRPP M4C2, Investment 1..3 DD. 341 15 march 2022 FAIR- Future Artificial Intelligence Research Spoke 4 PE00000013 D53C22002380006..
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
10

---

[2] Yasin Abbasi- Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages 1 1-26. JMLR Workshop and Conference Proceedings, 2011.
[3] Kavosh Asadi, Dipendra Misra, and Michael Littman. Lipschitz continuity in model-based reinforcement learning. In International Conference on Machine Learning, pages 264-273. PMIRR, 2018.
[4] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[5] Alberto Bemporad, Manfred Morari, Vivek Dua, and Efstratios N Pistikopoolos. The explicit linear quadratic regulator for constrained systems. Automatica, 38(1):3-20, 2002.
[6] Dimitri Bertsekas and Steven Shreve. Stochastic optimal control: the discrete-time case, volume 5. Athena Scientific, 1996.
[7] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: /606.01540 2016.
[8] Sayak Ray Chowdhury and Aditya Gopalan. Online learning in kernelized markov decision processes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3197-3205. PMLR, 2019.
[9] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only Vł regret. In International Conference on Machine Learning, pages 1300-1309. PMLR, 2019.
[10] Nathaël Da Costa, Marvin Pförtner, Lancelot Da Costa, and Philipp Hennig. Sample path regularity of gaussian processes from the covariance kernel. arXiv preprint arXiv:2312.14886, 2023.
[11] Angelo Damiani, Giorgio Manganini, Alberto Maria Metelli, and Marcello Restelli. Balanc- ing sample efficiency and suboptimality in inverse reinforcement learning. In International Conference on Machine Learning, pages 6618-4629. PMLR, 2022.
[12] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 31, 2018
[13] Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. Kernel-based reinforcement learning: A finite-time analysis. In International Conference on Machine Learning, pages 2783-2792. PMLR, 2021.
[14] Gerald B Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
[15] Ben Hambly, Renyuan Xu, and Huining Yang. Recent advances in reinforcement learning in finance. Mathematical Finance, 33(3):437-503 2023.
[16] David Janz, David Burt, and Javier González. Bandit optimisation of functions in the matérn kernel rkhs. In International Conference on Artificial Intelligence and Statistics, pages 2486- 2495. PMLR, 2020.
[17] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 14:13406-13414 2021.
[18] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
11

---

[19] B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Trunsportation Systems, 23())4909-4993 2021.
[20] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: survey. The International Journal of Robotics Research, (2(11): 2013.
[21] Charline Le Lan, Mare Bellemare, and Pablo Samuel Castro. Metrics and continuity in reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8261-8266 2021.
[22] Pierre Liotet, Davide Maran, Lorenzo Bisi, and Marcello Restelli. Delayed reinforcement learning by imitation. In International Conference on Machine Learning, pages 13528-13555 PMLR, 2022.
[23] Yusha Liu, Yining Wang, and Aarti Singh. Smooth bandit optimization: generalization to holder space. In International Conference Artificial Intelligence and Statistics, pages 2206-22- PMLR, 2021.
[24] Davide Maran, Alberto Maria Metelli, Matteo Papini, and Marcello Restell. Projection by convolution: Optimal sample complexity for reinforcement learning in continuous-space mdps. In Proceedings of the 37th Anmual Conference Learning Theory, pages 3743-3774, PMLR,
2024.
[25] Davide Maran, Alberto Maria Metelli, Matteo Papini, and Marcello Restelli. No-regret re- inforcement learning in smooth mdps. In Forty-first International Conference on Machine Learning, pages 34760-3478 34789. PMLR, 2024.
[26] Davide Maran, Alberto Maria Metelli, and Marcello Restelli. Tight performance guarantees of imitator policies with continuous actions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9073-9080, 2023.
[27] Alberto Maria Metelli. Exploiting environment configurability in reinforcement learning, volume 361. IOS Press, 2022.
[28] Alberto Maria Metelli, Flavio Mazzolini, Lorenzo Bisi, Luca Sabbioni, and Marcello Restelli. Control frequency adaptation via action persistence in batch reinforcement learning. In Interna- tional Conference on Machine Learning, pages 6862-6873. PMLR, 2020.
[29] Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Policy gradient in lipschitz markov decision processes. Machine Learning, 100:255-2888 2015.
[30] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[31] Emmanuel Rachelson and Michail G Lagoudakis. On the locality of action domination in sequential decision making. International Symposium on Artificial Intelligence and Mathematics, 2010.
[32] Sean Sinclair, Tianyu Wang, Gauri Jain, Siddhartha Banerjee, and Christina Yu. Adaptive dis- cretization for model-based reinforcement learning. Advances in Neural Information Processing Systems, 13:3858-3877 2020.
[33] Sean R Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization for episodic reinforcement learning in metric spaces. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3):1-44, 2019.
[34] Zhao Song and Wen Sun. Efficient model-free reinforcement learning in metric spaces. arXiv preprint 1905: 2019.
[35] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
12

---

[36] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for boddel-based control. In 2012 TEEE/RS/ international conference on intelligent robots and systems, pages 0026-5033. IEEE, 2012.
[37] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. International Conference on Artificial Intelligence and Statistics, pages 82-90. PMLR, 2021.
[38] Sattar Vakili and Julia Olkhovskaya. Kernllized reinforcement learning with order optimal regret bounds. Advances in Neural Information Processing Systems, 36, 2024.
[39] Sattar Vakili and Julia Olkhovskaya. Kernelized reinforcement learning with order optimal regret bounds. XrXiv preprint wrXiv:2306.07745, 2024.
[40] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In ICML,, volume 97 of Proceedings of Machine Learning Research, pages 6995-7004. PMLR, 2019.
[41] Zhuoran Yang. Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. Provably efficient reinforcement learning with kernel and neural function approximations. Advances in Neural Information Processing Systems, 33: 13903-13916, 2020.
[42] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
[43] Zihan Zhang, Xiangyang Ji, and Simon S. Du. Is reinforcement learning more difficult than bandits? A near-optnn opttmmll algorithm escaping the curse of horizon. In COLT, volume 134 of Proceedings of Machine Learning Research, pages
PMLR, 2021.
13

---

A
Table of Notation
S, A
State/Action space
Ph: Ph
transition/reward function at step /
H
time horizon
x A
0% Vi
Optimal state-action/state value function at step /
Th
Bellman optimality operator at step h
on
feature map at step
dn
dimension of Φn number of regions at step h
Na
bound over the two-norm of dnn for every h E [H]
Zn.n
Element of a partition of Z at step
Ph
Mapping from 2 to index in [Na]] f2 u Nh.
Un
Q-function associated to given 6,, parameter at step h.
V4, v.
m (x]((,,
Set of candidate 0, step
Bb.
Set of candidate fh.n step restricted to the region n
Rr.
Norm-2 radius of Bh.n
RA.max
SUPRE[NN] R4, Space of candidate asttonsctio value functions at step
Qh. Vn
0%
See equation 10
state/action/rewward relative to step of episode k
(sh a
Φn (=/)
Ah.n
Ridge regression matrix for space Za,n up to episode k Optimization variables of the problem in section B.2
En., Bn.ns In.n
(x)
(x)))
(*()))
m (8,
(VV
Bellman error step of episode ls w.r.t.
(n.n(Qu+1)
equation 12
(Qu+1)
Error done approximating Q4+1 with 0₂ (Q++1)
Phin
{pp (px)) = n)
V (Bh
Quantity defined by corollary 10
N(.
Covering number in infinity norm
E
Good event
14

---

Generic subset of [-1, 1]
d
dimension of a set (usually 2 = [-1,
Index saying how many times function is differentiable
P.
[ 1]
(n)
Lipschitz constant of w.r.t the index v
multi-index
D
multi-index derivative
Ca
space of functions that are v-times differentiable See definition
CT
supremum norm of function, I| = sup lf]
lee
norm over C²
T [S]
Taylor polynomial of order v, centered in (Mr+d)
dv.
B
Locally Linearizable MDPs
As stated in the main paper, Locally Linearizable MDPs are representation class of processes that can be efficiently approximated with linear function some predefined regions of Z.
Precisely, the linearity stays in the iterations of the Bellman optimality operator, which we recall here. For general MDP, we call S, A the state and action space, respectively. Z S A, and Ta the Bellman optimality operator at step h, which is given, for every function Z - [0, 11. by
TT.((z) == (2'(2) max f('s, a') ds'. a'EAA
Recalling the definition given in the main paper. in a Locally Linearizable MDP the state-action space 2 is partitioned into step-dependent number N₁, of regions Σn,5 that we collect into Us (Zn.n : = 1,... .N). To map every element function function Ph Z - [Nr). The importance of these regions stays in the fact that there is a step-dependent feature map on Z + &d such that the optimal statc-action value function is approximately linear in Φi, with a parameter depending on the region. Coherently, we define our approximator functions Qn to be the set of functions on Z that are linear on the regions, namely
2 to its corresponding region we define the
(x(=) = th.. (2) On.pa(e)
2 Z,
coherently, we define VA = (V(s) arg max, (ss Q E 2x). By convenience, we will sometimes stack all these parameters in the list 0 {0), Ju=i and call Q₁ [0,] the corresponding state-action value function. order not to allow the function set 2, contain functions with an arbitrary large slope, we impose the Or.,, parameters to be constrained into bounded sets that we call Bh.n-
We define the following bounds on the parameters of the process.
Definition 4. We call
Lo suPhe[m), (2)l2)
Rrn diam.
Now, calling B,, C Rdda X.N the sets given by
B₁ = X B
n=l
15

---

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.
inf [IQ]ON(() T.Q00 SI. 0 16 EBE
sup
(9)
Note that the low inherent Bellman error MDPs are subclass of this problem: it is sufficient to take NA every step.
B.1
Definition of the quasi-optimal solution
this subsection, we create what we will call a quasi-optimal solution the MDP. Define 0 following recursive way
Th. == arg min max (on( 0, 1h 0, EB SE 2
(10)
So that 0% is constructed by stacking these On, terms. We have the following result.
Theorem 6. The approximately optimal Q-function satisfies
vh [Q[0%](-) Q%(-) S (H-
Proof. We perform the proof by induction, with the case h H + being trivial.
[[Q[0](()) 2 (-) T1Qn+1(0++110) + TvQ 1 - Q7(-)
[Q(0](() T
1 TT(%-1())
s [[Q(0](-) - T1QN+1001+11())))
+ 1 - ThQ)+1())
< 1 11 + 10++11044100 Qh+ 1
where in the last passage we have used the non-expansivity of the Bellman operator. At this point, the second part is bounded
| 00+110041100 Q1+1()) (H - 1)Z,
by inductive hypothesis, while the first one satisfies, by equations (9) and 10
[QQ101(0) - 1 s
Combining the two results gives the thesis.
B.2 Algorithm
We call s/ at, r. the state, action, and reward relative to step h of episode k. Moreover, we denote = = (sf, ax) and of (n())) We define, for any region step h and episode k, the ridge regression matrix as
& Ah. = Σ (x) =
+ AI.
Our algorithm, CINDERELLA (Algorithm D is built top of an optimization problem (Eq. 7 which, the start of each episode k; provides an optimistic version of the state-action value function. We recall it here:
16

---

max
max (bt,8a) T 0(
(II)
En Shn On aEA
k-1
s.t.
Onn -A pmm
Σ ==1
1pp((=h) = (r) + V4+1(5%441)
V Vn+1()) max #h+1 - aEA
Bnn =On,n Enm
IESA,ellAs. S Valin
Note that, with respect to the main paper, we have given a name to the quantity V++1(t) = m 01+11', a) Bp+ (,((a) to make the variables more interpretable. The constant hnn will be defined in the next sections of this appendix.
B.3 Algorithm analysis
We will now continue our work by proving that CINDERELLA is able to achieve a regret guarantee for this setting. First, set up some additional notation.
ck Collecting the solution of the optimization algorithm the variables 8% 0
Additional notation and Eno we define
Qx (i())== = max (s, aed
Moreover, in the rest of the section, once fixed a function V S error step of episode
S - [0, 1]. we define the Bellman
(V) = - aft + ((s Eg Ex
Furthermore, given function Qh+1 E Qu+I, we define
0n (Q.n(Qn1)) arg min max EB,... zE2n, (=n(=) -T(h++)(3))
(12)
and, as before, we collect all these vectors in 0% (Qn+1) Finally, we define
A (n( ThQn+1 Qn)
B.4 Decomposition of the estimated solution
We start by proving proposition which establishes relation between the variables of the optimization problem
17

---

Proposition 7. Let EEt Bn 0h th be in the feasible region of Problem (1
at episode of the
process. We have
R-1
tk Un =hhn + Onn (Qu+z) A
(=) (m)o)))))))A)H+1111
(13)
TI
k-1
Ann
-10
O0 (h+1(
Ahn
Σ
1 (p)(t)) = ==)))==)okk (V (VR+1)
(14)
72
T3h.2
Proof. For simplicity, let us abbreviate Ph.n ((hh(=)) n.. By construction,
th
Ahn
1 + Vi+1((5++)))
Ah.
0h (rn(=T) E. pm (1:)) (a (+t))1)))())))) + Ahs ' Ch (+ (s%+1))
T3
A
Σ Ph.n
Th T3k
where we have used the definition of Bellman's optimality operator. By definition, we have
K. Q0 + (n(
which, when multiplied by Pī.,. lets only the term corresponding to the region remain. Then, by Equation (12). we have
Ph.y Tn Qh (h.)o on,n( Ph An)
Using this fact, we have
h-1
h-1
-1
Σ
Ph.n 26 To (h = Ah
Oh 0h Tn An An
1=1
0ho0 T (h T
Ann
For the remaining term, note that
R-11
R-1
k -1
Σ 0h.0%
To
(h+1)) Ah. -1
- -10nn + 10hn (C + Σ
Ph T0 (h.nChitt))
T=1
Ak. -1
-X0n ( (Th+1) + In
On.n (aan(Qia (hi+1) T22
18

---

The 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 E 2, any time-step h and any we have
(0)(2) hm
(T
[[ -1 ph -V
where
k-1
Ph =
1 (ph((z)) = =n Σ
and in particular
ITih S ph.nt.
Proof. By definition,
k-1 Σ (p)()))==))
(d)(2) TThh (=)))) Th.
S | -1 "dn(s,
= m =
(s (s)..)))l -1
Σ Hpp(=)) = -
At this point, leave the first term and, in the second we rewrite the sum for the indices where the indicator function is not zero, getting
Ph
Σ 0%
((Q
A4.
We can then use Lemma 8 from [42], taking a = of and b, AQQ 1) low inherent Bellman error assumption (Eq, 9 this gives
As 16y S I, by the
P
((#+)))
Ag
which ends the proof of the first part. The second one comes from
Pu.n
[
A/t
-1
o
A(Q
hnm
ph.
Σ
2h A(QH+a)(ET))
S V VIi.OI.
We proceed bounding the second part of the sum.
Lemma 2. For any E 2, any time-step and any n, we have
(0a(2) TT2 S [l)b)())lla Y RRun
and, in particular
| Mla.llla... S x -'Rnnn
19

---

Proof. By definition,
(z)(z) T2 hn
[x(2) T Aha -1 Bnn(Ch
11 -1 "n "on())lAA,, 10 (u+ Qutillln
II -1 =110m,n (aann((i)))) (hht))lll,
S [I 11-11innn( [=)A()) -1A -RA,nR
where the second inequality comes from the fact that Ahin is the sum of Xl and a positive semi- definite matrix, and the last one from the fact that On, (Qu+1) BR.n. The second part comes from
[T22 = =I1Ai.n '' (hnnaall)ll = [10nn( -1 R
The last part of the sum is more complex and, in order to bound it, need to define failure event.
B.5 Failure event
For every h, k, n define the failure event in the following way:
Fb := VE Vh: Σ (p)((x)) (V)
B
n.
Al..
for threshold / /Bh to be defined. The first step to bound the probability of this event to compute the covering number of the function space Vn.
Proposition 8. The coverring number of Vn infinity norm satisfies
log.N(e, Vn) O (Nd
log log (Rn,max/s))
where Ri,,max == SuPnE[N.] R
Proof. Note that the covering number V/ is not higher than the one of Q.. Indeed, let Qf be e-cover for On and define
VR = (s(s) = max Q(s : 2
aEA
Then, taking any V Vn there is Q Qn such that V(s) = max Q(s, a). At this point, taking
((s)
max @(s,a), a
where Q 2j, such that ||Q - 11 S e, have that V Vg by definition and
||Q - @ - ||V p1 S..
Now, the question reduced to covering On. by definition, every Qn E On takes the form Qx = (2) 0p.pa())>
where Ph: Z + [N₂] and every vector 8 is d, - dimensional with the norm bounded by Ra As the domain Z is partitioned into regions Zn, if get family of coverings 2i,n that cover each function in Q₁ restricted to the set Zt.n. can obtain a covering of Qn by defining it in this way
20

---

Ø = {Q Qlz,.. 1002x..:0 = Qn Qn E Ih.a),
Le., we cover every function Q by taking the nearest cover function on each region. a result, the total number of elements in C corresponds to the product I 1 of the elements in the smaller sets, so that we have only to estimate 1 for every n. To this aim, note that the functions in this set are all linear, as we are restricting to 2t,n. so that, applying standard bound for the covering number of spaces of linear functions can find Li, such that
I O (e)
Therefore, the total covering size amounts to
1 =0 0((1.up,, sup Run/e) Nad
nE(NNal
which completes the proof.
Theorem 9, For a choice of
V 8h. = Ō VV V.) 1og(116)
we have P(F (n S 6.
Proof. Let Vi be a cover of Vù in infinity norm, so that [V] = -N(s, V.). Now, for every E Va call
VE V 1i - VIl SE.
In this way, we have
P o5 (m)
Σ Ph 0% (ri - rnsss a + v(shin) (1sp [V
nh th (rx- rn(sh at) + ((shtn)) B Bpr (V('']]
Σ Phunh (v - v(sh+i))
Σ ph (Eeropacles v(631)
+
As we have
se,
[B.-ma (lo -
allows to bound the last two terms with 2 2 e the same argument used in the proof Lemma
The remaining term corresponds, for fixed V and indicating with F the filtration generated by all the events of the process up to step h of episode k.
Sh
(,t
rn (s att + ((sh (1
Fk
meas.
21

---

where the first term is an -vluued stochastic process which is entirely determined by the current state and current action, while the second zero-mean conditioned on the rest of the process, and 1 s-subaaussann thanks to assumption [ This last fact allows to apply Theorem from [ obtaining with probability at least - 6, for fixed V.
2
Σ oh (r) rh (o ah) + (0hi+2) -Bar-Ba Besmaa(lc
det AI-1/21/22 det A 1/2
< 2 log
< dr log(A + dn log((1 + +b+)) + log(d 1)
6
Applying union bound, it follows that the same result holds for every function in V% if we replace log(6-1) with log(N(s, Vx) Merging this result with what we have found before, we have that, with probability at least 6, for V Vn. we have
Σ nh (
v dn log(A-1) du log((1 kLt)) le,(N(e, Va)) log(1/6)
2 22/piine
If just bound Vrh. Vk. can take 1/v/: /: to have that the previous is bounded by
Ph. Ván log(>-1) dn log((1 + kLo)) + log(W v.) log(1/8) +
which completes the proof.
From this theorem, simple corollary follows by just taking union bound over h [H), [N,], & E [K]:
Corollary 10. For choice of
V h. = δ (Va, +log(W(1//VE M.)
(N
we have
P
F
U h.n.k
Fh
himm
Só.
From now on, we are going to indicate the good event as the opposite of the event defined in the previous corollary
N (F
honk
moreover, / / will always be the quantity defined by Corollary 10
We conclude the section
proving the following
Lemma 3. Under the event F., for any z E 2, any time-step h of episode and any n, we have
(0x(2) T33 S [10x())]l
- VB Bh
and, in particular
|T -1
/ //hh..
22

---

Proof. By definition,
(d)(2) T [
E 1 [ph((Eh) n (V 1o+1)
11 -1 *dn())llAt
1(p((=]) = mn) T
k-1
1l -Iobn())llx,,,
Σ
1px((=)) = nV (V++a)
Under the good event E, we have that the second term is bounded by v 1 for the choice defined in Corollary 10 The second part comes from the fact that
|33 mlag,..
h.n
(pn((x)) = = (V++1)
Σ (()o(()))
A2..
$ V Bh.
B.6 Quasi-optimal solution and good event
Thanks to the previous result, we are able show that the quasi-optimal solution is feasible with high probability.
Theorem 11. Consider the optimization problem (II. where Vaii.. is set B + ph...
Rh. Then, under the good event E, the quasi-optimal solution (0%) h=1 (see (TOp) feasible
for III at any episode k.
Proof. We perform the proof by induction the time-step h, starting from h H. Assuming that for every n E [Na]] the choice 07 I,n is feasible we have that the choice
a (z) = Qu-
also feasible. With this choice, proposition 7 ensures that, for every n,
pnn - + fn,,, (Q (0 T1 T2h + T3k
(15)
Now, to show that also 0 is feasible, we have to prove that, substituting each 0n., = 0% in the previous equation, get value for En.n such that IE I Var..
First note that, by definition, 0r = (O (% so that the previous equation simplifies to At this point we have by triangular incquality
En, =TI - T22 hn + T3k..-
(16)
| $ ||T fr ll + +11T2 + I1T
(17)
$ v phi I + x- X-Raa + v Ih.n
(18)
Vahi
(19)
23

---

where the second comes from Lemmas 22 and This completes the proves that each 8% is feasible, meaning that also 0% is, and completes the inductive step.
From the feasibility of i simple corollary follows
Corollary 12. Under the good event E, each episode k, the V V--function Vi( estimated from 01 as solution of solution of the optimization problem (11) satisfies
vs E
(T( - v s -
Proof. By design of the optimization problem, and the fact (0) = is feasible under E,, we have
Vi()) 2 ())
Now, we have
(1) - (s)) < V V(0
max (f(s. max ([0i](s,a) aEA
acA
max (i(s,)) -( aed
< 1Q1(0) - -101000--) s S - 1)Z,
where the last passage is possible by theorem
Moreover, we are also able to prove that the solution found by the optimization algorithm an "almost fixed" point of the Bellman optimiality operator.
Proposition 13. Under the good event F,, the Q Q-function computed with the optimization algorithm each step satisfies Outside of the failure event, we have
(h((2) Tn ThlQu+il(>) SI+2, 2 a (=)n
YZ Z
h.pp.
Proof. By Proposition 7 we have, taking = p=)())
[x((())) Th Th (0^(2) Onn [T(Q
|dn (F) T1
T2 + T T3
s I + (z)(z) En,ml + [1)(())) T
(x) T2 | + (x)(2) (
The first term satisfies, by the constrain in the program,
(sn(s, T En,.! S (EA,,zll3 [[ a) -1 S / a /
The other terms satisfy, thanks to lemmas
123 satisfies
TT + (b) T2 TT2 + (= S (s,
C Regret bound
Using all the results that we have proved, we can finally bound the regret
Theorem 14. Under event E, CINDERELLA, for achieves regret bound of order
h Rk S S
Σ VKND (Lş + vdh) sup Rn, dr + V d (o..o +KHIVA,)
24

---

Proof. By Corollary 12 the regret is bounded by
K
Rx (T VI ( (st)
KHI
V (s 1i (sf)
Note that, under the good event,
(*(h)
1/2 (s = 2 (=h))
V/ (sh)
Prop.
I + V at ph (2b) (l matt
+ Th Th - V/a (s%)
I + 2 a ph (2 |1 t. kona
+ B (1xft VV (444(115))) (
Now, if we define the quantity
ch == R. pp' (118) att ) (V (5') 1441 V (n+1(0++1) + (
we can rewrite the previous relation telescopic sum:
vi(tt) 11 (of) s + 2
a pn (1 m. M. + B (V 2((')) V22x('')) (6')l
I + 2 v a (ntt))) 11 (zf) (oft
-1 -1 st + Vi( 12
same quantity at next time step
H
S HI +
Σ 2 a
lon
+ ch.
This equation allows us to bound the regret, under the good event, as
K
RK S KHI +
2
k hn (2t)
Il (2h))lae
+ Sh.
1=1h=1
We start from the last term, which rewrite, by exchanging the index of the sums
H
K
*
For fixed h the term < is a martingale difference and, it is bounded almost surely in [-C, CJ for some constant C >> apply Hoeffding's 's inequality prove that w.p. least 1 - 8,
-2 K (1/8) S
ch 20 log(1/8).
In our case, due to problem definition have that C may be chosen La sup,, Rr, Imposing that the previous inequality works at every step at the same time, and summing over h, we get, w.p.
1 5,
K
ΣΣ
ch
2 K
log(H/H))
Σ h=1
Lop sup R
(20)
A=
Now, go bounding the other term
25

---

K
2
o h. h (o
o
(=k) (dn(=h)ll
Ion
h.m
k=1h=1
h=1
K
4
4 pn. (e (l (2h))
(21)
A=1
Where the last passage is due to the Cauchy-Schwee inequality. The last sum can be rewritten by summing over the regions instead of the episodes:
K
4a & p. llon (
(1 (
4a h.m
Io Ill Ain. -1,
12:0 mm
where the index i, enumerates the episodes is where of Zn, At this point, recall that have set v aahnn
VBhn + Vehi.. + so that, in particular
a¹ S 3 3ph... +3 RRan
S 3ph I² + 3d + 3 3oo (V V.)) + 3lg((1/)) + -x-33x--p RR
This way, the previous sum
>> > iin
Phin
4a,,nllon olllllaa )| A/n
can be again decomposed in few
terms, according to the decomposition of ofi...
N
Phan Σ
No = 12
Pk.
12
Ph.n
I 11 ((00(((("))) (2f"")] Air
I
Il
(2 I|
An
11,=1
n=1
Note that, by construction of the matrix Aip, we can use Lemma 11 from have
Phan I (2f || >|/,... S 2dp log((1 + K 2//nL2//n)) (de(((ttt))))
where by fixing we have
Pk
(onn(f))) )| Afr.
S 2d, log((1 + ph,,, I2g/d))) s 2d, (Tg + 1).
Therefore, we can bound the whole term as
No.
Phan
No.
12
KII (1 Ar -1 12
Σ ph.n I22 log (KL 1)
24KI d, log K KI3 + 1).
(22)
The remaining terms can bounded in a simpler way: by just calling v = d, doglog(NV(1/ (1/VV, Vv)) log(1/6) + Rh,ns we have
26

---

Ny
Phan
Nk. Phen
12 10 [1(2))))) 112
12
I (2) fn )|( A
Fp
#= Exx
N1.
S 12V
2dh. log( KT2g + 1)
< d4 log( K 2 1),
where we have used Lemma 11 by 1 before. This result, together with Equation 22 can be inserted into the previous Equation 21 to get
K
H
K 40 (n()))))
a (n
2 h=1
Ion (+))1
(
At (tf)
1=
S 224
VK / (KTT W. W.N,) log( K
H
< 24
(KI+ V dn log KT2 + 1).
h=1
Therefore, the full bound on the reget can be written, also thanks to Equation
20 as
Σ Lo sup Rn,, 224 RK 22/K (1/(
Σ(KI+ V (N.K) v dn log LK 1).
h=1
Ignoring terms that are logarithmic in K, H, Top: 1/6 and passing to the ① notation, we get
H
Rx S
VK Σ
sup sup RA. + d...N, + KHIVan)
h=1
Now, note that by definition V : dn + log(N((/VVR, V.) + log(1/6) + Rr, so the previous can be rewritten as
H Σ
Rk δ
VKN
sup (Lo + ddn) sup Ram + dn + ddn Log(V(//KKK +KHIVO.)
4=1
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 å (Corollary 10), we get
Corollary 15. Assume that Lg (1) and suPietH,,eE(Nal Ru.. O(vd.). Then, with probabil- ity at least 8, CINDERBLLA (Algorithm) 7. with X = 1 achieves a regret bound of order
R δ
NrdaV K + Σ Va,IK)
h=1
27

---

D Computational complexity
In this section, we are going to study the computational complexity of CINDERELLA (Algorithm) D. 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 0++1 0h+1($7+1;0) ( (p which breaks linearity B1+,nn.
2. In the third one, IlA,, S <val... h breaks the linearity also in En.a.
The confluence of these 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 inherent Bellman error, denoted by Z. This enables us to forego an exact solution to problem and instead seek an approximate solution. The resulting approximation enror, denoted by can be incorporated into the Bellman error term. From theorem 2 we deduce that if (K--1/2) its dependence in the regret bound is negligible. Therefore, a viable approach might involve constructing an E-grid, denoted by G. over the variable space for K-1/² 1/2 and then to solve the problem with exhaustive search on g. This idea is not completely satisfying, the cardinality of would be of order
| O (OOO(((())))) La= Nids
since we have three optimization variables nn St, On of dimension d, for every n E [Nx]- Unfortunately, this level of generality, strategy with polynomial computational complexity is known. As a comparison, algorithms presented in table are not better. LEGENDRE- ELEANOR [25] based on ELEANOR. optimization oracle. LEGENDRE-LSTE 25 and KOVI 41 can be implemented efficiently, but work only for simpler settings.
also intractable, GOLF 17] and NET-Q-LEARNING [34 require an
E
Mildly Smooth MDPs
In this section, we give our results for Mildly Smooth MDPs. First, we have to start from some notion from calculus.
E.1
Smoothness of real functions
Let Ω [-1, and Ω R. We say that f C")),, for (0, +00) if it is v, -imes continuously differentiable for v. = [v - 11, and there is a constant (f) such that
Va |a| =el=v.,Y,,p Vz, E Ω
D f(v)) s L, -
where is a multi-index, i.e. tuple of non-negative integers (ar,,... as)) and the multi-index derivative is defined as follows
ta.t..taa
D
0x Ox
The previous set becomes metric space when endowed with the following norm
| |100, L.(1)
[f = max
max |a Su.s.
Note that, when N, the previous simplifies
max |f
Salsv
28

---

since the Lipschitz constant (f) of the derivatives up to order V,, = V/ 1 corresponds exactly to the upper bound of the derivatives order (which exist as Lipschitz function is differentiable almost everywhere). For these values of v, the spaces defined here are equivalent to the spaces C²-1.1 (12) defined [5
The following approximation results hold true for this function space.
Theorem 16. Let us consider the Taylor polynomial TV [f((-) centered in E Q of order v.. This can be written as
D f(y)
Ty (f)xx)
Σ
(a 4) ad!
SK.
Then,
Ve E Q ff()) - Ty. [f((= s Lo(f)lx yllb-
As this formulation has the form of scalar product over ||]|| S of one vector with components D f(w) and another of components (xx - y)a, we rewrite the following form od!
D fly ad (x y)a= =: w T W (x).
T- = Σ
(23)
Here, note that the length of the two vectors corresponds to Ifx E N ||a|| S Sv.3l (2 S u.. Moreover, the first only depends on f. while the second depends on æ.
With all this notation settled, we can define what we call Mildly Smooth MDP.
E.2 Between Weak and Strong
We call Mildly Smooth MDP process where the Bellman optimality operator outputs functions that are smooth.
Definition (Mildly Smooth MDP). An MDPs is Mildly Smooth of order v for every [H] the Bellman optimality operator Th, is bounded on 1 (2) - (2).
Boundedness over L (z) - (z) means that the operator transforms functions that are bounded L into functions that y-timmes differentiable. Moreover, there exists constant CT too
such that [TTxflle> & (1Iffll + 1) for every h E [H] and every function f E C²(Z))
To determine how strong our assumptions are when compared to the literature, we prove the following considerations.
E.3 Relation between the settings
Kernelized C - ----ii Miiddl Smooth. Given the definitions of the two MDP families, this point reduces proving that the RKHS generated by the Matérn kernel of parameter v > 0 subspace of C* (S))..
Theorem 8, part (3) from 10 ensures that, for isotropic kernels, in order have sample path E C (12,, sufficient condition for the kernel to be in C2D (S??). The same theorem also shows (proof of Proposition 10) that the Matémn kernel can be written as
Ma(x, v) (Ji(læ v112) + || v112"
f2(11 vl12)),
where /1, E (R). Note that,
d || - --1 = (z. y1)² E cO (22?)
so that [i] - 112) 121 1 C (222). Therefore, these two terms do not affect the overall smoothness of the kernel. This implies that the order smoothness of M,(r, (r. y) corresponds the one of | 2 which is (perhaps the most basic example of) (2²)
C
29

---

For / E N, Milill Smooth C (v- - 1) -eakly Smooth. This part is obvious; indeed, as for
every function we have 1 $ Iffllc--1 (where the last norm is defined (25)) we have
[he le- I. IITnfllc. S OT +1) S CTlfllle- 1.1 + 1),
where in the first passage we have used the fact that for integer || I1e--1,1 -lee- and in the second we have used the definition v - Mildly-smooth MDP.
For // E N, (v 1) Strongly Smooth c. M--iiddy Smooth. Let assume MDP is Strongly Smooth. Indeed, for every function f A R we have:
Tu((s, = ()) + / (16.0)
mmxx f(6', ((6',a')) a')] d'EA
=r((s, + / max 1(6 ('d(, ds'
By triangular inequality, this entails:
|Tall S ||lleo + |/ max f(s', a ())() ds'
where the first term ||lle- = ||rlle- 1. (remember that v integer) is bounded by assumption and so can focus 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 a S v/:
D max (('',a"))nns))) ds' ds'= = max p()())))))( ds' sa'EA
(24)
Isa'dd
Using the abbreviation
f(8') max.'a ((s', a') we get:
1.I. ((s')pn(s')))
D f(s')pn ds
= max al
1.00
max L Da (('))p(ss'l)) ds'
af/5-1
Da Is f(s ) (s' (2)) ds D Ss (n's)p) ds'
sup ofSu-1 21.
max
| 221100
Is
()'p((8'122)) ds'
max
sup
al$v-1 22
2 22lloo
Ss C(s')cpllz1 - 22 l2 ds'
< sup
| 22|1,0
21.2
< (ol
Where the first step is the definition of Ilee, the second comes from the fact that, as we pointed out before, if function f is Lipschitz the I 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 (v 1) 10)=smmn smooth process (the part about pa) and the last one by just bounding the integral with the infinity norm times the measure of the set.
For v E N, there is an MDP that is v- M-idillyy Smooth but not (v- (ettS)Sttooyyy Smooth. Define an MDP where
S A [-1,1], 1). that 2 = 1].
(2) 0 everywhere (any smooth function would have worked as well).
30

---

P a) Unif(Bs, As + 1 3) for some / E (0,1).
Note that this transition function is well defined, as both Bs, As + 1 - B are in [-1, but is not continuous, its density corresponds to
[18.88+110)($)
( ()) = 1
Still, we can show that this process is Mildly smooth for v = 1. Indeed, take every f E L We have
1hh flle= max
[o|50 D flle,,
max
L1
The first part [7, z is bounded by || by the non-expansivity of Bellman operator. The second one corresponds to
fx f22)
(TTR)) sup 21.2gE2
|| - 22 00
We have, calling f(s') max EA f(s.s())))) a') (recall that reward constant),
- -
Is ((8")) (n(()))((''()))))) do' - [s (n (z'122) ds' 22 22
sup 21,
sup
21 222 222100
21,2E2
Is f(s') (2) - (n(ss1222 ds'
sup 21.
|||1 22 22/100
We now evaluate the numerator explicitly:
Is ((s'))nn(6()s1,a)) pr (8'18,, a2)) ds'
1 i(2))
1881 1s11
Bag Boa 1- ds
3
3
10 ds
f(8")
1-
1 f(s')
1 1802 +1 --
1 1- ds'
(fpeett 1 f(s') ds'
p f(s') ds'
B
Now, note that the function g(s) = fā. 1 f(s') ds' has derivative bounded by 2 fll in absolute value: indeed, from the fundamental theorem of calculus,
|s((s) = 1/(3s + 1- -133) - 2
s
so that it is 21] f1 Lipschitz continuous. Substituting in the previous equation get
(p f(d) ds' - 8
[s [(6))pn(6((s))a))) pm (5'182,, a2)) ds' S
f(s)) ds'
1- B
88g
221
(0(s1) [($2)) 5
|182 s2llzz.
1
31

---

This proves that
[=1) - [(2)
Is (pn (5'12)) - ph (5(1222)) ds'
sup 22.
sup
22 lc
21,2
| 2221
211/f| 1-8
|1 - 82|120
sup
2| - 22 02
21,
fll LM
2
1- $
8
Where the passage after the first inequality holds since |s 82/1>0 S || 22 loc (equality holds taking the supremum over 21, 22 as it is sufficient have ai 02 to enforce exactly ||81 - 82/1 = ||2] - 22/loo) and the second is due to the fact that being f(s') = ma as',aa') we have || < z= This proves that the process is u-Mildly for v = 1, while we have seen that this not 0 stronnyyyy smooth.
The relation between the different settings depicted in Figurd
E.4 Regret bound for Mildly smooth MDPs
As clarified in the main paper, we are going to see that for proper choice of the partition Un and of the feature map on. any Mildly Smooth MDP belongs to the Locally Linearizable representation
class. We start with the following consideration: as 2 [-1, 1]d we can find, for all E, set 2 which forms an E-cover of in infinity norm, such that | =: N S (2/e)*.
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 it turns out not to be necessary.
1. Now, for every z" E Z", we define recursively Z, to be the set of points which are covered by z" formally:
: (= 2 -|2- == 1oo Seh, 2n = {= E Z: ||| 1oo Se) ( Zz
As this sets form a partition of Z, we can take U 22,, J
2. Let p(-) be the function mapping each point of Z to the corresponding 2n,. We define our feature map starting from equation (3 as
((z) = 15t, ((=)(2)) (z), p(z)
(25)
that its length corresponds exactly dy, (c.
can prove the following fundamental result.
Theorem 17. For any f E C² (Z), there are f..... .. .n.... ... AN, all in BR such that
II((-) - (6.) (pc)) S (n)e)"
Moreover, the components of each of the vectors On satisfy
0 0m[a]] < |/ a= 0
[1ffle-
a + 0.
Proof. Let 2 Z and p(2). Then, if we take f to be the vector with components
D f(²")
0, [a] =
a!
have,
32

---

If(z) - -==) 0cxz)
=I[(=) -0(=) 0nl
DaS(=") ad
f(z) Σ
(x - )")a
|alis
[f(z) T [f(()),
where we have used both the definitions of Φ and On. Then, using Theorem 16 we have
(f(=) - 1f(z) Th [f](2)
- (f)ll 2"11
By definition of 2 we have || - =- = || x(=)]l o(>) S e, which entails the first part of the thesis. For what concerns the second one, bound the magnitude of the vectors l, component by component:
f(²")
[l]flI a=
10, [a]]
< (DDDS(="))
<
ad!
UISlle #0
where the last comes from the definition of l|f[le-
Theorem 18. Let M be a Mildly Smooth MDP, and e < H1) Then, setting
1. Zn.n in Equation
2. du to be the feature map defined in Equation 25
the tuple (M, (Znnkmns (dh is an Locally Linearizable MDP with
L 11=+22 1+22ddn
Rh,n =2Vdu, CT.
I 20TE".
Proof. Let us define the sets
BR.n == ER.. (ll I An, 1011 S An
(26)
= where (2,) stands for the supremum norm restriceted to Zn. Now, let <(z) Op(=) with 0x+1 B for Ba+1 = -x==BBa+,, BB+1,. Two facts hold:
By the non-expansivity of the Bellman optimality operator we have
|| - 10 < IQ]0,+1lll<> I A4t1-
(27)
2. By the Mildly smooth assumption (Asm. 5). we have
| [x+ill s CT 10++ + +1) 5
(28)
Now, we prove the low inherent Bellman error property (Eq.1), 9). To do this we apply Theorem which guarantees that there are 0,,... On ON, all Rdv., such that
17
T 1(-) (xx()) 1 S L. (TT.(((
Thus, if take O₂ the matrix stacking all these 0 Ony... ON get that the inherent Bellman error is bounded by
I < L. (TAQ < ITQQ00 & CT(1 + Ant1)e".
What is missing is to prove that this choice satisfies On E Br.
33

---

By triangular inequality, we have the following bound on the supremum norm
= I 10 [()) Qs Qn(OR](]Ix + 11ThQu+ 10 1()
$ I + Q 10+1
$ I + || QQ++1 1n+1 1n 1.)l0
CC 111))=" + An41
We apply again Theorem 17 having that the components of the On,m which form 0, satisfy
[h @x+illle= S ||T O1+tllle-
On. [a -
( On+1llle
a + 0,
which means, by Equation (88 that
0 [0,n S CT(1 Ant1),
so that, trivially, we have |l I CC((1AA44) Therefore, Equation 26
requires the condition
A. 2 CT(1 + Ant1)s" + An+1
A 2 CT(1 + An+1).
If we set S 1/((C the previous inequalities are satisfied if we set
- h
A H
A = 2CT.
Indeed, we have
h
A
H
hh
H
H
AA-1 +
H
AA-1 2CT
2CTH H
2 An-1 + +20T8"
H
2 A + CT(1 +
)m
H 4 + Cr + Ant1)E".
For what concerns the other term can simply write
An = 2CT 2 Cr(1 Ant1).
This allows to say that
Rr.. diam(Br,n) S Vdy, Ah, = 2V CT,
where the presence Vd,, needed to pass from the oc-norm in the definition of B to the norm two in the definition of diam(Bs,n). Instead, for the feature map have
La sup [1)(2
sup [|0(2)]12
262
sup [1
(
34

---

as from Definition 25 Note that, looking at the precise definition of 2 (2) in 23 this norm can be explicitly written as
calling p(z) =
1/ (=)ll==
Σ V Jallssu
(z
27)2a
+
Σ (2-21)) 221
S1+
Σ
= -VV2
Where the third passage is due to the fact that ||| 2² 1oo I 2 as we have assumed Z = [-1,
As consequence, merging the previous result with Theorem 14 we get the following result.
Corollary 19. Under the previous assumptions, with probability least 6, Algorithm 77 for achieves regret bound of order
RK S δ (HCTd, + HCTd/.
Note that, with this choice we have N S (2/e)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/(2CTH)*/* Algorithm achieves regret bound order
R S 5 (HCCTd,,NNK HCTd// K)
Let us now set K-9. The order of the regret bound in K corresponds to
Rx O(K1/2+9d + K2-$u).
Imposing that the two exponents are equal corresponds to setting
3d 1/2 Bv
3
2d + 2v
Therefore, choosing K 2442v, which corresponds to N = =OKK zatw). We formalize this reasoning in our last and main theorem.
Theorem 20. Let M be Mildly smooth MDP. With probability least 1 6, Algorithm 77 for achieves a regret bound of order
R & Ō (Hdy. K
H 2v42d
Proof. Let us set & = K x and, consequently, N = O(K (e/ea happen
Then, two scenarios may
1. 1 /V Corollary 19 ensures a regret bound of order
Rx < δ HC,d, NVK + HCTd),22 = ō HCTdy,
2. > H/ the regret is trivially bounded by K. Still, we have chosen K- -F the previous inequality entails K S (2C+H) 2-124 bounded by the same quantity.
Therefore, the regret
This completes the proof.
35

---

E,5
Discussion on d
possible criticism our main result (Theorem is that the regret bound grows linearly with the feature map dimension
dy. --//t
U
which is exponential in d, the dimension of Z.
While this phenomenon may be scary, this dependence is negligible w.r.t. the K in any learnable regime. To see this, note that, in the much easier bandit setting, where = 1 and there is no PA (-) function, 23 shows a lower bound which, for 1, writes
Rx = Ω K ltd
Now, let us assume that d 2 B Blog(K) for some constant 3 > O. We have
R = Ω K $11
1-Alon(() 2-Alog(k)
Q [ S-alog(R]
2 Ω2 K Bloc(k)
= -2 K
lou( lox(
= 2 K c2/00 = [K)
This lower bound shows that our problem is not learable unless = o(log(K))) In such case, dz. = (Mr+t)= = (1d) = o(T for every / > O.
E.6 Final considerations
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 ensures
RK s δ H
o 3d/2
2rtd
which is super-linear for 2d > n.
For Strongly Smooth MDPs, Theorem 2 from 25 provided a regret bound of
Rx < ①
k
+t24
which super-linear for d > v.
Mildly Smooth MDPs, although just defined in the present paper, are subset of the Weakly
Smooth family, for which Theorem in [25] provided regret bound that, in our notation, writes
Rk < δ
CHEK
K
This bound is not only super-linee linear for 2d >> V/ but also exponential in H.
In previous settings, theorem ensuress a regret bound for CINDERELLA of
RK S δ [K
which is both sub-linear in any regime and polynomial H. this way, we have proved for the first time that the previous settings allow for learnable and feasible Reinforcement Learning.
E.7 Lower bounds
lower bound the any of the previous settings has clearly to depend on K, H, v, In partieular, 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 major open problem in this field.
36

---

In fact, the only proved lower bound in the continuous setting involves smooth armed bandits, which can be seen as a special case of the Strongly Smooth MDPs for H 1. This bound [23], of order K 2eld is matched in the bandit case (same paper). As comparison, our bound only achieves K 17122, i.e. we pay a double dependence on d.
This poorer regret bound is not simply an artifact of the analysis, but rather a fundamental challenge that arises when moving from bandit problems to reinforcement learning (RL). In RL, the agent must estimate the value function at step / using its own estimates for the value function at the next step, h + 1. This forces make a covering argument on the space of candidate state-value functions (moving target problem, also topic of the next section F). which has detrimental effect on the regret bound.
At this point, there are essentially two possibilities:
1. The covering argument cannot be avoided, and regret order of K 2v42d is the best we can achieve for Kernelized MDPs, Strongly Smooth MDPs and Mildly Smooth MDPs. In that case, it would be proved that continuous armed bandits are essentially easier than MDPs with continuous state-action spaces.
2. As for tabular MDPs 4 more refined analysis allows to avoid doing the covering rid argument. In this way, a regret bound of order 2v+id can be proved, as the problem becomes as difficult as smooth bandit. This would mean that, as for the comparisons multi armed bandits/tabular MDP and linear bandit/linear MDP, there is no substantial difference between continuous armed bandits and MDPs with continuous state-action spaces.
We leave this as interesting open problem for the future advancements of the research in theoretical RL.
F
Some observations on (38]
38 is one of the most recent papers in the literature on RL with continuous spaces. This work, published at the celebrated Conference on Neural Information Processing Systems (2023) reported a
very strong result, proving regret bound of order Ö(K (K 20+4 for Kemeliizd RL with Matérn kemnll. If true, this bound would mean that possible to match the lower bound for the much easier case of Kernelized bandits.
old
In this section, we will pose some objections to the analysis of that paper. To this aim, we are going to refer to the updated version [39 of the same work, where the authors have corrected some minor mistakes of the published paper.
The result giving the regret bound is Theorem 2 and, precisely, equation (21) in that paper. Without digging into the algorithm that they use, we can say that, like one, it is based dividing Z into sub-regions, there called Z' (even if the way these regions are created is totally different). As the authors recognise in their section 4. the hardest point of the analysis is the called "moving target problem": to fit the current estimate Qi of the state-action value function, the authors use Th + PA. 4 which is a random function (as 1 is estimated as well). Therefore, standard confidence bounds do not apply straightforwardly. The way [39], as most papers, deal with this issue, make a covering of the space Vh+1 of the state-value functions at the next step, and then make union bound over all the possible values for Vh+1-
The tricky part of their analysis is that, instead of using the covering number of Vh+1, they fix one region Z' and cover the space of functions restricted to Z', as it is said in the first eight lines of section 4.2. In this way, as said in the same part of the paper, the e e-covering number of the function (To//T////////oo (2')) (where (2') corresponds to the number of times region Z' is visited), results for be of order log(
class, for O /log(?
Unfortunately, we find no justification for this choice. Line 7 of their algorithm, when the estimated (.)()) is computed, relies on equations (15-16), which do a Gaussian process regression with target Th(2') + V ($)+1) for all z' Z' visited in the process. The issue here is that, while know that z E z', we cannot say anything about 4/ which is sampled from Ps+1 p- The new state
37

---

is not guaranteed to belong to any specific sub-region of S. Therefore, it is not sufficient to do a cover restricted 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 way to avoid doing the covering at all. Note that tabular MDPs can be seen an extreme case where Z is divided in regions Z' containing just one state-action couple, and making a cover of V4+1 (the space of candidate value functions at the next step) restricted to a single state would trivially achieve optimal regret of order |/ Still, this move is known be wrong.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: every claim made in the abstract corresponds to result proved in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. 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 encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
38

---

If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All proofs are reported in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Thcorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descriregiong the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
39

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they (c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/
public/guide httaa//ggiide//ooouuuuiissssssss iisiionPoicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
/ /nips.cc/puut stsips.cc/publli/uuddeeee Seeguidddde//ddSubimmi ietobbmmssioooooiiiiiico
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
No experiments.
40

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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).
should be clear whether the eπror bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed 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 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 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
41

---

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

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, palasets.papersstt paperswi thcode. com con/datases has curated licenses for some datasets. Their licensing guide can help determine the license of 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 available online, the authors are encouraged reach out to the asset's s creators.
13. 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 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The work does not include crowdsourcing.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or 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 crowdsoureing nor research with human subjects.
43

---

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


Reviews:
[{"review_id": "KboIbMg0l6", "reviewer": "Reviewer_RTnn", "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.", "questions": "Please see the weaknesses part.", "limitations": "No further limitations need to be addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem is important.\n2. The new concept of local linearity is interesting and indeed capture a broad class of MDPs according the paper.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q: _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._\n\nIt is true that the number of regions is exponential in $d$. This makes the computational complexity exponential in this parameter. Still, we argue that this is not a downside w.r.t. the state of the art.\n\n 1. State of the art: other algorithms for other very general continuous RL settings require access to an optimization oracle [1, 2] over the space of candidate $Q$ functions. This means that if one is interested in approximating a $C^\\nu$ function, as in our case, an optimization over a space of $O(2^{(1/\\varepsilon)^d})$ functions is needed (if one is satisfied by $\\varepsilon-$cover, otherwise $+\\infty$).\n    \n 2. Magnitude of $d$: if, in linear MDP problems, it is well known that $d$ may be very large, almost of the order of $K$, the same thing does not apply here. In fact, the lower bound, even for the simple case $\\nu=1,H=1$, entails that $d$ is much smaller than $\\log(K)$:\n    $$R_K=\\Omega(K^{\\frac{d+1}{d+2}})\\quad \\text{and } \\quad  d\\approx c\\log(K) \\implies R_K=\\Omega(K^{\\frac{c\\log(K)+1}{c\\log(K)+2}})=\\Omega(K).$$\n    This means that, unless $d\\ll \\log(K)$, _the problem is provably unlearnable_.\n    Therefore, an exponential dependence in $d$ is not as bad as it may seem.\n\n\n[1] Jin et al. \"Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.\"\n\n[2] Du et al. \"Bilinear classes: A structural framework for provable generalization in rl.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sMAsWLMIAx", "reviewer": "Reviewer_MjfW", "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.", "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.\n\nMoreover, 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": "There is no obvious limitation in this paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper considers important complexity questions associated with the continuous episodic MDP, and is very well-written. Compared to the much more well-studied tabular episodic case, the complexity of continuous episodic MDPs is much more challenging to characterize. The authors identified a class of mildly smooth MDPs and show one can achieve no-regret learning in this regime. The regret bound still has an exponential dependence in $H$ but the authors demonstrated through a continuous bandit special case this exponential dependence is unavoidable. The class of mildly smooth MDPs is larger than the previously studied classes such as kernelized MDPs and strongly smooth MDPs where no-regret learning is possible.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We point out that the regret of our algorithm does _not_ depend exponentially in $H$. Exponential dependence cannot be avoided for the Lipschitz class, and this work is also born to find a class of MDPs that is able to elude this undesirable phenomenon.\n\nQ: _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?_\n\nTo have an idea of an MDP that is Midly Smooth but not Strongly Smooth, one can think about transition functions of the form\n\n$$s'=f(s,a)+U,\\qquad U\\sim \\text{Unif}(b_1,b_2).$$\n\nIndeed, the density function of the uniform noise is _not continuous_, which makes this class of MDPs not Strongly Smooth. Still, we argue that if $f(\\cdot,\\cdot)$ is not itself discontinuous, this class of MDPs is Mildly smooth. For more details, see the example at the end of page 29 and the whole page 30. Of course, this is true not only for uniform noise, but also for any noise admitting a bounded density function, even discontinuous. We argue that this family of processes is rather realistic and, therefore, the generalization has practical relevance.\n\nQ: _Moreover, can you discuss what the current gap between your_ $\\widetilde O(Hd_{\\nu_*}K^{\\frac{\\nu+2d}{2\\nu+2d}}+H^{\\frac{2\\nu+2d}{\\nu}})$ _is, especially in terms of_ $K$?\n\nWe do not understand which \"gap\" the reviewer was interested in, so we kindly ask the reviewer to clarify it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iBCvqviisA", "reviewer": "Reviewer_1ViU", "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. \n\nNext, 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.", "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\"*\n* Could you clarify how you achieve $\\sqrt{K}$ regret in the limit $\\nu \\to \\infty$?", "limitations": "For the most part, the paper addresses its limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-crafted and clearly positions itself within the existing literature. It employs a well-structured pedagogical approach. It first presents a straightforward solution for Locally Linearized MDPs and proceeds to point out that this naive approach's regret bounds are insufficient for deducing a non-trivial regret bound for Mildly Smooth MDPs. This leads to the introduction of their algorithm, which offers improved regret bounds and leads to their main result.\n    \nThe authors conduct a comprehensive analysis of the regret bounds, discussing each component to assess its necessity and provide a comparison with prior work. For the most part, the paper is transparent and addresses its limitations.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q: _However the proposed approach results in a regret bound that scales exponentially with \n, the dimension of the feature space. This raises similar concerns about the practical feasibility of the setting. (...) Does [24] also have similar dependency in_ \n$d_{\\nu_*}$? _If not, I wouldn't consider your regret as \"improved regret bounds for Strongly Smooth MDPs\"_\n\nYes, also [24] enjoys a regret that is exponential in $d$. This can be seen either from the proof of Theorem 11, where the regret scales as $\\sqrt{Vol(S\\times A)}=2^{d/2}$ or from the fact that the length of their feature map is $\\binom{N+d}{N}\\approx N^d$ (see last paragraph before section 4.3).  \nIn fact, this exponential dependence **cannot be avoided**. Indeed, if we look at Gaussian bandits with the squared-exponential kernel, a problem family that is strictly contained also in the Strongly Smooth class, [1] ensures an $\\exp(d)$ regret lower bound (see Table 1 of [1]).\n\nRegarding the comparison between our regret bound and the one of [24], we have to remark that not only our regret order is always strictly better, as\n\n$$\\frac{\\nu+3/2d}{2\\nu+d}>\\frac{\\nu+2d}{2\\nu+2d}\\qquad \\forall d,\\nu>0,$$\n\nbut also, and most importantly, our result is always sub-linear, while [24] gets vacuous for $d>2\\nu$. Therefore, our improvement over the regret bounds is not limited to avoiding the exponential dependence in $H$.\n\nQ: _Could you clarify how you achieve regret_ $\\sqrt K$ _in the limit_ $\\nu\\to \\infty$?\n\nThe regret order, for $\\nu\\to +\\infty$, gets\n$$\\lim_{\\nu\\to \\infty}\\frac{\\nu+2d}{2\\nu+2d}=1/2.$$\n\nIn general, this is the condition that papers on continuous space / RKHS seek, as it shows that whenever functions tend to be infinitely smooth the optimal order is recovered.\n\n[1] Vakili et al., On Information Gain and Regret Bounds in Gaussian Process Bandits.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MZu4fGMgCO", "reviewer": "Reviewer_TQwD", "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.\n\nEDIT: I appreciate the authors' detailed feedback. My score remains unchanged.", "questions": "What, if any, are the new analysis techniques developed for this setting?", "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.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "This paper is written very clearly, exposes all the strengths and weaknesses of its contributions, and makes connections to prior work in a thorough and honest fashion. The paper explain, in particular, why Cinderella is inadequate, and how the parameter learning is decoupled in a way to permit efficient learning. This requires additional technical subtlety in the analysis, but with it comes a bound which would be intractable otherwise.", "weaknesses": "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. \n\nThere 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q: _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\" ... What, if any, are the new analysis techniques developed for this setting?_\n\nWe thank the reviewer for giving us the opportunity to clarify this point. Section 3.1 does not explain the novelty of our approach, which is somehow hidden in the appendix; we are going to explain it here and add it to the final version.\n\nBefore this work, there were two main approaches to continuous MDPs. \n1. Discretization-based (e.g., the Zooming algorithm mentioned by the reviewer) algorithm cannot fully exploit smoothness: due to the \"zero-order approximation\" the regret scales as $K^{\\frac{1+d}{2+d}}$ even for $\\nu\\gg 1$, which makes them suboptimal. \n2. Linearization-based approaches [3], which are able to exploit the parameter $\\nu$, achieving regret $\\sqrt K$ for $\\nu \\to \\infty$, but fail to give a sub-linear regret bound for $d>2\\nu$. The reason can be found in a well-known problem of linear models with misspecification [1].\n\nOur novelty lies in **combining the two approaches by** splitting the parameters of the feature map (linearization) across different regions (discretization). In this way, we are able to get the best of both worlds: using our local linear approximation, we move from the zeroth-order approximation by Zooming/Net-Q-Learning to an arbitrary order $\\nu$, which gives sharper bounds for smooth functions. At the same time, the locality of the feature map bypasses the problem in [1], since it allows us to avoid using tools from linear algebra (like \"optimal design\" argument) [1,2], which has brought the same regret as [3].\nThis feature of _Cinderella_ shows that the former techniques can be replaced with the \"pigeonhole argument\", widely employed in the field of tabular MDPs. As a result, we get the first regret bound for the setting that achieves $\\sqrt K$ for $\\nu \\to \\infty$ while being always sub-linear.\n\nIn particular, we think that bridging these two approaches - which do not seem to have anything in common - and finding a strategy to elude the lower bound presented in [1] are relevant technical contributions to the learning theory community.\n\nQ: _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)._\n\nAs the reviewer correctly states, the same computational challenges exists also for celebrated algorithms which work at a similar level of generality. We remark that [4, 5] require access to an optimization oracle over the space of candidate $Q$ functions. This means that if one is interested in approximating a $C^\\nu$ function, as in our case, an optimization over a space of $O(2^{(1/\\varepsilon)^d})$ functions is needed (if one is satisfied by $\\varepsilon-$cover, otherwise $+\\infty$).\n\nQ: _Lastly, there do not seem to be any lower bounds that characterize the correct exponents._\n\nAs we write in Appendix E.7 Lower bounds, 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.\n\n\n[1] Lattimore et al., Learning with Good Feature Representations in Bandits and in RL with a Generative Model\n\n[2] Zanette et al., Learning Near Optimal Policies with Low Inherent Bellman Error\n\n[3] Maran et al., No-Regret Reinforcement Learning in Smooth MDPs\n\n[4] Jin et al. \"Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.\"\n\n[5] Du et al. \"Bilinear classes: A structural framework for provable generalization in rl.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2AfHLQyZ8j", "reviewer": "Reviewer_qoL4", "summary": "The paper proposes two novel classes of MDPs in the function approximation setting:\n* Mildly Smooth MDPs: in which the bellman optimality operator outputs smooth functions of degree $\\nu$.\n* 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).\n\nAn 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. \nAs a result, a sublinear regret bound of CINDERELLA is derived for the class of Mildly Smooth MDPs: \n$\\tilde O(H \\nu_*^d K^{\\frac{\\nu + 2d}{2\\nu + 2d}}$  $ + H^{\\frac{2\\nu + 2d}{\\nu}})$, \n\nwhere $\\nu_* := \\lceil \\nu - 1 \\rceil$.", "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.\n- 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?\n- 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": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* This work proposes a new class of continuous state-action MDPs in which sublinear regret is achievable\n* In particular, this new class is the currently the most general one that does not suffer from lower bounds exponential in $H$", "weaknesses": "* 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).\n* Similar to other algorithms in this line of work, the CINDERELLA is not computationally efficient and far from being a practical algorithm.\n* 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Q: _The regret bound has factors that are exponential in $d$._\n\nLower bounds show that exponential dependence is $d$ cannot be avoided. If we look at Gaussian bandits with the squared-exponential kernel, a problem family that is strictly contained also in the Strongly Smooth class, [1] ensures an $\\exp(d)$ regret lower bound (see Table 1 of [1]). Therefore, exponential scaling in $d$ should not be considered a limitation of our work: it is well-known that RL problems on continuous state-action space can be really hard even for moderately sized $d$.\n\nIf, in linear MDP problems, it is well known that $d$ may be very large, almost of the order of $K$, the same thing does not apply here. In fact, the lower bound, even for the simple case $\\nu=1,H=1$, entails that $d$ is much smaller than $\\log(K)$:\n$$R_K=\\Omega(K^{\\frac{d+1}{d+2}})\\quad \\text{and } \\quad  d\\approx c\\log(K) \\implies R_K=\\Omega(K^{\\frac{c\\log(K)+1}{c\\log(K)+2}})=\\Omega(K).$$\nThis means that, unless $d\\ll \\log(K)$, _the problem is provably unlearnable_.\n\nQ: _sublinearity in $K$ is weak_\n\n**About $K$, we do not only have sub-linearity**: of large importance is that for $\\nu\\to \\infty$ one recovers regret of $\\sqrt K$ as for tabular or linear MDPs. In fact, having $\\nu\\rightarrow +\\infty$ is very common in physical scenarios: the presence of a Gaussian noise in the transition function is sufficient to guarantee this condition. On the other side \"only sublinearity\", meant as having a regret order that is slightly less than one, is what competitor works get (See Net-Q-Learning).\n\nQ: _I am not sure what we really learn from such a work; the technical details are complicated even at the level of exposition._\n\nThe idea of using a feature map that splits across a finite number of regions of the state space is rather intuitive, in our opinion.\n\nBefore this work, there were mainly two approaches to continuous MDPs. 1) Discretization-based (e.g. NET-Q_LEARNING) algorithms cannot fully exploit smoothness: the regret scales as $K^{\\frac{1+d}{2+d}}$ even for $\\nu\\gg 1$, which makes them suboptimal. 2) Linearization-based approaches [2], which are able to exploit the parameter $\\nu$, achieving regret $\\sqrt K$ for $\\nu \\to \\infty$, but fail to give a sub-linear regret bound for $d>2\\nu$. The reason can be found in a well-known problem of linear models with misspecification [3].\n\nQ: _Definition 1 does not actually contain any structural assumption (...), so it doesn't make sense calling such MDPs (that have no structural properties) linearizable._\n\nAs the reviewer correctly states, Definition 1 does not contain any structural assumptions. In fact, as stated in the paper, potentially, every MDP belongs to this class.\nThe point is that the guarantees are \"non-trivial\" only if the approximation error $\\mathcal I$, which is built based on definition 1, is small. Having definition 1 + small $\\mathcal I$ corresponds to the intuitive idea of locally linearizable MDP. \nWe will modify the presentation to just define $\\mathcal I$ and then call, heuristically, Locally Linearizable MDPs, the ones for which this quantity is small, similarly to what was done in [4].\n\nOur novelty lies in **combining the two approaches by** splitting the parameters of the feature map (linearization) across different regions (discretization). In this way, we bypass the problem in [1], while having the same benefits of linearization approaches.\n\nThis technique partially solves a long-standing open problem in the Kernelized MDP community (see COLT 2024 Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning), as kernelized MDPs are a subclass of our setting. \n\nQ: _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?_\n\nAs we will clarify in the final version, this sentence does not mean to say \"all families that exist\" but rather \"all families that were defined in the continuous RL literature, to the best of our knowledge\". This sentence draws from some results in [2] saying that all the parametric families (LQRs, Linear MDPs, Kernelized MDPs, etc.) with a feasible regret bound are contained in the Strongly Smooth class, which is itself contained in the Mildly Smooth one.\n\nQ: _Does NET-Q-LEARNING indeed obtain regret bound that is independent of_ \n$\\nu$ _for the Strongly Smooth MDP setting? In this case is it strictly better than CINDERELLA for this MDP class?_\n\nWe remark that, as the lower bound decreases with $\\nu$, having a regret guarantee which improves for higher $\\nu$ is a desirable feature. Yes, the regret of NET-Q-LEARNING is independent of $\\nu$ (for $\\nu\\ge 1$), but this is a massive drawback w.r.t. our algorithm.\n\nIn fact, if one ignores the smoothness of the process, no better regret bound can be obtained than $K^{\\frac{d+1}{d+2}}$, the one of NET-Q-LEARNING. But ignoring all the smoothness of the process reveals suboptimal: the higher the $\\nu$, the lower the regret. Algorithms like ours, or the ones proposed in [2], as well as the ones coming from the Kernelized RL literature, are able to approach regret order $\\sqrt K$ for $\\nu \\to \\infty$, while NET-Q-LEARNING on MDPs cannot do better than $K^{3/4}$ (as $d\\ge 2$).\n\nFurthermore, note that many real settings are characterized by a very high value for $\\nu$: if the transition of the MDP is affected by a Gaussian noise, $\\nu=+\\infty$. Ideed, convolution of any function with a Gaussian density becomes infinite times differentiable.\n\n[1] Vakili et al., On Information Gain and Regret Bounds in Gaussian Process Bandits.\n\n[2] Maran et al., No-Regret Reinforcement Learning in Smooth MDPs.\n\n[3] Lattimore et al., Learning with Good Feature Representations in Bandits and in RL with a Generative Model.\n\n[4] Zanette et al., Learning Near Optimal Policies with Low Inherent Bellman Error", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)