Distributionally Robust Policy Learning under Concept Drifts
Authors: Jingyuan Wang
Zhimei Ren
Ruohan Zhan
Zhengyuan Zhou
Venue: ICML 2025 poster (2025)
Keywords: distributionally robust optimization
offline policy learning
concept drift
bandit learning
reinforcement learning.
Primary area: general_machine_learning->causality
TL;DR: We propose a minimax optimal offline policy learning algorithm that is robust under concept drifts.

Abstract: Distributionally robust policy learning aims to find a policy that performs well 
    under the worst-case distributional shift, and yet most existing methods for 
    robust policy learning consider the worst-case *joint* distribution of 
    the covariate and the outcome. The joint-modeling strategy can be unnecessarily conservative
    when we have more information on the source of distributional shifts. This paper studies
    a more nuanced problem --- robust policy learning under the *concept drift*, 
    when only the conditional relationship between the outcome and the covariate changes. 
    To this end, we first provide a doubly-robust estimator for evaluating
    the worst-case average reward of a given policy under a set of perturbed conditional distributions. 
    We show that the policy value estimator enjoys asymptotic normality even if the nuisance parameters 
    are estimated with a slower-than-root-$n$ rate.
    We then propose a learning algorithm that outputs the policy maximizing the 
    estimated policy value within a given policy class $\Pi$, and show
    that the sub-optimality gap of the proposed algorithm is of the order 
    $\kappa(\Pi)n^{-1/2}$, where $\kappa(\Pi)$ is the entropy integral of $\Pi$ under the Hamming distance
    and $n$ is the sample size. A matching lower bound is provided to show the optimality of the rate.
    The proposed methods are implemented and evaluated in numerical studies, 
    demonstrating substantial improvement compared with existing benchmarks.

Distributionally Robust Policy Learning under Concept Drifts
Jingyuan Wang'
Zhimei Ren
Ruohan Zhan Zhengyuan Zhou 14
Abstract
1. Introduction
In a wide range of fields, the abundance of user-specific historical data provides opportunities for learning efficient individualized policies. Examples include learning the op- timal personalized treatment from electronic health record data (Murphy, 2003; Kim et al., 2011; I; Chan et al., 2012), or obtaining an individualized advertising strategy using past customer behavior data (Bottou et al., 2013; Kallus & Udell, 2016). Driven by such a practical need, a line of works have been devoted developing efficient policy learning algorithms using historical data- a task often known as of- fline policy learning (Dudík et al., 2011; Zhang et al., 2012: Swaminathan & Joachims, 201 2a;b::; Kitagawa & Tetenov, 2018; Athey & Wager, 2021; Zhou et al., 2023; Zhan et al., 2023; Bibaut et al., 2021; Jin et al., 2021; 2022a).
Distributionally robust policy learning aims to find policy that performs well under the worst- case distributional shift, and yet most existing methods for robust policy learning consider the worst-case joint distribution of the covariate and the outcome. The unnecessarily conservative when we have more information on the source of distributional shifts. This paper studies more nuanced problem- ro- bust policy learning under the concept drift, when only the conditional relationship between the out- come and the covariate changes. To this end, we first provide a doubly-robust estimator for eval- uating the worst-case average reward of a given policy under set of perturbed conditional distri- butions. We show that the policy value estimator enjoys asymptotic normality even if the nuisance parameters are estimated with slower-than-ree n rate. We then propose a learning algorithm that outputs the policy maximizing the estimated policy value within a given policy class I1, and show that the sub-optimality gap of the proposed algorithm is of the order x(II)n 1/22, 11/2, where (III) is the entropy integral of II under the Hamming distance and is the sample size. A matching lower bound is provided to show the optimality of the rate. The proposed methods are implemented and evaluated in numerical studies, demonstrating substantial improvement compared with existing benchmarks.
strategy can be
Most existing methods for offline policy learning deliver performance guarantees under the premise that the target en- vironment remains the same as that from which the historical data is collected. It has been widely observed, however, that such condition is hardly met in practice (see e.g., Recht et al. (2019); Namkoong et al. (2023); Liu et al. (2023); Jin et al. (2023) and the references therein). Under distribu- tion shift, a policy learned in one environment often shows degraded performance when deployed in another environ- ment. To address this issue, there is emerging body of research robust policy learning, which aims at finding policy that still performs well when the target distribu- tion is perturbed. Pioneering works in this area consider the case where the joint distribution of the covariates and the outcome is shifted from the training distribution, and researchers devise algorithms that output a policy achieving reliable worst-case performance under the aforementioned shifts (Si et al., 2023; Kallus et al., 2022). The joint mod- eling approach, however, ignores the type of distributional shifts, and the resulting corst-case value can be unnecessar- ily conservative in practice.
'Stern School of Business, New York University 'Department of Statistics and Data Science, University of Pennsylvania 'IEDA, Hong Kong University of Science and Technology Arena Technologies. Correspondence to: Zhengyuan Zhou <chengyuanzhou24e aaaaaiannnnoo22eemmll....m... gma.
Indeed, distributional shifts can be categorized into two classes by their sources: (1) the shift in the covariate X, and/or (2) the shift in the conditional relationship between the outcome Y and the covariate X. The two types of distributional shifts are different in nature, have different implications on the objectives, and call for distinct treat- ment (Namkoong et al., 2023; Liu et al., 2023; Jin et al.,
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Distributionally Robust Policy Learning under Concept Drifts
Distribution shift
Unknown
General X
Upper bound
Lower bound
Athey & Wager (2021)
Zhou et al. (2023)
Si et al. (2023)
Joint
X
Kallus et al. (2022)
Joint
/
Mu et al. (2022)
Separate
x
olv
log i log (11))A)))
x
This work
Separate
Naiim (T)
Table Comparison of results in the offline policy learning literature. "Unknown mo" refers to whether an algorithm assumes knowledge of the behavior policy xo. "General X" refers to whether an algorithm allows for general types of covariates. Athey & Wager (2021), I); Zhou al. (2023); Si al. (2023); Kallus al. (2022) have the regret upper and lower bounds for the specific problems they consider that are not directly comparable to ours, so we do not include them in the table. | refers to the cardinality of the covariate support (if finite) and |A| to that of the action set. xIII) and Ndim (II) the entropy integral under Hamming distance and the Natarajan dimension of a policy class II, with the relation x(II)= (log (d) (d)ddi(())). where d is the dimension of the covariate space.
2023; Ai & Ren, 2024). To be concrete. imagine that the dis- tribution of covariates changes while that of Y X remains invariant - in this case, the distribution shift is identifi- able/estimable since the covariates are often accessible in the target environment. As a result, is often unneces- sary to account for the worst-case covariate shift rather than directly correcting for it. Alternatively, when the Y X dis- tribution changes but the X distribution remains invariant, the distribution shift is no longer identifiable, where we can instead apply the worst-case consideration to guarantee per- formance. This latter setting, known as concept drift, occurs due to sudden external shocks (Widmer& & Kubat, 1996; Lu et al., 2018; Gama et al., 2014). For example, in adver- tising, 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. In these applications, with the one extra bit of information that the shift is only in the conditional reward distribution, can we obtain a more efficient policy learning algorithm?
the covariate space is infinite, it remains unclear how to efficiently learn robust policy under concept drift. The current work aims to fill in the gap by answering the ques- tow can we efficiently learn a policy with optimal worst-case average performance under concept drift with minimal assumptions? We provide a rigorous answer to the above question. Specifically, distribution remains the same in the training and target en- vironments.' while the Y XX distribution shift is bounded in KL-divergence by a pre-specified constant 8. Our goal is to find a policy that maximizes the worst-case averaged outcome over all possible target distributions satisfying the previous condition.
assume the covariate
1.1. Our Contributions
Towards robust policy learning under concept drift, we make the following contributions.
Policy Evaluation. Given policy, we present a doubly- robust estimator for the worst-case policy value under con- cept drift. We prove that the estimator is asymptotic normal under mild conditions on the estimation rate of the nuisance parameter. Our approach involves solving the dual form of a distributionally robust optimization problem and tak- ing a de-biased step to deal with the slow convergence of the optimizer, thereby obtaining an estimator with root-n convergence rate.
Motivated by the above situations, study robust policy learning under concept drift. Most existing methods for robust policy learning (Si et al., 2023; Kallus et al., 2022) model the distributional shift jointly without distinguishing the sources, and the corresponding algorithms turn out to be suboptimal. The reason behind their suboptimality is that the worst-case distributions under the two models the joint-shift model and the concept-drift model can be substantially different, it would be "wasst" of our bud- get to consider adversarial distributions that are not feasible under concept drift. It is worth mentioning that a recent paper by Mu et al. (2022) accounts for the sources of distri- butional shifts in policy learning; their approach, however, applies only when the covariates take a finite number of values, and therefore is limited in its applicability. When
Policy Learning, We propose robust policy learning al- gorithm that outputs a policy maximizing the estimated policy value over a policy class II. Compared with the or- acle optimal policy, the policy provided by our algorithm with high probability has a regret/suboptimality gap of the order x (11)/ / /n, where x x(I) measure quantifying the
'Oteewwise, the covariate shift can be easily adjusted hy covari- ate matching discussed earlier.
2

---

Distributionally Robust Policy Learning under Concept Drifts
policy class complexity (to be formalized shortly) and n is the number of samples. Compared with Mu et al. (2022), our algorithm and theory apply to general covariate spaces and potentially infinite policy classes, while their method is restricted to finite covariate space and policy class. We complement the upper bound with a matching lower bound, thus establishing the minimax optimality of our proposed al- gorithm. We summarize the comparison between our result and prior work in Table for better demonstration.
for any a E [M]. We posit the underlying data-generating distribution P on the joint covariate-outcome random vector (x, (I),
Y (M)) E X x IL Va. Consider data set D = {(X,, A.. hegn consisting of n i.i.d. draws of (X, A, Y), where X; E X is the observed contextual vector, A, E [M] the action, and Y, = Y (A.) the realized reward. The actions are selected by the behavior policy To. where To(a x) = P(A+ = a X = I) is the propensity score, for any E [M ar X. We make the following assumptions for To and P.
Implementation and Empiries. We provide efficient im- plementation of our robust policy learning algorithm, and compare its empirical performance with existing bench- marks in numerical studies. Our proposed method exhibits substantial improvement.
Assumption 2.1. The behavior policy To and the joint dis- tribution P satisfy the following.
(1) Unconfoumdedness: (I) ([I),..... .Y())) | (2) Overlap: for some E > O, To 2) 2 e, for all (a, x) E [M] x X. (3) Bounded re-
ward support: there exists y > 0, such that S {((a) S y
for all E [M]
1.2. Related Works
Offiine Policy Learning. There is a long list of works devoted to offline policy learning. Most of them assume no distributional shifts (e.g.. Dudík et al. (2011); Zhang et al. (2012); Swaminathan & Joachims (2015a;b;c); Kita- gawa & Tetenov (2018); Athey & Wager (2021); Zhou et al. (2023)). Zhan et al. (2023); Jin et al. (2021; 2022a) allow the data to be adaptively collected, but the distribution over the covariate and the (potential) outcomes remain invariant in the training and target environment.
The above assumptions are standard in the literature (see e.g., Athey & Wager, 2021; Zhou et al., 2023; Si et al., 2023; Kallus et al., 2022). In particular, the unconfoundedness assumption guarantees identifiability, and the overlap as- sumption ensures sufficient exploration when collecting the training dataset. The bounded reward support is assumed for the ease of exposition, and can be relaxed to the sub- Gaussian reward straightforwardly.
2.1. The KI--istributtonalll Robust Formulation
As mentioned earlier, Si et al. (2023); Kallus al. (2022) study robust policy learning when the joint distribution of (X, Y) ranges in the neighborhood of the training distribu- tion; Mu et al. (2022) consider the case when the covariate shift and Y X shift are specified separately; their method, however, is restricted to finite covariate space, and their sub- optimality gap is logarithmic factors slower than parametric rates. More recently, Guo et al. (2024) considers pure covariate shift with focus on policy evaluation, where the setup and the goal are different from ours.
Given the training set D {(X,, A,, Yi) hejn)) and policy class II, we aim to learn policy π E II that achieves high expected reward in target environment that may deviate from the data-collection environment where D is collected. While distribution shift can take place in various forms, we focus primarily on the concept drift, where only the con- ditional reward distribution (a) X differs in the training and target environments. The distance between distributions is quantified by the KL divergence.
Distributionally Robust Optimization. More broadly, our work is closely related to DRO, where the goal is to learn a model that has good performance under the worst-case distri-
Definition 2.2 (KI. divergence). The KL. divergence dQ) = Eq [log apl, where dQ is the Radon- dP Nikodym derivative of Q with respect to P.
between two distributions Q and P is defined as (KL(Q || P)
bution (e.g.. Bertsimas & Sim (2004); Delage& & Ye (2010):
Hu & Hong (2013); Duchi et al. (2019); Dudík al. (2011); Zhang et al. (2023)). The major focus of the aforemen- tioned works involves parameter estimation and prediction in supervised settings; we however take a decision-making perspective and aim at learning an individualized policy with optimal worst-case performance guarantees.
We define an uncertainty set of neighboring distribu- tions around P, whose conditional outcome distribution is bounded in KL divergence from P. Given radius 8 > O. the uncertainty set of the conditional distribution is defined as P(Py 5) = {Qr1x DRL(Qy |x 1x) < 8). where Py Prxxx and Q refers to the distribution of (I Y (M)) X under P' and Q respectively. The distributionally robust policy value for any policy x at level
2. Preliminaries
8 is defined as
Consider set of M actions denoted by [M] and let X C Rd.. Throughout the paper, we follow the potential outcome framework (Imbens& & Rubin, 2015), where Y (a) E V. C R denotes the potential outcome had action a been taken
VT(T)= := Epx
inf E Ix
y (x(x))
x (1)
Q PPPPxp(Pr
3

---

Distributionally Robust Policy Learning under Concept Drifts
The optimal policy in II is the one that maximizes (TT),, L.e. Tz argmaxzen Vs (T)
estimate (oc 77), and then compute an estimate of V3
by plugging (o m7) into Equation (4).
Under this formulation, our goal is to learn a "robust" policy with a high value of (T) using dataset drawn from P. The task here is two-fold: we need to (i) estimate the policy value (T) for given policy n, and (ii) find a near-optimal robust policy के E II whose policy value is close to the optimal policy Tz.. Here, the performance of learned policy सt is measured by the sub-optimality gap (regret):
The remaining challenge in this proposal is the slow esti- mation rate of the optimizers - if we naively plug in the optimizers, the resulting policy value estimator typically has a convergence rate slower than root-n. To overcome this, we incorporate a novel adjustment method to debias the estimator, which allows us to obtain a doubly-robust estimator that achieves root-n convergence rate even when then nuisance parameters (e.g.. (7)) are converging slower than the root-n rate.
R == Vo(=))) (f).
In the following sections, we tackle each task sequentially.
We end this section by providing a sufficient condition to ensure ox (1)) > O, which we make throughout the paper.
2.2. Strong Duality
Assumption 2.4. For a E [M] and x E X, define y( a) sup(t: (P((()) < L X x, A = a) 0} and p(z;a) (a) y(æ; a) X = 2, a). It holds that log(1/5(x;a)) > ō for Px|A=a-almed all x.
In order to estimate (T), we first rewrite the inner op- timization problem in Equation (1) in its dual form using standard results in convex optimization (see e.g., Luenberger (1997)). The transformation is formalized in the following lemma, with its proof provided in Appendix D.I.
The above assumption is mild and can be satisfied by many commonly used distributions, e.g., all the continuous dis- tributions; it requires that PyIX.A does not posit a large point mass at its essential infimum. The following result from Jin et al. (2022b, Proposition 4), shows that a* 0 when Assumption 2.4 holds, ensuring that the gradient of the risk function in ERM has zero mean.
Lemma 2.3 (Strong Duality). Given any x E II and any E X, the optimal value of inner optimization problem in Equation (1) equals to
min Ep (ola,m:1) x x 1).
a20.nER
Proposition 2.5 (Jin et al. (2022b)). Under Assumption 2.4, the optimizer ox of (3) satisfies a* > 0.
where Vo(a, a exp(
((((())++ - 1) + 17 ad.
a
We note that the optimization problem in (3) depends on and
3. Policy Value Estimation under Concept Drift
to manifest this dependence, we use (a* (1c), n (z)) to denote its optimizer, i.e., of and ni are functions of x and
3.1. The Estimation Procedure
(x), E argmin Ep Vola, x x= }
Fixing policy x, we aim to estimate the policy value V5(T)) using the training dataset D. We first split D into K equally sized disjoint folds: D(k) for E [K].² where we slightly abuse the notation and use (Dk) to denote the data points or the corresponding indices interchangeably.
a20,nER
With this notation and Lemma 2.3, the robust policy value
VT(T) = EEp
(4)
For each & [K]. we first use data points in D(k++1) to ob- tain the propensity score estimator ((4) and the optimizers (a! ,, We then define
The above formulation has thus translated the original dis- tributionally robust optimization problem into an empiricul risk minimization (ERM) problem. We note that, unlike the well-studied joint distributional shift formulation, the above representation admits an optimizer pair (1),, ni (z:) that
2 (I, v) == (z)
+ (x a (x)
is dependent on the context & (i.e. xx, 77 are functions of r) and the policy π. As we shall see shortly, our proposed policy value estimation procedure employs ERM tools to
(ar) :Ep G (X, (((())
| X xx=2]
(lk We next use D(k+2) to obtain gF
(k)
as an estimator of g=
When the supremum cannot be attained, we can always con- struct sequence of policies whose policy values converge to the supremum, and all the arguments go through with limiting argument.
'e assume without loss of generality that n is divisible by K. In practice, we only need minimum of K = 3 folds. 'We use the convention that (1)) Dok mod K) for any
4

---

Distributionally Robust Policy Learning under Concept Drifts
Algorithm 1 Policy estimation under concept drift
By the notation, (z(2) (o (2), (x)) is the opti- mizer of (T(()) Throughout, we make the following assumption on 0=.
Input: Dataset D; policy म; uncertainty set parameter 6; propensity score estimation algorithm C: ERM algorithm E for obtaining (ax ( regression algorithm R. for estimating 9T-
x] with respect to 0.
Assumption 3.3. For any policy 3a, a, fj such that O < @ S a (1) S ã. [ (1)) S Va E X.
Randomly split D into K non-overlapping equally-sized folds D(k), k E [K];
The above assumption is mild and can be achieved, for example, when (z) is continuous in x and when X' is compact. We refer the readers to (Jin et al., 2022b) for a more detailed discussion.
for k- = 1, K do
(k)) + E(D(K+1)); To +- C(D(++2)), (az 7
(k)
9x + R[ An, (X,, Y:); E D(k+2)));
Compute D/(((()))) according to Equation (5); end for
Under the unconfoundednesss assumption, 02 is also mini- mizer of E [e(x, Y: ( = =(X)] We can thus estimate 0 by minimizing the empirical risk:
(00) Return: (T) +-+ k E k=1 (T).
0 k)) E aagmmin (Eprto) (XX,,+1
(X)I].
The policy value estimator (i(k) (x) for the k-th fold is
oee
(X, = A.}
D3( (T)
where + S {(a, 11) a R2o. n: X: + B) is to be determined. In our implementation, we follow Yadlowsky et al. (2022); Jin et al. (2022b); Sahoo et al. (2022), and adopt the method of sieves (Geman & Hwang, 1982) to solve (7). Specifically, we consider an increasing sequence O O2 C ... of spaces of smooth functions, and let θ O, in Equation (7). For example, G, can be class of polynomials, splines, wavelets. It has been shown in Jin et al. (2022b, Section 3.4) that under mild regularity con- ditions, 0²h) converges to 0 a reasonably fast rate, For example, if X' = I[ X, S Rd for some compact inter- vals X2 and that O belongs to the Hölder class of p-smooth functions with some other mild regularity conditions p/ (2p+))))
DDO1
# (k) (A: X.)
(ED
(G (X,, Yi) - 0/hh (X:)) + - (X.) (5)
The policy value estimator is (T) = Σ k= The complete procedure is summarized in Algorithm 1. Remark 3.1. The estimation procedure involves three model- fitting steps corresponding To. (att n,), and Dr. respec- tively. The propensity score function To can be estimated with off-the-shelf algorithms (e.g.. logistic regression, ran- dom forest): the conditional mean gl.²) can be obtained by regressing (( (X,, Y.) onto X; for the points such that A, = π (X,) with standard regression algorithms, e.g., ker- nel regression (Nadaraya, 1964; Watson, 1964), local poly- nomial regression (Cleveland, 1979; Cleveland & Devlin, 1988), smoothing spline (Green & Silverman, 1993), regres- sion trees (Loh, 2011) 1) and random forests (Ho et al., 1995). The ERM step is more complex, and will be discussed in details shortly.
K
(T).
then 10th - 0% La (=e(x)) = Op(( log 22
and 110|*) 0= = Op(( [ug - ((2p+))))) The solu-
tion details are given in Appendix B, and we also refer the readers to Yadlowsky et al. (2018) and Jin et al. (2022b).
3.2. Theoretical Guarantees
Remark 3.2. The construction of the estimator (T) em- ploys two major techniques: cross-fitting and diabinsing. The cross-fitting fitting technique splits the training dataset D into K folds equally and fits the nuisance parameters on the off- fold data. This crucially provides the convenient property of independence between the fitted nuisance parameters and policy value estimators. In contrast to the naive plug-in esti- mator whose convergence rate is largely affected by the slow estimation rate of the nuisance parameters, the de-biasing technique addresses this limitation, thereby leading to the doubly-robust property of the proposed estimator.
We are now ready to present the theoretical guarantees for the policy value estimator (TT). To start, we assume the following for the convergence rates of the nuisance parame- ter estimators.
Assumption 3.4 (Asymptotic estimation rate). For any pol- icy n, assume that for each & E [K], the estimators (R) (k) Fn and the empirical risk optimizer 0 satisfy
| Tollza Px| ( = or 7))
ll
gf (12a((x)Ammee)) (m)()))) = On -7²),
The ERM Step. For notational simplicity, we denote 0 (a, 1)) and write the loss function from Lemma 2.3
( 0 (1 (x)x())) = Opp(n +),
|0ا00
0 1/l = =0)(1),
y + (-"+² - 1) + 17 + aad (6)
E(1, y; 0) = a exp
for some 71. 2 and 7 + 72 2 1.
5

---

Distributionally Robust Policy Learning under Concept Drifts
Assumption 3.4 (1) requires either the propensity score Ro or the conditional mean of @ (X, Y) is well estimated. This is a standard assumption in the double machine learning literature (Chernozhukov et al., 2018; Athey & Wager, 2021; Zhou et al., 2023; Kallus al., 2019; 2022; Jin et al., 2022b) and can be achieved by various commonly-used machine learning methods discussed in Section 3.1. Assumption 3.4 (2) requires the optimizer [(4)) to be estimated at a rate faster than n 1/4 and can be achieved by, for example, the estimators discussed in Section 3.1 under mild conditions. The empirical sensitivity analysis in Jin et al. (2022b) also provides some justification for Assumption 3.4.
Remark 4.1 (Computational efficiency of the proposed short- cut). Constructing (2x with (n(e)) (z) substantially re- duces the computational complexity of the policy learning task. It is virtually infeasible to estimate 0g (a) for each π in a policy class II with infinite number of policies. Al- ternatively, solving for m=(z)) (a) transforms the infeasible task of computing a class of infinite nuisance parameters (0x : π E [1] to the feasible task of computing a finite one (x)
[M]] It remains an interesting future direction to extend this trick to continuous action spaces.
4.1. The Learning Algorithm
The following theorem states that our estimated policy value (T)) is consistent for estimating Vs8 and is asymptotically normal. Its proof is provided in Appendix D.2.
The policy learning algorithm consists of two main steps: (I) solving for 0 for each a E [M] and constructing the policy value estimator ()(T)); (2) learning the optimal policy Th by minimizing (TT).
Theorem 3.5 (Asymptotic normality). Suppose Assump- tions 2.1, 2.4, 3.3, and 3.4 hold. For any policy π : X + [M], we have Vn. (D)(T)) - -V((T) 4 N(O, where
As before, we randomly split the original data set D into K folds. For each fold k [K], we use samples in the (k+1)-th data fold D(*+1) to obtain the propensity estimator
of = Var 1[A= = 1[A=+(X]} (C(X,)) + xxxx): To(A|x)
* -)) (by regression) and the optimizer 0% (by ERM) for each a E [M]. Next, for each a E [M], define
Gx(2,)) v) =((2, y; 02);
9x = (((XX) X x=2].
Ga(o,y) = f(x, (lr.y:0,00 (1))), 2 (z,z) = ((. y: (1) (x)).
5.th = B (X. (x)) X x]
4. Policy Learning under Concept Drift
We then obtain an estimator ga for G (X,, Y) onto X, with i E ()*++)) Finally. we obtain the learned policy by maximizing the estimated policy value:
(b) by regressing
Building the results and methodology in Section 3, we turn to the problem of policy learning under concept drift. Given a policy class IT and an estimated policy value (T) for each π E 11, it is natural to consider optimizing the estimated policy value over II to find the best policy. The biggest challenge here is that the nuisance parameter ( in defining (T() is not only a function of x E X. but also a function of π E II. The above strategy requires carrying out the ERM step in Section 3.1, for all possible policies π 1I. posing major computational difficulties.
TIN = argmax DIN
1
DIN,CM (T):
(9)
TEN
K
(LN.(K) (T)
Σ
1(A, . (X,)}
[D(3]] iED())
(+( (A+ Xx))
x(X) (X,
(X,, Y.)
(.1)) T (X:)) + Xx(x (X.).
Instead of solving 0% for each π E II, we propose a com- putational shortcut that solves a similar ERM problem for each action E [M.. To see why this is sufficient, note that for any IT.
The above optimization problem can be solved efficiently by first-order optimization methods or policy tree search as in Zhou et al. (2023); we shall elaborate on the implementa- tion in Section 5. The complete policy learning procedure is summarized in Algorithm 2.
EE [[((X, Y (T(X))) = x]]
M
Σ [x((X) = a)- Eie(a, V(a):)) | X z]. (8)
4.2. Regret Upper Bound
In this section, we present the regret analysis of मLn ob- tained by Algorithm 2 (recall the definition of regret given in Equation (2)). Before we embark on the formal analysis, we introduce the Hamming entropy integral x(II), which measures the complexity of II.
Letting (z) E argmin [L Y (a): = x]}. we
can see that 0 (z)) (z) is a minimizer of (8). Then, the policy learning problem reduces to finding æ E IT that maximizes
Definition 4.2 (Hamming entropy integral). Given a policy class II and n data points (I1,..., [n] XX
E ((x, (xxx)))))x
6

---

Distributionally Robust Policy Learning under Concept Drifts
Algorithm 2 Policy learning under concept drift
4.3. Regret Lower Bound
Input: Dataset D; policy class II; uncertainty set param- eter 8; propensity score estimation algorithm C: ERM algorithm E() for obtaining 0%: regression algorithm R for estimating Pa-
In this section, we complement the regret upper bound in Theorem 4.3 with minimax lower bound that characterizes the fundamental difficulty of policy learning under concept drift. Our lower bound is stated in terms of the Natarajan dimension (Natarajan, 1989), defined as follows.
Randomly split D into K equal-sized folds;
for k = 1,.... K do
#6() + C(D(++1)), .M do 0ahh) + E(D(+t2));
Definition 4.4 (Natarajan dimension). Given an M-action policy class II, we say a set of m points {=1.-.., Fm is shattered by 11 if there exist two functions f-1. fi {II...., FTm. H [M] such that f f-((2)) * f12) for all j E [m] and for any a E {=1]",, there exists a policy π E II such that for any j E [m], (2,,) = Say (zz). The
for 1,.,,,
(k) + R(X,, Ar, G1h (X, D(
ga
end for end for
Natarajan dimension Ndim(II) of II is the size of the largest set shattered by II.
Return: ā that maximizes DIN as in Equation (9).
Remark 4.5 (Connection to other complexity measures). As can be seen from the definition, the Natarajan dimension generalizes the Sopnik-Chervonenkis (VC) dimension (Vap- nik & Chervonenkis, 2015) to the multi-class classification setting. The Natarajan dimension is also closely related to the Hamming entropy integral ((II) in our upper bound, as = O(v rlII)-
(I) The Hamming distance between two policies n. T' E II is (T, == :. E.= 1 (x(xx) * (x:)).
(2) The e-covering number of (#1....,7T,) denoted as C(c, II; (21,....,,1]) is the smallest number L of policies ( v.. in II, such that V a E II, 3
(Cai et al., 2020).
Tt such that (T. me) S.
Theorem 4.6 (Regret lower bound). Let P denote the set of all distributions of (X, A, (I)...... (M)) that satisfy As- sumption 2.1, 2.4, 3.3, and 3.4.5 Suppose that S 0.2, n 2 Ndim(11)², and Ndim(11) 2 4/(9s). ). For any policy leaning algorithm that outputs î as a function of {(X,, A,, Yo
(3) The Hamminn entropy integral of II is defined as IIII)= == So vlog NH de, where (e II:: sup suppr..... ........... C(e, 1I; (fi,...,
The following theorem provides regret upper bound for the policy learned by Algorithm 2.
there is suppEp Ep- [RF)) > 126
Ndim:
Theorem 4.3. Suppose Assumptions 2, 3.3, 3.4 hold. For any B E (0, 1), there exists N E N+ such that when n 2 N, we have with probability at least 1 - B that
The proof of Theorem 4.6 is provided in Appendix D.4. Theorem 4.6 implies that for any learning algorithm, there exists problem instance such that the regret scales as Ω v NKdim((I)//)
Co(a, C. 77 5,8) (65 (65+ + 8x(II) + + \lg(118))
R.s S
vn
Remark 4.7 (Optimality of Algorithm 2). Recalling the rela- tionship between the Natarajan dimension and the Hamming entropy integral in the remark above, we see that our pro- posed algorithm achieves the minimax rate in the sample size and the policy class complexity.
where a, = 6(ā-- (ite-eppf//a-111
The proof of Theorem 4.3 is deferred to Appendix D. At a high level, we decompose the regret and upper bound it with the supremum of the estimation error of policy values:
(fLNN) = =Vs(TT) - (+LN) $ Vo(T*) - -O (iT*) DIN (TT)) (fiN) + DIN (fLi)) (RLN)))
5. Numerical Results
We evaluated learning algorithm in two settings: simu- lated and a real-world dataset, against the benchmark algo- rithm SNLN in Si et al. (2023, Algorithm 2).
22 sup nell
(T) (T)
(T))
where the last step uses the choice of म... We bound the above quantity by establishing uniform convergence results for the policy value estimators. Through careful chain- ing argument, we show that the dependence of ((Tx)) on n is of the order Onn which is sharper than the O(n 1og dependence for that of Mu et al. (2022) by a logarithmic factor. We also note that both regrets are asymptotic in a and hold for sufficiently large n.
Simulated Dataset. Our data generating process follows that of the linear boundary example in Si et al. (2023). We let the context set X' be the closed unit ball of R and let the action set to be {1, 3): the rewards ((a)'s are mutually independent conditioned on X with Y(a) X
Whee we say distribution satisfies Assumption 3.4, we mean that under P there exist 0, Ro. and Ū that satisfy the conver- gence rates Assumption 3.4.
7

---

Distributionally Robust Policy Learning under Concept Drifts
METRIC
POLICY
n =500
n =3350
n 16500
n 19500
FLN
0.2272:10.002
0.229910.0001
0.2303:10.001
0.2310
0.05
RSNLN
0.0554+0.005
0.0589#0.004
0.0617=#0004
0.0664+0.003
0.1579+0.007
0.1662::0.022
0.1663#0.002
0.1678=0.000
0.1
RSNLN
0.0548+00.00
0.0580=0.000
0.0583=0.003
0.0616=0.000
WLN RSNLN
0.0781+0.003 0.0802+0.002
0.080410.002 0.0200=0.003
0.0831=0.000 0.0219=0.000
0.2
0.0182+0.003
0.0183+0.003
Table 2. Empirical robust policy value VA, of policies πT USNIN on the simulated dataset and the corresponding, over 50 seeds.
- 0.05
5 0.1
0.120
fux
flu.
0.076
0.138
Empirical policy value
0.074
0.116
0.072
0.070
20000
12000
14000
10000
19000
20000
10000
12000
14000
16000
18000
20000
Sample Size
Sample Size
Figure 1. Empirical robust policy value V. of policies म. n. TSNIN the real-world dataset, 50 seeds. Shading corresponds 95% confidence intervals.
being Gaussian, for a E [3]. The training datasets Duain are generated with an unknown given behavior policy No over 50 random seeds. We similarly generate 100 testing datasets Dies of size 10,000. The details are given in Appendix C.
Proposition 2.5. Finally. we optimize and find ãn with pol reytree (Sverdrup et al., 2020).
The benchmark algorithm SNLN is adapted from Si et al. (2023, Algorithm 2) as Kallus et al. (2022).7 Since Si et al. (2023, Algorithm 2) is designed for joint distribution shift formulation, we revised the original algorithm to fit our concept drift setting. The well-known KL-divergence chain rule (Cover, 1999) gives
Real-world Dataset. We consider the dataset of large- scale randomized experiment comparing assistance pro- grams offered to French unemployed individuals provided in Behaghel et al. (2014). The decision maker is trying to leam a personalized policy that decides whether to provide: (i) an intensive counseling program run by public agency (A = 0); or (ii) a similar program run by private agencies (A 1), to an unemployed individual. The reward Y is binary and indicates reemployment within six months. The processed dataset is provided in Kallus (2023).
DxI(Qx. || Px.x) Dxx((x Px) + (Ra Py)).
(10)
Therefore, given any uncertainty set radius 8 and known covariate shift (in this experiment, we assume covariate shift), Si al. (2023, Algorithm 2) can be used to imple- ment policy learning under concept drift. Note that SNLN admits known propensity scores. As we only consider the case where the propensity scores are unknown, we comple- ment Si et al. (2023, Algorithm 2) with estimated propensity scores from Random Forest Regressor in scikit-learn,
Implementation. In our implementation, the number of splits taken to be K = 3. We use the Random Forest regressor from the scikit-les rn Python library es- timate h. and g. For estimating 0", we adopt the cubic spline method and employ the Nelder-Mead optimization method in SciPy Python library (Virtanen al., 2020) to optimize the coefficients in the spline approximation, where the obtained estimator has threshold at 0.001 to guarantee
'A working example on the real- world dataset is given in https: Igithub.com/off www.ccoooooooooccccceeceee "The implemented code of SNLN benchmark provided by Kallus et al. (2022).
learnin.
8

---

Distributionally Robust Policy Learning under Concept Drifts
METRIC
POLICY
n =7500
n = 13500
n 16500
71 = 19500
ĀLN
0.2075:10.015
0.2149=0.007 0.2039 0.2017=0.006
0.2167=0.003 0.2020=0.004
0.1
RSNLN
0. 0.1884+0.007
0.2009+0.008
Table 3. Empirical worst case policy reward the KL-sphere Di of policies TIN TTNLNN over 20 seeds.
the same way as in the implementation of Algorithm 2.
as explained in Equation (10). Consequently, Va (TTNN)))) is lower bound of (LLN)) in theory, and by the results in Table 2, in practice. In real-world applications, knowing the source of the distribution shift effectively shrinks the uncer- tainty set, thereby yielding less conservative results. Since it is fairly easy to identify covariate shifts (comparing to detecting concept drift), 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.
Evaluation. For learned policy म. we evaluate its perfor- mance by the following performance metrics. (i) We use the testing dataset Drest to estimate the robust policy value Vi (f) by the empirical robust policy value
1
Σ DE
e(X,, ((T)(
iDess
where the nuisance parameters (X) are found via cu- bic spline method and employ the Nelder-Mead optimiza- tion method using the testing dataset according pol- icy म: D Dest, {(X,, Y.( (ii) We also per- turb the simulated dataset to mimic possible real-world distributional shift. For each testing dataset j contain- ing 10000 data points of the total 100 testing datasets, we generate a new testing dataset, with each reward dis- tribution (y,5) (1), (2), (3)) randomly sampled on the KL-sphere centered at the reward distribution (I), (1), (2), x,") of the testing data point with radius 8. Then we evaluate ã using
One limitation of our methodology (as well as in other DRO works) is the choice of 5. The parameter 5 controls the size of the uncertainty set considered and thus controls the degree of robustness in our model - the larger 6, the more robust the output. The empirical performance of the algorithm substantially depends on the selection of 8. A small 5 leads to negligible robustification effect and the al algorithm would learn an aver-aggressive policy; a large 8 tends to yield more conservative results. A more detailed discussion can be found in Si et al. (2023).
miin
min jE [100]
10000
Σ y (FXP)))
In Appendix C, we also provide simulation results of Algo- rithm I for fixed target policy, which show that Algorithm I can estimate the distributionally robust policy value under concept drift efficiently.
10000
This simulates more realistic scenario where the policy performance is measured by test datasets with concept drifts.
Results. Table 2 and I reports the values 7/5 of the learned policies Ln and TSNLN on the simulated and the woold dataset, respectively. Table 3 provides the result of Viuin All results are reported with 95% confidence intervals. Ta- ble shows that L outperforms the benchmark tSSNN consistently, with higher policy values and similar 95% con- fidence intervals. In Figure 1, #in continues to show this advantage over uSSEN on the real-world dataset. With higher 6, the policy values of T... SNLNN are smaller, due to a bigger uncertainty set. Table 3 shows that a achieves higher worst-case rewards than ASLLN does, in a more re- alistic setting with concept drift testing datasets. Together, we see that LLn succeeds in finding better policy under concept drift; while the performance of ANNNN is comprised by its conservative policy learning process, in which it con- siders joint distributional shifts even though it is given the information that no covariate shifts took place.
6. Discussion
In this paper, we study the policy learning problem under concept drift, where we propose a doubly-robust policy value estimator that is consistent and asymptotically nor- mal, and then develop minimax optimal policy learning algorithm, whose regret is (x(T))))) -1/2 with match- ing lower bound. Numerical results show that our learning algorithm outperforms the benchmark algorithm under con- cept drift. We also note that our results on pure concept drift could be extended concept drift adopts the same form as ours, but there is in addition identifiable covariate shift as in Jin et al. (2022b). The details can be found in Appendix E.
more general setting where the
The results align with the intuition that Algorithm 2 ad- mits a subset of the uncertainty set that SNLN considers,
9

---

Distributionally Robust Policy Learning under Concept Drifts
Acknowledgments
Chernozhukov, V., Chetverikov, D., Demirer, M., Duflo, E.,
Hansen, C.,, Newey, W., and Robins, J. Double/debiased machine learning for treatment and structural parameters, 2018.
This work is generously supported by the ONR grant 13983263 and the NSF grant CCF-2312205. The authors would like to thank Miao Lu and Wenhao Yang for pointing out an error in earlier draft of this manuseript and their helpful comments. Z. R. is supported by Wharton Analytics. R. Z. is supported by RGC grant BC3-26210324.
Cleveland, W. S. Robust locally weighted regression and smoothing scatterplots. Journal of the American statisti- cal association, 74((68):829-836, 1979.
Cleveland, W. S. and Devlin, S. Locally weighted regres- sion: an approach to regression analysis by local fitting. Journal of the American statistical association, 83(403); 596-610, 1988.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Cover, T. M. Elements of information theory. John Wiley & Sons, 1999.
References
Delage, E. and Ye, Y. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations research, 58(3):595-612. 2010.
Ai, J. and Ren, Z. Not all distributional shifts are equal: Fine-grained robust conformal inference, arXiv preprint arXiv:2402. 13042, 2024.
Duchi, J. C., Hashimoto, T., and Namkoong, H. Distri- butionally robust losses against mixture covariate shifts. Under review, 2(1). 2019.
Athey, S. and Wager, S. Policy learning with observational data. Econometrica, 133)613331,,, 2021.
Dudík, M., Langford, J., and Li, L. Doubly robust policy evaluation and learning. arXiv preprint arKiv: 101.110344000 2011.
Behaghel, L., Crépon, B., and Gurgand, M. Private and public provision of counseling to job seekers: Evidence from large controlled experiment. American economic journal: applied economics, 6(4): 147-17,, 2014.
Gama, J.. Žliobaité, I., Bifet, A., Pechenizkiy, M., and Bouchachia, A. A survey on concept drift adaptation. ACM computing surveys (CSUR), 46(4):1-37, 2014.
Bertsimas, D. and Sim, M. The price of robustness. Opera- tions research, 52(1):35-53, 2004.
Bibaut, A., Kallus, N., Dimakopoulou, M., Chambaz, A., and van Der Laan, M. Risk minimization from adap- tively collected data: Guarantees for supervised and pol- icy learning. Advances in neural information processing systems, 34:1 34:19261-19273, 2021.
Geman, S. and Hwang, C.-.. Nonparametric maximum likelihood estimation by the method of sieves. The annals of Statistics, pp. 401-414 1982.
Green, P. J. and Silverman, B. W. Nonparametric regres- sion and generalized linear models: a roughness penalty approach. Crc Press, 1993.
Bottou, I.., Peters, J., Quiñonero- Canneell,, J., Charles, D. X., Chickering, D. M., Portugaly, E., Ray, D., Simard, P., and Snelson, F. Counterfactual reasoning and learning sys- tems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 2013.
Guo, Y., Liu, H., Yue, Y., and Liu, A. Distributionally robust policy evaluation under general covariate shift in contextual bandits. arXiv preprint arXiv:2401.11353, 2024.
Cai, F., Qu, Z., Xia, L., and Zhou, Z. Multi-action of- fline policy learning with bayesian optimization. arXiv preprint arXiv:2003.07545V/ 2020.
Ho. T. K. et al. Proceedings of 3rd international conference on document analysis and recognition. In Proceedings of 3rd international conference on document analysis and recognition, 1995.
Cauchois, M., Gupta, S., Ali, A., and Duchi, J. C. Robust validation: Confident predictions even when distributions shift. Journal of the American Statistical Association, pp.
Hu, Z. and Hong, L. Kullback-leibler divergence con- strained distributionally robust optimization. Available Optimization Online, 1(2):9, 2013.
1-66, 2024.
Chan, C. W., Farias, V. F., Bambos, N., and Escobar, G. J. Optimizing intensive care unit discharge decisions with patient readmissions. Operations research, 60(3):1323- 1341, 2012.
Imbens, G. W. and Rubin, D. B. Causal inference in statis- tics, social, and biomedical sciences. Cambridge Univer- sity Press, 2015.
10

---

Distributionally Robust Policy Learning under Concept Drifts
Jin, Y., Yang, Z., and Wang, Z. Is pessimism provably efficient for offline rI? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021.
Luenberger, D. G. Optimization by vector space methods.
John Wiley & Sons, 1997.
Mu, T., Chandak, Y.. Hashimoto, T. B., and Brunskill, Factored dro: Factored distributionally robust policies for contextual bandits. Advances in Neural Information Processing Systems, 35:8318 15:8318-8331, 2022.
Jin, Y., Ren, Z. Yang, Z., and Wang, Z. Policy learning" without" ovvrlut" Pessimism and generalized empirical bernstein's ss incquality. arXiv preprint arXiv:2212.09900 099000 2022a.
Murphy, S. A. Optimal dynamic treatment regimes. Jour- nal of the Royal Statistical Society Series B: Statistical Methodology, 65(2)331-355, 2003.
Jin, Y., Ren, Z., and Zhou, Z. Sensitivity analysis under the s-sensitivity models: distributional robustness perspec- tive. arXiv preprint arXiv:2203.04372. 20226
Nadaraya, E. A. On estimating regression. Theory of Prob- ability & Its Applications, 91):1111-42,, 1964.
Jin, Y., Guo, K., and Rothenhäusler, D. Diagnosing the role of observable distribution shift in scientific replications. arXiv preprint 2309.0030000 2023.
Namkoong, H., Yadlowsky, S., et al. Diagnosing model performance under distribution shift. arXiv preprint UrXiv:2303.02011 2023.
Kallus, N. Treatment effect risk: Bounds and inference. Management Science 69(8):4579 4590,, 2023.
Natarajan, B. K. On learning sets and functions. Machine Learning, 4:67-97, 1989.
Kallus, N. and Udell, M. Dynamic assortment per- sonalization in high dimensions. arXiv preprint arXiv:1610.05664. 2016.
Recht, B., Roelofs, R., Schmidt, I.,, and Shankar, V. Do imagenet classifiers generalize to imagenet? In Interna- tional conference on machine learning, pp. 5389-5400. PMLR, 2019.
Kallus, N., Mao, X., and Uehara, M. Localized debiased ma- chine learning: Efficient inference on quantile treatment effects and beyond. arXiv preprint arXiv:1912.12945. 2019.
Sahoo, R., Lei, L.,, and Wager. S. Learning from biased sample. arXiv preprint arXiv:2209.01754 2022.
Si, N., Zhang, F., Zhou, Z., and Blanchet, J. Distributionally robust batch contextual bandits. Management Science, 2023.
Kallus, N., Mao, X., Wang, K., and Zhou, Z. Doubly robust distributionally robust off-policy evaluation and learning. In International Conference Machine Learning, pp. 10598-10632. PMLR, 2022.
Sverdrup, E., Kanodia, A., Zhou, Z., Athey, S., and Wager, S. policytree: Policy learning via doubly robust empirical welfare maximization over trees. Journal of Open Source Software, 5(50):2232, 2020.
Kim, E. S., Herbst, R. S., Wistuba, I., Lee, J. J., Blumen- schein Jr, G. R., Tsao, A., Stewart, D. J., Hicks, M. E., Erasmus Jr, J., Gupta, S., et al. The battle trial: person- alizing therapy for lung cancer. Cancer discovery, 1(1): 44-53, 2011.
Swaminathan, A. and Joachims. T. Batch learning from logged bandit feedback through counterfactual risk min- imization. The Journal of Machine Learning Research, 16(1):133 2015a.
Kitagawa, T. and Tetenov, A. Who should be treated? empir- ical welfare maximization methods for treatment choice. Econometrica, 86(2):591-616, 2018
Swaminathan, A. and Joachims, T. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference on Machine Learning, pp. 814-823 PMLR, 2015b.
Liu, J., Wang, T., Cui, P., and Namkoong, H. On the need for a language describing distribution shifts: Illustrations on tabular datasets. arXiv preprint arXiv:2307.05284, 2023.
Swaminathan, A. and Joachims, T. The self- normanordl estimator for counterfactual learning. advances in neural information processing systems, 28, 2015c.
Loh, W.-.. Classification and regression trees. Wiley inter- disciplinary reviews: data mining and knowledge discov- ery, 1(1):14-33, 2011.
Van der Vaart, A. W. Asymptotic statistics, volume 3. Cam- bridge university press, 2000.
Lu, J., Liu, A., Dong, F., Gu, F., Gama, J., and Zhang, G. Learning under concept drift: A review. JEEE transac- tions on knowledge and data engineering. 31((2):2346 2363, 2018
Vapnik, V. N. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity: festschrift for alexey chervonenkis, pp. 11-30. Springer, 2015.

---

Distributionally Robust Policy Learning under Concept Drifts
Virtanen, P., Gommers, R., Oliphant, T. E.,, Haberland, M., Reddy, T., Cournapeau, D., Burovski, E.,, Peterson, P. Weckesser, W., Bright, J., et al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261-27,, 2020.
Wainwright, M. J. High-dimensional stafisties: A asymptotic viewpoint, volume 48. Cambridge university press, 2019.
Watson, G. S. Smooth regression analysis. Sankhya: The Indian Journal of Statistics, Series A, pp. 359-372, 1964.
Widmer, G. and Kubat, M. Learning in the presence of concept drift and hidden contexts. Machine learning. 23: 69-101, 1996.
Yadlowsky, S., Namkoong, H., Basu, S., Duchi, J., and Tian, L. Bounds on the conditional and average treatment effect with unobserved confounding factors. arXiv preprint arXiv: 190.009188.. 2018.
Yadlowsky, S., Namkoong, H., Basu, S., Duchi, J., and Tian, L.. Bounds on the conditional and average treatment effect with unobserved confounding factors. Annals of statistics, 50(5):2587, 2022.
Yang, W., Zhang, L., and Zhang, Z. Toward theoretical un- derstandings of robust markov decision processes: Sam- ple complexity and asymptotics. The Annals of Statistics, 50(6):3223-322 2022.
Zhan, R., Ren, Z., Athey, S., and Zhou, Z. Policy learning with adaptively collected data. Management Science, 2023.
Zhang, B., Tsiatis, A. A.. Davidian, M., Zhang, M., and Laber, E. Estimating optimal treatment regimes from classification perspective. Stat, 1(1):103-114 2012.
Zhang, Z., Zhan, W., Chen, Y., Du, S. S., and Lee,
J. D. Optimal multi-distribution learning, arXiv preprinl arXiv:2312.051334 2023.
Zhou, Z. Athey. S., and Wager, S. Offline multi-action policy learning: Generalization and optimization. Opera- tions Research, 71(1):148-1888 2023.
12

---

Distributionally Robust Policy Learning under Concept Drifts
A. Notation
We use [r|] to denote the discrete set {1, (1,2,..., , for any n E Z. We use argmin and argmax to denote the minimizers and maximizers; if the minimizer or the maximizer cannot be attained, we project it back to the feasible set. We denote the usual p-norm as || Ilp. Denote P be any probability measure defined on the probability space (9))) P) and P to be the empirical distribution of P. For any function f. we denote the (n of f conventionally as llf = (f) d and Ilflle= = supsex lf(x).. . For any random variables X,Y, Y, we use Il to denote that X is independent of Y. For a random variable/vector X, we use Ex [-] to indicate the expectation taken over the distribution of X.
B. The ERM Solution
To solve the ERM problem, we follow Geman & Hwang (1982); Yadlowsky et al. (2022); Jin et al. (2022b) and adopt the method of sieves: consider an increasing sequence 01 O C... of spaces of smooth functions, and let (k) -lk)
Mi
argmin ET, (X, Y (T ()); In our case, we consider the following classes of sufficiently smooth functions. For l
Q1 [q] - 1 and Ø2 q Q1 (where q is the smoothness parameter), define the following function class for ry":
0%(2(= = { h (x)
DDh(z) - DP1((a)) S s
sup =EX El 2
[D +
sup xFZEX
1 x21
E
where we denote the derivative D = - 8hD To ensure the non-negativeness of of in Proposition 2.5, we define the truncated function class Og(X' <) : fxr + max (M(),, of h E (g())) for the search of az.. Consequently, the function class we consider is θ (x)) x ())
d2l
optimizers well, we need the true optimizer (a,, 175 to be sufficiently smooth in æ. Convexity and stability are also desirable property of the loss function for learning the optimizers. In the next assumption, we present the regularity condition on the conditional distribution Py x ensure smoothness of optimizers.
Assumption B.1 (Smooth conditional reward distribution). The conditional reward distribution PY(a)) X= |x=a is smooth in i.e. for some h E X, (Y(a)) X= (y(a)) X=x + t. Pr, for some measure Py. on )
Taking practical terms into consideration, Assumption B.1 is reasonable as we assume the conditional distributions of Y (a) are close for similar covariates, for any action a E A. Jin et al. (2022b, Appendix B.2) presents detailed discussion to justify smoothness of the optimizers under Assumption B.
Next, we would like to discuss the regularity conditions of the loss function in Equation (6) and its conditional expectation B[E(z, 6) X A T(z)]. In particular, require stability of the loss function and its conditional expectation so that plugging in estimators of the optimizers will not cause large errors, which is a mild condition that can be satisfied under the first-order Taylor expansion condition. Readers can refer to (Van der Vaart, 2000; Jin et al., 2022b) for more detailed discussion. Later, Lemma D. summarises the regularity conditions in formal terms and indicates that in our case, with KL-divergence and the loss function defined as in Equation (6), all the above regularity conditions are satisfied.
C. Experiment Details
We let the context set X {i E R ||0||2 < 1} to be the closed unit ball of R and let the action set to be [3]; the rewards ((a)ss (a)'s are mutually independent conditioned on X with (a) X ~ N x, o,), for a E [3]. We choose 8 and o's to be
81 (1,0,0,0,0),
B2 2--1-12233/20000000
8--(-1/2.
a (0.2, 02.,0.5,.08 0.8).
13

---

Distributionally Robust Policy Learning under Concept Drifts
The training dataset Duain {(X,; (X (x))) is generated with given behavior policy xo (unknown
policy learning algorithms), which chooses actions conditioned context a: according the following rules:
(0.5, 0.25, 0.25),
if argmax {3, x) 1,
1,,,,,
(z), mo To (2)) =
(0.25, 0.5, 0.25),
if argmax (3, x} = 2,
1=,,2,
(0.25, 0.25, 0.5),
if arrgaax {5, x}
(=1,2,3
We also generate 100 testing datasets, each with sample size 10,000. Each testing dataset Diea consists of i.i.d. draws of data tuple {X,, Y1) Y2(), (= and is generated similarly to the procedure described above.
We present the result of the policy estimation experiments in Figure 2, using Algorithm with inputs of the training datasets and the target policy
1, if ||l| 1/3).
<xx) = 2, if |al|2 [1/3, 2/3),
3, if ||l]2 [2/3. 1].
The underlying true policy value is obtained by the testing dataset Deas Similar to the learning experiment, repeat the estimation experiment over 50 seeds. Figure 2 shows that as the sample size increases, the estimated policy value by Algorithm is more accurate and stable.
0.05
a 0.1
a
0.000
0.0096
0,0006
0.0005
Latimmtte bibizufandly
0.0005
0.003
0.005
0.0005
0.004
0,0003
00003
0.002
0.0002
0.007
0000
10000
12000
14000 36000 Sumpll blze
18000
20000
8C00
10000
12000
14000 16000 Semple size
10000
20000
6000
10000
12000
14000
16000
28000
20000
Sample Siae
Figure 2. The Mean Square Error (MSF) of the estimated policy value by Algorithm 1. The r-axis is the number of samples used by Algorithm 1, and the y-axis is the mean squared error (MSE) of the policy value estimator.
Computation Details. The experiments were run on the following cloud servers: (i) an Intel Xeon Platinum 8160 2.1 GHz with 766GB RAM and 96 CPU 2.1 GHz; (ii) an Intel Xeon Platinum 8160 @ 2.1 GHz with 1.5TB RAM and 96 CPU 2.1 GHz; (iii) an Intel Xeon Gold 6132 @ 2.59 GHz with 768GB RAM and 56 CPU 2.59 GHz and (iv) an Intel Xeon GPU ES-2697A v4 @ 2.59 GHz with 384GB RAM and 64 CPU 2.59 GHz.
D. Deferred Proofs of the Main Results
D.I. Proof of Lemma 2.3
Fix E 1I and æ E X. Letting L dQv we can rewrite the inner minimization in Equation (1) as
dPy dPy1x 1x=x"
inf Epy x (T(( x] measurable
s.t. Ep, [ = = 11
(1I)
Epy [IL (L) = 6
14

---

Distributionally Robust Policy Learning under Concept Drifts
where the function (x) log represents the KL divergence function. In (11), the first constraint reflects that L is likelihood ratio, and the second constraint corresponds to the KI. divergence bound.
For notational simplicity, let E,, be the shorthand of E py 1x ||X z². By Theorem 8.6.1 of (Luenberger, 1997), the Slater's condition is satisfied and strong duality holds:
inf
Ex (+((x)))
max s(a: 77,2), a20,ER
(12)
B. =1,
E. (4
where
G(a, 2, = inf C(a, L,x,, L20
[(o, 11, I,,x = =Rx, -Fx))((())) + (Ex(T) - 1) + (Brl/K(((( - 6)
= + n 1) + (kk - -5]
We can explicitly work out the minimum of L(xx, yJs x), and we have
p(a, n. = E, affi.. (- [-X(m(a))+ - 17 ad)
where (v) = exply - 1) is the conjugate function of fKI. Using Equation (12), we arrive at
(- [_((T(E))+ + -1) + ad
inf [x((())) E. 11 (1)
= min az0.nER
Ex exepp
The proof is thus completed.
D.2. Proof of Theorem 3.5
For notational simplicity, we drop the dependence on P in EE when the context is clear. The proof of Theorem 3.5 makes use of the following lemma, which establishes some useful properties of the optimizer 0 The proof of Lemma D.1 can be found in Appendix F.1.
Lemma D.1. For any policy n, assume that Assumption 3.3 holds. We have the following properties of the optimizer 0
= 0 0 = (x) for any E X. (1) B[Vo ((T())): x = =x]
(2) There exists constant & such that for any and satisfying ||0 (r))l SE
[(xx, v) 0) E(x, v. (x)) 0;) (x)) < [x, v) |10 0 (x)
for some function ((x, y) such that supaex EL((Z, Y (T X = x| < for some L > 0.
(3) There exists constant & 0 such that for any 0 satisfying | 07 p.m - E1.
- E(X, Y (() (ot A=10)) S Cz 02llea(Px)
for some constant C₃ > 0.
We proceed to show the asymptotic normality of Vs(TT). For each &s E [K], we first define the following oracle quantity:
1(x(X,) A:)
(1(h)(m))
(G+(X,, Y.) (xx)) + (X.).
(DAA
(ED(K) Au(A X,)
15

---

Distributionally Robust Policy Learning under Concept Drifts
In the sequel, we shall show that 1 (T) (T) (/(10) (x) + +, +). We begin by decomposing the difference between ((k) 8 (अ) and Vothi
(K)) (T) (x) (T)
1
1 (X, A.) (x4 Yi) -))
Fz (x:)
((x(X;) = A.) To (A (xi)
-xx -
[D(
m (Ai Xx,)
Σ
9T ( (X,) - (X.))
[D(A]
(ED(A)
1(A, π. (X.)}
(G (X,, GX,,
D(k)
(Ai Xi)
iED(E)
1(A, = (X.))
1(A, = [(A,=((xi))
-x.)
D(Kj
To (A,1 Xx)
To(A:|X;
(ED(M)
(I)
Σ
1(A, = x(x.)
1(4 = x(Xi))
(G (X, Y2) - (x:))
D
m(K)) (A;
mo(A; (x.)
(ED(N)
(m
=A,=T(Xi
(7t (X.) - 9r (Xx))
Σ
Gf TH (X,, (x)))))((x))) (X.)).
D
To (x)
Diki
(EDIO)
iEDi
Bounding Term (I). Recall that (r) is the minimizer of
E[((<, | x
By the first-order condition established in part (1) of Lemma D.1, we have
V Vol(2 (o, ((T(z)) X = x =
(13)
For any E D(H), by the unconfoundedness condition in Assumption 2.1, we have
1(A, = mXx))
(X,,) G. (x)) x
Di-))
E
(A:AAIX))
1(A, x(X.).
(r--))
To(A; (X,)
2 (X,, ((TTX)(((()))) (G, (((()) D((-
-E(e(X,, (T ((x) ( XX(((X)))) Ox),) Vol(X,, (x)
D(-
where the last step is due to Equation (13). By Assumption 3.4, 11 0,1la.- or(1). Therefore, for any B (0, there
exists N N4 such that for n > N, |((()) 0f S min(g, &.). On the event that 110%²² (x) 0% (x)]le. S min(g,
16

---

Distributionally Robust Policy Learning under Concept Drifts
by part (2) of Lemma D.I and Jensen's inequality, we have
[[A, =(Xa). (X,, - Gx (X,, -X
x D(
E
(o( (AAi|XX) Xi)
[X,,, (,( @4 (x.)) ((,, V1(TT 0z()) F (xx) D(-
< 1
((X,, Yi) 1 0 (x.) 0 (X))) - LE 0 (x.) (X.) -x D( = -100, - 01l2
S 18
By Chebyshev's inequality, we have for any > 0 that
P
1
Σ
1(A:- (X-)
(G (X,, - -G(X
[D(H)
(o (1))
(ED(
1{A = T(x)
- |Di-0] 2 Di
E
xx(
1(A =[()]]
( (X,))
< DD( 1.2 Var
To(A|X X)
(Gth) G 1|2 (A(P))))
E2/D(K)|E2
Ce (10 (h) - 0 La La(Px
where the last step is due to part (3) of Lemma D.I. Combining the above results, we have that
term (I) = On 1/2 [|0[]] 0 0l + [ (px)))(P))) or(n 1/2).
where the last step is due to Assumption 3.4.
Bounding Term (II).
Applying the Cauchy- Schwarz inequality to term (II), we have
1
1 1(A, = TXx))
( | 1(A:= =
1 1(A:
(0t (X.) - k (x.))
[D(
(()
Σ
1(A, = x(x)))
(k) (A:)X,)
mo(A: Xx,)
(ED(M)
1
Σ
1fA, = (X,)) (X.) - gl (x,))²
x
V
[D(N)
(ED(R)
(e (=21 Toll a-x(0)
=0p
||
gl
(Px (x-())))))))) op(n" 0p(121/2).
where the next-to-last inequality is due to the lower bound on To and (h)); the last equality is due to the given convergence rate of the product estimation error in Assumption 3.4.
Bounding Term (III..
By Assumption 3.4, for any 3 E (0, 1), there exists N1 E N4, such that for n 2 Ni.
P( le, S min(a, 7)/2) 2 B.
On the event ( ()
0r I. < min(a. /2,
( x
(z, v\ = |((x, ys 0(0) < à Texp ( - 1) + nj + a6 =: Lg.
a
17

---

Distributionally Robust Policy Learning under Concept Drifts
Next, for any i D(A)
1 1(4, = x(Xi)
14,, -4,- -1x)))
(x.,) of (x.)) D(-a) k)
E
(k) (x)
mo(A:|x;)
[[A, = =((x))
14,, = x(Xi)}
D(,
E
E
(b)
(A, Xx)
To (x,)
x B ( ((x(X))) - 5f
oft (x:) X;, Di) Di-b0 = 0,
where the first step is by the unconfoundedness assumption and the second step is due to the fact that / is the conditional expectation of (k)
On the event [100%
0 1m I min(a, R)). By Chebyshev's s inequality, for any t > 0.
P
1
Σ
1{A, 1(A;=x(x))
1(4, (2.4 (G (X,, Y.) g6 (x:)) D(-b))
|D(
mo ( (Ail (,,)
xx)
iED(N)
[[A,, = π (xx))
1(4, = xXxi)
<
Var
(X,) Y.) gfhh (x.)) D(-
|22
#(() (A:1
To (A: Xi)
1
1(A, = T (X,))
= 144=x(Xp) (X,)))
(G,)) Y,) - 5f (x,)) D(
$
|D(
(k) (A:] Xx)
(x,)
412
[|=(() No (P'x ()=+(x)))
The above inequality along with union bound implies that
(II) Or (1 Tollez(Px | / / //DII/)=/ popnnnn//
term
where the last step is by the consistency of #b assumed in Assumption 3.4.
Bounding Term (IV).
We first show that term (IV) is of zero-mean:
E
Σ
144 1 (X.))
(ot (X.) - 9x (X.)) + [D(
Gffh ( (X+) =xx (()
DDAJ
To(A.
(ED(E
(ED())
1(A, = (X,))
(k) (X,) (x,)) D(-
(Xi) - 9 (X,)) D(- =0.
=-E E
(gth
E 9r
(A X1)
By Chebyshev's inequality, for any 1 0,
(xx) = Ad)
IP
(x.) - (X.)
(X.) - (x()) 21 )()))
[D(
(A(A Xi)
[D(
iED(E)
(ED(A)
1
1fA, T(Xi}
To(A,1 (3t (X.) - 9x - (x.) - I (X,)) ((-
Var
(D(
mo(TT(X,)|X (X.) - (xx)) D( (
(X() |X,)
E
(D( 2
As result, term (IV) = Op (11gg (k)
gz ll / / VT). Note that
(0 (Px) = (11 - 9 (eIlex(Px/Aemxx))
< 0 (1o -n llll (a ( + +10
18

---

Distributionally Robust Policy Learning under Concept Drifts
where the first inequality follows from the overlap condition. By Assumption 3.4, 1 (k)
Inl1e. = or(1). Meanwhile,
-0_h) 9- (P
[[(((X)
(4=)))
-E
((( [(X, ((T()) xx) A (x) x(X))
E
(axx,
-(x, A (())
< R
110 07 0 ( (1()).
Above, step (i) follows from Jensen's inequality and step (ii) from part (3) of Lemma D.1. Combining everything, we have that term (IV) is of rate o1/2))
Putting Everything Together. So far we have shown that for each fold k: E [K], there is
(T) (9 (T) op(n
Averaging over all & folds, we have
vn- (Va(T)) - Va(=))
1(A, = (xx))
}
-9x()))))))((x)))) (x.)) -V8())))) + top(1),
To (A4 (X.)
By the central limit theorem and Slutsky's theorem.
Vn Vn. (Po(#)-Vo(7T) N(0,00
where
(1(A 1 +xX== (G.(X, - (x(X)) + (x()
0² Var
(A(A
D.3. Proof of Theorem 4.3
By Assumption 3.3, taking π (ix) = a for any a E [M]. there exist constants Caa Ca. Tl such that
0 a < o (I) das [na())] Ta. Var X.
Letting a = | a. = max [M] C.. f = max. na. it follows that
0 < a (x) S a (=)] S 7, Vr E X, [M].
(14)
For any a E [M], if we take (xx) = a, then by (1) of Lemma D.1,
E Vol(z, 0 (z)) X x 0.
By (2) of Lemma D.I, for any a e [M], there exists a constant &a > such that for any - (2)0ll $ Ea
[6(x, v: 0) f(x, v: (x)) - Vol(e, (()) (0 (,)))) < (a v) (x)
for some function (x, y) S L,p for some constant Lap Similarly, we shall take { minge Ea. E(x, y) maxa Eo (x. y),
and L E.E,M] La.
By (3) of Lemma D.I, for any a E [M], there exists constant E1.a such that for any 0 - 07 S St.ar
((): -()) (a0xx < Ce.a 0
0 O1llca(xx|Asa)
Taking ε min ET, and Ce EaefMrt Ce the above inequality holds for any a E [M] and any |00 - 0.1k. S E1.
19

---

Distributionally Robust Policy Learning under Concept Drifts
1. REGRET DECOMPOSITION
The regret bound of Algorithm 2 builds the following regret decomposition:
Ra( VV((=)) Vo(TTN)
= -V(TT)- - 11. + D3 (T (OLN) + (TLN) - Vo(TTN)
S Va(T*)) - (+() (#LN) Vo(
(ALN)
< sup =enl
(T) Vs((T)
(15)
where the second-to-las, step is by the choice of L For any II and any fold & [K], we define intermediate quantity
1(A, = +X,)) 1(A,=
ViA = [D(
Σ
(o(A;1X,) (X,,.))(XX,))) (x(x))(Xii)) + (x(xx)(Xx.).
(ED
Letting V/5 R kk
Ex
(k) have
(T) Vo(TT)|
(IN (TT) V3(TT)
6
K
K
1
(K,,(K) (T) - -VS(TT) + (T((T) - VT(TT)
K
(LN,(K)
8 (अ)) 13 (TT)
-V((7) Vb(TT)
sup
sup mell
#ell
K
Taking the supremum over all II, we have that
K
DONN (x) - (z)=))())) S sup #Ill
sup
-V((T) VV(TT)
+ sup sEll K
1
(),, (TT) - 10((
8
TEll
k=1
We shall show that the first term above (//211/2) and the second term (n-12))) the following, we refer the two terms the effective term and the negligible term, respectively. The following lemma is essential for establishing the uniform convergence results.
Lemma D.2. Suppose h is a function of (xr, a, y, (()))- Given set of data {=t (2x, 0z, y:)) suppose that |h(,, (xx)) s cz(z)). Then the Rademacher complexity
n Σ
eah as Ur, maai)] <
V VELI c((2)2 (32 + 4x(II)),
E.
sup #ENI
iid. where E ~ Uni are i.i.d. Rademacher random variables and E, means the expectation over e.
D.3.2. THE EFFECTIVE TERM
Denote Z; = (X,, AG, Y.) and take
h(Z,, (X.)) 1fA, T(X)] Ro(A;|X))
(Cz(x))XX,,)) (x()))(Xi)) (xxx V5(TT).
Under the unconfoundedness assumption in Assumption 2.1, E(h TT (X,)) = 0. By Equation (14), have
[h(Z,, + ((x))) S - (axexp
7 -1) + + = Co a. (,,
a
20

---

Distributionally Robust Policy Learning under Concept Drifts
Meanwhile, have write
k
K
sup ttll
K
(/k (T) (x)
(7)-V6677 Vo(T))
= sup E
K k=
Dik) (ED(E)
Σ
((Z)s(((i)
= sup a
Σ
h (Zi (Z))
1=1
1=1
Next, we define
f4 2n:
Σ
h(z,, (2:)).
1=1
Consider two arbitrary data sets {z] and {<))=- We can check that for any π 11 and any j E [n].
(21. 1 (ni m)
sup r'Ell
[E
$ | ... (E(,..... 2/....,,2533
I sup ......,,,,,, kni - f(21, ,/., ..y,...,,,,, :n; [T
=ell
sup =ell n
m)) & Co a, 17, 8,
(16)
Above, the first inequality is because of the definition of sup and the second is due to the triangle inequality; the last step is due to the boundedness of h. Taking the supremum over all π E 1I in (16), we have that
sup xell
(z1..... Bj....; Znim) | - sup [( .y..... kni m S Co as 17, 6)8)/n
xell
By the bounded difference inequality (Wainwright, 2019, Corollary 2.21), for any t 0.
IP
sup =Ell
h 1(, n (x,,,())))
sup
h (Z (X:))
1t
n
rell
n
=P
sup nIll
|f(1 [i T)
sup [[Zi Lelll
2t) 2t) Se Colommnn.d.))
2n12
Take / = Cola, a n1, 6, 8, e) V
2n log (7)
Then with probability at least 1 3,
sup xell
h (2 (X.))
< E
sup xell
[22z (xx))] + Cola, 7,0,) 7,
1(
2n log (g)
It remains to bound the expectation term. Let Zi...., Z; be an i.idd copy of Zi...., Zn and let ltd Unif((+1])) Then
E
sup *E
Σ xZ,,((x)) - E (M (X,))
72
(E(D)
E
sup
h(Zz, xX.)) Ez 1 n
h(Zz, π (xx3)
(E|M)
vE(w)
( E
Σ |E[m]
M(Z (X,)) - 1 Σ
AZZ क (x-)))
sup TEll
i
E
sup TEll
Σ
(1(,,, M(Z,, (xx))
TE|n]
< 2E
sup FETT
1
Gh(Z,, x (x3))
n
3E|m]
1
2E
E.
sup L
Σ (c(m)
ech(Z,, (
(17)
n
21

---

Distributionally Robust Policy Learning under Concept Drifts
step (i) is by Jensen's is inequality and step (ii) is because of the symmetry of (2,, Zi).
Applying Lemma D.2,
E
sup LEll 71
Σ
ech(Zi, 7(xi)
2Co(a; n7, d, (32 + 4x(II).
vn
:E|n]
Combining the above, for any B (0, 1), we have with probability least 1 3,
Cu(a, a. F7, 5,)) (64 + SI([II + vlog(1/3))
sup rlll
[T(TT) - ()())) S
(18)
Vn
D.3.3. BOUNDING THE NEGLIGIBLE TERM
We now proceed to the negligible term. For any a E IT and any [K] consider the following decomposition:
DLN, (T)
1g (T)
1(A, T (X,))
(a(x)) (X,, 2.0) (x(x))(xi)) + +x((x) (X,)
|
(o X.))
IED(K)
1
Σ
1 (Xxi)
(x(A:|X,) (G (Gx, K.) (x:)) - (Xi)
[D(K)
(ED(K)
1
Σ
14A, T(x)}
1(A; x(x))) (2 (X,, Y.) - -100) (x(x)((x)))
[D(2]
To [x)
To(Ai113
DED
1{A, = (xx,) 1f4, = [(x)I
+
Σ
(2) (xxx))))))) - (x(x,)(X)))
[D
Ro(A: Xx)) (o(A:
(EDIN)
1(A, = xX.)}
Σ
| (G (X,, Y2) Gx(x))Xx, Yi))
+ [D(M] (ED(A)
Σ (ED())
1(4 T(x)}
(xxxx)(x))0nxxx((() + |DiN)]
1
Σ
(k) - (x.x)
[D(
(o (A, Xi)
(ED(A)
For notational simplicity, we denote
Ki(T)== = D(A)
Σ
1(4, = T(X)}}
1(A, TA,= (xxi)) x(,))
(G T(Xx) (X,, X.) (x(x)((xi)
7o(Ai (X))
(o(A:
iED(K)
K2(x)= = [D( (ED())
1(A; T(Xi)}
1(A =xxi)]
(0(0) (x,x))(x)) -x,(x)
X1)
In(A|Xx)
Ka(z):= = 'D(R)
1
1(A; = =X.)]
(GAR) (x(x) 83) - (X, YJ),
No (o (x))
(ED(E)
(²) == [D(
1(A (Xi))
(o(k)
(xxx,)()) - (X,))((i)) + D(A) iED(C)
(g(0)) (x) (x,x)(X))).
(A; X₂)
(ED(E
We proceed to bound each term separately. To ease the presentation, we shall write E, and Pk as the expectation and probability conditioned on D)= respectively.
Bounding (T(T). Here, we take
(1(A,= x(Xi))
1(4, 1(4,= x(Xi))
h (Z))
(() (o(A(1))) To(A: Xx)) (OUxx) (X,, (.), - (Xi)).
22

---

Distributionally Robust Policy Learning under Concept Drifts
Since (x)(()) is the conditional expectation of @ (x, (a))), we have
(X)
1[A, = T(X,))
1(4, = x
Ex (1, ((x))
(X,, Yi) 9/7 (xx)) X;
(Ai X;))
To (Ai (Ai))t)
To (X):)
(X,:) Xi) -1 1is
(())
7(x,) (X,,
[z(X,) (Xi) x
0.
By Assumption 3.4, there exists N1 E N., such that when 2 N1. W. p. at least 1 - 3,
0 1 max(ā, a. 12/2
max M
On the event {maxae[ar] 100h0 0, S <max(ā, @r 7)/2]. we have for any E [M]
(2 + 1) 2 26o.
((z,y,;0,(z)) - 2ā exp
a
(2t44 -1 1) 4nj + 45 We can then check that Letting Ci Cā 4x
2
(z;(Z;; - 2C (ā, a, 0, ( X,) (o (x,) < 2C1 (ā, a. 7,
max aE(M]
(a Xx) To X =: (X;))
The upper bound is constant conditional on X;'s and ( We now apply the bounded difference inequality conditional on X (e)]
P&
sup rell
[D [D(-k] k]]
Σ
h1 (Zi
E&
sup nell
[D(k)
Σ
(2,
|x] [ 2 x
iED(A)
(ED(R)
2)2((k) 1242
S Sexp
exp
Σ EiEDIN Ci (xx))
Taking V EsEDiN (xx,)) log( (1/33/ (D())) we have with probability at least 1 - B.
sup rlll |D(-
Σ h (Z,,
E&
sup xell
|D($)]
h hz (X,)) x
iED())
iED()
Σ LiEDI) (x))² [D(b]
v 1og(91/)).
For each i D(K), we take A and Y as i.i.d. copies of A, and V, conditional on X,, respectively. By similar symmetrization argument in the proof for the effective term, we have
Σ (ED())
h1 (Z,, T (xx)) x
Eg sup xell
(A))
Ex
sup rell
[D(
Σ
h1 (X,, A,, V.,
1 EA LYD(k))
Σ M(X,, AG, Y7,
x
iED(A)
(EDiRi
E3
sup sElt
[D(A]]
Σ (1 (,,,,,, (D-
h(Xi, A/e, Yú Yi, ((xx0)
x
iEDIM)
iED(N
(, Y1, 1(Xx AL, Y (X.))) x
< Ex
sup *Em
D
(ED()
< 2E
sup
[D(b]
eghi Ai, Y., Y.,
xx.
-
iED(M
23

---

Distributionally Robust Policy Learning under Concept Drifts
Applying Lemma D.2 with G (X)), have that
(xh Mi, (X.)) x} _ 2v LieDiE) (xx2))
Eg sup #Ell
Σ
(32 + (I)).
[D(k)
[D(k)]
DED))
Combining the above, on the event {maxue[M]] 110,²) - 0allax S max(ā, Q, ()/2),
LiDDIN Ci (X,)²
PA
sup FE
(T)
2
(64 + (II + vlog(1/3) xx) s s3.
[D(2]
Since
[o(aa X)- To x}|² S 1.
1
P4
max (mo(a| - To(a|x))²=
Σ
E [[(mo(a|x). - =o(a| 21
Dii)
eE[M]
iED())
dE[M]
<
Σ
(Tola - To(a x))²
Σ
E ( XX - Tu(a x 2t)
[D(K]
(ED(E) ME[M]
aE[Md]
< Σ PA
(To(a x) To(a| x))² - B[[To(aa x) x)=Ta(a| x))3] 21)
[D(
MM[M]
iED(A)
M exp (- 2 (8) (t²))
Taking union bound, with probability at least 1 - 33, we have that
sup =ell
(1)=) S
20 201 a, 7, 8)
(20 + 4x((TT + / /2log(1/3)
[D(J]]
- TolL
2m
M
Since EmE[M] 11 - TolL (=a) = (1))., there exists N1 2 N₁ such that when n 2 N1. with probability at least 1 - (/())),
K2 (T) v Cola, a. 5,5,))
sup elll
(19)
4yn
Bounding (T(T).
We first note that by Cauchy-Schwarzz eechwarzzieeuullinn
1 ((4, = ((x)))
1f4; = xX,))
(x.)
(k) (X.) - Ohh (xx))
(x.)
[D
(A; (X,) To (A, (x.)
iEDII)
1
(=(()) (I(X;) X,) - no (x.)
Σ
(ox(x,) (Xi)
xxxx,)(X.)) (x.))
-(K)
(ED())
(EDiE
M Σ RED(A) 1=1
M
(a Xx) - [ x
Σ
(k) (X.) - Da
1.0 (x.))
2
no
go
(ED(A a=1
Then for any 1> 0, let
M
||
mb.a (Px)(()))) j
max {1o!!* -/ 11<(1(o(())
max aE[M]
ls?
aE(M)]
24

---

Distributionally Robust Policy Learning under Concept Drifts
Then
1(A, 1144=x(M =x())) 1(A, = T(xi)
PP
max nell
[D(4]]
Ro(A; (x+)
To(A: Xi)
9A, (X,) 227 (xi)) 28
(k)
iEDIA)
M
M
Ipk
1
Σ
Σ
(a X.) - xx))
Ja (X:) -i (x:))² 20
(8)
122
(ED(R) aml
iEDiE) am
M
VM
< I
Σ
(k) (a X,) - mo(aa (xia
max
[1 - =o.ad lea(Ps)
|
Vie aE|M]
iEDEE) a=
+ P
Σ (ED(A) a=1
Σ
M
9a
(X.) (x,)) 2
VM
max (10% g. 1ea(Ps))))
E
[Dik]
vle
ae|M]
< 21,
where the last inequality is due to Chebyshev's inequality. Marginalizing over the randomness of D(-K), for any 3 E (0, 1), we have with probability at least 1 B that
max EIll [2)]
2M
max
|7
(16) max To (loo))
(1o%%
g. [lla((ss)) }-
3=a aE[M]
aE[M]
By Assumption 3.4, there exists N₂ E N such that when 2 N2. with probability at least 1 -3((KK),
Cola, a, d,),
sup (2((T]
(20)
4yn
=enl
Bounding Ka(T)) We start by taking
ha (())) = 1f4, = (X,))
|Ctx, (X,, X(T((.))) - (X,
[X(A:|Xi)
For any æ E IT,
E his Zi, x (X:)) X.]
Ex 1{4 = x(X)},
To(Ai (x))
[ (((((()()))) - (Xxx))(X [x:]
= E,
=Bx [((x,, Yi (i(T(())):: 24) (Xx) - L(X,, Y:: O- (xx)
VI(X,, (((T(X,)): 0- (x.) (Xx)) (01h)
x(x.) (X,) (x)) (X.)) x.]]
where the last step follows from part (1) of Lemma D.I. By Assumption 3.4, for any B E (0, 1), there exists N3 E N4 such that when n 2 Ng.
P max ME[M]
| 1% > min (S, a (.) s B.
On the event { [max.e[M] (10 0. S min((, ā, a, n). we have
((X,, Y:; (K) (X,)) - (Xx,, Y:: (xxx)()))) ve Y, Xxxi(x) (0x))) 02(xi))
((X,, Yi) Σ (x,().) 0x(x,))
ME(M]
25

---

Distributionally Robust Policy Learning under Concept Drifts
As result,
sup lell
Ex (T)) |x]] S sup .enl [D(
Σ
E&
[x.]
iEDiN)
(X,,) - (x)
[D
iDD(O) (E(
On the same event,
1f4, = x(ii) X((X,) (R) ((x (xi)) - e( Yo: 0 (xxx,) T(X.)
hhs (Z. x(x,)) =
(A: (x,)
(e( Vi(TT( O (X.)) T ((0()) ((x,) (X,) (x,))
[e V,(T(
(x.) (X: (x())
010 x(X,) (X,) 0i(x,)
< C2 a. 5,
max
- (X,) - (x,))
ad|M
where C2(0, (, = (1 + (g + n)) (0t///// + 5 + 1 is a constant. Let hs (Z, (Xx)) = (a(Zz,7((..)
Ex Z,, (X.)) Xi). and we have that
[h (xx)) (C, a. 6, max a aE[M]
(0()((x)) (x:))l
Next, we apply the bounded difference theorem conditional on Xy's:
P& sup Fell
Σ
bg( E& sup nell
Σ
ha ((xi))
x 2 x
[D(1]
[D(2)
(ED(A)
(ED())
12(
< exp
202( (,,0,,,,,,,0,))) 0),,) E EDD max.e[M]] (X.) 0: 0x()))1
for any > Taking C2(a, a 0,0, 2 EiEDIE) maxae[M] 0%'h) 100='(()) (X,) 0% (X,)) / /D(K)), we have with probability
at least 1 - 3 that
sup tell [D(1] (ED(A)
Σ
hn Zi, n (X.))
S E
sup
Σ
ha Zi, π (X:)) x
[D(A]
FEll
iED(A)
(,,0,,077,,000 [D(H)]
2 Σ
Σ
t (X,) (x:))
iED(
aE[M]
For the expectation thr same symmetrization argument as in the proof for K₁ (T) leads to
Eg
sup sell
[D(k)]
hz(Z, (x,)),((,i)
x
S 2E
sup xEll
D(()
1
Σ
x
(EDIK)
(ED())
Then by Lemma D.2, we have
E,
sup TEll
[
Σ
cohs(Zz. (z., [X.I)
tEDDA
2C2(a, 77, 5,
(32 + K(II))
Σ
) (X,) (x.))1
[D(1]
(EDIA) aE(M]]
26

---

Distributionally Robust Policy Learning under Concept Drifts
By Hoeftding's inequality, have that
1
PA
10 h (X.) O -100 0allia(Ps) 2 110 - -0.12.0.
log
3
-
D(R)
2n
KEDIK)
Taking union bound, with probability at least 1 - 33, we have that
sup Fell
KT(TT)
C2( a 8, (130 (x(II)
Σ
1 OallLa(Px) v M(ā 7)
log
M
1/4 )
V|D(A1]
|D(b)]
B
M
M M - Ballen Log(M/B8
(0(h)
02 0. (0 +
VID(AJ]
ME[M]
By Assumption 3.4, 110 0a [a(xx) = op(n and (10 0alla = =or(1), so there exists N2 2 N3 such that
when n 2 N2. with probability least 3/(4K),
Cola, 0r 0, 1,,
sup Kg(TT]] nell
(21)
4/n
Bounding Ka(T). For KL(T), we take
11(2,, 1(A, (Xx))
mo(A:1X,) (0=(x.) (X.) - (xxx))(Xi)) + (0 (mx(x)
(x.))
and therefore K1(x)= [D] EiEDus (T,,, Again by the unconfoundedness mmccofooodedessssssuupinio.
(xI = O.
Due to the overlap condition, we further have that
(x,(2,,T())) < 2 (2(0)) [x(x.) (X.) In(X)) (X.)) S max M
3h (k) (X.) Ia (X.))-
As before, we apply the bounded difference theorem conditional on X3's and the symmetrization argument to obtain
P
sup FENl
[T)
2 sup nell
1 [(k)
Σ
x] 2 2((x]
iED(
SP
sup
[T(T] - Ex sup
Ka(TT
X 2(|x)
nell
well
s² ((k) 2222
<
exp
2 2 DiED() m (Ma (Xi) Da (X:))²
We now apply Lemma D.2:
x < ViEEDO) maxae[M] (X.) - (x.))
Eg
sup
[D(b)
Σ
Gha(Z,, T (X+))
[D(A]|
(64 + 8k(II))
igDik)
By Assumption 3.4, there exists N₂ E N,, such that when n 2 N4. with probability at least - 8,
max
(((k)
0. I max(E, a, a, /2)
oE M
27

---

Distributionally Robust Policy Learning under Concept Drifts
On the event [ma |0% f. S <max(S, at a. n2/ we have for any E [M] that
[(z 0g (z)) (a,
On the same event, by Hoeffding's 's inequality, we have that
Pk
1 [D
Σ
(Q. (x.)))) - -10% ga -galli 2t exp (- (-8C
t² ((()(
8C1 (ā: a. 17, 6,,)
iED(K)
Taking union bound, we have with probability at least 2,3 that
max
Kn(TT]
_ @VIDDW))
(128 + (6x + 22log(1/8)
xell
( gollea(Px) + 2M
aE(
By Assumption 3.4, E l1aa 2.ll = (r(1), so there exists N 2 N4 such that when n 2 N2. with probability at least 1 - 3/(4K),
sup [a(TT) Colar a. 17, 1,,
(22)
4yn
well
Combining (18)-(22) and taking a union bound over & E [K], when n 2 max( N2, No. Na) we have that with probability least - 3,
sup 1iN (T) (T) - {T((T) < Colā,,,7,00
rIll
We have thus completed the proof of Theorem 4.3.
D.4. Proof of Theorem 4.6
We first state somes results from (Si et al., 2023) that will be used in the proof. For any p, q E [0, 1), define
D(p 4) plog (
(1 log (1=)), and ga(4) p.Daa 1s)
))
inf Pr
Lemma D.3 (Adapted from Lemma A17 of Si al. (2023)). For 5 0.2, 95(4) is differentiable and g6(9) 1/2 q E 0.64.
Note that our definition of 9s(g) is slightly different from that in (Si et al., 2023), so we include the proof of Lemma D.3 in Appendix F.4 for completeness.
For notational simplicity, we use d to denote the Natarajan dimension of the policy class II. By the definition of Natarajan dimension, there exists a set d data points (.1...., va) C shattered by II: there exist two functions f-1, (z1...... xx] + [M] such that (x;) # (Iz)) for any [d] and for any o E {-1.1] there exists II, such that (Tx)) Sa, (xg) for all [d].
Next, we construct class of distributions indexed by E [#1] that are "hard instances" for the learning problem. Fix any E { we construct distribution P. as follows. First, the covariate are drawn uniformly from {æ1...., FaJ. i.e.,
X; Lid Unif(fa1....... zal).
Given X,, the action A, is chosen according to the behavior policy To. where for any j E [d].
(2;)( = = 2'
E and (a æz)) = K-2
1-s for all # fi f2z)).f1114)
28

---

Distributionally Robust Policy Learning under Concept Drifts
The potential outcomes are generated as follows:
(z))) X = 2j ~ y Bern 1 1+ - {((f-((z))) Xx 2j ~ G Bern 1 - o,4
2 and Yi(a) = T BeBeeem (1/4) for all a * f((2z) f-1zz))
2
where A E (0,0.1) 0.1) is some constant to be determined later. Note that the distribution of (X,, A.) does not depend on a. By construction, is clear that the data-gent generrtnng process satisfies Assumption 2.1. For any p E {(1+ + A)/2, (1 - -4)/2,1/4/ log(1/(11 - p)) > 6. Therefore, the data-gent geta-generating process also satisfies Assumption 2.4. As for Assumption 3.3, suffices check the Bernoulli distributions with parameters (1 + /) (1 A)/2, 1/4, and can be verified. Since n 2 d², we can obtain 0, g. and Rg that converges at rate Op(n -1/4) (by stratifying on X), thereby satisfying Assumption 3.4.
We now proceed establish the lower bound. For any policy learning algorithm that returns म. the worst-case regret is lower bounded by the average regret over the class of hard instances we have constructed above:
sup Pp [R(T]] 2
Σ Epg [+)
2d
PEP
0E{+1}a
We now focus on the right-hand side above. Fix a E (#1]d. Recall that Ro(f) = Vo(TT)) - VV((). For the optimal policy value, there is
Vo(TT) = max E. #Ell
inf Qv X y
Eerix (x((X))
((x(()))+ + m(x)
-1) -x(X- ax(3)
max max Ep, #Ell a.1)
+((X)xxX exp
a(x)
((T(()) + n(x) -1) -n(x) a(x)
max max Ep,
- a(X) exp
(23)
a. REN
(x))
where the step (i) follows from the duality result in Proposition 2.3. We now take a closer look at the expectation above: by the construction of Po.
xxX))x)) exp (- (((((X)) + (XX)
-1) n((x a
Ep.
x(x)
1
(T(22)) + m71z)) 11) -n(x) axxz)) x zz
Ep. -a(x;) exp
7 j=1
(d(3)))
1
d
( xx1)) 1) Ep exp (- (T((T)))
n(xz)
Σ
-I)(I;;;) exp
a(1;) (-)((;))
X 23 -n(x)) - azx)))
d
j=1
Letting Pj - (T{zz) = 1|x =zz), we have
(- ((H(t)))) x Ti. Pj expepp(1/(((x))) +1 Pj,
Ep
exp
a(x;)
which is decreasing in pj and is minimized when (2x)) (x,)). By construction, such policy x is in I1. As result,
-a(x;) exp (- Y(Jo, (x;;)) + m(5)) -1) - axx)) x x3
(23)
max.
Ep
a.
(((1,))
j=1
1
exe (- (z))) + - - 17 a0 x x= zÿ
max Ep. 0.1)
j=1
(foo X 2,1 g (1+ A
inf QyIxEP(Pay 1=
EQ Ix
Qy
2
29

---

Distributionally Robust Policy Learning under Concept Drifts
The last step is because Y(So (xy)) X =; ~ B1 + 4)22). Similarly, for V(F), we have
Vs((T) = EP,x
inf Qr @ Beri (x((())
1
inf QrixEP(PoN11X-a
( EQrix ((f(2))) X == x=,,] xzg
d
1 d
Σ
- 2 ) - (x))0) (--A) 2
+ +
Combining the caleulation above, we have
d Σ
{ {a( - -g( -
2 }
R(A)
d
j=1
{ -+ o(1/2)}
+ + + fo,
@ 1
+(((()))) + (1,())))) (0( -1-++ =9(1/4)
Σ
7
j=1
1
d
4
Σ
( + (z, (9)
1(((x)) + (1z)),
2d
==1
j=1
where step (i) uses that g is non-decreasing (c.f. Cauchois et al. (2024, Proposition I)); in step (ii), E E ((1-A)/2, (1+4)/2), and step (ii) follows from Lemma D.3.
Next, we denote و(j] to be the vector a with the j-th element flipped. Then, we have
1
Σ
[RS(R(
1
Σ
E Pm
( A Sa, (15))
2d oE(+1)
2d
2d j=1
0E(=13d
Ppn (T((t))) # f1(25)) + PPay (f(z,) # f-1(1;))
d2++1
a:ay
A
Pps (Tzz)) # f((1,)) + PP (7(z)) f1
d2d+1
j=1
0:0,=1
Σ
(24)
d2d+1
0=10:0
where the last step follows from the definition of the TV distance. By Pinsker's inequality, there is
Div pmin)
< DKL (p
|| Pan)))
dP. dP
(X,, A,, y3)]
= Ep.
log
2 i=1
1 Σ
1(x, = x,, A = [z) Alog (+
Ep,
2 1=1
3ns A²
2d
30

---

Distributionally Robust Policy Learning under Concept Drifts
where the last step follows from I log( [ and d 2 4/(9)) and then
S 3x² for a E (0,1/3). Take A
18
V
d me
this is possible since n 2 d?
d2d-1
d
(24) 2 V n 15d2d42
120
YE
E. Generalization to Identifiable Covariate Distribution Shift
We now extend our methodology to handle situations where shift in X and Y ||X distributions are both present. We note that, in most practical cases, the decision maker has access to the covariates the target environment, making the shift covariate distribution identifiable and estimable is therefore unnecessary to guard against the worst-case shift.
Method. Formally, suppose have access to training dataset D collected in an environment P, and aims at learning policy that behaves well in the environment Q. Here, we assume that Qy xx E x for some given radius 8 >> 0 but do not impose any constraints on X distribution shift except that Qx is absolutely continuous with respect to Px and dQx
that the likelihood ratio is bounded. Letting r(æ) dfx (I), we can estimate r with from P and Q using standard tools (by directly estimating the density ratio or by means of classification algorithms). For any policy æ, the distributional robust policy value can be written as
V3(TT) = =xx Qy Ix Eqr x (T(()) x1]
inf
(25)
Note that the inner expectation of (25) the same as in (1). By Lemma 2.3, there is
exp (- ((T((X) + (x)) + (x) + af)
(25) F
(x)
IfA T(X))
(x(()) exp (- Y(A) 7 (x))
+ (x) + xx)6)
EQxxPrix
To
(X)
Ep r(x)
1(A 1{A= (LA=T(A [X))
O (X)
((A) + n (X)
(X) (x)))
To ()(A
(X)
The above expression ensures that the robust policy value is identifiable with the data accessible to the decision maker. With this representation, subsequent policy evaluation and learning are similar to the pure concept drift case, and we provide the adaptation below.
In addition to D. we let D = { denote the covariates from environment Q, i.e., X, Lid. Qx. Assume that limm,n-roe m/n 7. As before, we adopt K-fold cross-fitting scheme, where we split both D and D into non- overlapping equally-sized folds. For & E [K], we use DD+++) and ((+++) to obtain a p()), and (a (k)), estimates of No. r. and (a:,, ) respectively; we then use D(k+2) and (b+++) to obtain g(*) as an estimate for g The estimator of the k-tth fold
(X = (XX.]]
(10) 8 1
(T)
(X.
(kk) (x:)
(X,), (ED(A)
Σ
D
(1)
(A:
DIRI
(ED())
TO
and the final robust policy value estimator is Do(TT) = =- k Σk ((k) (T)..
We then obtain the learned policy via
WLN = argmax ((T)).
#Ell
where we apply the same computational trick as in the pure concept shift case.
Theoretical Guarantees. We now extend the theoretical guarantees to the general case. Since the proof similar to the pure concept drift case, the proof sketch is provided. As a prerequisite, we modify Assumption 3.4 be:
31

---

Distributionally Robust Policy Learning under Concept Drifts
(k) Assumption E.1. For any policy n, assume that for each E [K], the estimators a60) p(k), yx and the empirical risk optimizer 0 satisfy
| /
or(n ()) I1@[)) / |laalpx (m)())) 0p(n 74);
|0th) 0- (P op(n
[ 1 = op((),
for some 7/1 7/2 2 and "1 + 72 2 2.
Theorems E.2 and E.3 establish the asymptotic normality of the policy value estimator and the regret upper bound.
Theorem E.2. Suppose Assumptions 2.1, 2.4, 3.3, and E. hold. Additionally assume that dQx/dPx S C, a.s. some
constants C >>0 0, and that limm,n-+x m/n n 7.. For any policy π. X ++ [AM], we have vn- (Vs((V(T)) -v<(=)) 4 O0) where
r( = (()) x -cx(x,))-x(x3))) 9x(())) +7 Var(g=(X]] Ao(A X)
2 Var x
Theorem F.3. Suppose Assumptions 2.1, 2.4, 3.3, E.I hold. Additionally assume that dQx /dxx S C, a.s., for some
constants C > O, and that 1imo m/n = 7/ For any B E (0, 1), there exists N E N__ such that when n. 2 N, we have with probability at least 1 that
C(s(IT) v Tog(111)) (1/3)).
R₂ (TIN) S
n
where C' > O is a constant independent of n and II.
Proof Sketch. Recall that
(- 1/ + 7 (1) 2 (x)
G v) o (1r) exp
+ (17(2)) + (x)) and -=)x) (X, x =x]
can be checked that
= xxx)) (x
(25) Ep
To(A| X)
r(x)1{A = (x}) =(x))
()) go (X)) + +Exx 1 (X)]
EEp
no [A]] x)
So if we define VT(TT) = - 1 Σ k=
1((k) (m), with
K
(T)= = |D(
(T)
1
r(X,) 1 {A, = (X.)],
- -G)(X,)))9+x(())) + Dikk)
Σ In (X.), (EDi())
(A (X,)
(ED(A)
we have by the central limit theorem that
Vn ()(())))((T)) L N(0, oz).
As in the proof of Theorem 3.5, we can decompose the différence between 12(k) (TT) and DiAh) (T) as follows:
= 7 r(X,)1(A,=
((00 (T)
8 (T)
(2 (X,, Y,) (x,,
D(K)
To (X:)
iED(N)
1
Σ
1(A, xxx))
F(X,)
r(X,)
(X,, Y.) (2
D
(X.))
(X()))
iED(N)
A(X))
r(Xi))
+
Σ
1(A, = 7 x(x))
(xt - -xn(X))
D
(X.))))
To To(X.)
(EDIM)
1
r(X,) n (Xx))
1
(fth) (1) (Xi) - 9 (X,))
Σ
C (k) (X,) gr (Xt)).
[D(1]
xX()
|D(A)]
IED(M
tEDiA
(26)
32

---

Distributionally Robust Policy Learning under Concept Drifts
Following almost the same steps in the proof of Theorem 3.5, show that
((k) (())
(26) =Op (10 - -0 (mmeex))
+ +Op
r
nn 1/2 1/2
(xxx
(me())))
(1
-Or
11 gn dall ( )
+ Op (10tt) 9 ( in 1122)
(R)
x Lg(xx 1 (=)(x))
=0p(n 1/2). -/23)
Taking a union bound over E [K]. we can conclude (T( VT( + opp(n 1/2), and therefore (T())) is asymptotically normal. The proof of Theorem E.3 follows similarly.
F. Proof of technical lemmas
F.1. Proof of Lemma D.1
Proof of (1). Given 0, recall that our loss function is
((x, 0) (- (- 4 -1) -11 + ad.
exp
By the strong duality, optimization problem implies
0) X] is convex in by Proposition 2.5, the first-order condition of convex
VoLE ((1, ((TE)) x 2) 0.
Meanwhile, we can compute the gradient of ((x, y; 0) as
(xx, yi 0) = (1+ y + (1+ eep
(-
+
1 + 8,
da
a
0
((x,, y: =1 exep (-
y + 1]
-1 1).
(27)
0,
a
For any a such that la - a2,x)) < (x), we have
(x, yi (a, n (x))) s (1+ 2( + 11)
2( + 11)
11) + oc.
exp
da
By the mean value theorem and the dominated convergence theorem, we can change the order of expectation and taking limits and therefore
②
0 da = 02()) X z 0.
E
(xx,
((T))(((())))
(z)) x
Oa
Similarly, since o E( yi (x), m)) is non-decreasing in for |n (x)1 < 1.
@ 0 ((1, y: (z) mi) < max
{
2 D.
2 lxx y (x) + 1/)/ a
m
0, l(2, yi (a)()))
with the right-hand side being integrable under Py xx- Agian by the mean-value theorem and the dominated convergence theorem,
a
On la. (T(()): x = x
x = = 0.
On
We have thus completed the proof part (1) of Lemma D.I.
33

---

Distributionally Robust Policy Learning under Concept Drifts
Proof of (2). We now compute the Hessian of fxr, y; 0):
8a
(y) + 11)
1/ + 7
Jaz
(z, yi 0)
a33
exp
8
+ "
+ 1 -1 1).
(1r, v;
exp
dadn
a²
a
8²
(x, y:
exp (- y
-1) 1).
012
a
By the Taylor expansion,
(0-00(2)) + 1 20 (x)) (2(2,, (x)),,
0) f( 0z))
+ 1) (x,, (x)) Vl y O (x)) T -0-00 (x))
(y i)²
exp (- y |10 (x)
a3 á
à
where 0 = 10 + (1- (x) for some E [0, 1] and the last step is because
Pe y: 0) lopp - (y + i)
②)
1
exp ( (- 3 -1
ā
Let { min(a,,7/22 For any 0 such that
10- (z))
5, also have la (x) S E and I (x)) S &. Then
(v + 7)
exp (- (- - <
87
2
2y + 4 -1)
exp
2
ā
a
Letting the right-hand side be (1x, y), we have thus completed the proof of (2).
Proof of (3). By the Taylor expansion,
(x. 0) f(r,y; 0; = V ()) (0(x))0;(x)) (x)),
where 0 = (1- for some E [0, 1]. Let & = min(a, 72.2. When | 10-0; 4.x S E1, we have aá S &1
and [î - (x)) S &. Plugging the expressions of the gradient in Equation (27), we have
[((z, y; (ax)) - f(x, ys (x)))]² 2 = [v( y: (((x)) - 07 (z)))
y )+)
exp + 77(x)
11 5 2
+ exp ( (-
y y )+ 7(x) x(x))
-1) -1) })}}} 10(x)) 0;
a(zz)
â(x)
<C a. a. 5) 100(z) - (z) :
where C(j, ā a. 0) is function of (ū. a. az n7, 8). Taking the expectation over Px,Y |A=[)))))) have
|| O - (X ( SC(j,a,,,77.)) |0 0' (-)))))) (')
completing the proof of (3).
F.2. Proof of Lemma D.2
We first introduce the & distance on the policy space 11, as well as the corresponding covering number. Definition F.1. Given a function and set of realized data 21,... An.
(1) the Eg distance between two policies æ1, #2 II with respect to (21,..., zn is defined as
(z,,..,, zn3) = Σm (h(22, TI (xx)) h(2 (xx))))
4 1 czx))²
34

---

Distributionally Robust Policy Learning under Concept Drifts
N2(7, II; (a )n is the minimum number of policies needed to 7-cover II under lg with respect { zn)
Under the lg distance, we define sequence of approximation operators A,
II for j [J], where [log, n.. Specifically, for any 0, o,l,...,e J. let Sj be the of policies that 2-J-covers II and satisfies |sy| (2 TI; (Z1,-... 7n Specially, So { }. with is arbitrary policy in IT this is valid choice since for any 11.
( R; (2....., = Ei= (Miz2, (x;))) - M #(xi)))
1
E (2,)²
We shall let A 2VE - (2:)² to denote the normalization factor. The approximation operators defined in backward manner: for any π E II,
define A) argmin &2 (I n (21, -.,...,. zn]); T'ES,
(2) for j = JJ- 1..... 0, define
A argmin &g (As+1|=), 1211 ................................ 2n)). r'ES
Using the sequential approximation operators, decompose the inner expectation term in (17) (Rademacher complexity)
Eg
sup well
Σ (x,,)
< E,
sup TEIl
(((,), n M( AM
*E|n]
+ E,
sup
<: (i(, A,1-((X.)) -
-22 -
sEll
j=1
El|m
+ E,
sup well
(Z, (x11
sEin
E + E2 + E3-
For any i E II, by the Cauchy-Suhhee Schwarz inequality,
sup TEll
Σ
c: [[((2), h(,,, A [m]())
n
<E(m]
(1(=,,(<z)) - ha2s, A (s(T)xx)))
m
(e(n]
A
L2( Ay(T); (21.......
Vn
A A
2-
S
13/22'
where the second-to-lat step is because (T()) -J -lose to ा and the last step is by the choice of J. As a result the above derivation, E, < 3/23/2.
35

---

Distributionally Robust Policy Learning under Concept Drifts
Next, for any J use P3 to denote the projection of projecting a policy to Sj. i.e., A3-1(T] P3-1lA,(m) Once Az(z) is determined, 1 (л) is also determined. For any 0,
1 Σ
Pc
sup #Ell
G[M(z, A)(m((()) Az-
28
iE|n
Pe
Σ E: (
- h(zz, P3
(-
28)
r'ES;
(E(m]
2n²
2 exp
Ei=1 (x;))) - h(z,, P1
n'ES;
2n²
2 exp
A2 P)-1(T');
E'ES
22 II; Z) exp
A22-2j+1
we is a shorthand for {=1,-... }. For any j 1, 1,..., J and m E N, take
A n2/-1/2 1/2 V log (N2(2-),114 11;; 2)2m)) j2).
8jm
For fixed m, with union bound over .....,JJ J we have that
Pe
sup
4 ([((2,, A,(T(( - h(2, -2.
2 Σ sjm
nell
j=1
sEin
==1
1 Σ
1
P
sup nEll
(, - AZ.
2 sym
j
<
2
j=1
j=1
To proceed, we shall use the following lemma, whose proof is deferred to Appendix F.3.
Lemma F.2. For any realization 21, ......22 2n and O, there is N2(%, II; 21.... ..... 2n) S (2 II)
By Lemma F.2, for any E N_,
A
jmm
2 25-1/2p V
log (Na(2-i, II; Z) 2m+1 j2)
J=1
1=1
A
<
(2 + (m + log 2 + 2 log(j)
2 1/2
1=1
@ 2A
Σ
2ー
(V (2-2i,1)) + Vm +1+ (2log(j)
n
-=1
(18) 4A
(s(I)) Vm + +m+1+10 I+ =: Ums
n
36

---

Distributionally Robust Policy Learning under Concept Drifts
where step (i) uses va + +bbos va+ +b+ vetor a, b, O; step (ii) uses the definition of x(II). Then
22
E.
sup
Ay(T((z)) h(z,, A5- -
TEll
T
P
sup
h(22, (,(+](x4)) h(2, A, 1-- 1)-1 >5} ds
Ttll
n
ie(n
- 01
+
(1++1 uk) 2-k+1
k=
4A
(a(II) 12++++
- 1 n
4A (II[IT) +7).
n
Finally, consider E.. Recall that S { and therefore
E3 = E.
1 Σ sh(2,,,(z))
Pe
Σ e.h(zi -(;))
> } 5)dd
ds
tE(m)
iE(m
n22g²
= 31
2 2exp
ds
A2
Putting everything together,
A (4x(II) + 32)
Eg
n
n
2 E cz,)) (4k(1I) + 32).
F33 Proof of Lemma F.2
Fix 7 O. If (1 III oo, the lemma is trivially true. Otherwise, let No (1; For any realization 21, ....... An define
(Ti T(22)
argimax (1h(2, (1:))))((((())))) - m2,
Implicitly, (Ij,1, v2.2) depends on z;. For an arbitrary positive integer vn and i E [n]. we define
m
(h(2,, (x:)) h(z,, ((zz)
n,
A2n
where we recall that A² = E (z(z;)2 We then construct a new set of data
( ]N} ...,..., 21, #2.... 22, Bn...., kn)
where 2; appears n; times and
7 N
(1(2,, (i (x,()
ME, (1;)))())))) < +
14
2
37

---

Distributionally Robust Policy Learning under Concept Drifts
By definition, there exists policy So be -o-ver of II the Hamming distance with respect ö = ( .N. such that |Sol No- As result, for any IT, there exists n' So such that H(T n'; S r²- On the other hand,
((((at) (
(1:( # x' (x,))
m
[h 711 - h(2, (z {{(())) # *(())))
N
A
- -(2 ((((x;) + ((:))
ao (1(2 ((.)) - M (xx))
Above, step (i) and (ii) follow from the choice of and (मf 22 respectively; step (iii) because when (Tx,) x (x;). M22, (x;)) h(,, (x{)). By the definition of the lg distance and that N I n, further have
2 n';,,';;)
l (T, 22)
(m + n)
Since m is arbitrary, take infinity and have ET x²; 7. respect to ..,.... An. and therefore N2(7, .l, =n) S (1I1..1I).
By definition, So is a y-cover of II under l with
E.4. Proof of Lemma D.3
By Yang al. (2022, Lemma B12), (o(g) is differentiable in q. and
0, (xL(()))
s(4)/9 (1 g(g))((1 - ②) log (g(g)/(1 g(4)) log (1/(1 4))
db(() (g
Also by Yang et al. (2022, Lemma B12), go (g) is convex in q, so g5(g) is increasing in q, Since E (0.4.0.6) g5(g) 2 g' (0.4). From the dual form, we can check that g(0.4) 2 0.1. Plugging q = 0.4, we have
g(0.1) g(0.)) 5/3
g0..4)00.24 5/3
(0.4) log (g(0.4)/(1 - 9(0.4))) - (2g()/3) log(g(0.4)/(1 g(0.4))) log(2/3)
Since the function f(x) (g(=/(11=)) -ogg)))) is increasing in x for x E (0, 0.4), we conclude that
2/0.24-5/3
1/2.4 5/3
db(0.4) log(1/9) - log(2/3) 2 1/2,
completing the proof.
38


Reviews:
[{"review_id": "O9f7m7VixE", "reviewer": "Reviewer_wdwV", "summary": "This paper develops a distributionally robust policy learning framework under concept drift by focusing on shifts in conditional reward distributions while assuming stable covariate distributions. It introduces a doubly robust estimator with root‑n convergence for policy evaluation and proposes an efficient policy learning algorithm with optimal regret bounds.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n[1] Si, N., Zhang, F., Zhou, Z., and Blanchet, J. Distributionally robust batch contextual bandits. Management Science, 2023.\n\n[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.\n\n[3] Athey, S. and Wager, S. Policy learning with observational data. Econometrica, 89(1):133–161, 2021.\n\n[4] Zhou, Z., Athey, S., and Wager, S. Offline multi-action policy learning: Generalization and optimization. Opera- tions Research, 71(1):148–183, 2023.\n\n[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.\n\n[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.\n\n[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).\n\n[8] Kallus, Nathan, and Angela Zhou. \"Policy evaluation and optimization with continuous treatments.\" International conference on artificial intelligence and statistics. PMLR, 2018.\n\n[9] Rosenbaum, P.R. (2002). Observational Studies. Springer Series in Statistics. Springer, New York, NY.\n\n[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.\n\nWeakness\n\n1 See Question 1\n\n2 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. \n\n3 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.\n\nComments and Suggestions\n\n1 In terms of cross-fitting and de-biasing technique, we have added more detailed explanation in our manuscript.\n\n2 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.\n\n3 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.\n\nSee Question 2 for generalization to continuous action space.\n\nQuestions\n\n1 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.\n\n2 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.", "claims_and_evidence": "The paper supports its claims through rigorous theoretical proofs (e.g., asymptotic normality and regret bounds) and empirical studies comparing with benchmark methods. However, some claims rely on strong assumptions for nuisance parameter estimation, which might require additional discussion.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are well-tailored to the problem of concept drift. The separation of conditional reward shifts from joint distribution shifts is well motivated, and the use of simulated experiments with cross-fitting provides a reasonable evaluation framework.", "theoretical_claims": "I reviewed the proofs for asymptotic normality and the regret upper/lower bounds. They appear methodologically sound.", "experimental_designs_or_analyses": "The experimental design is robust, featuring multiple data splits, cross-validation, and a clear comparison against an established benchmark. However, the reliance on simulated data and sensitivity to hyperparameters may limit insights into performance on real-world datasets.", "relation_to_broader_scientific_literature": "The key contributions relate closely to recent advances in distributionally robust optimization and double machine learning. The work refines prior approaches—such as those by Si et al. (2023) and Mu et al. (2022)—by targeting concept drift specifically.", "essential_references_not_discussed": "While the paper cites relevant studies, it could benefit from discussing additional works on robust inference under distribution shifts, particularly recent advances in DRO and robust causal inference that address similar issues in a broader context.", "other_strengths_and_weaknesses": "Strengths:\n\n1. Provides a clear theoretical framework with rigorous proofs and optimal regret bounds.\n\n2. Effectively integrates doubly robust estimation with de-biasing and cross-fitting techniques.\n\n3. Presents a well-structured algorithm and detailed explanation of the methodological steps.\n\nWeaknesses:\n\n1. Relies on strong assumptions for nuisance parameter estimation rates without extensive empirical sensitivity analysis.\n\n2. Some derivations, especially in the ERM formulation, lack complete justification.\n\n3. Limited discussion of potential drawbacks or failure cases in the simulation setup.", "other_comments_or_suggestions": "1. Clarify the presentation of cross-fitting steps and the functions involved in de-biasing, as some parts could benefit from more detailed explanations.\n\n2.Provide additional details on hyperparameter selection in the simulation studies and discuss potential impacts of different settings.\n\n3.A brief discussion on how the methodology might generalize to real-world data or continuous action spaces would enhance the paper's practical insights.", "questions_for_authors": "1. What is the effect on the overall estimation error when nuisance parameter estimators converge slower than the required rate?\n\n2. Can the proposed ERM and de-biasing approach be efficiently extended to handle continuous action spaces?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kuqRK7Jmio", "reviewer": "Reviewer_fxks", "summary": "This paper investigates distributionally robust policy learning with concept shift. While this problem has been previously studied in the literature, the current work extends to a more general setting where the context space is not necessarily finite. To address this generalized setup, the authors propose a doubly robust estimator. The paper demonstrates that the policy value estimator exhibits asymptotic normality when the nuisance parameters are estimated with sufficient accuracy. Besides, other key contributions include establishing upper bounds for general spaces and providing corresponding lower bounds.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nClaims and Evidence\n\n1&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.\n\nWe 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.\n\nIn 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.\n\n3 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).\n\nWe 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].\n\nMethods 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.\n\nTheoretical 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.\n\nRelation 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. \n\nMost 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.", "claims_and_evidence": "I found the problem setup with exclusive focus on concept shift to be somewhat artificial. If there is only concept shift without uncertainty about the marginal distribution of the context $X$, it seems more natural to optimize the policy for each $X$ *individually*. Indeed, when $\\Pi$ encompasses all possible policies (or rectangular in the sense that having separate constraints for each context), by the interchangeability principle, the optimal policy that solves equation (1) satisfies:\n$$\\pi^*(X) \\in \\arg\\max_{p \\in \\Delta(A)} \\inf_{Q_{Y|X} \\in \\mathcal{P}(P_{Y|X},\\delta)} \\mathbb{E}_{Y|X}[Y(p)|X],$$\nwhere $\\Delta(A)$ is the set of randomized actions. \n\nThe restriction to specific policy families in the paper typically serves the purpose of generalization—learning a policy that performs well across the entire context space. However, the concept-shift-only setup implies no need for such generalization since $P_X$ is assumed to be known exactly. While there might be practical applications requiring certain policy forms or impose constraints across different contexts, apparently the paper does not focus on these considerations. To me, the joint or separate uncertainty in both $P_X$ and $P_{Y|X}$ makes more sense to me.\n\nFurthermore, given the assumption of no uncertainty in the marginal distribution of context $X$, one would expect generalization error bounds that are stronger than those presented in the paper, potentially avoiding the curse of dimensionality described at the end of Section 3.1. It's particularly concerning that Assumption 3.4 requires a dimension-independent convergence rate, which the results in Section 3.1 cannot achieve for high-dimensional spaces without imposing unrealistically strong smoothness constraints.", "methods_and_evaluation_criteria": "The numerical experiments would be substantially strengthened by including real-world datasets to demonstrate the effectiveness of the proposed method. Currently, the empirical validation appears limited to an artificial synthetic data, which may not fully capture the complexities encountered in practical applications. Having real data also helps solidify the concept-shift-only setup investigated in this paper.", "theoretical_claims": "The results look reasonable to me and the proofs are quite standard, although I did not check every detail and I wonder if they are optimal or too conservative given that the context distribution is assumed to be known exactly.", "experimental_designs_or_analyses": "As mentioned above, I think the experiments are too preliminary and it would be nicer to have real datasets support the assumed setup in the paper.", "relation_to_broader_scientific_literature": "In the literature, both joint and separate uncertainty in concept and covariate shift are studied. This paper focuses exclusively on the concept shift. It might have important applications and implications, but unfortunately the paper, in its current form, does not articulate it well.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "NA.", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rx521BwRxf", "reviewer": "Reviewer_YrNk", "summary": "This paper propose the distributionally robust method for offline bandit under concept shift, where the P(Y|X) is shifting. They propose a doubly robust method and DRO under KL divergence for offline policy learning. And they show the Asymptotic normality of the ope and propose a policy learning and the corresponding regret bound.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nClaims And Evidence\n\n1 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.\n\nIn 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.\n\n2 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.\n\nExcept 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.\n\nIn 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.\n\n3 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.\n\nOther Comments Or Suggestions\n\n1 See Claims and Evidence 2\n\n2 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].", "claims_and_evidence": "1) 'To be concrete, imagine that the distribution of covariates changes while that of Y | X remains invariant — in this case, the distribution shift is identifiable/estimable since the covariates are often accessible in the target environment. As a result, it is often unnecessary to account for the worst-case covariate shift rather than directly correcting for it.' This is not true, when there is some OOD data, especially in RL. \n\n2) Comparing with [1], what is the other difference except for the doubly robust estimator and you are only considering the concept shift instead of the joint shift?\n\n3) Is it possible that you provide some bias and variance of the proposed value estimator? And what is the benefit of Asymptotic normality, or in other word, why do we want this or what is the advantage compared with other estimator that is not Asymptotic normality?\n\n\n\n[1] Si, N., Zhang, F., Zhou, Z., and Blanchet, J. Distributionally robust batch contextual bandits. Management Science, 2023.", "methods_and_evaluation_criteria": "Looks good to me.", "theoretical_claims": "Yes. I check the proof of the regret bound.", "experimental_designs_or_analyses": "Yes. I check the whole data generation process.", "relation_to_broader_scientific_literature": "Provide a reliable method for the policy learning under concept shift, which is crucial for domain adaptation under the concept.", "essential_references_not_discussed": "The following paper also discuss the DRO for policy learning, maybe you can also discuss in the related work. \n\n[1] Distributionally Robust Policy Gradient for Offline Contextual Bandits", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "Maybe highlight the difference of your method compared with [1]. \n\nDiscuss (Hamming entropy integral) intuitively, currently it is hard to follow. \n\n[1] Si, N., Zhang, F., Zhou, Z., and Blanchet, J. Distributionally robust batch contextual bandits. Management Science, 2023.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a study on distributionally robust policy learning, specifically focusing on concept drift. The proposed methods and theoretical analyses are reasonable and the implementation appears sound. 

However, the core ideas presented in this work, such as the separate treatment of covariate and concept shifts via DRO, the use of doubly robust techniques for evaluation and learning, and the derivation of learning guarantees, are not entirely novel and have been well explored in existing literature. While the paper presents extensions in several aspects, the overall contribution is perceived as somewhat marginal in light of the existing body of research. Therefore, I recommend a **weak acceptance** of this paper.
Decision: Accept (poster)