Learning to Minimise Regret in Route Choice

Reinforcement learning (RL) is a challenging task, especially in highly competitive multiagent scenarios. We consider the route choice problem, in which self-interested drivers aim at choosing routes that minimise their travel times. Employing RL here is challenging because agents must adapt to each others' decisions. In this paper, we investigate how agents can overcome such condition by minimising the regret associated with their decisions. Regret measures how much worse an agent performs on average compared to the best fixed action in hindsight. We present a simple yet effective regret-minimising algorithm to address this scenario. To this regard, we introduce the action regret, which measures the performance of each route in comparison to the best one, and employ it as reinforcement signal. Given that agents do not know the cost of all routes (except for the currently taken ones) in advance, we also devise a method through which they can estimate the action regret. We analyse the theoretical properties of our method and prove it minimises the agents' regret by means of the action regret. Furthermore, we provide formal guarantees on the agents' convergence to a φ-approximate User Equilibrium, where φ is the bound on the agents' regret. To the best of our knowledge, this is the first work in which RL-agents are formally proven to converge to an approximate UE, without further assumptions, in the context of route choice. CCS Concepts •Theory of computation → Multi-agent reinforcement learning; Exact and approximate computation of equilibria; Convergence and learning in games; •Computing methodologies → Multi-agent reinforcement learning; Multi-agent systems;