Stochastic Stability of Perturbed Learning Automata in Positive-Utility Games.

This paper considers a class of reinforcement-based learning (namely,perturbed learning automata) and provides a stochastic-stability analysis inrepeatedly-played, positive-utility, strategic-form games. Prior work in thisclass of learning dynamics primarily analyzes asymptotic convergence throughstochastic approximations, where convergence can be associated with the limitpoints of an ordinary-differential equation (ODE). However, analyzing globalconvergence through an ODE-approximation requires the existence of a Lyapunovor a potential function, which naturally restricts the analysis to a fine classof games. To overcome these limitations, this paper introduces an alternativeframework for analyzing asymptotic convergence that is based upon an explicitcharacterization of the invariant probability measure of the induced Markovchain. We further provide a methodology for computing the invariant probabilitymeasure in positive-utility games, together with an illustration in the contextof coordination games.