One bit of feedback now matches the lower bound: a trace-square-root potential gives tight regret for contextual search and bilateral trade

Contextual search and contextual bilateral trade now achieve regret within a constant factor of the known lower bounds when the learner sees only one bit of feedback, and the bounds do not grow with the horizon. Both problems previously left a visible gap between upper and lower bounds, the gap was especially large for bilateral trade, and only one upper bound existed for the one-bit feedback model. Both problems are analyzed with the hidden vectors chosen adversarially from the Euclidean unit ball, and the expected-loss bounds match existing lower bounds up to a constant factor.

The algorithms drop explicit feasible sets and instead track a mean proxy and a square-root covariance proxy for uncertainty, pricing along the standard deviation in the context direction. Earlier approaches maintained a feasible polytope through cutting planes and needed geometric routines such as intrinsic volumes or barycenters of high-dimensional convex bodies. The adversarial contextual search algorithm uses few arithmetic operations per round and quadratic-order memory, while bilateral trade uses a one-round minimax argument to guarantee a finite lottery of prices valid for every hidden buyer-seller pair.

The Bayesian versions give bounds that depend only on the prior covariance matrices and hold at every horizon. This viewpoint departs from the existing literature but yields simpler algorithms and supplies the first potential used in the adversarial analysis. The bounds are set by the covariance matrix of the target prior and by the two covariance matrices of the seller's and buyer's valuations, allowing unbounded support or skewed covariance.

The scope is the adversarial setting where the hidden target or the seller and buyer valuations are chosen from the Euclidean unit ball, together with the Bayesian setting with finite second moments; both guarantees hold for every horizon.

The adversarial bilateral trade algorithm only proves that a finite lottery of prices satisfying the one-round bound exists, and the material explicitly does not claim an efficient implementation of the optimization in step 2; the Bayesian bounds assume a known prior and allow unbounded support or skewed covariance.