Timezone: »

Optimal Best Markovian Arm Identification with Fixed Confidence
Vrettos Moulos

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #19

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.

Author Information

Vrettos Moulos (UC Berkeley)