Epsilon-Minimax Rules and Minimax Gaps

Worst-Case Risk and the Minimax Value

A minimax analysis compares decision rules by their performance in the most demanding parameter state. The quantity being minimized is not a rule’s risk at one selected value of the parameter, but its maximum risk over the parameter space. Once this worst-case criterion is fixed, an exact minimax rule is one whose maximum risk equals the smallest possible maximum risk. Approximate minimax rules are assessed by how far their maximum risk lies above that benchmark.

Definition: Let $\Theta$ be a parameter space, let $\mathcal{D}$ be a nonempty class of decision rules, and let $R(\theta,\delta)$ be the risk of rule $\delta\in\mathcal{D}$ at $\theta\in\Theta$. The maximum risk of $\delta$ is $$ M(\delta)=\sup_{\theta\in\Theta} R(\theta,\delta). $$ The minimax value is $$ V=\inf_{\delta\in\mathcal{D}} M(\delta) =\inf_{\delta\in\mathcal{D}}\sup_{\theta\in\Theta}R(\theta,\delta). $$ A rule $\delta^\star$ is an exact minimax rule if $M(\delta^\star)=V$.

The supremum need not be attained at a particular parameter value: $M(\delta)$ is the least upper bound of the risks, whether or not some $\theta$ achieves it. Similarly, an infimum need not be attained by a rule. Thus, the minimax value is a benchmark even in a problem with no exact minimax rule. In what follows, when discussing finite approximation tolerances, assume $V<\infty$.

For a fixed rule, its maximum-risk gap (also called its excess maximum risk) is $\Delta(\delta)=M(\delta)-V$. Since $V$ is the infimum of all maximum risks, $\Delta(\delta)\geq 0$ whenever $M(\delta)$ is finite. A rule with infinite maximum risk has infinite gap when $V$ is finite.

Definition: For $\varepsilon\geq 0$, a rule $\delta$ is additive $\varepsilon$-minimax if $$ M(\delta)\leq V+\varepsilon. $$ For a relative tolerance $\eta\geq 0$, a rule is multiplicative $\eta$-minimax if $$ M(\delta)\leq (1+\eta)V. $$ The multiplicative definition is informative as a relative approximation when $0<V<\infty$. If $V=0$, it requires $M(\delta)=0$, regardless of the value of $\eta$.

These conventions use non-strict inequalities: a rule exactly at the tolerance boundary qualifies. Additive approximation measures excess risk in the units of the loss. Multiplicative approximation measures excess risk relative to the minimax value, since, for positive finite $V$, its condition is equivalent to $\Delta(\delta)\leq \eta V$.

Worked Risk Calculations

Worked Example: A Randomized Rule and Its Maximum-Risk Gap

Consider a decision problem with no informative observation, parameter space $\Theta=\{0,1\}$, and two actions $A$ and $B$. Their losses are:

Action	Loss at $\theta=0$	Loss at $\theta=1$
A	0	4
B	3	1

Let a randomized rule choose $A$ with probability $t$, where $0\leq t\leq 1$, and choose $B$ with probability $1-t$. Its risks are the expected losses:

R(0,t)=0t+3(1-t)=3-3t,\qquad R(1,t)=4t+1(1-t)=1+3t.

The maximum risk is the larger of these two quantities. They are equal when $3-3t=1+3t$, so $t=1/3$; both risks then equal $2$. For any $t<1/3$, $R(0,t)>2$, and for any $t>1/3$, $R(1,t)>2$. Therefore the smallest possible maximum risk is $V=2$, attained at $t=1/3$.

For $t=1/5$, the risks are $R(0,t)=3-3/5=12/5=2.4$ and $R(1,t)=1+3/5=8/5=1.6$. Hence $M(t)=2.4$ and $\Delta(t)=2.4-2=0.4$. This rule is additive $0.4$-minimax, and its relative excess is $0.4/2=0.2$, so it is multiplicative $0.2$-minimax as well.

Worked Example: How Loss Units Affect Additive Tolerances

Use the same decision problem, but measure loss in units one thousand times as large. Every risk and the minimax value are multiplied by $1000$; consequently the value is $V'=2000$. Consider the rule $t=0.3$. Its risks in the original units are $R(0,t)=3-0.9=2.1$ and $R(1,t)=1+0.9=1.9$, so its maximum risk is $2.1$. In the rescaled units its maximum risk is $M'=2100$, and its gap is $\Delta'=2100-2000=100$.

In the original units the gap was $2.1-2=0.1$. Thus, the same rule’s additive gap changes from $0.1$ to $100$ when the loss is rescaled. Its relative excess does not change: $0.1/2=0.05$ and $100/2000=0.05$. The rule is multiplicative $0.05$-minimax in either set of units. This illustrates why an additive tolerance must be chosen in context, while a relative tolerance is invariant to a positive rescaling of loss.

Worked Example: Zero Minimax Value

Suppose $\Theta=\{0,1\}$, there is no informative observation, and the available actions are $S$ and $C$. Action $S$ has loss $0$ at both parameter values; action $C$ has loss $1$ at both. A randomized rule chooses $C$ with probability $q$, where $0\leq q\leq 1$. At either parameter value its risk is $q$, so $M(q)=q$. The rule choosing $S$ with certainty has maximum risk $0$, and therefore $V=0$.

The gap of the randomized rule is $\Delta(q)=q-0=q$. It is additive $\varepsilon$-minimax exactly when $q\leq\varepsilon$. But the multiplicative condition is $q\leq(1+\eta)0=0$, which holds only when $q=0$. A positive relative tolerance cannot express a nonzero allowance above a zero benchmark.

What the Maximum-Risk Gap Tells Us

The gap gives a direct test of both exact and approximate performance for a specified rule. The following result makes the relationship precise; it does not assume that the minimax value is attained by any rule.

Theorem: Suppose $V<\infty$. For any rule $\delta$ with finite maximum risk, $\Delta(\delta)\geq 0$. The rule is additive $\varepsilon$-minimax if and only if $\Delta(\delta)\leq\varepsilon$. It is exact minimax if and only if $\Delta(\delta)=0$.

Proof. By the definition of the infimum $V=\inf_{\gamma\in\mathcal{D}}M(\gamma)$, $V\leq M(\delta)$. Subtracting $V$ gives $\Delta(\delta)=M(\delta)-V\geq0$. Also,

M(\delta)\leq V+\varepsilon \quad\Longleftrightarrow\quad M(\delta)-V\leq\varepsilon \quad\Longleftrightarrow\quad \Delta(\delta)\leq\varepsilon.

Taking $\varepsilon=0$, the condition is $M(\delta)\leq V$. Together with $M(\delta)\geq V$, this is equivalent to $M(\delta)=V$, which is exactly the definition of an exact minimax rule. $\square$

For positive finite $V$, the multiplicative condition has its own gap interpretation:

M(\delta)\leq(1+\eta)V \quad\Longleftrightarrow\quad \Delta(\delta)\leq\eta V \quad\Longleftrightarrow\quad \frac{\Delta(\delta)}{V}\leq\eta.

The last quantity is the relative excess maximum risk. This equivalence also shows that multiplicative $\eta$-minimax is the same as additive $\varepsilon$-minimax with $\varepsilon=\eta V$, provided $V$ is finite. If $V=0$, the algebraic inequality still makes sense, but it allows no positive gap.

Rescaling and Comparing Approximation Criteria

A positive rescaling of the loss clarifies the difference between the two criteria. Suppose every risk is replaced by $R_c(\theta,\delta)=cR(\theta,\delta)$, where $c>0$. Then $M_c(\delta)=cM(\delta)$ and $V_c=cV$, because multiplication by a positive constant preserves the ordering of all candidate maximum risks and commutes with their supremum and infimum. It follows directly that $\Delta_c(\delta)=c\Delta(\delta)$.

Thus an additive tolerance $\varepsilon$ must also be rescaled to $c\varepsilon$ to describe the same approximation. For $V>0$, however, the relative gap is unchanged: $\Delta_c(\delta)/V_c=c\Delta(\delta)/(cV)=\Delta(\delta)/V$. This is useful when losses are reported in different units, but relative comparisons still require a meaningful positive benchmark. When $V=0$, the ratio is undefined and the multiplicative condition collapses to exact minimaxity.

Why the Distinction Matters

The minimax value is an optimal benchmark; the gap says how far a particular rule’s worst-case risk is above it. This is a rule-specific comparison. It should not be confused with a minimax-interchange gap, which compares $\inf_\delta\sup_\theta R(\theta,\delta)$ with a reversed or randomized optimization, such as a supremum over priors of a corresponding Bayes risk. The two quantities answer different questions: one evaluates a rule against the minimax benchmark, while the other concerns whether two optimization orders have equal values.

A common mistake is to call a rule “within five percent of minimax” without checking that the minimax value is positive. If $V>0$, this phrase can be made precise as $M(\delta)\leq1.05V$. If $V=0$, that condition demands $M(\delta)=0$; it does not permit a small positive excess. In a zero-value problem, report an additive tolerance in the loss units instead. A second mistake is to infer exact attainment merely because the value $V$ is finite: finiteness defines a benchmark, but does not by itself show that a rule has gap zero.

Key takeaway: For a rule $\delta$, the maximum-risk gap $M(\delta)-V$ is its excess worst-case risk over the minimax benchmark. Additive approximation bounds this gap directly; multiplicative approximation bounds it relative to $V$ and is useful only when that benchmark is positive.

Check Your Understanding

Use the definitions and calculations above to answer these questions.

Why does every rule with finite maximum risk have a nonnegative maximum-risk gap?
A problem has $V=12$, and a rule has $M(\delta)=13.2$. What is its gap, and what is the smallest $\eta$ for which it is multiplicative $\eta$-minimax?
If all losses are multiplied by $c>0$, how do the minimax value, maximum-risk gap, and relative gap change?
Why does multiplicative $\eta$-minimaxity with $V=0$ require exact minimaxity?
In one sentence, distinguish a rule’s maximum-risk gap from a minimax-interchange gap.