ASYMPTOTICALLY OPTIMAL MULTI-ARMED BANDIT POLICIES UNDER A COST CONSTRAINT. Issue 3 (5th October 2016)

• Record Type: Journal Article
• Authors: Burnetas, Apostolos; Kanavetas, Odysseas; Katehakis, Michael N.
• Is Part Of: Probability in the engineering and informational sciences. Volume 31:Issue 3(2017)
• Page Start: 284
• Page End: 310
• Publication Date: 2016-10-05
• Subjects: applied probability, -- stochastic modelling; Probabilities -- Periodicals; Engineering -- Statistical methods -- Periodicals; Information science -- Statistical methods -- Periodicals; 519.202462
• DOI: 10.1017/S026996481600036X
• Languages: English
• ISSNs: 0269-9648

Abstract

Abstract : We consider the multi-armed bandit problem under a cost constraint. Successive samples from each population are i.i.d. with unknown distribution and each sample incurs a known population-dependent cost. The objective is to design an adaptive sampling policy to maximize the expected sum of n samples such that the average cost does not exceed a given bound sample-path wise. We establish an asymptotic lower bound for the regret of feasible uniformly fast convergent policies, and construct a class of policies, which achieve the bound. We also provide their explicit form under Normal distributions with unknown means and known variances.