Off-policy estimation with adaptively collected data: the power of online learning

We thank the reviewer for the detailed reviews. Below are point-by-point responses. We hope the reviewer can increase the score if our responses address your concerns.

1. Re "There is significant missing discussion of relevant related work on finite sample approaches for off policy evaluation in contextual bandits."

Thank you for the suggested related works. We will discuss these in our paper. Our main goal is different from the suggested papers. The first two papers focus on constructing confidence intervals (or sequences) for the off-policy value, while our objective is in estimation of the off-policy value. The last paper (which we have cited in the paper) focuses on OPE with i.i.d. data, while our work focuses on OPE with adaptively collected data.

Even if we translate the confidence intervals to prediction (in some way), it is hard to compare theoretically as no specific rate is provided for the confidence intervals in the paper “Anytime-valid off-policy inference for contextual bandits” by Waudby-Smith et al. Nevertheless, their methods are interesting, and we will try to compare our method with them empirically.

2. Re "The main result which holds for general plug-in estimators of the mean reward function."

We note that our main results (Theorems 3.1 and 3.2) hold in general: Theorem 3.1 holds for any sequence of estimates of the treatment effect, and Theorem 3.2 holds for estimates of the treatment effect resulting from any no-regret learning algorithm. Theorems 3.3 and 3.4 are just two examples (i.e., corollaries) of Theorem 3.2 to demonstrate how to apply the framework of online learning for some concrete classes of outcome models. We also provide results for the case of general function approximation in Appendix B.6 that goes beyond the two examples on the tabular setting and linear designs (i.e., the case of linear function approximation).

3. Re "The main results presented in this paper assume that the behavioral policies have constant exploration rates (Assumption 1)."

Similar to the response above, the strict overlap condition (Assumption 1) is imposed in the examples (Theorems 3.3 and 3.4, and Appendix B.6) of one of our main results---Theorem 3.2. Theorem 3.2 itself is applicable to cases with decaying exploration rates, but for simplicity we didn’t pursue this in this work. We leave this point as future work.

4. Re "The writing is technically precise, but extremely dense and often lacks sufficient context. "

Thanks for the critique. We will revise the submission accordingly. Here, we give some clarifications on the terminologies “treatment effect” or “mean reward function.” These two terminologies are used separately in two communities: causal inference, and bandits and reinforcement learning. They can be related as seen in line 111 of our paper. This choice of terminology also aligns with a prior work “Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency” by Mou et al.

5. Re "A severe limitation of this work (especially compared to the existing literature) is that the authors only provide guarantees about the mean-squared error."

We cannot agree with the reviewer on this point. We view the estimation task as equally important as uncertainty quantification (e.g., constructing confidence intervals) from both theoretical and practical perspectives. Moreover, our proposal, the doubly-robust (DR) estimator using an online learning algorithm as a sub-routine, is new to the literature, and practically useful.

6. Re "There are no simulation results demonstrating their approach in practice or comparing against the other methods in the literature."

We provided preliminary experimental results to corroborate our theory. Please check the attached PDF file. We mostly followed the experimental set-up in the paper “Off-policy evaluation via adaptive weighting with data from contextual bandits” by Zhan et al. Our DR estimator using an online learning algorithm as a sub-routine performs competitively against other estimators, while at the same time enjoying provable finite-sample performance guarantees. We will add more numerical simulation results to understand the pros and cons of each estimator.

We thank the reviewer for the suggestions. Below are the point-by-point responses. We hope the reviewer can increase the score if the weakness listed in the review has been improved.

1. Re "it would be helpful if the authors could include some simulation experiments to verify the theoretical results."

We provided preliminary experimental results to corroborate our theory. Please check the attached PDF file. We mostly followed the experimental set-up in the paper “Off-policy evaluation via adaptive weighting with data from contextual bandits” by Zhan et al. Our DR estimator using an online learning algorithm as a sub-routine performs competitively against other estimators, while at the same time enjoying provable finite-sample performance guarantees. We will add more numerical simulation results to understand the pros and cons of each estimator.

2. Re "It would be beneficial if the authors could provide more detailed explanations regarding certain definitions."

2.1. Our formulation of the off-policy value using the inner product between the treatment effect $\mu^*$ and the evaluation function $g$ is versatile: As elucidated in lines 109~121 in our paper, our definition of the off-policy value in the equation (1) recovers several important quantities of interest including the average treatment effect (ATE) or its weighted variants and the value function in contextual bandits.

2.2. The perturbed IPW estimator reduces the variance of the standard IPW estimator. This can be observed from Proposition 3.1 in our paper. With a proper choice of the collection of auxiliary functions $f$, the perturbed IPW estimator has smaller variance.

3. Re "Could the authors compare the results for i.i.d. data with those for adaptively collected data?"

As seen from both the upper bounds and lower bounds, the main difference lies in the measure of the size of noises: see the equations (7) and (2) in our paper. In an adaptive data collection model, the weighted $\ell_2$-norm of the noise depends on time-varying history-dependent behavioral policies, while in the i.i.d. data collection model, the weight is fixed over time and history-independent: see the paper “Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency” by Mou et al.

We thank the reviewer for the comments. Below are our point-by point responses to better position our paper and explain our contributions. We hope the reviewer can increase the score if the confusion about the paper and its contributions has been resolved.

1. Re "I am confused about the claim of "adaptive" and "online learning" in the title."

a) Why "adaptive" in the title? We focus on off-policy evaluation (OPE): the problem of estimating the value function based on an offline dataset. In OPE, the word “adaptive” means that in the offline dataset, the actions could be adaptively chosen based on previous samples. This is in contrast to OPE with i.i.d. dataset in which actions are drawn depending only on the current context.

b) Why "online learning" in the title? We use an “online learning” algorithm (or a no-regret learning algorithm) to iteratively learn the treatment effect function, and then use them in forming the AIPW estimator to solve the OPE problem; see Algorithm 1 in the paper. This is also different from OPE with i.i.d. dataset in which an “offline learning” algorithm such as the empirical risk minimization (ERM) is applied to learn the treatment effect. This gives rise to the term “the power of online learning” in the title.

2. Re "the technical distinction between the sequential decision setting and static setting is not clearly presented."

We hope the response above has already resolved some confusion about sequential vs static. We expand a bit on the challenge and our contributions here.

We view OPE as a static decision-making problem as the pre-collected offline dataset is already provided to the learner, and the learner's goal is to estimate the off-policy value. The major challenge here is that the offline data is adaptively collected, that is, in the sequence of observations of the form (context, action, outcome), the actions can be chosen depending on previous data. Focusing on OPE with adaptively collected data, we investigate finite-sample guarantees of the class of AIPW estimators, propose a specific AIPW estimator with a sequence of estimates of the mean reward function learned via an online learning algorithm, and show its near-optimality in a minimax sense. All of these are new to the literature.

3. Re "The formulation of the perturbed IPW estimator in Section 3.1 seems to be different from the doubly-robust (DR) estimator. "

The AIPW estimator (i.e., the DR estimator) is a special case of the perturbed IPW estimator with the collection of auxiliary functions $f^*$ takes form as the equation (5) in our paper, and the treatment effect $\mu^*$ is replaced by its empirical estimates. This will yield the DR estimator (cf. Eq (1)) in the paper “Doubly robust policy evaluation and learning” by Dudik et al.