在线学习中实现收益与队列长度的近优权衡，适合动态匹配平台。
Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets
- 基于在线学习设计定价与匹配策略，动态平衡收益与队列。
- 在T^{1-γ}后悔、平均队列T^{γ/2}、最大队列T^γ间实现近优权衡。
- 适用于需求供给未知场景，适合网约车等双侧市场平台应用。
我们研究一个双侧市场，其中价格敏感的异质客户和服务器到达并加入各自队列。平台可匹配兼容的客户-服务器对，匹配后双方离开系统。目标是设计定价与匹配算法，在最大化平台利润的同时维持合理队列长度。由于实际中需求与供给曲线决定的价格依赖到达率未知，我们设计了一种新型基于在线学习的定价策略，并证明其近最优性。具体地，我们建立了三个性能指标间的权衡：$ ilde{O}(T^{1-γ})$后悔、$ ilde{O}(T^{γ/2})$平均队列长度、$ ilde{O}(T^γ)$最大队列长度，其中$γ or 0, 1/6]$，显著优于现有结果[1]。除$γ$允许范围外，我们还证明该权衡在一类策略下近乎最优，仅差对数因子，与假设已知需求供给曲线的最优解[2]一致。所提策略具有两个特点：动态组件优化低后悔与小队列的权衡；概率组件缓解快速学习所需样本与小队列之间的冲突。
原文摘要 · Abstract (English)
We study a two-sided market, wherein, price-sensitive heterogeneous customers and servers arrive and join their respective queues. A compatible customer-server pair can then be matched by the platform, at which point, they leave the system. Our objective is to design pricing and matching algorithms that maximize the platform's profit, while maintaining reasonable queue lengths. As the demand and supply curves governing the price-dependent arrival rates may not be known in practice, we design a novel online-learning-based pricing policy and establish its near-optimality. In particular, we prove a tradeoff among three performance metrics: $\tilde{O}(T^{1-γ})$ regret, $\tilde{O}(T^{γ/2})$ average queue length, and $\tilde{O}(T^γ)$ maximum queue length for $γ\in (0, 1/6]$, significantly improving over existing results [1]. Moreover, barring the permissible range of $γ$, we show that this trade-off between regret and average queue length is optimal up to logarithmic factors under a class of policies, matching the optimal one as in [2] which assumes the demand and supply curves to be known. Our proposed policy has two noteworthy features: a dynamic component that optimizes the tradeoff between low regret and small queue lengths; and a probabilistic component that resolves the tension between obtaining useful samples for fast learning and maintaining small queue lengths.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。