Juliette Achddou
email: juliette.achdou@gmail.com

Diens

Olivier Cappé
email: olivier.cappe@cnrs.fr

Vineeth N Balasubramanian

Ivor Tsang

Fast Rate Learning in Stochastic First Price Bidding

Keywords: multi-armed bandits, sequential bidding, auctions

First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising. As far as learning is concerned, first-price auctions are more challenging because the optimal bidding strategy does not only depend on the value of the item but also requires some knowledge of the other bids. They have already given rise to several works in sequential learning, many of which consider models for which the value of the buyer or the opponents' maximal bid is chosen in an adversarial manner. Even in the simplest settings, this gives rise to algorithms whose regret grows as √ T with respect to the time horizon T . Focusing on the case where the buyer plays against a stationary stochastic environment, we show how to achieve significantly lower regret: when the opponents' maximal bid distribution is known we provide an algorithm whose regret can be as low as log 2 (T ); in the case where the distribution must be learnt sequentially, a generalization of this algorithm can achieve T 1/3+ regret, for any > 0. To obtain these results, we introduce two novel ideas that can be of interest in their own right. First, by transposing results obtained in the posted price setting, we provide conditions under which the first-price bidding utility is locally quadratic around its optimum. Second, we leverage the observation that, on small sub-intervals, the concentration of the variations of the empirical distribution function may be controlled more accurately than by using the classical Dvoretzky-Kiefer-Wolfowitz inequality. Numerical simulations confirm that our algorithms converge much faster than alternatives proposed in the literature for various bid distributions, including for bids collected on an actual programmatic advertising platform.

Introduction

We consider the problem of setting a bid in repeated first-price auctions. First-price auctions are widely used in practice, partly because they constitute the most natural and simple type of auctions. In particular, they have been largely adopted in the field of programmatic advertising, where they have progressively replaced second-price auctions [START_REF] Sluis | Big changes coming to auctions, as exchanges roll the dice on first-price[END_REF][START_REF] Slefo | Google's ad manager will move to first-price auction[END_REF]. This recent transition took place for various reasons. First, whereas second-price auctions have the advantage of being dominant-strategy incentive-compatible and hence allow for simple bidding strategies [START_REF] Vickrey | Counterspeculation, auctions, and competitive sealed tenders[END_REF], they were made obsolete by the widespread use of header bidding, a technology that puts different ad-exchange plat-forms in competition. With this technology, every participating ad-exchange has to provide the winning bid of the auction organized on its platform; a second-level auction is then organized between all the winners to determine which bidder earns the right of displaying its banner. Second price auctions would hence jeopardize the fairness of the attribution of the placement at sale with header bidding. Second, sellers have benefited from the transition, since many bidders continued to bid as in second-price auctions and despite the automated implementation of so-called bid shading by demand-side platforms, meant to adjust their bids to this new situation [START_REF] Sluis | Everything you need to know about bid shading[END_REF]. The transition to first price auctions raises questions for advertisers who need new bidding strategies. In general, bidders participating in auctions in the context of programmatic advertising do not know the bidding strategies of the other contestants in advance, or anything about the valuations that other bidders attribute to the advertisement slot. Not only do they have to learn other bidders' behavior on the go, but they also need to understand how valuable the placement is for their own use (how many clicks or actions the display of their ad on this placement will lead to), which is usually not the same for all bidders.

In this work, we model the problem faced by a single bidder in repeated stochastic firstprice auctions, that is, when the contestants' bids are drawn from a stationary distribution. We consider that the learner's bids will not influence the others' bidding strategies. This approximation is sensible in contexts where the major part of the stakeholders do not have an elaborate bidding strategy. More precisely, many stakeholders never modify their bids or do so at a very low frequency. Moreover, the poll of bidders is very large and each bidder only participates in a fraction of the auctions, which argues in favor of the assumption that the influence of one bidder on the rest of the participants can be neglected.

Model We consider that similar items are sold in T sequential first price auctions. For t = 1, . . . , T , the auction mechanism unfolds in the following way. First, the bidder submits her bid B t for the item that is of unknown value V t . The other players submit their bids, the maximum of which is called M t . If M t ≤ B t (which includes the case of ties), the bidder observes and receives V t and pays B t . If B t < M t , the bidder loses the auction and does not observe V t .

We make the following additional assumptions: {V t } t≥1 are independent and identically distributed random variables in the unit interval [0, 1]; their expectation is denoted by v := E(V t ). The {M t } t≥1 are independent and identically distributed random variables in the unit interval [0, 1] with a cumulative distribution function (CDF) F , independent from the {V t } t≥1 . When applicable, we denote by f = F the associated probability density function.

Due to the stochastic nature of the setting, we study the first-price utility of the bidder:

U v,F (b) := E (V t -b)1{M t ≤ b} = (v -b)F (b). The (pseudo-)regret is defined as R v,F T = T max b∈[0,1] U v,F (b) - T t=1 E[U v,F (B t )] .
We denote by b * v,F = max arg max b∈[0,1] U v,f (b) the (highest) optimal bid. In the rest of the paper, we will abuse notation and speak about regret although rigorously this quantity should be termed pseudo-regret. Note that the outer max is required as the utility may have multiple maxima (see Section 2 below): in that case, we define the optimal bid as the one that has the largest winning rate. In the sequel, we exclude the particular case where F (b * v,F ) = 0, since in this hopeless situation the contestants always bid above the value of the item and the best strategy is not to bid at all (B t ≡ 0): we thus assume that F (b * v,F ) > 0.

In Section 3, we will first assume that F is known to the learner. This setting bears some similarities with the case of second-price auctions considered by (Weed et al., 2016;[START_REF] Achddou | Efficient algorithms for stochastic repeated second-price auctions[END_REF]: the truthfulness of second-price auctions makes it sufficient for the bidder to learn the value of v and the valuation of the item is the only parameter to estimate in that case. However, an important feature of the second-price auction mechanism is that the utility of the bidder is quadratic in v under very mild assumptions on the bidding distribution F . In the case of first-price auctions, the utility is no longer guaranteed to be unimodal, neither is the optimal bid b * v,F a regular function of v. We treat the case, in Section 4, where the CDF F of the opponents' maximal bid is initially unknown to the learner, assuming that the maximal bid M t is observed for each auction. Note that in this more realistic setting, the bidder could not infer the optimal bid b * v,F even if she had perfect knowledge of the item value v. The bidder consequently needs to estimate F and v simultaneously, which makes it a clearly harder task. This second setting bears some similarities with the task of fixing a price in the posted price problem [START_REF] Huang | Making the most of your samples[END_REF][START_REF] Kleinberg | The value of knowing a demand curve: Bounds on regret for online posted-price auctions[END_REF][START_REF] Bubeck | Multi-scale online learning and its applications to online auctions[END_REF][START_REF] Cesa-Bianchi | Dynamic pricing with finitely many unknown valuations[END_REF], in which a seller needs to estimate the distribution of the valuations of buyers, in order to set the optimal price in terms of her revenue. However, in contrast to the posted-price setting, there is an additional unknown parameter v that also impacts the utility function.

In both of these settings, the learner is faced with a structured continuously-armed bandit problem with censored feedback. Indeed, the bidder only observes the reward associated with the chosen bid, but she observes the value only when she wins. This introduces a specific exploitation/exploration dilemma, where exploitation is achieved by bidding close to one of the optimal bids but exploration requires that the bids are not set too low. This structure seems to call for algorithms that bid above the optimal bid with high probability, as in (Weed et al., 2016;[START_REF] Achddou | Efficient algorithms for stochastic repeated second-price auctions[END_REF] for the second-price case, but we will see in the following that it is not necessarily true.

Related Works A major line of research in the field of online learning in repeated auctions is devoted to fixing a reserve price for second-price auctions or a selling price in posted price auctions, see [START_REF] Nedelec | Learning in repeated auctions[END_REF] for a general survey. In the posted price setting, arbitrarily bad distributions of bids give rise to very hard optimization problems [START_REF] Roughgarden | Ironing in the dark[END_REF]. That is why regularity assumptions are often used, like e.g. the monotonic hazard rate (MHR) condition. Most notably, [START_REF] Huang | Making the most of your samples[END_REF]; [START_REF] Cole | The sample complexity of revenue maximization[END_REF]; [START_REF] Dhangwatnotai | Revenue maximization with a single sample[END_REF] use this assumption to bound the sample complexity of finding the monopoly price. Regarding online learning in the posted price setting, [START_REF] Kleinberg | The value of knowing a demand curve: Bounds on regret for online posted-price auctions[END_REF] and [START_REF] Cesa-Bianchi | Dynamic pricing with finitely many unknown valuations[END_REF] introduce algorithms for the stochastic case, respectively in the cases where the distribution of the prices are continuous and discrete. [START_REF] Bubeck | Multi-scale online learning and its applications to online auctions[END_REF] study the adversarial counterpart. [START_REF] Blum | Online learning in online auctions[END_REF][START_REF] Cesa-Bianchi | Regret minimization for reserve prices in second-price auctions[END_REF] study online strategies that aim at setting the optimal reserve price in second-price auctions while learning the distribution of the buyer's bids. [START_REF] Cesa-Bianchi | Regret minimization for reserve prices in second-price auctions[END_REF] assume that bidders are symmetric, but that the bids distribution is not necessarily MHR. They introduce an optimistic algorithm based on two ideas. Firstly they observe that exploitation is achieved by submitting a price smaller than the optimal reserve price, and secondly they use the fact that the utility can be bounded in infinite norm, thanks to the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality [START_REF] Massart | The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality[END_REF].

The problem of learning in repeated auctions from the point of view of the buyer was originally addressed in the setting of second-price auctions. For the stochastic setting, Weed et al. (2016) propose an algorithm that overbids with high probability, and that is shown to have a regret of the order of log 2 T under mild assumptions on the distribution of the bids. They also provide algorithms for the adversarial case, that have a regret scaling in √ T . [START_REF] Achddou | Efficient algorithms for stochastic repeated second-price auctions[END_REF] extend their work by proposing tighter optimistic strategies that show better worst case performances. They also analyze non-overbidding strategies, proving that such strategies can perform well on a large class of second-price auctions instances. [START_REF] Flajolet | Real-time bidding with side information[END_REF] consider the contextual set-up where the value associated to an item is linear with respect to a context vector associated to the item, and revealed before each action.

Learning in repeated stochastic first price auctions is a difficult problem that has given rise to a number of very different though equally interesting modelizations. [START_REF] Feng | Convergence analysis of no-regret bidding algorithms in repeated auctions[END_REF] consider auctions in which the values of all the bidders are revealed as a context before each turn, proving that the bids of bidders who use no regret contextual learning strategies in first price auctions converge to Bayes Nash equilibria. [START_REF] Han | Optimal no-regret learning in repeated first-price auctions[END_REF] also consider the case where the values are assumed to be revealed as an element of context before each auction takes place and the highest bid among others' bids is only shown to the learner when she loses. This setting interestingly introduces a censoring structure that is opposed to the one we consider: in this context, exploitation is achieved by not bidding too high. [START_REF] Han | Optimal no-regret learning in repeated first-price auctions[END_REF] provide new algorithms for this setting which have a regret of the order of √ T . A setting somewhat closer to ours is studied by [START_REF] Feng | Learning to bid without knowing your value[END_REF]. This work deals with the setting of a bid in an adversarial fashion, when the other bids are revealed at each time step and the value is revealed only upon winning an auction. However the proposed algorithm is based on a discretization of the bidding space which relies on the prior knowledge of the smallest gap between two distinct bids. With this knowledge, the proposed algorithm achieves an adversarial regret of the order of √ T .

Contributions

The highlights of Sections 2-4 are the following. In Section 2 we stress the hardness of the first-price bid optimization task, showing that in general it necessarily leads to high minimax regret rates. We however transplant ideas introduced in the case of posted prices to exhibit natural assumptions ensuring that the first-price utility is smooth, paving the way for faster learning. In Section 3, we consider the case where the learner can assume knowledge of F and propose a new UCB-type algorithm called UCBid1 for learning the optimal bid with low regret. UCBid1 is adaptive to the difficulty of the problem in the sense that its regret is O( √ T ) in difficult cases, but comes down to O(log 2 T ) when the first-price utility is smooth. We also provide lower-bound results suggesting that these rates are nearly optimal. In Section 4, we consider the more general setting where F is initially unknown to the learner. By leveraging the structure of the first-price bidding problem, we are able to propose an algorithm, termed UCBid1+, which is a direct generalization of UCBid1. Interestingly, this algorithm is not optimistic anymore: it does not submit bids which are with high probability above the (unknown) optimal bid. However, it can still be proved to achieve a regret rate of O( √ T ) in the most general case and, more importantly, a regret rate upper bounded by O(T 1/3+ ) for every > 0 when the first-price utility satisfies the regularity assumptions mentioned in Section 2. The latter result relies on an original proof notably based on the use of a local concentration inequality on the empirical CDF. All the proofs corresponding to these three sections are presented in appendix. Section 5 closes the paper with numerical simulations where we compare the proposed algorithms with continuously-armed bandit strategies and tailored strategies from the literature, both using simulated and real-world data. There are two important difficulties with first price auctions. The first one lies in the fact that the utility can have multiple maximizers (or multiple modes with arbitrarily close values) and thus lead to arbitrarily hard optimization problems. To illustrate this, we provide in Figure 1 an example of value v and discrete distribution, supported on two values m 0 , m 1 , that leads to a utility having two global maximizers. Note that the utility U v,F (b) is the area of the rectangle with vertices (b, F (b)), (b, 0), (v, F (b)), (v, 0). This observation makes it easy to build examples with multiple maxima. Discrete examples like the one in Figure 1 are intuitive because the utility is decreasing between two successive points of the support, but there also exist similar cases with continuous distributions (see for example Appendix A.3). This example also shows that there exist combinations of bids distributions and values for which the utility is not regular around its maximum.

Properties of Stochastic First-Price auctions

The second difficulty comes from the fact that the mapping from v to the largest maximizer, ψ F : v → b * v,F may also lack regularity. Indeed, keeping the distribution in Figure 1 but setting the value to v = v + ∆, with a positive ∆ (resp. to v = -∆) yields that the set of maximizers is {m 1 } (resp. {m 0 }). Even though ψ F can not be proved to be regular in all generality, it always holds that ψ F is increasing. This is intuitive: the optimal bid grows with the private valuation.

Lemma 1 For any cumulative distribution F , ψ F : v → b * v,F is non decreasing.
The two aforementioned difficulties contribute to making the problem at hand particularly hard. In the following theorem, we show that any algorithm is bound to have a worst case regret growing at least like √ T .

Theorem 2 Let C denote the class of cumulative distribution functions on [0, 1]. Any strategy, whether it assumes knowledge of F or not, must satisfy

lim inf T →∞ max v∈[0,1],F ∈C R v,F T √ T ≥ 1 64 ,
Theorem 2 corresponds to Theorem 6 in [START_REF] Han | Optimal no-regret learning in repeated first-price auctions[END_REF]. For completeness, we prove it in Appendix B. The proof relies on specifically hard instances of CDF that are perturbations of the example of Figure 1. It illustrates the complexity of bidding in first-price auctions, when F and v are arbitrary. This complexity stems from specifically hard instances of F and v. We present a natural assumption that avoids these pathological cases.

Assumption 1 F is continuously differentiable and is strictly log-concave.

This assumption is reminiscent of the monotonic hazard rate (MHR) condition (see e.g. [START_REF] Cole | The sample complexity of revenue maximization[END_REF]), that appears in the analysis of the posted price problem. While MHR requires f /(1 -F ) to be increasing, Assumption 1 requires f /F to be decreasing. In particular, this condition is satisfied by truncated exponentials and Beta distributions with f of the form Cx α-1 where α > 1 or C(1 -x) β-1 where β > 1, or Beta distributions in which α + β < αβ (see Lemma 15 in Appendix A). Assumption 1 plays roughly the same role for first price auctions than MHR for the posted price setting. It guarantees in particular that there is a unique optimal bid. Note that if F satisfies Assumption 1, F is increasing, and admits an inverse which we denote by F -1 .

Lemma 3 Under Assumption 1, for any v ∈ [0, 1] the mapping b → U v,F (b) has a unique maximizer.

As does the MHR assumption for the posted-prices setting, Assumption 1 ensures that the utility is strictly concave when expressed as a function of the quantile q = F (b) associated with the bid b. Another important consequence of Assumption 1 is that the mapping from v to the optimal bid b * v,F is guaranteed to be regular.

Lemma 4 If Assumption 1 is satisfied and f is continuously differentiable, then ψ F : v → b * v,F is Lipschitz continuous with a Lipschitz constant 1.
Indeed, if f is continuously differentiable and if f does not vanish on [0, 1[ (which is implied by Assumption 1), ψ F is invertible and it inverse φ F writes φ F : b → b + F (b)/f (b). Assumption 1 ensures that φ F admits a derivative that is lower-bounded by φ F (b) > 1.

Assumption 1 also implies the important property that the probability of winning the auction at the optimal bid F (b * v,F ) cannot be arbitrarily small when compared to F (v).

Lemma 5 If Assumption 1 is satisfied, then

F (b * v,F ) ≥ F (v) e .
We conclude this section by additional properties that are essential for obtaining low regret rates: the utility is second-order regular, when expressed as a function of the quantiles. Let W v,F denote the utility expressed as a function of the quantile, W v,F : q → U v,F (F -1 (q)), and let q * v,F := F (b * v,F ) be its maximizer. Under Assumption 1, the deviations of W v,F from its maximum are lower-bounded by a quadratic function.

Lemma 6 Under Assumption 1, for any q ∈ [0, 1],

W v,F (q * v,F ) -W v,F (q) ≥ 1 4 (q * v,F -q) 2 W v,F (q * v,F ).
This property relies, among other arguments, on the observation that

W v,F (q) = v -φ F (F -1 (q)) = φ F (F -1 (q * v,F )) -φ F (F -1 (q))
and that φ F is lower-bounded by 1 under Assumption 1 (see discussion of Lemma 4 above).

Similarly, in order to obtain a quadratic lower bound on W v,F (q), one needs to show that φ F may be upper bounded. This is the purpose of the following regularity assumption.

Assumption 2 F admits a density f such that

c f < f (b) < C f , ∀b ∈ [b * v,F -∆, b * v,F + ∆] and φ F : b → b + F (b)/f (b) admits a derivative that is upper-bounded by a constant λ ∈ R + on [b * v,F , b * v,F + ∆].
Assumption 2 holds, in particular, when F is twice differentiable, f is lower-bounded by a positive constant and f is upper-bounded by a positive constant on a neighborhood of b * v,F . Note that in the field of auction theory, it is common to assume that the utility is approximately quadratic around the maximum, which is a far stronger assumption, as stated in [START_REF] Nedelec | Learning in repeated auctions[END_REF] (see [START_REF] Kleinberg | The value of knowing a demand curve: Bounds on regret for online posted-price auctions[END_REF] for example). Assumption 2 implies the following lower bound for the utility expressed as a function of the quantiles.

Lemma 7 Under Assumption 2, for any q ∈

[q * v,F , q * v,F + C f ∆], W v,F (q * v,F ) -W v,F (q) ≤ 1 c f λ(q * v,F -q) 2 .

Known Bid Distribution

In this section we address the online learning task in the setting where the bid distribution F is known to the learner from the start. In order to set the bid B t at time t, the available information consists in N t := t-1 s=1 1{M s ≤ B s }, the number of observed values before time t, and Vt := 1 Nt t-1 s=1 V s 1(M s ≤ B s ) the average of those values. Let t := γ log(t -1)/2N t denote a confidence bonus depending on a parameter γ > 0 to be specified below.

Algorithm 1 (UCBid1) Initially set B 1 = 1 and, for t ≥ 2, bid according to

B t = max arg max b∈[0,1] ( Vt + t -b)F (b) .
This algorithm, strongly inspired by UCB-like methods designed for second-price auctions by Weed et al. (2016); [START_REF] Achddou | Efficient algorithms for stochastic repeated second-price auctions[END_REF], is a natural approach to first-price auctions. The idea behind this kind of method is that one should rather overestimate the optimal bid, so as to guarantee a sufficient rate of observation. As an UCB-like algorithm, UCBid1 submits an (high probability) upper bound ψ F ( Vt + t ) of b * v,F , thanks to Lemma 1 and since ψ F is non decreasing. In practice, the algorithm requires a line search at each step as the utility maximization task is usually non-trivial, as discussed in Section 1.

In the most general case, the regret of UCBid1 admits an upper bound of the order of T log(T ).

Theorem 8 When γ > 1, the regret of UCBid1 is upper-bounded as

R v,F T ≤ √ 2γ F (b * v,F ) T log T + O(log T ) .
Note that √ T is the order of the regret of UCB strategies designed for second-price auctions in the absence of regularity assumptions on F (Weed et al., 2016). However, under the regularity assumptions introduced in Section 2, it is possible to achieve faster learning rates.

Theorem 9 If F satisfies Assumption 1 and 2, then, for any γ > 1,

R v,F T ≤ 2γλC 2 f F (b * v,F )c f log 2 (T ) + O(log T ).
The log 2 (T ) rate of the regret comes from the Lipschitz nature of ψ F , that makes it possible to bound the gap B t -b * v,F , and from the obervation that the utility is quadratic around its optimum. This explains the similarity with the order of the regret of UCBID in (Weed et al., 2016), when the distribution of the bids admits a bounded density. Indeed, in second-price-auctions, when the distribution of the bids admits a bounded density, the utility is locally quadratic around its maximum and the equivalent of ψ F is the identity, meaning that the optimal bid is just the value v of the item. The presence of the multiplicative constant 1/F (b * v,F ) is also expected: it is the average time between two successive observations under the optimal policy. This similarity between the structures of second and first price auctions under Assumptions 1 and 2 also suggest that the constants in the regret may be further improved by using a tighter confidence interval for v based on Kullback-Leibler divergence, proceeding as in [START_REF] Achddou | Efficient algorithms for stochastic repeated second-price auctions[END_REF].

Under Assumption 1, the regret of any optimistic strategy can be shown to satisfy the following lower bound.

Theorem 10 Consider all environments where V t follows a Bernoulli distribution with expectation v and F satisfies Assumption 1 and is such that φ ≤ λ, and there exists c f and

C f such that 0 < c f < f (b) < C f , ∀b ∈ [0, 1]. If a strategy is such that, for all such environments, R v,F T ≤ O(T a )
, for all a > 0, and there exists γ > 0 such that P(B t < b * ) < t -γ , then this strategy must satisfy:

lim inf T →∞ R v,F T log T ≥ c 2 f λ 2 v(1 -v)(v -b * v,F ) 32 .
The first assumption, R v,F T ≤ O(T a ), is a common consistency constraint that is used when proving the lower bound of [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF] in the well-established theory of multi-armed bandits. The second assumption, P(B t < v) < t -γ , restricts the validity of the lower bound to the class of strategies that overbid with high probability. By construction, this assumption is satisfied for UCBid1.

Note that there is a gap between the rates log T in the lower bound (Theorem 10) and log 2 T in the performance bound of UCBid1 (Theorem 9), which we believe is mostly due to the mathematical difficulty of the analysis. The v(1 -v) factor may be interpreted as an upper bound on the variance of the value distribution with expectation v. Theorem 10 displays a dependence on v of the order of v 2 when v tends to 0. However this has to be put in perspective with the fact that the value of the optimal utility U v,F (b * v,F ) is also quadratic in v, when v tends to zero under the assumptions of Theorem 10 (from Lemma 6).

Unknown Bid Distribution

We now turn to the more realistic, but harder, setting where both the parameter v and and the function F need to be estimated simultaneously. For this setting, we propose the following algorithm, which is a natural adaptation of UCBid1, simply plugging in the empirical CDF in place of the unknown F .

It may come as a surprise that we do not add any optimistic bonus to the estimate Ft : it is not necessary to be optimistic about F since the observation M t drawn according to F is observed at each time step whatever the bid submitted.

Algorithm 2 (UCBid1+) Submit a bid equal to 1 in the first round, then bid:

B t = max arg max b∈[0,1] ( Vt + t -b) Ft (b) , where Ft (b) := 1 t-1 t-1 s=1 1{M s < b} and t := γ log(t -1)/2N t .
Although B t produced by Algorithm 2 could, in principle, be arbitrarily small, it is possible to show that there is no extinction of the observation process. Indeed, after a time that only depends on v and F , F (B t ) is guaranteed to be higher than a strictly positive fraction of F (b * v,F ) with high probability (see Lemma 28 in Appendix E). This result implies that the number of successful auctions N t asymptotically grows at a linear rate (with high probability), making it possible to bound the expected difference between Vt + t and v. Combined with the DKW inequality [START_REF] Massart | The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality[END_REF], this allows to bound the difference between the utility and ( Vt + t -b) Ft (b) in infinite norm and hence the difference between B t and b * v,F . Putting all the pieces together (see the complete proof in Appendix E) yields the following upper bound on the regret of UCBid1+.

Theorem 11 UCBid1+ incurs a regret bounded by

R v,F T ≤ 12 γv U v,F (b * v,F ) T log T + O(log T ), provided that γ > 2.
Note that computing the bid B t for UCBid1+ is easy, as ( Vt + t -b) Ft (b) necessarily lies among the observed bids because this function is linearly decreasing between observed bids. More precisely, ( Vt

+ t -b) Ft (b)) = Ft (M (i) )( Vt + t -b), for b ∈ [M (i) , M (i+1) [, where M (i)
is the i-th order statistic of the observed bids (obtained by sorting the bids in ascending order). However, as there is no obvious way to update B t sequentially, this results in a complexity of UCBid1+ that grows quadratically with the time horizon T .

The proof of Theorem 11 relies on the DKW inequality to bound the difference between B t and b * . This happens to be very conservative and a little misleading in practice. Indeed, what really matters is the local behavior of the empirical utility, and hence, of Ft around b * . As illustrated by Figure 2, locally, Ft is roughly a translation of F plus a negligible perturbation which can be bounded in infinite norm. This intuition is formalized in Lemma 12, a localized version of the DKW inequality. The fact that Ft is locally almost parallel to F imposes a constraint on B t that may be used to bound its distance from b * , yielding an improved regret rate under Assumptions 1 and 2, as shown by Theorem 13.

Lemma 12 For any a, b ∈ [0, 1], if F is increasing, sup a≤x≤b | Ft (x) -F (x) -( Ft (a) -F (a))| ≤ 2(F (b) -F (a)) log e √ t η √ 2(F (b)-F (a)) t + log( t 2(F (b)-F (a)η 2 ) 6t ,
with probability 1 -η.

R v,F T ≤ O T 1/3+ ,
for any > 0, provided that γ > 2.

UCBid1+ thus retains the adaptivity of UCBid1. In general, its regret is of the order of √ T (omitting logarithmic terms), matching the lower bound of Theorem 2. But it is reduced to T 1/3+ , for any > 0, in the smooth case defined by Assumptions 1 and 2. In practice, the improvement over other √ T -regret algorithms is huge, as shown in the next section.

Numerical simulations

Benchmark Algorithms

Methods pertaining to black box optimization. Sequential black box optimization algorithms, also known as continuously-armed bandits [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF][START_REF] Bubeck | X-armed bandits[END_REF][START_REF] Munos | Optimistic optimization of deterministic functions without the knowledge of its smoothness[END_REF][START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF], are algorithms designed to find the optimum of an unknown function by receiving noisy evaluations of that function at points that are chosen sequentially by the learner. They rely on prior assumptions on the smoothness of the unknown function. For first-price bidding, we may consider that the reward (v -B t )1(M t ≤ B t ) is a noisy observation of the utility U v,F (B t ), with a noise bounded by 1. Moreover, when F admits a density f and f (b

) < C f , then -1 < U v,F (b) = (v -x)f (b) -F (b) < C f , which implies that U v,F is Lipschitz with constant max(1, C f ).
As a consequence, all blackbox optimization algorithms that consider an objective function with Lispchitz regularity may be used for learning in stochastic first price auctions. HOO [START_REF] Bubeck | X-armed bandits[END_REF] has a parameter ρ related to the level of smoothness of the objective function which we can set to 1/2, corresponding to the observation that the first-price utility is Lipschitz under the assumptions discussed above. This immediately leads to a first baseline approach with O( √ T log T ) regret rate. Setting the parameter related to the Lipschitz constant of HOO so that it is larger than C f is not possible in practice without prior knowledge on F . More generally, knowing the smoothness is considered a challenge most of the time in blackbox optimization, so that several methods have been introduced that are adaptive to the smoothness, e.g. stoSOO [START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF].

UCB on a smartly chosen discretization. [START_REF] Combes | Unimodal bandits: Regret lower bounds and optimal algorithms[END_REF] prove that when the reward function is unimodal, a discretization based on the smoothness level of this function suffices to achieve a regret of the order of √ T . If F satisfies Assumption 1, U v,F is unimodal, as shown by the proof of Lemma 3. Hence, using the right discretization while applying UCB, one can achieve a O( √ T ) regret. In particular if the utility is quadratic, the advised discretization is a grid of O(T 1/4 ) values.

O-UCBID1. We also implement the following algorithm, that is reminiscent of the method used by [START_REF] Cesa-Bianchi | Regret minimization for reserve prices in second-price auctions[END_REF] to learn reserve prices.

Algorithm 3 (O-UCBid1) Submit a bid equal to 1 in the first round, then bid:

B t = max{b ∈ [0, Vt + t ], Ût (b) ≥ max b∈[0,1] Ût (b) -2 t }, where Ût (b) = ( Vt -b) Ft (b).
This algorithm overbids with high probability, by construction. Thanks to the DKW inequality, one can control the difference between the true bid distribution F and its empirical version Ft in infinite norm. Because we observe M t at each round, F -Ft ∞ is at most t with high probability. It is easy to show that U v,F -Ût ∞ is bounded by a multiple of t showing that B t is (again with high probability) larger than the unknown optimal bid b * v,F . O-UCBid1 is very close to the method used by [START_REF] Cesa-Bianchi | Regret minimization for reserve prices in second-price auctions[END_REF] to set a reserve price in second-price auctions. While in first-price auctions, a bidder needs to overbid in order to favor exploration, sellers in second-price auctions are encouraged to offer a lower price than the optimal one, as they can only observe the second highest bid if their reserve price is set lower than the latter. The approach of Cesa-Bianchi et al. ( 2014) requires successive stages as sellers in second-price auctions can only observe the second-price and need to estimate the distribution of all bids based on this information. In our setting, we have direct access to the opponents' highest bid and successive stages are not required any longer. We prove that the regret incurred by O-UCBid1 is of the order of log T √ T when γ > 1, which makes it an interesting baseline algorithm, that has guarantees similar to those of black box optimization algorithm, without the need of knowing the smoothness or the horizon. We refer to Theorem 23 in Appendix E for further details.

Methods for discrete distributions We run UCBid1+ on discrete examples. In this case, we compare it to UCB on a discretization of [0, 1] and to WinExp, a generalization of Exp3 for the problem of learning to bid [START_REF] Feng | Learning to bid without knowing your value[END_REF]. In this section we focus on two particular instances of the first price auction learning problem. The first instance is characterized by a value distribution set to a Bernoulli distribution of average 0.5, and a distribution of the highest contestants' bids set to a Beta(1,6). The second instance only differs by the distribution of the highest contestants' bids, which is set to a mixture of two Beta distributions: 0.55 × Beta(500, 2500) + 0.45 × Beta (1000,2000). This distribution is very close to that used in the proof of Theorem 2, but is continuous. The cumulative distribution and the matching utility of each instance are plotted on Figure 3. Both distributions are smooth but the first one satisfies Assumption 1, while it is not clear that the second one does.

Experiments On Simulated Data

Figures 4(a)subfigure and 4(b)subfigure show the regret of various strategies when F is known. The first (respectively second) figure represents the regrets of these strategies under the first (respectively second) instance of the problem described above. The horizon is set to 10000 and the results of 720 Monte Carlo trials are aggregated. The plots represent the average regret over time (shaded areas correspond to the interquartile range). The strategy termed Greedy is a naive strategy that bids max arg max Ût (b), whenever it has made more than three observations. It shows a linear regret, which comes from the fact that when it only observes value samples equal to zero during the first three observations, it bids 0 indefinitely, and thus incurs the regret

U v,F (b * v,F ) -U v,F (
0) at each time step. Observing only 0 three times in a row is not very likely: the third quartile is very small, but the consequences are so terrible that the average is many orders of magnitude higher. The strategy termed Balanced consists in bidding the median of the highest contestants' bids. It guarantees that the learner is able to win half of the rounds. As expected, this strategy, which does not adapt to the instance at hand, shows poor performances in both cases. However, it is a better solution than bidding 0 or 1. Finally, we also plot the regret of UCBid1. Note that in order to implement UCBid1 we would have to compute arg max b∈[0,1] ( Vt + t -b)F (b) at each round; instead we only use an approximation of this quantity by computing the argmax of the function over a grid of 10000 values. UCBid1 outperforms the naive baseline strategies in both cases. Under the more complex second instance of the problem, it shows a larger regret than under the first one. However, even in this more complex case, the rate of growth of the regret stays very low.

In Figure 5, we analyze the regrets of different algorithms when F is unknown. In this setting, we compare UCB on a discretization of [0, 1] with 10 arms, HOO [START_REF] Bubeck | X-armed bandits[END_REF] with various parameters, O-UCBid1 and UCBid1+ with γ = 1 and stoSOO [START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF] with the parameters recommended in the latter paper. For efficiency reasons, we also do not allow the tree built by HOO and stoSOO to have a depth larger than log 2 T . The various versions of HOO, UCB, as well as stoSOO show regret plots that could correspond to a √ T behavior. UCBid1+ shows a dramatically improved regret plot compared to the black box optimization strategies. We compare UCBid1+ with UCB, having operated a discretization into 10 arms and with Winexp with a discretization into 50 arms. UCBid1+ again yields a regret at least 5 times smaller than the other algorithms. In addition, it is important to stress that UCBid1+ and O-UCBid1 are anytime algorithms, while all the alternatives shown on Figures 5 and6 require, at least, the knowledge of the time horizon.

Experiments On a Real Bidding Dataset

We also experiment on a real-world bidding dataset representing the highest bids from the contestants of one advertiser on a certain campaign. Thanks to Numberly, a media trading agency, Adverline, an advertising network, and Xandr, a supply and demand-side platform, we collected a set of 56607 bids that were made on a specific placement on Adverline's inventory on auctions that Numberly participated to, for a specific campaign. We keep only the bids smaller than the 90% quantile and we normalize them to get data between 0 and 1 (see Figure 10 in Appendix F for a histogram). The regret plots are represented in Figure 7(b)subfigure. As earlier, with discrete simulated data, we compare UCBid1+ with UCB, having operated a discretization into 10 arms and with Winexp with a discretization into 100 arms. Unsurprisingly, the regret plots are similar to those with simulated data, A.2. Properties under regularity assumptions Lemma 3 If Assumption 1 is satisfied, then for any v ∈ [0, 1], U v,F has a unique maximizer.

Proof If F satisfies Assumption 1 then f F is decreasing and φ

F : b → b + F (b) f (b) is increasing and f does not vanish on ]0, 1[. The derivative of U is U (b) = v -b -F (b) f (b) f (b). So U (b) = 0 if and only if v = b + F (b) f (b)
. Since φ F is increasing, this can only be satisfied by a single b ∈ [0, 1]. Also, since f does not vanish, U is unimodal (increasing then decreasing).

Lemma 14 If Assumption 1 is satisfied, then W v,F is strongly concave.

If F satisfies Assumption 1 then f F is decreasing and φ F : b → b + F (b) f (b) is increasing and f does not vanish on ]0, 1[. The derivative of U is U (b) = v -b -F (b) f (b) f (b). The derivative of W is W (q) = v -b -F (F -1 (q)) f (F -1 (q)) = v -φ F (F -1 (q)), since φ F is increasing. Consequently, U is de- creasing, and U is strongly concave. Lemma 4 If Assumption 1 is satisfied and f is differentiable, then ψ F : v → b * (v, F ) is Lipschitz continuous with a Lipschitz constant 1. Proof If b * is the optimum of the utility U , then it satisfies (v -b * )f (b * ) -F (b * ) = 0. It satisfies φ F (b * ) := b * + F (b * ) f (b * ) = v. Since φ F (b * ) > 1 thanks to Assumption 1, φ F is invertible and (φ F ) -1 = ψ F is Lipschitzian with constant 1 . Lemma 5 If Assumption 1 is satisfied, then F (b * ) ≥ e -1 F (v) Proof We know that b * < v and log F (v) F (b * ) = v b * f (u) F (u) du. Hence F (v) F (b) = exp v b * f (u) F (u) du .
Since f (u) F (u) is decreasing, thanks to Assumption 1,

F (v) F (b) ≤ exp (v -b * ) f (b * ) F (b * ) . We have v -b * = F (b * ) f (b * ) , by definition of b * . Hence exp v -b * ) f (b * ) F (b * ) = exp(1)
and

F (b * ) ≥ exp(-1)F (v).
Lemma 6 If Assumption 1 is satisfied, for any 0 ≤ q ≤ 1,

W (q * ) -W (q ) ≤ 1 4 (q * -q ) 2 W (q * )
Proof Note that this proof is an adaptation of the proof of Lemma 3.2 in [START_REF] Huang | Making the most of your samples[END_REF]. In this proof, we denote by b(q) F -1 (q). First of all, let us observe that

U (b) = (v-φ F (b))f (b). We have W (q) = v-φ F (F -1 (q)). Assumption 1 implies that φ F (b) > 1, ∀b ∈ [0, 1].
To prove Lemma 6, we will apply case-based reasoning. There are three cases depending on the relation between q and q * : q > q * , q = q * , and q < q * . The second case, i.e., q = q * , is trivial.

First, consider the case when q > q * . It holds

W (q * ) -W (q ) = q q * -W (q)dq = q q * φ F (b(q)) -v dq.
We therefore need to bound φ F (b(q), ∀q ∈ [q * , q ]. By definition of q * , for any q s.t. q * ≤ q ≤ q , we have q(v -b(q)) ≤ q * (v -b(q * )).

By rewriting this equation,

b(q) ≥ qv -q * v + q * b(q * ) q = v q -q * q + q * q b(q * ) (1)
Secondly, by the intermediate value theorem, there exists b

∈ [b(q * ), b(q)], such that φ F (b(q)) -φ F (b(q * )) = φ F (b) b(q) -b(q * ) ≥ b(q) -b(q * ),
for any q * ≤ q ≤ q , where the second inequality follows from Assumption 1 that dφ F (b) db ≥ 1 and F being increasing thanks to Assumption 1. This in turn yields

φ F (b(q)) ≥ v + b(q) -b(q * ), since by definition, W (q * ) = φ F (b(q * )) = v. Combining with Inequality 1, we get that φ F (b(q)) -v ≥ v( q -q * q ) + q * q b(q * ) -b(q * ) ≥ (v -b(q * ))( q -q * q ) = W (q * ) q * ( q -q * q )
Therefore, we get that

W (q * ) -W (q ) = q q * -W (q)dq = q q * φ F (b(q)) -v dq ≥ W (q * ) q * q q * q -q * q dq ≥ W (q * ) q * q q +q * 2
q -q * q dq, since q-q * q ≥ 0 for any q ≤ q ≤ q * . Moreover, for any q ≥ q +q * 2 , we have q-q * q = 1 -q * q ≥ 1 -2q * q +q * ≥ q -q * q +q * . Hence, we can derive the following inequality

W (q * ) -W (q ) ≥ q q +q * 2 q -q * q + q * W (q * ) q * dq = (q -q * ) 2 2(q + q * ) W (q * ) q * = (q -q * ) 2 2q * (q + q * ) W (q * ) .
The lemma then follows from the fact that 0 ≤ q , q * ≤ 1.

The second case, q > q * has to be treated a little differently than the first, partly because we now need to upper bound b(q) instead of lower-bounding it. We achieve this by using the concavity of W (proved in Lemma 14).

By concavity of the revenue curve, for any q ≤ q ≤ q * , we have W (q) ≥ q -q q * -q W (q * ) + q * -q q * -q W (q ) , because W lies above the segment that connects (q , W (q )) and (q * , W (q * )), between q and q * . Hence (v -b(q))q ≥ q -q q * -q (v -b(q * ))q * + q * -q q * -q (v -b(q ))q ≥ qv -b(q * )q * q -q q * -q -b(q )q q * -q q * -q , And -qb(q) ≥ q * q (q * -q ) b(q * ) -b(q ) + q q b(q ) -q * b(q * ) q * -q , which yields qb(q) ≤ q * q (q * -q ) b(q ) -b(q * ) + q q * b(q * ) -q b(q ) q * -q ,

Dividing both sides by q, we have b(q) ≤ q * q q(q * -q ) b(q ) -b(q * ) + q * b(q * ) -q b(q ) q * -q ,

Further, by the intermediate value theorem, there exists b ∈ [b(q * ), b(q)], such that

φ F (b(q)) -φ F (b(q * )) = φ F (b) b(q) -b(q * ) ,
for any q * ≤ q ≤ q . Further, by Assumption 1 that dφ F (b) db ≥ 1, and because b is increasing thanks to Assumption 1, for any q ≤ q ≤ q * , φ

F (b(q)) -φ F (b(q * )) ≤ b(q) -b(q * ) and φ F (b(q)) ≤ v + b(q) -b(q * ) = v + b(q) -b(q * ),
Combining with Inequality 2, we get that

φ F (b(q)) ≤ v + q * q q(q * -q ) b(q ) -b(q * ) + q * b(q * ) -q b(q ) q * -q -b(q * ) = v + q (q * -q) q(q * -q ) b(q ) -b(q * ) ≤ v + q (q * -q) q * (q * -q ) b(q ) -b(q * ) ,
where the last inequality is due to q ≤ q * and b(q ) -b(q * ) < 0. Hence, we have

W (q * ) -W (q ) = q * q W (q)dq = q * q v -φ F (b(q))dq ≥ q * q q (q * -q) q * (q * -q ) b(q * ) -b(q ) dq = q 2q * (q * -q ) b(q * ) -b(q ) . (3)
On the other hand, we have W (q * ) -W (q ) = (q * -q )v + q b(q ) -q * b(q * ).

(4)

Taking the linear combination 2q * 3q * -q • 3 + q * -q 3q * -q • 4, we have

W (q * ) -W (q ) ≥ v (q * -q ) 2 3q * -q ) - (q * -q ) 2 3q * -q b(q * ) = 1 q * (3q * -q ) (q * -q ) 2 W (q * ) ≥ 1 3 (q * -q ) 2 W (q * ) ,
where the last inequality holds because 0 ≤ q * , q ≤ 1.

Lemma 7 If Assumption 2 is satisfied, for any

F -1 (b * ) ≤ q ≤ F -1 (b * + ∆) ≤ b * + C f ∆), W (q * ) -W (q ) ≤ 1 c f λ(q * -q ) 2 , Proof W (q * ) -W (q ) = q q * -W (q)dq = q q * φ F (b(q)) -v dq.
by the intermediate value theorem, there exists b ∈ [b(q * ), b(q)], such that

φ F (b(q)) -φ F (b(q * )) = φ F (b) b(q) -b(q * ) ≥ λ(b(q) -b(q * )),
so that φ F (b(q))-v ≤ λ(b(q)-b(q * )) when q * ≤ q ≤ q and φ F (b(q))-v ≥ λ(b(q)-b(q * )) when q ≤ q ≤ q * . Since f is bounded from below by c f , and since by the intermediate value theorem ∃u ∈ [q, q * ], b(q) -b(q * ) = b (u)(q -q * ) ≥ 1 f (u) (q -q * ), this yields

W (q * ) -W (q ) ≤ λ 1 c f (q -q * ) 2
in both cases.

Lemma 15 Beta distributions such that α + β < αβ satisfy Assumption 1.

Proof The density of a Beta distribution satisfies

f (x) = x α-1 (1 -x) β-1 B(α, β)
And

f (x) = (α -1)x α-2 (1 -x) β-1 -(β -1)x α-1 (1 -x) β-2 B(α, β) ,
where B(α, β) = Γ(α+β) Γ(α)Γ(β) when Γ denotes the Gamma function. F satisfies assumption 1 if and only if

f F (x) = F (x)f (x)-f 2 (x) F 2 (x) < 0, ∀x ∈]0, 1[, which is equivalent to: f (x)F (x) -f 2 (x) < 0, ∀x ∈]0, 1[ ⇐⇒ f (x) f (x) F (x) < f (x), ∀x ∈]0, 1[) ⇐⇒ F (x)B(α, β) [(α -1)(1 -x) -(β -1)x] < x α (1 -x) β , ∀x ∈]0, 1[.

Therefore we study the function

G : x → F (x)B(α, β) [(α -1)(1 -x) -(β -1)x] - x α (1 -x) β .
First of all, we observe that G(0) = 0. Next, we note that

G (x) = -F (x)(α + β -2)B(α, β) + ((α -1) -(α + β -2)x)x α-1 (1 -x) β-1
and G (0) = 0. Now, we compute the second derivative of G:

G (x) = -(α + β -2)x α-1 (1 -x) β-1 + ((α -1) -(α + β -2)x)) 2 x α-2 (1 -x) β-2 -(α + β -2)x α-1 (1 -x) β-1 -(α -(α + β)x) ((α -1)- (α + β -2)x)x α-2 (1 -x) β-2 + (α + β)x α-1 (1 -x) β-1
The sign of G (x) is the same as that of P

(x) = -((α + β) -4) (x(1 -x)) + (-1 + 2x) ((α -1) -(α + β -2)x).
By simplifying, we get

P (x) = -(α + β)x 2 + 2αx -(α -1
). This polynomial is always negative because its maximum is

P ( α α+β ) = -α 2 α+β + 2 α 2 α+β -α + 1 = α 2 ( 2 α+β -1) -α + 1 = α 2 α+β -α + 1 = α+β-αβ α+β . Since G (x) < 0, ∀x ∈ [0, 1] and G (0) = 0, then G (x) < 0, ∀x ∈ [0, 1]. Similarly, G (x) < 0, ∀x ∈ [0, 1] and G(0) = 0, implies G (x) < 0, ∀x ∈ [0, 1],
which in turn implies that F satisfies Assumption 1.

A.3. Continuous distribution leading to a utility with two global maximizers

Consider a distribution which cumulative distribution function F is piece-wise linear on [0, v] at least. We consider that it changes slope at a 1 v < v, and that it is constant on [a 2 v, v], as in Figure 8. We denote by b 1 = F (a 1 v) and b 2 = F (a 2 v). For simplicity we assume that F is constant on [a 2 v, a 3 v] it is linear and does not change slope on [a 3 v, 1] with a 3 > 1. We make the following assumptions

a 2 v > v/2, a 2 v ≤ v+a 1 v 2 -a 2 v-a 1 v b 2 -b 1 b 1 2 . (5) Figure 8: Example of F Then • On [0, a 1 v] U v (x) = b 1 a 1 v
x, and the optimum on this interval is v/2. The optimal value on this interval is U

v (v/2) = b 1 a 1 v v 2 4 on this interval. • On [a 1 v, a 2 v], U v (x) = b 2 -b 1 a 2 v-a 1 v (x -a 1 v) + b 1 (v -x), and on this interval, U v (x) = b 2 -b 1 a 2 v-a 1 v (v -2x + a 1 v) -b 1 and U v (x) = 0 ⇐⇒ x = v+a 1 v 2 -a 2 v-a 1 v b 2 -b 1 b 1 2 . The optimizer on this interval is hence a 2 v, if v+a 1 v 2 -a 2 v-a 1 v b 2 -b 1 b 1 2 > a 2 v. Under this condition, the optimal value is U v (a 2 v) = b 2 (v -a 1 v
) on this interval. This can also be extended to the whole interval [a 1 v, v], since U is decreasing after a 2 v.

Setting b 1 a 1 v 4 = b 2 (6)
leads to the utility having two global maximizers, v/2 and a 2 v.

To summarize, the utility's argmax is {v/2, a 2 v} if the set of Equations 5 holds.

We can for example choose :

v = 1/2; a 2 = 15 16 ; a 1 = 29 32 ; b 2 = 128 29 b 1 ; b 1 = 0.5
This choice of parameters satisfies Condition 5 and Condition 6. Figure 9 shows the corresponding utility on [0, v].

T →∞ max v∈[0,1],F ∈C R v,F T √ T ≥ 1 64 ,

Proof

We exhibit a choice of F , and two alternative Bernoulli value distributions Ber(v) and Ber(v ) that are difficult to distinguish but whose difference is large enough so that mistaking one for the other necessarily leads to a regret of the order of √ T when the cumulative distribution function is F .

Let v < 1 and consider a discrete distribution with support v 3 , 2v 3 , 1 such that F ( v 3 ) = A and F ( 2v 3 ) = 2A + 3 ∆ T v , where ∆ T and A are positive constants, that we will fix later on. A maximizer of the utility can only be a point of the support, since U v,F decreases in the intervals where F is constant. It can not be 1, because v < 1. We have

U v,F ( v 3 ) = 2vA 3 and U v,F ( 2v 3 ) = 2vA 3 + ∆ T , while U v,F (
1) ≤ 0. Consequently, when the value is v, the optimum is achieved by bidding 2v 3 and bidding less than 2v 3 yields a regret of at least ∆ T . Now let us consider the alternative situation in which the value is

v = v -δ T , with δ T > 0. We get U v ,F ( v 3 ) = 2Av 3 -δ T A and U v ,F ( 2v 3 ) = 2Av 3 + ∆ T -δ T (2A + 3∆ T v ). When ∆ T < δ T (2A + 3∆ T v )
, the optimal bid is v 3 and the regret incurred by bidding more than 2v 3 is at least δ T (A + 3∆ T v ) -∆ T . By setting ∆ T = Aδ T 2-3δ T /v , we ensure that the regret incurred by bidding on the wrong side of 2v 3 is larger than ∆ T , whether the value is v or v . Further, by setting δ T = v(1 -v)/T , we force the error ∆ T to be of the order of 1/ √ T . We also set A = 1 4 , and v = 1/2. We can prove that ∀T > 16, 2A + 3

∆ T v < 1 ; Indeed, if T > 16 > (11/3) 2 , 4 3 < 2 √ T -6 hence 4 3 √ T < 2 -6 √ T which implies 2 3 1 √ T 2-6 √ T = 6∆ T < 1 2 = 1 -2A.
We denote by P v,F (•) the probability of an event under the first configuration (respectively E v,F (•) the expectation of a random variable under the first configuration), and by P v ,F (•) the probability of an event under the second configuration (respectively E v-δ-T,F (•) the expectation of a random variable under the first configuration). We denote by I t the information collected up to time t + 1 : (M t , V t , . . . M 1 , V 1 ). P It v,F (respectively P It v ) denotes the law of I t in the first (respectively second) configuration.

We consider the Kullback Leibler divergence between P It v,F and P It v ,F . We prove that it is equal to

KL(P It v , P It v ,F ) = kl(v, v )E[N t ], (7)
where kl(•, •) denotes the Kullback Leibler divergence between two Bernoulli distributions. Indeed, thanks to the chain rule for conditional KL,

KL(P It v,F , P It v ,F ) = KL(P It v,F , P It v ,F ) + KL(P (Mt,V t )|It v,F , P (Mt,V t )|It v ,F
),

and

KL(P (Mt,V t )|It v,F , P (Mt,V t )|It v ,F ) = E[E[KL(ν It ⊗ D F , ν It ⊗ D F )|I t ]] = E[kl(v, v )1(B t > M t )].
where ν It (respectively ν It ) denotes the law of V t knowing I t in the first configuration (respectively the second), and D F the law of M t . By induction, we obtain

KL(P It v,F , P It v ,F ) = kl(v, v )E v,F [N t ].
We stress that in either of the former configurations (under (v, F ) or (v , F )), playing on the wrong side of 2 3 v yields a regret larger than ∆ T . Using this, we get that ∀T > 16,

max(R v,F T , R v ,F T ) ≥ 1 2 (R v,F T + R v-δ,F T ) ≥ 1 2 T t=1 ∆ T P v,F B t < 2 3 v + ∆ T P v ,F B t > 2 3 v ≥ 1 2 T t=1 ∆ T P v,F B t < 2 3 v + ∆ T 1 -P v ,F (B t > 2 3 v) ≥ 1 2 T t=1 ∆ T 1 -T V (P It v,F , P It v ,F ) ≥ 1 2 T t=1 ∆ T 1 - 1 2 KL(P It v,F , P It v ,F ) ≥ 1 2 T t=1 ∆ T 1 - 1 2 E v,F [N t ]kl(v, v ) ≥ 1 2 T t=2 ∆ T 1 - 1 2 T kl(v, v )
where we used Pinsker's inequality in the fifth inequality and where T V (•, •) denotes the total variation. Yet, since kl(v, v

) = (v -v) 2 2 1 0 g (v + s(v + s(v -v ))
2(1 -s)ds, where g(x) = kl(x, v ) thanks to Taylor's inequality,

kl(v, v ) ≤ (v -v) 2 2 1 0 2 max u∈[v,v ] g (u)ds ≤ (v -v) 2 1 min u∈[v,v ] u(1 -u) ≤ (v -v) 2 v (1 -v ) , since v = 1 2 . Therefore, max(R v,F T , R v ,F T ) ≥ 1 2 T t=1 ∆ T 1 - 1 2 T kl(v, v ) ≥ 1 2 T t=1 ∆ T 1 - 1 8 1 (1/2 -1 2 √ T )(1/2 + 1 2 √ T ) ≥ 1 2 × Aδ T 2 -3/2δ T T 1 - 1 8 1 (1/2 -1 2 √ T )(1/2 + 1 2 √ T ) ≥ 1 16 -12/ √ T √ T 1 - 1 8 1 (1/2 -1 2 √ T )(1/2 + 1 2 √ T ) Finally lim inf T →∞ max(R v,F T , R v ,F T ) √ T ≥ 1 16 1 - 1 2 ≥ 1 64
Appendix C. Preliminary Results

C.1. Concentration inequalities used for the upper bounds

C.1.1. On the value V t

Lemma 16

The following concentration inequality on the values holds

T t=2 P ( Vt -v) 2 ≥ γ log(t -1) 2N t ≤ T t=1 2e √ γ(log(t))t -γ .
Proof We have, for all η t-1 ,

T t=2 P ( V (N t ) -v) 2 ≥ η t-1 2N t ≤ T t=2 P ∃m : 1 ≤ m ≤ t, 2m( V (m) -v) 2 ≥ η t-1 ≤ T t=1 2e η t-1 log(t -1) exp(-η t-1 ) := l 1 (T )
where the second inequality comes from Lemma 11 in [START_REF] Cappé | Kullback-Leibler upper confidence bounds for optimal sequential allocation[END_REF], and from the fact that V t is a positive random variable bounded by 1, so 1/2-sub-Gaussian. Therefore, if η t := γ log t,

l 1 (T ) = T t=2 2e √ γ(log(t -1))(t -1) -γ
which tends to a finite limit as soon as γ > 1.

C.1.2. On the cumulative distribution function of M t

Lemma 17

The following concentration inequality holds on the empirical cumulative distribution Ft .

T t=2 P Ft -F ∞ ≥ γ log(t -1) 2(t -1) ≤ 2 T t=1 t -γ .
Proof It holds

T t=2 P ( max b∈[0,1] |F t (b) -F (b)|) 2 ≥ γ log(t -1) 2(t -1) ≤ T t=2 P Ft -F 2 ∞ ≥ γ log(t -1) 2(t -1) ≤ T -1 t=1 2e -2γ log(t 2t ≤ T t=1 2t -γ ,
according to the Dvoretzky-Kiefer-Wolfowitz inequality (see [START_REF] Massart | The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality[END_REF]).

Note that this also yields

T t=2 P Ft -F ∞ ≥ γ log(t -1) 2N t ≤ T t=2 P Ft -F ∞ ≥ γ log(t -1) 2(t -1) ≤ 2 T t=1 t -γ .

C.1.3. Local concentration inequality

This lemma is key for the proof of the upper bound of the regret of UCBid1+. It quantifies the variation of Ft on a small interval.

Lemma 12 For any a, b ∈ [0, 1], if F is continuous and increasing, then

sup a≤x≤b | Ft (x) -F (x) -( Ft (a) -F (a))| ≤ 2(F (b) -F (a)) log e √ t √ 2(F (b)-F (a))η t + log( t 2(F (b)-F (a)η 2 ) 6t , (8)
with probability 1 -η Remark : it follows from the lemma that the the maximal gap between Ft (x) -F (x) and Ft ( a+b 2 ) -F ( a+b 2 ) can easily be bounded by :

sup a≤x≤b | Ft (x) -F (x) -( Ft ( a + b 2 ) -F ( a + b 2 ))| ≤ 2 2(F (b) -F (a)) log e √ t √ 2η(F (b)-F (a)) t + 2 log( t 2(F (b)-F (a)η 2 ) 6t
with probability 1 -η.

Proof : Let X 1 , . . . , X n iid ∼ dF . Let m > 2 For every 1 ≤ i ≤ m, let x i be such that F (x i ) = F (a) + i m F (b) -F (a)
.

By Bernstein's inequality, since t Ft (x i ) -Ft (a) ∼ B(n, F (x i ) -F (a)
) has a variance bounded by t F (b) -F (a)), there is an event A of probability at least 1 -me -z on which

max 0≤i≤m Ft (x i ) -Ft (a) -(F (x i ) -F (a)) ≤ 2 F (b) -F (a) z t + z 3t := δ, by a union bound. Besides, for i = 0, Ft (x i ) -Ft (a) -(F (x i ) -F (a)) = 0.
On this event, for every

x i-1 ≤ x ≤ x i : Ft (x) -Ft (a) -(F (x) -F (a)) ≤ Ft (x i ) -Ft (a) -(F (x i ) -F (a)) + F (x i ) -F (x) ≤ δ + 1 m , Ft (x) -Ft (a) -(F (x) -F (a)) ≥ Ft (x i-1 ) -Ft (a) -(F (x i-1 ) -F (a)) + F (x i-1 ) -F (x) ≥ -δ - 1 m .
and hence

sup a≤t≤b Ft (x) -Ft (a) -(F (x) -F (a)) ≤ 2 F (b) -F (a) z t + z 3t + 1 m . Now, take m = t 2 F (b) -F (a)
and z = log(m/η): one gets that with probability at least 1 -η,

sup a≤t≤b Ft (x) -Ft (a) -(F (x) -F (a)) ≤ 2 F (b) -F (a) log t 2(F (b)-F (a)) η t + log t 2(F (b)-F (a)) η 3t + 2 F (b) -F (a) t ≤ 2 F (b) -F (a) log e √ t √ 2(F (b)-F (a))η t + log t 2(F (b)-F (a))η 2 6t .

C.2. General bound on the instantaneous regret

In the following, we will repeatedly use the following general bound on the instantaneous regret conditioned on the and on a current victory.

Lemma 18 Let A be an

F t-1 -measurable event. Let S t denote (V t -b * )1(M t < b * ) -(V t - B t )1(M t < B t ).
The following inequality holds:

E [S t 1(B t > b * )1(A)|F t-1 ∨ σ(1(B t > M t ))] ≤ U (b * ) -U (B t ) F (b * ) 1(M t ≤ B t )1(A).
Proof When B t > b * , the instantaneous regret can be decomposed as follows

S t 1(B t > b * ) = (B t -v)1(M t ≤ b * )1(B t > b * ) + (B t -b * )1 {(M t ≤ b * ≤ B t )} . (9)
Note that in particular, there is no instantaneous regret when M t > B t . Therefore

E [S t 1(B t > b * )1(A)|F t-1 ∨ 1(B t > M t )] ≤ (B t -b * )F (b * ) + (B t -v)(F (B t ) -F (b * )) F (B t ) 1(M t ≤ B t )1(B t > b * )1(A) ≤ U (b * ) -U (B t ) F (b * ) 1(M t ≤ B t )1(A), since U (b * ) -U (B t ) = (v -b * )F (b * ) -(v -B t )F (B t ), which also equals (B t -b * )F (b * ) + (B t -v)(F (B t ) -F (b * )).

C.3. Other lemmas Lemma 19

The expectations E T t=2

1

Nt 1{M t ≤ B t } and E T t=2 1 Nt 1{M t ≤ B t } can always be bounded as follows    E T t=2 1 Nt 1{M t ≤ B t } ≤ 1 + log T, E T t=2 1 Nt 1{M t ≤ B t } ≤ 1 + √ T .
Proof Since winning an auction increments the number of observations N t by 1,

T t=2 E 1 N t 1(M t ≤ B t ) ≤ T t=2 T -1 n=1 1 n 1{N t = n, N t+1 = n + 1} ≤ T -1 n=1 1 n T t=2 1{N t = n, N t = n + 1} ≤ T -1 n=1 1 n ≤ 1 + T -1 n=2 n n-1 1 u du ≤ 1 + √ T .
Similarly, we get

T t=2 E 1 N t 1(M t ≤ B t ) ≤ T t=2 T -1 n=1 1 n 1{N t = n, N t+1 = n + 1} ≤ T -1 n=1 1 n T t=2 1{N t = n, N t = n + 1} ≤ T -1 n=1 1 n ≤ 1 + T -1 n=2 n n-1 1 u du ≤ 1 + log T.
Lemma 20 If g 1 and g 2 are two functions such that g 1 -g 2 ∞ ≤ δ, then

g 1 (b * 1 ) -g 1 (b * 2 ) ≤ 2δ where b * 1 = max(arg max b∈[0,1] g 1 (b)) and b * 2 = max(arg max b∈[0,1] g 2 (b)). Proof Indeed, 0 ≤ g 1 (b * 1 ) -g 1 (b * 2 ) ≤ g 1 (b * 1 ) -g 2 (b * 2 ) + g 2 (b * 2 ) -g 1 (b * 2 ) ≤ 2δ.
Lemma 21 For any a > 0, t ≥ 2a log(a) implies t ≥ a log t.

Proof

a log t ≥ a t 2a + log(2a) ≥ t/2 + a log(a),
where the first inequality follows from the fact that log(x/y) ≤ x/y for any positive x and y. Hence when t > 2a log(a), t ≥ t/2 + a log t ≥ a log t.

Appendix D. Known F

D.1. Upper Bounds of the Regret of UCBid1

We prove the somewhat more precise form of Theorem 8.

Theorem 8 UCBid1 incurs a regret bounded as follows

R T ≤ 1 F (b * ) γ log T ( √ T + 1) + O(1). Proof We denote by U U CBid1 t the function b → ( Vt + t -b)F (b)
. The regret can be decomposed as follows.

R T ≤ 1 + T t=2 P | Vt -v| ≥ t + T t=2 E S t 1 | Vt -v| ≤ t ,
Lemma 16 yields the following bound on the probability of over-estimating Vt :

T t=2 P(| Vt -v| ≥ t ) ≤ t t=1 2e √ γ(log t)t -γ . Since F (x) ≤ 1, ∀x ∈ [0, 1], and U U CBid1 t -U ∞ = ( Vt -v + t )F (x) ∞ ≤ | Vt -v + t |,
we can bound the difference between the utility function and its (upper confidence) estimate with high probability:

T t=2 P( U U CBid1 t -U ∞ ≥ 2 t ) ≤ T t=1 2e √ γ(log t)t -γ . When U U CBid1 t -U ∞ ≤ 2 t , then |U (b * ) -U (B t )| ≤ 4 t , thanks to Lemma 20. Additionally, using Lemma 1, if Vt + t -v ≥ 0 , then B t ≥ b * Therefore, T t=2 1 F (b * ) E S t 1 {M t ≤ B t } 1 {b * ≤ B t } 1 | Vt -v| ≤ t ≤ T t=2 E U (b * ) -U (B t ) F (b * ) 1 {b * ≤ B t } 1 {M t ≤ B t } 1 | Vt -v| ≤ t ≤ T t=2 E U (b * ) -U (B t ) F (b * ) 1 {b * ≤ B t } 1 {M t ≤ B t } 1 {U (b * ) -U (B t ) ≤ 4 t } ≤ T t=2 1 F (b * ) E [4 t 1 {M t ≤ B t } 1 {(U (b * ) -U (B t ) ≤ 4 t }] ≤ T t=2 1 F (b * ) 2 γ log T N t ≤ 1 F (b * ) 2γ log T (1 + √ T ),
where the second inequality comes from Lemma 18 (in fact | Vt -v| ≤ t is F t-1 -measurable) and the last inequality comes from Lemma 19. Using Lemma 16 yields

T t=2 P(| Vt -v| ≥ t ) ≤ T t=1 2e √ γ(log t)t -γ .
Combining this with the above decomposition of the regret yields

R T ≤ 1 + T t=1 2e √ γ(log t)t -γ + 1 F (b * ) 2 log T (1 + √ T ), When γ > 1, T t=1 2e
√ γ(log t)t -γ tends to a constant, and

R T ≤ 1 F (b * ) 2γ log T (1 + √ T ) + O(1),
which concludes the proof.

Theorem 9 If F satisfies Assumption 1 and 2, then

R T ≤ 2γλC 2 f F (b * )c f log 2 (T ) + O(log T ), when γ > 1. Fast Rate Learning in Stochastic First Price Bidding Proof Thanks to Lemma 1, if Vt + t -v ≥ 0 , then B t ≥ b * . Additionally, B t -b * ≤ ( Vt + t -v), thanks to Lemma 4. In particular, if Vt + t -v < 2 t , B t -b * ≤ 2 t .
The regret can therefore be decomposed as follows :

R T ≤ 1 + T t=2 P( Vt + t -v ≤ 0) + T t=2 P( Vt -t -v ≥ 0) + E T t=2 S t 1(B t ∈ [b * , b * + min(2 t , ∆)] + T t=2 E [S t 1(B t ∈ [b * + min(2 t , ∆), b * + ∆])] (10)
Let us bound the third term of this inequality. Thanks to Lemma 18 ,

E [S t 1(B t ∈ [b * , b * + t ])|F t-1 ∨ σ(1 {M t ≤ B t })] ≤ U (b * ) -U (B t ) F (b * ) × 1 {M t ≤ B t } 1 {b * ≤ B t ≤ b * + 2 t } , (11) because
(B t ∈ [b * , b * + t ]) is F t-1 -measurable. This is why T t=2 E [E [S t 1(B t ∈ [b * , b * + min(2 t , ∆])|F t-1 ∨ σ({1 {M t ≤ B t })}]] ≤ T t=2 E U (b * ) -U (B t ) F (b * ) × 1 {M t ≤ B t } 1 {b * ≤ B t ≤ b * + min(2 t , ∆} ≤ T t=2 E W (q * ) -W (Q t ) F (b * ) × 1 {M t ≤ B t } 1 {q * ≤ Q t ≤ b * + 2C f t } ≤ T t=2 E λ(q * -Q t ) 2 c f F (b * ) × 1 {M t ≤ B t } 1 {q * ≤ Q t ≤ b * + 2C f t } ≤ E λ(2C f ) 2 c f F (b * ) T t=2 γ log T 2N t 1 {M t ≤ B t } ≤ 2λγ Cf c f F (b * ) log T (log T + 1),
where the third inequality comes from Lemma 7 and the last one follows from Lemma 19. Thanks to Lemma 16, the sum of the first term and the second term of Equation ( 10) can be bounded by

T t=2 P( Vt -v < t ) + T t=2 P( Vt -t -v ≥ 0) ≤ T t=1 e √ γ log t t γ which is bounded by a constant when γ > 1.
The last term of Equation ( 10) can be bounded as follows:

T t=2 E [S t 1(B t ∈ [b * + min(2 t , ∆), b * + ∆])] ≤ T t=2 P [(∆ > 4 t , M t ≤ B t , B t > b * ] ≤ T t=2 P ∆ 2 > 4 γ log T 2N t , M t ≤ B t , B t > b * ≤ T t=2 T -1 n=1 P ∆ 2 > 2 γ log T 2N t 1 [N t = n, N t+1 = n + 1] ≤ T -1 n=1 1 n < 4 γ log T 2∆ 2 T t=2 1 {N t = n, N t+1 = n + 1} ≤ T -1 n=1 1 n < 4 γ log T 2∆ 2 ≤ 4 γ log T 2∆ 2
where the first inequality comes from the fact that when B t > b * , a positive instantaneous regret can only occur if M t ≤ B t . By summing all components of the regret,

R T ≤ 1 + 4 γ log T 2∆ 2 + 2γλC 2 f F (b * )c f (log 2 (T ) + log T ).
In conclusion,

R T ≤ 2γλC 2 f F (b * )c f log 2 (T ) + O(log T )
when γ > 1.

D.2. Lower bound of the regret of optimistic strategies

Lemma 10 Consider all environments where V t follows a Bernoulli distribution with expectation v and F satisfies Assumption 1 and is such that φ ≤ λ, and there exists c f and

C f such that 0 < c f < f (b) < C f , ∀b ∈ [0, 1]. If a strategy is such that, for all such envi- ronments, R v,F T ≤ O(T a )
, for all a > 0, and there exists γ > 0 such that P(B t < b * ) < t -γ , then this strategy must satisfy:

lim inf T →∞ R v,F T log T ≥ c 2 f λ 2 v(1 -v)(v -b * v,F ) 32 .
Note that this proof is an adaptation of the proof of the parametric lower bound of [START_REF] Achddou | Efficient algorithms for stochastic repeated second-price auctions[END_REF].

Lemma 22 If R T ≤ O(T a ), ∀a > 0, and F admits a density which is lower bounded by a positive constant and upper bounded. Then,

lim t→∞ E N t t = F (b * ).
Proof The fraction of won auctions is

E Nt t = E[ 1 t t s=1 F (B s ]
, by the tower rule. Since F admits a density f , upper bounded by a constant C f ,

E[(F (B t ) -F (b * )) 2 ]] ≤ C 2 f E[(B t -b * ) 2 ]. The consistency assumption implies T t=1 E[(B t -b * ) 2 ] ≤ O(T a
), ∀a > 0, because of Lemma 6. In particular lim t→∞ E[(B t -b * ) 2 ] = 0. Combining the two previous arguments yields

lim t→∞ E[(F (B t ) -F (b * )) 2 ] = 0. Then, because L 2 -convergence implies L 1 -convergence, lim t→∞ E[F (B t )] = F (b * ).
Together with the equality

E Nt t = E[ 1 t t s=1 F (B s )],
and with the Cesaro theorem, this result proves suffices to prove the lemma.

We set a time step t ∈ [1, T ]. We consider two alternative configurations with identical distributions for M t but that differ by the distribution of V t . The value V t is distributed according to a Bernoulli distribution of expectation v in the first configuration, respectively

v t = v + v(1-v)
F (b * )t , in the second configuration. Notation. We let P v (•) denote the probability of an event under the first configuration (respectively E v (•) the expectation of a random variable under the first configuration), whereas P v t (•) denotes the probability of an event under the second configuration (respectively E v t (•) the expectation of a random variable under the first configuration). The information collected up to time t + 1 is denoted I t : (M t , V t , . . . M 1 , V 1 ). Finally, P It v (respectively

P It v t
) is the law of I t in the first (respectively second) configuration.

The Kullback Leibler divergence between P It v and P It v t can be proved to satisfy

KL(P It v , P It v t ) = kl(v, v t )E[N t ],
exactly like in Equation 7. Using Lemma 22, ∀ > 0, ∃t 1 ( ), ∀t ≥ t 1 ( ),

KL(P It v , P It v t ) ≤ kl(v, v t )(1 + )F (b * ).
Using the data processing inequality (see for example Garivier et al. ( 2019)), we get

KL(P It v , P It v t ) ≥ kl P v B t > b * v,F + b * v t ,F 2 , P v t B t > v + b * v t ,F 2
≥ 2 P v B t > b * v,F + b * v t ,F 2 -P v t B t > b * v,F + b * v t ,F 2 2 ≥ 2 P v B t > b * v,F + b * v t ,F 2 + P v t B t ≤ b * v,F + b * v t ,F 2 -1 2 ,
where the second inequality comes from Pinsker inequality. Consequently, we get

P v B t > b * v,F + b * v t ,F 2 + P v t B t ≤ b * v,F + b * v t ,F 2 ≥ 1 - 1 2 KL(P It v , P It v t ).
Specifically, ∀t > t 0 ( ),

P v B t > b * v,F + b * v t ,F 2 + P v t B t ≤ b * v,F + b * v t ,F 2 ≥ 1 - 1 2 kl(v, v t )(1 + )F (b * v,F )t.
Using the fact that

E v [(B t -b * v,F ) 2 ] ≥ b * v,F - b * v,F +b * v t ,F 2 2 P v B t > b * v,F +b * v t ,F 2 yields E v [(B t -b * v,F ) 2 ] ≥ b * v,F -b * v t ,F 2 2 P v B t > b * v,F + b * v t ,F 2 ≥ λ v -v t 2 2 P v B t > b * v,F + b * v t ,F 2 ≥ λ 2 v(1 -v) 4F (b * v,F )t 1 - 1 2 (1 + )kl(v, v t )F (b * v,F )t -1/t γ ,
where the second inequality comes from the fact that

v = φ F (b * v,F ) (resp. v t = φ F (b * v t ,F
)) and that φ F ≤ λ and the the second inequality stems from the assumption that the algorithm outputs a bid that does not underestimate b * v t ,F with high probability:

P v t (B t < b * v t ,F ) < 1 t γ .
We use the fact that ∀ > 0, ∃t 2 (v, ), ∀t ≥ t 2 (v, ), kl v, v

+ v(1-v) F (b * v,F )t ≤ 1+ 2F (b * v,F )t
which is proved by observing that kl(v, v ) = (v -v) 2 2 1 0 g (v + s(v + s(v -v ))2(1 -s)ds, where g(x) = kl(x, v ); and that thanks to Taylor's inequality,

kl(v, v ) ≤ (v -v) 2 2 1 0 2 max u∈[v,v ] g (u)ds ≤ (v -v) 2 1 min u∈[v,v ] u(1 -u) and that ∀ > 0, ∃t 2 (v, ), such that min u∈[v,v ] u(1 -u) < 1+ v(1-v)
. Putting all the pieces together yields ∀t ≥ max(t 1 ( ), t 2 (v, )),

E v [(B t -b * v,F ) 2 ] ≥ v(1 -v) 4F (b * v,F )t 1 - 1 4 (1 + ) 2 -1/t γ .
Let t 0 (v, ) = max(t 1 ( ), t 2 (v, )). We obtain

T t=1 E v [(B t -b * v,F ) 2 ] ≥ T t=t 0 (v, ) λ 2 v(1 -v) 4F (b * v,F )t 1 - 1 2 (1 + ) -1/t γ .
Recall that, according to Lemma 6,

R T (v) = T t=1 E U (b * v,F ) -U (B t ) ≥ U (b * v,F ) 4 T t=1 E v [(Q t -q * ) 2 ] ≥ c 2 f U (b * v,F ) 4 T t=1 E v [(B t -b * v,F ) 2 ].
Hence, ∀ > 0,

R T (v) ≥ λ 2 c 2 f U (b * v,F ) 4 v(1 -v) 4 1 - 1 2 (1 + ) log T t 0 (v, )
-O(1).

And ∀ > 0, lim inf

T →∞ R T (v) log T ≥ c 2 f λ 2 U (b * v,F ) 4 v(1 -v) 4F (b * v,F ) 1 - 1 2 (1 + ) .
Since this holds for all , lim inf

T →∞ R T (v) log T ≥ λ 2 c 2 f v(1 -v)(v -b * v,F ) 32 .
Next we observe that if F and v lie in their confidence regions F t and V t , then Ût -

U ∞ ≤ 2 t . (Recall that Ût (b) = ( Vt -b) Ft (b).) Indeed, we have Ût (b) -U (b) = ( Vt -b) Ft (b) -(v -b)F (b) = ( Vt -v)F (b) + Vt ( Ft (b) -F (b)) + b(F (b) -Fb ) = ( Vt -v)F (b) + ( Vt -b)( Ft (b) -F (b)) which yields | Ût (b) -U (b)| ≤ | Vt -v| + F (b) -Ft (b) ∞ . ( 12
)
We then decompose the regret into

E(R T ) = T t=1 E(U (b * ) -U (B t )) ≤ 1 + T t= P(F / ∈ F t or v / ∈ V t ) + T t=2 E S t 1(B t > b * )1( Ût -U ∞ ≤ 2 t , F ∈ F t , v ∈ V t . (13)
The second term of the second hand side of Equation 13 is easily bounded thanks to the concentration inequalities in Lemmas 16 and 17. In fact, combining these latter lemmas yields the following bound.

Lemma 25

T t=2 P(F / ∈ F t or v / ∈ V t ) ≤ 2 T t=1 2e √ γ(log t)t -γ
We apply Lemma 18 to bound the third term of the second hand side of Equation 13 as follows:

E ]S t 1(B t > b * )1( Ût -U ∞ ≤ 2 t , F ∈ F t , v ∈ V t ) ≤ 1 F (b * ) E U (b * ) -U (B t )) × 1(M t ≤ B t )1( U -Ût ∞ ≤ 2 t , F ∈ F t , v ∈ V t )1(B t > b * ) , (14)
because

1(B t > b * )1( Ût -U ∞ ≤ 2 t , F ∈ F t , v ∈ V t ) is F t-1 -measurable. We then bound the deviation (U (b * ) -U (B t ))1(M t ≤ B t
) by 8 t by using Lemma 20.

Lemma 26 When applying the O-UCBid1 strategy, if U -Ût ∞ ≤ 2 t , then Then, by summing, we get

|U (B t ) -U (b * )| ≤ 8 t . Proof Assume U -Ût ∞ ≤ 2 t . Note that Ût (B t )-Ût (b * ) = Ût (B t )
T t=2 E ]S t 1(B t > b * )1( Ût -U ∞ ≤ 2 t , F ∈ F t , v ∈ V t ) ≤ T t=2 1 F (b * ) E U (b * ) -U (B t )) × 1(M t ≤ B t )1(B t > b * )1( U -Ût ∞ ≤ 2 t , F ∈ F t , v ∈ V t ) ≤ T t=2 1 F (b * ) E 8 t × 1(M t ≤ B t )1( U -Ût ∞ ≤ 2 t )1(B t > b * ) ≤ T t=2 1 F (b * ) E 8 log T 2N t 1(M t ≤ B t ) ≤ 1 F (b * ) 4 2 log T ( √ T + 1),
where the last inequality comes from Lemma 19. Using Equation 13and Lemma 25 yields

R T ≤ 1 F (b * ) 4 2 log T ( √ T + 1) + T t=2 2e √ γ(log t)t -γ .
Consequently, when γ > 1,

R T ≤ 1 F (b * ) 4 2 log T ( √ T + 1) + O(1).

E.2. General Upper Bound of the Regret of UCBid1+

We prove a slightly different version of Theorem 2 than that of the main paper.

Theorem 2 UCBid1+ incurs a regret bounded by

R T ≤ 12 γα F (b * ) log T √ T + O(log T ) ≤ 12 1 U (b * ) √ vγ log T √ T + O(log T ), where α := v v-b * , provided that γ > 2.
Proof We denote by E the event {∀t

0 < t < T, | Vt -v| ≤ t , F -Ft ∞ ≤ γ log(t-1) 2(t-1) }, where t 0 := min(3, 1 + 8 γ(α+1) 2 α(F (b * )) 2 log 4 γ(α+1) 2 α(F (b * )) 2
). Using Lemmas 16 and 17, this event happens with high probability, when γ > 2.

Lemma 27 The probability of the complementary of E is bounded as follows

P E C ≤ 4e(γ -1)(log T )(T ) 1-γ .
provided that γ > 2.

Proof

We have

P ∃t ∈ [t 0 , T ], ( V (N t ) -v) 2 ≥ γ log(t -1) 2N t ≤ P ∃t ∈ [2, T ], ( V (N t ) -v) 2 ≥ γ log(t -1) 2N t ≤ T t=2 P ( V (N t ) -v) 2 ≥ γ log(t -1) 2N t , ≤ T t=1 2e log(t)t -γ ≤ T u=1 2e log(t)u -γ du ≤ 2e(γ -1) log(T )(T ) 1-γ ,
thanks to Lemma 16. Similarly,

P   ∃t ∈ [t 0 , T ], F -F ∞ ≥ γ log(t -1) 2N t   ≤ T t=t 0 P   F -F ∞ ≥ γ log(t -1) 2N t   ≤ 2 T t=t 0 t -γ ≤ T u=2 2u -γ du ≤ 2(γ -1)(T ) 1-γ
thanks to Lemma 17.

When E occurs, it is possible to prove that F (B t ) is lower-bounded by a positive constant as soon as t is large enough.

Lemma 28 On E, provided that t > t 0 := min 3, 1 + 8 γ(α+1) 2 α(F (b * )) 2 log 4 γ(α+1) 2 α(F (b * )) 2 , F (B t ) is lower bounded by F (B t ) > F (b * ) 2α , where α = v v-b * . Proof b * = α-1 α v. Since we are on E, b * ≤ α -1 α ( Vt + t ).
Proof Indeed if t ≥ t 0 , then N t is larger than the sum N t of t -t 0 samples from a Bernoulli distribution with average 1 2α F (b * ) , hence the probability that N t < 1 4α F (b * )(t-t 0 ) intersected with E can be bounded as follows.

P N t < 1 4α F (b * )(t -t 0 ), E ≤ P N t < + 1 4α F (b * )(t -t 0 ) ≤ P 1 2α F (b * )(t -t 0 ) -(N t -t 0 ) > 1 4α F (b * )(t -t 0 ) ≤ exp - 2(( 1 2α F (b * )) 2 4 (t -t 0 ) ≤ exp - 2(( 1 2α F (b * )) 2 4 (t -t 0 ) ,
where we used Hoeffding's inequality for the third inequality.

Finally, we can prove that the expected instantaneous regret conditioned on B t is bounded by a multiple of t .

Lemma 30

U (B t ) -U (b * ) ≤ 6 t

Proof

Thanks to Equation 12, we have Ût -U ∞ ≤ 2 t . Very similarly we have

U U CBid1+ t -Û ∞ = max b∈[0,1] | t Ft (b)| ≤ t , where U U CBid1+ : b → ( Vt + t -b) Ft (b). Hence, U U CBid1+ t -U ∞ ≤ 3 t .
By Lemma 20, this yields

U (B t ) -U (b * ) ≤ 6 t
Proof of the Theorem We use the following decomposition

R T ≤ T × P(E c ) + T t=1 E[S t 1{E}] ≤ T × P(E c ) + t 0 + T t=t 0 E[S t 1{E}]
Thanks to Lemma 28, and when t > t 0 , F (B t ) ≥ 1 2α F (b * ). Using this, we get N t > 1 4α F (b * )(t -t 0 ), ∀t > t 0 with high probability.

Thanks to Lemma 29,

E[S t 1{E}] ≤ exp - 2(( 1 2α F (b * )) 2 4 (t -t 0 ) + E S t 1{N t ≥ 1 4α F (b * )(t -t 0 )} ≤ exp - 2(( 1 2α F (b * )) 2 4 (t -t 0 ) + E 6 4αγ log T F (b * )(t -t 0 ) 1{N t ≥ 1 4α F (b * )(t -t 0 )} ;
By summing,

T t=t 0 E[S t 1{E}] ≤ T t=t 0 exp - 2(( 1 2α F (b * )) 2 4 (t -t 0 ) + T t=t 0 6 4αγ log T F (b * )(t -t 0 ) ≤ 1 1 -exp(- 2( 1 2α F (b * )) 2 4 ) + 6 4αγ F (b * ) log T √ T ≤ 4 1 2α F (b * ) + 6 4αγ F (b * ) log T ( √ T ),
where the last inequality comes from 1 -exp(-u) ≥ 2/u, for any positive u. Using the decomposition of the regret yields

R T ≤ t 0 + T P(E C ) + 4 1 2α F (b * ) + 6 4α F (b * ) log T √ T ≤ 4 + 8 γ(α + 1) 2 α(F (b * )) 2 log 4 γ(α + 1) 2 α(F (b * )) 2 + 4e(γ -1) log T (T ) 2-γ + 8α F (b * ) + 12 αγ F (b * ) log T √ T ≤ 4 + 8α F (b * ) + 8 γ(α + 1) 2 α(F (b * )) 2 log 4 γ(α + 1) 2 α(F (b * )) 2 + 4e(γ -1) log T + 12 αγ F (b * ) log T ( √ T ),
which concludes the proof.

E.3. Proof of an Intermediary Regret Rate under Assumptions 1 and 2

In this section, we prove an easier version of Theorem 13. We will use lemmas of the previous subsection for this version as well as for the more complex version. In particular we have already proven that E ∩ {N t ≥ 1 4α F (b * )t}, occurs with high probability. Under Assumptions 1 and 2 and on this event, we prove the following result.

Lemma 31 Under Assumptions 1 and 2 and if t > max(t 0 , t 1 ),

• F -Ft ∞ ≤ + t and |v -Vt | ≤ + t , • |U (b * ) -U (B t )| ≤ 6 + t • |b * -B t | ≤ ∆, • |b * -B t | ≤ 1/ √ c U 6 + t . • |U (b * ) -U (B t )| ≤ C U (b * -B t ) 2 on E ∩ {N t ≥ 1 4α F (b * )t}, where                    t 0 = min 3, 1 + 8 γ(α+1) 2 α(F (b * )) 2 log 4 γ(α+1) 2 α(F (b * )) 2 t 1 = 2 √ C u ∆ 1/4 γα F (b * ) log T, + t = 2αγ log t F (b * )t , c U = c f 1 4 U (b * ), C U = C f c f λ. Proof On the event E ∩ {N t ≥ 1 4α F (b * )t}, F -Ft ∞ ≤ + t and
(b * ) -U (b) ≤ min(U (b * ) -U (b * -∆), U (b * ) -U (b * + ∆)), then b ∈ [b * -∆, b * + ∆].
It follows that if

6 + t ≤ min(U (b * ) -U (b * -∆), U (b * ) -U (b * + ∆)) and therefore 6 + t ≤ C u ∆ where C u := λC f /c f (see Lemma 7), then |b * -B t | ≤ ∆ on E ∩ {N t ≥ 1 4α F (b * )t}. Then, for all t > 2 √ c u ∆ 1/4 γα F (b * ) log T := t 1 , we have |B t -b * | ≤ ∆ on E ∩ {N t ≥ 1 4α F (b * )t}. Under Assumption 1, for any q ∈ [0, 1], W v,F (q * v,F ) -W v,F (q) ≥ 1 4 (q * v,F -q) 2 W v,F (q * v,F ). We have U = W •F , so that if t > t 1 , then B t ∈ [b * -∆, b * +∆] and U (b * )-U (B t ) ≥ c f 1 4 (b * - B t ) 2 U (b * ) := c U (b * -B t ) 2 . In this case, we can also prove that |b * -B t | ≤ 1/ √ c U 6 + t , under E ∩ {N t ≥ 1 4α F (b * )t}.
Proposition 32 Under Assumptions 1 and 2 and if t > max(t 0 , t 1 ),

δ t < ∆ , |B t -b * | ≤ δ t , and + t ≤ M δ t , Then |B t -b * | 2 ≤ 6 c U C f δ t log M e 2 t √ 2t 2c f η 2 t + 2 log( M t √ 2t 2c f η 2 ) c U t + 2 c U (2C f + 1)δ t 2αγ log T F (b * )t , with probability 1 -η on E ∩ {N t ≥ 1 4α F (b * )t}. Proof It is clear from Lemma 12 that sup b * -δt≤b≤b * +δt | Ft (b)-F (b)-( Ft (b * )-F (b * ))| ≤ 2 2C f δ t log e √ t √ 2c f δtη t +2 log( t 2c f δtη 2 ) 6t := β t ,
with probability 1-η. We can also decompose U (b)-U U CBid1+ Then , by definition of γ t and β t : , and η = 1 t . We use the general fact that log(At α ) ≤ 2α log t as soon as t α > A, for all A, a > 0, to derive the following two inequalities : where

(B t -b * ) 2 ≤ 6 c U C f δ
∀t ≥ M e 2 2c f 1 4 , 6 c U C f δ t log M
                   t 0 = min 3, 1 + 8 γ(α+1) 2 α(F (b * )) 2 log 4 γ(α+1) 2 α(F (b * )) 2 t 1 = 2 √ C u ∆ 1/4 γα F (b * ) log T, t 2 = max( √ c U e 2 2c f √ 6 1 4 , ( √ c U 2c f √ 6 ) 1 4 ) = ( √ c U e 2

E.4. Proof of Theorem 13

Theorem 33 is proved by applying Proposition 32 once. By iterating the argument, we can actually achieve a regret of the order of T a , for any a > 1 3 . The proof involves an induction argument. The following lemma is the main element of the proof of the induction.

Proof

We use Proposition 32, and the fact that

+ t ≤ 2αγ/F (b * ) log t t -u k ≤ 2αγ/F (b * )δ (k) t to prove that |B t -b * | 2 ≤ 6 c U C f δ (k) t log M e 2 t √ 2tK 2 t 2 2c f t + 2 log( M K 2 t 2 t √ 2t 2c f ) c U t + 2 c U (2C f +1)δ (k) t 2αγ log t F (b * )t ,
with probability (1 -η (k) )(1 -1 Kt ) and with M = 2αγ/F (b * )

We use the general fact that log(At α ) ≤ 2α log t as soon as t α > A, for all A, a > 0, to derive the following two inequalities : suffices to complete the induction.

∀t ≥ M e 2 K 2 2c f 1 4 , 6 c U C f δ (k) t log M e 2 t
We recall Theorem 13.

Theorem 13 Under Assumptions 1 and 2, R T ≤ O(T 1/3+ ),

for any > 0 as long as γ > 2.

We choose K such that 1 3 + 2 3×4 K + 2 4 K+1 < 1 3 + . (We can choose K = log 4 3 14 1 ) + 1 for example). Then, thanks to proposition 35, for all t > t 3 , on E ∩ {N t ≥ 1 4α F (b * )t},

|B t -b * | ≤ C (0) C 1 3 log(t)t -1 3 + 1 3×4 K + 1 4 K+1 ,
with probability 1 -1 t . We can therefore do the same decomposition as in the proof of Theorem 33.

Figure 1 :

 1 Figure 1: An example with two maximizers

Figure 2 :

 2 Figure 2: Local behavior of the empirical CDF

Figure 3 :

 3 Figure 3: Two choices of F ; associated utilities for v = 1/2.

  Figure 4: Regret plots for known F

Figure 6 :

 6 Figure 6: An example with discrete bids

Figure 7 :

 7 Figure 7: Experiment with real bidding data

Figure 9 :

 9 Figure 9: Associated Utility with two maximizers

  -Ût ( b)+ Ût ( b)-Ût (b * ), where b = max arg max b∈[0,1] ( Vt -b) Ft (b). By design , we have Ût (B t ) -Ût ( b) = -2 t . Thanks to Lemma 20, and because U -Ût ∞ ≤ 2 t we know that 0 ≤ Ût ( b) -Ût (b * ) ≤ 4 t . This yields | Ût (B t ) -Ût (b * )| ≤ 4 t . Finally |U (B t ) -U (b * )| ≤ 8 t .

  ) -U (b * )) = (v -b)F (b) -( Vt + t -b) Ft (b) -(v -b * )F (b * ) -( Vt + t -b * ) F * t (b) = (v -b)F (b) -(v -b) Ft (b) -(v -b * )F (b * ) -(v -b * ) F * t (b) -( Vt + t -v) Ft (b) -Ft (b * ) = (v -b * ) F (b) -Ft (b) -F (b * ) -F * t (b) -( Vt + t -v) Ft (b) -Ft (b * ) + (b * -b)( F (b) -Ft (b)) which in turn proves that |U (b) -U U CBid1+ t (b) -(U U CBid1+ t (b * ) -U (b * ))| ≤ β t + 2 t | Ft (b) -Ft (b * )| + δ t | Ft (b) -Ft (b)|

+t

  := γ t , for all b in [b * -δ t , b * + δ t ]. Now, we know that U (b * ) -U (b) is lower bounded by c U (b * -b) 2 , on this interval and U U CBid1+ t (b) -U (b) + U U CBid1+ t (b * ) -U (b * ) ∞ ≤ γ t on [b * -δ t , b * + δ t ]. We call G the shifted version of U defined by G(b) = U (b) + U U CBid1+ t (b * ) -U (b * ). Its argmax is b * and G(b * ) -G(b) is lower bounded by c U (b * -b) 2 then c U (B t -b * ) 2 ≤ G(b * ) -G(B t ) ≤ 2γ t (see Lemma 20).

Lemma 34

 34 Assume that t and F satisfy the assumptions of Proposition 32. Assume that|B t -b * | is bounded by δ C (k) log(t)t -u k ) with probability 1η (k) , and u k < 2/3, C (k) ≥ 1 . Then |B t -b * | is bounded by δ C (k+1) log(t)t -1 4 (1+u k ) ) with probability 1 -η (k) -1Kt , where C (k+1) = C C(k)

  + t from Lemmas 30 and 29.Under Assumptions 1 and 2, we prove that after t 1 , we have|B t -b * | ≤ ∆ on E ∩ {N t ≥

	|v -Vt | ≤ + t where
	+ t = 2αγ log t F (b 1 4α F (b

* )t from Lemmas, 16,17 29 and |U (b * ) -U (B t )| ≤ 6 t ≤ 6 * )t}, so that we will be able to use the boundedness of the density after this time step.

When F satisfies assumption 1, U is unimodal, as shown in the proof of Lemma 3, and so if U

  Theorem 33 Under Assumptions 1 and 2, R T ≤ O(T 3/8 log T ).ProofFrom Lemma 31, we have that |b * -B t | ≤ 1/ √ c U 6 + t , on E ∩ {N t ≥ 1 4α F (b * )t}}. Therefore, we can apply Proposition 32 with δ t = 1

	≤ ≤	6 c U 6 c U	e 2 t 2c f δtη 2 C f δ t log M e 2 t t 2c f + t η 2 + t C f δ t log M e 2 t √ t 2c f η 2 t +	2 log( t 2c f δtη 2 ) c U t + 2 log( M t 2c f + t η 2 ) + c U 2 c U t + 2 log( M t √ t 2c f η 2 ) c U t + 2 c U (2C f + 1)δ t (2C f + 1)δ t 2 c U (2C f + 1)δ t + t 2αγ log T + t F (b √ c U 6 + t with M = √ c U √ 6

t log * )t .

where the last inequality stems from that fact that 1/

+ t = F (b * )t 2αγ log t ≤ √ t since α, γ ≥ 1.

  e 2 t Therefore |B t -b * | 2 ≤ ) := t 2 on E ∩ {N t ≥ 1 4α F (b * )t}. On this event, U (b * ) -U (B t ) ≤ C U (b * -B t ) 2Fast Rate Learning in Stochastic First Price BiddingWe use the following decompositionR T ≤ T × P(E c ) + ≤ T × P(E c ) + max(t 0 , t 1 , t 2 ) + ≤ T × P(E c ) + max(t 0 , t 1 , t 2 ) + ) + max(t 0 , t 1 , t 2 ) +

	√ 2c f η 2 We also have, for all t, t ∀t ≥ ( M 2c f ) 1 4 , 2 c U (2C f + 1)δ t 2γα log T t ≤ 2 log( M t 2 t 6 √ 8 C f c 5 4 U √ t 2c f ) c U t F (b * )t ≤ 2 c U (2C f + 1) δ t log t t ≤ 16 c U log t = t 2γα 24(72αγ) c 5 4 . F (b * ) δ t log t 1 8 t = 2(72αγ) 1 4 c 3 2 1 4 (2C f + 1) 2γα F (b * ) (log t) C f 1 8 t 1 4 24(72αγ) 1 8 √ C f c 5 4 U F (b * ) 1 8 + 16 c U + 2(72αγ) 1 4 c 3 2 U F (b * ) 1 4 (2C f + 1) 2γα F (b * ) 1 8 ability 1 -1 t , for t ≥ max( M e 2 2c f 1 4 , ( M 2c f ) 1 t=1 E[S t 1{E}] T t=max(t 0 ,t 1 ,t 2 ) E[S t 1{E}] T t=max(t 0 ,t 1 ,t 2 ) P(E ∩ {N t < 1 4α F (b * )t}) log 2 t t 5 4 1 4 log t t log t t 5 8 with prob-. + T t=max(t 0 ,t 1 ,t 2 ) E[S t 1{E ∩ {N t ≥ 1 4α F (b T t=max(t 0 ,t 1 ,t 2 ) P(E ∩ {N t < 1 4α F (b + T t=max(t 0 ,t 1 ,t 2 ) C 0 log t t 5 8 + T t=max(t 0 ,t 1 ,t 2 ) 1 t T t=max(t 0 ,t 1 ,t 2 ) P(E ∩ {N t < 1 4α F (b * )t}) + C 0 8 3 T 4 T 2 ) + 8α F (b * ) + 8 3 C 0 T 3 8 log T.

U F (b * ) U F (b * ) * )t}}] ≤ T × P(E c * )t}) + T t=max(t 0 ,t 1 ,t 2 ) C U E[(b * -B t ) 2 ] ≤ T × P(E c ) + max(t 0 , t 1 , t 2 ) + T t=max(t 0 ,t 1 ,t 2 ) P(E ∩ {N t < 1 4α F (b * )t})

≤ T × P(E c ) + max(t 0 , t 1 , t 2 ) + 3 8 log T + log T ≤ log T + 4e(γ -1) log T (T ) 2-γ + max(t 0 , t 1 , t

  We can derive the following bounds• β 3,t ≤ β 1,t since δ

					t	√ 2c f 2tK 2 t 2			≤	6 8C f c U	δ	(k) t log t t	:= C 1	δ t log t (k) t	:= C 1 β 1,t .
		∀t ≥ ( M K 2 2c f )	1 4 ,
					2 log( M K 2 t 2 t √ 2c f c U t	2t	)	≤	16 c U	log t t	:= C 2	log t t	:= C 2 β 2,t .
	We also have, for all t,
	2 c U	(2C f + 1)δ	(k) t	2αγ log T F (b * )t	≤	2 c U	(2C f + 1)	2γα F (b * δ t (k)	log t t	:= C 3 δ	(k) t	log t t	:= C 3 β 3,t
					(k) t	≤ 1.

• β 2,t ≤ β 1,t since δ (k) t = min(1, C (k) log(t)t -u k ) ≥ log t t .

Proof Let 0 < v 1 < v 2 < 1. We have U v 2 ,F (b * v 2 ,F ) -U v 2 ,F (b * v 1 ,F ) ≥ 0 and U v 1 ,F (b * v 1 ,F ) -U v 1 ,F (b * v 2 ,F ) ≥ 0, by definition of b * v 1 ,F and b * v 2 ,F . By summing these two inequalities, U v 2 ,F (b * v 2 ,F )-U v 1 ,F (b * v 2 ,F )-(U v 2 ,F (b * v 1 ,F )-U v 1 ,F (b * v 1 ,F )) ≥ 0. Hence (v 2 -v 1 )(F (b * v 2 ,F ) -F (b * v 1 ,F )) ≥ 0.We then prove the result by contradiction, by assuming that b* v 1 ,F > b * v 2 ,F . Then F (b * v 1 ,F ) = F (b * v 2 ,F), since F is non decreasing. In this case,

Acknowledgments

We would like to thank Adverline for accepting to provide us with the bidding data on their inventories and Xandr for making this data transaction possible. We are very grateful to them for their support on this project. Aurélien Garivier acknowledges the support of the Project IDEXLYON of the University of Lyon, in the framework of the Programme Investissements d'Avenir (ANR-16-IDEX-0005), and Chaire SeqALO (ANR-20-CHIA-0020).

J. Weed, V. Perchet, and P. Rigollet. Online learning in repeated auctions. In Conference on Learning Theory, pages 1562-1583. PMLR, 2016.

Supplementary Material

Outline. We prove in Appendix A all the results pertaining to Section 2 apart from Theorem 2, which is proved separately in Appendix B. In Appendix C, we introduce preliminary results necessary to analyze the regrets of the algorithms presented in main body of the paper. Appendix D contains all the proofs of the results of Section 3, while the theorems of Section 4 are proved in Appendix E. A figure related to Section 5 is presented in Appendix F.

Notation.

• In the following we write

T ) when there is no ambiguity.

• b(q) denotes F -1 (q).

• V (n) := 1/n n s=1 V (s) is the mean of the n first observed values.

• We set F t = σ((M s , V s ) s≤t ) be the σ-algebra generated by the the bid maxima and the values observed up to time t.

Appendix A. Properties of first-price auctions

We first observe that the algorithm overbids (B t > b * ) when F and v belong to their confidence regions

because we assume that we are on E. Note that if t > t 0 , then

thanks to Lemma 21, and

which concludes the proof.

Lemma 29 ∀t > t 0 ,

with probability 1 -η (k) 1 Kt . This yields

Proposition 35 Assume that t and F satisfy the assumptions of Proposition 32. If t >

Proof The proposition follows from using an induction argument based on Lemma 34. We can initiate an induction argument with δ

), thanks to Lemma 31. The fact that u k and C (k) as defined as in Lemma 34 satisfy u k+1 = 1 4 (1 + u k ) which yields

and

1 4 which yields

where

. Hence R T ≤ O(T 1/3+ ).

Appendix F. Further figures

We present in Figure 10 the histogram of the normalized data used to simulate the real-world experiment.