提出新算法解决资源有限的多轮决策问题，适用于动态定价与拍卖场景。
Episodic Contextual Bandits with Knapsacks under Conversion Models
- 基于上下文带背包的多轮决策框架，共享转换模型
- 在非平稳上下文中实现亚线性后悔，依赖置信区间查询器
- 支持无标签特征数据，适用于资源受限的实际应用
我们研究一种在线设置，决策者（DM）在重复的上下文带背包（BwK）实例中交互。每轮开始时资源量不同，且上下文分布在一个回合内非平稳。所有回合共享相同的潜在转换模型，该模型决定请求上下文与分配决策下的随机结果。本模型适用于易腐资源的动态定价、以及起始预算不同的重复第一价格拍卖等场景。我们设计了一种在线算法，在拥有一个能实现o(T)后悔的置信区间查询器的前提下，达到关于回合数T的亚线性后悔。该查询器可从现有上下文带背包文献中获得。我们克服了可能上下文数量任意多带来的技术挑战，导致强化学习状态空间无界。当决策者获得无标签特征数据时，本框架在某些设定下提供更优的后悔界，这是上下文带背包文献中的新贡献。
原文摘要 · Abstract (English)
We study an online setting, where a decision maker (DM) interacts with contextual bandit-with-knapsack (BwK) instances in repeated episodes. These episodes start with different resource amounts, and the contexts' probability distributions are non-stationary in an episode. All episodes share the same latent conversion model, which governs the random outcome contingent upon a request's context and an allocation decision. Our model captures applications such as dynamic pricing on perishable resources with episodic replenishment, and first price auctions in repeated episodes with different starting budgets. We design an online algorithm that achieves a regret sub-linear in $T$, the number of episodes, assuming access to a \emph{confidence bound oracle} that achieves an $o(T)$-regret. Such an oracle is readily available from existing contextual bandit literature. We overcome the technical challenge with arbitrarily many possible contexts, which leads to a reinforcement learning problem with an unbounded state space. Our framework provides improved regret bounds in certain settings when the DM is provided with unlabeled feature data, which is novel to the contextual BwK literature.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。