This paper explores a practical but theoretically challenging constraint in online learning: monotonicity. In many real-world scenarios, agents cannot freely jump back and forth between options; they must commit to a single direction.
The "Price of Monotonicity"
The core finding of this NeurIPS 2021 paper is that requiring a sequence of actions to be monotone (e.g., only increasing prices or drug doses) fundamentally changes the complexity of the multi-armed bandit (MAB) problem. For unimodal reward functions, the optimal regret rate shifts from the standard $O(T^{2/3})$ to a slower $O(T^{3/4})$. This shift establishes a mathematical "price of monotonicity" for learning efficiency.
Why Monotonicity Matters
In a standard MAB problem, an agent explores different "arms" to find the one with the highest reward, assuming it can switch between any two arms at any time. However, this assumption fails in several critical applications:
- Dynamic Pricing: Firms often use "markup" pricing. Lowering a price later can alienate early loyal customers or encourage "strategic waiting" for discounts. Thus, prices typically only increase.
- Clinical Trials: In Phase I/II trials, researchers follow "dose escalation" protocols. To ensure patient safety, they start with low doses and gradually increase them, making it impossible to oscillate between high and low doses.
The paper asks a fundamental question: If the sequence of arms $X_1, X_2, \dots, X_T$ must be non-decreasing, can we still learn the optimal action efficiently?
The Challenge: Local Optima and Quasiconcavity
The "Impossible" General Case
For general Lipschitz continuous functions, achieving sublinear regret under a monotonicity constraint is impossible. If a reward function has multiple "humps" (multi-modal), a monotone agent might climb the first peak it encounters. Because it cannot go backward, it gets stuck in this local optimum and can never discover the true global optimum, resulting in a linear regret of $O(T)$.
The Quasiconcave Necessity
To achieve meaningful learning, the paper proves we must assume the reward function is quasiconcave (unimodal). Fortunately, this fits the target applications well: revenue usually peaks at a specific optimal price, and drug efficacy often follows a dose-response curve that plateaus or peaks.
Algorithm and Theoretical Analysis
The author focuses on the continuum-armed bandit, where available actions span the continuous interval $[0, 1]$. To handle the monotonicity constraint, the paper proposes a discretization-based approach:
- Discretization & Batch Testing: The $[0, 1]$ space is divided into $K$ evenly spaced points. The algorithm pulls each arm $k$ for a fixed batch of $m$ times.
- Stopping Criterion: Because the agent can only move forward, it must decide when to stop escalating. It calculates Upper Confidence Bounds (UB) and Lower Confidence Bounds (LB) for the rewards. If the UB of the current arm is lower than the LB of any previously tested arm, the algorithm assumes it has passed the peak.
- Commitment: Once this stopping criterion is met, the agent halts escalation and pulls the current arm for the remainder of the time horizon $T$.
Key Results
- The $T^{3/4}$ Penalty: In standard continuum bandits, the optimal regret is $\tilde{O}(T^{2/3})$. The monotonicity constraint forces the agent to be more cautious, leading to a slower optimal rate of $\tilde{O}(T^{3/4})$. This $T^{1/12}$ difference is the mathematical cost of not being able to backtrack.
- Upper and Lower Bounds: The proposed algorithm achieves a regret of $\tilde{O}(T^{3/4})$ for quasiconcave functions. Crucially, the paper proves a lower bound showing no algorithm can achieve a regret better than $\Omega(T^{3/4})$, confirming the proposed algorithm is rate-optimal.
- Simulation Performance: In synthetic simulations using sub-Gaussian noise, the proposed algorithm significantly outperformed naive versions of UCB constrained to be monotone, which tended to get stuck too early or explore too slowly.
Limitations and Future Directions
While theoretically robust, the approach has limitations. The current algorithm requires knowing the total time horizon $T$ and the noise parameter $\sigma$ in advance. Standard techniques like the "doubling trick" to handle unknown $T$ are inapplicable because the arm sequence cannot be reset to zero. Furthermore, the paper does not account for "context" (e.g., patient characteristics in a trial), leaving contextual monotone bandits as an open challenge. Finally, if the real-world reward function is even slightly multi-modal, the algorithm's performance guarantees vanish.
Summary updated