Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
Authors: Simon S. Du
Sham M. Kakade
Ruosong Wang
Lin F. Yang
Venue:  (2020)
Keywords: reinforcement learning
function approximation
lower bound
representation

Abstract: Modern deep learning methods provide effective means to learn good representations. However, is a good representation itself sufficient for sample efficient reinforcement learning? This question has largely been studied only with respect to (worst-case) approximation error, in the more classical approximate dynamic programming literature. With regards to the statistical viewpoint, this question is largely unexplored, and the extant body of literature mainly focuses on conditions which \emph{permit} sample efficient reinforcement learning with little understanding of what are \emph{necessary} conditions for efficient reinforcement learning.
This work shows that, from the statistical viewpoint, the situation is far subtler than suggested by the more traditional approximation viewpoint, where the requirements on the representation that suffice for sample efficient RL are even more stringent. Our main results provide sharp thresholds for reinforcement learning methods, showing that there are hard limitations on what constitutes good function approximation (in terms of the dimensionality of the representation), where we focus on natural representational conditions relevant to value-based, model-based, and policy-based learning. These lower bounds highlight that having a good (value-based, model-based, or policy-based) representation in and of itself is insufficient for efficient reinforcement learning, unless the quality of this approximation passes certain hard thresholds. Furthermore, our lower bounds also imply exponential separations on the sample complexity between 1) value-based learning with perfect representation and value-based learning with a good-but-not-perfect representation, 2) value-based learning and policy-based learning, 3) policy-based learning and supervised learning and 4) reinforcement learning and imitation learning.   

Published as a conference paper at ICLR 2020
IS A GOOD REPRESENTATION SUFFICIENT FOR SAM- PLE EFFICIENT REINFORCEMENT LEARNING?
Simon S. Du Institute for Advanced Study ssdu as edu
Sham M. Kakade
University of Washington, Seattle
shamecs wash inghoonnoon.... edu
Ruosong Wang
Lin F. Yang
Camegie Mellon University ruosongwe andrew. cmu. edu
University of California, Los Angles 1 Linyang@ee www..elllee...o edu
ABSTRACT
Modern deep learning methods provide effective means to learn good represen- tations. However, is a good representation itself sufficient for sample efficient reinforcement learning? This question has largely been studied only with respect to (worst-case) approximation error, in the more classical approximate dynamic programming literature. With regards to the statistical viewpoint, this question is largely unexplored, and the extant body of literature mainly focuses on conditions which permit sample efficient reinforcement learning with little understanding of what are necessary conditions for efficient reinforcement learning.
This work shows that, from the statistical viewpoint, the situation is far subtler than suggested by the more traditional approximation viewpoint, where the re- quirements on the representation that suffice for sample efficient RL are even more stringent. Our main results provide sharp thresholds for reinforcement learning methods, showing that there are hard limitations on what constitutes good function approximation (in terms of the dimensionality of the representation), where we focus on natural representational conditions relevant to value-based, model-based, and policy- based learning. These lower bounds highlight that having a good (value- based, model-based, or policy-based) representation in and of itself is insufficient for efficient reinforcement learning, unless the quality of this approximation passes certain hard thresholds. Furthermore, our lower bounds also imply exponential separations on the sample complexity between 1) value-based learning with perfect representation and value-based learning with a good-butt-ot--erfees representation. 2) value-based learning and policy-based learning, 3) policy-based learning and supervised learning and 4) reinforcement learning and imitation learning.
INTRODUCTION
Modern reinforcement learning (RL) problems are often challenging due to the huge state space. To tackle this challenge, function approximation schemes often employed provide a compact representation, so that reinforcement learning can generalize across states. A common paradigm to first use a feature extractor transform the raw input to features (a succinct representation) and then apply linear predictor on top of the features. Traditionally, the feature extractor is often handcrafted (Sutton & Barto] 2018), while more modern methods often train a deep neural network to extract features. The hope of this paradigm is that, if there exists good low dimensional (linear) representation, then efficient reinforcement learning is possible.
Empirically, combining various RL function approximation algorithms with neural networks for feature extraction has lead to tremendous successes on various tasks (Mnih et al. 2015) Schulman et al. 2015 2017). A major problem, however, is that these methods often require large amount of samples to learn a good policy. For example, deep Q Q-network requires millions of samples to solve certain Atari games (Mnih et al. 2015). Here, one may wonder if there are fundamental statistical

---

Published as a conference paper at ICLR 2020
limitations such methods, and, if so, under what conditions it would be possible to efficiently learn a good policy?
In the supervised learning context, is well-known that empirical risk minimization is statistically efficient method when using a low-complexity hypothesis space (Shalev-Shwart, & Ben-David 2014), e.g. hypothesis space with bounded VC dimension. For example, polynomial number of samples suffice for learning a near-optimal d-dimensional linear classifier, even in the agnostic setting In contrast, in the more challenging RL setting, we seek understand if efficient learning is possible (say from a sample complexity perspective) when we have access to an accurate (and compact) parametric representation e.g. our policy class contains a near-optimal policy or our hypothesis class accurately approximates the optimal value function. In particular, this work focuses on the following question:
Is a good representation sufficient for sample-efficient reinforcement learning?
This question has largely been studied only with respect to approximation error in the more classical approximate dynamic programming literature, where it is known that algorithms stable to certain worst-case approximation errors. With regards to sample efficiency, this question is largely unexplored, where the extant body of literature mainly focuses on conditions which are sufficient for efficient reinforcement learning though there is little understanding of what are necessary conditions for efficient reinforcement learning. In reinforcement learning, there is no direct analogue of empirical risk minimization as in the supervised learning context, and it is not evident what are the statistical limits of learning based on properties of our underlying hypothesis class (which may be value- based, policy-based, or model-based)
Many recent works have provided polynomial upper bounds under various sufficient conditions, and in what follows we list few examples. For value-based learning, the work of Wen & Van (2013) showed that for deterministic system if the optimal Q-function can perfectly predicted by linear functions of the given features, then the agent can learn the optimal policy exactly with polynomial
number of samples. Recent work (Jiang et al. 2017) further showed that if certain complexity measure called Bellman rank is bounded, then the agent can learn near-optimal policy efficiently. For policy- based learning, Agaawwll et al. (2019) gave polynomial upper bounds which depend on a parameter that measures the difference between the initial distribution and the distribution induced by the optimal policy.
This paper gives, perhaps surprisingly, strong negative results this question. The main results are exponential lower bounds in terms of planning horizon H for value-based, model- based, and policy-based algorithms with given good representations" Notably, the requirements on the representation that suffice for sample efficient RL are even more stringent than the more traditional approximation viewpoint. A comprehensive summary of previous upper bounds and our lower bounds is given in Table and here we briefly summarize our hardness results.
Our Contributions.
1. For value-based learning, we show even if Q-functions of all policies can be approximated by linear functions of the given representation with approximation error d = Ω (V where is the dimension of the representation and H is the planning horizon, then the agent still needs to sample exponential number of trajectories find a near-optimal policy.
2. For model-based learning, we show even if the transition matrix and the reward function be approximated by linear functions of the given representation with approximation
error 8 = Ω (v (in Eoo sense), the agent still needs sample exponential number of trajectories to find a near-optimal policy.
3. We show even if optimal policy can be perfectly predicted by a linear function of the given representation with a strictly positive margin, the agent still requires exponential number of trajectories to find a near-optimal policy.
Herre we only study the sample complexity and ignore the computational complexity.
2 "MDPs where both reward and transition are deterministie.
"Our results can be easily extend to infinite horizon MDPs with discount factors by replacing the planning where ry is the discount factor. We omit the discussion on discount MDPs for simplicity.
horizon H with
2

---

Published as a conference paper at ICLR 2020
These lower bounds hold even in deterministic systems and even if the agent knows the transition model. Note these negative results apply to the case where the Q-function, the model, or the optimal policy can be predicted well by linear function of the given representation. Since the class of linear functions is a strict subset of many more complicated function classes, including neural networks in particular, negative results imply lower bounds for these more complex function classes well. Our results highlight the following conceptual insights:
The requirements on the representation that suffice for sample efficient RL are significantly more stringent than the more traditional approximation viewpoint; our statistical lower bounds show that there are hard thresholds on the worst-case approximation quality of the representation which are not necessary from the approximation viewpoint.
Since our lower bounds apply even when the agent knows the transition model, the hardness is not due to the difficulty of exploration in the standard sense. The unknown reward function is sufficient to make the problem exponentially difficult.
Our lower bounds are not due to the agent's 's inability perform efficient supervised learning, since our assumptions do admit polynomial sample complexity upper bounds if the data distribution fixed.
Our lower bounds are not pathological in nature and suggest that these concerns may arise in practice. In precise sense, almost all feature extractors induce a hard MDP instance in our construction (see Section 4.4).
Instead, one interpretation is that the hardness is due to a distribution mismatch in the following sense: the agent does not know which distribution to use for minimizing (supervised) learning error (see Kakade 2003) for discussion), and even known transition model is not infornatiio--thoorriicalll sufficient to reduce the sample complexity.
Furthermore, our work implies several interesting exponential separations on the sample complexity between: 1) value-based learning with perfect representation and value-based learning with a good- but-not-perfect representation, 2) value-based learning and policy-based learning. 3) policy-based learning and supervised learning and 4) reinforcement learning and imitation learning. We provide more details in Section 5
2 RELATED WORK
A summary of previous upper bounds, together with lower bounds proved in this paper, is provided in [ Some key assumptions are formally stated in Section Jn and Section Our lower bounds highlight that classical complexity measures in supervised learning including small approximation error and margin, and standard assumptions in reinforcement learning including optimality gap and deterministic systems, are not enough for efficient RL with function approximation. We need additional assumptions, c.g., ones used previous upper bounds, for efficient RL.
2.1 PREVIOUS LOWER BOUNDS
Existing exponential lower bounds, ponentially large state space and reduce a bandit problem with exponentially many arms to an MDP (Krishnamurthy et al.) 2016 Sun et al. (017). However, these lower bounds cannot apply to MDPs whose transition models, value functions, or policies can be approximated with some natural function classes, e.g., linear functions, neural networks, etc. The current paper gives the first set of lower bounds for RL with linear function approximation (and thus also hold for super classes of linear functions such as neural networks).
knowledge, construct unstructured MDPs with
2.2 PREVIOUS UPPER BOUNDS
We divide previous algorithms (with provable guarantees) into three classes: those that utilize uncertainty-basse based bonuses (e.g. UCB variants or Thompson sampling variants); approximate dynamic programming variants (which often make assumptions with respect concentrability coefficients); and direct policy search-based methods (such as conserve policy iteration (CPI, see Kakade (2003) or policy gradient methods, which make assumptions with respect distribution mismatch coefficients).
3

---

Published as a conference paper at ICLR 2020
Query Oracle
RL
Generative Model
Known Transition
Previous Upper Bounds
Exact linear Q" DetMDP Wen & Van Roy
2013
Exact linear Q + Bellman- Rank Jiang et al.
2017]
Exact Linear Q" Low Var + Gap (Du et al.
2019a
Exact Linear Q' Gap (Open Problem / Theorem
C.I
Fxact Linear Q for all (Open Problem Theorem
D.1
Approx. Linear Q" for all æ Concentratability (Munos, 2005 Antos et al. 2008
x
Approx. Linear (2" for all æ
x
Bounded Dist Mismatch Coefl' (Kakade & Langford 2002
Lower Bounds (this work)
Approx Linear Q"" (Theorem 4.1
Approx Linear Q all (Theorem 4.1
foo Approx Linear MDP (Theorem 4.2
Exact Linear T² Margin Gap + DetMDP (Theorem 4.3
x
X
Exact Linear Q" (Open Problem)
Table 1: Summary of theoretical results reinforcement learning with linear function approximation.
See Section 2 for discussion on this table. RL. Generative Model, Known Transition are defined
in Section 3.3 Exact linear Q*: Assumption 4. with ò 0. Approx linear Q": Assumption 4.]
with 8 Ω H
Exact linear - Assumption 4.4 Margin: Assumption 4.5 Exact Linear Q"
for all m: Assumption 4.2 with 8 = 0. Approximate Linear Q" for all Assumption 4.2 with
5 ==0 Ω (v
DetMDP: deterministic system defined in Section 3.1 Bellman-rank: Definition 5 in
Jiang et al. (0177). Low Var: Assumption in Du et al. (2019b). Gap: Assumption 3.1 Bounded Distribution Mismatch Coefficient: Definition 3.3 in
Agarwal al. (2019). foc Approx Linear
MDP: Assumption 4.3 with 52 (v / V: there exists algorithm with polynomial sample
complexity to find a near-optimal policy. X: requires certain condition on the initial distribution. x: exponential number of samples required. ?: open problem.
4

---

Published as a conference paper at ICLR 2020
The first class of methods include those based witness rank. Belman rank, and the Eluder dimension, while the latter two classes of algorithms make assumptions either on concentrability coefficients or on distribution mismatch coefficients (see Agarwal et al. 2019);; Scherrer (2014) for discussions).
Uncertainty bonus-based algorithms. Now we discuss existing theoretical results on value- based learning with function approximation. The most relevant work is Wen & Van Roy (2013) which showed in deterministic systems, if the optimal Q-function is within a pre-specified function class which has bounded Eluder dimension, for which the class of linear functions is special case, then the agent can learn the optimal policy using polynomial number of samples. This result has recently been generalized by Du et al. (2019a) which can deal with stochastic reward and low variance transition but requires strictly positive optimality gap. As we listed in Table I it is an open problem whether the condition that the optimal Q-function linear itself is sufficient for efficient RI..
Li et al. (2011) proposed Q-learning algorithm which requires the Know- Woow-What-le Knows oracle. However, it is in general unknown how to implement such oracle practice. [Ting al. (2017) proposed the concept of Bellman Rank to characterize the sample complexity of value-based learning methods and gave an algorithm that has polynomial sample complexity in terms of the Bellman Rank, though the proposed algorithm is not computationally efficient. Bellman rank is bounded for wide range of problems, including MDP with small number of hidden states, linear MDP, LQR, etc. Later work gave computationally efficient algorithms for certain special cases (Dann et al. 2018 Du et al., 2019a Yang & Wang 2019b; Jin et al.) 2019). Recently, Witness rank, a generalization of Bellman rank to model-based methods, is studied in (un al. (2019).
Approximate dynamic programming--aased algorithms. We now discuss approximate dynamic programming- results characterized in terms of the concentrability coefficient. While classical approximate dynamic programming results typically require -bounded errors, the notion of concentrability (originally due to (Munos) 2005)) permits sharper bounds in terms of average-case function approximation error, provided that the concentrability coefficient is bounded (e.g. see Munos (2005): /Szepesáári & Munos (005); Antos al.) (2008); Geist et al. (2019)). Under the assumption that this (2005) and Antos et al. (2008) proved sample complexity and error bounds for approximate dynamic programming methods when there is data collection policy (under which value-function fitting occurs) that induces a finite concentrability coefficient. The assumption that the concentrability coefficient is finite is in fact quite limiting. See Chen & Jiang 2019) which provides more detailed discussion on this quantity.
parameter is bounded, Munos| (2005); Szepesvári & Munos)
Direct policy search-based algorithms. Stronger guarantees over approximate dynamic programming-basse algrithm can be obtained with direct policy search-based methods, where instead of having a bounded concentrability coefficient, one only needs to have a bounded distribution mismatch coefficient. The latter assumption requires the agent to have access to a "good" initial state distribution (e.g. a measure which has coverage over where an optimal policy tends to visit); note that this assumption does not make restrictions over the class of MDPs. There are two classes of algo- rithms that fall into this category. First, there is Conservative Policy Iteration (Kakade & Langford 2002), along with Policy Search by Dynamic Programming (PSDP) (Bagnell et al. 2004), and other noosting-style of policy cearch-based methods [Scherrer& & Geist (2014); |Scherrer (2014), which have guarantees in terms of bounded distribution mismatch ratio. Second, more recently, Agarwal et al. (2019) showed that policy gradient styles of algorithms also have comparable guarantees.
Recent extensions. Subsequent to this work, the work by Van Roy & Dong (2019) Lattimore & Szepesvari (2019) made notable contributions to the misspecified linear bandit problem. In particular, both papers found that Theorem 4.1 in our paper can be extended to the misspecified linear bandit problem and gave upper bounds for this problem showing that our lower bound has tight dependency on 8 and d. Lattimore & Szepesvari (2019) further gave upper bound for the setting where the Q-functions of all policies can be approximated by linear functions with small approximation errors and the agent can interact with the environment using generative model. This upper bound also demonstrates that our lower bound has tight dependency on and d.
PRELIMINARIES
Throughout this paper, for given integer H, we use [A] to denote the set (0, 1, 1,..., H 1).
5

---

Published as a conference paper at ICLR 2020
3.1 EPISODIC REINFORCEMEN LEARNING
Let M = (S,A, R) be an Markov Decision Process (MDP) where is the state space, A is the action space whose size bounded by constant, H Z+ is the planning horizon, A A (S) is the transition function which takes a state-action pair and returns distribution over states and S x A - A (R) the reward distribution. Without loss of generality, we assume fixed initial state s A policy : S + (AA) prescribes distribution over actions for each state. The policy x induces a (random) trajectory so, do To, $1, Q1, Pi...... -H-1: - TH-1 where ao (50),, ro Rs ao).
P(so; ao), d1 ~ (51), etc. To streamline our analysis, for each [H], we use S S S to denote the set of states at level h, and we assume Sy, do not intersect with each other. We also assume === Fh E
[0.1] almost surely. Our goal is to find policy x that We use π to denote the optimal policy. We
maximizes the expected total reward
E3
Σ h= Th
say policy is s-optimal if E
hh=0
2 E
H- 2n= Th TT -E.
In this paper we prove lower bounds for deterministic systems, i.e., MDPs with deterministic transition P. deterministic reward R. In this setting. P and R can be regarded as functions instead of distributions. Since deterministic systems are special cases of general stochastic MDPs, lower bounds proved in this paper still hold for more general MDPs.
3.2 Q-FUNCTION AND OPTIMALITY GAP
An important concept in RL is the Q-function. Given a policy π, level h E [H] and state-action pair (s,a) E S₁, x A, the Q-function is defined (8, E Σ H Th |8 8, 04 a,
For simplicity, we denote (7, a) Q7 (s.a). addition these definitions, we list below an important assumption, the optimality gap assumption, which is widely used in reinforcement learning and bandit literature. To state the assumption, we first define the function gap S x gap(s, a) arg max,'eA (" a') Q* a). Now we formally state the assumption.
as Assumption 3.1 (Optimality Gap). There exists 0 such that p S gap(s, for all (s.a) ESXA with gap(s, a) >
Here, p is the smallest reward-to-go difference between the best of actions and the rest. Recently, Q Q-learning algorithm based on this assumption and
Du et al. (219b) gave a provably efficient Simchowitz & Jamieson (2019) showed that with this condition, the agent only incurs logarithmic regret in the tabular setting.
3.3
QUERY MODELS
Here we discuss three possible query oracles interacting with the MDP.
RL: The most basic and weakest query oracle for MDP is the standard reinforcement learning query oracle where the agent can only interact with the MDP by choosing actions and observe the next state and the reward.
Generative Model: A stronger query model assumes the agent can transit to any state (Kearns & Singh 2002 Kakade 22033; Sidford et al.) 2018). This query model is available in certain robotic applications where state.
control the robot to reach the target
Known Transition: The strongest query model considered that the agent can not only transit any state, but also knows the whole transition function. In this model, only the reward is unknown.
In this paper, we will prove lower bounds for the strongest Known Transition query oracle. Therefore, lower bounds also apply to RL and Generative Model query oracles.
"Some papers assume the initial state is sampled from a distribution Pt. Note this is equivalent to assuming a fixed initial state 8o, by setting P(5o, a) P. for all a E A and now our state is equivalent to the initial state in their assumption.

---

Published as a conference paper at ICLR 2020
4 MAIN RESULTS
In this section we formally present our lower bounds. We also discuss proof ideas in Section
4.4
4.1 LOWER BOUND FOR VALUB-BASHE LEARNING
We first present our lower bound for value-based learning. A common assumption is that the Q- function can be predicted well by a linear function of the given features (representation) (Bertsekas) & Tssitsikiis 1996). Formally, the agent is given feature extractor Φ S x A -> IR which can be hand-crafted or a pre-trained neural network that transforms a state-action pair to a d-dimensional embedding. The following assumption states that the given feature extractor can be used to predict the Q-function with approximation error at most using a linear function.
Assumption 4.1. There exists 8 > 0 and 8o .,....,0 E R such that for any h E [H] and any (s, a) E Sn x A, 12% (x, (On, (s.a)), <
Here is the approximation error, which indicates the quality of the representation. If = 0, then Q-function can be perfectly predicted by linear function of 6 (---). In general, 5 becomes smaller as we increase the dimension of Φ, since larger dimension usually has more expressive power. When the feature extractor is strong enough, previous papers (Chen & Jiang 2019 Farahmand 2011) assume that linear functions of & can approximate the Q-function of any policy.
Assumption 4.2 (Policy Completeness). There exists 5 >> O, such that for any h E [M] and any policy π, there exists 0% E Rd such that for any (s, a) E S₁, x A. Q (s, a) - (0), ø (s,a)) s 6.
In the theoretical reinforcement learning literature, Assumption 4.2 is often called the (approximate) policy completeness assumption. This assumption is crucial in proving polynomial sample complexity
guarantee for value iteration type of algorithms (Chen & Jiang 2019 Farahmand 2011).
The following theorem shows when d = S (v H trajectories to find opar-optimal policy.
/) the agent needs to sample exponential number of
Theorem 4.1 (Exponential Lower Bound for Value-based Learning). There exists a family of MDPs
with AA| = 2 and feature extractor 6 that satisfy Assumption (.2 such that any algorithm that
returns 1/2-optimal policy with probability 0.9 needs to sample S2 [ 2 exp(dō" /16))) trajectories.
Note this lower bound also applies to MDPs that satisfy Assumption 4.1 since Assumption 4.2 strietly stronger. We would like to emphasize that since linear functions subclass of more complicated function classes, e.g., neural networks, our lower bound also holds for these function classes. Moreover, in many scenarios, the feature extractor é is the last layer of a neural network. Modern neural networks are often wver-parameterized, which makes d large. In this case, d is much larger than H. Thus, our lower bound holds even if the representation has small approximation error. Furthermore, the assumption that |A| = 2 is only for simplicity. Our lower bound can be casily generalized to the case that [A]] > 2, in which case the sample complexity lower bound is Q (min([S), |A|l cxp(ddd /16)]))
4.2 LOWER BOUND FOR MODEL-BASED LEARNING
Here we present our lower bound for model-based learning. Recently, Yang & Wang (019b) proposed the linear transition assumption which was later studied in Yang Wang a Jin et al. (2019). Again, we assume the agent is given a feature extractor Φ P the assumption formally as follow.
HR and now we state
E IRd and vi : S + IRd such that for any h [H 11. (s,a) a) S x A and s E Sh+1.
Assumption 4.3 (Approximate Linear MDP). There exists >
0, 3o
IP s, a, (1b(5)) & (s, a)}l < 8 and [E[R(s (s, a)] - (3,, Ø(s a))
5.
It has been shown in Yang& & Wang 20019b Jin et al. (2019) if P s, (v(-), l)) is bounded, then the problem admits an algorithm with polynomial sample complexity. Now we show that when Ω / HH near-optimal policy. /
in Assumption 4.3 4.3 the agent needs exponential number of samples to find
7

---

Published as a conference paper at ICLR 2020
Theorem 4.2 (Exponential Lower Bound for Linear Transition Model). There exists a famity of MDPs with [A| = and a feature extractor & that satisfy Assumption 4.3 such that any algorithm that returns a 1 /2-optimal policy with probability 0.9 needs to sample & min (iin 2 exp(dd2/110) trajectories.
Again, our lower bound can be easily generalized to the case that |A| > 2.
We do note that an foe approximation for a transition matrix may be weak condition. Under the stronger condition that the transition matrix can be approximated well under the total variational distance, there exists polynomial sample complexity upper bounds that can tolerate approximation errors (Yng Wang 2019b a Jin et al. 2019).
4.3 LOWER BOUND FOR POLICY-BASED LEARNING
Next we present lower bound for policy- based learning. This class of methods use function approximation on the policy and use optimization techniques, e.g., policy gradient, to find the optimal policy. In this paper, we focus on linear policies on top of given representation. A linear policy т is policy of the form π ((8)) = arg maxae. (On, 6(88, a)) where 84 E Sh. Φ (-s-) is a given feature extractor and 0g Rd is the linear coefficient. Note that applying policy gradient on softmax parameterization of the policy is indeed trying to find the optimal policy among linear policies.
Similar to value-based learning, a natural assumption for policy-based learning is that the optimal policy is realizable i.e., the optimal policy is linear. Assumption 4.4. For any h E [H], there exists On IR that satisfies for any E Shy we have xt" (s) arg max, (fn, @ (s,a)).
Here we discuss another assumption. For learning a linear classifier in the supervised learning setting, one can reduce the sample complexity significantly if the optimal linear classifier has margin. Assumption 4.5. We assume é (s, a) E Edd satisfies (lo a)ll, 1 for any (s, S A. For any and A > such that for any Sh, there is a unique
E [H) there exists 0g E RRd with | 11 optimal action n² (s), and for any + ' (s), (6,, o (s, x² (s)) (0,, Φ (s, a)) 2 A.
Here we restrict the linear coefficients and features to have unit norm for normalization. Note that Assumption 4.5 is strictly stronger than Assumption 4.4 Now we present our result for linear policy.
Theorem 4.3 (Exponential Lower Bound for Policy-based Learning). There exists an absolute constant Do. such that for any A < Do. there exists a family of MDPs with |A| = 2 and feature extractor & that satisfy Assumption 3.1 with p = mi. and Assumption 4.5 such that any algorithm that returns a 1/4-optimal policy with probability at least 0.9 needs to sample Ω (min(2" 2d3) trajectories.
Again, our lower bound can be easily generalized to the case that [A| > 2.
Compared with Theorem 4. Theorem is even more pessimistic, in the sense that even with perfect representation with benign properties (gap and margin), the agent still needs to sample exponential number of samples. It also suggests that policy- learning could be very different from supervised learning.
4.4 PROOF IDEAS
The binary tree hard instance. All our lower bound are proved based on reductions from the following hard instance. In this instance, both the transition P and the reward R are deterministic. There are H levels of states, which form full binary tree of depth H. There are 2 states in level and thus 2 1 states in total. Among all the 2 2 states in level H 1. there is only one state with reward R 1, and for all other states in the MDP, the corresponding reward value
0. Intuitively, to find 1 1/2-optimal policy for such MDPs, the agent must enumerate all possible states in level I to find the state with reward R = 1. Doing so intrinsically induces a sample complexity of (2 This intuition is formalized in Theorem A. using Yao's minimax principle (Yao 1977).
Unlike value-based learning, it is hard to define completeness on the policy-based learning with function approximation, since all policy has the arg max form.
8

---

Published as a conference paper at ICLR 2020
Lower bound for value-based and model-based learning We now show how to construct set of features so that Assumption 4.3 hold. Our main idea is to the utilize the following fact regarding the identity matrix: e-rank[ 12 I O(H/=²). Here for a matrix A R= its g-rank (a.k.a approximate rank) is defined to be min frinfran(B)) (B) B E R ||A Bl1 3 {), where we use 11 to denote the entry-wise foc norm of matrix. The upper bound e-rank(
O(log n n/ Lemma (Johnson & Lindenstrauss 1984), and we also provide a proof Lemma A.1 The concept of s-rank has wide applications in theoretical computer science (Alon 2009 Barak et al. 2011 Alon et al. 2013: 2014 Chen & Wang 2019). but to our knowledge, this is the first time that appears in reinforcement learning.
was first proved in Alon (2009) using the
This fact can be alternatively stated as follow: there exists & E R²" xo(H==") such that ||42 @ 1o S.. We interpret each row of o as the feature of state in the binary tree. By construction of ④, now features of states in the binary tree have a nice property that (i) each feature vector has approximately unit norm and (ii) different feature vector are nearly orthogonal. Using this set of features, we can now show that Assumption [41 4.33 hold. Here we prove Assumption h. as an example and prove other assumptions also hold in the appendix. To prove Assumption 4.1 we note that in the binary tree hard instance, for each level h. only a single state satisfies Q" = 1. and all other states satisfy Q* O. We simply take 8% to be the feature of the state with Q* 1. Since all feature vectors are nearly orthogonal, Assumption 4.1 holds.
Since the above fact regarding the g-rank of the identity matrix can be proved by simply taking each row of Φ to be random unit vector, our lower bound reveals another intriguing (yet pessimistic) aspect of Assumption 4. 4.3 for the binary tree instance, almost all feature extractors induce a hard MDP instance. This again suggests that a good representation itself may not necessarily lead to efficient RL and additional assumptions (c.g. on the reward distribution) could be crucial.
Lower bound for policy-based learning. It straightfoward to construct a set of feature vectors for the binary tree instance so that Assumption 4.4 holds, even if = 1. We set o(s, a) to be +1 aj and -1 if 02. For each level h, for the unique state in level h with Q' - 1, we set On, to be if x (s) = a1 and -1 if T (s(ss = 0g. With this construction, Assumption 4.4 holds.
To prove that the lower bound under Assumption 4.5
use new reward function for states in level H - in the binary tree instance above so that there exists a unique optimal action for each state in the MDP. See Figure S for example with H = 3 levels of states. Another nice property of the new reward function is that for all states 8 we always have π (s) = a1- Now, we define change its original reward (defined in Figure 2 to 1. An exponential sample complexity lower bound for these MDPs can be proved using the same argument as the original binary tree hard instance, and now we show this set of MDPs satisfy Assumption 4.5 We first show in Lemma A.2 that there exists a set / C g with IW = (1/A))(()) so that for each E N, there exists a hyperplane L that separates p and W (p). and all vectors in A have distance at least A to L. Equivalently, for each p E N, we can always define a linear function fp so that (p) Z A and fy(g) < - for all E N {p]. This can be proved using standard lower bounds on the size of s-nets. Now we simply use vectors in '' as features of states. By construction of the reward function, for each level h, there could only be two possible cases for the optimal policy n.. Le., either Nt (*(s) = aj for all states in level h, or ' rT( unique state 8 and x² (s') aj for all * s'. In both cases, we can easily define linear function with margin A to implement the optimal policy n², and thus Assumption holds. Notice that in this proof, we critically relies on d @(H), so that we can utilize the curse of dimensionality to construct a large set of vectors as features.
2 different new MDPs follow: for each state in level H -
0g for a
SEPARATIONS
good-but-not-perfess representation. For value-based learning in deterministic systems, Wen & Van Roy] (2013) showed polynomial sample complexity upper bound when the representation can perfectly predict the Q-function. In contrast, if the representation is only able to approximate the Q-function, then the agent requires exponential number of trajectories. This exponential separation demonstrates a provable exponential benefit of better representation.
Perfect representation
Value-based learning vs. bbsed learning. Note that if the optimal Q- Q-function can be perfectly predicted by the provided representation, then the optimal policy can also be perfectly

---

Published as a conference paper at ICLR 2020
predicted using the same representation. Since Wen & Van Roy (2013) showed polynomial sample complexity upper bound when the representation can perfectly predict the f-uuction, our lower bound on policy-based learning, which applies to perfect representations, thus demonstrates that the ability of predicting the Q-function is much stronger than that of predicting the optimal policy.
Supervised learning reinforcement learning. For policy- bbsie learning, if the planning horizon H = 1, the problem becomes learning linear classifier, for which there are polynomial sample complexity upper bounds. For policy-based learning, the agent needs to learn // linear classifiers sequentially. Our lower bound on policy-based learning shows the sample complexity dependency on H is exponential.
Imitation learning vs. reinforcement learning. In imitation learning (IL), the agent can observe trajectories induced by the optimal policy (expert). If the optimal policy is linear in the given representation, it can be shown that the simple behavior cloning algorithm only requires polynomial number of samples to find a near-optimal policy (Ross et al.) 2011). Our Theorem (.33) shows if the agent cannot observe expert's behavior, then it requires exponential number of samples. Therefore, our lower bound shows there an exponential separation between policy-bused RL and IL when function approximation is used.
ACKNOWLEDGMENTS
The authors would like to thank Yuping Luo, Wenlong Mou, Martin Wainwright, Mengdi Wang and Yifan Wu for insightful discussions. Also, the authors would also like gratefully acknowledge Benjamin Van Roy, Shi Dong, Tor Lattimore and Csaba Szepesvári for sharing a draft of their work and their comments. Simon S. Du is supported by NSF grant DMS- 1638--638352 and the Infosys Membership. Sham M. Kakade acknowledges funding from the Washington Research Foundation Fund for Innovation in Data-Intensive Discovery; the NSF award CCF 1740551; and the ONR award N00014-1 8-1-2247. Ruosong Wang is supported in part by NSF IIS 16356226, AFRI CogDeCON FA875018C0014, and DARPA SAGAMORE HR001 1990016. Part of this work was done while Simon S. Du was visiting Google Brain Princeton and Ruosong Wang was visiting Princeton University.
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. arXiv preprint 2019.
Noga Alon. Perturbed identity matrices have high rank: Proof and applications. Combinatorics, Probability and Computing, 18(1-2):3-15, 2009.
Noga Alon, Troy Lee, Adi Shraibman, and Santosh Vempala. The approximate rank of a matrix and its algorithmic applications: approximate rank. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 7755664, ACM, 2013.
Noga Alon, Troy Lee, and Adi Shraibman. The cover number of matrix and its algorithmic applications. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Technigues, pp. 34, 2014.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129, 2008
Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114, 2008
J. A. Bagnell, Sham M Kakade, Jeff G. Schneider, and Andrew Y. Ng. Policy search by dynamic programming. In S. Thrun, L. K. Saul, and B. Schölkopf (eds.), Advances in Neural Information Processing Systems 16, pp. 831-838. MIT Press, 2004.
10

---

Published as a conference paper at ICLR 2020
Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the forty-third annual ACM symposium Theory of computing, pp. 519-528. ACM, 2011.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming, volume Athena Scientific Belmont, MA, 1996.
Jinglin Chen and Nan Jiang. Information-theoreee considerations in batch reinforcement learning. arXiv preprint arXiv: 003600 2019.
Lijie Chen and Ruosong Wang. Classical algorithms from quantum and arthur-merlin communication protocols. 10th Innovations in Theoretical Computer Science, 2019.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert Schapire. On polynomial time PAC reinforcement learning with rich observations. arXiv preprint arXiv:1803.00666, 2018.
Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1):60-65, 2003.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudík, and John Lang- ford. Provably efficient RL with rich observations via latent state decoding. arXiv preprint arXiv:1901.09018. 2019a.
Simon S Du, Yuping Luo. Ruosong Wang, and Hanrui Zhang, Provably efficient Q-leaming with func- tion approximation via distribution shift error checking oracle. arXiv preprint arXiv:1906.06:: 06322,,, 2019b.
Amir-massoud Farahmand. Regularization in reinforcement learning. 2011.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. arXiv preprint arXiv:1901.11275. 2019.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are PAC-learnable. In Proceedings of the 34th International Conference Machine Learning-Voos Volume 70, pp. 1704-1713. JMLR. org, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. arXiv preprint arXiv:1907.05388 2019.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space.
Contemporary mathematics, (6(189-206):1. 1984.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML., volume pp. 267-274, 2002.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of College London, 2003.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learnng in polynomial time. Mach. Learn., 4922-2):209-232, November 2002. ISSN 0885-6125, doi: 10.1023/A:1011994441388 URL
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich
observations. In Advances in Neural Information Processing Systems, pp. 1840-1848, 2016.
Tor Lattimore and Csaba Szepesvari. Learning with good feature representations in bandits and in rl with a generative model. arXiv preprint arXiv:1911.070 2019.
Lihong Li, Michael I. Littman, Thomas J Walsh, and Alexander I. Strehl. Knows what it knows: framework for self-aware learning. Machine learning, 82(3):399 443, 2011.
GG Lorentz. Metric entropy and approximation. Bulletin of the American Mathematical Society, 72 (6):903-937, 1966.
11

---

Published as a conference paper at ICLR 2020
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 5 518(7540):529, 2015.
the Rémi Munos. Error bounds for approximate value iteration. In Proceedings the National Conference on Artificial Intelligence, volume 20, pp. 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 627-635, 2011.
Bruno Scherrer. Approximate policy iteration schemes: A comparison. Proceedings of the 31st International Conference International Conference on Machine Learning Volume 32, ICML' 14. JMLR. 2014.
Bruno Scherrer and Matthieu Geist. Local policy search convex space and conservative policy iteration as boosted policy search. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 35-50. Springer, 2014.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint urXiv:1707.063: 2017.
S. Shalev-Shwarts and S. Ben-David. Understanding Machine Learning: From Theory to Algo- rithms. Understanding Machine Learning: From Theory Algorithms. Cambridge University Press, 2014. ISBN 9781 1781100057135 URL https://books: google. cow.books ?id=
EtJKAWAAQBAJ
Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving discounted markov decision process with a generative model. arXiv preprint arXiv: 01492, 2018.
Max Simchowitz and Kevin Jamieson. Non-asymptotic gap-dependent regret bounds for tabular MDPs. 05 2019.
Wen Sun, Arun Venkatraman, Geoffrey Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In Proceedings of the 34th International Conference on Machine Learning- Vooluee 70, pp. 3309-3318. JMLR. org. 2017.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on Learning Theorry, pp. 2898-29989 2999,,993,.222 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pp. 880-887. ACM, 2005.
Benjamin Van Roy and Shi Dong. Comments the du-kakade-wang--aag lower bounds. arXiv preprint arXiv:1911.000 1.09900, 2019.
Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deterministic systems. In Advances in Neural Information Processing Systems, pp. 3021-3029, 2013.
Lin F. Yang and Mengdi Wang. Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. arXiv preprint arXiv: 2019a.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004, 2019b.
Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium Foundations of Computer Science (sfes 1977), pp. 222-227. IEFE, 1977.
12

---

Published as a conference paper at ICLR 2020
A PROOFS OF LOWER BOUNDS
In this section we present our lower bounds. It will also be useful to define the value function of given state E S₁ as (s) E - Th 5/ = 5, For simplicity, we denote Vi, = V (s). Throughout the appendix, for the Q-function Q% and Q% and the value function V and Vi may omit / from the subscript when it clear from the context.
We first introduce the INDEX-QUERY problem, which will be useful in lower bound arguments.
Definition A.1 (INDEX- QUEEY), In the INDQ,, problem, there is underlying integer i" [n]] The algorithm sequentially (and adaptively) outpus guesses E [n]] and queries whether = = The goal is to output i", using few queries as possible.
Definition A.2 (6-correct algorithms), For real number å E (0, 1), we say randomized algorithm
A is 6-correct for INDQ,.. if for any underlying integer i" E [n). with probability at least 1 5, A outputs i"
The following theorem states the query complexity of INDQ, for 0. 0.1-coreect algorithms, whose proof provided in Section B.I
Theorem A.I. Any 0. -correett algorithm for INDQ.. requires at least 0.9n queries in the worst case.
A.1 PROOF OF LOWER BOUND FOR VALUE-BASER LEARNING
In this section we prove Theorem 4.1 provided in Section B.2
We need the following existential result, whose proof is
Lemma A.1. For any n there exists a set of vectors P {po. Pi..... Pn- C Rd with d = [81n m/ such that
1. 1pell2 = for all 0 Sis S n 1;
2. (pr. S for any 0 S i,j S n with v
Now we give the construction the hard MDP instances. We first define the transitions and the reward functions. In the hard instances. both the rewards and the transitions are deterministic. There are H levels of states, and level h E [H] contains 2 distinct states. Thus we have |S] 2 - 1. If |S] 2 we simply add dummy states to the state space S. We use 8g; 81, ......... 82 -2 to name these states. Here, is the unique state in level h = 0, and 82 are the two states in level h = 1, 83, 84, 85 and se are the four states in level h = 2, etc. There are two different actions, @i and 02 in the MDPs. For state in level h with h < H 1, playing action aj transits state to state 52;4 and playing action a₂ transits state 8; to state #2++2. where 82++1 and 82:42 are both states in level
h + 1. See Figure for an example with H 3.
In our hard instances, r(s, a) = for all (s, a) pairs except for a unique state in level H - 2 and a unique action E {a1, }. It is convenient to define r(s') r(s, a), if playing action transits to s'. For our hard instances, we have r(s) = for a unique node s in level other nodes.
and r(s) = 0 for all
Now we define the features map o(..)). Here we assume 2 2- [8 2 and otherwise we
simply decrease the planning horizon so that d > 2. [8 2- H/82). We invoke Lemma A. to get set P {po, P1. -2 C 4://2 For each state 8i, d(s;, a1) Rd is defined to be [p:: 0), and Φ(s; 02) Rd is defined to be [0: p.]. This finishes the definition of the MDPs. We now show that no matter which state s in level H satisfies r(s) = 1, the resulting MDP always satisfies Assumption 4.2
By construction, for each level h E [H]. there is unique state sh in level i and action an E [a1, (z), such that Q" (sh, an) = 1. For all other (s, a) pairs such that take 07 to be Q* (ah an) o(sh an). Now we show that (Q= a) (07, o(s, a))l < for all states in level and {a1,a2)
Verifying Assumption 4.2
o St. oh, it is satisfied that Q* a) = 0. For given level h and policy
13

---

Published as a conference paper at ICLR 2020
(" (80,a1) a1)
Q (500 a2) =
81
82
(1(, =0
Q" (51, = Q'(s2, a1) =
Q" (5(2 02) 0
94
$6
Figure I: An example with H 3. For this example, we have r(ss) = and r(s) = for all other
states The unique state 8, which satisfies r(s) = marked dash in the figure. The induced Q" function is marked on the edges.
Case I: a * ag. In this case, we have Q" a) 0 and (0% ((s, a)) = 0, since f% and 6(s, a) do not have common non-zero coordinate.
Case II: a ag and * 8h. In this case, by the second property of P in Lemma A. and the fact that Q* (Sh, ap.) S 1, we have (00 (0x a)}l s 6. Meanwhile, we have Q (x, =0
Case III: a = dj and 8/.- In this case, we have (0% p(s a)) = (sh, an)-
Finally, we prove any algorithm that solves these MDP instances and succeeds with probability least 0.9 needs sample at least 20 2 trajectories. We do by providing reduction from INDQ2 to solving MDPs. Suppose we have an algorithm for solving these MDPs, we show that such algorithm can be transformed solve INDQ 1. For specific choice of i" in INDQ2* 1, there is corresponding MDP instance with
F(s) - {
if 8p422-1-1
otherwise
Notice that for all MDPs that we are considering, the transition and features are always the same. Thus, the only thing that the learner needs to learn by interacting with the environment is the reward value. Since the reward value is non-zero only for states in level H 1, each time the algorithm for solving MDP samples a trajectory that ends state s; where s; is state in level H
we query
whether i = 2 1 + 1 or not in INDQ and return reward value 1 if i = i i 2-2 + and otherwise. the algorithm is guaranteed to return a 1/2-optimal policy, then must able to find i*
A.2 PROOF OF LOWER BOUND FOR MODEL-BASED LEARNING
Note we just need to verify that the construction satisfies Assumption 4.3 By construction, for all e ... H - 1}. for each state s' in level h, there exists unique (s, a) pair such that playing action a transits to 8', and we take (ss)) = Φ(s,, a). We also take Bn = 0 for E {0,
Proof of Theorem We use the same construction as in the proof of Theorem 4.1
10, .,, 4, H 3) and 8H-2 o(s a) where (s is the unique pair with R(s. a) 1. Now, according to the design of ())))) and Lemma A.I Assumption 4.3 is satisfied.
A.3 PROOF OF LOWER BOUND FOR POLJCY-BASED LEARNING
In this section, we present our hardness results for linear policy learning. We first prove a weaker lower bound which only satisfies Assumption 4.4 and then prove Theoerem 4.3
14

---

Published as a conference paper at ICLR 2020
Warmup: Lower Bound for Linear Policy Without Margin. To present the hardness results, first give the construction of the hard instances. The transitions and rewards functions of these MDP instances are exactly the same as those in Bection[A.I] The main difference is in the definition of the feature map <6.;,). For this lower bound, we define o(s. = - R if a = 01 and Φ(8, a) = -1 if a 02- By construction, these MDPs satisfy Assumption 3.Twith p 1. We now show that no matter which state in level H - satisfies F(s) the resulting MDP always satisfies Assumption 4.4
Recall that for each level h [H]] there is unique state 8, in level h and action a₁ E {a1, a. such that Q" (sh, as) = 1. For all other (s, a) pairs such that & 8h or + d/. it is satisfied that Q" (s. a) = We simply take 0g be 1 if ag. a1 and take 0n to be -1 if an 02.
Verifying Assumption 4.4.
Using the same lower bound argument (by reducing INDEX-QUERY to MDPs), we have the following theorem.
Theorem A.2. There exists a family of MDPs and a feature map & (-5.) that satisfy Assumption 4.4 with d and Assumption 3.1 with p 1, such that any algorithm that returns a 1/2-oplimal policy with probability at least 0.9 needs to sample Q2 (2 trajectories.
Now we prove Theoerem 4.3 In order to prove Theoerem 4.3 the following geometric lemma whose proof provided in Section B.3
Proof of Theoerem
we need
Lemma A.2. Let d 4 be positive integer and e E (0, 1) be a real number. Then there exists set of points N C gd-1 with size IW = (2(1/4/22 such that for every point x E EN,
inf VEconv(VMMa)
|| - ul12 2 e/2.
Now we are ready to prove Theorem In the proof we assume H d, since otherwise we can take H and d to be min H, d} by decreasing the planning horizon H or adding dummy dimensions to the feature extractor Φb
Proof of Theorem 4.3 We define a set of H deterministic MDPs. The transitions of these hard instances are exactly the same as those in Section The main difference is in the definition of the feature map Φ(- .) and the reward function. Again in the hard instances, r(s, a) O for all in the first 1/ 2 levels. Using the terminology in Section A.] we have F(s) = 0 for all states in the first H 1 levels. Now we define F(s) for states s in level H - 1. We do so by recursively defining the
optimal value function (-(.). The initial state so in level satisfies V V*(sg) = 1/2. For each state s; in the first H - 2 levels, we have (*2+++1 = (*:);: and V (82)+2) = V*
1/2H. For each state 8; in the level h = - 2, we have r (82--1) 1) = (*:):) and F(22++2 = (*.))) - 1/2H. This
implies that p 1/2H. In fact, this implics stronger property that each state has unique optimal action. See Figure 2 for an example with H = 3.
To define 2 different MDPs, for each state in level // - of the MDP defined above, we define new MDP by changing F(s) from its original value to 1. This also affects the definition of the optimal
V function for states in the first H - 1 levels. In particular, for each level i {0, 2, ..... H 2]. we have changed the V value of a unique state in level from its original value (at most 1/2) to 1. By doing so we have defined 2 different MDPs. See Figure 3 for an example with H 3.
Now we define the feature function ((.,)). We invoke Lemma A.2 with e = 8A and d = H/2 d=H/2 - 1.
Since A is sufficiently small, we have [W1 2 2 We use P = {pu. P2..... P2 - C R 1/ to denote an arbitrary subset of A with cardinality 2 By Lemmal A.2 for any p E P. the distance between p and the convex hull of P \ {p} is at least 44. Thus, there exists hyperplane L which separates p and P (p), and for all points E P, the distance between g and L, is at least 2A. Equivalently, for each point p E P, there exists Rp E 1/2-1 and Op E R such that ||ppll = 1,
lopl < 1 and the linear function (q) (q, n,) op satisfies (p) 2 24 and fy(4) S -2A for all q E P (p). Given the set
{po. P2. ... P2# } C IR 112-1 we construct a new set
'Recall that r(s') = r(s,, a). if playing action transits to s'. Moreover, for the instances in Section A.1 we have F(s) for unique node in level H and ((a) = for all other nodes.
15

---

Published as a conference paper at ICLR 2020
(*(0)) = 1/2
(*(s)) = 1/2
(*( 1/3
F(83) 1/2
F(s1) 1/3
F(as) = 1/3
F(ss) 1/6
Figure 2: An example with H/
(50) =
V*(ai) 1/2
(x2) =
F(53) = 1/2
F(34) 1/3
F(s6) 1/6
Figure 3: An example with 3. Here we define a new MDP by changing r(8s) from its original value 1/3 to 1. This also affects the value of V(22) and (so)).
16

---

Published as a conference paper at ICLR 2020
P (Po. P....., .,. C R where P. |P;; 1] RR Thus I1, l2 v2 for all P. P.
Clearly, for each p P. there exists a vector wp E2 //2 such that (wp.P) 2 24 and (wp 7)
-2
for all q E P {p). It is also clear that ||,/||2 V v2. We take ((s;, ai) - [0: P.] ((8,, 02) = pp: E R
E R # and
We now show that all the 2 MDPs constructed above satisfy the linear policy assumption. Namely, we show that for any state in level H -1,
1. after changing 7(s) to be I, the resulting MDP satisfies the linear policy assumption. As in Section A. for each level h E [H.. there is unique state 8 in level and action on E {a), (2), such that (*h,,, a4) = For all other (s, a) pairs such that 8 + 8n. or & a/., is satisfied that Q" a) = 0. For each level h, if an d1, then we take (0h)
1 and (0x) = 11, and all other entries in 0n are zeros. If α₁ = 022 we use p to denote the vector formed by the first H/ 2 coordinates of ((5)> a2). By construction, we have p E P. We take 9, = [ 0] in this case. In any case, we have |6 2| I V2. Now for each level h, if aa d1, then for all states in level h, we have x =s) = 01 In this case. (ø(s, a1), 0a) = and (ø(s, 02), 0p) = 1 for all states in level h, and thus Assumption 4.5 is satisfied. If as d2, then x²" (sk. = d2 and x² ==((s) dg for all states + Sh. in level h. By construction, we have (fn, ((8, = O for all states s in level h, since On and ((s, a1) do not have common non-zero entry. We also have (0n, ó(5). (2))) and (On, Φ(8, a2)) S -22 for all states + 8%. in level h. Finally, we normalize all 0,, and ((s, a) so that they all have unit norm. Since [ a)ll2 = v2 for all (s, a) pairs before normalization, Assumption 4.5 still satisfied after normalization.
22
Finally, we prove any algorithm that solves these MDP instances and succeeds with probability least 0.9 needs sample at least 222 trajectories. We do so by providing a reduction from INDQgH-1 to solving MDPs. Suppose we have an algorithm for solving these MDPs, we show that such an algorithm can be transformed to solve INDQ2H-1. For specific choice of 1" in INDQ2r-1, there is corresponding MDP instance with
if 8:--2H
r(s) the original (recursively defined) value otherwise
Notice that for all MDPs that we considering, the transition and features are always the same. Thus, the only thing that the learner needs to learn by interacting with the environment is the reward value. Since the reward value is non-zero only for states in level H each time the algorithm for solving MDP samples a trajectory that ends at state where 8 is state in level H - 1, we query 2 -1
whether i and it original reward value otherwise. If the algorithm is guaranteed to return a 1/ /4-optimal policy, then it must be able to find i*.
or not in INDQ and return reward value I if i" i 2 + 1
B TECHNICAL PROOFS
B.1 PROOF OF THEOREM A.1
Proof. The proof is straightforward application of Yao's minimax principle Yao 1977). We provide the full proof for completeness.
Consider input distribution where i" is drawn uniformly random from [n]. Suppose there is a 0.1-correct algorithm for INDQ,, with worst-case query complexity T such that T < 0.9n. By averaging, there is deterministic algorithm A' with worst-case query complexity T, such that
Pr [A' correctly outputs i when i" = i] > 0.9. (M
We may assume that the sequence of queries made by A' is fixed. This is because (i) A' is deterministic and (ii) before A' correctly guesses it, all responses that A' receives the same (i.e., all guesses are incorrect). We use S = {(1, $2.... ....... sm)) } to denote the sequence of queries made by A'. Notice that m the worst-case query complexity of A'. Suppose m 0.9n, there exist 0.1n distinct [n] such that A' will never guess i, and will be incorrect if it equals i, which implies
Pr [A' correctly outputs i when i = s] < 0.9. sw/p
17

---

Published as a conference paper at ICLR 2020
B.2 PROOF OF LEMMA A.1
We need the following tail inequality for random unit vectors, which will be useful for the proof of Lemma A.1
Lemma B.1 (Lemma 2.2 in Dasgupta & Gupta (2003)). For a random unit vector in Rdd and B 1, we have
Pr [uî 2 3/d] s exp((1 + In B)/2).
In particular, when B 2 6, we have
Pr [u] > 3/d] S exp(-3/4).
92..9....... ... be a set of n independent random unit vectors IR with d = [8 In n/e" We will prove that with probability at least 1/2,, Q satisfies the desired properties as stated in Lemma A.I This implies the existence of such set P.
Proof of Lemma A. Let Q
It is clear that ||//||2 that for any i.j E [n] with * j. with probability at least 1 1/2 we have (gg, g,)l - c. Notice that this is sufficient to prove the lemma, since by union bound over all the (2) - n(n - 1)/2 possible pairs of (i,j), this implies that Q satisfies the two desired properties with probability at least 1/2.
for all i [n],, since each qi is drawn from the unit sphere. We prove
Now, we prove that for two independent random unit vectors and Rd with d 1/ n/ with probability at least 1 - _/2 (u, u) S e. By rotational invariance, we assume that e is a standard basis vector. I.e., we assume 11 and v 0 for all S d. Notice that now (u, v) is the magnitude of the first coordinate of u. We finish the proof by invoking Lemma B.1 and taking 8 In >
B.3 PROOF OF LEMMA A.2
Proof of Lemma A.2 Consider Ve-packing N with size 1/1/e4/2) on the d-dimensional unit sphere gd-1 (for the existence such a packing, see, e.g., Lorentz (166)). Let be the origin. For two points x' E RR4, we denote |xx'| := | x' a'112 the length of the line segment between æ.
Note that every two points x, x' E satisfy |a:=r| 2 Vt.
To prove the lemma, it suffices to show that N satisfies the property equation [ Consider a point x N, let A hyperplane that is perpendicular and every other points in N. We let the distance between and A be the largest possible, i.e., A contains point in Mxx Since x is on the unit sphere and / is a a/ /E-packing, we have that is at least /e away from every point the spherical cap not containing defined by the cutting plane A. More formally, let be the intersection point of the line segment oz and A. Then
x (notice that æ is a also vector) and separates
Vy (v/ E sd-= (b. v/) [1M12]
|| vl1 Ve.
Indeed, by symmetry, Vy e (6, < [bb12].
- vll 2 | 21|2 2 Ve.
where N' A. Notice that the distance between and the convex hull of A is lower bounded by the distance between x and A, which is given by |bx]. Consider the triangles defined by I, O, b. We have bz 1 oz (note that bz lies inside A). By Pythagorean theorem, we have
[bz|2 [bar 2
|=z|2
|xx| + |bo| |xo| 1;
2 = 1. |bz|2 + |ōol² |oz
Solve the above three equations for [bxr,, we have
|bx| |2:
1/222/2220 6/2
desired.
18

---

Published as a conference paper at ICLR 2020
C EXACT LINEAR Q' + GAP IN GENERATIVE MODEL
In this section we present and prove the following theorem.
Theorem C.1. Under Assumption 3.7 Assumption 4.2 and Generative Model query model, the agent can find the optimal x² with poly dd, H. p. log (1) queries with probability 1 - for a given failure probability 0,
C.1 We first describe the algorithm. For each level, the agent first construct barycentric spanner An - { (l))....((($f, ag} C db - (ss,a) (Awerbuch & Kleinberg 2008). We have the property that any o(s,a) with sh E Sh A, we have Ca.at.r, s,a [-1,,] such that Φ(s, a) = >i 2, (ss) aa))
Proof of Theorem
The algorithm learns the optimal policy from h = H 1....,0. has learned the optimal policy oh at level = + 1.....
0. At any level h. we assume the agent
Now present procedure to show how to learn the optimal policy level h. At level h, the (
agent queries every vector o(s), aa)) in A₁ for poly(d, /. log (4) times and uses Th+1: TH as the roll-out to get the on-the-go reward. Note by the definition of '² and Q", the on-the-go reward is an unbiased sample of (s), at)) We denote ((5) oj,) the average of these on-the-go rewards. By Hoeffding inequality, it is easy to show with probability 1 H² for all = 1....,d, d, (11 a.) (th ) S poly (). Now we define our estimated Q' at level h as follow: for any as E Sn x A. Q (s. = - ( ). By the boundedness property ca.a. we know for any (s, as.a)e E Sn x A, Q (s. a) Q (s, a) < f. Note this implies the policy induced by Q is the same as x². Therefore by induction we finish the proof.
D LINEAR Q" FOR ALL π IN GENERATIVE MODEL
In this section we present and prove the following theorem.
Theorem D.1. Under Assumption 4.2 with ó = O, in the Generative Model query model, there is an algorithm that finds an c-optimal policy áे using poly (d, ! trajectories with probability 0.99.
Proof of Theorem D. The algorithm is the same as the one in Theorem C.1 We only need to change the analysis. Suppose we are learning at level h and we have learned policies Th+1,...., - for level h + 1, + 2.... H - 1, respectively. Because we use the roll-out policy Th+1 -.. o H- by Assumption and and the property of barycentric spanner, using the same argument in the proof of Theorem C.1 we know with probability 1 0.01 / H, we can learn policy Ty with poly (d, H, samples such that for any s E Sn, we know n. is only sub-optimal by H from the T. where Tr is the HH 1 is the fixed roll-out policy.
optimal policy at level h such that Th+1
Now we can bound the sub-optimality of से A mo
WH-1:
VTOOTIOMOTTHL (s1) VIOO ow (81)
( ($1) p oo- (s1)
V AoomLomOFT (81) VIGORLOWOOR ((81)
+ 113 (81) V on (81).
The first term is at least - # by our estimation bound, The second term is positive by definition of no- We can just recursively apply this argument obtain
V Vaaomewerr
(s1) Vajum y oon (81)
улjomιo-от (($1) - yajoxio oo-ox (81)
c
H
2c
((1))
V o...orT (s1) H
19

---

Published as a conference paper at ICLR 2020
6,
20


Reviews:
[{"review_id": "SyeLBWVRFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper presents theoretical lower bounds on sample complexities to learn good policies in reinforcement learning. The derived theorems show that there exists MDPs which require an exponential number of samples to learn a near-optimal policy even if a good-but-not-perfect representation is given to the agent for both value-based and policy-based learning. These results constitute the first lower bounds for RL with linear function approximation.\n\nRepresentation learning is an important area of research and this paper advances our theoretical understanding in a notable way, helping to elucidate the limits of representation learning alone. The lower bounds derived in the paper would be of particular interest to the community as they can apply to a wide range of function approximators, including neural networks. Although this is not my area, the contributions are well-explained in the context of previous work and the theory was fairly easy to follow. The discussion also contained interesting points and summarized possible implications of the theoretical results. Overall, I think this paper presents a solid contribution and recommend acceptance.\n\nAlthough the paper was clear in general, I would like to have certain points clarified:\n1) Just to check, is it still possible that there exists certain representations that are not perfect but do lead to sample efficient learning? If I'm interpreting the results correctly, the theorems only posit the existence of a representation that is good in the sense of approximation error, but bad in terms of sample complexity, which does not necessarily preclude the possibility of other efficient representations.\n2) More generally, why is it that there are few results for lower bounds when it seems like an obvious direction? Are there technical barriers to proving such results?\n3) For value-based learning, the good representation has approximation error \\Omega(\\sqrt(H / d)). Could the authors explain why this assumption on the error is reasonable? \n3) In assumption 4.4, the features are assumed to have an l2-norm of 1. This seems like a fairly restrictive assumption. How important is this assumption and can it be relaxed?\n4) Also, in theorem 4.2, it is assumed that the dimension of the features, d = H. This would seem to allow the possibility of policy-based learning being sample efficient when the number of features is much smaller. \n\nThe paper is well-polished with few noticeable typos.\nMinor comments:\n- p.5 sec3.3: \"knows the whole transition\" -> \"knows the whole transition function\"\n- p.8 sec5.1: \"our lower bound on policy-based learning thus demonstrates\" It may be worth reminding the reader that the bound applies to perfect representations -> \"our lower bound on policy-based learning---which applies to perfect representations---thus demonstrates\"", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Skl9pF8vKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper's contribution is a sample complexity lower bound for linear value-based learning and policy-based learning methods. The bound being exponential in the planning horizon is bad news, and has some implications with respect to further analysing sample complexity in RL.\n\nThe gist of this paper is that one can craft a hard MDP which requires visiting every state at least once, and that since this MDP's state space is exponential in the MDP's horizon, then there exists a set of MDPs which require an exponential (in the horizon) number of trajectories to be solved. As a consequence, further analysis of sample complexity in RL may need some much stronger assumptions.\n\nThe writing of the paper is good, I was able to understand everything (I think). As far as I can tell, this is novel work. Unfortunately I am currently unable to see why this contribution is valuable. I have set my score to weak reject but I am very open to having my mind changed, as I feel I may have missed some critical element.\n\nI have two criticisms:\nA- I don't understand why this bound is significantly different than previous bounds.\nB- I don't understand why this is bad news for representation learning, nor how this failure mode of linear features translates to the \"deep\" case.\n\nIn the same spirit, I find rather odd the way the paper is introduced. Discussions of representations usually involve some discussion of generalization, but that's not what this paper is about. Deep neural networks/representation learning are only useful if there is an opportunity for generalization.\n\n\nWith respect to A, I am either grossly misunderstanding past bounds and/or your bounds, or something is wrong with the way complexities are compared:\n- In Wen & Van Roy, the \"polynomial\" sample complexity is in the number of states, it is related to |S|x|A|xH^2 (Theorem 3 of Wen & Van Roy)\n- In this paper, Theorem 4.1 states that the sample complexity is exponential because it is of the form 2^H. One *critical* assumption for this bound is precisely that |S| >= 2^H. Thus the bound that you propose is still polynomial in |S|.\nI am thus puzzled, how is this bound significantly different?\n\n\nWith respect to B, I don't see how this bound has much to do with good representations, or even representations at all.\nIn Lemma A.1, you essentially craft a set of features that, being mutually orthogonal, are in some sense \"mutually linearly separable\", making learning the mapping from those features to a value function \"trivial\" once data is obtained. This is barely different from saying that you assume there is a magical learner that learns in O(1) given the data, because in either case, you need to visit _every_ of the 2^H state in order to solve the MDP, because by construction of your problem, there is _no hope_ of generalization*. Since learning features or creating \"good\" features has everything to do with generalization (otherwise we'd just to tabular), I don't see how this bound is relevant to representations. (We already have Wolpert's no free lunch theorem to tell us that there are always some problems that ML just can't be general enough to solve efficiently. What is more interesting is understanding how we can efficiently learn where there _is_ structure to a problem.)\n* There is no hope of generalization, unless something about the observation space (which is left undiscussed in the paper) contains *information* about the agent being to the unique path to the reward. In such a case, I can see a probabilistic argument being made where in the worst case the agent needs to visit all 2^H states, but in the average case, the agent may learn to ignore paths where it can generalize that there is no reward. This is not entirely unreasonable, think of e.g. AlphaGo, where very few states end in victory, where there is an exponential number of states in the horizon, yet learning is totally reasonable because of structure in observation. This is where I don't agree with a statement like: \"Since the class of linear functions is a strict subset of many more complicated function classes, including neural networks in particular, our negative results imply lower bounds for these more complex function classes as well.\" \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxjXgv0tS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe author question an important aspect which is very often taken for granted in the RL community, that a good representation could lead to data-efficient RL. They show negative results, providing pessimistic lower bounds for both value-based and policy-based learning.  \n\nI believe the paper is an important contribution, in particular, it has the following advantages:\n\n - Well written, clear, and nicely structured. It is self contained, with main results and convincing sketch proofs provided in the main body of the document, and extended technical proofs made available in the supplementary material.\n\n - Authors provide the relevant related work and elegantly show how their work connects to the existing literature.  \n\n- The notation is consistent throughout the document, with necessary assumptions clearly stated.  \n\n- The discussion highlights important findings, in particular the difference between value-based and policy-based learning. Additionally, it offers some hope for sample-efficient RL, by discussing the exponential separation between policy-based RL and imitation learning, reminding the community that sample-efficient RL can still be achieved by IL even if it can’t be achieved through good-but-not-perfect representation. \n\n   Minor comment: - Phrasing of Assumption 4.3 seems to be off.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors challenge the idea that good representation in RL lead are sufficient for learning good policies with an interesting negative result -- they show that there exist MDPs which require an exponential number of samples to learn a near-optimal policy even if a good-but-not-perfect representation is given to the agent for both value-based and policy-based learning.  Reviewers had some minor technical questions which were clarified sufficiently by the authors, leading to a consensus of the contribution and quality of this work.  Thus, I recommend this paper for acceptance.
Decision: Accept (Spotlight)