Approximate Saddle Points in Risk-Prior Games

From Near-Optimal Strategies to Approximate Saddles

In a risk-prior game, the statistician chooses a decision rule to control risk across parameter values, while nature can mix parameter values according to a prior. A rule whose worst-case risk is close to the minimax value is nearly optimal for the statistician. A prior whose Bayes risk is close to that value is nearly optimal for nature. When both approximations hold, their combination has an approximate saddle property: neither player can improve the payoff much by changing strategy alone.

The two approximations play different roles. The rule gives a primal error, measured against the minimax value. The prior gives a dual error, measured by how far its Bayes risk falls below that value. Keeping these errors separate shows exactly what is needed for the saddle inequalities—and why a good rule by itself is not enough.

Values and Approximation Errors

Let \(\Theta\) be the 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 parameter \(\theta\). Assume the risk is nonnegative and measurable in \(\theta\). For a probability prior \(\pi\), write its integrated risk as \(r(\pi,\delta)\), and its Bayes risk as \(r(\pi)\). Assume the integrals and infima used below are well-defined; the selected rule and prior have finite values.

r(\pi,\delta)=\int_\Theta R(\theta,\delta)\,\pi(d\theta), \qquad r(\pi)=\inf_{\delta\in\mathcal D} r(\pi,\delta), \qquad V=\inf_{\delta\in\mathcal D}\sup_{\theta\in\Theta}R(\theta,\delta).

The value \(V\) is the primal minimax value. The dual value is \(D=\sup_\pi r(\pi)\), where the supremum is over the allowed priors. In general, do not assume that the primal and dual values are equal or that either supremum or infimum is attained. An \(\varepsilon\)-minimax rule is a rule \(\delta\) satisfying \(\sup_\theta R(\theta,\delta)\le V+\varepsilon\). A prior is within \(\eta\) of the primal value in Bayes risk if \(r(\pi)\ge V-\eta\).

Definition: For a selected rule \(\delta\) and prior \(\pi\), define the primal excess \(e_P=\sup_\theta R(\theta,\delta)-V\) and the dual deficiency \(e_D=V-r(\pi)\). When these quantities are finite, \(e_P\ge 0\) and \(e_D\ge 0\). The first measures the rule’s worst-case excess; the second measures how far the prior’s Bayes risk is below the minimax value.

The dual deficiency is nonnegative because every prior’s Bayes risk is at most \(V\). Indeed, for every rule \(\delta\), \(r(\pi)\le r(\pi,\delta)\le\sup_\theta R(\theta,\delta)\). Taking the infimum over \(\delta\) in the last bound gives \(r(\pi)\le V\). Taking the supremum over priors also shows \(D\le V\).

The Approximate Saddle Inequalities

For a fixed pair \((\delta,\pi)\), the game payoff is \(r(\pi,\delta)\): nature’s mixed strategy averages the rule’s risk, and the statistician seeks to reduce that average. The saddle inequalities compare the pair’s payoff with the payoffs after either player deviates alone. The next result bounds both comparisons using the two distinct approximation errors.

Theorem: Suppose \(\sup_\theta R(\theta,\delta)\) and \(r(\pi)\) are finite. For every parameter \(\theta\) and every rule \(\delta'\in\mathcal D\),

R(\theta,\delta)\le r(\pi,\delta)+e_P+e_D, \qquad r(\pi,\delta)\le r(\pi,\delta')+e_P+e_D.

The same first inequality holds with \(R(\theta,\delta)\) replaced by \(r(q,\delta)\) for any probability prior \(q\). In particular, if \(\delta\) is \(\varepsilon\)-minimax and \(r(\pi)\ge V-\eta\), both deviation gains are at most \(\varepsilon+\eta\).

Proof. By definition of the Bayes risk, \(r(\pi,\delta)\ge r(\pi)=V-e_D\). Also, \(r(\pi,\delta)\le\sup_\theta R(\theta,\delta)=V+e_P\). For every \(\theta\), risk is bounded by its supremum, so

R(\theta,\delta)\le V+e_P \le r(\pi,\delta)+e_P+e_D.

For any alternative rule \(\delta'\), its integrated risk is at least the infimum defining the Bayes risk. Therefore

r(\pi,\delta')\ge r(\pi)=V-e_D.

Combining this with \(r(\pi,\delta)\le V+e_P\) gives

r(\pi,\delta)\le V+e_P \le r(\pi,\delta')+e_P+e_D.

Finally, for any prior \(q\), its integrated risk \(r(q,\delta)\) is an average of values bounded above by \(\sup_\theta R(\theta,\delta)\). Thus \(r(q,\delta)\le V+e_P\), and the same lower bound \(r(\pi,\delta)\ge V-e_D\) proves the claimed inequality for \(q\). If \(e_P\le\varepsilon\) and \(e_D\le\eta\), the stated bound follows. \(\square\)

The theorem separates two possible improvements. Nature’s gain from switching to another prior is bounded using the rule’s worst-case risk and the current pair’s payoff. The statistician’s gain from switching rules is bounded using the pair’s payoff and the prior’s Bayes risk. In both comparisons the errors add, but their sources remain distinct: \(e_P\) comes from the rule and \(e_D\) from the prior.

Worked Examples

Worked Example: Two Small Errors Give a Near-Saddle Pair

There is no observation. The parameter is \(\theta\in\{0,1\}\), the action is \(0\) or \(1\), and loss is 0 for a correct action and 1 for an incorrect action. A randomized rule chooses action 1 with probability \(q\). Its risks are \(R(0,\delta)=q\) and \(R(1,\delta)=1-q\).

The worst-case risk is \(\max(q,1-q)\), which is at least \(1/2\) for every \(q\), with equality at \(q=1/2\). Hence \(V=1/2\). Take \(q=0.55\). Its worst-case risk is \(0.55\), so \(e_P=0.55-0.50=0.05\).

Let \(\pi\) assign probability \(p=0.45\) to \(\theta=1\), and probability \(0.55\) to \(\theta=0\). Choosing action 0 has prior risk \(p=0.45\); choosing action 1 has prior risk \(1-p=0.55\). Thus \(r(\pi)=0.45\) and \(e_D=0.50-0.45=0.05\). The selected rule’s integrated risk is

r(\pi,\delta)=0.55(0.55)+0.45(0.45)=0.3025+0.2025=0.505.

Nature’s best prior against this rule puts all mass on \(\theta=0\), giving payoff \(0.55\); the gain over \(0.505\) is \(0.045\). The statistician’s best response to \(\pi\) has risk \(0.45\); the gain from reducing the pair’s payoff is \(0.505-0.45=0.055\). Both are at most \(e_P+e_D=0.10\), as the theorem guarantees.

Worked Example: Exact Rule, Approximate Prior

Use the same binary decision problem, but take \(q=0.50\) and let \(\pi\) put probability \(0.40\) on \(\theta=1\). The rule has risk \(0.50\) at both parameter values, so its worst-case risk is \(V=0.50\) and \(e_P=0\).

Under \(\pi\), action 0 has risk \(0.40\), while action 1 has risk \(0.60\). Hence \(r(\pi)=0.40\), \(e_D=0.50-0.40=0.10\), and \(r(\pi,\delta)=0.50\). Nature cannot improve the payoff against this rule: every prior gives average risk \(0.50\). The statistician can reduce the pair’s payoff from \(0.50\) to \(0.40\), a gain of \(0.10\). This equals \(e_P+e_D\). The example shows that an exact minimax rule does not make an arbitrary prior a best response.

Worked Example: A Minimax Rule Need Not Have a Near-Dual Prior

Restrict the statistician to deterministic actions \(a_0,a_1\), and let \(\Theta=\{0,1\}\). The loss is 0 when the action matches the parameter and 2 otherwise. Each deterministic action has worst-case risk 2, so \(V=2\), and either action is an exact minimax rule with \(e_P=0\).

Let \(p=\pi(\theta=1)\). The prior risks of actions \(a_0\) and \(a_1\) are \(2p\) and \(2(1-p)\), respectively. Therefore

r(\pi)=\min\{2p,2(1-p)\}\le 1,

with equality at \(p=1/2\). Consequently, \(D=1\), and no prior has Bayes risk closer than 1 to \(V=2\). For the best prior, \(e_D=1\). Against that prior, either deterministic rule has payoff 1, while switching to the other action cannot reduce the prior risk below 1. But nature can choose the parameter that makes the selected deterministic action’s risk 2, increasing payoff by 1. This is consistent with the theorem’s bound \(e_P+e_D=1\); it also shows that the bound need not be small when the dual value is strictly below the primal value.

Interpreting the Error Bound

An approximate saddle pair requires evidence on both sides of the game. The condition on the rule alone controls its risk against every parameter, but does not show that the chosen prior places much weight on parameter values where that rule performs well. Conversely, a prior with high Bayes risk is informative about the difficulty of the decision problem, but it does not ensure that a particular rule is close to a best response to that prior.

The error sum gives a useful diagnostic. If the rule’s worst-case risk exceeds \(V\) by at most \(\varepsilon\), and the prior’s Bayes risk falls below \(V\) by at most \(\eta\), then neither player can improve the pair’s payoff by more than \(\varepsilon+\eta\) through a unilateral change. This statement does not assert that an exact saddle point exists, nor does it require that either optimum be attained.

Common Pitfall

A tempting but invalid argument is: “The rule is \(\varepsilon\)-minimax, so its pairing with any prior is an approximate saddle.” The rule’s risk bound only says \(r(\pi,\delta)\le V+\varepsilon\). It supplies no lower bound on the prior’s Bayes risk and therefore no guarantee that the statistician cannot substantially lower the integrated risk by switching rules. The correction is to establish a separate dual bound \(r(\pi)\ge V-\eta\). Only then does the theorem give a deviation bound of \(\varepsilon+\eta\). When \(D<V\), such a small dual error may not be available.

Key takeaway: The primal approximation controls the selected rule’s worst-case risk; the dual approximation controls the prior’s Bayes risk. Together they bound each unilateral-deviation gain by the sum of those two errors.

Check Your Understanding

Check that you can identify both approximation errors and apply the saddle inequalities.

State the definitions of the primal minimax value and the Bayes risk under a prior.
Why is every prior’s Bayes risk at most the primal minimax value?
If a rule has primal excess \(0.03\) and a prior has dual deficiency \(0.07\), what upper bound does the theorem give for either unilateral-deviation gain?
In the binary randomized example, why does an exact minimax rule paired with a prior of mass \(0.40\) on \(\theta=1\) still permit a reduction in integrated risk?
What does a strict inequality \(D<V\) imply about the possibility of finding priors with arbitrarily small dual deficiency?