# No-Regret Learning in Bilateral Trade via Global Budget Balance arXiv: https://arxiv.org/abs/2310.12370 · HTML: https://mlsanity.com/paper/2310.12370/ ## Key facts - Cited by 17 papers in the map (data through 14 Oct 2026). - Builds on 28 of its 60 references that are in the map. - First posted on arXiv 18 Oct 2023. ## Builds on (most cited first, 28 of 28) - [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019) - [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013) - [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017) - [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018) - [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015) - [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014) - [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014) - [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015) - [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022) - [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022) - [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021) - [Learning in Auctions: Regret is Hard, Envy is Easy](https://mlsanity.com/paper/1511.01411/) (2015) - [Online Learning with Vector Costs and Bandits with Knapsacks](https://mlsanity.com/paper/2010.07346/) (2020) - [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021) - [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022) - [Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion](https://mlsanity.com/paper/2303.01296/) (2023) - [Learning in repeated auctions](https://mlsanity.com/paper/2011.09365/) (2020) - [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023) - [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023) - [Efficient Two-Sided Markets with Limited Information](https://mlsanity.com/paper/2003.07503/) (2020) - [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021) - [Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem](https://mlsanity.com/paper/2209.12013/) (2022) - [Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms](https://mlsanity.com/paper/1706.04637/) (2017) - [Fixed-Price Approximations in Bilateral Trade](https://mlsanity.com/paper/2107.14327/) (2021) - [Learning and Efficiency in Games with Dynamic Population](https://mlsanity.com/paper/1505.00391/) (2015) - [Approximately Efficient Bilateral Trade](https://mlsanity.com/paper/2111.03611/) (2021) - [Reallocation Mechanisms](https://mlsanity.com/paper/1404.6786/) (2014) - [Improved Approximation to First-Best Gains-from-Trade](https://mlsanity.com/paper/2205.00140/) (2022) ## Built on by (most cited first, 17 of 17) - [Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints](https://mlsanity.com/paper/2405.16118/) (2024) - [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025) - [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024) - [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024) - [Market Making without Regret](https://mlsanity.com/paper/2411.13993/) (2024) - [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (2024) - [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024) - [Tight Regret Bounds for Fixed-Price Bilateral Trade](https://mlsanity.com/paper/2504.04349/) (2025) - [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026) - [Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting](https://mlsanity.com/paper/2501.16018/) (2025) - [A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage](https://mlsanity.com/paper/2503.02646/) (2025) - [The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms](https://mlsanity.com/paper/2602.10868/) (2026) - [Nonparametric Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12904/) (2026) - [Profit Maximization in Bilateral Trade against a Smooth Adversary](https://mlsanity.com/paper/2605.12664/) (2026) - [Trading Volume Maximization with Online Learning](https://mlsanity.com/paper/2405.13102/) (2024) - [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026) - [Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs](https://mlsanity.com/paper/2607.20258/) (2026) ## Abstract (arXiv) Bilateral trade models the problem of intermediating between two rational agents -- a seller and a buyer -- both characterized by a private valuation for an item they want to trade. We study the online learning version of the problem, in which at each time step a new seller and buyer arrive and the learner has to set prices for them without any knowledge about their (adversarially generated) valuations. In this setting, known impossibility results rule out the existence of no-regret algorithms when budget balanced has to be enforced at each time step. In this paper, we introduce the notion of global budget balance, which only requires the learner to fulfill budget balance over the entire time horizon. Under this natural relaxation, we provide the first no-regret algorithms for adversarial bilateral trade under various feedback models. First, we show that in the full-feedback model, the learner can guarantee tilde O(√T) regret against the best fixed prices in hindsight, and that this bound is optimal up to poly-logarithmic terms. Second, we provide a learning algorithm guaranteeing a tilde O(T3/4) regret upper bound with one-bit feedback, which we complement with a Omega(T5/7) lower bound that holds even in the two-bit feedback model. Finally, we introduce and analyze an alternative benchmark that is provably stronger than the best fixed prices in hindsight and is inspired by the literature on bandits with knapsacks.