Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 3661–3760 of 3949. Source text is displayed literally.
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 linear3701inequalities. The conclusion concerns joint laws, which3702can carry correlation through their common time index.3703A Nash statement on the last product distribution3704would require other hypotheses. This distinction is3705important in agent populations whose behavior continues3706to cycle or react to changing opponents.3707 3708\section{Outer selection and the evaluation interface}3709 3710A program strategy can be represented by a fixed artifact,3711with an evaluation map from its identity and the current3712context to a score. The test distribution, budget,3713counterfactual comparison class, and timing determine3714whether the score estimates the intended fitness.3715An inner process can generate or train candidate3716artifacts. An outer process can then keep a distribution3717over verified candidates and update that distribution using3718scores. Exponential weights keeps the distribution in the3719simplex and is insensitive to score shifts common to3720all candidates in a round. These facts are properties of3721the update. They alone say nothing about the behavior3722or validity of any candidate.3723 3724There is also a compositional concern. If an evaluator3725reports the same payoff for every strategy in a coarse3726fiber, deterministic aggregation can commute with3727selection. If it reports only a randomized label, the3728calculation of Chapter~\ref{ch:stochastic-compression}3729identifies a covariance defect even when the fine3730payoffs are conditional expectations of coarse3731scores. This gives a test of a proposed reporting3732interface before using it as a summary of population3733behavior. Delayed reports, context changes, or3734evaluation mismatch introduce separate errors. A3735learning guarantee is conditional on specifying3736those mechanisms and bounding their effect.3737 3738The constructions in the book put equilibrium,3739dynamics, stochastic modeling, and presentation3740changes into compatible types. A model of interacting3741agents adds an interpretation of strategies and a3742mechanism for producing scores at the chosen interface.3743The resulting learning statements remain relative3744to that mechanism.3745\par3746 3747\appendix3748\chapter{Notation}3749\label{app:notation}3750\small\raggedright3751\setlength{\parskip}{0pt}3752\begin{description}[leftmargin=2em,style=nextline,itemsep=.31\baselineskip]3753\item[$I$, $\Delta(I)$, $x_i$] Type set, its probability simplex,3754 and mass assigned to type $i$. See Chapter~\ref{ch:population}.3755\item[$f(x)$, $\langle x,f(x)\rangle$] The current fitness vector3756 and its mean under $x$.3757\item[$R_f(x)$, $M(x)$] The replicator field and the matrix3758 $\operatorname{diag}(x)-xx^\top$ that converts a payoff3759 covector into a selection direction. See Chapters~\ref{ch:replicator}3760 and~\ref{ch:stochastic-compression}.