Deterministic Restrictions and Incomplete Classes

Why the Decision Rule Class Matters

A complete-class conclusion depends on which procedures are allowed. In a finite experiment, randomized rules can mix actions after observing the data; deterministic rules cannot. That distinction matters because randomization can fill in gaps between attainable risk vectors. A geometric argument that relies on convexity for randomized rules therefore cannot automatically be transferred to a deterministic restriction.

The issue is not that deterministic rules are always inferior. For a fixed prior in a finite problem, a Bayes rule can always be chosen deterministic. Rather, deterministic risk vectors may form a nonconvex set, and a deterministic rule that is undominated among deterministic rules may be dominated by a randomized one. The distinction is essential when interpreting complete-class arguments based on risk-set geometry.

Finite Experiments and Risk Vectors

Definition: Consider a finite parameter space $\Theta$, a finite observation space $\mathcal X$, and a finite action space $\mathcal A$. The experiment specifies $P_\theta(X=x)$, and the loss of action $a$ at parameter value $\theta$ is $L(\theta,a)$. A deterministic decision rule is a function $d:\mathcal X\to\mathcal A$. A randomized decision rule is a probability kernel $q(a\mid x)$: for each observation $x$, $q(\cdot\mid x)$ is a probability distribution on $\mathcal A$. Its risk at $\theta$ is $$ R(\theta,q)=\sum_{x\in\mathcal X}P_\theta(X=x)\sum_{a\in\mathcal A}q(a\mid x)L(\theta,a). $$ The risk vector is $R(q)=(R(\theta,q):\theta\in\Theta)$.

A deterministic rule is the special case in which, for every $x$, all probability is assigned to one action $d(x)$. Thus deterministic rules are included among randomized rules, but the reverse is generally false.

Definition: A rule $q'$ weakly dominates $q$ if $R(\theta,q')\leq R(\theta,q)$ for every $\theta$. It dominates $q$ if it weakly dominates $q$ and the inequality is strict for at least one parameter value. A rule is admissible within a specified class if no rule in that class dominates it. The class must be stated: admissibility among deterministic rules is not the same as admissibility among randomized rules.

In the finite setting, say a class is complete in the exact domination sense if every rule under consideration is weakly dominated by some rule in the class. This definition makes explicit the comparison being made. A result established for the full class of randomized rules need not hold after restricting the comparison class to deterministic rules: the risk set used in its proof may have changed.

Randomization Convexifies the Risk Set

The key geometric fact is that the set of randomized risk vectors is exactly the convex hull of the deterministic risk vectors. Here a convex combination means a weighted average with nonnegative weights summing to one.

Theorem: In a finite experiment, let $\mathcal R_D$ be the set of risk vectors of deterministic rules and $\mathcal R_R$ the set of risk vectors of randomized rules. Then $$ \mathcal R_R=\operatorname{conv}(\mathcal R_D). $$ In particular, $\mathcal R_R$ is convex. The deterministic risk set $\mathcal R_D$ need not be convex.

Proof. First take two randomized rules $q_1,q_2$ and a number $t\in[0,1]$. Define $q_t(a\mid x)=tq_1(a\mid x)+(1-t)q_2(a\mid x)$. This is a probability distribution over actions for each $x$, and substitution into the risk formula gives $$ R(\theta,q_t)=tR(\theta,q_1)+(1-t)R(\theta,q_2) $$ for every $\theta$. Thus the randomized risk set is convex, and it contains every deterministic risk vector.

For the reverse inclusion, fix a randomized rule $q$. There are finitely many deterministic rules $d:\mathcal X\to\mathcal A$. Draw one such rule $D$ by independently drawing $D(x)$ from $q(\cdot\mid x)$ for each $x$. This defines a probability distribution on deterministic rules. For every parameter value, $$ E[R(\theta,D)] =\sum_{x\in\mathcal X}P_\theta(X=x)E[L(\theta,D(x))] =\sum_{x\in\mathcal X}P_\theta(X=x)\sum_{a\in\mathcal A}q(a\mid x)L(\theta,a) =R(\theta,q). $$ Therefore $R(q)$ is a convex combination of deterministic risk vectors. Both inclusions hold, proving the equality. $\square$

This result identifies exactly what the deterministic restriction removes: it may remove convex combinations of attainable risk vectors. A particular deterministic risk set can happen to be convex, or a particular conclusion may hold without convexity. The point is that convexity is guaranteed for the randomized class, not for the deterministic class.

Worked Example: A Deterministic Rule Dominated by Randomization

Suppose there is no informative observation, so a rule chooses one of three actions. There are two parameter values, $\theta_1,\theta_2$, and the actions have these loss vectors:

R(a)=(0,3),\qquad R(b)=(3,0),\qquad R(c)=(2,2).

Among deterministic rules, $c$ is not dominated. Action $a$ has risk $3>2$ at $\theta_2$, while action $b$ has risk $3>2$ at $\theta_1$. Neither of the other deterministic actions has risk no larger than $c$ at both parameter values.

Now randomize equally between $a$ and $b$. The risk vector is $$ \frac12(0,3)+\frac12(3,0)=(1.5,1.5). $$ Since $1.5<2$ at both parameter values, this randomized rule dominates $c$. Thus $c$ is admissible within the deterministic class but inadmissible within the randomized class. A deterministic admissibility conclusion cannot be carried over to the larger class without checking the comparison.

Worked Risk Calculations in an Observation Model

Worked Example: Four Deterministic Rules and Their Convex Hull

Let $\Theta=\{0,1\}$, $X\in\{0,1\}$, and suppose $P_\theta(X=\theta)=0.8$. Choose an action $a\in\{0,1\}$ and use zero-one loss, $L(\theta,a)=1$ if $a\ne\theta$ and $0$ otherwise. There are four deterministic rules.

The constant-zero rule has risk $0$ at $\theta=0$ and $0.8+0.2=1$ at $\theta=1$, so its risk vector is $(0,1)$. The constant-one rule has risk vector $(1,0)$. The rule $d(x)=x$ makes an error with probability $0.2$ at either parameter, giving $(0.2,0.2)$. The rule $d(x)=1-x$ makes an error with probability $0.8$ at either parameter, giving $(0.8,0.8)$.

For example, randomize between the constant-zero rule and $d(x)=x$, choosing each with probability $1/2$ before observing $X$. Its risk vector is $$ \frac12(0,1)+\frac12(0.2,0.2)=(0.1,0.6). $$ This is also a valid randomized kernel: at either observation, assign probability $1/2$ to action $0$ and $1/2$ to the action prescribed by $d(x)=x$. The calculation shows how a point between deterministic risk vectors is attainable by randomization, even though it is not required to correspond to any deterministic rule.

What Remains True for Bayes Rules

Although deterministic risk sets need not be convex, finite-prior Bayes optimization has a useful property: randomization cannot improve the minimum integrated risk. This follows directly from the linearity of expected loss and does not require a complete-class theorem.

Theorem: In a finite experiment with finite action space and finite losses, for every prior probability distribution $\pi$ on $\Theta$, there is a deterministic rule minimizing the integrated risk $$ r(\pi,q)=\sum_{\theta\in\Theta}\pi(\theta)R(\theta,q). $$

Proof. Substitute the risk formula and rearrange the finite sums: $$ r(\pi,q)=\sum_{x\in\mathcal X}\sum_{a\in\mathcal A}q(a\mid x)c_\pi(x,a), \qquad c_\pi(x,a)=\sum_{\theta\in\Theta}\pi(\theta)P_\theta(X=x)L(\theta,a). $$ For each fixed $x$, the values $c_\pi(x,a)$ are finitely many real numbers, so a minimizing action $a_x$ exists. For any probability distribution $q(\cdot\mid x)$, $$ \sum_{a\in\mathcal A}q(a\mid x)c_\pi(x,a)\geq \min_{a\in\mathcal A}c_\pi(x,a). $$ Choose the deterministic rule $d(x)=a_x$ at each observation. It attains this minimum separately for every $x$, and hence minimizes the sum over $x$. Therefore a deterministic Bayes rule exists. $\square$

Worked Example: A Deterministic Bayes Rule Under an Unequal Prior

Use the preceding binary observation model and zero-one loss, but take $P(\theta=1)=0.25$ and $P(\theta=0)=0.75$. At $X=1$, the joint weights for the two possible parameter values are $$ P(\theta=1,X=1)=0.25(0.8)=0.20,\qquad P(\theta=0,X=1)=0.75(0.2)=0.15. $$ Choosing action $1$ has smaller integrated loss at $X=1$, since its error weight is $0.15$, compared with $0.20$ for action $0$.

At $X=0$, the joint weights are $$ P(\theta=1,X=0)=0.25(0.2)=0.05,\qquad P(\theta=0,X=0)=0.75(0.8)=0.60. $$ Choosing action $0$ has smaller integrated loss there, since its error weight is $0.05$, compared with $0.60$ for action $1$. Thus $d(x)=x$ is a Bayes rule. Its integrated risk is $$ 0.25(0.2)+0.75(0.2)=0.05+0.15=0.20. $$ The calculation illustrates the theorem: at each observation the Bayes choice can be made as a single action, without randomization.

Common Pitfall and Practical Interpretation

Wrong reasoning: “The randomized risk set is convex, so the deterministic risk set is convex too; therefore a supporting-hyperplane or complete-class argument applies unchanged to deterministic rules.”

Correction: The theorem proves convexity only after allowing probability kernels. A deterministic rule chooses one action at each observation, so its risk vector need not include the mixtures between deterministic risk vectors. In the first worked example, the deterministic rule with risk $(2,2)$ is undominated within the deterministic set, yet the randomized risk vector $(1.5,1.5)$ dominates it. The convexity hypothesis must be checked for the actual class of procedures being studied.

It is equally important not to overstate the consequence. Lack of convexity does not prove that a particular deterministic rule fails a desired property. It means the convex-risk-set argument alone does not establish that property for the restricted class. Conversely, the finite-prior result above is not lost: a deterministic Bayes rule exists because the integrated risk is minimized action by action. The distinction is between a conclusion that follows from finite Bayes optimization and one that relies on the geometry of the full risk set.

Key takeaway: In a finite experiment, randomized risk vectors are the convex hull of deterministic risk vectors. Restricting to deterministic procedures can therefore change admissibility and invalidate convexity-based complete-class reasoning, even though a deterministic Bayes rule always exists for every finite prior.

Check Your Understanding

Use the definitions and calculations above to answer the following questions.

State the finite-experiment assumptions under which the randomized risk set equals the convex hull of the deterministic risk set.
In the three-action example, why is action $c$ admissible among deterministic rules but inadmissible when randomization is allowed?
For a randomized kernel $q(a\mid x)$, explain how independently drawing an action for each observation value produces a distribution over deterministic rules.
Why does the existence of a deterministic Bayes rule for every finite prior not imply that every deterministic admissible rule is admissible among randomized rules?
Give one reason why failure of deterministic risk-set convexity does not, by itself, prove that a specific complete-class conclusion is false.