A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage

We study a contextual version of the repeated brokerage problem. In each interaction, two traders with private valuations for an item seek to buy or sell based on the learner's—a broker—proposed price, which is informed by some contextual information.The broker's goal is to maximize the traders' net utility—also known as the gain from trade—by minimizing regret compared to an oracle with perfect knowledge of traders' valuation distributions.We assume that traders' valuations are zero-mean perturbations of the unknown item's current market value—which can change arbitrarily from one interaction to the next—and that similar contexts will correspond to similar market prices.We analyze two feedback settings: full-feedback, where after each interaction the traders' valuations are revealed to the broker, and limited-feedback, where only transaction attempts are revealed.For both feedback types, we propose algorithms achieving tight regret bounds.We further strengthen our performance guarantees by providing a tight $1/2$-approximation result showing that the oracle that knows the traders' valuation distributions achieves at least $1/2$ of the gain from trade of the omniscient oracle that knows in advance the actual realized traders' valuations.