Instance-dependent Stochastic Lipschitz bandit
Abstract
We study the Lipschitz bandit problem, where a learner sequentially maximizes an unknown Lipschitz function f over a domain 𝒳 ⊂ [0,1]d using noisy pointwise evaluations. Existing regret bounds are either worst-case, scaling as Θ̃ ( Td+1/d+2 ), or adaptive via the zooming dimension dz, yielding Θ̃ ( Tdz+1/dz+2 ). 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⋆>0, we obtain improved adaptive rates of order 𝒪̃ ( Tdz+1 / max(dz,d⋆)+2 ) 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.
Related
- Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
- Stochastic heat equations with non-Lipschitz coefficients driven by symmetric α-stable Lévy white noise
- Strong convergence rates of stochastic theta Milstein methods for index-1 stochastic differential algebraic equations under non-globally Lipschitz conditions
- Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
- Instance-dependent sequential limits as an exact information ledger
BibTeX
@misc{potfer2026instancedependent,
title = {{Instance-dependent Stochastic Lipschitz bandit}},
author = {Marius Potfer and Vianney Perchet},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.29748},
eprint = {2605.29748},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.29748},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Instance-dependent Stochastic Lipschitz bandit
AU - Marius Potfer
AU - Vianney Perchet
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2605.29748
UR - https://arxiv.org/abs/2605.29748
AB - We study the Lipschitz bandit problem, where a learner sequentially maximizes an unknown Lipschitz function f over a domain 𝒳 ⊂ [0,1]^d using noisy pointwise evaluations. Existing regret bounds are either worst-case, scaling as Θ̃ ( T^d+1/d+2 ), or adaptive via the zooming dimension d_z, yielding Θ̃ ( T^d_z+1/d_z+2 ). 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^⋆>0, we obtain improved adaptive rates of order 𝒪̃ ( T^d_z+1 / max(d_z,d^⋆)+2 ) 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.
ER -