Regret Minimization in Bilateral Trade With Perturbed Markets

• URL: http://arxiv.org/abs/2605.10475v1
• Date: Mon, 11 May 2026 12:37:53 GMT
• Title: Regret Minimization in Bilateral Trade With Perturbed Markets
• Abstract summary: We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints.<n> adversarial environments allow for no-regret learning against the best fixed-price mechanism.<n>Our algorithm maintains the worst-case $tildemathcalO(T3/4)$ regret bound relative to a per-round budget-balanced baseline.
• Score: 25.375074054942434
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\tilde{\mathcal{O}}(T^{3/4}) + \mathcal{O}(C\log(T))$ regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case $\tilde{\mathcal{O}}(T^{3/4})$ regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.

Related papers

• Profit Maximization in Bilateral Trade against a Smooth Adversary [14.182863671689836]
  Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good.<n>We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary.<n>We devise a learning algorithm that guarantees a $tildeO(sqrtT)$ regret bound, which is tight in the time horizon $T$ poly-logarithmic factors.
  arXiv  Detail & Related papers  (2026-05-12T19:12:57Z)
• Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
  We study episodic RL from emphmulti-source imperfect preferences through a cumulative imperfection budget.<n>We propose a unified algorithm with regret $tildeO(sqrtK/M+)$, which exhibits a best-of-both-regimes behavior.
  arXiv  Detail & Related papers  (2026-03-20T19:34:53Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade [14.182863671689836]
  Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations.<n>We study this problem from the perspective of a broker, in a regret minimization framework.<n>We propose a learning algorithm that guarantees a nearly tight $tildeO(sqrtT)$ regret when seller and valuations are drawn.
  arXiv  Detail & Related papers  (2025-09-26T16:42:05Z)
• Better Regret Rates in Bilateral Trade via Sublinear Budget Violation [28.647867626280316]
  We study how the optimal regret rate varies with the allowed violation of the global budget balance constraint.<n>We complement this result with a matching lower bound, thus fully characterizing the trade-off between regret and budget violation.
  arXiv  Detail & Related papers  (2025-07-15T15:45:36Z)
• Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
  We consider a common case of the $m$-set semi-bandit problem, where the learner exactly selects $m$ arms from the total $d$ arms.<n>We show that FTPL with a Fr'echet perturbation also enjoys the near optimal regret bound $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ in the adversarial setting.
  arXiv  Detail & Related papers  (2025-04-09T22:07:01Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Autoregressive Bandits [58.46584210388307]
  We propose a novel online learning setting, Autoregressive Bandits, in which the observed reward is governed by an autoregressive process of order $k$. We show that, under mild assumptions on the reward process, the optimal policy can be conveniently computed. We then devise a new optimistic regret minimization algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers sublinear regret of order $widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G
  arXiv  Detail & Related papers  (2022-12-12T21:37:36Z)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  This paper considers the multi-armed bandit (MAB) problem and provides a new best-of-both-worlds (BOBW) algorithm that works nearly optimally in both adversarial settings.
  arXiv  Detail & Related papers  (2022-06-14T12:58:46Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  We show that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is $O(textrmpolylog(T))$ after $T$ repetitions of the game. We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium.
  arXiv  Detail & Related papers  (2021-11-11T01:19:53Z)
• On Optimal Robustness to Adversarial Corruption in Online Decision Problems [27.68461396741871]
  We show that optimal robustness can be expressed by a square-root dependency on the amount of corruption. For the multi-armed bandit problem, we also provide a nearly tight lower bound up to a logarithmic factor.
  arXiv  Detail & Related papers  (2021-09-22T18:26:45Z)
• The Interplay between Distribution Parameters and the Accuracy-Robustness Tradeoff in Classification [0.0]
  Adrial training tends to result in models that are less accurate on natural (unperturbed) examples compared to standard models. This can be attributed to either an algorithmic shortcoming or a fundamental property of the training data distribution. In this work, we focus on the latter case under a binary Gaussian mixture classification problem.
  arXiv  Detail & Related papers  (2021-07-01T06:57:50Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  We provide two variants of a Robust Phased Elimination algorithm, one that knows $C$ and one that does not. We show that both variants attain near-optimal regret in the non-corrupted case $C = 0$, while incurring additional additive terms respectively. In a contextual setting, we show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing $C$.
  arXiv  Detail & Related papers  (2020-07-07T09:00:57Z)
• Non-Convex SGD Learns Halfspaces with Adversarial Label Noise [50.659479930171585]
  We show the solution to the problem of learning surrogate learning homogeneous halfspaces in the distribution-specific model. In any convex distributions, we show that the misclassification error inherently leads to misclassification error of halfspace.
  arXiv  Detail & Related papers  (2020-06-11T18:55:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.