Oracle-efficient Online Learning and Auction Design

DOI10.1145/3402203zbMATH Open1491.68093arXiv1611.01688OpenAlexW3090860245MaRDI QIDQ5066935FDOQ5066935

Authors:

Publication date: 31 March 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We consider the design of computationally efficient online learning algorithms in an adversarial setting in which the learner has access to an offline optimization oracle. We present an algorithm called Generalized Follow-the-Perturbed-Leader and provide conditions under which it is oracle-efficient while achieving vanishing regret. Our results make significant progress on an open problem raised by Hazan and Koren, who showed that oracle-efficient algorithms do not exist in general and asked whether one can identify properties under which oracle-efficient online learning may be possible. Our auction-design framework considers an auctioneer learning an optimal auction for a sequence of adversarially selected valuations with the goal of achieving revenue that is almost as good as the optimal auction in hindsight, among a class of auctions. We give oracle-efficient learning results for: (1) VCG auctions with bidder-specific reserves in single-parameter settings, (2) envy-free item pricing in multi-item auctions, and (3) s-level auctions of Morgenstern and Roughgarden for single-item settings. The last result leads to an approximation of the overall optimal Myerson auction when bidders' valuations are drawn according to a fast-mixing Markov process, extending prior work that only gave such guarantees for the i.i.d. setting. Finally, we derive various extensions, including: (1) oracle-efficient algorithms for the contextual learning setting in which the learner has access to side information (such as bidder demographics), (2) learning with approximate oracles such as those based on Maximal-in-Range algorithms, and (3) no-regret bidding in simultaneous auctions, resolving an open problem of Daskalakis and Syrgkanis.

Full work available at URL: https://arxiv.org/abs/1611.01688

Recommendations

• scientific article; zbMATH DE number 2079340
• Online learning in online auctions
• Multi-scale online learning: theory and applications to online auctions and pricing
• Oracle-based robust optimization via online learning
• Near-optimal online auctions
• Optimal design of online sequential buy-price auctions with consumer valuation learning
• A learning approach to auctions
• scientific article; zbMATH DE number 6381703
• Online learning and online convex optimization
• The computational power of optimization in online learning

zbMATH Keywords

online learningauction designfollow-the-perturbed-leaderoracle-efficiency

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Computational learning theory (68Q32) Auctions, bargaining, bidding and selling, and other market models (91B26) Rationality and learning in game theory (91A26)

Cited In (5)

• The computational power of optimization in online learning
• Efficient online linear optimization with approximation algorithms
• Multi-scale online learning: theory and applications to online auctions and pricing
• Learning in auctions: regret is hard, envy is easy
• Online learning for min-max discrete problems

This page was built for publication: Oracle-efficient Online Learning and Auction Design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066935)