Cours Agay 2004

De
Publié par

Dynamique des systèmes complexes et applications aux SHS :modèles, concepts méthodes-Equilibre(s).-Dynamiquesavec apprentissage par renforcement.Jean-Pierre NadalLaboratoire de Physique Statistique de l’ENSet CENECC (CENtre d’Etude des systèmes Complexes et de la Cognition, ENS)nadal@lps.ens.frEcoleThématique CNRS d ’Agay Roches Rouges 8 - 17 mars 2004ƒƒ999ƒƒƒ9ƒƒƒplan• Notations, rappels• EquilibresPoint fixe d’une dynamique déterministe Dyn. stochastique avec potentiel (énergie) : BoltzmannNashEquilibre de Nash en Stratégie Mixte (MSE)Quantal Response Equilibrium (QRE)Expérimentation : comparaison comportements / modèles• Dynamique avec apprentissage / adaptationPrincipe de l’apprentissage par renforcementIllustrations : Jeu à deux joueurs - QRE versus dynamique de populationsEl Farol / Minority GameMarché aux poissons de Marseille Mémoire à court-terme (variante du modèle de Hopfield)• Logit or not logit ? (le principe d’entropie maximale).mars 2004 école Systèmes Complexes 2notations, rappels• N agents : i = 1, 2,…, N Choix discrets - exemple du cas binaire :• choix de l’agent numéro i : ω = 1 / ω = 0 ou : S = +1 / S = -1i i i i assister/ne pas assister, acheter/ne pas acheter, groupe A/groupe B,neurone actif/inactif, spin d’Ising +/-, automate 1/0, action 1/action 2,stratégie 1/ stratégie 2 (coopérer/trahir, signaler/ne pas signaler,…) …• Pour chaque agent i : u (S , S ) = utilité = surplus = gain = - frustrationi i ...
Publié le : vendredi 23 septembre 2011
Lecture(s) : 46
Nombre de pages : 34
Voir plus Voir moins
Dynamique des ssyètem socpmelexets pp acaliontiua sHS xm: Slèdoconces,  méteptssohed
Jean-Pierre Nadal Laboratoire de Physique Statistique de lENS et CENECC (CENtre dEtude des systèmes Complexes et de la Cognition, ENS) nadal@lps.ens.fr
-Equilibre(s). -Dynamiques avec apprentissage par renforcement.
EcoleThématiqueCNRS dAgay Roches Rouges 8 -17 mars 2004
esèmom Ce olstSy02 scé40ramappelstions, ralnoNatlpxesep2
Equilibres ƒPoint fixe dune dynamique déterministe ƒDyn. stochastique avec potentiel (énergie) : Boltzmann ƒNash ƒEquilibre de Nash en Stratégie Mixte(MSE) ƒQuantal Response Equilibrium(QRE) ƒExpérimentation : comparaison comportements / modèles Dynamique avec apprentissage / adaptation ƒPrincipe de lapprentissage par renforcement ƒIllustrations :  9srsu Eevimuqydan joudeux -QReurs à ueJdee op patulnsio 9El Farol / Minority Game 9Marché aux poissons de Marseille 9Mémoire à court-terme (variante du modèle de Hopfield) Logitor not logit? (le principe dentropie maximale).
notations, rappels Nagents :i= 1, 2,, discrets - exemple du cas binaire :N Choix  choix de lagent numéroi:ωi= 1 /ωi S : ou= 0i= +1 / Si= -1 assister/ne pas assister, acheter/ne pas acheter, groupe A/groupe B, neurone actif/inactif, spin dIsing +/-, automate 1/0, action 1/action 2, stratégie 1/ stratégie 2 (coopérer/trahir, signaler/ne pas signaler,)  Pour chaque agenti:ui(Si, S-i) =utilité= surplus = gain =-frustration S-i= { choix des autres agents } ou { choix des agents voisins dei} Exemples :ui(Si, S-i) = Sihiavec : hi(S-i) =ΣkJi kSk+ Hi ui(ωi,ω-i) = Sihiavec : hi(S-i) =ΣkJi kωk+ Hi Ji k= influence de lagent numéroksur lagent numéroi(0,> 0ou< 0) Hi= préférence individuelle / prix de réserve  prix /,  Hi=-θi:θi= seuil dactivation « Energie »E( S ) =-½Σi,kJi kSiSk-ΣiHiSi « Utilité sociale » U ( S ) =Σiui(Si, S-i)similaire à, mais différent de,-E(S) avec S = { choix de tous les agents} = {S1, S2, , SN} = « configuration » mars 2004 école Systèmes Complexes 3
)ueiqsttita seuqisyhp ,seuqimdynames ystèes(silrbqEiuex4spmelnimie:st dueerétnyDƒqima= )1)1+ 1P(Si(t+1/ T)0 e = β =(eptnelocsyS emètoC sma 2rs4é00amixuq i xiShcioS-i(Si,  ui(miseér erueliem ed = ) +1(tSie)nspo =Σ Jkkih (i)t  Hi> 0,  Sk(t) +  tio(iS:) )ts ,   1  :si1)t+ + =utide l/ militéasitinim ealnod t ou t àt anstinmixam ,t noitasie ou séquentiell)e:   s(rttagéeiru frastontidy (iman euqaraplèll ).} }{=uesrartca{ttle: tielquene séS (E ed aminim{  = }esix ftsinpoaC sdni= -  1ƒ. Si(t+1)sinon : anyduqimuqir ,se snsétymrateioct
hi(t)
ƒDynamique stochastique (bain thermique, bruit synaptique, main temblante) avec interactions symétriques + logit :p(Si= 1/[1 + exp  2= +1) βhi] T = température = 1/β Péqu. (1/Z( S ) = ) exp βE( S ). = distribution deBoltzmann(1844 - 1906) (potential games en théorie des jeux)
½
Equilibres(économie) Nash:  S* est un équilibre de Nash si, pour touti: ui(S*i, S*-i)ui(Si, S*-i) quel que soit Si. cas, il existe 0, 1 ou plusieurs équilibres de Nash.selon les un point fixe attractif de la dynamique déterministe est un équilibre de Nash. Equilibre deNashenStratégieMixte (Mixed-StrategyEquilibrium) Chaque joueurijoue la stratégie Siavec une probabilité pi(Si) Gain anticipé pari: <ui(Si) > =Σp (S-i)ui(Si, Si) -{ S-i} MSE : <ui(Si quel que soit S identique) >i. il existe toujours un MSE. mars 2004 école Systèmes Complexes 5
Stratégies mixtes et comportement QuantalResponseEquilibrium(QRE) pi(Si) =f(< ui(Si) > ) /Σ{s}f(< ui(s) > )   ( <ui(Si) > = gain anticipé parisil choisit la stratégie Si) Exemple (logit !) : f(x) =exp(βx ). remarque : QRE« approximation dechamp moyen» en physique Expériences: comparaison des comportements avec les prédictions MSE et QRE Réf.: McKelvey and Palfrey,alrmnor gam or fliuqe esof airbiG maem,sdn sea er lnopsuQatna economic behavior, 7:6-38 (1995) Colin F.Camerer, « Behavorial Game Theory », Princeton Univ. Press 2003 mars 2004 école Systèmes Complexes 6
mars 2004
Dynamique : Apprentissage par renforcement
école Systèmes Complexes
7
Apprentissage par renforcement Gain / utilité / profitnon connuà lavance Exploration: lexpérience (la sienne et/ou celle des autres) permet dévaluer le bénéfice dune action (dune stratégie, dun choix) Renforcementdes actions qui se révèlent les plus efficaces :  augmentation de la probabilité de choisir cette action dans le futur (exploitationdes connaissances acquises) Cas le plus simple :le gain dune action est connu immédiatement (exemple : jeux usuels de la théorie des jeux, gain distribué après chaque tour) Cas plus difficile : gain connu uniquement après une suite dactions Encore plus difficile (mais très réaliste) : gain = information purement qualitative : «cest bien / cest mal» (réf. : R. S. Sutton & A. G. Barto, « Reinforcement learning », The MIT Press, 1998) mars 2004 école Systèmes Complexes 8
arning ((EWA) le &oH1 99aCemer re-ncigWexpEieertcar noidethttA téréeu i91)Jn 19tsna eniahuqA:c gesaisntreppA9)adroJ( neiseyab  7 ;aCemer r9189)Belief-learninsill ret1991te ,; c llWaeris99 1B or83; 59 1nw1 bins; Ro951)on 1tcif ,gp suoitiCo (yla18t nourp egr ratnerassil)rappAeh(bioavetemtnla eocpmroentissagxes9ApprAcM ; 1991 ruhtr A ;7319s osCr; 59 5re1 etllM soBushent(rcemenfometèys SlempCos 2 sramelocé400 )= = S ( )t( iS :piQREde a mo, s(A(fΣ  / ) t), S i( Af(  x(=)xe(ppmel: f  par exe t))avec )βx
{s}i
.e à ribuue achaql a t,taittegtndsoi punratta (op noitcS elbiss(  estimation dtcoin )iAS( ,)t dixSie t) ( l àu <e)S(i  > ohC)
Ai(Si, t)
stratégies (actions possibles)
la probabilité que lagentichoisisseSi=S est dautant plus grande que estAi(S, t)est grand
Si= 1
Si= 3
Si= 2  
gainui S(3 ,i(t) )
Si= 4
C semètssexelpmoenprAp10e agsstierfnap remtnroec 3choisie à tlocéyS e sra4002m
Si= 3  
Si= 4  
gainsuiit
stratégies (actions possibles)
Ai(Si, t)
Si= 2  
Si= 1  
la probabilité que lagentichoisisseSi=S est dautant plus grande que estAi(S, t)est grand
«fictitious play»
4,S 1=2,3, ,S((Ss nuurpo ))on cntap eer rrofnemec11esprAptienagssyStsmèseC molpxemars 2004école 
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.