Learning to play games in extensive form by valuation

• 成果类型: Article
• 署名作者: Jehiel, P; Samet, D
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; Ecole des Ponts ParisTech
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2004.09.004
• 发表日期: 2005
• 页码: 129-148
• 关键词: Reinforcement learning; valuation; perfect equilibrium

摘要

Game theoretic models of learning which are based on the strategic form of the game cannot explain learning in games with large extensive form. We study learning in such games by using valuation of moves. A valuation for a player is a numeric assessment of her moves that purports to reflect their desirability. We consider a myopic player, who chooses moves with the highest valuation. Each time the game is played, the player revises her valuation by assigning the payoff obtained in the play to each of the moves she has made. We show for a repeated win-lose game that if the player has a winning strategy in the stage game, there is almost surely a time after which she always wins. When a player has more than two payoffs, a more elaborate learning procedure is required. We consider one that associates with each move the average payoff in the rounds in which this move was made. When all players adopt this learning procedure, with some perturbations, then, with probability I there is a time after which strategies that are close to subgame perfect equilibrium are played. A single player who adopts this procedure can guarantee only her individually rational payoff. (c) 2004 Elsevier Inc. All rights reserved.