Rising Multi-Armed Bandits with Known Horizons
This work addresses a practical problem in scenarios like robotics and hyperparameter tuning where performance improves with repeated usage, but it is incremental as it builds on the underexplored horizon-aware setting in RMAB.
The paper tackles the problem of Rising Multi-Armed Bandits (RMAB) with known horizons, where expected rewards increase with plays, and proposes a novel CURE-UCB method that explicitly integrates the horizon to align decision-making with shifting optimality, resulting in a new regret upper bound and significant superiority over baselines in experiments.
The Rising Multi-Armed Bandit (RMAB) framework models environments where expected rewards of arms increase with plays, which models practical scenarios where performance of each option improves with the repeated usage, such as in robotics and hyperparameter tuning. For instance, in hyperparameter tuning, the validation accuracy of a model configuration (arm) typically increases with each training epoch. A defining characteristic of RMAB is em horizon-dependent optimality: unlike standard settings, the optimal strategy here shifts dramatically depending on the available budget $T$. This implies that knowledge of $T$ yields significantly greater utility in RMAB, empowering the learner to align its decision-making with this shifting optimality. However, the horizon-aware setting remains underexplored. To address this, we propose a novel CUmulative Reward Estimation UCB (CURE-UCB) that explicitly integrates the horizon. We provide a rigorous analysis establishing a new regret upper bound and prove that our method strictly outperforms horizon-agnostic strategies in structured environments like ``linear-then-flat'' instances. Extensive experiments demonstrate its significant superiority over baselines.