  We give a complete characterization of the sampling complexity of best
Markovian arm identification in one-parameter Markovian bandit models. We
derive instance specific nonasymptotic and asymptotic lower bounds which
generalize those of the IID setting. We analyze the Track-and-Stop strategy,
initially proposed for the IID setting, and we prove that asymptotically it is
at most a factor of four apart from the lower bound. Our one-parameter
Markovian bandit model is based on the notion of an exponential family of
stochastic matrices for which we establish many useful properties. For the
analysis of the Track-and-Stop strategy we derive a novel concentration
inequality for Markov chains that may be of interest in its own right.
