Contextual Linear Optimization with Bandit Feedback
Authors: Yichun Hu
Nathan Kallus
Xiaojie Mao
Yanchen Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: Contextual stochastic optimization
Personalized decision making
Prescriptive analytics
Primary area: optimization

Abstract: Contextual linear optimization (CLO) uses predictive contextual features to reduce uncertainty in random cost coefficients and thereby improve average-cost performance. An example is the stochastic shortest path problem with random edge costs (e.g., traffic) and contextual features (e.g., lagged traffic, weather). Existing work on CLO assumes the data has fully observed cost coefficient vectors, but in many applications, we can only see the realized cost of a historical decision, that is, just one projection of the random cost coefficient vector, to which we refer as bandit feedback. We study a class of offline learning algorithms for CLO with bandit feedback, which we term induced empirical risk minimization (IERM), where we fit a predictive model to directly optimize the downstream performance of the policy it induces. We show a fast-rate regret bound for IERM that allows for misspecified model classes and flexible choices of the optimization estimate, and we develop computationally tractable surrogate losses. A byproduct of our theory of independent interest is fast-rate regret bound for IERM with full feedback and misspecified policy class. We compare the performance of different modeling choices numerically using a stochastic shortest path example and provide practical insights from the empirical results.

Contextual Linear Optimization with Bandit Feedback
Yichun Hul
Nathan Kallus!*
Xiaojie M
Yanchen Wu?*
Cornell University 2 Tsinghua University Cyh767, kallus [allue/@cornell. eeternelleddu edu maoxj@sem tsinghua. edu. cn wu-yc23@mails. tsinghua. edu.
Abstract
Contextual linear optimization (CLO) predictive contextual features reduce uncertainty in random cost coefficients and thereby improve average-cost perfor- mance. An example the stochastic shortest path problem with random edge costs (c.g.. traffic) and contextual features (c.g., lagged traffic, weather). Existing work on CLO assumes the data has fully observed cost coefficient vectors, but many applications, we can only see the realized cost of a historical decision, that is, just one projection of the random cost coefficient vector, which we refer as bandit feedback. We study class of offline learning algorithms for CLO with bandit feedback, which we term induced empirical risk minimization (IERM), where we fit predictive model to directly optimize the downstream performance the policy induces. We show a fast-rate regret bound for IERM that allows for misspecified model classes and flexible choices of the optimization estimate, and we develop computationally tractable surrogate losses. byproduct of our theory of independent interest is fast-rate regret bound for IERM with full feedback and misspecified policy class. We compare the performance of different modeling choices numerically using stochastic shortest path example and provide practical insights from the empirical results.
1 Introduction
Contextual linear optimization (CLO) models the use of predictive features (context variables) to improve decision making in linear optimization with random coefficients. In CLO, we consider decision Z that incurs an uncertain cost Y determined by random cost vector Y Rd that is not observed at decision time. We do, however, observe predictive features X E R2 prior to decision, which help reduce uncertainty. CLO can be expressed either as a contextual stochastic optimization problem or a linear optimization problem where the cost vector is conditional expectation:
0" (x) = min.ez T X = x] mingez fo(x) 2, where fo(x) = LE|Y
X æ].
(I)
We assume throughout that a polytope (2 Conv( 22) for some vertex set
34 < oc with
supsez/ || S B) and is bounded (without loss of generality, Y y = {y lllll s 1)).
CLO has been the focus much recent work [e.g., driven operational decision making in many applications such network optimization, portfolio optimization, product recommendation, etc. The key question in these is how to use data to learn a good policy, π TR + 2, mapping feature observations to effective decisions. All of this literature studies an offline setting, where a batch of existing data (X,, Y,) for = 1,... n. is observed. These data are viewed as random draws from the joint distribution of (X, Y), and the goal to learn an effective decision policy from them. Crucially, this assumes that we fully observe the random cost
14 27 30), due to its relevance to data-
Authors are listed in alphahetical order. Correspondence to Xiaojie Mao: maoxj @ www.mnsiinuuuuu....m
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

vector Yi's, meaning that we fully know the corresponding costs Y, 2 for any potential decision 2. This may be unrealistic in many applications.
Consider for example the instantiation of Eq. ( as a stochastic shortest path problem of transporting one unit from start node to a desired end node, where Y contains the travel time on each of d edges, z the binary decision whether to traverse each edge, and Z constrains flow conservation. The data we would need in order apply existing approaches here would consist of simultaneous observations of the travel times on every single edge, encapsulated in the elements of Y,'s. However, such ideal observations may not be available. Indeed, modern travel time prediction models are often based on data from historical individual trips. For example, such is the case with Uber Movement data [26 [3], which is based on the total length of historical rides. Namely, instead of observing the entire Y,, we only observe the total travelling time C; Y, Z; for the path Z; in a historical trip i. We term this observation model bandit feedback as it corresponds to observing the cost only of a given decision and not the counterfactual cost of any alternative decision, as in bandit problems [25].
In this paper, we study the contextual linear optimization problem with bandit feedback and make several contributions. First, we adapt the end-to-end induced empirical risk minimization approach to the bandit feedback setting. This approach allows us optimize decision policies by directly targeting the decision objective. We provide three different methods to identify the expected cost of any given policy and show how to estimate the expected decision cost from feedbt-fedbbcck data. Second, we derive upper bounds on the regret (i.e., decision sub- sub-optimality) of the policy that minimizes the estimated objective. Our regret analysis accounts for the misspecification of the policy class and incorporates margin condition that potentially enables faster regret rate. This significantly extends existing theory for full-feedback CLOO, and as a byproduct, we provide a novel fast rate bound for full-feedback CLO with misspecification. Finally, we demonstrate that existing surrogate losses for full-feedback CLO (such as the our setting, enabling efficient policy optimization. We empirically test this in simulated shortest path problems and provide practical insights.
SPO+ loss in (II) can be adapted to
1.1 Background: The Full Feedback Setting
We first review two major approaches to the CLO problem with full feedback: estimate- then- optimize (ETO) approach and an end-to-end induced empirical risk minimization (IERM) approach. To this end, we need to define the generic plug-in in policy x for any given f R. - IR::
(x) E arg min:gz [x
Note that for any given covariate value x, this corresponds a linear programming problem with coefficients given by f(x). An optimal policy in Eq. (I) corresponds to fo Without loss of generaility, we restrict the value of (Ty to the set of vertices / of the polytope Z with ties broken according to some fixed rule (c.g., a total ordering over z such as lexicographic).
The ETO approach starts with estimating fo in Eq. T by any supervised learning method for predicting Y given X. This can, e.g., be implemented by minimizing prediction fitness criterion (e.g., sum of squared errors) over hypothesis class of functions F C [IR"" Rd (e.g., linear functions, decision trees, neural networks). After training an estimator ff of fo. the ETO approach then makes decisions according to the induced policy f. This approach is a straightforward two-step
approach, but it ignores the downstream optimization task in choosing f /E> F.
In contrast, some recent literature propose to integrate the estimation and the optimization, directly searching for a decision policy to minimize the decision cost. Following [4], we consider an IERM formulation that minimizes the sample average cost over the class of plug-in policies induced by F:
#F E arg min E Y,T (X.),, where ΙT = [
This approach is end-to-end in that it directly targets the decision- -aaiing objective. Recent literature demonstrates that end-to-ena approaches like IERM often outperform the ETO approach [1]] The benefits of end-to-end approaches are significant especially in the misspecified setting that is, when the function class F fails to contain the true expected cost function fo. and the policy class II does not include the globally optimal decision policy To [e.g.. 14 While Eq. (3) involves challenging bi-level optimization due to the definition of IT practical computational approximations have been proposed [6).

---

Nonetheless, the IERM formulation in Eq. ( requires observing the full feedback Yj's in the data. In this paper, we study how to extend this approach the setting with bandit feedback.
1.2 Our Problem: CLO with Bandit Feedback
We now formally define the data generating process in the bandit feedback setting. Assume we have an offline dataset consisting of n data points D {(X1, Z1, Ci)..... ........,,,... Zn, Cn)} that are independent draws from distribution P on (X, Z, C²) generated in the following way. We first draw (X, Z, Y) where the (X, Y) distribution as in the full feedback setting and is generated according to some historical decision policies for data collection. Then we set C Z y and omit the full Y. Below we impose some basic assumptions on the generating process of the historical
decision Z.
Assumption 1. The data generating process satisfies the following two properties:
1. (Ignorability) E|C 7, X] = 2 fo(X) (which could follow from 7 1 Y X).
2. (Coverage) inf inf zespan (2):1|/||=1 B[(2T> 2)² X] > O almost surely.
The ignorability condition is common assumption that plays a fundamental role in learning with partial feedback and causal inference (see the literature in Section 1.3). This condition requires that the assignments of the historical decisions Z do not depend on any unobserved factor potentially dependent on Y. The coverage condition requires that given the covariates X, historical decisions Z explore all directions of the linear span of the constraint set Z; otherwise it may be impossible to evaluate certain policies from the observed costs of historical decisions. This is an analogue of the overlap assumption in learning with partial feedback and causal inference [17].
The learning task is to use these data D to come up with a data-driven policy # (a:) that has low regret
Reg(T) (T Ex (X) #XX) min fo(X) 2] = V V( (TT,))
(4)
where V (TT) = Ex (x) T (x)].
1.3 Background: Off-Policy Evaluation and Optimization
1)} is the canonical basis and 2 is the simplex. This corresponds to choosing one of actions (or randomizing between them). The full-feedback problem in this case is sentiiensi classification [10]. In the bandit feedback case, with the restriction Z E z4, it is known as a logged or offline contextual bandit, and a long line of literature studies the problems of estimating and optimizing V VTT) I & 28-20 23 24 32 34 36 42]
An important special case is when g< ((1.,.....)............
[5]. is closely related to causal inference, viewing each component of Y as the potential outcome for the corresponding action (or treatment), where only see the realized outcome C' corresponding to the factual action with index 1 in Z E 2 and see nothing about counterfactual actions (Z). Two key differentiating characteristics of our problem with general polytope constraint Z are the opportunity to leverage the linear cost structure to extrapolate from the costs of historical decisions to costs of other decisions, and the presence of non-trivial constraints the output of decision policies.
Going beyond just finite discrete arms, 21 29 consider the logged contextual bandit with a continuum of arms, which is not generally representable in terms of the problem in Section [.2 These works make no restrictions on the relationship between the expected potential outcome and the corresponding action except generic smoothness, and leverage nonparametric approaches such as kernel weighting. Closest to our work is (6), which imposes a semiparametric assumption on this relationship. This includes our problem (Section 1.2) as a special case under the restriction that, conditional on X, expected outcomes are linear in actions (note that our E(C Z, is linear in Z the use
according to ignorability in Section 1.2). Relative this work, our unique contributions of induced policy classes to naturally deal with the constraints in Z, the adaptation of computational approximation such as SPO+, and obtaining the fast rates for the regret under misspecification.
2 Induced Empirical Risk Minimization with Bandit Feedback
Our IERM approach in the bandit setting follows the same idea of Eq. (3). directly minimizing an estimate of expected costs. However, since we not observe Y, our data, it is not as straightforward as sample average, Ei Y, T(X)/nn. Instead, we need alternative ways to identify ((T)..
3

---

Define [x = E[ZZT X] and recall fo(X) = B|y XX], which we will use to characterize the policy value (m)) We refer to these functions as nuisance functions following the existing literature on off-policy evaluation and learning contextual bandits or reinforcement learning [39], because they are not directly used for decision-making but serve merely as intermediaries for evaluating the policy value. Let (2,, 2, G f. 2) be a score function such that
Ep [0 Z, C: for Σo) [X)] = V(T), A fixed policy x, where Ep denotes taking expectation over P. Proposition ! summarizes a few possible choices. Proposition The following choices of ((x, 2, f. E) all satisfy Eq. (
(5)
1. (Direct Method) ODM(F, 2, c; J. .) [(x);
2. (Inverse Spectral Weighting) 01sw(1, 2, (. Et
3. (Doubly Robust) (2 2, f.E) f(x) (x))((c- =T
Here Σl denotes the Moore-Penrose pseudo-inverse of matrix Σ.
The doubly robust identification in Proposition D is generalization of the identification in [6] in that we allow for rank-deficient No by using a pseudo-inverse. Otherwise, our work significantly differs from [6] in terms of policy class specification, computation and theoretical analyses (see Section [.3). Note that identification in Proposition I Texploiss the linearity of the decision cost, which significantly improve upon algorithms that ignore the linear structure and naively extend existing offline bandit learning using discrete actions see Section 5 and Appendix C.2 for numerical evidence.
It remains to estimate Eq. (5) since we know neither P nor the nuisance functions fo, Eg. Following the approach of 1 45] for logged contextual bandits, we adapt the cross-fitting procedure advocated in [5]. For simplicity, we focus on the twofold version and assume is even. The extension to K- version is straightforward.
First, we split D into two equal-sized subsamples, D, and D2, each with n/2 data points. We can use Dj auxiliary sample to estimate the nuisance functions fo and Σo. denoting the estimates as fi and Σ.. We then use D:2 as main sample to obtain an estimate of V(T) using fi and Σ₁
2 EiED, 0(X,, Zr Cs Ê1) (Xx).
Of course, we can switch the roles of D2 and D2, i.e., Σg, then use D, to estimate V(x). Finally, given an induced policy class IIy, the IERM policy म minimizes the average of the above two V(T) estimates over Ily:
D2 get nuisance estimates fa and
# E arg min n. E) 8(X,, Zi C₁; fa-g, Ex-;) TX()).
(6)
Remark (Estimation of fo). The estimator f(x) can be obtained by minimizing the least square loss over some appropriate function class F.N:
f arg fin EiED(C, 2G, f(.)))
(7)
Note that two places in Eq. (6) require the specification of a function class for modeling fo: the F class used to induce the policy class HT, and the F class used to construct nuisance estimators to evaluate the expected cost of induced policies. In practice, we do not need to use the same class for F and FN. In fact, it might be desirable to use a more flexible function class FN to make sure it is well-specified for accurate policy evaluation, and a simpler class for F to make the policy optimization more tractable. We numerically test out different choices of F and J.N in Section 5
Remark (Estimation of Eg). There are multiple ways to estimate Eg. For example, (6) suggest estimating Eo by running a multi-task regression for all k) entries to the matrix over some appropriate hypothesis spaces Sik= Σ arg mins, E ES,........ Eagt.. Eiep 17 E(X,) 1 Proe To ensure a positive semi-definite estimator, we may posit each hypothesis Σ to be the outer product of some matrix-valued hypothesis of appropriate dimension. Alternatively, we may only need to consider finitely many feasible decisions
2 Zem such as the feasible paths for stochastic shortest path problems (see experiments Section 5) or more generally the vertices in Z-. Then we can first estimate the propensity scores eo(2 X) for 2 21,...,
. Zm using an suitable estimator ē(2 X)
and then estimate Eo(X) ΣØ= 2 eo (z) X)) by =(x)= Σm 232, é(z; X).

---

Theoretical Analysis
In this section, we provide theoretical regret analysis for the IERM approach with bandit feedback, allowing for model misspecification the induced policy class F That is, we allow the globally optimal policy f. to be not included in the class 1I We derive upper bound on the regret of the IERM approach, in terms of the complexity of the policy class 11,, its misspecification bias, and the estimation errors of nuisance functions.
Before stating the main theorem, we define few important notations. Let # be the best-in-class policy that minimizes expected regret over IIş:
n E arg min [[Jo(X)TT(X [x)]
We note that H can be different from the global optimal policy To if To & IIf, and Reg( characterizes the extent of misspecification in the induced policy class IIx. For j 1, 2, we define the function class
G3 9 -=((1.220) 0z0, 2, Sy E,) - (x)))e 1 T 11 [0.1]
-
(8)
2B0
For any function class G X' x x R. we define the local Rademacher complexity as (G, -E suupgee.llllly Sr Ei exg(X,, 2,
Z,, Cill]
where e, are i.i.d. Rademacher variables, and ||او| = v (X, [.
Throughout Section 3 we impose two assumptions. Assumption 2 concerns the algorithms we use to estimate the nuisance functions fo, Eo. requires that the nuisance estimates are close enough to their true values, and |10(z, 2, c; f. Σ) is bounded.
Assumption (Nuisance Estimation). The nuisance estimators f.E trained sample of size satisfy that [0x 2, Σ)1 < O for all x, 2, and any 5 E (0, 1) and at least 5,
Il,, with probability
Ep (0 2,1x, - 0(x,,,
(.3 (x)())))(xxx)))))))))))))))))( (x(x))+((x)))
s Rato 8).
In Section 3.1 we will relate Rate (n, 6) to the errors in estimating the individual nuisance functions fo and Eg for different choices of score function 0.
Assumption 3 which we term the margin condition, controls the density of the sub-optimality gap near zero in the CLO problem instance and allows to get faster regret rates. This type of condition was originally considered in the binary classification literature [2] [8]. is recently extended to contextual linear optimization by [14), which describe below.
Assumption 3 (Margin Condition). Let ('(x) = arg mig To and A(x) inf 2 2 (a) fo(x) z - -inf fo(x) T if Z (z) # Z and A(x) = otherwise. Assume for
some a, 7 2
(x < A < 8) S (18/B)a AO > 0.
Lemmas and 15) show that Assumption generally holds with a = for sufficiently well- for discrete X. Moreover, any CLO instance trivially satisfies a = O. Overall, a larger a means that the sub-optimality gap between the best and second-best decisions tends to be large in more contexts, so it is easier to distinguish the optimal decisions from others. We will show that a larger a parameter could lead to faster regret rates.
behaved fo and continuous X and with
3.1 Main Theorem
We now provide upper bound the regret of the IERM policy स in Eq. (6)
Theorem 1. Suppose Assumptions 2 and hold, and (X) defined in Assumption is singleton almost surely. Suppose there exists positive number (that depends on n) that upper bounds the critical radii of the function classes G G2 almost surely (i... 2n/2(0r,) 72 and (n,2(G2,7)
5

---

i2) and satisfies the inequalities 3nf /128 2 log (1gFF) and 2 rexp(-3ni2/11 - 8/4. Then,
there exists positive constant Č(a,7 7) such that with probability at least 8, we have
2a+2
Volan)
Reg(("))
(tg( <B 1 C(a,7))
+ +24BB
+ 8²
B
2
(n/2,0/4) (2
2Reg(#")
The upper bound in Theorem | involves several different types of error terms. The first type the critical radii F that characterize the complexity of the function classes G1. Gg. This is a common complexity measure for function classes in statistics and machine learning [4T. For example, as we will discuss below, the critical radii scale as Ö(yn/n) 91, G2 are VC subgraph classes of dimension 7. The second type is the term Rate [n/2, 6/4) resulted from the errors in estimating the nuisance functions fo, Eg. Similar nuisance estimation errors also appear in the previous literature offline S problems that involve nuisance functions [13. Below we will further discuss this term for different choices of score functions 0. The third type is the misspecification error term Reg(ā*). It is natural to expect a bigger decision regret when the misspecification error Reg(#*) is higher. In particular, when the policy class 1I is well-specified, i.e., fo E He we would have Reg(# (f") 0, and the regret upper bound would scale with the function
contextual bandit learning D 45 or more general learning
class complexity through a fast rate O 20.42 ). For VC subgraph classes with F = Ö 0(/n// n/n), the rate can range from nn/n) for a = to ((n/n)) for oc. However, if the policy class is
misspecified so that Reg (T) ) > then the dominating term related would be slow rate O
This reveals an interesting phase transition between the correctly specified and misspecified settings, which is not discovered in the previous theory that considers only seel-sppciiiiatiin [1.
Remark 3. The constant coefficients in the regret upper bound can be improved when 2(1 a)/a is an integer (which accommodates the case of a = justified in (15)):
Reg(ft) <B 120 7)
2
24(a 1 BO
(Clann)
Reg TT)
2[+0]
8 p2
a a+2
B
2a + Rate
+ +2
Reg("*).
Notably, the constant in front of the misspecification error Reg(ā*) becomes 1 instead of 2, which we believe is tight. This upper bound follows from nearly the same proof as Theorem [ except that it handles an inequality slightly differently. Specifically, the proof of Theorem / involves (org(t))((e))))
transcendental inequality of the form Reg(ft) & c, RRgg(f (t) |نो i + C2 for certain positive terms er, 02 This inequality difficult to solve exactly, so we can only get an upper bound on solution. It turns out that we can get better upper bound when 2(1 + ai/aa is an integer.
The nuisance estimation rate. DM, ISW and DR score functions. In pariticular, Rate (n., 5) is can be bounded by the estimation errors of the nuisance functions fo and Σg.
We now show that Rate 5) can be effectively controlled for the
Proposition 2. For any given 8 E (0, 1), let Xo.8 be a positive sequence converging to 0 as n oo, such that the mean square errors of the nuisance estimates satisfy the following with probability at least 1 8:
max Ex P| (2)(2))) (((0)))(()))))))1))))))) (IS" (X)
(X) S x2.61
where Projepan ()((())) - fo(X)) is the projection of f(x)= - fo(X) onto span(Z). Then,
1. we we take f = 6DM, we have Rate (n. 8) 0(xn,s);
2. If take 0 G1sw, we have Rate (n, 8) 0(xn8);
3. If we take 0 = 6DR, we have RateNa (n. 8) 0(x2,))
Compared to the DM and ISW scores, the impact of the estimation errors of the nuisances in the DR score is of only second order, i.e. O(x2,6) instead of (x..s). This echos the benefit of DR methods

---

in causal inference and offline contextual bandit learning [5 6]. Notably, here we only need to bound the projected error on the nuisance estimator f. which handles the setting when span 2) does not cover the whole Rd space, as is the case with the shortest path problem in Section 5
Computing the critical radius. The critical radius, characterizes the complexity of the function classes 91 and G2 defined in Eq. (8). The next proposition shows that F is of order Ó(1/ vz) if the function classes have finite Vu-subgraph dimensions. For simplicity, we focus on 91 only.
Proposition 3. Suppose 91 has VC-subgraph dimension 1i almost surely. Then for any 8 E (0, there exists universal positive constant Ö such that
CV Alogin+ (og((88))
12
satisfies the inequalities R., (9,, F2, 3nF /64 > log (1gF() and eexp(-3nr /64) s 6/4
3.2 Byproduct: Fast Rates in the Full Feedback Setting with Misspecification
Although main theorem is stated for the bandit feedback setting, our regret analysis techniques can be easily adapted to the full feedback setting. The following theorem states a similar regret upper bound. To our best knowledge, this is the first result for CLO that shows margin-dependent fast rate with potential policy misspecification in the full feedback setting.
Theorem 2. Suppose (X) defined in Assumption is a singleton almost surely. Define
gf = {x. x (x(())=="()))
2B
and of be any solution to the inequality R. (g, S 22 satisfying 3n((=)2 /64 (422 2 log (1/F()
and 2 2exp(-3n(F")) /644) S 6. If Assumpttin 3 farther holds, then, with probability least -8.
Reg(#") s B 12 C(a,))
+ 24B
Vola, v)
Rea( B
pP + (19)2) + 2Reg(
The regret bound is similar to that in Theorem T for the bandit setting, except that it does have 8/4). This is because, in the full feedback setting, we observe
the nuisance term 2Rate (n/2, (nate the entire vector, so we do not need to estimate any nuisance functions and can consider the nuisance estimation error term Rate (m/2, 8/4) as zero. When 1I is a well-specified VC-subgraph class with dimension we have Reg(#*) = 0, and FV = Ö(Vn/)), so the bound in Theorem reduces to ((nn/))aa+))///e
+ n/n). This bound interpolates between 1nn11/2 and O(n according the margin parameter a. recovering the fast rate in the full-feedback setting without misspecification as given in [14). In contrast, our bound in Theorem 2 adddiioonllyy quantifies the impact of policy misspecification, and its generalization Theorem further incorporates the impact of nuisance estimation errors in the bandit-feedback setting.
Computationally Tractable Surrogate Loss
The IERM objective is generally nonconvex in f E F, making it computationally intractable to optimize. In the full feedback setting, tractable surrogate losses have been proposed [T] 16. this section, we briefly explain the SPO+ loss in [1] and how it can be used in the bandit setting.
The full feedback IERM problem in Eq. can be viewed minimizing the following loss over F:
minser 1 En (IERM((((X)) YJ), where (ERM( (f()), y) = =y [000=yTTy(caa TT())) - y
This IERM loss equivalent the "smart predict-then-optimie (SPO) loss in Definition of M.. Letting x (yy E arg minlez y with the same tie-breaking rule as in πy. propose the SPO+ surrogate loss:
minjer 1 E (f(,), Yd), where /f = max,ez (y 2z())) (v 2f(x)) 2" 21)
The SPO+ loss has many desirable properties: given any fixed y, is an upper bound for the IERM loss, it is convex in fæ). and its subgradient at f (x)) has closed form 2(2" (v) z (2f(z) v)).
7

---

Training Data
Methods
400
1000
1600
ETO SPO+ DM SPO+ DR PI
3.34%
0.74%
0.35%
2.30%
0.36%
0.16%
2.47%
0.59%
0.32%
SPO+ DR Lambda
2.23%
0.40%
0.18%
SPO+ DR Clip
2.29%
0.44%
0.20%
Naive ETO
15.03%
12.12%
3.53%
Naive SPO+ DM
15.05%
12.85%
5.08%
Naive SPO+ DR
14.99%
13.00%
5.56%
Figure I: Stochastic Shortest path prob- lem on a 5 x grid with uncertain edge cost Y and decision 2j for 1,...,4..
Table 1: Average relative regret ratio of different meth- ods over 50 replications when both the policy-inducing model and the nuisance model are correctly specified. The logging policy is a random policy.
In the bandit setting, although Y; is not observed, the score (Xx, Zi, Ci f: Σ) plays the same role (see Eqs. 33 and (G). So it is natural to adapt the SPO+ loss to the bandit setting by replacing the unobserved cost vector Y; by the corresponding score 0(X,, Zz, C;f. E):
iSPO+ aiggenner +.2 E CiED, ISPO- (I(X)), 0(X; Zis CG f3- Ea-;))
Then we the plug-in policy क fwoo the decision policy. This is implemented in the experiments in Section 5] We can similarly adapt any surrogate loss for the full-feedback IERM problem to the bandit feedback setting, simply replacing the cost vector Y,'s ' by the corresponding scores.
Numerical Experiments
We now test the performance of our proposed methods in simulated stochastic shortest path problem
following II 14. Specifically, we aim to go from the start node s to the end node on a 5 x grid consisting of d 40 edges, where the costs of traveling on the edges are given by the random vector Y E. (see Fig.
We consider covariates E R and function fo()) E X x] whose components are cubic polynomials. The corresponding shortest path problem can be easily formulated into a CLO problem with the constraint set 2 given by standard flow preservation constraints. The resulting optimal solution z belongs to {0, 1 indicating whether passing each edge or not. We note that there are m = 70 feasible paths 21..... 2m E Z from the source node to the target node, and the feasible paths are lincarly dependent with rank of 18.
We consider bandit feedback setting, observing only the total traveling costs of the historical decisions Z generated by certain logging policy but not the edge-wise costs Y. We consider different types of logging policies that generate the decisions in the observed data. this section, we report results using random logging policy that picks path from all feasible ones at random regardless of the covariate value. Appendix C we further study the performance of two different covariate- dependent logging policies: one that picks paths according to the sign of the first covariate X1, and one that depends on the signs of both X, and X2. The empirical insights from the covariate -eeeddett logging policies are qualitatively the same as those for the random logging policy.
We numerically evaluate the performance of the ETO approach and the IERM approact For both approaches, we use the same class F to construct the decision policies. We consider three different classes for F: a correctly specified polynomial class, a misspecified class that omits two high-order terms (termed degree-2 misspecification). and misspecified class that omits four high-order terms (termed degree-4 misspecification). For the IERM approach, we consider DM and DR here but defer the results of ISW to Appendix C.2 Table 3 for its significantly worse performance. In both DM and DR, the nuisance fo is estimated by a bandit-feedback regression given in Eq. 77 with a ridge penalty, and we test out the three aforementioned function classes for the nuisance class J.N well. In DR, the nuisance (x)r is estimated by the propensity score approach described in Remark 2
The code scripts for all experiments can be found htttp:://githus http:hhwww.ccccceeaaaaaaaaallaaa

---

with the propensity scores estimated by either sample frequencies (for the random logging policy) or suitable decision tree models (for covariate-dependent logging policies). We further consider three variants when plugging Σ into the doubly robust score: pseudo-inverse (DR PT) as in the original 0DR definition; lambda regularization (DR Lambda), where we replace 2 with (2 + X/) for a positive constant A; and clipping (DR Clip), where eigenvalues Σ below certain threshold are clipped to the threshold before taking the pseudo-inverse. For all IERM variants, we optimize the SPO+ losses as discussed in Section 4 Further details on the experimentation setup and implementation summarized in Appendix C Finally, consider some naive extensions of the offline contextual bandit learning with finite discrete actions (Naive ETO and Naive SPO+), where we view the feasible paths separate discrete actions, without considering the linear structure of the decision-making problem. See Appendix A for details and Section 1.3 for background on offline bandits.
We test the performance of different methods on an independent testing sample of size 2000, and evaluate the ratio of their regrets relative to the expected cost of the global optimal policy म J.- T shows the average relative regret ratios of different methods across 50 replications of the experiment for a random logging policy. Due to space limitations, we include results for the training data size 400, 1000, 1600, and defer results for other sizes Appendix C.2 The relative regret of all methods properly decrease with the training data size n. In particular, the SPO+ approximation for the end-to-end IERM approach perform better than the ETO method. Among the SPO+ methods, the DM score achieves the best performance, while the DR score based pesudo-inverse performs the worst. Through close inspection, pseudo-inverse in the DR score causes a significant variance inflation. In fact, the ISW score also performs badly due to the high variance (see Appendix C.2) The Lambda regularization and Clip techniques can effectively reduce the variance and result in improved decision-making Moreover, the naive benchmarks that ignore the linear structure of the decision costs have much worse performance. This shows the importance of leveraging the linear problem structure.
found that the bias adjustment term that involves the
Training Data
Training Data n
Methods
400
1000
1600
400
1000
1600
F misspecified degree 2
F misspecified degree
ETO
11.04%
9.14%
8.34%
12.35%
11.42%
10.39%
F misspecified degree 2
IF misspecified degree 4
Well-specified Nuisance Model JON
SPO+ DM SPO+ DR PI
2.81%
0.80%
0.54%
4.06%
2.21%
2.06%
3.27%
1.36%
1.05%
4.83%
2.95%
2.71%
SPO+ DR Lambda SPO+ DR Clip
2.83%
0.97%
0.73%
4.33%
2.45%
2.25%
3.05%
1.09%
0.84%
4.59%
2.62%
2.38%
JFN misspecified degree 2
JEN misspecified degree
Well-specified
SPO+ DM SPO+ DR PI SPO+ DR Lambda
10.01%
8.37%
7.47%
12.51%
11.22%
9.68%
Policy-inducing Model F
9.11%
7.02%
6.44%
11.69%
10.19%
9.02%
9.05%
7.52%
6.68%
12.31%
10.38%
8.96%
SPO+ DR Clip
9.02%
7.28%
6.36%
11.87%
10.04%
8.70%
J,JN misspecified degree 2
F, FN
misspecified degree
SPO+ DM SPO+ DR PI SPO+ DR Lambda
9.90%
8.34%
7.41%
12.45%
11.16%
9.69%
Both F, FNN Misspecified
9.15%
7.23%
6.52%
11.92%
10.46%
9.42%
9.03%
7.46%
6.74%
12.01% %
10.72%
9.25%
SPO+ DR Clip
8.97%
7.22%
6.46%
11.75%
10.31%
8.95%
Table Mean relative regret ratio of different methods when the nuisance model J.N and the policy- inducing model F are misspecified to differrent degrees. The logging policy is a random policy.
In Table 2 we show the performance of different methods when either the pplicy-inducing model F or the nuisance model JrN or both are misspecified. We observe that when the policy-inducing model is misspecified, the end-to-end SPO+ methods perform much better than the ETO method, provided that the nuisance model for SPO+ correctly specified. This is consistent with the findings
in the previous full-feedback CLO literature [e.g.. I [4], showing the benefit of integrating

---

estimation and optimization for misspecified policy models. However, the advantage of the end- to-end approaches is weakened dramatically once the nuisance model is misspecified. In this case, the evaluation of decision policies is biased, so the end-to-end approaches also target a "wrong" objective that may not accurately capture the decision quality. Moreover, we observe that when the nuisance model is misspecified, the DR score can somewhat outperform the DM score, because it can debias the misspecified nuisance to some extent. These results demonstrate new challenges with the bandit-feedback CLO: the end-to-end approaches are sensitive to the misspecification of nuisance models, and the DM and DR scores face different bias-and-variance tradeoffs under nuisance model misspecification. Therefore, in practice may prefer more flexible models for accurate nuisance modeling, while using simpler policy-induse inducing models for tractable end-to-end optimization.
6 Conclusions
This paper studies the bandit- sendit-feedback setting for contextual linear optimization for the first time. We adapt the induced empirical risk minimization approach to this setting, provide novel theoretical analysis for the regret of the resulting policies, leverage surrogate losses for efficient optimization. and empirically demonstrate the performance of the proposed methods across different model specifications. Our paper has few limitations that we aim to address in the future. First, we primarily consider parametric induced policy classes, and it would be interesting to accommodate more general nonparametric classes. Second, we focus mainly on the SPO+ surrogate loss, and investigating other surrogate losses in the bandit feedback setting would also be of great interest.
Acknowledgments and Disclosure of Funding
Nathan Kallus acknowledges that this material is based upon work supported by the National Science Foundation under Grant No. 1846210. Xiaojie Mao is supported in part by National Natural Science Foundation of China (grant numbers 72322001, 72201 150, and 72293561) and National Key R&D Program of China (grant number 40222D0116700;
References
[1] Susan Athey and Stefan Wager. Policy learning with observational data. Econometrica, 89(1): 133-161, 2021.
[2] Jean-Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in elassifiers. The Annals of statistics, 35(2):608 1017660086366--- 2007.
[3] Stéphane Boucheron, Gábor Lugosi, Pascal Massart, et al. Concentration inequalities using the entropy method. The Annals of Probability, 31(3):1583-11) 1614, 2003.
[4] Olivier Bousquet. Concentration inequalities for sub-additive functions using the entropy method. In Stochastic inequalities and applications, pages 213-247. Springer, 2003.
[5] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. Double/debiased machine learning for treatment and structural parameters. The Econometrics Journal, 21 21 2018.
[6] Victor Chernozhukov, Mert Demirer, Greg Lewis, and Vasilis Syrgkanis. Semi-parametric efficient policy learning with continuous actions. Advances in Neural Information Processing Systems, 32, 2019.
[7] Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. arXiv preprint arXiv: / /03.4601, 2011.
[8] Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. 2014.
[9] Othman El Balghiti, Adam N Elmachtoub, Paul Grigas, and Ambuj Tewari. Generalization bounds in the predict-then-optimize framework. In NeurlPS, pages 1-421, 2019.
[10] Charles Elkan. The foundations of cost-sensitive learning. In International joint conference on artificial intelligence, volume 17, pages 978-978. Lawrence Erlbaum Associates Ltd, 2001.
10

---

[11] Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1)) 2022.
[12] Adam N Elmachtoub, Henry Lam, Haofeng Zhang, and Yunfan Zhao. Estimate-then-opimiie versus arXiv:2304.06883, 2023.
stochastic dominance perspective. arXiv preprint
[13] Dylan J Foster and Vasilis Syrgkanis. Orthogonal statistical learning. The Annals of Statistics, 5 11)):879-908, 2023.
[14] Yichun Hu, Nathan Kallus, and Xiaojie Mao. Fast rates for contextual linear optimization. Management Science, 68(6):4233-444) 4245, 2022.
[15] Yichun Hu, Nathan Kallus, and Masatoshi Uehara. Fast rates for the regret of offline reinforce- ment learning. Mathematics of Operations Rexearch, 2024.
[16] Michael Huang and Vishal Gupta. Learning best-in-class policies for the predict-then-optimize framework. arXiv preprint arXiv:2402.033: 03056,,,,.,,,.. 2024.
[17] Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge university press, 2015.
[18] Nathan Kallus, Recursive partitioning for personalization using observational data. In Proceed- ings of the 34th International Conference on Machine Learning- Craaning-VVluuee Volume 70, pages 1789-17966 JMLR. org, 2017.
[19] Nathan Kallus. Balanced policy evaluation and learning. In Advances in Neural Information Processing Systems, pages 8895-8906, 2018.
[20] Nathan Kallus. More efficient policy learning via optimal retargeting. Journal of the American Statistical Association, 116(534):64666555 658, 2021.
[21] Nathan Kallus and Masatoshi Uchara. Doubly robust off-policy value and gradient estimation for deterministic policies. Advances in Neural Information Processing Systems, 13:10420-10430, 2020.
[22] Nathan Kallus and Angela Zhou. Policy evaluation and optimization with continuous treatments. In International conference on artificial intelligence and statistics, pages 1243-1251. PMLR, 2018.
[23] Nathan Kallus, Xiaojie Mao, Kaiwen Wang, and Zhengyuan Zhou. Doubly robust distribu- tionally robust off-policy evaluation and learning. In International Conference Machine Learning, pages 10598-10632. PMLR, 2022.
[24] Toru Kitagawa and Aleksey Tetenov. Who should be treated? empirical welfare maximization methods for treatment choice. Econometrica, 86(2):591-616 2018.
[25] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
(26) Kelsey Maass, Arun V Sathanur, Arif Khan, and Robert Rallo. Street-level travel-time estimation via aggregated uber data. In 2020 Proceedings of the SIAM Workshop on Combinatorial Scientific Computing, pages 76-84. SIAM, 2020.
[27] Jayanta Mandi, James Kotary, Senne Berden, Maxime Mulamba, Victor Bucarey, Tias Guns, and Ferdinando Fioretto. Decision-focused learning: Foundations, state of the art, benchmark and future opportunities. arXiv preprint arXiv:2307.13.4 13565, 2023.
[28] David Pollard. Empirical processes: theory and applications. In NSF-CBMS regional conference series in probability and statistics, pages i-86. JSTOR, 1990.
[29] Noveen Sachdeva, Lequn Wang, Dawen Liang, Nathan Kallus, and Julian McAuley. Off-policy evaluation for large action spaces via policy convolution. In Proceedings of the ACM on Web Conference 2024, page 3576-3585, 2024.

---

[30] Utsav Sadana, Abhilash Chenreddy, Erick Delage, Alexandre Forel, Emma Frejinger, and Thibaut Vidal. A survey of contextual optimization methods for decision-makinn under uncer- tainty. European Journal of Operational Research, 2024.
[31] Bodhisattva Sen. A gentle introduction to empirical process theory and applications. Lecture Notes, Columbia University, 11:28-29 2018.
[32] Nian Si, Fan Zhang, Zhengyuan Zhou, and Jose Blanchet. Distributionally robust batch contextual bandits. Management Science, (9(10))5772-5799) 2023.
[33] Yeran Sun, Yinming Ren, and Xuan Sun. Uber movement data: A proxy for average one-way commuting times by car. ISPRS International Journal of Geo-Infornntion, 9(3):184, 2020.
[34] Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. The Journal of Machine Learning Research, 16(1): 1731-1755, 2015.
[35] Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference on Machine Learning, pages 814-823. PMLR, 2015.
[36] Adith Swaminathan and Thorsten Joachims. The self-normalized estimator for counterfactual learning. advances in neural information processing systems, 28, 2015.
[37] Michel Talagrand. New concentration inequalities in product spaces. Inventiones mathematicae, 126(3):505-566 1996.
[38] Alexander Tsybakov. Optimal aggregation of classifiers statistical learning. The Annals of Statistics, 32(1):335-166, 2004.
[39] Masatoshi Uchara, Chengchun Shi, and Nathan Kallus. A review of off-policy evaluation in reinforcement learning. arXiv preprint arXiv:2212.06355, 2022.
[40] Aad W Van Der Vaart and Jon A Wellner. Weak convergence and empirical processes. Springer, 1996.
[41] Martin J Wainwright. High-diimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[42] Baqun Zhang, Anastasios A Tsiatis, Marie Davidian, Min Zhang, and Eric Laber. Estimating optimal treatment regimes from a classification perspective. Stat, 1(1):103-114, 2012.
[43] Yingqi Zhao, Donglin Zeng, A John Rush, and Michael R Kosorok. Estimating individual- ized treatment rules using outcome weighted learning. Journal of the American Statistical Association, 1074499):106-11118 2012.
[44] Xin Zhou, Nicole Mayer-Hamblett, Umer Khan, and Michael R Kosorok. Residual weighted learning for estimating individualized treatment rules. Journal of the American Statistical Association, 112(517): 169-1887 2017.
[45] Zhengyuan Zhou, Susan Athey, and Stefan Wager. Offline multi-action policy learning: Gener- alization and optimization. Operations Research, 71(1):148-13) 2023.
12

---

A Naive Extensions of Offline Contextual Bandit Learning
In this section, we show some alternative approaches to solve the stochastic shortest path problem in Section[5] These approaches can be viewed as naive extensions of offline contextual bandit learning with discrete actions.
Specifically, consider the feasible paths 21...... Zm. for 70. We can view them as separate discrete actions, and a feasible decision policy π is mapping from the covariates X to one of the for the decisions. Consider simplex
m = 70 feasible paths. We now adopt one-hot-encoding zzimplx in R and zero-one vector E {0, 1 that takes the value 1 on one and only one of its coordinate. Each feasible decision in 21 ..... Zm corresponds one vector e.g., the decision 2j corresponds to the ă vector whose j-th entry is 1 and other entries are all 0.
Our decision-making problem restricted to the feasible decisions 21,-... Fi can be written follows:
min SE Zuigkk
E Z == =22 2j. x]
min 8 fo(x). 2E
1=1
where fu(z) = (B(C' Z 21, X E Z km, X= =))) For any given x, the result-
ing decision will be an one-hot vector that corresponds to optimal decision at x (which can be equivalently given by fo (1) for an plug-in policy in Eq. 2 at the true fo(x) = EE X = z)). In this formulation, we view the decisions 21,-... Zm separate discrete actions, and we do not necessarily take into account the linear structure of the decision cost.
We can easily adapt the bandit-feedback ETO to this new formulation. Specifically, we can first
construct an estimator f for the So function. For offinn bandit learning with discrte actions, this would usually be implemented by regressing the observed total cost C with respect to the covariates X, within each subsample for each of the feasible decisions respectively. Given the estimator f. we can then solve the optimization problem minge guimptes T fzr).. We finally inspect which coordinate of the resulting solution is equal to and choose as the decision.
To adapt the IERM approach, we similarly define the plug-in policy for any given hypothesis
f(x): R2 + Rm for the function fo (xx) (E[C)) Z 21, X xl...., E[C' | Z 2m, X =))T;
# *x((²) E arg min ee Zoinpees
[(
where ties are again broken by some fixed rules. Given function class F, we can then consider the induced policy class îl = ( f E F). For any policy E y. its output is an one-hot vector, whose entry with value corresponds to the chosen decision among 21, 2mm For any observed decision Z E { 2m J. we denote its one-hot transformation Z the zero-one vector whose value-one entry corresponds to the value of Z. For a given observed total cost C, we denote Č' as the vector all of whose entries are equal to C. In the lemma below, we show that the value of each policy т can be also identified by some score funtions.
Lemma 1. For any given policy ă that maps any covariate value to an m-dimensional one-hot vector, its policy value can be written as follows:
( L 0 2, C; eo) m(x)
E0)
where fo(x) (EE(C) Z 2= =1, X 2) a)..... ... B|C| 7 2m, X ===]] =²)T
Ea(x) (co(2) x,..., e.....,o(2E, x))) ca(2 x) PTZ 2Ú X = x),
and the score function ê can take three different forms:
1. (Direct Method) Öosr(,, 2, ( f(x);
2. (Inverse Propensity Weighting) 0/ 2, f. = マ(ं
3. (Doubly Robust) 0p (z, غ, f, f. f(x) -े f())).
In the three score functions above, all vector operations are entry-wise operations.
13

---

From Lemma 1 the new formulations above have very similar structure as our previous formulation in Section Propositiion [T] The major differences are that we restrict the discrete actions 21.... ................................ 2m redefine certain variables accordingly, and consider a simplex set as the constraint. We note that the identification in [ mimics the DM, IPW and DR identification offline contextual bandit learning [e.g.. [ 7 43]. Since the identification formulae are analogous to those in Section 2 we can easily apply the same policy learning methods in Section and the SPO+ relaxation Section
B Omitted Proofs
B.1 Supporting Lemmas
Lemma 2 (Talagrand's inequality, 33) Let -.,,,i,,....... be independent U-valued random variables. Let H. be countable family of measurable real-valued functions on U such that [| 20 S and (U;) E[h(U,,)] 0. for all h H. Define
Up = 2vE
sup ACH
Σ M(U)))
+ Σ
sup E (U;))
NEN
Then, for all t 2 O,
-12
IP bER
sup
h(U))
2 E
sup hEW
Σ h(U:))
-t)
S exp
2un, + 26v/3
Lemma 3. Fix functions f. E independent of {(X,, Zi, C:) such that 10 2, c; Σ)|l S for
all x, 2, c. Define the function class
g= (=((0.2.0)
6(x, c; (..00
(T(()) (x))pp
: pe 10.1]
2B0
Let i be any solution to the inequality (,, < x² satisfying 3nr log (0gg((1T)) Then we have
(E,
Er)gl |1g/12 7
(- ns²
P
sup gEg
2 67
< 2 exp
64
where
Eg(g) = Σ g(x,, C.).
Proof of Lemma must hold true:
When sup (En Er)gl/ (I19l1 +) > 67, one of the following two events
E, = {I(E, - -Ep)gl 2 67 for some g such that ||ا1|2 S f].
& = (En - -Ep)gl 2 61ايااا F for some E & such that || 2 f).
Define
Zr(r)= sup (,, Er)gl. /1G.11911.5 Sr
Note that lRgl|2 I r implies [[(g
² < r2, and we also have llg - -E(())l 2. By
Talagrand's inequality (Lemma over the function class {g - Ep(g) : g E 9).
nut2
(r) 2 E(2, S exp
(r) + 2r + 4t/3
We now bound the expectation (r)). Since is star-shaped by 41 Lemma 13.6),
R., (g,9G))/r is non-increasing. Thus, for any r 2 7,
2r R2 (G. 2rř,
E|Z, < 2R, (g. r) < 1
AA function class 9 is star- sha-ed if for any E & and p E |0, 1]. we have pg E G.
14

---

where the first inequality comes from symmetrization argument, the second inequality uses the fact that r + (G. r)/r non -oncinceaa,nn and the third inequality is by definition of
The Talagrand's then implies
nf²
P(Z,(r) 2 2r + t) - exp
(10)
16rā + 2r + 4t/3
We first bound P(E1). Taking r = and = 4 in Eq. (10) we get
24 P(E)) (2, 2 67 1 cxp
35
We now bound P(E2). Note that
P({2) s ((za(()))))) 61[g||2 for some y G, 119112 F).
Define
Gm = {g E 9 2m & ||l1|2 s i
Since |gll22 & 1, there exists M 5 log, (1/ such that
gn fg: 1اl12 2 F} C U 9
Therefore,
P( < Σ (1lgl) 2 6ااا||_5 for some g 9m).
We now bound each term in the summation above. If there exists Gm such that Zn (119112) 2 61gg then we have
Zn (2 2 (199l12))) 2 61|g|12 2 3 3-
Thus,
((Z9l()) 2 6||g||2 for some g E Gm) S P(Zn(2
23 2m
Now, taking r = 2 and = 22 in Eq. 10 we get
3nf
(2 2 3 2 S exp
eexp
32 1112
13 22-m +
Therefore, 61
3 n 2 log (1g))) then
3
P(E2) < M exp
32 カン²
S exp
64
Combining the bounds on (PEE) and ((22) leads to the final conclusion.
Lemma 4. Suppose Assumption holds and P((Z*(X) Č(a,7) 7) such that for any æ E π,
0. Then there exists constant
Reg(T)
T
P(x(X) # ( < ()),))
B
Proof of Lemma 4 This follows directly from 14 Lemma 1].
Lemma 5. Let 02, be positive constants. For any a > O, if a positive number x satisfies
x S 0x C2,
we have
2042 < (c1r)
a+2
+ 2c2
15

---

Proof of Lemma 5 First, note that
Ciaa 2(1 + a)
Oy y ciy a 02)
y/
The derivative is strictly increasing in and is eventually positive. Note the function (2/4/(2+2)) 22 takes a negative value at - 0. Then as y increases, the value of y 11-cg0/(2+2a) og first decreases and then increases. Therefore, y > satisfies the in- equality c212/12+2a), 02 0, then such also provides an upper bound on Hence it is sufficient to show that (c1r) 2a-2
+ 202 satisfies the inequality, or equivalently,
(cr) aाd t ((ar) 2012 + 20²
(11)
Suppose a2(2+ + 2a) is a rational number. In this case, we can write a/ (2 2a) mi /m2, where mi and my are positive integers such that m2 2 2m + Eq. (TT) is then equivalent to
1222
(crr)
C2
2 2 (cir)
+ 202
m2
(12)
Using the multinomial theorem, have
(ar))
me
((1r)= mp-mi + 2012
my
sa ma
02
m
m2!
m1 !m -
(cir) m1
mi mi
(i + M2 - i)!
(m1 i)li!
1=0
Since m2 2 2m1 + 1, we have for any i O,..., mi1.
m2!
12
+ m2 my [m 1)!
mm t)!!!
This can be proved by showing the ratio of LHS over RHS is larger than 1. Hence, Eq. true when az(2 2x) is rational number. Finally, note that
11 holds
22.12 as2 + c2 ci c(((rr)) 612
2a.12
(cIr)
+ 202
continuous in a. Since any real number a can be viewed as the limit of a sequence of rational numbers and Eq. (1)) holds for all rational numbers, it also holds true for all > 0.
Lemma 6. Let c1, T, 2 be positive constants, and let a be positive constant such that 2(1 + aa/a an integer. If a positive number x satisfies
x S C C + cig c2r² + 2 + + y:
have
2042 n+3
20+2 T o+2
2a +
2a +
2a + 2
S C1
+ +
Ciy +2
a a 62r +
+ 2 + y.
Proof of Lemma 0
Let 2(a +
1)/a a m, where is an integer by assumption. Using similar argu-
ments as in the proof of Lemma it sufficient to show that for w c
20+2
r
pa12
2n
2a-2
c1y Cyyaarr+ r a+2
2042 c2r + 20+2
and ch ciy 2( + c22 + y, have
a+2
a+2
-- C/ 2 0.
This is equivalent to showing
2042
2042
2x
+ 2
2a +
2x + 2
c a+2
+
CIy 22
C2r
+
z +
a+ 2
+
( 2
201
6
2
2042
8+2
2a 2
Ciy
26
2a + 2
(2)
2a 2
+ y
x(+0)
r eeg c2r + + y.
2
0 + 2
2
16

---

Since = 2m - 2), the above inequality is equivalent to
C1y +
c2r
2cpr
m
m C1y r
m
C2r
m
+
Using the multinomial theorem, it easy see that the expansion of LHS contains all terms on the RHS (plus additional positive terms). This finishes proving our conclusion.
B.2
Proof of Main Theorem
Proof of Theorem
To simplify notation, we define
Eng 0(X, Z, C; (4 - -+x)) +()))
2
0(x,, Z, C:; Ci 2 (f(X;) (Xi))
iED;
We can decompose the regret as
Reg(A) (t [Er(fo(X) -
_Ep, 2, So -x))) |
(((X))))+++]()))))))) +E| (F*(x) (F()) -x (X))
(0(X. 2, So Eo) 0(x, 2( (((x)=((x))
Ep
j=1
2
2 (Ep- E 10 3 -+(x))xxx) *x()]]
Σ
j=1
+ Reg(#i))
where the inequality follows from the definition of
By Assumption
2 with probability at least 1 - 55/2,
2
Σ Ep (8(X, Ex) - -(x,,, (+(X)
(x()) s Rate~ (1/2,
2
1=1
We now bound (Ep - Em,) 0(x, (x(X)) By Lemma 3 and the assump-
tion that 2 exx(p33r22) 1-:nn2/1000 112)) 8/4, we have that with probability least 1 8/4,
(En, Ep)gl
sup gEG;
67.
(13)
119112 +
Assuming Eq. (13 holds,
(Ep
5a #x)))
0(X, ((x, 22) -x(())))
<12Be
F F 82
2B0
To (X))
0(X, Z, f2, (TT, -x) -xx))
<12Be
7
8 72
2B0
2B0
(14)
17

---

For any x E II
0(X, L, 2, (T) (x(X) - 5 (X))
2BQ
0 Z. ( - 25. (X))
E
[(x(X) # xx
2B
(X)) # tT (X))
Reg(at)
140
<c(a,,)
where the last inequality follows from Lemma Applying the inequality above for both ī and To and plug the bounds into Eq. (14), we get
(Ep - -E,,) ((x,)) 2, E2) ((((() *xx)]
(V(ann) Reg((t)
Regg(T))
I14+a
<12BO
++ v ((a,7)
F
72
B
B
We can similarly bound (Ep - Enz (, (t) - #" (X))
Combining all pieces together, get that with probability least -.
Reg(f) (
<12
VV(ann)
Reg(#)
++ ++V0(a,))
Reg(
F R2
B
B
B
Rate (n/2,8/4)
Reg(#*)
B
B
Solving the above inequality with respect to Reg(#t) / B using Lemma 5
we have
20+2
Reg(#) <B 120 120/C(a,))
+
24BO
(Voaan)
Reg(#*)
2040)
f ++
B
+ 2Rate (n/2,6/4) (
B.3 Prools of Propositions
Proof of Proposition For direct method, the conclusion is obvious.
For ISW, we have for any E,
E (((=(())2C) T(X)]
- [(X)]
Let M(x) be matrix whose columns include all basis vectors of the span of Z. Then π +XX) Range [M (z)). According to the coverage assumption, the column space of Co(x) is identical to the column space of (zx. By the property of pseudo-inverse, the column space of (T E1 is orthogonal to the column space of M. Therefore, (7 Σ (X))
for any π E Z.
For doubly robust score, have that for any function f, E,
E ( ((x()) To
-X(x(X)T (X-
Taking either f fo Σ En gives 0.
18

---

Proof of Proposition 2
Because (2)) x" E span(2), for the DM score we have
(X, Eo) ADM (x,, (T(x)- - # *(x)))
Ep
T (x(x)- # -xx))))(x))
<Bp Proispan(2) (X, En) 8DM (x,
1/2
22B bx(x
0(n,s)
For the ISW score, we have
Ep (Issw(X,
Orsw (xs0 2, (x(x)=#(xi))
1/2 =((o))
$2B - (x)))) Prol
For the doubly robust score, we can easily get
T -10 ( (x
Ep
(
(x(X) *x))) (1- (X)) (f() [6(x))]
=Ep
=Ep
(x(X) ='(x)) _
- -xtxx-++(1)) (o()) - -
-Ep
(x(X) #*(x)) T (X)- - -x0()) Ex(x) Projssaa(z) -
Ex [xI]((*(X)) (x(x)) }
1/2
Ex Propois 2) (f(x) - -6(x)))111 1/2
Here the second equation holds because π (α) #* (a) belongs to the linear span of Z, but Et Eo) is orthogonal to the linear span of 2, as already argued in the proof of Proposition
The third equation holds because the column space of Ex(X) is identical to span(2 ()) according to the coverage assumption.
Proof of Proposition
Define
1
(1) exp(
5
Note that whenever EE (BW/)/) for some random variable W, we have by Markov's inequality that
P(W S 5exp(_t2/ww
W /.
P([ l)dt S 5w.
(15)
Throughout the proof, we condition on the event that 91 has VC-subgraph dimension 7). We finish the proof in three steps.
Step I: Critical radius for empirical Rademacher complexity. Rademacher complexity
Define the localized empirical
Rr r) E,
sup g
egg Xi, Zi, Ci)
where 61,..., are i.i.d. Rademacher random variables, and ||وا|, VV O Zi, C.)/n. Let fx be the smallest positive solution to R, (91,)) S /32. what follows, we show that there exists universal constant C' such that
nlog(n + 1)
IP
Pr < Ōv
1.
(16)
19

---

For any E G1. define set
G ((((X, 21, .(),...,(((,.. 7m Cn)) 9 E 11lll, s)..
Let (t, G) be the t-packing number of G and (t,, G) be the 1-covering number. Note that |gll I vur for all G. By [28] Theorem 3.5].
Σ eg((,, Zi, C.) 11
IE, V
J
sup
gEGt.Ilall..S St
where
J= 1mm
/m
Vlog D11 G)dl.
So by Eq. (15)
5 R1 S -J.
Consider the function class
g = (g: E I2,loll,, rr). Note that fir is the envelope of 9j on (X1, Z1, Ci)..... (Xns Zno Cn). Applying 40 Theorem 2.6.7] gives
D(virt, G) N(Vnrr//2,C
4n
S Ö(n + 1)(16))
for a universal constant Č Thus.
f V log D( G)dt
J =9/Vr
f + (17 (1g + r log n + 1oog 2n log tdt
<o/nr
// V2log C' 15 15 3log tdt v log(n + 1)nr,
59
where 1o V2log( C' +11+--1 3log tdt < co. We then obtain that for a (different) universal constant Ć
n plog(n + 1)
(9, =
32
Therefore, for any samples (X,, Z,, C.) 1= any An CVnlog(n 1)/n is valid solution to (9,, < 2 /32, which implies Eq. 16
Step II: Critical radius for Rademacher complexity. the inequality (,,,,) r) & r2/32. We now bound r.
Let r be the smallest positive solution to
For any > 0, define the random variable
n Σ ag((,, Z,, 27.
(t, E,
sup 1e9..llll.s
so that (,, [W (r)] by construction. Define the events
(t) = Wwi(t) Rn, t) =
112
||aa| |1
sup gEō.
|| + (r
20

---

Following the proof of [14 Lemma EC.12),
S S 3r.
P(2Ea(t)) n4).
Lemma EC.10] implies that
P(E)) S 2e (im(1))²
for some universal constant é > 0. Moreover, for any Ç 2 1, we have R,, (91,5r7)) 2 Rm((1))
(r7)² /32.. By 3 Theorem 16],
P(E)((r))) & 2e 2e-2eeen (2m(r))²
for some universal constant 02 0. Combining all pieces we have
5 Pm 3r 2 (Gr
(17)
By step in the proof, PP S Co / log(n + 1)/n) = for some constant Co- Let Ō > 5C. be constant such that 2- (()) < 1/6. rf > Cl + 1)/n, by Eq. we have Coynloognn 1)/n) 0, which leads contradiction. Thus,
+ H C + 1)/n.
Finally, any r 2 ČV 1 log(n + 1)/n solves the inequality R. r) S
Step III: Checking other conditions. The other two inequalities, 3nr² /64 2 log log2(1/7) and 2 exp (3nn² /64) < 5/2, are easily satisfied as long as we take C' big enough.
B.4 Proof for Full Feedback Setting
Proof of Theorem
To simplify notation, we write
E, Y (# (x*(X) #" (X))
(x,))) **(x)))
1=1
We can decompose the regret as
Reg (t)) = =Ep [Y EOYT(APO (+*(X) (x)())]
=Ep ( -x (x)) + B (#* 5o (X))
<EEp - E,,) -xx) + Reg(#*),
-
where the inequality follows from the definition of SF.
We now bound (Ep E.) (YT #* (X))] Following similar proof as in the proof of Lemma 3 we have that with probability at least 8,
(LEm
Ep)g
sup gEg
111l|2 + FF S 67
(18)
Assuming Eq. 18 holds,
Er
Em
(* (X) - #x)))
YT - (X))
<12B
*F + (7532
2B
<12B
YT (T(##(( - Tf 5. (X))
FF +
YT (X) - *x))))
#F + (FF)2)
2B
2B
21

---

For any x E II
(x(X) - (X))
Y (T(() - - Txo( 2
(x)(X)= & #x((x))
2B
2B
SP(T(X) + Tx(())
Reg(1))
1iu
<c(a,7)
where the last inequality follows from Lemma
Thus,
(LEp - En) -
<12B
(Cla.n)
Regg(*))
FP
Volan n)
Reg(#")
FP +
+(P)2)
B
B
Combining all pieces together, we get that with probability at least 1-8.
Reg(#*) (T
<12
Vola.n)
Reg(a")
7 + Vo(a,))
Reg(TT)
20+0)
p + (rT)2
B
B
B
Reg(#*))
B
Solving the above inequality with respect to Reg(af) using Lemma 5 have
20+2
Reg(##) B 12 Ö(a 7)T+)
at2
+ 24B
(V(a,1)
Reg( (7")
20
FF # =7F}2) + 2Reg(#*))
C Additional Experimental Details
In Section we provide experimental results for different methods under various model specifications and different logging policies. In this section, we further explain the details of experiment setup, implementation, and provide additional experimental results. All experiments in the paper are implemented on cloud computing platform with 128 CPUs of model Intel(R) Xeon(R) Platinum 8369B CPU @ 2.70GHz, 250GB RAM and 500GB storage. The experiment for each specification of F and FEN and each logging policy takes around days of running time based on parallel computing on 100 CPUs.
C.1 Experimental Setup and Implementation Details
Data generating process. We first generate i.i.d draws of the covariates X= (X1, X2, T E R3 from independent standard normal distribution. Then we simulate the full feedback Y according to the equation Y = fo(X) + where fo(X) 3 + WiX, + W + Wg + W X, X2Xx for coefficient vectors WT...., W E Rd and a random noise draw their entries
W X2Xx++ W X + W
drawn from the Unif[-0.5. 0.5, 0.5]. To fix the coefficient vectors W ..... W7. independently the from the Unif(0, distribution once, and then use the resulting fixed coefficient vectors throughout the experiment. We sample observed decisions Z from the set of all feasible path decisions {=1,-..,, Zm) } for m 70, according to different logging policies that will be described shortly. Then the total cost C Y T recorded in the observed data.
We consider three different logging policies. One is random logging policy that uniformly samples each decision from the feasible decisions, regardless of the covariate value. The other two are ewariate--depedeen logging policies. For these two policies, we first remove 20 feasible decisions that correspond to the optimal decisions for some covariate observations the testing data, and then randomly sample the observed decisions from the rest of 50 feasible decisions according to different rules. This means that many promising decisions are not explored by the logging policies at all. We hope to use these logging policies demonstrate the value of leveraging the linear structure of the
22

---

decision- decision-making problem, since exploiting the linear structure allows to extrapolate the feedback from the logged decisions decisions never explored by the policies. Specifically, we further divide the remaining 50 feasible decisions into two even groups. Then the two different logging policies sample decisions from the two groups according to different rules depending on the covariate value.
One covariate-dependent logging policy samples the decisions according to the sign of the first covariate X1. When X1 > 0, the logging policy chooses the first group with probability 2/3 and the second group with probability 1/3. When X1 S 0, the logging policy chooses the first group with probability 1/3 and the second group with probability 2/3. Once deciding the group, the policy then uniformly samples one decision from the chosen group. For concreteness, we will refer to this policy the Xi-poiccy.
The other covariate -dependet policy samples the decisions according to the signs of both X1 and X2. When X1 > 0 and X₂ > 0, the logging policy chooses the two groups with probabilities 2/3 and 1/3 respectively. When X1 > 0 and X₂ I O, the logging policy chooses the two groups with probabilities 1/3 and 2/3 respectively. When X1 S 0 and X2 > O, the policy chooses the two groups with probabilities 3/4 and 1/4 respectively. When X1 S 0 and X2 < O, the policy chooses the two groups with probabilities 1/4 and 3/4 respectively. Once deciding the group, the policy again uniformly samples one decision from the chosen group. We will refer to this policy as the Xi X1X2-policy,
Specification of the policy-inducing model and nuisance model. For the policy-inducing model and nuisance model, we consider three different classes. One is the correctly specified class ((31, F3, F3) H Wo w1 + W222 + W323 + W4 + W53223 + W6x123 + W731 Wo...., W7 E RJ. The second model class { I3, F3) + Wo + WII1 + W222 + W343 - W4 + Wgagg3 : Wo...., W3 E R} omits two interaction terms and is thus misspeci- fied (which we refer to as degree-2 misspecification) The third model class {(I1, T3, 43) + Wo + W121 + W222 + W343 W1, W2, W3 E R} omits all four interaction terms (which we refer to as degree- 4 misspecification).
Nuisance estimation for the SPO+ methods. The SPO+ methods involve two different nuisances. One is the function fz(z)= = E| X z). We estimate this by the least squares regression in Eq. (7). with the FNN class being one of the three classes described above (i.e., correct specification, degree-2 misspecification, degree-4 misspecificationn. We incorporate an additional ridge penalty with a coefficient 1. We estimate the the nuisance En(r) using the propensity score approach described in Remark 2 so we need to estimate the propensity scores P Z = 2j X x) for j = 1,.... m. For the random logging policy, we simply estimate IPZZ 2j X x)) for any by the empirical frequency of the decision 2j in the observed data. For the X, -pllicy and X, X.-polic, we estimate the propensity scores by classification decision trees of depth 3 trained to classify each instance to one of the observed classes among 21, Zm- These nuisances are all estimated using the two-fold cross-fitting described in Section 1.2
Since the Mg matrix is rank-deficient, we cannot directly invert it. Besides taking the pseudo-inverse, we also implement the Lambda regularization and clipping techniques described in Section 5 For Lambda regularization, we set the regularization parameter > to 1. For the clipping technique, we consider the ligendeccopositteee inverse of the transformed matrix. These two lead to the SPO+ DR Lambda and SPO+ DR Clip methods in Section 5 and this section.
of Eg, set all eigenvalues below 1 to 1, and then take a pseudo-
Naive Benchmarks. We also implemented the benchmarks in Appendix A For ETO, SPO+ DM, and SPO+ DR, we estimate fo(a)) by regressing C' with respect to X using data for each observed decision respectively. The regression function class uses similar correctly specified class, degree-2 misspecified class, degree-4 misspecified class mentioned above, with only slight difference in the dimension since the output of fo is m-dimensional while the output of fo is d-dimensional. For SPO+ DR and SPO+ IPW, we need to estimate the propensity scores. These are again estimated by either sample frequency or decision trees. Note that some feasible decisions are never observed in the training data. For these decisions, the corresponding component of so is heuristically imputed by a pooled regression of C against X using all observed data. For SPO+ IPW and SPO+ DR, although the propensity scores for the unseen decisions are zero, they do not impact the policy evaluation since they only need the propensity score for decisions observed in the data.
23

---

SPO+ Tuning and Optimization. We need to solve the SPO+ optimization problem in Section for the DM and DR scores. Following [T], we incorporate an additional ridge penalty on the coefficients of the hypotheses. We select the penalty coefficient from grid of O, 0.001, 0.011 and 10 points distributed uniformly on the logarithmic scale over 0.1 to 100. This done by minimizing the out-of-sample error an independent validation dataset with size equal to the corresponding training data. The penalty coefficient finally set as the half of the value chosen by this validation procedure.
To optimize the SPO+ loss, | recommend applying standard convex optimization solvers to dual reformulation, or by running stochastic subgradient descents. We tried both approaches and found that the stochastic subgradient descent method with the default hyperparameters in [[]] [4] (number iterations, step size, batch size) runs much faster, while performing similarly to the dual reformulation method.
C.2 Additional Experimental Results
In this section, provide some additional experimental results. Specifically, Tables and are extensions of Tables and the random logging policy. In particular, Table B results ISW and IPW methods. They generally worse than other alternative methods. Table additionally show results for the naive benchmarks under model misspecificatiio, and further confirm their worse performance. Tables55jo 8 results for two covariate-dependent logging policies, the X1 -policy and X1 Xp-oocy respectively. The performance of different methods tend to remain similar or slightly degrade under these more complicated logging policies. However, the comparisons of different methods remain qualitatively the same.
shows additional
Training Data n
Methods
400
600
800
1000
1200
1400
1600
ETO
3.34%
1.86%
1.04%
0.74%
0.50%
0.41%
0.35%
SPO+ DM
2.30%
1.14%
0.64%
0.36%
0.25%
0.20%
0.16%
SPO+ DR PI
2.47%
1.44%
0.86%
0.59%
0.45%
0.39%
0.32%
SPO+ DR Lambda
2.23%
1.15%
0.64%
0.40%
0.27%
0.23%
0.18%
SPO+ DR Clip
2.29%
1.22%
0.69%
0.44%
0.31%
0.25%
0.20%
SPO+ ISW
15.00%
15.52%
15.11%
15.02%
14.98%
15.03%
15.11%
Naive ETO
15.03%
15.26%
14.74%
12.12%
8.45%
5.17%
3.53%
Naive SPO+ DM
15.05%
15.46%
14.92%
12.85%
9.81%
6.63%
5.08%
Naive SPO+ DR
14.99%
15,42%
14.97%
13.00%
10.10%
6.98%
5.56%
Naive SPO+ IPW
15.56%
15.77%
16.06%
16.06%
16.06%
15.96%
15.96%
Table Mean relative regret ratio of different methods when the nuisance model JFN and the policy- inducing model F are correctly specified. The logging policy is a random policy.
24

---

Training Data n
Training Data
Methods
400
1000
1600
400
1000
1600
FF misspecified degree
JF misspecified degree 4
ETO
11.04%
9.14%
8.34%
12.35%
11.42%
10.39%
F misspecified degree
F misspecified degree 4
SPO+ DM SPO+ DR PI
2.81%
0.80%
0.54%
4.06%
2.21%
2.06%
Well-specified Nuisance Model
3.27%
1.36%
1.05%
4.83%
2.95%
2.71%
SPO+ DR Lambda
2.83%
0.97%
0.73%
4.33%
2.45%
2.25%
J=N
SPO+ DR Clip
3.05%
1.09%
0.84%
4.59%
2.62%
2.38%
Naive SPO+ DM
14.97%
12.78%
5.68%
15.27%
13.20%
6.42%
Naive SPO+ DR
15.00%
13.03%
6.31%
15.27%
13.48%
7.26%
J=N misspecified degree
JN misspecified degree
SPO+ DM SPO+ DR PI
10.01%
8.37%
7.47%
12.51%
11.22%
9.68%
Well-specified
9.11%
7.02%
6.44%
11.69%
10.19%
9.02%
Policy-inducing Model JF
SPO+ DR Lambda
9.05%
7.52%
6.68%
12.31%
10.38%
8.96%
SPO+ DR Clip
9.02%
7.28%
6.36%
11.87%
10.04%
8.70%
Naive SPO+ DM
15.56%
14.23%
12.96%
15.22%
14.51%
13.85%
Naive SPO+ DR
15.64%
14.36%
13.31%
15.17%
14.67%
14.12%
F,JN misspecified degree
F,JN misspecified degree 4
SPO+ DM SPO+ DR SPO+ DR Lambda
9.90%
8.34%
7.41%
12.45%
11.16%
9.69%
9.15%
7.23%
6.52%
11.92%
10.46%
9.42%
Both FN Misspecified
9.03%
7.46%
6.74%
12.01%
10.72%
9.25%
SPO+ DR Clip
8.97%
7.22%
6.46%
11.75%
10.31%
8.95%
Naive SPO+ DM
15.65%
14.23%
13.02%
15.16%
14.53%
13.84%
Naive SPO+ DR
15.63%
14.42%
13.33%
15.26%
14.74%
13.95%
Table 4: Mean relative regret ratio of different methods when the nuisance model J=N and the policy- inducing model F are misspecified to differrent degrees, The logging policy a random policy.
Training Data n
Methods
400
600
800
1000
1200
1400
1600
ETO SPO+ DM
3.20%
1.83%
1.05%
0.72%
0.56%
0.47%
0.38%
2.16%
1.12%
0.60%
0.40%
0.30%
0.25%
0.20%
SPO+ DR PI
2.51%
1.50%
0.97%
0.73%
0.59%
0.50%
0.44%
SPO+ DR Lambda
2.14%
1.10%
0.62%
0.41%
0.34%
0.28%
0.23%
SPO+ DR Clip
2.15%
1.18%
0.65%
0.44%
0.37%
0.31%
0.26%
SPO+ ISW
15.49%
15.39%
15.46%
15.43%
15.63%
15.75%
15.75%
Naive ETO
15.44%
14.92%
10.77%
6.56%
4.59%
3.39%
2.87%
Naive SPO+ DM
15.46%
15.21%
11.56%
7.49%
5.57%
4.32%
3.67%
Naive SPO+ DR
15.47%
15.19%
11.91%
8.09%
6.04%
4.81%
4.18%
Naive SPO+ IPW
15.57%
15.67%
15.71%
15.74%
15.66%
15.79%
15.80%
Table 5: Mean relative regret ratio of different methods when the nuisance model JFN and the policy- inducing model J are correctly specified. The logging policy is a X, Xi-policy.
25

---

Training Data n
Training Data
Methods
400
1000
1600
400
1000
1600
FF misspecified degree
JF misspecified degree 4
ETO
11.55%
9.56%
8.68%
11.41%
10.03%
9.60%
F misspecified degree
F misspecified degree 4
SPO+ DM SPO+ DR PI
2.86%
1.10%
0.86%
4.19%
2.53%
2.27%
Well-specified Nuisance Model
3.57%
1.74%
1.39%
5.11%
3.36%
3.10%
SPO+ DR Lambda
2.93%
1.26%
1.03%
4.45%
2.79%
2.53%
JEN
SPO+ DR Clip 3.05%
1.34%
1.11%
4.57%
2.98%
2.66%
Naive SPO+ DM
15.59%
7.80%
4.37%
15.43%
8.08%
5.19%
Naive SPO+ DR
15.60%
8.45%
5.00%
15.38%
8.83%
5.90%
JFN misspecified degree
J=N misspecified degree
SPO+ DM SPO+ DR PI
10.47%
8.31%
7.68%
10.77%
9.37%
8.82%
Well-specified
9.32%
7.48%
6.97%
10.69%
9.80%
9.43%
Policy-inducing Model JF
SPO+ DR Lambda
9.15%
7.48%
6.98%
10.36%
9.10%
8.72%
SPO+ DR Clip
9.23%
7.37%
6.78%
10.37%
8.94%
8.46%
Naive SPO+ DM
15.63%
14.58%
13.78%
14.93%
13.08%
12.71%
Naive SPO+ DR
15.56%
14.54%
13.95%
14.92%
13.57%
13.30%
F,JN misspecified degree
F, FNJN misspecified degree 4
SPO+ DM SPO+ DR SPO+ DR Lambda
10.36%
8.27%
7.58%
10.66%
9.35%
8.90%
9.19%
7.21%
6.46%
10.35%
8.96%
8.55%
Both FN Misspecified
9.24%
7.47%
6.98%
10.36%
9.18%
8.75%
SPO+ DR Clip
9.38%
7.39%
6.76%
10.28%
8.94%
8.55%
Naive SPO+ DM
15.61%
14.56%
13.88%
14.96%
13.25%
12.77%
Naive SPO+ DR
15.49%
14.62%
14.12%
14.96%
13.48%
13.23%
Table 6: Mean relative regret ratio of different methods when the nuisance model J.N and the policy- inducing model F are misspecified to differrent degrees, The logging policy a Xp-poiyy..
Training Data n
Methods
400
600
800
1000
1200
1400
1600
ETO
3.09%
1.92%
1.28%
0.86%
0.58%
0.41%
0.34%
SPO+ DM
2.19%
1.19%
0.66%
0.43%
0.32%
0.24%
0.19%
SPO+ DR PI
2.49%
1.42%
1.00%
0.72%
0.60%
0.46%
0.45%
SPO+ DR Lambda
2.08%
1.15%
0.67%
0.46%
0.35%
0.26%
0.21%
SPO+ DR Clip
2.17%
1.21%
0.73%
0.51%
0.36%
0.30%
0.25%
SPO+ ISW
14.57%
14.65%
14.49%
14.04%
14.36%
14.26%
14.30%
Naive ETO
14.30%
13.99%
11.01%
7.55%
5.21%
3.76%
3.11%
Naive SPO+ DM
14.31%
14.21%
11.89%
8.44%
6.16%
4.69%
3,97%
Naive SPO+ DR
14.29%
14.23%
12.12%
8.77%
6.52%
5.12%
4.45%
Naive SPO+ IPW
15.52%
15.64%
15.64%
15.66%
15.76%
15.74%
15.70%
Table Mean relative regret ratio of different methods when the nuisance model JFN and the policy- inducing model F are correctly specified. The logging policy is a X, X2-policy.
26

---

Training Data n
Training Data
Methods
400
1000
1600
400
1000
1600
F misspecified degree
JF misspecified degree 4
ETO
10.08%
8.86%
8.18%
12.03%
11.15%
11.03%
misspecified degree
F misspecified degree 4
SPO+ DM SPO+ DR PI
2.91%
1.10%
0.83%
4.32%
2.56%
2.24%
Well-specified Nuisance Model
3.55%
1.73%
1.42%
5.27%
3.36%
3.04%
SPO+ DR Lambda
2.91%
1.28%
1.01%
4.50%
2.78%
2.49%
JEN
SPO+ DR Clip
3.07%
1.37%
1.12%
4.67%
2.94%
2.69%
Naive SPO+ DM
14.32%
8.92%
4.69%
14.52%
9.32%
5.46%
Naive SPO+ DR
14.34%
9.33%
5.37%
14.56%
9.78%
6.13%
JFN misspecified degree
J=N misspecified degree
SPO+ DM SPO+ DR PI
8.78%
7.90%
7.11%
11.93%
11.08%
10.55%
Well-specified
8.23%
6.97%
6.51%
11.91%
11.36%
11.07%
Policy-inducing
SPO+ DR Lambda
8.28%
7.14%
6.60%
11.92%
11.01%
10.38%
Model
SPO+ DR Clip
8.19%
7.04%
6.37%
11.72%
10.95%
10.36%
Naive SPO+ DM
14.86%
12.50%
12.07%
14.68%
13.84%
13.09%
Naive SPO+ DR
14.77%
12.78%
12.26%
14.65%
14.19%
13.70%
FFJN misspecified degree
F, misspecified degree 4
SPO+ DM SPO+ DR SPO+ DR Lambda
8.75%
7.83%
7.09%
11.95%
11.07%
10.53%
8.07%
6.66%
6.03%
11.79%
10.84%
10.40%
Both FN Misspecified
8.23%
7.14%
6.58%
11.90%
10.87%
10.43%
SPO+ DR Clip
8.09%
6.95%
6.41%
11.90%
10.74%
10.22%
Naive SPO+ DM
14.85%
12.66%
12.14%
14.70%
14.02%
13.11%
Naive SPO+ DR
14.75%
12.78%
12.26%
14.67%
14.17%
13.41%
Table 8: Mean relative regret ratio of different methods when the nuisance model J=N and the policy- inducing model F are misspecified to differrent degrees, The logging policy a X2X2-ocy
27

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide the new methodology in Section main theoretical results in Section 3 and numerical findings in Section
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We discuss the limitations of our paper in Section 6
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Our main theoretical results are in Section 3 and we have proposition in Section 2
All detailed proofs are provided in Appendix
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide open access data and code https: httpa:///github.com com/ CausalML/CCLOBaniiz
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide open access to data and code at httts:///iithtt com/
CausalML/CLOBanditt
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide detailed explanations for the experiment setup in Section 5land Ap-
pendix C.2
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We have statistical significance results in our experiments, and all our results are significant. We did not report them in the paper due to limited space, but can provide them upon request.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed reproduce the experiments?
28

---

Answer: [Yes]
Justification: Computer resources are reported in Appendix C
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htt.h//www.tpp/p.......//ppcccct
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is foundational research and not tied to particular applications.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
29


Reviews:
[{"review_id": "bo26p4Efdy", "reviewer": "Reviewer_wdeG", "summary": "The paper aims at the following problem. The learner observes side information $x$ and needs to output $z$. The Nature will then generate $Y$ (which depends on $x$, but may be randomised) and the learner will suffer loss $Y'z$. The key feature of the setup is that $Y$ is not directly observable. The paper describes convincing real-life applications fitting this scenario.\n\nOne is after a policy $z=\\pi(x)$ minimising the loss expectation on the basis of the past data. One can obtain it by estimating the conditional expectations $f_0(x) = E(Y\\mid x)$ first. However, this is not necessarily the best approach. In the style of reinforcement learning, the paper aims to estimate the policy value $V(\\pi)$ directly.\n\nThe paper puts forward an algorithm, or, rather an approach for this called IERM (I understand some steps in it involve optimisation, which is very hard to perform). The performance of the approach is studied in Theorem 1. It bounds the regret of the policy found by IERM w.r.t. the optimal policy in a class. The bound involves Rademacher complexity of the class.\n\nThere is substantial empirical evaluation.", "questions": "None.", "limitations": "Yes", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I believe the approach of the paper is useful and very practical.", "weaknesses": "The paper is very hard to read for an uninitiated person like me. I found it very hard to distinguish between given data, estimates, datapoints, random variables etc. \n\nPerhaps it would help if the paper were structured in a more traditional way with definitions and algorithms rather than the free-flowing narrative.\n\nPage 3, line 125: I am not sure I parse\n\nwhich we call as nuisance functions as they will be used to\n\ncorrectly. Did you mean\n\nwhich we call nuisance functions because they will be used to\n\n?\n\n(I should say I do not understand the choice of the word \"nuisance\". The pun is lost on me.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We now further clarify our problem and explain the data, estimates, random variables, and nuisances involved.\n\nFirst, let's consider a linear programming problem $\\min_{z\\in \\mathcal{Z}} y^\\top z$ where $z$ is the decision variable, $\\mathcal{Z}$ is the constraint set, and $y$ is the coefficient vector in the objective. This can model many problems, such as the shortest-path problem in our paper. Specifically, consider finding the shortest path from a starting point to a destination along edges on a graph (with $d$ edges in total). Any feasible path can be represented by a vector $z \\in \\\\{0, 1\\\\}^d$, with each entry corresponding to one edge and a value of 1 indicating that the edge is picked by the path. A vector $y$ gives the traveling time along each edge respectively. Thus, the total traveling time for a path $z$ is $y^\\top z$. The set $\\mathcal{Z}$ constrains $z$ to represent a path (or, a convex combination of paths) such that $\\text{argmin}_{z\\in\\mathcal{Z}}y^\\top z$ gives a path that achieves the shortest total traveling time.\n\nOur paper considers an uncertain environment where the objective coefficient is a random vector $Y$. For example, the traveling time could be stochastic and uncertain in practice. While the realized value of $Y$ is unknown at the time of decision-making, we may have access to some predictive contextual features $X$ (also considered a random vector). For example, although we do not know the actual traveling time in each shortest-path decision-making instance, we may observe features such as weather, time of day, and traffic conditions that are predictive of the traveling time. Contextual linear optimization (CLO) provides a formal way to incorporate features in decision-making, solving for the optimal decision that minimizes the expected cost upon observing each context value $x$:\n\\begin{align*}\n\\min_{z\\in\\mathcal{Z}}~ \\mathbb{E}\\left[Y \\mid X = x\\right]^\\top z.\n\\end{align*}\nSince the distribution of $(X, Y)$ is unknown in practice, existing CLO literature uses samples $(X_i, Y_i)_{i=1}^n$ to estimate the unknown function $f_0(x) = \\mathbb{E}[Y \\mid X = x]$. There are primarily two different approaches: the estimate-then-optimize approach and the integrated approach. The estimate-then-optimize approach directly fits a standard regression of $Y$ against $X$ to get an estimator $\\hat f$, usually by minimizing some statistical error measures like mean squared errors. The integrated approach considers the decision policies $\\pi_f$ induced by each candidate estimator $f$ (e.g., linear functions): \n\n\\begin{align*}\n\\pi_f(x) \\in \\text{argmin}_{z\\in\\mathcal{Z}}~ f(x)^\\top z.\n\\end{align*}\n\nThen it picks an optimal policy achieving the smallest sample average cost $\\frac{1}{n}\\sum_{i=1}^n Y_i^\\top \\pi_f(X_i)$. \nThe integrated approach directly targets the decision cost objective and is favored in recent literature. Our paper also focuses on the integrated approach.\n\nThe existing literature only considers the full-feedback setting where $Y$ is fully observed so its observations can be directly used to evaluate any decision policy. In contrast, we consider a partial or bandit feedback setting where we can only observe the total cost $C = Y^\\top Z$ for some historical decision $Z$ prescribed by a previous policy. Here the historical decision $Z$ is also considered as a random vector because it may have been prescribed according to $X$ or some other uncertain factors. Therefore, we have access to samples $(X_i, Z_i, C_i)_{i=1}^n$ but without observing the underlying cost coefficients $Y_i$'s. In this case, we cannot directly evaluate the sample average cost of any induced policy $\\pi_f$.\n\nOur Proposition 1 shows that under Assumption 1, we can evaluate the mean cost of a policy $\\pi_f$ by using a score function $\\theta$ in place of the unobserved $Y$. This score function may depend on not only the observed variables but also two unknown functions $f_0$ and $\\Sigma_0$. We thus propose to first construct some estimators $\\hat f$ and $\\hat \\Sigma$ for the unknown functions and then plug these estimators into the score function for the downstream evaluation and learning of decision policies. This process involves constructing estimators $\\hat f$ and $\\hat \\Sigma$ in the score function and the estimator for the policy value $\\frac{1}{n}\\sum_{i=1}^n \\theta(X_i, Z_i, C_i; \\hat f, \\hat \\Sigma)^\\top \\pi_f(X_i)$. Our Section 2 considers a slightly different procedure that incorporates additional sample splitting, but the overall idea is the same.\n\nWe refer to the unknown functions $f_0$ and $\\Sigma_0$ in the score function $\\theta$ as \"nuisance\" functions, because these functions are not directly used for decision-making  but merely serve as intermediaries for the evaluation of the policy value. This is standard terminology in statistics and is also frequently used in off-policy evaluation and learning. For example, the off-policy evaluation of a contextual bandit policy or reinforcement learning policy often involves estimating a behavior policy function (propensity score) or a conditional reward Q function. These are often referred to as nuisance functions as well [1].\n\nThank you for your comments again. We will further clarify the data, estimators and random variables and explain the meaning of ''nuisance'' in the camera-ready version.\n\n[1] Uehara, Masatoshi, Chengchun Shi, and Nathan Kallus. \"A review of off-policy evaluation in reinforcement learning.\" arXiv preprint arXiv:2212.06355 (2022).", "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": "", "extra_scores": {}}, {"review_id": "LaqNA4lXVY", "reviewer": "Reviewer_d35g", "summary": "This work addresses the partial bandit feedback setup for contextual linear optimization. The authors propose an algorithm based on Induced Empirical Risk Minimization (IERM), which incorporates doubly-robust estimation to handle the reward model misspecification. They provide a regret bound for the partial bandit feedback setup and, as a byproduct, offer a regret bound for the full bandit feedback setup under model misspecification. This contribution is significant due to the robustness of the theoretical results and the broad applicability of the findings. The paper is well-written and merits acceptance with only minor revisions.", "questions": "Based on my understanding, ETO is a family of algorithms that use estimates directly, such as plug-in policies with estimates. In contrast, IERM-type algorithms include an additional optimization step based on these estimates. This step appears to make IERM-type algorithms function similarly to optimism in the face of uncertainty (OFU)-type algorithms. What aspects of IERM-type algorithms make them more effective than ETO-type algorithms? Is this improvement related to their exploration schemes?", "limitations": "It is not well explained why the suggested algorithm has improved performance as compared to the existing algorithms.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This work accommodates the practicality such as partial feedback and model misspecification. In addition, the theoretical results are solid enough. The numerical experiments demonstrate the theoretical results well.", "weaknesses": "This setup is similar to partial monitoring. It would be great if the suggested model is compared with partial monitoring. In addition, it is hard to interpret the result to the reviewer, as the complexities of terms are not stated. The reviewer would like to see a summary of what the order of regret with respect to n is. Further, the model misspecification is not fully explained in the first two sections. The authors should explain the model misspecification before starting a theoretical analysis. Lastly, there are some minor errors in the presentation:\n- In line 108, \"is\" should be corrected.\n- There is no definition of $\\chi^2_{n,\\delta}$.\n- In line 74, \"in that that\" should be corrected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments. We now address each point individually. \n\n**Comparison to partial monitoring.** It is interesting to compare our problem with partial monitoring. There are at least two major differences. One is that partial monitoring usually considers an online setting where the learner interacts with the environment and collects data on the fly while making decisions. In contrast, we consider an offline setting where the learner is provided with a fixed dataset without further interaction. See our response to Reviewer h4hQ for more details. The other is that partial monitoring is designed to allow the observed feedback to be different from the reward associated with each decision (a.k.a, arm) [1]. However, our setting is closer to the typical bandit setting, since our  observed feedback $C = Y^\\top Z$ is exactly the decision cost (i.e., negative reward) of each decision $Z$. \n\n**Complexity terms in theoretical guarantees.** Thank you for raising this issue. Our regret bounds are formulated in terms of the critical radius, a widely used complexity measure in statistical learning theory. This measure is very general and recovers the information-theoretically optimal rate for many function classes [2]. However, we agree that this may be abstract and could impede the readers' understanding. As we explain below Theorem 1, a concrete example is when the function classes $\\mathcal{G}_1, \\mathcal{G}_2$ are VC subgraph classes with VC dimension $\\eta$. The corresponding critical radius is $\\tilde{r} = O(\\sqrt{\\eta/n})$. Then the regret bound in Theorem 1 reduces to \n\\begin{align*}\n   \\text{Reg}(\\hat{\\pi}) \\lesssim \\left(\\frac{\\eta}{n}\\right)^{\\frac{\\alpha + 1}{\\alpha + 2}} + \\text{Reg}(\\tilde{\\pi}^*) \\left(\\frac{\\eta}{n}\\right)^{\\frac{1}{2}} + \\frac{\\eta}{n} + \\text{Rate}^N(n/2, \\delta/4) +  \\text{Reg}(\\tilde{\\pi}^*).\n\\end{align*}\nThe regret rate depends on the degree of misspecification characterized by $\\text{Reg}(\\tilde{\\pi}^*)$ (i.e, the regret of the best-in-policy-class policy), the nuisance estimation error rate $\\text{Rate}^N(n/2, \\delta/4)$, and the margin parameter $\\alpha$. Hu et al. [3] study the full-feedback setting without misspecification, so there is no nuisance estimation error or misspecification error (i.e., $\\text{Rate}^N(n/2, \\delta/4) = 0$ and $\\text{Reg}(\\tilde{\\pi}^*) = 0$). Our bound recovers their fast rate  $O((\\eta/n)^{(\\alpha+1)/(\\alpha+2)} + \\eta/n)$ that interpolates between $O(n^{-1/2})$ and $O(n^{-1})$ according to the margin parameter $\\alpha$. Our new bound shows that this fast rate could be dominated by the slow rate $O(\\text{Reg}(\\tilde{\\pi}^*) ({\\eta}/{n})^{{1}/{2}})$ when there is significant misspecification. Moreover, our bound shows that in the bandit-feedback setting, we also need to estimate nuisance functions, and the corresponding error $\\text{Rate}^N(n/2, \\delta/4)$ can also affect the final regret bound. The order of this nuisance error rate depends on the form of the score function (see Proposition 2) and the complexity of estimating the nuisances. For example, if we use the doubly robust score and both nuisances can be estimated at rates $ o(n^{-1/4})$, then $\\text{Rate}^N(n/2, \\delta/4) = o(n^{-1/2})$ is negligible [4]. We plan to explain these clearly in a dedicated remark  in Section 3. \n\n**Model misspecification.** Thanks for your suggestion of explaining the model misspecification before our theoretical analysis. We totally agree with this suggestion, because accommodating model misspecification is one of our major technical contributions. We plan to  explain model misspecification in Section 1.1 when we first introduce the induced policy class. \n\n**What makes IERM-type algorithms more effective?** IERM can be more effective than ETO because it more directly targets the decision-making problem. ETO first constructs an estimator $\\hat f$ for the unknown function $f_0(x) = \\mathbb{E}[Y \\mid X = x]$ by fitting standard regressions (e.g., linear regressions), and then solve optimization $\\min_{z\\in\\mathcal{Z}}\\hat f(x)^\\top z$ for each context value $x$ to get the final   policy. However, the estimation step typically optimizes some regression error (e.g., least squares objective), without considering the downstream decision-making problem. \n\nIn contrast, IERM considers the policies $\\pi_f \\in \\text{argmin}_{z\\in\\mathcal{Z}}f(x)^\\top z$ induced by candidate regression functions $f$ (e.g., linear functions) and then selects the policy  achieving the smallest in-sample average  cost. IERM directly optimizes the decision cost objective, thereby achieving better decision performance in many scenarios. This is quite different from the optimism in face of uncertainty type algorithms for balancing the exploration and exploitation in online decision-making. \n\n**Minor errors.** Thanks for pointing out the typos, which we will correct in the future. Regarding the definition of $\\chi^2_{n, \\delta}$, it is a vanishing sequence used to characterize the error in estimating the two nuisance functions. We will change the first two lines of Proposition 2 to the following: ''For any given $\\delta \\in (0, 1)$, let $\\chi_{n, \\delta}$ be a positive sequence converging to $0$ as $n \\to \\infty$, such that the mean square errors of the nuisance estimates satisfy the following with probability at least $1-\\delta$''. \n\n[1] Kirschner, Johannes, Tor Lattimore, and Andreas Krause. \"Linear partial monitoring for sequential decision making: Algorithms, regret bounds and applications.\" The Journal of Machine Learning Research (2023).\n\n[2] Wainwright, Martin J. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge university press, 2019.\n\n[3] Hu, Yichun, Nathan Kallus, and Xiaojie Mao. \"Fast rates for contextual linear optimization.\" Management Science (2022).\n\n[4] Victor Chernozhukov, Mert Demirer, Greg Lewis, and Vasilis Syrgkanis. Semi-parametric efficient policy learning with continuous actions. NeurIPS 2019.", "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": "", "extra_scores": {}}, {"review_id": "ZUS5Td1Li3", "reviewer": "Reviewer_h4hQ", "summary": "This paper studies Contextual Linear Optimization (CLO) with bandit feedback and presents a class of algorithms termed Induced Empirical Risk Minimization (IERM). The authors also derive the regret upper bounds. The regret analysis accounts for the misspecification of the policy class and incorporates a margin condition that potentially enables a faster regret rate.", "questions": "N/A", "limitations": "Limitations are adequately discussed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The extension of the CLO problem to bandit feedback is an important and novel research direction.\n2. The mathematical formulations and proofs are rigorous and well-presented.\n3. The analysis allows for model misspecification in the induced policy class.", "weaknesses": "Although I believe this paper is technically sound, the readability could be improved. The presentation of the problem and model could be clearer, especially for readers unfamiliar with the CLO problem. It would be better to provide a more detailed explanation of the problem setting before delving into mathematical formulas. For example, in the introduction, the authors could explain the interaction protocol between the learner and the environment, and specify which quantities are known or unknown to the learner/environment. Such elaborations would make the paper more accessible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We agree that providing more background information on the CLO problem would be helpful. Here, we clarify the unknown quantities and the interaction between the learner and the environment.\n\nIn classic CLO problems, the learner aims to solve the optimization problem $\\min_{z\\in\\mathcal{Z}}\\mathbb{E}[Y^\\top z \\mid X = x] = f_0(x)^\\top z$ for all observed context values $x$, where $f_0(x)$ is the conditional expectation function $\\mathbb{E}[Y \\mid X = x]$. This means the learner seeks to minimize the expected  total decision cost $Y^\\top z$ given the observed context value $x$. \nThe true  distribution of $(Y, X)$ is unknown, making the unknown $f_0$ function the main challenge for the learner. \n\n\nBefore making decisions, the learner  needs to estimate the $f_0$ function from samples $(X_i, Y_i)_{i = 1}^n$, typically assumed to be i.i.d draws from the population distribution of $(X, Y)$. Note that this is an offline setting: the learner is provided with a batch of existing data $(X_i, Y_i)$ for $i=1, ..., n$ and uses this dataset for learning, without further interaction with the environment to generate more data while learning and making decisions.  The existing literature has considered two major types of approaches to learning $f_0$ and the corresponding decision policy:  estimate-then-optimize (ETO) approaches and integrated approaches. The latter directly targets the decision objective and is thus favored by many recent papers. \n\nOur paper studies a CLO problem where the cost  coefficient $Y$ is not directly observed in the data. Instead, we observe only the total costs of some historical decisions implemented in the past. Specifically, we have access to some historical decisions $Z_1, \\dots, Z_n$, made by some previous policies that might depend on the corresponding contexts $X_1, \\dots, X_n$ and potentially other unobserved factors. The total costs $C_i = Y_i^\\top Z_i$ for these decisions were recorded,  but the underlying cost coefficient $Y_1, \\dots, Y_n$ were not. This means the learner only observes the costs of the decisions that were actually implemented, without information on the costs of other unimplemented counterfactual decisions. These constitute the observed samples $(X_i, Z_i, C_i)_{i = 1}^n$. Again, we consider an offline learning setting where the learner is given this dataset collected under  previous policies, without further interacting with the environment to generate new data. The learner does not know the population distribution of $(X, Z, Y, C)$ and aims to use the given dataset  $(X_i, Z_i, C_i)$ for $i=1, ..., n$ to learn a new decision policy for future decision-making.\nThis is akin to the offline contextual bandits widely studied in the literature [1, 2, 3]. However, the offline contextual bandit literature mostly considers the optimization over finitely many arms, while we consider a more general constrained linear programming problem. We in particular study how to extend the integrated IERM approach from regular CLO problems to CLO with partial/bandit feedback. \n\nIn summary, the main unknown quantity to the learner in the CLO problems is the conditional expectation function $f_0(x) = \\mathbb{E}[Y \\mid X = x]$ of the cost coefficient $Y$ given contextual features $X$. Once this function is known,  the CLO problems can be solved easily. Classic CLO literature considers learning this unknown function from samples of the cost coefficients and the contexts $(X_i, Y_i)$. Our paper considers the setting where only total costs $C_i$ associated with historical decisions $Z_i$ (along with the contexts $X_i$) can be observed, but the underlying cost coefficients $Y_i$'s are unobserved. \nBoth these CLO literature and our paper consider an offline setting where the learner is given a fixed set of data to decide a policy, without further interacting with the environment to collect more data. \nIt would be interesting to consider online settings where the learner can directly interact with the environment, generating data on the fly while learning and making decisions. But the online learning is out of the scope of our current paper. \n\n\nThanks for your suggestions. We will incorporate these clarifications into our Section 1. In particular, we will highlight that our paper considers an offline learning setting in both the abstract and introduction. \n\n\n[1] Dudík, Miroslav, John Langford, and Lihong Li. \"Doubly robust policy evaluation and learning.\" Proceedings of the 28th International Conference on International Conference on Machine Learning. 2011.\n\n[2] Dudík, Miroslav, et al. \"Doubly Robust Policy Evaluation and Optimization.\" Statistical Science 29.4 (2014): 485-511.\n\n[3] Swaminathan, Adith, and Thorsten Joachims. \"Batch learning from logged bandit feedback through counterfactual risk minimization.\" The Journal of Machine Learning Research 16.1 (2015): 1731-1755.", "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": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

Thank you for your thoughtful comments and constructive suggestions. We are encouraged to hear that you find our theoretical results solid, our numerical experiments demonstrate the theoretical results well, and our approach  useful and practical.

We appreciate your suggestions for improving the readability and presentation of our paper. We have addressed each of your points individually, and we will incorporate these clarifications in the camera-ready version if our paper is accepted. We are committed to enhancing the presentation and writing of our paper and are grateful for your valuable feedback.

Please let us know if you have any further comments. We are happy to discuss them.


Best regards,

The Authors.

Meta-review: This paper studies the contextual linear optimization problem under 'bandit feedback', i.e. only one projection of the random cost coefficient vector where the projection depends on which decision was made. Some reviewers had more expertise in the area than others, but everyone was positive about the technical contributions of this work. One criticism that was raised by multiple reviewers was that the paper was challenging to read for someone who is uninitiated in the CLO problem (even if they are familiar with adjacent areas, such as online learning/bandits/statistics/causal inference). Given that NeurIPS sees a broad audience, I strongly encourage the authors to make every effort possible to improve readability for the camera-ready version, starting with the reviewers' constructive suggestions.
Decision: Accept (poster)