  A multi-armed bandit with finitely many arms is studied when each arm is a
homogeneous Markov process on an underlying finite state space. The transition
law of one of the arms, referred to as the odd arm, is different from the
common transition law of all other arms. A learner, who has no knowledge of the
above transition laws, has to devise a sequential test to identify the index of
the odd arm as quickly as possible, subject to an upper bound on the
probability of error. For this problem, we derive an asymptotic lower bound on
the expected stopping time of any sequential test of the learner, where the
asymptotics is as the probability of error vanishes. Furthermore, we propose a
sequential test, and show that the asymptotic behaviour of its expected
stopping time comes arbitrarily close to that of the lower bound. Prior works
deal with independent and identically distributed arms, whereas our work deals
with Markov arms. Our analysis of the rested Markov setting is a key first step
in understanding the difficult case of restless Markov setting, which is still
open.
