Factored DRO: Factored Distributionally Robust Policies for Contextual Bandits
Authors: Tong Mu
Yash Chandak
Tatsunori Hashimoto
Emma Brunskill
Venue: NeurIPS 2022 Accept (2022)
Keywords: Contextual Bandits
Distributionally Robust Optimization
Distribution Shifts

Abstract: While there has been extensive work on learning from offline data for contextual multi-armed bandit settings, existing methods typically assume there is no environment shift: that the learned policy will operate in the same environmental process as that of data collection. However, this assumption may limit the use of these methods for many practical situations where there may be distribution shifts. In this work we propose Factored Distributionally Robust Optimization (Factored-DRO), which is able to separately handle distribution shifts in the context distribution and shifts in the reward generating process. Prior work that either ignores potential shifts in the context, or considers them jointly, can lead to performance that is too conservative, especially under certain forms of reward feedback. Our Factored-DRO objective mitigates this by considering the shifts separately, and our proposed estimators are consistent and converge asymptotically. We also introduce a practical algorithm and demonstrate promising empirical results in environments based on real-world datasets, such as voting outcomes and scene classification.

Factored DRO: Factored Distributionally Robust Policies for Contextual Bandits
Tong Mu
Yash Chandak University of Massachusetts ychandak@cs. umass edu
Stanford university tongmOcs. stanford.
Tatsunori Hashimoto
Emma Brunskill
Stanford University chashim@stanford edu
Stanford University ebrunêcs. stanford.
Abstract
While there has been extensive work on learning from offline data for contextual multi-armed bandit settings, existing methods typically assume there is environ- ment shift: that the learned policy will operate in the same environmental process that of data collection. However, this assumption may limit the of these methods for many practical situations where there may be distribution shifts. In this work we propose Factored Distributionally Robust Optimization (Factored DRO! which is able to separately handle distribution shifts in the context distribution and shifts in the reward generating process. Prior work that either ignores po- tential shifts the context, or considers them jointly, can lead to performance that is too conservative, especially under certain forms of reward feedback. Our Factored-DRO objective mitigates this by considering the shifts separately, and our proposed estimators are consistent and converge asymptotically, We also introduce practical algorithm and demonstrate promising empirical results in environments based on real-world datasets, such as voting outcomes and scene classification.
Introduction
In many real-world applications we often have access to historical data about past decisions and their associated outcomes. This data can leveraged for off-policy learning to optimize for decision making rule, called policy, that is more effective for the given application than that used for data collection. Off-policy learning from historical data for contextual multi-armed bandit settings has been well studied, due in part to the myriad of potential applications; from personalized recommendation [Strehl et al. 2010 to optimizing medical treatment [Kim et al. 201 Prior methods often focus on the stationary setting, where the learned policy will be deployed in setting with the same underlying data generation process that produces the observed contexts, and rewards upon intervention [Precup] 2000 Liu et al. 2018 Kallus and Uehara 2020a b Liu al., 2020).
However, in many settings, this assumption is not true and the distributions may shift.
As motivating example, consider the problem of increasing political participation during elec- tions using various interventions to encourage voting. In the past, different strategies have been implemented, ranging from reminding people of their own voting history, to reminding them of the voting history of their neighborhood, etc. [Gerber et al. 2008). Leveraging this historical data, an important question is: what strategy should be used during the next election to maximize political participation? Addressing this question requires careful consideration of two potential sources of
httpp:://github.comm/ htwp://pwgggggtto.oooooooaoeaaae
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

distribution shift: (a) How much has the population demographic in the area changed since the past data was collected? (e.g. the percentage of single person households may have changed due to change and developments in the city.) (b) How much has the effectiveness of each strategy on each demographic group changed? (e.g. as technology develops, the effectiveness of mail-based interventions may change.) Such challenges are ubiquitous in real-world problems. For example, in automated healthcare, data from patients of one locality may be used to develop treatments for other localities where the effectiveness of treatments may differ [Finlayson et al. 2021]. Similarly, recommendation systems need to account for both the changing interests and the demographic shifts of their user base [Koh al.) 2021]. Developing general procedure for addressing these challenges can provide a reliable solution for such applications where there may be high stakes in societal behavior, public health, or monetary assets.
Without considering potential shifts, there a risk of using suboptimal strategies, however is often difficult to predict exactly the shifts that will occur. Distributionally robust optimization formulations such as ours attempt to address this uncertainty over potential shifts by learning policies that attain good performance on all potential distributions within a user-defined set of distributions (denoted the uncertainty set), Prior methods for contextual multi-armed bandits (Si et al. 2020 Mo et al. 2021, Kallus et al. 2022] that aim to provide robustness against distribution shifts do not separate the different sources of shifts, and consider them in a joint formulation. These methods may be disadvantageous they lack the flexibiliiyy separate the sources. Consequently, we empirically find and show that some of these methods may produce degenerate results under binary reward feedback. This issue is theoretically proven to occur in the DRO literature in supervised learning (Hu et al. 2018). Due to this, methods that better use structure to mitigate this issue have been an active area of research in the supervised learning DRO literature (Sagawa et al. 2019) Duchi et al. 2019]. Inspired by this, our insight is that better usage of structure is important, and there is often expert opinion about the maximum amount of distribution shift that may occur that can be used to achieve better performance on the deployment environments.
In this work we incorporate this insight in the framework of contextual bandits. We propose our Factored Distributionally Robust Optimization (FDRO) algorithm that uses past data to search for a policy that has the best worst-case performance, when the context (e.g.. population demographic) or/and the reward model (c.g., influence of strategies on voting behavior) can be different from the ones during data collection. Towards this goal, we make three primary contributions:
I.
We present factored distributionally robust optimization formulation for contextual bandits that provides end-users the flexibility to separately specify different amounts of potential shifts in the two main sources of uncertainty: the context distribution and the reward distribution. Our factored formulation can overcome some failure cases of non-factored prior methods [Si al. (0200).
II. We establish theoretically that the proposed estimators provide convergence at a rate of o [lg(nn)/) in evaluation of any policy's worst-case performance under distribution shifts, as well as to a policy with the best worst-case performance.
III. Building on our theoretical insights, we develop a practical algorithm, FDRO, that uses function approximation and Taylor series expansion. We show that FDRO provides promising empirical results on several domains based on real-world datasets.
2
Related Works
Both off-policy learning for bandits and reinforcement learning, as well as distributionally robust optimization (DRO) for supervised learning and stochastic optimization have rich histories of research. To briefly summarize, methods for off-policy evaluation/lcarning predominantly assume that the
deployment environment for the learned policy will be the same as the environment the historical
data was collected in [Precup] 2000, Jiang and Li 2016 Thomas and Brunskill 2016a b Gelada and
Bellemare| 2019 Liu et al.] 20188] Imani et al. 2018 Yang al. [020] Jiang and Huang] 20200] Kallus
and Uehara 2020a b. Liu et al. 2020]. In contrast, DRO methods for tackling distributiona shifts
have predominantly focused on settings like supervised learning, and do not consider decision making
aspects present in (contextual) bandits [Bertsimas and Sim| 2004| Hu and Hong 2013] Namkoong
and Duchi 2016 [Shapiro] 2017 Duchi et al. 2016)] Duchi and Namkoong 2018 Hashimoto et al.
2018 Duchi et al. 2019 Sagawa et al. 2019 Oren et al. 2019 Michel et al. 2022
2

---

In addition to the prior work already previously mentioned in Section !1 there have been few recent papers investigating DRO for use in bandits and reinforcement learning Some works use DRO to account for the mismatch between the true distributions (of the context and rewards) and the observed empirical distributions (Swaminathan and Joachims 2015a by Faury et al. 2020, /akhi et al. 2020]. These methods account for the potential errors of finite data estimation, and, under infinite data, they converge to the best training distribution policy. However we are concerned with the setting when the test distribution may be different, and the best training-distin caining-distribution policy may not be optimal.
There has also been other work that consider settings when different forms of information are available a priori. For example, in settings where knowledge about the distribution of covariates during evaluation [Kato et al. 2020]. bounds on the ratio of train-eval covariate distribution (Hatt
et al. 2021, Giguere et al. 202TJ, bounds on train-evaluation performance differences CChandak
et al.
2021]. J, the causal directed acyclic graph [Subbaswamy et al., 2019 Singh et al., [021], or when
there is data through time that can be used to model potential non-stationarity [Thomas et al. 2017
Chandak et al., 2020 Xie et al.) 2020 Qin and Russo 2021 have been considered. While relevant,
they look at complementary problems.
3 Preliminaries
In this work, we consider the batch setting where the goal is to learn from an existing dataset D. We consider setting with discrete actions, where A denotes the set of i discrete actions, A. Let X' Rd denote the set of contexts, X. A policy π denotes a mapping from a context X to distribution over actions. For a given context X and action we observe stochastic reward R. We assume the dataset, D, consists of independently collected datapoints, each (context, action, reward) triplet:
D = {X,, A;, R₂ =- For this dataset, we assume the actions are selected with some data collection policy To where A; ~ To(-(X;). We assume there is an underlying context distribution Pao. and for each context-action pair there is an underlying reward distribution PralX.A- We additionally assume the observed contexts, X; are independent and identially distributed (i..d.) draws from Pag. and the observed rewards are i.i.d. draws from Pr. We assume Pzo is known while Proj A.,, is unknown.
We consider using D to learn a policy ı that will achieve the highest worst-case-rent deployment environment may be shifted from the one of data collection. Given a fixed policy, there are two ways the environment can shift and change the distribution of future outcomes. First the context distribution can shift so the inputs we see are different. Second the reward generation model can shift, changing the reward distribution of each (context, action) pair. We assume the exact shift not known, so we would like to learn a policy that would do well on all environments within user specified set of distributions of the context distribution Pa and reward distributions P PRIX.AL Formally, given D we aim to find the policy that optimizes the following distributionally robust objective:
when the
TFDRO E argmaax inf Ep. FETI P.EFep
Ex
inf P.EEFoIX.A
Ep, [R]
In Equation I the uncertainty sets 1. and F. describe the set of possible distributions, P. and Pa. respectively. The optimization set IP, 1P.r1.... .A is conditioned on random variables X ~ Pz and A ~ T-) We term our objective Factored-DRO as we have two layers of distributionally robust optimization, first over reward shifts PRIX,A. and another over context shifts Pz.
For theoretical analysis, we make the following assumptions common in prior literature Si et al.
2020 Swaminathan and Joachims 2015a Kallus and Ucharal 2020a]
Assumption 1. Assumptions on To and the reward distribution
(i) Unconfounded: Rewards are independent with A conditioned on X: (Rx,A1 Rx.Ag--)) 11 A|X
(ii) Bounded reward support: 0 S R S Ry for all rewards for a finite RM
(iii) Coverage/Sufficien exploration: To(A(X) 2 for all (X, A) E X x Afr some Ex 00
(iv) Positive density of rewards: Let fRIX,A A be the pdf (continuous case) or PRIX,A A be the pmf (discrete case) of the reward distribution PRIX,A- Then assume, for all reward distributions involved. it holds that fRIXA= 2 & (continous) or PR,X, 2 cr (discrete) the support of of R for all
(X, A) E X x for some &, > O.
3

---

We make an additional assumption, which we do not require in our practical algorithm: Assumption 2. Discrete contexts with sufficient mass: The context set X is a finite discrete set and the probability mass of each context is lower bounded with Pao (z = X) 2 cx for some cx > 0
Note about model misspecification: Context shifts are an issue when we have model misspecifica- tion and cannot model the best action for each context. In these cases, the learned model encodes the biases of the population distribution. Model misspecification can occur when the model is under-specified for example, to reduce variance (bias-variance tradeoff), for interpretability. or due to unobserved variables. Misspecification also occurs when the model is over-specified, where it may overfit and not generalize (ex. neural networks [Sagawa et al., 2019]). The real world is often complex and difficult model correctly, so throughout this work assume the misspecified setting.
Prior Work with Joint Shifts: Recently Si et al. [2020] proposed an algorithm for solving a DRO formulation for contextual bandits that does not separate the context and reward shift. They consider the optimization problem: π = argmax, inf PEPr. [p[R] where P encapsulates the joint distribution contexts and rewards and IP.. = [P: (u((PIPP S 8).
Degenerate Outcomes with binary rewards under the joint objective: Unfortunately. the joint formulation may have a key limitation in the common setting of binary reward outcomes (ex, clicked or cot-clickedd(huu et al. 201T]. voted or rud-not-voteGGerber et al. 2008). etc). In supervised learning (SL), similar DRO formulations have been theoretically proven to fail with certain loss functions. Hu et al. 2018 prove that when features are continous, and 0-1 classification loss is used, the DRO objective equivalent to the standard, non-robust optimization of the loss function on the training distribution. Intuitively, DRO can be seen as changing the weights of the datapoints based on the incurred loss, and increasing the radius parameters increases the weights on datapoints with larger incurred losses. However, under 0-1 loss, DRO upweights all missclassified examples equally, which does not change the decision boundary. Consequently, in SL, methods that can mitigate this issue by using structure, such as Duchi et al. [2019] or Sagawa et al. [2019], have been proposed. We observe this issue empirically for the joint formulation in the binary reward case (see Section 6 P Intuitively, the lower reward points for each context action pair are all upweighted equally the learned policy is equivalent to that optimized for the training distribution. Our method, which trades-off adding an additional hyperparameter with better structure usage to separate out the shifts mitigates this issue.
4 Factored DRO for Policy Evaluation and Learning
In our work, we consider uncertainty sets defined on the KI. radius from the data collection distributions. Due to the joint decomposition, we require the user to specify two KL-radius hyperparameters, & and ón. for rewards and contexts respectively as opposed to a single hy- perparameter required in prior work. The uncertainty sets defined in Equation I are defined as P Pro/X.A= = {P, Dia(P Pr,, Pro)X.A) < de) and Pz, = (Pa : Daa Pzo) 8,).
We can decompose our DRO objective from Equation I into two steps, first policy evaluation step which given policy evaluates the worst case policy reward. Notice the policy evaluation step itself can be separated into two steps: a step considering the potential reward generation shift (Q x.)) and a step over the potential context shift to arrive at the desired value (V))))
((x)
inf Ep, [Ex (Qx,1]] where Qx,1
inf ER-P. [R]
P.EPxo
PrEF.gix.A
Second, we have policy optimization step over the worst case policy rewards:
#FDRO
argmax V(T)
In this section, we present our estimators for policy evaluation and learning and our convergence guarantees. We give all result from prior work used and all full proofs in the appendix.
4.1 Policy Evaluation:
We start by discussing the policy evaluation step. Equation 2 as written a difficult constrained optimization over probability distribution space. Fortunately, prior work (such as Hu and Hong
Note. Si et al 2020 show good results in an enviromment (voting) which originally had binary rewards, but they transform the environment rewards to non-binary by shifting all rewards by different offset per action.

---

2013) ) exists that uses methods from convex optimization to transform the problem to an equivalent simpler convex optimization over a single scalar. They use convexity of the original objective and strong duality to derive an equivalent dual objective. We arrive at the following equivalent problem by applying this duality procedure twice, once for each layer.
Theorem (Strong Duality). The optimization problem in equation
equivalent to solving:
Ex [ Qx.Al
((T)
min dz
az loggogExxor ExwPro
exp
+ agdu {
(4)
Ox
-R
where Qx,A =
min a.30
log BR
exp
+ aode
(5)
Ole
Proof Sketch This follows from applying Theorem 1 of Hu and Hong
2013
twice.
We will use this easier optimize dual form derive estimators for policy evaluation. We will first consider the potential shift of the reward distribution each (context, action) pair and calculate
estimates of x of Equation We will then use these values to perform the second DRO layer over context shifts to estimate V (*) (Equation
4.1.1 First DRO, Reward Shift:
For theoretical analysis, consider the setting when the context and action sets are both finite and discrete (Assumptions 1.2 and 2). Therefore we have a finite number of unique (X, pairs, each which occurs with non-zero probability. For given (X, A) pair, let Rx,4 correspond to the set of the observed reward R, every time (X, A) is observed in D: Rx.AA = {R; (X;, A,, R,) E D if X; X, A, A). Additionally, let maa Po(z; (2, a)n denote the expected number of datapoints in each (X, A) bin and recall that &e denotes the user specified KL-radius of the ambiguity set For every unique (X, A) propose the following estimator for worst context-action reward for Qx,1 in equation
-Ri R2 Ore }]}
1
Qx = min
ae log
exp
+ aede
(6)
0r.300
Miza RGERX,A
Note that the objective inside the minimization in equation 6 is convex in Or for az > 0, therefore many optimization methods (ex. gradient descent, bisection search) are able achieve the global optimum when O₂ * O. We give the gradients and proof of convexity in the appendix. Additionally, note the Qx.A's 's only depend on D and do not depend on æ, therefore they only need to be computed once and can be used throughout the rest of the policy evaluation and optimization procedure.
4.1.2 Second DRO, Context Shift:
With the Qx.A values estimated above for each (X, A) pair complete the policy evaluation. Let & denote the eser-specified KL-radius for context distribution shift, then with the computed Qx,a for each (X, A) pair, we can complete the policy evaluation and estimate V(x)) from equation
(
EmEA (aaAT(((XXX)))) + andz }
(TT
min Our log a=>0
Σ Pao Pao (x) exp XEX
O₂
We can show that when 5, > and a > 0 policy evaluation converges at rate O (l)g()//m):
Theorem 2 (Convergence of policy evaluation). For n 2 a with probability of at least 6:
(2log(2)X) the following holds for any ( (z,0))=
-(+)) so ( log(n) log
2|2
32( 1/ma )
where c=
(8)
n
Se exp(
Rman
)p
(x, a)
3.
'Note it is also possible to provide different (X.A) for every unique (X, A), or different d per action. however this greatly increases the hyperparameter burden the end-user.
5

---

and Po (z, a) = (a, Po(z, a) 2 cxCx is the minimum over probability of occurrence of (X.A) pairs, and a. is the minimum value for ae.
Proof sketch: We utilize a uniform convergence result from stochastic optimization and local Lipschitz-continuigg to prove the desired result.
Note the objective in equation
is also convex and easy optimize for Or 0.
4.2 Policy Learning
We now consider the optimization over policy of equation g Define the true robust optimal policy as n TDDRO argmnx, (TT), with true optimal robust value V V(r*). Define the empirical robust optimal policy as R* argmax, V(x) with empirical robust optimal value V V (+*"). We additionally define the set of e-optimal policies II; = { V(x) 2 V -c.. We then have the following statement of the convergence of optimal policy and value:
Theorem 3 (Convergence of Policy Learning). For n 2 ( (a.0))
(2 the following holds with
probability of at least
5:
log(n) log
V- V- 50 e
n
Equivalently this says
P - (2/11]1/) -
exp (- ne2 Tog(n)
(TTog(
(10)
While this policy optimization is generally non-convex, for many policy classes we can use gradient ascent with multiple restarts. To learn policy, we first compute the Qx.A values of Section 4.1.1 we then perform alternating steps of the evaluation step in Section 4.1.2 and the policy optimization this section (Section 4.2
Practical Algorithm with Function Approximation
Our estimator for solving for the worst case reward shift value, Qx.a for each context action pair in our first DRO step (section 4.1.I) relies having sufficient number of datapoints per each (X, A) to approximate ER-PRIX.A eeep( ( (((/RR/au RR)),]] = 1/mza Σ, exp(-Rg/aa. However, in many settings, contexts may not be discrete and, these cases, each continuous context may only be observed once. One approach can be to discretize the context space, however selecting the correct discretization is challenging. Too coarse a discretization introduces looseness and leads to overly conservative results, but too fine discretization may not leave enough items in each bin accurately estimate E PR-xx. [cxp(- (cxpp. R/ aa))) To handle continuous and/or large contexts spaces, instead of binning we use function approximation that may not have the same convergence guarantees. Fortunately, as we show in Section 6lit can be quite accurate and lead to better results than the baseline methods. We develop empirically stable method for estimating ER-Pn x.A Taylor series approximation. The key feature of our method is that it does not require fitting the exponential dependence on R and 1/a.. We found alternate methods, such as fitting an approximator for ER- PRIx [exp(- RR/ae) directly by fitting exp( ax)) using corresponding values of X,, A and multiple values aa value sampled from the relevant range, to unstable at small values of az due to the exponential dependence.
ov..] using
5.1 Approximating ER-Pa x. (xp(-RRaa.))
We can use the Taylor series expansion, Ee= (1/a.)' 11/00" B(( B((-R)), to estimate order approxi- mation. We this by fitting multi-output function approximator, F to approximate the first m moments. We train F such that the jth output predicts (-R,) from (X,, A:). When trained on all

---

Simulated
Voting
Scene 2.407K, (~1.6K,00.8K)
Motaaa (Terain; Nltest)
40K, (00K220K)
180K, (~44K,~12Kf 5.
[A,, Reger R feats used
4,4,5
6, 2, 294 (projected to 3) (0.7,0.3)
Train % per eg
(0.1,0.,,011,0.4))
Test % per cg
Various
(0.15, 0.85)
TT(a)
(,1, 2, 4,
(.56, .1, -1, 11. .111
(.17, 17,,
091,3:(.35, 5, 2, 14)
cgu= 0, .4)
Errai A4]
002,4:(.33, 2,, 22. 14)
cg, 36, .3, 1,
Table I: Environmen//xperimeut details. The first row lists the approximate number of points in randomize the exact splits actoss runs. 'eg' stands for coarse group as
the train and test splits described in the text. The last three rows list the percentages/rewarrd values per action in the tuple. shift between cities, additionally
Note for voting, consider using data from only some of the cities so not all data is used. We use random projection to project the feature space of Scene to avoid ill illccondt behavior.
do not have coarse groups as
the data, Flj] should model the jth moment a Let Dx represent the sequence of contexts the dataset. Then for every context X; E Dx and every a E A and any des we use our approximators F3 to estimate the desired value:
exp (-R) R ] ace
1+ +). (m)();a) for any E A, 0, > 0. (11)
È PRX
a
m!!
This approximation achieves better regularity we are longer fitting the dependence on de. Practically, we find order m = can often be quite accurate. Additionally, note that while the context is high dimenstional, the Taylor expansion is only for the scalar de.
Complete Algorithm: With our estimator Erax, (exp(- R/az)] we proceed with our method by
first calculating n x k values of xx for each context in the dataset and each action the action set. To do this, iterate through (X,, a) (Dxx.)) A. and solve the following conver problem in deg
Qx,a
min {a log ( oc>0
+ acde).
(12)
We then carry out the procedure detailed in Section 4.1.2 onwards with these Qx,a. Algorithm I in the Appendix provides our full algorithm for policy evaluation and optimization, that considers both the discrete binned case (Section 4.2) and the function approximation case just discussed.
Experiments
We test and analyze our algorithm empirically in three settings, including two derived from real data. For all experiments, we use the practical algorithm discussed Section 5, While our method works for any policy that can be optimized, we consider learning the parameters 0 of a stochastic softmax linear contextual bandit policy of the form:
exp(o(X,A)
No X, A) EAEA exp(o(X,a)"0)
(13)
This policy Ta differentiable so we optimize 9 using gradient descent. For the function approxima- tors F discussed in section 5 we use exponential-keree linear regression models.
We compare against three baselines:
(i) baseline-IS: The standard non-robust method for maximizing the reward calculated using impor- tance sampling policy evaluation on the training data and does not consider the shift,
(ii) baseline-POEM (Swaminathan and Joachims 2015a] POEM improves the baseline-IS method by adding variance regularization account for finite sample error, and
(iii) baseline-DRO Si al. 2020) as mentioned throughout the text, considers the shift over the
joint (context, reward) distribution as opposed to separating them.
7

---

6.1 Evaluation Domains
We first provide a brief overview of our evaluation settings and provide full descriptions in the appendix. In one setting, the voting dataset setting, we consider the case when data from one city is used to train a policy deployed in some of the other cities. In the two other settings, to construct example shifts we cluster the datapoints by one of the context covariates into what we denote as Coarse Groups (cg). We then consider settings where the training distribution may consist of a different composition of cgs than the deploymen//esttng distribution. For each environment we give details in Table such as the average reward on the training set of each (eg, action) pair.
Simulated Setting: Our simulated setting has cgs. To mimic the non-linear relationships that may occur when using real data, unknown to the designer, eg I and 3 (cgi.a) are identical, as are egs 2 and 4 (c92,1). Each context is composed of the eg and 4 other values sampled from uniform distributions. For each of the 4 actions and cg. each (eg, action) pair has a set of true reward parameters o². The linear combination of 6² and the contexts determine the Bernoulli parameter of the observed reward.
Scene Setting: We additionally test in a setting derived from the multiclass-spperiieedd learning Scene classification dataset from the LibSVM [Chang and Lin 2011 repository. We slightly modified version of the supervised to bandit conversion method from prior literature [Swaminathan and Joachims 2015a Agarwal al. 2014]. In this method we assume we do not observe the correct label directly. Instead each label is an action and selecting the correct action/label gives positive reward, while the wrong action/label gives negative reward. We use the true label to create egs and consider the case where we do not have access to the coarse group at test time so it cannot be used in learning the policy. This illustrates a more challenging and realistic case where there shift in the unobserved context features. To create a context distribution shift between train and test, we sampled different proportions of datapoints from each group to put in the train distribution.
The voting dataset by Gerber et al. [2008] contains data collected from a randomized controlled trial-style study testing various actions (1 control and treatments) to increase voter turnout. We consider a potential real shift in the dataset by using data from one city to train a policy deployed in some of the other cities. To illustrate the worst case, we chose the training city and the deployment cities such that there is a large context difference between the cities (details in appendix). We consider the recorded binary voting outcome our reward. Because the non-control actions require additional effort of printing and mailing a letter compared to the control (do nothing), we slightly lower the non-control action rewards by 0.09 simulate this effort cost.
Voting Setting:
6.2 Results
We use the training dataset optimize the policies and evaluate on the test dataset. For the voting dataset we use importance sampling to evaluate the policies. For Simulated and Scene, we have the true rewards for all action and use them for evaluation. All the robust algorithms have robustness parameters. FDRO has two, the reward distribution uncertainty set radius, de. the context distribution radius, 8z. We expect many of our settings predominantly have context shifts. We leverage this information to set our FDRO parameter for reward shift to d = 0.001. In Figure If and the appendix we give performance at different values of 5, and show performance is similar for a range of values. We show our main results in the top row of Figure | where we consider the effect of 8g. Baseline- DRO has single parameter for the KL-radius over the joint context-rewarc distribution ambiguity set, 8. Baseline-POEN also has a single parameter, the variance regularization strength, A. Faury et al. [2220] prove that POEM can be equivalently viewed from a DRO fornulation. So for comparison when reporting the results, we first translate À to the corresponding DRO-radius 5 nx². We demonstrate in all three settings, FDRO is able to outperform all the baselines.
In Figure Dh. we consider the case of testing an algorithm fit with fixed 8, in different populations. We plot the performance gain of each algorithm over baseline-IS as the test population is increasingly different. We made this environment especially challenging for FDRO by fixing 85 for FDRO while solving for the best for each different test population for baseline- DeRRinneeROOOo and POEM.. We see that as expected when the test context distribution is nearly identical to the training context distribution, the robust policy learned by FDRO does not perform as well (negative reward difference). However as the test distribution differs, we see FDRO starts performing much better than the non- robust policy. Also as predicted, in setting with binary rewards, the joint formulation of DaOO suffers from the same issues of degeneration in learning the optimal train-distribution policy as in
8

---

FDRO
baseline-DRR
baseline-POEW
baseline-IS
Middle
Simulation Bernoulli, 6, = 0.9
Scene
Voting
Cities
Test
Train
Test
Reward A from 15
0.10
0034
Rewards
Rewards
0.30
0.2
0.32
0.00
0.29
0.1
0.28
0.30
0.0
Coarse KL Test Shift
0.5
1.0
0.00
0.75
0.00
0/
0.75
1.50
0.00
0.12
0.00
0/0x
0.12
0.25
b
Simulation Gaussian Test
Reward Shift, Fixed Context
Sensitivity
Train
Test
Train
Test
Train
0.5
0.3
0.4
Rewards
Rewards
0.4
Rewards
0.2
0.3
0.3
0.00
0.75
0.00
0.75
1.50
013,
6 6x
0.0
0.1
0/ 0/
& 0.001
& 0.1
... 025
d
Figure 1: The dotted line 'Middle" serves as a constant horizontal reference across the two panels in plots (b-e). All plots are plotted with 95% confidence intervals shaded. Reported results and confidence intervals are averaged over 10 runs in all simulated domains, and 30 runs in Scene and Voting. Top Row: We plot our main results and demonstrate FDRO is able to learn more robust policies under context shift in all setting.
(a) We vary the shift in the test distribution and plot results as the performance gain over baseline-IS, (b,c) fix the train and test distributions and plot the performance at different 5/6, hyperparameters in Scene and Voting. Bottom Row: We present discussion results: (d) Results from a continuous-
domain: FDRO is able to outperform baselines (e) A domain where the test reward distribution shifts but context does not. (f) We show performance of FDRO at multiple values of & for the Scene dataset.
the supervised DRO literature (Hu al. using the best parameter per test population, Maseline-POEL. still does not perform as well.
2018 We additionally that even with the advantage of
In Figures Tb and c. We consider fixed training and test distributions and plot performance at different values of 6/65 for the voting and scene settings. We see that with increasing 6z, FDRO can learn robust policies that perform well on the test set. MasselineDRRO suffers from the same issue previously discussed. The performance of Mnseline-PEER decreases on both distributions. As the variance regularization weight increases, POEM is incentivized to Iearn low variance policies, such as choosing low variance but low reward actions, or reducing the variance from importance sampling by choosing policy close to the data-collection policy, which may be suboptimal. Figure Ic shows real-world shift between cities, we can see we would like to use data from one city to train a policy to deploy in other cities, it is important to consider distribution shift. Additionally for the case consider with binary rewards it may be necessary to use FDRO.
6.3 Discussion
Continuous Rewards and Reward Shift We focus on the common bandit setting of binary rewards in the main result; however, we also show results for continuous rewards setting in simulations environment with Craussannddistibuttinned rewards. Figure [ we see that baseline-DRe is able to learn good polices, however FDRO with extra structure information was able to learn better policy, with better train performance the same test performance. Additionally, we explore reward shifts. We create new simple environment (described in the appendix) where we can easily create test environment with shifted rewards. We fix o, and sweep &, for FDRO and we see Figure It. both FDRO and baseline-DRe DRRO are able to handle this this case well.

---

When to use FDRO vs. baseline-DRO (equivalence of solutions) One question is if the parameters can be set such that baseline-DRC DRO and FDRO choose the same solution, and if not when one is beneficial over the other. To examine this question we can look at the KI.-divergence chain rule decomposition:
Recall (Po X)) (p)))pp(())) RR x)) 6. (x<(po(X))l(()) = 8g. (B)))
DRa(PO ( () p
X)) Dia(po (x)(x(())ll(())))> +
dg. We can see, when 6. is the same for each X, we have 5 = 0g + 5c. When ó of baseline-DRO is set to o, + 6g baseline-DRO and FDRO consider distributions the same KL distance away, with FDRO placing additional constraints on the set of distributions searched. From the decomposition, we can see, with additional stipulations (details in appendix), we can set family of 55 and de values for FDRO to achieve the same solution of baseline-DRO for each 5 However, for given 6₂ and &e it is not possible to find a for baseline-DRO that achieves the same solution. Baseline-DRO has less constraints and can, for example, place the shift "budget" (82 + 6,) all in the rewards or all in the contexts if that the worst case. This may cause the degenerate performance in the binary rewards case for Daseline-DRO where reward shift dominates. FDRO shift is considered and ensures context shift is considered, allows us to overcome this. This example informs us that generally, if the algorithm designer would like to ensure certain amount of reward and context shift are considered, then it may be beneficial to use FDRO and invest the additional effort decompose 8 between ó₂ and &
set limits on how much reward
Setting the 6 parameters and potential negative societal impacts One limitation common to all DRO methods is that choosing the uncertainty set (6) may be difficult (Rahimian and Mehrotral 2019 Accounting for too large shift may result overly conservative policies. While DRO methods and FDRO are robust to shifts, if the shift is not as large predicted, the policy learned using FDRO may be overly conservative which can potentially cause negative impact in terms of lower than necessary performance. To mitigate this risk, 8 should be carefully set. Common approaches from prior work, which can apply to our method as well, is to use other similar datasets or sources to derive reasonable shifts. Additionally, empirically we see, our method often works for many values of 5. For example in Figure h. we show while we may incur a small penalty by setting 6g too large if the distribution does not shift, can learn policy that has much larger gains if the context distribution does shift. Similarly. in Figure [ we show robustness to 6z. Another approach could be to utilize human the loop approach by examining the worst case distribution. The worst case distribution can be easily calculated for KI. uncertainty sets and more details and demonstration are provided in the appendix.
Conclusion
In this work we consider the batch learning of contextual bandit policies when the deployment distribution may shift from that of data collection. We propose a distributionally robust optimization formulation that separates the reward and context shift. We demonstrated that our proposed estimators converge asymptotically and then developed a practical algorithm FDRO that is able to overcome some failure cases of prior methods and learn better performing robust policies.
Acknowledgements
This work was supported in part by Stanford
AI Hoffman Yee Grant.
References
A. Agarwal, D. Hsu, S. Kale, J. Langford, L. Li, and R. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1644 1646. PMLR, 2014.
D. Bertsimas and M. Sim. The price of robustness. Operations research, 52(1):35 2004.
S. Boyd, S. P. Boyd, and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
Y. Chandak, G. Theocharous, S. Shankar, M. White, S. Mahadevan, and P. Thomas. Optimizing for the future in non-stationary mdps. In International Conference on Machine Learning, pages 1414-1425. PMLR, 2020.
10

---

Y. Chandak, S. Niekum, B. da Silva, E. Learned-Miil E. Brunskill, and P. S. Thomas. Universal off pollcy evaluation. Advances in Neural Information Processing Systems, 34, 2021.
C.-C. Chang and C.-J. Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
W. Chu, L. Li, L.. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214, JMLR Workshop and Conference Proceedings, 2011.
J. Duchi and H. Namkoong. Learning models with uniform performance via distributionally robust optimization. arXiv preprint arXiv:1810.08750 2018.
J. Duchi, P. Glynn, and Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. arXiv preprint arXiv:1610.034255 2016.
J. C. Duchi, T. Hashimoto, and H. Namkoong. Distributionally robust losses against mixture covariate shifts. Under review, 2, 2019.
L. Faury, U. Tanielian, E. Dohmatob, E. Smirnova, and Vasile. Distributionally robust counterfactual risk minimization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 3850-3857, 2020.
S. G. Finlayson, A. Subbaswamy, K. Singh. J. Bowers, A. Kupke, J. Zittrain, I. S. Kohane, and S. Saria. The clinician and dataset shift in artificial intelligence. The New England journal of medicine, 385(3):283, 2021.
C. Gelada and M. G. Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3647-3655, 2019.
A. S. Gerber, D. P. Green, and C. W. Larimer. Social pressure and voter turnout: Evidence from large-scale field experiment. American political Science review, 102(1):33-48, 2008
Giguere, B. Metevier, Y. Brun, S. Thomas, S. Nickum, and B. da Silva. Fairness guarantees under demographic shift. In International Conference Learning Representations, 2021.
T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, pages 1929-1938. PMLR, 2018.
T. Hatt, D. Tschernutter, and S. Feuerriegel. Generalizing off off-policy learning under sample selection bias. arXiv preprint arXiv:2112.01385 2021.
W. Hu, G. Niu, I. Sato, and M. Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference on Machine Learning, pages 2029-2037. PMLR, 2018.
Z. Hu and L. J. Hong. Kullback-leibler divergence constrained distributionally robust optimization. Available Optimization Online, 2013.
E. Imani, E. Graves, and M. White. An off-policy policy gradient theorem using emphatic weightings. Advances in Neural Information Processing Systems, 31, 2018.
N. Jiang and J. Huang. Minimax confidence interval for off off-policy evaluation and policy optimization. arXiv preprint ar XxXV:2002.000811. 2020.
N. Jiang and L. Li. Doubly robust off-po value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652 661-661. PMLR, 2016.
N. Kallus and M. Uehara. Double reinforcement learning for efficient off policy evaluation in markov decision processes. Journal of Machine Learning Research, 21(167): 1- 2020a.
N. Kallus and M. Uehara. Statistically efficient off-policy policy gradients. In International Confer- ence on Machine Learning, pages 5089-5100. PMLR, 2020b.

---

N. Kallus, X. Mao, K. Wang, and Z. Zhou. Doubly robust distributionally robust off-policy evaluation and learning. arXiv preprint arXiv:2002.09667, 2022.
M. Kato, M. Uehara, and S. Yasui. Off-policy evaluation and learning for external validity under covariate shift. arXiv preprint arXivv20002. 2020.
E. S. Kim, R. S. Herbst, I. I. Wistuba, J. J. Lee, G. R. Blumenschein, A. Tsao, D. J. Stewart, M. E. Hicks, J. Erasmus, S. Gupta, et al. The battle trial: personalizing therapy for lung cancer. Cancer discovery, 1(1):44-53, 2011.
P. W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Yasunaga. R. L.. Phillips, I. Gao, al. Wilds: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021.
Q. Liu, L. Li, Z. Tang, and D. Zhou. Breaking the curse of horizon: Infinite-horizz off-policy estimation. arXiv preprint arXiv: 1210.1229, 2018.
Y. Liu, A. Swaminathan, A. Agarwal, and E. Brunskill. Off- policy gradient with stationary distribution correction. Uncertainty in Artificial Intelligence, pages 1180-1190. PMLR, 2020.
Michel, Hashimoto, and G. Neubig. Distributionally robust models with parametric likelihood ratios. arXiv preprint arXiv:2204.06340) 2022.
W. Mo, Z. Qi, and Y. Liu. Learning optimal distributionally robust individualized treatment rules. Journal of the American Statistical Association, 116(534):659 674, 2021.
H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. Advances in neural information processing systems, 29, 2016.
Y. Oren, S. Sagawa, T. B. Hashimoto, and P. Liang. Distributionally robust language modeling. arXiv preprint urXiv::909.000
2019.
D. Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
C. Qin and D. Russo. On adaptivity and confounding in contextual bandit experiments. In NeurlPS 202/ Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
H. Rahimian and S. Mehrotra. Distributionally robust optimization: A review. arXiv preprint
arXiv:1988.05659 2019.
S. Sagawa, P. W. Koh, T. B. Hashimoto, and Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint
1rX1v:1911.0873,, 2019.
O. Sakhi, Faury, and F. Vasile. Improving offline contextual bandits with distributional robustness. arXiv preprint arXiv:201 2020.
S. Shalev-Shwarte O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In COLT, volume 2, page 5, 2009.
A. Shapiro. Distributionally robust stochastic programming. SIAM Journal on Optimization, 27(4): 2258-2275, 2017.
N. Si, F. Zhang, 7. Zhou, and J. Blanchet. Distributional robust batch contextual bandits. arXiv preprint arXiv:2006.0550 05630,, 2020.
H. Singh, S. Joshi, F. Doshi Velez, and H. Lakkaraju. Learning under adversarial and interventional shifts. arXiv preprint arXiv:2103.1593: 2021.
A. Strehl, J. Langford, L. Li, and S. M. Kakade. Learning from logged implicit exploration data. Advances in neural information processing systems, 23, 2010.
A. Subbaswamy, P. Schulam, and S. Saria. Preventing failures due to dataset shift: Learning predictive models that transport. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3118-3127. PMLR, 2019.
12

---

A. Swaminathan and T. Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. The Journal of Machine Learning Research, 16(1):1731-1755, 2015a.
A. Swaminathan and Joachims. The self-normalized estimator for counterfactual learning. advances in neural information processing systems, 28, 2015b.
P. Thomas and E. Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pages 2139-2148, 201
S. Thomas and E. Brunskill. Magical policy search: Data efficient reinforcement learning with guarantees of global optimality. In European workshop on reinforcement learning, 2016b.
Thomas, G. Theocharous, M. Ghavamzadeh, I. Durugkar, and E. Brunskill. Predictive off aff-policy policy evaluation for nonstationary decision problems, with applications to digital marketing, In Twenty-Ninth IAAI Conference, 2017.
A. Xie, Harrison, and C. Finn. Deep reinforcement learning amidst lifelong non-stationarity. arXiv preprint arXiv:2006. 10701, 2020.
M. Yang. O. Nachum, B. Dai, L. Li, and D. Schuurmans. Off-policy evaluation via the regularized lagrangian. arXiv preprint XKi::2007.03458 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes) Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Section 6.3
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Appendix Section
3. If you experiments..
(a) Did you include the code. data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] https
//github. wtatthub.cooo/... Scom/Stafforss DaaaaafooodAHH//aatoreeeeeee
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Appendix Section A.2
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] 95% confidence intervals over multiple runs
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] Appendix Section A.2
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] Appendix Section
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "qcjuBHyOtyX", "reviewer": "Reviewer_WGag", "summary": "This work considers the contextual bandit problem with shifts on the distributions of both contexts and reward generators. An analysis on asymptotical optimality is provided. A practical algorithm as well as the empirical evaluations are presented. ", "questions": "Sometimes the distribution shift on the context does not matter under some weak assumptions, e.g., LinUCB works on linear contextual bandit with any context distribution. Therefore, a relevant question is when we should take context distribution shift into consideration?", "limitations": "no obvious limitation.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThis work is well-motivated. The problem of distribution shift is significant in practice.\nThe theoretical result is satisfying, even though it analyses the asymptotic behavior of the algorithm.\nThis work attempts to provide practical version of the algorithm.\n\nWeakness:\nThe proposed algorithm seems not very practical as it relies on Taylor expansion, especially when the underlying functions have many parameters.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eUnDPEPDJpq", "reviewer": "Reviewer_tRpt", "summary": "This paper proposes an algorithm to learn a contextual bandit policy in the batch setting when there is a distributional shift between training and deployment. The main motivation of the proposed approach is the benefit of constraining the factors of the distribution of the context and the reward. \n\nBased on the existing theoretical work on the minimax approach to DRO, the paper proposes a procedure for policy evaluation and improvement with convergence analysis. With other estimation details filled, FDRO is empirically evaluated against other baselines highlighting the strength of the proposed approach.", "questions": "- It seems that MGF approximation seems working well in practice. However, (considering a bit of theoretical flavor of this paper) in theory, MGF is not always guaranteed to exist. Then if the nominal (true) distribution has the MGF, could it be possible to say that a distribution of $\\epsilon$ KL-ball of the nominal distribution had MFG?\n- For continuous contexts, binning approach has been proposed. I was wondering if there is any other approach the author tried, for example, k-NN like smoothing, estimating reward distribution for a given context using (R,C,A) triplets from nearby contexts.\n- When there is a joint shift in the context and the reward, how can FDRO be compared with the joint constraining, e.g. baseline-DRO?\n- Does theorem 2 hold uniformly for $\\pi$? Since the uniform convergence is mentioned on line 208, it would be better to clarify this.\n- Factor constraining is basically considering KL-ball for each factor from some factorization of the original full distribution. In the full KL-ball of the same factorization, it is KL-distance on context distribution and expected KL-distance on context-action conditioned reward distribution. Then this can motivate a variation of FDRO, in which not setting the uniform (minimax) bound of KL-distance on context-action conditioned reward distribution, expected (Bayesian) bound of KL-distance on reward distribution. How would this be compared with the FDRO, any thought on this?\n- In contrast to context shift, reward shift $\\delta_c$ is fixed to $0.001$. How is the sensitivity to this hyperparameter?", "limitations": "The main motivation seems that the training tractability of factored constraining over joint constraining. However, the benefit of the current approach does not seem to be easily translated into continuous contexts making the estimation of reward distribution difficult. Still, the benefit of FDRO in discrete contexts is noticeable. Maybe its extension of the currently proposed binning approach for continuous contexts can be future work. In relation to this limitation, I am curious about the extent of the FDRO in discrete reward settings, for example, in the case where there are a larger number of discrete contexts and discrete actions, how FDRO would perform. Rather than asking to perform additional experiments for this, I would be happy if the authors can share their thought and previous analyses on this.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The proposed policy iteration is well-motivated by a previously established theoretical work.\n- Also, the convergence analysis of the proposed method is provided.\n- Empirically it is demonstrated that the factor constraining generally does not harm the policy iteration compared to the joint constraining except for a slim edge case (the same train/test).\n\nWeaknesses\n\n- Rather than calling them weakness, I put relevant questions in below box.\n- There are some typos\n  * in eq.(6) $\\frac{-R}{\\alpha_c}$ subscript $j$ of $R$ missing\n  * at line 290, $V^* = \\min_{\\pi} V(\\pi)$ which seems to have to be $\\max_{\\pi}$, \n  * in line 102 'We assume we the', \n  * in eq.(4), closing curly/square parenthesis are swapped, etc. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZzDEQ-KIaNH", "reviewer": "Reviewer_R2tu", "summary": "This paper proposes an improvement of distributionally robust offline learning for contextual Bandit problem. The authors formulates the robust learning problem by proposing a nested robustness criteria involving context drfit and drift in reward distribution. It builds upon the recent work but expands to the 'factored' form to make the robustness specification more fine-grained. ", "questions": "Can you concretely show how your algorithm can fix the issue highlighted in line159-161?", "limitations": "I think the authors have done a good job in listing the limitations and I have nothing further to add. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To me this is a good piece of work that builds upon the existing work and make it more fine-grained. The motivation of the problem has been clearly articulated and the mathematical super-structure has been nicely laid out thorugh both the main text and the appendix. This is not in my field of expertise, but I think the amount of novelty and the rigor is enough for an acceptance.\n\nAt some points it feels like a jump, especially from eq 2 to eq 4 and 5. It would be nice to provide more detailed steps. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UujdRhgOhyO", "reviewer": "Reviewer_kRMP", "summary": "The paper studies the problem of distributionally robust batch policy optimization in contextual bandits, where the distributional shift occurs over both the context and reward distribution. Under bounded error in KL-divergence, the authors show that the value of a policy can be optimized by considering the dual objective under both distribution shifts. The authors deviate from prior work by considering the two distribution shifts separately in a factored optimization objective.\n\nThe authors theoretically show that that the estimated value of a policy converges to the true one asymptotically, and empirically demonstrate its effective against existing baselines in several real-world domains; in doing so, the authors propose how their proposed objective can be estimated outside of tabular domains (i.e. when context is a continuous vector). ", "questions": "I was wondering if sample complexity bounds can be derived for Theorem 2 and 3 akin to Lemma 1? Specifically, is there something that prevents the authors from applying the same analysis techniques on the context distribution shift as they did on the reward distribution? ", "limitations": "The authors discuss limitations of their work in a separate Discussion section. An important one that the authors mention is how to choose the maximum divergence, which would affect how conservative the optimized policy will be. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper tackles an important problem of robust batch policy optimization. The authors provide a compelling motivation for their work via voting and healthcare applications. \n- The proposed algorithm is sound and provides substantive improvements over existing baselines, including one that considers joint distribution shift rather than the context and reward shifts separately. The authors also provide an interesting approach to extend their approach beyond tabular environments via estimating the moments of the distribution.\n- The empirical evaluation is comprehensive. The authors compare their proposed approach against strong, well-tuned baselines in multiple domains that rely on real-world classification and voting data. \n\nWeaknesses:\n- The exact algorithm somewhat lacks in novelty, as it is a hierarchical application of the dual objective trick used in prior works, notably Si et al. (2020). This also applies to the analysis, as Lemma 1 matches Theorem 1 of Si et al. (2020).  \n- To my knowledge, the theoretical guarantees (Theorem 2 and 3)  argue mostly about asymptotic convergence. The results would be stronger if there were sample complexity bounds and showed the dependence on the number of samples n. There also is a lack of guarantees on lower-bounds.\n- Though the experiments use real-world data, the actual distribution shifts are simulated. It would be interesting to use a real-world example of a distribution shift. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QQ2tH3Wa6Uo", "reviewer": "Reviewer_yHTP", "summary": "This paper provides a method (Factored-DRO) that learns a distributionally robust policy over separately handled shifts in context and reward distributions.", "questions": "- Why is it the baseline-DRO can be overly conservative compared to FDRO? Are there situations where FDRO can also be overly conservative (or overly optimistic)?\n\n- Is FDRO guaranteed to be always better than baseline-DRO in test, and why? If not, is there a situation where we can expect baseline-DRO to do better?\n\n- Is it possible to set $\\delta$ and $\\delta_x, \\delta_c$ such that baseline-DRO and FDRO will have equivalent performance?\n\n- As the authors mention, one limitation common to DRO methods is setting the $\\delta$ parameter. Since FDRO has two parameters to set, is it more sensitive to improperly set values? E.g. if $\\delta_x$ and $\\delta_c$ in FDRO are set too large, does the error compound, leading to worse performance, compared to baseline-DRO when $\\delta$ is similarly set too large?\n\n- In this light, does this imply that FDRO may be less advantageous to use for users who have less information about the distribution shifts in their application of interest? Should the user be more or less conservative in setting the parameter $\\delta$ in FDRO vs baseline-DRO?\n\n- Why are finite sample guarantees given for reward shift but asymptotic for context shift? Is it possible to obtain finite sample guarantees for policy evaluation and learning (Theorems 2 and 3) versus convergence of reward shift estimates, and if not, what is the barrier?", "limitations": "Aside from the points addressed in my comments above, the authors have adequately addressed the limitations and impacts of their work. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n\nOverall, I find the motivations to be convincing, the methodology to be reasonable, and the paper to be generally well-written. \n\n\n**Weaknesses** \n\nI would be interested in a more in-depth conceptual, theoretical, and practical comparison between FDRO and its closest point of comparison baseline-DRO (Si et al). For example, while FDRO has the advantage of being able to separate out shifts in context and reward distributions, by requiring more parameters to be set, is it more sensitive to improperly set parameters, i.e. does the error compound? Does this imply that FDRO may be less advantageous to use for users who have less information about the distribution shifts in their application of interest? \n\nPlease see my questions below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept