Technical Program

Paper Detail

Paper Title Learning to Detect an Odd Markov Arm
Paper IdentifierFR1.R5.4
Authors P. N. Karthik, Rajesh Sundaresan, Indian Institute of Science, India
Session Bandits
Location Saint Victor, Level 3
Session Time Friday, 12 July, 09:50 - 11:10
Presentation Time Friday, 12 July, 10:50 - 11:10
Manuscript  Click here to download the manuscript
Abstract 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 iid arms, whereas our work deals with Markov arms.