Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^\pi$-Realizability and Concentrability
Authors: Volodymyr Tkachuk
Gellért Weisz
Csaba Szepesvari
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
learning theory
offline RL
batch RL
Primary area: reinforcement_learning
TL;DR: We show that trajectory data suffices for statistically efficient learning in offline reinforcement learning, under the assumptions of linear $q^\pi$-realizability, and concentrability.

Abstract: We consider offline reinforcement learning (RL) in $H$-horizon Markov decision processes (MDPs) under the linear $q^\pi$-realizability assumption, where the action-value function of every policy is linear with respect to a given $d$-dimensional feature function. The hope in this setting is that learning a good policy will be possible without requiring a sample size that scales with the number of states in the MDP. Foster et al. [2021] have shown this to be impossible even under $\text{\textit{concentrability}}$, a data coverage assumption where a coefficient $C_\text{conc}$ bounds the extent to which the state-action distribution of any policy can veer off the data distribution. However, the data in this previous work was in the form of a sequence of individual transitions. This leaves open the question of whether the negative result mentioned could be overcome if the data was composed of sequences of full trajectories. In this work we answer this question positively by proving that with trajectory data, a dataset of size $\text{poly}(d,H,C_\text{conc})/\epsilon^2$ is sufficient for deriving an $\epsilon$-optimal policy, regardless of the size of the state space. The main tool that makes this result possible is due to Weisz et al. [2023], who demonstrate that linear MDPs can be used to approximate linearly $q^\pi$-realizable MDPs. The connection to trajectory data is that the linear MDP approximation relies on "skipping" over certain states. The associated estimation problems are thus easy when working with trajectory data, while they remain nontrivial when working with individual transitions. The question of computational efficiency under our assumptions remains open.

Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear q" -"aaailizability and Concentrability
Volodymyr Tkachuk
Gellért Weisz Google DeepMind, London, UK
University of Alberta, Edmonton, Canada
Csaba Szepesvári
Google DeepMind, Edmonton, Canada University of Alberta, Edmonton, Canada
Abstract
We consider offline reinforcement learning (RL) in H-horizon Markov decision processes (MDPs) under the linear q" rralliizzabilyyy assumption, where the action- value function of every policy is linear with respect a given d-dimensional feature function. The hope in this setting is that learning good policy will be possible without requiring a sample size that scales with the number of states in the MDP. Foster et al. [2021] have shown this to be impossible even under concentrability, a data coverage assumption where a coefficient Ceone bounds the extent to which the state-action distribution of any policy can veer off the data dis- tribution. However, the data in this previous work was in the form sequence of individual transitions. This leaves open the question of whether the negative result mentioned could be overcome the data was composed sequences full trajectories. In this work answer this question positively by proving that with trajectory data, a dataset of size poly(d, H, Cconc)/e² is sufficient for deriving e-optimal policy, regardless of the size of the state space. The main tool that makes this result possible is due to Weisz et al. [2023], who demonstrate that linear MDPs be used approximate linearly "rerealizalle MDPs. The connection to trajectory data is that the linear MDP approximation relies on "skipping" over certain states. The associated estimation problems are thus easy when working with trajectory data, while they remain nontrivial when working with individual transitions. The question of computational efficiency under our assumptions re- mains open.
Introduction
We study the offline reinforcement learning (RL) setting, where the objective is to derive near- optimal policy for an !/-horizon Markov decision process (MDP) using offline data. This contrasts with the online RL paradigm, where learners interact directly with MDP or its simulator to collect new data. Offline RL is especially relevant when acquiring new data guided by the learner infeasible or ill-advised for safety reasons.
Deriving near-optimal policy is only possible from offline data that covers the MDP well enough. One way to formalize this as assumption, which we adopt for this work, is called concentrability. This assumption posits that the offline data sufficiently covers the distribution of state-action pairs that are accessible through running any policy. Challenges also arise in MDPs characterized by large or infinite state spaces. In such scenarios, an efficient learner's data requirements cannot scale
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Assumptions
Work
Task
Data
Structural
Result
[Xiong et al., 2022]
π-opt
Amin lower bound
Linear MDP
[Chen and Jiang,
2019]
T-opt
Conc
Bellman complete
[Xie and Jiang, 2021]
Strong Conc
[This work]
Conc & Traj data
q
[Foster et al.. 2021]
TTopp or 7-eval
Cone
q²
[Wang et al., 2020]
π-eval
Amio lower bound
[Jia et al., 2024]
T-eval
Conc
Restricted q"
X
Table 1: Notation is defined as: x-opt policy optimization, π-eval = pooiiyy evaluation, Conc = Concentrability,, q" linear 9" rrealiiizability. Traj Trajectory, V poly(d, H, Ceone, 1/c) sample complexity, x exponential lower bound in terms of one of d, H, Connc.
with the state space size. An approach to remove state space dependence is to assume that the state- action value function of any policy can be linearly represented using d-dimensional feature map, an assumption known as linear q" -realiizabill
While linear q" rralliizabyl facilitates efficient online RL [Weisz et al., 2023], its applicability has been limited offline contexts. For instance, Foster et al. [2021] proves that no learning algorithm can derive an e-optimal policy under linear q" ge-rralizability and concentrability bounded by Coone. with poly(d, H, Coones e number of samples. However, their result does not apply trajectory data, where the offline data contains full sequences of state, action, and reward tuples obtained by following some policy from the initial state to the terminal state. The following problem is left open:
"Does there exist an efficient learner that outputs an e-optimal policy, under the assumptions of linear d" realizabbil,,, concentrability, and trajectory data?"
Our findings affirmatively answer this question in terms of sample complexity, highlighting notable distinction in the requirements for trajectory data versus general offline data for effective learning. This underscores the practical value of accumulating trajectory data whenever feasible.
2 Related Works
In Table we provide a comparison of our result to the other works in offline RL discussed below.
Lower bounds: As we have already discussed in Section I, the work of Foster et [2021] shows a lower bound that depends on the size of the state space (in the same setting as ours), except they do not assume access to trajectory data. The work by Jia al. [2024] perhaps the most relevent to ours. They show an exponential lower bound in the horizon for policy evaluation, under the assumptions of trajectory data, concentrability, and restricted linear q" -raalizability where the value function of only the target policy is linear. While we anticipate that evaluating policies (their focus) is no more difficult than optimizing policies (our focus), our q" realizability for all memoryless policies (Assumption 1), while theirs is restricted to the target policy. Zanette [2021] shows an exponential lower bound in terms of the feature dimension d, under linear qº /e-rralizabilltyy and various other structural assumptions; however, their setting would result in concentrability coefficient larger than the size of the state space. Wang et al. [2020], Amortila et al. [2020] show lower bound that is exponential in the horizon, under linear qº' reaariizzaiil However, they use Amin lower bound condition, which requires a lower bound on the minimum eigenvalue Amio of the expected covariance matrix used for least-squares estimation. This is seen as weaker condition than ours, as it only posits good coverage in terms of the feature space, not the (possibly much richer) state-action space.
Chen and Jiang [2019], Munos and Szepesvári [2008] present efficient algorithms under concentrability and Bellman completeness, an assumption that the Bellman optimality op- erator outputs a linearly realizable function when its input linearly realizable. As linear q" realizability does not imply Bellman completeness [Zanette et al., 2020], these results do not transfer
Upper bounds:

---

to our setting. Xie and Jiang [2021] show an upper bound under linear g" re-rraalizability, albeit, us- ing stronger notion of data coverage than concentrability, which we call strong concentrabillty. The work of Xie et al. [2021, 2022] give data-dependent sample complexity bounds that hold under both Bellman completeness and linear qº -eaaliizabillty even in the absence of explicit data coverage assumptions. Jin et al. [2021] assume general function approximation setring and also provide data-dependent bounds, while Duan et al. [2020], Xiong et al. [2022] show upper bounds for linear MDPs (a stronger assumption than linear q" -realiizabillty [Zanette et al., 2020J) with the Amin lower bound condition.
3 Setting
Throughout we fix the integer d 2 1. Let Ô E IR be the d-dimensional, all zero vector. For L, > 0. let B(L) = { E Rd || I L} denote the d-dimensional Euclidean ball of radius centered at the origin, where || - ||2 denotes the Euclidean norm. The inner product (z, y) for x, E R is defined as the dot product x =Ty y. Let 1 [ be the indicator function of boolean-valued (possibly random) variable B. taking the value 1 if B is true and O if false. Let Mi (X) denote the set of probability distributions over the set X. Let EB-P denote the expectation of random variable B under distribution P. For integers i.j. let [i] = {1, (1.2....
and [i j] (......j.. For a symmetric matrix M E Iædxd we write min (M) and Amax (M) for its minimum and maximum eigenvalue.
The environment is modeled by a finite horizon Markov decision process (MDP). Fix the horizon to H. This MDP is defined by tuple AS,A, P. R). Here, the state space S is finite and organized by
stages: S = Une(Ht+1] Sr. starting from designated initial state 81 (S) = { and culminating
{sT })² Without loss of generality, we assume Sn and Sp for h * H are disjoint sets. Define the function stage S + H + 1]. such that stage(s) = h if s E Sn. The action space A is finite. The transition kernel is P (Une(H)) Sx) x A + MS). with the property that transitions occur between successive stages. Specifically, for any E [H] state Sh E Sn, and action E A. P(s), a) (1( The reward kernel is R. S x A - MI (fo, 1)). So that the terminal state ST has no influence on the learner we force the reward kernel to deterministically give zero reward for all actions E A in sT (i.e. R(ST, (r))=
in designated terminal state ST (S
1 r)). An agent interacts with this environment sequentially across an episode of H + stages, by selecting an action a E A in the current state. The environment (except at stage H 1) then transitions to subsequent state according to P and provides a reward in [0, 1] as specified by R
We define agent's interaction with the MDP through a policy π, which assigns probability distribution over actions based on the history of interactions (including states, actions, and rewards). For this work, we restrict policies to be memoryless, that is, their action distribution depends solely on the most recent state in the history. The set of all memoryless policies is II = {iT π S > (14)). For π II, write T[als) to denote the probability (s) assigns to action deterministic policies only (i.c., those that for each state place a unit probability mass on some action) sometimes abuse notation by writing TTs) to denote arg max,e,4 (a)s)) Starting from any state 8 within the MDP and using a policy π induces a probability distribution over trajectories, denoted as P a. For any E A, P a, is the distribution over the trajectories when first action is used in state 8, after which policy и is followed. Specifically, for some h E [H + 1] and (s, a) E (S x A, we write Traj ~ Pr... denote that Traj (Sn, An. Ra,..., "i....,,HH4.. AH+1, RH+1) for a random trajectory that follows the distribution specified by Fa.s.a that is, Sn 8, An = 0, A; ~ ((;)) for i E [h + 1: H + 1]. S P(S., Ar) for (h- H), and RG R(S,, A:) for i [h: H + 1). Writing Traj ~ P.. has an analogous meaning, with the only difference being that A, is not fixed,
For
'The state space is assumed to be finite to simplify presentation. Our results extend to infinite state spaces. "A deterministic start state 81 is added for simplicity of presentation. It is easy to show that adding an additional stage to the MDP allows for the transition dynamics to encode an arbitrary start state distribution.
A terminal state ST is added purely as a technical convenience for the analysis. We will focus on the interaction of learners for stages ht E [H]] (not [ 1)). since the terminal state will have no affect the learner.
'Here, the reward and next-state are independent, given the current state and last action. Independence is nonessential and is assumed only to simplify the presentation.
3

---

and instead A, ~ (S)). For E [ + 1), we write P (and IP ..,,,.) for the marginal distribution of AA) (i.c., the state-action pair of stage h) under the joint distribution of FR.. (and a.,,)). the notation V:::" (#a)uE(tar)) throughout, except when [[thr)
For stst' I H+ sequence of scalar rewards. In that case, for convenience, we write Tt: Σ nu and
RE = =E= Ry, The state-value and action-value functions v" and q" are defined as the expected total reward along the rest of the trajectory while æ is used:
(s)a for E and q' q=(5, a) 0² (s) Trajo
Ratage(s::H for (s, a) E E A. Traj.Pe,
E
Let n E IT an optimal policy, satisfying q3d (s, = sup+en q" (s, a) forall (s, a) E x A. Let 4² (s, a) = (s, (s,a) and e* (s) = maxaeA 9- (s, a) for (s,a) E A. By definition, we have 0" (ST) = v (ST) =0 0 and (s) q" (8T, =0
for all v E E.
(I)
3.1 Assumptions and Problem Statement
A feature map is defined as ø S x A - B((,) for some L1 > 0. The representative power of feature map for an MDP is described by the following assumption:
Assumption 1 (n,, L2 Apprroxxxxyyy Linear -e-RRelizable MDP). For some 1j 2 0, L2 0, assume that the MDP (together with a feature map o) is such that
max HEll ON, (B(L)) (s.. X
sup min
(s", an) - (Ø(*n, an), 0w) En
for all h E [H + 1].
For any h E H + 1], let th, II + B(2)) be mapping from policies to parameter values On that attain the min in the above display. For h + 1, we restrict this mapping to (H+1(.) Ö. which satisfies the above display by definition. We write ())a())fo
We also make the following assumptions the offline data (the relationship non-trajectory data and the negative result by Foster et al. [2021] is discussed in Appendix B):
Assumption 2 (Full Length Trajectory Data). Assume the learner is given dataset of full length
trajectories' and corresponding features of size 2 1:
"...."""j"""""" and ((o(s); a))e(()).A) (dbsh) a) ())
where for some "data collection policy" E II unknown to the learner, (traj²) ) are independent samples from PT where traj" = (s), ag r()ue To simplify notation we write
di = >6< o2,) for all h E [H),j E [n].
Definition (Admissible Distribution). A sequence of H state-action distributions v= (UN)NE(H) E (Mi(Sa A)) is admissible for MDP if there exists policy II such that Vi (s,,,, a,)) = n. Pht,, an)) for all (sh, on) E S₁ x A, E [H].
Define the state-action occupancy measure of the data collection policy TD μ (WA)ketA) such that
M un) = 1 (sh, an. for all (sh, an) E Sn A, h E [H]. Assumption (Concentrabilltyy) Assume there exists constant Ceone 1, such that for all admis- sible distributions v = (Vi)лε(m)
{ un an)
} S Counc.
max hE[H]
(.).s. x un(sn, (u(ss,,a)) an))
max
Problem 1. Let > O. Under Assumptions 1 to 3, does there exist a learner, with access to only poly(1/c fe, H, Ceone; log(1/5), log(1/ In), log(1/L2)) full length trajectories (as defined in Assumption 2), that oulputs a policy π such that, with probability at least - 8,
v (s1) v" (s1) <e?
*Our learner does not require explicit knowledge of the states within each trajectory: the features alone are sufficient.

---

Result
We resolve Problem in the positive by defining learner (Algorithm 1) that: selects parameters optimistically from modified MDPs that "skip over" certain states while preserving tight q-value estimation guarantees (achieved by solving Optimization Problem 1); then, outputs a greedy policy x' (defined in line 3) over the selected parameters. This result is made formal in following theorem (proof Section 5):
Theorem 1. Let e E (0, H. Under Assumptions I to 3, if the number of fill length trajectories @ dt and r Ó ome H)))) then, with probability least 1 8, the policy n' outpul by our learner (Algorithm 1) satisfies
2* (s1) 1" (s)
where 92, Ô and θ are the counterparts of Ω2 O and + from the big-Oh notation that hide polyloga- rithmic factors of the problem parameters (1/e, 1/5, H, H,d, Ceone, L1, L2)- The following subsections focus on introducing the theory needed to formally present our learner, giving intuition behind our learner, and presenting our learner.
4.1 Background Theory
Our learner relies on the observation due to Weisz et al. [2023] that linearly q" rrealizable MDPs are linear MDPs, long they contain low-range states. The range of state is the largest possible regret from that state, that is, the largest difference in action-value that the choice of action in that state make (up misspecification):
range(s) (s) = supxen ee a, a'), Vstage(s) for all 8 E S
(2)
where (bs a, a') = (18 s a) (8, d') is a notation we use to denote feature differences. Intuitively, the choice of actions in lowe states are unimportant, as
- (s) q" (s, a)l < range(s) + 2m for any II and all (s,a) E A.
(3)
As a warm-up, consider the example MDPs shown Fig. We will transform the linearly -"- realizable MDP on the left into a linear MDP on the right by "skipping over" the red low-range states. Let the features for both MDPs be o(31.) = ((3.)()).)) = (0.5). o(..)) = (0) otherwise. Then the left MDP is (0, 1)-approximmtell q" -r-realizable. with realizability parameter (x) (1) for h E [H + 11, π E II. However, it not a linear MDP, since the rewards cannot be represented by a linear function of the features. To see this, notice that there exists no & such that (Ø(s1, (1),0) 0)
r(s1, 01) = and (0(s1, 02), 8) = r(81, 42) ) = 0.5, since 6(81, a1) = ((s1, 02) = (1). We modify this MDP the left to "skip over" low-range red states, by automatically taking the first available
action at such states, and summing up the rewards along skipped paths. This turns the MDP into the the right of Fig. 1, which is linear MDP.
82
81
0.5
0.5
83
0.5
The features for both MDPs ((s).)) (1), (ss..) (0.5), o(:,)) (0) otherwise. Left: A (0, j-aapproximately qd' -eaarealze MDP. Right: Linear MDP, obtained by skipping low range (red) states in the left MDP. Source: Figure from [Weisz et al., 2023].
Figure 1:
The key fact about linear MDPs that will use is that for any function f S [0, H| (e.g., u-value approximators), and any [L]], there is some parameter 0,, E dd so that for any (s, E S₁ A, (o(s, a), 0x) gives the expectation the reward plus f's value on the next state. In our modified
'The bound on 7) is assumed for clarity of presentation, to avoid presenting two error terms in the final bound.
5

---

MDP this result transfers to the fact that the expected sum of rewards along a skipped path, plus f's value on the next state after the skipped path, is linearly realizable. Before making this result formal in Lemma 4.2, we clarify the skipping behavior.
First, we address the fact that we need an approximate, parametric bound range(-) with param- eter count that is independent of (S]. For / E [2: H. let LA = (T) the (compact) set of parameter values corresponding to all policies. For all h E [2 : ff], fix a subset Go. C VA of size |GA, = do == [4d log log(d) + 16] that is the basis of near-optimal design for V (more precisely, satisfying Definition 3). The existence of such near-optimal design follows from [Todd, 2016, Part (ii) of Lemma 3.9]. Let G = G2.H, which we call the tre guess. Now
E 11} C B(L2) be
notice that G E G where
(4) For G E G we will use the notation that G G2.H, where Gn (dh)e E (L Any G = G2.H E G can be used to define an approximate, low parameter-count "version" range that completely specified by dHHd²) parameters:
G G G-(B(L2)))2H))BB
range
G (s) = max maX., ( a, d'), 0) for all h E [2 H], s E Sn
(5)
As shown in Proposition 4.5 of [Weisz et al., 2023], range can be used to bound the true range:
Lemma 4.1. For all h E [2 H] and s Sn, range(s) S /2d range (s).
Based on any G E G. we are interested in simulating modified MDP that "skips over" states that have a low range (s). by taking an action according to n", and presenting as the reward the summed up rewards along paths consisting of skipped states. This "modified MDP" only serves as intuition, and will not be formally defined or used our formal arguments. Instead, we define the "skipping probability" parameter at state s E S, with a > 0 (set later in Eq. (35)), as
if E Si US and range @ (s) S a/ /2d if & S1 USH+1 and az/ /2d < range S 20/ /2d otherwise.
wa(s)= = 2 22d rangee
0
The skipping behavior is probabilisttc': it never skips for stages 1 and H + 1 (where range is not defined); it always skips for ranges lower than some threshold, never skips for ranges higher than twice this threshold, and linearly interpolates between the two in between the thresholds. For h [H), and 1 < h, let traj = (8t, de, 11) be any fixed trajectory that starts from some stage 1. Let T ~ Am1 E MM : H + I]] be the random stopping stage, when starting from state 8n and skipping subsequent states with probability wa(-). Formally, for t E [h + 1 H + 1]
let (G
t) (1 (G() I wa(ss). We will often write F GA denote
FGmmp, .+11 where traj (s/, of., r2 ( [n].
Next, we present key tool derived from results of Weisz et al. [2023]: as long as the skips are informed by the true guess, the resulting MDP is approximately linear (proof in Appendix C):
Lemma 4.2 (Approximate Linear MDP under the true guess). Let nj 2 0, L2 > Let M be an (n, Lg -pprrxxxxiill linear q" -realizable MDP (Assumption 1) with corresponding feature map ø. Let L2 L2 da/a / + 1). Then, for each : S > [0, H) with f(sT) O, policy a E IL, and stage h E [H), there exists a parameter (f) E ([)))) such that for all (s,a) E Sn x A.
E Traj P
E T FaT
[ + f(S.)] a). Sn
where vj = 2 do/a a [ +1.
4.2 The Benefit of Trajectory Data
Our learner will heavily rely on the result presented in Lemma 4.2. We will need to learn good estimates of the parameters p7 (f), for any f S + [0, HJ, h e [H]. However, to estimate a pl (f)
"The resulting smoothness of skipping behavior is beneficial for later technical covering argument (Fq. (90) in Lemma 1.4).

---

parameter well we will require least-squares targets that have bounded noise and expectation equal to (ó(s, a), P% (f)) for all (s, a) E S. x A. Full trajectory data (Assumption 2) makes this possible.
Each full length trajectory traj' = (st, a². r eetH--1 E [n] can be used to create the following
least-squares target (which has the desired properties):
+ [
Importantly, it is because we have full length trajectories that we can transform the data available to simulate arbitrary length skipping mechanisms.
4.3 Intuition Behind our Learner
Next, we describe the high-level intuition and ideas behind our learner. Consider the "modified" MDP where low-range states are skipped. As the learner has access to trajectory data (Assump- tion 2), it can transform this data accordingly to simulate trajectories from the modified MDP. Any near-optimal policy for the modified MDP is also near-optimal for the original MDP (due to Eq. (3)). Thus, our previous linear realizability property (Lemma 4.2) allows for an offline RL version of the algorithm ELEANOR [Zanette et al., 2020] to statistically efficiently derive near-optimal policy for the modified MDP. Indeed, the optimization problem underlying ELEANOR serves as a starting point for Optimization Problem 1, which
the heart of our learner.
The challenge is that the true guess G that Lemma 4.2 relies upon is not known to the learner. This means that the learner is not given any explicit information of what states to "skip over". To over- come this, we design a learner to output the policy T' (defined in Algorithm 1) based on Optimization Problem where the optimization problem considers all guesses for the possible values of G. For each G E G. it considers the MDP that skips over low-range states when the range is calculated according to G. It then calculates sets Oc, for each stage h, that are guaranteed (with high proba- bility) to include the parameter 4/ (m²)) realizing qT (where Tz. defined in Eq. (15), is the optimal policy in the MDP with skipping based on G). We achieve this by defining Oc,, backwards for = - 1. By induction, if G. stage. then some parameter sequence in the Cartesian product GG,4+1 X ... x Oa, H allows to near-perfectly (up some misspecification error) compute q"c-values of stages h. Therefore, the least-squares parameter based on this sequence will be near the true parameter for stage h. Defining Oa, to be all least-squares predictors for sequences in the aforementioned Cartesian product, and Og. be unions of the confidence ellipsoids around these predictors ensures the true parameter ( (TT) realizing nd for stage h included OC. This argument made precise in Lemma D.2.
OC.H H all contain the desired parameter for their
There are two problems remaining. One is that some values of G considered by Optimization Prob- lem lead skipping over important large- value states, degrading the performance of the best policy T available under that skipping. The other problem is that at the expense of making sure the true parameters included in the sets OG.A. these sets might become large, in the sense of containing parameters that lead to very different predictions. Avoiding the first problem would make b=e (s1) nearly as large as o" (s1). Avoiding the second problem would lead to tight q-value estimators, and therefore to a (s1) being nearly as large as e (s1), for a policy T'G that is greedy with respect to our hypothetically tight q-value estimator. A key idea is to reject from consideration any G e G that leads to g-estimations that are not sufficiently tight (Eq. (14)). The reason we can do this is because for G = G we can show that this condition passes (with high probability). and therefore we do not reject G (precise statement in Lemma D.3). We can show this since have trajectory data (Assumption 2), allowing us to use least-squares targets of the form used in Eq. (12), which we know are linearly realizable when G G (discussed in Section 4.2). Finally, we resolve the first problem by selecting among these tight estimators the one that guarantees the highest policy value from 81, which can be no worse than the value guaranteed by the choice of G = G, which itself can be seen to be close to o² (s1).
4.4 Learner
Next, we formally introduce our learner, at the heart of which lies Optimization Problem We de- fine various q and v-value estimators that we use. For x E IR let clip æ max(0, min x}}.
7

---

Then, for h E [H] Ue E A,0 E R. 00::H+1 = (8h..... 8 0H+1) (d(())++))) let
q0 a) = (0(s, 0),
00nme: (8, = Matageia) (s, a), 10 (8) = max 90.. ++ (8, (8,0), aeA
(7)
(s) = maxueA a),
(8)
go (8, cli (0(8,a);
aomuet (8, (Buanso(a) (8, a)
(9)
(s(s) clip u. (s(s),
voa.H- (5) (Bstngets) (s).
(10)
Optimization Problem 1.
arg max GEG 1. 00.00 Tog (31)
subject to, for all h [M]
X₁ AT + ESEMm (d)))
(11)
H+1
X Σ
E
h + Uo 000 1.#+1 (of) 01+1:1++1 E
X OG, umh+1
(12)
h
T G,++1
jE(n]
0n E B(L2) min 110, - -xllxx S $B]. 0G, {0} 8 defn Eq. (32), (13)
OG.
E Ljenn [max0eOox 20(5 a/)) miingea..... T06h/ o7)) SE
defn Eq. (29). (14)
Let (G',0..H+1) denote the solution to Optimization Problem 1. Notice that unlike ELEANOR, we optimize over all G E G. which can be seen as an optimization over all possible "modified MDPs" with different skipping mechanisms. Another observation that apart from h 1, the choice of 0/ from Ocr, made by the optimization is arbitrary. Indeed, unlike ELEANOR. which chooses globally optimistic least-squares predictors for each stage, our optimization does not need to care about (or optimize for) the specific choice of q-value predictors from their respective confidence sets Q,, We can be agnostic to the choice of q-value predictors because all choices lead similar predictions due to Eq. (14), as will be shown formally, in Lemma 5.1. However, fixing an arbitrary concrete choice in the optimization allows us to define an output policy x' that is parametrized only by these vectors, making both the memory and computational requirements of representing and executing x' small.
Our learner (Algorithm 1) solves Optimization Problem and uses 01 to output greedy policy,
Algorithm 1: Learner
1: input: accuracy e > 0, failure probability > O, concentrability coefficient Cemee < 00, trajectories (traj² .r..,,taji traj")) features ((ő(s) (()(=),.)))e]]).cco.. s)..e................. hon norm bounds L1, L2.
2: G',0'.H+1 <- solution Optimization Problem
3: (alss) + ifa = arg max,'EA 9o (essene (s, d) for all (s. ESXA
4: return
5 Proof of Theorem 1
Before giving the proof, we formally define the optimal policy in the modified MDP that skips c. for any G G
according to range
(als)) T (s)s)w((()) + 1fa arg raggaxrrea" (s, a') (s)
(15)
Notice that for states s E S₁ for some h E [H]. (-1s)) in the above definition depends on the value of a (s'. for some s' Sh+1- We can therefore interpret the above recursive definition as H + 1, then
defining (-1s) for Sn, first for we define the policy for some stage in such a way, the policy and á (s'.)) are already defined on later stages, making the definition valid, and resolving the recursive nature of Eq. (15).
H. etc., down to h Every time

---

Proof. 1* (s1) (51) can be decomposed into the following error terms.
00(11) - o" (s1)
v² (si) ( + (s1) vo; (81) + Vo (81) v (51)
(1)
(II)
(II)
The remainder of the proof focuses bounding these error terms. Following the intuition described in Section 4, showing that terms (I) and (II) are small can be seen as addressing the first problem of potentially skipping over large-value states, while showing that term (III) is small can be seen as addressing the second problem of n' being greedy w.r.t. to a potentially inaccurate estimates (114+1
Bounding (I) v 0T (s1): This term cannot be too large since the range function is ap- proximately correct (Lemma 4.1), and we only skip over states with low range (Eq. (6)), implying the action we take doesn't It affect the value function much (Eq. (3)). In Appendix D.1 we formalize this intuition, and show the following result.
(I) 20 (s2) (s1) & H + 27)
(16)
Bounding (I) = (s1) 5o; (51): This term can be bounded by approximately zero due to Optimization Problem I being optimistic from the start state. First, note that wn is approximately equal to (Tg) (Assumption 1). Then, in Lemma D.2 we show that Φ (TT)) E @ and in Lemma D.3 we show that G is feasible solution to Optimization Problem 1. Since (G',8',u (1. is the solution to Optimization Problem 1, it holds that Jor ($1) 2 (01) for any 0 E θG,1 where G is a feasible solution to Optimization Problem 1. Thus oo (81) 2 (rg))))) In Appendix D.2 we formalize this intuition, and show that with probability at least 1 - 6,
III à ooz (81) 511
(17)
Bounding (II) = Eog (81) Tr (s1): ): To bound term (III) we will first show in Lemma 5.1 that value estimates in terms of 8% and via (=ăr) are close with high probability for all h E [H + 1]. This lemma allows us to relate Uoy to (1g.) and then Assumption relates (xg.)) to v We are then left with relating o to v².. To do this we claim that T' is an approximate policy improvement step w.r.t. o which can be seen by recalling that x' is greedy w.r.t. Te, m+1 and as we mentioned a couple sentences ago, Ügg and (on((g))) are close for all h E [H + 1].
To formalize this intuition we begin by decomposing Tog (81) - v= (s1) into the following error terms
Toy (31) (s1) = To; ($1) - (1 ($1, T' (s1)) + Te (=zz)) (51 (s1)) - vz (s1). (18)
To bound ū0; (81) - Tvi( (81, T' (81)) we introduce a useful lemma (proof in Appendix F).
Lemma 5.1. There is an event E2, that occurs with probability at least 1- 8/3, such that under event Ez. for all G E G that are feasible solutions to Optimization Problem 1, for all h E [H]. for all (sa)E) A and (Bsa)(ss))Ssxx (De)ee(m, holds that
S.A.A. for all admissible distributions
E (8,A)-iA
(S,AA
T0,, T0,0,, (S. E
È defn Eq. (30).
To use Lemma 5.1 must show that üeg (81) (o1(( (81, (001,,7(())) (s1)) satisfies its requirements. First, note that Tog (51) = Zo: (#1,7' n' (s1)). by definition of x' (line 3). Second, G is the solution to Optimization Problem 1, thus, feasible solution. Third, by Lemma D.2, there is an event & which occurs with probability at least 1 18/3, such that under event E1, t/1 ( E OG and by definition 8 E OG.,1 Let (s, a) = ,, (s, for all h E [H], (s, a) E Sh x A. Clearly v = (Mi)eem is an admissible distribution by Definition 1. Thus, under event E₁ Ez by Lemma 5.1.
Ter (s1) - (02 x' xs())) = E
Toy (S, A) Tor( ( (S, A)] <τ.
(S.A)me)
9

---

TT (s1)) 0" (s1) in Eq. (18). To do this, first note that It is left to bound (vi(=T))) ( ($1:
Per (rgg) (51, T (s1)) v"' (s1) S ghà. ($1, x'(s1(())))))))))))) v"' (s1) +7.
where the inequality holds since we have approximate linear geareiiizability (Assumption 1). To bound qn ($1, II (s1)) vt (s1) notice that v" (s1) = q"h (s1)), which implies that gr ($), ( v² (81) nt (51, (81) qp' (81, T' (81)
E
O (S2) 6²' =52
Tha
Next, we give a bound on Ennj-P p(ez Tot' (S2) - v² (52) (proof in Appendix D.3):
Lemma 5.2. Under event & n E2r any h E [2: H + 1]. it holds that
E
(T - (5h) s 2(H + 2)
Trajo
Intuitively, the above lemma holds since n/ can be thought of as an approximate policy improvement step w.r.t. w To see this, recall that x' is greedy w.r.t. 40; (line 3). Then, with Lemma 5.1,
can show veg and (xg, ( (which is close to u (Assumption 1)) are close for all h E [H + 1]. The above bounds imply that under event & n E2, which occurs with probability at least 1 25/3.
(II) ūog (#1) - v" (s1) S ( + +) +
(19)
Combining the Bounds: To finish the proof we combine the bounds on all three terms (Eqs. (16). (17) and (19)), to get that under event E n & n &g, which occurs with probability at least 1 6,
v² (s1) ot' (s1) - H22a + 2n) + + (H + 2) + ? 4(H + 1)(a + 2).
To bound the above display by e we set a = (/2 1)) 1. In = @ H /e2) and 7 ò (0 ( (nHf (Eq. (26)), we show that = Õ H /n) (Fqq. (44)). This implies that
4(H + 1) ce
Limitations and Conclusions
In this work we resolved an open problem in the positive, by presenting the first statistically efficient learner (Section 4.4) that outputs a near optimal policy in the offline RL setting with approximate linear qt rrearizabbillty (Assumption 1), trajectory data (Assumption 2), and concentrability (Assump- tion 3). One limitation of this work is that we are not aware of any computationally efficient imple- mentation of Optimization Problem 1, which is at the heart of our learner. As such, it is left as an open problem whether computationally efficient learning is possible the setting we considered. Another limitation is that we not sure if our statistical rate in Theorem I is optimal. Showing matching lower bound or improving the rate is left for future work.
Another limitation of our work originates from our setting underpinning our result (Section 4), namely the three assumptions: approximate linear qa reariiiizabil trajectory data, and concentra- bility. Approximate linear -e-rellizability requires the value function of all memoryless policies to be linear in fixed and known d-dimensional feature map. While strictly weaker than the linear MDP assumption [Zanette et al., 2020], this assumption is still strong. Trajectory data requires full sequences of interactions with an environment to collected by a single policy. For long horizon problems this can be practically challenging. Concentrability requires the state and action spaces to be well-covered. This can be challenging to guarantee since often the state and action spaces are unknown at the time of data collection. Further, since require the trajectory data to be collected by a single policy, it may be the case that no single policy exists that covers the state and action spaces well, and mixture of policies must be considered, which our current result does not imme- diately hold for. Although the assumptions appear strong, a justification for them is that under many variations of weaker assumptions (for instance: general data, or linear of re-arlizabblltyy of only one policy, or only coverage of the feature space), polynomial statistical rates have been shown to be impossible achieve by any learner (Table l).
Since this work focused on foundational theoretical research it unlikely to have any direct and immediate societal impacts.
10

---

References
Y. Yadkor, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
P. Amortila, N. Jiang, and T. Xie. A variant of the wang-foster-kakate lower bound for the dis- counted setting. arXiv preprint arXiv:2011.01075, 2020.
Q. Cai, Z. Yang. C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
Chen and N. Jiang. Information theorreti considerations in batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019.
Y. Duan, Z. Jia, and M. Wang. Minimax-optimal off-policy evaluation with linear function approxi- mation. In International Conference on Machine Learning, pages 2701-2709. PMLR, 2020.
D. J. Foster, A. Krishnamurthy, D. Simchi-Levi, and Y. Xu. Offline reinforcement learning: Funda- mental barriers for value function approximation. arXiv preprint arXiv:2111. 2021.
W. Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffiding, pages 409-4209400 4299-426.11 1994.
Z. Jia, A. Rakhlin, A. Sekhari, and C.-Y. Wei. Offline reinforcement learning: Role of state aggre- gation and trajectory data, arXiv preprint arXiv:2403. 17091, 2024.
Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline rI? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021.
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
M. J. Todd. Minimum-volume ellipsoids: Theory and algorithms. SIAM, 2016.
R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
R. Wang, D. P. Foster, and S. M. Kakade. What are the statistical limits offline rl with linear function approximation? arXiv preprint arXiv:2010.1 1895, 2020.
G. Weisz, A. György, and Szepesvári. Online rl in linearly qpi-realizable mdps is as easy in linear mdps you learn what to ignore. arXiv preprint arXiv:2310.0781/ 2023.
T. Xie and N. Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pages 11404 11413. PMLR, 2021.
Xie, C.-A. Cheng, N. Jiang, Mineiro, and A. Agarwal. Bellman colssan-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694 2021.
T. Xie, M. Bhardwaj. N. Jiang, and C.-A. Cheng. Armor: A model-basee framework for improving arbitrary baseline policies with offline data, arXiv preprint arXiv:221 1.04538, 2022.
W. Xiong, H. Zhong, C. Shi, C. Shen, L. Wang, and T. Zhang. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint arXiv:2205. 155152 2022.
A. Zanette. Exponential lower bounds for batch reinforcement learning: Batch can be exponen- tially harder than online rl. In International Conference on Machine Learning, pages 12287- 12297. PMLR, 2021.
A. Zanette, A. Lazaric, M. Kochenderfer, and E. Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989, PMLR, 2020.

---

Appendix
A Parameter Settings and Notation
(CCom H. H'dd d 2
n =6
Set at the end of Section 5
(20)
dg 4d log log(d) + 16
Defined above Eq. (4)
(21)
L1 Upper bound on 2-norm of features ø
Defined above Assumption
(22)
L Upper bound on 2-norm of true parameters vh, h E [H]
Assumption 1
(23)
L2 22(8H2dg// +
Defined in Lemma 4.2
(24)
V // is
Defined in Eq. (57)
(25)
H3/2d
7 do 1
θ
VnHl
6
C 11
Defined in Eq. (59)
(26)
11322d
7 (100H1 do/a 1) =
Defined in Lemma 4.2
(27)
n
= (dd/Vn)
Defined in Eq. (72)
(28)
5/2 5/2
Defined in Eq. (51)
(29)
Vn
H5/2
ē
Defined in Eq. (44)
(30)
Vn
3 Ō H2(22)
Defined in Eq. (77)
(31)
8 = δ H2)2d)
Defined in Eq. (58)
(32)
1C (1 +
E> 0
Defined in Lemma I.4
(33)
14 22H2dH22 L (27ita . 0
Defined in Eq. (88)
(34)
12(H <1
Defined at the end of Section 5
(35)
12

---

B Trajectory Data vs. Non-Trajectory Data
To compare the two types of data, we first define "non-trajectory" data, which consist of individual transitions without any guarantees of them coming from complete MDP trajectories.
Assumption (Non-Trajcctory Data). Assume that for each h. E [H) the learner is given a dataset of transition tuples and corresponding features of size 2 1:
(sh 0 "1 8 hh-1)sE(m) and
where ()) Th R( a.),,, h+1 ( ~ P(5), d.)). for all j E [n], and pl E Mi x A)
is a "data collection distribution" unknown to the learner.
There are two differences between the above non-trajectory data and trajectory data as defined in Assumption 2. In particular, if n/a- = -P 79,0, and 8/ 2 then we get back the trajectory data assumption.
Foster et al. [2021] showed a negative result under Assumption 4. Our method addresses the hard instance from [Foster al., 2021] if the data is given as complete trajectories. Below we explain why the lower bound constructions from [Foster et al., 2021] break down if they need to use trajectory data, and why our algorithm breaks down if it doesnt have trajectory data.
The lower bound constructions in Theorems 1.1 and 1.2 of [Foster et al., 2021] were both made hard because the data collection distributions of individual transition tuples (s, a, r, 3) were selected such that they reveal no (or almost no) information about the MDP instance. In both cases, receiving samples from the joint distribution of the entire trajectory Fa makes the problem easy. In the case of Theorem 1.1, one would simply observe which states are reachable from the start state (the planted states). For Theorem 1.2, some information on whether any next-state is planted or not would be leaking in each trajectory, in the form of being able to observe the next-state transition from exactly
simpler example showing the root of the problem with non-trajectory data is as follows. Consider the toy problem of learning the value of some policy π after taking action in state $1 in 2- stage MDP. The data is given as tuples of the form ($1, a, rl. $2...., a, rf, 35) for the first stage and (sh, ah, r2, S] ................................ $2, az. r2, 53) ) for the second stage. Notice there is no guarantee that si ~ P(s1,a) a) with j [n]. We cannot infer what the rewards from the second-stage states distributed as P(s1,a) a) might look like from the data, making this problem hopelessly hard. In the extreme, the MDP might have infinitely many second-stage states, with the probability of any &y s (for any j and k) being 0, highlighting that one cannot just connect and importance weight matching next- states 82 of the first-stage transitions with matching start-states s of the second-stage transitions. In contrast, if we assume the data is such that 3/ szz this problem is immediately avoided as samples from ((11, a), along with rewards from those states are directly handed to the learner. The learner can then simply use all of the rewards rá from tuples that contain the action (s²)) (which we have on average at least 1/Coomc of, due to concentrability) to estimate the value of policy π after taking $1, a (solving the toy problem).
Now consider our algorithm if we do not have trajectory data. In this case we are no longer able to construct least squares targets of the form needed make use of Lemma 4.2 (discussed in Sec- tion 4.2). This means that we would not be able to guarantee that our targets are linear, even under the true skipping mechanism G, implying that G might not be a feasible solution to our optimiza- tion problem. Then our optimism argument that the output of the optimization problem has a value estimate at least as large as the value estimate based on G would no longer hold, causing our whole proof strategy to break down.
13

---

C Proof of Lemma 4.2
Proof. We follow proof technique introduced in [Weisz et al., 2023]. We start by quoting their definition of admissible functions and their admissible realizability lemma.
Definition 2 (Definition 4.6 in [Weisz et al., 2023]). For any h E [M) f: Sh - IR is o' a'aadmissible for some a' for all s E Sn, If()) I range(s)/a'.
Lemma C.1 ddmissible-realizabiin (Lemmaa 4.7 in [Weisz et al., 2023])). If Sh. + R is a'- admissible then it is realizable, that for all t E [h and π E 11, there exists some E R with
|0 S 4dg I2/ such that for all a) E E A.
E TrajoPP...
f(Sh) ( (() 0)
S 170
where nj 5don/a'.
Next, we fix some f S + [0. H with f(ST) O, and policy x E II. For 2 < h 2 H + 1, define Ih Sh H, H] gH+1 0, and
gn (8)
E
E
+ [(++)
Tri F.. T F.F.ta
E
REB + f(S:))( - (e() II we(S w=h
TrajePr.t
t=h
Notice that for any h E [H], (8, E Sp x A, the function of (8, a) we aim to linearly realize can be written
E
E
[ + f(S-))
E Traj-Pa
(1+1(Sn+1) + Ry:H
Traj
(36)
E gh+ (S++1) + q" (s,
Skt1~P(s,a)
The second term of the sum, (s, a) is linearly realizable by Assumption I with parameter th (T). The first term needs more work before Lemma C.1 can be applied. To this end, for E [2 H] we define 9h St + R as
(s) = (1 wa)))
E
[-RA H + f(s) - (S
Notice that Hr be decomposed into sum of 9t functions for all [2: H), Sn.
9n (s)
E
Σ (S.).
(37)
Traje
t=b
The benefit of decomposing Ih into It functions is that dr are a'-admissible under Definition 2 for a' a/(2H). To see this, note that for any trajectory and 8, - Rh.11 + f(x) g (Sk+1) e | 2H). sc(s) multiplies this by 1 wg(s) which by Eq. (6) is between 0 and 1, and satisfies 1 (s) = 0 if range (s) I a/ /2d. By Lemma 4.1, range(s) I /2d range (s), (s() 0 for any with range(s) I a. On any other s, [.)] & 2H. Therefore Jr a -dmissisible. This
allows us to use Lemma C. to get that for any h E [[-1]] there exist 0 E ((SHooLs/a)t such that for any stage [h + H), for all (s, a) Sh. x A.
E Traj-Pe.
(c,))) ()(s.a).0,) 0.) 10Hdon/a.
By combining this with Eq. (37), for all E [H] there exists Ō Et O. with Ō B(8H2 12/ such that for all (8, E Sn x A, Th+ (Sx+1) (((s. <
E
Sat1~((a.a)
Combined with Eq. (36) and the parameter (T)(T) from Assumption 1, there exists = Ø + (T())) with 0 B(L2(8H12d)) do/ 1)) such that for all (s, Sn x A.
E
E
[ S(S.)) (0(s, a), < v/(10/ 1)
Pr...
To finish the proof, we define Pj, (f) = 0 for the arbitrary h [H]. म. and f picked above.
14

---

D
Results used in Section 5
D.1 Bounding term (I)
We begin by defining an alternative policy =
= x (als))a +
This policy can only be worse in value than a Lemma D.I. For all E E.
(s) 2 (s).
Proof. We prove by induction for h + H..., that for all Sh, (=) 2 (s). The
base case of h = H + 1 is immediately true by definition as v-values are 0 on ST, regardless of the policy. Assuming the inductive hypothesis holds for h 1, we continue by proving it for h. Let (8, a) E Sn x A be arbitrary. Notice that
(s, -s,
E StnP(s.)
6 (S') 2 0,
where the inequality due the inductive hypothesis. Next, for any E Sp, by the above and the definition of the policies,
3 (+) = ws)))
E (s)
nd Ax) A) (1 (1 - wo())) max o Te (8,a))
aEA
2 (s)(s) (s)
E
f-c (s, A) +(1 (1- wa() max max ( (s,
aEA
2 ws( (s)
E
('c A) (1 wo()) E
A) ()
AmTi((s
finishing the induction.
Due to Lemma D.1, ot (s1) (81) S 0*( - (s)). We continue by bounding ef (81)
o
( (s1). We first decompose it using the performance difference lemma (Lemma J.3) to get that
H
(*1))) - u
Σ
E
(Sh. An) - (5)))
(38)
An)
h=2
where we only have the sum from h = 2 to H, since for h = 1 and h = H + 1, for any 8 E Sp. (s) 0 and therefore (5) xs). By the definition of we (Eq. (6)),
that for G (s) S 20/ 22d Thus, the policies x (s) and (s) are equal for all s that satisfy range (s) 2 20 /2d. Making use of this result in Eq. (38), we get that
s E ( ef only when range
E An 2
(Shn, An) -b)
h=2
[rannee (Sh) s 2a/V22/ ( (sh, - (sh))
E (P..
By Eq. (3), we know that
(s,a)) - (s) < range(s) + 21
Then, we can use Lemma 4.1 to get that for all h E [2: H and (8,a) E S₁ x A
(s, - s 22 range (s) + 2m.
15

---

Putting things together we get the following bound.
(I) S 0² (81) - (s1)
S v² (81) - (s1(s)
E
1 Frange = 2a/v2d (r)
(
h=2 (A A
$ H (2a: + 27)
D.2 Bounding term (II)
To bound (s1) - Tog (81) we decompose it into the following error terms
d (s1) oog (81) = (81) - (x)) + (01())) 000 (81) I (1)( (81) Vog (81) + 1/:
(39)
where the inequality holds since we have approximate linear qº' realizabbiliy (Assumption 1), which implies that
(s1) (()((g) I max gra (s1, (v)(rg)(s),a)) sn. aEA
To help us bound T (=z) (5)) ( - Dog (s1) in Eq. (39) we make use of two lemmas. The first is the following (proof in Appendix E).
Lemma D.2. There is an event ε which occurs with probability at least 1 - 8/3, such that under Ex, for all G G and h [ 1), it holds that the (TT) E AG
Lemma D.2 tells us that under event E₁, th1 (TT) E 0a.1- The second lemma is the following (proof in Appendix G).
Lemma D.3 (Feasibility). There is an event & n &2 n Es, which occurs with probability at least 1- 6, such that under event & n E Es, the true guess G is a feasible solution to Optimization Problem 1.
Notice that since (G', (G),0).444) is the solution to Optimization Problem 1, it holds that Eg; (81) Z (a())) for any 0 E Og,1 where G a feasible solution to Optimization Problem 1. Thus, we get that under event & && n E3. since t (TT) E θ (by Lemma D.3), and G is feasible solution to Optimization Problem 1 (by Lemma D.3), it holds that
((((())(11) 000 (81) S 17,
which together with Eq. (39), implies that
(II) = 0 - T0g (81) S n
D.3 Proof of Lemma 5.2
Proof. Recall that (G', (T.F++ ) is the solution to Optimization Problem 1. We aim to show that under event E n &g, for any h [2: H 1), it holds that
E
v (Sx) - v. (5h) S 2(H - h + ē).
(40)
Trajo
To prove Eq. (40) we will use induction. The base case is when h H + 1, which trivially holds, since of (BT) = T u) = 0 for all π E II, 8T E SH+1, A.
Now, we show the inductive step. Let h E [2: H] be arbitrary. Assume that Eq. (40) holds for any t h 1 H 1]. We prove that Eq. (40) also holds for h. For any (s, (S),)) x A, let
(a(()) if stage(s) n (a(s)
(a|s)) =
if (s) # h.
16

---

Then
E
vt (Sp) - -0 (Sm)
Traj"P s/
E
qr (Sh, x'
E
(Sh:
Pn
g¹00l An) - 40g (Sh. An)] + E
Doy An) TaiiPP Doy (Sh,
Traj-P 10.
TrajPFnni
E Tai
90% (Sh: An) 05 Anl]
E
("t An)) -9" (Sh, An)
(Sh.
Tmi
(on( (Sh, An) - R0r (Sh. And]
+ Trag
E
dog (Shi - E
gog (Sh, And)
Trajo ain
TrajuPP'..
E The TrapPPrtey
dog (Sh, An) ( (S AnD
E Traje
(S An) (8 (Sh: An) + +211
(41)
where the inequality holds since have approximate linear q" ""-realizability (Assumption 1). To bound the first and third error terms above notice that under event & by Lemma D.2, we know that pin ( OG .-- We also know that 0', E O A.s by definition. Let iu (Sa; (,5u;a,) an) Py Sr.es (8uy au) and (5, an) ss (Sus a.) for all [H], (Su; a.)) S,, A. Clearly, E (Pu)ue Hi] and v' ne()) are admissible distributions, by Definition 1. Notice that we have satisfied all the conditions to make use of Lemma 5.1. Thus, under event E n Eg it holds that
E Traj-PPaain 1i
ben (Sh, An) - To; (Sh. An)
E (Sh.An)vB
( (Sh, An).An) - T0, (Sh, And S Eē.
and
E Traj 2/1
for (Sh, Iva (rg (S: And]
E (nnrA
Tog (Sn, An) Avn (= An) S E.
The term Ergje-Pa dor (Sh, An) E ErajePt Jot, (Sh. An) ) in Eq. (41) can be bounded by recall- ing the definition of nt (s) (line 3), to get that
E Traje 1
q0, (Sh, An) I max aEA
To, (Sh, a) = Tri-PP
E
dog (Sh. An)
Under event & n &g, after plugging the above bounds into Eq. (41), we have that
E Traj-P, Mi
1T (Sh) - 0= (Sii) <
E Ta
oo (S q=¹ (Sh. And + 2n + 2E
E Tnj
v (Sh+1) -
xt (Sh+1) + +2n + +2n+
2
< 2 2) + ē)
where the last inequality holds by the inductive hypothesis for h (Eq. (40)), completing the proof of the claim.
17

---

E Proof of Lemma D.2
Proof. We will prove the claim using induction. The base case is when h H + 1, for which (=+1(T) 0 for all x by definition. Thus, for all G E G, it holds that #4+1 OG, = {0}.
Now, we show the inductive step. Let h E [H] be arbitrary. Assume Lemma D.2 holds for any t t h + 1: H + 1]. We prove that it also holds for h. Define
(
E
[ ( (s))
jEIn]
G1+1
By the inductive hypothesis we know that for any GEG
( E 0a,h11 x ... 0a,
Thus, (TT) E θG. is left to show that (T)(T)))))) 2 (T()) xn.
S, which together with the
fact that tha (m)) E B((2)) implies the desired result, ( E AG...
We would like to make use of Lemma H.1 to bound ( ()((T()
To do so, we map the
X
terms used in the Lemma H.1 to our terms as follows
n. A X, 0, 1/n (= = Xn. 0 (n(=
(0%)
jE(n]
Y
y Y
(0 ((ho)) JE(n] +
Phot- + U (oanmmlag (s))
T Fn-ldi
jE(n]
7
E
hhr-1 +
Dw ( (1(()
E
E
Bhi--I + Daan 1 (ann(())(s))))
Tnj-
To Fa.na
SEln]
A
E
E To Fa.
+ (1 - ( (h(t)((())) (T²)
TrajouP o0
jE
6 = Σ
W + B B (st)
E
E
R + m (8.)))
Trajo-FF 20,0%
Tne Am
jE[n]
With the definitions as above, applying Lemma H.1 get
( wa(mr)) I (Vllsa(TTall + 11 vn 11llxx1
(42)
The first term in Eq. (42) can be bounded by H3/2d by recalling that Vī H3/2d/ (Eq. (25))
and (*)))l < L2 < Lz.
The |ا in the second term in Eq. (42) can be bounded by first decomposing the error, and using a triangle inequality as follows.
( - max g (S,..0)) (
| S
E Po.maat
TrajouF
a'EA
D
jE(m)
Rhit-1 + max max ( (S,, - -(0h 2bn (T(T)
TrajoFF
of m
a'EA
jE(n]
(43)
For the first term in Eq. (43), notice that
P (1()) max 9 à (Sr, a') < max a'EA
(o(S), (stane(s.) (l..ss..).nnneesssss))) (t, S n,
a'EA
18

---

where the last inequality holds since we have approximate linear q" -eereliizability (Assump- tion 1). To bound the second term in Eq. (43) notice that by the definition of mG (Eq. (15)), arg EA (",
exactly the action gद would take at the stopping stage т, and that the distribution of Traj under policy TO until stopping stage same the distribution of Traj under policy T until stopping stage This implies that
E Taaju n0 1z
RETT- + max y gró (Sx. - (0hhsta(rt)
notht
jE(n]
- (0t at) (oh jE(M)
-
where the last inequality holds since have approximate linear q" q"-realizbiility (Assumption 1). Plugging the above bounds into Eq. (43), we get that || S 2n.
To bound the third term in Eq. (42), let the event & be as defined in the proof of Lemma H.2, which occurs with probability at least 1 - 6/3. Then, under event &,, the third term in Eq. (42) can be bounded by 3 (Eq. (31)), by applying Lemma H.2 since (1+1) E ((22) H- C ([2)) H H-h+1
Plugging the three bounds above back into Eq. (42) we get that, under event & it holds that
S (T²) (T()
- H3/2d - 2 + 3 B. x,
where B is defined in Eq. (32), and the last inequality can be seen hold by plugging in parameter values according to Appendix A. Thus, under event E,, which occurs with probability at least 1 1 5/33, for any G E G and h E [H] holds that th (TT) Og which completes the proof.
19

---

Proof of Lemma 5.1
Proof. Let G G be feasible solution to Optimization Problem 1. By Lemma I.1, there is an event Ez, that occurs with probability at least 1 6/3, such that under event Eg, for all G E G, and for all h E [H], it holds that
E (S,A)epp
max A)
min (0(5,A) BEBc.
1
Σ iE[M)
max (0(5 og)) PEBG.
min T0(5) ah)) 8E9a.
PE9G.
H
log
+ 2LE
where |CE Lig, are defined Eqs. (33) and (34). Let h [H]] Recall that since is a feasible solution to Optimization Problem we know that Eq. (14) passed for Thus,
Σ
max (0(5) a BEBG,
min BE@G.
go(s), ah)) SE.
(E(M)
Combining the above two results, we have that under event &2, for any h E [H], it holds that
H
6H C
E
(S, A) BEBc.
max
min To(S, A) 6E9G,
log
2 +
(8.A)~AA
n
Now will relate the data collecting distribution fa any admissible distribution v. Notice that by the definition of max and min, for any (s, a) E x A. holds that
max ( a) min (s, a) 0. #E9c.,
#g0c.h
Thus, we can apply Lemma G.4 to get that under event &g, for all E [H]. and admissible distribu- tion (V))E[(H) holds that
6H C
E
max To (S, A) min (S) OEGG,
S Ceome
log
+ 2Lg +
(8.A)mm
BEBo,
To conclude, we have that under event &g, for any G G that is feasible solution to Optimization Problem 1, for any E [H], for any (fs.a) xA and (6. ()..)) x. with 0..a 0,.a E Og,6 for all (s,a)= E Sn x A. and for any admissible distribution v = (4))E(H), it holds that
E A)
Tos.A (S, A) Abs.A (S, A)
E
max (S, A) DEDO,
min (S, A) 0E
(S.A)mMA
H
GHICE
Ceone
log
2
Vn
H
6H + 2L2/ (22
+ 2d12 (2v
"
< Coono
log
+
H
66
< Ceanc
d log 21 (/ + log
+ In
+
Vn
= ò
+
Coone
H5/2
=
-
C2 Commm-t1/22 5522d
(44)
Vn
Vn
Vn
Vn
The third inequality holds by plugging in the values of IC& Lgg defined in Eqs. (33) and (34).
The last inequality holds by setting {-1 24 2dv/d Lia (2( two equalities hold by plugging in parameter values according to Appendix A.
The last
20

---

G Proof of Lemma D.3
Proof. To show that G is feasible solution we need show that Eq. (14) is satisfied for all [4].
By Lemma 1.1, there is an event &2, that occurs with probability at least - 6/3, such that under event Ez, for all h [H] it holds that
1
Σ
max To (8 pEec,
min @0(h): BE0c.
ah)
IE
max (o A) min To A) pE0c,
n iE(M)
(8,A)~mu
H
log
+ 2L....
(45)
n
where ICE L.g, are defined Eqs. (33) and (34). Let [H] be arbitrary for the remainder of the proof. We focus on bounding (s),)) maxseec... To A) minsgee.,. (o(S, A) for the remainder of the proof. The following lemma will be helpful (proof Appendix G.1).
Lemma G.1. There is an event E,, that occurs with probability at least 5/3, such that under event for any (s) E Sr A, A,0, G it holds that
f0, (s, (s) 23
E Traj-Pr.naa
Σ t=h
min 1, 11, A0)lx; + (H + (46)
where, for any (s', A.
i(a's)) n (d)(sss))a((s'))))))))))))))))") + 1 arg max (s',"
- d' (sta")== (1- (1-w5()))),
(47)
a"EAA
and g" is a state-action value function of policy (similar to ), except in the alterna- tive MDP that has the same state and action spaces, and transition distributions as the orig- inal MDP under consideration, but with reward function modified as follows. For all (s',a') ES x A. the reward in this alternative MDP is deterministically m, (:)ló(('''')lxxxx" d')l (Le. a') = {min {1, (1l x0)xx)=)))
In particulla for any h' E (H, E Sp.XA xA
H
g" (s',a''=
E
Σ t=k'
min
(1in(1,,1d
(x), A
(48)
Tra Tra Pe
The recursive definition of can be interpreted in the same way as described below Eq. (15).
Let से be as defined in Lemma G.1. Then, by Lemma G.I, under event & it holds that
E
max @o (Sh, min To (S An) AE
(Sa.An)
Jap
E
max To 7o(S (Sh, AA) BEBc,
o (Sx) + (Sa)) BE0c.
min (S,, An)
H
<
E
48
E
Σ
min 1, A.ll:; + 2(H + 1)
Trij
Pai
AA
tm
"
43
E AM
min 1, (|@ AN)lx; }
48
Σ t=h+1
E (SurA))ma (SuA A
E
min 1, min
(1,1,, Ac)
+H (H-h+ 1)77
(49)
The inequality used Lemma G.I. As we will show shortly, the first term can be bounded by Lemma G.3, since its expectation is taken w.r.t the data collecting distribution μ.. Thus, the ap- proach we take to bounding the second term is to relate its nested expectations to just be a single
21

---

expectation taken w.r.t the distribution (similar to the first term, which we claim we know how to bound). To this end, for any (s',a') E S A. define the policy nn as
[ (a'(s") if stage( s - h (((a' if stage (0'g h.
nn. (a'1s')
Notice that for any 1 [M], (1 1 H + 1}, (s, I (s..AA))PP s, (.)
Let (8,, au) = Pa sg (8u; a.) for all u E [H], (Su; an) E S. x A. Clearly, i = (Ru)ue(H) is an admissible distribution by Definition Thus, with the definition of is and using Lemma G.4, we get that Eq. (49) is
= =3 (mh
E
min 1, (0o AN)lx, } 43
Σ
E (Seree)-Ph
min 1, |lo(s,, Aullx, } (1 h 1)7
t=++1
443 E
min
S 1, (k, AnDllx; + 4Coone
Σ
E (Se.A))
min 1in(1,1lo(S,, A.)l (,),l + (H h 1)
(=h+1
H
4Coon
Σ t=h
E (Se.Ae)mpp
ming 1, 1, Ab)llx {
+ (H h 1)7.
The last inequality used that Ceone 1. Finally, As) min 1, (1, Ac)ll In particular, let Eg be as defined the proof of Lemma G.3. Then, by Lemma G.3, under event E3. it holds that
apply Lemma G.3 to bound
H
4C 3
Σ
min 11 A 4Coone Σ Es 4H cunc
(Se.Ae)mup
Putting all of the bound after Eq. (49) together and plugging them into Eq. (49), have that, under event E n &2, holds that
max (Sh, An) - min (Sh. And s - h 1) 4HCoone2B. BE0c.
E (Sn.An)
(50)
6E0c.
are now ready to state the final result. Noting that h E [W]] was arbitrary, by combining Eqs. (45) and (50), have that, under event & E n Es, for all h E [H]. it holds that
min go(5) a4,)) oE
VE(D]
H
CHICE
log
+ 2L (1) - h 1)π 4HCoo0e
Vn
H
61 + 2L
22 (28
log
VT
8
+ (H h 1)7 + +HH Con
H
6H
d log 1 + 11 (a +log
Vnl
/n
+ (H h+ + 1)n + 4HC
= =E
Hdd
1
Ho/2d
Coone 26
= =0 Ceone H5/2,8 H/
((Coume
(51)
Vn
Vn
Vn
Vn
Vn
The first equality holds by plugging in the values of IC Leg, defined in Eqs. (33) and (34). The second equality holds by setting 5- 24 (2/ (H/ H equalities hold by plugging in parameter values according to Appendix A. The last two
22

---

Noticing that this is exactly the condition (Eq. (14)) in Optimization Problem that needs to be satisfied by any feasible solution, we conclude that, under event & Eg n &g, the true guess G is feasible solution to Optimization Problem 1.
G.1 Proof of Lemma G.1
Proof. To prove Eq. (46) we will use induction. The base case is when h H + 1, for which 1 (s) (s) for all s SH-1. This holds, since for all (s, a) E SH+1 A. qu (s, a) for 0111 E C. by the definition C. (Eq, (13)), and (s) = 0, by Eq. (1), since SH+1 {
Now, we show the inductive step. Let h E [H] be arbitrary. Assume that Eq. (46) holds for any t e [h 1: H 1]. We prove that Eq. (46) holds for h. Let (s, a) E Sh A, 0n Oc.. Then,
go. (), - qrà (s) $ min H. (o(s,a), 0x) (r)(s, (s
= =min H, (0( a), 0n) (s, a
(52)
where the last equality holds since (10(s, a), 0r) فー (s, a)) [[ H, , M.. We will focus bound- ing (o(s, a), On) - ghà a)). By the definition of the set θa,r (Eq, (13)) we know that there exists a On E θg. such that On - 0z < 3. Thus, by the Cauchy-Schwarz inequality, we have that
K (v(s,a), On - 0.)
s 11 a) xlxe |0. 1--00 100111s, s &1110(,,a))xx,,
This implies that
(o(s, 0n) (s. s (o(s, orà + Bllo(s, x)xxx"'
(53)
Since we know 0n da . by the definition oe (Eq, (12)), there exists a 9 1::1--1 E 0G x 06,441, such that
[ Phor-1 + 0o (o))
JE(n]
G.++1
By Lemma 4.2, we know there exists parameter Ph (ʃ) E B(L2), such that for all (8, E Sn A.A
Traj Taj-P,, R..... h4. [ + Go 11 (S.)] - [000][(((())) (((,,)), (Fo..LH))) .)) ST.
E
(54)
Let ph be as defined above. Next, we will show a bound on (o(s, a). On - ph: (fon+1:443))
and ())(s,a), ph"
(s, which together will give us a bound on
a), - (s, a), as desired. The following result gives us a bound on 0n "h" (10412.0
Lemma G.2. There is an event E,, which occurs with probability least 1 - 8/3, such that under event E for all G E G for all [H). and for all 0, & holds that
0hn 0z Xn.
38,
where
0, = xx-1
Σ
E T
P + Do P (sf) for some 0 E 0g.bt1 x ... x 0g,H41,
jE[n]
and 07, E B(Lz) is such that, for all (s, Sr x A. it satisfies
E
E
Phur-1 + 00 (S+) (0(s, 0h) sn.
Traj
23

---

Proof. Fix G E G. E [H] and On E @g.t such that
On = = Σ
P + 00 (o4) for some 01+1:H+1 E GG x .... x G,
JE[n]
Fix 0 E B(L2), such that, for all (s, Sp. x A, it satisfies
Ita tag R + U0 1.H [5+)] - (0(8, 02) s..
(55)
We would like to make use of Lemma H.1 to bound |00 0% Xn.
To do so, we map the terms used
in the Lemma H.1 to our terms as follows
n. X X, 0% V
Nn. 0 A
A
(b))
jE(N]
Y= = y + ((0%)00)) JE(m]
0oa 11 (6t)
+
E
hhr-1 +
Tow Fi
G1++1
sE(n]
h1--1 +
Don 11:111 (s2)
E TrajouP 0 oo 10
R + Co 11:08 ( [S+)
TruP 0,4+1
Tru Faj.a
jE[n]
A
E
R + Don+1: (Sr) - (0h,
TrjjoP
Fo.
jE(n)
Rh:T-1 + 0o 00 n+1 (5+)] )
==
( + 00 (et)
E Praj" 10.
E
TrPP G.
ma.hi
.E[n]
With the definitions as above, applying Lemma H.1 we get
0ōn 07 Xx
I vX + 11 Vn + ||l|x,1
(56)
The first term can be bounded by H3/2dd, by noting that |10/112 S Lz, and setting
-²= = 313 d/L2.
(57)
The second term can be bounded by n. by using Eq. (55).
To bound the third term let the event & be as defined in the proof of Lemma H.2, which occurs with probability at least 1 - 8/3. Then, under event ε,, the third term in Eq. (56) can be bounded by B (Eq. (31)), by applying Lemma H.2, since 0141:H+1 GG X Gg, B(
Plugging the three bounds above back into Eq. (56) we get that under event E,, it holds that
[0, 0%
< 3/2 dl +
N₂.
= = =3
(58)
The last equality holds by setting
H3/dd
S H3/2
(59)
Vn(10HPdo/aa do/a +1)
and the values of n, are set according to Appendix A.
We return back to the proof of Lemma G. Let & be as defined the proof of Lemma G.2. For the remainder of the proof, operate under event & By Lemma G.2 (with Pj (To..1 = 0%) we have that
|0h Ph (Don x, SB.
(60)
24

---

Returning ( - Ph (Bontumml) we can now bound it as follows.
(o(s,a), - ph (BenLumH)) 1l0(s, Ix, 00h Ph (Fe... |lx, s _ 1.
(61)
The first inequality used the Cauchy-Schwarz Schwarz inequality. The second inequality used Eq. (60). Now, q²a (8, by making use of Eq. (54), to get that
we bound (d(s,)) (),, Ph (Fon+1:043))
((s a), Ph (von)1 - g (8,
E Traje 20,
[ + 11 (S+) - - +
To Grg.hi
E
EB
RIuT-1 max 40 sosueetss (Sr; (Sr; a'EA
+ max g (S), d'EA
((, +
Traj ,e
d'EA
E
E
R1 + max "6
(S, 00) - (s,
Traj-PP
Tow Tog.t+1
a'EA
E
max
(Sr, (Sr,, (Sr, +
(62)
IrajrPP, ",. a... Fa, h+1 a'EA
The equality used the definition of e (Eq. (10)). To bound the first term in Eq. (62) notice that by the definition of के (Eq. (15)), arg max.ee4 g¹ (Sr,a' a') is exactly the action Ta would take at the stopping stage т, and that the distribution of Traj under policy Tº until stopping stage is same as the distribution of Traj under policy oe until stopping stage т. This gives that
RA-T-1 + max à (S,,a') a') a (s. = (s, - (s, (s) =0. d'EA
E
E
Traje
,,. T F.
To bound the second term in Eq. (62) can the inductive hypothesis (Eq. (46)). Defin- ing notation that will be needed for the below display, for any (8', aa) E S x A we will write Traj' PA,,a to have the usual definition Traj' (s', a', Ry .....,.>> SH+1 A' A'H R'1+)).
except with superscript (-)' added all of the random elements. Then, by letting a, arg max,' (90 (ieimet (S,, a') q"à (Sr,, applying the inductive hypothesis, and triangle inequality, we have that
E
E
max 90 (0sns (Sr, a') -"
Traje a. 1
H min 1, 10(() Abllx :)
E Tra
23
Σ
E Traj-P, P.... F mgja+1
E
(H- - 1)7
Tog.t
Traj' Pi
We bound each of the terms in the expectation separately. For the first term, first recall the definition of gº (Eq. (48)) and upper bound the term inside the expectation as follows, which will help relate things
shall see soon.
E Tray'
95 3 Σ min 1,, x = (|,xlo
S max (St, d'EA"
Along with the above result, notice that by the definition of न (Eq. (47)), arg max, g (S,, a') is exactly the action म would take at the stopping stage and that the distribution of Traj under policy T² until stopping stage T is same as the distribution of Traj under policy म until stopping stage т. Thus,
28
E Trajou a
E
max (S..aa))
The A- a' E'A
< 2,
E
E
min 1, 1101(SS. Ad) x Σ
max o² (St, a')
Traje ,0
F
d'EA
1==++
H
=23g (s, a) = 223
E
Σ
min m1n
11 Ar) Ar)llx,
Tra
1=
25

---

For the second term, since 5 2 h + where 7 ~ FG, Tra. +1+ it holds that
E
- 1)m S (H -1)
Trje- aao
T
Plugging the above two bounds into Eq. (62), we get that
( (o(s,)), (Dontemt))) - (8, 2
E
Σ
min
A.)lx² (H h 1)n
Traje 1=1+1
(63)
Combining Eqs. (52), (53), (61) and (63), we get that
Ga, (s, a) - ạ (8)
H
min H. 2, a)xx, + 28 E
Σ
min 1, I0llo(ss. AdIlx, . (H h + 1)m
Tra t=++1
28 min
(1ll x,²1
+ 2/3
E TrajrP
min min(1,11 1,116b55 Ad)ll } (H 11 + 1)
t=h+1
H Σ
2,8
E
min
1, (o((s 1 + (H - 1)77
Tra-- Pa
t=h
The second inequality used that 3 2 H and that min(a, + min(a, b) c for a, b, c 0.
Lemma G.3. There is event Es, that occurs with probability least 8/3, such that under event for all E [H) it holds that
min m 11 A)lxx, }ssc SE.
E (8.1)~p
where i is defined in Eq. (28).
Proof. First we will show two useful results (namely Eq. (64) and Eq. (66) that are needed in the proof. Let
x= {M paxd is positive semi-definite, and Amax S 1/A}.
Notice that any X X can be written as X >d nıao with æ; B(1/A) for all i [d]. By Lemma J.2, we know there exists a Cg C B(a)) a, { > 0 with |Cgl = (1 + 2a/E)* such that for
any x E (Ba)) there exists E Ce such that || ull2 < 5. Define the set
Σ yau, : yı E Ce for e (4
with |Y] = (1 (1+2/(EE)) Then, for
forany any X Ed 1 naoe E X there exists Y= Ei yiy, E E,, such that ||ær, 2 for all i E [d]. Let X, Y be as we just defined them. Then, writing II-Ilop
26

---

for the operator norm,
| YIl
Σ D Yolli
Σ 2 yi) - y22) + ye ye) (x= y/ 131
[| 1x 11) l1 Ba) 11 + ||(css y1) llop
(z; 1--111) 11)1121(0x - villla + 112:1aal( - willl + 110, - -4:4 1:)1121lb1112
i=1
25
d5² 2d
$ Σ
2 +
VX
VX
i=1
Then, for any E B((,))
2dg
||w/||x
|ulli/
= =IuT(x - Y)ul S || - -ylop - T. de²
vx
which implies that (since for non non-negative b, va+b Va vb)
2dk
2dg
|ullx s |ull + I
dE2
S Ilully + /
17 dg2 +
V1
VX
d62 + 2dE
I d52 + 2dg
|ully z $v V/lll's + 19
S ||ull x + V
VX
Vx
Thus, for any E B(L1)
2d
|||l|| - ||u||/| s L dE2 +
(64)
vx
Eq. (64) is the first useful result that we alluded to at the beginning the proof.
Now, we will show the second useful result. For any Y E Y and h [H], define the event
{
AY
E (S,A)~m
min(1, A)Ily
Σ jE(n)
min 1, o }
S
log
6H 8
Since min(1, [|ully] E [0.1] for all u E B(L)),Y E Y. we can use Hoeffding's inequality (Lemma J.1) to get that, for any Y E Y.h E [H], event Ey occurs with probability at least - (/(3H( Let
Eg= =
EYA
(65)
YEA
Then, by applying a union bound over Y, h we have that the event &g occurs with probability at least 1 5/3, and under event Eg, for all Y Y. E [H), it holds that
E (S.A)au
min (1, [8, A) S Σ min (1. (1,1
log
6
(66)
Vnl
5
JE[n]
Eq. (66) is the second useful result that alluded to at the beginning of the proof.
27

---

Now, we turn to proving Lemma G.3. Let h E [H]. Let X E X, and select Y E Y such that, for any (()))
2d
- || x L. d5 +
(67)
VX
which we know exists by Eq. (64). By using Eq. (67)
we get that
2de
min A)lx) Σ
E
min (l A)lly + Li dg² +
(68)
(S.A)~ps
(S.A)mph
VX
To bound the first term on the RHS in Eq. (68) we can use Eq. (66), to get that under event &
min ( 00 |
GH|Y
E
min (s, A)lly} S
+ Vn
log
(69)
(8,4)~p)
5
jE[n]
We can bound the first term on the RHS of Eq. (69), by again using Eq. (67), to get that
Σ min (1
Σ min 1, 06 [
2dg
Li Li
de
(70)
VX
JE(N]
jE(n]
Then, by Jensen's inequality we have that
| min (amn(,,1 1,
1, 0h +
06 [
1, 1.10%/133
min
min
JEIn
JE(M]
JEIM]
(71)
Putting Eqs. (68) to (71) together and noting that X, / were arbitrary, we get that, under event &s, for any X X, h E [H). it holds that
3 Σ min 1, 11100% oh
| x [x]
2dE
6/
E (S, (8,A)am
min (1,
A) A))lx
S
+ 2L, dea +
log
VX
We introduce X and make use of the above result. Notice that for any h E [H] X,=
(AI + Σje()) 0% (0)) T) such that (X,, S 1/A, since Amin(Xp) 2 A. Thus, X E X.
For any [m]. h E [H], define Xe,a + Σjen d6 (T)) and notice that X Xx= and
that X X is positive semidefinite. This implies that, for all h E [H]
1
Σ
1,
Σ min 1, 2
n jE(n]
JE[M]
Now, we can use the elliptical potential lemma (Lemma
J.4), to conclude that, for all h e [H]
1
Σ min
( 1, |
2d log
dd + nTa
dd
jEIn
Putting everything together, we get that, under event Eg, for all h E [H], it holds that
E (8,A)~pa
min
1, ( A)
2dg
6H
2d log
dd + nL?
< 2hg
d +
log
VA
n
dA
2
3H(1 + 2T.²" 1E)d2
2d log
dd +
+nI
$ /211/
dE2 +
log
+
H3/2
Vni
8
dd
Vd +
1
da
Foog
16nI3Iz 3) + log
3/1
+
2d
log
dd dd
nn=
Vn
Vnl
8
d)
=ē= =((d//n)
(72)
28

---

The second inequality used that |Y] = (1 + 2/(x))) The first equality holds by setting {-1 8T,2 Lnn. The last equality holds by plugging in parameter values according to Appendix A.
L
Lemma G.4. If Assumptiin 3 holds, then for any non-negative function f S x A - [0, 00), for any admissible distribution (U))E(H)) and for any h [H]. holds that
E f(S, A) S Ceone
E (S.A)~mh
A(S,A).
(S, (8.4)-M
Proof. Let f : A [0, 00) be any non-negative function. Let h E [H] be any stage. Then,
E
A)
JESANA (())un())d=
(8,A)mv
f JESAXA f(2) Un(2) (n(z) (o(2)dz
(z))
JEES XA
Crome (S,A)~AA
E A),
where the inequality holds by applying Assumption 3, and noting that f non-negative. This implies the desired result, since f and h were arbitrary.
29

---

H Lemmas Related to Least-squares
Lemma H.1 (Least-squares Error Decomposition). Let X 0,0, I2 and E N For all k E [n), let
A E RRd
7h R, Y% (Ak;; +K, Ys Tx=Y; + Ak:
V = X +
A,A, 0 = V-1 Σ A,Y,, 1= Σ
Acn, A = (At))e(a)
1=1
Then,
| 0.11y &v + || Vn ||lll--.
Proof. We begin by decomposing the targets used in 0 as follows
8= V-1
A.Y.
Ac((Ap, 0.) 7 70 Ac)
AI + A
A,A, 0. + +T0 -1T+.
+ +V-1 Σ A.(re + A.)
n AA Σ Am +
= 8. + AV 8, + V-1
Then, subtracting 0, from both sides and taking the matrix V weighted norm of both sides gives us that
n A,A
0 0, 11
AV
0
A
V
n
1
S Al10, lv- +
Σ
Ar7
+
A
V-1
Amio (V) |10 |101ly
IIal
S vAll0,l12 + --leell-- + 11A1l VT,
where the second inequality used that || I Amax (V-1) 1/Amin (V) and Lemma J.5 to bound IE A.
L
Lemma H.2 (Least-squares Noise Bound), There is an event E,, which occurs with probability at least 8/3, such that under event &,, for all h E [H) for all G E G, and 0,41:441 B(L2) H -+1,, holds that
Σ % 5E(n]
E
The--1 + 0g 0 (s+)
E Toe Ao.
[ + 08 +1:M
(S,))
33,
Traje o..
x
where B is defined in Eq. (31).
Proof. We begin the proof by showing two useful results (namely Eq, (74) and Eq. (75)), which will be needed later in the proof.
By Lemma J.2, know there exists set Cg B(a), with |Cgl (1 + 2a/E)á such that for any E B(a) there exists y E Cş such that || 2ll2 < &. Define the set C
30

---

X Cş C B(L))" with |C (1 2L2/E)) Then, for any 02 E B(L))", there exists 02:141 E C such that
0 8 = for h E (2: +
Which implies that for any h E [H], t E h+11: H + 11, S and 0141:H+1. h+1: as defined above
0o (s) - (8) - clip HJ max 01) clipo.m max 0,) aEA
aEA
max(o(ss a) 8.²
aEA
max]lo(s a) 112100 07112
aEd
< LE
(73)
Let O. Combining Eq. (73) with Lemma I.4, get that there exists set C C C G x (L2)) with ICg x x < (1+2L2L/ such that, for any (G, (210).41)) G GxB(L2)"
there exists (G, (11) E Ce C such that, any E [M], for any a E [M] and trajectory traj- = (st, oe, (c) it holds that
[Phr-11 + 8o 1 (8+)
PhoT-1 + Co (0+)
Fr 1.4
H
$ H - h 11t++)66v2ddF. 116
Li
Imh
(H - 1)7v 2dH
(74)
Eq. (74) is the first usefuu result alluded to at the beginning of the proof. Now, we show the second useful result, which is a bound under high probability event. For any (G, 11)+) E C.. C and [H] define the event
||lcorallss
3HICE x C
dde((Xn) det(AT)
S
2H log
+ log
5
where 18,00
Σ jE(m)
E
b pher-1 + 0o 1 (ot)
E F
Rier- 1 + 005 11 (8+)
TNN G.+1
TrajouP #
Notice that " H -ssuugaussian. Thus, can use Theorem from [Abbasi- -adkori al., occurs with probability at least - (3H x xfl)). Define
2011] to get that the event e cG,00.t
&
n
(c.0 JeC c
Then, by applying a union bound over G. 8 we have that the event E occurs with probability at [H]. it holds that
least 1 - 5/3, and under event ε,, for all (G, (7) E Ce x C
Σ
E
Pho--1
0o 1:
(5t)
E Trajr +o voo.
E Te Ao)
R + 0o (S+))
Fo G,0+1
jE
3H(1 + 2L,Lz/E) (L)
det((x)) det(Al)
2H log
+ log
(75)
31

---

Now with all of the above results in hand, we turn to finally proving Lemma H.2. Let G G as in the lemma statement. Then, by Eq. (74) we know that there exists a (G, 2 E Ce x C such that, for any h E [H], for any E [h] and trajectory traj (st, des [t) it holds that
E
[Pher-1 + v0 1I (++)]
E
(AUT-I + 00 (0x)
S L7V2dHfLii/a
G.
Ganide
(76)
8 22 be as defined above. Then, for any [H], by using the triangle inequality we can write
Let G,
Σ jEIn]
E Fo.10
Pho- +
(1 (8t)
R 1 + 0g +1: (5:)]
T-
Traj-iP ,0,r
To Fo,iiii
xxn
Σ
hhor-1 + Vam k1 (67)
E Trajo
E Tou C.tii
BRUT-I + 60 1 (S+))
jEIn]
Trw C.h+1
Xx
Σ EE(N]
E F-Fddas1
phor-1 + 00541:043 (0%)
E
Ther-1
0g P1 (st)
F. G,441
x
Σ JE[N]
E Traje-F
E T Fa
Rh:T-1 1 00 1+11 (S+)
E Fo,,
R 1 +1 (St)]
X
The first term can be bounded by Eq. (75), if we are under event & For the second and third term we make use of Lemma J.5, which ensures that for any sequence (b;))E(n) such that [byl S c E IR the following holds
Σ JE(M]
bi
S Sevn.
X2
For the second term and third term the respective by terms can be bounded by using Eq. (76), giving
us c = L22dH2LL//o
Putting the above three bounds together we have that under event & which occurs with probability at least 1 - 58/3, for all h E [H], for all G' E G, and 0x41:H+1 E B(L2) M H-++1 it holds that
Σ %
E Fro Fo
Uo (s4)
E TrajouP
E now 1
[R + Uo (S+))
h
jE m)
0.4+1
* . o
2H log
3H(1 + 2L2 2T2TTa/tydftidttt)
+ log
(
don((n) det((T)
+ +4V LiE/a
8
(3ll
H.
2dH + log 1 + ++22L(z/EE) + log(ddt(Xx))) dlog(A) + log
+ 2d
3H
< H1 (dH + log 1 2L2L2/E) + log(AA + /L - dogg(A) + log
+ 14V
where the last inequality used the Determinant-Trasn Inequality (see Lemma 10 in [Abbasi-Yadkori et al., (]). Setting g-1 14/7r2dH2 L we get that the above display is
(3H
H 2dH (do 1) [ 2 + dlog(A+nI3)) - nL3/d) dllo(A)) log
+1
8
= 3 = 6 (22
(77)
The last cquality holds by plugging in parameter values according to Appendix A.
32

---

I Lemmas Related to Covering
Lemma L.1 There is event &2. that occurs with probability at least 1 5/3, such that under event E2, for all G E G, and for all h E [H). it holds that
E
max A) D
min (o(S, BEBa,
1 n iE(m)
Σ
max (o(s). of) DE0G,
min dE@G,
go(of ah)
(8,A)~A
CH
log
+ 2
VT
5
where C Lg, are defined in Eqs. (33) and (34).
Proof. Let G G feasible solution to Optimization Problem 1. By the first result in Lemma 1.2, such that, there exists G E Cē such that, for any h [M], (s,
there exists a set C Sp. x A, it holds that
max (o(s,a)- min 80(s..)) (E0.,
max T0- (s) min To~ (1.aa) 6~E9&
S S (78)
Select G as defined above. Let h E [H]. Using Eq. (78), we know that
E
max A) min (s(S, #Eec,
E
max T0- (5,
min A
go- (S, A)
$ Lg.
(8.A)~Ja
#E
(8,4)<ps
(79)
To bound the second term in the absolute value of Eq. (79) to its empirical mean, we can use the second result in Lemma I.2, which gives that under event Eg
1 Σ
max To (S, 10
min To- (S, A)
max 0-E0
f0- (5h, at.) To (sh o/
min
(S,A)~mt
0 P~EE
a~ orERan
iE(n)
H
CHI $
log
(80)
6
We relate the G in the second term of the absolute value in Eq. (80) back to G, by again using Eq. (78), to get that
max fo- (5h oh) 8~E9
min o~ E
ao (s-, ah)
max (s ai)
min @EBc.,
to ( ah)
T
n
0E9g.
TE(M]
iE(n]
Tg.
(81)
Putting together Eqs. (79) to (81), and noting that h was arbitrary, gives the desired result.
Lemma I.2. Let & > O. There exists ser C. C G such that, for any
G. there exists
ā' E C such that, for any h [H], E Sn A, it holds that
( (mxx max (a(s,a) min (EGG,
go(s,
max (s- min 0-
To- (or()),)) S Le, g-EBe.
deGG,
where 1, defined in Eqs. (33) and (34). Furthermore, there is event Ez, which occurs
with probability at least 1 - 5/3, such that under event Ez, for any & E CG and E [H), it holds that
max T (S, P"E
min To- (S, A) 0'
Σ <c(m)
max go- (sh, o..)
min g
To- (shn (s)
0 (S.A)~Hh
0- 0-E
CHICS
log
V nn
5
33

---

Proof. Let & > 0, Kz 2 V E [2 H + 1]. By Lemma 1.4, there exists set C C G with
[C& < (1 + 2L2/E) di such that, for any G E G, there exists Õ E C such that, for any
h [H] for any 11 +
B[ such that for all t [h 1 H 1]
St, Eg, (s) v0r (s) S Kg. and for any j E [n]. it holds that
E 7o.t
PAT-- + Co, 10 (8+)
E
(hor-1 + Von (++)
TNFE
6,641
11
S (H - 116-
Σ Ke-1-
(82)
For the remainder of the proof let G, G be as described above. We first show the following intermediate result.
Lemma L.3. For all E [H), holds that:
1. For any On E da On E Ga there exists 07 E 2 0% E E0Gn such that
10x - 07 S Ss 10, - - 0,l,, S sc.
(83)
2. For any 87. E dan 0% E Gan there exists bn E dc,.. On E Oc, such that
S Sc |0,, lll,, I sc [bn 07 0711x,
(84)
where,
c - (1 VTL (a H-h
(85)
Proof. Proof of result 1.: To show Eq. (83) we will induction. The base case is when h H, for which
@GH Q
X
THTH H
OG, =6
jEIn]
Thus, for any Uu E θG,H Og E OG,H. select 0 = 011 E AG.. . 0 = =0 E 0 Then
0U - 07 XM 10, |1 - 8 0illx xw 50
Now, we show the inductive step. Let h E [H 1] be arbitrary. Assume Eq. (83) holds for any t E [h + 1: H]. We prove that Eq. (83) also holds for Let 0r E θc., be arbitrary. Notice that 9% must have the following form.
E
8o Bo 1 (o taa, for some 0,41:441 0G .... 0g,141 [
jEIn]
G.
Select 07 11114411
0g x... 0,HH1 such that for all i 11+1:++1]
|10, 8 11x S E
(86)
which exists by the inductive hypothesis (Bq, (83)) and since 0G, - (ő). Define
Or = x
E
P + ūo uo (st) E E
jE mg)
0.
34

---

Recall that we aim to bound we get that
On
0%
Plugging in the expressions for 0 0% as defined above.
Xn
||
@
0%
X
E
h +
(ot)
E Trupy d,N+1
( (ho-- +
Now (ot)
Xn.
T- G.A-1
jE(m]
X
by
Σ jE(m)
jE(m)
X
where in the second equality
we
let
by
[ + 60 11. 1n (o))
E E c. PheT-1 + 80 +
[s
To bound the above term we can make use of Lemma J.5,
which ensures that for any sequence (b:) such that |by] S a E R the following holds
Σ JEIn]
b
S savn.
X
Thus, we are left to bound bbyl- To do so, we can make use of Eq. (82), which requires us to bound To, (s) Ty. [s) for all E [h + +1:1:: HJ, s E Sr which can be done as follows.
To. (s) - Tor (s) = clip max a), B2) clip M) max(o(s, 0), 0,)
aEA
aEA
max ma) a). 02 - 077) -0,
aEd
S max]|<(s: a) ||x|= 110, -0, 1xx
aEA
4 - - Ln2c (H0/2d)
(87)
The second inequality uses the Cauchy- that Ammas (X, I 1/A (by definition of X₁, Eq. (I1)), and Eq. (86). The last equality used that VĀ= = H3/2 d/ L2 (Eq. (25)). Plugging Eq. (87) into Eq. (82) we get that for any j E [n]
inequality. The third inequality used Eq. (22),
|b9|
E
[Pher-1 + Ug 1 (87)
E
+ Toy + (0r)
Fr F..
Pd
G4++1
H
$ (H - ht
Σ
L,tz (1H3/2))
Thus.
L1 H3/dd Σ /4z
00h
0%
Σ
bgbb by
6V2dH2 Liça
Vi
JEmm]
xx=
= vn Lits 11
Σ
H3/2d
c
1=h
6 (1+ VTL (H33/22)))))) 1hh
= c
To see why the second last equality is true, let
2dH2 L and y
VnLi InL112/(H3//2) Then, for any E [h: H of = x(1 + y) (by Eq. (85) and
L2 Σ G44 = x + t Σ
H
6/H22 Li V
x(1
H3/2d
t=h
35

---

Notice that the sum can be rewritten as a finite geometric series.
H-h-1
(1+ H) -
Σ x)
Σ
(1 y)
x
y
Thus.
(1 + H) -1
+ y
Σ 1=h+1
s01 + y) y)
xx(1 + y) ")-h = G
y
This proves the first result in Eq. (83).
Next, we show the second result in Eq. (83). Let 02 E AG.. By the definition of the set G, there
exists a O2 E θc, such that | 0n
S B. Then, by the first result in Eq. (83) (which we have
Xx
shown holds for h above), there exists a f% @ such that |0. 0% x,
S c, Let On,, 07 be
as defined above, and select 0% = f/
0 + or. which is an element of G since
1% 0% Xn
11.. Bn + 0% 0% 0111x = =110, 0n Xn
S 3.
Then,
|10, 07 x,
00. On On 0% Xx
= =10%% - 0n Xx.
S E
This completes the proof of the second result in Eq. (83).
Proof of result 2.: The proof is identical to that of the proof of result 1., except swapping the roles of 8r On G and 0% 0% G.
Now, with the results of Eqs. (83) and (84) in hand, we return to proving Lemma 1.2. For any h E [H] let On arg maxge0a, (Ø(s, a), 0) then, by Eq. (83), there exists 0% E O such that
|10,- 1l x I c This gives that, for all h E [H], (s, E S₁ x A
max (o(s,a).0) 8 G
max (6(s,)), 00) = (d(s, a). An) - a).s.a),00) + (0(s, 0-
max (o(s,a),0))
#E0c..
< llo a) llx, xx, 110 llx,
La Sf L, L2ce / (1132d))
The second inequality used Eq. (22), that Amar (X=1) s 1/\ (by definition of X, Eq. (11)), and Eq. (86). The last equality used that Vx H//2d/ L2 (Eq. (25)). Now, for the other direction, using similar steps as above, for any h E [H], let 0f = arg max ()(s, 0*) then, by
Eq. (84), there exists On E OG.b such that 100, 0% I ch This gives that, for all h [H] a) E Sp A max (d(s,a),0*) 0
max (d(s,a),)) (d(s,a), 0N) (d(s, a), 0n) + ())ss)),00 0n) oE0a,
max ()(s,a),0) BeBa,
S | a) x 10% - 0n -111xx
I G Ln L2 (H²/2d)
VX
The above two results together imply that, for all h E [H], (s.a) E Sn x A
max (((s)a),0) max (d(s,a),07) S Tz (H3/2d). 8-E9
BEBa..
Following the same steps as above for min we can get that, for all h E [H], (s, E Sn x A
min (o(s,a).0) min (d(s,)), s /
oE
36

---

The above two results together imply that, for all h E [H], (s, E Sh x A.
max go(s,a) ) min 8o(s.a)) - (Eea
max 10E
min M-
go- po- (3.a)
Lg
BEeG.
where (by recalling Eq. (85)),
Lę 12V Lica (2rl
H 2 2L, L2ch/
(88)
This concludes the proof of the first result in Lemma 1.2.
Now we prove the second result in Lemma I.2. For any G E Ce h E [H). define the event
=G,b
E
max qo- AS, min qo- (S, A) 60
(S.A)~pA
6H CC
max y (6%, 0
min
qo- (5/, al)) 5
log
7 xE(m)
0 EGc
Then, since max 10- (8, a) mino c0 T0- (8,a) E [0, H] for all (s,a) E Ss x A. by
Hoeffding's inequality (Lemma J.1), we have that, for any G E C E [H] event & occurs with probability at least - C1 Let
G.
Eg
E2
(89)
GEOY, [N[H]
Then, by applying a union bound over G, h we have that the event & occurs with probability at least 1 - 8/3.
Lemma L4. Let 0, 0, Vt [2: H +1]. Then, there exists set C G with |CE) S (1
2 such that, for any G E G, there exists a G E Ce such that, for any h E [H], for any
E [h] and trajectory traj- = (st, at, re)te(u. H+1, and for any 0 0 14 E ([(l)) H-
that are close in predictions, that is, such that for all E [h+1: H+1], s Se, (o, - ū0. (s) s
Rt, it holds that
E T~ F4
[ThrT-1 1 + G0 1 (8+)
Phar- + 00 1 (07)
T TNEGmii
H Σ
(H -
- h 11)1)626 +
K4+1-
1=h
Proof. Recall that
G {(G))ne(2.M] (0) (0)) for all h [2: H], i [do], 0g E B(L2))
By Lemma J.2, know there exists set Ce a, > with |Cg| (1 + 2a 2a/E) such that for any E B(a) there exists y Cş such that || vll I &. Define the set C XMEpaAT)RE((a Cg C with | s (1 + 2222 Then, for any (D))nepmmm)ss e
G, there exists a G = (2)),,E)) E C such that
00 - 3 S E for all he [2: H), [do].
Let G, G be as defined above. Then, for all E S
Irange (())))(s)))))){ (s)
range G
(s)l
max max kk(do] a. E.E
(6s,, aaa),,)), a²), Sh (aage(())
max max (dss,,, als,,,,)), a'), Jt d)), (alage(s) kE(dg) a'''
< max max (b(s, a'), gk sttgge(s)
Tk Oetage(s))
ke(do] a.''A
< max max [|o a, a' 112 ge Jk
stage(s)
(stage(s)
kE(do) a.
< 2 2T
37

---

and, since we have by definition (Eq. (6)) that we is a smooth function in terms of range we get that
V2d range (s)
V2d range (s)
2v 2dL
S (g())
2
(90)
For all h E [H]. let +1 E B( h+1 such that for all E [h + H + 1].s E St, (ū, - E,- (s) S Kr.
Then, for any h [H] E [h]. and trajectory
traj = (8t, oe, +1) it holds that
T T~Fo,uihh [Thr--1 10 (s+)]
E
rh + (1 wo(sn+1 (0)++1))000000 (8h+1) + (86+11)) + (1 wc(s)+2))o, (86+2)) t...
Th + (1 - wa(#n+) )) (Sh+1) + (s F-Famaaa+
E
[ + 00 (8+) (91)
Using similar steps to above can be shown that
E
Th:r-1 + Tø 1 (0r)
Th + wo(sh+1)))mggg (sn+1) + wa(s
E
rht1:--1
0g 00 (s.) (92)
T mmii
We claim that for any h E [H], [h], and trajectory traj- (8t, ae, Te)
[hir-1 + E0g U0 To F Ammi
Thir-1 + 00 4 (3,)
T F.
(I -u-hh+166 (H--+1)ovddiLiff/
K1+1
(93)
To show Eq. (93) we will use induction on h. The base case is when h H, for which
E r~ Fa.mj, H-11
[T:r--1
+ 0g 1
E
TH:T-1 + U0 11. (st)
Tm F
anj
H+:
E Fmi.
[1
[TH:T-1]
0,
G.mii.
where the first equality holds since 0g, 08. {Õ} (detined in Eq. (13)). The second equality holds since for any E [H+1] and trajectory traj (st, ar r re)eejust++1] H1 H. 1) (+ =
+ 1) =.
Now, we show the inductive step. Let h |H - 1] be arbitrary. Assume Eq. (93) holds for any I E [h + 1, We prove that Eq. (93) also holds for h. Fix any u E [H + 1]. and trajectory traj (st, Oz. re) To shorten notation let Eg,0, = E 141 [Tee- + 00 11: (s, (and similar for p) Then using the assumption that for all u [2 H 1)
S., Va. (8) Tog: (s) < Ru along with Eqs. (90) (92) and noting that for any h
38

---

[H], E E,, E [0, 1, 08.41:1411 14 E [0, H.,, wo, wg E [0, 1], we have that
[Thor-1 + V (87)
Ph:r-1 + 4004+ (0+)
am Pr G.mj.A-1
(1 wc((h+1)) (su+1) - ( (sh+2) + wo(sstt) wo( ) n41
(11 wo(sh11) (1 w 80,, (sn+1) + 11 wa (8(+z))) Tonts (8u+z) UO% (Sh+1)
+ (wwa(14+1) we (s+
(wa )1 Ba B
2222HHLiEaa + Kh+1 4 4W2HH + EG EG,0rr41
H+1
6/2dHLL// + Kh+1 + (M - 2dH +
Σ
Ko+1
t=h+1
(H - h+ 11622
Σ Ke+1,
where the second last inequality holds by the inductive hypothesis.
39

---

J Other Useful Results and Definitions
Definition 3. A finite set G Ed is the basis of a near-optimal design for a S R if there exists a probability distribution over elements of G, such that for any 0 E O
(u, 0) = for all v E Ker(V(G,,)) and
(94)
[|0lviG..)] 2d,
(95)
where V(G,p) E [(x)ar
(96)
where for some matrix X, X denotes the Moore-Penrose inverse of some, and Ker(X) its kernel (or null space).
Lemma J.1 (Hoeffding's Inequality (Theorem 2 in [Hoeffding, 1994)), Let (Xi) be independent random variables such that X₁ E (a, b) for some a, b E R, and let Sn Li=1 X. Then, with probability least
( holds that
a) n2
log 2
S.S.. - S. S
Lemma J.2 (Covering number of the Euclidean ball). Let 0,E > 0, 2 and Ba(a) for R ||ا|| I a} denote the d-dimensional Euclidean ball of radius centered at the origin. The covering number of Ba(a) is upper bounded by (1 2
Proof. Same as the proof of Corollary 4.2.13 in [Vershynin, 2018] with B(1) replaced with B(a).
Lemma J.3 (Performance Difference Lemma (Lemma 3.2 in [Cai al., 2020])). For any policies n, n, it holds that
H E (Sn.AN)
0² (51) - (s1)
Σ h=1
(n) - (*)))
Lemma J.4 (Elliptical Potential Lemma (Lemma 19.4 in [Lattimore and Szepesvári, 2020))). Let Vo Raxd be positive definite and a1 E RRd be a sequence of vectors with ||a T. S for all t [n], V4 Vo + E.st a.ag. then,
det Vn det Vo
Tr Vo nL² dddetVV))1/d
dd) + nL?
min I, Iallalll 1.llaeli== s 2og
S 2d log
I 2d
dA
Lemma J.5 (Projection Bound (Lemmaa [Zanette et al., 2020))). Let (a:)ie(m) be any sequence of vectors in &d and (b:); in(n) be any sequence of scalars such that [by] I For any X 2 0 and E N we have
1
Σ a;be
nc?
E (.aaaaa))))) -N)-1
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims explained and shown in Section 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Discussed Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
41

---

Justification:
The result is Theorem 1, which lists all the assumptions it uses (which are presented in Section 3.1), and its proof is presented in Section 5.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
42

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: coips.cc/public//uii gwtg//udde////// /ooeeee/oooedubmii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
43

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eπrоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: https://neut httpp:ss/////iiss../eee wctppuliic/thhccccceeeelleeeelll
Answer: [Yes]
Justification: To the best of our knowledge our research does not violate anything in the Code of Ethics upon our careful review.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Discussed at the end of Section 6.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
44

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks since we do not use any data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi thcode com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
45

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "Bkeco5c5eV", "reviewer": "Reviewer_kP5e", "summary": "This paper considers the problem of learning the value ($Q$) function under q^{\\pi} realizability and concentration assumption. The major contribution is to use trajectory data instead of independent samples to learn the target function, where negative results have been proven with independent samples.", "questions": "I do not have any further questions.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem is definite challenging, in particular given the negative results with independent samples.", "weaknesses": "The presentation is a problem of this work. The notation system is not reading friendly, and there is no algorithm block. I suggest to add an algorithm to make the input and output clear.\n\nThe high-level idea is not clear. The authors spend too much space on introducing their methods, and there is no explanation about the hard term in learning with independent terms. For example, why should we skip the states with small range(s)? It is hard for readers to verify the result through touching the high-level intuition.\n\nAnother concern is about the computational efficiency. Seems there is no evidence the optimization problem could be resolved efficiently.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback.\n\n> The presentation is a problem of this work. The notation system is not reading friendly, and there is no algorithm block. I suggest to add an algorithm to make the input and output clear.\n\nAs in the camera ready we can have an additional page, assuming the paper gets accepted, we will be happy to add an algorithm (solving the optimization problem and outputting the policy defined in Eq. (15)) to subsection 4.4 (\"Learner\") with clear inputs and outputs, thanks for pointing this out.\n\nRegarding the notation, we thought a lot about how to present it in a clear and precise way, given the inherent complexity of dealing with many “modified MDPs” at once. We are keen to find ways to improve it further; could you please point to any specific notations that did not read well? Any further specific suggestions would be much appreciated.\n\n> The high-level idea is not clear.\n\nWe will improve the presentation of the high-level ideas; see our response to reviewer sDBe for more details on this.\n\n> The authors spend too much space on introducing their methods, and there is no explanation about the hard term in learning with independent terms.\n\nWe are having trouble understanding what you mean by \"hard term in learning with independent terms\". Could you clarify what you mean by this?\n\nIf you mean why trajectory data is crucial for our method, this is discussed in Section 4.2: “it is because we have full length trajectories that we can transform the data available to simulate arbitrary length skipping mechanisms.” In other words, without trajectory data, it is not possible to transform the existing data to data that one would have collected had one worked with a “skipping MDP”.\n\n> For example, why should we skip the states with small range(s)? \n\nThis is discussed in Section 4.3. We will improve this section to make sure the intuition that follows is clear. In a nutshell, if we could skip the states with small range(s), Lemma 4.2 shows the “modified MDP” would be approximately linear, transforming the problem to one we already know how to solve (e.g., with Eleanor [Zanette et al., 2020]). This would be great, but sadly it is hard to directly learn which states have small ranges. Instead, we use Lemma 4.2 as an analytical tool, as follows. We show that if we were to skip these states, the value function estimates in optimization problem 1 would be accurate. This guarantees that at least one near-optimal solution is considered by the optimizer. Without skipping, optimization problem 1 could optimize over the empty set, as it is possible that condition (14) would never be satisfied.\n\n> It is hard for readers to verify the result through touching the high-level intuition.\n\nWe hope that including the above, as well as the high-level argument using guarantees (1) and (2) in our response to reviewer sDBe will significantly improve this shortcoming.\n\n> Another concern is about the computational efficiency. Seems there is no evidence the optimization problem could be resolved efficiently.\n\nThe paper already acknowledges that computational efficiency is a concern. Through the skipping mechanism, our method inherently introduces complicated nonlinearities for value function estimations. It is an open question whether a computationally efficient solution to the problem considered in this paper exists at all. Our work only comments on statistical complexity, by discovering a polynomial-exponential complexity divide between trajectory data and individual transitions, which we found quite interesting. We think this contribution is of high interest and significance and thus warrants the paper to be published at NeurIPS even if we leave the question of efficient computation for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sdjlNuJKrQ", "reviewer": "Reviewer_eyWj", "summary": "This paper presents an important theoretical result in offline reinforcement learning (RL) with linear function approximation. The authors show that under the assumptions of linear q-realizability, concentrability, and access to full trajectory data, it is possible to efficiently learn an ε-optimal policy with a sample complexity that scales polynomially in the relevant problem parameters (horizon H, feature dimension d, concentrability coefficient Cconc) and inversely in the desired accuracy ε. This is in contrast to previous negative results showing exponential sample complexity lower bounds when only having access to individual transitions.", "questions": "na", "limitations": "Limitations are discussed in Section 6.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This is a strong theoretical contribution that significantly advances our understanding of the statistical complexity of offline RL under linear function approximation. The results are of high interest to the RL theory community.\n\nThe theoretical analysis is rigorous and the proofs seem correct. The assumptions are clearly stated and discussed. The authors also provide a thoughtful discussion of the limitations of their work, including the open question of computational efficiency and the restrictive nature of the linear q-realizability assumption.", "weaknesses": "It would be beneficial if the authors could add the concrete definition of the previous non-trajectory data to make a direct comparison with full length trajectory data (Assumtpion 2). Also, the authors could add some comments on the hardness results without the trajectory data after the added definition.\n\nIn Assumption 2, the notation $\\phi(s_h^1, \\cdot)$ is not clearly defined. It may lead to the meaning of $\\phi(s_h^1, a)$ for all $a$.\n\nGiven the lengthy proof with complex notations and limited review time, the proof details are challenging to follow. Adding more discussion on algorithm design, including a pseudocode, and explaining the intuitions behind the proof would be helpful.\n\nOne potential limitation is the absence of experimental results, which means the practical relevance of the theoretical findings is not directly demonstrated. However, considering the focus on fundamental statistical limits, the lack of experiments is understandable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback.\n\n> It would be beneficial if the authors could add the concrete definition of the previous non-trajectory data to make a direct comparison with full length trajectory data (Assumtpion 2). Also, the authors could add some comments on the hardness results without the trajectory data after the added definition.\n\nWe will add the definition of non-trajectory data and better highlight the corresponding negative result and how it contrasts with our positive one.\n\n> In Assumption 2, the notation $\\phi(s_{h}^{1}, \\cdot)$ is not clearly defined. It may lead to the meaning of $\\phi(s_{h}^{1}, a)$ for all $a$.\n\nThe learner is actually given access to $\\phi(s_h^1, a)$ for all $a \\in \\mathcal{A}$. Note that features corresponding to all actions are required for the optimization problem to be able to evaluate any choice of action. We will clarify the notation of Assumption 2 to reflect this.\n\n> Given the lengthy proof with complex notations and limited review time, the proof details are challenging to follow. Adding more discussion on algorithm design, including a pseudocode, and explaining the intuitions behind the proof would be helpful.\n\nAlthough the algorithm itself is conceptually simple (solving the optimization problem and outputting the policy defined in Eq. (15)), we agree that its presentation was fragmented. Currently, the algorithm definition is only mentioned in one sentence directly above Eq. (15), making it easy to miss. To enhance clarity, we will add an algorithm pseudocode block to subsection 4.4 (\"Learner\") that explicitly outlines the algorithm steps. We will also improve the presentation of the intuition; see our response to reviewer sDBe for more details on this.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vjcYHnUSJn", "reviewer": "Reviewer_sDBe", "summary": "This paper proves that finite horizon offline RL under linear q^\\pi realizability assumption can be solved efficiently (in terms of sample complexity) if the data are trajectories collected by a policy with bounded concentrability coefficient (that is, the density ratio between the state-action distribution induced by any policy and the data distribution is upper bounded). The result highlights the effect of trajectory data by sharply contrasting with the existing impossibility result where the data can be arbitrary state-action distribution with bounded concentrability coefficient.", "questions": "Please see above.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "To the best of my knowledge, this paper solves a long-standing open question of offline RL with linear q^\\pi realizability. The observation about trajectory data versus general offline data is solid and interesting.", "weaknesses": "I don’t think I completely follows the proof sketch shown in Section 4 & 5 given the complexity of the proofs, and some of the proof intuitions could be made more explicit instead of referring to some lemmas in the appendix. For example:\n\n-\tWhat is the reason that $G=\\bar{G}$ passes the condition (14)? Is it because the concentrability assumption plus Lemma 4.2 results in a tight confidence interval for the q-value?\n-\tOne thing I do not follow is how the algorithm eliminates incorrect guesses $G$. If I understand correctly, Lemma 4.2 only shows that linear q^\\pi-realizable MDPs with skips can be approximated by linear MDPs under the true guess. Then for an incorrect guess $G’$, is the modified MDPs still linear? If not, does optimization problem 1 still give some meaningful guarantees so that the algorithm can eliminate these cases? \nIn addition, since the optimization problem 1 is mostly built upon prior except for condition (14), if could be better to emphasize this new condition.\n\nMinor issue:\n\n-\tIn the statement of problem 1, n does not depend on \\delta.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback.\n\n> What is the reason that $G = \\bar G$ passes the condition (14)? Is it because the concentrability assumption plus Lemma 4.2 results in a tight confidence interval for the q-value?\n\nYes, it is precisely as you say “because the concentrability assumption plus Lemma 4.2 results in a tight confidence interval for the q-value”. Lemma 4.2 establishes that the targets of the least-squares regressions in optimization problem 1 are linearly realizable with the features (because skipping with $\\bar G$ results in an approximately linear MDP). Concentrability is then used to bound the average confidence of the least-squares predictor.\n\n> One thing I do not follow is how the algorithm eliminates incorrect guesses $G$. If I understand correctly, Lemma 4.2 only shows that linear $q^\\pi$-realizable MDPs with skips can be approximated by linear MDPs under the true guess. Then for an incorrect guess $\\bar G$, is the modified MDPs still linear? If not, does optimization problem 1 still give some meaningful guarantees so that the algorithm can eliminate these cases? In addition, since the optimization problem 1 is mostly built upon prior except for condition (14), if could be better to emphasize this new condition.\n\nRegarding “how the algorithm eliminates incorrect guesses”: it doesn't (necessarily). For an incorrect guess the modified MDP may not be linear, as you point out. In a nutshell, there are two key guarantees for optimization problem 1. (1) that specifically $G=\\bar G$ is not eliminated, and (2) that any $G$ that passes condition (14) leads to an accurate value estimation (even if the associated modified MDP isn't linear).\nTo show guarantee (2), we use $q^\\pi$-realizability only (no linear MDP properties) to prove that the true parameter $\\psi_h(\\pi^\\star_G)$ realizing $q^{\\pi^\\star_G}$ for stage $h$ is included in $\\Theta_{G, h}$ (Lemma C.2). Then the left hand side of condition (14) is exactly the confidence range for our estimator of $q^{\\pi^\\star_G}$. Condition (14) thus directly constrains these confidence ranges to be tight, leading to accurate estimators.\nGuarantee (1) gives legitimacy to including condition (14) in the optimization problem, by arguing that at least one choice ($G=\\bar G$) leading to a near-optimal policy value is considered by optimization problem 1. Therefore, whatever $G$ the optimization problem ends up choosing can only have a larger or equal value estimation than this near-optimal value. This value estimation is accurate by guarantee (2), finishing the proof.\n\nWe will follow your suggestion to better highlight condition (14), and we will make sure that the proof intuition above is clearly communicated in the paper.\n\n> In the statement of problem 1, n does not depend on \\delta.\n\nThanks for spotting the error in problem 1. We will revise it to $n = \\text{poly}(1/\\epsilon, H, d, C_\\text{conc}, \\log(1/\\delta), \\log(1/L_1), \\log(1/L_2))$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: There is general consensus about the value of the results in the current submission for the theoretical RL community, hence my recommendation for acceptance. The paper relies on the recent findings of Weisz et al., who first noticed how trajectory data would make it possible to prove positive learning complexity results in online RL under less restrictive assumptions. This paper leverages those technical results to do a similar treatment in the offline RL case. While the technical contribution of the paper may not be extremely novel, showing how leveraging trajectory data (instead of simple transitions) unlock polynomial sample complexity is particularly important from a conceptual point of view. Unfortunately, as pointed out by the reviewers, there remain several limitations, in particular on the “practicality” of the current algorithmic approach, which is not computationally efficient. Nonetheless, I believe there is enough interest in the formal result to propose acceptance. I still encourage the authors to integrate their rebuttal into the final version of the paper, in particular in making algorithmic choices and technical arguments as clear and accessible as possible.
Decision: Accept (poster)