Organizations: Graduate School of AI, POSTECH, Pohang, Republic of Korea · Qiuzhen College, Tsinghua University, Beijing, China · Department of CSE, POSTECH, Pohang, Republic of Korea · Microsoft Research, Beijing, China
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 Ω(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.
Figures & tables
Figure 1: Demonstration of Horizon-Adaptiveness. (a) Expected reward functions. Arm A represents an Early Peaker (high initial reward, limited growth), and Arm B represents a Late Bloomer (low initial reward, high potential). (b) Cumulative regret for different time horizons T , showing different regret trends among CURE-UCB , R-ed-UCB , and SW-UCB . (c) Selection trajectories: Horizon-agnostic baselines (R-ed-UCB and SW-UCB) follow a fixed selection trajectory regardless of the horizon T . In contrast, CURE-UCB adapts its trajectory to the horizon. (d) Decision criteria at different time steps t : SW-UCB focuses on current rewards, whereas R-ed-UCB focuses on a specific future point. CURE-UCB instead uses a horizon-aware criterion, evaluating the same arms differently depending on remaining time.
Figure 2: Performance Analysis in LTF (top row) and Concave (bottom row) Settings. (a, d) Cumulative regret as a function of the time horizon T . (b, e) Pairwise win rate at T=20K (short horizon). (c, f) Pairwise win rate at T=100K (long horizon). Each cell of the win-rate matrices shows how often the row algorithm attains lower regret than the column algorithm. Shaded regions and error bars denote 95% confidence intervals over 40 seeds, with the full results over all baselines in Appendix J .
Figure 3: Online model selection on IMDB and XSum-LLM. The top row shows reward dynamics, and the bottom row shows cumulative regret. The left column corresponds to IMDB sentiment analysis for horizons up to T=50K , and the right column corresponds to LLM fine-tuning on XSum summarization for horizons up to T=1K . The legends above (a) and (b) indicate model configurations, and the shared legend between the two rows indicates the algorithms used in the cumulative-regret plots. Shaded regions denote 95% confidence intervals over 40 seeds.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Example instances of LTF Setting.
Figure 5: Example instances of Concave Setting.
Figure 6: Extrapolation accuracy of parametric families on real reward curves. Each family is fit to an initial prefix of each arm’s training curve and evaluated by its RMSE against the full mean reward curve, averaged over arms. Most evaluated points lie beyond the prefix, so the RMSE reflects extrapolation of the remaining reward. Across both tasks, the two-parameter LTF family is consistently among the most accurate and clearly outperforms the higher-degree polynomial fits.
Figure 7: Full results for the LTF setting. (Left) Pairwise win-rate heatmap over all baselines. (Right) Average ranking over all baselines. Both are computed over 100 independent instances at T=20K , 60K , and 100K .
Figure 8: Full results for the Concave setting. (Left) Pairwise win-rate heatmap over all baselines. (Right) Average ranking over all baselines. Both are computed over 100 independent instances at T=20K , 60K , and 100K .
ε
Concave
LTF
1/2
2,056
3,230
1/4
2,818
4,576
1/8
3,691
6,574
1/16
4,766
9,158
1/32
6,069
12,254
Appendix
Table 1: Mean cumulative regret of CURE-UCB under varying window-size parameter ε at T=50,000 , where hi=max{⌊εNi,t−1⌋,1} .
Concave
LTF
Algorithm
σ=0.001
σ=0.01
σ=0.05
σ=0.1
σ=0.001
σ=0.01
σ=0.05
σ=0.1
CURE-UCB
783
2,057
3,439
4,145
1,974
3,239
5,450
6,981
SW-UCB
10,212
10,209
10,209
10,176
7,855
7,837
7,896
7,890
R-ed-UCB
6,667
7,886
8,059
8,530
8,761
10,268
13,805
15,585
Appendix
Table 2: Mean cumulative regret under varying noise levels σ at T=50,000 .
We study a stochastic multi-armed bandit problem in which the set of available arms expands over time. This setting arises in sequential experimentation when new actions or treatments become available during an ongoing study, making regret against a single best arm in hindsight inappropriate. We instead evaluate performance relative to the best arm currently available, leading to a dynamic-regret criterion for arriving-arm environments. To address the resulting challenges of arrival information discrepancy (AID) and a drifting benchmark (DB), we propose UCB for Arriving Arms (UCB-AA), an elimination-based procedure with an aiding preliminary screening step for newly arrived arms before full competition with incumbent arms. We show that UCB-AA attains regret bounds that depend explicitly on the arrival process, achieves sublinear dynamic regret under regularity conditions on gap evolution, and admits an online extension for unknown horizons. Simulation results show that UCB-AA reduces wasted pulls and maintains a smaller active arm set while preserving competitive regret performance.
Deqi Zheng, Xiaoyang Xu, Yuhong Yang
Qiuzhen College, Tsinghua University · Yau Mathematical Sciences Center, Tsinghua University
Organizations increasingly rely on sequential experimentation to improve decision-making. While the multi-armed bandit literature has developed algorithms with strong asymptotic regret guarantees, many practical applications operate over finite and externally imposed horizons. Motivated by the finite-horizon setting, we develop a class of regularized greedy algorithms for multi-armed Bernoulli bandits. We derive the first finite-horizon regret envelopes for regularized greedy bandits, showing that finite-horizon regret decomposes into transient exploration costs and a suboptimal convergence term that decays exponentially with the regularization strength. This characterization yields principled calibration rules for the regularization parameters and, as a limiting case, sharper regret guarantees for the classical greedy policy. Across extensive numerical experiments, calibrated regularized greedy policies consistently match or outperform state-of-the-art algorithms. These results suggest that regularized greedy policies can provide an effective approach for finite-horizon bandit problems.
In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.
Akram Erraqabi, Alessandro Lazaric, Michal Valko +2