Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces

Authors: yaqi  duan
martin j wainwright
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 09:46:27

Abstract: We introduce a novel framework for analyzing reinforcement learning (RL) in continuous state-action spaces, and use it to prove fast rates of convergence in both off-line and on-line settings. Our analysis highlights two key stability properties, relating to how changes in value functions and/or policies affect the Bellman operator and occupation measures. We argue that these properties are satisfied in many continuous state-action Markov decision processes. Our analysis also offers fresh perspectives on the roles of pessimism and optimism in off-line and on-line RL.

Main paper: 
 introduction: 
 Many domains of science and engineering involve making a sequence of decisions over time, with previous decisions influencing the future in uncertain ways [1, 13, 22, 31, 32] . For instance, clinicians managing diabetes [36] or engineers optimizing plasma control in tokamak systems [5] must develop policies that adapt based on evolving conditions and lead to desirable outcomes over a longer period. Markov decision processes (MDPs) and reinforcement learning (RL) provide frameworks and methods for estimating effective policies for such sequential problems. While RL excels in data-rich scenarios such as competitive gaming (e.g., AlphaGo and its extensions [30] ), its application in data-scarce areas like healthcare [36] and finance [27] remains challenging due to lack of history, or underlying non-stationarity. With limited data, characterizing and improving the sample complexity of RL methods becomes critical.Considerable research effort has been devoted to studying RL sample complexity in many settings. Existing studies for either the generative or the off-line settings (e.g., [21, 37, 35] ) give procedures that, when applied to a dataset of size n, yield a value gap that decays at the rate 1/ √ n. In the on-line setting, there are various procedures that yield cumulative regret that grows at the rate √ T (e.g., [18, 20, 19, 6] ). In contrast, the main result of this paper is to formalize conditions, suitable for RL in continuous domains, under which much faster rates can be obtained using the same dataset, achieving a value gap decay of 1/n and reducing regret growth to log T .As revealed by our analysis, these accelerated rates depend on certain stability properties, ones that-as we argue-are naturally satisfied in many control problems with continuous state-action spaces. Roughly speaking, these conditions ensure that the evolution of the dynamic system depends in a "smooth" way on the influence of decision policy. Such notions of stability should be expected in various controlled systems with continuous state-action spaces. In robotics, for example, a minor torque or motion perturbation that occurs during a single step should not cause a notable deviation from the intended trajectory. Similarly, in clinical treatment, slight deviations in medication dosage should not significantly compromise effectiveness or safety.The "Mountain Car" problem, a benchmark continuous control task, illustrates the acceleration phenomenon and underlying stability. In this task, as shown in Figure 1 (a), a car must reach the top of a hill by adjusting its acceleration within the interval [-1 , 1] . We employed fitted Q-iteration (FQI) with carefully selected linear basis functions to derive near-optimal policies with off-line data. This learning procedure exhibits a value sub-optimality decay at a rate of 1/n, a significant improvement over the classical rate of 1/ √ n, as detailed in Figure 1 (b). (See Appendix D for further explanation. The experiment ran for 3 days on two laptops, each equipped with an Apple M2 Pro CPU and 16 GB RAM.) In this example, slight perturbations in the driving policy lead to only modest changes in future trajectories, which shows the stability. Our theoretical analysis confirms that fast rates are achievable in this and similar continuous control tasks when such stability properties are present. Figure 1 : Illustration of the "fast rate" phenomenon using FQI on the Mountain Car problem. Each red point in the plot represents the average value sub-optimality J(π ⋆ ) -J( π n ) from T = 80 Monte Carlo trials, with the shaded area showing twice the standard errors. The blue dashed line is a least-squares fit to the last 6 data points, yielding a 95% confidence interval of (-1.084, -0.905) for the slope, significantly faster than the typical -0.5 "slow rate".With this high-level perspective in mind, let us summarize the key contributions of this paper.Fast rate of convergence: We develop a framework for analyzing RL in continuous state-action spaces, and use it to prove a general result (Theorem 1) under which fast rates can be obtained. The key insight is that stability conditions lead to upper bounds on the value sub-optimality that are proportional to the squared norm of Bellman residuals. In the off-line setting, this quadratic scaling improves convergence from a rate of n -1 2 to n -1 , while in on-line learning, it enhances the regret bound fromT to log T .Reconsidering pessimism and optimism principles: Our framework provides a novel perspective on the roles of pessimism [21, 4] and optimism [18, 20, 19, 6, 12] in off-line and on-line RL. Our theory reveals that there are settings in which neither pessimism nor optimism are required for effective policy optimization-in particular, they are not required as long as one has a sufficiently accurate pilot estimate policy. Moreover, our analysis shows that some procedures based on certainty equivalence can achieve fast-rate convergence, showing that the benefits gained from incorporating additional pessimism or optimism measures may be limited in this context.In this section, we discuss related work having to do with fast rates in optimization and statistics.Fast rates in stochastic optimization and risk minimization: For many statistical estimators (e.g., likelihood methods, empirical risk minimization), it is well-understood that the local geometry around the optimum determines whether fast rates can be obtained. For instance, when the loss function exhibits some form of strong convexity (such as exp-concave loss) or strict saddle properties, it can lead to significant reductions in additive regret from O( √ T ) to just O(log T ) in stochastic approximation (e.g., [15] ), or a decrease in the error rate from n -1 2 to n -1 in empirical risk minimization [23, 14] . These fast rate phenomena rely on a form of stability, one which relates the similarity of functions to the closeness of their optima. Our work develops a new framework for analyzing value-based RL methods, focusing on identifying specific stability conditions and inherent curvature properties that promote fast rate convergence in RL, similar to the role of stability analysis in statistical learning.Fast rates in reinforcement learning: In the RL literature, there are various lines of work related to fast rates, but the underlying mechanisms are typically different from those considered here. For problems with discrete state-action spaces, there is a line of recent work [17, 16, 33, 25] that performs gap/marginal-dependent analyses of RL algorithms. However, such separation assumptions are not helpful for continuous action spaces. Other work for discrete state-action spaces [28] has shown convergence rates in off-line RL are influenced by data quality, with a nearly-expert dataset enabling faster rate. In contrast, our analysis reveals that for off-line RL in continuous domains, fast convergence can occur whether or not the dataset has good coverage properties.An important sub-class of continuous state-action problems are those with linear dynamics and quadratic reward functions (LQR for short). For such problems, it has been shown [24, 29] that value sub-optimality can be connected with the squared error in system identification. Our general theory can also be used to derive guarantees for LQR problems, as we explore in more detail in a follow-up paper [8] . Stability also arises in the analysis of (deterministic) policy optimization and Newton-type algorithms [26, 3] , where it is possible to show superlinear convergence in a local neighborhood. This accelerated rate stems from the smoothness of the on-policy transition operator P π f with respect to changes in the value function f; for instance, see condition (10) in Puterman and Brumelle [26] . Our framework exploits related notions of smoothness, but is tailored to the stochastic setting of reinforcement learning, in which understanding the effect of function approximation and finite sample sizes is essential. 
fast rates for value-based reinforcement learning: 
 Let us now set up and state the main result of this paper. We begin in Section 2.1 with background on Markov decision processes (MDPs) and value-based methods, before turning to the statement of our main result in Section 2.2. In Section 2.3, we provide intuition for why stability leads to faster rates, and discuss consequences for both the off-line and on-line settings of RL.Basic set-up: We consider an episodic Markov decision process (MDP) defined by a quadruple S, A, P = {P h } H-1 h=1 , {r h } H h=1 . We assume that the rewards r h : S × A → R are known; however, this condition can be relaxed. A policy π h at time h is a mapping from any state s to a distribution π h (• | s) over the action space A. If the support of π h (• | s) is a singleton, we also let π h (s) ∈ A denote the single action to be chosen at state s. Given an initial distribution ξ 1 over the states at time h = 1, the expected reward obtained by choosing actions according to a policy sequence π = (π 1 , . . . , π H ) is given by J(π) ≡ J(π; ξ 1 ): =E ξ1,πH h=1 r h (S h , A h ) , where S 1 ∼ ξ 1 , S h+1 ∼ P h (• | S h , A h ) and A h ∼ π h (• | S h ) for h = 1, 2, .. . , H. Our goal is to estimate an optimal policy π ⋆ ∈ arg max π J(π).Value functions and Bellman operators: Starting from a given state-action pair (s, a) at stage h, the expected return over subsequent stages defines the state-action value functionQ π h (s, a) : = E π H h ′ =h r(S h ′ , A h ′ ) S h = s, A h = a . The sequence of functions Q π = (Q π 1 , . . . , Q π H )known as the Q-functions associated with π. The Q-functions Q π have an important connection with the Bellman evaluation operator for π. For any policy π and stage h, we introduce a linear transition operator(P π h f)(s, a) : = S×A f(s ′ , a ′ ) P h (ds ′ | s, a) π h+1 (da ′ | s ′ ) for any function f ∈ R S×A .With this notation, the Bellman evaluation operator at stage h takes the formEQUATIONFrom classical dynamic programming, the Q-functions Q π must satisfy the Bellman relationsQ π h (s, a) = (T π h Q π h+1 )(s, a) for h = 1, . . . , H -1.Bellman principle for optimal policies: Under mild regularity conditions, there is at least one policy π ⋆ such that, for any other policy π, we haveQ π ⋆ h (s, a) ≥ Q π h (s, a), for any h ∈ [H],and uniformly over all state-action pairs (s, a). Any optimal policy π ⋆ must be greedy with respect to the optimal Q-function Q ⋆ . By classical dynamic programming, the optimal Q-function Q ⋆ is obtained by setting Q ⋆ H = r H , and then recursively computingQ ⋆ h = T ⋆ h Q ⋆ h+1 for h = H -1, . . . , 2, 1, with the Bellman optimality operator defined asEQUATIONValue-based RL methods The main result of this paper applies to a broad class of methods for reinforcement learning. They are known as value-based, due to their reliance on the following two step approach for approximating an optimal policy π ⋆ : (1) Construct an estimateQ = ( f 1 , . . . , f H ) of the optimal value function Q ⋆ = (Q ⋆ 1 , . . . , Q ⋆ H ).(2) Use Q to compute the greedy-optimal policy π h (s) ∈ arg max a f h (s, a) for h = 1, 2, . . . , H. It should be noted that there is considerable freedom in the design of a value-based method, since different methods can be used to approximate value functions in Step 1. Rather than applying to a single method, our main result applies to a very broad class of these methods.Underlying any value-based method is a class F of functions (s, a) → f (s, a) used to approximate the state-action value functions. 1 We assume that the function class F is rich enough-relative to the Bellman evaluation operators-to ensure that for any greedy policy π induced by some f = (f 1 , . . . , f H ) ∈ F H , we have the inclusion T π h F ⊆ F for h = 1, . . . , H -1. We see that this condition depends on the structure of the transition distributions P h (• | s, a). In many practical examples, the reward function itself has some number of derivatives, and these transition distributions perform some type of smoothing, so that we expect that the output of the Bellman update, given a suitably differentiable function, will remain suitably differentiable.We now turn the central question in understanding the behavior of any value-based method: How to translate "closeness" of the Q-function estimate Q to a bound on the value gap J(π ⋆ ) -J( π)?At a high level, existing theory provides guarantees of the following type: if the Q-function estimates are ε-accurate for some ε ∈ (0, 1), then the value gap is bounded by a quantity proportional to ε.In contrast, our main result shows that when the MDP is stable in a suitable sense, the value gap can be upper bounded by a quantity proportional to ε 2 . This quadratic as opposed to linear scaling encapsulates the "fast rate" phenomenon of this paper.Our analysis isolates two key stability properties required for faster rates; both are Lipschitz conditions with respect to a certain norm. Here we define them with respect to the L2 -norm induced by the state-action occupation measure induced by the optimal policy-namelyEQUATIONand over a neighborhood N of the optimal Q-value function Q ⋆ .Bellman stability: The first condition measures the stability of the Bellman optimality operator (2): in particular, we require that there is a scalar κ ⋆ h such thatT ⋆ h f h+1 -T ⋆ h Q ⋆ h+1 h ≤ κ ⋆ h f h+1 -Q ⋆ h+1 h+1 (Stb(T ))for any f ∈ N . Moreover, for any pair(h, h ′ ) of indices such that 1 ≤ h < h ′ ≤ H -1, we define κ h,h ′ (T ⋆ ) : = κ ⋆ h κ ⋆ h+1 . . . κ ⋆ h ′ -1 . Condition (Stb(T ))is directly linked to the stability of estimating the Q-function Q ⋆ . In typical estimation procedures, such as approximate dynamic programming, the estimation is carried out iteratively in a backward manner, so that it is important to control the propagation of estimation errors across the iterations. Condition (Stb(T )) captures this property, since it implies thatT ⋆ h T ⋆ h+1 . . . T ⋆ h ′ -1 f h ′ -T ⋆ h T ⋆ h+1 . . . T ⋆ h ′ -1 Q ⋆ h ′ h ≤ κ h,h ′ (T ⋆ ) • f h ′ -Q ⋆ h ′ h ′ , which shows how the estimation error f h ′ -Q ⋆ h ′ at step h ′ canbe controlled in terms of estimation error at an earlier time step h ≤ h ′ .Occupation measure stability: Our second condition is more subtle, and is key in our argument. Let us begin with some intuition. Consider two sequences of policiesπ ⋆ 1 , . . . , π ⋆ h-1 , π ⋆ h , π ⋆ h+1 , . . . , π ⋆ h ′ and π ⋆ 1 , . . . , π ⋆ h-1 , π h , π ⋆ h+1 , . . . , π ⋆ h ′that only differ at the h-th step, where π ⋆ h has been replaced by π h . These two policy sequences induce Markov chains whose distributions differ from stage h onwards, and our second condition controls this difference in terms of the difference ∥f h -Q ⋆ h ∥ h between the two Q-functions f h and Q ⋆ h that induce π h and π ⋆ h , respectively. We adopt P ⋆ h as a convenient shorthand for the transition operator P π ⋆ h , and define the multi-step transition operator P ⋆ h,h ′ : = P ⋆ h P ⋆ h+1 • • • P ⋆ h ′ -1 . Using this notation, for any h ′ ≥ h + 1, we require that there is a scalar κ h,h ′ (π ⋆ ) such thatsup g∈∂F ∥g∥ h ′ >0 E π ⋆ P ⋆ h,h ′ g (S h , π ⋆ h (S h )) -P ⋆ h,h ′ g (S h , π h (S h )) ∥g∥ h ′ ≤ κ h,h ′ (π ⋆ ) f h -Q ⋆ h h Q ⋆ h h (Stb(ξ))for any f ∈ N . The renormalization in this definition serves to enforce a natural scale invariance.With these notions of stability in hand, we are now equipped to state our main result. Taking as input a value function estimate Q, it relates the induced value gap to the Bellman residuals T ⋆ h f h+1 -f h . Note that these residuals are a way of quantifying proximity to the optimal value function Q ⋆ , which has Bellman residual zero by definition. We assume that Q has Bellman residuals bounded asEQUATIONfor some sequence ε = (ε 1 , . . . , ε H-1 , ε H = 0) that satisfies the constraintEQUATIONThis last condition means that the Bellman residual ε h is larger than or equal to the average of the bounds established after step h + 1. It is natural because estimating at step h is at least as challenging as a stage h ′ > h; indeed, any such state h ′ occurs earlier in the dynamic programming backward iteration process. As a special case, the bound (4b) holds when ε h = ε for all stages.With this set-up, we have the following guarantee in terms of the stability coefficients κ h,h ′ (π ⋆ ) and κ h,h ′ (T ⋆ ) from conditions (Stb(ξ)) and (Stb(T )).Theorem 1. There is a neighborhood of Q ⋆ such that for any value function estimate f with ε-bounded Bellman residuals (4a), the induced greedy policy π has value gap bounded asEQUATIONSee Appendix A for the proof.Treating dependence on the stability coefficients as constant, the main take-away is that value suboptimality is bounded above by a quantity proportional to the squared norm of the Bellman residuals. Concretely, if the Bellman residuals are uniformly upper bounded by some ε, then equation ( 5) leads to an upper bound of the formJ(π ⋆ ) -J( π) ≤ c H 3 ε 2 ,where c is a universal constant. Due to the quadratic scaling in the Bellman residual error ε, this bound is substantially tighter than the linear in ε rates afforded by a conventional analysis.Why does "fast rate" phenomenon formalized in Theorem 1 arise? The fast rates proved in this paper are established by a novel argument, starting from a known telescope bound, which we begin by stating. Given a Q-function estimate f = f 1 , . . . , f H , let π denote the induced greedy policy.Then the value gap of π with respect to an arbitrary comparator policy π is bounded asEQUATIONThis result follows by a "telescope" relation induced by the structure of the Bellman updates. 3 For completeness, we provide a proof of the telescope bound in Appendix E.2.A key feature of inequality (6) is the difference of two expectations E π -E π , corresponding to the occupation measures under π versus π. In standard uses of this inequality, an initial argument is used to guarantee that one of these expectations is negative, and so can be dropped [20, 21] .In contrast, the proof of our Theorem 1 exploits a more refined approach, one that handles the difference of expectations directly. Doing so can be beneficial-and lead to "fast rates"-because various terms in this difference can cancel each other out. Specifically, under the smoothness conditions that underlie Theorem 1, when applying the telescope inequality (6) with comparator π = π ⋆ , we show that the discrepancy between the occupation measures associated with π ⋆ and π is of the same order as the Bellman residual associated with f . Note that the Bellman residuals of f already appear on the right-hand side of inequality (6) , so that this fortuitous cancellation can be exploited-along with a number of auxiliary results laid out in the proof-so as to upper bound the value gap by a quantity proportional to the squared Bellman residual ε 2 .It is worthwhile making an explicit comparison of our cancellation approach with the more standard uses of the telescope relation, which typically consider only one portion of the Bellman residuals (e.g., [18, 20, 21, 19, 6, 12, 35] ). We do so in the following two subsections.In the off-line instantiation of RL, the goal is to learn a "good" policy based on a pre-collected dataset D. Note that no further interaction with the environment is permitted, hence the notion of the learning being off-line. More precisely, an off-line dataset D of size n consists of quadruplesD = s h, i , a h, i , s ′ h, i , r h, i n i=1 ,where s h, i and a h, i represent the i-th state and action at the h-th step in the MDP; s ′ h, i is the successive state; and r h, i = r h (s h, i , a h, i ) denotes the scalar reward. Note that while the successive states are defined by transition dynamics, and the rewards by the reward function, there are no restrictions on how the state-action pairs (s h, i , a h, i ) are collected. That is, they need not have been generated by any fixed policy, but may have collected from some ensemble of behavioral policies, or even adaptively by human experts. The goal of off-line reinforcement learning is to use the n-sample dataset D so as to estimate a policy π ≡ π n that (approximately) maximizes the expected return J( π n ). We expect that-at least for a sensible method for estimating π n -the value gap J(π ⋆ ) -J( π n ) should decay to zero as n increases to infinity, and we are interested in understanding this rate of decay. The use of pessimism is standard in off-line RL algorithms. Its purpose is to mitigate risks associated with "poor coverage" of the off-line dataset. For instance, the naive approach of simply maximizing Q-function estimates based on an off-line dataset can behave poorly when certain portions of the state-action space are not well covered by the given dataset. The pessimism principle suggests to form a conservative estimate of the value function-say withEQUATIONwith high probability over state-action pairs (s, a). Thus, the estimated value f h (s, a) is an underestimate of the Bellman update, a form of conservatism that protects against unrealistically high estimates due to poor coverage. Doing so in the appropriate way ensures thatEQUATIONApplying this upper bound to the inequality ( 6) yields the sub-optimality boundJ(π) -J( π) ≤ H-1 h=1 E π T ⋆ h f h+1 -f h (S h , A h ) .Upper bounds derived in this manner only contain one portion of the Bellman residual. When the value functions are approximated in a parametric way (e.g., tabular problems, linear function approximation), this line of analysis leads to value sub-optimality decaying at a "slow" 1/ √ n rate in terms of the sample size n (e.g., [21] ). In contrast, an application of Theorem 1 can lead to value gaps bounded by 1/n.In the setting of on-line RL, a learning agent interacts with the environment in a sequential manner, receiving feedback in the form of rewards based on its actions. At the beginning, the learner possesses no prior knowledge of the system's dynamics. In the t-th episode, the agent learns an optimal policy π (t) using existing observations, implements the policy and collects data s(t) h , a (t) h , r (t) h H h=1from the new episode. In each round, the system starts at an initial state s (t) 1 independently drawn from a fixed distribution ξ 1 .In this on-line setting, it is common to measure the performance of an algorithm by comparing it, over the T rounds of learning, with an oracle that knows and implements an optimal policy. At each round t, we incur the instantaneous regret J(π ⋆ ) -J( π (t) ), where π ⋆ is any optimal policy. Over T rounds, we measure performance in terms of the cumulative regretRegret { π (t) } T t=1 : = max policy π T t=1 J(π) -J( π (t) ) = T t=1 J(π ⋆ ) -J( π (t) )Regret at round t .In a realistic problem, the cumulative regret of any procedure grows with T , and our goal is to obtain algorithms whose regret grows as slowly as possible.In contrast to off-line RL, the on-line setting allows for exploring state-action pairs that have been rarely encountered; doing so makes sense since they might be associated with high rewards. Principled exploration of this type can be effected via the optimism principle: one constructs function estimates such thatEQUATIONwith high probability over state-action pairs. 4 Note that f h (s, a) is optimistic in the sense that it is an over-estimate of the Bellman update T ⋆ h f h+1 (s, a). In this way, we can ensure thatEQUATIONCombining this inequality with the telescope bound (6) allows one to upper bound the regret asRegret { π (t) } T t=1 = T t=1 J(π ⋆ ) -J( π (t) ) ≤ T t=1 H-1 h=1 E π (t) f h -T ⋆ h f h+1 (S h , A h ) .which only includes a single portion of the Bellman residual. In the case of tabular or linear representations of the Q-functions, it results in a regret rate of √ T (e.g., see the papers [18, 20] ). In contrast, an appropriate use of Theorem 1 leads to regret growing only as log(T ), which corresponds to a much better guarantee.In summary, then, the fast rates obtained in this paper are based on a different approach than the standard pessimism or optimism principles. Since we deal directly with the difference of expectations in the bound (6) , there is no need to nullify either of them through the use of these principles. However, it should be noted that we are assuming smoothness conditions that allow us to control this difference. As we discuss in the sequel, such smoothness conditions rule out certain "hard instances" used in past work on lower bounds (e.g. [18, 20, 21, 37] ). 
consequences for linear function approximation: 
 In this section, we explore some consequences of our general theory when applied to value-based methods using (finite-dimensional) linear function approximation.Let ϕ : S × A → R d be a given feature map on the state-action space, and consider linear expansions of the form f w (s, a) = ⟨ϕ(s, a), w⟩ ≡ d j=1 w j ϕ j (s, a) where w ∈ R d is a weight vector. We adopt the conventional assumption that ∥ϕ(s, a)∥ 2 ≤ 1 and r h (s, a) ∈ [0, 1] for all state-action pairs. Defining the linear function class F : = f w | w ∈ R d , we note that the Minkowski difference class ∂F is equal to F .In our analysis of linear approximation, we make use of the norm ∥f ∥h : = E π ⋆ [f 2 (S h , A h )],corresponding to L 2 -norm under the occupation measure induced by the optimal policy π ⋆ .We now turn to some implications of Theorem 1 for off-line reinforcement learning. Let us recall the off-line setting: for each h = 1, . . . , H -1, we are given a datasetD h = {(s h,i , a h,i , s ′ h,i , r h,i )} n i=1of quadruples, from which we can compute estimates f = ( f h ) H h=1 with certain Bellman residuals {ε h } H-1 h=1 , which then appear in the bound (5) . The remaining factors on the right-hand side of inequality (5) do not depend on the dataset itself (but rather on structural properties of the MDP). Consequently, in terms of statistical understanding, the main challenge is to establish high-probability bounds on the Bellman residuals {ε h } H-1 h=1 for a particular estimator.As an illustration, let us analyze the use of fitted Q-iteration (FQI) for computing estimates of the Q-function. At a given stage h = 1, . . . , H -1, we can use the associated data D h to define a regularized objective functionL h f, g : = 1 |D h | (s h,i ,a h,i ,s ′ h,i ,r h,i )∈D h f (s h, i , a h, i ) -r h, i + max a∈A g(s ′ h, i , a) 2 + Λ 2 h (f ) .Here g represents the target function from stage h + 1, and it defines the targeted responses y h,i (g) : = r h,i + max a∈A g(s ′ h,i , a). For a given target g, we obtain a Q-function estimate for stage h by minimizing the functional f → L h (f, g). Given that our objective is defined with a quadratic cost, doing so can be understood as a regression method for estimating the conditional expectation that underlies the Bellman update-viz.T ⋆ h g(s, a) = E[ y h, i (g) | (s h, i , a h, i ) = (s, a) ]. Here Λ 2 h (f ) = λ h ∥w∥ 2 2 for f = ⟨ϕ(•), w⟩ is a regularizer, with λ h ≥ 0 being the regularization weight. Given this set-up, we can generate a Q-function estimate f = ( f 1 , . . . , f H ) by first initializing f H = r H , and then recursively computingf h = arg min f ∈F L h f, f h+1 , for h = H -1, H -2, . . . , 2, 1.In the analysis here, we assume that the dataset consists of i.i.d. tuples (but this can be relaxed as needed). We now state a corollary of Theorem 1, applicable to value function estimates based on FQI with ridge regression. Corollary 1 (Fast rates for ridge-based FQI). For FQI based on ridge regression, with a sufficiently large sample size n and with suitable choices of the regularization parameters {λ h } H-1 h=1 , the bound (5) from Theorem 1 holds withEQUATIONwith probability at least 1 -δ.We omit the proof of Corollary 1, as it follows from standard ridge regression analysis.Fast rates and comparisons to past work: So as to be able to compare with results from past work, let us consider some consequences of the bound (10) under the following assumptions:(i) κ h,h ′ (T ⋆ ) = O(1); (ii) κ h,h ′ (π ⋆ ) = O( √ d); (iii) ∥Q ⋆ h ∥ h ≍ H -h + 1.Then it can be shown that the bound from Corollary 1 takes the formEQUATIONand is valid for a sample size n ≥ cd 2 H 3 . Alternatively stated, Corollary 1 guarantees that for FQI using ridge regression with d-dimensional function approximation, the number of samples n(ϵ) required to obtain ϵ-optimal policy is at mostEQUATIONwhere we use ≍ to denote a scaling that ignores constants and logarithmic factors. Let us compare this guarantee to related work by Zanette et al. [37] , who analyzed the use of pessimistic actor-critic methods for linear function classes. When translated into the notation of our paper, their analysis established5 a sample complexity of the order n Zan (ϵ) ≍ d 2 H 3 /ϵ 2 . Consequently, we see that once the target error ϵ is relatively small-ϵ ∈ (0, 1)-then stable MDPs can exhibit a much smaller (1/ϵ) sample complexity. It should be noted that past work (e.g., [21, 37] ) has established (1/ϵ 2 )-lower bounds on the sample complexity of estimating ϵ policies in the off-line setting. However, these lower bounds do not contradict our fast rate guarantee (11b), because the "hard instances" used in these lower bound proofs violate the stability condition (Stb(ξ)). In particular, even infinitessimally small perturbations in policy lead to occupation measures that are significantly different.When is pessimism necessary? An interesting aspect of the guarantee from Corollary 1 is that it provides guarantees for off-policy RL (and with fast rates) using a method that does not incorporate any form of pessimism. This is a sharp contrast with many other methods for off-policy RL, such as pessimistic forms of Q-learning and actor-critic methods (e.g., [21, 37] ). To be clear, as noted following the bound (11a), the guarantee from Corollary 1 requires the sample size to be lower bounded as n ≥ cd 2 H 3 . In contrast, pessimistic schemes only require a sample size sufficiently large to ensure validity of the Bellman residual upper bounds that underlie Corollary 1meaning that n ≳ d up to logarithmic factors. Thus, the pessimism principle can be useful for problems with smaller sample sizes.In this section, we explore some consequences of Theorem 1 for on-line reinforcement learning. We begin by describing a two-stage procedure 6 that allows us to convert the risk bounds for FQI from off-line RL into regret in on-line RL:Phase 1 (Exploration) In the initial T 0 f episodes, the focus is purely on exploration, resulting in an estimate of Q-function denoted as f (T0) . Phase 2 (Fine-tuning) For k = 0, 1, . . . , K -1 with K : = ⌈log 2 (T /T 0 )⌉, repeat:• In the t-th episode, for each t = T 0 2 k + 1, . . . , T 0 2 k+1 , execute the greedy policy induced by function f (T0 2 k ) .• Update the Q-function estimate f (T0 2 k+1 ) using FQI based on observations collected from episodesT 0 2 k + 1, T 0 2 k + 2, . . . , T 0 2 k+1 .We assume the burn-in time T 0 is large enough so as to ensure the pilot Q-function estimate f (T0) obtained in Phase 1 falls within a certain "absorbing" region N (ρ) around Q ⋆ . Under these conditions, we have the following bound on the regret. Corollary 2. For FQI based on ridge regression with rewards in [0, 1], with a sufficiently large burn-in time T 0 and with suitable choices of the regularization parameters {λ h } H-1 h=1 , the two-phase scheme achieves regret bounded asRegret(T ) ≤ c T 0 • H + d √ d H 4 log T • log(dHK/δ)with probability at least 1 -δ.See Appendix C.1 for the proof.Sharper bound on regret: The leading term (as T grows) in the regret bound grows as log T , which is much smaller than the typical √ T -rate found in past work [18, 20] . The √ T rate has been shown to be unimprovable in general, but the worst-case instances [18, 20] that lead toT -regret violate the stability conditions used in our analysis.When is optimism needed? The use of optimism-by adding bonuses to the current value function estimates so as to encourage exploration-underlies many schemes in on-line RL. An interesting take-away from Corollary 2 is that under the stability conditions highlighted by our theory, it is possible to achieve excellent regret bounds without the use of optimism. In our two-phase scheme, the only exploration occurs in Phase 1. All other data is simply collected using the greedy policy induced by the current Q-function estimate. A well-designed exploration scheme-one that might incorporate the optimism principle-is necessary only during the burn-in Phase 1. 
discussion: 
 This paper introduces a novel approach for the analysis of value-based RL methods for continuous state-action spaces. Our analysis highlights two key stability properties of MDPs under which much sharper bounds on value sub-optimality can be guaranteed. Our analysis offers fresh perspectives on the commonly used pessimism and optimism principles, in off-line and on-line settings respectively.Our study leaves open various questions for future work. First, our main result (Theorem 1) has consequences for linear quadratic control, to be described in an upcoming paper [8] . It provides insight into the role of covariate shift in linear quadratic control, as well as efficient exploration in the on-line setting. Second, our current statistical analysis focused on i.i.d. data with linear function approximation. It is interesting to consider the extensions to dependent data and non-parametric function approximation (e.g. kernels, boosting, and neural networks). Third, while this paper has provided upper bounds, it remains to address the complementary question of lower bounds for policy optimization over the classes of stable MDPs isolated here. Last, to better align our framework with real-world scenarios, we intend to go beyond the idealized completeness condition used in this paper, and treat the role of model mis-specification.This section is devoted to the proof of Theorem 1, which consists of three main steps. These steps rely on two auxiliary lemmas whose proofs are fairly technical, so that they are deferred to in Appendices B.1 and B.2.High-level outline: Let us outline the three steps of the proof. In Step 1, we use a one-step expansion of the difference in the occupation measures to reformulate the standard telescope inequality (6) . Doing so results in a relation with structure similar to that of the left-hand side of inequality (Stb(ξ)). In Step 2, we develop a constraint on the function estimation error d h f h , Q ⋆ h that ensures the occupation measure produced by policy π remains stable and does not deviate too much from the occupation measure associated with the optimal policy π ⋆ . In Step 3, we use Bellman stability(Stb(T )) to connect the Q-function error f h -Q ⋆ h with Bellman residuals.With this high-level view in place, we now work through the three steps.A. 1 Step 1: Reformulation of the telescope inequality.Recall the standard telescope inequality (6) . Our proof makes use of an alternative form, which involves the functionsEQUATION) Lemma 1. Given a Q-function estimate f = f 1 , . . . , f H-1, f H = r H and the associated greedy policy π, we have the boundEQUATIONvalid for any policy π.See Appendix B.1 for the proof.We apply the bound (13) with π = π ⋆ . Following some algebra, we find thatJ(π ⋆ ) -J( π) ≤ H-1 h=1 H-1 h ′ =h β(h, h ′ ) • ε h ′ ,where ε h ′ is an upper bound on the Bellman residualEQUATION)We note that the left-hand side of inequality (Stb(ξ)) has a similar form to the term β(h, h ′ ), differing only in that the expectation is taken over the occupation measure of running the optimal policy π ⋆ , rather than the estimated policy π.A. 2 Step 2: Constraint to ensure stability Our next step is to establish an upper bound on the coefficient β(h, h ′ ) defined by the estimated policy π in terms of the analogous quantity defined by the optimal policy π ⋆ -namely, the coefficientEQUATIONIn order to do so, we demonstrate that a sufficiently small function estimation errorEQUATION)Once we have established this bound, we can replace the term β(h, h ′ ) withκ h,h ′ (π ⋆ )• f h -Q ⋆ h h ∥Q ⋆ h ∥ h ,using the inequality (Stb(ξ)). We summarize the result in the following auxiliary lemma: Lemma 2. Suppose that the function estimation errors satisfyd h Q h , Q ⋆ h ≤ 1 2 b F (H -h + 1) -1 for h = 2, 3, . . . , H -1 and the sequence ε = (ε 1 , . . . , ε H-1 , ε H = 0) satisfies the regularity condition (4b). Then we haveEQUATION)See Appendix B.2 for the proof.The remaining piece of the proof is to connect the function difference f h -Q ⋆ h with Bellman residuals T ⋆ h f h+1 -f h , using the stability condition (Stb(T )) on the Bellman operator T ⋆ . This is relatively straightforward: indeed, we claim thatEQUATIONRecall that Q ⋆ h = T ⋆ h Q ⋆ h+1 for h = 1, 2, . . . , H -1. Therefore, we havef h -Q ⋆ h = T ⋆ h f h+1 -T ⋆ h Q ⋆ h+1 -T ⋆ h f h+1 -f h .f h -Q ⋆ h h ≤ T ⋆ h f h+1 -f h h + T ⋆ h f h+1 -T ⋆ h Q ⋆ h+1 h ≤ T ⋆ h f h+1 -f h h + κ ⋆ h f h+1 -Q ⋆ h+1 h+1 .Applying this inequality recursively yields the claim (17) .With this piece in place, we can complete the proof of Theorem 1. Indeed, we haveEQUATION≤ 2H-1 h=1 f h -Q ⋆ h h ∥Q ⋆ h ∥ h H-1 h ′ =h κ h,h ′ (π ⋆ ) ε h ′ (b) ≤ 2 H-1 h=1 1 ∥Q ⋆ h ∥ h H-1 h ′ =h κ h,h ′ (T ⋆ ) ε h ′ H-1 h ′ =h κ h,h ′ (π ⋆ ) ε h ′ .Here step (a) is a restatement of the bound (16) from Lemma 2, whereas step (b) follows from inequality (17) . Thus, we have established the claim given in Theorem 1.We now turn to proofs of the two auxiliary results used to establish our main theorem, with Lemmas 1 and 2 treated in Appendices B.1 and B.2, respectively.For any integrable vector function g = (g 1 , . . . , g H ) ∈ R S×A×H , we defineEQUATIONWe claim that this functional satisfies the recursive relationEQUATIONwhere we have introduced the shorthand P π g : = P π 1 g 2 , . . . ,P π H-1 g H , 0 ∈ R S×A×H .Taking this claim as given for the moment, let us prove the bound (13) from Lemma 1. First, we set g : = (P π ) h g = P π 1,1+h g 1+h , . . . , P π H-h,H g H , 0, . . . , 0 in equation (18b) for h = 0, 1, . . . , H -1, which yieldsD (P π ) h g = 1≤h ′ ≤j≤H, j-h ′ =h E π {P π h ′ ,j g j }(S h ′ , π h ′ (S h ′ )) -{P π h ′ ,j g j }(S h ′ , π h ′ (S h ′ ))+ D (P π ) h+1 g .Note that (P π ) H g = 0, which implies D (P π ) H g = 0. We then sum the resulting bounds so as to obtainEQUATIONSetting g = T ⋆ ff , or equivalently g h = T ⋆ h f h+1 -f h , in equation ( 19), we find thatD T ⋆ f -f = H-1 h=1 E π ∆ h (π; S h , π h (S h )) -∆ h (π; S h , π h (S h )) ,where we have used the fact (12) that ∆ h (π;•) = H h ′ =h P π h,h ′ T ⋆ h ′ f h ′ +1 -f h ′. Thus, we have established the bound (13) stated in Lemma 1.It remains to establish the auxiliary claim (18b). Note that the functional D can be decomposed as D(g) = D 1 + D 2 , whereD 1 : = H h=1 E π g h (S h , π h (S h )) -g h (S h , π h (S h ))andD 2 : = H h=1 E π -E π g h (S h , π h (S h )) .Applying the tower property of conditional expectation, we find thatD 2 = H-1 h=1 E π -E π E[g h+1 (S h+1 , π h+1 (S h+1 )) | S h , A h ] = H-1 h=1 E π -E π (P π h g h+1 )(S h , A h ) = D P π g .Combining the expressions for D 1 and D 2 above yields the claim (18b).The key step in proving Lemma 2 is establishing that inequality (15) holds when the function estimation error d h f h , Q ⋆ h is sufficiently small. In order to do so, we need to establish upper bounds on the term β(h, h ′ ) by using β(h, h ′ ). In particular, we will show that for anyEQUATIONThe inequality ( 20) is derived based on the definitions of metric d h and parameter b F = 1. After a close examination of the right-hand side of this inequality, it becomes evident that as long as the function estimation error d h f h , Q ⋆ h is sufficiently small, the terms associated with d h f h , Q ⋆ h are negligible and are dominated by β(h, h ′ ). Consequently, inequality (15) within the arguments in Appendix A.2 is likely to hold true.With claim (20) assumed to be valid at this point, we now establish a proper upper bound on the estimation error d h f h , Q ⋆ h under which inequality ( 15) is satisfied. By taking linear combinations of inequality (20) using weights ε = (ε 1 , . . . , ε H-1 , ε H = 0), we obtainEQUATION)When the sequence ε = (ε 1 , . . . , ε H-1 , ε H = 0) is regular in the sense that inequality (4b) holds, the bound (21) reduces to1≤h≤h ′ ≤H β(h, h ′ ) • ε h ′ ≤ 1≤h≤h ′ ≤H β(h, h ′ ) • ε h ′ + 1≤h≤h ′ ≤H-2 β(h, h ′ ) • ε h ′ • b F (H -h ′ ) • d h ′ +1 f h ′ +1 , Q ⋆ h ′ +1 .h f h , Q ⋆ h ≤ 1 2 b F (H -h + 1) -1 for 2 ≤ h ≤ H -1,the inequality above implies bound (15) , which further establishes the bound (16) , as stated in Lemma 2.It remains to prove the relation between β(h, h ′ ) and β(h, h ′ ), as shown in inequality (20) .Proof of bound (20): It is evident that inequality (20) holds for h = 1, therefore, we focus on its validation for indices 2 ≤ h ≤ H -1. Recall the definitions of functions β(h, h ′ ) and β(h, h ′ ), as given by equations (14a) and (14b). We apply the triangle inequality and derive thatβ(h, h ′ ) -β(h, h ′ ) ≤ sup f∈∂F : ∥f∥ h ′ >0 1 ∥f∥ h ′ E π -E π ⋆ P ⋆ h,h ′ f (S h , π ⋆ h (S h )) -P ⋆ h,h ′ f (S h , π h (S h )) = sup f∈∂F : ∥f∥ h ′ >0 1 ∥f∥ h ′ E π -E π ⋆ P ⋆ h-1 -P π h-1 P ⋆ h,h ′ f (S h-1 , A h-1 ) = : ∆β(h, h ′ ) .The term ∆β(h, h ′ ) involves differences from two sources: (i) the difference in transition kernels P ⋆ h-1 -P π h-1 that captures the divergence between policies π ⋆ h and π h ; (ii) the discrepancy of occupation measures at the (h -1)-th step reflected by the difference in expectations E π ⋆ -E π , which is determined by the policies (π ⋆ 1 , . . . , π ⋆ h-1 ) and ( π 1 , . . . , π h-1 ) until the (h -1)-th step. We treat them separately and writeEQUATION)where the functionals ν 2 and ν 1 are defined asν 1 (h -1, h ′ ) : = sup f∈∂F : ∥f∥ h ′ >0 1 ∥f∥ h ′ P ⋆ h-1 -P π h-1 P ⋆ h,h ′ f h-1 , ν 2 (h -1) : = sup f∈∂F : ∥f∥ h-1 >0 1 ∥f∥ h-1 E π -E π ⋆ f(S h-1 , A h-1) .We first consider the term ν 1 . According to the definitions of metric d h and parameter b F we find thatP ⋆ h-1 -P π h-1 P ⋆ h,h ′ f h-1 ≤ d h f h , Q ⋆ h • P ⋆ h,h ′ f h ( * ) ≤ d h f h , Q ⋆ h • b F ∥f∥ h ′ ,which in turn impliesEQUATION)The proof of inequality ( * ) for b F = 1, as mentioned above, can be found in Appendix E.1.As for term ν 2 , we claim thatEQUATION)Combining the bound β(h, h ′ ) ≤ β(h, h ′ ) + ∆β(h, h ′ ) with inequalities ( 22), (23a) and (23b), we establish the bound (20), as claimed. It remains to prove the claim (23b).Proof of inequality (23b): This proof is analogous to that of Lemma 1. We begin by introducing an analogue of the functional D(g) from equation (18a); in particular, for any index h ∈ [H -1] and function g ∈ ∂F , defineD ⋆ h (g) : = E π ⋆ -E π g(S h , A h ) .h , we can rewrite the left-hand side of inequality (23b) asν 2 (h -1) = sup f∈∂F : ∥f∥ h-1 >0 |D ⋆ h-1 (f)|/∥f∥ h-1 .Following the same arguments as in the proof of inequality (18b), we can show thatEQUATIONwhere we set D ⋆ 0 ≡ 0. We consider function g : = P ⋆ j,h-1 f for 1 ≤ j < h ≤ H -1. It follows from equation (24) thatD ⋆ j P ⋆ j,h-1 f = E π P ⋆ j,h-1 f (S j , π ⋆ j (S j ))-P ⋆ j,h-1 f (S j , π j (S j )) + D ⋆ j-1 P ⋆ j-1,h-1 f ,where we have used the relationP ⋆ j-1 P ⋆ j,h-1 = P ⋆ j-1,h-1 .Recalling the definition of β(j, h -1) in equation (14a), applying the triangle inequality yieldsD ⋆ j P ⋆ j,h-1 f ≤ β(j, h -1) • ∥f∥ h-1 + D ⋆ j-1 P ⋆ j-1,h-1 f . Summing this equation over indices j = 1, 2, 3, . . . , h -1 yields |D ⋆ h-1 (f)| ≤ h-1 j=1 β(j, h -1) • ∥f∥ h-1 ,which establishes inequality (23b).This section cotains proofs of several corollaries.We now turn to proving Corollary 2 regarding ridge-based FQI in on-line settings.In Phase 1 of pure exploration, the cumulative regret is always bounded from above by T 0 • H. During Phase 2 of fine-tuning, we let π k be the policy employed in the rounds T 0 2 k +1, T 0 2 k +2,. . ., T 0 2 k+1 , which is determined by the estimate f (T02 k ) calculated at the end of the (T 0 2 k )-th round.To estimate the regret, we consider the decompositionT t=T0+1 J(π ⋆ ) -J( π (t) ) ≤ K-1 k=0 T02 k+1 t=T02 k J(π ⋆ ) -J( π (t) ) = K-1 k=0 T 0 2 k J(π ⋆ ) -J( π k ) .We leverage our bound (11a) for off-line RL in Section 3.1.2 to control the value sub-optimality J(π ⋆ ) -J( π k ). Recall that the policy π k is derived from i.i.d. trajectories collected from the rounds T 0 2 k-1 + 1, T 0 2 k-1 + 2, . . . , T 0 2 k . We divide those T 0 2 k-1 trajectories into H -1 equal shares and use each share to conduct estimation in one iteration of the FQI procedure. This subsampling technique ensures the independence of samples used in different iterations. It is primarily adopted for the sake of convenience (to keep the explanations concise) and is not essential in general. It follows from inequality (11a) that the boundJ(π ⋆ ) -J( π k ) ≤ c d √ d H 4 T 0 2 k log(dHK/δ)holds uniformly for indices k = 0, 1, . . . , K -1 with a probability exceeding 1 -δ.Putting together the pieces, we arrive atRegret(T ) ≤ T 0 • H + c d √ d H 4 K log(dHK/δ) .We then derive the regret bound in Corollary 2 by noticing that K = O(log T ).In this section, we derive the sample complexity n Zan (ϵ) ≍ d 2 H 3 ϵ 2 in Section 3.1.2 based on the results of Zanette et al. [37] ; it gives the conventional 1/ √ n slow rate to which we compare. Zanette et al. [37] proved upper bounds on a pessimistic actor-critic scheme based on d-dimensional linear function approximation. Using our notation, Theorem 1 in their paper [37] can be expressed asEQUATIONwhere the vector ϕ h is given by ϕh : = E π ⋆ ϕ(S h , A h ) , the covariance matrix Σ h,D : = 1 |D h | (s h,i ,a h,i ,s ′ h,i ,r h,i )∈D h ϕ(s h, i , a h, i )ϕ(s h, i , a h, i ) ⊤ .We now consider the explicit dependence of this upper bound on dimension d, horizon H and sample size n. The divergence term ϕ h ⊤ ( Σ h,D + λ h I) -1 ϕ h measures the conditioning of the regularized covariance matrix ( Σ h,D + λ h I) along a specific direction of ϕ h . When the feature mapping ϕ operates within a d-dimensional space, it is reasonable to assume thatϕ h ⊤ ( Σ h,D + λ h I) -1 ϕ h ≤ c ′ d .The bound (25) then reduces to J(π ⋆ ) -J( π) ≤ c dH 2 / √ n . Regarding the dependence on horizon H, we conjecture that by incorporating the law of total variance in a more refined manner, it may be possible to further reduce the dependence by a factor of √ H. Under these conditions, the bound takes the form J(π ⋆ ) -J( π) ≤ c d H 3 /n.In this experiment, a car is situated in a valley between two hills. The car's objective is to overcome the gravitational pull and reach the top of the right hill by efficiently controlling its acceleration.The Markov decision process underlying the mountain car problem has a state space S ⊂ R 2 and an action space A ⊂ R. The state s = (p, v) consists of the current position p and velocity v, whereas the scalar action a = f corresponds to the applied input force. The state variables (p, v) and action f are restricted asp ∈ [p min , p max ] = [-1.2, 0.6], v ∈ [v min , v max ] = [-0.07, 0.07] and f ∈ [f min , f max ] = [-1, 1] .The mountain is described by the functionm(p) = 1 3 sin(3p) + 0.025 (p max -p)(p -p min ),over the interval p ∈ [p min , p max ].Let m ′ be the derivative of the mountain shape function m, which represents the instantaneous slope, and let (σ v , σ p ) = (0.01, 0.0025) be a pair of standard deviations that dictate the amount of randomness in the updates. For an interval [a, b], we define the truncation functionΨ [a,b] (u) : =    u if u ∈ [a, b], b if u > b, a if u < a.With this notation, at each discrete time step h = 0, 1, 2, . . ., the position and velocity of the car evolve asv h+1 = Ψ [vmin,vmax] v h + 0.0015 f h -0.0025 m ′ (p h ) + σ v Z h p h+1 = Ψ [pmin,pmax] p h + v h+1 + σ p Z ′ hwhere (Z h , Z ′ h ) are a pair of independent standard normal variables. Note that the system dynamics are non-linear due to both the presence of the derivative m ′ and the truncation function Ψ.The objective of the car is to reach the peak of the mountain, designated by the position p goal = 0.45. The reward at state-action pair (s, a) is given by r(s, a) : = -1 10 f 2 + 100 max{0, p -p goal } 2 .For any policy π, we define the γ-discounted value functionJ(π) : = E π ∞ h=0 γ h r(S h , A h ) ,using γ = 0.97. The initial state s 0 = (p 0 , v 0 ) is generated with p 0 following a uniform distribution over the interval [-0.6, -0.4], and we initialize with velocity v 0 = 0.Here we describe the use of fitted Q-iteration (FQI) with linear function approximation to estimate the optimal Q-function, along with the corresponding greedy policy π.We approximate the the optimal Q-function (s, a) → Q ⋆ (s, a) using a d-dimensional linear function class with d = 3000 features. We begin by defining the base feature maps ϕ p : [ p min , p max ] → R 50 for position, and ϕ v : [ v min , v max ] → R 15 for velocity, with components given by ϕ p,2j+1 (p) : = cos(jp), for j = 0, 1, . . . , 24, and ϕ p,2j (p) : = sin(jp), for j = 1, 2, . . . , 25 ;EQUATION: = cos(jv), for j = 0, 1, . . . , 7, and ϕ v,2j (v) : = sin(jv), for j = 1, 2, . . . , 7.To represent the action a ≡ f , we define the base action feature mapϕ f (f ) : = 1, f, f 2 , f 3 ∈ R 4 .The overall feature map ϕ : S × A → R 3000 is constructed by taking the outer product of the three base feature maps ϕ p , ϕ v , and ϕ f as follows:EQUATIONTaking all possible triples of the three base features in the outer product leads to the overall dimension d = 3000 = 50 × 15 × 4. Given a weight vector w ∈ R 3000 , we define the function f w (s, a) : = ⟨w, ϕ(s, a)⟩, and we approximate the optimal Q-function using the function classF : = f w | w ∈ R 3000 .Fitted Q-iteration (FQI) We employed fitted Q-iteration with the linear feature ϕ : S ×A → R 3000 to estimate an optimal policy π. The FQI process begins by initializing the weight vector as w 0 : = 0 ∈ R 3000 . In each iteration, we first use the datasetEQUATIONcorresponding to a stochastic estimate of the Bellman update applied to our current Q-function estimate f wt . The polynomial form of the force feature ϕ f allows for a closed-form solution to the maximum operation required in equation (27) . Given these pseudo-responses, we then update the weight vector w t → w t+1 via the ridge regressionEQUATIONwhere λ n = 0.01 n in all experiments reported here. We terminate the procedure after at most 500 iterations, or when there have been 5 consecutive iterations with insignificant improvements in weights, where insignificant means that ∥w t+1w t ∥ 2 / √ 3000 < 0.005. Letting w represent the weight vector obtained from this procedure, the resulting policy π is given by selecting the greedy action based on the Q-function estimate f(s, a) : = ⟨ w, ϕ(s, a)⟩.Our experiments were based on an off-line dataset consisting of n i.i.d. tuplesD = (s i , a i , r i , s ′ i ) n i=1 ⊂ S × A × R × S,where the state-action pairs(s i , a i ) = (p i , v i , f i ) n i=1were generated from a uniform distribution over the cube In each experiment, we generated a dataset D, estimated an optimal policy π based on the data, and evaluated the return J( π). For each sample size, we conducted 80 independent trials. In order to evaluate the return J( π), for each initial position p 0 = -0.5 + 0.2 j/1000 with j = -500, -499, -498, . . . , 499, we simulated 30 independent 1000-step trajectories by executing the estimated policy π. The average return over the 30 × 1000 trajectories is used as the estimate of J( π).[p min , p max ] × [v min , v max ] × [f min , f max ].In order to approximate the policy7 π † that represents "ground truth", we conducted a single experiment with sample size n = 6.4 × 10 6 to obtain π † . We simulated 1000 trajectories for each initial position p 0 and calculated the average return, which serves as the reference value J(π † ). The value sub-optimality is then computed as the difference J(π † ) -J( π).In this appendix, we collect the verification of various auxiliary claims made in the main text.In this appendix, we prove a useful inequalityEQUATIONwhich holds for the state-action occupation measures (3). This bound is used in the proof of bound (20) in Appendix B.2.By definition, we have∥P ⋆ h f ∥ 2 h = E π ⋆ (P ⋆ h f ) 2 (S h , A h ) = E π ⋆ E h f(S h+1 , π ⋆ h+1 (S h+1 )) S h , A h 2 .According to the property of variance, we can deduceE π ⋆ E h f S h+1 , π ⋆ h+1 (S h+1 ) S h , A h 2 ≤ E π ⋆ f 2 S h+1 , π ⋆ h+1 (S h+1 ) = ∥f ∥ 2 h+1 .As a consequence, we find that ∥P ⋆ h f ∥ h ≤ ∥f ∥ h+1 . Applying this inequality recursively leads to the conclusion that for any indices 1 ≤ h ≤ h ′ ≤ H, we haveP ⋆ h,h ′ f h = P ⋆ h P ⋆ h+1,h ′ f h ≤ P ⋆ h+1,h ′ f h+1 ≤ P ⋆ h+2,h ′ f h+2 ≤ • • • ≤ ∥f ∥ h ′ .This establishes the bound (29) .E.2 Proof of the telescope inequality (6) For completeness of this paper,8 let us prove the telescope relation (6) stated in Section 2.3. For any policy π = (π 1 , . . . , π H ) and sequence of functions f = (f 1 , . . . , f H ) with f H = r H , we have the "telescope" relationEQUATION)Here the value functionEQUATION)Letting π = π in equation (31a) yieldsEQUATION)Since π is a greedy policy with respect to function f , we have f 1 (s, π 1 (s)) ≥ f 1 (s, π 1 (s)), and T π h f h+1 = T ⋆ h f h+1 ≥ T π h f h+1 for any policy π. Using this fact and subtracting equations (31a) and (31b), we obtainV π 1 (s) -V π 1 (s) ≤ H-1 h=1 E π -E π T ⋆ h f h+1 -f h (S h , A h ) S 1 = s .Finally, taking the expectation over the initial distribution ξ 1 yields the claimed inequality (6) .NeurIPS Paper Checklist Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory Assumptions and Proofs some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: The submission provides a supplementary code document to reproduce the Mountain Car experiment.• The answer NA means that paper does not include experiments requiring code. 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 a 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. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]Justification: The paper focuses on purely theoretical aspects of reinforcement learning and does not discuss direct societal impacts, given its theoretical nature. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.In general, different function classes may be selected at each stage h = 1,2, . . . , H; here, so as to reduce notational clutter, we assume that the same function class F is used for each stage.We let ∂F be the set of all difference functions of the form g = ff for some f, f ∈ F .Results of this type are known; for example, analogous results can be found in past work (e.g., Theorem 2 of the paper[34]; or Lemma 3.2 in the paper[7]).Please refer to, for example, Lemma B.3 in the paper[20] for further details.See Appendix C.2 for the details of this calculation.To be clear, the purpose of this scheme is primarily conceptual, rather than practical in nature.In general, it is not guaranteed that π † is equal to the optimal policy π ⋆ , due to approximation error that might arise from using the linear function class defined here.We are not claiming novelty here; see Theorem 2 of the paper[34]; or Lemma 3.2 in the paper[7] for analogous results. 
 
 Appendix:  


Decision: The paper presents conditions under which continuous (in states and actions) reinforcement learning converges rapidly in both online and offline settings. The reviewers are uniformly in agreement that the paper is deserving of acceptance. I have read the paper myself and agree that the results are interesting, and to my knowledge novel. I am confident that the results will be of interest to the NeurIPS community.

Reviews: review: paper_summary: paper_summary: This paper demonstrates how sample complexity can be improved under some conditions in offline and online RL.

It considers an episodic MDP framework with episodes of length H.

One of the contributions of the paper is that, under specific stability conditions for the MDP, getting Bellman residual errors < \epsilon results in a policy (more precisely a policy sequence) whose value sub-optimality is bounded by a quantity proportional to \epsilon^2.
As a result, in offline RL, algorithms for which \epsilon is proportional to n^{-1/2} (it is proved for ridge-regression-based Fitted Q-iteration in the paper, under some assumptions) result in a sub-optimality that dwindles proportionally to 1/n, and not n^{-1/2} which is the usual result (n is the number of samples).

For online RL, the paper studies a 2-phase algorithm based for on exploration for T0 episodes (similar to the offline case), and a fine-tuning phase based on online RL performing a sequence of rounds (and the number of episodes in round k is twice the number of episodes in round k-1). In this context and with the same assumpions as before, the paper shows that the regret upper bound grows as log(T), T being the total number of episodes.

These results identify cases in which the rates of convergence are significantly faster than the usual theoretical results, and intuitions related to these "fast rate cases" are extensively discussed in the paper, and in particular their links with optimism and pessimism.

An illustration of fast rate RL achieved in practice is shown on the famous Mountain Car problem.
strength_weakness: strength_weakness: - Discussing thoroughly on the qualitative implications of the results is a strength of the paper, but in some sense it can also be a weakness, since it can be tempting to jump to conclusions that are more global than the restricted context in which results have been proven. For instance, considering all the assumptions on which the results depend, statements like "Thus, the pessimism principle can be useful for problems with smaller sample sizes" must be taken with caution.
questions: questions: - The global approach has similarities with the much simpler result of logarithmic regret obtained in ["Logarithmic Regret Algorithms for Online Convex Optimization", Hazan et al.]. It raises the following: could some of the results or new results (maybe in a non-episodic framework) be obtained as direct consequences of the result in ["Logarithmic Regret Algorithms for Online Convex Optimization", Hazan et al.]? Typically, x would be a policy, and the update on x would depend on a policy gradient (e.g. with REINFORCE). In this case, would there be any relationship between the assumptions of the paper and the strong convexity required by ["Logarithmic Regret Algorithms for Online Convex Optimization", Hazan et al.]? In a similar direction, analyzing the relationships between the proposed approach and the following papers would be interesting:

Lale, S., Azizzadenesheli, K., Hassibi, B., & Anandkumar, A. (2020). Logarithmic regret bound in partially observable linear dynamical systems. Advances in Neural Information Processing Systems, 33, 20876-20888.

Agarwal, N., Hazan, E., & Singh, K. (2019). Logarithmic regret for online control. 
Advances in Neural Information Processing Systems, 32.

- Are the required theoretical assumptions valid in the Mountain Car environment? 

- Typos: 

line 369 "In the initial T0f episodes" => "In the initial T0 episodes"

line 854 "was previously defined (??)"
limitations: limitations: The limitations of the results are well addressed in the paper.
paper_summary: paper_summary: In the context of continual control reinforcement learning, this paper presents a new analysis of how a good Q-function estimate (measured in terms of the Bellman residual norms) induces a good greedy policy (measured in terms of the value gap compared to the optimal policy). The key contribution is the formalization of two "stability" criteria under which the authors prove $O(n^{-1})$ convergence of fitted Q-iteration in the offline RL setting and $O(\log T)$ regret in the online setting, considerably faster than previous results which do not make "stability" assumptions.
strength_weakness: strength_weakness: 1. This is the most important point. The two assumptions "Bellman stability" and "Occupation measure stability" are very difficult to understand. There is no proper motivation or illustrative example about when to expect these conditions to hold, and when not to expect so. The authors do translate these conditions to the special case of linear function approximation, but also these "specialized" conditions ("Curv1" and "Curv2") are unintuitive. The paper is very full already and I can understand why the authors decided to save space and not include in-depth discussions of these conditions. However, as these assumptions are really at the core of their results and what differentiates their setting from the "slower rate" setting, I believe the paper would be much clearer if, for example, Section 3 were shortened considerably and instead the stability assumptions were explained in more detail.
2. It is not clear to me what the authors mean by "stability". This term has a concrete meaning in control theory, but I don't understand how this meaning is related to their definitions of "Bellman stability" and "Occupation measure stability". This point is closely related to point 1. 
3. (minor) The theorem statements should include the full set of assumptions. For example, Theorem 1 should explicitly say that it holds only under the two stability assumptions.
4. (minor) In Figure 1b, the x-axis uses a logarithm base of $e$, while the y-axis uses the base $10$. This is not just unusual, it also makes the discussion about the slope of $-1$ vs. $-\frac{1}{2}$ confusing, as the plot actually shows a slope of $-\frac{1}{\ln 10}$.
5. (minor) The probability notation in line 307 is confusing. Do you mean $\mu_h^\star(s, a) = \mathbb P_{\xi_1, \pi^\star}[S_h = s, A_h = a]$?
questions: questions: The analysis presented in the paper shows that fitted Q-iteration converges much faster than previous results show if the environment satisfies certain stability criteria. Is it possible to exploit this stability explicitly in a new method, or is the rate achieved by the general FQI method already optimal?
limitations: limitations: The authors adequately address the limitations of their work.
paper_summary: paper_summary: The paper presents a novel approach to deriving convergence using two 'stability' properties or assumptions. Improved bounds are derived which show faster convergence than predicted by traditional bounds.
strength_weakness: strength_weakness: 1. Validating the theory with some MDPs, even toy domains can greatly help in increasing the quality of paper.
questions: questions: None
limitations: limitations: The authors have discusses limitations of their work in Section 4.

Comments: title: Please respond to the authors
Please respond to the authors
Please respond to the authors
comment: I thank the reviewers for their rebuttal. I ll maintain my score of acceptance.
Thank you for your detailed response. I will keep my rating as is.
Thank you for these answers and clarifications. My recommendation of acceptance remains.
Hello reviewer bfUp: The authors have responded to your comments. I would expect you to respond in kind.
Hello reviewer PVTM: The authors have responded to your comments. I would expect you to respond in kind.
Hello reviewer gsVp: The authors have responded to your comments. I would expect you to respond in kind.