2017/12/11 by Gayathri R Prabhu, Prabhu, Gayathri R, Srikrishna Bhashyam +5 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Advanced Statistical Process Monitoring #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1712.03682
openalex publication_date 2017/12/11 · openalex created_date 2023/02/15 · openalex updated_date 2026/07/28
The problem of detecting an odd arm from a set of K arms of a multi-armed\nbandit, with fixed confidence, is studied in a sequential decision-making\nscenario. Each arm's signal follows a distribution from a vector exponential\nfamily. All arms have the same parameters except the odd arm. The actual\nparameters of the odd and non-odd arms are unknown to the decision maker.\nFurther, the decision maker incurs a cost for switching from one arm to\nanother. This is a sequential decision making problem where the decision maker\ngets only a limited view of the true state of nature at each stage, but can\ncontrol his view by choosing the arm to observe at each stage. Of interest are\npolicies that satisfy a given constraint on the probability of false detection.\nAn information-theoretic lower bound on the total cost (expected time for a\nreliable decision plus total switching cost) is first identified, and a\nvariation on a sequential policy based on the generalised likelihood ratio\nstatistic is then studied. Thanks to the vector exponential family assumption,\nthe signal processing in this policy at each stage turns out to be very simple,\nin that the associated conjugate prior enables easy updates of the posterior\ndistribution of the model parameters. The policy, with a suitable threshold, is\nshown to satisfy the given constraint on the probability of false detection.\nFurther, the proposed policy is asymptotically optimal in terms of the total\ncost among all policies that satisfy the constraint on the probability of false\ndetection.\n