Randomized Actions Under Linear Conditional Risk

Why Consider Randomized Actions?

A decision rule usually assigns an action to each observed feature value. A randomized rule instead assigns a probability distribution over actions and draws one action from that distribution. Such a rule can be useful for describing procedures that use a random seed, or for expressing a mixture of tied decisions. The question here is whether that extra freedom can reduce expected loss when the objective is conditional expected loss.

The key condition is linearity: once the feature value is fixed, the risk of a randomized action is the probability-weighted average of the risks of its possible actions. An average cannot be smaller than every value being averaged. This simple fact also gives a precise account of ties: randomization is optimal exactly when it puts probability only on actions that are already conditionally optimal.

Conditional Risks and Randomized Rules

Let $X$ denote the observed features and $Y$ the outcome to be acted upon. Suppose the available actions form a finite set $\mathcal A=\{1,\ldots,K\}$, and let $L(a,Y)$ be the loss from taking action $a$ when the outcome is $Y$. Assume the losses have finite conditional expectations. The conditional risk of a deterministic action is

r_a(X)=E[L(a,Y)\mid X], \qquad a\in\mathcal A.

A randomized decision rule specifies, for each observed $X$, probabilities $q_a(X)$ satisfying $q_a(X)\geq 0$ and $\sum_{a=1}^K q_a(X)=1$. Assume each $q_a(X)$ is a measurable function of $X$. The action is drawn according to these probabilities using randomization that, conditional on $X$, is independent of $Y$. Thus the rule uses the observed information, not the unobserved outcome, to choose its distribution over actions.

Definition: The conditional risk of a randomized rule $q$ is the conditional expected loss after drawing an action from $q(\cdot\mid X)$. Under the conditional independence and integrability conditions above, it is $$ r_q(X)=\sum_{a=1}^K q_a(X)r_a(X). $$ The overall risk is $R(q)=E[r_q(X)]$, whenever this expectation is finite.

The displayed formula follows by conditioning first on the chosen action. Conditional on $X$, action $a$ is chosen with probability $q_a(X)$, and its expected loss is $r_a(X)$. The randomization mechanism does not change the conditional distribution of $Y$ given $X$, so each action retains its original conditional risk.

The Finite-Action Result

Theorem: Suppose $\mathcal A=\{1,\ldots,K\}$ is finite and the conditional risks $r_a(X)$ are finite almost surely. For any randomized rule $q$, define $$ m(X)=\min_{1\leq a\leq K}r_a(X). $$ Then, almost surely, $$ r_q(X)\geq m(X). $$ Equality holds at a feature value exactly when $q_a(X)>0$ only for actions $a$ satisfying $r_a(X)=m(X)$. In particular, a randomized rule is conditionally optimal if and only if it assigns probability only to conditionally optimal deterministic actions.

Proof. For each action $a$, $r_a(X)-m(X)\geq 0$. Since the probabilities are nonnegative and sum to one,

r_q(X)-m(X) =\sum_{a=1}^K q_a(X)\bigl(r_a(X)-m(X)\bigr)\geq 0.

This proves the risk inequality. Each summand is nonnegative. A finite sum of nonnegative terms equals zero exactly when every term with a positive coefficient is zero. Therefore $r_q(X)=m(X)$ exactly when $q_a(X)>0$ implies $r_a(X)-m(X)=0$, which is the stated tie characterization. $\square$

This is a conditional statement at each feature value. It also implies a result for overall risk. A deterministic rule can attain $m(X)$ measurably: choose the smallest-index action attaining the minimum. To see measurability, the event that action $a$ is selected is described by finitely many comparisons among the measurable functions $r_1(X),\ldots,r_K(X)$, together with the rule that lower indices win ties. These events are measurable.

Corollary: If the overall risks are finite, the deterministic rule that selects a minimizing action at each $X$ has risk $E[m(X)]$, and no randomized rule has smaller overall risk. A randomized rule has this same overall risk if and only if it puts probability only on minimizing actions almost surely.

Proof. The theorem gives $r_q(X)-m(X)\geq 0$ almost surely, so taking expectations yields $R(q)\geq E[m(X)]$. The measurable deterministic rule just described has conditional risk $m(X)$, hence overall risk $E[m(X)]$. Finally, a nonnegative random variable has expectation zero if and only if it is zero almost surely. Apply this fact to $r_q(X)-m(X)$, then use the theorem’s equality characterization. $\square$

Worked Examples

Worked Example: Binary Classification and a Posterior Tie

Let $Y\in\{0,1\}$, with $P(Y=1\mid X=x)=0.7$, and use zero-one loss: $L(a,Y)=1$ if $a\neq Y$ and $0$ otherwise. Find the conditional risks and compare a deterministic decision with a randomized one that chooses action 1 with probability $0.4$.

If the action is 1, an error occurs when $Y=0$, so $r_1(x)=P(Y=0\mid X=x)=0.3$. If the action is 0, an error occurs when $Y=1$, so $r_0(x)=0.7$. The best deterministic action is 1, with risk $0.3$.

The randomized rule chooses action 1 with probability $0.4$ and action 0 with probability $0.6$. Its conditional risk is

$$ r_q(x)=0.4(0.3)+0.6(0.7)=0.12+0.42=0.54. $$

Thus this randomization increases risk from $0.3$ to $0.54$. At a tie, however, mixtures are harmless. If instead $P(Y=1\mid X=x)=0.5$, then $r_0(x)=r_1(x)=0.5$. Choosing either action, or mixing between them with any probability, gives conditional risk $0.5$.

Worked Example: A Cost Matrix With Two Tied Actions

Suppose the outcome has three possible values, $Y\in\{1,2,3\}$, with conditional probabilities $(0.2,0.5,0.3)$ at a given feature value. There are three actions, with losses shown below. Compute the action risks and the risk of a specified mixture.

Action	Loss if $Y=1$	Loss if $Y=2$	Loss if $Y=3$
$a_1$	0	4	2
$a_2$	3	0	2
$a_3$	2	1	1

Multiplying each loss by the probability of its outcome gives

r_{a_1}=0(0.2)+4(0.5)+2(0.3)=2.6,

r_{a_2}=3(0.2)+0(0.5)+2(0.3)=0.6+0+0.6=1.2,

r_{a_3}=2(0.2)+1(0.5)+1(0.3)=0.4+0.5+0.3=1.2.

Actions $a_2$ and $a_3$ tie for the minimum risk. A rule choosing $a_2$ with probability $0.25$ and $a_3$ with probability $0.75$ has risk

$$ 0.25(1.2)+0.75(1.2)=0.3+0.9=1.2. $$

This mixture is optimal, but it does not improve on either tied deterministic action. Any positive probability assigned to $a_1$ would raise the risk, because $a_1$ has strictly larger conditional risk.

Worked Example: Randomization Across Feature Values

Let $X\in\{L,H\}$, with $P(X=L)=0.6$ and $P(X=H)=0.4$. Let $Y\in\{0,1\}$, with $P(Y=1\mid L)=0.2$ and $P(Y=1\mid H)=0.8$. Use two classification actions, 0 and 1, with zero-one loss. Compare a deterministic conditional-risk rule with a randomized rule that chooses action 1 with probability $0.5$ at $L$ and $0.25$ at $H$.

At $L$, action 1 has risk $P(Y=0\mid L)=0.8$, while action 0 has risk $P(Y=1\mid L)=0.2$. The minimizing action is 0. At $H$, action 1 has risk $P(Y=0\mid H)=0.2$, while action 0 has risk $P(Y=1\mid H)=0.8$. The minimizing action is 1. The deterministic rule’s overall risk is therefore

$$ 0.6(0.2)+0.4(0.2)=0.12+0.08=0.20. $$

For the randomized rule, the conditional risk at $L$ is $0.5(0.8)+0.5(0.2)=0.5$. At $H$, it is $0.25(0.2)+0.75(0.8)=0.05+0.60=0.65$. Its overall risk is

$$ 0.6(0.5)+0.4(0.65)=0.30+0.26=0.56. $$

The comparison is made separately at each feature value: the optimal deterministic action is 0 at $L$ and 1 at $H$. Randomizing at either value puts positive probability on a higher-risk action, so the overall risk increases.

What the Result Does—and Does Not—Say

The result matters because it settles whether randomization is needed to minimize an ordinary expected-loss objective over a finite action set. If an action is strictly worse conditionally, including it in a randomized rule cannot help. If several actions tie, any probability distribution over those minimizers has exactly the same conditional risk. Thus nonuniqueness can remain, but it comes from ties rather than from an advantage of mixing.

A common mistake is to say that because an average can be lower than some of its terms, a randomized action might beat the best deterministic action. The correction is to compare the average with the smallest term: a weighted average of numbers is at least their minimum. Another mistake is to confuse a randomized action with a fractional action. In the argument above, the rule draws one available action; it does not create a new action by averaging action labels. The conclusion depends on the specified linear expected-loss objective and the conditional risk calculation.

The finite-action assumption also makes the minimum attainable. For more general action spaces, the infimum of deterministic risks need not be attained; in that case, one must not claim that a best deterministic action exists without additional assumptions. Within the finite setting, the result is exact: randomization cannot lower conditional risk, and ties describe all the ways it can remain optimal.

Check Your Understanding

Use the conditional-risk formula and the tie characterization to answer the following questions.

There are three actions with conditional risks $2$, $2$, and $5$. Which randomized rules attain the minimum risk?
Why is the condition that the randomizer is independent of $Y$ given $X$ important for the risk formula?
If a randomized rule has conditional risk equal to the minimum, what can be said about every action to which it assigns positive probability?
Can a randomized rule have lower overall risk than the best deterministic rule in the finite-action setting described here? Explain.
In the feature-dependent example, what would the overall risk be if the rule always chose action 0?

Action	Loss if \(Y=1\)	Loss if \(Y=2\)	Loss if \(Y=3\)
\(a_1\)	0	4	2
\(a_2\)	3	0	2
\(a_3\)	2	1	1