From Predictive to Prescriptive Analytics

Dimitris Bertsimas; Nathan Kallus

Source-linked AI summary

From Predictive to Prescriptive Analytics

Dimitris Bertsimas, Nathan Kallus

arXiv:1402.5481v4Feb 22, 2014stat.MLcs.LGmath.OC

TL;DR

The paper asks how auxiliary data can support optimal OR/MS decisions when uncertainty is imperfectly observed and distributions are unknown. It combines ML-inspired predictive prescriptions with stochastic optimization and extends the framework to censored and decision-dependent data. In an inventory application, the collected data accounted for an 88% improvement toward the deterministic perfect-foresight counterpart.

Problem
The paper addresses how to make optimal OR/MS decisions from auxiliary observations when uncertainty is imperfectly observed and the underlying distributions are unknown.
Method
The paper combines ML-inspired predictive prescriptions with OR/MS optimization, including constructions based on local learning, trees, random forests, and empirical risk minimization.
Results
88% improvement toward the deterministic perfect-foresight counterpart was achieved in the inventory application.
Takeaways & Limitations
The framework uses auxiliary data to prescribe operational decisions and can retain favorable asymptotic properties for censored and decision-dependent uncertainty under certain conditions.
Takeaways & Limitations
The empirical-risk-minimization construction has limitations in the specific context of OR/MS problems that do not affect the predictive prescriptions derived from the alternative construction.

Abstract

from arXiv · show

In this paper, we combine ideas from machine learning (ML) and operations research and management science (OR/MS) in developing a framework, along with specific methods, for using data to prescribe optimal decisions in OR/MS problems. In a departure from other work on data-driven optimization and reflecting our practical experience with the data available in applications of OR/MS, we consider data consisting, not only of observations of quantities with direct effect on costs/revenues, such as demand or returns, but predominantly of observations of associated auxiliary quantities. The main problem of interest is a conditional stochastic optimization problem, given imperfect observations, where the joint probability distributions that specify the problem are unknown. We demonstrate that our proposed solution methods, which are inspired by ML methods such as local regression, CART, and random forests, are generally applicable to a wide range of decision problems. We prove that they are tractable and asymptotically optimal even when data is not iid and may be censored. We extend this to the case where decision variables may directly affect uncertainty in unknown ways, such as pricing's effect on demand. As an analogue to R^2, we develop a metric P termed the coefficient of prescriptiveness to measure the prescriptive content of data and the efficacy of a policy from an operations perspective. To demonstrate the power of our approach in a real-world setting we study an inventory management problem faced by the distribution arm of an international media conglomerate, which ships an average of 1bil units per year. We leverage internal data and public online data harvested from IMDb, Rotten Tomatoes, and Google to prescribe operational decisions that outperform baseline measures. Specifically, the data we collect, leveraged by our methods, accounts for an 88\% improvement as measured by our P.

1. Introduction

The paper combines machine learning and OR/MS to prescribe decisions from auxiliary data under uncertainty, addressing the gap between prediction and optimal decision-making. Its methods are tractable, asymptotically optimal under broad sampling conditions, and effective in an inventory application.

Motivation: OR/MS decision-making must account for uncertainty, while traditional ML prediction does not directly address optimal decisions under uncertainty.Using only the sample mean can produce inadequate solutions and waste auxiliary observations.
Framework: The framework uses auxiliary observations to construct predictive prescriptions for conditional stochastic optimization when the underlying distributions are unknown.The target prescription uses observed covariates to select decisions while minimizing expected costs.
Methods: The proposed constructions draw on local-learning methods, regression trees, random forests, and empirical risk minimization for multivariate OR/MS decisions.The paper extends out-of-sample guarantees for empirical risk minimization to multivariate-valued decision rules.
Theory: Under mild conditions, selected prescriptions are computationally tractable and converge to the full-information optimum under sampling assumptions more general than iid.The results also cover censored data and convergence of prescription optimizers.
Decision-dependent uncertainty: The framework extends to decisions that affect uncertainty in unknown ways, including pricing decisions whose causal effect on demand is not directly observed.Historical data contain outcomes corresponding only to past decisions, but the paper establishes favorable asymptotic properties under certain conditions.
Evaluation: The coefficient of prescriptiveness P measures the efficacy of a prescription and the prescriptive content of covariates on a scale from 0 to 1.In experiments, the proposed prescriptions eventually outperform SAA and other data-driven approaches, while random-forest prescriptions are no worse than SAA for small samples.
Application: In the inventory application, combining internal and auxiliary data produced an 88% improvement toward the deterministic perfect-foresight counterpart.The approach achieved large improvements over baseline measures in the distribution operation studied.

2. From Data to Predictive Prescriptions

The paper formulates predictive prescriptions as data-driven decisions that minimize locally reweighted expected costs when the joint distribution of covariates and outcomes is unknown. It develops local-learning constructions based on kNN, kernels, local linear regression, CART, and random forests.

Motivation: The unknown joint distribution makes direct conditional-cost optimization difficult, especially when an observed covariate value is absent or has only one observed outcome.The empirical distribution can be undefined at unobserved x or degenerate at observed x, so the data must be generalized to estimate conditional expected costs.
Framework: Predictive prescriptions assign data-driven weights to observations and optimize the decision against the resulting reweighted costs.The common construction defines weights w_N,i(x) and solves the corresponding weighted optimization problem.
Local methods: kNN and kernel methods construct local prescriptions by emphasizing observations near the queried covariate x.kNN uses neighboring observations, while kernel methods use bandwidth- and kernel-based weights, including naïve, Epanechnikov, and tri-cubic kernels.
Local methods: Local linear regression extends local weighting by estimating conditional costs with a locally linear function rather than a local constant.The paper also proposes a nonnegative modification of local-linear weights to preserve nonnegativity without sacrificing asymptotic optimality.
Tree methods: CART produces piecewise-constant prescriptions that can be compiled into an interpretable decision tree after solving one optimization problem per partition.Random forests extend the construction by extracting partition rules from an ensemble of randomized trees.
Tree methods: Random-forest prescriptions use tree partitions to form weights and performed well across two problems, sample sizes, and covariate dimensions.The authors consequently select random forests for their real-world application.

3. From Data to Predictive Prescriptions When Decisions A↵ect Uncertainty

When decisions affect uncertainty, observed outcomes reveal only the outcome under the chosen decision, leaving counterfactual outcomes unavailable. The paper uses ignorability and decision decomposition to adapt predictive prescriptions to this setting, with asymptotic and empirical support.

Problem formulation: When a decision affects uncertainty, each observation reveals only the outcome under its chosen decision, not the counterfactual outcomes under alternatives.This creates missing potential outcomes in historical data.
Decision decomposition: The paper decomposes decisions into components with unknown effects on uncertainty and components whose effects are known through the cost function.Pricing can be the unknown-effect component, while production and shipment decisions can affect costs without affecting demand.
Problem formulation: Pricing illustrates the challenge because increasing a price changes demand, so the decision’s causal effect on uncertainty must be modeled.The relevant distributions are those of (X,Y(z)) for each possible decision z.
Identification: Under ignorability, conditioning on X makes the potential outcome Y(z) independent of the historical decision Z, identifying the decision-dependent problem from observed data.The assumption requires X to account for features associated with potential outcomes that influenced managerial decisions.
Identification: Theorem 1 transforms the decision-dependent problem into a conditional stochastic optimization problem based only on the observed distribution of (X,Y,Z).This removes the need to model unknown counterfactual distributions directly.
Methods: The adapted local-learning methods augment each covariate vector with the unknown-effect decision component before constructing weights and optimizing the prescription.This extends the Section 2 methods to decisions that affect uncertainty.
Empirical results: In the pricing experiment, local-learning methods approach the full-information optimum with more data, whereas SAA and point prediction do not converge to it.The random-forest prescription addressing pricing’s unknown effect performs best overall.

4. Properties of Local Predictive Prescriptions

The paper establishes computational tractability and asymptotic optimality for local predictive prescriptions under explicit optimization and data-regularity conditions. When decisions affect uncertainty, tractability can worsen with the dimension of the unknown-effect component.

Computational tractability: With nonnegative weights, predictive-prescription optimization has computational complexity similar to sample average approximation.The paper develops sufficient conditions for polynomial-time solution using separation and evaluation oracles.
Computational tractability: For decisions affecting uncertainty, discrete unknown-effect components permit separate optimization over each value while retaining convex optimization in the remaining component.Theorem 3 gives the corresponding tractability conditions.
Computational tractability: For continuous unknown-effect components, discretization yields runtime polynomial in problem parameters but exponential in their dimension and in log(1/ε).Theorem 4 requires boundedness, Lipschitz continuity in the unknown-effect component, and convexity in the remaining decision component.
Computational tractability: The discretization approach is practical mainly for small unknown-effect dimension, as illustrated by the pricing example with d_z1 = 1.The paper explicitly notes the computational burden from exponential dependence and super-logarithmic dependence on 1/ε.
Computational tractability: For CART weights, the decision-dependent optimization can be discretized exactly and solved efficiently by traversing relevant tree partitions.The resulting procedure solves the problem exactly for CART weights.
Asymptotic properties: The asymptotic results require existence, continuity, and regularity conditions on the cost function and feasible decision set.The main text presents the iid case, while extensions to mixing processes are deferred to the supplement.
Asymptotic properties: Under the stated conditions, kNN, kernel, recursive-kernel, and adapted local methods yield asymptotically optimal prescriptions, with kernel methods also shown consistent.The results concern almost-everywhere covariate values as sample size increases.

5. Metrics of Prescriptiveness

The coefficient of prescriptiveness P is a relative, unitless measure of how effectively data and a predictive prescription reduce costs between data-poor and perfect-foresight decisions. Its interpretation depends on the problem, with values approaching 0 when covariates are uninformative and 1 when they determine outcomes; in the application example, P approaches 0.46 and reaches 0.88 in the real-world setting.

P is a relative, unitless measure of predictive-prescription efficacy and the prescriptive content of covariates X.It is intended as an operations-oriented analogue to R^2.
P combines estimated costs for a predictive prescription, perfect-foresight decisions, and a data-poor SAA prescription.The three quantities position the data-driven policy between full uncertainty and deterministic perfect foresight.
P is bounded above by 1: values near 0 indicate little useful information or ineffective use of X, whereas high values indicate effective cost reduction.The metric evaluates both the information in X and the prescription’s ability to leverage it.
When X and Y are independent, P approaches 0 as sample size grows; when Y is measurable from X, P approaches 1 under appropriate conditions.The latter case also supports a point-prediction-driven decision reaching P = 1 in the stated extreme.
0.46 is the out-of-sample P reached by methods converging to the full-information optimum in the Section 1.1 example.This value represents the potential for X to reduce costs in that particular problem, not a universal success threshold.
0.88 is the out-of-sample P found in the paper’s real-world application.The authors note that the magnitude denoting success depends on context, as with R^2.

6. A Real-World Application

The paper applies its predictive-prescription framework to inventory decisions for a large media distributor, using auxiliary data and censored-sales corrections. The resulting policy substantially improves sales-oriented performance over data-poor and baseline policies.

The vendor manages over 0.5 million entertainment media titles across 50,000 retailers and ships 1 billion units annually.
Limited shelf capacity makes overstocking costly because it displaces potential sales of other products.
New-release demand is especially difficult to predict, despite offering the greatest opportunity for high demand and sales.
Because observed sales are censored by inventory, the authors develop a conditional Kaplan–Meier transformation that preserves asymptotic optimality and consistency under stated conditions.
IMDb and Rotten Tomatoes attributes provide useful demand signals: voting volume is more indicative of first-week sales than aggregate title quality.
P = 0.88 across just under 20,000 locations, placing the policy 88% of the way from the best data-poor decision to perfect foresight.
The proposed policy generally outperforms point-prediction and SAA++ policies, although it does not win on every day or location.

7. Concluding Remarks

The paper combines ML and OR/MS to prescribe decisions from auxiliary data while emphasizing operational costs, revenues, and risk. It reports tractable, asymptotically optimal methods with measurable real-world improvements and potential practical impact.

The framework uses auxiliary observations to prescribe optimal decisions in OR/MS problems.
Its ML-inspired methods focus on decisions and their effects on costs, revenues, and risk rather than prediction alone.
The approach is generally applicable, tractable, and asymptotically optimal, and produces measurable improvements in a real-world setting.
The authors identify growing auxiliary-data availability as a basis for potential impact in OR/MS practice.

8. Alternative Approaches using Empirical Risk Minimization

This section develops an empirical-risk-minimization approach for predictive prescriptions with general costs and multivariate decisions. It establishes computational and out-of-sample guarantees, while identifying limitations involving decision-rule structure and constrained feasible sets.

The empirical-risk formulation extends predictive prescriptions to multivariate uncertainty and decisions with general cost functions.
The framework generalizes Rademacher complexity to multivariate-valued decision rules to derive out-of-sample guarantees.
Unlike the paper’s predictive prescriptions, this approach lacks universal asymptotic-optimality guarantees and instead depends on the chosen decision-rule class.
Applying the formulation to constrained feasible sets can be difficult because feasibility outside the dataset is not guaranteed and projection may be intractable.
Under convexity and oracle-access conditions, an ε-optimal solution can be found in polynomial time.
The resulting empirical-risk objective bounds true out-of-sample costs with additional confidence terms.

9. Extensions of Asymptotic Optimality to Mixing Processes and Proofs

The paper extends asymptotic-optimality results beyond iid data to stationary mixing processes. Under stated regularity and mixing conditions, kernel, nearest-neighbor, and local-linear prescriptions remain asymptotically optimal and consistent.

The supplemental results extend the paper’s asymptotic analysis to mixing processes, encompassing iid data as a special case.
Mixing processes model evolving, dependent observations while allowing dependence to weaken across time.
The corresponding theorem for kNN methods also establishes asymptotic optimality and consistency under iid or mixing data conditions.
Recursive kernel methods are asymptotically optimal and consistent under the stated assumptions and suitable mixing conditions.
Local linear and nonnegative local linear methods retain asymptotic optimality and consistency under density, smoothness, bounded-cost, and mixing assumptions.
The proofs establish convergence of estimated conditional distributions and costs, yielding convergence toward optimal decisions.

10. Extensions of Out-of-Sample Guarantees to Mixing Processes and Proofs

The paper extends out-of-sample guarantees from iid data to data generated by mixing processes. The extension combines prior iid and mixing results and applies the resulting theorem to the paper’s earlier guarantee.

The results of Section 8.2 are extended to mixing processes by combining and restating earlier iid and mixing results.
For iid sampling, the theorem sets δ0 = δ00 = δ and ν = N.
For β-mixing data, the theorem uses a block parameter t, ν satisfying 2tν = N, and adjusted δ0 and δ00 terms involving β(t).
Replacing the mixing-process result in the proof of Theorem 13 extends that theorem to data generated by a mixing process.

11. Proofs of Tractability Results

The tractability proofs reduce the paper’s optimization problems to weak optimization and separation procedures. They use evaluation, subgradient, and weak separation oracles to establish solvability for the relevant formulations.

The proof of Theorem 2 rewrites the optimization problem using the weights wN,i(x) over indices with positive weight.
The tractability argument formulates optimization over z and θ subject to z ∈ Z and θi ≥ c(z;yi) for every relevant observation.
Weak optimization over the closed convex feasible body is reduced to weak separation via the ellipsoid algorithm, assuming a weak separation oracle for Z.
A violated cost constraint is handled with an evaluation oracle and a subgradient oracle that produces a separating cut.
The proof of Theorem 3 solves the problem for each covered candidate point and takes the minimum, using an argument analogous to Theorem 2.

12. Proof of Theorem 1

The supplied proof passage begins by stating that, under Assumptions 1 and 2, the objective in problem (19) can be rewritten. The excerpt also notes that the displayed relation follows by definition of Y.

Under Assumptions 1 and 2, the objective of problem (19) can be rewritten.
The supplied proof excerpt provides no further stated derivation beyond this objective rewrite and definition-based relation.
The accompanying relation is identified as following by definition of Y.

13. Omitted Details from Sections 1.1 and 3.2

The omitted details specify the shipment-planning simulation, its network and demand assumptions, and experiments varying feature dimension and predictiveness. Results show that predictive prescriptions can improve with additional useful dimensions while several methods deteriorate under dimensionality.

13.1. Shipment Planning Example: The shipment-planning instance stocks dz = 4 warehouses to serve dy = 12 locations arranged on a two-dimensional unit-circle network.
13.1. Shipment Planning Example: Shipping costs are cij = $10Dij, while production costs are $5 per unit in advance and $100 per unit when done last.
13.1. Shipment Planning Example: The experiment observes dx = 3 demand-predictive features evolving as a three-dimensional ARMA(2,2) process, with demands generated by a factor model.
13.2. Effect of Additional Dimensions with Diminishing Predictiveness: Additional dimensions are created by noisy copies of the original variables, with each copy more noisy than the previous one while improving their identification.
13.2. Effect of Additional Dimensions with Diminishing Predictiveness: The point-prediction-driven decision and CART- and RF-based predictive prescriptions improve slowly as dimension grows, whereas KR, Rec.-KR, LOESS*, and kNN deteriorate with dimension.
13.2. Effect of Additional Dimensions with Diminishing Predictiveness: The deterioration of KR, Rec.-KR, LOESS*, and kNN reflects the curse of dimensionality and their inability to learn which features matter more.
13.3. Shipment Planning with Pricing Example: The pricing extension keeps the shipment-planning parameters, simulates historical prices log-normally, and varies the dependence between X and Y using κ.

14. Constructing Auxiliary Data Features from IMDb and RT data

The paper distills IMDb and Rotten Tomatoes information into auxiliary features, including genre, ratings, plot similarity, and actor-community representations. These features capture title characteristics, shared themes, and actor-group structure.

Plot text is converted into cosine-similarity measures and hierarchically clustered with Ward’s method to capture common themes.
The authors construct 12 historical plot clusters and represent new titles by median cosine similarity to each cluster.
Titles are linked when they share actors, with edge weights equal to the number of shared actors.
Community detection identifies title groups, which are summarized for each title by actor-counter memberships in the 10 largest communities.
These actor-group features reflect recurring co-starring groups whose titles often share themes, styles, and target audiences.