Distributed Dynamic Reinforcement of Efficient Outcomes in Multiagent Coordination and Network Formation

Georgios C. Chasparis, Jeff S. Shamma

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

We analyze reinforcement learning under so-called "dynamic reinforcement." In reinforcement learning, each agent repeatedly interacts with an unknown environment (i. e., other agents), receives a reward, and updates the probabilities of its next action based on its own previous actions and received rewards. Unlike standard reinforcement learning, dynamic reinforcement uses a combination of long-term rewards and recent rewards to construct myopically forward looking action selection probabilities. We analyze the long-term stability of the learning dynamics for general games with pure strategy Nash equilibria and specialize the results for coordination games and distributed network formation. In this class of problems, more than one stable equilibrium (i. e., coordination configuration) may exist. We demonstrate equilibrium selection under dynamic reinforcement. In particular, we show how a single agent is able to destabilize an equilibrium in favor of another by appropriately adjusting its dynamic reinforcement parameters. We contrast the conclusions with prior game theoretic results according to which the risk-dominant equilibrium is the only robust equilibrium when agents' decisions are subject to small randomized perturbations. The analysis throughout is based on the ODE method for stochastic approximations, where a special form of perturbation in the learning dynamics allows for analyzing its behavior at the boundary points of the state space.

Original languageEnglish (US)
Pages (from-to)18-50
Number of pages33
JournalDynamic Games and Applications
Volume2
Issue number1
DOIs
StatePublished - Nov 21 2012

Keywords

  • Coordination games
  • Dynamic reinforcement
  • Endogenous network formation
  • Evolutionary dynamics
  • Reinforcement learning

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Distributed Dynamic Reinforcement of Efficient Outcomes in Multiagent Coordination and Network Formation'. Together they form a unique fingerprint.

Cite this