# Contextual Online Bilateral Trade

arXiv: https://arxiv.org/abs/2602.12903 · HTML: https://mlsanity.com/paper/2602.12903/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 32 references that are in the map.
- First posted on arXiv 13 Feb 2026.

## Builds on (most cited first, 22 of 22)

- [Dynamic Pricing in High-dimensions](https://mlsanity.com/paper/1609.07574/) (2016)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [Logarithmic Regret in Feature-based Dynamic Pricing](https://mlsanity.com/paper/2102.10221/) (2021)
- [Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise](https://mlsanity.com/paper/2201.11341/) (2022)
- [Perishability of Data: Dynamic Pricing under Varying-Coefficient Models](https://mlsanity.com/paper/1701.03537/) (2017)
- [Semi-parametric dynamic contextual pricing](https://mlsanity.com/paper/1901.02045/) (2019)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [Efficient Two-Sided Markets with Limited Information](https://mlsanity.com/paper/2003.07503/) (2020)
- [Pricing Query Complexity of Revenue Maximization](https://mlsanity.com/paper/2111.03158/) (2021)
- [Approximately Efficient Bilateral Trade](https://mlsanity.com/paper/2111.03611/) (2021)
- [(Almost) Efficient Mechanisms for Bilateral Trading](https://mlsanity.com/paper/1604.04876/) (2016)
- [Fixed Price Approximability of the Optimal Gain From Trade](https://mlsanity.com/paper/1710.08394/) (2017)
- [Contextual Search in the Presence of Adversarial Corruptions](https://mlsanity.com/paper/2002.11650/) (2020)
- [Better Regret Rates in Bilateral Trade via Sublinear Budget Violation](https://mlsanity.com/paper/2507.11419/) (2025)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Learning to Maximize Gains From Trade in Small Markets](https://mlsanity.com/paper/2401.11596/) (2024)
- [Feature-Based Online Bilateral Trade](https://mlsanity.com/paper/2405.18183/) (2024)
- [Gains-from-Trade in Bilateral Trade with a Broker](https://mlsanity.com/paper/2410.17444/) (2024)
- [Approximately Efficient Bilateral Trade with Samples](https://mlsanity.com/paper/2502.13122/) (2025)

## Built on by (most cited first, 3 of 3)

- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)
- [Repeated Bilateral Trade: The Quest for Fairness](https://mlsanity.com/paper/2606.15369/) (2026)
- [Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs](https://mlsanity.com/paper/2607.20258/) (2026)

## Abstract (arXiv)

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 separately whether the agents accept their price -- the so-called two-bit feedback -- we design algorithms that achieve O(dlog d) regret for gain from trade, and O(d loglog T + dlog 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 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(dlog 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 exponential in the dimension d. For profit maximization, we maintain this exponential dependence on the dimension, which gets multiplied by a log T factor.