A Three-State Worked Example of Class Reduction

Why Reduce a Decision Class?

In a finite decision problem, a decision rule can be compared with another by asking whether its risk is no greater at every parameter value. A rule that is worse in at least one state and never better can be removed without sacrificing performance in any state. The central work is to calculate the risks correctly: a rule that looks attractive in one state may make a necessary trade-off in another.

This tutorial works through a problem with three parameter states and four deterministic rules. The calculation will identify one dominated rule and show why the remaining rules form a complete sub-class. Here, a class is complete relative to the stated collection of rules if every rule in that collection is matched or improved, state by state, by some rule in the sub-class.

Definition: For a rule \(\delta\), its risk at parameter value \(\theta\) is \(R(\theta,\delta)=E_\theta[L(\theta,\delta(X))]\), where \(L\) is the loss and the expectation is over the distribution of the data under \(\theta\), including any randomization in the rule. With three parameter states \(\theta_1,\theta_2,\theta_3\), the risk vector is \(R(\delta)=(R(\theta_1,\delta),R(\theta_2,\delta),R(\theta_3,\delta))\). A rule \(\delta'\) dominates \(\delta\) if \(R(\theta_i,\delta')\le R(\theta_i,\delta)\) for every \(i\), with strict inequality for at least one \(i\). A sub-class is complete relative to a class if, for every rule in the full class, some rule in the sub-class has no greater risk at any parameter state.

A Three-State Decision Problem

Let the parameter space be \(\{\theta_1,\theta_2,\theta_3\}\), and let the observed data \(X\) take values 0 and 1. The observation probabilities and losses for the two possible actions, \(a\) and \(b\), are given below. The loss depends on the state and chosen action; the observation probabilities depend on the state.

Parameter state	\(P_\theta(X=1)\)	\(L(\theta,a)\)	\(L(\theta,b)\)
\(\theta_1\)	0.2	0	4
\(\theta_2\)	0.5	3	1
\(\theta_3\)	0.8	4	0

A deterministic rule specifies an action for each possible observation. Denote the four rules by \(\delta_{aa},\delta_{ab},\delta_{ba},\delta_{bb}\), where the first letter is the action when \(X=0\) and the second is the action when \(X=1\). For instance, \(\delta_{ab}\) chooses \(a\) at \(X=0\) and \(b\) at \(X=1\). To calculate risk in a state, weight each action’s loss by the probability of the observation that leads to it.

Worked Example: Calculating All Four Risk Vectors

For \(\delta_{aa}\), the action is \(a\) for either observation, so the risk is just the loss of \(a\) in each state:

R(\delta_{aa})=(0,3,4).

For \(\delta_{bb}\), the action is always \(b\), giving:

R(\delta_{bb})=(4,1,0).

For \(\delta_{ab}\), action \(a\) is chosen when \(X=0\), and \(b\) when \(X=1\). Thus the risk in state \(\theta_i\) is \((1-P_{\theta_i}(X=1))L(\theta_i,a)+P_{\theta_i}(X=1)L(\theta_i,b)\). Substitution gives

\begin{aligned} R(\theta_1,\delta_{ab})&=0.8(0)+0.2(4)=0.8,\\ R(\theta_2,\delta_{ab})&=0.5(3)+0.5(1)=2,\\ R(\theta_3,\delta_{ab})&=0.2(4)+0.8(0)=0.8. \end{aligned}

Therefore \(R(\delta_{ab})=(0.8,2,0.8)\). For \(\delta_{ba}\), action \(b\) is chosen at \(X=0\), and \(a\) at \(X=1\). Its three risks are:

\begin{aligned} R(\theta_1,\delta_{ba})&=0.8(4)+0.2(0)=3.2,\\ R(\theta_2,\delta_{ba})&=0.5(1)+0.5(3)=2,\\ R(\theta_3,\delta_{ba})&=0.2(0)+0.8(4)=3.2. \end{aligned}

The complete list is therefore \((0,3,4)\), \((0.8,2,0.8)\), \((3.2,2,3.2)\), and \((4,1,0)\), in the order \(\delta_{aa},\delta_{ab},\delta_{ba},\delta_{bb}\). Each entry is an expected loss in its corresponding state, not a loss at a single observation.

Find the Dominated Rule

Compare risk vectors coordinate by coordinate. The vector for \(\delta_{ab}\) is no greater in any coordinate than the vector for \(\delta_{ba}\):

(0.8,2,0.8)\le(3.2,2,3.2),

where vector inequality means that the inequality holds in each coordinate. The first and third coordinates are strictly smaller, so \(\delta_{ab}\) dominates \(\delta_{ba}\). Replacing \(\delta_{ba}\) by \(\delta_{ab}\) cannot increase risk in any of the three states.

The other three rules do not dominate one another. For example, \(\delta_{aa}\) has lower risk than \(\delta_{ab}\) at \(\theta_1\), but higher risk at both \(\theta_2\) and \(\theta_3\). Likewise, \(\delta_{bb}\) has lower risk than \(\delta_{ab}\) at \(\theta_3\), but higher risk at \(\theta_1\) and \(\theta_2\). These are trade-offs, not domination.

Worked Example: Checking That the Survivors Are Incomparable

After removing \(\delta_{ba}\), compare the three remaining rules. Between \(\delta_{aa}\) and \(\delta_{ab}\), the risks at \(\theta_1\) are 0 and 0.8, respectively, while the risks at \(\theta_2\) are 3 and 2. Each rule is better in at least one of these states, so neither dominates the other. Between \(\delta_{ab}\) and \(\delta_{bb}\), the risk at \(\theta_1\) is 0.8 versus 4, but at \(\theta_3\) it is 0.8 versus 0; again, neither dominates. Finally, \(\delta_{aa}\) has lower risk than \(\delta_{bb}\) at \(\theta_1\) (0 versus 4), while \(\delta_{bb}\) has lower risk at \(\theta_3\) (0 versus 4). Thus all three survivors are undominated within this four-rule class.

Why the Reduced Class Is Complete

For this problem, the deterministic class consists of exactly the four rules listed above. The sub-class \(\{\delta_{aa},\delta_{ab},\delta_{bb}\}\) contains three of them, and the omitted rule \(\delta_{ba}\) is dominated by \(\delta_{ab}\). Every rule in the original class is therefore either already in the sub-class or is improved by a rule in it. That is precisely completeness relative to the original deterministic class.

Theorem: In a finite class of rules, choose one representative for each distinct risk vector that is undominated among the class’s risk vectors. The resulting sub-class is complete relative to the original class.

To prove the result, write \(u\le v\) when every coordinate of risk vector \(u\) is no greater than the corresponding coordinate of \(v\). In a finite collection of distinct risk vectors, start with any vector \(v\). If it is dominated, move to a distinct vector \(u\le v\). If \(u\) is also dominated, move again. Each move strictly decreases at least one coordinate and never increases any coordinate, so it cannot return to an earlier vector. Because the collection is finite, the sequence must stop at an undominated vector \(w\). Along the sequence, each move was coordinatewise non-increasing, so \(w\le v\). Consequently, for every original risk vector, there is an undominated vector no greater than it. Choosing a rule representative for that vector proves completeness. If multiple rules have identical risk vectors, any one of them can serve as the representative because their risks agree in every state. \(\square\)

Worked Example: Completeness for Randomized Rules

The reduction can also cover randomized rules in this finite problem. A randomized rule assigns an action distribution at each observation. It can be represented, for risk calculations, as a mixture of the four deterministic rules: independently draw in advance which action to use at \(X=0\) and which to use at \(X=1\), using the randomized rule’s specified probabilities. The resulting random pair is one of the four deterministic rules, and its average risk equals the randomized rule’s risk because, at each observed \(x\), the action has the required distribution.

For a numerical check, consider a mixture that assigns probabilities 0.2, 0.3, 0.1, and 0.4 to \(\delta_{aa},\delta_{ab},\delta_{ba},\delta_{bb}\), respectively. A mixture’s risk is the same weighted average of the component risk vectors. Thus:

\begin{aligned} R(\theta_1)&=0.2(0)+0.3(0.8)+0.1(3.2)+0.4(4)=2.16,\\ R(\theta_2)&=0.2(3)+0.3(2)+0.1(2)+0.4(1)=1.8,\\ R(\theta_3)&=0.2(4)+0.3(0.8)+0.1(3.2)+0.4(0)=1.36. \end{aligned}

Move the probability 0.1 assigned to \(\delta_{ba}\) onto \(\delta_{ab}\). The new mixture uses only the three retained rules, and the risk changes by \(0.1(R(\delta_{ab})-R(\delta_{ba}))=(-0.24,0,-0.24)\). Its risk vector is \((1.92,1.8,1.12)\), no greater than the original vector \((2.16,1.8,1.36)\) in any state. For any randomized rule, the same replacement works: represent it as a mixture over the four rules and transfer all its \(\delta_{ba}\) weight to \(\delta_{ab}\). The class of mixtures over the three retained rules is therefore complete relative to the randomized class in this example.

A Common Pitfall

A frequent error is to declare a rule dominated because it has a larger risk in one state. That is not enough. Domination requires no greater risk in every state, with a strict improvement in at least one. In this example, \(\delta_{aa}\) has greater risk than \(\delta_{ab}\) at \(\theta_2\), but smaller risk at \(\theta_1\); neither rule dominates the other. Removing either would discard a genuine trade-off.

A reliable reduction starts with the complete risk vectors, not a single coordinate or an informal impression of which rule is “better.” Once the vectors are correct, coordinatewise comparisons show exactly which replacements preserve or improve performance throughout the parameter space.

Key takeaway: In a finite decision problem, calculate each rule’s risk at every state, remove a rule only when another is no worse in all coordinates and strictly better in at least one, and retain representatives of the undominated risk vectors. The retained class is complete for the original class.

Check Your Understanding

Use the decision problem and risk vectors above to answer the following questions.

Why is the risk of \(\delta_{ab}\) at \(\theta_3\) \(0.8\), rather than \(0\) or \(4\)?
Which coordinates establish that \(\delta_{ab}\) dominates \(\delta_{ba}\)?
Explain why the lower risk of \(\delta_{aa}\) than \(\delta_{ab}\) at \(\theta_1\) does not make \(\delta_{aa}\) dominate \(\delta_{ab}\).
State what completeness of \(\{\delta_{aa},\delta_{ab},\delta_{bb}\}\) means relative to the four deterministic rules.
In the randomized example, what happens to the risk vector when 0.1 mixture weight is transferred from \(\delta_{ba}\) to \(\delta_{ab}\)?