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 245–344 of 725. Source text is displayed literally.
245\end{figure}246 247\subsection{Naturality}248 249\begin{definition}250A family of learners, one for each finite set $S$, is \term{natural} for a class of payoff-preserving maps if251for every $f\colon(S,A)\to(T,B)$ in the class, $f_*$ carries self-play trajectories in $\Dist(S)$ to self-play252trajectories in $\Dist(T)$.253\end{definition}254 255\noindent Naturality for inclusions says that an action never tried is never missed, and the rest behaves as256if it did not exist. Naturality for clone maps says that listing an action twice, or splitting it into257indistinguishable variants, changes nothing about the total weight of the variants. Naturality for symmetries258is equivariance.259 260\begin{theorem}[Which learners are natural]\label{thm:natural}261\Sob262\begin{enumerate}[label=(\alph*),leftmargin=1.5em,itemsep=1pt,topsep=2pt]263\item \emph{(R)} and \emph{(H)} are natural for all payoff-preserving maps.264\item \emph{(PG)} is natural for inclusions and symmetries and not for clone maps. If an action of total265probability $y$ is split into copies with probabilities $x_1,\dots,x_k$, the leading term of its drift is266$\sum_cx_c^2$ where the unsplit learner has $y^2$.267\item In the two-action problem of \Cref{prop:escape}, with either action split into $k$ equal copies, the268probability $y$ of the better class obeys $\dot y=(1+\tfrac1k)Dy^2(1-y)^2$. Every learning time is multiplied269by exactly $2k/(k+1)$.270\item \emph{(Q)} is natural for symmetries and not for clone maps. Its rest points are the logit equilibria271$x=\sm(Ax/\tau)$, which depend on the number of copies of each action, and every face of the simplex is272repelling: no action stays unused.273\end{enumerate}274\end{theorem}275\begin{proof}276(a) For (R), with $y=f_*x$, the pushforward identity gives277$\dot y_t=\sum_{f(i)=t}x_i((Ax)_i-x^{\T}Ax)=y_t((By)_t-y^{\T}By)$ for $t$ in the image and $y_t\equiv0$ otherwise.278(H) is a time-$\eta$ map of the same flow with frozen payoffs, and frozen payoffs are also preserved.279(b) In \eqref{eq:pgx} the factor $x_i$ gives invariance of faces. Summing \eqref{eq:pgx} over the copies of280one action gives $(\sum_cx_c^2)(\pi-\bar\pi)-y\sum_jx_j^2(\pi_j-\bar\pi)$, and $\sum_cx_c^2<y^2$ unless all but one281copy 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