Independent scholarship · Open accessThe monthly digest

Indexed text attachment

evolutionary-game-theory-in-machine-learning-and-ai.tex

Source for Evolutionary Game Theory in Machine Learning and AI: Naturality, Regret, and Recurrence

View paper · Download original file

Lines 281–380 of 725. Source text is displayed literally.

281copy is empty. (c) By symmetry the copies stay equal. Substituting $x_c=y/k$ for the split action in282\eqref{eq:pgx} and summing gives the stated equation in both cases; compare with $2Dy^2(1-y)^2$. (d) In the283variable $x$, (Q) in self-play is284\begin{equation}\label{eq:q}285\dot x_i=x_i\Bigl(\tfrac\alpha\tau(\pi_i-\bar\pi)-\alpha\bigl(\log x_i-\textstyle\sum_jx_j\log x_j\bigr)\Bigr),286\end{equation}287whose rest points satisfy $\log x_i=\pi_i/\tau+\mathrm{const}$. The entropy term makes $\dot x_i/x_i\to+\infty$ as288$x_i\to0$, and it distinguishes one action of weight $y$ from two of weight $y/2$, since289$2\cdot\tfrac y2\log\tfrac y2\ne y\log y$.290\end{proof}291 292\noindent \emph{Computed defects.} For Rock--Paper--Scissors with Rock duplicated, the largest discrepancy over293fifty random states between the pushed-forward field and the field of the three-action game was $4\times10^{-17}$294for (R) and $0.028$ for (PG). \chk{B19} From $\epsilon=0.01$ the policy-gradient time to $\tfrac12$ was $54.1$,295$72.1$, $86.5$ and $96.2$ for $k=1,2,4,8$, and the replicator time $4.60$ for every $k$. \chk{B20} For (Q) the296logit equilibrium of Rock--Paper--Scissors is uniform at every temperature; with Rock duplicated its mass on the297three types is $(0.49,0.29,0.23)$ at $\tau=2$, $(0.40,0.36,0.24)$ at $\tau=0.5$ and $(0.34,0.35,0.31)$ at298$\tau=0.1$. \chk{B21}299 300\begin{remark}301Large action spaces in practice contain near-duplicates: synonymous tokens, equivalent moves, redundant302members of a league. \Cref{thm:natural} says which update rules are indifferent to them. It is the303finite-dimensional shadow of the invariance of natural gradient under reparametrization \cite{Ama98}, stated for304the maps that matter in games. Entropy bonuses are the clearest case of a method that counts names: at high305temperature the regularized equilibrium gives duplicated Rock half the mass.306\end{remark}307 308\section{Regret}\label{sec:regret}309 310A learner has \term{no regret} if, against any stream of payoffs, its average payoff is asymptotically at311least that of the best fixed action. For the replicator learner this is an identity.312 313\begin{theorem}[Continuous time]\label{thm:regc}314\Scl[\cite{Sor09,KwMe17}] For the replicator learner and any bounded measurable payoff stream,315\[ \int_0^T\bigl(\pi_i-x\cdot\pi\bigr)\,dt=\log\frac{x_i(T)}{x_i(0)}\le\log\frac1{x_i(0)} \]316for every action $i$ and every horizon $T$. From the uniform initial state the regret is at most $\ln n$.317\end{theorem}318\begin{proof}319$\frac d{dt}\log x_i=\pi_i-x\cdot\pi$ by \Cref{prop:mwu}, and $x_i(T)\le1$.320\end{proof}321 322\noindent The bound does not grow with $T$. Against a stream of six payoffs that alternates between random323vectors and vectors chosen to punish the current favourite, the regret at $T=80$ was $0.24$, against324$\ln6=1.79$, and the identity held to $5\times10^{-8}$. \chk{B4}325 326\begin{theorem}[Discrete time]\label{thm:regd}327\Scl[\cite{FrSc97,CBL06}] For Hedge with payoffs in $[0,1]$ and $\eta=\sqrt{8\ln n/T}$, the regret after $T$ steps328is at most $\sqrt{T\ln n/2}$.329\end{theorem}330\begin{proof}[Sketch]331One step multiplies the normalizing constant by $\E_xe^{\eta\pi}$, and Hoeffding's lemma gives332$\log\E_xe^{\eta(\pi-x\cdot\pi)}\le\eta^2/8$. Summing, the discrete learner satisfies the identity of333\Cref{thm:regc} up to an excess of at most $\eta/8$ per step: the regret is at most $\ln n/\eta+\eta T/8$.334\end{proof}335 336\noindent Over forty runs with $n\in\{2,5,10\}$, $T\in\{200,1000\}$, half against random payoffs and half337against an adversary, the largest ratio of regret to bound was $0.50$. \chk{B5} The whole difference between338$\ln n$ and $\sqrt T$ is the term339\begin{equation}\label{eq:excess}340\Lambda_\eta(x,\pi)=\log\E_x\,e^{\eta(\pi-x\cdot\pi)}=\tfrac12\eta^2\Var_x(\pi)+O(\eta^3),341\end{equation}342the price of holding the payoff fixed for a step. The same term decides the fate of discrete learning in343games.344 345\begin{corollary}\label{cor:avg}346\Scl If both players of a zero-sum game with payoffs in an interval of length $1$ use Hedge with the step of347\Cref{thm:regd}, their time-averaged strategies form a $2\sqrt{\ln n/(2T)}$-equilibrium. In a general game the348time-averaged joint play approaches the set of coarse correlated equilibria.349\end{corollary}350 351\noindent In self-play of Rock--Paper--Scissors, whose payoffs have range $2$, the time average over352$T=20000$ steps could be exploited for $0.0015$, against the corresponding bound $0.0105$. \chk{B8}353 354\section{Zero-sum games: recurrence, divergence, repair}\label{sec:zerosum}355 356Regret bounds speak of averages. What the strategies themselves do is another matter, and it is the matter357that concerns adversarial training \cite{Goo14}, where the iterate and not the average is the model.358 359\subsection{The flow cycles}360 361\begin{theorem}[Conservation and recurrence]\label{thm:rec}362\Sli[\cite{HoSi98,PiSh14,MPP18}] Let $A$ be antisymmetric with an interior equilibrium $x^*$. Along replicator363self-play $\KL{x^*}{x(t)}$ is constant. For two replicator learners in a zero-sum game with interior equilibrium364$(x^*,y^*)$ the sum $\KL{x^*}{x}+\KL{y^*}{y}$ is constant, and the flow is Poincar\'e recurrent: almost every365trajectory returns arbitrarily close to its starting point infinitely often.366\end{theorem}367\begin{proof}[Proof of conservation]368$\frac d{dt}\KL{x^*}{x}=-\sum_ix^*_i(\pi_i-\bar\pi)=-(x^*)^{\T}Ax+x^{\T}Ax$. Antisymmetry gives $x^{\T}Ax=0$, and369$(x^*)^{\T}Ax=-x^{\T}Ax^*=0$ because $Ax^*$ is constant on the support of an interior equilibrium and that370constant is the value $0$.371\end{proof}372 373\noindent Conservation says that such a game does no work on the learner. An antisymmetric matrix has no374symmetric part, so the gradient component of the replicator field vanishes \cite{EGHC}; and when the equilibrium375is uniform the game is purely cyclic in the sense of the Hodge decomposition of \Cref{sec:eval}.376 377\subsection{The discretization spirals out}378 379\begin{proposition}[Exact drift of Hedge]\label{prop:drift}380\Srf[\cite{BaPi18}] In Hedge self-play of an antisymmetric game with interior equilibrium $x^*$, each step