Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting
Authors: Gen Li
Yuxin Chen
Yuejie Chi
Yuantao Gu
Yuting Wei
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
linearly realizable optimal Q-functions
sub-optimality gap
state revisiting
sample efficiency

Abstract: Low-complexity models such as linear function representation play a pivotal role in enabling sample-efficient reinforcement learning (RL). The current paper pertains to a scenario with value-based linear representation, which postulates linear realizability of the optimal Q-function (also called the ``linear $Q^{\star}$ problem''). While linear realizability alone does not allow for sample-efficient solutions in general, the presence of a large sub-optimality gap is a potential game changer, depending on the sampling mechanism in use.  Informally, sample efficiency is achievable with a large sub-optimality gap when a generative model is available, but is unfortunately infeasible when we turn to standard online RL settings.  

We make progress towards understanding this linear $Q^{\star}$ problem by investigating a new sampling protocol, which draws samples in an online/exploratory fashion but allows one to backtrack and revisit previous states. This protocol is more flexible than the standard online RL setting, while being practically relevant and far more restrictive than the generative model. We develop an algorithm tailored to this setting, achieving a sample complexity that scales polynomially with the feature dimension, the horizon, and the inverse sub-optimality gap, but not the size of the state/action space. Our findings underscore the fundamental interplay between sampling protocols and low-complexity function representation in RL.  

Sample-Eficcient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting
Gen Princeton
Yuxin Chen Princeton
Yuejie Chi CMU
Yuantao Gu Tsinghua
Yuting Wei UPenn
Abstract
Low-complexity models such as linear function representation play a pivotal role enabling sample-efficient reinforcement learning (RL). The current paper pertains to a scenario with value-based linear representation, which postulates linear real- izability of the optimal Q-function (also called the "linear Q' problem"). While linear realizability alone does not allow for sample-efficient solutions in general, the presence of large sub-optimality gap a potential game changer, depending on the sampling mechanism in use. Informally, sample efficiency is achievable with a large sub-optimality gap when a generative model is available, but is unfortunately infeasible when we turn to standard online RL settings.
We make progress towards understanding this linear Q' problem by investigating a new sampling protocol, which draws samples in an online/exploratory fashion but allows one to backtrack and revisit previous states. This protocol is more flexible than the standard online RL setting, while being practically relevant and far more restrictive than the generative model. We develop an algorithm tailored to this setting, achieving a sample complexity that scales polynomially with the feature dimension, the horizon, and the inverse sub-optimality gap. but not the size of the state/action space. Our findings underscore the fundamental interplay between sampling protocols and low-complexity function representation in RI.
Introduction
Emerging reinforcement learning (RL) applications necessitate the design of sample-efficient solutions in order to accommodate the explosive growth problem dimensionality. Given that the state/action space could be unprecedentedly enormous, it is often infeasible to request sample size exceeding the fundamental limit set forth by the ambient dimension in the tabular setting (which enumerates all combinations of state-action pairs). As result, the quest for sample efficiency cannot be achieved in general without exploiting proper low-complexity structures underlying the problem of interest.
1.1 Linear function approximation
Among the studies of low-complexity models for RI., linear function approximation has attracted flurry of recent activity, mainly due the promise of dramatic dimension reduction in conjunction with its mathematical tractability (see, e.g.. Wen and Van Roy (2017); 7 Yang and Wang (2019): Jin et al. (2020); Du et al. (2020a)). Two families of linear function approximation merit particular attention, which single out below. Here and throughout, we concentrate finite-horizon Markov decision process (MDP), and denote by S, A and its state space, action space, and horizon, respectively.
Model-based linear representation. Yang and Wangl 2019) Jin et al. (2020): Yang and Wang (2020) studied scenario when both the probability transition kernel and reward function of the MDP can be linearly parameterized. This type of MDPs is commonly referred as linear MDPs. Letting Pa 8, a) the transition probability from state s when action a is executed at step
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the linear MDP model postulates the existence of a set of predetermined di d-dimensional feature vectors {5n (s. a) E ] and a set of unknown parameter matrices {un E [Rdx|S such that
(1) Similar assumptions are imposed on the reward function too. In words, linear MDP posits that the probability transition matrix is low-rank (with rank at most d) with the column space known priori, which forms the basis for sample size saving compared to the unstructured setting.
V(s,a) E S x A and 1 S H
Pa s, = (s)(s,a) ph-
Value-bused linear realizubility. Rather than relying on linear embedding of the model specifica- tion (namely, the transition kernel and reward function), another class of linear representation assumes that the action-value function (or Q-function) can be well predicted by linear combina- tions of known feature vectors {spn(s, a) E R. A concrete framework of this kind assumes linear realizability of the optimal Q-function (denoted by Q7, at time step h from now on), that is, there exist some unknown vectors (0% E [24) such that
(7(s, a) (vP((, a))
holds for any state-action pair (s, a) and any step h. It self-evident that this framework seeks to represent the optimal Q-function - which is an [|]A|[H-iimension) object - via H parameter vectors each of dimension Throughout this work, an MDP obeying this condition is said to be an MDP with linearly realizable optimal Q-function, or more concisely, an MDP with linear Q*
1.2 Sample size barriers with linearly realizable Q"
This paper focuses on MDPs with linearly realizable optimal Q-function Q". In stark contrast to linear MDPs that allow for sample-efficient RL (in the sense that the sample complexity is almost independent of [S] and |A| but instead depends only polynomially on d, H and possibly a certain sub-optimality gap), MDPs with linear Q" do not admit a similar level of sample efficiency in general. To facilitate discussion, summarize key existing results for couple of settings. Here and below, fd) = (d)( means that (d) is at least on the same order as g(d) for d large enough.
Sample inefficiency under generative model. Even when generative model or simulator is available - so that the learner can query arbitrary state-action pairs to draw samples from (Kearns and Singh 1999) one can find a hard MDP instance in this class that requires least min { {())(((d)) exp((I((f)) samples regardless of the algorithm in use (Weisz et al. 202
Sample efficiency with a sub-optimality gap under generative model. The aforementioned sample size barrier can be alleviated if, for each state, there exists a sub-optimality gap Ago between the value under the optimal action and that under any sub-optimal action. As asserted by Du et al. (2020a) Appendix C), sample size that scales polynomially in d, H and 1/Agap is sufficient to identify the optimal policy, assuming access to the generative model.
Sample inefficiency with large sub-optimality gap in online RL. Turning to the standard episodic online RL setting (so that in each episode, the learner is given an initial state and executes the MDP for Hi steps to obtain sample trajectory). sample-efficient algorithms are, much to our surprise, infeasible even in the presence of a large sub-optimality gap. As has been formalized in Wang et al. (2021b), it is possible to construct a hard MDP instance with constant sub- sub-optimality gap that cannot be solved without at least min { (x)(()(d)), exp())(H)) samples.
In conclusion, the linear Q* assumption, while succinetly capturing the cow-dimensional structure, still presents an undesirable hurdle for RL. The sampling mechanism commonly studied in RL literature precludes cumple-efficien solutions even when a favorable sub-optimality gap exists.
1.3 Our contributions
Having observed the exponential separation between the generative model and standard online RL when it comes to the linear Q* problem, one might naturally wonder whether there exist practically relevant sampling mechanisms more flexible than standard online RL yet more practical than the generative model - that promise substantial sample size reduction. This motivates the investigation of the current paper, summarized below.
A new sampling protocol: sampling with state revisiting. We investigate flexible sampling protocol that is built upon classical online/cxploratory formalism but allows for state revisiting (detailed
2

---

in Algorithm| T]. In each episode, the learner starts by running the MDP for H steps, and is then allowed revisit any previously visited state and re-run the MDP from there. The learner allowed to revisit states for an arbitrary number of times, although executing this feature too often might inevitably incur an overly large sampling burden. This sampling protocol accommodates several realistic scenarios; for instance, it captures the "save files" feature in video games that allows players to record player progress and resume from the save points later on. In addition, state revisiting is reminiscent of Monte Carlo Tree Search implemented in various real-world applications. which
assumes that the learner can go back to father nodes (i.e., previous states) (Silver et al. 2016). This
protocol is also referred to local access to the simulator in the recent work Yin et al. (2021)
A sample-eftciiet algorithm. Focusing on the above sampling protocol, we propose value-baser method - called LinQ-LSVI-UCB adapted from the LSVI-UCB algorithm (Jin et al.] (020). The algorithm implements the optimism principle in the face of uncertainty, while harnessing the knowledge of the sub-optimality gap to determine whether to revisit states. Our algorithm achieves a sample complexity that scales polynomially in the feature dimension d. the horizon H, and the inverse sub-optimality gap 1/Agap gap. but is otherwise independent of the size of the state/action space.
2 Model and assumptions
We present precise problem formulation as well couple of key assumptions. Here and throughout, we denote by |S] the cardinality of set S, and adopt the notation [n]] == (1,-.",0) n].
2.1 Basics of Markov decision processes
Finite-horizon MDP. The focus of this paper is the setting of finite-horizen MDP, represented
by the quintuple M = (S. (Pr) { H). Here, S = {1..... |S|} denotes the state space, A = (1.... [Al] is the action space, H the time horizon, Ps, stands for the probability transition kernel at time step h E [H] (namely, (- 8, a) is the transition probability from state s upon execution of action
step h), whereas r4 S A - [0. represents the reward function at step h (namely, we denote by Tx (s, a) the immediate reward received at step h when the current state is and the current action is a). For simplicity,
assumed throughout that all rewards (s, } are deterministic and reside within the range [0, 1J. Note that our analysis can also be directly extended to accommodate random rewards, which we omit here for the sake of brevity.
Policy, value function, and Q-function. We let π = ( represent a policy or action selection rule. For each time step h, Th represents deterministic mapping from S to A, namely, action n (s) is taken at step h if the current state is 8. The value function associated with policy n at step h is then defined as the cumulative reward received between steps h and H under this policy:
H
((s h) E x (H):
(s) E
Σ
re(se, at) 8t
(3)
Here, the expectation taken over the randomness of an MDP trajectory {st { induced by policy (namely, a = Te(ss) and $t+1 ~ P(- st, at) for any h < t S H). Similarly, the action-value function (or (-function) associated with policy ι is defined as
H Σ k=
sn = s, on =a ..
ass E SxxXXxXX H
(Tss,))== :
a))
(4)
which resembles the definition reward assumption (i.c., rn a) E [0, 1) immediately leads to the trivial bounds
except that the action at step h is frozen to be a. Our normalized
V(s, a. ft) E S x Ax H
0. V. (s) < H and
S Q7 (s. a) < a) H.
(5)
recurring goal in reinforcement learning is to search for a policy that maximizes the value function and the Q-function. For notational simplicity, we define the optimal value function
V = (Vi) Jisch and optimal Q-function Q* = =QA (QAhsshH respectively as follows Vi((s) == max V (s) and Q7 a) = max (7,
V(s, a, h) E S x A [
with the optimal policy (i.c., the one that maximizes V*) represented by n² {mAhSnhH.
3

---

2.2 Key assumptions
Linear realizability of Q² In order to enable significant reduction of sample complexity, it is crucial exploit proper low-dimensional structure of the problem. This paper is built upon linear realizability of the optimal Q-function Q* as follows.
Assumption 1. Suppose that there exist collection of pre-determined feature maps
4 = (ph)ighsH
(hh : S A R
(6)
and a set of unknown vectors 0g E RR (1 S H) such that
(s, ES Ax H
@h(,,a) (1pn 0%)
In addition, we assume that
Ikp s and |10 S 2// 2H
(8)
In other words, assume that Q' = 1ithishhh H can be embedded into d-dimensional subspace encoded by i,, with d <. [|S|[A]. In fact, we shall often view d as being substantially smaller than the ambient dimension [S||A]] in order capture the dramatic degree of potential dimension reduction. It is noteworthy that linear realizabilitty of Q in itself is considerably weaker assumption compared the one commonly assumed for linear MDPs (Jin et al., 2020) (which assumes (Phlishs H and frn hrsis are all linearly parameterized). The latter necessarily implies the former, while in contrast the former by no means implies the latter. Additionally, we remark that the assumption (8) is compatible with what is commonly assumed for linear MDPs; see, e.g.. Jin et al. 2020 Lemma B.1) for a reasoning about why this bound makes sense.
Sub-optimality gap. As alluded to previously, another metric that comes into play in our theoretical development is the sub-optimality gap. Specifically, for each state s and each time step h, we define the following metric
(x = min (v) (s, with A = {a (T( (s)) agA;
(9)
In words, (s) quantifies the gap in terms of the resulting Q-values - between the optimal action and the sub-optimal ones. worth noting that there might exist multiple optimal actions for given (s, h) pair, namely, the set A; is not necessarily a singleton. Further, we define the minimum gap over all (s, h) pairs as follows
gap
min s, SX
(s),
(10)
and refer to it as the sub-optimality gap throughout this paper.
2.3 RL under sampling with state revisiting
In standard online episodic RL settings, the learner collects data samples by executing multiple length- H trajectories in the MDP M via suitably chosen policies: more concretely, in the n-th episode with a given initial state sy. the agent executes a policy to generate sample trajectory {( (i)ssss where (5%, ax) denotes the state-action pair at time step h. This setting underscores the importance of trading off exploitation and exploration. As pointed out previously, however, this classical sampling mechanism could be highly inefficient for MDPs with linearly realizable Q*, even in the face of constant sub- ootimaltty gap (Wang al.) 2021b).
new sampling protocol with state revisiting. In order to circumvent this sample complexity barrier, the current paper studies a more flexible sampling mechanism that allows one to revisit previous states in the same episode. Concretely, in each episode, the sampling process can be carried out in the following fashion:

---

Algorithm 1: Sampling protocol for an episode with state revisiting.
Input:
initial state 81-
Select policy and sample length- H trajectory {(s,, as)ss
3 repeat
Pick any previously visited state sa in this episode; Execute a new trajectory starting from 8n all the way up to step H, namely, {(5t Hesess here, we overload notation to simplify presentation. until the learner terminates it.
As distinguishing feature, the sampling mechanism described in Algorithm aallows one to revisit previous states and retake samples from there, which reveals more information regarding these states. To make apparent its practice relevance, we first note that the generative model proposed in Kearns and Singh (1999); Kakade (2003) in which one can query simulator with arbitrary state-action pairs to get samples - is trivially subsumed as special case of this sampling mechanism. Moving on more complicated yet realistic scenario, consider role-playing video games which commonly include built-in "save files" features. This type of features allows the player to record its progress at any given point, so that can resume the game from this save point later on. In fact, rebooting the game multiple times from saved point allows an RI. algorithm to conduct trial-and-error learning for this particular game point.
As a worthy note, while revisiting a particular state many times certainly yields information gain about this state, it also means that fewer samples can be allocated to other episodes if the total sampling budget is fixed. Consequently, how to design intelligent state revisiting schemes in order to optimize sample efficiency requires careful thinking.
Learning protocol and sample efficiency. We are now ready to describe the learning process which consists of N episodes and our goal.
In the n-th episode (1 < n S. N), the learner is given an initial state s(() (assigned by nature), and executes the sampling protocol in Algorithm I Jntil this episode is terminated.
At the end of the n-th episode, the outcome of the learning process takes the form of policy x ("), which is learned based on all information collected up the end of this episode.
The quality of the learning outcome {T((") JishsN is then measured by the cumulative regret over N episodes as follows:
N
Regret [) = Σ (vr()(")) - (8) (s{")),
(11)
which is what we aim to minimize under given sampling budget. More specifically, for any target level e E [0, H), the aim is to achieve
Regret( N) S
regardless of the initial states (which are chosen by nature), using a sample size T no larger than poly(d, (d, H, 1 >/m)) (but independent of [S] and [AD. Here and throughout, T stands for the total number of samples observed in the learning process; for instance, a new trajectory {s ax) )ssen amounts H h samples. Due to the presence of state revisiting, there is difference between our notions of regret sample complexity and the ones used in standard online RL, which we shall elaborate on in the next section. An RL algorithm capable of achieving this level of sample complexity is declared to be sample-efficient, given that the sample complexity does not scale with the ambient dimension of the problem (which could be enormous in contemporary RL).
Remark (From average regret to PAC guarantees and optimal policies.). There is some intimate connection between regret bounds and PAC guarantees that has been pointed out previously (c.g.. Jin al. 2018)). For instance, by fixing the initial state distribution to be identical (e.g., (x) s for all 1 S n S N) and choosing the output policy मे uniformly random from (х<(m) S n S N), one can casily verify that this output policy से is s-optimal for state s, as long as N Regret(NN S.
5

---

3 Algorithm and main results
In this section, we put forward an algorithm tailored to the sampling protocol described in Algorithm and demonstrate its desired sample efficiency.
3.1 Algorithm
Our algorithm design is motivated by the method proposed in (Jin et al. 2020) for linear MDPs called least-squares value iteration with upper confidence bounds (LSVI-UCB) - which follows the principle of "optimism in the face of uncertainty". In what follows, shall begin by briefly reviewing the key update rules of LSVI-UCB, and then discuss how to adapt it to accommodate MDPs with linearly realizable Q" when state revisiting is permitted.
Review: LSVI-UCB for linear MDPs. Let us remind the readers of the linear MDP setting. We assume that there exist unknown vectors (.)(.) = [u M1h ( E RR [S| and w/ E B such that
V(s, a, h) E S A x H P...1 s, a) = (f((s, (s, a), (.) and r a) = (s((s, a). wn (s, a)). In other words, both the probability transition kernel and the reward function can be linearly repre- sented using the set of feature maps (v=(s.a)) a)).
LSVI-UCB can be viewed as a generalization of the UCBVI algorithm (Azar et al. 2017 (originally proposed for the tabular setting) to accommodate linear function approximation. In each episode, the learner draws sample trajectory following the greedy policy w.r.t the current Q-function estimate with UCB exploration; namely, an MDP trajectory {(s ] J is observed in the n-th episode. Working backwards (namely, going from step H all the way back to step 1), the LSVI-UCB algorithm in the n-th episode consists of the following key updates:
An
p(sh p(sh, (p)) + AI,
(12a)
8n t A,,' Σ plsh alt {ra(sh oh) + max Qu+t((h+1110))
(12b)
Qa(s.)) min (0n. PT. (T: ,),
(12c)
with the regularization parameter À set to be 1. Informally speaking, On (cf. (2b) corresponds to the solution to ridge-regularized least-squares problem tailored to solving the Bellman optimality equation with linear parameterization - using all samples collected so far for step h, whereas the matrix Ad (cf. (2a)) captures the (properly regularized) covariance of (p:,-) associated with these samples. In particular, (0n. ((:-)) attempts to estimate the Q-function by exploiting its linear representation, and the algorithm augments it by an upper confidence bound (UCB) bonus
3/ ((:)) A, ((:)) - a term motivated by the linear bandit literature (Ltttimore and Szepesvári 2020) to promote exploration, where 33 is hyper-parameter to control the level of exploration. The update rule (2cp also ensures that the Q-estimate never exceeds the trivial upper bound H.
Our algorithm: LinQ-LSVI-UCB for linearly realizable Q*. Moving from linear MDPs to MDPs with linear Q", we need make proper modification of the algorithm. To facilitate discussion, let us introduce some helpful concepts.
Whenever we start a new episode or revisit state (and draw samples thereafter), we say that new path is being collected. The total number of paths we have collected is denoted by K.
For each & and each step h, we define set of indices
_ = 1 <iis 02 is updated in the i-th path at time step h}
(13)
which will be described precisely in Algorithm 2 As we shall see, the cardinality of IA is equal to the total number of new samples that have been collected at time step h up to the k-th path.
We are now ready describe the algorithm. For the k-th path, algorithm proceeds follows.

---

In addition, the total number of Sampling. Suppose that we start from a state S at time step h. The learner adopts the greedy policy x$ = { hisish in accordance with the current Q-estimate {2) "hsiisH and observes a fresh sample trajectory {(5), afsssss as follows: for j h h + 1,....P H, with
s0+1 P3 af))
= = arg max (s
(14)
Backtrack and update estimates. We then work backwards to update our Q-estimates and the f-estimates (i.e., estimates for the linear representation of Q²"), until the UCB bonus term (which reflects the estimated uncertainty level of the Q-estimate) drops below a threshold determined by the sub-optimality gap A gap-- More precisely, working backwards from h = H. carry out the following calculations if certain conditions (to be described shortly) are met:
A
Σ (n of (a (s), d +I. II
(15a)
VET
of - (Mh)
Σ
spulhh an) (ra (o ah) (phtt oh+2) of 0
(15b)
IEZ
6/(-.-) - 3V 3B pn((,)) (AA)) -1 (p((sr),
(15c)
2 - min (Fn(.)), + +b((s:), 3
(15d)
Here, we employ the fre-factor
KH
B = = dH log 8
(16)
to adjust the level of "optimism", where C3 > 0 is some suitably large constant. Crucially, whether the update (15b) - and hence (15d) - executed depends on the size of the bonus term b141 of the last attempt at step h + Informally, if the bonus term is sufficiently small compared to the sub-optimality gap, then we have confidence that the policy estimate (after time step h) can be trusted in the sense that it is guaranteed to generalize and perform well on unseen states.
The complete algorithm is summarized in Algorithm 2 with some basic auxiliary functions provided in Algorithm 3 To facilitate understanding, an illustration is provided in Figure
Two immediate remarks are in order. In comparison to LSVI-UCB in Jin et al. (2020), the update rule (15b) for 0% employs the linear representation (yM++1 (4) (1+1): BR 0R++) without the UCB bonus as the Q-value estimate. This subtle difference turns out to be important in the analysis for MDPs with linear Q*. In addition, LSVI-UCB equivalent
first obtaining a linear representation of transition kernel P (Agarwal et al. 2019) and then using it to build Q-function estimates and draw samples. In contrast, Algorithm 2 cannot be interpreted as a decoupling of model estimation and plaminngeexploration stage, and is intrinsically a value-based approach.
3.2 Theoretical guarantees
Equipped with the precise description of Algorithm 2 now positioned to present its regret bound and sample complexity analysis. Our result is this:
Theorem 1. Suppose that Assumption 7 Tholds, and that cæ 8 some fixed constant. Then for any
0 < 8 < 1, and any initial states {s1m) VIEnEN Algorithm achieves a regret (see 11 obeying
(m)
1
H log? Regret(N) S &808
(17)
N
T
Aelg 12' log" A
HT
with probability at least 1 8. provided that N- state revisits satisfies
4e, 115 log
2
KH 8
K - N
(18)
A
gap
7

---

Algorithm 2: LinQ-LSVI-UCB with state revisiting.
inputs: number of episodes N, sub-optimality gap gap- initial states {si hSnSN. 2 initialization: h 0, n 0, B3 0 and IJ for all S J H. for k 1, 2, ... do call n² +- get-ppoiccy).
<- h +
if h then
T(() t x/-1.// record the up-to-date policy learned in this episode.
4 7. // start new episode.
n > N then
K and return. // terminate after N episodes.
Set the initial state s =
11
12
call sampling()./ collect new samples from step h; see Algorithm 3
/* backtrack and determine whether to revisit state and redraw new samples.
Set 0/ 0 and h H.
13
while and k (s +1 441) gapp (cf (5c)) do
14
_ + - (kk). // expand b whenever we need to update 0%
15
Update 8 according to (15b).
16
h h h 1.
18
call remainn-e O).gg)./.1 // keep remaining iterates unchanged; see Algorithm 3
I3
(s)aa)
(s).a
(5)
k
($).a)
(5
(5)
(3
(3)
( 43)
(st
ag)
(5
(st.at)
(x).a)
k 3
(st (stlat)
(st
(s)
(s
(s).at)
k
I
h
H =
8 ++1
Figure 1: Illustationn of II for a simple scenario where N 1, H = 3, and the number paths is K 4. After the path, the sampling process revisits state s/ twice (each time drawing one new sample), and then revisits state s to draw two samples from there. This episode then terminates as the conditions are met for all steps. red superseript indicates new state or new actions, and the orange line illustrates the sampling process. Here, I3 {1, 2, 3, 4), IJ {3, 4} and Ií {4), which record the paths where the linear representations are updated for each respective step.
Theorem characterizes the sample efficiency the proposed algorithm. Specifically, the theorem implies that for any 0 < < H. the average regret satisfies x Regret(NN) S with probability exceeding 1 d, once the total number T of samples exceeds
64cg d HJ log² HT 6
T 2
(19)
e2
Several implications and further discussions of this result are in order.
Efficiency of the proposed algorithm. We highlight several benefits of our algorithm.
Sample efficiency. While our sample complexity bound (9 scales polynomial function of both and H, it does not rely on either [S] or [A]. This hints the dramatic sample size reduction when [S|[ far exceeds the feature dimension d and the horizon H.

---

Algorithm 3: Simple auxiliary functions.
Function sampling ():
/* sampling from the beginning (if h = 0) or from a revisited state (if h > 0).
/* do not update samples prior to step h.
2
for 1.2.....
do
L Set a = a and 8ft1 = Sj+1.
/* a new round of sampling from step h.
for j h h 1..... H do
Compute Q (s), a) according to [5d).
Take a = arg max, - (sf,a) a), and draw sf+1 Pj( PJ(-1sf, a9.
Function update-remaining
/* keep the estimates prior to step h unchanged. for j = 11......1 h do
L Set 0² 05-1
10 Function get- get-policy():
/* update the q-estimates. for 1 1 h < H do
11
Set Q 10--11 (:.:) according to ([dd
12
(-) & arg max,, (,,a).
13
small number of state revisits. Theorem developp an upper bound (18) on the total number of state revisits, which is gap-dependent but otherwise independent of the target accuracy level e. As a consequence, as the sample size T increases (or when decreases), the ratio of the number of state revisits to the sample size becomes vanishingly small, meaning that the true sampling process in our algorithm becomes increasingly closer to the standard online RL setting.
Computational complexity and memory complexity. The computational bottleneck of the proposed algorithm lies in the update of 0z and by (see (15b) and (T5c), respectively), which consists of solving linear systems of equations and be accomplished using, say, the conjugate gradient method in time on the order of d2 (up to logarithmic factor). In addition, one needs to search over all actions when drawing samples, the algorithm necessarily depends on |A], In total, the algorithm has runtime no larger than (dd A(T), and requires (dd H) units of memory.
Cumulative regret over paths. Due to the introduction of state revisiting, there are two possible ways to accumulate regrets: over the episodes or over the paths. While our analysis so far adopts the former (see (1)), ) it is not difficult to translate our regret bound over the episodes to the one over the paths. To more precise, let denote the regret over paths as follows for distinguishing purposes:
Regret path (K) =
(Vi((s)) VT (s4)
(20)
k=1
A close inspection of our analysis readily reveals the following regret upper bound
HT 8
4c 11 log² KH 5
Regret (K) < 4cp da HeHHKlog
(21a)
A gap
with probability exceeding 6; see Section B.2 for details. This bound confirms that the regret over the paths exhibits a scaling of at most VK.
Logarithmic regret. Our analysis further leads to a significantly strengthened upper bound on the regret. As we shall solidify in Section B.2 the regret incurred by algorithm satisfies
17c3.d @ /1 log2 (KH)
E. (Regret(N)) < IE RRegret (K)
(21b)
2
gap

---

largely owing to the presence of the gap assumption. This implies that the expected regret scales only logarithmically in the number of paths K, which could often be much smaller than the previous bound (2 In fact, this is consistent with the recent literature regarding logarithmic regrets under suitable gap assumptions (e.g., Simehowitz and Jamieson (2019); Yang et al. (202T) for tabular MDPs and He et al. (2021) for the case with linear function approximation).
Comparison to the case with a generative model. We find it helpful to compare our findings with the algorithm developed in the presence of generative model. In nutshell, the algorithm described in Du et al. (2020a] Appendix C) starts by identifying a "well-behaved" basis of the feature vectors, and then queries the generative model to sample the state-action pairs related to this basis. In contrast, our sampling protocol (cf. Algorithm [T] is substantially more restrictive and does not give us the freedom sample such a basis. In fact, our algorithm is exploratory in nature, which is more challenging to analyze than the case with a generative model.
We shall also point out a technical difference between our approach and the algorithm in Du et al. (2020a). A key insight in Du et al. (2020a) is that: by sampling each anchor state-action pair for poly gap) times, one can guarantee sufficiently accurate Q-estimates in all state-action pairs, which in turn ensures Tek = n² in all future estimates. This, however, is not guaranteed in our algorithm when it comes to the state revisiting setting. Fortunately, the gap condition helps ensure that there are at most p (A/A))) number of samples such that T& * π², although the discrepancy might happen at any time throughout the execution of the algorithm (rather than only happening at the beginning). In addition, careful use of state revisiting helps avoid these sub-optimal estimates by resetting for at most poly(1/ /app times, which effectively prevents error blowup.
Comparison to prior works under state revisiting. Upon closer examination, the sampling mechanism of Weisz et al. (2021a) considers another kind of state revisiting strategy and turns out to be quite similar to ours, which accesses a batch of samples {(sh, an 1) for the current state 8% with all actions a₁ E A. where = represents the i-th attempt to draw sample transition from 8h- Assuming only V* is linearly realizable, their sample complexity is on the order of (dH ||4] and hence its sample efficiency depends highly on the condition that A = O(1). Additionally, Du et al. (2020b) proposed an algorithm tailored to setting with deterministic transitions - that requires sampling each visited state multiple times (and hence can be accomplished when state revisiting is permitted)); this algorithm might be extendable to accommodate stochastic transitions. Additional discussions of related works can be found in Section A in the supplementary material.
4 Discussion
In this paper, we have made progress towards understanding the plausibility of achieving sample- efficient RL when the optimal Q-function is linearly realizable. While prior works suggested an exponential sample size barrier in the standard online RL setting even in the presence of a constant sub- optimality gap, we demonstrate that this barrier can be conquered by permitting state revisiting (also called local access to generative models). An algorithm called LinQ-LSVI-UCB has been developed that provably enjoys a reduced sample complexity, which is polynomial in the feature dimension, the horizon and the inverse sub-optimality gap, but otherwise independent of the dimension of the state/action space.
Note, however, that linear function approximation for online RL remains rich territory for further investigation. In contrast to the tabular setting, the feasibility and limitations of online RL might vary drastically across different families of linear function approximation. There are numerous directions that call for further theoretical development in order to obtain a more complete picture. For instance, can we identify other flexible, yet practically relevant, online RL sampling mechanisms that also allow for sample size reduction? Can we derive the anformation-theoreee function approximation classes, and characterize the fundamental interplay between din-dimnnsionll representation and sampling constraints? Moving beyond linear realizability assumptions, a very recent work Yin et al. 2021) showed that a gap-independent sample size reduction is feasible by assuming that Qa is linearly realizable for any policy π. However, what is the sample complexity limit for this class of function approximation remains largely unclear, particularly when state revisiting not permitted. All of these are interesting questions for future studies.
sampling limits for various linear
10

---

Acknowledgments and Disclosure of Funding
The authors are grateful to Csaba Szepesvári and Ruosong Wang for helpful discussions about Weisz et al. (2021a) and Du et al. (2019 2020b), respectively. Y. Chen is supported in part by the grants AFOSR YIP award F-9550-19-11 10030, ONR N00014-19-1-2120 ARO YIP award W91INF-20. 1-0097, NSF CCF-2106739, CCF-
MMM-20042299 and 11S-1900140, and the Princeton SEAS Innovation Award. Y. Chi is supported in part by the grants ONR N00014-18- 1---8-1--112 and N00014- 114--99--2404 and NSF CCF-2106778, CCF- 1FF-1806144 and CCF-2207911 1. Y. Gu is supported in part by the grant NSFC-61971266. Y. Wei is supported in part by the grants NSF CCF-2106778, CCF-2007911 and DMS-214754662015555 5447. Part of this work done while Y. Chen and Y. Wei were visiting the Simons Institute for the Theory of Computing.
References
Abbasi- Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312-2320.
Abbasi-Yadkori,
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. (2019). Reinforcement learning: Theory and algorithms.
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020a). FLAMBE: Structural complexity and representation learning of low rank MDPs. arXiv preprint arXiv:2006. 10814.
Agarwal, A., Kakade, S., and Yang, L. F. (2020b). Model-based reinforcement learning with generative model is minimax optimal. Conference on Learning Theory, pages 67-83.
Agarwal, A., Kakade, S. M., Lee, D., and Mahajan, G. (2020c). Optimality and approximation with policy gradient methods in Markov decision processes. In Conference on Learning Theory, pages 64-66. PMLR.
Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang. L. (2020). Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR.
Azar, M. G., Munos, R., and Kappen, H. J. (2013). Minimax PAC bounds on the sample complexity of reinforcement learning with generative model. Machine leurning, 91(3):325-349,
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
Azuma, K. (1967). Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3)3357-367.
Baird, L. (1995). Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pages 30-37. Elsevier.
Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. (2020). Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprini arXi::2007.06558.
Dann, C. and Brunskill, E. (2015). Sample complexity of episodic fixed-horizon reinforcement
learning. Advances in Neural Information Processing Systems, pages 2818-2826.
Dimakopoulou, M.. Zhou, Z., Athey. S., and Imbens, G. (2019). Balanced linear contextual bandits. In AAAI Conference on Artificial Intelligence, volume 33, pages 3445-3453.
Du, S. S., Kakade, S. M., Lee, J. D., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021). Bilinear classes: structural framework for provable generalization in RL. arXiv preprint arXiv:2/03.1 10897.
Du, S. S., Kakade, S. M., Wang, R., and Yang, I. (2020a). a good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations.
11

---

Du, S. S., Lee, J. D., Mahajan, G., and Wang, R. (2020b). Agnostic Q-learning with function approx- imation in deterministic systems: Tight bounds on approximation error and sample complexity. Neural Information Processing Systems.
Du, S. S., Luo, Y., Wang. R., and Zhang, H. (2019). Provably efficient Q-learning with function approximation via distribution shift error checking oracle. Advances Neural Information Processing Systems, pages 8058-8068.
Even-Dar, E. and Mansour, Y. (2003). Learning rates for Q-learning. Journal of machine learning Research, 5(Dec):
Hao, B., Duan, Y. Lattimore. T., Szepesvári, C., and Wang, M. (2020). Sparse feature selection makes batch reinforcement learning more sample efficient. arXiv preprint arXiv:2011.04019
He, J., Zhou, D., and Gu, Q. (2021). Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171-4180
Jaksch, T., Ortner, R., and Auer, P. (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4).
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2017). Contextual decision processes with low Bellman rank are PAC-lcarnable. In International Conference on Machine Learning, pages 1704-1713. PMLR.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873,
Jin, C., Liu, Q., and Miryoosefi, S. (2021). Bellman Eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00815.
Jin, C., Yang, Z., Wang. Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR.
Kakade, S. (2003). On the sample complexity of reinforcement learning. PhD) thesis, University of London.
Kearns, M. and Singh, P. (1999). simite-sample convergence rates for Q-learning and indirect algorithms. In Advances in neural information processing systems, pages 996-1002.
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Lattimore, T., Szepesvari, C., and Weisz, G. (2020). Learning with good feature representations in bandits and in RL with generative model. In International Conference on Machine Learning. pages 3662-5670 PMLR.
Li, G., Cai, C., Chen, Y., Gu, Y., Wei, Y., and Chi, Y. (2021a). Is Q-learning minimax optimal? tight sample complexity analysis. arXiv preprint 1rX.v:2102.06548
Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, Y. (2021b). Breaking the sample complexity barrier to regret-optimal model-free reinforcement leariing accepted to Neural Information Processing Systems (NeurIPS).
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020a). Breaking the sample size barrier in model-based reinforcement learning with generative model. Advances in Neural Information Processing Systems, 33.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020b). Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. Advances in Neural Information Processing Systems (NeurIPS).
Long, J. and Han, J. (2021). An 12 analysis of reinforcement learning in high dimensions with kernel and neural network approximation. arXiv preprint arXiv:2 07794.
Modi, A., Chen, J., Krishnamurthy, A., Jiang, N., and Agarwal, A. (2021). Model-free representation learning and exploration in low-rank MDPs. arXiv preprint arX1v:2102.07035.
12

---

Munos, R. (2005). Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, pages 1006-1011.
Osband, I. and Van Roy. B. (2014). Model-based reinforcement learning and the Eluder dimension. In Proceedings of the 27th International Conference on Neural Information Processing Systems- Volume 1, pages 1466-1474
Osband, I,, Van Roy, B., and Wen, Z. (2016). Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pages 2377-2386. PMLR.
Shariff, R. and Szepesvári, C. (2020). Efficient planning in large MDPs with weak linear function approximation. arXiv preprint arXiv:2007.06188
Sidford, A., Wang, M., Wu, X., and Ye, Y. (2018). Variance reduced value iteration and faster algorithms for solving Markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms, pages 770-787. SIAM.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam,, V., Lanctot, M.. et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484
Simchowitz, M. and Jamieson, K. (2019). Non-asymptotic gap-dependent regret bounds for tabular MDPs. arXiv preprint 190500840
Touati, A. and Vincent, P. (2020). Efficient learning in non-stationary linear Markov decision processes. arXiv preprint arXiv:2010.12870.
Wainwright, M. J. (2019). Stochastic approximation with cone-contractive operators: Sharp foo- bounds for Q-learning. arXiv preprint arXiv:1905.06265.
Wang, B., Yan, Y., and Fan, J. (2021a). Sample-efficient reinforcement learning for linearly- parameterized mdps with a generative model. arXiv preprint arXiv:2 14016.
Wang, R., Du, S. S., Yang, L. F., and Salakhutdinov, (2020a). On reward-free reinforcement learning with linear function approximation. arXiv preprint arXiv:2006.11274
Wang, R., Salakhutdinov, R. R., and Yang, L. (2020b). Reinforcement learning with general value function approximation: Provably efficient approach via bounded Eluder dimension. Advances in Neural Information Processing Systems, 33.
Wang, Y., Wang, R., Du, S. S., and Krishnamurthy, A. (2019). Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint 19Xiv:19/
Wang, Y., Wang, R., and Kakade, S. M. (2021b). An exponential lower bound for linearly-realizable MDPs with constant suboptimality gap. arXiv preprint arXiv:2103.12690
Wei, C.-Y,, Jahromi, M. J.. Luo, H., and Jain, R. (2021). Learning anfinite-horizon average-reward MDPs with linear function approximation. In International Conference Artificial Intelligence and Statistics, pages 3007-3015.
Weisz, G., Amortila, P., Janzer, B., Abbasi- Yadkori, Y.. Jiang. N., and Szepesvári, C. (2021a). On query-efficient planning in MDPs under linear realizability of the optimal state-value function. arXiv preprint arXiv:2102.02049.
Weisz, G., Amortila, P., and Szepesvári, C. (2021b). Exponential lower bounds for planning in MDPs with lealarle optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR.
Wen, Z. and Van Roy, B. (2017). Efficient reinforcement learning in deterministic systems with value function generalization. Mathematics of Operations Research, 42(3):762-782.
Yang, K., Yang, I.., and Du, S. (2021). Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576-1584. PMLR.
13

---

Yang, L. and Wang, M. (2019). Sample-opiin parametric Q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004.
Yang, L. and Wang, M. (2020). Reinforeement learning feature space; Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR.
Yang. Z., Jin, C., Wang, Z., Wang, M., and Jordan, M. I. (2020). Bridging exploration and general function approximation in reinforcement learning: Provably efficient kernel and neural value iterations. arXiv preprint 2.00::2001.04622
Yin, D., Hao, B., Abbasi- Yadkori, Y., Lazié, N., and Szepesvári, C. (2021). Efficient local planning with linear function approximation. arXiv preprint arXiv: (0t::2008.0553
Zanette, A., Brandffobrener, D., Brunskill, E., Pirotta, M., and Lazaric, A. (2020a). Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. (2019). Limiting extrapolation in linear approximate value iteration. Neural Information Processing Systems.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. (2020b). Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, pages 10978-10989, PMLR.
Zhang, Z., Zhou, Y., and Ji, X. (2020). Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33.
Zhou, D., Gu, Q. and Szepesvari, C. (2020). Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. arXiv preprint arXiv:2012.08507.
Checklist
1. For all authors...
(a) Do the main claims made the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e-g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're you're
using/curating? [N/A]
14

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "bKgSKGH7O-m", "reviewer": "Reviewer_SUw4", "summary": "Recent work in RL has been seeking ways that RL can draw the kinds of\ngeneralization that we see in supervised learning. Recently, a couple groups\nobtained efficient RL algorithms by assuming that the reward and transition\nprobabilities are linear combinations of some set of basis functions. A\nsomewhat more appealing, weaker assumption would be for merely the Q-function\n(state-action value function) to be linear. Unfortunately, recent works also\nfound hard examples of environments with linear Q-functions, that require\nexponential sample complexity. Indeed, even with a simulator, there are\nexponential lower bounds -- only recently have any kind of polynomial-time\nguarantees, with a polynomial dependence on the smallest gap between the\nvalue of any optimal action any any sub-optimal action.\n\nThis work proposes a new model in which linear Q-functions are learnable.\nThe model can be seen as a weakening of the simulator model: whereas the \nsimulator model allowed the learner to query any state-value pair to get a \nsample of the reward and transition functions, this model merely allows the \nlearner to return to states that it previously visited on some trajectory.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nI'm not aware of anything quite like the revisiting model being proposed \npreviously, and so that is novel, as is the kind of use that is made of it.\nHow applicable it is, is debatable. The paper claims that there are \"several\nrealistic scenarios,\" but more or less only mentions save points in video\ngames as something beyond the simulator model.\n\nThe other angle one could take on this work is figuring out exactly how strong\nof a model is necessary to learn MDPs with linear Q-functions. I'm not on \nboard with this take, though, because I don't think it's the case that we have a \nton of natural environments that are known to have linear Q-functions. \nRather, we were hoping that the linearity assumption would allow efficient \nlearners to exhibit generalization in a realistic learning model, and I think the \nmessage of this line of work has been largely negative, that the linear \nQ-function assumption just isn't adequate for this purpose. So rather than\npursuing linear Q-functions, we just have to try to find a different \nassumption.\n\nIn summary, it seems like novel work in a novel but somewhat narrow model. I \nam a little dubious about the long-term impact, since learning to play video\ngames was supposed to be a stepping stone to real-world problems, not an end\nunto itself. It should probably be published somewhere, and NeurIPS has a \nhistory of taking work on some oddball directions, and I don't think it would\n*hurt* the conference to take this one. I wouldn't fight for it though.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, I think reasonably so.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "E4X84oP01l", "reviewer": "Reviewer_fsA9", "summary": "This paper introduces a new problem setting of RL with state resetting. It then proves a polynomial (in ) sample complexity bound under linear approximation with assumptions of (1) $Q^*$ realizability and (2) suboptimality gap $\\Delta $ bounded away from 0. This setting and bound helps to reconcile recent results under assumptions (1) and (2) of exponential lower bounds in the online setting with polynomial upper bounds in the generative model setting.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths:\n\n1. The result closes a gap in the literature. Namely, it helps to explain what sort of sampling procedure may be required to achieve polynomial complexity under $ Q^* $ realizability without a full generative model. This can help people working in this subfield to understand more precisely where the hardness of the online problem is coming from and could potentially inspire future work that leverages this insight.\n2. The algorithm technique is interesting and proof is clean. I especially liked the way that the index set $\\mathcal{I}$ is used throughout to very elegantly keep track of the resetting. The technical details of the proof are clearly presented in the appendix. \n3. The presentation of related work is clear and comprehensive. The paper clearly explains the state of the literature and the existence of a gap in the realizability plus gap setting between online and generative model sampling procedures. The paper clearly explains the background on linearity assumptions in RL. \n\n---\n\n### Weaknesses:\n\n1. The paper has a few issues with clarity with respect to the novel contribution. While the paper clearly presents related work and setup/background, it ends up spending so much space on it that the presentation of the novel results is rushed and often unclear. I think the paper would benefit from more exposition about the novel components described below.\n\n   a) The sample complexity definition is non-standard. This is necessary because the standard definitions do not quite make sense in the novel setting. My understanding is that the regret definition captures regret of each \"episode\", but with the state resetting this is not sufficient because it does not measure regret suffered after each reset on the new \"paths\". So, the paper must consider the sample complexity that accounts for the samples collected on the reset paths. However instead of considering a standard notion of sample complexity as the number of samples until we arrive at an epsilon optimal policy, the paper considers sample complexity until the average regret is below epsilon. This definition is a sort of mash-up between regret and sample complexity that at least to me does not fit very obviously into the literature. More discussion and clarity around this definition would be helpful. \n\n   b) The paper does not provide an adequate description of the resetting strategy. After staring at the algorithm for a while it seems to me that the idea is to continue resetting to step $ h $ until we have enough certainty about  $ s_h, a_h $ that we can make an update with uncertainty that is smaller than the gap $ \\Delta$. Intuitively this requires very many resets, but as the proof shows it is polynomially bounded. This was never really explained in the text and definitely caused confusion for me when reading it for the first time. This seems to be the main algorithmic contribution, so it should be emphasized more. \n\n   c) The proof is entirely relegated to the appendix. It would be helpful to at least give some high level ideas about the structure of the proof in the main text. I understand this was likely cut due to space constraints, but since it seems to be the main contribution of the paper, it would be nice to see more discussion of it in the paper itself.\n\n2. I am somewhat wary of the significance of the result for a few reasons:\n\n   a) It is not clear that the linearly realizable resetting setting is very useful beyond being a theoretical curiosity. The one example provided in the paper is that video games can be reset to previously seen states. I agree that with access to a simulator, state resetting is possible. But it also seems that with access to a simulator, more aggressive sorts of access to the generative model are also possible so it is not clear why one would need to constrain themselves to previously seen states. And on the other hand, in the real world resetting is clearly not possible.\n\n   b) The paper only considers one very specific set of assumptions: realizability plus gap. This is not to say that it is not a novel contribution, only that the impact of results in this setting does not have clear implications for practice or beyond this specific setup. It would be useful to examine the effect of access to state resetting under slight variants of this setting as well. For example: Does it help without the gap? Does it help with $ Q^\\pi$ realizability? Answering questions like these would boost the significance.\n\n\n---\n\n### Recommendation:\n\nWeak accept.\n\nI think the paper has a nice contribution that closes a gap in the literature with a technically elegant solution. However, I am wary about some issues with clarity and significance so I recommend a weak accept.\n\n---\n\n### Typos/minor comments/questions:\n\n1. The computational complexity analysis seems wrong. At each $ k $, the computation in (15b) needs to take k inner products to compute the regression target $\\langle \\phi_i, \\theta_{h+1}^k\\rangle$. I think this cannot be pre-computed since the $ \\theta_{h+1}^k$ is potentially different at each iteration. This means that the computation time should be $ O(d^2|\\mathcal{A}| T^2)$.\n2. Algorithm 3, line 9, the subscript should be $j$ instead of $h$\n3. Equation 23 the superscripts should be $ K $ instead of $ k $ \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does a poor job discussing the limitations of the approach. This seems to largely be due to space constraints as the paper didn't even have space to really discuss the main technical contributions. However, the paper could benefit from a better discussion of limitations and future directions that could build on the idea state resetting.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "BH1mGW46vDb", "reviewer": "Reviewer_UaTx", "summary": "Disclaimer: I am not an expert in theoretical RL. My review is thus restricted to the overall soundness of the manuscript.\n\nThe authors describe theoretical work proposing a new sampling strategy for the online linear Q* problem making it sample efficient.\nThey modify and extend the LSVI-UCB algorithms for linear MDP and show via regret analysis, that their sampling scheme with state revisiting leads to sample efficient algorithms -  a feature missing in previous studies in this particular setting with classic episodic sampling.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors present an algorithm extending LSVI-UCB.\nThe LSVI-UCB algorithm exploits the assumption that both the reward, transition are linear functions of feature maps to derive closed form updates for the Q parameters via - quoting the paper -a ridge regularized least squares problem tailored to solving the Bellman optimality problem. Exploration bonuses are added to the resulting Q value that reflect the uncertainty in the estimation of Q.\n\nThe extensions are twofold\n1) the ridge-regression type updates for the Q* parameters are done ‘bootstrapping’ from the bonus-less version Q* and not the upper bound.\n2) a new episode sampling  protocol : having sampled k episodes, selected a particular h in [0,H-1], episode k+1 consists of episode k copied till h, then completed with H-h steps starting from the initial state in episode k at state h.\n\nThe manuscript is well written, background and previous work on which this work is built on are discussed and summarized. The contribution and its consequences are also clear and thorough.\nI can’t comment much on the novelty or the details of the regret analysis and set my confidence score accordingly.\n\nSome comments to (possibly) improve the manuscript\n- the detailed algorithm 2 & 3 help a lot to understand the algorithm. Is there a typo in the update_remaining? Index j should be on the Qs\n- it took me a while to understand when states are revisited, that it depended on the algorithm variables (bonus and gap), and how it happened (along the backward pass, this is hidden in alg2 and line 250). The presentation does not reflect that dependence and until the ‘our algorithm’ section this is not described. I’d suggest to extend on that and to change line 4 of Alg 1 to reflect that.\n- This might be naive, but a broader and earlier discussion of the suboptimality gap (mentioned  from the start and defined page 40) would be helpful.\n\n------------------------------------\n## post rebuttal and discussion\n\nI have read the response (thanks), the other reviews and the discussion and maintain my appreciation of the manuscript\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "3Lat5Drgcwz", "reviewer": "Reviewer_w8yy", "summary": "This paper studies the sample complexity of RL with the linear Q^* assumption. Previous work has shown that this problem can not be solved with polynomial samples neither in the generative setting nor in the online setting even with a large gap between the value of the best action and the second-best one. Here the authors show that the additional assumptions of a sampling procedure which allows the learner to backtrack to previously-seen states (together with a large gap) is sufficient for polynomial sample complexity (albeit with sample complexity scaling with the inverse gap). The algorithm is based on the “standard” LSVI-UCB template. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results in this paper form a nice bridge between the online setting (where even a large gap does not suffice for sample-efficient learning) and the generative setting (where a gap condition can enable sample-efficient learning). The main sample complexity bound tells us that the full power of the generative setting is not needed and a “hybrid” interaction protocol can be sufficient. Since this result adds to the body of knowledge of sample efficient RL with linear function approximation, I am recommending acceptance, but with some suggestions/comments. \n\nIn terms of organization, the related works section should be moved out of the appendix and into the main paper. This can be merged with the discussion in section 1 and there are several other passages which repeat the same point (/are otherwise unnecessary) and can be cut (e.g. the “Sample Efficiency” paragraph of line 274 is not needed).\n\nOn the technical side: can the authors comment a bit more on the use of the gap condition? The “usual” application is that after poly(1/gap) number of samples at any state-action pair we have pi_k = pi^* for all future estimates. In Appendix C of Du et al. 2020a the estimates are performed at the anchor states which is then extrapolated over all features, giving pi_k = pi^star for that entire horizon and thus preventing the blowup of errors that comes with bootstrapping/LSVI methods. Is there a similar intuition here? \n\nI am also wondering why the rewards are assumed to be deterministic, as I did not notice anywhere in the proofs where that was essential. Can the authors elaborate on this point?\n\nThe result is also framed in a somewhat abnormal way. It is neither a regret bound scaling with N nor a PAC bound on the risk, but rather a PAC bound for the average regret. Can a full regret bound be obtained?\n\nIn terms of related work: the “limited revisiting” framework introduced here is not new (despite the claims of Section 1.2). In fact the cited work of Weisz et. al 2021a introduced a similar framework. \n\nSmaller comments on the writing: \n- line 24: ‘’unprecedentedly enormous’’ <- why is it unprecedented?\n- line 146: “The latter necessarily implies the former, while in contrast the former by no means implies the latter” <- that’s what being a weaker assumption means (stated in the previous sentence)\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned above there are a couple of technical issues which should be elaborated on/further developed and a couple of presentation issues (or related work issues) which should be corrected. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the RL problem under Q* linear realizability assumptions. This setting has been extensively studied in a stream of recent papers detailing impossibility results as well as positive results depending on whether access to a generative model and large suboptimality gaps are available or not. The authors make a non-trivial contribution in showing a positive (i.e., sublinear regret) in a novel online setting where the agent is allowed to to revisit previously traversed states. This setting is somewhat in between the full online and generative model scenarios and it is motivated in problems where the agent is not allowed to pick an arbitrary state in advance but it can record states and reset the system to states that have been visited in the past (e.g., games). While the scope of this setting could be debatable, it is overall reasonable and it sheds more light in the intricate limits of learnability in the Q* linear realizable case. Also, the theoretical and algorithmic contributions are non trivial. Overall, I believe the paper is likely to encourage further discussions in the community and inspire further research on the topic.

From rebuttal and the extensive discussion with reviewers, there are a number of elements that the authors should integrate in the camera ready version:
- The current main theorem is somehow difficult to parse as it "mixes" sample complexity and regret. I suggest to either explain these two contributions better or first summarize the overall result as a sublinear regret bound and then explain how it is obtain.
- As pointed out in the discussion, the final regret depends on 1/Delta^2. This suggests that the worst-case bound may be of order O(K^{2/3}). While the focus is actually to prove "learnability" (i.e., sublinear regret) and this may be overall unavoidable, I think it's worth pointing this out explicitly as it is a clear venue where people may focus to improve the current result.
- Acknowledge explicitly other limitations in the current version (e.g., knowledge of the gap). Again, this is not the first time this assumption is made, but it is worth making it very clear so as to encourage further research in this direction.
- Be sure to properly contrast your setting and results with Weisz et. al 2021a.
- The reviewers pointed out a few things that may need further clarification.


Decision: Accept (Poster)