Toll-based reinforcement learning for efficient equilibria in route choice

The authors thank the anonymous reviewers for their thorough analysis and valuable suggestions. Ramos, Rădulescu, and Nowé were supported by Flanders Innovation & Entrepreneurship (VLAIO), SBO project 140047: Stable MultI-agent LEarnIng for neTworks (SMILE-IT). Part of this research was also supported by the The Flanders AI Research Impulse Program, Belgium. Ramos and da Silva were partially supported by FAPERGS (grants 19/2551-0001277-2 and 17/2551-000, respectively). Bazzan was partially supported by CNPq (grant 307215/2017-2). This work was also partially supported by CNPq and CAPES scholarships.

We abuse notation here and use $n_u^{p}$ ($n_v^{p}$) to denote the start (end) node of the $p^{th}$ link of route R.

As discussed forward, links’ costs are represented by positive reals. Since for every route with a cycle we can obtain an equivalent sequence without cycles, then cycles can be ignored without loss of generality.

Observe that although the reward an agent receives is formulated as a function of its route, it actually depends on the flow of vehicles on the links that comprise that route. This is expressed by means of the VDF function, as explained in Section 2.1, whose value is a function of the flow of vehicles on its links. Furthermore, since we assume a macroscopic traffic model, we remark that all routes’ costs can be computed together, when all drivers complete their trips.

We remark that, using a macroscopic traffic model (see Section 2), travel times are computed whenever all drivers complete their trips.

Hereafter, we refer to the action with highest Q-value as the best action and to the other actions as non-best. Observe that the best action is not necessarily optimal.

In order to improve presentation, whenever it is clear from the context, we refer to $\rho({{\hbox{$\begin{matrix}\scriptscriptstyle+\\[-5.6pt]a\end{matrix}$}}}{}^t_i)$ and $\rho(\bar{a}{}^t_i)$ as ${{\hbox{$\begin{matrix}\scriptscriptstyle+\\[-5.6pt]\rho\end{matrix}$}}}{}^t_i$ and $\bar{\rho}{}^t_i$, respectively. Whenever possible, we also omit t and i.

The road networks are publicly available at .

As for the BB networks, we enforced the route with fewest links among the shortest ones, otherwise the system optimum would not be attainable, as discussed in Ramos (2018).

We remark that, although other tolling schemes are also available in the literature (see discussion in Section 3.2), these cannot be directly applied to our problem. This is because such approaches do not present a learning scheme and cannot be run distributedly by the drivers.

Since our objective here is to compare the quality of the solutions obtained by the methods, we adopted the traditional version of difference rewards (DR, which assumes full observability in order to compute the difference signals) rather than the most recent, function approximation-based version (FADR) by Colby et al. (2016). The reason is that DR obtains better results than FADR (as discussed in Section 3). Hence, we believe this choice promotes a fairer comparison of DR against our method.