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 581–680 of 725. Source text is displayed literally.
581\midrule582Hedge and replicator & one is the other, sampled & exact at every step size & B1\\583Policy gradient & replicator with an extra factor $x_i$ & escape time $\sim1/(2D\epsilon)$ against $\log(1/\epsilon)/D$; ratios $3.0$, $11.8$, $73.3$ & B2, B3\\584Duplicated actions & (R), (H) natural; (PG), (Q) not & slowdown $2k/(k+1)$; defect $0.028$ & B19--B21\\585Regret & no regret & $\le\ln n$ continuous; $\le\sqrt{T\ln n/2}$ discrete; observed ratio $\le0.50$ & B4, B5\\586Zero-sum, flow & relative entropy conserved; recurrence & numerical drift $1.3\times10^{-15}$ over time $40$ & R4 of \cite{EGHC}\\587Zero-sum, Hedge & iterate leaves, average converges & $+\tfrac12\eta^2\Var$ per step; boundary after $1451$ steps; exploitability $0.0015$ & B6--B8\\588Optimism & last iterate converges & $0.070\to1.5\times10^{-10}$ in $6000$ steps & B9\\589Entropy regularization & converges; not natural; biased & rate at least $\alpha$, by an identity; type masses $(0.40,0.36,0.24)$ at $\tau=0.5$ & B10, B11, B21\\590Evaluation & ratings plus cycles plus harmonic & index $0.885$; curl $1.5$ & B12, B15\\591Redundant agents & averaging and name-mutation chain not natural; replicator average natural & $(0,0,0.25,-0.25)$; $(0.4,0.4,0.2)$; $(\tfrac13,\tfrac13,\tfrac13)$ & B13, B14\\592New conventions & can invade by drift & iff barrier $<\tfrac13$; $N\rho=1.021,\dots,0.958$ & B16\\593Copying topology & amplifiers and suppressors & $0.167<0.251<0.287$ & B17\\594Inference & Bayes is Hedge at $\eta=1$ & exact & B18\\595\bottomrule596\end{tabular}597\caption{Qualitative statements and their quantitative forms. All numbers are produced by the companion598script.}\label{tab:summary}599\end{table*}600 601\Cref{tab:summary} collects the results. Read down the middle column it is a list of facts most of which are602individually known; read across, each has a constant attached; and the recurring entry is naturality, which603sorts the methods into those that depend on how actions and agents are named and those that do not.604 605\section{Limits}\label{sec:limits}606 607\emph{Scope.} Everything here is tabular: a finite set of actions and exact payoffs. Function approximation,608sampling noise, and partial observation are outside it; they are where methods such as \cite{HMO20} do their609work. The numbers come from games with at most six actions and populations of at most a few hundred, chosen610to be exactly computable, and are illustrations of the statements and not benchmarks. No experiment on a611trained model was run.612 613\emph{Novelty.} The identifications of \Cref{prop:mwu,prop:pg,prop:bayes}, the regret bounds, recurrence, the614Hodge decomposition, the one-third law and the isothermal theorem are from the literature. The observations615are \Cref{thm:natural}, the identity of \Cref{thm:q}, \Cref{prop:evalnat}, and the placing of the three616repairs in \Cref{rem:repairs}. They are short, and parts of them are likely known in other forms; the617invariance of Nash averaging under redundancy, for one, is a stated motivation of \cite{BTPG18}.618 619\emph{How categorical.} Modestly. The category $\Game$, the functor to dynamical systems, and the operad of620wiring diagrams are ordinary category theory; the only cohomology is in degree one; the homotopy theory is in621the Conley index behind \Cref{rem:mcc}, which we invoke and do not compute. The language earns its place by one622question, whether a construction commutes with the maps, which turned out to separate methods that the623literature usually compares on other grounds.624 625\emph{References.} The bibliography was assembled from memory, except for \cite{OPP19,HMO20} and the five items626of \Cref{rem:llm}, whose bibliographic details were checked online on 17 November 2026. It should be verified627before it is relied on.628 629\emph{Authorship.} This paper was drafted with the assistance of an AI system (Anthropic's Claude), which also630wrote and ran the companion script.631 632\paragraph{Open problems.} \Spg (1) Characterize the learners that are natural for clone maps among those633derived from a regularizer; we expect entropy on types and not on names to be forced. (2) Give the634rate in \Cref{thm:q} for a non-uniform equilibrium, where the limit moves with $\tau$. (3) Extend635\Cref{prop:evalnat}(c) from time averages to chain components, so that a ranking by recurrent classes is636natural by construction. (4) Find the analogue of the isothermal theorem for populations of learners whose637fitness depends on the population, where the graph and the game interact.638 639\appendix640\section{The companion script}\label{app:checks}641 642\texttt{verify-evolutionary-learning.py} uses only the Python standard library, fixes its random seed, runs643in under half a minute, and exits with status zero if and only if its 21 checks pass. Flows are integrated by644a fourth-order Runge--Kutta scheme; fixation probabilities are exact. The checks test instances and recompute645the numbers quoted in the text. They do not prove the theorems.646 647\begin{center}\footnotesize648\begin{tabular}{@{}lp{0.82\columnwidth}@{}}649\toprule650B1 & Hedge equals the time-$\eta$ replicator flow, 30 random cases\\651B2 & policy gradient in logits; Fisher preconditioning\\652B3 & escape times, \Cref{prop:escape}, against numerical integration\\653B4 & continuous-time regret identity and bound\\654B5 & discrete regret bound, 40 runs, random and adversarial\\655B6 & exact drift of Hedge, \Cref{prop:drift}, three step sizes\\656B7 & monotone divergence to the boundary\\657B8 & exploitability of the time average\\658B9 & optimistic Hedge, last iterate\\659B10 & identity and rate of \Cref{thm:q}\\660B11 & rest points of \eqref{eq:q} are logit equilibria\\661B12 & Hodge decomposition of a planted example\\662B13 & mean score and replicator average under cloning\\663B14 & small-mutation chain: uniform, dominated, cloned\\664B15 & a harmonic class on a square of comparisons\\665B16 & one-third law, exact fixation, $N=400$\\666B17 & line, well-mixed, star: exact fixation, $N=6$\\667B18 & Bayes equals Hedge with $\eta=1$\\668B19 & naturality defect of (R) and (PG) under cloning\\669B20 & slowdown $2k/(k+1)$ for $k=1,2,4,8$\\670B21 & logit equilibrium with a cloned action, three temperatures\\671\bottomrule672\end{tabular}673\end{center}674 675\begin{thebibliography}{XLLS26}\footnotesize\setlength{\itemsep}{0.5pt}676\newcommand{\bi}[1]{\bibitem[#1]{#1}}677\bi{Alex23} J.~M.~Alexander, \emph{Evolutionary Game Theory}, Elements in Decision Theory and Philosophy, Cambridge University Press, 2023.678\bi{Ama98} S.~Amari, Natural gradient works efficiently in learning, \emph{Neural Comput.} 10 (1998), 251--276.679\bi{BaPi18} J.~P.~Bailey, G.~Piliouras, Multiplicative weights update in zero-sum games, in \emph{Proc.\ ACM Conf.\ Economics and Computation (EC)}, 2018, 321--338.680\bi{BoSa97} T.~B\"orgers, R.~Sarin, Learning through reinforcement and replicator dynamics, \emph{J.~Econom.\ Theory} 77 (1997), 1--14.