Compactness of Randomized Rules in Finite Experiments

Why Compactness of the Rule Space Matters

Minimax arguments often need more than a formula for risk: they need a strategy space on which limiting and optimization arguments are justified. In a finite experiment, randomization has a particularly concrete representation. At each possible observation, a rule assigns probabilities to the available actions. The collection of all such assignments is a finite product of probability simplexes, so its geometry and topology can be studied directly.

The point of this tutorial is to establish two facts precisely. First, the set of randomized rules is compact in its ordinary finite-dimensional Euclidean topology. Second, for each fixed parameter value, risk is a continuous function of the rule. These facts give useful attainment results when the parameter set is finite. They do not, by themselves, make every payoff involving an infinite supremum continuous.

Finite Experiments and Randomized Rules

Let $\Theta$ be a nonempty parameter set, and let the observation space $\mathcal X=\{x_1,\ldots,x_m\}$ and action space $\mathcal A=\{a_1,\ldots,a_k\}$ be finite and nonempty. For each $\theta\in\Theta$, write $p_\theta(x)=P_\theta(X=x)$, where $p_\theta(x)\geq 0$ and $\sum_{x\in\mathcal X}p_\theta(x)=1$. Suppose the loss $\lambda(\theta,a)$ is a finite real number for every $\theta\in\Theta$ and $a\in\mathcal A$.

Definition: A randomized rule $\delta$ assigns, to every observation $x\in\mathcal X$, a probability distribution on $\mathcal A$. Its coordinate $\delta(a\mid x)$ is the conditional probability of taking action $a$ after observing $x$. Thus, for each fixed $x$, $\delta(a\mid x)\geq 0$ for all $a$ and $\sum_{a\in\mathcal A}\delta(a\mid x)=1$.

Choose and fix an ordering $a_1,\ldots,a_k$ of the actions. At one fixed observation $x$, the vector $(\delta(a_1\mid x),\ldots,\delta(a_k\mid x))$ lies in the probability simplex $\Delta_k=\{u\in\mathbb R^k:u_j\geq 0,\ \sum_{j=1}^k u_j=1\}$. The coordinates in this vector are action probabilities at that observation; they are not probabilities indexed by different observations.

A rule chooses one such vector at each of the $m$ observations. Therefore the set of all randomized rules is $\mathcal D=\prod_{x\in\mathcal X}\Delta_k$, a subset of $\mathbb R^{mk}$. Equivalently, $\mathcal D$ is defined by the $mk$ inequalities $\delta(a_j\mid x)\geq 0$ and the $m$ equalities $\sum_{j=1}^k\delta(a_j\mid x)=1$, one equality per observation.

A nonrandomized rule is included as a special case: at each $x$, its probability vector places probability one on a single action. General points of $\mathcal D$ allow randomization separately at each observation.

Worked Example: Writing a Rule as Simplex Coordinates

Suppose there are two observations $x_1,x_2$ and three actions $a_1,a_2,a_3$. Consider a rule with action probabilities $(0.2,0.5,0.3)$ after $x_1$ and $(0,0.4,0.6)$ after $x_2$.

At $x_1$, the probabilities are nonnegative and sum to $0.2+0.5+0.3=1$, so they form a point of $\Delta_3$. At $x_2$, they also sum to $0+0.4+0.6=1$, so that vector is another point of $\Delta_3$. The rule is the ordered pair of these vectors, an element of $\Delta_3\times\Delta_3\subset\mathbb R^6$.

For example, if $x_2$ is observed, the rule assigns probability $0.4$ to $a_2$, regardless of the distribution of $X$. The sampling distribution determines how often $x_2$ occurs; the rule specifies what to do conditional on seeing it.

Compactness of the Set of Rules

Theorem: If both $\mathcal X$ and $\mathcal A$ are finite and nonempty, then the set $\mathcal D$ of randomized rules is compact in $\mathbb R^{mk}$.

Proof. Represent a rule by its $mk$ real coordinates $\delta(a_j\mid x)$. Each coordinate is between zero and one, since it is nonnegative and belongs to a probability vector whose entries sum to one. Hence $\mathcal D$ is bounded. It is also closed: each constraint $\delta(a_j\mid x)\geq 0$ defines a closed set, and each constraint $\sum_{j=1}^k\delta(a_j\mid x)=1$ defines a closed set. There are only finitely many such constraints, so their intersection $\mathcal D$ is closed. The Heine–Borel theorem in finite-dimensional Euclidean space states that a set is compact if and only if it is closed and bounded. Thus $\mathcal D$ is compact. $\square$

The same conclusion can be read as a finite-product fact: each simplex $\Delta_k$ is closed and bounded, hence compact, and a finite product of compact sets is compact. The coordinate proof makes explicit which finite-dimensional topology is being used.

Worked Example: A Convergent Sequence of Rules

Let $\mathcal X=\{+,-\}$ and $\mathcal A=\{0,1\}$. Write $q_+=\delta(1\mid +)$ and $q_-=\delta(1\mid -)$; the probabilities of action $0$ are $1-q_+$ and $1-q_-$. For even integers $n\geq 4$, define $q_{+,n}=0.2+1/n$ and $q_{-,n}=1/3+1/n$. For odd $n\geq 4$, set $q_{+,n}=0.8$ and $q_{-,n}=1/3+1/n$.

These are valid rule coordinates. For even $n\geq4$, $0.2+1/n\leq0.45$, and $1/3+1/n\leq7/12$; for odd $n\geq 5$, $q_{+,n}=0.8$ and $1/3+1/n\leq8/15$. All coordinates are in $[0,1]$, so each pair specifies a rule.

The full sequence need not converge, because $q_{+,n}$ alternates between values near $0.2$ along even indices and $0.8$ along odd indices. Along the even subsequence, however, $q_{+,n}\to0.2$ and $q_{-,n}\to1/3$. Thus this subsequence converges to the valid rule with coordinates $(q_+,q_-)=(0.2,1/3)$. This concrete behavior illustrates sequential compactness: every sequence of rules has a convergent subsequence whose limit is still a rule.

Risk as a Continuous Function of the Rule

Under rule $\delta$, the conditional expected loss after observing $x$ is $\sum_{a\in\mathcal A}\delta(a\mid x)\lambda(\theta,a)$. Averaging over the observation distribution gives the risk.

Definition: The risk of a randomized rule $\delta$ at parameter $\theta$ is $$ R(\theta,\delta)=\sum_{x\in\mathcal X}p_\theta(x)\sum_{a\in\mathcal A}\delta(a\mid x)\lambda(\theta,a). $$ For a fixed $\theta$, this is a finite real-valued function of $\delta$.

Theorem: For every fixed $\theta\in\Theta$, the map $\delta\mapsto R(\theta,\delta)$ is continuous on $\mathcal D$.

Proof. The quantities $p_\theta(x)$ and $\lambda(\theta,a)$ are fixed when $\theta$ is fixed. Expanding the finite sums gives $$ R(\theta,\delta)=\sum_{x\in\mathcal X}\sum_{a\in\mathcal A} \bigl[p_\theta(x)\lambda(\theta,a)\bigr]\delta(a\mid x). $$ This is a linear function of the $mk$ coordinates of $\delta$, with fixed real coefficients. Every linear function on a finite-dimensional Euclidean space is continuous, so its restriction to $\mathcal D$ is continuous. $\square$

The proof needs no interchange of limits and integrals: there are only finitely many observations and actions. More explicitly, if $\delta_r\to\delta$ coordinatewise, each term $p_\theta(x)\lambda(\theta,a)\delta_r(a\mid x)$ converges to its counterpart with $\delta$. A finite sum of convergent terms converges to the sum of their limits, giving $R(\theta,\delta_r)\to R(\theta,\delta)$.

Worked Example: Checking Risks and Continuity in a Binary Experiment

Let $\Theta=\{0,1\}$, let $\mathcal X=\{+,-\}$, and let $\mathcal A=\{0,1\}$. Use zero-one loss: $\lambda(\theta,a)=1$ if $a\ne\theta$, and $0$ otherwise. Suppose $P_0(+)=0.1$, $P_0(-)=0.9$, $P_1(+)=0.3$, and $P_1(-)=0.7$. Write $q_+=\delta(1\mid+)$ and $q_-=\delta(1\mid-)$.

At $\theta=0$, an error occurs when the rule chooses action $1$, so $R(0,\delta)=0.1q_++0.9q_-$. At $\theta=1$, an error occurs when the rule chooses action $0$, so $R(1,\delta)=0.3(1-q_+)+0.7(1-q_-)$. These are affine, hence continuous, functions of the two rule coordinates.

For $q_+=0.25$ and $q_-=0.75$, the calculations are $R(0,\delta)=0.1(0.25)+0.9(0.75)=0.025+0.675=0.70$, and $R(1,\delta)=0.3(0.75)+0.7(0.25)=0.225+0.175=0.40$. With prior probabilities $P(\theta=0)=0.4$ and $P(\theta=1)=0.6$, the prior-weighted risk is $0.4(0.70)+0.6(0.40)=0.28+0.24=0.52$.

Attainment for a Finite Parameter Set

Compactness and continuity give an immediate useful conclusion when there are finitely many parameter values. Define the worst-case risk by $W(\delta)=\max_{\theta\in\Theta}R(\theta,\delta)$.

Theorem: If $\mathcal D$ is the randomized-rule set of a finite experiment and $\Theta$ is finite, then $W$ is continuous on $\mathcal D$ and attains its minimum there. In particular, there exists a randomized rule minimizing maximum risk.

Proof. For each $\theta\in\Theta$, the risk $R(\theta,\cdot)$ is continuous by the risk-continuity theorem. The maximum of finitely many continuous real-valued functions is continuous: for two finite vectors $(u_i)$ and $(v_i)$, $\left|\max_i u_i-\max_i v_i\right|\leq\max_i|u_i-v_i|$. Applying this inequality to the risk values at two rules proves continuity of $W$. The rule set $\mathcal D$ is nonempty and compact; it is nonempty because any fixed action can be selected with probability one at every observation. The extreme value theorem now implies that the continuous function $W$ attains its minimum on $\mathcal D$. $\square$

Worked Example: A Prior-Weighted Payoff in a Finite Model

Use the binary experiment above and the rule $q_+=0.25,\ q_-=0.75$. The risk values were $R(0,\delta)=0.70$ and $R(1,\delta)=0.40$. For prior weights $\pi(0)=0.4$ and $\pi(1)=0.6$, the prior-weighted payoff is the finite sum $B(\delta)=\sum_{\theta\in\Theta}\pi(\theta)R(\theta,\delta)$.

Substitution gives $B(\delta)=0.4R(0,\delta)+0.6R(1,\delta)=0.4(0.70)+0.6(0.40)=0.52$. More generally, substituting the risk formulas yields $$ B(\delta)=0.4(0.1q_++0.9q_-)+0.6\{0.3(1-q_+)+0.7(1-q_-)\}. $$ Collecting terms, the constant is $0.6(0.3+0.7)=0.6$, the coefficient of $q_+$ is $0.04-0.18=-0.14$, and the coefficient of $q_-$ is $0.36-0.42=-0.06$. Thus $B(\delta)=0.6-0.14q_+-0.06q_-$, a continuous affine function on the square $[0,1]^2$. In particular, the stated coordinates give $0.6-0.14(0.25)-0.06(0.75)=0.6-0.035-0.045=0.52$, in agreement with the direct calculation.

Common Pitfalls and Scope

Indexing a simplex by observations. At a fixed observation $x$, the vector is $(\delta(a_1\mid x),\ldots,\delta(a_k\mid x))$, with one coordinate for each action. The product over observations collects these separate action-probability vectors.
Using the wrong observation probabilities in a risk. The factor multiplying a conditional loss is $p_\theta(x)$ under the parameter currently being considered. For example, in the binary calculation above, the coefficient of the error after $+$ at $\theta=1$ is $P_1(+)=0.3$, not $P_1(-)=0.7$.
Assuming compactness makes every payoff continuous. Compactness is a property of the strategy space, not a regularity guarantee for an arbitrary function on it. The risk continuity proved here follows from its finite-sum formula. If one takes a supremum over infinitely many parameter values, continuity of that supremum does not follow merely from continuity of each individual risk; additional conditions are needed for stronger conclusions.
Confusing compactness with a particular optimum. Compactness alone does not say which rule is optimal. Attainment follows when the objective being optimized is also continuous (as in the finite-parameter worst-case result).

The finite representation is valuable because it makes the relevant hypotheses visible: finitely many observation and action coordinates produce a compact set, while finite sums make each fixed-parameter risk continuous. Those are concrete foundations for minimax arguments, not automatic properties of arbitrary rule spaces or payoffs.

Check Your Understanding

Answer each question using the finite-experiment definitions and results above.

If there are four observations and three actions, how many real coordinates represent a randomized rule, and how many simplex constraints require a sum of probabilities to equal one?
For a fixed observation $x$, what are the entries of the probability vector in $\Delta_k$?
Which assumptions make the proof of continuity of $R(\theta,\delta)$ a finite linear-function argument?
Why does a finite parameter set allow the maximum risk to be continuous when each fixed-parameter risk is continuous?
What additional issue arises if the worst-case payoff is a supremum over infinitely many parameter values?