# A Dimension-free Algorithm for Contextual Continuum-armed Bandits

arXiv: https://arxiv.org/abs/1907.06550 · HTML: https://mlsanity.com/paper/1907.06550/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2019.

## Built on by (most cited first, 2 of 2)

- [A conversion theorem and minimax optimality for continuum contextual bandits](https://mlsanity.com/paper/2406.05714/) (2024)
- [Beyond ATE: Multi-Criteria Design for A/B Testing](https://mlsanity.com/paper/2509.05864/) (2025)

## Abstract (arXiv)

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.