Online linear programming: constraints arrive one at a time, and the algorithm must make irrevocable decisions about resource allocation before seeing future constraints. The competitive ratio depends on how much the algorithm knows about the distribution of incoming constraints. With full distributional knowledge, near-optimal solutions are standard. With no knowledge, the problem is impossible in the worst case.
Bray and Kolter work the single-sample regime: one sample from each round's constraint distribution, drawn before the round begins. This is the minimal information setting — less than a full distributional estimate, more than nothing. They achieve O((log n)²) regret. Polylogarithmic in the number of rounds, from a single sample.
The result is surprising because a single sample carries negligible information about the distribution's shape, tail behavior, or higher moments. It's a point estimate with no confidence interval. Yet the algorithm extracts enough structure from this one sample to make near-optimal allocation decisions over the entire sequence.
The mechanism: the single sample provides a noisy estimate of the constraint direction. The algorithm uses this to construct a hedge between the predicted direction and a conservative fallback. The polylogarithmic regret comes from the fact that the hedge only needs to be approximately correct — the LP structure ensures that small directional errors translate to small optimality gaps.
The setting is also nonstationary — the constraint distributions can change over time. The algorithm handles this through a doubling-trick that adapts the hedge to the current period's statistics, using the single sample as a detection mechanism for distributional shifts.
One sample per round. Polylogarithmic regret. The minimum amount of foresight, delivering near-optimal results.