A Dimension-free Algorithm for Contextual Continuum-armed Bandits
This addresses the scalability issue in high-dimensional bandit problems for applications like online advertising or recommendation systems, though it is incremental as it builds on existing assumptions.
The paper tackles the curse of dimensionality in contextual continuum-armed bandits by developing an algorithm that achieves regret $ ilde{O}(T^{ rac{d_x+1}{d_x+2}})$ when the payoff function is globally concave in arms, compared to the optimal $ ilde{O}(T^{ rac{d_x+d_y+1}{d_x+d_y+2}})$ for Lipschitz-continuous functions, showing that the arm dimension can be overcome with mild structural assumptions.
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.