Natural Gradient in Evolutionary Games

2025-05-02 0 0 208.36KB 13 页 10玖币

侵权投诉

arXiv:2210.00573v1 [cs.GT] 2 Oct 2022

NATURAL GRADIENT IN EVOLUTIONARY GAMES

A PREPRINT

Vladimir Ja´

cimovi´

Faculty of Natural Sciences and Mathematics

University of Montenegro

Cetinjski put bb., 81000 Podgorica

Montenegro

vladimirj@ucg.ac.me

October 4, 2022

ABSTRACT

We study evolutionary games with a continuous trait space in which replicator dynamics are re-

stricted to the manifold of multidimensional Gaussian distributions. We demonstrate that the repli-

cator equations are natural gradient ﬂow for maximization of the mean ﬁtness.

Our ﬁndings extend previous results on information-geometric aspects of evolutionary games with

a ﬁnite strategy set.

Throughout the paper we exploit the information-geometric approach and the relation between evo-

lutionary dynamics and Natural Evolution Strategies, the concept that has been developed within

the framework of black-box optimization. This relation sheds a new light on the replicator dynam-

ics as a compromise between maximization of the mean ﬁtness and preservation of diversity in the

population.

Keywords replicator equations ·Fisher information metric ·natural evolution strategies ·information-geometric

optimization

1 Introduction

Simple games, that serve as illustrative examples in Evolutionary Game Theory (EGT), belong to the class of evo-

lutionary games with a ﬁnite strategy set. In such a setup, one investigates a population that consists of nspecies.

Denote the set of species by A={A1,...,An}and consider the set P(A)of all probability distributions over A. Set

P(A)can be identiﬁed with the unit simplex in n-dimensional vector space:

P(A)≃∆n={p= (p1...pn)T:p1+···+pn= 1, pi≥0i= 1,...,n}.

Probability pi=P(Ai)can be conceived as a portion of species Aiin the population.

Elements of P(A)are called strategies. Those strategies that are concentrated at a single species (i.e. probability

distributions with pi= 1 for some i∈ {1,...,n}) are named pure strategies. Hence, there are precisely npure

strategies that correspond to nspecies. Strategies that are note pure are called mixed strategies.

Furthermore, to each Ai∈Awe assign a continuous function fi(p)≡fi(p1,...,pn) : Rn→R. Functions fi(p)

are called ﬁtness functions. Vector-valued function f(p)≡(f1(p),...,fn(p)) : Rn→Rndeﬁnes so-called ﬁtness

landscape. The assumption that the ﬁtness of one species depends on portions of all the others, brings a strategic

aspect into interactions between them.

Introduce the mean ﬁtness in the population:

hf(p)i=p·f(p) =

i=1

pifi(p).(1)

Natural Gradient in Evolutionary Games A PREPRINT

Throughout this paper the notion x·ystands for the inner product of vectors xand yin the vector space. Sometimes

we will also use the notation xTy.

We assume that portions pievolve with the time according to the following ODE’s

˙pi=pi(fi(p)− hf(p)i), i = 1,...,n. (2)

Equations (2) are well known as replicator equations. They have a simple justiﬁcation. We say that the state of

population at a moment tis given by vector p(t) = (p1(t),...,pn(t)). Then equations (2) claim that if for a given

state of population, species Aihas higher ﬁtness than the mean ﬁtness, its portion pi(t)will increase.

Foundations of EGT have been laid in 1970’s by Maynard Smith ([25]), who applied game-theoretic paradigms to the

Darwinian theory of evolution. Hence, the terminology inherited from the biological context (species, ﬁtness, etc.) is

commonly used in the literature. As EGT emerged into a prominent branch of Game Theory, it has been recognized

that its models and paradigms present a signiﬁcant interest for social sciences and Philosophy. Indeed, the evolution

is not exclusively biological concept; one can talk, for instance, about cultural, or behavioral evolution. Taking into

account such a wide scope of interpretations, elements of the set Ado not necessarily represent biological species.

Depending on the ﬁeld of applications, Aican correspond to political views, lifestyle habits, fashion preferences, or

moral choices. Such a variety of interpretations brought alternative terminologies into EGT. In some cases it is more

appropriate to talk about actions instead of species, payoff instead of ﬁtness; in these cases (1) represents an expected

payoff.

Regardless of applications and interpretations, the abstract mathematical framework of EGT remains the same. It is

easy to check that ∆nis an invariant set for the dynamics (2). Hence, replicator equations describe the evolution of

strategies, that is - of probability distributions over a ﬁnite set. Distributions from P(A)are usually called categorical

distributions.

In addition to evolutionary games with a ﬁnite strategy set, one can also conceive a situation where the set of actions

(that is - of pure strategies) is a continuous subset of Rn. Then mixed strategies are absolutely continuous probability

measures on Rn. In such a setup, evolutionary dynamics generate a ﬂow on a certain family of probability measures

on Rn. Such games are named evolutionary games with a continuous trait space.1

Mathematical framework of EGT makes it possible to study evolutionary games as ﬂows on families of probability

distributions. Such an approach relies on results and paradigms of Information Geometry (IG). Below, we will explain

information-geometric approach to evolutionary games and exploit it throughout the present paper.

When investigating evolutionary games with a ﬁnite strategy set, one should take into account metric properties of

P(A). It is not difﬁcult to notice that the standard Euclidean metric is an inappropriate measure of the distance between

two categorical distributions. Instead, IG proposes a general way to introduce a metric on families of probability

distributions, thus turning them into Riemannian manifolds. Metric further deﬁnes a gradient ﬂow on the manifold

and replicator dynamics can be studied from this point of view. In the case of games with a ﬁnite strategy set, this

has been recognized by Marc Harper and led to novel insights into geometric and information-theoretic aspects of

evolutionary dynamics, [17, 18]. In Section 2 we brieﬂy recall Harper’s results that serve as a starting point for further

generalizations.

Manifold P(A)of categorical distributions is just one particular example of the so-called statistical manifold. In Sec-

tion 3 we brieﬂy expose general geometric approach to families of probability distributions and introduce the notions

of Fisher information metric and natural gradient. From this point of view, Harper’s results about the evolutionary dy-

namics on the manifold of categorical distribution might turn out to be just the tip of the iceberg. This suggests that IG

provides a universal theoretical background for study of a broad class of evolutionary games. One can treat evolution-

ary dynamics as gradient ﬂows on statistical manifolds. Although information-geometric concepts are widely used in

Mathematics and Computer Science, the most comprehensive theoretic approach to gradient ﬂows on statistical man-

ifolds has been developed for purposes of black-box optimization. Black-box optimization (including evolutionary

algorithms and stochastic search methods) relied for decades on various heuristics without a coherent theoretical jus-

tiﬁcation. However, this direction of research evolved into a general framework that encompasses some of previously

known stochastic search algorithms and provides a solid theoretical background for them. The black-box optimization

community adopted the terms Natural Evolution Strategies (NES) and Information-Geometric Optimization (IGO) for

1Games with a continuous space of pure strategies allow for a biological interpretation in which pure strategies correspond to

individual traits of a certain species. Such an interpretation stands behind the expression "continuous trait space", see for instance

[10, 22]. On the other hand, the term "game with a ﬁnite strategy set" is a bit imprecise, since it means that the set of pure strategies

is ﬁnite. (The set of all strategies is continuous in any case.) Nevertheless, the term "games with a continuous strategy space" is

commonly used in the literature. Alternatively, some researchers ([26]) preferred to talk about evolutionary games with ﬁnite (or

continuous) action sets. This terminology is inspired by various non-biological interpretations of evolutionary games.

Natural Gradient in Evolutionary Games A PREPRINT

gradient ﬂows on statistical manifolds, [34, 33, 15, 28, 14, 1]. NES and IGO offer an abstract conceptual approach

which is valid for any statistical manifold. Section 4 contains an explanation of these concepts with a view on their

relevance for EGT.

In Section 5, following papers [10, 29], we introduce the general setup of games with a continuous trait space: ﬁtness

landscape, replicator equations, etc.

A notable example of statistical manifold is obtained by endowing the family of Gaussian distributions with the Fisher

information metric. In Section 6 we study restriction of the evolutionary dynamics to this particular statistical manifold

(we denote it by N(a, C)). We demonstrate that the replicator equations are natural gradient ﬂow on N(a, C)for

maximization of the mean ﬁtness. This assertion is an extension of the Harper’s result about gradient ﬂows on the

statistical manifold P(A).

In Section 7 we apply the NES and IGO approaches to evolutionary games with Gaussian mixed strategies. This

demonstrates the relation between recent advances in black-box optimization and EGT. Our study unveils the global

objective that the population as a whole tends to achieve. These ﬁndings also support an interpretation of evolutionary

dynamics as a multi-agent learning algorithm.

Analysis of asymptotic properties of replicator dynamics suggests that the corresponding optimization algorithm ex-

hibits a slow convergence. In Section 8 we borrow ideas from the black-box optimization in order to investigate

mechanisms that accelerate evolutionary dynamics (and hence the corresponding algorithms). By introducing these

mechanisms into evolutionary dynamics, one can design algorithms with signiﬁcantly higher convergence rate, at the

expense of diversity. We also brieﬂy point out some biological interpretations of these mechanisms that accelerate the

evolution.

Finally, Section 9 contains some concluding remarks, a brief discussion on various applications and an outlook into

future research directions.

The main result is reported in Section 6. Novel insights are also exposed in sections 7 and 8. Sections 1-5 serve as a

necessary introduction and are included for the sake of completeness of the exposition. The present paper is mostly

inspired by papers [10],[8] and [17]. On one side, Cressman at al. in [10] study the restriction of replicator dynamics

to the family of Gaussian distributions and derive ODE’s for the mean vector and covariance matrix. On the other

side, Beyer in [8] investigates the natural gradient policy for optimization of linear-quadratic function. Adaptation of

his analysis to the setup of an evolutionary game, yields precisely the system of ODE’s derived in [10]. Therefore, we

conclude that evolutionary dynamics on the manifold N(a, C)generate natural gradient ﬂow for the mean ﬁtness.

2 Natural gradient dynamics in games a with ﬁnite strategy set

In order to study information-geometric aspects of evolutionary dynamics, we start by introducing metric on the family

of categorical distributions. As already mentioned, this family can be identiﬁed with the unit simplex.

Each point of the simplex satisﬁes p1+···+pn= 1, so the tangent space at any interior point of ∆nis (n−1)-

dimensional vector space consisting of vectors v= (v1···vn)Tthat satisfy v1+···+vn= 0. Orthogonal complement

of this space is the line with direction vector 1= (1 ··· 1)T. We introduce the following Riemannian metric tensor

on the interior of ∆n

g(η, ν) =

i=1

ηiνi,(3)

where pis a point in the interior of ∆nand ηand νare vectors from the tangent space at p.

Metric gturns the unit simplex ∆n(and, hence, the family of categorical distributions P(A)) into a Riemannian

manifold.

Remark 1.In EGT (3) is commonly referred to as Shahshahani metric, because it has been introduced into Game

Theory in paper [32]. Notice that gdiverges at the boundary of ∆n(since on the boundary there exists i, such that

pi= 0), so the deﬁnition is valid only in the interior.

Theorem 1. [20, 17] If the system of differential equations ˙pi=fi(p)deﬁnes a Euclidean gradient ﬂow with fi(p) =

∂V

∂pi, then replicator equations (2) deﬁne a gradient ﬂow with respect to the Shahshahani metric.

Remark 2.In the literature on EGT it is often assumed that ﬁtness functions are linear:

fi(p) =

j=1

aij pj,for some coefﬁcients aij .

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.00573v1[cs.GT]2Oct2022NATURALGRADIENTINEVOLUTIONARYGAMESAPREPRINTVladimirJa´cimovi´cFacultyofNaturalSciencesandMathematicsUniversityofMontenegroCetinjskiputbb.,81000PodgoricaMontenegrovladimirj@ucg.ac.meOctober4,2022ABSTRACTWestudyevolutionarygameswithacontinuoustraitspaceinwhichreplicato...

展开>> 收起<<

Natural Gradient in Evolutionary Games.pdf

共13页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Natural Gradient in Evolutionary Games

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: