From Finite Risk Tables to Global Epsilon Rules

From a Finite Table to a Global Guarantee

A finite risk table can make a difficult minimax problem look manageable: its rows are parameter values and its columns are procedures. But a table alone says nothing about parameter values omitted from its rows. On a noncompact parameter space, even a calculation that is accurate on a large bounded region need not control risk far away. A global guarantee therefore needs two different ingredients: a lower bound on the minimax value and an upper bound on the risk of an actual procedure at every parameter value.

The lower bound can come from restricting attention to selected parameter values and using a prior supported there. The upper bound comes from a candidate procedure, a discretization bound on a compact region, and a separate risk certificate on its complement. The difference between these bounds is the quantity that certifies epsilon-minimaxity.

Definition: For a common class $\mathcal D$ of decision rules and risk function $R(\theta,\delta)$, the global minimax value is $$ V=\inf_{\delta\in\mathcal D}\sup_{\theta\in\Theta}R(\theta,\delta). $$ A rule $\delta$ is $\varepsilon$-minimax if $\sup_{\theta\in\Theta}R(\theta,\delta)\le V+\varepsilon$. A lower bound $L\le V$ and a certified upper bound $U\ge\sup_{\theta\in\Theta}R(\theta,\delta)$ establish this whenever $U-L\le\varepsilon$.

A finite risk table records values $R(\theta_i,\delta_j)$ at finitely many parameter values $\theta_i$ and candidate rules $\delta_j$. Randomizing among candidate rules is allowed when the rule class permits external randomization: if weights $\lambda_j\ge0$ sum to one, the mixture has risk $\sum_j\lambda_jR(\theta,\delta_j)$. Its maximum table entry can provide an upper bound on risk at the listed points. It is not, by itself, an upper bound outside those points.

What Restriction and a Prior Can Certify

For a subset $G\subseteq\Theta$, define the restricted minimax value using the same rule class: $$ V_G=\inf_{\delta\in\mathcal D}\max_{\theta\in G}R(\theta,\delta). $$ For each fixed rule, $\max_{\theta\in G}R(\theta,\delta)\le\sup_{\theta\in\Theta}R(\theta,\delta)$. Taking infima over the same class preserves the inequality, so $V_G\le V$. This is a valid lower bound, though its numerical value may be hard to compute. If a finite table restricts the rule class as well, its optimized value need not equal $V_G$, and cannot automatically be used as a lower bound for $V$.

A prior gives a related lower bound. For a probability distribution $\pi$ on $\Theta$, its Bayes risk is $b(\pi)=\inf_{\delta\in\mathcal D}\int R(\theta,\delta)\,\pi(d\theta)$. For every rule, its average risk under $\pi$ is at most its maximum risk over $\Theta$; hence $b(\pi)\le V$. This argument holds whether or not $\pi$ has finite support.

Result: If a finite table produces a candidate rule whose maximum risk on a finite set $G$ is $q$, that table supplies a global lower bound only if it also certifies a lower bound on $V_G$ or on a Bayes risk over the full rule class. A candidate's small table risk is an upper-bound ingredient, not a minimax lower bound.

Worked Example: A Two-Row Risk Table and Its Prior Bound

Suppose the parameter set is $\Theta=\{0,1\}$, there is no informative observation, the available actions are $0$ and $1$, and the loss is $1$ for an incorrect action and $0$ otherwise. The risk table is:

Parameter	Action 0	Action 1
0	0	1
1	1	0

Let a randomized rule choose action 1 with probability $p$. Its risks at parameters 0 and 1 are $p$ and $1-p$. Thus its maximum risk is $\max(p,1-p)$, minimized at $p=1/2$, where the maximum is $1/2$. The table gives a candidate upper bound $q=1/2$.

Now put prior probability $1/2$ on each parameter. The average risk of any such rule is $$ \frac12p+\frac12(1-p)=\frac12. $$ Therefore its Bayes risk is $1/2$, which is a lower bound on $V$. Here the table is the complete decision problem, so the calculation is exact: the randomized rule is minimax. If the table had omitted possible actions or rules, its optimization would not by itself establish that Bayes lower bound.

Extending a Grid Bound Across a Compact Region

Let $K\subseteq\Theta$ be compact, and let $G\subset K$ be a finite $h$-net: every $\theta\in K$ is within distance $h$ of some point of $G$. Suppose the candidate rule $\delta$ has a uniform modulus of continuity on $K$: for every $\theta,\theta'\in K$, $$ |R(\theta,\delta)-R(\theta',\delta)|\le \omega(d(\theta,\theta')), $$ where $\omega$ is nondecreasing. Then a grid maximum $q=\max_{\theta_i\in G}R(\theta_i,\delta)$ implies $\sup_{\theta\in K}R(\theta,\delta)\le q+\omega(h)$. The modulus must apply to the risk of the rule being certified; a modulus for some other rule does not suffice.

Worked Example: A Uniform Grid Error in a Bernoulli Model

Let $X\sim\operatorname{Bernoulli}(\theta)$, with $\theta\in[0,1]$. Consider rules that, after observing $X=x$, report an action $d_x\in[0,1]$, under squared-error loss $(d_X-\theta)^2$. For every such rule, the loss is between 0 and 1. Compare its risks at $\theta$ and $\theta'$ by first changing the Bernoulli probabilities while holding the loss at $\theta$ fixed, then changing the loss parameter:

The probability-change contribution is $|\theta-\theta'|\,|(d_1-\theta)^2-(d_0-\theta)^2|\le|\theta-\theta'|$, because both squared losses lie in $[0,1]$. For each $x$, the loss-change contribution is bounded by $2|\theta-\theta'|$, since $|(d_x-\theta)^2-(d_x-\theta')^2|=|\theta-\theta'||2d_x-\theta-\theta'|\le2|\theta-\theta'|$. Consequently,

|R(\theta,d)-R(\theta',d)|\le 3|\theta-\theta'|.

Take $G=\{0,1/2,1\}$, whose largest distance from a point in $[0,1]$ to the nearest grid point is $h=1/4$. The constant rule $d_0=d_1=1/2$ has risks $1/4,0,1/4$ at the three grid points, so $q=1/4$. The modulus gives the certified bound $\sup_{\theta\in[0,1]}R(\theta,d)\le1/4+3(1/4)=1$. This bound is valid but conservative; indeed the risk is $(1/2-\theta)^2$, whose actual maximum is $1/4$. The calculation illustrates why the modulus is a certificate, not necessarily a sharp estimate.

The Global Certificate and Its Proof

A compact-region grid bound still does not control $\Theta\setminus K$. For the selected candidate $\delta$, require a separate certified tail bound $T$ such that $R(\theta,\delta)\le T$ for every $\theta\notin K$. For the lower bound, let $\pi$ be a finite-support prior and suppose a calculation over the full rule class certifies $b(\pi)\ge L$. These pieces yield a direct global certificate.

Theorem: Suppose $G$ is an $h$-net of $K$, the candidate $\delta\in\mathcal D$ has risk modulus $\omega$ on $K$, its grid maximum is $q$, and $R(\theta,\delta)\le T$ for every $\theta\in\Theta\setminus K$. Suppose also that a prior $\pi$ on $\Theta$ has Bayes risk $b(\pi)\ge L$. Then $$ L\le V\le\sup_{\theta\in\Theta}R(\theta,\delta)\le U, \qquad U=\max\{q+\omega(h),T\}. $$ In particular, if $U-L\le\varepsilon$, then $\delta$ is $\varepsilon$-minimax.

Proof. Since $b(\pi)\le V$, the asserted lower bound $L\le V$ follows. For any $\theta\in K$, choose a net point $\theta_i\in G$ with $d(\theta,\theta_i)\le h$. Then $R(\theta,\delta)\le R(\theta_i,\delta)+\omega(h)\le q+\omega(h)$. For $\theta\notin K$, the tail hypothesis gives $R(\theta,\delta)\le T$. Taking the supremum over the two regions gives $\sup_\Theta R(\theta,\delta)\le U$. Finally, $\sup_\Theta R(\theta,\delta)-V\le U-L\le\varepsilon$, which is the definition of epsilon-minimaxity. $\square$

Accounting for Approximation Errors

The lower bound may come from approximating a prior that is easier to analyze than the final finite-support prior. The error must be stated in a way that controls Bayes risk, which is an infimum over rules. Suppose $0\le R(\theta,\delta)\le M$ for every parameter and rule, and two priors $\pi,\tilde\pi$ satisfy $\sup_{\delta\in\mathcal D}|\int R\,d\pi-\int R\,d\tilde\pi|\le\eta$. Then $|b(\pi)-b(\tilde\pi)|\le\eta$: if two functions differ everywhere by at most $\eta$, their infima differ by at most $\eta$. In particular, if their total variation distance is at most $\tau$, then $\eta\le M\tau$, using the convention that total variation is $\sup_A|\pi(A)-\tilde\pi(A)|$.

For example, suppose a prior $\pi_0$ has Bayes risk at least $V-\rho$, but has mass at most $\tau$ outside $K$. Move that mass to any fixed point in $K$. For every rule, the change in its integrated risk is at most $M\tau$, so the resulting prior's Bayes risk is at least $V-\rho-M\tau$. If this prior is then discretized with a uniform integrated-risk error at most $\eta$, the final finite prior has Bayes risk at least $V-\rho-M\tau-\eta$. The quantities $\rho$, $M\tau$, and $\eta$ are respectively the starting-prior, tail-restriction, and prior-discretization errors. Such a near-least-favorable starting prior is an additional hypothesis or certificate; it does not follow merely from noncompactness or from having a finite table.

The upper-bound errors have a separate ledger. If a table-based optimization returns a candidate whose grid maximum is at most $q_0+\alpha$, where $\alpha$ is its optimization or numerical error, then use $q=q_0+\alpha$ in the theorem. The compact-region extension adds $\omega(h)$, and the tail region contributes $T$. These errors are combined by taking the maximum of the two regional bounds, not by silently treating the grid bound as global.

Worked Example: A Noncompact Normal-Mean Certificate

Observe $Y\sim N(\theta,1)$, where $\Theta=\mathbb R\setminus\{0\}$. The action is $+1$ or $-1$, and the loss is 1 if the action has the wrong sign for $\theta$, and 0 otherwise. Consider the rule that ignores $Y$ and chooses each action with probability $1/2$. Its risk is exactly $1/2$ at every $\theta$, so $U=1/2$ is a global upper bound. In particular, it is a certified tail bound outside any compact region.

For a lower bound, put equal prior probability on $\theta=a$ and $\theta=-a$, with $a>0$. The likelihood ratio for the two normal distributions favors $+a$ exactly when $y>0$, because $f_a(y)/f_{-a}(y)=\exp(2ay)$. Thus the Bayes rule chooses the sign of $Y$. Under either parameter its error probability is $\Phi(-a)$, where $\Phi$ is the standard normal distribution function. The Bayes risk, and hence a lower bound on $V$, is $\Phi(-a)$.

Choose $a=0.01$. Numerically, $\Phi(-0.01)\approx0.4960106$, so the conservative lower bound $L=0.4960$ is valid. The gap is $U-L=0.0040$. Therefore the randomized rule is $0.0041$-minimax, with a small margin for rounding. The finite prior is supported on the two table rows $-0.01$ and $0.01$; its lower-bound validity comes from its Bayes risk, not from assuming that those rows represent all possible parameter values. The candidate's constant risk supplies the global upper bound, including arbitrarily large $|\theta|$.

Common Pitfalls

Calling a restricted table value an upper bound on global minimax risk. With the same rule class, restriction gives $V_G\le V$, a lower bound. A table of selected candidate rules may not even equal $V_G$.
Extending a grid maximum without a uniform modulus. A risk curve can rise sharply between grid points. State and verify a modulus for the candidate being certified.
Ignoring the complement of the compact region. Compact exhaustion does not prove a global upper bound. Give a tail-risk bound, or otherwise control risk on the entire complement.
Using a finite table's prior calculation as a Bayes lower bound without checking the rule class. The infimum defining Bayes risk must be over the full class in the minimax problem, or a valid reduction to the table's class must be established.

Key takeaway: A global epsilon-minimax certificate has two independent sides: a prior-based lower bound valid for the full rule class, and a candidate-specific upper bound valid at every parameter value. Restriction, discretization, prior approximation, and tail errors must each be accounted for explicitly.

Check Your Understanding

For each question, identify which part of a global certificate is at issue.

Why does restricting the parameter set give a lower bound on the global minimax value when the rule class is unchanged?
A candidate has grid maximum $q$, grid radius $h$, and risk modulus $\omega$ on $K$. What bound follows for its maximum risk on $K$?
What additional condition is needed before that compact-region bound controls its global risk?
If two priors have total variation distance at most $\tau$ and all risks lie in $[0,M]$, how large can their Bayes-risk difference be?
Why might optimizing a risk table over only a few candidate rules fail to provide a lower bound on the global minimax value?