改进上下文带约束的在线决策算法，显著降低收益损失。
Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints
- 基于UCB思想并引入重优化机制，动态调整策略。
- 实现平均遗憾度为O((ln T)^3 / T)，优于文献中O(1/√T)的旧结果。
- 适合资源有限场景下的个性化推荐与动态定价系统。
研究带有资源容量约束的上下文老虎机问题。存在有限种类的客户、产品和资源，每种产品由固定资源组合构成，资源容量有限。决策者需为每位到达的客户分配一个可选产品，每次分配产生随机收益，等于未知线性函数加噪声。目标是同时学习收益均值函数，并在线决策以最小化相对于已知收益函数最优策略的期望收益损失。本文提出一种自然且简单的UCB算法扩展，并结合重优化技术。理论证明，该算法在时长T下平均遗憾度为O((ln T)^3 / T)，显著优于同类动态定价问题中基于重优化的O(1/√T)已有结果。
原文摘要 · Abstract (English)
We study new algorithms for Contextual Bandits with Knapsack. In these problems, there are finitely many types of customers, products, and resources. Each product is made from a fixed combination of resources, and resources have finite capacity. A decision maker must assign each arriving customer one out of a set of multiple possible products. Every assignment of a customer to a product will generate a random reward, which equals an unknown linear function of customer and product features, plus a noise term. The objective is to jointly learn the mean reward function, and to make online assignments to minimize the expected revenue loss relative to an optimal policy that knows the reward function. We propose a natural and simple extension of the Upper-Confidence-Bound (UCB) family of algorithms and apply re-optimization techniques. We show that by taking advantage of re-optimization, our algorithm achieves an average regret of $O(\frac{(\ln T)^3}{T})$ where $T$ is the horizon length. Our bound significantly reduces the $O(\frac{1}{\sqrt{T}})$ bound in the literature for closely related dynamic-pricing problems that are based on re-optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。