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

181time-$\eta$ map of this flow under a payoff held constant over the step. \chk{B1}182\end{proposition}183 184\begin{proposition}[Policy gradient and its natural form]\label{prop:pg}185\Scl[\cite{Kak01,Ama98}] For $x=\sm(\theta)$, $\partial(x\cdot\pi)/\partial\theta_i=x_i(\pi_i-x\cdot\pi)$.186Multiplying this gradient by the inverse of the Fisher matrix $\operatorname{diag}(x)-xx^{\T}$, on the187tangent space, gives $\pi-(x\cdot\pi)\one$: natural policy gradient on a softmax policy is the replicator188learner. \chk{B2}189\end{proposition}190 191\noindent So (PG) differs from (R) by one factor of $x_i$ in the update of the logits. Neural Replicator192Dynamics makes exactly this change in a deep policy-gradient method, bypassing the gradient through the softmax,193and reduces to Hedge in the single-state tabular case \cite{HMO20}. In the variable $x$,194\begin{equation}\label{eq:pgx}195\text{(PG)}\qquad\dot x_i=x_i\Bigl(x_i(\pi_i-\bar\pi)-\sum_jx_j^2(\pi_j-\bar\pi)\Bigr),196\end{equation}197with $\bar\pi=x\cdot\pi$. The extra factor has a cost that is easy to state.198 199\begin{proposition}[Escape from a bad start]\label{prop:escape}200\Scl[cf.\ \cite{MXSS20}] Two actions, payoff gap $D>0$, the better action at initial probability $\epsilon$. The201time for it to reach $\tfrac12$ is202\begin{align*} t_{\mathrm R}&=\frac1D\log\frac{1-\epsilon}{\epsilon},\\203t_{\mathrm{PG}}&=\frac1{2D}\Bigl(\frac1\epsilon-\frac1{1-\epsilon}+2\log\frac{1-\epsilon}{\epsilon}\Bigr). \end{align*}204\end{proposition}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 one