Linear Programming for Finite Approximate Minimax Problems

Why a Finite Minimax Problem Is a Linear Program

Suppose there are finitely many possible parameter values and finitely many actions. Each parameter-action pair has a known risk. The statistician must choose a rule before knowing which parameter value is true, so the relevant criterion is the largest risk across those parameter values. Randomization matters: mixing actions can reduce this worst-case risk, and the resulting optimization can be expressed with linear constraints.

Write the parameter values as \(\theta_1,\ldots,\theta_m\), and the actions as \(a_1,\ldots,a_k\). Let \(r_{ij}\) denote the risk of taking action \(a_j\) when the parameter is \(\theta_i\). Assume all \(r_{ij}\) are finite real numbers. A randomized rule selects an action according to probabilities \(q_1,\ldots,q_k\), where \(q_j\geq 0\) and \(\sum_{j=1}^k q_j=1\). Its risk at \(\theta_i\) is the probability-weighted average of the action risks.

The minimum exists: \(\Delta_k\) is compact, and the maximum of finitely many linear functions of \(q\) is continuous. Introducing a variable \(t\) to bound every parameter-specific risk gives the primal linear program

The variables \(q_j\) describe the randomized decision rule; \(t\) is its worst-case risk bound. At an optimum, \(t\) equals the largest risk of that rule. Allowing \(t\) to be any real number is harmless: the constraints force it to be at least every risk attained by a feasible rule.

Worked Examples: Reading and Solving Risk Tables

The Dual Program: Prior Weights as Adversarial Choices

Assign nonnegative weights \(p_i\) to the parameter values, with \(\sum_i p_i=1\). These weights form a probability distribution on the finite parameter set. For a fixed rule \(q\), its risk averaged with these weights is \(\sum_i p_i\sum_j r_{ij}q_j\). The largest risk is at least this weighted average, so each such distribution gives a lower bound on the minimax value after minimizing over rules.

For fixed \(p\), the smallest weighted risk over randomized rules is the smallest weighted risk of a pure action: a mixture cannot be less than the minimum of the quantities it averages. Thus the dual program can be written as

The variable \(p_i\) is the weight on parameter value \(\theta_i\); \(v\) is a lower bound on the weighted risk of every pure action. The dual chooses the weights that make this lower bound as large as possible. In the first worked example, weights \((1/2,1/2)\) give weighted risk \(1/2\) for either action. In the second, weights \((1/3,2/3)\) give weighted risk \(2\) for either action.

The same dual program follows directly from the primal Lagrangian. Give the \(i\)th risk constraint a multiplier \(p_i\geq0\), and the equality \(\sum_jq_j=1\) a multiplier \(\lambda\in\mathbb{R}\). The Lagrangian is

For the infimum over the free variable \(t\) to be finite, \(\sum_i p_i=1\) is necessary. For the infimum over each \(q_j\geq0\) to be finite, \(\sum_i p_i r_{ij}-\lambda\geq0\) is necessary. The resulting dual objective is to maximize \(\lambda\), giving exactly the displayed dual after writing \(v=\lambda\).

Equality of the Primal and Dual Values

Here is a finite-dimensional separation argument for equality of the values. For \(q\in\Delta_k\), let \(x(q)\in\mathbb{R}^m\) have coordinates \(x_i(q)=\sum_jr_{ij}q_j\), and let \(C=\{x(q):q\in\Delta_k\}\). This is a compact convex set. By definition, \(V=\min_{x\in C}\max_i x_i\).

For any probability vector \(p\), take an \(x^*\in C\) attaining this minimum. Since \(p\) has nonnegative coordinates summing to one, \(\min_{x\in C}p\mathbin{\cdot}x\leq p\mathbin{\cdot}x^*\leq\max_i x_i^*=V\). Thus every dual objective is at most \(V\).

For the reverse inequality, fix any \(s<V\) and let \(D_s=\{y\in\mathbb{R}^m:y_i\leq s\text{ for every }i\}\). The sets \(C\) and \(D_s\) are disjoint, since every \(x\in C\) has at least one coordinate greater than \(s\). A compact convex set and a disjoint closed convex set in finite-dimensional Euclidean space can be strictly separated. Therefore there is a nonzero vector \(u\) such that

Every coordinate of \(u\) must be nonnegative: if some \(u_i<0\), sending \(y_i\) to negative infinity within \(D_s\) makes \(u\mathbin{\cdot}y\) arbitrarily large, contradicting the finite upper bound. Hence \(\sup_{y\in D_s}u\mathbin{\cdot}y=s\sum_i u_i\). Since \(u\ne0\), its coordinate sum is positive. Set \(p_i=u_i/\sum_hu_h\). Then \(p\) is a probability vector and \(\min_{x\in C}p\mathbin{\cdot}x>s\). Taking \(s\) upwards to \(V\) shows that the supremum of the dual objective is at least \(V\). The probability simplex is compact, and \(p\mapsto\min_{x\in C}p\mathbin{\cdot}x\) is continuous, so the supremum is attained. The primal minimum is attained by compactness of \(\Delta_k\) and continuity of the maximum risk. This proves equality and attainment. \(\square\)

Using the Programs to Extract Epsilon Solutions

The equality result gives a practical certificate. Any feasible primal rule \(q\) supplies an upper bound \(U=\max_i\sum_jr_{ij}q_j\) on \(V\). Any feasible dual weights \(p\) supply a lower bound \(L=\min_j\sum_i p_i r_{ij}\) on \(V\). Therefore

If \(U-L\leq\varepsilon\), then the displayed primal rule is \(\varepsilon\)-minimax, because \(U\leq L+\varepsilon\leq V+\varepsilon\). This also explains how to assess a numerical solution: verify probability constraints, calculate every parameter-specific risk, calculate the dual weighted risk of every action, and check the resulting gap. Small violations of solver constraints should be accounted for rather than silently treated as exact feasibility.

A finite risk table gives a guarantee only for the parameter values and actions it contains. If the table approximates a larger parameter space, a finite-table epsilon bound alone does not establish a bound over omitted parameter values. Such a conclusion requires an additional approximation argument that controls the omitted risks.

Common Pitfall

A frequent mistake is to read the dual weights as a prior that automatically makes every action have the same risk, or to assume that any prior yields the minimax value. Neither is guaranteed. A feasible prior supplies a lower bound, and it is least favorable only when its optimized weighted risk reaches the minimax value. Likewise, a primal rule is not certified by looking at its average risk under a chosen prior: its criterion is the largest risk across parameter values. The paired primal and dual bounds make both distinctions explicit.