Synchronous and Asynchronous Learning by Responsive Learning Automata
Eric Friedman, Scott Shenker · RePEc: Research Papers in Economics · 2010
We consider the ability of economic agents to learn in a decentralized environment in which agents do not know the (stochastic) payoff matrix and can not observe their opponents' actions; they merely know, at each stage of the game, their own action and the resulting payoff. We discuss the requirements for learning in such an environment, and show that a simple probabilistic learning algorithm satisfies two important optimizing properties: i) When placed in an unknown but eventually stationary random environment, they converge in bounded time, in a sense we make precise, to strategies that maximize average payoff. ii) They satisfy a monotonicity property (related to the "law of the effect") in which increasing the payoffs for a given strategy increases the probability of that strategy being played in the future. We then study how groups of such learners interact in a general game. We show that synchronous groups of these learners converge to the serially undominated set. ...