arXiv:2510.12523cs.LGmath.OC2025-10

在上下文多臂老虎机中,确保各臂最低收益并最大化总收益。

Multi-Armed Bandits with Minimum Aggregated Revenue Constraints

  • 设计乐观与悲观算法,平衡收益最大化与约束满足。
  • 理论证明算法在时间跨度上的表现接近最优。
  • 适合需要公平分配资源的现实场景,如推荐系统。

我们研究带有上下文信息的多臂老虎机问题,目标是在确保每个臂在不同上下文中获得最低累积收益的前提下,最大化总累积收益。该框架捕捉了众多现实应用中公平收益分配至关重要的场景,且上下文变化普遍存在。跨上下文的最小收益约束聚合虽提升了性能并简化可行性,却带来重大技术挑战——标准多臂老虎机中通常存在的闭式最优分配不再可用。我们设计并分析了两类算法:一类乐观地优先考虑性能,另一类悲观地强制满足约束。针对每种算法,我们推导出问题相关的后悔和约束违反上界。此外,我们建立了下界,表明我们的结果对时间跨度的依赖关系在一般情况下是最佳的,并揭示了先前工作中依赖自由探索原则的根本局限性。

原文摘要 · Abstract (English)

We examine a multi-armed bandit problem with contextual information, where the objective is to ensure that each arm receives a minimum aggregated reward across contexts while simultaneously maximizing the total cumulative reward. This framework captures a broad class of real-world applications where fair revenue allocation is critical and contextual variation is inherent. The cross-context aggregation of minimum reward constraints, while enabling better performance and easier feasibility, introduces significant technical challenges -- particularly the absence of closed-form optimal allocations typically available in standard MAB settings. We design and analyze algorithms that either optimistically prioritize performance or pessimistically enforce constraint satisfaction. For each algorithm, we derive problem-dependent upper bounds on both regret and constraint violations. Furthermore, we establish a lower bound demonstrating that the dependence on the time horizon in our results is optimal in general and revealing fundamental limitations of the free exploration principle leveraged in prior work.

多臂老虎机公平分配上下文

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。