Measurable Selection for Bayes Decisions

Why Measurable Selection Matters

A pointwise decision rule chooses, for each feature value, an action with the smallest conditional risk. But a prediction rule must also be measurable: otherwise events defined by its predictions need not be measurable, and its population risk may not be well defined. The issue is not just whether a minimum exists at each feature value; it is whether the minimizing actions can be chosen in a measurable way.

Write $X$ for the feature and $A$ for the action space. Suppose $r(x,a)$ is the conditional risk of taking action $a$ when the feature is $x$. The goal is to select an action from the set of minimizers of $r(x,\cdot)$ at every $x$, while making the selected action a measurable function of $x$. Finite action sets allow a direct construction. For compact action spaces, continuity in the action and a measurable-selection theorem provide a useful sufficient condition.

Definition: For a conditional-risk function $r$, the pointwise minimizing set at $x$ is $$ \Gamma(x)=\operatorname*{arg\,min}_{a\in A} r(x,a) =\{a\in A:r(x,a)=\inf_{b\in A}r(x,b)\}. $$ A measurable selection of $\Gamma$ is a measurable function $g$ from the feature space into $A$ such that $g(x)\in\Gamma(x)$ for every $x$. Such a function is a measurable pointwise risk-minimizing prediction rule.

Here the feature space is equipped with a sigma-algebra, and measurability of an action-valued function means that the inverse image of every Borel subset of $A$ is measurable. When we discuss compact action spaces below, the feature space is standard Borel and $A$ is a compact metric space. These assumptions make the selection result precise without requiring a special coordinate system for the actions.

Finite Action Sets

Suppose $A=\{a_1,\ldots,a_k\}$ and each function $x\mapsto r(x,a_j)$ is measurable. A minimum exists because there are only finitely many risks to compare. Fix an ordering of the actions and choose the first minimizer in that ordering. The ordering resolves ties consistently.

Theorem: If $A=\{a_1,\ldots,a_k\}$ and every $r(\cdot,a_j)$ is measurable and real-valued, then choosing the lowest-index action among the minimizers defines a measurable selection.

To verify this, let $m(x)=\min_{1\leq j\leq k}r(x,a_j)$. A finite minimum of measurable real-valued functions is measurable. The set where the rule selects $a_j$ is $$ C_j=\{x:r(x,a_j)=m(x)\}\cap \bigcap_{i<j}\{x:r(x,a_i)>m(x)\}. $$ Each set in this expression is measurable, so $C_j$ is measurable. The rule is constant on each $C_j$; because the action set is finite, this proves that the rule is measurable. At every $x$, the first minimizing index exists, and the selected action attains $m(x)$. Thus it is a measurable selection. $\square$

Worked Example: Choosing Between Two Actions

Let the feature take values $x\in[0,1]$, and let the actions be $a_0$ and $a_1$. Suppose their conditional risks are $$ r(x,a_0)=1+x,\qquad r(x,a_1)=1.5. $$ Both risk functions are measurable. To find the minimizing action, compare them: $$ 1+x\leq 1.5 \quad\Longleftrightarrow\quad x\leq 0.5. $$

With the tie-breaking convention that $a_0$ is preferred in a tie, the rule is $$ g(x)= \begin{cases} a_0,&0\leq x\leq 0.5,\\ a_1,&0.5<x\leq 1. \end{cases} $$ At $x=0.5$, both risks equal $1.5$, so the chosen action is still a minimizer. The two regions on which the rule is constant are Borel sets, hence $g$ is measurable.

Compact Action Spaces

For an infinite action space, pointwise comparison of finitely many risks is no longer available. A useful sufficient condition is that the action space is compact and the conditional risk varies continuously with the action. The relevant measurable-selection result can be stated in terms of the minimizing sets.

Theorem: Let the feature space be standard Borel, let $A$ be a nonempty compact metric space, and suppose $r(x,a)$ is real-valued, measurable in $x$ for each fixed $a$, and continuous in $a$ for each fixed $x$. Then $\Gamma(x)=\operatorname*{arg\,min}_{a\in A}r(x,a)$ is nonempty and compact for every $x$, and there is a measurable function $g$ with $g(x)\in\Gamma(x)$ for every $x$.

Here is the key measurability argument. For each fixed $x$, continuity and compactness imply that $r(x,\cdot)$ attains its minimum. For any nonempty compact subset $K$ of $A$, define $m_K(x)=\min_{a\in K}r(x,a)$. A compact metric space has a countable dense subset in each compact subset $K$. By continuity, the infimum over that dense subset equals the minimum over $K$. Thus $m_K$ is measurable: it is the infimum of countably many measurable functions $x\mapsto r(x,a)$. In particular, $m_A$ is measurable.

The correspondence $\Gamma$ has nonempty compact values. To check its measurability, take an open set $U\subseteq A$. A compact metric space has a countable family of compact subsets contained in $U$ whose union is $U$. For any such compact subset $K$, $$ \Gamma(x)\cap K\ne\varnothing \quad\Longleftrightarrow\quad m_K(x)=m_A(x). $$ The forward implication holds because any minimizer in $K$ achieves the global minimum. For the reverse implication, the minimum on compact $K$ is attained, and equality with the global minimum means that a minimizer on $K$ also belongs to $\Gamma(x)$. Consequently, $\{x:\Gamma(x)\cap U\ne\varnothing\}$ is a countable union of measurable equality sets, and is measurable.

The Kuratowski–Ryll-Nardzewski measurable-selection theorem states that a correspondence from a measurable space into a Polish space has a measurable selection if it has nonempty closed values and is measurable in the sense that $\{x:\Gamma(x)\cap U\ne\varnothing\}$ is measurable for every open $U$. A compact metric space is Polish, and the preceding argument verifies these conditions for $\Gamma$. The theorem therefore supplies a measurable $g$ with $g(x)\in\Gamma(x)$ for every $x$. $\square$

Worked Example: Squared-Error Decisions on an Interval

Suppose $A=[0,1]$, the response $Y$ is conditionally Bernoulli given $X=x$, and $P(Y=1\mid X=x)=p(x)$, where $p$ is a measurable function taking values in $[0,1]$. Use squared-error loss $L(a,Y)=(a-Y)^2$. Since $Y$ is either zero or one, the conditional risk is $$ r(x,a)=p(x)(a-1)^2+\{1-p(x)\}a^2. $$ Expanding and completing the square gives $$ r(x,a)=a^2-2ap(x)+p(x) =\{a-p(x)\}^2+p(x)\{1-p(x)\}. $$

The final term does not depend on $a$, and the squared term is nonnegative. Because $p(x)\in[0,1]$, the minimizing action $a=p(x)$ belongs to $A$ and makes the squared term zero. Therefore $\Gamma(x)=\{p(x)\}$, and $g(x)=p(x)$ is measurable by the assumed measurability of $p$. In this example, the minimizer is unique, but the compact-space result does not require uniqueness.

Worked Example: Measurable Tie-Breaking in a Compact Space

Let the feature space be $[0,1]$, the action space be $A=[-1,1]$, and $q(x)=x-\tfrac12$. Consider the continuous-in-$a$ risk $$ r(x,a)=\{a^2-q(x)^2\}^2. $$ This risk is nonnegative. It equals zero exactly when $a^2=q(x)^2$. Since $|q(x)|\leq\tfrac12$, both $|q(x)|$ and $-|q(x)|$ belong to $A$; the minimizing set is $\Gamma(x)=\{-|q(x)|,|q(x)|\}$, with these two values equal when $q(x)=0$.

Choose the lower minimizer $g(x)=-|q(x)|$. The absolute value and $q$ are continuous, so $g$ is continuous and therefore measurable. Direct substitution verifies its risk: $$ r(x,g(x)) =\{|-q(x)|^2-q(x)^2\}^2 =\{q(x)^2-q(x)^2\}^2=0. $$ Thus $g(x)\in\Gamma(x)$ everywhere, including at $x=\tfrac12$, where the minimizing set contains only the action zero.

What the Conditions Do—and Do Not—Say

These conditions are sufficient conditions for measurable selection, not a claim that every conditional-risk problem must have a compact action space or a continuous risk. The finite-action result needs only measurable risks for the available actions. The compact-action result uses compactness to ensure that continuous risks attain their minima and uses measurability to ensure that the minimizing sets can be selected measurably.

In applications, $r(x,a)$ often represents a version of $E[L(a,Y)\mid X=x]$. For a finite action set, one can work with a measurable conditional risk for each action. For an uncountable action space, it is important to have a risk function with the stated measurability and continuity properties; the existence of conditional expectations for individual actions alone does not automatically establish those joint properties for every action at once.

Common Mistake: Any Pointwise Choice Is Measurable

A frequent error is to reason that, because a minimizing action can be chosen separately at every $x$, the resulting rule must be measurable. That conclusion does not follow. For example, take $A=[0,1]$ and let $r(x,a)=0$ for every $x$ and $a$. Every action minimizes the risk at every feature value. If $B$ is a non-Borel subset of the feature space, the rule that selects $1$ on $B$ and $0$ outside $B$ is pointwise minimizing but is not measurable.

The correction is to construct or establish a measurable selection, rather than merely asserting that minimizers exist pointwise. In the example, the constant rule $g(x)=0$ is a measurable selection. In a finite action set, a fixed ordering gives one explicit construction. Under the compact-space conditions, the measurable-selection theorem guarantees that at least one such rule exists.

Key takeaway: Pointwise minimization identifies which actions are optimal at each feature value; measurable selection makes those decisions into a valid prediction rule. Finite measurable risks allow a direct tie-breaking construction, while compact metric actions with measurable, continuous conditional risk allow a measurable selector.

Check Your Understanding

Answer each question by identifying the relevant condition or calculation.

For a finite action set, why does choosing the lowest-index minimizer produce a measurable rule when each action-specific risk is measurable?
In the squared-error example, verify from the completed-square expression why $a=p(x)$ minimizes the conditional risk over $[0,1]$.
State the compactness and continuity assumptions that ensure the conditional risk attains its minimum over the action space.
In the tie-breaking example, describe the minimizing set when $x=\tfrac12$ and evaluate the selected action.
Why does pointwise existence of minimizing actions not, by itself, imply that an arbitrary choice of one minimizer at each $x$ is measurable?