acceptodds
Under review as a conference paper at ICLR 2027

Bilateral Trade with Independent Sellers and Buyers: Tight Regret under One-Bit Feedback

Abstract

We study regret minimization in repeated bilateral trade under one-bit feedback: over rounds, a learner posts a price to a seller and a price to a buyer to maximize gains-from-trade, but observes only whether trade occurs. When the two valuations are independent and drawn i.i.d. from an unknown distribution with bounded density, the tight regret was still open in two settings: weak budget balance against the best fixed price, and global budget balance against the best feasible distribution over price pairs. In both settings, the best known upper bound was , against a lower bound of . We close both gaps by designing two learning algorithms, one for each setting, each achieving regret . Combined with the known lower bound for correlated valuations, our results reveal that independence makes learning strictly easier in both settings. Our key technical ingredient is a recursion that relies on valuation independence, enabling our algorithms to learn gains-from-trade from trade bits alone while probing only inside the price interval being explored.

Primary area:
learning theory
Keywords:
bilateral trade, online learning, regret minimization, one-bit feedback, budget balance

Reviews

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

This paper studies the problem of bilateral trade with one bit feedback, first under the Weak Budget Balance (WBB) constraint, then under the Global Budget Balance (GBB) constraint. They obtain algorithm with regret of order O~(T2/3)\tilde{O}(T^2/3) in both cases, compared to the best identical buyer and seller price for WBB, and compared to the best distribution verifying in expectation GBB for GBB constraint.

Critical strengths

This paper bridges a gap in the current understanding of stochastic bilateral trade under one bit feedback, where T2/3T^{2/3} lower bound had been previously established, but with no matching lower bounds. This is an interesting result.

The algorithms are new, and I believe they could provide new insights to handle other problems with one bit feedback (e.g., dynamical pricing). The presentation of the first algorithm is especially clear and insightfull.

Critical weaknesses

The second algorithm is complex, and conceptually rather different to the algorithms classically used in this field. Given that the contribution of this paper is purely theoretical (1), I find it disappointing, if not a bit frustrating, that the authors did not spend more space - even in the appendix - to provide more insight on their algorithm. I believe a step-by-step explanation of how and why it works would be very beneficial.

(1) although one can only appreciate the honesty of the authors, the condition on l. 357 is not likely to be realized.

Questions for authors

How should the (infinite) set of candidate laws be constructed and updated in Algorithm GLOBAL-OFU ?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 6qf3

We thank the reviewer for the positive evaluation, and we are honored by the reviewer's kind words on the presentation of the WBB algorithm.

Weakness 1. The second algorithm (GBB) is complex, and conceptually rather different to the algorithms classically used in this field. […] I believe a step-by-step explanation of how and why it works would be very beneficial.

Following this suggestion, we have revised Section 4 to improve its readability, organizing the explanation of the GBB algorithm into paragraphs that each address one step, and we have added comments throughout its pseudocode (Algorithms 2, 3 and 5) to guide the reader through each phase. At a high level, estimating the GFT and the profit of each price pair separately would lead to a bandit problem with (K+1)2(K+1)^2 arms and only O~(T3/4)\widetilde O(T^{3/4}) regret. To avoid this, we split each side of a price pair into consecutive dyadic intervals, and by independence, the information collected on such an interval is shared by every price pair whose decomposition contains it, so the algorithm effectively learns two one-dimensional marginals instead of (K+1)2(K+1)^2 pairs. The new paragraphs of Section 4 give the details, namely, “Difficulties in implementing OFU directly” explains why the pairs cannot be learned separately; “Recursion on dyadic intervals” shows how the recursion of Lemma 2 lets us split the prices into dyadic intervals, and describes how we design the estimates on these intervals to be reused across pairs and epochs; and “Why paths?” explains why the intervals are extended to the paths illustrated in Figure 1. We hope that these revisions improve the reading experience.

Weakness 2. the condition on l. 357 is not likely to be realized.

We agree with the concern about this condition, so we have relaxed it by adjusting the parameters of the GBB algorithm (line 364 of the revised version). This condition is on the number T−τT-\tau of rounds that remain after the first stage, and for example, the resolution K=8K=8 now requires T−τ≥6.6×104T-\tau\ge6.6\times10^{4} rather than about 102110^{21} in the previous version.

Question. How should the (infinite) set of candidate laws be constructed and updated in Algorithm GLOBAL-OFU?

We thank the reviewer for this important question, which concerns the core of our algorithm. Global-OFU represents the confidence set Fk−1\mathcal F_{k-1} implicitly, by the constraints that its laws satisfy. It starts from the set F\mathcal F of all independent laws whose densities are bounded by MM, and its boundary exploration keeps the laws consistent with the estimated trade probabilities at the boundary pairs, which gives F0\mathcal F_0 (Algorithm 3, line 9). At each epoch kk, the algorithm optimistically selects a distribution γk\gamma_k over at most two price pairs by solving an infinite-dimensional problem over Fk−1\mathcal F_{k-1} (Algorithm 3, line 13). It then locates the support pair and the dyadic interval on its paths (detailed in “Recursion on dyadic intervals” of Section 4) at which the candidates disagree most about the local trade probabilities, weighted by the probability of the pair under γk\gamma_k (Algorithm 3, line 16), and refines the candidates there. Since the opposite-side price changes with the support of γk\gamma_k from epoch to epoch, the trade probabilities observed on an interval differ across epochs and cannot be pooled directly. Independence resolves this, as the probes on an interval of one side share the acceptance probability of the opposite side, which cancels in the ratios of their trade probabilities. The algorithm therefore pools the trades on each interval across pairs and epochs and keeps only the candidates whose ratios are consistent with them (Algorithm 5). Once the remaining disagreement is small (Algorithm 3, line 17), the algorithm exploits γk\gamma_k in the remaining rounds.

From a computational perspective, the revised Appendix E shows that the OFU problem is equivalent to a finite-dimensional one, since its objective and constraints depend on a candidate only through O(K)O(K) numbers at the grid prices (Lemma 11), and after a change of coordinates, the image of Fk−1\mathcal F_{k-1} in these numbers is convex and compact (Lemma 12). It also gives a polynomial-time algorithm that solves this problem approximately through O(K4)O(K^4) convex programs per epoch, with the guarantees of GBB and O~(T2/3)\widetilde O(T^{2/3}) regret preserved (Algorithm 8 and Corollary 4).

I thank the authors for these clarifications.

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

The paper studies regret minimisation in bilateral trade settings in which the learner receives one bit of feedback at each round, i.e., whether the trade occurs or not. The paper studies algorithms in scenarios in which the goal is to minimise regret compared to an optimal benchmark maximising gain from trade (GFT) when the buyer and the seller valuations are independent and drawn i.i.d. from a fixed distribution with bounded density. They focus in particular on weak budget balance against the best fixed price, and global budget balance against a distribution over price pairs.

Critical strengths
  • The paper closes two open problems in the literature on regret minimisation in bilateral trade.
  • The authors do a good job of identifying the two aforementioned open problems through the two tables presented in the appendix. This greatly helps to position the contribution of their work relative to previous work.
  • The paper uses two recursive approaches to estimate GFT in the two settings considered, making it interesting from a technical perspective.
Critical weaknesses
  • While I acknowledge that the paper addresses two open problems in the literature on online learning in bilateral trade, I think that the contribution and the scope of the paper are somewhat limited and may be of interest to only a small niche. A discussion of whether the techniques developed here could extend to more general models would help clarify the broader relevance of the contribution.
  • From lines 422-424, the computational complexity of the algorithm is not clear. At line 1553, the authors state that "solving the OFU problem requires O(K9)O(K^9) convex programs." Thus, the algorithm appears particularly expensive from a computational point of view.
Questions for authors
  • Could the authors clarify the relationship between TREE-SEARCH and the zooming algorithm in [1]? TREE-SEARCH appears to refine promising regions using a rule that combines interval width and estimated GFT, resembling the zooming rule underlying zooming algorithms. The main technical difference seems to lie in how the reward is estimated, since GFT is not directly observed and must be reconstructed recursively from one-bit feedback. Is this interpretation correct, or are there other substantial differences in the exploration strategy?

[1] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-Armed Bandits in Metric Spaces. STOC, 2008.

3 comments
AuthorsOpenReview ↗

Response to Reviewer nhWf (Part 1)

We thank the reviewer for the constructive feedback and for appreciating the technical contributions of our paper.

Weakness 1. A discussion of whether the techniques developed here could extend to more general models would help clarify the broader relevance of the contribution.

Our techniques based on the recursion (Lemmas 1 and 2) rely only on the quasi-linear structure of the utilities and the independence of the valuations, which makes them potentially extendable to many other areas. We share the view of Reviewer 6qf3 that our algorithms could provide new insights into other problems with a similar quasi-linear structure and one-bit feedback, such as dynamic pricing, principal-agent games, inventory management and Pandora's box.

Weakness 2. At line 1553, the authors state that “solving the OFU problem requires O(K9)O(K^9) convex programs.” Thus, the algorithm appears particularly expensive from a computational point of view.

Through a first-order approximation, Appendix E.1 now reduces the number of convex programs per epoch from O(K9)O(K^9) to O(K4)O(K^4), with the guarantees of GBB and O~(T2/3)\widetilde O(T^{2/3}) regret preserved. In fact, the number of convex programs can be further reduced to O(K)O(K) per epoch by optimizing the seller-side and buyer-side terms of the GFT and the profit separately rather than over a single candidate. However, since the O(K)O(K) method requires a more involved analysis and more technical details, which is beyond the scope of this work, we do not include it in the paper.

AuthorsOpenReview ↗

Response to Reviewer nhWf (Part 2)

Question. Could the authors clarify the relationship between TREE-SEARCH and the zooming algorithm in [1]? TREE-SEARCH appears to refine promising regions using a rule that combines interval width and estimated GFT, resembling the zooming rule underlying zooming algorithms. The main technical difference seems to lie in how the reward is estimated, since GFT is not directly observed and must be reconstructed recursively from one-bit feedback. Is this interpretation correct, or are there other substantial differences in the exploration strategy?

[1] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-Armed Bandits in Metric Spaces. STOC, 2008.

This question is insightful and interesting. The diagonal GFT GFT(z,z)\mathsf{GFT}(z,z) is MM-Lipschitz in the price zz (Lemma 3), and the arm space [0,1][0,1] is one-dimensional, so with bandit feedback, the zooming algorithm of [1], with the guarantee O~(T(d+1)/(d+2))\widetilde O(T^{(d+1)/(d+2)}) for an arm space of covering dimension dd, would already achieve O~(T2/3)\widetilde O(T^{2/3}) regret. Under one-bit feedback, however, posting (z,z)(z,z) only reveals whether trade occurs, so the reward has to be recovered in additional rounds. The following block-based zooming algorithm shows that the cost of these rounds cannot be ignored.

Algorithm. Split the TT rounds into NN blocks of T/NT/N rounds. In each block kk, do the following:

  1. Select. Zooming selects a price zkz_k based on the samples of the previous blocks.
  2. Estimate. In the first round tt of the block, post (X,zk)(X,z_k) with X∼Unif[0,zk]X\sim\mathrm{Unif}[0,z_k] with probability zkz_k, and (zk,Y)(z_k,Y) with Y∼Unif[zk,1]Y\sim\mathrm{Unif}[z_k,1] otherwise, and pass the trade bit ZtZ_t to zooming as the sample of zkz_k.
  3. Exploit. Post (zk,zk)(z_k,z_k) in the remaining TN−1\frac{T}{N}-1 rounds of the block.

The trade bit ZtZ_t in step 2 is an unbiased sample of GFT(zk,zk)\mathsf{GFT}(z_k,z_k), so zooming learns from these NN samples as under bandit feedback, and its guarantee bounds the total gap of the selected prices by E[∑k=1N(GFTW⋆−GFT(zk,zk))]=O~(N2/3)\mathbb E\bigl[\sum_{k=1}^{N}\bigl(\mathsf{GFT}^\star_{\mathrm W}-\mathsf{GFT}(z_k,z_k)\bigr)\bigr]=\widetilde O(N^{2/3}). Each gap is incurred in the TN−1\frac{T}{N}-1 rounds of step 3, leading to O~(TN−1/3)\widetilde O(TN^{-1/3}) regret in total, and the round of step 2, which posts prices spread over [0,1][0,1], costs a constant regret even when zk=z⋆z_k=z^\star, so the regret is O~(TN−1/3)+O(N)=O~(T3/4)\widetilde O(TN^{-1/3})+O(N)=\widetilde O(T^{3/4}) for N=T3/4N=T^{3/4}. Under one-bit feedback, the cost of estimation thus directly determines the rate.

In terms of the discretization parameter KK of our paper, the algorithm above reaches resolution 1/K1/K after N=O~(K3)N=\widetilde O(K^3) samples in the worst case, each of constant regret, and TREE-SEARCH reduces the resulting estimation regret from O~(K3)\widetilde O(K^3) to O~(K2)\widetilde O(K^2) by reusing information along its tree. Applied to an interval (p,q)(p,q), Lemma 1 recovers the midpoint utilities from the endpoint utilities US(p)U_S(p) and UB(q)U_B(q) and from trade probabilities at prices inside [p,q][p,q], and TREE-SEARCH applies it to dyadic intervals, starting from (0,1)(0,1). The endpoint utilities of an interval are midpoint utilities already estimated at smaller depths, so TREE-SEARCH reuses them and only posts prices inside the current interval, whose width at depth jj is 2−j2^{-j}. Moreover, TREE-SEARCH prunes every interval whose estimated GFT plus a slack proportional to its width falls below the best estimate (Algorithm 1, line 8), and this optimistic screening is similar in spirit to the arm selection of zooming. As a result, the midpoint of every interval at depth jj stays within O(2−j)O(2^{-j}) of the optimal GFT (Lemma 5), and each round at depth jj costs only O(2−j)O(2^{-j}) regret. Since the tree holds at most 2j2^j intervals at depth jj, the smaller per-round regret exactly offsets its growth, so with O~(K2)\widetilde O(K^2) rounds per interval every depth costs O~(K2)\widetilde O(K^2), and all O(log⁡K)O(\log K) depths together cost O~(K2)\widetilde O(K^2) rather than O~(K3)\widetilde O(K^3). Balancing this with the exploitation regret O(T/K)O(T/K) gives O~(T2/3)\widetilde O(T^{2/3}) at K=T1/3K=T^{1/3} instead of O~(T3/4)\widetilde O(T^{3/4}) at K=T1/4K=T^{1/4}. We therefore agree with the reviewer's interpretation. TREE-SEARCH shares the optimism-based multiscale exploration of zooming, while its key technical contribution is the recursive reuse of conditional-utility estimates, which improves the regret to O~(T2/3)\widetilde O(T^{2/3}).

Thank you for your responses. I am keeping my original score.

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

This paper studies bilateral trade from the online learning perspective. In particular, it focuses on two specific regimes which were overlooked by previous results: gain-from-trade maximization with one-bit feedback, when the agents’ valuations are generated by smooth and independent distributions, and the learner has to enforce either weak budget balance, or global budget balance.

In the first case, the learner’s profit has to be non-negative at each time step (i.e., the price posted to the seller should be at least that posted to the buyer), and the regret is measured with respect to the best fixed price in hindsight. In this setting, the paper proposes a O(T2/3)O(T^{2/3}) regret algorithm, matching a known lower bound, and improving on the previous state of the art of O(T3/4)O(T^{3/4}), which is tight for possibly non-independent distributions. This algorithm is based on an interesting recursive estimation technique, which exploits the specific structure of the GFT objective under the independence assumption.

In the second case, the learner’s overall profit has to be non-negative, and the regret is measured against the most challenging benchmark of the best distribution over prices, which enforce budget balance in expectation. In this setting, the paper proposes a O(T2/3)O(T^{2/3}) regret algorithm, matching a known lower bound, and improving on the previous state of the art of O(T3/4)O(T^{3/4}), which is tight for possibly non-independent distributions. This result is achieved using the two-phase approach by Bernasconi et al, combined with the novel Global OFU routine.

Critical strengths

The paper studies an interesting problem, which has received a lot of attention in both theory and ML conferences. The results proposed are tight, and they consider settings which are reasonable, improving on known results by partly novel methods, as far as I understand. The algorithmic problems are non-trivial, and they are solved by clever algorithms.

Critical weaknesses

The main weakness of the paper consists in the presentation quality of the technical results. From the main body it is nearly impossible to understand the algorithms proposed, and get an intuition of the regret guarantees. I understand the ICLR page limit, but the quality of exposition is definitely below the bar. Perhaps it would have been beneficial to replace the very technical description of GLOBAL-OFU with a clearer idea of why such a routine is necessary and how it solves the given challenges. Some concrete instances that made the paper difficult to understand:

  • In line 267, the authors talks about MIDPOINT-EST without introducing it, pointing to the pseudocode which is in the appendix.

  • In the pseudocode of algorithm 2, who are β,F\beta, \mathcal F, and KK? In which line of the pseudocode are they defined?

  • The two paragraphs in the Section 1.1 “A recursive estimation method.” and “The WBB algorithm.” were too condensed for me to get much of an idea of the techniques without consulting the main section. In order to be helpful they would need to be more detailed.

  • The definition of candidates F\mathcal{F} is not explained very well. The following sentence in line 366-368 “. The previous mechanism of Lunghi et al. (2026b) reduces GFT exploration to 2K groups (...)” is very difficult to make sense of without being quite familiar with the cited paper.

  • The “GLOBAL-OFU subroutine.” description starting at line 370 is difficult to follow since most paragraphs it contains don’t make it initially clear what the purpose of the current step is.

Questions for authors
  • How much of the papers’ techniques is novel, in particular compared to Lunghi et al. (2026b)?
3 comments
AuthorsOpenReview ↗

Response to Reviewer v2qT (Part 1)

We thank the reviewer for recognizing the contributions of our work and for the constructive feedback on its presentation. Following the reviewer's suggestions, we have revised the presentation of the relevant parts of the paper to improve its readability. In particular, for the GBB part, Section 4 now first gives an overview of the algorithm and its three phases (the "Algorithm overview" paragraph), and then explains step by step why the algorithm collects profit before exploring (the "Collecting profit first" paragraph), why a direct implementation of OFU fails (the "Difficulties in implementing OFU directly" paragraph), how a recursion on dyadic intervals overcomes these difficulties (the "Recursion on dyadic intervals" paragraph), and why these intervals are extended to paths that reach the boundary (the "Why paths?" paragraph), so as to convey the intuition behind the design of the algorithm. We have also added comments throughout the pseudocode, which we hope will make the algorithms easier to follow.

Weakness 1. In line 267, the authors talks about MIDPOINT-EST without introducing it, pointing to the pseudocode which is in the appendix.

Once the utilities at the endpoints pp and qq are known, Lemma 1 expresses the utilities at the midpoint z=p+q2z=\tfrac{p+q}{2} through five trade probabilities, each of which can be estimated from the observed trade bits. MIDPOINT-EST estimates these five probabilities by empirical trade frequencies and outputs the utilities given by the recursion, together with the resulting estimate of the GFT at the midpoint. To introduce it where the recursion is first used, we now state its role right after Lemma 1, with a link to its pseudocode (Algorithm 4 in Appendix B.2) for easy reference (lines 259–261), “Lemma 1 instead lets us estimate the utilities recursively (the subroutine MIDPOINT-EST, Algorithm 4, carries out this estimation)”.

Weakness 2. In the pseudocode of algorithm 2, who are β\beta, F\mathcal F, and KK? In which line of the pseudocode are they defined?

In Algorithm 2, β\beta is the amount of profit that the first stage accumulates to pay for exploration (lines 360–361), and KK is the discretization parameter of the price grid (lines 364–367). The set F\mathcal F of candidate valuation laws (to avoid confusion, we refer to the distribution of the valuations as their law and reserve the term distribution for distributions over price pairs, as we do in the paper) contains all independent laws whose densities are bounded by MM (lines 369–372). In the revision, we name the inputs of Algorithms 2 and 3 (e.g., “horizon TT, density bound MM” and “discretization parameter KK, set of laws with bounded densities F\mathcal F, stopping round τ\tau”) and add comments to Algorithm 2 that explain the parameters of PROFIT-MAX and the stopping round τ\tau, to avoid the confusion caused by defining these parameters only in the main text, and we hope that this makes the pseudocode easier to read.

Weakness 3. The two paragraphs in the Section 1.1 “A recursive estimation method.” and “The WBB algorithm.” were too condensed for me to get much of an idea of the techniques without consulting the main section. In order to be helpful they would need to be more detailed.

This suggestion helped us re-examine how the introduction presents our techniques. In the paragraph “The WBB algorithm.” (lines 118–124), we now explain why the recursion lets the algorithm refine a dyadic tree of prices, so that the reader can build an intuition for the algorithm when reading this part. The revised sentence now reads as follows, “For WBB, the recursion (Lemma 1) gives the utilities at the midpoint of an interval from those at its endpoints and trade probabilities at prices inside it, so the utilities estimated at a midpoint serve as endpoint utilities of the two halves, which lets the algorithm refine a dyadic tree of prices while probing only inside the interval to reduce the estimation loss”.

AuthorsOpenReview ↗

Response to Reviewer v2qT (Part 2)

Weakness 4. The definition of candidates F\mathcal F is not explained very well. The following sentence in line 366-368 “The previous mechanism of Lunghi et al. (2026b) reduces GFT exploration to 2K2K groups (…)” is very difficult to make sense of without being quite familiar with the cited paper.

The set F\mathcal F consists of all independent valuation laws whose seller and buyer densities are bounded by MM, and GLOBAL-OFU starts from F\mathcal F and keeps only the laws consistent with the observed trades. On top of the formula given in the submitted version, the revision (lines 369–377) adds a description of F\mathcal F in words, and explains that for a given candidate law θ∈F\theta\in\mathcal F, the trade probability, the GFT and the profit of every price pair can be computed. We hope that this helps the reader understand the role of F\mathcal F. As for the comparison with Lunghi et al. (2026b), we moved it to the end of Section 4 to keep the description of our algorithm fluent, and the separate paragraph “Comparison with Lunghi et al. (2026b)” (lines 518–532) now explains it in detail.

Weakness 5. The “GLOBAL-OFU subroutine.” description starting at line 370 is difficult to follow since most paragraphs it contains don't make it initially clear what the purpose of the current step is.

We agree that the purpose of each step should come first. In the revision, we therefore organize the description of GLOBAL-OFU around the difficulties that it resolves, and each paragraph starts from the question it answers. “Collecting profit first” (line 356) explains that learning the benchmark requires posting subsidized price pairs, so the algorithm first accumulates a profit reserve to pay for them. “Difficulties in implementing OFU directly” (line 423) explains why estimating the GFT and the profit of each selected pair separately fails, as these estimates are not reused across pairs and the probes can be far from the selected pair. “Recursion on dyadic intervals” (line 438) first extends the recursion of Lemma 1 to Lemma 2, which propagates the utility of each side across a short interval using only trade probabilities at prices inside it, and then resolves both difficulties by decomposing each side of a pair into dyadic intervals, on which the probes stay close to the pair and, by independence, the observations are shared by all pairs and epochs. “Why paths?” (line 481) explains why these intervals are extended to paths that reach the boundary, along which the scale of the marginal probabilities is recovered. We have also added comments to the pseudocode of Algorithms 2, 3 and 5 that state the role of each phase and step.

Question. How much of the papers' techniques is novel, in particular compared to Lunghi et al. (2026b)?

In the revised version, we discuss this in a separate paragraph, “Comparison with Lunghi et al. (2026b)” (lines 518–532). Both algorithms use the same PROFIT-MAX algorithm of Bernasconi et al. (2024) to collect profit. After this stage, Lunghi et al. (2026b) split the GFT through a more general version of our decomposition that holds without independence (lines 519–521), GFT(p,q)=E[(p−s),1s≤p,b≥q]⏟L(p,q)+E[(b−q),1s≤p,b≥q]⏟R(p,q)+PRO(p,q),\mathsf{GFT}(p,q) =\underbrace{\mathbb E\bigl[(p-s)\\,\mathbf 1\\{s\le p,\\ b\ge q\\}\bigr]}_{L(p,q)} +\underbrace{\mathbb E\bigl[(b-q)\\,\mathbf 1\\{s\le p,\\ b\ge q\\}\bigr]}_{R(p,q)} +\mathsf{PRO}(p,q), where LL and RR are not directly observable by posting (p,q)(p,q). They estimate LL and RR on the whole grid by pairing a uniform price with each buyer price and each seller price, and then learn the remaining profit through a constrained bandit problem with K2K^2 arms, which leads to O~(T3/4)\widetilde O(T^{3/4}) regret. Our algorithm instead learns the valuation law itself, which determines the GFT and the profit of all pairs at once, since under a given candidate law θ\theta, the gain-from-trade GFTθ(p,q)=E(s,b)∼θ[(b−s),1s≤p,b≥q]\mathsf{GFT}_\theta(p,q)=\mathbb E_{(s,b)\sim\theta}\bigl[(b-s)\\,\mathbf 1\\{s\le p,\\ b\ge q\\}\bigr] and the profit PROθ(p,q)=(q−p)⋅Pr⁡(s,b)∼θ[s≤p,b≥q]\mathsf{PRO}_\theta(p,q)=(q-p)\cdot\Pr_{(s,b)\sim\theta}[s\le p,\\ b\ge q] are expectations under a known law and can be computed for every price pair (see our explanation of the candidate laws in lines 373–377). Independence makes this law a product of its two marginals, so the trades observed on a dyadic interval of one side constrain the same marginal for every pair whose decomposition contains this interval. These observations are therefore reused across pairs and epochs, which avoids the K2K^2-armed problem and yields O~(T2/3)\widetilde O(T^{2/3}) regret.

Thank you again for your review. If your main concerns are now resolved, we would appreciate it if you could consider revising your score. Please let us know if any significant concerns remain.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.