Pruning Dominated Actions in Finite Loss Tables

Why Prune a Finite Risk Table?

A finite decision problem can produce many candidate rules, actions, or procedures whose performance is recorded across a finite set of parameter values. A risk table makes these comparisons concrete: each row gives one candidate’s risks, and each column records its risk at one parameter value. If one row is never better than another and is strictly worse somewhere, it can be discarded when the aim is to retain the best risk trade-offs.

The central question is not merely whether some rows can be removed. It is whether pruning leaves a representative for every risk vector that cannot be improved coordinate by coordinate. Duplicate rows also need attention: they describe the same risk vector, so only one representative is needed. The argument below handles chains of deletions, including the case where a row’s duplicate is itself later removed.

Definition: Let the parameter set be \(\Theta=\{\theta_1,\ldots,\theta_m\}\), and let \(A=\{a_1,\ldots,a_k\}\) be a finite set of candidate rules or actions. Write \(r_i=(R(\theta_1,a_i),\ldots,R(\theta_m,a_i))\) for the risk vector in row \(i\). For risk vectors \(r\) and \(s\), say that \(s\) weakly dominates \(r\) if \(s_j\le r_j\) for every coordinate \(j\). Say that \(s\) strictly dominates \(r\) if it weakly dominates \(r\) and \(s_j<r_j\) for at least one coordinate. A risk vector is undominated in a given finite collection if no vector in that collection strictly dominates it. Rows with identical risk vectors are risk-equivalent.

Risk is minimized in these comparisons. In a finite problem with no data, the risk of choosing action \(a_i\) at parameter \(\theta_j\) is simply its loss \(L(a_i,\theta_j)\), so the table entries are losses. In a statistical problem, the entries are risks \(R(\theta_j,a_i)\), typically expectations of loss under the sampling distribution. The pruning argument uses only the table of risks; it does not depend on how those risks were calculated.

How Row and Column Comparisons Work

To test whether row \(s\) dominates row \(r\), compare them across every column. The row \(s\) must have no larger entry in any parameter column, and it must have a smaller entry in at least one. Comparing just one column can show that \(s\) does better at that parameter, but it does not establish dominance across the whole parameter set.

Column-wise inspection is useful for organizing the test. In each parameter column, note which rows have the smallest risk. Then compare candidate rows across the full collection of columns. The separate column minima are not themselves a row: different rows may achieve the minima in different columns. Consequently, column minima alone do not prove that one row dominates another.

Worked Example: Comparing Rows Across All Parameter Values

Consider four candidate rules and three parameter values. The entries are their risks.

Rule	\(\theta_1\)	\(\theta_2\)	\(\theta_3\)
A	4	2	5
B	3	2	4
C	2	4	3
D	2	3	3

Compare B with A coordinate by coordinate: \(3\le4\), \(2\le2\), and \(4\le5\). The inequalities are strict in the first and third coordinates, so B strictly dominates A. Compare D with C: \(2\le2\), \(3\le4\), and \(3\le3\), with a strict inequality in the second coordinate. Thus D strictly dominates C.

B and D do not dominate one another. B has lower risk than D at \(\theta_2\), since \(2<3\), but higher risk at \(\theta_1\) and \(\theta_3\), since \(3>2\) and \(4>3\). D likewise cannot dominate B because it has higher risk at \(\theta_2\). After removing A and C, the remaining rows B and D are incomparable, so neither can be removed by strict domination within this table.

The column minima are 2 at \(\theta_1\), attained by C and D; 2 at \(\theta_2\), attained by A and B; and 3 at \(\theta_3\), attained by C and D. No one row attains all three minima. The valid pruning decisions came from comparing whole rows, not from treating these separate minima as a new row.

A Safe Pruning Procedure

A pruning step may remove a row if another currently present row either has the same risk vector or strictly dominates it. Continue making such deletions until no further deletion of either type is made. Because the table is finite and every step removes a row, the procedure terminates. The rows left at the end are called the retained rows.

A deletion record helps make the guarantee precise. For every removed row, record a row that was still present when it was removed and justified the deletion: a risk-equivalent row or a strictly dominating row. That recorded row may itself be deleted later. It is therefore not enough to say that each removed row has a representative; one must trace the deletion records until reaching a row that remains.

Theorem: In a finite risk table, suppose each deletion removes a row only when a currently present row has either the same risk vector or strictly dominates it. When the procedure terminates, every original row has a retained row whose risk vector weakly dominates it. Moreover, for every risk vector that was undominated among the original rows, at least one retained row has exactly that risk vector.

Proof. Associate each deleted row with its recorded witness. If the witness is later deleted, follow its witness as well. Each link moves to a row deleted later, or to a row that is never deleted. Since there are only finitely many rows and deletion times strictly increase along links, this tracing must end at a retained row.

At each link, the next row has either the same vector or a vector that is componentwise no larger, with at least one strict coordinate in the latter case. Thus, along the full chain, the terminal retained vector is componentwise no larger than the original row’s vector. If any link was a strict domination, its strict coordinate remains strict at the end: later vectors can only stay equal or decrease in that coordinate. Therefore, either the terminal vector equals the original vector, or it strictly dominates it. This proves the first claim.

Now take a row whose risk vector was undominated among the original rows. Its deletion chain cannot contain a strict-domination link, because the terminal retained vector would then strictly dominate its original vector. Every link in the chain must therefore be an equality of risk vectors. The retained row at the end has exactly the original undominated vector. This proves the second claim. \(\square\)

Worked Example: Why Deletion Links Must Be Traced

Consider a one-parameter table with three rows having risks \(1\), \(1\), and \(0\), labelled P, Q, and R respectively. Suppose Q is first deleted as a duplicate of P. Then P is deleted because R strictly dominates it: \(0<1\).

The deletion records are Q \(\to\) P and P \(\to\) R. Following both links shows that R is the retained row and its risk \(0\) is strictly smaller than the original risks of both P and Q. The first deletion did not secure a final row equal to Q’s vector: its recorded representative, P, was later removed. The chain argument still guarantees a retained row that weakly dominates each original row.

This example also clarifies the undominated-vector claim. The vector \(1\) was not undominated in the original table, because \(0<1\). It therefore need not have a risk-equivalent representative after pruning. By contrast, an originally undominated vector cannot have a strict link in its deletion chain, so its chain must end at a retained row with exactly the same vector.

What the Final Table Represents

When deletion continues until no duplicates or strictly dominated pairs remain, the retained rows have distinct, mutually incomparable risk vectors. Together with the theorem, this means that they are precisely one representative for each undominated risk vector in the original finite table. No undominated vector has been lost, and no retained vector is strictly dominated by another original vector: if one were, the theorem’s chain would produce a retained vector that strictly dominates it, contradicting termination.

This is a statement about risk vectors, not necessarily about the labels of the rules. Different rules can have the same risk vector, and the table does not distinguish between them on the criteria being used. Keeping one of them preserves the represented risk performance. In applications, other considerations—such as simplicity or interpretability—may guide which equivalent row to retain, but those considerations do not alter the risk comparison itself.

Worked Example: Column Minima Need Not Identify a Dominator

Consider the following table, where H is an additional candidate that can be pruned.

Rule	\(\theta_1\)	\(\theta_2\)
E	0	5
F	4	1
G	3	3
H	5	5

E strictly dominates H because \(0\le5\) and \(5\le5\), with a strict inequality in the first coordinate. But E does not dominate G: although \(0\le3\), its second entry is larger, \(5>3\). F does not dominate G either, because its first entry is larger, \(4>3\), even though \(1\le3\) in the second coordinate.

G does not dominate E, since \(3>0\) in the first coordinate; it does not dominate F, since \(3>1\) in the second. E and F also fail to dominate one another: E is smaller in the first coordinate, while F is smaller in the second. Thus E, F, and G are all undominated in this table, although different rows achieve the column minima: E achieves the minimum 0 at \(\theta_1\), and F achieves the minimum 1 at \(\theta_2\). The coordinatewise minimum vector \((0,1)\) is not a row in the table. Pruning H is justified by a row comparison; inventing a row from separate column minima would not be justified.

Common Pitfalls

Checking only one parameter value. A smaller entry in one column does not imply domination. Compare the candidate rows in every column.
Confusing equality with strict domination. Identical vectors are duplicates, not strictly dominating vectors. Keep one representative if only risk performance matters.
Assuming a duplicate’s first representative survives. A duplicate can point to a row that is later deleted. Trace equality and domination links until they end at a retained row.
Combining column minima into a fictitious row. The minima may come from different candidates. A row dominates another only if that same row is no larger in every coordinate.
Claiming every original vector remains unchanged. Dominated vectors can disappear. The exact-preservation guarantee applies to undominated vectors; every other original row is guaranteed a retained vector that weakly dominates it.

Key takeaway: In a finite risk table, compare entire rows, remove duplicates or rows strictly dominated by another current row, and trace every deletion through its recorded witness. The chain ends at a retained row that weakly dominates the original; if the original vector was undominated, the retained vector must be exactly equal to it.

Check Your Understanding

Use coordinatewise comparisons and the deletion-chain argument in your answers.

What two conditions must hold for one row to strictly dominate another?
A row has risks \((2,5,1)\), and another has risks \((3,4,1)\). Does either strictly dominate the other? Show the coordinate comparison.
Why do separate minima in each parameter column not necessarily establish that one row dominates all the others?
If a row is deleted as a duplicate of another row, and that second row is later strictly dominated, what does following the deletion links guarantee?
Why must an originally undominated vector have an exactly equal retained representative, rather than merely a weakly dominating one?