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.
A type of learning dynamics which is quite closely related to the dynamics of Table is the discrete-time version of (cf., @cite_12 ). There have been several variations with respect to the selection of the step-size sequence. For example, Arthur @cite_15 considered a similar rule, with @math and step-size @math , for some positive constant @math and for @math (in the place of the constant step-size @math of )). A comparative model is also used by Hopkins and Posch in @cite_0 , with @math , where @math is the accumulated benefits of agent @math up to time @math , which gives rise to the urn process of Erev-Roth @cite_7 . Some similarities are also shared with the Cross' learning model of @cite_25 , where @math and @math , and its modification presented by Leslie in @cite_1 , where @math , instead, is decreasing with time.
@cite_7 @cite_1 @cite_0 @cite_15 @cite_25 @cite_12
1564229172 2096702014 2030329396 1995622844 261814290
The authors examine learning in all experiments they could locate involving one hundred periods or more of games with a unique equilibrium in mixed strategies, and in a new experiment. They study both the ex post ('best fit') descriptive power of learning models, and their ex ante predictive power, by simulating each experiment using parameters estimated from the other experiments. Even a one-parameter reinforcement learning model robustly outperforms the equilibrium predictions. Predictive power is improved by adding 'forgetting' and 'experimentation,' or by allowing greater rationality as in probabilistic fictitious play. Implications for developing a low-rationality, cognitive game theory are discussed. Copyright 1998 by American Economic Association. This paper investigates the properties of the most common form of reinforcement learning (the "basic model" of Erev and Roth, American Economic Review, 88, 848-881, 1998). Stochastic approximation theory has been used to analyse the local stability of fixed points under this learning process. However, as we show, when such points are on the boundary of the state space, for example, pure strategy equilibria, standard results from the theory of stochastic approximation do not apply. We offer what we believe to be the correct treatment of boundary points, and provide a new and more general result: this model of learning converges with zero probability to fixed points which are unstable under the Maynard Smith or adjusted version of the evolutionary replicator dynamics. For two player games these are the fixed points that are linearly unstable under the standard replicator dynamics. This paper explores the idea of constructing theoretical economic agents that behave like actual human agents and using them in neoclassical economic models. It does this in a repeated-choice setting by postulating "artificial agents" who use a learning algorithm calibrated against human learning data from psychological experiments. The resulting calibrated algorithm appears to replicate human learning behavior to a high degree and reproduces several "stylized facts" of learning. It can, therefore, be used to replace the idealized, perfectly rational agents in appropriate neoclassical models with "calibrated agents" that represent actual human behavior. The paper discusses the possibilities of using the algorithm to represent human learning in normal-form stage games and in more general neoclassical models in economics. It explores the likelihood of convergence to long-run optimality and to Nash behavior, and the "characteristic learning time" implicit in human adaptation in the economy. This paper considers a version of Bush and Mosteller's stochastic learning theory in the context of games. We compare this model of learning to a model of biological evolution. The purpose is to investigate analogies between learning and evolution. We and that in the continuous time limit the biological model coincides with the deterministic, continuous time replicator process. We give conditions under which the same is true for the learning model. For the case that these conditions do not hold, we show that the replicator process continues to play an important role in characterising the continuous time limit of the learning model, but that a di®erent e®ect ( Matching") enters as well.(This abstract was borrowed from another version of this item.) 1 Preliminaries.- 1.1 Introduction.- 1.2 Measures and Functions.- 1.3 Weak Topologies.- 1.4 Convergence of Measures.- 1.5 Complements.- 1.6 Notes.- I Markov Chains and Ergodicity.- 2 Markov Chains and Ergodic Theorems.- 2.1 Introduction.- 2.2 Basic Notation and Definitions.- 2.3 Ergodic Theorems.- 2.4 The Ergodicity Property.- 2.5 Pathwise Results.- 2.6 Notes.- 3 Countable Markov Chains.- 3.1 Introduction.- 3.2 Classification of States and Class Properties.- 3.3 Limit Theorems.- 3.4 Notes.- 4 Harris Markov Chains.- 4.1 Introduction.- 4.2 Basic Definitions and Properties.- 4.3 Characterization of Harris recurrence.- 4.4 Sufficient Conditions for P.H.R.- 4.5 Harris and Doeblin Decompositions.- 4.6 Notes.- 5 Markov Chains in Metric Spaces.- 5.1 Introduction.- 5.2 The Limit in Ergodic Theorems.- 5.3 Yosida's Ergodic Decomposition.- 5.4 Pathwise Results.- 5.5 Proofs.- 5.6 Notes.- 6 Classification of Markov Chains via Occupation Measures.- 6.1 Introduction.- 6.2 A Classification.- 6.3 On the Birkhoff Individual Ergodic Theorem.- 6.4 Notes.- II Further Ergodicity Properties.- 7 Feller Markov Chains.- 7.1 Introduction.- 7.2 Weak-and Strong-Feller Markov Chains.- 7.3 Quasi Feller Chains.- 7.4 Notes.- 8 The Poisson Equation.- 8.1 Introduction.- 8.2 The Poisson Equation.- 8.3 Canonical Pairs.- 8.4 The Cesaro-Averages Approach.- 8.5 The Abelian Approach.- 8.6 Notes.- 9 Strong and Uniform Ergodicity.- 9.1 Introduction.- 9.2 Strong and Uniform Ergodicity.- 9.3 Weak and Weak Uniform Ergodicity.- 9.4 Notes.- III Existence and Approximation of Invariant Probability Measures.- 10 Existence of Invariant Probability Measures.- 10.1 Introduction and Statement of the Problems.- 10.2 Notation and Definitions.- 10.3 Existence Results.- 10.4 Markov Chains in Locally Compact Separable Metric Spaces.- 10.5 Other Existence Results in Locally Compact Separable Metric Spaces.- 10.6 Technical Preliminaries.- 10.7 Proofs.- 10.8 Notes.- 11 Existence and Uniqueness of Fixed Points for Markov Operators.- 11.1 Introduction and Statement of the Problems.- 11.2 Notation and Definitions.- 11.3 Existence Results.- 11.4 Proofs.- 11.5 Notes.- 12 Approximation Procedures for Invariant Probability Measures.- 12.1 Introduction.- 12.2 Statement of the Problem and Preliminaries.- 12.3 An Approximation Scheme.- 12.4 A Moment Approach for a Special Class of Markov Chains.- 12.5 Notes.