In the classic multi-armed bandit framework, the world is assumed to be stationary. Every time you pull a lever, you receive a reward drawn from a fixed, unchanging probability distribution.
In the real world, however, actions change the environment. A machine learning model or a human worker improves with practice, creating a "rising" or "improving" bandit setting. Conversely, an advertisement shown repeatedly to the same user suffers from diminishing marginal utility, while a worker grows tired, creating a "rotting" or "decaying" bandit setting.
When rewards can change over time, we enter the realm of non-stationary bandits. If rewards are allowed to fluctuate arbitrarily, learning becomes mathematically impossible. An arm that has performed terribly for thousands of rounds could suddenly experience an unpredictable spike in value, meaning an agent could never safely eliminate any option. As Suho Shin et al. show in Tokenized Bandit for LLM Decoding and Alignment, without structural constraints on how rewards evolve, any learning algorithm faces exponential regret.
To make non-stationary environments tractable, researchers enforce shape constraints—most notably, concavity and monotonicity. By assuming that rewards follow a concave trajectory, we can exploit the mathematics of diminishing returns to safely predict, bound, and optimize future performance.
The Core Problem: The Threat of Late-Stage Spikes
To understand why shape constraints are necessary, consider the problem of Best Arm Identification (BAI). In a stationary environment, you sample arms until you are confident which one has the highest mean. If an arm's rewards are rising over time, you might assume you can simply track the growth.
However, as Marco Mussi et al. demonstrate in Best Arm Identification for Stochastic Rising Bandits, without a constraint like concavity, a sub-optimal arm could remain indistinguishable from a high-potential one for an arbitrary duration. A flatlining arm might suddenly experience an exponential surge at the very end of your sampling budget.
Reward
^
| / <-- Unpredictable late spike (Unconstrained)
| /
| ---------------+---- <-- Diminishing returns (Concave constraint)
| /
|/
+---------------------> Time / Pulls
Without a structural ceiling, you can never prove an arm is permanently inferior. Alberto Maria Metelli et al. prove in Stochastic Rising Bandits that achieving sublinear regret in environments with increasing rewards is theoretically impossible without structural assumptions. Concavity provides the necessary regularity to ensure that early trends can be reliably extrapolated into the future.
Why Concavity Works: Natural Optimism
The core principle behind modern bandit algorithms is Optimism in the Face of Uncertainty (OFU). If we are unsure how good an arm is, we calculate an upper confidence bound (UCB) and try it.
Concavity is a powerful tool for OFU because of a fundamental geometric property: a concave function always lies below its tangent lines.
If a reward function is concave, its rate of improvement is non-increasing. If we measure the current reward of an arm and its recent rate of growth, we can project that growth forward linearly. Because the true function must curve downward due to diminishing returns, this linear projection serves as a mathematically guaranteed optimistic upper bound on future performance.
Reward
^
| / Linear Projection (Optimistic Upper Bound)
| /
| /.
- - - - - -
| / . \
| / . \ True Concave Reward Curve
| / .__________\
| /
+-------------------------> Time / Pulls
This mechanism, known as optimistic growth approximation, allows an algorithm to compare arms that have been sampled different numbers of times. As Vishakha Patil et al. explain in Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits, by projecting an arm's current reward forward based on its observed rate of improvement, the system can estimate what its cumulative output would be if it reached the same sampling frequency as the most-pulled arm.
Conversely, in "rotting" environments where rewards only decay, concavity implies that the decay rate will slow down or stabilize. As Julien Seznec et al. show in A single algorithm for both restless and rested rotting bandits, the constraint of non-increasing rewards allows any historical observation to serve as a persistent optimistic estimate of current performance, drastically simplifying the exploration-exploitation tradeoff.
Safe Elimination and Bounding
Enforcing a concave shape constraint allows algorithms to filter out stochastic noise and establish mathematical ceilings on an arm's maximum potential.
In Tight Policy Regret Bounds for Improving and Decaying Bandits, Hoda Heidari et al. demonstrate how this enables safe elimination. By comparing a pessimistic estimate of a leading arm's current reward against the optimistic ceiling of a trailing arm, the system can permanently prune suboptimal actions the moment their maximum potential falls below the guaranteed floor of a competitor.
To make this robust against noisy real-world data, David Lindner et al. introduce shape-constrained reward bounding in Addressing the Long-term Impact of ML Decisions via Policy Regret. They use linear programming to fit a monotone concave function directly to noisy historical observations. This optimization filters out random fluctuations, allowing the agent to maintain a stable strategy during saturation phases without being misled by temporary dips or spikes.
Shifting the Complexity Landscape
How much does a concavity constraint actually simplify the learning problem?
In the bandit literature, problems are categorized by their statistical difficulty, measured by cumulative regret. Fully restless bandits (where rewards change arbitrarily) are notoriously difficult, often resulting in linear regret. Stationary bandits are highly tractable, yielding sublinear regret.
Cristiano Migali et al. map this landscape in Tightening Regret Lower and Upper Bounds in Restless Rising Bandits. They prove that adding a concavity constraint to rising restless bandits creates a distinct complexity class:
$$\text{Stationary Bandits} \prec \text{Concave Rising Bandits} \prec \text{General Restless Bandits}$$
This structural property acts as a bridge. It is statistically easier than a general restless environment because the slowing rate of reward change allows the algorithm to settle on optimal choices.
The practical impact of this mathematical bridge spans multiple domains:
- Hyperparameter Optimization: Jiawei Jiang et al. apply this in Efficient Automatic CASH via Rising Bandits, treating the training of machine learning algorithms as rising bandits to prune poor configurations early.
- Welfare Economics: Maximilian Kasy et al. show in Adaptive Maximization of Social Welfare that assuming concavity in a social welfare function accelerates policy discovery, dropping cumulative regret from a slow $T^{2/3}$ rate to a much faster $T^{1/2}$ rate.
- Threshold Identification: James Cheshire et al. demonstrate in The Influence of Shape Constraints on the Thresholding Bandit Problem that when rewards are concave, the complexity of identifying all arms above a certain threshold scales with the double logarithm of the number of arms, making the search nearly independent of the total arm count.
By anchoring non-stationary changes within the predictable boundaries of concavity, these frameworks turn otherwise unlearnable, chaotic environments into structured, solvable optimization problems.
Key Foundational Work
Tight Policy Regret Bounds for Improving and Decaying Bandits (2016) — contributed 3 concept elements to this direction.
A single algorithm for both restless and rested rotting bandits (2020) — contributed 3 concept elements to this direction.
The Influence of Shape Constraints on the Thresholding Bandit Problem (2020) — contributed 1 concept elements to this direction.