An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
Year: 2022

Abstract:
A fundamental question in the theory of reinforcement learning is: suppose the optimal Q-function lies in the linear span of a given d dimensional feature mapping, is sample-efficient reinforcement learning (RL) possible? The recent and remarkable result of Weisz et al. (2020) resolves this question in the negative, providing an exponential (in d) sample size lower bound, which holds even if the agent has access to a generative model of the environment. One may hope that such a lower can be circumvented with an even stronger assumption that there is a constant gap between the optimal Q-value of the best action and that of the second-best action (for all states); indeed, the construction in Weisz et al. (2020) relies on having an exponentially small gap. This work resolves this subsequent question, showing that an exponential sample complexity lower bound still holds even if a constant gap is assumed. Perhaps surprisingly, this result implies an exponential separation between the online RL setting and the generative model setting, where sample-efficient RL is in fact possible in the latter setting with a constant gap. Complementing our negative hardness result, we give two positive results showing that provably sample-efficient RL is possible either under an additional low-variance assumption or under a novel hypercontractivity assumption.

heading: 1 Introduction
text: There has been substantial recent theoretical interest in understanding the means by which we can avoid the curse of dimensionality and obtain sample-efficient reinforcement learning (RL) methods [Wen and Van Roy, 2017, Du et al., 2019b,a, Wang et al., 2019, Yang and Wang, 2019, Lattimore et al., 2020, Yang and Wang, 2020, Jin et al., 2020, Cai et al., 2020, Zanette et al., 2020, Weisz et al., 2020, Du et al., 2020, Zhou et al., 2020b,a, Modi et al., 2020, Jia et al., 2020, Ayoub et al., 2020]. Here, the extant body of literature largely focuses on sufficient conditions for efficient reinforcement learning. Our understanding of what are the necessary conditions for efficient reinforcement learning is far more limited. With regards to the latter, arguably, the most natural assumption is linear realizability: we assume that the optimal Q-function lies in the linear span of a given feature map. The goal is to the obtain polynomial sample complexity under this linear realizability assumption alone.
This “linear Q∗ problem” was a major open problem (see Du et al. [2019a] for discussion), and a recent hardness result by Weisz et al. [2020] provides a negative answer. In particular, the result shows that even with access to a generative model, any algorithm requires an exponential number
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
of samples (in the dimension d of the feature mapping) to find a near-optimal policy, provided the action space has exponential size.
With this question resolved, one may naturally ask what is the source of hardness for the construction in Weisz et al. [2020] and if there are additional assumptions that can serve to bypass the underlying source of this hardness. Here, arguably, it is most natural to further examine the suboptimality gap in the problem, which is the gap between the optimal Q-value of the best action and that of the second-best action; the construction in Weisz et al. [2020] does in fact fundamentally rely on having an exponentially small gap. Instead, if we assume the gap is lower bounded by a constant for all states, we may hope that the problem becomes substantially easier since with a finite number of samples (appropriately obtained), we can identify the optimal policy itself (i.e., the gap assumption allows us to translate value-based accuracy to the identification of the optimal policy itself). In fact, this intuition is correct in the following sense: with a generative model, it is not difficult to see that polynomial sample complexity is possible under the linear realizability assumption plus the suboptimality gap assumption, since the suboptimality gap assumption allows us to easily identify an optimal action for all states, thus making the problem tractable (see Section C in Du et al. [2019a] for a formal argument).
More generally, the suboptimality gap assumption is widely discussed in the bandit literature [Dani et al., 2008, Audibert and Bubeck, 2010, Abbasi-Yadkori et al., 2011] and the reinforcement learning literature [Simchowitz and Jamieson, 2019, Yang et al., 2020] to obtain fine-grained sample complexity upper bounds. More specifically, under the realizability assumption and the suboptimality gap assumption, it has been shown that polynomial sample complexity is possible if the transition is nearly deterministic [Du et al., 2019b, 2020] (also see Wen and Van Roy [2017]). However, it remains unclear whether the suboptimality gap assumption is sufficient to bypass the hardness result in Weisz et al. [2020], or the same exponential lower bound still holds even under the suboptimality gap assumption, when the transition could be stochastic and the generative model is unavailable. For the construction in Weisz et al. [2020], at the final stage, the gap between the value of the optimal action and its non-optimal counterparts will be exponentially small, and therefore the same construction does not imply an exponential sample complexity lower bound under the suboptimality gap assumption.
Our contributions. In this work, we significantly strengthen the hardness result in Weisz et al. [2020]. In particular, we show that in the online RL setting (where a generative model is unavailable) with exponential-sized action space, the exponential sample complexity lower bound still holds even under the suboptimality gap assumption. Complementing our hardness result, we show that under the realizability assumption and the suboptimality gap assumption, our hardness result can be bypassed if one further assumes the low variance assumption in Du et al. [2019b] 1, or a hypercontractivity assumption. Hypercontractive distributions include Gaussian distributions (with arbitrary covariance matrices), uniform distributions over hypercubes and strongly log-concave distributions [Kothari and Steinhardt, 2017]. This condition has been shown powerful for outlier-robust linear regression [Kothari and Steurer, 2017], but has not yet been introduced for reinforcement learning with linear function approximation.
Our results have several interesting implications, which we discuss in detail in Section 6. Most notably, our results imply an exponential separation between the standard reinforcement learning setting and the generative model setting. Moreover, our construction enjoys greater simplicity, making it more suitable to be generalized for other RL problems or to be presented for pedagogical purposes.
1We note that the sample complexity of the algorithm in Du et al. [2019b] has at least linear dependency on the number of actions, which is not sufficient for bypassing our hardness results which assumes an exponential-sized action space.

heading: 2 Related work
text: Previous hardness results. Existing exponential lower bounds in RL [Krishnamurthy et al., 2016, Chen and Jiang, 2019] usually construct unstructured MDPs with an exponentially large state space. Du et al. [2019a] prove that under the approximate version of the realizability assumption, i.e., the optimal Q-function lies in the linear span of a given feature mapping approximately, any algorithm requires an exponential number of samples to find a near-optimal policy. The main idea in Du et al. [2019a] is to use the Johnson-Lindenstrauss lemma [Johnson and Lindenstrauss, 1984] to construct a large set of near-orthogonal feature vectors. Such idea is later generalized to other settings, including those in Wang et al. [2020a], Kumar et al. [2020], Van Roy and Dong [2019], Lattimore et al. [2020]. Whether the exponential lower bound still holds under the exact version of the realizability assumption is left as an open problem in Du et al. [2019a].
The above open problem is recently solved by Weisz et al. [2020]. They show that under the exact version of the realizability assumption, any algorithm requires an exponential number of samples to find a near-optimal policy assuming an exponential-sized action space. The construction in Weisz et al. [2020] also uses the Johnson-Lindenstrauss lemma to construct a large set of near-orthogonal feature vectors, with additional subtleties to ensure exact realizability.
Very recently, under the exact realizability assumption, strong lower bounds are proved in the offline setting [Wang et al., 2020b, Zanette, 2020, Amortila et al., 2020]. These work focus on the offline RL setting, where a fixed data distribution with sufficient coverage is given and the agent cannot interact with the environment in an online manner. Instead, we focus on the online RL setting in this paper.
Existing upper bounds. For RL with linear function approximation, most existing upper bounds require representation conditions stronger than realizability. For example, the algorithms in Yang and Wang [2019, 2020], Jin et al. [2020], Cai et al. [2020], Zhou et al. [2020b,a], Modi et al. [2020], Jia et al. [2020], Ayoub et al. [2020] assume that the transition model lies in the linear span of a given feature mapping, and the algorithms in Wang et al. [2019], Lattimore et al. [2020], Zanette et al. [2020] assume completeness properties of the given feature mapping. In the remaining part of this section, we mostly focus on previous upper bounds that require only realizability as the representation condition.
For deterministic systems, under the realizability assumption, Wen and Van Roy [2017] provide an algorithm that achieves polynomial sample complexity. Later, under the realizability assumption and the suboptimality gap assumption, polynomial sample complexity upper bounds are shown if the transition is deterministic [Du et al., 2020], a generative model is available [Du et al., 2019a], or a low-variance condition holds [Du et al., 2019b]. Compared to the original algorithm in Du et al. [2019b], our modified algorithm in Section 5 works under a similar low-variance condition. However, the sample complexity in Du et al. [2019b] has at least linear dependency on the number of actions, whereas our sample complexity in Section 5 has no dependency on the size of the action space. Finally, Shariff and Szepesvári [2020] obtain a polynomial upper bound under the realizability assumption when the features for all state-action pairs are inside the convex hull of a polynomial-sized coreset and the generative model is available to the agent.

heading: 3 Preliminaries

heading: 3.1 Markov decision process (MDP) and reinforcement learning
text: An MDP is specified by (S,A, H, P, {Rh}h∈[H]), where S is the state space, A is the action space with |A| = A, H ∈ Z+ is the planning horizon, P : S × A → ∆S is the transition function and Rh : S ×A → ∆R is the reward distribution. Throughout the paper, we occasionally abuse notation and use a scalar a to denote the single-point distribution at a.
A (stochastic) policy takes the form π = {πh}h∈[H], where each πh : S → ∆A assigns a distribution over actions for each state. We assume that the initial state is drawn from a fixed distribution, i.e. s1 ∼ µ. Starting from the initial state, a policy π induces a random trajectory s1, a1, r1, · · · , sH , aH , rH via the process ah ∼ πh(·), rh ∼ R(·|sh, ah) and sh+1 ∼ P (·|sh, ah). For a policy π, denote the distribution of sh in its induced trajectory by Dπh .
Given a policy π, the Q-function (action-value function) is defined as
Qπh(s, a) := E
[ H∑
h′=h
rh′ |sh = s, ah = a, π ] ,
while V πh (s) := Ea∼πh(s)[Qπh(s, a)]. We denote the optimal policy by π∗, and the associated optimal Q-function and value function by Q∗ and V ∗ respectively. Note that Q∗ and V ∗ can also be defined via the Bellman optimality equation2:
V ∗h (s) = max a∈A Q∗h(s, a), Q∗h(s, a) = E [ Rh(s, a) + V ∗ h+1(sh+1)|sh = s, ah = a ] .
The online RL setting. In this paper, we aim to prove lower bound and upper bound in the online RL setting. In this setting, in each episode, the agent interacts with the unknown environment using a policy and observes rewards and the next states. We remark that the hardness result by Weisz et al. [2020] operates in the setting where a generative model is available to the agent so that the agent can transit to any state. Also, it is known that with a generative model, under the linear realizability assumption plus the suboptimality gap assumption, one can find a near-optimal policy with polynomial number of samples (see Section C in Du et al. [2019a] for a formal argument).

heading: 3.2 Linear Q? function approximation
text: When the state space is large or infinite, structures on the state space are necessary for efficient reinforcement learning. In this work we consider linear function approximation. Specifically, there exists a feature map φ : S ×A → Rd, and we will use linear functions of φ to represent Q-functions of the MDP. To ensure that such function approximation is viable, we assume that the optimal Q-function is realizable. Assumption 1 (Realizability). For all h ∈ [H], there exists θ∗h ∈ Rd such that for all (s, a) ∈ S ×A, Q∗h(s, a) = φ(s, a) >θ∗h.
This assumption is widely used in existing reinforcement learning and contextual bandit literature [Du et al., 2019b, Foster and Rakhlin, 2020]. However, even for linear function approximation, realizability alone is not sufficient for sample-efficient reinforcement learning [Weisz et al., 2020]. In this work, we also impose the regularity condition that ‖θ∗h‖2 = O(1) and ‖φ(s, a)‖2 = O(1), which can always be achieved via rescaling.
Another assumption that we will use is that the minimum suboptimality gap is lower bounded. As mentioned in the introduction, this assumption is common in bandit and reinforcement learning literature. Assumption 2 (Minimum Gap). For any state s ∈ S, a ∈ A, the suboptimality gap is defined as ∆h(s, a) := V ∗ h (s) − Q∗h(s, a). We assume that minh∈[H],s∈S,a∈A {∆h(s, a) : ∆h(s, a) > 0} ≥ ∆min.

heading: 4 Hard Instance with Constant Suboptimality Gap
text: We now present our main hardness result: Theorem 1. Consider an arbitrary online RL algorithm that takes the feature mapping φ : S × A → Rd as input. In the online RL setting, there exists an MDP with a feature mapping φ satisfying Assumption 1 and Assumption 2 with ∆min = Ω(1), such that the algorithm requires min{2Ω(d), 2Ω(H)} samples to find a policy π with
Es1∼µV π(s1) ≥ Es1∼µV ∗(s1)− 0.05 with probability 0.1.
The remainder of this section provides the construction of a hard family of MDPs whereQ∗ is linearly realizable and has constant suboptimality gap and where it takes exponential samples to learn a
2We additionally define VH+1(s) = 0 for all s ∈ S.
near-optimal policy. Each of these hard MDPs can roughly be seen as a “leaking complete graph” (see detailed transtion probabilities below). Information about the optimal policy can only be gained by: (1) taking the optimal action; (2) reaching a non-terminal state at level H . We will show that when there are exponentially many actions, both events happen with negligible probability unless exponentially many trajectories are played.

heading: 4.1 Construction of the MDP family
text: In this section we describe the construction of the hard instance (the hard MDP family) in detail. Let m be an integer to be determined. The state space is {1̄, · · · , m̄, f}. The special state f is called the terminal state. At state ī, the set of available actions is [m] \ {i}; at the terminal state f , the set of available actions is [m− 1]. 3 In other words there are m− 1 actions available at each state. Each MDP in this family is specified by an index a∗ ∈ [m] and denoted byMa∗ . In other words, there are m MDPs in this family.
In order to construct the MDP family, we first find a set of approximately orthogonal vectors by leveraging the Johnson-Lindenstrauss lemma [Johnson and Lindenstrauss, 1984]. Lemma 1 (Johnson-Lindenstrauss). For any γ > 0, if m ≤ exp( 18γ
2d′), there exists m unit vectors {v1, · · · , vm} in Rd ′ such that for all i, j ∈ [m] such that i 6= j, |〈vi, vj〉| ≤ γ.
We will set γ = 14 and m = bexp( 1 8γ 2d)c. By Lemma 1, we can find such a set of d-dimensional unit vectors {v1, · · · , vm}. For the clarity of presentation, we will use vi and v(i) interchangeably. The construction ofMa∗ is specified below.
Features. The feature map, which maps state-action pairs to d dimensional vectors, is defined as φ(a1, a2) := (〈 v(a1), v(a2) 〉 + 2γ ) · v(a2), ∀a1, a2 ∈ [m], a1 6= a2,
φ(f, ·) := 0. Note that the feature map is independent of a∗ and is shared across the MDP family.
Rewards. For 1 ≤ h < H , the rewards are defined as
Rh(a1, a ∗) := 〈 v(a1), v(a ∗) 〉 + 2γ,
Rh(a1, a2) := −2γ [〈 v(a1), v(a2) 〉 + 2γ ] , (a2 6= a∗, a2 6= a1)
Rh(f, ·) := 0. For h = H , rH(s, a) := 〈φ(s, a), v(a∗)〉 for every state-action pair.
Transitions. The initial state distribution µ is set as a uniform distribution over {1̄, · · · , m̄}. The transition probabilities are set as follows.
Pr[f |a1, a∗] = 1,
Pr[·|a1, a2] = a2 : 〈 v(a1), v(a2) 〉 + 2γ f : 1− 〈 v(a1), v(a2) 〉 − 2γ , (a2 6= a∗, a2 6= a1)
Pr[f |f, ·] = 1. After taking action a2, the next state is either a2 or f . Thus this MDP looks roughly like a “leaking complete graph”: starting from state a, it is possible to visit any other state (except for a∗); however, there is always at least 1− 3γ probability of going to the terminal state f . The transition probabilities are indeed valid, because
0 < γ ≤ 〈 v(a1), v(a2) 〉 + 2γ ≤ 3γ < 1.
We now verify that realizability, i.e. Assumption 1, is satisfied. In particular, we claim the following. 3Note that for simplicity we assume different state could have different set of available actions. In the Supplementary Material we provide another construction where all states have the same set of available actions.
Lemma 2. In the MDPMa∗ , ∀h ∈ [H], for any state-action pair (s, a),Q∗h(s, a) = 〈φ(s, a), v(a∗)〉.
The lemma can be proved via induction, with the hypothesis being for all a1 ∈ [m], a2 6= a1, Q∗h(a1, a2) = (〈 v(a1), v(a2) 〉 + 2γ ) · 〈 v(a2), v(a ∗) 〉 , (1)
and that for all a1 6= a∗,
V ∗h (a1) = Q ∗ h(a1, a ∗) = 〈 v(a1), v(a ∗) 〉 + 2γ. (2)
From Eq. (1) and (2), it is easy to see that at state a1 6= a∗, for a2 6= a∗, the suboptimality gap is
∆h(a1, a2) := V ∗ h (a1)−Q∗h(a1, a2) > γ − 3γ2 ≥
1 4 γ.
Thus in this MDP, Assumption 2 is satisfied with ∆min ≥ 14γ = Ω(1). 4

heading: 4.2 The information-theoretic argument
text: Now we are ready to state and prove our main technical lemma. Lemma 3. For any algorithm, there exists a∗ ∈ [m] such that in order to output π with
Es1∼µV π(s1) ≥ Es1∼µV ∗(s1)− 0.05
with probability at least 0.1 forMa∗ , the number of samples required is 2Ω(min{d,H}).
We provide a proof sketch for the lower bound below. The full proof can be found in the Supplementary Material. Our main result, Theorem 1, is a direct consequence of Lemma 3.
Proof sketch. Observe that the feature map ofMa∗ does not depend on a∗, and that for h < H and a2 6= a∗, the reward Rh(a1, a2) also contains no information about a∗. The transition probabilities are also independent of a∗, unless the action a∗ is taken. Moreover, the reward at state f is always 0. Thus, to receive information about a∗, the agent either needs to take the action a∗, or be at a non-terminal state at the final time step (h = H).
However, note that the probability of remaining at a non-terminal state at the next layer is at most
sup a1 6=a2
〈v(a1), v(a2)〉+ 2γ ≤ 3γ ≤ 3
4 .
Thus for any algorithm, Pr[sH 6= f ] ≤ ( 3 4 )H , which is exponentially small. In other words, any algorithm that does not know a∗ either needs to “be lucky” so that sH = f , or needs to take a∗ “by accident”. Since the number of actions is m = 2Θ(d), either event cannot happen with constant probability unless the number of episodes is exponential in min{d,H}. In order to make this claim rigorous, we can construct a reference MDPM0 as follows. The state space, action space, and features ofM0 are the same as those ofMa. The transitions are defined as follows:
Pr[·|a1, a2] = a2 : 〈 v(a1), v(a2) 〉 + 2γ f : 1− 〈 v(a1), v(a2) 〉 − 2γ , (∀a1, a2 s.t. a1 6= a2)
Pr[f |f, ·] = 1.
The rewards are defined as follows: Rh(a1, a2) := −2γ [〈 v(a1), v(a2) 〉 + 2γ ] , ( ∀a1, a2 s.t. a1 6= a2)
Rh(f, ·) := 0. 4Here we ignored the terminal state f and the essentially unreachable state a∗ for simplicity. This issue will
be handled in the Supplementary Material rigorously.
Note thatM0 is identical toMa∗ , except when a∗ is taken, or when an trajectory ends at a nonterminal state. Since the latter event happens with an exponentially small probability, we can show that for any algorithm, the probability of taking a∗ inMa∗ is close to the probability of taking a∗ inM0. SinceM0 is independent of a∗, unless an exponential number of samples are used, for any algorithm there exists a∗ ∈ [m] such that the probability of taking a∗ inM0 is o(1). It then follows that the probability of taking a∗ inMa∗ is o(1). Since a∗ is the optimal action for every state, such an algorithm cannot output a near-optimal policy forMa∗ .

heading: 5 Upper Bounds under Further Assumptions
text: Theorem 1 suggests that Assumption 1 and Assumption 2 are not sufficient for sample-efficient RL when the number of actions could be exponential, and that additional assumptions are needed to achieve polynomial sample complexity. One style of assumption is via assuming a global representation property on the features, such as completeness [Zanette et al., 2020].
In this section, we consider two assumptions on additional structures on the transitions of the MDP rather than the feature representation that enable good rates for linear regression with sparse bias. The first condition is a variant of the low variance condition in Du et al. [2019b]. Assumption 3 (Low variance condition). There exists a constant 1 ≤ Cvar <∞ such that for any h ∈ [H] and any policy π,
Es∼Dπh [ |V π(s)− V ∗(s)|2 ] ≤ Cvar · ( Es∼Dπh [|V π(s)− V ∗(s)|] )2 .
The second assumption is that the feature distribution is hypercontractive. Assumption 4. There exists a constant 1 ≤ Chyper <∞ such that for any h ∈ [H] and any policy π, the distribution of φ(s, a) with (s, a) ∼ Dπh is (Chyper, 4)-hypercontractive. In other words, ∀π, ∀h ∈ [H], ∀v ∈ Rd,
E(s,a)∼Dπh [ (φ(s, a)>v)4 ] ≤ Chyper · ( E(s,a)∼Dπh [(φ(s, a) >v)2] )2 .
Intuitively, hypercontractivity characterizes the anti-concentration of a distribution. A broad class of distributions are hypercontractive with Chyper = O(1), including Gaussian distributions (of arbitrary covariance matrices), uniform distributions over the hypercube and sphere, and strongly log-concave distributions [Kothari and Steurer, 2017]. Hypercontractivity has been previously used for outlier-robust linear regression [Klivans et al., 2018, Bakshi and Prasad, 2020] and momentestimation [Kothari and Steurer, 2017].
We show that under Assumptions 1, 2, 3 or 1, 2, 4, a modified version of the Difference Maximization Q-learning (DMQ) algorithm [Du et al., 2019b] is able to learn a near-optimal policy using polynomial number of trajectories with no dependency on the number of actions.

heading: 5.1 Optimal experiment design
text: Given a set of d-dimensional vectors, G-optimal experiment design aims at finding a distribution ρ over the vectors such that when sampling from this distribution, the maximum prediction variance over the set via linear regression is minimized. The following lemma on G-optimal design is a direct corollary of the Kiefer-Wolfowitz theorem [Kiefer and Wolfowitz, 1960]. Lemma 4 (Existence of G-optimal design). For any set X ⊆ Rd, there exists a distribution ρX supported on X , known as the G-optimal design, such that
max x∈X
x> ( Ez∼ρXzz> )−1 x ≤ d.
Efficient algorithms for finding such a distribution can be found in Todd [2016].
In the context of reinforcement learning, the set X corresponds to the set of all features, which is inaccessible. Instead, one can only observe one state s at a time, and choose a ∈ A based on the features {φ(s, a)}a∈A. Such a problem is closer to the distributional optimal design problem described by Ruan et al. [2020]. For our purpose, the following simple approach suffices: given a state
s, perform exploration by sampling from the G-optimal design on {φ(s, a)}a∈A. The performance of this exploration strategy is guaranteed by the following lemma, which will be used in the analysis of Algorithm 1.
Lemma 5 (Lemma 4 in Ruan et al. [2020]). For any state s, denote the G-optimal design with its features by ρs(·) ∈ ∆A, and the corresponding covariance matrix by Σs := ∑ a ρs(a)φ(s, a)φ(s, a)
>. Given a distribution ν over states. Denote the average covariance matrix by Σ := Es∼νΣs. Then
Es∼ν [ max a∈A φ(s, a)>Σ−1φ(s, a) ] ≤ d2.
Note that the performance of this strategy is only worse by a factor of d (compared to the case where one can query all features), and has no dependency on the number of actions.

heading: 5.2 The modified DMQ algorithm
text: Overview. During the execution of the Difference Maximization Q-learning (DMQ) algorithm, for each level h ∈ [H], we maintain three variables: the estimated linear coefficients θh ∈ Rd, a set of exploratory policies Πh, and the empirical feature covariance matrix Σh associated with Πh. We initialize θh = 0 ∈ Rd, Σh := λrId×d and Πh to as a single purely random exploration policy, i.e., Πh = {π} where π chooses an action uniformly at random for all states.5
Each time we execute Algorithm 1, the goal is to update the estimated linear coefficients θh ∈ Rd, so that for all π ∈ Πh, θh is a good estimation to θ∗h with respect to the distribution induced by π. We run ridge regression on the data distribution induced by policies in Πh, and the regression targets are collected by invoking the greedy policy induced by {θh′}h′>h. However, there are two apparent issues with such an approach. First, for levels h′ > h, θh′ is guaranteed to achieve low estimation error only with respect to the distributions induced by policies Πh′ . It is possible that for some π ∈ Πh, the estimation error of θh′ is high for the distribution induced by π (followed by the greedy policy). To resolve this issue, the main idea in Du et al. [2019b] is to explicitly check whether θh′ also predicts well on the new distribution (see Line 5 in Algorithm 1). If not, we add the new policy into Πh′ and invoke Algorithm 1 recursively. The analysis in Du et al. [2019b] upper bounds the total number of recursive calls by a potential function argument, which also gives an upper bound on the sample complexity of the algorithm.
Second, the exploratory policies Πh only induce a distribution over states at level h, and the algorithm still needs to decide an exploration strategy to choose actions at level h. To this end, the algorithm in Du et al. [2019b] explores all actions uniformly at random, and therefore the sample complexity has at least linear dependency on the number of actions. We note that similar issues also appear in the linear contextual bandit literature [Lattimore and Szepesvári, 2020, Ruan et al., 2020], and indeed our solution here is to explore by sampling from the G-optimal design over the features at a single state. As shown by Lemma 5, for all possible roll-in distributions, such an exploration strategy achieves a nice coverage over the feature space, and is therefore sufficient for eliminating the dependency on the size of the action space.
The algorithm. The formal description of the algorithm is given in Algorithm 1. The algorithm should be run by calling LearnLevel on input h = 0.
Here, for a policy πh ∈ Πh, the associated exploratory policy π̃h is defined as
π̃h(sh′) =  π(sh′) (if h′ < h) Sample from ρsh(·) (if h′ = h) arg maxa φh′(sh′ , a) >θh′ (if h′ > h) . (3)
Here ρs(·) is the G-optimal design on the set of vectors {φ(s, ·)}a∈A, as defined by Lemma 4. Note that when h = 0, π̃h is always the greedy policy on {θh}h∈[H]. The choice of the algorithmic parameters (β, λr, λridge) can be found in the proof of Theorem 2.
5We also define a special Π0 in the same manner. Choice of λr and other parameters can be found in the Supplementary Material.
Algorithm 1: LearnLevel(h) Input: A level h ∈ {0, · · · , H}
1 for πh ∈ Πh do 2 for h′ = H,H − 1, · · · , h+ 1 do 3 Collect N samples {(sjh′ , a j h′)}j∈[N ] with s j h′ ∼ D π̃h h′ and a j h′ ∼ ρsj
h′ (π̃h defined in (3)) 4 Σ̂h′ ← 1N ∑N j=1 φ(s j h′ , a j h′)φ(s j h′ , a j h′) > 5 if ‖Σ− 1 2
h′ Σ̂h′Σ − 12 h′ ‖2 > β|Πh′ | then
6 Πh′ ← Πh′ ∪ {π̃h} 7 LearnLevel(h′) 8 LearnLevel(h)
9 if h = 0 then 10 Output greedy policy with respect to {θh}h∈[H] and exit 11 Σh ← λr|Πh|I , wh ← 0 ∈ R d 12 for i = 1, · · · , N |Πh| do 13 Sample π from uniform distribution over Πh 14 Execute π̃h (see (3)) to collect (sih, a i h, yi), where yi := ∑ h′≥h r i h′ is the on-the-go reward 15 Σh ← Σh + 1N |Πh|φ(s i h, a i h)φ(s i h, a i h) > 16 wh ← wh + 1N |Πh|φ(s i h, a i h)yi
17 θh ← ( (λridge − λr|Πh| )I + Σh )−1 wh

heading: 5.3 Analysis
text: We show the following theorem regarding the modified algorithm. Theorem 2. Assume that Assumption 1, 2 and one of Assumption 3 and 4 hold. Also assume that
≤ poly(∆min, 1/Cvar, 1/d, 1/H) (Under Assumption 3) or ≤ poly(∆min, 1/Chyper, 1/d, 1/H). (Under Assumption 4)
Let µ be the initial state distribution. Then with probability 1− , running Algorithm 1 on input 0 returns a policy π which satisfies Es1∼µV π(s1) ≥ Es1∼µV ∗(s1)− using poly(1/ ) trajectories.
Note that here both the algorithm and the theorem have no dependence on the number of actions A. The proof of the theorem under Assumption 3 is largely based on the analysis in Du et al. [2019b]. The largest difference is that we used Lemma 5 instead of the original union bound argument when controlling Pr [ supa |θ>h φ(s, a)Q∗h(s, a)| > γ 2 ] . The proof under Assumption 4 relies on a novel analysis of least squares regression under hypercontractivity. The full proof can be found in the Supplementary Material.

heading: 6 Discussion
text: Exponential separation between the generative model and the online setting. When a generative model (also known as simulator) is available, Assumption 1 and Assumption 2 are sufficient for designing an algorithm with poly(1/ , 1/∆min, d,H) sample complexity [Du et al., 2019a, Theorem C.1]. As shown by Theorem 1, under the standard online RL setting (i.e. without access to a generative model), the sample complexity is lower bounded by 2Ω(min{d,H}) when ∆min = Θ(1), under the same set of assumptions. This implies that the generative model is exponentially more powerful than the standard online RL setting.
Although the generative model is conceptually much stronger than the online RL model, previously little is known on the extent to which the former is more powerful. In tabular RL, for instance, the known sample complexity bounds with or without access to generative models are nearly the same [Zhang et al., 2020, Agarwal et al., 2020]. To the best of our knowledge, the only existing example of such separation is shown by Wang et al. [2020a] under the following set of conditions: (i)
deterministic system; (ii) realizability (Assumption 1); (iii) no reward feedback (a.k.a. reward-free exploration). In comparison, our separation result holds under less restrictions (allows stochasticity) and for the usual RL environment (instead of reward-free exploration), and is thus far more natural.
Connecting Theorem 1 and Theorem 2. Our hardness result in Theorem 1 shows that under Assumption 1 and Assumption 2, any algorithm requires exponential number of samples to find a near-optimal policy, and therefore, sample-efficient RL is impossible without further assumptions (e.g., Assumption 3 or 4 assumed in Theorem 2). Indeed, Theorem 1 and Theorem 2 imply that the coefficients Cvar and Chyper in Assumption 3 and 4 are at least exponential for the hard MDP family used in Theorem 1, which can also be verified easily.
Open problems. The first open problem is whether a sample complexity lower bound under Assumption 1 can be shown with polynomial number of actions. This will further rule out poly(A, d,H)style upper bounds, which are still possible with the current results. Another open problem is whether Assumption 3 or 4 can be replaced by or understood as more natural characterizations of the complexity of the MDP.
Acknowledgments and Disclosure of Funding
The authors would like to thank Kefan Dong and Dean Foster for helpful discussions. Sham M. Kakade acknowledges funding from the ONR award N00014-18-1-2247 and from the National Science Foundation under award #CCF-1703574. Ruosong Wang was supported in part by the NSF IIS1763562, US Army W911NF1920104, and ONR Grant N000141812861.

Review summaries:
This paper considers online RL with linear realizability of Q* and a suboptimality gap assumption. It shows an exponential sample complexity lower bound holds for this setting, but under an additional assumption of either (a) or (b), there is an algorithm (modified DMQ) that achieves a polynomial upper bound, showing sample-efficient RL is possible in this setting. The additional assumption required for this is either (a) low variance of value differences between some policy pi and the optimal policy, or (b) hypercontractivity of the distribution of features encountered along any policy.  The negative result is a modification of Weisz et al 2020’s construction of hard MDPs into a “leaky” graph that allows for a large suboptimality gap. The positive result is similar in algorithm and analysis to Du et al 2019b, with the novelties that (1) a number-of-actions factor in the sample complexity is avoided by sampling actions from an optimal design, and (2) the method is shown to work for assumption (b).   (1) is important to make the separation between the lower and upper bounds clear as the lower bound uses exponentially many actions. As the authors point out, these results also imply that there is an exponential separation between online RL and RL with a generative model, as in the latter, sample-efficient learning is possible in the same setting as this paper’s lower bound.

This paper studies lower bounds for the linear-$Q^*$ setting with a gap>0 assumption. Recently Weisz et al prove a milestone result that the linear-$Q^*$ setting requires exponential in d sample complexity. However the gap in these instances, the gap is exponentially small too. It is known that with linear-$Q^*$ assumption + gap>0 , an optimal policy can be learned with polynomial (in all parameters) sample complexity given access to a generative model. The result of this paper thus establishes a separation in the sample complexity compared to the online setting under the same assumptions. In addition, the authors also propose algorithms that break the exponential sample complexity lower bounds in this setting under either of (I) a low variance assumption on the variance of the value of any policy from $V^*$ under its own state distribution, or (II) a $(C,4)$-hypercontractivity assumption on the feature vector distribution under any policy. The proof under the latter assumption follows from a novel analysis of least squares regression under hypercontractivity assumptions.

This is a technical paper that considers online RL with linear function approximation under the assumptions: 1) Q^* is realizable, 2) gap = V^*(s) - Q^*(s,a) > 0 for all (s,a). The first result is an unfortunate impossibility result that gives an exponential sample lower bound without further assumptions. Then under additional assumptions on system dynamics, a variation of existing algorithm (Difference Maximization Q-Learning) returns a near-optimal policy in polynomial time.