📊 statistics

Prescribe-then-Select: Adaptive Policy Selection for Contextual Stochastic Optimization

This paper introduces Prescribe-then-Select (PS), a modular framework that constructs a library of feasible policies and employs data-driven Optimal Policy Trees to dynamically select the optimal policy for specific covariates, thereby outperforming single-policy approaches in contextual stochastic optimization settings with heterogeneous performance.

Original authors: Caio de Prospero Iglesias, Kimberly Villalobos Carballo, Dimitris Bertsimas

Published 2026-05-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Caio de Prospero Iglesias, Kimberly Villalobos Carballo, Dimitris Bertsimas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a ship navigating through unpredictable waters. Your goal is to reach your destination with the least amount of fuel (cost) possible. However, the weather (uncertainty) changes constantly, and you have a strict rule: you must never run out of fuel or crash into rocks (hard feasibility constraints).

In the past, captains had to choose one navigation strategy for the entire journey. Maybe they used a "Star Chart" method (good for clear nights) or a "Compass" method (good for foggy days). The problem was that the ocean isn't uniform; sometimes the Star Chart works best, and sometimes the Compass does. If you stuck to just one method, you might get lost in the wrong conditions.

This paper introduces a new, smarter way to captain the ship called "Prescribe-then-Select" (PS).

The Core Idea: A Library of Tools, Not Just One Tool

Instead of forcing the ship to use only one navigation method, the PS framework builds a library of different navigation tools (candidate policies).

Tool A might be great for calm, predictable seas.
Tool B might be excellent for stormy, chaotic waters.
Tool C might be the best for navigating around specific islands.

The paper argues that in real-world problems (like managing a store's inventory or planning shipping routes), no single tool is perfect for every situation. Sometimes the weather is calm, and sometimes it's a hurricane.

How It Works: The "Smart Dispatcher"

The PS framework works in two simple steps:

Prescribe (Build the Library): First, the system creates a diverse team of experts. It trains several different models (like a "k-Nearest Neighbor" expert, a "Random Forest" expert, and a "Neural Network" expert) to solve the problem. Each expert has a slightly different way of thinking and works best in different scenarios.
Select (The Smart Dispatcher): This is the magic part. The system trains a "Meta-Dispatcher" (using something called Optimal Policy Trees). This dispatcher looks at the current situation (the "covariates," like the time of year, weather forecast, or holiday season) and asks: "Which expert from our library is best suited for this specific moment?"

If the data shows it's a holiday rush, the dispatcher might say, "Send the Random Forest expert!" If it's a quiet Tuesday, it might say, "Send the k-Nearest Neighbor expert!"

The Analogy: The Restaurant Kitchen

Think of a busy restaurant kitchen:

The Problem: You have to cook meals for customers who have different tastes and dietary restrictions (constraints).
The Old Way: You hire one head chef who tries to cook everything. They are good at pasta but terrible at sushi. If a customer orders sushi, the meal suffers.
The PS Way: You hire a team of specialists: a Pasta Chef, a Sushi Chef, and a Grill Master.
- You also hire a Maitre d' (the Meta-Dispatcher).
- When a customer walks in, the Maitre d' looks at their order. If they want sushi, the Maitre d' immediately sends them to the Sushi Chef. If they want pasta, they go to the Pasta Chef.
- The Maitre d' doesn't cook; they just know exactly which specialist is best for the specific order.

What the Paper Found

The authors tested this idea on two real-world scenarios:

The Newsvendor Problem: Imagine a newspaper seller deciding how many papers to stock. Demand changes based on whether it's a holiday, a weekday, or a rainy day.
Shipment Planning: A logistics company deciding how much to produce and ship before knowing the exact customer orders.

The Results:

In Mixed Conditions: When the environment was mixed (some days were calm, some were chaotic), the "Smart Dispatcher" (PS) consistently outperformed the best single chef. It knew exactly when to switch strategies, saving money and avoiding mistakes.
In Uniform Conditions: If the environment was always the same (e.g., always calm weather), the system naturally figured out that one chef was the best and stuck with them. It didn't make mistakes by switching unnecessarily.
Safety: Crucially, because the system only selects from a list of pre-approved, safe strategies, it never makes a decision that breaks the rules (like running out of fuel).

The Bottom Line

This paper proposes a simple but powerful shift: Don't try to find the one perfect solution for everything. Instead, build a team of good solutions and hire a smart manager to pick the right one for the job.

This approach is "data-driven," meaning the manager learns from past data which expert works best in which situation, without needing to know the exact rules of the weather in advance. It's a flexible, low-risk way to make better decisions in a complex, changing world.

Technical Summary: Prescribe-then-Select (PS)

Problem Setting
The paper addresses Contextual Stochastic Optimization (CSO), a class of problems where a decision-maker observes covariates (context) $X$ before selecting an action $z$ from a feasible set $Z$ to minimize the expected cost $E[c(z, Y) | X=x]$ , where $Y$ is an uncertain random variable. A critical constraint in the setting studied is that decisions must satisfy hard feasibility constraints (which may include integrality constraints) for every realization of the context.

The authors identify a key challenge: in many CSO settings, no single candidate policy uniformly dominates across the entire covariate space. Different modeling paradigms (e.g., point-prediction vs. distributional estimation) often exhibit heterogeneous performance, excelling in specific regimes (e.g., low-variance vs. high-variance regions) while underperforming in others. Existing methods for policy selection often fail in constrained settings because averaging feasible policies does not guarantee a feasible result, and end-to-end training approaches can suffer from computational burdens and slower regret convergence.

Methodology: Prescribe-then-Select (PS)
The authors propose Prescribe-then-Select (PS), a modular, two-stage framework designed to adaptively select the best policy for a given context without violating feasibility constraints.

Prescribe (Library Construction):
The first stage constructs a diverse library of feasible candidate policies $\Pi_M = \{\pi_1, \dots, \pi_M\}$ . These policies map covariates to feasible decisions under different modeling assumptions. The paper utilizes three families of methods:
- Sample Average Approximation (SAA): Ignores covariates, solving a deterministic optimization over historical scenarios.
- Point-Prediction Policies (PPt): Fits a predictive model (e.g., kNN, Random Forest, Neural Network) to estimate $E[Y|X]$ and solves a deterministic optimization using this point estimate.
- Predictive-Prescriptive Policies (PP): Uses predictive models (e.g., kNN, Random Forest) to generate weights for a weighted sample average approximation, effectively approximating the conditional distribution $f_{Y|X}$ .
Select (Meta-Policy Learning):
The second stage learns a meta-policy to select the optimal candidate policy for a specific observed covariate $x$ .
- Mechanism: The meta-policy is implemented using an ensemble of Optimal Policy Trees (OPT). Unlike parametric decision rules, OPTs partition the covariate space into axis-aligned regions and assign a specific policy index to each region.
- Training: The OPTs are trained via K-fold cross-validation. For each fold, candidate policies are trained on the training split, and their out-of-sample costs are computed on the held-out fold to create a "cost table." The OPT is then trained to minimize the empirical cost based on this table, effectively learning which policy performs best in which region of the covariate space.
- Inference: At inference time, an ensemble of trees (trained across folds and random seeds) votes to select the final policy index, which is then applied to generate the decision.

Key Contributions

Formalization: The paper formally defines the problem of policy selection in CSO under hard feasibility constraints, a setting where standard ensemble averaging is often infeasible.
Framework: It introduces the Prescribe-then-Select framework, which decouples policy generation from policy selection. This allows for the integration of diverse, potentially incompatible modeling paradigms while ensuring the final decision remains feasible.
Data-Driven Selection: The approach is entirely data-driven, using cross-validated cost tables to train a meta-policy (Optimal Policy Trees) that learns to partition the covariate space and assign the most effective policy to each region.

Experimental Results
The authors evaluate PS on two benchmark problems: a multi-product newsvendor problem and a two-stage shipment planning problem. Both tasks utilize synthetic data with distinct demand segments (e.g., holiday spikes, seasonal trends) to induce heterogeneity.

Heterogeneity: Experiments confirm that no single policy dominates uniformly. Performance varies significantly across segments and training sizes (e.g., point-prediction methods excel in low-variance segments, while predictive-prescriptive methods dominate in high-variance or discontinuous regimes).
Performance Gains: In heterogeneous regimes, PS consistently outperforms the best single candidate policy. The gains are statistically significant, particularly when training data is limited or when the covariate space contains distinct regimes where different policies are optimal.
Convergence: In regimes where a single policy is uniformly dominant (or as training size $N$ becomes very large and one policy clearly emerges as superior), PS converges to that dominant policy, incurring negligible regret relative to the best single policy.
Computational Efficiency: The overhead of training the meta-policy is minimal compared to the cost of solving the underlying optimization problems for the candidate policies.

Significance and Claims
The paper claims that PS provides a practical, low-risk approach for decision-making environments where multiple high-quality prescriptive models are available. By leveraging contextual information to select the most suitable policy for each instance, PS exploits heterogeneity to improve upon the best single policy without requiring complex end-to-end training or violating feasibility constraints. The framework is presented as a modular solution that can flexibly integrate diverse policies, adapting to complex decision environments where a "one-size-fits-all" model is suboptimal. The authors note that while some base policies are asymptotically optimal, PS offers significant benefits in finite-sample settings by dynamically routing contexts to the most effective model.