Optimal Best Markovian Arm Identification with Fixed Confidence
arXiv:1912.00636
Abstract
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.
arXiv commentNeural Information Processing Systems (NeurIPS), 2019
Cited by in corpus (5)
- Learning to Detect an Odd Restless Markov Arm with a Trembling Hand
- Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
- Optimal Chernoff and Hoeffding Bounds for Finite State Markov Chains
- Detecting an Odd Restless Markov Arm with a Trembling Hand
- Learning to Detect an Odd Markov Arm