The route to chaos of reinforcement learning in routing networks

Without a central authority to manage traffic in a routing network, can a society consisting of uncoordinated, self-interested agents automatically reach the optimal traffic flow that minimizes the travel time of the society? For decades, game theory framework has been applied to study a set of stable strategies (Nash equilibria) that self-interested agents might adopt in these routing games. However, such framework focuses on the identification of equilibria, rather than on whether such equilibria are attainable if the agents individually and strategically learn from the history. In this work, we show that collective behaviors of reinforcement learning agents can be driven away from the Nash equilibrium. In fact, a period-doubling bifurcation route to chaos naturally emerges as the traffic load increases. Interestingly, even when the collective behaviors are chaotic (in the Li-Yorke sense), their ergodic average still coincides exactly with the Nash equilibrium. Lastly, we report the numerical evidence of the Feigenbaum's universality class in our non-unimodal map.