统一解释了UCB在总收益和最大收益问题中的最优性，提出新算法可适配不同目标。
Unified theory of upper confidence bound policies for bandit problems targeting total reward, maximal reward, and more
- 用‘最优臂的值’统一定义UCB策略，指导选臂决策。
- 证明了信心区间需随试验次数缩小才能保证最优性。
- 提出PIUCB算法，在玩具实验中表现优于或等同于现有方法。
上置信界（UCB）策略被公认为经典总收益强化学习问题的阶次最优解。尽管类似方法已被应用于最大收益问题（即最大化最大奖励的累积值），其阶次最优性仍不明确。本文阐明了在何种统一条件下UCB策略在两类问题中均能达到阶次最优。核心概念是“最优者量”——识别出具有最高值的臂。这使得UCB策略可统一定义为：选择具有最高最优者量置信上界的臂。在此设定下，可通过以“失败次数”替代传统损失函数来分析最优性。分析表明，最优者量的信心区间必须随试验次数适当缩小，方能确保阶次最优。基于此，我们证明了先前提出的MaxSearch算法满足该条件，因而对最大收益问题为阶次最优。同时，通过提供合适的最优者量及其置信区间，可系统性地推导出新的强化学习问题及对应的阶次最优UCB算法。在此基础上，我们提出了旨在选取最高改进概率（PI）臂的PIUCB算法。该算法在实际中可用于最大收益问题，在玩具示例中性能与或优于MaxSearch。这表明本理论具备生成针对特定最优者量的新策略的潜力。
原文摘要 · Abstract (English)
The upper confidence bound (UCB) policy is recognized as an order-optimal solution for the classical total-reward bandit problem. While similar UCB-based approaches have been applied to the max bandit problem, which aims to maximize the cumulative maximal reward, their order optimality remains unclear. In this study, we clarify the unified conditions under which the UCB policy achieves the order optimality in both total-reward and max bandit problems. A key concept of our theory is the oracle quantity, which identifies the best arm by its highest value. This allows a unified definition of the UCB policy as pulling the arm with the highest UCB of the oracle quantity. Additionally, under this setting, optimality analysis can be conducted by replacing traditional regret with the number of failures as a core measure. One consequence of our analysis is that the confidence interval of the oracle quantity must narrow appropriately as trials increase to ensure the order optimality of UCB policies. From this consequence, we prove that the previously proposed MaxSearch algorithm satisfies this condition and is an order-optimal policy for the max bandit problem. We also demonstrate that new bandit problems and their order-optimal UCB algorithms can be systematically derived by providing the appropriate oracle quantity and its confidence interval. Building on this, we propose PIUCB algorithms, which aim to pull the arm with the highest probability of improvement (PI). These algorithms can be applied to the max bandit problem in practice and perform comparably or better than the MaxSearch algorithm in toy examples. This suggests that our theory has the potential to generate new policies tailored to specific oracle quantities.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。