189 Learning Theory — Hedge Interaction

189.1 Overview

This module runs the Hedge (multiplicative weights) algorithm for the row player of a finite zero-sum game against an online column player who always plays a best response. It introduces the loss sequence \(1 - A(i, j_t)\) induced by a column-action sequence, time-averaged and empirical strategies, and an explicit prefix-recursive bookkeeping of the Hedge weights, and shows that the resulting column response sequence is a best response to the Hedge distribution at every round.

189.2 Declarations

Lemma 189.1 Online column response is a best response

✓

Let \(G\) be a finite zero-sum game with \(M \ge 1\) row actions and \(N \ge 1\) column actions, let \(\eta \in \mathbb {R}\) be a learning rate, and let \(T\) be a horizon. Write \(j_s = \texttt{hedgeResponseNat}(G, \eta , s)\) for the online column response at round \(s\), and let \(\ell = \texttt{ZeroSumGame.toLossSeq}(G, (j_s)_{s \lt T})\) be the loss sequence it induces for the row player. Then for every round \(t \lt T\) and every fixed column \(j\),

\[ \sum _{i} \texttt{hedgeDist}(\eta , \ell , t)_i \, A(i, j_t) \; \le \; \sum _{i} \texttt{hedgeDist}(\eta , \ell , t)_i \, A(i, j), \]

i.e. the played column \(j_t\) gives the row player, mixing according to the Hedge distribution at round \(t\), no more payoff than any other column.