Learning automata in games with memory with application to circuit-switched routing

A general setting is considered in which autonomous users interact by means of a finite-state controlled Markov process. This process is driven by the collective actions of all users, and individual users receive separate rewards according to its state. It is assumed that each user chooses its actions via a reinforcement learning algorithm based on its local information. The dynamic behavior of user strategies is characterized for small values of a step-size parameter adopted in learning. The general form of equilibria is obtained and is shown to be analogous to Wardrop equilibria if users update their strategies on a faster time-scale compared to the underlying process. The results are illustrated in the context of routing in circuit-switched communication networks.