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 205–304 of 725. Source text is displayed literally.

205\begin{proof}206With $x$ the probability of the better action, (R) is $\dot x=Dx(1-x)$ and, by \eqref{eq:pgx}, (PG) is207$\dot x=2Dx^2(1-x)^2$. Integrate.208\end{proof}209 210\noindent For $D=1$ and $\epsilon=0.1$, $0.01$, $0.001$ the two times are $2.20$ and $6.64$, $4.60$ and211$54.1$, $6.91$ and $506$: ratios $3.0$, $11.8$ and $73.3$. \chk{B3} The replicator learner recovers from a bad212initialization in logarithmic time and policy gradient in time of order $1/\epsilon$. In evolutionary terms (PG)213treats a rare good action as the drift game treats a neutral mutant \cite{EGHC}.214 215\subsection{Closing the loop}216 217A learner becomes a dynamical system when its input is supplied. \term{Self-play} in a symmetric game feeds218back $\pi=A\,r(z)$; for (R) this is \eqref{eq:rep}. Two learners in a bimatrix game $(A,B)$ are wired219crosswise, $\pi^1=A\,r(z^2)$ and $\pi^2=B^{\T}r(z^1)$. A league or a population on a graph is a larger diagram.220Formally, open dynamical systems are algebras for an operad of wiring diagrams \cite{SSV20,Mye21}, and a221multi-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 high