Online RL in Linearly $q^\pi$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore
Authors: Gellért Weisz
András György
Csaba Szepesvari
Venue: NeurIPS 2023 oral (2023)
Keywords: Reinforcement learning
linear function approximation
online learning

Abstract: We consider online reinforcement learning (RL) in episodic Markov decision processes (MDPs) under the linear $q^\pi$-realizability assumption, where it is assumed that the action-values of all policies can be  expressed as linear functions of state-action features. This class is known to be more general than  linear MDPs, where the transition kernel and the reward function are assumed to be linear functions of the feature vectors. As our first contribution, we show that the difference between the two classes is the presence of states in linearly $q^\pi$-realizable MDPs where for any policy, all the actions have  approximately equal values, and skipping over these states by following an arbitrarily fixed policy in those states transforms the problem to a linear MDP. Based on this observation, we derive a novel (computationally inefficient) learning algorithm for linearly $q^\pi$-realizable MDPs that simultaneously learns what states should be skipped over and runs another learning algorithm on the linear MDP hidden in the problem. The method returns an $\epsilon$-optimal policy after $\text{polylog}(H, d)/\epsilon^2$ interactions with the MDP, where $H$ is the time horizon and $d$ is the dimension of the feature vectors, giving the first polynomial-sample-complexity online RL algorithm for this setting. The results are proved for the misspecified case, where the sample complexity is shown to degrade gracefully with the misspecification error.

Online RL in Linearly q" Reallabzal MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore
Gellért Weisz Google DeepMind, London, UK University College London, London, UK
András György Google DeepMind, London, UK
Csaba Szepesvári
Google DeepMind, Montreal, Canada University of Alberta, Edmonton, Canada
Abstract
We consider online reinforcement learning (RL) in episodic Markov decision pro- cesses (MDPs) under the linear q" re-realizability assumption, where it is assumed that the action-values of all policies can be expressed linear functions of state- action features. This class is known to be more general than linear MDPs, where the transition kernel and the reward function are assumed be linear functions of the feature vectors. As our first contribution, we show that the difference between the two classes is the presence of states linearly q -*-realizable MDPs where for any policy, all the actions have approximately equal values, and skipping over these states by following an arbitrarily fixed policy in those states transforms the problem to linear MDP. Based this observation, we derive novel (com- putationally inefficient) learning algorithm for linearly **-rrelizaable MDPs that simultancously learns what states should be skipped over and runs another learn- ing algorithm on the linear MDP hidden in the problem. The method returns an e-optimal policy after polylog H. d)/e² interactions with the MDP, where H is the time horizon and d is the dimension of the feature vectors, giving the first oolynomial-sample complexxyy online RL algorithm for this setting. The results are proved for the misspecified case, where the sample complexity shown to degrade gracefully with the misspecification error.
Introduction
We consider reinforcement learning where agent interacts in online fashion with environ- ment modeled as a Markov decision process: The agent, observing state, takes an action that results in random next state and reward, the latter of which is to be maximized over time. To tackle large, possibly infinite state spaces, additional structure needs to be introduced to this problem. One such structure is "feature-map" that maps state-action pairs to d-dimensional vectors (for some positive integer d) with the intention that a "good feature-map extracts important information from the state-action pairs that learning with this extra information becomes tractable. An example is the case of linear MDPs [U el all RUzua), where the assumption is that both the transition and reward functions are linearly factorizable and their left factors are given by the feature-map. In con- trast, value-based approaches, such as ""rrealizability [Du ct all 201, Eattmore et al, 2020] aim model only the action-values with the features. In this work, we focus on the latter, strictly more general setting than that of linear MDPs IZanette et all, 2020, Proposition 4].
There several sample-effie -fnnlee-fficient algorithms discovering near-optimal policies in linear MDPs un- der various MDP access models and settings (online access: Um etal [2020a]; batch setting: all
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Online RL
Planning with simulator
MDP class
poly(-) sample
poly(-) compute
poly(-) sample poly(-) compute
Linear MDP
Inn et
[2020a]
9 R realizable MDP
This work
Open problem
Yin et al [2022]]
Table Comparison of efficiency results for linear MDPs and o reerliizaee MDPs under online RI. and planing with a simulator. This work establishes that q -realizzblle MDPs are also sample efficiently solvable under online RL. The computational complexity of this problem remains open.
[2021]]; reward-free setting: Wagenmaker et al. [2022]). The best known sample-complexity bound for the online access model is achieved by the computationally inefficient algorithm of Zanette et all [002]] called ELFEANO, which serves as a starting point of our work.
In this work we consider the setting of linearly q" -c-rlliizalle MDPs. As opposed to linear MDPs, before this work, sample efficient solutions were only known for this case when the MDP is accessed through a simulator that implements some form of a state-reset function [Lattumore et all, 2020, Yin et all 2022, Weisz et al, [022 (Table M... In this work we resolve an open problem by Du et all [2019] and show that having access to a state-reset is not essential in this setting. To this end, we present EXIPPYELEANE (Algorithm M) and corresponding theorem (Theorem [) that shows that SKIPPYELEANOR, which uses online interactions only, is a provably sample-efficient solution to this problem. The of this paper is organized as follows. In Section Ø we introduce the basic definitions. In Section B we give an insight into the difference between linear qº geareiiizbbility and linear MDPs, which motivates our approach. In Section E we describe our algorithm and the most important technical tools we discovered for its analysis. Notably, in Section A we establish a rich structure inherent in "-rreaizablle MDPs, which acts as the technical foundation may be of independent interest. Finally, Section 5 gives summary of the proof of our main result (Theorem I), before concluding with some notes on future work in Section R.
this work, and
2
Preliminaries
For a linear subspace X of Rdd let Projx denote the orthogonal projection matrix onto X. Throughout
we fix d E N+ For L > 0, let B(L) = (x E Rd ||x||2 z L} denote the d-dimensional Euclidean ball of radius L centered at the origin, where || ll2 denotes the Euclidean norm. Let PD denote the set of positive definite matrices in d We write a =e for a, b, & E R if la b) S e. Let I(B) be the indicator function of boolean-valued (possibly random) B taking value 1 if B is true and 0 false. Let M, (X) denote the set of probability distributions supported on set X. The rest of our notation is standard, but described in Appendix A for completeness.
For the setting of episodic finite horizon RI, with horizon H, finite-action Markov decision pro- cess (MDP) describes environment for sequential decision-making. It is defined by a tuple (S, [A], P. R) as follows. The state space S is split across stages: S= (S,)ret)) with S = {s1} for some designated initial state s1. Without loss of generality, we assume the (St) are disjoint sets. We define the function stage S - [H] as stage(s) = if s E S, We consider finite action spaces of size A for some A E N and without loss of generality, define the set of actions to be [R] := (l,..., A}. The transition kernel is P (Ure[æ-1] S,) x [R] S,) - (S),, with the prop- erty that transitions happen between successive stages, that is, for any and action a E [A], P(),.a) a) E (S, The reward kernel is R S x [A] - MI, IJ). An agent interacts sequentially with this environment in an episode lasting H steps by taking some action a E [A] in the current state. The environment responds by transitioning to some next-state according to P. and giving a reward in [0, 1] according R. !I
[H 1], state s, S,,
We describe an agent interacting with the MDP by a policy æ, which, to each history of interaction (including states, actions and rewards) assigns probability distribution over the actions. Policies where this distribution only depend on the last state in the history are called memoryless, and these identified with elements of the set II (x S M₁ [))) Using policy x, starting at some state s in an MDP induces a probability distribution over histories, which we denote by Px.5- For
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.

---

xx.saa is the distribution over the histories when first action a is used in state after which policy π is followed. E. is the expectation operator corresponding Ex,s is the expectation with respect to xx,,). The state- and action- value functions v and qº are defined as the expected total reward within the first episode while π is used:
any E [A],
Px.
distribution P. (e.g..
H
H
(s) = B
R₂ fors and q²(s,a)= =
E
Σ
R forseS, a (A).
R.8
REstage( (S)
Restagee (8)
(s. a) = supxeut policies q=(s,, a) for all (s,a) eS [A). Let (s. = q" (s.a) and v (s) = sup 9- (s. a) for all (s,
Let π² E IT be an optimal policy, satisfying q" (s.a) a) = supxen (=
3 From linear q"-realizability to linear MDPs
As described in the introduction, we endow our MDP with a feature map 9 : x [ - B(1)) for some L1 O. For reference, we start with definition of linear MDPs with a parameter norm bound L2 > O, formalizing that the transition kernel and the expected rewards are approximately linear functions of the features:
Definition 3.1. (x-approximately linear MDPJ For any K S 1, an MDP is a x-approximatell linear MDP if (i) there exists oy..... .H E ((L2) such that for any h E [H] and (s.a) Sn (A), (B--R(s.)) R - (P((s 0n) z к and (ii) for any f : :S - [0, H and h E [H - 1], there exists 8, B((2) such that for all (s,a) E S x [A], (Ps-P().a) S(S") (y((s a), R2) s k.
key consequence of the linear MDP assumption is that the inherent Bellman error
R(s, a)+ max (''('','') (n1)) a), (n)) d'([A)
sup inf (11)8(12)) (3(a) (8,(()
sup
scales with the misspecification K. This property is also referred to as the closedness to the Bellman operator, and is crucial component in the analysis of approximation errors for algorithms tackling linear MDPs.
In this work consider weaker linearity assumption where we only assume that the action-value functions are approximately linear:
Definition 3.2 (q realiiaizaaiilt::: uniform linear function approximation error of falut-nunctions). Given an MDP, the uniform value-function approximation error (or misspecification) induced by a
feature map v : S [ - B(L1), over a set of parameters in B (L2) is
17 = sup max inf
sup
(
(s. (0((s (((ss ow)|
x he [H] g(h) (B()
(s.a)&S,x(11)
For the MDP and the corresponding feature map, for all h E [M] fix any On II - B(L2) mapping each memoryless policy π E Il to its "parameter", such that
(s(ssa) Bn (sp(s, a). (x)x) for all π e II, s e Sn, and a E [A].
(1)
The set of all parameters On C B(L2) for a stage h [H] is given by O₁ = (0) II].
Note that 0n satisfying Eq. (I) always exist [Weisz el al, 2022 Appendix CJ. We focus on the feasible regime where 77 is polynomially small in the relevant parameters. Specifically, we assume that 1j is bounded according to Eq. (2I). The main problem of interest in this work is the following:
Problem 3.3 (informal), For any E O and any MDP with corresponding uniform value value-function approximation error n,, derive an algorithm that, with probability at least 1-Ç. will find an e-optimal policy (i.e.. policy such that (51) 2 v*(ss) e by interacting with the MDP online mor T steps with T bounded by a polynomial function of (d, H , - L1, log L2). That the interaction with the MDP is online means that it is only possible to observe the features corresponding to the current state, and to take an action and subsequently observe the resulting reward and next state, which then becomes the current state. We consider the fixed horizon episodic setting, that is, the next state is reset to the initial state si after every H steps.
Compared to the detinition of In et (2120]] our definition does not require the existence of a vector- valued measure to represent the transition kemel. This is a generalization that is compatible with all existing algorithms for linear MDPs
3

---

1/0
$2
1/1
1/1
2/0
$1
1/0.5
2/1
2/0.5
$3
2/0.5
Figure 1: Left: MDP with deterministic transitions and rewards (edges are labeled with action/reward), Right: The same MDP with the red "low range" states "skipped" over. ((3).)) (1)pp(s))) (0.5).((..)) (0) otherwise. Both MDPs are q -erraliizabl,, but only the right MDP is linear.
Algorithms developed for linear MDPs are not directly applicable to Problem B when the MDP is only -rerelizzal::: While linear MDP is also q" -raalizzabl,, a rrealiizal MDP may be neither linear MDP, nor one with a low inherent Bellman error [Zancile et all 2020]. As an illustrative example, Fig. M. left shows an MDP that is q -realiizable but not linear. To see this, observe that the features for both actions in are identical, but their transitions and rewards are not. As illustrated in the figure however, if we skip over the red states (with identical actions) by taking the first action on them and summing up the rewards received until reach black state, arrive at linear MDP. This serves as the main intuition behind our work: the red states have no bearing on action-values, so they can be skipped, and the resulting MDP is linear.
More generally, we can define the range of any state as the maximum possible difference in action- value that the choice of action in that state can make:
rs) = sup max (s)s,,,)), for all E [H], s E Sh
where ()), (ss, i) (), /) is the notation for feature differences. Clearly, the choice of action in low-range states is not too important, as for any II and all [A]].
r*(s)= (s, (s,a) I range(s) 2n
Not only are the action choices in low-range states unimportant for the task of finding a near-optimal policy for the MDP, these choices can affect transitions and rewards in nonlinear way. Interestingly, the existence of low-range states is the reason why q* -e-realizable MDPs are not necessarily linear, as shown by the next result (proved in Appendix Q) which follows easily from Lemma 9
Proposition 3.4. Consider an MDP with uniform value- calue-function approximation error 2 O. If there are states S with range(s) for MDP are linear (Definition 1. with misspecification scaling with r,, and parameter norms scaling inversely with
O, then the transitions and rewards of the
Our approach. The above result immediately offers a strategy learn under the (linear) q=- realizability assumption. Assuming access to an oracle that can determine whether not range a for any state s, the MDP could "converted" to one that has no low-range states but has near- identical state and action-value functions of any policy (compared to the original MDP), by skipping over low-range states (by executing an arbitrary action) until a state with a range at least a is reached. We will call such multi-state transition skippy step and refer to such policy The reward presented for a skippy step is the cumulative reward over the skipped states. When the oracle is correct, the new MDP is a linear MDP, allowing techniques such as ELEANOR efficiently learn a near-optimg optimal policy. This conversion argument is part of the intuition of our method, but is not strictly part of the proof,
skippy policy.
defer the details Appendix C The only missing piece for solving the general case, Problem 536 learning an oracle that can suggest when to skip over a state, and combining it with the learning algorithm for the linear MDP. This general approach leads to our algorithm, SKIPPYELEANOR, which runs a modified version of ELEANOR with guessed oracles. During the algorithm, we detect when incorrect oracle leads suboptimal results, and refine the oracle accordingly. The details of the algorithm are explained in the next section.
4 Algorithm
In this section we present our main results following our plan outlined above. We first give Algo- rithm MI along with a high-level overview of the algorithm; the details are explained throughout the section. The parameters of the algorithm are presented in Appendix B.

---

Algorithm SKIPPYBLEANOR
1: Input: accuracy & O, failure probability ? >
2: Initialize
0, m 0. Qa L2/ for h [H]], x
3: while m' 2 mmaxx do
4: m -
m' also counts iterations repeated due Line 5: Estimate optimistic problem parameters č by solving Optimization Problem I.T
m' m' +
6: for E [H] do
7:
Let π= the policy defined by SKIPPYPOLICY C Sample trajectories by executing xr* from for episodes
8:
9:
and stage-mapping functions (pmkki)jtte Solve Optimization Problem with input (Ō,0),
Record data (5 ATr
10:
Consistency check
record its value x (maximum discrepancy), and arguments y (direction) and (stage). Calculate useful component
11:
Projz(e.)
Definition
12:
x > discrepancy threshold then
13:
Qi - (0, + 2, ww QQ,1)= 1
append Q, w to C, according to Eq. redo this iteration
14:
15:
continue
16:
if
ensertainty_threshhoee then
return policy mH
17:
Algorithm 2 SKIPPYPOLICY
1: Input: G,0.k
2: Initialize e -1
1), stage mapping p
3:
i= to H do
4:
Compute skip probabilities Ti Ta (S;) and non-skip action at - rT from Eq. (S) 5: Sample independently B; (ernoulli(r))
6: if B; 0 then A; 1
skip (follow x0) with probability 1 1-T;
7: else
8:
P() - iij j+
9:
j S k then A₁ t- at (Phase I) else A + (Phase II)
10:
if = then
p(j') 11 for j.....
For every stage [H]. the algorithm keeps progressively refined estimate of the geometry of the parameter space O₁, by maintaining an ever shrinking ellipsoid enclosing θ₁, This ellipsoid is parametrized by an 'inverse covariance matrix -like quantity Qn. determined by ( vectors, which guarantees maxe, s0, ||0, ll, Ó(vd). Looking at the definition of range in Eq. (2), it is give for the ranges.
clear that the smaller the ellipsoid becomes, the better estimate
Given some data collected so far and (Qn)a=(w-- SKIPPYELEANOR computes optimistic estimates of the action-values by calculating an optimistic policy parameter 0, as well as guess to a near- optimal design which used to estimate the range for states (due to technical reasons, & will guess near-optimal design for the transformed parameter space O,), @₂).
Data is collected by rumning stochastic versions of skippy policies on the MDP, where the states to be skipped over are determined based on the range estimates; when state is skipped, an action selected using a deterministic policy x0 that always chooses the first action in every state. To ensure that the estimation problem is smooth terms of G, we use smoothed version of skippy policies, where states are skipped randomly, and the probability of skipping is larger for states with lower ranges, while high-range states are never skipped. Similarly ELEANOR, we aim to estimate the action-value function of a state-action pair by adding the estimated one-step reward to the estimated value-function of the next state. However, unlike ELEANOR, we would like to do this in the reduced MDP, where the low-range states that are skipped over are removed (and the corresponding transitions are replaced by skippy steps). Since we do not know these states in advance, we run exploratory policies that skip over next states starting from any state: namely,
5

---

we run SKIPPYPOLICY(C.... for all k e [H] with maximum number of unskipped states k (Phase I), and once this skip budget is exhausted, all remaining states are skipped over by rolling out TO (Phase II), which ensures that we collect enough data at every stage of the MDP to be able to estimate the one-skippy-step reward of any skipping mechanism. Compared to ELEANOR, this introduces an additional loop in Line R of SKIPPYEL.EANOR, see Appendix ID for additional details. For any exccution, SKIPPYPOLICY maintains stage-mapping function p. which, for any stage h of the trajectory in the reduced MDP gives the stage index in the original MDP. In other words, p(j) is the stage of the landing state of the jth skippy step.
Finally, we check if the data collected is consistent with our estimates G and 0, by calculating the maximal discrepancy of the estimates of the action-value difference at the last non-skipped state of I n= = SKIPPYPOLICY G, 0, k) and that of the fixed skipping policy N² in different directions in the parameter space. If the discrepaney is too large for any k, we add the discrepaney-maxiiiziin direction to Q and throw away the data collected in this (i.e., the m²") iteration; this is achieved by reducing the iteration counter m by On the other hand, if the discrepancy is small enough, can guarantee that the gap between the value of nH and v v*(ss) scales with how much new information we collected, thus the algorithm can terminate returning this policy if this term is sufficiently small (which it eventually has to be).
The following theorem shows that with high probability, SKIPPYELEANOR finds near-optimal policy after polynomially many interactions with the MDP. Rhe proof sketch is provided in Section HX while method and proof strategy is explained from the perspective of ELEANOR in Appendix D.
Theorem 4.1. With probability at least c, SKIPPYELEANOR interacts with the MDP for at most Ô (H" d' /6²) many steps, before returning a policy π that satisfies v (s1) S V (s1) + E.
4.1 Preconditioning: the enclosing ellipsoid
In this section we give the technical details about the effects of using the matrix Qn describing an enclosing ellipsoid for θ, (see Lemma P as preconditioning the features.
Definition 4.2 (Valid preconditioning). Q (Qn)ne(H) is a valid preconditioning matrix sequence for all h [H]
Qn (4,21+ Evec, wT) 1/2
(4)
for some sequence C₁ = (V), vn) of vectors in Bd such that for all S i S n,
| [1521 "
supeco, (0, (e) and
2 and ||v||2 s L3.
(5)
where Lg is some fixed polynomial of the problem parameters (d, H log log 1,, log 12). (see Eq. (BS) for its precise value).
For valid preconditioning Q and some h [H), let Z(Q. h) be the linear subspace spanned by those eigenvectors of Q whose corresponding eigenvalues are at least L Let Projz( be the orthogonal projection matrix onto this subspace.
Sometimes it will be convenient to precondition the features and parameters so that the enclosing el- lipsoid is transformed a ball of controlled radius (as Lemma T will show). To this end, introduce for all h E [H] and (s,a, b) E S₁ x [ x [A] the following."
(0 a) = @nf(s,a),
ae(s, Qn4((s,,b
0 (x) = e7 0n (x),
0 = 100 : x = = 0 On)
(6)
(".(sa)) a) = (p(ss a). (T)) = (po(s. a), 06 (m( for all II.
The next lemma (proved in Appendix B shows that for all h E [H], Qn defines an enclosing ellipsoid for On: that is, O, c (0 : ||0|| S vdi + +I).
Note that en. A [H] is invertible by construction.

---

Lemma 4.3. Let d1 44 - forn any valid preconditioning Q and h E [H],
supeee, |101| sup a ||01|2 vdi I
Clearly, every time
vector is added Ch. the enclosing ellipsoid {0- |00 $ vdi 1}
shrinks (as positive semidefinite matrix is added to 27,)) The following lemma (also proved in Appendix D uses an elliptical potential argument to bound the number of times this can happen.
Lemma 4.4. For any valid preconditioning Q. for all h E [H], the length of sequence Cn corre- sponding to On according to Definition 2. is at most d1.
Near-optimal design for OR. As Qn only provides an enclosing ellipsoid for On. introduce an (unknown) ellipsoid that aligns better with 0%. For all h E [H], fix a set G of policies of size do == 4el log log(d) () + 16, together with probability distribution p on G such that (G) p is near-optimal design for O (i.e., satisfying Definition ETI.. The existence of such near-optimal design follows from [Iodd 2016, Part (ii) of Lemma 3.9].
We apply Gh to define a cruder version of range that depends only on a small set of policies, and can therefore be succinctly parametrized to inform SKIPPYPOLICY:
r = max max ()(s.i.)), xEGς (Jj[A))
for all E [H], 8 E Sh-
rangeo is easy to estimate, and can be used to bound the range function (proved in Appendix E); Proposition 4.5. For all s S and Q e PDH, range(s) s V2d (sn
4.2 Linearly realizable functions
q² ge-realizabilityy (Definition 2 implies the linearity of many more functions than the action-value functions. In this section characterize an interesting set of such functions, whose (approximate) linearity plays crucial role in our algorithm and analysis, as their parameters can be conveniently estimated by least squares using the features. We rely on functions f - R (for some h [!]) being small for all states, relative to the states' rangeo-value:
Definition 4.6. For any E (H), f S₁ - R is a-admissible for some 0 if for all Sh. (f(s)) & (s)/a.
The key observation is that expected (admissible) f values are linearly realizable.
Lemma 4.7 (Admissilee-raliiaaiin)
I Sh IR is a-admissible then it is realizable, that is, for all E [h - 1] and x E II, there exists some ô E Rd with ||0]| S 4doL2/a a such that for all
(s S, S, x [A),
B f(Sh) Zmp (v(s,a).0)
where 110 = =5do//a.
The proof relies on constructing a set of policies that at states s E S₁, take higher value action as opposed lower one with a certain probability, configured such that the expected action-value difference of some pairs within the set of policies is (approximately) proportional to f(s). Thus, policies in this set are also (approximately) proportional
linear combination of the aetion-values to f()). The statement of the lemma then follows from setting Ø to the corresponding linear combi- nation of the policies' parameters. The full proof is presented in Appendix G.
Next, we define matrix-value functions with a special admissibility guarantee even when the under- lying realar-valued function does not satisfy any non-trin non-trivial admissibility criterion. We introduce guess on the near-optimal design parameters that define range (Eq. (()) for some valid precondi- tioning Q:
Definition 4.8. For h [2: H), fix some arbitrary order of the policies in the set G (recall that this set is the support of the near-optimal design for e.)) Let the parameter of the hh policy in Gh be o), for i [do]. Call a "guess" of these parameters G = (Gn)ne(2.)) = ( (8) (2-H)))is "valid". for all h [2: i E [do]. 8 E B(vdi+I), Let the set of valid guesses be G. By Lemma P. (2 E G, that is, it is a valid guess, and we call this the "correct" guess.
Nooe that while of contains policies, G and its elements (commonly denoted by G) contain policy param- eter vectors.
7

---

From a guess G = (0 we can calculate corresponding guesses of the range values:
range g(s)
max max ( G sage(s)) k k=|db (
for all h E [2 H) E Sn.
Note that for any he [2:H] and sES,, range (s) if & is the correct guess for stage h.
Let (s)s) be the unit vector in the direction of the largest feature difference between actions in and the zero vector if all feature vectors are the same (see Eq. (27)) for formal definition). Then, for any & E G. h E [2: HJ, and f Sh - [-11, I1], let
((s) ()()) min rangege ((s) V2dH &
f(() for s Sh
For such f : Sh - Rexd we adopt the notation a' fb for any a. b E Rd to denote the function s E Sn + f(s)b. and similarly, (r( denote the function s E Sn Tr(f(s)).
Let (()) be the projection matrix onto the linear subspace spanned by those eigenvectors the design matrix VGG -%)) (defined in Eq. (25)) whose corresponding eigenvalues are at least y (for some y 0 specified in Appendix B). Intuitively, this is the subspace where 6% has sufficiently large width. Let (roj be the projection to the orthogonal complement subspace. For any Rd, we write ()(())) and (i( for Proij(QQ.) and Proi_(Q.,) v, respectively.
We are now ready to state our special admissibility guarantee, which is proved in Appendix IG. Let (dE((d be as in Eq. (IG)).
Lemma 4.9. For any h E [2: HJ. G G, any function I constructed as above from some ʃ Sn
[-H, H). and any v, W E B(1), Ti fw is a-admissible. Furthermore, if G ( (the correct guess). Tr(f) is also a- a-addissible.
4.3 Least-squares targets and Optimization Problem I00
Recall that SKIPPYELEANON estimates action-valuee of states by first adding the estimated one- step reward and the estimated value-function of the next state in the reduced MDP (where low-range states are skipped). Due the linearity of qd -vauues, these can used as target variables of least-squares estimator to estimate the policy parameters. This estimator is only guaranteed to be accurate the right (low-range) states are skipped; otherwise, we will argue in Section !el that discrepancy is detected and it is handled by changing the preconditioning Q. Finally, to ensure optimism, we select parameter estimates that lead to the largest estimated policy values. The whole estimation process leads to Optimization Problem EMMm which we define in this section along with the functions that it uses as least-square targets. Each estimation for a particular stage and may use the estimates 0, of Optimization Problem a for stages > h. In this subsection, consider the mh iteration of the optimization called by SKIPPYELEANON shorthand, we introduce the following notation for / E [m]. E [n], E [H]:
and consider Q fixed. As
p(lkj) = (K) as recorded in Line El of Algorithm M. and
Sikj = Ski (k) A lkj p(k)
lkj A (2) Rlt
Akj
lkj (K))
lkj AAA [kj = (S
Ikj = ((Skkj [kj p())
=
p(k)* P(k)
We collect the set of (1, k. tuples for which the th skippy step lands at stage for r [H],
(1) k1 j) / E [m 1J.j e [n], k E
=1}
Note in particular that here E [m 1J. so !" only considers data collected prior to iteration m.
To estimate the parameters & and 0. we consider (simulated) trajectories of SKIPPYPOLICH starting from stage f. For simplicity, we suppress the dependence of quantities on & and é, which will be brought back later. The skipping probability 1-T, the policy x* (to be also used in SKIPPYPOLICY, and corresponding clipped action-value estimates are defined as
V2dH
T(s) min
1, range
if stage(s) 1, and T(s1)
(8)
π T*(s) arg max (p((), a). a). ac(
C(s,) = clip (p(s), xt (s))((ss))))))))))))) 0.)
8

---

[0. 1] be any ending of trajectory. For 54+1 -, let be the (random) index of the first state that is not skipped by SKIPPYPOLICY with the above (or H + 1, if such an index does not exist). Then the estimated policy value of SKIPPYPOLICY from stage I
Let s, = (S₁, ag. ................................ SH. (H.) E
Eu ru + H 1] C(s))).
the sum of rewards along the skipped states plus the policy-value estimate from stage It follows from Corollary I below (proved based on Lemma ! that if range is an accurate estimate of q. then this quantity decomposes into terms that are linearly expressible using the features. Therefore, we use such quantities as least-square targets. Indeed, writing out the expectation, we can re-express the estimated policy value as the sum of all rewards Σ Tu plus correction term E (s++1+) defined
1-1 --(--=> D(s,))(()) a- r(sy)) where D(s C(s;) Σn Tu for
"
E (s,+)
The next optimization problem aims find optimistic parameters yielding the largest estimated action-value function for 81, where 0 is in the confidence ellipsoid of the least-squares estimates é. Optimization Problem 4.10 (for iteration m). For input state s, with B defined Appendix (emphasizing the dependence of functions defined above on G and 0 by adding them as subscripts):
arg max GEG. eB eB B (E)((
CGo(si)
subject to, for all t [H]
Xmt +1+
Σ (kjEI"(()
41
TkjT
|10, - G < B11 0, = X Σ
41 ( Ik)EI"(())
R
least muast-squares target
Since our realizability results in Section 2 only apply to functions defined at given stage (as only memoryless policies are rerreaaizalle), be able to show that the least-squares targets are linearly realizable, we first decompose (s,-) (i E [2 H]) to directly express the effect of each stage in the trajectory (backwards): defining E(s-+) = (s E (S++1-) (for convenience, we use the notation (S = 0), we easily obtain
(10) Next we define matrix-valued functions, whose trace equals Ess,-), that have the same form as in Section g for which Lemma RJ applies. This is crucial in establishing optimism of Optimiza- tion Problem I. as well as learning from instances where we detect that E- is not realizable in Optimization Problem I2I To this end, let
(s,-) E E(s
and
= ((s)))))-)
E(s,)) F(s,-) = (o (E(())
and
F(s)) = Bx [(s,, A..... RH) for si E S₁
Let θ (B(4dHHL2/a)) denote the base set for the variables 0, in Optimization Problem I. As of the same form as f, we can apply Lemma g and then Lemma 7 to arrive at the following:
Corollary 4.11. For any E G, Ø Ô, v.w E B(1) 1), and for any / e [H - 1]. i [++ 1: H], there exists some Un E Idd with [[vill2 s 4dgL2/a = 1/Vā such that for all (s, a) E S, x [A), where n70 defined in Lemma 7
Exa.a Foa Zmx (((ss,)),..))
(11)
Furthermore, if G is the correct guess, there exists some 0% Rd with 100,l2 S 4do such that for all (s, a) S, x [A], Exd,s.a ( Rn)) = E, (araa (S)))) =m (o(s,a).0,))
4.4 Checking consistency
Considering the mh iteration of ELEANOR,, we want to verify if the estimated targets of Opti- mization Problem Im are accurate (and learn a discrepancy detected), by using Corollary I.I on the targets' decomposition into F F-functions. We filter the data collected in the m th iteration with the indicator با = 1 (p(mkj) for [n], k E [H 1), i [H 1], and further constrain

---

this by another indicator ck (defined in Appendix BD that requires the data-poing 's least- -uusses uncertainty term to be sufficiently low, and the prediction non non-negative (the contribution of the rest of the data will be analyzed separately). Next, we define the least-squares solution for estimating the matrix-valued F. as well as the empirical average prediction and realization of on the data collected in the mhh round. For any i [2 HJ. k E [ 1] (recall that @ denotes the tensor product):
G0 = Xmm (kjel(()))
Σ
Fi OF Ga (S)) ....,.+H1 1
for 1 [i-1]
(12)
ki GB
1 -
Σ
Cupppek mkj goimk p(K)
Aki = Σ Ea GaFealsT R...,, Rinjj jE[n]
J=[n]
In Appendix D it is established via the usual least-squares analysis techniques and covering argu- ments, that with high probability the norm of the product of the matrix yki fkk and the projection
Go Ga The next optimization problem tests if this is true
matrix Proj (Q.i) is small (Lemmas and
in arbitrary directions:
Optimization Problem 4.12 (Consistency check). Input: (G.0)
arg max & ke[H-I].ie[k+la)] veRd:]Iell==1
ki v (>0o
GG)
(ro V is close to v, where v is the outcome of Lemma shows that the projection w Optimization Problem TT Also, Lemmas E. B. imply that if the consistency check fails (i.e., Line I3 is executed because the value of Optimization Problem i. is large), then w aligns well with the subspace Proj_(Q.)) projects to, and therefore stays valid preconditioning after appending w to the list of values Q is calculated from (Lemma E.4). Thus, Q is always valid preconditioning.
Proof overview
The proof of Theorem I is presented in Appendix (E. It is composed of the following main steps: First, we bound the number of times the consistency check can fail (i.e., Line IK is executed) by Lemma 4.4. Combining this with Lemma E.S. an elliptical potential argument bounding the number of times the average uncertainty can be large (these are the only two ways that the main iteration can continue) implies sample-complexity result for SKIPPYELEANOS limited the number of times the consistency check can fail, we derive guarantees regarding the performance of the policy returned by the algorithm: Via induction argument (Lemma E.3) we show Corollary ET, which shows that with high probability the difference between the optimization
(Corollary E.T). Having
value of Optimization Problem I Ca (s)) and > scales with the average uncertainty term EH Tht Thus, they are close when FLIPPYELLFANOR returns in Line I7 This complemented with the optimism property proved in Lemma Eati, stating that the optimization value (s)) is
close to x (s1). Combined, this proves Theorem 1
6 Future work
Since we are not aware of a computationally efficient implementation of SKIPPYELEANOR, re- mains an open question whether the problem of learning near-optimal policies from online interac- tions with a q" realizaalle MDP (Problem B.3) possible if the computational resources as well as the sample complexity are bounded by a polynomial in the relevant parameters. One approach is to replace ELEANOR with LSVI-UCB as the underlying algorithm, as the latter, despite having worse sample complexity, has computationally efficient implementation [Um et all 2020b). The challenge is to compute the optimal solution for the parameter & in Optimization Problem aTI This parame- ter interacts with the least-squares targets highly nonlinear way. We have been unable derive a computationally efficient approximation that has an additive instead of a multiplicative approxima- tion error (additive errors increase linearly in H, while multiplicative errors increase exponentially). Alternatively. it may be possible to show a computational hardness result for Problem B.3 by e.g. reducing to the satisfiability problem. These are left for future work. Our work on the realizability of auxiliary functions (Section (22) may be of independent interest for designing provably efficient algorithms for related problem settings, e.g., the setting of 9 "e-realizability in batch RI., where the data collection is not controlled.
10

---

References
Simon Du, Sham M Kakade, Ruosong Wang, and Lin Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference Learning Represen- tations, 2019.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pages 2137- 2143. PMLR, 2020b.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021.
T. Lattimore and Cs. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Tor Lattimore, Csaba Szepesvári, and Gellért Weisz. Learning with good feature representations in bandits and in RL with generative model. ICML, pages 9464-9472, 2020.
Michael Todd. Minimum-volume ellipsoids: Theory and algorithms. SIAM, 2016.
Roman Vershynin. High-dimensional probubility: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. Reward- free RL is no harder than reward-aware RL in linear Markov decision processes. arXiv preprint 1rXiv:2201.11206. 2022.
Gellért Weisz, András György, Tadashi Kozuno, and Csaba Szepesvari. Confident approximate policy iteration for efficient local planning in -rerealizable MDPs. In Advances in Neural Infor- mation Processing Systems, 2022.
Dong Yin, Botao Hao, Yasin Abbasi- Yadkori, Nevena Lazié, and Csaba Szepesvári. Efficient local planning with linear function approximation. In International Conference on Algorithmic Learn- ing Theory, pages 1165-1192. PMLR, 2022.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near opti- mal policies with low inherent Bellman error. In International Conference Machine Learning, pages 10978-10989, PMLR, 2020.

---

A Notation
As usual, we use R. N. and No to denote the of reals, non-negative and positive integers, respec- for another positive integer j. let [i /l (i..... f) if let (lip(u.b] min ( (max a), b) and let [x] denote the smallest integer such that i 2 x. Let 0 he the all-O vector Rd and the dd-dimensional identity matrix. For (square) matrix V, let Vt denote its Moore-Penrose inverse, and Tr(V) denote its trace. Let PD (and PSD) denote the set of positive definite (and positive semi-definite, respec- tively) matrices in Rdxd For some A PSD let A denote the unique matrix B PSD such that A BB. For V PD and E Rd, let ||x|| = Gx. For matrices A and B, say that A B (or 3 B) if B (or A B, respectively) is positive semidefinite. Ker(A and Im(A) are the kernel (or null space), and image, respectively, of matrix A. For compatible vectors x, y, let (x, y) be their inner product: (x. y) =x y. We write yeA for the tensor product between y and matrix A, and then (x, (8A) (x, A. Where Q and
tively. For i E N let [i] = (l...... 1);
i S j. and [i = ( otherwise. For a, b,x
Gx.
obvious from the context, and v ()())) respectively. Throughout the paper, we omit commas between quantities in subscripts superscript for clarity of presentation, for example, by writing Abe for Ab,c.
write yI and Ti for (Q.))
For the big-Oh notation O, we introduce its counterpart Ô that hides logarithmic factors of the problem parameters (d, H, E 1-,,5- 5 L,, L2).
B Parameters of Algorithm II
Ō ( (62)
(for precise value Eq. (42)
7(di + (d))
(13)
y = 8d Odd)
(14)
B Ō(HISd)
(for precise value see Eq. (36)
(15)
V2d IH 0(d
(16)
VPE
x (4d0l2/a)²
(17)
HmnL?
max = =B² log 1 dd
1- Ō (H²{))
mmx -max Hdd Ō(H2d)
Σ
mk/ c RH min 2(BWdH))
p(k)
for k [H]
(18)
je[n]
(19)
ce p(ikj)) < and
|
2(BwdH) and (pmtk) (p(mkn))
(20)
x-1 m.p(mn()
H
average_umcertane unngggtinncrttttyyy.o = Σ Tt
1=1
uncertainty_threee thresshlhhtehhheeee s/(HH Bw))
pecrepaanc__treshhoee = ,h Bw + dH²
Assumption on the maximum discrepancy:
m = 6²
a min /// E/(ff w), 1/ V
S 10do
(21)
dd
12

---

C Proof of Proposition 3.4
Proof of Proposition F. and the MDP conversion argument. First, for (i), show the linearity of rewards with .I...., 0g. For this take any h E [H]. Fix any policy E II and let 0n E B (L2) be such that for all (s, a) Sh x [A], q" (s, a) zn (g(s, a), Bx) (the existence of such 0 follows from Definition 2 If h H, ER R(s,a) [R] q" (s. a), so 0H = 0н satisfies Definition E.T. For h < H. let f Sh+1 + be defned as f(s) = (s)).. Fix an arbitrary Q E PD", e.g.. Q (I..... 1). Since (s) E [O. II] and range (s) 2 range(s)/ v2d 2 a/ v2d by Proposition 2.5 is a (V2dH) -dmiissildms and therefore by Lemma we can take 0₂ E B( such that for all (s, a) E Sn x [
B(v*(Sn+1) ss,a) v (f(s,a),0))
where, as before, 110 = /a. Since
E (R) (Bv ss,a) R (s..a))
letting On 0 -0, 02 satisfies (i) of Definition 3. with = v2dHno = 5H
To show (ii), take any ʃ S - [0, II] and h [H| 1]. As before, f ar ( therefore Lemma H.7 immediately provides fr, satisfying the required conditions.
Therefore, the MDP is shown to be linear with misspecification 17 V2dHno. and parameter bound 12(4HdoV2djor 1).
Sketch of the 9 -totoiiin MDP conversion argument. We elaborate on the conversion to linear MDP mechanism presented in Section BL As the basis of this argument is that an idealistic range- determining oracle is present, we note that this argument only serves as intuition and is otherwise tangential to our proof. Instead of a direct approach of learning this oracle, our proof argues that learning about this oracle happens whenever there is need (performance shortfall) for it. A formal reduction to linear MDPs given this oracle however is fairly straightforward but cumbersome, with the caveat that the linear MDP will end up with dH (instead of d) dimensional features. One would proceed by copying the features of each state in stage h into the hthh chunk of size d of this vector of size dH (the rest of the vector remains zero). A similar transformation is applied to all 9 (z). Then, H copies are made of each gigh--nnough-angg state, with all possible stages (but keeping the feature vectors). These will be the states of the new MDP we construct. When a transition from state leads to skipped states, the linear MDP returns with the copy of the first non-skipped state that has a stage counter of stage(s) + 1, so that in this linear MDP the stage numbers are consecutive (as required by our definitions). 9º -rrraliizability of this modified MDP is easy show, and (as it has no low-range states) Proposition 3.4 can be used to show that the modified MDP is linear. To account for the fact that this new MDP may finish an episode in fewer than H steps due to the skips, we add a special, zero-reward, self-transitioning state called "episode-over". To ensure that the MDP stays linear, we extend the feature vectors of each state by scalar 1, and scalar indicator of being in this state, with all original features of the "episode-over" state defined to be zero. It is easy to see that this construction leads to a linear MDP with the desired action- valuee functions.
D Intuition behind our method and proof strategy from the perspective of ELEANOR [aneette et al., 2020
The starting point of our method is the ELEANOR algorithm, which is designed for linear MDPs. Similarly to SKIPPY ELEANOR, ELEANOR solves an optimistic optimization problem inside a loop. The optimization problem computes optimistic estimates é, of the parameters of the MDP simultane- ously for all / E [H), and in each iteration of the loop, more data is collected according to the policy that is optimal for the MDP defined by the estimated parameters. Initial estimates 0, are computed via solving least- sausr-squress problems whose covariates are the features corresponding to state-action pairs (S,, A,) from all the data collected so far, while the corresponding least-squares targets are computed as the sum of the immediate reward R, and the estimated value for S computed from Be+1. O, is then optimistically chosen as the solution of the optimization problem, in the neighbor- hood (confidence ellipsoid) of 0, the solution to this least-squares problem. It is shown that this
13

---

optimistic choice of estimates results in an optimistic estimate of the value of v* of the initial state, and the regret is upper bounded in terms of the sum of elliptic potentials of the covariates.
This argument appears our analysis too, with minor modifications due to our PAC-like setting (instead of aiming bound the regret), leading rithm M. Our Optimization Problem BM0 is similar to ELEANOR's, and the parameters 6, and 6, have the same meaning. SKIPPY ELEANOR are how the least-squares targets are determined. For ELEANOR, it is the sum of the immediate reward R, and its estimated value for S,+1); with this target, only one on- on-policy rollout is required for each episode in order to get the least-squares parameter estimate for all H stages, In contrast, our suuarss targets are formed as the sum of R +.....+ Ry+/ and the estimated value for S/4111, where the number of stages "skipped", depends on the guess G. The guess & is selected only in Optimization Problem E and we do not know its value at the time of data collection, so we cannot know which stages will have to be skipped for each rollout. Therefore, (i) we need access to the rewards of the current policy at any stage (similarly to ELEANOR), and hence we run the current policy to any stage (including the last one); and (ii) perform rollouts with the fixed policy x² (from any stage) to be able to estimate the reward R, + R, collected while skipping over i stages (for any 1). ensure this happens for every stage, we start Phase from every stage k, resulting in the additional for loop in Line R of Algorithm I1 compared to ELEANOR. Finally, the randomization in Phase is applied to make the optimization problem smooth, as described in Section EL
final-iteration condition of Line IIG in Algo-
key difference between the optimization problems of ELEANOR and
One could analyze this algorithm similarly to the analysis of ELEANOR if were not for the fact that the least-squares targets we just introduced are not realizable in general. We can, however, prove the realizability of certain components of the matrix-valued version of these targets, F (Lemma H. and Corollary I.). This enables us to detect when the realizability of our least-squares targets fail, measure the direction (component) of the largest error, and learn from that. This is the job of Optimization Problem I.2
fki Go corresponds to the matrix-valued empirical measurements of F,
while the yki are the average predictions of the same quantities. If the targets are realizable, which Go happens if we manage skip the right number of stages), these matrices are very close; if not, the direction of their largest discrepancy tells us something about T (Q.i), i), and allows us to learn.
Optimism ties all this together: either there no shortfall between predicted and measured g-values (and we are done) or we grow the elliptical potential of X (the two cases present in the analysis of ELBANOR, Zanette all (2020]), or we grow the elliptical potential of Q (the new case due the lack of realizability guarantees).
E Proof of Theorem
In this section we present the proof of Theorem Recall that some quantities are defined in Appendix [
E.1 Checking consistency
We introduce some lemmas to establish the required guarantees of the consistency checker. Their proofs, which rely on the usual least squares analysis techniques and covering arguments, are pre- sented in Appendix El
Lemma E. Let v) be the oulcome of Optimization Problem 1. any time during the execu- tion of SKIPPYELEANOR, and let Prrojz(e.)) in the algorithm. Then,
w (y GG w 2 v ( -
Aki
dH2w
Lemma E.2. There is an event Er that happens with probability at least 1- such that under E, during the execution of SKIPPYELEANOR, when the beginning of any iteration (Line D is executed, for any e [H 1], i [1+1: for any G G. E G, and v.w E B1),, for all (s. a) E S, x A).
Ii ((ss,))T0)) T0%
B FGo(Si) m/ (1l((s B+ dH
E
,ss
where I| denotes l(0.))
14

---

The next lemma uses the average least-squares predictions' (capped) uncertainty term 0 (defined in Eq. (T)), where the average is taken over predictions from the state-action pair where Phase of SKIPPY CHIPPYPOLICY(:.
ends.
Lemma E.3. There is an event E2 with probability at least 1 - <. such that under & O Eg, during the execution of SKIPPYEL,FAOOR when Optimization Problem 8. solved (Line ITA), for (G, 0) as recorded in Line for all k E [H 1], [k + H), and B(),
I Go
fil Gā w/ B+ 3 dIPw
where I| denotes I10.00)
Together, these lemmas can be used to show that the vector w derived from Line III in SKIPPYE- LEANOR is sufficiently aligned with both Z(Q.-) and the subspace Proji(e.)) projects to, which leads to the following important result:
Lemma E.4. Under the E1 n Eg, if Line I3 is executed any time during the execution of SKIP- PYELEANOR (i.e., when the consistency check fails), then the resulting Q continues to be valid preconditioning.
From on, lemmas assume the boob-bbbbbbiltty events of Lemmas P and B hold, and therefore Q is a valid preconditioning at any time during the execution by Lemma D
F,2 Sample complexity bounds
We bound the number of iterations of m that SKIPPYELEANOR can execute. The proof of the following lemma presented Appendix II
Lemma E.5. Throughout the execution of SKIPPYELEANOR,
Mmar.
Note that throughout the execution of SKIPPYELEANOR, m' S m'max As - m equals the number of times Line TE is executed, i.e., the sum of sequence lengths corresponding Q. by Lemma 34l Corollary E.6. Under E₁ n E2, SKIPPYELEANOR returns with policy before exiting the while loop of Line G. and each iteration executes Hn trajectories in Line B the number of interactions of
with the MDP is bounded by Ô (H!l d'/ /
E.3 Performance guarantee
We next consider the mh iteration of SKIPPYELEANOR under the assumption that the consistency check passes, that is, Line IIA is executed. We intend to guarantee the performance of mH in terms of Σ -.t given that the optimization value x satisfies s TT Biw+ 3 f__ (which follows from the execution reaching Line Id) Next we introduce variants of c/2 and E (Eq. (2l)) which act, instead of the data collected during the execution of the algorithm, corresponding stage mapping obtained by an independent run of SKIPPYPOLICY, which will be clear from the context: čki- (p(k) i), and
trajectory (Sn. As, Ra)ae(H) and
= p(k)) < i and Apte) _i.p <((BwdH)~ and (p((S(():AAps)) 0((s)) 2 20
Remark E.7. In our analysis we rely on the obvious fact that the laws of the trajectories of SKIPPYPOLICY O, k) and SKIPPYPOLICY(G. Ō. 1) are the same until stage p(k + 1) (as the policies are the same until then), for any parameters G and 0. This includes Spikt1) but not A p(k+1) if p(k + 1) S H, and includes the whole trajectory ending with Rh otherwise.
We prove the following using induction k H...., 1 in Appendix 0
Lemma E.8. There is an event &3 with probability at least - 33,, such that under E, E n Eg, during the execution of SKIPPYELEANOR, whenever Line W6 is executed, for (G, 0) as recorded in Line E of the current iteration, for [H),
ck E CG m
E Hm
Σ u=p(k)
Rú +
_ in
E o BwdH 4(H k+ (22)
H
15

---

As S1 = Si is fixed and T(s1) 1, we get the following corollary, which shows that the value Coo of the solution (G, 0) of Optimization Problem I.0 can be used as lower bound the value of the policy π mH up to the uncertainty and some & terms:
Corollary E.9. Under E1 SrnnEEE the value of Optimization Problem & M with the solution (G, 9) satisfies
H
H
H "Bddl + 4
CGa(si) =
R 15
Σ
Ru + 2
Th Budlf + = v (5)) +
Σ t=
oh
E.4
Optimism of Optimization Problem 3.1
The following establishes the optimistic property, that is, that the value of Optimization Problem H competes with y* (s1). The proof relies on the fact that the correct guess and a good choice feasible for the optimization problem, combined with the fact that this 0 induces policy SKIPPYPOLICY A, HI) that takes action-value maximizing actions according to very accurate approximation of action-valee values almost everywhere. In fact, it only skips states whose range is at most e/H. The proof is presented in Appendix IK]
Lemma E.10. There is event E4 with probability at least 1 1- such that under E1 O E2 n E throughout the execution of SKIPPY ELEANOR, the value of Optimization Problem 70 is at least (*1) - -2.
Proof of Theorem
S and the fact that the condition of Line IG is satisfied when SKIPPYELEANOR returns with policy, to get that under E| n Eg n &3 n 84, that is, with probability at least 67, SKIPPYELEANOR interacts with MDP for at most Ō (H1 dl (6)) many steps, before returning with the policy mH that satisfies
combine Lemma DA with Corollary
DRS.
Corollary
(51) CG8(s1) + mmH (s1) +2
Σ TT Bwoll + 68 s v mmH (s1) 88,
where the final inequality follows from the fact that when SKIPPYELFANNO returns in Line Iin HH Thhh s </Wddd)"") By scaling the parameters, this finishes the proof of Theorem B.
F Deferred definitions and proofs for Section
Proof of Lemma 3. For any A e 0. it holds that A 2 for some e On. Since ||0||2 12, and writing Qn as Definition H.21
|0l2 = 0T (1,21 + TT) A = 1,212 + |Cal s 1 d1,
where we used Definition and Lemma Finally, we conclude that ||01|2 s vdj I
Definition F.1. (G pf) is near-optimal design for 06. ffr any 0 e of.
(v.0) for all v Ker(V(G ( and
(23)
|0012 1 o8 s 2d,
(24)
where V(G (G pp)= Σ ph
(25)
XEG
An important corollary of the above definition is that if M = Proj P of)
then
V(G p/ - ( pf) = Mv, and (0, Mv) = (0, v) due to Eq. (3 and so
0T==0'v - t V P.C..pP))r A
for all 0 E 0f and e Rd.
(26)
16

---

Proof of Proposition 1.S Take any h E [H], s E Sh. and @ e PD" Take i.j E [A] such that range(s) sup (). 0). Then,
range(s)²= sup (c(ssi,,).00²= sup (ve(s.i.D.0)) 8c8n
sup || 0
s 2d
Σ ( fe(s,i.))
ncG
=dd((s,i,))*
Σ ((( XEG
((s,i,))
$ 2d max (p(s.i..)),0 s ra)ge z
where the first incquality uses Eq. (MG) and the
Swww-wwwwaeauuliliyy. and the second inequality follows by substituting the definition of v(G) k. pp
)) and using Eq. (24)). Finally, the first inequality replace the weighted sum from the previous line with the maximum
in the last line holds operator. We therefore get that range(s) V2d (s) finishing the proof.
Take any h [H] and the sequence C₁, corresponding Q. Assume that this sequence is of length I, and let Σn, L I En Vyv] for e [?]. By the second part of Eq. (s),
Proof of Lemma 94
min 1,2
1
Vi
S 2
min
Applying the elliptical potential lemma (Lemma
Tr(En.o) + 11.3 d dete(E
11.2
1 min I. IIvill
s log
Ad 1
1.22d
where Σn,o L by definition. Using that log(1 +x) vx for 0. we have / 4d 1L3L333 d. which implies I s L6dL3L33 Substituting this into the previous bound yiclds
(16dL323)33
s 4d log
4d log [+ 1629L7) di
L
G Deferred proofs for Section
g
For any vector E Rd, we define v = v/llvll2 as the unit vector in the direction of if v * 0 and Ō= = 0 otherwise. For any |2 H). Sh, the normalized version of the largest preconditioned feature difference is denoted by
(s(s) i,, where (i.)) arg max [lo {.
(27)
Proof of Lemma 4.7
Fix E [H), a-admissible f: Sn R. [h- [1-1], and π II. Our aim is to
construct policies म E II for [do], such that for all (s) S, x [7), Σ [dn) (a (s) nE (s, a)) is approximately proportional to the desired E,,s,a ff fSp). Let Gº h, policies in of underlying the near-optimal design of of. and for any E S,, denote by ord(s)
of h.2.... denote the
17

---

[do] the index of the policy maximizing the range of the action-value function in state that is, Gl
hoodi(s) arg max xeGg mexi,je(a((9 (s. q" f);; simplify notation, define G(s)
Gh
For s E Sn, let h,orr(s))
arg max (. ( ((()))s)))))))))))))) (s. (s.))(s. i()) 20
(a*(s), (s))=
arg [E{M] ( (s, g0(() (s.
otherwise.
By Eq. (02) and Definition 1 have that
6660) (s.a*(s)) -pth) (s, (s) rrange 2 alf(s))
Since Gis) (s, (s) - - (s,a 22 (s,a - - (66 (s,a a (s)), if a af)( 2 4n, we have
G (s,a" (s (s)) q (ls) (s.a (8)) as(() - 2n 2 z f(s)
if f(s) 2
(28)
(s)) G( (s. a (s)) s aa((s) + 2n s f(5) <0
(s,
otherwise.
Let us define f :Sh + as
af f'(s) (s,a" (s)) (5))) (8))
af) 2 4n
otherwise.
By Eq. (28), there can be no division by zero in the above definition, and f's) 1
Now we are ready to define n and g.. Both policies follow π up to stage h - 1, when they switch Gh h, except if at stage a state s Sn is such that Gf has the maximal action-value function range. this case x selects a+)s) with probability f'(s) and a (s) with probability - f'(s), while & always selects a (s). Formally, for & E [do]. we define for s E
T(S)
if stage(s) < h;
(s)
(s) w.p. f'(s), and a (s) w.p. 1- f((s if stage(s) and ord(s) k; (s),
otherwise,
where w.p. stands for with probability. Similarly,
(s))
stage(s) h;
(s)
a (s) w.p. stage(s) = h and ord(ss = k; Φ
(s) (s)
otherwise.
Note that x. E II and o E II. as desired. Since for all k E [do], the policies follow GY,,k for s E Sp for 1' > h, therefore for all k E [do].
(s) v (s)) v (h((s) for all s Sh+1, and
(29)
q (s, a) 9 (s. a) = q ch (s.aa) for all (s) E S₁ x [9].
(30)
Also, for any S with stage(s) < h and any E [R],
Σ ( (s. ( (s, kE[dg]
Σ
(1 v (Sh)
E
a.S kE[do]
r Fadts (Sh) v. (Toisss (Sx))
= E
B T55,a
q
@GSSN (Sn, a" (Sn)) + + GISn (Sp, (Sp.aa(Sa))(111 (1a)
q G(Sn (Sh, a (Sh))
(F'(SW) (11 (Sn, a' (Sn)) - -9 G (Sn. (Sx))
= BB
J.5aa
E Haal(Sh) 4n) マ f(S) #2n n.s.0
f(Sr)
T..aa
18

---

where the first line is due to both q and q=* following on states with stage less than ht the second line follows from the fact that for any s Sp. x = n (s) for any k ord(s); combining this with Eq. (29) leads to all k * ord(s) terms of the sum to cancel. The third line follows from expanding the definition of the policies and Eq. (GI..
Let 0= = 2 Ekeldhl (T,( (x))) Since |10,Ol12 s L2 by definition, we have ||0||2 4doL2/a. By Definition B.2. for all (s. E S, x [A]
(p(s.a). a)) 20)
=2d
Σ
(s, ( =2n
B f(Sb).
x,5,a
kE|da]
and hence
(v((s, 0)
#4(d++))n/a
f(Sa).
2,8,0
Since 4(do + 1)m/a z 170 5don/a do 2 by definition, this completes the proof.
Proof of Lemma 4. Take any E Sh. For the correct guess, range = ( Then, using
that || s 1. Tr(((s)) I range vean² proving the second claim of the lemma (as s 1).
For the first claim, take any & = (f) ( E G. Let s' be the unnormalized version of (s)s) of Eq. (22), that is, xp (s,i,) for the same i.j as Eq. (27)) (i.e., with the largest (2-norm). Then, using that G G.
range ( (s)
max max (Fe(s. 0t) s llv''le ke|dol (.j
max |105|l2 s l1ve'l2 vdi +1 ke/dbl
Using that above in combination with | = v.w e B(1), 11 1, we obtain
V2dH2
by fssww < (Fo(s), v1) (F)(s), w) range G (s)
$ ( 112'11 vdi v2dH2
= |||il|1 vdi + V2dH2
8
As the cigenvalues of V(G = Σ Leog ph (o) (x) (r)) corresponding to the subspace which i lies are by definition at least y, we can write
(m)) V h. p i TVIG pp 2 ||-ill1
(range (s)) max
zEG
Combining with the previous result, we get that
(s) 2 vy |
2
| f(s)w/ = f(s)wl v2d 1H2
vy8
finishing the proof.
H Deferred proofs for Appendix 3.
The definitions (Eqs. (1) and (IT)
immediately give rise to the following facts:
H
D(s E
Tus H
C H] and T(-) E [0, 1], implying
(31)
(S:+) -
Fus H
c 1I-H, implying
u=1
E(s,)) E (s;) (x H| _ 2-
Furthermore, since either T(;;) 0 or (0: (as [())))) 0 implies that range (s:) and hence Ts;; are both zero), we have
Tr(F(s;-)) E(s=))
(32)
which used to establish the last part of Corollary mm
19

---

Proof of Lemma E. We drop the subscripts 0). Let (2.meii)) be the projection of to the subspace orthogonal Z(Q. f), denoted by Z(Q,i)* In other words, z= Pro)z(e.n)* V. Let M = yki fhi By the symmetry of M.
= Ō E G. Let v-w
My 2 M(v + +w) w Mw.
It is enough to prove therefore that
dH 2 M()+w).
As ||vl|2 s and ||v wll2 s 2, and using the definitions and Eq. (3II), for any input (s:-),
| (w) (g(s)) (r+ + w. (o(s;) E(s,))
v2d11
4Hr(ss)
4 range (s,))
1z, (o(s)))))
E
V2dH2
s < fe(ss))
(oe(s, b), b), 01) max keb,k
v2dH²
max |101l12 Projzien Fe(5) 11
kc[col
&
$ < Projzienn 4'112 vdi + V2dH2
8
where s' is the unnormalized version of (s;)) of Eq. (221), that is, 8' = pQ(si, b) for the same a. as in Eq. (221) (i.e., with the largest (2-norm).
As Projzie.n 4' (Po some a, E [.]. and by definition Projzce. Qi 3 1,21, ||Proizie.0 4'll2 s L (ll((s)))
(2 b)) Proiz Qi(((s, ((s, b)) for
= 2 11,
F((=))) w)] s $8452 Li di + V2dH2
(33)
and hence
1x pki (v + w) & LL,5L1 + v2dH2
(34)
To bound
y (ikk(v (v + w)}. note that by the definition yki,
z yl (v+ w)
1
Σ
cki
mkj (pck)
jo(mkk)..))
jE[m]
where
8" -
Σ
Gr
(kl (e (2TF(
R (+))(v)))))))))))
for E [i 1]
(kjel((t)
Therefore
T Ri v ww]
max Se [
(c(s.a).0r)
a),
Fix any e [t 1]. s S [A]. By repeated application of the fact that Xmo 2 Al, the triangle inequality, and using Eq. (53).
inequality, the
(v((s.a).01) s (1 a)lxxn!
Σ
&i 1k (TT ..... R (v +w)
(KJEIM(0)
(1)
V2dH2
s llll a))2 -L,2 L1 vd +
Σ
| uk
(kjelm(e)
V2dH2
s <8L,2
v dd
[I"(t)),
Σ
1kj |,
8
(kjel((()
22dH2
s 28,,2131112
Vdi +
m MmaxnIld
20

---

where we use that (r) & mnH, m I mmax by Lemma and that
Σ
|
1kil
Σ
(kj [kj 91 s Tr X Vd. Tr(X
X
IkjEl!
())E)((())
Combining with Eq.
(54)) with an appropriate choice of L3, we obtain
1 (=M s 8L3 L Livd vd v2dH2
(1+ L, 1/2
mmaxnHld 5 E
(35)
dH2
as desired.
Proof of Lemma D
Choose
12dgHL2
m H²
B 2+ 2 2H 2dH(do+ log
log
+ d log (d (/dd).
(36)
ag
satisfying B 2222) d) given in Eq. (LS)) and define
min (d(fff 1/ mma 170)
5V L)
Note that subtracting n/0 keeps positive, and of the same order, by our assumption that 1 is small enough: no0 min (/(dH> 1/ nma which follows from Eq. (2T).
We start with covering argument for the set of functions of the form vi F Fogw, for different choices of G, 0, v. and w. By [Vershymm, 2018, Corollary 4.2.13], there is a set Cę C ( with |Cel s (3/g)² such that for all x B(1) there exists a y E Cg with ||x yll z 5. Therefore, there is set Cº C (Xhet2 B (dv++1) x (Xnε(2.H) B(4dgHL2/a) x B(1) x B(1) with IC (12dgHL2/(aa()ddHHl such that for any G (0) (21mmii E G, 0 é, and v, B(1), there exists y C such that if we let G = ( (1 (y0- Ā (6))kε[2.H] = (yHH-))dthhheppa and a 1(d=))(d++))+)
(4=+)))4+)+++ then & G.
E 6, a, B(1), and
||a vll2 & and | - wll2 s S. and
100 8'112 S and ||0, 5nl1 SE for all h E [2: H), E [do].
As result, for all x S S raagee range (s)) s 2L1E. and therefore (TGg(s) (s)(s) s LiE/s. Furthermore, 1D (y..... - -Daass...,,Fi rF)) & LIE. Combining these with the facts that in either case, T(-) [0, 1], D(-) [-H, H), and E --) E [-H, H] (Eq. (BI),, and using the definition E and E .we we have that for any i [H + 1] and inputs,
(EGa(S))- -EG(s))) 4N2dH Lig/e Li5 + IE -E
H Σ
4N2dH2LLgEE LIE
|Eaa(s))) EGa(s)-)
s (H+ 1)5v2dH'
where the first inequality sums over the contributions of т, D, and E and the second applies induction. By combining this bound with the bounds on ||v - all2 and ||w - bllz. and that E(-)
[-2H, 2111 (Eq. (EII) implying that F(-) E [-2H1 2H), for all s E S Si, we have that
IT LTF (Fa( - Foobl (s) = 6Hg + (H+ 1)5v2dH2
(37)
(1 1V Lig/s min(s/(dIf=w)) 1/ nj0
Take any m' [m (this includes the entire execution of SKIPPYELFANOR) and let the quan- tities of Section (such F) be calculated with the value of Q the beginning iteration mi
21

---

(Line D). Take any e [H - 1]. [r+1: Take any y E C and assign values to b. G, and based y above. For any Ikj (r), observe that given all the history of SKIPPY ELEANOR interacting with the MDP up (and including) S A, the trajectory S A -........ R is an independent rollout with policy x², with its law given by P Px se.t sP., .AA.. The random vari-
able aj FG R ) has range 1-2H, 2H) and expectation (conditioned on this history) E st .At F Let On be On from Corollary [. satisfying ||0ull2 1/va and Eq. ([TI for a b, G, and 0 instead of Vp, w, G. and 0:
B a Fi =m (p(s..))0.)) R,s,
(38)
Take the sequence A formed of [kj (for jkj E (t), in the order that these random variables observed), and the sequence X formed of VI (5, ..... R )w (for 1kj E I'"(), the same order), and the sequence formed of E xs AA! Vnj Ga - (4, .u) (for Ikj E (") in the same order, for any G. and & as in the statement of this lemma). Then the sequences A, X, and A satisfy conditions of Lemma M.4 with subgaussianity parameter or 2/H. Due this lemma, with probability least [m H2 C2 (), for any choice of v, w, G, and (as above).
M max H2 121C/
det Xmr
100, Biillx... < <V21l0ull2+ || vII +H 2H 2 2
log
(39)
5
where
0.i =xm
Σ
fi o Feals
Ikj
R(b))w
(R)
union bound over all m' e [m 1, and y E C% guarantees with probability least C. the above holds for all choice of these variables, any time beginning of any iteration (Line 5 is executed. Note that need the union bound over because the value of Q underlying the targets of least-squares estimations can potentially change between iterations.
To finish the proof, under this bigh-brobybility event, take any m.t,i. G. and 0 as in the statement of this lemma, and choose E C² as before. to satisfy Eq. (B7). Combined with Eq. (38), this immediately implies that the sequence A formed of quantities with absolute value
(00 ...))
E sti
(40)
B (
s min(s/ (dHH)//dH22)) w), 1/ // vmmaxuHH) - -10 170
satisfies || 5 min(s/(dff 1/ 1/ nHI, Take any (s. E S, x [A], and let o, and o. be as above (in Eq. (E9) for VI, w, G. and 0. Note that
a)) a)
T0i gr
w (v(s,a))
22

---

By the triangle inequality, using Cauchy-Schwarz, and Eqs. (39) and (20))
i ((ss,)T(8)
00
B
Foo(Si) w
x.s.
(v) Or -(ii++
B 'ij "iFGG())) x....
((p((s,),,
s )1lp(s,))llx,
v. Vrll6
(r)l
2H
2
M C
+ llog
det Xmi
+
e
M Max nH
dd
dH2
12dgH112
mmnx H² 6
<llg(s,))llx))
2 2H 2dH(do + log
log
+ log (d+ mmmenH
+ dH2
or
s slle(s,a)lxx; B+ dFP
(41)
where the fourth line we used that [r) & nH, |C &
(12))HL2/(EE)))HHCC and
we used the inequality of arithmetic and geometric means to bound det Xmt ( Tr Xou
(013
Proof of Lemma E.5. Choose n to satisfy
wd
18dH 2m 2m'nax H22
64
H²
2d log
2d
log
(42)
82
&
5
This leads to n = Ô /66))
Similarly the proof of Lemma E
we start with a covering argument. This time, as Ô and Ø are e
fixed, we only consider v and w, to cover vi F w and vi (() w. Let g' = 12SHT There is a set C. (1)) B(1 with |Cg'l (3 such that for all v, w B(1), there exists an (a, b) E C² with ||v all2 s g' (and therefore ||||| aull2 I g"), and ||w bll2 e.. Take such choice of (a, b) for any (v. w). As E() [-2H, 2H) by Eq. (III,, and ( s For [2 : H] and any input,
6Hg'= = 2dH2 [ij F(s))) ai F(s
and therefore for any s E SES)S, S1. |T - aT s (2(2H)) For j [n] let
FGa(S ...... Rmkj)=
FGo(S
SHR ((A)
mAy B(A)
x² s.,skky a mnk pek)
20h)
By the triangle inequality, for any & [l-1], e [k 1k+1: H].
ki vi Y G8
- wl
1
Σ
mkjT gotmkf). TonkiTpomknn.. - Go
Σ
(Fti ( ..... Rmei)
ki
jE(n]
n1
jE[n]
ki
x-1
B+ m.pimkt
dH
8
+
dH2
8
+
Σ
c (Fft (
Rink)) b
jE[N]
je[n]
(43)
where the second inequality uses Lemma M and applies the triangle inequality twice again. Ob- serve that for all j [n], given all the history of SKIPPYELEANOR interacting with the MDP
23

---

up to (and including) stk) A mkj (which also includes the value of de for i E [H ID, the tra- smnj jectory +1k))+1> A mkk Rin p(K)+1>--.,, R is independent rollout with policy x², with its law given by are
Therefore, for any fixed (a, b) Cg.. 22 (r) Foa(S, ...... Rm² R........)))
P an smn Arki independent zero-mean random variables with range 1-4H,4H], Applying Hoeffding's s inequality with union bound over m', i, a, and b, with probability at least 1 Ç, for any of the m' E [miax]] times the beginning of the iteration (Line BD is executed (this includes the entire execution of SKIP- PYELEANOR),
2m mas H²| g"
Σ jE[n]
a (F) FF
Rm
RmL1))
8H V/
log
n
8H
18dH3
2m H²
E dH2
2d log
llog
vn
5
where we used Eq. (E2).. To finish, note that unless cf can continue from Eq. by bounding the average feature-norm by o as
0.
2(BlodH) so we
Fkki Ii (y - GB w/ BOBB+3 dH
Proof of Lemma 44
Recall that (k,i.)) v) are the arguments and x the value of Optimization Prob- Throughout the proof we write Q to refer to its value jaste before Line I is executed. We write for IK(.,)) and T for (((..) Let M yki fki Therefore, My = x o 3w+3 aw GB
lem 17
and by Lemma
Mw Jh +2 _
Line IK changes Q; by appending 2,'w the sequence C; of vectors from which Q is calculated according to Eq. (E)) Eq. (5) lists the conditions on the new sequence C, that need to be satisfied for to stay a valid preconditioning. Consider the third condition, i.e., 1|0, f s L3. Observe that
0 Projzig,n x L and ||v||2 1, therefore ||o, ' w|l2 = lle,- Projz ull = L3.
Now consider the second condition. To prove that it holds, we need to show that |10.0,'wll, ||w||2 2 1. Let Lemma
||w||5". Since v was the argument of the optimization problem, and using
w Mw s v Mr w Mw+ dII- w "wTM(1 1/2)
Therefore, ||w]]] 3. We immediately get that
le.er'wlß3 3
satisfying the second condition.
remains to prove that the first condition also holds. First, noting that M is symmetric, we can decompose w Mw
W Mw = w Mw + w Mw + WIM
Applying Lemma b on the first two terms.
w T Mw s 20 B+ + dH
www [[M
Due to w and w Mw > Bw 2 E T and the above, w, # Let w' wi/llwall ll2. Since was the argument of the optimization problem, have that v My 2 w Mww. Putting this together,
|| 11 w[Mw: =WTM"' Mw' v Mv w Mw
S 20 B
dH + w MM
dHF
24

---

Since Mr 0 Bls + 3 JHz w w [ww, 2 (w- (/3) [T +3 dHf-cs) the above by w] MW1,
0 and therefore dividing
7/3
|| w
+
w-7l 7/3
7/3
|| 2
for c
1+6 c
c 7/3
1
[w s 1 I+
as ||w||2 1.
Now prove that the first condition also holds,
sup (e. 2, w
|
sup (e, w>l
S sup
|10112 ||
1lll + sup
100, w w.)l
#c0;
acef
vd
sup
|00|| & xby by
|l
c
0
$ vd +
1 + 2dd
1
1 1
$ dd
+ 22y = vdi +
c+c
1 1+c 2
where in the second line we used Lemma used Eq. (26) with Cauchy-Schwarz. In the third line we used Eq. (24)), and the definition of Proj Finally the last line we use that w is perpendicular to a, for s (by definition) and that A S y
bound sup o ||0l12- and for the second term we
for > d'. It is left to prove that vdi + +1 14c s 5 This holds c 2 1/(4(di + 1) - 1), which is satisfied as 1/(3(d) 1)), due to = = 1) 7/3 (Eq. (T3)
I Deferred proofs for Appendix E.2
Proof of Lemma PK The features Pp(k) observed by SKIPPYELEANOS in the order of increas-
[kj
ing within that increasing k, and within that, increasing j. Each time the next pp(k) is observed, we sum the elliptic potential as follows.
For [m].r [H).u [m], [H), let the set of indices observed before eiru whose Phase II (rollout phase) starts at some stage be: Trr (r) (1 [i], [H]. [n]] IHH++ kn+ iHn and p(lkj) =1}
Let version of this where only the whole iteration i's data is included be
J'(r) (1 i,k e [H],j [n] p((kj) r}
Let
Xiru (1) = =1+
Σ
Ikj p(k) p(K)
Ikjel(n(()
Observe that Xir, defined in Optimization Problem I.10 is the version of this that only updates at the start of each iteration i, that is,
X = Xa)()).
The total elliptic potential, observed by the end of iteration m is, writing k p(iru) on the left hand side:
Σ
1 H 1) min 1
Σ min 1. 11
[kj 1 (
ie[m].re[H] (kj
Applying the elliptical potential lemma (Lemma
H times for t E [H], this can be bounded as
Σ Σ min I, 1
[kj
HmnL?
[x s 2dH log 1+ d1
1E [e[m] (1)
25

---

On the other hand, by Lemma L.2 then switching to an f1-bound, then observing that by definition, Σ o sums the same quantities but caps them by some threshold,
E E min (1.110 1k1l
Σ
min
1.
1
Σ
P1
Ikl
X
ikje (1)
Σ min
Σ
Σ
10
2
X
[c(m]
re|H (kje)((1)
Σ
Σ
| 1xx
2
min
1, 21H
[m[m
(E[H] (R)EF(()
Σ
1
Σ T kE[H]
21I
ie[m]
Whenever iteration finishes without returning in Line
L7
EREIHI T
e/ e/dff Therefore,
HmnL
2
2dH log
Σ min
n
T
dd
2Hn
/c(m]
k
Σ min
1
1, 2H n
dff-Bw
ie /c[m]
Σ min
{1, (1.dd/B²)
=
i=[m
Therefore, even for the iteration that returns in Line I7
Hmnl.
m S 8² log
1+
+ 1 mmax
dd
J Deferred proofs for Appendix
DK
Proof of Lemma E.8. For notational simplicity we drop the subscripts (G, 0). We first use the usual high-probability bounds on the least squares predictor and Hoeffding's inequality on the empirical mean quantities, to prove that with probability at least 1 3G, during the execution of SKIPPYE- LEANOR whenever Line IG executed, for & [/]],
CK.H+I xua
Σ (=p(()
E Ru Ex.H+1 (SSLiE"(SppS)..... Rh) 20 BwdH +
H
(44)
The proof of this is presented as Lemma
Next, prove the statement for [H], assume by induction that Eq. (22) holds for i [k+ H].
Observe that SKIPPYPOLICY performs a rollout with policy d for the rest of the episode starting from stage p(k) + 1, that is, Ap(R)+1 ables Sp(k++...... RH. given (Sp()), A Ap(x) is fully determined by the dynamics of the MDP, and independent of the values of p(k ().....,((I),, Therefore,
Aн Therefore, the law of the random vari-
"
B C = m .5
RH) +
Σ
Ru
gun
ump(k+1)
(45)
H
ŌL.HII ( (Sp(k)+)...,, RH) 1+)+
Σ
Rus
gmn
u=p(k+l)
26

---

where we use Eq. (H), and that nr (SKIPPYPOLICY) is in phase II after stage p(k), but defines the the mapping p()) independently whether the policy is in phase or phase II, in such way that for any H 2 j p(k).
P mm
[p(k + 1) 1)= ( S((k) A Ap(k) ame
p
r(S))
(1- (1-r(S)))) ((k) Ap(k) j'=p(k)+1
Combining Eq. (45) with Eq. (93).
p(k+l)-
E T .51
CI.H+IC(SS ((k))
E Σ x=p(k)
Ru + Bu+t2Ht.H+C((p(ee) + BwdH + &
x .1
H
By Remark EML, Exmi xy Ck+1,H++ +1 I (()p()))) B CL+1, C++l Therefore, combining with the inductive hypothesis,
p(k+l)-1
CK. (AHH+I(SSp())
Σ (=p(k)
Ry + Ektt 20 Budd
gunk
qonk
H
p(k+l)-1
H
H
Σ
Ru +
Σ u=p(k+1)
Ru + Σ
o BodH + +(H + 1) H
rll
(=)(k)
H
Ru + 2
o
BwdH + 4(H -
II
(F)(K)
i=k
where the last equation uses Remark again, finishing the induction.
Lemma J.1. Adopt the notation of Lemma F.R With probability at least 1 1-3G, during the execution of SKIPPYELEANOR, whenever Line IG is executed, for all [H).
H Σ
CL,HHI((SS(H)) mn .1
Ru ŌR E E (Sp(k)-t.... Rτ) 20 Bwdll +
8 H
TH .1 (=p(k)
Proof. We refer θ to the value of the argument of Optimization Problem I0 recorded in Line For & [H], recall the definition of Ttm (Eq. (I8), along with the fact that unless c2 = 2(BodH)-1 we get useful bound on the average norm of the features under
(P00) [x (.ppmaR))
consideration:
Σ c 2.
S o
(46)
x-11 Kmp(mnk))
je[m]
If Line is executed, the consistency check passed, and therefore for all [H-1],i [ H).
phi) Tr (r -hid-ppi) T Bwd
(47)
H12
For [H] let the least-squares predictor of rewards sums under the policy nº be
H
H1- = x-1
Σ
6
R
lkj
Ikjel" (7)
1=1
For E [H] and j E [n] let us introduce the shorthand
H Σ
pnk k
ump(ikk)
27

---

and similarly when the trajectory is clear from context: RR- = 2 2u=p(k) Ru. For & e [H] let
E
Σ jE[n]
(E
(S
p())+1 Runkl )+ + Rat
Ck
Σ
k K, C(Smm))
jE[n]
kHH++ n
Σ
( (pptis Aplme).HH.)
JE(N]
2.+++1
Σ
cl h, R
JEIN]
For [H 11, [1+1: H). along with 0+ let
8" = X
Σ
Ikj Ti(((S R()))) Xmm
Ikj
E(S ...,,
P1
Pi
(1)
(k)el"())
where the second equality is by Eq. (62). Observe that for any E Rd, Tr(v = (v. Öri). Therefore, for k e [H],
H+1
H+1
,.H.++++
Tr = Σ
Σ
Σ
che (omis BolmbDii)
Σ
ck
mkj
Σ (mp(mk
@oimkj)
p(R)
i=ke
JE[N]
]E[m]
For any E [H], by the definitions,
H+1
H
H +
Σ
Σ
Σ 1=1+1
E(S
[kk
>
Rinkj
mt
1=7+1
Ikjel((()
u=1
X-1
41
[kj
(S
241
Rlk)
R
0
Plugging this into the previous calculation,
Tr(y
ki)
1
Σ
ck. (pptk) Op(mkR))
k=
jE[m]
1
Σ
Ck. (pptk) Op(mks))
n je[n]
Σ JE[N]
Ch. ||| /
11ppmkk)) @p
(48)
1
Σ
che ( mks
(PpL (pimes) BH
[c[m]
1
Σ
de clipio.u1 ( (ppth) (pemkn)) -6 BH
n jE[n]
Σ JE[N]
C(Stnk) p(k) 3. BH = CK BH,
where the first inequality uses Cauchy-See -Shhha-S The second inequality bounds the average of the first norm by Eq. (HT)), and the bound on the second norm (for any j) is by definition of Optimization Problem II. The third inequality relies on the fact that c xx O if the clipped inner product is negative, and the final equality is due the definition of C along with the fact that Apkk) n (sm))) as this is the last state in the trajectory where SKIPPYPOLICY takes the inner-product maximizing action (xr* before rolling out with "
28

---

By Eqs. (12) and (62), we have that
H+1
2 Tr(Fki)
Σ k,H++
E(S
Ruhii + Ranly
ie[k+I:H]
n
je(u]
i=p(mn
(49)
Σ
ck k,H+1
E (S
p(K)+1''!. Rink) ) + Rmah) = Ex
jE[n]
Combining Eqs. (48) and (99).
Ck- E. & th BH + (yhHttt s(Htt)
Tr(yki phll
(e(k+I:H]
8m B1I +
B A
RE
zt p,HH+
o Budll
(50)
where the sum (last term) is bounded by Eq. (H.)), and we apply triangle inequality on the second term. To continue bounding this term, we apply Hoeffding's inequality on the independent random variables cf Hg RR- (for j E [n]) that have range [0. H]. along with union bound over the iteration m' E mmax and E [//], to get that with probability at least 1 1-5. 5.
2m H E H
B Jeme .8
CR.H+I R R k.H+1
log
(51)
Vn
5
dHf2
The remaining term | Bxnk, Ck. Rk- bounded using the realizability of qx (Defi- nition (.2) as follows. Take any / [H]. By definition there exists 6, E of S B(L2), such that for all s S, and
[T], q (s,a) ,n (f(s, a),aa))))) Take the sequence A formed of & (for Ikj E (r), in the order that these random variables are observed), and the sequence X formed of Rmnki (for [kj E (r)( in the same order), and the sequence A formed of q=" (s .A! ( ot) kk
(for jkj I")(), in the same order). Then the sequences X, and satisfy the conditions of Lemma M4 with subgaussianity parameter or = Н. Due to this lemma, applied with a union bound over m' e [mmax and 1 [H], with probability least 1 1-5.
m'nax 5
det X Xm
|| 0f < vo | (I) H 2 log
+ log
dd
m H
det Xms
2 H
2 2og
+ log
S B.
2d
by Eq. (II). Therefore by Cauchy-Schwarz and Eq.
HQ.
jkHH+l
xmR .8
E CR.H+I
S n
Σ
d
k,
x-1
(D(mk)).H-11
opmnR blxmn +
jE[n]
E dH2
. + The
Combining this with Eqs. (5l) and (51)
- f* & 1 BudHH 3 + dlf
(52)
We introduce the following notation for j [n], k E [H 1], [H 1]:
ki = p(mkj) < and || Xoommn
2 2(BwddH) and (omb) (pmpt)) 2
x-1
2/- ((mmk) i) < and (ymmas (p(me
<0/-
29

---

such that for all)
d c + ki + ck
(53)
Continuing from Eq. (22). as E E (s++)+ Σ Tu b Eq. (III) and et k,H+1 then C(S
p(k)
we have that
Σ CCH knn (C(Smmi)) SE(N]
pik) ((E (S- (S R Rin + RT-/) $ 1.50 BudtH+3 =+2
H dHf
As (even if of
= 1) ((S s H,
2,H+1
1 Σ K. ((Sp(r) S H (( ((((BdH))))))) o BudH,
N je[m]
which combined with the previous inequality and Eq.
(X3) yields
Σ je/m
2. (C(SSme) p(k)) - (E ((())) R Rmtl)) s 20 BwdH + + E
H dIP
Observe that the random variables C% H+1 p(R)) (S
(C(smk))
p(X)+1' RTh RTL)) are inde-
pendent (for j e [n]) with range 1-2H, H] (Eq, (6I)). By Hoeffding's ' inequality, with probability
least - for all iteration m' E [m/ (this includes the entire execution of SKIPPY ELEANOY and & [H].
ČR.H+I (C(Sp(k)) (Sp(K)) RH) RR-1))
mink
Σ jE(m]
El x,1 (C(Smb))) (000)(EE0 (E (SSR)1 ...., RT.k Rmal))
4H
2m 2m'maxh H
log
dH
Combining with the previous bound, under the intersection of the high-probability events referred to above, which by a union bound has a probability at least - -36, we have that for all k [H].
Er.H+IC(Spte
Σ
Ru +
RH) 20 Budll + + E H
u=p(k)
K Deferred proofs for Appendix E.4
Proof of Lemma E.TO Let m be the current iteration. Unlike in previous lemmas, here we in- troduce (G,8) 0) that does not refer to the outcome of Optimization Problem A. Instead, let G be the correct guess. For = H...., 1, O, is defined in sequence along with the behavior of policy æ stage h.
G (8) (
For h = H.....I 1, assuming that this process already defined 0bt1..... Ur (in Eq. (155), let æ be the policy that, for any h and S, takes action
( with probability (G) and action 1 with probability (s) (T defined in Eq. (E)). Simultaneously. using the second part of Corollary IIl define 0ni E B(4dgL2/a) for [h + H] to satisfy for all e St. a e [A]:
E Tr (()))(()) zm (p(s, a), 0nt)
x...a
We also define Hn B(L2) to satisfy for all Sn, a E [A]:
H
Σ
B
Ru n
30

---

By Eq. (22),
H
Σ
Tr(Foo(S)))
Σ
Ru E
RH) + Σ
Ru =m ()(s.a).0))
x.s.a ic
a=h
(54)
where we define
On
Σ Oni ic[h+1:H+1]
(55)
We first show that (G, 0) is feasible for Optimization Problem Clearly, ||āu]12 4dollLa/a. For any e [h + 1 M1, let
Oni
mh
Σ (k)
Ikj
Tr
( hol hel...... ................................ R(11).
and let
H
8
X-1 mh
Σ
[kj
R
h
Ikjelm(M
u=h
Then, ô of Optimization Problem I. satisfies for all h E [H). by Eq. (52).
0n
Σ
Oni
rE[h+I:H++]
To show that (G, 0) is feasible, thus suffices to show for all [H]. i e [h + 1 H + 1J. that [0m- @hillxm,, S B.
Fix any h [H] and i [h+1 1 H 1]. Take the sequence A formed of f (for 1kj E I""(h). in the order that these random variables are observed). For < H take the sequence X formed of Tr( Tr(F (S ....,R(/)) (for lkj (h) in the same order), and the sequence A formed of ", .A Tr(FGo(S)) ( Ikj Ona) (for Ikj (n)(),, in the same order). For H + 1, the [kj .B.)). ( Then the sequence is formed of Σ Ri and A is formed of grh (s A// (41
sequences A, X, and A satisfy the conditions of Lemma M with a subgaussianity parameter or H. Due to this lemma, applied with union bound over m' [m/nax] 1, and i, with probability least 1 1-6,
M''ax H²
det Xmm 2d
||0m Ghill @hillxmm
< <Vellenell> + || (I H 2 2log
log
m M/nn H2
det X
$ 2+ H 1
2
+ +og
$ B,
dd
by Eq. (II).
Next, show that the resulting policy is near-optimal. Assume induction on h H...., that for all I [h+ + H), all s E S, and a E [A],
(*(s) 2 v* (s) (H + 1)(EHH and (v(s, a). 0.) (H 9" (s.
(56)
(57)
To prove the above for h as well, take any s Sb. a E [A]. Introduce the random variable that, for trajectory following P. takes its value the index of the first Bernoulli draw of I (starting
from index h+ 1), when the Bernoullis have means (S,) for j E [h+1: : H], and takes the value
H 1 if all of these Bernoullis have outcome O. Write E P for Ex Bp[- Shel..... RH
31

---

Then.
H
E (So RH) + Σ ,..
Ru
E
@G ................................ RH) Σ Ru
umh
u=h
B
Σ
Ru + [ CG
x s.a. u=h
where we use Eq. (9). Combining with Eq. (D
P-1
a), 6n)
Hm
B
Σ
Ry
+ 1 ( H (Gp(p)
s.a.P
u=h
Ru 1 (P // 1] clip (s
E
x s.a,P 16ch
P- ER,
R H
E
Ru+ + 1 11p
s.a.
umh
where we used the inductive assumption along with the fact that action-valuee are bounded in [0, H]. Observe also that
P-1
(s)
E
Σ
Ru
+ + ( to (SP))
s.a.P ush
and therefore
(g(s, a), 6n) (HH---1) as)
proving Eq. (b.l) of the inductive assumption for 1 h.
To show Eq. (56) for h. by Eq. (577) for and the inductive assumption for
(g(s, (n) = q" (s, a) 2 q" (s, a) (H H 2HH
Either x chooses the action a' maximizing the inner product above, for which
qd (s, max 9* (s.a) (H- h)/ ( 2 2212 v* (s) (11 ())/:++)((///+22111 aE[A]
or it chooses action This can only happen with non-zero probability if (G)(s) in which case we have by definition that (s) = (s) ViTH
Combining with Eq. (L) and Proposition range(s) I W. and therefore, using Eq. (56) for r = h+ + 1, in this case
9²t (s. 1) 2 (s, 1) (H h)(e/HHHHHHH) 2H²
(s) H
20 2n - + 2 v* (*) (H h+ () 2H
Therefore for any choice of action a' of policy π in state s, (5 a') 2 v* -H H 202 Therefore
V (s) 2
- ()/HH -H 21)
finishing the induction.
We thus conclude that
Td (>1(s) 2 (*1) - 2HH -
Combined with Eq. (5.2) of the inductive assumption, the value of Optimization Problem can be bounded as
(s) cl (0(s), x(s))) H + ( v*(s) - -2c.
by assumption 17 being relatively small (Eq. (2I)).
32

---

L Deferred lemmas
Lemma L.1 (Elliptical potential, Lemma 19.4 from Lattimore and Szepesvárt [202]]. Let Vo Raxd be positive definite and a1 d1...,a, an Rd be sequence of vectors with || L < ca for all
I [n]. V Vo Essi azaz. Then,
min 1. ||: [|
log
det v det Vo s 2d log
Tr Vo + nL? ddct(V)))
Lemma L.2. Let V E R be symmetric positive definite matrix and (at)ieta) be sequence of d-dimensional real vectors. Let = V EeEl[ a.a.. Then,
Σ TE[N]
laill min 1.2
Σ Bailly-1 dE[m]
Proof. If EIEnn) a.a; z V, then Vi = 2V, and therefore
Σ Te[n]
|1 V
1a:ll ||ailly-1 fE[M]
Σ
Otherwise, Σie[n] "aaV-- has eigenvalue that is at least 1. As all the other eigenvalues are non-negative (as symmetric positive definite), we have that
|aill Tr Σ [E[M]
a;a V-1
2 1.
/E[M]
M Estimation error blow-up guarantees
We borrow Assumption M and Theorem M from Lattimore and Szepesvár 2020 and refer the reader to the book for the corresponding proof.
Assumption M.1 (Prerequisites for Theorem M.2). Lei variables taking values in Rd For some 0x Rd, let X (Ax, 0x) + me for all k e N Here, Te is a conditionally I-subgaussian random variable ("noise") "), ie. satisfies:
For N Ag be random
/a2
for all a E B and 2 1,
Blexp(amp) Fx-1] s exp
a.s.
2
where T2-1 is such that A₁, XI........ A X2-1, Ag are Te-1-measurable.
Theorem M.2 (Lattumore and Szepesvári [2020], Theorem 20.5), Let & E (0. 1). Under Assump- tion M. with probability at least t, it holds that for all k N,
||0x oblvv < 11 + 2 1
det (a)) 1d
log
where for k E N,
V&(1) = =1 Σ A,A
s=l
0. = -
X,Ar
We generalize this theorem handle non-zero-mean noise with parametrized subgaussianity. To
handle non-zero-mean noise, we use [Zanette et all 2020 Lemma 8]. We state the lemma here and refer the reader to Zanctie. at al 2020 for the proof:
33

---

Lemma M.3 (Zanette et al [2020, Lemma 8). For n E N let {Aitt=l..... be any sequence of
vectors in R and !=!)......... be any sequence of scalars such that / S 5 E R. with & 2 0. For any A and (()) 2 A|A] AI we have:
Σ
A
A
S ng²
v(2)1
Lemma M.4. Let ( E (0, A
and O. For k E N², let Ag be random variables taking values in Rd For some 8. & Rd let XR = (AR. 0+) + for all k E N Here, is conditionally -ssuaaussiann random variable, ie. satisfies:
a=222 B(exp(anqc) FR-1l s exp
for all a and 1,
a.S.,
where Fk-1 is such that AI.XI, Xi...., AK-1, Rx-1, Ak are FK- 7e-a-measurable. With probability at least 1 it holds that for any sequence {Ai)i=i... such that | for all k E N,
det Vx
11xx lxlva 111101112 + + o 2 2og
+ +lg
(
2d
where for E N,
Xx Xx + Ak
Vx(d) al Σ A,A
5=1
8. = Ve(a)= Σ
X,Ar
Proof. Let X (X+ Ax)/Ox.. = Ax/or, X' 2/0 and 02 -0. ==(()=='1 V
Σ AGATT
and 0 = vi( Σト X, By assumption, X A/. and 0' then satisfy Assumption M.Il
Therefore by applying Theorem M.2 with probability at least - 5. it holds that for all E N,
det (2))
|00 Ballvian 110+122 + V 2 log
2
Under this high-probabilte event, since Vi(a") = Va(///o2, substituting into the previous display yields
det (x) 2d
110: - -0+lllv < 11 + o 2 log
( log
(58)
Take any sequence (Ai)ial... such that |&i s & and apply the triangle inequality:
1 @xllv.co I 100 oxllv + +110%
dellvaco
(59)
so it remains to bound 110g 0Bllva
1002 -0000lllaa 0ellv.co
1(()-11 Σ - - v((a)- Σ X,A,
1=1
s=1
(2(1)
k
V((a)-1 -1 Σ
(X, 4,) - V2(1)-1 Σ
X₂
(60)
sml
sml
(2)
VAC2)=1 Σ A,A
Σ
=
4,A
(1
==1
S Vkg.
where the final inequality uses Lemma The proof is finished by plugging in the bounds of Eqs. (5%) and (60) into the triangle inequality of Eq. (59).
34


Reviews:
[{"review_id": "MZPwsx4gVM", "reviewer": "Reviewer_dNHS", "summary": "The paper addresses online RL in episodic MDPs under linear $q^\\pi$-realizability, where policy action values are expressed as linear functions of state-action features. This class is shown to be more general than linear MDPs, where only the transition kernel and reward function are linear functions of feature vectors. The key contribution is identifying states in linearly $q^\\pi$-realizable MDPs where actions have approximately equal values, enabling transformation into a linear MDP. A novel learning algorithm is derived to determine which states to skip and apply another learning algorithm to the linear MDP. The proposed algorithm achieves an $\\varepsilon$-optimal policy after $\\operatorname{polylog}(H, d) / \\varepsilon^2$ interactions, representing the first online RL algorithm for linearly $q^\\pi$-realizable MDPs with polynomial sample complexity. Notably, the results hold in the misspecified case, where sample complexity gracefully degrades with the misspecification error.", "questions": "1. What is the lower bound for MDPs with $q^{\\pi}$-realizability? It appears to have significant dependencies on both the time H and d.\n\n2. There seems to be an issue with the citation format. The requirement is to use an unnumbered first-level heading for the references.\n", "limitations": "The suggestions have been claimed in \"Weaknesses\" and \"Questions\".\n\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper offers a comprehensive exploration of Linearly $q^{\\pi}$-Realizable MDPs, making a significant contribution to the field of reinforcement learning with feature learning.\n\n2. The paper exhibits a clear and concise mathematical exposition with a well-structured presentation that is easy to follow.", "weaknesses": "1. The current form of the paper lacks a Conclusion section, rendering it incomplete.\n\n2. It would enhance clarity if the authors presented a comparative analysis in tabular form, providing a clearer understanding of the different studies involving MDPs with $q^{\\pi}$-realizability and linear structure.\n\n3. The paper has relatively few references, and the discussion of this line of work appears somewhat limited. It would be beneficial for the authors to discuss more related work in this area.\n\n4. The left and right sides of Figure 1 seem to be reversed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments, based on which we have added a table to the revised version of our paper containing the summary of how our work fits in the wider literature. In short, (i) for linear MDPs, Jin et al. [2020] provide algorithms with both polynomial sample and computational complexity for the online RL setting, and hence also for the planning with a simulator setting; (ii) for the case of linearly $q^\\pi$-realizable MDPs, Yin et al. [2022] provide a computationally efficient algorithm with polynomial sample complexity for planning (with simulator access), but no prior work has provided algorithms with polynomial sample complexity for online RL; (iii) we provide a computationally inefficient method for this case with polynomial sample complexity (the first such result in the literature), but whether this is achievable with an efficient algorithm remains an intriguing open problem. We also added a discussion to conclude the paper clearly pointing out directions for future work. Due to space limitations we focused our literature review to the strictly most relevant works that provide a sufficient context to fully understand our new results. We are more than happy to include discussions on any works we might have missed out; please share any suggestions with us in a reply.\n\nQ1. We are not aware of any lower bounds beyond those that apply to linear MDPs. This lower bound is $d^2H^4/\\epsilon^2$ (from converting Remark 9 of Zhou et al., 2021, “Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes” to our setting, in the latter of which  parameters are not shared across the stages). This bound matches the upper bound of ELEANOR (Zanette et al., 2020) up to logarithmic factors.\nWhile we therefore have the optimal dependence on $\\epsilon$, our exponents of $d$ and $H$ may be far from optimal, though we were unable to improve upon them. That said, our result is the first one establishing that this problem is polynomial-sample-complexity solvable, resolving an open problem of Du et al., [2019]. In our opinion this is the first and most important question to resolve, as it tends to establish a dividing line between tractable and intractable problems: polynomial-complexity bounds often can (and tend to) be improved upon, while problems shown to be exponentially hard tend to remain intractable even despite technological advances.\n\nQ2. Thank you, we will make sure our citation format complies with the formatting requirements.\n\nRe Figure 1, the sides of the figure are correct: The right MDP is obtained from the left one by removing (skipping) the states marked by red (and showing the cumulative rewards for the corresponding transitions). E.g., the two possible 2-step transition in the left MDP from $s_1$ to $s_4$ through $s_3$ with reward 0.5 for each transition is replaced in the right MDP with a single-step transition from $s_1$ to $s_4$ with reward 1 (for action 2, the action leading from $s_1$ to $s_3$ in the left MDP). Note that, as mentioned in the review of Wpjh, there is a typo in the caption and the feature of all other states should be $(0)$ not $(0.5)$.\n"}, {"review_id": "0Z4knnZTem", "reviewer": "Reviewer_ap44", "summary": "This paper studies online RL under linear $q^\\pi$ realizable MDPs, and proposes an algorithm that learns an epsilon-optimal policy in polynomial time and polynomial sample complexity.  Previous online RL in linear RL either assumes that transitions and rewards are linear individually (e.g., linear MDP), or assumes ergodicity (e.g., Politex), or assumes access to an simulator that can reset to a previously visited states (Confidence-MC-Politex). This work removes all these assumptions and show that as long as $q^\\pi$ is realizable for all $\\pi$, polynomial-time algorithm is possible. The novel and surprising observation is that linear $q^\\pi$ MDP is actually a linear MDP if the \"range\" of all states are large. The proposed algorithm is inspired by ELEANOR but \"skip\" low-ranged state in its execution, and at the same time refine the estimation for the range on the fly using some techniques related to optimal design.", "questions": "Can you give some high-level ideas of Optimization Problem 4.12? What are the meanings of $y^{ki}\\_{\\hat{G}\\bar{\\theta}}$ and $\\hat{F}^{ki}\\_{\\hat{G}\\bar{\\theta}}$? \n\nBesides, why do we need the for-loop in Line 6 in Algorithm 1? ", "limitations": "There's no potential societal impact. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 4, "strengths": "The observations and techniques in this paper are novel and creative. It answers an open question by Du et al. (2019) on whether sample-efficient RL under linear $q^\\pi$ MDP is possible. \n\n[Du et al., 2019] Simon Du, Sham Kakade, Ruosong Wang, Lin F. Yang. Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?", "weaknesses": "While I appreciate the technical contribution, the delivery of the result is far from ideal. The paper is very difficult to read. I have identified the following possible reasons: \n1. Highly cluttered notation.  I think a rule of thumb in writing math is to avoid super/subscript of super/subscript as best as we can, and keeping the super/subscript as simple as possible, because they can make the expression difficult to parse. However, this kind of notations is everywhere in this paper, like $\\hat{\\theta}\\_{\\hat{G}\\bar{\\theta}}^{p^{mkj}(k),i}$ or \n$||\\varphi_{p(k)}^{mkj}||\\_{X^{-1}_{m,p^{mkj}(k)}}$ where not only the super/subscript dependence is deep, each layer has many letters. It becomes a significant obstacle when tracing the calculations. Besides, for the notation $p^{mkj}(k)$, I did not find a place where the parameter in the parenthesis does not match the second parameter in the superscript, so maybe one of them can be omitted? \n2. The \"definition\" dependence is deep. This means that the definition of a quantity usually involves another quantity defined somewhere else; and when I visit the \"somewhere else\", it further requires me to understand other quantities defined in other places, and so on. For example, Optimization Problem 4.12 involves $y^{ki}\\_{\\hat{G}\\bar{\\theta}}$ and \n$\\hat{F}^{ki}\\_{\\hat{G}\\bar{\\theta}}$ for which I have to check the complicated Eq. (12) for their definitions. The $c^j_{ki}$ \nthere is further defined by a big quantity in (18) and the definitions of $\\varphi^{mkj}\\_{p(k)}$ and $\\hat{\\theta}\\_{\\hat{G}\\bar{\\theta}}^{p^{mkj}(k), i}$ are further scattered in the previous page which further requires understanding other quantities first. I think part the difficulty to trace is also because of Reason 1 --- the readers are facing highly cluttered notations in each step of tracing the definitions, and eventually cannot really grasp the overall meaning.  \n3. No reminders for the place of the definitions.  Since there are a big amount of cluttered notations, the readers easily forget where they are defined, so I think it's better that there could be reminders here and there to let the reader know where the notations are defined previously.  For example, when I first see $C_{\\hat{G}\\bar{\\theta}}$ in Line 279, I don't know where this is defined. After a long time, I realized that it is a result of the statement in Line 256-258 with the $C$ defined in (8). \n4. Confusing notation/terminology: In Line 188, $Z(Q,h)$ is defined as some subspace, but $Proj_{Z(Q,h)}$ is defined as projection onto its *orthogonal* space, which is counterintuitive notational-wise. As another example, in Line 266 or Line 4 of Algorithm 2, $\\tau$ is called a \"skipping probability\", but to my understanding, $\\tau$ is more like \"probability of *not* skipping\". \n5. Lack of high-level explanation. Though I can see that the authors have used a considerable space for describing the components of the algorithm, there are still many design choices left unexplained. For example, I don't quite understand why an additional index of k in Line 6 of Algorithm 1 is needed, and why we need to call Algorithm 2 with that input k. I also hope to see a more high-level interpretation of the $\\mathbf{f}$ defined in Line 240, or what does it implied if $v^\\top_{\\||(Q,h)} \\mathbf{f}w$ is $\\alpha$-admissible (Lemma 4.9 and Corollary 4.11). For example, what's the importance of this fact for the checking consistency procedure. The design of the regression target $E^{\\rightarrow}(s_i\\rightarrow)$ also deserves more explanation, e.g., what's the relation between this and the standard one in ELEANOR. \n\nI understand that the main text space is very limited. But I believe there is way to give a high-level explanation and self-contained story in the main texts, and leaving details to the appendix. Currently, the main text itself is crowded with difficult-to-trace notation and lacks necessary explanations. This also hinders me from making a careful check for the correctness of the proofs. So I suggest that the authors spend time re-thinking about how to present the results, to really make it a strong paper. \n\nOther notations I couldn't find corresponding definitions: \n- $B_i$ in Line 5 of Algorithm 2\n- $\\otimes$ in (12). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for bringing these presentational issues to our attention, and a special thanks for taking the time to provide useful concrete suggestions for improvement! The proof of our result uses many novel ideas and techniques, and we strived hard to present it well despite its inherent complexity (e.g., by introducing our definitions in a conceptually sensible order, accompanied by high-level descriptions). It was very useful to read where this presentation fell short, and we have correspondingly carried out the following improvements (which will appear in the revised/final version):\n\n- All instances of super/subscript of super/subscript were eliminated with a notational shorthand to remove the clutter (most notably, $p^{...}(.)$ becomes $p(...)$).\n- Clarifications and reminders were added to aid understanding, addressing (among others) all concrete confusion points noted in the review.\n- Added a high-level explanation for the decomposition of $E^\\to$ first into $E$, before decomposing $E$ into matrix-valued $F$ functions that will be used for Optimization Problem 4.12: “Since our realizability results in Section 4.2 only apply to functions defined at a given stage (as only memoryless policies are $q^\\pi$ -realizable), to be able to show that the least-squares targets are linearly realizable, we first decompose $E^\\to$ to directly express the effect of each stage in the trajectory (backwards).”\n- See [“global” response](https://openreview.net/forum?id=HV85SiyrsV&noteId=26AjXdraOA) that adds high-level explanation to the paper and addresses the reviewer’s point 5 and both questions.\n\nminor comments:\n- To point 4 of the weaknesses, the reviewer possibly misread this as $Proj_{Z(Q,h)}$ is defined as the (orthogonal) projection onto $Z(Q,h)$, not its orthogonal space (Definition 4.2). We fixed the confusing “skipping probability” terminology for $\\tau$.\n- $B_i$ is a Bernoulli random variable and is defined in Appendix B (in the revised version we added this to Algorithm 2), and $\\otimes$, defined in Appendix A, denotes a tensor product. We added the necessary pointers to make this clear.\n"}, {"review_id": "tPEB6hkMkZ", "reviewer": "Reviewer_Wpjh", "summary": "This paper proves that the standard online episodic RL with the $q^\\pi$-realizability assumption can be learned with polynomial samples, without generative models. Technically, this paper proves that the states of any MDPs with $q^\\pi$-realizability assumption can be partitioned into two disjoint sets, where the states in the first set have small range (i.e., the advantage function on the state is always small for every policy), and the transitions on the states in the second set can be approximated by a linear MDP. Consequently, this paper designs a novel algorithm called SKIPPYELEANOR that learns to distinguish the states with small range and the linear MDPs simultaneously. ", "questions": "In the last paragraph in Section 3, this paper argues that a MDP with $q^\\pi$-realizability can be converted to linear MDP by skipping the states with low range. Is this a rigorous reduction? How to construct the new MDP? In particular, the states are staged in the original MDP. By skipping some states, is the new MDP also staged, and is the stage of the un-skipped states unchanged?\n\n[Minor] In the caption of Figure 1, should the feature of all other states be 0 instead of 0.5?\n\n[Minor] What’s $S_h$ in the displayed equation after line 222?\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "This paper solves a long-standing open question of reinforcement learning theory by showing that MDPs with $q^\\pi$-realizability assumption can be learned with polynomial samples. The result is significant and beneficial to the community. The observation that the difference between MDPs with $q^\\pi$-realizability and linear MDPs is only the set of states with very small range is novel and neat. Conceptually, this observation deepens our understand on the $q^\\pi$-realizability assumption and can potentially inspire a new line of research.", "weaknesses": "The exposition of the results could be improved. Current Section 4 of this paper is very technical and involves too many symbols and definitions, which makes it less readable, despite the fact that the algorithm is conceptually simple. Is there a simpler setting that demonstrate the core idea of the algorithm while keeps the technical part less involved? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their helpful comments. We address their concern mentioned in “weaknesses” in the [“global” response](https://openreview.net/forum?id=HV85SiyrsV&noteId=26AjXdraOA) and answer their questions below:\n\nQ1. We do not show a formal reduction of $q^\\pi$-realizable MDPs to linear MDPs in this work. Though such a reduction is part of the intuition of our method, it is not strictly part of the proof sadly. The reason for this is that the skipping oracle mentioned is hard to learn, and instead of a direct approach we argue that learning about this oracle happens whenever there is a need (performance shortfall) for it.\nA formal reduction, while tangential to our proof, is fairly straight-forward but cumbersome, with the caveat that the linear MDP will end up with $dH$ (instead of $d$) dimensional features to account for the technicality about the stage mapping that you mention.\nOne would proceed by copying the features of each state $s$ in stage $h$ into the $h^{th}$ chunk of size $d$ of this vector of size $dH$ (the rest of the vector remains zero). A similar transformation is applied to all $\\theta_h(\\pi)$. Then, $H$ copies are made of each high-enough-range state, with all possible stages (but keeping the feature vectors). These will be the states of the new MDP we construct. When a transition from state $s$ leads to skipped states, the linear MDP returns with the copy of the first non-skipped state that has a stage counter of stage($s$)+1, so that in this linear MDP the stage numbers are consecutive (as required by our definitions). $q^\\pi$-realizability of this modified MDP is easy to show, and – as it has no low-range states – Proposition 3.4, can be used to show that the modified MDP is linear. To account for the fact that this new MDP may finish an episode in fewer than H steps due to the skips, we add a special, zero-reward, self-transitioning state called “episode-over”. To ensure that the MDP stays linear, we extend the feature vectors of each state by a scalar 1, and a scalar indicator of being in this state, with all original features of the “episode-over” state defined to be zero. It is easy to see that this construction leads to a linear MDP with the desired action-value functions.\n\nQ2. Yes, thank you for pointing out this typo.\n\nQ3. $S_h$ is the (random) $h^{th}$-stage state when an MDP trajectory is started from state-action $(s, a)$, and policy $\\pi$ is followed. Note the preceding expectation operator; this notation is introduced in Line 76.\n"}, {"review_id": "30lvfhPHAF", "reviewer": "Reviewer_PFYK", "summary": "This submission provides the first algorithm learning an $\\epsilon$-optimal policy with poly many samples obtained through online interactions with a $q^\\pi$-realizable MDP. This is an important contribution to an open question in the community. Indeed previous works either adopted a generative model or they required more stringent condition on the MDP class such as Linear MDP.\nThe core observations that might be useful for futures work are that:\n1) $q^\\pi$-realizability + strictly positive lower bound on the range $\\implies$ Linear MDP.\n2) In a $q^\\pi$-realizable MDP not only $q^\\pi$ are in the features span but also all admissible (see definition 4.6) functions.\n\nUnfortunately, the proposed algorithm is computationally inefficient as the authors mention at line 35 in the introduction.\nI think that this limitation should have been better discussed in the paper and mentioned in the abstract as well.", "questions": "1) Which is the output of Algorithm 2 ? In Algorithm 1, at line 7 the policy $\\pi^{mk}$ is defined as output of Skippy Policy which is not specified. Is it the policy that at state $S_i$ sample an action from $\\pi^+(S_i)$ with probability $\\tau_i$ and plays action 1 otherwise ?\n\n2) Is the quantity $E^{\\rightarrow}(s_i \\rightarrow)$ at line 275 be the same as the quantity $E_{G\\theta}^{\\rightarrow}(S_{t+1}^{lkj}, \\dots R_H^{lkj})$ used in the least squares target ?\n\n3) I couldn't follow your reasoning to show that $E_{G\\theta}^{\\rightarrow}(S_{t+1}^{lkj}, \\dots R_H^{lkj})$\n  is linearly realizable. In particular, Corollary 4.11 shows that is realizable for the true guess. However the solution to the Optimization Problem 4.10 is different from the true guess so in this case $E_{G\\theta}^{\\rightarrow}(S_{t+1}^{lkj}, \\dots R_H^{lkj})$ can not be guaranteed to be realizable. Could you please elaborate more on this step in the rebuttal ?\n\n4) Given the reduction from $q^\\pi$-realizable MDPs to Linear MDPs that you discovered in this paper. What would prevent one from applying efficient algorithms for linear MDPs such as LSVI-UCB to solve $q^\\pi$-realizable  MDPs ? Why did you choose to adopt the computationally inefficient Eleanor as base algorithm for solving Linear MDPs while computationally efficient alternatives exist ?", "limitations": "The limitations are not well discussed. In particular, I would suggest to add a discussion concerning the computational cost of the algorithm.\n\n**Minor**: typo at line 302 \"th matrix\" -> \"the matrix\"", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Learning an $\\epsilon$-optimal policy with poly many samples obtained through online interactions with a $q^\\pi$-realizable MDP was an open question before this paper (to the best of my knowledge). This paper solves it with an elegant approach unveiling the fact that $q^\\pi$-realizable MDP are not linear MDP due to the existence of some low range states.\nHowever this states are unimportant for the goal of finding an optimal policy and therefore in these states we can fix an arbitrary policy and reduce a $q^\\pi$-realizable MDP to a Linear MDP with features norm bound inversely proportional to the range lower bound.\nThe authors further develop their algorithm to bypass the requirement of knowing the low range states in advance.\nI think this reduction to Linear MDP will be important for further advancements in the field. ", "weaknesses": "I think the authors should have discussed better the fact that their algorithm is not computationally efficient.\nIn particular, I believe that the authors should explain that the computational barrier comes from Optimization Problem 4.10. This is probably obvious for reader already familiar with ELEANOR but I would still suggest to include this discussion in a Limitations section that the authors may want to add in their final revision. \n\nSome steps in the presentation might also be improved (please see questions in the next Section)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments. We answer their questions below:\n\nComputational complexity and Q4: Regrettably, we eliminated our discussion on computational complexity when shortening the initial submission -- thank you for pointing this out. We will include it in the final submission, as summarized below (also mentioning the inefficiency of the algorithm in the abstract).\nIn our opinion significant challenges remain to determine whether a computationally efficient solution exists, and this remains an interesting open problem.\nOur method (Optimization Problem 4.10) includes a guess of G, which impacts the optimization quantities in a non-linear way. Computationally efficient approximations tend to lead to the approximation error growing exponentially in H. This is the main reason we could not show the computational efficiency of our method. As such, we opted to use an ELEANOR-style algorithm instead of one of LSVI-UCB-style, as the LSVI-UCB-style method would not present any advantages but (with our proof) would in fact result in worse sample complexity and would also make the presentation (even) more complex.\n\nQ1. SkippyPolicy is a policy in the MDP (with no return value). In line 7 of Algorithm 1, $\\pi^{mk}$ is the policy defined by SkippyPolicy$(\\hat{G},\\bar\\theta,k)$. We realized this was unclear and changed line 7 in the revised version to “Let $\\pi^{mk}$ be the policy defined by $\\text{SkippyPolicy}(\\hat{G},\\bar\\theta,k)$”.\n\nQ2. Yes (in the case that $i=t+1$). We drop the subscripts of $E$ when not needed (line 265) and introduce the $s_i \\rightarrow$ notation in line 268 to clean the notational clutter. We refer to states in a fixed trajectory with lower-case $s_i$ for the explanation in line 275 (and elsewhere), and denote random variables by upper-case in the least-squares target (and elsewhere). Please let us know if this is not presented well and we will improve it.\n\nQ3. You are right that the realizability of $E_{G\\theta}^{\\rightarrow}(S_{t+1}^{lkj}, \\dots R_H^{lkj})$ does not follow from Corollary 4.11 (and is not even true in general). In fact, we can only prove the realizability of this for the true guess (a fact we use to establish the optimism property of Optimization Problem 4.10). Once the optimism property is established, similarly to ELEANOR’s proof, we only need to learn (and make progress) whenever there is a discrepancy (i.e., a difference in the predicted and measured value for the optimistic policy). For ELEANOR, learning is always implemented in the form of an elliptical potential growth of the covariate-matrix, because the underlying least-squares targets are realizable. \nFor us, as we do not have realizability of $E_{G\\theta}^{\\rightarrow}(S_{t+1}^{lkj}, \\dots R_H^{lkj})$, the discrepancy can be either (as with ELEANOR) due to the elliptical potential growth of the covariate-matrix, but it could also be the result of our least-squares targets not being realizable.\nCorrespondingly, we need another component of the proof/algorithm to learn from these cases (Section 4.4, Checking consistency). This is why we introduce matrix-form versions of $E_{G\\theta}^{\\rightarrow}(S_{t+1}^{lkj}, \\dots R_H^{lkj})$, denoted by $F$. The guarantee of Corollary 4.11 can be used to show that projections of the matrix-form of the discrepancy (see Optimization Problem 4.12) align well with the $\\bot(Q, i)$ subspace. Consequently, we learn (and make progress) from the discrepancies that do not grow the elliptical potential of the covariate-matrix, as these stem from the non-realizability of $E_{G\\theta}^{\\rightarrow}(S_{t+1}^{lkj}, \\dots R_H^{lkj})$, an error we can learn from (Line 12 of Algorithm 1). For more information, please see the [“global” response](https://openreview.net/forum?id=HV85SiyrsV&noteId=26AjXdraOA), which includes an explanation of related ideas that we added to the paper.\n"}]

Author rebuttal:
Please see our individual responses to the reviewers. We use this space to address a comment made by multiple reviewers that the exposition of the results could be improved (thank you for this feedback). We provide below a high-level explanation of our method and proof compared to ELEANOR (such a description is also added the the revised version of the paper).

When setting up least-squares targets for the state-action pair $(S_t, A_t)$, ELEANOR uses $R_t + predicted \textunderscore value \textunderscore for(S_{t+1})$.
With this target we only require one on-policy rollout for each episode in order to get the least squares parameter estimate for all $H$ stages. In contrast, our least-squares targets are of the form of $R_t + … + R_{t+i} + predicted \textunderscore value \textunderscore for( S_{t+i+1})$, where $i$, the number of stages “skipped”, depends on the guess $\hat G$. The guess $\hat G$ is selected only in Optimization Problem 4.10, and we do not know its value at the time of data collection, so we cannot know which stages will have to be skipped. Therefore, (i) we need access to the rewards of the current policy at any stage (similarly to ELEANOR), and hence we run the current policy to any stage (including the last one); and (ii) perform rollouts with the fixed policy $\pi^0$ (from any stage) to be able to estimate the rewards $R_{t+1},...,R_{t+i}$ collected while skipping over $i$ stages (for any $i$). To ensure this happens for every stage, we start phase II from every stage $k$, resulting in the additional for loop in Algorithm 1 compared to ELEANOR. (Finally, the randomization in Phase I is applied to make the optimization problem smooth, as described from line 160.)

One could analyze this algorithm similarly to the analysis of ELEANOR if it were not for the fact that the least-squares targets we just introduced are not realizable in general. We can, however, prove the realizability of certain components of the matrix-valued version of these targets, $F$ (Lemma 4.9 and Corollary 4.11). This enables us to detect when the realizability of our least-squares targets fail, measure the direction (component) of the largest error, and learn from that. This is the job of Optimization Problem 4.12: 
$\hat{F}^{ki}_{\hat{G}\bar{\theta}}$ corresponds to the matrix-valued empirical measurements of $F$, 

while $y^{ki}_{\hat{G}\bar{\theta}}$ 
are the average predictions of the same quantities. If realizability were to hold, these matrices would be very close; if not, the direction of their largest discrepancy tells us something about $\bot(Q, i)$, and allows us to learn.

Optimism ties all this together: either there is no shortfall between predicted and measured $q$-values (and we are done) or we grow the elliptical potential of $X$ (the two cases present in ELEANOR), or we grow the elliptical potential of $Q$ (the new case due to the lack of realizability guarantees).


Meta-review: This paper resolves one of the major open problems in RL with function approximation: Linearly $q^\pi$-Realizable MDPs in the online setting. The paper gives structural lemmas by connecting $q^\pi$-Realizable MDPs with a seemingly significant broader class: linear MDP. All reviewers believe this paper makes significant contributions to the community. The AC agrees and recommends acceptance.
Please revise the writing according the reviewers' suggestions in the final version.
Decision: Accept (oral)