Contextual Linear Optimization with Bandit Feedback

Authors: yichun  hu
nathan  kallus
xiaojie  mao
yanchen  wu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:32:53

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.

Main paper: 
 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 a decision z ∈ Z that incurs an uncertain cost Y ⊤ z determined by a random cost vector Y ∈ R d that is not observed at decision time. We do, however, observe predictive features X ∈ R p 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 a conditional expectation:v * (x) = min z∈Z E Y ⊤ z | X = x = min z∈Z f 0 (x) ⊤ z, where f 0 (x) = E[Y | X = x]. (1)We assume throughout that Z is a polytope (Z = Conv(Z ∠ ) for some vertex set Z ∠ < ∞ with sup z∈Z ∠ ∥z∥ ≤ B) and Y is bounded (without loss of generality, Y ∈ Y = {y : ∥y∥ ≤ 1}).CLO has been the focus of much recent work [e.g., 9, 11, 14, 27, 30] , due to its relevance to datadriven operational decision making in many applications such as network optimization, portfolio optimization, product recommendation, etc. The key question in these is how to use data to learn a good policy, π : R p → Z, mapping feature observations to effective decisions. All of this literature studies an offline setting, where a batch of existing data (X i , Y i ) for i = 1, . . . , n is observed. These data are viewed as random draws from the joint distribution of (X, Y ), and the goal is to learn an effective decision policy from them. Crucially, this assumes that we fully observe the random cost vector Y i 's, meaning that we fully know the corresponding costs Y ⊤ i z for any potential decision z. This may be unrealistic in many applications.Consider for example the instantiation of Eq. ( 1) as a stochastic shortest path problem of transporting one unit from a 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 to apply existing approaches here would consist of simultaneous observations of the travel times on every single edge, encapsulated in the elements of Y i '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, 33] , which is based on the total length of historical rides. Namely, instead of observing the entire Y i , we only observe the total travelling time C i = Y ⊤ i Z i for the path Z i 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 to 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 bandit-feedback data. Second, we derive upper bounds on the regret (i.e., decision sub-optimality) of the policy that minimizes the estimated objective. Our regret analysis accounts for the misspecification of the policy class and incorporates a margin condition that potentially enables a faster regret rate. This significantly extends existing theory for full-feedback CLO, 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 well-known SPO+ loss in [11] ) can be adapted to our setting, enabling efficient policy optimization. We empirically test this in simulated shortest path problems and provide practical insights.We first review two major approaches to the CLO problem with full feedback: an estimate-thenoptimize (ETO) approach and an end-to-end induced empirical risk minimization (IERM) approach. To this end, we need to define the generic plug-in policy π f for any given f : R p → R d : π f (x) ∈ arg min z∈Z f (x) ⊤ z.(EQUATIONNote that for any given covariate value x, this corresponds to a linear programming problem with coefficients given by f (x). An optimal policy in Eq. ( 1) corresponds to π f0 . Without loss of generaility, we restrict the value of π f (x) to the set of vertices Z ∠ of the polytope Z with ties broken according to some fixed rule (e.g., a total ordering over Z ∠ such as lexicographic).The ETO approach starts with estimating f 0 in Eq. ( 1) by any supervised learning method for predicting Y given X. This can, e.g., be implemented by minimizing a prediction fitness criterion (e.g., sum of squared errors) over a hypothesis class of functions F ⊆ [R p → R d ] (e.g., linear functions, decision trees, neural networks). After training an estimator f of f 0 , 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 ∈ 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 [14] , we consider an IERM formulation that minimizes the sample average cost over the class of plug-in policies induced by F:EQUATION)This approach is end-to-end in that it directly targets the decision-making objective. Recent literature demonstrates that end-to-end approaches like IERM often outperform the ETO approach [12] . 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 f 0 , and the policy class Π F does not include the globally optimal decision policy π f0 [e.g., 11, 14] . While Eq. ( 3) involves a challenging bi-level optimization due to the definition of Π F , practical computational approximations have been proposed [11, 16] .Nonetheless, the IERM formulation in Eq. ( 3) requires observing the full feedback Y i 's in the data.In this paper, we study how to extend this approach to the setting 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 = {(X 1 , Z 1 , C 1 ), . . . , (X n , Z n , C n )} that are independent draws from a distribution P on (X, Z, C) generated in the following way. We first draw (X, Z, Y ) where the (X, Y ) distribution is as in the full feedback setting and Z 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 | Z, X] = Z ⊤ f 0 (X) (which could follow from Z ⊥ ⊥ Y | X). 2. (Coverage) inf z∈span(Z):∥z∥=1 E[(Z ⊤ z) 2 | X] > 0 almost surely.The ignorability condition is a 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 can 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 π(x) that has low regretEQUATIONwhereV (π) = E X f 0 (X) ⊤ π(X) .An important special case is when Z ∠ = {(1, 0, . . . , 0), . . . , (0, . . . , 0, 1)} is the canonical basis and Z is the simplex. This corresponds to choosing one of d actions (or randomizing between them). The full-feedback problem in this case is cost-sensitive classification [10] . In the bandit feedback case, with the restriction Z ∈ Z ∠ , it is known as a logged or offline contextual bandit, and a long line of literature studies the problems of estimating and optimizing V (π) [1, 8, 18-20, 23, 24, 32, 34-36, 42-45] . It is closely related to causal inference, viewing each component of Y as the potential outcome for the corresponding action (or treatment), where we only see the realized outcome C corresponding to the factual action with index 1 in Z ∈ Z ∠ and see nothing about counterfactual actions Z ∠ \{Z}.Two key differentiating characteristics of our problem with a 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 on the output of decision policies.Going beyond just finite discrete arms, [21, 22, 29] consider the logged contextual bandit with a continuum of arms, which is not generally representable in terms of the problem in Section 1.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, X] is linear in Z according to ignorability in Section 1.2). Relative to this work, our unique contributions are the use 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. 
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 do not observe Y i in our data, it is not as straightforward as a sample average, n i=1 Y ⊤ i π(X i )/n. Instead, we need alternative ways to identify V (π).Define Σ 0 (X) = E ZZ ⊤ | X and recall f 0 (X) = E[Y | X], which we will use to characterize the policy value V (π). We refer to these functions as nuisance functions following the existing literature on off-policy evaluation and learning in 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 θ(x, z, c; f, Σ) be a score function such thatEQUATIONwhere E P denotes taking expectation over P . Proposition 1 summarizes a few possible choices. Proposition 1. The following choices of θ(x, z, c; f, Σ) all satisfy Eq. (5):1. (Direct Method) θ DM (x, z, c; f, Σ) = f (x); 2. (Inverse Spectral Weighting) θ ISW (x, z, c; f, Σ) = Σ † (x)zc; 3. (Doubly Robust) θ DR (x, z, c; f, Σ) = f (x) + Σ † (x)z(c -z ⊤ f (x)).Here Σ † denotes the Moore-Penrose pseudo-inverse of matrix Σ.The doubly robust identification in Proposition 1 is a generalization of the identification in [6] in that we allow for rank-deficient Σ 0 by using a pseudo-inverse. Otherwise, our work significantly differs from [6] in terms of policy class specification, computation and theoretical analyses (see Section 1.3). Note that identification in Proposition 1 exploits 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 Z ∠ ; 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 f 0 , Σ 0 . 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 n is even. The extension to K-fold version is straightforward.First, we split D into two equal-sized subsamples, D 1 and D 2 , each with n/2 data points. We can use D 1 as an auxiliary sample to estimate the nuisance functions f 0 and Σ 0 , denoting the estimates as f1 and Σ1 . We then use D 2 as a main sample to obtain an estimate of V (π) using f1 and Σ1 :2 n i∈D2 θ(X i , Z i , C i ; f1 , Σ1 ) ⊤ π(X i ).Of course, we can switch the roles of D 1 and D 2 , i.e., we use D 2 to get nuisance estimates f2 and Σ2 , then use D 1 to estimate V (π). Finally, given an induced policy class Π F , the IERM policy π minimizes the average of the above two V (π) estimates over Π F :EQUATIONRemark 1 (Estimation of f 0 ). The estimator f (x) can be obtained by minimizing the least square loss over some appropriate function class F N :EQUATION)Note that two places in Eq. (6) require the specification of a function class for modeling f 0 : the F class used to induce the policy class Π F , and the F N 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 F N . In fact, it might be desirable to use a more flexible function class for F N 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 F N in Section 5.Remark 2 (Estimation of Σ 0 ). There are multiple ways to estimate Σ 0 . For example, [6] suggest estimating Σ 0 by running a multi-task regression for all (j, k) entries to the matrix over some appropriate hypothesis spaces S jk : Σ = arg min Σ11∈S11,...,Σ dd ∈S dd i∈D ∥Z i Z ⊤ i -Σ(X i )∥ 2 F ro . 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 z 1 , . . . , z m , such as the feasible paths for stochastic shortest path problems (see experiments in Section 5) or more generally the vertices in Z ∠ . Then we can first estimate the propensity scores e 0 (z | X) for z = z 1 , . . . , z m using an suitable estimator ê(z | X) and then estimate Σ 0 (X) = m j=1 z j z ⊤ j e 0 (z j | X) by Σ(X) = m j=1 z j z ⊤ j ê(z j | X).) θIPW (x, z, c; f , ẽ) = z ẽ(x) c; 3. (Doubly Robust) θ DR (x, z, c; f , ẽ) = f (x) + z ẽ(x) (c -f (x)).In the three score functions above, all vector operations are entry-wise operations.From Lemma 1, the new formulations above have very similar structure as our previous formulation in Section 2 Proposition 1. The major differences are that we restrict to the discrete actions z 1 , . . . , z m , redefine certain variables accordingly, and consider a simplex set as the constraint. We note that the identification in Lemma 1 mimics the DM, IPW and DR identification in offline contextual bandit learning [e.g., 1, 7, 43]. Since the identification formulae are analogous to those in Section 2, we can easily apply the same policy learning methods in Section 2 and the SPO+ relaxation in Section 4. 
theoretical analysis: 
 In this section, we provide a theoretical regret analysis for the IERM approach with bandit feedback, allowing for model misspecification in the induced policy class Π F . That is, we allow the globally optimal policy π f0 to be not included in the class Π F . We derive an upper bound on the regret of the IERM approach, in terms of the complexity of the policy class Π F , its misspecification bias, and the estimation errors of nuisance functions.Before stating the main theorem, we define a few important notations. Let π * be the best-in-class policy that minimizes expected regret over Π F :π * ∈ arg min π∈Π F E f 0 (X) ⊤ π(X) .We note that π * can be different from the global optimal policy π f0 if π f0 ̸ ∈ Π F , and Reg(π * ) characterizes the extent of misspecification in the induced policy class Π F . For j = 1, 2, we define the function classEQUATIONFor any function class G : X × Z × C → R, we define the local Rademacher complexity asR n (G, r) = E sup g∈G,∥g∥ 2 ≤r 1 n n i=1 ϵ i g(X i , Z i , C i ) ,where ϵ i are i.i.d. Rademacher variables, and∥g∥ 2 = E P [g 2 (X, Z, C)].Throughout Section 3, we impose two assumptions. Assumption 2 concerns the algorithms we use to estimate the nuisance functions f 0 , Σ 0 . It requires that the nuisance estimates are close enough to their true values, and ∥θ(x, z, c; f , Σ)∥ is bounded.Assumption 2 (Nuisance Estimation). The nuisance estimators f , Σ trained on a sample of size n satisfy that ∥θ(x, z, c; f , Σ)∥ ≤ Θ for all x, z, c, and for any δ ∈ (0, 1) and π ∈ Π F , with probability at least 1 -δ,E P θ(X, Z, C; f 0 , Σ 0 ) -θ(X, Z, C; f , Σ) ⊤ (π(X) -π * (X)) ≤ Rate N (n, δ).In Section 3.1, we will relate Rate N (n, δ) to the errors in estimating the individual nuisance functions f 0 and Σ 0 for different choices of score function θ.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 us to get faster regret rates. This type of condition was originally considered in the binary classification literature [2, 38] . It is recently extended to contextual linear optimization by [14] , which we describe below. Assumption 3 (Margin Condition). Let Z * (x) = arg min z∈Z f 0 (x) ⊤ z, and∆(x) = inf z∈Z ∠ \Z * (x) f 0 (x) ⊤ z -inf z∈Z f 0 (x) ⊤ z if Z * (x) ̸ = Z and ∆(x) = 0 otherwise. Assume for some α, γ ≥ 0, P X (0 < ∆(X) ≤ δ) ≤ (γδ/B) α ∀δ > 0.Lemmas 4 and 5 in [15] show that Assumption 3 generally holds with α = 1 for sufficiently wellbehaved f 0 and continuous X and with α = ∞ for discrete X. Moreover, any CLO instance trivially satisfies α = 0. Overall, a larger α 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 α parameter could lead to faster regret rates.We now provide an upper bound on the regret of the IERM policy π in Eq. ( 6). Theorem 1. Suppose Assumptions 2 and 3 hold, and Z * (X) defined in Assumption 3 is a singleton almost surely. Suppose there exists a positive number r (that depends on n) that upper bounds the critical radii of the function classesG 1 , G 2 almost surely (i.e., R n/2 (G 1 , r) ≤ r2 and R n/2 (G 2 , r) ≤ r2) and satisfies the inequalities 3nr 2 /128 ≥ log log 2 (1/r), and 2 exp -3nr 2 /128 ≤ δ/4. Then, there exists a positive constant C(α, γ) such that with probability at least 1 -δ, we haveReg(π) ≤B 12Θ C(α, γ)r 2α+2 α+2 + 24BΘ C(α, γ) Reg(π * ) B α 2(1+α) r + r2 + 2Rate N (n/2, δ/4) + 2Reg(π * ).The upper bound in Theorem 1 involves several different types of error terms. The first type is the critical radii r that characterize the complexity of the function classes G 1 , G 2 . This is a common complexity measure for function classes in statistics and machine learning [41] . For example, as we will discuss below, the critical radii scale asÕ( η/n) if G 1 , G 2 are VC subgraph classes of dimension η.The second type is the term Rate N (n/2, δ/4) resulted from the errors in estimating the nuisance functions f 0 , Σ 0 . Similar nuisance estimation errors also appear in the previous literature on offline contextual bandit learning [1, 5, 45] or more general learning problems that involve nuisance functions [13] . Below we will further discuss this term for different choices of score functions θ. 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 Π F is well-specified, i.e., π f0 ∈ Π F , we would have Reg(π * ) = 0, and the regret upper bound would scale with the function class complexity through a fast rate O(r 2α+2 α+2 ). For VC subgraph classes with r = Õ( η/n), the rate can range from Õ( η/n) for α = 0 to Õ(η/n) for α = ∞. However, if the policy class is misspecified so that Reg(π * ) > 0, then the dominating term related to r would be a slow rate O(r). This reveals an interesting phase transition between the correctly specified and misspecified settings, which is not discovered in the previous theory that considers only well-specification [14] . Remark 3. The constant coefficients in the regret upper bound can be improved when 2(1 + α)/α is an integer (which accommodates the case of α = 1 justified in [15] ):Reg(π) ≤B 12Θ C(α, γ)r 2α+2 α+2 + 24(α + 1) α + 2 BΘ C(α, γ) Reg(π * ) B α 2(1+α) r + r2 + 2α + 2 α + 2 Rate N (n/2, δ/4) + 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 1 except that it handles an inequality slightly differently. Specifically, the proof of Theorem 1 involves a transcendental inequality of the form Reg(π) ≤ c 1 Reg(π) α 2(1+α) r + c 2 for certain positive terms c 1 , c 2 . This inequality is difficult to solve exactly, so we can only get an upper bound on its solution. It turns out that we can get a better upper bound when 2(1 + α)/α is an integer.The nuisance estimation rate. We now show that Rate N (n, δ) can be effectively controlled for the DM, ISW and DR score functions. In pariticular, Rate N (n, δ) is can be bounded by the estimation errors of the nuisance functions f 0 and Σ 0 . Proposition 2. For any given δ ∈ (0, 1), let χ n,δ be a positive sequence converging to 0 as n → ∞, such that the mean square errors of the nuisance estimates satisfy the following with probability at least 1 -δ:max E X [∥Proj span(Z) ( f (X) -f 0 (X))∥ 2 ], E X [∥ Σ † (X) -Σ † 0 (X)∥ 2 Fro ] ≤ χ 2 n,δ ,whereProj span(Z) ( f (X) -f 0 (X)) is the projection of f (X) -f 0 (X) onto span(Z). Then, 1. If we take θ = θ DM , we have Rate N DM (n, δ) = O(χ n,δ ); 2. If we take θ = θ ISW , we have Rate N ISW (n, δ) = O(χ n,δ );in causal inference and offline contextual bandit learning [1, 5, 6] . Notably, here we only need to bound the projected error on the nuisance estimator f , which handles the setting when span(Z) does not cover the whole R d space, as is the case with the shortest path problem in Section 5.Computing the critical radius. The critical radius, r characterizes the complexity of the function classes G 1 and G 2 defined in Eq. ( 8). The next proposition shows that r is of order Õ(1/ √ n) if the function classes have finite VC-subgraph dimensions. For simplicity, we focus on G 1 only. Proposition 3. Suppose G 1 has VC-subgraph dimension η almost surely. Then for any δ ∈ (0, 1), there exists a universal positive constant C such thatr = C η log(n+1)+log(8/δ) n (9)satisfies the inequalities R n (G 1 , r) ≤ r2 , 3nr 2 /64 ≥ log log 2 (1/r), and 2 exp -3nr 2 /64 ≤ δ/4.Although our 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 a margin-dependent fast rate with potential policy misspecification in the full feedback setting. Theorem 2. Suppose Z * (X) defined in Assumption 3 is a singleton almost surely. DefineG F = (x, y) → y ⊤ (π(x)-π * (x))ρ 2B : π ∈ Π F , ρ ∈ [0, 1]and rF be any solution to the inequality R n (G F , r) ≤ r 2 satisfying 3n(r F ) 2 /64 ≥ log log 2 (1/r F ) and 2 exp -3n(r F ) 2 /64 ≤ δ. If Assumption 3 further holds, then, with probability at least 1 -δ,Reg(π F ) ≤ B 12 C(α, γ)r F 2α+2 α+2 + 24B C(α, γ) Reg(π * ) B α 2(1+α) rF + (r F ) 2 + 2Reg(π * ).The regret bound is similar to that in Theorem 1 for the bandit setting, except that it does not have the nuisance error term 2Rate N (n/2, δ/4). This is because, in the full feedback setting, we observe the entire Y vector, so we do not need to estimate any nuisance functions and can consider the nuisance estimation error term Rate N (n/2, δ/4) as zero. When Π F is a well-specified VC-subgraph class with dimension η, we have Reg(π * ) = 0, and rF = Õ( η/n), so the bound in Theorem 2 reduces to O((η/n) (α+1)/(α+2) + η/n). This bound interpolates between O(n -1/2 ) and O(n -1 ) according to the margin parameter α, recovering the fast rate in the full-feedback setting without misspecification as given in [14] . In contrast, our bound in Theorem 2 additionally quantifies the impact of policy misspecification, and its generalization Theorem 1 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 ∈ F, making it computationally intractable to optimize. In the full feedback setting, tractable surrogate losses have been proposed [11, 16] . In this section, we briefly explain the SPO+ loss in [11] and how it can be used in the bandit setting.The full feedback IERM problem in Eq. ( 3) can be viewed as minimizing the following loss over F:min f ∈F 1 n n i=1 l IERM (f (X i ), Y i ), where l IERM (f (x), y) = y ⊤ π f (x) -min z∈Z y ⊤ z.This IERM loss is equivalent to the "smart predict-then-optimize" (SPO) loss in Definition 1 of [11] . Letting z * (y) ∈ arg min z∈Z y ⊤ z with the same tie-breaking rule as in π f , [11] propose the SPO+ surrogate loss:min f ∈F 1 n n i=1 l SPO+ (f (X i ), Y i ), where l SPO+ (f (x), y) = max z∈Z (y -2f (x)) ⊤ z -(y -2f (x)) ⊤ z * (y).The SPO+ loss has many desirable properties: given any fixed y, it is an upper bound for the IERM loss, it is convex in f (x), and its subgradient at f (x) has a closed form 2(z * (y) -z * (2f (x) -y)). The logging policy is a random policy.In the bandit setting, although Y i is not observed, the score θ(X i , Z i , C i ; f , Σ) plays the same role (see Eqs. ( 3) and ( 6)). So it is natural to adapt the SPO+ loss to the bandit setting by replacing the unobserved cost vector Y i by the corresponding score θ(X i , Z i , C i ; f , Σ):fSPO+ ∈ arg min f ∈F 1 n j=1,2 i∈Dj l SPO+ f (X i ), θ(X i , Z i , C i ; f3-j , Σ3-j ) .Then we use the plug-in policy π fSPO+ as 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 i 's by the corresponding scores. 
numerical experiments: 
 We now test the performance of our proposed methods in a simulated stochastic shortest path problem following [11, 14] . Specifically, we aim to go from the start node s to the end node t on a 5 × 5 grid consisting of d = 40 edges, where the costs of traveling on the edges are given by the random vector Y ∈ R 40 (see Fig. 1 ). We consider covariates X ∈ R 3 and a function f 0 (x) = E[Y | X = x] whose components are cubic polynomials. The corresponding shortest path problem can be easily formulated into a CLO problem with the constraint set Z given by standard flow preservation constraints. The resulting optimal solution z belongs to {0, 1} 40 , indicating whether passing each edge or not. We note that there are m = 70 feasible paths z 1 , . . . , z m ∈ Z from the source node to the target node, and the feasible paths are linearly dependent with a rank of 18.We consider a bandit feedback setting, observing only the total traveling costs C of the historical decisions Z generated by a 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. In this section, we report results using a random logging policy that picks a path from all feasible ones at random regardless of the covariate value. In Appendix C, we further study the performance of two different covariatedependent logging policies: one that picks paths according to the sign of the first covariate X 1 , and one that depends on the signs of both X 1 and X 2 . The empirical insights from the covariate-dependent 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 approach2 . 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 a 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 f 0 is estimated by a bandit-feedback regression given in Eq. ( 7) with a ridge penalty, and we test out the three aforementioned function classes for the nuisance class F N as well.In DR, the nuisance Σ 0 (x) is estimated by the propensity score approach described in Remark 2, 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 PI) as in the original θ DR definition; lambda regularization (DR Lambda), where we replace Σ † with (Σ + λI) -1 for a positive constant λ; and clipping (DR Clip), where eigenvalues of Σ below a 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 are summarized in Appendix C. Finally, we 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 as 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 π f0 . Table 1 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 n = 400, 1000, 1600, and defer results for other sizes to 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 a close inspection, we found that the bias adjustment term that involves the 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. 2 : Mean relative regret ratio of different methods when the nuisance model F N and the policyinducing 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 policy-inducing model F or the nuisance model F N 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+ is correctly specified. This is consistent with the findings in the previous full-feedback CLO literature [e.g., 11, 12, 14] , showing the benefit of integrating estimation and optimization for misspecified policy models. However, the advantage of the endto-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 we may prefer more flexible models for accurate nuisance modeling, while using simpler policy-inducing models for tractable end-to-end optimization. 
conclusions: 
 This paper studies the bandit-feedback setting for contextual linear optimization for the first time. We adapt the induced empirical risk minimization approach to this setting, provide a 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 a 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. 
 
 Appendix: 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 z 1 , . . . , z m for m = 70. We can view them as separate discrete actions, and a feasible decision policy π is a mapping from the covariates X to one of the m = 70 feasible paths. We now adopt one-hot-encoding for the decisions. Consider a simplex Z simplex in R m and zero-one vector z ∈ {0, 1} m that takes the value 1 on one and only one of its coordinate. Each feasible decision in z 1 , . . . , z m corresponds to one vector z, e.g., the decision z j corresponds to the z vector whose j-th entry is 1 and other entries are all 0.Our decision-making problem restricted to the feasible decisions z 1 , . . . , z m can be written as follows:min z∈Z simplex m j=1 zj E[C | Z = z j , X = x] ⇐⇒ min z∈Z simplex z⊤ f0 (x), where f0 (x) = (E[C | Z = z 1 , X = x], . . . , E[C | Z = z m , X = x]) ⊤ .For any given x, the resulting decision will be an one-hot vector that corresponds to an optimal decision at x (which can be equivalently given by π f0 (x) for an plug-in policy in Eq. ( 2) at the truef 0 (x) = E[Y | X = x]).In this formulation, we view the decisions z 1 , . . . , z m as 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 f0 function. For offline 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 min z∈Z simplex z⊤ f0 (x). We finally inspect which coordinate of the resulting solution is equal to 1 and choose it as the decision.To adapt the IERM approach, we similarly define the plug-in policy for any given hypothesis f (x) : R p → R m for the function f0(x) = (E[C | Z = z 1 , X = x], . . . , E[C | Z = z m , X = x]) ⊤ : π f (x) ∈ arg min z∈Z simplex f (x) ⊤ z,where ties are again broken by some fixed rules. Given a function class F, we can then consider the induced policy class Π F = {π f : f ∈ F}. For any policy π ∈ Π F , its output is an one-hot vector, whose entry with value 1 corresponds to the chosen decision among z 1 , . . . , z m . For any observed decision Z ∈ {z 1 , . . . , z m }, we denote its one-hot transformation Z as the zero-one vector whose value-one entry corresponds to the value of Z. For a given observed total cost C, we denote C 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 x to an m-dimensional one-hot vector, its policy value can be written as follows:V (π) = E θ(X, Z, C; f0 , ẽ0 ) ⊤ π(X) , where f0 (x) = (E[C | Z = z 1 , X = x], . . . , E[C | Z = z m , X = x]) ⊤ ẽ0 (x) = (e 0 (z 1 | x, . . . , e 0 (z m | x))) ⊤ , e 0 (z | x) = P(Z = z j | X = x),and the score function θ can take three different forms:1. (Direct Method) θDM (x, z, c; f , ẽ) = f (x);B.1 Supporting Lemmas Lemma 2 (Talagrand's inequality, [4, 31, 37] ). Let U i , i = 1, . . . , n be independent U-valued random variables. Let H be a countable family of measurable real-valued functions on U such that ∥h∥ ∞ ≤ v andE[h(U 1 )] = • • • = E[h(U n )] = 0, for all h ∈ H. Define v n = 2vE sup h∈H n i=1 h(U i ) + n i=1 sup h∈H E h 2 (U i ) .Then, for all t ≥ 0,P sup h∈H n i=1 h(U i ) ≥ E sup h∈H n i=1 h(U i ) + t ≤ exp -t 2 2v n + 2tv/3 . Lemma 3. Fix functions f, Σ independent of {(X i , Z i , C i )} n i=1 such that ∥θ(x, z, c; f, Σ)∥ ≤ Θ for all x, z, c. Define the function class G = (x, z, c) → θ(x, z, c; f, Σ) ⊤ (π(x) -π * (x))ρ 2BΘ : π ∈ Π F , ρ ∈ [0, 1] .Let r be any solution to the inequality R n (G, r) ≤ r 2 satisfying 3nr 2 /64 ≥ log log 2 (1/r). Then we haveP sup g∈G |(E n -E P )g| ∥g∥ 2 + r ≥ 6r ≤ 2 exp - 3 64 nr 2 ,whereE n (g) = 1 n n i=1 g(X i , Z i , C i ).Proof of Lemma 3. When sup g∈G |(E n -E P )g|/(∥g∥ 2 + r) > 6r, one of the following two events must hold true:E 1 = |(E n -E P )g| ≥ 6r 2 for some g ∈ G such that ∥g∥ 2 ≤ r , E 2 = {|(E n -E P )g| ≥ 6∥g∥ 2 r for some g ∈ G such that ∥g∥ 2 ≥ r}. Define Z n (r) = sup g∈G,∥g∥ 2 ≤r|(E n -E P )g|.Note that ∥g∥ 2 ≤ r implies E[(g -E P (g)) 2 ] ≤ r 2 , and we also have ∥g -E P (g)∥ ∞ ≤ 2. By Talagrand's inequality (Lemma 2) over the function class {g -E P (g) : g ∈ G},P(Z n (r) ≥ E[Z n (r)] + t) ≤ exp - nt 2 8E[Z n (r)] + 2r 2 + 4t/3.We now bound the expectation E[Z n (r)]. Since G is star-shaped 3 , by [41, Lemma 13.6], r → R n (G, r)/r is non-increasing. Thus, for any r ≥ r,E[Z n (r)] ≤ 2R n (G, r) ≤ 2r r R n (G, r) ≤ 2rr,where the first inequality comes from a symmetrization argument, the second inequality uses the fact that r → R n (G, r)/r is non-increasing, and the third inequality is by definition of r.The Talagrand's then impliesEQUATION)We first bound P(E 1 ). Taking r = r and t = 4r 2 in Eq. ( 10), we getP(E 1 ) ≤P Z n (r) ≥ 6r 2 ≤ exp - 24 35 nr 2 .We now bound P(E 2 ). Note thatP(E 2 ) ≤ P(Z n (∥g∥ 2 ) ≥ 6∥g∥ 2 r for some g ∈ G, ∥g∥ 2 ≥ r).DefineG m = g ∈ G : 2 m-1 r ≤ ∥g∥ 2 ≤ 2 m r . Since ∥g∥ 2 ≤ 1, there exists M ≤ log 2 (1/r) such that G ∩ {g : ∥g∥ 2 ≥ r} ⊆ ∪ M m=1 G m . Therefore, P(E 2 ) ≤ M m=1 P(Z n (∥g∥ 2 ) ≥ 6∥g∥ 2 r for some g ∈ G m ).We now bound each term in the summation above. If there exists g ∈ G m such that Z n (∥g∥ 2 ) ≥ 6∥g∥ 2 r, then we haveZ n (2 m r) ≥ Z n (∥g∥ 2 ) ≥ 6∥g∥ 2 r ≥ 3 • 2 m r2 .Thus,P(Z n (∥g∥ 2 ) ≥ 6∥g∥ 2 r for some g ∈ G m ) ≤ P Z n (2 m r) ≥ 3 • 2 m r2 .Now, taking r = 2 m r and t = 2 m r2 in Eq. ( 10), we getP Z n (2 m r) ≥ 3 • 2 m r2 ≤ exp - 3nr 2 13 • 2 2-m + 6 ≤ exp - 3 32 nr 2 .Therefore, if 3 64 nr 2 ≥ log log 2 (1/r), thenP(E 2 ) ≤ M exp - 3 32 nr 2 ≤ exp - 3 64 nr 2 .Combining the bounds on P(E 1 ) and P(E 2 ) leads to the final conclusion.Lemma 4. Suppose Assumption 3 holds and P(|Z * (X)| > 1) = 0. Then there exists a constant C(α, γ) such that for any π ∈ Π F ,P(π(X) ̸ = π f0 (X)) ≤ C(α, γ) Reg(π) B α 1+α.Proof of Lemma 4. This follows directly from [14, Lemma 1] .Lemma 5. Let c 1 , c 2 , r be positive constants. For any α > 0, if a positive number x satisfiesx ≤ c 1 x α 2(1+α) r + c 2 ,we havex ≤ (c 1 r) 2α+2 α+2 + 2c 2 .Proof of Lemma 5. First, note that∂ ∂y y -c 1 y α 2(1+α) r -c 2 = 1 - c 1 rα 2(1 + α) y -2+α 2+2α .The derivative is strictly increasing in y and is eventually positive. Note the function yc 1 y α/(2+2α) r -c 2 takes a negative value at y = 0. Then as y increases, the value of y -c 1 y α/(2+2α) r -c 2 first decreases and then increases. Therefore, if y > 0 satisfies the inequality y -c 1 y α/(2+2α) r -c 2 ≥ 0, then such y also provides an upper bound on x. Hence it is sufficient to show that y = (c 1 r) 2α+2 α+2 + 2c 2 satisfies the inequality, or equivalently,EQUATION)Suppose α/(2 + 2α) is a rational number. In this case, we can write α/(2 + 2α) = m 1 /m 2 , where m 1 and m 2 are positive integers such that m 2 ≥ 2m 1 + 1. Eq. ( 11) is then equivalent toEQUATION)Using the multinomial theorem, we have(c 1 r) m 2 m 2 -m 1 + c 2 m2 -c m2 1 (c 1 r) m 2 m 2 -m 1 + 2c 2 m1 r m2 > m1 i=0 m 2 ! (i + m 2 -m 1 )!(m 1 -i)! - m 1 !2 m1-i (m 1 -i)!i! (c 1 r) im 2 m 2 -m 1 +m2 c m1-i 2 .Since m 2 ≥ 2m 1 + 1, we have for any i = 0, . . . , m 1 ,m 2 ! (i + m 2 -m 1 )!(m 1 -i)! ≥ m 1 !2 m1-i (m 1 -i)!i! .This can be proved by showing the ratio of LHS over RHS is larger than 1. Hence, Eq. ( 11) holds true when α/(2 + 2α) is a rational number.Finally, note that(c 1 r) 2α+2 α+2 + c 2 -c 1 (c 1 r) 2α+2 α+2 + 2c 2 α 2(1+α) ris continuous in α. Since any real number α can be viewed as the limit of a sequence of rational numbers and Eq. ( 11) holds for all rational numbers, it also holds true for all α > 0.Lemma 6. Let c 1 , c 2 , r, y, z be positive constants, and let α be a positive constant such that 2(1 + α)/α is an integer. If a positive number x satisfiesx ≤ c 1 x α 2(1+α) r + c 1 y α 2(1+α) r + c 2 r 2 + z + y, we have x ≤ c 2α+2 α+2 1 r 2α+2 α+2 + 2α + 2 α + 2 c 1 y α 2α+2 r + 2α + 2 α + 2 c 2 r 2 + 2α + 2 α + 2 z + y.Proof of Lemma 6. Let 2(α + 1)/α = m, where m is an integer by assumption. Using similar arguments as in the proof of Lemma 5, it is sufficient to show that for w = c2α+2 α+2 1 r 2α+2 α+2 + 2α+2 α+2 c 1 y α 2α+2 r + 2α+2 α+2 c 2 r 2 + 2α+2 α+2 z + y and c ′ 2 = c 1 y α 2(1+α) r + c 2 r 2 + z + y, we have w -c 1 w α 2(1+α) r -c ′ 2 ≥ 0. This is equivalent to showing c 2α+2 α+2 1 r 2α+2 α+2 + 2α + 2 α + 2 c 1 y α 2α+2 r + 2α + 2 α + 2 c 2 r 2 + 2α + 2 α + 2 z + y ≥c 1 c 2α+2 α+2 1 r 2α+2 α+2 + 2α + 2 α + 2 c 1 y α 2α+2 r + 2α + 2 α + 2 c 2 r 2 + 2α + 2 α + 2 z + y α 2(1+α) r + c 1 y α 2(1+α) r + c 2 r 2 + z + y. Since α = 2/(m -2), the above inequality is equivalent to c m m-1 1 r m m-1 + 1 m -1 c 1 y 1 m r + 1 m -1 c 2 r 2 + 1 m -1 z m ≥c m 1 r m c m m-1 1 r m m-1 + m m -1 c 1 y 1 m r + m m -1 c 2 r 2 + m m -1 z + y .Using the multinomial theorem, it is easy to see that the expansion of LHS contains all terms on the RHS (plus additional positive terms). This finishes proving our conclusion.Proof of Theorem 1. To simplify notation, we defineE nj θ(X, Z, C; f3-j , Σ3-j ) ⊤ (π(X) -π * (X)) = 2 n i∈Dj θ(X i , Z i , C i ; f3-j , Σ3-j ) ⊤ (π(X i ) -π * (X i )).We can decompose the regret asReg(π) =E P f 0 (X) ⊤ (π(X) -π f0 (X)) =E P θ(X, Z, C; f 0 , Σ 0 ) ⊤ (π(X) -π * (X)) + E f 0 (X) ⊤ (π * (X) -π f0 (X)) ≤ 1 2 2 j=1 E P θ(X, Z, C; f 0 , Σ 0 ) -θ(X, Z, C; fj , Σj ) ⊤ (π(X) -π * (X)) + 1 2 2 j=1 (E P -E nj ) θ(X, Z, C; f3-j , Σ3-j ) ⊤ (π(X) -π * (X)) + Reg(π * ),where the inequality follows from the definition of π.By Assumption 2, with probability at least 1 -δ/2, 1 22 j=1 E P θ(X, Z, C; f 0 , Σ 0 ) -θ(X, Z, C; fj , Σj ) ⊤ (π(X) -π * (X)) ≤ Rate N (n/2, δ/4).We now bound(E P -E n1 ) θ(X, Z, C; f2 , Σ2 ) ⊤ (π(X) -π * (X)). By Lemma 3 and the assumption that 2 exp -3nr 2 /128 ≤ δ/4, we have that with probability at least 1 -δ/4,EQUATION)Assuming Eq. ( 13) holds,EQUATION) For any π ∈ Π F , θ(X, Z, C; f2 , Σ2 ) ⊤ (π(X) -π f0 (X)) 2BΘ 2 2 =E   θ(X, Z, C; f2 , Σ2 ) ⊤ (π(X) -π f0 (X)) 2BΘ 2 I{π(X) ̸ = π f0 (X)}   ≤P(π(X) ̸ = π f0 (X)) ≤ C(α, γ) Reg(π) B α 1+α, where the last inequality follows from Lemma 4.Applying the inequality above for both π and π f0 and plug the bounds into Eq. ( 14), we get(E P -E n1 ) θ(X, Z, C; f2 , Σ2 ) ⊤ (π(X) -π * (X)) ≤12BΘ C(α, γ) Reg(π) B α 2(1+α) r + C(α, γ) Reg(π * ) B α 2(1+α) r + r2 .We can similarly bound(E P -E n2 ) θ(X, Z, C; f1 , Σ1 ) ⊤ (π(X) -π * (X)) .Combining all pieces together, we get that with probability at least 1 -δ,Reg(π) B ≤12Θ C(α, γ) Reg(π) B α 2(1+α) r + C(α, γ) Reg(π * ) B α 2(1+α) r + r2 + Rate N (n/2, δ/4) B + Reg(π * ) B .Solving the above inequality with respect to Reg(π)/B using Lemma 5, we haveReg(π) ≤B 12Θ C(α, γ)r 2α+2 α+2 + 24BΘ C(α, γ) Reg(π * ) B α 2(1+α) r + r2 + 2Rate N (n/2, δ/4) + 2Reg(π * ).Proof of Proposition 1. For direct method, the conclusion is obvious.For ISW, we have for any Σ,E Σ + (X)ZC ⊤ π(X) -E f 0 (X) ⊤ π(X) = E f 0 (X) ⊤ (I -Σ + (X)Σ 0 (X)) ⊤ π(X) .Let M (x) be a matrix whose columns include all basis vectors of the span of Z. Then π(X) ∈ Range(M (x)). According to the coverage assumption, the column space of Σ 0 (x) is identical to the column space of M (x). By the property of pseudo-inverse, the column space of (I -Σ † 0 Σ 0 ) is orthogonal to the column space of M . Therefore, (I -Σ + (X)Σ 0 (X)) ⊤ π(X) = 0 for any π ∈ Z.For doubly robust score, we have that for any function f, Σ,E π(X) ⊤ f (X) + Σ(X) + Z(C -Z ⊤ f (X)) -E[π(X) ⊤ f 0 (X)] =E π(X) ⊤ (I -Σ + (X)Σ 0 (X))(f (X) -f 0 (X)) .Taking either f = f 0 or Σ = Σ 0 gives 0.Proof of Proposition 2. Because π(x) -π * ∈ span(Z), for the DM score we haveE P θ DM (X, Z, C; f 0 , Σ 0 ) -θ DM (X, Z, C; f , Σ) ⊤ (π(X) -π * (X)) ≤E P Proj span(Z) θ DM (X, Z, C; f 0 , Σ 0 ) -θ DM (X, Z, C; f , Σ) ⊤ (π(X) -π * (X)) ≤2B E X [∥Proj span(Z) ( f (X) -f 0 (X))∥ 2 ] 1/2 = O(χ n,δ ).For the ISW score, we haveE P θ ISW (X, Z, C; f 0 , Σ 0 ) -θ ISW (X, Z, C; f , Σ) ⊤ (π(X) -π * (X)) ≤2B E X [∥( Σ † (X) -Σ † 0 (X))Σ 0 (X)∥ 2 Fro ] 1/2 = O(χ n,δ ).For the doubly robust score, we can easily getE P θ DR (X, Z, C; f 0 , Σ 0 ) -θ DR (X, Z, C; f , Σ) ⊤ (π(X) -π * (X)) =E P (π(X) -π * (X)) ⊤ I -Σ+ (X)Σ 0 (X) ( f (X) -f 0 (X)) =E P (π(X) -π * (X)) ⊤ Σ + 0 (X) -Σ+ (X) Σ 0 (X)( f (X) -f 0 (X)) =E P (π(X) -π * (X)) ⊤ Σ + 0 (X) -Σ+ (X) Σ 0 (X) Proj Span(Z) ( f (X) -f 0 (X)) ≲ E X [∥( Σ † (X) -Σ † 0 (X))Σ 0 (X)∥ 2 Fro ] 1/2 E X [∥Proj span(Z) ( f (X) -f 0 (X))∥ 2 ] 1/2 = O(χ 2 n,δ ).Here the second equation holds because π(x) -π * (x) belongs to the linear span of Z, but I -Σ + 0 (x)Σ 0 is orthogonal to the linear span of Z, as we already argued in the proof of Proposition 1. The third equation holds because the column space of Σ 0 (X) is identical to span(Z) according to the coverage assumption.Proof of Proposition 3. DefineΨ(t) = 1 5 exp(t 2 ).Note that whenever EΨ(|W |/w) ≤ 1 for some random variable W , we have by Markov's inequality thatEQUATIONThroughout the proof, we condition on the event that G 1 has VC-subgraph dimension η. We finish the proof in three steps.Step I: Critical radius for empirical Rademacher complexity. Define the localized empirical Rademacher complexityRn (G 1 , r) = E ϵ sup g∈G,∥g∥ n ≤r 1 n n i=1 ϵ i g(X i , Z i , C i ) ,where ϵ 1 , . . . , ϵ n are i.i.d. Rademacher random variables, and∥g∥ n = n i=1 g 2 (X i , Z i , C i )/n. Let r * n be the smallest positive solution to Rn (G 1 , r) ≤ r 2 /32.In what follows, we show that there exists a universal constant C such thatEQUATIONFor any g ∈ G 1 , define setG = {(g(X 1 , Z 1 , C 1 ), . . . , g(X n , Z n , C n )) : g ∈ G 1 , ∥g∥ n ≤ r}.Let D(t, G) be the t-packing number of G and N (t, G) be the t-covering number. Note that ∥g∥ ≤ √ nr for all g ∈ G. By [28, Theorem 3.5],E ϵ Ψ 1 J sup g∈G1,∥g∥ n ≤r n i=1 ϵ i g(X i , Z i , C i ) ≤ 1,whereJ = 9 √ nr 0 log D(t, G)dt.So by Eq. ( 15),Rn (G 1 , r) ≤ 5 n J.Consider the function class Therefore, for any samplesG ′ 1 = {g : g ∈ G 1 , ∥g∥ n ≤ r}. Note that √ nr is the envelope of G ′ 1 on (X 1 , Z 1 , C 1 ), . . . , (X n , Z n , C n ). Applying [40, Theorem 2.6.7] gives D( √ nrt, G) ≤ N ( √ nrt/2, G) ≤ C(η + 1)(16e) η+1 4n t 2 η a universal constant C. Thus, J =9 √ nr 1 0 log D( √ nrt, G)dt(X i , Z i , C i ) n i=1, any rn ≥ C η log(n + 1)/n is a valid solution to Rn (G 1 , r) ≤ r 2 /32, which implies Eq. ( 16).Step II: Critical radius for Rademacher complexity. Let r * n be the smallest positive solution to the inequality R n (G 1 , r) ≤ r 2 /32. We now bound r * n . For any t > 0, define the random variableW n (t) = E ϵ sup g∈G1,∥g∥ 2 ≤t 1 n n i=1 ϵ i g(X i , Z i , C i ) , so that R n (G 1 , r) = E P [W n (r)] by construction. Define the eventsE 3 (t) = |W n (t) -R n (G 1 , t)| ≤ r * n t 112 , E 4 =    sup g∈G1 ∥g∥ 2 n -∥g∥ 2 2 ∥g∥ 2 2 + (r * n ) 2 ≤ 1 2    .Following the proof of [14, Lemma EC.12],P r * n 5 ≤ r * n ≤ 3r * n ≥ P(2E 3 (r * n ) ∩ E 3 (7r * n ) ∩ E 4 ).[14, Lemma EC.10] implies thatP(E c 4 ) ≤ 2e -c1n(r * n ) 2for some universal constant c1 > 0. Moreover, for anyζ ≥ 1, we have R n (G 1 , ζr * n ) ≥ R n (r * n ) ≥ (r * n ) 2 /32. By [3, Theorem 16] ,P(E c 3 (ζr * n )) ≤ 2e -c2n(r * n ) 2for some universal constant c2 > 0. Combining all pieces we haveEQUATION)By step I in the proof, P r * n ≤ C0 η log(n + 1)/n = 1 for some constant C0 . Let C > 5 C0 be a constant such that 2 -C(c1∧c2) < 1/6. If r * n > C η log(n + 1)/n, by Eq. ( 17) we have P r * n > C0 η log(n + 1)/n > 0, which leads to contradiction. Thus,r * n ≤ C η log(n + 1)/n.Finally, any r ≥ C η log(n + 1)/n solves the inequality R n (G 1 , r) ≤ r 2 .Step III: Checking other conditions. The other two inequalities, 3nr 2 /64 ≥ log log 2 (1/r) and 2 exp -3nr 2 /64 ≤ δ/2, are easily satisfied as long as we take C big enough.Proof of Theorem 1. To simplify notation, we writeE n Y ⊤ πF (X) -π * (X) = 1 n n i=1 Y ⊤ i πF (X i ) -π * (X i ) .We can decompose the regret asReg πF =E P Y ⊤ πF (X) -π f0 (X) =E P Y ⊤ πF (X) -π * (X) + E Y ⊤ (π * (X) -π f0 (X)) ≤(E P -E n ) Y ⊤ πF (X) -π * (X) + Reg(π * ),where the inequality follows from the definition of πF .We now bound(E P -E n ) Y ⊤ πF (X) -π * (X). Following a similar proof as in the proof of Lemma 3, we have that with probability at least 1 -δ,EQUATION)Assuming Eq. ( 18) holds,(E P -E n ) Y ⊤ πF (X) -π * (X) ≤12B Y ⊤ πF (X) -π * (X) 2B 2 rF + (r F ) 2 ≤12B Y ⊤ πF (X) -π f0 (X) 2B 2 rF + Y ⊤ (π f0 (X) -π * (X)) 2B 2 rF + (r F ) 2 .For anyπ ∈ Π F , Y ⊤ (π(X) -π f0 (X)) 2B 2 2 =E Y ⊤ (π(X) -π f0 (X)) 2B 2 I{π(X) ̸ = π f0 (X)} ≤P(π(X) ̸ = π f0 (X)) ≤ C(α, γ) Reg(π) B α 1+α, where the last inequality follows from Lemma 4. Thus,(E P -E n ) Y ⊤ πF (X) -π * (X) ≤12B C(α, γ) Reg(π F ) B α 2(1+α) rF + C(α, γ) Reg(π * ) B α 2(1+α) rF + (r F ) 2 .Combining all pieces together, we get that with probability at least 1 -δ,Reg(π F ) B ≤12 C(α, γ) Reg(π F ) B α 2(1+α) rF + C(α, γ) Reg(π * ) B α 2(1+α) rF + (r F ) 2 + Reg(π * ) B .Solving the above inequality with respect to Reg(π F )/B using Lemma 5, we haveReg(π F ) ≤ B 12 C(α, γ)r F 2α+2 α+2 + 24B C(α, γ) Reg(π * ) B α 2(1+α) rF + (r F ) 2 + 2Reg(π * ).In Section 5, 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 a 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 F N and each logging policy takes around 2 days of running time based on parallel computing on 100 CPUs.Data generating process. We first generate i.i.d draws of the covariates X = (X 1 , X 2 , X 3 ) ⊤ ∈ R 3 from independent standard normal distribution. Then we simulate the full feedback Y according to the equation Y = f 0 (X) + ϵ, where f 0 (X) = 3 + W * 1 X 1 + W * 2 X 2 + W * 3 X 3 + W * 4 X 1 X 2 + W * 5 X 2 X 3 +W * 6 X 1 X 3 +W * 7 X 1 X 2 X 3 for coefficient vectors W * 1 , . . . , W * 7 ∈ R dand a random noise ϵ drawn from the Unif[-0.5, 0.5]. To fix the coefficient vectors W * 1 , . . . , W * 7 , we draw their entries independently the from the Unif[0, 1] 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 {z 1 , . . . , z m } for m = 70, according to different logging policies that will be described shortly. Then the total cost C = Y ⊤ Z is recorded in the observed data.We consider three different logging policies. One is a random logging policy that uniformly samples each decision from the feasible decisions, regardless of the covariate value. The other two are covariate-dependent logging policies. For these two policies, we first remove 20 feasible decisions that correspond to the optimal decisions for some covariate observations in 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 to demonstrate the value of leveraging the linear structure of the decision-making problem, since exploiting the linear structure allows to extrapolate the feedback from the logged decisions to 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 X 1 . When X 1 > 0, the logging policy chooses the first group with probability 2/3 and the second group with probability 1/3. When X 1 ≤ 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 as the X 1 -policy.• The other covariate-dependent policy samples the decisions according to the signs of both X 1 and X 2 . When X 1 > 0 and X 2 > 0, the logging policy chooses the two groups with probabilities 2/3 and 1/3 respectively. When X 1 > 0 and X 2 ≤ 0, the logging policy chooses the two groups with probabilities 1/3 and 2/3 respectively. When X 1 ≤ 0 and X 2 > 0, the policy chooses the two groups with probabilities 3/4 and 1/4 respectively. When X 1 ≤ 0 and X 2 ≤ 0, 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 X 1 X 2 -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{(x 1 , x 3 , x 3 ) → W 0 + W 1 x 1 + W 2 x 2 + W 3 x 3 + W 4 x 1 x 2 + W 5 x 2 x 3 + W 6 x 1 x 3 + W 7 x 1 x 2 x 3 : W 0 , . . . , W 7 ∈ R}. The second model class {(x 1 , x 3 , x 3 ) → W 0 + W 1 x 1 + W 2 x 2 + W 3 x 3 + W 4 x 1 x 2 + W 5 x 2x 3 : W 0 , . . . , W 5 ∈ R} omits two interaction terms and is thus misspecified (which we refer to as degree-2 misspecification). The third model classEQUATION∈ 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 f0 (x) = E[Y | X = x].We estimate this by the least squares regression in Eq. ( 7), with the F N class being one of the three classes described above (i.e., correct specification, degree-2 misspecification, degree-4 misspecification). We incorporate an additional ridge penalty with a coefficient 1. We estimate the the nuisance Σ 0 (x) using the propensity score approach described in Remark 2, so we need to estimate the propensity scores P(Z = z j | X = x) for j = 1, . . . , m.For the random logging policy, we simply estimate P(Z = z j | X = x) for any x by the empirical frequency of the decision z j in the observed data. For the X 1 -policy and X 1 X 2 -policy, we estimate the propensity scores by classification decision trees of depth 3 trained to classify each instance to one of the observed classes among z 1 , . . . , z m . These nuisances are all estimated using the two-fold cross-fitting described in Section 1.2.Since the Σ 0 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 eigen-decomposition of Σ 0 , set all eigenvalues below 1 to 1, and then take a pseudoinverse of the transformed matrix. These two lead to the SPO+ DR Lambda and SPO+ DR Clip methods in Section 5 and this section.Naive Benchmarks. We also implemented the benchmarks in Appendix A. For ETO, SPO+ DM, and SPO+ DR, we estimate f0 (x) 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 f0 is m-dimensional while the output of f 0 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 f0 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.SPO+ Tuning and Optimization. We need to solve the SPO+ optimization problem in Section 4 for the DM and DR scores. Following [11] , we incorporate an additional ridge penalty on the coefficients of the hypotheses. We select the penalty coefficient from a grid of 0, 0.001, 0.01 and 10 points distributed uniformly on the logarithmic scale over 0.1 to 100. This is done by minimizing the out-of-sample error on an independent validation dataset with size equal to the corresponding training data. The penalty coefficient is finally set as the half of the value chosen by this validation procedure.To optimize the SPO+ loss, [11] recommend applying standard convex optimization solvers to a 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 [11, 14] (number of iterations, step size, batch size) runs much faster, while performing similarly to the dual reformulation method.In this section, we provide some additional experimental results. Specifically, Tables 3 and 4 are extensions of Tables 1 and 2 for the random logging policy. In particular, Table 3 shows additional results on ISW and IPW methods. They are generally worse than other alternative methods. Table 4 additionally show results for the naive benchmarks under model misspecification, and further confirm their worse performance. Tables 5 to 8 provide results for two covariate-dependent logging policies, the X 1 -policy and X 1 X 2 -policy 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. 8 : Mean relative regret ratio of different methods when the nuisance model F N and the policyinducing model F are misspecified to differrent degrees. The logging policy is a X 1 X 2 -policy.If we take θ = θ DR , we have Rate N DR (n, δ) = O(χ 2 n,δ ).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(χ 2 n,δ ) instead of O(χ n,δ ). This echos the benefit of DR methodsThe code scripts for all experiments can be found at https://github.com/CausalML/CLOBandit.A function class G is star-shaped if for any g ∈ G and ρ ∈ [0, 1], we have ρg ∈ G. 


Decision: 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.

Reviews: review: paper_summary: paper_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.

One 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.

The 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.

There is substantial empirical evaluation.
strength_weakness: strength_weakness: 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. 

Perhaps it would help if the paper were structured in a more traditional way with definitions and algorithms rather than the free-flowing narrative.

Page 3, line 125: I am not sure I parse

which we call as nuisance functions as they will be used to

correctly. Did you mean

which we call nuisance functions because they will be used to

?

(I should say I do not understand the choice of the word "nuisance". The pun is lost on me.)
questions: questions: None.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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:
- In line 108, "is" should be corrected.
- There is no definition of $\chi^2_{n,\delta}$.
- In line 74, "in that that" should be corrected.
questions: 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: limitations: It is not well explained why the suggested algorithm has improved performance as compared to the existing algorithms.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: N/A
limitations: limitations: Limitations are adequately discussed in the paper.

Comments: comment: I thank the authors for their detailed response.
Thank you for the detailed response. It helps my understanding.

Special thanks for explaining "nuisance". This needs to be incorporated in the paper as the meaning seems to be remote from that in everyday English.
Thank you for your response. I appreciate the contributions your paper makes and I am willing to support this paper. However, to maintain consistency and fairness, I have decided to keep my current score. This score is based on a balanced comparison with other papers in my review batch.
Dear Reviewer h4hQ. Thank you for reading our rebuttal. As you write that it has addressed all your concerns, we would greatly appreciate if you would raise your rating and confidence scores accordingly. Thank you. And do let us know if you have further questions -- we would do our best to answer them promptly.
Thanks for your responses and my concerns have been addressed.