Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper presents a impossibility result for value-function approximation in batch-mode RL. The chart below puts this work in context. This work essentially shows -- through a constructive example of an MDP -- that the amount of data needed for approximating Q values must increases exponentially with the horizon in episodic RL tasks even if we assume that the Q-values are realizable and that the features gathered by the behavior policy -- that collected the data -- are uncorrelated. This problem arises because the data gathering policy can fail to get data from all states even though the features themselves are uncorrelated. 

The authors claim that this setting is interesting because these conditions only require polynomial-number of samples in the standard supervised learning case, and I agree with that. Broadly I checked the main construction in the paper and the result seems correct. I think this paper will be a good addition to ICLR.

      |                | Strong Concentratibility|  
      |                | extra conditions on     | (Xie Jiang 2020)
      |                |  the dynamics of the MDP|  [✓]
      |                |
      |Coverage of the | Concentrability         |       Szepesvári and Munos 2005
      |behavior policy | (experience gathered    |                      [✓]
      |                |  from every state)      |
      |                | 
      |                | Uncorrelated            | This work
      |                | Features                | [x]
      |________________|______________________________________________________________
      |                                           Realizability     Bellman Closedness
      | bellman closed = Every intermediate value function arrived at after 
      | bellman update is also linearly realizable
      |_______________________________________________________________________________
      |                             Representability of Q values


## Some comments

1. Assumption 2 will actually imply that  σ_max = 1/d as well because (σ_min + ... + σ_max) ≥ d σ_min = 1 and sum of eigenvalues equals the trace, and exchanging trace and expectation will give (σ_min + ... + σ_max) ≤ 1. I.e. the covariance is necessarily scaled identity matrix ⇒ the features are uncorrelated.


review_title: A good constructive example of the impossibility of efficient Batch RL with realizability and uncorrelated features.

final_score: rating: 7: Good paper, accept
review_content: ### Summary

This is a theoretical paper proving an MDP exists in which there is a lower bound on the number of off-policy samples necessary to sufficiently linearly approximate the Q-functions which is exponential in the time horizon of the MDP.  In addition, they demonstrate that while this can be mitigated with samples pulled from a similar policy to the optimal one, the sample distribution must be quite similar, due to cascading geometric error.  The paper is a challenging one to read, and I can't say I followed the whole proofs, but I understand the results.

### Significance

This result is quite important in understanding the feasibility of off-policy approximation.  While the proofs are on linear approximation schemes, it provides intuition into the behaviors of more modern off-policy non-linear schemes, as well.  Of course we intuitively knew off-policy approximation becomes more difficult the more dissimilar the samples are from the optimal policy, but the theoretical support of exponential sample size is very useful and meaningful.

### Originality

The paper's results are new, to my experience.

### Quality and Clarity

The proofs are creative and well done.  I do wish the intuitive explanations of the theorems were better organized and more fleshed out.  There is a heavy dependence on citation.  For example, "It is well known that in order to distinguish r_1 and r_2 with probability at least 0.9, any algorithm requires <many> samples." fills a very key place in understanding the theorem.  I'm not familiar with this result, and without it, I don't understand a key moment of the proof.

### Conclusion

I think it's an important paper, and is highly relevant to the large amount of work that uses off-policy samples.  I don't think it's written very clearly, which is a shame.
review_title: Important demonstration that off-policy RL requires a number of samples exponential in the horizon of the MDP for accurate value function approximation

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper provides a theoretical analysis on the sample complexity of OPE with linear function approximation and assumptions on representation and distribution shift. The main results shows that realizability and feature coverage are not sufficient to guarantee a polynomial sample complexity. The paper also provides a performance guarantee for LSVI with a stronger assumption on the distribution shift. 

In general, the paper provides a sound (and correct) theoretical analysis, the construction of the hard instance is new. In section 5,  I think the measure of the distribution shift in terms of the covariance matrix is also new. I believe the paper can have a significant contribution to the batch RL/offline RL community. Therefore, I recommend to accept this paper. 

##### Comments and clarification questions
In terms of clarity, the main text is clearly written, and the related work section is comprehensive.

The paper mentions that ”batch RL is not guaranteed unless stronger conditions on the distribution shift or stronger representation conditions beyond realizability”. However, the paper seems to focus on the former and does not have any analysis for the latter in the main text. For example, what is the guarantee of LSVI under closeness under Bellman update (without mild distribution shift assumption)?

The paper might benefit from giving some explanations on why low C_h (defined in assumption 3) implies mild distribution shift.  Moreover, can you elaborate more on this sentence "we measure the distribution shift in terms of the spectrum of the feature covariance matrix of the data distribution, which is more natural than the concentrability coefficient for the case of linear function approximation"? What is the connection between assumption 3 and the concentrability coefficient?

I did not carefully check the proof in the appendix, therefore, I give myself a slightly low confidence score. 

**
Post-rebuttal update: the score is increased from 7 to 8.
**
review_title: Sound theoretical analysis

final_score: rating: 7: Good paper, accept
review_content: It's an interesting paper showing provably efficient batch RL is impossible when only two assumptions holding: a) Realizability, and b) Feature Coverage. By providing counter-examples, which is quite persuasive as the State/Action Space is only polynomially dependent in H, the sample complexity could be exponentially dependent in H w.h.p. 

However, I still have doubts about the Assumption Feature Coverage. Different than Assumption Concentrability [Chen & Jiang(2019), Xie & Jiang(2020a)], Feature Coverage only assumes that feature covariance matrix has minimum eigenvalue 1/d. My doubts then follow: 
1) Is Asp Concentrability a more stringent asp than Asp Feature Coverage (from a mathematical perspective)? If so, why we would concern Asp Feature Coverage while Chen & Jiang(2019) already proves Asp Concentrability is necessary for efficient batch RL?
2) Can Asp Feature Coverage really represent exploratory of the batch dataset? In RL's perspective, exploratory is important empirically and theoretically. However, in the hard instance, the important states $s_h^*$ are even not in the support of the dataset (maybe also breaks the Asp Concentrability?), though I understand it's necessary to obtain the exponential lower bound.
3) Theorem 5.1 confuses me a little. I understand the main goal is to illustrate Error Amplification. But why we would concern upper bound instead of the lower bound? Or Sec5 aims to say that Error Amplification is unavoidable under Realizability and Feature Coverage?

In conclusion, I argue that this paper is well-written and answers the question perfectly with certain assumptions. I have also checked the proof and there are no significant errors. Though I have some doubts about whether certain assumptions are reasonable enough in RL, I still stay positive about this paper. My doubts may be incorrect, but I'm looking forward to the discussion.

review_title: Review

Meta-review: The paper shows hardness results for batch reinforcement learning. Authors show that even if all value functions are linear in a given set of features and the exploration data covers all directions, evaluating any policy might require a sample size that is exponentially large in the problem horizon. This is an interesting and somewhat surprising result, and I believe it would be of interest to the wider RL community. I recommend acceptance of this paper.
Decision: Accept (Spotlight)