Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes

• 成果类型: Article
• 署名作者: Emek, Yuval; Lavi, Ron; Niazadeh, Rad; Shi, Yangguang
• 署名单位: Technion Israel Institute of Technology; University of Bath; University of Chicago; Shandong University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• 发表日期: 2024
• 页码: 880-900
• 关键词: auction

摘要

An online problem called dynamic resource allocation with capacity constraints (DRACC) is introduced and studied in the realm of posted price mechanisms. This problem subsumes several applications of stateful pricing, including but not limited to posted prices for online job scheduling and matching over a dynamic bipartite graph. Because existing online learning techniques do not yield vanishing regret for this problem, we develop a novel online learning framework over deterministic Markov decision processes with dynamic state transition and reward functions. Following that, we prove, based on a reduction to the well-studied problem of online learning with switching costs, that if the Markov decision process admits a chasing oracle (i.e., an oracle that simulates any given policy from any initial state with bounded loss), then the online learning problem can be solved with vanishing regret. Our results for the DRACC problem and its applications are then obtained by devising (randomized and deterministic) chasing oracles that exploit the particular structure of these problems.