Deterministic limit of temporal difference reinforcement learning for stochastic games

Abstract

Reinforcement learning in multiagent systems has been studied in the fields of economic game theory, artificial intelligence and statistical physics by developing an analytical understanding of the learning dynamics (often in relation to the replicator dynamics of evolutionary game theory). However, the majority of these analytical studies focuses on repeated normal form games, which only have a single environmental state. Environmental dynamics, i.e., changes in the state of an environment affecting the agents' payoffs has received less attention, lacking a universal method to obtain deterministic equations from established multistate reinforcement learning algorithms. In this work we present a novel methodological extension, separating the interaction from the adaptation time scale, to derive the deterministic limit of a general class of reinforcement learning algorithms, called temporal difference learning. This form of learning is equipped to function in more realistic multistate environments by using the estimated value of future environmental states to adapt the agent's behavior. We demonstrate the potential of our method with the three well established learning algorithms Q learning, SARSA learning and Actor-Critic learning. Illustrations of their dynamics on two multiagent, multistate environments reveal a wide range of different dynamical regimes, such as convergence to fixed points, limit cycles, and even deterministic chaos.

arXiv comment18 pages, 10 figures, adjustments to fit approx. PRE version

References in corpus (10)

• Coupled Replicator Equations for the Dynamics of Learning in Multiagent Systems
• Opinion Polarization by Learning from Social Feedback
• Exact solution of a modified El Farol's bar problem: Efficiency and the role of market impact
• Stability and Diversity in Collective Adaptation
• Intrinsic noise in game dynamical learning
• Cycles of cooperation and defection in imperfect learning
• Learning to play public good games
• Fixation and escape times in stochastic game learning
• Effects of noise on convergent game learning dynamics
• Emergence of Cooperative Long-term Market Loyalty in Double Auction Markets

Cited by in corpus (12)

• Perspectives on adaptive dynamical systems
• Evolutionary dynamics of the delayed replicator-mutator equation: Limit cycle and cooperation
• Intrinsic fluctuations of reinforcement learning promote cooperation
• Deep reinforcement learning in World-Earth system models to discover sustainable management strategies
• Symmetric equilibrium of multi-agent reinforcement learning in repeated prisoner's dilemma
• Emergence of Cooperation in Two-agent Repeated Games with Reinforcement Learning
• Modeling the effects of environmental and perceptual uncertainty using deterministic reinforcement learning dynamics with partial observability
• Learning enables adaptation in cooperation for multi-player stochastic games
• Interactive diversity disrupts cyclic dominance but maintains cooperation in spatial social dilemma games
• Memory-two strategies forming symmetric mutual reinforcement learning equilibrium in repeated prisoners' dilemma game
• Selfish optimization and collective learning in populations
• Evolutionary Cooperation with Game Transitions via Markov Decision Chain in Networked Population