📊 statistics

Optimal Regret for Single Index Bandits

This paper resolves the open problem of optimal regret for general single-index bandits by proposing a two-phase $\texttt{ZoomSIB-UCB}$ algorithm that achieves a tight $\tilde{\mathcal{O}}(T^{2/3})$ regret bound, significantly improving upon the previous $\tilde{\mathcal{O}}(T^{3/4})$ result and matching a newly established minimax lower bound.

Original authors: Devdan Dey, Sujoy Bhore, Avishek Ghosh

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Devdan Dey, Sujoy Bhore, Avishek Ghosh

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

Imagine you are trying to find the best spot to set up a lemonade stand in a huge, sprawling city.

The Problem: The "Hidden Map"
In this city, the number of customers you get (your reward) depends on a single, hidden direction. Let's say the best spots are all along a specific diagonal street, but you don't know which diagonal it is. Furthermore, you don't know the "rule" that connects the street location to the number of customers. Maybe the middle of the street is best, maybe the ends are best, or maybe it's a weird zigzag pattern.

This is the Single Index Bandit problem. You have high-dimensional data (the whole city map), but the reward depends on a hidden, one-dimensional projection of that map. The challenge is twofold:

You don't know the direction of the "golden street" (the parameter $\theta^*$ ).
You don't know the shape of the curve that tells you how good a spot is once you find the street (the unknown function $f$ ).

The Old Way: Guessing and Checking
Previous researchers tried to solve this. If they knew the curve was always going "uphill" (monotone), they had a great solution. But for general, wiggly, non-monotone curves (where the best spot might be in the middle, or at the edges, or both), the best previous method was like a clumsy explorer. They would spend a lot of time blindly guessing, then commit to a guess, and repeat. This resulted in a "regret" (lost potential customers) that grew quite fast as time went on—specifically, proportional to $T^{3/4}$ (where $T$ is time).

The New Solution: "ZoomSIB-UCB"
The authors of this paper propose a smarter, two-step strategy called ZoomSIB-UCB. Think of it as a two-phase expedition:

Phase 1: Finding the Compass (Parameter Estimation)
Instead of wandering aimlessly, the algorithm first spends a short, calculated amount of time pulling levers (trying different spots) randomly. It uses a clever mathematical trick called a Stein Estimator.

The Analogy: Imagine you are in a dark room with a hidden wind direction. You throw a handful of feathers. By watching which way they drift on average, you can figure out the wind direction without knowing the exact shape of the room.
The algorithm uses this to estimate the direction of the "golden street" ( $\theta^*$ ). It doesn't need to know the reward function yet; it just needs to find the line.

Phase 2: The Zoomed Map (Discretization and UCB)
Once the algorithm has a good guess of the direction, it projects all the complex city maps onto that single line. Now, instead of a 100-dimensional city, it's just a 1D street.

The Analogy: Imagine taking a high-resolution photo of that street and shrinking it down into a simple ruler with 100 marked zones (bins).
The algorithm then treats these zones like "arms" in a classic slot machine game. It uses a strategy called UCB (Upper Confidence Bound), which balances exploring new zones and exploiting the ones that seem good.
The Twist: Because the city is huge, not every zone on the ruler will have a lemonade stand available every single day. This is called a "Sleeping Bandit" problem (some arms are "asleep" or unavailable). The algorithm is smart enough to only play the "awake" arms and compare them fairly.

The Result: A Perfect Balance
By carefully choosing how many zones (bins) to create on the ruler, the authors found the "Goldilocks" spot.

If you have too few zones, your map is too blurry (you miss the best spot).
If you have too many zones, you spend too much time checking empty spots.
They proved that having roughly $T^{1/3}$ zones is perfect.

This leads to a new, optimal "regret" rate of $T^{2/3}$ .

Translation: The new method loses significantly fewer potential customers over time compared to the old method. It's a mathematical proof that you can't do much better than this without knowing more information.

Why It Matters (According to the Paper)
The authors didn't just guess this; they proved it's the best possible speed for this type of problem.

Upper Bound: They showed their algorithm achieves the $T^{2/3}$ speed.
Lower Bound: They constructed a "worst-case scenario" (a tricky, bumpy reward function) and proved that no algorithm, no matter how smart, can beat the $T^{2/3}$ speed in this setting.
Real-World Tests: They tested this on synthetic data and real-world datasets (like network intrusion detection and forest cover types). In every case, their method found the best spots much faster and with less "regret" than the previous best methods. It also handled high-dimensional data (many features) much better, essentially ignoring the "curse of dimensionality" by compressing everything into that single 1D line.

In Summary
The paper solves a puzzle about how to learn efficiently when you have a complex, high-dimensional world that depends on a hidden, one-dimensional rule you don't fully understand. They built a tool that first finds the hidden direction, then zooms in on a simplified map to make decisions, proving that this is the fastest possible way to learn in this specific scenario.

Technical Summary: Optimal Regret for Single Index Bandits

Problem Definition

The paper addresses the Single-Index Bandit (SIB) problem, a sequential decision-making framework where rewards depend on an unknown one-dimensional projection of high-dimensional context vectors through an unknown, non-parametric reward function.

Formally, at each round $t$ , the learner observes a set of $K$ context vectors $X_t = \{x_{t,a} \in \mathbb{R}^d\}_{a \in [K]}$ . The learner selects an arm $x_{t,a}$ and observes a stochastic reward:
$y_t = f(x_{t,a}^\top \theta^*) + \eta_t$
where:

$\theta^* \in \mathbb{R}^d$ is an unknown parameter vector (the index direction).
$f: \mathbb{R} \to \mathbb{R}$ is an unknown, continuously differentiable link function.
$\eta_t$ is zero-mean noise with bounded variance.

The goal is to minimize cumulative regret, defined as the difference between the expected reward of the optimal arm and the chosen arm over a horizon $T$ .

Context and Gap:
While optimal regret rates are established for linear bandits ( $\tilde{O}(\sqrt{T})$ ) and generalized linear bandits (where $f$ is known), the SIB setting is more challenging because $f$ is unknown. Previous work by Kang et al. [2025] addressed the case where $f$ is unknown but monotone, achieving an optimal $\tilde{O}(\sqrt{T})$ regret using Stein estimators. However, for the general non-monotone case (assuming only boundedness and Lipschitz continuity of $f$ ), the best known bound was $\tilde{O}(T^{3/4})$ . The central question of this work is: What is the optimal regret scaling for general (non-monotone) single-index bandits?

Methodology: ZoomSIB-UCB

The authors propose a two-phase algorithm named Zoomed Single Index Bandit with Upper Confidence Bound (ZoomSIB-UCB). The core insight is to reduce the high-dimensional problem to a sequence of one-dimensional bandit problems by estimating the projection direction $\theta^*$ and then discretizing the projected space.

Phase 1: Parameter Estimation

The algorithm dedicates the first $T_0$ rounds to estimating the unknown direction $\theta^*$ .

Exploration: Arms are pulled uniformly at random.
Estimation: The algorithm employs a normalized Stein estimator. Leveraging Stein's Identity, which states that $E[y S(x)] = E[f'(x^\top \theta^*)] \theta^* = \mu^* \theta^*$ (where $S(x)$ is the score function of the context distribution), the algorithm constructs an unbiased estimator for the direction of $\theta^*$ .
Normalization: To resolve scaling and sign ambiguities, the estimator is normalized using the $\ell_1$ -norm.
Calibration: The exploration horizon $T_0$ is chosen such that the estimation error $\|\hat{\theta}_0 - \theta^*\|_1$ is sufficiently small (specifically bounded by $\Delta / 2L$ , where $\Delta$ is the bin width and $L$ is the Lipschitz constant of the context).

Phase 2: Discretized UCB

Once $\hat{\theta}_0$ is computed, the algorithm operates on the projected scalar values $z = x^\top \hat{\theta}_0$ .

Discretization: The real line is partitioned into $N = O(T^{1/3})$ bins of width $\Delta = T^{-1/3}$ .
Sleeping Bandits: At each round, only a random subset of bins is "active" (containing at least one available arm). This introduces a "sleeping bandit" structure where the set of available arms changes stochastically.
UCB Strategy: The algorithm runs a UCB algorithm over the available bins. It selects the arm belonging to the bin with the highest Upper Confidence Bound index.
Handling Bias: The algorithm accounts for two sources of error:
1. Discretization Bias: Approximating continuous rewards by bin centers (bounded by Lipschitz continuity).
2. Estimation Error: The displacement of the true index due to $\theta^*$ estimation error.
  These errors are absorbed into an inflated confidence radius.

Key Contributions

1. Improved Regret Upper Bound

The paper establishes a regret bound of $\tilde{O}(d^2 T^{2/3})$ for general non-monotone single-index bandits.

This improves significantly upon the previous best bound of $\tilde{O}(T^{3/4})$ by Kang et al. [2025].
The algorithm achieves this by balancing the discretization bias ( $O(T\Delta)$ ) and the exploration cost of the 1D bandit problem ( $O(\sqrt{N T})$ ). Setting $N \sim T^{1/3}$ (and thus $\Delta \sim T^{-1/3}$ ) minimizes the total regret to $O(T^{2/3})$ .

2. Matching Minimax Lower Bound

The authors prove a $\tilde{\Omega}(T^{2/3})$ minimax lower bound for the general non-monotone setting.

Construction: They construct a hard problem instance involving a family of functions with small, localized "bumps" of height $\sim T^{-1/3}$ .
Reduction: They reduce the SIB problem to an $N$ -armed bandit problem (where $N \sim T^{1/3}$ ) by ensuring high probability of arm availability in every bin.
Information Theoretic Trap: Using the Bretagnolle-Huber inequality, they show that distinguishing between a null hypothesis and a "spike" hypothesis (where a specific bin is optimal) requires massive exploration, forcing a regret of $\Omega(T^{2/3})$ .
Significance: This confirms that the $\tilde{O}(T^{2/3})$ upper bound is tight and that the proposed algorithm is minimax optimal.

3. Empirical Validation

Extensive experiments on synthetic and real-world datasets (KDD Cup 99, Forest Cover Type) demonstrate:

Superior Performance: ZoomSIB-UCB consistently outperforms the state-of-the-art GSTOR (Kang et al. [2025]) and Random baselines, achieving substantially lower cumulative regret.
Scaling: The algorithm exhibits sublinear regret scaling with an empirical exponent of $\approx 0.53$ (Quadratic) and $0.57$ (Zigzag), well below the theoretical worst-case ceiling of $2/3$ .
Dimensionality: The algorithm is robust to high-dimensional contexts ( $d$ ), as it operates in the projected 1D space after the initial estimation phase, effectively bypassing the curse of dimensionality that plagues kernel-based methods.
Adaptive Stopping: An adaptive stopping rule allows the algorithm to terminate the exploration phase early when the parameter estimate stabilizes, avoiding the need for prior knowledge of $\mu^*$ or $T$ .

Significance and Claims

The paper claims to resolve an open problem in sequential learning by providing the first sharp characterization of the regret for general non-monotone single-index bandits.

Optimality: By providing both an upper and a matching lower bound, the authors establish that the correct regret scaling is $\Theta(T^{2/3})$ (ignoring logarithmic factors).
Generality: Unlike previous approaches that relied on monotonicity or specific smoothness classes (like RKHS), this method works for any bounded, Lipschitz continuous reward function without requiring knowledge of the function's shape or the parameter $\mu^*$ .
Practicality: The introduction of an adaptive stopping rule makes the algorithm implementable in practice without requiring the theoretical exploration horizon $T_0$ to be fixed a priori based on unknown constants.

The work bridges the gap between non-parametric statistics and bandit theory, demonstrating that the single-index structure can be exploited to achieve optimal rates even when the reward function is completely unknown and non-monotone.