Improved learning strategy matches best possible regret rates
Optimal No-Regret Learning for Repeated Prophet Inequality
Machine Learning
Summary
This paper looks at a situation where someone must make a single choice from a sequence of unknown options one after another, but only sees values up to the point they stop. The authors develop a strategy to learn the best way to make these choices over many rounds, doing almost as well as if they knew all the chances ahead of time. They create an efficient method that learns quickly without needing to try every option too often. Their approach answers a question from recent research about how to do this learning well when there are many options.
What this means in practice
- •For online auction platforms: Improve automated bidding strategies to better decide when to accept offers under uncertain item values.
- •For supply chain managers: Enhance sequential acceptance decisions for sourcing with unknown supplier quality distributions revealed only upon inspection.
A theory result. No direct application yet.
Authors
Kun Wang
Abstract
We study repeated prophet inequalities under prefix feedback. In each of $T$ rounds, a learner encounters fresh values drawn independently from $n$ boxes with unknown $[0,1]$-supported distributions in a fixed order and must irrevocably accept one, observing only the prefix up to its stopping box. Regret is measured against the optimal stopping policy that knows the distributions. We give an efficient algorithm achieving $\widetilde O(\sqrt{T})$ expected regret, matching the lower bound up to logarithmic factors. Our algorithm explores directly through near-optimal policies, combining empirical backward induction with box-specific reach bonuses. A relative-drop aggregation rule then exploits the nesting structure of observed prefixes to preserve exploration, thereby removing the polynomial dependence on the box number $n$. This resolves an open question posed by Liu et al. (2025).