Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient
Authors: Ming Yin
Mengdi Wang
Yu-Xiang Wang
Venue: ICLR 2023 poster (2023)
Keywords: Reinforcement Learning Theory

Abstract: Offline reinforcement learning, which aims at optimizing sequential decision-making strategies with historical data, has been extensively applied in real-life applications. State-Of-The-Art algorithms usually leverage powerful function approximators (e.g. neural networks) to alleviate the sample complexity hurdle for better empirical performances. Despite the successes, a more systematic under- standing of the statistical complexity for function approximation remains lacking. Towards bridging the gap, we take a step by considering offline reinforcement learning with differentiable function class approximation (DFA). This function class naturally incorporates a wide range of models with nonlinear/nonconvex structures. We show offline RL with differentiable function approximation is provably efficient by analyzing the pessimistic fitted Q-learning (PFQL) algorithm, and our results provide the theoretical basis for understanding a variety of practical heuristics that rely on Fitted Q-Iteration style design. In addition, we further im- prove our guarantee with a tighter instance-dependent characterization. We hope our work could draw interest in studying reinforcement learning with differentiable function approximation beyond the scope of current research.


Published as a conference paper at ICLR 2023
OFFLINE REINFORCEMENT LEARNING WITH DIFFER- ENTIABLE FUNCTION APPROXIMATION IS PROVABLY
EFFICIENT
Ming Yin", Mengdi Wang', Yu-Xiang Wang"
"Department of Computer Science
'Department of Electrical and Computer Engineering Princeton University
University of California, Santa Barbara (ming_yin, yux suxiangw] @cs. ucsb edu
mengdiw@princet.om
ABSTRACT
Offline reinforcement learning. which aims at optimizing sequential decision- making strategies with historical data, has been extensively applied in real-life applications. Sfate-Of-The-Ar algorithms usually leverage powerful function ap- proximators (e.g. neural networks) to alleviate the sample complexity hurdle for better empirical performances. Despite the successes, more systematic under- standing of the statistical complexity for function approximation remains lacking. Towards bridging the gap, we take step by considering offline reinforcement learning with differentiable function class approximation (DFA). This function class naturally incorporates wide range of models with nonlinear/nonconvve. structures. We show offline RL with differentiable function approximation is prov- ably efficient by analyzing the pessimistic fitted Q-learning (PFQL) algorithm, and our results provide the theoretical basis for understanding variety of practical heuristics that rely on Fitted Q-Iteration style design. In addition, we further im- prove our guarantee with a tighter instance-dependent characterization. We hope our work could draw interest in studying reinforcement learning with differen- tiable function approximation beyond the scope of current research.
INTRODUCTION
Offline reinforcement learning (Lange al., 2012; Levine al., 2020) refers to the paradigm of learning policy in the sequential decision making problems, where only the logged data are avail- able and were collected from an unknown environment (Markov Decision Process / MDP). Inspired by the success of scalable supervised learning methods, modern reinforcement learning algorithms (e.g. Silver et al. (2017)) incorporate high-capacity function approximators to acquire generaliza- tion across large state-action spaces and have achieved excellent performances along wide range of domains. For instance, there are a huge body of deep RL-based algorithms that tackle challenging problems such the game of Go and chess (Silver al., 2017; Schrittwieser al., 2020), Robotics (Gu et al., 2017; Levine et al., 2018), energy control (Degrave et al., 2022) and Biology (Mahmud al., 2018: Popova et al., 2018). Nevertheless, practitioners also noticed that algorithms with gen- eral function approximators can be quite data inefficient, especially for deep neural networks where the models may require million of steps for tuning the large number of parameters they contain."
On the other hand, statistical analysis has been actively conducted to understand the sam- ple/statistical efficiency for reinforcement learning with function approximation, and fruitful results have been achieved under the respective model representations (Munos, 2003; Chen and Jiang, 2019; Yang and Wang, 2019; Du et al., 2019; Sun et al., 2019; Modi al., 2020; Jin al., 2020b; Ayoub et al., 2020; Zanette et al., 2020; Jin et al., 2021a; Du al., 2021; Jin et al., 2021b; Zhou et al., 2021a; Xie et al., 202 Min et al., 2021; Nguyen-Tang et al., 2022: Li et al., 2021; Zanette et al., 2021: Yin et al., 2022; Uehara et al., 2022: Cai al., 2022). However, most works consider lin- ear model approximators (e.g. linear (mixture) MDPs) or its variants. While the explicit linear
CCheck Arulkumaran et al. (2017) and the references therein for an overview.

---

Published as a conference paper at ICLR 2023
structures make the analysis trackable (linear problems easier to analyze), they unable to re- veal the sample/statistical complexity behaviors of practical algorithms that apply apply powerful function approximations (which might have complex structures).
In addition, there is an excellent line of works tackling provably efficient offline RL with general function approximation (e.g. (Chen and Jiang, 2019; Xie al., 2021a; Zhan al., 2022)). Due the generic function approximation class considered, those complexity bounds are usually expressed in the standard worst-case fashion O(V V + which lack the characterizations of individual instance behaviors. However, as mentioned in Zanette and Brunskill (2019), practical reinforcement learning algorithms often perform far better than what these gubble-inndependee bounds would suggest.
These observations motivate us to consider function approximation schemes that can help address the existing limitations. In particular, in this work consider offline reinforcement learning with differentiable function class approximations. Its definition is given in below.
Definition 1.1 (Parametric Differentiable Function Class). Let S, A be arbitrary state, action spaces and a feature map -(:,-): S x A + V C IR... The parameter space @ E RR Both & and y are compact spaces. Then the parametric finction class (for model f IRd IRm + IR.) is defined as
F = {f (). : x X A
that satisfies diffrrentibiilryymmootneer condition: 1. for any ó E IR",, f(0. 6) is third-time differ- entiable with respect to 2. f. a.f. Sg.5. G.e.of are jointly continuous for ().
Remark 1.2. Differentiable Function Class was recently proposed for studying Off-Policy Evalua- tion (OPE) Problem (Zhang et al., 2022a) and we adopt it here for the policy learning task. Note by the compaciness of O V and continuity, there exists constants Ce. By, Ki H2, Ny > that bounds: ||01|2 I Ce. (f Φ(8, a))l < By, V ((8,)())))))) S k1, 12.1[ 0o (( ((8,)))lls s K2, V [ ((ssa))]l S Ki for all E O, 8, E S A.2
Why consider differentiable function class (Definition 1.1)? There are two main reasons why differentiable function class is worth studying for reinforcement learning.
Due to the limitation of statistical tools, existing analysis in reinforcement learning usually favor basic settings such as tabular MDPs (where the state space and action space are finite (Azar et al., 2013; 2017; Sidford et al., 2018; 8; Jin et al., 2018; Cui and Yang, 2020; Agarwal et al., 2020; Yin et al., 202l;;b; Li et al., 2020; Ren et al., 2021; Xie et al., 2021b; Li et al., 2022: Zhang al. 2022b; Qiao et al., 2022; Cui and Du, 2022)) linear MDPs (Yang and Wang, 2020; Jin et al., 2020b; Wang et al., 2020; Jin et al., 2021b; Ding et al., 2021; Wang al., 2021a; Min al., 2021) linear Mixture MDPs (Modi et al., 2020; Cai et al., 2020; Zhang et al., 2021a; Zhou et al., 2021 (where the transition dynamic admits linear structures) so that well-established techniques (e.g. from linear regression) can be applied. In addition, subsequent extensions are often based on linear models (e.g. Linear Bellman Complete models (Zanette al., 2020) and Eluder dimension (Russo and Van Roy, 2013; Jin et al., 2021a)). Differentiable function class strictly generalizes over the previous popular choices, i.e. by choosing f00 x) = (0, Φ) or specifying & be one-hot representations, and is far more expressive as it encompasses nonlinear approximators.
Practically speaking, the flexibility of selecting model f provides the possibility for han- dling variety of tasks. For instance, when is specified be neural networks, 0 cor- responds to the weights of each network layers and df(,-) corresponds to the state-action representations (which induced by the network architecture). When facing with easier tasks, we can deploy simpler model ff such as polynomials. Yet, our statistical guarantee is not affected by the specific choices as we can plug the model f into Theorem 3.2 to obtain the respective bounds (we do not need separate analysis for different tasks).
1.1 RELATED WORKS
Reinforcement learning with function approximation. RL with function approximation has a long history that can date back to Bradtke and Barto (1996); Tsitsiklis and Van Roy (1996). Later,
'Heee Voo (0, a)s,a)))| is defined as the 2-norm for 3-d tensor and in the finite horizon setting simply instantiate By H.
2

---

Published as a conference paper at ICLR 2023
Algorithm
Assumption
Suboptimality Gap
v² k + vCet H + Her
VFQI., Theorem 3.1
Concentrahility 2.2
VC H
1 M².
PFQI., Theorem 3.2
Uniform Coverage 2.3
Ex-1 16dH Ex
S(22 ((sn. an) (oS( an))
VAFQL, Theorem 4.1
Unitorm Coverage 2.3 16d Σ Ex
1166 6(an, ab)) Voo((0 (0 (( an))
Suboptimality gaps for different algorithms with differentiable function class 1.1. Here we omit the higher order term for clear comparison. With Concentrability, we can only achieve the worst case bound that does not explicit depend on the function model f. With the stronger uniform coverage 2.3, better instance-dependent characterizations become available. Here Cott is in 2.2, 2 in 3.2, A in 4.1 and EF in 2.1.
Table 1:
draws significant interest for the finite sample analysis (Jin al., 2020b; Yang and Wang, 2019).
Since then, people put tremendous efforts towards generalizing over linear function approximations and examples include Linear Bellman complete models (Zanette et al., 2020), Eluder dimension (Russo and Van Roy, 2013; Jin et al., 2021a), linear deterministic Q* (Wen and Van Roy, 2013) or Bilinear class (Du al., 2021). While those extensions are valuable, the structure conditions assumed usually make the classes hard to track beyond the linear case. For example, the practical instances of Eluder Dimension are based on the linear-in-feature (or its transformation) represen- tations (Section 4.1 of Wen and Van Roy (2013)). As comparison, differentiable function class contains a range of functions that are widely used in practical algorithms (Riedmiller, 2005).
Offline RL with general function approximation (GFA). Another interesting thread of work con- sidered offline RL with general function approximation (Ernst et al., 2005; Chen and Jiang, 2019; Liu al., 2020; Xie al., 2021a) which only imposes realizability and completenes/omeennaablli assumptions. The major benefit is that the function hypothesis can be arbitrary with no structural assumptions and it has been shown that offline RL with GFA provably efficient. However, the generic form of functions in GFA makes it hard to go beyond worst-case analysis and obtain fine- grained instance-dependen learning bounds similar those under linear cases. On the contrary, our results with DFA can be more problem adaptive by leveraging gradients and higher order informa- tion. In addition the above, there are more connected works. Zhang al. (2022a) first considers the differentiable function approximation (DFA) for the off-policy evaluation (OPF) task and builds the asymptotic theory, Fan al. (2020) analyzes the deep Q-learning with the specific Rel.u activa- tions, and Kallus and Uehara (2020) considers semi-parametric/ nonparametric methods for offline RL (as opposed to our parametric DFA in 1.1). These are nice complementary studies to our work.
Our contribution. We provide the first Instance-dependent offline learning bound under non-linear function approximation. Informally, we show that (up to a lower order term) the natural complexity
measure is proportional to Σ Ber,nly go(s, T ga ga a)] where go(s, a) = ( Φ(s a)) is the gradient w.t.. the parameter 6* at feature & and Σ, = E. g($i,,, (1,x)g(SL... ar is the Fisher information matrix of the observed data at 0. This is achieved by analyzing the pessimistic fitted Q-learning (PFQL) algorithm (Theorem 3.2). In addition, we further analyze its variance- reweighting variant, which recovers the variance-deped deeendent structure and can yield faster sample convergence rate. Last but not least, existing offline RL studies with tabular models, linear models and GLM models can be directly indicated by the appropriate choice of model F.
2 PRELIMINARIES
Episodic Markov decision process. Let M PSr, di) to denote a finite-horizon Markov Decision Process (MDP), where S is the arbitrary state space and A is the arbitrary action space which can be infinite continuous. The transition kernel PA S x A A (AS represents distribution over states) maps each state action sh, as) to a probability distribution P-(-Is,, an) and PA, can be different for different h time-inhomogeneeue initial state distribution. Besides, r S x + R is the mean reward function satisfying 0 < r S 1. A policy (Z1y..., TH) assigns each state Sh. S probability distribution over actions by
H is the planning horizon and d1 is the
3

---

Published as a conference paper at ICLR 2023
mapping 84 > (n(-(s)) vh [H] and induces random trajectory $1, 01, P1,...... SH; aH, HH SH+1 with $1 ~ d1, an ~ T(-[sh), Sh+1 ~ Pr.-Ish, an), vh E [H]
Given a policy π, the V-value functions and state-action value function (Q-functions) (T(:..)
RSxA are defined as: (s) = E. (D relsa s), (ī(s, a) Bx
[2 Pr Sr as x
s,a], Vs, E S,A, [H]. The Bellman (optimality) equations follow Vh E |,],
(s,a(s as) + Is ViLi ()dP),
ra(s,a)) + (s) = max, a)(s,a). We define Bellman operator Ph. for any func- tion V. E RS as PA(V) = Th + Js VdPh. then (x(V = 0% and Pa(Vitt)) = Qi- Js
(s) (a- (o) a)], (s,
Ss Vitt (dP.
The performance measure is o = Es, [V]]] = En.h [ Lastly, the induced state- action marginal occupancy measure for any h [H] is defined to be: for any E C S x A, 4H = TE| (sh, an) E F|s1 ~ d1, as T-118),, ~ E B, = SSxA [(s o)d (s, (ssaa)ddaa addsda.
S S hj and
Offline Reinforcement Learning. The goal of Offline RL is to learn the policy x* = arg max, 2T using only the historical data D {(8,, ajs Th: sh+1)) [ej The data generating behavior policy is denoted as μ.. In the offline regime, we have neither the knowledge about μ nor the access to further exploration for a different policy. The agent asked to find a policy ग. such that V* - r" I for the given batch data D and specified accuracy > O.
2.1 ASSUMPTIONS
Function approximation in offline RL requires sufficient expressiveness of F. In fact, even under the realizability and concentrability conditions, sample efficient offline RL might not be achievable (Foster et al., 2021). Therefore, under the differentiable function setting (Definition 1.1), we make the following assumptions.
Assumption 2.1 (Realizability+Bellle Completeness). The differentiable function class F in Def- inilion 1.1 satisfies:
Realizubility: for optimal Qi there exists 0j E O such that Qh(:-)) [(0 (()) Vh;
* Bellmun Completeness: Let = (V(+) E R such that ||V S H}. Then in this case supveg inf PP(Vll S EF for some e 2 O.
Realizability and Bellman Completeness widely adopted in the offline RL analysis with general function approximations (Chen and Jiang, 2019; Xie et al., 2021a) and Assumption 2.1 states its dif- ferentiable function approximation version. There are other forms of completeness, e.g. optimistic closure defined in Wang et al. (2021b).
Data coverage assumption. Furthermore, in the offline regime, it is known that function approxi- mation cannot be sample efficient for learning e-optimal policy without data-coverage assumptions when e is small (i.e. high accuracy) (Wang et al., 2021a). In particular, we consider two types of coverage assumptions and provide guarantees for them separately.
Assumption 2.2 (Concentrability Coverage). For any fixed policy n, define the marginal state- action occupancy ratio as (s, a) ds, a) a, Then the concentrability coefficient is defined as Caf == sup, {M)
[| / 1 a2 where ( ()( and Cef < cc.
==
This is the standard coverage assumption that has has been widely assumed in (Ernst al., 2005; Szepesvári and Munos, 2005; Chen and Jiang, 2019; Xie and Jiang, 2020a), and 2.2 is fully charac- terized by the MDPs. In addition, we can make an alternative assumption 2.3 that depends on both the MDPs and the function approximation class F. It assumes a curvature condition for F.
Assumption 2.3 (Uniform Coverage). We have vh [H), there exists k 0.
Fy. [(f(), o(s +) f(22, ((-2))((--))1]11 2 ||0 02112. V0,,02 E θ (+)
E,,. [V ((. a)) Vf ((s, > RI, 40 E O. (**)
Generally speaking, 2.2 and 2.3 are not directly comparable. However, for the specific function class (0, Ø) with Ó 18, a) and tabular MDPs, it is easy to check 2.3 strong than 2.2.
4

---

Published as a conference paper at ICLR 2023
In the linear function approximation regime, Assumption 2.3 reduces to 2.4 since
and (+*) are identical assumptions. Concretely, if f(0.0) σ) = (8, 6). then En.,[[[(0,,,(( d(. f(02, +)=-=) (01- 02) (ot:))(())) 10, - 02) 2 1|0 - 02 vo, O2 @ + 2.4 + (x [V Φ(s, V.((0, ((,,)))))))))))))))))))))))))( a)) ]] > kT. Therefore, 2.3 can be considered as a natural extension of 2.4 for differentiable class. We do point that 2.3 can be violated for function class F that is "not identifiable" by the data distribution μ (i.e., there exists ((0)).(()) E F,0 # Og s.t. (0,,, ()--)) [(22, ((:;)))) +)))" = =0). Nevertheless, there are representative non-linear differentiable classes (e.g. generalized linear model (GLM)) satisfying 2.3.
Example 2.4 (Linear function coverage assumption (Wang et al., 2021a; Min et al., 2021; Yin et al., 2022; Xiong et al., 2022)). 2 == Ep [o(s, a) (), a) T] > nI Vh E [H] with some k > O.
Example 2.5 (offline generalized linear model (Li et al., 2017; Wang al., 2021b)), For known feature map o : S x A + Ba and link function f [-1, + [-1, 1] the class of GLM is FGLM == {(, a) + I((((s a), 0)) 0 E }} satisfying Ey,h [ø(s, (0),)))(ss)) a) > kI. Furthermore, f(() is either monotonically increasing or decreasing and 0 < K S (f)( S K < =0,, S M < co for all |2| S. 1 and some K, K, M. Then FGLM satisfies 2.3, see Appendix B.
3 DIFFERENTIABLE FUNCTION APPROXIMATION IS PROVABLY EFFICIENT
In this section, we present our solution for offline reinforcement learning with differentiable function approximation. As warm-up, we first analyze the vanilla fitted Q-learming (VFQL, Algorithm 2), which only requires the concentrability Assumption 2.2. The algorithm is presented in Appendix I. Theorem 3.1. Choose 0 < À 1/2C2 in Algorithm 2. Suppose Assumption 2.1. Then if with probability 1 --
K 2 max {512 (log( 2 dllo(1 + Aa
AA J.
6, the ousput क
X
of VFQL guarantees: -² s VCottl-- (V HH (
+ Hidez
+O(CCenl +HEF)
If the model capacity is insufficient, 3.1 will induce extra error due to the large EF. eF O, the parametric rate /K can be recovered and similar results are derived with general function approximation (GFA) (Chen and Jiang, 2019). However, using concentrability coefficient conceals the
structure and omits the specific information of differentiable functions in the complexity measure. Owing to this, we switch to the stronger "uniform" coverage 2.3 and analyze the pessimistic fitted Q-learning (PFQL,, Algorithm 1).
Motivation of PFQL. The PFQL algorithm mingles the two celebrated algorithmic choices: Fitted Q-tteratoon (FQI) and Pessimism. However, before going into the technical details, we provide some interesting insights that motivate our analysis.
First of all, the square error loss used in FQI (Gordon, 1999; Ernst et al., 2005) naturally couples with the diffcrentiable function class as the resulting optimization objective is more computation- ally tractable (since stochastic gradient descent (SGD) can be readily applied) comparing to other information-theorrtiial algorithms derived with general function approximation (e.g. the maxmin objective in Xie et al. (2021a), eqn (3.2)). In particular, FQI with differentiable function approx- imation resembles the theoretical prototype of neural FQI algorithm (Riedmiller, 2005) and DQN algorithm (Mnih al., 2015; Fan et al., 2020) when instantiating the model to be deep neural networks. Furthermore, plenty of practical algorithms leverage fitted-Q subroutines for updating the critic step (e.g, (Schulman al., 2017; Haarnoja et al., 2018)) with different differentiable function choices.
In addition, we also incorporate pessimism for the design. Indeed, one of the fundamental chal- lenges in offline RL comes from the distributional shift. When such a mismatch occurs, the esti- mated/optimized Q-function (using batch data D) may witness severe overestimation eтror due to the extrapolation of model f (Levine et al., 2020). Pessimism is the scheme to mitigate the error / overestimation bias via penalizing the Q-functions at state-action locations that have high uncer- tainties (as opposed to the optimism used in the online case), and has been widely adopted (e.g. (Buckman et al., 2020; Kidambi et al., 2020; Jin et al., 2021b)).
We mention Xic et al. (2021a) has a nice practical version PSPI, but the convergence is slower (the rate
On" } ))
5

---

Published as a conference paper at ICLR 2023
Algorithm 1 description. Inside the backward iteration of PFQL, Fitted Q-update is per- formed to optimize the parameter (Line 4). On is the root of the first-order stationar- ity equation Σ [[(0,ónk) - Th. ( Vo [(0, Dn,)) + A0 = 0 and En is the Gram matrix with respect to Voflo=ō,- Note for any S, E S x A, m(s, a) = (Voi(On, D(s, a)) En Von a))) measures the effective sample size that explored 8, and B/ / a) is the estimated uncertainty at (s, a). How- along the gradient direction Vefla-ā. ã,,
ever, the quantity m((s a) depends on Oz. and 0n needs to be close to the true 0% (i.e. Qn f s0h. +) needs to be close to QF) for the uncertainty estimation Is to be valid, since putting a random 0 into m(s, a) can cause an arbitrary r that is useless (or might even deteriorate the algorithm). Such an "implicit" constraint over 0 imposes the extra difficulty for the theoretical analysis due to that general differentiable functions encode nonlinear structures. Besides, the choice of / is set to be in I' is for theoretical reason only.
OdHH) in Theorem 3.2 and the extra term Ö K
Algorithm 1 Pessimistic Fitted Q-Learning (PFQL)
1: Input: Offline Dataset D { (s oh, rh. .1+) K,h=1 Require 3. Denote óh,6 == s(sh. ati).
2: Initialization: Set VH+1(.)
and À 0.
3: for h = H, H -,, .,.,.,, do
4: Set 0/ + arg miggon
Σ { (0, - Fhi - Bhen(sh+t))
+ +A +
5: Set En + Eim (of(On, x Vo (0hn xnxx) + Nos-
Set 1'n.t)) + 3 Vovo ((.))) )) Vol 01.))) (+0(z))
6:
7:
Set (x(:)) + f(On, o(: -) (s--)
8:
Set (..) )) + min (-))))), h 11+
9: Set #x (:1 s arg max (Qx(: .), (T 1-)) A pa()) + maxz, (x(1))))((.11)))
10:
end for
11:
Output: {
Model-Based vs. Model-Free. PFQL can be viewed as the strict generalization over the previous value iteration based algorithms, e.g. PEVI algorithm (Jin et al. (2021b), linear MDPs) and the VPVI algorithm (Yin and Wang (2021), tabular MDPs). On one hand, approximate value iteration (AVI) algorithms (Munos, 2005) are usually model-based algorithms (for instance the tabular algorithm VPVI uses empirical model P for planning). On the other hand, FQI has the form of batch Q- learning update (i.e. Q-learning is a special case with batch size equals to one), therefore is more of model-free flavor. Since FQI is concrete instantiation of the abstract AVI procedure (Munos, 2007), PFQL draws unified view of model-based and model-free learning.
Now we are ready to state our main result for PFQL and the full proof can be found in Ap- pendix D,E,F.
Theorem 3.2. Let B 8dHi and choose 0 < X S 1/2C2 in Algorithm 1. Suppose Assump- tion 2.1, with EF 0,5 Then if K 2 max 512 [log( 2ndd) + d dllo(1 Cu xz
)) 1A
X²
with probability - 5, for all policy π simultaneously, the output of PFQL. guarantees
[V (0n, f
Chot K
SdH Bx
(68,, an)) - Ō M(an, an)) (o 'o
where L is Polylog term and the expectation of π is taken over sh, an- In particular, if further K max (M, A 128k² log(2d/6) } we have x*
No
16dH E., [V V 0(8 /Vof( (oo an)) + Ō Chat
0 S Td
K
'Here we assume model capacity is sufficient to make the presentation concise. If > 0, the complexity hound will include the term ey. We include more discussion Appendix H.

---

Published as a conference paper at ICLR 2023
Here Σj, = =E Vof (s V. f(0%, ( aa,) + AIa and the definition of higher order parameter Chot. Coot can be found in List A. Corollary 3.3 (Offline Generalized Linear Models (GLM)). Consider the GLM function class de- fined in 2.5. Suppose B. X, K are defined the same as Theorem 3.2. cy = O. Then with probability 1 - 8, for all policy simultaneously, PFQL guarantees
8dH Bx
[VS((0,, ((sn,,,((s,,,)))) ? (sh, on D2) 6lsh, and
. O
Chot K
PFQL is provably efficient. Theorem 3.2 verifies PFQL is statistically efficient. In particular, by Lemma I..5 we have VVV I)],,, X
2s vxk resulting the main term to be bounded by 32dH1 VKK
that recovers the standard statistical learning convergence rate VK*
Comparing to Jin et al. (2021b). Theorem 3.2 strictly subsumes the linear MDP learning bound in Jin et al. (2021b). In fact, in the linear case Vaf(O, Φ) = Vo(0, 6) = Φ and 3.2 reduces to O(HH Σ h= E.r lV ((sh. an) (Elinear) 116( (l)))))))))
Instance-dependen learning. Previous studies for offline RL with general function approxima- tion (GFA) (Chen and Jiang, 2019; Xie and Jiang, 2020b) are more of worst-case flavors as they usually rely on the concentrability coefficient C. The resulting learning bounds expressed in the form O V ( that is unable depict the behavior of individual instances. In con- trast, the guarantee with differentiable function approximation is more adaptive due to the instance-
dependent structure Σ E.. VJ f(0 +) 'V,7 ( o) This Hisher-Informatinn style quantity characterizes the learning hardness of separate problems explicitly as for different MDP instances M1. M2, the coupled 07 07, 0h,M,, will generate different performances via the measure
E Ex [V V 5(0 6) (o.(0%.m..)) (i 1).). Standard worst-case bounds (e.g. from GFA approximation) cannot explicitly differentiate between problem instances.
Feature representation vs. Parameters. One interesting observation from Theorem 3.2 is that the learning complexity does not depend on the feature representation dimension m but only on parameter dimension d as long as function class F satisfies differentiability definition 1.1 (not even in the higher order term). This seems to suggest, when changing the model f with more complex representations, the learning hardness will not grow as long as the number of parameters need be learned does not increase. Note in the linear MDP analysis this phenomenon is not captured since the two dimensions are coupled (d m). Therefore, this heuristic might help people rethink about what is the more essential element (feature representation vs. parameter space) in the representation learning RL regime (e.g. low rank MDPs (Uehara al., 2022)). We leave the concrete understanding the connection between features and parameters as the future work.
Technical challenges with differentiable function approximation (DFA). Informally, key step for the analysis is to bound (f d) f(0,,)) Φ)1. This can be estimated by the first order approximation V/ //(0,,)) Φ)) (0,, 03). However, different from the least-square value iteration (LSVT) objective (Jin et al., 2020h; 2021b), the fitted Q-update (Line 4, Algorithm 1) longer admits a closed-form solution for t/. Instead, we can only leverage 8n is a stationary point of Zn (0) == k= I (0, @N.x) - TA, Vh+1 (sh+.)) (f(0, db,a) + X 0 (since Zn. (0r) 0). To measure the difference 8n - -8,, for any E θ, we do the Vector Taylor expansion Zy.(0) - Z (0h) = 2 (0- 0n,) (0) (where Rx (0) is the higher-order residuals) at the point 0/ with
K
3 00
7,, (0)
Σ
[s (h..k) anc Vn (ninlsh)1) VS(0, vn.2) + x..0)
8-
00
0-
(1)
(1(6n )o.e)) Phik
Vats (oh
Voos(On. Σ Vel(On on. 1(On (n.k) Mas
'Here n is the number of samples used in the infinite horizon discounted setting and is similar K in the episodic setting.
7

---

Published as a conference paper at ICLR 2023
The perturbation term Azg encodes one key challenge for solving 8,, -0, since it breaks the positive definiteness of Σj and, as a result, we cannot invert the Σx in the Taylor expansion of Zn. This is due to DFA (Definition 1.1) is rich class that incorporates nonlinear curvatures. In the linear function approximation regime, this hurdle will not show up since Vo = 0 and Ax; is always invertible as long as À 0. Moreover, for the off-policy evaluation (OPE) task, one can overcome this issue by expanding over the population counterpart of Zn at underlying true parameter of the given behavior target policy (Zhang et al., 2022a). However, for the policy learning task, we can- not use either population quantity or the true parameter 8% since we need a computable/data- based pessimism a to make the algorithm practical.
3.1 SKETCH OF THE PFQL ANALYSIS
Due to the space constraint, here we only overview the key components of the analysis. To begin with, by following the result of general MDP in Jin et al. (2021b), the suboptimality gap can be bounded by (Appendix D) Σ 2 [Ta ax]] if V - [(ūn, (s) a)l & ( a). To deal with Pa PA by Assumption 2.1 we can leverage the parameter Bellman operator T (Defini- tion 1. so that PA Vh+1 = -((0T (). Next, we apply the second-order approximation to obtain PA P - f(Oh. o) 2 V. Φ) (OTT. 0n) + (1 - 0n) T V2 f (0 -0)) Later, we use (I) to represent Zn (O2V..)))
2n (0)) = 23 (1 0n) + Rx (0:Vo))) = En (O 0n) + Rx (OrV,,))) ) by denoting Rx (0IVhr)) ) = A (On Oz + R (0((0114)))
Now that In, is invertible thus provides the estimation (note Zn (0n) 0)
PTV 0. E Zr (OTT
R (Q )
However, to handle the higher order terms, we need the explicit finite sample bound for 1077.4 0alla (or |10]- 0x In the OPE literature, Zhang et al. (2022a) uses asymptotic theory (Prohorovs Theorem) to show the existence of ((5) such that |10, - 0 S B()) for finite sumplehon--asyppooie guarantees since the abstraction of B(5) might prevent the result
vK However, this is insufficient
from being sample efficient. For example, if (6) has the form e" log( ())()), then c" log(+) is an inefficient bound since K needs to be e" /²² large to guarantee e accuracy.
vK
To address this, we use novel reduction general function approximation (GFA) learning proposed in Chen and Jiang (2019). We first bound the loss objective E,,(e, (o.) E,, (O+V.,;))) via a "orthogonal" decomposition and by solving a quadratic equation. The resulting bound can be directly used to further bound |1Qr,, Ō,lla for obtaining efficient guarantee Ō Vvk
dlf ). During the course,
the covering technique is applied to extend the finite function hypothesis to all the differentiable functions in 1.1. See Appendix and Appendix D,E,F for the complete proofs.
IMPROVED LEARNING VIA VARIANCE AWARENESS
In addition to knowing the provable efficiency for differentiable function approximation (DFA), it is of great interest to understand what is the statistical limit with DFA, equivalently, what is the "optimal" sample/statistical complexity can achieved in DFA (measured by minimaxity criteria)? Towards this goal, we further incorporate variance awareness to improve our learning guarantee. Variance awareness is first designed for linear Mixture MDPs (Talebi and Maillard, 2018; Zhou et al., 2021a) to achieve the near- merrmmii sample complexity and it uses estimated conditional variances Varp(lle.a) (Vi+1) to reweight each training sample in the LSVI objective.* Later, such a technique leveraged by Min et al. (2021); Yin et al. (2022) to obtained the instance-dependent results. In- tuitively, conditional variances ( a) == Varp(-Is.a) (V 1 serves the uncertainty measure of the sample (s, o, 8') that comes from the distribution P(-|s, a). If o² (s(s a) is large, then the dis- tribution P(-18, a) has high variance and we should put less weights in a single sample (s, a, r, s')
LLe expanding over (0) := E.,.,/ [(f (0, ō(s, a)) -r VT VV f(0, ((s, a))], and the correspond- ing Agg in 0 Zz. (0) is zero by Bellman equation.
88
We mention Zhang al. (2021b) uses variance-aware confidence sets in a slightly different way.
8

---

Published as a conference paper at ICLR 2023
rather than weighting all the samples equally. In the differentiable function approximation regime, the update is modified to
El (0 thi Va+1( /o a + A |1013
On <- min sEe
with (; estimated by the offline data. Notably, empirical algorithms have also shown uncertainty reweighting can improve the performances for both online RL (Mai et al., 2022) and offline RL (Wu al., 2021). These motivates our variance-aware fitted Q-learning (VAFQL) algorithm
Theorem 4.1. Suppose Assumption 2.1,2.3 with EF 0. Let 3 =
Sdl and choose 0 < X S
1 1/2C3 in Algorithm 3. Then if K 2 Ko and vd 2 Ō()), with probability 6, for all policy π simultaneously, the output of VAFQL guarantees
o 8d B [V VV o(on,an)) Vof osn. Men.aa)) 1 + Ō(
Onot K
S
where is a Polylog term and the expectation of π is taken over S/s O/- In particular. we
have 0 S yx -² I 16d
Emm Bn
V VV 100 d(st. an) A Vof ((u,,a))
Ō Cret). Here AT E (of(Hh, ) V f0% 1 (hh, x + Ala and the of ());))))== max (1, Varp, (-+)((--))- The definition of Ko, Chot, Choer S can be found in List A.
In partieular, to bound the error for u/ 2/ and 0h need to define an operator J that is similar to the parameter Bellman operator D.I. The Full proof of Theorem 4.1 can be found in Appendix J. Comparing to Theorem 3.2, VAFQL enjoys net improvement of the horizon dependence since Vary(Vi)) S H². Moreover, VAFQL provides better instance- -etance-dependent characterizations as the main term is fully depicted by the system quantities except the feature dimension d. For instance, when the system is fully deterministic (transition P 's are deterministic), of ~ Varp, (:+ = 0 (if ignore the truncation) and A O. This yields faster convergence with rate O( ( ). Lastly, when reduced to linear MDPs, 4.1 recovers the results of Yin et al. (2022) except an extra /d.
On the statistical limits. To complement the study, we incorporate a minimax lower bound via re- duction to Zanette et al. (2021). The following theorem reveals we cannot improve over Theorem 4.1 by more than a factor of vd in the most general cases. The full discussion is in K.
Theorem 4.2 (Minimax lower bound). Specifying the model to have linear representation f (0, ø). There exist a pair of universal constants c, H and sample size K > c'd', one can always find a family of MDP instances such that for any Voll02. 1110 slth.nf)) (....f))-V.. Vo5(0% 100k, (or,(V/2110
O such that given dimension d, horizon
algorithm ā (where ATT" E EK
inf sup EM [V' - c* 2 evd. Σ E. [ -V MEM
(2)
5 CONCLUSION, LIMITATION AND FUTURE DIRECTIONS
In this work, we study offline RL with differentiable function approximation and show the sample efficient learning. We further improve the horizon dependence via variance aware variant. How- ever, the dependence of the parameter space still scales with d (whereas for the linear case it is vd), and this is due to applying covering argument for the rich class of differentiable functions. For large deep models, the parameter dimension huge, therefore it would be interesting know if certain algorithms can further improve the parameter dependence, or whether this d is essential
Also, how to relax uniform coverage 2.3 is unknown under the current analysis. In addition, under- standing the connections between the differentiable function approximation and overparameterized neural networks approximation Nguyen- Tang and Arora (2023); Xu and Liang (2022) is important. We leave these open problems as future work. Lastly, the differentiable function approximation setting provides a general framework that is not confined to offline RL. Understanding the sam- ple complexity behaviors of online reinforcement learning (Jin et al., 2020b; Wang et al., 2021b), reward-free learning (Jin et al., 2020a; Wang et al., 2020) and representation learning (Uchara et al., 2022) might provide new and unified views over the existing studies.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors would like thank anonymous reviewers for their helpful suggestions. Ming Yin would like to thank Chi Jin for the helpful suggestions regarding the assumption for differentiable function class and Andrea Zanette, Xuezhou Zhang for the friendly discussion. Mengdi Wang gratefully ac- knowledges funding from Office of Naval Research (ONR) N00014-21-1-22 1--1-8888 Air Force Office of Scientific Research (AFOSR) FA9550- 19-1 19-1-99-10000 1-0203, and NSF 19-589, CMMI- MMM1-1653435. Ming Yin and Yu- Yu-Xiang Wang are gratefully supported by National Science Foundation (NSF) Awards #2707117
and #2003257.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with gener- ative model minimax optimal. In Conference on Learning Theory, pages 67-83, 2020.
Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep rein- forcement learning: A brief survey. IEEE Signal Processing Magazine, 34(6):26-38, 2017.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pages 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91(3): 325-349, 2013.
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning-Vane -Volmee 70, pages 263-272. JMLR. org, 2017.
Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine learning, 22(1):33-57, 1996.
Jacob Buckman, Carles Gelada, and Mare G Bellemare. The importance of pessimism in fixed- dataset policy optimization. arXiv preprint arXiv:2009.0679) 2020.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration policy opti- mization. In International Conference on Machine Learning, pages 2283-1294 PMLR, 2020.
Qi Cai, Zhuoran Yang. and Zhaoran Wang. Reinforcement learning from partial observation: Linear function approximation with provable sample efficiency. In International Conference on Machine Learning, pages 2485-2522. PMLR, 2022.
Jinglin Chen and Nan Jiang. Information- -hhooretic considerations batch reinforcement learning.
In International Conference on Machine Learning, pages 1042-1051, 2019.
Qiwen Cui and Simon S Du. When is offline two-player zero-sum markov game solvable? arXiv preprint arXiv:2201.03522 2022.
Qiwen Cui and Lin F Yang. Is plug-in solver sample-efficient for feature-based reinforcement learn- ing? In Advances in neural information processing systems, 2020.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al. Mag- netic control of tokamak plasmas through deep reinforcement learning. Nature, 602(7897):414- 419, 2022.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic. Provably efficient safe exploration via primal-dual policy optimization. In International Conference on Artificial Intelligence and Statistics, pages 3304-3312, PMLR, 2021.
10

---

Published as a conference paper at ICLR 2023
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674. PMLR, 2019.
Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization rl. Inter- national Conference Machine Learning, 2021.
Damien Ernst, Piere Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning.
Journal of Machine Learning Research, 6:503-556, 2005.
Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q learning. In Learming for Dynamics and Control, pages 489- PMLR, 2020.
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline rein- forcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10919, 2021.
Geoffrey Gordon. Approximate solutions Markov decision processes. Carnegie Mellon Univer- sity, 1999.
Shixiang Gu, Ethan Holly. Timothy Lillicrap, and Sergey Levine. Deep reinforeement learning for robotic manipulation with asynchronous off-policy updates. In 20/7 IEEE international confer- ence on robotics and automation (ICRA), pages 3389-3396. IEEE, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning, pages 1861-1870. PMLR, 2018.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? In Advances Neural Information Processing Systems, pages 4863-4873, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870-4879.
PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theooyy pages 2137- 2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. arXiv preprint arXiv:2 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021b.
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evalu- ation in markov decision processes. J. Mach. Learn. Res., 21(167):1-63, 2020.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. Advances in Neural Information Processing Systems, 2020.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforce- ment learning, pages 45-73. Springer, 2012.
Sergey Levine, Peter Pastor, Alex Krizhevsky, Julian Ibarz, and Deirdre Quillen. Learning hand- eye coordination for robotic grasping with deep learning and large-scale data collection. The International journal of robotics research, 37(4-5):421 436, 2018.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives open problems. arXiv preprint arXiv:2005.01644; 2020.
Gen Li, Yuting Wei. Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. Advances in neural information processing systems, 33:7031-7044 2020.
11

---

Published as a conference paper at ICLR 2023
Gen Li, Yuxin Chen, Yuejie Chi, Yuantao Gu, and Yuting Wei. Sample-efficient reinforcement learn- ing is feasible for linearly realizable mdps with limited revisiting. Advances in Neural Information Processing Systems, 14.16671-16688 2021.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-base based offline reinforcement learning. arXiv preprint arXiv:2204.05275, 2022.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear con- textual bandits. In International Conference on Machine Learning, pages 2071 PMLR, 2017.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.06202, 2020.
Mufti Mahmud, Mobammed Shamim Kaiser, Amir Hussain, and Stefano Vassanelli. Applications of deep learning and reinforcement learning to biological data. IEEE transactions on neural networks and learning systems, 29(6))2063-2077 2018.
Vincent Mai, Kaustubh Mani. and Liam Paull. Sample efficient deep reinforcement learning via uncertainty estimation. International Conference on Learning Representations, 2022.
Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 8(7554):552955333 2015.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pages 560-567, 2003.
Rémi Munos. Error bounds for approximate value iteration. In Proceedings of the National Confer- Artificial Intelligence, volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
Rémi Munos. Performance bounds in 1 p-norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-561, 2007.
Thanh Nguyen-Tann and Raman Arora. Provably efficient neural offline reinforcement learning via perturbed rewards. International Conference on Learning Representations, 2023.
Thanh Nguyen- Tang, Sunil Gupta, Hung Tran-The and Svetha Venkatesh. On snite-sample analysis of offline reinforcement learning with deep relu networks. Transactions on Machine Learning Research, 2022.
Mariya Popova, Olexandr Isayev, and Alexander Tropsha. Deep reinforcement learning for de novo drug design. Science advances, xe7as78778 2018.
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang, Sample-efficient reinforcement learning with loglog (t) switching cost. International Conference on Machine Learning, 2022.
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-frec offline reinforcement learning. Advances neural information processing systems, 2021.
Martin Riedmiller. Neural fitted q iteration-fiss experiences with a data efficient neural reinforce- ment learning method, In European conference machine learning, pages 317-328. Springer, 2005.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration, Advances in Neural Information Processing Systems, 26, 2013.
12

---

Published as a conference paper at ICLR 2023
Julian Schrittweser,, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):604-609 2020.
John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft q- learning. arXiv preprint arrXiv:/04.0000 2017.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, pages 1186-5196, 2018
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Mathhw Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-35,, 2017.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-208 2933.993. PMLR, 2019.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference Machine learning, pages 880-887, 2005.
Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-aware regret bounds for undis- counted reinforcement learning in mdps. In Algorithmic Learning Theory, pages 770-805, PMLR, 2018.
John Tsitsiklis and Benjamin Van Roy. Analysis of approximation. Advances in neural information processing systems, 9, 1996.
learning with function
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. In International Conference Learning Representations, 2022.
Ruosong Wang, Simon Du, Lin F Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 2020.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? International Conference Learning Representations, 2021a.
Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. International Conference on Learning Representations, 2021b.
Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deter- ministic systems. Advances Neural Information Processing Systems, 26, 2013.
Yue Wu, Shuangfei Zhai, Nitish Srivastava, Joshua Susskind, Jian Zhang, Ruslan Salakhutdinov, and Hanlin Goh. Uncertainty weighted actor-critic for offline reinforcement learning. International Conference on Machine Learning, 2021.
Tengyang Xie and Nan Jiang. Batch malue-function approximation with only realizability. arXiv preprint arXiv:2008. 049900, 2020a.
theoretical comparison. Uncertainty in Artificial Intelligence, pages 550-559, 2020b. Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: A
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficien offline and online reinforcement learning. Advances in neural information pro- cessing systems, 34:27395-27407, 2021b.
13

---

Published as a conference paper at ICLR 2023
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly mini- max optimal offline reinforcement learning with linear function approximation: Single-agens mdp and markov game. arXiv preprint arXiv:2205.155122 2022.
Tengyu Xu and Yingbin Liang. Provably efficient offline reinforcement learning with trajectory-wise reward. arXiv preprint (XXi:22006006226, 2022.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features.
In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pes- simism. Advances in neural information processing systems, 2021.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline pol-
icy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Stafistics, pages 1567-1575. PMLR, 2021a.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. Advances in Neural Information Processing Systems, 2021b.
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. Interna- fional Conference on Learning Representations, 2022.
Andrea Zanette and Emma Brunskill. Tighter
regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference on Machine Learning. pages 10978-10989. PMLR, 2020.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic meth- ods for offline reinforcement learning, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. arXiv preprint arXiv:2202.04 04634,, 2022.
Ruiqi Zhang, Xuezhou Zhang, Chengzhuo Ni, and Mengdi Wang. Off-policy fitted q-evaluation with differentiable function approximators: Z-estimation and inference theory. International Con- ference on Machine Leurning, 2022a.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-based reinforcement learn- ing with linear function approximation. Advances in Neural Information Processing Systems, 34: 1582 1593, 2021a.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances Neural Information Processing Systems, 34, 2021b.
Zihan Zhang, Xiangyang Ji, and Simon Du. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference Learning Theory, pages 3858-3900 PMLR, 2022b.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532 4576. PMLR, 2021a.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for dis- counted mdps with feature mapping. In International Conference on Machine Learning, pages 12793-12802. PMLR, 2021b.
14

---

Published as a conference paper at ICLR 2023
Appendix
A
NOTATION LIST
(0)
Bn, f(, ((s,)) Vf(0, o(s)))
ming,0 Ami (2%
(s,a)
max (1, Va (V) a)) for any V
8
Failure probability
Ku
51 max
x (Iog( 2nd + d dllog11 4x anj
(PA -
<
2 M(aay-P(laa)
(1,0))
Chot Chot
KiH VR
+
d d
+ HH
+ 62 max( M1
d'H Ag Ca + Hdnd
Cho
Chot
Chot 66 63/2
B FURTHER ILLUSTRATION THAT GENERALIZED LINEAR MODEL EXAMPLE SATISFIES 2.3
Recall the definition in 2.5, then:
For (**),
E (V5(0, V((0, Enn ((s .(.))))((.))))))))) o(-,-) Ey,n (o(+.) ((..) 131, V
For (+), by Taylor's Theorem,
Eych (S(0), o(. f(0,, Mi ,))²] = Ep,. [f' ob ()) 02)0(((())))))))))))))))1 (()))((())) T(a 022] T ))(;))))))) T(4 - 02]] x2 - 02) Bp.nlo((s)) [[(1 - -22) 2 n.3 1:1101 -02112
N E 1(1 02) o(-
and choose x²3 as i in 2.3.
C ON THE COMPUTATIONAL COMPLEXITY
For storage of Pessimistic Fitted Q-learning, at each time step [H] Algorithm 1, we need to store 6r, Σ, and (0,,,, xn,x)- Therefore, the total space complexity is O + H +KKK H). For computation, assuming 0 is solved via SGD and let M denote the number of gradient steps, then the complexity is dominated by computing 0,, 2), and 2 which results O(MH + KdHl d3 H) complexity (where H comes from h H..... 1).
The space complexity and computational complexity for VAFQL has the same order PFQL except that the constant factors are larger.
D SOME BASIC CONSTRUCTIONS
First of all, Recall in the first-order condition, we have
V,
f (0.k)) -h.kk Vn+ta (s A 11011
=0, vh [H].
15

---

Published as a conference paper at ICLR 2023
Therefore, if we define the quantity Zx(:,-) R as
K
(0VV Σ (0, (1,k) - rh - -
V (sh+z))
v0 W s HI
then we have (recall 0, E Enn((O))
Zn 10 =0
In addition, according to Bellman completeness Assumption 2.1, for any bounded V(.) IR with [[V]] S H. inf fer I[ʃ 1iff-Ppii PP((V) S cr. vh. (recall Pv((V) = rh + Is VdPa). Therefore, we can define the parameter Bellman operator T as follows.
Definition D.1 (parameter Bellman operator). By the Bellman completeness Assumption 2.1, I, for Ol I H. we can define the parameter Bellman operator T V - OTV E θ such that
foraaorrrrrna any
arg min [f 6) - (V)
aee
Denote dy f(rrv. 6) (V(V), then we have [[ -P = llóv S cF. In particular, by realizability Assumption 2.1 it holds OTV = 07 and this is due to [(DrVig):
cF.
Pa (A Vi f(0%,)) +)."
D.1
SUBOPTIMALITY DECOMPOSITION
Denote as) = PA (s a) (s, by Jin et al. (2021b) we have the following decompo- sition.
Lemma D.2 (Lemma 3.1 of Jin et al. (2021b)). Let ãे = [ policy and Qn be any estimates with VT (8, (, 8)), Then for any policy n, have
"1
0
Eslun(sn,a))) an)] +
Σ h=1
(sl
Er ( (sh, Ta (. 8n) Tn (:1 s1))aa
In particular, if we choose tn (-1s) == arg max, (s) T(- [s))s then
H
H
Exlun(shan)) +
Σ Esl
h=1
h=1
Lemma D.3. Let Ph be the general estimated Bellman operator. Suppose with probability
holds for all h 8, E [ x S A that [(P,, V P, (r S Ta(s, a), then implies
as h E S x A [.]. 0 (s) I (T)(s,)). Furthermore, it holds for any policy simultaneously, with probability
8,
H
(T(() - (
Σ 2 E. (s), = h=1
Proof of Lemma D.3. This is a generic result that holds true for the general MDPs and was first raised by Theorem 4.2 of Jin et al. (2021b). Later, it is summarized in Lemma C.1 of Yin et al. (2022).
With Lemma D.3, need to bound the term |PA (PaDhii(s,a) - Pa
Here without loss of generality assume Qi can be uniquely identified, i.c. there is a unique 0* such that f(0%, Φ) Qi.
16

---

Published as a conference paper at ICLR 2023
E ANALYZING |Pr (1, a) - PP h+ (s, a) FOR PFQL.
Throughout this section, suppose ey = 0. i.e. f(OTv, Φ) = (V).. According to the regression oracle (Line Algorithm 1), the estimated Bellman operator Pb, maps Vn+1 200 i.e. Pa. Vn+1 f(h,, 6). Therefore (recall Definition D.1)
P Phinii - o(s.)))
- (() - [Oh,, ((8,a))
(3)
=V ((s, a)) (TT - 0n) Hots,1.
where apply the first-order Taylor expansion for the differentiable function f point On and 1 is a higher-order term. Indeed, the following Lemma E.1 bounds the Hota,1 term with O(+))
Lemma E.1. Recall the definition (from the above decomposition) Hobs,1 = : ((s,))
1(0n, (s( ((s,a)) a)) (rrinss Bn): then with probability 1
18H 02 (log( H/6) + Ca.og x) + R2AC2
|Htt, <
Vh E [H].
kK
Proof of Lemma E.I. By second-order Taylor's Theorem, there exists a point & (lies in the line seg-
ment of 0 and D. such that
f(02D) (s, a))--a)-e f(0,, ((s, = VI a() (oro... - +
1 (0 (0ro441 2 - 0n) (oof(E (PrPnes -0n)
Therefore, by directly applying Theorem G.2, with probability 8, for all h E [H].
|ooh, (Orhhe -
-0.) 0.))
Vios(s, ((s,)))))) (Arah. 0n))
S 2zx2 || - 02l =x113= 12ogg2 + Ca.tog K) + x2dC2
kK
E.1 ANALYZING V f o(s, (oro,. -kh) VIA Zn-
From (3) and Lemma E, 1, the problem further reduces to bounding f ((s, (OTO..1 0n))
To begin with, we first provide characterization of OrV.., Or.- Indeed, by first-order Vector Taylor expansion (Lemma L.1), we have (note Zí, (0% V/+1) 0) for any 0 O
Z (0 Vn+1) - Zn Zn(0n, (0 Vh+1) = Σj 0%) + (0).
(4)
where (0) is the higher-order residuals and Dj = 39 (B n- with
Σj = 00
à
Σ
K
(0, (m.)) - -ha - Pan VS(0, dn. + +2.0)
0=0n
30
o=0x
(f(0n. (n,k) Th.k (i+t(sh+tt)
Voof(On. on.))
K
Vol (Oh, )n.)) (Oh, @n.k) + Ada
(5)
17

---

Published as a conference paper at ICLR 2023
here V V denotes outer product of gradients.
Note Ag; is not desirable since it could prevent 2; from being positive-definite (and could cause 2i to be singular). Therefore, we first deal with Asg in below.
Lemma E.2. With probability 6, for all h E [H)
K
[(0 )m.n) Th - Vht2(sh-1)) Vhof @n)
K
K
2
R1
(log((2// + dloo(1 + 2CeHigg) + Cd.log
<9R² max
K
K
Proof of Lemma E.2. Stepl:
We prove for fixed 0 E θ, with probability 1 1-6, 6, for all h E [M].
(1 dn.)) - Thit - (o(41))))) (ia.((,,cn) din)
61
(log((2HH/) Cd.log K)
-
9122 max
K
K
Indeed, we have
(Oh) rh,* Ph+1(sh+2)) Vool(0,oo)
2
s K
- - (2,f(0,
(6)
(f(Drean (n.)) (n, - -hh Poni(sh+z)) Viol(0,
On one hand, by Theorem G.2 with probability 1 - -5/2 for all h [H]
((0), - 5(02Dm pn.)) Vool(0, mn)l
162 max |V ((s ((s,))( 0,3,a
00
@1 112
K 1=1
(60//()) (
V + Calor x) 2XC2
ba.Ker
2HH
Oreazz// S 12k
RK
Ki
(7)
On other hand, recall the definition of T. have
E (f(O )b,n) Th, Vn+z(s Vool(0, )n
=E [1OT (h.kk) Th,k Vn sh at]
Viol(0, @))
(hat att -E [rr. Ph+i (sh+ sti, ahl)
dn.
((Ph (Phh att (Ph Ph+a (sh+2) () (5 at))
V2el vn.a) 0.
Also, since (S(OTVL)) ThA - (s(+ H² k2, then by Vector Hoeffding's inequality (Lemma L.2),
V dn)) || < H82, denote o=
K
P
(10-0.... rh.k Vi+z(shimi) (iaf(A,
2t/K {st d S de -118k//H
K
which is equivalent
k
8dH2 n22 log(d/8)
Σ
(100 21.6) Th. (itt(shim)) Vioo(0,
S
a
21-8
K
k=
2
18

---

Published as a conference paper at ICLR 2023
A = E (f(Dre.,, (n.x) - rh Vh+1(sh++)) of dn) 1/1
Define
SdH logla/61) ), then by law of total expectation P(A) [F[LA] = E. a|t a )
B[P[A| 5 0 ) E[1 - 6] =1-8,ie i.. with probability at least 1 6/2 (and union bound),
1
K
f(e [(0rvr.,:nnN) on.a) - rh (h+r(sh+i)) (inf @n)
8d112 log(2dd/)) wh E [H].
-
K
K
2
Using above and equation 6, equation and union bound, w.p. 1 1 5, for all h E [H]
(( - Th.2 Vhtz(6h+1))= Voof(0, 6n)
GRIK1
Cd.log
8d112 K3 log 2Hd/8)
K
kK
K
RI 1)
(log((22 + Ca.lor
91² max
K
Step2:
we finish the proof of the lemma.
Consider the function class (5()) = ΣK (f(hn
(nx) - rn. -rik - Po+i(shtt)) V8of(0.0n))110)) [E o).
then by triangular inequality
K
lf((,) - f(==)) =
K Σ
f(0r. )n.n) - - - P(+z(oh+1)) [Vin @n) Vonf on)]
<H sup 8,0
Vosl (01, 0b)) -00 (00,,,))l b2)1l2 S HKa ||ó 02
By Lemma L.8, the covering number C of the c-net of the above function class satisfies log < d doog(1 2CaHia) ). By choosing 6 = 1/K, by union bound over C cases we obtain for all h [
1
(1 (h. Th,k Vi+i(1i+1)) Veol sbn)
K
2
K1
(Hg((100(H11) + dloo(1 + HCg + Ca.log K)
<9ng max(
1)
+ K"
Vk"
K
Combing Lemma E.2 and Theorem G.2 (and a union bound), we directly have Corollary E.3. With probability 1- ò,
Ki2 max( 11, 1 )d H² K vx
K Am, (ōn - -
00 0rvn- 11 5 Ō
K
K
Here Ö absorbs all the constants and Polylog terms.
Now we select 0 fTū in equation 4, and denote Rx(OTV ArR (0n 8 Rg (0.o...), ), then equation is equivalent to
Zn (OrV._, ( - Zn (0m (n Ex (OTV... 0+)+ (0 En(OTiir) + (x((V
Note A > 0 implies Ei, is invertible, then we have (recall Zn (Op (0h+1) =)
OrV.z, - 0₂ =-, (/n (2-1) - Zn (. - Σn Rx (OrDres)
(Zu (0TT),,1 - EnH Rx (0T
[
19

---

Published as a conference paper at ICLR 2023
Plug it back to equation to get
VS(O,, (() (Irnnt - 0n)
=V ((s, 2/ [Z (OTDa, [B+1)] V ((s, Rx (x((rpn7))
K
-V 06
(10 0b.x) - rh. (h+z(shi+1)) V/ S(0TV, , (.hn) + 20TV.11
S (s, a) 2)
Rx (OTV..))
V ((.,
((0Thnrr:0n - Thik - Vhti(sh+z)) Vi 100 Sna))
(f ((
RI (0 + 1Q
Hotz
We will bound second term Hot, to have higher order 0 k in Section E.5 and focus on the first term. By direct decomposition,
vs 0(8, a)
(0 (O-Var - thik ((+1(1)+1)) Vo f(0 dn+)
((.
(f 0nk) Thin Vit1(sh+1)) V s(ōn, on,
km
x (100 )m.k) 1(Orv .n.x)
+ 6(3,),
Vatz(shin)) (iin( vo 1(On, on,,)]
1=1
K
Σ
(( Thit (ata(sh+t)) (Vo (b.)) Vi
E.2 BOUNDING THE TERM I3
We first bound the term Iz. We have the following Lemma.
Lemma E.4. For any fixed V()) E RS with ||V I and any fixed 0 such that ||ōTv - 0112 5
(log((H)))) +22A22
Let
kk
K
T. = VI(On, a)) --1
([(OTV,OnN)) - Th.t ((siin)) (Vol(Orv, pn.x) Vel (1,))))))))
and if K 2 max 512 kg RJ
llog( 2d) + dlog(1 + Ar, D
42
then with probability - 8,
Cs (14dd112 (og( +s x) #8811 1 log(d//)
(where maxx(11
(14Ad11'x3 (112 log (1/((11))))))))) Catoa k) 8d112 log()/)) 1
Tal S 4KlV
+ +
x3
K
K3/2
20

---

Published as a conference paper at ICLR 2023
Proof of Lemma E.4. Indeed, with probability 1 1 8/2.
[Tal =
V ((s,)) mn
(10vv, (n.)) - Thi -h,, (
- Vo5(0, 0b,))
K
V 1(0,
Σ
(f(Orv)0u.) -Paa (
(Ves(0tv (b.b))
1/
2kl $ (vRk +
Σ
on, - rin - -Val---) (Val( Vof(O, on.e))
11 where, under the condition K 2 max { 512 (ogg(() + dlog(1 + minxgok²)) )) plied Lemma L.5
}. we ap- x
Next, on one hand, Voo Φn,x) - Vef xl12
K2
110vv-011 - -012 5
360H (log( B//////////CCCC k)+2AC3, On the other hand,
N2)
kk
E [(f(Orv, (n.k) - -h,k ((th+2))= (Vo [ODVV, )n.n) - (T dn.k)) joh anl
=E [(f(Dvv 0h,kk) Th,* ((sh+1)) ssh a (V) flr. 01,x) - v f(0, x1,x)) ((PV) a - Vs )) (V, [(OTV, (b.)) V [(0 (0.)))))
Therefore by Vector Hoeffding's ' inequality (Lemma L.2) (also note the condition for boundedness (f . Th, (( (Vef xb,aa) (0, (x.))) S Hx2 110TT Ol12 s
(Hog) x 1+2AC2 with probability 1 8/2.
H
(100rv The v(sttt)) (Vof (a.x) (of(0,0ax))
K
2
4d
HKav
(Hg/)) x x122AC
log(g) (
K
(14ddH²23 (og + Ca.oo K) + +3
1
K
K
and this implies with probability 1- 55/2.
K
(S(OTV, (n.k)) - ThAA (( -Vo 01.)))
(14AdH1223 (112 (1)) + Ca.oo k) + 8dH12 log(d/0)
choose u IK (J(OTV, ΦR.x) Th,* V (Vof(Orv, - Vof (n.k) in
Lemma L.5, by a union bound we obtain with probability 1 -
[Ta| = V Vf(On, ((,00,00ss))) a)) T)) ET
(f(ezv, (n.k) - -hhk - (Vof(Otv. -o
2kL + )
Σ (5(TTV Thik - (
V*K
2xl
+ )
(1AAdH1N3 (H² log (og(H/8) +C k)
log + 0 (
<
2/
VKK
k²K
(144dH2 n3 (H² log (H/8) + Calog k) 5odrh + 0 1
=4k1
33
R3/2
21

---

Published as a conference paper at ICLR 2023
Lemma E.5. Under the same condition Lemma E.4. With probability 1 1
Mal S 4ma [14 (H² log (o)(H/6) Da,log K Ca.log k) + 8dH2 (3H Da, K )
+0
13 d log(1 6Ce (2n KK2) + dlog(1 6CoHk2R)
K K3/22
Here DaJosK
dooo (1 + 288ComL(MIVCC + 22IRK1))) + dl log (1 288 /dBmtk*) = O(d)) with O
absorbs Polylog terms.
Proof of Lemma E.5. Define
K
h(V,0,0) = Σ [((0,0n.) -hi - - (Vef(0, onx) Vef(0. )
then
[nVV, 0,,, - l1V2 02,
K
(If(0l. (2(5// [f - Ve(ohi+ll)) bnn) - )n.s))
[[(02,0n,)) ((
-h, - - va(oht+)) (IVos(0,, - - (n,,))))) sn.c)))
<K sup s,,s"
[1(0,, 0(, a)) - /(02, 0(s, a))] (Vi(s') ve(6')) 2n1
+KH sup
[os (88 a)) Vol(O), (8, a)) - [o/ o(8,a)) - Vol o(8
8.0
<K2N]
--
01 82
+ 2K ki
11 1/2l + HKK2 0 02 ||_ HKK2 10, - 02112
=(2ng + HR2) K
01 02
+ 2 K 1|V Vall
HKK2 1|0 82ll2.
2
Let C. be the defined in Lemma L.9 and C. be the 3HeaK covering net of (0: : ||0||2 < Ce). then by Lemma L.8 and Lemma L.9,
H covering net of (0 |00| Ce). Cv be the , covering net of V
c/3
log Call S d-- Hl-oo(1+ + 6C (2n + H ), log Col S dlog(1 + HCoHr2k
288CBnf Cg 2 22 + d² do log
288 288 / R2
log Cy I dlog 1+
1+
c²
e²
Further notice with probability 1- 1-5/2 Lemma L.5), for all fixed sets of parameters 0, V satisfies simultaneously.
0|12 S V ()0H x) x)+2Acg
||ōTv
xk
113 Tsl < V o(s. a)) 22,"
0rV, |((Vnzz. 1 0TV,,,, 0n.) h-V, 0rv, .0) EN
+ +0 x)) 2k
|/P(Pt1: Orr.n 0m) h(V,
M,V) 0TV. |)||_/
VkK
and 0 -
0%
3612 (log(2H0 10122/H///CCaaaaam Ca,lnn +22C with probability 1 1 8/2 Theorem G.2.
KK
Now, choosing O(1/K3) and by Lemma E.4 and union bound over covering instances, obtain with probability 1
(144dH²23 (H² log H/6) + Da.oo & + CaJoo + 8dH (O/FF Da K
1 Ra/2
[Tal S 4x1
+0
K
22

---

Published as a conference paper at ICLR 2023
E.3 BOUNDING THE SECOND TERM Ig
In this section, we bound the term
12 Vi ((, #=1
: - ( + Virn(thez)) vol s(ōn, sb,,)]
The following Lemma shows that 12 is higher-order error term with rate θ(
Lemma E.6 (Bounding 12). If K satisfies K 2 512
(log(( 3 + d'log1 + 2²
))) and
K 2 42/K, then with probability 1
112 Ō R9 d2
1
0
kK
K3/2
Here Ô absorbs constants and Polylog terms.
Proof of Lemma E.6. Step1. Define (V) f(0rv, )R,A) f(Orvi,,, .n.e) (( Vht1( (5%% and let () I Н be any fixed function such that supst In (V) -
Ök₁ H2, V (x))) Le. arbitrary fixed V function in the neighborhood (measured by m)) of Vit1- Then by definition T it holds E[m (V, (V,0)ss,, a
0. Let the fixed 0 E θ be arbitrary and define (0) (of ().))) Next, define (0) Σt Di=1 VI dis at)) (0(0,, @s* af)) + Ala.
since | ll2 < K1 and Imel < 0(k, 112 Kk ). by self-normalized Hoeffding's inequality (Lemma L.3), with probability 8 (recall === K in Lemma L.3),
K
d² kK
(X+ Kri
nR (0)m (V)
5K(K H2
dllg
A8
Gn(0)-1
Step2. Define A(V.0) = ER= In (V) and (V, = - IR (V) note by definition [nx(()) S 2H, which implies [lA(V,0)ll - Hk1 and
then
Gn(()-1"
mm (V1) nu (V2) s \PAV1 V/ + \|Vi 12ll.0 s 2 - -V2llo
and
-oVi,)))-((V2... 02)11, <K max (2H1 (0)) - Ix (02)) +vilno( - (m (V2)) <K(2HKg |0 02l12 + 2xz 1| -V2llooo)
Furthermore,
-Ga S G.(().) 11, (0,) G. (B2) 112 GI 1
sup
(7((1.))n,)) V 10 (S(22, xb) (/((02
X2
&
||| (VF(1,, 0m.k) (5 )), [f(0l, o1.)) + V5(022 (V (00))))n))
suu X2
k
2
Ne |10 02112= 2NinaK
X 10: 021l.
X2
All the above imply
(H(V, H2)2 VI
h(V,, &T 1VVV
Sv [I((V 0,) N(V,. B2)12 1 12KHA + /2KHH (G, (z)))) -11 112 2K Hm,
+ 2KHM A [IN(1, 01) - N(V2, 02)1l2
1 7 -2KH + + |2K
2x1KgKK
/2/
K(2HK2 10, - 02112 + 2x 11 - Velloo)
11 02ll2 2K HK)
X2
(/ (3 1 + W
1
V100 -0211 + +4V K3nGH A
82112
1 V2lloo
23

---

Published as a conference paper at ICLR 2023
Then e-covering net of (V be constructed by the union of covering 8Ce (4/ (4/K31Pminat + @8K3HRRRK2t
covering net of {0 )) and MA
net of V in Lemma L.9. The covering number No satisfies
log.N No Edlog
1+
e²
SCe(NIVCO + +2 x2)
8v
+dlog
1
+ d &ellog 1+
16(4/KSnf
16(4y
Step3. First note by definition in Step2
K
Σ (10 ona)) - f(0rvg (n.)) Pntz(sh+1)) + (iin())+1)) V Vi f0h,, 2m.kk)
H HV 0n)
and with probability 1-8
In (V++2) =If = 01,a)) f(OTVir, 0h,k) Vn+z(5h+1)) + V
SKI
Orh.. 0%
|n++ 1h+t1-W -1/41
36HH2(1og(HH))) + Ca.loo x) 22CB +C K1 H2
d2
d2
SK1
Ō
H2
sK
kK
kK
(9)
where the second inequality uses θrvi,, = aadd the third inequality uses Theorem G.2 and Theo- rem G.3. The last equal sign is due Cd.log S Ö(d)) (recall Lemma G.I).
Now choosing = O11/K) in Step2 and union bound over both equation and covering number in Step2, obtain with probability 1 d.
K
d RK
) d d Ō ( 1R
Ow)
Σ
SŌ H2
VRK
Gn(
(10)
where we absorb all the Polylog terms. Meanwhile, by Lemma L.5 with probability 1 --
v [ )rw)
2k1
+ +0
(11)
VKK
K
Finally, by equation 10 and equation 11 and union bound, we have with probability 6,
[12 = v (0,, a))2%
(500 dmnn) - 1(Orv;,; (o..) (n+i(Sh + viina(Hit))) v 10,, dn,))l
V V (2n))
Σ
(f(OTo )n.)) f(0rvi @n.k) Vnti(sh Vite(shh+1))
vJ f(0n,
[ )0.0) (o.a)
ببااا
H (V
2x1
+0(
5 Ki H2
Ō
Ō
Vkk
VKK
k.
K3/2
where the first inequality is CauchySehwarz inequality.
E.4 BOUNDING THE MAIN TERM I1
In this section, we bound the dominate term
K
h = Vf(ō,, ((., 2
(f(Prvz,, - Thik - Viin(shtti)
ViTh Φn.b)).
24

---

Published as a conference paper at ICLR 2023
First of all, by CauchySchwarz inequality, we have
| (T a))
Σ (0Oivitn:0a. nb Vitzlohttt) Vi f(On, @n.k)
1 (12)
Then we have the following Lemma to bound J. Lemma E.7. With probability 6,
|h 4Hd | | Ms, a))
((,
Co.log K + 0 K1
VKK
where 1o K only contains Polylog terms.
Proof of Lemma E.7. Stepl. Let the fixed 0 E O be arbitrary and define (0) = Vef(0, Φb,x). Next, define Gz denote 7//: == f 0n,k) rh.k Vht (1 then 1 at] and Ins H. Now by self-normalized Hoeffding's inequality (Lemma L.3), with probability 1 å (recall == K in Lemma L.3),
K (S(0, (s af)) (00 ( T + Ala: then || S Ki. Also
K
A + Km1
Σ
I& mp
2H
dlog
Ad
G.(())
Step2. Define h(0) := Σ 1=1 mx (0) and (0) := EK (0) (0) then note by defini-
tion mi S H, which implies ||(()) S K H81 and by xa (61) - =x(
= Voo Φ) (01 - -2).
[lh(6,) - (02))l, < max (H [<xx - =x (02)112) - HKN2 110 82ll2.
Furthermore,
- -12 - [G) (1, - (l2))
(
1 K Ksup [V (b,,k) V [ oh,x) T (S(02, sn,,)) . VS(02,
2
2x K
281 K
X² 12 100 - 02112
X² 10: 02112
All the above imply
(H(1)) - H(02)l S VIN(I)
(1((0)) - M(02)l2 1 -KHRI + |KH - KH
+V
KHK x [1((0,) n(02)ll2
2 2RiKgK
$2
KHrz 1101
82l12 182l12 KHH1 KHK]
110 02l12 K KH
X2
/AKHHPIKO/A> + 22 / |00 02212
Then a
e-covering net of (H(0)} can be constructed by the union of covering net of {0 O). By Lemma L.8, the covering (VAK2PP 2 HP
number No satisfies
2Ce (V4K2HPMA0/A + /2
lo Sd 1
-(d)
25

---

Published as a conference paper at ICLR 2023
Step3. First note by definition in Step2
K
(OOvvi+ 0n.N) - Thik - Vitt (5h+t))))) V f(0n, 2n,a)
1 ((a))
Now choosing O(1/K) in Step2 and union bound over the covering number in Step2, we obtain with probability 1 6,
H(Om)
=
K
Te (n Mi
< 2H
V
d
log
A +
)
- =((a)
+ +0
(13)
A8
(())
where we absorb all the Polylog terms. Combing above with equation 12, we obtain with probability 6,
K Σ
A1 & V Vi o(s,
((OTVi 2m.k) - Th. Vi
Vo f(On, Φn.k)
In"
kml
< v Vi(On, ((s
2H
/ay d log
KKi
+o(d) + +0 1
<4Hd V o(s ((s
Cá.log K + Ō
K1
VRK
where Cá.log K only contains Polylog terms.
E.5 ANALYZING Hotz IN EQUATION
Lemma E.8. Recall Hotæ Vf(On, ((s, a))= [ [ ... A0 episode K satisfies K 2 max {512 (1og( (d) + dlog(1 + 1nin2Cok" xx
If the number of
x j then with proba-
bility 1 8,
Ki m22 13 x Nta )d² H2
H22
d &H Cia
[ M(s ((s,aa a))
[Rx(Or0nn)) A0 5
K
where Ô absorbs all the constants and Polylog terms.
Proof of Lemma E.8. Stepl: we first show with probability 1 1
v f o(s, a))= R
(x(0 $ 5 1
) K
Recall by plug in Ore in equation 4, have
(1 Ph+1) Zn, (oh P441) aB
(1 0m)) (x((rraa))
(14)
and by second-order Taylor's Theorem we have
Rx (0 1
(6 (0 ((TT,,,,1B44)) (,(00Iiin1))
Zn (n+h)
(n)
00
-/ ( - TT)TT
Zn (5 (A)) - 0m)
(15)
0000
Kea | on l
5 5g
26

---

Published as a conference paper at ICLR 2023
Note
000 2, (0) 12
0
11)
0
2
Σ
K
0
((((s)n))) - Th, -h, Paoalohiti)) Vool(S
00
0b
==
K
+
(Vof
oh, ( (h.k) + ATa)
0e
A=1
(16)
Therefore, can bound K2z with Riz I (Hrg +31 K and this implies with probability 1- 8/2..
Rx (fTV >>///11
@TV - 8. 8.11: - (Mks + 3k1 ||
8/ 2
2 kizz
36 (log (8) + Ca.log () + 2AC3
(Hii 331122)
kK
<H(1 + 3x1 1f)
And by Corollary E.3 with probability 6/2.
A (On - 0 OTP |1. s 50(1),
Therefore, by Lemma L.5 and a union bound with probability
5,
f (O,, ((s, a)) Inm RR TV (0 )1 = [ ((s,a)) Exp
A2zz (On - -81
) + Rx((0 l
V [s( ((8,a))
1:711 Am; (Ōn - -Drrnt)) ) + RK (xx(0rDrrr (1TVN 1
2m1
+ +
|دم (Op - -OzDn_,)
) + Rx (2
VEK
2kL
+ + +
(cx +0 x = =
Ki K2 max
dd2 + H
VKK
K
K
where Ō absorbs all the constants and Polylog terms. Here the last inequality uses bound for Rx (8.T).
1/1
and Amg (0, 8 >
Step2: By Lemma L.5, with probability 1 8,
ff(On, 0(s, a))=% 1 1BTRm.n
> | fi ((s
||2,1 "/²² / /
+ VĀK
2kg
( VKK
[2Ca + 0 +1 ) = DrriCo
<
+ 0
kk
K2
F PROOF OF THEOREM 3.2
Now we are ready to prove Theorem 3.2. In particular, we prove the first part. Also, recall that we consider the exact Bellman completeness (Ex = 0).
F.1 THE FIRST PART
Proof of Theorem 3.2 (first part). First of all, from the previous calculation (3), (8), we have
(P PA (h a)
< f( o(s, a)) (Prv.., -%% + Hotp,1l
< h + [Zll + [Tl + |Htt + |ott
27

---

Published as a conference paper at ICLR 2023
Now by Lemma E.5, Lemma E.6, Lemma E.7, Lemma E.8 and Lemma E.1 (and union bound), with probability 6,
d 2 2 R2
1
[43|
13
K'
x 12
1
[/2 <ō
) + O
k.
K3/2
[1 <4Hd
V [5 (58, 0.)
Co.log + Ō K1
Vir
K2 max 12 vx
dl H²
H Kat
Hot <ō
K
H²
1 Sō(
K
Finally, Plug the above into Lemma D.3, by a union bound over all h E [M]] we have with probability 1 - 6, for any policy n
H
0
Ex
[4 + 12 + [7al + |Hota + |
h=1
Chot K
8dHE,
V f(On, @(sn, an))
+2+ Ō
where = Ca.iog only contains Polylog terms and
HIH
&
Kl 1 the max H
d 12H*Ko + Ami Ce
H nnd
Chot
VK
K
k3
K Vk
k
K
F.2 THE SECOND PART
Next we prove the second part of Theorem 3.2.
Proof of Theorem 3.2 (second part). Step1. Choose x² in the first part, we have
H
0
Σ sdH Ex
f(h, f(h olsn an)) 'V Vof(On o(sn, an)) - Ō
Chot
K
h=1
Next, by the triangular inequality the norm to obtain
V (On p(s, an))
b:: IVVof o(sn, an))l
Vo (O ak))
Vof p( an)) x7
Vão ((sh, on))
(0n 0% ||a,"
since with probability 1 8,
Vho O(s,, an)) (0) (0h-8%) 8:)1| < R2
0r - 87 s Sō
(mimeelfd
K
V
K
where the last inequality uses part three of Theorem G.3. Then by union bound and Lemma L.5,
RingHdd
Viol(E ((N,, an)) (0h 07)
3/2
K
28

---

Published as a conference paper at ICLR 2023
Step2. Next, we show with probability 1 - 6,
|| Vo (0h. 0(8,, (x)))
First of all,
1 K
1
-0000000000000000000000000000 )
En K
K
(1l (I(v ((s, V ((0.a. Vf10hh.(l..)))VV/000oo00...
ssup
s.a
(V o(s,,)) vf(0%, 0bs, ((. (f )
Kgn9 Hdd
<25igh1 10. 0% | 0
K
Second, by Lemma L.6 with probability 1 1-8
Σ K
A
4/2x3
2d
1/2
0)
log 8
K
VK K
This implies
Σ K
À
4v2R2
2d
1/2
$ Ve oo T]
+
+
log
K
VK
8
2d
1/2
+
log
and also by Weyl's spectrum theorem and under the condition K >
128k log(2d/6)
with probability
1
X
4v
2d
1/2
Amin
Amin (oy(VoS(%% Vol の)
1)
+
log
K
K
VK
8
4/2mg
2d
1/2
k
> +
log 8
2
K
VK
2
then
(x)
E
3-1
2 Similarly, with probability - 5, -,,1(<2) < 3. Then by Lemma L.7,
||Vo (ss al)l KO 1
1 +
|K
||2//K1 ||3//||||KK,,1| ||En/K - |j
6(s
< +
4
+0<+++)0
K2x? 1
K 1x)
IVV (ls, ((s)
x2
K
<2 Vo 0(8, a)) K=
as long as K > Ō (n/+ ). The above is equivalently to
VoJ(07, ((8), < 2 V ((ss,,n)))l))
29

---

Published as a conference paper at ICLR 2023
Combining Step1, Step2 and a union bound, we have with probability 1 - 8,
0 "V"
8dH E.
(V Vof
o(sh,an))
+ Ō Chos K
11
8dHl Ex
Vi 100 @(5n 1o 0(5,, |1.
. Ö
Chot K
+
KIIKHH' 1 k3/2
K
H
16dH By
cla ((sh
0
Chot K
h
where Chot Chot +
G PROVABLE EFFICIENCY BY REDUCTION TO GENERAL FUNCTION APPROXIMATION
In this section, we bound the accuracy of the parameter difference 16, - 8 1| via reduction to General Function Approximation scheme in Chen and Jiang (2019). Recall the objective
(0) : K (0,
Σ
r(8% Vnt (oh+a)]
+ -0112
A
(17)
K
Then by definition, Gr arg mingge (0) and Br satisfies / ((TTVr Therefore, in this case, we have the following lemma:
Lemma G.1. Fix h E [H]. With probability 1 1 8.
(0TO, 5 36H² 36H² (log(1/6) Ca.log R) + AC3 +1
(log((1)))))))) + Ca.log K
E2 where the expectation over p is taken w.r.t. (hi. sh+1) first compute (f)] for fixed 0, then plug-in either Tht1 or B Here
AHEF.
K
K
ohi k 1,.., K only (i.e.
Ca.log(K) == :100o[1424440 + 1)sxK) (1+ 28+88 + 2//11t//)//3 dl log ( (1+288H//dx)k3//
Proof of Lemma G.I. Stepl: we first prove the case where À =
Indeed, fix h [M] and any function V(-) E R Similarly, define (v, = f(Orv, P.VV + 5y. For any fixed 0 E O, denote g(8, a) = f(0 ((s,a)). Then define 10
( V, fv) = (a(s, - V())) (Jv(s,
Since all episodes are independent (((( aft,, (1 (s ) are independent r.v.s and it holds
each other.
Xalg,
K
Xa(g, V.fv) = ((g) E(JV)
(18)
K
We abuse the notation here either X(g. V,fv) ( Vv They mean the same quantity.
30

---

Published as a conference paper at ICLR 2023
Next, the variance of X is bounded by:
Var(X V. [v)] - F (o.J.
(lo(s): an) - - V((a+1)) (fv -m v(sn+1)) 2)
-By,
=En [(((s); an) (sh, (g(s)) an) + fv (sh, 2rn 2V (sh+1)))
<4H² 1 an) [v(sh;
<4112 2. Ex (g(sh: an) Th ((sh+1))) (fv(sh, - ((on+1)) 811 (+)
=4H². (g I. [v]] 8
where the step (+) comes from
Ex (g(on, an) - Th - ((*++1))² ([v(sh:uu) - Th - V (8h++)))
Ex (g and (sh, a+)) (g(sh, an) + fv(s,; ah) 2r (Vh+1)))
= -Ep [[0(s) an.) - (sh, a+)) (g(sn, ax) - fv(sn, ax) + 2fv at) - 2rn (V
-E,, (0(sn, an) - fv )x))²
+ B, [2(g(s), an) - fr(ss, BBp, (fv an) - -n - -V(844) Sh. anl]
2 BBy (g(sn, (n) - (8 ax))²
2H jóvll 2 Ey [(((n, an) - (v an))² -2HeF
(19)
where the last step uses law of total expectation and the definition of fv. Therefore, by Bernstein inequality, with probability 1-6, 6,
Xx(g.f.fv)
K
2Vr ((g.((())) f. fv (1/5)
4H² log(1/8)
K
3K
811E,, [X f. fv log(1/0)
1611 log(1/0)
4/1² log
K
K
3K
Now, if we choose a( = f(h,, ((s, a)), then 0r minimizes (0), therefore, it also minimizes R Dk (0, IV,,.) and this implies
K
K
Σ
(rn Vnti, SV )
Σ
X Da,1, O.
K
K
k=1
Therefore, we obtain
8H2 E,,(X(n,, Vn,1, f1..,,)) 16H log(1/0)
4H2 log(1/0)
[x(XX(n, Pa+1, Je,1,1 5
K
K
3K
However, the above does hold with probability 1 8 since 0n and V min(max, - TT A (f(0, ø(. a)), H) (where A is certain sym- metric matrix with bounded norm) depend on 0n and 0a+1 which are data data-dependent. Therefore, we need to further apply covering Lemma I. and choose ((1/K) K) and a union bound to obtain with probability 1-60 ô,
8H² E, Vn-1. 1. fv.., (log((1))) + Ca.log k) (log(11) + Ca.log
5x(X(On Ph4ZA Si. 5
K
3K
(logg) + Ca x)
+ +4Her
K
31

---

Published as a conference paper at ICLR 2023
where (o))og(K) == 1og(1+24CC + +1)x (1+ 288H CasHH /C + +ate//C+2/// dl log [1+2888 288HHH/V.
1//2///2//// / k
Solving this quadratic equation to obtain with probability 1
36H² (log(1/6) + Cd.log k)
+ Cá.log k) +Aller (log/))))
E [X (On, (4,1,51,1
K
Now according to equation 18, by definition we finally have with probability 1 - 8 (recall the expectation over j is taken w.r.t. (sh ag, sh+1) 1o I,..., oolly
E Le (0x - Eulen (1 = 1 ([(XX(00, (On, Va+1, (D
(20)
36H (log(1/0) Caloo k)
ez 1/0) + Cd.log
4HCF.
K
K
Step2. If X > there is only extra term * (10011, - -1 12)= to above. This finishes the proof.
S
1 Bn
XC
in addition
Theorem G.2 (Provable efficiency (Part I)). Let Cajogg K be the same as Lemma G.I. Then denote b.,KerF 16H + + 4H with probability -
pn. BrVen
36 (/6)) + CaJog k) + 2A0 + bs.Keez
2HEF
vh E [H].
kK
Proof of Theorem G.2. Apply union bound in Lemma G.I, we have with probability 1 1- 8
B., (0 36H² 3 (H))(H/)) + Cajto x) + AC
(ea
ba.Kiez: Vh [H]
K
= (Ca À 0h | Bulen
A K
13+
(log2(1) + Cating x) + 2AC2
+ ba.Keez
K
(21)
Now we prove for all [1]].
0 1
2 1 |
Ep [1r 1(0 . H(, ((.))) -1) Ex (n((r))
1
En En (1
+2HeF.
K
K
(22)
Indeed, similar to equation 20, by definition have
1
> 2110PPanr1
127
E, (On)
E, la (OTinn))))
= EEIX (On. Vh+1s fihnl
K
K
(Tn an)) -rh -Ph+1(ent1)
( ((sh,,)(ss,,a))) -rh - -Pati(5nti))
E,,
-
(Onn 1(0 0 ((.)))) 27
E2
+E,
(Oh, 0(8,, an)) - 1(0 o(
p(sh, (s (Orh ((on rh. -Pat(sn+1))]
(((n,, ((. 1(0 0 27
E2
(1 0(sn, an)) - ((sh E (5 (frti
-Data(sntt) sn, an
+ +
2 2kp
(1(h,o(,)) 1(0TB M( 2H
Here in realization of Lemma 1.9, B 1/2 (since || 11, S 11/)).
32

---

Published as a conference paper at ICLR 2023
where the third identity uses is taken w.r.. S/: au. 8h41 (recall Lemma G.1) and law of total expectation. The first inequality uses the definition of P
Now apply Assumption 2.3, we have
By (f(02: 1(0 2 n 0n 0
1| 112
Combine the above with equation 21 and equation 22, obtain the stated result.
Theorem G.3 (Provable efficiency (Part II)) Let Cd.logK be the same as Lemma G.1 and suppose of O. Furthermore, suppose I 1/2C2 and K N
max 1 (log( (2) + d dolog(1 + AnfnzCok" } Then, with probability 1 vh [H].
(61H2 H22 /6) + Ca.io ) + 2XC + Vk
2H2
V V
sup ((0,.,(s,,)) 100 (s $ 18 KHHV
Furthermore, we have with probability 5,
36 36og /8) + Ca.log R)) 210
2H VK
) +
sup
Vn
V/
Ki H <
h
d2
Kn 1
K
where Ô absorbs Polylog terms and higher order terms. Lastly, it also holds for all h E [H]. w.p.
1 1-6
4H ) V T -
0n 0/112 5 kiHl
72 12 (log( + Caling K) + 4X0%
Ki K2
K
Proof of Theorem G.3. Stepl: we show the first result.
We prove this by backward induction. When = H + 1, by convention [Ohn Ø(s a)) = [0), ((5, a)) 0 the base case holds. Suppose for h 1, with probability (H h)o,
holds true that supa,a [(0++1, (s, (0) a)) s CutIV R + a(h + 1), we next consider the case for h.
On one hand, by Theorem G.2, we have with probability 1 - -8/2.
f(On, o(s (ss a)) - f(0,, o(s,a))
sup 5.a
f(On, o(s. a)) f( ((s, a)) + sup f(Ora,,, ((, ((s,))
Ssup
sup s.a
VS(E, T)) T(On - O ( )
sup 8.0
[(0T M(s - (0r,,,,
SK 00 OTV.. || sup 8.0
Phoca Du+t
Phina h+1
36H²(1og + Ca. x) + 210%
||| Vhi
SKI
KK
Recall (-+ = min f
an(;,), 13 and (.)(())
maxa /(0; ((.,a)) = min (max (0 (( H3. we obtain
| Vittl/_ I ssup f(0 a)) f(0 f(0ht),(ss.)) + sup (n(ss a)
(23)
h,0.
33

---

Published as a conference paper at ICLR 2023
Note the above holds true for any generic (n(s,a). In particular, according to Algorithm 1, specify
(x(--)= = dH Vof Vo o(..)) (+Ō(z)
and by Lemma L.5, with probability d.
2dH VnK
+ Ō 1
TA
K
and by union bound this implies with probability 1 - (H- - h + 1)6.
sup s.a
[(On, ((s,
f(0%, ((s,a)
I
36H2 (H/0) + Ca.log K) + 2X0
2dHK1
VEK + -0=Crr// / + +
SCh+1 V + V K
kK
Solving for Cn, we obtain Oj S k union bound (replacing ō by 8/H), we obtain the stated result.
(6og( HHllog(H///) Coler 22AC k
2dHr1 vkc
for all H. By
Step2: Utilizing the intermediate result equation 23, directly have with probability 1 1 5,
sup h
Vn Vill
S Ssup 8.0
[(hn, Msx a)) - [(0% M6, a)) +
2dHxi
+0
1
VxK
K
where sups,a 8.a f(On. o(s,a)) - f f0%. o(s a)) can be bounded using Step1.
Step3: Denote M == Ki H 36H1 (log( 220)((22/88))00))) C8) K)+2ACE
2H des v
V + O( then by
Stepl we have with probability 1 - 8 (here is some point between On and 07) for all h [H]
2 2 sup 8.0
[( ((,,a) 5(0%, (85
2B ((s, a)) - 100 (bx a)) 2 x |0, 0% ||
where the last inequality is by Assumption 2.3. Solve this to obtain the stated result.
H WITH POSITIVE BELLMAN COMPLETENESS COFFFICIENT 6x >> 0
In Theorem 3.2, we consider the case where ef = O. If cf > O, similar guarantee can be achieved with the measurement of model misspecification. For instance, the additional error (1g())
+ 4Her will show up Lemma G.1 (as stated the current version),
ba.Keer + 22Her will show up in Lemma G.2. Then the decomposition in equation 3 will incur the extra 00, term with 8 might not be 0. The analysis with positive c O will make the proofs more intricate but incurs no additional technical challenge. Since the inclusion of this quan- tity is not our major focus, as a result, we only provide the proof for the case where e = 0 so the readers can focus on the more critical components that characterize the hardness of differentiable function class.
I VFQL AND ITS ANALYSIS
We present the vanilla fitted Q-learning (VFQL) Algorithm 2 as follows. For VFQL, pessimism used and assume 0z θ without loss of generality.
34

---

Published as a conference paper at ICLR 2023
Algorithm 2 Vanilla Fitted Q-Learning (VFQL)
1: Input: Offline Dataset D = {s a rh s/41) 1A==1'
K.H
Denote 0n := Φ(5)) aat)
2: Initialization: Set VH (-)) t
(-)
and > 0.
3: for h H, ....., do
4: Set On 1-+-ar arg mingee
E [0, [0,,0n, on, Th, P x. 11013
5: Set (.(+))) - min [ ((,,)),H H - -h+1}
6: Set (- 1) <- arg max (Qn(:)) mal (n((1-)) Vn(-) maxx. (Qn())),T 1-))
7: end for
8: Output: [=
1.1 ANALYSIS FOR VFQL (THEOREM 3.1)
Recall un(s,a) == Pa (s - (n a) and the definition of Bellman operator D.I. Note minf., - h- 13 is non-expansive operator, therefore we have
(n, a)l =|pn D i1 (s)ssa)) min (PA (s, - h h 13 h - min {1 (()
$ Pn PP - f(On, ol, o(. & [(0th)))) f(0n, 0(. teF.
By Lemma D.2, we have for any
0"
Ex Esh, + Σ Bulun(sh, S
Eellun an)ll + Σ
Ex (s,,
1(0,, ((. Es (1 . 0(-,))
Σ
B. (0.00)))
(1. 2He
h=1
A=1
H
E#
((.
E. Ex (000 (0n,, p( ))F 2Her
h=1
<2rCau
+(, - (0nn (. )MP + 2He
(24)
where the second inequality uses Cauchy inequality and the third uses the definition of concen- trability coefficient 2.2.
Next, for VFQL,, there is no pessimism therefore the quantity B in Lemma L.10 is zero, hence the covering number applied Lemma G.1 is bounded by Cd.tog(K) S ((d) and
36 (log(1/8) + Ca.log K) + XC2 +V
(lo({)() + Ca.tog x) -4He
E,
>
K
K
Now leveraging equation 21 and equation in Theorem G.2 obtain
> 1
> 0
27
En (1(h,,())))) f(0 (( (1:-))))
<En
(n.)))
E, en (a(O
1 K
+ 2HE
K
36H² (log (log((log( (H/5) + Ca.tog x) + 2XC2
6
+ ba.Kee + 211ez
K
35

---

Published as a conference paper at ICLR 2023
Plug the above into equation 24, obtain with probability 6, for all policy x.
36H (log(H///))) + Cd.log + 2AC3 + ba,Kerr + +2He + 2HEF
-" 22/CoaH
K
36HH2 H/00) + Ca.tog K) + 22C
16H (log(1/6) + Cd.log 6Her + 2
-2 Cont W
K
K
=VCant δ
H2d+ AC
+ V Hdder
+
HeF)
K
K
This finishes the proof Theorem 3.1.
PROOFS FOR VAFQL
In this section, present the analysis for variance-aware fitted Q learning (VAFQL). Throughout the whole section, we assume 6 = 0, i.e. the exact Bellman-Comp Bellman-Completenes holds. The algorithm presented in the following. Before giving the proofs of Theorem 3, first prove some useful lemmas.
Algorithm 3 Variance-Aware Fitted Q Learning (VAFQL)
I: Input: Split dataset D {sh ah) K.H. D' = { (5 ah ph) ]
J,A Require 3.
K.H
2: Initialization: Set V (.) < O. Denote dR == (sh, ahi,, dan == 66hh, a
3: for h H, H 1,..., do
4: Set arg mingee
Σ =k=1 (0, Putt (5h )] (2+1(8h+2)) }]
+ x. 10013
5: Set U/ arg min
kk=1 (0,
- 1101
6: Set Vara ((,,) f(vR, ol: (0, [s o6, (6(;,))) ((:)):)) -).
Set G.t ) + max(1, Varp, P,az(,,))}
8: Set <- arg mingee
Σ / (0, (n, Thit - Pi-i 10 a + A 1013
9:
Set + Ek_ v V x ( )n.))) (0 att +d.1,
10: Set Ta < 8v // V (0n, (6. Ar Vaf )(:-)) (+0(k))
11: Set (.).)) - f(0n, Φ1: )) - [n(.)), (n(. t min (Q((s)) ), H - h 11+
12: Set (- (.1 <- arg max (1) ). 1) Pz()) +- max=, (Q)(.)), TT( ()))))
13:
end for
Output: (
J.1 PROVABLE EFFICIENCY FOR VARIANCE-AWARE FITTED Q LEARNING
Recall the objective
1 K K
(0) = E (0,0ls)) - -sss att) - ( ( + K -10112
Then by definition, On == arg millage (0) and OTV.., satisfies 1'0 Pa Cattii (recall Err = 0). Therefore, in this case, we have the following lemma: Lemma J.1. Fix h E [4]. With probability 1 8.
[e (6 36HH + Ca,tog K) XC2
K
where the expectation over a is taken w.r.t first compute (0) for fixed 0, then plug-in either Ont1 U Here
(st, sht2) 1, K only (Le.,
36

---

Published as a conference paper at ICLR 2023
Cajlo((K) == dlog((++04200 + 1)x, (1+ 288 C88 2/ dl log + 11288H + d + 16CgH'R1K) + dlog + 32Cg
Proof of Lemma J.I. Stepl: Consider the case where = 0. Indeed, fix h E [H] and any function V()) IRS. Similarly, define fv(s,a) f(Ory, ()) PAV. For any fixed 0 6, denote g(s, a) ((,, a)). Moreover, for any u, v E θ, define
2 (..) = max f(u, o(. (), - [f(u, oc; No,H
Then define (we omit the subscript u, u of a.v for the illustration purpose when there is no ambigu- ity)
(g(8, a) - (()))))))- V(s))
(g, V, Vv
o (8.
Since
all episodes are independent of each other, Nx V. fv) ( ), (s 11) fv a (8% a))) are independent r.v. and it holds
=
K Xulo.V, = E(g) ((fv)..
(25)
K
1=1
Next, the variance of X is bounded by
Var[X V. fv. [E,(((,,..foo
(co(s)) an) - Th -V(s(()))) (fv - Thh (((x+t))²)) (s2 an)
Ep
(g(sn, an) - an)) (g(sn, an) + fv(ls, an) 2rp - 2V (8(+)))))
Ep
(2(8) an)
02 o² a1)
Eypl (g(Sn) an) - fv((n, an))
<4H²
(2)
(g(sh, an) - To ((sh+1))2 (s), -Th (((h+2))2
-4H² Ey
(*)
(2(snaan)
- (g. f. fv,
(+) follows from that
[Oh,, o(en, an)) an)) f(0 p(sh an)) E (f M Th -Vnt((snz) sn an
E,
0.
( an)
Therefore, by Bernstein inequality, with probability 1- 5,
Xalg.J.Jv.o*
K
k=1
2Vrr|X (g, fv, o²)
log (18)
4H² log(1/0)
K
3K
8H W(g.fffffvv.... log(1/8)
4H2 log(1/8)
3K
Now, if choose a( [ ((s a)) and uh, vn from Algorithm 3, then 0n minimizes en (0), therefore, also minimizes * >K Xi(O, Pnt1,Srr.." 0f) and this implies
K Σ
1 K (u, Phti. fv.... hR) <
Σ
Xe(OTVi, fa, -0)=0 = 0.
K
K
k=
37

---

Published as a conference paper at ICLR 2023
Thus, obtain
8H2. ( Va+i, Jv. :R]] log(1/6) 4H2 log( (1 (1/0) 3K
[ Vati fr, , s
K
However, the above does not hold with probability
6 since On. 0 and V
mmxx ((0++1,0( ((: - f(0n+1. a)) A. Vf(0, ((- a)), H (where A is certain sym- metric matrix with bounded norm) depend on On. 0n+1 which are data-dependent. Therefore, we need to further apply covering Lemma L.11 and choose () and a union bound to obtain with probability 1
8H2 [,|X (On, Vi (Rog((())))) + Catog 4H (log(1/0) + CaJogk)
(O Pn+i, P Rb)1 s
K
3K
where Cd 1log ()ss))))Ktttt +) (1 288 VC + +
d2 log (1 [1+ Vok dloo(1 + 1fC K) + d 32Cg/I*k] K) (where
we = 1/2 since
| - 1/1). Solving this quadratic equation to obtain with probability
1 6,
E,(X (On, Vh+1, f 1 36 (log(10) - Cd.logK)
K
Now according to equation 25, by definition we finally have with probability - 5 (recall the expectation over f is taken w.r.t. (sh, ah, s/41) = 1,.... K only)
36H (log(1/)) + Ca,log x)
En (. - Exlen(0r )1 = [x (On, Tht1.frrn 11
(26)
K
where we used f(Orpr,, = Ph Ph = fPami'
Step2. If X >> there is only extra term * (100))2 -1 (2) S 0n |n/1
AC in addition
to above. This finishes the proof.
Theorem J.2 (Provable efficiency for VAFQL). Lel Cd be the same as Lemma J.1. Then, with probability 1 8
(log(())(H/)) + Cd K) + 2XC wh E [H]
0/ OTV
kK
Proof of Theorem J.2. Apply union bound in Lemma J.1, we have with probability 1 5,
36/12 36/12 (log( (1/) + Ca. x) + XC
(..(n(0)) E, (en (O A On 2
vh [H]
2
(log( + Ca.oo K) 2XC3
(ex - K
E,lla
Orv
K
(27)
Now we prove for all E [H].
27
X
0n
X
E, (1(0n,((.)))) - (((0)))--00mmm) (0 ((:11)9 = Ey
(0))
EE
Cn (n(O
K
K
(28)
38

---

Published as a conference paper at ICLR 2023
Indeed, identical to equation 26,
A 0ren 122 = Bull (xnn )
E
(On)
2
E
ln (OTTVa+))
K
K
[1 (Oh. p(on, an)) -hh (o+2( To and - [5 : an)) rr - -Van( (oilon
=E
Ex
(100,, ((: -1(0-in (..-)))))).)))))) 1oA(:-)
+E
((s,, an)) 1(OTRiNs -(0t ( (PoPhns ((onsaa))))) ra (iti( (oh(on
-Ex
(100,,(, - 1(00p ((.))) (oh(t.))
(S ((s,, an)) S(TT (( E (s ((on - -hatsontt)/sssaa) (oh an))
+
F (1,n, ((.))))11( (
where the third identity uses law of total expectation and that μ is taken w.r.t. Sh. ah. Sh+1 only (recall Lemma J.1) so the o can be move outside of the conditional expectation. The fourth identity uses the definition of Orū.. since f(OTV ((s,a) = Ph.ca Va+1.
Then have
(10),.6::))) f( f(0v o(.1)) 10%(.))
E,
27
0 2 0r
EE f(0p,, 66 / /12
1
H12
where the third identity uses y is over 8h, ag only and the last one uses (%(())) H². Combine the above with equation 27 and equation 28, we obtain the stated result.
Theorem J.3 (Provable efficiency of VAFQL (Part II)). Let Ca,log be the same as Lemma J.1. Fur- thermore, suppose À < 1/2C2 and 2 max 512 (log( 2d + dlog(1 4n Maa K3 xxx)))
)) 11
X
Then, with probability 6, Yh E [H]
(mIHH
36H (log(H/0) Ca, &) 2XC2
2dHT'Mi K1
sup ((0,, - f(0%, pls a(s 5.0
vk
Furthermore, we have with probability 1 - 5,
36H (log( H/8) + Ca.log K) + 2XC
2dH k Vk
>F
+
sup
1/ Vi2
5
K
h
K
d2 K
=ō
3
K
where Ō absorbs Polylog terms and higher order terms. Lastly, it also holds for all h E [H], w.p.
1 1-6 8
0n 0% < K1 / 72H (log( (log((15)) + Ca.log K + 4XC%
4H3
VV 0 K
+
K
K H3
K
Reccal 3 computed in Algorithm uses an independent copy D'.
39

---

Published as a conference paper at ICLR 2023
Proof of Theorem J.3. Step1: show the first result.
We prove this by backward induction. When h = H + by convention s(On; ((s, a)) f(0%, ((s, a)) = 0 so the base case holds. Suppose for + 1, with probability (H h)6,
s. [(O a)) f(6,, ((s,))) I Ch+1 kc we next consider the case for t = h.
On one hand, by Theorem J.2, we have with probability 1 - 5/2,
f(0,, Ms,, a)) - f(0% o(s,))))
sup
sup
((s, b(s a)) - [(0 (s, + sup ((s,a - f(th, ((s,a))
8,8
VS(s, 0(, a)) (On - ) + sup 1(0rpanr -
sup 8.0
00h -rrpa 11 + sup SK1
Phee,uut+1 1ic1-Phhas Phooo Vit1
8.0
|| - Vi (H/)) + Cd.logg k) + 2XCO 36HH'1ogg
SKIV
kK
Recall we have the form (.) min ((; a)) -n(:: a),H) H) and (+++()) maxa [00 ((., a)) min (max. 0( ()), H). we obtain
M Vitn Il.
S sup
((s, a)) f1 ols a))
+ sup (n(s,
(29)
s.a
h,a
Note the above holds true for any generic (s. a). In particular, according to Algorithm 3, specify
[x(:-)) dy Vof(On. 0l: )) A Vof o(.-)) (
and by Lemma L.5, with probability 1-8 8 (note here nn, is replaced by A and || |A, 112 S H22mm)
2dH2 11 +0( +
r
VRK
and by union bound this implies with probability 1 - (H - h + 1)5.
sup f(On, a)s f(8h, ((s.))
SCh+i K
1 + t
36H (log(H) H/8) + Ca.log k) + 2XC3
2dH2 k2
+ +0 ( = C.
=)==C//
1
+ VRK
RK
K
Solving for Ch, we obtain Cn S. K1 H union bound (replacing d by 8/H), we obtain the stated result.
36H ((og x)
+ 22HH for all H. By a VR
R
Step2: Utilizing the intermediate result equation 29, we directly have with probability 1 1- 5
2dH12k ki
sup 1/ - Vir < sup 8.a
[(On, ((s a)) f(0 (fs (2)+
+0(-))
VRK
K
where sup,,a s. [(h d(s,a)) - [00 (b5 a)) can be bounded using Stepl.
Step3: Denote M == Ki H. 3611 36 (1) x222A22
2 v
V + O(k), then by
Stepl we have with probability 1 - 8 (here is some point between On and 07) for all h E [H]
M > sup f( ((s. f(8 ((s, a))) 2
sa
> Ey (1 ((+, 100 Cis a)) 92n xx 0, 0z 2
40

---

Published as a conference paper at ICLR 2023
where the last step is by Assumption 2.3. Solving this to obtain the stated result.
J.2 BOUNDING ( 0%²²
Recall the definition (-,)) = max[]1[[arrs Vitil(s)). In this section, we bound the term [ x = (;)())) (h
and
K
4/h = arg min dEG
f (0, (n.)) - (h+1(5h+1) }]
+ K
11013
K
(30)
1/ arg min AE
S (0, - (
}]
A K
1101/
K
where
(. :0a,)))aa f( ø6, (a.m
and true parameters 2h ox satisfy f(u7,0((..)) = (V =
Ep (s))) Furthermore, we define
(v)) max [Var,, Va+il(,)))
and the parameter Expectation operator J V E R Olv E θ such that:
f(0ıv, Φ) = Ep, (v))'), v|V - By.
Note OJV E @ by Bellman completeness, reward is constant and differentiability (Definition 1.1)
an additive closed property. By definition,
/ Butt S|s(wn, Ø) 5(0 3) - [S(us, o)² [(0 6)
<ls(nn Φ) 5(030z [0) - 2H If(un, 1000)-((p)
f(0 (00
and
10 0 [1 Φ) s(mn, x) + +f(f,) o)2 2 -i(wn, 3)² f( 6) f(vn, Φ) 2H If Φ) f(vh. Φ)
We first give the following result.
Lemma J.4. Suppose À S 1/2C3 and K max 5122 (log( 2d) d dog(( )njmaCol)) 41
1 :
Then, with probability 8, vh E [H].
wh E (H), 36H2(log( (H/5) + +(P)) + 2XC
u/ 0g 1
k.K
wh E [H] (log(() + Ö(d)) (((()))+2CE 22C
11. -Oppz SV
kK
and
36H² ((())))))) 2XC3
2H²dk + /R
T
+ +
sup If(u,, a(s,a)) f(uh, o(s,
KIH
V K
*.a
36o4((ogg( (H2 -3 + 2k1
T
+
sup (fpl ((, - f(vi, o(s, a))l s
K1 H
VR
The above directly implies for all h
[H]. with probability 1 1- 8,
10022 - -711 < 3xz 11 (lg(H))))))))))) + Ō(d))) ((dd)))++ + 2XC2 6H
/ VE+
Vn
(log(H/))) + O(dP)) - 2XC3
|0 22 <3HRi|
111
k.K.
41

---

Published as a conference paper at ICLR 2023
Proof of Lemma J.4. In fact, the proof follows reduction from the provable efficiency procedure conducted in Section G. This is due to the regression procedure equation 30 is the same as the procedure equation 17 except the parameter Bellman operator T is replaced by the param- eter Expectation operator J (recall here Φ1, uses the independent copy D' and (dd)) comes from the covering argument.). Concretely, the (g. V. fv) used in Lemma G.1 will be modified (gg fv) (g(s, a) V(s'))² (f(0)v.(s.aa) Vs'))² by removing reward information
and the decomposition
Ep [(g(s), sh, a,) - (sn+1))) - (((0),0(ss) an)) - V (s = Ex [[g(s), as) - f(0l,, 9
holds true. Then with probability 5,
10 o. 511(0% ②) - f(v,, 6) + 2H [f 6) f(mn, Ø)
) V + + K
36H (H3 + ((d))) 2ACg
6H dri
3kg H²
Vk
and
G p
Slf(vn, Φ) - -(0002,,,00 2H If(un, の) f(0)p_,,,)))
Pati
Ski
1/1 -800
+HHK] un 83v 10
2
(lo(4H))((H))) Ō(d)) + 2AC
<311i||
kK
J.3 PROOF OF THEOREM 4.1
In this section, sketch the proof of Theorem 4.1 since the most components are identical to Theorem 3.2. We will focus on highlighting the difference for obtaining the tighter bound.
First of all, Recall in the first-order condition, we have
(h.k)) - rh.k - Vnta (sh+1)
V
+ A 1101
0, wh [H].
( ag)
10=0%
Therefore, if we define the quantity Z,(,,') E TR.d as
2, (0, k) - (st vf(0,00 on,)) o att
+x 0, V0 E0 s H,
( a
then have
Zn (n(0% ==)==0
= 0.
According to the regression oracle (Line of Algorithm 3), the estimated Bellman operator Pa, maps Th+1 to Op. i.e. PAVn+1 = [0n, o). Therefore (recall Definition D.1)
Pa Painita P (8, P f(0,, ((s.
=f(0 ((s,a)) (0h, ((s,a))
(31)
=VI(0,, ((s.a)) a)) (0Ti. 8n) Hot
where we apply the first-order Taylor expansion for the differentiable function f point 0n and Hota,1 is a higher-order term. Indeed, the following Lemma E.1 bounds the Hot term with Ö(k)
42

---

Published as a conference paper at ICLR 2023
Lemma J.5. Recall the definition (from the above decomposition) Hot :
f(0,, ((s,)) v f(0,, (Tr - B.)) then with probability 1 - 5,
Hot - Ō1 1 ), vh E [
Proof.
The proof is identical that of Lemma E.1 but with the help of Lemma J.2.
Next, according to the expansion of (o Vn+1, [ we have
(b o(s,a)) (OzVnts - 0m) 11 + 12 b7 Hot2,
(32)
where
Hot = (0 a))A (Rx((TTNn + A0T
[(0 on,N) - Thin - V Vool(On, Φn.))
A.
(2( att)
Vos(On, on,x)) (Oh, sman)
A
+ Ala
(2 a%)
Rx (0
A (On ( Rx Rx(O0Tv..
where Rx (Vr+1) is the second order residual that is bounded by Ö(1K)) and
(((evve )n.n) Th.n - 2 Vo f on.c)
((s
(3 ah)
[00TBhe Φm,)) f(Orvie (mnk)) (n+1(51+11) + Vhttl V s(On, d).
12 -V o(s
(7 ah))
K (10Pppn) )n.)) Th. Pn (Vo (00p) -V ((s,4)))
V/ f(On, Φn,x))
0 a7)
Similar to the PFQL case, I2, Is, Hotz can be bounded to have order O(1/K) via provably efficiency theorems in Section J.1 and in particular, the inclusion of of will not cause additional order in d. Now we prove the result for the dominate term IT.
Lemma J.6. With probability
1-
Thl S 4Hd (0, 0(8 a))
Co.log K +
Ki VKK
where Co.tog only contains Polylog terms.
Proof of Lemma J.6. First of all, by CauchySchwarz inequality, we have
K
(f(TTVE) (n,k) Thik V (sh+
VJ f(0n Φn.e)
|h < V (0,, 0(8 a))
Σ
A
67,0%% at)
A
(33)
Recall that (.))) max(1, f(v, 0(, 10.000 (00))
[f(u. :)) 1000---44 -+
Note in Lemma I.11, we only have additive terms that has the order has Lemma I.100.
43

---

Published as a conference paper at ICLR 2023
Step1. Let the fixed 0 E + be arbitrary and fixed u, such that o., 2 oo (1, 2 (,+)) and define xn (0, u, v) = (of on, at). Next, define Gap (0)
(1)))
Σ ff(0, )) Vf(0, p(s , a²)) /o (sh at) + Maa, then || I 81. Also denote
Th = (OTv.... )n Th (5+ u af), then E/ a = 0 and
Varlf(Orv k ph,k - Vhtt (8 (1h+12) 1s% a
Varlmk 1sh a
2Var(5 141 2). Th.k
Vitn (6h+1)
Th (
p, Vittilssh (
2
(5h (6h%o0) of)
then by Self-normalized Bernstein's inequality (Lemma L.4), with probability 1- 6,
4K
14K2)
T& (0, u. 7)
<66 dlog
1
loog
+
+4clog
Ō(Va)
Ad
5
8
G(
[100v (((,a))) - (s'))
(s') and the last inequality uses vd
where Incl $ 5 with Ç (= 2 m Õ())
Step2. Define ((0,u,0) = -K 3xx u) v) and H u, v) 11,(0, u, v)llc.,..00
[1h(01, uI, v1) 1:(02, U2 022 112 S K max (25 (0) v1, (xt m1s (02, 12 02)112
Vf(0,, )n,k) - ff pnkk)
02 u (s a.) o² Ju ($/, a/j
$ K max
11
+ HKi
k
o 2 (s at)
pn (sh o ug ( agt)
$ KHK1 ||0 02l12 + K KHK1 || I - o 222.2al2
Furthermore,
GG, 01) 1-- Gr U2, 22) 111 S Gi,(O,, u1 0z) (0,, u1, 01) Gr2 u2, uz)ll Gl u2, 02) 02) 2|12
Vf(02, xh,x) (Or, )n.N)
Vf(02, )n.a) Vf((2, 2b.))
K Ksup X2
o2 (6 ag))
o2 (8%
k
1 $ (KKgta ||0 - 02ll2 + Kv² | 0 v222)
X²
All the above imply
[0(0,, u1, v1) (02, u2, 22)1 S / 1h(01,, u1, v1) Cuner (01)- u1, h(02,, u2, v2) Guzivz (0)))~(((22) u2, 22)
[11(0,, v1) 11(02. U2, 12) x KHKi + KHHI [/aan. (0)) Guz.nz KHRI
(KHm 1) 1--1h(0,, un, v2) - h(02, u2, 12)112
KKi KH (110) -00l2 + 1102a - ohg KH + K2HHN
22
(N2 110 - 02112 + Ni 1|02,m - o22.))ll))
x2
4K=HH4R//++ (KHHInNKO/E+) V100 - Balla
- + (VKKHPRR/A+ /KHHEn/XX*
Vilotnes Abavella
note
10 (s, on (s)a)) < f(1 ((s,a)) f(12, ((s. a))l + 2H ((8, f(uz, ((s,
< || rell2 + 2H ||u
U2 w2ll2
Then e-covering net of (11 u, e can be constructed by the union of covering net for 0, u and by Lemma L.8, the covering number Nv. satisfies (where Ô absorbs Polylog terms)
log.N. zŌ(d)
44

---

Published as a conference paper at ICLR 2023
Step3. First note by definition in Step2
K
(f(0vV) 0b,N) Th, Vit (5h+1) V/ f(On; (n,k) 9n,k)
H(O,, uns U%.)
(
Now choosing = O11/K) in Step2 and union bound over the covering number in Step2, we obtain with probability 8 (recall vd 2 O())),
H (0,, Un vn)) S16 dlog
1+
KnT Xd
[log
4K2 8
+ +(d) + 4c
4K²
+ +(d) +0 - K
8
<õ(d) + +0
1
K
where we absorb all the Polylog terms. Combing above with equation 33, obtain with probability 1 - 6,
44 < v vi(On, ((0,nooss.0)
())
(O un, v%))
A2
[ōie)+ + 0 + K
vs(ōn @ 0)))
2,2
<ō (a/
<0(4
V f( ols ((..)))/
+ +0
+ VKK
16
Combing dominate term [1 (via Lemma J.6) and all other higher order terms we can obtain the first result together with Lemma D.3.
The proof of the second result is also very similar to the proofs in Section F.2. Concretely, when picking n², we convert the quantity
VJ ol o. o(sh,
to
V f(0 ((sn
((s
using Theorem J.3, and convert
V. ((s an))a)))aaa (sn an))
to
f(0 p68 an (,)) (88 an))
using Lemma J.4.
K THE LOWER BOUND
Theorem K.1 (Restatement of Theorem 4.2). Specifying the model to have linear representation = (0, Φ). There exist a pair of universal constants c, c, > 0 such that given dimension d, horizon H and sample size K. > c'd3, one can always find a family of MDP instances such that for any algorithm म
inf sup EM [V' - 22l2evd Σ E. -1 MEM
(34)
where AT = ΣX Vof(O, Vo o000
Varg Va 110
Remark K.2. Note Theorem 4.2 is a valid lower bound for comparison. This is because the upper bound result holds true for all model such that the corresponding F satisfies Assumption 2. 2.3. Therefore, for the lower bound construction it suffices to find one model such that the lower bound equation 34 holds. Here we simply choose the linear function approximation.
45

---

Published as a conference paper at ICLR 2023
K.1 REGARDING THE PROOF OF LOWER BOUND
The proof of Theorem 4.2 can be done via a reduction to linear function approximation lower bound. In fact, it can be directly obtained from Theorem 3.5 of Yin al. (2022), and the original proof comes from Theorem 2 of Zanette et al. (2021).
Concretely, all the proofs in Theorem 3.5 of Yin et al. (2022) follows and the only modification is to replace
1 V Ex [o] (A Ex. [0] s 2
16 (+1, un wa)ll (A)0)) + 2 11 (-1, (-1,wa)l(a3.))
Section E.5 by
Ex Vo(.))
1 | + +
1 -- un un>llag07>-
-
and the final result holds with ((.,)) (of o(:,)) :) by the reduction f (0.
L AUXILIARY LEMMAS
Lemma L.1 (k-th Order Mean Value Form of Taylor's Expansion). Let k: 2 1 be integer and let functionn f IRd - be times differentiable and continuous over the compuct domain O C Rd.
Then for any x, 0 O, there exists in the line segment of x and 0, such that
1 fxx) 5(0) =V (() T (x 0) 21 (x
T) (0 0) + ... + 1
V
((0)
X (x 8))
(k. 1)!
1 V ((E) (zx-
Rs!
Here V*5(0) denotes k-dimensional lensor and X denotes lensor product. Lemma L.2 (Vector Hoeffding's s Inequality). Let X (X ,Xa) be d-dimensional vector Ran- dom Variable with E X = 0 and | I R. x x(1)'s 's are n samples. Then with probabil- ity 1 - 6.
n1
4d
d log( )
(
Proof of Lemma L.2. Since || S R implies X
S R, by the univariate Hoeffding's 's inequality,
for fixed j E {l, d). denote Y, == 1 n Di=
Then with probability 1-6 (note (x s R),
R22
log( (
Y 2 2
58.
By a union bound,
R2
1
R² 1
P Bist [Y 2V n
log( 8
< d8 +
Vi Yy]] s 2/
log(
2 1 - d5
8
n
4R
1
4dR2 log(
1
# P
Vi Y? <
log( 0
> 1 d8 + P
||X||| S
(5)
2 1 d6
4d
+ P
||8112 <
log(
2 8.
Lemma L.3 (Hoeffding inequality for self-normalized martingales (Abbasi-Yadkori Yadkori et al., 201 1)). Let (n 1 be a real-valued stochastic process. Let (Fe) be a filtration, such that ne is Ft- measurable, Assume The also satisfies th given F.-1 is zero-mean and R-subgaussian, i.c.
AA TR,
E AM [i-1]
xxx2 R²
46

---

Published as a conference paper at ICLR 2023
Let {xx )2 be -valud stochastic process where 2, is Fi-1 measurable and || L. Let A ATa E.=1 Fzgigg Then for any 5 > with probability 6. for all t 0,
Σ Iz
S SRR
d
log
A + tL
2
Lemma L.4 (Bernstein inequality for nelf-normalized martingales (Zhou et al., 2021a)). Let (ne he be real-valued stochastic process. Let {Fi) be filtration, such that is Fe-measurable. Assume Tit also satisfies
mel S R. [ 1 O, [Tte Ft-1] So²
Let (1)))= be -valuue stochastic process where I2 is F; measurable and ||=a|| S L. Let
A Ala E.= FsHg. Then for any 5 > O, with probability 1 for all t >> 0,
Σ X
$80 dlog [+
tL? Xd
log
4t2
lo
1t
A,
Lemma L.S. Let V1(0,ol; x(:
S A
IR be
bounded function S.I.
suPace [|V o(; o(s 2ll S 11. If K satisfies
K max 512 Mi
2d logl 8
4kg B² 32 )
4X
+ d log(1 +
x²
X2
Then with probability at least
8, for all ||ul12 S
simultaneously, it holds that
2B
1
|ul|2,, S
VRK + 0
K
where En, -E Vi o(sh .t)) VS ( x Ala-
Proof of Lemma L.5. For fixed 0 define G Σn ff ( at)) ( oss a Ala-
and G = E,IVV ( o(s,, an)) (f, ((5h, a+)) 1. then by Lemma H.5. of Min al. (2021), as long as
2d K 2 max G || log( _))) 42 ---
(35)
then with probability 1 5, for all u E Rdd simultaneously, | S Vेx ||u|| As a corollary, if we constraint u to the subspace ||u||2 S B, then we have: with probability 1 8, for all {u Rd. ||u]|2 < B} simultaneously.
2 VK
2 VuTG-luS
2B V G
|
|lull
(36)
VK
VK
Next, for any 0, define
K
uT ho)(0) = |lull 8-1 Vu GG-u-- V
EV
f((0, oi at)) v5(0, (s dt))TT + Mla)
and G(0) = MK Vf(0, p(s) at)) Vf(A, ((s) a + Ala, we have for any 0, 02
K
[G(()) - G(82))12 -
(V (f o(s) ah) v f(2,, o(s - (b)) ff((,,
Vf Φ ( (Vi(01, ob at) Vf o af)))
<KNzKi ||0 02112 + KNana 1|0 02112 < 2KKrr ||0 - 02112-
47

---

Published as a conference paper at ICLR 2023
Use the basic inequality for a, b 0= Vā- v0I b/.
sup (0,) (u((22) sup
I (G(0))-1 (G(0))--- o| S <VB²... - G(0,)-111
S Ba |[((0))"" [[0(0) - G(02))1 ( |[((0)) 1/12
1
2Ba Knin
|00 02112
Ba 2KK2k 10: 02l12
X²
Therefore, the e-covering net of (h(0) 0 E ) is implies by the -overrinn net of {0: 0 E θ), so by Lemma L.8, the covering number No satisfies
x
2K BK
Ng & dllo(1 + 4B 1K2KKI
X
Select 0 0n. Choose O(1/K) and by union bound over equation 36 to get with probability 1 8, for all ||ul|2 B (note By Assumption 2.3
1|G- S 1/k),
2B
1
|ul|
+
+0
VkK
K
(union bound over the condition equation 35)
Ki k
2d + d log(1 +
4kg 4k, B² 132r22CCC (
)
41
K 2 max
512
Log( 5
X2
where this condition is satisfied by the Lemma statement.
Lemma L.6. let Φ S + Rd satisfies a))l
I C. for all s,a 8 A. For any
K > 0, O, define GK = =E Φ(sk, as (((k) ax)
+ Ala where (sk. ax) 's are i.id samples
from some distribution Then with probability
GK K
[GK]
4v202
2d 1/2 log 8
Ey
K
VK
Proof of Lemma L.6. See Lemma H.5 of Yin et al. (2022) Lemma H.4 of Lemma Min al. (2021) for details.
Lemma L.7 (Lemma H.4 in Yin et al. (2022)). Let A₁ and A2 Ruxd are two positive semi-definite matrices. Then:
||Ti|| < | + || ||a ||A
A2ll
and
| S 1 + VIA45'1 ||a/| ||T ||A1 A2ll ||0lll," 1.
for all á BER Rd..
L.1 COVERING ARGUMENTS
Lemma L.8. (Covering Number of Euclidean Ball) For any 0, the e-covering number of the Euclidean ball in Idd with radius R. > 0 upper bounded by (1 + 2R/e)a.
Lemma L.9. Define V to be the class mapping S to RR with the parametric form
v())= min f(0, ol, a)) - V ol T T A.
H}
where the parameter spaces are (0 |10112 S Ce} ) and {A: ||A||, - B}. Let NY be the covering number of c-net with respect to loo distance, then we have
log < dlogg (1 SColxi + 22 2BBB 22)
8vaBn?
+ dl Plog log
1
2
e²
48

---

Published as a conference paper at ICLR 2023
Proof of Lemma L.9.
sup [V( - V2(s)]
f(01, (0, f(01, - A ((s)), a)) / sup
/V 0(s,0)) As V/(02, ((s,a))
5.
sup
VS(E, (s, (0) 02) (000))000000---00010d000)0
Vf((1.
(. ()) A2 V
-m1-10 02 + sup
Vf((0,, -
A2 Vf(02,
SK1 10 - 02 + sup
A1 V/(01,
+sup v /V (s a)) (A - A2) ((s0), + sup V ((s, A2 (V](0,,0(s,0) (( (0(00.((5,
Sm 10 - 00212 + 2sup
v (((0), ((s,),(())))) B- + r || A2ll2
8,a
Smi 10, - 0212 + 2sup
f o(s. vf(22, 0(s, a) 0)) B. + n ||A - A2ll2
VS(0,, (s.. a))l2 110, 02112 B. B-Mi + v |A - -2ll2
Smi 10 - 02112 + 2sup
Smi 100 - 02/12 + 2 N2
10: 02112 B. + v vr 1|A1 - A2l1z
(NIVCa 2v (xBNA)))
/ /100 02ll2 NI /IIAi Azll2 S (NIVOO 2v BNIK2) 2 v V110 02112 MIA
A2ll
net Let Co be the NeivDe+22 2 net of space (0 100| S Co) and Cu be the ax3 nnet of the space {A: ||A|| S VdB}, then by Lemma L.8,
Here ||-11 is Frobenius
8C@(ki V Co + 24 Br CCul s (1+
8vdBMi
|calS 1
2
Therefore, the covering number of space satisfies
1o S Log(((wl-1CC,) s dlog (1+ 8Ce(n) Vo + 22 2/BKk Bkikk)
8/dBk²
+cllog log
1+
Lemma L.10 (Covering of (X V. Define
X(0.0') = (f(0, ((., - - Vor(s (s. - (s))))
where fv == PAV+ and V(s) has form (s(s) that belongs to V (as defined in Lemma L.9). Here X(0,0" 8') ) is a function s, a. as well, and we suppress the notation for conciseness only. Then the function class H [h(00 0') = Ex, (0,00)) 1012 < Ce. E V} has the covering number of (e AHer)-nee bounded by
dlog(1+ 24Co(H 1)kg Jdd (1+ 1+
Vo + 2 (BBBAAA)))))
288H2 V
+ log
1+
x²
Proof of Lemma L.10. First of all, ((,,0') = = ((s, a))² (8, -
((., (r+ Vo)) + +25,, (s, (r Vor(s)),
49

---

Published as a conference paper at ICLR 2023
For any (1), (02,
[x(0), 87) - X(02, 02) = (f(0), ((s, f(0,, Φb a)}
+lfv,; (s, a,, -v,, (s,y (s, fv., (s.a)) (r (s')
(s,a) - o(s. - f(0,, o(s a))l (r + (s')
Vog
$2H - a))] 2H VVv (8, IV (8,
-VV- + 15( ((8, f(0,, ((
+1).111)(..000s..))) f (10 2H max Voy (5' Vos (s') + +Hcr
0(s, a))l
+4H. -Ve; (s')
<(HH + 1) |/ fS, ((5, a)) ||0 82ll2 + 6H VV;
Vos Io + 4Hcr
<(HH + +)x1 ||01 82l12 + 6H VV:, Vogll 4HEF
where the second inequality comes from fv +ôv. Note the above holds true for all s, r, therefore it implies
(x [1)] - (62, I sup |X(0), 81) - -x(2, 62)1
8,0,5'
S(H + 1)m1 |10| 02112 + 6HH | Vogllo + tHer
Now let C1 be the T2( net of {0:
|10||2 I Ce} and C2 be the e/6Mtnnet of V. applying
Lemma L.8 and Lemma L.9 to obtain
log [Ca| S d log(1+ 24Ce(H + 1)81,
1+ 288HF 2 2/
288 2
/dRx3
log |C2| dlog
t log 1+
2²
which implies the covering number of H to be bounded by
log [C1l-|Cal S dloog(1 24Ce(H 1)k1
288/H 2 Brake) 2)
288 VdBRi
[
+d log 1
6
Lemma L.11. Denote oū, = ((, -++1)] ((,,,(s-))) -441l and define
X 0' w. = (f(0, - - VVr(s'))) (fv (8, - Vor (s'))
(s,
where Jv = PRV and (8) has form Vo(8) that belongs to V (as defined in Lemma L.9). Here X(0, 6' u. v) is a function of s, a,T,T as well, and we suppress the notation for conciseness only. Then the function class H {h(0, 0', v) = E,(X 0', 1)]1101122 S Co. V} has the covering number of e-net bounded by
dlog(1 24Co(H + +1)=1 dlog
( 2 BBIIN)))) + d log 1+
288/ VdBRa
1
6²
d + 16C&HH' + dlog(1
32CoHH'
Proof of Lemma L.II. Recall
0 (..))))))
[[(u, o(. (0.H--)))) }, and since max, truncation are non-expansive operations, then we can achieve for any 8,a
Jo (s o on (8, a)l & [(1,, (s),))) [(22, (6, a))l + 22H ((),)))))))))))) (122,
Ssi ||| valla 2Hmm || u2 2
50

---

Published as a conference paper at ICLR 2023
Hence
X()),
X(82, 822
(01, (1,,00 v1) X(2,, 82 u2, u2)
01,
0 u1,0h
0
U2,02
X(01, 01) - -X(02, 02) 0h [x 01) - ( (0)20/2)2 | 277 10
X ((0,,0g)
(o (1,10
0 21 42.12
2 u2.
- [x((),0() - ((2, 02) 21 K1 ||11 - 22212 + 2/1 ||ui - -12l2
- (6H + 1))11 ||0: - 02ll2 + 6H Vo; - -Vosll + 2H K1 ||U| - -22122 + 4HHM, 161 ||u1 u2ll2
Note the above holds true for all s, a, r, s', therefore it implies
E (x 84 u1. 02) - E., (2, 22 1/2 12)]l
<6H + 1)x1 |10, 02l12 + 6// VV Ve, Il 2/H2ki kt ||0| 1/11--2ll 02ll2 + 4HHxx ||ui u2ll2
and similar to Lemma 1., the covering number of c-net will be bounded by
dlog(1 + 2HCa(H + dlog (1+
Co + 2/Bk)12))) + d log 1+ 28811 VdBRi
- doogg(1+ + 16CaH + dlog(1 +
32CaH'ki
Comparing to Lemma 10, the last two terms are incurred by covering u, v arguments.
51


Reviews:
[{"review_id": "nnwOoVfLwmF", "reviewer": "Reviewer_7cjK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies offline RL with a differentiable function class. With the assumption that the covariance of the gradient of every function (w.r.t. the parameters) in the function class has a positive minimum eigenvalue, this paper proves sample complexity bounds that scale with the number of the parameters. The results in this paper recover existing results for linear models and generalized linear models (up to an additional $\\sqrt{d}$ factor in the instance-dependent bound).", "summary_of_the_review": "My main concern is whether the differentiable function approximation setting considered in this paper contains new settings that is unknown in prior works. However, given that the results in this paper require some novel techniques, I will recommend a weak accept at this point.\n\n=== after rebuttal ===\nAfter reading through the authors' response, I tend to keep my score as weak accept.", "strength_and_weaknesses": "Strength:\n- The differentiable function class considered in this paper generalizes linear/generalized linear models. The sample complexity bounds for generalized linear models in this setting seem to be new.\n\nWeakness:\n- The two equations in Assumption 2.3 is required for every possible parameter $\\theta$, which seems to be very strong. It’s unclear to me whether there are other function classes (beyond linear and generalized linear models) that can satisfy Assumption 2.3. For example, does a two-layer neural network with constant number of neurons satisfy Assumption 2.3?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "iwdIcw1TAQ", "reviewer": "Reviewer_4N32", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies parametric offline rl with a class of general differentiable function class approximation (DFA). The differentiable function class they consider is the set of functions $f(\\theta, \\phi)$ whose argument can be decomposed into two parts: $\\theta$ is the parameter vector and $\\phi$ is the feature map. They further assume that $f$ is third-time differentiable with respect to $\\theta$ and their derivatives are jointly continuous wrt $\\theta$ and $\\phi$. This function class is a generalization of linear model where $f$ is not necessarily dot product of its arguments. \n\nUnder two assumptions: (1) realizability + Bellman completeness, and (2)  the behavior policy is well exploratory over all dimensions of the gradient of DFA wrt $\\theta$, they obtain a guarantee in a form that is similar to the linear MDP; though here they consider a much more general function class. Their bound scales linearly with d, H times the uncertainty quantifier across the trajectory of target policy. They also incorporate variance information to remove the factor $H$ in their learning bound.", "summary_of_the_review": "See the strengths and weaknesses section. ", "strength_and_weaknesses": "**Strengths** \n\n- A generalization result of offline linear MDP to differentiable function class and incorporation of variance information \n\n- The paper is well-written and easy to read \n\n- The remark about feature representation and parameters looks interesting and can give some room to think more about the problem of representation learning in offline RL.\n\n**Weaknesses** \n\n- The data coverage assumption 2.3 is pretty some as it is equivalent to the uniform feature coverage assumption when realized to linear MDP, which is among the strongest data coverage assumption. \n\n- Optimization oracle at line 4 of Algorithm 1 is pretty strong as obtaining the global minimizer for a non-convex differentiable objective is difficult unless it is an overparameterized neural nets (see also the next point)\n\n- However, the dependence on $d$ in the learning bound makes their result inapplicable to overparameterized neural networks where $d$ could be a high-order polynomial of the number of samples\n\n- The assumption about third-time differentiability also cannot apply to neural networks (not necessarily overparameterized) with non-smooth activation such as ReLU. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "hzoRgy0m8Xn", "reviewer": "Reviewer_tREF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies offline reinforcement learning with differential function approximation (DFA) indexed by a parameter. Leveraging the ideas in DFA and the pessimism principle, the authors propose a value-iteration-based algorithm and analyze the suboptimality of the learned policy. The theoretical results generalize previous asymptotic analysis for DFA by constructing a finite-sample uncertainty quantification for the fitted value functions. A variant based on variance reduction is also provided and analyzed. The authors also discuss a few implications of this framework. ", "summary_of_the_review": "I find this paper to be good overall. It provides new algorithms and analyses that generalize the existing ones to the FDA setting, and is quite intensive and comprehensive, covering almost all aspects of value iteration with offline data. This is a solid work although I find the technical novelty to be not very pronounced.", "strength_and_weaknesses": "Strength:\n\n1. This paper provides a new algorithm and finite-sample analysis for offline RL with DFA. The theory seems sound because the main arguments look correct to me, although the analysis is too overwhelming hence I did not check all the details. \n\n2. This paper provides a comprehensive discussion of the application of existing results to the DFA setting, including the pessimistic value iteration and its variance reduction results. \n\n3. The authors did a good job in positing this paper in the related literature, and include detailed discussion on the implications, making this paper fruitful and dense. \n\nWeakness:\n\n1. All the results seem to be generalizations of existing algorithms and theoretical results. It may be helpful if the technical novelty can be discussed more thoroughly. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IwQ8VTgMS_", "reviewer": "Reviewer_eR8G", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies offline reinforcement learning with differentiable function class approximation (DFA). This function class incorporates a wide range of models with nonlinear/nonconvex structures. The authors show that offline RL with DFA is provably efficient via analyzing the pessimistic fitted Q-learning (PFQL) algorithm. They further improve the guarantee with a tighter instance-dependent characterization. ", "summary_of_the_review": "The technical contribution of this paper is significant. It provides novel ideas in the theoretical analysis of offline RL. ", "strength_and_weaknesses": "This paper provides novel theoretical results for the offline RL with function approximation. The authors of this paper study the differentiable function approximation, which is new to the area of offline RL, though some parts of the related theory are first studied by [Zhang et al. (2022)]. Their analysis is further improved based on the idea of variance awareness. Thus, the contribution is significant to this area. \n\nThere are also several questions regarding this submission:\n\n1. Can the authors provide some explanations on why in Theorem 3.2 and Theorem 4.1, the results only hold for $K \\geq K_0$? What is the technical consideration behind $K_0$. How are $\\kappa_1$ and $\\kappa_2$ defined?\n\n2. Is it possible to have an improvement on other factors ( e.g., $d$ ) beyond only an $H$ in the result in Theorem 4.1 based on the idea of variance awareness?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster