Theorem. Uniform proxy disagreement gives two-epsilon regret [ftip-00E2]
Theorem. Uniform proxy disagreement gives two-epsilon regret [ftip-00E2]
Let \(\mathcal Y_x\) be finite, let \(u,r:\mathcal Y_x\to \mathbb R\), and assume \(|r(y)-u(y)|\le \varepsilon \) for every \(y\), with \(\varepsilon \ge 0\). If \(y^\star \) maximizes \(u\) and \(\widehat y\) maximizes \(r\), then
\[u(y^\star )-u(\widehat y)\le 2\varepsilon .\]Indeed, \(u(y^\star )\le r(y^\star )+\varepsilon \le r(\widehat y)+\varepsilon \le u(\widehat y)+2\varepsilon \). This is a finite same-class decision bound, not an optimization, distribution-shift, or capability theorem.