Optimal Adaptive Learning in Uncontrolled Restless Bandit Problems
  In this paper we consider the problem of learning the optimal policy for
uncontrolled restless bandit problems. In an uncontrolled restless bandit
problem, there is a finite set of arms, each of which when pulled yields a
positive reward. There is a player who sequentially selects one of the arms at
each time step. The goal of the player is to maximize its undiscounted reward
over a time horizon T. The reward process of each arm is a finite state Markov
chain, whose transition probabilities are unknown by the player. State
transitions of each arm is independent of the selection of the player. We
propose a learning algorithm with logarithmic regret uniformly over time with
respect to the optimal finite horizon policy. Our results extend the optimal
adaptive learning of MDPs to POMDPs.
