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

305temperature the regularized equilibrium gives duplicated Rock half the mass.306\end{remark}307 308\section{Regret}\label{sec:regret}309 310A learner has \term{no regret} if, against any stream of payoffs, its average payoff is asymptotically at311least that of the best fixed action. For the replicator learner this is an identity.312 313\begin{theorem}[Continuous time]\label{thm:regc}314\Scl[\cite{Sor09,KwMe17}] For the replicator learner and any bounded measurable payoff stream,315\[ \int_0^T\bigl(\pi_i-x\cdot\pi\bigr)\,dt=\log\frac{x_i(T)}{x_i(0)}\le\log\frac1{x_i(0)} \]316for every action $i$ and every horizon $T$. From the uniform initial state the regret is at most $\ln n$.317\end{theorem}318\begin{proof}319$\frac d{dt}\log x_i=\pi_i-x\cdot\pi$ by \Cref{prop:mwu}, and $x_i(T)\le1$.320\end{proof}321 322\noindent The bound does not grow with $T$. Against a stream of six payoffs that alternates between random323vectors and vectors chosen to punish the current favourite, the regret at $T=80$ was $0.24$, against324$\ln6=1.79$, and the identity held to $5\times10^{-8}$. \chk{B4}325 326\begin{theorem}[Discrete time]\label{thm:regd}327\Scl[\cite{FrSc97,CBL06}] For Hedge with payoffs in $[0,1]$ and $\eta=\sqrt{8\ln n/T}$, the regret after $T$ steps328is at most $\sqrt{T\ln n/2}$.329\end{theorem}330\begin{proof}[Sketch]331One step multiplies the normalizing constant by $\E_xe^{\eta\pi}$, and Hoeffding's lemma gives332$\log\E_xe^{\eta(\pi-x\cdot\pi)}\le\eta^2/8$. Summing, the discrete learner satisfies the identity of333\Cref{thm:regc} up to an excess of at most $\eta/8$ per step: the regret is at most $\ln n/\eta+\eta T/8$.334\end{proof}335 336\noindent Over forty runs with $n\in\{2,5,10\}$, $T\in\{200,1000\}$, half against random payoffs and half337against an adversary, the largest ratio of regret to bound was $0.50$. \chk{B5} The whole difference between338$\ln n$ and $\sqrt T$ is the term339\begin{equation}\label{eq:excess}340\Lambda_\eta(x,\pi)=\log\E_x\,e^{\eta(\pi-x\cdot\pi)}=\tfrac12\eta^2\Var_x(\pi)+O(\eta^3),341\end{equation}342the price of holding the payoff fixed for a step. The same term decides the fate of discrete learning in343games.344 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$.