An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap
Authors: Yuanhao Wang
Ruosong Wang
Sham M. Kakade
Venue: NeurIPS 2021 Oral (2021)
Keywords: Reinforcement Learning
Linear Function Approximation
Lower Bound

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 \emph{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.

An Exponential Lower Bound for Linearly-Realizabll MDPs with Constant Suboptimality Gap
Yuanhao Wang Princeton University
Ruosong Wang
Carnegie Mellon University ruosongv@andres. cmu.
yuanhao@princeton..oo
Sham M. Kakade
University of Washington and Microsoft Research shamêcs. washington, edu
Abstract
A fundamental question in the theory of reinforcement learning is: suppose the optimal Q-function lies in the linear span of given d dimensional feature map- ping, 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 lower can be circumvented with 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 exponential sample complexity lower bound still holds even if a constant gap is assumed. Perhaps surprisingly, this result implies an expo- nential 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-efficien RL is possible either under an additional low-variance assumption or under novel hypercontractivity assumption.
stronger assumption that there
Introduction
There has been substantial recent theoretical interest in understanding the means by which can avoid the curse of dimensionality and obtain sample-efficiae
reinforcement learning (RL)
methods [Wen and Van Roy 2017 Du et al. [019b la 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.
Weisz et al. 2020 Du al.) 2020 Zhou al. 2020b a Modi al.] 2020 Jia 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 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 al. (2000 provides 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 (NcurIPS 2021).

---

Minimum Gap?
Generative Model
Online RL
No
Exponential
Weisz et al.
2020
Exponential [Weisz et al. 2020
Yes
Polynomial [Du et al.
2019a]
Exponential (This work, Theorem
Table I: Known sample complexity results for RL with linear function approximation under re- alizability. "Exponential" refers to exponential lower bound (in the dimension or horizon), while "polynomial" refers to polynomial upper bound.
of samples (in the dimension d of the feature mapping) to find 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 al. [2020) and if there are additional assumptions that can serve 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-bes 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 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 ct al., 2008 Auudibert and Bubeck 2010 Abbasi- Yadkori et al. 2011 and the reinforcement learning literature [Simchowitz and Jamieson 2019] Yang et al.) [2020] to obtain fine- fine-grained sample com- plexity 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 (2077). However, it remains unclear whether the suboptimality gap assumption is sufficient to bypass the hardness result in Weisz jet 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 al. (202)). In particular, we show that in the online RL setting (where a generative model is unavailable) with exponential-sizee 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. [2019)] | or a hypercontractivity assumption. Hypercontractive distributions include Gaussian distributions (with arbitrary covariance matrices), uniform distributions over hypercubes and strongly log- log-concave distributions (Kothari and Steinhardt (017). This condition has been shown powerful for outlier-robust linear regres- sion [Kothari and Steurer (017], 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 be presented for pedagogical purposes.
We 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-size action space.
2

---

2
Related work
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- 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.
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 (201). 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 Du et al. [2019a].
[2019a] is to use the Johnson-Lindenstran
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-sizze action space. The construction in Weisz lemma to construct a large set of hear-orthogonal feature vectors, with additional subtleties ensure exact realizability.
et al. 2020] also uses the Hhanson-Lindensteen
Very recently, under the exact realizability assumption, strong lower bounds are proved the offline setting [Wang et al., 2020bb Zanette, 2020 Ammrttia et al. 22020). These work focus the offline RL setting, where a fixed data distribution with sufficient coverage is given and the agent cannot interact with the environment in 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), JJnn et al. 2020], Cai et al. 2020). [Zhou et al. (2020bla]. Modi et al. [2220] Jia et al. 2020)) Ayoub et al. [2020) assume that the transition model lies in the linear span of
given feature mapping, and the algorithms in Wang et al. (219), Lattimore et al. [2020). |anette 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 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 ct al. [2019b], our modified algorithm in Section works under similar low-variance condition. However, the sample complexity in Du et al.
[2019b] has at least linear dependency on the number of
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 fate-acctoon pairs inside the convex hull of a polynomial sized coreset and the generative model is available to the agent.
actions, whereas our sample complexity in Section 5 has no dependency
3 Preliminaries
3.1 Markoy decision process (MDP) and reinforcement learning
An MDP is specified by (R, with [A| = A, H -+ is the planning horizon, P: S x A + As is the transition function and RA S x - Ag is the reward distribution. Throughout the paper, we occasionally abuse notation and use a scalar a to denote the single-pons point distribution at a.
where S is the state space, A is the action space
A (stochastic) policy takes the form π = } he([F) where each S + AA assigns distribution over actions for each state. We assume that the initial state is drawn from a fixed distribution, i.e. 81 ~ μ.. Starting from the initial state, a policy æ induces random trajectory 81, 01, r1.............................. 88,, aH TH via the process as ~ ()), Fh ~ R(-[sh; aa) and 8h+1 1 ~ P(- an). For policy n, denote the distribution of 5 in its induced trajectory by DT.
3

---

Given policy x. the Q-function (action-valie function) is defined as
H
(x( =
Σ
18 = 8, O4 = a,
while (s) (s) == E (aw Q (s, a)}. We denote the optimal policy by 't, 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 equation
(s) mmx (s, aEA
Q, a) = E [R, a) +
Gb = 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 policy and observes rewards and the next states. We remark that the hardness result by Weisz ct al. [2200] operates the setting where a generative model available to the agent so that the agent can transit to any state. Also, it is known that with generative model, under the linear realizability assumption plus the suboptimality gap assumption, one can find near- cetr-oltimal policy with polynomial number of samples (see Section C in Du et al. [2019a] for formal argument).
3.2 Linear Q' function approximation
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 x + 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 realizable.
Assumption 1 (Realizability). For all h E [H], there exists 0% Rd such that for all (s,a) ESxA Q7,(s, a) = a)
This assumption is widely used in existing reinforcement learning and contextual bandit literature Du al. 20196 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,
also impose the regularity condition that |10%, l2 O(1) and [0s l) 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 the introduction, this assumption is common in bandit and reinforcement learning literature.
Assumption 2 (Minimum Gap). For any state E S, a E A, the suboptimality gap is defined as (s, (s) Q7 (s, a). We assume that sin (A, a) a) > 0} >
Amin.
4 Hard Instance with Constant Suboptimality Gap
We now present our main hardness result:
Theorem 1. Consider arbitrary online RL algorithm that takes the feature mapping ò S x
A + d as input. In the online RL setting, there exists an MDP with a feature mapping o satisfying Assumption and Assumption 2 with Amin 2(1), such that the algorithm requires min (22(H)) samples find a policy with
[
Ezjoy (s1) 2 EE 0.05
with probability 0.1.
The remainder of this section provides the construction a hard family of MDPs where Q" is linearly realizable and has constant suboptimality gap and where it takes exponential samples to learn
We additionally define Vzz+(ss) 0 for all S.

---

near-optimal policy. Each of these hard MDPs can roughly be seen as "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.
4.1 Construction of the MDP family
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 {I, ... m, f]- The special state f is called the terminal state. At state i. the set of available actions [m]] {i}: the terminal state f. the set of available actions is Im ll. In other words there are m 1 actions available at each state. Each MDP in this family is specified by an index m MDPs in this family.
[m]] and denoted by Ma.. In other words, there
In order construct the MDP family, first find of approximately orthogonal vectors by leveraging the Mhanson-Lindensrrane lemma [Johnson and Lindenstrauss) [984].
Lemma (oobsson-Lindenstraass)) For any y O, m exp()>²dd) there exists m unit vectors (V1,'. )m in RRd such that for all i, E [m] such that + j. (V,, uy)l 5-
We will set 7 = 1 and m = Lexp( $ unit vectors -. , Um J. For the clarity of presentation, will use o; and v(i) interchangeably. The construction of Ma- is specified below.
{ dd).. By Lemmal | we can find such a set of d-dimensional
Features.
The feature map, which maps state-action pairs to d dimensional vectors, is defined as o(āT, a2) = ((v(a)), v((a)) + 27) v(a2),
Val, 02 E [m]] ai o a2
<(f.-) 0.
Note that the feature map is independent of a" and shared across the MDP family. Rewards.
For 1 < h < H. the rewards are defined
Rg (TT, a²) = (v(a)) 2%
Rí Ra 02) = 22 (u((a)).v(a)) 27/
(a2 + a² 02 + a1)
Rx(fs)) = O.
For h HI ()( = (ø(s, a), v(a")) for every state-action pair.
Transitions. The initial state distribution is set as uniform distribution over (I. .I........ m.. The transition probabilities are set as follows.
Pr[f[ai, a=] =
α2 (o(ar), + +
Pr| a2] =
(a2 + a", a2 + a1)
f (((a)), v(az) - 27
Pr[
After taking action a2 the next state is either 0g or f. Thus this MDP looks roughly like a "leaking complete graph": starting from state a, it possible to visit any other state (except for a²); however, there always at least 1- 3y probability of going to the terminal state f. The transition probabilities indeed valid, because
0 0<>5 (((1),, u(())))(()))))))))))))))))) 2 S 37 < 1.
We now verify that realizability. i.c. Assumption is satisfied. In particular, we claim the following.
NNot that for simplicity we assume different state could have different set of available actions. In the Supplementary Material provide another construction where all states have the same set of available actions.
5

---

Lemma 2. In the MDP Ma.. wh E for any state-action pair (s,a). (s a) = (0(s, v(2,))))))))))))))))))))))))))))
The lemma can be proved via induction, with the hypothesis being for all a [m], a2 # as
Qi(ai, 02) (( ((v(a)), o((z)) + 27) (u((a): u(a"))
and that for all an a",
V ( (T a²) (o(as), o(aa)) 22
From Eq. (1 and (2). it is easy to that at state बe + a", for a2 + a", the suboptimality gap is
A (11, a2) == Vi (an) Q% (aT, > 3, 4
Thus in this MDP, Assumption is satisfied with Amin 2 / = 22(1)
4.2
The information-theorede argument
Now are ready to state and prove our main technical lemma. Lemma 3. For any algorithm, there exists a" E [mm]] such that in order ouipul with
Esyog V (81) 2 ( 0.05
with probability at least 0.1 for Ma-, the number of samples required is (dm
provide proof sketch for the lower bound below. The full proof can be found in the Supplemen- tary Material. Our main result, Theorem I is a direct consequence of Lemma 3
Proof sketch. Observe that the feature map of Ma. does not depend on a", and that for h < H and 02 A a", the reward RA (TT, 02) also contains no information about a". The transition probabilities are also independent 0. Thus, to receive information about a*, the agent either needs to take the action a", or be at non-terminal state at the final time step (h H).
a", unless the action a* is taken. Moreover, the reward at state f always
However, note that the probability of remaining at non-terminal state at the next layer is at most
3
sup v((2)) + 2 s 37 S 01//02
Thus for any algorithm, Pr[SH # f (2) " which is exponentially small.
In other words, any algorithm that does not know a' either needs to "be lucky" so that 8H = f. or needs to take a" "by accident". Since the number of actions is m = 28(4), 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 MDP Mn as follows. The state space, action space, and features of Mn the same those of Ma- The transitions are defined as follows:
:ee:((uon (u(ar), + + f u(ar),, v((2)) 27
Pr|. az)
(Va), s.t. an + az)
The rewards are defined as follows:
Ra u2) = -2 (v(()))) + +27
(Yai, 02 s.t. a # a2)
(f.f.)) =-
'Here 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 that Mo is identical to Mar, except when a" is taken, or when an trajectory ends at non- terminal state. Since the latter event happens with an exponentially small probability, we can show that for any algorithm, the probability of taking a" in Ma- is close to the probability of taking a" in Ma- Since Mo is independent of a", unless an exponential number of samples are used, for any algorithm there exists a" E [m]] such that the probability of taking a" in Mo is o( )). It then follows that the probability of taking a" Ma is o(1). Since a" the optimal action for every state, such an algorithm cannot output near-optimal policy for Ma
5 Upper Bounds under Further Assumptions
Theorem [ suggests that Assumption | and Assumption 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 global representa- tion property on the features, such completeness Zanette 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 (Low variance condition). There exists a constant h [H] and any policy r,
S Cvas < oo such that for any
EywDy (P)(s) S Cvar (BanDy
-V
The second assumption is that the feature distribution is hypercontractive.
Assumption 4. There exists a constant S Chyper < oo such that for any h E [H] and any policy the distribution of o(s, a) with (s, a) ~ Dj, is (Chyper, -h-hyyercootrractive. In other words, Vi, vh E [M], Vo R
((, [[0(s, a) [D]]] < Chyper (E)ss))=,;((((s,, ()))s
[[
Intuitively, hypercontractivity characterizes the anti-connentraatio 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 moment-
estimation Kothari and Steurer 2017).
We show that under Assumptions 2 or 12 modified version of the Difference Maximization Q-learning (DMQ) algorithm DDu al. 2019b] able to learn near-optimal policy using polynomial
number of trajectories with no dependency on the number of actions.
5.1 Optimal experiment design
Given set of d-dimensional vectors, G-optimal experiment design aims at finding distribution p over the vectors such that when sampling from this distribution, the maximum prediction variance over the set via linear regression minimized. The following lemma on G-optimal design is direct corollary of the Kiefer-Wool Wolfowitz theorem [Kiefer and Wolfowitz/ [960].
Lemma 4 (Existence of G-optimal design). For any set X S Rd. there exists a distribution px supported on X, known the G-optimal design, such that
max x zEX
(Eznpx 2z 2 < d.
Efficient algorithms for finding such distribution can be found in Todd (016).
In the context reinforcement learning, the set X corresponds to the set of all features, which is inaccessible. Instead, one can only observe one state s at time, and choose E A based on the features (d(s, a) ). Such a problem closer to the distributional optimal design problem described by Ruan al. 22020.. For purpose, the following simple approach suffices: given state
7

---

perform exploration by sampling from the G-optimal design on {o(s, a) The performance of this exploration strategy guaranteed by the following lemma, which will be used in the analysis of Algorithm] I
Lemma 5 (Lemma 4 in Ruan al. (0200). For any state denote the G-optimal design with its fea-
tures by (-(-) E A and the corresponding covariance matrix by L. := P=(P)())) (((())( a ())(,, a)
Given distribution v states. Denote the average covariance matrix by Σ == Egwy Eg. Then
Egwy
max ((ss,))T=-lll aEA
S dd.
Note that the performance of this strategy is only worse by factor of d (compared to the case where one can query all features), and has no dependency on the number of actions.
5.2 The modified DMQ algorithm
Overview. During the execution of the Difference Maximization Q-learning (DMQ) algorithm, for each level h E [. we maintain three variables: the estimated linear coefficients 0, IR a set of exploratory policies lIs, and the empirical feature covariance matrix Σn associated with Il, We initialize 0₂ = 0 E Rdd Σn == Aalaxd and II, to as a single purely random exploration policy, i.e., II } where chooses action uniformly random for all states 1
Each time we execute Algorithm| 1. the goal is to update the estimated linear coefficients 0, E Rd, so that for all E T, 0% is good estimation 0% with respect the distribution induced by We run ridge regression on the data distribution induced by policies in 1I, and the regression targets are collected by invoking the greedy policy induced by {0w Juss..
However, there are two apparent issues with such an approach. First, for levels h > On is guaranteed achieve low estimation error only with respect to the distributions induced by policies I1. is possible that for some π E II, the estimation error of f₂ is high for the distribution induced by (followed by the greedy policy). To resolve this issue, the main idea in Du et al. (20196] is to explicitly check whether O₂ also predicts well on the new distribution (see Line Al Algorithm| 1). not, add the new policy into NT and invoke Algorithm 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 II, only induce a distribution over states at level h, and the algorithm still needs to decide exploration strategy to choose actions at level h. To this end, the algorithm Du et al. [209b) explores all actions uniformly at random, and therefore the sample complexity has at least linear dependency 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 explore by sampling from the G-optimal design over the features As shown by Lemma 5, for all possible roll-in distributions, such an exploration strategy achieves a nice coverage the feature space, and is therefore sufficient for eliminating the dependency the size of the action space.
single state.
The algorithm. The formal description of the algorithm is given in Algorithm | should be run by calling LearnLevel on input
The algorithm
Here, for policy mi E Il, the associated exploratory policy 7n is defined as
T ((w)
(if h' < h)
Sample from Pea. (-) TA (sw)
(if h = h)
(3)
arg max, dwwws (SN a) On
(if h' h)
Here (-).) is the G-optimal design on the set of vectors {Ø(8, ))aAA as defined by Lemma 4 Note
that when 0, 7t is always the greedy policy on {0, )- The choice of the algorthmmic parameters (3, Xr, Aridge) can be found in the proof of Theorem
'We also detine special 1lp in the same manner. Choice of A, and other parameters can be found in the Supplementary Material.
8

---

Algorithm 1: LearnLeve((h)
Input: level h E {0,... H}}
for Th E I, do
for h' = H, H 1, ,h do
Collect N samples "e),, with o%. ~ Di and a ~ Pojy (an defined in 3)
EN N EE= (( ax ) oT
Lear)Level(h') M Ex 2 112 > 8|11,/| then
Il < N2 U }
LeamLevel(h)
9 if h 0 then
Output greedy policy with respect to (Onm and exit
Σn mm wh E Rd
12
for i = 1, .N |IAA| do
13
Sample ı from uniform distribution over I
Execute nn (see (3) collect (s), af. ys), where Yi = En'a r/e is the on-the reward
14
15
Mn + Mn + M (s of jo))) a;)"
wh + Wh + NIT (s), ( a3)y
16
0%. + (Aridgee Ar T Σn,
17
5.3 Analysis
We show the following theorem regarding the modified algorithm.
Theorem 2. Assume that Assumption 7 2 and one of Assumption and hold. Also assume that
6 < poly (min 1/C 1/d.1/R
(Under Assumption
E polyyoll (Amin 1/Chyper: 1/d, 1/H).
(Under Assumption
Let ( be the initial state distribution. Then with probability c, running Algorithml on imput returns policy which satisfies Egy V (81) 2 Vn
(*1)
using poly(1/c) 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| Bis 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 10, o(s, Q7 (s, a)l > I The proof under Assumption 4 relies on novel analysis of least squares regression under hypercontractivity. The full proof can be found in the Supplementary Material.
Discussion
Exponential separation between the generative model and the online setting. When a generative
model (also known as simulator) is available, Assumption [ and Assumption 2 are sufficient for designing an algorithm with poly(1/e, 1//e,,//nnnn 1/Amin, d, H)) sample complexity (Du et al. 2019a Theorem C.I]. As shown by Theorem [ under the standard online RI setting (i.e. without access to a generative model), the sample complexity lower bounded by (m,mi)(d,HH) when Amin = ((), 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 known on the extent which the former is more powerful. tabular RL, for instance, the known sample complexity bounds with without access to generative models are nearly the same /Zhang et al., 20200 Agarwal al. 2020]. To the best of our knowledge, the only existing example of such separation shown by Wang et al. 2020al under the following set of conditions: (i)

---

deterministic system; (ii) realizability (Assumption I (iii) reward feedback (a.k.a. reward- free exploration). In comparison, our separation result holds under less restrictions (allows stochasticity) and for the usual RI. environment (instead of reward-free exploration), and is thus far more natural.
Connecting Theorem | and Theorem 2 Our hardness result in Theorem I shows that under Assumption D Jand Assumption any algorithm requires exponential number of samples to find near-optimal policy, and therefore, sample-efficient RL is impossible without further assumptions (e.g., Assumption or assumed in Theorem 2). Indeed, Theorem and Theorem 2 imply that the coefficients Cvar and Chype in Assumption and are at least exponential for the hard MDP family used Theorem which can also be verified easily.
Open problems. The first open problem is whether sample complexity lower bound under As- sumption[] can be shown with polynomial number actions. This will further rule out poly(A, (A, d. H)- style upper bounds, which are still possible with the current results. Another open problem whether Assumption 3 can be replaced by or understood as more natural characterizations of the com- plexity of the MDP
Acknowledgments and Disclosure of Funding
The authors would like thank Kefan Dong and Dean Foster for helpful discussions. Sham M. Kakade acknowledges funding from the ONR award N00014-18-1-2277 and from the National Science Foundation under award #CCC-11035777 Ruosong Wang was supported in part by the NSF IIS1763562, US Army INII122001, and ONR Grant N000141812861.
References
Y. Abbasi-Yadkori D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits, In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
A. Agarwal, S. Kakade, and L. F. Yang. Model-basee reinforcement learning with generative model is minimax optimal. In Conference on Learning Theory, pages 67-83 PMLR, 2020.
P. Amortila, N. Jiang, and T. Xie. A variant of the wang- kasker- lower bound for the discounted setting. arXiv preprint arXiv:2011.0105,, 2020.
J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits. In COLT-23th Conference on learning theory-2010, pages 13-p, 2010.
A. Ayoub, Z. Jia, C. Szepesvari, M. Wang, and L. Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR, 2020.
A. Bakshi and A. Prasad. Robust linear regression: Optimal rates in polynomial time. arXiv preprint PrXiv:2007.0194 2020.
Q. Cai, Z. Yang. C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
J. Chen and N. Jiang. Information thhooretic considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR, 2019.
V. Dani. T. P. Hayes, and S. M. Kakade, Stochastic linear optimization under bandit feedback. In Conference on Learning Theory, 2008
S. S. Du, S. M. Kakade, R. Wang, and I.. F. Yang. Is good representation sufficient for sample efficient reinforcement learning? International Conference on Learning Representations, 2019. aa.
S. S. Du, Y. Luo, R. Wang, and H. Zhang. Provably efficient q-learning with function approximation via distribution shift error checking oracle. In Advances in Neural Information Processing Systems, pages 8060-8070, 2019b.
10

---

S. S. Du, J. D. Lee. G. Mahajan, and R. Wang. Agnostic g-learming with function approximation in deterministic systems: Near-optimal bounds on approximation error and sample complexity. Advances in Neural Information Processing Systems, 33, 2020.
D. Foster and A. Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
Z. Jia, L. Yang, C. Szepesvari, and M. Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pages 666-686. PMLR, 2020.
C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pages 2137-2143, PMLR, 2020.
W. B. Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contem- porary mathematics, 26(189-206)11, 1984.
Kiefer and J. Wolfowitz. The equivalence of extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
A. Klivans, P. K. Kothari, and R. Meka. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory, pages 1430. PMLR, 2018
P. K. Kothari and J. Steinhardt. Better agnostic clustering via relaxed tensor norms. arXiv preprint 17X1v:1711.07465. 2017.
K. Kothari and D. Steurer. Outlier-robus' moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581, 2017.
A. Krishnamurthy, A. Agarwal, and J. Langford. Pac reinforcement learning with rich observations. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1848-1856, 2016.
A. Kumar, A. Gupta, and S. Levine. Discor: Corrective feedback in reinforcement learning via distribution correction. arXiv preprint arXiv:2003.07303 2020.
Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lattimore, C. Szepesvari, and G. Weisz. Learning with good feature representations in bandits and in rl with generative model. In International Conference on Machine Learning, pages 5662-5670. PMLR, 2020.
A. Modi, N. Jiang. A. Tewari, and S. Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
Y. Ruan, Yang, and Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. arXiv preprint arXiv:2007.019800 2020.
R. Shariff and C. Szepesvári. Efficient planning in large mdps with weak linear function approxima- tion. arXiv preprint arXiv:2007.06//6 2020.
M. Simchowitz and K. Jamieson. aon-asympiotic gap-dependent regret bounds for tabular mdps. arXiv preprint orXiv:1905.. 00814,, 2019.
M. Todd. Minimum- Volume Ellipsoids: Theory and Algorithmss, volume 23. SIAM, 2016.
B. Van Roy and S. Dong. Comments on the du-kakkade-wagg-yany lower bounds. arXiv preprint arXiv: 19l.://99//////1 2019.
R. Wang, S. S. Du, I. F. Yang, and R. Salakhutdinov. On reward-free reinforcement learning with linear function approximation. arXiv preprint arXiv:2006. /274, 2020a.
R. Wang, Foster, and Kakade. What are the statistical limits of offline rl with linear function approximation? arXiv preprint 2rXiv:2010.11895, 2020b.

---

Y. Wang, R. Wang. S. S. Du, and A. Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:1912.04136, 2019.
G. Weisz, P. Amortila, and C. Szepesvári. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-valle value functions. arXiv preprint arX1v:2010.01374, 2020.
Z. Wen and B. Van Roy. Efficient reinforcement learning in deterministic systems with value function generalization. Mathematics of Operations Research, 42(3):762-782, 2017.
K. Yang, L. F. Yang, and S. S. Du. q-learning with logarithmic regret. arXiv preprint arXiv:2006.09111 2020.
L. Yang and M. Wang. Sample-optinal parametric q-learning using linearly additive features. In International Conference Machine Learning, pages 6995-7004. PMLR, 2019.
L. Yang and M. Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-
PMLR, 2020.
A. Zanette, Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. arXiv preprint arXiv:2012.08003 2020.
A. Zanette, A. Lazaric, M. Kochenderfer, and E. Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference Machine Learning, pages 10978-10989, PMLR, 2020.
Z. Zhang, Y. Zhou, and X. Ji. Almost optimal model-free reinforcement learningvia reference- advantage decomposition. Advances in Neural Information Processing Systems, 33, 2020.
D. Zhou, Q Gu, and C. Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. arXiv preprint arXiv:2012.08507, 2020a.
D. Zhou, J. He, and Q. Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. arXiv preprint arXi::200..1316, 2020b.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work theoretical in nature and does not have immediate social impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? Yes]]
2. If you including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Assump-
tions T 2 and
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs of all theorems and lemmas are included the Supplementary Material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A] No datasets are used.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] No empirical experiments involved.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A] No empirical experiments are involved.
12

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A] No empirical experiments are involved.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A] No existing assests are used.
(b) Did you mention the license of the assets? [N/A] No existing assests used.
(C) Did you include any new assets either in the supplemental material or as a URL? [N/A] No existing assests are used.
(d) Did you discuss whether and how consent obtained from people whose data you're re using/curating? [N/A] No existing assests are used.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] No existing assests are used.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] No crowdsourcing/huma. subjects are used.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] No crowdsourcinghuuman subjects used.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] No crowdsourcing/human subjects are used.
13


Reviews:
[{"review_id": "tba6cZN55vU", "reviewer": "Reviewer_HMEJ", "summary": "The authors present exponential lower bounds under perfect realizability when the model must be learned online even with constant action-value function gaps. An upper bound is presented under a new hypercontractivity assumption.", "questions": "", "limitations": "", "rating": 8, "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": "I thank the authors for their submission, I liked the work very much.\n\nStrengths:\n+ the work has some genuinely new ideas in the construction (although it leverages prior techniques like JL lemma)\n+ it clarifies what’s achievable in the far more interesting online setting (i.e., the separation with the generative model setting)\n+ the construction is easier than Weisz et al ’20, making it more amenable to explanation\n\nI read the upper bound section a bit faster, but I’d like the authors to clarify a bit better the assumption about hypercontractivity  (in particular, its meaning in the RL setting) in the final version of the work.\n\nThe work makes a non-trivial technical contribution, but most importantly, it presents a key new result: while Weisz et al ’20 also give MDPs that are hard to learn in the online setting considered here, the construction there is more contrived / pathological (this is by necessity). By making the setting more realistic (i.e., online), learning becomes harder and the authors leverage a less pathological construction to still get ~ e^d complexity, further supporting the idea that such hardness is more ``   `realistic'. \n\n I support the work for publication to NeurIPS 2021.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ljs7aS9iE65", "reviewer": "Reviewer_vgYe", "summary": "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. ", "questions": "", "limitations": "", "rating": 8, "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 paper considers an interesting open question on the online RL with linear function approximation. Realizability and constant minimum gap are commonly used, and reasonable assumptions for this setting, but nevertheless, the paper shows that it is still a hard problem without further assumptions. This negative result is a good addition to the current literature. For the upper bound, a major contribution is to remove the linear dependency on the number of actions with a nice adaptation of G-optimal experimental design. Overall, the paper is very well-written and presents solid improvements/contributions to the RL theory, hence I recommend the acceptance. \n\n\n\n\nMain Comments\n\n- It seems that there is a caveat in this negative result: there is no limit on the action space and thus there could be exponentially many possible actions to choose. It would have been better clarified if the same negative result can be obtained when the number of actions are finite (like in many practical problems). \n\n- Could you explain what Assumption 4 (hypercontractivity) means in the RL world more explicitly? Unlike in robust-statistics where the hypercontractivity is crucial for the success of specific moment-based methods, for the proposed algorithm it is hard to see why it helps to overcome the impossibility result. Is Assumption 4 some sort of uniform ergodicity? or is it some variation of (nearly) deterministic systems? \n\n- How broadly Assumption 3 or 4 can be applied in practice? What are some practical examples whose transition kernels are not completely deterministic but still satisfying these assumptions?\n\n\nMinor Comments\n\n- Line 225 - 226: One style of assumption ... [Zanette et al., 2020] -> I don't understand how this work is relevant to your assumptions. \n\n- Section 5.1: It might be nicer to state and emphasize what is the major challenge / target to improve at the beginning of the section.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and remarks are well pointed out in the discussion section. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "hemBtggKzib", "reviewer": "Reviewer_ca1d", "summary": "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.\nIn 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.", "questions": "", "limitations": "", "rating": 8, "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": "Overall I think the contribution of the paper is significant and the presentation is quite clear. To the best of my knowledge most of the related works have been sufficiently addressed.\nHere are my suggestions for the paper:\n\n* In the paper, it would help (subject to space constraints) to (i) include a figure detailing a rough description of the lower bound in the paper and (ii) a discussion comparing the current construction to the previous lower bound of Weisz et al.\n\n* In section 4.1 it would help to add a line that the total number of states in the MDP is also equal to $m$.\n\n* In the presentation, I sometimes got confused with notations such as $\\bar{a}_1$, $\\bar{a}_2$, etc. which are in fact used to refer to states and not actions. This is a bit jarring at times. I think in general it may help to only index the states by $\\bar{i}$ and $\\bar{j}$ and avoid using the notation $a_\\cdot$ entirely here.\n\n* In Theorem 2, it might helpful for a reader to see a more explicit description of the number of trajectories consumed by the algorithm instead of $\\text{poly} (1/\\epsilon)$.\n\n* In the case the action space constrained to be $\\text{poly}(d)$, is there any conjectured approach for a lower bound?\nA natural approach is to split each state in the current (exponential action space) MDP into an exponential number of states with a constant number of actions each, and inducing the uniform distribution over these states upon taking any action in the previous state. However, this approach fails because even the value of the optimal policy becomes exponentially small. But of course, there is a lot more room to work around here. So, I wonder: do you believe the flexibility of the next-state distribution here is sufficient to get such a lower bound instance to work when the action space is only polynomially large?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have addressed the limitations / future work and also potential negative impacts of their work sufficiently.", "review_text": "", "extra_scores": {"ethical_concerns": "None to the best of my knowledge.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "3jpW60Ig6c", "reviewer": "Reviewer_PcYF", "summary": "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.\nThe 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.\n\nThe 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.\nThe 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). \n\n(1) is important to make the separation between the lower and upper bounds clear as the lower bound uses exponentially many actions.\nAs 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.", "questions": "", "limitations": "", "rating": 8, "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": "LOWER BOUND:\n\nThe construction for the bound seems to be largely inspired by Weisz et al. 2020’s construction: the crucial difference to achieve the suboptimality gap is to construct a \"leaky” graph instead of downscaling the features. This way, the downscaling is essentially achieved by the transitions. The two techniques allow for a similar information theoretic argument to finish the bound. The result is both stronger and weaker: the suboptimality gap is a stronger assumption, but the lower bound only works in the online RL setting (as opposed to the generative model).\nI was happy to see a hard MDP construction similar to Weisz et al 2020’s presented (in my opinion) much more cleanly.\n\n- I am missing the definition of Pr_M at appendix line 61.\n- I am unsure why the appendix \"addressing footnote 3\" is necessary: could we not just bijectively remap the m-1 actions of each state to [m-1]?\n\nUPPER BOUND:\n\nI would like to see some assumptions clarified here, as there might be inaccuracies. Below is my best attempt at understanding them. Whether I am right or wrong here, the effort required to address my issues in the paper should be fairly small.\n- First, in line 147, I believe the precise assumption on theta* and phi's 2-norms is that they are <=1 (instead of O(1); see eg appendix line 189). I would like to see this stated as a separate assumption. The trouble with the argument that this \"can always be achieved via rescaling\" is that one would have to rescale the rewards, and consequently epsilon too, to achieve the same guarantee. This means that the final bound will scale polynomially with these 2-norms, instead of (what might be possible) logarithmically. I believe for this reason the assumption should be made explicit, as it is in Du et al 2019b. It would be nice for this assumption to be referenced in the proof too, (eg appendix lines 103, 189, lemma 7, etc.).\n- Second, in lemma 7, Du et al 2019b’s relevant lemma is A.3 instead of A.2, (at least in the versions available to me), and it is stated slightly differently. I would like to see these differences proved or explained. These are:\n  - a condition on eta<=1\n  - |\\xi|<=1 (I'm not sure what n refers to in appendix line 149)\n  - eta^2 in the bound instead of eta\n- Third, Du et al 2019b uses an additional assumption, that rewards are nonnegative and the sum of rewards on *any* trajectory is bounded by 1. I believe this assumption is missing from this paper, but seems to be implicitly used at places like (other than possibly at lemma 7): appendix line 98 (for the value bound), and line 107 (to bound \\xi almost surely; here this bound would be <=1, not sure where the 2 comes from). Both of these arguments feel somewhat unfinished to me.\n\nFor the low variance and hypercontractivity assumptions introduced at the beginning of section 5, it would be nice to see examples or descriptions of the kinds of MDPs whose value functions satisfy this assumption. The current description focuses on the value functions, not on the MDPs that might induce such value functions. Having this could help interpreting the generality of these assumptions (and hence the corresponding upper bound too).\n\nDoes the upper bound work under a near-realizability assumption (eg. ||Q*-phi^T theta*||_\\infty <= something *very* small)?\n\n- Line 315: is known -> was known\n- Line 7: such a lower bound (add bound)\n- Appendix line 119: consider better justifying line 3 to line 4, bound of theta-theta* by including the calculation", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all liked the paper very much. It will be a very nice addition to the conference program, presenting interesting and important additions to the growing body of literature on the theoretical analysis of RL algorithms with function approximation under the assumption that the action-value function of the optimal policy ($Q^*$) is linearly realizable.
Decision: Accept (Oral)