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
$\tilde{O}(T^{\frac{d_x+d_y+1}{d_x+d_y+2}})$, where $d_x$ and $d_y$ are the
dimensions of contexts and arms, and thus suffers from the curse of
dimensionality. We develop an algorithm that achieves regret
$\tilde{O}(T^{\frac{d_x+1}{d_x+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.
