2013/04/21 by Hemant Tyagi, Tyagi, Hemant, Bernd Gärtner +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1304.5793
openalex publication_date 2013/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the stochastic and adversarial settings of continuum armed bandits where the arms are indexed by [0,1]d. The reward functions r:[0,1]d -> R are assumed to intrinsically depend on at most k coordinate variables implying r(x1,..,xd) = g(xi1,..,xik) for distinct and unknown i1,..,ik from 1,..,d and some locally Holder continuous g:[0,1]k -> R with exponent 0 < alpha <= 1. Firstly, assuming (i1,..,ik) to be fixed across time, we propose a simple modification of the CAB1 algorithm where we construct the discrete set of sampling points to obtain a bound of O(n^((alpha+k)/(2*alpha+k)) (log n)^((alpha)/(2*alpha+k)) C(k,d)) on the regret, with C(k,d) depending at most polynomially in k and sub-logarithmically in d. The construction is based on creating partitions of 1,..,d into k disjoint subsets and is probabilistic, hence our result holds with high probability. Secondly we extend our results to also handle the more general case where (i1,...,ik) can change over time and derive regret bounds for the same.