针对可预测性能提升的决策问题,提出能利用总尝试次数信息的新算法。
Rising Multi-Armed Bandits with Known Horizons
- 基于对总尝试次数的了解,设计新型上置信界算法
- 在结构化场景下实现比传统方法更优的累积收益
- 适合超参数调优等性能随使用提升的场景
Rising Multi-Armed Bandit(RMAB)框架建模了各选项收益随使用次数增加的环境,适用于机器人控制、超参数调优等场景。例如,模型配置(臂)的验证准确率通常随训练轮次增加而提升。RMAB的一个关键特性是与时间范围相关的最优性:最优策略随可用预算 $T$ 显著变化。这意味着知晓 $T$ 能极大提升学习者表现,使其策略与这一动态最优性对齐。然而,该设定仍研究不足。为此,我们提出一种新的累积奖励估计UCB(CURE-UCB),显式融入时间范围信息。通过严格分析,建立了新的后悔上界,并证明该方法在如“线性后平缓”这类结构化实例中严格优于无时间范围感知的策略。大量实验表明其显著优于基线方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。