This paper considers a class of reinforcement-learning that belongs to the family of Learning Automata and provides a stochastic-stability analysis in strategic-form games. For this class of dynamics, convergence to pure Nash equilibria has been demonstrated only for the fine class of potential games. Prior work primarily provides convergence properties of the dynamics through stochastic approximations, where the asymptotic behavior can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through the ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the applicabity of these algorithms to a fine class of games. To overcome these limitations, this paper introduces an alternative framework for analyzing stochastic-stability that is based upon an explicit characterization of the (unique) invariant probability measure of the induced Markov chain.
This issue has also been raised by @cite_19 @cite_0 . Reference @cite_19 considered the model by @cite_6 and showed that convergence to non-Nash pure strategy profiles can be excluded as long as @math for all @math and @math . On the other hand, convergence to non-Nash action profiles was not an issue with the urn model of @cite_5 (as analyzed in @cite_0 ). However, the use of an urn-process type step-size sequence significantly reduces the applicability of the reinforcement learning scheme. In conclusion, the perturbation parameter @math may serve as a design tool for reinforcing convergence to Nash equilibria without necessarily employing an urn-process type step-size sequence. For engineering applications this is a desirable feature.
@cite_0 @cite_19 @cite_5 @cite_6
2096702014 1989107041 1564229172 2030329396
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. In this paper we study a stochastic learning model for 2, 2 normal form games that are played repeatedly. The main emphasis is put on the emergence of cycles. We assume that the players have neither information about the payoff matrix of their opponent nor about their own. At every round each player can only observe his or her action and the payoff he or she receives. We prove that the learning algorithm, which is modeled by an urn scheme proposed by Arthur (1993), leads with positive probability to a cycling of strategy profiles if the game has a mixed Nash equilibrium. In case there are strict Nash equilibria, the learning process converges a.s. to the set of Nash equilibria. 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 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.