A Sensing Policy Based on Confidence Bounds and a Restless Multi-Armed
  Bandit Model
  A sensing policy for the restless multi-armed bandit problem with stationary
but unknown reward distributions is proposed. The work is presented in the
context of cognitive radios in which the bandit problem arises when deciding
which parts of the spectrum to sense and exploit. It is shown that the proposed
policy attains asymptotically logarithmic weak regret rate when the rewards are
bounded independent and identically distributed or finite state Markovian.
Simulation results verifying uniformly logarithmic weak regret are also
presented. The proposed policy is a centrally coordinated index policy, in
which the index of a frequency band is comprised of a sample mean term and a
confidence term. The sample mean term promotes spectrum exploitation whereas
the confidence term encourages exploration. The confidence term is designed
such that the time interval between consecutive sensing instances of any
suboptimal band grows exponentially. This exponential growth between suboptimal
sensing time instances leads to logarithmically growing weak regret. Simulation
results demonstrate that the proposed policy performs better than other similar
methods in the literature.
