提出分层约束强化学习算法,解决多层级决策中的探索与约束平衡问题。
Hierarchical Upper Confidence Bounds for Constrained Online Learning
- 设计分层置信度上界算法(HC-UCB),在多层级结构中动态调整探索策略。
- 理论证明算法具有次线性累积误差,且所有层级约束满足概率保证。
- 适用于医疗试验、广告投放等需逐级审批的现实决策场景。
多臂老虎机(MAB)是不确定性环境下序列决策的基础框架,广泛应用于临床试验、在线广告和资源分配等领域。然而,传统MAB模型难以刻画具有层次化决策结构、多层级约束或上下文相关动作空间的实际场景。本文提出分层约束老虎机(HCB)框架,将上下文老虎机问题扩展至包含层级结构与多层级约束的情形。我们设计了分层约束上置信界(HC-UCB)算法,利用分层置信区间应对复杂性。理论分析表明,该算法实现次线性遗憾,并在所有层级上提供约束满足的高概率保证。此外,我们推导了HCB问题的极小极大遗憾下界,证明算法近乎最优。研究成果对决策过程天然分层且受多重约束的真实应用具有重要意义,提供了高效均衡探索与利用的解决方案。
原文摘要 · Abstract (English)
The multi-armed bandit (MAB) problem is a foundational framework in sequential decision-making under uncertainty, extensively studied for its applications in areas such as clinical trials, online advertising, and resource allocation. Traditional MAB formulations, however, do not adequately capture scenarios where decisions are structured hierarchically, involve multi-level constraints, or feature context-dependent action spaces. In this paper, we introduce the hierarchical constrained bandits (HCB) framework, which extends the contextual bandit problem to incorporate hierarchical decision structures and multi-level constraints. We propose the hierarchical constrained upper confidence bound (HC-UCB) algorithm, designed to address the complexities of the HCB problem by leveraging confidence bounds within a hierarchical setting. Our theoretical analysis establishes sublinear regret bounds for HC-UCB and provides high-probability guarantees for constraint satisfaction at all hierarchical levels. Furthermore, we derive a minimax lower bound on the regret for the HCB problem, demonstrating the near-optimality of our algorithm. The results are significant for real-world applications where decision-making processes are inherently hierarchical and constrained, offering a robust and efficient solution that balances exploration and exploitation across multiple levels of decision-making.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。