Slope Independent Regret for Generalized Linear Bandits

31 concepts20 papers1 proposal

In sequential decision-making, an agent must learn to select actions that maximize an unknown reward function. In a classic linear bandit, the expected reward of an action is simply the inner product of its feature vector and an unknown parameter vector. However, real-world feedback is rarely perfectly linear. For binary outcomes—such as whether a user clicks an advertisement or a patient responds to a treatment—we turn to Generalized Linear Bandits (GLBs). Here, the expected reward is passed through a non-linear link function $\mu(\cdot)$, such as the sigmoid function in logistic bandits.

For years, a major theoretical hurdle plagued these non-linear models: their performance guarantees (regret bounds) suffered from an exponential penalty factor derived from the worst-case flatness of the link function. A wave of recent insights has fundamentally dismantled this barrier, proving that we can achieve slope-independent regret by matching the geometry of our confidence sets to the local variance of the environment.

The Inflationary Penalty of Non-Linearity

To understand why non-linear rewards historically broke bandit analysis, we have to look at how an algorithm like the Upper Confidence Bound (UCB) maps what it knows about the world.

A UCB algorithm maintains an estimate of the unknown parameter vector $\theta^*$ and draws a confidence ellipsoid around it. When deciding which arm to pull, it looks at the maximum possible reward within that ellipsoid. To translate uncertainty in the parameter space back into uncertainty in the reward space, traditional proofs rely on the Mean Value Theorem. The difference in expected rewards between two parameter estimates $\theta_1$ and $\theta_2$ for a given feature vector $x$ is given by:

$$\mu(x^T \theta_1) - \mu(x^T \theta_2) = \mu'(z) \cdot x^T(\theta_1 - \theta_2)$$

where $z$ is some intermediate point between the two projections.

To guarantee that the algorithm never under-explores, traditional analyses bounded this relationship from below using the global minimum slope of the link function across the entire feasible domain. This introduced a penalty factor:

$$\kappa = \frac{1}{\inf_z \mu'(z)}$$

If the link function becomes very flat—as the sigmoid function does when its argument moves away from zero—the derivative $\mu'(z)$ approaches zero, causing $\kappa$ to explode exponentially. Consequently, classical regret bounds scaled directly with this massive $\kappa$ factor, making the theoretical guarantees practically vacuous for many real-world settings.

The Flatness Paradox

This exponential explosion reveals a stark disconnect between theory and physical reality. If a link function is extremely flat (for instance, $\mu(z) \approx 1$), the outcome is highly predictable. In a logistic bandit, where rewards are binary, the variance of the observation is given by $\mu(z)(1 - \mu(z))$. Crucially, for the logistic link function, this variance is exactly equal to the derivative $\mu'(z)$.

When $\mu'(z)$ is tiny, the noise in our observations vanishes. Intuitively, a learning agent should find these flat regions easier to master because each sample provides highly deterministic, low-noise information.

As Marc Abeille et al. formally demonstrated in Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits, the difficulty of a learning task is governed by the local geometry around the optimal action rather than a global worst-case constant. Steeper non-linearity or extreme flatness near the optimal point can actually accelerate convergence by suppressing observation noise. The historical $\kappa$ penalty was not an intrinsic property of non-linear learning, but an artifact of loose analytical tools.

Localizing Confidence Sets

To align the mathematics with this intuition, researchers had to redesign how algorithms construct confidence sets. Instead of using a uniform confidence ellipsoid that expands globally based on the worst-case $\kappa$, modern algorithms use localized analysis.

In Improved Optimistic Algorithms for Logistic Bandits, Louis Faury et al. introduced localized confidence sets that track the exact derivative $\mu'$ at the specific points being evaluated. By weighting the parameter estimation matrix by these local derivatives, the authors proved that the leading $O(\sqrt{T})$ regret term can be completely decoupled from the global penalty factor $\kappa$. Instead, the dependence on $\kappa$ is relegated to a lower-order, logarithmic term that becomes negligible as the time horizon $T$ grows large.

This approach was further refined by focusing explicitly on the non-linearity at the optimal action. By centering the analysis around the target solution, Alberto Maria Metelli et al. showed in Generalized Kernelized Bandits: Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds that the true learning difficulty is dictated by local behavior near the optimal parameter, effectively bridging the theoretical performance gap between linear models and highly non-linear generalized linear models.

Sharp Concentration and Asymptotic Decoupling

Fully eliminating the non-linearity parameter from the leading regret terms requires tighter concentration inequalities that can natively account for changing variance. Traditional self-normalized martingale bounds over-corrected for worst-case noise. By developing Bernstein-like self-normalized inequalities, Yu-Jie Zhang et al. designed algorithms in Online (Multinomial) Logistic Bandit: Improved Regret and Constant Computation Cost that decouple high-probability confidence bounds from the exponential non-linearity constant entirely.

Similarly, Ayush Sawarni et al. leveraged these localized concentration techniques in Generalized Linear Bandits with Limited Adaptivity to prove that the leading term of regret in generalized linear bandits is entirely independent of the link function's flatness, ensuring robust performance even when the reward distribution is highly skewed.

An additional benefit of this decoupled perspective is the elimination of the "warmup phase." Historically, to prevent the $\kappa$ factor from breaking the algorithm in early rounds, agents were forced to undergo a lengthy initial exploration phase of purely random actions. Sukruta Prakash Midigeshi et al. demonstrated in Achieving Limited Adaptivity for Multinomial Logistic Bandits that by utilizing a specific regret decomposition strategy, algorithms can bypass this warmup phase entirely, avoiding costly random exploration periods that scale with the non-linearity of the reward function.

Generalizing Beyond Simple Parametric Spaces

The principle of decoupling regret from local derivative penalties has allowed bandit theory to expand into highly complex, structured, and even infinite-dimensional action spaces without sacrificing efficiency.

Traditional Analysis:
Global Minimum Slope (inf μ') ──> Exploding Penalty κ ──> Vacuous Regret Bounds

Modern Localized Analysis:
Local Derivative Tracking ──> Variance-Aware Concentration ──> Slope-Independent Regret

This evolution is visible across several distinct domains:

By localizing confidence bounds and matching variance to the shape of the link function, modern bandit algorithms successfully bypass historical non-linearity penalties, achieving optimal, slope-independent regret.

Key Foundational Work

Eluder Dimension and the Sample Complexity of Optimistic Exploration (2013) — contributed 2 concept elements to this direction.
Combinatorial Multi-Armed Bandit with General Reward Functions (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_linearity_independent_regret_ee22f6ec,
  title = {non-linearity independent regret},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-linearity-independent-regret/rdr_ee22f6ecebaa4434b233607afdfff536},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_linearity_independent_regret_ee22f6ec_v1,
  title = {non-linearity independent regret},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-linearity-independent-regret/rdr_ee22f6ecebaa4434b233607afdfff536/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake