No-regret Learning in Repeated First-Price Auctions with Budget Constraints

There is a flourishing source of literature on bidding strategies in repeated auctions with budgets. Through the lens of online learning, Balseiro and Gur (2019) identify asymptotically optimal online bidding strategies known as pacing (a.k.a. bid-shading in literature) in repeated second-price auctions with budgets. Inspired by the pacing strategy, Flajolet and Jaillet (2017) develop no-regret non-anticipating algorithms for learning with contextual information in repeated second-price auctions. Another line of works that uses similar techniques in the present paper includes Amin et al. (2012); Tran-Thanh et al. (2014); Gummadi et al. (2012). Gummadi et al. (2012) and Amin et al. (2012) study bidding strategies in repeated second-price auctions with budget constraints, but the former does not involve any learning and the latter does not provide any regret analysis (their estimator is biased). Tran-Thanh et al. (2014) derive regret bounds for the same scenario but the optimization objective is the number of items won instead of value or surplus. Baltaoglu et al. (2017) also use dynamic programming to tackle repeated second-price auctions with budgets. However, they assume per-round budget constraints and their dynamic programming algorithm is for allocating bids among multiple items. Again, we emphasize that no prior work has been done in repeated first-price auctions with budgets, since the structure of the problem (compared to second-price variants) is fundamentally different (recall Example 1.1).

Two notable works concerning repeated first-price auctions are Han et al. (2020b) and Han et al. (2020a). In Han et al. (2020b), they introduce a new problem called monotone group contextual bandits and then obtain an $O(\sqrt{T}\ln^{2}T)$-regret algorithm for repeated first-price auctions without budget constraints under stationary settings. In Han et al. (2020a), they concentrate on an adversarial setting and develop a mini-max optimal online bidding algorithm with $O(\sqrt{T}\ln T)$ regret against all Lipschitz bidding strategies. A crucial difference is that in the present paper, budgets are involved thus the bandit algorithm by Han et al. (2020b) is not suitable for our needs.

From the bandit side, Badanidiyuru et al. (2013) develop bandit algorithms under resource constraints. They show that their algorithm can be used in dynamic procurement, dynamic posted pricing with limited supply, etc. However, since the bidder observes her value before bidding in our problem, results by Badanidiyuru et al. (2013) cannot be directly applied to our setting. Our setting also relates to contextual bandit problems with resource constraints (Badanidiyuru et al., 2014; Agrawal and Devanur, 2016; Agrawal et al., 2016). Nevertheless, applying this contextual bandit approach requires discretizing the action space, which needs Lipschitz continuity of distributions. Our approach does not rely on any continuity assumption. Further, the performance guarantee (typically $\widetilde{O}(T^{\frac{2}{3}})$) is worse than ours. It also does not fit into our information structure when the feedback is censored.

The establishment of the regret bounds will be given in two steps. First, we will show that the buyer’s estimation $V_{\hat{F}}$ is approximately accurate with a sufficient number of samples. This relies on the estimation of $F$. Concentration inequalities are thus intrinsic to our analysis. Second, we bridge the regret defined in Equation 1 with $V$ and $V_{\hat{F}}$. This is done by a series of auxiliary quantities measuring the regret. We obtain the desired result by combining the two steps.

We first present the following lemma (Dvoretzky et al., 1956; Massart, 1990), which states a uniform convergence result for the estimation of cumulative distribution functions.

With Lemma 3.1 in hand, given any $T$, we show a bound for the difference between $V(B_{t},t)$ and $V_{\hat{F}}(B_{t},t)$ for any $1\leq t\leq T$ (recall that $V(B_{t},t)$ is the accumulated utility of the optimal strategy with the knowledge of $F$). We prove this using induction. Note that the induction basis is a little tricky due to the base case of recursion in Algorithm 1. Therefore, in the following lemma, we first deal with the induction step.

Note that the lemma above assumes that $\sup_{B_{t_{0}}}|V(B_{t_{0}},t_{0})-V_{\hat{F}}(B_{t_{0}},t_{0})|$ is bounded above by $\sqrt{\frac{1}{2}\ln\frac{2T}{\delta}}\frac{1+\lambda}{(1-\lambda)^{2}}t^{-\frac{1}{2}}$, which holds if the base case $V_{\hat{F}}(B_{t_{0}},t_{0})$ is set accurately (i.e. $V(B_{t_{0}},t_{0})=V_{\hat{F}}(B_{t_{0}},t_{0})$). We use $\widetilde{V}_{\hat{F}}(B_{t},t)$ to denote the estimated value function using $\hat{F}$ if the base is indeed accurate. In the following lemma, we show that using the alternative initialization method specified in 5 of Algorithm 1, $\sup_{B_{t}}|V_{\hat{F}}(B_{t},t)-\widetilde{V}_{\hat{F}}(B_{t},t)|$ actually satisfies the condition of Lemma 3.2.

Synthesizing Lemma 3.2 and Lemma 3.3, we have $|V(B_{t},t)-V_{\hat{F}}(B_{t},t)|\leq(C+C_{1})t^{\frac{1}{2}}$. A crucial next step is to relate this bound to the final regret. This is achieved by two transformations. Roughly speaking, the buyer’s “regret” can be viewed in two parts: 1) she does not bid according to the optimal strategy; 2) her strategy is not optimally spending the budget which leads to future losses. These two transformations are done with this intuitive observation and summarized in the following lemma that bounds the performance of the buyer’s strategy. Below we first condition on the good event that the estimation succeeds for every $t$. Then we add the contribution of the bad event to the regret in Theorem 3.5.

By Lemma 3.4 and further transformations, we can now establish the regret bound of Algorithm 1.

Note that the regret bound is meaningful only if $B=\omega(T^{\frac{1}{2}})$. Let us now take the budget $B$ to scale linearly with $T$ as in Balseiro and Gur (2019); Flajolet and Jaillet (2017). Specifically, assume that $T<+\infty$ and there exists a constant $\beta$ such that the budget $B=\beta T$, then we establish that the regret is $\widetilde{O}(\sqrt{T})$ in this special case. Indeed, under this condition, we can simply set $t_{0}=T+1$ and $V_{\hat{F}}(B_{T+1},T+1)=0$ for any $B_{T+1}$ in Algorithm 1. Therefore, $C_{1}=0$ and the worst-case regret is bounded by $\left(4\sqrt{\frac{1}{2}\ln 2T^{2}}\frac{1+\lambda}{(1-\lambda)^{2}}+1-\lambda\right)\sqrt{T}+\frac{\lambda}{2}\log_{\frac{1}{\lambda}}\frac{T}{(1-\lambda)^{2}}+1$.

Next we deal with the case where $G$ is also initially unknown. Based on Algorithm 1, we additionally maintain an estimation $\hat{G}$ of $G$ based on past observations of valuations. $\hat{G}$ is initialized to be a uniform distribution and will be used to solve the dynamic programming problem (see 7 of Algorithm 2). Using similar techniques as before (with more work), we obtain the following theorem.

We now present the procedure for estimating $F$ under censored feedback. It suffices to estimate the distribution function of $1-m_{t}$ which is right-censored by $1-b_{t}$. Let $y_{t}=\min\{1-m_{t},1-b_{t}\},r_{t}=\mathbf{1}_{\{m_{t}\geq b_{t}\}}$. The observations can now be described as $(y_{t},r_{t},\bm{h}_{t})_{t=1}^{T}$.

Roughly speaking, to decouple the dependency between $m_{t},b_{t}$, we use the fact that $b_{t}$ and $m_{t}$ are independent conditioning on $\bm{h}_{t}$. Intuitively, the history $\bm{h}_{t}$ provides information for getting enough effective samples for $m_{t}$. Next we establish models to estimate the hazard rate functions⁴⁴4The hazard rate function of a random variable $X$ with p.d.f. $f$ and c.d.f. $F$ is $H_{X}(x)=\frac{f(x)}{1-F(x)}$. of $1-m_{t},1-b_{t}$ using $\bm{h}_{t}$. With the hazard rate functions, we use the maximum likelihood method with a kernel to compute the final estimation $\hat{F}_{t}$ and obtain Equation 3.

Details follow. We initialize with a sequence (bandwidth) $(a_{t})_{t=1}^{T}$ such that $\frac{\log^{2}a_{t}}{ta_{t}^{2}}\to 0,ta_{t}^{2}\to\infty,ta_{t}^{4}\to 0$ as $t\to+\infty$ and a symmetric kernel function $K(\cdot,\cdot)\in C^{2}(\mathbb{R}^{2})$ with bounded gradient. Now, at each time $t$, we compute two vectors $\bm{\beta}_{t},\bm{\gamma}_{t}$ which maximize each of the followings

We arbitrarily pad $\bm{h}_{1},\dotsc,\bm{h}_{t}$ with zeros to make their length the same (we will show that this is without loss of generality in a moment). Compute $\bm{Z}_{t}=(\bm{\beta}_{t}^{\top}\bm{h}_{t},\bm{\gamma}_{t}^{\top}\bm{h}_{t})^{\top}$. The survival function of $1-m_{t}$, or equivalently the cumulative distribution function of $m_{t}$, is estimated based on Zeng (2004)’s estimator

Now, we are ready to apply the estimator and the algorithm for censored feedback is depicted in Algorithm 2. Note that the new estimator’s convergence rate is slower than that for the full-feedback case. Therefore, compared to Algorithm 1, Algorithm 2 is now a multi-phase algorithm. The algorithm only updates the estimation of $\hat{F}$ at the end of each phase (see Figure 1 for an illustration). The other elements of each phase in Algorithm 2 are similar to Algorithm 1.

To analyze the performance of Algorithm 2, we will prove a series of lemmas on the estimation error of Equation 3. In particular, our proof relies on the following convergence result.

Before we proceed to apply the lemma, we verify a series of prerequisites mentioned in Zeng (2004) to make sure it holds. First, we make sure that conditioning on $\bm{h}_{t}$, the random variables $1-m_{t}$ and $1-b_{t}$ are independent. Indeed, $b_{t}$ is completely decided by $\bm{h}_{t}$ and $m_{t}$ is independent of $\bm{h}_{t}$. Second, we note that the maximizer shown in Equation 2 is essentially doing Cox’s proportional hazards regression analysis. To establish consistency of the estimator, we show that at least one of $\widetilde{m}_{t}\coloneqq 1-m_{t}$ and $1-b_{t}$ follows Cox’s proportional model. That is to say, there exists $\bm{\beta}$ and a function $f(y)$ such that the hazard rate function of $\widetilde{m}_{t}$ or $1-b_{t}$ conditioning on $\bm{h}_{t}$ exactly follows

Equation 4 holds for $\widetilde{m}_{t}$. In fact, taking $\bm{\beta}=\mathbf{0}$ and $f(y)=\frac{F^{\prime}(1-y)}{1-F(1-y)}$ suffices. Since we take $\bm{\beta}=\mathbf{0}$, consistency establishes regardless of the way we pad $\bm{h}_{t}$.

Next, consider some phase at time $2^{n}\leq t\leq 2^{n+1}-1$. The estimation $\hat{F}_{n}$ is computed using the first $2^{n}$ observed data points. Applying similar techniques for the rate of convergence of empirical process (Norvaiša and Paulauskas, 1991), we obtain

Synthesizing the convergence results in Lemma 3.7 and Lemma 3.8, we establish the following lemma on the performance of $\hat{F}$ in Algorithm 2.

Finally, we now bound the difference between $\hat{F}_{n}$ and $F$ with the help of Lemma 3.9.

With Lemma 3.10 in hand and employing a similar methodology in the proof of Theorem 3.5, we now have