Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Chapter 6. Fully Distributed Learning Al... > 6.3 Trial-and-Error Learning: Learni... - Pg. 158

158 CHAPTER 6 Fully Distributed Learning Algorithms We would like to mention once again that, usually, game-theoretic modeling assumes rational players, and that rationality is common knowledge. In the fully dis- tributed learning schemes described in this chapter, each player is assumed to select a learning pattern, but does not need to know whether the other players are rational or not. 6.3 TRIAL-AND-ERROR LEARNING: LEARNING BY EXPERIMENTING We now present a completely uncoupled (fully distributed) learning rule such that, when used by all players in a finite game, stage-by-stage play comes close to pure Nash equilibrium play a high proportion of the time, provided that the game is generic, and has such a pure equilibrium. The interactive learning by experimentation is in discrete time, t N, t 1. At each time t, a player j has his own state s j,t which contains his own decision a j,t and his own perceived utility u j,t i.e., s j,t = (a j,t , u j,t ). At time t + 1, each player does some experiment, with some probability j (0, 1). The player keeps the action a j,t at time t + 1 when he does not experiment, otherwise he/she plays a j A j drawn uniformly at random. If the received utility after experi-