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 141–240 of 725. Source text is displayed literally.
141 142\subsection{Games and their maps}143 144A \term{symmetric game} $(S,A)$ is a finite set $S$ of actions and a matrix $A\in\R^{S\times S}$; $A_{ij}$ is145the payoff of $i$ against $j$. Mixed strategies form the simplex $\Dist(S)$. A \term{payoff-preserving map}146$f\colon(S,A)\to(T,B)$ is a function with $B_{f(i)f(j)}=A_{ij}$. These are the morphisms of a category $\Game$147\cite{EGHC}. They are generated by three kinds: \emph{inclusions} of a subset of actions, \emph{clone maps},148which are surjections identifying actions with equal rows and columns, and \emph{symmetries}. A map $f$149induces the pushforward $f_*\colon\Dist(S)\to\Dist(T)$, which adds the weights of identified actions. The basic150fact is that $f_*$ preserves payoffs: $(Bf_*x)_{f(i)}=(Ax)_i$ and $(f_*x)^{\T}B(f_*x)=x^{\T}Ax$.151 152\subsection{Learners}153 154\begin{definition}155A \term{learner} on $S$ is an open dynamical system with input a payoff vector $\pi\in\R^S$, a state $z$, a156readout $x=r(z)\in\Dist(S)$, and an update: $\dot z=V(z,\pi)$ in continuous time or $z^+=U(z,\pi)$ in discrete157time.158\end{definition}159 160\noindent Five learners recur below. All read out by $\sm$, applied to $Q/\tau$ in the last case.161\begin{center}\small162\begin{tabular}{@{}lll@{}}163\toprule164learner & state & update\\165\midrule166replicator (R) & scores $z$ & $\dot z=\pi$\\167Hedge, MWU (H) & scores $z$ & $z^+=z+\eta\pi$\\168optimistic (O) & scores $z$ & $z^+=z+\eta(2\pi_t-\pi_{t-1})$\\169policy grad.\ (PG) & logits $\theta$ & $\dot\theta_i=x_i(\pi_i-x\!\cdot\!\pi)$\\170Boltzmann $Q$ (Q) & values $Q$ & $\dot Q=\alpha(\pi-Q)$\\171\bottomrule172\end{tabular}173\end{center}174\noindent (PG) is gradient ascent on expected payoff $x\cdot\pi$ in the logits; (Q) is the expected,175all-actions form of $Q$-learning with Boltzmann exploration \cite{TVL03,SaCr03}.176 177\begin{proposition}[Hedge is the replicator, sampled]\label{prop:mwu}178\Scl The replicator learner fed a payoff stream $\pi(\cdot)$ has179\[ x(t)=\sm\Bigl(\log x(0)+\textstyle\int_0^t\pi\Bigr), \]180and in the variable $x$ it obeys $\dot x_i=x_i(\pi_i-x\cdot\pi)$. One step of Hedge with step size $\eta$ is the181time-$\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};