Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces
Authors: Yaqi Duan
Martin J Wainwright
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
continuous control
stability analysis
Primary area: reinforcement_learning
TL;DR: We introduce an RL framework for continuous state-action spaces with faster convergence rates than previous ones. Key to this are stability conditions of the Bellman operator and occupation measures that are prevalent in continuous domain MDPs.

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.

Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces
Yaqi Duan
Department of Technology, Operations, and Statistics Stern School of Business, New York University
New York, NY 10012
yaqi. driidduudsterrn nyw...........mm .nyu.ddu edu
Martin J. Wainwright
Laboratory for Information and Decision Systems, Statistics and Data Science Center
Department of Electrical Engineering and Computer Science, and Department Mathematics Massachusetts Institute of Technology Cambridge, MA 02139
wainvrigworkOgmail. com
Abstract
We introduce 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 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.
Introduction
Many domains of science and engineering involve making a sequence of decisions over time, with previous decisions influencing the future in uncertain ways [3] 22 31 32]. For instance, clinicians managing diabetes [36] or engineers optimizing plasma control in tokamak systems [5] must develop policies that adapt based 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 (00,, its application in data-scarc scarcs areas like healthcare (36] and finance [27 remains challenging due lack of history, or underlying non-stationarity. With limited data, characterizing and improving the sample complexity of RI. 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.. 37 35)) give procedures that, when applied to dataset of size yield value gap that decays at the rate 1/ l/vn. In the on-line setting, there are various procedures that yield cumulative regret that grows at the rate /T 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 value gap decay of 1/n and reducing regret growth log T.
(e.g., 18 20 19
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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

spaces, Roughly speaking, these conditions ensure that the evolution of the dynamic system depends "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, minor torque or motion perturbation that occurs during a single step should not cause notable deviation from the intended trajectory. Similarly, in clinical treatment, slight deviations in medication dosage should not significantly compromise effectiveness or safety.
1.1 A simple illustrative example: Mountain Car
The "Mountain Car" problem, benchmark continuous control task, illustrates the acceleration phenomenon and underlying stability. In this task, as shown in Figure car must reach the top of 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 optimmttyl decay at a rate of 1/n, a significant improvement over the classical rate of 1/ /T. as detailed in Figure b). (See Appendix D for further explanation. The experiment ran for 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.
Value sub-optinality versus sumple size
10P
Value sul hh--oyimmallty
Sample size
(a)
(b)
Figure 1: Illustration of the "fast rate" phenomenon using FQI the Mountain Car problem. Each red point in the plot represents the average value sub-optimality J(x*) ) - (f.,) from T = 80 Monte Carlo trials, with the shaded area showing twice the standard errors. The blue dashed line is 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.. "slow rate".
1.2 Contributions of this paper
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 general result (Theorem I 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 rate of n & to n while in on-line learning, it enhances the regret bound from vT log T.
Reconsidering pessimism and optimism principles: Our framework provides a novel perspective on the roles of pessimism [2 4 and optimism [18 20
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- particular, they are not required as long as one has sufficiently accurate pilot estimate policy. Moreover, our analysis shows that some procedures based on certainty
19

---

equivalence can achieve fast-rate convergence, showing that the benefits gained from incorporating additional pessimism or optimism measures may be limited in this context.
1.3
Related work
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), is well-understood that the local geometry around the optimum determines whether fast rates can be obtained. For instance, when the loss function ex- hibits some form of strong convexity (such exp-coneave loss) or strict saddle properties, can lead significant reductions in additive regret from O(VT) to just (log T) in stochastic approximation (e.g., (15)). or a decrease in the error rate from n à to n in empirical risk minimization [23] [4]. These fast rate phenomena rely 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 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
that performs htg/mmarginlldependeee 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.
33 25
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 (2 29 that value sub-optimality can be connected with the squared error in system identification. Our general theory can also be used derive guarantees for LQR problems, as we explore in more detail in follow-up paper [8]. Stability also arises in the analysis of (deterministic) policy optimization and Newton-type algorithms 26 where it is possible to show superlinear convergence in a local neighborhood. This accelerated rate stems from the smoothness of the on- on-policy transition operator pay 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.
2
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-basce methods, before turning to the statement of our main result in Section 2.2 In Section [2.3)on]]]] we provide intuition for why stability leads to faster rates, and discuss consequences for both the off-line and on-line settings of RL.
2.1 Markoy decision processes and value-based methods
Basic set-up: We consider an episodic Markov decision process (MDP) defined by a quadru- ple (S,A = K=!, fr% )/ We assume that the rewards Th : S A + are known; however, this condition can be relaxed. A policy Th at time h is a mapping from any state s to distribution (- s) over the action space A. If the support of 7. s) a singleton, we also let (+) E A denote the single action to be chosen at state Given an initial distribution { over the states time = 1, the expected reward obtained by choosing actions according to a policy sequence π = (TI,..., TH) ) is given by J(x) = J(T:; =Eg, | r' (Sh, An)]. where S₁ ~ E1, Sh+1 ~ Pn(- | Sh, An) and Ap, ~ T.(. Sn) for 1.2,..., H. Our goal is to estimate optimal policy Tr" E arg max, J(TT).
3

---

Value functions and Bellman operators: Starting from given state-action pair (s. stage h, the expected return over subsequent stages defines the state-action value function Q% (s, a) = En Ei AN)),AN) S. = s, A,, a The sequence of functions Q" = (QT,.... QT) ) 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 hi we introduce linear transition operator (PA ()s a) IsxA J(s', d') Paad'' s,a) ( s') for any function f RSXA, With this notation, the Bellman evaluation operator at stage h takes the form
(Th (), = rn), + (PI
From classical dynamic programming, the Q-functions Q must satisfy the Bellman relations (s, (7,))s a) for h = I,..,, -
Bellman principle for optimal policies: Under mild regularity conditions, there at least one policy π² such that, for any other policy лτ, we have Q7 (s.a) a) 2 Q (s, a), for any h E [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' obtained by setting QH rn. and then recursively computing Q Th, Qh+1 for h = H 1, 2, 1, with the Bellman optimality operator defined as
(Th f) a) = (n(s, a) + En max f(S", .') s,a]
for ~ PM(- 8, s.
(2)
d'EA
Value-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 optimal policy π²: (1) Construct an estimate Q = (f1...., f()
of the optimal value function Q' (Qi ..... Q7 (2) Use Q to compute the greedy-optimal policy T (s) E arg max, (s, a) for = 1, 2, H. It should be noted that there considerable freedom in the design of 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 class I of functions (s, a) - [(s, a) used to approximate the state-action value functions [ We assume that the function class I is rich to the Bellman evaluation operators- to ensure that for any greedy policy π induced by some f = (fi..... fH) 3 we have the inclusion T 5 C g for h = 1, L,..., 1-111 1. We that this condition depends on the structure of the transition distributions PA (- 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 suitably differentiable function, will remain suitably differentiable.
2.2
Stable problems have fast rates
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 bound on the value gap J(Tx") (
At a high level, existing theory provides guarantees of the following type: if the Q-function estimates are e-accurate for some E E (0, 1), then the value gap bounded by a quantity proportional e. In contrast, our main result shows that when the MDP is stable in a suitable sense, the value gap can be upper bounded by quantity proportional to e", 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 certain norm. Here we define them with respect to the L2-noom induced by the
In general, different function classes may be selected at each stage h = 1, 2, H:: here, so as to reduce notational clutter, assume that the same function class F is used for each stage.

---

state-action occupation measure induced by the optimal policy namely for any f 0.3
Ilf IIx
E [f(S A.]]
(3)
and 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, require that there is scalar Ki, such that
Th Ja+1 Th Qh+illa S Ki || - Qi+1lla41
(Stb(T))
for any N. Moreover, for any pair (h, of indices such that 1 I h h' S H define
KA,N (T*) := Ni, 1T
Condition (Stb(T))
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 backward manner, that it important control the propagation of estimation errors across the iterations. Condition (Stb(T) )) captures this property, since it implies that
Th Th+1 TI Jw - Th Thtt The Qi ll, I (T*) || - Qi
which shows how the estimation error (Jn- Qi.)) at step h can be controlled in terms of estimation error 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
(Ti.... - Ths "h+1:...,,7W
and (Ti, 7 The T
that only differ at the h-th step, where o has been replaced by Th 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 [ - Q ||a between the two Q-functions fn. and Q; that induce n, and n respectively.
We adopt PA as a convenient shorthand for the transition operator P and define the multi-step transition operator Pi., = P% Ph++1 ... -Ph--1 Using this notation, for any h' 2 h + 1, we require that there is a scalar (T=") such that
Ee (PT.(((P (S., (Sa)) - (SA,
(TT ||5h Qilla (Stb(E)
sup
119||
Q
gEa
11
for any f E N. The renormalization in this definition serves to enforce natural scale invariance.
With these notions of stability in hand, we are now equipped to state our main result. Taking as imput value function estimate Q it relates the induced value gap to the Bellman residuals Tí fa+1 - Sn- Note that these residuals are a way quantifying proximity to the optimal value function Q", which has Bellman residual zero by definition. We assume that Q has Bellman residuals bounded as
Th Pr+1 Sn lla
Eh for 1, 2,...... 1
(4a)
for some sequence & = (E
EH EH = 0) that satisfies the constraint
H
1
Eh > H h W=h+1
Σ
EM
for h = 1,2, H 11
(4b)
This last condition means that the Bellman residual E larger than 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 special case, the bound (4b) holds when En = for all stages.
With this set-up, we have the following guarantee in terms of the stability coefficients (AA (Te*) and BA, (T*) from conditions (S) and (Stb(T))
We let 0.50 be the set of all difference functions of the form g f J for some f. $.
5

---

Theorem 1. There is neighborhood of Q" such that for any value function estimate f with e-bounded Bellman residuals (4). the induced greedy policy i has value gap bounded as
H
H KIN (T*) eN en-
J(x') J(
2
Σ M'=h
(TT" eN
(5)
1Q
h=1
See Appendix A for the proof.
Treating dependence on the stability coefficients as constant, the main take-away is that value sub- optimality 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 an upper bound of the form
J - J
s²,
where e is 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.
2.3 Intuition for fast rates: Smoothness and cancelling terms in the telescope bound
Why does "fast rate" phenomenon formalized in Theorem D 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 = (f1..... fH). let के denote the induced greedy policy. Then the value gap of से with respect to arbitrary comparator policy π is bounded
#-1
J(A)
S
(Ex ( (Fx Jnti (S,, An)
(6)
1=1
This result follows by "telescope" relation induced by the structure of the Bellman updates For completeness, we provide a proof of the telescope bound in Appendix E.2
A key feature of inequality O is the difference of two expectations E, Eq, corresponding to the occupation measures under π versus म. In standard uses of this inequality, an initial argument used to guarantee that one of these expectations is negative, and so can be dropped [20] (1].
In contrast, the proof of our Theorem Saaeeemmexppe ence of expectations directly. Doing so can be beneficial-and lead to "fast rates" " because various terms this difference can cancel each other out. Specifically, under the smoothness conditions that underlie Theorem [ 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-alone along with a number of auxiliary results laid out in the proof- so as to upper bound the value gap by quantity proportional to the squared Bellman residual e².
exploits
refined approach, one that handles the differ-
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 We do so in the following two subsections.
(e.g., 18 20 21
19
12 35
2.3.1 Pessimism for off-line RL
In the off-line instantiation of RL, the goal is to learn "good" policy based on pre-collected dataset D. Note that further interaction with the euvironment permitted, hence the notion the learning being lif-line. More precisely, an off line dataser D of size consists of quadruples
D D= = (Sn. an, sh, The i== }
where 8 and on, represent the i-th state and action at the h-th step in the MDP; sh, is the successive state; and Th, = rn(5), ap, denotes the scalar reward. Note that while the successive
'Results of this type are known; for example, analogous results can be found in past work (e.g.. Theorem 2 of the paper [34] Lemma 3.2 in the paper (7).

---

states are defined by transition dynamics, and the rewards by the reward function, there are no restrictions on how the state-action pairs (sh, i: (n. 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 to estimate policy शे = R, that (approximately) maximizes the expected return ( We expect that-at least for sensible method for estimating -he the value gap J ( J J(f,) 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- 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- -aay with
as) S Th fn+1(s,a)
(7a)
with high probability over state-action pairs (s. Thus, the estimated value (1, a) is an under- estimate of the Bellman update, form of conservatism that protects against unrealistically high estimates due to poor coverage. Doing in the appropriate way ensures that
F (Tr fn+1 (S,, Ab)] S.
(7b)
Applying this upper bound to the inequality (6) yields the sub-optimality bound
((x) - ((A)
Σ Ex frtt (S,.
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 "slow" 1/v2 rate in terms of the sample size n (e.g.. (2]).. contrast, an application of Theorem can lead to value gaps bounded by 1/n.
2.3.2 Optimism in on-line RL
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 's dynamics. In the f-th episode, the agent learns an optimal pol- icy A (3) using existing observations, implements the policy and collects data {<(] af r(()) }==1
(t) from the new episode. In each round, the system starts at initial state s 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 f, we incur the instantaneous regret J JTT") - where πt is any optimal policy. Over T rounds, we measure performance in terms of the cumulative regret
T Σ [
Regret ( (T))
]T=)==
max policy क
Σ -(TT)) ((T
(8)
Regret round
In 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 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 that
(n(s,a) 2 T (s,)
(9a)
7

---

with high probability over state-action pairs 4 Note that (s. a) is optimistic in the sense that it is an over-estimate of the Bellman update Th f a). In this way,
ensure that
E (Th Jht1 fn) (Sh, A,) S O.
(9b)
Combining this inequality with the telescope bound O allows one to upper bound the regret
Regret ( (E
J(
ΣΣ E Rgt [[h -Th f1+1) An)]
which only includes single portion of the Bellman residual. In the case of tabular or linear representations of the Q-functions, it results in regret rate of vT (e.g.. see the papers [88 20) ) In contrast, an appropriate use Theorem leads to regret growing only as log(T"), which corresponds to 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 to control this difference. As we discuss in the sequel, such smoothness conditions rule out certain "hard instances"
used past work on lower bounds (e.g. [8 20 37
Consequences for linear function approximation
In this section, explore some consequences of our general theory when applied to value-based methods using (fiite-dimennionaal) linear function approximation.
Let Φ : S x A Rd be given feature map on the state-action space, and consider linear expansions of the form (s, a) (Ø(s, a), w) = > wy (s,),,,,) where IRd is weight vector. We adopt the conventional assumption that || s, a)ll I 1 and (s, E [0, 1] for all state-action pairs. Defining the linear function class $ := fw E Rd note that the Minkowski difference class 0. equal to
In our analysis of linear approximation, we make use of the norm llf == Ex. [f? An)]. corresponding to T.2-norm under the occupation measure induced by the optimal policy n²
3.1 Consequences for off-line RL
We now turn to some implications of Theorem for off-line reinforcement learning. Let us recall the off- off- setting: for each h I,..., 1, we given dataset D,, {(s,,s, 0h,ss $ /= of quadruples, from which we can compute estimates f ( with certain Bellman residu- als {Ex h=1 [aaaM-l which then appear in the bound (5). The remaining factors 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 fEN M
H-1 for particular estimator.
3.1.1 Fitted Q-iteration (FQI)
As an illustration, let us analyze the use of fitted Q-iteration (FQI) for computing estimates of the Q-function. At given stage h 1...., H 1, we can the associated data D,, define regularized objective function
La (f. 9)
1 Drl
Σ (f(sh. an,)) (r max g(5h, 1s. ....
a)) Af()).
aeA
Here g represents the target function from stage h + 1, and it defines the targeted responses gh,i(g) Th, + max g(sh, a). For given target g, we obtain a Q-function estimate for
Pleesse refer for example, Lemma B.3 the paper 20 for further details.

---

stage h by minimizing the functional f + (.(f.)) Given that our objective is defined with a quadratic cost, doing so can be understood as a regression method for estimating the conditional ex- pectation that underlies the Bellman update- vvz. Th g(x, a) = El vh,) (8h, in (s, a) Here (f) = A w [ for f f= (d(-), w) is a regularizer, with A 2 0 being the regulariza- tion weight. Given this set-up,
can generate Q-function estimate f (f Sn) by first initializing JH = rH, and then recursively computing fn. = arg min Ln fh+1). for h = H- - 1, 2, ...., 2,
3.1.2 Fast rates for FQI-based estimates
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 corollary of Theorem 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 suffi- ciently large sample size and with suitable choices of the regularization parameters (>r) the bound (5) from Theorem Aheorem[holdde hoodd with
H-1
En - - log(dH/8)
(10)
with probability at least 1 5.
We omit the proof of Corollary I 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 consider some consequences of the bound (TO) under the following assumptions: (i) (T*) = 0(1): (ii) Ki. (*T) = O(v O(Va); (iii) ||Q H h
+ 1. Then it can be shown
that the bound from Corollary | takes the form
J ((=))- S 2/2 n1 log(dH//))
(1
and is valid for sample size n 2 H3 Alternatively stated, Corollary guarantees that for FQI using ridge regression with d-dimensional function approximation, the number of samples n()) required to obtain e-optimal policy is at most
(e H H
(11b)
where we use x to denote 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 established a sample complexity of the order Tizmn x H3/22 Consequently, we see that once the target error is relatively small-e E (0, 1) then stable MDPs can exhibit much smaller (1/e) sample complexity.
It should be noted that past work (e.g., 21 37
) has established (1/c2)-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 (TTb), because the "hard instances" used in these lower bound proofs violate the stability condition (Sth())) 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 D 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 sharp contrast with many other methods for off-policy RL. such as pessimistic forms of Q-lcarning and actor-critic methods (e.g., (7).
To be clear, noted following the bound (aa), the guarantee from Corollary | requires the sample size to be lower bounded as n 2 ed H3 In contrast, pessimistic schemes only require a sample size sufficiently large to ensure validity of the Bellman residual upper bounds that underlie Corollary - meaning that n 2 d up to logarithmic factors. Thus, the pessimism principle can be useful for problems with smaller sample sizes.
SSee Appendix C.2 for the details of this calculation.

---

3.2 Consequences for on-line RL
In this section, we explore some consequences of Theorem | for on-line reinforcement learning. We begin by describing two-stage procedure that allows to convert the risk bounds for FQI from off-line RL into regret in on-line RL:
Phase 1
(Exploration) In the initial Tof episodes, the focus is purely on exploration, resulting in an estimate of Q-function denoted as f(rt))
Phase 2 (Fine-tuning) For 0, ......... , K- with K [log (T/To)] repeat:
In the f-th episode, for each t = To 2 + 1,.... induced by function fl
......I6 To 2 execute the greedy policy
Update the Q-function estimate f using FQI based on observations collected from episodes To 2 1, 2 2,...,,2 2
We assume the burn-in time To is large enough so as to ensure the pilot Q-function estimate f(Ta) obtained in Phase I falls within certain "absorbing" region ((() 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 sufficiently large burn-in time To and with suitable choices of the regularization parameters {Milk=1 1 the two-phase scheme achieves regret bounded as
(T) S cTTo H dvd H log T 1og(dH
with probability at least 1 5.
See Appendix for the proof.
The leading term (as T grows) in the regret bound grows log T, which is much smaller than the typical -ate found in past work [18] 20 The V rate has been
Sharper bound regret:
shown to be unimprovable in general, but the worst-case instances 18 20 that lead /T-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 iidiorationunddrrii 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 is necessary only during the burn-in Phase 1.
4 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, main result (Theorem 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, well 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 function approximation (c.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 go beyond the idcalized completeness condition used in this paper, and treat the role of model mis mniisspccfiicttin.
consider the extensions dependent data and non-parametric
TTo be clear, the purpose of this scheme is primarily conceptual, rather than practical nature.
10

---

Acknowledgements
This work was partially supported by NSF grant CCF-1955450, ONR grant N00014-21-1-2842, and NSF DMS-2311072 to MJW.
References
[1] A. Altamimi, C. Lagoa, J. G. Borges, M. E. McDill, C. Andriotis, and K. Papakonstantinou. Large-scale wildfire mitigation through deep reinforcement learning. Frontiers in Forests and Global Change, 5:734330, 2022.
[2] H. Bastani, M. Bayati, and K. Khosravi. Mostly exploration-free algorithms for contextual bandits. Management Science, 67(3):132--1399, 2021.
[3] D. Bertsekas. Lessons from AlphaZero for optimal, model predictive, and adaptive control. Athena Scientific, 2022.
[4] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-679, 2020.
[5] J. Degrave, F. Felici, and J. B. et al. Magnetic control of tokamak plasmas through deep reinforcement learning. Nature, 602:414-419, 2022.
[6] S. Du, S. Kakade, J. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization in RL. In International Conference Machine Learning, pages 2826-2836 PMLR, 2021.
[7] Y. Duan, C. Jin, and Z. Li. Risk bounds and Rademacher complexity in batch reinforcement learning. In International Conference on Machine Learning, pages 1892-2902. PMLR, 2021,
[8] Y. Duan and M. Wainwright. Covariate shift linear quadratic control. Manuscript.
[9] Y. Duan and M. J. Wainwright. Policy evaluation from single path: Multi-step methods, mixing and mis-specification. arXiv preprint arXiv:2211.03899, 2022.
[10] Y. Duan and M. Wang. Minimax-optimal off off-policy evaluation with linear function approxima- tion. In International Conference on Machine Learning, pages 2701-2709, PMLR, 2020.
[11] Y. Duan, M. Wang, and M. J. Wainwright. Optimal policy evaluation using kernel- based temporal difference methods. arXiv preprint arXiv:2109, /2002, 2021.
[12] D. Foster, S. M. Kakade, Qian, and A. Rakhlin. The statistical complexity interactive decision making, arXiv preprint arXiv:2 2021.
[13] Gijsbrechts, R. N. Boute, J. A. Van Mieghem, and D. Zhang. Can deep reinforcement learning improve inventory management? Performance on lost sales, nual-sourcing, and multi- echelon problems. Manufacturing & Service Operations Management, 24(3):1349-13 1368, 2022.
[14] A. Gonen and S. Shalev-Shwartz. Fast rates for empirical risk minimization of strict saddle problems. In Conference on Learning Theory, pages 1043-1063. PMLR, 2017.
[15] E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimiza- tion. Machine Learning, 69:169-199 2007.
[16] He, D. Zhou, and Q. Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171-4180. PMLR, 2021.
[17] Y. Hu, N. Kallus, and M. Uehara. Fast rates for the regret of offline reinforcement learning. Conference Learning Theory, 134:2462-2462, 2021.
[18] C. Jin Z. Allen-Zhu, Bubeck, and M. Jordan. Is Q-learning provably efficient? Advances in neural information processing systems, 31, 2018.

---

[19] C. Jin, Q. Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficien algorithms. Advances in neural information processing systems, 14:44 13418, 2021.
[20] C. Jin, Z. Yang, Z. Wang. and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, PMLR, 2020.
[21] Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? International Conference on Machine Learning, pages 5084-5096, 2021.
[22] B. R. Kiran. I. Sobh, V. Talpaert, P. Mannion, A. A. Al Sallab, S. Yogamani, and P. Pérez. Deep reinforcement learning for autonomous driving: survey. IEEE Transactions on Intelligent Transportation Systems, 23()):9009 2021.
[23] T. Koren and K. Levy. Fast rates for exp-concave empirical risk minimization. Advances in Neural Information Processing Systems, 28, 2015.
[24] H. Mania, S. Tu, and B. Recht. Certainty equivalence efficient for linear quadratic control. Advances in Neural Information Processing Systems, 32, 2019.
[25] T. Nguyen-Tangg M. Yin, S. Gupta, S. Venkatesh, and R. Arora. On instance-dependent bounds for offlin reinforcement learning with linear function approximation. Association for the Advancement of Artificial Intelligence, 2023.
[26] M. L. Puterman and S. L. Brumelle. On the convergence of policy iteration in stationary dynamic programming. Mathematics of Operations Research, 4(1):60-69, 1979.
[27] A. Rao and Jelvis. Foundations of Reinforcement Learning with Applications to Finance. CRC Press, Boca Raton, FL, 2022.
[28] P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell. Bridging offline reinforcement learning and imitation learning: tale of pessimism. Advances Neural Information Processing Systems, 34:11702--1116, 2021.
[29] B. Recht. A tour of reinforcement learning: The view from continuous control. Annual Review of Control, Robotics, and Autonomous Systems, 2:253-279, 2019.
[30] D. Silver, J. Schrittwieser, K. Simonyan, Antonoglou, A. Huang, et al. Mastering the game of Go without human knowledge. Nature, 550(7676):354, 2017.
[31] S. Spielber, A. Tulsyan, N. P. Lawrence, P. D. Loewen, and R. B. Gopaluni. Toward self-driving processes: deep reinforcement learning approach to control. Amer. Inst, Chem. Eng. Journal, 65:e16689, 2022.
[32] I.. Tai, G. Paolo, and M. Liu. Virtual-to-real deep reinforcement learning: Continuous control of mobile robots for mapless navigation. In 20/7 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 31-36. IEEE, 2017.
[33] X. Wang, Q Cui, and S. S. Du. On gap-dependent bounds for offline reinforcement learning. Advances in Neural Information Processing Systems, 35: 14855-14877 2022.
[34] Xie and N. Jiang. Q" approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertuinty in Artificial Intelligence, pages 550-559. PMLR, 2020.
[35] M. Yin, Y. Duan, M. Wang, and Y.-X. Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.0 05804, 2022.
[36] C. Yu, Liu, S. Nemati, and G. Yin. Reinforcement learning in healthcare: A survey. ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
[37] A. Zanette, M. J. Wainwright, and F. Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 34:13626- 13640, 2021.
12

---

A Proofs of Theorem I
This section is devoted to the proof of Theorem | which consists of three main steps. These steps rely on two auxiliary lemmas whose proof's 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 I, we use a one-step expansion of the difference the occupation measures 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 constraint on the function estimation error d, (Fn, Q7, 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, (Stb(T)) to connect the Q-function error fr. - Qi with Bellman residuals. With this high-level view in place, we now work through the three steps.
Bellman stability
A.1 Step 1: Reformulation of the telescope inequality.
Recall the standard telescope inequality (6). involves the functions
Our proof makes of an alternative form, which
H-1
(MT;; s,a)
Σ W'
PhN (Th fN++1 (s,
(12)
Lemma 1. Given a Q-function estimate policy we have the bound
f -fr...,,fuuI. =TH) and the associated greedy
FH-1:
J S
Ez (T; 8h, (n())) An(T; sh (x())))
(13)
valid for any policy
See Appendix B. for the proof.
We apply the bound 13 with π = =T". Following some algebra, we find that
H-1 --1
J(TT)) J(
Σ
3(,, h²) Ew
h=1
M=hh
where Ew is upper bound the Bellman residual The term A(h, h!) is given by
Th Pw Fr IIx given in equation (4a).
{
1 [1lflln
Ex (P ff (sh, ((())) - (Ph. (sn, # m|]))))]]]
3(h, M²) =
sup (fll
(14a)
We note that the left-hand side of inequality (Stb(E) has similar form the term 3(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 upper bound on the coefficient B(h, h') defined by the estimated policy fे in terms of the analogous quantity defined by the optimal policy π -namely, the coefficient
{ { 11llln
Fy. [PP (sn, o, (sn)) (Pi. (sh. 7. (s))) }
feaf: >0 B(h,h):=
sup
(14b)
13

---

In order to do so, we demonstrate that sufficiently small function estimation error dn (fh Q7) ensures the inequality
--1
H --1 Σ Σ
3(h, EN 2 Am Mamh
8(h, h²) EN
(15)
Am
h
Once we have established this bound, we can replace
the term ((h,h)) with
KA, (T*) "-I11lil Q / using the inequality (Stb(E))
We summarize the result in the following auxiliary lemma:
Lemma 2. Suppose that the function eslimation errors satisfy da (Qn, Qi) S hH- for h 2.3....,H H. 1 and the sequence (H1,...,,H-1,,. 0) satisfies the regularity condition (bb). Then we have
1 Q ll. 1
H-1
-( J(F) S 2
{ k'=h
KAN (T() EN
(16)
See Appendix BB2 for the proof.
A.3 Step Connecting Q-function error and Bellman residuals
The remaining piece of the proof is to connect the function difference Fr - 2% with Bellman residuals
T, Л4+1 Jn, using the stability condition (Stb(T)) on the Bellman operator T This is relatively straightforward: indeed, we claim that
H-1
11 Qilla S
Σ h'=h
KhNN (T") 11TH PN41
Fre Il
(17)
Recall that O7 Th Q for h 1,2, ................................ 1. Therefore, have
hn Q = (Tx fit1 To (h+1) - (Tr futt1 fu)
By employing the triangle inequality and the Bellman stability given in equation (Stb(T) ) we derive that
F Qilla S 1h fr+t Fulla Th Futz Th Qi+illa
Th fr+t Jalla mh Fl Qh+11ll41
Applying this inequality recursively yields the claim
With this piece in place, we can complete the proof Theorem [
Indeed, we have
Fn
Qilla
J(TT) (
2
KA. (Tr*) Ew
11Q l|A
A=1
W=h
(6)
Ka (T*) EK
Ki, En
1Q
Here step (a) is a restatement of the bound (16) from Lemma 2 whereas step (b) follows from inequality (17 Thus, have established the claim given in Theorem I
B Proof of auxiliary lemmas for Theorem
We now turn to proofs the two auxiliary results used establish our main theorem, with Lemmas D and 2 treated in Appendices B.I and B.2 respectively.
14

---

B.1 Proof of Lemma 1
For any integrable vector function g = ((n....,9n) E RSXAXX we define
D(g)
Σ
(En- - Ean (Sp, (s An)]
(18a)
h=1
We claim that this functional satisfies the recursive relation
H
D(g)
Σ [gn ( (a())) (S( (A())) D(P
(18b)
h=1
where we have introduced the shorthand P" g = (PT 92, PH-19H (H, 0) E RRSAAH
Taking this claim as given for the moment, let us prove the bound 13 from Lemma | First, we set g (P*) / g (PT, 1,144 91th.--.. P 9H, o,...;0) in equation (18h) for h 0, 1.................... H- which yields
D((PT) g)
Σ
F [[PT hig (S (Sw (P (St, ax.
+ D( g).
Note that (PT) g 0, which implies D D(P"))" g) -.. We then sum the resulting bounds as to obtain
D(g)=
Σ
Eg [[PT gh [Sh, (8x)) (PT gn (Sp. (S.)))
(19)
IShSN'H
Setting g = T f f. or equivalently Ih = Tht FAt1 Fr.. equation (9). we find that
D f) Σ F (T; mn (= Sn, an (Sa))
where we have used the fact (12) that (A( En PiN (Tx Pwttt Fw.) Thus, have established the bound (13) stated in Lemma
remains establish the auxiliary claim (8b). Note that the functional D be decomposed as D(g)= = Dj + D2, where
D
Σ
Ex (S,, TT (Sw)) - gn (Sh, Fr. (Sx))
and
h=1
H
D2
Σ
[E
E+) (Sh, TA (Sw)))
hml
Applying the tower property of conditional expectation, we find that
D2
Σ
EE Ex) Elght 1 Th+i ( Sn. Anl]
1=1
H
Σ
(En
E+)
(PP gh+ (S,, An)] D(P
1=1
Combining the expressions for Dj and D2 above yields the claim 18b).
15

---

B.2 Proof of Lemma 2
The key step in proving Lemma 2 establishing that inequality (15) holds when the function estimation error dn (fh, Q7) is sufficiently small. order to do so, we need to establish upper bounds on the term ((h, h() by using 3(h, h²). In particular, will show that for any S S h²' -
8(h, h²) B(h, h))
Σ BG. h 1) 1) bs da (Frs Q%)
(20)
The inequality (20) is derived based on the definitions of metric da and parameter byr 1. After a close examination of the right-hand side of this inequality, becomes evident that as long as the function estimation error dj (fh, Qi, is sufficiently small, the terms associated with d, (fn, Q1) are negligible and are dominated by 3(h, I.). Consequently, inequality (T5) within the arguments in Appendix A.2 is likely to hold true.
With claim 20 assumed be valid this point, we now establish proper upper bound on the estimation error di (fh, Q%) under which inequality (I5) is satisfied. By taking linear combinations of inequality (20 using weights & (E1,...,E EH-1: EH 0), we obtain
H Σ
H-1H-1
Σ
3(h, eN Σ
Σ
3(h, 10) ew
H H-1h-1
H Σ EMC
+
Σ
B(j, h 10-1) 1) b9 dn Qi)
(21)
2= jml
h'mh
When the sequence = (EI...... -11 the bound (2I) reduces to
0) is regular in the sense that inequality
4b holds,
Σ ISNSN'H
3(h, h') EN 1
Σ
8(h, h') EN
IShSN'S
Σ
3(h, h¹) EW by (H- 12--)) Rt) dic4ifww41, Qu+11)
IShEWSH-2
Under the condition du (fr, Qi) S 26 - h 1) for 2 S H 1, the inequality above implies bound (I).. which further establishes the bound (16). as stated in Lemma
remains to prove the relation between 3(,, h²) and ((h, W). as shown in inequality 20
Proof of bound 20 It 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 3(h, k²) and (3h, h!), as given by equations (4ab and [4b). We apply the triangle inequality and derive that
BBh, 1/) - 3(h, 1()
(Ex - Ex.) ((Pr (),, ([(S), -Pi (Sh, An(SW))
sup
sup
[lfllN
1
[E4 Exr)
((Phh) P Ph.M f) P -)
reaf: 12
=: A,3h, h!).
The term (B h/) involves differences from two sources: (i) the difference in transition kernels Pi, P that captures the divergence between policies गे and î. (ii) the discrepancy of
occupation measures at the (h- - 1)-th step reflected by the difference in expectations Ez. E which is determined by the policies (mī --1)) and (f...... .)) until the (h- 1)-th step. We treat them separately and write
Ap h²) & (h- - 1, h²) 12 - 1),
(22)
16

---

where the functionals 1/2 and are defined as
{ Ilflll
(1 - 1, 1,) =
sup
(Ph-1 - -P%-1) Ph ofarsllaa 11a-11)
rea.: 11
1
v2(h- 1) =
sup 1>0
[[
(15 En (
fEA I|
We first consider the term V4. According to the definitions of metric d,, and parameter by we find that
(2) S dn dn Q7) bs lI
( Ph f fln-11 I dr dr Q7) 1|P7 fll,
which in turn implies
(2 1, 1) & by dn (fh, Qi)
(23a)
The proof of inequality (+) for by = 1, as mentioned above, can be found in Appendix E.1 As for term V2, claim that
12(h 1) S B0j h 1)
(23b)
Combining the bound (h, M) B(h, R²) + A8 h²) with inequalities 22
23a and 23b
establish the bound 20 as claimed. It remains to prove the claim (23b).
Proof of inequality (3bb: This proof is analogous to that of Lemma 1 an analogue of the functional D(g) from equation (Taa;; in particular, for any index It E [H 1] and function g 0gF define
We begin by introducing
Dx(2) = (E.. E&) [9(Sn, An)]
Using the notation of Dj rewrite the left-hand side of inequality (2hh) u2 1) sup rears: [I 1 (f11://///l Following the same arguments in the proof of inequal-
ity 18b). we can show that
(g) = E= (S o (S.)) ((hh, (S.)) Di g)
for h = 1,2...... H, (24)
where we set Dí =
We consider function g: p for 1 15 < h H - It follows from equation 24 that
(P = E [ (P) DDj
where we have used the relation Pj-iPj = Pi-1.A-- Recalling the definition of 3(j, 1) in equation (4a),, applying the triangle inequality yields
[P](j],-1 < 3 h - 1): 11fln-1 +
Summing this equation over indices j = 1, 2, ......AA h - yields
h-1
|-)((()) < Σ
B(j. h - 1) 11fll-11
/=1
which establishes inequality 23b
17

---

C Proof of corollaries
This section cotains proofs of several corollaries.
C.1 Proof of Corollary 2
We now turn to proving Corollary D regarding ridge-based FQI in on-line settings.
In Phase of pure exploration, the cumulative regret is always bounded from above by To H. During Phase 2 of fine-tuning, we let ** be the policy employed in the rounds To2k +1, 2/22 +2,.......... To2*+1 which is determined by the estimate f((T22)) calculated at the end of the ) round. To estimate the regret, we consider the decomposition
K-1 To24
K-1 Σ -(4"))((()))) = Σ To (J(T)) K= 162
Σ ( 1=++1
We leverage our bound (Ta) for off-line RL in Section 3.1.2 to control the value sub-optimality J(T') J(f*), Recall that the policy ** is derived from i..d. trajectories collected from the rounds To 2----11--- + 1, To 2 + 2 To 2* We divide those To 2k-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 general. It follows from inequality (Tab that the bound
dvd H
J(T²' - J( S c
log(dHK/8)
To 2*
holds uniformly for indices k: 0,1,..., K 1 with a probability exceeding 1 8. Putting together the pieces, we arrive at
Regret(T) To H + H K log(dHK/8).
We then derive the regret bound in Corollary by noticing that K Ollog T).
C.2 Comparing to known off-line bounds
2 in Section 3.1.2 based on the results of Zanette et al. [37]; it gives the conventional 1/vni slow rate to which we compare. Zanette et al. (37) proved upper bounds on a pessimistic actor-critic scheme based on d-dimensional lincar function approximation. Using our notation, Theorem in their paper [37 can be expressed as
In this section, derive the sample complexity rizan (e) x L
H-1 Σ
dH
- - s c
Φn T (En, + 1, कn
(25)
n
A=1
where the vector कn is given by क == E, [Ø(S An)]. the covariance matrix
EnD: |Da]
Σ
(sn as, (ss.. On, on.e)"
We now consider the explicit dependence of this upper bound on dimension d, horizon H and sample size n. The divergence term の, T (Én, + A₂ o, measures the conditioning of the regularized covariance matrix (Eh, + \) along specific direction of Th. When the feature mapping & operates within a d-dimensional space, it is reasonable to assume that
1 T + 2x Tn d.
The bound (25) then reduces to J( J( S cdH2/ /v. 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 factor of VH. Under these conditions, the bound takes the form J(T') ( < ed H3/n.. edvH33/
18

---

D Details of the mountain car experiment
In this experiment, a car is situated in a valley between two hills. The car's objective to overcome the gravitational pull and reach the top of the right hill by efficiently controlling its acceleration.
D.1 Structure of the Markov decision process
The Markov decision process underlying the mountain car problem has state space S C R and an action space C The state (p. r) consists of the current position p and velocity v, whereas the scalar action f corresponds to the applied input force. The state variables (p, v) and action are restricted as
p E Punins Pinax] = 1.2112200 0.6],
E [Umins Umax 0.07, 0.07]
and
E [uins fmaxl 1, 1].
The mountain is described by the function
0.025
m (p) 3 sin(3p) +
(Pmax pp - Puuin)
over the interval p E [Pmia Pmax]
Let m be the derivative of the mountain shape function m, which represents the instantancous slope, and let (a,, op) (0.01, 0.0025) be pair standard deviations that dictate the amount of randomness in the updates. For an interval (a, b), define the truncation function
u
if u E [a, b].
V [o (u)
if > b, b
if <
With this notation, at each discrete time step = 0, 0,,..,.... the position and velocity of the car evolve as
Uk+1 Vaain [maxx] Up + 0.0015 fn 0.0025 (pp)) a 7,
Ph+1 Pani Pmax]] Ph + 04+1 + 7p7%)
where (Z,, ()) 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 Pgoal = 0.45. The reward at sate-action pair (s, a) is given by
r(s, a) f 100 max (0, p - Proat 31²
For any policy n, we define the y-discounted value function
((T) Ex
>" rrSn An)
using 7 = 0.97. The initial state sp = (po, vo) is generated with following a uniform distribution over the interval [-0.6, -0.4], and we initialize with velocity vo
D.2 Fitted Q-iteration (FQI) with linear function approximation
Here describe the of fitted Q-iteration (FQI) with linear function approximation estimate the optimal Q-function, along with the corresponding greedy policy म.
Linear function approximation We approximate the the optimal Q-function (s, a) + Q* a) using a d-dimensional linear function class with d 3000 features. We begin by defining the base
19

---

feature maps 6,
Punin Pmax | + R for position, and Φ, [Umin Umax + R 15 for velocity, with
components given by
@p.2)+1(p) cos(ip). for j = 0, 1, 24, and
(p) sin(jp), for j 1, ... 25;
(0.25+1(0) = cos()u), for j = 0, 1, ..... ..., 7, and (v)2)()) = sin(jv), for j 1, ..... 7.
To represent the action f. we define the base action feature map
= (L..P.
The overall feature map Φ S x A + R 3000 constructed by taking the outer product of the three base feature maps &p. Φ.. and Φ, follows:
Φ(s, a) o6 ev(v) @ o,(1)) 3000
(26)
Taking all possible triples of the three base features in the outer product leads to the overall di- mension = 3000 50 15 x 4. Given a weight vector w E R3000, we define the function (s, a) (w, ((s, a)), and we approximate the optimal Q-function using the function class F : f w E R 33000.
Fitted Q-iteration (FQI) We employed fitted Q-iteration with the linear feature Φ S Ax--RRM 3000 to estimate an optimal policy न. The FQI process begins by initializing the weight vector as wn E 3000 In each iteration, we first use the dataset D = {ss, Os Ta, s)) C construct the pseudo-responses
y/ = ri + Y max (w;, (1 a))
for 1,..., n4,
(27)
GEA
corresponding a stochastic estimate of the Bellman update applied our current Q-function estimate Jw. The polynomial form of the force feature Φ, allows for a closed-form solution to the maximum operation required in equation (27). Given these pseudo-responses, we then update the weight vector - W2++1 via the ridge regression
1++1 arg
min WE WE R800
Σ (vr (w, Ø(s ((s;, Am1le0183.
(28)
where Xn 0.01 in all experiments reported here.
We terminate the procedure after most 500 iterations, or when there have been 5 consecutive iterations with insignificant improvements in weights, where insignificant means that || w.ll2 / 3000 < 0.005. Letting @ represent the weight vector obtained from this procedure, the resulting policy given by selecting the greedy action based on the Q-function estimate f(s a) = (w, Φ(8,a))
D.3
Experimental configurations
Our experiments were based on an off-line dataset consisting of i..d. tuples
D = { (8i, az 4)) C x Ax
where the state-action pairs {8; a;) = (pi, Vz, fi)) were generated from a uniform distribution
over the cube [pmin Pmaa]] X [Uminn Umax] x [fmin fmax]. We performed independent experiments with the sample size varying over the range
n E { 1: = 10.5, 10.75, 11...., 13}
= (36315, 46630, 59874, 76879, 98715, 126753, 162754, 208981, 268337, 344551, 442413)
In each experiment, we generated a dataset D, estimated an optimal policy के based on the data, and evaluated the return ( For each sample size, conducted 80 independent trials.
20

---

In order to evaluate the return J. for each initial position -0.5 + 0.2, with j = -500, -99, -98, ... 499, we simulated 30 independent 1000-step trajectories by executing the estimated policy म. The average return over the 30 x 1000 trajectories is used as the estimate of J(T).
In order to approximate the policy n that represents "ground truth", we conducted a single experi- ment with sample size 6.4 x 10 obtain n². We simulated 1000 trajectories for each initial position Po and caleulated the average return, which serves the reference value [xx)). The value sub-optimality is then computed as the difference J(x²) J(A).
E
Verification of auxiliary claims
In this appendix, we collect the verification of various auxiliary claims made in the main text.
E.1 Properties of occupation measures
In this appendix, we prove a useful inequality
PP fll,, S ||
(29)
which holds for the state-action occupation measures in Appendix [B.2
This bound is used in the proof of bound (20
By definition, we have
|| of E. ((P))) An)] Ex [f (Sa+1))
Sh, An]
According to the property of variance, we can deduce
E
Ex.
Sh An]*] & Emp ((SutIs Thet (Sh+1)) = Il
As consequence, we find that [|,] f ||I S || Applying this inequality recursively leads to the conclusion that for any indices < h h' H, we have
| / 1l, P2 Ph+1. f Il, S
[KtiN Allm+1 S 1| Illms .... (I. ||
This establishes the bound
29
E,2 Proof of the telescope inequality
For completeness of this paper let us prove the telescope relation (6) stated in Section 2.3 For any policy ( TH) and sequence of functions (f1...., fn) with fu TH. we have the "telescope" relation
&
H
(s) = fi(8,
-
Σ
Em (T. fn+1 (S Av)) = for any state E S. (30)
Here the value function V is given by (s)(s) = QT (s, (s)). Taking f f in equation (30 yields
H Σ
(s) f(s, +
En
(Th Frtt (sh. =s].
(31a)
A=
Letting म = मे equation
3la yields
# -(s Σ
E - (hh, || =
(31b)
"I general, it is not guaranteed that n² equal the optimal policy n", due approximation enror 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.
21

---

Since गे is a greedy policy with respect to function f, we have
(s)) (s, (s)), and fh+1 Ty futz 2 Th fh+1
for any policy æ.
Using this fact and subtracting equations 3la and 31b). we obtain
VT(()-
Σ
(T) JA+I [S An) 81 = =s]
Finally, taking the expectation over the initial distribution yields the claimed inequality
22

---

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]
The paper thoroughly discusses each point made in the abstract, including fast-rate convergence of RL in continuous state-action spaces, key stability properties, and the pessimism and optimism principles.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section discusses the work's limitations and future directions, such as adapting the framework to linear quadratic control, extending beyond i.i.d. data and finite- dimensional linear function spaces, proving lower bound demonstrate sharpness, and examining model mis-specification.
Guidelines:
The answer NA means that the paper has 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 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 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 low or 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.
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 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
23

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The theoretical results in this paper mathematically rigorous, with intuitions in the main body and detailed justifications and proofs 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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if 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.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Appendix D explains how to reproduce the synthetic Mountain Car experi- ment from Section I.I including MDP structure, linear function space construction, FQI implementation, and experimental setups. No data is required.
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 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 make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS 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 a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- 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 describe the partieular way they provide for reproducibiliity In the case of closed-source models, it 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 the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The submission provides supplementary code document to reproduce the Mountain Car experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
publlc//guidee/fodeetummsssss son for more details.
While we encourage the release of code and data, we understand that this might 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 reproduce the results. See the NeurlPS code and data submission guidelines (https
ctspss.c/publii//uuii httaa//gguuieee//oteuubmiiisss
for more details.
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.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they 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 possible in supplemental material (appended the paper) is 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 to understand the results?
Answer: [Yes]
Justification: Appendix D exxlains how to reproduce the synthetic Mountain Car experi- ment from Section I.I including MDP structure, linear function space construction, FQI implementation, and experimental setups.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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: [Yes]
Justification: Figure bb) in the paper includes error bars for the standard errors, and the estimated slope in Figure ([bb uses a bootstrap confidence interval to confirm observation validity.
Guidelines:
25

---

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, 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section I. details the computer setup: "The experiment ran for days two laptops, each equipped with an Apple M2 Pro CPU and 16 GB RAM."
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Yes, the research the paper fully conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
26

---

The paper focuses on purely theoretical aspects of reinforcement learning and does not discuss direct societal impacts, given its theoretical nature.
Justification:
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), faimesss 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 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 unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
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 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 require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
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 used and, possible, include URL.
27

---

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 palaaets.ppperssttt paperssi thcode. com con/datases package should be provided. For popular datasets,
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 to 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 paper does not involve crowdsourcing nor research with human subjects.
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 NeurlPS 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 nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
28

---

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


Reviews:
[{"review_id": "GjgrVVanv8", "reviewer": "Reviewer_gsVp", "summary": "This paper demonstrates how sample complexity can be improved under some conditions in offline and online RL.\n\nIt considers an episodic MDP framework with episodes of length H.\n\nOne 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.\nAs 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).\n\nFor 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.\n\nThese 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.\n\nAn illustration of fast rate RL achieved in practice is shown on the famous Mountain Car problem.", "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:\n\nLale, 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.\n\nAgarwal, N., Hazan, E., & Singh, K. (2019). Logarithmic regret for online control. \nAdvances in Neural Information Processing Systems, 32.\n\n- Are the required theoretical assumptions valid in the Mountain Car environment? \n\n- Typos: \n\nline 369 \"In the initial T0f episodes\" => \"In the initial T0 episodes\"\n\nline 854 \"was previously defined (??)\"", "limitations": "The limitations of the results are well addressed in the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written, with a high level of technicality.\n\n- The results obtained are interesting because they may help shedding light on properties that make RL \"easy\", and how algorithms could potentially maximize their effectiveness on such easy cases. This is very important because a lot of continuous RL problems are hard mostly because of their high-dimensional and non-linear nature, but the \"absorbing regions\" of these problems (to re-employ a term used in the paper) often have good smoothness properties and can be categorized as \"easy\".\n\n- The developments of the paper are well motivated, and there are many discussions trying to make a link between the results and simpler intuitions.\n\n- Although the detailed analyses are based on assumptions of linear function approximation, the framework proposed in the paper is general, and could be applied to more complex contexts.", "weaknesses": "- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our paper. We are grateful for your recognition of our theory as both well-motivated and general. Below, we will address each of the points you’ve raised.\n\n$Weakness$\n\nThat is a good point; we will be more cautious about the rigor of the discussions.\n\n$Question$\n- \"Could some of the results or new results (maybe in a non-episodic framework) be obtained as direct consequences of the result in [\"LogarithmicRegret Algorithms for Online Convex Optimization\", Hazan et al.]? ... In a similar direction, analyzing the relationships between the proposed approach and thefollowing papers would be interesting: Lale, S. et. al. (NeurIPS 2020), Agarwal, N. et. al. (NeurIPS 2019)\"\n\nRE: Thank you for bringing these pieces of literature to our attention.\n\n[Connection of our results to strong convexity]\n\nYou are correct; the fast-rate convergence discussed in our paper has strong connections with fast rates in stochastic optimization and (partially observable) linear dynamical systems, as we partially introduced in Section 1.3. Our theory indicates that the fast rate for continuous RL results from the geometry of the function class, sharing the same spirit as Hazan et al. (2007), Lale et al. (NeurIPS 2020), and Agarwal et al. (NeurIPS 2019), although the “strong convexity” may pertain to different components in different models. We will provide a more thorough discussion on these connections in the revision.\n\nTo clarify the connection further, in our paper, we used the linear function approximation example to show that the two stability conditions in the main theorem result from local curvature/strong convexity. In Sections 3.1 and 3.2, where we discuss how curvature implies fast rates, we mentioned in line 253 that “these two (curvature) inequalities arise naturally from a sensitivity analysis of maximizing a linear objective function over a constraint set defined by the feature mapping.” Our understanding is that this sensitivity analysis is closely related to the principles behind Hazan et al. (2007), Lale et al. (NeurIPS 2020), and Agarwal et al. (NeurIPS 2019). Further exploration of these connections is needed.\n\n\n[Generalization to policy-based methods]\n\nThank you for the great suggestion. It is indeed interesting and stimulating to consider whether the framework can be extended to policy-based or actor-critic methods, such as REINFORCE. By parameterizing the policy class, it is possible that some geometric structures in the parameter space could guarantee super efficiency. For those policy optimization settings, the occupation measure stability condition in our paper—interpreted as the stability of the system under policy perturbation—may still be useful and essential.\n\n- Validation of our theory in the Mountain Car environment.\n\nRE: Thank you for your advice. It will help complete our discussion. We plan to include the following paragraph in the revised version:\n\nIn the numerical example of the mountain car problem, we employed linear features defined by trigonometric and polynomial functions. This choice resulted in the feature set $ \\Phi(s) = ${$\\boldsymbol{\\phi}(s,a) \\mid a \\in \\mathcal{A}$} forming a one-dimensional smooth manifold within the $\\mathbb{R}^{3000}$ space. The manifold has positive curvature around the point $\\boldsymbol{\\phi}(s, \\pi^{\\star}(s))$, thereby validating our arguments (Curv 1) and (Curv 2).\n\n- Typos: Thanks for catching those typos. We will revise them accordingly.", "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": "ldCcZycEmm", "reviewer": "Reviewer_PVTM", "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.", "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": "The authors adequately address the limitations of their work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper starts with a very illustrative motivating example that empirically demonstrates the fast $O(n^{-1})$ convergence rate of FQI not explained by the known upper bound of $O(n^{-\\frac{1}{2}})$. They go on to introduce two \"stability\" assumptions about MDPs under which they show that this faster convergence rate is to be expected, and even extend this result to the online setting demonstrating that the previous upper bound on the regret of $O(\\sqrt T)$ can be improved to $O(\\log T)$ under the same stability assumptions. This is a strong result that will be of interest to the community. To the best of my knowledge, the ideas presented in this paper are novel.", "weaknesses": "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.\n2. 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. \n3. (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.\n4. (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}$.\n5. (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]$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the value of our research! Below, we will address each of the points you’ve raised.\n\n- $Weakness 1$\n\nRE: Thank you for your valuable feedback. We will work on shortening Section 3 and adding more discussions of stability conditions and toy examples to make the intuitions more explicit.\n\nRegarding the intuitions behind the two assumptions:\n\n-- Bellman stability: This can be interpreted as the propagation of estimation errors across backward iterations in dynamic programming.\n\n-- Occupation measure stability: This relates to the forward evolution of divergences in occupancy measures after perturbations on policy.\n\nThese assumptions are relatively natural in many practical cases: Bellman stability ensures the validity of value function estimation, while occupation measure stability characterizes the sensitivity of the system to policy changes.\n\nRegarding the curvature conditions, we plan to move the geometric illustration from Appendix G to the main body to help readers understand better.\n\n- $Weakness 2$\n\nRE: Thank you for raising this point. We will be more cautious about the use of the term “stability”.  In general, the conditions in our paper are Lipschitz continuous conditions, capturing smoothness of the changes. We chose to use the term “stability” because these conditions both characterize properties regarding system evolution, similar to what “stability” conventionally means in control theory. We will make it clear from the beginning that this does not carry the same meaning as in control theory.\n\n- $Weakness 3$\n\nRE: Thanks for your suggestions on the theorem statement. We will adjust accordingly.\n\n- $Weakness 4$\n\nRE: Thank you for your comment. We will rescale the axes properly.\n\n- $Weakness 5$\n\nRE: Yes, for discrete state-action spaces with countable elements, we can write $\\mu_h^{\\star}(s, a) = \\mathbb{P}_{\\xi_1, \\pi^{\\star}}[S_h = s, A_h = a]$. However, since we are considering RL on continuous spaces, we adopted the notations in the paper to maintain the generality of the definition. We will add a footnote in the revision to clarify this.\n\n- $Question$\n\nRE: That is a great point. It is always desirable to see how theory can develop into efficient new algorithms, and this will definitely be our next step. Regarding the efficacy of FQI, we believe the rate in terms of $n$ or $T$ should be optimal. However, there is still plenty of room to consider other factors. For instance, our theory might help devise new strategies for tackling distributional shift in offline data or improving exploration in online RL. These new methods could significantly reduce the covariate shift or dimensionality issues that also appear in the value sub-optimality upper bound.", "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": "fJcAEwAhaV", "reviewer": "Reviewer_bfUp", "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.", "questions": "None", "limitations": "The authors have discusses limitations of their work in Section 4.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The authors present a new framework for analyzing RL convergence properties. The authors propose two new stability notions that will help them derive improved convergence rates: a. propogation of estimation errors across iterations b. change of occupancy measure w.r.t policy  \n\n2. The paper uses the above two notions (which are relatively mild) to derive bounds in the standard tabular setting that decay as 1/n for offline and log T in the online setting, which is in contrast to previous bounds of 1/n^2 or \\sqrt(T) respectively. This takes a step towards partly explaining the fast convergence of RL algorithms observed in practice, atleast in the environments where the stability properties hold.\n\n3.  The intuition for the proof of fast rates in section 2.3 greatly helps in clarifying the approach towards deriving these rates. Authors extend the analysis to the setting of linear function approximation.\n\n4. The bounds lead to interesting insights on covariate shifts and are justified as purely being a computing the loss under a different distribution of data.\n\n5. Finally, the authors demonstrate an important benefit of their framework - their bounds do not require any kind of pessimism and yet are able to derive fast bounds. It is discussed under what conditions ignoring pessimism or optimism can still give better bounds.", "weaknesses": "1. Validating the theory with some MDPs, even toy domains can greatly help in increasing the quality of paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback on our work. We really appreciate it!\n\n- $Weakness$\n\nRE: Thank you for your helpful suggestion. We will add toy examples and include more discussions to improve the clarity of the paper.", "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: 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.
Decision: Accept (poster)