# Polynomial Cost of Adaptation for X -Armed Bandits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2019.

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

- [Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces](https://mlsanity.com/paper/2207.05849/) (2022)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Adaptation to Misspecified Kernel Regularity in Kernelised Bandits](https://mlsanity.com/paper/2304.13830/) (2023)
- [Infinite Action Contextual Bandits with Reusable Data Exhaust](https://mlsanity.com/paper/2302.08551/) (2023)
- [Graph Learning Is Suboptimal in Causal Bandits](https://mlsanity.com/paper/2510.16811/) (2025)
- [Smoothness-Adaptive Dynamic Pricing with Nonparametric Demand Learning](https://mlsanity.com/paper/2310.07558/) (2023)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)

## Abstract (arXiv)

In the context of stochastic continuum-armed bandits, we present an algorithm that adapts to the unknown smoothness of the objective function. We exhibit and compute a polynomial cost of adaptation to the H"older regularity for regret minimization. To do this, we first reconsider the recent lower bound of Locatelli and Carpentier [20], and define and characterize admissible rate functions. Our new algorithm matches any of these minimal rate functions. We provide a finite-time analysis and a thorough discussion about asymptotic optimality.