Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions
Authors: Wei Zhang
Yanjun Han
Zhengyuan Zhou
Aaron Flores
Tsachy Weissman
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online learning
bandit
first-price auction

Abstract: With the advent and increasing consolidation of e-commerce, digital advertising has very recently replaced traditional advertising as the main marketing force in the economy. In the past four years, a particularly important development in the digital advertising industry is the shift from second-price auctions to first-price auctions for online display ads. This shift immediately motivated the intellectually challenging question of how to bid in first-price auctions, because unlike in second-price auctions, bidding one's private value truthfully is no longer optimal. Following a series of recent works in this area, we consider a differentiated setup: we do not make any assumption about other bidders' maximum bid (i.e. it can be adversarial over time), and instead assume that we have access to a hint that serves as a prediction of other bidders' maximum bid, where the prediction is learned through some blackbox machine learning model. We consider two types of hints: one where a single point-prediction is available, and the other where a hint interval (representing a type of confidence region into which others' maximum bid falls) is available. We establish minimax optimal regret bounds for both cases and highlight the quantitatively different behavior between the two settings. We also provide improved regret bounds when the others' maximum bid exhibits the further structure of sparsity. Finally, we complement the theoretical results with demonstrations using real bidding data.

Leveraging The Hints: Adaptive Bidding in Repeated First-Price Auctions
Wei Zhang' Yanjun Han
Zhengyuan 3ho
Aaron Flores Tsachy Weissman
'IIT BECS "MIT IDSS 3 AArena Technologies
"NYU Stem Yahoo! Research Stanford EE
(w_zhang, yjhan] edu
zGarena-ai ai com
aaron. aaron..lores@yahooin. com tsachy@stanford.co edu
Abstract
With the advent and increasing consolidation of c-commerce, digital advertising has very recently replaced traditional advertising the main marketing force in the economy. the past four years, a particularly important development in the digital advertising industry is the shift from second-prics auctions first-price auctions for online display ads. This shift immediately motivated the intellectually challenging question of how to bid in first-price auctions, because unlike in second-price auctions, bidding one's 's private value truthfully is no longer optimal. Following a series of recent works in this area, consider a differentiated setup: we do not make any assumption about other bidders' maximum bid (i.e. it can be adversarial over time), and instead assume that we have access hint that serves as a prediction of other bidders' maximum bid, where the prediction is learned through some blackbox machine learning model. We consider two types of hints: single point-prediction, and hint interval (representing type of confidence region into which others' maximum bid falls). We establish minimax near-optimal regret bounds for both cases and highlight the quantitatively different behavior between them. We also provide improved regret bounds when the others' maximum bid exhibits the further structure of sparsity. Finally, we complement the theoretical results with demonstrations using real bidding data.
Introduction
As e-commerce proliferates across the industries, digital advertising has become the predominant marketing force in the economy: in 2019, businesses in the US alone [Wag have spent more than 129 billion dollars on digital advertising, surpassing for the first time the combined amount spent via traditional advertising channels by 20 billion dollars. Since then, this number has been growing and continues to outpace traditional advertising spending [Wag19]. Within digital advertising, the key step that generates such revenue for digital advertising online ads auctions. In the past, second-price auctions, as result of its truthful nature, have been the standard format for online ads auctions [LR00, Kle04, LRBPR07). However, the industry has recently witnessed shift from second-price auctions to first-price auctions in display ads auctions, which currently account for 54% of the digital advertising market" share [DRS19].
This industry-wide shift first-price auctions has occurred for several reasons, including larger revenue (the exchange charges percentage of the winning bid) [Ben18a] and no last-look advantage
"Corresoondence to Yanjun Han (yjhan @ mit.edu) and Zhengyuan Zhou (2@ aiema-ai.ccom.. Search auctions dominate the remaining market, which are still conducted using second-price (or generalize second-price) auctions.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

for exchanges: under second-price auctions, an ad exchange can examine all the submitted bids and then raise the floor price to above the eecond-highess bid and obtain a larger' revenue [Ben18b].
Motivated by these considerations, several ad exchanges, including AppNexus (now Xandr), Index Exchange and OpenX, started to roll out first-price auctions in 2017 and completed the transition by 2018 [Slu App18.]... Google Ad Manager (previously Adx) followed suit and also completed the move to first-price auctions the end of 2019 [Dav 19] and incorporated additional transparency' in their new first-price auction platform: bidders would be able to see the jiinimum-bid-to-ie full information) after each auction on Google Ad Manager, whereas in many other ad exchanges, a bidder only knows whether he/she wins the bid (i.e. binary feedback) [Dav19], Situated in this background, an important question arises: how should a bidder adaptively bid in repeated online first-price auctions to maximize the cumulative payoffs?
(i.e.
Prior to the shift, bidding is straightforward: the optimal bidding strategy is simply truthfully bid one's private value (regardless of what the other bidders do). However, this truthful property no longer holds in first-price auctions. As such, bidding in first-price auctions-and the various inferenceelearning problems arising from it-quickly become complicated. In response, an online decision-making approach has emerged recently, where bidder at each auction t needs to decide the amount b, to bid with given valuation Vt, whereas others' maximum bid my is either assumed to be iid drawn from a distribution (unrelated to anything else) or fully adversarial. More specifically. [BGM 19] (and its follow-up journal version [BGM*2] 21 studied the binary feedback setting and show that: 1) if my drawn iid from an underlying distribution (with a generic CDF), then one achieves the minimax optimal regret of Õ(T3); ); 2) if my is adversarial, then one achieves the minimax optimal regret of ((T)). Subsequently, [HZW20] considered the winning- bid only feedback (i.e. a bidder can observe the winning bid) and established that if m, is drawn iid from an underlying distribution (with a generic CDF), one can achieve the minimax optimal regret of O(T?). While it remains unknown what the result would be when m, is adversarial under winning-bio only feedback, [HZF+ 20] studied
the full-informatin feedback setting and showed that the minimax optimal regret of ( can be achieved when m, is adversarial", [ZKH+21] 21] also studied the full-information feedback setting where it designed and implemented space-efficient variant of the algorithm proposed in [HZF-20] 20] and through empirical evaluations, showed that the algorithmic variant is quite effective.
In practice, others' highest bid m, is often neither stochastic nor adversarial, and contextual informa- tion is often available to gain some knowledge of m, We aim to make inroads into this more practical setup by considering a differentiated setup from the existing and growing adaptive-bidding -idddidddddiifiiii in-first- price auctions literature: we do not make any assumption about other bidders' maximum bid (i.c. can be adversarial over time), model the contexts directly [BFG21]: instead assume an access to a hint that serves as a prediction of other bidders' maximum bid, where the prediction is learned through some blackbox machine learning model which could be much more powerful than simple linear models. We consider two types of hints: one where a single point-prediction is available, and the other where hint interval (representing type of confidence region into which others' maximum bid falls) is available. We establish minimax optimal regret bounds for both cases and highlight the quantitatively different behavior between the two settings. We also provide improved regret bounds when the others' maximum bid exhibits the further structure of sparsity. Finally, we complement the theoretical results with demonstrations using real bidding data.
1.1 Additional Application: Personalized Hospitality Pricing
Another important application that shares similar elements to adaptive bidding in first-price auctions and that hence is also amenable to the methodological framework develop in this paper is personalized hospitality pricing. In personalized hospitality pricing, a travel distribution platform applies a markup given hotel room provided by a supplier (either the hotel itself or some travel
At the extreme, raising the floor price to barely under the highest bid effectively turns it into first-price auction without the bidders being aware.
Google was under sustained criticism of leveraging last-look advantage second-price auctions. This is likely an effort to offset the previous negative image, although there was no such mention in Google's official language.
Note that under both full illlinfformaton feedback and iid m. pure exploitation algorithu already achieves the minimax optimal regret e @(VT).
2

---

aggregator such as Expedia) and presents the final price along with the hotel room whenever user (either consumer or a travel agency) searches for hotel when booking travel. To see the parallel with first-price auctions, the supplier's cost corresponds to the private value, and the final price (which supplier's cost plus the markup) corresponds to the "bid". Note that, the user can access many other competing travel distribution platforms, each of which may provide a different price for the same hotel room (type). Consequently, there is a bidding element because the user will take the lowest price. Further, in this problem, the platform would want to provision personalized markups, where the markup is decided based on search features (destination city, number of nights, days until first check-in). hotel features (ratings, room types) and other generic features (holiday season, time of the year etc). Note that as of this writing, although almost all existing markup provisioning schemes are fixed business rules that are handcrafted (many "if this feature then that markup" logic statements), an adaptive learning approach - such as the one proposed in this paper, has great applicability in practice. In particular, Arena Technologies', a leading enterprise AI solution provider, provides reinforcement learning enabled personalized hospitality pricing. Using publicly available travel pricing data, Arena builds price prediction models that serve as hints, which are in turn used in its real-time adaptive personalization engine. Such differentiated infrastructure both in terms of engineering sophistication and learning flexibility makes easy for the deployment and testing of our (and any future improved) algorithm, thereby broadening its potential impact.
2 Problem Formulation
We study the problem of repeated first- auction with hint as follows. Consider a time horizon with total length T, and there is one round of first-price auction taking place at each time. At the beginning of each round, a bidder observes a particular item and has a private value v, E [0, 1] for Then, based on her past observations of others' bid and by for that round, she bids b, E [0, us] for that item. The bidder wins the round if and only by is larger than others' highest bid, defined as m.. Under the above settings one could write the instantaneous reward at time / for that bidder:
r(bei Ut, me) = (ve- - be) 1(b 2 mz).
Define policy the overall bidding strategy, which is sequence of bidding prices (b1, b2 br)
under corresponding private value sequence {v,} } and others' highest bid sequence {m,}, }. and we use Elr(b;; m,, v. denote the expected reward under policy ı while the expectation is taken over the randomness inside randomized policy л. Then we define the regret under policy T:
T
T
Reg(T) = max Σ r(a(u)): m4, ut) t=1
Σ
Bir(by m,, ve)l.
(2)
aEFLM
where a denotes a bidding oracle a map from private values vi to bidding prices by and a(v)) is the bidding price under oracle a." Here FL-M is the set of oracles we compete with, which is the set of all 1-Lipschitz and increasing functions from [0, 1] + [0, 1].
The above settings are similar to that in [HZW20] [HZF* 20), and in this work, we include additional information provided to the bidder at each round. The goal is to analyze how the performance of hints may influence the regret bounds in theory. We consider two forms of hint, both of which contain a point estimate h, of the minimum-bidd bid-t--ddt-tiiinn m, at time and the difference lies in whether a bidder observes single hint or a hint interval, with the latter defined as a pair (he, ox) satisfying:
E [lh - mzl' S of, t t= 1,2,
,T ,,
(3)
where q measures how accurate the error estimation is, namely, as q becomes larger the bidder is more confident that hy and my's 's difference is smaller than de- If we consider the extreme case of q + oc, then m, is almost surely inside [hg - or, h4 or). Note that (3) always holds regardless of whether the learner observes a hint or hint interval, and the main difference is that o, is only revealed in the latter scenario. The bidder's goal is to maximize the cumulative reward for the whole time horizon, and equivalently, to minimize the overall regret. Let := Σi= ae be the total error of hints, the learner aims to achieve a small regret adaptive to the unknown quantity L: the regret is never larger than the no-hint case even for large L, but becomes significantly smaller if L is small.
See http://www..renaa-ll com/ for more information.
In the following we may use Fr.e to abbreviate ((a(v); me, mv) ve).
3

---

3 Regret Gap Between Single Hint and Hint Interval
In this section we identify two unique features of leveraging the hints in first-price auctions. First, the best way to use hints is different from the ones in the literature of online learning: instead of adding an optimistic term based on the hints in the multiplicative weights algorithm, in first-price auctions we should manually add the hints as between the regrets under single hints and hint intervals, a phenomenon which does not occur in the hint literature.
expert. Second, first-price auctions exhibit provable gap
3.1 Online Learning with Hints
There is rich line of literature related to online learning with hints where aims achieve data-dependent regret bounds terms of the variation in the environment [AAGO06, HKI1,CYL++ 122+12 RS13,SL114, WL.18, BLL.19) 19], by taking part of the revealed past losses implicitly the hint. The algorithm to leverage these hints typically falls into the category of optimistic online mirror descent, where the hint is used form optimistic estimate of the current loss. piece of work that explicitly formulated the hint similar to ours is [WLA20], which used an optimistic EXP4 algorithm to achieve regret bound of (mmin ( (VT, //T when the total eπrоr L of the loss predictors is known.
The nature of first-price auction problems, however, is different from the above. The crucial feature the discontinuity the reward function (1) when b, close to the minimum- bid-to-win m,, which means that every bid by This distinction not only leads to different optimal regrets, but also results in different algorithms for regret minimization, well as curious gap between the optimal regrets under single hints and hint intervals. The concept of the hint interval does not offer additional help over single hints in many other online learning problems, and the best of our knowledge, new in the literature.
accurate prediction of my does not imply accurate reward prediction under
3.2 Regret Gap Between a Single Hint and a Hint Interval
In this section, show that the above distinctions are already present in toy example where all private values i, are the same for / = 1.2..... T (say v, = 1). Our first result states that even under this very simple case, there striet separation between the regret bounds of knowing single hints and that of knowing hint intervals.
Theorem 1. For L E [1, (o), if = 1 and the bidder observes a hint interval at each time the policy лi in Algorithm 1 satisfies
Reg(a1) & CV log T Tw Lavi,
for a numerical constant C independent of {m,, hi, ot). Moreover, the following minimax lower bound holds:
inf sup Reg(T) 2 eV THT LutT. he
Here e > 0 is numerical constant independent of (T, L), the supremum is taken over all {ma, he, oz} sequences that satisfy (3), and the infimum is taken over all possible policies n.
Theorem v = and the bidder observes a single hint at each time t, then for every q E oo),
the policy in Algorithm I with T extra experts bidding h2 + 1/. ... 1/T) achieves
Reg( S C (log T) (T 1.)
for a numerical constant C independent of (ma, hr). Moreover, the following minimax lower bound holds:
inf sup Reg(T) 2 cT L)
(m
Here c. >> O is a numerical constant independent (T, L.), the supremum taken over all {mi, sequences that satisfy (3), and the infinum is taken over all possible policies n.

---

The above result shows that there is a strict separation in regret bounds compared to the previous subsection when additional information given. Observe that in Theorem I, when q becomes larger. the minimax regret becomes smaller because the error estimation is more accurate. In Theorem 2, however, the lower bound stays the same order as q changes, and strictly larger than the case of knowing the hint interval as long as q 1. When -> oc, the upper and lower bound in Theorem 1 gives optimal Ö(VL) magnitude for the minimax regret.
The intuition behind this separation can be explained as follows: hint intervals can be considered as single hints plus an additional information of its accuracy. For example, if the hint interval has length 6 -> O, one strategy would be bid exactly as the hint suggests; however, if the bidder do not observe an interval, it is hard for her to wisely arrange the weight she put in the hints given and thus leading to a smaller reward compared to previous case. This distinction turns out to be crucial because of the discontinuity of the reward in (1).
Also note that the upper and lower bounds in Theorems and are tight within logarithmic factors, and exhibit the desired adaptive regret the hint performance T: when as large as T, an O O(vT) regret is attainable which is optimal without the hints; as the quality of the hints becomes better, the regret dependence on I' is greatly improved.
3.3 Algorithm for Section 3.2
It is classical result in online learning that the multiplicative weights algorithm in [LW94] leads to classical regret upper bound of O (VT. .og K), for K experts and time horizon T under the setting of prediction with expert advice. With hints in first-price auctions, instead of using optimistic online mirror descent in the literature, we modify the multiplicative weights in another way: we run the same multiplicative weights algorithm with an additional expert in the existing set of experts, whose bid depends on the hint /4,
Specifically, the algorithm achieve the upper bound in Theorem 1 is Algorithm 1. Construct T base experts, and let the i-th (i = 1,2, 1....... TT base expert bid T at each time t (since i2 = the Lipschitz oracle will bid constant value). It is easy see that the discretization error incurs additional regret at most T (1/T) = (1)) Now with the hint interval, we include an extra expert a² who bids h, + of of/(o+1)) each time Consequently, have set of K T + 1 experts in total, containing T base experts and one hint expert. The multiplicative weights algorithm is then applied as follows:
exp (n Eoci EdeeKy exp (n Eoce)) a a [K], 1 t= I,...,T, T,
Pt.a
The main ideas of our algorithm are:
We discretize the bids by (and possibly the private values i when we do not assume that = 1 later) when constructing oracles without large loss of cumulative rewards compared to continuous ones, since an enumeration of all 1-Lipschitz functions is unrealistic.
Imagine if the bidder knew the possible range of m, at the beginning of time t: [m, my). then she could bid the upper point my and this is a (m, - m,)-good expert in the sense of [HZF*22 20, Lemma 1], which is an appropriate tool handle the discontinuity in the rewards.
We show in Appendix B. that Algorithm achieves the regret upper bound shown in Theorem I. As for Theorem 2 we include N hint experts, each of which bids constant gap A above h at all time, iee. the first one bids b, = hy for all f, and the second one bids b, = h4 + 1 for all f, ect. We now have "dense" set of hint experts covering all strategies that bid b, h4 T t= 1,2, .. T, with total loss at most ((1). (See details of the proof in Appendix B.
[0, 1),
Notice that in both cases we required knowledge of L to decide learning rate 7/t at each time I, but this problem can be addressed by existing techniques [ACBG02, YEYS04). Indeed, the upper bound in Theorem 2 still holds even if L is not known in advance.
5

---

Algorithm 1: Multiplicative Weights with Hint Intervals
Input: Time horizon T; Hints accuracy I q-
Output: A bidding policy π. Initialization: Construct = T experts, with the i-th 1, ,,) base expert bidding T at each time and an extra expert a" bidding he + of o//l++1) at each time t; for a E [K] do Initialize Ta.a f- 0: end
for & (1,2,...,,T) do
The bidder receives private value E2 1; The bidder observes hint hy E [0, 1], along with its accuracy oz
Set bt.a" + h4 + oz
Set learning rate T/ f min
log
41
V
Ensior Eusoogti
Let by br,a with probability
exp (m: Eseer Teaa)
Pta Exe(K] exp (nh Eoce )
The bidder receives others' highest bid mi; for E [K] do
Tıa - Tiaa + r(be,oi U2, mi).
end
Update R2 R + r(be U., end
3.4 Varying Private Prices
When private values could vary, oracles cannot bid the same price anymore. The following theorem holds, again showing a strict separation and furthermore indicates that for varying Ut hints does not help much for continuous bidding value.
Theorem 3.
Let L E [1, q [1, oo), and v, E [0. for 1.2....,11 T. hint intervals, the following characterization of the minimax regret holds:
the bidder observes
inf (ee
sup
Reg(T)- = (min { LatE, vT)).
-6mmn
where the supremumn taken over rewards under all possible {Di, m,, hy, 01} sequences and hints that satisfy (3), and the infimum is taken over all possible policies π.
Theorem 4. Let L E [1. and v, E [0, for t = 1, 1.2....,T. T. then Vig E [1, oc). the following characterization of the minimax regret holds:
the bidder observes single hints,
Reg(T)= = (
inf
sup (n.o))
where the supremum is taken over rewards under all possible (ve, m4, he, or) sequences and hints that satisfy (3), and the infimum is taken over all possible policies n.
Although both results in Theorems 3 and 4 tight within logarithmic factors, they pessimistic results. When the hint intervals are observed, Theorem 3 shows that the help from the hint exhibits thresholding phenomenon: either bidding without hints or only bidding the hints is optimal. For example, when y = oc, the minimax regret is simply tedious quantity (min L, vT)). When there are only single hints, Theorem 4 even shows that the hint is of no help unless its quality is very high, i.e. T, S 1. This pessimistic situation is alleviated in the next section, by imposing an additional assumption that others' bids m, only supported few locations.

---

Exploiting the Sparsity of Others' Bids
The previous section gives a pessimistic result that hints help only the same extent of bidding the hint itself. To mitigate this drawback, we identify a useful structure in practical online first-price auctions: the maximum competing bids my are supported on only few locations. See Figure for typical example in real data. The reason why sparsity arises in practice is partially due to the scenario where the maximum competing bid is the reserve price set by the seller.
x10
Data
2
2.5
3.5
4
4.5
5
Highest Bid of Other Bidders
Figure I: Histogram of others' highest bid in real data.
Assuming that m, only supported on locations, the central question in this section is as follows:
How does the sparsity improve the minimax regret? Can we devise learning algorithm that is adaptive to the parameter K (and other parameters such as L)?
4.1 Minimax Regret with Sparsity
The central result of this section is the following characterization of the minimax regret with sparsity:
Theorem 5. For g E [1, oo) and varying private prices, suppose that the minimum-bie bii------d--tiin me only takes K support values and the hint intervals are available. The regret is upper bounded by:
Reg(n) 0 00000000mn (
T L K, KT L VT)) VT))
inf sup he
where the supremum is taken all (U,, my, O1) sequences and hints that satisfies (3), and the infimum is taken over all possible policies x. In addition, the following minimax lower bound for the regret holds:
Reg(m)= = Ω (min min (Vr Lo KK Loti VTJ). de.
inf sup
Theorem shows that the minimax regret exhibits an elbow with respect to the sparsity: the regret grows sublinearly with K for small K, but reduces to the fixed value è (min {T - vT) of Theorem 3 when K is large. Moreover, the better the hint quality is, the more helpful the sparsity will be. For example, if = O(1), sparsity helps reduce the regret whenever K < T1/(+1), as the other extreme, = (TT), the classical O (VTT) regret is always unavoidable, no matter how small K is.
4.2 Meta Algorithm Adaptive to Unknown L and K
In the proof of Theorem 5 (see appendix C.I) we prove the three upper bounds can indeed be achieved separately. If bidder observes the overall quality of hints L at the beginning, she can casily choose the best among those three bounds and achieve an optimal. It is not straightforward though, to achieve them simultancously without this knowledge. For instance, to achieve each single upper bound, there a data-driven algorithm agnostic to (such as using the idea in [ACBG02]]; however, the choice of which algorithm to still depends on the knowledge of L.
Algorithm (pseudocode Appendix A) with meta-experts addresses this problem and ensures to achieve the optimal one among the three upper bounds for any L = 2(1). The intuition is to give hints a higher priority the error small. Meanwhile, with this meta structure, is possible to set different fine tuning strategy for the two layers. By including three "Meta Experts" in the upper layer,
7

---

whose strategies are indeed output of algorithms rather than pre-designed oracles, we can achieve the minimum of the three regret bounds listed Theorem 5.
Algorithm 2
Super Expert
Hint Expert(s)
ChEW [HZF+20]
Base Experts
Hint Expert(s)
Theorem 6. Algorithm 2 achieves the regret upper bound of Theorem while it is agnostic the knowledge of L.
Theorem is also true when the support size K and support locations are unknown together with L." Using similar ideas of the doubling trick, we can deal with unknown K. At the beginning assume constant value Ku (e.g. Ko 8), and run the above algorithm until the number of observed supports up to time exceeds the current value. If that happens, we double the value of K: K (i E N), and restart the learning algorithm. Since assuming a larger K than reality only makes the oracle stronger, substituting the regret upper bound (4) below to this strategy leads regret upper [log
K;
bound (let M
(8)
1):
M
Ti+1
T Σ
Vlog log T
K₁
50 Vlo /
(Ko+ + + KM)
0
1=0
t=
0
VVogT TogT-220 2K T L
where K; : Ko 2" and Ti are the dividing points when current number of supports exceeds current K (T (TM+1 T).
For unknown support values construct an expert set as follows. We divide y-axis (bidding price) into
T small intervals, with the i-th interval being [ T (i = 0, 1,. T 1). Our goal is allocate the K supports into these 7" intervals, with each interval containing at most one support (two supports in the same interval could be merged with additional O(1) regret). The total number of allocations
(7). and for each allocation, the oracle can only choose from T bidding functions (cf. the proof of Theorem 5), thus the size of the complete expert set is:
lexpert set| s
T < T
K
Then the regret upper bound can written as (using similar analysis to Appendix B.1.1)
(1 log (
T Σ o
(1
T
=0
K log T
Σ 0
(4)
1=1
1=1
4.2.1 Single Hints Case
In Section 3 mainly showed that there strict difference the regret bound for single hints and hint intervals case. Here we also provide results for single hints case for completeness.
Theorem 7. For q [L, 00) and varying private prices, the minimum bid to win takes K support values and the bidder only observes a single hint at each time then the regret bounds hold:
Reg(T) = min VT. (TT.VVLT.K)
inf sup (v.mm.....r..)
where the supremum is taken over all K-sparse m, sequence and hints that satisfies (3), and the infimum is taken over all possible policies n.
"Since our algorithm is adaptive to I as discussed in the previous section, it is equivalent to say no parameter about the whole game known.

---

Real-data Experiments
This section presents several real-data experiments in repeated first-price auctions based on practical bidding data, where the hint is the context-bane based prediction provided by blackbox machine learning models. For business confidentiality
do not disclose further information about the datasets.
Our experiments are run on auction datasets from the first-price auctions on real-world sites, with around 0.38 million data points, where each data point is quadruple of scalars (Vz, M7, h4, oτ). Here Vi is the private value and my is the minimum bid to win for each auction. The private value or is computed by Verizon Media based and is therefore taken as given. The quantity m, is the minimum bid to win and is returned by the platform after each auction, which is by definition the other bidders' highest bid (possibly including the seller's s reserve price and measured up to I cent). These datasets have already been pruned to only contain data points with t > My, for otherwise the bidder never wins regardless of her bids. Hints hy and its accuracy o, are provided by fitting lognormal model using other contextual information.
independent learning scheme not relying on the auction,
We did two parts of experiments. In the first part, applied the main insight in Section 3 that for fixed private value, given extra information of hints helps reduce the regret for optimal policy, and hint intervals outperforms single hints, as long q > 1. We allocate all data points to separate bins according to the private value bt and each bin is a subproblem described Section Figure ((a) compares the results of binned exponential weighting (without hint) and whether hint intervals or single hints are given. We can observe although the performance of hints itself is obviously bad, by incorporating hint into the learning method, could improve the cumulative reward by 2.96% if knowing point estimation only, and by 3.55% if an interval is provided in each round.
We also provide polynomial time algorithm for conducting the meta algorithm we proposed before. Even with T experts, we may use dynamic programming to achieve a space complexity O(DK) and time complexity O(DK where D is parameter for the discretization on private values. We implemented Algorithm 3 on dataset with support size K
3.5 x
18
Baseline
Bineed
Sianed EW
Dracee Rest
Learinn with Hin mevil
Cumulative Raward
2.5
Beating fixt
Cumule live Reward
Bidding Hill
10
Time Horzzn
Time Horzzo
x10
(a)
(b)
Figure 2: Cumulative rewards function of time, based on Algorithms and 3. Panel (a) uses binning method to show the improvement by incorporating hints. The yellow solid line corresponds to learning with single hints, while the dashdot line corresponds to hint intervals. As comparisons, also include a baseline algorithm (blue) provided by Verizon Media, the simple exponential weights algorithm without hints (red), and just bidding the hint (green). Panel (b) illustrates the performance of our Algorithm 3 (purple solid line), which almost coincides with the performance of the best increasing and I-Lipschitz function for the oracle (yellow dashed line). The other algorithms the same as Panel (a).
Conclusion
In this work we study the overall regret for particular bidder without further assumption for other bidders in repeated first-price auction. We target at the case when an additional information given to only this bidder at each round. We show that even in a simple setting, there is strict gap between two different forms of hints, where in either one the upper bound and lower bound matches with regard to log factor. We further consider the case when others' highest bid lies in finite support,

---

and provide modified algorithm as well as matching regret upper and lower bounds. While not knowing the critical parameters for the whole game the begimning, our adaptive algorithm always achieves the best among three different upper bounds. Finally, we appreciate data from company that corresponds with our framework, and carry out two parts of experiments on it. The first one is mainly to show the performance improvement with the information given, and in the second part, we provide a way to implement our algorithm in polynomial time and show corresponding results.
Acknowledgements
This work supported in part by NSF awards CCF-2106467 and CCF-2106508. Zhengyuan Zhou acknowledges the generous support from New York University's s Center for Global Economy and Business faculty research grant. We would like to thank the NeurIPS 2022 reviewers for their constructive feedback and Eric Ordentlich for helpful discussions in the early stage of this work.
10

---

References
[AAGO06]
Chamy Allenberg, Peter Auer, László Györfi, and György Ottucsák. Hannan consisteney in on-line learning in case of unbounded losses under partial monitoring. In International Conference Algorithmic Learning Theory, pages 229-243. Springer, 2006.
[ACBG02]
Peter Auer, Nicolo Cesa-Bianchi, and Claudio Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48-75, 2002.
[App18]
AppNexus. Demystifying auction dynamics for digital buyers and sellers. AppNexus white paper, 2018.
[8en18a]
Ross Benes. Published: October 17, 2018.
First-price auctions are driving up ad prices. wwt..//arrceer..o///ontnnttitiie
wrrpiioon--ae-driiine are-ddiving-uy saape------d---eeeee 2018.
[Ben18b]
Ross Benes. How ssps use deceptive price floors to squeeze ad buyers. 2018.
http://awwainnss--uuddeeeeeeeeee Published: September 13, 2017.
[BFG21]
Ashwinkumar Badanidiyuru, Zhe Feng, and Guru Guruganesh. Learning to bid in contextual first price auctions. arXiv preprint wrxiv:2/09.03173. 2021.
[BGM+19 19] Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. Contextual bandits with cross-learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché Buc, E. Fox, and R. Garnet,, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[BGM*21] Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. Contextual bandits with cross-learning. 2021.
[BLLW19] Sébastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen- Yu Wei. Improved path- aeth-length regret bounds for bandits. In Conference On Learning Theory, pages 508-528. PMLR, 2019.
(CBL066
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
12YL+12] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pages 6-1. JMLR Workshop and Conference Proceedings, 2012.
[D]v19]
Jessica Davies. What to know about google's implementation of first- ad auc- tions. http://diiiday..oommmiiaaa wwwpe/////tteeewwwlloo---atteete welcome-auction www.om--cuuccooostttaarraattttoi standardizztiinn-sssss-sss- google- finall-goessalll- -nn---nn---------stttt-e-------- piric-ricee,t 2019. Published: September 6, 2019.
[DRS19] Stylianos Despotakis, Ravi, and Amin Sayedi. First-price auctions in online display advertising. Available at SSRN 3485410, 2019.
[HK11]
Hlad Hazan and Satyen Kale. Better algorithms for benign bandits. Journal of Machine Learning Research, 12(4), 2011.
[HZF+20] Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman. Learning to bid optimally and efficiently in adversarial first-price auctions. arXiv preprint arXiv:2007.c 200V::2007..4568,, 2020.
[HZW20] Yanjun Han, Zhengyuan Zhou, and Tsachy Weissman. Optimal no-regret learning in repeated first-price auctions. arXiv preprint arXiv:2003.09793 2020.
[Klc04]
Paul Klemperer. Auctions: theory and practice. Princeton University Press, 2004.
[LR00]
David Lucking-Reiley. Vickrey auctions in practice: From nineteenth-century philately to weent--firstceetuue e-commerce. Journal of economic perspectives, 14(3):183-192. 2000.
[LRBPR07] David I Lucking-Reiley Doug Bryan, Naghi Prasad, and Daniel Reeves. Pennies from
ebay: The determinants of price in online auctions. The journal of industrial economics, 55(2):223 233, 2007.
[LW94]
N Litttlestone and MK Warmuth, The weighted majority algorithm. Information and Computation, 108(2):112-611, 1994.

---

[RS13]
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019. PMLR, 2013.
[SL14]
Jacob Steinhardt and Percy Liang. Adaptivity and optimism: An improved exponen- tiated gradient algorithm. In International Conference on Machine Learning, pages 1593-1601. PMLR, 2014.
[Slu17]
Sarah Sluis. Big changes coming auctions, exchanges roll the dice exchanges-roll-dice
www.://wwwccage...oooaaatooooooe channcs--caannnggg coming-auctiions first-price. diiee--iist-price.l.. 2017. Published: September 5, 2017.
[Wag19]
Kurt Wagner. Digital advertising in the us is finally bigger than print and televi- sion. http:///wwwwoo.oo////////9/2/0//
aalaaadveetisin-aaceboooo 2019. Published: Feburary 20, 2019.
wowwth-t--prin--marreee-------
[WL18]
Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1263-1291. PMLR, 2018.
[WLA20] Chen- Yu Wei, Haipeng Luo, and Alekh Agarwal. Taking hint: How to leverage loss predictors in contextual bandits? Conference on Learning Theory, pages 3583-3634. PMLR, 2020.
[YEYS04]
Rani Yaroshinsky, Ran El- Yaniv, and Steven S Seiden. How to better use expert advice. Machine Learning, 55(3):271-309, 2004.
[ZKH+21] Wei Zhang. Brendan Kitts, Yanjun Han, Zhengyuan Zhou, Tingyu Mao, Hao He, Shengjun Pan, Aaron Flores, San Gultekin, and Tsachy Weissman. Meow: A space- efficient nonparametrie bid shading algorithm. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 3928 3936, 2021.
12

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] Results stated and properly qualified.
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All theorem's have clearly stated assumptions
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are detailed in the Appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [Yes] Pseudocode is included but data confidential
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Didou report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "u7DFGXxojOT", "reviewer": "Reviewer_Bu8B", "summary": "This paper studies the problem of online learning to bid in first-price auctions. In this problem, each round a bidder with some value for the item (either fixed over the duration of the bidding, or independently sampled from a known distribution) must submit a bid; simultaneously, a minimum-bid-to-win MBTW is generated (either adversarially or stochastically from the distribution). If the bidder bids above the MBTW, they win the item (and receive value - bid in utility); otherwise, they lose (and receive nothing). \n\nThis has been a popular question in recent years (largely motivated by the migration of several large advertising auctions from second-price to first-price); this work contributes to the literature by exploring what happens when the bidder is provided some side information regarding the true MBTW. This information takes the form of a “hint”; a value who is guaranteed to be somewhat close (on average) to the true MBTW. The authors differentiate between the cases where the learner receives just the hint each round (“single hint”), or the case where they receive the hint and how noisy it is (“hint interval”) each round. The ultimate regret bounds are in terms of the total error L of the hints (in a similar manner as data-dependent regret guarantees). \n\nThe authors show the following results:\n\n- The authors characterize (up to logarithmic factors) the optimal regret guarantees for the single hint and hint interval setting, in the case where value is fixed. To do this, they present an adaptation of multiplicative weights that incorporates hint information. Interestingly, they show there exists a gap in regret guarantees between these two settings.\n- They also characterize the optimal regret guarantees in the setting of varying private prices. They show in this case it is hard to take advantage of hint information to get asymptotically better regret guarantees.\n- To address this, they investigate whether it is possible to get better regret guarantees if the MBTW is “sparse” and can take on at most K different values. Again they provide asymptotically tight regret guarantees in this setting.\n- Finally, they perform empirical simulations of these learning algorithms on data taken from real auctions (and demonstrate they are effective at incorporating this side-information).\n", "questions": "In Algorithm 1, is it necessary to know all the accuracies sigma_t ahead of time? If not, how do you set the learning rate eta (it seem s like it depends on all sigma_t).", "limitations": "They have adequately addressed this.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Understanding how to bid in first-price auctions is an immensely important problem in practice. Although this paper is not the first paper to study this, I think it makes some fairly interesting and significant contributions both theoretically (it is nice they have fairly tight characterizations of regret guarantees everywhere, and I think the existence of a gap between single hints and hint intervals is an interesting message) and experimentally (they present fairly simple / implementable methods for taking advantage of hint information, something which does exist in real life). \n\nI am not super familiar with all the related literature, so it is hard for me to evaluate how novel these techniques are over e.g. the techniques in the related first-price bidding paper [HZF+ 20] or more general data-dependent learning papers like [WLA20]. My reading is that the proofs are technically involved but this paper doesn’t contribute any especially novel techniques (but I think this is OK in light of its other contributions). \n\nOverall the paper was well-written and easy to read. I would recommend acceptance. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eESL7lHXgiJ", "reviewer": "Reviewer_SqbQ", "summary": "This paper focus on the problem of deriving a best-response bidding strategy in a first-price auction in a bandit setting where a so-called \"hint\" $h_t$ on the highest bid from the competition (the other bidders) is provided. The paper refines existing upper and lower bound on the regret by parametrizing them with the total error made by the hints, inspired by recent path-length parametrizations of regret in bandit. \n\nThe main difference is that, usually, in the literature, a hint $tilde{r}_t(b)$ is provided as an indication of the reward function $r(b, m_t)$ itself. Here the hint $h_t$ informs about the parameter $m_t$ of the reward function.\n\nThe paper provides an algorithm with matching upper and lower bounds in 3 settings about 2 types of hints.\nTypes of hints: just a prediction of $m_t$ or an interval that contains $m_t$ with high proba.\nTypes settings: \n* Constant value $v_t :=1$ and $m_t\\in [0,1]$ \n* Varying values $v_t \\in [0,1]$ and $m_t\\in[0,1]$ \n* Varying values $v_t \\in [0,1]$ and $m_t$ belonging to a finite subset of $[0,1]$ ", "questions": "1. With the same definition for the hint $h_t$, would it be possible / relevant to provide regret bounds parametrized in terms of cumulative reward prediction error $\\tilde{L} = \\sum_{t=1}^T \\int \\big| (v_t - b) \\big(\\mathbb{1}[b\\geq m_t] - \\mathbb{1}[b\\geq h_t]\\big) \\big| {\\rm d}b$ rather than cumulative competition prediction error $L = \\sum_{t=1}^T \\sigma_t$ ? \n\n2. Following the previous question, may it provide finer parametrized bound for the case when $v_t$ varies (Th. 3 and 4)? Even though in my understanding of the proof, it won't improve the lower-bound I think.\n\n3. Would the results of the paper extend to best-response to any (nice enough) auction? Like for instance for C-Lipschitz auctions which have a regret without hint of order $CT^{2/3}$ (see [2, Prop. 4.2]).\n\n[2] Learning in repeated auctions, Nedelec et al. (2022)", "limitations": "I would have liked to have a bit more motivation on the practical use of hints in auctions. Where does it come from ? Who is providing it ? What data is it based on ?", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(+) To my knowledge, the paper does not consists in a simple application of previous technique to the problem of bidding in first-price auction. Indeed, usually, the hint concerns the reward function it self and not a parameter of the reward function. Here, the parametrization of the regret is based on the cumulative prediction error of the parameter and not on the cumulative error of the induced reward function.\n\n(+) I find the result of Th. 3 and 4 unexpected, especially the lower-bound part, even though they feel a bit frustrating. \n\n(-) I would have expected this somehow negative result (of Th. 3 and 4) to be more commented and some intuition as for the why detailed. Especially, this degradation of the regret is introduced as a result of considering varying (rather than constant) values $v_t$, but is solved by considering $m_t$ to have finite support. I completely fail to follow the logic and the intuition.\n\nMinor detail:\n* line 48 it is not optimal for an exchange bidding in a header bidder to bid the second highest internal value see [1] for instance\n* I think the paper could shorten a lot the introduction. The study of first-price auctions is widespread enough not to need such a long motivation in introduction.\n\n[1] Bidder collusion. Marshall (2007)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dKqJpR_s6km", "reviewer": "Reviewer_8AsX", "summary": "In the past four years, an important development in the digital advertising industry is the shift from second-price auctions to first-price auctions. They consider a differentiated setup: assume that we have access to a hint that serves as a prediction of other bidders’ maximum bid, where the prediction is learned through some blackbox machine learning model. They consider two types of hints: one where a single point-prediction is available, and the other where a  hint interval (representing a type of confidence region into which others’ maximum bid falls) is available. They establish minimax optimal regret bounds for both cases and highlight the quantitatively different behavior between the two settings, and provide improved regret bounds when the others’ maximum bid exhibits the further structure of sparsity. They also complement the theoretical results with demonstrations using real bidding data. ", "questions": "Line 259, what is CheW?", "limitations": " I didn’t think it has negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper studies first price auction with hint. Nowadays, first price auction obtains more research interest. The topic is important and the result is good. The writing is clear. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JXVMUPcizWQ", "reviewer": "Reviewer_Bere", "summary": "This paper studies bidding in repeated first-price actions with hints, which could be a point estimate or an interval. The authors first establish optimal regret bounds for both cases when the bidder's value is the same across auctions. The authors further show that when the private values could vary, the hints do not help much. The authors then examine the cases when the others' bids are sparse and demonstrate a better bound. The empirical results support and validate the theoretical findings.", "questions": "* It seems that for the sparsity assumption, even if it holds in practice now, it is vulnerable to future changes or adversarial attacks. In particular, the authors mention that \"Part of the reason for the sparsity is due to the scenario where the maximum competing bid is the reserve price set by the seller.\" If the seller adopts the strategy to set randomized reserve, will the assumption break? Similarly, the competing bidders could adopt randomized bidding strategy as well.", "limitations": "The authors adequately addressed the limitations and potential negative societal impact is not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n* The problem studied in this paper is timely, interesting and important.\n\n* The paper is generally well-written, clear, and easy to follow.\n\n* The results are novel and technically strong; and the empirical results nicely support and validate the effectiveness of the proposed methods.\n\nWeakness\n\n* The sparsity assumption requires more motivations and support from practice. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept