Aspiration-based Perturbed Learning Automata

2018/03/07 by Chasparis, Georgios C.
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1803.02751

Abstract

This paper introduces a novel payoff-based learning scheme for distributed optimization in repeatedly-played strategic-form games. Standard reinforcement-based learning exhibits several limitations with respect to their asymptotic stability. For example, in two-player coordination games, payoff-dominant (or efficient) Nash equilibria may not be stochastically stable. In this work, we present an extension of perturbed learning automata, namely aspiration-based perturbed learning automata (APLA) that overcomes these limitations. We provide a stochastic stability analysis of APLA in multi-player coordination games. We further show that payoff-dominant Nash equilibria are the only stochastically stable states.

Related

• Aspiration-based Perturbed Learning Automata in Games with Noisy Utility Measurements. Part B: Stochastic Stability in Weakly Acyclic Games
• Aspiration-based Perturbed Learning Automata in Games with Noisy Utility Measurements. Part A: Stochastic Stability in Non-zero-Sum Games
• Stochastic Stability of Perturbed Learning Automata in Positive-Utility Games
• Stochastic Stability Analysis of Perturbed Learning Automata with\n Constant Step-Size in Strategic-Form Games
• Pareto-Optimal Algorithms for Learning in Games