Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
Authors: Bingyan Wang
Yuling Yan
Jianqing Fan
Venue: NeurIPS 2021 Poster (2021)
Keywords: model-based reinforcement learning
vanilla Q-learning
linear transition model
sample complexity
leave-one-out analysis

Abstract: The curse of dimensionality is a widely known issue in reinforcement learning (RL). In the tabular setting where the state space $\mathcal{S}$ and the action space $\mathcal{A}$ are both finite, to obtain a near optimal policy with sampling access to a generative model, the minimax optimal sample complexity scales linearly with $|\mathcal{S}|\times|\mathcal{A}|$, which can be prohibitively large when $\mathcal{S}$ or $\mathcal{A}$ is large. This paper considers a Markov decision process (MDP) that admits a set of state-action features, which can linearly express (or approximate) its probability transition kernel. We show that a model-based approach (resp.$~$Q-learning) provably learns an $\varepsilon$-optimal policy (resp.$~$Q-function) with high probability as soon as the sample size exceeds the order of $\frac{K}{(1-\gamma)^{3}\varepsilon^{2}}$ (resp.$~$$\frac{K}{(1-\gamma)^{4}\varepsilon^{2}}$), up to some logarithmic factor. Here $K$ is the feature dimension and $\gamma\in(0,1)$ is the discount factor of the MDP. Both sample complexity bounds are provably tight, and our result for the model-based approach matches the minimax lower bound. Our results show that for arbitrarily large-scale MDP, both the model-based approach and Q-learning are sample-efficient when $K$ is relatively small, and hence the title of this paper.

Sample-Efficient Reinforcement Learning for Linearly-Prrameterized MDPs with a Generative Model
Bingyan Wang' Princeton University bingyans@princeton.edd
Yuling Yan* Princeton University
yulingy@princetonn.c edu
Jianqing Fan Princeton University j q ggfanpprinceton.cm
Abstract
The curse of dimensionality is a widely known issue in reinforcement learning (RL). In the tabular setting where the state space and the action space A are both finite, to obtain a nearly optimal policy with sampling access generative model, the minimax-optimal sample complexity scales linearly with |S] x |AA, which can be prohibitively large when S or A is large. This paper considers Markov decision process (MDP) that admits set state-action features, which can linearly express (or approximate) its probability transition kernel. We show that model-based approach (resp. Q-learning) provably learns an e-optimal policy (resp. Q-function) with high probability soon the sample size exceeds the order of (1-1)*E> K
K
(resp. (I-7)1ez), ). up some logarithmic factor. Here K is the feature dimension and y (0. 1) the discount factor of the MDP. The results is applicable the tabular MDPs by taking the coordinate basis with K S) x [A]. Both sample complexity bounds are provably tight, and our result for the model-based approach matches the minimax lower bound. Our results show that for arbitrarily large-scale MDP, both the model-based approach and Q-lerniing are sample-efficiett when K is relatively small, and hence the title of this paper.
Introduction
Reinforcement learning (RL) studies the problem of learning and decision making in Markov decision process (MDP). Recent years have seen exciting progress in applications of RL. in real world decision-making problems such as AlphaGo [46, 47] and autonomous driving [33]. Specifically, the goal of RL is to search for optimal policy that maximizes the cumulative reward, based on sequential noisy data. There are two popular approaches to RL: model-based and model-free ones.
The model-based approaches start with formulating empirical MDP by learning the probability transition model from the collected data samples, and then estimating the optimal policy value function based the empirical MDP.
The model-free approaches (e.g. Q-learning) learn the optimal policy the optimal doction-)valus function from samples. As its name suggests, model-free approaches do not attempt to learn the model explicitly.
"qqual contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Generally speaking, model-base badel- approaches enjoy great flexibility since after the transition model is learned in the first place, it can then be applied any other problems without touching the raw data samples. In comparison, model-free methods, due to its online nature, are usually memory-efficient and can interact with the environment and update the estimate on the fly.
This paper is devoted to investigating the sample efficiency of both model-based RL and Q-learning (arguably one of the most commonly adopted model-free RL algorithms). is well known that MDPs suffer from the curse of dimensionality. For example, in the tabular setting where the state space S and the action space A are both finite, to obtain near optimal policy or value function given sampling access to generative model, the minimax optimal sample complexity scales linearly with [S] AA| [5. 2]. However contemporary applications of RL often encounters environments with exceedingly large state and action spaces, whilst the data collection might be expensive or even high-stake. This suggests a large gap between the theoretical findings and practical decision-making problems where [S] and |A| are large or even infinite.
To close the aforementioned theory-practice gap, one natural idea is impose certain structural assumption on the MDP. In this paper we follow the feature-based linear transition model studied in [63], where each state-action pair a) E S admits K dimensional feature vector ((s,, a) IR that expresses the transition dynamics P(-|s, a) Vrr(s, a) for some unknown matrix V RR S|x which is common for all (s, a). This model encompasses both the tabular case and the homogeneous model in which the state space can be partitioned into K equivalent classes. Assuming access to a generative model [31, 32], under this structural assumption, this paper aims to answer the following two questions:
How many samples are needed for model-base RL and Q-learning to learn an optimal policy under the feature- -bated linear transition model?
In what follows, we will show that the answer to this question scales linearly with the dimension of the feature space K and independent of [S] and |A] under the Teature-based linear transition model. With the aid of this structural assumption, model-based RI. and Q-learning becomes significantly more sample-efficiees than that the tabular setting.
Our contributions. We focus our attention on an infinite horizon MDP with discount factor Y (0, 1). We use s-optimal policy to indicate the policy whose expected discounted cumulative rewards are E close to the optimal value of the MDP. Our contributions are two-fold:
We demonstrate that model-based RL provably learns an e-optimal policy by performing planning based on an empirical MDP constructed from total number of
δ
K
samples, for all E (0. Here Ö(-) hides logarithmic factors compared to the usual O()) notation. To the best of our knowledge, this the first theoretical guarantee for model-based RL under the feature-based linear transition model. This sample complexity bound matches the minimax limit established in [63] up to logarithmic factor.
We also show that Q-learning provably finds an entrywise s-optimal Q-function using a total number of
( K (1 (1-7)' 62
samples, for all E E (0, 1]. This sample complexity upper bound improves the state-of-the -frth--rr result in [63] and the dependency the effective horizon (1 7) -4 is sharp in view of [34].
These results taken collectively show the minimax optimality of model-based RI. and the sub- optimality of Qelaaniing in sample complexity.
2

---

2 Problem formulation
This paper focuses tabular MDPs in the discounted infinite-horizon setting [10]. Here and throughout, A = {o E R Di=1 vi = 1, 2 0, [d] stands for the d-dimensional probability simplex and [N] = {1.2. NN for any N
Discounted infinite-horizon MDPs. Denote a discounted infinite-horizon MDP by a tuple M = (S,,,,rr.1) where S {1.... } is finite set of states, A = {1, ... -AAl) is a finite set of actions, P: S x A + -1 represents the probability transition kernel where P(s'ls a) denotes the probability of transiting from state s to state when action a is taken, 7 S x A - [0. 1] denotes the reward function where r(s, a) is the instantaneous reward received when taking action A while state 8 E S, and y E (0, 1) is the discount factor.
Value function and Q-function. Recall that the goal of RL is to learn a policy that maximizes the cumulative reward, which corresponds to value functions or Q-functions the corresponding MDP. For deterministic policy S + A and starting state E S, we define the value function as
v ss) E
Ar (sk: ax)
so =
for all E S. Here, the trajectory is generated by aμ = T(s)) and 88+1
P( [sx ag) for
every 0. This function measures expected discounted cumulative reward received on the trajectory {sk, (xx)))))))))) (x)) and the expectation is taken with respect to the randomness of the transitions 8841 P(-| (1,, (s)) on the trajectory. Recall that the immediate rewards lie in [0, 1]. it is easy to for any policy and state Accordingly, we define the Q-function
derive that 0 S (T(s)
for policy
(s) = E Σ r (8k, ax) 180 = 8,
for all (s, S x A. Here, the actions are chosen by the policy x except for the initial state (i.e. ak (sk) for all k 2 1). Similar the value function, can easily check that (s((s, a) S T-y for any т and (s. To maximize the value function or Q function, previous literature [9, 51] establishes that there exists an optimal policy x' which simultaneously maximizes V*(s) (resp. Q* (s, a)) for all s E (resp. (s, a) E S x A). We define the optimal value function V and optimal Q-function Q" respectively as
V (s) = max V (s) = V* (s),
Q' (s, = -max (s, = Q" (s,
for any state-action pair (s, a) ESXAA
Linear transition model. Given set of K feature functions Φ1, Φ2. .., ØK: S x A IR, we define & to be feature mapping from S x A to R.K such that
(s, = (oh a), , OK (s, a)] E K
Then we are ready to define the linear transition model [63] as follows.
Definition 1 (Linear transition model). Given a discounted infinite-horizon MDP M AS, P.r,)) and a feature mapping & S x A + RK, M admits the linear transition model if there exists some (unknown) functions VI, ", v/ - R, such that
K
p()1), = Σ de (8, the (s')
for every (s E S x A and s' S.
Readers familiar with linear MDP literatures might immediately recognize that the above definition the same as the structure imposed on the probability transition kernel the linear MDP model [63, 30, 65, 26, 52, 56, 60]. However unlike línear MDP which also requires the reward function r(s, a) to be linear the feature mapping (08, a), here we do not impose any structural assumption on the reward.
3

---

Example 1 (Tabular MDP). Each tabular MDP can be viewed as linear transition model with feature mapping Φ(s.a) = e(s,a) IR x| (i.e. the vector with all entries equal to but the one corresponding to (s, a) equals for all (s,a) E 8 x A. To see this, we can check that Definition 1 is satisfied with K = [S] x |A| and (s.a))
P(s' s, a) for each 8, E S and a E A. This example is a sanity check of Definition which also shows that our results (Theorem I and 2) can recover previous results on tabular MDP [2, 34] by taking K = [S] |A].
Example 2 (Simplex Feature Space). If all feature vectors {db(s, a)) (s. fall in the probability simplex - a linear transition model can be constructed by taking (x(+) to be any probability measure over S for all k E [
key observation is that the model size of linear transition model with known feature mapping ø is |8] K (the number of coefficients 4/x (s') in (1)), which is still large when the state space S is large. In contrast, it will be established later that to learn near-optimal policy or Q-function, we only need much smaller number of samples, which depends linearly on K and is independent of [S].
Next, we introduce a critical assumption employed in prior literature [63, 67, 45].
Assumption 1 (Anchor state-action pairs). Assume there exists set of anchor state-action pairs K C S A with |K| = K² such that for any (s, a) E S x A, its corresponding feature vector can be expressed as a convex combination of the feature vectors of anchor state sate-action pairs {(s, (8, E K.):
K ① (8,a)= = E (s,,a) for () and A (s, 0. (:(BL,))EK
(2)
Further, we assume that the vectors in (ő(s,a) (s, E K3 are linearly independent.
We pause to develop some intuition of this assumption using Examples I and In Example is straightforward to check that tabular MDPs satisfies Assumption with IC = S x A. In terms of Example without loss of generality we can assume that the subspace spanned by the features has full rank, i.e. span ((s, a): (s, a) E S x A} R (otherwise we can reduce the dimension of feature space). Then we can also check that Example 2 satisfies Assumption with arbitrary K C x A such that the vectors in {Ø(s. a) (s, a) E K.} are linearly independent. In fact, this sort of "anchor" notion appears widely in the literature: [3] considers "anchor word"' in topic modeling: [19] defines "separability" in their study of non-negative matrix factorization; [48] introduces "aggregate" in reinforcement learning: [21] studies "anchor state" in soft state aggregation models. These concepts all bear some kind of resemblance our definition of anchor state-action pairs here.
Throughout this paper, we assume that the feature mapping is known, which is a widely adopted assumption in previous literature [63, 30, 68, 26, 52, 56, 60]. In practice, large scale RL usually makes use of representation learning to obtain the feature mapping Φ Furthermore, the learned representations can be selected to satisfy the anchor state-action pairs assumption by design.
useful implication of Assumption is that can represent the transition kernel
P P(((s.a)= = Σ
Ne (8, P (+)
(3)
:((s,a))EK
This follows simply from substituting (2) into (1) (see (14) in Appendix A for a formal proof).
3
Model-based RL with a generative model
We start with studying model-based RL with generative model in this section. We propose model-based planning algorithm and show that it returns an e-optimal policy with minimax optimal sample size.
3.1 Main results
generative model and an empirical MDP. We assume access to generative model that provides us with independent samples from M. For each anchor state-action pair (8i, a;) E K. we collect N
Without loss of generality, one can always assume that the number of anchor state state-action pairs equals to the feature dimension K. Interested readers are referred to Appendix D for detailed argument.

---

independent samples (0 (7)) E [M]. This allows to construct an empirical transition kernel P where
K
N
P(d(0,0)= = Σ de (B,
(4)
5'} is an empirical estimate of P(s'(ss, a:) and then (3) is employed. With P hand, we can construct an empirical MDP M = (S, P .r, r),)). Our goal here is to derive the sample complexity which guarantees that the optimal policy of M is an e-optimal policy for the true MDP M. The algorithm is summarized below.
each (8,4) E A. Here, 1/ EE 160 = N
Algorithm 1 Model-based RL with generative model
Inputs: a set of anchor state-action pairs = {(s;, a,) : E [K]], feature mapping o : x A RK any planning algorithm P, target algorithmic error level Eopt.
For i = 1,..,, K do
Draw N independent samples B
P(-(si, a())si;a;)..- 1,
End for
Construct empirical MDP M A,,, where P can be computed by (4),
Output an Copt-optima policy of M computed by the planning algorithm P.
Careful readers may note that in Algorithm 1, {M(s, a) (s,a) E S x A} is used in the construction of P, while (A(s, a) (s, a) E S x AA} is not input into the algorithm. This is because given IC and ø are known, {A(s, a) (s, a) E 8 x A} can be calculated explicitly. The following theorem provides theoretical guarantees for the output policy मे of the chosen optimization algorithm on the empirical MDP M.
Theorem 1. Suppose that > 0 andd E (0, (1-7)) Let न be the policy returned by Algorithm 1.
Assume that
N 2 Clogg (K/ ((1 7))
(5)
71- E²
for some sufficiently large constant C > 0. Then with probability exceeding - 5,
4E
(* - Q3 (8. S 1-n¹
(6)
for every (s,a) E S x A. Here Eopt is the target algorithmic error level in Algorithm 1.
We first remark that the two terms on the right hand side of (6) can be viewed as statistical error and algorithmic error, respectively. The first term ε denotes the statistical error coming from the deviation of the empirical MDP M from the true MDP M. As the sample size N grows, E could decrease towards O. The other term 4 - ?) represents the algorithmic error where Sopt is the target accuracy level of the planning algorithm applied to M. Note that Eopt can be arbitrarily small if we run the planning algorithm (e.g. value iteration) for enough iterations. A few implications of this theorem are in order.
Minimax-optimal sample complexity. Assume that Copt made negligibly small, e.g. Copt O((1 - E)) to be discussed in the next point. Note that we draw N independent samples for each state-action pair (s, a) E K, therefore the requirement (5) for finding an O(p)ooptimal policy translates into the following sample complexity requirement
K
(1 (1-7)
This matches the minimax optimal lower bound (up to a logarithm factor) established in [63, Theorem 1] for feature-based MDP. In comparison, for tabular MDP the minimax optimal sample complexity is ②(11 -3==2|))|AA]] [5. 2]. Our sample complexity scales linearly with K instead of |S| |A| for tabular MDP as desired.
5

---

Computational complexity. An advantage of Theorem 1 is that it incorporates the use of any efficient planning algorithm applied to the empirical MDP M. Classical algorithms include Q-value iteration (QVI) or policy iteration (PI) [43]. For example, QVI achieves the target level Copt in Q((1 - -7) log Sopt) iterations, and each iteration takes time proportional to O(NK K + [S]]A[K). To learn an (e)-opiiial policy, which requires sample complexity (5) and the target level Copt = O((1 - )))), the overall running time is
(
|S| |A K 1 1-7
K 71-
+
In comparison, for the tabular MDP the corresponding running time (1 (|||A| [2].
This suggests that under the feature-based linear transition model, the computational complexity is { |||||| /K, 1-- =/// times lower than that for the tabular MDP (up to logarithm factors), which is significantly more efficient when K is not too large.
Stability vis-å-vis model misspecification. A more general version of Theorem 1 (Theorem 3 in Appendix B) shows that when P approximately (instead of exactly) admits the linear transition model, we can still achieve some meaningful result. Specifically, if there exists a linear transition kernel P obeying (ax(s (--ss, a) P(-|s, a) s & for some M O, we can show that f returned by Algorithm (with slight modification) satisfies
4Eopt
22
Q*(s. @* (s, <
1-7 (1 7-)
for every as E S x A. This shows that the model-based method is stable vis-asvis model misspecification. Interested readers are referred to Appendix B for more details.
In Algorithm 1, the reward function r assumed to be known. the information of is unavailable, an alternative is to assume that r is linear with respect to the feature mapping o, i.e. r(s, a) = 0 Φ(s, a)
for every (s, a) E A, which is widely adopted in linear MDP literature [26, 30, 56, 60]. Under this linear assumption, one can obtain 0 by solving the following linear system of equations
r (s, a) = T a (s, a).
(s, E K,
which can be constructed by the observed reward r(s, a) for all anchor state-action pairs.
4 Model-free RL-vanilla Q Learning
In this section, we turn to study one of the most popular model-free RL algorithms-Q-lee Q-learning. We provide tight sample complexity bound for vanilla Q-lcarning under the feature-based linear transition model, which shows its sample-effiiiency (depends on K instead of |S] or (AA) and sub-optimality in the dependency on the effective horizon.
4.1 Q-learning algorithm
The vanilla Q-learning algorithm maintains a Q-function estimate Qr S Xxxxx A + R for all / 2 0, with initialization Qo obeying 0 < Qo(s, a) S _ for every (s, a) S A. Assume have access a generative model. each iteration / 2 1, we collect an independent sample st(s, a) ~ P(ls,,)) for every anchor state-action pair (s, a) E K. and define Q K. R to be
de (s,a) a) = max Qt (st, a'), a'E.A
8t = st (s, a) P ())..).
Then given the learning rate E (0, 1]. the algorithm adopts the following update rule to update all entries of the fuunctio estimate
Q: = (1 - TK) Q. + Th (Q:-1).
Here, T(()) is empirical Bellman operator associated with the linear transition model M and the set IC and is given by
Tk (s, = r ((( Qf0

---

where (3) is used in the construction. Clearly, this newly defined operator Th is unbiased estimate of the famous Bellman operator 7 [8] defined as
(8, A
(()) (s, a) = r (8, -(
max Q ( (s',a') ''EA
critical property is that the Bellman operator is contractive with unique fixed point which is the optimal Q-function [*[8]. To solve the fixed-point equation T(Q*) = Q*, Q-laarnin was then introduced by [58] based on the idea of stochastic approximation [44]. This procedure is precisely described in Algorithm 2.
Algorithm 2 Vanilla Q-learning for infinite- discounted MDPs
inputs: learning rates {m;), number of iterations T, discount factor y, initial estimate Qn- for l 1,..., do
Draw (8,a) P (-18, a) for each (s, a) E K. Compute Qi according to the update rule
Qt (1 Th) Qt-1 + n6 TxTK (Q1-1).
end for
4.2
Main results
We are now ready to provide our main result for vanilla Q-learning, assuming sampling access to a generative model.
Theorem 2. Consider any 8 E (0, 1) and E (0, 1}. Assume that for any OSIS., T, the learning rates satisfy
+
c1(1-T log2?
Me
1 +
ca(1->10
log T
2 62 > 0. Suppose that the total number of for some sufficiently small universal constants iterations exceeds
T2 Calog (KT/0)
(9)
(1 (1-7)²
for some sufficiently large universal constant C3 0. the initialization obeys O S Qo(s, S
1
for any (8,a) a) S A, then with probubility exceeding 6, the output Qr of Algorithm 2 satisfies
max (
1Q (5, a) Q" (s,a) S
(10)
In addition, let ær (resp. Vr) to be the policy (resp. value function) induced by Qr, then has
2nE
max
V (s) - V (s) 1-7
(11)
SES
This theorem provides theoretical guarantees on the performance of Algorithm 2. A few implications of this theorem are order.
Learning rate. The condition (8) accommodates two commonly adopted choice of learning rates: (i) linearly rescaled learning rates 7) = [1 + c2(1 - 7)t/ log T T-- and (ii) deratioo-invariian learning rates тソ = [1 [1+ ci ()- log T.. Interested readers are referred to the discussions in [34, Section 3.1] for more details on these two learning rate schemes.
Tight sample complexity bound. Note that we draw K independent samples each iteration, therefore the iteration complexity (9) be translated into the sample complexity bound TK in order for Q-learning to achieve e-accuracy:
δ
(12)
(1-7)*
As we will see shortly, this result improves the state-of-the-art sample complexity bound presented in [63, Theorem 2] In addition, the dependency on the effective horizon (1 -) matches the lower bound established [34, Theorem 2] for vanilla Q-learning using either learning rate scheme covered in the previous remark, suggesting that our sample complexity bound (12) is sharp.
7

---

Stability vis-â-vis model misspecification. Just like the model based approach, we can also show that Q-learnigg is also stable vis-arvis model misspecification when approximately admits the linear transition model. We refer interested readers to Theorem 4 in Appendix B for more details.
Comparison with [63]. We compare our result with the sample complexity bounds for Q-learning under the feature-based linear transition model in [63].
We first compare our result with [63, Theorem 2], which state-of-the-ar theory for this problem. When there is no model misspecification, [63, Theorem showed that in order for their Phased Parametric Q-learning (Algorithm therein) to learn an e-optimal policy, the sample size needs to be
the best our knowledge, the
K
(1->)'
Note that (12) is the sample complexity required for entrywise s-accurate estimate of the optimal Q-function, thus fair comparison requires to use the sample complexity for learning s-optimal policy deduced from (11), which is
K
Hence, our sample complexity improves upon previous work by a factor at least on the order of (1 (1-?)-1 ? However it is worth mentioning that [63, Theorem 2] is built upon weaker conditions EK a)
and Σ Ass a)] I L for some L 2 1, which does not require A a) 0.
Our result holds under Assumption 1, which requires Σ (s,s, a) = and A a) 2 0. Under the current analysis framework, it difficult to obtain tight sample complexity bounds without assuming (s, a)= 2 0.
Besides vanilla Q-learning, [63] also proposed new variant of Q-learning called Optimal Phased Parametric Q-Learning (Algorithm 2 therein), which is essentially Q-learning with variance reduc- tion. [63, Theorem 3] showed that the sample complexity for this algorithm
K
(1-7)882
which matches minimax optimal lower bound (up a logarithm factor) established in [63, Theorem IJ. Careful reader might notice that this sample complexity bound is better than ours for vanilla Q-learning. We emphasize that elucidated the second implication under Theorem 2, result is already tight for vanilla Q-learning. This observation reveals that while the sample complexity for vanilla Q-learning is provably sub-optimal, the variants of Q-learning can have better performance and achieve minimax optimal sample complexity.
We conclude this section by comparing model-based and model-free approaches. Theorem shows that the sample complexity of the model-based approach is minimax optimal, whilst vanilla Q- learning, perhaps the most commonly adopted model-free method, sub-optimal according to Theorem 2. However this does not mean that model-based method is better than model-free ones since (i) some variants of Q-learning (see [63, Algorithm 2] for example) also has minimax optimal sample complexity; and (ii) in many applications it might be unrealistic to estimate the model in advance.
A glimpse of our technical approaches
The establishment of Theorems and calls for a series of technical novelties in the proof. In what follows, we briefly highlight our key technical ideas and novelties.
3 'hhe difference between Algorithm and Phased Parametric Q-Leaming [63] that Algorithm 2 maintains and updates Q-function estimate Qt, while Phased Parametric Q-Learning parameterized Q-function by
Qu (s, a) = r (s,a) a) + 7ob (s,a)" w,
and then updates the parameters

---

For the model-based approach, we employ "leave-one-out" analysis to decouple the complicated statistical dependency between the empirical probability transition model P and the corresponding optimal policy. Specifically, [2] proposed to construct a collection of auxiliary MDPs where each one of them leaves out single state s by setting to be absorbing state and keeping everything else untouched. We tailor this high level idea to the needs of linear transition model, then the independence between the newly constructed MDP with absorbing state and data samples collected at state will facilitate our analysis, as detailed in Lemma 1. Compared with [2]. Theorem extends the tabular setting studied in [2] to the linear transition model and accommodates model misspecificattion which actually needs significant efforts as detailed in the supplementary materials. This "leave-one-out" type of analysis has been utilized in studying numerous problems by a long line of work, such as [22, 38, 53, 13, 12, 14, 15]. just to name a few.
To obtain tighter sample complexity bound than the previous one Ö( K (2= ) in [63] for vanilla Q-learning, we invoke Freedman's ' inequality [24] for the concentration of an eπror term with martingale structure as illustrated in Appendix C. while the classical ones used in analyzing Q-learning are Hoeffding's inequality and Bernstein's 's inequality [63]. The use of Freedman's ' inequality helps us establish recursive relation on (1Q, - Q1 17 1==o- which consequently leads to the performance guarantee (10). It is worth mentioning that [34] also studied vanilla Q-learning in the tabular MDP setting and adopted Freedman's s inequality. while we emphasize that requires a lot of efforts and more delicate analyses in order to study linear transition model and also allow for model misspecification in the current paper, as detailed in the supplementary material.
6 Additional related literature
To remedy the issue of prohibitively high sample complexity, there exists a substantial body of literature proposing and studying many structural assumptions and complexity notions under different settings. This current paper focuses on linear transition model which is studied in MDP by numerous previous works [63, 30, 64, 68, 40, 25, 56, 52, 26, 60]. Among them, [63] studied linear transition model and provided tight sample complexity bounds for new variant of Q-learning with the help of variance reduction. [30] focused on linear MDP and designed an algorithm called Squares Value Iteration with UCB" with both polynomial runtime and polynomial sample complexity without accessing generative model. [56] extended the study of linear MDP to the framework of reward- free reinforcement learning. [68] considered a different feature mapping called linear kernel MDP and devised an algorithm with polynomial regret bound without generative model. Other popular structure assumptions include: [61] studied fully deterministic transition dynamics; [28] introduced Bellman rank and proposed an algorithm which needs sample size polynomially dependent on Bellman rank to obtain near-optimal policy in contextual decision processes; [20] assumed that the value function has low variance compared to the mean for all deterministic policy; [39, 42, 7, 66] used linear model to approximate the value function; [35] assumed that the optimal Q-function can be paraully-ppammmtrizeeee by the features.
Apart from the linear transition model, another notion adopted in this work is the generative model, whose role in discounted MDP has been studied by extensive literature. The concept of generative model was originally introduced by [32], and then widely adopted in numerous works, including [31, 5, 63, 54, 2, 41], to name a few. Specifically, it is assumed that a generative model of the studied MDP is available and can be queried for every state-action pair and output the next state. Among previous works, [5] proved that the minimax lower bound on the sample complexity to obtain an s-optimal policy was Ā [SIIA] ). [5] also showed that model-based approach can output an e-optimal value function with near-optimal sample complexity for 8 E (0. Then [2] made significant progress on the challenging problem of establishing minimax optimal sample complexity in estimating an e-optimal policy with the help of "leave-one-oue analysis.
In addition, after being proposed in [59], Q-learning has become the focus of a rich line of research [58, 11, 32. 23, 4, 29, 53, 16. 37, 62]. Among them, [16. 37, 62] studied Q-learning in the presence of Markovian data, i.e. a single sample trajectory. In contrast, under the generative setting of Q- learning where a fresh sample can be drawn from the simulator at each iteration, [54] analyzed a variant of Q-learning with the help of variance reduction, which was proved to enjoy minimax optimal sample complexity Ō [S][A]
Then more recently, [34] improved the lower bound of the
(111-)

---

vanilla Q Q-learning algorithm in terms of its scaling with I-y - and proved matching upper bound Ō |S||Al
7 Discussion
This paper studies sample complexity of both model-basee and model-free RL under discounted infinite-horizon MDP with feature-based linear transition model. We establish tight sample complexity bounds for both model-based approaches and Q-learning, which scale linearly with the feature dimension K instead of [S] x [A], thus considerably reduce the required sample size for large-scale MDPs when K is relatively small. Our results sharp, and the sample complexity bound for the model-based approach matches the minimax lower bound. The current work suggests couple of directions for future investigation, discussed in detail below.
Extension episodic MDPs. An interesting direction for future research is to study linear transition model in episodic MDP. This focus this work is hofiittehoorzonn discounted MDPs, and hopefully the analysis here can be extended to study the episodic MDP well ([17, 18, 6, 27, 55, 26)).
Continuous state and action space. The state and action spaces in this current paper still assumed to be finite, since the proof relies heavily on the matrix operations. However, we expect that the results can be extended to accommodate continuous state and action space by employing more complicated analysis.
Accommodating entire range af Since both value functions and Q-functions can take value in [0, (1-11-111,, ideelll our theory should cover all choices of E (0, (1-7)-1J. However we require that E (1-7)-11/2 in Theorem 1 and (0, 1] in Theorem 2. While most of the prior works like [2, 63] also impose these restrictions, a recent work [36] proposed a perturbed model-based planning algorithm and proved minimax optimal guarantees for any (0, (1-?) >))-))>-_0 While their work only focused on model based RL under tabular MDP, an interesting future direction is improve our theory accommodate any & E (0, (1 (1-
model-based
General function approximation. Another future direction to extend the study to more general function approximation starting from linear structure covered in this paper. There exists a rich body of work proposing and studying different structures, such as linear value function approximation [39, 42, 7, 66), linear MDPs with infinite dimensional features [1], Eluder dimension [57], Bellman rank [28] and Witness rank [50], etc. Therefore, it is hopeful to investigate these settings and improve the sample efficiency.
Acknowledgments and Disclosure of Funding
B. Wang is supported in part by Gordon Y. S. Wu Fellowships in Engineering. Y. Yan is supported in part by ARO grant W91 INF-20- 1-0097 and NSF grant CCF-1907661. Part of this work was done while Y. Yan was visiting the Simons Institute for the Theory of Computing. J. Fan is supported in part by the ONR grant N00014-19- 1--014-19-1-1200 and the NSF grants DMS-1662139, 171-17, DMS-2052926, DMS-2053832, and the NIH grant 2R01-GM002611-15.
References
[1] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pc-pg: Policy cover directed exploration for provable policy gradient learning. arXiv preprint wwX1::2007.08459, 2020.
[2] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference Learning Theory, pages 67-83. PMLR, 2020.
[3] Sanjeev Arora. Rong Ge, and Ankur Moitra. Learning topic modell-ggongg beyond svd. In 2012 IEEE 53rd annual symposium on foundations of computer science, pages 1-10, IEEE, 2012.
[4] Mohammad Gheshlaghi Azar, Remi Munos, Ghavamzadaeh, and Hilbert Kappen. Speedy g-leamnig. 2011.
10

---

[5] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning. 91(3):225-34 339, 2013.
[6] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[7] Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through bayesian deep q-networks. In 2018 Information Theory and Applications Workshop (ITA), pages 1-9. IEEE, 2018.
[8] Richard Bellman. On the theory of dynamic programming. Proceedings of the National Academy of Sciences of the United States of America, 38(8):716, 1952.
[9] Richard Bellman and Stuart Dreyfus. Functional approximations and dynamic programming. Mathematical Tables and Other Aids to Computation, pages 247-251, 1959.
[10] Dimitri Bertsekas et al. Dynamic programming and optimal control: Vol. 1. Athena scientific Belmont, 2000.
[11] Dimitri P Bertsekas and John N Tsitsiklis. Neuro Neuro-dynamic programming. Athena Scientific, 1996.
[12] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM Journal on Optimization, 3094):309--3 2020.
[13] Yuxin Chen, Jianqing Fan, Cong Ma, and Kaizheng Wang. Spectral method and regularized mle are both optimal for top-k ranking. Annals of statistics, 47(4):2204, 2019,,
[14] Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan. Bridging convex and nonconvex optimization robust pea: Noise, outliers, and missing data. arXiv preprint 4rX1v:2001.05444. accepted to Annals of Statistics, 2020.
[15] Yuxin Chen, Jianqing Fan, Bingyan Wang, and Yuling Yan. Convex and nonconvex optimization are both minimax-optimal for noisy blind deconvolution under random designs. Journal of the American Statistical Association, cosss--cceteed:1122 2021.
[16] Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke. Performance of q-learning with linear function approximation: Stability and finite-time analysis. arXiv preprini arXiv: 1905. 1425, 2019.
[17] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforce- ment learning, Advances in Neural Information Processing Systems, 28:2818-288 18188888266,, 2015.
[18] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: uniform pac bounds for episodic reinforcement learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 5717-5727, 2017.
[19] David Donoho and Victoria Stodden. When does non-negative matrix factorization give correct decomposition into parts? In 17th Annual Conference on Neural Information Processing Systems, NIPS 2003. Neural information processing systems foundation, 2004.
[20] Simon S Du, Yuping Luo, Ruosong Wang, and Hanrui Zhang. Provably efficient q-learning with function approximation via distribution shift error checking oracle. In Proceedings of the 33rd International Conference Neural Information Processing Systems, pages 8060-8070, 8070, 2019.
[21] Yaqi Duan, Zheng Tracy Ke, and Mengdi Wang. State aggregation learning from markov transition data. Advances in Neural Information Processing Systems, 32, 2019.
[22] Noureddine El Karoui. On the impact of predictor geometry on the performance on high- dimensional ridge-regularized generalized robust regression estimators. Probability Theory and Related Fields, 170 2018.
11

---

[23] Eyal Even-Dar, Yishay Mansour, and Peter Bartlett. Learning rates for q-learning. Journal of machine learning Research, 5(1), 2003.
[24] David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
[25] Botao Hao, Yaqi Duan, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Sparse feature selection makes batch reinforcement learning more sample efficient. In International Conference on Machine Learning, pages 4063-4073. PMLR, 2021.
[26] Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171-4180. PMLR, 2021.
[27] Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, pages 3395-3398. PMLR, 2018.
[28] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-Icarnable. In International Conference on Machine Learning, pages 1704-1713. PMLR, 2017.
[29] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably ef- ficient? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4868 4878, 2018.
[30] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[31] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, UCL (University College London), 2003.
[32] Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms. Advances in neural information processing systems, pages 996-1002, 1999.
[33] B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey, IEEE Transactions on Intelligent Transportation Systems, 2021.
[34] Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejie Chi. Is q-learning minimax optimal? tight sample complexity analysis. arXiv preprint 10o::22022.6548 2021.
[35] Gen Li, Yuxin Chen, Yuejie Chi, Yuantao Gu, and Yuting Wei. Sample-efficient reinforce- ment learning is feasible for linearly realizable mdps with limited revisiting. arXiv preprint arXiv:2105.0800 080024 2021.
[36] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with generative model. Advances in Neural Information Processing Systems, 33, 2020.
[37] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asyn- chronous g-leamnin:: Sharper analysis and variance reduction. Advances in neural information processing systems, 2020.
[38] Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in noncon- vex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pages 3345-3354. PMLR, 2018.
[39] Francisco S Melo and M Isabel Ribeiro. Q-learning with linear function approximation. In International Conference Computational Learning Theory, pages 308-322. Springer, 2007.
12

---

[40] Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of rein- forcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
[41] Ashwin Pananjady and Martin Wainwright. Instance-dependent -bondss for policy evalua- tion in tabular reinforcement learning. IEEE Transactions on Information Theory, 67(1) (1)5:66-
585, 2020.
[42] Ronald Parr, Lihong Li, Gavin Taylor, Christopher Painter- Wakefield, and Michael L Littman. An amalysis of linear models, linear value-function approximation, and feature selection for reinforcement learning. In Proceedings of the 25th international conference on Machine learning, pages 752-759, 2008
[43] Martin Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[44] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[45] Roshan Shariff and Csaba Szepesvári. Efficient planning in large mdps with weak linear function approximation. arXiv preprinl 2rXiv:2007.06/88 2020.
[46] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[47] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. nature, 550(7676):354-335 2017.
[48] Satinder P Singh, Tommi Jaakkola, and Michael Jordan. Reinforcement learning with soft state aggregation. Advances in neural information processing systems 7, 7:361, 1995.
[49] Satinder P Singh and Richard C Yee. An upper bound the loss from approximate optimal- value functions. Machine Learning, 16(3):227-25 -233, 1994.
[50] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference Learning Theory, pages 2898-2933. PMLR, 2019.
[51] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[52] Ahmed Touati and Pascal Vincent. Efficient learning in non-stationary linear markov decision processes, arXiv preprint arXiv:2010.12870 2020.
[53] Martin J Wainwright. Stochastic approximation with cone-contractive operators: Sharp 60- bounds for g-learning arXiv preprint ww0v.:190.00626 2019.
[54] Martin J Wainwright. Variance-reduced q-learning is minimax optimal. arXiv preprint arXiv:
2019.
[55] Ruosong Wang, Simon S Du, Lin Yang, and Sham Kakade. Is long horizon more difficult than short horizon r?? Advances in Neural Information Processing Systems, 33, 2020.
[56] Ruosong Wang, Simon Du, Lin F Yang. and Ruslan Salakhutdinov. On reward-free re- inforcement learning with linear function approximation. arXiv preprint arXiv:2006.11274, 2020.
[57] Ruosong Wang, Russ R Salakhurdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020.
13

---

[58] Christopher JCH Watkins and Peter Dayan. Q-learning Machine learning, 8(3-4):279-299
1992.
[59]
Christopher John Comish Hellaby Watkins, Learning from delayed rewards. 1989.
[60] Chen-Yo Yu Wei, Mchdi Jafarnia Jahromi, Haipeng Luo, and Rahul Jain. Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference Artificial Intelligence and Statistics, pages 3007-3015. PMLR, 2021.
[61] Zheng Wen and Benjamin Van Roy. Efficient reinforcement learning in deterministic systems with value function generalization. Mathematics of Operations Research, 42(3):762-782, 2017.
[62] Pan Xu and Quanquan Gu. A finite-time time analysis of q-leaming with neural network function approximation. In International Conference on Machine Learning, pages 10555-10565. PMLR, 2020.
[63] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
[64] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
[65] Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964 PMLR, 2020.
[66] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
[67] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Limiting extrapolation in linear approximate value iteration. Advances in Neural Information Processing Systems, 32:5615-5624, 2019.
[68] Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 12793-12802. PMLR, 2021.
14


Reviews:
[{"review_id": "cVYAx9E_LeE", "reviewer": "Reviewer_G5iQ", "summary": "This paper considers reinforcement learning in infinite horizon discounted Markov decision processes with access to a generative model with linearly parameterized transitions.  At a high level, the authors consider an infinite horizon discounted Markov decision process with discount factor $\\gamma$, finite state and action spaces, and known reward functions.  The high level goal is to query the transition kernel at various states in order to learn a policy $\\pi$ mapping states $s$ to actions $a$ which maximizes the cumulative reward experienced across the trajectory.\n\nIt is widely known that learning in general depends on $|S| \\times |A|$ which can be prohibitively large whenever $S$ or $A$ is large.  As such, the authors impose additional assumptions in the paper different from prior work with respect to the transition kernel (the only uncertainty present in the model) in order to avoid this worst-case scaling.  In particular, they assume that the algorithm designer has access to a feature function $\\phi : S \\times A \\rightarrow R^K$ such that there are unknown functions $\\psi_1, \\ldots, \\psi_k$ where $P(s' | s,a) = \\sum_k \\phi_k(s,a) \\psi_k(s').$  This definition is the same structure imposed on the probability transition kernel in the linear MDP model (but doesn't also require that the reward function is a linear mapping of the features $\\phi$).  This model encompasses tabular MDPs with no additional assumptions where $K$ can be taken to be $S \\times A$.\n\nIn addition to the linear assumption, the authors assume access to a set of anchor state action pairs of size $K$.  With this assumption, they assume that the feature vectors can be expressed as a convex combination of the feature vectors of the anchor state action pairs (which additionally imposes that the transition kernel can be written as $P(s' | s,a) = \\sum_i \\lambda_i(s,a) P(s' | s_i, a_i))$ where $i$ indexes over the anchor state action pairs. The authors assume that the $\\lambda$ function and the anchor pairs are known in advance to the algorithm designer.\n\nThis assumption differentiates the model from the typical infinite horizon discounted MDP to (hopefully) obtain improved regret guarantees.  In particular, the theoretical contributions for the authors follows via two separate strands.\n\nFirst, the authors consider a model based reinforcement learning algorithm using the generative model.  In particular, their algorithm queries all of the anchor state-action pairs a given number of times to obtain independent samples from the transition $P( | s_i, a_i)$.  Using this, they can then construct an empirical transition kernel for all state action pairs using the linear combination arising from the anchor state action pair assumption.  With this estimate of the transition kernel, the authors can construct an empirical MDP where the true transition is replaced by its estimate (which can be done as the reward function is known), and use planning to find an optimal policy in this perturbed MDP.\n\nVia this method the authors show that the sample complexity scales via $K / (1 - \\gamma)^3 \\epsilon^2$, which is minimax optimal up to logarithmic factors.\n\nSecond, the authors consider a model free reinforcement learning algorithm using the generative model.  This algorithm proceeds across time steps, where in each time step they sample a transition for each anchor state action pair, and update an estimate for the $Q$ function using the 'anchored' Bellman equations.\n\nVia this method the authors show that the sample complexity scales via $K / (1 - \\gamma)^4 \\epsilon^2$, which is minimax optimal or 'sharp' under naive $Q$ learning based algorithms.\n\nLastly, the authors complement the theoretical results by a detailed discussion comparing the theoretical guarantees on the performance of their approaches to that in [61].", "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": "### Originality:\nThe authors present an extension of existing model based and $Q$ learning based algorithms to the infinite horizon discounted MDP setting with linearly parameterized transition kernels.  While the algorithms presented are simple extensions of vanilla model based or $Q$ learning based algorithms, the authors express the necessary and straight-forward modifications to better exploit the linearly parameterized transitions in the algorithm design.  The proof techniques employed seemed like simple extensions of existing proof techniques, but see the questions section for more detailed comments.\n\n### Quality:\nThe submission is technically sound and the theoretical claims are well supported.  The authors are honest and upfront on the new techniques used in both their proof and algorithm development.  However, there were certain additional assumptions required for the algorithm, namely:\n- Known reward function\n- Known feature representations $\\phi$ and anchor states\nwhich are never fully discussed or compared to the previous literature.\n\n### Clarity:\nThe submission is clearly written and well organized.  However, with this there are a couple of confusing sections and theorem presentations:\n- The title of the paper is misleading, as the authors do not consider the true 'linear MDP' model but instead 'linearly parameterized transitions'\n- The sample complexity bounds for Theorem 1 are performance guarantees with respect to the $Q$ function of the learned policy.  However, the guarantees in Theorem 2 are just guarantees with respect to the estimated $Q$ function (independent of the performance of the greedy policy with respect to the estimated $Q$ function).  This is later discussed in the comments, but might be easier to understand if the theorems are in the same 'format'.  Also, upon checking the cited result to transform the bound, it does not provide performance guarantee of the greedy w/r/t $Q$ estimates in the true MDP as cited - unless I am misunderstanding the result.\n- The key algorithmic differences between this paper and [61] are never fully discussed.\n- Line 324 minor typo in 'employing more complicated analysis tool'.\n- The relation to the other linear MDP models listed in line 286 is never fully discussed with respect to the different proof techniques and algorithmic tools needed.\n\n### Significance:\nThe results in this paper improve the best known bounds for sample complexity guarantees with their model. While the novel techniques used are quite limited (just modifying existing generative model RL algorithms to exploit the anchor state representations), the work can be built upon by better understanding the required assumptions (finite state action space and known anchor state representation).\n\n### Strengths:\nThe main strengths of the paper are as follows:\n- The authors present minimax sample complexity bounds for the infinite horizon MDP setting with linear transitions and access to a generative model\n- The paper is incredibly well written and easy to follow\n\n### Weaknesses:\nThe main weaknesses of the paper are as follows:\n- The novel contributions seem limited as the algorithms are straightforward extensions of existing generative model algorithms.  While it seems like the theoretical tools required are novel, these contributions were not fully highlighted in the paper.\n- There are no concrete or realistic problem set-ups presented which satisfy the authors linearly parametrized MDP assumptions\n\n### Questions and Comments:\n- Line 118 - 121 was a nice point and helped highlight the improvements from the additional assumption.\n- Line 134 - 137 was a useful discussion on the notion of anchor states.  However, the assumption that these are known as well as $\\lambda(s,a)$ was never explicitly stated but required in the algorithms.  While it seems straightforward to learn the anchor state and $\\lambda$ function just from the feature mapping $\\phi$, this should be explicitly discussed in the paper.  Especially in the algorithm description you state the feature mapping $\\phi$ only is needed (as in Algorithm 1).\n- In Theorem 1, the notation $\\epsilon_{opt}$ was introduced in the result but not in the theorem statement.  While there was a discussion after the theorem statement, this should be included in the formal theorem definition.\n- Section on line 175 was a nice point to consider the computational complexity required.\n- For the first point in section 5.  It seems a straightforward proof technique would be to show that the constructed estimated transition kernel approximates the true one up to some accuracy, and then use sensitivity of planning in the perturbed MDP with respect to the estimated transition kernel.  Did you try this approach and show that it leads to suboptimal guarantees?\n\n\nEDIT: I'd like to thank the authors for their detailed comments for each of the concerns that they bring up, and I've updated my score accordingly.  The authors seem to have taken great care to improve the readability and clarity of the paper, especially addressing some of my earlier concerns with respect to constructing the set of anchor states from the feature representation $\\phi$, and comparing some aspects of their proof techniques to other more 'naive' approaches to solving the problem.  All in all, my only concerns that remain are with respect to:\n1. The usefulness of the model.  Even in responding to my comment the authors are unable to describe a concrete model where Assumption 1 is valid.  While it is still useful as a starting point for other theoretical analysis, having an example would help.\n2. The strength of assumption 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper focuses on the theory of reinforcement learning, and so it is expected that it will not have any potential negative societal impacts.  The authors are also clear on the limitations of their work, including:\n- Assumption that $S$ and $A$ are finite\n- Accommodating a large range on $\\epsilon$ for the sample complexity guarantees\n\nIn addition, there are two assumptions which are stated implicitly but the authors never explicitly discussed their importance:\n- Known feature representation $\\phi$ and anchor states\n- Known reward function", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {"ethical_concerns": "The work presented in this paper considers a theoretical model for solving reinforcement learning problems via learning in an unknown infinite horizon Markov decision process. As such, there are little ethical considerations for this paper.\n"}}, {"review_id": "YY4VF8bp2-w", "reviewer": "Reviewer_u4X6", "summary": "This paper derives sample complexity for both model-based RL algorithms and model-free RL algorithm (i.e. $Q$-learning) in the case where the underlying MDP admits a linear structure. The resulting sample complexity bounds in both cases are shown to be tight. ", "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": "The linear parametrized MDP model, although was studied in related literature, seems to be relatively restrictive. It would be nice if such model is motivated by some real world applications.\n\nThe contributions of this paper are purely theoretical. The two major results are the sample complexity bounds for model-based and model-free RL algorithms. It seems that the approach for obtaining the sample complexity bound of model-based algorithm is similar to [2,5], and the approach for obtaining the sample complexity bound of model-free $Q$-learning is similar to [34]. It should be clearly stated what the technical challenges are in extending the results of [2,5,34] to the setting of this paper.\n\nThe $Q$-learning algorithm studied in this paper uses synchronous update, while practically $Q$-learning updates $Q_k$ in an asynchronous manner based a trajectory of samples obtained from a behavioral policy. \n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No Societal Impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "TdAfTqxY5K7", "reviewer": "Reviewer_7gbE", "summary": "This paper considers MDPs with linear transition models. Assuming access to a generative model, under certain anchor state assumption, the authors prove the following two results:\n\n1. A model-based approach achieves a sample complexity of $O~(K / ((1 - \\gamma)^3 \\epsilon^2))$ which matches the minimax optimal lower bound up to logarithm factors; \n2. A model-free approach based on Q-learning achieves a sample complexity of  $O~(K / ((1 - \\gamma)^3 \\epsilon^2))$.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Understanding the tight sample complexity of RL with linear function approximation is an important problem in RL. This paper improves the state-of-the-art sample complexity for RL with linear function approximation assuming access to a generative model. The authors show that the sample complexity of a model-based approach matches the minimax optimal lower bound up to logarithm factors when $\\epsilon$ is sufficiently small. The authors also improve the sample complexity of vanilla Q-learning in this setting. \n\nOn the technical side, for the model-based result, the authors borrow the “leave-one-out” analysis developed by Agarwal et al. and generalize it to the linear function approximation setting. For the model-free result, the authors use Freeman's inequality to improve the concentration of the error term.\n\nMy major concern is Assumption 1 which is very strong. Although it has been adopted in the RL literature (the authors should consider citing [1] and [2] which also used this assumption) and could be crucial for obtaining tight bounds, the authors should at least discuss whether it is possible to weaken such an assumption. What happens if some $\\lambda_i(s, a)$ can be negative but still has bounded absolute value? What happens if we instead assume $\\sum \\lambda_i(s, a) \\le T$ for some $T > 0$? How should the sample complexity depend on $T$? Note that there always exists a set of anchor state-action pairs with $|\\lambda_i(s, a)| \\le 1$ for all $i \\in [K]$ and $(s, a)$ which is implied by the existence of barycentric spanners [3]. This paper could be significantly stronger if such a discussion is available. \n\nOverall, this is an interesting paper, and the writing is easy to follow. However, the main assumption (assumption 1) seems pretty strong, and thus my recommendation is merely a weak acceptance. \n\n\n[1] Efficient Planning in Large MDPs with Weak Linear Function Approximation\n\n[2] Limiting Extrapolation in Linear Approximate Value Iteration\n\n[3] Online linear optimization and adaptive routing", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "JJNJBMvC7Ay", "reviewer": "Reviewer_bj21", "summary": "The paper considers reinforcement learning problem in infinite-horizon, discounted reward MDPs with a generative model. The authors aim to obtain upper bounds on the number of samples required to efficiently learn the optimal policy or the optimal $Q$-function when number of states and actions are very large. In order to achieve this, the authors impose generalization by considering transition probabilities to be linear in known state-action features (a.k.a. the linear MDP setting). The authors further assume access to a number of anchor state-action pairs, whose features (essentially) form a basis of the feature space. Under these assumptions on the MDP, the authors propose both model-based and model-free algorithm for learning the optimal policy (or $Q$-function), and analyze their sample complexity guarantees. The authors prove that the sample complexities of both the algorithms scale linearly with the dimension of the feature space (which is also equal to the number of anchor state-action pairs). The sample complexity bound of the model-based algorithm is the first of its kind for linear MDPs, and matches the minimax lower bound of Yang and Wang, 2019. The sample complexity bound of the model-free algorithm, though suboptimal, improves over the previously known bound of Yang and Wang, 2019.", "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 model based algorithm and its analysis is novel in the context of linear MDPs. The model-free algorithm, though known and analyzed before, obtains an improved sample complexity which is achieved through a novel application of Freedman inequality. However, I have not checked the correctness of the proofs in detail. The results are significant as long as sample complexity bounds in linear MDPS are concerned, but similar results already exist for tabular MDPs. This paper, though provide sample complexity bounds independent of number of state and actions, do not go beyond the tabular setting. The paper is well-written and the flow is clear.\n\nI have one question for the authors. The dimension of the features and the number of anchor state-action pairs are assumed to be equal. What happens and how the results change is these are different?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work, and hence possible implications on the society are not foreseeable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper has initially received mixed reviews, with several reviewers taking issue with the strength of the assumptions. After reading the very detailed author response and some further discussion, two reviewers have decided to raise their scores, so eventually all scores ended up being positive. The reviewers agreed that the paper offers an interesting technical contribution clearly improving the previous state of the art, and that it is worthy of being published at the conference. Based on my own reading, I concur with this assessment and strongly recommend this paper for acceptance.
Decision: Accept (Poster)