A Dimension-free Algorithm for Contextual Continuum-armed Bandits

In contextual continuum-armed bandits, the contexts x and the arms y are both continuous and drawn from high-dimensional spaces. The payoff function to learn f(x,y) does not have a particular parametric form. The literature has shown that for Lipschitz-continuous functions, the optimal regret is tildeO(T^fracdx+dy+1dx+dy+2), where dx and dy are the dimensions of contexts and arms, and thus suffers from the curse of dimensionality. We develop an algorithm that achieves regret tildeO(T^fracdx+1dx+2) when f is globally concave in y. The global concavity is a common assumption in many applications. The algorithm is based on stochastic approximation and estimates the gradient information in an online fashion. Our results generate a valuable insight that the curse of dimensionality of the arms can be overcome with some mild structures of the payoff function.