99 Learning Theory — Episode
99.1 Overview
This module develops the adaptive-episode framework for the Hedge algorithm. It introduces the notions of a loss history, learner policy, and adaptive adversary, then constructs the canonical generated episode by running the learner/adversary interaction recursively, and shows that Hedge’s tight regret bound carries over to every such adaptive episode.
99.2 Declarations
\(\texttt{LossHistory}\ N\ t\) is the type of length-\(t\) histories of loss vectors for \(N\) experts: it is the function type \(\mathrm{Fin}\, t \to \mathrm{Fin}\, N \to \mathbb {R}\), recording all loss vectors that have been revealed in the past \(t\) rounds.
Given a history \(h : \texttt{LossHistory}\ N\ t\), \(\text{\texttt{LossHistory.toLossSeq}}\ h\) coerces it to a \(\texttt{LossSeq}\ N\ t\), enabling the reuse of definitions and theorems from the pathwise Hedge formalization that are stated over finite loss sequences.
A \(\texttt{LearnerPolicy}\ N\) is a deterministic online strategy for a learner interacting with \(N\) experts: it provides a weight function \(\mathrm{weights} : (t : \mathbb {N}) \to \texttt{LossHistory}\ N\ t \to \mathrm{Fin}\, N \to \mathbb {R}\) together with proofs that the weights are nonnegative and sum to one, so that the weight vector at each round forms a valid mixed strategy.
An \(\texttt{AdaptiveAdversary}\ N\) is an online strategy for the adversary: it provides a loss-selection function \(\mathrm{loss} : (t : \mathbb {N}) \to \texttt{LossHistory}\ N\ t \to (\mathrm{Fin}\, N \to \mathbb {R}) \to \mathrm{Fin}\, N \to \mathbb {R}\) that maps the current round index, the past loss history, and the learner’s current mixed strategy to a loss vector, subject to the validity condition that every coordinate of the chosen loss vector lies in \([0, 1]\).
\(\texttt{hedgePolicy}\ N\ \eta \) is the \(\texttt{LearnerPolicy}\) that implements the Hedge algorithm with learning rate \(\eta \gt 0\): at each round \(t\) and for each loss history \(h\), the weights are given by \(\texttt{hedgeDist}\ \eta \ (\text{\texttt{LossHistory.toLossSeq}}\ h)\ t\), the exponential-weights distribution derived from the past realized losses.
\(\texttt{episodeLossNat}\ \mathrm{learner}\ \mathrm{adversary}\ t : \mathrm{Fin}\, N \to \mathbb {R}\) is the loss vector produced at round \(t\) when the learner and adversary interact adaptively: the adversary sees the prefix of losses from rounds \(0, \ldots , t-1\) and the learner’s mixed strategy for round \(t\), then returns the loss vector for round \(t\). The definition is well-founded because the recursion only refers to strictly earlier rounds.
\(\texttt{episodeLossSeq}\ T\ \mathrm{learner}\ \mathrm{adversary} : \texttt{LossSeq}\ N\ T\) is the finite loss sequence realized over \(T\) rounds by running the learner against the adaptive adversary, obtained by restricting \(\texttt{episodeLossNat}\) to the first \(T\) rounds.
An \(\texttt{Episode}\ N\ T\) packages a learner policy, an adaptive adversary, and a finite loss sequence of length \(T\) for \(N\) experts, together with a consistency proof that the stored loss sequence equals the one generated by running \(\texttt{episodeLossSeq}\ T\ \mathrm{learner}\ \mathrm{adversary}\).
\(\texttt{Episode.generated}\ \mathrm{learner}\ \mathrm{adversary}\) is the canonical \(\texttt{Episode}\ N\ T\) constructed by taking the loss sequence to be exactly \(\texttt{episodeLossSeq}\ T\ \mathrm{learner}\ \mathrm{adversary}\); the consistency condition is satisfied by reflexivity.
Fix a number of experts \(N \ge 1\) and a horizon \(T\), and let a learner policy play against an adaptive adversary over \(N\) experts. Then the episode loss sequence they generate over the first \(T\) rounds is valid: for every round \(t \lt T\) and every expert \(i\), the realized loss satisfies \(0 \le \ell _t(i) \le 1\).
Fix a number of experts \(N \ge 1\) and a number of rounds \(T\), and consider any episode for \(N\) experts over \(T\) rounds — that is, a learner policy, an adaptive adversary, and a loss sequence \(\ell \) of length \(T\) that equals the sequence generated by running that learner against that adversary. Then \(\ell \) is a valid loss sequence: for every round \(t \lt T\) and every expert \(i\), the generated loss satisfies \(0 \le \ell _t(i) \le 1\).
Fix \(N \ge 1\) experts, a horizon of \(T\) rounds, and a learning rate \(\eta \gt 0\). Let the Hedge algorithm with rate \(\eta \) — the learner policy whose round-\(t\) distribution is the exponential-weights distribution \(p_t(i) \propto \exp (-\eta L_t(i))\) built from the past realized cumulative losses — play against an arbitrary adaptive adversary, whose loss vectors have every coordinate in \([0,1]\) and may depend on the full history of losses and on the learner’s current distribution. Let \(\ell \) be the loss sequence realized over the \(T\) rounds of this interaction. Then the regret of Hedge, its cumulative expected loss minus the least cumulative loss \(L^* = \min _{i} L_T(i)\) of any single expert in hindsight, satisfies
Fix \(N \ge 1\) experts, a horizon of \(T\) rounds, and a learning rate \(\eta \gt 0\). Consider a full interaction in which the learner runs the Hedge algorithm with learning rate \(\eta \) — playing at each round \(t\) the exponential-weights distribution \(p_t(i) \propto \exp (-\eta L_t(i))\) over the experts, where \(L_t(i)\) is the cumulative loss of expert \(i\) over rounds \(0,\dots ,t-1\) — against an adaptive adversary who, having observed the past loss vectors and the learner’s current distribution, returns a loss vector with every coordinate in \([0,1]\); let \(\ell \) be the loss sequence so generated. Writing \(\widehat{L}_T = \sum _{t=0}^{T-1}\sum _{i} p_t(i)\, \ell _t(i)\) for the learner’s expected cumulative loss and \(L^\ast = \min _{i} L_T(i)\) for the loss of the best expert in hindsight, the regret satisfies