Q-learning for adaptive load based routing
Ann Nowé, Kris Steenhaut, Mohamed Fakir, Katja Verbeeck · 2002
The paper deals with the control problem of routing in packet switched networks. Using Q-learning an adaptive, distributed and autonomous routing strategy can be obtained. The objective of the Q-learner under study is to balance the load such that average packet delivery time is optimised. If pure Q-learning is applied to routing each source has to learn the expected cost for sending a message via each of its neighbours for all destinations. Since Q-learning is basically a trial and error method packets have to be sent along non-optimal paths, which artificially increases the load. To reduce this effect and to speed up the learning a variant of Q-learning has been developed. Exploration and exploitation are partially decoupled such that stabilising features can be included in the Q-learning algorithm to cope with instabilities and overhead that might be caused by the costly exploitation in search of alternative paths. In the paper the above statements are justified mathematically and supported by the results of experiments.