betaFeedback

WorksComputer Science

Contextual Search and Bilateral Trade with a Trace-Square-Root Potential

Abstract

We present a unified potential method for contextual search and bilateral trade with one-bit feedback and obtain order-tight algorithms for both problems. Our framework starts from a Bayesian perspective in which the unknown target (for contextual search) and the unknown pair of valuations (for bilateral trade) are sampled from a known prior distribution. In that model, the decision maker bases its prediction on the posterior distribution, obtained by conditioning on feedback received in previous rounds. For Bayesian contextual search, we present an algorithm with a total loss bounded by O(TrΣ)O(\mathrm{Tr} \sqrt Σ), where ΣΣ is the covariance matrix of the target's prior; and for contextual bilateral trade, our algorithm's regret is bounded by O(TrΣS+TrΣB)O(\mathrm{Tr} \sqrt{Σ_S}+\mathrm{Tr} \sqrt{Σ_B}), where ΣSΣ_S and ΣBΣ_B are the covariance matrices of the seller's and buyer's valuations. We then use ideas from this Bayesian setting and adapt a ``dual'' of this trace-square-root potential to the classical worst-case setting, where the target and valuations are chosen adversarially from the unit Euclidean ball. For both contextual search and bilateral trade, we obtain tight O(d)O(\sqrt d)-regret algorithms. These results match the existing lower bounds up to a constant factor and improve on the previous guarantees of O(dlog⁡d)O(d\log d) for contextual search and of O(d6d)O(d6^d) for bilateral trade.

Introduction

We study parameter search problems in settings where decision makers receive only limited feedback. For example, a pricing algorithm sees the features of the customer, quotes a price for a product described by a feature vector and learns only whether the customer bought it. An idealized dosing procedure receives patient features and learns only whether the dose was too low or too high. A broker quotes prices to both a buyer and a seller, and learns only whether they traded. In each case, there is a vector hidden from the learner, and at each step, the observed features provide a “context”: together, the hidden vector and the context determine a target value that the learner tries to match. In this paper, we study two classical problems at the intersection of theoretical computer science and economics that are inspired by such situations: contextual search and contextual bilateral trade.

Contextual search. The basic problem in this setting is contextual search, where the target is an unknown vector z∈Rdz \in\mathbb{R}^{d}. In round tt, an adversary reveals the context vector xtx_t with ∥xt∥2≤1\lVert x_t\rVert_2 \le1. The two together define the target value xtTzx_t^{\mathsf{T}}z—this is unknown to the learner, since zz is unknown. The learner does observe xtx_t, then proposes a price ptp_t and incurs symmetric loss ℓt=∣xtTz−pt∣\ell_t = \lvert x_t^{\mathsf{T}}z - p_t\rvert. The learner observes neither the target value nor the loss incurred, but only the one-bit feedback sign⁡(xtTz−pt)\operatorname{sign}(x_t^{\mathsf{T}}z-p_t)—i.e., whether the price was too high or too low. Using this information, the learner aims to bound its total loss ∑t=1TE[ℓt]\sum_{t=1}^{T} \mathbb{E}[\ell_t] (also called the “regret”) independently of TT. The problem of contextual search arose from feature-based pricing and auctions [15, 9, 17]. It is useful to note that, for d=1d = 1, the problem reduces to binary search, but higher-dimensional versions become much more challenging. Indeed, a series of works has studied this problem, and the state of the art is an O(dlog⁡d)O(d\log d)-competitive algorithm [16]. However, the lower bound was only Ω(d)\Omega(\sqrt{d}): can we close this gap?

Contextual bilateral trade. An extension of contextual search is bilateral trade, where the learner is a broker who intermediates between a seller and a buyer with hidden vectors s,b∈Rds,b \in\mathbb{R}^{d}. In round tt, an adversary reveals a context vector xtx_t with ∥xt∥2≤1\lVert x_t\rVert_2 \le1 corresponding to valuations xtTsx_t^{\mathsf{T}}s for the seller and xtTbx_t^{\mathsf{T}}b for the buyer—these are unknown to the broker, who does not see s,bs,b. The broker then proposes a price ptp_t and observes whether both agents are willing to trade at that price, i.e., if xtTs≤pt≤xtTbx_t^{\mathsf{T}}s \le p_t \le x_t^{\mathsf{T}}b. Note that, given the feedback structure, a failed trade does not identify which agent refused. The broker aims to maximize gain from trade, defined as ∑(xtTb−xtTs)+\sum(x_t^{\mathsf{T}}b-x_t^{\mathsf{T}}s)_+, where the sum is taken over all rounds tt in which the trade took place, or equivalently, to minimize the total loss ∑t=1TE[ℓt]\sum_{t=1}^{T}\mathbb{E}[\ell_t], which is the total gain from trade it failed to realize. The model was introduced by Gaucher et al. [GBC⁺25], building on the online bilateral trade framework of Cesa-Bianchi et al. [CBC⁺21, CCC⁺24]. The gaps left by the literature are much larger in this setting: the only upper bound for this one-bit feedback model is O(dδb)O(d\delta^b) [CFG⁺26], and the lower bound is again Ω(d)\Omega(\sqrt{d}), leaving a huge gap: can we close it?

Results

In this work, we give tight results for both these problems: we show that both problems admit O(d)O(\sqrt{d})-regret algorithms, which are tight by the lower bounds mentioned above. In addition to giving tight results, however, our work showcases the use of a potential function—the square-root trace potential—which is the central tool in both analyses. Moreover, we also present results for the Bayesian setting (where zz, ss, and bb are drawn from known prior distributions), which inspire our algorithms for the adversarial setting.

Worst-case guarantees. For worst-case guarantees, the unknown target z∈Rdz \in\mathbb{R}^d and the valuation vectors s,b∈Rds,b \in\mathbb{R}^d are assumed to be selected from the Euclidean unit ball by the adversary. The adversary knows the learner’s algorithm, but not the random bits it uses. This is the main point of view taken in prior works on both contextual search and bilateral trade. We obtain horizon-independent O(d)O(\sqrt{d}) expected-loss bounds for both problems, matching the existing lower bounds up to constant factors. Table 1 summarizes our worst-case guarantees and compares them with prior work for contextual search and bilateral trade.

ResultContextual searchBilateral trade
Standard lower bound [16, 8]d\sqrt{d}d/6\sqrt{d}/6
Paes Leme and Schneider [19]O(d4)O(d^4)—
Liu, Paes Leme, and Schneider [16]O(dlog⁡d)O(d\log d)—
Cosson et al. [8]—O(d6)O(d^6)
This paper (Thms. 2.4 and 3.4)O(d)O(\sqrt{d}) (Alg. 2)O(d)O(\sqrt{d}) (Alg. 4)

Table 1. Worst-case guarantees for unit-norm contexts and hidden vectors.

Bayesian guarantees. For Bayesian guarantees, we assume that the unknown vectors z,s,b∈Rdz,s,b \in\mathbb{R}^d are sampled from a known prior distribution with finite second moments. This point of view deviates from the existing literature but is particularly illuminating: it yields simpler algorithms and a first potential function, based on posterior covariance, that will guide the adversarial analysis. For known priors with finite second moments, our bounds depend only on the prior covariance matrices and hold at every horizon (Table 2).

ResultContextual searchBilateral trade
This paper (Thms. 2.1 and 3.2)O(Tr⁡Σ)O(\operatorname{Tr}\sqrt{\Sigma}) (Alg. 1)O(Tr⁡ΣS+Tr⁡ΣB)O(\operatorname{Tr}\sqrt{\Sigma_S}+\operatorname{Tr}\sqrt{\Sigma_B}) (Alg. 3)

Table 2. Bayesian rates for unit-norm contexts and priors with finite second moments. Σ\Sigma is the prior covariance in contextual search, and ΣS,ΣB\Sigma_S,\Sigma_B are the seller’s and buyer’s marginal prior covariances in bilateral trade.

Our worst-case guarantees and our Bayesian guarantees are clearly related, since Tr⁡Σ=O(d)\operatorname{Tr}\sqrt{\Sigma}=O(\sqrt{d}) when Σ\Sigma is the covariance matrix associated with the uniform distribution in the Euclidean ball. Yet neither directly implies the other: in particular, the Bayesian setting allows for distributions with unbounded support or with skewed covariance matrices, such as Gaussian distributions. Thus, the Bayesian setting is not merely an intermediate conceptual step toward worst-case competitive guarantees, but is of independent interest.

Our Techniques

We now outline the intuition behind our algorithms and the essential ingredients of their analysis.

Our Algorithms

In the Bayesian setting, the learner is given a prior distribution on the hidden parameters: the vector zz for contextual search, or the pair (b,s)(b,s) for contextual bilateral trade. Using this, at any time tt, the learner has access to the posterior distribution of the unknown parameters zz or $s,b conditioned on all the past observations. Our Bayesian algorithms (Algorithms 1 and 3) compute a proposed price ptp_t based only on that posterior distribution and on the context vector xtx_t; then they update the posterior distribution with the corresponding feedback. Our Bayesian algorithm for contextual search (Algorithm 1) is remarkably simple: it posts prices μt±σt/2\mu_t \pm\sigma_t/2, where μt\mu_t is the posterior mean of xtTzx_t^\mathsf{T}z, and σt\sigma_t is the posterior standard deviation of xtTzx_t^\mathsf{T}z. The bilateral trade algorithm (Algorithm 3) similarly uses the posterior, now of the two projected values xtTsx_t^\mathsf{T}s and xtTbx_t^\mathsf{T}b, and posts a common price to both agents. This price is chosen to balance trading and learning, allowing us to bound total regret by the learner’s initial uncertainty (Lemma 3.1).

In the worst-case setting, the learner has no posterior distribution on the unknown parameters, so it maintains a suitable “proxy” for the potential used in the Bayesian analysis. For contextual search, it maintains two parameters, a vector mt∈Rdm_t \in\mathbb{R}^d and a matrix Rt∈Rd×dR_t \in\mathbb{R}^{d \times d}, which we call the posterior mean proxy and the posterior square-root covariance proxy. Informally, these parameters can be interpreted as an estimate of the unknown parameter (for mtm_t) and a measure of uncertainty in that estimate in all directions (for RtR_t). Importantly, we do not maintain explicit uncertainty sets as in previous work—in particular, the unknown parameter need not lie within the ellipsoid mt+RtBdm_t + R_t B_d, where BdB_d is the unit Euclidean ball (as, e.g., in the ellipsoid method). Instead, our proofs directly show that the per-step regret can be charged to the decrease in a certain potential. From this perspective, the worst-case contextual search algorithm (Algorithm 2) posts prices mt±rt/2m_t \pm r_t/2, where mt=xtTmtm_t = x_t^\mathsf{T}m_t, and rt=∥Rtxt∥2r_t = \lVert R_t x_t\rVert_2—a rule remarkably similar to the Bayesian rule in Algorithm 1. For bilateral trade (Algorithm 4), mt∈R2dm_t \in\mathbb{R}^{2d} stores separate dd-dimensional mean proxies for the seller and buyer, and the matrix Rt∈R2d×2dR_t \in\mathbb{R}^{2d \times2d} is block diagonal, with one d×dd \times d block for each agent’s square-root covariance proxy. The algorithm samples a common price and two possible successor states from a finite lottery, then keeps the successor selected by the trade bit. Whereas contextual search admits explicit state updates, here we apply the minimax theorem to guarantee the existence of a single lottery that works for every possible hidden pair of buyer and seller.

Although the focus of the paper is not on computational complexity, we note that our worst-case contextual search algorithm (Algorithm 2) uses O(d2)O(d^2) memory throughout the execution and performs only O(d2)O(d^2) operations per round, making it significantly more practical than previous approaches for contextual search that rely on costly geometric routines such as computing intrinsic volumes or barycenters of high-dimensional convex bodies [19, 16].

Analyses via the Trace-Sqrt Potential

We bound the regret of all our algorithms via a potential-based analysis, using a pair of potential functions we feel may be useful in other contexts. It will be illuminating to start with the Bayesian problem for contextual search. Here we have a random vector z∈Rdz \in\mathbb{R}^d with finite second moment; this represents the hidden vector that a learner does not know; however, we do know the distribution from which zz is drawn, and hence know its mean μ=E[z]\mu= \mathbb{E}[z] and covariance Σ=Cov⁡(z)⪰0\Sigma= \operatorname{Cov}(z) \succeq0. In order to quantify the uncertainty about zz, we use the trace-sqrt potential of the covariance:

Ψ(Σ)=Tr⁡Σ=∑i=1dσi,(1)\Psi(\Sigma) = \operatorname{Tr}\sqrt{\Sigma} = \sum_{i=1}^{d} \sigma_i, \tag*{(1)}

where σi=λi\sigma_i = \sqrt{\lambda_i} is the square root of the ii-th eigenvalue of Σ\Sigma, commonly called the ii-th semiaxis length; see Figure 1 for an illustration. The figure highlights a key point: the potential naturally captures a notion of “distance” and “spread”, as opposed to other potentials (like the logarithm of the volume) which would need various tricks to relate regret to the reduction in the volume, incurring losses along the way.

The covariance ellipsoid associated with $\Sigma$, shown with its principal axes and enclosing box

Figure 1. The covariance ellipsoid associated with Σ\Sigma. Geometrically, the trace-square-root potential Ψ=σ1+σ2\Psi= \sigma_1 + \sigma_2 equals the 1-dimensional intrinsic volume (i.e., half the perimeter) of the smallest enclosing box of the ellipsoid, divided by 2. This perspective relates our potential to early geometric approaches to contextual search [19], which relied on intrinsic volumes.

Whatever the learner observes next — the feedback from a round, a new context, or any other information revealed about zz — is a signal: a random variable YY defined jointly with zz. After observing YY, the remaining uncertainty is described by z∣Yz \mid Y; let the new covariance matrix be ΣY\Sigma_Y. This means the potential moves from Ψ(Σ)\Psi(\Sigma) to Ψ(ΣY)\Psi(\Sigma_Y).

The effect of signals on the potential. The first important observation is this: For any signal YY, the law of total covariance (which states that the total covariance equals the expected posterior covariance plus the covariance of the posterior mean) gives

Cov⁡(z)⪰E[Cov⁡(z∣Y)].(2)\operatorname{Cov}(z) \succeq\mathbb{E}[\operatorname{Cov}(z \mid Y)] . \tag*{(2)}

Now, the monotonicity and concavity of the operator A↦AA \mapsto\sqrt{A} on the positive-semidefinite cone (see, e.g., Example 3.48 in [5]) allow us to infer that the potential is monotone in the Löwner order. This, combined with (2), means that

Ψ(Σ)≥E[Ψ(ΣY)](3)\Psi(\Sigma) \ge\mathbb{E}[\Psi(\Sigma_Y)] \tag*{(3)}

and hence the potential is non-increasing in expectation. Of course, this expected decrease is not good enough—we need the potential decrease to pay for our regret.

Potential drops versus directional uncertainty. The key ingredient in relating the potential drop to our regret is the following claim, which is a strengthening of the matrix square-root function’s monotonicity and concavity:

References

  1. [1]Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. In NIPS, pages 622–630, 2014.
  2. [2]M. Bernasconi, M. Castiglioni, A. Celli, and F. Fusco. No-regret learning in bilateral trade via global budget balance. In Proceedings of the ACM Symposium on Theory of Computing (STOC), 2024.DOI
  3. [3]O. Besbes, Y. Fonseca, and I. Lobel. Contextual inverse optimization: Offline and online learning. Operations Research, 73(1):424–443, 2025.
  4. [4]A. Bärmann, S. Pokutta, and O. Schneider. Emulating the expert: Inverse optimization through online learning. In Proceedings of the International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pages 400–410, 2017.
  5. [5]Stephen Boyd and Lieven Vandenberghe. Convex optimization, volume 1. Cambridge university press, Cambridge, 2004.
  6. [7]Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Math. Oper. Res., 49(1):171–203, 2024.
  7. [8]R. Cosson, F. Fusco, A. Gupta, S. Leonardi, R. Paes Leme, and M. Russo. Contextual online bilateral trade. In Proceedings of the ACM Conference on Economics and Computation (EC), 2026. arXiv:2602.12903.arxiv.org/abs/2602.12903
  8. [9]M. C. Cohen, I. Lobel, and R. Paes Leme. Feature-based dynamic pricing. Management Science, 66(11):4921–4943, 2020.
  9. [10]S. Gaucher, M. Bernasconi, M. Castiglioni, A. Celli, and V. Perchet. Feature-based online bilateral trade. In International Conference on Learning Representations (ICLR), 2025. arXiv:2405.18183.arxiv.org/abs/2405.18183
  10. [11]Simone Di Gregorio, Paul Dütting, Federico Fusco, and Chris Schwiegelshohn. Nearly tight regret bounds for profit maximization in bilateral trade. In FOCS, pages 1570–1594. IEEE, 2025.DOI
  11. [12]S. Gollapudi, G. Guruganesh, K. Kollias, P. Manurangsi, R. Paes Leme, and J. Schneider. Contextual recommendations and low-regret cutting-plane algorithms. In Advances in Neural Information Processing Systems, 2021.arxiv.org/abs/2106.04819
  12. [13]Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, and David P Woodruff. Optimal and efficient online inverse optimization. arXiv preprint arXiv:2610.08735, 2026.arxiv.org/abs/2610.08735
  13. [14]Adel Javanmard. Perishability of data: Dynamic pricing under varying-coefficient models. J. Mach. Learn. Res., 18:53:1–53:31, 2017.arxiv.org/abs/1701.03537
  14. [15]Robert D. Kleinberg and Frank Thomson Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In FOCS, pages 594–605. IEEE Computer Society, 2003.DOI
  15. [16]A. Liu, R. Paes Leme, and J. Schneider. Optimal contextual pricing and extensions. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1059–1078, 2021. arXiv:2003.01703.arxiv.org/abs/2003.01703
  16. [17]I. Lobel, R. Paes Leme, and A. Vladu. Multidimensional binary search for contextual decision-making. Operations Research, 66(5):1346–1361, 2018.
  17. [18]R. B. Myerson and M. A. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29(2):265–281, 1983.DOI
  18. [19]R. Paes Leme and J. Schneider. Contextual search via intrinsic volumes. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 268–282, 2018.
  19. [20]S. Sakaue. Tight regret bound for online inverse linear optimization via multiscale matrix weights. arXiv preprint arXiv:2609.26978, 2026.arxiv.org/abs/2609.26978
  20. [21]Naum Z Shor. Cut-off method with space extension in convex programming problems. Cybernetics, 13(1):94–96, 1977.DOI
  21. [22]M. Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171–176, 1958.DOI
  22. [23]S. Sakaue, T. Tsuchiya, H. Bao, and T. Oki. Online inverse linear optimization: Efficient logarithmic-regret algorithm, robustness to suboptimality, and lower bound. In Advances in Neural Information Processing Systems, 2025.arxiv.org/abs/2501.14349
  23. [24]David B Yudin and Arkadi S Nemirovskii. Informational complexity and efficient methods for the solution of convex extremal problems. Matekon, 13(2):22–45, 1976.

Paper details

vlnc:W_9ems3ukt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents