111 Learning Theory — Finite Minimax
111.1 Overview
This module develops finite two-player zero-sum games and proves an approximate minimax theorem via the Hedge (multiplicative weights) algorithm. The main results are weak duality—showing that the row player’s mixed-strategy minimum payoff never exceeds the column player’s mixed-strategy maximum payoff—and approx_minimax, which constructs an \(\varepsilon \)-approximate saddle point for any \(\varepsilon \gt 0\) by running Hedge for sufficiently many rounds against column best responses.
111.2 Declarations
A finite two-player zero-sum game with \(M\) row actions and \(N\) column actions is a record consisting of a payoff matrix \(A : \mathrm{Fin}\, M \to \mathrm{Fin}\, N \to \mathbb {R}\) together with proofs that every entry satisfies \(0 \le A_{ij} \le 1\). The row player seeks to maximise the payoff; the column player seeks to minimise it.
A mixed strategy over \(n\) actions is a record consisting of a weight function \(w : \mathrm{Fin}\, n \to \mathbb {R}\) together with proofs that every weight is non-negative and that the weights sum to \(1\), i.e. \(w\) is a probability distribution over \(\mathrm{Fin}\, n\).
Given a game \(G\), a mixed row strategy \(p\), and a pure column \(j\), the expected payoff against column \(j\) is
Given a game \(G\), a pure row \(i\), and a mixed column strategy \(q\), the expected payoff of row \(i\) against \(q\) is
Given a game \(G\) and a mixed row strategy \(p\), bestColumn is the pure column \(j^* \in \mathrm{Fin}\, N\) that minimises \(\mathrm{payoffVsPure}(G, p, \cdot )\), chosen via the classical axiom of choice from the finite minimiser.
For any game \(G\), mixed row strategy \(p\), and pure column \(j\),
That is, the chosen column is indeed a minimiser.
Given a game \(G\) and a mixed column strategy \(q\), bestRow is the pure row \(i^* \in \mathrm{Fin}\, M\) that maximises \(\mathrm{pureVsPayoff}(G, \cdot , q)\), chosen classically from the finite maximiser.
For any game \(G\), mixed column strategy \(q\), and pure row \(i\),
For any game \(G\) and any mixed strategies \(p\) (row) and \(q\) (column),
The row player’s worst-case mixed payoff never exceeds the column player’s best-case mixed payoff.
Given a game \(G\) and a sequence of column responses \(j_0, \dots , j_{T-1}\), the induced loss sequence for the row player is \(\ell _t(i) = 1 - A_{i,j_t} \in [0,1]\). This translates a zero-sum game into the abstract loss-sequence framework used by Hedge.
The loss sequence \(G.\mathrm{toLossSeq}(\mathrm{colResponse})\) is valid, i.e. every loss lies in \([0, 1]\), because the payoffs satisfy \(0 \le A_{ij} \le 1\).
Given \(T\) distributions \(p_0, \dots , p_{T-1}\) over \(\mathrm{Fin}\, n\) (each presented as non-negative weights summing to \(1\)) and \(T \gt 0\), the average strategy is the mixed strategy with weights
The Hedge distribution at round \(t\) for learning rate \(\eta \) and loss sequence \(\ell \), packaged as a MixedStrategy by bundling the non-negativity and sum-one proofs from hedgeDist.
Given \(T \gt 0\) pure actions \(a_0, \dots , a_{T-1} \in \mathrm{Fin}\, n\), the empirical strategy is the mixed strategy assigning to each \(i\) the fraction of rounds on which action \(i\) was played:
For a game \(G\), a column \(j\), and \(T\) row distributions \(p_0, \dots , p_{T-1}\),
where \(\bar{p}\) is the average strategy.
For a game \(G\), a pure row \(i\), and a sequence of pure column actions \(a_0, \dots , a_{T-1}\),
where \(\hat{q}\) is the empirical column strategy.
Given a game \(G\), a prefix of \(t\) column actions, and a row \(i\), the prefix cumulative loss of row \(i\) is
This mirrors cumLoss from the abstract Hedge framework, expressed directly in terms of game payoffs.
The unnormalised Hedge weight of row \(i\) after seeing a prefix of column actions at learning rate \(\eta \) is
where \(L_t(i)\) is the prefix cumulative loss.
The prefix potential is the sum of prefix Hedge weights over all rows:
For any game \(G\), learning rate \(\eta \), prefix of column actions, and row \(i\), the prefix Hedge weight \(w_t(i) = \exp (-\eta L_t(i)) \gt 0\).
When \(M \ge 1\), the prefix potential \(\Phi _t \gt 0\), since it is a non-empty sum of positive terms.
The normalised Hedge distribution after a prefix of \(t\) column actions is the mixed row strategy with weights
where \(w_t(i)\) is the prefix Hedge weight and \(\Phi _t\) the prefix potential.
The sequence of column best responses generated online against Hedge: at time \(t\), given the history \(a_0, \dots , a_{t-1}\) of prior column choices, the column player responds with \(a_t = \mathrm{bestColumn}(G, p_t)\), where \(p_t\) is the prefix Hedge mixed strategy. This is defined by well-founded recursion on \(t\).
For any fixed column-action sequence \(a : \mathrm{Fin}\, T \to \mathrm{Fin}\, N\), round \(t \lt T\), and row \(i\), the prefix cumulative loss of row \(i\) along the first \(t\) actions equals the abstract cumulative loss of \(i\) in the induced loss sequence: \(\mathrm{prefixGameLoss}(\dots ) = \mathrm{cumLoss}(G.\mathrm{toLossSeq}(a), t, i)\).
The prefix Hedge weight of row \(i\) at round \(t\) equals the abstract Hedge weight \(\mathrm{hedgeWeight}(\eta , G.\mathrm{toLossSeq}(a), t, i)\) for the induced loss sequence.
The prefix potential at round \(t\) equals the abstract Hedge potential \(\mathrm{potential}(\eta , G.\mathrm{toLossSeq}(a), t)\) for the induced loss sequence.
The weight of row \(i\) in the prefix Hedge mixed strategy at round \(t\) equals the abstract Hedge distribution \(\mathrm{hedgeDist}(\eta , G.\mathrm{toLossSeq}(a), t, i)\).
Suppose the row player uses per-round distributions \(p_0, \dots , p_{T-1}\) (each summing to \(1\)) against column responses \(j_0, \dots , j_{T-1}\), and achieves cumulative loss regret at most \(R\):
Then the total payoff satisfies
For any \(f : \mathrm{Fin}\, T \to \mathrm{Fin}\, N \to \mathbb {R}\) and \(T \gt 0\),
Given a game \(G\) with \(M \ge 2\) rows, a number of rounds \(T \gt 0\), and a learning rate \(\eta \gt 0\), there exist mixed strategies \(p\) (row) and \(q\) (column) such that for all pure \(i \in \mathrm{Fin}\, M\) and \(j \in \mathrm{Fin}\, N\),
The strategies are constructed by running Hedge for \(T\) rounds, with the column player taking pure best responses, and then averaging.
For any finite zero-sum game \(G\) with \(M \ge 2\) rows and any \(\varepsilon \gt 0\), there exist mixed strategies \(p\) (row) and \(q\) (column) forming an \(\varepsilon \)-approximate saddle point: for all pure \(i \in \mathrm{Fin}\, M\) and \(j \in \mathrm{Fin}\, N\),
For any finite zero-sum game \(G\) with at least \(2\) row actions and any \(\varepsilon \gt 0\), there exist mixed strategies \(p, q\) such that for all pure \(i, j\),
This is the same guarantee as approx_minimax, stated in the \(\forall \varepsilon \gt 0, \exists p, q\) form.