2020/10/08 by Sayin, Muhammed O., Parise, Francesca, Ozdaglar, Asuman · 5 citations
#Computer Science and Game Theory (cs.GT) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2010.04223
We present a novel variant of fictitious play dynamics combining classical fictitious play with Q-learning for stochastic games and analyze its convergence properties in two-player zero-sum stochastic games. Our dynamics involves players forming beliefs on the opponent strategy and their own continuation payoff (Q-function), and playing a greedy best response by using the estimated continuation payoffs. Players update their beliefs from observations of opponent actions. A key property of the learning dynamics is that update of the beliefs on Q-functions occurs at a slower timescale than update of the beliefs on strategies. We show both in the model-based and model-free cases (without knowledge of player payoff functions and state transition probabilities), the beliefs on strategies converge to a stationary mixed Nash equilibrium of the zero-sum stochastic game.