带有背包约束的上下文老虎机的重优化算法

arXiv cs.LG 论文
contextual-bandits knapsack-constraints reoptimization regret-analysis online-learning machine-learning

摘要

本文提出了带有背包约束的上下文老虎机的新的重优化算法，实现了平均遗憾界 O((ln T)^3 / T)，并改进了现有结果。

arXiv:2608.11383v1 公告类型：新 摘要：我们研究了带有背包约束的上下文老虎机的新算法。在这些问题中，客户、产品和资源的类型都是有限的。每种产品由固定的资源组合制成，且资源容量有限。决策者必须为每位到达的客户分配一组多种可能产品中的一种。每次将客户分配给产品都会产生随机奖励，该奖励等于客户和产品特征的未知线性函数加上噪声项。目标是联合学习平均奖励函数，并进行在线分配，以最小化相对于已知奖励函数的最优策略的期望收入损失。我们提出了上置信界（UCB）算法家族的一种自然且简单的扩展，并应用了重优化技术。我们证明，通过利用重优化，我们的算法实现了平均遗憾 $O(\frac{(\ln T)^3}{T})$，其中 $T$ 是时间范围长度。我们的界限显著降低了文献中基于重优化的密切相关的动态定价问题的 $O(\frac{1}{\sqrt{T}})$ 界限。
查看原文
查看缓存全文

缓存时间: 2026/08/13 15:35 

# 用于带有背包约束的上下文赌博机的重新优化算法  
来源：https://arxiv.org/html/2608.11383  
###### 摘要  
我们研究了针对带有背包约束的上下文赌博机（Contextual Bandits with Knapsack）的新算法。在这类问题中，存在有限类型的客户、产品和资源。每种产品由固定组合的资源制成，且资源具有有限容量。决策者必须为每个到达的客户分配一组多种可能产品中的一种。每次将客户分配给产品都会产生一个随机奖励，该奖励等于客户和产品特征的未知线性函数加上噪声项。目标是联合学习平均奖励函数，并做出在线分配决策，以最小化相对于知道奖励函数的最优策略的期望收入损失。我们提出了上置信界（UCB）算法族的一个自然且简单的扩展，并应用了重新优化技术。我们表明，通过利用重新优化，我们的算法实现了平均遗憾 \(O\left(\frac{(\ln T)^3}{T}\right)\)，其中 \(T\) 是时间跨度长度。我们的界显著降低了文献中基于重新优化的密切相关动态定价问题的 \(O\left(\frac{1}{\sqrt{T}}\right)\) 界。

关键词：收入管理；近似算法；机器学习；遗憾分析。  

## 1 引言  
数字平台日益成为异质需求与容量受限供给之间的核心匹配者。以网约车平台或在线广告交易平台为例：每天，平台必须将数百万个请求（例如乘客、展示次数）分配给有限的资源池（例如司机工时、广告主预算）。平台必须实时做出这些分配决策，但每次匹配产生的收入很少能事先知晓。相反，它取决于用户特征与产品属性之间复杂的、不可观测的交互，

相似文章

有限适应性下的上下文Slate GLM Bandits

arXiv cs.LG

提出了在有限适应性下具有广义线性奖励的上下文Slate Bandit算法，实现了与非线性参数无关的遗憾界。批量式和少切换算法计算高效，且在经验上优于基线，包括在语言模型示例选择任务中。

捕捉移动子空间：超越平稳性的低秩老虎机

arXiv cs.LG

本文研究了分段平稳的低秩线性上下文老虎机，提出了SPSC算法，该算法实现了与内在秩（而非环境维度）成比例的动态遗憾，并刻画了在标量反馈下子空间恢复的辨识边界。