Constructing Epsilon-Minimax Rules from Infima

Why an Infimum Gives an Approximate Rule

A minimax value summarizes the smallest worst-case risk available in a decision problem. The infimum defining that value need not be achieved by any rule. Still, if the value is finite, then for every positive tolerance there is an admissible rule whose worst-case risk is within that tolerance of the value. The justification is elementary, but its scope matters: it proves existence of approximate rules, not the existence of an exactly minimax rule or of a saddle point.

Let $\Theta$ be the parameter space and $\mathcal D$ a nonempty class of admissible decision rules. For a rule $\delta\in\mathcal D$, write $R(\theta,\delta)$ for its risk at parameter $\theta$, usually the expected loss. Its worst-case risk is the supremum over the parameter space. The minimax value is the infimum of these worst-case risks over all admissible rules.

Definition: The worst-case risk of a rule $\delta$ is $$ M(\delta)=\sup_{\theta\in\Theta}R(\theta,\delta). $$ The minimax value is $$ V=\inf_{\delta\in\mathcal D}M(\delta). $$ For $\varepsilon>0$, a rule is $\varepsilon$-minimax if $M(\delta)\leq V+\varepsilon$.

Assume throughout that risks are nonnegative, possibly taking the value $+\infty$, and that $V$ is finite. The rule class is assumed nonempty. These conditions are natural for ordinary statistical decision problems with nonnegative loss; they also make explicit why the argument has a rule to select from.

The Infimum Selection Argument

The key fact is a defining property of the infimum. If a nonempty set of extended nonnegative numbers has a finite infimum $V$, then for every $\varepsilon>0$, at least one number in the set is strictly less than $V+\varepsilon$. Otherwise every number would be at least $V+\varepsilon$, contradicting that $V$ is the greatest lower bound.

Lemma: Let $\mathcal D$ be nonempty and let $M(\delta)\in[0,\infty]$ for each $\delta\in\mathcal D$. If $V=\inf_{\delta\in\mathcal D}M(\delta)<\infty$, then for every $\varepsilon>0$ there exists $\delta_\varepsilon\in\mathcal D$ such that $$ M(\delta_\varepsilon)<V+\varepsilon. $$

Proof. Suppose, to the contrary, that for some $\varepsilon>0$, every $\delta\in\mathcal D$ satisfies $M(\delta)\geq V+\varepsilon$. Then $V+\varepsilon$ is a lower bound for the set of worst-case risks. This contradicts $V$ being its greatest lower bound, since $V+\varepsilon>V$. Therefore some rule has worst-case risk less than $V+\varepsilon$. $\square$

Theorem: If the minimax value $V=\inf_{\delta\in\mathcal D}\sup_{\theta\in\Theta}R(\theta,\delta)$ is finite, then for every $\varepsilon>0$ there exists an $\varepsilon$-minimax rule.

Proof. Apply the lemma to the set $\{M(\delta):\delta\in\mathcal D\}$. It supplies a rule $\delta_\varepsilon$ with $M(\delta_\varepsilon)<V+\varepsilon$. In particular, $M(\delta_\varepsilon)\leq V+\varepsilon$, which is exactly the stated $\varepsilon$-minimax condition. $\square$

The strict inequality from the lemma is slightly stronger than the usual definition requires. It also avoids ambiguity about whether “within $\varepsilon$” means less than or equal to the tolerance. No compactness, continuity, convexity, or minimax interchange is needed for this conclusion. The argument only uses the definition of an infimum and the existence of a nonempty rule class with finite infimum.

Worked Examples

Worked Example: A Finite Value That Is Not Attained

Suppose $X\sim N(0,1)$, the parameter space is $\Theta=\{0\}$, the action space is $(0,\infty)$, and the loss for action $a$ is $L(0,a)=a^2$. Consider all measurable decision rules that take values in $(0,\infty)$.

For any such rule $\delta$, the risk is $R(0,\delta)=E[\delta(X)^2]$. It is nonnegative, and the constant rules $\delta_a(X)=a$, for $a>0$, have risk $a^2$. Letting $a$ decrease to zero shows $V\leq 0$; nonnegativity gives $V\geq 0$. Hence $V=0$.

No admissible rule attains this value. Since $\delta(X)>0$ almost surely, $\delta(X)^2>0$ almost surely, so its expectation cannot equal zero. For any $\varepsilon>0$, choose the constant rule $\delta(X)=\sqrt{\varepsilon/2}$. Its risk is $\varepsilon/2<\varepsilon=V+\varepsilon$, so it is $\varepsilon$-minimax despite the absence of an exactly minimax rule.

Worked Example: Two Parameters and Squared-Error Loss

Let $\Theta=\{-1,1\}$, let the observation have the same distribution under both parameter values, and let the action space be $(0,1)$. Use squared-error loss $L(\theta,a)=(a-\theta)^2$. A rule may randomize, but its selected action $A$ must lie in $(0,1)$.

At $\theta=-1$, the loss is $(A+1)^2>1$ almost surely. Therefore $R(-1,\delta)>1$, and in particular $M(\delta)>1$, for every admissible rule. On the other hand, for a constant action $a\in(0,1)$, the two risks are $$ R(-1,\delta_a)=(1+a)^2,\qquad R(1,\delta_a)=(1-a)^2. $$ Since $(1+a)^2>(1-a)^2$, the worst-case risk is $(1+a)^2$, which decreases to $1$ as $a$ decreases to zero. Thus $V=1$, but no rule attains it.

For a given $\varepsilon>0$, set $a=\min(\varepsilon/4,1/2)$. If $\varepsilon\leq 2$, then $$ (1+a)^2=1+\varepsilon/2+\varepsilon^2/16<1+\varepsilon, $$ because $\varepsilon^2/16\leq\varepsilon/8$. If $\varepsilon>2$, then $a=1/2$ and $(1+a)^2=9/4<1+\varepsilon$. In either case the constant rule is $\varepsilon$-minimax. The calculation exhibits the general pattern: approach the excluded boundary closely enough to meet the chosen tolerance.

Worked Example: An Approximate Rule Need Not Be Exactly Minimax

Consider a decision problem with parameter space $\Theta=\{0,1\}$, one uninformative observation, and three available actions $a,b,c$. Their losses at the two parameter values are:

Action	Loss at $\theta=0$	Loss at $\theta=1$
$a$	0	4
$b$	2	2
$c$	2.04	2.04

A randomized rule chooses these actions with probabilities $p_a,p_b,p_c$, where the probabilities are nonnegative and sum to one. Its risks are $R(0,\delta)=2p_b+2.04p_c$ and $R(1,\delta)=4p_a+2p_b+2.04p_c$. The second risk is at least $2$, because it equals $2+2p_a+0.04p_c$. The deterministic rule choosing $b$ has risk $2$ at both parameter values. Therefore $V=2$, attained by $b$.

The deterministic rule choosing $c$, however, has worst-case risk $2.04$. For $\varepsilon=0.05$, it satisfies $2.04\leq 2+0.05$, so it is $\varepsilon$-minimax, but it is not exactly minimax. The theorem guarantees the existence of a rule within the tolerance; it does not make every such rule an exact optimizer.

What the Argument Does Not Establish

The infimum selection argument is deliberately limited. It does not identify a rule explicitly unless the problem supplies additional calculations or structure. The proof says that a suitable rule exists; it does not provide a computational method for finding one. In an infinite rule class, the selection may be entirely abstract.

It also does not show that the minimax value is attained. The first two examples have finite minimax values but no rule with worst-case risk exactly equal to the value. In general, an exactly minimax rule would require some $\delta^*\in\mathcal D$ satisfying $M(\delta^*)=V$. An infimum need not be a minimum.

Nor does this argument prove a minimax interchange, identify a least-favorable prior, or produce an approximate saddle point. Those conclusions compare or relate different optimization problems and require additional hypotheses. Selecting a rule near the infimum of the worst-case risks alone makes no such comparison.

A common mistake is to reason that because $V$ is finite, there must be a rule with $M(\delta)=V$. This confuses an infimum with a minimum. The correction is to use the defining approximation property: for each $\varepsilon>0$, select a rule with $M(\delta)<V+\varepsilon$, while leaving open whether equality at $V$ is possible. A second mistake is to set $\varepsilon=0$ in that property. The infimum guarantee applies to positive tolerances; it does not promise a rule with risk below $V$, or even one with risk equal to $V$.

Check the setup.
Confirm that the rule class is nonempty and the minimax value is finite.

Fix a positive tolerance.
Choose any $\varepsilon>0$; the claim is made separately for each such tolerance.

Apply the infimum property.
Select a rule whose worst-case risk is less than $V+\varepsilon$.

State only what follows.
The selected rule is $\varepsilon$-minimax; exact attainment and other game-theoretic conclusions remain open.

The practical value of the result is that approximate minimax performance is available even in settings where optimal rules fail to exist. It gives a rigorous existence guarantee without adding regularity assumptions that may not hold. When a problem asks only for an $\varepsilon$-minimax rule, the infimum argument is sufficient; when it asks for an exact optimizer or a relationship to priors, further reasoning is needed.

Key takeaway: A finite minimax value is always approachable from above: for every $\varepsilon>0$, some admissible rule has worst-case risk less than $V+\varepsilon$. This is an existence statement about approximate performance, not a claim of attainment.

Check Your Understanding

Use the infimum property to answer each question precisely.

What assumptions on the rule class and minimax value are used to guarantee an $\varepsilon$-minimax rule?
Why does $M(\delta_\varepsilon)<V+\varepsilon$ imply the usual definition $M(\delta_\varepsilon)\leq V+\varepsilon$?
In the first worked example, why does the risk approach zero without any admissible rule having risk zero?
Does a finite minimax value guarantee an exactly minimax rule? Explain the distinction between an infimum and a minimum.
Name one conclusion about priors or saddle points that does not follow from the infimum selection argument alone.

Action	Loss at \(\theta=0\)	Loss at \(\theta=1\)
\(a\)	0	4
\(b\)	2	2
\(c\)	2.04	2.04

Constructing Epsilon-Minimax Rules from Infima

What You'll Learn