# Regret Minimization in Bilateral Trade With Perturbed Markets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 40 references that are in the map.
- First posted on arXiv 11 May 2026.

## Builds on (most cited first, 30 of 34)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (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)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [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)
- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [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)
- [Approximately Efficient Bilateral Trade](https://mlsanity.com/paper/2111.03611/) (2021)
- [An Online Learning Theory of Brokerage](https://mlsanity.com/paper/2310.12107/) (2023)
- [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)
- [Reallocation Mechanisms](https://mlsanity.com/paper/1404.6786/) (2014)
- [Approximately Stationary Bandits with Knapsacks](https://mlsanity.com/paper/2302.14686/) (2023)
- [Bandits with Replenishable Knapsacks: the Best of both Worlds](https://mlsanity.com/paper/2306.08470/) (2023)
- [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024)
- [Online Learning under Budget and ROI Constraints via Weak Adaptivity](https://mlsanity.com/paper/2302.01203/) (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)
- [Online Two-Sided Markets: Many Buyers Enhance Learning](https://mlsanity.com/paper/2503.01529/) (2025)
- [Efficient learning by implicit exploration in bandit problems with side observations](https://mlsanity.com/paper/2604.24555/) (2026)
- [Improved Approximation to First-Best Gains-from-Trade](https://mlsanity.com/paper/2205.00140/) (2022)
- [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (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)

## Abstract (arXiv)

We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints. While this problem is well-understood in purely adversarial and stochastic settings, these environments exhibit a sharp dichotomy: adversarial environments allow for no-regret learning against the best fixed-price mechanism, whereas stochastic environments allow for no-regret learning against the best distribution over prices that is budget balanced in expectation. This gap is significant, as policies balanced in expectation can increase the GFT by a multiplicative factor of two. In this work, we bridge these extremes by studying perturbed markets, where an underlying stochastic distribution is subject to an adversarial corruption C. We design an algorithm that adaptively scales with the level of corruption, achieving an tildeO(T3/4) + O(Clog(T)) regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case tildeO(T3/4) regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.