On the Learning Curves of Revenue Maximization

• URL: http://arxiv.org/abs/2604.26922v1
• Date: Wed, 29 Apr 2026 17:38:25 GMT
• Title: On the Learning Curves of Revenue Maximization
• Abstract summary: A learning curve plots the decay of an algorithm's error for a fixed underlying distribution as a function of the number of training samples.<n>Prior work on revenue-maximizing learning algorithms adopts a distribution-free perspective, which parallels the PAC learning framework in learning theory.<n>We show that there exists a Bayes-consistent algorithm, meaning that its learning curve converges to zero for any arbitrary valuation distribution.
• Score: 62.087200798198786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning curves are a fundamental primitive in supervised learning, describing how an algorithm's performance improves with more data and providing a quantitative measure of its generalization ability. Formally, a learning curve plots the decay of an algorithm's error for a fixed underlying distribution as a function of the number of training samples. Prior work on revenue-maximizing learning algorithms, starting with the seminal work of Cole and Roughgarden [STOC, 2014], adopts a distribution-free perspective, which parallels the PAC learning framework in learning theory. This approach evaluates performance against the hardest possible sequence of valuation distributions, one for each sample size, effectively defining the upper envelope of learning curves over all possible distributions, thus leading to error bounds that do not capture the shape of the learning curves. In this work we initiate the study of learning curves for revenue maximization and provide a near-complete characterization of their rate of decay in the basic setting of a single item and a single buyer. In the absence of any restriction on the valuation distribution, we show that there exists a Bayes-consistent algorithm, meaning that its learning curve converges to zero for any arbitrary valuation distribution as the number of samples $n \to \infty$. However, this convergence must be arbitrarily slow, even if the optimal revenue is finite. In contrast, if the optimal revenue is achieved by a finite price, then the optimal rate of decay is roughly $1/\sqrt{n}$. Finally, for distributions supported on discrete sets of values, we show that learning curves decay almost exponentially fast, a rate unattainable under the PAC framework.

Related papers

• Successive Halving with Learning Curve Prediction via Latent Kronecker Gaussian Processes [7.6801618830697285]
  We investigate whether guiding Successive Halving with learning curve predictions based on Latent Kronecker Gaussian Processes can overcome limitations.<n>We compare this predictive approach to the standard approach based on current performance values.<n>Our experiments show that, although the predictive approach achieves competitive performance, it is not optimal compared to investing more resources into the standard approach.
  arXiv  Detail & Related papers  (2025-08-20T16:10:23Z)
• Faster Diffusion Models via Higher-Order Approximation [28.824924809206255]
  We propose a principled, training-free sampling algorithm that requires only the order of $$ d1+2/K varepsilon-1/K $$ score function evaluations.<n>Our theory is robust vis-a-vis inexact score estimation, degrading gracefully as the score estimation error increases.<n>More broadly, our work develops a theoretical framework towards understanding the efficacy of high-order methods for accelerated sampling.
  arXiv  Detail & Related papers  (2025-06-30T16:49:03Z)
• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  Reinforcement learning with outcome-based feedback faces a fundamental challenge.<n>How do we assign credit to the right actions?<n>This paper provides the first comprehensive analysis of this problem in online RL with general function approximation.
  arXiv  Detail & Related papers  (2025-05-26T17:44:08Z)
• Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation [8.378137704007038]
  We present a regret analysis of distributional reinforcement learning with general value function approximation in a finite episodic Markov decision process setting.<n>We propose a provably efficient algorithm, $textttSF-LSVI$, that achieves a tight regret bound of $tildeO(d_E Hfrac32sqrtK)$ where $H$ is the horizon, $K$ is the number of episodes, and $d_E$ is the eluder dimension of a function class.
  arXiv  Detail & Related papers  (2024-07-31T00:43:51Z)
• Rejection via Learning Density Ratios [50.91522897152437]
  Classification with rejection emerges as a learning paradigm which allows models to abstain from making predictions.<n>We propose a different distributional perspective, where we seek to find an idealized data distribution which maximizes a pretrained model's performance.<n>Our framework is tested empirically over clean and noisy datasets.
  arXiv  Detail & Related papers  (2024-05-29T01:32:17Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time [45.72323731094864]
  In this paper, we study the optimality gap between two-layer ReLULU networks regularized with weight decay and their convex relaxations. Our study sheds new light on understanding why local methods work well.
  arXiv  Detail & Related papers  (2024-02-06T01:29:35Z)
• Towards Understanding and Improving GFlowNet Training [71.85707593318297]
  We introduce an efficient evaluation strategy to compare the learned sampling distribution to the target reward distribution. We propose prioritized replay training of high-reward $x$, relative edge flow policy parametrization, and a novel guided trajectory balance objective.
  arXiv  Detail & Related papers  (2023-05-11T22:50:41Z)
• Fine-Grained Distribution-Dependent Learning Curves [27.09513298165498]
  Learning curves plot the expected error of a learning algorithm as a function of the number of labeled input samples. In this paper we introduce a new dimension characterization called the grained PAC that improves and refines the recent results of Bousquet et al. Our characterization sheds new light on the structure of learning curves by providing fine-grained bounds.
  arXiv  Detail & Related papers  (2022-08-31T03:29:21Z)
• A Theory of Universal Learning [26.51949485387526]
  We show that there are only three possible rates of universal learning. We show that the learning curves of any given concept class decay either at an exponential, or arbitrarily slow rates.
  arXiv  Detail & Related papers  (2020-11-09T15:10:32Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.