# Instance-dependent Stochastic Lipschitz bandit

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 35 references that are in the map.
- First posted on arXiv 28 May 2026.

## Builds on (most cited first, 21 of 21)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes](https://mlsanity.com/paper/1909.02553/) (2019)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Robust Lipschitz Bandits to Adversarial Corruptions](https://mlsanity.com/paper/2305.18543/) (2023)
- [Online learning with kernel losses](https://mlsanity.com/paper/1802.09732/) (2018)
- [A Lipschitz Bandits Approach for Continuous Hyperparameter Optimization](https://mlsanity.com/paper/2302.01539/) (2023)
- [Stochastic simultaneous optimistic optimization](https://mlsanity.com/paper/2604.24537/) (2026)
- [Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates](https://mlsanity.com/paper/2102.01977/) (2021)
- [Instance-Dependent Regret Analysis of Kernelized Bandits](https://mlsanity.com/paper/2203.06297/) (2022)
- [Federated X-Armed Bandit](https://mlsanity.com/paper/2205.15268/) (2022)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctions](https://mlsanity.com/paper/1703.02567/) (2017)
- [PyXAB -- A Python Library for X-Armed Bandit and Online Blackbox Optimization Algorithms](https://mlsanity.com/paper/2303.04030/) (2023)
- [Certified Multi-Fidelity Zeroth-Order Optimization](https://mlsanity.com/paper/2308.00978/) (2023)
- [Tree Search-Based Evolutionary Bandits for Protein Sequence Optimization](https://mlsanity.com/paper/2401.06173/) (2024)
- [Non-Stationary Lipschitz Bandits](https://mlsanity.com/paper/2505.18871/) (2025)

## Abstract (arXiv)

We study the Lipschitz bandit problem, where a learner sequentially maximizes an unknown Lipschitz function f over a domain X subset [0,1]d using noisy pointwise evaluations. Existing regret bounds are either worst-case, scaling as tildeTheta left ( Td+1/d+2right ), or adaptive via the zooming dimension dz, yielding tildeTheta left ( Tdz+1/dz+2right ). However, such zooming-based guarantees are only partially instance-dependent, as they depend solely on the asymptotic growth of near-optimal level sets and fail to capture finer structural properties of f. We provide an analysis and an algorithm that characterizes the regret through integrals of the suboptimality gap of f over its level sets. This yields regret bounds that adapt to the local growth of level sets, rather than only their asymptotic behavior. As a corollary, when the set of maximizers has dimension d^star>0, we obtain improved adaptive rates of order tildeO left ( Tdz+1 / max(dz,d^star)+2right ) strictly improving over classical zooming bounds in this regime. Finally, we extend our analysis to the full-information setting (Lipschitz experts) and show how some of the regularity assumptions can be relaxed.