📊 statistics

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

This paper addresses the challenge of learning to bid in repeated second-price auctions with dynamic values dependent on past outcomes and aggregated feedback, proposing a confidence-bound algorithm that achieves near-optimal regret bounds of $\widetilde{O}(\log N)$ and $\widetilde{O}(N^{1/3})$ for piecewise linear and general smooth primitives, respectively, without requiring explicit randomization.

Original authors: Benjamin Heymann, Otmane Sakhi

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin Heymann, Otmane Sakhi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a lemonade stand in a busy town square. Every few minutes, a new customer walks by, and you have to decide how much to charge for a cup. This is a second-price auction: if you win the sale, you don't pay your asking price; you pay whatever the second highest bidder was willing to pay.

Usually, in economics, you'd just charge your "true value" (how much the lemonade is worth to you). But this paper introduces a twist: your value changes based on your recent history.

The "Lemonade Fatigue" Problem

In this story, if you sell a cup of lemonade to a customer, that customer gets "full" or "tired" of lemonade for a while. If you try to sell them another cup five minutes later, it's worth almost nothing to them. They need time to recover their thirst.

This is what the paper calls Dynamic Values.

The Dilemma: If you sell a cup now, you get money immediately, but you might ruin the chance to sell a more valuable cup to that same customer later.
The Trap: If you just bid your "true value" every time (like in a standard auction), you will lose money in the long run because you are selling too often, devaluing your own product. You need a strategy that says, "I'll skip this sale to save the customer for a better moment later."

The Challenge: You Don't Know the Rules

The problem gets harder because you don't know two crucial things:

How fast customers recover: You don't know exactly how long it takes for a customer to get thirsty again (the paper calls this function $k$ ).
How competitive the market is: You don't know how much other lemonade stands are willing to bid (the paper calls this function $q$ ).

You have to learn these rules while you are playing the game, all while trying to make as much money as possible.

The Solution: A Smart, Self-Correcting Guide

The authors propose a way to learn these rules and find the perfect bidding strategy without needing a crystal ball. They use a mix of guessing and mathematical planning.

Think of their method like a GPS for your lemonade stand:

The Map (The Solver): They use a complex mathematical formula (a differential equation) that acts like a map. It tells you the perfect bid if you knew all the rules.
The Compass (The Estimators): Since you don't know the rules, you use your past sales data to build a rough map.
- You look at how much money you made after different time gaps to guess how fast customers recover.
- You look at the prices you paid when you won to guess how competitive the other stands are.
The Feedback Loop: You plug your "rough map" into the "perfect strategy" calculator. This gives you a new bidding plan. You try it, collect more data, update your map, and try again.

The Four Strategies Tested

The paper tests four different ways to do this learning:

The "Just Keep Going" Approach: You just keep updating your map and bidding based on it. The paper proves that if you keep doing this long enough, you will eventually figure out the perfect strategy, even without trying to "explore" randomly. It's like walking down a hallway; eventually, you hit the right door.
The "Explore then Commit" Approach: You spend a little time bidding very high (just to learn the rules quickly), then you switch to your best guess for the rest of the day. This is fast and efficient.
The "Confidence Bound" Approach (The Winner): This is the most sophisticated method. It creates a "safety zone" around your guesses.
- If you aren't sure about the rules, it acts a bit more aggressively to learn more.
- If you are confident, it acts conservatively to protect your profits.
- The Result: This method learns the optimal strategy incredibly fast. The paper proves it makes very few mistakes compared to the perfect strategy, growing only logarithmically (very slowly) as time goes on. It achieves this without needing to randomly throw darts (randomization) to learn, which is a big deal in this field.

Why This Matters

The paper shows that even when your value changes based on your past actions (like ad fatigue in digital marketing), you can still learn to bid perfectly.

The Big Takeaway: You don't need to know the future or the competition perfectly. By using a smart combination of estimating the rules from data and solving a planning equation, you can learn to bid in a way that maximizes your long-term profit, even in a complex, changing environment.

In short: Don't just bid your heart out. Bid smartly, learn from your wins and losses, and let the math tell you when to stop and wait for the next opportunity.

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

1. Problem Formulation

This work addresses the problem of learning optimal bidding strategies in repeated second-price auctions where the bidder's value is dynamic. Unlike static models where a bidder's valuation is independent of past actions, here the value of winning an auction depends on the time elapsed since the bidder's last successful win. Specifically, the value function $k(\tau)$ is a concave, increasing function of the time $\tau$ since the last win, reflecting phenomena such as user ad fatigue in digital advertising.

The setting involves:

Continuous Time: Auctions arrive according to a Poisson process with intensity $\mu$ .
Dynamic Values: The reward for winning at time $t$ is $k(t - T_{last})$ , where $T_{last}$ is the time of the previous win.
Stationary Competition: Competitors' bids (price-to-beat) are drawn i.i.d. from an unknown continuous cumulative distribution function (CDF) $q$ .
Aggregated Feedback: The bidder does not observe individual auction outcomes or prices immediately. Instead, feedback is revealed only at the end of an "episode" (a sequence of auctions ending at a random time drawn from an exponential distribution with rate $\gamma$ ). The feedback consists of the total value generated by the episode.
Learning Objective: The bidder must learn the unknown primitives $k$ (value dynamics) and $q$ (competition distribution) to maximize cumulative expected payoff over $N$ episodes, minimizing regret defined as $Regret(N) = \sum_{l=1}^N (V_{\pi^*}(0) - V_{\pi_l}(0))$ .

2. Methodology and Theoretical Framework

2.1 Optimal Control Characterization

Building on the continuous-time dynamic programming formulation from [6], the authors characterize the optimal policy $\pi^*$ via the Bellman value function $V^*(\tau)$ . The optimal bid satisfies a differential equation derived from the Bellman value:
$\dot{\pi}(t) = \dot{k}(t) - \gamma(V^*(0) + k(t)) + \mu f(\pi(t)) + \gamma \pi(t)$
where $f(v) = q(v)v - p(v)$ and $p(v)$ is the expected price paid. The solution requires finding a specific initial condition $V^*(0)$ such that the resulting trajectory remains bounded, a problem solved via a bisection method (the "solver" $S$ ).

2.2 Learning Primitives via Plug-in Estimators

Since $k$ and $q$ are unknown, the authors propose learning them from data and plugging the estimates into the solver $S$ .

Estimating $k$ : Modeled as a piecewise linear, concave, increasing function. Estimation is performed via Projected Ordinary Least Squares (OLS) on aggregated episode data, projecting the unconstrained estimator onto the convex set of concave functions.
Estimating $q$ : Modeled as a piecewise linear, increasing CDF. Estimation uses Maximum Likelihood Estimation (MLE) on win/loss outcomes and observed prices (when wins occur).

2.3 Extension Invariance Theorem

A core theoretical contribution is the Extension Invariance Theorem (Theorem 4.1). It establishes that to identify the optimal policy, one does not need to learn the entire distribution $q$ . It is sufficient to estimate $q$ accurately only up to the maximal optimal bid $\beta(\pi^*)$ . This insight decouples the need for full exploration of the bid space from the requirement to learn the optimal policy, provided the learning algorithm ensures bids cover the relevant region.

3. Algorithms and Regret Bounds

The paper analyzes four algorithms based on plug-in estimators:

Asymptotic Convergence (Iterative Plug-in): An iterative approach where data is collected, estimators are updated, and the policy is re-computed. Theorem 5.1 proves that if the policy sequence explores a region where $q$ is identifiable (i.e., $\limsup \beta(\pi_n) > 0$ ), the policy converges to the optimal one asymptotically. However, this does not guarantee finite-time regret bounds.
Two-Phase and Three-Phase Algorithms: These follow an "Explore-Then-Commit" structure.
- Two-Phase: A fixed exploratory policy (bidding the maximal value) runs for $N_1$ episodes to learn both $k$ and $q$ , followed by exploitation.
- Three-Phase: Separates the learning of $k$ and $q$ . First, a fixed policy learns $k$ ; then, the learned $k$ guides a policy to learn $q$ ; finally, exploitation occurs.
- Result: Both achieve sub-linear regret of $O(\sqrt{N})$ (Theorems 5.4 and 5.5).
Confidence Bounds Algorithm (Online Learning): An online algorithm inspired by Upper Confidence Bound (UCB) principles.
- It constructs optimistic estimates for $k$ (UCB) and pessimistic estimates for $q$ (Lower Confidence Bound, LCB) to balance exploration and exploitation.
- Crucially, it achieves near-logarithmic regret $\tilde{O}(\log N)$ for piecewise linear primitives (Theorem 5.7) without requiring explicit randomization, which is typically necessary in first-price auctions.
- The algorithm is shown to be near-minimax optimal, as a lower bound of $\Omega(\log N)$ is derived (Theorem 5.8), matching the static case complexity despite the dynamic setting.
General Smooth Primitives: The results are extended to general smooth primitives (continuously differentiable with Lipschitz derivatives) by approximating them with piecewise linear functions. This yields a regret bound of $\tilde{O}(N^{1/3})$ (Theorem 5.10).

4. Key Contributions

First Regret Analysis for Dynamic Values: This is the first work to provide regret bounds for learning to bid in repeated second-price auctions where values depend on the time since the last win, a setting distinct from standard static or budget-constrained models.
Extension Invariance: The proof that accurate estimation of the competition distribution is only required up to the optimal bid threshold, simplifying the learning requirement.
Optimal Regret Rates: Demonstration that near-logarithmic regret is achievable in this complex, dynamic setting without explicit randomization, matching the theoretical lower bound of the static case.
Integration of Control and Learning: The work bridges continuous-time optimal control (via ODE characterization of the optimal policy) and model-based reinforcement learning (via plug-in estimation), offering a framework for problems with state resets.

5. Significance and Claims

The authors claim that this study offers a theoretically sound approach to auto-bidding in environments with dynamic values, such as digital advertising where ad fatigue is prevalent. The significance lies in:

Practical Relevance: It addresses the "planning problem" where immediate gains must be balanced against future value degradation, a challenge that simple feature engineering or supervised learning cannot solve optimally.
Theoretical Insight: It demonstrates that even with aggregated feedback and dynamic values, the problem does not become intractably harder than the static case in terms of regret rates (logarithmic vs. square root), provided the right estimation and control tools are used.
Broader Impact: The framework offers insights for the broader reinforcement learning literature, particularly for continuous-time control problems involving resets and non-linear rewards.

The paper concludes that while the analysis is theoretical, the combination of plug-in estimation with differential-equation-based solvers suggests a viable path for practical applications in real-world auction systems. Numerical experiments support the theoretical findings, showing the confidence bounds algorithm outperforming explore-then-commit strategies in terms of regret growth.