On the Learning Curves of Revenue Maximization

A team of researchers—Steve Hanneke, Alkis Kalavasis, Shay Moran, and Grigoris Velegkas—has published a paper titled "On the Learning Curves of Revenue Maximization," which will appear at STOC 2026. The work fundamentally rethinks how revenue-maximizing algorithms improve with more data, moving beyond the traditional PAC (Probably Approximately Correct) framework that only considers worst-case performance. Instead, the authors analyze learning curves—plots of error decay as a function of training samples—for the specific task of setting prices to maximize revenue from a single buyer and a single item.

The paper delivers a near-complete characterization of these learning curves under different conditions. In the most general scenario, with no restrictions on the buyer's valuation distribution, the authors prove that a Bayes-consistent algorithm exists that eventually converges to zero error, but the convergence can be arbitrarily slow—even when the optimal revenue is finite. This highlights a fundamental limitation: without assumptions, you cannot guarantee fast learning. In contrast, if the optimal revenue is achieved by a finite price, the optimal rate of decay is roughly 1/√n. For distributions supported on discrete sets of values, the learning curve decays almost exponentially fast—a rate that is unattainable under the standard PAC framework. These results provide practical guidance for designing pricing algorithms that learn efficiently from data.