2015/04/22 by Wesley Cowan, Cowan, Wesley, Honda, Junya +3 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1504.05823
15 pages 3 figures
openalex publication_date 2015/04/22 · arxiv created 2015/06/03 · arxiv updated 2015/06/04 · openalex created_date 2022/08/30 · openalex updated_date 2026/07/28
Consider the problem of sampling sequentially from a finite number of N ≥ 2 populations, specified by random variables Xik, i = 1,… , N, and k = 1, 2, …; where Xik denotes the outcome from population i the kth time it is sampled. It is assumed that for each fixed i, \ Xik \k ≥ 1 is a sequence of i.i.d. normal random variables, with unknown mean μi and unknown variance σi2. The objective is to have a policy π for deciding from which of the N populations to sample form at any time n=1,2,… so as to maximize the expected sum of outcomes of n samples or equivalently to minimize the regret due to lack on information of the parameters μi and σi2. In this paper, we present a simple inflated sample mean (ISM) index policy that is asymptotically optimal in the sense of Theorem 4 below. This resolves a standing open problem from Burnetas and Katehakis (1996). Additionally, finite horizon regret bounds are given.