How Can the “Optimize Then Predict” Approach Transform Real-Time Decisions?

Imagine you have to pick the best bike route in a city full of obstacles, but you don’t know the traffic conditions yet. Scientists have devised a method called “optimize then predict” (OTP) that tackles similar problems on a much larger scale, like managing servers or planning production.

In the offline stage, the team runs many simulations using different “covariates,” i.e., variables that describe the context (weather, demand, resources). From these data they build a function that approximates the optimal solution for every possible scenario.

When it’s time to decide (online stage), you simply plug the observed covariate into the ready‑made function and instantly get the best decision, without re‑simulating.

The critical point is that simulations are not perfect: they produce “inexact” solutions with a certain bias (systematic error) and variance (noise). The authors created a theoretical framework that accounts for both, showing how they affect the gap to the true optimum.

Using Polyak‑Ruppert averaged SGD, they tested four smoothing techniques: k‑nearest neighbor, kernel smoothing, linear regression, and kernel ridge regression. They figured out the optimal way to split the computational budget Γ between the number of covariates to simulate and the number of replications per covariate, achieving a convergence speed close to Γ⁻¹.

A numerical study confirms the theory, proving that OTP is not only elegant but also practically valuable for ultra‑fast decisions.

The work falls within simulation optimization, where the goal is to find near‑optimal decisions by leveraging costly simulation models. Strong convexity ensures a unique global minimum and permits gradient‑based methods with convergence guarantees.

In the offline stage, the optimal‑solution function \(x^*(z)\) is approximated by an estimator \(\hat{x}(z)\) built on a finite design set \(\{z_i\}_{i=1}^N\). The choice of \(N\) and the number of replications \(M_i\) per \(z_i\) is crucial: a limited budget \(\Gamma = \sum_i M_i\) must be allocated to minimize total error.

The theoretical framework introduces two error components: bias \(\mathbb{E}[\hat{x}(z)]-x^*(z)\) due to data smoothing, and variance \(\mathbb{V}[\hat{x}(z)]\) due to simulation noise. For each of the four smoothing techniques, asymptotic expressions of bias and variance are derived as functions of \(N\) and \(M_i\). For instance, for k‑NN the bias decays as \(N^{-2/d}\) (d is the covariate dimension) while variance scales with \(1/M\).

Using Stochastic Gradient Descent with Polyak‑Ruppert averaging, one obtains an estimate \(\hat{x}_t\) that converges almost deterministically to \(x^*(z)\) at a rate \(O(t^{-1})\). The analysis shows that, by choosing \(N \propto \Gamma^{\frac{d}{2+d}}\) and \(M_i \propto \Gamma^{\frac{2}{2+d}}\), the overall optimality gap scales as \(\Gamma^{-1}\).

The result is striking because, despite the presence of bias and variance, the optimal combination of smoothing and budget allocation recovers almost the convergence speed of an ideal algorithm with exact solutions. Numerical experiments on a stochastic inventory management problem confirm the theoretical predictions: error curves align with asymptotic estimates and kernel ridge regression with proper regularization yields the best practical performance. This study paves the way for OTP implementations in real‑time critical settings such as algorithmic trading or cyber‑physical system control.