Finite-sample expected-risk control on a finite grid

For any admissible input to the rule, every threshold is a finite real number since its numerator is a finite sum and $n+1>0$. The scan tests each index at most once, returning at the first passing index; if none passes, the specified fallback returns the supplied rule at index $M$. Since $M\ge 1$, both branches give a unique output after at most $M$ tests, without any monotonicity or endpoint-safety assumption.

Write $C_j=({\sum }_{i=1}^n{L}_i({\lambda }_j)+B)\mathrm{/}(n+1)$ and $S_j=({\sum }_{i=1}^{n+1}{L}_i({\lambda }_j))\mathrm{/}(n+1)$. These are Borel functions of the finite row matrix. Each calibration pass event and the fallback event is a finite Boolean combination of Borel threshold sets, so the selected index is Borel-measurable. Define $j_{\ast }=\min \{j:S_j\le \alpha \}$; this set is nonempty since $S_M\le \alpha$ by endpoint safety. Each event $\{j_{\ast }=j\}=\{S_j\le \alpha \}\cap {\bigcap }_{k<j}\{S_k>\alpha \}$ is Borel, so $j_{\ast }$ and $g(W)=L_{n+1}(\widehat{\lambda }(W))$ are Borel-measurable as well.

If the calibration scan passes first at $q$, then $S_q=C_q+(L_{n+1}({\lambda }_q)-B)\mathrm{/}(n+1)\le C_q\le \alpha$, so $j_{\ast }\le q=\widehat{j}$. If the scan has no pass, then $\widehat{j}=M$ and $j_{\ast }\le M$. In either case $j_{\ast }\le \widehat{j}$, and row monotonicity gives $L_{n+1}({\lambda }_{\widehat{j}})\le L_{n+1}({\lambda }_{j_{\ast }})$ almost surely.

Set $V_i=L_i({\lambda }_{j_{\ast }})$. The full-row averages $S_j$ are invariant under row permutations, so $j_{\ast }$ is a symmetric measurable function of all rows. Consequently the vector $(V_1,\dots ,V_{n+1})$ is exchangeable. Its entries have the same law by [F7]; since they are bounded, [F8] gives finite expectations and [F6] gives their equality. By [F6], the expectation of their average is $\mathbb{E}[S_{j_{\ast }}]$, which is at most $\alpha$ because $S_{j_{\ast }}\le \alpha$ almost surely. Thus $\mathbb{E}[L_{n+1}({\lambda }_{j_{\ast }})]\le \alpha$.

By step 2.1 and monotonicity of expectation in [F6], $\mathbb{E}[L_{n+1}(\widehat{\lambda })]\le \mathbb{E}[L_{n+1}({\lambda }_{j_{\ast }})]$. Step 2.2 bounds the right side by $\alpha$, proving the marginal guarantee.

For almost every training outcome $\omega$, apply the argument established in steps 1.2 and 2.1–2.2 under the conditional row law $Q_{\omega }$ to obtain $\int gd{Q}_{\omega }\le \alpha$, where $g(W)=L_{n+1}(\widehat{\lambda }(W))$. The function is Borel-measurable by step 1.2 and bounded by $B$ by [F1]. Its dyadic lower approximations $g_m=2^{-m}\lfloor 2^{m}g\rfloor$ are finite-valued Borel simple functions increasing to $g$. For each conditioning event $H\in \mathcal{T}$, decompose $g_m$ into its finitely many level-set indicators. The event identities in [F3] and linearity in [F6] then give ${\int }_H\int g_{m}d{Q}_{\omega }d\mathbb{P}(\omega )={\int }_H{g}_m(W)d\mathbb{P}$. Applying [F5] to both sides gives the same identity for $g$. Each kernel integral of $g_m$ is $\mathcal{T}$-measurable by [F3], so their pointwise limit $\int gd{Q}_{\omega }$ is measurable. By [F4], this bounded function is a version of $\mathbb{E}[g\mid \mathcal{T}]$. The sectionwise bound therefore gives the claimed conditional inequality almost surely.