A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage

François Bachoc, Tommaso Cesari, Roberto Colomboni
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:2836-2844, 2025.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-bachoc25a, title = {A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage}, author = {Bachoc, Fran{\c{c}}ois and Cesari, Tommaso and Colomboni, Roberto}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {2836--2844}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/bachoc25a/bachoc25a.pdf}, url = {https://proceedings.mlr.press/v258/bachoc25a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage %A François Bachoc %A Tommaso Cesari %A Roberto Colomboni %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-bachoc25a %I PMLR %P 2836--2844 %U https://proceedings.mlr.press/v258/bachoc25a.html %V 258 %X 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.
APA
Bachoc, F., Cesari, T. & Colomboni, R.. (2025). A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:2836-2844 Available from https://proceedings.mlr.press/v258/bachoc25a.html.

Related Material