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

121\item \emph{Regret} (\Cref{sec:regret}). An identity gives regret at most $\ln n$ in continuous time; the122term that discretization adds is the one that reappears as divergence in games.123\item \emph{Recurrence} (\Cref{sec:zerosum}). In zero-sum games continuous-time learning cycles, discrete-time124learning spirals out at a computable rate, and three repairs act at three different places of the wiring125diagram.126\item \emph{Populations} (\Cref{sec:pop}). Fixation probabilities, the one-third law, and the effect of the127copying topology.128\end{itemize}129\Cref{tab:summary} lists the pairs of qualitative and quantitative statements. \Cref{sec:limits} states what130is not claimed.131 132\paragraph{Related work.} The link between reinforcement learning and replicator dynamics goes back to133\cite{BoSa97} and is surveyed in \cite{BTHK15}; the behaviour of regularized learning in zero-sum games is the134subject of \cite{PiSh14,MPP18,BaPi18}; evolutionary methods for evaluating agents are developed in135\cite{BTPG18,OPP19}. On the categorical side, learners as open systems composed along wiring diagrams follow136\cite{SSV20,Mye21}, and compositional accounts of gradient-based learning are given in \cite{FST19,CGG22}. What we137add to both is the question of naturality with respect to maps of games, which neither literature asks in this138form.139 140\section{Learners, games, and naturality}\label{sec:setting}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 a