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 165–264 of 725. Source text is displayed literally.
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};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 total