A Dimension-free Algorithm for Contextual Continuum-armed Bandits

2019/07/15 by Wenhao Li, Li, Wenhao, Ningyuan Chen +3 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1907.06550

openalex publication_date 2019/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 O(T^{(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 O(T^{(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.

Citations

• A Stochastic Approximation Method
• Stochastic Estimation of the Maximum of a Regression Function
• The Nonstochastic Multiarmed Bandit Problem

Cited by

• Beyond ATE: Multi-Criteria Design for A/B Testing

Related

• Continuum armed bandit problem of few variables in high dimensions
• A Time and Space Efficient Algorithm for Contextual Linear Bandits
• Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit
• Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting