Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback
This work addresses the problem of learning to bid with dynamic values and aggregated feedback, which is relevant for online advertising and auction markets, and provides theoretical guarantees for a practical setting.
The paper studies a bidder with dynamic values in repeated second-price auctions with aggregated feedback, deriving regret bounds for learning methods that combine plug-in estimators with a differential-equation characterization of the optimal policy. The proposed algorithm achieves near-optimal regret of O(log N) for piecewise linear primitives and O(N^{1/3}) for general smooth primitives.
We study the problem of learning to bid when the bidder's value is dynamic, i.e., when the current value depends on past outcomes. Specifically, we consider a bidder participating in repeated second-price auctions whose value depends on the time elapsed since their last successful bid, with auctions arriving in continuous time and only aggregated feedback revealed at the end of the horizon. Such a bidder must (1) balance the immediate benefit of winning the current auction against its impact on future values and (2) learn unknown environmental parameters. We derive regret bounds for a class of learning methods that combine plug-in estimators with a differential-equation characterization of the optimal policy, and show that a specific confidence bound algorithm learns the optimal policy with a near optimal regret of $\widetilde{O}(\log N)$ for piecewise linear primitives, and $\widetilde{O}(N^{1/3})$ for general, smooth primitives, achieving these regrets without explicit randomization. These theoretical results are supported by numerical experiments.