Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting

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

heading: 1 Introduction
text: Emerging reinforcement learning (RL) applications necessitate the design of sample-efficient solutions in order to accommodate the explosive growth of problem dimensionality. Given that the state/action space could be unprecedentedly enormous, it is often infeasible to request a 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 a result, the quest for sample efficiency cannot be achieved in general without exploiting proper low-complexity structures underlying the problem of interest.

heading: 1.1 Linear function approximation
text: Among the studies of low-complexity models for RL, linear function approximation has attracted a flurry of recent activity, mainly due to the promise of dramatic dimension reduction in conjunction with its mathematical tractability (see, e.g., Wen and Van Roy (2017); Yang and Wang (2019); Jin et al. (2020); Du et al. (2020a)). Two families of linear function approximation merit particular attention, which we single out below. Here and throughout, we concentrate on a finite-horizon Markov decision process (MDP), and denote by S, A and H its state space, action space, and horizon, respectively.
• Model-based linear representation. Yang and Wang (2019); Jin et al. (2020); Yang and Wang (2020) studied a scenario when both the probability transition kernel and reward function of the MDP can be linearly parameterized. This type of MDPs is commonly referred to as linear MDPs. Letting Ph(· | s, a) be the transition probability from state s when action a is executed at step h,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
the linear MDP model postulates the existence of a set of predetermined d-dimensional feature vectors {ϕh(s, a) ∈ Rd} and a set of unknown parameter matrices {µh ∈ Rd×|S|} such that
∀(s, a) ∈ S ×A and 1 ≤ h ≤ H : Ph(· | s, a) = ( ϕh(s, a) )> µh. (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 a priori, which forms the basis for sample size saving compared to the unstructured setting.
• Value-based linear realizability. Rather than relying on linear embedding of the model specification (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 combinations of known feature vectors {ϕh(s, a) ∈ Rd}. A concrete framework of this kind assumes linear realizability of the optimal Q-function (denoted by Q?h at time step h from now on), that is, there exist some unknown vectors {θ?h ∈ Rd} such that
Q?h(s, a) = 〈 ϕh(s, a), θ ? h 〉 (2)
holds for any state-action pair (s, a) and any step h. It is self-evident that this framework seeks to represent the optimal Q-function — which is an |S||A|H-dimensional object — via H parameter vectors each of dimension d. 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?.

heading: 1.2 Sample size barriers with linearly realizable Q?
text: 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, we summarize key existing results for a couple of settings. Here and below, f(d) = Ω(g(d)) means that f(d) is at least on the same order as g(d) for d large enough.
• Sample inefficiency under a generative model. Even when a generative model or a 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 at least min { exp(Ω(d)), exp(Ω(H)) } samples regardless of the algorithm in use (Weisz et al., 2021b).
• Sample efficiency with a sub-optimality gap under a generative model. The aforementioned sample size barrier can be alleviated if, for each state, there exists a sub-optimality gap ∆gap between the value under the optimal action and that under any sub-optimal action. As asserted by Du et al. (2020a, Appendix C), a sample size that scales polynomially in d, H and 1/∆gap is sufficient to identify the optimal policy, assuming access to the generative model.
• Sample inefficiency with a 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 H steps to obtain a 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 a constant sub-optimality gap that cannot be solved without at least min { exp(Ω(d)), exp(Ω(H)) } samples.
In conclusion, the linear Q? assumption, while succinctly capturing the low-dimensional structure, still presents an undesirable hurdle for RL. The sampling mechanism commonly studied in RL literature precludes sample-efficient solutions even when a favorable sub-optimality gap exists.

heading: 1.3 Our contributions
text: 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, as summarized below.
A new sampling protocol: sampling with state revisiting. We investigate a flexible sampling protocol that is built upon classical online/exploratory formalism but allows for state revisiting (detailed
in Algorithm 1). In each episode, the learner starts by running the MDP for H steps, and is then allowed to revisit any previously visited state and re-run the MDP from there. The learner is 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 as local access to the simulator in the recent work Yin et al. (2021).
A sample-efficient algorithm. Focusing on the above sampling protocol, we propose a value-based method — called LinQ-LSVI-UCB — adapted from the LSVI-UCB algorithm (Jin et al., 2020). 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/∆gap, but is otherwise independent of the size of the state/action space.

heading: 2 Model and assumptions
text: We present precise problem formulation as well as a couple of key assumptions. Here and throughout, we denote by |S| the cardinality of a set S , and adopt the notation [n] := {1, · · · , n}.

heading: 2.1 Basics of Markov decision processes
text: Finite-horizon MDP. The focus of this paper is the setting of a finite-horizon MDP, as represented by the quintupleM = (S,A, {Ph}Hh=1, {rh}Hh=1, H). Here, S := {1, · · · , |S|} denotes the state space, A := {1, · · · , |A|} is the action space, H is the time horizon, Ph stands for the probability transition kernel at time step h ∈ [H] (namely, Ph(· | s, a) is the transition probability from state s upon execution of action a at step h), whereas rh : S × A → [0, 1] represents the reward function at step h (namely, we denote by rh(s, a) the immediate reward received at step h when the current state is s and the current action is a). For simplicity, it is assumed throughout that all rewards {rh(s, a)} are deterministic and reside within the range [0, 1]. 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 π = {πh}1≤h≤H represent a policy or action selection rule. For each time step h, πh represents a deterministic mapping from S to A, namely, action πh(s) is taken at step h if the current state is s. The value function associated with policy π at step h is then defined as the cumulative reward received between steps h and H under this policy:
∀(s, h) ∈ S × [H] : V πh (s) := E [ H∑ t=h rt(st, at) ∣∣∣ st = s] . (3)
Here, the expectation is taken over the randomness of an MDP trajectory {st}Ht=h induced by policy π (namely, at = πt(st) and st+1 ∼ P (· | st, at) for any h ≤ t ≤ H). Similarly, the action-value function (or Q-function) associated with policy π is defined as
∀(s, a, h) ∈ S ×A× [H] : Qπh(s, a) := E [ H∑ t=h rt(st, at) ∣∣∣ sh = s, ah = a] , (4)
which resembles the definition (3) except that the action at step h is frozen to be a. Our normalized reward assumption (i.e., rh(s, a) ∈ [0, 1]) immediately leads to the trivial bounds
∀(s, a, h) ∈ S ×A× [H] : 0 ≤ V πh (s) ≤ H and 0 ≤ Qπh(s, a) ≤ H. (5)
A 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 ? = {V ?h }1≤h≤H and optimal Q-function Q? = {Q?h}1≤h≤H respectively as follows ∀(s, a, h) ∈ S ×A× [H] : V ?h (s) := max
π V πh (s) and Q ? h(s, a) := max π Qπh(s, a),
with the optimal policy (i.e., the one that maximizes V π) represented by π? = {π?h}1≤h≤H .

heading: 2.2 Key assumptions
text: Linear realizability of Q?. In order to enable significant reduction of sample complexity, it is crucial to 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 a collection of pre-determined feature maps
ϕ = (ϕh)1≤h≤H , ϕh : S ×A → Rd (6)
and a set of unknown vectors θ?h ∈ Rd (1 ≤ h ≤ H) such that
∀(s, a, h) ∈ S ×A× [H] : Q?h(s, a) = 〈ϕh(s, a), θ?h〉. (7)
In addition, we assume that
∀(s, a, h) ∈ S ×A× [H] : ‖ϕh(s, a)‖2 ≤ 1 and ‖θ?h‖2 ≤ 2H √ d. (8)
In other words, we assume that Q? = {Q?h}1≤h≤H can be embedded into a d-dimensional subspace encoded by ϕ, with d ≤ |S||A|. In fact, we shall often view d as being substantially smaller than the ambient dimension |S||A| in order to capture the dramatic degree of potential dimension reduction. It is noteworthy that linear realizability of Q? in itself is a considerably weaker assumption compared to the one commonly assumed for linear MDPs (Jin et al., 2020) (which assumes {Ph}1≤h≤H and {rh}1≤h≤H 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
∆h(s) := min a/∈A?s
{ V ?h (s)−Q?h(s, a) } with A?s := { a : Q?h(s, a) = V ? h (s) } . (9)
In words, ∆h(s) quantifies the gap — in terms of the resulting Q-values — between the optimal action and the sub-optimal ones. It is worth noting that there might exist multiple optimal actions for a given (s, h) pair, namely, the set A?s is not necessarily a singleton. Further, we define the minimum gap over all (s, h) pairs as follows
∆gap := min s,h∈S×[H] ∆h(s), (10)
and refer to it as the sub-optimality gap throughout this paper.

heading: 2.3 RL under sampling with state revisiting
text: In standard online episodic RL settings, the learner collects data samples by executing multiple lengthH trajectories in the MDPM via suitably chosen policies; more concretely, in the n-th episode with a given initial state sn0 , the agent executes a policy to generate a sample trajectory {(snh, anh)}1≤h≤H , where (snh, a n h) 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 a constant sub-optimality gap (Wang et al., 2021b).
A 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. 1 Input: initial state s1. 2 Select a policy and sample a length-H trajectory {(st, at)}1≤t≤H . 3 repeat 4 Pick any previously visited state sh in this episode; 5 Execute a new trajectory starting from sh all the way up to step H , namely, {(st, at)}h≤t≤H ; here, we overload notation to simplify presentation. 6 until the learner terminates it.
As a distinguishing feature, the sampling mechanism described in Algorithm 1 allows 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 a simulator with arbitrary state-action pairs to get samples — is trivially subsumed as a special case of this sampling mechanism. Moving on to a 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 it can resume the game from this save point later on. In fact, rebooting the game multiple times from a saved point allows an RL 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 ≤ N ), the learner is given an initial state s(n)1 (assigned by nature), and executes the sampling protocol in Algorithm 1 until this episode is terminated.
• At the end of the n-th episode, the outcome of the learning process takes the form of a policy π(n), which is learned based on all information collected up to the end of this episode.
The quality of the learning outcome {π(n)}1≤n≤N is then measured by the cumulative regret over N episodes as follows:
Regret(N) := N∑ n=1 ( V ?1 ( s (n) 1 ) − V π(n)1 ( s (n) 1 )) , (11)
which is what we aim to minimize under a given sampling budget. More specifically, for any target level ε ∈ [0, H], the aim is to achieve
1
N Regret(N) ≤ ε
regardless of the initial states (which are chosen by nature), using a sample size T no larger than poly ( d,H, 1ε , 1 ∆gap ) (but independent of |S| and |A|). Here and throughout, T stands for the total number of samples observed in the learning process; for instance, a new trajectory {(st, at)}h≤t≤H amounts to H − h new samples. Due to the presence of state revisiting, there is a 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 1 (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 (e.g., Jin et al. (2018)). For instance, by fixing the initial state distribution to be identical (e.g., s(n)1 = s for all 1 ≤ n ≤ N ) and choosing the output policy π̂ uniformly at random from {π(n) | 1 ≤ n ≤ N}, one can easily verify that this output policy π̂ is ε-optimal for state s, as long as 1N Regret(N) ≤ ε.

heading: 3 Algorithm and main results
text: In this section, we put forward an algorithm tailored to the sampling protocol described in Algorithm 1, and demonstrate its desired sample efficiency.

heading: 3.1 Algorithm
text: 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, we 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 µh(·) = [µ(1)h , · · · , µ (d) h ] > ∈ Rd×|S| and wh ∈ Rd such that
∀(s, a, h) ∈ S ×A× [H] : Ph(· | s, a) = 〈 ϕ(s, a), µh(·) 〉 and rh(s, a) = 〈 ϕ(s, a), wh(s, a) 〉 .
In other words, both the probability transition kernel and the reward function can be linearly represented using the set of feature maps {ϕ(s, 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 a sample trajectory following the greedy policy w.r.t. the current Q-function estimate with UCB exploration; namely, an MDP trajectory {(snh, anh)}1≤h≤H 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:
Λh ← n∑ i=1 ϕ(sih, a i h)ϕ(s i h, a i h) > + λI, (12a)
θh ← Λ−1h n∑ i=1 ϕ(sih, a i h) { rh(s i h, a i h) + max a Qh+1(s i h+1, a) } , (12b)
Qh(·, ·) ← min {〈 θh, ϕ(·, ·) 〉 + β √ ϕ(·, ·)>Λ−1h ϕ(·, ·), H } , (12c)
with the regularization parameter λ set to be 1. Informally speaking, θh (cf. (12b)) corresponds to the solution to a 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 Λh (cf. (12a)) captures the (properly regularized) covariance of ϕ(·, ·) associated with these samples. In particular, 〈 θh, ϕ(·, ·) 〉 attempts to estimate the Q-function by exploiting its linear representation, and the algorithm augments it by an upper confidence bound (UCB) bonus
β √ ϕ(·, ·)>Λ−1h ϕ(·, ·) — a term motivated by the linear bandit literature (Lattimore and Szepesvári, 2020) — to promote exploration, where β is a hyper-parameter to control the level of exploration. The update rule (12c) 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 to make proper modification of the algorithm. To facilitate discussion, let us introduce some helpful concepts.
• Whenever we start a new episode or revisit a state (and draw samples thereafter), we say that a new path is being collected. The total number of paths we have collected is denoted by K.
• For each k and each step h, we define a set of indices Ikh := { i : 1 ≤ i ≤ k | θih 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 Ikh 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 to describe the algorithm. For the k-th path, our algorithm proceeds as follows.
• Sampling. Suppose that we start from a state skh at time step h. The learner adopts the greedy policy πk = {πkj }h≤j≤H in accordance with the current Q-estimate {Qk−1j }h≤j≤H , and observes a fresh sample trajectory {(skj , akj )}h≤j≤H as follows: for j = h, h+ 1, . . . ,H ,
skj+1 ∼ Pj(· | skj , akj ) with akj = πkj (skj ) := arg max a Qk−1j (s k j , a). (14)
• Backtrack and update estimates. We then work backwards to update our Q-estimates and the θ-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 ∆gap. More precisely, working backwards from h = H , we carry out the following calculations if certain conditions (to be described shortly) are met:
Λkh ← ∑ i∈Ikh ϕh(s i h, a i h)ϕh(s i h, a i h) > + I, (15a)
θkh ← ( Λkh )−1 ∑
i∈Ikh
ϕh(s i h, a i h) { rh(s i h, a i h) + 〈 ϕh+1(s i h+1, a i h+1), θ k h+1 〉} , (15b)
bkh(·, ·) ← β √ ϕh(·, ·)> ( Λkh )−1 ϕh(·, ·), (15c)
Qkh(·, ·) ← min {〈 ϕh(·, ·), θkh 〉 + bkh(·, ·), H } . (15d)
Here, we employ the pre-factor
β = cβ
√ dH4 log KH
δ (16)
to adjust the level of “optimism”, where cβ > 0 is some suitably large constant. Crucially, whether the update (15b) — and hence (15d) — is executed depends on the size of the bonus term bk−1h+1 of the last attempt at step h+ 1. 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 1.
Two immediate remarks are in order. In comparison to LSVI-UCB in Jin et al. (2020), the update rule (15b) for θkh employs the linear representation 〈 ϕh+1(s i h+1, a i h+1), θ k h+1 〉 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 is equivalent to 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 planning/exploration stage, and is intrinsically a value-based approach.

heading: 3.2 Theoretical guarantees
text: Equipped with the precise description of Algorithm 2, we are now positioned to present its regret bound and sample complexity analysis. Our result is this: Theorem 1. Suppose that Assumption 1 holds, and that cβ ≥ 8 is some fixed constant. Then for any 0 < δ < 1, and any initial states { s
(n) 1 } 1≤n≤N , Algorithm 2 achieves a regret (see (11)) obeying
1
N Regret(N) ≤ 8cβ
√ d2H7 log2 HTδ
T (17)
with probability at least 1− δ, provided that N ≥ 4c 2 βd 2H5 log2 HTδ ∆2gap
. In addition, the total number of state revisits satisfies
K −N ≤ 4c2βd 2H5 log2 KHδ ∆2gap . (18)
Algorithm 2: LinQ-LSVI-UCB with state revisiting.
1
1
Theorem 1 characterizes the sample efficiency of the proposed algorithm. Specifically, the theorem implies that for any 0 < ε < H , the average regret satisfies 1N Regret(N) ≤ ε with probability exceeding 1− δ, once the total number T of samples exceeds
T ≥ 64c2βd 2H7 log2 HTδ ε2 . (19)
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 (19) scales as a polynomial function of both d and H , it does not rely on either |S| or |A|. This hints at the dramatic sample size reduction when |S||A| far exceeds the feature dimension d and the horizon H .
8
Algorithm 3: Simple auxiliary functions. 1 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 j = 1, 2, . . . , h− 1 do 3 Set akj = a k−1 j , and s k j+1 = s k−1 j+1 .
/* a new round of sampling from step h. */ 4 for j = h, h+ 1, · · · , H do 5 Compute Qk−1j (s k j , a) according to (15d). 6 Take akj = arg maxaQ k−1 j (s k j , a), and draw s k j+1 ∼ Pj(· | skj , akj ).
7 Function update-remaining(): /* keep the estimates prior to step h unchanged. */ 8 for j = 1, 2, . . . , h do 9 Set θkj = θ k−1 j .
10 Function get-policy(): /* update the Q-estimates. */ 11 for 1 ≤ h ≤ H do 12 Set Qk−1h (·, ·) according to (15d). 13 πkh(·)← arg maxaQk−1h (·, a).
• A small number of state revisits. Theorem 1 develops an upper bound (18) on the total number of state revisits, which is gap-dependent but otherwise independent of the target accuracy level ε. 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 θkh and b k h (see (15b) and (15c), respectively), which consists of
solving a linear systems of equations and can 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, so the algorithm necessarily depends on |A|. In total, the algorithm has a runtime no larger than Õ(d2|A|T ), and requires O(d2H) 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 (11)), it is not difficult to translate our regret bound over the episodes to the one over the paths. To be more precise, let us denote the regret over paths as follows for distinguishing purposes:
Regretpath(K) := K∑ k=1 ( V ?1 ( sk1 ) − V πk1 ( sk1 )) . (20)
A close inspection of our analysis readily reveals the following regret upper bound Regretpath(K) ≤ 4cβ √ d2H6K log2 HT
δ +
4c2βd 2H6 log2 KHδ
∆2gap (21a)
with probability exceeding 1 − δ; see Section B.2 for details. This bound confirms that the regret over the paths exhibits a scaling of at most √ K.
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 our algorithm satisfies
E [ Regret(N) ] ≤ E [ Regretpath(K) ] ≤ 17c2βd 2H7 log2(KH)
∆2gap , (21b)
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 (21a). In fact, this is consistent with the recent literature regarding logarithmic regrets under suitable gap assumptions (e.g., Simchowitz and Jamieson (2019); Yang et al. (2021) 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 a generative model. In a 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 1) is substantially more restrictive and does not give us the freedom to 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(1/∆gap) times, one can guarantee sufficiently accurate Q-estimates in all state-action pairs, which in turn ensures πk = π? 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 poly(1/∆gap) number of samples such that πk 6= π?, 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/∆gap) 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, ah, sih+1)}i≥1 for the current state sh with all actions ah ∈ A. where sih+1 represents the i-th attempt to draw sample transition from sh. Assuming only V ? is linearly realizable, their sample complexity is on the order of (dH)|A|, and hence its sample efficiency depends highly on the condition that A = O(1). Additionally, Du et al. (2020b) proposed an algorithm — tailored to a 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.

heading: 4 Discussion
text: In this paper, we have made progress towards understanding the plausibility of achieving sampleefficient 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 suboptimality 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 a 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 information-theoretic sampling limits for various linear function approximation classes, and characterize the fundamental interplay between low-dimensional 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 thatQπ 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 is not permitted. All of these are interesting questions for future studies.
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 FA9550-19-1-0030, ONR N00014-19-1-2120, ARO YIP award W911NF-201-0097, NSF CCF-2106739, CCF-1907661, DMS-2014279 and IIS-1900140, and the Princeton SEAS Innovation Award. Y. Chi is supported in part by the grants ONR N00014-18-1-2142 and N00014-19-1-2404, and NSF CCF-2106778, CCF-1806154 and CCF-2007911. 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-2147546/2015447. Part of this work was done while Y. Chen and Y. Wei were visiting the Simons Institute for the Theory of Computing.

Review summaries:
Disclaimer: I am not an expert in theoretical RL. My review is thus restricted to the overall soundness of the manuscript.  The authors describe theoretical work proposing a new sampling strategy for the online linear Q* problem making it sample efficient. They 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.  

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. 

Recent work in RL has been seeking ways that RL can draw the kinds of generalization that we see in supervised learning. Recently, a couple groups obtained efficient RL algorithms by assuming that the reward and transition probabilities are linear combinations of some set of basis functions. A somewhat more appealing, weaker assumption would be for merely the Q-function (state-action value function) to be linear. Unfortunately, recent works also found hard examples of environments with linear Q-functions, that require exponential sample complexity. Indeed, even with a simulator, there are exponential lower bounds -- only recently have any kind of polynomial-time guarantees, with a polynomial dependence on the smallest gap between the value of any optimal action any any sub-optimal action.  This work proposes a new model in which linear Q-functions are learnable. The model can be seen as a weakening of the simulator model: whereas the  simulator model allowed the learner to query any state-value pair to get a  sample of the reward and transition functions, this model merely allows the  learner to return to states that it previously visited on some trajectory. 

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.