Stochastic Rising Bandits with Concave Learning Curves

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 226 papers61 conceptsfrozen 2026-10-04

In the classic multi-armed bandit problem, a gambler faces a row of slot machines, each with a fixed but unknown probability of payout. The goal is to find the best machine as quickly as possible. But in the real world—especially in machine learning—the "machines" aren't static. A neural network architecture might perform poorly after ten minutes of training but become state-of-the-art after ten hours. A student might struggle with a new language initially but eventually achieve fluency.

This is the core of the Stochastic Rising Bandit (SRB) or Improving Multi-Armed Bandit (IMAB) problem: how do we make optimal decisions when the rewards for our actions increase the more we perform them?

The Challenge of Unpredictable Growth

If rewards can increase in any arbitrary way, the problem is mathematically impossible to solve efficiently. As Alberto Maria Metelli, Francesco Trovò, and their colleagues demonstrate in Stochastic Rising Bandits, if an arm's reward can experience a sudden, massive spike at any moment, a learner will suffer "linear regret." This means the learner can never truly "catch up" to the optimal strategy because they might abandon a potentially great option just before it blossoms.

In Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem, Avrim Blum and Kavya Ravichandran argue that without structural constraints, an optimal choice remains indistinguishable from a poor one for an arbitrary duration. To make the problem "learnable," we need a prior assumption about the shape of the improvement.

Concavity as a Structural Prior

The most powerful assumption used across this research is concavity, or the principle of diminishing returns. In a concave learning curve, the reward increases over time, but the rate of increase slows down.

This assumption is not just a mathematical convenience; it mirrors the reality of most learning processes, where the biggest gains happen early on. By assuming concavity, researchers like Marco Mussi and Marcello Restelli can construct optimistic upper bounds on future performance.

If you know the curve is concave, the current rate of improvement (the derivative) is the maximum possible rate of improvement for all future steps. This allows an algorithm to say: "Even if this arm continues to improve at its current best rate, it still won't beat the current leader within our time budget." This logic enables the pruning of sub-optimal candidates, a technique Ashish Sabharwal and Horst Samulowitz used in the DAUB algorithm to achieve a 16x speedup in model selection.

Mechanisms for Identifying Potential

How do these algorithms actually decide which "rising" arm to pull? They typically use a variation of the Upper Confidence Bound (UCB) that accounts for growth:

  1. Optimistic Growth Projection: Instead of looking only at the average historical reward, algorithms like R-UCB or R-ed-UCB calculate the current "slope" of improvement. As described in Rising Rested Bandits: Lower Bounds and Efficient Algorithms, they project this slope forward to estimate the arm's "potential" at a future time $T$.
  2. Potential Reward Summation: In Mitigating Disparity while Maximizing Reward, Vishakha Patil and Vineet Nair introduce a mechanism that compares arms by "filling in" the missing pulls. If Arm A has been pulled 10 times and Arm B 100 times, the algorithm estimates what Arm A's total reward would be if it were also pulled 100 times, based on its current trajectory.
  3. Shape-Constrained Bounding: For more complex scenarios, such as the "single-peaked" curves explored by David Lindner and Andreas Krause, the system uses linear programming to fit a monotone concave function to noisy data. This filters out temporary fluctuations and focuses on the underlying trend.

From AutoML to Social Impact

The implications of this research extend far beyond simple toy problems. In the Combined Algorithm Selection and Hyperparameter optimization (CASH) problem, Jiawei Jiang and Yang Li use Rising Bandits to efficiently navigate thousands of possible model configurations, identifying the "rising stars" early in the training process.

Perhaps more importantly, this framework addresses a fundamental issue in fairness. Standard bandit algorithms often favor "early bloomers"—options that start with high rewards. By explicitly modeling improvement, researchers like Arindam Khan show that we can mitigate initial disparities. We can justify investing in a "slow starter" (a community or a new technology) because the concave growth model proves that its long-term potential outweighs its current low performance.

By shifting the focus from what an arm is to what an arm is becoming, the study of Rising Bandits provides a mathematically rigorous way to value growth, practice, and potential.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 17 papers
  2. Version 1 · 2026-10-04 · 26 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_concavity_constraint_572975c8,
  title = {concavity constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/concavity-constraint/rdr_572975c86a3a45319187422b03fc1296},
  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_stochastic_rising_bandits_with_concave_l_572975c8_v1,
  title = {Stochastic Rising Bandits with Concave Learning Curves},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-rising-bandits-with-concave-learning-curves/rdr_572975c86a3a45319187422b03fc1296/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}