Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
Year: 2021

Abstract:
The curse of dimensionality is a widely known issue in reinforcement learning (RL). In the tabular setting where the state space S and the action space A are both finite, to obtain a nearly optimal policy with sampling access to a generative model, the minimax-optimal sample complexity scales linearly with |S| × |A|, which can be prohibitively large when S or 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 ε-optimal policy (resp. Q-function) with high probability as soon as the sample size exceeds the order of K (1−γ)3ε2 (resp. K (1−γ)4ε2 ), up to some logarithmic factor. Here K is the feature dimension and γ ∈ (0, 1) is the discount factor of the MDP. The results is applicable to the tabular MDPs by taking the coordinate basis with K = |S| × |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-learning are sample-efficient when K is relatively small, and hence the title of this paper.

heading: 1 Introduction
text: Reinforcement learning (RL) studies the problem of learning and decision making in a 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 an 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 an empirical MDP by learning the probability transition model from the collected data samples, and then estimating the optimal policy / value function based on the empirical MDP.
• The model-free approaches (e.g. Q-learning) learn the optimal policy or the optimal (action-)value function from samples. As its name suggests, model-free approaches do not attempt to learn the model explicitly. ∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Generally speaking, model-based approaches enjoy great flexibility since after the transition model is learned in the first place, it can then be applied to 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). It 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 a near optimal policy or value function given sampling access to a generative model, the minimax optimal sample complexity scales linearly with |S| × |A| [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 to 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 (s, a) ∈ S×A admits aK dimensional feature vector φ(s, a) ∈ RK that expresses the transition dynamics P(·|s, a) = Ψφ(s, a) for some unknown matrix Ψ ∈ R|S|×K 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-based RL and Q-learning to learn an optimal policy under the feature-based 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 is independent of |S| and |A| under the feature-based linear transition model. With the aid of this structural assumption, model-based RL and Q-learning becomes significantly more sample-efficient than that in the tabular setting.
Our contributions. We focus our attention on an infinite horizon MDP with discount factor γ ∈ (0, 1). We use ε-optimal policy to indicate the policy whose expected discounted cumulative rewards are ε close to the optimal value of the MDP. Our contributions are two-fold:
• We demonstrate that model-based RL provably learns an ε-optimal policy by performing planning based on an empirical MDP constructed from a total number of
Õ
( K
(1− γ)3 ε2
)
samples, for all ε ∈ (0, (1− γ)−1/2]. Here Õ(·) hides logarithmic factors compared to the usual O(·) notation. To the best of our knowledge, this is 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 ε-optimal Q-function using a total number of
Õ
( K
(1− γ)4 ε2
)
samples, for all ε ∈ (0, 1]. This sample complexity upper bound improves the state-of-the-art result in [63] and the dependency on the effective horizon (1− γ)−4 is sharp in view of [34].
These results taken collectively show the minimax optimality of model-based RL and the suboptimality of Q-learning in sample complexity.

heading: 2 Problem formulation
text: This paper focuses on tabular MDPs in the discounted infinite-horizon setting [10]. Here and throughout, ∆d−1 := {v ∈ Rd : ∑d i=1 vi = 1, vi ≥ 0,∀i ∈ [d]} stands for the d-dimensional probability simplex and [N ] := {1, 2, · · · , N} for any N ∈ N+.
Discounted infinite-horizon MDPs. Denote a discounted infinite-horizon MDP by a tuple M = (S,A, P, r, γ), where S = {1, · · · , |S|} is a finite set of states, A = {1, · · · , |A|} is a finite set of actions, P : S ×A → ∆|S|−1 represents the probability transition kernel where P (s′|s, a) denotes the probability of transiting from state s to state s′ when action a is taken, r : S ×A → [0, 1] denotes the reward function where r(s, a) is the instantaneous reward received when taking action a ∈ A while in state s ∈ S, and γ ∈ (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 in the corresponding MDP. For a deterministic policy π : S → A and a starting state s ∈ S, we define the value function as
V π (s) := E [ ∞∑ k=0 γkr (sk, ak) ∣∣∣ s0 = s]
for all s ∈ S. Here, the trajectory is generated by ak = π(sk) and sk+1 ∼ P (sk+1|sk, ak) for every k ≥ 0. This function measures the expected discounted cumulative reward received on the trajectory {(sk, ak)}k≥0 and the expectation is taken with respect to the randomness of the transitions sk+1 ∼ P (·|sk, ak) on the trajectory. Recall that the immediate rewards lie in [0, 1], it is easy to derive that 0 ≤ V π(s) ≤ 11−γ for any policy π and state s. Accordingly, we define the Q-function for policy π as
Qπ (s, a) := E [ ∞∑ k=0 γkr (sk, ak) |s0 = s, a0 = a ] for all (s, a) ∈ S × A. Here, the actions are chosen by the policy π except for the initial state (i.e. ak = π(sk) for all k ≥ 1). Similar to the value function, we can easily check that 0 ≤ Qπ(s, a) ≤ 1 1−γ for any π and (s, a). To maximize the value function or Q function, previous literature [9, 51] establishes that there exists an optimal policy π? which simultaneously maximizes V π(s) (resp. Qπ(s, a)) for all s ∈ S (resp. (s, a) ∈ S ×A). We define the optimal value function V ? and optimal Q-function Q? respectively as
V ? (s) := max π
V π (s) = V π ?
(s) , Q? (s, a) := max π
Qπ (s, a) = Qπ ? (s, a)
for any state-action pair (s, a) ∈ S ×A.
Linear transition model. Given a set of K feature functions φ1, φ2, · · · , φK : S × A → R, we define φ to be a feature mapping from S ×A to RK such that
φ (s, a) = [φ1 (s, a) , · · · , φK (s, a)] ∈ RK . Then we are ready to define the linear transition model [63] as follows. Definition 1 (Linear transition model). Given a discounted infinite-horizon MDPM = (S,A, P, r, γ) and a feature mapping φ : S ×A → RK , M admits the linear transition model if there exists some (unknown) functions ψ1, · · · , ψK : S → R, such that
P (s′|s, a) = K∑ k=1 φk (s, a)ψk (s ′) (1)
for every (s, a) ∈ S ×A and s′ ∈ S.
Readers familiar with linear MDP literatures might immediately recognize that the above definition is the same as the structure imposed on the probability transition kernel P in the linear MDP model [63, 30, 65, 26, 52, 56, 60]. However unlike linear MDP which also requires the reward function r(s, a) to be linear in the feature mapping φ(s, a), here we do not impose any structural assumption on the reward.
Example 1 (Tabular MDP). Each tabular MDP can be viewed as a linear transition model with feature mapping φ(s, a) = e(s,a) ∈ R|S|×|A| (i.e. the vector with all entries equal to 0 but the one corresponding to (s, a) equals to 1) for all (s, a) ∈ S ×A. To see this, we can check that Definition 1 is satisfied with K = |S| × |A| and ψ(s,a)(s′) = P(s′|s, a) for each s, s′ ∈ S and a ∈ A. This example is a sanity check of Definition 1, which also shows that our results (Theorem 1 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 {φ(s, a)}(s,a)∈S×A fall in the probability simplex ∆K−1, a linear transition model can be constructed by taking ψk(·) to be any probability measure over S for all k ∈ [K].
A key observation is that the model size of linear transition model with known feature mapping φ is |S|K (the number of coefficients ψk (s′) in (1)), which is still large when the state space S is large. In contrast, it will be established later that to learn a near-optimal policy or Q-function, we only need a 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 a set of anchor state-action pairs K ⊂ S ×A with |K| = K2 such that for any (s, a) ∈ S ×A, its corresponding feature vector can be expressed as a convex combination of the feature vectors of anchor state-action pairs {(s, a) : (s, a) ∈ K}:
φ (s, a) = ∑
i:(si,ai)∈K
λi (s, a)φ (si, ai) for K∑ i=1 λi (s, a) = 1 and λi (s, a) ≥ 0. (2)
Further, we assume that the vectors in {φ(s, a) : (s, a) ∈ K} are linearly independent.
We pause to develop some intuition of this assumption using Examples 1 and 2. In Example 1, it is straightforward to check that tabular MDPs satisfies Assumption 1 with K = S ×A. In terms of Example 2, without loss of generality we can assume that the subspace spanned by the features has full rank, i.e. span{φ(s, a) : (s, a) ∈ S ×A} = RK (otherwise we can reduce the dimension of feature space). Then we can also check that Example 2 satisfies Assumption 1 with arbitrary K ⊆ S ×A such that the vectors in {φ(s, a) : (s, a) ∈ 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 to 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.
A useful implication of Assumption 1 is that we can represent the transition kernel as P (·|s, a) = ∑
i:(si,ai)∈K
λi (s, a)P (·|si, ai) , (3)
This follows simply from substituting (2) into (1) (see (14) in Appendix A for a formal proof).

heading: 3 Model-based RL with a generative model
text: We start with studying model-based RL with a generative model in this section. We propose a model-based planning algorithm and show that it returns an ε-optimal policy with minimax optimal sample size.

heading: 3.1 Main results
text: A generative model and an empirical MDP. We assume access to a generative model that provides us with independent samples from M . For each anchor state-action pair (si, ai) ∈ K, we collect N
2Without loss of generality, one can always assume that the number of anchor state-action pairs equals to the feature dimension K. Interested readers are referred to Appendix D for detailed argument.
independent samples s(j)i ∼ P (·|si, ai), j ∈ [N ]. This allows us to construct an empirical transition kernel P̂ where
P̂ (s′ | s, a) = K∑ i=1 λi (s, a) ·  1 N N∑ j=1 1 { s (j) i = s ′ } , (4)
for each (s, a) ∈ S × A. Here, 1N ∑N j=1 1{s (j) i = s
′} is an empirical estimate of P (s′|si, ai) and then (3) is employed. With P̂ in hand, we can construct an empirical MDP M̂ = (S,A, P̂ , r, γ). Our goal here is to derive the sample complexity which guarantees that the optimal policy of M̂ is an ε-optimal policy for the true MDP M . The algorithm is summarized below.
Algorithm 1 Model-based RL with a generative model Inputs: a set of anchor state-action pairs K = {(si, ai) : i ∈ [K]}, feature mapping φ : S ×A → RK , any planning algorithm P , target algorithmic error level εopt. For i = 1, · · · ,K do
Draw N independent samples s(j)i ∼ P (·|si, ai), j = 1, · · · , N . End for Construct an empirical MDP M̂ = (S,A, P̂ , r, γ) where P̂ can be computed by (4). Output π̂ as an εopt-optimal policy of M̂ computed by the planning algorithm P .
Careful readers may note that in Algorithm 1, {λ(s, a) : (s, a) ∈ S ×A} is used in the construction of P̂ , while {λ(s, a) : (s, a) ∈ S ×A} is not input into the algorithm. This is because given K and φ are known, {λ(s, a) : (s, a) ∈ S ×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 and ε ∈ (0, (1−γ)−1/2]. Let π̂ be the policy returned by Algorithm 1. Assume that
N ≥ C log (K/ ((1− γ) δ)) (1− γ)3 ε2
(5)
for some sufficiently large constant C > 0. Then with probability exceeding 1− δ,
Q?(s, a)−Qπ̂(s, a) ≤ ε+ 4εopt 1− γ , (6)
for every (s, a) ∈ S ×A. Here εopt 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, ε could decrease towards 0. The other term 4εopt/(1 − γ) represents the algorithmic error where εopt is the target accuracy level of the planning algorithm applied to M̂ . Note that εopt 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 εopt is made negligibly small, e.g. εopt = O((1 − γ)ε) to be discussed in the next point. Note that we draw N independent samples for each state-action pair (s, a) ∈ K, therefore the requirement (5) for finding an O(ε)-optimal policy translates into the following sample complexity requirement
Õ
( K
(1− γ)3 ε2
) .
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 Ω̃((1−γ)−3ε−2|S||A|) [5, 2]. Our sample complexity scales linearly withK instead of |S||A| for tabular MDP as desired.
• 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 εopt in O((1− γ)−1 log ε−1opt ) iterations, and each iteration takes time proportional to O(NK + |S||A|K). To learn an O(ε)-optimal policy, which requires sample complexity (5) and the target level εopt = O((1− γ)ε), the overall running time is
Õ
( |S| |A|K
1− γ +
K
(1− γ)4 ε2
) .
In comparison, for the tabular MDP the corresponding running time is Õ((1− γ)−4ε−2|S||A|) [2]. This suggests that under the feature-based linear transition model, the computational complexity is min{|S||A|/K, (1− γ)−3ε−2/K} 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 max(s,a)∈S×A ‖P̃ (·|s, a)− P (·|s, a)‖1 ≤ ξ for some ξ ≥ 0, we can show that π̂ returned by Algorithm 1 (with slight modification) satisfies
Q?(s, a)−Qπ̂(s, a) ≤ ε+ 4εopt 1− γ + 22ξ (1− γ)2 ,
for every (s, a) ∈ S × A. This shows that the model-based method is stable vis-a-́vis model misspecification. Interested readers are referred to Appendix B for more details.
In Algorithm 1, the reward function r is assumed to be known. If the information of r is unavailable, an alternative is to assume that r is linear with respect to the feature mapping φ, i.e. r(s, a) = θ>φ(s, a) for every (s, a) ∈ S ×A, which is widely adopted in linear MDP literature [26, 30, 56, 60]. Under this linear assumption, one can obtain θ by solving the following linear system of equations
r (s, a) = θ>φ (s, a) , ∀ (s, a) ∈ K, (7) which can be constructed by the observed reward r(s, a) for all anchor state-action pairs.

heading: 4 Model-free RL—vanilla Q Learning
text: In this section, we turn to study one of the most popular model-free RL algorithms—Q-learning. We provide tight sample complexity bound for vanilla Q-learning under the feature-based linear transition model, which shows its sample-efficiency (depends on |K| instead of |S| or |A|) and sub-optimality in the dependency on the effective horizon.

heading: 4.1 Q-learning algorithm
text: The vanilla Q-learning algorithm maintains a Q-function estimateQt : S×A → R for all t ≥ 0, with initialization Q0 obeying 0 ≤ Q0(s, a) ≤ 11−γ for every (s, a) ∈ S ×A. Assume we have access to a generative model. In each iteration t ≥ 1, we collect an independent sample st(s, a) ∼ P (·|s, a) for every anchor state-action pair (s, a) ∈ K and define Q(t)K : K → R to be
Q (t) K (s, a) := max
a′∈A Qt (st, a
′) , st ≡ st (s, a) ∼ P (·|s, a) .
Then given the learning rate ηt ∈ (0, 1], the algorithm adopts the following update rule to update all entries of the Q-function estimate
Qt = (1− ηt)Qt−1 + ηtT (t)K (Qt−1) .
Here, T (t)K is an empirical Bellman operator associated with the linear transition model M and the set K and is given by
T (t)K (Q) (s, a) := r (s, a) + γλ (s, a)Q (t) K ,
where (3) is used in the construction. Clearly, this newly defined operator T (t)K is an unbiased estimate of the famous Bellman operator T [8] defined as
∀ (s, a) ∈ S ×A : T (Q) (s, a) := r (s, a) + γEs′∼P (·|s,a) [ max a′∈A Q (s′, a′) ] .
A critical property is that the Bellman operator T is contractive with a unique fixed point which is the optimal Q-function Q?[8]. To solve the fixed-point equation T (Q?) = Q?, Q-learning 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-horizon discounted MDPs inputs: learning rates {ηt}, number of iterations T , discount factor γ, initial estimate Q0. for t = 1, . . . , T do
Draw st (s, a) ∼ P (·|s, a) for each (s, a) ∈ K. Compute Qt according to the update rule
Qt = (1− ηt)Qt−1 + ηtT (t)K (Qt−1) . end for

heading: 4.2 Main results
text: We are now ready to provide our main result for vanilla Q-learning, assuming sampling access to a generative model. Theorem 2. Consider any δ ∈ (0, 1) and ε ∈ (0, 1]. Assume that for any 0 ≤ t ≤ T , the learning rates satisfy
1
1 + c1(1−γ)T log2 T
≤ ηt ≤ 1
1 + c2(1−γ)t log2 T
(8)
for some sufficiently small universal constants c1 ≥ c2 > 0. Suppose that the total number of iterations T exceeds
T ≥ C3 log (KT/δ) log 4 T
(1− γ)4 ε2 (9)
for some sufficiently large universal constant C3 > 0. If the initialization obeys 0 ≤ Q0(s, a) ≤ 11−γ for any (s, a) ∈ S ×A, then with probability exceeding 1− δ, the output QT of Algorithm 2 satisfies
max (s,a)∈S×A
|QT (s, a)−Q? (s, a)| ≤ ε. (10)
In addition, let πT (resp. VT ) to be the policy (resp. value function) induced by QT , then one has
max s∈S |V πT (s)− V ? (s)| ≤ 2γε 1− γ . (11)
This theorem provides theoretical guarantees on the performance of Algorithm 2. A few implications of this theorem are in order.
• Learning rate. The condition (8) accommodates two commonly adopted choice of learning rates: (i) linearly rescaled learning rates ηt = [1 + c2(1 − γ)t/ log2 T ]−1, and (ii) iteration-invariant learning rates ηt ≡ [1 + c1(1− γ)T/ log2 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 in each iteration, therefore the iteration complexity (9) can be translated into the sample complexity bound TK in order for Q-learning to achieve ε-accuracy:
Õ
( K
(1− γ)4 ε2
) . (12)
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− γ)−4 matches the lower bound established in [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.
• Stability vis-à-vis model misspecification. Just like the model-based approach, we can also show that Q-learning is also stable vis-a-́vis model misspecification when P 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 is, to the best of our knowledge, the state-of-the-art theory for this problem. When there is no model misspecification, [63, Theorem 2] showed that in order for their Phased Parametric Q-learning3 (Algorithm 1 therein) to learn an ε-optimal policy, the sample size needs to be
Õ
( K
(1− γ)7 ε2
) .
Note that (12) is the sample complexity required for entrywise ε-accurate estimate of the optimal Q-function, thus a fair comparison requires to use the sample complexity for learning an ε-optimal policy deduced from (11), which is
Õ
( K
(1− γ)6 ε2
) .
Hence, our sample complexity improves upon previous work by a factor at least on the order of (1− γ)−1. However it is worth mentioning that [63, Theorem 2] is built upon weaker conditions∑K i=1 λi(s, a) = 1 and ∑K i=1 |λi(s, a)| ≤ L for some L ≥ 1, which does not require λi(s, a) ≥ 0.
Our result holds under Assumption 1, which requires ∑K i=1 λi(s, a) = 1 and λi(s, a) ≥ 0. Under the current analysis framework, it is difficult to obtain tight sample complexity bounds without assuming λi(s, a) ≥ 0.
• Besides vanilla Q-learning, [63] also proposed a new variant of Q-learning called Optimal Phased Parametric Q-Learning (Algorithm 2 therein), which is essentially Q-learning with variance reduction. [63, Theorem 3] showed that the sample complexity for this algorithm is
Õ
( K
(1− γ)3ε2
) ,
which matches minimax optimal lower bound (up to a logarithm factor) established in [63, Theorem 1]. Careful reader might notice that this sample complexity bound is better than ours for vanilla Q-learning. We emphasize that as elucidated in the second implication under Theorem 2, our 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 1 shows that the sample complexity of the model-based approach is minimax optimal, whilst vanilla Qlearning, perhaps the most commonly adopted model-free method, is 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.

heading: 5 A glimpse of our technical approaches
text: The establishment of Theorems 1 and 2 calls for a series of technical novelties in the proof. In what follows, we briefly highlight our key technical ideas and novelties.
3The difference between Algorithm 2 and Phased Parametric Q-Learning in [63] is that Algorithm 2 maintains and updates a Q-function estimate Qt, while Phased Parametric Q-Learning parameterized Q-function by
Qw (s, a) := r (s, a) + γφ (s, a) > w,
and then updates the parameters w.
• 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 a single state s by setting s to be an 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 s and data samples collected at state s will facilitate our analysis, as detailed in Lemma 1. Compared with [2], Theorem 1 extends the tabular setting studied in [2] to the linear transition model and accommodates model misspecification, 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 Õ( K(1−γ)7ε2 ) in [63] for vanilla Q-learning, we invoke Freedman’s inequality [24] for the concentration of an error 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 inequality [63]. The use of Freedman’s inequality helps us establish a recursive relation on {‖Qt −Q?‖∞}Tt=0, 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 inequality, while we emphasize that it 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.

heading: 6 Additional related literature
text: 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 a new variant of Q-learning with the help of variance reduction. [30] focused on linear MDP and designed an algorithm called “Least-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 a 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 linearly-parameterized 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 ε-optimal policy was Ω̃( |S||A|(1−γ)3ε2 ). [5] also showed that model-based approach can output an ε-optimal value function with near-optimal sample complexity for ε ∈ (0, 1). Then [2] made significant progress on the challenging problem of establishing minimax optimal sample complexity in estimating an ε-optimal policy with the help of “leave-one-out” 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 Qlearning 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 Õ( |S||A|(1−γ)3ε2 ). Then more recently, [34] improved the lower bound of the
vanilla Q-learning algorithm in terms of its scaling with 11−γ and proved a matching upper bound Õ( |S||A|(1−γ)4ε2 ).

heading: 7 Discussion
text: This paper studies sample complexity of both model-based and model-free RL under a 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| × |A|, thus considerably reduce the required sample size for large-scale MDPs when K is relatively small. Our results are sharp, and the sample complexity bound for the model-based approach matches the minimax lower bound. The current work suggests a couple of directions for future investigation, as discussed in detail below.
• Extension to episodic MDPs. An interesting direction for future research is to study linear transition model in episodic MDP. This focus of this work is infinite-horizon discounted MDPs, and hopefully the analysis here can be extended to study the episodic MDP as well ([17, 18, 6, 27, 55, 26]).
• Continuous state and action space. The state and action spaces in this current paper are 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 of ε. Since both value functions and Q-functions can take value in [0, (1−γ)−1], ideally our theory should cover all choices of ε ∈ (0, (1−γ)−1]. However we require that ε ∈ (0, (1− γ)−1/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 − γ)−1]. While their work only focused on model-based RL under tabular MDP, an interesting future direction is to improve our theory to accommodate any ε ∈ (0, (1− γ)−1].
• General function approximation. Another future direction is 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 W911NF-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-2120 and the NSF grants DMS-1662139, DMS-1712591, DMS-2052926, DMS-2053832, and the NIH grant 2R01-GM072611-15.

Review summaries:
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.

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.  It 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$.  In 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.  This 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.  First, 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.  Via 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.  Second, 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.  Via 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.  Lastly, the authors complement the theoretical results by a detailed discussion comparing the theoretical guarantees on the performance of their approaches to that in [61].

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:  1. 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;  2. A model-free approach based on Q-learning achieves a sample complexity of  $O~(K / ((1 - \gamma)^3 \epsilon^2))$.

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.