Adaptive Shortest-Path Routing under Unknown and Stochastically Varying
  Link States
  We consider the adaptive shortest-path routing problem in wireless networks
under unknown and stochastically varying link states. In this problem, we aim
to optimize the quality of communication between a source and a destination
through adaptive path selection. Due to the randomness and uncertainties in the
network dynamics, the quality of each link varies over time according to a
stochastic process with unknown distributions. After a path is selected for
communication, the aggregated quality of all links on this path (e.g., total
path delay) is observed. The quality of each individual link is not observable.
We formulate this problem as a multi-armed bandit with dependent arms. We show
that by exploiting arm dependencies, a regret polynomial with network size can
be achieved while maintaining the optimal logarithmic order with time. This is
in sharp contrast with the exponential regret order with network size offered
by a direct application of the classic MAB policies that ignore arm
dependencies. Furthermore, our results are obtained under a general model of
link-quality distributions (including heavy-tailed distributions) and find
applications in cognitive radio and ad hoc networks with unknown and dynamic
communication environments.
