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

345\begin{corollary}\label{cor:avg}346\Scl If both players of a zero-sum game with payoffs in an interval of length $1$ use Hedge with the step of347\Cref{thm:regd}, their time-averaged strategies form a $2\sqrt{\ln n/(2T)}$-equilibrium. In a general game the348time-averaged joint play approaches the set of coarse correlated equilibria.349\end{corollary}350 351\noindent In self-play of Rock--Paper--Scissors, whose payoffs have range $2$, the time average over352$T=20000$ steps could be exploited for $0.0015$, against the corresponding bound $0.0105$. \chk{B8}353 354\section{Zero-sum games: recurrence, divergence, repair}\label{sec:zerosum}355 356Regret bounds speak of averages. What the strategies themselves do is another matter, and it is the matter357that concerns adversarial training \cite{Goo14}, where the iterate and not the average is the model.358 359\subsection{The flow cycles}360 361\begin{theorem}[Conservation and recurrence]\label{thm:rec}362\Sli[\cite{HoSi98,PiSh14,MPP18}] Let $A$ be antisymmetric with an interior equilibrium $x^*$. Along replicator363self-play $\KL{x^*}{x(t)}$ is constant. For two replicator learners in a zero-sum game with interior equilibrium364$(x^*,y^*)$ the sum $\KL{x^*}{x}+\KL{y^*}{y}$ is constant, and the flow is Poincar\'e recurrent: almost every365trajectory returns arbitrarily close to its starting point infinitely often.366\end{theorem}367\begin{proof}[Proof of conservation]368$\frac d{dt}\KL{x^*}{x}=-\sum_ix^*_i(\pi_i-\bar\pi)=-(x^*)^{\T}Ax+x^{\T}Ax$. Antisymmetry gives $x^{\T}Ax=0$, and369$(x^*)^{\T}Ax=-x^{\T}Ax^*=0$ because $Ax^*$ is constant on the support of an interior equilibrium and that370constant is the value $0$.371\end{proof}372 373\noindent Conservation says that such a game does no work on the learner. An antisymmetric matrix has no374symmetric part, so the gradient component of the replicator field vanishes \cite{EGHC}; and when the equilibrium375is uniform the game is purely cyclic in the sense of the Hodge decomposition of \Cref{sec:eval}.376 377\subsection{The discretization spirals out}378 379\begin{proposition}[Exact drift of Hedge]\label{prop:drift}380\Srf[\cite{BaPi18}] In Hedge self-play of an antisymmetric game with interior equilibrium $x^*$, each step381changes the relative entropy by exactly382\[ \KL{x^*}{x^+}-\KL{x^*}{x}=\Lambda_\eta(x,Ax)\ \ge0, \]383with equality only if all actions in use earn the same. Hence $\KL{x^*}{x_t}$ is non-decreasing, and it increases384by about $\tfrac12\eta^2\Var_x(Ax)$ per step.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.