109 Learning Theory — Convex Minimax Core
109.1 Overview
This module develops the core ingredients for the convex-compact minimax theorem, following Cesa-Bianchi and Lugosi Theorem 7.1 specialized to subsets of \(\mathbb {R}\). It provides the exact minimax value for finite matrix games (derived from the Hedge approximate saddle-point theorem), Jensen-type inequalities for mixed-strategy convex combinations, a sampled-game construction that bridges finite and continuous settings, and the compactness machinery (sublevel sets, finite-intersection property) needed for the infinite-dimensional direction.
109.2 Declarations
Given \(n \geq 1\), OnlineLearning.arbitraryMixedStrategy is a concrete element of \(\mathrm{MixedStrategy}(n)\) that places all probability mass on a single arbitrarily chosen action. It is used solely to witness that the type of mixed strategies is nonempty.
For a finite zero-sum game \(G\) with \(M\) row actions and \(N\) column actions, the lower value is
where the row player maximises over mixed strategies and the column player minimises over pure responses.
The upper value of \(G\) is
where the column player minimises over mixed strategies and the row player maximises over pure responses.
For any game \(G\), mixed row strategy \(p\), and pure column action \(j\), \(\mathrm{payoffVsPure}(G,p,j) \geq 0\). This follows because every entry of \(G\) is nonnegative and the mixing weights are nonnegative.
For any game \(G\), mixed row strategy \(p\), and pure column action \(j\), \(\mathrm{payoffVsPure}(G,p,j) \leq 1\). This follows because every entry of \(G\) is at most one and the mixing weights sum to one.
For any game \(G\), pure row action \(i\), and mixed column strategy \(q\), \(\mathrm{pureVsPayoff}(G,i,q) \geq 0\).
For any game \(G\), pure row action \(i\), and mixed column strategy \(q\), \(\mathrm{pureVsPayoff}(G,i,q) \leq 1\).
When \(N \geq 1\), the set \(\bigl\{ \inf _{j}\, \mathrm{payoffVsPure}(G,p,j) : p \in \Delta _M\bigr\} \) is bounded above by \(1\).
When \(M \geq 1\), the set \(\bigl\{ \sup _{i}\, \mathrm{pureVsPayoff}(G,i,q) : q \in \Delta _N\bigr\} \) is bounded below by \(0\).
For any finite zero-sum game \(G\) (with \(M,N \geq 1\)), \(v^-(G) \leq v^+(G)\).
For a finite zero-sum game \(G\) with \(M \gt 1\) rows and \(N \geq 1\) columns, the lower and upper values coincide:
The proof extracts arbitrarily good approximate saddle points from the Hedge algorithm, then passes to the limit in \(\varepsilon \).
For sets \(X, Y \subseteq \mathbb {R}\) and a payoff function \(f : \mathbb {R}\to \mathbb {R}\to \mathbb {R}\), OnlineLearning.ConvexCompactMinimaxStatement is the proposition
It is packaged as a named Prop so that intermediate lemmas can refer to it while the proof is built up incrementally.
A structure bundling the assumptions of Cesa-Bianchi–Lugosi Theorem 7.1 for \(f : \mathbb {R}\to \mathbb {R}\to \mathbb {R}\) on sets \(X, Y \subseteq \mathbb {R}\): both sets are nonempty, \(X\) is compact and convex, \(Y\) is convex, \(f(\cdot ,y)\) is continuous and convex on \(X\) for every \(y \in Y\), \(f(x,\cdot )\) is concave on \(Y\) for every \(x \in X\), and \(f\) is bounded above and below on \(X \times Y\).
If \(S \subseteq \mathbb {R}\) is convex, \(p \in \Delta _n\) is a mixed strategy, and \(x_1,\dots ,x_n \in S\), then \(\sum _{i} p_i\, x_i \in S\).
If \(g\) is convex on \(S \subseteq \mathbb {R}\), \(p \in \Delta _n\), and every \(x_i \in S\), then
If \(g\) is concave on \(S \subseteq \mathbb {R}\), \(p \in \Delta _n\), and every \(y_j \in S\), then
Given a payoff function \(f : \mathbb {R}\to \mathbb {R}\to \mathbb {R}\) with values in \([0,1]\), finite families of row points \(x : [M] \to \mathbb {R}\) and column points \(y : [N] \to \mathbb {R}\), the sampled game is the \(M\times N\) matrix game whose \((i,j)\) entry is \(f(x_i, y_j)\).
Under the same size hypotheses as OnlineLearning.finite_minimax_value, the sampled game satisfies \(v^-(\mathrm{sampledGame}) = v^+(\mathrm{sampledGame})\).
If \(f(\cdot , y_j)\) is convex on \(X\) and every \(x_i \in X\), then for any mixed row strategy \(p \in \Delta _M\),
That is, convexity in the row variable means the continuous mixed-action payoff is at most the finite-game expected payoff.
If \(f(x_i,\cdot )\) is concave on \(Y\) and every \(y_j \in Y\), then for any mixed column strategy \(q \in \Delta _N\),
Under the hypotheses OnlineLearning.ConvexCompactMinimaxHypotheses,
This is the easy direction of the minimax theorem: for every fixed \((x,y)\), \(\inf _{x'} f(x',y) \leq f(x,y) \leq \sup _{y'} f(x,y')\), and the inequality is preserved when taking \(\sup \) then \(\inf \).
For a set \(X \subseteq \mathbb {R}\), a payoff function \(f\), a column point \(y\), and a threshold \(c \in \mathbb {R}\), the minimax sublevel set is
\(\mathrm{sublevel}(X,f,y,c) \subseteq X\) for all \(f\), \(y\), \(c\).
If \(X\) is closed and \(f(\cdot ,y)\) is continuous on \(X\), then \(\mathrm{sublevel}(X,f,y,c)\) is closed.
If \(X\) is compact and \(f(\cdot ,y)\) is continuous on \(X\), then \(\mathrm{sublevel}(X,f,y,c)\) is compact (as a closed subset of a compact set).
Under OnlineLearning.ConvexCompactMinimaxHypotheses, let \(c \in \mathbb {R}\). If for every finite subset \(u \subseteq Y\) there exists \(x \in X\) with \(f(x,y) \leq c\) for all \(y \in u\), then there exists \(x \in X\) with \(f(x,y) \leq c\) for all \(y \in Y\). The proof applies the finite-intersection property to the compact collection of sublevel sets.