在上下文影响交易的场景中，用树结构设计价格策略，实现极低后悔值。
Nonparametric Contextual Online Bilateral Trade
- 用分层树结构建模上下文与买卖双方估值的关系。
- 在仅知是否成交的情况下，后悔值达到约 T^(d-1)/d。
- 适用于不依赖线性假设、需严格预算平衡的实时交易系统。
我们研究上下文驱动的在线双边交易问题。每轮中，学习者面对一对买卖方，需在未观测其私有价值的情况下提出交易价格，目标是促成交易。学习者在定价前可获取一个 d 维上下文向量，该向量影响买卖方的估值。以往工作多基于线性模型，本文首次处理一般非参数情形：买卖方估值为上下文的任意 Lipschitz 函数。我们设计一种基于分层树结构的算法，确保后悔值为 ‘O(T^{(d-1)/d})’。算法满足两项严苛条件：（1）仅接收一比特反馈（即是否成交），（2）强预算平衡（学习者不能补贴或获利）。我们还提供了全反馈设定下的匹配下界，证明了该后悔界紧致。
原文摘要 · Abstract (English)
We study the problem of contextual online bilateral trade. At each round, the learner faces a seller-buyer pair and must propose a trade price without observing their private valuations for the item being sold. The goal of the learner is to post prices to facilitate trades between the two parties. Before posting a price, the learner observes a $d$-dimensional context vector that influences the agent's valuations. Prior work in the contextual setting has focused on linear models. In this work, we tackle a general nonparametric setting in which the buyer's and seller's valuations behave according to arbitrary Lipschitz functions of the context. We design an algorithm that leverages contextual information through a hierarchical tree construction and guarantees regret $\widetilde{O}(T^{{(d-1)}/d})$. Remarkably, our algorithm operates under two stringent features of the setting: (1) one-bit feedback, where the learner only observes whether a trade occurred or not, and (2) strong budget balance, where the learner cannot subsidize or profit from the market participants. We further provide a matching lower bound in the full-feedback setting, demonstrating the tightness of our regret bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。