No-regret Learning in Repeated First-Price Auctions with Budget Constraints
Authors: Rui Ai
Chang Wang
Chenchen Li
Jinshan Zhang
Wenhan Huang
Xiaotie Deng
Venue: Submitted to ICLR 2023 (2023)
Keywords: first-price auction
budget
no-regret learning

Abstract: Recently the online advertising market has exhibited a gradual shift from second-price auctions to first-price auctions. Although there has been a line of works concerning online bidding strategies in first-price auctions, it still remains open how to handle budget constraints in the problem. In the present paper, we initiate the study for a buyer with budgets to learn online bidding strategies in repeated first-price auctions. We propose an RL-based bidding algorithm against the optimal non-anticipating strategy under stationary competition. Our algorithm obtains 
$\widetilde O(\sqrt T)$-regret if the bids are all revealed at the end of each round. With the restriction that the buyer only sees the winning bid after each round, our modified algorithm obtains $\widetilde O(T^{\frac{7}{12}})$-regret by techniques developed from survival analysis. Our analysis extends to the more general scenario where the buyer has any bounded instantaneous utility function with regrets of the same order.

Under review as a conference paper at ICLR 2023
NO-REGRET LEARNING IN REPEATED FIRST-PRICE AUCTIONS WITH BUDGET CONSTRAINTS
Anonymous authors Paper under double-blind review
ABSTRACT
Recently the online advertising market has exhibited gradual shift from second- price auctions to first-price auctions. Although there has been line of works concerning online bidding strategies in first-price auctions, still remains open how handle budget constraints in the problem. In the present paper, we initiate the study for a buyer with a budget to learn her online bidding strategies in repeated first-price auctions. We propose an RL-based bidding algorithm against the optimal non-anticipating strategy under stationary competition. Our algorithm obtains ((VT) if the bids are all revealed at the end of each round, where O(-) is variant of the big-O that hides logarithmic factors. With the restriction that the buyer only sees the winning bid after each round, our modified algorithm obtains Ö regret by techniques developed from survival analysis. Our analysis extends the more general scenario where the buyer can have any bounded instantaneous utility function with regrets of the same order. Simulation experiments show that the constant factor inside the regret bound is rather small.
INTRODUCTION
There has been extensive growth in the online advertising market in recent years. It was estimated that the volume of online advertising worldwide would reach 500 billion dollars in 2022 (Statista (001)) In such market, advertising platforms auctions allocate ad opportunities. Typically, each advertiser has a limited amount of capital for an advertisement campaign. Therefore, consecutive rounds of competition are interconnected by budgets of participating advertisers. Furthermore, each advertiser has very limited knowledge of 1) her valuation of certain keywords and 2) the competitors she facing. There are many works being devoted studying algorithms for learning strategies for optimally spending the budget in repeated second-pris -price auctions (see Section
In practice, on the other hand, we have witnessed numerous switches from second-price auctions to first-price auctions in the online advertising market. A recent remarkable example is Google AdSenses' integrated move at the end of 2021 (I..C) 202T). Earlier examples also include AppNexus, Index Exchange, and OpenX (Sluis) 2017). This industry-wied shift is due to various factors including a fairer transactional process and increased transparency. Therefore, the shift to first-price auctions brings about major importance the following open question which is barely considered in previous works:
How should budget-consttraieed advertisers learn to compete in repeated first-price auctions?
This paper thus initiates the study of learning to bid with budget constraints in repeated first- frst-price auctions. It has been noted that the application of first-price auctions with budgets is not limited to online advertising mentioned above. Traditional competitive environments like mussel trade in Netherlands (van Schaik et al. 200T), modern price competition, and procurement auctions (e.g. U.S. Treasury Securities auction (Chari and Weber 1992)) are examples as well.
Challenges and contributions
The challenges in this setting are two-fold.
The first challenge relates to the specific information structure of first-price auctions. In practice, it is often the case that only the highest bid is revealed to all participants (Esponda 2008). This is known censored-feedhack or informational version of winner's 's curse in literature (Capen et al. 1971).

---

Under review as a conference paper at ICLR 2023
This affects the information structure of learning since the buyer learns less information when she wins. This makes the problem challenging compared to standard contextual bandits (c.f. Section I.I].
The second challenge is more fundamental. It is known that the strategy in first-price auctions is notoriously complex to analyze, even in the static case (Lebrum 1996). To get an intuitive feeling of this difficulty in our problem compared to repeated second-price auctions. Let us consider the offline case where the opponents' bids are all known. Given the budget, the problem for second-price auctions can be reduced to pure knapsack problem, where the budget regarded weight capacity and prices as weights. This structure enables mature techniques including duality theory to be applied to study the benchmark strategy. Pitifully in first first-price auctions, since the payment depends on the buyer's s own bid, the previous approach/bent brroochh/bencmark is not directly usable. We provide a concrete example to further illustrate such difficulties.
Example 1.1. Consider case where the buyer's value v follows a uniform distribution on [0.4,] 1] and the highest bid m of her opponents follows uniform distribution on 0.5). The time horizon T and the buyer's budget B 0.5l. The first-best benchmark (an anticipating strategy that knows her values and her opponents' bids) can be viewed as a knapsack problem, which is
T Σ (ve (vee-be) (ve-bb)11
E UNFT m
subject to
Elanzmoh S B (ir))-i (m=))=
bI...bbr
where Uy is her value and my is her opponents' highest bid at time t.. The buyer wants determine each be to maximize the revenue. In hindsight, we need to pay as close to m, as possible. Using 0.45T. On the contrary, the optimal non-anticipatin bidding strategy in a first-price auction is to bid and the utility is T 18[1 (22m) 3 0.261. There is already an (2(T)) separation between the first-best benchmark and the ideal case with full information.
the theory of knapsack, the utility is T [ (o2m) - -m)]=
This example shows that simple characterization of the optimum in Balseiro and Gur (2019) is not applicable to our problem. Furthermore, it remains unclear what methodology can be applied in first-price auctions with budgets. The state-of-the-an adaptive pacing strategy downgrades to truthful bidding the budget increases, in first-price auctions, it may result in near-zero reward and thus cannot have any theoretical guarantee (see (Balseiro and Gur 2019 $2.4) for further discussions).
The present paper takes the first step combat the challenges mentioned above with dynamic programming approach. Correspondingly, our contribution is also two-fold:
We provide an RL-based learning algorithm. Through the characterization of the optimal strategy. we obtain O(VT)-regret guarantee for the algorithm in the full-feedback case In the censored-feedbace setting, by techniques developed from survival analysis, we modify our algorithm and obtain regret of +TT+)
1.1 RELATED WORK
Repeated second-price auctions with budgets There is a flourishing source of literature on bidding strategies in repeated auctions with budgets. Through the lens of online learning, Balseiro and Gur (2019) identify asymptotically optimal online bidding strategies known as pacing (a.k.a. bid-shading in literature) in repeated second-price auctions with budgets. Inspired by the pacing strategy, FFajoolct and Jaillet (2017) develop no-regret non-anticipating algorithms for learning with contextual information in repeated second-price auctions. Another line of works that uses similar techniques in the present paper includes Amin et al. (2012): Tran-Thank, et al.] (2014); Gummadi et al. (2122). Gummadi et al. 2012) and Amin al. (2012) study bidding strategies in repeated second-price auctions with budget constraints, but the former does not involve any learning and the latter does not provide any regret analysis (their estimator is biased). TTan-TTaan et al. (2014) derive regret bounds for the same scenario but the optimization objective is the number of items won instead of value or surplus. Baltaoglu et (2017) also use dynamic programming to tackle repeated
1 algorithm is anticipating bid selection depends on future observations, see Flajolet and Jaillet 2017). Thii is especially practical in public-sector auctions Chari and Weher 1992] as regulations mandate all hids to he revealed.
2

---

Under review as a conference paper at ICLR 2023
second-price auctions with budgets. However, they assume per-round budget constraints and their dynamic programming algorithm is for allocating bids among multiple items. Again, we emphasize that prior work has been done in repeated first-price auctions with budgets since the structure of the problem (compared to second-price variants) is fundamentally different (recall Example 1.1
Repeated first-price auctions without budgets Two notable works concerning repeated first-price auctions are Han et al. (2020b) and Han et al. (2020a). Han et al. (2020b) introduce a new problem
called monotone group contextual bandits and obtain an O(vTIn" T) -regrtt algorithm for repeated first-price auctions without budget constraints under stationary settings. This bound is improved to
) by Achddou al. (2021) with additional assumptions on distributions. Haan et al. (2020a) concentrate on adversarial setting and develop a mini-max optimal online bidding algorithm with
+
O(yT In 7') regret against all Lipschitz bidding strategies. BBaanidiiyuru et al. (2021 1 consider the
problem in a contextual setting. crucial difference is that in the present paper, budgets are involved thus the algorithms from previous works are not directly suitable for our needs.
Bandit with knapsack From the bandit side, BBdanidiyuru et al. (2013) develop bandit algorithms under resource constraints. They show that their algorithm be used in dynamic proeurement, dynamic posted pricing with limited supply, etc. However, since the bidder observes her value before bidding in our problem, results by [Badanidiyuru et al.] (2013) cannot be directly applied to our setting. Our setting also relates to contextual bandit problems with resource constraints (Badanidyyruu et al.] 2014 Agrawal and Devanur, 2016) Agrawal al., 2016). Nevertheless, applying this contextual bandit approach requires discretizing the action space, which needs Lipschitz continuity of distributions. Our approach does not rely on any continuity assumption. Further, the
performance guarantee (typically Ó(T3), )) is worse than ours, It also does not fit into our information structure when the feedback is censored.
2 PRELIMINARIES
Auction mechanism We consider a repeated first-price auction with budgets. Specifically, we suppose that the buyer has limited budget B to spend in a time horizon T S +00 (can be unknown to her) rounds. At the beginning of each round / = 1,2,... ..... T, the bidder privately observes a value ve for a fresh copy of item and bids b, according to her past observations h, and value e, Denote the strategy she employs history h; to a bid. Let my be the maximum bid of the other bidders. Since the auction is a first price auction, if by is larger than m,, then the buyer wins the auction, is charged b, and obtains utility of it by; otherwise, she loses and the utility is O. Therefore, the instantaneous utility of the buyer is
(vr, Be, h.) + be, which maps her current budget B,, value and past
It (v2- bx) (b.22m.)
The exact information structure of history the buyer observes is dictated by how the mechanism reveals my, In full generality, we assume that the feedback is censored, i.c. only the highest bid is revealed at the end of each round and the winner does not observe my exactly. This is considered to be an informational version of winner's 's curse (Capen et al. 1971) and is of practical interest (Esponda 2008). For the purpose of modeling, we suppose that ties are broken favor of the buyer but this choice is arbitrary and by no means a limitation of our approach.
Next, we state the assumptions on m, and u. Without loss of generality, we assume that by my, Vr are normalized to be in [0, 1). In the present paper, we consider stochastic setting where my and o, are drawn from some distributions F, G unknown to the buyer, respectively, and independent from the past. We will also refer to the cumulative distribution functions of F, G with the same notations. No further assumptions will be made on F, G. Now, the expected instantaneous utility of the buyer at time with strategy is
R (Ve, bx) = E [ril = (ve - F(b.).
To argue for the reasonability of this assumption, note that although other buyers may also involve learning behavior, it is typical that in real advertising market, there are large number of buyers (Kahng et al., 2004). The specific buyer only faces a different small portion of them and is completely oblivious of whom she is facing in each round. Therefore, the buyer's sole objective is maximize
3

---

Under review as a conference paper at ICLR 2023
her utility (instead of fooling other buyers) and by the law of large numbers, the price m, and value 2t the buyer observes are independent and identically distributed at least for period of time
Buyer's target and regret The buyer aims at maximizing her long-term accumulated utility subject to budget constraints. Recall that the instantaneous utility of the buyer is Tr = (vr - bx) (b.2 The payment o b, 1 [b,2m²) } and the budget will then decrease accordingly as the payment incurs. She can continue to bid as long as the budget has not run out but must stop at
T" = min 1 1, min SIEN:
Σ G= 1++11 +1 T=1
The buyer's problem now becomes determining how much bid in each round to maximize her accumulated utility. In line with works Gummadi et al. (2012); Golrezaei et al. (2019); Deng and Zhang (202T), the buyer adopts a discount factor E (0, 1). She takes discounts since she does not know T or T" Discount factors can be interpreted to be the estimate of the probability that the repeated auction will last for at least rounds (Devanur et al.] 2014; Drutsa 2018). It means
that the process will terminate each round with probability economic side, in important real-world markets like online advertising platforms, buyers are impatient for opportunities since companies of different sizes have different capabilities. Discount factors Al model how impatien the buyer is in (Drutsa 2017 Vanunts and Drutsa, 2019). Now the buyer's optimization problem is to determine a non-anticipating strategy for the following:
À (Uehara et al.) 2021). On the
T x
max 77
E FT m T
1
subject
(1.2m.) S B V(UD (mo)
where b, = TV2, Br, h2). Here, v = (U1,..., uT) denotes the sequence of private values the buyer observes, and m == (m...... my) is the sequence of the highest bids of the other bidders. V (B, t) denotes the expected accumulated utility using strategy æ with budget B and starting from time t. Let n²" denote the optimal bidding strategy with the knowledge of the underlying distributions F and G. The corresponding expected accumulated utility is V (B, (We sometimes use ((,,.) to
represent V* (+--) for convenience in the rest of the paper.)
We now come to define the regret. First, write the per-episode revenue suboptimality for each round t
(ubOpt((TT) = V= t) V (Bi, t),
where ne is the strategy used in round f. Our evaluation metric is then the sum of suboptimality for t T, namely
T
Regret (T) = E
(mt)
(1)
1=1
where the expectation is taken over the trajectories of the achievement of u and the realization of others' bids inexplicitly.
The definition of regret comes from traditional reinforcement learning (RL) literature of infinite- horizon discounted model (Kaelbling al. 1996). The definition is also inspired by the recent advances in Yang et al. (2021); He et al. (2021) Liu and Su (2020); Zhou et al. (202T). Zhou et al. (2021) call cumulative error. reflects the suboptimality for n. learn the optimal valuation of attending the auction.
In the most common scenario, such as Balseiro and Gur 2019) the budget constraint is linear to time horizon T, i.e. & J (1)). Therefore, a bidder has an expectation that she will win for O(T) rounds.
"This assumption has support from experimental evidence (Pin and Key 2011 can also be theoretically justified using mean field asymptotics. Please also see Han et al. (2020b) for another justification.
see|Han
"As an additional explanation, in budget-constrained first-price auctions, the bidder always bids below equal her value. So she very sensitive to the market price. However, by not winning the auction at certain price, the bidder creates a future opportunity to win an equivalent auction at a lower price. The use of a bid discount factor adds flexibility to tune this behavior. As the bidder has preference for present utility over future utility, the discount factor moderates the extent of underhidding that she finds to be optimal, which makes the model more general.
4

---

Under review as a conference paper at ICLR 2023
With sub-optimal policy, it is easy to suffer (T) regret which is intolerable for bidders. It leads to the challenge to achieve sublinear regret in first-price auctions and we design algorithms to answer the question.
BIDDING ALGORITHM AND ANALYSIS
In this section, we present our bidding algorithm and the high-level ideas in the analysis of regret. We first consider the case where the feedback is not censored, i.e. the buyer is aware m, no matter whether she wins or not. Then we extend our algorithm to the case where the feedback is censored with techniques developed from survival analysis.
3.1 FULL FEEDBACK
When F and G are known, the buyer's problem can be viewed offline. The technical challenge lies the observation that even when the distributions are known, the buyer's problem cannot be directly dynamic programming approach
analyzed as knapsack problem. To tackle this challenge, to solve the problem. In particular, the optimal strategy π satisfies the following Bellman equation:
ba [Br, v) E arg max (v: - b) + (V b, r + ()) + (V t + 1)(1 F(b)),
b
V(B,, = El( + - 7 + 1 + AV + F(6))(()),
for all 7 N and 0 5 B, < B. Note that for any B, < O, ((B. -00 By choosing appropriate initialization conditions, we can solve the equation recursively and obtain the optimal bidding strategy together with the function (:,.). The above recursion also characterizes the optimal solution, which will be used in the analysis later.
When the buyer does not have the information of and G, she can learn the distributions from past observations. Therefore, it natural maintain estimations F and G of the true distributions. Our algorithm for the hull-feedback case is now depicted in Algorithm To ease technical loads, first assume the knowledge of and only estimate F' in Algorithm Later, we will add the estimation of
G' and its analysis is presented in Theorem 3.2
Algorithm Algorithm for the full-feedback case
C1 is an arbitrary positive constant 2: Initialize the estimation f' of F to uniform distribution over [0, 1] and B +- B
1: Input: Initial budget B and constant C1
3: for = ... do
4: Observe the value 02 in round
5: Let to be the smallest integer that satisfies A + I-N
Vi Vp is algorithm's estimation of V
6: Set V (Bro (u) = 0 for any B.
7: for T = to, tu 1....,
8:
(B,, + [(v b) + (V + f)))f(b + (V, 1)(1 - F(b))
9:
Solve the optimization problem by f- arg max, & (B,
V T) + EunolQ, B,, T, T,6;)]
end for
12: Place bid b, +- arg max, Q,, B1,
13: Observe mz Ct and r, from this round of auction and update F(x) = - [m,
B + Be- Gr If Be+1 S then halt.
15:
end for
Similar to prior work (Amin et al. 2012), Algorithm 1 performs exploration and exploitation simultaneously. The buyer initializes the estimation of F uniform distribution (Line 2 At round 6, the buyer observes her valuation. Then, she uses her estimation of /' to solve the dynamic programming problem recursively to obtain an estimation of the optimal bid (Line -ine 11 To
For the non-trivial case B < T, this be solved in O
(1-116) time with only O(T 1 loss (sce, c.g.
74.5
Chow and Tsitsikiis 1989).
5

---

Under review as a conference paper at ICLR 2023
provide base case for recursion, note that for sufficiently large to t. Vp(:, tu)'s impact to Vp(t,t) is negligible due to the discount Xo-t Therefore, the buyer can approximate (;(; with zero for to (Line 55. Finally, the auction proceeds with my, Tr, c revealed and the buyer updates her information accordingly (Line Line I4p.
Analysis of regret To analyze the algorithm, we first assume that Algorithm I knows the distribution G exactly and establishes the regret. Then add the contribution of the estimation of F. Theorem 3.1. Under the circumstance that F is unknown, the worst-case regret of Algorithm Ō(y Ö(VT), where the regret is computed according to Equation (1. Explicitly, if we take C1 1,
(Tgren(T) < (4vln(v21)
1 Aj3 1 1 +T+1.
To show an example of the application of the result, let us take the budget B to scale linearly with T as in Balseiro and Gur 2219); Flajolet and Jailler (2017). Specifically, assume that T < +00 and there exists a constant 3 such that the budget B = 3r, then we establish that the regret is Õ(VT) in this special case. Indeed, under this condition, we can simply set to T + and Ve(Br+I. T + for any BT+1 in Algorithm| | Therefore, C₁ and the worst-case regret
bounded by
I+A (I-
VT+1. +1.
Next, we deal with the case where G is also initially unknown. Based on Algorithm|] 1 we additionally maintain estimation G of G' based past observations of valuations. G is initialized to be uniform distribution and will be used to solve the dynamic programming problem (see Line of Algorithm 2 Using similar techniques as before (with more work), we obtain the following theorem. Theorem 3.2, Under the circumstance that F, G are both unknown, it holds that the worst-case regret of Algorithm uusng empirical distribution functions estimate F and G is Ö D(VT). Explicitly, if we take C1
6(1 + RTg S (VIn(2T)
X) 1- VT+1
3.2 CENSORED FEEDRACK
In this subsection, we deal with the case that the buyer can only see the winner's bid after each round. In other words, the feedback is left-censored. Concretely, the buyer's observation is
Or max(bb, me).
When she wins, the exact value of m, is not revealed. The buyer only knows that m, is smaller than her bid in the current round. To estimate the distribution of m, there is classical statistics (KM estimator) developed by Kaplan and Meier (1958) for the estimation of F' in this scenario. However, the KM estimator assumes the sequence (me)i= deterministic, which does not fit our needs. Although Suzukawa (2004) 's extension allows random censorship, it requires independence between b, and m, which is not realistic since we use the estimated distribution place bids.
To tackle this problem, we first introduce an estimator proposed by Zeng (004) denoted by F, to take place of the previous empirical distribution used in Algorithm
Estimation procedure We now present the procedure for estimating F under censored feedback. It suffices to estimate the distribution function of 1 - my which is right-censored by 1 by. Let Vi = min(1 - m,, b,), r = 26)) The observations can now be described as (ys, rt, h4 )
Roughly speaking, to decouple the dependency between m4 are independent conditioning on ht- Intuitively, the history he provides information for getting enough effective samples for M4, Next, we establish models to estimate the hazard rate functions" of 1 1- m4 1 - b, using h,, With the hazard rate functions, we use the maximum likelihood method with kernel to compute the final estimation F; and obtain Equation
the fact that b, and my
1(x) Thhe hazard function of random variable X with p.d.f. and c.d.f. Fis HisH)(z) I-F(3

---

Under review as a conference paper at ICLR 2023
Details follow. We initialize with a sequence (bandwidth) (at) such that los" to; 0, ta
00, ta + 0 as t - +oo and symmetric kernel function ((,,)) C2 (RR) with bounded gradient. Now, at each time t, we compute two vectors Bt. Y which maximize each of the following likelihood functions (these can be regarded loss functions of the estimation that aim optimize)
f(3) = Σ Fr
Bh log Σ M:
eB
.9
Σ ry 7 7 log
Σ 2r2
e
We arbitrarily pad hi:.... hy with zeros to make their length the same (we will show that this without loss of generality in moment). Compute Z, = (3, h Ye h₂) The survival function
of 1 my or equivalently the cumulative distribution function of my, is estimated based on Zeng (2004)* 's estimator
(((x) - -
(1 11- "-E Σ K((Z, Zmm /an))/)))))))))()) [
K((Z,- - 2;)/an) (1;
Now, we are ready to apply the estimator to design the algorithm for the censored-feedback case. Note that the new estimator's convergence rate slower than that for the full-feedback case. Therefore, compared to Algorithm [] Algorithm 2 is now multi-phase algorithm. The algorithm only updates the estimation of F at the end of each phase (see Figure for illustration). The other elements of each phase Algorithm are similar to Algorithm
Algorithm 2 Algorithm for the sensored-feedback case
b C1 is an arbitrary positive constant 2: Initialize the estimation f of F and the estimation G of G to uniform distributions over [0, 1]
Input: Initial budget B and constant C1
3: B1 <- B
4: for Phase i 1, 2...... do > Phase i (i 1) lasts for 2 rounds. Phase lasts for 2 rounds
5: for each t in the time interval of round i do
6: Observe the value i in round
7: Update G(x)
Σi= 1 Sn)
8: Let to the smallest integer that satisfies fo-t
1-X 9 Vt
9:
Set V (o) 0 for any Bi,
VE G. is algorithm's estimation of V
10:
for r = to, to - 1,..., do This loop can be moved to the end of each phase to reduce the invocation time from to In
11:
Qp.c(B,,,,bl < [[v + AV - b, b.
1)(1
F(b))
12:
Solve the optimization problem 02 mrg,ax, (p.c(Br,7.b))
13:
V VB,,(B,,T) + Em-alQ [Q (Br, b;)]
14:
end for
15:
Place a bid by f- arg max, Qp (Br, 6) Observe Ot, Ct and r, from this round auction If B < 0 then halt.
16:
17:
B + B, end for
18:
19:
Update F using the estimator specified in Equation (3) with data observed before this phase
20:
end for
Analysis of regret To analyze the performance of Algorithm 2 we will prove a series of lemmas on the estimation error of Equation (3) We concentrate the performance of the estimator since this is the major difference between Algorithm and Algorithm In particular, our proof relies on the following convergence result.
Lemma 3.3 (Zeng). Let Fr, be the estimation of after using n observations. We have
Vn(f, -x F(1 x)) = B(x) in e 1)),
where B(x)) is a Gaussian process.

---

Under review as a conference paper at ICLR 2023
Estimate F using Equation 33)
Estimate F using Equation
Phase 1
Phase k
Phase A
Length 2
Length 2
Length 2
Estimate F using Equation (3)
Schematic representation of the phases in Algorithm of F the end of each phase.
Figure I:
Algorithm
updates its estimates
Before proceed apply the lemma, we verify series of prerequisites mentioned in Zeng 2004 to make sure it holds. First, we make sure that conditioning on h., the random variables my and 1 - b, are independent. Indeed, b, is completely decided by h4 and m, is independent of h Second, we note that the maximizer shown in Equation (2) is essentially doing Cox's proportional hazards regression analysis. To establish consistency of the estimator,
show that least of my = 1 - and 1 - b, follows Cox's 's proportional model. That is to say, there exists / and function fyy such that the hazard rate function of m, or 1 bç conditioning on h exactly follows
( h4) f h..
Equation (4) holds for my. In fact, taking 3 0 and f() ('(1-)) F(1 suffices. Since we take G = 0, consistency establishes regardless of the way we pad ht.
Next, consider some phase at time 2 Sts 2n+1 1. The estimation A, computed using the first 2" observed data points. Applying similar techniques for the rate of convergence of empirical process (Norvaiša and Paulauskas 1991). obtain the following lemma the performance of F in
Algorithm 2
Lemma 3.4. Under the update process in Algorithm 2 for any 2n 2
have the
following bounds for the estimation Fy:
[6] - Pr(ssup (B(1-)) b) 2 r) < (n
2
In
b
where M is a constant depending only F and Algorithm
Finally, we now bound the difference between Fn and F with the help of Lemma 3.4
Lemma 3.5. Recall that we use the first 2n data points to estimate F. Under the update procedure of Algorithm for any 2n S t t 2n+1 1, with probability at least 1 - T da (2
sup [(x) F(x) s 12 T) - T
where C3 is an absolute constant.
With Lemma 3.5 in hand, we now have
Theorem 3.6. Under the circumstance that F, G are both unknown and the feedback is censored, the worst-case regret of Algorithm 2 is Ö(T Explicitly, if we take C1 = 1,
9 + A) In +) 2(1 AJ3
T ( 2(1+ 4
RTg <
VT.
Remark 3.7. The setting in Han et al. (2020b) is a special case of ours, where there are no budget constraints and X 0 (thus removing the T-x factor in our results). The buyer's 's aim is to maximize (v - Fb) each round. This is equivalent to Vp = in our setting with no need to estimate G, yielding regret Ö(VT) in the feel-bee case and regret Ö(T 14) in the censored-feedbact case. Remark 3.8. The regret-bound looks unusual at a first glance. The reason is that the convergence rate of the estimator is lower than that in the commonly used "Hoeffding type" "Bernstein-type" inequalities. However, due to the information structure, they are not suitable to used our environment our best knowledge.
8

---

Under review as a conference paper at ICLR 2023
4 LOWER BOUND
Here, we discuss the lower bound for the regret under such settings, This will shed light on the optimality gap of the proposed policies.
Full Feedback We have proposed a general solution framework that works for any & where the budget constraint is B = 3T and any discount rate À [0, 1). Note that the general lower bound is no less than the lower bound for a specific case. Consider the case when 3 = and À = 0. Our problem reduces to the case where the buyer essentially does not face budget constraints and is extremely myopic. Under this circumstance, the problem is a multi-armed bandit problem. |Auer et al. (2002) shows that it suffers from @ ((vT)) lower bound. This means that our algorithm is optimal up to logarithmic terms.
Censored Feedback The Õ(VT) lower bound also applies here. However, the upper bound and the lower bound have not matched yet. We leave this as an intriguing open problem as there is a lack of relevant literature to show regret lower bounds under the mnnsored-feedbace case. However, want to provide some evidence that our upper bound is sufficiently good. For example, parallel to our work. Gaitonde al. (2022) extend the pacing techniques class of auction forms including first-price auctions. They obtaín an ( }-regret bounds against the best linear policy under the value-mmaximization objective. Under censored-
information structure with contextual 1/8
valuations, Cesa-Bianchi et al. (0117) show Ö 7-373 }-regret upper bound without budget constraints where d's is the dimension of the context. And similar information and payment structure in Bayesian persuation yield an Ö(Tē) regret bound Castiglioni et al. 2020).
DISCUSSION AND CONCLUSION
In this paper, we develop a learning algorithm to adaptively bid in repeated first-price auctions with budgets. On the theoretical side, our algorithm, together with its analysis of ((VT)) in the full-feedback case and (T }-regret in the censored-fcedben case, takes the first step in understanding the problem. On the practical side, our algorithm is simple and readily applicable to the digital world that has shifted to first-price auctions]
Questions raise themselves for future explorations. We observe here that the limiting case + the optimal bidding strategy in Algorithm 2 is similar to pucing strategy, which relates to the open questior raised in Balseiro and Gur 2019). In the limiting case of X - 1, the optimal bid of Algorithm 2 is of the form 1+2,' where 2; is pacing multiplier that depends only B, and F and can be computed without solving the dynamic programming problem. This observation can be viewed as corollary (Theorem 3. /uummadi et al. 2012). This connection between Algorithm 2 and pacing suggests further investigations. Other immediate open questions include closing the gap between upper and lower bounds for the censored feedback case.
REFERENCES
Juliette Achddou, Olivier Cappé, and Aurélien Garivier. Fast rate learning in stochastic first price bidding. In Asian Conference Machine Learning, pages 1754-1769. PMLR, 2021.
Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29, 2016.
Shipra Agrawal, Nikhil R. Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and extension to concave objectives. In Conference on Learning Theory, pages 4-18. PMLR, 2016.
7 For simulation experiments, please refer to Appendix
'AA question of theoretical and practical interest is how to extend the adaptive pacing approach that is suggested in this paper nontruthful mechanisms such first-price auctions."
9

---

Under review as a conference paper at ICLR 2023
Kareem Amin, Michael Kearns, Peter Key, and Anton Schwaighofer. Budget optimization for sponsored search: Censored learning in MDPs. arXiv preprint arXiv:1210.4847, 2012.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 207-216. IEEE, 2013.
Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. Resourceful contextual bandits. In Conference Learning Theory, pages 1 1109-11344 1134. PMLR, 2014.
Ashwinkumar Badanidiyuru, Zhe Feng, and Guru Guruganesh. Learning bid in contextual first price auctions. arXiv preprint PrXii:2109.03113, 2021.
Santiago R. Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimiza- tion and equilibrium. Management Science, (199))9952-966 2019.
M. Sevi Baltaoglu, Lang Tong, and Qing Zhao. Online learning of optimal bidding strategy in repeated multi-commodity auctions. Advances in Neural Information Processing Systems, 30, 2017.
Edward C. Capen, Robert V. Clapp, and William M. Campbell. Competitive bidding in high-risk situations. Journal of Petroleum Technology, 23(06)):41-653) 1971.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online bayesian persuasion. Advances in Neural Information Processing Systems, 13:16188-16196 2020.
Nicolò Cesa-Bianchi, Pierre Gaillard, Claudio Gentile. and Sébastien Gerchinovitz. Algorithmic chaining and the role of partial feedback in online nonparametric learning. In Conference on Learning Theory, pages 465 481. PMLR, 2017.
V. Chari and Robert Weber. How the us treasury should auction its debt. Quarterly Review, 16(4), 1992.
Chef-Seng Chow and John N Tsitsiklis. The complexity of dynamic programming. Journal of complexity, 5(4):4666488, 1989.
Yuan Deng and Hanrui Zhang. Prior-independent dynamic auctions for a value- aaleemmaxmiizin buyer. Advances in Neural Information Processing Systems, 34, 2021.
Nikhil Devanur, Yuval Peres, and Balasubramanian Sivan. Perfect bayesian equilibria in repeated sales. In Proceedings of the twenty-sixhh annual ACM-SIAM symposium Discrete algorithms, pages 983-1002. SIAM, 2014.
Alexey Drutsa. Horizon-independent optimal pricing in repeated auctions with truthful and strategic buyers. In Proceedings of the 26th International Conference on World Wide Web, pages 33-42, 2017.
Alexey Drutsa. Weakly consistent optimal pricing algorithms in repeated posted-price auctions with strategic buyer. In International Conference on Machine Learning, pages 1319-1328. PMLR, 2018.
Ignacio Esponda. Information feedback in first price auctions. The RAND Journal of Economics, 39 (2):491-508, 2008
Arthur Flajolet and Patrick Jaillet. Real-time bidding with side information. In I. Guyon, U. Von Luxburg, S. Bengio, Wallach, R. Fergus, S. Vishwanathan, and Garnett, editors, Advances in Neural Information Processing Systems, volume 30, 2017.
Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget Pac- ing in Repeated Auctions: Regret and Efficiency without Convergence. arXiv e-prints, art. DxXxv2205.0067.. May 2022.
10

---

Under review as a conference paper at ICLR 2023
Negin Golrezaci, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning: Robust pricing in contextual auctions. Advances in Neural Information Processing Systems, 32, 2019.
Ramakrishna Gummadi, Peter Key, and Alexandre Proutiere. Repeated auctions under budget constraints: Optimal bidding strategies and equilibria. In the Eighth Ad Auction Workshop. volume 4, 2012.
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.04568. 2020a.
Yanjun Han, Zhengyuan Zhou, and Tsachy Weissman. Optimal no-regret learning in repeated first-price auctions. arXiv preprint arXiv:2003.0971 09795,, 2020b.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for
discounted MDPs. Advances in Neural Information Processing Systems, 34:22288-223 -23000, 2021.
Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. Reinforcement learning: A survey.
Journal of Artificial Intelligence Research, 4:237-288 1996.
Kahng, I Yang, Jeong, and A-I. Barabási. Emergence of power-law behaviors in online auctions. In The Application of Econophysics, pages 204-209. Springer, 2004.
Edward L. Kaplan and Paul Meier. Nonparametric estimation from incomplete observations. Journal of the American Statistical Association, 53(282):457-48) 1958.
Bernard Lebrun. Existence of an equilibrium first price auctions. Economic Theory, 7(3):221-443, 1996.
Shuang Liu and Hao Su. Regret bounds for discounted MDPs. arXiv preprint arXiv: arXiv:2002..57738 2020.
Google LLC. Faqs about adsense moving to a first-price auction google adsense help. https goog
77 //support.. goog htt..c//cccceeeeeaaeee/////////0 2022-05-06.
2021. Accessed:
R. Norvaiša and V. Paulauskas. Rate of convergence in the central limit theorem for empirical processes. Journal of Theoretical Probability, 4(3):511-534, 1991.
Furcy Pin and Peter Key. Stochastic variability in sponsored search auctions: observations and models. In Proceedings of the 12th ACM conference on Electronic commerce, pages 61-70, 2011.
Sarah Sluis. Big changes coming to auctions, as exchanges roll the dice on first-price. https //www www.aadexcaanger.cco wwtpp//e...cco///.ooooooooooo cha.orrrrriiiiiicnananeeeeeee coming auctions exc harges-rool-diie--fist-----e
2017.
Statista. Digital advertising spending worldwide from 2019 to 2024 (in billion u.s. dollars). https
w/ww. www.sstttttaa... com wtt.://ttttttttttee33311111
g- wor --worldwides 2021.
Accessed: 2022-05-05.
Akio Suzukawa. Unbiased estimation of functionals under random censorship. Journal of the Japan Statistical Society, 3432):153-17,, 2004.
Long Tran-Thanh, Lampros Stavrogiannis, Victor Naroditskiy, Valentin Robu, Nicholas R Jennings, and Peter Key. Efficient regret bounds for online bid optimisation in budget-limited sponsored search auctions. In 30th Conference on Uncertainty in AI, 2014.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. arXiv preprint arXiv:21 2021.
Frans D. J. van Schaik, Jack P. C. Kleijnen, et al. Sealed-bid auctions: case study. Center for Economic Research, 2001.
Arsenii Vanunts and Alexey Drutsa. Optimal pricing in repeated posted-price auctions with different patience of the seller and the buyer. Advances Neural Information Processing Systems, 32, 2019.

---

Under review as a conference paper at ICLR 2023
Kunhe Yang. Lin Yang, and Simon Du Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1584. PMLR, 2021.
Donglin Zeng. Estimating marginal survival function by adjusting for dependent censoring using many covariates. The Annals of Statistics, 3234):153311555 2004.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted MDPs with feature mapping. In International Conference on Machine Learning, pages 12793- 12802. PMLR, 2021.
12


Reviews:
[{"review_id": "ziEfZCvxbaH", "reviewer": "Reviewer_fj85", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The submission proposes an online learning approach to bidding in repeated stochastic first price auctions with a global budget constraint. The main idea is to approximately learn the distribution of values and other bidders’ top bid, and then solve a DP for the optimal “non-anticipating” strategy assuming values and bids will actually be drawn from learnt distributions.", "summary_of_the_review": "The problem seems of fairly wide interest, but the results given in the submission are not particularly exciting and the techniques aren't novel AFAICT.", "strength_and_weaknesses": "•\tI’m a bit confused by the way the discount factor is presented:\n\no\tIn the context of a global budget across time periods, I’m not sure what the discount factor models.\n\no\tI cannot find where in the definition of SubOpt the discount factor appears\n\no\tOn the experiments, I would like to see what happens with a more aggressive discount factor\n\n•\tI believe that the term “winner’s curse” is used incorrectly. It just means that winners in auctions tend to be the ones who overestimate the true value of the item for sale, so they’re likely to actually make a bad deal. \n\n•\tAre F and G independent from each other? (And if so, what does that model?\n\n•\tYou should clearly define non-anticipating strategies\n\n•\tI’m not sure that the solution to the DP is exactly the “optimal” bidding strategy as you claim: AFAICT it doesn’t account for the noise – e.g. it only satisfies the budget in expectation.\n\n•\tTypo: “worse-case”\n\n•\t$\\frac{1}{2}\\ln(T^2)$  --  Wouldn’t it be easier to cancel the 2 and the 1/2?\n\n•\tDoes the DP really take you T^4.5 time to solve? What did you do in the experiments?\n\n•\tI couldn’t follow (at a high level) what are f and g. \n\n•\tWhat does the \\implies symbol in Lemma 3.3 mean?\n\n•\tIn Lemma 3.4, you want to bound the sup of the learnt and actual distribution. Maybe that’s too strong? You could get a better result by relaxing that?\n\n•\t“regret bound is the best possible…” – can you formalize that claim?\n\n•\tDid you use T=2,000,000 or T=200,000?\n\n•\tThe ~5% regret in experiments seems pretty high. \no\t\\sqrt{T} is roughly 1,000, so that’s 1+ order of magnitudes off\no\tIn the worst case theorem there are some hidden constants, but this is on pretty reasonable distributions and very large T\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "UvHAXxvAUK9", "reviewer": "Reviewer_NJbs", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies the interesting problem of repeated bidding in a stochastic first price auction setting with budget constraints. The paper builds up to the algorithm by first presenting and analyzing the simpler case of (i) only the player's reward distribution is unknown, and (ii) feedback is not censored by the winner's curse. Under these simplifying assumptions, the paper presents a simple algorithm -- estimate the unknown F and bid by solving the Bellman recursion for the optimal bid by using the estimated distribution. The paper then builds up to an elegant phase based solution for the case when the simplifying assumptions are not there. The winner's curse introduces bias in the estimation that the paper proposes to solve the one-sided bias through a kernelized estimator to estimate the hazard function of the unknown distribution. Since the rate of convergence of this estimator is slower, the algorithm is layered and only updates the unknown estimates in phases of exponentially increasing lengths. This phase based algorithm also gives the statistical independence between the estimator's error and the regret, that can be used for analysis. ", "summary_of_the_review": "A well written paper with clear insights and novel contributions on an important problem.", "strength_and_weaknesses": "Strength -- An important problem, very well written paper with the final algorithm built up using simpler ones working under simplifying assumptions. \n\nWeakness -- \n\n1. The buyer interacts with a stochastic environment as opposed to a strategic one. The paper justifies this assumption in the case of large internet market places where due to law of large number effects, the strategic actions of one buyer does not affect the rest. \n\n2. No insights into any lower bounds/reductions. The paper however sheds some light by showing that comparing with the hindsight anticipatory optimal strategy is not productive as even simple cases yields linear regret. Nevertheless, a more principled discussion on lower bounds or reductions is a nice to have.\n\nThat said, the strengths in the paper outweighs the weaknesses.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TCImTypO6g", "reviewer": "Reviewer_s5bF", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper presents a learning algorithm for first price auction with budget constraint. The authors consider an artificial discounted scenario and measure the regret of a learning algorithm as the sum of the suboptimality gap. Their propose two algorithms: the first always observe the highest bid of the others while the second observes the highest bid of others only when it does not win. They show that their algorithm have a sublinear regret.\n", "summary_of_the_review": "The paper is interesting but it does not prove what is claimed, because the regret definition is not adapted.\n", "strength_and_weaknesses": "**Strengths:**\n- The problem studied (learning first-price auction with budget) is of importance, is actual and is challenging.\n- The results seems non-trivial technical and provide non-trivial results\n\n**Weakness:** unless I missed something, I do not think that the regret definition used by the authors is adapted to the problem. It seems to me that designing a low regret algorithm for this problem is not a hard task. This leans me to reject the paper.\n\nMore precisely: the authors introduce an artificial discounted first auction problem with budget constraint with a given discount factor \\lambda<1 that does not depend on the budget B. My problem is that I have the impression that when B is large $(B\\gg 1/(1-\\lambda)$, the optimal policy essentially does not depend on B because the budget will never expire before $\\lambda^t$ becomes too small. To me, this means that a learning algorithm that completely ignore the budget will have a sublinear regret.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GZltx53Nrl", "reviewer": "Reviewer_6CuB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper initiates the study for a buyer with budgets to learn online bidding strategies in repeated first-price auctions. They propose an RL-based bidding algorithm against the optimal non-anticipating strategy under stationary competition. The algorithm obtains T^{1/2}-regret if the bids are all revealed at the end of each round. With the restriction that the buyer only sees the winning bid after each round, the algorithm obtains T^{7/12}-regret by techniques developed from survival analysis. ", "summary_of_the_review": "This paper studies for buyer with budgets to learn online bidding strategies in repeated first-price auctions. The contribution is quite good, but I think the writing should be improvement. I can’t check the correctness. I have some problems about the Theorem results, the bound in the theorem is not consistent with the result in the context.\n\nI vote for a weakly reject as it hasn’t convince me (mainly because of the writting), although I think the results are quite good.", "strength_and_weaknesses": "Strength: This paper initiates the study to learn online bidding strategies in repeated first-price auctions with budgets and shows good sublinear regret.\n\nWeakness: No proof and less explanations for the theorem and equation used (such as the meaning of the Bellman equation used in this paper), so it is quite hard to check the correctness.\nI have an question about the theorem. In theorem 3.1, from the inequation, the regret is \\tilde O (T), but not the \\tilde O (T^{1/2}) shown in the context. Similarly for Theorem 3.2 and 3.6\nTypo: Theorem 3.2 should be Section 3.2 on Page 5\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "75k3_R81pHB", "reviewer": "Reviewer_pUFT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper considers the problem of repeated first-priced auctions with budget constraints, a new model that did not capture attention before. Two scenarios of full feedback and censored feedback are analyzed. For full feedback, the proposed algorithm has a regret of $\\tilde{O}(\\sqrt{T})$. For censored feedback,  the proposed algorithm has a regret of $\\tilde{O}(T^{\\frac{7}{12}})$", "summary_of_the_review": "The score is mainly based on the first item of the weaknesses. I will consider raising the score if the concerns above can be addressed.", "strength_and_weaknesses": "Strength:\n1. The paper is well organized and easy to read overall. The difference between the two scenarios is clearly addressed. \n2. Good discussion on why the prior works do not work for this new setting.\n\nWeaknesses:\n1. It it somewhat disappointing that there is not any lower bound result. Given the model is claimed to be new, I am fine with any conjecture discussion on the lower bound. Without a lower bound, it is hard to see if the upper bound is nontrivial.\n2. Some arguments in the paper are lack of proper citations for support. i). Page 3: 'it is typical that in a real advertising market....'. ii). Page 8: 'Note that by domain knowledge...'", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6xH5czHyEaE", "reviewer": "Reviewer_NGYd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies the first price auction in a repeated setting and with budget constraints. The authors propose some algorithms showing sublinear regret under different levels of knowledge of the learner in the setting. The authors also provide some synthetically generated experiments to check the performances of the algorithm.", "summary_of_the_review": "The paper presents a new algorithm for first-price auctions and provides theoretical guarantees on the regret. The empirical analysis is quite preliminary.", "strength_and_weaknesses": "The paper is mainly theoretical and presents only a few empirical experiments. I think that the topics covered by this work are interesting from an applied point of view. \n\nThe experimental part would have benefited from a real-world example. In particular:\n\"Note that by domain knowledge, most valuations and bids in online auctions follow exponential distributions, so we believe that our simulations can correctly reflect real scenarios\". This statement is not supported by any evidence. I would instead say that the empirical evaluation is preliminary and on synthetically generated data. I think that without evidence you cannot claim that your experiments reflect the real phenomenon of bidding.\n\nWhy not use the dataset with full feedback as a real-world benchmark?\n\nMinor:\nworse-case -> worst-case\nChoosing a name for the algorithm would help to refer it to in the experimental section\nRegarding the \\lambda parameter, did you run a sensitivity analysis on this parameter to understand its impact on the algorithm?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject