Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 3601–3700 of 3949. Source text is displayed literally.
3601minus $\eta^{-1}D(y\Vert x^+)$. Nonnegativity of relative3602entropy and its equality condition follow from Jensen's3603inequality for $\log$, with terms of zero mass handled3604by continuity. If the initial state has zeros, the same3605definition is used on its support face. This is a3606multiplicative weights update \cite{freund-schapire,arora-mw}.3607 3608Differentiation at $\eta=0$ gives3609\[3610 \frac{\partial x_i^+}{\partial\eta}\bigg|_{\eta=0}3611 =x_i(a_i-\langle x,a\rangle).3612\]3613Putting $a=f(x)$ yields the replicator field. If $f$ is3614Lipschitz on the compact simplex, it is bounded there3615and the local truncation error relative to the Euler3616step is uniformly $O(\eta^2)$. Indeed the denominator3617is bounded away from zero for small $\eta$ and the3618second derivative with respect to $\eta$ is uniformly3619bounded. On a bounded time interval, compare with3620the Lipschitz ordinary differential equation. The local3621flow also differs from its Euler step by $O(\eta^2)$.3622The discrete error then satisfies a recursion bounded by3623$(1+L\eta)$ times the previous error plus $O(\eta^2)$.3624Summing the geometric series gives an $O(\eta)$ error3625at grid times for fixed elapsed time. This connects the3626update to continuous selection without drawing a3627conclusion about arbitrarily long training.3628 3629\section{The pathwise regret bound}3630 3631Suppose payoffs $a^t$ are observed each round, with3632$|a^t_i|\leq M$ for every coordinate and round. Their3633choice may depend on previous weights. Let $x^t$ be3634the pre-update state and $\eta$ a fixed step size.3635 3636\begin{proposition}[External regret of exponential weights]3637\label{prop:regret}3638For a comparator $p$ supported on the initial support,3639after $T$ updates one has3640\[3641 \sum_{t=0}^{T-1}\langle p-x^t,a^t\rangle3642 \leq \frac{D(p\Vert x^0)}{\eta}3643 +\frac{\eta M^2 T}{2}.3644\]3645\end{proposition}3646 3647\begin{proof}3648Write $Z_t=\sum_i x^t_i e^{\eta a^t_i}$.3649The update equation gives3650\[3651 D(p\Vert x^{t+1})-D(p\Vert x^t)3652 =-\eta\langle p,a^t\rangle+\log Z_t .3653\]3654For a fixed round, the second derivative of3655$\log\sum_i x^t_i e^{s a^t_i}$ is the variance of $a^t$3656under the distribution tilted by $s$. It is at most $M^2$3657since all of its values belong to $[-M,M]$.3658The first derivative at zero is $\langle x^t,a^t\rangle$.3659Integrating the second derivative bound gives3660$\log Z_t\leq\eta\langle x^t,a^t\rangle+\eta^2M^2/2$.3661The claimed inequality follows by summing and dropping the3662nonnegative final relative entropy.3663\end{proof}3664 3665This is a comparison to a fixed behavior in hindsight.3666With an appropriate step as a function of the horizon, the3667bound divided by $T$ tends to zero. It allows an arbitrary3668sequence of bounded revealed scores and does not require3669that a single game produce them. For continuous-time3670regularized reinforcement learning and its relation to3671replicator and other dynamics, see3672\cite{mertikopoulos-sandholm}.3673 3674\section{Averaged joint play}3675 3676The regret theorem yields a statement about a game when3677the scores are the actual counterfactual payoffs of that3678game. For a finite action product, let $u_i$ be player $i$'s3679utility. Each round the players independently use their3680mixed strategies conditioned on the history, giving a3681product law $\nu_t$. If player $i$ receives the payoff3682vector of expected utilities of each of its possible3683actions against the other players' current choices of3684distributions, its payoff under its own distribution is3685$\mathbb E_{\nu_t}u_i(a)$. Its payoff from a fixed unilateral3686deviation $b_i$ is3687$\mathbb E_{\nu_t}u_i(b_i,a_{-i})$. Set3688$\overline\nu_T=T^{-1}\sum_t\nu_t$. Then the coarse3689correlated equilibrium inequalities take the form3690\[3691 \mathbb E_{\overline\nu_T}3692 [u_i(b_i,a_{-i})-u_i(a)]3693 \leq \frac{\operatorname{Regret}_i(T)}{T}3694\]3695for every $i,b_i$, with regret defined as the maximum3696over the fixed deviations (or a bound on that maximum).3697This is obtained by adding the per-round deviations.3698When these bounds tend to zero every accumulation point3699of the averaged joint laws is a coarse correlated3700equilibrium, by continuity of the finitely many linear