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 385–484 of 725. Source text is displayed literally.
385\end{proposition}386\begin{proof}387$x^+_i=x_ie^{\eta\pi_i}/Z$ with $Z=\E_xe^{\eta\pi}$, so the difference is $-\eta\,x^*\!\cdot\pi+\log Z$. As in388\Cref{thm:rec}, $x^*\!\cdot\pi=0=x\cdot\pi$, so the difference is $\log Z=\Lambda_\eta$, and Jensen's inequality389gives the sign.390\end{proof}391 392\noindent At the state $(0.5,0.3,0.2)$ of Rock--Paper--Scissors the increase per step was $5.01\times10^{-5}$,393$2.01\times10^{-4}$ and $8.08\times10^{-4}$ for $\eta=0.05$, $0.1$, $0.2$, against394$\tfrac12\eta^2\Var=5.00\times10^{-5}$, $2.00\times10^{-4}$, $8.00\times10^{-4}$. \chk{B6} With $\eta=0.1$ the395relative entropy increased at every step and some action fell below probability $0.01$ after $1451$ steps.396\chk{B7} The quantity \eqref{eq:excess} that costs a learner $\sqrt T$ in regret is, in a game, energy pumped397into the cycle at every step. The time average still converges (\Cref{cor:avg}); the iterate leaves.398 399\subsection{Three repairs, in three places}400 401\begin{proposition}[Optimism]\label{prop:opt}402\Sli[\cite{RaSr13,DISZ18,DaPa19}] The optimistic learner \emph{(O)}, which uses $2\pi_t-\pi_{t-1}$ as its403prediction of the next payoff, converges in the last iterate in zero-sum games with a unique equilibrium, for404small enough $\eta$.405\end{proposition}406 407\noindent From the same initial state and $\eta=0.1$ the relative entropy to equilibrium fell from $0.070$ to408$1.5\times10^{-10}$ in $6000$ steps. \chk{B9}409 410\begin{theorem}[Entropy regularization, with its rate]\label{thm:q}411\Sob Let $A$ be antisymmetric with the uniform state $u$ as equilibrium. Under the dynamics \eqref{eq:q},412for every $\tau>0$,413\[ \frac d{dt}\KL ux=-\alpha\bigl(\KL ux+\KL xu\bigr), \]414and therefore $\KL u{x(t)}\le e^{-\alpha t}\KL u{x(0)}$.415\end{theorem}416\begin{proof}417$\frac d{dt}\KL ux=-\sum_iu_i\dot x_i/x_i$. The payoff terms vanish as in \Cref{thm:rec}. The entropy terms418give $\alpha\bigl(\sum_iu_i\log x_i-\sum_jx_j\log x_j\bigr)$, and419$\KL ux+\KL xu=\sum_jx_j\log x_j-\sum_iu_i\log x_i$.420\end{proof}421 422\noindent Convergence of $Q$-learning dynamics in competitive games is known in much greater generality423\cite{LPS21}; the point of \Cref{thm:q} is the exact identity, in which the rate is the learning rate $\alpha$424and does not depend on the game or the temperature. With $\alpha=0.7$ the relative entropy fell from $0.070$ to425$6.1\times10^{-8}$ at $t=10$, against the bound $6.4\times10^{-5}$. \chk{B10} In general the limit is a logit426equilibrium and not a Nash equilibrium \chk{B11}, and by \Cref{thm:natural}(d) it is not natural.427 428\begin{remark}[Where each repair acts]\label{rem:repairs}429Averaging changes the \emph{readout}: the box and the wiring are untouched and one reports $\frac1T\sum x_t$.430Optimism changes the \emph{box}: the learner carries one more step of memory. Regularization changes the431\emph{wiring}: \eqref{eq:q} is the replicator learner in the game with the additional self-payoff432$-\tau\log x_i$, a loop from each learner's output to its own input, up to a constant change of time scale. In433evolutionary terms these are434time-averaging of frequencies, anticipation, and mutation \cite{TVL03}. The trade is visible in the table of435\Cref{sec:summary}: averaging keeps naturality and loses the iterate; regularization gains a rate and loses436both naturality and the equilibrium.437\end{remark}438 439\section{Evaluating agents}\label{sec:eval}440 441Training by self-play, leagues and population-based methods all need to say which of a set of agents is442better \cite{Vin19,LZG17}. The data is an \term{evaluation matrix}: an antisymmetric $K$ with $K_{ij}$ the443advantage of agent $i$ over agent $j$, for instance the log-odds of winning. This is a symmetric zero-sum game444on the set of agents, and an \term{evaluation method} assigns to it a score vector or a distribution on agents.445 446\begin{theorem}[Ratings and cycles]\label{thm:hodge}447\Sli[\cite{JLYY11,BTPG18}] Every antisymmetric $K$ decomposes uniquely and orthogonally as448\[ K_{ij}=(r_i-r_j)+C_{ij},\quad r_i=\tfrac1n\textstyle\sum_jK_{ij},\quad\textstyle\sum_jC_{ij}=0. \]449The first part satisfies $G_{ij}+G_{jk}+G_{ki}=0$ on every triple, and every matrix satisfying this is of that450form. The second part carries the same curl $K_{ij}+K_{jk}+K_{ki}$ as $K$.451\end{theorem}452 453\noindent The ratings $r$ are the least-squares fit of an Elo-like scale; the \term{transitivity index}454$\|G\|^2/\|K\|^2$ measures how much of the data a scale can explain. For five agents with planted ratings and one455planted cycle of strength $0.5$ among three of them, the decomposition returned the ratings456$(0.7,0.3,0,-0.3,-0.7)$, index $0.885$ and curl $1.5$ on the planted triple. \chk{B12} That closed implies457exact is the vanishing of the first cohomology of a simplex.458 459\begin{proposition}[Incomplete comparisons]\label{prop:harmonic}460\Sli[\cite{JLYY11}] If only some pairs of agents have been compared, the decomposition acquires a third,461harmonic component: circulations around loops of the comparison graph that bound no triple of mutually462compared agents. It is locally consistent and globally not a rating, and its dimension is the first Betti463number of the comparison complex.464\end{proposition}465 466\noindent Four agents compared only around a square, each beating the next by one unit, give the smallest467example: zero divergence, no triangles, nothing to fit. \chk{B15} Sparse tournament schedules create such468classes by design.469 470The naturality criterion of \Cref{sec:setting} applies to evaluation unchanged. A league that contains two471copies of an agent, or ten near-copies obtained from one checkpoint, should not be ranked differently for472that reason.473 474\begin{proposition}[Naturality of evaluation methods]\label{prop:evalnat}475\Sob Let $f\colon(S,K)\to(T,K')$ be a clone map between evaluation games.476\begin{enumerate}[label=(\alph*),leftmargin=1.5em,itemsep=1pt,topsep=2pt]477\item Mean score against the field, $s_i=\frac1n\sum_jK_{ij}$, is not natural: duplicating an agent raises the478score of everything that beats it.479\item The set of Nash equilibria is natural: $x$ is an equilibrium of $(S,K)$ if and only if $f_*x$ is one of480$(T,K')$. When the equilibrium of $(T,K')$ is unique, every rule that selects an equilibrium is therefore481natural on types. Invariance to redundant agents is the stated aim of Nash averaging \cite{BTPG18}.482\item The time average of replicator self-play is natural, and when $(T,K')$ has a unique interior equilibrium483it assigns to each type its equilibrium mass.484\item The stationary distribution of the small-mutation chain in which a monomorphic population is invaded by