Pure and Mixed Strategies in Finite Decision Problems

From Individual Choices to Randomized Choices

In a finite statistical decision problem, the statistician chooses a decision rule and nature chooses a parameter value. A pure strategy makes one choice with certainty. A mixed strategy assigns probabilities to the available pure choices. These probabilities let us describe randomized behavior precisely, without confusing it with the uncertainty already present in the data.

The central calculation is an average: if a decision rule is selected at random, its expected loss is the probability-weighted average of the risks of the rules it could select. If nature also randomizes over parameter values, the expected loss averages over both choices. The calculations below focus on these expectations, not on determining an optimal strategy.

Definition: Let \(\Theta=\{\theta_1,\ldots,\theta_m\}\) be a finite parameter set and let \(\mathcal{D}=\{\delta_1,\ldots,\delta_k\}\) be a finite set of measurable decision rules. Write \(R(\theta_i,\delta_j)=E_{\theta_i}[L(\theta_i,\delta_j(X))]\) for the risk of rule \(\delta_j\) at parameter \(\theta_i\), assuming the loss is measurable and this expectation exists and is finite. A pure strategy for the statistician is one rule \(\delta_j\); a mixed strategy for the statistician is a probability distribution \(q=(q_1,\ldots,q_k)\) on \(\mathcal{D}\). A pure strategy for nature is one value \(\theta_i\); a mixed strategy for nature is a probability distribution \(\pi=(\pi_1,\ldots,\pi_m)\) on \(\Theta\).

Thus \(q_j\geq 0\) and \(\sum_{j=1}^k q_j=1\), while \(\pi_i\geq 0\) and \(\sum_{i=1}^m\pi_i=1\). A mixed strategy \(q\) means that a rule is drawn according to these probabilities. A mixed strategy \(\pi\) means that a parameter value is drawn according to \(\pi\). The draw from \(q\) or \(\pi\) is a separate source of randomization from the sample \(X\).

How a Distribution over Rules Determines Risk

For a fixed parameter value, the statistician can first draw a rule \(J\) with \(P(J=j)=q_j\), independently of the data-generating mechanism, and then apply \(\delta_J\) to the observation. The expected loss is the average of the losses under the possible selected rules. Conditional on selecting rule \(j\), its expected loss is \(R(\theta,\delta_j)\). Averaging over the rule selection gives the following result.

Result: For every \(\theta\in\Theta\), the risk of the mixed strategy \(q\) is

R(\theta,q)=\sum_{j=1}^k q_j R(\theta,\delta_j).

This expectation is finite whenever the displayed sum is finite; in particular, it is finite if all the pure-rule risks in the sum are finite.

To verify the formula, let \(J\) denote the selected rule. The expected loss can be evaluated by conditioning on its finitely many possible values:

\begin{aligned} E_\theta[L(\theta,\delta_J(X))] &=\sum_{j=1}^k P(J=j)\, E_\theta[L(\theta,\delta_J(X))\mid J=j]\\ &=\sum_{j=1}^k q_j E_\theta[L(\theta,\delta_j(X))]\\ &=\sum_{j=1}^k q_j R(\theta,\delta_j). \end{aligned}

The second equality uses that selecting rule \(j\) leaves the sampling distribution at \(\theta\) unchanged. The finite sum needs no interchange of an infinite limit and an expectation.

The formula also shows that risk is affine in the mixing probabilities. For example, if \(q\) and \(q'\) are two distributions over rules and \(0\leq \lambda\leq 1\), then the distribution \(q''=\lambda q+(1-\lambda)q'\) satisfies \(R(\theta,q'')=\lambda R(\theta,q)+(1-\lambda)R(\theta,q')\). This follows by substituting \(q''_j=\lambda q_j+(1-\lambda)q'_j\) into the finite sum. Mixing therefore averages risks; it does not introduce an extra interaction term.

Worked Example: Mixing Two Constant Classification Rules

Suppose \(\Theta=\{0,1\}\), and the loss is zero for a correct classification and one for an incorrect classification. The rule \(\delta_0\) always reports 0, and \(\delta_1\) always reports 1. The risks are \(R(0,\delta_0)=0\), \(R(1,\delta_0)=1\), \(R(0,\delta_1)=1\), and \(R(1,\delta_1)=0\).

Let the statistician choose \(\delta_0\) with probability \(q_0=0.25\) and \(\delta_1\) with probability \(q_1=0.75\). At parameter value 0, the mixed risk is

$$ R(0,q)=0.25(0)+0.75(1)=0.75. $$

At parameter value 1, it is

$$ R(1,q)=0.25(1)+0.75(0)=0.25. $$

Now let nature use the distribution \(\pi_0=0.6,\ \pi_1=0.4\). Averaging the two parameter-specific risks gives expected loss

$$ 0.6(0.75)+0.4(0.25)=0.45+0.10=0.55. $$

The calculation averages first over which rule is selected and then over which parameter is selected. Reversing the order gives the same finite weighted sum.

Mixing over Parameter Values and Combining Both Sides

A probability distribution \(\pi\) on the finite parameter set is a prior distribution. For a fixed rule \(\delta_j\), its expected loss when \(\theta\) is drawn from \(\pi\) is the prior-averaged risk, often called the Bayes risk of that rule under \(\pi\):

r(\pi,\delta_j)=\sum_{i=1}^m \pi_i R(\theta_i,\delta_j).

This expression averages the risk over possible parameter values. It is not the risk at an “average parameter”; in general, parameters do not combine that way, and loss need not be linear in the parameter.

If the statistician and nature randomize independently, the probability of selecting the pair \((\theta_i,\delta_j)\) is \(\pi_i q_j\). Consequently the joint expected loss is

Result: For independent mixed strategies \(\pi\) and \(q\), the expected loss is

\mathcal{L}(\pi,q)= \sum_{i=1}^m\sum_{j=1}^k \pi_iq_jR(\theta_i,\delta_j).

It can equivalently be calculated by averaging the mixed-strategy risk over \(\pi\), or by averaging each rule’s prior risk over \(q\).

Indeed, conditioning on the selected parameter first gives \(\sum_i\pi_i R(\theta_i,q)\). Substituting the risk formula proved above yields

\sum_{i=1}^m\pi_i\sum_{j=1}^k q_jR(\theta_i,\delta_j) =\sum_{i=1}^m\sum_{j=1}^k\pi_iq_jR(\theta_i,\delta_j).

Alternatively, grouping the same finite terms by rule gives \(\sum_jq_j r(\pi,\delta_j)\). The two ways of grouping the terms agree because both calculate the expectation under the same independent random choices.

Worked Example: Mixing Rules That Use an Observation

Let the parameter be either \(\theta_0\) or \(\theta_1\), and suppose the observation \(X\) is binary. Under \(\theta_0\), let \(P_{\theta_0}(X=1)=0.2\); under \(\theta_1\), let \(P_{\theta_1}(X=1)=0.8\). Use zero-one classification loss. Consider three rules: \(\delta_0\) always reports 0, \(\delta_1\) always reports 1, and \(\delta_X\) reports the observed value \(X\).

Under \(\theta_0\), \(\delta_0\) is always correct, so its risk is 0; \(\delta_1\) is always wrong, so its risk is 1; and \(\delta_X\) is wrong exactly when \(X=1\), so its risk is \(0.2\). Under \(\theta_1\), the corresponding risks are 1, 0, and \(P_{\theta_1}(X=0)=0.2\).

Choose \(\delta_0,\delta_1,\delta_X\) with probabilities \(0.2,0.3,0.5\), respectively. At \(\theta_0\), the mixed risk is

R(\theta_0,q)=0.2(0)+0.3(1)+0.5(0.2)=0.30+0.10=0.40.

At \(\theta_1\), it is

R(\theta_1,q)=0.2(1)+0.3(0)+0.5(0.2)=0.20+0.10=0.30.

If nature selects \(\theta_0\) with probability \(0.4\) and \(\theta_1\) with probability \(0.6\), the joint expected loss is

$$ 0.4(0.40)+0.6(0.30)=0.16+0.18=0.34. $$

For example, the contribution from selecting \(\delta_X\) is \(0.5[0.4(0.2)+0.6(0.2)]=0.10\); the contributions from \(\delta_0\) and \(\delta_1\) are \(0.2[0.4(0)+0.6(1)]=0.12\) and \(0.3[0.4(1)+0.6(0)]=0.12\). Their sum is \(0.34\), checking the calculation by grouping first by rule.

Randomizing Among Rules Is Not Averaging Their Actions

A mixed strategy over rules means selecting one rule at random, then using that rule. It does not usually mean averaging the actions the rules would take. With nonlinear loss, these operations can have different expected losses. The distinction matters even when every rule is a simple estimator.

Worked Example: Randomized Estimates Under Squared-Error Loss

Let \(\Theta=\{0,2\}\), use squared-error loss \(L(\theta,a)=(a-\theta)^2\), and consider three constant estimators with actions 0, 1, and 2. At \(\theta=0\), their risks are \(0^2=0\), \(1^2=1\), and \(2^2=4\). At \(\theta=2\), their risks are \(2^2=4\), \(1^2=1\), and \(0^2=0\).

Mix the estimators with probabilities \(0.25,0.50,0.25\), respectively. The mixed risk at \(\theta=0\) is

$$ 0.25(0)+0.50(1)+0.25(4)=0+0.50+1=1.50. $$

At \(\theta=2\), the calculation is

$$ 0.25(4)+0.50(1)+0.25(0)=1+0.50+0=1.50. $$

If instead one replaces the random selected estimate by its average action, that action is \(0.25(0)+0.50(1)+0.25(2)=1\). The constant estimator reporting 1 has squared-error risk \((1-0)^2=1\) at \(\theta=0\) and \((1-2)^2=1\) at \(\theta=2\). Thus the averaged action has risk 1 at each parameter, whereas the randomized estimator has risk 1.5 at each parameter. These are different procedures, and neither calculation can be substituted for the other without justification.

What the Expected-Loss Calculation Does—and Does Not—Say

The finite-sum formulas make strategy randomization concrete. A pure strategy is represented by a distribution concentrated on one choice; a mixed strategy distributes probability across choices. The expected loss is then an average of the risks associated with the pure choices. This description is useful whenever a decision problem is treated as a zero-sum game, because it keeps the statistician’s randomization and nature’s uncertainty in one consistent calculation.

The formulas alone do not say which distribution should be chosen, whether randomization improves a particular objective, or whether two ways of optimizing expected loss can be interchanged. Those are further questions. Here, the essential bookkeeping is to specify the available pure strategies, the probabilities assigned to them, and the risk of each pure strategy at each parameter value.

State what is randomized. A distribution over rules selects a rule; a distribution over parameters represents uncertainty or a mixed choice by nature.
Average risks with the stated probabilities. For a mixed rule, weight each pure-rule risk by its selection probability.
Use joint weights only when independence is assumed. The product \(\pi_iq_j\) is the probability of a parameter-rule pair under independent choices.

Common pitfall: It is incorrect to claim that a mixed rule’s risk is the risk of the probability-weighted average of its actions. That treats a random selected rule as if it were replaced by a deterministic averaged action. The correction is to average the pure-rule risks, \(\sum_jq_jR(\theta,\delta_j)\). If one wants to analyze the averaged action instead, it defines a different procedure and its risk must be calculated under the given loss.

Check Your Understanding

Use finite weighted sums to answer each question.

In your own words, distinguish a pure strategy for the statistician from a pure strategy for nature.
A mixed strategy assigns probabilities \(0.6\) and \(0.4\) to two rules whose risks at a fixed parameter are 0.2 and 0.7. What is the mixed risk?
What additional assumption lets you assign probability \(\pi_iq_j\) to the pair consisting of parameter \(\theta_i\) and rule \(\delta_j\)?
Explain why a distribution over parameter values averages risks and does not generally amount to evaluating risk at an average parameter.
Under squared-error loss, why need the risk of a randomly selected estimator differ from the risk of the estimator that reports the average action?