Learning to Detect an Odd Markov Arm A multiarmed 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. 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.

An ArmWise Randomization Approach to Combinatorial Linear SemiBandits Combinatorial linear semibandits (CLS) are widely applicable frameworks of sequential decisionmaking, in which a learner chooses a subset of arms from a given set of arms associated with feature vectors. Existing algorithms work poorly for the clustered case, in which the feature vectors form several large clusters. This shortcoming is critical in practice because it can be found in many applications, including recommender systems. In this paper, we clarify why such a shortcoming occurs, and we introduce a key technique of armwise randomization to overcome it. We propose two algorithms with this technique: the perturbed C2 UCB (PC2 UCB) and the Thompson sampling (TS). Our empirical evaluation with artificial and realworld datasets demonstrates that the proposed algorithms with the armwise randomization technique outperform the existing algorithms without this technique, especially for the clustered case. Our contributions also include theoretical analyses that provide high probability asymptotic regret bounds for our algorithms.