Reproduce “Contextual Search and Bilateral Trade with a Trace-Square-Root Potential” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo

The authors develop one-bit learning methods that track uncertainty through a potential whose expected decrease pays for information from feedback. In contextual search, their adversarial method guarantees expected cumulative absolute error at most 12√d, against a matching √d lower bound, for every horizon. For bilateral trade, they prove an existence-based 2¹²√d+1 regret bound, not an efficient implementation. Both guarantees assume unit-ball targets and contexts.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.