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 221–320 of 725. Source text is displayed literally.
221multi-agent learning problem is a diagram together with a choice of box for each node (\Cref{fig:wiring}).222 223\begin{figure}[t]224\centering225\begin{tikzpicture}[>=Stealth,every node/.style={font=\footnotesize},scale=0.82]226\node[draw,thick,minimum width=1.25cm,minimum height=0.62cm] (p) at (0,0) {learner};227\node[draw,minimum width=0.7cm,minimum height=0.5cm] (a) at (0,-1.05) {$A$};228\draw[->] (p.east) -- ++(0.45,0) |- node[pos=0.25,right]{$x$} (a.east);229\draw[->] (a.west) -- ++(-0.75,0) |- node[pos=0.25,left]{$\pi$} (p.west);230\node at (0,-1.75) {self-play};231\begin{scope}[xshift=4.6cm]232\node[draw,thick,minimum width=0.95cm,minimum height=0.62cm] (r) at (-1.25,0) {$L_1$};233\node[draw,thick,minimum width=0.95cm,minimum height=0.62cm] (c) at (1.25,0) {$L_2$};234\node[draw,minimum width=0.7cm,minimum height=0.5cm] (a2) at (0,0.62) {$B^{\T}$};235\node[draw,minimum width=0.7cm,minimum height=0.5cm] (b2) at (0,-0.62) {$A$};236\draw[->] (r.north) |- (a2.west);237\draw[->] (a2.east) -| (c.north);238\draw[->] (c.south) |- (b2.east);239\draw[->] (b2.west) -| (r.south);240\node at (0,-1.75) {two players};241\end{scope}242\end{tikzpicture}243\caption{A game is a wiring of learners. The boxes can be changed without changing the diagram, and the244diagram without changing the boxes.}\label{fig:wiring}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}