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

Summary

This paper presents an approach to estimating linear functionals of the reward function in contextual bandit settings from adaptively collected data. They consider the class of augmented inverse propensity weighted (AIPW) estimators and prove guarantees about the quality of the estimator in terms of the quality of the plugin estimator of the mean reward. Specifically, they characterize the finite sample MSE of the AIPW estimator on adaptively collected data. They quality of the estimator (in terms of low MSE) depends on the quality of the plugin estimator of the mean. They relate online learning of the plugin estimator of the mean reward to online non-parametric regression; they then prove a regret bound, where regret relates to the quality of the plug-in estimator learned online. ***edited score based on rebuttal. See comment below***

Strengths

This paper's presentation is technically precise and seems mathematically thorough. The author's approach of relating the estimation problem online learning seems interesting and creative.

Weaknesses

- There is significant missing discussion of relevant related work on finite sample approaches for off policy evaluation in contextual bandits. For example "Anytime-valid off-policy inference for contextual bandits" by Waubly-Smith et al., "Off-Policy Confidence Sequences" by Karampatziakis et al. and "Optimal and Adaptive Off-policy Evaluation in Contextual Bandits" by Wang et al., as some examples. I would recommend the authors compare to these papers both theoretically and ideally experimentally as well. - The main result the authors present that holds for general plug-in estimators of the mean is the derivation of the MSE upper bound for the AIPW estimator (Theorem 3.2) as a function of the "regret" of the plug-in estimator error. Beyond this the authors provide results for the plug-in estimators in tabular data settings (Theorem 3.3) and plug-in estimators that are linear models (Theorem 3.4). I feel this is a limited contribution in terms of the types of plug-in estimators the authors can provide guarantees for. - The main results presented in this work assume that the behavior has a constant exploration rate (Assumption 1). Other works on statistical inference after adaptive sampling generally can prove results when the exploration can decay. - The writing is technically precise but extremely dense and often lacks sufficient context. I give explicit examples below: (-) The final result in section 4 was extremely hard to parse. There is a mention of "mis-specification" in the section 4.1 title, but then there is no mention of mis-specification anywhere in the section itself. It is not easy to understand how the result presented in that section is related to mis-specification. (-) There was little discussion as to why the pertubed IPW estimator was introduced in section 3.1, rather than just starting with the AIPW estimator in 3.2 (since there were no examples discussed of the perturbed IPW estimator that were not some version of an AIPW estimator). Furthermore, if the discussion in 3.1 is kept, the connection between these two estimators presented in 3.1 and 3.2 respectively needs to be made more explicitly. For example, explicitly relating AIPW if for a certain choice of $f$ these two estimators are the same.

Questions

- In line 97, I do not understand why $\mu$ is called a treatment effect. It is also called the "reward model" and appears to be the expected reward function (function of context and action). Why is this called a treatment effect? This is not what is "commonly referred to" as a treatment effect in the causal inference literature. - In line 107 you state that its assumed the propensities are "revealed", does this mean known? - Please define << notation used in 117

Rating

5

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

- A severe limitation of this work (especially compared to previous literature) is that they only provide guarantees about the mean squared error of the AIPW estimator and do not provide any approach to constructing confidence intervals for the quantities of interest. I would expect most people interested in using statistical inference methods on adaptively collected data (especially if data is small enough to warrant using a linear plug-in model or be in a tabular data setting) would care solely about estimation and not uncertainty quantification. As a result, the practical utility of this work is very limited. - There are no simulations demonstrating their approach in practice or comparing to other methods.

Summary

The paper investigates the challenge of estimating a linear functional of the treatment effect from adaptively collected data, commonly found in contextual bandits and causal inference studies. It introduces finite-sample upper bounds for the mean-squared error (MSE) of augmented inverse propensity weighting (AIPW) estimators and proposes a reduction scheme to minimize these bounds. The method is illustrated through three concrete examples. Additionally, the paper establishes a local minimax lower bound, demonstrating the instance-dependent optimality of the AIPW estimator.

Strengths

- The paper extends the non-asymptotic theory of AIPW estimators to adaptively collected data. - The paper provides both an upper bound and a local minimax lower bound on the MSE of the off-policy value, which quantifies the similarity between a given target evaluation function $g$ and the treatment effect $\mu^*$.

Weaknesses

- Although the paper is primarily theoretical, it would be helpful if the authors could include some simulation experiments to verify the theoretical results. For example, it would be interesting to see how the regret converges in practice in the examples of Section 3.5. - It would be beneficial if the authors could provide more explanations regarding certain definitions. For example, the off-policy value is defined as the expectation of the inner product between $g$ and $\mu^*$, rather than, e.g., the expectation of $g$ itself. What is the rationale behind this definition? In addition, why is the perturbed IPW estimator considered over the traditional IPW estimator? - The paper has generalized the theory developed for i.i.d. data to adaptively collected data and discussed the technical difficulties in Section 3.2. Could the authors compare the results for i.i.d. data with those for adaptively collected data? Is there any efficiency loss when the data is collected adaptively?

Questions

See above.

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

Limitations have been discussed in the checklist.

Summary

This paper study the off-policy problem in the sequential decision setting with adaptively collected data. The authors propose to use augmented Inverse propensity weighting estimator to estimate the policy value and conduct extensive theoretical analysis on the estimator, including variance and mean square error. Based on the analysis, the authors propose the methods to learn the function estimator in AIPW estimators.

Strengths

This paper comprehensively analyze the property of the AIPW estimator, including the variance and MSE bound. Therefore, I think this is a theoretically solid paper. And the connection between theory and the method is smooth and well-grounded.

Weaknesses

I am confused about the claim of "adaptive" and "online learning" in the title. The two words seems that the decision-maker can adaptively select the action during the decision process. However, it seems that the record (context, actions, outcomes) are passively observed in the problem. So I concern that the paper may be mis-positioned. Therefore, the technical distinction between the sequential decision setting and static setting is not clearly presented. It seem to be a trivial extention of the traditional policy evaluations problem in the static setting.

Questions

The formulation of perturbed IPW estimator in section 3.1 seems different with the doubly robust estimator. Can the authors provide the connection between the perturbed IPW estimator and the doubly robust estimator in other papers. For example, the doubly robust estimators in [1]. [1] Miroslav Dudik, John Langford, and Lihong Li. 2011. Doubly robust policy evaluation and learning. In International Conference on International Conference on Machine Learning. 1097–1104.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

I think the discussion of the limitation in the paper is not sufficient.