Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers a generic importance sampling weighted ERM algorithm for minimizing the loss over a hypothesis class when the data are adaptively collected (i.e., previous choices and their respective feedback received affect subsequent choices). Such adaptively collected data are the result of data collected from a contextual bandit algorithm, for example. The paper provides generalization guarantees for the proposed method and fast convergence rates under some extra assumptions. The technical derivations are based on a new maximal inequality that obtains a better dependence on the exploration rate of the data than prior work. The paper shows the applications of the method for the convergence rates on least squares and policy learning. Finally, it provides empirical results comparing the proposed method with related ones.

main_review: ===== After Rebuttal =====

I'm thankful to the authors for their response and for providing clarifications to my questions! I remain positive towards the paper but would like to stress once more that, as a non-expert in the area, it was sometimes hard to evaluate the significance of the paper. Please incorporate the suggestions that myself and others included in their reviews, and hopefully, this will make the paper more accessible to non-experts.

======================


Evaluation.
The paper is pretty much outside of my area of expertise. Below is my best effort to evaluate whatever I could understand from the paper. 
* The method of reweighting the importance sampling in order to account for changes in the data looks like something that people have already thought about. I am not sure about prior work related to the present paper, but there are certainly bandits settings (even non contextual ones) where the better regret rates are obtained just by carefully reweighting with the appropriate distribution.
* That said, it seems that the topic (i.e., identifying ways to reweigh the ERM so as to achieve generalization bounds when the data is adaptively collected) is very interesting and broadly applicable. It is also nice that the paper closes previous gaps existent in the literature and that it shows the applicability of the method in the regression and policy learning settings. 
* It was nice that the paper has remarks and explanations in various places that explain connections and differences with prior work. 
* One limitation that I see from the general setting is that it seems to require perfect knowledge of the algorithm (or at least the process) used to collect the data (see also my first question below). 

Questions.
* This is pretty fundamental and I am sorry if it is obvious but in order to do this reweighting don’t you need to know the density p^{(T)} but also the decomposition to p_X, \tilde{g}, and p_Y? Why is this an okay assumption in this line of work? It would seem to me that it is restraining since you need to know exactly the process by which the dataset was generated. Or is the paper saying that just by having access to \bar{O}_T you can compute p^{(T)}?
* It is claimed in at least two places (see Lines 9 and 170) that the dependence on \gamma_t from Theorem 1 is the “right” or the “optimal” one. But how do we know this? I could not find a lower bound in the paper. Is there a result in the literature that establishes it? Is it due to the lower bound of Zhan et al. [58]?
* I understand that the paper acknowledges that the empirical results are not intended to provide state-of-the-art methods. That said, I am sorry to say that I am a bit confused regarding the usefulness of the method since it doesn’t outperform other methods dramatically. Also, could you please comment on the runtimes for the methods?

Additional comments.
* What is \tilde{g} referring to in Line 43? Is it the probability that action a_t was chosen given context x_t and the history of past outcome tuples?  
* What is the “following” referring to in the citations in Line 301?
* Is \alpha also <=1 in Assumption 4? I was trying to figure out which one is the dominant term in the last equation of Page 5, to see the difference with Theorem 2. 
* Structurally, I think since Sections 4 and 5 are applications of the main theorems of section 3, I would suggest that you have them as subsections in Section 3, rather than standalone sections.
* Regarding the limitations question in the checklist, you do list carefully all the assumptions under which your theorems work, but I think it would be nice to include a small paragraph about more model-specific/high-level limitations. For example, if indeed p^{(T)} is assumed to be known in this work, I would consider this a potential limitation.

Typos.
* Line 80: “biblioraphies” → “bibliographies”
* Line 151: “of classes of classes” → “of classes”
* Line 156: “rate of the the IS” → “rate of the IS”
* Line 233: “withe envelope constant” → “with the envelope constant”
* Line 300: “different mutli-calss classification dataset” → “different multi-class classification datasets”
* Line 661: I think that the instantiation is on Theorem 3, not Theorem 6.

limitations_and_societal_impact: Overall yes. I have added a comment regarding the limitations in my main review.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper considers empirical risk minimization when data is generated from a markov decision process.
Their particular framework, called stochastic-contextual-bandit, covers several applications such as e-commerce and policy making.
The paper is mostly theoretical: a uniform bound on empirical sums over classes of functions with controlled bracketing numbers is given. Then this general result is applied to two different loss functions (least squares regression and one other related to policy learning).  In both settings, slow and fast rates are obtained depending on certain assumptions on the model.
main_review: Let me say from the start that I like this paper very much. It is well written, the results are interesting and novel, and the mathematics are well-educated. I have several questions and concerns that I hope will help the authors to improve their work.


1. I am not sure the context of Markov decision process is useful in their proof of Theorem 1. Would it be possible to extend their results? In a more general context where the triplet O = (x,a,y) would no longer be necessary. In this way, (a) the proof’s arguments could become clearer  and (b) I also think that a more general framework could help in including more examples such as importance sampling (see for instance eq. (6) in Portier and Delyon. "Asymptotic optimality of adaptive importance sampling." NeurIPS. 2018, which seems to fall in the authors framework). Finally, the application to the context of Markov decision process would become less obvious than in the current version where Theorem 2 and 3 are direct corollary of Theorem 1.

2. It is difficult to see how the proposed bound compares with known basic results. For instance, if one is interested in the simple case when the class of functions is made of one single element, what would the authors recommend to use instead of their bound? How would it compare to their bound? In the same line of remarks, what is the closest results to their results in the iid setting?

3. While the literature review seems to have been done seriously, it is difficult to understand because it is written at an expert level. The framework described by the authors seems to be valid to post-process the data. Is this context different from standard online policy estimation such as in the classical reinforce algorithm? Being not very familiar with the contextual bandit framework, I had some issues in understanding the context clearly. I would suggest the authors be more specific about the applications.

4. The process xi_t is hard to understand and I believe it is not needed in the applications of their results. I would suggest simplifying the paper by removing to the supplement everything that is related to this process. If I am wrong and xi_t is useful then some remarks and examples should be given. In the event that xi_t is useless, then I would recommend simply writing f(O) rather than xi(f)(O).

5. The statement of Th1 is a bit strange due to the definition (or rather assertion), concerning gamma_T tilde inside the theorem. I suppose another way is possible.
 
6. Include a discussion about the validity of assumption 1. It seems to be related to the exploration in bandits algorithm but it is difficult to understand for non specialists. The behavior in T^beta of g^* / g_T is a claim that I cannot verify. Since this is used later in the paper to compare with the existing literature, I would recommend to give mode details;

7. The simulation study shows an advantage of ISWERM (over competitor) when using the LASSO and no significant difference for other considered methods. ISWERM is implemented with g^* = 1 and the model is then evaluated with the same g^*, I wonder what the role of that choice is. More generally, I believe that the role of g^* could have an impact on the outcome. Could the authors comment on this point? In example 1 and 2, the choice of g^* seems to be arbitrary but it certainly influences the results. Is there any recommendation to choose it?

8. The variance bound, Assumption 4, is given without any explanation or references, contrary to the margin assumptions.

Typos:
TH1 There is an epsilon in the bound of Th1 which should be an r I guess.
line 156 the the
line 151 classes of classes

##############SUPLEMENT###############

The supplementary material is well organized.
As far as I can check, the proof is valid.

I would suggest giving more details in some places such as:
- at the beginning of the proof, the authors combine Markov inequality and some properties of their function psi without saying it.
- Page 16, the given chaining decomposition is confusing because of the presence of two different index s and t (one of them seems to be useless).
- The definition of u^{j,f} equal to v^{j,k(j,f)} is surprising as the index t has been removed. Is it a short cut?
- The definition of Delta (indexed by t rather than s) is also surprising.
- I think the authors could be clearer on the meaning of their inequalities between functions (such as in the definition of tau), I
- Perhaps some explanations on the use of tau in the proof would be welcome
- When adding up the bounds, check they all are correct.
- At the beginning of the proof of Th2, there is some redundancy in saying that the diameter assumption is used.
limitations_and_societal_impact: YES
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the excess-risk rate of (importance weighted) ERM when data is collected adaptively (e.g. by a bandit algorithm). The authors argue that current excess-risk bounds are sub-optimal when the exploration rate of the data-collection process converges to zero. They then derive tighter bounds for this problem using a new maximal inequality for an importance-weighted empirical process. The results are instantiated for least-squares regression where it is shown that fast rates are achievable due to the properties of the square loss. Excess risk rates of the importance weighted ERM are also presented for policy learning, closing an open question around achievable rates in this setting. Illustrative experiments are also presented.
main_review:  In many modern applications, data is indeed collected adaptively (using a bandit algorithm for example) and it is important to be able to learn from such data. Therefore, this paper's topic is very important in machine learning. The paper also strengthens our theoretical understanding of generalization when learning from adaptively collected data by providing "state of the art" excess risk rates of importance weighted ERM (ISWERM). From a practical standpoint, this justifies the use of ISWERM instead of other alternatives. 

The results of the paper are based on a new maximal inequality for Martingale Difference Sequences (MDS) in Theorem 1. I wonder if the same type of result---with the right dependence in \gamma---can be derived more easily using concentration inequalities for MDS; for example, using Freedman's inequality (e.g. see Lemma 12 in http://proceedings.mlr.press/v125/wei20a/wei20a.pdf). The fact that Freedman's inequality has a variance term in the bound, would also allow the cancellation of the g_t(A_t |X_t) in the denominator of the importance weight. Freedman's inequality can be extended to the case where the process is index by f, where f is in some function class F. Can you explain why such a method would not work?

The paper is in general well written and has only minor typos.
limitations_and_societal_impact: The discussion provided in the paper seems adequate.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies how to perform risk minimization when the training data is adaptively collected. The main example that the authors refer to is the setting where the data is collected while running a contextual bandit algorithm. That data is certainly not i.i.d., so empirical risk minimization (ERM) will not necessarily generalize well. A popular alternative approach is to employ importance sampling (IS), where the samples are weighted by the inverse of the policy’s probability of choosing the observed action. However, the authors write that the existing analyses of IS are not well-suited for data collected via a contextual bandit algorithm, where the rate of exploration is decaying, so the IS weights will diverge to infinity. From my understanding, the authors provide a new analysis of “IS-weighted ERM” (ISWERM) which allows them to provide a bound on excess risk that has a better dependence on the exploration rate. For policy learning, with this new analysis, they match a lower bound by Zhan et al. [arXiv‘21].
main_review: This paper studies a very important, practical problem where we want to optimize over a hypothesis class using adaptively collected data. The main downside is that as a non-expert reviewer (but with expertise in related areas), I had trouble seeing the forest for the trees. It was difficult for me to understand the core technical contribution (the new “maximal inequality” described in Section 2) because of how technical it was—the entire paper could *really* benefit from some interpretation for the reader. Here are some specific examples:
-	Lines 53: What do you mean by a reference policy g*? How is it chosen, and how does it relate to g_t? Are there reasons why we’d use a different reference policy than the deterministic one suggested in line 53 (g*(x | a) = 1)?
-	Line 144: The function M_T(f) seems to be an important definition. It’s always important to not only provide the mathematical definition, but also describe what it is in words.
-	Line 147: Can you provide some interpretation of the sequential bracketing entropy, in addition to defining it formally?
-	Theorem 1: This is difficult for me to parse. Can you provide some intuitive interpretation of this bound? Most importantly, intuitively, how will it help you provide better rates for ISWERM?
-	Assumptions 1-7: There are a quite a few assumptions that are stated quite formally. Perhaps these are common (for example, from lines 285-288, it seems like Assumption 7 is common), but as someone who is not familiar with the related research, it’s a bit hard for me to grasp whether they’re reasonable assumptions to make. If you could provide more context around the assumptions and explain why they might be reasonable, that would help a lot.

More detailed comments:
-	Line 51: What is a “non-anticipatory action”?
-	Line 80: “biblioraphies" -> “bibliographies”
-	Line 145: “sequence sequence” -> “sequence”
-	Line 146: I am not familiar with what it means for g* to be in the subscript of the norm notation. Could you please define this?
-	Line 147: It seems that lambda is overloaded.
-	Line 151: “of classes of classes” -> “of classes”
-	Line 233: “withe” -> “with”
-	Line 300: “mutli-calss” -> “multi-class”
limitations_and_societal_impact: I believe that the authors have sufficiently described the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: Thanks for the strong submission. After discussion, the reviewers were unanimously in favor of acceptance, although are concerned that the paper is difficult to read for readers even a little bit outside of the target area: we suggest a revision for clarity. 
Decision: Accept (Poster)