Reproduce “Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade” 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
Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn
Researchers developed an online learning algorithm for profit maximization in repeated bilateral trade, achieving a nearly optimal "~O(sqrt(T))" regret against the best non-parametric, incentive-compatible mechanism in a stochastic setting. They also proved that sublinear regret is impossible in an adversarial environment and improved regret bounds for the joint ads problem to "~O(sqrt(T))".
Key insights
- Standard online learning techniques, such as fixed discretization or local search, are provably insufficient for achieving sublinear regret in this non-parametric bilateral trade problem.
- A bespoke chaining analysis, leveraging a "local dichotomy" to bound expected errors, is necessary and effective for tackling online learning problems with non-parametric, non-regular hypothesis classes.
- There is a fundamental separation in learnability: nearly optimal sublinear regret is achievable in the stochastic setting, but sublinear regret is impossible in the adversarial setting for this problem.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.