aiqbench analysis
This paper introduces CURE-UCB, a novel algorithm for Rising Multi-Armed Bandits that leverages knowledge of the time horizon to significantly reduce regret compared to standard approaches. Theoretically, it demonstrates constant regret ($O(1)$) in specific instances where naive methods suffer linear regret growth, and empirical results confirm its superiority across synthetic benchmarks and real-world model selection tasks. This work advances the theoretical understanding of sequential decision-making under non-stationary reward structures.
Rising Multi-Armed Bandits with Known Horizons
arXiv:2602.10727v3 Announce Type: replace Abstract: Rising Multi-Armed Bandits (RMABs) model sequential decision problems where each arm's expected reward improves with repeated pulls. In such problems, the value of investing in an arm depends on how much time remains, making knowledge of the horizon useful side information, yet its benefit remains underexplored. We investigate this benefit through CURE-UCB, a horizon-aware algorithm that estimates each arm's cumulative reward over the remaining horizon. Theoretically, under structured assumptions, we prove that CURE-UCB uniformly dominates a representative horizon-agnostic algorithm and show that the advantage of horizon awareness can be substantial: on some instances, CURE-UCB incurs only $O(1)$ regret whereas the horizon-agnostic algorithm suffers $\Omega(T)$. Furthermore, we establish a regret upper bound for the general concave rising bandit setting whose growth-dependent term matches the known lower bound in its dependence on $T$. Empirically, across synthetic benchmarks and real-world model selection tasks, CURE-UCB achieves lower regret than both rising and non-stationary baselines over a wide range of horizons.
Abstract:Rising Multi-Armed Bandits (RMABs) model sequential decision problems where each arm's expected reward improves with repeated pulls. In such problems, the value of investing in an arm depends on how much time remains, making knowledge of the horizon useful side information, yet its benefit remains underexplored. We investigate this benefit through CURE-UCB, a horizon-aware algorithm that estimates each arm's cumulative reward over the remaining horizon. Theoretically, under structured assumptions, we prove that CURE-UCB uniformly dominates a representative horizon-agnostic algorithm and show that the advantage of horizon awareness can be substantial: on some instances, CURE-UCB incurs only $O(1)$ regret whereas the horizon-agnostic algorithm suffers $\Omega(T)$. Furthermore, we establish a regret upper bound for the general concave rising bandit setting whose growth-dependent term matches the known lower bound in its dependence on $T$. Empirically, across synthetic benchmarks and real-world model selection tasks, CURE-UCB achieves lower regret than both rising and non-stationary baselines over a wide range of horizons.
Machine Learning (cs.LG)
arXiv:2602.10727 [cs.LG]
(or arXiv:2602.10727v3 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2602.10727 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 248 words
Related coverage
Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
arXiv · Sep 22, 2026
Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise
arXiv · Sep 17, 2026
Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
arXiv · Aug 19, 2026
The Greedy Advantage in Finite-Horizon Bandits
arXiv · Aug 3, 2026