Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: 
The 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.  

I believe the paper is an important contribution, in particular, it has the following advantages:

 - 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.

 - Authors provide the relevant related work and elegantly show how their work connects to the existing literature.  

- The notation is consistent throughout the document, with necessary assumptions clearly stated.  

- 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. 

   Minor comment: - Phrasing of Assumption 4.3 seems to be off.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: 
This 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.

Representation 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.

Although the paper was clear in general, I would like to have certain points clarified:
1) 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.
2) 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?
3) 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? 
3) 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?
4) 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. 

The paper is well-polished with few noticeable typos.
Minor comments:
- p.5 sec3.3: "knows the whole transition" -> "knows the whole transition function"
- 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"
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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.

The 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.

The 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.

I have two criticisms:
A- I don't understand why this bound is significantly different than previous bounds.
B- 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.

In 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.


With respect to A, I am either grossly misunderstanding past bounds and/or your bounds, or something is wrong with the way complexities are compared:
- 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)
- 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|.
I am thus puzzled, how is this bound significantly different?


With respect to B, I don't see how this bound has much to do with good representations, or even representations at all.
In 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.)
* 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." 

review_title: Official Blind Review #1

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)