Instance-dependent Stochastic Lipschitz bandit

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.