Emergence of communication through reinforcement learning with invention

Abstract:   Reinforcement learning in a two-player Lewis signaling game is a simple model to study the emergence of communication in cooperative multi-agent systems. When there are a fixed number of states and signals there is a positive probability that a successful communication system does not emerge. If the learning dynamics are modified to include invention – rather than fixing the number of signals, at each step there is always a chance to introduce a new signal – then the system converges to successful signaling almost surely. The reinforcement process can be modeled as an interacting urn system, and the proof uses a combination of stochastic approximation techniques and comparison with simpler urn models.