Rising Multi-Armed Bandits with Known Horizons

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.