Grigoris Velegkas

Grigoris Velegkas

Auto-generated profile, based on publicly available information

Grigoris Velegkas

Google Research, Mountain View, USA

Research Focus & Metrics

Representative Publications

View All Publications

13 May 2024
Verified
Conference Paper
Open access
YCYang Cai
Yang Cai
ZFZhe Feng
Zhe Feng
CLChristopher Liaw
Christopher Liaw
AMAranyak Mehta
Aranyak Mehta
GVGrigoris Velegkas
Grigoris Velegkas
We propose a new Markov Decision Process (MDP) model for ad auctions to capture the user response to the quality of ads, with the objective of maximizing the long-term discounted revenue. By incorporating user response, our model takes into consideration all three parties involved in the auction (advertiser, auctioneer, and user). The state of the user is modeled as a user-specific click-through rate (CTR) with the CTR changing in the next round according to the set of ads shown to the user in the current round. We characterize the optimal mechanism for this MDP as a Myerson's auction with a notion of modified virtual value, which relies on the value distribution of the advertiser, the current user state, and the future impact of showing the ad to the user. Leveraging this characterization, we design a sample-efficient and computationally-efficient algorithm which outputs an approximately optimal policy that requires only sample access to the true MDP and the value distributions of the bidders. Finally, we propose a simple mechanism built upon second price auctions with personalized reserve prices and show it can achieve a constant-factor approximation to the optimal long term discounted revenue.

9 June 2026
Verified
Conference Paper
Open access
SHSteve Hanneke
Steve Hanneke
AKAlkis Kalavasis
Alkis Kalavasis
SMShay Moran
Shay Moran
GVGrigoris Velegkas
Grigoris Velegkas
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, 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 we 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 its learning curve converges to zero for any arbitrary valuation distribution as the number of samples n → ∞. 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/√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. From a technical perspective, establishing lower bounds on learning curves is significantly more challenging than in the PAC framework, as it requires fixing a single hard distribution and proving a bound that holds for infinitely many values of n. Conversely, deriving upper bounds involves non-trivial algorithmic principles, including techniques such as regularization and structural risk minimization, which are crucial for achieving optimal learning rates.