Continuum-Armed Bandits: A Function Space Perspective

Abstract

Continuum-armed bandits (a.k.a., black-box or $0^{th}$-order optimization) involves optimizing an unknown objective function given an oracle that evaluates the function at a query point, with the goal of using as few query points as possible. In the most well-studied case, the objective function is assumed to be Lipschitz continuous and minimax rates of simple and cumulative regrets are known in both noiseless and noisy settings. This paper studies continuum-armed bandits under more general smoothness conditions, namely Besov smoothness conditions, on the objective function. In both noiseless and noisy conditions, we derive minimax rates under simple and cumulative regrets. Our results show that minimax rates over objective functions in a Besov space are identical to minimax rates over objective functions in the smallest Hölder space into which the Besov space embeds.

References in corpus (9)

• Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
• Black-box optimization of noisy functions with unknown smoothness
• Stochastic Zeroth-order Optimization in High Dimensions
• Gradientless Descent: High-Dimensional Zeroth-Order Optimization
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• Optimization of Smooth Functions with Noisy Observations: Local Minimax Rates
• On Thompson Sampling for Smoother-than-Lipschitz Bandits
• Smooth Bandit Optimization: Generalization to Hölder Space