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 3541–3640 of 3949. Source text is displayed literally.

3541is a homotopy pullback. This describes quotient families3542while retaining their lifts and all compatibility3543conditions for change of context.3544 3545An evaluator $P\times X\to Y$ between equivariant objects3546is represented in this slice, so its local evaluations3547must transform both their parameters and inputs. For a3548discrete group acting on spaces, the space of equivariant3549maps from $X$ to $Y$ is the homotopy fixed-point space of3550$\operatorname{Map}(X,Y)$ with conjugation transport.3551For example, the cosimplicial description has in degree3552$n$ a family of maps for each string in $G^n$. Transporting3553the domain along the string identifies it with the usual3554cosimplicial diagram for the homotopy limit of the3555conjugation action. Totalization imposes naturality and3556its higher coherence. The assertion concerns the space3557of possible equivariant maps. The existence of a3558natural dynamical invariant, a distinguished equilibrium,3559or a numerical update requires its own mathematical3560conditions.3561 3562In these constructions the context can be an ordinary3563parameter space, a classifying groupoid, or an internal3564base for locally varying types. Equivariance and descent3565describe how locally constructed fitness and revision3566laws assemble. They do not determine a revision law3567without assumptions on its behavioral or statistical3568meaning. Weight updates provide a particularly direct3569case where those assumptions and the resulting equations3570can be specified together.3571\par3572\chapter{Learning rules and populations of agents}3573\label{ch:agent-learning}3574 3575Selection can act on candidate policies or programs as well3576as on inherited traits. In a learning system, three choices3577enter explicitly: what counts as a strategy, how its score3578is obtained, and how that score changes its frequency.3579The replicator field is an infinitesimal revision rule.3580A discrete-time learner can approximate it or use a3581different 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\[