# Rising Multi-Armed Bandits with Known Horizons

arXiv: https://arxiv.org/abs/2602.10727 · HTML: https://mlsanity.com/paper/2602.10727/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 33 references that are in the map.
- First posted on arXiv 11 Feb 2026.

## Builds on (most cited first, 17 of 17)

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [Teacher algorithms for curriculum learning of Deep RL in continuously parameterized environments](https://mlsanity.com/paper/1910.07224/) (2019)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Efficient Automatic CASH via Rising Bandits](https://mlsanity.com/paper/2012.04371/) (2020)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Sliding-Window Thompson Sampling for Non-Stationary Settings](https://mlsanity.com/paper/2409.05181/) (2024)
- [Waypoint-Based Reinforcement Learning for Robot Manipulation Tasks](https://mlsanity.com/paper/2403.13281/) (2024)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2404.01198/) (2024)
- [Rising Rested Bandits: Lower Bounds and Efficient Algorithms](https://mlsanity.com/paper/2411.14446/) (2024)
- [Thompson Sampling-like Algorithms for Stochastic Rising Bandits](https://mlsanity.com/paper/2505.12092/) (2025)
- [Diversity-Based Recruitment in Crowdsensing By Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2312.15729/) (2023)
- [Combinatorial Rising Bandits](https://mlsanity.com/paper/2412.00798/) (2024)
- [Rising Rested MAB with Linear Drift](https://mlsanity.com/paper/2501.04403/) (2025)

## Abstract (arXiv)

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.