Multi-scale Online Learning and its Applications to Online Auctions
We consider revenue maximization in online auction/pricing problems. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online posted pricing problem, we show regret bounds that scale with the best fixed price, rather than the range of the values. We also show regret bounds that are almost scale free, and match the offline sample complexity, when comparing to a benchmark that requires a lower bound on the market share. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their multi-scale versions. In this version, the reward of each action is in a different range, and the regret w.r.t. a given action scales with its own range, rather than the maximum range.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Real-Time Optimisation for Online Learning in Auctions
In display advertising, a small group of sellers and bidders face each other in up to 10 12 auctions a day. In this context, revenue maximisation via monopoly price learning is a high-value problem for sellers. By nature…
NMA: Neural Multi-slot Auctions with Externalities for Online Advertising
Online advertising driven by auctions brings billions of dollars in revenue for social networking services and e-commerce platforms. GSP auctions, which are simple and easy to understand for advertisers, have almost beco…
Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems
Matching problems have been widely studied in the research community, especially Ad-Auctions with many applications ranging from network design to advertising. Following the various advancements in machine learning, one …
Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets
In online ad markets, a rising number of advertisers are employing bidding agencies to participate in ad auctions. These agencies are specialized in designing online algorithms and bidding on behalf of their clients. Typ…
Bid Shading in The Brave New World of First-Price Auctions
Online auctions play a central role in online advertising, and are one of the main reasons for the industry's scalability and growth. With great changes in how auctions are being organized, such as changing the second- t…