Applying bandit algorithms to the route choice problem

Abstract

Traffic infrastructure in major cities must be able to handle increasing demand. Building this infrastructure is expensive and not something that is done in a short time frame. Bottlenecks in the network and potential improvements must be identified for further planning and expansion. However, changes to the network are not always beneficial as shown by the Braess paradox. Therefore, it is ever more important to be able to understand the demand of its users and how it affects the network, and predict the effect changes in the network will cause. Traffic demand is normally defined in origin destination studies but this information is incomplete. It shows only the endpoints of trips but not the routes they take. To understand how each link in the network is used, a route allocation must be calculated. The problem of allocation of routes to trips is called the traffic assignment problem. We compare the performance of selected bandit algorithms with that of Q-learning in the context of the traffic assignment problem in a multi-agent reinforcement learning scenario. Specifically, non-stationary bandit algorithms were the main focus due to the nonstationarity of the problem. These algorithms were evaluated in their ability to provide traffic allocations that minimize the average travel time on a traffic network. Through experimentation, we found that bandit algorithms show potential. However, they did not perform better than Q-learning. Further study is required to better ascertain their capabilities for the problem.

Infraestrutura de tráfego em grandes cidades deve ser capaz de lidar com demanda crescente. Construção de infraestrutura tem altos custos e requer longo tempo de construção. Gargalos e melhorias em potencial em redes de tráfego devem ser identificados para planejamento e expansão. No entanto, mudanças na rede não são sempre benéficas como mostrado pelo paradoxo de Braess. Portanto, é cada vez mais importante entender a demanda dos usuários e como ela afeta a rede, e prever os efeitos que mudanças na rede vão causar. Demanda de tráfego é normalmente definida em estudos de origem e destino mas essa informação é incompleta. Ela mostra apenas o inicio e fim de cada viagem mas não as rotas seguidas. para compreender como cada aresta na rede é usada uma alocação de rotas deve ser calculada. O problema de alocação de rotas a viagens é chamado de Traffic Assignment Problem. Nós comparamos a performance de algoritmos de bandits selecionados com aquela do Q-learning no contexto do Traffic Assignment Problem em um cenário multi-agente com aprendizagem por reforço. Especificamente, algoritmos de bandits não estacionários foram o principal foco devido a não-estacionaridade do problema. Esse algoritmos foram avaliados nas suas habilidades de prover alocações de tráfego que minimizem o tempo médio de viagem. Através de experimentação, foi descoberto que os algoritmos de bandits mostram potencial. No entanto, eles não tem performance melhor que a do Q-learning. Mais estudos são necessários para melhor determinar as capacidades desses algoritmos para o problema.