Stochastic Stability of Perturbed Learning Automata in Positive-Utility Games

DOI10.1109/TAC.2019.2895300MaRDI QIDQ5211206zbMATH OpenOpenAlexWikidataFDO

Authors Georgios C. Chasparis

Publication date 28 January 2020

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.05859

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Computational learning theory (68Q32) Formal languages and automata (68Q45) Distributed algorithms (68W15) Applications of game theory (91A80) Stochastic stability in control theory (93E15)

Abstract: This paper considers a class of reinforcement-based learning (namely, perturbed learning automata) and provides a stochastic-stability analysis in repeatedly-played, positive-utility, finite strategic-form games. Prior work in this class of learning dynamics primarily analyzes asymptotic convergence through stochastic approximations, where convergence can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through an ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the analysis to a fine class of games. To overcome these limitations, this paper introduces an alternative framework for analyzing asymptotic convergence that is based upon an explicit characterization of the invariant probability measure of the induced Markov chain. We further provide a methodology for computing the invariant probability measure in positive-utility games, together with an illustration in the context of coordination games.

Cited in

(6)

• Large deviations and stochastic stability in population games
• Measurement-based efficient resource allocation with demand-side adjustments
• On the robustness of learning in games with stochastically perturbed payoff observations
• Corrections to “Stochastic Stability of Perturbed Learning Automata in Positive-Utility Games” [Nov 19 4454-4469]
• Stability of learning dynamics in two-agent, imperfect-information games
• Stability properties for learning with heterogeneous expectations and multiple equilibria

This page was built for publication: Stochastic Stability of Perturbed Learning Automata in Positive-Utility Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211206)