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

41\newcommand{\Sli}[1][]{\stag{fwd}{literature\if\relax\detokenize{#1}\relax\else; #1\fi}}42\newcommand{\Srf}[1][]{\stag{accent}{reformulation\if\relax\detokenize{#1}\relax\else; cf.\ #1\fi}}43\newcommand{\Sob}{\stag{accent}{observation}}44\newcommand{\Spg}{\stag{bwd}{programme}}45\newcommand{\chk}[1]{{\footnotesize\sffamily\upshape\color{accent}[#1]}}46\newcommand{\cat}[1]{\mathsf{#1}}47\renewcommand{\Game}{\cat{Game}}48\newcommand{\Dyn}{\cat{Dyn}}49\newcommand{\Dist}{\Delta}50\newcommand{\R}{\mathbb{R}}51\newcommand{\E}{\mathbb{E}}52\newcommand{\one}{\mathbf{1}}53\newcommand{\T}{\mathsf{T}}54\newcommand{\KL}[2]{D(#1\,\|\,#2)}55\newcommand{\sm}{\operatorname{softmax}}56\newcommand{\Var}{\operatorname{Var}}57\newcommand{\term}[1]{\textbf{\itshape #1}}58\setlength{\parskip}{0pt}59\frenchspacing60\raggedbottom61\title{\textbf{Evolutionary Game Theory in Machine Learning and AI:\\ Naturality, Regret, and Recurrence}}62\author{Anonymous}63\date{Higher Categorical Semantics \quad$\cdot$\quad Version 1.0, 17 November 2026}64\begin{document}65\twocolumn[66\maketitle67\begin{center}\begin{minipage}{0.86\textwidth}\small68\textbf{Abstract.} The replicator equation of evolutionary game theory and the standard learning rules of69machine learning are the same objects under different names: multiplicative weights is the replicator flow70sampled in time, natural policy gradient is the replicator field, and Bayesian updating is the replicator map71with log-likelihood as payoff. We organize these identifications around one structure. A learner is an open72dynamical system with payoffs as input and a mixed strategy as output; a game is a wiring of learners; and a73learning rule is \emph{natural} if its closed-loop dynamics commutes with payoff-preserving maps of games, in74particular with the duplication of actions. Each qualitative statement is paired with a quantitative one.75Naturality: the replicator learner is natural, while softmax policy gradient, entropy regularization, score76averaging and a mutation-chain ranking are not, with computed defects; duplicating an action $k$ times multiplies77the policy-gradient learning time by exactly $2k/(k+1)$. Regret: at most $\ln n$ in continuous time for every78horizon, against $\sqrt{T\ln n/2}$ in discrete time. Recurrence: in zero-sum games the relative entropy to79equilibrium is conserved by the flow, increases by exactly $\log\E e^{\eta f}\approx\eta^2\Var(f)/2$ per step80of multiplicative weights, and decays at rate at least $\alpha$ under entropy-regularized dynamics. Finite81populations of learners obey the one-third law and the amplifier and suppressor phenomena of evolutionary graph82theory. All numerical statements are recomputed by a companion script with 21 checks. No new theorem of83learning theory is claimed; the contribution is the organization, the exact constants, and the naturality84criterion.85\end{minipage}\end{center}86\vspace{1.2em}87]88 89\section{Introduction}90 91Evolutionary game theory studies populations in which strategies that earn more become more common. Its92central object, the replicator equation93\begin{equation}\label{eq:rep}94\dot x_i=x_i\bigl((Ax)_i-x^{\T}Ax\bigr),95\end{equation}96was written down for animal conflicts \cite{TaJo78,MSP73}. Machine learning arrived at the same equation97several times: as the continuous-time limit of reinforcement learning \cite{BoSa97} and of multiplicative98weights \cite{FrSc97,Sor09}, as natural policy gradient on a softmax policy \cite{Kak01}, and implicitly in99population-based training, where agents copy their betters \cite{Jad17}. A compact account of the evolutionary side, written100for philosophers and candid about the fragility of the models, is Alexander's Element \cite{Alex23}; a101companion volume \cite{EGHC} retells it in categorical language. This paper carries the results of that volume102to machine learning.103 104The organizing idea is to separate what the evolutionary literature fuses. In \eqref{eq:rep} a learning rule105and a game are multiplied together. We take them apart (\Cref{sec:setting}): a \emph{learner} is an open106dynamical system, a box with payoffs flowing in and a mixed strategy flowing out, and a \emph{game} is a wiring107of such boxes. Self-play, two-player training, leagues and populations on graphs are different diagrams108filled with the same boxes. The question that the categorical setting makes precise is which learners are109\emph{natural}: whose behaviour does not depend on how the actions happen to be named, and in particular on110whether one action has been listed twice.111 112\paragraph{Results.} Each is stated with its status. Tags follow the conventions of the series:113\Scl a classical result; \Sli[source] a result of the cited literature; \Srf[source] a known result restated;114\Sob an observation of this paper, proved here. Tags such as \chk{B6} name checks in the companion script115\texttt{verify-evolutionary-learning.py}.116\begin{itemize}[leftmargin=1.2em,itemsep=1pt,topsep=2pt]117\item \emph{Naturality} (\Cref{sec:setting,sec:eval}). The replicator learner is natural for all118payoff-preserving maps. Softmax policy gradient is not natural for duplication, and the slowdown is the119exact factor $2k/(k+1)$ (\Cref{thm:natural}). Entropy regularization and two common ways of ranking agents fail120the same test (\Cref{prop:evalnat}).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}