Let \(G\) be a finite two-player zero-sum game with \(M\) row actions and \(N \ge 1\) column actions, given by a payoff matrix \(A_{ij} \in [0,1]\), and let \(p\) be a mixed strategy for the row player, with weights \(p_i\). Write \(v(j) = \sum _i p_i A_{ij}\) for the expected payoff of \(p\) against the pure column \(j\), and let \(j^*\) be a column that minimises \(v\) over all \(N\) columns. Then \(v(j^*) \le v(j)\) for every column \(j\); that is, \(j^*\) is indeed a minimiser of the expected payoff against \(p\).

Let \(G\) be a finite two-player zero-sum game with a nonempty set of \(M\) row actions and \(N\) column actions, given by a payoff matrix \(A\) with \(0 \le A_{ij} \le 1\), and let \(q\) be a mixed strategy for the column player. For a pure row \(i\), write \(u(i) = \sum _{j} A_{ij}\, q_j\) for its expected payoff against \(q\), and let \(i^\ast \) be a row maximising \(u\). Then \(u(i) \le u(i^\ast )\) for every row \(i\).

Let \(G\) be a finite two-player zero-sum game with \(M\) row actions and \(N\) column actions, given by a payoff matrix \(A\) whose entries satisfy \(0 \le A_{ij} \le 1\), and let \(j_0, \dots , j_{T-1}\) be any sequence of column responses. Then the induced loss sequence for the row player, defined by \(\ell _t(i) = 1 - A_{i,j_t}\) for each round \(t \lt T\) and row action \(i\), is valid: every loss lies in \([0,1]\), i.e. \(0 \le \ell _t(i) \le 1\) for all \(t\) and \(i\).

Let \(G\) be a finite two-player zero-sum game with \(M \ge 1\) row actions and \(N\) column actions, given by a payoff matrix \(A\) with \(0 \le A_{ij} \le 1\), and fix a pure column action \(j\). Let \(T \gt 0\) and let \(p_0, \dots , p_{T-1}\) be probability distributions over the \(M\) row actions, each presented as non-negative weights \(p_t(i)\) summing to \(1\), and let \(\bar{p}\) be their average strategy, the mixed row strategy with weights \(\bar{p}_i = \frac{1}{T}\sum _{t=0}^{T-1} p_t(i)\). Then the expected payoff of \(\bar{p}\) against column \(j\) satisfies

Let \(G\) be a finite two-player zero-sum game with \(M\) row actions and \(N \ge 1\) column actions, and payoff matrix \(A\). Fix a row action \(i\) and a sequence of column actions \(a_0, \dots , a_{T-1}\) with \(T \gt 0\), and let \(\hat{q}\) be the associated empirical column strategy. Then the expected payoff of row \(i\) against \(\hat{q}\) equals the average payoff over the sequence:

Let \(G\) be a finite two-player zero-sum game with \(M\) row actions and \(N\) column actions, let \(\eta \in \mathbb {R}\) be a learning rate, and fix any prefix \(a_0, \dots , a_{t-1}\) of \(t\) column actions together with a row \(i\). Then the prefix Hedge weight \(w_t(i) = \exp \! \bigl(-\eta \cdot L_t(i)\bigr)\) is strictly positive, where \(L_t(i) = \sum _{s=0}^{t-1}\bigl(1 - A_{i,a_s}\bigr)\) is the prefix cumulative loss of row \(i\).

Let \(G\) be a finite two-player zero-sum game with at least one row action, fix a learning rate \(\eta \in \mathbb {R}\), and let \(a_0, \dots , a_{t-1}\) be any prefix of column actions. Then the prefix potential is strictly positive,

where \(L_t(i)\) is the prefix cumulative loss of row \(i\).

Let \(G\) be a finite two-player zero-sum game with \(M\) row actions and \(N\) column actions, given by a payoff matrix \(A\) with \(0 \le A_{ij} \le 1\), and let \(a_0, \dots , a_{T-1}\) be a sequence of column actions with each \(a_s \in \mathrm{Fin}\, N\). Fix a row action \(i \in \mathrm{Fin}\, M\) and a round \(t \in \mathrm{Fin}\, T\). Then the prefix cumulative loss of row \(i\) along the first \(t\) column actions coincides with the cumulative loss of expert \(i\) through the first \(t\) rounds of the loss sequence induced by \(G\) and \((a_s)_s\); that is,

Let \(G\) be a finite two-player zero-sum game with \(M\) row actions and \(N\) column actions, with payoff matrix \(A\), let \(\eta \in \mathbb {R}\) be a learning rate, and let \(a_0, \dots , a_{T-1}\) be a sequence of column actions, so that \(a : \mathrm{Fin}\, T \to \mathrm{Fin}\, N\). Fix a round \(t \in \mathrm{Fin}\, T\) and a row \(i \in \mathrm{Fin}\, M\). Then the prefix Hedge weight of row \(i\) at learning rate \(\eta \), computed from the length-\(t\) prefix \(a_0, \dots , a_{t-1}\) of column actions, equals the Hedge weight of expert \(i\) at time \(t\) and learning rate \(\eta \) for the loss sequence \(\ell _s(j) = 1 - A_{j, a_s}\) induced by \(G\) along \(a\); that is, both equal

Let \(G\) be a finite two-player zero-sum game with payoff matrix \(A\) having \(M\) rows and \(N\) columns, fix a learning rate \(\eta \in \mathbb {R}\), and let \(a_0, \dots , a_{T-1}\) be a sequence of \(T\) column actions. For any round \(t \lt T\), the prefix potential of \(G\) at learning rate \(\eta \) formed from the first \(t\) column actions \(a_0, \dots , a_{t-1}\) equals the Hedge potential at time \(t\) of the loss sequence \(\ell _s(i) = 1 - A_{i, a_s}\) induced on the row player by \(G\) and the full sequence of column actions; that is,

where \(L_t(i) = \sum _{s \lt t} \ell _s(i)\) is the cumulative loss of row \(i\).

Let \(G\) be a finite two-player zero-sum game with \(M \ge 1\) row actions and \(N\) column actions, fix a learning rate \(\eta \in \mathbb {R}\), and let \(a_0, \dots , a_{T-1}\) be a sequence of column actions. For any round \(t \lt T\) and any row \(i\), the weight assigned to \(i\) by the prefix Hedge mixed strategy built from the length-\(t\) prefix \(a_0, \dots , a_{t-1}\) equals the Hedge distribution value \(p_t(i)\) obtained by running abstract Hedge, at the same learning rate \(\eta \), on the loss sequence \(\ell \) induced by \(G\) and \(a\), namely \(\ell _s(i) = 1 - A_{i, a_s}\). In symbols, both sides equal \(w_t(i)/\Phi _t\), where \(w_t(i) = \exp (-\eta \sum _{s\lt t}(1 - A_{i,a_s}))\) and \(\Phi _t = \sum _{k} w_t(k)\).

Consider a finite two-player zero-sum game with \(M \ge 1\) row actions and \(N\) column actions and payoff matrix \(A\), every entry of which satisfies \(0 \le A_{ij} \le 1\), played over \(T \ge 1\) rounds. Suppose that in each round \(t\) the row player commits to a probability distribution \(p_t\) over the row actions (so \(\sum _i p_t(i) = 1\)) while the column player chooses an action \(j_t\), and that the cumulative loss regret is bounded by \(R\):

where the minimum runs over the row actions. Then the row player’s cumulative expected payoff satisfies

with the maximum taken over the row actions.

Let \(N \ge 1\) and \(T \ge 1\) be integers, and let \(f(t,j)\) be a real number for each \(t \in \{ 1,\dots ,T\} \) and each \(j \in \{ 1,\dots ,N\} \). Then averaging over \(t\) before minimising over \(j\) can only increase the value:

Let \(G\) be a finite two-player zero-sum game with \(M \ge 2\) row actions and \(N \ge 1\) column actions, with payoff matrix \((A_{ij})\) satisfying \(0 \le A_{ij} \le 1\); the row player maximises and the column player minimises. Fix an integer \(T \gt 0\) and a learning rate \(\eta \gt 0\). Then there exist a mixed row strategy \(p\) and a mixed column strategy \(q\) such that, for every pure row \(i \in \{ 1,\dots ,M\} \) and every pure column \(j \in \{ 1,\dots ,N\} \),