针对奖励递增的老虎机问题，提出高效算法并给出理论下界。
Rising Rested Bandits: Lower Bounds and Efficient Algorithms
- 设计基于单调非减奖励的改进UCB算法
- 理论证明最坏情况下的后悔上界为T^{2/3}阶
- 适合动态环境中的在线模型选择场景
本文研究随机多臂老虎机（MAB）中的一种特殊情形——休息型老虎机，其各臂期望回报呈单调非减且凹函数特性。通过推导合适的后悔下界，揭示该问题的固有样本复杂性。随后提出针对休息型情况的算法R-ed-UCB，其后悔上界依赖于实例特性，在特定条件下达到𝑁(“T^{2/3}”)阶。在多个合成任务及真实数据集上的在线模型选择问题中，与现有非平稳MAB方法进行实验对比，验证了所提算法的有效性。
原文摘要 · Abstract (English)
This paper is in the field of stochastic Multi-Armed Bandits (MABs), i.e. those sequential selection techniques able to learn online using only the feedback given by the chosen option (a.k.a. $arm$). We study a particular case of the rested bandits in which the arms' expected reward is monotonically non-decreasing and concave. We study the inherent sample complexity of the regret minimization problem by deriving suitable regret lower bounds. Then, we design an algorithm for the rested case $\textit{R-ed-UCB}$, providing a regret bound depending on the properties of the instance and, under certain circumstances, of $\widetilde{\mathcal{O}}(T^{\frac{2}{3}})$. We empirically compare our algorithms with state-of-the-art methods for non-stationary MABs over several synthetically generated tasks and an online model selection problem for a real-world dataset
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。