acceptodds
Under review as a conference paper at ICLR 2027

Regret Minimization in Bilateral Trade With Perturbed Markets

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 . We design an algorithm that adaptively scales with the level of corruption, achieving an regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.

Primary area:
learning theory
Keywords:
Online Learning, Bilateral Trade, Adversarial

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_tsyWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

this paper studies maximizing Gain from Trade (GFT) in (repeated) bilateral trade. In prior work, either fully adversarial or stochastic environment alone has been well understood.

The main contirbution of this paper is to propose a new and unified online learning algorithm that can handle both envs. This requires a new type of primal-dual-style alg. design.

Critical strengths
  1. in the well-established online bilateral trade setting, this paper gives an improved algorithm in the sense that it achieves the best of both worlds between sto. and adv. envs.
  2. the algorithm design is under primal-dual framework, which is of independent interest due to its broad use. In this particular problem, the proposed algorithm can bypass the standard Slater condition to a weaker one.
Critical weaknesses
  1. unfortunately, due to page limit, in the main body, the authors were not able to give discussion/future direction/limitation
Questions for authors
  1. could authors explain how the equations in lines 1319 - 1323 derived?
  2. can this new primal-dual design be potentially applied to other constrained online learning problem, such as the basic online OCO?
  3. why does the formulation in Eq. (2) make sense? I.e., why do not we care about how much the revenue is, as long as it's non-negative?
1 comment

We thank the reviewer for the positive evaluation and for these questions.

  1. Could authors explain how the equations in lines 1319 - 1323 derived?

The submitted Lemma 3 did not justify the signed comparator-revenue term in this display. We have corrected Lemma 3 and added its proof in the appendix. The corrected lemma gives ∑t∈T1E(p,q)∼π[GFTt(p,q)+Revt(p,q)]≤M∑t∈T1Revt(pt,qt)+2+MO~(KT).\sum_{t\in\mathcal T_1}\mathbb E_{(p,q)\sim\pi}[\mathrm{GFT}_t(p,q)+\mathrm{Rev}_t(p,q)] \le M\sum_{t\in\mathcal T_1}\mathrm{Rev}_t(p_t,q_t)+2+M\widetilde O(\sqrt{KT}). Moving ∑t∈T1E(p,q)∼π[Revt(p,q)]\sum_{t\in\mathcal T_1}\mathbb{E}_{(p,q)\sim\pi}[\mathrm{Rev}_t(p,q)] to the right and subtracting the learner’s nonnegative GFT on T1\mathcal T_1 gives the displayed regret bound. At the chosen KK, the additive error is absorbed into O~(T3/4)\widetilde O(T^{3/4}). Adding the Primal-Dual bound cancels the learner’s Rev-Max revenue and leaves −∑t=1TwtE(p,q)∼π[Revt(p,q)]-\sum_{t=1}^T w_t\mathbb E_{(p,q)\sim\pi}[\mathrm{Rev}_t(p,q)], where wt=1w_t=1 on T1\mathcal T_1 and wt=λtw_t=\lambda_t on T2\mathcal T_2.

  1. Can this new primal-dual design be potentially applied to other constrained online learning problem, such as the basic online OCO?

The design could extend to online convex optimization with a cumulative resource constraint if the learner can replenish the resource and bound the objective loss incurred while doing so. In bilateral trade, the corrected Lemma 3 supplies that bound by relating the comparator’s GFT plus its signed revenue to the revenue earned on replenishment rounds. Convexity alone does not imply such a bound. An extension would therefore require an analogous comparison for the actions and feedback available in the new problem.

  1. why does the formulation in Eq. (2) make sense? I.e., why do not we care about how much the revenue is, as long as it's non-negative?

Thank you for raising this point. We study a standard formulation in bilateral trade, in which the goal is to maximize gains from trade subject to budget balance. Revenue plays an important role because it can finance trades that generate surplus but require a subsidy. Giving additional weight to profit could favor policies that earn more revenue at the expense of gains from trade. Eq. (2) therefore requires nonnegative expected revenue over the horizon and compares feasible policies by their expected gains from trade.

Reviewer_QtFBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers repeated bilaterial exchange. In each round a buyer and seller arrive with private values and costs. Prices are posted and trade occurs when the buyer's value is above the buyers price and the seller's cost is below the sellers price. The model is bayesian with adversarial perturbations where the joint distribution satisfies a natural smoothness property. The aim is to maximize gains from trade while not subsidizing trades on average.

In this model the paper develops an algorithm based on interleaving profit maximization and subsidized gains from trade maximization. The rate at which this is done is with a Lagrangian parameter that is reminiscent of the Myerson and Satterthwaite (1983) analysis, though the authors do not make this connection.

What I understood most from reading this paper is that there are some specific challenges of the bilateral exchange model that stress the limits of existing methods for online learning. Specifically a quantity called the Slater condition, which requires all rounds to have strictly positive payoff.

To my tastes, there is a modeling issue in this paper. There are now several papers in this line of literature. The first paper requires each round have budget balanced (and ex post IR/IC). This assumption, by known results in bilateral exchange, forces the mechanism to be a posted pricing. Subsequent papers relax the per-round budget balance assumption but keep, without justification, the posted pricing format. Now, especially, that presents a problem. The benchmark in this paper in the standard bayesian model cannot recover the gains from trade from the Myerson-Satterthwaite mechanisms. Thus, it is the wrong thing to try to approximate.

This leads us to a fundamental question for this paper: Is it a paper about advancing techniques in online learning with adversarial perturbations, or is it a paper on solving online bilateral exchange? For the former, the model seems not to be general enough, and we need more justification for why, after relaxing the per-round budget-balance we should keep the per-round posted pricing. On the other hand, if this is really a paper on online learning, then I wonder if there are more applications of these techniques?

Critical strengths
  • Technically competent work, improving the state of the art.
Critical weaknesses
  • Assumes model from prior papers that hasn't been sufficiently vetted.
Questions for authors

I don't have questions for the authors.

2 comments

On retaining posted prices under global budget balance. Regret minimization relative to the best posted-price mechanism is well established in the literature, including in settings with global budget balance (see [1],[2],[3],[4]). We agree that richer Bayesian mechanisms can achieve greater gains from trade than posted-price mechanisms. However, we believe that posted prices offer several advantages that make them worth studying even under global budget balance, particularly their simplicity, ease of implementation, and transparency. Each party observes the terms of trade in advance and can decide whether to trade by comparing the posted price with its own valuation, without having to report that valuation.

[1] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. STOC 2024

[2] Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang. Tight Regret Bounds for Fixed-Price Bilateral Trade. ICALP 2026.

[3] Yaonan Jin. Tight regret bounds for bilateral trade under semi feedback.

[4] Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi. Better Regret Rates in Bilateral Trade via Sublinear Budget Violation SODA 2026

On the online learning contribution and extension. A potential extension is online convex optimization with a cumulative resource constraint. The same design could apply when some actions replenish the resource and the learner can bound the objective loss incurred while using them. In bilateral trade, Lemma 3 provides this bound by relating the comparator’s gains from trade plus its signed revenue to the revenue earned on replenishment rounds.

Many papers using a flawed model is, in my opinion, not a good reason to continue writing papers about it. Especially, without explicitly acknowledging the flaw in the model. I am guessing that the gaps between the posted pricing benchmark and the second best benchmark are unbounded. If we think this is really a paper about learning to mediate bilateral trade, we must then really have motivation for losing all the gains from trade.

Reviewer_CVfKOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
2(+1)
Read review
Paper summary

This paper studies a classical online bilateral trade problem, where the objective is to maximize the total Gain from Trade (GFT) subject to Global Budget Balance (GBB), rather than the more restrictive per-round Weak Budget Balance (WBB). The paper considers two benchmarks: (1) OptF\mathrm{Opt}^F, the best fixed price chosen in hindsight, where the seller and buyer prices are identical (p=qp=q), resulting in zero revenue in every round; and (2) OptD\mathrm{Opt}^D, the best fixed distribution π\pi over price pairs (p,q)(p,q), subject to an expected global budget-balance constraint. Neither benchmark represents the unrestricted optimal adaptive trading policy. The former restricts the decision space to a single price, while the latter allows randomized price pairs and yields a linear optimization problem over a probability simplex. In terms of the admissible policy class, OptD\mathrm{Opt}^D is the stronger benchmark.

Previous work has largely studied stochastic and adversarial environments separately. The main contribution of this paper is to bridge these two regimes by considering perturbed markets, where an oblivious adversary selects a sequence of market distributions whose cumulative total-variation distance from an underlying stationary distribution is bounded by CC. Under this model, the paper establishes high-probability guarantees on the cumulative GFT, achieving O~(T3/4)\widetilde{O}(T^{3/4}) regret against OptF\mathrm{Opt}^F in adversarial environments and O~(T3/4)+O(Clog⁡T)\widetilde{O}(T^{3/4})+O(C\log T) regret against OptD\mathrm{Opt}^D when the underlying stationary distribution satisfies a smoothness assumption.

Critical strengths

1, The paper bridges stochastic and adversarial bilateral trade by establishing O~(T3/4)+O(Clog⁡T)\widetilde O(T^{3/4})+O(C\log T) regret against the stronger distributional benchmark OptD\mathrm{Opt}^D under smoothness, while retaining O~(T3/4)\widetilde O(T^{3/4}) regret against the fixed-price benchmark OptF\mathrm{Opt}^F without smoothness. Importantly, the algorithm achieves these guarantees while maintaining global budget balance and without prior knowledge of the corruption level CC. Competing with two different benchmark classes under a unified framework is a meaningful theoretical contribution.

2, Although the paper builds on existing primal-dual methods, revenue-maximization procedures, and bandit learning techniques, their integration is actually non-trivial and not straightforward. In particular, the budget-dependent switching mechanism, the use of weakly adaptive dual regret to control budget recovery costs, and the construction of loss estimators under one-bit feedback require nontrivial analysis.

Critical weaknesses

Updated after rebuttal: The authors have revised their submission and relieved my concerns on Lemma 3 and accordingly Theorem 1. I boosted up my scores.


Major concern:

I notice a potential soundness issues in Lemma 3 and the proof of Theorem 1. Lemma 3 is stated for any distribution π\pi satisfying expected budget balance over the entire horizon, but bounds its GFT only on the adaptively selected Rev-Max rounds T1\mathcal T_1; this extension does not appear to follow directly from the cited prior work and is not proved in the submission. More importantly, the proof of Lemma 13 in Appendix E uses an additional term −∑t∈T1Eπ[Revt]-\sum_{t\in\mathcal T_1}\mathbb E_\pi[\mathrm{Rev}_t], which is absent from Lemma 3 and cannot be directly derived from it. Furthermore, the proof for the OptF\mathrm{Opt}^F benchmark applies Lemma 3 to a comparator from Program (3), which may not satisfy its global budget-feasibility assumption. Since these steps are essential to establishing Theorem 1, the authors should provide a rigorous justification or a corrected proof of the claimed regret guarantees.

Minor concerns:

While the paper recovers the established regret rates in the stochastic and adversarial extremes, it does not establish whether the O(Clog⁡T)O(C\log T) dependence is optimal or necessary. No matching lower bound is provided for intermediate corruption levels. As a result, the paper demonstrates an interesting interpolation between existing guarantees but does not fully characterize the fundamental difficulty of learning in perturbed markets. Also, the regret bound comparing to OptD\mathrm{Opt}^D requires the underlying stationary distribution to satisfy a σ\sigma-smoothness assumption. This excludes potentially relevant settings with discrete or highly concentrated valuations, even when the market is otherwise stochastic.

Questions for authors

I would say this is an overall good work but I cannot ignore what is going on here at Lemma 3. If the authors can provide a corrected patch on Lemma 3 and Theorem 1 in Appendix, with rigorous proofs and without substantially adjusting the main content and claim, then I would still consider leaning on acceptance. Otherwise the outcome is obvious.

2 comments

We thank the reviewer for identifying the gaps in Lemma 3 and the proof of Theorem 1. We have now replaced Lemma 3 and prove it in Appendix C, and we revised Section 8 and Appendix F. The statement of Theorem 1 is unchanged.The revised Lemma 3 bounds the comparator’s gain from trade plus its signed revenue on the realized Rev-Max rounds, simultaneously for every grid distribution. Moving comparator revenue to the right-hand side gives exactly the term used in Lemma 13.

Adaptive Rev-Max rounds and the signed revenue term. The replacement lemma holds simultaneously for every π∈Δ(GK)\pi\in\Delta (\mathcal G_K), with no budget-feasibility assumption. It bounds ∑t∈T1Eπ[GFTt+Revt]≤M∑t∈T1Revt(pt,qt)+2+MO~(KT),\sum_{t\in\mathcal T_1}\mathbb E_\pi[GFT_t+Rev_t]\le M\sum_{t\in\mathcal{T}_1}Rev_t(p_t,q_t)+2+M\widetilde{O}(\sqrt{KT}), with M=16ln⁡TM=16\ln T. The proof starts from the pointwise identity GFTt(p,q)+Revt(p,q)=(bt−p)+(q−st)\mathrm{GFT}_t(p,q)+\mathrm{Rev}_t(p,q)=(b_t-p)+(q-s_t) whenever the comparator trades. Each positive part is bounded using revenue from a price pair with a dyadic spread, up to the smallest-scale error. This comparison can be summed over the realized Rev-Max rounds. To control revenue on those rounds, we analyze EXP3-IX over the full horizon with zero loss vectors on inactive rounds. Activation depends on the previous round’s budget and is determined before the current arm draw. With fixed bandit parameters, the zero losses leave the weights unchanged, so the full-horizon analysis applies to the implementation that updates only on active rounds.

Application to both benchmarks. Moving the comparator revenue to the right-hand side supplies exactly the term identified in the review. When we combine the two phases, the learner’s Rev-Max revenue cancels, leaving signed comparator revenue with weight 11 on Rev-Max rounds and λt\lambda_t on Primal-Dual rounds. For Program (3), the per-round expected revenue bound −1/K-1/K controls this weighted term at a cost of MT/KMT/K, up to concentration. For Program (4), full-horizon feasibility and the total-variation perturbation bound give a cost of 2MC2MC, up to concentration. The repaired grid approximation proof gives RK=O((σT/K+C)log⁡(2K))R_K=O((\sigma T/K+C)\log(2K)). With the original parameter choices, these bounds yield O~(T3/4)\widetilde{O}(T^{3/4}) regret against OptF\mathrm{Opt}^F and O~(T3/4)+O(Clog⁡T)\widetilde O(T^{3/4})+O(C\log T) regret against OptD\mathrm{Opt}^D for fixed σ\sigma.

Corruption and smoothness. We agree that the endpoint results do not establish a matching lower bound at intermediate corruption levels. Whether linear dependence on CC is necessary in that regime, and whether the log⁡T\log T factor can be removed, remain open. We also agree that smoothness limits the scope of the distributional guarantee. In the proof, bounded density controls the probability of valuations in the narrow strips where rounding changes whether a trade occurs. The fixed-price guarantee requires no smoothness, and the distributional result leaves open what can be achieved for structured discrete markets.

Thank you for the detailed response and the revisions to the manuscript. The revised Lemma 3 and its proof sufficiently address my main soundness concerns, particularly regarding the signed comparator-revenue term, the adaptively selected Rev-Max rounds, and the application to both benchmarks.

I am satisfied with these clarifications and will raise my score accordingly.

Comments on the paper

1 comment

Dear Reviewers,

The reviewer–author discussion period closes in approximately 36 hours. If you have not yet reviewed the authors’ rebuttal, please do so as soon as possible and post a brief acknowledgment, indicating whether the response addresses your main concerns. Please raise any remaining questions promptly so the authors have an opportunity to respond, and update your review and scores if warranted.

Thank you for your time and thoughtful engagement!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.