Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback

• URL: http://arxiv.org/abs/2605.28133v1
• Date: Wed, 27 May 2026 08:20:08 GMT
• Title: Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback
• Abstract summary: 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.<n>We derive regret bounds for a class of learning methods that combine plug-in estimators with a differential-equation characterization of the optimal policy.
• Score: 5.65780894346598
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  We consider the problem of learning an unknown subset $N_texttarget$ of a domain in an online setting.<n>This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback.<n>We show that a hypothesis class is learnable in this setting if and only if it has finite Vapnik-Chervonenkis dimension.
  arXiv  Detail & Related papers  (2026-05-10T14:28:05Z)
• Log-Sum-Exponential Estimator for Off-Policy Evaluation and Learning [50.93804891554481]
  We introduce a novel estimator based on the log-sum-exponential (LSE) operator, which outperforms traditional inverse propensity score estimators.<n>Our LSE estimator demonstrates variance reduction and robustness under heavy-tailed conditions.<n>In the off-policy learning scenario, we establish bounds on the regret -- the performance gap between our LSE estimator and the optimal policy.
  arXiv  Detail & Related papers  (2025-06-07T17:37:10Z)
• Online Bidding under RoS Constraints without Knowing the Value [22.193658401789033]
  We consider the problem of bidding in online advertising, where an advertiser aims to maximize value while adhering to budget and Return-on-Spend constraints.<n>We propose a novel Upper Confidence Bound (UCB)-style algorithm that carefully manages this trade-off.
  arXiv  Detail & Related papers  (2025-03-05T05:25:54Z)
• Joint Value Estimation and Bidding in Repeated First-Price Auctions [31.17583484579669]
  We study regret in repeated first-price auctions, where a bidder observes only the realized outcome after each auction -- win or loss.<n>We propose algorithms that jointly estimate private values and optimize bidding strategies, achieving near-optimal regret bounds.
  arXiv  Detail & Related papers  (2025-02-24T16:21:50Z)
• Learning to Bid in Non-Stationary Repeated First-Price Auctions [27.743710782882136]
  First-price auctions have gained significant traction in digital advertising markets.<n> determining an optimal bidding strategy in first-price auctions is more complex.<n>We provide a minimax-optimal characterization of the dynamic regret for the class of sequences of opponents' highest bids.
  arXiv  Detail & Related papers  (2025-01-23T03:53:27Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  We study a game between autobidding algorithms that compete in an online advertising platform.<n>We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret.
  arXiv  Detail & Related papers  (2023-01-30T21:59:30Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  We study reinforcement learning with linear function approximation and adversarially changing cost functions. We present a computationally efficient policy optimization algorithm for the challenging general setting of unknown dynamics and bandit feedback.
  arXiv  Detail & Related papers  (2023-01-30T17:26:39Z)
• A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design [158.0041488194202]
  We study reserve price optimization in multi-phase second price auctions. From the seller's perspective, we need to efficiently explore the environment in the presence of potentially nontruthful bidders. Third, the seller's per-step revenue is unknown, nonlinear, and cannot even be directly observed from the environment.
  arXiv  Detail & Related papers  (2022-10-19T03:49:05Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  Intrinsic rewards play a central role in handling the exploration-exploitation trade-off. We introduce emphanti-concentrated confidence bounds for efficiently approximating the elliptical bonus. We develop a practical variant for deep reinforcement learning that is competitive with contemporary intrinsic rewards on Atari benchmarks.
  arXiv  Detail & Related papers  (2021-10-21T15:25:15Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising. We show how to achieve significantly lower regret when the opponents' maximal bid distribution is known. Our algorithms converge much faster than alternatives proposed in the literature for various bid distributions.
  arXiv  Detail & Related papers  (2021-07-05T07:48:52Z)
• Optimal No-regret Learning in Repeated First-price Auctions [38.908235632001116]
  We study online learning in repeated first-price auctions. We develop the first learning algorithm that achieves a near-optimal $widetildeO(sqrtT)$ regret bound.
  arXiv  Detail & Related papers  (2020-03-22T03:32:09Z)

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.