Greedy beats Nature: New paper proves optimal decisions under complete uncertainty
Even with zero information about probabilities, picking the best-so-far option is provably optimal.
A new paper proposes a game-theoretic model to study the worst-case regret of the greedy strategy under complete (Knightian) uncertainty. For arbitrary numbers of products and ratings, the authors establish matching upper and lower bounds on worst-case regret when every product has the same number of observations: regret vanishes as observations increase, and the greedy strategy is rate-optimal up to universal constants. In the special case of two products and two ratings, with one observation per product, the greedy strategy is minimax-optimal. When products have different numbers of observations, greedy remains robust in a conservative sense—its worst-case regret is controlled by the least-reviewed product—but adding observations for only one product can actually increase that regret. The model is tested on data collected from Google reviews for restaurants, and the greedy strategy's empirical performance closely aligns with the theoretical findings.
- Greedy strategy (pick highest average rating) is minimax-optimal for worst-case regret under complete (Knightian) uncertainty.
- Worst-case regret vanishes at rate Θ(1/√n) as observations increase, matching the optimal theoretical bound.
- Adding observations to one product can increase greedy's worst-case regret—a counterintuitive result confirmed in Google reviews data.
Why It Matters
Proves that simple 'best-so-far' heuristics are theoretically sound, even against adversarial environments—useful for recommendation systems and automated decisions.