Independent scholarship · Open accessThe monthly digest

Indexed text attachment

evolutionary-game-theory-in-higher-categories.tex

Source for Evolutionary Game Theory in Higher Categories

View paper · Download original file

Lines 3581–3680 of 3949. Source text is displayed literally.

3581different update with its own statistical guarantee.3582 3583\section{An update from relative entropy}3584 3585Let $x$ be a probability vector with positive coordinates3586on a finite set $I$. Given a payoff vector $a$ and a step3587$\eta>0$, exponential weights defines3588\[3589 x_i^+=\frac{x_i e^{\eta a_i}}{\sum_j x_j e^{\eta a_j}}.3590\]3591A common additive shift of the payoff cancels. The3592update uniquely maximizes on the simplex3593\[3594 y\longmapsto3595 \langle y,a\rangle-\eta^{-1}D(y\Vert x),3596 \qquad3597 D(y\Vert x)=\sum_i y_i\log(y_i/x_i),3598\]3599where a zero summand is interpreted as zero. Indeed,3600substitution of $x^+$ writes the objective as a constant3601minus $\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 a