Distributionally Robust Policy Learning under Concept Drifts

We would like to thank the reviewer for dedicating the time to review our paper and for providing the insightful comments. Due to the character limit, we cannot upload the revised manuscript, however we have edited according to the reviewer's helpful suggestions. Reference can be found in our reply to Reviewer wdwV.

Claims And Evidence

1 To our best knowledge, context shift and concept shift are two big sources of out of distribution data. In our setting, we are concerned with concept shift dataset, i.e. OOD data such that the distribution of $Y|X$ in testing data is shifted from that in training data. In the quoted sentence, we are discussing the other case of context shift, where the distribution of $X$ in testing data is shifted from that in training data, with the conditional reward $Y|X$ distribution unchanged. Please let us know if we have misunderstood your question.

In our revision, we have extended our framework to incorporate context shift. One can find that the policy value in this case is $\mathcal{V}\_{\delta}(\pi) = -\mathbb{E}\_{P}[r(X)(\alpha^*_\pi(X)e^{-\frac{Y(\pi(X))+\eta^*_\pi(X)}{\alpha^*_\pi(X)}-1}+\eta^*_\pi(X)+\alpha^*_\pi(X)\delta)]$, where $r(x)=\frac{P'_X}{P_X}$ with $P'_X$ being the shifted context distribution. Here, we make a conscious choice to estimate the context shift (as opposed to hedge again the worst-case shift) because in most practical situations, users have access to the covariates in the target environment and the context shift is identifiable and estimable; it is thus unnecessary to guard against the worst-case shift. We have added this extension to our manuscript.

2 Thank you for your question. The concept-shift setting is one of the major differences: we aim at providing a better solution to DRO policy learning when knowing additionally the type of distribution shift. Such a change of objective brings substantial technical challenges, which are what we have addressed in this paper.

Except for the differences in settings, [1] assumes a known behavior policy $\pi_0$ (and thus known propensity score), while our setting allows for an unknown $\pi_0$, which adds new challenge as slow estimation rates of the propensity score could result in high regret bound. We note that unknown $\pi_0$ setting is ubiquitous in observational studies [9]. This challenge calls for regression methods for fitting $\pi_0$ and an intricate design of empirical risk minimization (ERM) method, combined with a double-robust construction, in our work to compensate for the unknown $\pi_0$. In spite of all these challenges, we managed to show theoretically and empirically that, if only concept shift takes place, then employing [1] is suboptimal, and our algorithm does better with this one bit of extra information. We have added this comparison to our literature review section.

In terms of theoretical analysis, we adopt the chaining technique to achieve a regret rate of $O(n^{-1/2})$, while [1] uses a quantile trick.

3 Thank you for your question. To learn a near-optimal policy that maximizes the distributionally robust value $\mathcal{V}\_{\delta}(\pi)$ from a dataset, a consistent (i.e. asymptotically normal) estimator of $\mathcal{V}\_{\delta}(\pi)$ is a necessary intermediate step to achieve good quality learning. Asymptotic normality allows for inference on the policy value (e.g., constructing confidence intervals, conducting hypothesis testing). In terms of the variance of the proposed value estimator, asymptotically the variance is $\sigma_\pi^2$ as stated in Theorem 3.5. This is to say that the bias is asymptotically 0, given consistent nuisance parameter estimators. The non-asymptotical bias contributed by each nuisance parameter estimator is carefully analyzed in Appendix D.2, proof of Theorem 3.5.

Other Comments Or Suggestions

1 See Claims and Evidence 2

2 Hamming entropy integral is a variant of the classical entropy integral introduced in [10], based on the Hamming distance, which is a well-known metric for measuring the similarity between two equal-length arrays (policies in our context) whose elements are supported on on discrete sets. Hamming entropy integral is widely used in offline learning literature [1-4] for measuring the complexity of a policy class. Details and examples can be found in [1].

We would like to thank the reviewer for dedicating the time to review our paper and for providing the insightful comments. Due to the character limit, we cannot upload the revised manuscript, however we have edited according to the reviewer's helpful suggestions. Reference can be found in our reply to Reviewer wdwV.

Claims and Evidence

1&2 We would like to first note that our work does not assume known context distribution $P_X$. We only assume that no covariate shift takes place (which has been relaxed in our revision), and we aim to learn an optimal policy that is robust to any shift of $P_{Y\mid X}$ within the $\delta$ KL-divergence. The setup is similar to the setting of [2], with the latter focusing on a finite covariate space.

We also note that the per-x optimization formulation proposed your comment 1 itself is highly challenging when $X$ has continuous components and/or is high-dimensional ---indeed, it then requires to evaluate $\mathbb{E}[Y | X=x]$ for each $x$. At a high level, this is the challenge our work addresses.

In our revision, we have extended our framework to incorporate context shift. One can find that the policy value in this case is $\mathcal{V}\_{\delta}(\pi) = -\mathbb{E}\_{P}[r(X)(\alpha^*_\pi(X)e^{-\frac{Y(\pi(X))+\eta^*_\pi(X)}{\alpha^*_\pi(X)}-1}+\eta^*_\pi(X)+\alpha^*_\pi(X)\delta)]$, where $r(x)=\frac{P'_X}{P_X}$ with $P'_X$ being the shifted context distribution. Here, we make a conscious choice to estimate the context shift (as opposed to hedge again the worst-case shift) because in most practical situations, users have access to the covariates in the target environment and the context shift is identifiable and estimable; it is thus unnecessary to guard against the worst-case shift. We have added this extension to our manuscript.

3 As discussed in our previous reply, we do not assuming knowing $P_X$ and solving the per-$x$ optimization problem is challenging with continuous and/or high-dimensional $X$---this is where the curse of dimensionality kicks in (think of the task of estimating conditional mean).

We also note that Assumption 3.4 is standard in offline learning literature [1,2,3,4,5]. The empirical sensitivity analysis of Assumption 3.4 can be found in [7] which justifies it. The results in [7] also parallels standard conditions in double-machine-learning, achievable by a variety of machine-learning methods [6].

Methods And Evaluation Criteria: We are now running a new set of experiments with real-world dataset, which will be ready before the camera ready version.

Theoretical Claims: The optimality of our regret bound is verified by our lower bound result of $\Omega(n^{-1/2})$ in Theorem 4.6. In terms of results in literature, our setting is similar to that of [2], however [2] only considers discrete $P_X$ with finite support, while we extend the case to continuous unknown $P_X$ with infinite support. We also improve the regret bound of in [2]. Please see table 1 for an overview of results in literature and our results.

Relation To Broader Scientific Literature: Concept shifts occurs in many real-world situations. For example, in advertising, the customer behavior can evolve over time as the environment changes, while the population remains largely the same. In personalized product recommendation, similar population segments in developed and emerging markets may prefer different product features.

Most existing robust policy learning algorithms model joint distributional shift without distinguishing the sources. The suboptimality of these algorithms under concept shift is because the worst-case distributions under the joint-shift model and the concept-drift model can be substantially different, so it would be a “waste” to consider joint shift under concept drift. With one extra bit of information, our work shows that we can obtain a better policy. The above discussion was already in our introduction, but we expanded it in our revision.

We would like to thank the reviewer for dedicating the time to review our paper and for providing the insightful comments. Due to the character limit, we cannot upload the revised manuscript, but we have edited according to the reviewer's helpful suggestions. We use the following references.

[1] Si, N., Zhang, F., Zhou, Z., and Blanchet, J. Distributionally robust batch contextual bandits. Management Science, 2023.

[2] Mu, T., Chandak, Y., Hashimoto, T. B., and Brunskill, E. Factored dro: Factored distributionally robust policies for contextual bandits. Advances in Neural Information Processing Systems, 35:8318–8331, 2022.

[3] Athey, S. and Wager, S. Policy learning with observational data. Econometrica, 89(1):133–161, 2021.

[4] Zhou, Z., Athey, S., and Wager, S. Offline multi-action policy learning: Generalization and optimization. Opera- tions Research, 71(1):148–183, 2023.

[5] Kallus, N., Mao, X., and Uehara, M. Localized debiased machine learning: Efficient inference on quantile treatment effects and beyond. arXiv preprint arXiv:1912.12945, 2019.

[6] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. 2018. Double/debiased machine learning for treatment and structural parameters. Econometrics Journal 21, 1 (2018), C1–C68.

[7] Jin, Ying, Zhimei Ren, and Zhengyuan Zhou. "Sensitivity analysis under the f-sensitivity models: a distributional robustness perspective." arXiv preprint arXiv:2203.04373 (2022).

[8] Kallus, Nathan, and Angela Zhou. "Policy evaluation and optimization with continuous treatments." International conference on artificial intelligence and statistics. PMLR, 2018.

[9] Rosenbaum, P.R. (2002). Observational Studies. Springer Series in Statistics. Springer, New York, NY.

[10] Dudley, Richard M. "The sizes of compact subsets of Hilbert space and continuity of Gaussian processes." Journal of Functional Analysis 1.3 (1967): 290-330.

Weakness

1 See Question 1

2 Thank you for your helpful comments. The ERM step follows from standard duality results in the DRO literature. To improve readability, we have added a detailed explanation of the ERM derivation in our manuscript. With an empirical dataset, it is natural to propose an ERM solution based on the loss function inspired by the strong duality result in Lemma 2.3.

3 A potential drawbacks in our framework (as well as in other distributional robust optimization works) is the choice of $\delta$. The parameter $\delta$ controls the size of the uncertainty set considered and thus controls the degree of robustness in our model --- the larger $\delta$, the more robust the output. The empirical performance of the algorithm substantially depends on the selection of $\delta$. A small $\delta$ leads to negligible robustification effect and the algorithm would learn an over-aggressive policy; a large $\delta$ tends to yield more conservative results. A more detailed discussion can be found in [1]. We have incorporated the above in the revision.

Comments and Suggestions

1 In terms of cross-fitting and de-biasing technique, we have added more detailed explanation in our manuscript.

2 In our simulation, we set $K=3$, which is the minimal number of splits possible, and the default spline threshold at 0.001 without fine-tuning. Under this default choice, we see that the algorithm already performs well. Increasing $K$ and decreasing the spline threshold would increase the computation complexity.

3 In real-world applications, knowing the source of the distribution shift effectively shrinks the uncertainty set, thereby yielding less conservative results (compared with the joint modeling approach). Moreover, since in most cases, practitioners have access to the covariate in target environment, it is then possible to identify and estimate covariate shifts: when the decision maker observes none or little covariate shifts and would like to hedge against the risk of concept drift, it is suitable to apply our method which outperforms existing method designed for learning under joint distributional shifts. We are now applying our method to a real dataset, which would be ready before camera ready version.

See Question 2 for generalization to continuous action space.

Questions

1 The rate Assumption 3.4 is standard in literature [1,2,3,4,5]: it suffices to have $o_P(n^{-1/4})$-rates on all nuisance parameters or no rate on $\hat{g}_\pi$ at all if $\pi_0$ is given. This assumption also parallels standard conditions in double-machine-learning, achievable by a variety of machine-learning methods [6]. The empirical sensitivity analysis can be found in [7] which justifies Assumption 3.4. We have added this discussion to our manuscript.

2 We agree with the reviewer that it might be possible to apply our ERM approach to the continuous action space extension, however the problem setting would deviate from the current discrete case, as discussed in [8]. We leave this for future works.