Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: null
review_content: Dear all,

I have a serious concern that I would like the authors and reviewers to confirm.  
As I have already explained in several replies, it seems that Assumptions 5 and 6 constrain the bandit problem that the proposed method can be used.  
- Under these assumptions, the problem suffers a $T^{2/3}$ regret even in the ideal situation. We agree with the authors on this point.
- This constraint becomes more difficult depending on the problem (Assumption 5). This is very different from the case of Hadad et al. (2020), where a bandit problem (without contextual information) with a regret close to $\log T$ can be evaluated independently of the problem (Theorem 3 in Hadad et al. (2020)).
- It is not clear what kind of bandit problems can be evaluated under Assumption 5 and Assumption 6.
- In the limited case of nonparametric bandits, which may suffer from a $T^{2/3}$ regret, the $p$ in Assumption 5 will become large, requiring a slower exploration rate from Assumption 6. Under these assumptions, it is unclear how much of the regret will be incurred.
- It is also unclear whether the experimental setup of the paper satisfies Assumptions 5 and 6. I am concerned that these assumptions may be violated. The paper sets an exploration rate of at least $t^{-1/3}$, which implies that $p$ is zero unless the expansion rate of the bandit algorithm is sufficiently slow, but $p=0$ contradicts with Assumption 6.

I believe that mathematical proof is needed for justifying Assumption 5 and 6.   
Also, these are not explained in the introduction and the problem formulation in this paper, and I think that the authors need to explain these limitation there.

Also, I want to discuss the novelty of this paper.   
- I think that Hadad et al. (2020)'s contribution was to simplify Luedtke and van der Laan (2016) by omitting the variance estimation and not considering the context. Luedtke and van der Laan (2016) used a rolling window (sample splitting) to estimate the variance, but avoiding it would require assumptions like Assumption 5 and 6.   
-  Therefore, if the authors use assumptions like Assumptions 5 and 6 to estimated the variance without a rolling-window, I think that the authors need to provide a justification for them.
-  Also, as I already mentioned, I think that the authors' results are a bit different from Hadad et al. (2020), where we can arbitrarily evaluate the bandit algorithm with a $\log T$ regret, while the authors' proposed method is applicable only to the bandit algorithm with a $T^{2/3}$ regret even in the ideal conditions (Assumption 5). 

The novelty may be a bit subjective issue, so not a core.  
Therefore, if the other reviewers agree that this study is novel, I have no objection.  
However, I think that theoretical justification is a critical issue.   

I feel that there is a big gap between the claims of the paper and the results as it is now.  
Readers will think that the proposed method can be widely used for the linear bandit after reading the beginning of the paper and problem setting.   
And they will not consider that the targeted bandit algorithms suffer from at least the $T^{2/3}$ regret.  
In order for this paper to be published, I strongly believe that during the reviewing period, the authors need to prove that the proposed method can be applied to some bandit algorithms, such as Rigollet and Zeevi (2010), which is cited by the authors in their reply to my comment.     
In addition, I think it is desirable to get agreement from the reviewers on which bandit algorithms the proposed method can and cannot be applied for and whether the experimental setup of the paper meets the assumptions, etc.  

By clarifying them, I hope to avoid misunderstandings of readers and subsequent researchers.  
I would like authors and reviewers to check these points.    
And if I am wrong, please tell me about it.  
review_title: Official Review of Paper10679 by Reviewer 2WyM: Discussion on the theoretical justification

final_score: rating: 7: Good paper, accept
review_content: summary: The current paper concerns inference of quantities such as
treatment effects or policy values from data that is collected
from contextual bandit experiments, Motivated by applications
in healthcare, revenue management or product recommendations
where randomized experimentation is not often the norm.
They isolate a key issue (variance stabilization), identified
in previous works on analysis of adaptively collected data (see
paper for references), and propose estimators for average causal effects of the 
`doubly robust` form to overcome this issue. The main result
is a central limit theorem for this estimator, allowing
for frequentist inference (i.e. confidence intervals, p values) in the standard way.
The estimator relies heavily on a sequence of conditional variance estimators, which 
they construct using a judicious use of averaging and a base regression model for the outcome (
which may be misspecified even in the limit).

main_review: The problem dealt with in the paper is well-motivated and of significant interest
to the NeurIPS community. The paper is, modulo some suggestions below, well-written. 
I would advocate its inclusion in the conference program once the major comments
below are addressed.

Major comments:

1. Assumption 6 supersedes Assumption 3, saying the exploration rate needs to be
significantly greater than the worst case 1/sqrt(t) rate. This is crucial to the
construction of the CADR estimator and it is somewhat disingenuous to isolate it thus, unless
you have concrete scenarios where an alternative estimation scheme might exist that
does not require this exploration rate.

2. In the same vein as point 1, I don't think the form of Assumption 3 is sufficient for
the Lindeberg condition argument as laid out. For instance, consider the array Z_{t, T} = \sqrt{t/T} \eps_t
where \eps_t are i.i.d. random signs. This satisfies Assumption 3 but not the Lindeberg condition.
Possibly the argument may be tightened, but at the moment, it seems you need that the exploration is
\Omega(1/sqrt(t)).

Moderate comments:

1. Can you say how your CADR estimator reduces to the variance stabilizing construction in Hadad et al 2019 and, if not, what are the
differences? This would aid intuition for the reader.

2. Can you comment on the efficiency of the constructed estimator, or if we might need to look outside this class of estimators
for the most efficient estimator? Alternatively, a simple setting where it is the most efficient?

3. Some popular policies like UCB are not covered by your scheme given they have trivial propensities, it is good 
to mention this. I would also welcome a remark on how Thompson sampling type policies might apply.

Minor comments:

1. L.80 ambiguity with g vs g^*
2. Assumption 5 needs to be restated; perhaps missing punctuation/sentence splitting.
3. Similar ambiguity with Q_{0, X}, Q_{0,Y} vs Q_X, Q_Y in L78, L79. In general, the `0` subscript is a little overused. 
4. Define \cal{O} as the space of a, x, y triples (I assumed this and faced no obvious errors)
5. The use of a \bar{} is a bit inconsistent: \bar{O}(t), \bar{Q} and \bar{\Phi} mean different things (a sequence, 
an empirical average and just another thing). This causes some unnecessary readability issues.



limitations_and_societal_impact: The authors' work allows to use observational data from contextual bandit experiments for statistical inference purposes. In principle this can have potential societal impact, but would be within the context of a specific application (e.g. personalized medicine, policy making...). The authors' conclusion makes some aspects of this apparent.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a method for estimating the value of some fixed evaluation policy of interest using data that was collected with a contextual bandit algorithm. They prove that their estimator is asymptotically normal even when the model of the expected reward conditional on state and action is misspecified.
main_review: The result the authors present is interesting and appears to be an important contribution to the literature particularly because the model of the reward model can be misspecified. However, I believe that the paper is currently still weak because (1) insufficient discussion of the relationship to previous literature and (2) limited empirical evaluation. I would be willing to raise my score if the authors improve in these two respects.

Regarding previous literature
-	I am still unclear about how exactly your method differs from that of Hadad et al., 2019 and I think there should be additional discussion. In a non-contextual setting, is your estimator equivalent to that of Hadad et al. in a special case? How is your weighting scheme similar / different from that of Hadad et. al, 2019? There should be a more explicit comparison to understand how your contribution is different.
-	Line 127-128: This comment is vague. Could you elaborate on the relationship to Hadad et al., 2019. Later at Line 256, you say the main focus of the paper is that the estimator of Hadad is biased on contextual bandit data; this should be stated earlier if this is the case. And more discussion should be made, is your proposed estimator unbiased on contextual bandit data? What exactly is your argument that Hadad et. al, 2019 is insufficient for contextual bandit data?
-	How is your work related to more recent related work:
o	Off Policy Evaluation via Adaptive Weighting with Data Collected from Contextual Bandits: https://arxiv.org/abs/2106.02029 
o	Statistical Inference with M-Estimators on Adaptively Collected Data: https://arxiv.org/abs/2104.14074 

Empirical Evaluation
-	The Figure 1 plots are quite difficult to interpret, what do the colors mean? What are the different settings you consider? How do you compute standard errors?
-	In your empirical evaluation you have T=10000, it is unclear how your method performs in smaller sample settings, which is commonly the case in real world problems. 
-	How is the empirical performance of your estimator affected if the model Q does not converge to the true value (if at all)?
-	Are there any limitations or downsides of your approach empirically due to the large number of terms that must be plugged-in?

Additional Questions
-	Line 80: You define g^*, but in the equation above you use g. Is this intentional?
-	Theoretically / in practice do we expect Assumption 4 to hold?

limitations_and_societal_impact: See above comments.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper is motivated by the fact that no asymptotically normal estimators exist when the data is collected context-dependent adaptively. This work provides such estimators (named CADR, Algo. 1) exhibiting asymptotic normality (Thm. 1). 
main_review: This paper is motivated by the fact that no asymptotically normal estimators exist when the data is collected context-dependent adaptively. This work provides such estimators (named CADR, Algo. 1) exhibiting asymptotic normality (Thm. 1). 

This paper is based on the solid theoretical foundation and sophisticated observation that asymptotically normal estimators have only been developed under a non-contextual adaptive setting. This observation came as a surprise to me because the contextual adaptive setting is quite practical, but we still don't have a good estimator on it. Theories are strong, and experiments corroborate with the theory. 

Here are some points that I'd like to ask for authors to help readers' understanding a bit more. 
* C1. Line 30-32 — "However, due to the adaptive nature of the data collection, unlike classic randomized trials, standard estimates and their confidence intervals actually fail to provide correct coverage" seems to be a key motivation of the paper. I think it should be more enlightened to make readers motivated.

* C2. Line 62-72. It would be helpful if you could provide a graphical representation (i.e., DAG) for encoding the assumption, such as "Xt is independent of all else given A(t)." This would help to be more explicit and automatically tell some questions such as "What is all-else in the assumption"? 

* C3. Line 110-117. Can you formalize this observation with some examples? Despite the importance of this paragraph (this paragraph gives the very motivation of this work), explanations seem weak. 

I have one question about this work. 
* Q1. In Algo. 1, did you use sample-splitting (or cross-fitting) technique? If not, does the result still hold? 


limitations_and_societal_impact: Yes. Assumptions are written in explicit and transparent manner. Still, I think it'd be more helpful if authors can provide a DAG representation for encoding the dependency assumption in Line 62-72.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This study proposes a variance-stabilized estimator for policy evaluation from data obtained from contextual bandit algorithms, which is inspired by [Luedtke and van der Laan 2016]  and [Hadad et al. 2019].  In this study, the authors estimate the variance of the score function (canonical gradient) from samples, which standardizes the MDS for applying martingale CLT.
[Luedtke, and van der Laan 2016] Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy  
[Hadad et al 2019] Confidence Intervals for Policy Evaluation in Adaptive Experiments.
main_review: I vote for clear reject.  
I appreciate that this problem tackles a mathematically challenging problem.  
Also, there is not enough of a survey of the bandit problem, and it is not clear under what circumstances the proposed method would be needed.  
Although the authors do not mention it much, several methods of statistical inference from contextual moon bandits have already been proposed.  
Compared with them, I consider that the authors' method aims to enable statistical inference in more difficult situations.  
However, for me, it seems that it is unnecessary for the bandit problem, that is, there is a few concrete examples of a bandit algorithm in which the proposed method is needed.  
Furthermore, Assumptions 5 and 6 restrict the logging policy (sampling strategy of bandit algorithm), and it is not clear what specific bandit algorithms satisfy these assumptions.  
In addition, the essential contribution of this paper seems to be the proof of Theorem 2 (other parts have already been known).   
However, the notation is complicated, and there are some omissions and typos, so I could not check it sufficiently.   
The inability to read the proofs is partly my problem and partly due to the time constraints of the conference review process, but I also think that the authors could make an effort to make the proof more readable.  
In order to increase the score, the authors need to 
- explain the connection with existing studies of the "bandit problem" or change the field that the authors want to contribute.
- make proofs and notations easier to read.  
Detailed comments are listed below.

# Major concerns
I have three major concerns for this paper: 
- Point 1: lack of connection to bandit problem and the usefulness of the proposed methods.
- Point 2: theoretical correctness and implicit restriction to the bandit algorithms;
- Point 3: the setting of the experiment may not be appropriate.
Among them, I am particularly concerned with Point 1, that is, the proposed method is not designed for the bandit problem.

## Point 1
### Existing studies
The paper does not cite much of the bandit literature, and it is not clear how the proposed method can be applied.  
In addition, there are also several studies on evaluation from data gathered from adaptive experiments (including bandit algorithms) although not cited in this paper.  
For example,  
[van der Laan 2008] The Construction and Analysis of Adaptive Group Sequential Designs  
[Hahn et al 2011] Adaptive Experimental Design Using the Propensity Score  
I think that the following papers also propose such methods.  
[van der Laan and Lendle] Online Targeted Learning   
[Chambaz et al. 2014] Targeted Covariate-Adjusted Response-Adaptive LASSO-Based Randomized Controlled Trials  
[Tabord-Meehan 2020] Stratification Trees for Adaptive Randomization in Randomized Controlled Trials  
I can list other more studies tackling this problem.  

Some of these studies assumes that the contextual policy $g_t(a | x)$ converges to a time-independent measure and $g_t(a| x)\neq 0$.  
This is a natural assumption for some bandit problems (but not for regret minimization).    
Under this assumption, we can obtain asymptotically normal estimator with a simpler form, such as the IPW (IPS) estimator without the variance-stabilization.

In situations where the data is in batch form, statistical inference also can be performed even if the policy does not converge.  
[Zhang et al 2020] Inference for Batched Bandits  
This is essentially a generalized method of moments (GMM).
(Although it is not well known, a GMM estimator is known to have asymptotic normality for martingales)

Compared to these uncited previous studies, I cannot understand how useful the proposed method is to the bandit community.  
In addition, as described below, I cannot think of a specific bandit case where this proposed method would be necessary.  
 
### Variance-stabilized estimators and fewer applications in bandit problem
I consider that the contribution of this study lies in avoiding sample splitting, which (I think) is used in [Luedtke, and van der Laan 2016] and [Kato 2020], to obtain $\sqrt{N}$-consistent estimator.  
[Kato 2020] Confidence Interval for Off-Policy Evaluation from Dependent Samples via Bandit Algorithm: Approach from Standardized Martingales  
By using sample splitting, we can show asymptotic normality without making assumptions about the contextual policy.   
Instead, with that sample split, it is no longer $\sqrt{N}$-consistent.  
Recently, [Hadad et al 2019] proposed a method for statistical inference from a bandit data without context, which attains  $\sqrt{N}$-consistency.  
It can avoid estimation of the variance by considering bandit problem without context.  
In this study, the authors do not use sample-splitting and obtain a  $\sqrt{N}$-consistent estimator.  

However, I believe that these methods are essentially unnecessary for the bandit problem, and a simpler estimator is sufficient.
The reasons for this are listed below.
- If the logging policy converges, asymptotic normality can be obtained using other simpler estimators, such as IPW (IPS) estimators without using the methods of [Hadad et al 2019] or [Luedtke, and van der Laan 2016].  
- These papers presume stochastic bandit problem, but it is difficult to find a bandit algorithm, where the logging policy does not converge. 
- None of [Hadad et al 2019] or [Luedtke, and van der Laan 2016] can be used for the regret minimization, where the logging policy converges to zero. (In this case, the cannonical gradient diverges).
- In bandit problems, the target policy (denoted by $g^*$ in this paper) to be evaluated is also time-dependent, and there is no problem setting in which a time-independent target policy exists in advance and it is evaluated.  
I also think that [Luedtke, and van der Laan 2016] and [Hadad et al 2019] consider a different situation from bandit problem.  

### Lack of connection to bandit problem
I explain this in more details.  As well as [Luedtke, and van der Laan 2016] and [Hadad et al 2019],  the proposed method is needed if a bandit problem satisfies the following situations:
1. Bandit model is stochastic bandit (so not adversarial bandit);
2. The goals is not regret minimization (logging policy does not converges to $0$ or take $0$ value);
3. The policy (sapling strategy) does not converge;  

If not 1., we cannot assume the data generating process and define the causal effect.  
If the bandit algorithm aims to minimize the regret, the canonical gradient will diverge.  
(Variance also becomes $\infty$. Exclusion of regret minimization is Asssumtpion 6?)   
The authors raised a problem that "IS ratios can both diverge to infinity or converges to zero" in line 114.   
If the IS ratios really diverges, we cannot define the variance.  
To avoid this problem, we need to carefully restrict the class of the logging policy.  
For instance, [Hadad et al 2019] also restricted the class in their Assumptions 1--3.  
In this paper, it seems that Assumption 5 corresponds to the  Assumptions 1--3 of [Hadad et al 2019].  
Can the authors show the method of Li et al 2010, Kallus and Udell 2020, Qiang and Bayati 2016 etc, which the authors cited in Introduction, satisfy these conditions?    
In contrast, if the sampling strategy converges, we do not have to use variance stabilization.   
For instance, the IPW (IPS) estimator $y/ g(a| x)$ also have asymptotic normality owing to the martingale property.  
(In this paper $\hat{\Psi}^{IPS}$ without variance stabilization. Without variance stabilization, this type of estimator is often used.)

In addition,   
 4. The authors also seem to restrict the sampling strategy (logging policy) in Assumption 5.  
This is a specific assumption of this paper to show Theorem 2.  
What kind of bandit algorithms satisfy this assumption?   
In bandit literature, this kind of assumption is carefully discussed in the paper.  
For instance, the following paper considers a nonparametric method for regret minimization with carefully restricting the class of sampling strategy.   
[Yang and Zhu 2002] Randomized Allocation with nonparametric estimation for a multi-armed bandit problem with covariates  
Thus, I think that Assumption 5 (and 6) is not trivial, and the authors should discuss more carefully.  

In conclusion, I do not know whether there is a bandit problem where the proposed method is needed.  
This is not to deny the author's attempt, but if the author thinks the proposed method is necessary for bandit problem, I would like to know the specific bandit paper.  
The paper cites some papers in the field of adaptive experimental design and causal inference, but not many of papers in bandit problem, which is main topic of this paper.   
There are several cited papers, but I think that all of them converge on the sampling strategy or do not satisfy Assumption 5--6,.    
That is, the authors should motivate the proposed method more from the viewpoint of bandit algorithms.    
Otherwise, the authors should change the field that they want to contribute.   
I believe that the current structure of the paper, if accepted, will confuse the bandit community.  

## Point 2:
### Assumption 5 and 6
As pointed in Point 1, Assumption 5 and 6 restrict the logging policy. 
These assumptions should be more paid attention because it is closely related to design of the bandit algorithm. For example, [Yang and Zhu 2002] more carefully discuss the assumption.  
In addition, the authors should cite an example of bandit algorithm satisfying these assumptions.  
(But the logging policy does not converge. As mentioned above, if it converges, we do not have to use the proposed method)  

### Proof of Theorem 2
I think that Theorem 2 is the most important in this paper.
Because if we use sample splitting, we can show the asymptotic normality more easily by losing the $\sqrt{T}$-consistency for a sample size $N$ ([Luedtke, and van der Laan 2016]).  
However, owing to the difficulty of the notations, we cannot fully understand the proof.  
Could the authors answer the following questions?
- Does line (6) of $\ell 571$ in supplementary material is MDS?
The authors may omit $g_t$, but I think $g_t$ is correlated with past samples. Does it satisfy MDS?
- Do we need to assume boundedness or sub-gaussian to the outcome $Y$?
- If we do sample splitting, can't we prove asymptotic normality without assuming Assumptions 5 and 6, instead of losing $\sqrt{N}$-consistency? [Luedtke, and van der Laan 2016] and [Kato 2020] (I think this paper is essentially same as [Luedtke, and van der Laan 2016]) do this?   
If sample splitting can solve the problem, the authors should explain this fact even if they are inferior to the proposed method in the sense of $\sqrt{N}$-consistency?  

## Part 3
In experiments, the logging policy seems to converge.  
If so, we do not have to use the proposed variance stabilization and obtain asymptotic normality with simpler estimators proposed in existing studies.  
In addition, If so, the authors should change the setting of experiments.  

# Minor points
- As pointed in Part 1, there are many methods for causal inference from contextual experimental designs in situations where the logging policy converges, but they are almost never cited.
- I am a bit familiar with this notation, so I could read it, but this notation would be very difficult for machine learning people to read. More explanation of terminology is needed, since prior knowledge differs between the bandit and causal inference communities.
- The notation in this paper is difficult and the proof is very hard to read. I don't mind that the proof is difficult, but there are many notations that are not explicitly defined, making it difficult to read. In addition, there are typos in some places.  
- Assumption 5 constrains the behavior of the original Bandit algorithm. However, if we are going to put constraints on the algorithm, why not design the algorithm so that it is easy to evaluate measures?   

# Requirements to the author
I would require the authors to answer the following point
- Raise an example of a situation of bandit problems, where this algorithm is needed, with justifying Assumption 5 and 6;
and improve following points in the next revision:
- Reorganization of Notation;
- Another experiment using  logging policy that needs the proposed method;
- A better literature review.
limitations_and_societal_impact: This paper does not describe a specific bandit algorithm, where the proposed method can be applied.   
As pointed in Main review, there are three possible settings for the bandit problem settings:
- regret minimization: Cannot be applied to regret minimization where the variance of the IPW part jumps infinitely (Assumption 6?).
- best arm identification: There is no generally accepted research on contextual best arm identification.
- adversarial bandit: This is not the data generating process considered in this paper.
I do not believe the proposed method can be used for any of these.  

In addition, for example, in a problem where the logging policy converges and does not take $0$ value, the IPW (IS) estimator is sufficient without the proposed method.   
The authors state that IPW (IS) estimators "are (not) generally asymptotically normal under adaptive data collection" (line 253), but this is not true. (line 253) because if the logging policy converges, the IPW estimator will asymptotically follow normality by the martingale CLT.   
The authors also pointed out the problem that the logging policy take $0$.  
Indeed, under this situation, the IPW (IS) estimator cannot be used, but the proposed method also cannot be used (Assumption 6).  
After all, the authors have made (implicit) assumptions on the sampling strategy, and they should discuss whether those assumptions are more valid than other assumptions.

Moreover, in the setting of the experiment, it appears that the authors consider a problem where the logging policy converges.  
So, I think that the authors do not have to use their proposed method to obtain asymptotic normal estimator.  
If my comment is incorrect, the authors should clarify this in the paper.
review_title: null

Meta-review: Thank you to the authors and the reviewers for their contributions! There was a long discussion on this paper, and we sought external opinions to add clarifications. The final consensus is that the paper makes an interesting technical contribution to the literature on inference over adaptively collected data, specifically via contextual bandits. However, the paper is not very clear in terms of its key results and their limitations, and I urge the authors to clarify the exposition in the next version. Key issues have already been noted in the discussion period; one reviewer also specifically requested clarifications on whether Assumptions 5 and 6 hold in the experiments (i.e., whether the \epsilon is decaying too fast) or to adapt the experiment parameters accordingly.
Decision: Accept (Poster)