2015/09/09 by Apostolos Burnetas, Burnetas, Apostolos N., Odysseas Kanavetas +3
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Smart Grid Energy Management
paper · pdf · doi:10.48550/arxiv.1509.02857
openalex publication_date 2015/09/09 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We develop asymptotically optimal policies for the multi armed bandit (MAB),\nproblem, under a cost constraint. This model is applicable in situations where\neach sample (or activation) from a population (bandit) incurs a known bandit\ndependent cost. Successive samples from each population are iid random\nvariables with unknown distribution. The objective is to design a feasible\npolicy for deciding from which population to sample from, so as to maximize the\nexpected sum of outcomes of n total samples or equivalently to minimize the\nregret due to lack on information on sample distributions, For this problem we\nconsider the class of feasible uniformly fast (f-UF) convergent policies, that\nsatisfy the cost constraint sample-path wise. We first establish a necessary\nasymptotic lower bound for the rate of increase of the regret function of f-UF\npolicies. Then we construct a class of f-UF policies and provide conditions\nunder which they are asymptotically optimal within the class of f-UF policies,\nachieving this asymptotic lower bound. At the end we provide the explicit form\nof such policies for the case in which the unknown distributions are Normal\nwith unknown means and known variances.\n