Rising Multi-Armed Bandits with Known Horizons

Seockbean Song; Chenyu Gan; Youngsik Yoon; Siwei Wang; Wei Chen; Jungseul Ok

cs.LGFeb 11, 2026

Rising Multi-Armed Bandits with Known Horizons

Authors: Seockbean Song, Chenyu Gan, Youngsik Yoon, Siwei Wang, Wei Chen, Jungseul Ok

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

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 $Ω(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

Panel of Figure 1 — 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.

Panel of Figure 2 — 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 .

Panel of Figure 3 — 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

Panel of Figure 4 — Figure 4: Example instances of LTF Setting.

Panel of Figure 5 — Figure 5: Example instances of Concave Setting.

Panel of Figure 6 — 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.

Panel of Figure 7 — 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$ .

Panel of Figure 8 — 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$ .

$\varepsilon$	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

\varepsilon

T=50{,}000

, where

h_{i}=\max\left\{\lfloor\varepsilon N_{i,t-1}\rfloor,1\right\}

	Concave				LTF
Algorithm	$\sigma{=}0.001$	$\sigma{=}0.01$	$\sigma{=}0.05$	$\sigma{=}0.1$	$\sigma{=}0.001$	$\sigma{=}0.01$	$\sigma{=}0.05$	$\sigma{=}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

\sigma

T=50{,}000

Explore similar work

Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees
Jun 8, 2026Deqi Zheng, Xiaoyang Xu, Yuhong YangStochastic Multi-Armed Bandits Screening
Qiuzhen College, Tsinghua University · Yau Mathematical Sciences Center, Tsinghua University
The Greedy Advantage in Finite-Horizon Bandits
Jul 31, 2026Kai Zhou, Michael Lingzhi Li, Kai WangStochastic Multi-Armed Bandits Interval Regret
Tsinghua University · Harvard Business School
Trading off rewards and errors in multi-armed bandits
May 1, 2026Akram Erraqabi, Alessandro Lazaric, Michal Valko +2Stochastic Multi-Armed Bandits Regret
Inria SequeL · CMU · EnLearn

Jun 8, 2026, stat.MLJ/K move · Enter open · S save

Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees

Deqi Zheng, Xiaoyang Xu, Yuhong Yang

Qiuzhen College, Tsinghua University · Yau Mathematical Sciences Center, Tsinghua University

Stochastic Multi-Armed Bandits Screening

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees

The Greedy Advantage in Finite-Horizon Bandits

Trading off rewards and errors in multi-armed bandits