Theorem 8 — under the noise condition, a plug-in policy with pointwise sub-Gaussian estimation error at rate aₙ has regret ≤ C(α,γ) B aₙ^{−(1+α)/2}

Let $\mathcal Z = \{z : Az \le b\} \subseteq \mathbb R^d$ be a nonempty polytope with $\|z\| \le B$ on $\mathcal Z$ and extreme points $\mathcal Z^\angle$. Let $(X, Y)$ have feature law $\mathbb P_X$ on $\mathbb R^p$ and bounded costs $\|Y\| \le 1$, with $f^*(x) = \mathbb E[Y \mid X = x]$ and gap $\Delta$. From $n$ i.i.d. observations $\mathcal D$ an estimate $\hat f = \hat f_{\mathcal D}$ of $f^*$ is formed, and the estimate-then-optimize policy $\pi_{\hat f}$ chooses, at every $x$, an extreme point minimizing $\hat f(x)^\top z$ over $\mathcal Z$.

Fix $\alpha, \gamma \ge 0$ and constants $C_1, C_2 > 0$. There is a constant $C$, depending only on $\alpha, \gamma, C_1, C_2$, such that the following holds for every polytope, every distribution, every $n$, every $a_n > 0$ and every estimator. If

1. the noise condition (Assumption 2) holds: $\mathbb P_X(0 < \Delta(X) \le \delta) \le (\gamma\delta/B)^\alpha$ for all $\delta > 0$, and
2. for every $\delta > 0$ and almost every $x$, $\mathbb P_{\mathcal D}\bigl(\|\hat f(x) - f^*(x)\| \ge \delta\bigr) \le C_1 \exp(-C_2 a_n \delta^2)$,

then

With $a_n$ of order $n$ up to a logarithmic factor, as for well-specified least squares, the rate $n^{-(1+\alpha)/2}$ is, up to logarithms, faster than the rate $n^{-(1+\alpha)/(2+\alpha)}$ that no method relying only on a policy class of finite Natarajan dimension can beat (Theorem 7 of the paper): estimate-then-optimize can outperform integrated methods.

Formalization Note The paper writes $C(\alpha, \gamma)$ and calls $C_1, C_2$ universal constants; here $C$ is chosen after $\alpha, \gamma, C_1, C_2$ and before everything else, which is that reading. The distribution is given as the law of $X$ together with the conditional law of $Y$ given $X$. Plug-in policies are any selection from the argmin with values in $\mathcal Z^\angle$ (the paper's consistent tie-breaking is not required, which makes the statement stronger). The estimator and the policy are assumed jointly measurable in the data and the feature, so that the regret is a genuine integral; the paper leaves this implicit. Positivity of $C_1, C_2$ and of $a_n$ is the paper's implicit convention.