2017/02/26 by Rahul Singh, Singh, Rahul, Taposh Banerjee +1
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems #Smart Grid Energy Management
paper · pdf · doi:10.48550/arxiv.1702.08000
openalex publication_date 2017/02/26 · openalex created_date 2017/03/16 · openalex updated_date 2026/07/28
We consider the problem of designing an allocation rule or an "online learning algorithm" for a class of bandit problems in which the set of control actions available at each time s is a convex, compact subset of ℝd. Upon choosing an action x at time s, the algorithm obtains a noisy value of the unknown and time-varying function fs evaluated at x. The "regret" of an algorithm is the gap between its expected reward, and the reward earned by a strategy which has the knowledge of the function fs at each time s and hence chooses the action xs that maximizes fs. For this non-stationary bandit problem set-up, we consider two variants of the Kiefer Wolfowitz (KW) algorithm i) KW with fixed step-size β, and ii) KW with sliding window of length L. We show that if the number of times that the function fs varies during time T is o(T), and if the learning rates of the proposed algorithms are chosen "optimally", then the regret of the proposed algorithms is o(T), and hence the algorithms are asymptotically efficient.