Reinforcement learning means learning a policy--a mapping of observations into actions--based on feedback from the environment. The learning can be viewed as browsing a set of policies while evaluating them by trial through interaction with the environment. We present an application of gradient ascent algorithm for reinforcement learning to a complex domain of packet routing in network communication and compare the performance of this algorithm to other routing methods on a benchmark problem.
Generally speaking, value-search algorithms have been more extensively investigated than policy search ones in the domain of communications. Value-search (Q-learning) algorithms have arrived at promising results. Boyan and Littman's @cite_9 algorithm - Q-routing, proves superior to non-adaptive techniques based on shortest path, and robust with respect to dynamic variations in the simulation on a variety of network topology, including an irregular @math grid and 116-node lata phone network. It regulates the trade-off between the number of nodes a packet has to traverse and the possibility of congestion.
@cite_9
2156666755
This paper describes the Q-routing algorithm for packet routing, in which a reinforcement learning module is embedded into each node of a switching network. Only local communication is used by each node to keep accurate statistics on which routing decisions lead to minimal delivery times. In simple experiments involving a 36-node, irregularly connected network, Q-routing proves superior to a nonadaptive algorithm based on precomputed shortest paths and is able to route efficiently even when critical aspects of the simulation, such as the network load, are allowed to vary dynamically. The paper concludes with a discussion of the tradeoff between discovering shortcuts and maintaining stable policies.