📊 statistics

Instance-dependent Stochastic Lipschitz bandit

This paper introduces an algorithm for Lipschitz bandits that achieves improved, instance-dependent regret bounds by characterizing performance through integrals of the suboptimality gap over level sets, thereby capturing local structural properties of the function that traditional zooming-based methods miss.

Original authors: Marius Potfer, Vianney Perchet

Published 2026-05-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Marius Potfer, Vianney Perchet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding the Best Spot in a Foggy City

Imagine you are trying to find the highest point in a vast, foggy city (the "action space"). You can't see the whole map. You can only stand at one spot, ask a local guide how high it is there, and then move to a new spot. The guide gives you an answer, but they are a bit noisy and might lie slightly (this is the "noisy evaluation").

Your goal is to climb as high as possible as quickly as possible. Every time you stand on a hill that isn't the highest, you lose a little bit of "regret" (opportunity cost).

This problem is called a Lipschitz Bandit. "Lipschitz" just means the city has smooth hills and valleys; you can't have a cliff that jumps up 1,000 feet in a single step. If you know the height at one point, you know the height of nearby points is roughly similar.

The Old Way: Guessing the Worst-Case Scenario

For a long time, computer scientists tried to solve this by assuming the worst possible city layout. They asked, "What if the hills are tricky everywhere?" This led to a formula that told them how many steps they would need to take in the absolute worst case.

However, this approach is like packing for a trip assuming it will be a blizzard, even if you are going to a tropical beach. It's safe, but it's inefficient. It doesn't account for the fact that your specific city might have a huge, flat plateau at the top, or that the hills might be very gentle in some areas and steep in others.

The New Discovery: Reading the Map as You Go

This paper introduces a smarter way to think about the problem. Instead of just looking at the "worst-case" city, the authors look at the specific shape of the hills in your current city.

They developed a new way to measure "regret" (how much time you waste) that depends on the geometry of the top of the hill.

The "Zooming" Analogy

Imagine you are using a camera to find the peak.

Old Method: You zoom out to see the whole world, then zoom in slowly, checking every single pixel. You assume the peak might be a tiny, sharp needle hidden anywhere.
New Method: You realize that sometimes the peak isn't a needle; it's a giant, flat table. If you know the peak is a big table, you don't need to check every single inch of it. You can just check the edges and know the middle is good.

The authors call this "Instance-Dependent." It means the algorithm adapts to the specific "instance" (the specific function or city) it is facing.

The Secret Sauce: Integrals and "Slices"

The paper's main mathematical breakthrough is describing the difficulty of the problem using an integral (a fancy way of adding up slices).

Think of the city as a loaf of bread.

The Crust: The bottom of the loaf represents the very low, terrible spots. You get rid of these quickly.
The Crumb: The middle represents the "okay" spots.
The Top: The very top slice represents the best spots.

The authors show that the time it takes to find the top depends on how thick the top slice is.

If the top is a tiny, sharp point (a needle), it's hard to find.
If the top is a wide, flat plateau (a table), it's easy to find.

Their formula calculates the "volume" of these near-optimal slices. If the top is wide, the formula says, "Great, you can stop searching sooner!" If the top is narrow, it says, "Okay, keep digging."

The Two Algorithms: PACO and SOUS

The paper proposes two specific strategies (algorithms) to put this theory into practice:

PACO (Phased Adaptive Covering Optimization): This is for the "foggy city" where you only get one data point at a time.
- How it works: It starts by looking at the whole city. It picks a few random spots to test. If a spot looks promising, it draws a small circle around it and focuses only on that circle for the next round. It keeps shrinking the search area, "zooming in" only where the hills look high.
- The Magic: It doesn't just shrink randomly; it shrinks based on how "thick" the high ground is. If the high ground is a wide plateau, it covers it efficiently.
SOUS (Sequential Optimism with Uniform Sampling): This is for when you get full information (like looking at a full weather map instead of just one spot).
- How it works: Since you can see the whole map, you don't need to guess. You just look at the map, find the "good enough" areas, and pick a spot randomly within those areas.
- The Magic: If the best area is huge, you are very likely to pick a good spot immediately. If the best area is tiny, you might miss it, but the math proves you won't miss it too often.

Why This Matters (According to the Paper)

The authors prove that their new method is strictly better than the old "worst-case" methods in many situations.

The "Flat Top" Bonus: If the best solution is a large, flat area (like a plateau), their algorithm finds it much faster than previous methods. The old methods treated a flat plateau the same as a sharp needle, wasting time. The new method recognizes the plateau and speeds up.
Tight Bounds: They didn't just invent a faster way; they proved mathematically that you cannot do much better than their method. They showed a "lower bound," meaning there is a physical limit to how fast anyone can solve this, and their algorithm hits that limit almost perfectly.

Summary in One Sentence

This paper teaches computers how to stop treating every search problem like a worst-case nightmare and instead read the "shape" of the solution to find the best answer faster, especially when the best answer is a big, easy-to-find area rather than a tiny, hidden needle.

Technical Summary: Instance-dependent Stochastic Lipschitz bandit

Problem Setting

The paper addresses the stochastic Lipschitz bandit problem, where a learner seeks to sequentially maximize an unknown $L$ -Lipschitz function $f: X \to \mathbb{R}$ over a bounded domain $X \subset [0, 1]^d$ . At each round $t$ , the learner selects an action $x_t \in X$ and observes a noisy reward $Y_t = f(x_t) + \eta_t$ , where $\eta_t$ is zero-mean, conditionally 1-sub-Gaussian noise. The objective is to minimize the expected cumulative regret $R_T = \mathbb{E}[\sum_{t=1}^T (f^* - f(x_t))]$ , where $f^* = \max_{x \in X} f(x)$ .

While existing literature provides worst-case regret bounds scaling as $\tilde{\Theta}(T^{\frac{d+1}{d+2}})$ and adaptive bounds based on the zooming dimension $d_z$ scaling as $\tilde{\Theta}(T^{\frac{d_z+1}{d_z+2}})$ , the authors argue these are insufficient. Zooming-based guarantees depend solely on the asymptotic growth of near-optimal level sets and fail to capture finer structural properties of the specific instance $(X, f)$ , particularly the geometry of the set of maximizers $X^*$ .

Methodology

1. Algorithmic Framework: PACO

The authors propose Phased Adaptive Covering Optimization (PACO) for the bandit setting. The algorithm operates in phases $k=1, 2, \dots$ , where the resolution $r_k = 2^{-k}$ decreases over time.

Discretization: In each phase, PACO uses a Discretization Oracle to construct a finite set of points $S_k$ that covers the current "active" region $A_k$ with $\ell_\infty$ -balls of radius $r_k/L$ . The oracle ensures points are well-separated and the set size is bounded by the covering number of the region.
Successive Elimination: Within each phase, the algorithm runs a successive elimination subroutine (Algorithm 2) on $S_k$ . It pulls arms to estimate their means and eliminates those that are statistically suboptimal relative to the best surviving arm, adjusted for the phase's resolution $r_k$ .
Active Region Update: The active region for the next phase is updated to the union of balls centered at the surviving arms.

2. Theoretical Analysis: Integral Characterization

The core theoretical contribution is a shift from asymptotic dimension-based bounds to non-asymptotic, instance-dependent integral bounds.

Packing to Integral Link: The authors derive a regret bound expressed as a sum of packing numbers over level-set annuli. They then bridge this discrete sum to a continuous integral using a "peeling" argument over level sets of the gap function $\Delta(x) = f^* - f(x)$ .
Geometric Assumptions: To establish the integral form, they assume a mild geometric condition (Assumption 3/4): for any near-optimal point, a small fraction of the ball centered at that point is contained within $X$ . This ensures the volume of level sets behaves predictably.
Truncated Integral Bound: The resulting regret bound takes the form of a truncated integral:
$R_T \leq C R \log(T) \int_{X \setminus X^*} \frac{dx}{\max(\Delta(x), 2^{-k_T})^{d+1}}$
where $k_T$ is the phase index at horizon $T$ . This integral explicitly depends on the geometry of the level sets of $f$ rather than just an asymptotic exponent.

3. Extension to Lipschitz Experts

The paper extends these results to the full-information Lipschitz experts setting (Algorithm 3: SOUS). Here, the learner observes the entire reward function $f_t(\cdot)$ at each round. The authors propose an algorithm that samples uniformly from a set of points with "reasonably good" estimates. They derive a similar instance-dependent integral bound and show how the geometry of $X^*$ refines the worst-case rates.

4. Relaxations

The analysis is extended to one-sided Lipschitz functions (Assumption 6), where the Lipschitz condition holds only for $x \preceq y$ . This requires modifying the discretization oracle to provide "forward coverings" and adjusting the integral proof to use backward boxes, but the core integral characterization remains valid.

Key Results

1. Instance-Dependent Upper and Lower Bounds

The paper provides matching upper and lower bounds (up to logarithmic factors) for the regret.

Upper Bound: The regret is bounded by the integral of the inverse gap over the domain.
Lower Bound: For any $a_0$ -consistent algorithm (where $a_0 = \frac{d+1}{d+2}$ ), there exist instances where the regret is lower-bounded by a similar integral term. This demonstrates that the instance-dependent characterization is essentially tight.

2. Refined Asymptotic Rates

By analyzing the integral bounds in terms of the zooming dimension $d_z$ and the dimension of the maximizer set $d^*$ , the authors derive improved asymptotic rates.

Main Corollary: When the set of maximizers $X^*$ has dimension $d^* > 0$ , the regret scales as:
$R_T \leq \tilde{O}\left( T^{\frac{d_z+1}{\max(d_z, d^*) + 2}} \right)$
Improvement: This strictly improves upon classical zooming bounds ( $\tilde{O}(T^{\frac{d_z+1}{d_z+2}})$ ) when $d^* > d_z$ .
Geometric Relation: The authors prove that under mild connectivity assumptions, $d_z + 1 \geq d^*$ , ensuring the exponent remains non-negative and the bound is valid.

3. Full-Information Setting

For the Lipschitz experts setting, a similar refined rate is obtained:
$R_T \leq \tilde{O}\left( T^{\frac{1+d_z-\max(d_z, d^*)}{2}} \right)$
This highlights that the geometry of the maximizer set dictates regret improvements even in the full-information regime.

Significance and Claims

The paper claims to fill a gap in the literature by providing a precise, non-asymptotic, instance-dependent analysis for Lipschitz bandits.

Beyond Asymptotics: Unlike previous works that rely on asymptotic complexity parameters (like $d_z$ ), this work characterizes regret through integrals of the suboptimality gap over level sets. This captures the specific geometry of the instance $(X, f)$ rather than just its asymptotic growth.
Refinement of Zooming Bounds: The work demonstrates that classical zooming bounds are not always tight when the set of maximizers is "large" (high $d^*$ ). The new bounds strictly improve upon existing rates in these regimes.
Tightness: The provision of matching lower bounds confirms that the derived integral characterization is essentially the best possible for consistent algorithms.
Generality: The framework is shown to be adaptable to weaker regularity assumptions (one-sided Lipschitz) and full-information settings, suggesting a robust theoretical foundation for continuous-armed optimization.

The authors note that while their analysis is specific to the PACO algorithm, extending these instance-dependent bounds to other popular algorithms (like the standard Zooming algorithm or tree-based methods) remains an open direction for future work.