在上下文影响的双边交易中,设计了能自适应定价并保持收支平衡的高效算法。
Contextual Online Bilateral Trade
- 基于上下文向量和未知偏好向量建模买卖双方估值,动态设定价格。
- 两比特反馈下,贸易收益与利润最大化的后悔率分别为 $O(d\ log d)$ 与 $O(d\ log\ log T + d\ log d)$。
- 即使只获知是否成交(一比特反馈),也能保持低后悔率,适合在线交易场景。
研究上下文影响下的重复双边交易问题,其中买卖双方的估值由上下文向量与两个未知 $d$-维向量的内积决定。每轮中,学习者接收上下文并为买卖双方设定价格,当双方均接受时交易发生。针对收益最大化与利润最大化目标,证明了相对于强基准——最优全知动态策略的无后悔性。在可分别观测双方接受与否(两比特反馈)的自然场景下,设计的算法实现 $O(d\log d)$ 的收益后悔率,以及 $O(d \log\log T + d\log d)$ 的利润后悔率,且满足每步收支平衡。在一比特反馈(仅知是否成交)情形下,仍可达到类似后悔率,但允许学习者产生 $O(d\log d)$ 的小额负利润,该值与时间跨度无关。进一步研究一比特反馈与每步收支平衡的结合,对收益最大化,设计出与时间无关的后悔率,但指数依赖于维度 $d$;对利润最大化,后悔率保持指数依赖 $d$,并乘以 $\log T$ 因子。
原文摘要 · Abstract (English)
We study repeated bilateral trade when the valuations of the sellers and the buyers are contextual. More precisely, the agents' valuations are given by the inner product of a context vector with two unknown $d$-dimensional vectors -- one for the buyers and one for the sellers. At each time step $t$, the learner receives a context and posts two prices, one for the seller and one for the buyer, and the trade happens if both agents accept their price. We study two objectives for this problem, gain from trade and profit, proving no-regret with respect to a surprisingly strong benchmark: the best omniscient dynamic strategy. In the natural scenario where the learner observes \emph{separately} whether the agents accept their price -- the so-called \emph{two-bit} feedback -- we design algorithms that achieve $O(d\log d)$ regret for gain from trade, and $O(d \log\log T + d\log d)$ regret for profit maximization. Both results are tight, up to the $\log(d)$ factor, and implement per-step budget balance, meaning that the learner never incurs negative profit. In the less informative \emph{one-bit} feedback model, the learner only observes whether a trade happens or not. For this scenario, we show that the tight two-bit regret regimes are still attainable, at the cost of allowing the learner to possibly incur a small negative profit of order $O(d\log d)$, which is notably independent of the time horizon. As a final set of results, we investigate the combination of one-bit feedback and per-step budget balance. There, we design an algorithm for gain from trade that suffers regret independent of the time horizon, but \emph{exponential} in the dimension $d$. For profit maximization, we maintain this exponential dependence on the dimension, which gets multiplied by a $\log T$ factor.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。